Residual Belief Propagation: Informed Scheduling for Asynchronous Message Passing

By Gal Elidan, Ian McGraw, Daphne Koller. Conference on Uncertainty in Artificial Intelligence, 2006

315 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/8850119d05f852e67a71151b6da2f88e9bcac9be

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

Citations in the corpus

Dynamic conditional random fields: factorized probabilistic models for labeling and segmenting sequence data (2004, background): “Finally, dynamic schedules for BP (Elidan et al., 2006), which depend on the current message values during inference, have recently been shown to converge significantly faster than TRP on sufficiently difficult graphs, and may be preferable to TRP on certain DCRFs.”
Learning message-passing inference machines for structured prediction (2011, methodology): “Asynchronous message passing often allows faster convergence and methods such as Residual BP [5] have been developed to achieve still faster convergence by prioritizing the messages to compute.”
Stereo Matching with Color-Weighted Correlation, Hierachical Belief Propagation and Occlusion Handling (2006, background): “Elidan [8] maintained a priority queue of messages and updated the one with the highest residual.”
Distributed GraphLab: A Framework for Machine Learning in the Cloud (2012, methodology): “For example, in parameter optimization, often a large number of parameters will quickly converge in a few iterations, while the remaining parameters will converge slowly over many iterations [11, 10].”
Graphical Models, Exponential Families, and Variational Inference (2008, background): “, 164]; some recent work has also studied adaptive schedules for message-passing [72, 221].”
Advanced Structured Prediction (2014, methodology): “This can be viewed as a theoretical reinforcement of selective scheduling algorithms such as Residual Belief Propagation (Elidan et al., 2006).”
Dependency Parsing by Belief Propagation (2008, unknown): “For example, instead of updating all messages in parallel at every iteration, it is empirically faster to serialize updates using a priority queue (Elidan et al., 2006; Sutton and McCallum, 2007).”
Tightening LP Relaxations for MAP using Message Passing (2008, unknown): “[2].”
Distributed GraphLab: A Framework for Machine Learning in the Cloud (2012, methodology): “ and then updating the GMM given the labels from LBP. 724 The GraphLab update function executes the LBP local iterative update. We implement the state-of-the-art adaptive update schedule described by [11], where updates that are expected to change vertex values signicantly are prioritized. We theref”
Residual Splash for Optimally Parallelizing Belief Propagation (2009, methodology): “To schedule Splash operations, we extend the residual heuristic introduced by Elidan et al. [2006] which prioritizes message updates based on their residual, greedily optimizing the convergence criterion given in Eq.”
Accelerating Feedforward Computation via Parallel Nonlinear Equation Solving (2020, methodology): “Jacobi-type iterations are also used in message passing algorithms for probabilistic graphical models (Elidan et al., 2012; Niu et al., 2011) and graph neural networks (GNNs, Scarselli et al.”
Gaia: Geo-Distributed Machine Learning Approaching LAN Speeds (2017, background): “It is worth noting that our finding is consistent with the findings of prior work [21, 22, 40, 47, 80] on other”
Feature Correspondence Via Graph Matching: Models and Global Optimization (2008, methodology): “rithm. As in [13], we used Residual Belief Propagation (RPB) [ 34 ] with damping=0.3 for computing pseudo min-marginals for the “smoothness” subnetwork containing pairwise terms �abxaxb.”
GraphLab: A Distributed Framework for Machine Learning in the Cloud (2011, methodology): “For example, in parameter optimization, often a large number of parameters will quickly converge after only a few iterations, while the remaining parameters will converge slowly over many iterations [27, 28].”
MRF Energy Minimization and Beyond via Dual Decomposition (2011, unknown): “As a result, many generalizations of belief propagation have been proposed in the literature [57], [55], [45], [9], [5], [16].”
An Introduction to Conditional Random Fields (2010, background): “However, more sophisticated schedules can also be effective [35, 135, 152].”
Graph Partition Neural Networks for Semi-Supervised Classification (2018, background): “See also [10, 36, 38] for more discussion of sequential updates in the context of belief propagation.”
Structured Learning and Prediction in Computer Vision (2011, unknown): “Alternative message schedules are discussed in [36].”