Loopy Belief Propagation for Approximate Inference: An Empirical Study

By Kevin P. Murphy, Yair Weiss, Michael I. Jordan. 1999

Recently, researchers have demonstrated that "loopy belief propagation" -- the use of Pearl's polytree algorithm in a Bayesian network with loops -- can perform well in the context of error-correcting codes. The most dramatic instance of this is the near Shannon-limit performance of "Turbo Codes" -- codes whose decoding algorithm is equivalent to loopy belief propagation in a chain-structured Bayesian network. In this paper we ask: is there something special about the error-correcting code context, or does loopy propagation work as an approximate inference scheme in a more general setting? We compare the marginals computed using loopy propagation to the exact ones in four Bayesian network architectures, including two real-world networks: ALARM and QMR. We find that the loopy beliefs often converge and when they do, they give a good approximation to the correct marginals. However, on the QMR network, the loopy beliefs oscillated and had no obvious relationship to the correct posteriors. We present some initial investigations into the cause of these oscillations, and show that some simple methods of preventing them lead to the wrong results.

Subfields: Probabilistic & Bayesian Methods

How researchers see this paper

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

In Probabilistic & Bayesian Methods

Citations in the corpus

Deep Unsupervised Learning using Nonequilibrium Thermodynamics (2015, background): “…instance mean ﬁeld theory and its expansions [39, 40], variational Bayes [19], contrastive divergence [44, 13], minimum probability ﬂow [36, 35], minimum KL contraction [28], proper scoring rules [9, 32], score matching [15], pseudolikelihood [5], loopy belief propagation [29], and many, many more.”
Discriminative Embeddings of Latent Variable Models for Structured Data (2016, positive): “Several theoretical studies have also provided insight into the approximations made by loopy BP, partially justifying its application to graphs with cycles (Wainwright & Jordan, 2008; Yedidia et al., 2001a).”
Determinantal Point Processes for Machine Learning (2012, background): “What makes DPPs particularly unique is the marriage of these computational advantages with the ability to express global, negative interactions between modeling variables; this repulsive domain is notoriously intractable using traditional approaches like graphical models [17, 70, 82, 109, 146, 156, ”
Kernel Belief Propagation (2011, background): “In many applications, however, the resulting loopy BP algorithm exhibits excellent empirical performance (Murphy et al., 1999).”
Representation Learning on Graphs: Methods and Applications (2017, methodology): “Motivated by this connection, Dai et al. [16] also propose a modiﬁed encoder based on Loopy Belief Propagation [41].”
Sentence-State LSTM for Text Representation (2018, background): “S-LSTM is inspired by message passing over graphs (Murphy et al., 1999; Scarselli et al., 2009).”
Deep Coordination Graphs (2019, background): “However, subtracting a normalization constant cij := ∑ a μ ij t (a) / |A| from each message μ before it is sent often leads to convergence in cyclic graphs as well (Murphy et al., 1999; Crick & Pfeffer, 2002; Yedidia et al., 2003).”
Expectation Propagation for approximate Bayesian inference (2001, background): “In belief networks with loops it is known that approximate marginal distributions can be obtained by iterating the be lief propagation recursions, a process known as loopy be lief propagation (Frey & MacKay, 1997; Murphy et al., 1999).”
Recurrent Relational Networks (2017, methodology): “In our experiments, since the messages in (1) are linear, this is similar to how log-probabilities are summed in belief propagation [Murphy et al., 1999].”
Inductive biases for deep learning of higher-level cognition (2020, neutral): “consider loopy belief propagation [195,196].”
Dynamic conditional random fields: factorized probabilistic models for labeling and segmenting sequence data (2004, methodology): “Although belief propagation is exact only in certain special cases, in practice it has been a successful approximate method for general graphical models (Murphy et al., 1999; Aji et al., 1998).”
CCCP Algorithms to Minimize the Bethe and Kikuchi Free Energies: Convergent Alternatives to Belief Propagation (2002, methodology): “…proven to converge only for tree-like graphical models (Pearl, 1988), it has been amazingly successful when applied to inference problems with closed loops (Freeman & Pasztor, 1999; Frey, 1998; Murphy, Weiss, & Jordan, 1999) including these particularly important coding applications (Forney, 2001).”
Extracting Places and Activities from GPS Traces Using Hierarchical Conditional Random Fields (2007, unknown): “If the graph contains loops, in which case BP is called loopy BP, then the algorithm is only approximate and might not converge to the correct probability distribution (Murphy et al. 1999).”
Recurrent Relational Networks for Complex Relational Reasoning (2018, methodology): “Empirically it works well though and it is widely used (Murphy et al., 1999).”