"""Bishop and Bishop (2024), Chapter 8: Backpropagation.

Reproduces the figures of Chapter 8 of C. M. Bishop and H. Bishop, Deep Learning: Foundations and
Concepts (Springer, 2024), pp. 233-252, written from scratch with numpy and matplotlib, and supplies the reference numbers of the
three browser demonstrations. Every algorithm is a short function meant to be read next to the
lecture notes (ch08-backpropagation.html):

* Section 8.1.2, backpropagation on a network of arbitrary feed-forward topology: FeedForwardNet
  stores a directed acyclic graph of units, runs forward propagation (8.5)-(8.6) and Algorithm 8.1
  (the delta recursion (8.13) and the products (8.10)), and counts the multiply-adds of each pass.
* Exercise 8.2, the layered (matrix) form: mlp_forward / mlp_backward for a batch, with linear,
  logistic-sigmoid and softmax outputs and their matching errors.
* Section 8.1.3 and Exercise 8.4: the two-layer tanh network with optional skip-layer weights
  (tl_forward, tl_grad), the worked numerical example (worked_example).
* Section 8.1.4: forward and central differences (fd_gradient, fd_error_curve; Figure 8.2).
* Section 8.1.5 and Exercise 8.5: the Jacobian by backward and by forward propagation
  (mlp_jacobian_backward, mlp_jacobian_forward).
* Section 8.1.6 and Exercises 8.6-8.12: the exact Hessian of a two-layer network with skip layers
  (tl_hessian), the outer-product (Gauss-Newton) approximation for sum-of-squares, logistic and
  softmax outputs (tl_outer), the R-operator Hessian-vector product (tl_rop) and the sequential
  inverse Hessian (sequential_inverse).
* Section 8.2: automatic differentiation from scratch. Dual is forward mode (dual numbers), Var is
  reverse mode (a tape with adjoints); both work on the same generic elementary functions (exp, sin,
  tanh, softplus, ...), and they nest, so forward-over-reverse gives Hessian-vector products (hvp).
  trace_f / trace_f2 are the evaluation traces (8.50)-(8.56) and Figure 8.5; Expr is a tiny
  computer-algebra system whose derivative rules show expression swell (Exercises 8.13, 8.14).
* JSRandom: the seeded generator DK.rng of the browser demos. demo_backprop (backprop-steps-demo.html),
  graph_eval (autodiff-modes-demo.html) and HessDemo (hessian-vector-demo.html) are plain-float
  versions of the pages' code, so the pages reproduce them number for number.

Figures reproduced: 8.2 (computed from a small network), 8.4 and 8.5 (the evaluation-trace graphs,
drawn from the trace with every primal, tangent and adjoint value at x = (1, 2)).
Figures skipped: 8.1 (a schematic of units i, j, k and the direction of the delta messages; no
data or computation) and 8.3 (a schematic of a modular architecture with modules u, v, w).

Supplementary figures (our own, numbered 8.S1-8.S4; they illustrate the gaps filled in the notes):
8.S1 the cost of a gradient (backprop against central differences) and of a full Jacobian (forward
against reverse mode), counted exactly; 8.S2 the exact Hessian against its outer-product
approximation while a network trains, with and without noise and with too few hidden units;
8.S3 expression swell of symbolic differentiation against the size of the evaluation trace;
8.S4 the sequential inverse Hessian and its sensitivity to the initial alpha.

Run `python3 ch08_backpropagation.py --list`, `python3 ch08_backpropagation.py` (all figures, about
15 seconds on one CPU thread) or `python3 ch08_backpropagation.py --fig 8.2 8.S2`.
Files go to ../img/ch08/.
"""
import math
import os

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

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

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

HERE = os.path.dirname(os.path.abspath(__file__))
CACHE_DIR = os.path.join(HERE, "cache")
CH = 8
M32 = 0xFFFFFFFF
U_ROUND = np.finfo(float).eps / 2      # unit round-off of double precision, 1.1e-16


# =========================================================================== 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)


# =========================================================================== activations
def act(name, a):
    """h(a) for numpy arrays."""
    if name == "tanh":
        return np.tanh(a)
    if name == "logistic":
        return common.sigmoid(a)
    if name == "relu":
        return np.maximum(a, 0.0)
    if name == "softplus":
        return np.logaddexp(0.0, a)
    return np.asarray(a, dtype=float)


def act_d(name, a):
    """h'(a)."""
    if name == "tanh":
        return 1.0 - np.tanh(a) ** 2                      # (8.16)
    if name == "logistic":
        s = common.sigmoid(a)
        return s * (1.0 - s)
    if name == "relu":
        return (np.asarray(a) > 0).astype(float)
    if name == "softplus":
        return common.sigmoid(a)
    return np.ones_like(np.asarray(a, dtype=float))


def act_dd(name, a):
    """h''(a)."""
    if name == "tanh":
        t = np.tanh(a)
        return -2.0 * t * (1.0 - t ** 2)
    if name in ("logistic", "softplus"):
        s = common.sigmoid(a)
        return s * (1.0 - s) * (1.0 - 2.0 * s) if name == "logistic" else s * (1.0 - s)
    return np.zeros_like(np.asarray(a, dtype=float))


def output_y(out, a):
    """Output activation of the canonical pairs: linear (sum-of-squares), logistic (binary CE), softmax (CE)."""
    a = np.asarray(a, dtype=float)
    if out == "linear":
        return a.copy()
    if out == "sigmoid":
        return common.sigmoid(a)
    m = a.max(axis=-1, keepdims=True)
    e = np.exp(a - m)
    return e / e.sum(axis=-1, keepdims=True)


def output_error(out, y, t):
    """E_n summed over the rows of y (sum-of-squares (8.3) or the cross-entropies)."""
    y, t = np.asarray(y, float), np.asarray(t, float)
    if out == "linear":
        return 0.5 * np.sum((y - t) ** 2)
    if out == "sigmoid":
        return -np.sum(t * np.log(y) + (1 - t) * np.log(1 - y))
    return -np.sum(t * np.log(y))


def output_M(out, y):
    """M = d^2 E_n / da da^T at the output pre-activations for the canonical pairs (Exercise 8.6)."""
    y = np.asarray(y, float)
    if out == "linear":
        return np.eye(len(y))
    if out == "sigmoid":
        return np.diag(y * (1 - y))
    return np.diag(y) - np.outer(y, y)                    # from (8.34)


# =========================================================================== 8.1.2 general topology
class FeedForwardNet:
    """A feed-forward network of arbitrary (acyclic) topology, Section 8.1.2.

    Unit indices: 0..D-1 are the inputs, D is the bias unit (z = 1), D+1, D+2, ... are hidden and output
    units in a topological order (every connection goes from a lower to a higher index). edges is a list
    of (j, i): a weight w_ji carrying z_i into a_j. outputs lists the output units (sinks), whose output
    activation is the canonical one for `out`. acts[j] names the activation of hidden unit j.
    """

    def __init__(self, D, n_units, edges, outputs, acts, out="linear"):
        self.D, self.U = D, n_units
        self.edges = list(edges)
        self.outputs = list(outputs)
        self.acts = dict(acts)
        self.out = out
        self.n = D + 1 + n_units
        self.into = {j: [] for j in range(D + 1, self.n)}       # j -> [(edge index, i)]
        self.out_of = {i: [] for i in range(self.n)}            # i -> [(edge index, k)]
        for e, (j, i) in enumerate(self.edges):
            assert i < j, "connections must go forwards"
            self.into[j].append((e, i))
            self.out_of[i].append((e, j))
        self.W = len(self.edges)
        self.ops = {"forward": 0, "backward": 0, "grad": 0}

    def forward(self, w, x):
        """Forward propagation (8.5)-(8.6); returns pre-activations a and activations z (dicts over units)."""
        a, z = {}, {}
        for i in range(self.D):
            z[i] = float(x[i])
        z[self.D] = 1.0
        for j in range(self.D + 1, self.n):
            s = 0.0
            for e, i in self.into[j]:
                s += w[e] * z[i]
                self.ops["forward"] += 1
            a[j] = s
            if j in self.outputs:
                z[j] = None                                    # filled below (softmax needs all outputs)
            else:
                z[j] = float(act(self.acts[j], s))
        y = output_y(self.out, np.array([a[k] for k in self.outputs]))
        for k, yk in zip(self.outputs, y):
            z[k] = float(yk)
        return a, z

    def error(self, w, x, t):
        a, z = self.forward(w, x)
        return float(output_error(self.out, np.array([z[k] for k in self.outputs]), t))

    def backprop(self, w, x, t):
        """Algorithm 8.1: returns (dE_n/dw as an array over edges, the deltas, a, z)."""
        a, z = self.forward(w, x)
        delta = {}
        for k, tk in zip(self.outputs, t):
            delta[k] = z[k] - tk                                # (8.11), canonical link
        for j in range(self.n - 1, self.D, -1):                 # reverse topological order
            if j in self.outputs:
                continue
            s = 0.0
            for e, k in self.out_of[j]:
                s += w[e] * delta[k]                            # sum over the FIRST index of w_kj
                self.ops["backward"] += 1
            delta[j] = float(act_d(self.acts[j], a[j])) * s     # (8.13)
        g = np.zeros(self.W)
        for e, (j, i) in enumerate(self.edges):
            g[e] = delta[j] * z[i]                              # (8.10)
            self.ops["grad"] += 1
        return g, delta, a, z


def random_dag(D, H, K, p_skip=0.4, rng=None, acts=("tanh", "logistic", "softplus"), out="linear"):
    """A random feed-forward topology: H hidden units, each fed by the bias, some inputs and some earlier
    hidden units (skip connections across 'layers' included), and K outputs fed by random subsets."""
    rng = rng or np.random.default_rng(0)
    edges, hid = [], list(range(D + 1, D + 1 + H))
    for n, j in enumerate(hid):
        srcs = [D] + [i for i in range(D) if rng.random() < 0.7] + [h for h in hid[:n] if rng.random() < p_skip]
        if len(srcs) == 1:
            srcs.append(int(rng.integers(D)))
        edges += [(j, i) for i in srcs]
    outs = list(range(D + 1 + H, D + 1 + H + K))
    for k in outs:
        srcs = [D] + [h for h in hid if rng.random() < 0.8] + [i for i in range(D) if rng.random() < 0.3]
        edges += [(k, i) for i in sorted(set(srcs))]
    a = {j: acts[int(rng.integers(len(acts)))] for j in hid}
    return FeedForwardNet(D, H + K, edges, outs, a, out=out)


