Chapter 13 · Part III: Unsupervised Learning
Clustering and the EM Algorithm
With no labels, look for groups. $k$-means and Gaussian mixtures are the two classic answers, and they introduce two ideas used everywhere in machine learning: alternating minimization and the EM algorithm.
After this chapter you will be able to
- State the $k$-means objective and derive Lloyd's algorithm.
- Prove that Lloyd's algorithm never increases the objective, and explain why it can still fail.
- Initialize with $k$-means++ and choose the number of clusters.
- Write down a Gaussian mixture and compute responsibilities with Bayes' rule.
- Derive EM for Gaussian mixtures and relate it to $k$-means.
13.1Unsupervised Learning and Clustering
Unsupervised learning has inputs only. Clustering assigns each example to one of $k$ groups of similar examples: customers, topics, pixel colors, cell types. With no ground truth, different criteria give different answers, so the algorithms here state their criteria explicitly.
13.2The k-Means Objective and Lloyd's Algorithm
$k$-means picks centers $\vmu_j$ and assignments $c^{(i)}$ to minimize the within-cluster sum of squares:
Joint minimization is NP-hard, but each half is easy. Assignment: with centers fixed, send each point to its nearest center. Update: with assignments fixed, each center's gradient $-2\sum_{i:c^{(i)}=j}(\vx^{(i)} - \vmu_j)$ vanishes at the mean of its members. Alternating is Lloyd's algorithm.
Proposition 13.1
Lloyd's algorithm never increases $J$ and stops after finitely many iterations. Proof: each step exactly minimizes $J$ over one block of variables, so $J$ cannot rise; there are finitely many assignments and none can repeat while $J$ strictly falls.
It finds a local minimum that depends on initialization, so run several restarts and keep the lowest $J$. Every cluster is a convex Voronoi cell, so $k$-means suits compact, round clusters of similar size, and it needs scaled features.
13.3Initialization with k-Means++
Pick the first center at random from the data; then repeatedly pick the next center with probability proportional to $D(\vx)^2$, the squared distance to the nearest center so far. Far-away points are likely picks, so centers spread across clusters. This seeding alone guarantees an expected objective within $O(\log k)$ of optimal, and it is scikit-learn's default.
13.4Choosing the Number of Clusters
$J$ always falls as $k$ grows, so it cannot choose $k$. Use the elbow of $J$ versus $k$; the silhouette $s = (b - a)/\max(a, b)$, where $a$ is a point's mean distance within its cluster and $b$ to the nearest other cluster; likelihood criteria such as BIC for mixtures; or the needs of the application.
13.5Gaussian Mixture Models
A GMM is a generative model with a hidden component $z$: draw $z = j$ with probability $\pi_j$, then $\vx\sim\Normal(\vmu_j, \mSigma_j)$. So $p(\vx) = \sum_j\pi_j\Normal(\vx; \vmu_j, \mSigma_j)$, with clusters that can be elongated, tilted, and of different sizes. Bayes' rule gives each point's soft assignment, its responsibility:
$$r_{ij} = p(z = j\mid\vx^{(i)}) = \frac{\pi_j\Normal(\vx^{(i)}; \vmu_j, \mSigma_j)}{\sum_l\pi_l\Normal(\vx^{(i)}; \vmu_l, \mSigma_l)}. \tag{13.3}$$13.6The EM Algorithm
The log-likelihood $\sum_i\log\sum_j\pi_j\Normal(\vx^{(i)}; \vmu_j, \mSigma_j)$ has no closed-form maximizer. But with known components it would split into $k$ ordinary Gaussian fits. EM alternates soft guessing and refitting:
- E-step: compute $r_{ij}$ with the current parameters.
- M-step: weighted Gaussian MLE with $N_j = \sum_i r_{ij}$:
Show derivation: why EM never decreases the likelihood
For any distribution $q_i$ over components, Jensen's inequality gives
$$\log p(\vx^{(i)}) = \log\sum_j q_i(j)\frac{p(\vx^{(i)}, j)}{q_i(j)} \ge \sum_j q_i(j)\log\frac{p(\vx^{(i)}, j)}{q_i(j)},$$with gap $D_{\mathrm{KL}}(q_i\Vert p(z\mid\vx^{(i)}))$. The E-step sets $q_i$ to the posterior, closing the gap; the M-step maximizes the bound, so the likelihood can only rise. This bound is the evidence lower bound (ELBO), the training objective of VAEs in Chapter 25.
Key idea: $k$-means is a limit of EM
Fix covariances to $\sigma^2\mI$ and weights to $1/k$, and let $\sigma\to0$. Responsibilities become hard nearest-mean assignments, and EM becomes Lloyd's algorithm.
EM finds local maxima (initialize from $k$-means, restart a few times). A component that collapses onto one point has a singular covariance and infinite likelihood; add a small multiple of $\mI$ to every covariance.
13.7EM in General
Nothing above was specific to Gaussians. For any model with observed $\vx$, latent $\vz$, and parameters $\vtheta$ where the complete-data likelihood $p(\vx,\vz;\vtheta)$ is easy but the marginal $p(\vx;\vtheta)$ is not, define the evidence lower bound
$$\mathrm{ELBO}(q,\vtheta)=\sum_{i}\sum_{\vz}q_i(\vz)\log\frac{p(\vx^{(i)},\vz;\vtheta)}{q_i(\vz)}=\ell(\vtheta)-\sum_{i}D_{\mathrm{KL}}\big(q_i\,\Vert\,p(\vz\mid\vx^{(i)};\vtheta)\big)\le\ell(\vtheta). \tag{13.5}$$EM is coordinate ascent on it. E-step: with $\vtheta$ fixed, the KL term vanishes at $q_i=p(\vz\mid\vx^{(i)};\vtheta)$. M-step: with $q$ fixed, maximize the expected complete-data log-likelihood $\sum_i\E_{q_i}[\log p(\vx^{(i)},\vz;\vtheta)]$. Then
$$\ell(\vtheta_{t+1})\ \ge\ \mathrm{ELBO}(q^{(t)},\vtheta_{t+1})\ \ge\ \mathrm{ELBO}(q^{(t)},\vtheta_t)\ =\ \ell(\vtheta_t),$$so the likelihood never decreases, even if the M-step only improves the bound (generalized EM). The recipe fits hidden Markov models (Baum–Welch), mixtures of Naive Bayes for semi-supervised text, missing data, and factor analysis. When the posterior is intractable, restricting $q$ to a tractable family and ascending the ELBO by gradients is variational inference; with a neural network computing $q$ it becomes the VAE of Chapter 25.
13.8Factor Analysis
A full covariance has $d(d+1)/2$ parameters and is singular when $n$ is not much larger than $d$; a diagonal one discards all correlations. Factor analysis explains correlations with $k<d$ hidden factors:
$$\vz\sim\Normal(\mathbf 0,\mI_k),\qquad \vx\mid\vz\sim\Normal(\vmu+\mathbf\Lambda\vz,\,\mathbf\Psi), \tag{13.6}$$with a $d\times k$ loading matrix $\mathbf\Lambda$ and diagonal noise $\mathbf\Psi$: each feature is a combination of the factors plus its own noise (ten test scores explained by verbal and quantitative ability, say). Marginally $\vx\sim\Normal(\vmu,\mathbf\Lambda\mathbf\Lambda\T+\mathbf\Psi)$: low rank plus diagonal, $dk+d$ parameters, positive definite even when $n<d$.
EM. The E-step is Gaussian conditioning: $\mSigma_{z\mid x}=(\mI+\mathbf\Lambda\T\mathbf\Psi^{-1}\mathbf\Lambda)^{-1}$ and $\hat\vz_i=\mSigma_{z\mid x}\mathbf\Lambda\T\mathbf\Psi^{-1}(\vx^{(i)}-\vmu)$. With $\vx_c^{(i)}=\vx^{(i)}-\vmu$, the M-step is
This is least squares of $\vx$ on the expected factors, corrected by the posterior uncertainty $\mSigma_{z\mid x}$ (treating guessed factors as observed would be a mistake).
Relation to PCA. With isotropic noise $\mathbf\Psi=\sigma^2\mI$ the model is probabilistic PCA (Tipping and Bishop 1999), whose MLE spans the principal subspace and reduces to PCA as $\sigma\to0$ (Chapter 14). Per-feature noise keeps one very noisy feature from hijacking a factor. Factors are identified only up to rotation ($\mathbf\Lambda\mathbf R$ gives the same distribution), so interpret individual factors with care.
import numpy as np
from sklearn.decomposition import FactorAnalysis
def fit_factor_analysis(X, k, iters=500, seed=0):
n, d = X.shape
mu = X.mean(0)
Xc = X - mu
S = Xc.T @ Xc / n # sample covariance
rng = np.random.default_rng(seed)
Lam = rng.standard_normal((d, k)) * np.sqrt(np.diag(S).mean() / k)
Psi = np.diag(S).copy()
for _ in range(iters):
# E-step: Gaussian posterior of z given each x
G = np.linalg.inv(np.eye(k) + Lam.T @ (Lam / Psi[:, None])) # Sigma_{z|x}
Ez = Xc @ (Lam / Psi[:, None]) @ G # rows: E[z | x_i]
Ezz = n * G + Ez.T @ Ez # sum_i E[z z^T | x_i]
# M-step, Eq. (13.7)
Lam = (Xc.T @ Ez) @ np.linalg.inv(Ezz)
Psi = np.maximum(np.diag(S - Lam @ (Ez.T @ Xc) / n), 1e-6)
return mu, Lam, Psi
def avg_loglik(X, mu, Lam, Psi):
C = Lam @ Lam.T + np.diag(Psi) # marginal covariance
_, logdet = np.linalg.slogdet(C)
Xc = X - mu
quad = np.einsum("ij,ij->i", Xc @ np.linalg.inv(C), Xc)
return np.mean(-0.5 * (quad + logdet + X.shape[1] * np.log(2 * np.pi)))
rng = np.random.default_rng(1)
n, d, k = 300, 10, 2
L_true = rng.standard_normal((d, k))
noise_sd = rng.uniform(0.2, 1.5, d) # a different noise level per feature
X = rng.standard_normal((n, k)) @ L_true.T + noise_sd * rng.standard_normal((n, d))
mu, Lam, Psi = fit_factor_analysis(X, k)
ref = FactorAnalysis(n_components=k).fit(X)
print("our average log-likelihood: ", round(avg_loglik(X, mu, Lam, Psi), 4))
print("sklearn average log-likelihood:", round(ref.score(X), 4))
print("estimated noise sd:", np.round(np.sqrt(Psi), 2))
print("true noise sd: ", np.round(noise_sd, 2))
Both reach the same log-likelihood, and the estimated per-feature noise levels track the true ones.
13.9Implementation
import numpy as np
def kmeans_pp_init(X, k, rng):
centers = [X[rng.integers(len(X))]]
for _ in range(k - 1):
d2 = np.min(((X[:, None, :] - np.array(centers)[None])**2).sum(-1), axis=1)
centers.append(X[rng.choice(len(X), p=d2 / d2.sum())])
return np.array(centers)
def kmeans(X, k, iters=100, seed=0):
rng = np.random.default_rng(seed)
mu = kmeans_pp_init(X, k, rng)
for _ in range(iters):
d2 = ((X[:, None, :] - mu[None])**2).sum(-1)
c = d2.argmin(1) # assignment
new_mu = np.array([X[c == j].mean(0) if np.any(c == j) else mu[j]
for j in range(k)]) # update
if np.allclose(new_mu, mu):
break
mu = new_mu
return mu, c, d2[np.arange(len(X)), c].sum()
def gaussian_logpdf(X, mu, S):
L = np.linalg.cholesky(S)
z = np.linalg.solve(L, (X - mu).T)
return -0.5 * (z**2).sum(0) - np.log(np.diag(L)).sum() - 0.5 * X.shape[1] * np.log(2 * np.pi)
def gmm_em(X, k, iters=200, seed=0, reg=1e-6):
n, d = X.shape
mu, _, _ = kmeans(X, k, seed=seed)
S = np.array([np.cov(X.T) for _ in range(k)])
pi = np.full(k, 1 / k)
for _ in range(iters):
logp = np.stack([np.log(pi[j]) + gaussian_logpdf(X, mu[j], S[j]) for j in range(k)], axis=1)
logp -= logp.max(1, keepdims=True)
R = np.exp(logp); R /= R.sum(1, keepdims=True) # E-step
N = R.sum(0)
pi, mu = N / n, (R.T @ X) / N[:, None] # M-step
for j in range(k):
D = X - mu[j]
S[j] = (R[:, j, None] * D).T @ D / N[j] + reg * np.eye(d)
return pi, mu, S, R
In scikit-learn: KMeans(n_clusters=k, n_init=10) and GaussianMixture(n_components=k). Project 4 uses $k$-means to compress image colors.
13.10Common Pitfalls
Pitfall: reading clusters as ground truth
Clustering returns $k$ groups even for structureless data. Check stability across seeds and subsamples before interpreting.
Pitfall: unscaled features
The feature with the largest range dominates Euclidean distance. Standardize or choose a meaningful distance.
13.11Summary
- $k$-means alternates nearest-center assignment and mean updates, reaching a local minimum of $J$.
- $k$-means++ spreads initial centers; use restarts.
- Choose $k$ by elbow, silhouette, BIC, or application needs.
- A GMM has a latent component; responsibilities are posterior probabilities.
- EM alternates responsibilities and weighted refits, never decreasing likelihood; $k$-means is its hard limit.
- In general, EM is coordinate ascent on the ELBO: the E-step sets $q$ to the posterior, the M-step maximizes the expected complete-data log-likelihood, and the likelihood never decreases.
- Factor analysis models $\vx=\vmu+\mathbf\Lambda\vz+\text{noise}$ with $k$ factors and diagonal noise: a low-rank-plus-diagonal covariance that works even when $n<d$, fitted by EM; it generalizes probabilistic PCA.
13.12Exercises
- MathShow the cluster mean minimizes $\sum_{i\in C}\norm{\vx^{(i)} - \vmu}^2$, with minimum $\frac{1}{2|C|}\sum_{i,i'\in C}\norm{\vx^{(i)} - \vx^{(i')}}^2$.
- MathShow the boundary between two centers is the hyperplane $(\vmu_1 - \vmu_2)\T\vx = \frac12(\norm{\vmu_1}^2 - \norm{\vmu_2}^2)$.
- MathDerive the M-step update for $\vmu_j$.
- MathShow the gap in the EM lower bound equals $D_{\mathrm{KL}}(q\Vert p(z\mid\vx))$.
- CodingRun $k$-means ($k=2$) on two concentric rings. Why does it fail? Add the feature $x_1^2 + x_2^2$ and retry.
- CodingCluster
load_digitswith $k = 10$, show centers as images, and score withadjusted_rand_score. - MathShow that the two expressions for the ELBO in Equation (13.5) are equal, and conclude that the posterior maximizes it over $q$.
- MathDerive the joint distribution of $(\vz,\vx)$ under (13.6) and the posterior of $\vz$ given $\vx$. Verify $\mathbf\Lambda\T(\mathbf\Lambda\mathbf\Lambda\T+\mathbf\Psi)^{-1}=(\mI+\mathbf\Lambda\T\mathbf\Psi^{-1}\mathbf\Lambda)^{-1}\mathbf\Lambda\T\mathbf\Psi^{-1}$.
- CodingWith $d=50$, $k=3$, $n=40$, compare held-out log-likelihoods of a full-covariance Gaussian (small ridge), a diagonal Gaussian, and factor analysis with $k=1,\dots,6$.