Machine Learning · Lecture 16a

Lecture 16a
Dimension Reduction I: Linear Methods

Part IV · Unsupervised learning  |  principal component analysis by maximum variance and minimum error, the SVD, eigenfaces, scree plots and the Eckart–Young theorem, PCA of human genotypes, probabilistic PCA and factor analysis, random projections and the Johnson–Lindenstrauss lemma, matrix factorisation for recommendations  |  reading: Hastie, Tibshirani & Friedman, The Elements of Statistical Learning (2nd ed.), §14.5; Bishop, Pattern Recognition and Machine Learning (2006), ch. 12; Tipping & Bishop (1999); Dasgupta & Gupta (2003); Koren, Bell & Volinsky (2009)  |  nonlinear methods follow in Lecture 16b

Cartoon: choosing the shadowA stick figure holds a long loaf of bread in front of a lamp. On the wall one shadow is a small circle; after turning the loaf, the shadow is a long oval. The figure says the long shadow shows more of the bread. Head-on, the loaf is acircle. Sideways, a loaf. shadows
A projection keeps some of an object's shape and loses the rest; PCA chooses the direction that keeps the most
In this lecture
  1. Principal component analysis
  2. Choosing the dimension, and PCA of genomes
  3. Probabilistic PCA and factor analysis
  4. Random projections and the Johnson–Lindenstrauss lemma
  5. Matrix factorisation for recommendations
  6. Summary, exercises, projects, reading

A 64×64 grey-scale photograph is a point in 4,096 dimensions; a genotype at 9,000 sites, a point in 9,000. Lecture 14 showed that such spaces are hostile: distances concentrate and densities cannot be estimated. But real data rarely fill them: faces lie near a much lower-dimensional shape. Dimension reduction describes each point by a few coordinates on that shape.

The linear methods of this lecture look for a flat subspace (a line, plane or higher analogue through the origin) and project each point onto it, like a shadow under an overhead lamp. Lecture 16b follows curved shapes, with Isomap, Laplacian eigenmaps, t-SNE, UMAP and autoencoders.

By the end you should be able to compute principal components by the SVD and prove that maximum variance and minimum reconstruction error agree; use the Eckart–Young theorem; choose a dimension; read a PCA of genotypes and explain its use against confounding; say when probabilistic PCA and factor analysis differ; prove the Johnson–Lindenstrauss lemma; and fit a regularised low-rank model to a sparse ratings matrix.

1 — Principal component analysis

Take the Old Faithful eruptions of Lecture 14 as points (duration, waiting time). Projecting onto a line through the mean replaces two numbers by one. Which line: the one along which the projections spread most, or the one the points are closest to? They are the same line, in any dimension.

definition 16.1 — principal component analysis

Let \(x_1,\dots,x_n\in\mathbb R^d\) have mean \(\bar x\), and let \(X_c\) be the \(n\times d\) matrix with rows \(x_i-\bar x\).

If \(X_c=U\Sigma V^\top\) is the singular value decomposition, then

$$V=(v_1,\dots,v_d),\qquad\lambda_j=\frac{\sigma_j^2}{n-1},\qquad\text{scores}=U\Sigma.$$

The principal directions are the axes of the data cloud, longest first, like the axes of a rugby ball; each eigenvalue is the variance along its axis.

theorem 16.1 — maximum variance and minimum error agree

Let \(W\in\mathbb R^{d\times k}\) have orthonormal columns and let \(P=WW^\top\) be the orthogonal projection onto their span. Then

$$\underbrace{\frac1{n-1}\sum_i\lVert P(x_i-\bar x)\rVert^2}_{\text{variance kept}}+\underbrace{\frac1{n-1}\sum_i\lVert(I-P)(x_i-\bar x)\rVert^2}_{\text{reconstruction error}}=\operatorname{tr}S=\sum_{j=1}^d\lambda_j.$$

Hence maximising the variance kept is the same as minimising the reconstruction error. Both are achieved by the span of \(v_1,\dots,v_k\), with variance kept

$$\lambda_1+\dots+\lambda_k.$$

For each \(i\), the vectors \(P(x_i-\bar x)\) and \((I-P)(x_i-\bar x)\) are orthogonal, so by Pythagoras their squared lengths add to \(\lVert x_i-\bar x\rVert^2\).

Summing and dividing by \(n-1\) gives \(\operatorname{tr}S\), which does not depend on \(W\). This proves the identity, so the two problems have the same solutions.

The variance kept is

$$\frac1{n-1}\sum_i\lVert W^\top(x_i-\bar x)\rVert^2=\operatorname{tr}(W^\top SW).$$

Write \(S=\sum_j\lambda_jv_jv_j^\top\). Then

$$\operatorname{tr}(W^\top SW)=\sum_j\lambda_jc_j,\qquad c_j=\lVert W^\top v_j\rVert^2.$$

Each \(c_j\in[0,1]\), being the squared length of the projection of a unit vector, and \(\sum_jc_j=\operatorname{tr}(WW^\top)=k\).

A sum \(\sum_j\lambda_jc_j\) with weights in \([0,1]\) adding to \(k\) is largest when weight 1 goes to the \(k\) largest \(\lambda_j\). This gives \(\lambda_1+\dots+\lambda_k\), attained by \(W=(v_1,\dots,v_k)\). \(\square\)

Turning the projection line

The 272 Old Faithful eruptions, standardised. Turn the rose line: projected variance plus mean squared distance to the line stays constant (Theorem 16.1). Snap to PC 1 finds the best line.

In practice one uses the SVD of \(X_c\), never \(S\): it is more accurate (forming \(X_c^\top X_c\) squares the condition number), and when \(n<d\), as with faces, it works in the small dimension.

data — Olivetti faces

Ten photographs of each of 40 people, taken between 1992 and 1994 at Olivetti Research Laboratory (later AT&T Laboratories Cambridge), with varying lighting, expression and glasses (the "ORL" or "AT&T" database; Samaria and Harter, 1994). We use Sam Roweis's 64×64-pixel grey-scale version distributed with scikit-learn, from the PNG copy in the GitHub repository lloydmeta/Olivetti-PNG, as scikit-learn's own source was not reachable from the build environment. Images are ordered by person, ten at a time.