def layered_net(sizes, act_name="tanh", out="linear"):
    """A fully connected layered network as a FeedForwardNet (for counting operations)."""
    D = sizes[0]
    edges, prev, nxt, acts = [], list(range(D)), D + 1, {}
    for li, m in enumerate(sizes[1:]):
        units = list(range(nxt, nxt + m))
        for j in units:
            edges += [(j, D)] + [(j, i) for i in prev]
            if li < len(sizes) - 2:
                acts[j] = act_name
        prev, nxt = units, nxt + m
    return FeedForwardNet(D, nxt - D - 1, edges, prev, acts, out=out)


# =========================================================================== Exercise 8.2: matrix form
def mlp_init(sizes, rng, scale=1.0):
    """[(W1, b1), ..., (WL, bL)] with W_l of shape (M_l, M_{l-1}) and N(0, scale^2 / M_{l-1}) entries."""
    return [(rng.normal(size=(m, n)) * scale / math.sqrt(n), rng.normal(size=m) * 0.1)
            for n, m in zip(sizes[:-1], sizes[1:])]


def mlp_forward(params, X, hidden="tanh"):
    """Forward pass for a batch X (N x D): z^(l) = h(W^(l) z^(l-1) + b^(l)), (6.19), as rows."""
    Zs, As = [np.atleast_2d(X)], []
    for l, (W, b) in enumerate(params):
        A = Zs[-1] @ W.T + b
        As.append(A)
        Zs.append(act(hidden, A) if l < len(params) - 1 else A)
    return As, Zs


def mlp_backward(params, As, Zs, Delta, hidden="tanh"):
    """Matrix backpropagation (Exercise 8.2): Delta^(l-1) = h'(A^(l-1)) * (Delta^(l) W^(l)), row form.

    Delta holds dE/da at the output layer (N x K). Returns [(dW1, db1), ...] summed over the batch (8.14).
    """
    grads = [None] * len(params)
    for l in range(len(params) - 1, -1, -1):
        W, _ = params[l]
        grads[l] = (Delta.T @ Zs[l], Delta.sum(0))
        if l > 0:
            Delta = act_d(hidden, As[l - 1]) * (Delta @ W)
    return grads


def mlp_loss_grad(params, X, T, hidden="tanh", out="linear"):
    """E (summed over the batch) and its gradient by backpropagation."""
    As, Zs = mlp_forward(params, X, hidden)
    Y = output_y(out, As[-1])
    E = output_error(out, Y, T)
    return E, mlp_backward(params, As, Zs, Y - T, hidden)


def flat(grads):
    return np.concatenate([np.concatenate([g[0].ravel(), g[1].ravel()]) for g in grads])


def unflat(vec, like):
    out, k = [], 0
    for W, b in like:
        nW, nb = W.size, b.size
        out.append((vec[k:k + nW].reshape(W.shape), vec[k + nW:k + nW + nb].copy()))
        k += nW + nb
    return out


def dy_da(out, y):
    """dy_k/da_l at the output layer: (8.31), (8.33) and (8.34)."""
    if out == "linear":
        return np.eye(len(y))
    if out == "sigmoid":
        return np.diag(y * (1 - y))
    return np.diag(y) - np.outer(y, y)


def mlp_jacobian_backward(params, x, hidden="tanh", out="linear"):
    """J = dy/dx (K x D) by backpropagation (8.29)-(8.34): all K rows at once (one pass per output row)."""
    As, Zs = mlp_forward(params, x[None, :], hidden)
    y = output_y(out, As[-1][0])
    S = dy_da(out, y)                                          # dy_k / da^(L)
    for l in range(len(params) - 1, 0, -1):
        S = (S @ params[l][0]) * act_d(hidden, As[l - 1][0])  # (8.30)
    return S @ params[0][0]                                    # (8.29)


def mlp_jacobian_forward(params, x, hidden="tanh", out="linear"):
    """J = dy/dx by forward propagation of da/dx (Exercise 8.5): all D columns at once."""
    As, Zs = mlp_forward(params, x[None, :], hidden)
    T = params[0][0].copy()                                    # da^(1)/dx = W^(1)
    for l in range(1, len(params)):
        T = params[l][0] @ (act_d(hidden, As[l - 1][0])[:, None] * T)
    y = output_y(out, As[-1][0])
    return dy_da(out, y) @ T


def mlp_jvp_x(params, x, r, hidden="tanh"):
    """One forward-mode pass: J r for a linear-output network (tangent propagation from the inputs)."""
    z, zd = x, r
    for l, (W, b) in enumerate(params):
        a, ad = W @ z + b, W @ zd
        if l < len(params) - 1:
            z, zd = act(hidden, a), act_d(hidden, a) * ad
        else:
            z, zd = a, ad
    return z, zd


def mlp_vjp_x(params, x, u, hidden="tanh"):
    """One reverse-mode pass: u^T J for a linear-output network (backpropagation of u to the inputs)."""
    As, Zs = mlp_forward(params, x[None, :], hidden)
    d = u.copy()
    for l in range(len(params) - 1, -1, -1):
        d = d @ params[l][0]
        if l > 0:
            d = d * act_d(hidden, As[l - 1][0])
    return d


# =========================================================================== 8.1.3 / 8.1.6: two-layer network
class TwoLayer:
    """The two-layer network of Section 8.1.3: a_j = sum_i W1[j,i] x_i (x_0 = 1), z_j = h(a_j),
    a_k = sum_j W2[k,j] z_j (z_0 = 1) + sum_i U[k,i] x_i (skip-layer weights, Exercise 8.4; optional),
    y = g(a_k) with g linear, logistic or softmax. Parameter vector order: W1, W2, U (row-major)."""

    def __init__(self, D, M, K, hidden="tanh", out="linear", skip=False):
        self.D, self.M, self.K, self.hidden, self.out, self.skip = D, M, K, hidden, out, skip
        self.n1, self.n2 = M * (D + 1), K * (M + 1)
        self.nu = K * D if skip else 0
        self.W = self.n1 + self.n2 + self.nu

    def unpack(self, w):
        W1 = w[:self.n1].reshape(self.M, self.D + 1)
        W2 = w[self.n1:self.n1 + self.n2].reshape(self.K, self.M + 1)
        U = w[self.n1 + self.n2:].reshape(self.K, self.D) if self.skip else np.zeros((self.K, self.D))
        return W1, W2, U

    def init(self, rng, s1=1.0, s2=0.5):
        w = np.concatenate([rng.normal(size=self.n1) * s1, rng.normal(size=self.n2) * s2, rng.normal(size=self.nu) * s2])
        return w

    def forward(self, w, x):
        W1, W2, U = self.unpack(w)
        xt = np.concatenate([[1.0], x])
        a = W1 @ xt                                             # (8.18)
        z = np.concatenate([[1.0], act(self.hidden, a)])        # (8.19)
        ak = W2 @ z + U @ x                                     # (8.20) plus skip layer
        return xt, a, z, ak, output_y(self.out, ak)

    def error(self, w, X, T):
        return sum(float(output_error(self.out, self.forward(w, x)[4], t)) for x, t in zip(X, T))

    def grad_point(self, w, x, t):
        """Backpropagation (8.21)-(8.23) for one point, with the skip-layer derivatives (Exercise 8.4)."""
        W1, W2, U = self.unpack(w)
        xt, a, z, ak, y = self.forward(w, x)
        dk = y - t                                              # (8.21)
        dj = act_d(self.hidden, a) * (W2[:, 1:].T @ dk)         # (8.22)
        g = [np.outer(dj, xt).ravel(), np.outer(dk, z).ravel()]  # (8.23)
        if self.skip:
            g.append(np.outer(dk, x).ravel())                   # dE/du_ki = delta_k x_i
        return np.concatenate(g)

    def grad(self, w, X, T):
        return sum(self.grad_point(w, x, t) for x, t in zip(X, T))

    def dak_dw(self, w, x):
        """B (K x W): the derivatives of the output pre-activations a_k with respect to every weight."""
        W1, W2, U = self.unpack(w)
        xt, a, z, ak, y = self.forward(w, x)
        hp = act_d(self.hidden, a)
        B = np.zeros((self.K, self.W))
        for k in range(self.K):
            B[k, :self.n1] = np.outer(W2[k, 1:] * hp, xt).ravel()
            row = np.zeros((self.K, self.M + 1))
            row[k] = z
            B[k, self.n1:self.n1 + self.n2] = row.ravel()
            if self.skip:
                rowu = np.zeros((self.K, self.D))
                rowu[k] = x
                B[k, self.n1 + self.n2:] = rowu.ravel()
        return B

    def hessian_point(self, w, x, t):
        """Exact Hessian of E_n by the formulas of Exercises 8.6 and 8.7 (in terms of delta_k and M_kk')."""
        D, M, K = self.D, self.M, self.K
        W1, W2, U = self.unpack(w)
        xt, a, z, ak, y = self.forward(w, x)
        dk = y - t
        Mk = output_M(self.out, y)
        hp, hpp = act_d(self.hidden, a), act_dd(self.hidden, a)
        V = W2[:, 1:]                                           # w^(2)_kj for hidden j = 1..M
        H = np.zeros((self.W, self.W))
        i1 = lambda j, i: j * (D + 1) + i                       # noqa: E731
        i2 = lambda k, j: self.n1 + k * (M + 1) + j             # noqa: E731
        iu = lambda k, i: self.n1 + self.n2 + k * D + i         # noqa: E731
        # (i) both weights in the second layer: z_j z_j' M_kk'
        for k in range(K):
            for j in range(M + 1):
                for k2 in range(K):
                    for j2 in range(M + 1):
                        H[i2(k, j), i2(k2, j2)] = z[j] * z[j2] * Mk[k, k2]
        # (ii) both in the first layer
        s = V.T @ dk                                            # sum_k w_kj delta_k
        VMV = V.T @ Mk @ V                                      # sum_kk' w_kj M_kk' w_k'j'
        for j in range(M):
            for i in range(D + 1):
                for j2 in range(M):
                    for i2_ in range(D + 1):
                        val = xt[i] * xt[i2_] * hp[j] * hp[j2] * VMV[j, j2]
                        if j == j2:
                            val += xt[i] * xt[i2_] * hpp[j] * s[j]
                        H[i1(j, i), i1(j2, i2_)] = val
        # (iii) one in each layer: x_i h'(a_j) [delta_k I_jj' + z_j' sum_k' w_k'j M_kk']
        MV = Mk @ V                                             # (K x M): sum_k' M_kk' w_k'j
        for j in range(M):
            for i in range(D + 1):
                for k in range(K):
                    for j2 in range(M + 1):
                        val = xt[i] * hp[j] * z[j2] * MV[k, j]
                        if j2 == j + 1:                         # hidden unit j sits at z index j + 1
                            val += xt[i] * hp[j] * dk[k]
                        H[i1(j, i), i2(k, j2)] = H[i2(k, j2), i1(j, i)] = val
        if self.skip:                                           # Exercise 8.7
            for k in range(K):
                for i in range(D):
                    for k2 in range(K):
                        for i2_ in range(D):
                            H[iu(k, i), iu(k2, i2_)] = Mk[k, k2] * x[i] * x[i2_]
                        for j in range(M + 1):
                            H[iu(k, i), i2(k2, j)] = H[i2(k2, j), iu(k, i)] = Mk[k, k2] * z[j] * x[i]
                    for j in range(M):
                        for i2_ in range(D + 1):
                            H[iu(k, i), i1(j, i2_)] = H[i1(j, i2_), iu(k, i)] = x[i] * xt[i2_] * hp[j] * MV[k, j]
        return H

    def hessian(self, w, X, T):
        return sum(self.hessian_point(w, x, t) for x, t in zip(X, T))

    def outer(self, w, X):
        """Outer-product (Gauss-Newton) approximation: sum_n B_n^T M_n B_n.

        Linear outputs: sum_n sum_k grad y_nk grad y_nk^T ((8.40), Exercise 8.8); a logistic output gives
        (8.41) and softmax outputs Exercise 8.11."""
        G = np.zeros((self.W, self.W))
        for x in X:
            B = self.dak_dw(w, x)
            y = self.forward(w, x)[4]
            G += B.T @ output_M(self.out, y) @ B
        return G

    def rop_point(self, w, x, t, v):
        """Hessian-vector product H_n v by the R-operator (Pearlmutter 1994): one forward and one backward
        pass of R{.} = d/dr (.)(w + r v) at r = 0, cost O(W)."""
        W1, W2, U = self.unpack(w)
        V1, V2, VU = self.unpack(v)
        xt, a, z, ak, y = self.forward(w, x)
        hp, hpp = act_d(self.hidden, a), act_dd(self.hidden, a)
        Ra = V1 @ xt                                            # R{a_j}
        Rz = np.concatenate([[0.0], hp * Ra])                   # R{z_j}, R{z_0} = 0
        Rak = W2 @ Rz + V2 @ z + VU @ x                         # R{a_k}
        dk = y - t
        Rdk = output_M(self.out, y) @ Rak                       # R{delta_k} = M R{a_k}
        Vh, RVh = W2[:, 1:], V2[:, 1:]
        s = Vh.T @ dk
        Rdj = hpp * Ra * s + hp * (RVh.T @ dk) + hp * (Vh.T @ Rdk)
        out = [np.outer(Rdj, xt).ravel(), (np.outer(Rdk, z) + np.outer(dk, Rz)).ravel()]
        if self.skip:
            out.append(np.outer(Rdk, x).ravel())
        return np.concatenate(out)

    def hv(self, w, X, T, v):
        return sum(self.rop_point(w, x, t, v) for x, t in zip(X, T))


