"""Murphy (2022), Chapter 15: Neural Networks for Sequences.

Companion code for Chapter 15 of K. P. Murphy, Probabilistic Machine Learning: An Introduction
(MIT Press, 2022; April 2025 draft), pp. 503-544, written from scratch with numpy, scipy, matplotlib and
PyTorch (CPU, one thread), to be read next to the lecture notes (../ch15-neural-networks-sequences.html).

Methods
* Section 15.2, recurrent networks: the vanilla RNN (15.5), the gated recurrent unit written exactly as
  (15.23)-(15.26) (BookGRU, gru_step) and the LSTM (15.27)-(15.32) (lstm_step); character-level language
  models trained by truncated backpropagation through time with teacher forcing (train_lm); state
  Jacobians and the gradient-flow curves of Section 15.2.6 (state_jacobian, grad_flow); greedy decoding,
  temperature sampling and beam search (greedy_decode, beam_search, exhaustive_map), Gumbel-top-k sampling
  without replacement (gumbel_top_k).
* Section 15.3, 1d CNNs: causal dilated convolution and its receptive field (receptive_field).
* Section 15.4, attention: soft dictionary lookup (15.34)-(15.35), kernel regression as attention
  (15.36)-(15.41) (kernel_attention), scaled dot-product attention (15.44) (attention), a sequence-to-sequence
  model with attention on a toy task (Seq2Seq, train_seq2seq).
* Section 15.5, transformers: multi-head attention (15.55)-(15.56) (mha), sinusoidal positional encoding
  (15.57) (positional_encoding), the encoder and decoder blocks (encoder_block), the cost table 15.1
  (cost_table), and a tiny vision transformer on 8x8 digits (TinyViT).
* Section 15.6, efficient transformers: block-local attention, linear attention by associativity (15.69)
  and the positive and trigonometric random-feature approximations of softmax attention (15.64)-(15.68)
  (performer_features, linear_attention).

Data. The text corpus is Carroll (1865), Alice's Adventures in Wonderland (public domain, 136,418
characters of lower-case letters, spaces and full stops, stored in data/ch15-alice.txt), a stand-in for the
book's corpus (The Time Machine, not available offline). Everything else is simulated with fixed seeds, or the
8x8 digits bundled with scikit-learn. All networks are scaled down to CPU size (hidden sizes 32 to 96, a few
thousand optimiser steps): the figures show the mechanisms, not state-of-the-art accuracy.

Figures. Reproduced here: 15.2, 15.12, 15.13, 15.15, 15.17, 15.19, 15.25. Skipped, with the reason:
  15.1, 15.4-15.7, 15.9-15.11, 15.14, 15.16, 15.18, 15.21, 15.24, 15.26   architecture diagrams (nothing is computed);
  15.3, 15.8, 15.20, 15.22, 15.23, 15.28, 15.32-15.36   photographs and screenshots from other papers, or
        diagrams of pretrained models that need data and compute far beyond a CPU;
  15.27  a hand-drawn comparison; replaced by the measured path lengths of Figure 15.S3;
  15.29-15.31  a taxonomy diagram and two sketches of the random-feature factorisation; replaced by
        Figures 15.S6 and 15.S7, which compute the approximation.
Supplementary figures for the gaps filled in the notes:
  15.S1 learning curves (perplexity) of the RNN, GRU and LSTM language models, with a Markov baseline;
  15.S2 gradient flow ||d s_T / d s_{T-k}|| against the lag k for the vanilla RNN, GRU and LSTM;
  15.S3 maximum path length and sequential operations of recurrent, convolutional and attention layers (Table 15.1);
  15.S4 remembering the first symbol after a delay of T steps: RNN, GRU, LSTM, dilated CNN and transformer;
  15.S5 beam search against greedy decoding on the character model, and exact MAP on small trees;
  15.S6 positional-encoding similarity p_t . p_{t+phi} (the Toeplitz structure and the rotation property);
  15.S7 random-feature approximation of the softmax attention matrix (error against the number of features);
  15.S8 a tiny vision transformer on 8x8 digits: patches and the attention of the class token;
  15.S9 seq2seq with and without attention on a string-reversal task (accuracy against length);
  15.S10 spectrum of softmax attention matrices (not low rank).
Run `python3 ch15_neural_networks_sequences.py --list`, `python3 ch15_neural_networks_sequences.py` (all figures,
about ten minutes) or `python3 ch15_neural_networks_sequences.py --fig 15.2`. Files go to ../img/ch15/; the
data used by the browser demonstrations go to ../data/ch15-*.json. Trained weights are cached in cache/.
"""
import itertools
import json
import math
import os
import sys
import time

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

import numpy as np
from scipy import special

sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
import common  # noqa: E402
from common import BLUE, CYAN, GREEN, GREY, MAGENTA, ORANGE, PURPLE, RED, plt, savefig  # noqa: E402

CH = 15
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)
sigmoid = common.sigmoid
softmax = lambda a, axis=-1: np.exp(a - special.logsumexp(a, axis=axis, keepdims=True))


def torch_mod():
    return common.torch_setup(0, 1)


def dump_json(name, obj):
    os.makedirs(DATA_OUT, exist_ok=True)
    path = os.path.join(DATA_OUT, name)
    with open(path, "w") as f:
        json.dump(obj, f, separators=(",", ":"))
    print("wrote", os.path.relpath(path, os.getcwd()), "(%d bytes)" % os.path.getsize(path))


def r4(a, nd=4):
    return np.round(np.asarray(a, float), nd).tolist()


# =========================================================================== numpy recurrent cells
# Row-vector convention as in the book: x is 1 x D, h is 1 x H; weights are D x H and H x H.
def rnn_step(h, x, P):
    """Vanilla RNN, (15.5): h_t = tanh(x W_xh + h W_hh + b_h)."""
    z = x @ P["Wxh"] + h @ P["Whh"] + P["bh"]
    return z if P.get("linear") else np.tanh(z)


def gru_step(h, x, P):
    """Gated recurrent unit, exactly (15.23)-(15.26): reset R, update Z, candidate, new state."""
    R = sigmoid(x @ P["Wxr"] + h @ P["Whr"] + P["br"])
    Z = sigmoid(x @ P["Wxz"] + h @ P["Whz"] + P["bz"])
    Hc = np.tanh(x @ P["Wxh"] + (R * h) @ P["Whh"] + P["bh"])
    return Z * h + (1.0 - Z) * Hc


def lstm_step(h, c, x, P):
    """LSTM, (15.27)-(15.32): output O, input I, forget F gates, candidate cell, cell and hidden state."""
    O = sigmoid(x @ P["Wxo"] + h @ P["Who"] + P["bo"])
    I = sigmoid(x @ P["Wxi"] + h @ P["Whi"] + P["bi"])
    F = sigmoid(x @ P["Wxf"] + h @ P["Whf"] + P["bf"])
    Ct = np.tanh(x @ P["Wxc"] + h @ P["Whc"] + P["bc"])
    c2 = F * c + I * Ct
    return O * np.tanh(c2), c2


def rand_params(arch, Dx, H, seed, gain=1.0, rho=None, bias=0.0):
    """Random cell parameters for the gradient-flow experiments.

    Every weight matrix is gain * Z / sqrt(fan_in) with Z standard normal; biases are 0 except the
    forget-gate bias of the LSTM and the update-gate bias of the GRU, both set to `bias`. For the
    vanilla RNN, W_hh is rescaled to have spectral radius exactly rho."""
    rng = np.random.default_rng(seed)
    mk = lambda a, b: gain * rng.standard_normal((a, b)) / math.sqrt(a)
    if arch == "rnn":
        W = rng.standard_normal((H, H)) / math.sqrt(H)
        W = W / np.max(np.abs(np.linalg.eigvals(W)))
        return {"Wxh": mk(Dx, H), "Whh": (1.0 if rho is None else rho) * W, "bh": np.zeros(H)}
    if arch == "gru":
        P = {}
        for g in "rzh":
            P["Wx" + g], P["Wh" + g], P["b" + g] = mk(Dx, H), mk(H, H), np.zeros(H)
        P["bz"] = np.full(H, float(bias))
        return P
    P = {}
    for g in "oifc":
        P["Wx" + g], P["Wh" + g], P["b" + g] = mk(Dx, H), mk(H, H), np.zeros(H)
    P["bf"] = np.full(H, float(bias))
    return P


def run_cell(arch, P, X):
    """Run a cell over the rows of X (T x Dx) from the zero state; returns the list of states
    (state = h for rnn and gru, concatenated [h, c] for lstm) including the initial state."""
    H = P["Whh"].shape[0] if arch != "lstm" else P["Whc"].shape[0]
    h, c = np.zeros(H), np.zeros(H)
    S = [np.r_[h, c] if arch == "lstm" else h.copy()]
    for x in X:
        if arch == "rnn":
            h = rnn_step(h, x, P)
        elif arch == "gru":
            h = gru_step(h, x, P)
        else:
            h, c = lstm_step(h, c, x, P)
        S.append(np.r_[h, c] if arch == "lstm" else h.copy())
    return S


def state_jacobian_fd(arch, P, s_prev, x, eps=1e-6):
    """One-step state Jacobian A = d s_t / d s_{t-1} (rows: new state) by central differences (used to
    confirm the closed forms below)."""
    n = len(s_prev)
    H = n // 2 if arch == "lstm" else n

    def step(s):
        if arch == "rnn":
            return rnn_step(s, x, P)
        if arch == "gru":
            return gru_step(s, x, P)
        h2, c2 = lstm_step(s[:H], s[H:], x, P)
        return np.r_[h2, c2]
    A = np.zeros((n, n))
    for j in range(n):
        d = np.zeros(n)
        d[j] = eps
        A[:, j] = (step(s_prev + d) - step(s_prev - d)) / (2 * eps)
    return A