code — eigenfaces by the SVD, and Theorem 16.1 numerically
# Eigenfaces: PCA of 400 face images by the singular value decomposition
import numpy as np
from PIL import Image
faces = np.array([np.asarray(Image.open(f'data/olivetti/images/image-{i}.png'), float) / 255 for i in range(400)])
X = faces.reshape(400, -1); n, d = X.shape                 # 400 images of 64 x 64 = 4,096 pixels
mu = X.mean(0); Xc = X - mu
U, s, Vt = np.linalg.svd(Xc, full_matrices=False)          # Xc = U diag(s) Vt; rows of Vt are the eigenfaces
lam = s**2 / (n - 1)                                       # eigenvalues of the sample covariance matrix
print(f"{n} faces x {d} pixels; rank of the centred data {np.sum(s > 1e-8 * s[0])}")
C = Xc.T @ Xc / (n - 1); ev = np.linalg.eigvalsh(C)[::-1]  # the slow way: eigenvalues of the 4096 x 4096 covariance
print(f"top 3 eigenvalues via SVD {np.round(lam[:3], 3)}, via the covariance matrix {np.round(ev[:3], 3)}")
total = lam.sum()
for k in [1, 5, 20, 50, 100, 200]:
    P = Vt[:k]; Z = Xc @ P.T                               # scores on the first k components
    var_kept = (Z**2).sum() / (n - 1); recon = ((Xc - Z @ P)**2).sum() / (n - 1)
    print(f"k = {k:3d}: variance kept {var_kept:7.3f} ({var_kept / total:5.1%}), reconstruction error {recon:7.3f}, "
          f"sum {var_kept + recon:.3f}")
400 faces x 4096 pixels; rank of the centred data 399
top 3 eigenvalues via SVD [26.256 18.063 10.236], via the covariance matrix [26.256 18.063 10.236]
k =   1: variance kept  26.256 (21.3%), reconstruction error  97.252, sum 123.508
k =   5: variance kept  65.510 (53.0%), reconstruction error  57.998, sum 123.508
k =  20: variance kept  93.207 (75.5%), reconstruction error  30.301, sum 123.508
k =  50: variance kept 107.348 (86.9%), reconstruction error  16.160, sum 123.508
k = 100: variance kept 115.182 (93.3%), reconstruction error   8.326, sum 123.508
k = 200: variance kept 120.730 (97.8%), reconstruction error   2.778, sum 123.508
meanPC 1PC 2PC 3PC 4PC 5PC 6PC 7
The mean of the 400 faces and the first seven principal directions ("eigenfaces"). The leading ones capture lighting and head shape; later ones finer features.

The SVD and the 4,096×4,096 covariance give the same eigenvalues (26.256, 18.063, 10.236), and variance kept plus error is 123.508 at every \(k\) (Theorem 16.1). The rank is 399, not 400, because centring removes one dimension. Five components keep 53.0% of the variance, 50 keep 86.9%, 200 keep 97.8%.

k = 5k = 20k = 50k = 150k = 399original
One face rebuilt as \(\bar x+\sum_{j\le k}z_jv_j\). Five components give a generic face with the right lighting, 50 a recognisable person, 399 the exact image.

Rebuilding a face from eigenfaces

Choose a person and \(k\); the right image is the mean face plus the first \(k\) eigenfaces weighted by this face's scores (32×32 pixels, first 100 components).

spot check 16.1

Two-dimensional data have covariance matrix \(\begin{pmatrix}4&0\\0&1\end{pmatrix}\). What fraction of the total variance does the first principal component keep?

The eigenvalues of a diagonal matrix are its diagonal entries.
\(\lambda_1=4\), \(\lambda_2=1\), so the first component (the horizontal axis) keeps \(4/5=0.8\); the mean squared distance to that axis is the other 1.
history — from Pearson's lines to eigenfaces

Karl Pearson posed the minimum-error problem ("lines and planes of closest fit", 1901). Harold Hotelling (1933) gave the maximum-variance version, the name and an iterative method, motivated by psychological test scores. The SVD goes back to Beltrami and Jordan in the 1870s; Golub and Kahan's 1965 algorithm made it practical. Sirovich and Kirby applied PCA to faces in 1987, and Turk and Pentland's "Eigenfaces for recognition" (1991) made it the first widely used face recogniser: project a new face onto the eigenfaces and find the nearest known face.

2 — Choosing the dimension, and PCA of genomes

How many components to keep? A scree plot (Cattell, 1966, after the rubble below a cliff) shows \(\lambda_j\) against \(j\); keep the components before it flattens. The explained variance

$$\frac{\lambda_1+\dots+\lambda_k}{\sum_j\lambda_j}$$

gives a threshold rule (keep 90% or 95%). Whatever \(k\), the PCA reconstruction is the best of its rank, in the Frobenius norm \(\lVert A\rVert_F\) (root sum of squared entries) and the spectral norm \(\lVert A\rVert_2\) (largest stretch of a unit vector).

theorem 16.2 — Eckart–Young

Let \(A\) be an \(n\times d\) matrix with SVD and truncation

$$A=\sum_{j}\sigma_ju_jv_j^\top,\qquad A_k=\sum_{j\le k}\sigma_ju_jv_j^\top,$$

where \(\sigma_1\ge\sigma_2\ge\dots\). Then for every matrix \(B\) of rank at most \(k\),

$$\lVert A-B\rVert_F^2\;\ge\;\lVert A-A_k\rVert_F^2=\sum_{j>k}\sigma_j^2,$$

and the same holds in the spectral norm, with

$$\lVert A-B\rVert_2\;\ge\;\lVert A-A_k\rVert_2=\sigma_{k+1}.$$

(Eckart and Young, 1936; Mirsky, 1960.)

Spectral norm. If \(\operatorname{rank}B\le k\), its null space has dimension at least \(d-k\). So it meets the \((k+1)\)-dimensional span of \(v_1,\dots,v_{k+1}\) in some unit vector \(w\).

Since \(w\) is a combination of the first \(k+1\) right singular vectors,

$$\lVert(A-B)w\rVert=\lVert Aw\rVert\ge\sigma_{k+1}.$$

Hence \(\lVert A-B\rVert_2\ge\sigma_{k+1}=\lVert A-A_k\rVert_2\).

Frobenius norm. Weyl's inequality for singular values gives

$$\sigma_{i+j-1}(A)\le\sigma_i(A-B)+\sigma_j(B).$$

