Belief Optimization for Binary Networks: A Stable Alternative to Loopy Belief Propagation

Abstract

We present a novel inference algorithm for arbitrary, binary, undirected graphs. Unlike loopy belief propagation, which iterates fixed point equations, we directly descend on the Bethe free energy. The algorithm consists of two phases, first we update the pairwise probabilities, given the marginal probabilities at each unit,using an analytic expression. Next, we update the marginal probabilities, given the pairwise probabilities by following the negative gradient of the Bethe free energy. Both steps are guaranteed to decrease the Bethe free energy, and since it is lower bounded, the algorithm is guaranteed to converge to a local minimum. We also show that the Bethe free energy is equal to the TAP free energy up to second order in the weights. In experiments we confirm that when belief propagation converges it usually finds identical solutions as our belief optimization method. However, in cases where belief propagation fails to converge, belief optimization continues to converge to reasonable beliefs. The stable nature of belief optimization makes it ideally suited for learning graphical models from data.

Appears in Proceedings of the Seventeenth Conference on Uncertainty in Artificial Intelligence (UAI2001)

References in corpus (1)

• Loopy Belief Propagation for Approximate Inference: An Empirical Study

Cited by in corpus (25)

• Residual Belief Propagation: Informed Scheduling for Asynchronous Message Passing
• Block Models and Personalized PageRank
• Iterative Join-Graph Propagation
• Convexifying the Bethe Free Energy
• Improved Dynamic Schedules for Belief Propagation
• Convergent Propagation Algorithms via Oriented Trees
• A Simple Insight into Iterative Belief Propagation's Success
• Properties of Bethe Free Energies and Message Passing in Gaussian Models
• Discrete geometric analysis of message passing algorithm on graphs
• Inference for Generalized Linear Models via Alternating Directions and Bethe Free Energy Minimization
• Bounds on the Bethe Free Energy for Gaussian Networks
• Amortized Bethe Free Energy Minimization for Learning MRFs
• Generalized Belief Propagation on Tree Robust Structured Region Graphs
• On the Choice of Regions for Generalized Belief Propagation
• Bethe Bounds and Approximating the Global Optimum
• Fixed Points of Belief Propagation -- An Analysis via Polynomial Homotopy Continuation
• Approximating the Bethe partition function
• The Complexity of Approximating a Bethe Equilibrium
• Fast Convergence of Belief Propagation to Global Optima: Beyond Correlation Decay
• Region-based Energy Neural Network for Approximate Inference
• Mathematical Programs for Belief Propagation and Consensus
• Lifted Hybrid Variational Inference
• Factored expectation propagation for input-output FHMM models in systems biology
• Zero-Temperature Limit of a Convergent Algorithm to Minimize the Bethe Free Energy
• Learning unbelievable marginal probabilities