Expectation-Maximization (EM)

Summary

Expectation-Maximization alternates posterior computation with parameter improvement for a latent-variable model. An exact posterior makes a likelihood lower bound touch the current objective; improving that fixed bound cannot decrease observed likelihood. This guarantee is not a global-optimum or component-identification guarantee.

The two steps

Let x be observations, z latent variables, and theta parameters. Require available exact posteriors, common support, finite required expectations, and an M-step that does not reduce its target.

E-step

Given current parameters $θ_{t}$ , compute the posterior over latents:

q_{t} (z) = p (z ∣ x; θ_{t}) .

Current theta stays fixed while q is computed. Calculate expected complete-data sufficient statistics, not merely a substituted mean latent value. For example, $E [z z^{⊤}]$ generally differs from $E [z] E [z]^{⊤}$ .

M-step

Update $θ$ to maximize the expected complete-data log-likelihood:

θ_{t + 1} = ar g θ max E_{z \sim q_{t}} [lo g p (x, z; θ)] .

Here q stays fixed while theta changes. Write $Q (θ ∣ θ_{t}) = E_{q_{t}} lo g p (x, z; θ)$ .

For a teaching mixture, choose a coin independently for each two-toss group. Initial weights are $(0.5, 0.5)$ and head probabilities $(0.75, 0.25)$ ; observe head counts two and one. The binomial probability includes $(h 2) p^{h} (1 - p)^{2 - h}$ . Count two has likelihoods $(0.5625, 0.0625)$ , giving responsibilities $(0.9, 0.1)$ . Count one has likelihoods $(0.375, 0.375)$ , giving responsibilities $(0.5, 0.5)$ .

Effective group counts are $(1.4, 0.6)$ ; weighted heads are $(2.3, 0.7)$ . The M-step sets weights to $(0.7, 0.3)$ and head probabilities to $(2.3/2.8, 0.7/1.2) = (23/28, 7/12)$ . The denominators count expected tosses, not expected groups. Observed likelihood rises from $0.3125 \times 0.375 = 0.1171875$ to approximately $0.20172548$ . Its log rises from $- 2.143980$ to $- 1.600848$ .

Why it works

EM maximizes a lower bound on $lo g p (x; θ)$ :

lo g p (x; θ) = E_{q} [lo g p (x, z; θ)] - E_{q} [lo g q (z)] + KL (q ∥ p_{θ} (z ∣ x)) .

Write $F (q, θ) = Q (θ ∣ θ_{t}) + H (q)$ when q is the current posterior. The identity says $ℓ (θ) = F (q, θ) + KL (q ∥ p_{θ})$ , with a nonnegative KL gap. Exact E sets the gap to zero at theta_t. Improving Q with q fixed then yields:

ℓ (θ_{t + 1}) \geq F (q_{t}, θ_{t + 1}) \geq F (q_{t}, θ_{t}) = ℓ (θ_{t}) .

Learning objective

Raise a touching lower bound to prevent the likelihood from falling

Derivation

exact E makes the dashed bound touch observed log likelihood at the current parameter. M improves that fixed bound. Likelihood remains above it, proving nondecrease under the stated assumptions. The next exact E-step closes the new gap.

Check: Which two inequalities ensure the new likelihood cannot fall after the bound is improved?

Read it this way: This illustrative bound touches at 0.5. Its maximum at 0.25 raises the objective from -0.25 to -0.0625.
Why is the true objective at the new bound maximum no lower than the old objective?

Add a Parameter Prior

New task: Prefer interior coin probabilities with independent Beta(2,2) priors; leave mixture weights unregularized.

Picture and change: Keep posterior responsibilities, but maximize Q plus log prior.

Check: Probability updates become $3.3/4.8 = 0.6875$ and $1.7/3.2 = 0.53125$ .

Use when: A MAP estimator is required. The protected objective is log posterior, not bare observed likelihood.

Improve Only Part of M

New task: Update mixture weights while keeping both coin probabilities at their initial values.

Picture and change: This generalized M-step improves Q without jointly maximizing every parameter.

Check: Weights $(0.7, 0.3)$ give observed likelihood $0.4125 \times 0.375 = 0.1546875$ , above the initial value.

Use when: A verified improving parameter block is available but joint optimization is expensive.

Identical components can remain identical; nondecreasing likelihood does not distinguish them or identify a global solution. Under appropriate regularity and convergence conditions, limit points can be stationary, including saddles. Unconstrained Gaussian mixtures can instead diverge through covariance collapse.

Canonical example: GMM

Gaussian mixtures apply this owner to posterior component responsibilities and weighted Gaussian sufficient statistics. Detailed covariance updates belong to that application, not a second generic EM derivation.

Variants

Hard assignment: k-means relates to restricted mixtures through hard-assignment or small-variance limits, not ordinary finite-variance exact EM.
Stochastic approximations: sampling noise need not preserve likelihood nondecrease at every iteration.
Variational E: improving a restricted lower bound does not automatically increase observed likelihood; the touching-bound step may be missing.
MAP-EM: an explicit prior changes the optimized objective.

Limitations

Initialization, latent-model specification, missing information, and numerical optimization affect convergence and usefulness. Comparing restarts does not turn a nonconvex model into a globally solved problem.

Common pitfalls

Ad hoc covariance stabilization and approximate E/M updates require their own objective/monotonicity analysis. Alternating two convenient steps is not enough to establish the exact EM proof.

Gaussian mixture models. The canonical EM application.
Hidden Markov models. Sequential model trained by EM (Baum-Welch).