Team for Research in
Ubiquitous Secure Technology

Citation
Jason K. Johnson, Dmitry Malioutov, Alan S. Willsky. "Lagrangian Relaxation for MAP Estimation in Graphical Models". 45th Annual Allerton Conference on Communication, Control and Computing, September, 2007.

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.

Electronic downloads

• http://ssg.mit.edu/group/jasonj/jmw-allerton07.pdf

• HTML

  Jason K. Johnson, Dmitry Malioutov, Alan S. Willsky. <a
  href="http://www.truststc.org/pubs/266.html"
  >Lagrangian Relaxation for MAP Estimation in Graphical
  Models</a>, 45th Annual Allerton Conference on
  Communication, Control and Computing, September, 2007.

• Plain text

  Jason K. Johnson, Dmitry Malioutov, Alan S. Willsky.
  "Lagrangian Relaxation for MAP Estimation in Graphical
  Models". 45th Annual Allerton Conference on
  Communication, Control and Computing, September, 2007.

• BibTeX

  @inproceedings{JohnsonMalioutovWillsky07_LagrangianRelaxationForMAPEstimationInGraphicalModels,
      author = {Jason K. Johnson and Dmitry Malioutov and Alan S.
                Willsky},
      title = {Lagrangian Relaxation for MAP Estimation in
                Graphical Models},
      booktitle = {45th Annual Allerton Conference on Communication,
                Control and Computing},
      month = {September},
      year = {2007},
      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.},
      URL = {http://www.truststc.org/pubs/266.html}
  }
  

Posted by Jason K. Johnson on 19 Jul 2007.
For additional information, see the Publications FAQ or contact webmaster at www truststc org.