Stochastic Systems Group  

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 wellknown 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 sumproduct) algorithm.
This is joint work with Tommi Jaakkola and Alan Willsky
Problems with this site should be emailed to jonesb@mit.edu