Convexifying the Bethe Free Energy

Ofer Meshi, Ariel Jaimovich, Amir Globerson, Nir Friedman

Abstract: The introduction of loopy belief propagation (LBP) revitalized the application of graphical models in many domains. Many recent works present improvements on the basic LBP algorithm in an attempt to overcome convergence and local optima problems. Notable among these are convexified free energy approximations that lead to inference procedures with provable convergence and quality properties. However, empirically LBP still outperforms most of its convex variants in a variety of settings, as we also demonstrate here. Motivated by this fact we seek convexified free energies that directly approximate the Bethe free energy. We show that the proposed approximations compare favorably with state-of-the art convex free energy approximations.

Introduction

In the domain of probabilistic graphical models, computing marginal probabilities is a fundamental yet often computationally intractable task. Approximate inference typically falls into two camps. Loopy Belief Propagation (LBP) is the empirical "gold standard," optimizing the non-convex Bethe Free Energy. While accurate, LBP can fail to converge or get trapped in local optima. Conversely, convex approximations like Tree-Reweighted (TRW) belief propagation guarantee a global optimum and provide upper bounds on the partition function, but often at the cost of significant predictive accuracy. This research explores whether one can construct an approximation that is provably convex while remaining as close as possible to the Bethe Free Energy.

Methods and the Variable-Valid Subspace

The authors frame the approximation problem using "counting numbers"—coefficients ($c_i$ for variables and $c_\alpha$ for factors) that define the system's approximate entropy. The Bethe approximation uses specific numbers that do not guarantee convexity. To bridge this gap, three novel methods are proposed:

  1. convexBethe-c (Static): Minimizes the Euclidean distance ($L_2$ norm) between the proposed counting numbers and the Bethe numbers under convexity constraints.
  2. convexBethe-μ (Static): Minimizes the $L_2$ distance between the Bethe entropy function and the convex entropy function over the space of marginals, utilizing MCMC for integration over the local polytope.
  3. convexBethe-u (Adaptive): Dynamically tunes counting numbers based on model weights using a conditional gradient algorithm to find the tightest possible upper bound on the Bethe free energy.
The parameter space of counting numbers ($C_i, C_\alpha$), highlighting the provably convex region and the variable-valid subspace where optimal approximations reside.

A critical insight is the "Variable-Valid" subspace. For an approximation to be accurate, it must be exact for independent models. The authors observe that high-performing approximations, including their proposed variants, typically lie within this subspace (see Figure 1).

Experimental Evaluation

The methods were evaluated on synthetic Markov Random Fields (MRFs) to test various difficulty regimes:

  • Toroidal Grids ($5 \times 5$ and $10 \times 10$): Standard spatial benchmarks.
  • Fully Connected Graphs (10 nodes): Testing performance on dense, highly coupled models.
  • Parameter Variations: Testing both "attractive" and "mixed" potentials with varying interaction strengths ($\omega_I$) and external fields ($\omega_F$).

Key Results

The proposed convexBethe-u and convexBethe-μ consistently outperformed standard convex methods like TRW in estimating both the partition function and marginal probabilities.

Comparison of error in log-partition and marginals across different interaction regimes, demonstrating the performance of convexified Bethe approximations relative to standard methods.

Key findings include:

  • Function vs. Parameter Approximation: convexBethe-μ (approximating the entropy function) generally outperforms convexBethe-c (approximating counting numbers), suggesting that the shape of the energy surface is more critical than the specific coefficients.
  • Regime Sensitivity: In "easy" regimes with weak interactions, Bethe remains nearly perfect. However, in "hard" regimes (strong interactions, weak external fields), the adaptive convexBethe-u often provides superior marginal estimates compared to standard LBP.
  • Efficiency: convexBethe-u proved faster and more generalizable to non-pairwise models than optimized TRW variants.

Discussion and Conclusion

While these methods represent the state-of-the-art in convex approximations to the Bethe Free Energy, a "Bethe gap" remains. The original non-convex Bethe approximation often retains higher accuracy for the partition function, suggesting its non-convexity captures essential distribution features. Future work may involve exploring additional constraints beyond variable-validity to further tighten these convex bounds and assessing scalability for large-scale real-world datasets in fields like computer vision or genomics.

Summary updated

Abstract

The introduction of loopy belief propagation (LBP) revitalized the application of graphical models in many domains. Many recent works present improvements on the basic LBP algorithm in an attempt to overcome convergence and local optima problems. Notable among these are convexified free energy approximations that lead to inference procedures with provable convergence and quality properties. However, empirically LBP still outperforms most of its convex variants in a variety of settings, as we also demonstrate here. Motivated by this fact we seek convexified free energies that directly approximate the Bethe free energy. We show that the proposed approximations compare favorably with state-of-the art convex free energy approximations.
BibTeX
@inproceedings{meshi2009convexifying,
  author = {Ofer Meshi and Ariel Jaimovich and Amir Globerson and Nir Friedman},
  title = {{Convexifying the Bethe Free Energy}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2009},
  url = {https://openreview.net/forum?id=YuJuUM4yVZN},
}

Loading related content...

Figure