Tightening LP Relaxations for MAP using Message Passing

By David A. Sontag, Talya Meltzer, Amir Globerson, Tommi S. Jaakkola, Yair Weiss. 2008

323 citations recorded by the source corpus.

Linear Programming (LP) relaxations have become powerful tools for finding the most probable (MAP) configuration in graphical models. These relaxations can be solved efficiently using message-passing algorithms such as belief propagation and, when the relaxation is tight, provably find the MAP configuration. The standard LP relaxation is not tight enough in many real-world problems, however, and this has lead to the use of higher order cluster-based LP relaxations. The computational cost increases exponentially with the size of the clusters and limits the number and type of clusters we can use. We propose to solve the cluster selection problem monotonically in the dual LP, iteratively selecting clusters with guaranteed improvement, and quickly re-solving with the added clusters by reusing the existing solution. Our dual message-passing algorithm finds the MAP configuration in protein side-chain placement, protein design, and stereo problems, in cases where the standard LP relaxation fails.

Subfields: Computational Theory and Mathematics, Molecular Biology, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Molecular Biology

In Optimization & Training

Citations in the corpus

Barrier Frank-Wolfe for Marginal Inference (2015, methodology): “(25) For example, we could use a linear programming relaxation or a message-passing algorithm based on dual decomposition such as Sontag et al. (2008) to obtain the upper bound κ.”
TerpreT: A Probabilistic Programming Language for Program Induction (2016, background): “pand the number of back-ends. Natural next steps are back-ends based on local search or Markov Chain Monte Carlo, and on message passing inference in graphical models, perhaps taking inspiration from Sontag et al. (2008). Third, we would like to build higher level languages on top of TerpreT, to sup”
Taming the Curse of Dimensionality: Discrete Integration by Hashing and Optimization (2013, methodology): “For concreteness, we discuss our setup and assumptions in the context probabilistic graphical models, which is our motivating application.”
MRF Energy Minimization and Beyond via Dual Decomposition (2011, background): “As it is immediately seen, the sequences of primal and dual costs converge to each other, hence meaning that DD-MRF is able to compute a globally optimal solution even when dealing with non-submodular MRFs, and this is due to the fact that it relies on a tighter relaxation (see also [44],[54],[23] f”
Learning Efficient Random Maximum A-Posteriori Predictors with Non-Decomposable Loss Functions (2013, methodology): “linear program relaxations can be solved efficiently using different convex max-product solvers, and whenever these solvers produce an integral solution it is guaranteed to be the MAP prediction [21].”
AD3: alternating directions dual decomposition for MAP inference in graphical models (2015, background): “There are also alternatives to branch-and-bound, such as tightening procedures (Sontag et al., 2008; Batra et al., 2011), which progressively add larger factors to decrease the duality gap.”
Blending Learning and Inference in Conditional Random Fields (2016, background): “Examples include object detection (e.g., by Felzenszwalb et al. (2010)), parsing (e.g., by Koo et al. (2010)), or protein design (e.g., by Sontag et al. (2008)).”
On Sampling from the Gibbs Distribution with Random Maximum A-Posteriori Perturbations (2013, methodology): “Substantial effort has gone into developing algorithms for recovering MAP assignments, either based on specific structural restrictions such as super-modularity [2] or by devising cutting-planes based methods on linear programming relaxations [19, 24].”
Exact Decoding of Phrase-Based Translation Models through Lagrangian Relaxation (2011, methodology): “, 2010), and also to Markov random fields (Wainwright et al., 2005; Komodakis et al., 2007; Sontag et al., 2008).”
Hinge-Loss Markov Random Fields and Probabilistic Soft Logic (2015, methodology): “Other approaches to approximate inference include tighter linear programming relaxations (Sontag et al., 2008, 2012).”
An Unsupervised Model for Instance Level Subcategorization Acquisition (2014, methodology): “We applied the message passing algorithm for linear-programming (LP) relaxation of the MAP assignment (MPLP, (Sontag et al., 2008)).”
Optimization for machine learning (2010, methodology): “, 1998; Sontag and Jaakkola, 2007; Sontag, 2007), then dual methods (Werner, 2008a, 2010; Kumar and Torr, 2008; Sontag et al., 2008; Komodakis and Paragios, 2008).”
Introduction to dual composition for inference (2011, background): “frequently found using dual decomposition, in spite of the corresponding optimization problems being NP-complete (Koo et al., 2010; Sontag et al., 2008; Yanover et al., 2006).”
The OS* Algorithm: a Joint Approach to Exact Optimization and Sampling (2012, methodology): “In what follows, we only consider exact sampling, the problem of MAP estimation (i.e. optimization) in graphical models having been thoroughly investigated over the past decade (e.g. [Sontag et al., 2008]).”