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.
Three primary convexification strategies are proposed:
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.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.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-umethod 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.
- Superior Performance:
convexBethe-uconsistently 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-uapproach 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