Correctness of Local Probability Propagation in Graphical Models with Loops

By Yair Weiss. Neural Computation, 2000

529 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Networks and Communications, Molecular Biology

View Paper: https://www.semanticscholar.org/paper/300f73c89bfeb6b88b9b18f63793568c3d06bee6

How researchers see this paper

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

In Artificial Intelligence

In Computer Networks and Communications

In Molecular Biology

Citations in the corpus

Learning to Reason: Leveraging Neural Networks for Approximate DNF Counting (2019, methodology): “pply to weighted #DNF. Beyond hashing techniques, loopy belief propagation (LBP) (Pearl 1982; Murphy, Weiss, and Jordan 1999) has been applied to approximate WMC. LBP does not provide any guarantees (Weiss 2000). Conceptually, our work also uses message passing, but instead learns messages and state”
Estimating the "Wrong" Graphical Model: Benefits in the Computation-Limited Setting (2006, background): “The behavior of sum-product is relatively well understood in certain settings, including graphs with single cycles (Weiss, 2000), Gaussian models (Freeman and Weiss, 2001; Rusmevichientong and Roy, 2000) and Ising models (Tatikonda and Jordan, 2002; Ihler et al.”
Residual Splash for Optimally Parallelizing Belief Propagation (2009, background): “1 to arbitrary cyclic graphs by considering the possibly unbounded computation tree described by Weiss [2000]. Mooij and Kappen [2007] provide sufficient conditions for fBP(m) to be a contraction mapping under a variety of norms including a variation of the max-morm.”
The generalized distributive law (2000, background): “Conversely, the AI community has become excited by the developments in the information theory community [14] [38], which demonstrate that these algorithms can be successful on graphs with cycles.”
Segmentation and Tracking of Multiple Humans in Crowded Environments (2008, methodology): “MCMC-based methods are receiving increasing popularity for computer vision problems due to their flexibility in optimizing an arbitrary energy function as opposed to energy functions of a specific type as in graph cut [2] or belief propagation [49].”
On the optimality of solutions of the max-product belief-propagation algorithm in arbitrary graphs (2001, methodology): “It is easy to show [20] that sum-product belief propagation on this graph gives the turbo decoding algorithm and max-product belief propagation gives the modi ed turbo decoding algorithm of [3].”
Graphical Models, Exponential Families, and Variational Inference (2008, background): “However, it is known [244, 107] that for any discrete Markov random field in exponential family form with at most a single cycle, the sum-product has a unique fixed point, and always converges to it.”
Constructing free-energy approximations and generalized belief propagation algorithms (2005, background): “In graphs with no more than a single cycle, it was known that if all factors are soft, then there was a unique BP fixed point [45].”
Scale-invariant contour completion using conditional random fields (2005, methodology): “We approximate the edge and vertex degree expectations using loopy belief propagation[26].”
Bounded approximate decentralised coordination via the max-sum algorithm (2009, background): “, several researchers have focused on the analysis of the convergence and solution quality in graphs containing just a single loop [30, 31]).”
Unsupervised Learning (2018, unknown): “Although BP is only valid on singly connected graphs there is a large body of research on its application to multiply connected graphs— the use of BP on such graphs is called loopy belief propagation and has been analyzed by several researchers [39, 40].”
Tree consistency and bounds on the performance of the max-product algorithm and its generalizations (2004, background): “Freeman and Weiss (2001) analyzed the max-product assignment for positive compatibility functions on arbitrary graphs, and showed that the cost of the max-product assignment cannot be improved by changing any subset of the variables that form no more than a single cycle in the underlying graph.”
Multiresolution Markov models for signal and image processing (2002, methodology): “[143], [168]–[170], [197], [204], [236], [267], [294], [295], [302], [337], [339], [357].”
A Bayesian network framework for relational shape matching (2003, background): “This representation matches up well with recent work in Bayesian networks [29].”
Contour Detection and Hierarchical Image Segmentation (2011, background): “They use loopy belief propagation [43] to compute expectations.”