Lagrangian Relaxation for MAP Estimation in Graphical Models

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 max-product (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.

10 pages, presented at 45th Allerton conference on communication, control and computing, to appear in proceedings

References in corpus (1)

• On the optimality of tree-reweighted max-product message-passing

Cited by in corpus (19)

• A Tutorial on Dual Decomposition and Lagrangian Relaxation for Inference in Natural Language Processing
• The power of linear programming for general-valued CSPs
• A new look at reweighted message passing
• Efficient MRF Energy Minimization via Adaptive Diminishing Smoothing
• Join-graph based cost-shifting schemes
• Efficient Learning of Interpretable Classification Rules
• Alternating Directions Dual Decomposition
• Approximated Structured Prediction for Learning Large Scale Graphical Models
• Norm-Product Belief Propagation: Primal-Dual Message-Passing for Approximate Inference
• Efficient Message Passing for 0-1 ILPs with Binary Decision Diagrams
• Improved Linear Programming Decoding using Frustrated Cycles
• One-sided Frank-Wolfe algorithms for saddle problems
• Dual Decomposition from the Perspective of Relax, Compensate and then Recover
• Blending Learning and Inference in Structured Prediction
• Zero-Temperature Limit of a Convergent Algorithm to Minimize the Bethe Free Energy
• Scaling Inference for Markov Logic with a Task-Decomposition Approach
• Tree-based iterated local search for Markov random fields with applications in image analysis
• MAP Inference via L2-Sphere Linear Program Reformulation
• Linear Programming based Detectors for Two-Dimensional Intersymbol Interference Channels