May 5, 2005: Dr. Martin Wainwright (University of California at Berkeley) Treereweighted Messagepassing Algorithms in Graphical Models: Some Theory and Applications Place: 2328 A.V. Williams Time: 3:30 PM Host: Dr. Alexander Barg Abstract:Graphical models (e.g., factor graphs, Markov random fields) provide a flexible framework for capturing statistical dependencies among large collections of random variables, and are widely used in various fields, including statistical signal processing, coding and communication theory, and machine learning. Central to the widespread use of graphical models are distributed "messagepassing" algorithms (e.g., sumproduct, maxproduct), in which nodes perform local computations and communicate with their neighbors. The purpose of these algorithms is to solve various statistical inference problems (e.g., image denoising, errorcontrol decoding) that arise in applying a graphical model. These methods are wellknown to be exact for trees, but they are also widely applied to graphs with cycles, where they yield approximate answers. To motivate our work, we describe some potential pitfalls associated with applying the standard forms of messagepassing to graphs with cycles (sumproduct: multiple fixed points and instability; maxproduct: misleading outputs). We then describe a novel family of treereweighted algorithms, and present some theoretical guarantees on their behavior for graphs with cycles. The treereweighted sumproduct algorithm has a unique fixed point for any problem, and it can be understood as computing an optimal upper bound on the log partition function. On the other hand, the treereweighted maxproduct algorithm has the desirable property of never deceiving the user; this behavior can be understood in terms of a particular linear programming relaxation of the modefinding problem. We conclude with an overview of some applications of these modified algorithms. Talk based on joint work with: Jon Feldman, Tommi Jaakkola, Alan Willsky.  
