Gaussian Mixtures & EM

A Gaussian Mixture Model is K-Means with two restrictions lifted: clusters can be tilted ellipses of different sizes, and every point gets a soft probability of membership. It is fit by Expectation-Maximization, a general algorithm for problems with hidden variables. This page covers the mixture model and its EM updates, then EM as a meta-algorithm.

Rapid Recall

A GMM models data as a weighted sum of Gaussians, each with its own mean, covariance, and weight, and fits them by EM. The E-step computes responsibilities, the soft posterior probability that cluster k produced each point; the M-step re-estimates each Gaussian as a responsibility-weighted mean, covariance, and count. Constraining the covariance to a scaled identity collapses GMM to K-Means, so K-Means is hard EM on a spherical GMM. EM exists to beat the log-of-a-sum: it climbs a lower bound that touches the true log-likelihood, guaranteeing monotonic improvement to a local optimum.

§1 The generative model

K-Means assumes every cluster is a round blob of the same size and every point belongs entirely to one cluster. GMM relaxes both. It says your data was generated by a mixture of Gaussians; each cluster is a Gaussian with its own center, its own shape (stretched, tilted, not just round), and its own weight. Every point gets a soft assignment: a probability of belonging to each cluster. A boundary point can be "70% A, 30% B" instead of being snapped to one. Soft membership plus elliptical clusters are what GMM buys over K-Means.

The generative process:

1. Pick a cluster \(k\) with probability \(\pi_k\) (the mixing coefficient; \(\sum_k\pi_k=1\)).
2. Draw a point from that cluster's Gaussian \(\mathcal{N}(\mu_k,\Sigma_k)\), mean \(\mu_k\) (center), covariance \(\Sigma_k\) (shape, orientation, spread).

The overall density is a weighted sum of Gaussians:

\[p(\mathbf{x})=\sum_{k=1}^{K}\pi_k\,\mathcal{N}(\mathbf{x}\mid\boldsymbol{\mu}_k,\boldsymbol{\Sigma}_k)\]

In words: the probability of a point is the sum, over clusters, of "how likely that cluster is" times "how likely that cluster would produce this point." Fitting finds the \(\pi_k,\mu_k,\Sigma_k\) that make the observed data most likely.

The K-Means connection

The covariance \(\Sigma_k\) is where the power lives, it lets a cluster be a tilted ellipse. Constrain \(\Sigma_k\) to a scaled identity (spherical, equal size) and a GMM collapses into K-Means. That is the precise relationship.

K-Means forces round, equal blobs and hard labels; GMM fits tilted ellipses of different shapes and assigns soft probabilities.

§2 Fitting via EM (the specific case)

Chicken-and-egg: to know each cluster's parameters you'd need to know which points belong to it, but to assign points you'd need the parameters. EM alternates:

E-step: responsibilities (soft assignment via Bayes)

"Of all clusters, weighted by how likely each is to have produced point \(n\), what fraction of the credit goes to cluster \(k\)?"

\[\gamma(z_{nk})=\frac{\pi_k\,\mathcal{N}(\mathbf{x}_n\mid\boldsymbol{\mu}_k,\boldsymbol{\Sigma}_k)}{\sum_{j=1}^{K}\pi_j\,\mathcal{N}(\mathbf{x}_n\mid\boldsymbol{\mu}_j,\boldsymbol{\Sigma}_j)}\]

M-step: re-estimate parameters from responsibilities

Let \(N_k=\sum_n\gamma(z_{nk})\) be the total "responsibility mass" of cluster \(k\). Then:

\[\boldsymbol{\mu}_k^{\text{new}}=\frac{1}{N_k}\sum_n\gamma(z_{nk})\,\mathbf{x}_n\]

\[\boldsymbol{\Sigma}_k^{\text{new}}=\frac{1}{N_k}\sum_n\gamma(z_{nk})\,(\mathbf{x}_n-\boldsymbol{\mu}_k^{\text{new}})(\mathbf{x}_n-\boldsymbol{\mu}_k^{\text{new}})^{\top}\]

