"""Murphy (2022), Chapter 20: Dimensionality Reduction.

Companion code for Chapter 20 of K. P. Murphy, Probabilistic Machine Learning: An Introduction
(MIT Press, 2022; April 2025 draft), pp. 657-714, written from scratch with numpy, scipy and
matplotlib (PyTorch for the autoencoders), to be read next to the lecture notes
(../ch20-dimensionality-reduction.html). scikit-learn is used to load data and to confirm the
implementations.

Methods
* Section 20.1, PCA: eigendecomposition, SVD and Gram-matrix routes (pca_eig, pca_svd, pca_gram),
  reconstruction error and scree quantities, the profile likelihood of (20.28)-(20.31).
* Section 20.2, factor analysis: the FA and PPCA marginals, the PPCA maximum likelihood estimate
  (20.45)-(20.46), EM for FA (20.54)-(20.60) and for PCA (20.63)-(20.64), the mixture of PPCA
  models by EM, binary PCA by variational EM with the Jaakkola-Jordan bound, supervised PCA,
  canonical correlation analysis.
* Section 20.3, autoencoders (PyTorch, CPU): bottleneck, denoising, sparse (L1 and KL) and
  variational autoencoders, the reparameterisation trick and the closed-form Gaussian KL.
* Section 20.4, manifold learning: classical MDS, SMACOF metric MDS, Isomap, kernel PCA, locally
  linear embedding, Laplacian eigenmaps, SNE and t-SNE (own gradient-descent implementation).
* Section 20.5, word embeddings: PPMI + SVD (LSA), the shifted-PMI optimum of skip-gram with
  negative sampling, the parallelogram rule for analogies on a synthetic corpus.

Data. Figure 20.5 uses the Davis (1990) height and weight data (R package carData) as a stand-in
for the book's data set. MNIST (cached, see common.py) replaces the book's Fashion-MNIST in the
autoencoder figures and the Olivetti faces of Figure 20.3 (neither is available offline); the
captions say so. Swiss roll, UCI digits (8 x 8) come from scikit-learn. All trainings are sized
for a single CPU thread: small MNIST subsets and a few epochs, so the reconstructions and
latent spaces are rougher than the book's.

Figures. Reproduced here: 20.1-20.10, 20.12, 20.13, 20.17-20.21 (20.20 against the exact score of a Gaussian mixture), 20.24-20.27, 20.29-20.38,
20.41, 20.42, 20.45 (with a synthetic-corpus stand-in). Skipped, with the reason:
  20.11, 20.14, 20.15  graphical models of mixtures of factor analysers, supervised PCA / PLS and CCA
                       (hand-drawn diagrams, nothing computed);
  20.16, 20.22, 20.23  the one-hidden-layer autoencoder, the VAE schematic and the VAE computation
                       graph (diagrams);
  20.28                tangent spaces on a curved manifold (an illustration borrowed from the
                       literature, nothing computed);
  20.39, 20.40         a Laplacian matrix worked on a small graph and a function on a graph
                       (illustrations; the same objects are computed in Figure 20.S3);
  20.43, 20.44         the cosine-similarity sketch and the word2vec architecture diagrams.
Supplementary figures for the gaps filled in the notes:
  20.S1  convergence of EM for PCA: it is subspace iteration, so the angle to the principal
         subspace shrinks by (lambda_{L+1} / lambda_L) per step;
  20.S2  the PPCA maximum likelihood estimate against a brute-force search (profile in sigma^2);
  20.S3  Laplacian eigenvectors on the Swiss-roll nearest-neighbour graph (the smoothest functions);
  20.S4  the crowding problem: Gaussian against Student-t (nu = 1) similarity kernels;
Run `python3 ch20_dimensionality_reduction.py --list`, `python3 ch20_dimensionality_reduction.py`
(all figures, about ten minutes) or `python3 ch20_dimensionality_reduction.py --fig 20.5`. Files go
to ../img/ch20/; the data used by the browser demonstrations go to ../data/ch20-*.json.
"""
import json
import os
import sys

os.environ.setdefault("OPENBLAS_NUM_THREADS", "1")

import numpy as np
from scipy import linalg, sparse, special
from scipy.sparse import csgraph

sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
import common  # noqa: E402
from common import BLUE, CYAN, GREEN, GREY, MAGENTA, ORANGE, PURPLE, RED, plt, savefig  # noqa: E402

CH = 20
HERE = os.path.dirname(os.path.abspath(__file__))
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
CACHE_DIR = os.path.join(HERE, "cache")
os.makedirs(CACHE_DIR, exist_ok=True)
sigmoid = common.sigmoid
TEN = list(plt.get_cmap("tab10").colors)


def r_(a, d=5):
    return np.round(np.asarray(a, dtype=float), d).tolist()


# =========================================================================== data
def mnist_subset(n_train=10000, n_test=2000, seed=0):
    """A fixed random subset of MNIST (cached): (Xtr, ytr, Xte, yte), pixels in [0, 1]."""
    path = os.path.join(CACHE_DIR, "ch20_mnist_%d_%d_%d.npz" % (n_train, n_test, seed))
    if not os.path.exists(path):
        X, y = common.mnist(train=True)
        rng = np.random.default_rng(seed)
        idx = rng.permutation(len(X))[:n_train]
        Xtr, ytr = X[idx].astype(np.float32), y[idx]
        del X, y
        X, y = common.mnist(train=False)
        idx = rng.permutation(len(X))[:n_test]
        Xte, yte = X[idx].astype(np.float32), y[idx]
        np.savez_compressed(path, Xtr=Xtr, ytr=ytr, Xte=Xte, yte=yte)
    d = np.load(path)
    return d["Xtr"], d["ytr"], d["Xte"], d["yte"]


def davis():
    """Height (cm), weight (kg) and sex of the 200 subjects of the Davis (1990) study (R package
    carData), without the one record whose height and weight were swapped (height 57, weight 166)."""
    import subprocess
    import shutil
    path = os.path.join(CACHE_DIR, "ch20_davis.csv")
    if not os.path.exists(path):
        rscript = shutil.which("Rscript") or "/usr/local/bin/Rscript"
        r = 'library(carData); write.csv(Davis[,c("sex","height","weight")], "%s", row.names=FALSE)' % path
        subprocess.run([rscript, "-e", r], check=True, capture_output=True)
    import pandas as pd
    d = pd.read_csv(path)
    d = d[d.height > 100]
    return d.height.values.astype(float), d.weight.values.astype(float), (d.sex.values == "M")


def swiss_roll(n=1000, noise=0.0, seed=0):
    from sklearn.datasets import make_swiss_roll
    return make_swiss_roll(n, noise=noise, random_state=seed)


def uci_digits():
    from sklearn.datasets import load_digits
    d = load_digits()
    return d.data.astype(float), d.target


# =========================================================================== PCA (Section 20.1)
def pca_eig(X):
    """Mean, eigenvalues (descending) and eigenvectors (columns) of the empirical covariance
    S = Xc' Xc / N of (20.2)."""
    mu = X.mean(0)
    Xc = X - mu
    S = Xc.T @ Xc / len(X)
    lam, U = np.linalg.eigh(S)
    o = np.argsort(lam)[::-1]
    return mu, np.maximum(lam[o], 0.0), U[:, o]


def pca_svd(X, L):
    """PCA through the thin SVD of the centred data: returns mean, eigenvalues s^2/N, W = V_L and
    the scores Z = U_L S_L (20.23)."""
    mu = X.mean(0)
    Xc = X - mu
    U, s, Vt = np.linalg.svd(Xc, full_matrices=False)
    return mu, s ** 2 / len(X), Vt[:L].T, U[:, :L] * s[:L]


def pca_gram(X, L):
    """PCA through the N x N Gram matrix (20.21)-(20.22): the D x L basis V = Xc' U Lambda^{-1/2}."""
    Xc = X - X.mean(0)
    lam, U = np.linalg.eigh(Xc @ Xc.T)
    o = np.argsort(lam)[::-1][:L]
    lam, U = lam[o], U[:, o]
    return lam / len(X), Xc.T @ U / np.sqrt(lam)


def recon_error_curve(Xte, mu, U, Ls):
    """Mean squared reconstruction error (20.25) of the rows of Xte against the number of
    components L, using the identity ||x - mu||^2 - sum_{j<=L} (u_j'(x - mu))^2."""
    Xc = Xte - mu
    tot = (Xc ** 2).sum(1).mean()
    sc = np.cumsum((Xc @ U) ** 2, axis=1).mean(0)
    return np.array([tot - (sc[L - 1] if L > 0 else 0.0) for L in Ls])


def profile_loglik(lam):
    """The profile log likelihood (20.31) of the change-point model on the eigenvalues lam
    (descending), for L = 1 .. Lmax - 1, with the pooled variance (20.30)."""
    lam = np.asarray(lam, float)
    Lm = len(lam)
    out = []
    for L in range(1, Lm):
        a, b = lam[:L], lam[L:]
        m1, m2 = a.mean(), b.mean()
        s2 = (((a - m1) ** 2).sum() + ((b - m2) ** 2).sum()) / Lm
        ll = (-0.5 * np.log(2 * np.pi * s2) * Lm - 0.5 * (((a - m1) ** 2).sum() + ((b - m2) ** 2).sum()) / s2)
        out.append(ll)
    return np.arange(1, Lm), np.array(out)


# =========================================================================== PPCA and FA (Section 20.2)
def ppca_mle(S, L):
    """Closed-form PPCA maximum likelihood (20.45)-(20.46) with R = I: W, sigma^2."""
    lam, U = np.linalg.eigh(S)
    o = np.argsort(lam)[::-1]
    lam, U = lam[o], U[:, o]
    D = len(lam)
    s2 = lam[L:].mean() if L < D else 0.0
    W = U[:, :L] * np.sqrt(np.maximum(lam[:L] - s2, 0.0))
    return W, s2


def ppca_loglik_S(W, s2, S, N):
    """log p(X | mu_hat, W, sigma^2) of (20.44), given the empirical covariance S."""
    D = S.shape[0]
    C = W @ W.T + s2 * np.eye(D)
    sign, ld = np.linalg.slogdet(C)
    return -0.5 * N * (D * np.log(2 * np.pi) + ld + np.trace(np.linalg.solve(C, S)))


def ppca_posterior(x, mu, W, s2):
    """p(z | x) = N(M^{-1} W'(x - mu), sigma^2 M^{-1}), (20.52), with M = W'W + sigma^2 I."""
    L = W.shape[1]
    M = W.T @ W + s2 * np.eye(L)
    Mi = np.linalg.inv(M)
    return (np.atleast_2d(x - mu) @ W @ Mi.T), s2 * Mi


def em_pca(Xt, W0, iters):
    """Zero-noise EM for PCA (20.63)-(20.64); Xt is D x N (centred). Returns the list of W's
    (the first is W0)."""
    W = W0.copy()
    out = [W.copy()]
    for _ in range(iters):
        Z = np.linalg.solve(W.T @ W, W.T @ Xt)         # E step
        W = Xt @ Z.T @ np.linalg.inv(Z @ Z.T)          # M step
        out.append(W.copy())
    return out


def subspace_angle(W, U):
    """Largest principal angle (radians) between the column spaces of W and U."""
    Qw, _ = np.linalg.qr(W)
    Qu, _ = np.linalg.qr(U)
    s = np.linalg.svd(Qw.T @ Qu, compute_uv=False)
    return float(np.arccos(np.clip(s.min(), -1, 1)))


def fa_em(X, L, iters=200, seed=0, W0=None, psi0=None):
    """EM for factor analysis (20.54)-(20.60), mu estimated jointly with W. Returns mu, W, psi and
    the log-likelihood after each iteration."""
    N, D = X.shape
    rng = np.random.default_rng(seed)
    mu = X.mean(0)
    Xc = X - mu
    S = Xc.T @ Xc / N
    W = rng.normal(size=(D, L)) * 0.5 if W0 is None else W0.copy()
    psi = np.diag(S).copy() if psi0 is None else psi0.copy()
    ll = []
    for _ in range(iters):
        C = W @ W.T + np.diag(psi)
        ll.append(-0.5 * N * (D * np.log(2 * np.pi) + np.linalg.slogdet(C)[1] + np.trace(np.linalg.solve(C, S))))
        Sig = np.linalg.inv(np.eye(L) + W.T @ (W / psi[:, None]))      # (20.55)
        Mz = Xc @ (W / psi[:, None]) @ Sig.T                              # rows m_i (20.56)
        Ezz = N * Sig + Mz.T @ Mz
        W = (Xc.T @ Mz) @ np.linalg.inv(Ezz)                              # (20.59), mu already centred
        psi = np.maximum(np.diag(S - W @ (Mz.T @ Xc) / N), 1e-6)         # (20.60)
    return mu, W, psi, np.array(ll)


