"""Bishop and Bishop (2024), Chapter 19: Autoencoders.

Reproduces the figures of Chapter 19 of C. M. Bishop and H. Bishop, Deep Learning: Foundations and
Concepts (Springer, 2024), pp. 563-579, written from scratch with numpy, PyTorch (CPU, one thread)
and matplotlib, and supplies the reference numbers of the four browser demonstrations. Every model is
a short function meant to be read next to the lecture notes (ch19-autoencoders.html):

* Section 19.1.1, linear autoencoders: PCA (pca), principal angles between subspaces
  (principal_angles), and a linear autoencoder trained by full-batch gradient descent on centred,
  down-sampled MNIST digits (linear_ae_train), in exactly the arithmetic of
  linear-autoencoder-demo.html; a one-hidden-layer autoencoder with sigmoid hidden units, a deep
  autoencoder and PCA compared on MNIST (shallow_deep_errors).
* Section 19.1.2, deep autoencoders: a 3-2-3 deep autoencoder on a curved two-dimensional sheet in
  three dimensions (curved_sheet, train_ae).
* Section 19.1.3, sparse autoencoders: an over-complete ReLU autoencoder with the L1 activation
  penalty (19.2), with and without unit-norm decoder columns (sparse_ae).
* Section 19.1.4, denoising autoencoders: two-dimensional data from Gaussian mixtures along curves,
  for which the noisy density, its score and the optimal denoiser are known exactly
  (mixture_centres, noisy_score, optimal_denoiser); a small tanh network trained with Adam on (19.3)
  (dae_train), in exactly the arithmetic of denoising-score-demo.html.
* Section 19.1.5, masked autoencoders: a tiny vision transformer encoder and decoder trained on MNIST
  with 75% of 7 x 7 patches masked (MAE, train_mae).
* Section 19.2, variational autoencoders: the circle model of Figures 16.13 and 19.7, its exact
  posterior and log likelihood by quadrature (circle_*), the ELBO of a Gaussian q (circle_elbo), EM
  with an exact E step and joint ELBO ascent (Figures 19.8, 19.9), and Gaussian-q fitting by the
  reparameterisation trick (fit_q_reparam), in exactly the arithmetic of elbo-gap-demo.html.
  VAEs with a Bernoulli decoder on binarised MNIST for seven values of beta (train_vae), their rate,
  distortion, active units, importance-sampled log likelihood and the amortisation gap; the variance of
  reparameterisation and score-function gradients of the ELBO; a linear Gaussian VAE whose optimum is
  known in closed form (linear_vae_closed_form, train_linear_vae).
* JSRandom: the seeded generator DK.rng of the browser demos (mulberry32 uniforms and Box-Muller
  normals). linear_ae_train, dae_train and fit_q_reparam use only that generator and plain
  floating-point arithmetic, so the demos reproduce them to rounding error. The beta-VAE demo runs the exported decoders
  (float16 weights) forward only.

Figures reproduced (computed versions): 19.3 (a trained deep autoencoder, D = 3, M = 2, and the
curved surface F2 embeds), 19.4 (a trained denoising autoencoder on data near a circle: corruption
vectors and the learned field pointing back to the manifold), 19.6 (the phenomenon at small scale: a
masked autoencoder on MNIST reconstructing digits from 4 of 16 patches; the book's images come from
He et al. (2021)), 19.7 (exact), 19.8 and 19.9 (schematic in the book; here computed for the circle
model with a Gaussian q).
Skipped: 19.1 and 19.2 (network diagrams), 19.5 (a drawing of the masked-autoencoder architecture),
19.10 and 19.11 (computational-graph diagrams of the reparameterisation trick). None contains data.

Supplementary figures (our own, numbered 19.S1-19.S8 in the order they appear in the notes):
19.S1 a linear autoencoder learns the principal subspace but not the eigenvectors;
19.S2 sigmoid hidden units do not beat PCA, extra layers do;
19.S3 the sparse autoencoder and the scaling degeneracy of the L1 activation penalty;
19.S4 the optimal denoiser, Tweedie's formula and the small-noise limit of the score;
19.S5 the gap between log likelihood and ELBO: approximation and amortisation gaps on MNIST;
19.S6 reparameterisation versus score-function gradients of a VAE's ELBO;
19.S7 the beta trade-off on MNIST: rate, distortion, active units, reconstructions and samples;
19.S8 the linear Gaussian VAE: posterior collapse and reverse water-filling in closed form.

Run `python3 ch19_autoencoders.py --list`, `python3 ch19_autoencoders.py` (all figures; about
10 minutes the first time on one CPU thread, under a minute once the trained models are cached in
cache/) or `python3 ch19_autoencoders.py --fig 19.7 19.S8`. Files go to ../img/ch19/; the demo data
go to ../data/ch19-*.json.
"""
import base64
import json
import math
import os

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

import numpy as np  # noqa: E402
import matplotlib.pyplot as plt  # noqa: E402

import common  # noqa: E402
from common import BLUE, GREEN, GREY, ORANGE, PURPLE, RED, savefig  # noqa: E402

CH = 19
HERE = os.path.dirname(os.path.abspath(__file__))
CACHE = os.path.join(HERE, "cache")
DATA = os.path.normpath(os.path.join(HERE, "..", "data"))
M32 = 0xFFFFFFFF
BETAS = (0.25, 0.5, 1.0, 2.0, 4.0, 8.0, 16.0)
VAE_M = 10


# =========================================================================== the demos' random numbers
def _imul(a, b):
    return (a * b) & M32


class JSRandom:
    """The seeded random numbers of the browser demos (DK.rng in courses/demo-kit.js).

    Uniforms come from the mulberry32 generator and normals from the Box-Muller transform, the
    second normal of each pair being cached, exactly as in JavaScript.
    """

    def __init__(self, seed):
        self.a = int(seed) & M32
        self.spare = None

    def u(self):
        a = (self.a + 0x6D2B79F5) & M32
        self.a = a
        t = _imul(a ^ (a >> 15), 1 | a)
        t = ((t + _imul(t ^ (t >> 7), 61 | t)) & M32) ^ t
        return ((t ^ (t >> 14)) & M32) / 4294967296.0

    def _pos(self):
        x = 0.0
        while x == 0.0:
            x = self.u()
        return x

    def norm(self):
        if self.spare is not None:
            s, self.spare = self.spare, None
            return s
        r = math.sqrt(-2.0 * math.log(self._pos()))
        th = 2.0 * math.pi * self.u()
        self.spare = r * math.sin(th)
        return r * math.cos(th)


def _cache(name):
    os.makedirs(CACHE, exist_ok=True)
    return os.path.join(CACHE, name)


def _write_json(name, obj):
    os.makedirs(DATA, exist_ok=True)
    path = os.path.join(DATA, name)
    with open(path, "w") as f:
        json.dump(obj, f, separators=(",", ":"))
    print("wrote", os.path.relpath(path, os.getcwd()), "(%.0f kB)" % (os.path.getsize(path) / 1024))
    return path


def b64_f16(a):
    return base64.b64encode(np.ascontiguousarray(a, dtype="<f2").tobytes()).decode("ascii")


def b64_u8(a):
    return base64.b64encode(np.ascontiguousarray(a, dtype=np.uint8).tobytes()).decode("ascii")


# =========================================================================== 19.1.1 linear autoencoders
def pca(X):
    """Eigenvalues (descending) and eigenvectors (columns) of the sample covariance of the rows of X."""
    Xc = X - X.mean(0)
    S = Xc.T @ Xc / len(X)
    lam, U = np.linalg.eigh(S)
    return lam[::-1].copy(), U[:, ::-1].copy()


def principal_angles(A, B):
    """Cosines of the principal angles between span(A) and span(B) (columns), largest first."""
    Qa, _ = np.linalg.qr(A)
    Qb, _ = np.linalg.qr(B)
    return np.clip(np.linalg.svd(Qa.T @ Qb, compute_uv=False), 0.0, 1.0)


