Lecture 20 Properties of the EM Algorithm

In lecture 19 we introduced the EM algorithm for models with latent variables: starting from a guess $\theta_{0}$ , the algorithm alternates between computing the function $Q(\theta\mskip 1.0mu|\mskip 1.0mu\theta_{k})$ in the E step and maximising it over $\theta$ in the M step, as in definition 19.2. In this lecture we prove that no step of the algorithm can decrease the observed-data log-likelihood, and that the fixed points of the iteration solve the likelihood equation. We then discuss the issues which arise when the algorithm is used in practice. We use the notation of lecture 19 throughout, and we continue with the two-component normal mixture of example 19.1.

20.1 The Ascent Property

The EM algorithm only ever maximises $Q$ , and it is not obvious that this does anything for the observed-data log-likelihood $\ell$ . The central result of this lecture is that it does: no step of the algorithm can decrease $\ell$ . The proof rests on writing $\ell$ as the difference of $Q$ and a second function $H$ , and we prove this decomposition first. We make three assumptions, which hold for the rest of this lecture:

•

The set of values $z$ with $f_{c}(x,z;\theta)>0$ does not depend on $\theta$ . This is the analogue for the latent variables of condition (R2) in definition 16.1.
•

We have $f(x;\theta)>0$ for every data point $x$ and every $\theta\in\Theta$ , so that $g(z\mskip 1.0mu|\mskip 1.0mux;\theta)$ is defined.
•

The conditional expectation $\mathbb{E}_{\theta^{\prime}}\bigl{(}\log f_{c}(x,Z;\theta)\!\mathrel{\big{|}}% \!X=x\bigr{)}$ is finite for all $\theta,\theta^{\prime}\in\Theta$ and every data point $x$ , so that $Q(\theta\mskip 1.0mu|\mskip 1.0mu\theta^{\prime})$ is finite.

The following lemma gives the decomposition. The function $H$ in it is defined like $Q$ , with the conditional density $g$ in place of the complete-data density $f_{c}$ .

Lemma 20.1.

For all $\theta,\theta^{\prime}\in\Theta$ we have

equation (20.1) (20.1)

\ell(\theta)=Q(\theta\mskip 1.0mu|\mskip 1.0mu\theta^{\prime})-H(\theta\mskip 1% .0mu|\mskip 1.0mu\theta^{\prime}),

where $H$ is given by

H(\theta\mskip 1.0mu|\mskip 1.0mu\theta^{\prime})=\sum_{i=1}^{n}\mathbb{E}_{% \theta^{\prime}}\bigl{(}\log g(Z_{i}\mskip 1.0mu|\mskip 1.0muX_{i};\theta)\!% \mathrel{\big{|}}\!X_{i}\bigr{)}.

Proof.

We start from the formula $g(z\mskip 1.0mu|\mskip 1.0mux;\theta)=f_{c}(x,z;\theta)/f(x;\theta)$ for the conditional distribution of the latent variable. Solving it for $f(x;\theta)$ and taking logarithms gives

\log f(x;\theta)=\log f_{c}(x,z;\theta)-\log g(z\mskip 1.0mu|\mskip 1.0mux;\theta)

for every $z$ with $f_{c}(x,z;\theta)>0$ . By the first assumption, these are the values which $Z$ can take, whatever the parameter. We now replace $z$ by the random variable $Z$ and take conditional expectations given $X=x$ under $\theta^{\prime}$ . Since the left-hand side does not depend on $z$ , it stays the same, and we find

\log f(x;\theta)=\mathbb{E}_{\theta^{\prime}}\bigl{(}\log f_{c}(x,Z;\theta)\!% \mathrel{\big{|}}\!X=x\bigr{)}-\mathbb{E}_{\theta^{\prime}}\bigl{(}\log g(Z% \mskip 1.0mu|\mskip 1.0mux;\theta)\!\mathrel{\big{|}}\!X=x\bigr{)}.

The first term on the right is finite by the third assumption, and thus so is the second. Summing this identity over the observations $X_{1},\dots,X_{n}$ gives (20.1). This completes the proof. ∎

We now use the lemma to show that the EM algorithm can only increase the observed-data log-likelihood.

Proposition 20.2.

Let $\theta_{0},\theta_{1},\theta_{2},\dots$ be generated by the EM algorithm from definition 19.2. Then

\ell(\theta_{k+1})\geq\ell(\theta_{k})\qquad\text{for all $k=0,1,2,\dots$.}

Proof.

