Machine Learning from First Principles

Chapter 14 · Part III: Unsupervised Learning

Dimensionality Reduction

High-dimensional data usually lie near a much smaller subspace. PCA finds the best such linear subspace, and two natural definitions of "best" turn out to give the same answer: the eigenvectors of the covariance matrix.

After this chapter you will be able to

  • Explain what dimensionality reduction is for.
  • Derive PCA as maximum-variance directions: eigenvectors of the covariance.
  • Show the same directions minimize reconstruction error, and compute it from eigenvalues.
  • Compute PCA stably with the SVD.
  • Choose the number of components.
  • Recognize when linear PCA is not enough.

14.1Why Reduce Dimensions?

An $8\times8$ digit image lives in $\R^{64}$, but neighboring pixels are correlated and most pixel combinations never occur. Dimensionality reduction finds a compact code $\vz\in\R^k$, $k\ll d$, for visualization, compression, denoising (noise spreads over all directions, signal concentrates in a few), and preprocessing. Throughout, center the data so the rows of $\mX$ average to zero; the covariance is $\mS = \frac1n\mX\T\mX$.

14.2Maximum Variance Directions

Projections onto a unit vector $\vu$ have variance $\frac1n\sum_i(\vu\T\vx^{(i)})^2 = \vu\T\mS\vu$. Maximize it subject to $\vu\T\vu = 1$: the Lagrangian condition $2\mS\vu - 2\lambda\vu = \mathbf 0$ gives

$$\mS\vu = \lambda\vu, \qquad \vu\T\mS\vu = \lambda. \tag{14.3}$$

The best direction is the top eigenvector, and its eigenvalue is the variance along it. Later components are the next eigenvectors; with $\mS = \mU\mathbf\Lambda\mU\T$, the coordinates $z_j = \vu_j\T\vx$ are uncorrelated with variances $\lambda_j$.

Intuition: finding the long axis

Rotate a line through a tilted elliptical cloud and watch the spread of the points' shadows. It peaks along the long axis and bottoms out along the short axis. Those axes are the principal components.

14.3Minimum Reconstruction Error

Encode with $\vz = \mU_k\T\vx$ and decode with $\hat\vx = \mU_k\vz$, the projection onto a $k$-dimensional subspace. By Pythagoras, $\norm{\vx}^2 = \norm{\mU_k\T\vx}^2 + \norm{\vx - \hat\vx}^2$, so the average error is a constant minus the captured variance $\sum_{j\le k}\vu_j\T\mS\vu_j$. Minimizing error = maximizing variance, and

$$\min_{\mU_k}\frac1n\sum_i\norm{\vx^{(i)} - \mU_k\mU_k\T\vx^{(i)}}^2 = \sum_{j=k+1}^d\lambda_j. \tag{14.4}$$

Key idea: two views, one answer

The PCA subspace keeps the most variance and loses the least squared distance. Each eigenvalue is both the variance along its component and the error from dropping it.

14.4Computing PCA with the SVD

Avoid forming $\mX\T\mX$ (it squares the condition number). Take the SVD of the centered data, $\mX = \mathbf A\mathbf\Sigma\mV\T$. Then $\mS = \mV(\mathbf\Sigma^2/n)\mV\T$: the right singular vectors are the components, $\lambda_j = s_j^2/n$, and the projected data are $\mathbf Z = \mX\mV_k = \mathbf A_k\mathbf\Sigma_k$. The truncated SVD is also the best rank-$k$ approximation of $\mX$ (Eckart–Young). Randomized SVD computes the top components of huge matrices quickly.

14.5Choosing the Number of Components

The explained variance ratio $(\lambda_1 + \dots + \lambda_k)/(\lambda_1 + \dots + \lambda_d)$ guides the choice: keep 90–99%, look for an elbow in the scree plot, or cross-validate the downstream model. For plots, $k = 2$ or 3.