def mnist14(n=500, seed=0):
    """n MNIST training digits (balanced over the 10 classes) down-sampled to 14 x 14 by 2 x 2
    averaging and stored as integers 0-255, the data of linear-autoencoder-demo.html."""
    X, y = common.mnist(True)
    rng = np.random.default_rng(seed)
    idx = np.concatenate([rng.choice(np.where(y == d)[0], n // 10, replace=False) for d in range(10)])
    idx = idx[rng.permutation(len(idx))]
    img = X[idx].reshape(-1, 14, 2, 14, 2).mean((2, 4))
    return np.round(img.reshape(len(idx), 196) * 255).astype(np.uint8), y[idx]


def linear_ae_data():
    """The demo's data matrix: centred 14 x 14 digits in [0, 1] (N x 196)."""
    U8, _ = mnist14()
    X = U8.astype(float) / 255.0
    return X - X.mean(0)


def linear_ae_init(D, M, scale, seed):
    """Encoder W1 (M x D) then decoder W2 (D x M), entries scale * N(0, 1) drawn row by row from
    JSRandom(seed), as in the demo."""
    r = JSRandom(seed)
    W1 = np.array([[scale * r.norm() for _ in range(D)] for _ in range(M)])
    W2 = np.array([[scale * r.norm() for _ in range(M)] for _ in range(D)])
    return W1, W2


def linear_ae_loss(X, W1, W2, wd=0.0):
    """(1/2N) sum_n ||W2 W1 x_n - x_n||^2 (+ wd/2 (||W1||^2 + ||W2||^2)): (19.1) divided by N."""
    R = X @ W1.T @ W2.T - X
    return 0.5 * np.sum(R * R) / len(X) + 0.5 * wd * (np.sum(W1 * W1) + np.sum(W2 * W2))


def linear_ae_train(X, M, steps, lr, wd=0.0, scale=0.01, seed=1, every=10, U=None):
    """Full-batch gradient descent on linear_ae_loss (no biases: X is centred).

    Gradients: with Z = X W1^T and R = Z W2^T - X, dE/dW2 = R^T Z / N + wd W2 and
    dE/dW1 = (R W2)^T X / N + wd W1. Returns W1, W2 and a history (every `every` steps) of the
    loss and of the cosines of the principal angles between span(W2) and the top-M eigenvectors U.
    """
    N, D = X.shape
    W1, W2 = linear_ae_init(D, M, scale, seed)
    if U is None:
        U = pca(X)[1][:, :M]
    hist = {"step": [], "loss": [], "cos": []}
    for t in range(steps + 1):
        if t % every == 0 or t == steps:
            hist["step"].append(t)
            hist["loss"].append(linear_ae_loss(X, W1, W2, wd))
            hist["cos"].append(principal_angles(W2, U))
        if t == steps:
            break
        Z = X @ W1.T
        R = Z @ W2.T - X
        gW2 = R.T @ Z / N + wd * W2
        gW1 = (R @ W2).T @ X / N + wd * W1
        W1 = W1 - lr * gW1
        W2 = W2 - lr * gW2
    hist = {k: np.array(v) for k, v in hist.items()}
    return W1, W2, hist


def column_eigen_match(W2, U):
    """For each decoder column, the largest |cosine| with any eigenvector in U (columns)."""
    Wn = W2 / np.linalg.norm(W2, axis=0, keepdims=True)
    return np.abs(Wn.T @ U).max(1)


def export_linear_ae():
    """../data/ch19-mnist14.json: 500 digits (uint8, base64), their labels, and the top 16
    eigenvalues and eigenvectors of the covariance (for the demo's PCA reference)."""
    U8, y = mnist14()
    X = U8.astype(float) / 255.0
    lam, U = pca(X)
    return _write_json("ch19-mnist14.json", {
        "about": "500 MNIST training digits down-sampled to 14 x 14 (uint8, base64, row-major), labels, and the top 16 "
                 "eigenvalues/eigenvectors of their covariance; written by ch19_autoencoders.py (export_linear_ae).",
        "n": int(len(U8)), "d": 196, "pixels": b64_u8(U8), "labels": y.tolist(),
        "lam": [float(v) for v in lam[:16]], "U": [[float(v) for v in U[:, k]] for k in range(16)],
        "lam_sum": float(lam.sum())})


def fig_19_s1(out=None):
    """Figure 19.S1: a linear autoencoder finds the principal subspace, not the eigenvectors."""
    X = linear_ae_data()
    lam, U = pca(X)
    M = 6
    runs = {"plain": linear_ae_train(X, M, 3000, 0.3, 0.0, 0.001, 1, every=2, U=U[:, :M]),
            "wd": linear_ae_train(X, M, 3000, 0.3, 0.002, 0.001, 1, every=2, U=U[:, :M])}
    fig = plt.figure(figsize=(12.6, 3.5))
    gs = fig.add_gridspec(1, 4, width_ratios=[1, 1, 0.9, 0.9], wspace=0.35)
    ax = fig.add_subplot(gs[0])
    W1, W2, h = runs["plain"]
    st = np.maximum(h["step"], 1)
    ax.semilogx(st, h["loss"], color=BLUE, label="linear AE")
    for j in range(M + 1):
        ax.axhline(0.5 * lam[j:].sum(), color=GREY, lw=0.6, ls=":")
        ax.text(1.1, 0.5 * lam[j:].sum() + 0.03, "$k=%d$" % j, fontsize=7, color=GREY)
    ax.set_xlabel("gradient step")
    ax.set_ylabel(r"$E/N$")
    ax.set_title("error; dotted: PCA with $k$ components", fontsize=9.5)
    common.panel_label(ax, "a", "upper right")
    ax = fig.add_subplot(gs[1])
    for j in range(M):
        ax.semilogx(st, np.degrees(np.arccos(np.clip(h["cos"][:, j], 0, 1))), color=plt.cm.viridis(j / M), lw=1.1)
    ax.semilogx(st, np.degrees(np.arccos(np.clip(h["cos"][:, -1], 0, 1))), color=RED, lw=2, label="largest angle")
    ax.set_xlabel("gradient step")
    ax.set_ylabel("principal angle (degrees)")
    ax.set_title("principal angles to span($\\mathbf{U}_M$)", fontsize=9.5)
    ax.legend(loc="upper right", frameon=False)
    common.panel_label(ax, "b", "lower left")
    for k, (key, title) in enumerate((("plain", "decoder columns (no decay)"), ("wd", "decoder left singular vectors (decay)"))):
        W1, W2, h = runs[key]
        if key == "wd":
            Ul, s, _ = np.linalg.svd(W2, full_matrices=False)
            cols = Ul
        else:
            cols = W2 / np.linalg.norm(W2, axis=0)
        sub = gs[2 + k].subgridspec(M, 2, hspace=0.08, wspace=0.05)
        for j in range(M):
            for c, vec in enumerate((cols[:, j], U[:, j])):
                a = fig.add_subplot(sub[j, c])
                v = vec * np.sign(vec @ U[:, j]) if c == 0 and key == "wd" else vec
                a.imshow(v.reshape(14, 14), cmap="RdBu_r", vmin=-np.abs(v).max(), vmax=np.abs(v).max())
                a.set_xticks([])
                a.set_yticks([])
                if j == 0:
                    a.set_title("learned" if c == 0 else "eigenvector", fontsize=8)
                if c == 0:
                    a.set_ylabel("%.2f" % abs(cols[:, j] @ U[:, j]) if key == "wd" else "%.2f" % column_eigen_match(W2, U[:, :M])[j],
                                 fontsize=7, rotation=0, labelpad=12, va="center")
        fig.text(0.62 + 0.19 * k, 0.97, title, ha="center", fontsize=9)
    fig.text(0.62, -0.02, "(c)", ha="center")
    fig.text(0.81, -0.02, "(d)", ha="center")
    return savefig(fig, CH, "fig19-s1", out)


# =========================================================================== shallow versus deep
def _torch():
    return common.torch_setup(0, threads=1)


def train_ae(torch, enc, dec, Xtr, epochs, lr=1e-3, batch=128, seed=0, loss_extra=None, after_step=None, log=None):
    """Adam on the mean over a batch of ||dec(enc(x)) - x||^2 / 2 (+ loss_extra(z))."""
    params = list(enc.parameters()) + list(dec.parameters())
    opt = torch.optim.Adam(params, lr=lr)
    g = torch.Generator().manual_seed(seed)
    N = len(Xtr)
    for ep in range(epochs):
        perm = torch.randperm(N, generator=g)
        for i in range(0, N, batch):
            xb = Xtr[perm[i:i + batch]]
            z = enc(xb)
            loss = 0.5 * ((dec(z) - xb) ** 2).sum(1).mean()
            if loss_extra is not None:
                loss = loss + loss_extra(z)
            opt.zero_grad()
            loss.backward()
            opt.step()
            if after_step is not None:
                after_step()
        if log is not None:
            log(ep)
    return enc, dec


def shallow_deep_errors(Ms=(2, 5, 10, 20), epochs=25, n=10000):
    """Mean reconstruction error per image (1/2 ||y - x||^2) on the training set for PCA, a 784-M-784
    autoencoder with sigmoid hidden units and linear outputs, and a deep 784-256-M-256-784
    autoencoder (tanh, linear code and output), all on n MNIST training digits."""
    path = _cache("ch19_shallow_deep.npz")
    if os.path.exists(path):
        d = np.load(path)
        return {k: d[k] for k in d.files}
    torch = _torch()
    nn = torch.nn
    X, _ = common.mnist(True)
    X = X[np.random.default_rng(0).permutation(len(X))[:n]]
    lam, U = pca(X)
    Xt = torch.tensor(X, dtype=torch.float32)
    res = {"M": np.array(Ms), "pca": [], "shallow": [], "deep": [], "lam": lam}
    for M in Ms:
        res["pca"].append(0.5 * lam[M:].sum())
        torch.manual_seed(M)
        enc = nn.Sequential(nn.Linear(784, M), nn.Sigmoid())
        dec = nn.Linear(M, 784)
        train_ae(torch, enc, dec, Xt, epochs, lr=3e-3, seed=M)
        with torch.no_grad():
            res["shallow"].append(float(0.5 * ((dec(enc(Xt)) - Xt) ** 2).sum(1).mean()))
        torch.manual_seed(100 + M)
        enc = nn.Sequential(nn.Linear(784, 256), nn.Tanh(), nn.Linear(256, M))
        dec = nn.Sequential(nn.Linear(M, 256), nn.Tanh(), nn.Linear(256, 784))
        train_ae(torch, enc, dec, Xt, epochs, lr=1e-3, seed=M)
        with torch.no_grad():
            res["deep"].append(float(0.5 * ((dec(enc(Xt)) - Xt) ** 2).sum(1).mean()))
        print("  M = %d: PCA %.3f shallow %.3f deep %.3f" % (M, res["pca"][-1], res["shallow"][-1], res["deep"][-1]))
    res = {k: np.array(v) for k, v in res.items()}
    np.savez(path, **res)
    return res


def fig_19_s2(out=None):
    """Figure 19.S2: a sigmoid hidden layer does not beat PCA; a deep autoencoder does."""
    r = shallow_deep_errors()
    fig, ax = plt.subplots(1, 2, figsize=(9.2, 3.3))
    a = ax[0]
    a.plot(r["M"], r["pca"], "o-", color=GREY, label="PCA (bound of Result 19.2)")
    a.plot(r["M"], r["shallow"], "s--", color=BLUE, label="784-M-784, sigmoid hidden")
    a.plot(r["M"], r["deep"], "^-", color=RED, label="784-256-M-256-784 (deep)")
    a.set_xlabel("code size $M$")
    a.set_ylabel(r"training error per image $\frac{1}{2}\|\mathbf{y}-\mathbf{x}\|^2$")
    a.set_xscale("log")
    a.set_xticks(r["M"])
    a.set_xticklabels([str(v) for v in r["M"]])
    a.legend(frameon=False, fontsize=8)
    common.panel_label(a, "a", "lower left")
    a = ax[1]
    a.bar(np.arange(len(r["M"])) - 0.2, r["shallow"] / r["pca"], 0.4, color=BLUE, label="sigmoid hidden / PCA")
    a.bar(np.arange(len(r["M"])) + 0.2, r["deep"] / r["pca"], 0.4, color=RED, label="deep / PCA")
    a.axhline(1, color="k", lw=0.8)
    a.set_xticks(np.arange(len(r["M"])))
    a.set_xticklabels(["M = %d" % v for v in r["M"]])
    a.set_ylabel("error relative to PCA")
    a.legend(frameon=False, fontsize=8, loc="lower left")
    common.panel_label(a, "b", "upper right")
    fig.tight_layout()
    return savefig(fig, CH, "fig19-s2", out)


# =========================================================================== 19.1.2 deep autoencoders
def curved_sheet(n=2000, seed=0, noise=0.02):
    """Points on a sheet bent through 240 degrees: x = (sin 2u, v, cos 2u) for u uniform on
    (-1.05, 1.05), v uniform on (-1, 1), plus N(0, noise^2) in every coordinate."""
    rng = np.random.default_rng(seed)
    u = rng.uniform(-1.05, 1.05, n)
    v = rng.uniform(-1, 1, n)
    X = np.stack([np.sin(2 * u), v, np.cos(2 * u)], 1) + noise * rng.standard_normal((n, 3))
    return X, u, v


def deep_sheet_ae():
    """A 3-64-64-2-64-64-3 tanh autoencoder (linear code and outputs) trained on curved_sheet."""
    torch = _torch()
    nn = torch.nn
    path = _cache("ch19_sheet_ae.pt")
    X, u, v = curved_sheet()
    torch.manual_seed(0)
    enc = nn.Sequential(nn.Linear(3, 64), nn.Tanh(), nn.Linear(64, 64), nn.Tanh(), nn.Linear(64, 2))
    dec = nn.Sequential(nn.Linear(2, 64), nn.Tanh(), nn.Linear(64, 64), nn.Tanh(), nn.Linear(64, 3))
    if os.path.exists(path):
        st = torch.load(path)
        enc.load_state_dict(st["enc"])
        dec.load_state_dict(st["dec"])
    else:
        Xt = torch.tensor(X, dtype=torch.float32)
        train_ae(torch, enc, dec, Xt, 400, lr=3e-3, batch=100)
        torch.save({"enc": enc.state_dict(), "dec": dec.state_dict()}, path)
    return torch, enc, dec, X, u, v


def fig_19_3(out=None):
    """Figure 19.3: the deep autoencoder's F1 maps the data to a 2-D latent space; F2 embeds a curved
    surface S in 3-D."""
    torch, enc, dec, X, u, v = deep_sheet_ae()
    with torch.no_grad():
        Z = enc(torch.tensor(X, dtype=torch.float32)).numpy()
        Y = dec(torch.tensor(Z)).numpy()
    lam, U = pca(X)
    err_ae = 0.5 * ((Y - X) ** 2).sum(1).mean()
    err_pca = 0.5 * lam[2:].sum()
    fig = plt.figure(figsize=(10.5, 3.9))
    ax = fig.add_subplot(1, 2, 1)
    ax.scatter(Z[:, 0], Z[:, 1], c=u, s=4, cmap="coolwarm")
    z0, z1 = np.percentile(Z[:, 0], [0.5, 99.5]), np.percentile(Z[:, 1], [0.5, 99.5])
    g0, g1 = np.linspace(*z0, 13), np.linspace(*z1, 13)
    for a in g0:
        ax.plot([a, a], z1, color=GREY, lw=0.4)
    for b in g1:
        ax.plot(z0, [b, b], color=GREY, lw=0.4)
    ax.set_xlabel("$z_1$")
    ax.set_ylabel("$z_2$")
    ax.set_title("latent space: codes $F_1(\\mathbf{x})$ and a grid $S$", fontsize=10)
    ax3 = fig.add_subplot(1, 2, 2, projection="3d")
    ax3.scatter(X[::3, 0], X[::3, 1], X[::3, 2], c=u[::3], s=3, cmap="coolwarm", alpha=0.6)
    with torch.no_grad():
        for a in g0:
            P = dec(torch.tensor(np.stack([np.full(60, a), np.linspace(*z1, 60)], 1), dtype=torch.float32)).numpy()
            ax3.plot(P[:, 0], P[:, 1], P[:, 2], color="k", lw=0.6)
        for b in g1:
            P = dec(torch.tensor(np.stack([np.linspace(*z0, 60), np.full(60, b)], 1), dtype=torch.float32)).numpy()
            ax3.plot(P[:, 0], P[:, 1], P[:, 2], color="k", lw=0.6)
    ax3.set_xlabel("$x_1$")
    ax3.set_ylabel("$x_2$")
    ax3.set_zlabel("$x_3$")
    ax3.view_init(18, -60)
    ax3.set_title("data space: the surface $F_2(S)$ (black)\nerror/point: deep AE %.4f, PCA %.4f" % (err_ae, err_pca), fontsize=9.5)
    fig.tight_layout()
    return savefig(fig, CH, "fig19-3", out)


# =========================================================================== 19.1.3 sparse autoencoders
def sparse_ae(lam, unit_norm=True, K=100, epochs=12, n=10000, seed=0, track=False):
    """Over-complete autoencoder z = ReLU(A x + a), y = B z + b with K = 100 units on n MNIST digits,
    trained with Adam on the batch mean of 1/2 ||y - x||^2 + lam sum_k |z_k| (19.2). With unit_norm
    the columns of B are rescaled to unit length after every step. Returns the parameters and, if
    track, the per-epoch history of ||B||_F, mean sum_k z_k and the reconstruction error."""
    key = "ch19_sparse_%g_%d_%d.npz" % (lam, int(unit_norm), epochs)
    path = _cache(key)
    if os.path.exists(path):
        d = np.load(path)
        return {k: d[k] for k in d.files}
    torch = _torch()
    nn = torch.nn
    X, _ = common.mnist(True)
    X = X[np.random.default_rng(1).permutation(len(X))[:n]]
    Xt = torch.tensor(X, dtype=torch.float32)
    torch.manual_seed(seed)
    enc = nn.Sequential(nn.Linear(784, K), nn.ReLU())
    dec = nn.Linear(K, 784)

    def renorm():
        if unit_norm:
            with torch.no_grad():
                dec.weight /= dec.weight.norm(dim=0, keepdim=True).clamp_min(1e-8)
    renorm()
    hist = {"Bnorm": [], "zsum": [], "rec": []}

    def log(ep):
        with torch.no_grad():
            Z = enc(Xt)
            hist["Bnorm"].append(float(dec.weight.norm()))
            hist["zsum"].append(float(Z.sum(1).mean()))
            hist["rec"].append(float(0.5 * ((dec(Z) - Xt) ** 2).sum(1).mean()))
    train_ae(torch, enc, dec, Xt, epochs, lr=2e-3, loss_extra=lambda z: lam * z.abs().sum(1).mean(), after_step=renorm, log=log)
    with torch.no_grad():
        Z = enc(Xt).numpy()
    res = {"B": dec.weight.detach().numpy().copy(), "active": (Z > 0).mean(), "rec": hist["rec"][-1], "usage": (Z > 0).mean(0),
           "zsum": hist["zsum"][-1], "Bnorm_hist": np.array(hist["Bnorm"]), "zsum_hist": np.array(hist["zsum"]),
           "rec_hist": np.array(hist["rec"]), "lam": lam}
    np.savez(path, **res)
    return res


SPARSE_LAMS = (0.0, 0.03, 0.1, 0.3, 1.0)


def fig_19_s3(out=None):
    """Figure 19.S3: the L1 activation penalty (19.2) with unit-norm decoder columns, and without."""
    runs = [sparse_ae(l) for l in SPARSE_LAMS]
    free = sparse_ae(0.3, unit_norm=False, epochs=30, track=True)
    fig = plt.figure(figsize=(12.4, 3.4))
    gs = fig.add_gridspec(1, 4, width_ratios=[1, 0.85, 0.85, 1], wspace=0.35)
    ax = fig.add_subplot(gs[0])
    lams = np.array(SPARSE_LAMS)
    xl = np.where(lams == 0, 0.01, lams)
    ax.plot(xl, [r["active"] for r in runs], "o-", color=RED, label="fraction of units active")
    ax.set_xscale("log")
    ax.set_xlabel(r"$\lambda$ (0 plotted at 0.01)")
    ax.set_ylabel("fraction of $z_k>0$", color=RED)
    ax2 = ax.twinx()
    ax2.plot(xl, [r["rec"] for r in runs], "s--", color=BLUE)
    ax2.set_ylabel("reconstruction error", color=BLUE)
    ax.set_ylim(-0.03, 0.8)
    ax.set_title("unit-norm decoder columns", fontsize=10)
    common.panel_label(ax, "a", "upper left")
    for k, (r, lab) in enumerate(((runs[0], r"$\lambda=0$"), (runs[3], r"$\lambda=0.3$"))):
        sub = gs[1 + k].subgridspec(5, 5, hspace=0.06, wspace=0.06)
        B = r["B"]
        order = np.argsort(-r["usage"])
        for i in range(25):
            a = fig.add_subplot(sub[i // 5, i % 5])
            w = B[:, order[i]]
            a.imshow(w.reshape(28, 28), cmap="RdBu_r", vmin=-np.abs(w).max(), vmax=np.abs(w).max())
            a.set_xticks([])
            a.set_yticks([])
        fig.text(0.355 + 0.205 * k, 0.94, "decoder columns, " + lab, ha="center", fontsize=9)
        fig.text(0.355 + 0.205 * k, 0.02, "(%s)" % "bc"[k], ha="center")
    ax = fig.add_subplot(gs[3])
    ep = np.arange(1, len(free["Bnorm_hist"]) + 1)
    ax.plot(ep, free["Bnorm_hist"] / free["Bnorm_hist"][0], color=RED, label=r"$\|\mathbf{B}\|_F$ (relative)")
    ax.plot(ep, free["zsum_hist"] / free["zsum_hist"][0], color=BLUE, label=r"mean $\sum_k z_k$ (relative)")
    ax.plot(ep, free["rec_hist"] / free["rec_hist"][0], color=GREEN, ls="--", label="reconstruction (relative)")
    ax.set_yscale("log")
    ax.set_xlabel("epoch")
    ax.set_title(r"no constraint, $\lambda=0.3$: the scaling escape", fontsize=10)
    ax.legend(frameon=False, fontsize=7.5, loc="upper left")
    common.panel_label(ax, "d", "lower left")
    return savefig(fig, CH, "fig19-s3", out)


# =========================================================================== 19.1.4 denoising autoencoders
DAE_SETS = {"ring": dict(K=60, tau=0.03), "spiral": dict(K=90, tau=0.03), "moons": dict(K=60, tau=0.04)}


def mixture_centres(name):
    """Centres c_k of the equal-weight mixture (1/K) sum_k N(c_k, tau^2 I) that defines each 2-D data set
    (computed identically in denoising-score-demo.html)."""
    K = DAE_SETS[name]["K"]
    C = []
    for k in range(K):
        if name == "ring":
            t = 2 * math.pi * k / K
            C.append((math.cos(t), math.sin(t)))
        elif name == "spiral":
            t = 0.5 * math.pi + 3.5 * math.pi * k / (K - 1)
            r = 0.1 * t
            C.append((r * math.cos(t), r * math.sin(t)))
        else:
            h = K // 2
            if k < h:
                t = math.pi * k / (h - 1)
                C.append((math.cos(t) - 0.5, math.sin(t) - 0.25))
            else:
                t = math.pi * (k - h) / (h - 1)
                C.append((0.5 - math.cos(t), 0.25 - math.sin(t)))
    return np.array(C)


def _resp(Xq, C, var):
    d2 = ((Xq[:, None, :] - C[None, :, :]) ** 2).sum(-1)
    a = -0.5 * d2 / var
    a -= a.max(1, keepdims=True)
    r = np.exp(a)
    return r / r.sum(1, keepdims=True)


def mixture_logpdf(Xq, C, var):
    d2 = ((Xq[:, None, :] - C[None, :, :]) ** 2).sum(-1)
    return common.logsumexp(-0.5 * d2 / var, axis=1) - math.log(len(C)) - math.log(2 * math.pi * var)


def mixture_score(Xq, C, var):
    """grad_x ln (1/K) sum_k N(x | c_k, var I)."""
    r = _resp(Xq, C, var)
    return (r @ C - Xq) / var


def noisy_score(Xq, name, sigma):
    """The score of the corrupted-data density p_sigma = p * N(0, sigma^2 I)."""
    C, tau = mixture_centres(name), DAE_SETS[name]["tau"]
    return mixture_score(Xq, C, tau ** 2 + sigma ** 2)


def optimal_denoiser(Xq, name, sigma):
    """E[x | x~] for x ~ (1/K) sum_k N(c_k, tau^2 I), x~ = x + sigma eps: the posterior over the
    component times the Gaussian posterior mean c_k + tau^2/(tau^2 + sigma^2) (x~ - c_k)."""
    C, tau = mixture_centres(name), DAE_SETS[name]["tau"]
    v = tau ** 2 + sigma ** 2
    r = _resp(Xq, C, v)
    return r @ C + (tau ** 2 / v) * (Xq - r @ C)


def dae_init(H, seed):
    """Weights of the 2-H-H-2 tanh network, drawn row by row from JSRandom(seed): W1 (H x 2) with
    variance 1/2, W2 (H x H) and W3 (2 x H) with variance 1/H; biases zero."""
    r = JSRandom(seed)
    W1 = np.array([[r.norm() * math.sqrt(0.5) for _ in range(2)] for _ in range(H)])
    W2 = np.array([[r.norm() * math.sqrt(1.0 / H) for _ in range(H)] for _ in range(H)])
    W3 = np.array([[r.norm() * math.sqrt(1.0 / H) for _ in range(H)] for _ in range(2)])
    return [W1, np.zeros(H), W2, np.zeros(H), W3, np.zeros(2)], r


def dae_forward(P, Xq):
    """y(x~) = x~ + f(x~), with f a 2-H-H-2 tanh network (residual form of the denoiser)."""
    W1, b1, W2, b2, W3, b3 = P
    h1 = np.tanh(Xq @ W1.T + b1)
    h2 = np.tanh(h1 @ W2.T + b2)
    return Xq + h2 @ W3.T + b3


def dae_batch(name, sigma, B, r, C=None):
    """B training pairs: k ~ uniform, x = c_k + tau n1, x~ = x + sigma n2 (draws in this order)."""
    if C is None:
        C = mixture_centres(name)
    tau = DAE_SETS[name]["tau"]
    K = len(C)
    X = np.empty((B, 2))
    Xn = np.empty((B, 2))
    for b in range(B):
        k = int(math.floor(r.u() * K))
        x0 = C[k, 0] + tau * r.norm()
        x1 = C[k, 1] + tau * r.norm()
        X[b] = (x0, x1)
        Xn[b] = (x0 + sigma * r.norm(), x1 + sigma * r.norm())
    return X, Xn


def dae_train(name="ring", sigma=0.2, H=32, steps=1500, lr=0.01, B=64, seed=1, every=50):
    """Adam (beta1 0.9, beta2 0.999, eps 1e-8) on the batch mean of ||y(x~) - x||^2, (19.3), with fresh
    samples every step. The same JSRandom stream gives the initial weights and then the batches.
    Returns the parameters and the loss history (every `every` steps)."""
    P, r = dae_init(H, seed)
    C = mixture_centres(name)
    m = [np.zeros_like(p) for p in P]
    v = [np.zeros_like(p) for p in P]
    hist = []
    b1, b2, eps = 0.9, 0.999, 1e-8
    for t in range(1, steps + 1):
        X, Xn = dae_batch(name, sigma, B, r, C)
        W1, c1, W2, c2, W3, c3 = P
        a1 = Xn @ W1.T + c1
        h1 = np.tanh(a1)
        a2 = h1 @ W2.T + c2
        h2 = np.tanh(a2)
        Y = Xn + h2 @ W3.T + c3
        R = Y - X
        loss = np.sum(R * R) / B
        if (t - 1) % every == 0 or t == steps:
            hist.append((t - 1, loss))
        dY = 2.0 * R / B
        gW3 = dY.T @ h2
        gc3 = dY.sum(0)
        d2 = (dY @ W3) * (1 - h2 * h2)
        gW2 = d2.T @ h1
        gc2 = d2.sum(0)
        d1 = (d2 @ W2) * (1 - h1 * h1)
        gW1 = d1.T @ Xn
        gc1 = d1.sum(0)
        G = [gW1, gc1, gW2, gc2, gW3, gc3]
        for i in range(6):
            m[i] = b1 * m[i] + (1 - b1) * G[i]
            v[i] = b2 * v[i] + (1 - b2) * G[i] * G[i]
            mh = m[i] / (1 - b1 ** t)
            vh = v[i] / (1 - b2 ** t)
            P[i] = P[i] - lr * mh / (np.sqrt(vh) + eps)
    return P, np.array(hist)


def dae_test_points(name, sigma, n=1000, seed=12345):
    """n corrupted points x~ ~ p_sigma used to score a denoiser (same stream as the demo)."""
    return dae_batch(name, sigma, n, JSRandom(seed))[1]


def dae_rel_error(P, name, sigma, n=1000):
    """E||f(x~) - f*(x~)||^2 / E||f*(x~)||^2 over x~ ~ p_sigma, with f* = E[x|x~] - x~ (Tweedie)."""
    Xq = dae_test_points(name, sigma, n)
    fs = optimal_denoiser(Xq, name, sigma) - Xq
    f = dae_forward(P, Xq) - Xq
    return float(((f - fs) ** 2).sum() / (fs ** 2).sum())


def fig_19_4(out=None):
    """Figure 19.4: a denoising autoencoder maps corrupted points back towards the data manifold."""
    sigma = 0.2
    P, hist = dae_train("ring", sigma, 32, 2000, 0.01, 64, 1)
    C = mixture_centres("ring")
    r = JSRandom(7)
    X, Xn = dae_batch("ring", sigma, 40, r, C)
    fig, ax = plt.subplots(1, 3, figsize=(11.6, 3.8))
    th = np.linspace(0, 2 * np.pi, 400)
    for a in ax:
        a.plot(np.cos(th), np.sin(th), color=GREEN, lw=1.2, alpha=0.7)
        a.set_aspect("equal")
        a.set_xlim(-1.6, 1.6)
        a.set_ylim(-1.6, 1.6)
        a.set_xticks([-1, 0, 1])
        a.set_yticks([-1, 0, 1])
    a = ax[0]
    a.scatter(X[:, 0], X[:, 1], s=10, color=BLUE, zorder=3, label="original $\\mathbf{x}_n$")
    a.scatter(Xn[:, 0], Xn[:, 1], s=10, color=RED, zorder=3, label="corrupted $\\widetilde{\\mathbf{x}}_n$")
    for i in range(len(X)):
        a.annotate("", X[i], Xn[i], arrowprops=dict(arrowstyle="->", color=GREY, lw=0.7))
    a.legend(frameon=False, fontsize=8, loc="center")
    a.set_title(r"corruption, $\sigma=%.1f$ (the arrows are $\mathbf{x}_n-\widetilde{\mathbf{x}}_n$)" % sigma, fontsize=9)
    common.panel_label(a, "a", "lower left")
    g = np.linspace(-1.5, 1.5, 13)
    G = np.array([(x, y) for y in g for x in g])
    with np.errstate(all="ignore"):
        Fl = dae_forward(P, G) - G
        Fo = optimal_denoiser(G, "ring", sigma) - G
    for k, (F, title) in enumerate(((Fl, "learned $\\mathbf{y}(\\widetilde{\\mathbf{x}})-\\widetilde{\\mathbf{x}}$"),
                                    (Fo, "optimal $E[\\mathbf{x}|\\widetilde{\\mathbf{x}}]-\\widetilde{\\mathbf{x}}=\\sigma^2\\nabla\\ln p_\\sigma$"))):
        a = ax[1 + k]
        a.quiver(G[:, 0], G[:, 1], F[:, 0], F[:, 1], angles="xy", scale_units="xy", scale=2, color=[RED, BLUE][k], width=0.006)
        a.set_title(title, fontsize=9.5)
        common.panel_label(a, "bc"[k], "lower left")
    ax[1].text(0, -1.45, "relative error vs optimal: %.3f" % dae_rel_error(P, "ring", sigma), ha="center", fontsize=8)
    fig.tight_layout()
    return savefig(fig, CH, "fig19-4", out)


def fig_19_s4(out=None):
    """Figure 19.S4: the optimal denoiser residual divided by sigma^2 tends to the score of p as
    sigma -> 0; denoisers trained at several noise levels; and the direction of the optimal field."""
    sig = np.geomspace(0.001, 1.0, 31)
    C, tau = mixture_centres("ring"), DAE_SETS["ring"]["tau"]
    t2 = []
    for s in sig:
        Xq = dae_test_points("ring", s, 2000)
        f = optimal_denoiser(Xq, "ring", s) - Xq
        s0 = mixture_score(Xq, C, tau ** 2)
        t2.append(np.sqrt(np.mean(((f / s ** 2 - s0) ** 2).sum(1)) / np.mean((s0 ** 2).sum(1))))
    fig, ax = plt.subplots(1, 3, figsize=(12.2, 3.5))
    a = ax[0]
    a.loglog(sig, t2, "s-", ms=3, color=RED, label=r"$\|f^\star/\sigma^2-\nabla\ln p\|$ (relative)")
    a.loglog(sig[sig < 0.02], (sig[sig < 0.02] / tau) ** 2, "k:", lw=1.2, label=r"$(\sigma/\tau)^2$")
    a.axvline(tau, color=GREY, lw=0.7, ls="--")
    a.text(tau * 1.1, 3e-3, r"$\sigma=\tau$", fontsize=8, color=GREY)
    a.set_xlabel(r"noise level $\sigma$")
    a.set_title("small noise: residual/$\\sigma^2\\to$ score of $p$", fontsize=9.5)
    a.legend(frameon=False, fontsize=8, loc="lower right")
    common.panel_label(a, "a", "upper left")
    sigs = (0.05, 0.1, 0.2, 0.4, 0.8)
    errs = []
    for s in sigs:
        P, _ = dae_train("ring", s, 32, 2000, 0.01, 64, 1)
        errs.append(dae_rel_error(P, "ring", s))
    a = ax[1]
    a.semilogx(sigs, errs, "o-", color=RED)
    a.set_xlabel(r"noise level $\sigma$")
    a.set_ylabel(r"$E\|f-f^\star\|^2/E\|f^\star\|^2$")
    a.set_title("learned vs optimal denoiser (2000 Adam steps)", fontsize=9.5)
    common.panel_label(a, "b", "upper right")
    a = ax[2]
    g = np.linspace(-1.5, 1.5, 11)
    G = np.array([(x, y) for y in g for x in g])
    th = np.linspace(0, 2 * np.pi, 300)
    a.plot(np.cos(th), np.sin(th), color=GREEN, lw=1)
    for s, col in ((0.1, BLUE), (0.8, RED)):
        F = (optimal_denoiser(G, "ring", s) - G)
        nF = np.linalg.norm(F, axis=1, keepdims=True) + 1e-12
        a.quiver(G[:, 0], G[:, 1], F[:, 0] / nF[:, 0], F[:, 1] / nF[:, 0], color=col, angles="xy", scale_units="xy", scale=4,
                 width=0.007, label=r"$\sigma=%.1f$" % s, alpha=0.8)
    a.set_aspect("equal")
    a.set_xlim(-1.75, 1.75)
    a.set_ylim(-1.75, 1.75)
    a.legend(frameon=True, framealpha=0.95, fontsize=7.5, loc="lower right")
    a.set_title("direction of $f^\\star$: to the circle, or to its centre", fontsize=9.5)
    common.panel_label(a, "c", "lower left")
    fig.tight_layout()
    return savefig(fig, CH, "fig19-s4", out)


# =========================================================================== 19.1.5 masked autoencoders
def _mae_modules(torch):
    nn = torch.nn

    class Block(nn.Module):
        def __init__(self, d, heads, dff):
            super().__init__()
            self.ln1 = nn.LayerNorm(d)
            self.att = nn.MultiheadAttention(d, heads, batch_first=True)
            self.ln2 = nn.LayerNorm(d)
            self.mlp = nn.Sequential(nn.Linear(d, dff), nn.GELU(), nn.Linear(dff, d))

        def forward(self, x):
            h = self.ln1(x)
            x = x + self.att(h, h, h, need_weights=False)[0]
            return x + self.mlp(self.ln2(x))

    class MAE(nn.Module):
        """Patches of 7 x 7 pixels (16 tokens). Encoder: linear embedding (49 -> 64) + learned position
        embedding, 3 pre-norm transformer blocks, applied to the visible tokens only. Decoder: linear
        64 -> 48, a learned mask token inserted at the masked positions, a second position embedding,
        2 blocks, and a linear layer 48 -> 49 pixel values."""

        def __init__(self, d=64, dd=48):
            super().__init__()
            self.emb = nn.Linear(49, d)
            self.pos = nn.Parameter(0.02 * torch.randn(16, d))
            self.enc = nn.Sequential(*[Block(d, 4, 2 * d) for _ in range(3)])
            self.ln = nn.LayerNorm(d)
            self.proj = nn.Linear(d, dd)
            self.mask = nn.Parameter(torch.zeros(dd))
            self.pos2 = nn.Parameter(0.02 * torch.randn(16, dd))
            self.dec = nn.Sequential(*[Block(dd, 4, 2 * dd) for _ in range(2)])
            self.out = nn.Linear(dd, 49)

        def encode(self, P, keep):
            tok = self.emb(P) + self.pos
            vis = torch.gather(tok, 1, keep[:, :, None].expand(-1, -1, tok.shape[-1]))
            return self.ln(self.enc(vis))

        def forward(self, P, keep):
            B = P.shape[0]
            h = self.proj(self.encode(P, keep))
            full = self.mask.expand(B, 16, -1).clone()
            full.scatter_(1, keep[:, :, None].expand(-1, -1, h.shape[-1]), h)
            return self.out(self.dec(full + self.pos2))

    return MAE


def patches(X):
    """(N, 784) -> (N, 16, 49): 7 x 7 patches in raster order."""
    return X.reshape(-1, 4, 7, 4, 7).transpose(0, 1, 3, 2, 4).reshape(-1, 16, 49)


def unpatch(P):
    return P.reshape(-1, 4, 4, 7, 7).transpose(0, 1, 3, 2, 4).reshape(-1, 784)


def train_mae(epochs=6, keep_n=4, seed=0):
    """Train the MAE on the 60000 MNIST training digits, masking 12 of 16 patches (75%) at random for
    each image; the loss is the mean squared error over the masked patches only."""
    torch = _torch()
    MAE = _mae_modules(torch)
    torch.manual_seed(seed)
    model = MAE()
    path = _cache("ch19_mae.pt")
    if os.path.exists(path):
        model.load_state_dict(torch.load(path))
        return torch, model
    X, _ = common.mnist(True)
    P = torch.tensor(patches(X), dtype=torch.float32)
    opt = torch.optim.AdamW(model.parameters(), lr=2e-3, weight_decay=0.02)
    g = torch.Generator().manual_seed(seed)
    steps = epochs * (len(P) // 128)
    sched = torch.optim.lr_scheduler.OneCycleLR(opt, 2e-3, total_steps=steps, pct_start=0.1)
    for ep in range(epochs):
        perm = torch.randperm(len(P), generator=g)
        tot = 0.0
        for i in range(0, len(P) - 127, 128):
            pb = P[perm[i:i + 128]]
            order = torch.rand(128, 16, generator=g).argsort(1)
            keep, drop = order[:, :keep_n], order[:, keep_n:]
            pred = model(pb, keep)
            m = torch.zeros(128, 16).scatter_(1, drop, 1.0)
            loss = (((pred - pb) ** 2).mean(-1) * m).sum() / m.sum()
            opt.zero_grad()
            loss.backward()
            opt.step()
            sched.step()
            tot += float(loss.detach())
        print("  MAE epoch %d: masked-patch MSE %.4f" % (ep + 1, tot / (len(P) // 128)))
    torch.save(model.state_dict(), path)
    return torch, model


def mae_test(n=2000, seed=3):
    """Masked-patch mean squared error on n test digits for the MAE and for two baselines: predicting
    the mean training patch at each position, and the mean training image."""
    torch, model = train_mae()
    X, _ = common.mnist(False)
    Xtr, _ = common.mnist(True)
    X = X[:n]
    P = torch.tensor(patches(X), dtype=torch.float32)
    g = torch.Generator().manual_seed(seed)
    order = torch.rand(n, 16, generator=g).argsort(1)
    keep, drop = order[:, :4], order[:, 4:]
    with torch.no_grad():
        pred = model(P, keep).numpy()
    m = np.zeros((n, 16))
    np.put_along_axis(m, drop.numpy(), 1.0, 1)
    Pn = P.numpy()
    mse = (((pred - Pn) ** 2).mean(-1) * m).sum() / m.sum()
    meanp = patches(Xtr).mean(0)
    mse0 = (((meanp[None] - Pn) ** 2).mean(-1) * m).sum() / m.sum()
    return {"mse": float(mse), "mse_mean": float(mse0), "pred": pred, "keep": keep.numpy(), "m": m, "X": X}


def fig_19_6(out=None):
    """Figure 19.6 (the phenomenon at small scale): MNIST digits reconstructed by a masked autoencoder
    from 4 of their 16 patches (75% masked)."""
    r = mae_test()
    picks = [0, 1, 2, 3, 4, 7, 8, 11]
    fig, axes = plt.subplots(2, 12, figsize=(12.0, 2.5))
    for j, i in enumerate(picks):
        x = r["X"][i]
        P = patches(x[None])[0]
        vis = np.full((16, 49), np.nan)
        vis[r["keep"][i]] = P[r["keep"][i]]
        rec = np.where(r["m"][i][:, None] > 0, r["pred"][i], P)
        imgs = (unpatch(vis[None])[0], np.clip(unpatch(rec[None])[0], 0, 1), x)
        for c in range(3):
            a = axes[j // 4, (j % 4) * 3 + c]
            cm = plt.cm.gray.copy()
            cm.set_bad("#8fa8c8")
            a.imshow(np.ma.masked_invalid(imgs[c].reshape(28, 28)), cmap=cm, vmin=0, vmax=1)
            a.set_xticks([])
            a.set_yticks([])
            if j < 4:
                a.set_title(("masked", "reconstructed", "original")[c], fontsize=8)
    fig.suptitle("masked-patch MSE on 2000 test digits: %.4f (mean-patch baseline %.4f)" % (r["mse"], r["mse_mean"]), fontsize=9, y=0.02)
    fig.subplots_adjust(wspace=0.05, hspace=0.12)
    return savefig(fig, CH, "fig19-6", out)


# =========================================================================== 19.2 the circle model
ZG = np.linspace(-8.0, 8.0, 3201)
DZ = ZG[1] - ZG[0]


def circle_g(z, w=1.0):
    """The decoder mean of Figures 16.13 and 19.7: g(z) = w (sin z, cos z)."""
    return w * np.stack([np.sin(z), np.cos(z)], -1)


def circle_log_joint(x, w=1.0, sigma=0.3, z=ZG):
    """ln p(x | z, w) + ln p(z) on the grid z, with p(x | z, w) = N(x | g(z, w), sigma^2 I), p(z) = N(0, 1)."""
    g = circle_g(z, w)
    return (-((x[None, :] - g) ** 2).sum(-1) / (2 * sigma ** 2) - math.log(2 * math.pi * sigma ** 2)
            - 0.5 * z ** 2 - 0.5 * math.log(2 * math.pi))


def circle_loglik(x, w=1.0, sigma=0.3):
    """ln p(x | w) = ln int p(x | z, w) p(z) dz (trapezoid rule on ZG)."""
    a = circle_log_joint(x, w, sigma)
    m = a.max()
    return float(m + math.log(np.trapz(np.exp(a - m), dx=DZ)))


def circle_posterior(x, w=1.0, sigma=0.3):
    """p(z | x, w) on ZG by Bayes' theorem (19.12)."""
    a = circle_log_joint(x, w, sigma)
    p = np.exp(a - a.max())
    return p / np.trapz(p, dx=DZ)


def circle_elbo(x, m, s, w=1.0, sigma=0.3):
    """L(q) for q = N(z | m, s^2): int q ln{p(x|z)p(z)} dz + H[q], by quadrature on a grid around m."""
    z = m + s * np.linspace(-9, 9, 1801)
    q = np.exp(-0.5 * ((z - m) / s) ** 2) / (s * math.sqrt(2 * math.pi))
    return float(np.trapz(q * circle_log_joint(x, w, sigma, z), z) + 0.5 * math.log(2 * math.pi * math.e * s * s))


def best_gaussian_q(x, w=1.0, sigma=0.3, starts=(-2.5, -1.0, 0.0, 1.0, 2.5)):
    """argmax over (m, s) of circle_elbo (Nelder-Mead from several starts): the best Gaussian q."""
    from scipy.optimize import minimize
    best = None
    for m0 in starts:
        r = minimize(lambda p: -circle_elbo(x, p[0], math.exp(p[1]), w, sigma), [m0, math.log(0.3)], method="Nelder-Mead",
                     options=dict(xatol=1e-8, fatol=1e-10, maxiter=4000))
        if best is None or r.fun < best.fun:
            best = r
    return best.x[0], math.exp(best.x[1]), -best.fun


X_STAR = np.array([-0.2, -1.1])


def fig_19_7(out=None):
    """Figure 19.7: prior and bimodal posterior for the circle model, and the marginal p(x)."""
    sigma = 0.3
    post = circle_posterior(X_STAR)
    m, s, L = best_gaussian_q(X_STAR)
    fig = plt.figure(figsize=(12.2, 3.3))
    gs = fig.add_gridspec(1, 5, width_ratios=[1.5, 1, 1, 1, 1], wspace=0.3)
    a = fig.add_subplot(gs[0])
    prior = np.exp(-0.5 * ZG ** 2) / math.sqrt(2 * math.pi)
    a.plot(ZG, prior, color=BLUE, label="$p(z)$")
    a.plot(ZG, post, color=RED, label=r"$p(z|\mathbf{x}^\star)$")
    a.plot(ZG, np.exp(-0.5 * ((ZG - m) / s) ** 2) / (s * math.sqrt(2 * math.pi)), color=ORANGE, ls="--",
           label="best Gaussian $q$")
    a.set_xlim(-4.5, 4.5)
    a.set_xlabel("$z$")
    a.legend(frameon=False, fontsize=8)
    common.panel_label(a, "a", "upper left")
    g = np.linspace(-1.8, 1.8, 241)
    G1, G2 = np.meshgrid(g, g)
    for k, zc in enumerate((-1.5, 0.0, 1.5)):
        a = fig.add_subplot(gs[1 + k])
        c = circle_g(np.array(zc))
        dens = np.exp(-((G1 - c[0]) ** 2 + (G2 - c[1]) ** 2) / (2 * sigma ** 2))
        a.contourf(G1, G2, dens, 12, cmap="Blues")
        a.plot(*circle_g(np.linspace(-np.pi, np.pi, 200)).T, color=GREY, lw=0.6)
        a.set_title("$p(\\mathbf{x}|z=%.1f)$" % zc, fontsize=9)
        a.set_aspect("equal")
        a.set_xticks([])
        a.set_yticks([])
        if k == 0:
            common.panel_label(a, "b", "upper left")
    a = fig.add_subplot(gs[4])
    P = np.array([[math.exp(circle_loglik(np.array([u, v]))) for u in g[::3]] for v in g[::3]])
    a.contourf(g[::3], g[::3], P, 14, cmap="Blues")
    a.plot(*X_STAR, "*", color=RED, ms=10)
    a.text(X_STAR[0] + 0.12, X_STAR[1] - 0.05, r"$\mathbf{x}^\star$", color=RED)
    a.set_title(r"$p(\mathbf{x})$", fontsize=9)
    a.set_aspect("equal")
    a.set_xticks([])
    a.set_yticks([])
    return savefig(fig, CH, "fig19-7", out)


def fig_19_8(out=None):
    """Figure 19.8 (computed): ELBO curves L(w, phi) below ln p(x|w) for the circle model at x*."""
    ws = np.linspace(0.3, 1.8, 121)
    ll = np.array([circle_loglik(X_STAR, w) for w in ws])
    w0 = 0.6
    phi0 = (-2.3, 0.6)
    m1, s1, _ = best_gaussian_q(X_STAR, w0)
    L0 = np.array([circle_elbo(X_STAR, *phi0, w) for w in ws])
    L1 = np.array([circle_elbo(X_STAR, m1, s1, w) for w in ws])
    w1 = ws[np.argmax(L1)]
    fig, ax = plt.subplots(1, 2, figsize=(9.6, 3.4), sharey=True)
    for a in ax:
        a.plot(ws, ll, color=RED, lw=2, label=r"$\ln p(\mathbf{x}^\star|w)$")
        a.set_xlabel("decoder parameter $w$")
        a.set_ylim(ll.max() - 2.6, ll.max() + 1.0)
    a = ax[0]
    a.plot(ws, L0, color=BLUE, ls="--", label=r"$\mathcal{L}(w,\phi_0)$")
    a.plot(ws, L1, color=BLUE, label=r"$\mathcal{L}(w,\phi_1)$, $\phi_1$ best at $w_0$")
    a.axvline(w0, color=GREY, lw=0.7, ls=":")
    a.plot([w0, w0], [circle_elbo(X_STAR, *phi0, w0), circle_elbo(X_STAR, m1, s1, w0)], "o", color="k", ms=4)
    a.text(w0 + 0.02, ll.max() - 2.5, "$w_0$")
    a.legend(frameon=False, fontsize=8, loc="upper right")
    common.panel_label(a, "a", "upper left")
    a = ax[1]
    m2, s2, _ = best_gaussian_q(X_STAR, w1)
    L2 = np.array([circle_elbo(X_STAR, m2, s2, w) for w in ws])
    a.plot(ws, L1, color=BLUE, label=r"$\mathcal{L}(w,\phi_1)$")
    a.plot(ws, L2, color=BLUE, ls="-.", label=r"$\mathcal{L}(w,\phi_2)$, $\phi_2$ best at $w_1$")
    for wv, lab in ((w0, "$w_0$"), (w1, "$w_1$")):
        a.axvline(wv, color=GREY, lw=0.7, ls=":")
        a.text(wv + 0.02, ll.max() - 2.5, lab)
    a.plot([w0, w1], [circle_elbo(X_STAR, m1, s1, w0), L1.max()], "o", color="k", ms=4)
    a.legend(frameon=False, fontsize=8, loc="upper right")
    common.panel_label(a, "b", "upper left")
    fig.tight_layout()
    return savefig(fig, CH, "fig19-8", out)


EM_SIGMA = 0.7


def circle_data(n=20, w=1.0, sigma=EM_SIGMA, seed=4):
    rng = np.random.default_rng(seed)
    z = rng.standard_normal(n)
    return circle_g(z, w) + sigma * rng.standard_normal((n, 2))


def em_circle(Xd, w0=0.4, iters=12, sigma=0.3):
    """EM for the scalar w with the exact posterior on the grid (E step) and the closed-form M step
    w = sum_n E_q[g(z)]^T x_n / sum_n E_q[||g(z)||^2] = (1/N) sum_n E_q[(sin z, cos z)]^T x_n.
    Returns the sequence (w, ln p(X|w), bound after E, bound after M)."""
    def total_ll(w):
        return sum(circle_loglik(x, w, sigma) for x in Xd)

    def bound(w, posts):
        tot = 0.0
        for x, q in zip(Xd, posts):
            lj = circle_log_joint(x, w, sigma)
            qq = np.maximum(q, 1e-300)
            tot += np.trapz(q * (lj - np.log(qq)), dx=DZ)
        return tot
    w = w0
    rows = []
    for _ in range(iters):
        posts = [circle_posterior(x, w, sigma) for x in Xd]
        lE = bound(w, posts)
        num = sum(np.trapz(q[:, None] * circle_g(ZG), dx=DZ, axis=0) @ x for x, q in zip(Xd, posts))
        w_new = num / len(Xd)
        lM = bound(w_new, posts)
        rows.append((w, total_ll(w), lE, lM))
        w = w_new
    return np.array(rows)


def joint_elbo_ascent(Xd, w0=0.4, iters=300, lr=0.02, sigma=0.3):
    """Joint gradient ascent on the quadrature ELBO over w and per-point Gaussian q_n = N(m_n, s_n^2)
    (torch autograd, double precision). Returns rows (iteration, ln p(X|w), ELBO, w)."""
    torch = _torch()
    t = torch.tensor(np.linspace(-9, 9, 721), dtype=torch.float64)
    X = torch.tensor(Xd, dtype=torch.float64)
    w = torch.tensor(w0, dtype=torch.float64, requires_grad=True)
    m = torch.tensor(np.arctan2(Xd[:, 0], Xd[:, 1]) * 0.5, dtype=torch.float64, requires_grad=True)
    ls = torch.full((len(Xd),), math.log(0.5), dtype=torch.float64, requires_grad=True)
    opt = torch.optim.Adam([w, m, ls], lr=lr)
    rows = []
    for it in range(iters + 1):
        s = ls.exp()
        z = m[:, None] + s[:, None] * t[None, :]
        q = torch.exp(-0.5 * t ** 2) / math.sqrt(2 * math.pi)
        g1, g2 = w * torch.sin(z), w * torch.cos(z)
        lj = (-((X[:, 0:1] - g1) ** 2 + (X[:, 1:2] - g2) ** 2) / (2 * sigma ** 2) - math.log(2 * math.pi * sigma ** 2)
              - 0.5 * z ** 2 - 0.5 * math.log(2 * math.pi))
        elbo = (torch.trapezoid(q[None, :] * lj, t, dim=1) + 0.5 * math.log(2 * math.pi * math.e) + ls).sum()
        if it % 5 == 0:
            wv = float(w.detach())
            rows.append((it, sum(circle_loglik(x, wv, sigma) for x in Xd), float(elbo.detach()), wv))
        if it == iters:
            break
        opt.zero_grad()
        (-elbo).backward()
        opt.step()
    return np.array(rows)


def fig_19_9(out=None):
    """Figure 19.9 (computed): EM with an exact E step closes the gap after every E step; joint ELBO
    ascent with a Gaussian q leaves a gap (circle model with sigma = 0.7, 20 data points)."""
    sig = EM_SIGMA
    Xd = circle_data(20, 1.0, sig)
    em = em_circle(Xd, 0.1, 8, sig)
    jr = joint_elbo_ascent(Xd, 0.1, 300, 0.02, sig)
    fig, ax = plt.subplots(1, 2, figsize=(10.4, 3.5))
    a = ax[0]
    xs, ys = [], []
    for i, (w, ll, lE, lM) in enumerate(em):
        xs += [i, i + 1]
        ys += [lE, lM]
    a.plot(np.arange(len(em)), em[:, 1], "o", color=RED, ms=5, label=r"$\ln p(\mathbf{X}|w)$ at $w^{(t)}$", zorder=3)
    a.plot(xs, ys, "-", color=BLUE, lw=1.2, label="bound: E step (vertical), M step")
    for i in range(len(em) - 1):
        a.plot([i + 1, i + 1], [em[i, 3], em[i + 1, 1]], color=BLUE, lw=1.2)
    a.set_xlabel("EM iteration $t$")
    a.set_title("EM: each exact E step closes the gap", fontsize=10)
    a.legend(frameon=False, fontsize=8, loc="lower right")
    a.set_ylim(em[0, 1] - 1, em[-1, 1] + 1)
    common.panel_label(a, "a", "upper left")
    a = ax[1]
    a.plot(jr[:, 0], jr[:, 1], color=RED, label=r"$\ln p(\mathbf{X}|w)$")
    a.plot(jr[:, 0], jr[:, 2], color=BLUE, label="ELBO, Gaussian $q_n$")
    a.set_xlabel("joint gradient step (Adam)")
    a.set_ylim(em[0, 1] - 1, em[-1, 1] + 1)
    a.set_title("joint ascent: %.2f nats remain; $w$ = %.3f (ML %.3f)" % (jr[-1, 1] - jr[-1, 2], jr[-1, 3], em[-1, 0]), fontsize=9.5)
    a.legend(frameon=False, fontsize=8, loc="lower left", bbox_to_anchor=(0.38, 0.5))
    common.panel_label(a, "b", "upper left")
    ins = a.inset_axes([0.42, 0.12, 0.33, 0.33])
    ins.plot(jr[:, 0], jr[:, 1] - jr[:, 2], color="k", lw=1)
    ins.set_ylim(0, 3)
    ins.set_title("gap", fontsize=8)
    ins.tick_params(labelsize=7)
    fig.tight_layout()
    return savefig(fig, CH, "fig19-9", out)


def circle_dlogjoint(x, z, w=1.0, sigma=0.3):
    """d/dz [ln p(x|z,w) + ln p(z)] = (w/sigma^2) [(x1 - w sin z) cos z - (x2 - w cos z) sin z] - z."""
    s, c = math.sin(z), math.cos(z)
    return (w / sigma ** 2) * ((x[0] - w * s) * c - (x[1] - w * c) * s) - z


def fit_q_reparam(x, m0=0.0, ls0=math.log(0.5), steps=400, lr=0.05, L=1, w=1.0, sigma=0.3, seed=1):
    """Gradient ascent on the ELBO of q = N(m, s^2) with the reparameterisation z = m + s eps:
    per sample, d/dm = f'(z) and d/d ln s = f'(z) s eps, plus 1 from the entropy ln s; f = ln p(x, z).
    Plain gradient steps of size lr (the arithmetic of elbo-gap-demo.html). Returns the (m, ln s) path."""
    r = JSRandom(seed)
    m, ls = m0, ls0
    path = [(m, ls)]
    for _ in range(steps):
        s = math.exp(ls)
        gm, gl = 0.0, 0.0
        for _ in range(L):
            e = r.norm()
            fp = circle_dlogjoint(x, m + s * e, w, sigma)
            gm += fp
            gl += fp * s * e
        m += lr * gm / L
        ls += lr * (gl / L + 1.0)
        path.append((m, ls))
    return np.array(path)


# =========================================================================== 19.2 VAEs on MNIST
def binarised_mnist(train=True):
    X, y = common.mnist(train)
    return (X > 0.5).astype(np.float32), y


def _vae_modules(torch, M=VAE_M):
    nn = torch.nn
    enc = nn.Sequential(nn.Linear(784, 256), nn.Tanh(), nn.Linear(256, 2 * M))
    dec = nn.Sequential(nn.Linear(M, 128), nn.Tanh(), nn.Linear(128, 784))
    return enc, dec


def gaussian_kl_std(mu, logvar):
    """KL(N(mu, diag exp(logvar)) || N(0, I)) = 1/2 sum_j (mu_j^2 + sigma_j^2 - 1 - ln sigma_j^2):
    the correct sign of (19.15)."""
    return 0.5 * (mu ** 2 + np.exp(logvar) - 1.0 - logvar).sum(-1)


def train_vae(beta, epochs=12, M=VAE_M, seed=0):
    """A VAE with q(z|x) = N(mu(x), diag sigma^2(x)) (19.13) and a Bernoulli decoder on binarised MNIST,
    trained with Adam (1e-3, batch 100) on the negative of E_q[ln p(x|z)] - beta KL (one reparameterised
    sample, (19.19) with the KL weighted by beta). Cached in cache/."""
    torch = _torch()
    enc, dec = _vae_modules(torch, M)
    path = _cache("ch19_vae_b%g.pt" % beta)
    if os.path.exists(path):
        st = torch.load(path)
        enc.load_state_dict(st["enc"])
        dec.load_state_dict(st["dec"])
        return torch, enc, dec
    torch.manual_seed(seed)
    enc, dec = _vae_modules(torch, M)
    X, _ = binarised_mnist(True)
    Xt = torch.tensor(X)
    opt = torch.optim.Adam(list(enc.parameters()) + list(dec.parameters()), lr=1e-3)
    g = torch.Generator().manual_seed(seed)
    bce = torch.nn.functional.binary_cross_entropy_with_logits
    for ep in range(epochs):
        perm = torch.randperm(len(Xt), generator=g)
        tr, tk = 0.0, 0.0
        for i in range(0, len(Xt), 100):
            xb = Xt[perm[i:i + 100]]
            h = enc(xb)
            mu, lv = h[:, :M], h[:, M:]
            z = mu + torch.exp(0.5 * lv) * torch.randn(mu.shape, generator=g)
            rec = bce(dec(z), xb, reduction="sum") / len(xb)
            kl = 0.5 * (mu ** 2 + lv.exp() - 1 - lv).sum() / len(xb)
            loss = rec + beta * kl
            opt.zero_grad()
            loss.backward()
            opt.step()
            tr += float(rec.detach())
            tk += float(kl.detach())
        nb = len(Xt) // 100
        print("  beta %g epoch %d: distortion %.2f rate %.2f" % (beta, ep + 1, tr / nb, tk / nb))
    torch.save({"enc": enc.state_dict(), "dec": dec.state_dict()}, path)
    return torch, enc, dec


def vae_eval(beta, n=10000, S=10, seed=0):
    """Rate R = E KL(q||p), distortion D = -E_q ln p(x|z) (S samples), KL per latent dimension and
    the number of active units (Cov_x E_q[z_j] > 0.01, Burda et al. 2016) on n test digits."""
    path = _cache("ch19_vae_eval_b%g.npz" % beta)
    if os.path.exists(path):
        d = np.load(path)
        return {k: d[k] for k in d.files}
    torch, enc, dec = train_vae(beta)
    X, _ = binarised_mnist(False)
    Xt = torch.tensor(X[:n])
    g = torch.Generator().manual_seed(seed)
    bce = torch.nn.functional.binary_cross_entropy_with_logits
    with torch.no_grad():
        h = enc(Xt)
        mu, lv = h[:, :VAE_M], h[:, VAE_M:]
        D = 0.0
        for _ in range(S):
            z = mu + torch.exp(0.5 * lv) * torch.randn(mu.shape, generator=g)
            D += float(bce(dec(z), Xt, reduction="sum")) / n / S
    mu, lv = mu.numpy().astype(float), lv.numpy().astype(float)
    kld = (0.5 * (mu ** 2 + np.exp(lv) - 1 - lv)).mean(0)
    res = {"beta": beta, "R": kld.sum(), "D": D, "kl_dim": kld, "au": int((mu.var(0) > 0.01).sum()), "mu_var": mu.var(0)}
    np.savez(path, **res)
    return res


def iwae_bound(torch, enc, dec, X, K=1000, seed=0, chunk=250, mu=None, lv=None):
    """ln (1/K) sum_k p(x|z_k) p(z_k) / q(z_k|x), z_k ~ q(z|x): a stochastic lower bound on ln p(x) that
    increases with K (Burda et al. 2016) and is the importance-sampling estimate the book suggests on
    p. 576 for assessing a test point. Returns one value per row of X. A different Gaussian proposal can
    be passed as (mu, lv) (means and log-variances, one row per digit)."""
    g = torch.Generator().manual_seed(seed)
    bce = torch.nn.functional.binary_cross_entropy_with_logits
    Xt = torch.tensor(X)
    out = []
    with torch.no_grad():
        h = enc(Xt)
        if mu is None:
            mu, lv = h[:, :VAE_M], h[:, VAE_M:]
        mu, lv = torch.as_tensor(mu).double(), torch.as_tensor(lv).double()
        for i in range(len(X)):
            lw = []
            for c in range(0, K, chunk):
                e = torch.randn(min(chunk, K - c), VAE_M, generator=g, dtype=torch.float64)
                z = mu[i] + torch.exp(0.5 * lv[i]) * e
                lpx = -bce(dec(z.float()), Xt[i].expand(len(z), -1), reduction="none").sum(1).double()
                lpz = -0.5 * (z ** 2).sum(1) - 0.5 * VAE_M * math.log(2 * math.pi)
                lq = -0.5 * (e ** 2).sum(1) - 0.5 * lv[i].sum() - 0.5 * VAE_M * math.log(2 * math.pi)
                lw.append(lpx + lpz - lq)
            lw = torch.cat(lw)
            out.append(float(torch.logsumexp(lw, 0) - math.log(K)))
    return np.array(out)


def amortisation_gap(n=100, steps=400, S=16, seed=0):
    """For n test digits (beta = 1 VAE): ln p(x), estimated by the importance-weighted bound with
    K = 5000 samples from the per-digit optimised Gaussian (the better of the two proposals), the
    amortised ELBO (encoder q) and the ELBO of the best Gaussian q found per digit by Adam from the
    encoder's output (reparameterisation, S samples; evaluated with 1000 samples)."""
    path = _cache("ch19_amort.npz")
    if os.path.exists(path):
        d = np.load(path)
        return {k: d[k] for k in d.files}
    torch, enc, dec = train_vae(1.0)
    X, _ = binarised_mnist(False)
    X = X[:n]
    Xt = torch.tensor(X)
    bce = torch.nn.functional.binary_cross_entropy_with_logits
    g = torch.Generator().manual_seed(seed)

    def elbo(mu, lv, Ssamp):
        e = torch.randn(Ssamp, *mu.shape, generator=g)
        z = mu + torch.exp(0.5 * lv) * e
        lpx = -bce(dec(z), Xt.expand(Ssamp, -1, -1), reduction="none").sum(-1).mean(0)
        return lpx - 0.5 * (mu ** 2 + lv.exp() - 1 - lv).sum(-1)
    with torch.no_grad():
        h = enc(Xt)
        mu0, lv0 = h[:, :VAE_M].clone(), h[:, VAE_M:].clone()
        L_am = elbo(mu0, lv0, 1000).numpy()
    for p in dec.parameters():
        p.requires_grad_(False)
    mu = mu0.clone().requires_grad_(True)
    lv = lv0.clone().requires_grad_(True)
    opt = torch.optim.Adam([mu, lv], lr=0.01)
    for _ in range(steps):
        loss = -elbo(mu, lv, S).sum()
        opt.zero_grad()
        loss.backward()
        opt.step()
    with torch.no_grad():
        L_opt = elbo(mu, lv, 1000).numpy()
    logp = iwae_bound(torch, enc, dec, X, K=5000, mu=mu.detach(), lv=lv.detach())
    res = {"logp": logp, "L_am": L_am, "L_opt": L_opt}
    np.savez(path, **res)
    return res


def fig_19_s5(out=None):
    """Figure 19.S5: log likelihood, best-Gaussian ELBO and amortised ELBO on 100 MNIST test digits."""
    r = amortisation_gap()
    torch, enc, dec = train_vae(1.0)
    X, _ = binarised_mnist(False)
    Ks = (1, 10, 100, 1000)
    iw = [iwae_bound(torch, enc, dec, X[:20], K=k, seed=1).mean() for k in Ks]
    fig, ax = plt.subplots(1, 3, figsize=(12.0, 3.4))
    a = ax[0]
    o = np.argsort(r["logp"])
    a.plot(r["logp"][o], color=RED, label=r"$\ln p(\mathbf{x})$ (IWAE, $K=5000$, optimised $q$)")
    a.plot(r["L_opt"][o], color=ORANGE, lw=1, label="ELBO, best Gaussian per digit")
    a.plot(r["L_am"][o], color=BLUE, lw=1, label="ELBO, amortised encoder")
    a.set_xlabel("test digit (sorted by $\\ln p$)")
    a.set_ylabel("nats")
    a.legend(frameon=False, fontsize=7.5)
    common.panel_label(a, "a", "lower right")
    a = ax[1]
    approx = r["logp"] - r["L_opt"]
    amort = r["L_opt"] - r["L_am"]
    a.bar([0, 1], [approx.mean(), amort.mean()], yerr=[approx.std() / 10, amort.std() / 10], color=[ORANGE, BLUE], capsize=4)
    a.set_xticks([0, 1])
    a.set_xticklabels(["approximation gap\n$\\ln p-\\mathcal{L}^\\star$", "amortisation gap\n$\\mathcal{L}^\\star-\\mathcal{L}(\\phi)$"], fontsize=8.5)
    a.set_ylabel("nats per digit (mean $\\pm$ s.e.)")
    common.panel_label(a, "b", "upper right")
    a = ax[2]
    a.semilogx(Ks, iw, "o-", color=PURPLE)
    a.set_xlabel("number of importance samples $K$")
    a.set_ylabel("mean IWAE bound (20 digits)")
    a.set_title("$K=1$ is the ELBO; the bound rises with $K$", fontsize=9.5)
    common.panel_label(a, "c", "lower right")
    fig.tight_layout()
    return savefig(fig, CH, "fig19-s5", out)


def grad_variance(n_rep=2000, idx=0, seed=0):
    """Single-sample estimates of the gradient of E_q[ln p(x|z)] with respect to the encoder outputs
    (mu_j, ln sigma_j^2) for one test digit (beta = 1 VAE): the reparameterisation estimator, the
    score-function estimator (19.21) and the score function with the optimal constant baseline per
    coordinate; plus the exact gradient (average of 200000 reparameterised samples)."""
    path = _cache("ch19_gradvar.npz")
    if os.path.exists(path):
        d = np.load(path)
        return {k: d[k] for k in d.files}
    torch, enc, dec = train_vae(1.0)
    X, _ = binarised_mnist(False)
    x = torch.tensor(X[idx:idx + 1])
    bce = torch.nn.functional.binary_cross_entropy_with_logits
    g = torch.Generator().manual_seed(seed)
    with torch.no_grad():
        h = enc(x)[0].double()
    mu0, lv0 = h[:VAE_M], h[VAE_M:]
    for p in dec.parameters():
        p.requires_grad_(False)

    def f(z):
        return -bce(dec(z.float()), x.expand(len(z), -1), reduction="none").sum(1).double()
    e = torch.randn(n_rep, VAE_M, generator=g, dtype=torch.float64)
    mu = mu0.clone().requires_grad_(True)
    lv = lv0.clone().requires_grad_(True)
    z = mu + torch.exp(0.5 * lv) * e
    fv = f(z)
    rp = []
    for i in range(n_rep):
        gm, gl = torch.autograd.grad(fv[i], [mu, lv], retain_graph=True)
        rp.append(torch.cat([gm, gl]).numpy())
    rp = np.array(rp)
    fz = fv.detach().numpy()
    en = e.numpy()
    sm = en / np.exp(0.5 * lv0.numpy())
    sl = 0.5 * (en ** 2 - 1)
    score = np.concatenate([sm, sl], 1)
    sf = fz[:, None] * score
    b = (fz[:, None] * score ** 2).mean(0) / (score ** 2).mean(0)
    sfb = (fz[:, None] - b[None, :]) * score
    with torch.no_grad():
        pass
    E2 = torch.randn(200000, VAE_M, generator=g, dtype=torch.float64)
    mu2 = mu0.clone().requires_grad_(True)
    lv2 = lv0.clone().requires_grad_(True)
    tot = 0
    for c in range(0, 200000, 20000):
        zz = mu2 + torch.exp(0.5 * lv2) * E2[c:c + 20000]
        tot = tot + f(zz).sum()
    gm, gl = torch.autograd.grad(tot / 200000, [mu2, lv2])
    exact = torch.cat([gm, gl]).numpy()
    res = {"rp": rp, "sf": sf, "sfb": sfb, "exact": exact, "f": fz}
    np.savez(path, **res)
    return res


def fig_19_s6(out=None):
    """Figure 19.S6: reparameterisation versus score-function gradients of a VAE's ELBO."""
    r = grad_variance()
    j = int(np.argmax(np.abs(r["exact"][:VAE_M])))
    fig, ax = plt.subplots(1, 2, figsize=(10.4, 3.4))
    a = ax[0]
    lo, hi = np.percentile(r["sf"][:, j], [1, 99])
    bins = np.linspace(lo, hi, 70)
    a.hist(np.clip(r["sf"][:, j], lo, hi), bins, color=RED, alpha=0.5, density=True, label="score function (19.21)")
    a.hist(np.clip(r["sfb"][:, j], lo, hi), bins, color=ORANGE, alpha=0.5, density=True, label="score function + baseline")
    a.hist(np.clip(r["rp"][:, j], lo, hi), bins, color=BLUE, alpha=0.8, density=True, label="reparameterisation")
    a.axvline(r["exact"][j], color="k", lw=1)
    a.set_xlabel(r"single-sample estimate of $\partial E_q[\ln p(\mathbf{x}|\mathbf{z})]/\partial\mu_{%d}$" % (j + 1))
    a.set_yscale("log")
    a.legend(frameon=False, fontsize=7.5, loc="upper left")
    common.panel_label(a, "a", "upper right")
    a = ax[1]
    k = np.arange(2 * VAE_M)
    for est, col, lab, mk in ((r["sf"], RED, "score function", "o"), (r["sfb"], ORANGE, "+ baseline", "s"), (r["rp"], BLUE, "reparameterisation", "^")):
        a.semilogy(k, est.var(0), mk, color=col, label=lab, ms=4)
    a.set_xticks(k)
    a.set_xticklabels(["$\\mu_{%d}$" % (i + 1) for i in range(VAE_M)] + ["$s_{%d}$" % (i + 1) for i in range(VAE_M)], fontsize=6.5, rotation=90)
    a.set_ylabel("variance of one-sample estimate")
    a.legend(frameon=False, fontsize=7.5)
    common.panel_label(a, "b", "lower right")
    fig.tight_layout()
    return savefig(fig, CH, "fig19-s6", out)


def vae_decode(dec_np, Z):
    """The exported decoder, run in float64: sigmoid(W2 tanh(W1 z + b1) + b2)."""
    W1, b1, W2, b2 = dec_np
    h = np.tanh(Z @ W1.T + b1)
    return 1.0 / (1.0 + np.exp(-(h @ W2.T + b2)))


def vae_decoder_f16(beta):
    """The decoder weights rounded to float16 (as exported), as float64 arrays."""
    torch, enc, dec = train_vae(beta)
    return [p.detach().numpy().astype(np.float16).astype(np.float64) for p in
            (dec[0].weight, dec[0].bias, dec[2].weight, dec[2].bias)]


VAE_TEST_IDX = (3, 2, 1, 18, 4, 8, 11, 0, 61, 7, 10, 5)


def export_vae():
    """../data/ch19-vae-summary.json (rate, distortion, KL per dimension, active units for every beta,
    the 12 test digits) and ../data/ch19-vae-b<beta>.json (float16 decoder weights and the encoder
    means and standard deviations of the 12 test digits)."""
    X, y = binarised_mnist(False)
    summ = {"about": "beta-VAEs (M = 10, Bernoulli decoder 10-128-784, encoder 784-256-20) on binarised MNIST; "
                     "rate R and distortion D in nats per test digit (10000 test digits); written by ch19_autoencoders.py.",
            "betas": list(BETAS), "M": VAE_M, "rows": [], "digits": b64_u8(np.packbits(X[list(VAE_TEST_IDX)].astype(np.uint8))),
            "labels": [int(y[i]) for i in VAE_TEST_IDX]}
    for beta in BETAS:
        ev = vae_eval(beta)
        summ["rows"].append({"beta": beta, "R": float(ev["R"]), "D": float(ev["D"]), "au": int(ev["au"]),
                             "kl_dim": [float(v) for v in ev["kl_dim"]]})
        torch, enc, dec = train_vae(beta)
        with torch.no_grad():
            h = enc(torch.tensor(X[list(VAE_TEST_IDX)])).numpy().astype(float)
        W = vae_decoder_f16(beta)
        _write_json("ch19-vae-b%g.json" % beta, {
            "beta": beta, "shapes": [list(w.shape) for w in W], "weights": [b64_f16(w) for w in W],
            "mu": h[:, :VAE_M].round(6).tolist(), "sd": np.exp(0.5 * h[:, VAE_M:]).round(6).tolist()})
    return _write_json("ch19-vae-summary.json", summ)


def fig_19_s7(out=None):
    """Figure 19.S7: the beta trade-off on MNIST: rate against distortion, KL per latent dimension,
    reconstructions and samples from the prior."""
    evs = [vae_eval(b) for b in BETAS]
    X, _ = binarised_mnist(False)
    fig = plt.figure(figsize=(12.6, 6.4))
    gs = fig.add_gridspec(2, 3, height_ratios=[1, 1.05], hspace=0.35, wspace=0.5)
    a = fig.add_subplot(gs[0, 0])
    R = np.array([e["R"] for e in evs])
    D = np.array([e["D"] for e in evs])
    a.plot(R, D, "o-", color=RED)
    for e in evs:
        a.annotate(r"$\beta=%g$" % e["beta"], (e["R"], e["D"]), textcoords="offset points", xytext=(5, 4), fontsize=7.5)
    Rl = np.linspace(0, R.max(), 10)
    a.plot(Rl, -Rl + (D + R).min(), ":", color=GREY, lw=0.8)
    a.set_xlabel("rate $R=E\\,\\mathrm{KL}(q\\|p)$ (nats)")
    a.set_ylabel("distortion $D=-E_q\\ln p(\\mathbf{x}|\\mathbf{z})$")
    a.set_title("rate-distortion curve (dotted: slope $-1$)", fontsize=9.5)
    common.panel_label(a, "a", "upper right")
    a = fig.add_subplot(gs[0, 1])
    K = np.array([np.sort(e["kl_dim"])[::-1] for e in evs])
    im = a.imshow(K, aspect="auto", cmap="magma_r")
    a.set_yticks(range(len(BETAS)))
    a.set_yticklabels([r"$\beta=%g$ (AU %d)" % (e["beta"], e["au"]) for e in evs], fontsize=7.5)
    a.set_xticks(range(VAE_M))
    a.set_xticklabels([str(i + 1) for i in range(VAE_M)], fontsize=7)
    a.set_xlabel("latent dimension (sorted by KL)")
    fig.colorbar(im, ax=a, fraction=0.05, pad=0.03, label="KL per dimension (nats)")
    a.set_title("KL per latent dimension; AU = active units", fontsize=9.5)
    a = fig.add_subplot(gs[0, 2])
    a.semilogx(BETAS, -(D + R), "o-", color=BLUE)
    a.set_xticks(BETAS)
    a.set_xticklabels(["%g" % b for b in BETAS])
    a.set_xlabel(r"$\beta$ used in training")
    a.set_ylabel("ELBO ($\\beta=1$) per test digit")
    a.set_title("the ELBO itself is best near $\\beta=1$", fontsize=9.5)
    common.panel_label(a, "c", "lower left")
    show = (0.25, 1.0, 4.0, 16.0)
    sub = gs[1, :].subgridspec(len(show), 2, wspace=0.05, hspace=0.15)
    rng = np.random.default_rng(5)
    Zp = rng.standard_normal((10, VAE_M))
    for i, beta in enumerate(show):
        torch, enc, dec = train_vae(beta)
        W = vae_decoder_f16(beta)
        with torch.no_grad():
            h = enc(torch.tensor(X[list(VAE_TEST_IDX[:10])])).numpy().astype(float)
        rec = vae_decode(W, h[:, :VAE_M])
        smp = vae_decode(W, Zp)
        for c, imgs in enumerate((np.concatenate([X[list(VAE_TEST_IDX[:10])], rec]), smp)):
            a = fig.add_subplot(sub[i, c])
            if c == 0:
                row = np.concatenate([np.concatenate([imgs[k].reshape(28, 28), imgs[10 + k].reshape(28, 28)], 0) for k in range(10)], 1)
            else:
                row = np.concatenate([imgs[k].reshape(28, 28) for k in range(10)], 1)
            a.imshow(row, cmap="gray_r", vmin=0, vmax=1, aspect="auto" if c == 1 else "equal")
            a.set_xticks([])
            a.set_yticks([])
            if c == 0:
                a.set_ylabel(r"$\beta=%g$" % beta, fontsize=8.5)
            if i == 0:
                a.set_title(("test digits (top) and reconstructions from $\\boldsymbol{\\mu}(\\mathbf{x})$ (bottom)",
                             "decoder means for 10 draws $\\mathbf{z}\\sim\\mathcal{N}(\\mathbf{0},\\mathbf{I})$")[c], fontsize=9)
    return savefig(fig, CH, "fig19-s7", out)


# =========================================================================== linear Gaussian VAE
LIN_LAM = np.array([4.0, 2.5, 1.6, 1.0, 0.6, 0.35, 0.2, 0.1])
LIN_S2 = 0.1


def linear_vae_closed_form(beta, lam=LIN_LAM, s2=LIN_S2, M=None):
    """Optimum of E_q ln p(x|z) - beta KL(q||p) for p(z) = N(0, I_M), p(x|z) = N(Wz + b, s2 I) and a
    linear encoder with diagonal covariance, on data with covariance eigenvalues lam: the probabilistic
    PCA solution with noise variance beta s2. Returns the number of active dimensions, the rate
    R = sum_j 1/2 ln(lam_j / (beta s2))_+ and the squared-error distortion
    D2 = sum_j min(lam_j, beta s2) over the first M directions + sum of the remaining lam_j."""
    M = len(lam) if M is None else M
    th = beta * s2
    act = lam[:M] > th
    R = 0.5 * np.log(lam[:M][act] / th).sum()
    D2 = np.minimum(lam[:M], th).sum() + lam[M:].sum()
    return int(act.sum()), float(R), float(D2)


def train_linear_vae(beta, n=20000, steps=6000, lr=0.01, seed=0, lam=LIN_LAM, s2=LIN_S2):
    """Linear VAE trained by Adam with the reparameterisation trick: data x ~ N(0, U diag(lam) U^T)
    (U a fixed random rotation), encoder q(z|x) = N(V x, diag(exp(l))) (a constant diagonal covariance,
    which is optimal for this model), decoder N(W z, s2 I). Returns W, V, l, U and the exact rate and
    squared-error distortion of the trained parameters (expectations in closed form)."""
    torch = _torch()
    torch.manual_seed(seed)
    D = len(lam)
    rng = np.random.default_rng(seed)
    U = np.linalg.qr(rng.standard_normal((D, D)))[0]
    X = (rng.standard_normal((n, D)) * np.sqrt(lam)) @ U.T
    Xt = torch.tensor(X)
    W = torch.nn.Parameter(0.1 * torch.randn(D, D, dtype=torch.float64))
    V = torch.nn.Parameter(0.1 * torch.randn(D, D, dtype=torch.float64))
    lv = torch.nn.Parameter(torch.zeros(D, dtype=torch.float64))
    opt = torch.optim.Adam([W, V, lv], lr=lr)
    sched = torch.optim.lr_scheduler.ExponentialLR(opt, (0.02) ** (1.0 / steps))
    g = torch.Generator().manual_seed(seed)
    for t in range(steps):
        xb = Xt[torch.randint(0, n, (256,), generator=g)]
        mu = xb @ V.T
        z = mu + torch.exp(0.5 * lv) * torch.randn(mu.shape, generator=g, dtype=torch.float64)
        rec = ((xb - z @ W.T) ** 2).sum(1).mean() / (2 * s2)
        kl = 0.5 * ((mu ** 2).sum(1).mean() + lv.exp().sum() - D - lv.sum())
        loss = rec + beta * kl
        opt.zero_grad()
        loss.backward()
        opt.step()
        sched.step()
    Wn, Vn, ln_ = W.detach().numpy(), V.detach().numpy(), lv.detach().numpy()
    S = U @ np.diag(lam) @ U.T
    R = 0.5 * (np.trace(Vn @ S @ Vn.T) + np.exp(ln_).sum() - D - ln_.sum())
    A = np.eye(D) - Wn @ Vn
    D2 = np.trace(A @ S @ A.T) + np.trace(Wn @ np.diag(np.exp(ln_)) @ Wn.T)
    kl_dim = 0.5 * (np.diag(Vn @ S @ Vn.T) + np.exp(ln_) - 1 - ln_)
    return {"W": Wn, "V": Vn, "l": ln_, "U": U, "R": float(R), "D2": float(D2), "kl_dim": kl_dim}


def linear_vae_exact(beta, seed=0, lam=LIN_LAM, s2=LIN_S2, iters=400):
    """The same linear VAE with the expectations over the data and over q done in closed form,
    E||x - W z||^2 = tr S - 2 tr(W V S) + tr(W (V S V^T + diag e^l) W^T) and
    KL = 1/2 (tr(V S V^T) + sum e^l - D - sum l), maximised by L-BFGS (double precision) from a random
    start. Returns the same fields as train_linear_vae."""
    torch = _torch()
    D = len(lam)
    rng = np.random.default_rng(seed)
    U = np.linalg.qr(rng.standard_normal((D, D)))[0]
    S = torch.tensor(U @ np.diag(lam) @ U.T)
    torch.manual_seed(seed + 1)
    W = (0.3 * torch.randn(D, D, dtype=torch.float64)).requires_grad_(True)
    V = (0.3 * torch.randn(D, D, dtype=torch.float64)).requires_grad_(True)
    lv = torch.zeros(D, dtype=torch.float64, requires_grad=True)
    opt = torch.optim.LBFGS([W, V, lv], lr=1, max_iter=iters, tolerance_grad=1e-12, tolerance_change=1e-15,
                            history_size=50, line_search_fn="strong_wolfe")

    def obj():
        opt.zero_grad()
        VS = V @ S
        d2 = torch.trace(S) - 2 * torch.trace(W @ VS) + torch.trace(W @ (VS @ V.T + torch.diag(lv.exp())) @ W.T)
        kl = 0.5 * (torch.trace(VS @ V.T) + lv.exp().sum() - D - lv.sum())
        loss = d2 / (2 * s2) + beta * kl
        loss.backward()
        return loss
    for _ in range(5):
        opt.step(obj)
    Wn, Vn, ln_ = W.detach().numpy(), V.detach().numpy(), lv.detach().numpy()
    Sn = S.numpy()
    A = np.eye(D) - Wn @ Vn
    D2 = np.trace(A @ Sn @ A.T) + np.trace(Wn @ np.diag(np.exp(ln_)) @ Wn.T)
    kl_dim = 0.5 * (np.diag(Vn @ Sn @ Vn.T) + np.exp(ln_) - 1 - ln_)
    return {"W": Wn, "V": Vn, "l": ln_, "U": U, "R": float(kl_dim.sum()), "D2": float(D2), "kl_dim": kl_dim}


LIN_BETAS = (0.6, 1.4, 2.6, 4.5, 8.0, 13.0, 20.0, 30.0)


def fig_19_s8(out=None):
    """Figure 19.S8: the linear Gaussian VAE: active dimensions and rate-distortion in closed form,
    against VAEs trained by stochastic gradients."""
    path = _cache("ch19_linvae.npz")
    if os.path.exists(path):
        d = np.load(path, allow_pickle=True)
        tr = list(d["tr"])
    else:
        tr = [train_linear_vae(b) for b in LIN_BETAS]
        np.savez(path, tr=np.array(tr, dtype=object))
    bs = np.geomspace(0.3, 60, 300)
    cf = np.array([linear_vae_closed_form(b) for b in bs])
    fig, ax = plt.subplots(1, 3, figsize=(12.4, 3.5))
    a = ax[0]
    a.semilogx(bs, cf[:, 0], color=RED, label="closed form")
    au = [int((t["kl_dim"] > 0.01).sum()) for t in tr]
    a.semilogx(LIN_BETAS, au, "o", color=BLUE, label="trained (dimensions with KL > 0.01)")
    for lj in LIN_LAM:
        a.axvline(lj / LIN_S2, color=GREY, lw=0.5, ls=":")
    a.set_xlabel(r"$\beta$ (dotted: $\lambda_j/s^2$)")
    a.set_ylabel("active latent dimensions")
    a.legend(frameon=False, fontsize=7.5, loc="upper right")
    common.panel_label(a, "a", "lower left")
    a = ax[1]
    a.plot(cf[:, 1], cf[:, 2] / (2 * LIN_S2), color=RED, label="closed form")
    a.plot([t["R"] for t in tr], [t["D2"] / (2 * LIN_S2) for t in tr], "o", color=BLUE, label="trained")
    for t, b in zip(tr, LIN_BETAS):
        a.annotate(r"$\beta=%g$" % b, (t["R"], t["D2"] / (2 * LIN_S2)), textcoords="offset points", xytext=(4, 3), fontsize=7)
    a.set_xlabel("rate $R$ (nats)")
    a.set_ylabel(r"distortion $E\|\mathbf{x}-\mathbf{W}\mathbf{z}\|^2/2s^2$")
    a.legend(frameon=False, fontsize=8)
    common.panel_label(a, "b", "upper right")
    a = ax[2]
    t = linear_vae_exact(2.6)
    C = np.abs(t["U"].T @ (t["W"] / np.maximum(np.linalg.norm(t["W"], axis=0), 1e-12)))
    C[:, t["kl_dim"] < 1e-6] = np.nan
    im = a.imshow(C, cmap="Blues", vmin=0, vmax=1)
    a.set_xticks(range(len(LIN_LAM)))
    a.set_yticks(range(len(LIN_LAM)))
    a.set_xticklabels([str(i + 1) for i in range(len(LIN_LAM))])
    a.set_yticklabels([str(i + 1) for i in range(len(LIN_LAM))])
    a.set_xlabel("decoder column $j$ (blank: collapsed)")
    a.set_ylabel(r"eigenvector $\mathbf{u}_i$")
    a.set_title(r"$|\mathbf{u}_i^{\rm T}\mathbf{w}_j|/\|\mathbf{w}_j\|$ at the optimum, $\beta=2.6$", fontsize=9.5)
    fig.colorbar(im, ax=a, fraction=0.046)
    common.panel_label(a, "c", "lower left")
    fig.tight_layout()
    return savefig(fig, CH, "fig19-s8", out)


def export_all(out=None):
    """Write the demo data files ../data/ch19-*.json."""
    export_linear_ae()
    export_vae()


FIGURES = {
    "19.3": fig_19_3, "19.4": fig_19_4, "19.6": fig_19_6, "19.7": fig_19_7, "19.8": fig_19_8, "19.9": fig_19_9,
    "19.S1": fig_19_s1, "19.S2": fig_19_s2, "19.S3": fig_19_s3, "19.S4": fig_19_s4, "19.S5": fig_19_s5,
    "19.S6": fig_19_s6, "19.S7": fig_19_s7, "19.S8": fig_19_s8, "data": export_all,
}

if __name__ == "__main__":
    common.run(FIGURES, CH)
