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.
Introduction
Inference in Markov Random Fields (MRFs) is a cornerstone of machine learning, used to model complex dependencies in data ranging from image pixels to biological sequences. Two primary tasks define this challenge: Maximum A Posteriori (MAP) inference, which seeks the most likely configuration of variables, and the computation of the partition function ($Z$), the normalization constant essential for probabilistic interpretation.
Researchers from Carnegie Mellon and Bosch have addressed these challenges by unlocking the power of Semidefinite Programming (SDP) for complex probabilistic models. While SDP relaxations offer a theoretically robust framework for these approximations, their practical application has historically been hindered by the computational intensity of standard solvers. Furthermore, extending these models from binary to multi-class variables typically results in a quadratic explosion of constraints, rendering them intractable for large-scale applications.
Methodology
The proposed framework overcomes these barriers through three key innovations:
- Coordinate-Descent Solver: Instead of traditional interior-point methods, the authors utilize a fast coordinate-descent-based solver optimized for low-rank SDPs. This "Mixing Method" significantly accelerates convergence.
- Compact Multi-class Relaxation: A novel mathematical relaxation for multi-class MRFs was developed. By mapping discrete classes to the vertices of a simplex in high-dimensional space, the authors reduced the number of constraints from quadratic to linear relative to the number of variables.
- Importance Sampling for $Z$: The optimized vectors from the SDP are used to perform targeted importance sampling. This approach focuses on the "peaks" of the distribution, providing a more accurate estimate of the partition function than standard random sampling.
Results and Discussion
The effectiveness of the M4 and M4+ methods was evaluated against standard baselines like Annealed Importance Sampling (AIS) and Belief Propagation variants.
Speed and Accuracy
The M4 method achieves near-optimal modes significantly faster than AIS. In terms of the partition function estimation, the approach was consistently more accurate than "Spectral AI" and other recent approximations, maintaining high accuracy even as "coupling strength" increases—a "low-temperature" regime where traditional methods often fail.
The Rounding Insight
A critical observation is that the randomized rounding process used to extract discrete solutions from the SDP naturally explores the most significant probability mass. The samples generated during rounding capture the bulk of the distribution's mass, making them ideal for importance sampling.
Scalability
The method's scalability was demonstrated on large-scale image segmentation tasks. Using fully-connected Conditional Random Fields (CRFs), the authors successfully segmented 400x400 pixel images in approximately two minutes on a standard CPU, a task typically considered infeasible for traditional MCMC-based inference.
Conclusion
By combining a compact multi-class relaxation with an efficient low-rank SDP solver, this work makes semidefinite-programming-based inference practical for large-scale MRFs. While the current sampling strategy may face challenges with highly multi-modal distributions where peaks are widely separated, the method's performance in high-coupling settings marks a significant advancement. Future research will explore more structured sampling mechanisms and the integration of this differentiable relaxation into end-to-end deep learning architectures.
Summary updated