\[\pi_k^{\text{new}}=\frac{N_k}{N}\]

Each update is a responsibility-weighted mean / covariance / count: points that "belong more" to \(k\) pull its parameters more. The log-likelihood is guaranteed to increase (or stay flat) each iteration, so it converges.

Carry this into an interview

E-step assigns, M-step updates, exactly K-Means' assign/update loop, but with soft probabilistic responsibilities instead of hard nearest-centroid assignments. K-Means is "hard EM" on a spherical GMM.

The catches

• Local optimum only, sensitive to init → initialize with K-Means first, then run EM.
• Still must choose \(K\), but principled: use BIC / AIC (likelihood vs parameter-count tradeoff), pick lowest. Quantitative model selection, unlike eyeballing an elbow.
• Covariance singularity: a Gaussian latching onto one point sends its variance to 0 and likelihood to \(\infty\). Regularize by adding a small value to \(\Sigma\)'s diagonal.
• Covariance type knob: full (any ellipse), diag (axis-aligned), spherical (circles), tied (shared shape). More freedom → more parameters → more data needed, more overfitting risk.

Complexity

\(O(n\cdot K\cdot d^2\cdot\text{iters})\) for full covariance (the \(d^2\) is the covariance matrices). Heavier than K-Means' \(O(nKd)\), but still linear in \(n\), scales far better than hierarchical.

Where to use it

• Good for: elliptical, overlapping, or unequal clusters; needing soft membership; a generative model (sample, density, BIC); density-based anomaly detection (low \(p(x)\)).

§3 Expectation-Maximization (the general algorithm)

EM is not just for GMMs, it's a general meta-algorithm for a recurring class of problem.

The problem EM exists to solve

You want maximum-likelihood parameters \(\theta\). Normally: write the likelihood, differentiate, set to zero, solve. EM exists for when you can't, when there are hidden (latent) variables \(Z\) that, if known, would make the problem trivial.

The signature of an EM-shaped problem

"If I knew \(Z\), estimating \(\theta\) would be easy. And if I knew \(\theta\), inferring \(Z\) would be easy. But I know neither." In a GMM, \(Z\) = which Gaussian generated each point.

Why the direct approach breaks

The observed-data log-likelihood requires summing over all hidden values:

\[\log p(X\mid\theta)=\log\sum_{Z}p(X,Z\mid\theta)\]

The killer is the log of a sum. If it were a sum of logs you could differentiate term-by-term and solve. But the log sits outside the summation over \(Z\), tangling all clusters' parameters inside one logarithm, no closed form. EM is the trick for getting around the log-of-a-sum.

The core idea: optimize a surrogate lower bound

The complete-data log-likelihood \(\log p(X,Z\mid\theta)\) is a sum of logs, easy. The only difficulty is not knowing \(Z\). So EM replaces \(Z\) with its expectation under the current best guess, the Q-function:

\[Q(\theta\mid\theta^{\text{old}})=\mathbb{E}_{Z\mid X,\theta^{\text{old}}}\big[\log p(X,Z\mid\theta)\big]\]

"The average of the easy complete-data log-likelihood, taken over the hidden variables, using current beliefs about them."

The two steps fall out

• E-step: with \(\theta^{\text{old}}\) fixed, infer the posterior over hidden variables \(p(Z\mid X,\theta^{\text{old}})\) and form \(Q\). (In a GMM this posterior is the responsibilities.)
• M-step: maximize \(Q\) over \(\theta\). Because \(Q\) is the expected complete-data likelihood, it's a sum of logs again, the tangle is gone, closed-form solvable. The maximizer is the new \(\theta\).

\[\theta^{\text{new}}=\arg\max_{\theta}\;Q(\theta\mid\theta^{\text{old}})\]

Why it's guaranteed to work