def worked_example():
    """The worked example of Section 8.1.3 used in the notes: D = 2, M = 2, K = 1, tanh hidden units."""
    net = TwoLayer(2, 2, 1, "tanh", "linear")
    W1 = np.array([[0.1, 0.5, -0.4], [-0.2, 0.3, 0.8]])        # rows j = 1, 2; columns: bias, x1, x2
    W2 = np.array([[0.05, 1.2, -0.7]])                          # columns: bias, z1, z2
    w = np.concatenate([W1.ravel(), W2.ravel()])
    x, t = np.array([1.0, 0.5]), np.array([0.3])
    xt, a, z, ak, y = net.forward(w, x)
    dk = y - t
    dj = (1 - z[1:] ** 2) * (W2[:, 1:].T @ dk)
    return dict(net=net, w=w, x=x, t=t, a=a, z=z, y=y, dk=dk, dj=dj, g=net.grad_point(w, x, t),
                E=float(output_error("linear", y, t)))


def sequential_inverse(Bs, alpha):
    """Exercise 8.12: one pass through the data, (M + v v^T)^-1 = M^-1 - (M^-1 v)(v^T M^-1)/(1 + v^T M^-1 v),
    starting from H_0 = alpha I. Bs is a list of vectors b_n (one per data point and output)."""
    W = len(Bs[0])
    Hinv = np.eye(W) / alpha
    for b in Bs:
        Hb = Hinv @ b
        Hinv -= np.outer(Hb, Hb) / (1.0 + b @ Hb)
    return Hinv


# =========================================================================== 8.1.4 numerical differentiation
def fd_gradient(f, w, eps=1e-6, central=True):
    """Finite-difference gradient (8.24) or (8.25): 1 or 2 evaluations of f per weight, O(W^2) in all."""
    w = np.array(w, dtype=float)
    g = np.zeros_like(w)
    f0 = None if central else f(w)
    for i in range(len(w)):
        wp = w.copy()
        wp[i] += eps
        if central:
            wm = w.copy()
            wm[i] -= eps
            g[i] = (f(wp) - f(wm)) / (2 * eps)
        else:
            g[i] = (f(wp) - f0) / eps
    return g


def fd_error_curve(f, w0, dfdw, eps_list):
    """|numerical - analytic| for forward and central differences of a scalar function f(w) at w0 (Figure 8.2)."""
    f0 = f(w0)
    fwd = np.array([abs((f(w0 + e) - f0) / e - dfdw) for e in eps_list])
    cen = np.array([abs((f(w0 + e) - f(w0 - e)) / (2 * e) - dfdw) for e in eps_list])
    return fwd, cen


# =========================================================================== 8.2 automatic differentiation
OPS = {"n": 0}


class Dual:
    """A dual number a + b eps with eps^2 = 0 (forward mode). b is the tangent, Section 8.2.1.

    Components may themselves be Duals or Vars, so the classes nest (higher derivatives, forward-over-
    reverse and reverse-over-forward)."""
    __slots__ = ("a", "b")

    def __init__(self, a, b=0.0):
        self.a, self.b = a, b

    @staticmethod
    def _c(o):
        return o if isinstance(o, Dual) else Dual(o, 0.0)

    def __add__(self, o):
        o = Dual._c(o)
        return Dual(self.a + o.a, self.b + o.b)
    __radd__ = __add__

    def __sub__(self, o):
        o = Dual._c(o)
        return Dual(self.a - o.a, self.b - o.b)

    def __rsub__(self, o):
        return Dual._c(o) - self

    def __neg__(self):
        return Dual(-self.a, -self.b)

    def __mul__(self, o):
        o = Dual._c(o)
        return Dual(self.a * o.a, self.a * o.b + self.b * o.a)
    __rmul__ = __mul__

    def __truediv__(self, o):
        o = Dual._c(o)
        return Dual(self.a / o.a, (self.b * o.a - self.a * o.b) / (o.a * o.a))

    def __rtruediv__(self, o):
        return Dual._c(o) / self

    def __repr__(self):
        return "Dual(%r, %r)" % (self.a, self.b)


class Var:
    """A node of a reverse-mode tape: a value, its parents with the local partial derivatives, and an
    adjoint filled in by backward(), Section 8.2.2."""
    __slots__ = ("val", "parents", "adj")

    def __init__(self, val, parents=()):
        self.val, self.parents, self.adj = val, tuple(parents), 0.0
        OPS["n"] += 1

    @staticmethod
    def _v(o):
        return o.val if isinstance(o, Var) else o

    def _bin(self, o, val, d_self, d_o):
        ps = [(self, d_self)]
        if isinstance(o, Var):
            ps.append((o, d_o))
        return Var(val, ps)

    def __add__(self, o):
        return self._bin(o, self.val + Var._v(o), 1.0, 1.0)
    __radd__ = __add__

    def __sub__(self, o):
        return self._bin(o, self.val - Var._v(o), 1.0, -1.0)

    def __rsub__(self, o):
        return Var(o - self.val, [(self, -1.0)])

    def __neg__(self):
        return Var(-self.val, [(self, -1.0)])

    def __mul__(self, o):
        ov = Var._v(o)
        return self._bin(o, self.val * ov, ov, self.val)
    __rmul__ = __mul__

    def __truediv__(self, o):
        ov = Var._v(o)
        return self._bin(o, self.val / ov, 1.0 / ov, -self.val / (ov * ov))

    def __rtruediv__(self, o):
        return Var(o / self.val, [(self, -o / (self.val * self.val))])


def _topo(out):
    order, seen, stack = [], set(), [(out, False)]
    while stack:
        node, done = stack.pop()
        if done:
            order.append(node)
            continue
        if id(node) in seen:
            continue
        seen.add(id(node))
        stack.append((node, True))
        for p, _ in node.parents:
            if id(p) not in seen:
                stack.append((p, False))
    return order


def backward(out, seed=1.0):
    """Reverse sweep (8.69): adjoint of each node = sum over its children of child adjoint x local partial."""
    order = _topo(out)
    for n in order:
        n.adj = 0.0
    out.adj = seed
    for n in reversed(order):
        for p, d in n.parents:
            p.adj = p.adj + n.adj * d
    return order


def _elem(x, fn, dfn):
    """Apply an elementary function generically: fn acts on floats and dfn, its derivative, is itself generic.

    A float gives fn(x); a Dual a + b eps gives fn(a) + dfn(a) b eps (forward mode); a Var records a tape
    node whose local partial derivative is dfn(val) (reverse mode). Nested types recurse."""
    if isinstance(x, Dual):
        return Dual(_elem(x.a, fn, dfn), dfn(x.a) * x.b)
    if isinstance(x, Var):
        return Var(_elem(x.val, fn, dfn), [(x, dfn(x.val))])
    return fn(x)


