"""Bishop and Bishop (2024), Chapter 9: Regularization.

Reproduces the figures of Chapter 9 of C. M. Bishop and H. Bishop, Deep Learning: Foundations and
Concepts (Springer, 2024), pp. 253-285, written from scratch with numpy, scipy (image transformations
and a constrained minimiser), PyTorch (autograd only, for the deep networks of Figure 9.14) and
matplotlib, and supplies the reference numbers of the three browser demonstrations. Every model is a
short function meant to be read next to the lecture notes (ch09-regularization.html):

* Section 9.1, inductive bias: augment() applies the eight transformations of Figure 9.1 to an MNIST
  digit; segment() and shift() are a translation-equivariant 'segmentation' and a cyclic translation
  (Figure 9.2, equation (9.2)).
* Section 9.2, weight decay: the quadratic error and its weight-decay minimiser in closed form
  (ridge_eigen), prior draws of a 12-unit tanh network (prior_functions, Figure 9.4), the L_q penalty
  and the constrained minimiser in two dimensions (lq_constrained_2d, Figures 9.5, 9.6), and, for the
  regularisation paths, ridge() and the lasso by cyclic coordinate descent (lasso_cd).
* Section 9.3, learning curves: sine_data / net_init / train_net train a one-input tanh network by
  full-batch gradient descent with an optional weight-decay term (Figure 9.7); gd_filter and
  ridge_filter are the eigen-direction filters of early stopping and weight decay (Exercise 9.6,
  Figure 9.8); random_features_dd computes test and training error of minimum-norm least squares on
  random ReLU features of MNIST against the number of features (Figure 9.9); two_speed_risk is a linear
  model whose features learn at two speeds (Figure 9.10); gauss_dd_theory is the exact expected risk of
  minimum-norm least squares with an isotropic Gaussian design (Figure 9.11).
* Section 9.4, soft weight sharing: sws_omega and sws_grads give the mixture-of-Gaussians regulariser
  (9.22) and its derivatives (9.25), (9.26), (9.28), (9.31).
* Section 9.5, residual connections: input_gradient computes dy/dx of deep ReLU networks with and
  without residual connections (Figure 9.12); loss_surface trains deep plain and residual networks and
  evaluates the loss on a filter-normalised random plane through the trained weights (Figure 9.14).
* Section 9.6, model averaging and dropout: train_adam trains a one-input tanh network with Adam,
  optionally on a bootstrap sample or with dropout masks on the hidden units; ensemble_run and
  dropout_run are the two modes of the dropout-and-ensembles demo; linear_dropout_objective is the
  expected dropout error of a linear model (Exercise 9.18) and linear_dropout_solution its minimiser.
* JSRandom: the seeded generator DK.rng of the browser demos (mulberry32 uniforms and Box-Muller
  normals). The demo functions (lasso_data, lasso_cd, ridge, sine_data, net_init, train_net,
  train_adam, ensemble_run, dropout_run) use only that generator and plain floating-point arithmetic,
  so l1-l2-paths-demo.html, early-stopping-demo.html and dropout-ensemble-demo.html reproduce them.

Figures reproduced (13): 9.1, 9.2, 9.3, 9.4, 9.5, 9.6, 9.7, 9.8, 9.9, 9.10, 9.11, 9.12 and 9.14.
* 9.1 is a photograph of a cat in the book; here the same eight augmentations are applied to an MNIST
  digit (colour shift: the grey digit is drawn in colour and its colour balance changed).
* 9.2 is a schematic; here the image is a digit on a textured background and the segmentation is an
  actual translation-equivariant map (smoothing by a cyclic convolution followed by a threshold).
* 9.9, 9.10 and 9.11 are reprinted in the book from Nakkiran et al. (2019) (ResNet18 and transformer
  experiments). We reproduce the phenomena at small scale: 9.9 with minimum-norm least squares on random
  ReLU features of 300 MNIST digits (a two-layer network whose first layer is fixed); 9.10 with gradient
  descent on linear models whose features learn at two different speeds (the mechanism proposed by
  Heckel and Yilmaz, 2021), using three model sizes as in the book; 9.11 with the exact risk formula of
  minimum-norm least squares for two training-set sizes.
* 9.12 is reprinted from Balduzzi et al. (2017); here it is recomputed for randomly initialised ReLU
  networks with batch normalisation (2 and 25 layers of weights, and 51 layers with residual
  connections), width 200, on 256 inputs in [-2, 2] as in that paper.
* 9.14 is reprinted from Li et al. (2017) (56-layer image networks); here a 30-layer plain network and a
  30-layer network with 14 two-layer residual blocks are trained on a two-dimensional three-class spiral and
  the loss is drawn over a filter-normalised random plane through each trained weight vector.
Figures skipped: 9.13, 9.15 and 9.16 (diagrams of residual blocks) and 9.17 (a diagram of a network and
two of its pruned sub-networks); they are hand-drawn schematics with no data. Equation (9.40) is what
Figure 9.15 depicts.

Supplementary figures (our own, numbered 9.S1-9.S4; they illustrate the gaps filled in the notes):
9.S1 lasso and ridge regularisation paths and validation error (the demo's data);
9.S2 early stopping against weight decay: the two eigen-direction filters and the matched paths;
9.S3 ensembles: committee error against the number of members, with the correlation formula;
9.S4 dropout: the expected dropout error of a linear model against Monte Carlo, and weight scaling
     against Monte Carlo dropout for a trained network.

Run `python3 ch09_regularization.py --list`, `python3 ch09_regularization.py` (all figures, about two
minutes on one CPU thread) or `python3 ch09_regularization.py --fig 9.7 9.S1`.
Files go to ../img/ch09/; the slower results (Figures 9.9, 9.14, 9.S3 and 9.S4) are cached in cache/.
The browser demos generate their data from the seeded generator, so no JSON export is needed.
"""
import math
import os

for _v in ("OPENBLAS_NUM_THREADS", "MKL_NUM_THREADS", "OMP_NUM_THREADS"):
    os.environ.setdefault(_v, "1")

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

import common  # noqa: E402
from common import savefig, run  # noqa: E402

HERE = os.path.dirname(os.path.abspath(__file__))
CACHE_DIR = os.path.join(HERE, "cache")
CH = 9
M32 = 0xFFFFFFFF


# =========================================================================== the demos' generator
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)


# =========================================================================== Section 9.1
def digit(index=0, label=4):
    """A 28 x 28 MNIST training digit (the index-th example of the given label)."""
    X, y = common.mnist(train=True)
    return X[np.where(y == label)[0][index]].reshape(28, 28)


def augment(img, rng):
    """The eight panels of Figure 9.1 for a grey image in [0, 1]: a list of (name, RGB image)."""
    from scipy import ndimage
    pad = np.pad(img, 6)
    H = pad.shape[0]

    def rgb(g, tint=(1.0, 1.0, 1.0)):
        g = np.clip(g, 0, 1)
        base = np.stack([1 - g * (1 - 0.15), 1 - g * (1 - 0.25), 1 - g * (1 - 0.55)], -1)  # dark blue ink on white
        return np.clip(base * np.array(tint), 0, 1)

    def zoom(g, s):
        z = ndimage.zoom(g, s, order=1)
        c = (z.shape[0] - H) // 2
        if s >= 1:
            return z[c:c + H, c:c + H]
        out = np.zeros_like(g)
        o = (H - z.shape[0]) // 2
        out[o:o + z.shape[0], o:o + z.shape[1]] = z
        return out

    out = [("original", rgb(pad)),
           ("horizontal flip", rgb(pad[:, ::-1])),
           ("scaling", rgb(zoom(pad, 1.3))),
           ("translation", rgb(ndimage.shift(pad, (4, -5), order=1))),
           ("rotation", rgb(ndimage.rotate(pad, 30, reshape=False, order=1))),
           ("brightness and contrast", rgb(0.55 * pad + 0.25)),
           ("additive noise", rgb(pad + 0.25 * rng.standard_normal(pad.shape))),
           ("colour shift", rgb(pad, tint=(1.0, 0.82, 0.55)))]
    return out


def shift(img, dy, dx):
    """Cyclic translation T of an image (np.roll), the group action of Figure 9.2."""
    return np.roll(np.roll(img, dy, axis=0), dx, axis=1)


def segment(img, thr=0.35):
    """A translation-equivariant 'segmentation' S: 3 x 3 cyclic box smoothing, then a threshold."""
    sm = sum(shift(img, a, b) for a in (-1, 0, 1) for b in (-1, 0, 1)) / 9.0
    return (sm > thr).astype(float)


def equivariance_scene(seed=3):
    """A digit pasted on a smoothly textured background (48 x 48), for Figure 9.2."""
    rng = np.random.default_rng(seed)
    yy, xx = np.mgrid[0:48, 0:48]
    bg = 0.12 + 0.08 * np.sin(xx / 4.0) * np.cos(yy / 5.0) + 0.03 * rng.standard_normal((48, 48))
    img = bg.copy()
    d = digit(3, 2)
    img[6:34, 4:32] = np.maximum(img[6:34, 4:32], d)
    return np.clip(img, 0, 1)


def fig_9_1(out_dir=None):
    """Figure 9.1: data augmentation (flip, scale, translate, rotate, brightness/contrast, noise, colour)."""
    rng = np.random.default_rng(0)
    panels = augment(digit(0, 4), rng)
    fig, axes = plt.subplots(2, 4, figsize=(8.0, 4.3))
    for k, (ax, (name, im)) in enumerate(zip(axes.ravel(), panels)):
        ax.imshow(im, interpolation="nearest")
        ax.set_xticks([])
        ax.set_yticks([])
        ax.set_title("(%s) %s" % ("abcdefgh"[k], name), fontsize=9.5)
    fig.tight_layout()
    return savefig(fig, CH, "fig9-1", out_dir)