Each iteration EM maximizes a lower bound on the true log-likelihood, constructed to touch it exactly at \(\theta^{\text{old}}\). The M-step pushes the bound up, so the true likelihood must rise at least as much. Therefore the log-likelihood monotonically increases every iteration. Formally, the gap between the true likelihood and the bound is a KL divergence (always \(\geq 0\)); the E-step zeroes that gap at \(\theta^{\text{old}}\) by setting the bound's distribution to the true posterior.

\[\log p(X\mid\theta)=\underbrace{\mathcal{L}(q,\theta)}_{\text{lower bound (ELBO)}}+\underbrace{\mathrm{KL}\!\left(q\,\|\,p(Z\mid X,\theta)\right)}_{\geq 0}\]

The catch

Monotonic improvement guarantees you reach a peak, not the highest peak, EM converges to a local optimum. Hence sensitivity to initialization.

The clean mental model

EM turns one impossible optimization into a sequence of easy ones. It guesses the latent variables (E-step), solves the now-easy problem as if the guess were truth (M-step), then re-guesses with improved parameters, bootstrapping uphill, alternately refining beliefs about hidden structure and the parameters until both stop moving.

Where EM shows up beyond GMMs

• K-Means — hard EM (hidden = cluster label; E = hard nearest-centroid assignment; M = recompute centroids).
• Hidden Markov Models — Baum-Welch is EM (hidden = unobserved state sequence). Classical speech recognition, bioinformatics.
• Missing-data imputation — hidden = the missing values themselves (the most general framing; clustering is just "the cluster label is missing").
• Latent Dirichlet Allocation / topic models — variational EM (hidden = which topic generated each word).
• Factor analysis / probabilistic PCA — hidden = the low-dimensional latent factors.
• Mixtures of anything (Bernoulli, Poisson), censored / truncated data in survival analysis.

Recipe for a novel situation

1. Am I doing maximum likelihood (or MAP) on a probabilistic model?
2. Is there a latent variable such that, if I knew it, the fit would be easy?
3. Given current parameters, can I compute (or approximate) the posterior over that hidden variable?

All three yes → EM applies. If step 3's posterior is intractable → variational EM (approximate the posterior with a simpler family), the bridge to variational inference and the VAE.

Interview questions

Q1: What does a GMM add over K-Means, and how are they related? A GMM models data as a weighted mixture of Gaussians, each with its own mean and covariance, so clusters can be tilted ellipses of different sizes, and it gives every point a soft probability of membership rather than a hard label. Constraining every covariance to a scaled identity makes the clusters spherical and equal and collapses the GMM into K-Means. So K-Means is hard EM on a spherical GMM.

Q2: Describe the E-step and M-step for a GMM. The E-step computes responsibilities, the posterior probability that each cluster produced each point, by Bayes' rule using the current parameters. The M-step re-estimates each Gaussian as a responsibility-weighted mean, a responsibility-weighted covariance, and a mixing weight equal to its share of total responsibility. Points that belong more to a cluster pull its parameters more, and the log-likelihood increases each round until convergence.

Q3: Why does EM exist, and what is the trick? The observed-data log-likelihood is a log of a sum over the hidden variable, which has no closed form because the log sits outside the sum and tangles all parameters. EM sidesteps this with the complete-data likelihood, which is a clean sum of logs: the E-step fills in the expected hidden variables given current parameters, and the M-step maximizes that expected complete-data likelihood, which is now solvable in closed form.

Q4: Why is EM guaranteed to improve, and what does it not guarantee? Each iteration maximizes a lower bound on the true log-likelihood that the E-step makes touch the true value at the current parameters, since the gap is a non-negative KL divergence that the E-step zeroes. Pushing the bound up in the M-step therefore raises the true likelihood at least as much, so it increases monotonically. It only guarantees reaching a local optimum, not the global one, which is why EM is sensitive to initialization and GMMs are seeded with K-Means.