"""Murphy (2022), Chapter 14: Neural Networks for Images.

Companion code for Chapter 14 of K. P. Murphy, Probabilistic Machine Learning: An Introduction
(MIT Press, 2022; April 2025 draft), pp. 467-501, written from scratch with numpy, scipy and
matplotlib (PyTorch is used to train the small networks and to confirm the hand-written
convolution, normalisation and backpropagation code), to be read next to the lecture notes
(../ch14-neural-networks-images.html).

Methods
* Section 14.2, common layers: 1-d convolution and cross-correlation (14.2)-(14.4) (conv1d_full,
  xcorr1d), 2-d cross-correlation with padding, stride and dilation (14.5), (14.10), (14.12), (14.25)
  (xcorr2d, out_size), the matrix C of a convolution (14.8) (conv_matrix), multi-channel
  convolution (14.14), (14.15) and 1 x 1 convolution (14.16) (conv_nchw), max and average pooling
  (maxpool2d), batch, layer, instance and group normalisation (14.17)-(14.21) with their
  backward pass and the fused batch-norm identity (norm_nchw, bn_backward, fuse_bn).
* Section 14.3, architectures: LeNet5, AlexNet, ResNet-18 and DenseNet shapes and parameter counts
  (layer tables), receptive-field growth, residual and plain networks trained on digits.
* Section 14.4, other convolutions: dilated convolution (14.25) (as zero-inserted filter),
  transposed convolution (the book's trans_conv, and C^T), depthwise separable convolution (14.26)
  with its parameter and multiplication counts, and Wiener deconvolution.
* Section 14.5, other vision tasks: anchor boxes and intersection over union, the output sizes of
  the U-Net of Figure 14.30, a toy encoder-decoder segmentation network with and without skip
  connections.
* Section 14.6, inverting a CNN: the Langevin-type image update (14.28)-(14.30) with Gaussian and
  total-variation priors (14.31), activation maximisation, DeepDream-style feature amplification,
  and neural style transfer with Gram-matrix style loss (14.33)-(14.37) and adaptive instance
  normalisation (14.38), (14.39).

Data. MNIST (LeCun et al., 1998) is read through common.mnist(); the two sample photographs and
the digits come from scikit-learn and the course cache. The book's ImageNet-trained networks (AlexNet,
Inception, VGG) and its photographs are not available offline, so Figures 14.33, 14.35, 14.36 and
14.37 use a small two-convolution CNN trained here on MNIST (the same network is the one in the
browser demonstration), and Figures 14.38 and 14.41 use random-weight convolutional features and
simulated images; the captions say so. Heavy training is scaled down to CPU size (tens of
thousands of MNIST images, a few epochs).

Figures. Reproduced here: 14.1 (re-made with computed numbers), 14.3, 14.5, 14.6, 14.7, 14.8, 14.9,
14.11, 14.12, 14.14, 14.16 (as computed layer tables), 14.17, 14.23, 14.24, 14.25, 14.26, 14.27b,
14.33, 14.34, 14.35, 14.36, 14.37, 14.38, 14.41. Skipped, with the reason:
  14.2   digit templates (a book illustration of a CNN idea, nothing computed);
  14.4   1-d cross-correlation (a textbook sketch; the numbers are in Figure 14.3);
  14.10  a CNN with two convolutional layers (hand-drawn);
  14.13  a simple CNN (hand-drawn diagram; the layer sizes are in Figure 14.16);
  14.15  LeNet5 (hand-drawn diagram; the shapes are in Figure 14.16);
  14.18, 14.19, 14.20, 14.21, 14.22  Inception, GoogLeNet, residual and dense blocks, ResNet-18
         (hand-drawn diagrams; the shapes, parameter counts and gradient flow are computed in the
         supplementary figures 14.S1 and 14.S2);
  14.27a, 14.28, 14.31, 14.32, 14.39  photographs of detection, segmentation, depth and pose outputs;
  14.29, 14.30  the encoder-decoder and the U-Net (hand-drawn; the sizes are computed, and a toy
         encoder-decoder is trained in 14.S4);
  14.40  how neural style transfer works (hand-drawn flowchart).
Supplementary figures for the gaps filled in the notes:
  14.S1 gradient norms and training loss of plain and residual networks as the depth grows;
  14.S2 batch, layer, instance and group normalisation against the batch size (test accuracy and the
        noise of the batch statistics);
  14.S3 receptive-field growth for stacked, strided and dilated convolutions;
  14.S4 toy semantic segmentation with an encoder-decoder, with and without skip connections.
Run `python3 ch14_neural_networks_images.py --list`, `python3 ch14_neural_networks_images.py` (all
figures, about ten minutes) or `python3 ch14_neural_networks_images.py --fig 14.17`. Files go to
../img/ch14/; the data used by the browser demonstrations go to ../data/ch14-*.json.
"""
import json
import math
import os
import sys

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

import numpy as np

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 = 14
HERE = os.path.dirname(os.path.abspath(__file__))
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
CACHE_DIR = os.path.join(HERE, "cache")
os.makedirs(CACHE_DIR, exist_ok=True)


# =========================================================================== convolution in numpy
def out_size(n, k, p=0, s=1, r=1):
    """Output length of a convolution: floor((n + 2p - r(k-1) - 1)/s) + 1, equal to (14.10) for
    s = r = 1 and to (14.12) for r = 1 (the book writes floor((n + 2p - k + s)/s))."""
    return (n + 2 * p - r * (k - 1) - 1) // s + 1


def conv1d_full(x, w):
    """Convolution (14.2): flip w and drag it over x; full output of length len(x) + len(w) - 1."""
    x, w = np.asarray(x, float), np.asarray(w, float)
    z = np.zeros(len(x) + len(w) - 1)
    for i in range(len(x)):
        for j in range(len(w)):
            z[i + j] += x[i] * w[j]
    return z


def xcorr1d(x, w):
    """Cross-correlation (14.4), valid part: z_i = sum_u w_u x_{i+u}."""
    x, w = np.asarray(x, float), np.asarray(w, float)
    return np.array([np.dot(w, x[i:i + len(w)]) for i in range(len(x) - len(w) + 1)])


def xcorr2d(X, W, stride=1, pad=0, dil=1):
    """Single-channel 2-d cross-correlation (14.5) with zero padding, stride and dilation (14.25)."""
    X = np.pad(np.asarray(X, float), pad)
    W = np.asarray(W, float)
    kh, kw = W.shape
    Ho = (X.shape[0] - dil * (kh - 1) - 1) // stride + 1
    Wo = (X.shape[1] - dil * (kw - 1) - 1) // stride + 1
    Y = np.zeros((Ho, Wo))
    for i in range(Ho):
        for j in range(Wo):
            for u in range(kh):
                for v in range(kw):
                    Y[i, j] += W[u, v] * X[stride * i + dil * u, stride * j + dil * v]
    return Y


def xcorr2d_fast(X, W, stride=1, pad=0, dil=1):
    """The same as xcorr2d, vectorised over the output (used for images)."""
    X = np.pad(np.asarray(X, float), pad)
    W = np.asarray(W, float)
    kh, kw = W.shape
    Ho = (X.shape[0] - dil * (kh - 1) - 1) // stride + 1
    Wo = (X.shape[1] - dil * (kw - 1) - 1) // stride + 1
    Y = np.zeros((Ho, Wo))
    for u in range(kh):
        for v in range(kw):
            Y += W[u, v] * X[dil * u:dil * u + stride * (Ho - 1) + 1:stride, dil * v:dil * v + stride * (Wo - 1) + 1:stride]
    return Y


def conv_matrix(in_shape, W, stride=1, pad=0, dil=1):
    """The matrix C with  vec(Y) = C vec(X)  for the cross-correlation Y = W (*) X, as in (14.8)
    (rows: outputs in row-major order, columns: inputs in row-major order; padding is zero, so
    entries that would read the padding are dropped)."""
    H, Wd = in_shape
    kh, kw = W.shape
    Ho = out_size(H, kh, pad, stride, dil)
    Wo = out_size(Wd, kw, pad, stride, dil)
    C = np.zeros((Ho * Wo, H * Wd))
    for i in range(Ho):
        for j in range(Wo):
            for u in range(kh):
                for v in range(kw):
                    a, b = stride * i + dil * u - pad, stride * j + dil * v - pad
                    if 0 <= a < H and 0 <= b < Wd:
                        C[i * Wo + j, a * Wd + b] += W[u, v]
    return C


def trans_conv(X, K):
    """Transposed convolution as in the book's code of Section 14.4.2 (stride 1, no padding):
    every input pixel stamps a weighted copy of the kernel."""
    X, K = np.asarray(X, float), np.asarray(K, float)
    h, w = K.shape
    Y = np.zeros((X.shape[0] + h - 1, X.shape[1] + w - 1))
    for i in range(X.shape[0]):
        for j in range(X.shape[1]):
            Y[i:i + h, j:j + w] += X[i, j] * K
    return Y


def maxpool2d(X, k=2, stride=None, mode="max"):
    stride = stride or k
    X = np.asarray(X, float)
    Ho, Wo = (X.shape[0] - k) // stride + 1, (X.shape[1] - k) // stride + 1
    Y = np.zeros((Ho, Wo))
    for i in range(Ho):
        for j in range(Wo):
            patch = X[i * stride:i * stride + k, j * stride:j * stride + k]
            Y[i, j] = patch.max() if mode == "max" else patch.mean()
    return Y


def conv_nchw(x, W, b=None, stride=1, pad=0, dil=1):
    """Multi-channel convolution (14.15): x (N, C, H, W), W (D, C, kh, kw) (PyTorch layout, the
    book's (kh, kw, C, D) transposed), b (D,). Via a loop over the kernel taps."""
    x = np.pad(np.asarray(x, float), ((0, 0), (0, 0), (pad, pad), (pad, pad)))
    D, C, kh, kw = W.shape
    N, _, H, Wd = x.shape
    Ho = (H - dil * (kh - 1) - 1) // stride + 1
    Wo = (Wd - dil * (kw - 1) - 1) // stride + 1
    y = np.zeros((N, D, Ho, Wo))
    for u in range(kh):
        for v in range(kw):
            patch = x[:, :, dil * u:dil * u + stride * (Ho - 1) + 1:stride, dil * v:dil * v + stride * (Wo - 1) + 1:stride]
            y += np.einsum("nchw,dc->ndhw", patch, W[:, :, u, v])
    if b is not None:
        y += np.asarray(b)[None, :, None, None]
    return y


