Interactive demo · Bayesian and Probabilistic Machine Learning · Chapter 10

Expectation propagation and the clutter problem

We want the mean θ of a Gaussian, N(x | θ, 1), but half of the points are clutter from a broad N(x | 0, 10); the prior is θ ~ N(0, 100). The exact posterior is a mixture of 2^N Gaussians (gold, computed here by quadrature). EP approximates every likelihood factor f_n(θ) by a Gaussian-shaped site f̃_n(θ) and refines one site at a time: remove it from q (the cavity, green), multiply in the exact factor (the tilted distribution, gold) and match its mean and variance (white dashed); the new site is what q^new divided by the cavity leaves (red). The bottom panel shows the latest update; the small panels track the error against the computing cost.

Data (N points)

True mean θ

Expectation propagation

Compare with

Scoreboard

Try these

Click a cross to choose the site that the next update refines. Cost is counted in floating-point operations: one EP site update costs 59, one variational Bayes iteration 12N + 2 and one Newton step of the Laplace approximation 19N + 8 (see the Python code).

In the lecture notes

Section 10.7 (expectation propagation: minimising KL(p ‖ q) matches moments, the cavity, the tilted distribution and the EP algorithm) and Section 10.7.1 (the clutter problem: the updates (10.214) to (10.222) and the evidence (10.223), (10.224)).
Section 10.7.2 (EP on graphs, where the same moment matching becomes loopy belief propagation).
Python code: code/ch10_local_variational_ep.py (functions ep_clutter, vb_clutter, laplace_clutter, exact_clutter; Figures 10.15 to 10.17) and the checks in code/checks_ch10b.py.