def exp(x):
    return _elem(x, math.exp, exp)


def sin(x):
    return _elem(x, math.sin, cos)


def cos(x):
    return _elem(x, math.cos, lambda u: -sin(u))


def log(x):
    return _elem(x, math.log, lambda u: 1.0 / u)


def sigmoid(x):
    return _elem(x, lambda u: 1.0 / (1.0 + math.exp(-u)), lambda u: sigmoid(u) * (1.0 - sigmoid(u)))


def softplus(x):
    """zeta(a) = ln(1 + exp(a)), (8.46); derivative is the logistic sigmoid."""
    return _elem(x, lambda u: math.log1p(math.exp(-abs(u))) + max(u, 0.0), sigmoid)


def tanh(x):
    return _elem(x, math.tanh, lambda u: 1.0 - tanh(u) * tanh(u))


def relu(x):
    return _elem(x, lambda u: u if u > 0 else 0.0, lambda u: 1.0 if Var._v(_primal(u)) > 0 else 0.0)


def _primal(u):
    while isinstance(u, (Dual, Var)):
        u = u.a if isinstance(u, Dual) else u.val
    return u


def trace_f(x1, x2):
    """The evaluation trace (8.50)-(8.56) of f = x1 x2 + exp(x1 x2) - sin(x2), (8.49); generic in the number type."""
    v = {1: x1, 2: x2}
    v[3] = v[1] * v[2]
    v[4] = sin(v[2])
    v[5] = exp(v[3])
    v[6] = v[3] - v[4]
    v[7] = v[5] + v[6]
    return v


def trace_f2(x1, x2):
    """Figure 8.5: the same trace plus v8 = v5 v6 = f2 = (x1 x2 - sin x2) exp(x1 x2), (8.65)."""
    v = trace_f(x1, x2)
    v[8] = v[5] * v[6]
    return v


def f_849(x1, x2):
    return x1 * x2 + math.exp(x1 * x2) - math.sin(x2)


def taylor3(f, x):
    """First, second and third derivatives of a scalar function by three nested dual numbers.

    With X = ((x + e1) + e2) + e3, the e3-coefficient of f(X) is f'((x + e1) + e2); its components are the
    first derivative, the second derivative (twice) and the third derivative."""
    r = f(Dual(Dual(Dual(x, 1.0), 1.0), 1.0)).b
    return r.a.a, r.a.b, r.b.b


def grad_forward(f, x):
    """Gradient of a scalar f by forward mode: one pass per input (D passes)."""
    g = []
    for i in range(len(x)):
        out = f(*[Dual(xi, 1.0 if j == i else 0.0) for j, xi in enumerate(x)])
        g.append(out.b)
    return np.array(g)


def grad_reverse(f, x):
    """Gradient of a scalar f by reverse mode: one forward sweep and one backward sweep."""
    xs = [Var(xi) for xi in x]
    out = f(*xs)
    backward(out)
    return np.array([v.adj for v in xs])


def jacobian_forward(f, x):
    """K x D Jacobian of a vector function f by D forward-mode passes (8.66): column i from x_dot = e_i."""
    cols = []
    for i in range(len(x)):
        out = f(*[Dual(xi, 1.0 if j == i else 0.0) for j, xi in enumerate(x)])
        cols.append([o.b for o in out])
    return np.array(cols).T


def jacobian_reverse(f, x):
    """K x D Jacobian by K reverse-mode passes: row k from the seed f_k_bar = 1."""
    rows = []
    for k in range(len(f(*x))):
        xs = [Var(xi) for xi in x]
        out = f(*xs)
        backward(out[k])
        rows.append([v.adj for v in xs])
    return np.array(rows)


def jvp(f, x, r):
    """J r in one forward-mode pass by seeding x_dot = r (Exercise 8.18)."""
    out = f(*[Dual(xi, ri) for xi, ri in zip(x, r)])
    return np.array([o.b for o in out])


def vjp(f, x, u):
    """u^T J in one reverse-mode pass by seeding the output adjoints with u."""
    xs = [Var(xi) for xi in x]
    out = f(*xs)
    s = 0.0
    for uk, ok in zip(u, out):
        s = ok * uk + s
    backward(s)
    return np.array([v.adj for v in xs])


def hvp_forward_over_reverse(f, x, v):
    """H v: reverse mode on inputs that carry a forward-mode tangent v (Var of Dual)."""
    xs = [Var(Dual(xi, vi)) for xi, vi in zip(x, v)]
    out = f(*xs)
    backward(out, Dual(1.0, 0.0))
    return np.array([n.adj.b for n in xs])


def hvp_reverse_over_forward(f, x, v):
    """H v as in Section 8.2.2: forward mode gives v^T grad f; reverse mode differentiates it (Dual of Var)."""
    xs = [Var(xi) for xi in x]
    out = f(*[Dual(xv, vi) for xv, vi in zip(xs, v)])        # out.b = v^T grad f, a Var
    backward(out.b)
    return np.array([n.adj for n in xs])


def hessian_by_hvp(f, x):
    """The full Hessian by W Hessian-vector products (O(W^2) in all)."""
    D = len(x)
    return np.array([hvp_forward_over_reverse(f, x, np.eye(D)[i]) for i in range(D)])


def softrelu_net(x, w1, b1, w2, b2):
    """y(x) = zeta(w2 zeta(w1 x + b1) + b2), (8.44)-(8.47)."""
    return softplus(w2 * softplus(w1 * x + b1) + b2)


def dy_dw1_848(x, w1, b1, w2, b2):
    """The symbolic derivative (8.48), typed in as printed in the book."""
    e1 = math.exp(w1 * x + b1)
    inner = b2 + w2 * math.log(1 + e1)
    return w2 * x * math.exp(w1 * x + b1 + inner) / ((1 + e1) * (1 + math.exp(inner)))


def logistic_map(x, n):
    """L_n(x) with L_1 = x and L_{m+1} = 4 L_m (1 - L_m) (Exercise 8.14); generic in the number type."""
    L = x
    for _ in range(n - 1):
        L = 4 * (L * (1 - L))
    return L


# =========================================================================== symbolic differentiation
class Expr:
    """A tiny computer-algebra expression (no simplification), to measure expression swell."""
    __slots__ = ("op", "args", "val", "_size")

    def __init__(self, op, args=(), val=None):
        self.op, self.args, self.val, self._size = op, tuple(args), val, None

    def size(self):
        """Number of nodes of the expression written out as a tree (no shared sub-expressions)."""
        if self._size is None:
            self._size = 1 + sum(a.size() for a in self.args)
        return self._size

    def dag_size(self):
        """Number of distinct nodes when equal sub-expressions are stored once (the evaluation trace)."""
        seen, stack = set(), [self]
        while stack:
            e = stack.pop()
            if id(e) in seen:
                continue
            seen.add(id(e))
            stack.extend(e.args)
        return len(seen)

    def ev(self, env):
        o, a = self.op, self.args
        if o == "c":
            return self.val
        if o == "x":
            return env[self.val]
        v = [e.ev(env) for e in a]
        return {"+": lambda: v[0] + v[1], "-": lambda: v[0] - v[1], "*": lambda: v[0] * v[1],
                "/": lambda: v[0] / v[1], "exp": lambda: math.exp(v[0]), "log": lambda: math.log(v[0]),
                "sp": lambda: math.log1p(math.exp(v[0])), "sig": lambda: 1 / (1 + math.exp(-v[0]))}[o]()

    def d(self, name, memo=None):
        """Derivative by the rules of calculus, applied mechanically. Subtrees are reused by reference, so
        size() counts the derivative as it would be printed. With a memo dict, the derivative of a shared
        sub-expression is built once and reused: that is forward-mode automatic differentiation on the trace."""
        if memo is not None:
            if id(self) in memo:
                return memo[id(self)]
            out = self._d(name, memo)
            memo[id(self)] = out
            return out
        return self._d(name, None)

    def _d(self, name, memo):
        o, a = self.op, self.args
        d_ = lambda e: e.d(name, memo)  # noqa: E731
        if o == "c":
            return C(0.0)
        if o == "x":
            return C(1.0 if self.val == name else 0.0)
        if o == "+":
            return d_(a[0]) + d_(a[1])
        if o == "-":
            return d_(a[0]) - d_(a[1])
        if o == "*":
            return d_(a[0]) * a[1] + a[0] * d_(a[1])
        if o == "/":
            return (d_(a[0]) * a[1] - a[0] * d_(a[1])) / (a[1] * a[1])
        if o == "exp":
            return Expr("exp", a) * d_(a[0])
        if o == "log":
            return d_(a[0]) / a[0]
        if o == "sp":
            return Expr("sig", a) * d_(a[0])
        if o == "sig":
            return Expr("sig", a) * (C(1.0) - Expr("sig", a)) * d_(a[0])
        raise ValueError(o)

    def __add__(self, o):
        return Expr("+", (self, _e(o)))

    def __radd__(self, o):
        return Expr("+", (_e(o), self))

    def __sub__(self, o):
        return Expr("-", (self, _e(o)))

    def __rsub__(self, o):
        return Expr("-", (_e(o), self))

    def __mul__(self, o):
        return Expr("*", (self, _e(o)))

    def __rmul__(self, o):
        return Expr("*", (_e(o), self))

    def __truediv__(self, o):
        return Expr("/", (self, _e(o)))


def C(v):
    return Expr("c", val=float(v))


def X(name):
    return Expr("x", val=name)


def _e(o):
    return o if isinstance(o, Expr) else C(o)


def swell_table(nmax=10):
    """Exercise 8.14: sizes of L_n and of its symbolic derivative (as trees), against the evaluation trace."""
    rows = []
    x = X("x")
    for n in range(1, nmax + 1):
        L = x
        for _ in range(n - 1):
            L = C(4.0) * (L * (C(1.0) - L))
        dL = L.d("x")
        dLm = L.d("x", {})
        rows.append(dict(n=n, f_tree=L.size(), df_tree=dL.size(), f_trace=L.dag_size(),
                         ad_trace=Expr("pair", (L, dLm)).dag_size() - 1, df_dag_naive=dL.dag_size()))
    return rows


