"""Bishop and Bishop (2024), Chapter 10: Convolutional Networks.

Reproduces the computed figures of Chapter 10 of C. M. Bishop and H. Bishop, Deep Learning: Foundations
and Concepts (Springer, 2024), pp. 287-324, written from scratch with numpy (every convolution, pooling,
unpooling and transposed convolution, with their backward passes), PyTorch (only to train one small
convolutional network on MNIST on the CPU) and
matplotlib. The functions are meant to be read next to the lecture notes (ch10-convolutional-networks.html):

* Section 10.2, convolutional filters: pad2d, out_size, xcorr2d (the book's 'convolution' (10.2), a
  cross-correlation), conv2d_math (the mathematical convolution (10.19)), im2col / conv_forward /
  conv_backward for multi-channel layers with padding, stride and dilation, conv_backward_input_full
  (the input gradient written as a full convolution with the flipped kernel), conv_matrix_1d (a
  convolution as a sparse weight-shared matrix, Exercise 10.2), maxpool / avgpool and their backward
  passes, receptive_field (the recursion for the receptive field of a stack of layers), separable_ops
  (Exercise 10.9) and vgg16_counts (Exercise 10.8).
* Section 10.3, visualising trained networks: gabor (10.6)-(10.8), a small MNIST CNN (SmallCNN, trained
  once and cached; also exported to JSON for the browser demos), numpy forward and input-gradient passes
  for it (np_forward, np_input_grad), Grad-CAM (10.9)-(10.10), the fast gradient sign method (10.11),
  class-maximising images, and DeepDream (10.12).
* Section 10.4, object detection: iou, nms (non-max suppression), sliding windows over a canvas of
  digits, and the toy network of Figures 10.22-10.23 (toy_net) used for the sliding-window identity and
  the operation counts of Exercise 10.12.
* Section 10.5, segmentation: unpool_copy, unpool_first, max_unpool (Figures 10.28-10.29),
  conv_transpose1d / conv_transpose2d (Figure 10.30, Exercise 10.13).
* Section 10.6, style transfer: gram (10.15), content and style errors (10.14), (10.16).

The network. SmallCNN has three convolutional layers (16 filters 5x5, 24 filters 5x5, 32 filters 3x3,
each with 'same' padding and ReLU; 2x2 max-pooling after the first two), global max-pooling over
positions and a linear layer with 11 outputs: the ten digits and a 'background' class (Exercise 10.11)
made of digits shifted by 8 to 16 pixels, so that the network can be used as a sliding-window detector.
The global pooling makes it accept any input size (and in a trial run learned faster than global average
pooling: 98.4% versus 97.2% test accuracy after 3 epochs). It has 17,347 parameters and is trained for 3
epochs with Adam (learning rate 0.003, multiplied by 0.6 after each epoch) on the 60,000 MNIST training
digits plus 15,000 background crops (three to four minutes on one thread); the weights are cached in
cache/ch10_cnn.pt.

Figures reproduced (computed): 10.4 (edge detection with the filters (10.3)-(10.4), on a synthetic
image), 10.8 (max-pooling), 10.9 (receptive fields, computed: nominal and effective), 10.10 (VGG-16:
feature-map sizes, parameters and connections per layer, computed), 10.11 (Gabor filters), 10.12
(first-layer filters: our MNIST CNN, and independent component analysis of natural-image patches),
10.13 (image patches that most activate units in each layer), 10.14 (class-maximising images),
10.15 (Grad-CAM saliency maps), 10.16 (an adversarial example by the fast gradient sign method),
10.18 (DeepDream), 10.20 (intersection-over-union), 10.25 (non-max suppression on real sliding-window
detections), 10.28 (unpooling), 10.29 (max-unpooling with switches), 10.30 (transposed convolution) and
10.32 (style transfer). Figures that show a large ImageNet network (10.12-10.16, 10.18, 10.32) are
reproduced at small scale with the MNIST network; the captions say so.

Figures skipped, with reasons: 10.1, 10.2, 10.5, 10.6, 10.7 (schematic diagrams of receptive fields,
weight sharing, padding and multi-channel filters; their content is computed by Figure 10.9), 10.3 (a symbolic
worked example: its numerical counterpart is Exercise 10.3), 10.17, 10.19, 10.24 and 10.26 (photographs, with drawn boxes or a segmentation), 10.21, 10.22,
10.23, 10.27, 10.31 (network schematics; toy_net computes 10.22-10.23 numerically).

Supplementary figures (ours): 10.S1 translation equivariance of the convolutional layers and the
growing invariance after pooling, measured on the trained network; 10.S2 accuracy under the fast
gradient sign method against epsilon for the CNN and a linear softmax model, and under random sign
noise of the same size.

Run `python3 ch10_convolutional_networks.py --list`, `python3 ch10_convolutional_networks.py` (all
figures; about four minutes on one CPU thread the first time, when the network is trained) or
`python3 ch10_convolutional_networks.py --fig 10.15`. Figures go to ../img/ch10/, the demo data to
../data/ch10-*.json.
"""
import json
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
from matplotlib.patches import Rectangle  # noqa: E402

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

HERE = os.path.dirname(os.path.abspath(__file__))
CACHE_DIR = os.path.join(HERE, "cache")
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
CH = 10
N_CLASSES = 11          # ten digits and the background class
BG = 10                 # index of the background class
CLASS_NAMES = [str(d) for d in range(10)] + ["bg"]


# =========================================================================== 10.2 convolution primitives
def pad2d(x, P, value=0.0):
    """Pad the last two axes of x with P pixels on every side (Figure 10.5)."""
    if P == 0:
        return np.asarray(x, dtype=float)
    widths = [(0, 0)] * (np.ndim(x) - 2) + [(P, P), (P, P)]
    return np.pad(np.asarray(x, dtype=float), widths, constant_values=value)


def out_size(J, M, P=0, S=1, D=1):
    """Number of output positions along an axis of length J: floor((J + 2P - D(M - 1) - 1)/S) + 1.

    With D = 1 this is floor((J + 2P - M)/S) + 1, the corrected (10.5)."""
    return (J + 2 * P - D * (M - 1) - 1) // S + 1


def xcorr2d(I, K, S=1, P=0, D=1):
    """The book's 'convolution' (10.2), C(j, k) = sum_{l,m} I(j + l, k + m) K(l, m) (a cross-correlation),
    for one channel, with zero padding P, stride S and dilation D (indices from 0)."""
    I = pad2d(I, P)
    K = np.asarray(K, dtype=float)
    M1, M2 = K.shape
    H = out_size(I.shape[0], M1, 0, S, D)
    W = out_size(I.shape[1], M2, 0, S, D)
    C = np.zeros((H, W))
    for l in range(M1):
        for m in range(M2):
            C += K[l, m] * I[l * D: l * D + (H - 1) * S + 1: S, m * D: m * D + (W - 1) * S + 1: S]
    return C


def conv2d_math(I, K, mode="valid"):
    """The mathematical convolution (10.19), C(j, k) = sum_{l,m} I(j - l, k - m) K(l, m).

    mode 'full' keeps every (j, k) with at least one overlapping term (size J + L - 1), 'valid' only those
    where the kernel lies inside the image (size J - L + 1). Equal to xcorr2d with the kernel rotated by 180
    degrees (Exercise 10.4)."""
    I = np.asarray(I, dtype=float)
    K = np.asarray(K, dtype=float)
    L, M = K.shape
    J, Kc = I.shape
    full = np.zeros((J + L - 1, Kc + M - 1))
    for l in range(L):
        for m in range(M):
            full[l:l + J, m:m + Kc] += K[l, m] * I
    if mode == "full":
        return full
    return full[L - 1:J, M - 1:Kc]


def im2col(X, M, S=1, P=0, D=1):
    """Columns of all receptive fields: X (C, H, W) -> (C*M*M, Ho*Wo), row order (c, l, m)."""
    Xp = pad2d(X, P)
    C = Xp.shape[0]
    Ho = out_size(Xp.shape[1], M, 0, S, D)
    Wo = out_size(Xp.shape[2], M, 0, S, D)
    cols = np.empty((C, M, M, Ho, Wo))
    for l in range(M):
        for m in range(M):
            cols[:, l, m] = Xp[:, l * D: l * D + (Ho - 1) * S + 1: S, m * D: m * D + (Wo - 1) * S + 1: S]
    return cols.reshape(C * M * M, Ho * Wo), Ho, Wo


def col2im(cols, shape, M, S=1, P=0, D=1):
    """Adjoint of im2col: scatter-add the columns back into an array of shape (C, H, W)."""
    C, H, W = shape
    Hp, Wp = H + 2 * P, W + 2 * P
    Ho = out_size(Hp, M, 0, S, D)
    Wo = out_size(Wp, M, 0, S, D)
    cols = cols.reshape(C, M, M, Ho, Wo)
    Xp = np.zeros((C, Hp, Wp))
    for l in range(M):
        for m in range(M):
            Xp[:, l * D: l * D + (Ho - 1) * S + 1: S, m * D: m * D + (Wo - 1) * S + 1: S] += cols[:, l, m]
    return Xp[:, P:P + H, P:P + W] if P else Xp


def conv_forward(X, W, b=None, S=1, P=0, D=1):
    """Multi-channel convolutional layer (Section 10.2.5): X (C, H, W), W (Cout, C, M, M), b (Cout,).

    a[o, j, k] = b[o] + sum_{c,l,m} W[o, c, l, m] X_pad[c, jS + lD, kS + mD]."""
    Co, C, M, _ = W.shape
    cols, Ho, Wo = im2col(X, M, S, P, D)
    A = W.reshape(Co, -1) @ cols
    if b is not None:
        A = A + np.asarray(b)[:, None]
    return A.reshape(Co, Ho, Wo)


