The core challenge of Bayesian inference lies in computing the posterior distribution. According to Bayes' theorem, the posterior is proportional to the product of a prior and a likelihood function. When dealing with complex, real-world systems, this likelihood function is rarely conjugate to the prior. Instead, it often introduces non-linearities, discrete constraints, or non-smooth boundaries that render exact integration mathematically intractable.
To bypass this intractability, researchers rely on approximate inference. While Markov Chain Monte Carlo (MCMC) sampling provides asymptotic exactness, its computational burden is often prohibitive. Deterministic alternatives like the Laplace approximation simplify the posterior by fitting a Gaussian at the mode via a local Taylor expansion, but they fail when the posterior is non-smooth or multi-modal. Variational Inference (VI) recomputes the problem as an optimization task by minimizing the reverse Kullback-Leibler (KL) divergence, $\text{KL}(q \parallel p)$, which typically underestimates uncertainty by fitting tightly around a single mode.
Expectation Propagation (EP) offers a different path. It is a deterministic message-passing algorithm that constructs a global, tractable approximation (typically a Gaussian) by minimizing the forward KL divergence, $\text{KL}(p \parallel q)$. This choice of objective function forces the approximation to be "mass-covering," capturing the overall mean and variance (the moments) of the true distribution rather than merely anchoring to its peak.
The Core Mechanism: Factorization and Local Updates
To understand why EP works, consider a target posterior distribution $p(\theta)$ that factorizes into a prior $f_0(\theta)$ and a set of $n$ independent likelihood terms $f_i(\theta)$:
$$p(\theta) = \frac{1}{Z} f_0(\theta) \prod_{i=1}^n f_i(\theta)$$
where $Z$ is the normalizing constant (the marginal likelihood). EP aims to approximate this intractable product with a unnormalized exponential family distribution $q(\theta)$, such as a multivariate Gaussian:
$$q(\theta) = t_0(\theta) \prod_{i=1}^n t_i(\theta)$$
Here, each $t_i(\theta)$ is a simple, tractable "site approximation" (e.g., an unnormalized Gaussian factor) corresponding to the complex true factor $f_i(\theta)$.
Optimizing all site approximations simultaneously is too difficult. EP solves this by updating one site approximation $t_i(\theta)$ at a time, iteratively refining the global approximation $q(\theta)$ until consistency is reached across all factors.
[True Posterior Factors] f_1(θ) f_2(θ) ... f_n(θ)
| | |
v v v
[EP Site Approximations] t_1(θ) t_2(θ) ... t_n(θ)
\_____________\__________ ___________/
|
v
[Global Approximation q(θ)]
The Cavity Distribution Trick
The elegance of EP lies in how it updates a single site factor $t_i(\theta)$ without losing the context of the rest of the model. The algorithm proceeds through a four-step loop:
-
Compute the Cavity Distribution: To isolate the influence of the $i$-th factor, we remove the current site approximation $t_i(\theta)$ from the global approximation $q(\theta)$. This leaves us with the cavity distribution $q^{\setminus i}(\theta)$: $$q^{\setminus i}(\theta) \propto \frac{q(\theta)}{t_i(\theta)}$$ Because $q(\theta)$ and $t_i(\theta)$ are both Gaussians, this division is simple and amounts to subtracting their natural parameters (precision and precision-adjusted means). As noted by Aki Vehtari et al. in their work on Bayesian Leave-One-Out Cross-Validation Approximations for Gaussian Latent Variable Models, this cavity distribution acts as a highly accurate proxy for the leave-one-out conditional posterior.
-
Form the Hybrid Distribution: Next, we substitute the true, intractable factor $f_i(\theta)$ back into the cavity distribution to form a hybrid distribution $h_i(\theta)$: $$h_i(\theta) = f_i(\theta) q^{\setminus i}(\theta)$$ This hybrid distribution is locally accurate: it pairs the exact non-Gaussian factor we care about with a Gaussian summary of all other data points.
-
Match Moments (Projection): We now update our global approximation $q(\theta)$ by finding a new Gaussian distribution $q^{\text{new}}(\theta)$ that minimizes the forward KL divergence to the hybrid distribution: $$q^{\text{new}}(\theta) = \arg\min_q \text{KL}(h_i(\theta) \parallel q(\theta))$$ Minimizing $\text{KL}(h_i \parallel q)$ is mathematically equivalent to matching the lower-order moments of the distributions. Thus, we compute the exact mean and variance of the hybrid distribution $h_i(\theta)$ and set the mean and variance of $q^{\text{new}}(\theta)$ equal to them. Because $f_i(\theta)$ is a local factor, this integration is low-dimensional and often analytical or easily solved via low-dimensional numerical quadrature.
-
Recover the Updated Site Factor: Finally, we deduce the new site approximation $t_i^{\text{new}}(\theta)$ by dividing the newly updated global distribution by the cavity distribution: $$t_i^{\text{new}}(\theta) \propto \frac{q^{\text{new}}(\theta)}{q^{\setminus i}(\theta)}$$
This process is repeated across all sites iteratively. By matching moments locally, the site approximations learn to smooth out the complex behavior of the true likelihood factors, passing messages back and forth until they agree on a consistent global Gaussian representation.
Why EP Excels Where Others Fail
Handling Non-Smooth and Non-Differentiable Priors
The Laplace approximation relies on the gradient and Hessian at the mode. If a model utilizes a non-differentiable prior—such as a Laplace (sparsity-inducing) prior—the mode often sits precisely on a sharp discontinuity where derivatives are undefined or uninformative.
In Improving posterior marginal approximations in latent Gaussian models, Botond Cseke demonstrates that EP bypasses this limitation entirely. Because moment matching integrates over the distribution mass rather than evaluating point-wise derivatives, EP remains robust and stable in the presence of non-smooth priors. This property is heavily exploited by Sebastian Gerwinn et al. in Bayesian Inference for Spiking Neuron Models with a Sparsity Prior and by Matthias Seeger in Compressed sensing and Bayesian experimental design to maintain conservative, robust uncertainty estimates under $L_1$ regularization frameworks.
Taming Discrete and Hard Constraints
When likelihoods represent discrete outcomes, they introduce step functions or hard thresholds into the posterior. A classic example is the TrueSkillTM: A Bayesian Skill Rating System developed by Ralf Herbrich et al.. In TrueSkill, a player's performance is modeled as a continuous latent variable, but the observed data consists only of discrete win/loss/tie outcomes. This introduces indicator functions into the likelihood that are zero or one depending on whether one latent skill exceeds another.
True Likelihood f_i(θ) (Step Function) EP Site Approximation t_i(θ) (Gaussian)
| |
1 _____| | _--_
| ===> EP Smooths This ===> | / \
| | / \
0 _____|___________ |__/__________\____
| Skill Diff | Skill Diff
A local Taylor expansion cannot handle a step function because its derivative is zero everywhere and infinite at the boundary. EP, however, smooths these hard constraints. When the step function $f_i(\theta)$ is multiplied by the Gaussian cavity distribution $q^{\setminus i}(\theta)$, the resulting hybrid distribution is simply a truncated Gaussian. Calculating the mean and variance of a truncated Gaussian is analytically tractable. EP uses these moments to update the global distribution, effectively smoothing the discrete threshold into a soft Gaussian message.
Broad Utility in Complex Pipelines
Beyond basic classification, EP serves as a foundational engine for complex decision-making frameworks where high-dimensional integration would otherwise stall execution.
In Bayesian Optimization, evaluating acquisition functions over multiple objectives or constraints requires integrating over multivariate Gaussian processes. For instance, Daniel Hernández-Lobato et al. utilize EP in Predictive Entropy Search for Multi-objective Bayesian Optimization to approximate the conditional predictive distributions of Pareto sets. By substituting intractable integration with fast, deterministic moment matching, they reduce exponential computational scaling down to linear scaling.
Similarly, in high-dimensional feature selection, the authors of Predictive automatic relevance determination by expectation propagation demonstrate that using EP to approximate the posterior distribution of feature weights yields significantly more accurate estimates of the posterior mean than local approximations. This prevents the model from prematurely zeroing out relevant features, ensuring robust classification performance in sparse Bayesian frameworks.
Key Foundational Work
Expectation Propagation for approximate Bayesian inference (2001) — contributed 3 concept elements to this direction.