Efficient semidefinite-programming-based inference for binary and multi-class MRFs

Chirag Pabbaraju, Po-Wei Wang, J. Zico Kolter

TL;DR

This paper introduces a highly efficient approach to perform probabilistic inference in Markov Random Fields (MRFs) by leveraging fast, low-rank semidefinite programming (SDP) solvers. By designing a novel SDP relaxation with only a linear number of constraints, the authors achieve state-of-the-art accuracy and significant speedups in both finding the most likely state (MAP inference) and estimating the partition function. This holds true even in challenging "low-temperature" settings where traditional methods typically fail.

What Problem Does This Paper Address?

Markov Random Fields (MRFs) are a staple of machine learning, widely used to model complex dependencies in fields like computer vision and computational biology. However, two fundamental tasks associated with MRFs are notoriously difficult:

  1. MAP Inference: Finding the single most likely configuration of variables (an NP-hard problem for general graphs).
  2. Computing the Partition Function ($Z$): Calculating the normalization constant of the probability distribution, which is essential for determining the actual probability of any given state (a #P-hard problem).

While Semidefinite Programming (SDP) relaxations offer a powerful theoretical framework for tackling these problems, they have historically been too slow for practical use because standard solvers scale poorly with the number of variables. Furthermore, most existing SDP research focuses on binary (two-class) variables, leaving a significant gap for multi-class "Potts models."

Methods

The authors bridge the gap between theoretical SDP power and practical efficiency through three key innovations:

  • Compact Multi-class Relaxation: They derive a new SDP relaxation specifically for $k$-class MRFs. Unlike previous relaxations that required a quadratic number of constraints ($O(n^2)$), their formulation requires only a linear number ($O(n)$), making it substantially lighter to solve.
  • The "Mixing Method" Solver: They employ a recently proposed coordinate-descent-based solver (dubbed $M^4$) designed for low-rank SDPs. This solver is extremely fast and converges to global solutions much quicker than traditional interior-point methods.
  • Unbiased Partition Function Estimation: To estimate $Z$, they use the SDP solution to inform an importance sampling scheme. They combine samples clustered around the "mode" (found by the SDP) with uniform samples to ensure the estimate is theoretically unbiased and robust across the entire search space.

Datasets

The researchers evaluated their approach on both synthetic and real-world benchmarks:

  • Synthetic MRFs: Randomly generated complete graphs and Erdős-Rényi graphs with varying "coupling strengths" (simulating different "temperatures" of the physical system).
  • Image Segmentation: They applied their method to DenseCRF models, which are fully-connected pairwise CRF models used in computer vision to refine image labels. This demonstrates the method's ability to scale to thousands of variables.

Key Insights and Ideas

  • Linear is the Magic Word: Moving from $O(n^2)$ to $O(n)$ constraints is the crucial breakthrough that makes SDPs viable for large-scale graphical models. It allows the use of fast first-order solvers that were previously inapplicable.
  • Conquering the "Low-Temperature" Regime: In physics terms, "low temperature" means the distribution is highly peaked and dominated by a few states. Most approximate methods (like Belief Propagation or Mean-Field) struggle in this regime. Because the SDP relaxation effectively "finds" these peaks, it excels exactly where other methods fail.
  • Rounding Matters: The paper highlights that how one moves from a continuous SDP solution back to discrete classes (rounding) is critical. The authors provide a two-step rounding procedure that reconciles random projections with the geometry of the multi-class simplex.

Key Results

The proposed methods demonstrate strong empirical performance across multiple dimensions:

Performance comparison of M4/M4+ against baselines across time and coupling strengths.
  • Speed and Accuracy: On MAP inference tasks, the proposed method achieved near-optimal results significantly faster than Annealed Importance Sampling (AIS), a common gold standard.
  • Partition Function Estimation: Their method consistently outperformed "Spectral Approximate Inference" and AIS in accuracy, particularly as the coupling strength increased (representing harder settings).
  • Scalability: The authors successfully ran their solver on fully-connected CRFs for image segmentation, a task where traditional SDP solvers would be computationally paralyzed. The results were competitive with specialized vision algorithms but utilized a more general-purpose optimization framework.

Limitations and Future Work

  • Multi-modal Distributions: The current importance sampling approach is highly effective at finding the primary mode of a distribution. However, if a distribution has many high-probability "islands" (modes) that are far apart, the sampler might get stuck near one and miss the others.
  • Structured Sampling: The authors suggest that future work could involve more sophisticated sampling mechanisms (beyond simple uniform exploration) to better navigate these complex, multi-modal landscapes.
  • Differentiability: While not fully explored in the paper, the authors note that because their method is based on a continuous relaxation, it could potentially be integrated into "end-to-end" deep learning pipelines where the inference step itself needs to be differentiable.

Summary updated

Abstract

Probabilistic inference in pairwise Markov Random Fields (MRFs), i.e. computing the partition function or computing a MAP estimate of the variables, is a foundational problem in probabilistic graphical models. Semidefinite programming relaxations have long been a theoretically powerful tool for analyzing properties of probabilistic inference, but have not been practical owing to the high computational cost of typical solvers for solving the resulting SDPs. In this paper, we propose an efficient method for computing the partition function or MAP estimate in a pairwise MRF by instead exploiting a recently proposed coordinate-descent-based fast semidefinite solver. We also extend semidefinite relaxations from the typical binary MRF to the full multi-class setting, and develop a compact semidefinite relaxation that can again be solved efficiently using the solver. We show that the method substantially outperforms (both in terms of solution quality and speed) the existing state of the art in approximate inference, on benchmark problems drawn from previous work. We also show that our approach can scale to large MRF domains such as fully-connected pairwise CRF models used in computer vision.
BibTeX
@inproceedings{pabbaraju2020efficient,
  author = {Chirag Pabbaraju and Po-Wei Wang and J. Zico Kolter},
  title = {{Efficient semidefinite-programming-based inference for binary and multi-class MRFs}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=CTGiueOY_j9},
}
Figure