Take \(j=k+1\), where \(\sigma_{k+1}(B)=0\). Then \(\sigma_i(A-B)\ge\sigma_{i+k}(A)\) for every \(i\).

Squaring and summing over \(i\) gives \(\lVert A-B\rVert_F^2\ge\sum_{j>k}\sigma_j^2\). Equality at \(A_k\) follows from orthonormality of the singular vectors. \(\square\)

code — explained variance, and Eckart–Young against a random subspace
# Choosing the dimension, and Eckart-Young: no rank-k matrix approximates the faces better than PCA
cum = np.cumsum(lam) / total
for q in [0.5, 0.8, 0.9, 0.95, 0.99]:
    print(f"components needed for {q:.0%} of the variance: {np.searchsorted(cum, q) + 1}")
rng = np.random.default_rng(0)
for k in [10, 50]:
    Xk = (U[:, :k] * s[:k]) @ Vt[:k]
    err = np.sum((Xc - Xk)**2)
    Q = np.linalg.qr(rng.standard_normal((d, k)))[0]       # a random k-dimensional subspace, for comparison
    err_r = np.sum((Xc - Xc @ Q @ Q.T)**2)
    print(f"rank {k}: ||X - X_k||_F^2 = {err:.2f}; sum of discarded s_i^2 = {np.sum(s[k:]**2):.2f}; "
          f"projection on a random {k}-dim subspace: {err_r:.2f}")
components needed for 50% of the variance: 5
components needed for 80% of the variance: 28
components needed for 90% of the variance: 69
components needed for 95% of the variance: 127
components needed for 99% of the variance: 267
rank 10: ||X - X_k||_F^2 = 17523.60; sum of discarded s_i^2 = 17523.60; projection on a random 10-dim subspace: 49139.88
rank 50: ||X - X_k||_F^2 = 6447.95; sum of discarded s_i^2 = 6447.95; projection on a random 50-dim subspace: 48718.69
0%25%50%75%100%120406080100120cumulative shareshare of each component (×4)number of components
Scree plot for the 400 faces: variance share per component (rose, ×4) and cumulative share (sky). No sharp elbow: the eigenvalues decline smoothly, as for most natural images.

The faces need 5 components for half the variance, 28 for 80%, 69 for 90%, 127 for 95% and 267 for 99%. With no elbow, the choice depends on the purpose. The rank-10 squared error equals the sum of the discarded squared singular values (17,523.60), as Eckart–Young says; a random 10-dimensional subspace leaves 49,139.88, close to the total (see Section 4).

PCA's most consequential application may be in human genetics. A genotype at a single-nucleotide polymorphism (SNP) is the number of copies, 0, 1 or 2, of the less common allele. Allele frequencies differ slightly between populations; each SNP says almost nothing about ancestry, but thousands of small nudges add up, as many slightly biased coin tosses reveal a bias no single toss could.

data — HapMap genotypes (substitute for the 1000 Genomes Project)

Genotypes of 279 people at 9,088 SNPs from Phase II of the International HapMap Project: Yoruba from Ibadan, Nigeria (YRI); Utah residents with northern and western European ancestry (CEU); Han Chinese from Beijing (HCB); and Japanese from Tokyo (JPT). The sample ships with the SNPRelate R package (Zheng et al., 2012; zhengxwen/SNPRelate on GitHub, GPL-3) in GDS format; as R was not available, data/hapmap_from_gds.py extracts the genotypes from the file's bytes, and the code below checks them. The plan called for the 1000 Genomes Project, HapMap's successor, whose files could not be downloaded from the build environment. YRI and CEU were collected as parent–child trios, so some individuals are closely related.

code — PCA of 279 genotypes
# PCA of genotypes: 279 HapMap individuals at 9,088 SNPs (extracted by data/hapmap_from_gds.py)
H = np.load('data/hapmap.npz'); G = H['G'].astype(float); pop = H['pop']
G[G == 3] = np.nan; p = np.nanmean(G, 0) / 2                # allele frequency of each SNP
keep = (p > 0.01) & (p < 0.99)
Gs = (np.where(np.isnan(G), 2 * p, G) - 2 * p)[:, keep] / np.sqrt(2 * p * (1 - p))[keep]   # Patterson et al. (2006)
Ug, sg, Vg = np.linalg.svd(Gs, full_matrices=False); PC = Ug * sg
print(f"{Gs.shape[0]} individuals, {Gs.shape[1]} SNPs after removing near-monomorphic ones; missing genotypes {np.isnan(G).mean():.2%}")
print("variance explained by PCs 1-6:", " ".join(f"{v:.1%}" for v in sg[:6]**2 / np.sum(sg**2)))
for g in ['YRI', 'CEU', 'HCB', 'JPT']:
    m = pop == g; print(f"  {g}: n = {m.sum():2d}, mean PC1 {PC[m, 0].mean():+6.1f}, PC2 {PC[m, 1].mean():+6.1f}, "
                        f"PC3 {PC[m, 2].mean():+6.1f}, PC4 {PC[m, 3].mean():+6.1f}")
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import cross_val_score
for k in [2, 4, 10]:
    acc = cross_val_score(KNeighborsClassifier(5), PC[:, :k], pop, cv=5).mean()
    print(f"5-NN population accuracy from the first {k:2d} PCs (5-fold CV): {acc:.3f}")
ea = np.isin(pop, ['HCB', 'JPT']); Ue = np.linalg.svd(Gs[ea] - Gs[ea].mean(0), full_matrices=False)[0][:, 0]
sep = max(np.mean((Ue > 0) == (pop[ea] == 'JPT')), np.mean((Ue > 0) != (pop[ea] == 'JPT')))
print(f"PCA of the 94 East Asian individuals alone: sign of PC1 separates HCB from JPT for {sep:.1%} of them")
279 individuals, 9039 SNPs after removing near-monomorphic ones; missing genotypes 0.40%
variance explained by PCs 1-6: 12.4% 5.8% 1.0% 0.9% 0.9% 0.7%
  YRI: n = 93, mean PC1  -49.4, PC2   +4.4, PC3   +0.0, PC4   -0.1
  CEU: n = 92, mean PC1  +19.0, PC2  -31.7, PC3   +0.1, PC4   +0.1
  HCB: n = 47, mean PC1  +30.2, PC2  +26.2, PC3   -0.0, PC4   -0.1
  JPT: n = 47, mean PC1  +30.3, PC2  +27.1, PC3   -0.2, PC4   +0.2