def state_jacobian(arch, P, s_prev, x):
    """Closed-form one-step state Jacobian d s_t / d s_{t-1} (column-vector convention, rows = new state):
    RNN: diag(phi') W_hh^T; GRU: the three-term formula of the notes (gap 15.8); LSTM: the 2 x 2 block matrix
    of the notes (gap 15.9) with the cell block diag(F_t)."""
    if arch == "rnn":
        z = x @ P["Wxh"] + s_prev @ P["Whh"] + P["bh"]
        d = np.ones_like(z) if P.get("linear") else 1 - np.tanh(z) ** 2
        return d[:, None] * P["Whh"].T
    if arch == "gru":
        h = s_prev
        R = sigmoid(x @ P["Wxr"] + h @ P["Whr"] + P["br"])
        Z = sigmoid(x @ P["Wxz"] + h @ P["Whz"] + P["bz"])
        Hc = np.tanh(x @ P["Wxh"] + (R * h) @ P["Whh"] + P["bh"])
        dRh = np.diag(R) + (h * R * (1 - R))[:, None] * P["Whr"].T
        return (np.diag(Z) + ((h - Hc) * Z * (1 - Z))[:, None] * P["Whz"].T
                + ((1 - Z) * (1 - Hc ** 2))[:, None] * (P["Whh"].T @ dRh))
    H = len(s_prev) // 2
    h, c = s_prev[:H], s_prev[H:]
    O = sigmoid(x @ P["Wxo"] + h @ P["Who"] + P["bo"])
    I = sigmoid(x @ P["Wxi"] + h @ P["Whi"] + P["bi"])
    F = sigmoid(x @ P["Wxf"] + h @ P["Whf"] + P["bf"])
    Ct = np.tanh(x @ P["Wxc"] + h @ P["Whc"] + P["bc"])
    c2 = F * c + I * Ct
    dc_dh = ((c * F * (1 - F))[:, None] * P["Whf"].T + (Ct * I * (1 - I))[:, None] * P["Whi"].T
             + (I * (1 - Ct ** 2))[:, None] * P["Whc"].T)
    g = O * (1 - np.tanh(c2) ** 2)
    dh_dh = (np.tanh(c2) * O * (1 - O))[:, None] * P["Who"].T + g[:, None] * dc_dh
    dh_dc = g * F
    return np.block([[dh_dh, np.diag(dh_dc)], [dc_dh, np.diag(F)]])


def grad_flow(arch, P, X):
    """Spectral norms ||d s_T / d s_{T-k}||_2 for k = 0, 1, ..., T-1 along the trajectory driven by X.

    d s_T / d s_t = A_T A_{T-1} ... A_{t+1} (the chain rule behind (15.22)); the k = 0 entry is 1."""
    S = run_cell(arch, P, X)
    T = len(X)
    J = np.eye(len(S[0]))
    out = [1.0]
    for t in range(T, 1, -1):
        A = state_jacobian(arch, P, S[t - 1], X[t - 1])
        J = J @ A
        out.append(np.linalg.norm(J, 2))
    return np.array(out)


# =========================================================================== text data
def alice():
    """The corpus (lower-case letters, spaces and full stops) and the start of the held-out last 10%."""
    with open(os.path.join(HERE, "data", "ch15-alice.txt")) as f:
        t = f.read().strip()
    split = t.index(" ", int(0.9 * len(t))) + 1
    return t, split


def vocab_of(t):
    chars = sorted(set(t))
    return chars, {c: i for i, c in enumerate(chars)}


def markov_perplexity(text, split, order, alpha=0.1):
    """Held-out perplexity of an order-k character Markov model with add-alpha smoothing
    (Section 3.6.1 of the book), fitted on text[:split]."""
    chars, idx = vocab_of(text)
    V = len(chars)
    a = np.array([idx[c] for c in text])
    counts = {}
    for i in range(order, split):
        key = tuple(a[i - order:i])
        row = counts.setdefault(key, np.zeros(V))
        row[a[i]] += 1
    nll, n = 0.0, 0
    for i in range(max(split, order), len(a)):
        row = counts.get(tuple(a[i - order:i]), np.zeros(V))
        p = (row[a[i]] + alpha) / (row.sum() + alpha * V)
        nll -= math.log(p)
        n += 1
    return math.exp(nll / n)


# =========================================================================== torch language models
def _torch_models():
    torch = torch_mod()
    import torch.nn as nn

    class BookGRU(nn.Module):
        """GRU with the reset gate applied before the matrix product, exactly (15.23)-(15.26)."""

        def __init__(self, V, H):
            super().__init__()
            s = 1.0 / math.sqrt(H)
            self.V, self.H = V, H
            self.Wx = nn.Parameter(torch.randn(V, 3 * H) * s)
            self.Whrz = nn.Parameter(torch.randn(H, 2 * H) * s)
            self.Whh = nn.Parameter(torch.randn(H, H) * s)
            self.b = nn.Parameter(torch.zeros(3 * H))

        def forward(self, idx, h=None):
            B, T = idx.shape
            H = self.H
            h = torch.zeros(B, H) if h is None else h
            xs = self.Wx[idx]   # one-hot x W_x as a table lookup
            out = []
            for t in range(T):
                xr, xz, xh = xs[:, t, :H], xs[:, t, H:2 * H], xs[:, t, 2 * H:]
                rz = h @ self.Whrz
                R = torch.sigmoid(xr + rz[:, :H] + self.b[:H])
                Z = torch.sigmoid(xz + rz[:, H:] + self.b[H:2 * H])
                Hc = torch.tanh(xh + (R * h) @ self.Whh + self.b[2 * H:])
                h = Z * h + (1 - Z) * Hc
                out.append(h)
            return torch.stack(out, 1), h

    class CharLM(nn.Module):
        def __init__(self, kind, V, H):
            super().__init__()
            self.kind, self.V, self.H = kind, V, H
            if kind == "gru":
                self.core = BookGRU(V, H)
            elif kind == "lstm":
                self.core = nn.LSTM(V, H, batch_first=True)
            else:
                self.core = nn.RNN(V, H, nonlinearity="tanh", batch_first=True)
            self.out = nn.Linear(H, V)

        def forward(self, idx):
            if self.kind == "gru":
                o, _ = self.core(idx)
            else:
                o, _ = self.core(nn.functional.one_hot(idx, self.V).float())
            return self.out(o)

    return torch, nn, BookGRU, CharLM


def train_lm(kind, steps=1500, H=80, seq=64, batch=32, lr=5e-3, seed=0, force=False):
    """Train a character language model by truncated BPTT with teacher forcing (Sections 15.2.4, 15.2.5).

    Windows of `seq` characters are drawn at random from the first 90% of the text, so the hidden
    state starts from zero at each window; gradients are clipped to norm 1 (Section 13.4.2). Returns
    (model, curve) with curve = [(step, train_ppl, val_ppl)], cached in cache/."""
    torch, nn, BookGRU, CharLM = _torch_models()
    path = os.path.join(CACHE_DIR, "ch15_lm_%s_H%d_s%d.pt" % (kind, H, steps))
    text, split = alice()
    chars, idx = vocab_of(text)
    V = len(chars)
    a = torch.tensor([idx[c] for c in text])
    torch.manual_seed(seed)
    model = CharLM(kind, V, H)
    if os.path.exists(path) and not force:
        d = torch.load(path)
        model.load_state_dict(d["state"])
        return model, d["curve"]
    opt = torch.optim.Adam(model.parameters(), lr=lr)
    rng = np.random.default_rng(seed)
    nv = (len(a) - split - 1) // seq
    vx = torch.stack([a[split + i * seq: split + i * seq + seq] for i in range(nv)])
    vy = torch.stack([a[split + i * seq + 1: split + i * seq + seq + 1] for i in range(nv)])
    ce = nn.CrossEntropyLoss()
    curve, run = [], []
    for step in range(1, steps + 1):
        st = rng.integers(0, split - seq - 1, batch)
        x = torch.stack([a[s:s + seq] for s in st])
        y = torch.stack([a[s + 1:s + seq + 1] for s in st])
        loss = ce(model(x).reshape(-1, V), y.reshape(-1))
        opt.zero_grad()
        loss.backward()
        nn.utils.clip_grad_norm_(model.parameters(), 1.0)
        opt.step()
        run.append(loss.item())
        if step % 50 == 0 or step == 1:
            with torch.no_grad():
                vl = ce(model(vx).reshape(-1, V), vy.reshape(-1)).item()
            curve.append((step, math.exp(float(np.mean(run[-50:]))), math.exp(vl)))
    torch.save({"state": model.state_dict(), "curve": curve}, path)
    return model, curve


def gru_params_np(model, rounding=4):
    """The trained BookGRU character model as numpy arrays (rounded), in the layout of gru_step."""
    H, V = model.core.H, model.core.V
    Wx = model.core.Wx.detach().numpy()
    Whrz = model.core.Whrz.detach().numpy()
    b = model.core.b.detach().numpy()
    P = {"Wxr": Wx[:, :H], "Wxz": Wx[:, H:2 * H], "Wxh": Wx[:, 2 * H:],
         "Whr": Whrz[:, :H], "Whz": Whrz[:, H:], "Whh": model.core.Whh.detach().numpy(),
         "br": b[:H], "bz": b[H:2 * H], "bh": b[2 * H:],
         "Wy": model.out.weight.detach().numpy().T, "by": model.out.bias.detach().numpy()}
    return {k: np.round(np.asarray(v, float), rounding) for k, v in P.items()}


class CharModel:
    """Numpy (float64) forward pass of the trained GRU character model; gives p(y_t | y_{<t})."""

    def __init__(self, P, chars):
        self.P, self.chars = P, chars
        self.idx = {c: i for i, c in enumerate(chars)}
        self.V = len(chars)
        self.H = P["Whh"].shape[0]

    def step(self, h, ci):
        R = sigmoid(self.P["Wxr"][ci] + h @ self.P["Whr"] + self.P["br"])
        Z = sigmoid(self.P["Wxz"][ci] + h @ self.P["Whz"] + self.P["bz"])
        Hc = np.tanh(self.P["Wxh"][ci] + (R * h) @ self.P["Whh"] + self.P["bh"])
        h2 = Z * h + (1 - Z) * Hc
        logits = h2 @ self.P["Wy"] + self.P["by"]
        return h2, logits - special.logsumexp(logits)

    def feed(self, text, h=None):
        """Feed a string; returns the final hidden state and log p(next char) after it."""
        h = np.zeros(self.H) if h is None else h
        lp = None
        for ch in text:
            h, lp = self.step(h, self.idx[ch])
        return h, lp

    def greedy(self, prefix, n):
        h, lp = self.feed(prefix)
        out, tot = "", 0.0
        for _ in range(n):
            j = int(np.argmax(lp))
            tot += lp[j]
            out += self.chars[j]
            h, lp = self.step(h, j)
        return out, tot

    def sample(self, prefix, n, temperature, rng):
        h, lp = self.feed(prefix)
        out = ""
        for _ in range(n):
            p = softmax(lp / temperature)
            j = int(rng.choice(self.V, p=p))
            out += self.chars[j]
            h, lp = self.step(h, j)
        return out

    def beam(self, prefix, n, K):
        """Beam search of width K for n further characters; returns (best string, its log-probability).

        Candidates are ranked by total log-probability; all sequences have the same length so no length
        normalisation is needed (Section 15.2.8)."""
        h0, lp0 = self.feed(prefix)
        beams = [("", 0.0, h0, lp0)]
        for _ in range(n):
            cand = []
            for s, sc, h, lp in beams:
                top = np.argsort(-lp)[:K]
                for j in top:
                    cand.append((s + self.chars[j], sc + lp[j], h, int(j)))
            cand.sort(key=lambda c: -c[1])
            nb = []
            for s, sc, h, j in cand[:K]:
                h2, lp2 = self.step(h, j)
                nb.append((s, sc, h2, lp2))
            beams = nb
        best = max(beams, key=lambda b: b[1])
        return best[0], best[1]

    def seq_logprob(self, prefix, cont):
        h, lp = self.feed(prefix)
        tot = 0.0
        for ch in cont:
            tot += lp[self.idx[ch]]
            h, lp = self.step(h, self.idx[ch])
        return tot