def mppca_em(X, K, L, iters=100, seed=0, init_labels=None):
    """Mixture of PPCA models by EM; the M step uses the weighted PPCA maximum likelihood (20.45)-(20.46)
    for every component (a valid EM step: it maximises the expected complete-data log likelihood in which
    only the component indicator is treated as missing). Returns dict(pi, mu, W, s2, ll)."""
    from sklearn.cluster import KMeans
    N, D = X.shape
    lab = KMeans(K, n_init=3, random_state=seed).fit_predict(X) if init_labels is None else init_labels
    R = np.eye(K)[lab] + 1e-3
    R /= R.sum(1, keepdims=True)
    ll = []
    for it in range(iters + 1):
        nk = R.sum(0)
        pi = nk / N
        mu, W, s2 = [], [], []
        for k in range(K):
            m = (R[:, k:k + 1] * X).sum(0) / nk[k]
            Xc = X - m
            S = (R[:, k:k + 1] * Xc).T @ Xc / nk[k] + 1e-8 * np.eye(D)
            Wk, sk = ppca_mle(S, L)
            mu.append(m)
            W.append(Wk)
            s2.append(max(sk, 1e-6))
        lp = np.zeros((N, K))
        for k in range(K):
            C = W[k] @ W[k].T + s2[k] * np.eye(D)
            lp[:, k] = np.log(pi[k]) + common.gauss_logpdf(X, mu[k], C)
        lse = common.logsumexp(lp, axis=1)
        ll.append(lse.sum())
        R = np.exp(lp - lse[:, None])
    return dict(pi=pi, mu=np.array(mu), W=W, s2=np.array(s2), ll=np.array(ll), R=R)


def _lam_jj(xi):
    xi = np.maximum(np.abs(xi), 1e-8)
    return (sigmoid(xi) - 0.5) / (2 * xi)


def binary_pca(X, L=2, iters=60, seed=0):
    """Binary PCA, p(x_nd = 1 | z) = sigmoid(w_d' z + b_d), z ~ N(0, I), fitted by variational EM with the
    Jaakkola-Jordan bound (Tipping 1998). Returns dict(W, b, m, S, bound) where m (N x L) are the posterior
    means E[z | x] and bound is the variational lower bound after every iteration."""
    N, D = X.shape
    rng = np.random.default_rng(seed)
    Wt = np.hstack([rng.normal(size=(D, L)) * 0.1, np.zeros((D, 1))])    # rows (w_d, b_d)
    xi = np.ones((N, D))
    bound = []
    for it in range(iters):
        lam = _lam_jj(xi)                                                  # N x D
        # E step: q(z_n) = N(m_n, S_n)
        Sn = np.zeros((N, L, L))
        m = np.zeros((N, L))
        W, b = Wt[:, :L], Wt[:, L]
        for n in range(N):
            P = np.eye(L) + 2 * (W.T * lam[n]) @ W
            Sn[n] = np.linalg.inv(P)
            m[n] = Sn[n] @ (W.T @ ((X[n] - 0.5) - 2 * lam[n] * b))
        # M step: w~_d = (2 sum_n lam_nd E[z~ z~'])^{-1} sum_n (x_nd - 1/2) E[z~]
        Ez = np.hstack([m, np.ones((N, 1))])
        Ezz = np.zeros((N, L + 1, L + 1))
        Ezz[:, :L, :L] = Sn + m[:, :, None] * m[:, None, :]
        Ezz[:, :L, L] = m
        Ezz[:, L, :L] = m
        Ezz[:, L, L] = 1.0
        for d in range(D):
            A = 2 * np.einsum("n,nij->ij", lam[:, d], Ezz)
            Wt[d] = np.linalg.solve(A, ((X[:, d] - 0.5)[:, None] * Ez).sum(0))
        # variational parameters: xi_nd^2 = E[(w~_d' z~)^2]
        xi = np.sqrt(np.einsum("di,nij,dj->nd", Wt, Ezz, Wt))
        bound.append(_binary_pca_bound(X, Wt, xi, m, Sn))
    W, b = Wt[:, :L], Wt[:, L]
    return dict(W=W, b=b, m=m, S=Sn, xi=xi, bound=np.array(bound))


def _binary_pca_bound(X, Wt, xi, m, Sn):
    """Variational lower bound on log p(X): sum_n { E_q[log p-bound(x_n | z)] - KL(q(z_n) || N(0, I)) } with
    q(z_n) = N(m_n, S_n) and xi given; a valid (and tight in xi) lower bound for any xi."""
    N, L = m.shape
    lam = _lam_jj(xi)
    Ezz = np.zeros((N, L + 1, L + 1))
    Ezz[:, :L, :L] = Sn + m[:, :, None] * m[:, None, :]
    Ezz[:, :L, L] = m
    Ezz[:, L, :L] = m
    Ezz[:, L, L] = 1.0
    Ea = np.einsum("di,ni->nd", Wt, np.hstack([m, np.ones((N, 1))]))
    Ea2 = np.einsum("di,nij,dj->nd", Wt, Ezz, Wt)
    # log sigma((2x-1) a) >= log sigma(xi) + ((2x-1) a - xi)/2 - lam (a^2 - xi^2); here with t = 2x-1
    t = 2 * X - 1
    term = np.log(sigmoid(xi)) + (t * Ea - xi) / 2 - lam * (Ea2 - xi ** 2)
    kl = 0.5 * (np.trace(Sn, axis1=1, axis2=2) + (m ** 2).sum(1) - L - np.linalg.slogdet(Sn)[1])
    return float(term.sum() - kl.sum())


# =========================================================================== manifold learning (Section 20.4)
def sqdist(X, Y=None):
    Y = X if Y is None else Y
    d = (X ** 2).sum(1)[:, None] + (Y ** 2).sum(1)[None, :] - 2 * X @ Y.T
    return np.maximum(d, 0.0)


def center_gram(K):
    """C K C with the centering matrix C = I - 11'/N (double centering, (7.89))."""
    return K - K.mean(0, keepdims=True) - K.mean(1, keepdims=True) + K.mean()


def classical_mds(D2, L=2):
    """Classical MDS from squared Euclidean distances: K~ = -1/2 C D2 C, embedding U_L S_L^{1/2}
    (20.106)-(20.109). Returns Z and the eigenvalues of K~ (descending)."""
    K = -0.5 * center_gram(D2)
    lam, U = np.linalg.eigh((K + K.T) / 2)
    o = np.argsort(lam)[::-1]
    lam, U = lam[o], U[:, o]
    return U[:, :L] * np.sqrt(np.maximum(lam[:L], 0.0)), lam


def smacof(D, L=2, iters=300, init=None, seed=0, tol=1e-9):
    """Metric MDS by SMACOF (Guttman transform), minimising the raw stress sum_{i<j}(d_ij - dhat_ij)^2.
    D is the matrix of dissimilarities (not squared). Returns Z and the stress after every iteration."""
    N = len(D)
    rng = np.random.default_rng(seed)
    Z = rng.normal(size=(N, L)) if init is None else init.copy()
    stress = []
    for _ in range(iters):
        Dh = np.sqrt(sqdist(Z))
        stress.append(0.5 * ((D - Dh) ** 2).sum())
        with np.errstate(divide="ignore", invalid="ignore"):
            B = np.where(Dh > 1e-12, -D / Dh, 0.0)
        np.fill_diagonal(B, 0.0)
        np.fill_diagonal(B, -B.sum(1))
        Zn = B @ Z / N
        if len(stress) > 1 and abs(stress[-2] - stress[-1]) < tol * max(stress[-1], 1e-12):
            Z = Zn
            break
        Z = Zn
    Dh = np.sqrt(sqdist(Z))
    stress.append(0.5 * ((D - Dh) ** 2).sum())
    return Z, np.array(stress)


def knn_graph(X, k, mode="distance"):
    """Symmetrised k-nearest-neighbour graph as a dense matrix (0 = no edge): an edge i-j is present when j
    is among the k nearest neighbours of i or the other way round."""
    D = np.sqrt(sqdist(X))
    N = len(X)
    idx = np.argsort(D, axis=1)[:, 1:k + 1]
    A = np.zeros((N, N))
    rows = np.repeat(np.arange(N), k)
    A[rows, idx.ravel()] = D[rows, idx.ravel()]
    A = np.maximum(A, A.T)
    return A, D


def geodesic_distances(X, k):
    """Shortest-path distances on the k-NN graph (Isomap, Section 20.4.5); Dijkstra via scipy."""
    A, _ = knn_graph(X, k)
    G = csgraph.shortest_path(sparse.csr_matrix(A), method="D", directed=False)
    return G


def isomap(X, k=10, L=2):
    """Isomap: classical MDS applied to the squared graph geodesic distances (disconnected pairs are
    handled by connecting components through their closest points: not needed for the data used here)."""
    G = geodesic_distances(X, k)
    if not np.isfinite(G).all():
        raise ValueError("k-NN graph is disconnected; increase k")
    Z, lam = classical_mds(G ** 2, L)
    return Z, lam, G


def kernel_pca(K, L=2):
    """Kernel PCA from a (not necessarily centred) kernel matrix: eigenvectors of K~ = CKC; returns the
    scores U_L Lambda_L^{1/2} (the training projections) and the eigenvalues of K~ / N (the variances)."""
    Kc = center_gram(K)
    lam, U = np.linalg.eigh((Kc + Kc.T) / 2)
    o = np.argsort(lam)[::-1]
    lam, U = lam[o], U[:, o]
    return U[:, :L] * np.sqrt(np.maximum(lam[:L], 0)), lam / len(K), U


def rbf_kernel(X, Y=None, gamma=1.0):
    return np.exp(-gamma * sqdist(X, Y))


def lle(X, k=10, L=2, reg=1e-3):
    """Locally linear embedding (Section 20.4.8): sum-to-one reconstruction weights from the local Gram matrix
    (with the trace regulariser reg), then the bottom eigenvectors of M = (I - W)'(I - W), skipping the
    constant one. Returns Z (with Z'Z = I as scaled by the eigenvectors) and the L + 1 smallest eigenvalues."""
    N = len(X)
    D2 = sqdist(X)
    idx = np.argsort(D2, axis=1)[:, 1:k + 1]
    W = np.zeros((N, N))
    for i in range(N):
        Zi = X[idx[i]] - X[i]
        G = Zi @ Zi.T
        G = G + reg * np.trace(G) * np.eye(k) if np.trace(G) > 0 else G + reg * np.eye(k)
        w = np.linalg.solve(G, np.ones(k))
        W[i, idx[i]] = w / w.sum()
    M = (np.eye(N) - W).T @ (np.eye(N) - W)
    lam, V = np.linalg.eigh((M + M.T) / 2)
    return V[:, 1:L + 1] * np.sqrt(N), lam[:L + 2], W


def gaussian_knn_weights(X, k=10, sigma=None):
    """Symmetrised k-NN graph with Gaussian edge weights W_ij = exp(-||x_i - x_j||^2 / (2 sigma^2)); sigma defaults to
    the mean k-NN distance."""
    A, D = knn_graph(X, k)
    if sigma is None:
        sigma = A[A > 0].mean()
    return np.where(A > 0, np.exp(-D ** 2 / (2 * sigma ** 2)), 0.0), sigma


def laplacian_eigenmaps(Wm, L=2):
    """Laplacian eigenmaps (Section 20.4.9): generalised eigenproblem L z = lambda D z with L = D - W; returns the L
    eigenvectors after the constant one (D-orthonormal: Z'DZ = I) and the smallest L + 1 eigenvalues."""
    d = Wm.sum(1)
    Ls = np.diag(d) - Wm
    Dm = 1 / np.sqrt(d)
    Sym = Dm[:, None] * Ls * Dm[None, :]
    lam, V = np.linalg.eigh((Sym + Sym.T) / 2)
    Z = V * Dm[:, None]
    return Z[:, 1:L + 1], lam[:L + 1], Z


# ================================================================ SNE / t-SNE
def sne_conditional_p(X, perplexity, tol=1e-6, max_iter=100):
    """Conditional probabilities p_{j|i} of (20.130), with sigma_i^2 found by bisection on beta_i = 1/(2 sigma_i^2)
    so that the perplexity 2^{H(P_i)} equals the target (H in bits). Returns the matrix P (rows sum to 1) and the
    vector of sigma_i."""
    N = len(X)
    D2 = sqdist(X)
    P = np.zeros((N, N))
    sig = np.zeros(N)
    target = np.log(perplexity)
    for i in range(N):
        di = np.delete(D2[i], i)
        lo, hi, beta = 0.0, np.inf, 1.0 / max(np.median(di), 1e-12)
        for _ in range(max_iter):
            e = np.exp(-(di - di.min()) * beta)
            s = e.sum()
            p = e / s
            H = np.log(s) + beta * ((di - di.min()) * p).sum()
            if abs(H - target) < tol:
                break
            if H > target:            # too flat: increase beta
                lo = beta
                beta = beta * 2 if np.isinf(hi) else 0.5 * (beta + hi)
            else:
                hi = beta
                beta = 0.5 * (beta + lo)
        P[i, np.arange(N) != i] = p
        sig[i] = np.sqrt(1.0 / (2 * beta))
    return P, sig


def tsne_joint_p(X, perplexity):
    """Symmetrised joint probabilities p_ij = (p_{j|i} + p_{i|j}) / (2N), summing to 1 over ordered pairs i != j."""
    P, _ = sne_conditional_p(X, perplexity)
    return (P + P.T) / (2 * len(X))


