Past exam of the mathematics course of the University of Cambridge / 2009 / iii / Paper 40 / 6

The observed-data likelihood function integrates out the latent variable:Choose an initial parameter ${\theta }^{(0)}$ with positive likelihood. At iteration $t$, the E-step of the EM algorithm forms the entire expected complete-data log-likelihoodThe expectation is under the conditional missing-data law at the old parameter, while the argument $\theta$ remains free. The M-step then choosesThe observed data $x$ stay fixed throughout. This is not obtained merely by substituting the conditional mean of $z$ into a nonlinear log-likelihood: the expectation of all required complete-data terms must be taken. A generalized EM step only requires $Q({\theta }^{(t+1)}\mid {\theta }^{(t)})\ge Q({\theta }^{(t)}\mid {\theta }^{(t)})$, which suffices for the monotonicity proved next. Exact maximization assumes that an admissible maximizer exists.

Write ${\theta }_0={\theta }^{(t)}$ and $h_0(z)=f(x,z;{\theta }_0)/L(x\mid {\theta }_0)$. Assume the likelihoods are positive and the expected log likelihoods used in the step are finite. On the support where $h_0>0$, let $r(z)=f(x,z;\theta )/f(x,z;{\theta }_0)$. Integrating over that support givesIt is an equality when the candidate joint density has no additional mass outside the old support. Concavity of the logarithm and the Jensen inequality now implyThus the argument does not silently require an identical support at every parameter. The M-step selects a value whose right-hand side is nonnegative, proving EM likelihood monotonicity:When the conditional densities allow finite divergence, the same calculation has the informative exact formThe Kullback-Leibler divergence is nonnegative, since ${\mathbb{E}}_{h_0}\log (h_{\theta }/h_0)\le \log {\int }_{\{h_0>0\}}{h}_{\theta }\le 0$. This also explains why an increase of the surrogate objective guarantees an increase of the observed objective, while equality of the two likelihoods is possible.

EM likelihood monotonicity makes EM an ascent method, not a global-optimization theorem. If the log-likelihood is bounded above along the iterates, its nondecreasing values converge. That alone does not show that the parameters converge, nor that any limiting parameter is a global maximum-likelihood estimator. Under additional regularity, accumulation points can be stationary; local maxima, other stationary points or flat sets can depend on initialization. Multiple starting values and comparison of the achieved observed likelihoods are therefore useful.

The upper-bound hypothesis is substantive. In a finite mixture model with a freely shrinking normal-component variance, placing one component at an observed value can make the likelihood unbounded while other components cover the remaining observations. In that situation monotonicity provides no finite maximum to converge to. EM may also improve very slowly, and a small change in likelihood alone is not proof of an accurate global solution. The guarantee in part (b) is nondecrease, not strict increase at every iteration.

Both EM algorithm and data augmentation exploit a latent completion $z$, but they use it differently. EM takes a conditional expectation of the complete-data log-likelihood and then maximizes over the parameter, producing a deterministic sequence of point estimates when the M-step is uniquely specified.

In Bayesian data augmentation, choose a prior distribution $p(\theta )$ and targetAlternate the Gibbs sampler updatesThese are stochastic draws from full conditional distributions, not an expectation followed by maximization. Their invariant law is the augmented joint posterior, and discarding $z$ gives posterior inference for $\theta$, including uncertainty rather than only an MLE. A sampled completion followed by maximization would instead be a stochastic EM variant. Individual likelihood values along a data-augmentation chain need not increase: the chain is designed to sample a posterior, not to ascend the likelihood.