def fig_9_2(out_dir=None):
    """Figure 9.2: equivariance S(T(I)) = T(S(I)) for a translation T and a segmentation S."""
    I = equivariance_scene()
    TI = shift(I, 9, 12)
    SI = segment(I)
    STI = segment(TI)
    TSI = shift(SI, 9, 12)
    assert np.array_equal(STI, TSI)
    fig, axes = plt.subplots(2, 2, figsize=(5.4, 5.6))
    items = [(axes[0, 0], I, "(a) image I", "gray_r"), (axes[0, 1], TI, "(b) T(I)", "gray_r"),
             (axes[1, 0], SI, "(c) S(I)", "Blues"), (axes[1, 1], STI, "(d) S(T(I)) = T(S(I))", "Blues")]
    for ax, im, title, cmap in items:
        ax.imshow(im, cmap=cmap, vmin=0, vmax=1, interpolation="nearest")
        ax.set_xticks([])
        ax.set_yticks([])
        ax.set_title(title, fontsize=10)
    fig.tight_layout(h_pad=2.6, w_pad=2.6)
    kw = dict(arrowstyle="-|>", color=common.RED, lw=1.6, mutation_scale=14)
    from matplotlib.patches import FancyArrowPatch
    for (a, b, lab) in [((0.49, 0.75), (0.53, 0.75), "T"), ((0.49, 0.27), (0.53, 0.27), "T"),
                        ((0.27, 0.52), (0.27, 0.48), "S"), ((0.77, 0.52), (0.77, 0.48), "S")]:
        fig.patches.append(FancyArrowPatch(a, b, transform=fig.transFigure, **kw))
        fig.text((a[0] + b[0]) / 2 + (0.0 if lab == "T" else 0.025), (a[1] + b[1]) / 2 + (0.02 if lab == "T" else 0.0),
                 lab, color=common.RED, ha="center", va="center", fontsize=11, fontweight="bold")
    return savefig(fig, CH, "fig9-2", out_dir)


# =========================================================================== Section 9.2: weight decay
def ridge_eigen(wstar, eig, lam):
    """Minimiser of E0 + (w - w*)^T H (w - w*)/2 + lam w^T w / 2 when H = diag(eig): w_j = eig_j/(eig_j + lam) w*_j."""
    eig = np.asarray(eig, float)
    return eig / (eig + lam) * np.asarray(wstar, float)


def fig_9_3(out_dir=None):
    """Figure 9.3: contours of a quadratic error, of the weight-decay term and of their sum."""
    eig = np.array([0.12, 1.0])
    ws = np.array([1.55, 1.05])
    lam = 0.25
    what = ridge_eigen(ws, eig, lam)
    g = np.linspace(-0.6, 2.6, 400)
    W1, W2 = np.meshgrid(g, np.linspace(-0.9, 1.9, 400))
    E = 0.5 * (eig[0] * (W1 - ws[0]) ** 2 + eig[1] * (W2 - ws[1]) ** 2)
    R = 0.5 * lam * (W1 ** 2 + W2 ** 2)
    fig, ax = plt.subplots(figsize=(4.9, 4.1))
    ax.contour(W1, W2, E, levels=[0.02, 0.06, 0.12, 0.2], colors=common.RED, linewidths=1.2)
    ax.contour(W1, W2, R, levels=[0.02, 0.06, 0.12], colors=common.GREEN, linewidths=1.2)
    tot = E + R
    m = tot.min()
    ax.contour(W1, W2, tot, levels=[m + 0.012, m + 0.04, m + 0.09], colors=common.BLUE, linewidths=1.4)
    ax.plot(*ws, "o", color=common.RED, ms=5)
    ax.plot(*what, "o", color=common.BLUE, ms=5)
    ax.annotate(r"$\mathbf{w}^\star$", ws, xytext=(6, 4), textcoords="offset points", color=common.RED)
    ax.annotate(r"$\widehat{\mathbf{w}}$", what, xytext=(-14, 6), textcoords="offset points", color=common.BLUE)
    ax.axhline(0, color="k", lw=0.6)
    ax.axvline(0, color="k", lw=0.6)
    ax.set_xlabel(r"$w_1$ (small curvature, $\lambda_1=%.2f$)" % eig[0])
    ax.set_ylabel(r"$w_2$ (large curvature, $\lambda_2=%.0f$)" % eig[1])
    ax.plot([], [], color=common.RED, label=r"$E(\mathbf{w})$")
    ax.plot([], [], color=common.GREEN, label=r"$\frac{\lambda}{2}(w_1^2+w_2^2)$")
    ax.plot([], [], color=common.BLUE, label="sum")
    ax.legend(loc="lower right", fontsize=8.5)
    ax.set_aspect("equal")
    ax.set_xlim(-0.6, 2.6)
    ax.set_ylim(-0.9, 1.9)
    fig.tight_layout()
    return savefig(fig, CH, "fig9-3", out_dir)


def prior_functions(sd1w, sd1b, sd2w, sd2b, n_draws=5, H=12, seed=11, xs=None):
    """Functions y(x) = sum_j v_j tanh(w_j x + b_j) + c drawn from a Gaussian prior with the given
    standard deviations (first-layer weights, first-layer biases, second-layer weights, second-layer bias)."""
    xs = np.linspace(-1, 1, 400) if xs is None else xs
    rng = np.random.default_rng(seed)
    out = []
    for _ in range(n_draws):
        w = sd1w * rng.standard_normal(H)
        b = sd1b * rng.standard_normal(H)
        v = sd2w * rng.standard_normal(H)
        c = sd2b * rng.standard_normal()
        out.append(np.tanh(np.outer(xs, w) + b) @ v + c)
    return xs, np.array(out)


def fig_9_4(out_dir=None):
    """Figure 9.4: functions drawn from the prior of a 12-unit tanh network, four hyperparameter settings."""
    # The book's panel labels are read as prior standard deviations (precision = label^-2); see the notes.
    panels = [(1, 1, 1, 1), (1, 1, 10, 1), (1000, 100, 1, 1), (1000, 1000, 1, 1)]
    cols = [common.RED, common.GREEN, common.BLUE, "#b5a000", common.MAGENTA]
    fig, axes = common.panel_grid(2, 2, size=(3.7, 2.7))
    for (s1w, s1b, s2w, s2b), ax in zip(panels, axes.ravel()):
        xs, F = prior_functions(s1w, s1b, s2w, s2b)
        for f, c in zip(F, cols):
            ax.plot(xs, f, color=c, lw=1.4)
        ax.set_xlim(-1, 1)
        ax.set_title(r"$\sigma_1^w=%g,\ \sigma_1^b=%g,\ \sigma_2^w=%g,\ \sigma_2^b=%g$" % (s1w, s1b, s2w, s2b), fontsize=8.8)
    fig.tight_layout()
    return savefig(fig, CH, "fig9-4", out_dir)


def lq_norm(w, q):
    return np.sum(np.abs(w) ** q, axis=-1)


def fig_9_5(out_dir=None):
    """Figure 9.5: contours of the regulariser sum_j |w_j|^q for q = 0.5, 1, 2, 4."""
    g = np.linspace(-1.6, 1.6, 501)
    W1, W2 = np.meshgrid(g, g)
    fig, axes = plt.subplots(1, 4, figsize=(9.4, 2.6))
    for ax, q in zip(axes, (0.5, 1, 2, 4)):
        Z = np.abs(W1) ** q + np.abs(W2) ** q
        ax.contour(W1, W2, Z, levels=[0.25, 0.5, 1.0, 1.5], colors=common.GREEN, linewidths=1.2)
        ax.contour(W1, W2, Z, levels=[1.0], colors=common.GREEN, linewidths=2.2)
        ax.axhline(0, color="k", lw=0.5)
        ax.axvline(0, color="k", lw=0.5)
        ax.set_aspect("equal")
        ax.set_xticks([])
        ax.set_yticks([])
        ax.set_title("q = %g" % q)
        ax.set_xlabel(r"$w_1$")
        ax.set_ylabel(r"$w_2$")
    fig.tight_layout()
    return savefig(fig, CH, "fig9-5", out_dir)


def lq_constrained_2d(wstar, Hm, q, eta, n=20000):
    """Minimise (w - w*)^T H (w - w*)/2 subject to |w1|^q + |w2|^q <= eta (two dimensions).

    If w* is feasible it is the answer; otherwise the minimum is on the boundary, which is searched
    densely (parametrised by angle) and then refined by golden-section search. Works for any q > 0.
    Returns the minimiser."""
    wstar = np.asarray(wstar, float)
    if np.sum(np.abs(wstar) ** q) <= eta:
        return wstar.copy()

    def bpt(th):
        c, s = math.cos(th), math.sin(th)
        r = (eta / (abs(c) ** q + abs(s) ** q)) ** (1.0 / q)
        return np.array([r * c, r * s])

    def E(th):
        d = bpt(th) - wstar
        return 0.5 * d @ Hm @ d

    ths = np.linspace(-math.pi, math.pi, n, endpoint=False)
    vals = np.array([E(t) for t in ths])
    k = int(np.argmin(vals))
    a, b = ths[k] - 2 * math.pi / n, ths[k] + 2 * math.pi / n
    gr = (math.sqrt(5) - 1) / 2
    for _ in range(80):
        c1, c2 = b - gr * (b - a), a + gr * (b - a)
        if E(c1) < E(c2):
            b = c2
        else:
            a = c1
    return bpt(0.5 * (a + b))


