Residual Belief Propagation: Informed Scheduling for Asynchronous Message Passing

Abstract

Inference for probabilistic graphical models is still very much a practical challenge in large domains. The commonly used and effective belief propagation (BP) algorithm and its generalizations often do not converge when applied to hard, real-life inference tasks. While it is widely recognized that the scheduling of messages in these algorithms may have significant consequences, this issue remains largely unexplored. In this work, we address the question of how to schedule messages for asynchronous propagation so that a fixed point is reached faster and more often. We first show that any reasonable asynchronous BP converges to a unique fixed point under conditions similar to those that guarantee convergence of synchronous BP. In addition, we show that the convergence rate of a simple round-robin schedule is at least as good as that of synchronous propagation. We then propose residual belief propagation (RBP), a novel, easy-to-implement, asynchronous propagation algorithm that schedules messages in an informed way, that pushes down a bound on the distance from the fixed point. Finally, we demonstrate the superiority of RBP over state-of-the-art methods for a variety of challenging synthetic and real-life problems: RBP converges significantly more often than other methods; and it significantly reduces running time until convergence, even when other methods converge.

Appears in Proceedings of the Twenty-Second Conference on Uncertainty in Artificial Intelligence (UAI2006)

References in corpus (3)

• Expectation Propagation for approximate Bayesian inference
• Belief Optimization for Binary Networks: A Stable Alternative to Loopy Belief Propagation
• Sufficient conditions for convergence of Loopy Belief Propagation

Cited by in corpus (18)

• GraphLab: A New Framework For Parallel Machine Learning
• GraphLab: A New Framework for Parallel Machine Learning
• Tightening LP Relaxations for MAP using Message Passing
• Distributed GraphLab: A Framework for Machine Learning in the Cloud
• Informed Dynamic Scheduling for Belief-Propagation Decoding of LDPC Codes
• Mean Field Variational Approximation for Continuous-Time Bayesian Networks
• Improved Dynamic Schedules for Belief Propagation
• Template Based Inference in Symmetric Relational Markov Random Fields
• Efficiently Searching for Frustrated Cycles in MAP Inference
• A Gaussian Belief Propagation Solver for Large Scale Support Vector Machines
• Constrained Approximate Maximum Entropy Learning of Markov Random Fields
• GraphLab: A Distributed Framework for Machine Learning in the Cloud
• Join-graph based cost-shifting schemes
• Approximate inference on planar graphs using Loop Calculus and Belief Propagation
• Gaussian Belief Propagation for Solving Systems of Linear Equations: Theory and Application
• Memory-Efficient Topic Modeling
• Generalized Belief Propagation on Tree Robust Structured Region Graphs
• Linearized and Single-Pass Belief Propagation