def conv_backward(X, W, dA, S=1, P=0, D=1):
    """Gradients of a convolutional layer: given dE/da (Cout, Ho, Wo) return dE/dX, dE/dW, dE/db."""
    Co, C, M, _ = W.shape
    cols, Ho, Wo = im2col(X, M, S, P, D)
    dA2 = dA.reshape(Co, -1)
    dW = (dA2 @ cols.T).reshape(W.shape)
    db = dA2.sum(1)
    dX = col2im(W.reshape(Co, -1).T @ dA2, X.shape, M, S, P, D)
    return dX, dW, db


def conv_backward_input_full(W, dA, P=0):
    """For stride 1 and no dilation, dE/dX as a convolution: the 'full' cross-correlation of dE/da (zero
    padded by M - 1) with the kernel rotated by 180 degrees and its channel axes swapped, then cropped by P."""
    Co, C, M, _ = W.shape
    Wf = W[:, :, ::-1, ::-1].transpose(1, 0, 2, 3)      # (C, Co, M, M)
    dXp = conv_forward(dA, Wf, None, 1, M - 1, 1)
    return dXp[:, P:dXp.shape[1] - P, P:dXp.shape[2] - P] if P else dXp


def conv_matrix_1d(n, w, S=1, P=0):
    """The matrix A with (xcorr of the zero-padded x with w, stride S) = A @ x_padded (Exercises 10.2, 10.13)."""
    w = np.asarray(w, dtype=float)
    npad = n + 2 * P
    m = out_size(npad, len(w), 0, S)
    A = np.zeros((m, npad))
    for i in range(m):
        A[i, i * S:i * S + len(w)] = w
    return A


def conv_transpose1d(z, w, S=1, out_len=None):
    """Transposed (fractionally strided) convolution in 1-D: out[iS + l] += z[i] w[l] (Exercise 10.13)."""
    z = np.asarray(z, dtype=float)
    w = np.asarray(w, dtype=float)
    n = (len(z) - 1) * S + len(w)
    out = np.zeros(max(n, out_len or 0))
    for i, zi in enumerate(z):
        out[i * S:i * S + len(w)] += zi * w
    return out


def conv_transpose2d(Z, K, S=1):
    """Transposed convolution in 2-D (Figure 10.30): each input value stamps a scaled copy of the kernel,
    S pixels apart, and overlapping contributions are summed. Output size (n - 1)S + M."""
    Z = np.asarray(Z, dtype=float)
    K = np.asarray(K, dtype=float)
    M = K.shape[0]
    out = np.zeros(((Z.shape[0] - 1) * S + M, (Z.shape[1] - 1) * S + M))
    for i in range(Z.shape[0]):
        for j in range(Z.shape[1]):
            out[i * S:i * S + M, j * S:j * S + M] += Z[i, j] * K
    return out


def maxpool(X, k=2, s=2):
    """Max-pooling of each channel of X (C, H, W) over k x k windows with stride s (Figure 10.8).
    Returns the pooled array and the flat index (within each channel) of every maximum (the 'switches');
    ties go to the first maximum in row-major order."""
    C, H, W = X.shape
    Ho, Wo = (H - k) // s + 1, (W - k) // s + 1
    win = np.empty((C, Ho, Wo, k * k))
    idx = np.empty((C, Ho, Wo, k * k), dtype=int)
    for a in range(k):
        for b in range(k):
            win[..., a * k + b] = X[:, a:a + (Ho - 1) * s + 1:s, b:b + (Wo - 1) * s + 1:s]
            rows = np.arange(Ho)[:, None] * s + a
            colz = np.arange(Wo)[None, :] * s + b
            idx[..., a * k + b] = rows * W + colz
    am = win.argmax(-1)
    Y = np.take_along_axis(win, am[..., None], -1)[..., 0]
    sw = np.take_along_axis(idx, am[..., None], -1)[..., 0]
    return Y, sw


def maxpool_backward(dY, switches, shape):
    """Route each output gradient to the input that won the max (the same operation as max-unpooling)."""
    C, H, W = shape
    dX = np.zeros((C, H * W))
    for c in range(C):
        np.add.at(dX[c], switches[c].ravel(), dY[c].ravel())
    return dX.reshape(shape)


def avgpool(X, k=2, s=2):
    C, H, W = X.shape
    Ho, Wo = (H - k) // s + 1, (W - k) // s + 1
    Y = np.zeros((C, Ho, Wo))
    for a in range(k):
        for b in range(k):
            Y += X[:, a:a + (Ho - 1) * s + 1:s, b:b + (Wo - 1) * s + 1:s]
    return Y / (k * k)


def unpool_copy(Y, k=2):
    """Up-sampling analogue of average pooling: copy each value into a k x k block (Figure 10.28a)."""
    return np.kron(np.asarray(Y, dtype=float), np.ones((k, k)))


def unpool_first(Y, k=2):
    """Up-sampling analogue of max-pooling: each value goes to the first cell of its block (Figure 10.28b)."""
    Y = np.asarray(Y, dtype=float)
    out = np.zeros((Y.shape[0] * k, Y.shape[1] * k))
    out[::k, ::k] = Y
    return out


def max_unpool(Y, switches, shape):
    """Max-unpooling with the switches recorded by maxpool (Figure 10.29)."""
    return maxpool_backward(Y, switches, shape)


def receptive_field(layers):
    """Receptive field r and jump j (input pixels between neighbouring units) after each layer.

    layers: list of (k, s, d) = (kernel size, stride, dilation); a pooling layer is (k, s, 1).
    Recursion: r_l = r_{l-1} + d_l (k_l - 1) j_{l-1}, j_l = j_{l-1} s_l, from r_0 = j_0 = 1."""
    r, j, out = 1, 1, []
    for k, s, d in layers:
        r = r + d * (k - 1) * j
        j = j * s
        out.append((r, j))
    return out


def separable_ops(J, K, L, M):
    """Multiply-adds of a valid 2-D convolution with an L x M kernel on a J x K image, directly and as two
    1-D convolutions when the kernel is separable, K(l, m) = F(l) G(m) (Exercise 10.9)."""
    direct = (J - L + 1) * (K - M + 1) * L * M
    two = J * (K - M + 1) * M + (J - L + 1) * (K - M + 1) * L
    return direct, two


VGG16 = [  # (kind, spatial size of the layer's output, input channels, output channels)
    ("conv", 224, 3, 64), ("conv", 224, 64, 64),
    ("conv", 112, 64, 128), ("conv", 112, 128, 128),
    ("conv", 56, 128, 256), ("conv", 56, 256, 256), ("conv", 56, 256, 256),
    ("conv", 28, 256, 512), ("conv", 28, 512, 512), ("conv", 28, 512, 512),
    ("conv", 14, 512, 512), ("conv", 14, 512, 512), ("conv", 14, 512, 512),
    ("fc", 1, 7 * 7 * 512, 4096), ("fc", 1, 4096, 4096), ("fc", 1, 4096, 1000),
]


def vgg16_counts():
    """Per learnable layer of VGG-16 (Figure 10.10, Exercise 10.8): (connections incl. bias, parameters).

    A 3x3 'same' convolution on an H x H map with C_in -> C_out channels has H^2 (9 C_in + 1) C_out
    connections (counting the padding inputs, as the manual does) and (9 C_in + 1) C_out parameters; a
    fully connected layer has (n_in + 1) n_out of both."""
    rows = []
    for kind, H, cin, cout in VGG16:
        if kind == "conv":
            rows.append((H * H * (9 * cin + 1) * cout, (9 * cin + 1) * cout))
        else:
            rows.append(((cin + 1) * cout, (cin + 1) * cout))
    return rows


# =========================================================================== 10.3 Gabor filters
def gabor(x, y, A=1.0, alpha=1.0, beta=1.0, omega=1.0, phi=0.0, theta=0.0, x0=0.0, y0=0.0):
    """The Gabor filter (10.6) with the rotated coordinates (10.7)-(10.8)."""
    xt = (x - x0) * np.cos(theta) + (y - y0) * np.sin(theta)
    yt = -(x - x0) * np.sin(theta) + (y - y0) * np.cos(theta)
    return A * np.exp(-alpha * xt ** 2 - beta * yt ** 2) * np.sin(omega * xt + phi)


# =========================================================================== 10.4 detection measures
def iou(a, b):
    """Intersection-over-union of boxes given as (x0, y0, x1, y1) (Figure 10.20)."""
    ix = max(0.0, min(a[2], b[2]) - max(a[0], b[0]))
    iy = max(0.0, min(a[3], b[3]) - max(a[1], b[1]))
    inter = ix * iy
    ua = (a[2] - a[0]) * (a[3] - a[1]) + (b[2] - b[0]) * (b[3] - b[1]) - inter
    return inter / ua if ua > 0 else 0.0


def nms(boxes, scores, p_min=0.7, iou_max=0.5):
    """Non-max suppression (Section 10.4.5) for one class: drop boxes with score < p_min; repeatedly keep
    the highest-scoring remaining box and discard every remaining box whose IoU with it exceeds iou_max."""
    order = [i for i in np.argsort(-np.asarray(scores), kind="stable") if scores[i] >= p_min]
    keep = []
    while order:
        i = order.pop(0)
        keep.append(i)
        order = [j for j in order if iou(boxes[i], boxes[j]) <= iou_max]
    return keep


def toy_net(X, K, F):
    """The network of Figures 10.22-10.23 with one channel: valid 3x3 convolution K, ReLU, 2x2 max-pooling
    with stride 2, then the 2x2 'fully connected' filter F applied as a valid convolution with stride 1.
    A 6x6 input gives one output; an 8x8 input gives a 2x2 array of outputs."""
    Z = np.maximum(xcorr2d(X, K), 0.0)
    Pm, _ = maxpool(Z[None], 2, 2)
    return xcorr2d(Pm[0], F)


def toy_net_ops(n):
    """Operation counts of toy_net on an n x n input (Exercise 10.12): an inner product of length N costs
    N multiplications and N - 1 additions, and the max of 4 numbers costs 3 comparisons."""
    c = n - 2
    p = c // 2
    o = p - 1
    return c * c * (2 * 9 - 1) + p * p * 3 + o * o * (2 * 4 - 1)


