# Lagrangian Relaxation For Map Estimation In Graphical Models

Jason K. Johnson, Dmitry M. Malioutov and Alan S. Willsky Abstract— We develop a general framework for MAP estimation in discrete and Gaussian graphical models using Lagrangian relaxation techniques. The key idea is to reformulate an intractable estimation problem as one defined on a more tractable graph, but subject to additional constraints.

Relaxing these constraints gives a tractable dual problem, one defined by a thin graph, which is then optimized by an iterative procedure. When this iterative optimization leads to a consistent estimate, one which also satisfies the constraints, then it corresponds to an optimal MAP estimate of the original model. Otherwise there is a "duality gap", and we obtain a bound on the optimal solution. Thus, our approach combines convex optimization with dynamic programming techniques applicable for thin graphs. The popular tree-reweighted maxproduct (TRMP) method may be seen as solving a particular class of such relaxations, where the intractable graph is relaxed to a set of spanning trees. We also consider relaxations to a set of small induced subgraphs, thin subgraphs (e.g. loops), and a connected tree obtained by "unwinding" cycles. In addition, we propose a new class of multiscale relaxations that introduce "summary" variables. The potential benefits of such generalizations include: reducing or eliminating the "duality gap" in hard problems, reducing the number or Lagrange multipliers in the dual problem, and accelerating convergence of the iterative optimization procedure.

## I. Introduction

Graphical models are probability models for a collection of random variables on a graph: the nodes of the graph represent random variables and the graph structure encodes conditional independence relations among the variables. Such models provide compact representations of probability distributions, and have found many practical applications in physics, statistical signal and image processing, error-correcting coding and machine learning. However, performing optimal estimation in such models using standard junction tree approaches generally is intractable in large-scale estimation scenarios. This motivates the development of variational techniques to perform approximate inference, and, in some cases, recover the optimal estimate.

We consider a general Lagrangian relaxation (LR) approach to *maximum a posteriori* (MAP) estimation in graphical models. The general idea is to reformulate the estimation problem on an intractable graph as a constrained estimation over an augmented model defined on a larger, but more tractable graph. Then, using Lagrange multipliers to relax the constraints, we obtain a tractable estimation problem that gives an upper-bound on the original problem. This leads to a convex optimization problem of minimizing the upper-bound as a function of Lagrange multipliers.

The authors are with the Electrical Engineering and Computer Science Department, Massachusetts Institute of Technology, Cambridge, MA 02139, USA.{jasonj,dmm,willsky}@mit.com.

We consider a variety of strategies to augment the original graph. The simplest approach breaks the graph into many small, overlapping subgraphs, which involves replicating some variables. Similarly, the graph can be broken into a set of thin subgraphs, as in the TRMP approach, or "unrolled" to obtain a larger, but connected, thin graph. We show that all of these approaches are essentially equivalent, being characterized by the set of maximal cliques of the augmented graph. More generally, we also consider the introduction of "summary" variables, which leads naturally to multiscale algorithms. We develop a general optimization approach based on marginal and max-marginal matching procedures, which enforce consistency between replicas of a node or edge, and moment-matching in the multiscale relaxation.

We show that the resulting bound is tight if and only if there exists an optimal assignment in the augmented model that satisfies the constraints. In that case, we obtain the desired MAP estimate of the original model. When there is a duality gap, this is evidenced by the occurrence of "ties" in the resulting set of max-marginals, which requires further augmentation of the model to reduce and ultimately eliminate the duality gap. We focus primarily on discrete graphical models with binary variables, but also consider the extension to Gaussian graphical models. In the Gaussian model, we find that, whenever LR is "well-posed", so that the augmented model is valid, it leads to a tight bound and the optimal MAP estimate, and also gives *upper-bounds* on variances that provide a measure of confidence in the MAP estimate.

II. BACKGROUND
We consider probabilistic graphical models [1], [2], [3],
which are probability distributions of the form 

$$p(x_{1},\ldots,x_{n})=\frac{1}{Z}\exp\{f(x)\}=\frac{1}{Z}\exp\left\{\sum_{C\in\mathcal{G}}f_{C}(x_{C})\right\}\tag{1}$$

where each functionfC only depends on a subset of variables xC = (xv,v∈C) andZ is a normalization constant of the model, called the *partition function* in statistical physics. If the sum ranges over all *cliques* of the graph, which are the fully connected subsets of variables, this representation is sufficient to realize any Markov model onG [1]. However, it is also common to consider restricted Markov models where only singleton and pairwise interactions are specified. In general, we specify the set of interactions by a hypergraph G
⊂2 V, where 2 Vrepresents the set of all subsets ofV. The elements ofG are its *hyperedges*, which generalizes the usual concept of a graph with pairwise edges.

Discrete Models. While our approach is applicable for general discrete models, we focus on models with binary