Stochastic Systems Group
Home Research Group Members Programs  
Demos Calendar Publications Mission Statement Alumni

SSG Seminar Abstract

The max-product algorithm for approximate MAP estimation for graphs with cycles

Dr. Martin Wainwright
Stochastic Systems Group, MIT

Graphical models arise in a variety of fields, including image processing, machine learning, information theory, and statistical physics. Inference problems entail estimating a set of hidden variables on the basis of a set of noisy observations (e.g., computing posterior marginal distributions, or computing the maximum a posteriori (MAP) configuration). Many applications require efficient methods for solving such inference problems (e.g., denoising in image processing; iterative decoding for graphical codes; scene analysis in computer vision; computing ground states in statistical physics; multiuser detection in communication).

The max-product algorithm is an iterative method for the combinatorial problem of determining the MAP assignment in a discrete graphical model. For tree-structured graphs, the max-product algorithm is well-known to compute the exact MAP estimate after a finite number of iterations, and can be understood as a generalization of the Viterbi algorithm. On graphs with cycles, max-product is not guaranteed to converge, and (in general) provides only an approximate solution to the MAP problem.

Most previous work on the max-product algorithm for graphs with cycles is based on analyzing the computation tree associated with the message-passing updates. This talk presents a different viewpoint, based on the junction tree representation, that involves reparameterizing distributions in terms of their so-called max-marginals. We develop this reparameterization idea first in the context of trees, and then show how it extends to graphs with cycles. This perspective allows us to prove several new results about the max-product algorithm, including a characterization of its fixed points, as well as bounds on the error in its assignment. It also leads naturally to generalizations of the max-product algorithm that perform reparameterization over higher-order cliques.

Problems with this site should be emailed to