Computer Science Colloquium

Message-passing algorithms in graphical models and their applications to large-scale stochastic systems

Martin Wainwright
UC Berkeley

Monday, April 19, 2004 11:30 A.M.
Room 1302 Warren Weaver Hall
251 Mercer Street
New York, NY 10012-1185

Colloquium Information:


Richard Cole, (212) 998-3119


Probability distributions defined by graphs arise in a variety of fields, including statistical signal and image processing, sensor networks, machine learning, and communication theory. Graphical models provide a principled framework in which to combine local constraints so as to construct a global model. Important practical problems in applications of graphical models include computing marginal distributions or modes, and the log partition function. Although these problems can be solved efficiently in tree-structured models, these same tasks are intractable for general large-scale graphs with cycles.

In recent years, local message-passing algorithms (i.e., belief propagation, max-product) have been widely used to compute approximate solutions in graphs with cycles. We describe a class of reweighted message-passing algorithms, and illustrate how they can be understood as methods for solving graph-structured optimization problems. These modified algorithms have advantages over standard methods, including unique fixed points and guaranteed upper bounds (reweighted belief propagation), and performance guarantees (reweighted max-product). We discuss applications of graphical models and message-passing to statistical image processing, sensor networks, and error-control coding.

top | contact