Stochastic Systems Group  

Lagrangian Relaxation Methods for Intractable Graphical Models
Jason Johnson
SSG, LIDS, MIT
A graphical model is a multivariate probability distribution defined on a graph. The nodes of the graph represent random variables and the edges represent interactions between variables. We consider the problem of determining the MAP configuration of all variables. In general, this is NPhard. But in graphs with narrow tree width, the problem is efficiently solved by applying the maxproduct algorithm to a junction tree of the graph. Hence, in intractable models, it is natural to consider if we can exploit tractable calculations on thin subgraphs in order to approximate exact inference on the overall graph.
We present a Lagrangian relaxation framework which decomposes the graphical model into a collection of tractable models defined on subgraphs. We develop two approaches to solve the dual problem: The first approach minimizes a sequence of smooth, convex upperbounds on the dual function parameterized by a ``temperature'' parameter which is gradually reduced to zero. This involves a procedure which adjusts Lagrange multipliers so that marginal distributions agree between subgraphs that share nodes or edges. The second approach corresponds to the zerotemperature limit of the first method and reduces to a maxmarginal equalization procedure. We also discuss connections to variational methods developed by M. Wainwright based on spanning trees of a graph and present some preliminary computational results.
Problems with this site should be emailed to jonesb@mit.edu