Expectation propagation (EP) is a technique in Bayesian machine learning used to approximate probability distributions that are computationally intractable to handle exactly. It was introduced by Thomas Minka in a 2001 paper presented at the 17th Conference on Uncertainty in Artificial Intelligence. The method is designed to find a tractable approximation to a complex target distribution by exploiting the factorization structure of that distribution, making it useful in various inference problems across Machine learning and related fields.
The core idea of EP is to approximate an intractable distribution \(p(\mathbf{x})\) with a simpler, tractable distribution \(q(\mathbf{x})\). This is achieved by minimizing the Kullback-Leibler divergence \(\mathrm{KL}(p||q)\), a measure of how one probability distribution diverges from a second. This choice of divergence direction is a key distinction from variational Bayesian methods, which instead minimize \(\mathrm{KL}(q||p)\). The practical consequence is that EP tends to focus on matching the overall shape of the target distribution, including its moments, rather than avoiding regions where the target is small.
When the approximating distribution \(q(\mathbf{x})\) is chosen to be a Gaussian \(\mathcal{N}(\mathbf{x}|\mu, \Sigma)\), minimizing \(\mathrm{KL}(p||q)\) leads to a closed-form solution: the optimal \(\mu\) and \(\Sigma\) are simply the mean and covariance of the target distribution \(p(\mathbf{x})\). This operation, known as moment matching, is central to the EP algorithm. In practice, EP iteratively updates individual factors of the approximation, refining the moments until convergence, which allows it to handle complex factorized models.
Algorithmic Framework
The EP algorithm operates by maintaining an approximation to each factor of the target distribution. Initially, these factor approximations are set to simple forms, often uniform or Gaussian. The algorithm then iterates through each factor, removing it from the current approximation, computing a cavity distribution, and then projecting the resulting tilted distribution back onto the tractable family via moment matching. This process is repeated until the approximations stabilize, yielding a final \(q(\mathbf{x})\) that approximates the full target.
A notable strength of EP is its ability to handle non-Gaussian factors, such as indicator functions, which are common in models involving constraints or discrete outcomes. The moment matching step ensures that the approximation captures the essential statistics of these factors, even when exact inference is impossible. This flexibility has made EP a popular choice for approximate inference in Probabilistic graphical models and other structured prediction tasks.
Applications
One prominent application of EP is in the derivation of message passing equations for TrueSkill, a ranking system developed by Microsoft Research for online gaming. TrueSkill models player skill as a Gaussian distribution and updates these estimates based on match outcomes. The indicator functions that arise from win-loss events are intractable to handle directly, but EP provides an efficient way to approximate them, enabling real-time skill estimation and matchmaking.
Beyond TrueSkill, EP has been applied in areas such as Neural network training, where it can be used for Bayesian inference over weights, and in Large language model contexts for uncertainty quantification. Its ability to provide calibrated uncertainty estimates has made it relevant in fields like Artificial intelligence and Deep learning, where probabilistic interpretations of models are increasingly valued.
Comparison with Other Methods
EP differs fundamentally from variational Bayesian methods in the direction of the Kullback-Leibler divergence minimized. Variational methods, which minimize \(\mathrm{KL}(q||p)\), tend to produce approximations that are more conservative, often underestimating the variance of the target. In contrast, EP's use of \(\mathrm{KL}(p||q)\) can lead to approximations that better capture the target's variance, though it may be less stable in some cases.
Another related approach is Markov chain Monte Carlo (MCMC), which provides asymptotically exact samples but can be computationally expensive. EP offers a deterministic alternative that is often faster, at the cost of introducing approximation error. This trade-off makes EP particularly attractive in large-scale problems where sampling is impractical.
Limitations and Extensions
EP is not guaranteed to converge for all models, and its performance can depend on the initialization of the factor approximations. In some settings, the moment matching updates can oscillate or diverge, requiring damping or other stabilization techniques. Researchers have developed variants, such as expectation propagation with damping and fractional EP, to address these issues.
Despite these challenges, EP remains a widely used tool in the Bayesian inference toolbox. Its theoretical foundations, laid out in Minka's original work, have inspired numerous extensions and applications, from Computer vision to Reinforcement learning. The method's ability to balance accuracy and computational efficiency continues to make it a subject of active research in the Stanford AI Lab and other leading institutions.
See Also
- variational-inference
- Bayesian Inference
- moment-matching
- trueskill