Expectation–maximization algorithm

Remarks

The key property is monotonicity: $L(\theta^{(t+1)}) \ge L(\theta^{(t)})$. Indeed, $\log L(\theta) = Q(\theta \mid \theta^{(t)}) - E\big[\log p(Z \mid x; \theta)\big]$ with the expectation over $Z \sim p(\cdot \mid x; \theta^{(t)})$, and by Jensen's inequality the second term is smallest at $\theta = \theta^{(t)}$. The E-step is a conditional expectation given the observed data. The iterates need not converge to the maximum likelihood estimate: they may stop at a local maximum or a saddle point.

Example: a mixture of two normal densities $\pi\, \varphi_{\mu_1, 1} + (1 - \pi)\, \varphi_{\mu_2, 1}$ with latent labels $z_i \in \set{1, 2}$. The E-step computes the weights $w_i = \pi \varphi_{\mu_1,1}(x_i) / \big(\pi \varphi_{\mu_1,1}(x_i) + (1-\pi)\varphi_{\mu_2,1}(x_i)\big)$ at the current parameters; the M-step sets $\pi = \frac{1}{n}\sum_i w_i$, $\mu_1 = \sum_i w_i x_i / \sum_i w_i$ and $\mu_2 = \sum_i (1 - w_i) x_i / \sum_i (1 - w_i)$.

Non-example: if the M-step only chooses some $\theta^{(t+1)}$ with $Q(\theta^{(t+1)} \mid \theta^{(t)}) \ge Q(\theta^{(t)} \mid \theta^{(t)})$, without maximizing, clause 2 fails; this variant is called a generalized EM algorithm, and it keeps the monotonicity property.