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

Directions: http://cs.nyu.edu/csweb/Location/directions.html
Colloquium Information: http://cs.nyu.edu/csweb/Calendar/colloquium/index.html

Hosts:

Richard Cole cole@cs.nyu.edu, (212) 998-3119

Abstract

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.