The Linearization of Belief Propagation on Pairwise Markov Random Fields

Belief Propagation (BP) is an iterative message-passing algorithm for performing inference in graphical models Convergent message-passing algorithms. There has (GMs), such as Markov Random Fields (MRFs). BP calculates been much research on finding variations to the update equations the marginal distribution for each unobserved node, of BP that guarantee convergence. These algorithms conditional on any observed nodes (Pearl 1988). It achieves are often similar in structure to the nonconvergent algorithms, this by propagating the information from a few observed yet it can be proven that the value of the variational nodes throughout the network by iteratively passing information problem (or its dual) improves at each iteration (Hazan and between neighboring nodes. It is known that when Shashua 2008; Heskes 2006; Meltzer, Globerson, and Weiss the graphical model has a tree structure, then BP converges 2009). Another body of recent papers have suggested to to the true marginals (according to exact probabilistic inference) solve the convergence problems of MMinference by linearizing after a finite number of iterations.