FIG96 = dict(wstar=np.array([0.45, 1.7]), H=np.array([[0.6, 0.25], [0.25, 1.0]]), eta=1.0)


def fig_9_6(out_dir=None):
    """Figure 9.6: the minimum of a quadratic error inside the L1 ball (sparse) and inside the L2 ball."""
    ws, Hm, eta = FIG96["wstar"], FIG96["H"], FIG96["eta"]
    g1 = np.linspace(-1.6, 2.4, 400)
    g2 = np.linspace(-1.6, 2.6, 400)
    W1, W2 = np.meshgrid(g1, g2)
    D1, D2 = W1 - ws[0], W2 - ws[1]
    E = 0.5 * (Hm[0, 0] * D1 ** 2 + 2 * Hm[0, 1] * D1 * D2 + Hm[1, 1] * D2 ** 2)
    fig, axes = plt.subplots(1, 2, figsize=(8.2, 4.2))
    for ax, q, lab in zip(axes, (1, 2), (r"$|w_1|+|w_2|\leq\eta$", r"$w_1^2+w_2^2\leq\eta$")):
        wh = lq_constrained_2d(ws, Hm, q, eta)
        Ewh = 0.5 * (wh - ws) @ Hm @ (wh - ws)
        ax.contour(W1, W2, E, levels=[Ewh * f for f in (0.25, 0.6, 1.0, 1.6, 2.4)], colors=common.RED, linewidths=1.1)
        Z = np.abs(W1) ** q + np.abs(W2) ** q
        ax.contourf(W1, W2, Z, levels=[0, eta], colors=[common.GREEN], alpha=0.25)
        ax.contour(W1, W2, Z, levels=[eta], colors=common.GREEN, linewidths=1.4)
        ax.plot(*ws, "o", color=common.RED, ms=4)
        ax.annotate(r"$\mathbf{w}^\star$", ws, xytext=(5, 4), textcoords="offset points", color=common.RED)
        ax.plot(*wh, "o", color=common.BLUE, ms=6)
        ax.annotate(r"$\widehat{\mathbf{w}}=(%.2f,\ %.2f)$" % (wh[0] + 0.0, wh[1]), wh, xytext=(8, -14),
                    textcoords="offset points", color=common.BLUE, fontsize=9)
        ax.axhline(0, color="k", lw=0.6)
        ax.axvline(0, color="k", lw=0.6)
        ax.set_aspect("equal")
        ax.set_xlabel(r"$w_1$")
        ax.set_ylabel(r"$w_2$")
        ax.set_title(("lasso, q = 1: " if q == 1 else "quadratic, q = 2: ") + lab, fontsize=10)
        ax.set_xlim(g1[0], g1[-1])
        ax.set_ylim(g2[0], g2[-1])
    fig.tight_layout()
    return savefig(fig, CH, "fig9-6", out_dir)


# ---------------------------------------------------------------- regularisation paths (demo 1)
LASSO_W = (3.0, 1.5, 0.0, 0.0, 2.0, 0.0, 0.0, 0.0)


def lasso_data(seed=7, N=40, Nv=200, rho=0.5, sigma=2.0, w=LASSO_W):
    """The data of l1-l2-paths-demo.html. Inputs are AR(1) correlated, x_1 = z_1,
    x_j = rho x_{j-1} + sqrt(1 - rho^2) z_j, targets t = w^T x + sigma eps; training rows first, then
    validation rows, each row drawing its D normals and then its noise. Columns are standardised with the
    training mean and (population) standard deviation and the targets centred with the training mean.
    Returns X, t, Xv, tv."""
    D = len(w)
    r = JSRandom(seed)
    rows, ts = [], []
    c = math.sqrt(1 - rho * rho)
    for n in range(N + Nv):
        x = []
        for j in range(D):
            z = r.norm()
            x.append(z if j == 0 else rho * x[j - 1] + c * z)
        rows.append(x)
        ts.append(sum(wj * xj for wj, xj in zip(w, x)) + sigma * r.norm())
    A = np.array(rows)
    T = np.array(ts)
    X, t, Xv, tv = A[:N], T[:N], A[N:], T[N:]
    mu = X.mean(0)
    sd = np.sqrt(((X - mu) ** 2).mean(0))
    tm = t.mean()
    return (X - mu) / sd, t - tm, (Xv - mu) / sd, tv - tm


def ridge(X, t, lam):
    """argmin 1/2 ||t - X w||^2 + lam/2 ||w||^2 = (X^T X + lam I)^{-1} X^T t."""
    D = X.shape[1]
    return np.linalg.solve(X.T @ X + lam * np.eye(D), X.T @ t)


def soft(z, a):
    return math.copysign(max(abs(z) - a, 0.0), z)


def lasso_cd(X, t, lam, sweeps=500, w0=None):
    """argmin 1/2 ||t - X w||^2 + lam/2 sum_j |w_j| by cyclic coordinate descent (soft thresholding at
    lam/2), written with explicit loops in the same order as the browser demo."""
    N, D = X.shape
    w = [0.0] * D if w0 is None else list(w0)
    cols = [[float(X[n, j]) for n in range(N)] for j in range(D)]
    tt = [float(v) for v in t]
    sq = [sum(v * v for v in cols[j]) for j in range(D)]
    r = [tt[n] - sum(cols[j][n] * w[j] for j in range(D)) for n in range(N)]
    for _ in range(sweeps):
        for j in range(D):
            cj = cols[j]
            rho_j = 0.0
            for n in range(N):
                rho_j += cj[n] * r[n]
            rho_j += sq[j] * w[j]
            new = soft(rho_j, 0.5 * lam) / sq[j]
            d = new - w[j]
            if d != 0.0:
                for n in range(N):
                    r[n] -= cj[n] * d
                w[j] = new
    return np.array(w)


def lasso_lambda_max(X, t):
    """Smallest lam for which the lasso solution is exactly zero: 2 max_j |x_j^T t|."""
    return 2.0 * np.max(np.abs(X.T @ t))


def reg_paths(X, t, Xv, tv, lams):
    """Ridge and lasso coefficients and validation RMS error along a grid of lam (largest first, warm start)."""
    WL, WR, eL, eR = [], [], [], []
    w = None
    for lam in lams:
        w = lasso_cd(X, t, lam, sweeps=200, w0=w)
        WL.append(w.copy())
        wr = ridge(X, t, lam)
        WR.append(wr)
        eL.append(math.sqrt(np.mean((Xv @ w - tv) ** 2)))
        eR.append(math.sqrt(np.mean((Xv @ wr - tv) ** 2)))
    return np.array(WL), np.array(WR), np.array(eL), np.array(eR)


# =========================================================================== Section 9.3: learning curves
def sine_data(seed, N, Nv, sigma=0.3):
    """N training and Nv validation points of t = sin(2 pi x) + sigma eps with x ~ U(0, 1); each point
    draws its x (one uniform) and then its noise (one normal), training points first."""
    r = JSRandom(seed)
    xs, ts = [], []
    for _ in range(N + Nv):
        x = r.u()
        xs.append(x)
        ts.append(math.sin(2 * math.pi * x) + sigma * r.norm())
    xs, ts = np.array(xs), np.array(ts)
    return xs[:N], ts[:N], xs[N:], ts[N:]


def net_init(seed, H, s1=3.0):
    """Initial weights of y(x) = sum_j v_j tanh(w_j x + b_j) + c: all w_j ~ s1 N(0,1), then all
    b_j ~ s1 N(0,1), then all v_j ~ N(0,1)/sqrt(H); c = 0. Returns [w, b, v, c] (numpy arrays)."""
    r = JSRandom(seed)
    w = np.array([s1 * r.norm() for _ in range(H)])
    b = np.array([s1 * r.norm() for _ in range(H)])
    v = np.array([r.norm() / math.sqrt(H) for _ in range(H)])
    return [w, b, v, np.zeros(1)]


def _tanh(a):
    return np.tanh(a)


def net_forward(P, x, R=None):
    """Outputs y(x) and hidden activations z; R (same shape as z) is an optional 0/1 dropout mask."""
    w, b, v, c = P
    z = _tanh(np.outer(x, w) + b)
    if R is not None:
        z = z * R
    return z @ v + c[0], z


def net_grads(P, x, t, lam=0.0, R=None):
    """Gradient of E = 1/2 sum_n (y_n - t_n)^2 + lam/2 (|w|^2 + |b|^2 + |v|^2) (the output bias c is not
    decayed). With a dropout mask R, the hidden activations are z * R."""
    w, b, v, c = P
    a = np.outer(x, w) + b
    th = _tanh(a)
    z = th if R is None else th * R
    y = z @ v + c[0]
    d = y - t
    gv = z.T @ d + lam * v
    gc = np.array([d.sum()])
    dz = np.outer(d, v) * (1 - th * th)
    if R is not None:
        dz = dz * R
    gw = (dz * x[:, None]).sum(0) + lam * w
    gb = dz.sum(0) + lam * b
    return [gw, gb, gv, gc], 0.5 * float(d @ d)


def rms(P, x, t):
    y, _ = net_forward(P, x)
    return math.sqrt(float(np.mean((y - t) ** 2)))


ES_DEFAULT = dict(seed=1, N=10, Nv=20, H=12, s1=1.0, lr=0.005, steps=50000, every=1000, lam=0.0)


