Residual Belief Propagation: Informed Scheduling for Asynchronous Message Passing

Understand

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.