def tsne_q(Z, dof=1.0):
    """Joint q_ij of t-SNE (20.137) (dof = 1, Cauchy kernel) or the Gaussian kernel exp(-d^2) of symmetric SNE
    (dof = None); returns Q and the unnormalised kernel."""
    D2 = sqdist(Z)
    Kn = 1.0 / (1.0 + D2) if dof is not None else np.exp(-D2)
    np.fill_diagonal(Kn, 0.0)
    return Kn / Kn.sum(), Kn


def tsne_kl(P, Q):
    m = P > 0
    return float((P[m] * np.log(P[m] / np.maximum(Q[m], 1e-300))).sum())


def tsne_grad(P, Z, dof=1.0):
    """Gradient of KL(P || Q) with respect to the embedding, 4 sum_j (p_ij - q_ij) (z_i - z_j) w_ij where w_ij =
    (1 + d_ij^2)^{-1} for t-SNE (20.138) and w_ij = 1 for Gaussian symmetric SNE (20.136)."""
    Q, Kn = tsne_q(Z, dof)
    Wt = Kn if dof is not None else np.ones_like(Kn)
    M = (P - Q) * Wt
    return 4 * (M.sum(1)[:, None] * Z - M @ Z)


def tsne(X, perplexity=30.0, n_iter=750, lr=100.0, exag=4.0, exag_iters=100, dim=2, init="pca", seed=0, P=None,
         record=0, dof=1.0):
    """t-SNE by gradient descent with momentum (0.5, then 0.8 after the early-exaggeration phase) and the
    delta-bar-delta gains of van der Maaten and Hinton (2008). The initialisation is PCA scaled to a small standard
    deviation (deterministic). Returns Z, the final KL and the KL curve (recorded every iteration if record)."""
    N = len(X)
    if P is None:
        P = tsne_joint_p(X, perplexity)
    if init == "pca":
        Xc = X - X.mean(0)
        _, _, Vt = np.linalg.svd(Xc, full_matrices=False)
        Z = Xc @ Vt[:dim].T
        Z = Z / Z[:, 0].std() * 1e-2
    else:
        Z = np.random.default_rng(seed).normal(size=(N, dim)) * 1e-2
    upd = np.zeros_like(Z)
    gains = np.ones_like(Z)
    curve = []
    for t in range(n_iter):
        ex = exag if t < exag_iters else 1.0
        g = tsne_grad(P * ex, Z, dof)
        gains = np.where(np.sign(g) != np.sign(upd), gains + 0.2, gains * 0.8)
        gains = np.maximum(gains, 0.01)
        mom = 0.5 if t < exag_iters else 0.8
        upd = mom * upd - lr * gains * g
        Z = Z + upd
        Z = Z - Z.mean(0)
        if record and (t % record == 0 or t == n_iter - 1):
            curve.append((t, tsne_kl(P, tsne_q(Z, dof)[0])))
    kl = tsne_kl(P, tsne_q(Z, dof)[0])
    return Z, kl, curve


# =========================================================================== word embeddings (Section 20.5)
def ppmi(C, shift=0.0):
    """Positive pointwise mutual information matrix of a co-occurrence count matrix C (20.143):
    max(log p(i,j) / (p(i) p(j)) - shift, 0)."""
    tot = C.sum()
    pi = C.sum(1, keepdims=True) / tot
    pj = C.sum(0, keepdims=True) / tot
    with np.errstate(divide="ignore", invalid="ignore"):
        pmi = np.log(C / tot / (pi * pj))
    pmi[~np.isfinite(pmi)] = 0.0
    return np.maximum(pmi - shift, 0.0), pmi


def toy_corpus(seed=0, n_ctx=3000):
    """A synthetic co-occurrence matrix with gender / royalty / age structure, used only to illustrate the
    parallelogram rule for analogies. Rows are the target words, columns the context words; every target word
    draws n_ctx context tokens, with probabilities that depend on its attributes (gender, royal, young) and on a
    shared Zipf-like background distribution."""
    rng = np.random.default_rng(seed)
    words = ["man", "woman", "king", "queen", "boy", "girl", "prince", "princess", "uncle", "aunt", "father", "mother"]
    attr = {"man": (0, 0, 0), "woman": (1, 0, 0), "king": (0, 1, 0), "queen": (1, 1, 0), "boy": (0, 0, 1),
            "girl": (1, 0, 1), "prince": (0, 1, 1), "princess": (1, 1, 1), "uncle": (0, 0, 0), "aunt": (1, 0, 0),
            "father": (0, 0, 0), "mother": (1, 0, 0)}
    g_words = [["he", "his", "him", "beard", "husband", "sir"], ["she", "her", "hers", "dress", "wife", "madam"]]
    r_words = ["crown", "throne", "palace", "kingdom", "royal", "reign"]
    y_words = ["school", "toy", "play", "young", "grow", "small"]
    f_words = ["the", "a", "and", "of", "to", "in", "was", "said", "with", "for", "on", "at", "by", "from", "very",
               "old", "good", "went", "came", "saw"]
    ctx = g_words[0] + g_words[1] + r_words + y_words + f_words
    cidx = {w: j for j, w in enumerate(ctx)}
    bg = 1.0 / (1 + np.arange(len(f_words)))
    bg /= bg.sum()
    C = np.zeros((len(words), len(ctx)))
    for i, w in enumerate(words):
        g, ro, yo = attr[w]
        probs = np.zeros(len(ctx))
        for u in g_words[g]:
            probs[cidx[u]] += 1.0
        for u in g_words[1 - g]:
            probs[cidx[u]] += 0.05
        if ro:
            for u in r_words:
                probs[cidx[u]] += 1.5
        else:
            for u in r_words:
                probs[cidx[u]] += 0.03
        if yo:
            for u in y_words:
                probs[cidx[u]] += 1.5
        else:
            for u in y_words:
                probs[cidx[u]] += 0.03
        for j, u in enumerate(f_words):
            probs[cidx[u]] += 12 * bg[j] * np.exp(0.5 * rng.normal())     # word-specific taste for the filler words
        probs /= probs.sum()
        C[i] = rng.multinomial(n_ctx, probs)
    return words, ctx, C


def analogy(Vs, words, a, b, c, exclude=True):
    """3CosAdd: the word d maximising cos(v_d, v_c + v_b - v_a), excluding a, b, c."""
    ia, ib, ic = words.index(a), words.index(b), words.index(c)
    Vn = Vs / np.linalg.norm(Vs, axis=1, keepdims=True)
    q = Vs[ic] + Vs[ib] - Vs[ia]
    q = q / np.linalg.norm(q)
    sc = Vn @ q
    for i in (ia, ib, ic):
        sc[i] = -np.inf
    return words[int(np.argmax(sc))]


# =========================================================================== autoencoders (Section 20.3, PyTorch)
def _torch():
    return common.torch_setup(0, 1)


def _cache_path(name):
    return os.path.join(CACHE_DIR, "ch20_" + name + ".pt")


def make_mlp_ae(torch, hidden=100, latent=30, act="selu", sigmoid_latent=False):
    nn = torch.nn
    A = nn.SELU if act == "selu" else nn.ReLU
    enc = [nn.Linear(784, hidden), A(), nn.Linear(hidden, latent)]
    if sigmoid_latent:
        enc.append(nn.Sigmoid())
    dec = [nn.Linear(latent, hidden), A(), nn.Linear(hidden, 784)]
    return nn.Sequential(*enc), nn.Sequential(*dec)


def make_cnn_ae(torch):
    nn = torch.nn
    enc = nn.Sequential(nn.Conv2d(1, 16, 3, padding=1), nn.SELU(), nn.MaxPool2d(2),
                        nn.Conv2d(16, 32, 3, padding=1), nn.SELU(), nn.MaxPool2d(2),
                        nn.Conv2d(32, 64, 3, padding=1), nn.SELU(), nn.MaxPool2d(2))
    dec = nn.Sequential(nn.ConvTranspose2d(64, 32, 3, stride=2), nn.SELU(),
                        nn.ConvTranspose2d(32, 16, 3, stride=2, padding=1, output_padding=1), nn.SELU(),
                        nn.ConvTranspose2d(16, 1, 3, stride=2, padding=1, output_padding=1))
    return enc, dec


def train_ae(kind, Xtr, epochs, seed=0, noise=None, lam_l1=0.0, lam_kl=0.0, target=0.1, latent=30, hidden=100,
             sigmoid_latent=False, bs=128, lr=1e-3, tag=None):
    """Train an autoencoder with the Bernoulli (binary cross-entropy) likelihood. kind: 'mlp' or 'cnn'.
    noise: None, ('gauss', sd) or ('drop', p) to make a denoising autoencoder; lam_l1, lam_kl: sparsity penalties on
    the (sigmoid) latent activations. Returns (encode, decode) functions on numpy arrays; cached to disk."""
    torch = _torch()
    torch.manual_seed(seed)
    path = _cache_path(tag) if tag else None
    if kind == "mlp":
        enc, dec = make_mlp_ae(torch, hidden, latent, sigmoid_latent=sigmoid_latent)
    else:
        enc, dec = make_cnn_ae(torch)
    if path and os.path.exists(path):
        sd = torch.load(path)
        enc.load_state_dict(sd["enc"])
        dec.load_state_dict(sd["dec"])
    else:
        params = list(enc.parameters()) + list(dec.parameters())
        opt = torch.optim.Adam(params, lr=lr)
        Xt = torch.tensor(Xtr)
        n = len(Xt)
        g = torch.Generator().manual_seed(seed)
        for ep in range(epochs):
            perm = torch.randperm(n, generator=g)
            for i in range(0, n, bs):
                xb = Xt[perm[i:i + bs]]
                xin = xb
                if noise is not None:
                    if noise[0] == "gauss":
                        xin = (xb + noise[1] * torch.randn(xb.shape, generator=g)).clamp(0, 1)
                    else:
                        xin = xb * (torch.rand(xb.shape, generator=g) > noise[1]).float()
                if kind == "cnn":
                    z = enc(xin.view(-1, 1, 28, 28))
                    logits = dec(z).view(-1, 784)
                else:
                    z = enc(xin)
                    logits = dec(z)
                loss = torch.nn.functional.binary_cross_entropy_with_logits(logits, xb, reduction="none").sum(1).mean()
                if lam_l1 > 0:
                    loss = loss + lam_l1 * z.abs().sum(1).mean()
                if lam_kl > 0:
                    q = z.mean(0).clamp(1e-6, 1 - 1e-6)
                    loss = loss + lam_kl * (target * torch.log(target / q) + (1 - target) * torch.log((1 - target) / (1 - q))).sum()
                opt.zero_grad()
                loss.backward()
                opt.step()
        if path:
            torch.save({"enc": enc.state_dict(), "dec": dec.state_dict()}, path)
    enc.eval()
    dec.eval()

    def encode(X):
        with torch.no_grad():
            x = torch.tensor(np.asarray(X, dtype=np.float32))
            z = enc(x.view(-1, 1, 28, 28)) if kind == "cnn" else enc(x)
            return z.reshape(len(x), -1).numpy()

    def decode(Z, shape=None):
        with torch.no_grad():
            z = torch.tensor(np.asarray(Z, dtype=np.float32))
            if kind == "cnn":
                z = z.view(-1, 64, 3, 3)
            return torch.sigmoid(dec(z)).reshape(len(z), 784).numpy()
    return encode, decode


class VAE:
    """A VAE for 784-pixel images: encoder 784-400-(mu, log sigma^2) with a 20-dimensional latent space, decoder
    20-400-784 with a Bernoulli likelihood; the loss is the negative ELBO (20.102) with the closed-form KL (20.103)."""

    def __init__(self, torch, latent=20, hidden=400):
        nn = torch.nn
        self.torch = torch
        self.enc = nn.Sequential(nn.Linear(784, hidden), nn.ReLU())
        self.mu = nn.Linear(hidden, latent)
        self.lv = nn.Linear(hidden, latent)
        self.dec = nn.Sequential(nn.Linear(latent, hidden), nn.ReLU(), nn.Linear(hidden, 784))

    def parameters(self):
        return list(self.enc.parameters()) + list(self.mu.parameters()) + list(self.lv.parameters()) + list(self.dec.parameters())

    def elbo_terms(self, x, g=None, sample=True):
        torch = self.torch
        h = self.enc(x)
        mu, lv = self.mu(h), self.lv(h)
        eps = torch.randn(mu.shape, generator=g) if sample else torch.zeros_like(mu)
        z = mu + torch.exp(0.5 * lv) * eps                                      # reparameterisation (20.101)
        logits = self.dec(z)
        rec = torch.nn.functional.binary_cross_entropy_with_logits(logits, x, reduction="none").sum(1)
        kl = 0.5 * (torch.exp(lv) + mu ** 2 - 1 - lv).sum(1)                    # (20.103)
        return rec, kl, mu, lv


