Past exam of the mathematics course of the University of Cambridge / 2008 / iii / Paper 47 / 6

The expectation-maximization algorithm alternates conditional averaging over missing data with maximization over the parameter. Start at a parameter value ${\theta }^{(0)}$ for which the observed likelihood function is positive. At iteration $t$, its E-step formsusing the current conditional law of $Z$ but treating $\theta$ as the candidate parameter. Its M-step takesRepeat until the parameter or observed log-likelihood stabilizes. An increase of $Q$ implies an increase of the observed log-likelihood: if $q_t(z)=f(z\mid x;{\theta }^{(t)})$, thenwhere Kullback-Leibler divergence is nonnegative. In general this monotonicity does not guarantee a global maximum; distinct initializations may approach different stationary points. The particular observed log-likelihood below is concave, which makes a stronger conclusion possible there.

The parameter-dependent part of the complete multinomial distribution log-likelihood isThe remaining probability factors and multinomial coefficient are constant in $\theta$. If $y_1+y_2+y_3>0$, differentiating gives $-y_1/(1-\theta )+(y_2+y_3)/\theta$, whose zero isThe log-likelihood is concave. If $y_2+y_3=0<y_1$, its maximum is at zero; if $y_1=0<y_2+y_3$, its maximum is at one. These boundary cases are included by the same formula. If $y_1=y_2=y_3=0$, the data lie entirely in the parameter-independent fourth cell and every $\theta \in [0,1]$ is a maximum-likelihood estimator.

Within the merged third observed cell, the probability of belonging to the original fourth cell isThe allocation therefore has the conditional binomial distributionIts conditional expectation and the filled-in missing counts arewith $y_1^{(t)}=x_1$ and $y_2^{(t)}=x_2$.

Taking the conditional expectation of the complete log-likelihood gives the EM for merged multinomial cells E-step:This is the parameter-dependent part of $\log L(y^{(t)}\mid \theta )$. More precisely, $Q(\theta \mid {\theta }^{(t)})=\log L(y^{(t)}\mid \theta )+C_t^{\prime }$, where the constant is independent of the candidate $\theta$, interpreting factorials of noninteger filled counts through the gamma function. The expected log-factorials are not generally the log-factorials of expected counts, so literal equality including the normalization would be false. Equality up to this constant is exactly what the M-step needs. Filling in conditional means works here because the candidate-parameter terms are linear in the missing counts; it is not a universal rule for the expectation-maximization algorithm.

Initialize $0<{\theta }^{(0)}<1$. At each iteration first compute $y_3^{(t)}=x_3{\theta }^{(t)}/(2+{\theta }^{(t)})$ by the conditional expectation above. The M-step applies the complete-data maximum-likelihood estimator to the filled counts, givingRepeat until convergence. If all counts are zero, the likelihood function is constant and any parameter can be retained. For a nonempty sample an interior start makes the displayed denominator positive.

Here the three observed cell probabilities are $(1-\theta )/2$, $\theta /4$ and $(2+\theta )/4$, so the observed log-likelihood isFor a nonempty sample its second derivative on $(0,1)$ isThus the maximum-likelihood estimator is unique, allowing a boundary maximum. To verify that the iteration actually finds it, let $u(\theta )=x_3\theta /(2+\theta )$ and $F(\theta )=(x_2+u(\theta ))/(x_1+x_2+u(\theta ))$. Then $F^{\prime }(\theta )=x_1{u}^{\prime }(\theta )/(x_1+x_2+u(\theta ){)}^2\ge 0$, andIf the maximum is interior, this identity moves each iterate towards it, and monotonicity of $F$ prevents crossing it. The bounded monotone iterates converge; continuity makes their limit a fixed point, and strict concavity makes that fixed point the maximum. If the maximum is at zero or one, the sign of ${\ell }^{\prime }$ gives the same monotone convergence towards the appropriate endpoint. In the special case $x_1=0$, $F$ is identically one whenever its denominator is positive, so the maximum is reached in one step. An interior initialization avoids the possible spurious zero fixed point when $x_2=0$; starting at zero can otherwise trap the iteration even when the true maximum is positive.

Using the EM for merged multinomial cells E-step,Applying the M-step maximum-likelihood estimator to the filled counts gives