Stochastic Systems Group  

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 maxproduct algorithm is an iterative method for the combinatorial problem of determining the MAP assignment in a discrete graphical model. For treestructured graphs, the maxproduct algorithm is wellknown 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, maxproduct is not guaranteed to converge, and (in general) provides only an approximate solution to the MAP problem.
Most previous work on the maxproduct algorithm for graphs with cycles is based on analyzing the computation tree associated with the messagepassing updates. This talk presents a different viewpoint, based on the junction tree representation, that involves reparameterizing distributions in terms of their socalled maxmarginals. 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 maxproduct 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 maxproduct algorithm that perform reparameterization over higherorder cliques.
Problems with this site should be emailed to jonesb@mit.edu