EM & Gaussian Mixture Models

Chapter 1: The Mixture Model — A Recipe for the Data

To cluster probabilistically, we first tell a story about how the data was generated — just like the generative-learning lesson. The story is called a Gaussian Mixture Model, and it imagines each data point being born in two steps:

Repeat for every point, and you get data that looks like several overlapping elliptical blobs of different sizes — exactly the kind of data k-means struggles with. The crucial twist: we see the points, but not which cluster each one came from. That cluster identity — the hidden label z — is a latent variable: real, but unobserved. Our whole job is to work backwards from the visible points to recover the k Gaussians and the hidden labels.

This generative view is powerful because it tells us exactly what we're estimating: the mixing weights φ_j (how big each cluster is), the means μ_j (where each is centered), and the covariances Σ_j (each cluster's shape). Find those, and you've not just clustered the data — you've built a full probabilistic model that can score how likely any new point is, generate synthetic data, and report calibrated cluster memberships. It's clustering and density estimation in one.

Chapter 2: The Chicken-and-Egg Problem

Here's what makes fitting a mixture model genuinely tricky — and the trap reveals the elegant idea that escapes it. We want to find the Gaussians (the φ's, μ's, Σ's) and recover the hidden labels z. But these two unknowns are locked in a circular dependency.

So each unknown is easy if you have the other. But we have neither — we start with just a cloud of unlabeled points. It's a perfect chicken-and-egg deadlock: to find the labels we need the Gaussians, and to find the Gaussians we need the labels.

The Expectation-Maximization (EM) algorithm breaks the deadlock with a move you've now seen several times in this course: guess, then refine. Start with random Gaussians. Then alternate two steps, each one using the current best guess of one unknown to improve the other:

That's the whole idea, and it should feel deeply familiar — it's the exact same "alternate between two easy sub-problems" structure as k-means (assign, then update). In fact, as we'll see in Chapter 6, k-means is EM with the soft guesses hardened to 0-or-1. EM is k-means that kept the probabilities.

Chapter 3: The E-Step — Soft-Guessing the Labels

Let's build the first half of EM. The E-step (Expectation) answers: given my current guess of the Gaussians, how likely is each point to have come from each cluster? The answer is a set of soft memberships called responsibilities — for point i and cluster j, the responsibility w_ij is the probability that point i was generated by cluster j.

We compute it with Bayes' rule — the exact same tool from the generative-learning lesson. Two ingredients decide how much cluster j "claims" a point:

• The prior φ_j: how big cluster j is overall. A bigger cluster is an a-priori more likely origin for any point.
• The likelihood: how well cluster j's Gaussian explains this point — its density at the point's location. A point sitting in the heart of a tight blob gets high likelihood from that blob; one far out in the tails gets low.

Multiply prior × likelihood for each cluster, then normalize so the responsibilities across all clusters sum to 1. That normalization is what makes them honest probabilities — "this point is 70% cluster A, 25% cluster B, 5% cluster C." A point dead-center in one blob gets responsibility ≈1 for it; a point on a boundary splits its responsibility between the neighbors, exactly the soft, uncertain answer we wanted in Chapter 0.

Notice this is precisely the soft version of k-means' assign step. k-means said "go to your single nearest center." The E-step says "distribute yourself across all centers, weighted by how probable each is." Same role — figure out cluster membership — but k-means commits to one answer while EM keeps the full distribution. And because it uses the full Gaussian (not just distance to the center), it naturally accounts for each cluster's shape and size: a point can be far from a stretched cluster's center yet still firmly belong, if it lies along the cluster's long axis.

Chapter 4: The M-Step — Re-Fitting the Gaussians

Now the second half. The M-step (Maximization) takes the soft responsibilities from the E-step and uses them to update each Gaussian. It pretends the soft memberships are correct and asks: given these weighted points, what's the best Gaussian for each cluster? The answer is a beautiful weighted version of the same count-and-average we used for hard labels.

For each cluster j, every point contributes to it in proportion to its responsibility w_ij for that cluster. A point that's 90% cluster A counts as 0.9 of a point toward A's statistics and 0.1 toward B's. Then:

• Mixing weight φ_j: the total responsibility cluster j received, divided by the number of points. ("How many points, softly, belong to me?")
• Mean μ_j: the responsibility-weighted average position of all points. Points that strongly belong pull the center harder; weakly-belonging points barely nudge it.
• Covariance Σ_j: the responsibility-weighted spread of points around the new mean — this is what lets each cluster discover its own shape, stretching and tilting its ellipse to match the data it owns.

Compare these to the hard-label formulas from the generative-learning lesson and they're identical — except the crisp 0/1 "is this point in cluster j?" indicator is replaced by the soft responsibility w_ij ∈ [0,1]. That's the entire difference between EM and supervised Gaussian fitting: EM uses fractional memberships because it doesn't actually know the labels, only its current best guess of them. Each M-step move is the exact maximum-likelihood update given those soft guesses.

Chapter 5: The EM Lab

