"""Murphy (2022), Chapter 13: Neural Networks for Tabular Data.

Companion code for Chapter 13 of K. P. Murphy, Probabilistic Machine Learning: An Introduction
(MIT Press, 2022; April 2025 draft), pp. 425-465, written from scratch with numpy, scipy and
matplotlib, to be read next to the lecture notes (../ch13-neural-networks-tabular.html). PyTorch is
used only to confirm the hand-written backpropagation; scikit-learn only to load the digits data.

Methods
* Section 13.2, multilayer perceptrons: the hand-built Heaviside XOR network (13.5)-(13.6), a small
  numpy MLP class (MLP: forward pass (13.7)-(13.9), backpropagation of Section 13.3, optional
  inverted dropout), the activation functions of Table 13.4 with their derivatives (ACTS), the
  heteroskedastic two-head regression network (13.21) trained on its own NLL, and the parameter
  counts of Tables 13.2 and 13.3 (param_count).
* Section 13.3, backpropagation: reverse mode and forward mode on a chain, with the multiply-add
  counts of both (chain_jacobian_forward, chain_jacobian_reverse), the cross-entropy, elementwise and
  linear-layer vector-Jacobian products, the computation graph of (13.56) (graph_value_and_adjoints),
  and the gradients of Exercise 13.1 (exercise_13_1).
* Section 13.4, training: vanishing and exploding signals across depth for several activations and
  initialisations, with and without residual connections (signal_flow), the initialisation variances
  (13.93)-(13.95), the closed-form SELU constants.
* Section 13.5, regularisation: early stopping and weight decay (the gradient-descent filter against
  the ridge filter), l1 regularisation by proximal gradient steps, dropout and Monte Carlo dropout
  (13.96), the modified-loss analysis of gradient descent (13.98)-(13.100), and double descent for
  minimum-norm interpolation (closed form and simulation).
* Section 13.6, other feedforward networks: radial basis function networks (13.101)-(13.104) and a
  mixture of linear experts fitted by EM (13.106)-(13.110).

Data. The two-dimensional data sets of Figure 13.3 and of the demonstrations (circles, XOR, moons,
spirals) are simulated; the digits of Figure 13.4 are MNIST (LeCun et al., 1998) read through
common.mnist (60 000 training images, 10 000 test images); every other data set is simulated with
seeds fixed in the code, because the book's own point sets are not available offline: the captions
say so. All training runs are small enough for a CPU, single-threaded, in seconds to a few minutes.

Figures. Reproduced here: 13.1a, 13.2, 13.3, 13.4, 13.6, 13.7, 13.14, 13.17, 13.20, 13.21, 13.22, 13.23.
Skipped, with the reason:
  13.1b  the hand-weighted XOR network as a drawing (nothing is computed; its weights are tested and
         its decision regions are Figure 13.1a);
  13.5, 13.8, 13.10, 13.11, 13.12, 13.13, 13.15, 13.16, 13.18, 13.24, 13.25  hand-drawn diagrams or
         photographs (the MLP with two heads, two neurons, the chain, the computation graph of (13.56),
         the generic graph node, the weight-decay graph, the residual block, data parallelism,
         dropout, the deep mixture of experts and the hierarchical mixture of experts);
  13.9   the plot of network sizes over the years (a table of historical numbers, nothing computed);
  13.19  flat against sharp minima (a hand-drawn sketch; the idea is computed in Figure 13.20).
Supplementary figures for the gaps filled in the notes:
  13.S1 signal and gradient sizes across 50 layers for several activations and initialisations;
  13.S2 universal approximation by ReLU units in one dimension, and the depth-width gap of the
        sawtooth construction;
  13.S3 gradient descent against the modified loss (13.98): the error against the step size;
  13.S4 double descent of minimum-norm interpolation;
  13.S5 early stopping against ridge regression;
  13.S6 Monte Carlo dropout on a one-dimensional regression problem;
  13.S7 multiply-adds needed for a Jacobian by forward and by reverse mode.
Run `python3 ch13_neural_networks_tabular.py --list`, `python3 ch13_neural_networks_tabular.py` (all
figures, a few minutes) or `python3 ch13_neural_networks_tabular.py --fig 13.4`. Files go to
../img/ch13/; the data used by the browser demonstrations go to ../data/ch13-*.json.
"""
import json
import math
import os
import sys

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

import numpy as np
from scipy import special

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 = 13
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")
sigmoid = common.sigmoid


def softplus(a):
    return np.logaddexp(0.0, a)


# =========================================================================== seeded generator
class Mulberry:
    """The mulberry32 generator with Box-Muller normals, identical to DK.rng in courses/demo-kit.js,
    so that the browser demonstrations and this code start from exactly the same random numbers."""

    def __init__(self, seed):
        self.a = seed & 0xFFFFFFFF
        self.spare = None

    def u(self):
        self.a = (self.a + 0x6D2B79F5) & 0xFFFFFFFF
        a = self.a
        t = ((a ^ (a >> 15)) * (1 | a)) & 0xFFFFFFFF
        t = ((t + (((t ^ (t >> 7)) * (61 | t)) & 0xFFFFFFFF)) & 0xFFFFFFFF) ^ t
        return ((t ^ (t >> 14)) & 0xFFFFFFFF) / 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)


# =========================================================================== activations (Table 13.4)
_SQ2 = math.sqrt(2.0)
SELU_ALPHA = 1.6732632423543772848170429916717
SELU_LAMBDA = 1.0507009873554804934193349852946


def _phi(a):
    return np.exp(-0.5 * a * a) / math.sqrt(2 * math.pi)


def _Phi(a):
    return 0.5 * (1.0 + special.erf(a / _SQ2))


def _act_table(leak=0.1, elu_alpha=1.0, swish_beta=1.0):
    """name -> (f, f') with f' written out by hand (checked against finite differences)."""
    def sig_d(a):
        s = sigmoid(a)
        return s * (1 - s)

    return {
        "identity": (lambda a: a, lambda a: np.ones_like(a)),
        "sigmoid": (sigmoid, sig_d),
        "tanh": (np.tanh, lambda a: 1 - np.tanh(a) ** 2),
        "relu": (lambda a: np.maximum(a, 0.0), lambda a: (a > 0).astype(float)),
        "leaky_relu": (lambda a: np.maximum(a, 0) + leak * np.minimum(a, 0),
                       lambda a: np.where(a > 0, 1.0, leak)),
        "elu": (lambda a: np.where(a > 0, a, elu_alpha * np.expm1(np.minimum(a, 0))),
                lambda a: np.where(a > 0, 1.0, elu_alpha * np.exp(np.minimum(a, 0)))),
        "selu": (lambda a: SELU_LAMBDA * np.where(a > 0, a, SELU_ALPHA * np.expm1(np.minimum(a, 0))),
                 lambda a: SELU_LAMBDA * np.where(a > 0, 1.0, SELU_ALPHA * np.exp(np.minimum(a, 0)))),
        "softplus": (softplus, sigmoid),
        "swish": (lambda a: a * sigmoid(swish_beta * a),
                  lambda a: sigmoid(swish_beta * a) + swish_beta * a * sig_d(swish_beta * a)),
        "gelu": (lambda a: a * _Phi(a), lambda a: _Phi(a) + a * _phi(a)),
        "sin": (np.sin, np.cos),
    }


ACTS = _act_table()


# =========================================================================== a small MLP with backpropagation
class MLP:
    """A fully connected network z_l = phi(W_l z_{l-1} + b_l) (13.7)-(13.9) with a linear last layer.

    W_l has shape (K_l, K_{l-1}) as in the book; data are rows (N, D), so a_l = z_{l-1} W_l^T + b_l.
    backward() is Algorithm 13.3 specialised to the chain: the adjoint u = dL/da is multiplied by W
    (the VJP of a linear layer, (13.50)) and by diag(phi'(a)) (13.43), and the weight gradient is the
    outer product u z^T (13.55).
    """

    def __init__(self, sizes, act="relu", init="auto", seed=0, rng=None):
        self.sizes = list(sizes)
        self.act = act
        self.f, self.df = ACTS[act]
        rng = rng if rng is not None else np.random.default_rng(seed)
        if init == "auto":
            init = "he" if act in ("relu", "leaky_relu", "elu", "swish", "gelu") else "glorot"
        self.W, self.b = [], []
        for nin, nout in zip(sizes[:-1], sizes[1:]):
            self.W.append(rng.normal(size=(nout, nin)) * weight_std(init, nin, nout))
            self.b.append(np.zeros(nout))

    # ---- parameters as one flat list (for optimisers)
    def params(self):
        return [p for pair in zip(self.W, self.b) for p in pair]

    def forward(self, X, drop=0.0, rng=None):
        """Returns the output logits and the cache needed by backward(). drop is the dropout
        probability p applied (inverted, i.e. divided by 1 - p) to every hidden layer."""
        zs, As, masks = [X], [], []
        z = X
        L = len(self.W)
        for l in range(L):
            a = z @ self.W[l].T + self.b[l]
            As.append(a)
            if l < L - 1:
                z = self.f(a)
                if drop > 0:
                    m = (rng.random(z.shape) >= drop) / (1.0 - drop)
                    z = z * m
                    masks.append(m)
                zs.append(z)
            else:
                z = a
        return z, (zs, As, masks)

    def backward(self, cache, dout):
        """Gradients of the loss with respect to all parameters, given dL/d(output). Returns
        grads (same layout as params()) and dL/dX."""
        zs, As, masks = cache
        L = len(self.W)
        gW, gb = [None] * L, [None] * L
        u = dout
        for l in range(L - 1, -1, -1):
            gW[l] = u.T @ zs[l]
            gb[l] = u.sum(0)
            u = u @ self.W[l]
            if l > 0:
                if masks:
                    u = u * masks[l - 1]
                u = u * self.df(As[l - 1])
        grads = [g for pair in zip(gW, gb) for g in pair]
        return grads, u

    def predict(self, X):
        return self.forward(X)[0]


def weight_std(init, nin, nout):
    """Standard deviation of the weights for the initialisation schemes of Section 13.4.5.1."""
    if init == "glorot":
        return math.sqrt(2.0 / (nin + nout))          # (13.95)
    if init == "lecun":
        return math.sqrt(1.0 / nin)
    if init == "he":
        return math.sqrt(2.0 / nin)
    if init == "normal":
        return 1.0
    raise ValueError(init)