# =========================================================================== normalisation layers
def norm_nchw(z, kind="bn", groups=None, eps=1e-5, gamma=None, beta=None, stats=None):
    """Normalise a tensor z of shape (N, C, H, W) as in (14.17)-(14.21).

    kind: 'bn' pools over (N, H, W) for each channel; 'ln' over (C, H, W) for each example; 'in'
    over (H, W) for each example and channel; 'gn' over (C/groups, H, W) for each example and group.
    stats = (mu, var) overrides the batch statistics (batch norm at test time). Returns z_tilde,
    mu, var."""
    z = np.asarray(z, float)
    N, C, H, W = z.shape
    if kind == "gn":
        zg = z.reshape(N, groups, C // groups, H, W)
        mu = zg.mean(axis=(2, 3, 4), keepdims=True)
        var = zg.var(axis=(2, 3, 4), keepdims=True)
        zh = ((zg - mu) / np.sqrt(var + eps)).reshape(N, C, H, W)
    else:
        ax = {"bn": (0, 2, 3), "ln": (1, 2, 3), "in": (2, 3)}[kind]
        if stats is not None:
            mu, var = stats
        else:
            mu = z.mean(axis=ax, keepdims=True)
            var = z.var(axis=ax, keepdims=True)
        zh = (z - mu) / np.sqrt(var + eps)
    g = np.ones(C) if gamma is None else np.asarray(gamma, float)
    be = np.zeros(C) if beta is None else np.asarray(beta, float)
    return g[None, :, None, None] * zh + be[None, :, None, None], mu, var


def bn_backward(z, dout, gamma, eps=1e-5):
    """Gradient of batch norm (training mode) for z (N, C, H, W): returns dz, dgamma, dbeta.
    With zh the standardised input, sigma = sqrt(var + eps), dzh = gamma dout: dz = (dzh - mean(dzh) - zh mean(dzh zh)) / sigma."""
    N, C, H, W = z.shape
    mu = z.mean(axis=(0, 2, 3), keepdims=True)
    var = z.var(axis=(0, 2, 3), keepdims=True)
    sig = np.sqrt(var + eps)
    zh = (z - mu) / sig
    dzh = dout * gamma[None, :, None, None]
    dz = (dzh - dzh.mean(axis=(0, 2, 3), keepdims=True) - zh * (dzh * zh).mean(axis=(0, 2, 3), keepdims=True)) / sig
    return dz, (dout * zh).sum(axis=(0, 2, 3)), dout.sum(axis=(0, 2, 3))


def fuse_bn(W, b, mu, var, gamma, beta, eps=1e-5):
    """Fuse a frozen batch norm into the preceding dense layer  Wx + b: W' = diag(gamma/sigma) W,
    b' = gamma (b - mu)/sigma + beta (the identity below (14.20); W has one row per output unit)."""
    s = gamma / np.sqrt(var + eps)
    return W * s[:, None], s * (b - mu) + beta


# =========================================================================== data
def mnist_split(n_train=20000, n_test=10000, seed=0):
    """MNIST images as (N, 1, 28, 28) float32 in [0, 1]: a random subset of the training set and the
    full test set (or its first n_test images)."""
    Xtr, ytr = common.mnist(True)
    Xte, yte = common.mnist(False)
    rng = np.random.default_rng(seed)
    idx = rng.permutation(len(Xtr))[:n_train]
    f = lambda X: X.reshape(-1, 1, 28, 28).astype(np.float32)
    return f(Xtr[idx]), ytr[idx], f(Xte[:n_test]), yte[:n_test]


def sample_photos():
    """The two photographs shipped with scikit-learn (china.jpg, flower.jpg) as float arrays in [0, 1]."""
    from sklearn.datasets import load_sample_images
    d = load_sample_images()
    return {n.split("/")[-1].split(".")[0]: im.astype(float) / 255.0 for n, im in zip(d.filenames, d.images)}


def gray(im):
    return im @ np.array([0.299, 0.587, 0.114])


def resize_mean(a, f):
    """Block-mean downsampling of a 2-d (or H x W x 3) array by an integer factor f."""
    H, W = a.shape[:2]
    H, W = H - H % f, W - W % f
    a = a[:H, :W]
    if a.ndim == 2:
        return a.reshape(H // f, f, W // f, f).mean(axis=(1, 3))
    return a.reshape(H // f, f, W // f, f, a.shape[2]).mean(axis=(1, 3))


# =========================================================================== small figure helpers
def show_matrix(ax, M, title=None, fmt="%g", cmap="Blues", vmin=None, vmax=None, fs=8, hl=None, hlcolor=RED, lw=2.0,
                grid=True, xlabel=None, ylabel=None):
    """Draw a small matrix with its entries written in the cells; hl = (i0, j0, h, w) outlines a window."""
    M = np.asarray(M, float)
    lo = M.min() if vmin is None else vmin
    hi = M.max() if vmax is None else vmax
    span = (hi - lo) if hi > lo else 1.0
    ax.imshow(M, cmap=cmap, vmin=lo - 0.12 * span, vmax=hi, aspect="equal")
    for (i, j), v in np.ndenumerate(M):
        ax.text(j, i, fmt % v, ha="center", va="center", fontsize=fs, color="white" if (v - lo) / span > 0.55 else "black")
    if grid:
        ax.set_xticks(np.arange(-.5, M.shape[1], 1), minor=True)
        ax.set_yticks(np.arange(-.5, M.shape[0], 1), minor=True)
        ax.grid(which="minor", color="#888", lw=0.5)
        ax.tick_params(which="both", length=0)
    ax.set_xticks([])
    ax.set_yticks([])
    for s in ax.spines.values():
        s.set_visible(False)
    if hl is not None:
        i0, j0, h, w = hl
        ax.add_patch(plt.Rectangle((j0 - .5, i0 - .5), w, h, fill=False, ec=hlcolor, lw=lw))
    if title:
        ax.set_title(title, fontsize=9)
    if xlabel:
        ax.set_xlabel(xlabel, fontsize=8)
    if ylabel:
        ax.set_ylabel(ylabel, fontsize=8)


def imshow_gray(ax, im, title=None, vmin=0, vmax=1, cmap="gray_r"):
    ax.imshow(im, cmap=cmap, vmin=vmin, vmax=vmax, interpolation="nearest")
    ax.set_xticks([])
    ax.set_yticks([])
    if title:
        ax.set_title(title, fontsize=8.5)


# =========================================================================== small CNNs (torch for training, numpy for analysis)
def _torch():
    return common.torch_setup(seed=0, threads=1)


def small_cnn_module(torch):
    nn = torch.nn

    class SmallCNN(nn.Module):
        """conv(1->6, 5x5) - ReLU - maxpool 2 - conv(6->12, 5x5) - ReLU - maxpool 2 - dense(192->10)."""

        def __init__(self):
            super().__init__()
            self.conv1 = nn.Conv2d(1, 6, 5)
            self.conv2 = nn.Conv2d(6, 12, 5)
            self.fc = nn.Linear(192, 10)

        def forward(self, x):
            F = torch.nn.functional
            x = F.max_pool2d(F.relu(self.conv1(x)), 2)
            x = F.max_pool2d(F.relu(self.conv2(x)), 2)
            return self.fc(x.flatten(1))

    return SmallCNN()


def train_small_cnn(n_train=20000, epochs=3, seed=0, force=False):
    """Train the two-convolution network of Figures 14.33-14.37 (and of the browser demonstration) on
    MNIST; returns the parameters rounded to 4 decimals as float64 arrays and the test accuracy."""
    path = os.path.join(CACHE_DIR, "ch14_smallcnn.npz")
    if os.path.exists(path) and not force:
        z = np.load(path)
        return {k: z[k] for k in z.files if k != "acc"}, float(z["acc"])
    torch = _torch()
    torch.manual_seed(seed)
    Xtr, ytr, Xte, yte = mnist_split(n_train, 10000, seed)
    net = small_cnn_module(torch)
    opt = torch.optim.Adam(net.parameters(), lr=3e-3)
    Xt, yt = torch.tensor(Xtr), torch.tensor(ytr)
    g = torch.Generator().manual_seed(seed)
    for ep in range(epochs):
        perm = torch.randperm(len(Xt), generator=g)
        for i in range(0, len(Xt), 64):
            idx = perm[i:i + 64]
            opt.zero_grad()
            loss = torch.nn.functional.cross_entropy(net(Xt[idx]), yt[idx])
            loss.backward()
            opt.step()
    P = {"W1": net.conv1.weight, "b1": net.conv1.bias, "W2": net.conv2.weight, "b2": net.conv2.bias,
         "Wf": net.fc.weight, "bf": net.fc.bias}
    P = {k: np.round(v.detach().numpy().astype(np.float64), 4) for k, v in P.items()}
    acc = float((np.argmax(cnn_forward(P, Xte.astype(np.float64))[0], 1) == yte).mean())
    np.savez(path, acc=acc, **P)
    return P, acc


def _pool2(a):
    """2x2 max pool with stride 2 of (N, C, H, W); returns pooled values and a one-hot mask (first max wins)."""
    N, C, H, W = a.shape
    w = a.reshape(N, C, H // 2, 2, W // 2, 2).transpose(0, 1, 2, 4, 3, 5).reshape(N, C, H // 2, W // 2, 4)
    k = np.argmax(w, axis=-1)
    mask = np.zeros_like(w)
    np.put_along_axis(mask, k[..., None], 1.0, axis=-1)
    return np.take_along_axis(w, k[..., None], -1)[..., 0], mask


def _unpool2(d, mask):
    N, C, h, w = d.shape
    full = (mask * d[..., None]).reshape(N, C, h, w, 2, 2).transpose(0, 1, 2, 4, 3, 5)
    return full.reshape(N, C, 2 * h, 2 * w)


def cnn_forward(P, x):
    """Forward pass of the small CNN in float64 numpy for x of shape (N, 1, 28, 28); returns the logits
    and a cache holding every intermediate tensor (used by cnn_backward and by activation maximisation)."""
    a1 = conv_nchw(x, P["W1"], P["b1"])
    r1 = np.maximum(a1, 0)
    p1, m1 = _pool2(r1)
    a2 = conv_nchw(p1, P["W2"], P["b2"])
    r2 = np.maximum(a2, 0)
    p2, m2 = _pool2(r2)
    z = p2.reshape(len(x), -1) @ P["Wf"].T + P["bf"]
    return z, dict(x=x, a1=a1, r1=r1, p1=p1, m1=m1, a2=a2, r2=r2, p2=p2, m2=m2)


def cnn_backward(P, cache, dz=None, d_a2=None, d_a1=None):
    """Gradient with respect to the input pixels. dz (N, 10) is the gradient arriving at the logits; or
    d_a2 (N, 12, 8, 8) the gradient arriving at the second convolution's pre-activations; or d_a1
    (N, 6, 24, 24) the gradient arriving at the first convolution's pre-activations."""
    N = len(cache["x"])
    if d_a1 is None:
        if d_a2 is None:
            dp2 = (dz @ P["Wf"]).reshape(N, 12, 4, 4)
            d_a2 = _unpool2(dp2, cache["m2"]) * (cache["a2"] > 0)
        dp1 = np.zeros_like(cache["p1"])
        for u in range(5):
            for v in range(5):
                dp1[:, :, u:u + 8, v:v + 8] += np.einsum("dc,ndij->ncij", P["W2"][:, :, u, v], d_a2)
        d_a1 = _unpool2(dp1, cache["m1"]) * (cache["a1"] > 0)
    dx = np.zeros_like(cache["x"])
    for u in range(5):
        for v in range(5):
            dx[:, :, u:u + 24, v:v + 24] += np.einsum("dc,ndij->ncij", P["W1"][:, :, u, v], d_a1)
    return dx


def softmax(z):
    z = z - z.max(-1, keepdims=True)
    e = np.exp(z)
    return e / e.sum(-1, keepdims=True)


def log_softmax(z):
    z = z - z.max(-1, keepdims=True)
    return z - np.log(np.exp(z).sum(-1, keepdims=True))


# ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ total variation (14.31)
def tv(x):
    """Total-variation penalty (14.31) of images x (N, 1, H, W): sum of squared horizontal and vertical differences."""
    return ((x[..., 1:, :] - x[..., :-1, :]) ** 2).sum(axis=(1, 2, 3)) + ((x[..., :, 1:] - x[..., :, :-1]) ** 2).sum(axis=(1, 2, 3))


def tv_grad(x):
    g = np.zeros_like(x)
    dv = x[..., 1:, :] - x[..., :-1, :]
    dh = x[..., :, 1:] - x[..., :, :-1]
    g[..., 1:, :] += 2 * dv
    g[..., :-1, :] -= 2 * dv
    g[..., :, 1:] += 2 * dh
    g[..., :, :-1] -= 2 * dh
    return g


def mulberry32_normals(seed, n):
    """The generator of the browser demonstrations (mulberry32 + Box-Muller): n standard normals."""
    a = seed & 0xFFFFFFFF
    state = {"a": a, "spare": None}

    def u():
        state["a"] = (state["a"] + 0x6D2B79F5) & 0xFFFFFFFF
        x = state["a"]
        t = ((x ^ (x >> 15)) * (1 | x)) & 0xFFFFFFFF
        t = (t + (((t ^ (t >> 7)) * (61 | t)) & 0xFFFFFFFF)) & 0xFFFFFFFF ^ t
        return ((t ^ (t >> 14)) & 0xFFFFFFFF) / 4294967296.0

    out = []
    while len(out) < n:
        if state["spare"] is not None:
            out.append(state["spare"])
            state["spare"] = None
            continue
        x = 0.0
        while x == 0.0:
            x = u()
        r = math.sqrt(-2 * math.log(x))
        th = 2 * math.pi * u()
        state["spare"] = r * math.sin(th)
        out.append(r * math.cos(th))
    return np.array(out)


def invert_class(P, c, steps=100, eps1=0.1, eps2=1.0, eps3=0.0, prior="gauss", lam_tv=0.1, x0=None, seed=1, record=()):
    """Image that (approximately) maximises p(y=c | x) p(x): the update (14.28),

        x <- x + eps1 * grad log p(x) + eps2 * grad log p(y=c | x) + eps3 * noise,

    with log p(x) = -||x||^2/2 (gaussian, so the first term is -eps1 x as in (14.29)-(14.30)) or
    -lam_tv * TV(x) (total variation (14.31)). Starts from x0 (zeros by default). Returns the image
    (28, 28), the final p(y=c | x), and the list of recorded intermediate images."""
    x = np.zeros((1, 1, 28, 28)) if x0 is None else np.array(x0, float).reshape(1, 1, 28, 28)
    noise = mulberry32_normals(seed, steps * 784).reshape(steps, 1, 1, 28, 28) if eps3 > 0 else None
    snaps = {}
    for t in range(steps):
        if t in record:
            snaps[t] = x[0, 0].copy()
        z, cache = cnn_forward(P, x)
        p = softmax(z)
        e = np.zeros_like(p)
        e[0, c] = 1.0
        g_lik = cnn_backward(P, cache, dz=e - p)            # grad of log p(y=c | x) wrt x
        g_pri = -x if prior == "gauss" else (-lam_tv * tv_grad(x) if prior == "tv" else 0.0)
        x = x + eps1 * g_pri + eps2 * g_lik
        if noise is not None:
            x = x + eps3 * noise[t]
    z, _ = cnn_forward(P, x)
    for t in record:
        if t >= steps:
            snaps[t] = x[0, 0].copy()
    return x[0, 0], float(softmax(z)[0, c]), snaps


# =========================================================================== layer tables (Figures 14.15, 14.16, 14.21)
def net_table(spec, in_shape):
    """Walk a list of layer specs and return rows (name, output shape, parameters).

    spec items: ("conv", cout, k, stride, pad), ("pool", k, stride), ("fc", out), ("flatten",).
    in_shape = (C, H, W)."""
    C, H, W = in_shape
    rows, flat = [], None
    for item in spec:
        kind = item[0]
        if kind == "conv":
            _, co, k, s, p = item
            n = co * C * k * k + co
            H, W, C = out_size(H, k, p, s), out_size(W, k, p, s), co
            rows.append(("conv %dx%d (%d)" % (k, k, co) + (", s%d" % s if s > 1 else "") + (", p%d" % p if p else ""), (C, H, W), n))
        elif kind == "pool":
            _, k, s = item
            H, W = out_size(H, k, 0, s), out_size(W, k, 0, s)
            rows.append(("pool %dx%d, s%d" % (k, k, s), (C, H, W), 0))
        elif kind == "flatten":
            flat = C * H * W
            rows.append(("flatten", (flat,), 0))
        elif kind == "fc":
            n_in = flat if flat is not None else C * H * W
            rows.append(("dense (%d)" % item[1], (item[1],), n_in * item[1] + item[1]))
            flat = item[1]
    return rows


LENET5 = [("conv", 6, 5, 1, 2), ("pool", 2, 2), ("conv", 16, 5, 1, 0), ("pool", 2, 2), ("flatten",), ("fc", 120), ("fc", 84), ("fc", 10)]
ALEXNET = [("conv", 96, 11, 4, 1), ("pool", 3, 2), ("conv", 256, 5, 1, 2), ("pool", 3, 2), ("conv", 384, 3, 1, 1),
           ("conv", 384, 3, 1, 1), ("conv", 256, 3, 1, 1), ("pool", 3, 2), ("flatten",), ("fc", 4096), ("fc", 4096), ("fc", 1000)]


def resnet18_table(num_classes=1000, in_ch=3):
    """Parameter count of ResNet-18 (He et al. 2016, as drawn in Figure 14.21): a 7x7 stride-2 conv, batch norm,
    3x3 max pool, four stages of two basic blocks (the first block of stages 2-4 has stride 2 and a 1x1 projection),
    global average pooling and a dense layer. Returns (total parameters, number of weight layers, downsampling factor)."""
    n, layers = 0, 0

    def conv_bn(ci, co, k):
        return ci * co * k * k + 2 * co            # conv without bias + batch-norm scale and shift

    n += conv_bn(in_ch, 64, 7)
    layers += 1
    ci, factor = 64, 4                              # conv stride 2 and the max pool
    for si, co in enumerate((64, 128, 256, 512)):
        for b in range(2):
            stride = 2 if (si > 0 and b == 0) else 1
            n += conv_bn(ci, co, 3) + conv_bn(co, co, 3)
            layers += 2
            if stride == 2 or ci != co:
                n += conv_bn(ci, co, 1)             # the 1x1 projection on the skip path
            if stride == 2:
                factor *= 2
            ci = co
    n += ci * num_classes + num_classes
    layers += 1
    return n, layers, factor


def fig_14_16(out=None):
    """Layer tables of LeNet5 and AlexNet: output shapes and parameters (replaces the diagrams of Figure 14.16)."""
    fig, axes = plt.subplots(1, 2, figsize=(10.6, 4.4), gridspec_kw=dict(width_ratios=[1, 1.45]))
    for ax, spec, shape, title in [(axes[0], LENET5, (1, 28, 28), "LeNet5 (input 1x28x28)"),
                                   (axes[1], ALEXNET, (3, 224, 224), "AlexNet as drawn in Figure 14.16b (input 3x224x224)")]:
        rows = [r for r in net_table(spec, shape) if r[2] > 0]
        allrows = net_table(spec, shape)
        total = sum(r[2] for r in allrows)
        y = np.arange(len(rows))[::-1]
        ax.barh(y, [r[2] for r in rows], color=BLUE, alpha=0.85)
        ax.set_xscale("log")
        ax.set_yticks(y)
        ax.set_yticklabels([r[0] for r in rows], fontsize=8)
        for yi, r in zip(y, rows):
            ax.text(r[2] * 1.15, yi, "%s  (%s)" % (format(r[2], ","), "x".join(map(str, r[1]))), va="center", fontsize=7.5)
        ax.set_xlim(50, max(r[2] for r in rows) * 40)
        ax.set_xlabel("parameters (log scale); label: parameters (output shape)")
        ax.set_title("%s: %s parameters" % (title, format(total, ",")), fontsize=9.5)
    fig.tight_layout()
    savefig(fig, CH, "fig14-16", out)


# =========================================================================== Figures 14.1 - 14.14
def fig_14_1(out=None):
    """A matched filter on a dense layer is not translation invariant; a convolution is equivariant."""
    def image(col):
        im = np.zeros((6, 9))
        for (r, c) in [(0, 1), (1, 0), (1, 1), (1, 2), (2, 1)]:
            im[r + 1, c + col] = 1.0
        return im
    left, right = image(1), image(3)
    plus = np.array([[0, 1, 0], [1, 1, 1], [0, 1, 0]], float)
    template = image(1)                               # the dense unit's weight vector: the plus at the left position
    fig, axes = plt.subplots(2, 4, figsize=(9.2, 4.2), gridspec_kw=dict(width_ratios=[1.2, 1.2, 0.8, 1.2]))
    for row, (im, name) in enumerate([(left, "object at the left"), (right, "object shifted right by 2")]):
        r_dense = float((template * im).sum())
        resp = xcorr2d(im, plus, pad=1)
        imshow_gray(axes[row, 0], im, "input: %s" % name)
        imshow_gray(axes[row, 1], template, "dense unit: weights = template")
        axes[row, 2].bar([0], [r_dense], color=RED, width=0.5)
        axes[row, 2].set_ylim(0, 6)
        axes[row, 2].set_xticks([0])
        axes[row, 2].set_xticklabels(["dense\nresponse"], fontsize=8)
        axes[row, 2].text(0, r_dense + 0.15, "%g" % r_dense, ha="center", fontsize=9)
        imshow_gray(axes[row, 3], resp, "convolution response map (max = %g)" % resp.max(), vmin=0, vmax=5, cmap="Blues")
        i, j = np.unravel_index(np.argmax(resp), resp.shape)
        axes[row, 3].plot(j, i, "x", color=RED, ms=9)
    fig.tight_layout()
    savefig(fig, CH, "fig14-1", out)


def fig_14_3(out=None):
    """Convolution of x = [1,2,3,4] with w = [5,6,7]: flip w and drag it over x."""
    x, w = np.array([1, 2, 3, 4.]), np.array([5, 6, 7.])
    z = conv1d_full(x, w)
    lo, hi = -(len(w) - 1), len(z)                      # positions on the line: x is zero outside 0..3
    fig, axes = plt.subplots(len(z), 1, figsize=(6.4, 6.2), sharex=True)
    for k, ax in enumerate(axes):
        ax.set_xlim(lo - 0.6, hi - 0.4)
        ax.set_ylim(-0.1, 1.1)
        ax.axis("off")
        for i in range(lo, hi):
            inside = 0 <= i < len(x)
            ax.add_patch(plt.Rectangle((i - 0.45, 0.55), 0.9, 0.45, fc="#e8eefc" if inside else "white", ec="#888", lw=0.6))
            ax.text(i, 0.77, "%g" % (x[i] if inside else 0), ha="center", va="center", fontsize=9, color="black" if inside else "#aaa")
        for j in range(len(w)):                          # w flipped: at output k, w_j sits over x_{k-j}
            pos = k - j
            ax.add_patch(plt.Rectangle((pos - 0.45, 0.0), 0.9, 0.45, fc="#fde4e4", ec=RED, lw=0.8))
            ax.text(pos, 0.22, "%g" % w[j], ha="center", va="center", fontsize=9, color=RED)
        terms = ["x_{%d}w_{%d}" % (k - j, j) for j in range(len(w)) if 0 <= k - j < len(x)]
        ax.text(hi - 0.3, 0.55, "$z_{%d}=%s=%g$" % (k, "+".join(terms), z[k]), fontsize=8.5, va="center", ha="left")
    fig.suptitle("x = [1 2 3 4] (blue), w = [5 6 7] flipped and dragged (red); z = [%s]" % " ".join("%g" % v for v in z), fontsize=9)
    fig.subplots_adjust(right=0.60, top=0.93, hspace=0.05)
    savefig(fig, CH, "fig14-3", out)


def fig_14_5(out=None):
    """2-d cross-correlation of a 3x3 input with a 2x2 kernel (Equation 14.6-14.7)."""
    X = np.arange(9.).reshape(3, 3)
    W = np.array([[0, 1], [2, 3.]])
    Y = xcorr2d(X, W)
    fig, axes = plt.subplots(1, 3, figsize=(6.6, 2.4), gridspec_kw=dict(width_ratios=[3, 2, 2]))
    show_matrix(axes[0], X, "input $X$ (3x3)", fmt="%g", hl=(0, 0, 2, 2), fs=10)
    show_matrix(axes[1], W, "kernel $W$ (2x2)", fmt="%g", cmap="Reds", fs=10)
    show_matrix(axes[2], Y, "output $Y=W\\circledast X$", fmt="%g", fs=10, hl=(0, 0, 1, 1))
    axes[2].set_xlabel("$Y_{11}=0\\cdot0+1\\cdot1+2\\cdot3+3\\cdot4=19$", fontsize=8)
    fig.tight_layout()
    savefig(fig, CH, "fig14-5", out)


def digit_examples(classes=(7, 1, 4)):
    X, y = common.mnist(False)
    return [X[np.argmax(y == c)].reshape(28, 28) for c in classes]


DIAG = np.array([[2, -1, -1], [-1, 2, -1], [-1, -1, 2.]])          # responds to lines sloping down and to the right


def fig_14_6(out=None):
    """A 3x3 diagonal-edge filter applied to three digits: the response map lights up on matching strokes."""
    digs = digit_examples()
    fig, axes = plt.subplots(3, 3, figsize=(5.6, 5.4), gridspec_kw=dict(width_ratios=[1, 0.55, 1]))
    for r, d in enumerate(digs):
        resp = xcorr2d_fast(d, DIAG, pad=1)
        imshow_gray(axes[r, 0], d, "image" if r == 0 else None)
        show_matrix(axes[r, 1], DIAG, "filter" if r == 0 else None, fmt="%g", cmap="Reds", fs=8)
        im = axes[r, 2].imshow(resp, cmap="RdBu_r", vmin=-2.5, vmax=2.5, interpolation="nearest")
        axes[r, 2].set_xticks([])
        axes[r, 2].set_yticks([])
        if r == 0:
            axes[r, 2].set_title("response map", fontsize=8.5)
    fig.tight_layout()
    savefig(fig, CH, "fig14-6", out)


def fig_14_7(out=None):
    """Same convolution with zero padding: a 5x5 input, a 3x3 kernel, a 5x5 output."""
    X = np.array([[0, 1, 1, 1, 0], [0, 0, 1, 0, 0], [0, 0, 1, 0, 0], [0, 0, 1, 0, 0], [0, 1, 1, 1, 0.]])    # a letter "I"
    W = np.array([[0, 1, 0], [1, 1, 1], [0, 1, 0.]])
    Xp = np.pad(X, 1)
    Y = xcorr2d(X, W, pad=1)
    assert Y.shape == X.shape
    fig, axes = plt.subplots(1, 3, figsize=(8.0, 2.8), gridspec_kw=dict(width_ratios=[7, 3, 5]))
    show_matrix(axes[0], Xp, "padded input (7x7, zero border)", fmt="%g", fs=9, hl=(0, 0, 3, 3), vmax=1.5)
    show_matrix(axes[1], W, "kernel (3x3)", fmt="%g", cmap="Reds", fs=9)
    show_matrix(axes[2], Y, "output (5x5)", fmt="%g", fs=9, hl=(0, 0, 1, 1))
    fig.tight_layout()
    savefig(fig, CH, "fig14-7", out)


def fig_14_8(out=None):
    """Padding and stride: a 3x3 filter on a 5x7 input, same convolution (5x7 output) and stride 2 (3x4 output)."""
    H, W_, k, p = 5, 7, 3, 1
    fig, axes = plt.subplots(1, 2, figsize=(8.6, 3.5))
    for ax, s, tag in [(axes[0], 1, "(a) same convolution, stride 1"), (axes[1], 2, "(b) stride 2")]:
        Ho, Wo = out_size(H, k, p, s), out_size(W_, k, p, s)
        pad = np.full((H + 2 * p, W_ + 2 * p), 0.35)
        pad[p:-p, p:-p] = 0.0
        ax.imshow(pad, cmap="Greys", vmin=0, vmax=1, interpolation="nearest")
        ax.set_xticks(np.arange(-.5, W_ + 2 * p, 1), minor=True)
        ax.set_yticks(np.arange(-.5, H + 2 * p, 1), minor=True)
        ax.grid(which="minor", color="#999", lw=0.5)
        ax.tick_params(which="both", length=0, labelbottom=False, labelleft=False)
        for i in range(Ho):
            for j in range(Wo):
                ax.plot(s * j + 1, s * i + 1, "o", color=BLUE, ms=4)       # centre of the window of output (i, j)
        i0, j0 = (Ho - 1), (Wo - 1)
        ax.add_patch(plt.Rectangle((s * j0 - .5, s * i0 - .5), k, k, fill=False, ec=RED, lw=2))
        ax.add_patch(plt.Rectangle((-.5, -.5), k, k, fill=False, ec=GREEN, lw=2, ls="--"))
        ax.set_title("%s\noutput %dx%d = floor((%d+%d-%d+%d)/%d) x floor((%d+%d-%d+%d)/%d)" % (tag, Ho, Wo, H, 2 * p, k, s, s, W_, 2 * p, k, s, s), fontsize=8)
    fig.suptitle("white: input pixels, grey: zero padding, blue dots: window centres (one per output pixel)", fontsize=8.5, y=0.02)
    fig.tight_layout(rect=(0, 0.05, 1, 1))
    savefig(fig, CH, "fig14-8", out)


def fig_14_9(out=None):
    """Convolution of a two-channel input: convolve each channel with its own kernel and add."""
    X = np.stack([np.arange(9.).reshape(3, 3), np.arange(1., 10.).reshape(3, 3)])
    K = np.stack([np.array([[0, 1], [2, 3.]]), np.array([[1, 2], [3, 4.]])])
    Y = sum(xcorr2d(X[c], K[c]) for c in range(2))
    fig, axes = plt.subplots(1, 6, figsize=(10.6, 2.0), gridspec_kw=dict(width_ratios=[3, 3, 2, 2, 2, 2]))
    show_matrix(axes[0], X[0], "input channel 1", fs=9, hl=(0, 0, 2, 2))
    show_matrix(axes[1], X[1], "input channel 2", fs=9, hl=(0, 0, 2, 2))
    show_matrix(axes[2], K[0], "kernel 1", cmap="Reds", fs=9)
    show_matrix(axes[3], K[1], "kernel 2", cmap="Reds", fs=9)
    show_matrix(axes[4], xcorr2d(X[0], K[0]) * 0 + xcorr2d(X[0], K[0]), "ch.1 $\\circledast$ ker.1", fs=9)
    show_matrix(axes[5], Y, "sum over channels", fs=9, hl=(0, 0, 1, 1))
    fig.tight_layout()
    savefig(fig, CH, "fig14-9", out)


def fig_14_11(out=None):
    """1 x 1 convolution maps 3 channels to 2 at every pixel with the same 2x3 matrix."""
    rng = np.random.default_rng(0)
    X = rng.integers(0, 5, size=(3, 3, 3)).astype(float)               # (C, H, W)
    Wm = np.array([[1, 0, 2], [0, 1, -1.]])                              # (D, C): the 1x1xCxD filter
    Y = np.einsum("dc,chw->dhw", Wm, X)
    ref = conv_nchw(X[None], Wm[:, :, None, None])[0]
    assert np.allclose(Y, ref)
    fig, axes = plt.subplots(1, 6, figsize=(10.6, 2.0), gridspec_kw=dict(width_ratios=[3, 3, 3, 2.4, 3, 3]))
    for c in range(3):
        show_matrix(axes[c], X[c], "input channel %d" % (c + 1), fs=9)
    show_matrix(axes[3], Wm, "$1\\times1$ filter\n(2 x 3)", cmap="Reds", fs=9)
    for d in range(2):
        show_matrix(axes[4 + d], Y[d], "output channel %d" % (d + 1), fs=9)
    fig.tight_layout()
    savefig(fig, CH, "fig14-11", out)


def fig_14_12(out=None):
    """Max pooling: the 2x2, stride-1 example, and the (partial) invariance of pooling to small shifts."""
    X = np.arange(9.).reshape(3, 3)
    Yp = maxpool2d(X, 2, 1)
    fmap = np.zeros((8, 8))
    fmap[2:4, 2:4] = [[1.0, 0.6], [0.4, 0.9]]
    shifted = np.roll(fmap, 1, axis=1)
    fig, axes = plt.subplots(1, 5, figsize=(10.4, 2.5), gridspec_kw=dict(width_ratios=[3, 2, 4, 4, 4]))
    show_matrix(axes[0], X, "input (3x3)", fs=9, hl=(0, 0, 2, 2))
    show_matrix(axes[1], Yp, "2x2 max, stride 1", fs=9, hl=(0, 0, 1, 1))
    for ax, fm, t in [(axes[2], fmap, "feature map"), (axes[3], shifted, "shifted by one pixel")]:
        imshow_gray(ax, fm, t, cmap="Blues")
    p0, p1 = maxpool2d(fmap, 2, 2), maxpool2d(shifted, 2, 2)
    axes[4].axis("off")
    axes[4].text(0, 0.5, "max over the whole map:\n  %.1f and %.1f (same)\n2x2 pooling, stride 2:\n  outputs differ in %d of 16\n  cells" % (fmap.max(), shifted.max(), int((p0 != p1).sum())), fontsize=8.5, va="center")
    fig.tight_layout()
    savefig(fig, CH, "fig14-12", out)


def fig_14_14(out=None):
    """Which activations share mean and variance: batch, layer, instance and group normalisation.
    Each square is a (example, channel) pair; the spatial positions inside it are always pooled.
    The set is found by perturbation: add noise to one (example, channel) block and see whether the
    normalised output at the reference activation changes."""
    N, C, H, W = 4, 6, 3, 3
    rng = np.random.default_rng(1)
    z0 = rng.normal(size=(N, C, H, W))
    ref = (1, 2)
    kinds = [("bn", None, "batch norm"), ("ln", None, "layer norm"), ("in", None, "instance norm"), ("gn", 2, "group norm (2 groups)")]
    fig, axes = plt.subplots(1, 4, figsize=(10.4, 2.5))
    sets = {}
    base = {k: norm_nchw(z0, k, g)[0][ref[0], ref[1]] for k, g, _ in kinds}
    for ax, (k, g, name) in zip(axes, kinds):
        S = np.zeros((N, C))
        for n in range(N):
            for c in range(C):
                z = z0.copy()
                z[n, c] += rng.normal(size=(H, W)) * 0.5 + 1.0
                S[n, c] = float(np.abs(norm_nchw(z, k, g)[0][ref[0], ref[1]] - base[k]).max() > 1e-9)
        sets[k] = S
        ax.imshow(S, cmap="Blues", vmin=0, vmax=1.6, interpolation="nearest")
        ax.add_patch(plt.Rectangle((ref[1] - .5, ref[0] - .5), 1, 1, fill=False, ec=RED, lw=2))
        ax.set_xticks(np.arange(-.5, C, 1), minor=True)
        ax.set_yticks(np.arange(-.5, N, 1), minor=True)
        ax.grid(which="minor", color="#888", lw=0.5)
        ax.tick_params(which="both", length=0)
        ax.set_xticks(range(C))
        ax.set_xticklabels(range(1, C + 1), fontsize=8)
        ax.set_yticks(range(N))
        ax.set_yticklabels(range(1, N + 1), fontsize=8)
        ax.set_xlabel("channel $c$", fontsize=8.5)
        ax.set_ylabel("example $n$", fontsize=8.5)
        ax.set_title("%s: %d block(s) pooled" % (name, int(S.sum())), fontsize=8.5)
    fig.tight_layout()
    savefig(fig, CH, "fig14-14", out)
    return sets


# =========================================================================== Section 14.3: LeNet on MNIST (Figure 14.17)
def lenet_and_mlp(n_train=60000, epochs=2, seed=0, force=False):
    """Train LeNet5 (tanh, average pooling, Figure 14.16a) and an MLP with two hidden layers of 128 units on a
    random subset of MNIST; record the test accuracy every 1/4 epoch and the predictions after every epoch.
    Cached in cache/ch14_lenet.npz."""
    path = os.path.join(CACHE_DIR, "ch14_lenet.npz")
    if os.path.exists(path) and not force:
        z = np.load(path, allow_pickle=True)
        return {k: z[k] for k in z.files}
    torch = _torch()
    nn, F = torch.nn, torch.nn.functional
    Xtr, ytr, Xte, yte = mnist_split(n_train, 10000, seed)
    Xt, yt, Xv, yv = torch.tensor(Xtr), torch.tensor(ytr), torch.tensor(Xte), torch.tensor(yte)
    res = {}
    for name in ("lenet", "mlp"):
        torch.manual_seed(seed)
        if name == "lenet":
            net = nn.Sequential(nn.Conv2d(1, 6, 5, padding=2), nn.Tanh(), nn.AvgPool2d(2, 2), nn.Conv2d(6, 16, 5), nn.Tanh(),
                                nn.AvgPool2d(2, 2), nn.Flatten(), nn.Linear(400, 120), nn.Tanh(), nn.Linear(120, 84), nn.Tanh(), nn.Linear(84, 10))
        else:
            net = nn.Sequential(nn.Flatten(), nn.Linear(784, 128), nn.ReLU(), nn.Linear(128, 128), nn.ReLU(), nn.Linear(128, 10))
        opt = torch.optim.Adam(net.parameters(), lr=2e-3)
        g = torch.Generator().manual_seed(seed)
        accs, steps, preds = [], [], []
        n_steps = 0
        bs = 64
        per_epoch = (len(Xt) + bs - 1) // bs
        for ep in range(epochs):
            perm = torch.randperm(len(Xt), generator=g)
            for bi, i in enumerate(range(0, len(Xt), bs)):
                idx = perm[i:i + bs]
                opt.zero_grad()
                F.cross_entropy(net(Xt[idx]), yt[idx]).backward()
                opt.step()
                n_steps += 1
                if (bi + 1) % (per_epoch // 4) == 0 or bi + 1 == per_epoch:
                    with torch.no_grad():
                        pr = net(Xv).argmax(1)
                    accs.append(float((pr == yv).float().mean()))
                    steps.append(n_steps / per_epoch)
                    if bi + 1 == per_epoch:
                        preds.append(pr.numpy().copy())
        res[name + "_acc"], res[name + "_steps"], res[name + "_preds"] = np.array(accs), np.array(steps), np.array(preds)
    np.savez(path, **res)
    return res


def fig_14_17(out=None):
    """LeNet5 on MNIST: predictions on ten test digits after one and two epochs, and test accuracy against
    training for LeNet5 and a dense network (scaled down: two epochs)."""
    r = lenet_and_mlp()
    _, _, Xte, yte = mnist_split(60000, 10000, 0)
    p1, p2 = r["lenet_preds"]
    ok1 = np.where(p1 == yte)[0][:7]
    bad1 = np.where(p1 != yte)[0][:3]
    pick = np.sort(np.r_[ok1, bad1])
    fig = plt.figure(figsize=(10.4, 4.6))
    gs = fig.add_gridspec(2, 11, width_ratios=[1] * 10 + [0.0001], wspace=0.05, hspace=0.35, left=0.02, right=0.98, top=0.9, bottom=0.5)
    for row, (pr, lab) in enumerate([(p1, "(a) after 1 epoch"), (p2, "(b) after 2 epochs")]):
        for k, i in enumerate(pick):
            ax = fig.add_subplot(gs[row, k])
            ax.imshow(Xte[i, 0], cmap="gray_r")
            ax.set_xticks([])
            ax.set_yticks([])
            ax.set_title(str(pr[i]), fontsize=10, color=BLUE if pr[i] == yte[i] else RED, pad=2)
            if k == 0:
                ax.set_ylabel(lab, fontsize=8)
    ax = fig.add_axes([0.08, 0.08, 0.4, 0.32])
    ax.plot(r["lenet_steps"], 100 * r["lenet_acc"], "o-", color=RED, label="LeNet5 (conv, tanh, average pool)")
    ax.plot(r["mlp_steps"], 100 * r["mlp_acc"], "s-", color=BLUE, label="MLP, 2 x 128 ReLU")
    ax.set_xlabel("epochs")
    ax.set_ylabel("test accuracy (%)")
    ax.set_ylim(90, 100)
    ax.legend(fontsize=8, loc="lower right")
    ax2 = fig.add_axes([0.58, 0.1, 0.4, 0.3])
    n_params = {"LeNet5": 61706, "MLP 2x128": 784 * 128 + 128 + 128 * 128 + 128 + 1290}
    ax2.bar(list(n_params), list(n_params.values()), color=[RED, BLUE])
    for i, v in enumerate(n_params.values()):
        ax2.text(i, v, format(v, ","), ha="center", va="bottom", fontsize=8)
    ax2.set_ylabel("parameters")
    ax2.set_ylim(0, 140000)
    savefig(fig, CH, "fig14-17", out)


# =========================================================================== Section 14.4
def fig_14_23(out=None):
    """Dilated convolution with a 3x3 filter at rates 1, 2 and 3: which input pixels are read."""
    fig, axes = plt.subplots(1, 3, figsize=(9.2, 3.3))
    rng = np.random.default_rng(0)
    w = rng.normal(size=(3, 3))
    x = rng.normal(size=(9, 9))
    for ax, r in zip(axes, (1, 2, 3)):
        k_eff = r * (3 - 1) + 1
        wt = np.zeros((k_eff, k_eff))
        wt[::r, ::r] = w                                     # the zero-inserted ("with holes") filter
        a = xcorr2d(x, w, dil=r)
        b = xcorr2d(x, wt)
        assert np.allclose(a, b)
        grid = np.zeros((9, 9))
        c0 = 4 - (k_eff // 2)
        for u in range(3):
            for v in range(3):
                grid[c0 + r * u, c0 + r * v] = 1
        ax.imshow(grid, cmap="Blues", vmin=0, vmax=1.4, interpolation="nearest")
        ax.add_patch(plt.Rectangle((c0 - .5, c0 - .5), k_eff, k_eff, fill=False, ec=RED, lw=1.8))
        ax.set_xticks(np.arange(-.5, 9, 1), minor=True)
        ax.set_yticks(np.arange(-.5, 9, 1), minor=True)
        ax.grid(which="minor", color="#999", lw=0.5)
        ax.tick_params(which="both", length=0, labelbottom=False, labelleft=False)
        ax.set_title("rate $r=%d$: 9 taps spread over %dx%d" % (r, k_eff, k_eff), fontsize=9)
    fig.tight_layout()
    savefig(fig, CH, "fig14-23", out)


def tconv_matrix_check(X, K):
    """trans_conv(X, K) equals reshape(C^T vec(X)) where C is the matrix of the valid cross-correlation with K."""
    h, w = K.shape
    Ho, Wo = X.shape[0] + h - 1, X.shape[1] + w - 1
    C = conv_matrix((Ho, Wo), K)                      # maps (Ho x Wo) -> X.shape
    return (C.T @ X.ravel()).reshape(Ho, Wo)


def fig_14_24(out=None):
    """Transposed convolution of a 2x2 input with a 2x2 kernel: stamp one weighted copy of the kernel per input pixel."""
    X = np.array([[0, 1], [2, 3.]])
    K = np.array([[0, 1], [2, 3.]])
    Y = trans_conv(X, K)
    assert np.allclose(Y, tconv_matrix_check(X, K))
    fig, axes = plt.subplots(1, 6, figsize=(11.0, 2.2), gridspec_kw=dict(width_ratios=[2, 2, 3, 3, 3, 3]))
    show_matrix(axes[0], X, "input $X$", fs=10, cmap="Greens")
    show_matrix(axes[1], K, "kernel $K$", fs=10, cmap="Reds")
    # the four stamped copies, 0-3 in the book's picture: one per input pixel, in the first three panels, then sum
    stamps = []
    for (i, j) in [(0, 0), (0, 1), (1, 0), (1, 1)]:
        S = np.zeros((3, 3))
        S[i:i + 2, j:j + 2] = X[i, j] * K
        stamps.append(S)
    for ax, S, (i, j) in zip(axes[2:], stamps[1:] + [None], [(0, 1), (1, 0), (1, 1)]):
        pass
    show_matrix(axes[2], stamps[1] + stamps[2], "stamps of $X_{01}=1$, $X_{10}=2$", fs=9)
    show_matrix(axes[3], stamps[3], "stamp of $X_{11}=3$ (and $X_{00}=0$)", fs=9)
    show_matrix(axes[4], Y, "sum: output $Y$ (3x3)", fs=10)
    show_matrix(axes[5], tconv_matrix_check(X, K), "$C^{\\top}\\mathrm{vec}(X)$ reshaped", fs=10)
    fig.tight_layout()
    savefig(fig, CH, "fig14-24", out)


def gauss_kernel(size, sigma):
    ax = np.arange(size) - size // 2
    g = np.exp(-0.5 * (ax / sigma) ** 2)
    k = np.outer(g, g)
    return k / k.sum()


def circ_blur_filter(shape, k):
    """Fourier transform of the circular convolution with the (odd-sized, centred) kernel k on an image of the given shape."""
    pad = np.zeros(shape)
    kh, kw = k.shape
    pad[:kh, :kw] = k
    pad = np.roll(pad, (-(kh // 2), -(kw // 2)), axis=(0, 1))
    return np.fft.fft2(pad)


def deconvolution_demo(noise=0.003, size=7, sigma=1.5, lam=2e-3, seed=0):
    """Blur a grey photograph (circular boundary), then try to undo it: the naive inverse filter, Wiener
    deconvolution, and the transposed convolution C^T y (which is NOT the inverse)."""
    im = gray(sample_photos()["china"])
    x = resize_mean(im, 4)[10:106, 20:116]                           # 96 x 96 crop
    H = circ_blur_filter(x.shape, gauss_kernel(size, sigma))
    rng = np.random.default_rng(seed)
    clean = np.real(np.fft.ifft2(np.fft.fft2(x) * H))
    y = clean + noise * rng.normal(size=x.shape)
    naive = np.real(np.fft.ifft2(np.fft.fft2(y) / H))
    wiener = np.real(np.fft.ifft2(np.fft.fft2(y) * np.conj(H) / (np.abs(H) ** 2 + lam)))
    tconv = np.real(np.fft.ifft2(np.fft.fft2(y) * np.conj(H)))
    exact = np.real(np.fft.ifft2(np.fft.fft2(clean) / H))
    return dict(x=x, y=y, naive=naive, wiener=wiener, tconv=tconv, exact=exact, H=H)


def psnr(a, b):
    return 10 * np.log10(1.0 / np.mean((a - b) ** 2))


def fig_14_25(out=None):
    """Convolution, deconvolution and transposed convolution: blurring is undone only by (regularised) deconvolution."""
    d = deconvolution_demo()
    fig, axes = plt.subplots(1, 5, figsize=(11.2, 2.7))
    items = [("original", d["x"]), ("blurred + noise", d["y"]), ("transposed conv $C^{\\top}y$", d["tconv"] / d["H"][0, 0].real),
             ("naive inverse filter", np.clip(d["naive"], -0.5, 1.5)), ("Wiener deconvolution", d["wiener"])]
    for ax, (t, im) in zip(axes, items):
        imshow_gray(ax, im, "%s\nPSNR %.1f dB" % (t, psnr(d["x"], np.clip(im, 0, 1))) if t != "original" else t, cmap="gray")
    fig.tight_layout()
    savefig(fig, CH, "fig14-25", out)


def sep_counts(k, C, D, out_hw):
    """Weights and multiplications of a regular k x k conv and of a depthwise separable one (14.26), no biases."""
    reg_w = k * k * C * D
    sep_w = k * k * C + C * D
    reg_m = out_hw * out_hw * reg_w
    sep_m = out_hw * out_hw * sep_w
    return reg_w, sep_w, reg_m, sep_m


def fig_14_26(out=None):
    """Depthwise separable convolution: the book's 12x12x3 -> 8x8x256 example, and the saving as D and k vary."""
    fig, axes = plt.subplots(1, 2, figsize=(9.4, 3.4))
    reg_w, sep_w, reg_m, sep_m = sep_counts(5, 3, 256, 8)
    ax = axes[0]
    ax.bar([0, 1], [reg_w, sep_w], color=[BLUE, RED], width=0.55)
    ax.set_yscale("log")
    ax.set_xticks([0, 1])
    ax.set_xticklabels(["regular 5x5x3x256", "depthwise 5x5x3\n+ pointwise 1x1x3x256"], fontsize=8.5)
    for i, v in enumerate([reg_w, sep_w]):
        ax.text(i, v * 1.15, "%s weights\n%s mult." % (format(v, ","), format([reg_m, sep_m][i], ",")), ha="center", fontsize=8)
    ax.set_ylim(300, 1e5)
    ax.set_ylabel("weights (log scale)")
    ax.set_title("book's example, output 8x8x256", fontsize=9)
    ax = axes[1]
    D = np.arange(1, 513)
    for k, c in [(3, GREEN), (5, BLUE), (7, RED)]:
        ax.plot(D, k * k * D / (k * k + D), color=c, label="$k=%d$" % k)
        ax.axhline(k * k, color=c, lw=0.6, ls=":")
    ax.set_xlabel("output channels $D$")
    ax.set_ylabel("saving factor (multiplications)")
    ax.legend(fontsize=8)
    ax.set_title("regular / separable $=1/(1/D+1/k^2)$", fontsize=9)
    fig.tight_layout()
    savefig(fig, CH, "fig14-26", out)


def iou(a, b):
    """Intersection over union of boxes (x0, y0, x1, y1)."""
    iw = max(0.0, min(a[2], b[2]) - max(a[0], b[0]))
    ih = max(0.0, min(a[3], b[3]) - max(a[1], b[1]))
    inter = iw * ih
    return inter / ((a[2] - a[0]) * (a[3] - a[1]) + (b[2] - b[0]) * (b[3] - b[1]) - inter)


def anchors(H, W, grid, scales, ratios):
    """Anchor boxes centred on a grid x grid lattice: for scale s (fraction of the shorter side) and aspect ratio r = w/h,
    width s*min(H,W)*sqrt(r), height s*min(H,W)/sqrt(r)."""
    boxes = []
    for i in range(grid[0]):
        for j in range(grid[1]):
            cy, cx = (i + 0.5) * H / grid[0], (j + 0.5) * W / grid[1]
            for s in scales:
                for r in ratios:
                    w_, h_ = s * min(H, W) * math.sqrt(r), s * min(H, W) / math.sqrt(r)
                    boxes.append((cx - w_ / 2, cy - h_ / 2, cx + w_ / 2, cy + h_ / 2))
    return boxes


def fig_14_27(out=None):
    """Anchor boxes (Figure 14.27b): boxes of several scales and aspect ratios on a grid; those with large IoU with the
    ground-truth box (the pagoda) are the positive anchors that learn to predict it."""
    photo = resize_mean(sample_photos()["china"], 2)                # 213 x 320
    H, W = photo.shape[:2]
    gt = (35, 12, 165, 205)
    fig, axes = plt.subplots(1, 2, figsize=(9.6, 3.6))
    ax = axes[0]
    ax.imshow(photo)
    for s in (0.25, 0.5, 0.75):
        for r in (0.5, 1, 2):
            w_, h_ = s * H * math.sqrt(r), s * H / math.sqrt(r)
            col = {0.25: CYAN, 0.5: ORANGE, 0.75: MAGENTA}[s]
            ax.add_patch(plt.Rectangle((W / 2 - w_ / 2, H / 2 - h_ / 2), w_, h_, fill=False, ec=col, lw=1.0))
    ax.set_title("9 anchors at one location: 3 scales x 3 ratios", fontsize=9)
    ax.axis("off")
    ax = axes[1]
    ax.imshow(photo)
    allb = anchors(H, W, (4, 6), (0.25, 0.5, 0.75, 1.0), (0.5, 1, 2))
    ious = np.array([iou(b, gt) for b in allb])
    pos = np.where(ious >= 0.5)[0]
    for k in pos:
        b = allb[k]
        ax.add_patch(plt.Rectangle((b[0], b[1]), b[2] - b[0], b[3] - b[1], fill=False, ec=GREEN, lw=1.2))
    ax.add_patch(plt.Rectangle((gt[0], gt[1]), gt[2] - gt[0], gt[3] - gt[1], fill=False, ec=RED, lw=2.2))
    ax.set_title("%d anchors in all; %d have IoU >= 0.5 with the red box (green)" % (len(allb), len(pos)), fontsize=9)
    ax.set_xlim(0, W)
    ax.set_ylim(H, 0)
    ax.axis("off")
    fig.tight_layout()
    savefig(fig, CH, "fig14-27", out)


# =========================================================================== Section 14.6: inverting a CNN
INV_GAUSS = dict(prior="gauss", eps1=0.05, eps2=0.5, steps=200)
INV_TV = dict(prior="tv", eps1=0.05, lam_tv=0.5, eps2=0.5, steps=200)


def fig_14_33(out=None):
    """Images that maximise p(y=c | x) under a Gaussian prior, from the update (14.30) with a blank start
    (small CNN trained on MNIST; the book uses ImageNet networks)."""
    P, acc = train_small_cnn()
    fig, axes = plt.subplots(2, 5, figsize=(8.0, 3.7))
    for c in range(10):
        x, p, _ = invert_class(P, c, **INV_GAUSS)
        ax = axes[c // 5, c % 5]
        imshow_gray(ax, x, "class %d, $p=%.2f$" % (c, p), vmin=None, vmax=None)
        ax.images[0].set_clim(np.percentile(x, 1), np.percentile(x, 99))
    fig.tight_layout()
    savefig(fig, CH, "fig14-33", out)


def fig_14_35(out=None):
    """The same with a total-variation prior (14.31): smoother, more stroke-like images."""
    P, acc = train_small_cnn()
    fig, axes = plt.subplots(2, 5, figsize=(8.0, 3.7))
    for c in range(10):
        x, p, _ = invert_class(P, c, **INV_TV)
        ax = axes[c // 5, c % 5]
        imshow_gray(ax, x, "class %d, $p=%.2f$" % (c, p), vmin=None, vmax=None)
        ax.images[0].set_clim(np.percentile(x, 1), np.percentile(x, 99))
    fig.tight_layout()
    savefig(fig, CH, "fig14-35", out)


def fig_14_34(out=None):
    """Total variation of an image: horizontal and vertical differences (Figure 14.34), and TV of the
    original, a noisy and a blurred version."""
    im = gray(sample_photos()["china"])
    x = resize_mean(im, 4)[10:106, 20:116]
    rng = np.random.default_rng(0)
    noisy = np.clip(x + 0.1 * rng.normal(size=x.shape), 0, 1)
    H = circ_blur_filter(x.shape, gauss_kernel(9, 2.0))
    blur = np.real(np.fft.ifft2(np.fft.fft2(x) * H))
    tvs = [float(tv(a[None, None])[0]) for a in (x, noisy, blur)]
    fig, axes = plt.subplots(1, 6, figsize=(11.6, 2.4))
    imshow_gray(axes[0], x, "(a) image", cmap="gray")
    imshow_gray(axes[1], x[:, 1:] - x[:, :-1], "(b) horizontal deltas", vmin=-0.3, vmax=0.3, cmap="RdBu_r")
    imshow_gray(axes[2], x[1:] - x[:-1], "(c) vertical deltas", vmin=-0.3, vmax=0.3, cmap="RdBu_r")
    for ax, a, t, v in zip(axes[3:], (x, noisy, blur), ("original", "+ noise", "blurred"), tvs):
        imshow_gray(ax, a, "%s: TV = %.0f" % (t, v), cmap="gray")
    fig.tight_layout()
    savefig(fig, CH, "fig14-34", out)
    return tvs


def act_max(P, kind, idx, steps=120, eta=0.05, eps1=0.02, lam_tv=0.02, seed=3):
    """Activation maximisation: gradient ascent on the pixels to raise the mean activation of one unit
    (kind 'conv1' or 'conv2': the mean ReLU output of channel idx over all positions; 'logit': logit idx),
    with a weight-decay (Gaussian-prior) term and a total-variation term. The gradient is divided by its
    root-mean-square value, so eta is the step size in pixel units."""
    x = 0.1 * mulberry32_normals(seed, 784).reshape(1, 1, 28, 28)
    for _ in range(steps):
        z, cache = cnn_forward(P, x)
        if kind == "conv1":
            d = np.zeros_like(cache["a1"])
            d[:, idx] = (cache["a1"][:, idx] > 0) / 576.0
            g = cnn_backward(P, cache, d_a1=d)
        elif kind == "conv2":
            d = np.zeros_like(cache["a2"])
            d[:, idx] = (cache["a2"][:, idx] > 0) / 64.0
            g = cnn_backward(P, cache, d_a2=d)
        else:
            e = np.zeros((1, 10))
            e[0, idx] = 1.0
            g = cnn_backward(P, cache, dz=e)
        x = x + eta * g / (np.sqrt((g ** 2).mean()) + 1e-12) - eps1 * x - lam_tv * tv_grad(x)
    return x[0, 0]


def fig_14_36(out=None):
    """What do the units of a CNN respond to? Optimal stimuli (activation maximisation with a TV prior) for the
    channels of the first and second convolution and for the ten logits of the small MNIST CNN."""
    P, acc = train_small_cnn()
    rows = [("conv1", 6, "conv 1 (5x5, 6 channels)"), ("conv2", 12, "conv 2 (5x5, 12 channels)"), ("logit", 10, "logits (classes 0-9)")]
    fig, axes = plt.subplots(3, 12, figsize=(11.2, 3.5))
    for r, (kind, n, name) in enumerate(rows):
        for j in range(12):
            ax = axes[r, j]
            if j < n:
                x = act_max(P, kind, j)
                imshow_gray(ax, x, None, vmin=None, vmax=None, cmap="gray_r")
                ax.images[0].set_clim(np.percentile(x, 1), np.percentile(x, 99))
            else:
                ax.axis("off")
        axes[r, 0].set_ylabel(name, fontsize=7, rotation=0, ha="right", va="center", labelpad=4)
    fig.subplots_adjust(left=0.13, right=0.995, wspace=0.05, hspace=0.05)
    savefig(fig, CH, "fig14-36", out)


def deep_dream(P, x0, steps=50, lr=0.02, record=(0, 10, 50)):
    """DeepDream-style amplification: gradient ascent on  L(x) = mean over positions and channels of the squared
    second-convolution activation, with the gradient scaled by its mean absolute value."""
    x = np.array(x0, float).reshape(1, 1, 28, 28)
    snaps = {}
    for t in range(steps + 1):
        z, cache = cnn_forward(P, x)
        if t in record:
            snaps[t] = (x[0, 0].copy(), float((cache["r2"] ** 2).mean()))
        if t == steps:
            break
        d = 2 * cache["r2"] / cache["r2"].size * (cache["a2"] > 0) * 100.0
        g = cnn_backward(P, cache, d_a2=d)
        x = x + lr * g / (np.abs(g).mean() + 1e-12)
    return snaps


def fig_14_37(out=None):
    """DeepDream on the small CNN: starting from a digit, amplify the features of the second convolutional layer."""
    P, acc = train_small_cnn()
    X, y = common.mnist(False)
    x0 = X[np.argmax(y == 5)].reshape(28, 28)
    snaps = deep_dream(P, x0)
    fig, axes = plt.subplots(1, 3, figsize=(7.2, 2.6))
    for ax, t in zip(axes, (0, 10, 50)):
        im, L = snaps[t]
        imshow_gray(ax, im, "iteration %d, mean activation$^2$ %.2f" % (t, L), vmin=None, vmax=None)
        ax.images[0].set_clim(min(0.0, np.percentile(im, 1)), max(1.0, np.percentile(im, 99)))
    fig.tight_layout()
    savefig(fig, CH, "fig14-37", out)


# ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ neural style transfer (Figures 14.38, 14.41)
def kandinsky_style(size=96, seed=3):
    """A synthetic abstract 'painting' (coloured discs, rings and black lines on a cream ground) used as the style image."""
    rng = np.random.default_rng(seed)
    yy, xx = np.mgrid[0:size, 0:size].astype(float)
    im = np.ones((size, size, 3)) * np.array([0.95, 0.9, 0.75])
    pal = np.array([[0.85, 0.15, 0.15], [0.15, 0.25, 0.75], [0.95, 0.8, 0.1], [0.1, 0.1, 0.1], [0.2, 0.6, 0.3]])
    for _ in range(14):
        cx, cy, r = rng.uniform(0, size, 2).tolist() + [rng.uniform(4, 14)]
        col = pal[rng.integers(5)]
        d = np.hypot(xx - cx, yy - cy)
        im[d < r] = col
        im[(d > r) & (d < r + 1.6)] = pal[3]
    for _ in range(9):
        th, c0 = rng.uniform(0, np.pi), rng.uniform(0, size)
        dist = np.abs((xx - size / 2) * np.sin(th) - (yy - size / 2) * np.cos(th) - (c0 - size / 2))
        im[dist < 1.0] = pal[3]
    return im


def style_transfer(content, style, steps=250, lam_c=1.0, lam_s=30.0, lam_tv=1e-3, lr=0.03, seed=0):
    """Neural style transfer (14.33)-(14.37): minimise  lam_tv TV(x) + lam_c L_content + lam_s L_style  over the pixels,
    starting from the content image, by Adam. The features are those of a fixed random-weight convolutional network
    (three 3x3 convolutions with 16, 32 and 64 channels, ReLU, 2x2 average pooling after the first two): the book
    uses a trained image classifier. Each term is divided by the squared norm of its target, so the weights are
    comparable. content and style are (H, W, 3) arrays in [0, 1]. Returns the output image and the loss history."""
    torch = _torch()
    nn, F = torch.nn, torch.nn.functional
    g = torch.Generator().manual_seed(seed)
    ws = []
    for ci, co in [(3, 16), (16, 32), (32, 64)]:
        ws.append(torch.randn(co, ci, 3, 3, generator=g) * math.sqrt(2.0 / (ci * 9)))

    def feats(x):
        out, h = [], x
        for i, w in enumerate(ws):
            h = F.relu(F.conv2d(h, w, padding=1))
            out.append(h)
            if i < 2:
                h = F.avg_pool2d(h, 2)
        return out

    def gram(f):
        n, c, hh, ww = f.shape
        v = f.reshape(n, c, hh * ww)
        return v @ v.transpose(1, 2) / (hh * ww)

    tt = lambda a: torch.tensor(a.transpose(2, 0, 1)[None], dtype=torch.float32)
    xc, xs = tt(content), tt(style)
    with torch.no_grad():
        fc, fs = feats(xc), feats(xs)
        Gs = [gram(f) for f in fs]
    x = xc.clone().requires_grad_(True)
    opt = torch.optim.Adam([x], lr=lr)
    hist = []
    for t in range(steps):
        opt.zero_grad()
        fx = feats(x)
        Lc = ((fx[2] - fc[2]) ** 2).sum() / (fc[2] ** 2).sum()
        Ls = sum(((gram(f) - G) ** 2).sum() / (G ** 2).sum() for f, G in zip(fx, Gs))
        Ltv = ((x[..., 1:, :] - x[..., :-1, :]) ** 2).sum() + ((x[..., :, 1:] - x[..., :, :-1]) ** 2).sum()
        loss = lam_c * Lc + lam_s * Ls + lam_tv * Ltv
        loss.backward()
        opt.step()
        hist.append((float(Lc.detach()), float(Ls.detach()), float(Ltv.detach())))
    return np.clip(x.detach().numpy()[0].transpose(1, 2, 0), 0, 1), np.array(hist)


def fig_14_38(out=None):
    """Neural style transfer: content image (a photograph), style image (a synthetic abstract painting) and the result.
    Random-weight convolutional features stand in for the trained classifier of the book."""
    path = os.path.join(CACHE_DIR, "ch14_style.npz")
    content = resize_mean(sample_photos()["china"], 4)[:96, 8:152]
    style = kandinsky_style()
    if os.path.exists(path):
        z = np.load(path)
        outim, hist = z["out"], z["hist"]
    else:
        outim, hist = style_transfer(content, style)
        np.savez(path, out=outim, hist=hist)
    fig, axes = plt.subplots(1, 4, figsize=(11.0, 2.7), gridspec_kw=dict(width_ratios=[1.5, 1, 1.5, 1.2]))
    axes[0].imshow(content)
    axes[0].set_title("(a) content image", fontsize=9)
    axes[1].imshow(style)
    axes[1].set_title("(b) style image", fontsize=9)
    axes[2].imshow(outim)
    axes[2].set_title("(c) output after %d steps" % len(hist), fontsize=9)
    for ax in axes[:3]:
        ax.axis("off")
    ax = axes[3]
    ax.semilogy(hist[:, 0], color=BLUE, label="content")
    ax.semilogy(hist[:, 1], color=RED, label="style")
    ax.set_xlabel("Adam step")
    ax.set_title("normalised losses", fontsize=9)
    ax.legend(fontsize=8)
    fig.tight_layout()
    savefig(fig, CH, "fig14-38", out)


def spiky_image(colour, centres, size=32, seed=0):
    """A grey 32x32 image with 10x10 patches filled with a high-frequency 'spiky' texture of the given colour."""
    rng = np.random.default_rng(seed)
    im = np.ones((size, size, 3)) * 0.55
    chk = (np.add.outer(np.arange(10), np.arange(10)) % 2) * 2 - 1.0
    for (r, c) in centres:
        tex = 1 + 0.35 * chk * (0.6 + 0.4 * rng.random((10, 10)))
        im[r:r + 10, c:c + 10] = np.clip(np.array(colour)[None, None] * tex[..., None], 0, 1)
    return im


def detector_maps(im):
    """Three hand-made feature maps: green detector, spikiness detector, brown detector (all non-negative)."""
    R, G, B = im[..., 0], im[..., 1], im[..., 2]
    green = np.maximum(G - 0.5 * (R + B) - 0.05, 0)
    brown = np.maximum(R - B - 0.1, 0) * (G < R)
    g = gray(im)
    lap = np.abs(4 * g[1:-1, 1:-1] - g[:-2, 1:-1] - g[2:, 1:-1] - g[1:-1, :-2] - g[1:-1, 2:])
    spiky = np.zeros_like(g)
    spiky[1:-1, 1:-1] = lap
    return np.stack([green, spiky, brown])


def gram_matrix(f):
    """Gram matrix (14.35) of a (C, H, W) feature map: (1/(HW)) sum_{h,w} f_c(h,w) f_d(h,w)."""
    C = f.shape[0]
    v = f.reshape(C, -1)
    return v @ v.T / v.shape[1]


def fig_14_41(out=None):
    """Style as co-occurrence statistics: three images with green spiky, green spiky and brown spiky patches, three
    detectors (green, spiky, brown), and the 3x3 Gram matrices (14.35); the first two images have similar Gram matrices."""
    spec = [((0.25, 0.65, 0.2), [(3, 4), (18, 17)], 1), ((0.25, 0.65, 0.2), [(5, 19), (20, 4)], 2), ((0.55, 0.35, 0.15), [(4, 18), (18, 6)], 3)]
    ims = [spiky_image(c, ctr, seed=s) for c, ctr, s in spec]
    Gs = [gram_matrix(detector_maps(im)) for im in ims]
    d12, d13 = np.linalg.norm(Gs[0] - Gs[1]), np.linalg.norm(Gs[0] - Gs[2])
    fig, axes = plt.subplots(2, 3, figsize=(7.8, 5.0))
    for k in range(3):
        axes[0, k].imshow(ims[k])
        axes[0, k].set_title("image %d" % (k + 1), fontsize=9)
        axes[0, k].axis("off")
        show_matrix(axes[1, k], Gs[k], None, fmt="%.2f", fs=9, vmin=0, vmax=0.15)
        axes[1, k].set_xticks([0, 1, 2])
        axes[1, k].set_xticklabels(["green", "spiky", "brown"], fontsize=7)
        axes[1, k].set_yticks([0, 1, 2])
        axes[1, k].set_yticklabels(["green", "spiky", "brown"], fontsize=7)
        axes[1, k].tick_params(length=0)
    fig.suptitle("Gram matrices $G_{cd}$; $\\|G_1-G_2\\|_F=%.3f$, $\\|G_1-G_3\\|_F=%.3f$" % (d12, d13), fontsize=9)
    fig.tight_layout()
    savefig(fig, CH, "fig14-41", out)
    return d12, d13


# =========================================================================== supplementary experiments
# ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 14.S1: plain vs residual networks
def _resnet_like(torch, kind, n_blocks, width=8):
    """A small image classifier on 14x14 digits: stem conv-BN-ReLU, n_blocks blocks, global average pooling, dense.
    kind 'plain': x <- relu(BN(conv(relu(BN(conv x)))))   (two convolutions, no skip);
    kind 'post':  x <- relu(x + BN(conv(relu(BN(conv x)))))   (the residual block of Figure 14.20, (14.22));
    kind 'pre':   x <- x + conv(relu(BN(conv(relu(BN x)))))  (the pre-activation block, (14.23))."""
    nn = torch.nn

    class Block(nn.Module):
        def __init__(self):
            super().__init__()
            self.c1 = nn.Conv2d(width, width, 3, padding=1, bias=False)
            self.b1 = nn.BatchNorm2d(width)
            self.c2 = nn.Conv2d(width, width, 3, padding=1, bias=False)
            self.b2 = nn.BatchNorm2d(width)
            self.b0 = nn.BatchNorm2d(width)

        def forward(self, x):
            F = torch.nn.functional
            if kind == "plain":
                return F.relu(self.b2(self.c2(F.relu(self.b1(self.c1(x))))))
            if kind == "post":
                return F.relu(x + self.b2(self.c2(F.relu(self.b1(self.c1(x))))))
            return x + self.c2(F.relu(self.b1(self.c1(F.relu(self.b0(x))))))

    class Net(nn.Module):
        def __init__(self):
            super().__init__()
            self.stem = nn.Sequential(nn.Conv2d(1, width, 3, padding=1, bias=False), nn.BatchNorm2d(width), nn.ReLU())
            self.blocks = nn.ModuleList([Block() for _ in range(n_blocks)])
            self.head = nn.Linear(width, 10)

        def forward(self, x, keep=None):
            x = self.stem(x)
            for b in self.blocks:
                x = b(x)
                if keep is not None:
                    x.retain_grad()
                    keep.append(x)
            return self.head(x.mean(dim=(2, 3)))

    return Net()


def residual_experiment(force=False):
    """Gradient norms at initialisation and training loss after 300 steps for plain, post-activation and
    pre-activation networks of 2, 8 and 24 blocks (48 convolutions at the deepest), on 14x14 downsampled digits."""
    path = os.path.join(CACHE_DIR, "ch14_resnet.npz")
    if os.path.exists(path) and not force:
        z = np.load(path)
        return {k: z[k] for k in z.files}
    torch = _torch()
    F = torch.nn.functional
    Xtr, ytr, Xte, yte = mnist_split(4000, 1000, 1)
    down = lambda X: torch.tensor(X.reshape(-1, 1, 14, 2, 14, 2).mean(axis=(3, 5)))
    Xt, Xv = down(Xtr), down(Xte)
    yt, yv = torch.tensor(ytr), torch.tensor(yte)
    res = {}
    for kind in ("plain", "post", "pre"):
        for nb in (2, 8, 24):
            torch.manual_seed(0)
            net = _resnet_like(torch, kind, nb)
            keep = []
            net.train()
            loss = F.cross_entropy(net(Xt[:128], keep), yt[:128])
            loss.backward()
            res["gn_%s_%d" % (kind, nb)] = np.array([float(k.grad.norm()) for k in keep])
            opt = torch.optim.Adam(net.parameters(), lr=3e-3)
            g = torch.Generator().manual_seed(0)
            losses = []
            for step in range(300):
                idx = torch.randint(0, len(Xt), (64,), generator=g)
                opt.zero_grad()
                l = F.cross_entropy(net(Xt[idx]), yt[idx])
                l.backward()
                opt.step()
                losses.append(float(l))
            net.eval()
            with torch.no_grad():
                acc = float((net(Xv).argmax(1) == yv).float().mean())
            res["loss_%s_%d" % (kind, nb)] = np.array(losses)
            res["acc_%s_%d" % (kind, nb)] = np.array(acc)
    np.savez(path, **res)
    return res


def fig_14_S1(out=None):
    """Plain against residual networks: (a) the gradient norm at each block output (depth 24, at initialisation);
    (b) training loss against the number of blocks."""
    r = residual_experiment()
    fig, axes = plt.subplots(1, 3, figsize=(10.8, 3.2))
    cols = {"plain": RED, "post": BLUE, "pre": GREEN}
    names = {"plain": "plain (no skip)", "post": "residual, $\\varphi(x+F(x))$", "pre": "pre-activation, $x+F(x)$"}
    ax = axes[0]
    for kind in cols:
        g = r["gn_%s_24" % kind]
        ax.semilogy(np.arange(1, 25), g, "o-", ms=3, color=cols[kind], label=names[kind])
    ax.set_xlabel("block $l$ (of 24)")
    ax.set_ylabel("$\\|\\partial L/\\partial x_l\\|$ at initialisation")
    ax.legend(fontsize=7.5)
    ax = axes[1]
    for kind in cols:
        for nb, ls in [(2, ":"), (8, "--"), (24, "-")]:
            l = r["loss_%s_%d" % (kind, nb)]
            ax.plot(np.convolve(l, np.ones(20) / 20, mode="valid"), ls, color=cols[kind], lw=1.3)
    ax.set_xlabel("training step")
    ax.set_ylabel("training loss (moving average)")
    ax.set_title("dotted: 2 blocks, dashed: 8, solid: 24", fontsize=8.5)
    ax = axes[2]
    for kind in cols:
        ax.plot([2, 8, 24], [100 * float(r["acc_%s_%d" % (kind, nb)]) for nb in (2, 8, 24)], "o-", color=cols[kind], label=names[kind])
    ax.set_xlabel("number of blocks")
    ax.set_ylabel("test accuracy (%)")
    ax.set_xscale("log")
    ax.set_xticks([2, 8, 24])
    ax.set_xticklabels(["2", "8", "24"])
    fig.tight_layout()
    savefig(fig, CH, "fig14-S1", out)


# ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 14.S2: normalisation layers and the batch size
def norm_experiment(force=False):
    """Test accuracy of a small CNN with no normalisation, batch norm, layer norm, instance norm or group norm after
    each convolution, trained for one epoch on 6,000 digits with batch sizes 2, 8, 32 and 128; and the noise
    of the batch statistics of the first-layer activations as a function of the batch size."""
    path = os.path.join(CACHE_DIR, "ch14_norms.npz")
    if os.path.exists(path) and not force:
        z = np.load(path)
        return {k: z[k] for k in z.files}
    torch = _torch()
    nn, F = torch.nn, torch.nn.functional
    Xtr, ytr, Xte, yte = mnist_split(6000, 2000, 2)
    Xt, yt, Xv, yv = torch.tensor(Xtr), torch.tensor(ytr), torch.tensor(Xte), torch.tensor(yte)

    def make(kind):
        def nl(c):
            return {"none": nn.Identity(), "bn": nn.BatchNorm2d(c), "ln": nn.GroupNorm(1, c), "in": nn.GroupNorm(c, c), "gn": nn.GroupNorm(4, c)}[kind]
        return nn.Sequential(nn.Conv2d(1, 8, 5, padding=2), nl(8), nn.ReLU(), nn.MaxPool2d(2), nn.Conv2d(8, 16, 5, padding=2), nl(16),
                             nn.ReLU(), nn.MaxPool2d(2), nn.Flatten(), nn.Linear(16 * 49, 10))

    kinds, bss = ["none", "bn", "ln", "in", "gn"], [2, 8, 32, 128]
    acc = np.zeros((len(kinds), len(bss)))
    for i, kind in enumerate(kinds):
        for j, bs in enumerate(bss):
            torch.manual_seed(0)
            net = make(kind)
            opt = torch.optim.Adam(net.parameters(), lr=1e-3)
            g = torch.Generator().manual_seed(0)
            perm = torch.randperm(len(Xt), generator=g)
            for s in range(0, len(Xt), bs):
                idx = perm[s:s + bs]
                opt.zero_grad()
                F.cross_entropy(net(Xt[idx]), yt[idx]).backward()
                opt.step()
            net.eval()
            with torch.no_grad():
                acc[i, j] = float((net(Xv).argmax(1) == yv).float().mean())
    # noise of the batch statistics: first-layer activations of a random-weight 5x5 convolution
    rng = np.random.default_rng(0)
    W1 = rng.normal(size=(8, 1, 5, 5)) * 0.3
    A = conv_nchw(Xtr[:4096].astype(np.float64), W1, None, pad=2)         # (4096, 8, 28, 28)
    sizes = [1, 2, 4, 8, 16, 32, 64, 128]
    sd_mean, sd_var = [], []
    for B in sizes:
        ms, vs = [], []
        for s in range(0, 4096 - B + 1, B):
            blk = A[s:s + B, 0]
            ms.append(blk.mean())
            vs.append(blk.var())
        sd_mean.append(np.std(ms))
        sd_var.append(np.std(vs))
    np.savez(path, acc=acc, sizes=np.array(sizes), sd_mean=np.array(sd_mean), sd_var=np.array(sd_var))
    return dict(acc=acc, sizes=np.array(sizes), sd_mean=np.array(sd_mean), sd_var=np.array(sd_var))


def fig_14_S2(out=None):
    """Normalisation layers against the batch size (one epoch of training on 6,000 digits) and the noise of the batch mean."""
    r = norm_experiment()
    kinds = ["none", "bn", "ln", "in", "gn"]
    names = {"none": "no normalisation", "bn": "batch norm", "ln": "layer norm", "in": "instance norm", "gn": "group norm (4 groups)"}
    cols = {"none": GREY, "bn": RED, "ln": BLUE, "in": GREEN, "gn": ORANGE}
    fig, axes = plt.subplots(1, 2, figsize=(9.2, 3.3))
    ax = axes[0]
    for i, k in enumerate(kinds):
        ax.plot([2, 8, 32, 128], 100 * r["acc"][i], "o-", color=cols[k], label=names[k])
    ax.set_xscale("log")
    ax.set_xticks([2, 8, 32, 128])
    ax.set_xticklabels(["2", "8", "32", "128"])
    ax.set_xlabel("batch size")
    ax.set_ylabel("test accuracy (%) after 1 epoch")
    ax.legend(fontsize=7.5, loc="lower right")
    ax = axes[1]
    ax.loglog(r["sizes"], r["sd_mean"], "o-", color=RED, label="std of the batch mean (one channel)")
    ax.loglog(r["sizes"], r["sd_mean"][0] / np.sqrt(r["sizes"]), "k:", label="$\\propto1/\\sqrt{B}$")
    ax.set_xlabel("batch size $B$ (statistic pooled over $B$ images and all pixels)")
    ax.set_ylabel("standard deviation across batches")
    ax.legend(fontsize=8)
    fig.tight_layout()
    savefig(fig, CH, "fig14-S2", out)


# ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 14.S3: receptive fields
def receptive_field(layers):
    """Receptive field (r) and jump (j) of a stack of layers given as (kernel, stride, dilation):
    r <- r + (r_eff - 1) j with r_eff = d (k - 1) + 1, then j <- j s."""
    r, j = 1, 1
    for k, s, d in layers:
        r += (d * (k - 1)) * j
        j *= s
    return r


def measured_receptive_field(layers, size=129):
    """Size of the set of input pixels with non-zero gradient for the centre output of a stack of convolutions
    with all-ones kernels and positive inputs (autograd)."""
    torch = _torch()
    F = torch.nn.functional
    x = torch.ones(1, 1, size, size, requires_grad=True)
    h = x
    for k, s, d in layers:
        pad = d * (k - 1) // 2
        h = F.conv2d(h, torch.ones(1, 1, k, k), stride=s, padding=pad, dilation=d)
    c = h.shape[-1] // 2
    h[0, 0, c, c].backward()
    nz = (x.grad[0, 0] != 0).numpy()
    rows = np.where(nz.any(1))[0]
    return int(rows.max() - rows.min() + 1)


def fig_14_S3(out=None):
    """Receptive field against depth: stacked 3x3 convolutions, 3x3 with stride 2, and 3x3 with dilation 1, 2, 4, ..."""
    Ls = np.arange(1, 8)
    designs = [("stacked 3x3, stride 1", lambda L: [(3, 1, 1)] * L, BLUE),
               ("3x3, stride 2 in every layer", lambda L: [(3, 2, 1)] * L, RED),
               ("3x3, dilation $2^{l-1}$", lambda L: [(3, 1, 2 ** l) for l in range(L)], GREEN)]
    fig, ax = plt.subplots(figsize=(5.2, 3.4))
    for name, f, c in designs:
        ax.semilogy(Ls, [receptive_field(f(L)) for L in Ls], "-", color=c, label=name)
        Lm = [1, 2, 3, 4, 5]
        ax.semilogy(Lm, [measured_receptive_field(f(L)) for L in Lm], "o", color=c, ms=5)
    ax.axhline(7, color="k", lw=0.6, ls=":")
    ax.text(7.05, 7.5, "one 7x7 filter", fontsize=7.5, ha="right")
    ax.set_xlabel("number of layers $L$")
    ax.set_ylabel("receptive field (pixels per side)")
    ax.legend(fontsize=8)
    ax.set_title("line: formula; dots: measured by autograd", fontsize=8.5)
    fig.tight_layout()
    savefig(fig, CH, "fig14-S3", out)


# ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 14.S4: toy semantic segmentation
def seg_data(n, seed):
    """32x32 noisy images with random discs (class 1) and squares (class 2) of equal brightness on background 0."""
    rng = np.random.default_rng(seed)
    X = np.zeros((n, 1, 32, 32), np.float32)
    Y = np.zeros((n, 32, 32), np.int64)
    yy, xx = np.mgrid[0:32, 0:32]
    for i in range(n):
        for _ in range(rng.integers(1, 4)):
            cy, cx = rng.integers(6, 26, 2)
            if rng.random() < 0.5:
                r = rng.integers(3, 6)
                m = (yy - cy) ** 2 + (xx - cx) ** 2 <= r * r
                Y[i][m] = 1
            else:
                h = rng.integers(3, 6)
                m = (abs(yy - cy) <= h) & (abs(xx - cx) <= h)
                Y[i][m] = 2
        X[i, 0] = (Y[i] > 0) * 1.0 + 0.5 * rng.normal(size=(32, 32))
    return X, Y


def seg_experiment(force=False):
    """Train an encoder-decoder (max pooling down, transposed convolution up) with and without skip connections
    (a miniature U-Net) for 600 steps; returns pixel accuracy, mean IoU and example predictions."""
    path = os.path.join(CACHE_DIR, "ch14_seg.npz")
    if os.path.exists(path) and not force:
        z = np.load(path)
        return {k: z[k] for k in z.files}
    torch = _torch()
    nn, F = torch.nn, torch.nn.functional

    class Net(nn.Module):
        def __init__(self, skip):
            super().__init__()
            self.skip = skip
            self.e1 = nn.Conv2d(1, 16, 3, padding=1)
            self.e2 = nn.Conv2d(16, 32, 3, padding=1)
            self.e3 = nn.Conv2d(32, 64, 3, padding=1)
            self.u2 = nn.ConvTranspose2d(64, 32, 2, stride=2)
            self.d2 = nn.Conv2d(64 if skip else 32, 32, 3, padding=1)
            self.u1 = nn.ConvTranspose2d(32, 16, 2, stride=2)
            self.d1 = nn.Conv2d(32 if skip else 16, 16, 3, padding=1)
            self.out = nn.Conv2d(16, 3, 1)

        def forward(self, x):
            a1 = F.relu(self.e1(x))
            a2 = F.relu(self.e2(F.max_pool2d(a1, 2)))
            a3 = F.relu(self.e3(F.max_pool2d(a2, 2)))
            h = F.relu(self.u2(a3))
            h = F.relu(self.d2(torch.cat([h, a2], 1) if self.skip else h))
            h = F.relu(self.u1(h))
            h = F.relu(self.d1(torch.cat([h, a1], 1) if self.skip else h))
            return self.out(h)

    Xtr, Ytr = seg_data(1500, 0)
    Xte, Yte = seg_data(300, 1)
    Xt, Yt, Xv = torch.tensor(Xtr), torch.tensor(Ytr), torch.tensor(Xte)
    res = {"X": Xte[:4, 0], "Y": Yte[:4]}
    for name, skip in (("noskip", False), ("skip", True)):
        torch.manual_seed(0)
        net = Net(skip)
        opt = torch.optim.Adam(net.parameters(), lr=3e-3)
        g = torch.Generator().manual_seed(0)
        for step in range(600):
            idx = torch.randint(0, len(Xt), (32,), generator=g)
            opt.zero_grad()
            F.cross_entropy(net(Xt[idx]), Yt[idx]).backward()
            opt.step()
        with torch.no_grad():
            pred = net(Xv).argmax(1).numpy()
        ious = []
        for c in range(3):
            inter = ((pred == c) & (Yte == c)).sum()
            union = ((pred == c) | (Yte == c)).sum()
            ious.append(inter / union)
        res[name + "_pred"] = pred[:4]
        res[name + "_acc"] = np.array((pred == Yte).mean())
        res[name + "_miou"] = np.array(np.mean(ious))
        res[name + "_params"] = np.array(sum(p.numel() for p in net.parameters()))
    np.savez(path, **res)
    return res


def matplotlib_cmap():
    from matplotlib.colors import ListedColormap
    return ListedColormap(["#ffffff", "#d62728", "#1f5fbf"])


def fig_14_S4(out=None):
    """Toy semantic segmentation (Section 14.5.4): input, truth, and the predictions of an encoder-decoder without and with skip connections."""
    r = seg_experiment()
    fig, axes = plt.subplots(4, 4, figsize=(6.6, 6.8))
    cm = matplotlib_cmap()
    for i in range(4):
        axes[i, 0].imshow(r["X"][i], cmap="gray_r", vmin=-1, vmax=2)
        axes[i, 1].imshow(r["Y"][i], cmap=cm, vmin=0, vmax=2)
        axes[i, 2].imshow(r["noskip_pred"][i], cmap=cm, vmin=0, vmax=2)
        axes[i, 3].imshow(r["skip_pred"][i], cmap=cm, vmin=0, vmax=2)
        for j in range(4):
            axes[i, j].set_xticks([])
            axes[i, j].set_yticks([])
    for j, t in enumerate(["input", "truth (red disc, blue square)", "no skip: acc %.3f\nmean IoU %.3f" % (float(r["noskip_acc"]), float(r["noskip_miou"])),
                           "skip: acc %.3f\nmean IoU %.3f" % (float(r["skip_acc"]), float(r["skip_miou"]))]):
        axes[0, j].set_title(t, fontsize=7.5)
    fig.tight_layout()
    savefig(fig, CH, "fig14-S4", out)


# =========================================================================== U-Net sizes (used in the notes and checks)
def unet_sizes(n=572, depth=4):
    """Spatial sizes along the contracting path of the U-Net of Figure 14.30 (two 3x3 valid convolutions per level, 2x2 pooling)."""
    sizes = []
    for _ in range(depth):
        n = n - 4
        sizes.append(n)
        n = n // 2
    n = n - 4
    sizes.append(n)
    up = []
    for _ in range(depth):
        n = 2 * n - 4
        up.append(n)
    return sizes, up


# =========================================================================== exports for the browser demonstrations
def r4(a):
    return np.round(np.asarray(a, float), 4).tolist()


def kernel_def(kind, k):
    """The three kernels of the convolution demonstration, for any size k: 'edge' (columns -1, 0, +1 pattern: the sign of the
    column offset from the centre; [[1]] for k = 1), 'blur' (every weight 1/k^2) and 'diag' (identity matrix / k)."""
    if kind == "blur":
        return np.ones((k, k)) / (k * k)
    if kind == "diag":
        return np.eye(k) / k
    if k == 1:
        return np.ones((1, 1))
    return np.tile(np.sign(np.arange(k) - (k - 1) / 2.0), (k, 1))


def export_json():
    """Data for the three demonstrations: small CNN weights, digits and reference numbers; the conv explorer's images; the
    normalisation tensors with reference statistics."""
    os.makedirs(DATA_OUT, exist_ok=True)
    # ~~~~~~~~~~~~~~~~ demo 3: invert the small CNN
    P, acc = train_small_cnn()
    X, y = common.mnist(False)
    first = [int(np.argmax(y == c)) for c in range(10)]
    digs = [(np.round(X[i] * 255)).astype(int).reshape(28, 28).ravel().tolist() for i in first]
    ref = {}
    for name, kw in [("gauss", dict(prior="gauss", eps1=0.05, eps2=0.5, steps=100)),
                     ("tv", dict(prior="tv", eps1=0.05, lam_tv=0.5, eps2=0.5, steps=100)),
                     ("none", dict(prior="none", eps1=0.0, eps2=0.5, steps=100))]:
        ref[name] = {}
        for c in (3, 8):
            x, p, _ = invert_class(P, c, **kw)
            ref[name][str(c)] = dict(p=round(p, 6), sum=round(float(x.sum()), 5), min=round(float(x.min()), 5), max=round(float(x.max()), 5))
    xn, pn, _ = invert_class(P, 3, prior="gauss", eps1=0.05, eps2=0.5, eps3=0.05, steps=100, seed=1)
    ref["noise_c3"] = dict(p=round(pn, 6), sum=round(float(xn.sum()), 5))
    x9 = (np.array(digs[9], float) / 255.0).reshape(1, 1, 28, 28)
    xd, pd_, _ = invert_class(P, 8, prior="gauss", eps1=0.05, eps2=0.5, steps=40, x0=x9)
    ref["from_digit9_to_8"] = dict(p=round(pd_, 6), sum=round(float(xd.sum()), 5))
    z, _ = cnn_forward(P, (np.array(digs[3], float) / 255.0).reshape(1, 1, 28, 28))
    ref["logits_digit3"] = r4(z[0])
    d3 = dict(acc=acc, W1=r4(P["W1"]), b1=r4(P["b1"]), W2=r4(P["W2"]), b2=r4(P["b2"]), Wf=r4(P["Wf"]), bf=r4(P["bf"]), digits=digs, ref=ref)
    with open(os.path.join(DATA_OUT, "ch14-invert.json"), "w") as f:
        json.dump(d3, f, separators=(",", ":"))
    # ~~~~~~~~~~~~~~~~ demo 1: convolution explorer
    imgs = {}
    for c in (3, 7):
        imgs["digit%d" % c] = r4(resize_mean(X[first[c]].reshape(28, 28), 2))
    imgs["pattern"] = r4((np.add.outer(np.arange(5), np.arange(7)) % 4).astype(float) / 3.0)
    cref = {}
    for key, kind, kk, (p, st, r) in [("digit3", "edge", 3, (0, 1, 1)), ("digit3", "edge", 3, (1, 1, 1)), ("digit3", "edge", 3, (1, 2, 1)),
                                      ("digit3", "blur", 3, (0, 1, 2)), ("digit3", "diag", 4, (2, 2, 2)), ("digit7", "blur", 5, (1, 3, 1)),
                                      ("pattern", "edge", 3, (1, 2, 1)), ("pattern", "blur", 3, (0, 1, 1))]:
        img = np.array(imgs[key])
        Kk = kernel_def(kind, kk)
        Y = xcorr2d_fast(img, Kk, stride=st, pad=p, dil=r)
        C = conv_matrix(img.shape, Kk, st, p, r)
        cref["%s_%s%d_p%ds%dr%d" % (key, kind, kk, p, st, r)] = dict(shape=list(Y.shape), sum=round(float(Y.sum()), 5), abs=round(float(np.abs(Y).sum()), 5), nnz=int((C != 0).sum()),
                                                                  tsum=round(float((C.T @ Y.ravel()).sum()), 5))
    with open(os.path.join(DATA_OUT, "ch14-conv.json"), "w") as f:
        json.dump(dict(images=imgs, ref=cref), f, separators=(",", ":"))
    # ~~~~~~~~~~~~~~~~ demo 2: normalisation
    rng = np.random.default_rng(14)
    N, C, H, W = 32, 6, 4, 4
    mu_c = np.array([0.0, 2.0, -1.0, 4.0, 0.5, -2.5])
    sd_c = np.array([1.0, 0.5, 2.0, 1.5, 0.3, 1.0])
    off_n = rng.normal(size=(N, 1, 1, 1))
    gain_n = np.exp(rng.normal(size=(N, 1, 1, 1)) * 0.4)
    Z = (mu_c[None, :, None, None] + sd_c[None, :, None, None] * rng.normal(size=(N, C, H, W))) * gain_n + off_n
    Z = np.round(Z, 3)
    nref = {}
    for kind, g in [("bn", None), ("ln", None), ("in", None), ("gn2", 2), ("gn3", 3)]:
        o, mu, var = norm_nchw(Z[:6], "gn" if kind.startswith("gn") else kind, g, 1e-5)
        nref[kind] = dict(out_sum_sq=round(float((o ** 2).sum()), 5), o0=round(float(o[0, 0, 0, 0]), 5), mu0=round(float(np.ravel(mu)[0]), 5), var0=round(float(np.ravel(var)[0]), 5))
    sdm = {}
    for B in (1, 2, 4, 8, 16):
        sdm[str(B)] = round(float(np.std([Z[s:s + B, 0].mean() for s in range(0, N - B + 1, B)])), 5)
    with open(os.path.join(DATA_OUT, "ch14-norm.json"), "w") as f:
        json.dump(dict(shape=[N, C, H, W], z=Z.ravel().tolist(), ref=nref, sd_batch_mean_ch0=sdm), f, separators=(",", ":"))
    print("wrote ch14-*.json")


FIGURES = {"14.1": fig_14_1, "14.3": fig_14_3, "14.5": fig_14_5, "14.6": fig_14_6, "14.7": fig_14_7, "14.8": fig_14_8,
           "14.9": fig_14_9, "14.11": fig_14_11, "14.12": fig_14_12, "14.14": fig_14_14, "14.16": fig_14_16, "14.17": fig_14_17,
           "14.23": fig_14_23, "14.24": fig_14_24, "14.25": fig_14_25, "14.26": fig_14_26, "14.27": fig_14_27, "14.33": fig_14_33,
           "14.34": fig_14_34, "14.35": fig_14_35, "14.36": fig_14_36, "14.37": fig_14_37, "14.38": fig_14_38, "14.41": fig_14_41,
           "14.S1": fig_14_S1, "14.S2": fig_14_S2, "14.S3": fig_14_S3, "14.S4": fig_14_S4}


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