5-NN population accuracy from the first  2 PCs (5-fold CV): 0.831
5-NN population accuracy from the first  4 PCs (5-fold CV): 0.885
5-NN population accuracy from the first 10 PCs (5-fold CV): 0.860
PCA of the 94 East Asian individuals alone: sign of PC1 separates HCB from JPT for 96.8% of them

PC 1 (12.4% of the variance) separates the Yoruba from everyone else, and PC 2 (5.8%) Europeans from East Asians: the oldest split, Africa against the rest, comes first. Later components explain about 1% each. Han Chinese and Japanese have almost equal means on the first four, so a nearest-neighbour classifier on them reaches only 88.5% (86.0% with 10). Yet a PCA of the 94 East Asians alone separates them along its first component for 96.8% of people. Variance is not importance.

Genetic space

The 279 individuals on two of their first six PC scores, coloured by population. Try PC 1 against PC 2, then later components, which mix small population differences with trio family structure.

causal — principal components as confounders in genetic association studies

A genome-wide association study (GWAS) tests hundreds of thousands of SNPs against a trait. If the sample mixes populations, a trait that differs between them for non-genetic reasons (diet, healthcare, measurement) is associated with every SNP whose frequency differs. Ancestry causes both: population stratification, a textbook confounder.

The standard remedy (Price et al., 2006, EIGENSTRAT) adds the top genotype PCs as covariates. They estimate the unobserved confounder, and adjusting for them blocks the backdoor path through ancestry. It works because ancestry leaves a strong low-rank signature; it can fail when confounding varies on a finer scale, and modern studies add mixed models with a genetic-relatedness matrix.

spot check 16.2

A matrix has singular values 5, 3 and 1. What is the smallest possible squared Frobenius error \(\lVert A-B\rVert_F^2\) for a matrix \(B\) of rank 1?

Theorem 16.2: the error is the sum of the dropped squared singular values.
\(3^2+1^2=10\), achieved by \(B=\sigma_1u_1v_1^\top\). The total is \(25+9+1=35\), so the best rank-1 approximation keeps \(25/35\approx71\%\) of the squared norm.

3 — Probabilistic PCA and factor analysis

PCA is a procedure, not a model: it gives no probability for a new point, no principled treatment of missing values and no likelihood for comparing dimensions. Probabilistic PCA (Tipping and Bishop, 1999; Roweis, 1998) writes the data as a few latent (hidden) factors seen through fixed weights, the loadings, plus noise; test scores might be explained by two latent abilities, verbal and numerical.

definition 16.2 — probabilistic PCA and factor analysis

Both models generate \(x\in\mathbb R^d\) from a latent vector \(z\in\mathbb R^k\) through a \(d\times k\) loading matrix \(W\):

$$z\sim N(0,I_k),\qquad x=Wz+\mu+\varepsilon.$$

Marginally, the covariance is low rank plus a simple term:

$$x\sim N(\mu,\,WW^\top+\sigma^2I)\qquad\text{or}\qquad x\sim N(\mu,\,WW^\top+\Psi).$$
theorem 16.3 — the probabilistic PCA maximum-likelihood estimate (Tipping and Bishop, 1999)

Let \(S\) have eigenvalues \(\lambda_1\ge\dots\ge\lambda_d\) and eigenvectors \(U=(v_1,\dots,v_d)\). The maximum-likelihood estimates of probabilistic PCA with \(k\) factors are \(\hat\mu=\bar x\) and

$$\hat\sigma^2=\frac1{d-k}\sum_{j>k}\lambda_j,\qquad\hat W=U_k\big(\Lambda_k-\hat\sigma^2I\big)^{1/2}R,$$

So the columns of \(\hat W\) span the PCA subspace, and the noise variance is the average variance in the discarded directions.

(Statement only; the proof sets the derivative of the log-likelihood to zero and analyses its stationary points.)

The likelihood depends on \(W\) only through \(WW^\top\), so factors are identified only up to rotation. (Psychologists, who invented factor analysis to find "general intelligence", spent decades on rotations that make factors nameable.) A likelihood also lets us choose \(k\) on held-out data, as in Lecture 14.

code — held-out likelihood for probabilistic PCA; factor analysis against PCA
# Probabilistic PCA: closed-form maximum likelihood, held-out likelihood to choose k; factor analysis
from sklearn.decomposition import PCA, FactorAnalysis
person = np.repeat(np.arange(40), 10)                      # 10 images of each of 40 people
tr_i, te_i = person < 30, person >= 30                     # hold out 10 people entirely
for k in [5, 20, 50, 100, 200, 250, 290]:
    pp = PCA(k).fit(X[tr_i])                               # PCA.score = average log-likelihood under PPCA
    s2 = pp.noise_variance_
    print(f"PPCA k = {k:3d}: sigma^2 = mean discarded eigenvalue = {s2:.5f}; held-out log-likelihood per face {pp.score(X[te_i]):8.1f}")
# factor analysis vs PCA when the noise is uneven across variables
rng = np.random.default_rng(4); n2 = 2000
Wtrue = rng.normal(size=(10, 2)); Zf = rng.normal(size=(n2, 2))
psi = np.full(10, 0.2); psi[0] = 25.0                      # variable 0 is very noisy
Y = Zf @ Wtrue.T + rng.normal(size=(n2, 10)) * np.sqrt(psi)
def angle(A, B):                                           # largest principal angle between column spaces (degrees)
    qa, qb = np.linalg.qr(A)[0], np.linalg.qr(B)[0]
    return np.degrees(np.arccos(np.clip(np.linalg.svd(qa.T @ qb)[1].min(), -1, 1)))
pc = PCA(2).fit(Y); fa = FactorAnalysis(2, random_state=0).fit(Y)
print(f"uneven noise (variance 25 on one variable, 0.2 on the others): angle to the true 2-D loading space")
print(f"  PCA {angle(pc.components_.T, Wtrue):5.1f} degrees; factor analysis {angle(fa.components_.T, Wtrue):5.1f} degrees; "
      f"FA's estimated noise variances: {fa.noise_variance_[0]:.1f} (variable 0), median of the rest {np.median(fa.noise_variance_[1:]):.2f}")