def param_count(sizes):
    """Number of weights and biases of a fully connected network, Section 13.2.4 (Tables 13.2 and 13.3)."""
    return sum((a + 1) * b for a, b in zip(sizes[:-1], sizes[1:]))


class Adam:
    """Adam (Kingma and Ba, 2015) with the usual defaults, on a list of arrays updated in place."""

    def __init__(self, params, lr=1e-3, b1=0.9, b2=0.999, eps=1e-8):
        self.p, self.lr, self.b1, self.b2, self.eps = params, lr, b1, b2, eps
        self.m = [np.zeros_like(p) for p in params]
        self.v = [np.zeros_like(p) for p in params]
        self.t = 0

    def step(self, grads):
        self.t += 1
        c1, c2 = 1 - self.b1 ** self.t, 1 - self.b2 ** self.t
        for p, g, m, v in zip(self.p, grads, self.m, self.v):
            m *= self.b1
            m += (1 - self.b1) * g
            v *= self.b2
            v += (1 - self.b2) * g * g
            p -= self.lr * (m / c1) / (np.sqrt(v / c2) + self.eps)


def bce_logits(a, y):
    """Mean binary cross entropy of logits a for labels y in {0,1} and its gradient dL/da (13.39 with C = 2)."""
    a = a.reshape(-1)
    loss = np.mean(softplus(a) - y * a)
    return loss, ((sigmoid(a) - y) / len(y))[:, None]


def softmax_ce(a, Y):
    """Mean cross entropy of logits a (N, C) for one-hot labels Y and its gradient (p - y)/N (13.39)."""
    m = a.max(1, keepdims=True)
    lse = np.log(np.exp(a - m).sum(1, keepdims=True)) + m
    logp = a - lse
    p = np.exp(logp)
    return -(Y * logp).sum(1).mean(), (p - Y) / len(a)


def train_adam(net, X, loss_grad, steps, lr=1e-2, batch=None, seed=0, l2=0.0, drop=0.0, log_every=0):
    """Minibatch (or full-batch) Adam on loss_grad(output, index) -> (loss, dL/doutput)."""
    opt = Adam(net.params(), lr)
    rng = np.random.default_rng(seed)
    N = len(X)
    hist = []
    for t in range(steps):
        idx = np.arange(N) if batch is None else rng.integers(0, N, batch)
        out, cache = net.forward(X[idx], drop=drop, rng=rng)
        loss, dout = loss_grad(out, idx)
        grads, _ = net.backward(cache, dout)
        if l2:
            grads = [g + (l2 * p if i % 2 == 0 else 0.0) for i, (g, p) in enumerate(zip(grads, net.params()))]
        opt.step(grads)
        if log_every and t % log_every == 0:
            hist.append(loss)
    return hist


