Expectation propagation
Expectation propagation (EP) is a technique in Bayesian machine learning.[1]
EP finds approximations to a probability distribution.[1] It uses an iterative approach that uses the factorization structure of the target distribution.[1] It differs from other Bayesian approximation approaches such as variational Bayesian methods.[1]
More specifically, suppose we wish to approximate an intractable probability distribution [math]\displaystyle{ p(\mathbf{x}) }[/math] with a tractable distribution [math]\displaystyle{ q(\mathbf{x}) }[/math]. Expectation propagation achieves this approximation by minimizing the Kullback-Leibler divergence [math]\displaystyle{ \mathrm{KL}(p||q) }[/math].[1] Variational Bayesian methods minimize [math]\displaystyle{ \mathrm{KL}(q||p) }[/math] instead.[1]
If [math]\displaystyle{ q(\mathbf{x}) }[/math] is a Gaussian [math]\displaystyle{ \mathcal{N}(\mathbf{x}|\mu, \Sigma) }[/math], then [math]\displaystyle{ \mathrm{KL}(p||q) }[/math] is minimized with [math]\displaystyle{ \mu }[/math] and [math]\displaystyle{ \Sigma }[/math] being equal to the mean of [math]\displaystyle{ p(\mathbf{x}) }[/math] and the covariance of [math]\displaystyle{ p(\mathbf{x}) }[/math], respectively; this is called moment matching.[1]
Applications
Expectation propagation via moment matching plays a vital role in approximation for indicator functions that appear when deriving the message passing equations for TrueSkill.
References
- Thomas Minka (August 2–5, 2001). "Expectation Propagation for Approximate Bayesian Inference". in Jack S. Breese, Daphne Koller. UAI '01: Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence. University of Washington, Seattle, Washington, USA. pp. 362–369. http://research.microsoft.com/en-us/um/people/minka/papers/ep/minka-ep-uai.pdf.
External links
 |  |