14.6Using PCA in Practice

  • Standardize or not? PCA is unit-sensitive. Standardize features measured in different units; for pixels, only center.
  • Whitening divides each coordinate by $\sqrt{\lambda_j}$ for identity covariance; it helps conditioning but amplifies noisy directions.
  • Limitations. PCA finds flat subspaces only. t-SNE and UMAP preserve local neighborhoods for visualization (distances between their clusters mean little). Autoencoders (Section 14.9) generalize PCA to nonlinear encoders and decoders, and ICA (Section 14.8) looks for independent rather than merely uncorrelated directions.

14.7Implementation

import numpy as np
from sklearn.datasets import load_digits

X = load_digits().data                       # (1797, 64), pixel values 0..16
mean = X.mean(0)
Xc = X - mean

A, s, Vt = np.linalg.svd(Xc, full_matrices=False)
eigvals = s**2 / len(X)
ratio = np.cumsum(eigvals) / eigvals.sum()
k = int(np.searchsorted(ratio, 0.90)) + 1
print(f"{k} components explain 90% of the variance")

Z = Xc @ Vt[:k].T                            # encode
X_hat = Z @ Vt[:k] + mean                    # decode
err = np.mean(np.sum((X - X_hat)**2, axis=1))
print(f"reconstruction error {err:.2f} = sum of dropped eigenvalues {eigvals[k:].sum():.2f}")

scikit-learn's PCA(n_components=k) does the same; PCA(0.90) picks $k$ for 90% explained variance. Project 5 goes further.

14.8Independent Component Analysis

At a party $d$ people talk at once and $d$ microphones each record a different mixture. Recovering each voice from the recordings alone is the cocktail-party problem, solved by independent component analysis (ICA). The model is

$$\vx=\mA\vs,\qquad p(\vs)=\prod_{j=1}^dp_s(s_j), \tag{14.7}$$

with independent sources $\vs$, an unknown invertible mixing matrix $\mA$, and the goal $\mW=\mA^{-1}$.

What can be recovered. Order and scale (including sign) of the sources are unidentifiable, which is harmless for separating voices. The sources must not be Gaussian: for $\vs\sim\Normal(\mathbf 0,\mI)$ every rotation $\mathbf R\vs$ has the same distribution, so the rotation can never be identified (at most one source may be Gaussian).

Why PCA is not enough. PCA decorrelates. After whitening, every rotation is still white, so second-order statistics cannot choose among rotations; ICA uses higher-order statistics. By the central limit theorem, mixtures are “more Gaussian” than sources, so ICA can search for the least Gaussian directions: this is FastICA (Hyvärinen and Oja 2000).

Maximum likelihood ICA. By change of variables $p(\vx)=p(\mW\vx)|\det\mW|$, so with rows $\vw_j\T$ of $\mW$

$$\ell(\mW)=\sum_{i=1}^n\Big(\sum_{j=1}^d\log p_s(\vw_j\T\vx^{(i)})+\log|\det\mW|\Big). \tag{14.8}$$

With the sigmoid as source CDF, $p_s=\sigma'$, and $\nabla_{\mW}\log|\det\mW|=(\mW^{-1})\T$, stochastic gradient ascent is $\mW\gets\mW+\alpha\big((\mathbf 1-2\sigma(\mW\vx^{(i)}))\vx^{(i)\top}+(\mW\T)^{-1}\big)$ (Bell and Sejnowski 1995). Multiplying by $\mW\T\mW$ gives the natural gradient $(\mI+(\mathbf 1-2\sigma(\vy))\vy\T)\mW$, $\vy=\mW\vx$, with no inverse. The logistic density is heavy-tailed (super-Gaussian), suiting speech; light-tailed sources such as sine waves need another nonlinearity, and FastICA handles both.

ICA removes eye-blink artifacts from EEG, separates audio, and analyzes fMRI and financial series. On natural image patches it learns oriented edge detectors, much like first-layer CNN filters (Chapter 17).

import numpy as np
from sklearn.decomposition import FastICA

rng = np.random.default_rng(0)
n = 5000
t = np.linspace(0, 10, n)
# three "speech-like" super-Gaussian sources: Laplace noise with slowly varying loudness
S = rng.laplace(size=(3, n)) * np.abs(np.sin(np.outer([0.7, 1.3, 2.1], t)))
A = rng.uniform(-1, 1, (3, 3))                         # unknown mixing matrix
X = A @ S                                              # three microphones

