Source-linked AI summary
Tightening LP Relaxations for MAP using Message Passing
David Sontag, Talya Meltzer, Amir Globerson, Tommi S. Jaakkola, Yair Weiss
TL;DR
MAP inference is difficult because standard LP relaxations may be too loose, while tighter cluster relaxations become computationally expensive. The paper addresses this by adding guaranteed-improving clusters in the dual, reusing existing messages, and reports MAP recovery across several real-world problem classes where standard LP fails.
Problem
Standard LP relaxations often fail to find MAP configurations in real-world graphical models, while tighter cluster relaxations have exponentially increasing computational costs.
Method
The paper incrementally selects clusters in the dual LP, uses messages from the current approximation to guide selection, and reuses existing dual variables when re-solving.
Results
The method finds MAP configurations in protein sidechain placement, protein design, and stereo problems where the standard LP relaxation fails.
Takeaways & Limitations
Dual cluster pursuit provides a practical way to tighten LP relaxations while retaining message-passing optimization and a monotonically decreasing MAP upper bound.
Takeaways & Limitations
The approach is computationally limited by triplet messages, with one unsolved protein-design model exhausting machine memory.
Abstract
from arXiv · showhide
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.
1 Introduction
MAP inference is NP-hard, motivating LP relaxations that offer optimality guarantees and scalable message-passing solutions. However, basic relaxations often fail on real problems, while tighter cluster-based relaxations become exponentially more expensive; the paper proposes incrementally adding guaranteed-improving clusters in the dual.
- MAP inference is NP-hard on arbitrary graphs, so approximation algorithms are needed.
- LP relaxations guarantee the global MAP optimum when their solution is integral and can be solved efficiently with message passing.
- The standard LP relaxation found MAP in only 2 of 97 protein design problems, illustrating its limited utility on real-world instances.
- Cluster-based relaxations tighten approximations but incur exponential computational costs as cluster size grows.With roughly 100 states per variable, a triplet can have 10^6 states.
- The paper proposes incrementally selecting clusters guaranteed to improve the relaxation, using existing messages to guide selection and dual message passing to monotonically lower the MAP upper bound.
2 MAP and its LP Relaxation
The paper formulates MAP inference through marginal distributions and relaxes the marginal polytope by enforcing consistency only within selected clusters. It then selects clusters in the dual to reduce an upper bound efficiently, avoiding repeated primal re-solving and enabling warm starts.
- MAP seeks the assignment xM that maximizes the graphical-model objective f(x; θ).
- The exact MAP problem can be represented as an LP over node and edge marginal probabilities constrained by the marginal polytope.
- Although the LP has O(|E|+|V|) variables, describing the exact marginal polytope typically requires exponentially many inequalities.
- Cluster-based relaxations replace the difficult global consistency constraint with consistency enforced over selected variable subsets and their auxiliary cluster distributions.
- Adding clusters tightens the relaxation, but cluster selection must balance approximation quality against state-dependent computational cost.The method considers gradually adding clusters from a predefined candidate set rather than using all candidates.
- The dual approach selects clusters by minimizing an upper bound on MAP, then warm-starts subsequent optimization using dual variables from earlier iterations.
3 Dual LP Relaxation
The paper works in a dual LP formulation where MPLP supports monotone upper-bound reduction, guaranteed cluster selection, and warm starts as clusters are added. The resulting procedure incrementally tightens the relaxation and can identify MAP assignments for nearly all tested problems.
- The chosen dual formulation enables coordinate-descent message passing with a monotonically decreasing upper bound on MAP.MPLP decreases the dual objective at every iteration, although convergence need not produce a dual-optimal solution.
- The experiments show that MAP assignments can be found for nearly all considered problems, while the improvement theorem does not quantify how much a selected constraint was violated.When MPLP is run to convergence before selecting a cluster, greedy bound minimization corresponds to a cutting-plane algorithm.
- Generalized MPLP uses edge-to-node, edge-to-edge, and triplet-to-edge messages, with messages from each edge or triplet updated simultaneously to guarantee descent.The paper presents triplets for simplicity, while stating that the algorithm applies to general clusters.
- New cluster messages are initialized at zero while existing messages are reused, preserving the previous dual value before further MPLP updates.This supplies a simple warm start for the tighter relaxation.
- The algorithm selects clusters that provide a guaranteed bound improvement, using the difference between independent edge maximization and joint maximization over a candidate triplet.It adds the triplet maximizing d(c), a lower bound on the improvement from adding that cluster.
- The complete procedure repeatedly runs MPLP, decodes an integral assignment, checks the primal-dual gap, adds the cluster with largest d(c), and continues updating.The first iteration after adding a cluster obtains at least the promised bound improvement, while further iterations propagate its effect through the model.
4 Related Work
The paper situates its region-pursuit approach among related message-passing methods, emphasizing cluster-selection criteria and the dual LP’s guarantee of monotonic improvement.
- Region-pursuit connections: The approach resembles region-pursuit for generalized belief propagation by greedily adding clusters from a candidate set.It is related to Welling’s sum-product region-pursuit method, which selects clusters using changes in GBP free energy.
- Monotonic improvement: Unlike related region-pursuit methods, the dual LP formulation guarantees monotonic improvement as clusters are added.The dual function provides a guarantee that avoids the performance deterioration reported for additional clusters in some fully connected graphs.
- Cluster selection: The work focuses on evaluating cluster utility rather than efficiently discovering candidate clusters.The experiments found simple enumeration over small clusters effective, while larger clusters can be considered by triangulating the graph when triplets are insufficient.
- Relation to convex BP: Similar region-pursuit procedures can be derived for other convex max-product belief-propagation algorithms, but MPLP uniquely guarantees dual-value decrease at every iteration.The guarantee is identified as MPLP’s main advantage over general convex BP algorithms.
- Message scheduling: Region-pursuit can be viewed as a message-scheduling problem over clusters that are present but initially send non-informative messages.Selecting the next cluster is analogous to selecting the next message update in belief propagation.
5 Experiments
Experiments apply the scalable dual message-passing method to side-chain prediction, protein design, and stereo vision, where it often finds MAP solutions that standard methods miss. Performance depends on cluster selection and batching, while triplet-message processing and memory constrain larger protein-design instances.
- Experimental setup: The experiments target computational-biology and machine-vision problems where standard primal LP solvers may be impractical.The procedure uses MPLP, decodes an integral solution during message passing, and compares it with the dual objective to certify MAP solutions when they match.
- 5.1 Side-Chain Prediction: Side-chain prediction previously defeated TRBP on 30 models, whereas the dual algorithm solved all of them under the stated precision.The reported procedure terminates when the dual objective is within 10^-4 of the decoded assignment, so the solutions are approximate MAP solutions.
- 5.1 Side-Chain Prediction: All 30 side-chain models reached the MAP solution up to a 10^-4 integrality gap, using 1–27 triplets per model.Average triplet additions were 7 per model; runtimes ranged from 1 minute to 1 hour, with over half solved in under 9 minutes.
- 5.1 Side-Chain Prediction: The schedule that runs MPLP to convergence after each triplet requires many more overall iterations than alternating cluster additions with 20 MPLP iterations.Figure 2 compares these schedules on the side-chain protein ‘1gsk’, which took 30 minutes to solve.
- 5.2 Protein Design: The method found exact MAP configurations for 96 of 97 protein-design problems up to a 10^-4 integrality gap, compared with 2 solvable by TRBP.The unsolved protein, ‘1fpo’, was the largest and could not be completed because memory ran out before all triplets were included.
- 5.2 Protein Design: Among exactly solved protein-design problems, mean runtime was 9.7 hours, with a maximum of 11 days and a minimum of a few minutes.When commercial LP solvers could be used, they were typically at least 10 times slower than similar message-passing algorithms.
- 5.2 Protein Design: Triplet-message processing is the main computational burden; solved protein-design models used a median of 145 triplets, ranging from 5 to 735.Each triplet message requires about 10^6 operations because variables have roughly 100 states.
- 5.3 Stereo Vision: For stereo instances, the method found MAP solutions in all 4 cases where TRBP-based methods failed.The Tsukuba sequence was reduced to 116x154 pixels, and square clusters were triangulated into two triplet clusters.
6 Conclusion
The paper addresses efficient cluster addition by using a greedy dual-LP algorithm with warm starts and a monotonically decreasing MAP upper bound. It finds MAP configurations in real-world problems where standard approaches were previously too difficult, while remaining applicable to larger clusters when dual messages are efficiently computable.
- The approach provides an efficient way to add clusters that improves the MAP approximation while keeping the relaxed problem tractable.
- The greedy dual-LP algorithm combines efficient message passing, warm starts from current beliefs, and a monotonically decreasing MAP bound.These ingredients support iterative cluster selection while preserving tractable re-solving.
- The algorithm finds MAP configurations for real-world problems that were previously too difficult for known methods.
- Although the experiments focused primarily on triplet clusters, the approach can add larger clusters when dual messages can be computed efficiently.
- Similar ideas may also be applicable to approximating marginals, beyond the MAP problem.