Part IV · Unsupervised learning | MDS, Isomap, Laplacian eigenmaps, t-SNE and UMAP, a single-cell pipeline, autoencoders, VAEs and the ELBO | reading: van der Maaten & Hinton (2008); McInnes, Healy & Melville (2018); Kingma & Welling (2014); Prince, Understanding Deep Learning (2023), ch. 17 | linear methods are in Lecture 16a
Lecture 16a looked for flat subspaces. Many data sets lie near curved shapes instead (cells along a developmental trajectory, digits that morph into one another), where straight-line distance misleads, as the cartoon's ant and bird disagree. This lecture follows the shape: with neighbour graphs (Isomap, Laplacian eigenmaps), with t-SNE and UMAP, in a single-cell analysis, and with autoencoders and variational autoencoders.
Goals: show classical MDS is PCA for Euclidean distances; explain how Isomap and Laplacian eigenmaps use a neighbour graph and fail; state the t-SNE objective and what t-SNE and UMAP plots do not show; run a single-cell pipeline; relate linear autoencoders to PCA; derive the evidence lower bound and the reparameterisation trick.
Given only a table of distances between cities, multidimensional scaling (MDS) draws the map: low-dimensional points whose distances match the table.
Let \(D=(d_{ij})\) be an \(n\times n\) distance matrix and \(D^{(2)}=(d_{ij}^2)\). With the centring matrix \(J=I-\frac1n\mathbf 1\mathbf 1^\top\), form
$$B=-\tfrac12JD^{(2)}J.$$Classical MDS (Torgerson, 1952). Take the top \(k\) eigenvalues \(\mu_1\ge\dots\ge\mu_k\) of \(B\), with eigenvectors \(e_j\), and place point \(i\) at
$$y_i=\big(\sqrt{\mu_1}\,e_{1i},\dots,\sqrt{\mu_k}\,e_{ki}\big).$$Metric MDS. Minimise the stress by iterative optimisation:
$$\sum_{i<j}\big(d_{ij}-\lVert y_i-y_j\rVert\big)^2.$$Let \(d_{ij}=\lVert x_i-x_j\rVert\) for points \(x_i\in\mathbb R^d\) with centred data matrix \(X_c\). Then
$$B=X_cX_c^\top,$$and the classical MDS coordinates are the principal component scores, up to the sign of each coordinate.
Distances are invariant under translation, so assume \(\sum_ix_i=0\), i.e. \(X=X_c\).
Expanding \(d_{ij}^2=\lVert x_i\rVert^2+\lVert x_j\rVert^2-2x_i^\top x_j\) gives, with \(a_i=\lVert x_i\rVert^2\),
$$D^{(2)}=a\mathbf 1^\top+\mathbf 1a^\top-2X_cX_c^\top.$$Since \(J\mathbf 1=0\), the first two terms vanish under \(J\cdot J\); and \(JX_c=X_c\) because the columns of \(X_c\) have mean zero. Hence
$$B=-\tfrac12J\big(-2X_cX_c^\top\big)J=X_cX_c^\top.$$With the SVD \(X_c=U\Sigma V^\top\),
$$B=U\Sigma^2U^\top,$$so the eigenvectors are the columns of \(U\) and the eigenvalues are \(\sigma_j^2\). Thus \(\sqrt{\mu_j}e_j=\sigma_ju_j\), the \(j\)-th column of \(U\Sigma\), which is the \(j\)-th PC score (Definition 16.1). \(\square\)
So classical MDS adds nothing for Euclidean distances; its power is that \(D\) can be any dissimilarity. A manifold is a smooth surface that looks flat up close, like the Swiss roll below; a geodesic is the shortest path on it, the ant's route. Isomap (Tenenbaum, de Silva and Langford, 2000) estimates geodesics by hopping between near neighbours and feeds them to MDS. Laplacian eigenmaps (Belkin and Niyogi, 2003) ask only that neighbours stay close, using the graph Laplacian of Lectures 9 and 15.
Both start from a graph joining each point to its \(k\) nearest neighbours.
Isomap. Weight edges by Euclidean length, estimate geodesic distances by shortest paths in the graph, and apply classical MDS.
Laplacian eigenmaps. Give the edges weights \(w_{ij}\), for example 1 or \(e^{-\lVert x_i-x_j\rVert^2/t}\). With \(L=D-W\) the graph Laplacian, choose \(y_1,\dots,y_n\in\mathbb R^k\) to minimise
$$\sum_{i,j}w_{ij}\lVert y_i-y_j\rVert^2=2\operatorname{tr}(Y^\top LY)\qquad\text{subject to }Y^\top DY=I,\;Y^\top D\mathbf 1=0.$$The solution is given by the generalised eigenvectors
$$Lf=\lambda Df$$with the 2nd to \((k+1)\)-th smallest eigenvalues: the eigenproblem of spectral clustering (Lecture 15, Theorem 15.4).
# The Swiss roll: PCA and classical MDS flatten it badly, Isomap and Laplacian eigenmaps unroll it import numpy as np, time from sklearn.datasets import make_swiss_roll from sklearn.decomposition import PCA from sklearn.manifold import Isomap, SpectralEmbedding, trustworthiness from scipy.stats import spearmanr from scipy.spatial.distance import pdist, squareform Xs, ts = make_swiss_roll(1500, noise=0.3, random_state=0) # 3-D points; ts = position along the roll def cmds(D, k=2): # classical MDS (Definition 16.4) n = len(D); J = np.eye(n) - 1 / n; B = -0.5 * J @ (D**2) @ J w, V = np.linalg.eigh(B); o = np.argsort(w)[::-1][:k] return V[:, o] * np.sqrt(np.maximum(w[o], 0)) emb_s = {'PCA': PCA(2).fit_transform(Xs), 'classical MDS': cmds(squareform(pdist(Xs)))} print(f"PCA and classical MDS on Euclidean distances agree: max |difference| of |coordinates| " f"{np.abs(np.abs(emb_s['PCA']) - np.abs(emb_s['classical MDS'])).max():.2e} (Theorem 16.5)") for nn in [10, 30]: emb_s[f'Isomap, {nn} neighbours'] = Isomap(n_neighbors=nn).fit_transform(Xs) emb_s['Laplacian eigenmaps, 10 neighbours'] = SpectralEmbedding(2, n_neighbors=10, random_state=0).fit_transform(Xs) for name, E in emb_s.items(): rho = max(abs(spearmanr(E[:, 0], ts)[0]), abs(spearmanr(E[:, 1], ts)[0])) print(f"{name:35s} |Spearman| of a coordinate with roll position {rho:.3f}; trustworthiness (10-NN) " f"{trustworthiness(Xs, E, n_neighbors=10):.3f}")
PCA and classical MDS on Euclidean distances agree: max |difference| of |coordinates| 1.05e-13 (Theorem 16.5) PCA |Spearman| of a coordinate with roll position 0.212; trustworthiness (10-NN) 0.962 classical MDS |Spearman| of a coordinate with roll position 0.212; trustworthiness (10-NN) 0.962 Isomap, 10 neighbours |Spearman| of a coordinate with roll position 1.000; trustworthiness (10-NN) 0.999 Isomap, 30 neighbours |Spearman| of a coordinate with roll position 0.666; trustworthiness (10-NN) 0.961 Laplacian eigenmaps, 10 neighbours |Spearman| of a coordinate with roll position 0.999; trustworthiness (10-NN) 0.902
PCA and classical MDS agree to rounding error (\(10^{-13}\)) and neither unrolls the roll: the best coordinate has rank correlation 0.212 with position along it. Isomap with 10 neighbours gives 1.000, Laplacian eigenmaps 0.999. Trustworthiness (Venna and Kaski, 2001), whether embedding neighbours were original neighbours, is high for all (0.90–1.00), so it says little about global shape. The fragility is in the graph: with 30 neighbours, edges jump between layers and Isomap drops to 0.666.
Isomap is run on data near a curved surface, with a few outliers scattered between the folds. What is the most likely failure?
Keeping all distances in two dimensions is usually impossible. Stochastic neighbour embedding (Hinton and Roweis, 2002) keeps only who is near whom, as probabilities, like seating each party guest near their closest friends; t-SNE (van der Maaten and Hinton, 2008) made it work.
For each point \(i\), define conditional probabilities over the other points:
$$p_{j\mid i}=\frac{\exp(-\lVert x_i-x_j\rVert^2/2\sigma_i^2)}{\sum_{l\ne i}\exp(-\lVert x_i-x_l\rVert^2/2\sigma_i^2)}.$$Choose \(\sigma_i\) so that the perplexity \(2^{H(p_{\cdot\mid i})}\), with \(H\) the entropy in bits, equals a chosen value (typically 5–50). It is roughly the effective number of neighbours.
Symmetrise:
$$p_{ij}=\frac{p_{j\mid i}+p_{i\mid j}}{2n}.$$In the embedding, use a Student-t kernel with one degree of freedom:
$$q_{ij}=\frac{(1+\lVert y_i-y_j\rVert^2)^{-1}}{\sum_{k\ne l}(1+\lVert y_k-y_l\rVert^2)^{-1}}.$$Choose \(y_1,\dots,y_n\in\mathbb R^2\) to minimise, by gradient descent,
$$\mathrm{KL}(P\Vert Q)=\sum_{i\ne j}p_{ij}\log\frac{p_{ij}}{q_{ij}}.$$UMAP (McInnes, Healy and Melville, 2018) builds a similar weighted \(k\)-nearest-neighbour graph, with kernel and normalisation from a topological argument, and optimises a cross-entropy between neighbour graphs by negative sampling. It behaves much like t-SNE, is faster on large data, and tends to keep more large-scale arrangement.
Two design choices explain t-SNE's pictures. The KL divergence punishes placing near neighbours (large \(p_{ij}\)) far apart (small \(q_{ij}\)) but barely the reverse, so neighbourhoods are kept and global distances are not. The heavy-tailed Student-t kernel relieves the crowding problem (two dimensions lack room for all points moderately close in fifty) and opens gaps between clusters.
Handwritten digits, 28×28 pixels with grey levels in [0, 1], from the MNIST database (LeCun, Cortes and Burges, 1998), in the 50,000/10,000/10,000 split of Michael Nielsen's mnist.pkl.gz (GitHub mnielsen/neural-networks-and-deep-learning). The embeddings use a random 5,000 training digits; the autoencoders of Section 4 use all 50,000.
# MNIST in two dimensions: PCA, t-SNE and UMAP import gzip, pickle, warnings from sklearn.manifold import TSNE from sklearn.neighbors import KNeighborsClassifier from sklearn.model_selection import cross_val_score import umap warnings.filterwarnings('ignore') with gzip.open('data/mnist.pkl.gz') as f: (Xtr, ytr), (Xva, yva), (Xte, yte) = pickle.load(f, encoding='latin1') rng = np.random.default_rng(0); sel = rng.choice(len(Xtr), 5000, replace=False) Xm, ym = Xtr[sel], ytr[sel] # 5,000 training digits, 784 pixels each P50 = PCA(50, random_state=0).fit_transform(Xm) # all three start from 50 principal components emb_m = {}; tm = {} t0 = time.time(); emb_m['PCA'] = P50[:, :2]; tm['PCA'] = time.time() - t0 t0 = time.time(); emb_m['t-SNE'] = TSNE(2, perplexity=30, init='pca', random_state=0).fit_transform(P50); tm['t-SNE'] = time.time() - t0 t0 = time.time(); emb_m['UMAP'] = umap.UMAP(n_neighbors=15, min_dist=0.1, random_state=0).fit_transform(P50); tm['UMAP'] = time.time() - t0 knn = lambda E: cross_val_score(KNeighborsClassifier(10), E, ym, cv=5).mean() print(f"10-NN digit accuracy in the original 784 pixels: {knn(Xm):.3f}; in 50 PCs: {knn(P50):.3f}") D50 = pdist(P50) for nm, E in emb_m.items(): print(f"{nm:6s} ({tm[nm]:5.1f} s): 10-NN accuracy in 2-D {knn(E):.3f}; trustworthiness {trustworthiness(P50, E, n_neighbors=10):.3f}; " f"Spearman correlation of all pairwise distances with those in 50-D {spearmanr(pdist(E), D50)[0]:.3f}")
10-NN digit accuracy in the original 784 pixels: 0.923; in 50 PCs: 0.934 PCA ( 0.0 s): 10-NN accuracy in 2-D 0.413; trustworthiness 0.745; Spearman correlation of all pairwise distances with those in 50-D 0.554 t-SNE ( 29.4 s): 10-NN accuracy in 2-D 0.931; trustworthiness 0.985; Spearman correlation of all pairwise distances with those in 50-D 0.430 UMAP ( 26.8 s): 10-NN accuracy in 2-D 0.935; trustworthiness 0.966; Spearman correlation of all pairwise distances with those in 50-D 0.366
t-SNE and UMAP keep almost all the nearest-neighbour label information: accuracy 0.931 and 0.935, against 0.934 in the 50 principal components they start from and 0.413 for two PCs. Trustworthiness is 0.985 and 0.966, against PCA's 0.745. But on the rank correlation of all 12.5 million pairwise distances, PCA does best (0.554) and UMAP worst (0.366). The islands are right; the sea between them is not to scale.
# How t-SNE and UMAP mislead: cluster sizes, gaps between clusters, and clusters in pure noise rb = np.random.default_rng(3) A = rb.normal(0, 1, (300, 50)); Bc = rb.normal(0, 10, (300, 50)) + np.r_[60, np.zeros(49)] Cc = rb.normal(0, 1, (300, 50)) + np.r_[300, np.zeros(49)] # A and C tight (sd 1), B wide (sd 10) Xb = np.vstack([A, Bc, Cc]); yb = np.repeat([0, 1, 2], 300) cent = lambda E: [E[yb == j].mean(0) for j in range(3)] spread = lambda E: [np.sqrt(((E[yb == j] - E[yb == j].mean(0))**2).sum(1).mean()) for j in range(3)] for nm, E in [('original 50-D', Xb), ('t-SNE, perplexity 30', TSNE(2, perplexity=30, random_state=0).fit_transform(Xb)), ('UMAP, 15 neighbours', umap.UMAP(random_state=0).fit_transform(Xb))]: c = cent(E); sp = spread(E) print(f"{nm:22s} cluster spreads A, B, C: {sp[0]:6.1f} {sp[1]:6.1f} {sp[2]:6.1f} ratio B/A {sp[1] / sp[0]:5.1f} " f"gap A-B {np.linalg.norm(c[0] - c[1]):6.1f}, gap B-C {np.linalg.norm(c[1] - c[2]):6.1f}, ratio {np.linalg.norm(c[1] - c[2]) / np.linalg.norm(c[0] - c[1]):4.1f}") noise = rb.normal(size=(500, 50)) for perp in [2, 30]: E = TSNE(2, perplexity=perp, random_state=0).fit_transform(noise) from sklearn.cluster import DBSCAN nn5 = np.sort(squareform(pdist(E)), 1)[:, 5]; lab = DBSCAN(eps=np.median(nn5) * 1.5, min_samples=5).fit_predict(E) print(f"pure Gaussian noise (500 points, 50-D), t-SNE perplexity {perp:2d}: DBSCAN finds {len(set(lab) - {-1})} 'clusters'")
original 50-D cluster spreads A, B, C: 7.0 69.9 7.1 ratio B/A 9.9 gap A-B 60.2, gap B-C 240.0, ratio 4.0 t-SNE, perplexity 30 cluster spreads A, B, C: 5.4 6.2 5.4 ratio B/A 1.2 gap A-B 18.3, gap B-C 58.2, ratio 3.2 UMAP, 15 neighbours cluster spreads A, B, C: 0.8 1.0 0.8 ratio B/A 1.2 gap A-B 4.1, gap B-C 16.1, ratio 3.9 pure Gaussian noise (500 points, 50-D), t-SNE perplexity 2: DBSCAN finds 22 'clusters' pure Gaussian noise (500 points, 50-D), t-SNE perplexity 30: DBSCAN finds 1 'clusters'
Three Gaussian clusters in 50 dimensions have spreads 7.0, 69.9 and 7.1 (B ten times A and C), with C four times as far from B as A is. Both methods draw them at nearly equal size (B 1.2 times as wide as A), because every neighbourhood is normalised to a fixed effective size. The gap ratio is roughly kept (3.2 and 3.9 against 4.0), helped by PCA initialisation for t-SNE and spectral initialisation for UMAP, but not reliably across perplexities and seeds. And 500 points of pure noise give 22 "clusters" at perplexity 2 (one blob at 30). Wattenberg, Viégas and Johnson's "How to use t-SNE effectively" (Distill, 2016) collects many more cases.
Point \(i\)'s conditional distribution \(p_{\cdot\mid i}\) puts equal probability on exactly 30 neighbours and none on the rest. What is its perplexity?
In a UMAP plot of patients' gene expression, cluster X looks twice as large as Y and twice as far from Z as from W. What does the plot alone support?
Warren Torgerson's classical scaling (1952) came from psychophysics, Joseph Kruskal's stress-based MDS (1964) from Bell Labs. The 22 December 2000 issue of Science launched "manifold learning" with Isomap (Joshua Tenenbaum, Vin de Silva, John Langford) and locally linear embedding (Sam Roweis, Lawrence Saul); Laplacian eigenmaps (Mikhail Belkin, Partha Niyogi) followed in 2003. Stochastic neighbour embedding (Geoffrey Hinton, Roweis, 2002) became t-SNE (Laurens van der Maaten, Hinton, 2008), later sped up by Barnes–Hut and FFT approximations. UMAP (Leland McInnes, John Healy, James Melville, 2018) soon became the standard figure of single-cell biology, and a target of sharp criticism for how easily it is over-read (Chari and Pachter, PLoS Computational Biology, 2023).
Single-cell RNA sequencing counts, in each of thousands of cells, the messenger RNA molecules from each of about 30,000 genes. Each cell type switches on different genes, so the counts fingerprint a cell's type (T cell, B cell, monocyte) and state. The data are high-dimensional, sparse and noisy, and the types are unknown: an unsupervised problem solved by a standard recipe combining Lectures 15 and 16. A marker gene is switched on strongly in one cell type (MS4A1 in B cells) and serves as a label.
2,700 peripheral blood mononuclear cells from a healthy donor, sequenced with 10x Genomics' Chromium technology and released as a free demonstration data set ("3k PBMCs from a Healthy Donor", 2016): counts for 32,738 genes, the data of the Seurat and Scanpy tutorials. We use the raw counts pbmc3k_raw.h5ad from GitHub munaberhe/pbmc3k-analysis, because 10x Genomics' site was not reachable, and follow the Scanpy tutorial (Wolf, Angerer and Theis, 2018).
# Single-cell RNA-seq: 2,700 blood cells, from raw counts to PCA, a neighbour graph, clusters and UMAP import warnings; warnings.filterwarnings("ignore") import numpy as np import scanpy as sc, anndata as ad, pandas as pd sc.settings.verbosity = 0 pb = ad.read_h5ad('data/pbmc3k_raw.h5ad'); pb.var_names_make_unique() pb.var['mt'] = pb.var_names.str.startswith('MT-') sc.pp.filter_cells(pb, min_genes=200); sc.pp.filter_genes(pb, min_cells=3) sc.pp.calculate_qc_metrics(pb, qc_vars=['mt'], inplace=True, percent_top=None, log1p=False) pb = pb[(pb.obs.n_genes_by_counts < 2500) & (pb.obs.pct_counts_mt < 5)].copy() # quality control as in the Seurat tutorial print(f"after quality control: {pb.n_obs} cells x {pb.n_vars} genes; {pb.X.nnz / np.prod(pb.shape):.1%} of entries non-zero") pb.raw = sc.pp.log1p(sc.pp.normalize_total(pb, target_sum=1e4, copy=True), copy=True) sc.pp.normalize_total(pb, target_sum=1e4); sc.pp.log1p(pb) sc.pp.highly_variable_genes(pb, min_mean=0.0125, max_mean=3, min_disp=0.5); pb = pb[:, pb.var.highly_variable].copy() sc.pp.scale(pb, max_value=10); sc.tl.pca(pb, n_comps=50, random_state=0) vr = pb.uns['pca']['variance_ratio'] print(f"{pb.n_vars} highly variable genes; first 10 PCs explain {vr[:10].sum():.1%} of their variance (PC1 {vr[0]:.1%})") sc.pp.neighbors(pb, n_neighbors=10, n_pcs=40, random_state=0) sc.tl.leiden(pb, resolution=1.0, random_state=0, flavor='igraph', n_iterations=2, directed=False) sc.tl.umap(pb, random_state=0) markers = {'CD4 T': ['IL7R', 'CCR7'], 'CD8 T': ['CD8A'], 'NK': ['GNLY', 'NKG7'], 'B': ['MS4A1', 'CD79A'], 'CD14 monocyte': ['CD14', 'LYZ'], 'FCGR3A monocyte': ['FCGR3A', 'MS4A7'], 'dendritic': ['FCER1A', 'CST3'], 'platelet': ['PPBP']} expr = pd.DataFrame(pb.raw[:, sum(markers.values(), [])].X.toarray(), columns=sum(markers.values(), []), index=pb.obs_names) z = (expr - expr.mean()) / expr.std(); score = pd.DataFrame({t: z[g].mean(1) for t, g in markers.items()}) for cl in sorted(pb.obs.leiden.unique(), key=int): m = (pb.obs.leiden == cl).to_numpy(); top = score[m].mean().sort_values(ascending=False) print(f"cluster {cl:>2s}: {m.sum():4d} cells; marker score highest for {top.index[0]:16s} ({top.iloc[0]:.2f}), next {top.index[1]} ({top.iloc[1]:.2f})")
after quality control: 2638 cells x 13714 genes; 6.2% of entries non-zero 1838 highly variable genes; first 10 PCs explain 6.8% of their variance (PC1 2.2%) cluster 0: 641 cells; marker score highest for CD4 T (0.45), next platelet (-0.10) cluster 1: 275 cells; marker score highest for CD8 T (1.32), next NK (0.93) cluster 2: 163 cells; marker score highest for NK (2.73), next FCGR3A monocyte (0.69) cluster 3: 532 cells; marker score highest for CD4 T (0.49), next CD8 T (0.08) cluster 4: 339 cells; marker score highest for B (2.21), next platelet (-0.08) cluster 5: 211 cells; marker score highest for FCGR3A monocyte (1.94), next dendritic (0.72) cluster 6: 427 cells; marker score highest for CD14 monocyte (1.62), next dendritic (0.72) cluster 7: 37 cells; marker score highest for dendritic (3.97), next CD14 monocyte (0.76) cluster 8: 13 cells; marker score highest for platelet (11.45), next dendritic (0.13)
Quality control removes 62 cells with too few or too many genes, or too much mitochondrial RNA (a sign of damage). Counts are scaled to 10,000 per cell and logged, and 1,838 highly variable genes kept. PCA (Lecture 16a) gives 50 components, which explain little variance (6.8% in the first ten) but carry the cell-type structure; the rest is mostly sampling noise. A 10-nearest-neighbour graph on 40 components is split into nine clusters by the Leiden algorithm (Traag, Waltman and van Eck, 2019), a modularity-based community detection method related to spectral clustering, and UMAP draws the same graph. Marker genes recover the tutorials' cell types: two CD4 T clusters (641 and 532 cells; the tutorials label theirs naive and memory), CD8 T, NK, B cells, CD14 and FCGR3A monocytes, 37 dendritic cells and 13 platelets.
The clusters come from the graph on 40 components; UMAP only displays them. Their number is set by the Leiden resolution: at 0.5 instead of 1.0 there are six, merging CD8 T with NK cells and the two monocyte types. The labels come from marker genes, the external check Lecture 14 called for.
The methods so far embed the given points but give no formula for new ones and no way back to data. An autoencoder learns both maps with neural networks (Lecture 10): an encoder squeezes each input through a narrow code, a decoder rebuilds it, and the bottleneck forces it to keep the most useful information.
An autoencoder is a pair of maps, with \(k<d\):
They are trained to minimise the reconstruction error
$$\sum_i\big\lVert x_i-g_\theta(f_\phi(x_i))\big\rVert^2.$$The code \(z=f_\phi(x)\) is the low-dimensional representation. If both maps are linear, it is a linear autoencoder.
Consider a linear autoencoder with \(k\) hidden units, trained by squared error on centred data whose covariance has distinct eigenvalues. Then:
The hidden units need not be the principal components themselves: any invertible mixing gives the same reconstruction. (Statement.)
A linear autoencoder is PCA reached by gradient descent, and the absence of local minima is why training works. Nonlinear maps can follow curved shapes.
# Autoencoders in JAX: a linear autoencoder finds the PCA subspace; nonlinear ones do better at low dimension import jax, jax.numpy as jnp def adam_step(loss): @jax.jit def step(p, m, v, t, x, key): L, g = jax.value_and_grad(loss)(p, x, key) m = jax.tree.map(lambda m, g: 0.9 * m + 0.1 * g, m, g); v = jax.tree.map(lambda v, g: 0.999 * v + 0.001 * g * g, v, g) p = jax.tree.map(lambda p, m, v: p - 1e-3 * (m / (1 - 0.9**t)) / (jnp.sqrt(v / (1 - 0.999**t)) + 1e-8), p, m, v) return p, m, v, L return step def train(loss, p, steps=3000, B=256, seed=0): step = adam_step(loss); m = jax.tree.map(jnp.zeros_like, p); v = jax.tree.map(jnp.zeros_like, p) key = jax.random.PRNGKey(seed); Xj = jnp.asarray(Xtr) for t in range(1, steps + 1): key, k1, k2 = jax.random.split(key, 3) p, m, v, L = step(p, m, v, t, Xj[jax.random.randint(k1, (B,), 0, len(Xtr))], k2) return p def dense(key, a, b): return {'W': jax.random.normal(key, (a, b)) * np.sqrt(2 / a), 'b': jnp.zeros(b)} def init_ae(k, hidden, seed=0): ks = jax.random.split(jax.random.PRNGKey(seed), 4) if hidden == 0: return {'e': [dense(ks[0], 784, k)], 'd': [dense(ks[1], k, 784)]} return {'e': [dense(ks[0], 784, hidden), dense(ks[1], hidden, k)], 'd': [dense(ks[2], k, hidden), dense(ks[3], hidden, 784)]} def mlp(layers, h, last=None): for j, l in enumerate(layers): h = h @ l['W'] + l['b'] if j < len(layers) - 1: h = jax.nn.relu(h) return h if last is None else last(h) def ae_loss(p, x, key): return jnp.mean(jnp.sum((mlp(p['d'], mlp(p['e'], x)) - x) ** 2, 1)) mse_test = lambda rec: float(np.mean(np.sum((rec - Xte) ** 2, 1))) pca_full = PCA(50, random_state=0).fit(Xtr) t0 = time.time() for k in [2, 16]: pc = PCA(k, random_state=0).fit(Xtr); print(f"PCA, {k:2d} components: test squared error per image {mse_test(pc.inverse_transform(pc.transform(Xte))):.2f}") if k == 16: lin = train(ae_loss, init_ae(16, 0), steps=12000) # cheap: no hidden layer rec = np.asarray(mlp(lin['d'], mlp(lin['e'], jnp.asarray(Xte)))) Wd = np.asarray(lin['d'][0]['W']).T # decoder columns span the learned subspace qa, qb = np.linalg.qr(Wd)[0], np.linalg.qr(pc.components_.T)[0] ang = np.degrees(np.arccos(np.clip(np.linalg.svd(qa.T @ qb)[1], -1, 1))) print(f" linear autoencoder, 16 units: test error {mse_test(rec):.2f}; principal angles to the PCA subspace: " f"median {np.median(ang):.1f} deg, largest {ang.max():.1f} deg (Theorem 16.7)") ae = train(ae_loss, init_ae(k, 256)); globals()[f'ae{k}'] = ae print(f" nonlinear autoencoder 784-256-{k}-256-784: test error {mse_test(np.asarray(mlp(ae['d'], mlp(ae['e'], jnp.asarray(Xte))))):.2f}") Z_ae = np.asarray(mlp(ae2['e'], jnp.asarray(Xm))) print(f"10-NN accuracy of the 5,000 digits in the 2-D autoencoder code: {knn(Z_ae):.3f} ({time.time() - t0:.0f} s for all training)")
PCA, 2 components: test squared error per image 43.30 nonlinear autoencoder 784-256-2-256-784: test error 35.96 PCA, 16 components: test squared error per image 20.90 linear autoencoder, 16 units: test error 20.92; principal angles to the PCA subspace: median 1.0 deg, largest 2.0 deg (Theorem 16.7) nonlinear autoencoder 784-256-16-256-784: test error 15.39 10-NN accuracy of the 5,000 digits in the 2-D autoencoder code: 0.531 (89 s for all training)
The linear autoencoder's test error (20.92) matches PCA's with 16 components (20.90); principal angles between the two subspaces have median 1.0° and maximum 2.0°, as Theorem 16.7 predicts. (With a quarter of the steps the largest was still 74°: small-eigenvalue directions have small gradients and are learned slowly.) The nonlinear autoencoder reconstructs better: 35.96 against PCA's 43.30 with a 2-dimensional code, 15.39 against 20.90 with 16. As a map it is much worse than t-SNE or UMAP (10-NN accuracy 0.531): it was trained on pixels, not neighbours.
A plain autoencoder's code space has no particular shape, so arbitrary codes decode to garbage. The variational autoencoder (Kingma and Welling, 2014; Rezende, Mohamed and Wierstra, 2014) makes the decoder probabilistic, as probabilistic PCA did for PCA (Lecture 16a, Definition 16.2), with a neural network in place of \(W\). Each image maps to a small Gaussian cloud, and a penalty packs the clouds around the origin, so draws from the prior decode to plausible images: the VAE is generative.
The generative model is
$$z\sim N(0,I_k),\qquad x\mid z\sim p_\theta(x\mid z),$$with the parameters of \(p_\theta\) (for binary pixels, Bernoulli probabilities) output by a decoder network.
The posterior \(p_\theta(z\mid x)\) is intractable, so an encoder network outputs the mean and diagonal variance of an approximation
$$q_\phi(z\mid x)=N\big(\mu_\phi(x),\operatorname{diag}\sigma^2_\phi(x)\big).$$Encoder and decoder are trained together to maximise the evidence lower bound (ELBO),
$$\mathcal L(\theta,\phi;x)=\mathbb E_{q_\phi(z\mid x)}\big[\log p_\theta(x\mid z)\big]-\mathrm{KL}\big(q_\phi(z\mid x)\,\Vert\,p(z)\big):$$a reconstruction term minus a term that keeps codes close to the prior.
Let \(q(z)\) be any distribution with \(q(z)>0\) wherever \(p_\theta(z\mid x)>0\), and let
$$\mathcal L(q)=\mathbb E_q[\log p_\theta(x\mid z)]-\mathrm{KL}(q\Vert p).$$Then
$$\log p_\theta(x)=\mathcal L(q)+\mathrm{KL}\big(q(z)\,\Vert\,p_\theta(z\mid x)\big)\;\ge\;\mathcal L(q),$$with equality exactly when \(q\) is the true posterior.
By Bayes' rule, for every \(z\),
$$\log p_\theta(x)=\log p_\theta(x\mid z)+\log p(z)-\log p_\theta(z\mid x).$$Add and subtract \(\log q(z)\) and take the expectation under \(q\):
$$\log p_\theta(x)=\mathbb E_q\big[\log p_\theta(x\mid z)\big]-\mathbb E_q\!\left[\log\frac{q(z)}{p(z)}\right]+\mathbb E_q\!\left[\log\frac{q(z)}{p_\theta(z\mid x)}\right].$$The first two terms are \(\mathcal L(q)\); the third is \(\mathrm{KL}(q\Vert p_\theta(\cdot\mid x))\).
A KL divergence is non-negative (Gibbs' inequality, from Jensen's inequality applied to \(-\log\)), and zero only when the distributions agree. \(\square\)
Maximising the ELBO over \(\phi\) pulls \(q_\phi\) towards the posterior; over \(\theta\) it raises a lower bound on the likelihood. The Gaussian KL term has a closed form,
$$\tfrac12\sum_j\big(\sigma_j^2+\mu_j^2-1-\log\sigma_j^2\big).$$The reconstruction term is estimated with one sample, written via the reparameterisation trick
$$z=\mu_\phi(x)+\sigma_\phi(x)\odot\varepsilon,\qquad\varepsilon\sim N(0,I),$$which moves the randomness into \(\varepsilon\), so gradients flow through \(\mu_\phi,\sigma_\phi\) by ordinary backpropagation.
# A variational autoencoder with a 2-D latent space (Kingma and Welling, 2014) def init_vae(seed=1): ks = jax.random.split(jax.random.PRNGKey(seed), 5) return {'e': [dense(ks[0], 784, 256)], 'mu': dense(ks[1], 256, 2), 'lv': dense(ks[2], 256, 2), 'd': [dense(ks[3], 2, 256), dense(ks[4], 256, 784)]} def encode(p, x): h = jax.nn.relu(x @ p['e'][0]['W'] + p['e'][0]['b']) return h @ p['mu']['W'] + p['mu']['b'], h @ p['lv']['W'] + p['lv']['b'] # mean and log-variance of q(z|x) def neg_elbo(p, x, key): mu_, lv = encode(p, x) z = mu_ + jnp.exp(0.5 * lv) * jax.random.normal(key, mu_.shape) # reparameterisation trick logits = mlp(p['d'], z) rec = jnp.sum(jnp.maximum(logits, 0) - logits * x + jnp.log1p(jnp.exp(-jnp.abs(logits))), 1) # Bernoulli -log p(x|z) kl = 0.5 * jnp.sum(jnp.exp(lv) + mu_**2 - 1 - lv, 1) # KL(q(z|x) || N(0, I)), closed form return jnp.mean(rec + kl) t0 = time.time(); vae = train(neg_elbo, init_vae(), steps=6000) mu_te, lv_te = encode(vae, jnp.asarray(Xte)) elbo = -float(neg_elbo(vae, jnp.asarray(Xte), jax.random.PRNGKey(9))) kl_te = float(jnp.mean(0.5 * jnp.sum(jnp.exp(lv_te) + mu_te**2 - 1 - lv_te, 1))) print(f"VAE trained in {time.time() - t0:.0f} s; test ELBO {elbo:.1f} nats per image (a lower bound on log p(x)); " f"KL term {kl_te:.2f} nats") Z_vae = np.asarray(encode(vae, jnp.asarray(Xm))[0]) print(f"10-NN accuracy of the 5,000 digits in the VAE's 2-D latent means: {knn(Z_vae):.3f}") print(f"latent means of the test set: mean {np.round(np.asarray(mu_te).mean(0), 2)}, sd {np.round(np.asarray(mu_te).std(0), 2)} " f"(the prior is N(0, I))") samp = jax.nn.sigmoid(mlp(vae['d'], jax.random.normal(jax.random.PRNGKey(3), (2000, 2)))) lab_s = KNeighborsClassifier(10).fit(Xtr[:20000], ytr[:20000]).predict(np.asarray(samp)) print("digits classified among 2,000 samples drawn from the prior:", np.bincount(lab_s, minlength=10).tolist())
VAE trained in 59 s; test ELBO -154.8 nats per image (a lower bound on log p(x)); KL term 5.77 nats 10-NN accuracy of the 5,000 digits in the VAE's 2-D latent means: 0.693 latent means of the test set: mean [-0.04 -0.56], sd [1.23 1.09] (the prior is N(0, I)) digits classified among 2,000 samples drawn from the prior: [443, 196, 163, 294, 134, 199, 214, 48, 137, 172]
The VAE trains in about a minute. Its test ELBO is -154.8 nats per image, a likelihood bound no plain autoencoder provides; only 5.77 nats go to the KL term, the information the code carries beyond the prior. Its latent means beat the plain autoencoder's code (10-NN accuracy 0.693 against 0.531) but not t-SNE or UMAP, since the KL term pulls classes together near the origin. Test codes have means (-0.04, -0.56) and standard deviations (1.23, 1.09), close to the N(0, I) prior. Decoding 2,000 prior draws yields every digit, but unevenly (443 zeros against 48 sevens): two dimensions are too few.
For a one-dimensional code, the encoder outputs \(\mu=1\) and \(\sigma^2=1\) for some image. What is \(\mathrm{KL}\big(N(\mu,\sigma^2)\,\Vert\,N(0,1)\big)\) in nats?
Variational inference approximates a posterior \(p(z\mid x)\) by the \(q\) in a simple family that maximises the ELBO, i.e. (Theorem 16.8) the one closest in KL. Classical variational inference fits a separate \(q\) per data point; the VAE amortises this with one encoder, so a new point costs one forward pass. The price is an "amortisation gap": \(q_\phi(\cdot\mid x)\) can be worse than the best Gaussian for that \(x\). Probabilistic PCA (Lecture 16a) is the linear-Gaussian case, where the bound can be tight; EM (Lecture 17a) is the case of a computable posterior, with the KL term zero at every step.
Can latent axes be read as hidden causes (stroke thickness, slant, digit identity)? Causal representation learning (Schölkopf et al., 2021) asks when, and the first answer is negative: Locatello et al. (2019) proved that without assumptions, unsupervised learning cannot identify "disentangled" factors, since infinitely many latent spaces give the same data distribution, as with the rotation \(R\) of probabilistic PCA (Lecture 16a, Theorem 16.3). Identifiability returns with extra information: several environments or interventions, auxiliary variables, time structure, or sparse mechanisms. Otherwise VAE axes are coordinates, not causes.
Learned embeddings are the common currency of modern machine learning: text, images, proteins and users become vectors, and search, recommendation and retrieval-augmented generation (Lecture 12) use nearest neighbours among them. Stable Diffusion runs diffusion in the latent space of a VAE that compresses each image about 48-fold (Rombach et al., 2022). Cell atlases such as the Human Cell Atlas organise hundreds of millions of cells with the tools of Section 3. In each case the embedding keeps what its objective rewards, and nothing else is guaranteed.
The mean is \(10/3\), so the centred positions are \(-10/3,\,-1/3,\,11/3\).
By Theorem 16.5, \(B=X_cX_c^\top\) with \(X_c=(-10/3,-1/3,11/3)^\top\). This is rank one, with eigenvector \(X_c/\lVert X_c\rVert\) and eigenvalue
$$\lVert X_c\rVert^2=\frac{100+1+121}{9}=24.67.$$The MDS coordinate is \(\sqrt{24.67}\,X_c/\lVert X_c\rVert=X_c\) (or \(-X_c\)): the positions up to the mean and a sign. Computing \(B\) directly from
$$D^{(2)}=\begin{pmatrix}0&9&49\\9&0&16\\49&16&0\end{pmatrix}$$gives the same matrix.
Expanding,
$$\sum_{ij}w_{ij}(y_i^2+y_j^2-2y_iy_j)=2\sum_id_iy_i^2-2\sum_{ij}w_{ij}y_iy_j=2y^\top(D-W)y.$$Without the constraint, the constant vector \(y=c\mathbf 1\) (scaled so that \(y^\top Dy=1\)) gives objective 0, mapping every point to one place. It is the eigenvector of eigenvalue 0, so the embedding starts from the second eigenvector, as in spectral clustering.
In 50 dimensions a point can have many neighbours at moderate distance; two dimensions lack the room. With Gaussians in both spaces they are squeezed towards the centre and clusters run together (the crowding problem).
The Student-t kernel decays polynomially, so a moderate \(p_{ij}\) is matched by a much larger map distance; such points are pushed out and gaps open between clusters.
By the theorem,
$$\mathcal L(q)=\log p_\theta(x)-\mathrm{KL}\big(q\Vert p_\theta(\cdot\mid x)\big),$$and \(\log p_\theta(x)\) does not depend on \(q\), so the two problems have the same solution.
If \(q\) is the exact posterior \(p_{\theta_{\text{old}}}(z\mid x)\) (the E-step), then
$$\mathcal L=\mathbb E_q[\log p_\theta(x,z)]+\text{const},$$and maximising it over \(\theta\) is exactly the M-step of EM (Lecture 17a).
We have \(\mathbb E[z^2]=\mathbb E[(\mu+\sigma\varepsilon)^2]\) and
$$\frac{\partial}{\partial\mu}(\mu+\sigma\varepsilon)^2=2(\mu+\sigma\varepsilon),$$with expectation \(2\mu\). Exactly, \(\mathbb E[z^2]=\mu^2+\sigma^2\), whose derivative is \(2\mu\).
The distribution of \(\varepsilon\) does not depend on \(\mu\), so the derivative passes inside the expectation and a Monte Carlo average of \(2(\mu+\sigma\varepsilon)\) is unbiased.
B cells, platelets, dendritic cells and the T/NK–monocyte split are stable, because they differ in many genes. The T-cell subsets (naive and memory CD4, CD8) and NK cells, and the two monocyte types, merge at low resolution (six clusters at 0.5) and split further at high resolution.
The number of cell types is a choice of resolution, as Lecture 15 found for \(k\); report the cluster tree across resolutions and validate each split with marker genes or independent data.
Each project uses this lecture's methods and public data, and has a clear result.
Data. Swiss roll: scikit-learn's make_swiss_roll. MNIST: Y. LeCun, C. Cortes, C. J. C. Burges, in Michael Nielsen's split, github.com/mnielsen/neural-networks-and-deep-learning. PBMC 3k: 10x Genomics (free demonstration data set), raw counts from github.com/munaberhe/pbmc3k-analysis because 10x Genomics' site was not reachable. Gaussian clusters and noise in the t-SNE experiment are simulated.
continues Lecture 16a: linear methods | numbers in the text not printed by a code box are computed in verify_L16b.py, figures and widget data in figs_L16b.py; code-box outputs are pasted from actual runs (numpy, scikit-learn, umap-learn, Scanpy and JAX on one CPU core)