Stochastic Systems Group  

Martin Wainwright
SSG Doctoral Student
Stochastic processes defined on graphs arise in a variety of fields (e.g., coding theory; statistical physics; signal processing; artificial intelligence). One important problem is estimating unknown variables on the basis of other observed quantities. For singlyconnected graphs (i.e., trees), there are very efficient algorithms for estimation; however, exact solutions to these same problems are intractable for general graphs with cycles.
We develop a treebased reparameterization framework that provides a new conceptual view of a large class of iterative algorithms for computing approximate marginals in graphs with cycles. Included in this class is belief propagation (also known as the sumproduct algorithm), which can be reformulated as a very local form of reparameterization. More generally, this class includes algorithms in which updates are more global, and involve performing exact computations over spanning trees of the full graph. On the practical side, we find that such tree reparameterization (TRP) algorithms tend to have superior convergence properties to belief propagation (BP), with equivalent or lower cost.
Our framework also provides new theoretical insights into approximate estimation. We analyze the fixed points of the reparameterization operations, and also examine the question of convergence. A fundamental property of reparameterization updates is that they leave invariant the distribution on the full graph, which has a number of important consequences. For instance, it enables us to derive an exact relation between the true marginals on an arbitrary graph, and the approximations provided by TRP or BP. We also develop bounds on this approximation error, which illuminate the conditions that govern performance of these methods. Our results also have natural extensions to approximations (e.g., Kikuchi) that involve clustering nodes.
Problems with this site should be emailed to jonesb@mit.edu