Expectation Maximization

Where We Are

A Gaussian Mixture Model would be easy to fit if every point told us which Gaussian created it. But those component labels are hidden.

Expectation Maximization (EM) turns that circular problem into an alternating conversation.

1. The chicken-and-egg problem

To estimate component means, we want assignments. To estimate assignments, we want component means.

need assignments ──→ estimate parameters
      ↑                    │
      └──── need parameters┘

EM does not solve both simultaneously. It alternates.

2. E-step: estimate hidden membership

Using current parameters, compute responsibilities

$r_{ik}=p(z_i=k\mid x_i).$

For a GMM,

$r_{ik}=\frac{\pi_k\mathcal N(x_i\mid\mu_k,\Sigma_k)}{\sum_j\pi_j\mathcal N(x_i\mid\mu_j,\Sigma_j)}.$

This is Bayes’ rule from Chapter 086 returning in a practical algorithm.

3. M-step: update parameters

Treat responsibilities as fractional membership. Define

$N_k=\sum_i r_{ik}.$

Then

$\mu_k=\frac{1}{N_k}\sum_i r_{ik}x_i,$

$\pi_k=\frac{N_k}{N},$

with covariance updated by a responsibility-weighted variance calculation.

A point with responsibility 0.8 contributes 0.8 of itself to that component’s statistics.

4. Repeat

initialize parameters
      ↓
E: infer hidden variables
      ↓
M: improve parameters
      ↓
likelihood converged? ──no──↺

Each iteration does not decrease the observed-data likelihood, but EM can converge to a local optimum. Initialization matters.

5. Why EM is a bigger idea than GMMs

The pattern applies whenever a useful variable is latent:

• infer hidden structure under current parameters;
• optimize parameters under the inferred structure.

The mathematics can be derived using Jensen’s inequality and a lower bound on log likelihood. The intuitive story, however, is already powerful: guess hidden explanations, improve the model, then improve the explanations.

6. Relationship to K-Means

K-Means alternates assignments and centres. EM for a GMM alternates soft assignments and distribution parameters. This makes K-Means feel less like an isolated trick and more like part of a family of alternating optimization methods.

What to Remember

• EM is useful when learning involves latent variables.
• E-step estimates a distribution over hidden variables.
• M-step optimizes parameters using those estimates.
• Likelihood improves monotonically, but local optima remain possible.

Next → PCA from Eigenvectors: clustering asks for hidden groups. Can we instead discover hidden directions that explain most of the variation?