Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms

TLDR

Inference problems in statistical physics, computer vision, coding theory, and AI can be cast as computing marginal probabilities on factor graphs, where belief propagation is exact on trees but only approximate on graphs with cycles. The authors develop region‑based free‑energy approximations that improve upon Bethe, propose corresponding generalized belief propagation algorithms, and delineate the conditions for a valid or maxent‑normal approximation while relating four construction methods. They construct these approximations via the Bethe, junction‑graph, cluster‑variation, and region‑graph methods, provide criteria to assess their accuracy, and demonstrate empirically that the resulting GBP algorithms can substantially outperform standard BP. They prove that BP fixed points are stationary points of the Bethe free energy and show through experiments that GBP achieves markedly better performance than BP.

Abstract

Important inference problems in statistical physics, computer vision, error-correcting coding theory, and artificial intelligence can all be reformulated as the computation of marginal probabilities on factor graphs. The belief propagation (BP) algorithm is an efficient way to solve these problems that is exact when the factor graph is a tree, but only approximate when the factor graph has cycles. We show that BP fixed points correspond to the stationary points of the Bethe approximation of the free energy for a factor graph. We explain how to obtain region-based free energy approximations that improve the Bethe approximation, and corresponding generalized belief propagation (GBP) algorithms. We emphasize the conditions a free energy approximation must satisfy in order to be a "valid" or "maxent-normal" approximation. We describe the relationship between four different methods that can be used to generate valid approximations: the "Bethe method", the "junction graph method", the "cluster variation method", and the "region graph method". Finally, we explain how to tell whether a region-based approximation, and its corresponding GBP algorithm, is likely to be accurate, and describe empirical results showing that GBP can significantly outperform BP.