Approximate Inference in Graphical Models: The Fenchel Duality Perspective

Quite a number of problems involving inference from data, whether visual data or otherwise, can be set as a problem of finding the most likely setting of variables of a joint distribution over locally interacting variables. These include stereopsis, figure-ground segmentation, model-to-image matching, super-resolution, and so forth. Inference over locally interacting variables can be naturally represented by a graphical model, however exact inference over general graphs is computationally unwieldy.

In the context of approximate inference, I will describe a general scheme for message passing update rules based on the framework of Fenchel duality. Using the framework we derive all past inference algorithms like the Belief Propagation sum-product and max-product, the Tree-Re-Weighted (TRW) model as well as new convergent algorithms for maximum-a-posteriori (MAP) and marginal estimation using "convex free energies".

Joint work with Tamir Hazan.

Amnon Shashua, The Hebrew University of Jerusalem, Israel

Renew SIAM · Contact Us · Site Map · Join SIAM · My Account
Facebook Twitter Youtube