The EM Algorithm

The expectation-maximization algorithm for any model with unobserved data, beyond the mixtures where the site first uses it. The decomposition of the log-likelihood into an expected complete-data part and a conditional part, and the proof by Jensen's inequality that no iteration lowers the likelihood; the theorem that the algorithm's interior stopping points are stationary points of the likelihood, with a stationary point that is not a maximum and a boundary point where runs stall; the rate of convergence as the fraction of missing information, proved and checked on a two-component Poisson mixture of Cranfield word counts; and standard errors, which the algorithm does not supply. Worked problems on two coins, censored lifetimes and a zero-inflated stalling point.

In the Cranfield collection of 1,400 aerodynamics abstracts the word flutter occurs 282 times, but in only 56 documents. The 2-Poisson Model explains the clumping with a mixture. A fraction $\pi$ of documents are about flutter and use the word at a high Poisson rate $\lambda_E$, and the rest use it at a low rate $\lambda_N$. Which documents are which is not recorded. That article fits the three parameters by alternating two steps: guessing each document's class from the current parameters, and re-estimating the parameters from the guesses. It proves for this mixture that the likelihood never falls. Does the alternation work for every model with unobserved data, where does it stop, and how fast does it get there? It works whenever the model with the missing data filled in is easy to fit. It stops, in the interior of the parameter space, only at points where the likelihood has zero gradient, and those need not be maxima. And near a local maximum that is a fixed point, with nonzero curvature, the linear approximation of the algorithm shrinks the error at each step by a factor equal to the fraction of the information that is missing; the runs below show the error ratio settling there.

The EM algorithm, for expectation-maximization, is a method for computing a maximum likelihood estimate when part of the data that the model describes was not observed. Each iteration has two steps. The E step averages the log-likelihood of the complete data over the unobserved part, given what was observed and the current parameters. The M step maximizes that average. Dempster, Laird and Rubin (1977) presented it under that name, as "a broadly applicable algorithm for computing maximum likelihood estimates from incomplete data": "Since each iteration of the algorithm consists of an expectation step followed by a maximization step we call it the EM algorithm" (p. 1). They note that it "has been proposed many times in special circumstances" (p. 3), and their contribution was the general form and its theory.

First we set up incomplete data and the two steps in general. Then we prove that no iteration lowers the likelihood, by Jensen's inequality, and follow the proof's two terms through the first iterations on flutter. Next we show which points the algorithm can stop at, and exhibit a stopping point that is not a maximum. Then we separate what convergence is guaranteed from what is not, with thirty random starts. Finally we derive the rate of convergence and compute standard errors. The article assumes the likelihood function and maximum likelihood estimation, and uses the score and the information and the large-sample theory of the estimate.

Model-Based Clustering and the EM Algorithm is the site's home for EM applied to mixtures. It derives the E and M steps for Gaussian and Bernoulli mixtures from a lower bound, proves monotonicity in that setting, and shows the limit in which EM becomes k-means. This article does not repeat those derivations. It gives the general theory beneath them: models that are not mixtures, the characterization of stopping points, and the rate.

Incomplete data

Write $\mathbf{x}$ for everything observed and $\mathbf{z}$ for what the model describes but the data lack. The pair $(\mathbf{x}, \mathbf{z})$ is the complete data, with joint mass function or density $f(\mathbf{x}, \mathbf{z}; \theta)$. The parameter $\theta$ may be a vector. What can be computed from the observations is the likelihood of $\mathbf{x}$ alone, obtained by summing over every value the missing part could have taken:

$$L(\theta) = f(\mathbf{x};\theta) = \sum_{\mathbf{z}} f(\mathbf{x}, \mathbf{z};\theta), \qquad \ell(\theta) = \ln L(\theta).$$

For continuous $\mathbf{z}$ the sum is an integral; the proofs below are written with sums and hold with integrals in their place. The logarithm of a sum does not simplify, and that is the whole difficulty: $\ell$ is awkward to maximize even when the complete-data log-likelihood $\ln f(\mathbf{x}, \mathbf{z};\theta)$ would be easy.

The third object is the conditional distribution of the missing part given the observed part,

$$k(\mathbf{z} \mid \mathbf{x};\theta) = \frac{f(\mathbf{x}, \mathbf{z};\theta)}{f(\mathbf{x};\theta)},$$

which is what the model, at the parameter value $\theta$, believes about $\mathbf{z}$ after seeing $\mathbf{x}$. Taking logarithms of this definition gives the identity on which everything rests: for every $\mathbf{z}$ with positive conditional probability,

$$\ell(\theta) = \ln f(\mathbf{x}, \mathbf{z};\theta) - \ln k(\mathbf{z} \mid \mathbf{x};\theta). \qquad (1)$$

Throughout we assume that the set of pairs $(\mathbf{x}, \mathbf{z})$ with $f(\mathbf{x}, \mathbf{z};\theta) > 0$ is the same for every $\theta$ in the parameter space, so that every logarithm in (1) is finite wherever any is. This is the common-support condition of the earlier articles, applied to the complete data.

Three examples fix the idea.

  • Mixtures. For flutter, $\mathbf{x}$ is the 1,400 counts $k_d$ and $\mathbf{z}$ the 1,400 class labels $z_d$, with $z_d = 1$ for an elite document. The complete data would make the fit trivial: $\pi$ would be the share of elite documents and each rate the mean count in its class. The conditional distribution of $z_d$ is the posterior probability of eliteness, $r_d$.
  • Censored observations. Ten machines are run until they fail or until the study ends. For the machines still running at the end, the failure time is known only to exceed the length of the study. The missing data are those failure times, and their conditional distribution is that of a lifetime given that it exceeds a known value.
  • Latent variables. In probabilistic latent semantic analysis the missing data are the topic of each word occurrence, and in variational inference for LDA the conditional distribution is itself intractable and is replaced by an approximation.

The abstract of Dempster, Laird and Rubin (1977) lists the applications they sketch: "missing value situations, applications to grouped, censored or truncated data, finite mixture models, variance component estimation, hyperparameter estimation, iteratively reweighted least squares and factor analysis".

The two steps

Let $\theta'$ be the current value of the parameter. Define