def ica_infomax(X, lr=0.1, iters=500):
    # maximum likelihood ICA with a logistic source CDF (Bell and Sejnowski)
    Xc = X - X.mean(1, keepdims=True)
    d, E = np.linalg.eigh(np.cov(Xc))
    K = E @ np.diag(d ** -0.5) @ E.T                   # whitening matrix
    Z = K @ Xc
    W = np.eye(len(X))
    for _ in range(iters):
        Y = W @ Z
        G = 1 - 2 / (1 + np.exp(-Y))                   # d/dy log sigmoid'(y) = 1 - 2 sigmoid(y)
        W += lr * (np.eye(len(X)) + G @ Y.T / Z.shape[1]) @ W   # natural-gradient ascent
    return W @ K                                       # unmixing matrix for centered X

W = ica_infomax(X)
S_hat = W @ (X - X.mean(1, keepdims=True))
C = np.abs(np.corrcoef(S, S_hat)[:3, 3:])              # |correlation| true vs recovered
print("infomax: best |corr| per source:", np.round(C.max(1), 3))
S_fast = FastICA(3, random_state=0, whiten="unit-variance").fit_transform(X.T).T
C2 = np.abs(np.corrcoef(S, S_fast)[:3, 3:])
print("FastICA: best |corr| per source:", np.round(C2.max(1), 3))

14.9Autoencoders

An autoencoder replaces PCA's linear maps with learned functions: an encoder $f_{\boldsymbol\phi}:\R^d\to\R^k$ produces a code, a decoder $g_{\vtheta}$ maps it back, and both minimize reconstruction error:

$$\min_{\boldsymbol\phi,\vtheta}\ \frac1n\sum_{i=1}^n\big\Vert\vx^{(i)}-g_{\vtheta}\big(f_{\boldsymbol\phi}(\vx^{(i)})\big)\big\Vert^2. \tag{14.9}$$

The linear autoencoder is PCA. With linear $f(\vx)=\mathbf E\vx$, $g(\vz)=\mathbf D\vz$, the reconstruction is a rank-$k$ map and the best one projects onto the top-$k$ principal subspace (Equation (14.4)). Baldi and Hornik (1989) showed every local minimum is global. The code units need not be the principal components themselves: $\mathbf E\to\mathbf M\mathbf E$, $\mathbf D\to\mathbf D\mathbf M^{-1}$ gives the same reconstruction.

Deep autoencoders with nonlinear layers capture curved manifolds and beat PCA at the same code size (Hinton and Salakhutdinov 2006).

Regularized autoencoders. With $k\ge d$ an unconstrained autoencoder can learn the identity. A sparse autoencoder penalizes the code (e.g. $\lambda\norm{\vz}_1$); sparse autoencoders are now used to find interpretable features inside large language models. A denoising autoencoder (Vincent et al. 2008) reconstructs the clean $\vx$ from a corrupted $\tilde\vx=\vx+\boldsymbol\epsilon$, so it must learn where the data lie. That idea seeds diffusion models (Chapter 25); masking instead of noise gives masked autoencoders (Chapter 26); a probabilistic code gives the VAE.

import numpy as np
import torch
from torch import nn
from sklearn.datasets import load_digits

X = load_digits().data / 16.0                          # (1797, 64) in [0, 1]
rng = np.random.default_rng(0)
perm = rng.permutation(len(X))
Xtr, Xte = X[perm[:1500]], X[perm[1500:]]
k = 8                                                  # code size

# PCA: encode with the top-k right singular vectors of the centered training data
mean = Xtr.mean(0)
Vk = np.linalg.svd(Xtr - mean, full_matrices=False)[2][:k]
pca_err = np.mean(np.sum((Xte - ((Xte - mean) @ Vk.T @ Vk + mean)) ** 2, axis=1))

