# How to picture EM algorithm and KL-divergence geometrically?

In reading up on the Expectation-Maximization 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 understand the algorithm sounds great, but the statement is a rather vague ... Also my understanding of KL-divergence is NOT geometric.

Could someone propose a geometric interpretation? And are there any covariance estimation (perhaps with missing data), related applications?

Related reference would also be much appreciated!

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').$$

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.