# =========================================================================== demo references (plain floats, JS order)
def _h(name, a):
    if name == "tanh":
        return math.tanh(a)
    if name == "logistic":
        return 1.0 / (1.0 + math.exp(-a))
    return a if a > 0 else 0.0


def _hp(name, a, z):
    if name == "tanh":
        return 1.0 - z * z
    if name == "logistic":
        return z * (1.0 - z)
    return 1.0 if a > 0 else 0.0


DEMO_X = (0.6, -0.4)
DEMO_T = {"linear": (0.5, -0.3), "sigmoid": (1.0,), "softmax": (0.0, 1.0, 0.0)}
DEMO_K = {"linear": 2, "sigmoid": 1, "softmax": 3}


def demo_weights(seed, M, out, D=2, scale=0.9):
    """Weights of backprop-steps-demo.html: W1 (M x (D+1)), W2 (K x (M+1)), U (K x D), in that draw order."""
    K = DEMO_K[out]
    rng = JSRandom(seed)
    W1 = [[scale * rng.norm() for _ in range(D + 1)] for _ in range(M)]
    W2 = [[scale * rng.norm() for _ in range(M + 1)] for _ in range(K)]
    U = [[scale * rng.norm() for _ in range(D)] for _ in range(K)]
    return W1, W2, U


def demo_flat(W1, W2, U, skip):
    w = [v for r in W1 for v in r] + [v for r in W2 for v in r]
    if skip:
        w += [v for r in U for v in r]
    return w


def demo_unflat(w, M, K, D, skip):
    W1 = [w[j * (D + 1):(j + 1) * (D + 1)] for j in range(M)]
    o = M * (D + 1)
    W2 = [w[o + k * (M + 1):o + (k + 1) * (M + 1)] for k in range(K)]
    o += K * (M + 1)
    U = [w[o + k * D:o + (k + 1) * D] for k in range(K)] if skip else [[0.0] * D for _ in range(K)]
    return W1, W2, U


def demo_forward(w, M, hidden, out, skip, x=DEMO_X, t=None):
    """The forward pass and error of backprop-steps-demo.html (sums in the same order as the page)."""
    D, K = len(x), DEMO_K[out]
    t = DEMO_T[out] if t is None else t
    W1, W2, U = demo_unflat(w, M, K, D, skip)
    a = []
    for j in range(M):
        s = W1[j][0]
        for i in range(D):
            s += W1[j][i + 1] * x[i]
        a.append(s)
    z = [_h(hidden, v) for v in a]
    ak = []
    for k in range(K):
        s = W2[k][0]
        for j in range(M):
            s += W2[k][j + 1] * z[j]
        if skip:
            for i in range(D):
                s += U[k][i] * x[i]
        ak.append(s)
    if out == "linear":
        y = list(ak)
        E = 0.0
        for k in range(K):
            E += 0.5 * (y[k] - t[k]) * (y[k] - t[k])
    elif out == "sigmoid":
        y = [1.0 / (1.0 + math.exp(-ak[0]))]
        E = -(t[0] * math.log(y[0]) + (1 - t[0]) * math.log(1 - y[0]))
    else:
        m = max(ak)
        e = [math.exp(v - m) for v in ak]
        s = 0.0
        for v in e:
            s += v
        y = [v / s for v in e]
        E = 0.0
        for k in range(K):
            if t[k] > 0:
                E -= t[k] * math.log(y[k])
    return dict(a=a, z=z, ak=ak, y=y, E=E)


def demo_backprop(seed=1, M=3, hidden="tanh", out="linear", skip=False, kink=False, x=DEMO_X):
    """Everything backprop-steps-demo.html shows: forward values, deltas, gradient, and the weights used."""
    D, K = len(x), DEMO_K[out]
    t = DEMO_T[out]
    W1, W2, U = demo_weights(seed, M, out, D)
    if kink:                                                   # put hidden unit 1 just above its kink
        s = 0.0
        for i in range(D):
            s += W1[0][i + 1] * x[i]
        W1[0][0] = 1e-6 - s
    w = demo_flat(W1, W2, U, skip)
    f = demo_forward(w, M, hidden, out, skip, x, t)
    dk = [f["y"][k] - t[k] for k in range(K)]                  # (8.11)
    dj = []
    for j in range(M):
        s = 0.0
        for k in range(K):
            s += W2[k][j + 1] * dk[k]
        dj.append(_hp(hidden, f["a"][j], f["z"][j]) * s)       # (8.13)
    g = []
    for j in range(M):
        g += [dj[j]] + [dj[j] * x[i] for i in range(D)]        # (8.10): z_0 = 1 for the bias
    for k in range(K):
        g += [dk[k]] + [dk[k] * f["z"][j] for j in range(M)]
    if skip:
        for k in range(K):
            g += [dk[k] * x[i] for i in range(D)]
    f.update(w=w, dk=dk, dj=dj, g=g, t=t)
    return f


def demo_fd(res, idx, eps, M, hidden, out, skip, central=True):
    w = list(res["w"])
    wp = list(w)
    wp[idx] += eps
    Ep = demo_forward(wp, M, hidden, out, skip)["E"]
    if central:
        wm = list(w)
        wm[idx] -= eps
        return (Ep - demo_forward(wm, M, hidden, out, skip)["E"]) / (2 * eps)
    return (Ep - res["E"]) / eps


# =========================================================================== autodiff-modes-demo graphs
GRAPHS = {
    # name: (inputs, nodes [(id, op, parents)], outputs)
    "f": (["x1", "x2"], [("v3", "mul", ("v1", "v2")), ("v4", "sin", ("v2",)), ("v5", "exp", ("v3",)),
                         ("v6", "sub", ("v3", "v4")), ("v7", "add", ("v5", "v6"))], ["v7"]),
    "f12": (["x1", "x2"], [("v3", "mul", ("v1", "v2")), ("v4", "sin", ("v2",)), ("v5", "exp", ("v3",)),
                           ("v6", "sub", ("v3", "v4")), ("v7", "add", ("v5", "v6")), ("v8", "mul", ("v5", "v6"))],
            ["v7", "v8"]),
    "net": (["x", "w1", "b1", "w2", "b2"], [("v6", "mul", ("v2", "v1")), ("v7", "add", ("v6", "v3")),
                                            ("v8", "softplus", ("v7",)), ("v9", "mul", ("v4", "v8")),
                                            ("v10", "add", ("v9", "v5")), ("v11", "softplus", ("v10",))], ["v11"]),
    "logistic": (["x"], [("v2", "oneminus", ("v1",)), ("v3", "mul", ("v1", "v2")), ("v4", "times4", ("v3",)),
                         ("v5", "oneminus", ("v4",)), ("v6", "mul", ("v4", "v5")), ("v7", "times4", ("v6",)),
                         ("v8", "oneminus", ("v7",)), ("v9", "mul", ("v7", "v8")), ("v10", "times4", ("v9",))], ["v10"]),
}


def _sp(u):
    return math.log1p(math.exp(-abs(u))) + max(u, 0.0)


def _sg(u):
    return 1.0 / (1.0 + math.exp(-u))


def _node_val(op, p):
    return {"mul": lambda: p[0] * p[1], "add": lambda: p[0] + p[1], "sub": lambda: p[0] - p[1],
            "sin": lambda: math.sin(p[0]), "exp": lambda: math.exp(p[0]), "softplus": lambda: _sp(p[0]),
            "oneminus": lambda: 1.0 - p[0], "times4": lambda: 4.0 * p[0]}[op]()


def _node_partials(op, p, v):
    """Local partial derivatives d v / d parent, in parent order (as the page computes them)."""
    if op == "mul":
        return [p[1], p[0]]
    if op in ("add",):
        return [1.0, 1.0]
    if op == "sub":
        return [1.0, -1.0]
    if op == "sin":
        return [math.cos(p[0])]
    if op == "exp":
        return [v]
    if op == "softplus":
        return [_sg(p[0])]
    if op == "oneminus":
        return [-1.0]
    return [4.0]


def graph_eval(name, x, xdot=None, ubar=None):
    """Primal values, tangents (seed xdot) and adjoints (seed ubar on the outputs) on a demo graph."""
    ins, nodes, outs = GRAPHS[name]
    val, tan = {}, {}
    for i, n in enumerate(ins):
        val["v%d" % (i + 1)] = float(x[i])
        tan["v%d" % (i + 1)] = float(xdot[i]) if xdot is not None else 0.0
    part = {}
    for nid, op, ps in nodes:
        pv = [val[q] for q in ps]
        val[nid] = _node_val(op, pv)
        part[nid] = _node_partials(op, pv, val[nid])
        s = 0.0
        for q, d in zip(ps, part[nid]):
            s += tan[q] * d                                    # (8.57)
        tan[nid] = s
    adj = {k: 0.0 for k in val}
    if ubar is not None:
        for o, u in zip(outs, ubar):
            adj[o] = float(u)
        for nid, op, ps in reversed(nodes):                    # (8.69), children before parents
            for q, d in zip(ps, part[nid]):
                adj[q] += adj[nid] * d
    return dict(val=val, tan=tan, adj=adj, outs=outs, ins=["v%d" % (i + 1) for i in range(len(ins))])


