Past exam of the mathematics course of the University of Cambridge / 2002 / iii / Paper 40 / 4 / b / i / Solution

For observed data $x$ and latent variables $Z$, let ${\ell }_c(\theta ;x,Z)=\log p_{\theta }(x,Z)$ be the complete-data log-likelihood. From a current parameter ${\theta }^{(m)}$, the expectation-maximization algorithm computesand then chooses ${\theta }^{(m+1)}$ maximizing this function in its first argument. Thus the E-step averages the missing information conditional on the current model and observed data; the M-step treats those expectations as fixed while maximizing.

For a short proof of likelihood function monotonicity, let $q_m(Z)=p_{{\theta }^{(m)}}(Z\mid x)$. ThenThe Jensen inequality for the logarithm gives $\ell (\theta ;x)-\ell ({\theta }^{(m)};x)\ge Q(\theta \mid {\theta }^{(m)})-Q({\theta }^{(m)}\mid {\theta }^{(m)})$. The M-step makes the right side nonnegative. Thus observed likelihood function cannot decrease. This proves the usual EM likelihood monotonicity, while allowing convergence to local stationary points rather than guaranteeing a global maximum.