Machine Learning · Lecture 16b

Lecture 16b
Dimension Reduction II: Nonlinear Methods

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

Cartoon: the ant and the birdA rolled-up carpet. A bird flying straight across the roll says two points are close; an ant walking along the carpet between the same two points says they are far apart. Bird: those two pointsare a hop apart. Ant: it's a long walkround the roll.
Distance in the space the data are recorded in is not distance along the shape the data lie on
In this lecture
  1. Multidimensional scaling, Isomap and Laplacian eigenmaps
  2. t-SNE and UMAP: what they preserve and how they mislead
  3. A single-cell pipeline: PCA, a graph, clusters, UMAP
  4. Autoencoders and variational autoencoders
  5. Summary, exercises, projects, reading

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.

1 — Multidimensional scaling, Isomap and Laplacian eigenmaps

Given only a table of distances between cities, multidimensional scaling (MDS) draws the map: low-dimensional points whose distances match the table.

definition 16.4 — classical and metric MDS

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.$$
theorem 16.5 — classical MDS of Euclidean distances is PCA

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.

definition 16.5 — Isomap and Laplacian eigenmaps

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).

code — unrolling a Swiss roll
# 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
the roll (x, z)PCA = classical MDSIsomap, 10 neighbours
1,500 points on a Swiss roll, coloured by position along it. Left: side view. Centre: PCA (identical to classical MDS) projects, so layers overlap. Right: Isomap with 10 neighbours unrolls it into an ordered strip.

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 and the neighbour count

Left: the Swiss roll, coloured by position. Right: Isomap's embedding; a good one is a strip with smoothly running colours. Find the neighbour count at which the graph short-circuits between layers.

spot check 16.5

Isomap is run on data near a curved surface, with a few outliers scattered between the folds. What is the most likely failure?

Isomap trusts shortest paths in the neighbour graph. What does one bridging point do to them?
A point between two folds neighbours points on both; every shortest path between the folds uses this short cut, and Isomap squashes them together. Isomap needs clean data and a careful \(k\).

2 — t-SNE and UMAP: what they preserve and how they mislead

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.

definition 16.6 — t-SNE

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.

data — MNIST

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.

code — PCA, t-SNE and UMAP on 5,000 digits
# 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
PCAt-SNEUMAPautoencoderVAE (latent mean)0123456789
2,500 of the digits embedded by five methods, coloured by the true digit (unseen by every method). PCA overlaps most classes; t-SNE and UMAP form islands; the autoencoder and VAE of Section 4 are intermediate. Panels are scaled independently.

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.

code — sizes, gaps and phantom clusters
# 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.

The perplexity dial

t-SNE of the same 1,000 digits at six perplexities (same seed). Small ones fragment digits into clumps; large ones merge similar digits. The readout gives 10-nearest-neighbour accuracy.

spot check 16.6

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?

A uniform distribution on \(m\) outcomes has entropy \(\log_2m\) bits.
\(H=\log_230\) bits, so the perplexity is \(2^{\log_230}=30\): an effective neighbour count.
spot check 16.7

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?

What does the objective reward, and what does it ignore?
The code above drew a ten-fold difference in spread as a 1.2-fold difference in size, and gaps are not guaranteed. Measure spreads and centroid distances in the original space.
history — the manifold year, and the map that took over biology

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).

3 — A single-cell pipeline: PCA, a graph, clusters, UMAP

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.

data — PBMC 3k (10x Genomics)

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).

code — quality control, normalisation, PCA, neighbours, Leiden clusters, UMAP
# 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)
0: CD4 T1: CD8 T2: NK3: CD4 T4: B5: FCGR3A monocyte6: CD14 monocyte7: dendritic8: platelet
UMAP of the 2,638 cells that pass quality control, coloured by Leiden cluster and labelled with the cell type whose marker genes score highest in each cluster.

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.

Blood cells, coloured by cluster or by gene

Colour the cells by Leiden cluster or a marker gene: CD3E marks all T cells, CD8A the cytotoxic ones, GNLY and NKG7 NK cells, MS4A1 B cells, CD14 and LYZ classical monocytes, FCGR3A non-classical monocytes and NK cells, FCER1A dendritic cells, PPBP platelets.