def train_net(seed=1, N=10, Nv=20, H=10, s1=3.0, lr=0.02, steps=40000, every=800, lam=0.0, sigma=0.3):
    """Full-batch gradient descent on the sum-of-squares error (plus weight decay lam) of a one-input tanh
    network on the sinusoidal data (the early-stopping demo and Figure 9.7). Data come from
    sine_data(seed, ...), initial weights from net_init(seed + 100, ...). Records, every `every` steps,
    (step, training RMS, validation RMS, squared norm of w, b, v). Returns the final weights and the record."""
    x, t, xv, tv = sine_data(seed, N, Nv, sigma)
    P = net_init(seed + 100, H, s1)
    rec = []
    for k in range(steps + 1):
        if k % every == 0:
            rec.append((k, rms(P, x, t), rms(P, xv, tv), float(sum((p * p).sum() for p in P[:3]))))
        if k == steps:
            break
        G, _ = net_grads(P, x, t, lam)
        for p, g in zip(P, G):
            p -= lr * g
    return P, np.array(rec)


def fig_9_7(out_dir=None):
    """Figure 9.7: training-set and validation-set error during gradient-descent training (sinusoidal data)."""
    _, rec = train_net(**ES_DEFAULT)
    it = rec[:, 0] / ES_DEFAULT["every"]
    k = int(np.argmin(rec[:, 2]))
    fig, axes = plt.subplots(1, 2, figsize=(8.2, 2.9))
    axes[0].plot(it, rec[:, 1], color=common.BLUE)
    axes[1].plot(it, rec[:, 2], color=common.RED)
    for ax, lab in zip(axes, ("training-set RMS error", "validation-set RMS error")):
        ax.axvline(it[k], color="k", ls="--", lw=1)
        ax.set_xlabel("iteration (units of %d gradient steps)" % ES_DEFAULT["every"])
        ax.set_ylabel(lab)
        ax.set_xlim(0, it[-1])
    axes[0].set_ylim(0.15, 0.55)
    axes[1].set_ylim(0.3, 0.65)
    fig.tight_layout()
    return savefig(fig, CH, "fig9-7", out_dir)


def gd_filter(eig, rho, tau):
    """Fraction of w*_j reached after tau steps of gradient descent from the origin (9.58): 1 - (1 - rho eig)^tau."""
    return 1.0 - (1.0 - rho * np.asarray(eig, float)) ** tau


def ridge_filter(eig, lam):
    """Fraction of w*_j kept by weight decay: eig/(eig + lam)."""
    eig = np.asarray(eig, float)
    return eig / (eig + lam)


def fig_9_8(out_dir=None):
    """Figure 9.8: the gradient-descent path from the origin on a quadratic, and the weight-decay path."""
    eig = np.array([0.05, 1.0])
    ws = np.array([1.6, 0.95])
    rho = 0.2
    taus = np.arange(0, 600)
    path = np.array([gd_filter(eig, rho, t) * ws for t in taus])
    lams = np.logspace(3, -4, 400)
    rpath = np.array([ridge_filter(eig, l) * ws for l in lams])
    tau_hat = 25
    w_es = gd_filter(eig, rho, tau_hat) * ws
    w_wd = ridge_filter(eig, 1.0 / (rho * tau_hat)) * ws
    g1 = np.linspace(-0.3, 2.3, 300)
    g2 = np.linspace(-0.3, 1.5, 300)
    W1, W2 = np.meshgrid(g1, g2)
    E = 0.5 * (eig[0] * (W1 - ws[0]) ** 2 + eig[1] * (W2 - ws[1]) ** 2)
    fig, ax = plt.subplots(figsize=(5.0, 3.8))
    ax.contour(W1, W2, E, levels=[0.004, 0.015, 0.04, 0.08, 0.14], colors=common.RED, linewidths=1.0)
    ax.plot(path[:, 0], path[:, 1], color=common.BLUE, lw=1.8, label="gradient descent from the origin")
    ax.plot(rpath[:, 0], rpath[:, 1], color=common.GREEN, lw=1.4, ls=":", label=r"weight decay, $\lambda$ from $\infty$ to 0")
    ax.plot(*ws, "o", color=common.RED, ms=5)
    ax.annotate(r"$\mathbf{w}^\star$", ws, xytext=(6, 3), textcoords="offset points", color=common.RED)
    ax.plot(*w_es, "o", color=common.BLUE, ms=5)
    ax.annotate(r"$\widehat{\mathbf{w}}$ ($\tau=%d$)" % tau_hat, w_es, xytext=(6, -12), textcoords="offset points", color=common.BLUE, fontsize=9)
    ax.plot(*w_wd, "s", color=common.GREEN, ms=4, mfc="none")
    ax.axhline(0, color="k", lw=0.6)
    ax.axvline(0, color="k", lw=0.6)
    ax.set_xlabel(r"$w_1$ (eigenvalue %.2f)" % eig[0])
    ax.set_ylabel(r"$w_2$ (eigenvalue %.0f)" % eig[1])
    ax.set_aspect("equal")
    ax.legend(loc="lower right", fontsize=8)
    fig.tight_layout()
    return savefig(fig, CH, "fig9-8", out_dir)


# ---------------------------------------------------------------- double descent
def _mnist_rf_data(N=300, Ntest=2000, seed=0, label_noise=0.0):
    X, y = common.mnist(train=True)
    Xt, yt = common.mnist(train=False)
    rng = np.random.default_rng(seed)
    idx = rng.choice(len(X), N, replace=False)
    Xtr, ytr = X[idx], y[idx].copy()
    if label_noise > 0:
        flip = rng.random(N) < label_noise
        ytr[flip] = rng.integers(0, 10, flip.sum())
    it = rng.choice(len(Xt), Ntest, replace=False)
    Xte, yte = Xt[it], yt[it]
    mu = Xtr.mean(0)
    return Xtr - mu, ytr, Xte - mu, yte


def relu_features(Xtr, Xte, p, seed):
    """Random ReLU features max(0, V^T x) with V ~ N(0, 1/(D s^2)), s^2 the mean pixel variance."""
    r = np.random.default_rng(seed)
    sc = math.sqrt(Xtr.shape[1] * Xtr.var(0).mean())
    V = r.standard_normal((Xtr.shape[1], p)) / sc
    return np.maximum(Xtr @ V, 0), np.maximum(Xte @ V, 0)


DD_PS = (10, 20, 40, 70, 100, 140, 180, 220, 250, 270, 285, 295, 300, 305, 315, 330, 360, 400, 470, 560, 700,
         900, 1200, 1600, 2200, 3000, 4500, 6000)


def random_features_dd(N=300, ps=DD_PS, n_seeds=5):
    """Minimum-norm least squares (np.linalg.lstsq) on p random ReLU features of N MNIST digits, one-hot
    targets. Returns ps and arrays (len(ps), 4): training squared error, test squared error (both summed over
    the 10 outputs, averaged over points), training and test misclassification rates, averaged over seeds,
    as dict(ps, R)."""
    Xtr, ytr, Xte, yte = _mnist_rf_data(N)
    Ttr, Tte = np.eye(10)[ytr], np.eye(10)[yte]
    out = []
    for p in ps:
        acc = []
        for s in range(n_seeds):
            F, Ft = relu_features(Xtr, Xte, p, 100 + s)
            W = np.linalg.lstsq(F, Ttr, rcond=None)[0]
            acc.append([((F @ W - Ttr) ** 2).sum(1).mean(), ((Ft @ W - Tte) ** 2).sum(1).mean(),
                        (np.argmax(F @ W, 1) != ytr).mean(), (np.argmax(Ft @ W, 1) != yte).mean()])
        out.append(np.mean(acc, 0))
    return dict(ps=np.array(ps), R=np.array(out))


def fig_9_9(out_dir=None):
    """Figure 9.9: double descent: training and test error against the number of random ReLU features (MNIST)."""
    d = _cached("ch09_dd", lambda: random_features_dd())
    ps, R = d["ps"], d["R"]
    N = 300
    fig, axes = plt.subplots(1, 2, figsize=(8.6, 3.2))
    ax = axes[0]
    ax.axvspan(150, 600, color=common.ORANGE, alpha=0.15, lw=0)
    ax.plot(ps, R[:, 3], "-o", ms=3, color=common.BLUE, label="test")
    ax.plot(ps, R[:, 2], "--", color=common.BLUE, alpha=0.7, label="train")
    ax.set_ylabel("misclassification rate")
    ax.set_ylim(0, 0.9)
    ax = axes[1]
    ax.axvspan(150, 600, color=common.ORANGE, alpha=0.15, lw=0)
    ax.plot(ps, R[:, 1], "-o", ms=3, color=common.RED, label="test")
    ax.plot(ps, np.maximum(R[:, 0], 1e-3), "--", color=common.RED, alpha=0.7, label="train")
    ax.set_yscale("log")
    ax.set_ylim(1e-3, 1e3)
    ax.set_ylabel("squared error (10 outputs)")
    for ax in axes:
        ax.set_xscale("log")
        ax.axvline(N, color="k", ls="--", lw=1)
        ax.text(N * 1.08, ax.get_ylim()[1] * (0.8 if ax is axes[0] else 0.3), "interpolation\nthreshold p = N", fontsize=8, va="top")
        ax.set_xlabel("number of random features p (network width)")
        ax.legend(loc="lower left" if ax is axes[0] else "upper left", fontsize=8)
    fig.tight_layout()
    return savefig(fig, CH, "fig9-9", out_dir)


