Graphical models, local probability propagation algorithms, and convex duality
Tuesday, Oct. 22, 2002
2:00-3:30 p.m.
Hughes Room
Joint work with Tommi Jaakkola and Alan Willsky, MIT

Probability distributions defined by graphical models are studied and used in a variety of fields, including error-correcting coding, machine learning, communication theory, computer vision, and statistical physics. One important problem is to perform statistical inference on the basis of noisy observations. While there exist efficient and exact algorithms for acyclic graphs, approximate methods are needed for graphs with cycles. Local probability propagation techniques, including the sum-product (belief propagation) and min-sum (max-product) algorithms, are widely used for this purpose (e.g., iterative decoding of graphical codes; image denoising; multiuser detection).

In this talk, we describe how the sum-product algorithm and its generalizations can be understood as seeking a particular reparameterization of a graphical distribution. We provide an intuitive characterization of sum-product fixed points, and more generally, of any local minimum of Bethe/Kikuchi variational problems (Yedidia et al., 2001). We also derive an exact expression for the difference between the approximate and exact marginals for an arbitrary graph, and develop computable bounds on this approximation error. Finally, we briefly describe approximation methods, based on duality theory, that (unlike the Bethe/Kikuchi approach) involve convex variational problems, and give upper bounds on the partition function.

UC Berkeley Networking
Ashwin Pananjady and Orhan Ocal
Last Modification Date: Wednesday, February 10, 2016