PPCA k =   5: sigma^2 = mean discarded eigenvalue = 0.18785; held-out log-likelihood per face   -545.9
PPCA k =  20: sigma^2 = mean discarded eigenvalue = 0.09872; held-out log-likelihood per face    691.4
PPCA k =  50: sigma^2 = mean discarded eigenvalue = 0.05617; held-out log-likelihood per face   1725.4
PPCA k = 100: sigma^2 = mean discarded eigenvalue = 0.03280; held-out log-likelihood per face   2641.0
PPCA k = 200: sigma^2 = mean discarded eigenvalue = 0.01477; held-out log-likelihood per face   3806.9
PPCA k = 250: sigma^2 = mean discarded eigenvalue = 0.00952; held-out log-likelihood per face   4287.8
PPCA k = 290: sigma^2 = mean discarded eigenvalue = 0.00505; held-out log-likelihood per face   4624.1
uneven noise (variance 25 on one variable, 0.2 on the others): angle to the true 2-D loading space
  PCA  76.0 degrees; factor analysis   1.2 degrees; FA's estimated noise variances: 25.2 (variable 0), median of the rest 0.20

The fitted noise variance is the mean discarded eigenvalue, falling from 0.188 with 5 factors to 0.005 with 290. On ten held-out people the log-likelihood per face rises all the way to 290 factors, near the maximum 300 training faces allow: face variance decays smoothly over hundreds of directions, not "a few factors plus isotropic noise". A probabilistic model judges dimension only as well as its noise assumption.

With two true factors in ten variables, one carrying 125 times the noise of the others, PCA's first two components are 76.0° from the true loading space: most of the variance is the noisy variable. Factor analysis estimates the noise variances correctly (25.2 and 0.20) and recovers the space to within 1.2°. Use it when variables differ in precision; standardise before PCA when they differ in scale.

Bayes — what the latent-variable view buys

Bayes' rule gives the posterior of the latent factors for each point:

$$p(z\mid x)=N\big(M^{-1}W^\top(x-\mu),\;\sigma^2M^{-1}\big),\qquad M=W^\top W+\sigma^2I.$$

This shrinks the scores towards zero in poorly determined directions. The model fills in missing values by conditional expectation, can be fitted by the EM algorithm of Lecture 17a without forming the \(d\times d\) covariance, and extends to mixtures of PCAs for data that are locally but not globally flat. A prior on \(W\) gives Bayesian PCA (Bishop, 1999), whose automatic relevance determination chooses \(k\) by the evidence. With a neural network as the map from \(z\) to \(x\), the same structure is the variational autoencoder of Lecture 16b.

4 — Random projections and the Johnson–Lindenstrauss lemma

PCA needs an SVD, about \(nd\min(n,d)\) operations. A cruder idea ignores the data: multiply every point by one random \(d\times k\) matrix. A random subspace keeps almost none of the faces' variance (Section 2), yet it keeps all pairwise distances up to a small factor, in a dimension depending only on the number of points.

The reason is concentration (Lecture 14). Each of the \(k\) random weighted sums is a noisy reading of a vector's length, but the average of \(k\) squared readings has relative error about \(1/\sqrt k\). The chance that any of the \(n^2/2\) pairs is badly distorted falls exponentially in \(k\), so \(k\) need grow only like \(\log n\).

theorem 16.4 — Johnson–Lindenstrauss lemma (proof of Dasgupta and Gupta, 2003)

Let \(0<\varepsilon<1\), let \(x_1,\dots,x_n\in\mathbb R^d\), and let

$$k\;\ge\;\frac{4\ln n}{\varepsilon^2/2-\varepsilon^3/3}.$$

Let \(R\) be a \(k\times d\) matrix of independent \(N(0,1/k)\) entries and \(f(x)=Rx\). Then with probability at least \(1/n\), for all pairs \(i,j\),

$$(1-\varepsilon)\lVert x_i-x_j\rVert^2\le\lVert f(x_i)-f(x_j)\rVert^2\le(1+\varepsilon)\lVert x_i-x_j\rVert^2.$$

In particular such a map exists, and repeating the random draw \(O(n)\) times finds one with high probability.

One vector. Fix \(u=x_i-x_j\ne0\). Each coordinate of \(Ru\) is \(N(0,\lVert u\rVert^2/k)\), and the coordinates are independent. So

$$Q=\frac{k\lVert Ru\rVert^2}{\lVert u\rVert^2}\sim\chi^2_k,\qquad\mathbb Ee^{tQ}=(1-2t)^{-k/2}\quad(t<1/2).$$

Upper tail. By Markov's inequality applied to \(e^{tQ}\), for \(0<t<1/2\),

$$P\big(Q\ge(1+\varepsilon)k\big)\le(1-2t)^{-k/2}e^{-t(1+\varepsilon)k}.$$

The choice \(t=\frac{\varepsilon}{2(1+\varepsilon)}\) gives the bound \(\big((1+\varepsilon)e^{-\varepsilon}\big)^{k/2}\). Since \(\ln(1+\varepsilon)\le\varepsilon-\varepsilon^2/2+\varepsilon^3/3\), this is at most

$$\exp\!\big(-\tfrac k2(\varepsilon^2/2-\varepsilon^3/3)\big).$$

Lower tail. The same argument with \(e^{-tQ}\) and \(t=\frac{\varepsilon}{2(1-\varepsilon)}\), using \(\ln(1-\varepsilon)\le-\varepsilon-\varepsilon^2/2\), gives

$$P\big(Q\le(1-\varepsilon)k\big)\le\big((1-\varepsilon)e^{\varepsilon}\big)^{k/2}\le e^{-k\varepsilon^2/4},$$

which is smaller than the upper-tail bound.

All pairs. With \(k\) as stated, the upper-tail bound is at most \(e^{-2\ln n}=n^{-2}\), so each pair fails with probability at most \(2/n^2\).

By the union bound over the \(n(n-1)/2\) pairs, some pair fails with probability at most \((n-1)/n=1-1/n\). \(\square\)

The bound does not involve \(d\). A million points can be embedded in about

$$\frac{4\ln(10^6)}{0.02-0.0027}\approx3{,}200$$

dimensions with every squared distance within 20%, whether they started in ten thousand dimensions or ten billion; a thousand times more points need only about 50% more. The worst-case bound is conservative: far fewer dimensions preserve most distances in practice.

