In Bayesian machine learning, we often face a fundamental wall: the posterior distribution is mathematically "intractable." Whether we are trying to rank video game players, optimize a black-box function, or reconstruct a signal from noisy sensors, the math usually requires integrating over complex, high-dimensional spaces that have no closed-form solution.
Traditionally, researchers turned to Markov Chain Monte Carlo (MCMC) methods—essentially throwing thousands of random samples at the problem until a shape emerges. But MCMC is slow and computationally expensive. Expectation Propagation (EP), popularized by Tom Minka, offers a deterministic alternative. Instead of sampling, EP approximates the complex posterior by matching its statistical "moments" (like mean and variance) to a simpler distribution, usually a Gaussian.
The Core Intuition: Moment Matching
The "magic" of EP lies in moment matching. Imagine you have a complicated, multi-modal distribution that you cannot easily describe. EP asks: "If I had to replace this with a simple bell curve (a Gaussian), which bell curve would be the best fit?"
The answer is the Gaussian that has the same mean and the same variance as the complicated one. By matching these "moments," you ensure that the approximation captures the center of mass and the spread of the true distribution. As Alyson K. Fletcher and Philip Schniter demonstrate in Learning and free energies for vector approximate message passing, this strategy allows for highly efficient signal reconstruction even when the underlying measurement matrices are ill-conditioned or "difficult."
From Local Factors to Global Consistency
Most complex models are built from many small, "local" constraints or likelihoods. For example, in the TrueSkillTM rating system developed by Ralf Herbrich, Tom Minka, and Thore Graepel, each match outcome is a local constraint: "Player A beat Player B." This constraint is non-linear and non-Gaussian.
EP handles this through an iterative message-passing process:
- Factorization: Break the complex posterior into a product of simple local factors.
- Cavity Distribution: Temporarily remove one local factor to see what the rest of the model "thinks" about a variable.
- Refinement: Combine that "cavity" with the actual non-Gaussian local factor, calculate the moments of this new hybrid, and update the local factor to match those moments.
- Iteration: Repeat this for every factor until the whole system reaches a global consensus.
This iterative refinement allows EP to approximate high-dimensional integrals, such as the probability of a Gaussian sample falling within a polyhedral cone, as explored by John P. Cunningham and Philipp Hennig in Gaussian Probabilities and Expectation Propagation.
Handling Constraints and Non-Conjugacy
EP is particularly powerful when dealing with "hard" constraints that break traditional Gaussian models. In Gaussian processes with monotonicity information, Jaakko Riihimäki and Aki Vehtari use EP to enforce that a function must only increase. They treat "monotonicity" as a series of virtual observations and use EP to project these non-Gaussian constraints back into a tractable Gaussian Process framework.
Similarly, in Bayesian Optimization, researchers often face "black-box" constraints—rules you don't know until you test them. Predictive Entropy Search with Constraints uses EP to construct a Gaussian approximation of the feasible region, allowing the optimizer to "see" where the global minimum likely hides without needing to sample the entire space.
Scaling and Robustness
While standard EP can be computationally heavy for massive datasets, recent innovations have focused on speed. Whitened Expectation Propagation reduces complexity from cubic to linear by leveraging signal statistics to "whiten" data, making it feasible for pixel-level computer vision tasks.
Furthermore, the framework is not limited to Gaussians. Nan Ding 0002 proposed t-divergence Based Approximate Inference, which uses the heavy-tailed $t$-exponential family to make models more resilient to outliers and noise.
Why It Works: The Efficiency of Determinism
The ultimate justification for EP is its surprising accuracy relative to its cost. In Leave Pima Indians Alone, Nicolas Chopin and James Ridgway demonstrate that for many standard benchmarks, EP achieves near-exact results at a fraction of the time required by MCMC. By focusing on the essential statistics (the moments) rather than the exhaustive density, EP provides a "good enough" approximation that is fast enough for real-time systems, from autonomous driving Semantic Property Maps to radiation monitoring.