2012/06/27 by Gal Elidan, Elidan, Gal, Ian McGraw +3 · 3 citations
Computer Science · #Artificial Intelligence (cs.AI) #Bayesian Modeling and Causal Inference #Error Correcting Code Techniques #FOS: Computer and information sciences #Gaussian Processes and Bayesian Inference #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.1206.6837
openalex publication_date 2012/06/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Inference for probabilistic graphical models is still very much a practical\nchallenge in large domains. The commonly used and effective belief propagation\n(BP) algorithm and its generalizations often do not converge when applied to\nhard, real-life inference tasks. While it is widely recognized that the\nscheduling of messages in these algorithms may have significant consequences,\nthis issue remains largely unexplored. In this work, we address the question of\nhow to schedule messages for asynchronous propagation so that a fixed point is\nreached faster and more often. We first show that any reasonable asynchronous\nBP converges to a unique fixed point under conditions similar to those that\nguarantee convergence of synchronous BP. In addition, we show that the\nconvergence rate of a simple round-robin schedule is at least as good as that\nof synchronous propagation. We then propose residual belief propagation (RBP),\na novel, easy-to-implement, asynchronous propagation algorithm that schedules\nmessages in an informed way, that pushes down a bound on the distance from the\nfixed point. Finally, we demonstrate the superiority of RBP over\nstate-of-the-art methods for a variety of challenging synthetic and real-life\nproblems: RBP converges significantly more often than other methods; and it\nsignificantly reduces running time until convergence, even when other methods\nconverge.\n