code — random projections of the faces, compared with PCA
# Random projections: Johnson-Lindenstrauss in practice on the 4,096-pixel faces
from scipy.spatial.distance import pdist
D0 = pdist(X, 'sqeuclidean')                               # 79,800 squared distances
rng = np.random.default_rng(5)
print("  k    random projection: ratio of squared distances    PCA to k dims        JL bound on k for")
print("       min     1%     99%     max   share within 20%     min    max            eps = 0.2, n = 400")
for k in [10, 50, 200, 399]:
    R = rng.normal(size=(d, k)) / np.sqrt(k)               # entries N(0, 1/k)  (PCA can use at most 399 dims here)
    r = pdist(X @ R, 'sqeuclidean') / D0
    rp = pdist(Xc @ Vt[:k].T, 'sqeuclidean') / D0
    kb = 4 * np.log(400) / (0.2**2 / 2 - 0.2**3 / 3)
    print(f"{k:4d}   {r.min():.3f}  {np.quantile(r, .01):.3f}  {np.quantile(r, .99):.3f}  {r.max():.3f}   {np.mean(abs(r - 1) < 0.2):6.1%}"
          f"       {rp.min():.3f}  {rp.max():.3f}          {kb:.0f}")
  k    random projection: ratio of squared distances    PCA to k dims        JL bound on k for
       min     1%     99%     max   share within 20%     min    max            eps = 0.2, n = 400
  10   0.062  0.263  2.149  3.690    35.5%       0.021  0.934          1383
  50   0.502  0.679  1.502  1.893    73.7%       0.141  0.977          1383
 200   0.643  0.812  1.239  1.466    96.7%       0.378  0.997          1383
 399   0.746  0.877  1.190  1.319    99.3%       1.000  1.000          1383

For the 400 faces and \(\varepsilon=0.2\) the guarantee needs \(k\ge1383\), a third of the 4,096 dimensions. In practice 200 random dimensions keep 96.7% of the 79,800 squared distances within 20% (worst pair: factor 1.466); 10 are hopeless (ratios from 0.06 to 3.7).

PCA's ratios never exceed 1, since orthogonal projection only shrinks distances, and with 50 components some pairs keep only 14%: two photos of one person differing in fine detail look almost identical. PCA keeps total variance best by sacrificing small distances; random projections treat all pairs alike. Hence their use in nearest-neighbour search, sketching, and randomised linear algebra, where a random projection shrinks a matrix before an exact SVD gives an accurate approximate PCA (Halko, Martinsson and Tropp, 2011).

Projecting 100 faces at random

100 faces (1,024 dimensions) times a Gaussian random matrix with \(k\) columns. The histogram shows the squared-distance ratio for all 4,950 pairs; the green band is \(\pm20\%\). The spread shrinks like \(1/\sqrt k\).

spot check 16.3

You need to embed 10,000 points with all squared distances preserved to within 10%, using the bound of Theorem 16.4. The points currently have 50 dimensions. What should you conclude?

Compute \(4\ln n/(\varepsilon^2/2-\varepsilon^3/3)\) with \(n=10^4\) and \(\varepsilon=0.1\).
\(4\times9.21/(0.005-0.00033)\approx7{,}900\). The lemma helps only when \(d\gg\log n/\varepsilon^2\); here keep the data as they are, or use PCA if distorting small distances is acceptable.

5 — Matrix factorisation for recommendations

A ratings matrix has a row per user, a column per item, and entries almost nowhere; predicting the missing ones is the recommendation problem. Describe each user and item by \(k\) hidden numbers ("how much this user likes action", "how much action this film has") and model a rating as their inner product. A few tastes (action over romance, acclaim over spectacle) explain much of how people rate, so the matrix is roughly low rank.

definition 16.3 — regularised matrix factorisation

Given observed ratings \(r_{ui}\) for pairs \((u,i)\) in a set \(\Omega\), fit a global mean \(\mu\), biases \(b_u,b_i\) and factor vectors \(p_u,q_i\in\mathbb R^k\) by minimising

$$\sum_{(u,i)\in\Omega}\big(r_{ui}-\mu-b_u-b_i-p_u^\top q_i\big)^2+\lambda\Big(\sum_ub_u^2+\sum_ib_i^2+\sum_u\lVert p_u\rVert^2+\sum_i\lVert q_i\rVert^2\Big).$$

Only observed entries enter the loss, unlike an SVD of a filled-in matrix.

Alternating least squares fixes the item parameters and solves a small ridge regression (Lecture 3) for each user, then the reverse, and repeats.

Each half-step is convex with a closed form, so, as in Lloyd's algorithm (Lecture 15), the objective never increases; the whole problem is not convex, since \(p_u^\top q_i\) is a product of unknowns. The penalty is essential: a user with three ratings has \(k+1\) parameters, which would otherwise fit them exactly.

data — MovieLens 100K

100,000 ratings (1 to 5 stars) of 1,682 films by 943 MovieLens users, each with at least 20 ratings, collected by GroupLens at the University of Minnesota between September 1997 and April 1998 (Harper and Konstan, 2015). We use the standard split u1.base/u1.test (80,000 training, 20,000 test ratings) from the copy of the official archive in the GitHub repository rudrasingh21/Data-ML-100k-, as GroupLens's server was not reachable. Research use is permitted under GroupLens's terms.

