"""Bishop and Bishop (2024), Chapter 12: Transformers.

Reproduces the computed figures of Chapter 12 of C. M. Bishop and H. Bishop, Deep Learning: Foundations
and Concepts (Springer, 2024), pp. 357-406, written from scratch with numpy, PyTorch (for training the
small models only) and matplotlib, and supplies the models and reference numbers of the three browser
demonstrations. Every algorithm is a short function meant to be read next to the lecture notes
(ch12-transformers.html):

* Section 12.1, attention: softmax_rows and softmax_jacobian, attention (12.14) with an optional mask
  and its backward pass written out (attention_backward), multi_head (12.15)-(12.19), layer_norm,
  the transformer layer in post-norm (12.20), (12.22) and pre-norm (12.21), (12.23) form, the
  fully connected matrix of Exercise 12.6 (attention_as_matrix), flop counts (layer_flops) and the
  sinusoidal position encoding (12.25) with its rotation matrices (sinusoidal_pe, pe_shift_matrix).
* Section 12.2, natural language: a character corpus (Lewis Carroll, Alice's Adventures in
  Wonderland, 1865, public domain), byte-pair encoding (bpe_learn, bpe_encode), bag-of-words,
  naive Bayes and n-gram models with their maximum-likelihood tables (ngram_counts, ngram_logprob),
  and the skip-gram/PMI identity (sgns_optimum).
* Section 12.3, transformer language models: a decoder-only character transformer (TinyGPT, trained
  in about three minutes on one CPU thread and cached), its numpy forward pass gpt_forward (the one
  the browser runs), cross-entropy and perplexity, the sampling rules of Section 12.3.2 (temperature
  (12.35), top-k, nucleus), greedy and beam search, and exact best sequences for a bigram model.
* Section 12.4, multimodal transformers: patch tokens of a vision transformer (patchify), a tiny ViT
  on MNIST, a tiny autoregressive pixel transformer for Figure 12.24 (same code as TinyGPT, with two
  pixel tokens), a mel spectrogram computed from scratch (mel_spectrogram) for Figure 12.25, and
  vector quantisation (12.38).
* JSRandom: the seeded generator DK.rng of the browser demos (mulberry32 uniforms and Box-Muller
  normals). The demos reproduce attention weights, logits and sampled text from this module number for
  number.

Figures reproduced: 12.2 (phenomenon: learned attention weights, here from the character
transformer), 12.10 (a) and (b), 12.12 (byte-pair encoding of the book's sentence), 12.16 (the
causal mask, with the attention weights of a masked layer), 12.17 (phenomenon: probabilities of
beam-search text against real text, from the character transformer), 12.24 (phenomenon:
raster-scan sampling from a small autoregressive transformer on 14 x 14 binary MNIST digits) and 12.25
(phenomenon: a mel spectrogram, of a synthetic whale-like song computed from scratch).

Figures skipped (schematic diagrams, drawn in the book, with nothing to compute): 12.1 (lines
between words), 12.3 (the data matrix), 12.4 and 12.5 (matrix products), 12.6, 12.7, 12.8 and 12.9
(information flow in a head, in multi-head attention and in a layer), 12.11 (word2vec networks),
12.13 and 12.14 (RNN diagrams), 12.15, 12.18, 12.19, 12.20 and 12.22 (architectures), 12.21 (LoRA
diagram), 12.23 (raster scan order) and 12.26 (Vall-E diagram). Skipped because they are images
reprinted from other papers: 12.2 (Vaswani et al., 2017) and 12.17 (Holtzman et al., 2019), whose
phenomena are reproduced here at small scale, and 12.27 (CM3Leon outputs, Yu et al., 2023), which
needs a large multimodal model.

Supplementary figures (our own, numbered 12.S1-12.S8; they illustrate the gaps filled in the notes):
12.S1 why the 1/sqrt(D) scaling keeps the softmax out of saturation; 12.S2 relative positions of
the sinusoidal encoding (Gram matrix and rotations); 12.S3 cost of a transformer layer against N
and D; 12.S4 training the character transformer against n-gram baselines (cross-entropy and
perplexity); 12.S5 byte-pair encoding of the corpus: vocabulary size against sequence length;
12.S6 temperature, top-k and nucleus sampling on a next-word distribution; 12.S7 a tiny vision
transformer on MNIST; 12.S8 self-attention and the position-wise MLP written as N D x N D matrices
(Exercise 12.6).

Run `python3 ch12_transformers.py --list`, `python3 ch12_transformers.py` (all figures, about ten
minutes on one CPU thread the first time, then about a minute from the cache) or
`python3 ch12_transformers.py --fig 12.10 12.S1`. Files go to ../img/ch12/; trained weights and slow
results are cached in cache/; the demos' JSON files go to ../data/.
"""
import base64
import collections
import hashlib
import json
import math
import os
import re
import time

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

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

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

HERE = os.path.dirname(os.path.abspath(__file__))
CACHE_DIR = os.path.join(HERE, "cache")
JSON_DIR = os.path.normpath(os.path.join(HERE, "..", "data"))
CH = 12
M32 = 0xFFFFFFFF


# =========================================================================== the demos' generator
def _imul(a, b):
    return (a * b) & M32


class JSRandom:
    """The seeded random numbers of the browser demos (DK.rng in courses/demo-kit.js).

    Uniforms come from the mulberry32 generator and normals from the Box-Muller transform, the
    second normal of each pair being cached, exactly as in JavaScript.
    """

    def __init__(self, seed):
        self.a = int(seed) & M32
        self.spare = None

    def u(self):
        a = (self.a + 0x6D2B79F5) & M32
        self.a = a
        t = _imul(a ^ (a >> 15), 1 | a)
        t = ((t + _imul(t ^ (t >> 7), 61 | t)) & M32) ^ t
        return ((t ^ (t >> 14)) & M32) / 4294967296.0

    def _pos(self):
        x = 0.0
        while x == 0.0:
            x = self.u()
        return x

    def norm(self):
        if self.spare is not None:
            s, self.spare = self.spare, None
            return s
        r = math.sqrt(-2.0 * math.log(self._pos()))
        th = 2.0 * math.pi * self.u()
        self.spare = r * math.sin(th)
        return r * math.cos(th)

    def normals(self, n):
        return np.array([self.norm() for _ in range(int(n))])


def _cached(name, fn):
    """Compute fn() once and keep the result (a dict of arrays/values) in cache/<name>.npz."""
    os.makedirs(CACHE_DIR, exist_ok=True)
    path = os.path.join(CACHE_DIR, name + ".npz")
    if os.path.exists(path):
        d = np.load(path, allow_pickle=True)
        return d["res"].item()
    res = fn()
    np.savez(path, res=np.array(res, dtype=object))
    return res


# =========================================================================== 12.1 attention (numpy)
def softmax_rows(S):
    """Softmax of each row of S (entries -inf are allowed and give weight 0)."""
    S = np.asarray(S, dtype=float)
    m = np.max(S, axis=-1, keepdims=True)
    m = np.where(np.isfinite(m), m, 0.0)
    E = np.exp(S - m)
    return E / E.sum(axis=-1, keepdims=True)


def softmax_jacobian(a):
    """J_ij = d a_i / d z_j = a_i (delta_ij - a_j) for a = softmax(z)."""
    a = np.asarray(a, dtype=float)
    return np.diag(a) - np.outer(a, a)


def causal_mask(N):
    """Additive mask: 0 on and below the diagonal, -inf above it (token n may not see m > n)."""
    M = np.zeros((N, N))
    M[np.triu_indices(N, 1)] = -np.inf
    return M


def attention(Q, K, V, mask=None, scale=True, temperature=1.0):
    """Scaled dot-product attention (12.14): Softmax[Q K^T / sqrt(D_k)] V.

    Returns (Y, A) with A the N x M matrix of attention weights. mask is added to the scores
    (use causal_mask for (masked) self-attention); temperature divides the scores further.
    """
    Dk = Q.shape[-1]
    S = Q @ K.T
    if scale:
        S = S / math.sqrt(Dk)
    S = S / temperature
    if mask is not None:
        S = S + mask
    A = softmax_rows(S)
    return A @ V, A


def attention_backward(Q, K, V, dY, scale=True):
    """Gradients of a scalar E with respect to Q, K, V given dY = dE/dY for Y = attention(Q, K, V).

    With S = Q K^T / sqrt(Dk), A = Softmax[S], Y = A V:
        dV = A^T dY,  dA = dY V^T,  dS_nm = A_nm (dA_nm - sum_m' A_nm' dA_nm'),
        dQ = dS K / sqrt(Dk),  dK = dS^T Q / sqrt(Dk).
    """
    c = 1.0 / math.sqrt(Q.shape[-1]) if scale else 1.0
    _, A = attention(Q, K, V, scale=scale)
    dV = A.T @ dY
    dA = dY @ V.T
    dS = A * (dA - np.sum(A * dA, axis=1, keepdims=True))
    return c * dS @ K, c * dS.T @ Q, dV


def self_attention(X, Wq, Wk, Wv, mask=None, scale=True):
    """Algorithm 12.1: one head of scaled dot-product self-attention."""
    return attention(X @ Wq, X @ Wk, X @ Wv, mask=mask, scale=scale)


def multi_head(X, Wq, Wk, Wv, Wo, mask=None):
    """Algorithm 12.2, (12.15)-(12.19): Wq, Wk, Wv are lists of H matrices; Wo is (H Dv) x D."""
    heads = [self_attention(X, Wq[h], Wk[h], Wv[h], mask=mask)[0] for h in range(len(Wq))]
    return np.concatenate(heads, axis=1) @ Wo


def multi_head_as_sum(X, Wq, Wk, Wv, Wo, mask=None):
    """Exercise 12.5 (corrected): Y = sum_h A_h X W_v,h W_o,h, with A_h the N x N weight matrix."""
    Dv = Wv[0].shape[1]
    Y = 0.0
    for h in range(len(Wq)):
        _, A = self_attention(X, Wq[h], Wk[h], Wv[h], mask=mask)
        Y = Y + A @ X @ (Wv[h] @ Wo[h * Dv:(h + 1) * Dv])
    return Y


def layer_norm(X, gamma=None, beta=None, eps=1e-5):
    """Layer normalisation of each row (token) of X, as in Section 7.4.3."""
    mu = X.mean(axis=-1, keepdims=True)
    var = ((X - mu) ** 2).mean(axis=-1, keepdims=True)
    Z = (X - mu) / np.sqrt(var + eps)
    if gamma is not None:
        Z = Z * gamma + beta
    return Z


def mlp(X, W1, b1, W2, b2):
    """The position-wise two-layer ReLU network applied to every row of X."""
    return np.maximum(X @ W1 + b1, 0.0) @ W2 + b2