$$Q(\theta;\theta') = E_{\theta'}\big[\ln f(\mathbf{x}, \mathbf{Z};\theta) \mid \mathbf{x}\big] = \sum_{\mathbf{z}} k(\mathbf{z} \mid \mathbf{x};\theta')\,\ln f(\mathbf{x}, \mathbf{z};\theta).$$

The first argument is the parameter at which the complete-data log-likelihood is evaluated. The second is the parameter that supplies the distribution of the missing data. In words, $Q(\theta;\theta')$ is the complete-data log-likelihood at $\theta$, averaged over what the model at $\theta'$ believes about the missing part.

Starting from some $\theta^{(0)}$, iteration $t$ consists of two steps.

  1. E step. Compute the function $Q(\,\cdot\,;\theta^{(t)})$, which in practice means computing the conditional expectations it involves.
  2. M step. Set $\theta^{(t+1)}$ to a value of $\theta$ that maximizes $Q(\theta;\theta^{(t)})$.

Write $\theta^{(t+1)} = M(\theta^{(t)})$, so that $M$ is the map applied at each iteration.

For the Poisson mixture, the complete-data log-likelihood is linear in the labels:

$$\ln f(\mathbf{x}, \mathbf{z};\theta) = \sum_d \Big[ z_d\big(\ln\pi - \lambda_E + k_d\ln\lambda_E\big) + (1 - z_d)\big(\ln(1-\pi) - \lambda_N + k_d\ln\lambda_N\big) \Big] - \sum_d \ln k_d! .$$

Averaging over the labels therefore only replaces each $z_d$ by its conditional mean, the posterior probability $r_d$ computed at $\theta'$. The E step computes the $r_d$, and the M step is the complete-data fit with fractional labels:

$$\pi = \frac1n\sum_d r_d, \qquad \lambda_E = \frac{\sum_d r_d k_d}{\sum_d r_d}, \qquad \lambda_N = \frac{\sum_d (1-r_d)k_d}{\sum_d (1 - r_d)}.$$

The 2-Poisson Model derives these formulas and checks the second derivatives. Its starting point is $\pi = 0.1$, $\lambda_E = 5\bar{k} = 1.0071$ and $\lambda_N = 0.3\,\bar{k} + 0.001 = 0.0614$, where $\bar{k} = 282/1{,}400$ is the mean count; the numbers below are computed from the unrounded values. From there the iteration settles at $\hat\pi = 0.0360$, $\hat\lambda_E = 5.485$, $\hat\lambda_N = 0.0044$, where the log-likelihood is −367.60.

Example (what the M step maximizes). A common summary is "EM maximizes the expected complete-data log-likelihood". The function maximized is a different one at every iteration, because its second argument changes. $Q$ is a device, and the quantity that the iterations improve is $\ell$. For flutter at the starting point, $Q(\theta^{(0)};\theta^{(0)}) = -893.67$ while $\ell(\theta^{(0)}) = -656.26$: the two are different numbers, and the next section shows what separates them.

Why the likelihood cannot fall

Here is the idea in plain words. Identity (1) holds for every value of the missing data, so it still holds after averaging over them, under any distribution. Average under the conditional distribution at the current parameter. The log-likelihood then splits into $Q$ minus a second term. The M step raises $Q$ by construction. The second term can only move in the helpful direction, because an average of logarithms of probabilities is largest when the probabilities are those of the averaging distribution itself.

The decomposition. Multiply (1) by $k(\mathbf{z} \mid \mathbf{x};\theta')$ and sum over $\mathbf{z}$. The left side does not involve $\mathbf{z}$ and the weights sum to 1, so for every $\theta$ and $\theta'$

$$\ell(\theta) = Q(\theta;\theta') - H(\theta;\theta'), \qquad H(\theta;\theta') = \sum_{\mathbf{z}} k(\mathbf{z} \mid \mathbf{x};\theta')\,\ln k(\mathbf{z} \mid \mathbf{x};\theta). \qquad (2)$$

Lemma (the conditional term). For every $\theta$ and $\theta'$, $H(\theta;\theta') \le H(\theta';\theta')$, with equality exactly when the conditional distributions $k(\,\cdot \mid \mathbf{x};\theta)$ and $k(\,\cdot \mid \mathbf{x};\theta')$ are the same.

Proof. Abbreviate $k = k(\mathbf{z} \mid \mathbf{x};\theta)$ and $k' = k(\mathbf{z} \mid \mathbf{x};\theta')$. The logarithm is concave, so by Jensen's inequality (Probability Inequalities, section "Jensen's inequality") the mean of a logarithm is at most the logarithm of the mean. Apply it to the ratio $k/k'$ under the distribution $k'$:

$$H(\theta;\theta') - H(\theta';\theta') = \sum_{\mathbf{z}} k'\,\ln\frac{k}{k'} \le \ln\sum_{\mathbf{z}} k'\cdot\frac{k}{k'} = \ln\sum_{\mathbf{z}} k = \ln 1 = 0.$$

The logarithm is strictly concave, so equality requires the ratio $k/k'$ to be constant over the values of $\mathbf{z}$. Both distributions sum to 1, so the constant is 1. $\square$

The difference $H(\theta';\theta') - H(\theta;\theta')$ is the Kullback–Leibler divergence from the conditional distribution at $\theta'$ to the one at $\theta$. The lemma is the nonnegativity of that divergence, which Cross-Entropy and Kullback–Leibler Divergence proves a second way.

Theorem 1 (monotonicity). Let $\theta^{\text{old}}$ be any parameter value and let $\theta^{\text{new}}$ satisfy $Q(\theta^{\text{new}};\theta^{\text{old}}) \ge Q(\theta^{\text{old}};\theta^{\text{old}})$. Then

$$\ell(\theta^{\text{new}}) - \ell(\theta^{\text{old}}) = \underbrace{Q(\theta^{\text{new}};\theta^{\text{old}}) - Q(\theta^{\text{old}};\theta^{\text{old}})}_{\ge\, 0} + \underbrace{H(\theta^{\text{old}};\theta^{\text{old}}) - H(\theta^{\text{new}};\theta^{\text{old}})}_{\ge\, 0} \;\ge\; 0.$$

In particular every EM iteration satisfies $\ell(\theta^{(t+1)}) \ge \ell(\theta^{(t)})$. Equality holds exactly when the step did not raise $Q$ and did not change the conditional distribution of the missing data.

Proof. Apply (2) twice with $\theta' = \theta^{\text{old}}$, once at $\theta = \theta^{\text{new}}$ and once at $\theta = \theta^{\text{old}}$, and subtract. The first bracket is nonnegative by hypothesis; the M step, which maximizes $Q(\,\cdot\,;\theta^{\text{old}})$, satisfies the hypothesis. The second bracket is nonnegative by the lemma. A sum of two nonnegative terms is zero exactly when both are, and the lemma says when the second is. $\square$

The theorem asks only that the step not lower $Q$. An M step that stops short of the maximum, for instance one that improves some of the parameters and leaves the others, keeps the guarantee. Dempster, Laird and Rubin (1977, Section 3) prove the theorem in this generality. They call an iterative algorithm whose map satisfies $Q(M(\theta);\theta) \ge Q(\theta;\theta)$ for every $\theta$ a generalized EM algorithm, or GEM algorithm, and their Theorem 1 states that the likelihood does not decrease under any GEM algorithm, with equality exactly when both brackets above are zero (p. 7). The proof is the one given here: the decomposition (2) is their equation (3.2), and the lemma, their Lemma 1, is "a well-known consequence of Jensen's inequality" (p. 6).

That article proves monotonicity from a lower bound $F(w, \Theta) \le L(\Theta)$ that holds for any weights $w$. The two arguments are the same inequality. With the weights taken to be a conditional distribution $k(\,\cdot \mid \mathbf{x};\theta')$, its bound is $Q(\theta;\theta') - H(\theta';\theta')$, and by (2) that equals $\ell(\theta) - [H(\theta';\theta') - H(\theta;\theta')]$: the log-likelihood minus a divergence that vanishes at $\theta = \theta'$.

The two terms on flutter. The script evaluates $Q$ and $H$ at each of the first iterations and confirms (2) to nine decimals. The table splits each rise of $\ell$ into its two parts.

Iteration $\ell$ before Gain in $Q$ Fall in $H$ Rise of $\ell$
1 −656.26 158.19 63.14 221.33
2 −434.93 48.06 12.87 60.93
3 −374.00 3.33 1.14 4.47
4 −369.53 0.86 0.59 1.45

In every row both parts are positive, as the theorem requires. Between 21% and 41% of each rise comes from the fall in $H$, a quantity the algorithm never computes. When the parameters move, the posterior probabilities of eliteness move with them, and that alone raises the likelihood. At the start, $Q = -893.67$ and $H = -237.41$, and their difference is the −656.26 of the first row.

Where the algorithm can stop

A point $\theta^*$ with $M(\theta^*) = \theta^*$ is a fixed point: the algorithm, once there, stays. The monotonicity theorem says nothing about what kind of point that is. The next theorem does.

Theorem 2 (the gradient identity). Let $\theta'$ be an interior point of the parameter space at which $\ell$, $Q(\,\cdot\,;\theta')$ and $H(\,\cdot\,;\theta')$ are differentiable. Then the gradient of $Q$ in its first argument, evaluated at $\theta = \theta'$, is the score of the observed data:

$$\nabla_\theta\, Q(\theta;\theta')\Big|_{\theta = \theta'} = \nabla\ell(\theta').$$

Proof. Differentiate (2) with respect to $\theta$: $\nabla\ell(\theta) = \nabla_\theta Q(\theta;\theta') - \nabla_\theta H(\theta;\theta')$. By the lemma, the function $\theta \mapsto H(\theta;\theta')$ has a maximum at $\theta = \theta'$. That point is interior and the function is differentiable there, so its gradient there is zero. $\square$

The vanishing of the gradient of $H$ is the first score identity of Fisher Information and the Cramér–Rao Bound, applied to the conditional distribution of the missing data. A score has mean zero under its own distribution.

Corollary (fixed points and stationary points). Under the conditions of Theorem 2:

  1. If $\theta^*$ is an interior fixed point of EM, then $\nabla\ell(\theta^*) = 0$: it is a stationary point of the likelihood.
  2. If $\nabla\ell(\theta^*) = 0$ and $Q(\,\cdot\,;\theta^*)$ is concave with a unique maximizer, then $\theta^*$ is a fixed point of EM.

Proof. (1) A fixed point maximizes $Q(\,\cdot\,;\theta^*)$ at the interior point $\theta^*$, so the gradient of $Q$ in its first argument vanishes there, and by Theorem 2 that gradient is $\nabla\ell(\theta^*)$. (2) By Theorem 2 the gradient of $Q(\,\cdot\,;\theta^*)$ vanishes at $\theta^*$. A concave differentiable function lies below its tangent plane at every point, so a point of zero gradient is a maximizer, and it is the M step's choice because the maximizer is unique. $\square$

For the Poisson mixture $Q(\,\cdot\,;\theta')$ is a sum of concave functions of $\pi$, of $\lambda_E$ and of $\lambda_N$ separately, with a unique maximizer when both classes have positive weight and positive weighted counts. So in the interior its fixed points are exactly the stationary points of the likelihood, including any that are not maxima.

A stopping point that is not a maximum

Give both classes the same rate, the overall mean count $\bar{k}$, with any weight $\pi$. Both classes then assign the same probability to every count, so every posterior probability $r_d$ equals $\pi$. The M step returns the weight $\frac1n\sum_d \pi = \pi$ and, for each class, the mean count of all documents, $\bar{k}$. Nothing moves: every such point is a fixed point, and by the corollary a stationary point of the likelihood. The model there is a single Poisson distribution, whose log-likelihood for flutter is −1,045.86, far below −367.60.

It is not a maximum when the counts vary more than a Poisson distribution allows. Split the two rates apart while holding the mixture's mean fixed: put $\lambda_E = \bar{k} + (1-\pi)\delta$ and $\lambda_N = \bar{k} - \pi\delta$, and let $p(k;\lambda)$ be the Poisson mass function, with $p'$ and $p''$ its derivatives in $\lambda$. The probability of a count $k$ is $P_\delta(k) = \pi\,p(k;\lambda_E) + (1-\pi)\,p(k;\lambda_N)$, and at $\delta = 0$

$$\frac{dP_\delta}{d\delta} = \pi(1-\pi)p' - (1-\pi)\pi p' = 0, \qquad \frac{d^2P_\delta}{d\delta^2} = \pi(1-\pi)^2p'' + (1-\pi)\pi^2p'' = \pi(1-\pi)\,p'' .$$

Because the first derivative vanishes, the second derivative of $\ln P_\delta$ at $\delta = 0$ is $P''_\delta/P_\delta = \pi(1-\pi)\,p''/p$. For the Poisson distribution $p'/p = k/\lambda - 1$, and differentiating once more, $p''/p = (k/\lambda - 1)^2 - k/\lambda^2 = [(k-\lambda)^2 - k]/\lambda^2$. Summing over the documents at $\lambda = \bar{k}$,

$$\frac{d^2\ell}{d\delta^2}\bigg|_{\delta = 0} = \frac{\pi(1-\pi)}{\bar{k}^2}\sum_d\big[(k_d - \bar{k})^2 - k_d\big] = \frac{\pi(1-\pi)\,n\,(v - \bar{k})}{\bar{k}^2},$$

where $v = \frac1n\sum_d (k_d - \bar{k})^2$ is the variance of the counts. The curvature along the split is positive exactly when the variance exceeds the mean, which is the overdispersion that Overdispersion in Count Data measures. For flutter the mean is 0.2014 and the variance 1.2951, so $v - \bar{k} = 1.0937$, and with $\pi = 0.1$ the curvature is 3,396.5. The likelihood rises in both directions along the split. The point has zero gradient and is not a local maximum.

EM started exactly there never leaves. Started one percent away, with $\lambda_E = 1.01\,\bar{k}$ and $\lambda_N = 0.99\,\bar{k}$, it does: the log-likelihood is −1,044.30 after one iteration and −370.66 after five, and it is within 0.01 of the maximum after 9. The stationary point is unstable, and a run reaches it only by starting on it. Probabilistic latent semantic analysis works the same trap for its model, a start with identical topics.

What convergence is and is not guaranteed

Guaranteed: the likelihood values converge when the likelihood is bounded. By Theorem 1 the sequence $\ell(\theta^{(t)})$ never decreases, and a nondecreasing sequence that is bounded above converges. For the Poisson mixture $\ell \le 0$, because each term is the logarithm of a probability. For Gaussian mixtures with a free variance in each component the likelihood is unbounded, and Model-Based Clustering and the EM Algorithm shows runs that follow it to infinity.

Not guaranteed by Theorem 1: anything about the parameters. The convergence of $\ell(\theta^{(t)})$ does not by itself imply that $\theta^{(t)}$ converges, nor that a limit is a stationary point, nor that a stationary point is a maximum. Dempster, Laird and Rubin (1977, Theorem 2, p. 7) claimed that, under two conditions, the parameters of a GEM sequence converge to a point. Wu (1983) showed that their proof contains an error, an incorrect use of the triangle inequality, so that the convergence asserted in their Theorems 2 and 3 is "cast in doubt", while the monotonicity of the likelihood and their rate of convergence (Theorems 1 and 4) "remain valid" (p. 95); he reports a GEM sequence published by R. A. Boyles as a counterexample to the claim (p. 99). Wu then studied the two questions again: whether the algorithm finds a local maximum or a stationary value of the likelihood (his Section 2.1), and whether the sequence of parameter estimates converges (Section 2.2). Under standing assumptions that include compact sets $\{\theta: \ell(\theta) \ge \ell(\theta^{(0)})\}$ and iterates in the interior of the parameter space, his Theorem 2 (p. 98) states that if $Q(\theta;\theta')$ is continuous in both arguments, then all limit points of an EM sequence are stationary points of the likelihood, and $\ell(\theta^{(t)})$ converges monotonically to the value at a stationary point. The continuity holds when the complete data come from a curved exponential family with a compact parameter space (p. 99). Convergence to a local maximum needs a further condition, which he calls hard to verify (Theorem 3, p. 98). Convergence of the parameters themselves is obtained, for example, when the stationary points with the limiting likelihood value are isolated and successive iterates come together (Theorems 4 to 6, pp. 99–100), and, as his Corollary 1 (p. 100), when the likelihood is unimodal with a single stationary point and the gradient of $Q$ in its first argument is continuous in both arguments: then any EM sequence converges to the unique maximizer. His Section 2.1 takes from the printed discussion of Dempster, Laird and Rubin's paper an example of G. D. Murray (p. 27 there), twelve observations from a bivariate normal distribution with some values missing, in which EM started with a correlation of zero converges to a saddle point of the likelihood (pp. 97 and 99).

Three limits of the guarantee are visible on the page's own example.

  • A stationary point need not be a maximum. The single-Poisson point above is one.
  • A maximum need not be the global one. For flutter we found only one interior maximum, but probabilistic latent semantic analysis and model-based clustering record runs ending at several different values on their examples.
  • On the boundary, a fixed point need not even be stationary. Part 1 of the corollary needs an interior point. The next experiment meets a boundary point where the gradient of the likelihood is not zero.

Thirty random starts

We ran EM on the flutter counts from 30 seeded random starts, with $\pi$ uniform on (0.05, 0.95) and each rate uniform on (0.05, 10), for 2,000 iterations each. The script asserts that the log-likelihood never fell in any iteration of any run. All 30 runs ended at the same point, the maximum found before (with the two classes in either order). In 28 runs the log-likelihood was within $10^{-6}$ of its maximum after a median of 8 iterations, and at most 21.

The other two runs, seeds 4 and 6, took 55 and 39 iterations, and for a stretch in the middle they looked finished. Both started with both rates far above the mean count. One class then took the documents with no occurrence, and its rate collapsed toward zero, to a lowest value of $2.3 \times 10^{-21}$ in the first run and $3.7 \times 10^{-15}$ in the second. At iteration 24 of the first run and iteration 18 of the second, no parameter was changing by more than $10^{-8}$, a common stopping rule. The log-likelihood stood at −372.89, which is 5.29 below the maximum.

The point where they paused is the best fit of a restricted model: one class that never uses the word, and one Poisson class with weight 0.0403 and mean 5.002. This is a zero-inflated Poisson distribution, the mixture with $\lambda_N = 0$, and −372.89 is its maximized log-likelihood. With $\lambda_N$ exactly zero the algorithm cannot move off it. A document with any occurrence has probability zero under the empty class, so its posterior probability for the other class is 1, and the M step returns $\lambda_N = 0$ again. Yet the point is not a stationary point of the full model. The derivative of $\ell$ with respect to $\lambda_N$ there is 3,615, not zero. It is a fixed point on the boundary of the parameter space, outside the reach of Theorem 2.

A run that comes near that point, with $\lambda_N$ tiny but positive, does escape, and the rate of escape can be computed. Near the point each iteration multiplies $\lambda_N$ by 3.69 (Problem 3 derives the multiplier). From values as small as those reached here, that is a large relative change and an invisible absolute one for many iterations: at that factor it takes about 22 iterations to climb from $2.3 \times 10^{-21}$ to $10^{-8}$, and about 11 from $3.7 \times 10^{-15}$. That is the stretch the stopping rule mistook for convergence.

Example (a small change is not convergence). "The parameters stopped changing, so the algorithm has converged" is the usual stopping rule and the usual misreading. For seeds 4 and 6 the parameters changed by less than $10^{-8}$ at a point 5.29 log-likelihood units below the maximum, where the gradient of the likelihood was in the thousands. The algorithm had not converged; it was moving slowly. Checking the gradient of $\ell$ at the stopping point, or running from several starts and comparing, exposes the stall. So does knowing the rate at which EM approaches a genuine limit, the subject of the next section.

How fast: the fraction of missing information

Near a fixed point $\theta^*$, a differentiable map behaves like its linear approximation: $M(\theta) - \theta^* \approx DM(\theta^*)\,(\theta - \theta^*)$, where $DM$ is the matrix of first derivatives of $M$ (for one parameter, the number $M'(\theta^*)$). Each iteration multiplies the error by that matrix. The theorem identifies it.

Two matrices are needed. The observed information is $J_{\text{obs}} = -\nabla^2\ell(\theta^*)$, minus the matrix of second derivatives of the log-likelihood. The complete information is $J_{\text{com}} = -\nabla^2_\theta Q(\theta;\theta^*)$ at $\theta = \theta^*$: the curvature the log-likelihood would be expected to have if the missing data were supplied.

Here is the idea. The M step solves the complete-data likelihood equation, with the missing data replaced by their expectations under the current parameter. How far the solution moves when the current parameter moves depends on two things. One is how sensitive those expectations are to the parameter, which is information the missing data would have carried. The other is how stiff the complete-data problem is. Their ratio is the share of the complete information that is missing.

Theorem 3 (rate of convergence). Let $\theta^*$ be an interior fixed point of EM. Suppose $Q(\theta;\theta')$ is twice continuously differentiable in both arguments near $(\theta^*, \theta^*)$, that $M$ is differentiable at $\theta^*$, and that $J_{\text{com}}$ is invertible. Then

$$DM(\theta^*) = \mathbf{I} - J_{\text{com}}^{-1}J_{\text{obs}} = J_{\text{com}}^{-1}J_{\text{mis}}, \qquad J_{\text{mis}} = J_{\text{com}} - J_{\text{obs}},$$

where $\mathbf{I}$ is the identity matrix. For one parameter, $M'(\theta^*) = 1 - J_{\text{obs}}/J_{\text{com}}$.

Proof. Write $\nabla_1 Q$ for the gradient of $Q$ in its first argument, $\nabla_{11}Q$ for its matrix of second derivatives in the first argument, and $\nabla_{12}Q$ for the matrix of mixed second derivatives, once in each argument. There are three steps.

Step 1. For $\theta'$ near $\theta^*$ the M step's value $M(\theta')$ is an interior maximizer of $Q(\,\cdot\,;\theta')$, so $\nabla_1 Q(M(\theta');\theta') = 0$. Differentiate this identity with respect to $\theta'$ at $\theta' = \theta^*$, by the chain rule, using $M(\theta^*) = \theta^*$:

$$\nabla_{11}Q(\theta^*;\theta^*)\,DM(\theta^*) + \nabla_{12}Q(\theta^*;\theta^*) = 0.$$

Step 2. By Theorem 2, $\nabla\ell(\theta) = \nabla_1 Q(\theta;\theta)$ for every $\theta$ near $\theta^*$. On the right $\theta$ appears in both arguments, so differentiating gives

$$\nabla^2\ell(\theta) = \nabla_{11}Q(\theta;\theta) + \nabla_{12}Q(\theta;\theta).$$

Step 3. At $\theta = \theta^*$, step 2 reads $-J_{\text{obs}} = -J_{\text{com}} + \nabla_{12}Q$, so $\nabla_{12}Q = J_{\text{com}} - J_{\text{obs}} = J_{\text{mis}}$. Step 1 reads $-J_{\text{com}}\,DM + J_{\text{mis}} = 0$. Multiplying by $J_{\text{com}}^{-1}$ gives $DM = J_{\text{com}}^{-1}J_{\text{mis}}$. $\square$

The matrix $J_{\text{mis}}$ is the missing information. Differentiating (2) twice in $\theta$ at $\theta = \theta' = \theta^*$ shows that it is $-\nabla^2_\theta H(\theta;\theta^*)$ at $\theta^*$, minus the curvature of $H$ at its maximum, so it is positive semidefinite. In one dimension the theorem then says $0 \le M'(\theta^*) = J_{\text{mis}}/J_{\text{com}}$: the rate is the fraction of missing information. If the missing data carry little information about the parameter, the fraction is near 0 and EM converges in a few steps. If nearly all the information is in the missing data, the fraction is near 1 and EM crawls. Dempster, Laird and Rubin (1977, Theorem 4, p. 9) give the same matrix, in their notation $DM(\phi^*) = D^{20}H(\phi^* \mid \phi^*)\,[D^{20}Q(\phi^* \mid \phi^*)]^{-1}$ with the parameters written as row vectors, and conclude that "if the information loss due to incompleteness is small, then the algorithm converges rapidly" (p. 10).

For several parameters the eigenvalues of $DM$ play the role of the rate. Suppose $J_{\text{com}}$ is positive definite, as it is when $\theta^*$ is a strict maximizer of $Q$ with nonzero curvature. Then $DM = J_{\text{com}}^{-1}J_{\text{mis}}$ has the same eigenvalues as the symmetric matrix $J_{\text{com}}^{-1/2}J_{\text{mis}}J_{\text{com}}^{-1/2}$, because the two are related by the change of basis $J_{\text{com}}^{1/2}$. Those eigenvalues are real and nonnegative. They are all below 1 exactly when $\mathbf{I} - J_{\text{com}}^{-1/2}J_{\text{mis}}J_{\text{com}}^{-1/2} = J_{\text{com}}^{-1/2}J_{\text{obs}}J_{\text{com}}^{-1/2}$ is positive definite, that is, when $J_{\text{obs}}$ is positive definite. That makes $\theta^*$ a strict local maximum of the likelihood. The converse fails: a strict local maximum can have zero curvature in some direction, as $-t^4$ does at 0, and then $J_{\text{obs}}$ is singular and an eigenvalue of $DM$ equals 1. When $J_{\text{obs}}$ is positive definite, the linear approximation multiplies the error, at each iteration, by a matrix whose largest eigenvalue $\rho$ is below 1. An error that shrinks by a constant factor per iteration is called linear convergence: the number of correct digits grows by a fixed amount per iteration. Two things are not proved here. One is that a given local maximum is a fixed point, which part 2 of the corollary gives when $Q(\,\cdot\,;\theta^*)$ is concave with a unique maximizer. The other is that the iterates of the map itself, and not only of its linear approximation, converge from nearby starts with error ratio tending to $\rho$. In the runs below the ratio of successive errors does settle at $\rho$.

Example (censored lifetimes, where the rate is exact). Lifetimes are exponential with mean $\theta$. Of $n$ machines, $r$ fail at observed times $t_1, \ldots, t_r$, and the other $n - r$ are still running when the study ends at time $c$. With all lifetimes $T_i$ known, the log-likelihood would be $-n\ln\theta - \sum_i T_i/\theta$, which is linear in the lifetimes. So the E step needs only the expected lifetime of a machine known to have survived to $c$. The exponential distribution has no memory: $P(T > c + s \mid T > c) = e^{-(c+s)/\theta}/e^{-c/\theta} = e^{-s/\theta}$, so the remaining life is again exponential with mean $\theta$, and $E_{\theta'}[T \mid T > c] = c + \theta'$. Hence

$$Q(\theta;\theta') = -n\ln\theta - \frac{\sum_{i \le r} t_i + (n-r)(c + \theta')}{\theta}, \qquad M(\theta') = \frac{\sum_{i\le r} t_i + (n-r)(c+\theta')}{n},$$

the M step being the complete-data estimate, a mean of $n$ lifetimes. The map is linear in $\theta'$ with slope $(n-r)/n$. Its fixed point solves $n\theta = \sum t_i + (n-r)c + (n-r)\theta$, so

$$\theta^* = \frac{\sum_{i \le r} t_i + (n-r)\,c}{r},$$

the total running time divided by the number of failures. That is the maximum likelihood estimate: the observed likelihood is $\prod_{i \le r}\theta^{-1}e^{-t_i/\theta}$ times $e^{-c/\theta}$ for each survivor, so $\ell(\theta) = -r\ln\theta - r\theta^*/\theta$, with $\ell'(\theta) = -r/\theta + r\theta^*/\theta^2$ vanishing at $\theta^*$. Every iteration multiplies the error by exactly $(n-r)/n$, the share of machines censored. Theorem 3 agrees: $J_{\text{obs}} = -\ell''(\theta^*) = r/\theta^{*2}$, $J_{\text{com}} = n/\theta^{*2}$, and $1 - J_{\text{obs}}/J_{\text{com}} = (n - r)/n$. Each machine's complete lifetime would have carried information $1/\theta^{*2}$, and the observed data carry that amount for each failure only, so the fraction of missing information is the fraction censored. Problem 2 runs the numbers.

The rate on the Cranfield counts. For the Poisson mixture $J_{\text{com}}$ is diagonal, with entries $\sum_d r_d/\pi^2 + \sum_d(1-r_d)/(1-\pi)^2$, $\sum_d r_dk_d/\lambda_E^2$ and $\sum_d(1-r_d)k_d/\lambda_N^2$, and $J_{\text{obs}}$ comes from differentiating the mixture log-likelihood twice. The script computes both at the fitted parameters, checks $\mathbf{I} - J_{\text{com}}^{-1}J_{\text{obs}}$ against a numerical derivative of the EM map, and compares the largest eigenvalue with the ratio of successive errors late in a run.

Term Fitted $\pi$, $\lambda_E$, $\lambda_N$ Eigenvalues of $DM$ Observed error ratio Iterations per decimal digit Iterations until no parameter changes by $10^{-8}$
flutter 0.0360, 5.485, 0.0044 0.269, 0.018, 0 0.269 1.8 18
boundary 0.240, 3.71, 0.144 0.651, 0.119, 0 0.651 5.4 42

The observed ratio matches the largest eigenvalue to three decimals for both terms. Flutter converges fast because its classes barely overlap: a document with rate 5.485 and one with rate 0.0044 are rarely confused, so the labels are nearly known and little information is missing. For boundary, a quarter of the collection is elite and the low rate is 0.144, so documents with one or two occurrences are ambiguous. Nearly two thirds of the information in the slowest direction is missing. The number of iterations per decimal digit is $\ln 10/(-\ln\rho)$ for a rate $\rho$.

The zero eigenvalue has a reason. Every M step makes the mixture's mean, $\pi\lambda_E + (1-\pi)\lambda_N$, equal to the mean count of the data, whatever the posteriors were (The 2-Poisson Model, Problem 4). So the map $M$ sends every point onto the surface where that function equals $\bar{k}$, and a change of the input cannot change the function's value at the output. One combination of the errors is removed completely in a single step.

The rate also depends on what is unknown. Hold the two rates for boundary at their fitted values and let only $\pi$ be estimated. Then $J_{\text{obs}} = 6{,}413$ and $J_{\text{com}} = n/(\pi(1-\pi)) = 7{,}675$, and the rate is $1 - 6{,}413/7{,}675 = 0.164$, against 0.651 with all three parameters free. From $\pi = 0.6$ the one-parameter iteration gives 0.305, then 0.251, on its way to 0.240.

Left: the log-likelihood of the elite fraction π for boundary, with the two rates held at their fitted values (solid), and the functions that two successive M steps maximize, shifted by a constant so that each touches the log-likelihood at the current value (dashed, from π = 0.6, then from π = 0.305). Notice that each dashed curve lies below the solid one everywhere and touches it at its starting value, so climbing to the top of the dashed curve must raise the solid one. Right: the distance from the fitted parameters at each iteration, on a logarithmic scale, for flutter and boundary with all three parameters free. Notice that each settles into a straight line, whose slope is the logarithm of the largest eigenvalue: 0.269 and 0.651.
Left: the log-likelihood of the elite fraction π for boundary, with the two rates held at their fitted values (solid), and the functions that two successive M steps maximize, shifted by a constant so that each touches the log-likelihood at the current value (dashed, from π = 0.6, then from π = 0.305). Notice that each dashed curve lies below the solid one everywhere and touches it at its starting value, so climbing to the top of the dashed curve must raise the solid one. Right: the distance from the fitted parameters at each iteration, on a logarithmic scale, for flutter and boundary with all three parameters free. Notice that each settles into a straight line, whose slope is the logarithm of the largest eigenvalue: 0.269 and 0.651.

Standard errors

EM delivers an estimate and nothing else. In particular the curvature it works with, $J_{\text{com}}$, is the information the complete data would have had, and using it for standard errors would understate them. The large-sample theory of Asymptotics of the Maximum Likelihood Estimator, in its version for several parameters, takes standard errors from the inverse of the observed information $J_{\text{obs}}$ at the estimate.

For flutter the square roots of the diagonal of $J_{\text{obs}}^{-1}$ are 0.0051 for $\pi$, 0.350 for $\lambda_E$ and 0.0020 for $\lambda_N$. The Wald interval for the elite fraction is $0.0360 \pm 1.96 \times 0.0051$, or (0.0260, 0.0459). In documents, the estimate is 50.3 of the 1,400, with an interval of 36 to 64.

How much did not knowing the labels cost? Had the classes been observed, the estimate of $\pi$ would be a sample proportion with standard error $\sqrt{\pi(1-\pi)/n}$, which is 0.0050 at the fitted value. The ratio of that variance to the actual one is 0.968 for flutter. The counts identify the elite documents so well that hiding the labels loses about 3% of the information about $\pi$. For boundary the two standard errors are 0.0114 and 0.0138, a ratio of variances of 0.686. The same quantity that slows the algorithm, the missing information, widens the interval.

Two cautions apply to these intervals. The theory behind them assumes the model is correct and the true parameter is in the interior, with the two classes distinct. The 2-Poisson model fits flutter closely and boundary only roughly, as The 2-Poisson Model shows. The asymptotics article gives an example of what a wrong model does to a standard error. And the statement for several parameters is cited there, not proved.

Here $J_{\text{obs}}$ was computed by differentiating the mixture likelihood directly, which is feasible for a three-parameter model. Louis (1982) gives a method for obtaining the observed information matrix within the EM framework. According to its abstract it requires only a gradient or a second-derivative matrix of the complete-data log-likelihood, not those of the incomplete-data likelihood. We read the abstract only and did not use the method.

What is proved, what is cited, what the experiment shows

Proved on this page:

  • the decomposition (2), and the lemma on the conditional term, from Jensen's inequality;
  • monotonicity for any step that does not lower $Q$ (Theorem 1);
  • the gradient identity and the correspondence between interior fixed points and stationary points (Theorem 2 and its corollary);
  • the instability condition for the single-Poisson point;
  • the rate formula (Theorem 3) under its differentiability assumptions, with the eigenvalue bounds;
  • the exact rate for censored exponential lifetimes.

The proofs are written for discrete missing data, and with integrals in place of sums they are the same. The interchange of differentiation and summation is assumed where a derivative of $Q$ or $H$ is taken.

Used from other pages: Jensen's inequality (Probability Inequalities); the M step of the Poisson mixture (The 2-Poisson Model); the several-parameter large-sample theory (Asymptotics of the Maximum Likelihood Estimator, where it is cited).

Cited: the origin and scope of the algorithm, and the published forms of this page's Theorems 1 and 3, their Theorems 1 and 4 (Dempster, Laird and Rubin, 1977); the convergence results of Wu (1983), stated and not proved here; the method of Louis (1982), of which we read the abstract only and attribute to it only what the abstract states.

Observed in the experiment: on the flutter counts, 30 random starts all reached the same maximum. Two of them did so after a stall near a boundary point that a common stopping rule would have accepted. The observed rates of convergence for flutter and boundary matched the largest eigenvalue of the theorem's matrix. Local convergence at that rate is observed here, not proved: Theorem 3 identifies the linear approximation at a fixed point. These are results for two terms of one collection. Every number is produced by tools/experiments/statistics/em-algorithm.py.

Worked problems

These problems are posed for this article on small exact cases and on the Cranfield counts; the unit has no course assignments. Every number is recomputed by the article's script, the first two problems in exact fractions.

Problem 1 (two coins). Each of 10 tosses is made with coin A, which shows heads with probability 3/4, or coin B, which shows heads with probability 1/4. Coin A is chosen with unknown probability $\pi$, independently for each toss, and the choice is not recorded. Six tosses show heads.

  • (a) Write the E and M steps and run two iterations from $\pi = 1/2$.
  • (b) Find the maximum likelihood estimate directly, and verify Theorem 2.
  • (c) Find the rate of convergence from Theorem 3 and compare it with the iterations.
  • (d) Repeat for nine heads, and say what is different.

Solution. (a) The missing data are the coins. By Bayes' rule the posterior probability of coin A is

$$r_H = \frac{\frac34\pi}{\frac34\pi + \frac14(1-\pi)} = \frac{3\pi}{1 + 2\pi} \text{ after heads}, \qquad r_T = \frac{\frac14\pi}{\frac14\pi + \frac34(1-\pi)} = \frac{\pi}{3 - 2\pi} \text{ after tails}.$$

With the coins known, the estimate of $\pi$ would be the share of tosses made with coin A, so the M step is the mean posterior: with $h$ heads in $n$ tosses,

$$M(\pi) = \frac{h\,r_H + (n-h)\,r_T}{n}.$$

At $\pi = 1/2$: $r_H = 3/4$ and $r_T = 1/4$, so $M = (6 \times \tfrac34 + 4 \times \tfrac14)/10 = 11/20 = 0.55$. At $\pi = 11/20$: $r_H = 11/14$ and $r_T = 11/38$, so $M = (6 \times \tfrac{11}{14} + 4 \times \tfrac{11}{38})/10 = 781/1330 = 0.5872$.

(b) A toss shows heads with probability $\frac34\pi + \frac14(1-\pi) = \frac14 + \frac12\pi$, so $\ell(\pi) = h\ln(\frac14 + \frac12\pi) + (n-h)\ln(\frac34 - \frac12\pi)$ and

$$\ell'(\pi) = \frac{2h}{1 + 2\pi} - \frac{2(n-h)}{3 - 2\pi}.$$

For $h = 6$, $n = 10$ this vanishes when $12(3 - 2\pi) = 8(1 + 2\pi)$, that is at $\hat\pi = 7/10$, where the model's probability of heads is 0.6, the observed share. For Theorem 2, the complete-data log-likelihood is $\sum_i [z_i\ln\pi + (1-z_i)\ln(1-\pi)]$ plus terms without $\pi$, so $Q(\pi;\pi')$ has derivative $\sum_i r_i'/\pi - \sum_i (1 - r_i')/(1-\pi)$ in $\pi$, with the posteriors $r_i'$ computed at $\pi'$. At $\pi' = \pi$, using $1 - r_H = (1-\pi)/(1+2\pi)$ and $1 - r_T = 3(1-\pi)/(3-2\pi)$,

$$\frac{h}{\pi}\cdot\frac{3\pi}{1+2\pi} + \frac{n-h}{\pi}\cdot\frac{\pi}{3-2\pi} - \frac{h}{1-\pi}\cdot\frac{1-\pi}{1+2\pi} - \frac{n-h}{1-\pi}\cdot\frac{3(1-\pi)}{3-2\pi} = \frac{2h}{1+2\pi} - \frac{2(n-h)}{3-2\pi},$$

which is $\ell'(\pi)$, as the theorem says. At $\pi = 7/10$ the posteriors are $7/8$ and $7/16$ and $M = (6 \times \tfrac78 + 4 \times \tfrac{7}{16})/10 = 7/10$: the stationary point is the fixed point.

(c) $J_{\text{obs}} = -\ell''(\hat\pi) = 4h/(1+2\hat\pi)^2 + 4(n-h)/(3-2\hat\pi)^2 = 24/5.76 + 16/2.56 = 125/12$. The complete data are 10 indicators with success probability $\pi$, so $J_{\text{com}} = n/(\hat\pi(1-\hat\pi)) = 10/0.21 = 1000/21$. The rate is

$$1 - \frac{125/12}{1000/21} = 1 - \frac{7}{32} = \frac{25}{32} = 0.7813 .$$

The errors of the iterates 0.5, 0.55 and 0.5872 are 0.2, 0.15 and 0.1128, with ratios 0.750 and 0.752, rising toward 0.7813 as the iterates approach 0.7. The convergence is slow because one toss says little about which coin made it: only $7/32$ of the complete information about $\pi$ is in the observed tosses.

(d) With $h = 9$, $\ell'(\pi) = 18/(1+2\pi) - 2/(3-2\pi)$, which is positive on all of $[0, 1]$: it decreases in $\pi$, and at $\pi = 1$ it is $6 - 2 = 4$. The likelihood increases up to the end of the parameter space, so the maximum likelihood estimate is $\hat\pi = 1$, on the boundary, where the likelihood equation does not hold. EM still goes there. $\pi = 1$ is a fixed point, since both posteriors are then 1, and from $\pi = 1/2$ the iterates increase to it. Here is the proof. For $0 < \pi < 1$ the function $Q(\,\cdot\,;\pi)$ is strictly concave, being a positive combination of $\ln$ of its argument and $\ln$ of one minus its argument, and by Theorem 2 its derivative at the point $\pi$ is $\ell'(\pi) > 0$. A strictly concave function that is still increasing at $\pi$ has its maximizer above $\pi$, so $M(\pi) > \pi$. The iterates therefore increase, and they are bounded by 1, so they converge to some limit $L$ with $1/2 < L \le 1$. The map $M$ is continuous on $[0, 1]$, so $L = M(L)$: the limit is a fixed point. If $L$ were below 1 it would be an interior fixed point, hence a stationary point of $\ell$ by the corollary, and $\ell'$ has no zero. So $L = 1$. Near the limit the error shrinks at the rate $M'(1) = [9 \times 3/(1+2)^2 + 1 \times 3/(3-2)^2]/10 = 3/5$, from the derivative $M'(\pi) = [3h/(1+2\pi)^2 + 3(n-h)/(3-2\pi)^2]/n$. So EM can converge to a maximum that is not a stationary point. Theorem 2 and its corollary are statements about interior points, and at a boundary the fixed-point property and the gradient are unrelated. Here the boundary fixed point is the right answer; at the zero-inflated point of the flutter runs it was not.

Problem 2 (censored lifetimes). Ten machines are observed for 5 thousand hours. Seven fail, at times totaling 21 thousand hours, and three are still running at the end. Assuming exponential lifetimes with mean $\theta$, run EM from $\theta = 3$, find its limit and rate, and give a standard error.

Solution. By the example in the body, $M(\theta') = [21 + 3(5 + \theta')]/10 = 3.6 + 0.3\,\theta'$. From $\theta = 3$ the iterates are $4.5$, $4.95$ and $5.085$. The fixed point is $\theta^* = (21 + 3 \times 5)/7 = 36/7 = 5.143$ thousand hours, the total running time over the number of failures. The errors are 2.1429, then 0.6429, then 0.1929: each is exactly 0.3 times the one before, the fraction of machines censored. For the standard error, $J_{\text{obs}} = r/\theta^{*2} = 7/\theta^{*2}$, so the standard error is $\theta^*/\sqrt{7} = 1.944$ thousand hours. Using $J_{\text{com}} = 10/\theta^{*2}$ instead would give $\theta^*/\sqrt{10}$, the precision of ten complete lifetimes, which the data do not have.

Problem 3 (the stall near the zero-inflated point). For the 2-Poisson mixture, let $m_0$ and $m_1$ be the numbers of documents with no occurrence and with one. Suppose the current parameters are $\pi$ and $\lambda_E$ for the elite class and a very small rate $\lambda_N$ for the other, with $\pi$ and $\lambda_E$ at the zero-inflated fit.

  • (a) Show that one EM iteration multiplies $\lambda_N$ by approximately $\kappa = m_1/(n\,\pi\lambda_Ee^{-\lambda_E})$. This is the observed number of documents with one occurrence over the number the elite class alone predicts.
  • (b) Evaluate $\kappa$ for flutter and explain the stall of seeds 4 and 6.

Solution. (a) The M step sets $\lambda_N' = \sum_d (1-r_d)k_d/\sum_d(1-r_d)$, where $1 - r_d$ is the posterior probability of the non-elite class. For a document with count $k \ge 1$, the non-elite class gives probability $(1-\pi)e^{-\lambda_N}\lambda_N^k/k!$, which for small $\lambda_N$ is approximately $(1-\pi)\lambda_N$ when $k = 1$ and of order $\lambda_N^2$ or smaller when $k \ge 2$. The elite class gives a document with one occurrence the probability $\pi\lambda_Ee^{-\lambda_E}$, which does not shrink with $\lambda_N$. So to first order in $\lambda_N$ the numerator is

$$\sum_d (1-r_d)k_d \approx m_1\,\frac{(1-\pi)\lambda_N}{\pi\lambda_Ee^{-\lambda_E}} .$$

In the denominator the documents with no occurrence dominate. Each has $1 - r_d = (1-\pi)/[(1-\pi) + \pi e^{-\lambda_E}]$ in the limit $\lambda_N \to 0$, so $\sum_d(1-r_d) \approx m_0(1-\pi)/[(1-\pi) + \pi e^{-\lambda_E}]$. At the zero-inflated fit the model reproduces the share of empty documents exactly, $(1-\pi) + \pi e^{-\lambda_E} = m_0/n$; this is the likelihood equation for the weight in that model, and the script confirms it. The denominator is therefore approximately $n(1-\pi)$, and

$$\frac{\lambda_N'}{\lambda_N} \approx \frac{m_1(1-\pi)}{\pi\lambda_Ee^{-\lambda_E}}\cdot\frac{1}{n(1-\pi)} = \frac{m_1}{n\,\pi\lambda_Ee^{-\lambda_E}} = \kappa .$$

(b) For flutter, $m_1 = 7$, and the zero-inflated fit has $\pi = 0.0403$ and $\lambda_E = 5.002$, which predict $1{,}400 \times 0.0403 \times 5.002 \times e^{-5.002} = 1.90$ documents with one occurrence. So $\kappa = 7/1.90 = 3.69$; the script confirms it by applying the EM map at $\lambda_N = 10^{-12}$. Since $\kappa > 1$, a tiny $\lambda_N$ grows: the zero-inflated point repels. It repels because the restricted model predicts too few documents with a single occurrence, and a second class with a small positive rate supplies them. But the two runs had driven $\lambda_N$ down to $2.3 \times 10^{-21}$ and $3.7 \times 10^{-15}$. Growth by a factor of 3.69 per iteration from $\lambda$ to $10^{-8}$ takes $\ln(10^{-8}/\lambda)/\ln 3.69$ iterations, about 22 and about 11 for those two values. Through all of them the change in every parameter is below $10^{-8}$ and the log-likelihood sits at −372.89. Had $\kappa$ been below 1, with fewer one-occurrence documents than the elite class predicts, the point would have attracted. It would then be the maximum likelihood fit on the boundary, as $\pi = 1$ was in Problem 1(d).

Summary

  • Incomplete data: observed $\mathbf{x}$, missing $\mathbf{z}$, observed log-likelihood $\ell(\theta) = \ln\sum_{\mathbf{z}} f(\mathbf{x},\mathbf{z};\theta)$. The E step forms $Q(\theta;\theta') = E_{\theta'}[\ln f(\mathbf{x},\mathbf{Z};\theta) \mid \mathbf{x}]$ and the M step maximizes it in $\theta$.
  • $\ell(\theta) = Q(\theta;\theta') - H(\theta;\theta')$, and $H(\theta;\theta') \le H(\theta';\theta')$ by Jensen's inequality. So any step that does not lower $Q$ does not lower $\ell$ (Theorem 1).
  • $\nabla_\theta Q(\theta;\theta')$ at $\theta = \theta'$ equals $\nabla\ell(\theta')$ (Theorem 2). Interior fixed points of EM are stationary points of $\ell$, and when $Q$ is concave with a unique maximizer every stationary point is a fixed point, maxima or not.
  • Guaranteed: $\ell(\theta^{(t)})$ is nondecreasing and converges if $\ell$ is bounded. Not guaranteed: convergence of $\theta^{(t)}$, a maximum, the global maximum. On the boundary a fixed point need not be stationary.
  • Rate: $DM(\theta^*) = \mathbf{I} - J_{\text{com}}^{-1}J_{\text{obs}} = J_{\text{com}}^{-1}J_{\text{mis}}$, the fraction of missing information (Theorem 3). It is $(n-r)/n$ for censored exponential lifetimes, 0.269 for flutter and 0.651 for boundary.
  • Standard errors come from $J_{\text{obs}}^{-1}$, not from the algorithm: 0.0051 for the elite fraction of flutter.
  • A small change between iterations is not convergence: two of 30 random starts stalled 5.29 log-likelihood units below the maximum.

What we have learned

The EM algorithm replaces one hard maximization by a sequence of easy ones. Its guarantee is exactly Theorem 1: because the log-likelihood is $Q$ minus a term that can only fall when the parameters move, raising $Q$ raises the likelihood. Everything else has to be earned case by case. Interior stopping points are stationary points of the likelihood, and the single-Poisson fit of an overdispersed term is one that is not a maximum. Boundary stopping points need not be stationary at all. The speed is set by how much information the unobserved data would have carried. That is little for flutter, whose classes are far apart, more for boundary, and exactly the censored fraction for exponential lifetimes. The same missing information is what the standard errors pay for.

This article closes the unit on likelihood and estimation. The mixture models that EM fits return in Bayesian Inference, where the unobserved labels and the parameters are both given distributions. There the lower bound of this article becomes the objective of variational inference.

References

  • Dempster, A. P., Laird, N. M., and Rubin, D. B. (1977). Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society, Series B, 39(1), 1–38. The paper occupies pages 1 to 22; the printed discussion, with the authors' reply, runs from page 22 to 38. record · 4 pages
  • Louis, T. A. (1982). Finding the observed information matrix when using the EM algorithm. Journal of the Royal Statistical Society, Series B, 44(2), 226–233. record
  • Wu, C. F. J. (1983). On the convergence properties of the EM algorithm. The Annals of Statistics, 11(1), 95–103. record · 2 pages