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 wide-spread use of graphical models are distributed "message-passing" algorithms (e.g., sum-product, max-product), 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, error-control decoding) that arise in applying a graphical model. These methods are well-known 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 message-passing to graphs with cycles (sum-product: multiple fixed points and instability; max-product: misleading outputs). We then describe a novel family of tree-reweighted algorithms, and present some theoretical guarantees on their behavior for graphs with cycles. The tree-reweighted sum-product 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 tree-reweighted max-product 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 mode-finding 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.