# UMass LIVING

## June 22, 2009

### (Jun 25 3-5pm) Pre-meeting Overview: Wainwright / Jordan, ch 4.3

Filed under: Uncategorized — umassliving @ 6:14 pm
Tags: ,

This week’s reading is on expectation propagation (EP), another method for approximating the negative entropy $A^\ast$ and the set of realizable mean parameters $\mathcal{M}$.

The idea behind EP is to partition the sufficient statistics into a tractable component and an intractable component, such that it is possible to exactly compute marginals in polynomial time for the distribution associated with the tractable component, as well as the distributions associated with the tractable component combined with any one element of the intractable component.

This partitioning leads to an approximation of $\mathcal{M}$ as $\mathcal{L}$ given in Equation 4.67 (how do we know that $\mathcal{L}$ is convex?), and an approximation of the entropy as $H_{ep}$ given in Equation 4.68.  As before, we can apply the Lagrangian method to the resulting constrained optimization problem, and derive the moment matching EP updates (Fig 4.7).

Important things to follow:

• The running example of the mixture model – Example 4.8, Example 4.12
• How the Bethe approximation can be seen as a specific case of EP and sum-product as a case of moment matching – Example 4.9, Example 4.10
• Deriving the EP updates – Section 4.3.2
• Tree-structured EP – Example 4.11

The Bethe approximation is a special case of EP where all the sufficient statistics associated with the nodes are put into the tractable component, and each sufficient statistic associated with an edge is an element of the intractable component.  How would $H_{ep}$ and $\mathcal{L}$ change if, instead, we took the sufficient statistic associated with one particular node, removed it from the tractable component, and made it a separate element of the intractable component?