# =========================================================================== 10.6 style
def gram(A):
    """Style matrix (10.15): A (K, I, J) -> F (K, K) with F_kk' = sum_ij a_ijk a_ijk'."""
    K = A.shape[0]
    Am = A.reshape(K, -1)
    return Am @ Am.T


def style_error(AG, AS):
    """(10.16) for one layer."""
    K, I, J = AG.shape
    return np.sum((gram(AG) - gram(AS)) ** 2) / (2.0 * I * J * K) ** 2


def style_error_grad(AG, AS):
    """dE_style/da_ijk = (1/(IJK)^2) sum_k' a_ijk' (F - S)_k'k (derived in the notes)."""
    K, I, J = AG.shape
    Dm = gram(AG) - gram(AS)
    return (Dm @ AG.reshape(K, -1)).reshape(AG.shape) / (I * J * K) ** 2


def content_error(AG, AC):
    """(10.14)."""
    return np.sum((AG - AC) ** 2)


# =========================================================================== the MNIST CNN
_TORCH = None


def _torch():
    global _TORCH
    if _TORCH is None:
        _TORCH = common.torch_setup(0, threads=1)
    return _TORCH


def make_cnn():
    """The small network described in the module docstring (built lazily so that numpy-only use of this
    module does not import PyTorch)."""
    torch = _torch()
    nn = torch.nn

    class SmallCNN(nn.Module):
        def __init__(self):
            super().__init__()
            self.conv1 = nn.Conv2d(1, 16, 5, padding=2)
            self.conv2 = nn.Conv2d(16, 24, 5, padding=2)
            self.conv3 = nn.Conv2d(24, 32, 3, padding=1)
            self.fc = nn.Linear(32, N_CLASSES)

        def features(self, x):
            """Pre-activations of the three convolutional layers (and the pooled maps)."""
            F = torch.nn.functional
            a1 = self.conv1(x)
            p1 = F.max_pool2d(F.relu(a1), 2)
            a2 = self.conv2(p1)
            p2 = F.max_pool2d(F.relu(a2), 2)
            a3 = self.conv3(p2)
            return a1, p1, a2, p2, a3

        def head(self, a3):
            return self.fc(torch.relu(a3).amax((2, 3)))

        def forward(self, x):
            return self.head(self.features(x)[-1])

    return SmallCNN()


def shift_image(img, dy, dx):
    """Shift a 2-D image by (dy, dx) pixels, filling with zeros."""
    out = np.zeros_like(img)
    H, W = img.shape
    ys, yd = (slice(0, H - dy), slice(dy, H)) if dy >= 0 else (slice(-dy, H), slice(0, H + dy))
    xs, xd = (slice(0, W - dx), slice(dx, W)) if dx >= 0 else (slice(-dx, W), slice(0, W + dx))
    out[yd, xd] = img[ys, xs]
    return out


def background_set(X, n, seed=1):
    """Background crops for the 11th class: digits shifted by 8 to 16 pixels (Chebyshev distance) in a
    random direction, so that only part of a digit is in the window; one in ten is an empty window."""
    rng = np.random.default_rng(seed)
    out = np.zeros((n, 28, 28))
    for i in range(n):
        if rng.random() < 0.1:
            continue
        img = X[rng.integers(len(X))].reshape(28, 28)
        d = rng.integers(8, 17)
        other = rng.integers(-d, d + 1)
        dy, dx = (d * rng.choice([-1, 1]), other) if rng.random() < 0.5 else (other, d * rng.choice([-1, 1]))
        out[i] = shift_image(img, int(dy), int(dx))
    return out


def train_cnn(epochs=3, n_bg=15000, seed=0, verbose=True):
    torch = common.torch_setup(seed, threads=1)
    X, y = common.mnist(train=True)
    Xb = background_set(X, n_bg, seed=seed + 1)
    Xall = np.concatenate([X.reshape(-1, 28, 28), Xb]).astype(np.float32)[:, None]
    yall = np.concatenate([y, np.full(n_bg, BG)])
    Xt, yt = torch.from_numpy(Xall), torch.from_numpy(yall).long()
    net = make_cnn()
    opt = torch.optim.Adam(net.parameters(), lr=3e-3)
    sched = torch.optim.lr_scheduler.StepLR(opt, 1, 0.6)
    g = torch.Generator().manual_seed(seed)
    B = 128
    for ep in range(epochs):
        perm = torch.randperm(len(Xt), generator=g)
        tot = 0.0
        for i in range(0, len(Xt), B):
            idx = perm[i:i + B]
            loss = torch.nn.functional.cross_entropy(net(Xt[idx]), yt[idx])
            opt.zero_grad()
            loss.backward()
            opt.step()
            tot += loss.item() * len(idx)
        sched.step()
        if verbose:
            print("   epoch %d: mean training cross-entropy %.4f" % (ep + 1, tot / len(Xt)))
    return net


def get_cnn():
    """The trained SmallCNN (trained on first use, then loaded from cache/ch10_cnn.pt)."""
    torch = _torch()
    path = os.path.join(CACHE_DIR, "ch10_cnn.pt")
    net = make_cnn()
    if os.path.exists(path):
        net.load_state_dict(torch.load(path))
    else:
        os.makedirs(CACHE_DIR, exist_ok=True)
        net = train_cnn()
        torch.save(net.state_dict(), path)
    net.eval()
    return net


def get_linear():
    """A linear softmax model on the raw pixels (10 digit classes), for the adversarial comparison."""
    torch = _torch()
    path = os.path.join(CACHE_DIR, "ch10_linear.pt")
    lin = torch.nn.Linear(784, 10)
    if os.path.exists(path):
        lin.load_state_dict(torch.load(path))
        return lin
    common.torch_setup(3, threads=1)
    X, y = common.mnist(train=True)
    Xt, yt = torch.from_numpy(X.astype(np.float32)), torch.from_numpy(y).long()
    opt = torch.optim.Adam(lin.parameters(), lr=1e-3)
    g = torch.Generator().manual_seed(3)
    for _ in range(5):
        perm = torch.randperm(len(Xt), generator=g)
        for i in range(0, len(Xt), 128):
            idx = perm[i:i + 128]
            loss = torch.nn.functional.cross_entropy(lin(Xt[idx]), yt[idx])
            opt.zero_grad()
            loss.backward()
            opt.step()
    os.makedirs(CACHE_DIR, exist_ok=True)
    torch.save(lin.state_dict(), path)
    return lin


def cnn_params(net, decimals=None):
    """The network's weights as a dict of float64 numpy arrays; with decimals=d they are rounded to d
    significant digits (exactly the numbers written to the JSON file used by the demos)."""
    P = {k: v.detach().double().numpy().copy() for k, v in net.state_dict().items()}
    if decimals:
        P = {k: np.array([float("%.*g" % (decimals, t)) for t in v.ravel()]).reshape(v.shape) for k, v in P.items()}
    return P


def np_forward(P, x):
    """Forward pass of SmallCNN in numpy (float64) for one image x (H, W); returns logits and a cache."""
    X0 = np.asarray(x, dtype=float)[None]
    a1 = conv_forward(X0, P["conv1.weight"], P["conv1.bias"], 1, 2)
    z1 = np.maximum(a1, 0)
    p1, s1 = maxpool(z1)
    a2 = conv_forward(p1, P["conv2.weight"], P["conv2.bias"], 1, 2)
    z2 = np.maximum(a2, 0)
    p2, s2 = maxpool(z2)
    a3 = conv_forward(p2, P["conv3.weight"], P["conv3.bias"], 1, 1)
    z3 = np.maximum(a3, 0)
    flat = z3.reshape(len(z3), -1)
    arg = flat.argmax(1)
    g = flat[np.arange(len(z3)), arg]
    logits = P["fc.weight"] @ g + P["fc.bias"]
    cache = dict(X0=X0, a1=a1, z1=z1, p1=p1, s1=s1, a2=a2, z2=z2, p2=p2, s2=s2, a3=a3, z3=z3, g=g, arg=arg)
    return logits, cache


def softmax(a):
    e = np.exp(a - np.max(a))
    return e / e.sum()


def np_input_grad(P, x, dlogits):
    """Backpropagate dE/dlogits to dE/dx (and return dE/da3, used by Grad-CAM)."""
    _, c = np_forward(P, x)
    dg = P["fc.weight"].T @ dlogits
    dz3 = np.zeros(c["a3"].size).reshape(len(dg), -1)
    dz3[np.arange(len(dg)), c["arg"]] = dg          # global max-pooling routes the gradient to the maximum
    da3 = dz3.reshape(c["a3"].shape) * (c["a3"] > 0)
    dp2, _, _ = conv_backward(c["p2"], P["conv3.weight"], da3, 1, 1)
    da2 = maxpool_backward(dp2, c["s2"], c["z2"].shape) * (c["a2"] > 0)
    dp1, _, _ = conv_backward(c["p1"], P["conv2.weight"], da2, 1, 2)
    da1 = maxpool_backward(dp1, c["s1"], c["z1"].shape) * (c["a1"] > 0)
    dX0, _, _ = conv_backward(c["X0"], P["conv1.weight"], da1, 1, 2)
    return dX0[0], da3


def gradcam(P, x, cls, maps="pre"):
    """Grad-CAM on the last convolutional layer. maps='pre' is the book's form (10.9)-(10.10): alpha_k is
    the mean over positions of d a^(c) / d a3_kij and L = sum_k alpha_k a3_k (pre-activations). maps='post'
    is the form of Selvaraju et al.: the same with the post-ReLU maps z3 = ReLU(a3) in place of a3 (the
    gradient taken with respect to z3), followed by a final ReLU. Returns L (H3, W3) and alpha."""
    e = np.zeros(N_CLASSES)
    e[cls] = 1.0
    _, c = np_forward(P, x)
    if maps == "pre":
        _, da3 = np_input_grad(P, x, e)
        alpha = da3.mean((1, 2))
        return np.tensordot(alpha, c["a3"], 1), alpha
    dg = P["fc.weight"].T @ e                      # d a^(c) / d g_k
    M = c["a3"].shape[1] * c["a3"].shape[2]
    alpha = dg / M                                 # global max-pooling: the gradient sits at one position
    return np.maximum(np.tensordot(alpha, c["z3"], 1), 0.0), alpha