# =========================================================================== data sets
def make_circles(n=200, noise=0.08, seed=1):
    rng = np.random.default_rng(seed)
    r = np.r_[np.full(n // 2, 0.45), np.full(n - n // 2, 1.0)] + noise * rng.normal(size=n)
    th = rng.uniform(0, 2 * np.pi, n)
    return np.c_[r * np.cos(th), r * np.sin(th)], np.r_[np.zeros(n // 2), np.ones(n - n // 2)]


def make_xor(n=200, noise=0.18, seed=2):
    rng = np.random.default_rng(seed)
    c = rng.integers(0, 2, (n, 2))
    X = (2.0 * c - 1.0) * 0.6 + noise * rng.normal(size=(n, 2))
    return X, (c[:, 0] ^ c[:, 1]).astype(float)


def make_moons(n=200, noise=0.12, seed=3):
    rng = np.random.default_rng(seed)
    h = n // 2
    t1 = rng.uniform(0, np.pi, h)
    t2 = rng.uniform(0, np.pi, n - h)
    A = np.c_[np.cos(t1), np.sin(t1)]
    B = np.c_[1 - np.cos(t2), 0.5 - np.sin(t2)]
    X = np.vstack([A, B]) + noise * rng.normal(size=(n, 2))
    X = (X - np.array([0.5, 0.25])) / 0.9
    return X, np.r_[np.zeros(h), np.ones(n - h)]


def make_spirals(n=200, noise=0.04, seed=4):
    rng = np.random.default_rng(seed)
    h = n // 2
    t = np.sqrt(rng.uniform(0.03, 1.0, h)) * 3.2 * np.pi
    r = t / (3.2 * np.pi) * 1.1
    A = np.c_[r * np.cos(t), r * np.sin(t)]
    X = np.vstack([A, -A]) + noise * rng.normal(size=(2 * h, 2))
    return X, np.r_[np.zeros(h), np.ones(h)]


DATASETS = {"circles": make_circles, "xor": make_xor, "moons": make_moons, "spirals": make_spirals}


def grid2d(lim=1.5, n=121):
    g = np.linspace(-lim, lim, n)
    A, B = np.meshgrid(g, g)
    return g, A, B, np.c_[A.ravel(), B.ravel()]


def prob_cmap():
    from matplotlib.colors import LinearSegmentedColormap
    return LinearSegmentedColormap.from_list("pml", ["#e8761f", "#ffffff", "#2b6cb0"])


# =========================================================================== Figure 13.1: XOR by hand
def heaviside(a):
    return (np.asarray(a) >= 0).astype(float)


def xor_net(X):
    """The hand-weighted MLP of Figure 13.1b: h1 = AND, h2 = OR, y = (NOT h1) AND h2 (13.5)-(13.6)."""
    X = np.atleast_2d(X)
    h1 = heaviside(X @ np.array([1.0, 1.0]) - 1.5)
    h2 = heaviside(X @ np.array([1.0, 1.0]) - 0.5)
    return heaviside(-h1 + h2 - 0.5), h1, h2


def fig_13_1(out=None):
    """Figure 13.1a: XOR is not linearly separable, but two Heaviside layers separate it."""
    g, A, B, G = grid2d(1.3, 261)
    g = np.linspace(-0.2, 1.2, 281)
    A, B = np.meshgrid(g, g)
    G = np.c_[A.ravel(), B.ravel()]
    y = xor_net(G)[0].reshape(A.shape)
    fig, ax = plt.subplots(1, 2, figsize=(6.6, 3.1))
    P = np.array([[0, 0], [0, 1], [1, 0], [1, 1]], float)
    lab = np.array([0, 1, 1, 0])
    for a in ax:
        a.scatter(P[lab == 0, 0], P[lab == 0, 1], marker="o", s=70, c=BLUE, zorder=3)
        a.scatter(P[lab == 1, 0], P[lab == 1, 1], marker="s", s=70, c=RED, zorder=3)
        a.set_xlim(-0.2, 1.2)
        a.set_ylim(-0.2, 1.2)
        a.set_xlabel("$x_1$")
        a.set_aspect("equal")
    ax[0].set_ylabel("$x_2$")
    ax[0].set_title("no single line separates the classes")
    ax[0].plot([-0.2, 1.2], [0.5, 0.5], color=GREY, ls="--", lw=1)
    ax[0].plot([0.5, 0.5], [-0.2, 1.2], color=GREY, ls="--", lw=1)
    ax[1].contourf(A, B, y, levels=[-0.5, 0.5, 1.5], colors=["#cfe0f5", "#f7d3d0"], alpha=0.9)
    xs = np.array([-0.2, 1.2])
    ax[1].plot(xs, 1.5 - xs, color="k", lw=1.2, label="$h_1$: $x_1+x_2=1.5$ (AND)")
    ax[1].plot(xs, 0.5 - xs, color="k", lw=1.2, ls="--", label="$h_2$: $x_1+x_2=0.5$ (OR)")
    ax[1].set_title("two layers of perceptrons")
    ax[1].legend(loc="upper right", fontsize=6.5, framealpha=0.9)
    fig.tight_layout()
    savefig(fig, CH, "fig13-1", out)


# =========================================================================== Figures 13.2 and 13.14: activations
def fig_13_2(out=None):
    """Figure 13.2: the sigmoid saturates; sigmoid, tanh and ReLU."""
    a = np.linspace(-5, 5, 400)
    fig, ax = plt.subplots(1, 2, figsize=(7.0, 2.8))
    ax[0].plot(a, sigmoid(a), color=BLUE)
    ax[0].axvspan(-5, -2.2, color="#f3dcdc", alpha=0.7)
    ax[0].axvspan(2.2, 5, color="#f3dcdc", alpha=0.7)
    ax[0].axvspan(-1.2, 1.2, color="#dce9f6", alpha=0.7)
    ax[0].text(-3.6, 0.42, "saturating", ha="center", fontsize=8)
    ax[0].text(3.6, 0.42, "saturating", ha="center", fontsize=8)
    ax[0].text(0, 0.1, "nearly\nlinear", ha="center", fontsize=8)
    ax[0].set_title("sigmoid activation function")
    ax[0].set_xlabel("$a$")
    for name, c in (("sigmoid", BLUE), ("tanh", RED), ("relu", GREEN)):
        ax[1].plot(a, ACTS[name][0](a), color=c, label={"sigmoid": "sigmoid", "tanh": "tanh", "relu": "ReLU"}[name])
    ax[1].set_ylim(-1.1, 1.1)
    ax[1].set_title("activation functions")
    ax[1].set_xlabel("$a$")
    ax[1].legend()
    fig.tight_layout()
    savefig(fig, CH, "fig13-2", out)


def fig_13_14(out=None):
    """Figure 13.14: the activation functions of Table 13.4 and their derivatives."""
    a = np.linspace(-4, 4, 600)
    names = [("sigmoid", BLUE, "sigmoid"), ("leaky_relu", RED, "leaky ReLU ($\\alpha=0.1$)"), ("elu", GREEN, "ELU"),
             ("swish", ORANGE, "swish"), ("gelu", PURPLE, "GELU")]
    fig, ax = plt.subplots(1, 2, figsize=(7.2, 2.9))
    for n, c, lab in names:
        ax[0].plot(a, ACTS[n][0](a), color=c, label=lab)
        ax[1].plot(a, ACTS[n][1](a), color=c, label=lab)
    ax[0].set_ylim(-1.1, 2.1)
    ax[0].set_title("activation functions")
    ax[1].set_title("gradients of the activation functions")
    ax[1].set_ylim(-0.3, 1.3)
    ax[0].legend(loc="upper left", fontsize=7.5)
    for x in ax:
        x.set_xlabel("$a$")
    fig.tight_layout()
    savefig(fig, CH, "fig13-14", out)


# =========================================================================== Figure 13.3: 2-4-2-1 on two circles
def fit_circles_mlp(seed=0, steps=1500):
    X, y = make_circles(240, 0.07, 11)
    net = MLP([2, 4, 2, 1], act="tanh", seed=seed)
    train_adam(net, X, lambda o, i: bce_logits(o, y[i]), steps, lr=0.03)
    return net, X, y


def hidden_maps(net, G):
    """Activations of every hidden unit and the output probability on the points G."""
    z, maps = G, []
    L = len(net.W)
    for l in range(L - 1):
        z = net.f(z @ net.W[l].T + net.b[l])
        maps.append(z)
    p = sigmoid((z @ net.W[-1].T + net.b[-1]).ravel())
    return maps, p


def fig_13_3(out=None):
    """Figure 13.3: what each hidden unit of a 2-4-2-1 tanh MLP computes on two concentric circles."""
    net, X, y = fit_circles_mlp()
    g, A, B, G = grid2d(1.5, 121)
    maps, p = hidden_maps(net, G)
    cm = prob_cmap()
    fig, ax = plt.subplots(2, 4, figsize=(8.6, 4.6))

    def show(a, Z, title, rng_=(-1, 1)):
        a.imshow(Z.reshape(A.shape), origin="lower", extent=[-1.5, 1.5, -1.5, 1.5], cmap=cm, vmin=rng_[0], vmax=rng_[1])
        a.set_xticks([])
        a.set_yticks([])
        a.set_title(title, fontsize=8.5)
    for k in range(4):
        show(ax[0, k], maps[0][:, k], "layer 1, unit %d" % (k + 1))
    ax[1, 0].scatter(X[y == 0, 0], X[y == 0, 1], s=9, c=ORANGE)
    ax[1, 0].scatter(X[y == 1, 0], X[y == 1, 1], s=9, c=BLUE)
    ax[1, 0].set_xlim(-1.5, 1.5)
    ax[1, 0].set_ylim(-1.5, 1.5)
    ax[1, 0].set_xticks([])
    ax[1, 0].set_yticks([])
    ax[1, 0].set_title("input data", fontsize=8.5)
    for k in range(2):
        show(ax[1, 1 + k], maps[1][:, k], "layer 2, unit %d" % (k + 1))
    show(ax[1, 3], 2 * p - 1, "output $P(y=1\\mid x)$")
    ax[1, 3].scatter(X[y == 0, 0], X[y == 0, 1], s=5, c=ORANGE, edgecolor="k", linewidth=0.2)
    ax[1, 3].scatter(X[y == 1, 0], X[y == 1, 1], s=5, c=BLUE, edgecolor="k", linewidth=0.2)
    ax[1, 3].set_xlim(-1.5, 1.5)
    ax[1, 3].set_ylim(-1.5, 1.5)
    fig.tight_layout()
    savefig(fig, CH, "fig13-3", out)


# =========================================================================== Figure 13.4: MNIST MLP
def mnist_mlp(epochs=2, batch=32, lr=1e-3, seed=0, use_cache=True):
    """784-128-128-10 ReLU network trained with Adam; returns test predictions after each epoch."""
    path = os.path.join(CACHE_DIR, "ch13_mnist_mlp_e%d_b%d.npz" % (epochs, batch))
    if use_cache and os.path.exists(path):
        d = np.load(path)
        return {k: d[k] for k in d.files}
    Xtr, ytr = common.mnist(True)
    Xte, yte = common.mnist(False)
    Ytr = np.eye(10)[ytr]
    net = MLP([784, 128, 128, 10], act="relu", init="glorot", seed=seed)
    opt = Adam(net.params(), lr)
    rng = np.random.default_rng(seed)
    N = len(Xtr)
    res = {}
    for ep in range(epochs):
        perm = rng.permutation(N)
        for s in range(0, N - batch + 1, batch):
            idx = perm[s:s + batch]
            out, cache = net.forward(Xtr[idx])
            _, dout = softmax_ce(out, Ytr[idx])
            grads, _ = net.backward(cache, dout)
            opt.step(grads)
        logits = net.predict(Xte)
        pr = special.softmax(logits, axis=1)
        res["prob%d" % (ep + 1)] = pr[:300].astype(np.float32)
        res["acc%d" % (ep + 1)] = np.array((pr.argmax(1) == yte).mean())
        res["trainacc%d" % (ep + 1)] = np.array((net.predict(Xtr[:10000]).argmax(1) == ytr[:10000]).mean())
    os.makedirs(CACHE_DIR, exist_ok=True)
    np.savez(path, **res)
    return res


def fig_13_4(out=None):
    """Figure 13.4: predictions of the MNIST MLP after one and two epochs (cherry-picked to show errors)."""
    res = mnist_mlp()
    Xte, yte = common.mnist(False)
    err1 = np.where(res["prob1"].argmax(1) != yte[:300])[0]
    ok1 = np.where(res["prob1"].argmax(1) == yte[:300])[0]
    pick = list(err1[:4]) + list(ok1[:6])
    pick = sorted(pick)
    fig, ax = plt.subplots(2, 10, figsize=(9.6, 2.6))
    for r, key in enumerate(("prob1", "prob2")):
        pr = res[key]
        for c, i in enumerate(pick):
            a = ax[r, c]
            a.imshow(Xte[i].reshape(28, 28), cmap="gray_r")
            a.set_xticks([])
            a.set_yticks([])
            k = pr[i].argmax()
            colour = BLUE if k == yte[i] else RED
            a.set_title("%d (%.0f%%)" % (k, 100 * pr[i, k]), fontsize=8, color=colour)
    ax[0, 0].set_ylabel("epoch 1", fontsize=8)
    ax[1, 0].set_ylabel("epoch 2", fontsize=8)
    fig.tight_layout()
    savefig(fig, CH, "fig13-4", out)
    print("  test accuracy after epoch 1: %.4f, after epoch 2: %.4f" % (float(res["acc1"]), float(res["acc2"])))


# =========================================================================== Figure 13.6: heteroskedastic regression
def hetero_data(n=500, seed=5):
    rng = np.random.default_rng(seed)
    x = np.sort(rng.uniform(-20, 60, n))
    mean = 0.06 * x + 0.5 + 1.1 * np.sin(x / 7.0)
    sd = 0.12 + 0.0004 * (x + 20) ** 2
    return x, mean + sd * rng.normal(size=n), mean, sd


def hetero_nll_grad(out, y):
    """NLL of N(y | mu, softplus(s)^2) for output columns (mu, s) and its gradient (13.21)."""
    mu, s = out[:, 0], out[:, 1]
    sig = softplus(s) + 1e-6
    r = y - mu
    nll = np.mean(0.5 * np.log(2 * np.pi * sig ** 2) + 0.5 * r ** 2 / sig ** 2)
    n = len(y)
    d = np.zeros_like(out)
    d[:, 0] = -r / sig ** 2 / n
    d[:, 1] = (1 / sig - r ** 2 / sig ** 3) * sigmoid(s) / n
    return nll, d


def fit_hetero(seed=0, steps=2500):
    x, y, mean, sd = hetero_data()
    xs = (x / 40.0)[:, None]
    net = MLP([1, 32, 32, 2], act="tanh", seed=seed)
    # initialise the variance head near the data scale
    net.b[-1][1] = 0.5
    train_adam(net, xs, lambda o, i: hetero_nll_grad(o, y[i]), steps, lr=5e-3)
    return net, x, y, mean, sd


def fig_13_6(out=None):
    """Figure 13.6: heteroskedastic MLP regression against a fixed-variance model with the same mean."""
    net, x, y, mean, sd = fit_hetero()
    xs = np.linspace(-20, 60, 400)
    o = net.predict((xs / 40.0)[:, None])
    mu, sig = o[:, 0], softplus(o[:, 1])
    mu_tr = net.predict((x / 40.0)[:, None])[:, 0]
    s2 = np.mean((y - mu_tr) ** 2)
    fig, ax = plt.subplots(1, 2, figsize=(8.2, 3.0), sharey=True)
    for a, band, tt in ((ax[0], 2 * sig, "(a) input-dependent variance"), (ax[1], 2 * math.sqrt(s2) * np.ones_like(xs), "(b) fixed variance")):
        a.plot(x, y, ".", color=BLUE, ms=3, alpha=0.6)
        a.plot(xs, mu, color=RED, lw=1.8, label="mean")
        a.plot(xs, mu + band, color=GREEN, lw=1.2, label="mean $\\pm$ 2 sd")
        a.plot(xs, mu - band, color=GREEN, lw=1.2)
        a.set_xlabel("$x$")
        a.set_title(tt, fontsize=9.5)
    ax[0].legend(loc="upper left", fontsize=8)
    fig.tight_layout()
    savefig(fig, CH, "fig13-6", out)
    nll_het = hetero_nll_grad(np.c_[mu_tr, np.log(np.expm1(softplus(net.predict((x / 40.0)[:, None])[:, 1])))], y)[0]
    nll_fix = np.mean(0.5 * np.log(2 * np.pi * s2) + 0.5 * (y - mu_tr) ** 2 / s2)
    print("  mean NLL: input-dependent variance %.3f, fixed variance %.3f (sigma_MLE = %.3f)" % (nll_het, nll_fix, math.sqrt(s2)))


# =========================================================================== Figure 13.7: linear regions of ReLU nets
def relu_net_regions(widths, seed, lim=3.0, n=700, return_pre=False):
    """Random ReLU network on the plane: the pre-activations of every unit on a grid, and the number
    of distinct activation patterns (= linear regions met by the grid)."""
    rng = np.random.default_rng(seed)
    g = np.linspace(-lim, lim, n)
    A, B = np.meshgrid(g, g)
    Z = np.c_[A.ravel(), B.ravel()]
    pres, pats = [], []
    z, nin = Z, 2
    for l, w in enumerate(widths):
        W = rng.normal(size=(w, nin))
        if l == 0:
            P = rng.uniform(-lim * 0.8, lim * 0.8, size=(w, 2))     # each line passes through a point of the window
            b = -(W * P).sum(1)
        else:
            b = rng.normal(size=w) * 0.6
        a = z @ W.T + b
        pres.append(a)
        pats.append(a > 0)
        z = np.maximum(a, 0)
        nin = w
    pat = np.concatenate(pats, 1)
    codes = np.packbits(pat, axis=1)
    nreg = len(np.unique(codes, axis=0))
    return (A, B, pres, nreg) if return_pre else nreg


def fig_13_7(out=None):
    """Figure 13.7: the decomposition of the plane by a random ReLU network with one and with two hidden layers."""
    fig, ax = plt.subplots(1, 2, figsize=(7.2, 3.5))
    counts = []
    for a, widths, title in ((ax[0], [25], "(a) one hidden layer, 25 units"), (ax[1], [10, 10, 10], "(b) three hidden layers of 10 units")):
        A, B, pres, nreg = relu_net_regions(widths, 3 if len(widths) == 1 else 7, return_pre=True)
        counts.append(nreg)
        for l, P in enumerate(pres):
            for k in range(P.shape[1]):
                a.contour(A, B, P[:, k].reshape(A.shape), levels=[0.0], colors=[(BLUE, RED, GREEN)[l]], linewidths=0.8)
        a.set_xlim(-3, 3)
        a.set_ylim(-3, 3)
        a.set_xticks([])
        a.set_yticks([])
        a.set_aspect("equal")
        a.set_title("%s\n%d linear regions" % (title, nreg), fontsize=9)
    fig.tight_layout()
    savefig(fig, CH, "fig13-7", out)
    print("  regions: %s (one layer, 25 units: at most %d)" % (counts, 1 + 25 + 25 * 24 // 2))


# =========================================================================== Figure 13.17: sparse MLP by l1 regularisation
def soft_threshold(w, t):
    """The proximal operator of t ||.||_1, applied elementwise (see gap 13.14)."""
    return np.sign(w) * np.maximum(np.abs(w) - t, 0.0)


def sparse_data(n=150, seed=21):
    rng = np.random.default_rng(seed)
    x = np.sort(rng.uniform(-4.5, 4.5, n))
    f = 2.2 * np.sin(1.8 * x) * np.exp(-x ** 2 / 14.0) + 0.5 * np.cos(0.6 * x)
    return x, f + 0.15 * rng.normal(size=n), f


def fit_sparse_mlp(lam=3e-3, seed=0, warm=3000, steps=20000, lr=0.02):
    """Squared-error fit of a 1-5-5-5-5-1 tanh network with an l1 penalty on the weights (not the biases),
    by plain gradient steps followed by soft thresholding (proximal gradient), so that weights become
    exactly zero."""
    x, y, f = sparse_data()
    X = (x / 4.5)[:, None]
    net = MLP([1, 5, 5, 5, 5, 1], act="tanh", seed=seed)
    mse = lambda o, i: (0.5 * np.mean((o[:, 0] - y[i]) ** 2), ((o[:, 0] - y[i]) / len(y))[:, None])
    train_adam(net, X, mse, warm, lr=0.01)
    for t in range(steps):
        out, cache = net.forward(X)
        _, d = mse(out, np.arange(len(y)))
        grads, _ = net.backward(cache, d)
        for l in range(len(net.W)):
            net.W[l] = soft_threshold(net.W[l] - lr * grads[2 * l], lr * lam)
            net.b[l] = net.b[l] - lr * grads[2 * l + 1]
    return net, x, y, f


def fig_13_17(out=None):
    """Figure 13.17: a deep network pruned by l1 regularisation, and its fit."""
    net, x, y, f = fit_sparse_mlp()
    fig = plt.figure(figsize=(8.6, 3.5))
    ax0 = fig.add_axes([0.02, 0.04, 0.44, 0.9])
    sizes = net.sizes
    pos = {}
    for l, w in enumerate(sizes):
        n_nodes = w + (1 if l < len(sizes) - 1 else 0)          # one clamped bias node per layer
        ys = np.linspace(0.9, 0.1, 6)[:n_nodes] if n_nodes > 1 else [0.5]
        if w == 1 and l == 0:
            ys = [0.7, 0.3]
        if l == len(sizes) - 1:
            ys = [0.5]
        for k in range(n_nodes):
            pos[(l, k)] = (l, ys[k])
    nz = 0
    tot = 0
    for l in range(len(net.W)):
        W, b = net.W[l], net.b[l]
        for j in range(W.shape[0]):
            for i in range(W.shape[1]):
                tot += 1
                if abs(W[j, i]) > 1e-12:
                    nz += 1
                    ax0.plot([pos[(l, i)][0], pos[(l + 1, j)][0]], [pos[(l, i)][1], pos[(l + 1, j)][1]], color="k",
                             lw=0.3 + 1.2 * min(abs(W[j, i]), 3) / 3, alpha=0.7, zorder=1)
            tot += 1
            bi = sizes[l]               # the bias node is the last node of layer l
            if abs(b[j]) > 1e-12:
                nz += 1
                ax0.plot([pos[(l, bi)][0], pos[(l + 1, j)][0]], [pos[(l, bi)][1], pos[(l + 1, j)][1]], color=GREY,
                         lw=0.3 + 1.2 * min(abs(b[j]), 3) / 3, alpha=0.6, ls="--", zorder=1)
    for (l, k), (px, py) in pos.items():
        isbias = (l < len(sizes) - 1 and k == sizes[l])
        ax0.scatter([px], [py], s=130, c=("#ffffff" if isbias else "#fdf3c4"), edgecolors="k", linewidths=0.8, zorder=2)
        if isbias:
            ax0.text(px, py, "1", ha="center", va="center", fontsize=7, zorder=3)
    ax0.set_xlim(-0.3, len(sizes) - 0.7)
    ax0.set_ylim(0.0, 1.0)
    ax0.axis("off")
    ax0.set_title("(a) weights that survive: %d of %d" % (nz, tot), fontsize=9.5)
    ax1 = fig.add_axes([0.56, 0.14, 0.42, 0.74])
    xs = np.linspace(-4.5, 4.5, 300)
    ax1.plot(x, y, "k.", ms=3, label="data")
    ax1.plot(xs, net.predict((xs / 4.5)[:, None])[:, 0], color=GREEN, lw=2, label="sparse network")
    ax1.set_title("(b) predictions on the training set", fontsize=9.5)
    ax1.set_xlabel("$x$")
    ax1.legend(fontsize=8)
    savefig(fig, CH, "fig13-17", out)
    r = np.sqrt(np.mean((net.predict((x / 4.5)[:, None])[:, 0] - y) ** 2))
    print("  nonzero parameters: %d of %d, train RMSE %.3f" % (nz, tot, r))


# =========================================================================== Figure 13.20: SGD and the loss landscape
def minibatch_curves(kind, m=12, seed=0):
    """Loss as a function of one parameter for m minibatches: kind 'stable' (all curves wide, same minimum) or
    'unstable' (every curve a narrow dip at its own minimum, whose average is wide). Returns a list of callables."""
    rng = np.random.default_rng(seed)
    if kind == "stable":
        mins = rng.normal(0, 0.5, m)
        return [(lambda w, mk=mk: 0.28 * (w - mk) ** 2) for mk in mins], mins
    mins = rng.normal(0, 3.0, m)
    return [(lambda w, mk=mk: 28.0 * (1 - np.exp(-(w - mk) ** 2 / 2.0))) for mk in mins], mins


def fig_13_20(out=None):
    """Figure 13.20: minibatch loss curves around a stable and around an unstable minimum."""
    w = np.linspace(-10, 10, 500)
    fig, ax = plt.subplots(1, 2, figsize=(7.6, 2.9), sharey=True)
    stats = []
    for a, kind, ttl in ((ax[0], "stable", "(a) low gradient variance"), (ax[1], "unstable", "(b) high gradient variance")):
        fs, _ = minibatch_curves(kind)
        for f in fs:
            a.plot(w, f(w), color=BLUE, lw=0.8, alpha=0.55)
        mean = np.mean([f(w) for f in fs], 0)
        a.plot(w, mean, color=RED, lw=2.2, label="average over minibatches")
        w0 = w[np.argmin(mean)]
        h = 1e-5
        g = np.array([(f(w0 + h) - f(w0 - h)) / (2 * h) for f in fs])
        stats.append((w0, float(np.var(g)), float(np.mean(g ** 2))))
        a.set_title(ttl, fontsize=9.5)
        a.set_xlabel("parameter $w$")
        a.set_ylim(0, 30)
    ax[0].legend(fontsize=8, loc="upper center")
    fig.tight_layout()
    savefig(fig, CH, "fig13-20", out)
    print("  gradient variance at the minimum of the average: stable %.3g, unstable %.3g" % (stats[0][1], stats[1][1]))


# =========================================================================== Figures 13.21 and 13.22: RBF networks
def rbf_features(X, centres, sigma):
    """phi_k(x) = exp(-||x - mu_k||^2 / (2 sigma^2)) (13.101)-(13.102), one column per centre."""
    X = np.asarray(X, float)
    X = X.reshape(len(X), -1)
    C = np.asarray(centres, float).reshape(len(centres), -1)
    d2 = ((X[:, None, :] - C[None, :, :]) ** 2).sum(-1)
    return np.exp(-d2 / (2 * sigma ** 2))


def logreg_newton(Phi, y, lam=1e-6, iters=60):
    """Ridge-penalised logistic regression by Newton's method (the bias is the first column of Phi)."""
    w = np.zeros(Phi.shape[1])
    R = lam * np.eye(Phi.shape[1])
    R[0, 0] = 0
    for _ in range(iters):
        mu = sigmoid(Phi @ w)
        g = Phi.T @ (mu - y) + R @ w
        H = (Phi * (mu * (1 - mu))[:, None]).T @ Phi + R + 1e-10 * np.eye(len(w))
        step = np.linalg.solve(H, g)
        w = w - step
        if np.linalg.norm(step) < 1e-11:
            break
    return w


def xor_cloud(n=100, jitter=0.12, seed=0):
    rng = np.random.default_rng(seed)
    c = rng.integers(0, 2, (n, 2))
    return c + jitter * rng.normal(size=(n, 2)), (c[:, 0] ^ c[:, 1]).astype(float)


def fig_13_21(out=None):
    """Figure 13.21: XOR with a degree-10 polynomial logistic regression and with an RBF network on four prototypes."""
    from sklearn.linear_model import LogisticRegression
    from sklearn.preprocessing import PolynomialFeatures
    X, y = xor_cloud()
    g = np.linspace(-0.5, 1.5, 201)
    A, B = np.meshgrid(g, g)
    G = np.c_[A.ravel(), B.ravel()]
    pf = PolynomialFeatures(10)
    clf = LogisticRegression(C=1.0, max_iter=100000).fit(pf.fit_transform(X), y)
    pp = clf.predict_proba(pf.transform(G))[:, 1].reshape(A.shape)
    acc_poly = float((clf.predict(pf.transform(X)) == y).mean())
    cent = np.array([[0, 0], [0, 1], [1, 0], [1, 1]], float)
    Phi = np.c_[np.ones(len(X)), rbf_features(X, cent, 0.7)]
    w = logreg_newton(Phi, y, 1e-4)
    pr = sigmoid(np.c_[np.ones(len(G)), rbf_features(G, cent, 0.7)] @ w).reshape(A.shape)
    acc_rbf = float(((Phi @ w > 0) == (y > 0.5)).mean())
    fig, ax = plt.subplots(1, 3, figsize=(9.4, 3.2))
    ax[0].axis("off")
    ax[0].set_title("(a) the XOR truth table", fontsize=9.5)
    cells = [["$x_1$", "$x_2$", "$y$"], ["0", "0", "0"], ["0", "1", "1"], ["1", "0", "1"], ["1", "1", "0"]]
    for r, row in enumerate(cells):
        for c, s in enumerate(row):
            ax[0].text(0.2 + 0.3 * c, 0.85 - 0.12 * r, s, ha="center", va="center", fontsize=12, fontweight="bold" if r == 0 else None, transform=ax[0].transAxes)
    ax[0].plot([0.05, 0.95], [0.79, 0.79], "k", lw=0.8, transform=ax[0].transAxes)
    cm = prob_cmap()
    for a, P, ttl in ((ax[1], pp, "(b) degree-10 polynomial\n(accuracy %.0f%%)" % (100 * acc_poly)),
                      (ax[2], pr, "(c) RBF network, 4 prototypes\n(accuracy %.0f%%)" % (100 * acc_rbf))):
        a.contourf(A, B, P, levels=np.linspace(0, 1, 11), cmap=cm, alpha=0.85)
        a.contour(A, B, P, levels=[0.5], colors="k", linewidths=1.2)
        a.scatter(X[y == 0, 0], X[y == 0, 1], marker="o", s=14, c=ORANGE, edgecolor="k", linewidth=0.3)
        a.scatter(X[y == 1, 0], X[y == 1, 1], marker="s", s=14, c=BLUE, edgecolor="k", linewidth=0.3)
        a.set_title(ttl, fontsize=9.5)
        a.set_xlim(-0.5, 1.5)
        a.set_ylim(-0.5, 1.5)
        a.set_aspect("equal")
        a.set_xlabel("$x_1$")
    ax[2].scatter(cent[:, 0], cent[:, 1], marker="x", s=60, c="k", zorder=5)
    ax[1].set_ylabel("$x_2$")
    fig.subplots_adjust(left=0.02, right=0.99, bottom=0.14, top=0.84, wspace=0.28)
    savefig(fig, CH, "fig13-21", out)
    print("  training accuracy: polynomial %.2f, RBF %.2f" % (acc_poly, acc_rbf))


def rbf_regression_data(n=50, seed=8):
    rng = np.random.default_rng(seed)
    x = np.sort(rng.uniform(0, 20, n))
    f = 0.045 * (x - 4.0) ** 2 - 3.0 + 1.8 * np.sin(x / 1.7) * np.exp(-x / 25)
    return x, f + 1.3 * rng.normal(size=n), f


def rbf_lstsq(x, y, sigma, K=10, lo=0.0, hi=20.0):
    """Least-squares RBF fit with K equally spaced centres plus an intercept, by the minimum-norm solution of
    numpy.linalg.lstsq (tiny singular values are dropped, as in every numerical library)."""
    cent = np.linspace(lo, hi, K)
    Phi = np.c_[np.ones(len(x)), rbf_features(x, cent, sigma)]
    w = np.linalg.lstsq(Phi, y, rcond=None)[0]
    return cent, Phi, w


def fig_13_22(out=None):
    """Figure 13.22: linear regression on 10 RBF basis functions with bandwidth 0.5, 10 and 50."""
    x, y, f = rbf_regression_data()
    xs = np.linspace(0, 20, 400)
    fig, ax = plt.subplots(3, 3, figsize=(7.8, 7.4))
    for r, sg in enumerate((0.5, 10, 50)):
        cent, Phi, w = rbf_lstsq(x, y, sg)
        ax[r, 0].plot(x, y, "o", color=BLUE, ms=3)
        ax[r, 0].plot(xs, np.c_[np.ones(len(xs)), rbf_features(xs, cent, sg)] @ w, color=ORANGE, lw=1.8)
        ax[r, 0].set_ylim(-10, 20)
        ax[r, 0].set_ylabel("$\\sigma=%g$" % sg)
        Phis = rbf_features(xs, cent, sg)
        for k in range(Phis.shape[1]):
            ax[r, 1].plot(xs, Phis[:, k], color=BLUE, lw=0.8)
        ax[r, 2].imshow(Phi[:, 1:], aspect="auto", cmap="viridis")
        ax[r, 2].set_xticks([0, 4, 9])
        ax[r, 2].set_xticklabels([1, 5, 10])
    ax[0, 0].set_title("fitted function", fontsize=9)
    ax[0, 1].set_title("basis functions", fontsize=9)
    ax[0, 2].set_title("design matrix", fontsize=9)
    fig.tight_layout()
    savefig(fig, CH, "fig13-22", out)


# =========================================================================== Figure 13.23: mixture of linear experts
def one_to_many_data(n=300, seed=0):
    """The inverse of a smooth function: y uniform, x = y + 0.3 sin(2 pi y) + noise, so x -> y is multivalued."""
    rng = np.random.default_rng(seed)
    y = rng.uniform(0, 1, n)
    x = y + 0.3 * np.sin(2 * np.pi * y) + rng.uniform(-0.1, 0.1, n)
    return x, y


def moe_gate(X1, V):
    return special.softmax(X1 @ V.T, axis=1)


def fit_moe_em(x, y, K=3, iters=300, seed=0, inner=15):
    """Mixture of K linear experts with a softmax gate (13.106)-(13.110), fitted by EM. E-step: the
    responsibilities r_nk. M-step: weighted least squares for every expert; the gate is fitted to the soft
    labels r_nk by `inner` steps of the bound-optimisation (Bohning) iteration for softmax regression."""
    rng = np.random.default_rng(seed)
    X1 = np.c_[np.ones(len(x)), x]
    N = len(y)
    r = rng.dirichlet(np.ones(K), N)
    V = np.zeros((K, 2))
    Wexp = np.zeros((K, 2))
    s2 = np.ones(K)
    XtX = X1.T @ X1
    for it in range(iters):
        for k in range(K):
            rk = r[:, k]
            A = (X1 * rk[:, None]).T @ X1 + 1e-8 * np.eye(2)
            Wexp[k] = np.linalg.solve(A, (X1 * rk[:, None]).T @ y)
            s2[k] = max((rk * (y - X1 @ Wexp[k]) ** 2).sum() / rk.sum(), 1e-4)
        for _ in range(inner):
            P = moe_gate(X1, V)
            G = (r - P).T @ X1                                  # gradient of the expected complete log-likelihood
            # Bohning bound for K classes (the full, unclamped parametrisation): B = 1/2 (I - 11'/K) kron X'X;
            # it is singular along the shared direction, which a ridge term handles
            Bm = 0.5 * (np.eye(K) - np.ones((K, K)) / K)
            step = np.linalg.solve(np.kron(Bm, XtX) + 1e-6 * np.eye(2 * K), G.reshape(-1)).reshape(K, 2)
            V = V + step
        P = moe_gate(X1, V)
        mu = X1 @ Wexp.T
        lik = P * np.exp(-0.5 * (y[:, None] - mu) ** 2 / s2) / np.sqrt(2 * np.pi * s2)
        ll = np.log(lik.sum(1) + 1e-300).sum()
        r = lik / (lik.sum(1, keepdims=True) + 1e-300)
    return dict(V=V, W=Wexp, s2=s2, ll=ll)


def best_moe(x, y, K=3, restarts=8):
    best = None
    for s in range(restarts):
        m = fit_moe_em(x, y, K, seed=s)
        if best is None or m["ll"] > best["ll"]:
            best = m
    return best


def fig_13_23(out=None):
    """Figure 13.23: a mixture of three linear experts on one-to-many data; the mean prediction and the most-probable-expert prediction."""
    x, y = one_to_many_data()
    m = best_moe(x, y, 3)
    xs = np.linspace(min(x) - 0.05, max(x) + 0.05, 300)
    X1 = np.c_[np.ones(len(xs)), xs]
    P = moe_gate(X1, m["V"])
    mu = X1 @ m["W"].T
    cols = [RED, GREEN, BLUE]
    fig, ax = plt.subplots(1, 4, figsize=(11.0, 2.9))
    ax[0].plot(x, y, "o", color=BLUE, ms=3, mfc="none")
    ax[0].set_title("(a) inverse problem", fontsize=9.5)
    for k in range(3):
        ax[1].plot(xs, P[:, k], color=cols[k], lw=1.8)
        ax[2].plot(xs, mu[:, k], color=cols[k], lw=1.8)
    ax[2].plot(x, y, "o", color="k", ms=2, alpha=0.5)
    ax[1].set_title("(b) gating functions", fontsize=9.5)
    ax[2].set_title("(c) expert predictions", fontsize=9.5)
    ax[3].plot(x, y, "o", color="k", ms=2, alpha=0.4)
    mean = (P * mu).sum(1)
    mode = mu[np.arange(len(xs)), P.argmax(1)]
    ax[3].plot(xs, mean, "x", color=RED, ms=3, label="mean")
    ax[3].plot(xs, mode, "s", color="k", ms=2, label="mode")
    ax[3].legend(fontsize=8)
    ax[3].set_title("(d) prediction", fontsize=9.5)
    for a in ax:
        a.set_xlabel("$x$")
        a.set_ylim(-0.1, 1.1) if a is not ax[1] else a.set_ylim(-0.05, 1.05)
    fig.tight_layout()
    savefig(fig, CH, "fig13-23", out)
    print("  mixture of experts: log-likelihood %.2f, expert slopes %s" % (m["ll"], np.round(m["W"][:, 1], 2)))


# =========================================================================== Section 13.3: autodiff on chains and graphs
def graph_value_and_adjoints(x1, x2):
    """The computation graph of (13.56)-(13.61): f(x1, x2) = x2 e^{x1} sqrt(x1 + x2 e^{x1}).

    Returns the node values x3..x7 and the adjoints o_j = d f / d x_j obtained by reverse mode in reverse
    topological order (13.62)-(13.67); o_1 and o_2 are the two partial derivatives."""
    x3 = math.exp(x1)
    x4 = x2 * x3
    x5 = x1 + x4
    x6 = math.sqrt(x5)
    x7 = x4 * x6
    a7 = 1.0
    a6 = a7 * x4                                  # dx7/dx6 = x4
    a5 = a6 * 0.5 / x6                            # dx6/dx5 = 1/(2 sqrt(x5))
    a4 = a5 * 1.0 + a7 * x6                       # x4 feeds x5 and x7 (13.62)
    a3 = a4 * x2                                  # dx4/dx3 = x2
    a2 = a4 * x3                                  # dx4/dx2 = x3
    a1 = a5 * 1.0 + a3 * x3                       # x1 feeds x3 and x5
    return dict(values=[x1, x2, x3, x4, x5, x6, x7], adjoints=[a1, a2, a3, a4, a5, a6, a7])


def graph_forward_mode(x1, x2, seed):
    """Forward mode on the same graph: tangents t_j = d x_j / d(seed variable), seed = 1 or 2."""
    t1, t2 = (1.0, 0.0) if seed == 1 else (0.0, 1.0)
    x3 = math.exp(x1)
    t3 = x3 * t1
    x4 = x2 * x3
    t4 = t2 * x3 + x2 * t3
    x5 = x1 + x4
    t5 = t1 + t4
    x6 = math.sqrt(x5)
    t6 = 0.5 / x6 * t5
    t7 = t4 * x6 + x4 * t6
    return [t1, t2, t3, t4, t5, t6, t7]


def graph_closed_form_grad(x1, x2):
    """d/dx of f = x2 e^{x1} sqrt(x1 + x2 e^{x1}) written directly."""
    e = math.exp(x1)
    s = math.sqrt(x1 + x2 * e)
    d1 = x2 * e * s + x2 * e * (1 + x2 * e) / (2 * s)
    d2 = e * s + x2 * e * e / (2 * s)
    return d1, d2


def chain_jacobian_forward(Ws, acts, x):
    """Jacobian of a chain f = f_K o ... o f_1, f_k(z) = act(W_k z), by n forward-mode passes (one per input
    direction). Returns the Jacobian and the number of multiply-adds spent on matrix-vector products."""
    n = len(x)
    cost = 0
    cols = []
    for j in range(n):
        z = np.asarray(x, float)
        v = np.zeros(n)
        v[j] = 1.0
        for W, (f, df) in zip(Ws, acts):
            a = W @ z
            cost += W.size
            v = df(a) * (W @ v)
            cost += W.size
            z = f(a)
        cols.append(v)
    return np.array(cols).T, cost


def chain_jacobian_reverse(Ws, acts, x):
    """The same Jacobian by m reverse-mode passes (one per output). Returns it with the multiply-add count
    (one forward pass, then m vector-Jacobian products)."""
    z = np.asarray(x, float)
    As, cost = [], 0
    for W, (f, df) in zip(Ws, acts):
        a = W @ z
        cost += W.size
        As.append(a)
        z = f(a)
    m = len(z)
    rows = []
    for i in range(m):
        u = np.zeros(m)
        u[i] = 1.0
        for W, a, (f, df) in zip(Ws[::-1], As[::-1], acts[::-1]):
            u = (u * df(a)) @ W
            cost += W.size
        rows.append(u)
    return np.array(rows), cost


def exercise_13_1(seed=0, D=5, K=4, C=3):
    """Exercise 13.1: gradients of the one-hidden-layer ReLU classifier by the formulas (13.116)-(13.122), returned
    with the finite-difference gradients for comparison."""
    rng = np.random.default_rng(seed)
    W, b1, U, b2 = rng.normal(size=(K, D)), rng.normal(size=K), rng.normal(size=(C, K)), rng.normal(size=C)
    x = rng.normal(size=D)
    y = np.eye(C)[1]

    def loss(W, b1, U, b2, x):
        a = U @ np.maximum(W @ x + b1, 0) + b2
        return -(y * (a - special.logsumexp(a))).sum()
    z = W @ x + b1
    h = np.maximum(z, 0)
    a = U @ h + b2
    p = special.softmax(a)
    d1 = p - y
    d2 = (U.T @ d1) * (z > 0)
    ana = dict(U=np.outer(d1, h), b2=d1, W=np.outer(d2, x), b1=d2, x=W.T @ d2)

    def fd(idx):
        args = [W, b1, U, b2, x]
        A = args[idx].copy()
        G = np.zeros_like(A)
        for i in np.ndindex(A.shape):
            for s, sgn in ((1e-6, 1), (-1e-6, -1)):
                B = A.copy()
                B[i] += s
                a2 = list(args)
                a2[idx] = B
                G[i] += sgn * loss(*a2) / 2e-6
        return G
    num = dict(W=fd(0), b1=fd(1), U=fd(2), b2=fd(3), x=fd(4))
    return ana, num


# =========================================================================== Section 13.4: signal flow across depth
def signal_flow(L=50, width=64, batch=16, act="relu", c=math.sqrt(2.0), residual=False, beta=1.0, seed=1):
    """Forward and backward signals of a depth-L network z_l = phi(W_l z_{l-1}) (or z_l = z_{l-1} + beta phi(W_l z_{l-1})
    with residual=True), weights N(0, c^2 / width), a batch of standard normal inputs and the objective
    L = (1 / 2B) sum_n ||z_L,n||^2. The random numbers come from the same generator as the browser demonstration.

    Returns the root-mean-square of z_l (l = 0..L), the norm of dL/dz_l (l = 0..L) and the norm of dL/dW_l (l = 1..L)."""
    f, df = ACTS[act]
    rng = Mulberry(seed)
    X = np.array([[rng.norm() for _ in range(width)] for _ in range(batch)])
    Ws = [np.array([[rng.norm() * c / math.sqrt(width) for _ in range(width)] for _ in range(width)]) for _ in range(L)]
    zs, As = [X], []
    z = X
    for W in Ws:
        a = z @ W.T
        As.append(a)
        z = z + beta * f(a) if residual else f(a)
        zs.append(z)
    g = z / batch
    gn, gw = [np.linalg.norm(g)], []
    for l in range(L - 1, -1, -1):
        u = g * df(As[l]) * (beta if residual else 1.0)
        gw.append(np.linalg.norm(u.T @ zs[l]))
        g = u @ Ws[l] + (g if residual else 0.0)
        gn.append(np.linalg.norm(g))
    rms = [float(np.sqrt(np.mean(z_ ** 2))) for z_ in zs]
    return np.array(rms), np.array(gn[::-1]), np.array(gw[::-1])


def fig_13_S1(out=None):
    """Figure 13.S1: signals and gradients across 50 layers for several activations, initialisations and a residual network."""
    L = 50
    cases = [("sigmoid", 1.0, False, 1.0, "sigmoid, $c=1$", BLUE),
             ("tanh", 1.0, False, 1.0, "tanh, $c=1$ (Glorot)", GREEN),
             ("tanh", 2.0, False, 1.0, "tanh, $c=2$", CYAN),
             ("relu", 1.0, False, 1.0, "ReLU, $c=1$", ORANGE),
             ("relu", math.sqrt(2), False, 1.0, "ReLU, $c=\\sqrt{2}$ (He)", RED),
             ("relu", 2.0, False, 1.0, "ReLU, $c=2$", MAGENTA),
             ("relu", math.sqrt(2), True, 0.2, "ReLU, He, residual ($\\beta=0.2$)", PURPLE),
             ("selu", 1.0, False, 1.0, "SELU, $c=1$ (LeCun)", GREY)]
    fig, ax = plt.subplots(1, 2, figsize=(9.4, 3.6))
    for act, c, res, beta, lab, col in cases:
        rms, gn, gw = signal_flow(L, 64, 16, act, c, res, beta)
        ax[0].plot(np.arange(0, L + 1), np.log10(gn / gn[-1] + 1e-300), color=col, lw=1.6, label=lab)
        ax[1].plot(np.arange(0, L + 1), np.log10(rms + 1e-300), color=col, lw=1.6)
    ax[0].set_title("(a) backward signal $\\|\\partial L/\\partial z_l\\|$ relative to the output", fontsize=9.5)
    ax[1].set_title("(b) size of the activations $z_l$ (rms)", fontsize=9.5)
    ax[0].set_ylabel("$\\log_{10}$ of the ratio")
    ax[1].set_ylabel("$\\log_{10}$ rms")
    for a in ax:
        a.set_xlabel("layer $l$ (input at 0, output at %d)" % L)
    ax[0].set_ylim(-35, 12)
    ax[1].set_ylim(-12, 12)
    ax[1].legend(*ax[0].get_legend_handles_labels(), fontsize=6.8, loc="lower left", ncol=1)
    fig.tight_layout()
    savefig(fig, CH, "fig13-S1", out)


# =========================================================================== universal approximation and depth
def relu_interpolant(f, K, lo=0.0, hi=1.0):
    """Shallow ReLU network with K hidden units and a skip of the constant: f(lo) + sum_k c_k relu(x - t_k) is the
    piecewise-linear interpolant of f at the K+1 equally spaced knots; returns (knots, slopes changes, function)."""
    t = np.linspace(lo, hi, K + 1)
    ft = f(t)
    slope = np.diff(ft) / np.diff(t)
    c = np.r_[slope[0], np.diff(slope)]
    ts = t[:-1]

    def net(x):
        x = np.asarray(x, float)
        return ft[0] + (c[None, :] * np.maximum(x[:, None] - ts[None, :], 0)).sum(1)
    return ts, c, net


def tent(x):
    """The tent map on [0, 1] as a two-unit ReLU layer: 2 relu(x) - 4 relu(x - 1/2)."""
    return 2 * np.maximum(x, 0) - 4 * np.maximum(x - 0.5, 0)


def count_linear_pieces(g, lo=0.0, hi=1.0, n=400001):
    x = np.linspace(lo, hi, n)
    y = g(x)
    d = np.diff(y)
    s = np.round(d / (x[1] - x[0]), 6)
    return int(1 + np.count_nonzero(np.abs(np.diff(s)) > 1e-4 * (1 + np.abs(s[:-1]))))


def fig_13_S2(out=None):
    """Figure 13.S2: ReLU interpolants of a smooth function, their error, and the sawtooth of composed tent maps."""
    f = lambda x: np.sin(2 * np.pi * x) + 0.5 * x
    xs = np.linspace(0, 1, 2001)
    fig, ax = plt.subplots(1, 3, figsize=(10.4, 3.0))
    for K, c in ((3, RED), (6, ORANGE), (12, GREEN)):
        _, _, net = relu_interpolant(f, K)
        ax[0].plot(xs, net(xs), color=c, lw=1.3, label="K = %d units" % K)
    ax[0].plot(xs, f(xs), "k", lw=1.0, ls="--", label="target")
    ax[0].legend(fontsize=7, loc="lower left")
    ax[0].set_title("(a) one hidden layer of K ReLUs", fontsize=9.5)
    Ks = np.array([2, 4, 8, 16, 32, 64, 128, 256])
    errs = np.array([np.max(np.abs(relu_interpolant(f, K)[2](xs) - f(xs))) for K in Ks])
    ax[1].loglog(Ks, errs, "o-", color=BLUE, label="sup error")
    ax[1].loglog(Ks, (2 * np.pi) ** 2 / 8 * (1.0 / Ks) ** 2, "k--", lw=1, label="$\\frac{1}{8}\\|f''\\|_\\infty/K^2$")
    ax[1].set_title("(b) the error decays like $K^{-2}$", fontsize=9.5)
    ax[1].set_xlabel("number of hidden units $K$")
    ax[1].legend(fontsize=8)
    g = xs.copy()
    for Lc, c in ((1, RED), (2, ORANGE), (3, GREEN)):
        h = xs.copy()
        for _ in range(Lc):
            h = tent(h)
        ax[2].plot(xs, h + 0.0 * Lc, color=c, lw=1.0, label="depth %d: %d units, %d pieces" % (Lc, 2 * Lc, 2 ** Lc))
    ax[2].legend(fontsize=6.8, loc="upper right")
    ax[2].set_ylim(-0.05, 1.45)
    ax[2].set_title("(c) composing tent maps", fontsize=9.5)
    for a in ax:
        a.set_xlabel(a.get_xlabel() or "$x$")
    fig.tight_layout()
    savefig(fig, CH, "fig13-S2", out)


# =========================================================================== modified loss of gradient descent
def logreg_problem():
    from sklearn.datasets import load_iris
    d = load_iris()
    X = d.data[:, [2, 3]]
    X = (X - X.mean(0)) / X.std(0)
    X = np.c_[np.ones(len(X)), X]
    y = (d.target == 2).astype(float)

    def grad(w):
        return X.T @ (sigmoid(X @ w) - y) / len(y)

    def hess(w):
        mu = sigmoid(X @ w)
        return (X * (mu * (1 - mu))[:, None]).T @ X / len(y)
    return X, y, grad, hess


def rk4(rhs, w0, T, h):
    w = np.array(w0, float)
    for _ in range(int(round(T / h))):
        k1 = rhs(w)
        k2 = rhs(w + 0.5 * h * k1)
        k3 = rhs(w + 0.5 * h * k2)
        k4 = rhs(w + h * k3)
        w = w + h / 6 * (k1 + 2 * k2 + 2 * k3 + k4)
    return w


def gd_vs_flows(eps_list, T=2.0, w0=(0.0, -0.5, 0.5), h=0.002):
    """Gradient descent with step eps for T/eps steps against gradient flow on L and on the modified loss
    L + (eps/4)||grad L||^2 (13.98); returns the two distances for each eps."""
    X, y, grad, hess = logreg_problem()
    w0 = np.array(w0)
    w_flow = rk4(lambda v: -grad(v), w0, T, h)
    e_plain, e_mod = [], []
    for eps in eps_list:
        w = w0.copy()
        for _ in range(int(round(T / eps))):
            w = w - eps * grad(w)
        wm = rk4(lambda v: -(grad(v) + 0.5 * eps * hess(v) @ grad(v)), w0, T, h)
        e_plain.append(np.linalg.norm(w - w_flow))
        e_mod.append(np.linalg.norm(w - wm))
    return np.array(e_plain), np.array(e_mod)


def fig_13_S3(out=None):
    """Figure 13.S3: gradient descent follows the modified loss (13.98) to second order in the step size."""
    eps = np.array([0.4, 0.2, 0.1, 0.05, 0.025, 0.0125])
    e1, e2 = gd_vs_flows(eps)
    fig, ax = plt.subplots(1, 2, figsize=(7.6, 3.0))
    ax[0].loglog(eps, e1, "o-", color=BLUE, label="gradient flow on $L$")
    ax[0].loglog(eps, e2, "s-", color=RED, label="gradient flow on $\\tilde L$")
    ax[0].loglog(eps, 0.5 * e1[-1] / eps[-1] * eps, "k:", lw=1, label="slope 1")
    ax[0].loglog(eps, 0.5 * e2[-1] / eps[-1] ** 2 * eps ** 2, "k--", lw=1, label="slope 2")
    ax[0].set_xlabel("step size $\\epsilon$")
    ax[0].set_ylabel("distance to gradient descent at $t=2$")
    ax[0].legend(fontsize=7.5)
    ax[0].set_title("(a) error against the step size", fontsize=9.5)
    X, y, grad, hess = logreg_problem()
    ev = np.linalg.eigvalsh(hess(np.array([0.0, 0.5, 0.5])))
    nll = lambda w: np.mean(softplus(X @ w) - y * (X @ w))
    w0 = np.array([0.0, -0.5, 0.5])
    for e, c in ((0.4, RED), (0.05, BLUE)):
        w, tr = w0.copy(), []
        for _ in range(int(2.0 / e) + 1):
            tr.append(nll(w))
            w = w - e * grad(w)
        ax[1].plot(np.arange(len(tr)) * e, tr, color=c, lw=1.6, label="gradient descent, $\\epsilon=%g$" % e)
    wf = w0.copy()
    ts, fl = np.linspace(0, 2, 200), []
    for t in ts:
        fl.append(nll(rk4(lambda v: -grad(v), w0, t, 0.002) if t > 0 else w0))
    ax[1].plot(ts, fl, "k--", lw=1.2, label="gradient flow")
    ax[1].set_xlabel("time $t=\\epsilon\\times$ steps")
    ax[1].set_ylabel("training NLL")
    ax[1].legend(fontsize=7.5)
    ax[1].set_title("(b) larger steps lag behind the flow", fontsize=9.5)
    fig.tight_layout()
    savefig(fig, CH, "fig13-S3", out)
    print("  slopes: %.2f and %.2f" % (np.polyfit(np.log(eps), np.log(e1), 1)[0], np.polyfit(np.log(eps), np.log(e2), 1)[0]))


# =========================================================================== double descent
def dd_risk_theory(P, N, D, sigma2, theta_norm2=1.0):
    """Expected test MSE of the least-norm least-squares fit on the first P of D isotropic Gaussian features, when the
    true coefficient vector has equal-size entries and squared norm theta_norm2 (gap 13.17): OLS variance
    sigma_P^2 P/(N-P-1) below the threshold; bias (1-N/P)||theta_S||^2 and variance sigma_P^2 N/(P-N-1) above it."""
    P = np.asarray(P, float)
    tau2 = (1 - P / D) * theta_norm2                  # variance of the omitted features
    sp2 = sigma2 + tau2
    thS2 = P / D * theta_norm2
    out = np.full(P.shape, np.nan)
    lo = P <= N - 2
    hi = P >= N + 2
    out[lo] = sp2[lo] * (1 + P[lo] / (N - P[lo] - 1))
    out[hi] = sp2[hi] + thS2[hi] * (1 - N / P[hi]) + sp2[hi] * N / (P[hi] - N - 1)
    return out


def dd_simulate(P, N, D, sigma2, trials, seed=0, theta_norm2=1.0):
    rng = np.random.default_rng(seed)
    theta = np.ones(D) * math.sqrt(theta_norm2 / D)
    res = []
    for _ in range(trials):
        X = rng.normal(size=(N, D))
        y = X @ theta + math.sqrt(sigma2) * rng.normal(size=N)
        XS = X[:, :P]
        th = np.linalg.pinv(XS) @ y                    # minimum-norm least squares
        d = np.zeros(D)
        d[:P] = th
        res.append(sigma2 + np.sum((d - theta) ** 2))
    return np.mean(res)


def fig_13_S4(out=None):
    """Figure 13.S4: double descent of the least-norm fit as the number of features P passes the sample size N."""
    N, D, s2 = 40, 400, 0.05
    Ps = np.unique(np.r_[np.arange(2, 38, 2), 38, 39, 40, 41, 42, 44, 50, 60, 80, 120, 160, 240, 320, 400])
    th = dd_risk_theory(Ps, N, D, s2)
    sim = np.array([dd_simulate(int(P), N, D, s2, 300, seed=int(P)) for P in Ps])
    fig, ax = plt.subplots(1, 1, figsize=(5.6, 3.2))
    ax.semilogy(Ps, sim, "o", color=BLUE, ms=4, label="simulation (300 data sets)")
    ok = ~np.isnan(th)
    ax.semilogy(Ps[ok & (Ps < N)], th[ok & (Ps < N)], color=RED, lw=1.6, label="closed form (gap 13.17)")
    ax.semilogy(Ps[ok & (Ps > N)], th[ok & (Ps > N)], color=RED, lw=1.6)
    ax.axvline(N, color=GREY, ls=":")
    ax.text(N + 4, ax.get_ylim()[0] * 1.5, "$P=N$", fontsize=8, color=GREY)
    ax.set_ylim(0.5, 1e3)
    ax.set_xlabel("number of features $P$ ($N=40$ training points)")
    ax.set_ylabel("expected test MSE")
    ax.legend(fontsize=8)
    fig.tight_layout()
    savefig(fig, CH, "fig13-S4", out)


# =========================================================================== early stopping against ridge
def early_stopping_problem(seed=5, N=30, D=20, noise=3.0):
    rng = np.random.default_rng(seed)
    scales = 1.0 / np.arange(1, D + 1) ** 0.9
    Q = np.linalg.qr(rng.normal(size=(D, D)))[0]
    mk = lambda n: (rng.normal(size=(n, D)) * scales) @ Q.T
    theta = Q @ (rng.normal(size=D) * 3.0)
    Xtr, Xva = mk(N), mk(2000)
    ytr = Xtr @ theta + noise * rng.normal(size=N)
    yva = Xva @ theta + noise * rng.normal(size=2000)
    return Xtr, ytr, Xva, yva


def gd_path(X, y, eta, T):
    N = len(y)
    w = np.zeros(X.shape[1])
    ws = [w.copy()]
    for _ in range(T):
        w = w - eta * X.T @ (X @ w - y) / N
        ws.append(w.copy())
    return np.array(ws)


def ridge_w(X, y, lam):
    N = len(y)
    return np.linalg.solve(X.T @ X / N + lam * np.eye(X.shape[1]), X.T @ y / N)


def fig_13_S5(out=None):
    """Figure 13.S5: stopping gradient descent at time t is close to ridge regression with penalty 1/(eta t)."""
    Xtr, ytr, Xva, yva = early_stopping_problem()
    eta = 0.05
    T = 4000
    ws = gd_path(Xtr, ytr, eta, T)
    val = np.mean((Xva @ ws.T - yva[:, None]) ** 2, 0)
    ts = np.arange(1, T + 1)
    lam = 1.0 / (eta * ts)
    rval = np.array([np.mean((Xva @ ridge_w(Xtr, ytr, l) - yva) ** 2) for l in lam[::20]])
    tr = np.mean((Xtr @ ws.T - ytr[:, None]) ** 2, 0)
    fig, ax = plt.subplots(1, 2, figsize=(8.0, 3.0))
    ax[0].semilogx(ts, tr[1:], color=BLUE, label="training error (gradient descent)")
    ax[0].semilogx(ts, val[1:], color=RED, label="validation error (gradient descent)")
    ax[0].semilogx(ts[::20], rval, "k.", ms=3, label="ridge with $\\lambda=1/(\\eta t)$")
    k = int(np.argmin(val[1:]))
    ax[0].axvline(ts[k], color=GREY, ls=":")
    ax[0].set_xlabel("iteration $t$")
    ax[0].set_ylabel("mean squared error")
    ax[0].legend(fontsize=7)
    ax[0].set_title("(a) early stopping at $t=%d$" % ts[k], fontsize=9.5)
    s = np.linspace(0.001, 1.5, 300)
    for t_, c in ((10, BLUE), (100, GREEN), (1000, RED)):
        ax[1].plot(s, 1 - (1 - eta * s) ** t_, color=c, label="GD, $t=%d$" % t_)
        ax[1].plot(s, s / (s + 1 / (eta * t_)), color=c, ls="--")
    ax[1].set_xlabel("eigenvalue $s$ of $X^\\top X/N$")
    ax[1].set_ylabel("shrinkage factor")
    ax[1].legend(fontsize=7.5)
    ax[1].set_title("(b) filters: GD (solid), ridge (dashed)", fontsize=9.5)
    fig.tight_layout()
    savefig(fig, CH, "fig13-S5", out)


# =========================================================================== Monte Carlo dropout
def mc_dropout_fit(p=0.1, seed=0, steps=5000):
    rng = np.random.default_rng(1)
    x = np.r_[rng.uniform(-3, -1, 25), rng.uniform(1, 3, 25)]
    y = np.sin(1.4 * x) + 0.15 * rng.normal(size=50)
    net = MLP([1, 64, 64, 1], act="tanh", seed=seed)
    mse = lambda o, i: (0.5 * np.mean((o[:, 0] - y[i]) ** 2), ((o[:, 0] - y[i]) / len(y))[:, None])
    train_adam(net, (x / 3)[:, None], mse, steps, lr=3e-3, drop=p, seed=seed)
    return net, x, y


def mc_dropout_predict(net, xs, p, S=300, seed=3):
    rng = np.random.default_rng(seed)
    X = (xs / 3)[:, None]
    draws = np.array([net.forward(X, drop=p, rng=rng)[0][:, 0] for _ in range(S)])
    return net.predict(X)[:, 0], draws


def fig_13_S6(out=None):
    """Figure 13.S6: Monte Carlo dropout (13.96) on a regression problem with a gap in the data."""
    fig, ax = plt.subplots(1, 2, figsize=(8.2, 3.0), sharey=True)
    xs = np.linspace(-4, 4, 300)
    for a, p in zip(ax, (0.05, 0.2)):
        net, x, y = mc_dropout_fit(p)
        det, draws = mc_dropout_predict(net, xs, p)
        m, s = draws.mean(0), draws.std(0)
        a.plot(x, y, "k.", ms=4, zorder=4)
        a.plot(xs, det, color=BLUE, lw=1.4, label="weights scaled (test-time rule)")
        a.plot(xs, m, color=RED, lw=1.4, label="MC dropout mean")
        a.fill_between(xs, m - 2 * s, m + 2 * s, color=RED, alpha=0.2, label="$\\pm2$ sd, $S=300$")
        a.set_title("dropout probability $p=%g$" % p, fontsize=9.5)
        a.set_xlabel("$x$")
    ax[0].legend(fontsize=7, loc="lower right")
    fig.tight_layout()
    savefig(fig, CH, "fig13-S6", out)


# =========================================================================== cost of forward and reverse mode
def fig_13_S7(out=None):
    """Figure 13.S7: multiply-adds needed for the whole Jacobian of a 4-layer chain by forward and by reverse mode."""
    rng = np.random.default_rng(0)
    ns = np.array([4, 8, 16, 32, 64])
    res = {}
    for m_out in ("scalar", "square"):
        cf, cr = [], []
        for n in ns:
            m = 1 if m_out == "scalar" else n
            Ws = [rng.normal(size=(n, n)) / math.sqrt(n) for _ in range(3)] + [rng.normal(size=(m, n)) / math.sqrt(n)]
            acts = [ACTS["tanh"]] * 4
            x = rng.normal(size=n)
            Jf, c1 = chain_jacobian_forward(Ws, acts, x)
            Jr, c2 = chain_jacobian_reverse(Ws, acts, x)
            assert np.allclose(Jf, Jr, atol=1e-10)
            cf.append(c1)
            cr.append(c2)
        res[m_out] = (np.array(cf), np.array(cr))
    fig, ax = plt.subplots(1, 2, figsize=(7.6, 3.0))
    for a, key, ttl in ((ax[0], "scalar", "(a) scalar output ($m=1$)"), (ax[1], "square", "(b) as many outputs as inputs ($m=n$)")):
        cf, cr = res[key]
        a.loglog(ns, cf, "o-", color=RED, label="forward mode, $n$ passes (slope %.1f)" % np.polyfit(np.log(ns), np.log(cf), 1)[0])
        a.loglog(ns, cr, "s-", color=BLUE, label="reverse mode, $m$ passes (slope %.1f)" % np.polyfit(np.log(ns), np.log(cr), 1)[0])
        a.set_xlabel("width $n$")
        a.set_ylabel("multiply-adds")
        a.legend(fontsize=7.5)
        a.set_title(ttl, fontsize=9.5)
    fig.tight_layout()
    savefig(fig, CH, "fig13-S7", out)


# =========================================================================== mirrors of the browser demonstrations
def playground_init(sizes, act, seed):
    """Weights N(0, 2/n_in) for ReLU and N(0, 2/(n_in+n_out)) otherwise, zero biases, drawn row by row (output
    unit by output unit) from the mulberry32 generator, exactly as in mlp-playground-demo.html."""
    rng = Mulberry(seed)
    net = MLP(sizes, act=act, seed=0)
    for l, (nin, nout) in enumerate(zip(sizes[:-1], sizes[1:])):
        std = math.sqrt(2.0 / nin) if act == "relu" else math.sqrt(2.0 / (nin + nout))
        net.W[l] = np.array([[rng.norm() * std for _ in range(nin)] for _ in range(nout)])
        net.b[l] = np.zeros(nout)
    return net


def playground_run(X, y, hidden, act, opt, lr, l2, steps, seed=1):
    """Full-batch training of the playground network: mean cross entropy plus (l2/2) sum of squared weights,
    plain gradient descent (opt='gd') or Adam (opt='adam'). Returns the net and the data loss after 0, 1, ... steps."""
    net = playground_init([2] + list(hidden) + [1], act, seed)
    adam = Adam(net.params(), lr) if opt == "adam" else None
    hist = []
    for t in range(steps + 1):
        out, cache = net.forward(X)
        loss, d = bce_logits(out, y)
        hist.append(loss)
        if t == steps:
            break
        grads, _ = net.backward(cache, d)
        grads = [g + (l2 * p if i % 2 == 0 else 0.0) for i, (g, p) in enumerate(zip(grads, net.params()))]
        if adam:
            adam.step(grads)
        else:
            for p_, g in zip(net.params(), grads):
                p_ -= lr * g
    return net, np.array(hist)


def rbf_ridge(x, y, sigma, K, lam, lo=0.0, hi=20.0):
    """Ridge-penalised RBF regression with K equally spaced centres and an unpenalised intercept (rbf-network-demo.html)."""
    cent = np.linspace(lo, hi, K) if K > 1 else np.array([(lo + hi) / 2])
    Phi = np.c_[np.ones(len(x)), rbf_features(x, cent, sigma)]
    R = lam * np.eye(Phi.shape[1])
    R[0, 0] = 0
    w = np.linalg.solve(Phi.T @ Phi + R, Phi.T @ y)
    return cent, w


# =========================================================================== exports for the browser demonstrations
def export_json():
    os.makedirs(DATA_OUT, exist_ok=True)
    r4 = lambda a: np.round(np.asarray(a, float), 4).tolist()
    d1 = {}
    for name, fn in DATASETS.items():
        X, y = fn()
        d1[name] = dict(X=r4(X), y=[int(v) for v in y])
    with open(os.path.join(DATA_OUT, "ch13-datasets.json"), "w") as f:
        json.dump(d1, f, separators=(",", ":"))
    x, y, f_ = rbf_regression_data()
    Xc, yc = xor_cloud()
    d2 = dict(reg=dict(x=r4(x), y=r4(y)), xor=dict(X=r4(Xc), y=[int(v) for v in yc]))
    with open(os.path.join(DATA_OUT, "ch13-rbf.json"), "w") as f:
        json.dump(d2, f, separators=(",", ":"))
    print("wrote ch13-*.json")


FIGURES = {"13.1": fig_13_1, "13.2": fig_13_2, "13.3": fig_13_3, "13.4": fig_13_4, "13.6": fig_13_6, "13.7": fig_13_7,
           "13.14": fig_13_14, "13.17": fig_13_17, "13.20": fig_13_20, "13.21": fig_13_21, "13.22": fig_13_22,
           "13.23": fig_13_23, "13.S1": fig_13_S1, "13.S2": fig_13_S2, "13.S3": fig_13_S3, "13.S4": fig_13_S4,
           "13.S5": fig_13_S5, "13.S6": fig_13_S6, "13.S7": fig_13_S7}


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