# =========================================================================== hessian-vector-demo
class HessDemo:
    """The 1-M-1 tanh network of hessian-vector-demo.html, in plain floats and the page's order of sums.

    Data: x_n = -1 + 2n/(N-1), t_n = sin(pi x_n) + sigma * normal (JSRandom(data_seed)). Weights: per hidden
    unit j the bias and input weight, then the output bias and weights (JSRandom(seed)). Parameter order:
    [b1_1, w1_1, ..., b1_M, w1_M, b2, w2_1, ..., w2_M], W = 3M + 1. Training: full-batch Adam on
    E = 1/2 sum_n (y_n - t_n)^2."""

    def __init__(self, M=6, N=30, sigma=0.0, seed=1, data_seed=7):
        self.M, self.N, self.sigma = M, N, sigma
        r = JSRandom(data_seed)
        self.x = [-1.0 + 2.0 * n / (N - 1) for n in range(N)]
        self.t = [math.sin(math.pi * xn) + sigma * r.norm() for xn in self.x]
        g = JSRandom(seed)
        w = []
        for _ in range(M):
            w += [g.norm(), 2.0 * g.norm()]
        w.append(0.3 * g.norm())
        for _ in range(M):
            w.append(g.norm() / math.sqrt(M))
        self.w = w
        self.W = 3 * M + 1
        self.m = [0.0] * self.W
        self.v = [0.0] * self.W
        self.step = 0

    def _fw(self, w, x):
        M = self.M
        a = [w[2 * j] + w[2 * j + 1] * x for j in range(M)]
        z = [math.tanh(v) for v in a]
        y = w[2 * M]
        for j in range(M):
            y += w[2 * M + 1 + j] * z[j]
        return a, z, y

    def error(self, w=None):
        w = self.w if w is None else w
        E = 0.0
        for x, t in zip(self.x, self.t):
            y = self._fw(w, x)[2]
            E += 0.5 * (y - t) * (y - t)
        return E

    def grad_y(self, w, x):
        """grad of y(x, w) with respect to w (the vector b_n of the outer product)."""
        M = self.M
        a, z, y = self._fw(w, x)
        g = [0.0] * self.W
        for j in range(M):
            hp = 1.0 - z[j] * z[j]
            g[2 * j] = w[2 * M + 1 + j] * hp
            g[2 * j + 1] = w[2 * M + 1 + j] * hp * x
            g[2 * M + 1 + j] = z[j]
        g[2 * M] = 1.0
        return g, y

    def grad(self, w=None):
        w = self.w if w is None else w
        G = [0.0] * self.W
        for x, t in zip(self.x, self.t):
            g, y = self.grad_y(w, x)
            r = y - t
            for i in range(self.W):
                G[i] += r * g[i]
        return G

    def adam(self, steps, eta=0.01, b1=0.9, b2=0.999, delta=1e-8):
        for _ in range(steps):
            g = self.grad()
            self.step += 1
            c1, c2 = 1.0 - b1 ** self.step, 1.0 - b2 ** self.step
            for i in range(self.W):
                self.m[i] = b1 * self.m[i] + (1 - b1) * g[i]
                self.v[i] = b2 * self.v[i] + (1 - b2) * g[i] * g[i]
                self.w[i] -= eta * (self.m[i] / c1) / (math.sqrt(self.v[i] / c2) + delta)

    def hv(self, vec, w=None):
        """H v by the R-operator, summed over the data (one forward and one backward R-pass per point)."""
        w = self.w if w is None else w
        M = self.M
        out = [0.0] * self.W
        for x, t in zip(self.x, self.t):
            a, z, y = self._fw(w, x)
            Ra = [vec[2 * j] + vec[2 * j + 1] * x for j in range(M)]
            hp = [1.0 - z[j] * z[j] for j in range(M)]
            Rz = [hp[j] * Ra[j] for j in range(M)]
            Ry = vec[2 * M]
            for j in range(M):
                Ry += w[2 * M + 1 + j] * Rz[j] + vec[2 * M + 1 + j] * z[j]
            dk, Rdk = y - t, Ry                                  # linear output: R{delta} = R{y}
            for j in range(M):
                v2, Rv2 = w[2 * M + 1 + j], vec[2 * M + 1 + j]
                hpp = -2.0 * z[j] * hp[j]
                Rdj = hpp * Ra[j] * v2 * dk + hp[j] * Rv2 * dk + hp[j] * v2 * Rdk
                out[2 * j] += Rdj
                out[2 * j + 1] += Rdj * x
                out[2 * M + 1 + j] += Rdk * z[j] + dk * Rz[j]
            out[2 * M] += Rdk
        return out

    def hessian(self):
        H = []
        for i in range(self.W):
            e = [0.0] * self.W
            e[i] = 1.0
            H.append(self.hv(e))
        return np.array(H)

    def outer(self):
        G = np.zeros((self.W, self.W))
        for x in self.x:
            g = np.array(self.grad_y(self.w, x)[0])
            G += np.outer(g, g)
        return G

    def rel_err(self):
        H, G = self.hessian(), self.outer()
        return float(np.linalg.norm(H - G) / np.linalg.norm(H))


def hess_demo_run(M=6, N=30, sigma=0.0, steps=3000, every=50, seed=1, data_seed=7):
    """Relative Frobenius error ||H - G|| / ||H|| along a training run (Figure 8.S2, demo presets)."""
    d = HessDemo(M, N, sigma, seed, data_seed)
    ts, errs, Es = [0], [d.rel_err()], [d.error()]
    done = 0
    while done < steps:
        k = min(every, steps - done)
        d.adam(k)
        done += k
        ts.append(done)
        errs.append(d.rel_err())
        Es.append(d.error())
    return d, np.array(ts), np.array(errs), np.array(Es)


# =========================================================================== figures
def fig_8_2(out_dir=None):
    """Figure 8.2: error of forward and central differences against the step size epsilon."""
    res = demo_backprop(seed=1, M=3, hidden="tanh", out="linear")
    idx = 4                                                    # w^(1)_{2,1}: weight from x_1 into hidden unit 2
    w = list(res["w"])

    def f(val):
        ww = list(w)
        ww[idx] = val
        return demo_forward(ww, 3, "tanh", "linear", False)["E"]

    def fdual(val):                                            # the same error with generic arithmetic
        ww = list(w)
        ww[idx] = val
        return _demo_forward_generic(ww, 3)
    E1, E2, E3 = taylor3(fdual, w[idx])                        # exact derivatives by nested duals
    g = res["g"][idx]
    eps = np.logspace(-15, -1, 700)
    fwd, cen = fd_error_curve(f, w[idx], g, eps)
    fig, ax = plt.subplots(figsize=(5.6, 4.2))
    ax.loglog(eps, np.maximum(fwd, 1e-20), color=common.RED, lw=0.7, label="finite differences (8.24)")
    ax.loglog(eps, np.maximum(cen, 1e-20), color=common.BLUE, lw=0.7, label="central differences (8.25)")
    E0 = abs(res["E"])
    ax.loglog(eps, abs(E2) / 2 * eps, "--", color=common.RED, lw=1.0, alpha=0.7)
    ax.loglog(eps, abs(E3) / 6 * eps ** 2, "--", color=common.BLUE, lw=1.0, alpha=0.7)
    ax.loglog(eps, U_ROUND * E0 / eps, ":", color=common.GREY, lw=1.2)
    ax.text(3e-3, abs(E2) / 2 * 3e-3 * 3, r"$\frac{|E''|}{2}\epsilon$", color=common.RED, ha="right")
    ax.text(3e-3, abs(E3) / 6 * 9e-6 / 30, r"$\frac{|E'''|}{6}\epsilon^2$", color=common.BLUE, ha="left")
    ax.text(2e-3, U_ROUND * E0 / 2e-3 * 0.02, r"$u\,|E|/\epsilon$", color=common.GREY, ha="center", va="top")
    ax.set_xlabel(r"$\epsilon$")
    ax.set_ylabel("error")
    ax.set_ylim(1e-21, 1e-1)
    ax.set_xlim(1e-15, 1e-1)
    ax.legend(loc="lower left", frameon=False)
    return savefig(fig, CH, "fig8-2", out_dir)


def _demo_forward_generic(w, M, x=DEMO_X, t=DEMO_T["linear"]):
    """demo_forward for the linear-output tanh network, written with the generic elementary functions."""
    D, K = 2, 2
    W1, W2, U = demo_unflat(w, M, K, D, False)
    z = []
    for j in range(M):
        s = W1[j][0]
        for i in range(D):
            s = s + W1[j][i + 1] * x[i]
        z.append(tanh(s))
    E = 0.0
    for k in range(K):
        s = W2[k][0]
        for j in range(M):
            s = s + W2[k][j + 1] * z[j]
        E = E + 0.5 * (s - t[k]) * (s - t[k])
    return E


def _fmt(v):
    return ("%.3f" % v)


def _trace_figure(nodes, edges, outputs, title_vals, fname, out_dir, size):
    from matplotlib.patches import FancyBboxPatch, FancyArrowPatch
    fig, ax = plt.subplots(figsize=size)
    ax.set_xlim(-0.6, max(p[0] for p in nodes.values()) + 1.25)
    ys = [p[1] for p in nodes.values()]
    ax.set_ylim(min(ys) - 0.95, max(ys) + 0.62)
    ax.axis("off")
    for a, b in edges:
        (x0, y0), (x1, y1) = nodes[a][:2], nodes[b][:2]
        ax.add_patch(FancyArrowPatch((x0 + 0.33, y0), (x1 - 0.33, y1), arrowstyle="-|>", mutation_scale=11,
                                     color="black", lw=1.0, shrinkA=2, shrinkB=2))
    for k, (x, y, lab, expr) in nodes.items():
        ax.add_patch(FancyBboxPatch((x - 0.32, y - 0.2), 0.64, 0.4, boxstyle="round,pad=0.02,rounding_size=0.12",
                                    fc="#eaf1fb" if k.startswith("x") else "white", ec=common.BLUE, lw=1.2))
        ax.text(x, y + 0.04, lab, ha="center", va="center", fontsize=10.5)
        ax.text(x, y + 0.31, expr, ha="center", va="bottom", fontsize=8.5, color="#333333")
        if k in title_vals:
            for r, (txt, col) in enumerate(title_vals[k]):
                ax.text(x, y - 0.27 - 0.19 * r, txt, ha="center", va="top", fontsize=8.6, color=col)
    for name, (src, x, y) in outputs.items():
        ax.add_patch(FancyArrowPatch((nodes[src][0] + 0.33, nodes[src][1]), (x - 0.12, y), arrowstyle="-|>",
                                     mutation_scale=11, color="black", lw=1.0))
        ax.text(x, y, name, ha="left", va="center", fontsize=11)
    return savefig(fig, CH, fname, out_dir)


def _trace_values(two_outputs):
    x = (1.0, 2.0)
    fwd = graph_eval("f12" if two_outputs else "f", x, xdot=(1.0, 0.0))
    rev = graph_eval("f12" if two_outputs else "f", x, ubar=(1.0, 0.0) if two_outputs else (1.0,))
    lab = {}
    for k in fwd["val"]:
        lab[k] = [(r"$v=%s$" % _fmt(fwd["val"][k]), "#222222"), (r"$\dot v=%s$" % _fmt(fwd["tan"][k]), common.RED),
                  (r"$\bar v=%s$" % _fmt(rev["adj"][k]), common.BLUE)]
    return lab