def train_vae_ae(Xtr, epochs=15, seed=0, bs=128, lr=1e-3, latent=20, tag="vae_ae"):
    """Train the VAE and a deterministic autoencoder of the same shape (20-dimensional code) on Xtr.
    Returns dict of numpy-level functions: vae_enc_mean, vae_dec, ae_enc, ae_dec."""
    torch = _torch()
    p_vae, p_ae = _cache_path(tag + "_vae"), _cache_path(tag + "_ae")
    torch.manual_seed(seed)
    vae = VAE(torch, latent)
    ae_enc, ae_dec = make_mlp_ae(torch, 400, latent, act="relu")
    if os.path.exists(p_vae) and os.path.exists(p_ae):
        sd = torch.load(p_vae)
        for m, k in [(vae.enc, "enc"), (vae.mu, "mu"), (vae.lv, "lv"), (vae.dec, "dec")]:
            m.load_state_dict(sd[k])
        sd = torch.load(p_ae)
        ae_enc.load_state_dict(sd["enc"])
        ae_dec.load_state_dict(sd["dec"])
    else:
        Xt = torch.tensor(Xtr)
        n = len(Xt)
        g = torch.Generator().manual_seed(seed)
        o1 = torch.optim.Adam(vae.parameters(), lr=lr)
        o2 = torch.optim.Adam(list(ae_enc.parameters()) + list(ae_dec.parameters()), lr=lr)
        for ep in range(epochs):
            perm = torch.randperm(n, generator=g)
            for i in range(0, n, bs):
                xb = Xt[perm[i:i + bs]]
                rec, kl, _, _ = vae.elbo_terms(xb, g)
                loss = (rec + kl).mean()
                o1.zero_grad()
                loss.backward()
                o1.step()
                l2 = torch.nn.functional.binary_cross_entropy_with_logits(ae_dec(ae_enc(xb)), xb, reduction="none").sum(1).mean()
                o2.zero_grad()
                l2.backward()
                o2.step()
        torch.save({"enc": vae.enc.state_dict(), "mu": vae.mu.state_dict(), "lv": vae.lv.state_dict(), "dec": vae.dec.state_dict()}, p_vae)
        torch.save({"enc": ae_enc.state_dict(), "dec": ae_dec.state_dict()}, p_ae)

    def vae_enc_mean(X):
        with torch.no_grad():
            return vae.mu(vae.enc(torch.tensor(np.asarray(X, dtype=np.float32)))).numpy()

    def vae_dec(Z):
        with torch.no_grad():
            return torch.sigmoid(vae.dec(torch.tensor(np.asarray(Z, dtype=np.float32)))).numpy()

    def ae_enc_(X):
        with torch.no_grad():
            return ae_enc(torch.tensor(np.asarray(X, dtype=np.float32))).numpy()

    def ae_dec_(Z):
        with torch.no_grad():
            return torch.sigmoid(ae_dec(torch.tensor(np.asarray(Z, dtype=np.float32)))).numpy()
    return dict(vae_enc_mean=vae_enc_mean, vae_dec=vae_dec, ae_enc=ae_enc_, ae_dec=ae_dec_, vae=vae, torch=torch)


# =========================================================================== figures: Sections 20.1 and 20.2
def _img_grid(fig_or_ax, imgs, nrow, ncol, cmap="gray_r", vmin=None, vmax=None):
    """Tile 28 x 28 images into one array and show it on `ax`."""
    ax = fig_or_ax
    h = w = int(np.sqrt(imgs.shape[1]))
    tile = np.ones((nrow * h, ncol * w)) * (np.nan if cmap is None else 0)
    for k, im in enumerate(imgs[:nrow * ncol]):
        i, j = divmod(k, ncol)
        tile[i * h:(i + 1) * h, j * w:(j + 1) * w] = im.reshape(h, w)
    ax.imshow(tile, cmap=cmap, vmin=vmin, vmax=vmax, interpolation="nearest")
    ax.set_xticks([])
    ax.set_yticks([])


def correlated_2d(n, seed=1, angle=0.5, sd=(1.6, 0.45)):
    rng = np.random.default_rng(seed)
    Rm = np.array([[np.cos(angle), -np.sin(angle)], [np.sin(angle), np.cos(angle)]])
    return (rng.normal(size=(n, 2)) * np.array(sd)) @ Rm.T


def fig_20_1(out=None):
    """PCA from 2-D to 1-D: data, reconstructions on the first principal axis."""
    X = correlated_2d(24, seed=2)
    mu, lam, U = pca_eig(X)
    w = U[:, :1]
    Xh = mu + (X - mu) @ w @ w.T
    fig, ax = plt.subplots(figsize=(4.0, 3.6))
    t = np.array([-5, 5])
    ax.plot(mu[0] + t * w[0, 0], mu[1] + t * w[1, 0], color=GREY, lw=1, zorder=1)
    for a, b in zip(X, Xh):
        ax.plot([a[0], b[0]], [a[1], b[1]], color="#bbbbbb", lw=0.8, zorder=1)
    ax.scatter(*X.T, s=26, facecolors="none", edgecolors=RED, label="data $x_n$", zorder=3)
    ax.scatter(*Xh.T, s=22, color=BLUE, label="reconstruction $\\hat x_n$", zorder=3)
    ax.scatter(*mu, s=40, color=RED, marker="o", zorder=4, label="mean")
    ax.set_xlim(-4.5, 4.5)
    ax.set_ylim(-4.5, 4.5)
    ax.set_aspect("equal")
    ax.legend(loc="upper left", fontsize=8)
    ax.set_title("PCA, $D=2$ to $L=1$")
    savefig(fig, CH, "fig20-1", out)


def _digit_pca_data(digit=9):
    Xtr, ytr, _, _ = mnist_subset()
    return Xtr[ytr == digit].astype(float)


def fig_20_2(out=None):
    """PCA of the MNIST nines projected to 2-D, with the quantile grid and the nearest images."""
    X = _digit_pca_data(9)
    mu, lam, U = pca_eig(X)
    Z = (X - mu) @ U[:, :2]
    q = [5, 25, 50, 75, 95]
    gx, gy = np.percentile(Z[:, 0], q), np.percentile(Z[:, 1], q)
    fig, axes = plt.subplots(1, 2, figsize=(8.2, 4.0), gridspec_kw=dict(width_ratios=[1.1, 1]))
    ax = axes[0]
    ax.scatter(*Z.T, s=5, color=BLUE, alpha=0.5)
    sel = []
    for yy in gy[::-1]:
        for xx in gx:
            ax.plot([xx], [yy], "+", color=GREY, ms=7, zorder=2)
            j = int(np.argmin((Z[:, 0] - xx) ** 2 + (Z[:, 1] - yy) ** 2))
            sel.append(j)
    ax.scatter(*Z[sel].T, s=70, facecolors="none", edgecolors=RED, lw=1.4, zorder=3)
    ax.set_xlabel("first principal component")
    ax.set_ylabel("second principal component")
    ax.set_title("Projection of %d nines" % len(Z))
    ax = axes[1]
    _img_grid(ax, X[sel], 5, 5)
    ax.set_title("the circled images (grid quantiles 5, 25, 50, 75, 95 %)")
    savefig(fig, CH, "fig20-2", out)
    return Z, sel


def fig_20_3(out=None):
    """Mean and first three principal components of MNIST digits (stand-in for the Olivetti faces)."""
    Xtr, ytr, _, _ = mnist_subset()
    X = Xtr[:5000].astype(float)
    mu, lam, U = pca_eig(X)
    fig, axes = plt.subplots(1, 2, figsize=(8.0, 2.6), gridspec_kw=dict(width_ratios=[1, 1.15]))
    _img_grid(axes[0], X[:32], 4, 8)
    axes[0].set_title("(a) 32 of the images")
    h = 28
    tile = np.zeros((h, 4 * h))
    tile[:, :h] = mu.reshape(h, h)
    ax = axes[1]
    for j in range(3):
        v = U[:, j].reshape(h, h)
        tile[:, (j + 1) * h:(j + 2) * h] = v / np.abs(v).max()
    ax.imshow(tile[:, :h], extent=(0, 1, 0, 1), cmap="gray_r", vmin=0, vmax=1)
    ax.imshow(tile[:, h:], extent=(1, 4, 0, 1), cmap="RdBu_r", vmin=-1, vmax=1)
    ax.set_xticks([0.5, 1.5, 2.5, 3.5])
    ax.set_xticklabels(["mean", "basis 1", "basis 2", "basis 3"])
    ax.set_yticks([])
    ax.set_title("(b) mean and first three principal basis vectors")
    savefig(fig, CH, "fig20-3", out)


def fig_20_4(out=None):
    """Variance of the data projected onto three directions: v1, an intermediate v', and v2."""
    X = correlated_2d(300, seed=5, angle=0.55, sd=(1.1, 0.35))
    mu, lam, U = pca_eig(X)
    v1, v2 = U[:, 0], U[:, 1]
    vp = (v1 + v2) / np.linalg.norm(v1 + v2)
    fig, axes = plt.subplots(1, 2, figsize=(8.0, 3.4), gridspec_kw=dict(width_ratios=[1, 1.1]))
    ax = axes[0]
    ax.scatter(*X.T, s=6, color=GREY, alpha=0.6)
    for v, c, nm in [(v1, RED, "$v_1$"), (vp, GREEN, "$v'$"), (v2, BLUE, "$v_2$")]:
        ax.annotate("", xy=2.2 * v, xytext=(0, 0), arrowprops=dict(arrowstyle="->", color=c, lw=2))
        ax.text(*(2.5 * v), nm, color=c, ha="center", va="center", fontsize=11)
    ax.set_aspect("equal")
    ax.set_xlim(-3, 3)
    ax.set_ylim(-3, 3)
    ax.set_xlabel("$x_1$")
    ax.set_ylabel("$x_2$")
    ax = axes[1]
    bins = np.linspace(-4, 4, 41)
    for v, c, nm in [(v1, RED, "$v_1$"), (vp, GREEN, "$v'$"), (v2, BLUE, "$v_2$")]:
        z = (X - mu) @ v
        ax.hist(z, bins=bins, histtype="step", color=c, lw=1.6, label="%s: variance %.2f" % (nm, z.var()))
    ax.set_xlabel("$z_1 = v^\\top x$")
    ax.legend(fontsize=8)
    ax.set_title("projected data")
    savefig(fig, CH, "fig20-4", out)


def fig_20_5(out=None):
    """Effect of standardisation on PCA of height and weight."""
    h, w, male = davis()
    X = np.column_stack([h, w])
    fig, axes = plt.subplots(1, 2, figsize=(8.2, 3.6))
    for ax, std in zip(axes, (False, True)):
        Xp = (X - X.mean(0)) / X.std(0) if std else X
        mu, lam, U = pca_eig(Xp)
        ax.scatter(*Xp[~male].T, s=10, color=RED, label="female")
        ax.scatter(*Xp[male].T, s=10, color=BLUE, label="male")
        sc = 2.0 * np.sqrt(lam[0])
        ax.plot([mu[0] - sc * U[0, 0], mu[0] + sc * U[0, 0]], [mu[1] - sc * U[1, 0], mu[1] + sc * U[1, 0]], "k", lw=1.8)
        ax.set_xlabel("height" + (" (standardised)" if std else " (cm)"))
        ax.set_ylabel("weight" + (" (standardised)" if std else " (kg)"))
        ax.set_title("(%s) PCA of %s data" % ("b" if std else "a", "standardised" if std else "raw"))
        if not std:
            ax.legend(fontsize=8, loc="upper left")
    savefig(fig, CH, "fig20-5", out)


def _mnist_scree_data():
    Xtr, _, Xte, _ = mnist_subset()
    Xa, Xb = Xtr[:5000].astype(float) * 255, Xte.astype(float) * 255
    mu, lam, U = pca_eig(Xa)
    return Xa, Xb, mu, lam, U


def fig_20_6(out=None):
    """Reconstruction error of PCA on MNIST against L: training and test sets."""
    Xa, Xb, mu, lam, U = _mnist_scree_data()
    Ls = list(range(0, 401, 5))
    fig, axes = plt.subplots(1, 2, figsize=(8.2, 3.1))
    for ax, X, nm in [(axes[0], Xa, "(a) training set"), (axes[1], Xb, "(b) test set")]:
        e = np.sqrt(recon_error_curve(X, mu, U, Ls) / X.shape[1])
        ax.plot(Ls, e, "-o", color=BLUE, ms=2.5)
        ax.set_xlabel("number of components $L$")
        ax.set_ylabel("RMSE per pixel")
        ax.set_title(nm)
        ax.set_ylim(0, None)
    savefig(fig, CH, "fig20-6", out)


def fig_20_7(out=None):
    """Scree plot and fraction of variance explained for the MNIST training set."""
    Xa, Xb, mu, lam, U = _mnist_scree_data()
    fig, axes = plt.subplots(1, 2, figsize=(8.2, 3.0))
    axes[0].plot(np.arange(1, 51), lam[:50], "-o", color=BLUE, ms=3)
    axes[0].set_xlabel("component $j$")
    axes[0].set_ylabel("eigenvalue $\\lambda_j$")
    axes[0].set_title("(a) scree plot")
    F = np.cumsum(lam) / lam.sum()
    axes[1].plot(np.arange(1, 51), F[:50], "-o", color=BLUE, ms=3)
    axes[1].set_xlabel("number of components $L$")
    axes[1].set_ylabel("fraction of variance explained")
    axes[1].set_title("(b) $F_L$ of (20.27)")
    savefig(fig, CH, "fig20-7", out)