TWO_SPEED = dict(D_fast=50, D_slow=10, N=200, sigma=2.0, lam_fast=1.0, lam_slow=0.01, b_fast=1.0, b_slow=3.0)


def two_speed_risk(use_fast=True, use_slow=True, ts=None, reps=50, seed=0, D_fast=50, D_slow=10, N=200, sigma=2.0,
                   lam_fast=1.0, lam_slow=0.01, b_fast=1.0, b_slow=3.0):
    """Expected excess test risk of gradient flow (time t, from w = 0) for least squares with a Gaussian
    design whose features have variance lam_fast (D_fast of them) or lam_slow (D_slow of them). The true
    weights put signal power b_fast and b_slow in the two groups (sum lam_j theta_j^2 per group). A model may
    use only one group (the other group's signal then acts as extra noise). The exact path
    w(t) = V diag((1 - exp(-s^2 t))/s) U^T y/sqrt(N) is averaged over `reps` training sets.
    Returns ts and the risk E[(w(t) - theta)^T Sigma (w(t) - theta)] (noise variance not included)."""
    ts = np.logspace(-1, 4.5, 80) if ts is None else ts
    lam = np.r_[np.full(D_fast, lam_fast), np.full(D_slow, lam_slow)]
    th = np.r_[np.full(D_fast, math.sqrt(b_fast / (D_fast * lam_fast))), np.full(D_slow, math.sqrt(b_slow / (D_slow * lam_slow)))]
    keep = np.r_[np.full(D_fast, use_fast), np.full(D_slow, use_slow)]
    rng = np.random.default_rng(seed)
    R = np.zeros(len(ts))
    for _ in range(reps):
        X = rng.standard_normal((N, len(lam))) * np.sqrt(lam)
        y = X @ th + sigma * rng.standard_normal(N)
        Xk = X[:, keep] / math.sqrt(N)
        U, s, Vt = np.linalg.svd(Xk, full_matrices=False)
        uy = U.T @ (y / math.sqrt(N))
        for k, t in enumerate(ts):
            wk = Vt.T @ ((1 - np.exp(-s * s * t)) / s * uy)
            w = np.zeros(len(lam))
            w[keep] = wk
            d = w - th
            R[k] += (d * lam) @ d / reps
    return ts, R


def fig_9_10(out_dir=None):
    """Figure 9.10: test error against training time for three model sizes; epoch-wise double descent."""
    ts = np.logspace(-1, 4.5, 90)
    cfg = [("small model (10 slow features)", False, True, "#d4a017"),
           ("intermediate model (50 fast features)", True, False, "#2a7f7f"),
           ("large model (all 60 features)", True, True, "#9b2d4f")]
    fig, ax = plt.subplots(figsize=(6.0, 3.6))
    for lab, f, s, c in cfg:
        _, R = two_speed_risk(f, s, ts=ts)
        ax.plot(ts, R + TWO_SPEED["sigma"] ** 2, color=c, lw=1.8, label=lab)
    ax.set_xscale("log")
    ax.set_xlabel(r"training time $t=\eta\tau$ (gradient descent steps $\times$ learning rate)")
    ax.set_ylabel("expected test error")
    ax.legend(fontsize=8.5, loc="lower left")
    fig.tight_layout()
    return savefig(fig, CH, "fig9-10", out_dir)


def gauss_dd_theory(p, N, beta2, sigma2):
    """Exact expected test error E[(y - x^T w_hat)^2] of least squares (p < N - 1) or minimum-norm least
    squares (p > N + 1) using the first p of D isotropic Gaussian features; beta2[j] = theta_j^2.
    Omitted features act as noise of variance s2 = sigma2 + sum_{j>p} beta2_j (Belkin, Hsu and Xu, 2020):
      p <= N - 2:  s2 (1 + p/(N - p - 1));
      p >= N + 2:  sum_{j<=p} beta2_j (1 - N/p) + s2 (1 + N/(p - N - 1)).
    Returns nan for N - 1 <= p <= N + 1 (infinite)."""
    beta2 = np.asarray(beta2, float)
    s2 = sigma2 + beta2[p:].sum()
    if p <= N - 2:
        return s2 * (1 + p / (N - p - 1))
    if p >= N + 2:
        return beta2[:p].sum() * (1 - N / p) + s2 * (1 + N / (p - N - 1))
    return float("nan")


def gauss_dd_mc(p, N, beta2, sigma2, reps=200, Ntest=None, seed=0):
    """Monte Carlo version of gauss_dd_theory (exact test error from the population covariance = I)."""
    rng = np.random.default_rng(seed)
    beta = np.sqrt(np.asarray(beta2, float))
    D = len(beta)
    out = []
    for _ in range(reps):
        X = rng.standard_normal((N, D))
        y = X @ beta + math.sqrt(sigma2) * rng.standard_normal(N)
        w = np.zeros(D)
        w[:p] = np.linalg.pinv(X[:, :p]) @ y
        out.append(((w - beta) ** 2).sum() + sigma2)
    return float(np.mean(out))


def dd_beta2(D=400):
    b = 1.0 / np.arange(1, D + 1)
    return b / np.sqrt((b ** 2).sum())


def fig_9_11(out_dir=None):
    """Figure 9.11: more data can hurt near the interpolation threshold (two training-set sizes)."""
    b2 = dd_beta2() ** 2 * 1.0
    sigma2 = 0.1
    fig, ax = plt.subplots(figsize=(6.0, 3.6))
    for N, c in ((40, common.ORANGE), (100, common.BLUE)):
        ps = np.arange(1, 401)
        R = np.array([gauss_dd_theory(p, N, b2, sigma2) for p in ps])
        ax.plot(ps, R, color=c, lw=1.8, label="N = %d training points (theory)" % N)
        pm = [5, 15, 25, 33, 50, 60, 70, 80, 90, 120, 150, 200, 300, 400]
        pm = [p for p in pm if abs(p - N) > 3]
        ax.plot(pm, [gauss_dd_mc(p, N, b2, sigma2, reps=60, seed=p) for p in pm], "o", ms=3.5, color=c)
    worse = [p for p in range(1, 401) if np.isfinite(gauss_dd_theory(p, 40, b2, sigma2)) and np.isfinite(gauss_dd_theory(p, 100, b2, sigma2))
             and gauss_dd_theory(p, 100, b2, sigma2) > gauss_dd_theory(p, 40, b2, sigma2)]
    if worse:
        ax.axvspan(min(worse), max(worse), color=common.RED, alpha=0.08, lw=0)
    ax.set_yscale("log")
    ax.set_ylim(0.1, 20)
    ax.set_xlabel("number of features used, p (model size)")
    ax.set_ylabel("expected test error")
    ax.legend(fontsize=8.5, loc="upper right")
    fig.tight_layout()
    return savefig(fig, CH, "fig9-11", out_dir)


# =========================================================================== Section 9.4: soft weight sharing
def _npdf(w, mu, s2):
    return np.exp(-0.5 * (w - mu) ** 2 / s2) / np.sqrt(2 * np.pi * s2)


def sws_omega(w, eta, mu, xi):
    """Omega(w) = -sum_i ln sum_j pi_j N(w_i | mu_j, sigma_j^2) (9.22), with pi = softmax(eta) (9.30) and
    sigma_j^2 = exp(xi_j) (9.27)."""
    pi = np.exp(eta - eta.max())
    pi /= pi.sum()
    s2 = np.exp(xi)
    dens = pi[None, :] * _npdf(w[:, None], mu[None, :], s2[None, :])
    return -np.log(dens.sum(1)).sum()


def sws_grads(w, eta, mu, xi):
    """Derivatives of Omega with respect to w (9.25), mu (9.26), xi (9.28) and eta (9.31)."""
    pi = np.exp(eta - eta.max())
    pi /= pi.sum()
    s2 = np.exp(xi)
    dens = pi[None, :] * _npdf(w[:, None], mu[None, :], s2[None, :])
    gam = dens / dens.sum(1, keepdims=True)                    # (9.24)
    diff = w[:, None] - mu[None, :]
    g_w = (gam * diff / s2[None, :]).sum(1)                    # (9.25) without lambda
    g_mu = (gam * (-diff) / s2[None, :]).sum(0)                # (9.26)
    g_xi = 0.5 * (gam * (1 - diff ** 2 / s2[None, :])).sum(0)  # (9.28)
    g_eta = (pi[None, :] - gam).sum(0)                         # (9.31)
    return g_w, g_mu, g_xi, g_eta, gam