Everything together, live. Below is a full GMM trained by EM. Watch the Gaussians begin as random circles and, through alternating E and M steps, flow outward — stretching, tilting, and sliding until each ellipse wraps snugly around a real cluster. This is where you see EM do what k-means cannot.

(No quiz — the lab is the test. If you can watch an ellipse and predict which way it'll stretch on the next M-step, you understand EM. Notice how the soft coloring in overlap regions never fully commits — that honesty about uncertainty is the whole point.)

Chapter 6: EM vs. k-Means — The Same Algorithm, Softened

We've hinted at it repeatedly; now let's make it precise. k-means is a special case of EM. They're not cousins — one is literally the other with two simplifications. Seeing this unifies everything you've learned across these two lessons.

Take EM for Gaussian mixtures and make two changes. First, harden the responsibilities: instead of soft probabilities, force each point to give responsibility 1 to its most-probable cluster and 0 to all others. Second, freeze the covariances: force every cluster to be a fixed-size sphere (identity covariance), so the Gaussian density depends only on distance to the center. Make those two changes, and the E-step becomes "assign each point to its nearest center" and the M-step becomes "move each center to the mean of its assigned points." That's exactly k-means.

Chapter 7: Why EM Converges

EM feels like a heuristic — guess, refine, repeat — but it carries a real guarantee: every iteration increases (or holds) the likelihood of the data. The model gets strictly more probable each round until it settles. Let's understand why, without drowning in algebra.

The quantity EM is climbing is the log-likelihood — how probable the observed data is under the current Gaussians. We can't maximize it directly (that's the chicken-and-egg problem). So EM does something clever: at each step it builds a lower bound — a simpler function that sits underneath the true log-likelihood and touches it at the current parameters. The E-step constructs this bound (using the responsibilities); the M-step jumps to the top of the bound. Because the bound touches the true objective where you started and you climbed the bound, you must have climbed the true objective too.

The mathematical tool that builds the bound is Jensen's inequality — a fact about convex functions stating that "the average of a function is at least the function of the average" (for convex functions; the reverse for concave). Applied to the log (a concave function), it lets us swap a hard-to-handle "log of a sum" for an easy-to-maximize "sum of logs," producing exactly the bound EM optimizes. You don't need the derivation to use EM, but the upshot is solid: EM is principled hill-climbing on the data likelihood, guaranteed never to go downhill.

Two practical consequences follow. First, like k-means, EM can get stuck in a local optimum — the likelihood surface is bumpy, and a bad initialization lands in a mediocre valley. The cure is the same: run multiple random restarts (often initialized with k-means!) and keep the highest-likelihood result. Second, EM is a general framework, not just a clustering trick: any model with hidden variables — mixtures, hidden Markov models, topic models, missing-data problems — can be trained with the same E-step/M-step recipe. Learning EM here unlocks a huge swath of probabilistic modeling.

Chapter 8: Connections & Cheat Sheet

You've turned k-means' rigid "pick one" into a full probabilistic model — soft memberships, flexible shapes, and a convergence guarantee — and met EM, a framework that reaches far beyond clustering. That's a major step into modern probabilistic machine learning.

The whole lesson on one page

GMM in code

python
import numpy as np
from scipy.stats import multivariate_normal

def em_gmm(X, k, iters=100):
    n, d = X.shape
    # init: random means, identity covariances, equal weights
    mu = X[np.random.choice(n, k, replace=False)]
    Sigma = [np.eye(d) for _ in range(k)]; phi = np.ones(k)/k
    for _ in range(iters):
        # E-STEP: responsibilities = prior × Gaussian density, normalized
        W = np.array([phi[j]*multivariate_normal(mu[j],Sigma[j]).pdf(X) for j in range(k)]).T
        W /= W.sum(1, keepdims=True)
        # M-STEP: weighted re-estimation
        Nk = W.sum(0); phi = Nk/n
        mu = (W.T @ X) / Nk[:,None]
        for j in range(k):
            diff = X - mu[j]
            Sigma[j] = (W[:,j,None]*diff).T @ diff / Nk[j] + 1e-6*np.eye(d)
    return phi, mu, Sigma, W

# sklearn (k-means init + restarts built in):
from sklearn.mixture import GaussianMixture
gmm = GaussianMixture(n_components=3, n_init=5).fit(X)
gmm.predict_proba(X_new)   # soft responsibilities for new points

Where to go next

• k-Means — the hard, spherical special case; revisit it now seeing it inside EM.
• Generative Learning (GDA) — EM's M-step is GDA's Gaussian fitting, but with soft labels instead of given ones.
• Hidden Markov Models — EM (the Baum-Welch algorithm) for sequences with hidden states; the same E/M recipe over time.
• Variational Autoencoders — the modern deep-learning descendant of EM for latent-variable models; the E-step becomes a neural network.
• The next lesson, PCA — another unsupervised method, but for dimensionality reduction rather than clustering: finding the few directions that capture most of the data's variation.

"When you have eliminated the impossible, whatever remains, however improbable, must be the truth." — Sherlock Holmes. EM never eliminates — it keeps every possibility alive with a probability, and lets the data slowly sharpen the improbable into the clear.