摘要翻译：
在大领域中，概率图形模型的推理仍然是一个很大的实际挑战。常用的有效的信念传播(BP)算法及其推广应用于实际困难的推理任务时往往不收敛。虽然人们普遍认为这些算法中的消息调度可能会产生重大影响，但这个问题在很大程度上仍未被探索。在这项工作中，我们解决了如何调度异步传播的消息以便更快更频繁地到达固定点的问题。我们首先证明了任何合理的异步BP在与保证同步BP收敛的条件相似的条件下收敛到唯一的不动点。此外，我们还证明了简单循环调度的收敛速度至少与同步传播的收敛速度一样好。然后，我们提出了一种新的、易于实现的异步传播算法&剩余信念传播(RBP)，它以一种知情的方式调度消息，并将距离固定点的一个界限向下推。最后，我们证明了RBP算法在许多具有挑战性的综合和现实问题上优于现有的方法：RBP算法比其他方法收敛得更快；并且它显著地减少了直到收敛的运行时间，即使在其他方法收敛的情况下也是如此。
---
英文标题：
《Residual Belief Propagation: Informed Scheduling for Asynchronous
  Message Passing》
---
作者：
Gal Elidan, Ian McGraw, Daphne Koller
---
最新提交年份：
2012
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Artificial Intelligence        人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--

---
英文摘要：
  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.
---
PDF链接：
https://arxiv.org/pdf/1206.6837