EECS Joint Colloquium Distinguished Lecture Series
     
 

Monday, March 01, 2004
430-438 Soda Hall, Wozniak Lounge
1:30 - 3:00 p.m.

Dr. Martin Wainwright

EECS Dept., UC Berkeley
 
 

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

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.

    Biography:
   

Martin Wainwright received his doctorate in Electrical Engineering and Computer Science from MIT in 2002, and is currently a post-doctoral research associate in the Department of EECS at UC Berkeley. His research interests are centered on issues of modeling, analysis and computation in large-scale stochastic systems, and their applications to problems including statistical signal processing, sensor networks, and error-control coding. He received the 1967 Fellowship from the Natural Sciences and Engineering Research Council of Canada, and the George M. Sprowls award for best Ph.D. thesis from the EECS department at MIT.