We first show that $H(\theta\mskip 1.0mu|\mskip 1.0mu\theta_{k})\leq H(\theta_{k}\mskip 1.0mu|% \mskip 1.0mu\theta_{k})$ for all $\theta$ . Since $H$ is a sum over the observations, we only need to consider a single observation with observed value $x$ . Let $Y=g(Z\mskip 1.0mu|\mskip 1.0mux;\theta)/g(Z\mskip 1.0mu|\mskip 1.0mux;\theta_{% k})$ . This value is well defined and positive by our assumption on the supports. Since $-\log$ is convex, we can use Jensen’s inequality, lemma A.7, for the conditional distribution of $Z$ given $X=x$ under $\theta_{k}$ to get

\displaystyle\mathbb{E}_{\theta_{k}}\bigl{(}\log g(Z\mskip 1.0mu|\mskip 1.0mux% ;\theta)\!\mathrel{\big{|}}\!X=x\bigr{)}-\mathbb{E}_{\theta_{k}}\bigl{(}\log g% (Z\mskip 1.0mu|\mskip 1.0mux;\theta_{k})\!\mathrel{\big{|}}\!X=x\bigr{)}

\displaystyle\qquad=\mathbb{E}_{\theta_{k}}\bigl{(}\log Y\!\mathrel{\big{|}}\!% X=x\bigr{)}\leq\log\mathbb{E}_{\theta_{k}}\bigl{(}Y\!\mathrel{\big{|}}\!X=x% \bigr{)}

\displaystyle\qquad=\log\sum_{z}\frac{g(z\mskip 1.0mu|\mskip 1.0mux;\theta)}{g% (z\mskip 1.0mu|\mskip 1.0mux;\theta_{k})}\,g(z\mskip 1.0mu|\mskip 1.0mux;% \theta_{k})=\log\sum_{z}g(z\mskip 1.0mu|\mskip 1.0mux;\theta)=\log 1=0,

since $z\mapsto g(z\mskip 1.0mu|\mskip 1.0mux;\theta)$ is a probability distribution over $z$ (with sums replaced by integrals for a continuous latent variable). This is the same argument as in the proof of lemma 16.2.

Now we can use lemma 20.1 with $\theta^{\prime}=\theta_{k}$ at $\theta=\theta_{k+1}$ and at $\theta=\theta_{k}$ , and taking the difference we get

\ell(\theta_{k+1})-\ell(\theta_{k})=\bigl{(}Q(\theta_{k+1}\mskip 1.0mu|\mskip 1% .0mu\theta_{k})-Q(\theta_{k}\mskip 1.0mu|\mskip 1.0mu\theta_{k})\bigr{)}-\bigl% {(}H(\theta_{k+1}\mskip 1.0mu|\mskip 1.0mu\theta_{k})-H(\theta_{k}\mskip 1.0mu% |\mskip 1.0mu\theta_{k})\bigr{)}.

The first bracket is non-negative, since $\theta_{k+1}$ is the maximiser of $\theta\mapsto Q(\theta\mskip 1.0mu|\mskip 1.0mu\theta_{k})$ in the M step, and the second bracket is non-positive by the first step of the proof. Thus the difference is non-negative. This completes the proof. ∎

The statement of the proposition does not imply that EM finds the MLE: the sequence $\ell(\theta_{k})$ converges whenever $\ell$ is bounded above, but the iteration may stop at a local maximum or, in principle, at a saddle point. In general we can only say that the fixed points of the iteration are stationary points of $\ell$ .

Proposition 20.3.

Let $\Theta$ be open and $\ell$ as well as $\theta\mapsto Q(\theta\mskip 1.0mu|\mskip 1.0mu\theta^{\prime})$ differentiable for all $\theta^{\prime}\in\Theta$ . Then

\ell^{\prime}(\theta^{\prime})=\left.\frac{\partial}{\partial\theta}\,Q(\theta% \mskip 1.0mu|\mskip 1.0mu\theta^{\prime})\right|_{\theta=\theta^{\prime}}% \qquad\text{for all $\theta^{\prime}\in\Theta$.}

In particular, if $\theta_{k+1}=\theta_{k}$ for some $k$ , the point $\theta_{k}$ is a root of the likelihood equation $\ell^{\prime}(\theta)=0$ .

Proof.

From lemma 20.1 we know that the function $\theta\mapsto H(\theta\mskip 1.0mu|\mskip 1.0mu\theta^{\prime})=Q(\theta\mskip 1% .0mu|\mskip 1.0mu\theta^{\prime})-\ell(\theta)$ is differentiable. Furthermore, from the first step of the proof of proposition 20.2 we know that this function has its maximum at an interior point $\theta^{\prime}$ . Thus, the derivative at this point must be zero. Taking derivatives of the decomposition at $\theta=\theta^{\prime}$ gives the identity. If $\theta_{k+1}=\theta_{k}$ , then $\theta_{k}$ is an interior maximiser of $\theta\mapsto Q(\theta\mskip 1.0mu|\mskip 1.0mu\theta_{k})$ and the right-hand side equals zero at $\theta^{\prime}=\theta_{k}$ . Thus we have $\ell^{\prime}(\theta_{k})=0$ . This completes the proof. ∎

