Convexifying the Bethe Free Energy

Ofer Meshi, Ariel Jaimovich, Amir Globerson, Nir Friedman

Abstract

Approximate inference in probabilistic graphical models often involves a trade-off between the high empirical accuracy of the Bethe free energy and the convergence guarantees of convex approximations. This paper introduces "convexified" versions of the Bethe free energy that bridge this gap. By exploring the space of counting numbers and entropy functions, the authors propose methods—convexBethe-c, convexBethe-μ, and convexBethe-u—that provide global convergence while maintaining accuracy close to standard Loopy Belief Propagation (LBP), and in some cases, surpassing it.

Introduction

In probabilistic graphical models, calculating the partition function for normalization and determining marginal probabilities are generally NP-hard problems. A common approach is Loopy Belief Propagation (LBP), which minimizes the Bethe Free Energy. While LBP is often remarkably accurate, it suffers from two major drawbacks: it may fail to converge (oscillating indefinitely) and, due to the non-convexity of the Bethe Free Energy, it can get trapped in local optima.

Previous attempts to address these issues involved convex approximations like Tree-Reweighted Belief Propagation (TRW). While these methods guarantee a single global optimum and convergence, they often sacrifice significant accuracy compared to LBP. This research seeks a middle ground: a convex approximation that remains as close as possible to the Bethe Free Energy.

Methods

The authors define the entropy approximation using "counting numbers" ($c_i$ for variables and $c_\alpha$ for factors). The goal is to find counting numbers that satisfy convexity constraints while minimizing the distance to the original Bethe coefficients.

The space of counting numbers ($C_i, C_\alpha$) showing the 'Provably convex' region and the location of Bethe, convexBethe-c, and TRW approximations.

Three primary convexification strategies are proposed:

  1. convexBethe-c (Static/Geometric): This method identifies the set of counting numbers closest to the Bethe coefficients in terms of Euclidean ($L_2$) distance, subject to convexity.
  2. convexBethe-μ (Static/Functional): Rather than approximating coefficients, this approach approximates the entropy function itself. It uses MCMC to sample marginals and finds a convex entropy function that best fits the Bethe entropy in an $L_2$-norm sense.
  3. convexBethe-u (Adaptive): This method adapts to the specific weights of the model. The authors derive a condition under which a convex free energy bounds the Bethe free energy and use a conditional gradient algorithm to minimize this bound.

Key Insights

  • Variable-Validity: For an approximation to be accurate, it must count variables correctly. The authors enforce this "variable-validity" property across their models.
  • Bethe as the Accuracy Limit: Empirical results confirm that as convex approximations approach the Bethe counting numbers, their accuracy typically improves, explaining why LBP remains a strong baseline.
  • Functional vs. Structural Approximation: Approximating the entropy function (convexBethe-μ) is significantly more effective than simply approximating the counting numbers (convexBethe-c).
  • The Power of Adaptation: By considering the model's actual parameters, the adaptive convexBethe-u method outperforms static structural approximations.

Key Results

The proposed methods were evaluated on synthetic benchmarks, including toroidal grids and fully connected graphs, with varying interaction strengths.

Error in marginals and log-partition function as a function of the counting number $C_i$.
  • Superior Performance: convexBethe-u consistently outperformed state-of-the-art convex methods like TRW-opt in both marginal accuracy and partition function estimation.
  • Regime-Dependent Success: While LBP remains superior in "easy" regimes with weak interactions, the new convex approximations actually outperformed LBP in "hard" regimes characterized by strong interactions and weak external fields.
  • Efficiency and Scalability: The convexBethe-u approach is more computationally efficient and generalizes more easily to higher-order factors than previous tree-based convex methods.

Conclusion

This work demonstrates that it is possible to construct convex approximations of the Bethe free energy that retain much of LBP's accuracy while providing robust convergence. While the Bethe approximation still generally provides better log-partition estimates, the proposed convex variants offer a powerful alternative for stable and accurate inference in complex graphical models. Future work remains to address the MCMC overhead for convexBethe-μ and to theoretically formalize the importance of variable-validity.

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},
}
Figure