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

SSG Seminar Abstract

Lagrangian Relaxation Methods for Intractable Graphical Models

Jason Johnson

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 NP-hard. But in graphs with narrow tree width, the problem is efficiently solved by applying the max-product 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 upper-bounds 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 zero-temperature limit of the first method and reduces to a max-marginal 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