Stable Fixed Points of Loopy Belief Propagation Are Local Minima of the Bethe Free Energy

Neural Information Processing SystemsPublished 1 January 2002

Tom Heskes

Citations136

TL;DR

Stability analysis leads us to conclude that stable fixed points of loopy belief propagation must be (local) minima of the Bethe free energy: minima can be unstable fixed points.

Abstract

We extend recent work on the connection between loopy belief propagation and the Bethe free energy. Constrained minimization of the Bethe free energy can be turned into an unconstrained saddle-point problem. Both converging double-loop algorithms and standard loopy belief propagation can be interpreted as attempts to solve this saddle-point problem. Stability analysis then leads us to conclude that stable fixed points of loopy belief propagation must be (local) minima of the Bethe free energy. Perhaps surprisingly, the converse need not be the case: minima can be unstable fixed points. We illustrate this with an example and discuss implications.

Keywords

Computer ScienceBiochemistry, Genetics and Molecular Biology

Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference

16,927 Citations1988Judea Pearl

The author provides a coherent explication of probability as a language for reasoning with partial belief and offers a unifying perspective on other AI approaches to uncertainty, such as the Dempster-Shafer formalism, truth maintenance systems, and nonmonotonic logic.

IEEE Transactions on Information TheoryFactor graphs and the sum-product algorithm

6,481 Citations2001Frank R. Kschischang, Brendan J. Frey +1 more

A generic message-passing algorithm, the sum-product algorithm, that operates in a factor graph, that computes-either exactly or approximately-various marginal functions derived from the global function.

arXiv (Cornell University)Loopy Belief Propagation for Approximate Inference: An Empirical Study

1,468 Citations2013Kevin P. Murphy, Yair Weiss +1 more

View PDF

Generalized Belief Propagation

906 Citations2000Jonathan S. Yedidia, William T. Freeman +1 more

It is shown that BP can only converge to a stationary point of an approximate free energy, known as the Bethe free energy in statistical physics, and generalized belief propagation (GBP) versions of these Kikuchi approximations are derived.

Neural ComputationCCCP Algorithms to Minimize the Bethe and Kikuchi Free Energies: Convergent Alternatives to Belief Propagation

240 Citations2002Alan Yuille

A class of discrete iterative algorithms that are provably convergent alternatives to believe propagation (BP) and generalized belief propagation (GBP) and are pointed out that have a large range of inference and learning applications.

Radboud Repository (Radboud University)Expectation propagation for approximate inference in dynamic bayesian networks

110 Citations2002Tom Heskes, Onno Zoeter

A double-loop algorithm, guaranteed to converge to a local minimum of a Bethe free energy is derived, and it is shown that stable fixed points of (damped) expectation propagation correspond to local minima of this free energy, but that the converse need not be the case.

View PDF

The Unified Propagation and Scaling Algorithm

46 Citations2001Yee Whye Teh, Max Welling

It is shown that a restricted class of constrained minimum divergence problems, named generalized inference problems, can be solved by approximating the KL divergence with a Bethe free energy.

Minimax and Hamiltonian Dynamics of Excitatory-Inhibitory Networks

21 Citations1997H. Sebastian Seung, Tom Richardson +2 more

The relations of the Lyapunov function to optimization theory and classical mechanics are revealed by minimax and dissipative Hamiltonian forms of the network dynamics.