Expectation propagation

Expectation propagation (EP) is a technique in Bayesian machine learning.

EP finds approximations to a probability distribution. It uses an iterative approach that uses the factorization structure of the target distribution. It differs from other Bayesian approximation approaches such as variational Bayesian methods.

More specifically, suppose we wish to approximate an intractable probability distribution

    p
    (
    
      x
    
    )
  

{\displaystyle p(\mathbf {x} )}

with a tractable distribution

    q
    (
    
      x
    
    )
  

{\displaystyle q(\mathbf {x} )}

. Expectation propagation achieves this approximation by minimizing the Kullback–Leibler divergence

      K
      L
    
    (
    p
    
      |
    
    
      |
    
    q
    )
  

{\displaystyle \mathrm {KL} (p||q)}

. Variational Bayesian methods minimize

      K
      L
    
    (
    q
    
      |
    
    
      |
    
    p
    )
  

{\displaystyle \mathrm {KL} (q||p)}

instead.

If

    q
    (
    
      x
    
    )
  

{\displaystyle q(\mathbf {x} )}

is a Gaussian

        N
      
    
    (
    
      x
    
    
      |
    
    μ
    ,
    Σ
    )
  

{\displaystyle {\mathcal {N}}(\mathbf {x} |\mu ,\Sigma )}

, then

      K
      L
    
    (
    p
    
      |
    
    
      |
    
    q
    )
  

{\displaystyle \mathrm {KL} (p||q)}

is minimized with

    μ
  

{\displaystyle \mu }

and

    Σ
  

{\displaystyle \Sigma }

being equal to the mean of

    p
    (
    
      x
    
    )
  

{\displaystyle p(\mathbf {x} )}

and the covariance of

    p
    (
    
      x
    
    )
  

{\displaystyle p(\mathbf {x} )}

, respectively; this is called moment matching.

Expectation propagation via moment matching plays a vital role in approximation for indicator functions that appear when deriving the message passing equations for TrueSkill.

.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}body.skin-vector-2022 .mw-parser-output .reflist-columns-2{column-width:27em}body.skin-vector-2022 .mw-parser-output .reflist-columns-3{column-width:22.5em}.mw-parser-output .references[data-mw-group=upper-alpha]{list-style-type:upper-alpha}.mw-parser-output .references[data-mw-group=upper-roman]{list-style-type:upper-roman}.mw-parser-output .references[data-mw-group=lower-alpha]{list-style-type:lower-alpha}.mw-parser-output .references[data-mw-group=lower-greek]{list-style-type:lower-greek}.mw-parser-output .references[data-mw-group=lower-roman]{list-style-type:lower-roman}.mw-parser-output div.reflist-liststyle-upper-alpha .references{list-style-type:upper-alpha}.mw-parser-output div.reflist-liststyle-upper-roman .references{list-style-type:upper-roman}.mw-parser-output div.reflist-liststyle-lower-alpha .references{list-style-type:lower-alpha}.mw-parser-output div.reflist-liststyle-lower-greek .references{list-style-type:lower-greek}.mw-parser-output div.reflist-liststyle-lower-roman .references{list-style-type:lower-roman}

• Thomas Minka (August 2–5, 2001). "Expectation Propagation for Approximate Bayesian Inference". In Jack S. Breese, Daphne Koller (ed.). UAI '01: Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence (PDF). University of Washington, Seattle, Washington, USA. pp. 362–369.{{cite book}}: CS1 maint: location missing publisher (link)

• Minka's EP papers

• List of papers using EP

.mw-parser-output .asbox{position:relative;overflow:hidden}.mw-parser-output .asbox table{background:transparent}.mw-parser-output .asbox p{margin:0}.mw-parser-output .asbox p+p{margin-top:0.25em}.mw-parser-output .asbox-body{font-style:italic}.mw-parser-output .asbox-note{font-size:smaller}.mw-parser-output .asbox .navbar{position:absolute;top:-0.75em;right:1em;display:none}.mw-parser-output :not(p):not(.asbox)+style+.asbox,.mw-parser-output :not(p):not(.asbox)+link+.asbox{margin-top:3em}