Source-linked AI summary
MAP Estimation, Linear Programming and Belief Propagation with Convex Free Energies
Yair Weiss, Chen Yanover, Talya Meltzer
TL;DR
MAP inference is NP-hard in general graphical models, so the paper studies broader conditions for provable extraction through belief propagation. It defines convex BP, links convex sum-product BP to LP relaxations, and proves MAP guarantees for convex max-product BP, including a tie-handling condition. Experiments report MAP recovery on large real-world models where junction-tree inference is intractable.
Problem
MAP inference is NP-hard on arbitrary graphical models, motivating provable approximation methods.
Method
The paper defines convex BP as belief propagation based on a convex free-energy approximation and extends prior tree-reweighted guarantees.
Results
Convex max-product BP recovers the MAP when beliefs have no ties, while a new condition handles some tied beliefs; convex sum-product BP can solve MAP-derived LP relaxations at sufficiently small temperatures.
Takeaways & Limitations
The theorems enable provable MAP recovery on large graphical-model instances from computational biology and error-correcting codes, beyond cases tractable by junction trees.
Takeaways & Limitations
Using convex sum-product BP at sufficiently small temperatures may cause serious numerical problems, and max-product-to-sum-product correspondence does not always work.
Abstract
from arXiv · showhide
Finding the most probable assignment (MAP) in a general graphical model is known to be NP hard but good approximations have been attained with max-product belief propagation (BP) and its variants. In particular, it is known that using BP on a single-cycle graph or tree reweighted BP on an arbitrary graph will give the MAP solution if the beliefs have no ties. In this paper we extend the setting under which BP can be used to provably extract the MAP. We define Convex BP as BP algorithms based on a convex free energy approximation and show that this class includes ordinary BP with single-cycle, tree reweighted BP and many other BP variants. We show that when there are no ties, fixed-points of convex max-product BP will provably give the MAP solution. We also show that convex sum-product BP at sufficiently small temperatures can be used to solve linear programs that arise from relaxing the MAP problem. Finally, we derive a novel condition that allows us to derive the MAP solution even if some of the convex BP beliefs have ties. In experiments, we show that our theorems allow us to find the MAP in many real-world instances of graphical models where exact inference using junction-tree is impossible.
1 Introduction
The paper extends provable MAP extraction beyond existing BP settings by introducing convex BP, a family based on convex free-energy approximations. It connects convex BP to LP relaxations and provides guarantees with or without belief ties.
- MAP inference is NP-hard on arbitrary graphical models, motivating approximation methods for applications including image understanding, error-correcting codes, and protein folding.
- The authors ask whether TRBP guarantees extend to non-tree-based BP variants and whether MAP-extraction conditions can hold when existing sufficient conditions fail.
- Convex BP comprises belief-propagation algorithms built from convex free-energy approximations, including tree-reweighted BP and broader families.The paper states that many convex free energies cannot be represented as tree-reweighted free energies.
- Convex max-product BP fixed-points yield the MAP assignment when beliefs have no ties, unifying guarantees for single-cycle BP and tree-reweighted BP.A new condition also permits MAP extraction from convex BP beliefs when ties occur.
- The approximate free-energy framework covers Bethe free energy and generalized BP algorithms whose stationary points can be characterized through belief constraints.The framework includes sum-product and max-product updates, with ordinary BP recovered for a specific parameter setting.
2 Convex Free energies
Convex free energies strictly extend tree-reweighted free energies. The paper distinguishes convexity, which enables LP-solving BP algorithms, from the stronger property of providing rigorous free-energy bounds.
- Tree-reweighted BP combines free energies over spanning trees and provides both a rigorous free-energy bound and a convex free-energy approximation.
- Convexity is evaluated over beliefs satisfying marginalization constraints, a weaker condition than convexity over arbitrary beliefs.
- Not every convex free energy has a tree-reweighted representation because tree-reweighted entropies lack a degree of freedom associated with single-node entropy terms.The paper notes that tree-reweighted entropies form only a measure-zero subset of convex entropies.
- The Bethe free energy for a single cycle is convex but cannot be represented as tree-reweighted free energy and does not provide a free-energy bound.
- BP algorithms that provide a rigorous free-energy bound form a strict subset of convex BP algorithms.
3 When does sum-product BP solve the LP relaxation?
Convex sum-product BP approaches the MAP linear-program relaxation as temperature decreases, while convexity ensures fixed-points represent global minima. The contrast with Bethe free energy shows why convexity matters for reliably reaching the LP solution.
- LP convergence: As T →0, fixed-point beliefs from convex BP approach the solution to the linear program.The energy term is the LP objective, while the bounded entropy term vanishes relative to it as temperature decreases.
- Role of convexity: Convex approximate free energies make every fixed-point a global minimum because the free energy is convex.This follows from minimizing the free energy under the admissibility and marginalization constraints.
- Role of convexity: Any BP free-energy minimization approaches the LP as temperature decreases, but non-convex entropy provides no guarantee that fixed-points reach the global optimum.Ordinary BP minimizes the Bethe free energy, whose non-convexity can preserve suboptimal local minima.
- Illustration: For the 2D Ising model, the MAP and LP optimum occur at x = 1, y = 0, where all nodes occupy their preferred state.The model uses binary nodes, pairwise interactions favoring similarity, and a uniform external field.
- Illustration: Both free energies approach the LP as temperature decreases, but Bethe free energy retains a local minimum at arbitrarily small temperatures.The contour plots compare Bethe and convex free energies through their local stationary points.
4 How are max-product BP and sum-product BP related?
Max-product BP is the zero-temperature limit of sum-product BP, but max-product beliefs can lose multiplicity information among tied configurations. A sharpening and marginalizability condition identifies when those beliefs still solve the LP, while counterexamples show the condition is necessary.
- Zero-temperature relation: As T →0, raising fixed-point sum-product beliefs to the power T produces fixed-point conditions for max-product BP at T = 1.The proof uses admissibility and sum-marginalization to obtain max-marginalization in the limit.
- Counterexample: A two-node counterexample shows that max-product BP can yield uniform beliefs at every temperature even though sum-product beliefs remain non-uniform.Raising the max-product beliefs to the power 1/T cannot recover the missing information, although the zero-temperature limit from sum-product remains valid.
- Information loss: Max-product beliefs retain maximal values but lose information about how many configurations attain those values.This loss can prevent max-product beliefs from defining the corresponding sum-product or LP solution.
- Sufficient condition: If sharpened max-product beliefs are sum-marginalizable, they solve the LP for a convex BP algorithm.Sharpening assigns equal mass to tied maxima and zero mass elsewhere.
- Counterexample: Figure 2 presents a case where max-product convex BP converges in one iteration, but its sharpened beliefs are not sum-marginalizable and cannot solve the LP.The example motivates checking the sufficient condition rather than assuming convergence alone is enough.
- Implication: The relation between max-product convex BP and LP is subtle: an LP-corresponding fixed-point is guaranteed to exist, but the algorithm is not guaranteed to find it.By contrast, sum-product convex BP connects more directly to the LP at sufficiently small temperatures.
5 When can we extract the MAP from max-product convex BP?
Convex max-product BP can certify the MAP when beliefs have unique maxima, and a new condition extends MAP extraction to tied beliefs and frustrated cycles.
- Without ties, fixed-points of max-product BP with a provably convex entropy function yield the MAP assignment.
- The result extends earlier guarantees for single-cycle ordinary BP and tree reweighted BP to arbitrary convex BP algorithms.
- Dealing with frustrations: Frustrated cycles can prevent any assignment from simultaneously maximizing all factor beliefs, so the no-ties condition alone is insufficient.
- Dealing with frustrations: Theorem 2 extracts the MAP despite frustrations by uniquely maximizing non-tied local beliefs and jointly maximizing beliefs over tied variables and mixed regions.
- Dealing with frustrations: For pairwise factors, uniform beliefs on the boundary of tied nodes ensure that the non-tied beliefs are optimal.
6 An illustrative example
Simulations on 3 × 3 spin-glass grids compared ordinary BP, TRBP, and two convex BP approximations across regimes defined by LP integrality.
- The experiments used 100 sampled 3 × 3 spin glasses to compare LP, ordinary BP, TRBP, and convex BP approximations.
- Easy regime: In the easy regime, 53% of runs had integer LP solutions, and every convex approximation recovered the MAP with a certificate.
- Easy regime: Ordinary BP was fastest in the easy regime at 48 median iterations, followed by default CBP at 112, TRBP at 176, and trivial CBP at 225.
- Hard regime: In the hard regime, 36% of runs had fully fractional LP solutions; ordinary BP never converged, while convex algorithms were equally ineffective for finding the MAP.
- Intermediate regime: In the intermediate regime, 11% of runs were partially fractional, ordinary BP failed to converge in 8 of 11 cases, and convex BP converged with MAP extraction guarantees.
- Summary: Convex BP had its greatest practical advantage in the partially fractional regime, although convergence rates varied substantially across convex algorithms.
7 Real World Experiments
Experiments tested convex BP on real-world graphical models from computational biology and error-correcting codes. The theorems found MAP solutions for many large instances, including cases where LP solutions were fractional and junction-tree inference was infeasible.
- Experimental limits: The experiments used junction-tree inference to check theorem conditions, making evaluation infeasible when the tied-node subgraph had large induced width.Thus, the number of ties—not convergence—determined whether the theorems could be applied.
- Protein experiments: About 92% of side-chain prediction instances yielded the global optimum, whereas protein design was too tie-heavy for theorem checks to remain feasible.Protein design has hundreds of possible states per node, making its state space substantially larger than side-chain prediction.
- Protein experiments: For side-chain prediction, convex BP converged in reasonable time and found the global optimum in over 90% of instances despite NP-hard exact inference.The largest reported search space was 10^600, with a largest junction-tree clique of 10^60.
- Error-correcting codes: In the LDPC experiment, high-SNR LP solutions were almost always integer, while theorem 1 recovered the MAP in all lower-SNR cases with partially fractional LP solutions.The search space had size 2^204 and the maximal junction-tree clique contained 134 bits; convex BP found the global optimum within minutes.
8 Discussion
The discussion places convex BP within a broader connection between belief propagation and LP relaxations. The results extend provable MAP extraction beyond integral LP solutions and beyond previously covered BP variants.
- Discussion: Single-cycle BP and tree-reweighted BP are special cases of the broader convex-free-energy result.The paper also derives a condition for extracting MAP assignments from convex BP beliefs with frustrated cycles.
- Discussion: Convex BP variants can solve LP relaxations of MAP, while the LP connection is distinct from providing a rigorous free-energy bound.This distinction expands the family of possible LP algorithms beyond tree-reweighted free energies.
- Discussion: Theorems from the paper can recover MAP assignments even when LP relaxations are partially fractional and junction-tree methods are intractable.Experiments on side-chain prediction and error-correcting codes demonstrated this capability on very large graphical models.