Lab Meeting April 14th, 2008 (Atwood): Loopy Belief Propagation

I will explain the principles behind the belief propagation (BP) algorithm, which is an efficient way to solve inference problems based on passing local messages, and one extension, Residual Belief Propagation, to arbitrary graphs possibly with loops.

References:

Understanding Belief Propagation and its Generalizations, Jonathan S. Yedidia, William T. Freeman, and Yair Weiss, MERL Technical Report, 2001

G. Elidan, I. McGraw, and D. Koller (2006). "Residual Belief Propagation: Informed Scheduling for Asynchronous Message Passing." Proceedings of the Twenty-second Conference on Uncertainty in AI (UAI).


Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms Yedidia, J.S.; Freeman, W.T.; Weiss, Y. ,IEEE Transactions on Information Theory, 2005