def fgsm(P, x, t, eps, steps=1, target=None):
    """Fast gradient sign method (10.11), x' = clip(x + eps sign(grad_x E(x, t)), 0, 1), with E the
    cross-entropy of the true label t. steps > 1 gives the iterative version (eps/steps per step, kept
    within eps of x); target=c instead descends the cross-entropy of class c."""
    x0 = np.asarray(x, dtype=float)
    xa = x0.copy()
    for _ in range(steps):
        logits, _ = np_forward(P, xa)
        y = softmax(logits)
        if target is None:
            d = y.copy()
            d[t] -= 1.0
            s = 1.0
        else:
            d = y.copy()
            d[target] -= 1.0
            s = -1.0
        gx, _ = np_input_grad(P, xa, d)
        xa = xa + s * (eps / steps) * np.sign(gx)
        xa = np.clip(np.clip(xa, x0 - eps, x0 + eps), 0.0, 1.0)
    return xa


# =========================================================================== data for figures and demos
def test_digits():
    X, y = common.mnist(train=False)
    return X.reshape(-1, 28, 28), y


DEMO_IDX = [3, 2, 1, 18, 4, 8, 11, 0, 61, 7, 10, 5, 13, 14, 15, 17, 19, 21, 22, 33]


def synthetic_scene(n=96):
    """A grey-scale test image with straight and curved edges of both polarities (for Figure 10.4)."""
    yy, xx = np.mgrid[0:n, 0:n] / (n - 1.0)
    img = 0.35 + 0.25 * xx                                         # smooth shading
    img = np.where((xx - 0.3) ** 2 + (yy - 0.3) ** 2 < 0.04, 0.95, img)         # bright disc
    img = np.where((xx > 0.55) & (xx < 0.9) & (yy > 0.15) & (yy < 0.45), 0.08, img)   # dark rectangle
    tri = (yy > 0.58) & (yy < 0.92) & (np.abs(xx - 0.72) < (yy - 0.58) * 0.6)
    img = np.where(tri, 0.8, img)
    stripes = (xx > 0.08) & (xx < 0.45) & (yy > 0.62) & (yy < 0.92)
    img = np.where(stripes, 0.5 + 0.4 * np.sign(np.sin(2 * np.pi * (xx + yy) * 7)), img)
    return img


EDGE_V = np.array([[-1, 0, 1], [-1, 0, 1], [-1, 0, 1]], dtype=float)     # (10.3)
EDGE_H = EDGE_V.T.copy()                                                  # (10.4)


def export_demo_data(net=None):
    """Write ../data/ch10-cnn.json (weights, test digits, reference numbers) and ../data/ch10-conv.json
    (the small images and kernels of the convolution calculator)."""
    net = net or get_cnn()
    P = cnn_params(net, decimals=7)
    Xt, yt = test_digits()
    digits = [{"label": int(yt[i]), "index": int(i), "px": [int(round(v * 255)) for v in Xt[i].ravel()]} for i in DEMO_IDX]
    ref = []
    for k, i in enumerate(DEMO_IDX[:6]):
        x = np.array(digits[k]["px"], dtype=float).reshape(28, 28) / 255.0
        logits, _ = np_forward(P, x)
        L, _ = gradcam(P, x, int(yt[i]), "pre")
        L2, _ = gradcam(P, x, int(yt[i]), "post")
        xa = fgsm(P, x, int(yt[i]), 0.15)
        la, _ = np_forward(P, xa)
        ref.append({"k": k, "logits": logits.tolist(), "gradcam_pre": L.ravel().tolist(),
                    "gradcam_post": L2.ravel().tolist(), "fgsm_eps": 0.15, "fgsm_logits": la.tolist()})
    W = {k: np.round(v, 12).ravel().tolist() for k, v in P.items()}
    shapes = {k: list(v.shape) for k, v in P.items()}
    os.makedirs(DATA_OUT, exist_ok=True)
    out = {"about": "SmallCNN of ch10_convolutional_networks.py trained on MNIST (10 digits + background); "
                    "weights rounded to 7 significant digits; digits are MNIST test images (0-255).",
           "head": "max", "classes": CLASS_NAMES, "shapes": shapes, "weights": W, "digits": digits, "reference": ref}
    with open(os.path.join(DATA_OUT, "ch10-cnn.json"), "w") as f:
        json.dump(out, f, separators=(",", ":"))
    # the convolution calculator: three 12 x 12 images (two digits, one synthetic) with values in [0, 1]
    imgs = []
    for i, name in ((0, "digit 7"), (1, "digit 2")):
        d = Xt[DEMO_IDX[i]]
        small = d[2:26, 2:26].reshape(12, 2, 12, 2).mean((1, 3))
        imgs.append({"name": name, "px": [round(float(v), 3) for v in small.ravel()]})
    sc = synthetic_scene(48).reshape(12, 4, 12, 4).mean((1, 3))
    imgs.append({"name": "shapes", "px": [round(float(v), 3) for v in sc.ravel()]})
    with open(os.path.join(DATA_OUT, "ch10-conv.json"), "w") as f:
        json.dump({"size": 12, "images": imgs}, f, separators=(",", ":"))
    print("wrote ../data/ch10-cnn.json and ../data/ch10-conv.json")
    return out


# =========================================================================== plotting helpers
def num_grid(ax, A, title=None, cmap="Greys", vmin=None, vmax=None, fmt="%g", hl=None, fs=10, x0=0.0, y0=0.0,
             colour_cells=True, edge="#444444"):
    """Draw array A as a grid of numbered cells with its top-left corner at (x0, y0) in data coordinates
    (y downwards). hl maps (i, j) -> face colour for highlighted cells."""
    A = np.asarray(A, dtype=float)
    vmin = A.min() if vmin is None else vmin
    vmax = A.max() if vmax is None else vmax
    cm = plt.get_cmap(cmap)
    for i in range(A.shape[0]):
        for j in range(A.shape[1]):
            fc = "white"
            if colour_cells and vmax > vmin:
                fc = cm(0.08 + 0.45 * (A[i, j] - vmin) / (vmax - vmin))
            if hl and (i, j) in hl:
                fc = hl[(i, j)]
            ax.add_patch(Rectangle((x0 + j, y0 + i), 1, 1, fc=fc, ec=edge, lw=0.8))
            ax.text(x0 + j + 0.5, y0 + i + 0.5, fmt % A[i, j], ha="center", va="center", fontsize=fs)
    if title:
        ax.text(x0 + A.shape[1] / 2, y0 - 0.35, title, ha="center", va="bottom", fontsize=fs)


def clean(ax):
    ax.set_xticks([])
    ax.set_yticks([])
    for s in ax.spines.values():
        s.set_visible(False)


def show_img(ax, img, title=None, cmap="gray", vmin=None, vmax=None):
    ax.imshow(img, cmap=cmap, vmin=vmin, vmax=vmax, interpolation="nearest")
    ax.set_xticks([])
    ax.set_yticks([])
    if title:
        ax.set_title(title, fontsize=9.5)


def _torch_x(x):
    torch = _torch()
    return torch.tensor(np.asarray(x, dtype=np.float32))[None, None]


# =========================================================================== Figures, Section 10.2
def fig_10_4(out=None):
    """Edge detection with the filters (10.3) and (10.4)."""
    img = synthetic_scene(96)
    v = xcorr2d(img, EDGE_V)
    h = xcorr2d(img, EDGE_H)
    fig, ax = common.panel_grid(1, 3, size=(2.7, 2.75))
    show_img(ax[0, 0], img, vmin=0, vmax=1)
    m = max(np.abs(v).max(), np.abs(h).max())
    show_img(ax[0, 1], v, vmin=-m, vmax=m)
    show_img(ax[0, 2], h, vmin=-m, vmax=m)
    for k, t in enumerate("abc"):
        ax[0, k].set_xlabel("(%s)" % t, fontsize=10)
    fig.tight_layout()
    return savefig(fig, CH, "fig10-4", out)


