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