torch.manual_seed(0)
Xtr_t, Xte_t = (torch.tensor(a, dtype=torch.float32) for a in (Xtr, Xte))

def train(model, noise=0.0, epochs=300):
    opt = torch.optim.Adam(model.parameters(), lr=3e-3)
    for _ in range(epochs):
        for idx in torch.randperm(len(Xtr_t)).split(128):
            xb = Xtr_t[idx]
            x_in = xb + noise * torch.randn_like(xb)   # denoising variant: corrupt the input only
            loss = ((model(x_in) - xb) ** 2).sum(1).mean()
            opt.zero_grad(); loss.backward(); opt.step()
    with torch.no_grad():                              # held-out reconstruction error
        return ((model(Xte_t) - Xte_t) ** 2).sum(1).mean().item()

linear = nn.Sequential(nn.Linear(64, k), nn.Linear(k, 64))
deep = nn.Sequential(nn.Linear(64, 128), nn.ReLU(), nn.Linear(128, k),
                     nn.ReLU(), nn.Linear(k, 128), nn.ReLU(), nn.Linear(128, 64))
print(f"test error  PCA (k={k}):         {pca_err:.3f}")
print(f"test error  linear autoencoder: {train(linear):.3f}")
print(f"test error  deep autoencoder:   {train(deep):.3f}")

The linear autoencoder matches PCA, and the deep autoencoder reconstructs held-out digits noticeably better with the same 8 numbers per image.

Pitfall: good reconstructions, useless codes

Low reconstruction error does not make the code useful downstream: the autoencoder spends capacity on whatever dominates squared error (backgrounds, lighting). Evaluate codes on the task, for example with a linear classifier.

14.10Common Pitfalls

Pitfall: forgetting to center

Uncentered, the first "component" points toward the data mean rather than along the spread.

Pitfall: fitting PCA on all the data

Fit on training data only and apply the same transform to validation and test data.

Pitfall: assuming high variance means useful

PCA ignores labels; a low-variance direction may be the one that separates classes.

14.11Summary

  • Principal components are covariance eigenvectors ordered by eigenvalue (variance).
  • They also minimize reconstruction error, which equals the sum of dropped eigenvalues.
  • Compute from the SVD of centered data; $\lambda_j = s_j^2/n$.
  • Choose $k$ by explained variance, scree plot, or downstream validation.
  • PCA is linear and label-blind; autoencoders generalize it.
  • ICA models $\vx=\mA\vs$ with independent non-Gaussian sources and recovers them up to order and scale; Gaussian sources cannot be unmixed.
  • Autoencoders reconstruct the input through a bottleneck; the linear one recovers the PCA subspace, deep ones capture curved manifolds, and denoising autoencoders lead to diffusion models and masked pretraining.

14.12Exercises

  1. MathShow the coordinates $z_j = \vu_j\T\vx$ are uncorrelated with $\Var(z_j) = \lambda_j$.
  2. MathProve the second component is the second eigenvector, using two Lagrange multipliers.
  3. MathFor $\mS = \begin{pmatrix}a&b\\b&c\end{pmatrix}$, find the eigenvalues and the angle of the first component.
  4. MathShow $\mX\mV_k = \mathbf A_k\mathbf\Sigma_k$. Why might the right side be preferable?
  5. CodingDenoise digits (noise s.d. 4) by projecting onto components learned from clean images. Plot error against $k$; why isn't the best $k$ 64?
  6. CodingCompare 2D embeddings of load_digits from PCA and t-SNE, colored by label.
  7. MathDerive the gradient of (14.8) with the logistic source density, and show that multiplying by $\mW\T\mW$ gives the natural-gradient update.
  8. MathShow that for Gaussian sources $\mA$ and $\mA\mathbf R$ give the same distribution of $\vx$ for every orthogonal $\mathbf R$.
  9. CodingTrain denoising autoencoders on the digits with noise 0, 0.2, 0.5 and code size 32. Show reconstructions of noisy test digits and compare a logistic regression trained on each set of codes.
Machine Learning from First Principles · Edition 2.0 · Companion site to the PDF book.