def fig_10_8(out=None):
    """Max-pooling of 2x2 blocks with stride 2 (own numbers)."""
    A = np.array([[2, 7, 1, 3], [4, 0, 6, 5], [8, 1, 2, 2], [3, 9, 4, 0]], dtype=float)
    Y, sw = maxpool(A[None], 2, 2)
    cols = {(0, 0): "#fde0dd", (0, 1): "#deebf7", (1, 0): "#e5f5e0", (1, 1): "#fff2cc"}
    hl = {}
    for i in range(4):
        for j in range(4):
            hl[(i, j)] = cols[(i // 2, j // 2)]
    hl2 = {(i, j): cols[(i, j)] for i in range(2) for j in range(2)}
    fig, ax = plt.subplots(figsize=(5.2, 2.6))
    num_grid(ax, A, hl=hl, fs=12)
    for (i, j) in [(int(s) // 4, int(s) % 4) for s in sw[0].ravel()]:
        ax.add_patch(Rectangle((j + 0.08, i + 0.08), 0.84, 0.84, fc="none", ec="#c0392b", lw=1.8))
    num_grid(ax, Y[0], hl=hl2, fs=12, x0=6.0, y0=1.0)
    ax.annotate("", xy=(5.8, 2.0), xytext=(4.3, 2.0), arrowprops=dict(arrowstyle="->", lw=1.4))
    ax.text(5.05, 1.75, "max", ha="center", fontsize=10)
    ax.set_xlim(-0.2, 8.2)
    ax.set_ylim(4.2, -0.2)
    ax.set_aspect("equal")
    clean(ax)
    return savefig(fig, CH, "fig10-8", out)


def _ones_erf(dils):
    """Effective receptive field: |d(centre output)/d(input)| for a linear stack of 3x3 all-ones filters."""
    g = np.zeros((1, 1))
    g[0, 0] = 1.0
    for d in reversed(dils):
        K = np.zeros((2 * d + 1, 2 * d + 1))
        K[::d, ::d] = 1.0
        g = conv2d_math(g, K, "full")
    return g


def fig_10_9(out=None):
    """Receptive fields grow with depth (computed)."""
    fig = plt.figure(figsize=(10.4, 3.0))
    gs = fig.add_gridspec(1, 5, width_ratios=[1.45, 1, 1, 1, 1], wspace=0.25)
    ax = fig.add_subplot(gs[0])
    L = np.arange(1, 11)
    r_plain = [receptive_field([(3, 1, 1)] * k)[-1][0] for k in L]
    r_pool = [receptive_field([(3, 1, 1), (2, 2, 1)] * k)[-1][0] for k in L]
    r_dil = [receptive_field([(3, 1, 2 ** i) for i in range(k)])[-1][0] for k in L]
    sd = [2 * math.sqrt(2 * k / 3.0) for k in L]
    ax.semilogy(L, r_plain, "o-", color=common.BLUE, ms=3.5, label="3x3, stride 1")
    ax.semilogy(L, r_pool, "s-", color=common.GREEN, ms=3.5, label="3x3 + 2x2 pool")
    ax.semilogy(L, r_dil, "^-", color=common.RED, ms=3.5, label="3x3, dilation $2^{l-1}$")
    ax.semilogy(L, sd, "--", color=common.GREY, lw=1.2, label="effective width (2 s.d.)")
    ax.set_xlabel("number of layers $L$")
    ax.set_ylabel("receptive field (pixels)")
    ax.legend(fontsize=7, loc="upper left", frameon=False)
    ax.set_xticks([1, 4, 7, 10])
    panel_label(ax, "a", loc="lower right")
    for k, (dils, ttl) in enumerate([([1], "1 layer"), ([1, 1], "2 layers"), ([1] * 3, "3 layers"),
                                     ([1, 2, 4], "3 layers, dilation 1,2,4")]):
        a = fig.add_subplot(gs[k + 1])
        g = _ones_erf(dils)
        n = 17
        G = np.zeros((n, n))
        o = (n - g.shape[0]) // 2
        G[o:o + g.shape[0], o:o + g.shape[1]] = g / g.max()
        a.imshow(G, cmap="magma", vmin=0, vmax=1, interpolation="nearest")
        a.set_title(ttl, fontsize=9)
        a.set_xticks([])
        a.set_yticks([])
    fig.text(0.62, 0.1, "(b) weight of each input pixel in one output unit (all-ones 3x3 filters, 17x17 input window)",
             ha="center", fontsize=8.5)
    return savefig(fig, CH, "fig10-9", out)


def fig_10_10(out=None):
    """VGG-16: feature-map sizes, parameters and connections per learnable layer (computed)."""
    rows = vgg16_counts()
    names = ["c%d" % (i + 1) for i in range(13)] + ["fc1", "fc2", "fc3"]
    conn = np.array([r[0] for r in rows], dtype=float)
    par = np.array([r[1] for r in rows], dtype=float)
    fig, ax = plt.subplots(1, 2, figsize=(10.0, 3.1), gridspec_kw=dict(width_ratios=[1.3, 1]))
    x = np.arange(16)
    ax[0].bar(x - 0.2, conn, 0.4, color=common.BLUE, label="connections (incl. bias)")
    ax[0].bar(x + 0.2, par, 0.4, color=common.RED, label="learnable parameters")
    ax[0].set_yscale("log")
    ax[0].set_xticks(x)
    ax[0].set_xticklabels(names, rotation=90, fontsize=8)
    ax[0].set_ylabel("count per layer")
    ax[0].legend(fontsize=8, frameon=False, loc="upper center", bbox_to_anchor=(0.5, 1.17), ncol=2)
    ax[0].set_ylim(1e3, 1e10)
    sizes = [224, 224, 112, 112, 56, 56, 56, 28, 28, 28, 14, 14, 14]
    ch = [64, 64, 128, 128, 256, 256, 256, 512, 512, 512, 512, 512, 512]
    ax[1].plot(range(13), np.array(sizes) ** 2 * np.array(ch) / 1e6, "o-", color=common.BLUE, ms=4, label="units (millions)")
    ax2 = ax[1].twinx()
    ax2.plot(range(13), ch, "s--", color=common.GREEN, ms=4, label="channels")
    ax[1].set_xticks(range(13))
    ax[1].set_xticklabels(names[:13], rotation=90, fontsize=8)
    ax[1].set_ylabel("units in the feature map (millions)", color=common.BLUE)
    ax2.set_ylabel("channels", color=common.GREEN)
    ax[1].set_title("(b) size of each convolutional layer", fontsize=9)
    fig.tight_layout()
    return savefig(fig, CH, "fig10-10", out)


# =========================================================================== Figures, Section 10.3
def fig_10_11(out=None):
    """Gabor filters (10.6): orientation theta from 0 (top) to pi/2 (bottom), frequency omega 1 to 10."""
    n = 41
    yy, xx = np.mgrid[-1:1:n * 1j, -1:1:n * 1j]
    thetas = np.linspace(0, np.pi / 2, 8)
    omegas = np.linspace(1, 10, 9) * 1.6
    fig, ax = plt.subplots(8, 9, figsize=(6.3, 5.6))
    for i, th in enumerate(thetas):
        for j, om in enumerate(omegas):
            G = gabor(xx, yy, alpha=3.0, beta=3.0, omega=om, phi=np.pi / 2, theta=th)
            ax[i, j].imshow(G, cmap="gray", vmin=-1, vmax=1, interpolation="bilinear")
            ax[i, j].set_xticks([])
            ax[i, j].set_yticks([])
    fig.subplots_adjust(wspace=0.06, hspace=0.06)
    return savefig(fig, CH, "fig10-11", out)


def ica_filters(n_comp=40, patch=10, n_patches=50000, seed=0):
    """Independent component analysis of grey-scale patches of the two sample photographs that ship with
    scikit-learn: the rows of the unmixing matrix are localized, oriented, Gabor-like filters. The
    photographs are first averaged over 2x2 blocks, which removes most of the 8x8 block structure of
    their JPEG compression (otherwise ICA finds the compression grid)."""
    from sklearn.datasets import load_sample_image
    from sklearn.decomposition import FastICA
    rng = np.random.default_rng(seed)
    P = []
    for name in ("china.jpg", "flower.jpg"):
        im = load_sample_image(name).astype(float).mean(2) / 255.0
        im = im[:im.shape[0] // 2 * 2, :im.shape[1] // 2 * 2]
        im = im.reshape(im.shape[0] // 2, 2, im.shape[1] // 2, 2).mean((1, 3))
        H, W = im.shape
        for _ in range(n_patches // 2):
            i, j = rng.integers(0, H - patch), rng.integers(0, W - patch)
            P.append(im[i:i + patch, j:j + patch].ravel())
    P = np.array(P)
    P -= P.mean(1, keepdims=True)
    ica = FastICA(n_components=n_comp, whiten="unit-variance", random_state=seed, max_iter=800, tol=1e-3)
    ica.fit(P)
    return ica.components_.reshape(n_comp, patch, patch)


def fig_10_12(out=None):
    """First-layer filters: the MNIST CNN (a) and ICA of natural-image patches (b)."""
    net = get_cnn()
    W = net.conv1.weight.detach().numpy()[:, 0]
    F = ica_filters()
    fig = plt.figure(figsize=(10.0, 3.3))
    gs = fig.add_gridspec(1, 2, width_ratios=[1, 1.5], wspace=0.12)
    g1 = gs[0].subgridspec(4, 4, wspace=0.08, hspace=0.08)
    for k in range(16):
        a = fig.add_subplot(g1[k // 4, k % 4])
        m = np.abs(W[k]).max()
        a.imshow(W[k], cmap="gray", vmin=-m, vmax=m, interpolation="nearest")
        a.set_xticks([])
        a.set_yticks([])
        if k == 0:
            a.set_title("(a) CNN on MNIST, 5x5", fontsize=9, loc="left")
    g2 = gs[1].subgridspec(4, 10, wspace=0.08, hspace=0.08)
    for k in range(40):
        a = fig.add_subplot(g2[k // 10, k % 10])
        m = np.abs(F[k]).max()
        a.imshow(F[k], cmap="gray", vmin=-m, vmax=m, interpolation="nearest")
        a.set_xticks([])
        a.set_yticks([])
        if k == 0:
            a.set_title("(b) ICA of natural-image patches, 10x10", fontsize=9, loc="left")
    return savefig(fig, CH, "fig10-12", out)


def _layer_maps(net, X):
    """Pre-activations a1, a2, a3 and logits for a batch X (N, 28, 28) as numpy arrays."""
    torch = _torch()
    with torch.no_grad():
        xt = torch.from_numpy(X[:, None].astype(np.float32))
        a1, p1, a2, p2, a3 = net.features(xt)
        lo = net.head(a3)
    return a1.numpy(), a2.numpy(), a3.numpy(), lo.numpy()


def fig_10_13(out=None):
    """Top-9 image patches for four channels in each convolutional layer and for four output units."""
    net = get_cnn()
    X, _ = test_digits()
    X = X[:5000]
    a1, a2, a3, lo = _layer_maps(net, X)
    # receptive fields: conv1 5 (jump 1), conv2 14 (jump 2), conv3 24 (jump 4); 'same' padding offsets 2, 6, 10
    specs = [("layer 1", a1, 5, 1, 2, [0, 3, 6, 9]), ("layer 2", a2, 14, 2, 6, [1, 5, 9, 13]),
             ("layer 3", a3, 24, 4, 10, [2, 7, 12, 20])]
    fig = plt.figure(figsize=(10.4, 3.2))
    outer = fig.add_gridspec(1, 4, wspace=0.12)
    Xp = np.pad(X, ((0, 0), (12, 12), (12, 12)))
    for col, (name, A, r, jump, off, chans) in enumerate(specs):
        inner = outer[col].subgridspec(2, 2, wspace=0.06, hspace=0.06)
        for q, ch in enumerate(chans):
            M = A[:, ch]
            flat = M.reshape(len(M), -1)
            best = flat.max(1)
            imgs = np.argsort(-best)[:9]
            tile = np.zeros((3 * r + 2, 3 * r + 2)) + 0.5
            for t, n in enumerate(imgs):
                p = flat[n].argmax()
                i, j = divmod(p, M.shape[2])
                y0, x0 = i * jump - off + 12, j * jump - off + 12
                tile[(t // 3) * (r + 1):(t // 3) * (r + 1) + r, (t % 3) * (r + 1):(t % 3) * (r + 1) + r] = Xp[n, y0:y0 + r, x0:x0 + r]
            a = fig.add_subplot(inner[q // 2, q % 2])
            a.imshow(tile, cmap="gray", vmin=0, vmax=1, interpolation="nearest")
            a.set_xticks([])
            a.set_yticks([])
        fig.text(0.125 + col * 0.2 + 0.08, 0.93, "%s (%dx%d patches)" % (name, r, r), ha="center", fontsize=9)
    inner = outer[3].subgridspec(2, 2, wspace=0.06, hspace=0.06)
    for q, c in enumerate([0, 3, 5, 8]):
        imgs = np.argsort(-lo[:, c])[:9]
        tile = np.zeros((3 * 29, 3 * 29)) + 0.5
        for t, n in enumerate(imgs):
            tile[(t // 3) * 29:(t // 3) * 29 + 28, (t % 3) * 29:(t % 3) * 29 + 28] = X[n]
        a = fig.add_subplot(inner[q // 2, q % 2])
        a.imshow(tile, cmap="gray", vmin=0, vmax=1, interpolation="nearest")
        a.set_xticks([])
        a.set_yticks([])
    fig.text(0.125 + 3 * 0.2 + 0.08, 0.93, "output units 0, 3, 5, 8", ha="center", fontsize=9)
    return savefig(fig, CH, "fig10-13", out)


def _blur(t, s=0.6):
    torch = _torch()
    k = torch.tensor([math.exp(-0.5 * (i / s) ** 2) for i in (-1, 0, 1)])
    k = (k[:, None] * k[None, :]) / k.sum() ** 2
    return torch.nn.functional.conv2d(t, k[None, None], padding=1)


def class_images(net, lam=0.05, blur_every=0, steps=200, lr=0.05, size=28, seed=0, clip=True):
    """Images maximising the pre-softmax output a^(c) - lam ||x||^2 for each digit class by gradient ascent,
    optionally with periodic blurring and clipping to [0, 1] (Section 10.3.2)."""
    torch = _torch()
    torch.manual_seed(seed)
    out = []
    for c in range(10):
        x = (0.1 * torch.rand(1, 1, size, size)).requires_grad_(True)
        opt = torch.optim.Adam([x], lr=lr)
        for t in range(steps):
            obj = net(x)[0, c] - lam * (x ** 2).sum()
            opt.zero_grad()
            (-obj).backward()
            opt.step()
            with torch.no_grad():
                if blur_every and (t + 1) % blur_every == 0:
                    x.copy_(_blur(x))
                if clip:
                    x.clamp_(0, 1)
        with torch.no_grad():
            p = torch.softmax(net(x), 1)[0, c].item()
        out.append((x.detach().numpy()[0, 0], p))
    return out


def fig_10_14(out=None):
    """Class-maximising images for the ten digits under two regularisation settings."""
    net = get_cnn()
    rows = [class_images(net, lam=0.02, blur_every=0), class_images(net, lam=0.15, blur_every=4)]
    fig, ax = plt.subplots(2, 10, figsize=(10.0, 2.45))
    for r, res in enumerate(rows):
        for c, (img, p) in enumerate(res):
            show_img(ax[r, c], img, vmin=0, vmax=1)
            ax[r, c].set_title("%d: %.2f" % (c, p), fontsize=8)
    ax[0, 0].set_ylabel("weak", fontsize=8.5)
    ax[1, 0].set_ylabel("strong + blur", fontsize=8.5)
    fig.tight_layout(pad=0.3)
    return savefig(fig, CH, "fig10-14", out)


def two_digit_image():
    """A 28 x 56 image with a 3 on the left and a 7 on the right (MNIST test digits)."""
    X, y = test_digits()
    i3 = int(np.where(y == 3)[0][0])
    i7 = int(np.where(y == 7)[0][1])
    return np.concatenate([X[i3], X[i7]], 1), (3, 7)


def fig_10_15(out=None):
    """Grad-CAM saliency maps: two classes in one image, and the book's pre-activation form against the
    post-ReLU form of Selvaraju et al."""
    net = get_cnn()
    P = cnn_params(net)
    img, (c1, c2) = two_digit_image()
    X, y = test_digits()
    fig, ax = plt.subplots(2, 3, figsize=(8.4, 3.7))

    def overlay(a, base, L, ttl):
        a.imshow(base, cmap="gray", vmin=0, vmax=1, interpolation="nearest")
        Lu = np.kron(L, np.ones((4, 4)))
        m = np.abs(Lu).max() or 1.0
        a.imshow(np.maximum(Lu, 0) / m, cmap="jet", alpha=0.45, vmin=0, vmax=1, interpolation="bilinear")
        a.set_title(ttl, fontsize=9)
        a.set_xticks([])
        a.set_yticks([])
    show_img(ax[0, 0], img, "image with a '3' and a '7'")
    lo, _ = np_forward(P, img)
    p = softmax(lo)
    for k, c in enumerate((c1, c2)):
        L, _ = gradcam(P, img, c, "post")
        overlay(ax[0, k + 1], img, L, "Grad-CAM for '%d' (p = %.2f)" % (c, p[c]))
    x0, t0 = X[DEMO_IDX[0]], int(y[DEMO_IDX[0]])
    overlay(ax[1, 0], x0, gradcam(P, x0, t0, "pre")[0], "'%d': book's form (10.10)" % t0)
    overlay(ax[1, 1], x0, gradcam(P, x0, t0, "post")[0], "'%d': post-ReLU maps" % t0)
    x4, t4 = X[DEMO_IDX[4]], int(y[DEMO_IDX[4]])
    overlay(ax[1, 2], x4, gradcam(P, x4, t4, "post")[0], "'%d': post-ReLU maps" % t4)
    fig.tight_layout(pad=0.4)
    return savefig(fig, CH, "fig10-15", out)


def fig_10_16(out=None):
    """An adversarial example by the fast gradient sign method (10.11)."""
    net = get_cnn()
    P = cnn_params(net)
    X, y = test_digits()
    i = DEMO_IDX[0]
    x, t = X[i], int(y[i])
    eps = 0.15
    xa = fgsm(P, x, t, eps)
    p0, pa = softmax(np_forward(P, x)[0]), softmax(np_forward(P, xa)[0])
    d = np.zeros(N_CLASSES)
    d[:] = p0
    d[t] -= 1
    g, _ = np_input_grad(P, x, d)
    fig, ax = plt.subplots(1, 3, figsize=(7.6, 2.9))
    show_img(ax[0], x, "'%s' %.1f%%" % (CLASS_NAMES[t], 100 * p0[t]), vmin=0, vmax=1)
    show_img(ax[1], np.sign(g), "sign of the gradient (x %.2f)" % eps, cmap="RdBu_r", vmin=-1, vmax=1)
    ca = int(pa.argmax())
    show_img(ax[2], xa, "'%s' %.1f%%" % (CLASS_NAMES[ca], 100 * pa[ca]), vmin=0, vmax=1)
    ax[1].text(-4.5, 14, "+", fontsize=18, ha="center", va="center")
    ax[2].text(-4.5, 14, "=", fontsize=18, ha="center", va="center")
    fig.tight_layout()
    return savefig(fig, CH, "fig10-16", out)


def deepdream(net, x, layer, iters, lr=0.01, size=56):
    """Gradient ascent on F(I) = sum a_ijk(I)^2 (10.12) for the pre-activations of conv layer `layer`
    (2 or 3), with normalised steps, light blurring and clipping."""
    torch = _torch()
    nnf = torch.nn.functional
    xt = torch.tensor(np.asarray(x, dtype=np.float32))[None, None]
    xt = nnf.interpolate(xt, size=(size, size), mode="bilinear", align_corners=False).clamp(0, 1)
    xt.requires_grad_(True)
    for _ in range(iters):
        feats = net.features(xt)
        a = feats[2] if layer == 2 else feats[4]
        F = (a ** 2).sum()
        g, = torch.autograd.grad(F, xt)
        with torch.no_grad():
            xt += lr * g / (g.abs().mean() + 1e-12)
            xt.copy_(_blur(xt, 0.5).clamp(0, 1))
    return xt.detach().numpy()[0, 0]


def fig_10_18(out=None):
    """DeepDream on a digit: conv layer 2 and 3, after 5 and 30 iterations."""
    net = get_cnn()
    X, _ = test_digits()
    x = X[DEMO_IDX[3]]
    fig, ax = plt.subplots(2, 3, figsize=(6.4, 4.4))
    for r, layer in enumerate((2, 3)):
        show_img(ax[r, 0], np.asarray(_torch().nn.functional.interpolate(_torch_x(x), size=(56, 56), mode="bilinear",
                                                                          align_corners=False).clamp(0, 1)[0, 0]),
                 "start" if r == 0 else None, vmin=0, vmax=1)
        for k, it in enumerate((5, 30)):
            show_img(ax[r, k + 1], deepdream(net, x, layer, it), ("%d iterations" % it) if r == 0 else None, vmin=0, vmax=1)
        ax[r, 0].set_ylabel("layer %d" % layer, fontsize=9)
    fig.tight_layout(pad=0.4)
    return savefig(fig, CH, "fig10-18", out)


# =========================================================================== Figures, Section 10.4
def fig_10_20(out=None):
    """Intersection-over-union: two boxes, and IoU of two equal squares against their offset."""
    a, b = (1.0, 1.0, 6.0, 5.0), (3.0, 2.5, 8.5, 7.0)
    fig, ax = plt.subplots(1, 3, figsize=(9.6, 3.0), gridspec_kw=dict(width_ratios=[1, 1, 1.2]))
    ix0, iy0, ix1, iy1 = max(a[0], b[0]), max(a[1], b[1]), min(a[2], b[2]), min(a[3], b[3])
    for k in range(2):
        A = ax[k]
        if k == 0:
            A.add_patch(Rectangle((ix0, iy0), ix1 - ix0, iy1 - iy0, fc="#8fd18f", ec="none"))
            A.set_title("area of intersection = %.2f" % ((ix1 - ix0) * (iy1 - iy0)), fontsize=9)
        else:
            for bb in (a, b):
                A.add_patch(Rectangle((bb[0], bb[1]), bb[2] - bb[0], bb[3] - bb[1], fc="#8fd18f", ec="none"))
            ua = (a[2] - a[0]) * (a[3] - a[1]) + (b[2] - b[0]) * (b[3] - b[1]) - (ix1 - ix0) * (iy1 - iy0)
            A.set_title("area of union = %.2f;  IoU = %.3f" % (ua, iou(a, b)), fontsize=9)
        A.add_patch(Rectangle((a[0], a[1]), a[2] - a[0], a[3] - a[1], fc="none", ec=common.RED, lw=2))
        A.add_patch(Rectangle((b[0], b[1]), b[2] - b[0], b[3] - b[1], fc="none", ec=common.BLUE, lw=2))
        A.set_xlim(0, 9.5)
        A.set_ylim(8, 0)
        A.set_aspect("equal")
        A.set_xticks([])
        A.set_yticks([])
        panel_label(A, "ab"[k], loc="lower left")
    d = np.linspace(0, 28, 200)
    s = 28.0
    ax[2].plot(d, [iou((0, 0, s, s), (t, 0, t + s, s)) for t in d], color=common.BLUE,
               label="shift $t$ along one axis: $(s-t)/(s+t)$")
    ax[2].plot(d, [iou((0, 0, s, s), (t, t, t + s, t + s)) for t in d], color=common.RED,
               label="diagonal shift $(t, t)$")
    ax[2].axhline(0.5, color=common.GREY, ls="--", lw=1)
    ax[2].set_xlabel("offset $t$ of a 28x28 box (pixels), $s = 28$")
    ax[2].set_ylabel("IoU")
    ax[2].legend(fontsize=8, frameon=False)
    panel_label(ax[2], "c", loc="upper right")
    fig.tight_layout()
    return savefig(fig, CH, "fig10-20", out)


def digit_canvas(seed=4):
    """A 76 x 120 canvas with four MNIST test digits at fixed positions (top-left corners) and their labels."""
    X, y = test_digits()
    picks = [(DEMO_IDX[0], 6, 8), (DEMO_IDX[4], 40, 30), (DEMO_IDX[5], 8, 62), (DEMO_IDX[9], 44, 88)]
    C = np.zeros((76, 120))
    truth = []
    for i, r, c in picks:
        C[r:r + 28, c:c + 28] = np.maximum(C[r:r + 28, c:c + 28], X[i])
        truth.append((int(y[i]), (c, r, c + 28, r + 28)))
    return C, truth


def sliding_window(net, C, stride=2):
    """Class probabilities for every 28x28 window of the canvas (top-left corners on a grid of step `stride`)."""
    torch = _torch()
    H, W = C.shape
    pos = [(r, c) for r in range(0, H - 27, stride) for c in range(0, W - 27, stride)]
    batch = np.stack([C[r:r + 28, c:c + 28] for r, c in pos])[:, None].astype(np.float32)
    with torch.no_grad():
        p = torch.softmax(net(torch.from_numpy(batch)), 1).numpy()
    return pos, p


def detections(net, C, p_min=0.7, iou_max=0.5, stride=2):
    pos, p = sliding_window(net, C, stride)
    cand, kept = [], []
    for c in range(10):
        boxes = [(cc, r, cc + 28, r + 28) for (r, cc) in pos]
        sc = p[:, c]
        idx = [i for i in range(len(pos)) if sc[i] >= p_min]
        cand += [(c, boxes[i], sc[i]) for i in idx]
        kept += [(c, boxes[i], sc[i]) for i in nms(boxes, sc, p_min, iou_max)]
    return cand, kept


def fig_10_25(out=None):
    """Sliding-window detections before and after non-max suppression."""
    net = get_cnn()
    C, truth = digit_canvas()
    cand, kept = detections(net, C)
    fig, ax = plt.subplots(1, 2, figsize=(9.6, 3.4))
    cols = plt.get_cmap("tab10")
    for k, (A, dets, ttl) in enumerate([(ax[0], cand, "%d windows with p > 0.7" % len(cand)),
                                        (ax[1], kept, "after non-max suppression (IoU > 0.5 removed)")]):
        A.imshow(C, cmap="gray", vmin=0, vmax=1, interpolation="nearest")
        for c, bb, s in dets:
            A.add_patch(Rectangle((bb[0] - 0.5, bb[1] - 0.5), 28, 28, fc="none", ec=cols(c), lw=1.6 if k else 0.7,
                                  alpha=1 if k else 0.7))
            if k:
                A.text(bb[0] + 0.5, bb[1] + 2.5, "%d: %.2f" % (c, s), color="white", fontsize=8,
                       bbox=dict(fc=cols(c), ec="none", pad=1.0))
        A.set_title(ttl, fontsize=9.5)
        A.set_xticks([])
        A.set_yticks([])
    fig.tight_layout()
    return savefig(fig, CH, "fig10-25", out)


# =========================================================================== Figures, Section 10.5
def fig_10_28(out=None):
    """Unpooling: copy (analogue of average pooling) and first-cell (analogue of max-pooling)."""
    Y = np.array([[3, 8], [5, 1]], dtype=float)
    fig, ax = plt.subplots(1, 2, figsize=(8.4, 2.6))
    for k, (U, lab) in enumerate([(unpool_copy(Y), "a"), (unpool_first(Y), "b")]):
        A = ax[k]
        num_grid(A, Y, fs=11, y0=1.0)
        num_grid(A, U, fs=11, x0=4.0)
        A.annotate("", xy=(3.8, 2.0), xytext=(2.25, 2.0), arrowprops=dict(arrowstyle="->", lw=1.4))
        A.set_xlim(-0.2, 8.2)
        A.set_ylim(4.2, -0.2)
        A.set_aspect("equal")
        clean(A)
        A.text(0, 4.1, "(%s)" % lab, fontsize=10, va="bottom")
    return savefig(fig, CH, "fig10-28", out)


def fig_10_29(out=None):
    """Max-unpooling with the switches recorded by the matching max-pooling layer."""
    A = np.array([[1, 6, 2, 0], [4, 3, 9, 5], [7, 2, 1, 8], [0, 5, 3, 2]], dtype=float)
    Y, sw = maxpool(A[None], 2, 2)
    Z = np.array([[2, 4], [7, 3]], dtype=float)   # values arriving at the up-sampling layer
    U = max_unpool(Z[None], sw, (1, 4, 4))[0]
    win = [(int(s) // 4, int(s) % 4) for s in sw[0].ravel()]
    hl = {w: "#fde0dd" for w in win}
    fig, ax = plt.subplots(figsize=(10.0, 2.7))
    num_grid(ax, A, hl=hl, fs=11, title="max-pooling input")
    num_grid(ax, Y[0], fs=11, x0=5.5, y0=1.0, title="pooled")
    ax.text(9.6, 2.0, "intermediate\nlayers", ha="center", va="center", fontsize=9)
    num_grid(ax, Z, fs=11, x0=11.6, y0=1.0, title="to up-sample")
    num_grid(ax, U, hl={w: "#fde0dd" for w in win}, fs=11, x0=15.1, title="max-unpooled")
    for x0, x1 in ((4.2, 5.3), (7.7, 8.5), (10.7, 11.4), (13.8, 14.9)):
        ax.annotate("", xy=(x1, 2.0), xytext=(x0, 2.0), arrowprops=dict(arrowstyle="->", lw=1.3))
    ax.set_xlim(-0.2, 19.3)
    ax.set_ylim(4.2, -0.9)
    ax.set_aspect("equal")
    clean(ax)
    return savefig(fig, CH, "fig10-29", out)


def fig_10_30(out=None):
    """Transposed convolution of a 2x2 input with a 3x3 kernel and output stride 2: a 5x5 output."""
    Z = np.array([[2, -1], [1, 3]], dtype=float)
    K = np.array([[1, 2, 1], [0, 1, 0], [-1, 1, 2]], dtype=float)
    O = conv_transpose2d(Z, K, 2)
    fig, ax = plt.subplots(figsize=(8.6, 3.0))
    num_grid(ax, Z, fs=11, y0=1.5, title="input 2x2", hl={(0, 0): "#fde0dd", (0, 1): "#deebf7"}, colour_cells=False)
    num_grid(ax, K, fs=11, x0=3.2, y0=1.0, title="kernel 3x3", colour_cells=False)
    hl = {}
    for i in range(3):
        for j in range(5):
            if j <= 2:
                hl[(i, j)] = "#fde0dd"
            if j >= 2:
                hl[(i, j)] = "#deebf7" if j > 2 else "#e8d9f0"
    num_grid(ax, O, fs=11, x0=7.5, title="output 5x5 (stride 2)", hl=hl, colour_cells=False)
    ax.annotate("", xy=(7.3, 2.5), xytext=(6.4, 2.5), arrowprops=dict(arrowstyle="->", lw=1.3))
    ax.set_xlim(-0.2, 12.7)
    ax.set_ylim(5.2, -0.9)
    ax.set_aspect("equal")
    clean(ax)
    return savefig(fig, CH, "fig10-30", out)


# =========================================================================== Figures, Section 10.6
def texture(kind, n=56):
    yy, xx = np.mgrid[0:n, 0:n].astype(float)
    if kind == "stripes":
        return 0.5 + 0.5 * np.sin(2 * np.pi * (xx + yy) / 6.0)
    if kind == "dots":
        rng = np.random.default_rng(5)
        img = np.zeros((n, n))
        for _ in range(70):
            cy, cx = rng.uniform(0, n, 2)
            img = np.maximum(img, np.exp(-((yy - cy) ** 2 + (xx - cx) ** 2) / 3.0))
        return img
    raise ValueError(kind)


def style_transfer(net, content, style, steps=300, w_style=1e3, layers=(1, 2, 3), lr=0.03, seed=0):
    """Minimise E_content (10.14) at layer 2 plus a weighted sum of style errors (10.16)-(10.17) over the
    given layers, starting from a random image (Section 10.6)."""
    torch = _torch()
    torch.manual_seed(seed)
    feats = lambda x: [f for k, f in enumerate(net.features(x)) if k in (0, 2, 4)]  # noqa: E731
    C = torch.tensor(content, dtype=torch.float32)[None, None]
    S = torch.tensor(style, dtype=torch.float32)[None, None]
    with torch.no_grad():
        fc = feats(C)
        fs = feats(S)

    def gram_t(a):
        K = a.shape[1]
        am = a.reshape(K, -1)
        return am @ am.T

    Gs = [gram_t(f) for f in fs]
    x = torch.rand(1, 1, *content.shape).requires_grad_(True)
    opt = torch.optim.Adam([x], lr=lr)
    for _ in range(steps):
        fx = feats(x)
        e_c = ((fx[1] - fc[1]) ** 2).sum()
        e_s = 0.0
        for l in layers:
            a = fx[l - 1]
            K, I, J = a.shape[1:]
            e_s = e_s + ((gram_t(a) - Gs[l - 1]) ** 2).sum() / (2.0 * I * J * K) ** 2
        loss = e_c + w_style * e_s
        opt.zero_grad()
        loss.backward()
        opt.step()
        with torch.no_grad():
            x.clamp_(0, 1)
    return x.detach().numpy()[0, 0]


def fig_10_32(out=None):
    """Style transfer at small scale: a digit rendered with the feature statistics of two textures."""
    net = get_cnn()
    X, _ = test_digits()
    torch = _torch()
    c = torch.nn.functional.interpolate(_torch_x(X[DEMO_IDX[1]]), size=(56, 56), mode="bilinear",
                                        align_corners=False).clamp(0, 1).numpy()[0, 0]
    fig, ax = plt.subplots(1, 5, figsize=(10.0, 2.3))
    show_img(ax[0], c, "content", vmin=0, vmax=1)
    for k, kind in enumerate(("stripes", "dots")):
        s = texture(kind)
        show_img(ax[1 + 2 * k], s, "style", vmin=0, vmax=1)
        show_img(ax[2 + 2 * k], style_transfer(net, c, s), "result", vmin=0, vmax=1)
    fig.tight_layout(pad=0.4)
    return savefig(fig, CH, "fig10-32", out)


# =========================================================================== supplementary figures
def shift_response(net, X, shifts):
    """Mean relative change ||f(T x) - f(x)|| / ||f(x)|| of the representation after each stage, for
    horizontal shifts T of the input; and the same after undoing the shift on the conv-1 maps (equivariance)."""
    torch = _torch()
    nnf = torch.nn.functional
    res = {k: [] for k in ("pixels", "conv1", "conv1 shifted back", "pool1", "pool2", "conv3 + global max", "probabilities")}

    def stages(B):
        with torch.no_grad():
            xt = torch.from_numpy(B[:, None].astype(np.float32))
            a1, p1, a2, p2, a3 = net.features(xt)
            g = torch.relu(a3).amax((2, 3))
            pr = torch.softmax(net.fc(g), 1)
        return [xt.numpy(), nnf.relu(a1).numpy(), p1.numpy(), p2.numpy(), g.numpy(), pr.numpy()]
    base = stages(X)

    def rel(a, b):
        a = a.reshape(len(a), -1)
        b = b.reshape(len(b), -1)
        return float(np.mean(np.linalg.norm(a - b, axis=1) / (np.linalg.norm(b, axis=1) + 1e-12)))
    for s in shifts:
        Xs = np.stack([shift_image(x, 0, s) for x in X])
        st = stages(Xs)
        res["pixels"].append(rel(st[0], base[0]))
        res["conv1"].append(rel(st[1], base[1]))
        back = np.roll(st[1], -s, axis=3)
        if s > 0:
            back[..., -s:] = base[1][..., -s:]
        res["conv1 shifted back"].append(rel(back, base[1]))
        res["pool1"].append(rel(st[2], base[2]))
        res["pool2"].append(rel(st[3], base[3]))
        res["conv3 + global max"].append(rel(st[4], base[4]))
        res["probabilities"].append(rel(st[5], base[5]))
    return res


def fig_10_S1(out=None):
    """Equivariance of convolution and growing invariance after pooling, on the trained network."""
    net = get_cnn()
    X, _ = test_digits()
    shifts = list(range(0, 7))
    res = shift_response(net, X[:500], shifts)
    fig, ax = plt.subplots(1, 2, figsize=(9.6, 3.2), gridspec_kw=dict(width_ratios=[1.25, 1]))
    sty = {"pixels": (common.GREY, "o"), "conv1": (common.BLUE, "s"), "conv1 shifted back": (common.CYAN, "D"),
           "pool1": (common.GREEN, "^"), "pool2": (common.ORANGE, "v"), "conv3 + global max": (common.RED, "P"),
           "probabilities": (common.PURPLE, "x")}
    for k, v in res.items():
        ax[0].plot(shifts, v, marker=sty[k][1], color=sty[k][0], ms=4, label=k)
    ax[0].set_xlabel("horizontal shift of the input (pixels)")
    ax[0].set_ylabel(r"mean $\|f(Tx)-f(x)\|\,/\,\|f(x)\|$")
    ax[0].legend(fontsize=7.5, frameon=False, ncol=2)
    panel_label(ax[0], "a", loc="lower right")
    x = X[DEMO_IDX[0]]
    xs = shift_image(x, 0, 4)
    torch = _torch()
    with torch.no_grad():
        f0 = torch.relu(net.features(_torch_x(x))[0])[0, 3].numpy()
        f1 = torch.relu(net.features(_torch_x(xs))[0])[0, 3].numpy()
    show = np.concatenate([x, np.ones((28, 1)), xs, np.ones((28, 2)), f0 / f0.max(), np.ones((28, 1)), f1 / f0.max()], 1)
    ax[1].imshow(show, cmap="gray", vmin=0, vmax=1, interpolation="nearest")
    ax[1].set_xticks([14, 43, 72, 101])
    ax[1].set_xticklabels(["x", "x shifted 4", "conv-1 map", "map of shifted"], fontsize=8)
    ax[1].set_yticks([])
    panel_label(ax[1], "b", loc="lower right")
    fig.tight_layout()
    return savefig(fig, CH, "fig10-s1", out)


def adversarial_curves(net, lin, eps_list, n=1000):
    """Accuracy on the first n test digits under FGSM for the CNN and the linear model, and under random
    sign noise of the same size for the CNN (torch, float32)."""
    torch = _torch()
    X, y = test_digits()
    Xt = torch.from_numpy(X[:n, None].astype(np.float32))
    yt = torch.from_numpy(y[:n]).long()
    g = torch.Generator().manual_seed(11)
    R = torch.randint(0, 2, Xt.shape, generator=g).float() * 2 - 1
    out = {"cnn": [], "linear": [], "cnn random": []}
    for model, key, flat in ((net, "cnn", False), (lin, "linear", True)):
        x = Xt.clone().requires_grad_(True)
        lo = model(x.reshape(n, -1) if flat else x)
        loss = torch.nn.functional.cross_entropy(lo, yt, reduction="sum")
        gx, = torch.autograd.grad(loss, x)
        for e in eps_list:
            xa = (Xt + e * gx.sign()).clamp(0, 1)
            with torch.no_grad():
                p = model(xa.reshape(n, -1) if flat else xa).argmax(1)
            out[key].append(float((p == yt).float().mean()))
    for e in eps_list:
        with torch.no_grad():
            p = net((Xt + e * R).clamp(0, 1)).argmax(1)
        out["cnn random"].append(float((p == yt).float().mean()))
    return out


def fig_10_S2(out=None):
    """Accuracy against epsilon: FGSM on the CNN and on a linear model, and random sign noise."""
    net = get_cnn()
    lin = get_linear()
    eps = np.linspace(0, 0.3, 13)
    r = adversarial_curves(net, lin, eps)
    fig, ax = plt.subplots(figsize=(5.4, 3.3))
    ax.plot(eps, r["cnn"], "o-", color=common.RED, ms=4, label="CNN, FGSM")
    ax.plot(eps, r["linear"], "s-", color=common.BLUE, ms=4, label="linear softmax, FGSM")
    ax.plot(eps, r["cnn random"], "^--", color=common.GREY, ms=4, label="CNN, random signs")
    ax.set_xlabel(r"$\epsilon$ (pixel values in [0, 1])")
    ax.set_ylabel("test accuracy (1000 digits)")
    ax.set_ylim(-0.02, 1.02)
    ax.legend(fontsize=8.5, frameon=False)
    fig.tight_layout()
    return savefig(fig, CH, "fig10-s2", out)


def demo_data(out=None):
    """Export the JSON files used by the browser demos."""
    export_demo_data()


FIGURES = {
    "10.4": fig_10_4, "10.8": fig_10_8, "10.9": fig_10_9, "10.10": fig_10_10, "10.11": fig_10_11,
    "10.12": fig_10_12, "10.13": fig_10_13, "10.14": fig_10_14, "10.15": fig_10_15, "10.16": fig_10_16,
    "10.18": fig_10_18, "10.20": fig_10_20, "10.25": fig_10_25, "10.28": fig_10_28, "10.29": fig_10_29,
    "10.30": fig_10_30, "10.32": fig_10_32, "10.S1": fig_10_S1, "10.S2": fig_10_S2, "data": demo_data,
}

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