def fig_8_4(out_dir=None):
    """Figure 8.4: the evaluation trace of (8.49), with primal, tangent and adjoint values at x = (1, 2)."""
    nodes = {"x1": (0, 1, r"$v_1$", r"$x_1$"), "x2": (0, -1, r"$v_2$", r"$x_2$"),
             "v3": (1.5, 1, r"$v_3$", r"$v_1v_2$"), "v4": (1.5, -1, r"$v_4$", r"$\sin v_2$"),
             "v5": (3.0, 1, r"$v_5$", r"$\exp v_3$"), "v6": (3.0, -1, r"$v_6$", r"$v_3-v_4$"),
             "v7": (4.5, 0, r"$v_7$", r"$v_5+v_6$")}
    edges = [("x1", "v3"), ("x2", "v3"), ("x2", "v4"), ("v3", "v5"), ("v3", "v6"), ("v4", "v6"), ("v5", "v7"), ("v6", "v7")]
    lab = _trace_values(False)
    tv = {"x1": lab["v1"], "x2": lab["v2"]}
    tv.update({k: lab[k] for k in ("v3", "v4", "v5", "v6", "v7")})
    return _trace_figure(nodes, edges, {"$f$": ("v7", 5.25, 0)}, tv, "fig8-4", out_dir, (7.2, 3.6))


def fig_8_5(out_dir=None):
    """Figure 8.5: the trace extended to two outputs f1 = v7 and f2 = v8 = v5 v6, with values at x = (1, 2)."""
    nodes = {"x1": (0, 1, r"$v_1$", r"$x_1$"), "x2": (0, -1, r"$v_2$", r"$x_2$"),
             "v3": (1.5, 1, r"$v_3$", r"$v_1v_2$"), "v4": (1.5, -1, r"$v_4$", r"$\sin v_2$"),
             "v5": (3.0, 1, r"$v_5$", r"$\exp v_3$"), "v6": (3.0, -1, r"$v_6$", r"$v_3-v_4$"),
             "v7": (4.5, 1, r"$v_7$", r"$v_5+v_6$"), "v8": (4.5, -1, r"$v_8$", r"$v_5v_6$")}
    edges = [("x1", "v3"), ("x2", "v3"), ("x2", "v4"), ("v3", "v5"), ("v3", "v6"), ("v4", "v6"),
             ("v5", "v7"), ("v6", "v7"), ("v5", "v8"), ("v6", "v8")]
    lab = _trace_values(True)
    tv = {"x1": lab["v1"], "x2": lab["v2"]}
    tv.update({k: lab[k] for k in ("v3", "v4", "v5", "v6", "v7", "v8")})
    return _trace_figure(nodes, edges, {"$f_1$": ("v7", 5.25, 1), "$f_2$": ("v8", 5.25, -1)}, tv, "fig8-5",
                         out_dir, (7.2, 4.0))


def cost_counts(widths=(2, 4, 8, 16, 32, 64), D=8, K=4):
    """Multiply-adds per gradient: forward pass, backpropagation, and central differences (2W forward passes),
    counted by the instrumented FeedForwardNet on fully connected D-M-M-K networks."""
    rows = []
    rng = np.random.default_rng(0)
    for M in widths:
        net = layered_net([D, M, M, K], "tanh", "linear")
        w = rng.normal(size=net.W) * 0.3
        x, t = rng.normal(size=D), rng.normal(size=K)
        net.ops = {"forward": 0, "backward": 0, "grad": 0}
        net.backprop(w, x, t)
        fw = net.ops["forward"]
        bp = fw + net.ops["backward"] + net.ops["grad"]
        rows.append(dict(M=M, W=net.W, forward=fw, backprop=bp, central=2 * net.W * fw))
    return rows


def graph_size(outs):
    """(nodes, edges) of the recorded computational graph that produced the outputs (inputs excluded)."""
    seen, n, e = set(), 0, 0
    for o in outs:
        for node in _topo(o):
            if id(node) not in seen:
                seen.add(id(node))
                if node.parents:
                    n += 1
                    e += len(node.parents)
    return n, e


def jacobian_counts(Ds=(1, 2, 4, 8, 16, 32, 64), K_list=(1, 8), M=16):
    """Operations for the full K x D Jacobian of a D-M-K tanh network, counted on its computational graph
    (n elementary operations, e edges). A forward-mode pass evaluates every node and, per edge, one
    multiply-add of the tangents: n + 2e, so D passes cost D (n + 2e). Reverse mode records the graph once
    (n) and runs one backward sweep (one multiply-add per edge, 2e) per output: n + 2Ke."""
    rows = []
    rng = np.random.default_rng(1)
    for K in K_list:
        for D in Ds:
            W1, W2 = rng.normal(size=(M, D)) / math.sqrt(D), rng.normal(size=(K, M)) / math.sqrt(M)
            xs = [Var(float(v)) for v in rng.normal(size=D)]
            z = []
            for j in range(M):
                s = xs[0] * W1[j, 0]
                for i in range(1, D):
                    s = s + xs[i] * W1[j, i]
                z.append(tanh(s))
            outs = []
            for k in range(K):
                s = z[0] * W2[k, 0]
                for j in range(1, M):
                    s = s + z[j] * W2[k, j]
                outs.append(s)
            n, e = graph_size(outs)
            rows.append(dict(K=K, D=D, n=n, e=e, forward=D * (n + 2 * e), reverse=n + 2 * K * e))
    return rows


def fig_8_s1(out_dir=None):
    """Figure 8.S1: exact operation counts, backprop O(W) against central differences O(W^2); and the full Jacobian by forward mode (D passes) against reverse mode (K passes)."""
    rows = cost_counts()
    fig, axs = plt.subplots(1, 2, figsize=(10.2, 3.9))
    ax = axs[0]
    W = np.array([r["W"] for r in rows])
    ax.loglog(W, [r["forward"] for r in rows], "o-", color=common.GREY, label="one forward pass")
    ax.loglog(W, [r["backprop"] for r in rows], "o-", color=common.BLUE, label="backpropagation (forward + backward)")
    ax.loglog(W, [r["central"] for r in rows], "o-", color=common.RED, label="central differences (2W forward passes)")
    ax.set_xlabel("number of weights and biases $W$")
    ax.set_ylabel("multiply-adds per gradient")
    ax.legend(frameon=False, fontsize=8.5)
    panel_label(ax, "a", "lower right")
    ax = axs[1]
    jr = jacobian_counts()
    for K, col in ((1, common.BLUE), (8, common.RED)):
        sub = [r for r in jr if r["K"] == K]
        Ds = [r["D"] for r in sub]
        ax.loglog(Ds, [r["forward"] for r in sub], "o-", color=col, label="forward mode, $K=%d$" % K)
        ax.loglog(Ds, [r["reverse"] for r in sub], "s--", color=col, label="reverse mode, $K=%d$" % K)
    ax.set_xlabel("number of inputs $D$")
    ax.set_ylabel("operations for the full $K\\times D$ Jacobian")
    ax.legend(frameon=False, fontsize=8.5)
    panel_label(ax, "b", "lower right")
    fig.tight_layout()
    return savefig(fig, CH, "fig8-s1", out_dir)


def onehidden_np(w, x, t, M):
    """Vectorised 1-M-1 tanh network of HessDemo (same parameter order): returns E, the gradient, the matrix B of
    rows grad y_n, the exact Hessian H = sum_n (b_n b_n^T + r_n grad grad y_n) and the residual term R."""
    x, t = np.asarray(x, float), np.asarray(t, float)
    b1, w1 = w[0:2 * M:2], w[1:2 * M:2]
    c, v = w[2 * M], w[2 * M + 1:]
    A = b1[None, :] + w1[None, :] * x[:, None]                 # N x M
    Z = np.tanh(A)
    hp, hpp = 1 - Z ** 2, -2 * Z * (1 - Z ** 2)
    y = c + Z @ v
    r = y - t
    N, W = len(x), 3 * M + 1
    B = np.zeros((N, W))
    B[:, 0:2 * M:2] = v * hp
    B[:, 1:2 * M:2] = v * hp * x[:, None]
    B[:, 2 * M] = 1.0
    B[:, 2 * M + 1:] = Z
    R = np.zeros((W, W))
    for j in range(M):
        ib, iw, iv = 2 * j, 2 * j + 1, 2 * M + 1 + j
        s0, s1, s2 = np.sum(r * v[j] * hpp[:, j]), np.sum(r * v[j] * hpp[:, j] * x), np.sum(r * v[j] * hpp[:, j] * x * x)
        R[ib, ib], R[ib, iw], R[iw, iw] = s0, s1, s2
        R[iw, ib] = s1
        R[ib, iv] = R[iv, ib] = np.sum(r * hp[:, j])
        R[iw, iv] = R[iv, iw] = np.sum(r * hp[:, j] * x)
    G = B.T @ B
    return 0.5 * np.sum(r ** 2), B.T @ r, B, G + R, R


def train_onehidden_np(M, N, sigma, steps, eta=0.01, seed=1, data_seed=7, x=None, t=None):
    """Full-batch Adam on the HessDemo problem (vectorised; same initial weights and data as HessDemo)."""
    d = HessDemo(M, N, sigma, seed, data_seed)
    x = np.array(d.x) if x is None else x
    t = np.array(d.t) if t is None else t
    w = np.array(d.w)
    m, s = np.zeros_like(w), np.zeros_like(w)
    for k in range(1, steps + 1):
        g = onehidden_np(w, x, t, M)[1]
        m = 0.9 * m + 0.1 * g
        s = 0.999 * s + 0.001 * g * g
        w -= eta * (m / (1 - 0.9 ** k)) / (np.sqrt(s / (1 - 0.999 ** k)) + 1e-8)
    return w, x, t


