Expectation Propagation for approximate Bayesian inference

By Tom Minka. 2001

1,996 citations recorded by the source corpus.

This paper presents a new deterministic approximation technique in Bayesian networks. This method, "Expectation Propagation," unifies two previous techniques: assumed-density filtering, an extension of the Kalman filter, and loopy belief propagation, an extension of belief propagation in Bayesian networks. Loopy belief propagation, because it propagates exact belief states, is useful for a limited class of belief networks, such as those which are purely discrete. Expectation Propagation approximates the belief states by only retaining expectations, such as mean and varitmce, and iterates until these expectations are consistent throughout the network. This makes it applicable to hybrid networks with discrete and continuous nodes. Experiments with Gaussian mixture models show Expectation Propagation to be donvincingly better than methods with similar computational cost: Laplace's method, variational Bayes, and Monte Carlo. Expectation Propagation also provides an efficient algorithm for training Bayes point machine classifiers.

Subfields: Artificial Intelligence, 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 Artificial Intelligence

In Probabilistic & Bayesian Methods

Citations in the corpus

Analytic-DPM: an Analytic Estimate of the Optimal Reverse Variance in Diffusion Probabilistic Models (2022, background): “The proof of Theorem 1 consists of three key steps: • The first step (see Lemma 9) is known as the moment matching (Minka, 2013), which states that approximating arbitrary density by a Gaussian density under the KL divergence is equivalent to setting the first two moments of the two densities as the”
Reinforcement Learning and Control as Probabilistic Inference: Tutorial and Review (2018, background): “In the case of Toussaint (2009), expectation propagation (Minka, 2001) was adapted for approximate message passing during planning.”
A* Sampling (2014, background): “…of bounds: constant bounds as in the clutter problem; linear bounds, where we compute linear upper bounds on each term of the sum, then sum the linear functions and take the max over the region; and quadratic bounds, which are the same as linear except quadratic bounds are computed on each term.”
BinaryConnect: Training Deep Neural Networks with binary weights during propagations (2015, methodology): “EBP is based on Expectation Propagation (EP) [41], which is a variational Bayes method used to do inference in probabilistic graphical models.”
Kernel Mean Embedding of Distributions: A Review and Beyonds (2016, methodology): “Minka (2001) proposes the expectation-propagation (EP) algorithm which requires an estimation of only certain moments of the messages.”
Variational Inference: A Review for Statisticians (2016, background): “As one example, expectation propagation (Minka 2001) is inspired by the KL divergence “in the other direction,” between p ( z | x ) and q ( z ) .”
Progress & Compress: A scalable framework for continual learning (2018, background): “(Husz´ar, 2017) propose taking the expectation propagation (EP) (Minka, 2001) approach of keeping an explicit approximation term for each likelihood, so that when a task is revisited the approximation to its likelihood can be removed and recomputed.”
Variational Auto-Regressive Gaussian Processes for Continual Learning (2020, background): “Expectation Propagation (EP) (Minka, 2001) then proceeds by repeating the following steps to convergence: i) remove the approximate contributions gi and hi from the posterior to form the cavity for i-th datum, ii) merge the cavity with p(y(t)i | f,x (t) i ) to form the tilted distribution p̃i, iii)…”
Online Structured Laplace Approximations For Overcoming Catastrophic Forgetting (2018, background): “Laplace propagation, similar to expectation propagation [27], maintains a factor for every task, but approximates each of them with a Gaussian.”
Dropout Inference in Bayesian Neural Networks with Alpha-divergences (2017, methodology): “, 2016; Li & Turner, 2016; Minka, 2005) is a class of approximate inference methods extending on VI, approximating EP’s energy function (Minka, 2001) as well as the Hellinger distance (Hellinger, 1909).”
Multiplicative Normalizing Flows for Variational Bayesian Neural Networks (2017, neutral): “Many works have considered the task of approximate Bayesian inference for neural networks using either Markov Chain Monte Carlo (MCMC) with Hamiltonian Dynamics (Neal, 1995), distilling SGD with Langevin Dynamics (Welling & Teh, 2011; Korattikara et al., 2015) or deterministic techniques such as the”
Deep Bayesian Bandits Showdown: An Empirical Comparison of Bayesian Deep Networks for Thompson Sampling (2018, background): “ that it underestimates uncertainty (e.g., (Bishop, 2006)), which could lead to under-exploration. Expectation-Propagation The family of expectation-propagation algorithms (Opper & Winther, 2000; Minka, 2001b;a) is based on the message passing framework (Pearl, 1986). They iteratively approximat”
Assumed Density Filtering Methods for Learning Bayesian Neural Networks (2016, methodology): “Following (Hern´andez-Lobato and Adams 2015), we incorporate the prior terms N ( w ijl | 0 , λ − 1 ) into the approximate posterior using expectation propagation (EP) (Minka 2001a).”
Binarized Neural Networks (2016, methodology): “. Soudry et al. (2014); Cheng et al. (2015) do not train their DNN with Backpropagation (BP) but with a variant called Expectation Backpropagation (EBP). EBP is based on Expectation Propagation (EP) (Minka, 2001), which is a variational Bayes method used to do inference in probabilistic graphical mo”
Note on the quadratic penalties in elastic weight consolidation (2017, methodology): “EWC can be seen as an on-line approximate inference algorithm, closely related to assumed density ﬁltering [ADF Opper and Winther, 1998, Minka, 2001] and Laplace propagation [Eskin et al., 2004].”
Optimal control as a graphical model inference problem (2009, neutral): “del obstacles as subsets of the state space where R(x) = ∞. For such non-diﬀerential problems a variational (Gaussian) approximation will not work, but we have recently obtained good results using EP [18]. It is well-known that approximate inference methods are particularly successful for sparse, or”
Streaming Variational Bayes (2013, methodology): “An EP [7] algorithm for approximating the LDA posterior appears in Alg.”
Structured and Efficient Variational Deep Learning with Matrix Gaussian Posteriors (2016, background): “Finally, (Hern´andez-Lobato & Adams, 2015) also assume fully factorized posterior distributions and uses Expectation Propagation (Minka, 2001) instead of variational in-Structured ference.”
Entropy Search for Information-Efficient Global Optimization (2011, background): “However, it is possible to construct an eﬀective approximation ˆ q min based on Expectation Propagation (EP) (Minka, 2001): Consider the belief p ( f (˜ x )) as a “prior message” on f (˜ x ), and each of the terms in the product as one factor providing another message.”