Correctness of Belief Propagation in Gaussian Graphical Models of Arbitrary Topology

By Yair Weiss, William T. Freeman. 1999

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Kernel Belief Propagation (2011, background): “In these applications, the variables are usually assumed either to be finite dimensional, or in continuous cases, to have a Gaussian distribution (Weiss & Freeman, 2001).”
On Convergence Conditions of Gaussian Belief Propagation (2015, methodology): “It is known that damped Gaussian BP shares the same fixed points as Gaussian BP [25], thus damped Gaussian BP can also be applied to compute the true marginal mean upon convergence [6].”
On the construction of some capacity-approaching coding schemes (2000, methodology): “Another approach to understand the sum-product algorithm on a graph with many cycles is to assume that all variables are jointly Gaussian [23, 71, 57].”
Distributed Estimation of Variance in Gaussian Graphical Model via Belief Propagation: Accuracy Analysis and Improvement (2015, methodology): “Lemma 1: [15] If , the error between the exact marginal variance and the variance calculated with BP at the -th iteration equals to”
Learning 3D Part Detection from Sparsely Labeled Data (2014, methodology): “The most common approaches to inference on graphical models with cycles are message passing algorithms such as Loopy Belief Propagation (LBP) and Tree Re-Weighted Belief Propagation [27], [15].”
Learning Low-Level Vision (1999, unknown): “Strong empirical results in \Turbo codes" [24, 27] and recent theoretical work [39, 40] provide support for a very simple approximation: applying the propagation rules derived above even in a network with loops.”
Inference in Probabilistic Graphical Models by Graph Neural Networks (2018, background): “Past work provides some insight into the dynamics and convergence properties of BP [28]–[30].”
Bayesian Spiking Neurons I: Inference (2008, background): “…inference and priors in human perception recently has been shown to account for a wide range of perceptual phenomena (Knill & Richards, 1996; Weiss & Freeman, 2001; Weiss & Fleet, 2002; Feldman, 2001; Geisler, Perry, Super, & Gallogly, 2001; van Beers, Sittig, & Gon, 1999; Ernst & Banks,…”
Bounded approximate decentralised coordination via the max-sum algorithm (2009, background): “, to find the maximum a posteriori assignment in Markov random fields [23] or compute the posterior probabilities [24]).”
Cooperative Localization in Wireless Networks (2009, background): “However, the computed functions b Xk (·) and b∗Xl (·) are no longer exactly equal to the corresponding marginal a posteriori distributions, and bX is not necessarily a distribution [97].”
Analysis of sum-product decoding of low-density parity-check codes using a Gaussian approximation (2001, unknown): “In other related works, the sum-product algorithm was analyzed for graphs with cycles when messages are jointly Gaussian [19]–[21], [31].”
MRF Energy Minimization and Beyond via Dual Decomposition (2011, unknown): “However, despite the fact that there has been a lot of work on trying to provide a better theoretical analysis of BP-based algorithms [57], [51], [50], [15], an important drawback of these methods remains that their theoretical optimality and/or convergence properties are not yet well understood…”
Simultaneous Localization and Mapping with Sparse Extended Information Filters (2004, methodology): “This sparse matrix defines a Web-like network of local relative constraints between pairs of adjacent features in the map, reminiscent of a Gaussian Markov random field (Weiss and Freeman 2001).”
Gaussian sampling by local perturbations (2010, methodology): “However, in graphs with cycles its loopy version typically underestimates the marginal variances since it overcounts the evidence, even when it converges to the correct means [13,33].”