def fig_20_8(out=None):
    """Profile log likelihood (20.31) of the eigenvalues of the MNIST covariance."""
    Xa, Xb, mu, lam, U = _mnist_scree_data()
    Ls, ll = profile_loglik(lam[:50])
    fig, ax = plt.subplots(figsize=(4.2, 3.0))
    ax.plot(Ls, ll, "-o", color=BLUE, ms=3)
    j = int(np.argmax(ll))
    ax.axvline(Ls[j], color=RED, lw=1, ls="--")
    ax.text(Ls[j] + 1, ll.min() + 0.05 * (ll.max() - ll.min()), "$L^*=%d$" % Ls[j], color=RED)
    ax.set_xlabel("number of components $L$")
    ax.set_ylabel("profile log likelihood")
    savefig(fig, CH, "fig20-8", out)
    return int(Ls[j])


def fig_20_9(out=None):
    """The factor-analysis generative process with L = 1, D = 2 and Psi = sigma^2 I."""
    w = np.array([1.0, 0.7])
    mu = np.array([0.0, 0.0])
    s = 0.35
    rng = np.random.default_rng(3)
    fig, axes = plt.subplots(1, 3, figsize=(10.0, 3.1), gridspec_kw=dict(width_ratios=[1, 1.05, 1.05]))
    ax = axes[0]
    zz = np.linspace(-3.5, 3.5, 200)
    ax.plot(zz, np.exp(-zz ** 2 / 2) / np.sqrt(2 * np.pi), color=BLUE)
    for z0, c in [(-1.5, RED), (0.0, GREEN), (1.4, ORANGE)]:
        ax.plot([z0], [0], "o", color=c, ms=7, clip_on=False)
    ax.set_xlabel("$z$")
    ax.set_title("(a) prior $p(z)=\\mathcal{N}(0,1)$")
    ax = axes[1]
    t = np.array([-3, 3])
    ax.plot(mu[0] + t * w[0], mu[1] + t * w[1], color=GREY, lw=1)
    th = np.linspace(0, 2 * np.pi, 100)
    for z0, c in [(-1.5, RED), (0.0, GREEN), (1.4, ORANGE)]:
        c0 = mu + z0 * w
        ax.plot(c0[0] + 2 * s * np.cos(th), c0[1] + 2 * s * np.sin(th), color=c, lw=1.6)
        ax.plot(*c0, "o", color=c, ms=4)
        pts = c0 + s * rng.normal(size=(12, 2))
        ax.scatter(*pts.T, s=7, color=c, alpha=0.7)
    ax.set_aspect("equal")
    ax.set_xlim(-3.2, 3.2)
    ax.set_ylim(-2.5, 2.5)
    ax.set_title("(b) $p(x\\mid z)$ slides along $\\mu+zw$")
    ax = axes[2]
    z = rng.normal(size=400)
    Xs = mu + z[:, None] * w + s * rng.normal(size=(400, 2))
    ax.scatter(*Xs.T, s=5, color=BLUE, alpha=0.6)
    C = np.outer(w, w) + s ** 2 * np.eye(2)
    for ns in (1, 2):
        ex, ey = common.ellipse_xy(mu, C, ns)
        ax.plot(ex, ey, color=RED, lw=1.3)
    ax.set_aspect("equal")
    ax.set_xlim(-3.2, 3.2)
    ax.set_ylim(-2.5, 2.5)
    ax.set_title("(c) marginal $\\mathcal{N}(\\mu,ww^\\top+\\sigma^2I)$")
    savefig(fig, CH, "fig20-9", out)


def fig_20_10(out=None):
    """EM for PCA with D = 2, L = 1: two E steps and two M steps."""
    rng = np.random.default_rng(4)
    X = correlated_2d(14, seed=6, angle=0.5, sd=(1.5, 0.5))
    X = X - X.mean(0)
    Xt = X.T
    w0 = np.array([[0.3], [-1.0]])
    Ws = em_pca(Xt, w0, 3)
    fig, axes = plt.subplots(1, 4, figsize=(11.0, 2.8))
    t = np.array([-3.5, 3.5])
    for k, ax in enumerate(axes):
        step = k // 2                    # which W is held fixed in an E step; produced in an M step
        e_step = (k % 2 == 0)
        W = Ws[step] if e_step else Ws[step + 1]
        w = W[:, 0]
        z = (X @ w) / (w @ w) if e_step else (X @ Ws[step][:, 0]) / (Ws[step][:, 0] @ Ws[step][:, 0])
        proj = np.outer(z, Ws[step][:, 0] if e_step else Ws[step][:, 0])
        wdraw = Ws[step][:, 0] if e_step else Ws[step + 1][:, 0]
        ax.plot(t * wdraw[0] / np.linalg.norm(wdraw), t * wdraw[1] / np.linalg.norm(wdraw), color=BLUE, lw=2)
        pr = np.outer(z, Ws[step][:, 0])
        for a, b in zip(X, pr):
            ax.plot([a[0], b[0]], [a[1], b[1]], color="#aaaaaa", lw=0.8)
        ax.scatter(*X.T, marker="*", s=40, color=GREEN, zorder=3)
        ax.scatter(*pr.T, s=16, color="k", zorder=3)
        ax.set_xlim(-3.3, 3.3)
        ax.set_ylim(-2.6, 2.6)
        ax.set_aspect("equal")
        ax.set_title("(%s) %s step %d" % ("abcd"[k], "E" if e_step else "M", step + 1))
    savefig(fig, CH, "fig20-10", out)


def mixture_curve_data(n=300, seed=7):
    rng = np.random.default_rng(seed)
    th = rng.uniform(-1.5, 1.5, n)
    X = np.column_stack([1.6 * np.sin(th), 1.1 * np.cos(th) - 0.3]) + 0.09 * rng.normal(size=(n, 2))
    return X


def fig_20_12(out=None):
    """Mixture of PPCA with L = 1 latent dimension: K = 1 and K = 10 components."""
    X = mixture_curve_data()
    fig, axes = plt.subplots(1, 2, figsize=(8.4, 3.2))
    for ax, K in zip(axes, (1, 10)):
        m = mppca_em(X, K, 1, iters=80, seed=1)
        ax.scatter(*X.T, s=7, color=GREY, alpha=0.7)
        for k in range(K):
            Wk = m["W"][k]
            C = Wk @ Wk.T + m["s2"][k] * np.eye(2)
            ex, ey = common.ellipse_xy(m["mu"][k], C, 1.0)
            ax.plot(ex, ey, color=RED, lw=1.1)
            ax.plot(*m["mu"][k], "o", color=BLUE, ms=3)
        ax.set_aspect("equal")
        ax.set_xlim(-2.3, 2.3)
        ax.set_ylim(-1.6, 1.4)
        ax.set_title("(%s) $K=%d$, log likelihood %.1f" % ("ab"[K > 1], K, m["ll"][-1]))
    savefig(fig, CH, "fig20-12", out)


