Accuracy of Loopy belief propagation in Gaussian models.

Abstract

This paper considers the loopy belief propagation (LBP) algorithm applied to Gaussian graphical models. It is known for Gaussian belief propagation that, if LBP converges, LBP computes the exact posterior means but incorrect variances. In this paper, we analytically derive the posterior variances for some special structured graphs and clarify the accuracy of LBP. For the graphs of a single cycle, we derive a rigorous solution for the posterior variances and thereby find the quantity that determines the accuracy of LBP. Based on this result, we state a necessary condition for LBP convergence. The quantity above also plays an important role in graphs of a single cycle with arbitrary trees. For arbitrary topological graphs, we consider the situation where correlations between any pair of nodes are comparatively small and show analytically the principal values that determine the accuracy of LBP.