Approximating MAP by Compensating for Structural Relaxations

Arthur Choi, Adnan DarwicheNeurIPS 2009 · OpenReview

TL;DR

This paper introduces a "Relax then Compensate" framework for solving the Maximum A Posteriori (MAP) problem in graphical models. By starting with a structural relaxation (such as deleting edges) and subsequently adding auxiliary parameters to "compensate" for the lost constraints, the authors demonstrate that max-product belief propagation is just one specific type of compensation. Building on this, they propose a new compensation method (REC-I) that provides tighter, monotonic upper bounds on the true MAP value.

The Challenge of MAP Inference

Finding the most likely state of a complex system—the MAP assignment—is a fundamental task in fields like computer vision and bioinformatics. However, because it is computationally NP-hard, researchers often rely on relaxations. By simplifying the problem (e.g., assuming certain variables are independent), they can compute an answer much more quickly.

Unfortunately, this introduces a painful trade-off: achieving a more accurate answer typically requires a more complex relaxation, which drastically increases computation time. The authors address a critical question: Is it possible to tighten a relaxation without making the underlying model structure more complex?

The "Relax then Compensate" Framework

To bypass the traditional complexity trade-off, the authors propose a two-step approach:

  1. Relaxation: The model is simplified by relaxing "equivalence constraints." For example, if a variable $C$ appears in two different parts of a model, a relaxation might "clone" $C$ into $C$ and $C'$, allowing them to take different values. This effectively breaks the dependencies (edges) in the graph, making the problem tractable.
  2. Compensation: Auxiliary parameters ($\theta$) are introduced to the relaxed model. These parameters act as a penalty or "nudge" to encourage the cloned variables to behave as if they were still a single, unified variable.

The paper identifies two primary ways to set these compensation parameters:

  • REC-BP: This approach sets parameters based on a condition for exactness in simple cases. The authors mathematically prove that this formulation is actually a novel way to understand max-product belief propagation (BP).
  • REC-I (Ideal Compensation): This is a new approach designed to yield a tighter upper bound on the MAP value. Unlike standard BP, which can oscillate or produce overconfident answers, REC-I is mathematically guaranteed to provide an upper bound.

To implement this, the authors provide an iterative fixed-point algorithm (Algorithm 1: REC) to find the optimal compensation parameters.

Key Insights

  • BP is a Compensation Scheme: One of the paper's most elegant insights is the formal proof that loopy max-product belief propagation is a specific instance of "compensating" for a fully disconnected relaxation. This offers a fresh geometric and optimization-based perspective on a classic algorithm.
  • Tightening Without Complexity: The compensation parameters do not change the treewidth (a measure of graph complexity) of the relaxed model. Consequently, the algorithm achieves a better bound for the same computational "price" per iteration.
  • Principled Upper Bounds: While standard BP is a heuristic lacking strict guarantees, the REC-I variant is specifically designed to maintain the "upper bound" property. This makes it highly valuable for exact search algorithms like branch-and-bound.

Experimental Results

The authors evaluated their methods using synthetic 10x10 grid networks, which serve as standard benchmarks for testing inference algorithms. They tested both Random Grids (where edge weights are assigned uniformly at random) and Frustrated Grids (which include a mix of "attractive" and "repulsive" interactions that make the MAP problem particularly difficult).

Approximation error over iterations for REC-BP and REC-I on random and frustrated grids.
  • Convergence: On simple random grids, both REC-BP and REC-I significantly tighten the initial relaxation. As seen in the results, REC-BP converges faster (requiring fewer iterations), but REC-I remains more stable.
  • Handling Frustration: In "frustrated" networks, standard belief propagation (REC-BP) often oscillates or fails to converge. In contrast, REC-I remains well-behaved and produces monotonically decreasing upper bounds.
  • Exactness: By utilizing a slightly more sophisticated relaxation (mini-buckets with a cluster size of 3) combined with REC-I compensation, the algorithm successfully found the exact MAP solution in 7 out of 10 difficult frustrated instances.

Limitations and Future Work

While the framework is highly promising, the authors note a few limitations:

  • Convergence Speed: REC-I generally requires more iterations than REC-BP to reach a stable fixed point.
  • Empirical Monotonicity: Although Theorem 3 proves that REC-I provides an upper bound, the strictly monotonic decrease of this bound during iteration is observed empirically but not yet proven for all possible edge cases.
  • Scaling: The experiments were conducted on 10x10 grids. Performance on massive, real-world datasets (such as those in modern deep learning or large-scale genomics) remains an open question.
  • Beyond MAP: The current work focuses exclusively on the MAP task. Extending this "Relax then Compensate" logic to marginal inference (calculating probabilities) is a natural and exciting next step for future research.

Summary updated

Abstract

We introduce a new perspective on approximations to the maximum a posteriori (MAP) task in probabilistic graphical models, that is based on simplifying a given instance, and then tightening the approximation. First, we start with a structural relaxation of the original model. We then infer from the relaxation its deficiencies, and compensate for them. This perspective allows us to identify two distinct classes of approximations. First, we find that max-product belief propagation can be viewed as a way to compensate for a relaxation, based on a particular idealized case for exactness. We identify a second approach to compensation that is based on a more refined idealized case, resulting in a new approximation with distinct properties. We go on to propose a new class of algorithms that, starting with a relaxation, iteratively yields tighter approximations.
BibTeX
@inproceedings{choi2009approximating,
  author = {Arthur Choi and Adnan Darwiche},
  title = {{Approximating MAP by Compensating for Structural Relaxations}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2009},
  url = {https://openreview.net/forum?id=r1Wa-FW_-r},
}
Figure