Tightening LP Relaxations for MAP using Message Passing
arXiv:1206.3288
Abstract
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 sidechain placement, protein design, and stereo problems, in cases where the standard LP relaxation fails.
Appears in Proceedings of the Twenty-Fourth Conference on Uncertainty in Artificial Intelligence (UAI2008)
References in corpus (4)
Cited by in corpus (52)
- Answering Table Queries on the Web using Column Keywords
- Hinge-Loss Markov Random Fields and Probabilistic Soft Logic
- Learning Deep Structured Models
- A Tutorial on Dual Decomposition and Lagrangian Relaxation for Inference in Natural Language Processing
- TerpreT: A Probabilistic Programming Language for Program Induction
- Taming the Curse of Dimensionality: Discrete Integration by Hashing and Optimization
- Large-scale Binary Quadratic Optimization Using Semidefinite Relaxation and Applications
- A new look at reweighted message passing
- On the Partition Function and Random Maximum A-Posteriori Perturbations
- MAP Estimation of Semi-Metric MRFs via Hierarchical Graph Cuts
- On Sampling from the Gibbs Distribution with Random Maximum A-Posteriori Perturbations
- Efficiently Searching for Frustrated Cycles in MAP Inference
- Atomic-accuracy prediction of protein loop structures through an RNA-inspired ansatz
- Join-graph based cost-shifting schemes
- Scalable Semidefinite Relaxation for Maximum A Posterior Estimation
- Optimization With Parity Constraints: From Binary Codes to Discrete Integration
- Exact and Approximate Inference in Associative Hierarchical Networks using Graph Cuts
- Decomposition Bounds for Marginal MAP
- Optimizing wind farms layouts for maximum energy production using probabilistic inference: Benchmarking reveals superior computational efficiency and scalability
- Understanding Protein Dynamics with L1-Regularized Reversible Hidden Markov Models
- Message-Passing Algorithms for Quadratic Programming Formulations of MAP Estimation
- Tightening Fractional Covering Upper Bounds on the Partition Function for High-Order Region Graphs
- On Measure Concentration of Random Maximum A-Posteriori Perturbations
- Alternating Directions Dual Decomposition
- Playing with Duality: An Overview of Recent Primal-Dual Approaches for Solving Large-Scale Optimization Problems
- The OS* Algorithm: a Joint Approach to Exact Optimization and Sampling
- Fast Planar Correlation Clustering for Image Segmentation
- Higher-order Segmentation via Multicuts
- On MAP Inference by MWSS on Perfect Graphs
- Variable Elimination in the Fourier Domain
- Tighter Linear Program Relaxations for High Order Graphical Models
- Relax, no need to round: integrality of clustering formulations
- Red-QAOA: Efficient Variational Optimization through Circuit Reduction
- Tightening MRF Relaxations with Planar Subproblems
- Tracking Objects with Higher Order Interactions using Delayed Column Generation
- Constraint Reduction using Marginal Polytope Diagrams for MAP LP Relaxations
- Next Generation Multicuts for Semi-Planar Graphs
- LPQP for MAP: Putting LP Solvers to Better Use
- Lifted Tree-Reweighted Variational Inference
- Planar Cycle Covering Graphs
- Norm-Product Belief Propagation: Primal-Dual Message-Passing for Approximate Inference
- Reified Context Models
- Submodular Decomposition Framework for Inference in Associative Markov Networks with Global Constraints
- Marginal Weighted Maximum Log-likelihood for Efficient Learning of Perturb-and-Map models
- Efficient semidefinite bounds for multi-label discrete graphical models
- Automatically selecting inference algorithms for discrete energy minimisation
- Efficient Semidefinite Branch-and-Cut for MAP-MRF Inference
- Dual Decomposition from the Perspective of Relax, Compensate and then Recover
- Distributed Anytime MAP Inference
- Blending Learning and Inference in Structured Prediction
- Scalable Probabilistic Databases with Factor Graphs and MCMC
- Convex Optimization For Non-Convex Problems via Column Generation