4
$\begingroup$

In reading up on the Expectation-Mmaximization algorithm on Wikipedia, I read this short and intriguing line, under the subheading "Geometric Intuition":

In information geometry, the E step and the M step are interpreted as projections under dual affine connections, called the e-connection and the m-connection; the Kullback–Leibler divergence can also be understood in these terms.

Interesting! A geometric way to view the algorithm sounds great, but this is a rather vague statement... I also know something about KL-divergence, but my understanding of it is also decidedly NOT geometric.

This promise of a geometric picture of EM and KL-divergence is intriguing. Can someone either point to a colorful illustration of what this means, or else help supply it? I am most interested in the case of covariance estimation (perhaps with missing data), if it is desirable to fix a setting.

If I am asking for too much, help pointing me to a reference that can get me "up and running" fairly quickly to a decent picture of things would be much appreciated!

$\endgroup$
3
$\begingroup$

In the derivation of EM, the log-likelihood is decomposed into two terms $$\log p(x|\theta) = F(q, \theta) + D_{KL}(q | p_{z|x,\theta})$$ where $F(q, \theta)$ is the evidence lower bound. The E-step optimizes $F(q, \theta)$ wrt $q$, which is done by setting $D_{KL}(q | p_{z|x,\theta})=0$. The M-step optimizes $F(q, \theta)$ wrt $\theta$.

It turns out these two terms $F$ and $D_{KL}$ can be transformed into the same form $D_{KL}(q_{x,z} | p_{x,z})$ (details are shown later), and in the E-step we optimize $D_{KL}(q_{x,z} | p_{x,z})$ wrt $q_{x,z}$ in the M-step we optimize wrt $p_{x,z}$.

If we think of the set of all distributions as a space, then KL divergence can be thought of as a distance measure in the space. The two distributions $q_{x,z}$ and $p_{x,z}$, can be thought of as points living in two manifolds in the space satisfying their own constraints. Therefore the EM algorithm is to find two distributions from each manifold that minimize the KL divergence $D_{KL}(q_{x,z} | p_{x,z})$.


There's a nice illustration in this paper (information geometry and maximum likelihood criteria). Say $Y$ is the data set and $x$ the latent variable, we can define the data manifold $D$ as $$D=\{p_Y: \sum_xp_Y(y,x)=\hat{p_Y}(y)=\frac{1}{\mid Y\mid}\sum_{i\in Y}\delta(y_i)\}$$ which is the set of all joint distributions $p_Y(x,y)$ whose marginals $p_Y(y)$ place all the mass on the observed data $Y$.

Let the model manifold $M=\{q_\theta(x,y)\}$ be the set of all distributions represented by the model, it can be shown that minimizing the KL-divergence $D_{KL}(p_Y|q_\theta)$ between these two manifolds is equivalent to maximizing the log likelihood $\log q_\theta(Y)$. If we minimize over $p_Y$ and $q_\theta$ alternatively then it's the same algorithm as EM.

E step corresponds to $\arg\min_{p_Y\in D}D_{KL}(p_Y|q_\theta)$, we have $$p_Y^*(x,y)=q_\theta(x|y)\hat{p_Y}(y)$$ which is to compute $q_\theta(x|y)$.

M step corresponds to $\arg\min_{q_\theta\in M}D_{KL}(p_Y|q_\theta)$, which is equivalent to $$\arg\max_{q_\theta\in M}\int p_Y(x,y)\log q_\theta(x,y) dxdy$$ substituting in $p_Y^*$ we have $$\arg\max_{q_\theta\in M}\int q_{\theta}(x|y)\hat{p_Y}(y)\log q_\theta(x,y) dxdy=\arg\max_{q_\theta\in M}\int \hat{p_Y}(y)E_{q_{\theta'}(x|y)}[\log q_\theta(x,y)]dy$$ $$=\arg\max_{q_\theta\in M}Q(\theta|\theta').$$
enter image description here


As mentioned in the paper there's also the geometric em algorithm based on the exponential family and sufficient statistics, where the terms e-connection and m-connection basically refer to optimizing $D_{KL}(p|q)$ wrt the first and second parameter in that setting.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.