def binary_data(seed=0, N=150, D=16, flip=0.15):
    rng = np.random.default_rng(seed)
    protos = (rng.random((3, D)) < 0.5).astype(float)
    lab = np.repeat(np.arange(3), N // 3)
    X = protos[lab]
    X = np.where(rng.random(X.shape) < flip, 1 - X, X)
    return X, lab, protos


def fig_20_13(out=None):
    """Binary PCA by variational EM on 150 noisy 16-bit vectors from three prototypes."""
    X, lab, protos = binary_data()
    m = binary_pca(X, L=2, iters=60, seed=0)
    Ea = (m["m"] @ m["W"].T + m["b"])
    # posterior predictive (20.75) by the probit-type approximation sigma(a / sqrt(1 + pi v / 8)) with
    # a = E[w'z + b] and v = w' S w
    v = np.einsum("dl,nlk,dk->nd", m["W"], m["S"], m["W"])
    pp = sigmoid(Ea / np.sqrt(1 + np.pi * v / 8))
    fig, axes = plt.subplots(1, 4, figsize=(11.5, 3.0))
    axes[0].imshow(X, aspect="auto", cmap="gray_r", interpolation="nearest")
    axes[0].set_title("(a) noisy binary data")
    for c in range(3):
        axes[1].scatter(*m["m"][lab == c].T, s=12, color=[RED, BLUE, GREEN][c])
    axes[1].set_title("(b) latent embedding $E[z\\mid x]$")
    axes[2].imshow(pp, aspect="auto", cmap="gray_r", vmin=0, vmax=1, interpolation="nearest")
    axes[2].set_title("(c) predicted probability")
    axes[3].imshow((pp > 0.5).astype(float), aspect="auto", cmap="gray_r", interpolation="nearest")
    axes[3].set_title("(d) thresholded at 0.5")
    for a in (axes[0], axes[2], axes[3]):
        a.set_xlabel("bit $d$")
        a.set_ylabel("example $n$")
    savefig(fig, CH, "fig20-13", out)
    return float((pp > 0.5).astype(float).__ne__(protos[lab]).mean()), float((X != protos[lab]).mean())


# =========================================================================== figures: Section 20.3 (autoencoders)
def cached_npz(name, fn):
    path = os.path.join(CACHE_DIR, "ch20_" + name + ".npz")
    if os.path.exists(path):
        d = np.load(path)
        return {k: d[k] for k in d.files}
    res = fn()
    np.savez_compressed(path, **res)
    return res


def tsne_embed(X, name, perplexity=30, n_iter=500, lr=100.0):
    return cached_npz(name, lambda: dict(Z=tsne(X, perplexity, n_iter=n_iter, lr=lr)[0]))["Z"]


def _rec_rows(ax, X_in, X_out, n=5, title=None):
    _img_grid(ax, np.vstack([X_in[:n], X_out[:n]]), 2, n)
    if title:
        ax.set_title(title, fontsize=9)


def fig_20_17(out=None):
    """Autoencoder reconstructions: an MLP and a CNN bottleneck autoencoder (MNIST stand-in for Fashion-MNIST)."""
    Xtr, ytr, Xte, yte = mnist_subset()
    e1, d1 = train_ae("mlp", Xtr, 20, tag="mlp_ae")
    e2, d2 = train_ae("cnn", Xtr, 5, tag="cnn_ae")
    r1, r2 = d1(e1(Xte[:5])), d2(e2(Xte[:5]))
    fig, axes = plt.subplots(2, 1, figsize=(4.6, 4.2))
    _rec_rows(axes[0], Xte, r1, 5, "(a) MLP 784-100-30 (20 epochs)")
    _rec_rows(axes[1], Xte, r2, 5, "(b) CNN, 3 x 3 x 64 bottleneck (5 epochs)")
    savefig(fig, CH, "fig20-17", out)
    mse = lambda a, b: float(((a - b) ** 2).mean())
    return mse(d1(e1(Xte)), Xte), mse(d2(e2(Xte)), Xte)


def fig_20_18(out=None):
    """t-SNE of the latent codes of the two autoencoders of Figure 20.17 for 1000 held-out images."""
    Xtr, ytr, Xte, yte = mnist_subset()
    e1, _ = train_ae("mlp", Xtr, 20, tag="mlp_ae")
    e2, _ = train_ae("cnn", Xtr, 5, tag="cnn_ae")
    fig, axes = plt.subplots(1, 2, figsize=(8.6, 3.9))
    for ax, e, nm, key in [(axes[0], e1, "(a) MLP", "tsne_mlp"), (axes[1], e2, "(b) CNN", "tsne_cnn")]:
        Z = tsne_embed(e(Xte[:1000]), key)
        for c in range(10):
            ax.scatter(*Z[yte[:1000] == c].T, s=6, color=TEN[c], label=str(c))
        ax.set_title(nm + ": t-SNE of the latent codes")
        ax.set_xticks([])
        ax.set_yticks([])
    axes[1].legend(ncol=2, fontsize=7, markerscale=2, loc="center left", bbox_to_anchor=(1.0, 0.5), title="digit")
    savefig(fig, CH, "fig20-18", out)


def fig_20_19(out=None):
    """Denoising autoencoders: Gaussian corruption and Bernoulli dropout corruption."""
    Xtr, ytr, Xte, yte = mnist_subset()
    fig, axes = plt.subplots(1, 2, figsize=(8.6, 2.5))
    rng = np.random.default_rng(0)
    for ax, kind, noise, tag, nm in [(axes[0], "g", ("gauss", 0.4), "dae_g", "(a) Gaussian noise, sd 0.4"),
                                      (axes[1], "d", ("drop", 0.4), "dae_d", "(b) dropout noise, p = 0.4")]:
        e, d = train_ae("mlp", Xtr, 20, noise=noise, tag=tag)
        x = Xte[:5]
        xn = (x + noise[1] * rng.normal(size=x.shape)).clip(0, 1) if kind == "g" else x * (rng.random(x.shape) > noise[1])
        _img_grid(ax, np.vstack([xn, d(e(xn.astype(np.float32)))]), 2, 5)
        ax.set_title(nm + "\ntop: corrupted input, bottom: output", fontsize=9)
    savefig(fig, CH, "fig20-19", out)


def arc_density(n_comp=80, s0=0.04):
    """A thin curved 1-D data manifold in 2-D as a mixture of isotropic Gaussians (so that the score is known)."""
    th = np.linspace(0.15 * np.pi, 0.85 * np.pi, n_comp)
    C = np.column_stack([np.cos(th), 0.8 * np.sin(th) - 0.3])
    return C, s0


def mixture_score(x, C, s):
    """grad_x log of the equal-weight isotropic Gaussian mixture with centres C and standard deviation s."""
    d2 = ((x[:, None, :] - C[None]) ** 2).sum(-1)
    lw = -d2 / (2 * s ** 2)
    w = np.exp(lw - lw.max(1, keepdims=True))
    w /= w.sum(1, keepdims=True)
    return (w[:, :, None] * (C[None] - x[:, None, :])).sum(1) / s ** 2


def fig_20_20(out=None):
    """The residual of a denoising autoencoder is sigma^2 times the score of the data density."""
    torch = _torch()
    C, s0 = arc_density()
    sig = 0.15
    rng = np.random.default_rng(0)
    path = _cache_path("dae_field")
    net = torch.nn.Sequential(torch.nn.Linear(2, 128), torch.nn.Tanh(), torch.nn.Linear(128, 128), torch.nn.Tanh(), torch.nn.Linear(128, 2))
    if os.path.exists(path):
        net.load_state_dict(torch.load(path))
    else:
        opt = torch.optim.Adam(net.parameters(), lr=2e-3)
        for it in range(6000):
            idx = rng.integers(0, len(C), 512)
            x = C[idx] + s0 * rng.normal(size=(512, 2))
            xt = x + sig * rng.normal(size=x.shape)
            xt_, x_ = torch.tensor(xt, dtype=torch.float32), torch.tensor(x, dtype=torch.float32)
            loss = ((net(xt_) - x_) ** 2).sum(1).mean()
            opt.zero_grad()
            loss.backward()
            opt.step()
        torch.save(net.state_dict(), path)
    g = np.linspace(-1.6, 1.6, 17)
    G = np.stack(np.meshgrid(g, np.linspace(-1.4, 1.2, 14)), -1).reshape(-1, 2)
    G = G[np.sqrt(sqdist(G, C)).min(1) < 0.55]          # draw the field near the data curve only
    with torch.no_grad():
        R = net(torch.tensor(G, dtype=torch.float32)).numpy() - G
    s_eff = np.sqrt(s0 ** 2 + sig ** 2)
    Sc = sig ** 2 * mixture_score(G, C, s_eff)         # exact optimal residual (Tweedie)
    fig, axes = plt.subplots(1, 2, figsize=(8.8, 3.5))
    for ax, V, nm in [(axes[0], R, "(a) trained DAE: $r(\\tilde x)-\\tilde x$"), (axes[1], Sc, "(b) exact: $\\sigma^2\\nabla\\log p_\\sigma(\\tilde x)$")]:
        ax.plot(C[:, 0], C[:, 1], "-", color=RED, lw=1.5)
        ax.quiver(G[:, 0], G[:, 1], V[:, 0], V[:, 1], angles="xy", scale_units="xy", scale=1.0, color=BLUE, width=0.004)
        ax.set_xlim(-1.8, 1.8)
        ax.set_ylim(-1.6, 1.4)
        ax.set_aspect("equal")
        ax.set_title(nm)
    savefig(fig, CH, "fig20-20", out)
    return float(np.sqrt(((R - Sc) ** 2).sum(1).mean() / (Sc ** 2).sum(1).mean()))


def fig_20_21(out=None):
    """Neuron activity of sparse autoencoders: no penalty, L1 penalty, KL penalty on the mean activation."""
    Xtr, ytr, Xte, yte = mnist_subset()
    cfg = [("none", dict(), "no penalty"), ("l1", dict(lam_l1=1.5), "$\\ell_1$ penalty"), ("kl", dict(lam_kl=40.0, target=0.1), "KL penalty")]
    fig, axes = plt.subplots(3, 3, figsize=(9.6, 6.4))
    stats_ = {}
    for j, (tag, kw, nm) in enumerate(cfg):
        e, d = train_ae("mlp", Xtr, 10, hidden=300, latent=300, sigmoid_latent=True, tag="sparse_" + tag, **kw)
        A = e(Xte[:1000])
        axes[0, j].imshow(A[:100], aspect="auto", cmap="gray_r", vmin=0, vmax=1, interpolation="nearest")
        axes[0, j].set_title("%s: 100 examples x 300 units" % nm, fontsize=9)
        axes[1, j].hist(A.ravel(), bins=40, weights=np.ones(A.size) / A.size * 100, color=BLUE)
        axes[1, j].set_title("overall mean activation = %.2f" % A.mean(), fontsize=9)
        axes[1, j].set_xlabel("activation")
        axes[1, j].set_ylabel("% of activations")
        mn = A.mean(0)
        axes[2, j].hist(mn, bins=30, weights=np.ones(300) / 300 * 100, color=GREEN)
        axes[2, j].set_xlabel("mean activation of a neuron")
        axes[2, j].set_ylabel("% of neurons")
        stats_[tag] = dict(mean=float(A.mean()), frac_off=float((mn < 0.01).mean()), mse=float(((d(e(Xte)) - Xte) ** 2).mean()))
    fig.tight_layout()
    savefig(fig, CH, "fig20-21", out)
    return stats_


def _vae_pair():
    Xtr, ytr, Xte, yte = mnist_subset()
    return train_vae_ae(Xtr, epochs=15), Xte, yte


def fig_20_24(out=None):
    """Reconstructions by a VAE and by a deterministic autoencoder with a 20-dimensional code."""
    m, Xte, yte = _vae_pair()
    fig, axes = plt.subplots(2, 1, figsize=(5.6, 3.6))
    _rec_rows(axes[0], Xte, m["vae_dec"](m["vae_enc_mean"](Xte[:8])), 8, "(a) VAE (decoding the posterior mean)")
    _rec_rows(axes[1], Xte, m["ae_dec"](m["ae_enc"](Xte[:8])), 8, "(b) deterministic autoencoder")
    savefig(fig, CH, "fig20-24", out)
    return (float(((m["vae_dec"](m["vae_enc_mean"](Xte)) - Xte) ** 2).mean()), float(((m["ae_dec"](m["ae_enc"](Xte)) - Xte) ** 2).mean()))


def fig_20_25(out=None):
    """Digits sampled from the prior: z ~ N(0, I) decoded by the VAE and by the autoencoder."""
    m, Xte, yte = _vae_pair()
    Z = np.random.default_rng(0).normal(size=(40, 20))
    fig, axes = plt.subplots(1, 2, figsize=(8.0, 2.6))
    _img_grid(axes[0], m["vae_dec"](Z), 4, 10)
    axes[0].set_title("(a) VAE: decoder at $z\\sim\\mathcal{N}(0,I)$")
    _img_grid(axes[1], m["ae_dec"](Z), 4, 10)
    axes[1].set_title("(b) autoencoder: decoder at $z\\sim\\mathcal{N}(0,I)$")
    savefig(fig, CH, "fig20-25", out)


def fig_20_26(out=None):
    """t-SNE of the 20-dimensional latent codes of the VAE and of the autoencoder."""
    m, Xte, yte = _vae_pair()
    fig, axes = plt.subplots(1, 2, figsize=(8.6, 3.9))
    for ax, enc, nm, key in [(axes[0], m["vae_enc_mean"], "(a) VAE", "tsne_vae"), (axes[1], m["ae_enc"], "(b) autoencoder", "tsne_ae")]:
        Z = tsne_embed(enc(Xte[:1000]), key)
        for c in range(10):
            ax.scatter(*Z[yte[:1000] == c].T, s=6, color=TEN[c], label=str(c))
        ax.set_title(nm + ": t-SNE of the latent codes")
        ax.set_xticks([])
        ax.set_yticks([])
    axes[1].legend(ncol=2, fontsize=7, markerscale=2, loc="center left", bbox_to_anchor=(1.0, 0.5), title="digit")
    savefig(fig, CH, "fig20-26", out)


def fig_20_27(out=None):
    """Linear interpolation in latent space between two test images: VAE against autoencoder."""
    m, Xte, yte = _vae_pair()
    pairs = [(int(np.where(yte == a)[0][0]), int(np.where(yte == b)[0][0])) for a, b in [(1, 7), (3, 8), (0, 6)]]
    fig, axes = plt.subplots(2, 1, figsize=(6.4, 4.6))
    for ax, enc, dec, nm in [(axes[0], m["vae_enc_mean"], m["vae_dec"], "(a) VAE"), (axes[1], m["ae_enc"], m["ae_dec"], "(b) autoencoder")]:
        rows = []
        for i, j in pairs:
            z1, z2 = enc(Xte[[i]])[0], enc(Xte[[j]])[0]
            lam = np.linspace(0, 1, 10)
            rows.append(dec(lam[:, None] * z1 + (1 - lam[:, None]) * z2))
        _img_grid(ax, np.vstack(rows), 3, 10)
        ax.set_title(nm + ": $z=\\lambda z_1+(1-\\lambda)z_2$, $\\lambda$ from 0 to 1", fontsize=9)
    savefig(fig, CH, "fig20-27", out)


# =========================================================================== figures: Section 20.4 (manifold learning)
def fig_20_29(out=None):
    """The image manifold: 360 rotated copies of one digit lie on a closed curve in the plane of the first two PCs."""
    from scipy import ndimage
    Xtr, ytr, _, _ = mnist_subset()
    img = Xtr[np.where(ytr == 6)[0][3]].reshape(28, 28).astype(float)
    ims = np.array([ndimage.rotate(img, a, reshape=False, order=1, mode="constant") for a in range(360)]).reshape(360, -1)
    mu, lam, U = pca_eig(ims)
    Z = (ims - mu) @ U[:, :2]
    fig, axes = plt.subplots(1, 3, figsize=(9.6, 3.0), gridspec_kw=dict(width_ratios=[0.8, 0.8, 1.6]))
    axes[0].imshow(img, cmap="gray_r")
    axes[0].set_title("(a) one image, $D=784$")
    rng = np.random.default_rng(0)
    axes[1].imshow((rng.random((28, 28)) < 0.5).astype(float), cmap="gray_r")
    axes[1].set_title("(b) a random point of $\\{0,1\\}^{784}$")
    for a in axes[:2]:
        a.set_xticks([])
        a.set_yticks([])
    sc = axes[2].scatter(*Z.T, c=np.arange(360), s=8, cmap="hsv")
    axes[2].set_aspect("equal")
    axes[2].set_xlabel("PC 1")
    axes[2].set_ylabel("PC 2")
    axes[2].set_title("(c) 360 rotations, projected to 2-D")
    fig.colorbar(sc, ax=axes[2], label="rotation angle (degrees)", fraction=0.046)
    savefig(fig, CH, "fig20-29", out)
    return float(lam[:2].sum() / lam.sum())


def fig_20_30(out=None):
    """The two running examples: the Swiss roll (3-D, 2-D manifold) and the UCI digits (64-D)."""
    X, t = swiss_roll(1000, 0, 0)
    Xd, yd = uci_digits()
    fig = plt.figure(figsize=(8.6, 3.5))
    ax = fig.add_subplot(1, 2, 1, projection="3d")
    ax.scatter(X[:, 0], X[:, 1], X[:, 2], c=t, cmap="Spectral", s=6)
    ax.view_init(8, -70)
    ax.set_title("(a) Swiss roll, $N=1000$")
    ax = fig.add_subplot(1, 2, 2)
    _img_grid(ax, Xd[:100] / 16.0, 10, 10, cmap="gray_r", vmin=0, vmax=1)
    ax.set_title("(b) UCI digits, $8\\times8$ pixels")
    savefig(fig, CH, "fig20-30", out)


def _manifold_fig(name, embed, title, out, digits_labels=True):
    """Two panels: the embedding of the Swiss roll (coloured by position along the roll) and of the UCI digits."""
    X, t = swiss_roll(1000, 0, 0)
    Xd, yd = uci_digits()
    fig, axes = plt.subplots(1, 2, figsize=(8.8, 3.7))
    Z1 = embed(X, "roll")
    axes[0].scatter(*Z1.T, c=t, cmap="Spectral", s=7)
    axes[0].set_title("(a) Swiss roll")
    Z2 = embed(Xd, "digits")
    for c in range(10):
        axes[1].scatter(*Z2[yd == c].T, s=5, color=TEN[c], label=str(c))
    axes[1].set_title("(b) UCI digits")
    axes[1].legend(ncol=2, fontsize=6.5, markerscale=2.2, loc="center left", bbox_to_anchor=(1.0, 0.5), title="digit")
    for a in axes:
        a.set_xticks([])
        a.set_yticks([])
    fig.suptitle(title, fontsize=10.5, y=1.0)
    savefig(fig, CH, name, out)


def fig_20_31(out=None):
    """Metric MDS (SMACOF) of the Swiss roll and the UCI digits."""
    def embed(X, key):
        def run_():
            D = np.sqrt(sqdist(X))
            Z0, _ = classical_mds(D ** 2, 2)
            Z, st = smacof(D, 2, iters=300, init=Z0)
            return dict(Z=Z, stress=st)
        return cached_npz("mds_" + key, run_)["Z"]
    _manifold_fig("fig20-31", embed, "Metric MDS (SMACOF)", out)


def fig_20_32(out=None):
    """Distance along the manifold against distance in the ambient space, on the Swiss roll."""
    X, t = swiss_roll(1000, 0, 0)
    A, Dm = knn_graph(X, 10)
    G = csgraph.shortest_path(sparse.csr_matrix(A), method="D", directed=False)
    # two points on adjacent layers of the roll: close in space, far along the manifold
    i = int(np.argmin(np.abs(t - 7.0) + 3 * np.abs(X[:, 1] - 0)))
    cand = np.where(np.abs(t - t[i]) > 3.2)[0]
    j = int(cand[np.argmin(Dm[i, cand])])
    prev = csgraph.shortest_path(sparse.csr_matrix(A), method="D", directed=False, return_predecessors=True)[1]
    path = [j]
    while path[-1] != i:
        path.append(prev[i, path[-1]])
    fig = plt.figure(figsize=(8.8, 3.6))
    ax = fig.add_subplot(1, 2, 1, projection="3d")
    ax.scatter(X[:, 0], X[:, 1], X[:, 2], c=t, cmap="Spectral", s=4, alpha=0.5)
    P = X[path]
    ax.plot(P[:, 0], P[:, 1], P[:, 2], color="k", lw=2)
    ax.plot([X[i, 0], X[j, 0]], [X[i, 1], X[j, 1]], [X[i, 2], X[j, 2]], color=RED, lw=2, ls="--")
    ax.view_init(8, -70)
    ax.set_title("(a) ambient %.1f, along the graph %.1f" % (Dm[i, j], G[i, j]), fontsize=9)
    ax = fig.add_subplot(1, 2, 2)
    sub = np.random.default_rng(0).choice(len(X), 600, replace=False)
    ii, jj = np.meshgrid(sub, sub)
    ax.scatter(Dm[ii, jj].ravel()[::7], G[ii, jj].ravel()[::7], s=1.5, color=BLUE, alpha=0.4, rasterized=True)
    ax.plot([0, 40], [0, 40], color=GREY, lw=1)
    ax.set_xlabel("Euclidean distance")
    ax.set_ylabel("shortest-path distance on the 10-NN graph")
    ax.set_title("(b) the two distances disagree for far pairs", fontsize=9)
    savefig(fig, CH, "fig20-32", out)
    return float(Dm[i, j]), float(G[i, j])


def fig_20_33(out=None):
    """Isomap on the Swiss roll and on the UCI digits."""
    def embed(X, key):
        return cached_npz("isomap_" + key, lambda: dict(Z=isomap(X, 10, 2)[0]))["Z"]
    _manifold_fig("fig20-33", embed, "Isomap, $K=10$", out)


def fig_20_34(out=None):
    """Isomap on a noisy Swiss roll: short-circuit edges distort the embedding."""
    Xn, t = swiss_roll(1000, 0.5, 0)
    fig = plt.figure(figsize=(8.8, 3.5))
    ax = fig.add_subplot(1, 3, 1, projection="3d")
    ax.scatter(Xn[:, 0], Xn[:, 1], Xn[:, 2], c=t, cmap="Spectral", s=4)
    ax.view_init(8, -70)
    ax.set_title("(a) noisy roll (sd 0.5)", fontsize=9)
    for k, (kk, nm) in enumerate([(10, "(b) Isomap, $K=10$"), (20, "(c) Isomap, $K=20$: short circuits")]):
        Z = cached_npz("isomap_noisy_%d" % kk, lambda: dict(Z=isomap(Xn, kk, 2)[0]))["Z"]
        ax = fig.add_subplot(1, 3, 2 + k)
        ax.scatter(*Z.T, c=t, cmap="Spectral", s=6)
        ax.set_title(nm, fontsize=9)
        ax.set_xticks([])
        ax.set_yticks([])
    savefig(fig, CH, "fig20-34", out)


def three_blobs(n=60, seed=2):
    rng = np.random.default_rng(seed)
    centres = np.array([[-1.5, -0.3], [1.4, -0.7], [0.0, 1.6]])
    return np.vstack([c + 0.32 * rng.normal(size=(n, 2)) for c in centres])


def kpca_project(Xtr, Xnew, gamma):
    """Scores of the points Xnew on the kernel principal components fitted to Xtr (centred kernel, test-point
    centring included): K~_*j = k_*j - mean_i k_*i - mean_i K_ij + mean K, scores = K~_* U Lambda^{-1/2}."""
    K = rbf_kernel(Xtr, gamma=gamma)
    Ks = rbf_kernel(Xnew, Xtr, gamma=gamma)
    Kc = center_gram(K)
    lam, U = np.linalg.eigh((Kc + Kc.T) / 2)
    o = np.argsort(lam)[::-1]
    lam, U = lam[o], U[:, o]
    Ksc = Ks - Ks.mean(1, keepdims=True) - K.mean(0, keepdims=True) + K.mean()
    return Ksc @ U / np.sqrt(np.maximum(lam, 1e-12)), lam / len(Xtr)


def fig_20_35(out=None):
    """Eight kernel principal components of 2-D data with an RBF kernel (sigma^2 = 0.1)."""
    X = three_blobs()
    gamma = 1.0 / (2 * 0.1)
    g = np.linspace(-3, 3, 70)
    G = np.stack(np.meshgrid(g, g), -1).reshape(-1, 2)
    S, lam = kpca_project(X, G, gamma)
    fig, axes = plt.subplots(2, 4, figsize=(9.6, 4.9))
    for k, ax in enumerate(axes.ravel()):
        ax.contourf(g, g, S[:, k].reshape(70, 70), 18, cmap="RdBu_r")
        ax.scatter(*X.T, s=4, color="k")
        ax.set_title("$\\lambda=%.3f$" % lam[k], fontsize=9)
        ax.set_xticks([])
        ax.set_yticks([])
    savefig(fig, CH, "fig20-35", out)
    return lam[:8]


def fig_20_36(out=None):
    """Kernel PCA with an RBF kernel (bandwidth by the median heuristic) on the Swiss roll and the digits."""
    def embed(X, key):
        K = rbf_kernel(X, gamma=1.0 / np.median(sqdist(X)))
        return kernel_pca(K, 2)[0]
    _manifold_fig("fig20-36", embed, "Kernel PCA, RBF kernel with $\\gamma=1/\\mathrm{median}\\,d_{ij}^2$", out)


def fig_20_37(out=None):
    """Locally linear embedding of the Swiss roll and of the UCI digits."""
    def embed(X, key):
        return cached_npz("lle_" + key, lambda: dict(Z=lle(X, 12 if key == "roll" else 10, 2)[0]))["Z"]
    _manifold_fig("fig20-37", embed, "Locally linear embedding", out)


def fig_20_38(out=None):
    """Laplacian eigenmaps (spectral embedding) of the Swiss roll and of the UCI digits."""
    def embed(X, key):
        Wm, _ = gaussian_knn_weights(X, 10)
        return laplacian_eigenmaps(Wm, 2)[0]
    _manifold_fig("fig20-38", embed, "Laplacian eigenmaps", out)


def fig_20_41(out=None):
    """t-SNE of the Swiss roll and of the UCI digits (perplexity 30)."""
    def embed(X, key):
        return tsne_embed(X, "tsne_" + key, 30, 600)
    _manifold_fig("fig20-41", embed, "t-SNE, perplexity 30", out)


def fig_20_42(out=None):
    """The effect of the perplexity: t-SNE of three 2-D clusters."""
    X = three_blobs(50)
    fig, axes = plt.subplots(2, 3, figsize=(9.2, 5.6))
    cols = np.repeat([RED, BLUE, GREEN], 50)
    axes[0, 0].scatter(*X.T, s=8, color=cols)
    axes[0, 0].set_aspect("equal")
    axes[0, 0].set_title("original 2-D data")
    for ax, pp in zip(axes.ravel()[1:], (2, 5, 30, 50, 100)):
        Z = tsne_embed(X, "tsne_blobs_%d" % pp, pp, 800, lr=50.0)
        ax.scatter(*Z.T, s=8, color=cols)
        ax.set_title("perplexity %d" % pp)
        ax.set_aspect("equal")
    for a in axes.ravel():
        a.set_xticks([])
        a.set_yticks([])
    savefig(fig, CH, "fig20-42", out)


# =========================================================================== supplementary figures
def fig_20_S1(out=None):
    """EM for PCA is subspace iteration: the angle to the principal subspace against the iteration."""
    rng = np.random.default_rng(0)
    D, L, N = 10, 2, 400
    lam_true = np.array([9.0, 6.0, 2.0, 1.2, 1, 0.8, 0.6, 0.5, 0.4, 0.3])
    Q, _ = np.linalg.qr(rng.normal(size=(D, D)))
    X = (rng.normal(size=(N, D)) * np.sqrt(lam_true)) @ Q.T
    X = X - X.mean(0)
    mu, lam, U = pca_eig(X)
    fig, ax = plt.subplots(figsize=(4.8, 3.2))
    for s_, c in [(1, BLUE), (2, RED), (3, GREEN)]:
        W0 = np.random.default_rng(s_).normal(size=(D, L))
        Ws = em_pca(X.T, W0, 25)
        ang = [subspace_angle(W, U[:, :L]) for W in Ws]
        ax.semilogy(ang, "-o", ms=3, color=c, lw=1.2)
    t = np.arange(26)
    ax.semilogy(t, 1.5 * (lam[L] / lam[L - 1]) ** t, "k--", lw=1, label="$(\\lambda_{L+1}/\\lambda_L)^t$")
    ax.set_xlabel("EM iteration $t$")
    ax.set_ylabel("largest principal angle (rad)")
    ax.legend()
    ax.set_ylim(1e-9, 3)
    savefig(fig, CH, "fig20-S1", out)
    return float(lam[L] / lam[L - 1])


def fig_20_S2(out=None):
    """The PPCA log likelihood at the closed-form estimate against a grid over (sigma^2, L eigen-directions)."""
    X = mixture_curve_data()
    X = np.hstack([X, 0.15 * np.random.default_rng(1).normal(size=(len(X), 3))])
    mu, lam, U = pca_eig(X)
    S = np.cov(X.T, bias=True)
    N = len(X)
    L = 2
    W, s2 = ppca_mle(S, L)
    s2g = np.exp(np.linspace(np.log(s2) - 1.5, np.log(s2) + 1.5, 120))
    ll = []
    for s_ in s2g:
        Wg = U[:, :L] * np.sqrt(np.maximum(lam[:L] - s_, 0))
        ll.append(ppca_loglik_S(Wg, s_, S, N) if s_ < lam[L - 1] else np.nan)
    fig, ax = plt.subplots(figsize=(4.6, 3.1))
    ax.plot(s2g, ll, color=BLUE)
    ax.axvline(s2, color=RED, ls="--", lw=1)
    ax.set_xscale("log")
    ax.set_xlabel("$\\sigma^2$ (with $W=U_L(\\Lambda_L-\\sigma^2I)^{1/2}$)")
    ax.set_ylabel("log likelihood")
    ax.set_title("maximum at the mean of the discarded eigenvalues")
    savefig(fig, CH, "fig20-S2", out)


def fig_20_S3(out=None):
    """The smoothest functions on the Swiss-roll neighbourhood graph: Laplacian eigenvectors."""
    X, t = swiss_roll(1000, 0, 0)
    Wm, _ = gaussian_knn_weights(X, 10)
    _, lam, Zall = laplacian_eigenmaps(Wm, 2)
    d = Wm.sum(1)
    Ls = np.diag(d) - Wm
    fig, axes = plt.subplots(1, 4, figsize=(10.5, 2.7))
    for k, ax in enumerate(axes):
        f = Zall[:, k + 1] if k < 3 else Zall[:, 10]
        ax.scatter(t, X[:, 1], c=f, cmap="RdBu_r", s=7)
        j = k + 1 if k < 3 else 10
        ax.set_title("eigenvector %d, $\\lambda=%.4f$\nDirichlet energy %.4f" % (j + 1, lam[j] if j < len(lam) else np.linalg.eigvalsh(np.diag(d ** -0.5) @ Ls @ np.diag(d ** -0.5))[j],
                                                                                (f @ Ls @ f) / (f @ (d * f))), fontsize=8)
        ax.set_xlabel("position along the roll")
        ax.set_yticks([])
    savefig(fig, CH, "fig20-S3", out)


def fig_20_S4(out=None):
    """The crowding problem: Gaussian and Student-t (nu = 1) similarity kernels, and the mass at large distance."""
    d = np.linspace(0, 6, 300)
    fig, axes = plt.subplots(1, 2, figsize=(8.4, 3.0))
    axes[0].plot(d, np.exp(-d ** 2), color=BLUE, label="Gaussian $e^{-d^2}$")
    axes[0].plot(d, 1 / (1 + d ** 2), color=RED, label="Student-t, $\\nu=1$: $(1+d^2)^{-1}$")
    axes[0].set_xlabel("distance $d$ in the embedding")
    axes[0].set_ylabel("unnormalised similarity")
    axes[0].legend(fontsize=8)
    axes[1].semilogy(d, np.exp(-d ** 2), color=BLUE)
    axes[1].semilogy(d, 1 / (1 + d ** 2), color=RED)
    axes[1].set_ylim(1e-10, 2)
    axes[1].set_xlabel("distance $d$")
    axes[1].set_title("log scale: the heavy tail")
    savefig(fig, CH, "fig20-S4", out)


# =========================================================================== figures: Section 20.5
def words_embedding(L=3):
    words, ctx, C = toy_corpus()
    Pp, pmi = ppmi(C)
    U, s, Vt = np.linalg.svd(Pp, full_matrices=False)
    return words, ctx, C, Pp, U[:, :L] * np.sqrt(s[:L]), s


def fig_20_45(out=None):
    """The parallelogram of word analogies in a PPMI-SVD embedding of a synthetic corpus (stand-in)."""
    words, ctx, C, Pp, V, s = words_embedding(3)
    mu = V.mean(0)
    Uc, sc, Vtc = np.linalg.svd(V - mu, full_matrices=False)
    Z = (V - mu) @ Vtc[:2].T
    fig, axes = plt.subplots(1, 2, figsize=(9.0, 3.6), gridspec_kw=dict(width_ratios=[1.2, 1], wspace=0.12))
    ax = axes[0]
    ax.scatter(*Z.T, s=18, color=BLUE)
    for i, w in enumerate(words):
        ax.text(Z[i, 0], Z[i, 1], " " + w, fontsize=8)
    for a, b in [("man", "woman"), ("king", "queen"), ("prince", "princess"), ("boy", "girl"), ("uncle", "aunt"), ("father", "mother")]:
        ia, ib = words.index(a), words.index(b)
        ax.annotate("", xy=Z[ib], xytext=Z[ia], arrowprops=dict(arrowstyle="->", color=RED, lw=1.2))
    ax.set_title("(a) embedding, first two PCs: gender arrows are parallel", fontsize=9)
    ax.set_xticks([])
    ax.set_yticks([])
    ax = axes[1]
    quads = [("man", "woman", "king", "queen"), ("man", "woman", "prince", "princess"), ("boy", "girl", "king", "queen"),
             ("king", "queen", "boy", "girl"), ("man", "king", "woman", "queen"), ("man", "boy", "woman", "girl"),
             ("uncle", "aunt", "king", "queen"), ("father", "mother", "prince", "princess")]
    res = [analogy(V, words, *q[:3]) == q[3] for q in quads]
    ax.axis("off")
    ax.set_title("(b) 3CosAdd: a : b :: c : ?  (answer, correct?)", fontsize=9)
    for i, q in enumerate(quads):
        pred = analogy(V, words, *q[:3])
        ax.text(0.0, 0.92 - 0.115 * i, "%s : %s :: %s : ?" % q[:3], fontsize=8.5, va="center")
        ax.text(0.62, 0.92 - 0.115 * i, "%s  %s" % (pred, "ok" if pred == q[3] else "wrong (expected %s)" % q[3]), fontsize=8.5, va="center",
                color=GREEN if pred == q[3] else RED)
    savefig(fig, CH, "fig20-45", out)
    return float(np.mean(res))


FIGURES = {
    "20.1": fig_20_1, "20.2": fig_20_2, "20.3": fig_20_3, "20.4": fig_20_4, "20.5": fig_20_5, "20.6": fig_20_6,
    "20.7": fig_20_7, "20.8": fig_20_8, "20.9": fig_20_9, "20.10": fig_20_10, "20.12": fig_20_12, "20.13": fig_20_13,
    "20.17": fig_20_17, "20.18": fig_20_18, "20.19": fig_20_19, "20.20": fig_20_20, "20.21": fig_20_21,
    "20.24": fig_20_24, "20.25": fig_20_25, "20.26": fig_20_26, "20.27": fig_20_27, "20.29": fig_20_29,
    "20.30": fig_20_30, "20.31": fig_20_31, "20.32": fig_20_32, "20.33": fig_20_33, "20.34": fig_20_34,
    "20.35": fig_20_35, "20.36": fig_20_36, "20.37": fig_20_37, "20.38": fig_20_38, "20.41": fig_20_41,
    "20.42": fig_20_42, "20.45": fig_20_45, "20.S1": fig_20_S1, "20.S2": fig_20_S2, "20.S3": fig_20_S3, "20.S4": fig_20_S4,
}


# =========================================================================== data for the browser demonstrations
PCA_SIGMAS = (0, 4, 8)
PPCA_ANGLE0, PPCA_NORM0, PPCA_RATIO = 80.0, 1.2, 0.15
TSNE_LR, TSNE_ITERS = 100.0, 300


def digits_noise_split(n=1000, ntrain=600):
    Xd, yd = uci_digits()
    perm = np.random.default_rng(0).permutation(len(Xd))[:n]
    X, y = Xd[perm], yd[perm]
    Z = np.round(np.random.default_rng(1).normal(size=X.shape), 3)
    return X, y, Z, ntrain


def pca_digit_reference(X, Z, ntrain, sigma, Lmax=40):
    """Reference numbers of the PCA demonstration: fit on the noisy training images, errors for L = 0 .. Lmax."""
    Xn = X + sigma * Z
    mu, lam, U = pca_eig(Xn[:ntrain])
    Ls = list(range(Lmax + 1))
    D = X.shape[1]
    tr = np.sqrt(recon_error_curve(Xn[:ntrain], mu, U, Ls) / D)
    te = np.sqrt(recon_error_curve(Xn[ntrain:], mu, U, Ls) / D)
    # test images reconstructed from the noisy fit, compared with the CLEAN test images
    Xc = Xn[ntrain:] - mu
    cl = []
    for L in Ls:
        Xh = mu + Xc @ U[:, :L] @ U[:, :L].T
        cl.append(np.sqrt(((Xh - X[ntrain:]) ** 2).mean()))
    Lp, ll = profile_loglik(lam[:Lmax])
    return dict(lam=r_(lam[:Lmax], 5), train=r_(tr, 5), test=r_(te, 5), clean=r_(cl, 5), Lstar=int(Lp[np.argmax(ll)]),
                Lbest=int(np.argmin(cl)), profile=r_(ll, 4))


def ppca_em_1d(X, w0, iters, mode):
    """EM for L = 1: mode 'pca' (sigma^2 = 0) or 'ppca' (sigma^2 learned); X is N x 2 and centred.
    Returns a list of dicts (w, s2, ll or None, err) for t = 0 .. iters."""
    N, D = X.shape
    S = X.T @ X / N
    w = np.array(w0, float)
    s2 = 0.0 if mode == "pca" else float(np.trace(S) / D)
    out = []

    def rec(w, s2):
        if mode == "ppca":
            ll = ppca_loglik_S(w[:, None], s2, S, N) / N
        else:
            ll = None
        z = X @ w / (w @ w)
        err = float(((X - np.outer(z, w)) ** 2).sum() / N)
        return dict(w=w.tolist(), s2=float(s2), ll=ll, err=err)
    out.append(rec(w, s2))
    for _ in range(iters):
        if mode == "pca":
            z = X @ w / (w @ w)
            w = (X.T @ z) / (z @ z)
        else:
            m = X @ w / (w @ w + s2)
            v = s2 / (w @ w + s2)
            w = (X.T @ m) / (m @ m + N * v)
            s2 = float(((X ** 2).sum() - 2 * (m * (X @ w)).sum() + (m @ m + N * v) * (w @ w)) / (N * D))
        out.append(rec(w, s2))
    return out


def sim_cloud(Zs, ratio, angle=30.0, sd1=1.6):
    t = np.deg2rad(angle)
    R = np.array([[np.cos(t), -np.sin(t)], [np.sin(t), np.cos(t)]])
    X = (Zs * np.array([sd1, sd1 * np.sqrt(ratio)])) @ R.T
    return X - X.mean(0)


def tsne_datasets():
    Xb = np.round(three_blobs(50), 4)
    Xd, yd = uci_digits()
    perm = np.random.default_rng(2).permutation(len(Xd))[:300]
    Xr, tr = swiss_roll(300, 0, 3)
    return dict(blobs=(Xb, np.repeat([0, 1, 2], 50)), digits=(Xd[perm], yd[perm]), roll=(np.round(Xr, 3), tr))


def export_json():
    os.makedirs(DATA_OUT, exist_ok=True)
    # 1. PCA demonstration on the digits
    X, y, Z, ntr = digits_noise_split()
    d1 = dict(X=X.astype(int).tolist(), y=y.tolist(), Z=Z.tolist(), ntrain=ntr, ref={str(s): pca_digit_reference(X, Z, ntr, s) for s in PCA_SIGMAS})
    with open(os.path.join(DATA_OUT, "ch20-pca-digits.json"), "w") as f:
        json.dump(d1, f, separators=(",", ":"))
    # 2. EM for PCA / PPCA
    Zs = np.round(np.random.default_rng(4).normal(size=(60, 2)), 4)
    h, w, male = davis()
    HW = np.column_stack([h, w])
    HW = np.round((HW - HW.mean(0)) / HW.std(0), 4)
    ref = {}
    w0 = PPCA_NORM0 * np.array([np.cos(np.deg2rad(PPCA_ANGLE0)), np.sin(np.deg2rad(PPCA_ANGLE0))])
    for name, Xs in (("sim", sim_cloud(Zs, PPCA_RATIO)), ("hw", HW - HW.mean(0))):
        S = Xs.T @ Xs / len(Xs)
        mu_, lam_, U_ = pca_eig(Xs)
        Wm, s2m = ppca_mle(S, 1)
        ref[name] = dict(lam=r_(lam_, 6), u1=r_(U_[:, 0], 6), mle=dict(w=r_(Wm[:, 0], 6), s2=float(s2m), ll=float(ppca_loglik_S(Wm, s2m, S, len(Xs)) / len(Xs))))
        for mode in ("pca", "ppca"):
            run = ppca_em_1d(Xs, w0, 30, mode)
            ref[name][mode] = [dict(w=r_(q["w"], 6), s2=round(q["s2"], 6), ll=None if q["ll"] is None else round(q["ll"], 6), err=round(q["err"], 6)) for q in run[:31]]
    d2 = dict(Z=Zs.tolist(), hw=HW.tolist(), male=[int(v) for v in male], angle0=PPCA_ANGLE0, norm0=PPCA_NORM0, ratio=PPCA_RATIO, ref=ref)
    with open(os.path.join(DATA_OUT, "ch20-ppca-em.json"), "w") as f:
        json.dump(d2, f, separators=(",", ":"))
    # 3. t-SNE
    ds = tsne_datasets()
    d3 = dict(lr=TSNE_LR, iters=TSNE_ITERS, data={}, ref={})
    for k, (Xk, lab) in ds.items():
        d3["data"][k] = dict(X=np.asarray(Xk).tolist(), lab=np.asarray(lab).tolist() if k != "roll" else r_(lab, 3))
    for k, pp, dof in [("blobs", 5, 1.0), ("blobs", 30, 1.0), ("digits", 30, 1.0), ("digits", 30, None), ("roll", 15, 1.0)]:
        Xk = ds[k][0]
        P, sig = sne_conditional_p(Xk, pp)
        Pj = (P + P.T) / (2 * len(Xk))
        kl_at = {}
        for tt_ in (0, 10, 20, 50, 100, TSNE_ITERS):                 # the first iterations are deterministic to rounding;
            kl_at[str(tt_)] = float(tsne(Xk, pp, n_iter=tt_, lr=TSNE_LR, P=Pj, dof=dof)[1])   # later ones amplify rounding errors
        d3["ref"]["%s_%d_%s" % (k, pp, "t" if dof else "g")] = dict(kl=kl_at[str(TSNE_ITERS)], kl_at=kl_at, sigma_mean=float(sig.mean()))
    with open(os.path.join(DATA_OUT, "ch20-tsne.json"), "w") as f:
        json.dump(d3, f, separators=(",", ":"))
    # 4. Swiss roll: Isomap and the neighbourhood size
    Xr, tr = swiss_roll(500, 0, 5)
    Xr = np.round(Xr, 3)
    tt = np.round(tr, 3)
    Zn = np.round(np.random.default_rng(6).normal(size=Xr.shape), 3)
    d4 = dict(X=Xr.tolist(), t=tt.tolist(), Zn=Zn.tolist(), ref={})
    for noise in (0.0, 0.5):
        Xn = Xr + noise * Zn
        for k in (6, 10, 14, 20, 30):
            A, _ = knn_graph(Xn, k)
            ii, jj = np.where(np.triu(A) > 0)
            sc = int((np.abs(tt[ii] - tt[jj]) > 3.0).sum())
            nconn = csgraph.connected_components(sparse.csr_matrix(A))[0]
            ent = dict(edges=int(len(ii)), short=sc, comps=int(nconn))
            if nconn == 1:
                G = csgraph.shortest_path(sparse.csr_matrix(A), method="D", directed=False)
                Zi, lam_i = classical_mds(G ** 2, 2)
                ent["iso_lam"] = r_(lam_i[:3], 3)
                ent["iso_corr"] = float(abs(np.corrcoef(Zi[:, 0], tt)[0, 1]))
                ent["gmax"] = float(G.max())
            d4["ref"]["%g_%d" % (noise, k)] = ent
    Zm, lam_m = classical_mds(sqdist(Xr), 2)
    d4["ref"]["mds"] = dict(lam=r_(lam_m[:3], 3), corr=float(abs(np.corrcoef(Zm[:, 0], tt)[0, 1])))
    with open(os.path.join(DATA_OUT, "ch20-roll.json"), "w") as f:
        json.dump(d4, f, separators=(",", ":"))
    print("wrote ch20-*.json")


if __name__ == "__main__":
    if "--json" in sys.argv:
        export_json()
    else:
        common.run(FIGURES, CH)
        if "--fig" not in sys.argv and "--list" not in sys.argv:
            export_json()
