Overview

This report treats Factor Graphs and Loopy Belief Propagation. Belief Propagation is a message passing algorithm which allows to efficiently perform inference on graphical models by exploiting the graph structure. The first section presents the Factor Graph. The second section gives a brief introduction to Belief Propagation on tree-structured factor graphs. The third section provides an intuition on how to interpret Belief Propagation in terms of probabilistic inference. The fourth section then extends the concept of Belief Propagation to cyclic graphs where the algorithm might not converge anymore. The fifth section shows some of the approaches that have been made to provide a better understanding of Loopy Belief Propagation. However, full comprehension of the algorithm on a general graph is not achieved yet according to the literature found within the scope of this report. On the one hand, empirical studies have been made, on the other hand some analytic analysis of message errors and conditions for convergence have been derived. A paper that analyzes the effects of message scheduling in Loopy Belief Propagation is presented as well. The conclusion finally mentions some other algorithms that can be applied for cyclic graphs and discusses them briefly in comparison with Loopy Belief Propagation