For a vector parameter the same argument applies, but now using gradients instead of derivatives.

20.2 Practical Matters

Three issues arise whenever EM is used, and the mixture shows all three.

The first issue is the promised failure of identifiability. The parameter values $(\pi,\mu_{1},\mu_{2})$ and $(1-\pi,\mu_{2},\mu_{1})$ give the same density $f(x;\theta)$ , and thus the model is not identifiable in the sense of definition 4.10. This is the difficulty foreshadowed after example 4.11. It is called label switching: the likelihood has two global maxima which are mirror images of each other. For the data of exercise 20.2, EM started from $(1/2,2,4)$ converges to $(0.4,0.5,6.0)$ , but started from $(1/2,4,2)$ it converges to $(0.6,6.0,0.5)$ . Either answer is fine on its own, but averaging different runs is not. The remedy of lecture 4 is to restrict the parameter space by a convention such as $\mu_{1}<\mu_{2}$ .

The second issue is local maxima. Proposition 20.2 guarantees ascent and nothing more, and a poor starting value can lead the iteration to a local maximum of $\ell$ without warning. The standard precaution is to run EM from several starting values and to keep the run with the largest observed-data log-likelihood, which we can always evaluate.

The third issue is when to stop. Since $\ell(\theta_{k})$ is non-decreasing, we stop when its increase falls below a small tolerance. Convergence is typically geometric near the fixed point, but can be slow.

Finally, EM produces an estimate but no standard error. The standard error is obtained afterwards from the observed information at the fixed point, as in section 17.3. Lecture 21 shows label switching, a starting value for which the iteration converges to a saddle point and the stopping rule in R.

Summary.

•

We have shown that $\ell(\theta_{k+1})\geq\ell(\theta_{k})$ for all $k$ . The proof uses $\ell=Q-H$ and Jensen’s inequality to show that the maximum of $\theta\mapsto H(\theta\mskip 1.0mu|\mskip 1.0mu\theta_{k})$ is attained at $\theta_{k}$ .
•

A fixed point of the EM iteration is a root of the likelihood equation.
•

Mixture parameters are only identifiable up to relabelling the components (label switching). Local maxima of the likelihood function can be avoided by running EM with different starting values and by comparing runs of the algorithm using the observed-data log-likelihood.

Exercise 20.1.

Suppose $f_{1}$ and $f_{2}$ are two known, distinct densities, and that $X_{1},\dots,X_{n}$ are i.i.d. with density

f(x;\pi)=\pi f_{1}(x)+(1-\pi)f_{2}(x),

where $\pi\in(0,1)$ is the only unknown parameter. Let $Z_{i}\in\{1,2\}$ be the component observation $i$ belongs to, as in example 19.1.

1.

Write down the observed-data log-likelihood $\ell(\pi)$ and the likelihood equation $\ell^{\prime}(\pi)=0$ .
2.

Write down the complete-data log-likelihood and show that the E step determines the responsibilities $\gamma_{i}(\pi_{k})=\pi_{k}f_{1}(x_{i})/\bigl{(}\pi_{k}f_{1}(x_{i})+(1-\pi_{k}% )f_{2}(x_{i})\bigr{)}$ and the M step determines the update $\pi_{k+1}=\frac{1}{n}\sum_{i}\gamma_{i}(\pi_{k})$ .
3.

Show that $\gamma_{i}(\pi)-\pi=\pi(1-\pi)\,\bigl{(}f_{1}(x_{i})-f_{2}(x_{i})\bigr{)}/f(x_% {i};\pi)$ and thus that $\frac{1}{n}\sum_{i}\gamma_{i}(\pi)-\pi=\pi(1-\pi)\,\ell^{\prime}(\pi)/n$ . Deduce that $\pi^{*}\in(0,1)$ is a fixed point of the EM iteration if and only if it solves the likelihood equation. This shows that for this model the converse of proposition 20.3 holds as well.

Exercise 20.2.

Consider the normal mixture of example 19.1 with $\sigma=1$ , the observations $x=(0,1,5,6,7)$ and the initial value $\theta_{0}=(1/2,2,4)$ .

1.

Show that the responsibilities are $\gamma_{i,0}=1/(1+e^{2x_{i}-6})$ , compute them to four decimal digits and use the updates (19.1) to find the first iterate $\theta_{1}$ .
2.

Compute the observed-data log-likelihood $\ell(\theta)=\sum_{i=1}^{5}\log\bigl{(}\pi\varphi_{1}(x_{i}-\mu_{1})+(1-\pi)% \varphi_{1}(x_{i}-\mu_{2})\bigr{)}$ at $\theta_{0}$ and at $\theta_{1}$ , and show that the likelihood has increased. Which of the five observations contributes most to the increase in likelihood? Why?