# =========================================================================== decoding (Section 15.2.8)
def beam_search(logp_fn, V, K, T, eos=None):
    """Beam search of width K (Section 15.2.8) for a model given by logp_fn(prefix) -> log p(next | prefix).

    prefix is a tuple of token indices. A hypothesis that has emitted `eos` is finished: it keeps its
    score and is not expanded. Returns (steps, best) where steps[t] is the list of candidates
    (prefix, log-probability, kept) at step t+1 sorted by score and best = (prefix, log-probability)
    of the highest-scoring hypothesis in the final beam."""
    beam = [((), 0.0)]
    steps = []
    for _ in range(T):
        cand = []
        for pre, sc in beam:
            if eos is not None and pre and pre[-1] == eos:
                cand.append((pre, sc))
                continue
            lp = logp_fn(pre)
            for j in range(V):
                cand.append((pre + (j,), sc + float(lp[j])))
        cand.sort(key=lambda c: -c[1])
        beam = cand[:K]
        kept = {c[0] for c in beam}
        steps.append([(p, s, p in kept) for p, s in cand])
    best = max(beam, key=lambda c: c[1])
    return steps, best


def exhaustive_map(logp_fn, V, T, eos=None):
    """The MAP sequence argmax p(y_{1:T}) by enumerating all V^T sequences (O(V^T) calls, Section 15.2.8)."""
    best = ((), -np.inf)

    def rec(pre, sc):
        nonlocal best
        if len(pre) == T or (eos is not None and pre and pre[-1] == eos):
            if sc > best[1]:
                best = (pre, sc)
            return
        lp = logp_fn(pre)
        for j in range(V):
            rec(pre + (j,), sc + float(lp[j]))
    rec((), 0.0)
    return best


def greedy_path(logp_fn, T, eos=None):
    pre, sc = (), 0.0
    for _ in range(T):
        lp = logp_fn(pre)
        j = int(np.argmax(lp))
        pre, sc = pre + (j,), sc + float(lp[j])
        if eos is not None and j == eos:
            break
    return pre, sc


def book_toy_model():
    """The four-token example of Figure 15.12 (tokens A, B, C, eos): the conditional distributions quoted in
    the text are used where the book gives them; every other prefix gets the uniform distribution (my
    choice). The distribution of y_1 is also my choice (the book only says that A is the most probable)."""
    table = {
        (): [0.5, 0.25, 0.15, 0.10],
        (0,): [0.1, 0.4, 0.3, 0.2],
        (0, 1): [0.2, 0.2, 0.4, 0.2],
        (0, 1, 2): [0.0, 0.2, 0.2, 0.6],
        (0, 2): [0.1, 0.6, 0.2, 0.1],
        (0, 2, 1): [0.1, 0.2, 0.1, 0.6],
    }

    def logp(pre):
        p = np.array(table.get(tuple(pre), [0.25] * 4), float)
        with np.errstate(divide="ignore"):
            return np.log(p)
    return logp, table


def random_tree_model(V, seed, alpha=0.6):
    """A deterministic random conditional distribution p(y_t | y_{<t}) (Dirichlet(alpha) rows, seeded by the prefix)."""
    def logp(pre):
        s = seed * 1000003 + 17
        for j in pre:
            s = (s * 31 + int(j) + 1) % (2 ** 31 - 1)
        p = np.random.default_rng(s).dirichlet(alpha * np.ones(V))
        return np.log(np.maximum(p, 1e-12))
    return logp


def gumbel_top_k(logp, k, rng):
    """Indices of the k largest of log p_i + G_i, G_i i.i.d. standard Gumbel: a sample of size k from the
    categorical distribution p without replacement (Plackett-Luce), the idea of stochastic beam search."""
    g = -np.log(-np.log(rng.random(len(logp))))
    return list(np.argsort(-(np.asarray(logp) + g))[:k])


def plackett_luce_prob(p, order):
    """Probability that sampling without replacement from p produces the ordered tuple `order`."""
    p = np.asarray(p, float)
    rest, out = 1.0, 1.0
    for i in order:
        out *= p[i] / rest
        rest -= p[i]
    return out


# =========================================================================== 1d convolutions (Section 15.3)
def causal_conv1d(x, w, dilation=1):
    """y_t = sum_{j=0}^{k-1} w_j x_{t - j*dilation} with zero left padding: each output sees only the past.
    x: (T, Cin); w: (k, Cin, Cout)."""
    T, Cin = x.shape
    k, _, Cout = w.shape
    y = np.zeros((T, Cout))
    for j in range(k):
        s = j * dilation
        if s < T:
            y[s:] += x[:T - s] @ w[j]
    return y


def receptive_field(kernel, dilations):
    """Size of the receptive field of a stack of causal convolutions with the given dilations:
    1 + (kernel - 1) * sum(dilations)."""
    return 1 + (kernel - 1) * int(sum(dilations))


# =========================================================================== attention (Section 15.4)
def attention(Q, K, V, mask=None, scale=True):
    """Scaled dot-product attention (15.44): softmax(Q K^T / sqrt(d)) V. mask (n x m, True = allowed) is
    applied by adding -1e6 to the scores of disallowed entries (Section 15.4.1). Returns (output, weights)."""
    S = Q @ K.T
    if scale:
        S = S / math.sqrt(Q.shape[1])
    if mask is not None:
        S = np.where(mask, S, S - 1e6)
    A = softmax(S, axis=1)
    return A @ V, A


def kernel_attention(xq, xk, yk, beta=1.0):
    """Nadaraya-Watson kernel regression as attention, (15.36)-(15.41): alpha_i = softmax_i(-(beta (x - x_i))^2 / 2).
    Returns predictions at the points xq and the attention matrix A[j, i]."""
    S = -0.5 * (beta * (xq[:, None] - xk[None, :])) ** 2
    A = softmax(S, axis=1)
    return A @ yk, A


def additive_score(q, k, Wq, Wk, wv):
    """Additive attention score (15.42): w_v^T tanh(W_q q + W_k k)."""
    return float(wv @ np.tanh(Wq @ q + Wk @ k))