def averaging_study(Ns=(10, 20, 40, 80, 160, 320, 640, 1280), reps=40, sigma=0.3):
    """The book's averaging argument for neglecting the second term of (8.39), made exact.

    Noisy targets: a teacher network w* (HessDemo, M = 6, trained on noise-free data) and t_n = y(x_n, w*) +
    sigma eps_n, evaluated at w*, where the residuals r_n = -sigma eps_n have mean zero and are independent of
    grad grad y_n; ||sum_n r_n grad grad y_n|| / ||sum_n b_n b_n^T|| then falls like N^-1/2.
    Too few hidden units: M = 1 at its best fit to sin(pi x) on a fine grid; the residuals are systematic,
    correlated with grad grad y_n, and the ratio does not fall with N. Data: x_n on a grid in [-1, 1]."""
    rng = np.random.default_rng(3)
    w6 = train_onehidden_np(6, 30, 0.0, 3000)[0]
    w1 = train_onehidden_np(1, 400, 0.0, 6000)[0]
    out = {"N": np.array(Ns, float), "noisy": [], "underfit": []}
    for N in Ns:
        x = np.linspace(-1, 1, N)
        y6 = _y_onehidden(w6, x, 6)
        vals = []
        for _ in range(reps):
            t = y6 + sigma * rng.normal(size=N)
            _, _, B, H, R = onehidden_np(w6, x, t, 6)
            vals.append(np.linalg.norm(R) / np.linalg.norm(B.T @ B))
        out["noisy"].append(float(np.mean(vals)))
        _, _, B, H, R = onehidden_np(w1, x, np.sin(np.pi * x), 1)
        out["underfit"].append(float(np.linalg.norm(R) / np.linalg.norm(B.T @ B)))
    out["noisy"], out["underfit"] = np.array(out["noisy"]), np.array(out["underfit"])
    return out


def _y_onehidden(w, x, M):
    return w[2 * M] + np.tanh(w[0:2 * M:2][None, :] + w[1:2 * M:2][None, :] * x[:, None]) @ w[2 * M + 1:]


def fig_8_s2(out_dir=None):
    """Figure 8.S2: the exact Hessian against the outer-product approximation for a 1-M-1 tanh network."""
    runs = [("noise-free targets, $M=6$", dict(M=6, N=30, sigma=0.0), common.BLUE),
            ("noisy targets ($\\sigma=0.3$), $M=6$", dict(M=6, N=30, sigma=0.3), common.GREEN),
            ("too few hidden units, $M=1$", dict(M=1, N=30, sigma=0.0), common.RED)]
    fig, axs = plt.subplots(1, 3, figsize=(12.6, 3.8))
    finals = []
    for lab, kw, col in runs:
        d, ts, errs, Es = hess_demo_run(steps=3000, every=50, **kw)
        axs[0].semilogy(ts, errs, color=col, label=lab)
        finals.append((lab, d, col))
    axs[0].set_xlabel("Adam step")
    axs[0].set_ylabel(r"$\|\mathbf{H}-\mathbf{H}_{\mathrm{OP}}\|_F\,/\,\|\mathbf{H}\|_F$")
    axs[0].legend(frameon=False, fontsize=8)
    panel_label(axs[0], "a", "lower left")
    ax = axs[1]
    st = averaging_study()
    ax.loglog(st["N"], st["noisy"], "o-", color=common.GREEN, label="noisy targets at the teacher $\\mathbf{w}^\\star$")
    ax.loglog(st["N"], st["underfit"], "s-", color=common.RED, label="noise-free, too few units ($M=1$)")
    ref = st["noisy"][0] * np.sqrt(st["N"][0] / st["N"])
    ax.loglog(st["N"], ref, "--", color=common.GREY, lw=1, label=r"slope $-1/2$")
    ax.set_xlabel("number of data points $N$")
    ax.set_ylabel(r"$\|\sum_n r_n\nabla\nabla y_n\|_F\,/\,\|\mathbf{H}_{\mathrm{OP}}\|_F$")
    ax.legend(frameon=False, fontsize=8)
    panel_label(ax, "b", "lower left")
    ax = axs[2]
    lab, d, col = finals[0]
    H, G = d.hessian(), d.outer()
    lh, lg = np.sort(np.linalg.eigvalsh(H))[::-1], np.sort(np.linalg.eigvalsh(G))[::-1]
    idx = np.arange(1, len(lh) + 1)
    ax.semilogy(idx, np.abs(lh), "o", color=common.BLUE, mfc="none", label="exact $\\mathbf{H}$, |eigenvalue|")
    ax.semilogy(idx[lh < 0], np.abs(lh[lh < 0]), "o", color=common.BLUE, label="negative eigenvalue of $\\mathbf{H}$")
    ax.semilogy(idx, np.maximum(lg, 1e-16), "x", color=common.ORANGE, label="outer product (all $\\geq 0$)")
    ax.set_xlabel("index (eigenvalues sorted)")
    ax.set_ylabel("eigenvalue")
    ax.set_title("after 3000 steps, noise-free targets, $M=6$", fontsize=9.5)
    ax.legend(frameon=False, fontsize=8)
    panel_label(ax, "c", "lower left")
    fig.tight_layout()
    return savefig(fig, CH, "fig8-s2", out_dir)


def fig_8_s3(out_dir=None):
    """Figure 8.S3: expression swell. Tree sizes of L_n and its symbolic derivative against the evaluation trace."""
    rows = swell_table(14)
    n = np.array([r["n"] for r in rows])
    fig, ax = plt.subplots(figsize=(6.2, 4.3))
    ax.semilogy(n, [r["df_tree"] for r in rows], "o-", color=common.RED, label="symbolic derivative $L_n'(x)$, written out")
    ax.semilogy(n, [r["f_tree"] for r in rows], "s-", color=common.ORANGE, label="the function $L_n(x)$, written out")
    ax.semilogy(n, [r["df_dag_naive"] for r in rows], "d--", color=common.PURPLE, label="derivative with shared nodes, but each occurrence re-derived")
    ax.semilogy(n, [r["ad_trace"] for r in rows], "^-", color=common.BLUE, label="trace of $L_n$ and $L_n'$, each node derived once (forward mode)")
    ax.semilogy(n, [r["f_trace"] for r in rows], "v-", color=common.GREEN, label="evaluation trace of $L_n$")
    ax.set_xlabel("$n$ (logistic map $L_{n+1}=4L_n(1-L_n)$)")
    ax.set_ylabel("number of nodes")
    ax.legend(frameon=False, fontsize=8)
    return savefig(fig, CH, "fig8-s3", out_dir)


def seq_inverse_study(alphas=np.logspace(-10, 1, 45), M=2):
    """Exercise 8.12 in practice, on the 1-M-1 network after training (W = 3M + 1 = 7 for M = 2).

    N = 30 > W: G = sum_n b_n b_n^T is invertible and the one-pass result equals (G + alpha I)^-1, within
    about alpha / lambda_min of G^-1. N = 5 < W: G has rank N, and the result has W - N eigenvalues 1/alpha."""
    out = {}
    for N, lab in ((30, "big"), (5, "small")):
        w, x, t = train_onehidden_np(M, N, 0.0, 3000)
        B = onehidden_np(w, x, t, M)[2]
        G = B.T @ B
        lam = np.linalg.eigvalsh(G)
        errs, exact, eig = [], [], []
        for a in alphas:
            S = sequential_inverse(list(B), a)
            exact.append(np.linalg.norm(S - np.linalg.inv(G + a * np.eye(G.shape[0]))) / np.linalg.norm(S))
            if N > G.shape[0]:
                errs.append(np.linalg.norm(S - np.linalg.inv(G)) / np.linalg.norm(np.linalg.inv(G)))
            eig.append(np.sort(np.linalg.eigvalsh((S + S.T) / 2)))
        out[lab] = dict(N=N, W=G.shape[0], lam=lam, err=np.array(errs), exact=np.array(exact), eig=np.array(eig),
                        alphas=alphas)
    return out


def fig_8_s4(out_dir=None):
    """Figure 8.S4: the sequential inverse Hessian (Exercise 8.12) and its dependence on the initial alpha."""
    st = seq_inverse_study()
    fig, axs = plt.subplots(1, 2, figsize=(10.0, 3.8))
    ax = axs[0]
    s = st["big"]
    lmin = s["lam"].min()
    ax.loglog(s["alphas"], s["err"], "o-", ms=3, color=common.BLUE, label="one pass from $\\alpha\\mathbf{I}$, $N=%d$, $W=%d$" % (s["N"], s["W"]))
    ax.loglog(s["alphas"], s["alphas"] / lmin, "--", color=common.GREY, lw=1, label=r"$\alpha/\lambda_{\min}$, $\lambda_{\min}=%.1e$" % lmin)
    ax.axvline(lmin, color=common.GREY, lw=0.8, ls=":")
    ax.set_ylim(1e-7, 3)
    ax.set_xlabel(r"initial $\alpha$ ($\mathbf{H}_0=\alpha\mathbf{I}$)")
    ax.set_ylabel(r"relative error against $\mathbf{H}_{\mathrm{OP}}^{-1}$")
    ax.legend(frameon=False, fontsize=8)
    panel_label(ax, "a", "lower right")
    ax = axs[1]
    s = st["small"]
    for i in range(s["eig"].shape[1]):
        big = i >= s["N"]
        ax.loglog(s["alphas"], s["eig"][:, i], color=common.RED if big else common.BLUE, lw=2.2 if big else 1.4,
                  label=("%d eigenvalues in the null space of $\\mathbf{H}_{\\mathrm{OP}}$" % (s["W"] - s["N"]) if i == s["N"]
                         else ("%d eigenvalues $\\approx 1/\\lambda_i$" % s["N"] if i == 0 else None)))
    ax.loglog(s["alphas"], 1 / s["alphas"], "--", color=common.GREY, lw=1, label=r"$1/\alpha$")
    ax.set_ylim(3e-4, None)
    ax.set_xlabel(r"initial $\alpha$")
    ax.set_ylabel("eigenvalues of the one-pass inverse")
    ax.set_title("$N=%d$ points, $W=%d$ weights: rank-deficient" % (s["N"], s["W"]), fontsize=9.5)
    ax.legend(frameon=False, fontsize=8.5)
    panel_label(ax, "b", "lower left")
    fig.tight_layout()
    return savefig(fig, CH, "fig8-s4", out_dir)


FIGURES = {"8.2": fig_8_2, "8.4": fig_8_4, "8.5": fig_8_5,
           "8.S1": fig_8_s1, "8.S2": fig_8_s2, "8.S3": fig_8_s3, "8.S4": fig_8_s4}

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