Expectation-Maximization (EM)

Source: Unit 3 §10

The problem EM solves

≡FactsWhere plain MLE runs out

• Maximum Likelihood Estimation (MLE) searches over distributions and parameters to fit the data, but it requires complete data - every interacting variable must be observed.
• MLE becomes intractable the moment there are hidden or latent variables: unobserved variables that interact with the data you can see.

EM performs MLE in the presence of latent variables by alternating two steps that each assume the other's answer:

• E-step: estimate the values of the latent variables, given the current parameters.
• M-step: optimise the model parameters, assuming the estimated latent values are true.
• Repeat until convergence.

Neither half can be computed without the other, so EM alternates: freeze the parameters to fill in the hidden data, then freeze the hidden data to re-fit the parameters. The loop only ever climbs, which is also why it can only reach a local maximum.

⚠GotchaEM converges, but not necessarily to the right place

The loop converges to a local maximum. A different initial guess can land on a different answer, so EM in practice means EM with several random restarts, keeping the best likelihood.

Warm-up: K-means as a special case

K-means partitions data into K distinct, non-overlapping clusters. You must specify K in advance, and each observation is assigned to exactly one cluster.

≡FactsThe two cluster properties

With clusters C₁, …, Cₖ:

1. C₁ ∪ C₂ ∪ … ∪ Cₖ = {1, …, n} - every point belongs to some cluster.
2. Cₖ ∩ Cₖ' = ∅ for k ≠ k' - the clusters do not overlap.

Objective: minimise the within-cluster variation summed over all clusters, where intra-cluster distance is measured by Euclidean distance between pairs of points.

EM step	K-means action
E-step	Assign each data point to the closest cluster: wᵢₖ = 1 if xᵢ is in cluster k, else 0.
M-step	Recompute the centroid (the mean) of each cluster.

K-means is EM with hard assignments: the E-step colours every point by its nearest centroid, and the M-step slides each centroid to the mean of its colour. Repeat until nothing moves.

Convergence is guaranteed, but only to a local minimum, which is the same caveat as EM in general and the same fix: multiple random restarts.

EM in general

→StepsThe two steps, stated without reference to any model

1. E-step: the missing data are estimated, given the observed data and the current parameter estimates.
2. M-step: the likelihood is maximised, assuming the missing data are known - the E-step's estimates are used in place of the actual missing data.
3. Repeat, feeding each step's output into the other, until the parameters stop changing.

Worked example: two coins

Problem: estimate the biases $\theta_A$ and $\theta_B$ of two coins. The experiment: pick a coin at random, flip it 10 times, record the results. Do that 5 times.

Case 1: the coin identities are known

This is the easy case, and it is just counting.

θ₁ = 24/30 = 0.80 (24 heads out of 30 flips assigned to coin A)

θ₂ = 9/20 = 0.45 (9 heads out of 20 flips assigned to coin B)

Case 2: the coin identities are unknown

The coin identity is now a latent variable, and counting is no longer available. Use EM.

→StepsOne pass of EM on the coins

1. Guess initial biases, say $\theta_A = 0.4$ and $\theta_B = 0.7$. Each coin is equally likely to have been picked: $P(Z_A) = P(Z_B) = 0.5$.
2. E-step. For each trial - take $E = HHHHHHHHTT$, which is 8 heads and 2 tails - compute how likely each coin is to have produced it: $P(E \mid Z_A) = \theta_A^{8}(1 - \theta_A)^{2}$ and $P(E \mid Z_B) = \theta_B^{8}(1 - \theta_B)^{2}$.
3. Apply Bayes. Because $P(Z_A) = P(Z_B) = 0.5$, the priors cancel: $P(Z_A \mid E) = \dfrac{P(E \mid Z_A)}{P(E \mid Z_A) + P(E \mid Z_B)}$.
4. Proportionally assign the head and tail counts of that trial to each coin, in the ratio of those responsibilities. The counts become fractional.
5. M-step. Recompute $\theta_A$ and $\theta_B$ from the fractional assigned counts, exactly as in case 1 but with soft counts.
6. Repeat. The iteration converges to a local maximum.

E-step: "how likely is each coin, given this trial's flips?" → soft-assign heads/tails

M-step: "given those soft counts, what bias best explains them?" → update θ_A, θ_B

◎Exam cueCase 1 is what EM is imitating

EM's M-step is the same counting formula as the known-identity case. The only difference is that the counts are fractional, weighted by the E-step's responsibilities. If the responsibilities ever became 0 or 1, EM would reduce exactly to case 1.

Gaussian Mixture Models

≡FactsGMM in three lines

• A multivariate Gaussian is a vector of normally distributed variables where any linear combination is also normal. The univariate case is the familiar single bell.
• A GMM models the data as a mixture of several Gaussians, and we estimate their parameters - means, covariances and mixing weights - by Maximum Likelihood, which in practice means EM.
• EM for GMM is soft clustering: the E-step computes the responsibility of each Gaussian for each point, and the M-step updates each Gaussian's mean, covariance and weight.

⇄CompareHard versus soft assignment

K-means (hard)The E-step assigns each point to exactly one cluster, so wᵢₖ is 0 or 1. A point on the boundary has to pick a side.

GMM (soft)The E-step gives each Gaussian a fractional responsibility for each point. A boundary point contributes to both clusters, in proportion to how well each explains it.

≡FactsApplications of EM

• Estimating the parameters of a Gaussian Mixture Model.
• The Baum-Welch algorithm for Hidden Markov Models - see HMM Algorithms.
• Clustering generally.