# Expectation maxmisation algorithm increases true likelihood at each iteration

I've heard that the EM algorithm ensures that the true likelihood is non-decreasing at each iteration of the algorithm, but I'm not sure why this is the case. I've provided a basic plot which I believe to illustrate the difficulty I have in understanding this.

To frame the question, let's first consider the EM algorithm decomposition, where $x$ is the observed data, $z$ is the missing data, $\theta$ represents the parameter set.

$$L(\theta) \equiv \text{ln}P(x|\theta) = \text{ln}\left[\sum_{z}P(x|z,\theta)P(z|\theta)\right]$$

Multiplying by $\text{ln}\left[\frac{P(z|x,\theta\prime)}{P(z|x,\theta\prime)}\right]$ and adding and subtracting $L(\theta\prime) \equiv \text{ln}P(x|\theta\prime)$ yields

$$\text{ln}\left[\sum_{z}P(x|z,\theta\prime)\frac{P(x|z,\theta)P(z|\theta)}{P(x|z,\theta\prime)}\right] - \text{ln}P(z|\theta\prime) + L(\theta\prime) \\ \geq \sum_{z}P(x|z,\theta\prime)\text{ln}\left[\frac{P(x|z,\theta)P(z|\theta)}{P(x|z,\theta\prime)P(z|\theta\prime)}\right] + L(\theta\prime)\ldots (\text{by Jensen's inequality}) \\ = \sum_{z}P(x|z,\theta\prime)\text{ln}\left[\frac{P(x,z|\theta)}{P(z,x|\theta\prime)}\right] + L(\theta\prime) \equiv B(\theta,\theta\prime)$$

This represents the expression we want to maximize in the EM process; from this, we can see that $L(\theta\prime)$ is a lower bound for $L(\theta)$ (this bound is realized when $\theta$ is equal to $\theta\prime$).

Now assume two possible entry points (theta$\prime$1 and theta$\prime$2) to the EM process exhibited in the plot below. In this plot, the true likelihood is given by the L(theta) (blue) line whilst the function to be maximised is given by the B(theta,theta$\prime$) (orange) line.

The local maximum corresponding theta$\prime$1 (which corresponds to the lower bound scenario mentioned above, L(theta) = L(theta$\prime)$) does indeed increase L(theta); however, the local maximum corresponding to theta$\prime$2 doesn't increase L(theta). What's to prevent the theta$\prime$2 scenario from happening? Also, I've also heard that the role of the expectation step is to equate $P(x,z|\theta)$ and $P(z,x|\theta\prime)$ which would achieve the lower bound scenario above, but I'm not sure how this works. I suspect that this property is linked to the answer to the above question. Perhaps somebody could elaborate on this.

I think your picture is misleading you. Rather than envisioning a single orange lower-bound approximation to the true blue likelihood, instead you should be thinking of a series of orange lower-bounds that are approximations about particular points $\theta_t$. In particular, the approximation is necessarily tightest about the approximation point. So at $\theta_2$ your orange approximation must be closer to the blue curve than it is at $\theta_{2}^{\mbox{max}}$. See figure (from wikipedia). This follows from the EM derivation. First observe that the incomplete data likelihood can be written as a ratio of a joint and a conditional: $p(X|\theta)=\frac{P(X,Z|\theta)}{P(Z|X,\theta)}$, and that the expectation over $Z$ leaves the LHS unchanged. Restating this fact and taking logs, \begin{align*} \log p(\mathbf{X}|\theta) &= E_z \left[ \log p(\mathbf{X},\mathbf{Z}|\theta) - \log p(\mathbf{Z}|\mathbf{X},\theta) \right] \\ \log p(\mathbf{X}|\theta) & = \sum_{\mathbf{Z}} p(\mathbf{Z}|\mathbf{X},\theta_t) \log p(\mathbf{X},\mathbf{Z}|\theta) - \sum_{\mathbf{Z}} p(\mathbf{Z}|\mathbf{X},\theta_t) \log p(\mathbf{Z}|\mathbf{X},\theta) \\ & = Q(\theta|\theta_t) + H(\theta|\theta_t). \end{align*} So we hope to use $Q(\theta|\theta_t)$ as a surrogate of $\log p(\mathbf{X}|\theta)$, and the error from using this approximation is $-H(\theta|\theta_t)=Q(\theta|\theta_t)-p(\mathbf{X}|\theta)$.
Now, I contend that when $\theta = \theta_t$, then $-H(\theta_t|\theta_t)$ is minimized, thus the approximation is tightest. In fact, this follows directly from $H$ being an expectation of a log-likelihood, which is maximized (thus $-H$ minimized) at its generative value,in this case $\theta_t$. (This is just restating that the expectation of a score function is zero).