def positional_encoding(n, d, C=10000.0):
    """Sinusoidal positional encoding (15.57): P[i, 2j] = sin(i / C^(2j/d)), P[i, 2j+1] = cos(i / C^(2j/d))."""
    P = np.zeros((n, d))
    i = np.arange(n)[:, None]
    w = 1.0 / C ** (2 * np.arange(d // 2) / d)
    P[:, 0::2] = np.sin(i * w)
    P[:, 1::2] = np.cos(i * w)
    return P


def pe_rotation(phi, d, C=10000.0):
    """The block-diagonal matrix R(phi) of (15.59)-(15.60) with p_{t+phi} = R(phi) p_t (applied to p as a column)."""
    w = 1.0 / C ** (2 * np.arange(d // 2) / d)
    R = np.zeros((d, d))
    for k, wk in enumerate(w):
        c, s = math.cos(wk * phi), math.sin(wk * phi)
        # rows: [sin(w(t+phi)), cos(w(t+phi))] = [[c, s], [-s, c]] [sin(wt), cos(wt)]
        R[2 * k:2 * k + 2, 2 * k:2 * k + 2] = [[c, s], [-s, c]]
    return R


def layer_norm(x, eps=1e-5):
    m = x.mean(-1, keepdims=True)
    v = x.var(-1, keepdims=True)
    return (x - m) / np.sqrt(v + eps)


def mha(Xq, Xkv, Wq, Wk, Wv, Wo, heads, mask=None):
    """Multi-head attention (15.55)-(15.56). Xq: n x dq, Xkv: m x dk; Wq/Wk/Wv: (dmodel x heads*p) so that all
    heads are computed together and split; Wo: (heads*p) x po. Returns (output n x po, per-head weights)."""
    Q, K, V = Xq @ Wq, Xkv @ Wk, Xkv @ Wv
    p = Q.shape[1] // heads
    outs, atts = [], []
    for i in range(heads):
        sl = slice(i * p, (i + 1) * p)
        o, A = attention(Q[:, sl], K[:, sl], V[:, sl], mask)
        outs.append(o)
        atts.append(A)
    return np.concatenate(outs, 1) @ Wo, np.array(atts)


def encoder_block(X, P, heads, mask=None):
    """EncoderBlock of Section 15.5.4: Z = LN(MHA(X, X, X) + X); E = LN(FF(Z) + Z)."""
    A, _ = mha(X, X, P["Wq"], P["Wk"], P["Wv"], P["Wo"], heads, mask)
    Z = layer_norm(A + X)
    FF = np.maximum(Z @ P["W1"] + P["b1"], 0) @ P["W2"] + P["b2"]
    return layer_norm(FF + Z)


def rand_block_params(d, dff, seed):
    rng = np.random.default_rng(seed)
    g = lambda a, b: rng.standard_normal((a, b)) / math.sqrt(a)
    return {"Wq": g(d, d), "Wk": g(d, d), "Wv": g(d, d), "Wo": g(d, d), "W1": g(d, dff), "b1": np.zeros(dff),
            "W2": g(dff, d), "b2": np.zeros(d)}


def cost_table(n, d, k=3):
    """Multiply-add counts of one layer mapping n vectors of dimension d to n vectors of dimension d
    (Table 15.1, constants included): self-attention scores and weighted sum 2 n^2 d (projections 4 n d^2 not
    counted), recurrent n steps of (W_xh, W_hh) 2 d^2 each, convolution k n d^2 per layer (dilated stack of
    ceil(log_k n) layers for the path length)."""
    return {"attention": 2 * n * n * d, "recurrent": 2 * n * d * d, "conv": k * n * d * d,
            "attn_sequential": 1, "rnn_sequential": n, "conv_sequential": 1}


def path_length(layer, n, k=2):
    """Maximum path length between any two positions (Table 15.1): attention 1; recurrent n steps (x_1 -> h_1 -> ... -> h_n);
    stack of dilated causal convolutions with kernel k and dilations k^l: ceil(log_k n) layers;
    undilated stack: ceil((n - 1) / (k - 1)) layers."""
    if layer == "attention":
        return 1
    if layer == "recurrent":
        return n
    if layer == "conv_dilated":
        return int(math.ceil(math.log(n) / math.log(k) - 1e-12))
    return int(math.ceil((n - 1) / (k - 1)))


# =========================================================================== efficient attention (Section 15.6)
def blocks_mask(n, K):
    """Block-diagonal mask: n tokens in K blocks of n/K, attention only inside a block (Section 15.6.1)."""
    b = n // K
    ids = np.arange(n) // b
    return ids[:, None] == ids[None, :]


def performer_features(X, W, kind="positive"):
    """Random features eta(x) with E[eta(x)^T eta(y)] = exp(-||x - y||^2 / 2) (Gaussian kernel (15.63)):
    'trig': eta = M^{-1/2} [sin(Wx), cos(Wx)]  (15.65 with the trigonometric features),
    'positive': eta = M^{-1/2} exp(Wx - ||x||^2)  (positive features).
    Multiplying by exp(||x||^2 / 2) gives phi with E[phi(x)^T phi(y)] = exp(x^T y), cf. (15.64)-(15.67)."""
    M = W.shape[0]
    Z = X @ W.T
    sq = (X ** 2).sum(1, keepdims=True)
    if kind == "trig":
        eta = np.concatenate([np.sin(Z), np.cos(Z)], 1) / math.sqrt(M)
    else:
        eta = np.exp(Z - sq) / math.sqrt(M)
    return np.exp(0.5 * sq) * eta


def softmax_attention_matrix(Q, K):
    S = Q @ K.T / math.sqrt(Q.shape[1])
    return softmax(S, axis=1)


def linear_attention(Qp, Kp, V):
    """(15.69): diag^{-1}(Q'(K'^T 1)) (Q'(K'^T V)) in O(N M d) time: the N x N matrix is never formed."""
    num = Qp @ (Kp.T @ V)
    den = Qp @ Kp.sum(0)
    return num / den[:, None]


def performer_attention(Q, K, V, M, rng, kind="positive", orthogonal=False):
    """Softmax attention approximated with M random features (Section 15.6.4)."""
    D = Q.shape[1]
    W = rng.standard_normal((M, D))
    if orthogonal:
        W = orthogonal_features(M, D, rng)
    Qs, Ks = Q / D ** 0.25, K / D ** 0.25
    return linear_attention(performer_features(Qs, W, kind), performer_features(Ks, W, kind), V)


def orthogonal_features(M, D, rng):
    """M x D matrix whose rows are orthogonal within blocks of D (rows rescaled to chi-distributed norms),
    the 'orthogonal random features' of Choromanski et al. (2020), used to lower the variance."""
    blocks = []
    for _ in range(int(math.ceil(M / D))):
        G = rng.standard_normal((D, D))
        Qm, _ = np.linalg.qr(G)
        norms = np.sqrt(rng.chisquare(D, D))
        blocks.append(Qm.T * norms[:, None])
    return np.concatenate(blocks, 0)[:M]


# =========================================================================== shared experiment data
def kr_pool():
    """100 candidate inputs x ~ U(0, 5) and 100 standard normal noise draws (seeded): the data of the kernel-regression
    figure and demonstration use the first n of them, sorted by x."""
    rng = np.random.default_rng(15)
    return np.round(rng.uniform(0, 5, 100), 6), np.round(rng.standard_normal(100), 6)


def kr_truth(x):
    return 2 * np.sin(x) + x ** 0.8


def kr_data(n=50, sd=0.5):
    xp, zp = kr_pool()
    x, z = xp[:n], zp[:n]
    o = np.argsort(x)
    x, z = x[o], z[o]
    return x, kr_truth(x) + sd * z


def loo_kernel_error(x, y, beta):
    """Leave-one-out mean squared error of the Nadaraya-Watson estimator (closed form: drop the diagonal weight)."""
    S = -0.5 * (beta * (x[:, None] - x[None, :])) ** 2
    np.fill_diagonal(S, -np.inf)
    A = softmax(S, axis=1)
    return float(np.mean((A @ y - y) ** 2))


GF_T, GF_DX, GF_H, GF_SEED = 60, 4, 8, 3


def gf_inputs():
    return np.random.default_rng(1).standard_normal((GF_T, GF_DX))



def gf_base(arch):
    """Base parameters of the gradient-flow experiment (rounded to 6 decimals, exported to the demonstration):
    weights Z / sqrt(fan_in); for the RNN, W_hh has spectral radius 1. gf_params scales them."""
    a = "rnn" if arch.startswith("rnn") else arch
    P = rand_params(a, GF_DX, GF_H, GF_SEED, gain=1.0, rho=1.0, bias=0.0)
    return {k: np.round(v, 6) for k, v in P.items()}


def gf_params(arch, rho=1.0, gain=1.0, bias=0.0):
    B = gf_base(arch)
    if arch.startswith("rnn"):
        P = {"Wxh": gain * B["Wxh"], "Whh": rho * B["Whh"], "bh": B["bh"].copy()}
        if arch == "rnnlin":
            P["linear"] = True
        return P
    P = {k: (gain * v if k[0] == "W" else v.copy()) for k, v in B.items()}
    P["bz" if arch == "gru" else "bf"] = np.full(GF_H, float(bias))
    return P


def gf_curve(arch, rho=1.0, gain=1.0, bias=0.0):
    """Gradient-flow curve of Section 15.2.6 (log10 of ||d s_T / d s_{T-k}||_2, k = 0..T-1) for one setting.
    arch: 'rnnlin' (identity activation), 'rnn' (tanh), 'gru', 'lstm'."""
    a = "rnn" if arch.startswith("rnn") else arch
    X = np.round(gf_inputs(), 6)
    return np.log10(np.maximum(grad_flow(a, gf_params(arch, rho, gain, bias), X), 1e-300))


# =========================================================================== figures
def _panel_text(ax, s, **kw):
    ax.text(0.0, 1.0, s, transform=ax.transAxes, va="top", ha="left", **kw)


def lm_models():
    """The three trained language models (rnn, gru, lstm) and their learning curves."""
    return {k: train_lm(k) for k in ("rnn", "gru", "lstm")}


def fig_15_2(out=None):
    """Text generated by the character GRU: greedy decoding (as in the book) and temperature sampling."""
    import textwrap
    model, curve = train_lm("gru")
    text, split = alice()
    chars, _ = vocab_of(text)
    cm = CharModel(gru_params_np(model), chars)
    g, lp = cm.greedy("the ", 500)
    s = cm.sample("the ", 500, 0.8, np.random.default_rng(2))
    fig, ax = plt.subplots(figsize=(7.4, 3.7))
    ax.axis("off")
    for y0, title, body in ((1.0, "greedy decoding, prefix 'the '", "the " + g),
                            (0.5, "sampling at temperature 0.8, prefix 'the '", "the " + s)):
        ax.text(0.0, y0, title, transform=ax.transAxes, va="top", fontsize=9.5, fontweight="bold")
        ax.text(0.0, y0 - 0.075, "\n".join(textwrap.wrap(body, 92)), transform=ax.transAxes, va="top", fontsize=7.8,
                family="monospace", linespacing=1.35)
    savefig(fig, CH, "fig15-2", out)
    return g


def fig_15_S1(out=None):
    """Perplexity of the RNN, GRU and LSTM character language models during training, with Markov baselines."""
    ms = lm_models()
    text, split = alice()
    fig, axes = plt.subplots(1, 2, figsize=(8.2, 3.1))
    cols = {"rnn": GREY, "gru": BLUE, "lstm": RED}
    names = {"rnn": "tanh RNN", "gru": "GRU", "lstm": "LSTM"}
    for k, (m, c) in ms.items():
        st = [r[0] for r in c]
        axes[0].plot(st, [r[2] for r in c], color=cols[k], label=names[k])
        axes[1].plot(st, [r[1] for r in c], color=cols[k], label=names[k])
    base = {o: markov_perplexity(text, split, o) for o in (2, 3, 4)}
    axes[0].axhline(base[3], color="k", ls=":", lw=1)
    axes[0].text(1450, base[3] * 0.96, "order-3 Markov", ha="right", va="top", fontsize=8)
    axes[0].axhline(base[4], color="k", ls="--", lw=1)
    axes[0].text(1450, base[4] * 1.02, "order-4 Markov", ha="right", va="bottom", fontsize=8)
    for ax, t in zip(axes, ("held-out perplexity", "training perplexity (running mean)")):
        ax.set_xlabel("optimiser step")
        ax.set_ylabel("perplexity")
        ax.set_title(t)
        ax.set_yscale("log")
        ax.set_ylim(3, 12)
        ax.set_yticks([3, 4, 5, 6, 8, 10])
        ax.set_yticklabels(["3", "4", "5", "6", "8", "10"])
    axes[0].legend(loc="upper right", fontsize=8)
    fig.tight_layout()
    savefig(fig, CH, "fig15-S1", out)
    return {k: (c[-1][1], c[-1][2]) for k, (m, c) in ms.items()}, base


def fig_15_12(out=None):
    """The greedy path and the second path of the toy example: conditional distributions and path probabilities."""
    logp, table = book_toy_model()
    toks = ["A", "B", "C", "eos"]
    paths = [((0, 1, 2, 3), "greedy: A, B, C, eos"), ((0, 2, 1, 3), "less greedy: A, C, B, eos")]
    fig, axes = plt.subplots(2, 4, figsize=(8.4, 4.2), sharey=True)
    for r, (path, title) in enumerate(paths):
        prob = 1.0
        for t in range(4):
            pre = path[:t]
            p = np.exp(logp(pre))
            ax = axes[r, t]
            colors = [BLUE if j == path[t] else "#c8c8c8" for j in range(4)]
            ax.bar(range(4), p, color=colors)
            ax.set_xticks(range(4))
            ax.set_xticklabels(toks, fontsize=8)
            ax.set_ylim(0, 0.75)
            prob *= p[path[t]]
            ax.set_title("$p(y_%d\\mid%s)$" % (t + 1, "\\cdots" if t else ""), fontsize=8.5)
            ax.text(path[t], p[path[t]] + 0.02, "%.2g" % p[path[t]], ha="center", fontsize=8)
        axes[r, 0].set_ylabel(title, fontsize=8.5)
        axes[r, 3].text(1.05, 0.5, "product\n%.3f" % prob, transform=axes[r, 3].transAxes, fontsize=9, va="center")
    fig.subplots_adjust(right=0.88, wspace=0.12, hspace=0.45)
    savefig(fig, CH, "fig15-12", out)


def fig_15_13(out=None):
    """Beam search with K = 2 on a random model with V = 5 tokens: the candidates at each step and the two kept."""
    V, K, T = 5, 2, 3
    logp = random_tree_model(V, seed=11, alpha=1.0)
    steps, best = beam_search(logp, V, K, T)
    names = "ABCDE"
    fig, ax = plt.subplots(figsize=(7.6, 4.8))
    pos = {}
    for t, cands in enumerate(steps):
        ranked = cands[:10]
        for r, (pre, sc, kept) in enumerate(ranked):
            pos[pre] = (t + 1, -r)
    for t, cands in enumerate(steps):
        for pre, sc, kept in cands[:10]:
            x, y = pos[pre]
            par = pre[:-1]
            if par in pos:
                px, py = pos[par]
                ax.plot([px + 0.2, x - 0.2], [py, y], color="#bbbbbb" if not kept else BLUE, lw=0.9 if not kept else 1.6, zorder=1)
            ax.text(x, y, "".join(names[j] for j in pre) + "\n%.3f" % math.exp(sc), ha="center", va="center", fontsize=7.5,
                    bbox=dict(boxstyle="round,pad=0.25", fc="#dbe7fb" if kept else "white", ec=BLUE if kept else "#bbbbbb", lw=1.2 if kept else 0.7), zorder=2)
    for t in range(T):
        ax.text(t + 1, 0.9, "step %d" % (t + 1), ha="center", fontsize=9)
    ax.set_xlim(0.5, T + 0.6)
    ax.set_ylim(-9.9, 1.3)
    ax.axis("off")
    ax.text(0.5, -10.5, "Candidates ranked by probability of the prefix; the top K = 2 (shaded) are expanded at the next step.", fontsize=8.5)
    savefig(fig, CH, "fig15-13", out)
    return best


def _dilated_net(T, dilations, k, seed):
    rng = np.random.default_rng(seed)
    return [rng.standard_normal((k, 1, 1)) for _ in dilations]


def fig_15_15(out=None):
    """Dilated causal convolutions with kernel 2 and dilations 1, 2, 4, 8: the connections and the receptive field."""
    T, dil = 16, [1, 2, 4, 8]
    ws = _dilated_net(T, dil, 2, 0)

    def forward(x):
        h = x[:, None]
        for w, d in zip(ws, dil):
            h = np.tanh(causal_conv1d(h, w, d))
        return h[:, 0]
    # the receptive field of the last output, measured: perturb each input and see whether the output moves
    x0 = np.random.default_rng(1).standard_normal(T)
    base = forward(x0)[-1]
    moved = []
    for i in range(T):
        x = x0.copy()
        x[i] += 1e-3
        moved.append(abs(forward(x)[-1] - base) > 1e-12)
    fig, axes = plt.subplots(1, 2, figsize=(8.6, 3.5), gridspec_kw={"width_ratios": [1.9, 1]})
    ax = axes[0]
    L = len(dil)
    # nodes: layer l (0 = input) position t; a node is in the cone if the final output at T-1 depends on it
    cone = [set() for _ in range(L + 1)]
    cone[L] = {T - 1}
    for l in range(L, 0, -1):
        for t in cone[l]:
            cone[l - 1].add(t)
            if t - dil[l - 1] >= 0:
                cone[l - 1].add(t - dil[l - 1])
    for l in range(1, L + 1):
        for t in range(T):
            for s in (t, t - dil[l - 1]):
                if s >= 0:
                    inc = t in cone[l] and s in cone[l - 1]
                    ax.plot([s, t], [l - 1, l], color=BLUE if inc else "#cccccc", lw=1.1 if inc else 0.5, zorder=1)
    for l in range(L + 1):
        for t in range(T):
            ax.scatter(t, l, s=28, color=BLUE if t in cone[l] else "white", edgecolor=BLUE if t in cone[l] else "#999999", zorder=2, lw=0.8)
    ax.set_yticks(range(L + 1))
    ax.set_yticklabels(["input"] + ["dilation %d" % d for d in dil], fontsize=8)
    ax.set_xlabel("position $t$")
    ax.set_title("connections into the last output", fontsize=10)
    ax.set_xticks([0, 5, 10, 15])
    for sp in ("top", "right"):
        ax.spines[sp].set_visible(False)
    ax = axes[1]
    Ls = np.arange(0, 11)
    ax.plot(Ls, [receptive_field(2, [2 ** l for l in range(n)]) for n in Ls], "o-", color=BLUE, ms=4, label="dilations $1,2,4,\\dots$")
    ax.plot(Ls, [receptive_field(2, [1] * n) for n in Ls], "s-", color=RED, ms=4, label="no dilation")
    ax.set_yscale("log", base=2)
    ax.set_xlabel("number of layers")
    ax.set_ylabel("receptive field")
    ax.legend(fontsize=8)
    ax.set_title("kernel size 2", fontsize=10)
    fig.tight_layout()
    savefig(fig, CH, "fig15-15", out)
    return int(sum(moved)), receptive_field(2, dil)


def fig_15_17(out=None):
    """Kernel regression as attention: attention matrix, predictions, and the leave-one-out error against beta."""
    x, y = kr_data(50, 0.5)
    xq = np.linspace(0, 5, 50)
    yq, A = kernel_attention(xq, x, y, 1.0)
    xd = np.linspace(0, 5, 400)
    fig, axes = plt.subplots(1, 3, figsize=(10.0, 3.2))
    im = axes[0].imshow(A, origin="lower", aspect="auto", cmap="Reds", extent=[0, 50, 0, 50])
    axes[0].set_xlabel("sorted training inputs $i$")
    axes[0].set_ylabel("test inputs $j$")
    axes[0].set_title("attention weights $\\alpha_i(x_j)$, $\\beta=1$")
    fig.colorbar(im, ax=axes[0], fraction=0.046, pad=0.04)
    ax = axes[1]
    ax.plot(xd, kr_truth(xd), color="k", lw=1.2, label="truth")
    ax.plot(x, y, ".", color=GREY, ms=5, label="data")
    betas_ = np.logspace(-0.7, 1.7, 60)
    bs = betas_[int(np.argmin([loo_kernel_error(x, y, b) for b in betas_]))]
    for b, c in ((1.0, RED), (round(bs, 1), GREEN), (25.0, BLUE)):
        ax.plot(xd, kernel_attention(xd, x, y, b)[0], color=c, lw=1.4, label="$\\beta=%g$" % b)
    ax.set_xlabel("$x$")
    ax.set_ylabel("$y$")
    ax.legend(fontsize=7.5, ncol=2, loc="upper left")
    ax.set_ylim(-1.6, 6.2)
    ax.set_title("predictions")
    ax = axes[2]
    betas = betas_
    ax.plot(betas, [loo_kernel_error(x, y, b) for b in betas], color=PURPLE)
    ax.axvline(bs, color=GREY, ls="--", lw=1)
    ax.set_xscale("log")
    ax.set_xlabel("$\\beta$")
    ax.set_ylabel("leave-one-out squared error")
    ax.set_title("choosing $\\beta$: minimum at %.2f" % bs)
    fig.tight_layout()
    savefig(fig, CH, "fig15-17", out)
    return bs


def fig_15_25(out=None):
    """The sinusoidal positional-encoding matrix (n = 60, d = 32) and four of its columns."""
    P = positional_encoding(60, 32)
    fig, axes = plt.subplots(1, 2, figsize=(8.4, 3.4))
    im = axes[0].imshow(P, aspect="auto", cmap="RdBu_r", vmin=-1, vmax=1, origin="upper")
    axes[0].set_xlabel("column (encoding dimension)")
    axes[0].set_ylabel("row (position)")
    fig.colorbar(im, ax=axes[0], fraction=0.046, pad=0.04)
    for j, c in zip((6, 7, 8, 9), (RED, BLUE, GREEN, ORANGE)):
        axes[1].plot(P[:, j], color=c, label="col %d" % j)
    axes[1].set_xlabel("position")
    axes[1].set_ylim(-1.1, 1.3)
    axes[1].legend(ncol=4, fontsize=7.5, loc="upper right")
    fig.tight_layout()
    savefig(fig, CH, "fig15-25", out)


def fig_15_S6(out=None):
    """Similarity of positional encodings p_t . p_{t+phi} depends only on the offset; the rotation property."""
    n, d = 80, 32
    P = positional_encoding(n, d)
    G = P @ P.T / (d / 2)
    fig, axes = plt.subplots(1, 3, figsize=(10.2, 3.2))
    im = axes[0].imshow(G, cmap="RdBu_r", vmin=-1, vmax=1, origin="upper")
    axes[0].set_title("$\\mathbf{p}_s^{T}\\mathbf{p}_t/(d/2)$")
    axes[0].set_xlabel("$t$")
    axes[0].set_ylabel("$s$")
    fig.colorbar(im, ax=axes[0], fraction=0.046, pad=0.04)
    phi = np.arange(0, 60)
    for t0, c in ((0, RED), (20, BLUE), (40, GREEN)):
        axes[1].plot(phi, [G[t0, t0 + f] for f in phi if t0 + f < n] + [np.nan] * sum(t0 + f >= n for f in phi), color=c, label="$t=%d$" % t0)
    w = 1.0 / 10000.0 ** (2 * np.arange(d // 2) / d)
    axes[1].plot(phi, [np.mean(np.cos(w * f)) for f in phi], "k:", lw=1.4, label="$\\frac{2}{d}\\sum_k\\cos(\\omega_k\\phi)$")
    axes[1].set_xlabel("offset $\\phi$")
    axes[1].legend(fontsize=7.5)
    axes[1].set_title("same curve for every $t$")
    for dd, c in ((4, ORANGE), (8, GREEN), (32, BLUE)):
        Pd = positional_encoding(n, dd)
        axes[2].plot(phi[:40], [np.linalg.norm(Pd[10 + f] - Pd[10]) if 10 + f < n else np.nan for f in phi[:40]], color=c, label="d = %d" % dd)
    axes[2].set_xlabel("offset $\\phi$")
    axes[2].set_ylabel("$\\|\\mathbf{p}_{t+\\phi}-\\mathbf{p}_t\\|$")
    axes[2].legend(fontsize=7.5)
    axes[2].set_title("not small for the fast dimensions")
    fig.tight_layout()
    savefig(fig, CH, "fig15-S6", out)


def fig_15_S2(out=None):
    """Gradient flow ||d s_T / d s_{T-k}|| for the vanilla RNN (linear and tanh), the GRU and the LSTM."""
    k = np.arange(GF_T)
    fig, axes = plt.subplots(1, 4, figsize=(11.2, 2.9), sharey=True)
    ax = axes[0]
    for rho, c in ((0.8, BLUE), (1.0, GREEN), (1.2, RED)):
        ax.plot(k, gf_curve("rnnlin", rho=rho, gain=0.3), color=c, label="$\\rho=%.1f$" % rho)
        ax.plot(k, k * math.log10(rho) + 0.0, color=c, ls=":", lw=1)
    ax.set_title("RNN, identity activation")
    ax.legend(fontsize=7.5)
    ax = axes[1]
    for rho, c in ((0.8, BLUE), (1.0, GREEN), (1.2, RED)):
        ax.plot(k, gf_curve("rnn", rho=rho, gain=0.3), color=c, label="$\\rho=%.1f$" % rho)
    ax.set_title("RNN, tanh")
    ax.legend(fontsize=7.5)
    for ax, a, name, cols in ((axes[2], "gru", "GRU, update-gate bias", None), (axes[3], "lstm", "LSTM, forget-gate bias", None)):
        for b, c in ((-2, BLUE), (0, GREEN), (2, ORANGE), (4, RED)):
            ax.plot(k, gf_curve(a, gain=1.5, bias=b), color=c, label="$b=%d$" % b)
        ax.set_title(name)
        ax.legend(fontsize=7.5)
    for ax in axes:
        ax.set_xlabel("lag $k$")
        ax.set_ylim(-25, 3)
    axes[0].set_ylabel("$\\log_{10}\\|\\partial s_T/\\partial s_{T-k}\\|_2$")
    fig.tight_layout()
    savefig(fig, CH, "fig15-S2", out)


# =========================================================================== delayed-recall task (Figure 15.S4)
def memory_batch(T, K, B, rng):
    """B sequences of length T + 1: symbol s in {0..K-1} at time 0, then T blanks (index K). Target: s."""
    s = rng.integers(0, K, B)
    x = np.full((B, T + 1), K)
    x[:, 0] = s
    return x, s


def _memory_models(T, K=4, H=32):
    torch, nn, BookGRU, CharLM = _torch_models()
    F = torch.nn.functional

    class Rec(nn.Module):
        def __init__(self, kind, forget_bias=None):
            super().__init__()
            self.core = {"rnn": lambda: nn.RNN(K + 1, H, batch_first=True), "gru": lambda: nn.GRU(K + 1, H, batch_first=True),
                         "lstm": lambda: nn.LSTM(K + 1, H, batch_first=True)}[kind]()
            self.out = nn.Linear(H, K)
            if forget_bias is not None:   # gate order of torch.nn.LSTM: input, forget, cell, output
                with torch.no_grad():
                    self.core.bias_ih_l0[H:2 * H] = forget_bias

        def forward(self, x):
            o, _ = self.core(F.one_hot(x, K + 1).float())
            return self.out(o[:, -1])

    class CausalCNN(nn.Module):
        def __init__(self):
            super().__init__()
            self.L = max(1, int(math.ceil(math.log2(T + 1))))
            self.convs = nn.ModuleList([nn.Conv1d(K + 1 if l == 0 else H, H, 2, dilation=2 ** l) for l in range(self.L)])
            self.out = nn.Linear(H, K)

        def forward(self, x):
            h = F.one_hot(x, K + 1).float().transpose(1, 2)
            for l, c in enumerate(self.convs):
                h = F.relu(c(F.pad(h, (2 ** l, 0))))
            return self.out(h[:, :, -1])

    class Tfm(nn.Module):
        def __init__(self):
            super().__init__()
            self.emb = nn.Linear(K + 1, H)
            self.register_buffer("pe", torch.tensor(positional_encoding(T + 1, H), dtype=torch.float32))
            self.layer = nn.TransformerEncoderLayer(H, 2, 2 * H, dropout=0.0, batch_first=True)
            self.out = nn.Linear(H, K)

        def forward(self, x):
            h = self.emb(F.one_hot(x, K + 1).float()) + self.pe
            return self.out(self.layer(h)[:, -1])

    return {"rnn": Rec("rnn"), "gru": Rec("gru"), "lstm": Rec("lstm"), "lstm_fb": Rec("lstm", forget_bias=5.0),
            "cnn": CausalCNN(), "transformer": Tfm()}, torch


def memory_experiment(Ts=(4, 8, 16, 32, 64), steps=500, seeds=(0, 1), K=4, force=False):
    """Test accuracy (mean over seeds) of six sequence models on the delayed-recall task, for each delay T.
    'lstm_fb' is the LSTM with the forget-gate bias initialised to 5 (Section 15.2.7.2). Results are cached,
    and models missing from an existing cache are added."""
    path = os.path.join(CACHE_DIR, "ch15_memory.json")
    res = json.load(open(path)) if (os.path.exists(path) and not force) else {}
    names = ("rnn", "gru", "lstm", "lstm_fb", "cnn", "transformer")
    todo = [k for k in names if k not in res]
    if not todo:
        return res
    for k in todo:
        res[k] = {}
    for T in Ts:
        for seed in seeds:
            models, torch = _memory_models(T, K)
            for name in todo:
                model = models[name]
                torch.manual_seed(seed)
                opt = torch.optim.Adam(model.parameters(), lr=3e-3)
                rng = np.random.default_rng(100 + seed)
                for _ in range(steps):
                    x, y = memory_batch(T, K, 64, rng)
                    loss = torch.nn.functional.cross_entropy(model(torch.tensor(x)), torch.tensor(y))
                    opt.zero_grad()
                    loss.backward()
                    torch.nn.utils.clip_grad_norm_(model.parameters(), 1.0)
                    opt.step()
                x, y = memory_batch(T, K, 2000, np.random.default_rng(999))
                with torch.no_grad():
                    acc = float((model(torch.tensor(x)).argmax(1).numpy() == y).mean())
                res[name].setdefault(str(T), []).append(acc)
        print("  delay", T, {k: round(float(np.mean(res[k][str(T)])), 3) for k in todo}, flush=True)
    json.dump(res, open(path, "w"))
    return res


def fig_15_S4(out=None):
    """Accuracy of recalling the first symbol after a delay of T steps, five sequence models."""
    res = memory_experiment()
    Ts = sorted(int(k) for k in res["rnn"])
    fig, ax = plt.subplots(figsize=(5.4, 3.3))
    style = {"rnn": (GREY, "o", "tanh RNN"), "gru": (BLUE, "s", "GRU"), "lstm": (RED, "^", "LSTM"),
             "lstm_fb": (ORANGE, "P", "LSTM, forget bias 5"), "cnn": (GREEN, "D", "dilated causal CNN"),
             "transformer": (PURPLE, "v", "transformer (1 layer)")}
    for k, (c, mk, lab) in style.items():
        ax.plot(Ts, [np.mean(res[k][str(T)]) for T in Ts], color=c, marker=mk, ms=5, label=lab)
    ax.axhline(0.25, color="k", ls=":", lw=1)
    ax.text(Ts[-1], 0.265, "chance", ha="right", fontsize=8)
    ax.set_xscale("log", base=2)
    ax.set_xticks(Ts)
    ax.set_xticklabels([str(t) for t in Ts])
    ax.set_xlabel("delay $T$ (blank steps between the symbol and the question)")
    ax.set_ylabel("test accuracy")
    ax.set_ylim(0.1, 1.05)
    ax.legend(fontsize=7.5, loc="lower left")
    fig.tight_layout()
    savefig(fig, CH, "fig15-S4", out)
    return res


# =========================================================================== seq2seq with attention (Figures 15.19, 15.S9)
S2S_LETTERS = "abcdefgh"
S2S_PAD, S2S_BOS, S2S_EOS = 8, 9, 10
S2S_V = 11


def _s2s_batch(B, rng, lens=(3, 8)):
    L = rng.integers(lens[0], lens[1] + 1, B)
    M = lens[1]
    src = np.full((B, M), S2S_PAD)
    tgt = np.full((B, M + 1), S2S_PAD)
    for i, l in enumerate(L):
        s = rng.integers(0, 8, l)
        src[i, :l] = s
        tgt[i, :l] = s[::-1]
        tgt[i, l] = S2S_EOS
    return src, tgt, L


def _s2s_net(attn, H=64, E=16):
    torch, nn, BookGRU, CharLM = _torch_models()
    F = torch.nn.functional

    class Seq2Seq(nn.Module):
        """GRU encoder-decoder. With attn=True the context at step t is (15.45): c_t = sum_i alpha_i(h^d_{t-1}, h^e_{1:T}) h^e_i
        with scaled dot-product scores; otherwise c is the final encoder state (Section 15.2.3.2)."""

        def __init__(self):
            super().__init__()
            self.attn = attn
            self.emb = nn.Embedding(S2S_V, E)
            self.enc = nn.GRU(E, H, batch_first=True)
            self.cell = nn.GRUCell(E + H, H)
            self.out = nn.Linear(H + (H if attn else 0), S2S_V)
            self.H = H

        def encode(self, src, L):
            o, _ = self.enc(self.emb(src))
            idx = (torch.as_tensor(L) - 1).long()
            last = o[torch.arange(len(idx)), idx]
            mask = torch.arange(src.shape[1])[None, :] < torch.as_tensor(L)[:, None]
            return o, last, mask

        def step(self, y_prev, h, enc, last, mask):
            if self.attn:
                s = (enc @ h.unsqueeze(2)).squeeze(2) / math.sqrt(self.H)
                s = s.masked_fill(~mask, -1e6)
                a = torch.softmax(s, 1)
                c = (a.unsqueeze(2) * enc).sum(1)
            else:
                a, c = None, last
            h = self.cell(torch.cat([self.emb(y_prev), c], 1), h)
            logits = self.out(torch.cat([h, c], 1) if self.attn else h)
            return logits, h, a

        def forward(self, src, L, tgt=None, steps=None, want_att=False):
            enc, last, mask = self.encode(src, L)
            B = src.shape[0]
            h = last
            y = torch.full((B,), S2S_BOS, dtype=torch.long)
            outs, atts = [], []
            T = tgt.shape[1] if tgt is not None else steps
            for t in range(T):
                logits, h, a = self.step(y, h, enc, last, mask)
                outs.append(logits)
                atts.append(a)
                y = tgt[:, t] if tgt is not None else logits.argmax(1)   # teacher forcing / greedy decoding
            return torch.stack(outs, 1), (torch.stack(atts, 1) if want_att and attn else None)

    return Seq2Seq(), torch, F


def train_seq2seq(attn, steps=1200, seed=0, force=False):
    path = os.path.join(CACHE_DIR, "ch15_s2s_%s.pt" % ("attn" if attn else "plain"))
    torch_mod().manual_seed(seed)
    net, torch, F = _s2s_net(attn)
    if os.path.exists(path) and not force:
        net.load_state_dict(torch.load(path))
        return net
    opt = torch.optim.Adam(net.parameters(), lr=4e-3)
    rng = np.random.default_rng(seed)
    for step in range(steps):
        src, tgt, L = _s2s_batch(64, rng)
        logits, _ = net(torch.tensor(src), L, torch.tensor(tgt))
        loss = F.cross_entropy(logits.reshape(-1, S2S_V), torch.tensor(tgt).reshape(-1), ignore_index=S2S_PAD)
        opt.zero_grad()
        loss.backward()
        torch.nn.utils.clip_grad_norm_(net.parameters(), 1.0)
        opt.step()
        if step % 300 == 0:
            print("   s2s", "attn" if attn else "plain", step, round(loss.item(), 3), flush=True)
    torch.save(net.state_dict(), path)
    return net


def s2s_accuracy(net, length, n=400, seed=5):
    torch = torch_mod()
    rng = np.random.default_rng(seed)
    src, tgt, L = _s2s_batch(n, rng, lens=(length, length))
    with torch.no_grad():
        logits, _ = net(torch.tensor(src), L, steps=length + 1)
    pred = logits.argmax(2).numpy()
    return float((pred == tgt[:, :length + 1]).all(1).mean())


def s2s_translate(net, s):
    torch = torch_mod()
    src = np.full((1, 8), S2S_PAD)
    src[0, :len(s)] = [S2S_LETTERS.index(c) for c in s]
    with torch.no_grad():
        logits, att = net(torch.tensor(src), [len(s)], steps=len(s) + 1, want_att=True)
    pred = logits.argmax(2)[0].numpy()
    out = "".join(S2S_LETTERS[j] if j < 8 else "." for j in pred)
    return out, (att[0, :, :len(s)].numpy() if att is not None else None)


def fig_15_19(out=None):
    """Attention heatmaps of the trained encoder-decoder on two reversal examples (stand-in for the translation example)."""
    net = train_seq2seq(True)
    ex = ["dcagfb", "heba"]
    fig, axes = plt.subplots(1, 2, figsize=(7.6, 3.3), gridspec_kw={"width_ratios": [6, 4]})
    for ax, s in zip(axes, ex):
        o, A = s2s_translate(net, s)
        im = ax.imshow(A, cmap="Blues", vmin=0, vmax=1, aspect="auto")
        ax.set_xticks(range(len(s)))
        ax.set_xticklabels(list(s))
        ax.set_yticks(range(len(s) + 1))
        ax.set_yticklabels(list(o))
        ax.set_xlabel("input: " + s)
        ax.set_ylabel("generated")
        ax.set_title("output %s" % o.rstrip("."), fontsize=9.5)
    fig.colorbar(im, ax=axes, fraction=0.03, pad=0.02)
    savefig(fig, CH, "fig15-19", out)


def fig_15_S9(out=None):
    """Sequence accuracy against length for the encoder-decoder with and without attention."""
    na, npl = train_seq2seq(True), train_seq2seq(False)
    Ls = list(range(3, 9))
    fig, ax = plt.subplots(figsize=(4.6, 3.1))
    ax.plot(Ls, [s2s_accuracy(na, l) for l in Ls], "o-", color=BLUE, label="with attention")
    ax.plot(Ls, [s2s_accuracy(npl, l) for l in Ls], "s-", color=RED, label="fixed context vector")
    ax.set_xlabel("input length")
    ax.set_ylabel("exact-match accuracy")
    ax.set_ylim(0, 1.05)
    ax.legend(fontsize=8, loc="lower left")
    fig.tight_layout()
    savefig(fig, CH, "fig15-S9", out)


# =========================================================================== tiny vision transformer (Figure 15.S8)
def patchify(imgs, p=2):
    """(N, 8, 8) images -> (N, (8/p)^2, p*p) flattened non-overlapping p x p patches in raster order (Section 15.5.6)."""
    N, h, w = imgs.shape
    x = imgs.reshape(N, h // p, p, w // p, p).transpose(0, 1, 3, 2, 4)
    return x.reshape(N, (h // p) * (w // p), p * p)


def train_vit(epochs=40, d=32, heads=2, layers=2, seed=0, force=False):
    """A tiny ViT on the 8x8 digits: 2x2 patches (16 tokens) plus a [class] token, learned positional embeddings,
    post-norm encoder blocks as in Section 15.5.4. Returns (model, test accuracy, test images, test labels)."""
    from sklearn.datasets import load_digits
    torch, nn, BookGRU, CharLM = _torch_models()
    D = load_digits()
    X = D.images / 16.0
    y = D.target
    rng = np.random.default_rng(0)
    perm = rng.permutation(len(y))
    tr, te = perm[:1300], perm[1300:]

    class Block(nn.Module):
        def __init__(self):
            super().__init__()
            self.att = nn.MultiheadAttention(d, heads, batch_first=True)
            self.ff = nn.Sequential(nn.Linear(d, 2 * d), nn.ReLU(), nn.Linear(2 * d, d))
            self.n1, self.n2 = nn.LayerNorm(d), nn.LayerNorm(d)

        def forward(self, x):
            a, w = self.att(x, x, x, need_weights=True, average_attn_weights=False)
            z = self.n1(a + x)
            return self.n2(self.ff(z) + z), w

    class ViT(nn.Module):
        def __init__(self):
            super().__init__()
            self.proj = nn.Linear(4, d)
            self.cls = nn.Parameter(torch.zeros(1, 1, d))
            self.pos = nn.Parameter(torch.randn(1, 17, d) * 0.1)
            self.blocks = nn.ModuleList([Block() for _ in range(layers)])
            self.head = nn.Linear(d, 10)

        def forward(self, p, want=False):
            z = torch.cat([self.cls.expand(len(p), -1, -1), self.proj(p)], 1) + self.pos
            ws = []
            for b in self.blocks:
                z, w = b(z)
                ws.append(w)
            out = self.head(z[:, 0])
            return (out, ws) if want else out

    path = os.path.join(CACHE_DIR, "ch15_vit.pt")
    torch.manual_seed(seed)
    model = ViT()
    Ptr, Pte = torch.tensor(patchify(X[tr]), dtype=torch.float32), torch.tensor(patchify(X[te]), dtype=torch.float32)
    ytr, yte = torch.tensor(y[tr]), torch.tensor(y[te])
    if os.path.exists(path) and not force:
        model.load_state_dict(torch.load(path))
    else:
        opt = torch.optim.Adam(model.parameters(), lr=3e-3)
        g = np.random.default_rng(seed)
        for ep in range(epochs):
            o = g.permutation(len(tr))
            for i in range(0, len(tr), 64):
                b = torch.tensor(o[i:i + 64])
                loss = nn.functional.cross_entropy(model(Ptr[b]), ytr[b])
                opt.zero_grad()
                loss.backward()
                opt.step()
        torch.save(model.state_dict(), path)
    with torch.no_grad():
        acc = float((model(Pte).argmax(1) == yte).float().mean())
    return model, acc, X[te], y[te], Pte


def fig_15_S8(out=None):
    """The tiny ViT: patches of a digit and the attention of the [class] token (last layer, averaged over heads)."""
    model, acc, Xte, yte, Pte = train_vit()
    torch = torch_mod()
    with torch.no_grad():
        pred, ws = model(Pte[:6], want=True)
    A = ws[-1].mean(1)[:, 0, 1:].numpy()   # class token -> 16 patches
    fig, axes = plt.subplots(3, 6, figsize=(8.4, 4.4))
    for j in range(6):
        ax = axes[0, j]
        ax.imshow(Xte[j], cmap="gray_r")
        for t in (1.5, 3.5, 5.5):
            ax.axhline(t, color=RED, lw=0.6)
            ax.axvline(t, color=RED, lw=0.6)
        ax.set_title("label %d" % yte[j], fontsize=8.5)
        ax.axis("off")
        axes[1, j].imshow(A[j].reshape(4, 4), cmap="Blues", vmin=0, vmax=A.max())
        axes[1, j].axis("off")
        im = axes[2, j].imshow(Xte[j], cmap="gray_r")
        axes[2, j].imshow(np.kron(A[j].reshape(4, 4), np.ones((2, 2))), cmap="Reds", alpha=0.5, vmin=0, vmax=A.max())
        axes[2, j].axis("off")
    axes[0, 0].text(-0.2, 0.5, "image and\n2x2 patches", transform=axes[0, 0].transAxes, ha="right", va="center", fontsize=8)
    axes[1, 0].text(-0.2, 0.5, "[class] attention\nover 16 patches", transform=axes[1, 0].transAxes, ha="right", va="center", fontsize=8)
    axes[2, 0].text(-0.2, 0.5, "overlay", transform=axes[2, 0].transAxes, ha="right", va="center", fontsize=8)
    fig.subplots_adjust(left=0.17, wspace=0.05, hspace=0.12)
    fig.suptitle("tiny ViT, test accuracy %.3f (1.3k training digits)" % acc, fontsize=9.5, y=0.99)
    savefig(fig, CH, "fig15-S8", out)
    return acc


# =========================================================================== efficient attention figures
def performer_error_curve(sigma, Ms, kinds, N=128, D=16, reps=12, seed=0):
    """Mean relative error ||A_hat V - A V||_F / ||A V||_F of the random-feature attention against the number of features."""
    out = {k: [] for k in kinds}
    for M in Ms:
        errs = {k: [] for k in kinds}
        for r in range(reps):
            rng = np.random.default_rng(seed + r)
            Q, K, V = sigma * rng.standard_normal((N, D)), sigma * rng.standard_normal((N, D)), rng.standard_normal((N, 4))
            exact = softmax_attention_matrix(Q, K) @ V
            for kind in kinds:
                base, ortho = (kind.replace("+ortho", ""), kind.endswith("+ortho"))
                est = performer_attention(Q, K, V, M, np.random.default_rng(1000 + 31 * r + M), base, ortho)
                errs[kind].append(np.linalg.norm(est - exact) / np.linalg.norm(exact))
        for k in kinds:
            out[k].append(float(np.median(errs[k])))
    return out


def fig_15_S7(out=None):
    """Random-feature approximation of softmax attention (Section 15.6.4): accuracy, and cost against N."""
    Ms = [4, 8, 16, 32, 64, 128, 256, 512]
    kinds = ["trig", "positive", "positive+ortho"]
    fig, axes = plt.subplots(1, 3, figsize=(10.4, 3.2))
    style = {"trig": (GREEN, "trigonometric"), "positive": (BLUE, "positive"), "positive+ortho": (RED, "positive, orthogonal")}
    for ax, sg in zip(axes[:2], (0.3, 0.8)):
        res = performer_error_curve(sg, Ms, kinds)
        for k in kinds:
            ax.plot(Ms, res[k], "o-", ms=4, color=style[k][0], label=style[k][1])
        ax.plot(Ms, [res["positive"][0] * math.sqrt(Ms[0] / m) for m in Ms], "k:", lw=1, label="$\\propto M^{-1/2}$")
        ax.set_xscale("log", base=2)
        ax.set_yscale("log")
        ax.set_xlabel("number of random features $M$")
        ax.set_ylabel("relative error of the output")
        ax.set_title("queries and keys with std %.1f" % sg)
        ax.legend(fontsize=7.5)
    d = 16
    Ns = np.array([64, 128, 256, 512, 1024, 2048, 4096, 8192])
    ax = axes[2]
    ax.plot(Ns, 2 * Ns.astype(float) ** 2 * d, "o-", color=RED, ms=4, label="exact: $2N^2d$")
    for M in (64, 256):
        ax.plot(Ns, 2.0 * Ns * M * d + 2 * Ns * M * d, "s-", ms=4, label="linear, $M=%d$: $4NMd$" % M)
    ax.set_xscale("log", base=2)
    ax.set_yscale("log")
    ax.set_xlabel("sequence length $N$")
    ax.set_ylabel("multiply-adds ($d=16$)")
    ax.legend(fontsize=7.5)
    fig.tight_layout()
    savefig(fig, CH, "fig15-S7", out)
    return {k: v for k, v in performer_error_curve(0.5, [64, 512], kinds).items()}


def fig_15_S10(out=None):
    """Singular values of softmax attention matrices for three score scales (full rank, but near rank 1 for flat attention)."""
    n, d = 64, 16
    fig, axes = plt.subplots(1, 2, figsize=(7.6, 3.1))
    rng = np.random.default_rng(3)
    ranks = {}
    for sg, c in ((0.3, GREEN), (1.0, BLUE), (3.0, RED)):
        Q, K = sg * rng.standard_normal((n, d)), sg * rng.standard_normal((n, d))
        s = np.linalg.svd(softmax_attention_matrix(Q, K), compute_uv=False)
        axes[0].semilogy(np.arange(1, n + 1), s, color=c, label="$\\sigma=%.1f$" % sg)
        axes[1].plot(np.arange(1, n + 1), np.cumsum(s ** 2) / np.sum(s ** 2), color=c, label="$\\sigma=%.1f$" % sg)
        ranks[sg] = int((s > 1e-10 * s[0]).sum())
    axes[0].set_xlabel("index")
    axes[0].set_ylabel("singular value of $A$")
    axes[0].legend(fontsize=8)
    axes[1].set_xlabel("rank $r$")
    axes[1].set_ylabel("energy captured by the best rank-$r$ approximation")
    axes[1].axhline(0.99, color=GREY, ls=":", lw=1)
    fig.tight_layout()
    savefig(fig, CH, "fig15-S10", out)
    return ranks


def fig_15_S3(out=None):
    """Maximum path length and cost per layer (Table 15.1): measured on the dependency graphs, and operation counts."""
    ns = [4, 8, 16, 32, 64, 128, 256]
    fig, axes = plt.subplots(1, 2, figsize=(8.2, 3.1))
    ax = axes[0]
    for name, c, lab in (("recurrent", RED, "recurrent: $n$"), ("conv_plain", ORANGE, "convolution, $k=2$, undilated"),
                         ("conv_dilated", GREEN, "dilated convolution: $\\log_2 n$"), ("attention", BLUE, "self-attention: 1")):
        ax.plot(ns, [path_length(name, n, 2) for n in ns], "o-", ms=4, color=c, label=lab)
    ax.set_xscale("log", base=2)
    ax.set_yscale("log", base=2)
    ax.set_xlabel("sequence length $n$")
    ax.set_ylabel("maximum path length")
    ax.legend(fontsize=7.5)
    ax = axes[1]
    nn_ = np.array([8, 16, 32, 64, 128, 256, 512, 1024])
    d = 64
    ax.plot(nn_, [cost_table(n, d)["attention"] for n in nn_], "o-", ms=4, color=BLUE, label="self-attention $2n^2d$")
    ax.plot(nn_, [cost_table(n, d)["recurrent"] for n in nn_], "s-", ms=4, color=RED, label="recurrent $2nd^2$")
    ax.plot(nn_, [cost_table(n, d, 3)["conv"] for n in nn_], "^-", ms=4, color=GREEN, label="convolution $knd^2$, $k=3$")
    ax.axvline(d, color=GREY, ls=":", lw=1)
    ax.text(d * 1.05, ax.get_ylim()[0] * 3 if False else 3e5, "$n=d$", fontsize=8, color=GREY)
    ax.set_xscale("log", base=2)
    ax.set_yscale("log")
    ax.set_xlabel("sequence length $n$ ($d=64$)")
    ax.set_ylabel("multiply-adds per layer")
    ax.legend(fontsize=7.5)
    fig.tight_layout()
    savefig(fig, CH, "fig15-S3", out)


def fig_15_S5(out=None):
    """Beam search against greedy decoding: log-probability on the character GRU, and the chance of finding the exact MAP on small random trees."""
    model, _ = train_lm("gru")
    text, split = alice()
    chars, _ = vocab_of(text)
    cm = CharModel(gru_params_np(model), chars)
    prefixes = ["the ", "alice was ", "she ", "i ", "it was ", "and the "]
    Ks = [1, 2, 4, 8, 16]
    n = 40
    fig, axes = plt.subplots(1, 2, figsize=(8.2, 3.2))
    sc = np.zeros((len(prefixes), len(Ks)))
    for i, p in enumerate(prefixes):
        for j, K in enumerate(Ks):
            s, lp = cm.beam(p, n, K)
            sc[i, j] = lp
        axes[0].plot(Ks, sc[i], "o-", ms=3.5, lw=1, label="'%s'" % p.strip())
    axes[0].set_xscale("log", base=2)
    axes[0].set_xticks(Ks)
    axes[0].set_xticklabels([str(k) for k in Ks])
    axes[0].set_xlabel("beam width $K$ (K = 1 is greedy)")
    axes[0].set_ylabel("log-probability of the 40 characters")
    axes[0].legend(fontsize=7, ncol=2)
    V, T, ntree = 4, 6, 60
    Kt = [1, 2, 4, 8, 16, 32]
    hit = np.zeros(len(Kt))
    for tr in range(ntree):
        lg = random_tree_model(V, 100 + tr, 0.5)
        best = exhaustive_map(lg, V, T)[1]
        for j, K in enumerate(Kt):
            b = beam_search(lg, V, K, T)[1]
            hit[j] += abs(b[1] - best) < 1e-12
    axes[1].plot(Kt, hit / ntree, "o-", color=BLUE)
    axes[1].set_xscale("log", base=2)
    axes[1].set_xticks(Kt)
    axes[1].set_xticklabels([str(k) for k in Kt])
    axes[1].set_ylim(0, 1.05)
    axes[1].set_xlabel("beam width $K$")
    axes[1].set_ylabel("fraction of trees where beam search finds the MAP")
    axes[1].set_title("$V=4$ tokens, $T=6$ steps, %d random models" % ntree, fontsize=9)
    fig.tight_layout()
    savefig(fig, CH, "fig15-S5", out)
    return sc, hit / ntree


# =========================================================================== data for the browser demonstrations
def export_data(out=None):
    """JSON files for the four demonstrations: gradient flow, character-model decoding, kernel regression."""
    gf = {"T": GF_T, "Dx": GF_DX, "H": GF_H, "X": np.round(gf_inputs(), 6).tolist(),
          "base": {a: {k: r4(v, 6) for k, v in gf_base(a).items() if k != "linear"} for a in ("rnn", "gru", "lstm")}}
    dump_json("ch15-gradflow.json", gf)
    model, _ = train_lm("gru")
    text, split = alice()
    chars, _ = vocab_of(text)
    P = gru_params_np(model)
    cr = {"chars": chars, "H": int(P["Whh"].shape[0]), "params": {k: np.asarray(v).tolist() for k, v in P.items()},
          "prefixes": ["the ", "alice was ", "she ", "and the ", "it was "]}
    dump_json("ch15-charrnn.json", cr)
    logp, table = book_toy_model()
    rt = random_tree_model(5, 11, 1.0)
    tree5 = {}
    for L in range(3):
        for pre in itertools.product(range(5), repeat=L):
            tree5["".join(map(str, pre))] = np.round(np.exp(rt(pre)), 8).tolist()
    toy = {"book": {"".join(map(str, k)): v for k, v in table.items()}, "tree5": tree5}
    dump_json("ch15-toy.json", toy)
    xp, zp = kr_pool()
    dump_json("ch15-kr.json", {"x": xp.tolist(), "z": zp.tolist()})


FIGURES = {
    "15.2": fig_15_2, "15.12": fig_15_12, "15.13": fig_15_13, "15.15": fig_15_15, "15.17": fig_15_17,
    "15.19": fig_15_19, "15.25": fig_15_25,
    "15.S1": fig_15_S1, "15.S2": fig_15_S2, "15.S3": fig_15_S3, "15.S4": fig_15_S4, "15.S5": fig_15_S5,
    "15.S6": fig_15_S6, "15.S7": fig_15_S7, "15.S8": fig_15_S8, "15.S9": fig_15_S9, "15.S10": fig_15_S10,
    "data": export_data,
}

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