Residual Belief Propagation: Informed Scheduling for Asynchronous Message Passing
arXiv:1206.6837
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 (4)
Cited by in corpus (37)
- GraphLab: A New Framework For Parallel Machine Learning
- GraphLab: A New Framework for Parallel Machine Learning
- Tightening LP Relaxations for MAP using Message Passing
- Sufficient conditions for convergence of the Sum-Product Algorithm
- Dynamic Compressive Sensing of Time-Varying Signals via Approximate Message Passing
- Distributed GraphLab: A Framework for Machine Learning in the Cloud
- Hybrid Approximate Message Passing
- Graph Partition Neural Networks for Semi-Supervised Classification
- Informed Dynamic Scheduling for Belief-Propagation Decoding of LDPC Codes
- Improved Dynamic Schedules for Belief Propagation
- Mean Field Variational Approximation for Continuous-Time Bayesian Networks
- 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
- A visual introduction to Gaussian Belief Propagation
- GraphLab: A Distributed Framework for Machine Learning in the Cloud
- Join-graph based cost-shifting schemes
- A New Approach to Speeding Up Topic Modeling
- Semi-Supervised Learning with Heterophily
- Approximate inference on planar graphs using Loop Calculus and Belief Propagation
- Message Error Analysis of Loopy Belief Propagation for the Sum-Product Algorithm
- Gaussian Belief Propagation for Solving Systems of Linear Equations: Theory and Application
- Towards Big Topic Modeling
- Generalized Belief Propagation on Tree Robust Structured Region Graphs
- Loop corrections for approximate inference
- Memory-Efficient Topic Modeling
- Interpreting Graph Cuts as a Max-Product Algorithm
- Residual Belief Propagation for Topic Modeling
- Strengthening Probabilistic Graphical Models: The Purge-and-merge Algorithm
- Coding Techniques for Future Wi-Fi
- Fixed Points of Belief Propagation -- An Analysis via Polynomial Homotopy Continuation
- Relaxed Scheduling for Scalable Belief Propagation
- Linearized and Single-Pass Belief Propagation
- Truncating the loop series expansion for Belief Propagation
- Anytime Belief Propagation Using Sparse Domains
- Equivariant Neural Network for Factor Graphs