Expectation Maximization

Expectation Maximization

1. When Needed

Data has hidden variables (which Gaussian generated $x$? what is missing value?). Direct likelihood needs sum over unknowns — hard. EM alternates guessing hiddens and refitting.

2. Two Steps (repeat till converged)

E-step: q = p(hidden | x, current θ)  (soft assignments)
M-step: θ = argmax expected complete log-likelihood under q

Likelihood never decreases. Converges to local optimum — restart like $k$-means.

3. Example — 1-D Two Gaussians

Heights mix of two groups. E: responsibility $γ_{i} = p(group₁|x_{i})$. M: $μ₁$ = weighted mean with $γ$, $μ₂$ with $1-γ$, similarly variances + mixing weight.

4. Uses

Missing data fill, HMM training (Baum-Welch), topic models, semi-supervised.

5. Exam Points

• E + M steps + monotonicity — 5-7 marks, very frequent.
• Responsibility numerical — 5 marks, frequent.
• Local-optimum + restarts — 2 marks.