def transformer_layer(X, p, mask=None, pre_norm=False):
    """Algorithm 12.3. Post-norm: (12.20), (12.22). Pre-norm: (12.21), (12.23).

    p holds lists Wq, Wk, Wv (H matrices each), Wo, and W1, b1, W2, b2 for the MLP.
    """
    if pre_norm:
        Z = multi_head(layer_norm(X), p["Wq"], p["Wk"], p["Wv"], p["Wo"], mask) + X
        return mlp(layer_norm(Z), p["W1"], p["b1"], p["W2"], p["b2"]) + Z
    Z = layer_norm(multi_head(X, p["Wq"], p["Wk"], p["Wv"], p["Wo"], mask) + X)
    return layer_norm(mlp(Z, p["W1"], p["b1"], p["W2"], p["b2"]) + Z)


def random_layer(D, H, Dff, rng):
    """Random parameters for transformer_layer (variance 1/fan-in)."""
    Dk = D // H
    s = 1.0 / math.sqrt(D)
    return {"Wq": [rng.normal(0, s, (D, Dk)) for _ in range(H)],
            "Wk": [rng.normal(0, s, (D, Dk)) for _ in range(H)],
            "Wv": [rng.normal(0, s, (D, Dk)) for _ in range(H)],
            "Wo": rng.normal(0, 1 / math.sqrt(H * Dk), (H * Dk, D)),
            "W1": rng.normal(0, s, (D, Dff)), "b1": rng.normal(0, 0.1, Dff),
            "W2": rng.normal(0, 1 / math.sqrt(Dff), (Dff, D)), "b2": rng.normal(0, 0.1, D)}


def attention_as_matrix(X, Wq, Wk, Wv):
    """Exercise 12.6: for the input X, the ND x ND matrix M with vec(Y) = M vec(X) (row-major vec).

    Block (n, m) of M is a_nm Wv^T: every block is a multiple of the same D x D matrix (parameter
    sharing), the multiples being the attention weights.
    """
    _, A = self_attention(X, Wq, Wk, Wv)
    return np.kron(A, Wv.T)


def layer_flops(N, D, H=None, Dff=None):
    """Multiply-adds of one transformer layer (Section 12.1.8), split into the two kinds of term.

    Returns (attention_pairs, per_token): attention_pairs = 2 N^2 D (scores Q K^T and the product
    A V), per_token = 4 N D^2 (the four projections) + 2 N D Dff (the MLP).
    """
    Dff = 4 * D if Dff is None else Dff
    return 2 * N * N * D, 4 * N * D * D + 2 * N * D * Dff


def param_count_layer(D, H, Dk=None, Dv=None, Dff=None, bias=True, ln=True):
    """Number of parameters of one transformer layer (multi-head attention + MLP + 2 layer norms)."""
    Dk = D // H if Dk is None else Dk
    Dv = D // H if Dv is None else Dv
    Dff = 4 * D if Dff is None else Dff
    att = H * (2 * D * Dk + D * Dv) + H * Dv * D
    if bias:
        att += H * (2 * Dk + Dv) + D
    ff = 2 * D * Dff + ((Dff + D) if bias else 0)
    return att + ff + (4 * D if ln else 0)


def bert_large_params():
    """Exercise 12.16: parameters of BERT-Large (24 layers, D = 1024, 16 heads of 64, MLP 4096)."""
    D, V, Nmax = 1024, 30000, 512
    layers = 24 * param_count_layer(D, 16, 64, 64, 4096)
    emb = V * D + Nmax * D + 2 * D + 2 * D     # tokens, positions, two segment vectors, embedding LN
    pooler = D * D + D
    return {"layers": layers, "embeddings": emb, "pooler": pooler, "total": layers + emb + pooler}


# ================================================================ position encodings
def sinusoidal_pe(N, D, L=10000.0, start=0):
    """(12.25): r_ni = sin(n / L^(i/D)) for even i, cos(n / L^((i-1)/D)) for odd i (i = 0..D-1)."""
    n = np.arange(start, start + N, dtype=float)[:, None]
    i = np.arange(D)
    expo = np.where(i % 2 == 0, i, i - 1) / D
    ang = n / (L ** expo)[None, :]
    return np.where(i % 2 == 0, np.sin(ang), np.cos(ang))


