Stochastic Systems Group
Home Research Group Members Programs  
Demos Calendar Publications Mission Statement Alumni

SSG Seminar Abstract

A new class of variational upper bounds for graphical models

Martin Wainwright
SSG Doctoral Student

Stochastic processes defined on graphical models arise in a variety of fields, including statistical image processing, coding theory, artificial intelligence, and statistical physics. For graphs without cycles (i.e., trees), there exist well-known and very efficient algorithms for standard problems like inference and parameter estimation. In contrast, these same problems are intractable on graphs with cycles of any substantial size. This difficulty motivates the development of approximate methods.

In this talk, we present a new class of upper bounds on probabilistic quantities (e.g., partition functions, or expectations of functions) for graphs with cycles. These bounds arise from convex combinations of tractable distributions formed by simpler structures (e.g., spanning trees) embedded within the original graph. The problem of optimizing these bounds --- over both tractable distributions and their associated weights in the convex combination --- turns out to have an interesting structure. Moreover, the resultant variational formulation gives a new perspective on the Bethe free energy, which plays an important role in the belief propagation (or sum-product) algorithm.

This is joint work with Tommi Jaakkola and Alan Willsky

Problems with this site should be emailed to