• login

Belief Propagation

Loopy Belief Propagation

Loopy belief propagation (Pearl 1988) is a popular algorithm for approximate inference. Its popularity stems in part from its extremely effective application to channel coding, first to turbo decoding and then to low-density parity check (LDPC) codes (McEliece et al. 1998). While initially not well understood, in recent years a host of theoretical results have been obtained which help to quantify its behavior.

Bethe approximation

Bethe trees and convergence

One way to understand the behavior of loopy belief propagation in a graph G is by constructing the "Bethe tree" of G. The Bethe tree is formed by "unrolling" G around a root node (say, "1"), so that the root of the Bethe tree corresponds to node "1", the next level

Self-avoiding walk trees and accuracy

The self-avoiding walk (SAW) tree of a graph is a sub-tree of the Bethe tree (Figure 1, black only). In essence, it corresponds to the unrolling of the graph G, up to the point at which each path forms a loop. Self-avoiding is a slight misnomer, since the walks forming this graph do intersect themselves, but only at the terminal point.

It turns out that the SAW tree is also closely connected to the behavior of belief propagation on G. Weitz (2006) and Jung and Shaw (2007) showed that marginalization in a binary, pairwise Markov random field defined on G can be performed exactly on the SAW tree, which suggested various approximations to exact inference corresponding to early termination of the SAW tree. We showed (2007) that the error incurred by belief propagation on any Markov random field defined on G can also be computed via methods similar to our convergence results. (While the paper focuses on pairwise MRFs, extension to the more general factor graph formulation is trivial.)