code — biases and low-rank factors by alternating least squares
# Matrix factorisation on MovieLens 100K: predict held-out ratings from 943 users x 1,682 films
import pandas as pd
cols = ['user', 'item', 'rating', 'ts']
trn = pd.read_csv('data/ml-100k/u1.base', sep='\t', names=cols); tst = pd.read_csv('data/ml-100k/u1.test', sep='\t', names=cols)
titles = pd.read_csv('data/ml-100k/u.item', sep='|', header=None, encoding='latin-1')[1].to_numpy()
nu, ni = 943, 1682; u, i, r = trn.user.values - 1, trn.item.values - 1, trn.rating.values.astype(float)
ut, it, rt = tst.user.values - 1, tst.item.values - 1, tst.rating.values.astype(float)
rmse = lambda pred: np.sqrt(np.mean((pred - rt)**2))
print(f"{len(trn):,} training and {len(tst):,} test ratings; {len(trn) / (nu * ni):.1%} of the matrix is observed")
g = r.mean(); print(f"predict the global mean {g:.2f}: test RMSE {rmse(np.full(len(rt), g)):.4f}")
def als(k, reg, iters=15, seed=0):                         # alternating least squares with user and item biases
    rg = np.random.default_rng(seed); P = 0.1 * rg.normal(size=(nu, k)); Q = 0.1 * rg.normal(size=(ni, k))
    bu = np.zeros(nu); bi = np.zeros(ni)
    byu = [np.flatnonzero(u == a) for a in range(nu)]; byi = [np.flatnonzero(i == b) for b in range(ni)]
    for _ in range(iters):
        for a in range(nu):                                # solve for user a's bias and factors, items fixed
            ix = byu[a]; A = np.c_[np.ones(len(ix)), Q[i[ix]]]
            sol = np.linalg.solve(A.T @ A + reg * np.eye(k + 1), A.T @ (r[ix] - g - bi[i[ix]])); bu[a], P[a] = sol[0], sol[1:]
        for b in range(ni):
            ix = byi[b]
            if len(ix) == 0: continue
            A = np.c_[np.ones(len(ix)), P[u[ix]]]
            sol = np.linalg.solve(A.T @ A + reg * np.eye(k + 1), A.T @ (r[ix] - g - bu[u[ix]])); bi[b], Q[b] = sol[0], sol[1:]
    return bu, bi, P, Q
pred = lambda m: np.clip(g + m[0][ut] + m[1][it] + np.sum(m[2][ut] * m[3][it], 1), 1, 5)
m0 = als(0, 10.0, iters=5); print(f"user and item biases only: test RMSE {rmse(pred(m0)):.4f}")
for k, reg in [(2, 10.0), (10, 10.0), (50, 10.0), (50, 1.0), (50, 30.0)]:
    print(f"biases + rank {k:2d} factors, lambda = {reg:4.1f}: test RMSE {rmse(pred(als(k, reg))):.4f}")
M2 = als(2, 10.0); cnt_i = np.bincount(i, minlength=ni)
pop_i = np.flatnonzero(cnt_i >= 100)
for f in range(2):
    o = pop_i[np.argsort(M2[3][pop_i, f])]
    print(f"factor {f + 1}, low end: {'; '.join(titles[o[:3]])}\n          high end: {'; '.join(titles[o[-3:]])}")
80,000 training and 20,000 test ratings; 5.0% of the matrix is observed
predict the global mean 3.53: test RMSE 1.1537
user and item biases only: test RMSE 0.9598
biases + rank  2 factors, lambda = 10.0: test RMSE 0.9305
biases + rank 10 factors, lambda = 10.0: test RMSE 0.9253
biases + rank 50 factors, lambda = 10.0: test RMSE 0.9328
biases + rank 50 factors, lambda =  1.0: test RMSE 1.1688
biases + rank 50 factors, lambda = 30.0: test RMSE 0.9682
factor 1, low end: Star Wars (1977); Return of the Jedi (1983); Terminator, The (1984)
          high end: Postino, Il (1994); Evita (1996); English Patient, The (1996)
factor 2, low end: Leaving Las Vegas (1995); Dead Man Walking (1995); Boogie Nights (1997)
          high end: Saint, The (1997); Twister (1996); Independence Day (ID4) (1996)

Only 5.0% of the matrix is observed. The global mean (3.53 stars) gives test RMSE 1.1537; user and item biases bring it to 0.9598, most of the gain. Two factors give 0.9305 and ten 0.9253; fifty are slightly worse (0.9328), and the penalty matters (\(\lambda=1\): 1.1688, worse than biases alone; \(\lambda=30\): 0.9682).

The first factor runs from Star Wars, Return of the Jedi and The Terminator to Il Postino, Evita and The English Patient (blockbusters against prestige dramas); the second sets Leaving Las Vegas, Dead Man Walking and Boogie Nights against The Saint, Twister and Independence Day (admired films against mainstream entertainment). Nobody told the model what genres are.

spot check 16.4

How many parameters does the model of Definition 16.3 have for MovieLens 100K with \(k=10\)? (Count the global mean, the biases and the factors.)

There are 943 users and 1,682 films; each has one bias and \(k\) factors.
\(10\times(943+1682)+943+1682+1=28{,}876\), against 80,000 training ratings and 1.59 million cells in the full matrix. The low-rank assumption is what makes the problem possible.
history — the Netflix Prize

In October 2006 Netflix offered US$1 million for beating its recommender, Cinematch, by 10% in RMSE, releasing 100 million ratings by 480,000 customers of 17,770 films. Simon Funk's blog post "Netflix Update: Try This at Home" (December 2006) described regularised matrix factorisation by stochastic gradient descent and took him near the top within weeks; biases, implicit feedback and time effects followed (Koren, Bell and Volinsky, 2009). BellKor's Pragmatic Chaos won in September 2009 with a blend of hundreds of models, submitted 20 minutes before an equally accurate rival. Netflix never deployed the full blend, judging it not worth the engineering cost, and cancelled a second prize in 2010 after the "anonymised" ratings were linked to public IMDb reviews (Narayanan and Shmatikov, 2008) and a privacy lawsuit followed.

quantum — quantum PCA, quantum recommendations, and their dequantisation

Lloyd, Mohseni and Rebentrost (2014) showed that a quantum computer given many copies of a density matrix \(\rho\) can reveal its leading eigenvectors in time polylogarithmic in the dimension. Kerenidis and Prakash (2017) built on this a quantum recommendation algorithm, apparently exponentially faster than any classical method.

In 2018 Ewin Tang, an 18-year-old undergraduate at the University of Texas at Austin working with Scott Aaronson, found a classical algorithm with the same polylogarithmic dependence given the same input access: sampling rows and entries with probability proportional to their squared norms (Tang, STOC 2019). The speed-up came from the input model, not quantum mechanics. "Dequantisation" has since reached quantum PCA and other proposals. The classical versions still have large polynomial overheads, so how much quantum advantage survives is still being studied.

big picture — low rank is everywhere

word2vec implicitly factorises a word co-occurrence matrix (Levy and Goldberg, 2014), and latent semantic analysis (Lecture 12) is an SVD of a term–document matrix. LoRA (Hu et al., 2021) fine-tunes large language models by learning a low-rank update \(\Delta W=BA\) for each frozen weight matrix, often of rank 8 or 16 for matrices with thousands of rows. Vector databases compress embeddings by PCA before indexing. These, compressed sensing, the Gaussian-process approximations of Lecture 7, and genetic PCA covariates rest on one observation: real data matrices have quickly decaying singular values.