# =========================================================================== Section 9.5: residual connections
def input_gradient(depth, width=200, residual=False, seed=0, xs=None, bn=True):
    """dy/dx on a grid of inputs xs (default 256 points in [-2, 2], the 'batch') for a randomly initialised
    ReLU network with one input, one linear output and `width` units per layer.

    Plain: z_l = ReLU(BN(W_l z_{l-1})); `depth` counts the layers of weights (input and output included).
    Residual (pre-activation blocks, Figure 9.16(b)): after the input layer and one linear layer W_0,
    z_l = z_{l-1} + W_l2 ReLU(BN(W_l1 ReLU(BN(z_{l-1})))), so that depth = 3 + 2 x (number of blocks).
    The input layer has weights and biases N(0, 1), so its kinks -b_j/w_j are spread over the inputs; later
    weights are N(0, 2/fan_in) (He) and have no biases, because BN removes them. BN standardises each unit
    over the batch of inputs, with the batch mean and standard deviation then held fixed (the network
    evaluated in inference mode with statistics taken from this batch), so dy/dx is the derivative of an
    ordinary piecewise-linear function. It is computed exactly by forward-mode differentiation (each layer's
    derivative with respect to x is propagated alongside its value). bn=False drops the normalisation."""
    xs = np.linspace(-2, 2, 256) if xs is None else xs
    rng = np.random.default_rng(seed)
    x = xs[None, :]

    def norm(a, da):
        if not bn:
            return a, da
        m = a.mean(1, keepdims=True)
        sd = a.std(1, keepdims=True) + 1e-8
        return (a - m) / sd, da / sd

    W = rng.standard_normal((width, 1))
    b = rng.standard_normal((width, 1))
    a, da = W @ x + b, W * np.ones_like(x)           # input layer: weights and biases N(0, 1), no BN
    z, dz = np.maximum(a, 0), (a > 0) * da
    if not residual:
        for _ in range(depth - 2):
            W = rng.standard_normal((width, width)) * math.sqrt(2.0 / width)
            a, da = norm(W @ z, W @ dz)
            z, dz = np.maximum(a, 0), (a > 0) * da
    else:
        W0 = rng.standard_normal((width, width)) * math.sqrt(2.0 / width)
        z, dz = W0 @ z, W0 @ dz                        # a linear layer starts the residual stream
        for _ in range((depth - 3) // 2):
            W1 = rng.standard_normal((width, width)) * math.sqrt(2.0 / width)
            W2 = rng.standard_normal((width, width)) * math.sqrt(2.0 / width)
            a, da = norm(z, dz)
            h, dh = np.maximum(a, 0), (a > 0) * da
            a, da = norm(W1 @ h, W1 @ dh)
            h, dh = np.maximum(a, 0), (a > 0) * da
            z, dz = z + W2 @ h, dz + W2 @ dh
    Wo = rng.standard_normal((1, width)) * math.sqrt(1.0 / width)
    return xs, (Wo @ dz)[0], (Wo @ z)[0]


def gradient_correlation(g):
    """Correlation between the gradients at neighbouring inputs (lag-1 autocorrelation)."""
    g = g - g.mean()
    return float((g[:-1] * g[1:]).sum() / (g * g).sum())


def correlation_vs_depth(depths_plain=(2, 3, 4, 6, 8, 12, 16, 25), depths_res=(5, 9, 15, 21, 31, 41, 51), seeds=10):
    """Mean neighbour correlation of dy/dx against depth for plain and residual networks (Figure 9.12(d))."""
    cp = [np.mean([gradient_correlation(input_gradient(L, seed=s)[1]) for s in range(seeds)]) for L in depths_plain]
    cr = [np.mean([gradient_correlation(input_gradient(L, residual=True, seed=s)[1]) for s in range(seeds)]) for L in depths_res]
    return np.array(depths_plain), np.array(cp), np.array(depths_res), np.array(cr)


def fig_9_12(out_dir=None):
    """Figure 9.12: dy/dx against x for a 2-layer network, a 25-layer network and a 51-layer residual network."""
    cases = [("(a) 2 layers", 2, False), ("(b) 25 layers", 25, False), ("(c) 51 layers, residual", 51, True)]
    fig, axes = plt.subplots(1, 4, figsize=(12.4, 2.9))
    for ax, (lab, L, res) in zip(axes, cases):
        xs, g, _ = input_gradient(L, residual=res, seed=1)
        cbar = np.mean([gradient_correlation(input_gradient(L, residual=res, seed=s)[1]) for s in range(10)])
        ax.plot(xs, g, color=common.BLUE, lw=0.8)
        ax.set_xlabel("input x")
        ax.set_ylabel("gradient dy/dx")
        ax.set_title("%s\nneighbour correlation %.2f" % (lab, cbar), fontsize=9.5)
        ax.set_xlim(-2, 2)
    dp, cp, dr, cr = correlation_vs_depth()
    ax = axes[3]
    ax.plot(dp, cp, "o-", color=common.RED, ms=4, label="plain")
    ax.plot(dr, cr, "s-", color=common.BLUE, ms=4, label="residual")
    ax.plot(dr, 1.0 / np.sqrt((dr - 3) / 2.0), ":", color=common.BLUE, lw=1, label=r"$1/\sqrt{\rm blocks}$")
    ax.axhline(0, color="k", lw=0.5)
    ax.set_xlabel("layers of weights")
    ax.set_ylabel("neighbour correlation")
    ax.set_title("(d) mean over 10 networks", fontsize=9.5)
    ax.set_ylim(-0.1, 1.05)
    ax.legend(fontsize=8)
    fig.tight_layout()
    return savefig(fig, CH, "fig9-12", out_dir)


def spiral_data(n_per=200, K=3, seed=0, noise=0.2):
    rng = np.random.default_rng(seed)
    X, y = [], []
    for k in range(K):
        r = np.linspace(0.05, 1, n_per)
        th = np.linspace(k * 4.0, (k + 1) * 4.0, n_per) * 1.0 + noise * rng.standard_normal(n_per)
        X.append(np.c_[r * np.sin(th), r * np.cos(th)])
        y.append(np.full(n_per, k))
    return np.vstack(X), np.concatenate(y)


def _deep_net(torch, residual, depth=30, width=24):
    nn = torch.nn

    class Plain(nn.Module):
        def __init__(self):
            super().__init__()
            self.inp = nn.Linear(2, width)
            self.hid = nn.ModuleList([nn.Linear(width, width) for _ in range(depth - 2)])
            self.out = nn.Linear(width, 3)

        def forward(self, x):
            z = torch.relu(self.inp(x))
            for L in self.hid:
                z = torch.relu(L(z))
            return self.out(z)

    class Res(nn.Module):
        def __init__(self):
            super().__init__()
            self.inp = nn.Linear(2, width)
            nb = (depth - 2) // 2
            self.l1 = nn.ModuleList([nn.Linear(width, width) for _ in range(nb)])
            self.l2 = nn.ModuleList([nn.Linear(width, width) for _ in range(nb)])
            self.out = nn.Linear(width, 3)

        def forward(self, x):
            z = self.inp(x)
            for A, B in zip(self.l1, self.l2):
                z = z + B(torch.relu(A(torch.relu(z))))     # Figure 9.16(b): ReLU, linear, ReLU, linear, add
            return self.out(torch.relu(z))

    net = Res() if residual else Plain()
    for m in net.modules():
        if isinstance(m, nn.Linear):
            nn.init.kaiming_normal_(m.weight, nonlinearity="relu")
            nn.init.zeros_(m.bias)
    if residual:
        for B in net.l2:
            B.weight.data *= 1.0 / math.sqrt(len(net.l2))
    return net


def loss_surface(residual, depth=30, steps=1500, n_grid=41, span=0.5, seed=0):
    """Train a deep plain or residual ReLU network on the spiral data (Adam, full batch) and evaluate the
    cross-entropy over the plane w + a d1 + b d2, a, b in [-span, span], where d1, d2 are random directions
    with filter normalisation (each row of each weight matrix rescaled to the norm of the trained row;
    bias directions zero; Li et al., 2017). Returns a dict with the grid, the losses and the training curve."""
    torch = common.torch_setup(seed, threads=1)
    X, y = spiral_data()
    Xt = torch.tensor(X, dtype=torch.float32)
    yt = torch.tensor(y)
    net = _deep_net(torch, residual, depth)
    opt = torch.optim.Adam(net.parameters(), lr=1e-3)
    lossf = torch.nn.CrossEntropyLoss()
    curve = []
    for k in range(steps):
        opt.zero_grad()
        L = lossf(net(Xt), yt)
        L.backward()
        opt.step()
        curve.append(float(L.detach()))
    base = [p.detach().clone() for p in net.parameters()]

    def direction():
        ds = []
        for p in base:
            d = torch.randn_like(p)
            if p.dim() == 2:
                d = d / d.norm(dim=1, keepdim=True) * p.norm(dim=1, keepdim=True)
            else:
                d = torch.zeros_like(p)
            ds.append(d)
        return ds

    d1, d2 = direction(), direction()
    al = np.linspace(-span, span, n_grid)
    Z = np.zeros((n_grid, n_grid))
    with torch.no_grad():
        for i, a in enumerate(al):
            for j, b in enumerate(al):
                for p, p0, u, v in zip(net.parameters(), base, d1, d2):
                    p.copy_(p0 + a * u + b * v)
                Z[j, i] = float(lossf(net(Xt), yt))
        for p, p0 in zip(net.parameters(), base):
            p.copy_(p0)
        acc = float((net(Xt).argmax(1) == yt).float().mean())
    return dict(al=al, Z=Z, curve=np.array(curve), acc=acc)


def fig_9_14(out_dir=None):
    """Figure 9.14: the loss over a random plane through the trained weights, without and with residual connections."""
    from mpl_toolkits.mplot3d import Axes3D  # noqa: F401
    res = {k: _cached("ch09_surface_%s" % k, lambda r=(k == "res"): loss_surface(r)) for k in ("plain", "res")}
    fig = plt.figure(figsize=(9.0, 4.0))
    for i, (k, lab) in enumerate((("plain", "(a) 30 layers, no residual connections"),
                                  ("res", "(b) 30 layers with residual connections"))):
        ax = fig.add_subplot(1, 2, i + 1, projection="3d")
        al = res[k]["al"]
        A, B = np.meshgrid(al, al)
        Z = np.minimum(res[k]["Z"], 5.0)
        ax.plot_surface(A, B, Z, cmap="viridis", vmin=0, vmax=5, rstride=1, cstride=1, linewidth=0.1,
                        edgecolor="k", alpha=0.95)
        ax.set_zlim(0, 5)
        ax.set_title("%s\ntrain accuracy %.2f" % (lab, res[k]["acc"]), fontsize=9.5)
        ax.set_xlabel(r"$\alpha$", labelpad=-6)
        ax.set_ylabel(r"$\beta$", labelpad=-6)
        ax.set_zlabel("loss", labelpad=-4)
        ax.tick_params(labelsize=7, pad=-2)
        ax.view_init(elev=38, azim=-55)
    fig.subplots_adjust(left=0.0, right=1.0, wspace=0.02)
    return savefig(fig, CH, "fig9-14", out_dir)


# =========================================================================== Section 9.6: ensembles and dropout
def bootstrap_indices(seed, N):
    r = JSRandom(seed)
    return np.array([int(math.floor(r.u() * N)) for _ in range(N)])


def train_adam(P, x, t, lr=0.01, steps=3000, lam=0.0, rho=None, mask_seed=None, b1=0.9, b2=0.999, eps=1e-8):
    """Adam on E = 1/2 sum_n (y_n - t_n)^2 (+ weight decay lam) for the one-input tanh network.
    With rho (keep probability) and mask_seed, every step draws a fresh dropout mask R_nj (1 with
    probability rho: JSRandom(mask_seed).u() < rho, in the order step, n, j) for the hidden units."""
    P = [p.copy() for p in P]
    m = [np.zeros_like(p) for p in P]
    s = [np.zeros_like(p) for p in P]
    r = JSRandom(mask_seed) if rho is not None else None
    N, H = len(x), len(P[0])
    p1 = p2 = 1.0                      # b1^k and b2^k, by repeated multiplication (as in the demo)
    for k in range(1, steps + 1):
        R = None
        if r is not None:
            R = np.array([[1.0 if r.u() < rho else 0.0 for _ in range(H)] for _ in range(N)])
        G, _ = net_grads(P, x, t, lam, R)
        p1 *= b1
        p2 *= b2
        c1, c2 = 1 - p1, 1 - p2
        for i in range(4):
            m[i] = b1 * m[i] + (1 - b1) * G[i]
            s[i] = b2 * s[i] + (1 - b2) * G[i] * G[i]
            P[i] = P[i] - lr * (m[i] / c1) / (np.sqrt(s[i] / c2) + eps)
    return P


ENS_DEFAULT = dict(seed=3, N=20, H=20, M=10, steps=2000, lr=0.01, bootstrap=False, s1=3.0)
GRID = np.linspace(0, 1, 201)


def ensemble_run(seed=3, N=20, H=20, M=10, steps=2000, lr=0.01, bootstrap=False, s1=3.0, sigma=0.3):
    """M networks trained with Adam on the same sinusoidal data (sine_data(seed, N, 0)), member m starting
    from net_init(seed + 1000 + m) and, if bootstrap, trained on the sample bootstrap_indices(seed + 500 + m).
    Errors are measured against h(x) = sin(2 pi x) on GRID (201 points): E_m = mean over x of eps_m(x)^2.
    Returns dict(preds (M, 201), E (M,), E_AV, E_COM, E_COM_m (committee of the first m), C (error
    covariance matrix))."""
    x, t, _, _ = sine_data(seed, N, 0, sigma)
    h = np.sin(2 * np.pi * GRID)
    preds = []
    for mm in range(M):
        P0 = net_init(seed + 1000 + mm, H, s1)
        if bootstrap:
            idx = bootstrap_indices(seed + 500 + mm, N)
            P = train_adam(P0, x[idx], t[idx], lr, steps)
        else:
            P = train_adam(P0, x, t, lr, steps)
        preds.append(net_forward(P, GRID)[0])
    preds = np.array(preds)
    eps = preds - h
    E = (eps ** 2).mean(1)
    com = np.cumsum(preds, 0) / np.arange(1, M + 1)[:, None]
    E_com_m = ((com - h) ** 2).mean(1)
    C = eps @ eps.T / len(GRID)
    return dict(x=x, t=t, preds=preds, E=E, E_AV=float(E.mean()), E_COM=float(E_com_m[-1]), E_COM_m=E_com_m, C=C)


DROP_DEFAULT = dict(seed=1, N=20, H=50, steps=3000, lr=0.01, rho=0.8, K=50, s1=3.0)


def dropout_run(seed=1, N=20, H=50, steps=3000, lr=0.01, rho=0.8, K=50, s1=3.0, sigma=0.3):
    """One network trained with dropout on the hidden units (keep probability rho, masks from
    JSRandom(seed + 2000)), and the same network trained without dropout, both from net_init(seed + 1000).
    Predictions on GRID: weight scaling (outgoing weights times rho), and Monte Carlo dropout (mean and
    standard deviation over K masks from JSRandom(seed + 3000), drawn in the order mask k, unit j, shared by
    all inputs). Returns a dict of predictions and errors against sin(2 pi x)."""
    x, t, _, _ = sine_data(seed, N, 0, sigma)
    h = np.sin(2 * np.pi * GRID)
    P0 = net_init(seed + 1000, H, s1)
    Pd = train_adam(P0, x, t, lr, steps, rho=rho, mask_seed=seed + 2000)
    Pp = train_adam(P0, x, t, lr, steps)
    w, b, v, c = Pd
    ws = net_forward([w, b, rho * v, c], GRID)[0]
    r = JSRandom(seed + 3000)
    mc = []
    for _ in range(K):
        Rk = np.array([1.0 if r.u() < rho else 0.0 for _ in range(H)])
        mc.append(net_forward([w, b, v * Rk, c], GRID)[0])
    mc = np.array(mc)
    plain = net_forward(Pp, GRID)[0]
    err = lambda f: float(((f - h) ** 2).mean())  # noqa: E731
    return dict(x=x, t=t, ws=ws, mc_mean=mc.mean(0), mc_sd=mc.std(0), plain=plain, mc=mc,
                E_ws=err(ws), E_mc=err(mc.mean(0)), E_plain=err(plain))


def committee_subset_errors(C):
    """Mean committee error over all subsets of each size m of the M members, from the error covariance
    matrix C (C_ml = E_x[eps_m eps_l]); the committee of a subset S has error sum_{m,l in S} C_ml / |S|^2."""
    import itertools
    M = len(C)
    out = []
    for m in range(1, M + 1):
        vals = [C[np.ix_(S, S)].sum() / m ** 2 for S in itertools.combinations(range(M), m)]
        out.append(np.mean(vals))
    return np.array(out)


def linear_dropout_objective(W, X, T, rho):
    """Expected dropout error (9.72)-(9.73) for y_k = sum_i w_ki R_ni x_ni (W is K x D):
    sum_nk (t_nk - rho sum_i w_ki x_ni)^2 + rho(1 - rho) sum_nki w_ki^2 x_ni^2."""
    fit = ((T - rho * X @ W.T) ** 2).sum()
    pen = rho * (1 - rho) * ((W ** 2) @ (X ** 2).sum(0)).sum()
    return fit + pen


def linear_dropout_solution(X, T, rho):
    """Minimiser of the expected dropout error: W = T^T X (rho X^T X + (1 - rho) diag(X^T X))^{-1}."""
    G = X.T @ X
    A = rho * G + (1 - rho) * np.diag(np.diag(G))
    return np.linalg.solve(A, X.T @ T).T


# =========================================================================== supplementary figures
def fig_9_s1(out_dir=None):
    """Figure 9.S1: lasso and ridge regularisation paths and validation error (the L1/L2 demo's data)."""
    X, t, Xv, tv = lasso_data()
    lmax = lasso_lambda_max(X, t)
    lams = lmax * np.logspace(0.05, -4, 90)
    WL, WR, eL, eR = reg_paths(X, t, Xv, tv, lams)
    cols = [common.RED, common.BLUE, common.GREY, "#999999", common.GREEN, "#bbbbbb", "#aaaaaa", "#cccccc"]
    fig, axes = plt.subplots(1, 3, figsize=(10.4, 3.2))
    for j in range(X.shape[1]):
        lw = 1.8 if LASSO_W[j] != 0 else 1.0
        axes[0].plot(lams, WL[:, j], color=cols[j], lw=lw)
        axes[1].plot(lams, WR[:, j], color=cols[j], lw=lw)
    for ax, ttl in zip(axes[:2], ("lasso (q = 1)", "ridge (q = 2)")):
        ax.set_xscale("log")
        ax.axhline(0, color="k", lw=0.5)
        ax.set_xlabel(r"$\lambda$")
        ax.set_ylabel("coefficient $w_j$")
        ax.set_title(ttl)
        ax.invert_xaxis()
    nz = (np.abs(WL) > 1e-12).sum(1)
    ax2 = axes[0].twinx()
    ax2.step(lams, nz, color="k", lw=0.8, alpha=0.5, where="mid")
    ax2.set_ylabel("non-zero coefficients", fontsize=8)
    ax2.set_ylim(0, 8.5)
    axes[2].plot(lams, eL, color=common.RED, label="lasso")
    axes[2].plot(lams, eR, color=common.BLUE, label="ridge")
    axes[2].set_xscale("log")
    axes[2].invert_xaxis()
    axes[2].set_xlabel(r"$\lambda$")
    axes[2].set_ylabel("validation RMS error")
    axes[2].legend(fontsize=8)
    fig.tight_layout()
    return savefig(fig, CH, "fig9-s1", out_dir)


def es_wd_linear(seed=0, N=30, D=20, sigma=1.0, rho=None):
    """A linear regression problem for Figure 9.S2: gradient descent from w = 0 against weight decay.
    Returns eigenvalues, test errors along the GD path (tau) and along the ridge path (lam = 1/(rho tau))."""
    rng = np.random.default_rng(seed)
    sc = np.logspace(0, -2, D)
    X = rng.standard_normal((N, D)) * sc
    th = rng.standard_normal(D)
    t = X @ th + sigma * rng.standard_normal(N)
    Hm = X.T @ X
    eig, U = np.linalg.eigh(Hm)
    rho = 1.0 / eig.max() if rho is None else rho
    wls = np.linalg.lstsq(X, t, rcond=None)[0]
    taus = np.unique(np.logspace(0, 6, 120).astype(int))
    risk = lambda w: float(((w - th) ** 2 * sc ** 2).sum() + sigma ** 2)  # noqa: E731
    zs = U.T @ wls
    gd = [risk(U @ (gd_filter(eig, rho, tau) * zs)) for tau in taus]
    rd = [risk(U @ (ridge_filter(eig, 1.0 / (rho * tau)) * zs)) for tau in taus]
    return eig, rho, taus, np.array(gd), np.array(rd)


def fig_9_s2(out_dir=None):
    """Figure 9.S2: early stopping against weight decay: the filters of Exercise 9.6, and matched test errors."""
    fig, axes = plt.subplots(1, 2, figsize=(9.0, 3.3))
    x = np.logspace(-2.5, 2.5, 400)          # x = rho eta_j tau
    tau = 1000
    eig = x / tau                            # with rho = 1
    g = gd_filter(eig, 1.0, tau)
    r = ridge_filter(eig, 1.0 / tau)
    ax = axes[0]
    ax.plot(x, g, color=common.BLUE, label=r"early stopping: $1-(1-\rho\eta_j)^\tau$")
    ax.plot(x, r, color=common.GREEN, ls="--", label=r"weight decay: $\eta_j/(\eta_j+\lambda)$, $\lambda=1/(\rho\tau)$")
    ax.plot(x, np.minimum(2 * r, 1), color=common.GREY, ls=":", lw=1, label=r"$2\times$ weight decay (upper bound)")
    ax.set_xscale("log")
    ax.set_xlabel(r"$\rho\,\eta_j\,\tau$ (eigenvalue in units of $1/(\rho\tau)$)")
    ax.set_ylabel(r"fraction of $w_j^\star$ kept")
    ax.legend(fontsize=7.5, loc="upper left")
    eigs, rho, taus, gd, rd = es_wd_linear()
    ax = axes[1]
    ax.plot(taus, gd, color=common.BLUE, label=r"gradient descent, step $\tau$")
    ax.plot(taus, rd, color=common.GREEN, ls="--", label=r"weight decay, $\lambda=1/(\rho\tau)$")
    ax.set_xscale("log")
    ax.set_xlabel(r"$\tau$")
    ax.set_ylabel("test error")
    ax.legend(fontsize=8)
    fig.tight_layout()
    return savefig(fig, CH, "fig9-s2", out_dir)


def fig_9_s3(out_dir=None):
    """Figure 9.S3: an ensemble of networks: members, committee, and committee error against M."""
    res = _cached("ch09_ensemble", lambda: ensemble_run(**ENS_DEFAULT))
    resb = _cached("ch09_ensemble_boot", lambda: ensemble_run(**dict(ENS_DEFAULT, bootstrap=True)))
    fig, axes = plt.subplots(1, 2, figsize=(9.0, 3.3))
    ax = axes[0]
    for p in res["preds"]:
        ax.plot(GRID, p, color=common.BLUE, lw=0.7, alpha=0.45)
    ax.plot(GRID, res["preds"].mean(0), color=common.RED, lw=2, label="committee (9.43)")
    ax.plot(GRID, np.sin(2 * np.pi * GRID), color=common.GREEN, lw=1.5, ls="--", label=r"$h(x)=\sin 2\pi x$")
    ax.plot(res["x"], res["t"], "o", mfc="none", color="k", ms=5)
    ax.set_ylim(-1.8, 1.8)
    ax.set_xlabel("x")
    ax.legend(fontsize=8, loc="lower left")
    ax = axes[1]
    for r_, lab, c in ((res, "different initialisations", common.BLUE), (resb, "bootstrap samples (bagging)", common.ORANGE)):
        M = len(r_["E"])
        ms = np.arange(1, M + 1)
        C = r_["C"]
        v = np.mean(np.diag(C))
        cbar = (C.sum() - np.trace(C)) / (M * (M - 1)) / v
        ax.plot(ms, committee_subset_errors(C), "o", color=c, ms=4.5, label=lab + r" ($\bar c$ = %.2f)" % cbar)
        ax.plot(ms, v * (cbar + (1 - cbar) / ms), color=c, lw=1.4)
        ax.plot(ms, v / ms, color=c, ls="--", lw=0.9, alpha=0.7)
    ax.set_xlabel("number of members M")
    ax.set_ylabel(r"$E_{\rm COM}$")
    ax.set_yscale("log")
    ax.legend(fontsize=7.5)
    fig.tight_layout()
    return savefig(fig, CH, "fig9-s3", out_dir)


def linear_dropout_sgd(X, t, rho, steps=20000, lr=0.002, seed=0):
    """Gradient descent on the dropout error (9.69) of a single-output linear model, a fresh Bernoulli(rho)
    mask R_ni at every step, with the iterates averaged over the second half of the run (they then estimate
    the minimiser of the expected error)."""
    rng = np.random.default_rng(seed)
    N, D = X.shape
    w = np.zeros(D)
    avg = np.zeros(D)
    for k in range(steps):
        Z = (rng.random((N, D)) < rho) * X
        w -= lr * 2 * Z.T @ (Z @ w - t)
        if k >= steps // 2:
            avg += w / (steps - steps // 2)
    return avg


S4_SCALES = np.array([0.5, 1.0, 2.0, 1.0])


def s4_linear_data(seed=3, N=60):
    rng = np.random.default_rng(seed)
    X = rng.standard_normal((N, 4)) * S4_SCALES
    X[:, 3] = 0.7 * X[:, 1] + 0.3 * rng.standard_normal(N)
    t = X @ np.array([1.5, -1.0, 0.5, 1.0]) + 0.5 * rng.standard_normal(N)
    return X, t


def fig_9_s4(out_dir=None):
    """Figure 9.S4: dropout: the minimiser of the expected error of a linear model, and weight scaling against MC dropout."""
    X, t = s4_linear_data()
    rhos = np.linspace(0.1, 1.0, 46)
    Wc = np.array([rho * linear_dropout_solution(X, t[:, None], rho)[0] for rho in rhos])
    rs = np.array([0.2, 0.4, 0.6, 0.8])
    Ws = np.array([r * linear_dropout_sgd(X, t, r, seed=int(10 * r)) for r in rs])
    res = _cached("ch09_dropout", lambda: dropout_run(**DROP_DEFAULT))
    fig, axes = plt.subplots(1, 2, figsize=(9.0, 3.3))
    ax = axes[0]
    cols = [common.RED, common.BLUE, common.GREEN, common.ORANGE]
    for i in range(4):
        ax.plot(rhos, Wc[:, i], color=cols[i], label=r"input %d ($\sum_n x_{ni}^2$ = %.0f)" % (i + 1, (X[:, i] ** 2).sum()))
        ax.plot(rs, Ws[:, i], "o", ms=4, color=cols[i], mfc="none")
    ax.set_xlabel(r"keep probability $\rho$")
    ax.set_ylabel(r"effective weight $\rho\,w_i$")
    ax.legend(fontsize=7, loc="upper left")
    ax = axes[1]
    ax.fill_between(GRID, res["mc_mean"] - 2 * res["mc_sd"], res["mc_mean"] + 2 * res["mc_sd"], color=common.BLUE, alpha=0.15, lw=0)
    ax.plot(GRID, res["mc_mean"], color=common.BLUE, lw=1.6, label="MC dropout, mean of %d masks" % DROP_DEFAULT["K"])
    ax.plot(GRID, res["ws"], color=common.RED, lw=1.4, ls="--", label=r"weight scaling ($\rho v_j$)")
    ax.plot(GRID, res["plain"], color=common.GREY, lw=1.0, label="same network, no dropout")
    ax.plot(GRID, np.sin(2 * np.pi * GRID), color=common.GREEN, lw=1.2, ls=":")
    ax.plot(res["x"], res["t"], "o", mfc="none", color="k", ms=5)
    ax.set_ylim(-2, 2)
    ax.set_xlabel("x")
    ax.legend(fontsize=7.5, loc="lower left")
    fig.tight_layout()
    return savefig(fig, CH, "fig9-s4", out_dir)


def _cached(name, fn):
    os.makedirs(CACHE_DIR, exist_ok=True)
    path = os.path.join(CACHE_DIR, name + ".npz")
    if os.path.exists(path):
        d = np.load(path, allow_pickle=True)
        return d["res"].item()
    res = fn()
    np.savez(path, res=np.array(res, dtype=object))
    return res


FIGURES = {"9.1": fig_9_1, "9.2": fig_9_2, "9.3": fig_9_3, "9.4": fig_9_4, "9.5": fig_9_5, "9.6": fig_9_6,
           "9.7": fig_9_7, "9.8": fig_9_8, "9.9": fig_9_9, "9.10": fig_9_10, "9.11": fig_9_11, "9.12": fig_9_12,
           "9.14": fig_9_14, "9.S1": fig_9_s1, "9.S2": fig_9_s2, "9.S3": fig_9_s3, "9.S4": fig_9_s4}


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