def pe_frequencies(D, L=10000.0):
    """Angular frequencies omega_j = L^(-2j/D) of the D/2 sine-cosine pairs."""
    return L ** (-2.0 * np.arange(D // 2) / D)


def pe_shift_matrix(k, D, L=10000.0):
    """The block-diagonal matrix M(k) with r_{n+k} = M(k) r_n for every n (Exercise 12.10).

    Each 2 x 2 block, acting on (sin w n, cos w n), is [[cos wk, sin wk], [-sin wk, cos wk]]: a
    rotation by the angle -w k that depends on the offset k only.
    """
    M = np.zeros((D, D))
    for j, w in enumerate(pe_frequencies(D, L)):
        c, s = math.cos(w * k), math.sin(w * k)
        M[2 * j:2 * j + 2, 2 * j:2 * j + 2] = [[c, s], [-s, c]]
    return M


# =========================================================================== 12.2 natural language
TEXT_URL = "https://www.gutenberg.org/cache/epub/11/pg11.txt"
ALLOWED = set("abcdefghijklmnopqrstuvwxyz .,;:!?'\"-()\n")


def corpus(raw_path=None):
    """The character corpus: Alice's Adventures in Wonderland (Carroll, 1865; public domain).

    The text between the licence header and footer is lower-cased; curly quotes become straight,
    dashes become '-', line breaks inside a paragraph become spaces, a paragraph break becomes one
    newline, and any other character is dropped. Returns the string (about 140 000 characters).
    """
    raw_path = raw_path or os.path.join(common.CACHE, "text", "alice.txt")
    if not os.path.exists(raw_path):
        common._download([TEXT_URL], raw_path)
    with open(raw_path, encoding="utf-8-sig") as f:
        s = f.read()
    a = s.index("*** START OF")
    a = s.index("\n", a) + 1
    b = s.index("*** END OF")
    s = s[a:b]
    k = s.find("CHAPTER I.", s.find("CHAPTER I.") + 1)   # skip the table of contents
    s = s[k:] if k > 0 else s
    s = s.replace("\r", "")
    for x, y in (("\u2018", "'"), ("\u2019", "'"), ("\u201c", '"'), ("\u201d", '"'), ("\u2014", "-"),
                 ("\u2013", "-"), ("_", ""), ("*", "")):
        s = s.replace(x, y)
    s = s.lower()
    paras = [re.sub(r"\s+", " ", p).strip() for p in re.split(r"\n\s*\n", s)]
    s = "\n".join(p for p in paras if p)
    s = "".join(ch for ch in s if ch in ALLOWED)
    s = re.sub(r" +", " ", s)
    return s


def corpus_split(text, frac=0.9):
    k = int(len(text) * frac)
    return text[:k], text[k:]


# ================================================================ byte-pair encoding
def bpe_learn(text, n_merges, words=True):
    """Byte-pair encoding (Sennrich, Haddow and Birch, 2015) as described in Section 12.2.2.

    Starts from single characters and repeatedly merges the most frequent adjacent pair of tokens.
    With words=True a merge never crosses white space (the text is split into words first, and each
    word keeps a leading space marker except the first). Ties are broken deterministically in the
    text: ties in the count go to the shorter new token, then to the pair that occurs first (with
this rule the merges on the book's sentence come out in the book's order). Returns the list of
merges [(a, b), ...] and the token sequences after each merge.
    """
    if words:
        parts = re.findall(r"\S+|\s+", text)
        seqs = [list(w) for w in parts]
    else:
        seqs = [list(text)]
    merges, history = [], [[t for s in seqs for t in s]]
    for _ in range(n_merges):
        counts, first = collections.Counter(), {}
        pos = 0
        for s in seqs:
            if s and s[0].isspace():
                pos += len(s)
                continue
            for i in range(len(s) - 1):
                p = (s[i], s[i + 1])
                counts[p] += 1
                first.setdefault(p, pos + i)
            pos += len(s)
        if not counts:
            break
        best = max(counts, key=lambda p: (counts[p], -len(p[0] + p[1]), -first[p]))
        if counts[best] < 2:
            break
        merges.append(best)
        new = best[0] + best[1]
        out = []
        for s in seqs:
            t, i = [], 0
            while i < len(s):
                if i < len(s) - 1 and (s[i], s[i + 1]) == best:
                    t.append(new)
                    i += 2
                else:
                    t.append(s[i])
                    i += 1
            out.append(t)
        seqs = out
        history.append([t for s in seqs for t in s])
    return merges, history


def bpe_encode(text, merges):
    """Apply learned merges, in order, to new text (words separately); returns the token list."""
    parts = re.findall(r"\S+|\s+", text)
    toks = []
    for w in parts:
        s = list(w)
        if not w[0].isspace():
            for a, b in merges:
                i, t = 0, []
                while i < len(s):
                    if i < len(s) - 1 and s[i] == a and s[i + 1] == b:
                        t.append(a + b)
                        i += 2
                    else:
                        t.append(s[i])
                        i += 1
                s = t
        toks.extend(s)
    return toks


# ================================================================ n-gram models
def ngram_counts(seq, n):
    """Counts of all n-grams (tuples) in a token sequence."""
    return collections.Counter(tuple(seq[i:i + n]) for i in range(len(seq) - n + 1))


def ngram_logprob(train, test, n, vocab, alpha=0.1):
    """Average log-probability per token of `test` under an add-alpha smoothed n-gram model.

    p(x | context) = (c(context, x) + alpha) / (c(context) + alpha K), the counts c(context)
    being the (n-1)-grams that are followed by a token (Exercise 12.13). The first n-1 test tokens
    use the training text before them as context (test is a continuation of train).
    """
    K = len(vocab)
    if n == 1:
        c = collections.Counter(train)
        tot = len(train)
        lp = [math.log((c[x] + alpha) / (tot + alpha * K)) for x in test]
        return float(np.mean(lp))
    cn = ngram_counts(train, n)
    cc = collections.Counter(tuple(train[i:i + n - 1]) for i in range(len(train) - n + 1))
    full = train[-(n - 1):] + test
    lp = []
    for i in range(n - 1, len(full)):
        ctx = tuple(full[i - n + 1:i])
        lp.append(math.log((cn[ctx + (full[i],)] + alpha) / (cc[ctx] + alpha * K)))
    return float(np.mean(lp))


def best_alpha_ngram(train, val, n, vocab, alphas=(0.003, 0.01, 0.03, 0.1, 0.3, 1.0)):
    """Smoothing constant chosen on the second half of the validation text; returns (alpha, lp)."""
    h = len(val) // 2
    tune = {a: ngram_logprob(train, val[:h], n, vocab, a) for a in alphas}
    a = max(tune, key=tune.get)
    return a, ngram_logprob(train, val, n, vocab, a)


def words_of(text):
    return re.findall(r"[a-z]+(?:'[a-z]+)?", text)


def next_word_distribution(text, context, top=None):
    """Maximum-likelihood bigram distribution p(next word | previous word(s) = context)."""
    w = words_of(text)
    ctx = tuple(context.split())
    n = len(ctx)
    c = collections.Counter(w[i + n] for i in range(len(w) - n) if tuple(w[i:i + n]) == ctx)
    items = c.most_common(top)
    tot = sum(c.values())
    return [k for k, _ in items], np.array([v for _, v in items], float) / tot, tot


def sgns_optimum(C, k):
    """Skip-gram with negative sampling (Mikolov et al., 2013) at its optimum (Levy and Goldberg, 2014).

    For a co-occurrence count table C (words x contexts) and k negative samples drawn from the
    unigram context distribution, the per-pair objective
        #(w,c) log s(x) + k #(w) #(c) / |D| log s(-x)
    is maximised at x = log(#(w,c) |D| / (#(w) #(c))) - log k = PMI(w, c) - log k.
    Returns that matrix.
    """
    C = np.asarray(C, float)
    D = C.sum()
    return np.log(C * D / (C.sum(1, keepdims=True) * C.sum(0, keepdims=True))) - math.log(k)


# =========================================================================== 12.3 sampling rules
def temperature_probs(logits, T):
    """(12.35): softmax(a / T); T = 0 is greedy (all mass on the largest a, shared among ties)."""
    a = np.asarray(logits, float)
    if T == 0:
        m = (a == a.max()).astype(float)
        return m / m.sum()
    return softmax_rows(a / T)


def top_k_probs(p, k):
    """Keep the k largest probabilities and renormalise (ties broken by index)."""
    p = np.asarray(p, float)
    order = np.argsort(-p, kind="stable")
    q = np.zeros_like(p)
    q[order[:k]] = p[order[:k]]
    return q / q.sum()


def top_p_probs(p, top_p):
    """Nucleus sampling (Holtzman et al., 2019): the smallest set of most probable tokens whose total
    probability reaches top_p, renormalised."""
    p = np.asarray(p, float)
    order = np.argsort(-p, kind="stable")
    cum = np.cumsum(p[order])
    m = int(np.searchsorted(cum, top_p - 1e-12) + 1)
    m = min(m, len(p))
    q = np.zeros_like(p)
    q[order[:m]] = p[order[:m]]
    return q / q.sum()


def sampling_dist(logits, T=1.0, k=0, top_p=1.0):
    """Temperature first, then top-k (k > 0), then nucleus (top_p < 1): the order the demos use."""
    q = temperature_probs(logits, T)
    if k and k < len(q):
        q = top_k_probs(q, k)
    if top_p < 1.0:
        q = top_p_probs(q, top_p)
    return q


def entropy(p):
    p = np.asarray(p, float)
    nz = p > 0
    return float(-(p[nz] * np.log(p[nz])).sum())


def draw(q, u):
    """Inverse-CDF draw from q with the uniform u, scanning indices in order (as the demos do)."""
    c = 0.0
    last = 0
    for i, qi in enumerate(q):
        if qi <= 0:
            continue
        last = i
        c += qi
        if u < c:
            return i
    return last


def beam_search(step_logprobs, start, steps, B):
    """Beam search (Section 12.3.2) with beam width B over `steps` tokens.

    step_logprobs(seq) returns the vector of log p(next | seq). Each of the B hypotheses is
    extended by its B best tokens, and the best B of the B^2 extensions are kept. Returns the best
    final sequence and its total log-probability (B = 1 is greedy search).
    """
    beams = [(0.0, list(start))]
    for _ in range(steps):
        cand = []
        for lp, seq in beams:
            v = step_logprobs(seq)
            for j in np.argsort(-v, kind="stable")[:B]:
                cand.append((lp + float(v[j]), seq + [int(j)]))
        cand.sort(key=lambda c: -c[0])
        beams = cand[:B]
    return beams[0][1], beams[0][0]


def viterbi_bigram(logP, start, steps):
    """Exact most probable continuation of length `steps` under a bigram model (dynamic programming).

    logP[i, j] = log p(next = j | previous = i). Returns (sequence, total log-probability).
    """
    K = logP.shape[0]
    score = logP[start].copy()
    back = []
    for _ in range(steps - 1):
        cand = score[:, None] + logP
        back.append(np.argmax(cand, axis=0))
        score = cand.max(axis=0)
    j = int(np.argmax(score))
    best = float(score[j])
    seq = [j]
    for b in reversed(back):
        j = int(b[j])
        seq.append(j)
    return seq[::-1], best


# =========================================================================== 12.3 the character transformer
GPT_CFG = dict(D=64, H=4, L=2, Dff=256, N=64, pe_L=10000.0)


def _torch():
    return common.torch_setup(0, threads=1)


def gpt_init(V, D, H, L, Dff, N, seed=0, pe_L=10000.0):
    """Parameters of the decoder-only transformer (pre-norm, ReLU MLP, sinusoidal positions (12.25))."""
    torch = _torch()
    g = torch.Generator().manual_seed(seed)

    def W(*s, std):
        return (torch.randn(*s, generator=g) * std).requires_grad_()

    def Z(*s):
        return torch.zeros(*s).requires_grad_()

    def O(*s):
        return torch.ones(*s).requires_grad_()

    P = {"emb": W(V, D, std=0.5)}
    for l in range(L):
        P.update({
            "l%d.ln1.g" % l: O(D), "l%d.ln1.b" % l: Z(D),
            "l%d.Wq" % l: W(D, D, std=D ** -0.5), "l%d.bq" % l: Z(D),
            "l%d.Wk" % l: W(D, D, std=D ** -0.5), "l%d.bk" % l: Z(D),
            "l%d.Wv" % l: W(D, D, std=D ** -0.5), "l%d.bv" % l: Z(D),
            "l%d.Wo" % l: W(D, D, std=(D * 2 * L) ** -0.5), "l%d.bo" % l: Z(D),
            "l%d.ln2.g" % l: O(D), "l%d.ln2.b" % l: Z(D),
            "l%d.W1" % l: W(D, Dff, std=D ** -0.5), "l%d.b1" % l: Z(Dff),
            "l%d.W2" % l: W(Dff, D, std=(Dff * 2 * L) ** -0.5), "l%d.b2" % l: Z(D)})
    P.update({"lnf.g": O(D), "lnf.b": Z(D), "Wp": W(D, V, std=D ** -0.5), "bp": Z(V)})
    return P


def gpt_forward_torch(P, idx, cfg, return_att=False):
    """Forward pass in PyTorch: idx is a (B, N) tensor of token ids; returns logits (B, N, V)."""
    torch = _torch()
    D, H, L = cfg["D"], cfg["H"], cfg["L"]
    B, N = idx.shape
    pe = torch.tensor(sinusoidal_pe(N, D, cfg["pe_L"]), dtype=P["emb"].dtype)
    x = P["emb"][idx] + pe
    mask = torch.triu(torch.full((N, N), float("-inf"), dtype=x.dtype), 1)
    atts = []

    def ln(z, g, b):
        mu = z.mean(-1, keepdim=True)
        var = ((z - mu) ** 2).mean(-1, keepdim=True)
        return (z - mu) / torch.sqrt(var + 1e-5) * g + b

    dk = D // H
    for l in range(L):
        p = lambda k: P["l%d.%s" % (l, k)]  # noqa: E731
        h = ln(x, p("ln1.g"), p("ln1.b"))
        q = (h @ p("Wq") + p("bq")).view(B, N, H, dk).transpose(1, 2)
        k = (h @ p("Wk") + p("bk")).view(B, N, H, dk).transpose(1, 2)
        v = (h @ p("Wv") + p("bv")).view(B, N, H, dk).transpose(1, 2)
        A = torch.softmax(q @ k.transpose(-1, -2) / math.sqrt(dk) + mask, dim=-1)
        if return_att:
            atts.append(A)
        o = (A @ v).transpose(1, 2).reshape(B, N, D)
        x = x + o @ p("Wo") + p("bo")
        h = ln(x, p("ln2.g"), p("ln2.b"))
        x = x + torch.relu(h @ p("W1") + p("b1")) @ p("W2") + p("b2")
    x = ln(x, P["lnf.g"], P["lnf.b"])
    logits = x @ P["Wp"] + P["bp"]
    return (logits, atts) if return_att else logits


def gpt_forward(W, ids, cfg, return_att=False):
    """The same forward pass in numpy (float64), for one sequence of ids: the one the browser runs.

    W maps parameter names to numpy arrays. Returns the logits (N, V) and optionally the attention
    weights att[l][h] (N x N) of every layer and head.
    """
    D, H, L = cfg["D"], cfg["H"], cfg["L"]
    N = len(ids)
    x = W["emb"][np.asarray(ids)] + sinusoidal_pe(N, D, cfg["pe_L"])
    mask = causal_mask(N)
    dk = D // H
    atts = []
    for l in range(L):
        p = lambda k: W["l%d.%s" % (l, k)]  # noqa: E731
        h = layer_norm(x, p("ln1.g"), p("ln1.b"))
        q, k, v = h @ p("Wq") + p("bq"), h @ p("Wk") + p("bk"), h @ p("Wv") + p("bv")
        heads, al = [], []
        for hh in range(H):
            sl = slice(hh * dk, (hh + 1) * dk)
            Y, A = attention(q[:, sl], k[:, sl], v[:, sl], mask=mask)
            heads.append(Y)
            al.append(A)
        atts.append(al)
        x = x + np.concatenate(heads, axis=1) @ p("Wo") + p("bo")
        h = layer_norm(x, p("ln2.g"), p("ln2.b"))
        x = x + mlp(h, p("W1"), p("b1"), p("W2"), p("b2"))
    x = layer_norm(x, W["lnf.g"], W["lnf.b"])
    logits = x @ W["Wp"] + W["bp"]
    return (logits, atts) if return_att else logits


def _batches(data, N, B, rng):
    i = rng.integers(0, len(data) - N - 1, size=B)
    X = np.stack([data[j:j + N] for j in i])
    Y = np.stack([data[j + 1:j + N + 1] for j in i])
    return X, Y


def train_gpt(data_tr, data_va, V, cfg, steps, lr=3e-3, B=32, seed=0, log_every=100, bos=None):
    """Train with Adam (Section 7.3.3), a short warm-up and cosine decay, on random windows of the text.

    Returns the float32 parameters (dict of numpy arrays) and the training history.
    """
    torch = _torch()
    torch.manual_seed(seed)
    P = gpt_init(V, cfg["D"], cfg["H"], cfg["L"], cfg["Dff"], cfg["N"], seed=seed, pe_L=cfg["pe_L"])
    opt = torch.optim.Adam(list(P.values()), lr=lr, betas=(0.9, 0.99))
    rng = np.random.default_rng(seed)
    hist = {"step": [], "train": [], "val": []}
    warm = max(1, steps // 20)
    run_loss = []
    vrng = np.random.default_rng(12345)
    Xv, Yv = _batches(data_va, cfg["N"], 256, vrng)
    Xv, Yv = torch.tensor(Xv), torch.tensor(Yv)
    t0 = time.time()
    for s in range(1, steps + 1):
        f = s / warm if s <= warm else 0.5 * (1 + math.cos(math.pi * (s - warm) / (steps - warm)))
        for gr in opt.param_groups:
            gr["lr"] = lr * max(f, 0.02)
        X, Y = _batches(data_tr, cfg["N"], B, rng)
        logits = gpt_forward_torch(P, torch.tensor(X), cfg)
        loss = torch.nn.functional.cross_entropy(logits.reshape(-1, V), torch.tensor(Y).reshape(-1))
        opt.zero_grad()
        loss.backward()
        torch.nn.utils.clip_grad_norm_(list(P.values()), 1.0)
        opt.step()
        run_loss.append(loss.item())
        if s % log_every == 0 or s == steps:
            with torch.no_grad():
                lv = torch.nn.functional.cross_entropy(gpt_forward_torch(P, Xv, cfg).reshape(-1, V),
                                                       Yv.reshape(-1)).item()
            hist["step"].append(s)
            hist["train"].append(float(np.mean(run_loss[-log_every:])))
            hist["val"].append(lv)
            print("  step %5d  train %.3f  val %.3f  (%.0f s)" % (s, hist["train"][-1], lv, time.time() - t0))
    W = {k: v.detach().numpy().astype(np.float32) for k, v in P.items()}
    return W, hist


def char_model():
    """The trained character transformer (cached): weights, vocabulary, history and test numbers."""
    def fit():
        text = corpus()
        chars = sorted(set(text))
        stoi = {c: i for i, c in enumerate(chars)}
        data = np.array([stoi[c] for c in text], dtype=np.int64)
        tr, va = corpus_split(data)
        W, hist = train_gpt(tr, va, len(chars), GPT_CFG, steps=3000, lr=3e-3, B=32)
        return {"W": W, "chars": "".join(chars), "hist": hist, "sha": hashlib.sha256(text.encode()).hexdigest()}
    return _cached("ch12_char_gpt", fit)


def as64(W):
    """float32 weights -> float64 arrays (what the browser computes with)."""
    return {k: np.asarray(v, np.float32).astype(np.float64) for k, v in W.items()}


def gpt_nll(W, ids, cfg, stride=None):
    """Average negative log-likelihood (nats per token) of a long id sequence, in windows of N tokens.

    Each window predicts its tokens 2..N from the ones before (the first window also scores token 1
    given nothing would need a start token, so it is skipped); consecutive windows overlap by half
    so every scored token has at least N/2 tokens of context, except at the very start.
    """
    N = cfg["N"]
    stride = stride or N // 2
    tot, cnt = 0.0, 0
    first = True
    for a in range(0, len(ids) - N, stride):
        w = ids[a:a + N + 1]
        lg = gpt_forward(W, w[:N], cfg)
        lp = lg - common.logsumexp(lg, axis=1, keepdims=True)
        tgt = w[1:N + 1]
        lo = 0 if first else N - stride
        first = False
        tot += -lp[np.arange(lo, N), tgt[lo:]].sum()
        cnt += N - lo
    return tot / cnt


def generate(W, cfg, chars, prompt, n, seed=1, T=1.0, k=0, top_p=1.0):
    """Sample n characters after `prompt` with the demo's generator and rules; returns (text, probs).

    probs[i] is the model probability (at T = 1, no truncation) of the i-th generated character.
    The context is the last N characters. Greedy decoding is T = 0.
    """
    stoi = {c: i for i, c in enumerate(chars)}
    ids = [stoi[c] for c in prompt]
    rng = JSRandom(seed)
    probs = []
    for _ in range(n):
        ctx = ids[-cfg["N"]:]
        lg = gpt_forward(W, ctx, cfg)[-1]
        q = sampling_dist(lg, T, k, top_p)
        j = int(np.argmax(q)) if T == 0 else draw(q, rng.u())
        probs.append(float(softmax_rows(lg)[j]))
        ids.append(j)
    return "".join(chars[i] for i in ids[len(prompt):]), probs


def b64_f32(a):
    return base64.b64encode(np.ascontiguousarray(a, dtype="<f4").tobytes()).decode("ascii")


def export_char_model(path=None):
    """Write ../data/ch12-char-gpt.json: config, vocabulary and float32 weights (base64), plus 400
    characters of the held-out text (its first 64 are the prompt of beam_vs_text, Figure 12.17)."""
    m = char_model()
    text = corpus()
    _, va = corpus_split(text)
    out = {"cfg": GPT_CFG, "chars": m["chars"], "order": list(m["W"].keys()),
           "shapes": {k: list(v.shape) for k, v in m["W"].items()},
           "weights": {k: b64_f32(v) for k, v in m["W"].items()},
           "heldout": va[2000:2400],
           "valCE": float(ngram_baselines()["gpt"]) if os.path.exists(os.path.join(CACHE_DIR, "ch12_ngram.npz")) else None,
           "note": "Character transformer trained on Alice's Adventures in Wonderland (Lewis Carroll, 1865, "
                   "public domain), Bishop and Bishop (2024), Chapter 12; see code/ch12_transformers.py."}
    path = path or os.path.join(JSON_DIR, "ch12-char-gpt.json")
    os.makedirs(os.path.dirname(path), exist_ok=True)
    with open(path, "w") as f:
        json.dump(out, f, separators=(",", ":"))
    return path


SAMPLING_CONTEXTS = ["the", "said the", "alice", "she", "in a"]


def export_sampling(path=None):
    """Write ../data/ch12-sampling.json: next-word distributions from the corpus for the sampling demo,
    and a word bigram model (the 60 commonest words) for the sequence-search panel."""
    text = corpus()
    ctxs = []
    for c in SAMPLING_CONTEXTS:
        words, p, tot = next_word_distribution(text, c)
        ctxs.append({"context": c, "words": words, "counts": [int(round(x * tot)) for x in p], "total": int(tot)})
    w = words_of(text)
    top = [k for k, _ in collections.Counter(w).most_common(60)]
    ix = {k: i for i, k in enumerate(top)}
    C = np.zeros((60, 60))
    for a, b in zip(w[:-1], w[1:]):
        if a in ix and b in ix:
            C[ix[a], ix[b]] += 1
    out = {"contexts": ctxs, "bigram": {"words": top, "counts": C.astype(int).tolist()},
           "note": "Word counts from Alice's Adventures in Wonderland (Lewis Carroll, 1865, public domain)."}
    path = path or os.path.join(JSON_DIR, "ch12-sampling.json")
    with open(path, "w") as f:
        json.dump(out, f, separators=(",", ":"))
    return path, out


def bigram_logP(counts, alpha=0.5):
    """Add-alpha smoothed log p(next | previous) from a square count table (the demo's search panel)."""
    C = np.asarray(counts, float) + alpha
    return np.log(C / C.sum(1, keepdims=True))


# =========================================================================== the attention explorer
def explorer_inputs(words, D, seed, mode="independent", inputs="words", s=1.0):
    """Token vectors and weight matrices of attention-explorer-demo.html, from the demo's generator.

    The distinct words, in alphabetical order, get embeddings with N(0, 1) entries; then W_q, W_k,
    W_v (D x D, row by row) with N(0, 1/D) entries. mode 'identity' uses W_q = W_k = W_v = I
    ((12.5)-(12.6)); 'shared' uses W_q = W_k = W_v = U = W_q ((12.7)-(12.8)); 'independent' uses
    (12.10)-(12.12). inputs 'orthogonal' replaces the embeddings by s times the unit vectors e_1,
    e_2, ... (one per position; needs N <= D), the orthogonal inputs of Exercise 12.3; 'none' sets
    them to zero, so that only the position encodings remain.
    """
    rng = JSRandom(seed)
    vocab = sorted(set(words))
    emb = {w: rng.normals(D) for w in vocab}
    Wq = rng.normals(D * D).reshape(D, D) / math.sqrt(D)
    Wk = rng.normals(D * D).reshape(D, D) / math.sqrt(D)
    Wv = rng.normals(D * D).reshape(D, D) / math.sqrt(D)
    if inputs == "orthogonal":
        X = np.zeros((len(words), D))
        X[np.arange(len(words)), np.arange(len(words))] = s
    elif inputs == "none":
        X = np.zeros((len(words), D))
    else:
        X = np.stack([emb[w] for w in words])
    if mode == "identity":
        Wq = Wk = Wv = np.eye(D)
    elif mode == "shared":
        Wk = Wv = Wq
    return X, Wq, Wk, Wv


def explorer_attention(words, D=16, seed=1, mode="independent", inputs="words", s=1.0, scale=True, T=1.0,
                       causal=False, pe=0.0, perm=None):
    """The attention matrix the explorer shows: rows are queries, columns keys.

    pe is the amplitude of the sinusoidal encoding (12.25) (L = 10000) added to the inputs (12.24);
    perm, if given, reorders the words before anything else (positions stay 0..N-1).
    """
    if perm is not None:
        words = [words[i] for i in perm]
    X, Wq, Wk, Wv = explorer_inputs(words, D, seed, mode, inputs, s)
    X = X + pe * sinusoidal_pe(len(words), D)
    mask = causal_mask(len(words)) if causal else None
    Y, A = attention(X @ Wq, X @ Wk, X @ Wv, mask=mask, scale=scale, temperature=T)
    return A, Y


def js_shuffle(n, seed):
    """Fisher-Yates permutation with the demo's generator (as ML.shuffle in ml-kit.js)."""
    rng = JSRandom(seed)
    a = list(range(n))
    for i in range(n - 1, 0, -1):
        j = int(math.floor(rng.u() * (i + 1)))
        a[i], a[j] = a[j], a[i]
    return a


# =========================================================================== 12.4 multimodal pieces
def patchify(img, P):
    """Split an H x W (x C) image into non-overlapping P x P patches, each flattened (Section 12.4.1).

    Returns an (HW/P^2) x (P^2 C) matrix whose rows follow the raster order of the patches.
    """
    img = np.asarray(img)
    if img.ndim == 2:
        img = img[:, :, None]
    H, W, C = img.shape
    x = img.reshape(H // P, P, W // P, P, C).transpose(0, 2, 1, 3, 4)
    return x.reshape((H // P) * (W // P), P * P * C)


def vector_quantise(X, C):
    """(12.38): replace each row of X by the index of its nearest codebook vector (Euclidean)."""
    d = ((X[:, None, :] - C[None, :, :]) ** 2).sum(-1)
    return np.argmin(d, axis=1)


def hz_to_mel(f):
    """The mel scale m = 2595 log10(1 + f / 700) (O'Shaughnessy's formula)."""
    return 2595.0 * np.log10(1.0 + np.asarray(f, float) / 700.0)


def mel_to_hz(m):
    return 700.0 * (10.0 ** (np.asarray(m, float) / 2595.0) - 1.0)


def mel_filterbank(n_mels, n_fft, sr, fmin=0.0, fmax=None):
    """Triangular filters equally spaced on the mel scale; returns an n_mels x (n_fft/2 + 1) matrix."""
    fmax = fmax or sr / 2
    edges = mel_to_hz(np.linspace(hz_to_mel(fmin), hz_to_mel(fmax), n_mels + 2))
    f = np.linspace(0, sr / 2, n_fft // 2 + 1)
    Fb = np.zeros((n_mels, len(f)))
    for m in range(n_mels):
        lo, c, hi = edges[m], edges[m + 1], edges[m + 2]
        Fb[m] = np.clip(np.minimum((f - lo) / (c - lo), (hi - f) / (hi - c)), 0, None)
    return Fb, edges


def mel_spectrogram(x, sr, n_fft=512, hop=128, n_mels=64, fmin=50.0, fmax=None):
    """Power spectrogram (Hann window) mapped to mel bands, in decibels; returns (S_db, times, mel edges)."""
    w = np.hanning(n_fft)
    frames = np.array([x[i:i + n_fft] * w for i in range(0, len(x) - n_fft, hop)])
    P = np.abs(np.fft.rfft(frames, axis=1)) ** 2
    Fb, edges = mel_filterbank(n_mels, n_fft, sr, fmin, fmax)
    S = P @ Fb.T
    S_db = 10 * np.log10(np.maximum(S, 1e-10))
    t = (np.arange(len(frames)) * hop + n_fft / 2) / sr
    return S_db.T, t, edges


def whale_song(sr=8000, seconds=8.0, seed=3):
    """A synthetic stand-in for a humpback whale song: frequency-modulated units with harmonics.

    Each unit is a sweep f(t) = f0 + (f1 - f0) s(t) with a smooth sweep shape s, two harmonics at
    reduced amplitude, a raised-cosine envelope, and low-level noise.
    """
    rng = np.random.default_rng(seed)
    n = int(sr * seconds)
    x = 0.003 * rng.normal(size=n)
    units = [(0.2, 0.9, 220, 520), (1.1, 1.6, 600, 300), (1.9, 2.3, 150, 160), (2.5, 3.3, 300, 900),
             (3.6, 4.0, 800, 780), (4.2, 4.6, 800, 760), (4.9, 5.8, 900, 250), (6.0, 6.3, 180, 420),
             (6.5, 7.6, 420, 1100)]
    t = np.arange(n) / sr
    for a, b, f0, f1 in units:
        sel = (t >= a) & (t < b)
        u = (t[sel] - a) / (b - a)
        f = f0 + (f1 - f0) * (0.5 - 0.5 * np.cos(np.pi * u))
        ph = 2 * np.pi * np.cumsum(f) / sr
        env = np.sin(np.pi * u) ** 2
        x[sel] += env * (np.sin(ph) + 0.35 * np.sin(2 * ph) + 0.15 * np.sin(3 * ph))
    return x, sr


# ================================================================ tiny pixel transformer (Figure 12.24)
PIX_CFG = dict(D=48, H=4, L=2, Dff=192, N=196, pe_L=10000.0)


def binary_digits(n=6000, size=14, seed=0):
    """MNIST digits shrunk to size x size by 2 x 2 averaging and thresholded at 0.5 (binary pixels)."""
    X, y = common.mnist(train=True)
    X = X[:n].reshape(-1, 28, 28)
    X = X.reshape(-1, size, 28 // size, size, 28 // size).mean((2, 4))
    return (X > 0.5).astype(np.int64).reshape(len(X), -1), y[:n]


def pixel_model():
    """A decoder-only transformer over the 196 binary pixels of a 14 x 14 digit in raster order (cached).

    Tokens: 0 = black, 1 = white, 2 = <start>. Trained like the language model, by next-token
    cross-entropy with the causal mask, on 6000 binarised MNIST digits.
    """
    def fit():
        torch = _torch()
        X, _ = binary_digits()
        cfg = PIX_CFG
        P = gpt_init(3, cfg["D"], cfg["H"], cfg["L"], cfg["Dff"], cfg["N"], seed=1)
        opt = torch.optim.Adam(list(P.values()), lr=3e-3, betas=(0.9, 0.99))
        rng = np.random.default_rng(1)
        steps, B, hist = 1000, 24, []
        t0 = time.time()
        for s in range(1, steps + 1):
            f = min(1.0, s / 50) * 0.5 * (1 + math.cos(math.pi * s / steps))
            for gr in opt.param_groups:
                gr["lr"] = 3e-3 * max(f, 0.02)
            Y = X[rng.integers(0, len(X), B)]
            Xin = np.concatenate([np.full((B, 1), 2), Y[:, :-1]], axis=1)
            logits = gpt_forward_torch(P, torch.tensor(Xin), cfg)
            loss = torch.nn.functional.cross_entropy(logits.reshape(-1, 3), torch.tensor(Y).reshape(-1))
            opt.zero_grad()
            loss.backward()
            torch.nn.utils.clip_grad_norm_(list(P.values()), 1.0)
            opt.step()
            hist.append(loss.item())
            if s % 250 == 0:
                print("  pixel model step %d  loss %.3f  (%.0f s)" % (s, np.mean(hist[-250:]), time.time() - t0))
        return {"W": {k: v.detach().numpy().astype(np.float32) for k, v in P.items()}, "hist": hist}
    return _cached("ch12_pixel_gpt", fit)


def sample_pixels(W, n_img=4, seed=0):
    """Raster-scan ancestral sampling (12.37): each pixel from p(x_n | x_1..x_{n-1}), one at a time."""
    rng = np.random.default_rng(seed)
    out = []
    for _ in range(n_img):
        seq = [2]
        for _ in range(196):
            lg = gpt_forward(W, seq, PIX_CFG)[-1][:2]
            p1 = 1.0 / (1.0 + math.exp(lg[0] - lg[1]))
            seq.append(int(rng.random() < p1))
        out.append(np.array(seq[1:]))
    return np.array(out)


# ================================================================ tiny vision transformer (Figure 12.S7)
def vit_results():
    """A tiny ViT (Dosovitskiy et al., 2020) on MNIST: 7 x 7 patches -> 16 tokens + <class>, learned
    positions, 2 post-norm layers (Algorithm 12.3), D = 64, 4 heads; 10 000 training digits (cached)."""
    def fit():
        torch = common.torch_setup(2, threads=1)
        Xtr, ytr = common.mnist(train=True)
        Xte, yte = common.mnist(train=False)
        Xtr, ytr, Xte, yte = Xtr[:10000], ytr[:10000], Xte[:2000], yte[:2000]
        pt = lambda X: torch.tensor(np.stack([patchify(x.reshape(28, 28), 7) for x in X]), dtype=torch.float32)  # noqa: E731
        Ptr, Pte = pt(Xtr), pt(Xte)
        D, H, L = 64, 4, 2
        nn = torch.nn

        class ViT(nn.Module):
            def __init__(self):
                super().__init__()
                self.embed = nn.Linear(49, D)
                self.cls = nn.Parameter(torch.zeros(1, 1, D))
                self.pos = nn.Parameter(0.02 * torch.randn(1, 17, D))
                self.layers = nn.ModuleList([nn.TransformerEncoderLayer(D, H, 4 * D, dropout=0.0, batch_first=True,
                                                                        norm_first=False) for _ in range(L)])
                self.head = nn.Linear(D, 10)

            def forward(self, x, keep=False):
                z = torch.cat([self.cls.expand(len(x), -1, -1), self.embed(x)], 1) + self.pos
                att = None
                for i, layer in enumerate(self.layers):
                    if keep and i == L - 1:
                        _, att = layer.self_attn(z, z, z, need_weights=True, average_attn_weights=True)
                    z = layer(z)
                return self.head(z[:, 0]), att

        net = ViT()
        opt = torch.optim.Adam(net.parameters(), lr=2e-3)
        rng = np.random.default_rng(2)
        steps, B, curve = 2500, 64, []
        for s in range(1, steps + 1):
            for gr in opt.param_groups:
                gr["lr"] = 2e-3 * 0.5 * (1 + math.cos(math.pi * s / steps))
            i = rng.integers(0, len(Ptr), B)
            loss = nn.functional.cross_entropy(net(Ptr[i])[0], torch.tensor(ytr[i]))
            opt.zero_grad()
            loss.backward()
            opt.step()
            if s % 250 == 0:
                with torch.no_grad():
                    acc = (net(Pte)[0].argmax(1).numpy() == yte).mean()
                curve.append((s, float(acc)))
                print("  ViT step %d  test accuracy %.3f" % (s, acc))
        with torch.no_grad():
            _, att = net(Pte[:8], keep=True)
        return {"curve": np.array(curve), "att": att.numpy(), "X": Xte[:8], "y": yte[:8],
                "params": sum(p.numel() for p in net.parameters())}
    return _cached("ch12_vit", fit)


# ================================================================ BPE on the whole corpus
def bpe_learn_counts(word_counts, n_merges):
    """Byte-pair encoding on a table of word frequencies (the efficient form of bpe_learn).

    Same tie rule as bpe_learn (count, then shorter token, then alphabetical as the order of first
    occurrence is not kept). Returns the merges and, after each merge, the vocabulary size and the
    total number of tokens.
    """
    words = {tuple(w): c for w, c in word_counts.items()}
    vocab = set(ch for w in words for ch in w)
    merges, sizes, lengths = [], [len(vocab)], [sum(len(w) * c for w, c in words.items())]
    for _ in range(n_merges):
        counts = collections.Counter()
        for w, c in words.items():
            for i in range(len(w) - 1):
                counts[(w[i], w[i + 1])] += c
        if not counts:
            break
        best = max(counts, key=lambda p: (counts[p], -len(p[0] + p[1]), tuple(-ord(ch) for ch in p[0] + p[1])))
        if counts[best] < 2:
            break
        new = best[0] + best[1]
        nw = {}
        for w, c in words.items():
            t, i = [], 0
            while i < len(w):
                if i < len(w) - 1 and (w[i], w[i + 1]) == best:
                    t.append(new)
                    i += 2
                else:
                    t.append(w[i])
                    i += 1
            nw[tuple(t)] = nw.get(tuple(t), 0) + c
        words = nw
        vocab.add(new)
        merges.append(best)
        sizes.append(len(vocab))
        lengths.append(sum(len(w) * c for w, c in words.items()))
    return merges, np.array(sizes), np.array(lengths)


def corpus_bpe(n_merges=1500):
    def fit():
        text = corpus()
        tr, _ = corpus_split(text)
        wc = collections.Counter(re.findall(r"[^\s]+", tr))
        spaces = len(re.findall(r"\s", tr))
        merges, sizes, lengths = bpe_learn_counts(wc, n_merges)
        return {"merges": merges, "sizes": sizes, "lengths": lengths + spaces, "chars": len(tr)}
    return _cached("ch12_bpe_corpus", fit)


# =========================================================================== figures
def _char_model_64():
    m = char_model()
    return as64(m["W"]), m["chars"]


def fig_12_2(out_dir=None):
    """Learned attention weights (phenomenon of Figure 12.2), from the character transformer."""
    W, chars = _char_model_64()
    stoi = {c: i for i, c in enumerate(chars)}
    text = "the queen turned crimson with fury, and, after glaring at her"
    ids = [stoi[c] for c in text]
    _, att = gpt_forward(W, ids, GPT_CFG, return_att=True)
    # the head whose weights reach furthest back on average (a long-range head)
    N = len(ids)
    dist = np.abs(np.arange(N)[:, None] - np.arange(N)[None, :])
    reach = [[(a * dist).sum() / N for a in layer] for layer in att]
    l, h = np.unravel_index(np.argmax(reach), (GPT_CFG["L"], GPT_CFG["H"]))
    A = att[l][h]
    fig = plt.figure(figsize=(10.5, 4.5))
    ax = fig.add_axes([0.02, 0.4, 0.96, 0.52])
    xs = np.arange(N)
    for n in range(N):
        for m_ in range(n + 1):
            if A[n, m_] > 0.04:
                ax.plot([xs[m_], xs[n]], [1, 0], color=common.BLUE, alpha=min(1.0, 1.2 * A[n, m_]), lw=0.4 + 2.2 * A[n, m_])
    for i, c in enumerate(text):
        lab = "_" if c == " " else c
        ax.text(xs[i], 1.04, lab, ha="center", va="bottom", fontsize=9, family="monospace")
        ax.text(xs[i], -0.04, lab, ha="center", va="top", fontsize=9, family="monospace")
    ax.text(-1.5, 1.04, "keys", ha="right", va="bottom", fontsize=9, color=common.GREY)
    ax.text(-1.5, -0.04, "queries", ha="right", va="top", fontsize=9, color=common.GREY)
    ax.set_xlim(-6, N)
    ax.set_ylim(-0.25, 1.25)
    ax.axis("off")
    ax.set_title("layer %d, head %d: each query character (bottom) attends to earlier characters (top)" % (l + 1, h + 1),
                 fontsize=10)
    for j in range(GPT_CFG["L"] * GPT_CFG["H"]):
        lj, hj = divmod(j, GPT_CFG["H"])
        a2 = fig.add_axes([0.03 + 0.122 * j, 0.02, 0.11, 0.11 * 10.5 / 4.5])
        a2.imshow(att[lj][hj], cmap="Blues", vmin=0, vmax=1, interpolation="nearest")
        a2.set_xticks([])
        a2.set_yticks([])
        a2.set_title("L%d H%d" % (lj + 1, hj + 1), fontsize=9)
    savefig(fig, CH, "fig12-2", out_dir)


def fig_12_10(out_dir=None):
    """Sinusoidal position encodings (12.25): (a) six components against position, (b) heat map."""
    fig = plt.figure(figsize=(10, 5.2))
    ax = fig.add_axes([0.06, 0.12, 0.38, 0.8])
    D6, L6 = 6, 30.0
    pos = np.linspace(0, 50, 1001)
    R = sinusoidal_pe(len(pos), D6, L6)  # uses integer positions; recompute on the fine grid
    i = np.arange(D6)
    expo = np.where(i % 2 == 0, i, i - 1) / D6
    ang = pos[:, None] / (L6 ** expo)[None, :]
    R = np.where(i % 2 == 0, np.sin(ang), np.cos(ang))
    n_, m_ = 12, 36
    for k in range(D6):
        x0 = 2.6 * (D6 - 1 - k)
        col = common.BLUE if k % 2 == 0 else common.RED
        ax.plot(x0 + R[:, k], pos, color=col, lw=1.2)
        for p_ in (n_, m_):
            v = sinusoidal_pe(1, D6, L6, start=p_)[0, k]
            ax.plot(x0 + v, p_, "o", color=common.GREY, ms=4.5, zorder=3)
    for p_ in (n_, m_):
        ax.axhline(p_, color=common.GREY, lw=1, alpha=0.7)
    ax.set_xticks([2.6 * (D6 - 1 - k) for k in range(D6)])
    ax.set_xticklabels([r"$r_{%d}$" % (k + 1) for k in range(D6)])
    ax.set_yticks([n_, m_])
    ax.set_yticklabels(["n", "m"])
    ax.set_ylim(0, 50)
    ax.set_xlabel("embedding dimension")
    ax.set_ylabel("position")
    panel_label(ax, "a")
    ax2 = fig.add_axes([0.53, 0.12, 0.36, 0.8])
    P = sinusoidal_pe(200, 100, 30.0)
    im = ax2.imshow(P, cmap="gist_heat", origin="lower", aspect="auto", vmin=-1, vmax=1, interpolation="nearest")
    ax2.set_xlabel("embedding dimension")
    ax2.set_ylabel("position")
    cax = fig.add_axes([0.91, 0.12, 0.018, 0.8])
    fig.colorbar(im, cax=cax, ticks=[-1, 0, 1])
    panel_label(ax2, "b")
    savefig(fig, CH, "fig12-10", out_dir)


def fig_12_12(out_dir=None):
    """Byte-pair encoding of the book's sentence: the first five merges."""
    sent = "Peter Piper picked a peck of pickled peppers"
    merges, hist = bpe_learn(sent, 5)
    cols = [common.RED, common.BLUE, common.GREEN, common.PURPLE, "#e8a400"]
    tok_col = {}
    fig, ax = plt.subplots(figsize=(8.4, 3.4))
    cw = 0.0185
    for row, seq in enumerate(hist):
        if row > 0:
            a, b = merges[row - 1]
            tok_col[a + b] = cols[row - 1]
        y = 1 - row * 0.17
        x = 0.02
        for t in seq:
            new = row > 0 and t == merges[row - 1][0] + merges[row - 1][1]
            ax.text(x, y, t, family="monospace", fontsize=12, color=tok_col.get(t, "black"), va="center",
                    fontweight="bold" if new else "normal")
            if new:
                ax.plot([x, x + cw * len(t)], [y - 0.055, y - 0.055], color=tok_col[t], lw=1.6)
            x += cw * len(t)
        lab = "start: characters" if row == 0 else "merge %d: '%s' + '%s'" % (row, merges[row - 1][0], merges[row - 1][1])
        ax.text(0.86, y, lab, fontsize=9.5, va="center", color=common.GREY)
    ax.set_xlim(0, 1.12)
    ax.set_ylim(1 - 5 * 0.17 - 0.1, 1.08)
    ax.axis("off")
    savefig(fig, CH, "fig12-12", out_dir)


def fig_12_16(out_dir=None):
    """The mask of masked (causal) self-attention, with the weights of one masked head."""
    inputs = ["<start>", "I", "swam", "across", "the"]
    outputs = ["I", "swam", "across", "the", "river"]
    rng = np.random.default_rng(4)
    X = rng.normal(size=(5, 8))
    _, A = self_attention(X, 0.4 * rng.normal(size=(8, 8)), 0.4 * rng.normal(size=(8, 8)), np.eye(8), mask=causal_mask(5))
    fig, ax = plt.subplots(figsize=(4.8, 4.2))
    for n in range(5):
        for m_ in range(5):
            if m_ > n:
                ax.add_patch(plt.Rectangle((m_, 4 - n), 1, 1, color=common.RED, alpha=0.85))
            else:
                ax.add_patch(plt.Rectangle((m_, 4 - n), 1, 1, color=common.BLUE, alpha=0.15 + 0.75 * A[n, m_]))
                ax.text(m_ + 0.5, 4 - n + 0.5, "%.2f" % A[n, m_], ha="center", va="center", fontsize=8.5,
                        color="white" if A[n, m_] > 0.5 else "black")
    for k in range(6):
        ax.plot([k, k], [0, 5], color="white", lw=2)
        ax.plot([0, 5], [k, k], color="white", lw=2)
    ax.set_xlim(0, 5)
    ax.set_ylim(0, 5)
    ax.set_xticks(np.arange(5) + 0.5)
    ax.set_xticklabels(inputs, rotation=35, ha="left")
    ax.set_yticks(np.arange(5) + 0.5)
    ax.set_yticklabels(outputs[::-1])
    ax.set_xlabel("inputs (keys)")
    ax.set_ylabel("outputs (queries)")
    ax.xaxis.set_ticks_position("top")
    ax.xaxis.set_label_position("top")
    ax.tick_params(length=0)
    for s in ax.spines.values():
        s.set_visible(False)
    savefig(fig, CH, "fig12-16", out_dir)


def beam_vs_text(B=4, n=100):
    """Per-character probabilities of beam-search text and of the real continuation (Figure 12.17)."""
    def fit():
        W, chars = _char_model_64()
        stoi = {c: i for i, c in enumerate(chars)}
        _, va = corpus_split(corpus())
        prompt = va[2000:2064]
        human = va[2064:2064 + n]
        ids = [stoi[c] for c in prompt]

        def lp(seq):
            lg = gpt_forward(W, seq[-GPT_CFG["N"]:], GPT_CFG)[-1]
            return lg - common.logsumexp(lg)
        seq, _ = beam_search(lp, ids, n, B)
        beam = seq[len(ids):]
        pb, ph = [], []
        cur_b, cur_h = list(ids), list(ids)
        for j in range(n):
            pb.append(math.exp(lp(cur_b)[beam[j]]))
            cur_b.append(beam[j])
            hj = stoi[human[j]]
            ph.append(math.exp(lp(cur_h)[hj]))
            cur_h.append(hj)
        return {"prompt": prompt, "human": human, "beam": "".join(chars[i] for i in beam),
                "pb": np.array(pb), "ph": np.array(ph)}
    return _cached("ch12_beam_vs_text", fit)


def fig_12_17(out_dir=None):
    """Probabilities of the characters chosen by beam search and of the real text (phenomenon of 12.17)."""
    r = beam_vs_text()
    fig, axes = plt.subplots(1, 2, figsize=(11, 3.4), gridspec_kw={"width_ratios": [2.3, 1]})
    ax = axes[0]
    t = np.arange(len(r["pb"]))
    ax.plot(t, r["pb"], color=common.BLUE, lw=1.6, label="beam search (B = 4)")
    ax.plot(t, r["ph"], color=common.ORANGE, lw=1.6, label="real text")
    ax.set_xlabel("character")
    ax.set_ylabel("probability")
    ax.set_ylim(0, 1.05)
    ax.set_xlim(0, len(t) - 1)
    ax.legend(loc="lower right", frameon=True, fontsize=8.5)
    panel_label(ax, "a", "lower left")
    ax = axes[1]
    ax.plot(t + 1, np.cumsum(np.log(r["pb"])), color=common.BLUE, lw=1.6, label="beam search")
    ax.plot(t + 1, np.cumsum(np.log(r["ph"])), color=common.ORANGE, lw=1.6, label="real text")
    ax.set_xlabel("number of characters")
    ax.set_ylabel("cumulative log-probability")
    ax.legend(fontsize=8.5)
    panel_label(ax, "b", "lower left")
    fig.tight_layout()
    savefig(fig, CH, "fig12-17", out_dir)


def fig_12_24(out_dir=None):
    """Raster-scan sampling of a 14 x 14 binary digit from a small autoregressive transformer."""
    m = pixel_model()
    W = as64(m["W"])
    S = sample_pixels(W, n_img=4, seed=5)
    stages = [1, 50, 98, 147, 196]
    fig, axes = plt.subplots(4, 5, figsize=(7.6, 6.2))
    for r in range(4):
        for c, k in enumerate(stages):
            img = np.full(196, 0.5)
            img[:k] = S[r, :k]
            ax = axes[r, c]
            ax.imshow(img.reshape(14, 14), cmap="gray", vmin=0, vmax=1, interpolation="nearest")
            ax.set_xticks([])
            ax.set_yticks([])
            if r == 0:
                ax.set_title("%d pixel%s" % (k, "" if k == 1 else "s"), fontsize=10)
    savefig(fig, CH, "fig12-24", out_dir)


def fig_12_25(out_dir=None):
    """A mel spectrogram, computed from scratch, of a synthetic whale-like song."""
    x, sr = whale_song()
    S, t, edges = mel_spectrogram(x, sr, n_fft=512, hop=96, n_mels=80, fmin=50.0, fmax=4000.0)
    fig, ax = plt.subplots(figsize=(9, 3.4))
    ax.imshow(S, origin="lower", aspect="auto", cmap="magma", extent=[t[0], t[-1], 0, S.shape[0]],
              vmin=S.max() - 70, vmax=S.max())
    ticks = [100, 250, 500, 1000, 2000, 4000]
    mel_lo, mel_hi = hz_to_mel(50.0), hz_to_mel(4000.0)
    ax.set_yticks([(hz_to_mel(f) - mel_lo) / (mel_hi - mel_lo) * S.shape[0] for f in ticks])
    ax.set_yticklabels([str(f) for f in ticks])
    ax.set_xlabel("time (s)")
    ax.set_ylabel("frequency (Hz, mel scale)")
    savefig(fig, CH, "fig12-25", out_dir)


# ================================================================ supplementary figures
def saturation_stats(Ds=(2, 4, 8, 16, 32, 64, 128, 256, 512), N=16, reps=400, seed=0):
    """Logit spread, largest attention weight and softmax-Jacobian size, with and without 1/sqrt(D)."""
    rng = np.random.default_rng(seed)
    out = {"D": np.array(Ds)}
    for key in ("sd_raw", "sd_scaled", "amax_raw", "amax_scaled", "jac_raw", "jac_scaled"):
        out[key] = []
    for D in Ds:
        q = rng.normal(size=(reps, D))
        K = rng.normal(size=(reps, N, D))
        s = np.einsum("rd,rnd->rn", q, K)
        for tag, z in (("raw", s), ("scaled", s / math.sqrt(D))):
            a = softmax_rows(z)
            out["sd_" + tag].append(z.std())
            out["amax_" + tag].append(a.max(1).mean())
            out["jac_" + tag].append(np.mean([np.abs(softmax_jacobian(ai)).sum(1).max() for ai in a]))
    return {k: np.array(v) for k, v in out.items()}


def fig_12_s1(out_dir=None):
    """Why scale by 1/sqrt(D): logit spread, saturation and the softmax Jacobian against D."""
    r = saturation_stats()
    fig, axes = plt.subplots(1, 3, figsize=(11, 3.3))
    ax = axes[0]
    ax.loglog(r["D"], r["sd_raw"], "o-", color=common.RED, label=r"$\mathbf{q}^{\rm T}\mathbf{k}$")
    ax.loglog(r["D"], r["sd_scaled"], "o-", color=common.BLUE, label=r"$\mathbf{q}^{\rm T}\mathbf{k}/\sqrt{D}$")
    ax.loglog(r["D"], np.sqrt(r["D"]), "--", color=common.GREY, lw=1, label=r"$\sqrt{D}$")
    ax.set_xlabel("D")
    ax.set_ylabel("standard deviation of the score")
    ax.legend(fontsize=8.5, loc="center left")
    panel_label(ax, "a", "upper left")
    ax = axes[1]
    ax.semilogx(r["D"], r["amax_raw"], "o-", color=common.RED, label="unscaled")
    ax.semilogx(r["D"], r["amax_scaled"], "o-", color=common.BLUE, label="scaled")
    ax.axhline(1 / 16, color=common.GREY, ls=":", lw=1)
    ax.set_xlabel("D")
    ax.set_ylabel("mean of the largest weight")
    ax.set_ylim(0, 1.02)
    ax.legend(fontsize=8.5, loc="center right")
    panel_label(ax, "b", "lower left")
    ax = axes[2]
    ax.semilogx(r["D"], r["jac_raw"], "o-", color=common.RED, label="unscaled")
    ax.semilogx(r["D"], r["jac_scaled"], "o-", color=common.BLUE, label="scaled")
    ax.set_xlabel("D")
    ax.set_ylabel("size of the softmax Jacobian")
    ax.set_ylim(0, 1.0)
    ax.legend(fontsize=8.5)
    panel_label(ax, "c", "lower left")
    fig.tight_layout()
    savefig(fig, CH, "fig12-s1", out_dir)


def fig_12_s2(out_dir=None):
    """Relative positions: the Gram matrix of the encodings depends only on n - m; sine-only does not."""
    N, D = 96, 64
    R = sinusoidal_pe(N, D)
    G = R @ R.T
    fig, axes = plt.subplots(1, 2, figsize=(10, 3.9))
    ax = axes[0]
    im = ax.imshow(G, cmap="RdBu_r", vmin=-D / 2, vmax=D / 2, interpolation="nearest")
    ax.set_xlabel("position m")
    ax.set_ylabel("position n")
    fig.colorbar(im, ax=ax, fraction=0.046, label=r"$\mathbf{r}_n^{\rm T}\mathbf{r}_m$")
    panel_label(ax, "a")
    ax = axes[1]
    ks = np.arange(0, 40)
    i = np.arange(D)
    expo = np.where(i % 2 == 0, i, i - 1) / D
    om = 1 / 10000.0 ** expo
    for n0, ls in ((0, "-"), (20, "--"), (50, ":")):
        Rn = sinusoidal_pe(1, D, start=n0)[0]
        ax.plot(ks, [Rn @ sinusoidal_pe(1, D, start=n0 + k)[0] for k in ks], ls, color=common.BLUE, lw=1.6,
                label="sin and cos, n = %d" % n0)
        S = np.sin(n0 * om)
        ax.plot(ks, [S @ np.sin((n0 + k) * om) for k in ks], ls, color=common.RED, lw=1.2,
                label="sine only, n = %d" % n0)
    ax.set_xlabel("offset k")
    ax.set_ylabel(r"$\mathbf{r}_n^{\rm T}\mathbf{r}_{n+k}$")
    ax.legend(fontsize=7.5, ncol=2, loc="upper right")
    panel_label(ax, "b", "lower left")
    fig.tight_layout()
    savefig(fig, CH, "fig12-s2", out_dir)


def layer_timing():
    """Measured forward time of the attention core and of the per-token parts of one layer (numpy)."""
    def fit():
        rng = np.random.default_rng(0)
        D = 64
        Ns = np.array([32, 64, 128, 256, 512, 1024, 2048])
        ta, tp = [], []
        Wq, Wk, Wv, Wo = (rng.normal(size=(D, D)) / 8 for _ in range(4))
        W1, W2 = rng.normal(size=(D, 4 * D)) / 8, rng.normal(size=(4 * D, D)) / 16
        for N in Ns:
            X = rng.normal(size=(N, D))
            reps = max(3, int(2e6 / (N * N)))
            t0 = time.perf_counter()
            for _ in range(reps):
                Q, K, V = X @ Wq, X @ Wk, X @ Wv
                M = np.maximum(X @ W1, 0) @ W2 + X @ Wo
            tp.append((time.perf_counter() - t0) / reps)
            t0 = time.perf_counter()
            for _ in range(reps):
                A = softmax_rows(Q @ K.T / 8.0)
                Y = A @ V
            ta.append((time.perf_counter() - t0) / reps)
        return {"N": Ns, "t_att": np.array(ta), "t_tok": np.array(tp), "D": D}
    return _cached("ch12_layer_timing", fit)


def fig_12_s3(out_dir=None):
    """Cost of a transformer layer: the N^2 D attention term against the N D^2 per-token term."""
    fig, axes = plt.subplots(1, 2, figsize=(10, 3.6))
    ax = axes[0]
    Ns = np.logspace(1, 4.3, 60)
    for D, ls in ((64, "-"), (512, "--")):
        a, p = layer_flops(Ns, D)
        ax.loglog(Ns, a, ls, color=common.RED, label=r"$2N^2D$ (scores, $AV$), D = %d" % D)
        ax.loglog(Ns, p, ls, color=common.BLUE, label=r"$12ND^2$ (projections, MLP), D = %d" % D)
        ax.axvline(6 * D, color=common.GREY, ls=ls, lw=0.8)
    ax.set_xlabel("sequence length N")
    ax.set_ylabel("multiply-adds")
    ax.legend(fontsize=7.5)
    panel_label(ax, "a", "lower right")
    ax = axes[1]
    r = layer_timing()
    ax.loglog(r["N"], 1e3 * r["t_att"], "o-", color=common.RED, label="attention core")
    ax.loglog(r["N"], 1e3 * r["t_tok"], "o-", color=common.BLUE, label="projections + MLP")
    ax.loglog(r["N"], 1e3 * r["t_att"][-1] * (r["N"] / r["N"][-1]) ** 2, ":", color=common.RED, lw=1, label=r"slope 2")
    ax.loglog(r["N"], 1e3 * r["t_tok"][-1] * (r["N"] / r["N"][-1]), ":", color=common.BLUE, lw=1, label="slope 1")
    ax.set_xlabel("sequence length N")
    ax.set_ylabel("time (ms), D = 64, one CPU thread")
    ax.legend(fontsize=8)
    panel_label(ax, "b", "lower right")
    fig.tight_layout()
    savefig(fig, CH, "fig12-s3", out_dir)


def ngram_baselines():
    """Validation cross-entropy (nats per character) of add-alpha n-gram models, n = 1..6, and of the
    character transformer (computed with the numpy forward pass on the whole validation text)."""
    def fit():
        text = corpus()
        tr, va = corpus_split(text)
        vocab = sorted(set(text))
        out = {"n": [], "alpha": [], "ce": []}
        for n in range(1, 7):
            a, lp = best_alpha_ngram(tr, va, n, vocab)
            out["n"].append(n)
            out["alpha"].append(a)
            out["ce"].append(-lp)
        W, chars = _char_model_64()
        stoi = {c: i for i, c in enumerate(chars)}
        out["gpt"] = gpt_nll(W, [stoi[c] for c in va], GPT_CFG)
        tr_ids = [stoi[c] for c in tr[:len(va)]]
        out["gpt_train"] = gpt_nll(W, tr_ids, GPT_CFG)
        return {k: (np.array(v) if isinstance(v, list) else v) for k, v in out.items()}
    return _cached("ch12_ngram", fit)


def fig_12_s4(out_dir=None):
    """Training the character transformer: cross-entropy and perplexity against n-gram baselines."""
    m = char_model()
    b = ngram_baselines()
    h = m["hist"]
    fig, axes = plt.subplots(1, 2, figsize=(10.5, 3.7))
    ax = axes[0]
    ax.plot(h["step"], h["train"], color=common.BLUE, label="training windows")
    ax.plot(h["step"], h["val"], color=common.RED, label="held-out windows")
    cols = [common.GREY, common.GREEN, common.PURPLE, common.ORANGE, common.CYAN, common.MAGENTA]
    for n, ce, c in zip(b["n"], b["ce"], cols):
        if n in (1, 2, 3, 5):
            ax.axhline(ce, color=c, ls="--", lw=1, label="%d-gram" % n)
    ax.set_xlabel("Adam step")
    ax.set_ylabel("cross-entropy (nats per character)")
    ax.set_ylim(1.2, 3.2)
    ax.legend(fontsize=8, ncol=2)
    panel_label(ax, "a", "lower left")
    ax = axes[1]
    ax.plot(b["n"], np.exp(b["ce"]), "o-", color=common.GREY, label="n-gram, held-out text")
    ax.axhline(math.exp(b["gpt"]), color=common.RED, lw=1.6, label="transformer, held-out text")
    ax.axhline(math.exp(b["gpt_train"]), color=common.BLUE, lw=1.2, ls="--", label="transformer, training text")
    ax.set_xlabel("n (context of n - 1 characters)")
    ax.set_ylabel("perplexity (per character)")
    ax.set_yscale("log")
    ax.set_yticks([4, 6, 10, 20])
    ax.set_yticklabels(["4", "6", "10", "20"])
    ax.legend(fontsize=8)
    panel_label(ax, "b", "lower left")
    fig.tight_layout()
    savefig(fig, CH, "fig12-s4", out_dir)


def fig_12_s5(out_dir=None):
    """Byte-pair encoding of the training text: vocabulary size against tokens per character."""
    r = corpus_bpe()
    fig, axes = plt.subplots(1, 2, figsize=(10, 3.5))
    ax = axes[0]
    ax.plot(np.arange(len(r["sizes"])), r["lengths"] / r["chars"], color=common.BLUE)
    ax.set_xlabel("number of merges")
    ax.set_ylabel("tokens per character")
    ax.set_ylim(0, 1.05)
    panel_label(ax, "a", "lower left")
    ax = axes[1]
    ax.axis("off")
    ms = ["%s+%s" % (a, b) for a, b in r["merges"][:40]]
    ax.text(0.0, 1.0, "first 40 merges, in order:", fontsize=9.5, va="top", color=common.GREY)
    for j in range(4):
        ax.text(0.0 + 0.25 * j, 0.88, "\n".join(ms[10 * j:10 * j + 10]), family="monospace", fontsize=9, va="top")
    savefig(fig, CH, "fig12-s5", out_dir)


def fig_12_s6(out_dir=None):
    """Temperature, top-k and nucleus sampling on the distribution of the word after 'the'."""
    text = corpus()
    words, p, tot = next_word_distribution(text, "the")
    logits = np.log(p)
    K = 25
    fig, axes = plt.subplots(1, 3, figsize=(12, 3.7), gridspec_kw={"width_ratios": [1.5, 1, 1]})
    ax = axes[0]
    x = np.arange(K)
    for T, c, off in ((0.5, common.BLUE, -0.27), (1.0, common.GREY, 0.0), (2.0, common.RED, 0.27)):
        ax.bar(x + off, temperature_probs(logits, T)[:K], width=0.27, color=c, label="T = %g" % T)
    ax.set_xticks(x)
    ax.set_xticklabels(words[:K], rotation=70, fontsize=7.5)
    ax.set_ylabel("probability of the next word")
    ax.legend(fontsize=8.5)
    panel_label(ax, "a", "upper right")
    ax = axes[1]
    Ts = np.linspace(0.05, 3, 120)
    H = [entropy(temperature_probs(logits, T)) for T in Ts]
    ax.plot(Ts, H, color=common.BLUE)
    ax.axhline(math.log(len(p)), color=common.GREY, ls=":", lw=1)
    ax.text(0.1, math.log(len(p)) - 0.35, "ln K, K = %d words" % len(p), fontsize=8, color=common.GREY)
    ax.set_xlabel("temperature T")
    ax.set_ylabel("entropy (nats)")
    panel_label(ax, "b", "lower right")
    ax = axes[2]
    ks = np.arange(1, len(p) + 1)
    mass = np.cumsum(np.sort(p)[::-1])
    ax.semilogx(ks, mass, color=common.BLUE, label="top-k: mass kept")
    for pp in (0.5, 0.9):
        kk = int(np.searchsorted(mass, pp - 1e-12) + 1)
        ax.plot([kk, kk], [0, pp], ":", color=common.RED, lw=1)
        ax.plot([1, kk], [pp, pp], ":", color=common.RED, lw=1)
        ax.text(kk * 1.1, pp - 0.07, "p = %.1f: %d words" % (pp, kk), fontsize=8, color=common.RED)
    ax.set_xlabel("k")
    ax.set_ylabel("cumulative probability")
    ax.set_ylim(0, 1.02)
    panel_label(ax, "c", "lower right")
    fig.tight_layout()
    savefig(fig, CH, "fig12-s6", out_dir)


def fig_12_s7(out_dir=None):
    """A tiny vision transformer on MNIST: patch tokens, test accuracy, attention of the class token."""
    r = vit_results()
    fig = plt.figure(figsize=(11, 3.6))
    ax = fig.add_axes([0.02, 0.12, 0.2, 0.78])
    img = r["X"][0].reshape(28, 28)
    ax.imshow(img, cmap="gray_r")
    for k in range(1, 4):
        ax.axhline(7 * k - 0.5, color=common.RED, lw=1)
        ax.axvline(7 * k - 0.5, color=common.RED, lw=1)
    for k in range(16):
        ax.text(7 * (k % 4) + 0.3, 7 * (k // 4) + 1.6, str(k + 1), color=common.RED, fontsize=7)
    ax.set_xticks([])
    ax.set_yticks([])
    ax.set_title("16 patches of 7 x 7 pixels", fontsize=9.5)
    panel_label(ax, "a", "lower left")
    ax = fig.add_axes([0.3, 0.16, 0.25, 0.72])
    c = r["curve"]
    ax.plot(c[:, 0], 100 * c[:, 1], "o-", color=common.BLUE)
    ax.set_xlabel("Adam step (batches of 64)")
    ax.set_ylabel("test accuracy (%)")
    ax.set_title("%d parameters, 10 000 training digits" % r["params"], fontsize=9.5)
    panel_label(ax, "b", "lower right")
    for j in range(4):
        a2 = fig.add_axes([0.6 + 0.1 * j, 0.5, 0.09, 0.38])
        a2.imshow(r["X"][j].reshape(28, 28), cmap="gray_r")
        a2.set_xticks([])
        a2.set_yticks([])
        a3 = fig.add_axes([0.6 + 0.1 * j, 0.1, 0.09, 0.38])
        a3.imshow(r["att"][j, 0, 1:].reshape(4, 4), cmap="Blues", interpolation="nearest")
        a3.set_xticks([])
        a3.set_yticks([])
        if j == 0:
            a3.set_ylabel("<class> attends", fontsize=8)
    fig.text(0.79, 0.93, "last layer: attention of the <class> token to the 16 patches", ha="center", fontsize=9)
    savefig(fig, CH, "fig12-s7", out_dir)


def fig_12_s8(out_dir=None):
    """Exercise 12.6: self-attention and the position-wise MLP as N D x N D matrices."""
    rng = np.random.default_rng(6)
    N, D = 6, 4
    X = rng.normal(size=(N, D))
    Wq, Wk, Wv = (rng.normal(size=(D, D)) * sc for sc in (0.4, 0.4, 1.0))
    Ma = attention_as_matrix(X, Wq, Wk, Wv)
    _, A = self_attention(X, Wq, Wk, Wv, mask=causal_mask(N))
    Mc = np.kron(A, Wv.T)
    Wm = rng.normal(size=(D, D))
    Mm = np.kron(np.eye(N), Wm.T)
    fig, axes = plt.subplots(1, 3, figsize=(11, 3.9))
    for ax, Mx, title in zip(axes, (Ma, Mc, Mm), ("self-attention: block (n, m) = $a_{nm}\\mathbf{W}^{(v)\\mathrm{T}}$",
                                                 "masked self-attention", "position-wise layer: shared diagonal blocks")):
        v = np.abs(Mx).max()
        ax.imshow(Mx, cmap="RdBu_r", vmin=-v, vmax=v, interpolation="nearest")
        for k in range(1, N):
            ax.axhline(k * D - 0.5, color="k", lw=0.6)
            ax.axvline(k * D - 0.5, color="k", lw=0.6)
        ax.set_xticks([])
        ax.set_yticks([])
        ax.set_title(title, fontsize=9.5)
    savefig(fig, CH, "fig12-s8", out_dir)


FIGURES = {"12.2": fig_12_2, "12.10": fig_12_10, "12.12": fig_12_12, "12.16": fig_12_16, "12.17": fig_12_17,
           "12.24": fig_12_24, "12.25": fig_12_25, "12.S1": fig_12_s1, "12.S2": fig_12_s2, "12.S3": fig_12_s3,
           "12.S4": fig_12_s4, "12.S5": fig_12_s5, "12.S6": fig_12_s6, "12.S7": fig_12_s7, "12.S8": fig_12_s8}


def export_all():
    """Write the JSON files used by the demonstrations."""
    print("wrote", export_char_model())
    print("wrote", export_sampling()[0])


if __name__ == "__main__":
    import sys
    if "--export" in sys.argv:
        export_all()
    else:
        run(FIGURES, CH)
        export_all()