4 — Autoencoders and variational autoencoders

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.

definition 16.7 — autoencoder

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.

theorem 16.7 — a linear autoencoder learns the PCA subspace (Baldi and Hornik, 1989)

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.

code — linear and nonlinear autoencoders on MNIST (JAX)
# 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.

definition 16.8 — variational autoencoder

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.

theorem 16.8 — the evidence lower bound

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.

code — a variational autoencoder with a 2-D latent space
# 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.

Walking the latent space

Latent means of 1,500 test digits, coloured by digit. Tap or drag: the decoder, running in your browser, turns that \(z\) into the image on the right. Near the centre digits are clean and morph into one another; far outside the dashed circles they degrade.

spot check 16.8

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?

Use \(\tfrac12(\sigma^2+\mu^2-1-\log\sigma^2)\).
\(\tfrac12(1+1-1-0)=0.5\) nats, all from the shifted mean. A code with \(\mu=0,\sigma^2=1\) costs nothing but carries no information: the tension the ELBO balances.
Bayes — the VAE is amortised variational inference

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.

causal — can a latent space find the true causes?

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.

big picture — embeddings and latent spaces everywhere

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.

5 — Summary, exercises, projects, reading

summary
exercises
  1. Three cities lie on a straight road at kilometre posts 0, 3 and 7. Write down the distance matrix, compute \(B=-\tfrac12JD^{(2)}J\), and check that classical MDS in one dimension recovers the positions up to a shift and a reflection.

    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.

  2. Show that the Laplacian-eigenmap objective \(\sum_{i,j}w_{ij}(y_i-y_j)^2\) for a one-dimensional embedding equals \(2y^\top Ly\), and explain why the constraint \(y^\top D\mathbf 1=0\) is needed.

    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.

  3. Explain why t-SNE uses a heavy-tailed kernel in the embedding but a Gaussian in the original space. What would happen with Gaussians in both (the original SNE)?

    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.

  4. In Theorem 16.8, show that maximising the ELBO over \(q\) for fixed \(\theta\) is equivalent to minimising \(\mathrm{KL}(q\Vert p_\theta(\cdot\mid x))\), and that maximising it over \(\theta\) for the exact posterior is the M-step of EM.

    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).

  5. Write the reparameterisation \(z=\mu+\sigma\varepsilon\) for \(z\sim N(\mu,\sigma^2)\) and use it to compute \(\frac{\partial}{\partial\mu}\mathbb E[z^2]\) by differentiating inside the expectation. Check against the exact answer.

    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.

  6. (Code.) Rerun the single-cell code with Leiden resolutions 0.3, 0.5, 1.0 and 2.0 and with 5, 10 and 30 neighbours. Which cell types are stable, and which appear or merge? What does that suggest about reporting "the number of cell types"?

    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.

student projects

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

1. How misleading is UMAP?

question
Across hyperparameters and random seeds, how much do t-SNE and UMAP distort cluster sizes, between-cluster distances and the number of apparent clusters, on data whose geometry is known?
data
Simulated mixtures with controlled spreads, separations and densities; data sets with known structure (MNIST, the Swiss roll, single-cell data with sorted cell types such as the Zheng et al. 2017 purified PBMC populations).
method
Grids over perplexity, number of neighbours, minimum distance and seed; quantitative distortion measures (ratio of spreads, rank correlation of centroid distances, cluster counts by a fixed rule); comparison with PCA and with densMAP, a density-preserving variant of UMAP.
outcome
A practical guide with numbers: which features of a t-SNE or UMAP plot can be trusted under which settings, and which should never be reported.

2. A two-dimensional map of New York neighbourhoods

question
Do nonlinear embeddings of New York census tracts reveal structure (gradients, enclaves, outliers) that PCA misses?
data
American Community Survey 5-year tract estimates for New York City, with borough and Neighborhood Tabulation Area labels held out.
method
PCA, Isomap, t-SNE, UMAP and a small VAE; trustworthiness and global-distance measures; stability across seeds; maps linking embedding regions back to geography.
outcome
A comparison of what each method shows about the city's social geography and how robust each feature is, building on the PCA project of Lecture 16a.

Reading and sources

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)