Machine Learning from First Principles

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:

$$J(c, \vmu) = \sum_{i=1}^n\norm{\vx^{(i)} - \vmu_{c^{(i)}}}_2^2. \tag{13.1}$$

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}$:
$$\pi_j = \frac{N_j}{n}, \quad \vmu_j = \frac{1}{N_j}\sum_i r_{ij}\vx^{(i)}, \quad \mSigma_j = \frac{1}{N_j}\sum_i r_{ij}(\vx^{(i)} - \vmu_j)(\vx^{(i)} - \vmu_j)\T. \tag{13.4}$$
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

$$\mathbf\Lambda=\Big(\sum_i\vx_c^{(i)}\hat\vz_i\T\Big)\Big(\sum_i\big(\hat\vz_i\hat\vz_i\T+\mSigma_{z\mid x}\big)\Big)^{-1},\qquad \mathbf\Psi=\diag\Big(\frac1n\sum_i\big(\vx_c^{(i)}\vx_c^{(i)\top}-\mathbf\Lambda\hat\vz_i\vx_c^{(i)\top}\big)\Big). \tag{13.7}$$

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

  1. 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$.
  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)$.
  3. MathDerive the M-step update for $\vmu_j$.
  4. MathShow the gap in the EM lower bound equals $D_{\mathrm{KL}}(q\Vert p(z\mid\vx))$.
  5. CodingRun $k$-means ($k=2$) on two concentric rings. Why does it fail? Add the feature $x_1^2 + x_2^2$ and retry.
  6. CodingCluster load_digits with $k = 10$, show centers as images, and score with adjusted_rand_score.
  7. MathShow that the two expressions for the ELBO in Equation (13.5) are equal, and conclude that the posterior maximizes it over $q$.
  8. 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}$.
  9. 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$.
Machine Learning from First Principles · Edition 2.0 · Companion site to the PDF book.