Marginal Inference in Continuous Markov Random Fields Using Mixtures

Yuanzhen Guo, Hao Xiong, Nicholas RuozziAAAI 2019 · DOI

Abstract

Continuous Markov Random Fields (MRFs) are powerful tools for modeling complex dependencies in spatial and temporal data. However, marginal inference in these models—calculating partition functions and variable distributions—is notoriously difficult because messages lack closed-form representations. We present QBethe, a novel inference framework that approximates beliefs as Gaussian mixtures within the Bethe Free Energy (BFE) optimization landscape. By utilizing Gauss-Hermite quadrature for deterministic integration and direct gradient-based optimization, QBethe achieves superior accuracy, stability, and computational efficiency compared to state-of-the-art particle-based message-passing algorithms.

Introduction

Marginal inference is a fundamental task in probabilistic graphical models, yet it remains computationally NP-hard. In continuous domains, the challenge is amplified: standard algorithms like Belief Propagation (BP) require passing "messages" between nodes that do not have simple parametric forms. Existing solutions typically resort to stochastic approximations, such as Particle Belief Propagation (PBP), or moment-matching heuristics like Expectation Propagation (EP). These methods often struggle with convergence on loopy graphs, high computational overhead for representing complex distributions, and a lack of local consistency in marginal estimates.

QBethe introduces a paradigm shift by directly approximating the beliefs (pseudomarginals) rather than the messages. By constraining these beliefs to the family of Gaussian mixtures and optimizing the Bethe Free Energy directly, QBethe provides a principled and efficient alternative for continuous inference.

Methodology

The core of QBethe lies in its approach to the Bethe Free Energy (BFE) objective. Instead of the iterative message-passing heuristic of standard BP, QBethe treats inference as a constrained optimization problem.

Gaussian Mixture Beliefs

Unlike standard Gaussian approximations which collapse multimodal distributions into a single peak, QBethe restricts the set of allowable beliefs to Gaussian mixtures. This allows the model to faithfully represent complex, multimodal posterior distributions common in real-world data.

Gauss-Hermite Quadrature (GHQ)

To evaluate the intractable integrals required by the BFE objective, QBethe employs Gauss-Hermite Quadrature. GHQ is a deterministic integration method that is significantly more efficient than random sampling. In practice, a few carefully chosen quadrature points (e.g., $K_Q=4$) can provide higher accuracy than hundreds of random particles used in PBP.

Direct Optimization and Convergence

Rather than relying on potentially oscillating message-passing updates, QBethe uses projected gradient ascent to maximize the BFE. This approach guarantees convergence to a local optimum, providing much-needed stability in loopy graphical models. Furthermore, by imposing specific structural constraints on the inverse covariance, the resulting local marginals can be used to extract any conditional distribution in a single pass.

Experimental Evaluation

The authors benchmarked QBethe against Particle BP (PBP) and Expectation Particle BP (EPBP) across several challenging domains.

Image Denoising

In a $50 \times 50$ grid graph representing a noisy image, QBethe demonstrated an extraordinary speed advantage. While EPBP required 50 seconds for a single iteration, QBethe completed an iteration in just 0.02 seconds. This efficiency allowed QBethe to perform 2,500 iterations in the time its competitors performed one, leading to superior reconstruction quality.

Comparison of image denoising results: (a) Original, (b) Noisy, (c) EP, (d) PBP, (e) EPBP, and (f) QBethe. QBethe (f) provides the most faithful reconstruction of the original gradient and edges.

Stability and Scalability

On UCI datasets, QBethe consistently yielded more accurate estimates of the partition function ($Z$) and lower KL divergence to ground-truth marginals. In a synthetic 3-node cycle—a classic test for loopy convergence—QBethe remained stable while PBP and EPBP estimates fluctuated wildly by up to 12 orders of magnitude.

The method's scalability was further proven on a large-scale optical flow problem (Middlebury "Hydrangea" dataset) involving over 200,000 variables. QBethe completed 5,000 iterations in under 200 seconds on a single GPU, achieving a state-of-the-art end-point error of 0.273.

Discussion

The success of QBethe stems from the realization that deterministic quadrature points are far more informative per point than random particles. By treating inference as optimization, the authors bypass the convergence pitfalls of standard BP. Additionally, the reliance on matrix-vector operations makes the algorithm highly compatible with modern GPU acceleration.

However, some limitations persist. The quadrature scheme's complexity scales exponentially with clique size ($K_Q^r$), which may necessitate alternative integration techniques for models with high-arity cliques. Furthermore, the lack of a closed-form solution for the entropy of Gaussian mixtures requires the use of Taylor series approximations.

Conclusion

QBethe represents a significant advancement in continuous marginal inference. By combining the flexibility of Gaussian mixtures with the efficiency of deterministic quadrature and the stability of direct BFE optimization, it offers a powerful tool for researchers dealing with large-scale, multimodal continuous graphical models.

Summary updated

BibTeX
@inproceedings{guo2019marginal,
  author = {Yuanzhen Guo and Hao Xiong and Nicholas Ruozzi},
  title = {{Marginal Inference in Continuous Markov Random Fields Using Mixtures}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33017834},
}
Figure