6 — Summary, exercises, projects, reading

summary
exercises
  1. Show that the first principal component score \(z_{i1}=v_1^\top(x_i-\bar x)\) is uncorrelated with the second, \(z_{i2}\), across the sample.

    The sample covariance of the two scores is

    $$\frac1{n-1}\sum_iv_1^\top(x_i-\bar x)(x_i-\bar x)^\top v_2=v_1^\top Sv_2=\lambda_2v_1^\top v_2=0.$$

    In general the score vectors are the columns of \(U\Sigma\), which are orthogonal: PCA rotates the data so that the new coordinates are uncorrelated.

  2. Explain why PCA should usually be run on standardised variables when they are measured in different units, using the Old Faithful data (duration in minutes, waiting time in minutes, with standard deviations 1.14 and 13.6) as an example.

    Variance depends on units. Unstandardised, waiting time has about \((13.6/1.14)^2\approx142\) times the variance of duration, so the first component is essentially the waiting-time axis, whatever the correlation.

    After standardising, the first component lies along the strong positive correlation, as in the widget of Section 1. Standardising is a choice too: it treats every variable as equally important.

  3. Show that for a \(1\times d\) data matrix (a single centred point) PCA is undefined, and more generally that with \(n\le d\) points at most \(n-1\) eigenvalues of \(S\) are non-zero. What does this imply for the faces?

    The rows of \(X_c\) sum to zero, so its rank is at most \(n-1\), and \(S=X_c^\top X_c/(n-1)\) has the same rank. With one point, \(X_c=0\).

    For the faces, \(n=400\le d=4096\), so at most 399 eigenvalues are non-zero, as the code found; the other 3,697 directions carry no variance in the sample, and PCA can say nothing about them.

  4. In the proof of Theorem 16.4, verify that the choice \(t=\varepsilon/(2(1+\varepsilon))\) turns \((1-2t)^{-k/2}e^{-t(1+\varepsilon)k}\) into \(\big((1+\varepsilon)e^{-\varepsilon}\big)^{k/2}\).

    With this \(t\), \(1-2t=1-\varepsilon/(1+\varepsilon)=1/(1+\varepsilon)\), so

    $$(1-2t)^{-k/2}=(1+\varepsilon)^{k/2}.$$

    Also \(t(1+\varepsilon)k=\varepsilon k/2\), so \(e^{-t(1+\varepsilon)k}=e^{-\varepsilon k/2}\). The product is \(\big((1+\varepsilon)e^{-\varepsilon}\big)^{k/2}\). (This \(t\) minimises the bound over \(t\).)

  5. A user has rated a single film. In Definition 16.3 with \(k\) factors, what happens to that user's bias and factor vector as \(\lambda\to0\), and what as \(\lambda\to\infty\)? Why is cross-validating \(\lambda\) essential?

    As \(\lambda\to0\), \(k+1\) parameters face one equation, so infinitely many fit exactly; ALS picks one arbitrarily and predictions for the user's other films are meaningless (the overfitting seen at \(\lambda=1\)).

    As \(\lambda\to\infty\), bias and factors shrink to zero and predictions become \(\mu+b_i\), the item's average appeal.

    The best \(\lambda\) lies between and is chosen on held-out ratings (\(\lambda=10\) beat 1 and 30).

  6. (Code.) Run PCA on the HapMap data without the standardisation by \(\sqrt{2p(1-p)}\), using only centring. Does the picture change? Which SNPs gain influence?

    Replace Gs by the centred genotypes without dividing. The main picture (Africa, Europe, East Asia) is unchanged, because it is carried by thousands of SNPs.

    Without standardisation, SNPs with intermediate frequencies (\(p\) near 0.5, where \(2p(1-p)\) is largest) weigh more and rare variants less. Patterson et al.'s scaling gives each SNP equal weight, assuming independent drift, which emphasises rarer variants that often differ more sharply between populations.

student projects

Each project uses this lecture's methods and public data, and has a clear result.

1. Principal components of New York's census tracts

question
What are the main axes of variation among New York City's 2,300 census tracts, and do they line up with the city's official neighbourhood typologies?
data
American Community Survey 5-year estimates by tract (income, rent burden, education, age, household size, commuting mode, language, housing age); NYC Neighborhood Tabulation Areas and Community District profiles (NYC Department of City Planning).
method
Standardised PCA with bootstrap confidence intervals for the loadings; factor analysis with rotations for interpretability; maps of the leading scores; comparison of score distributions across official neighbourhood types.
outcome
Named, mapped axes of the city's social geography (for example an income–education axis and a household-composition axis), with an honest account of how stable each is.

2. How many dimensions do recommendations need?

question
How does recommendation accuracy depend on the rank and on the amount of data per user, and do the factors mean anything stable?
data
MovieLens 1M or 25M (GroupLens), or a public Goodreads or music-listening data set.
method
ALS and stochastic-gradient matrix factorisation with biases; cross-validated rank and penalty; accuracy for users grouped by number of ratings; stability of the leading factors across random restarts (principal angles) and their correlation with genre tags.
outcome
A learning curve for "cold" and "warm" users and an assessment of whether the factors are genuine structure or artefacts of the fit.

Reading and sources

Data. Olivetti faces: AT&T Laboratories Cambridge, 64×64 version distributed with scikit-learn, PNG copy from github.com/lloydmeta/Olivetti-PNG. HapMap Phase II genotypes (279 individuals, 9,088 SNPs): sample shipped with SNPRelate, github.com/zhengxwen/SNPRelate (GPL-3), extracted by data/hapmap_from_gds.py; used in place of the 1000 Genomes Project, which could not be downloaded. MovieLens 100K: GroupLens, University of Minnesota, copy from github.com/rudrasingh21/Data-ML-100k-. Old Faithful: R datasets::faithful, as in Lecture 14.

continued in Lecture 16b: nonlinear methods  |  numbers in the text not printed by a code box are computed in verify_L16a.py, figures and widget data in figs_L16a.py; code-box outputs are pasted from actual runs (numpy, SciPy and scikit-learn on one CPU core)