"""Bishop and Bishop (2024), Chapter 6: Deep Neural Networks.

Reproduces the figures of Chapter 6 of C. M. Bishop and H. Bishop, Deep Learning: Foundations and
Concepts (Springer, 2024) that are computed from data, a model or a simulation, written from
scratch with numpy, scipy and matplotlib. Each algorithm is a short function meant
to be read next to the lecture notes (../ch06-deep-neural-networks.html):

* Section 6.1, limitations of fixed basis functions: n_poly_coefficients (the count behind (6.3)),
  the grid classifier of Figure 6.2 (grid_classify), hypersphere volumes and shells ((6.4), (6.5),
  Exercises 6.1 and 6.2: unit_sphere_area, unit_ball_volume, sphere_cube_ratio), the radial density
  of a Gaussian ((6.58), gauss_radial_density), and the digit manifold of Figure 6.7 (warp).
* Section 6.2, multilayer networks: ACT (the activation functions of Figure 6.12 with their
  derivatives, and swish of Exercise 6.5); TwoLayer, a two-layer network (6.7)-(6.12) whose weights
  are one flat vector, with forward propagation, backpropagation of any output error signal and
  plain finite differences; sigmoid_to_tanh_weights (Exercise 6.4); symmetry_orbit (the M! 2^M
  weight-space symmetries of Section 6.2.4); staircase_network and relu_interpolant (constructive
  universal approximation).
* Section 6.3, deep networks: DeepReLU (any depth, ReLU hidden units), activation_patterns and
  count_regions (linear regions of a ReLU network on a 2-D grid), sawtooth (the composition of tent
  maps with 2^L linear pieces from 2L hidden units), info_nce and clip_loss ((6.20), (6.21)).
* Section 6.4, error functions: sse, bce and softmax cross-entropy and the noise-variance estimates
  (6.25)-(6.36); noisy_label_error (Exercise 6.11).
* Section 6.5, mixture density networks: mdn_split, mdn_nll and mdn_deltas ((6.38)-(6.47), any
  number L of target dimensions), mdn_mean_var ((6.48), (6.50)), robot_forward / robot_inverse
  (Exercise 6.16) and the toy inverse problem of Figures 6.17 and 6.19.
* JSRandom: the seeded generator DK.rng of the browser demos (mulberry32 uniforms and Box-Muller
  normals). The demos' data, initial weights and Adam steps (adam_train) use only its numbers, so
  universal-approximation-demo.html, relu-regions-demo.html, high-dimensional-geometry-demo.html
  and robot-arm-mdn-demo.html reproduce its numbers.

Figures reproduced: 6.1, 6.2, 6.3 (redrawn: the grid itself is the content), 6.4, 6.5, 6.6, 6.7,
6.8 (at small scale, see below), 6.10, 6.11, 6.12, 6.16 (redrawn from the forward kinematics),
6.17 and 6.19, plus four figures for the notes that the book does not have: ex6.5 (swish and its
derivative, Exercise 6.5), relu-regions (linear regions against depth), robot-mdn (a mixture density
network on the robot arm of Section 6.5.1) and approx-rate (approximation error against the number
of hidden units).
Skipped, with the reason:
* Figure 6.9 (two-layer network diagram), 6.13 (transfer-learning schematic), 6.14 (contrastive
  learning schematic), 6.15 (a general feed-forward topology) and 6.18 (mixture density network
  diagram): network schematics with no data or computation (the notes redraw 6.9 and 6.15 as SVG).

Run `python3 ch06_deep_neural_networks.py --list`, `python3 ch06_deep_neural_networks.py` (all
figures, about a minute) or `python3 ch06_deep_neural_networks.py --fig 6.19`. Files go to
../img/ch06/; demo data to ../data/ch06-*.json.

What differs from the book, and the settings chosen where the book gives none:
* Figure 6.1 and 6.2: the Iris data (Fisher 1936) as shipped with scikit-learn; red = versicolor,
  green = virginica, blue = setosa; the test point is (6.1, 2.85) cm. Figure 6.2 uses a 6 x 6 grid
  over the plotted range and colours each cell by its majority class (white = empty).
* Figure 6.8: we have no natural photographs, so the "real images" row shows MNIST digits and the
  random row shows images of the same size with independent uniform pixels; a third panel compares
  the correlation of horizontally adjacent pixels (about 0.8 for digits, 0 for random images).
* Figure 6.10: N = 50 equally spaced points on [-1, 1] (the plotted points are equally spaced);
  panel (b) uses sin(2.5 x), because the caption's sin(x) is almost a straight line on (-1, 1) while
  the plotted curve rises from a minimum near -0.6 to a maximum near 0.6. Three tanh hidden units,
  linear output, sum-of-squares error, L-BFGS from 20 random starts (best kept).
* Figure 6.11: the generating distributions are not given; we draw 50 points per class from our
  own: blue N((-0.6, 0), diag(0.7^2, 1.2^2)), red an equal mixture of N((1.0, 1.2), diag(0.5^2, 0.6^2))
  and N((1.1, -0.9), diag(0.5^2, 0.6^2)). The green curve is the 0.5 contour of the true posterior.
  The dashed blue lines are a_j = 0 for each hidden unit, where z_j = tanh(a_j) = 0 (the caption
  says z = 0.5, which is the midpoint of the logistic sigmoid, not of tanh).
* Figure 6.12: leaky ReLU drawn with alpha = 0.1.
* Figures 6.17 and 6.19: N = 300 points; x uniform on (0, 1), t = x + 0.3 sin(2 pi x) + U(-0.1, 0.1).
  Networks: 6 tanh hidden units (6.17) and 5 tanh hidden units with 9 outputs (6.19), fitted with
  L-BFGS from 8 random starts (best kept), with a small weight decay (0.01 for 6.17, 0.1 for 6.19) that
  keeps the fits away from near-vertical steps and from components collapsing onto a few points.
  Which colour is which component is arbitrary.
* Figure 6.16: drawn from the forward and inverse kinematics (robot_forward, robot_inverse) with
  L1 = 1, L2 = 0.7.
* The MDN demo agrees with numpy to about
  1e-11 for the first 150 Adam steps; later the last-bit differences between the browser's and numpy's
  tanh/exp/log are amplified while the component widths shrink, so longer runs are not compared.
"""
import json
import math
import os
import sys
from itertools import permutations, product

import numpy as np
from scipy import optimize, special

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

CH = 6
CACHE = os.path.join(HERE, "cache")
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
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 the 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)


# =========================================================================== Section 6.1
def n_poly_coefficients(D, M):
    """Number of independent coefficients of a general polynomial of order M in D variables.

    A monomial x_1^{k_1} ... x_D^{k_D} with k_1 + ... + k_D <= M is a multiset, so the count is
    C(D + M, M) (stars and bars); for fixed M it grows like D^M / M!.
    """
    return math.comb(D + M, M)


def unit_sphere_area(D):
    """Surface area S_D = 2 pi^{D/2} / Gamma(D/2) of the unit sphere in R^D (6.53)."""
    return 2.0 * math.pi ** (D / 2) / math.gamma(D / 2)


def unit_ball_volume(D):
    """Volume V_D = S_D / D of the unit ball in R^D (6.54)."""
    return unit_sphere_area(D) / D


def sphere_cube_ratio(D):
    """Volume of the ball of radius a over the cube of side 2a (6.55), computed in logs."""
    return math.exp((D / 2) * math.log(math.pi) - math.log(D) - (D - 1) * math.log(2) - math.lgamma(D / 2))


def shell_fraction(eps, D):
    """Fraction of the unit ball's volume between radius 1 - eps and 1 (6.5)."""
    return 1.0 - (1.0 - np.asarray(eps, float)) ** D


def gauss_radial_density(r, D, sigma=1.0):
    """Density of r = ||x|| for x ~ N(0, sigma^2 I_D) (6.58), evaluated in logs."""
    r = np.asarray(r, float)
    with np.errstate(divide="ignore"):
        lp = (math.log(2) + (D / 2) * math.log(math.pi) - math.lgamma(D / 2) + (D - 1) * np.log(r)
              - (D / 2) * math.log(2 * math.pi * sigma ** 2) - r ** 2 / (2 * sigma ** 2))
    return np.exp(lp)


def iris_sepal():
    """Iris sepal length and width (cm) and labels 0 setosa, 1 versicolor, 2 virginica."""
    from sklearn.datasets import load_iris
    d = load_iris()
    return d.data.astype(float), d.target.astype(int)


def grid_classify(Xtr, ytr, Xte, lo, hi, k, K=3):
    """The grid classifier of Figure 6.2: each test point gets the majority class of the training
    points in its cell of a k^D grid over the box [lo, hi]; -1 if the cell is empty (ties go to the
    smallest label). Returns (labels, number of non-empty cells)."""
    lo, hi = np.asarray(lo, float), np.asarray(hi, float)

    def cell(X):
        c = np.floor((X - lo) / (hi - lo) * k).astype(int)
        c = np.clip(c, 0, k - 1)
        return [tuple(r) for r in c]

    counts = {}
    for c, y in zip(cell(Xtr), ytr):
        counts.setdefault(c, np.zeros(K, int))[y] += 1
    out = np.array([int(np.argmax(counts[c])) if c in counts else -1 for c in cell(Xte)])
    return out, len(counts)


def mc_empty_cells(D, k, N, seed):
    """Monte Carlo with the demos' generator: N points uniform in [0, 1]^D, a k^D grid;
    returns the fraction of cells that hold no point and the fraction of N fresh points that
    land in an empty cell (the probability that a test point cannot be classified).
    Same arithmetic as high-dimensional-geometry-demo.html (panel 4)."""
    r = JSRandom(seed)
    occ = set()
    for _ in range(N):
        occ.add(tuple(min(int(r.u() * k), k - 1) for _ in range(D)))
    miss = 0
    for _ in range(N):
        if tuple(min(int(r.u() * k), k - 1) for _ in range(D)) not in occ:
            miss += 1
    return 1.0 - len(occ) / float(k) ** D, miss / N


def mc_gauss_radii(D, n, seed):
    """n radii ||x|| of standard Gaussian vectors in R^D, with the demos' generator (panel 2)."""
    r = JSRandom(seed)
    out = np.empty(n)
    for i in range(n):
        s = 0.0
        for _ in range(D):
            z = r.norm()
            s += z * z
        out[i] = math.sqrt(s)
    return out


def mc_shell(D, eps, n, seed):
    """Fraction of n uniform points in the unit ball of R^D that lie within eps of the surface.

    A uniform point in the ball is (direction) * U^{1/D}, so only the radius matters:
    the point is in the shell when U^{1/D} > 1 - eps (panel 1 of the geometry demo)."""
    r = JSRandom(seed)
    hit = 0
    for _ in range(n):
        if r.u() ** (1.0 / D) > 1.0 - eps:
            hit += 1
    return hit / n


def mc_distance_contrast(D, n, seed):
    """(max - min) / min of the distances from one uniform point to n others in [0, 1]^D:
    the relative contrast that vanishes as D grows (distance concentration, panel 3)."""
    r = JSRandom(seed)
    q = [r.u() for _ in range(D)]
    ds = []
    for _ in range(n):
        s = 0.0
        for j in range(D):
            d = r.u() - q[j]
            s += d * d
        ds.append(math.sqrt(s))
    return (max(ds) - min(ds)) / min(ds)


def warp(img, dx=0.0, dy=0.0, angle=0.0, size=40):
    """Place a 28 x 28 digit in a size x size frame, rotated by angle (degrees) and shifted."""
    from scipy import ndimage
    big = np.zeros((size, size))
    o = (size - 28) // 2
    big[o:o + 28, o:o + 28] = img.reshape(28, 28)
    big = ndimage.rotate(big, angle, reshape=False, order=1)
    big = ndimage.shift(big, (dy, dx), order=1)
    return np.clip(big, 0, 1)


# =========================================================================== Section 6.2: activations
def _sig(a):
    return 0.5 * (1.0 + np.tanh(0.5 * np.asarray(a, float)))


def _softplus(a):
    a = np.asarray(a, float)
    return np.maximum(a, 0) + np.log1p(np.exp(-np.abs(a)))


LEAK = 0.1
ACT = {
    # name: (h(a), h'(a)); derivatives at the kinks use the right-hand value (ReLU'(0) = 0 as in the demos)
    "tanh": (np.tanh, lambda a: 1.0 - np.tanh(a) ** 2),
    "sigmoid": (_sig, lambda a: _sig(a) * (1 - _sig(a))),
    "hardtanh": (lambda a: np.clip(a, -1, 1), lambda a: ((np.asarray(a) > -1) & (np.asarray(a) < 1)).astype(float)),
    "softplus": (_softplus, _sig),
    "relu": (lambda a: np.maximum(a, 0.0), lambda a: (np.asarray(a) > 0).astype(float)),
    "leaky": (lambda a: np.maximum(a, 0.0) + LEAK * np.minimum(a, 0.0), lambda a: np.where(np.asarray(a) > 0, 1.0, LEAK)),
    "abs": (np.abs, lambda a: np.where(np.asarray(a) > 0, 1.0, -1.0)),
    "swish": (lambda a: np.asarray(a) * _sig(a), lambda a: _sig(a) + np.asarray(a) * _sig(a) * (1 - _sig(a))),
    "identity": (lambda a: np.asarray(a, float), lambda a: np.ones_like(np.asarray(a, float))),
}


def swish(x, beta):
    """Swish x sigma(beta x) (6.61) and its derivative sigma(bx) + b x sigma(bx)(1 - sigma(bx))."""
    s = _sig(beta * np.asarray(x, float))
    return x * s, s + beta * x * s * (1 - s)


# =========================================================================== Section 6.2: a two-layer network
class TwoLayer:
    """A two-layer network (6.7)-(6.12): D inputs, M hidden units with activation `act`, O outputs.

    The weights are one flat vector w (the layout of the demos): hidden unit j holds
    [bias, w_j1 .. w_jD] at j (D + 1); output k holds [bias, w_k1 .. w_kM] at o2 + k (M + 1).
    forward returns the hidden pre-activations, hidden outputs and output pre-activations;
    backward turns output error signals delta_k = dE_n / da_k into dE / dw by backpropagation.
    """

    def __init__(self, D, M, O, act="tanh"):
        self.D, self.M, self.O, self.act = D, M, O, act
        self.o2 = M * (D + 1)
        self.W = self.o2 + O * (M + 1)

    def unpack(self, w):
        W1 = w[:self.o2].reshape(self.M, self.D + 1)
        W2 = w[self.o2:].reshape(self.O, self.M + 1)
        return W1, W2

    def forward(self, w, X):
        W1, W2 = self.unpack(np.asarray(w, float))
        X = np.asarray(X, float).reshape(-1, self.D)
        a1 = X @ W1[:, 1:].T + W1[:, 0]
        z = ACT[self.act][0](a1)
        a2 = z @ W2[:, 1:].T + W2[:, 0]
        return a1, z, a2

    def backward(self, w, X, delta):
        """dE/dw from the output error signals delta (N x O): (6.31)-style deltas pushed back."""
        W1, W2 = self.unpack(np.asarray(w, float))
        X = np.asarray(X, float).reshape(-1, self.D)
        a1, z, _ = self.forward(w, X)
        g2 = np.concatenate([delta.sum(0)[:, None], delta.T @ z], axis=1)
        d1 = ACT[self.act][1](a1) * (delta @ W2[:, 1:])
        g1 = np.concatenate([d1.sum(0)[:, None], d1.T @ X], axis=1)
        return np.concatenate([g1.ravel(), g2.ravel()])

    def init(self, rng, sd1=1.0, sd2=None):
        """Initial weights in flat order from a JSRandom: first layer N(0, sd1^2), second N(0, sd2^2)."""
        sd2 = 1.0 / math.sqrt(self.M) if sd2 is None else sd2
        w = np.empty(self.W)
        for i in range(self.o2):
            w[i] = sd1 * rng.norm()
        for i in range(self.o2, self.W):
            w[i] = sd2 * rng.norm()
        return w


def sse_error(net, w, X, T):
    """Sum-of-squares error (6.26)/(6.29) and its output deltas y - t (6.31)."""
    a2 = net.forward(w, X)[2]
    d = a2 - np.asarray(T, float).reshape(a2.shape)
    return 0.5 * float(np.sum(d * d)), d


def bce_error(net, w, X, T):
    """Cross-entropy (6.33) for a logistic-sigmoid output, written with the stable softplus, and y - t."""
    a = net.forward(w, X)[2]
    t = np.asarray(T, float).reshape(a.shape)
    return float(np.sum(_softplus(a) - t * a)), _sig(a) - t


def fd_grad(f, w, eps=1e-6):
    """Central finite differences of a scalar function f(w)."""
    w = np.array(w, float)
    g = np.zeros_like(w)
    for i in range(len(w)):
        wi = w[i]
        w[i] = wi + eps
        fp = f(w)
        w[i] = wi - eps
        fm = f(w)
        w[i] = wi
        g[i] = (fp - fm) / (2 * eps)
    return g


def fit_lbfgs(net, err, X, T, starts=10, seed=0, sd1=1.0, maxiter=3000, wd=0.0):
    """Minimise err(net, w, X, T) + (wd/2)|w|^2 with L-BFGS from several random starts; best kept."""
    rng = np.random.default_rng(seed)
    best = None
    for s in range(starts):
        w0 = np.concatenate([rng.normal(0, sd1, net.o2), rng.normal(0, 1 / math.sqrt(net.M), net.W - net.o2)])

        def fg(w):
            E, d = err(net, w, X, T)
            return E + 0.5 * wd * w @ w, net.backward(w, X, d) + wd * w

        r = optimize.minimize(fg, w0, jac=True, method="L-BFGS-B", options={"maxiter": maxiter, "gtol": 1e-10})
        if best is None or r.fun < best.fun:
            best = r
    return best.x, best.fun


def adam_train(net, w0, X, T, err, lr=0.02, steps=500, wd=0.0, record=None):
    """Adam on E(w)/N + (wd/2) w^T w, full batch: the optimiser of the demos (same arithmetic).

    err(net, w, X, T) returns (E, output deltas). Returns the final weights and, if record is an
    int r, the list of E/N after every r steps (starting with the initial value)."""
    w = np.array(w0, float)
    m, v = np.zeros_like(w), np.zeros_like(w)
    N = len(X)
    hist = []
    if record:
        hist.append(err(net, w, X, T)[0] / N)
    for t in range(1, steps + 1):
        E, d = err(net, w, X, T)
        g = net.backward(w, X, d) / N + wd * w
        m = 0.9 * m + (1 - 0.9) * g
        v = 0.999 * v + (1 - 0.999) * g * g
        c1, c2 = 1 - 0.9 ** t, 1 - 0.999 ** t
        w = w - lr * (m / c1) / (np.sqrt(v / c2) + 1e-8)
        if record and t % record == 0:
            hist.append(err(net, w, X, T)[0] / N)
    return (w, hist) if record else w


# ==== the universal-approximation demo
APPROX_TARGETS = {
    "x2": lambda x: x * x,
    "sin": lambda x: np.sin(2.5 * x),
    "abs": np.abs,
    "step": lambda x: (np.asarray(x) > 0).astype(float),
}


def approx_data(fn, N=50):
    """N equally spaced points on [-1, 1] and the target f(x) (Figure 6.10, the demo's data)."""
    x = np.array([-1.0 + 2.0 * n / (N - 1) for n in range(N)])
    return x[:, None], APPROX_TARGETS[fn](x)[:, None]


def approx_demo_run(fn, act, M, seed, sd1, lr, steps):
    """What universal-approximation-demo.html does: init from JSRandom(seed), Adam on E/N.
    Returns the final mean error E/N and the weights."""
    X, T = approx_data(fn)
    net = TwoLayer(1, M, 1, act)
    w0 = net.init(JSRandom(seed), sd1)
    w = adam_train(net, w0, X, T, sse_error, lr=lr, steps=steps)
    return sse_error(net, w, X, T)[0] / len(X), w


# ==== Exercise 6.4 and the weight-space symmetries of Section 6.2.4
def sigmoid_to_tanh_weights(net, w):
    """Weights of a tanh network computing exactly the same function as the logistic-sigmoid
    network `w`: sigma(a) = (1 + tanh(a/2)) / 2 gives w1' = w1 / 2 (biases included),
    w2'_kj = w2_kj / 2 for j >= 1 and w2'_k0 = w2_k0 + (1/2) sum_{j>=1} w2_kj."""
    W1, W2 = net.unpack(np.asarray(w, float))
    V1 = W1 / 2.0
    V2 = W2.copy()
    V2[:, 1:] = W2[:, 1:] / 2.0
    V2[:, 0] = W2[:, 0] + 0.5 * W2[:, 1:].sum(1)
    return np.concatenate([V1.ravel(), V2.ravel()])


def symmetry_orbit(net, w):
    """All M! 2^M weight vectors obtained from w by permuting hidden units and flipping signs
    (for an odd activation such as tanh every one computes the same function)."""
    W1, W2 = net.unpack(np.asarray(w, float))
    out = []
    for perm in permutations(range(net.M)):
        for signs in product((1.0, -1.0), repeat=net.M):
            s = np.array(signs)
            V1 = W1[list(perm)] * s[:, None]
            V2 = W2.copy()
            V2[:, 1:] = W2[:, 1:][:, list(perm)] * s
            out.append(np.concatenate([V1.ravel(), V2.ravel()]))
    return np.array(out)


# ==== constructive universal approximation in one dimension
def staircase_network(f, n, s, lo=0.0, hi=1.0):
    """A sigmoid network with n hidden units approximating f on [lo, hi] (the proof in the notes):
    g(x) = f(x_0) + sum_j [f(x_j) - f(x_{j-1})] sigma(s (x - x_{j-1} - h/2)), x_j = lo + j h.
    (The step is centred half a cell after x_{j-1}, so at the grid points it is nearly 0 or 1.)"""
    xs = np.linspace(lo, hi, n + 1)
    h = (hi - lo) / n
    d = np.diff(f(xs))
    c = xs[:-1] + h / 2

    def g(x):
        x = np.asarray(x, float)
        return f(xs[0]) + (d[None, :] * _sig(s * (x[:, None] - c[None, :]))).sum(1)

    return g


def relu_interpolant(f, n, lo=0.0, hi=1.0):
    """A ReLU network with n hidden units equal to the piecewise-linear interpolant of f at n + 1
    equally spaced knots: g(x) = f(x_0) + sum_j (s_j - s_{j-1}) relu(x - x_{j-1}), s_0 = 0."""
    xs = np.linspace(lo, hi, n + 1)
    slopes = np.diff(f(xs)) / np.diff(xs)
    c = np.diff(np.concatenate([[0.0], slopes]))

    def g(x):
        x = np.asarray(x, float)
        return f(xs[0]) + (c[None, :] * np.maximum(x[:, None] - xs[:-1][None, :], 0)).sum(1)

    return g


# =========================================================================== Section 6.3: depth
class DeepReLU:
    """A fully connected network with ReLU hidden layers of the given widths and one linear output.

    Weights are drawn unit by unit from a JSRandom, [bias, weights] per unit, layer by layer:
    bias N(0, sb^2), weights N(0, 2 / fan_in) (He initialisation): the relu-regions demo's order."""

    def __init__(self, D, widths, seed, sb=0.5):
        r = JSRandom(seed)
        self.D, self.widths, self.layers = D, list(widths), []
        fan = D
        for n in list(widths) + [1]:
            b = np.empty(n)
            Wm = np.empty((n, fan))
            sd = math.sqrt(2.0 / fan)
            for i in range(n):
                b[i] = sb * r.norm()
                for j in range(fan):
                    Wm[i, j] = sd * r.norm()
            self.layers.append((Wm, b))
            fan = n

    def forward(self, X):
        """Output and the list of hidden pre-activations; sums run in input order (as in the demo)."""
        h = np.asarray(X, float)
        pre = []
        for li, (Wm, b) in enumerate(self.layers):
            a = np.repeat(b[None, :], len(h), axis=0)
            for j in range(Wm.shape[1]):
                a = a + h[:, j:j + 1] * Wm[:, j][None, :]
            if li < len(self.layers) - 1:
                pre.append(a)
                h = np.maximum(a, 0.0)
            else:
                return a[:, 0], pre


def grid2(G, lo=-1.0, hi=1.0):
    """Pixel centres of a G x G grid on [lo, hi]^2, row by row from the top (the demo's order)."""
    c = np.array([lo + (hi - lo) * (i + 0.5) / G for i in range(G)])
    yy, xx = np.meshgrid(c[::-1], c, indexing="ij")
    return np.stack([xx.ravel(), yy.ravel()], axis=1)


def activation_patterns(pre):
    """Activation pattern (which ReLUs are on) of every point, as an integer id per point."""
    bits = np.concatenate([(a > 0) for a in pre], axis=1)
    _, ids = np.unique(bits, axis=0, return_inverse=True)
    return ids.ravel(), bits


def count_regions(net, G=200, lo=-1.0, hi=1.0):
    """Number of distinct activation patterns on a G x G grid: the linear regions seen at that
    resolution (each pattern is one region of input space for a one-hidden-layer network; for a
    deep network a pattern can in principle cover several pieces, and tiny regions can be missed)."""
    _, pre = net.forward(grid2(G, lo, hi))
    ids, _ = activation_patterns(pre)
    return int(ids.max()) + 1


def arrangement_regions(Wm, b, lo=-1.0, hi=1.0):
    """Exact number of regions cut out of the square [lo, hi]^2 by the lines w_i . x + b_i = 0, for
    lines in general position: 1 + (lines that cross the square) + (crossings inside the square).
    (Each line entering the square adds one region plus one per earlier line it crosses inside.)"""
    corners = np.array([(lo, lo), (lo, hi), (hi, lo), (hi, hi)])
    vals = corners @ Wm.T + b
    n_lines = int(np.sum((vals.min(0) < 0) & (vals.max(0) > 0)))
    n_cross = 0
    for i in range(len(b)):
        for j in range(i + 1, len(b)):
            p = np.linalg.solve(np.array([Wm[i], Wm[j]]), -np.array([b[i], b[j]]))
            n_cross += int(lo < p[0] < hi and lo < p[1] < hi)
    return 1 + n_lines + n_cross


def tent(x):
    """The tent map 2 relu(x) - 4 relu(x - 1/2), which maps [0, 1] onto itself with two pieces."""
    return 2 * np.maximum(x, 0) - 4 * np.maximum(x - 0.5, 0)


def sawtooth(x, L):
    """L compositions of the tent map: a ReLU network with L hidden layers of 2 units, 2^L pieces."""
    y = np.asarray(x, float)
    for _ in range(L):
        y = tent(y)
    return y


def count_pieces(f, lo, hi, n=200001, tol=1e-6):
    """Number of linear pieces of a continuous piecewise-linear f on [lo, hi], from slope changes
    on a fine grid (a piece shorter than the grid step can be missed)."""
    x = np.linspace(lo, hi, n)
    s = np.diff(f(x)) / np.diff(x)
    idx = np.where(np.abs(np.diff(s)) > tol * max(1.0, np.abs(s).max()))[0]
    # a kink strictly inside a grid cell gives that cell an intermediate slope, so two adjacent
    # slope changes; count each run of adjacent changes once
    return 1 + int(len(idx) and 1 + np.sum(np.diff(idx) > 1))


def shallow_bound(M, D):
    """Maximum number of regions of an arrangement of M hyperplanes in R^D: sum_{j<=D} C(M, j)."""
    return sum(math.comb(M, j) for j in range(D + 1))


def montufar_lower(n, L, D):
    """Lower bound of Montufar et al. (2014) on the maximal number of linear regions of a ReLU
    network with L hidden layers of width n >= D on R^D: (floor(n/D))^{D(L-1)} sum_{j<=D} C(n, j)."""
    return (n // D) ** (D * (L - 1)) * shallow_bound(n, D)


# ==== contrastive losses (Section 6.3.5)
def info_nce(f, fp, fneg):
    """InfoNCE (6.20) for unit vectors: anchor f, positive fp, negatives fneg (N x d)."""
    logits = np.concatenate([[f @ fp], fneg @ f])
    return float(-logits[0] + common.logsumexp(logits))


def info_nce_grad_anchor(f, fp, fneg):
    """Gradient of (6.20) with respect to the anchor embedding f (treating f as unconstrained):
    -f_+ + sum_j p_j f_j, where p = softmax of the similarities over (f_+, f_1-, ..., f_N-)."""
    logits = np.concatenate([[f @ fp], fneg @ f])
    p = np.exp(logits - common.logsumexp(logits))
    keys = np.vstack([fp[None, :], fneg])
    return -fp + p @ keys


def clip_loss(fx, gy, xneg, yneg):
    """The two-sided loss (6.21) for one positive pair (fx, gy) with negative images xneg and
    negative captions yneg (all unit vectors)."""
    s = fx @ gy
    l1 = np.concatenate([[s], xneg @ gy])
    l2 = np.concatenate([[s], yneg @ fx])
    return float(0.5 * (-s + common.logsumexp(l1)) + 0.5 * (-s + common.logsumexp(l2)))


# =========================================================================== Section 6.4
def noisy_label_error(y, t, eps):
    """Negative log likelihood when each label is flipped with probability eps (Exercise 6.11)."""
    p1 = (1 - eps) * y + eps * (1 - y)
    return float(-np.sum(t * np.log(p1) + (1 - t) * np.log(1 - p1)))


# =========================================================================== Section 6.5: mixture density networks
def mdn_split(a, K, L):
    """Split output pre-activations (N x (L+2)K) into pi (6.40), sigma (6.41) and mu (6.42).
    Order: [a^pi_1..K, a^sigma_1..K, a^mu_{k l} at 2K + k L + l]."""
    a = np.atleast_2d(a)
    ap = a[:, :K]
    pi = np.exp(ap - common.logsumexp(ap, axis=1, keepdims=True))
    sig = np.exp(a[:, K:2 * K])
    mu = a[:, 2 * K:].reshape(len(a), K, L)
    return pi, sig, mu


def mdn_logcomp(a, T, K, L):
    """log pi_k + log N(t | mu_k, sigma_k^2 I) for every point and component (N x K)."""
    pi, sig, mu = mdn_split(a, K, L)
    T = np.asarray(T, float).reshape(len(pi), L)
    sq = ((T[:, None, :] - mu) ** 2).sum(2)
    return np.log(pi) - L * np.log(sig) - 0.5 * L * math.log(2 * math.pi) - 0.5 * sq / sig ** 2, sq, pi, sig, mu


def mdn_nll(a, T, K, L):
    """The error (6.43): minus the log likelihood of the mixture density network."""
    lc = mdn_logcomp(a, T, K, L)[0]
    return float(-common.logsumexp(lc, axis=1).sum())


def mdn_deltas(a, T, K, L):
    """dE_n / d(output pre-activations): (6.45) pi_k - gamma_k, (6.47) gamma_k (L - |t - mu_k|^2 / sigma_k^2),
    (6.46) gamma_k (mu_kl - t_l) / sigma_k^2, with gamma the posterior responsibilities (6.44)."""
    lc, sq, pi, sig, mu = mdn_logcomp(a, T, K, L)
    gam = np.exp(lc - common.logsumexp(lc, axis=1, keepdims=True))
    T = np.asarray(T, float).reshape(len(pi), L)
    d_pi = pi - gam
    d_sig = gam * (L - sq / sig ** 2)
    d_mu = gam[:, :, None] * (mu - T[:, None, :]) / sig[:, :, None] ** 2
    return np.concatenate([d_pi, d_sig, d_mu.reshape(len(pi), K * L)], axis=1), gam


def mdn_error(K, L):
    """An err(net, w, X, T) function for TwoLayer: the MDN error (6.43) and its deltas."""
    def err(net, w, X, T):
        a = net.forward(w, X)[2]
        return mdn_nll(a, T, K, L), mdn_deltas(a, T, K, L)[0]
    return err


def mdn_mean_var(pi, sig, mu):
    """Conditional mean (6.48) and variance s^2 (6.50) of the mixture (per input)."""
    L = mu.shape[2]
    mean = (pi[:, :, None] * mu).sum(1)
    var = (pi * (L * sig ** 2 + ((mu - mean[:, None, :]) ** 2).sum(2))).sum(1)
    return mean, var


def mdn_mode(pi, sig, mu, t0, iters=200):
    """A mode of one Gaussian mixture sum_k pi_k N(t | mu_k, sigma_k^2 I) by the fixed-point iteration
    t <- sum_k (gamma_k(t) / sigma_k^2) mu_k / sum_k (gamma_k(t) / sigma_k^2), which is grad ln p(t) = 0
    rearranged (each step does not decrease p). pi, sig: (K,), mu: (K, L), t0: (L,)."""
    t = np.array(t0, float)
    for _ in range(iters):
        lc = np.log(pi) - mu.shape[1] * np.log(sig) - 0.5 * ((t - mu) ** 2).sum(1) / sig ** 2
        g = np.exp(lc - common.logsumexp(lc)) / sig ** 2
        t = (g[:, None] * mu).sum(0) / g.sum()
    return t


def toy_inverse_data(N=300, seed=0):
    """The toy problem of Section 6.5.1: x ~ U(0, 1), t = x + 0.3 sin(2 pi x) + U(-0.1, 0.1)."""
    rng = np.random.default_rng(seed)
    x = rng.random(N)
    t = x + 0.3 * np.sin(2 * np.pi * x) + rng.uniform(-0.1, 0.1, N)
    return x, t


# ==== the robot arm of Figure 6.16 (Exercise 6.16)
ARM = (1.0, 0.7)


def robot_forward(th1, th2, L1=ARM[0], L2=ARM[1]):
    """End-effector position for joint angles theta_1 (first link from the horizontal) and theta_2
    (angle at the elbow between the two links, as in Figure 6.16):
    x1 = L1 cos th1 - L2 cos(th1 + th2), x2 = L1 sin th1 - L2 sin(th1 + th2)."""
    return L1 * np.cos(th1) - L2 * np.cos(th1 + th2), L1 * np.sin(th1) - L2 * np.sin(th1 + th2)


def robot_inverse(x1, x2, L1=ARM[0], L2=ARM[1]):
    """Both solutions (theta_1, theta_2) and (theta_1', 2 pi - theta_2) of the inverse kinematics.

    Law of cosines: r^2 = L1^2 + L2^2 - 2 L1 L2 cos th2. Then th1 = atan2(x2, x1) + beta with
    tan beta = L2 sin th2 / (L1 - L2 cos th2) (beta measured at the base, signed with th2)."""
    r2 = x1 * x1 + x2 * x2
    c = (L1 * L1 + L2 * L2 - r2) / (2 * L1 * L2)
    th2 = np.arccos(np.clip(c, -1, 1))
    sols = []
    for t2 in (th2, 2 * np.pi - th2):
        beta = np.arctan2(L2 * np.sin(t2), L1 - L2 * np.cos(t2))
        t1 = np.mod(np.arctan2(x2, x1) + beta, 2 * np.pi)
        sols.append((t1, t2))
    return sols


def robot_data(N, seed):
    """Training data of the robot-arm demo, from JSRandom(seed): theta_1 ~ U(pi/6, 5 pi/6),
    theta_2 ~ U(pi/3, 5 pi/3); inputs the end-effector position, targets the two angles."""
    r = JSRandom(seed)
    X, T = np.empty((N, 2)), np.empty((N, 2))
    for n in range(N):
        t1 = math.pi / 6 + (4 * math.pi / 6) * r.u()
        t2 = math.pi / 3 + (4 * math.pi / 3) * r.u()
        x1 = ARM[0] * math.cos(t1) - ARM[1] * math.cos(t1 + t2)
        x2 = ARM[0] * math.sin(t1) - ARM[1] * math.sin(t1 + t2)
        X[n] = (x1, x2)
        T[n] = (t1, t2)
    return X, T


def robot_demo_run(K, H, seed_data, seed_w, lr, steps, N=400, sse=False):
    """What robot-arm-mdn-demo.html does: data robot_data(N, seed_data), a TwoLayer(2, H, O) tanh
    network initialised from JSRandom(seed_w) with sd1 = 1, and Adam. Returns E/N and the weights."""
    X, T = robot_data(N, seed_data)
    if sse:
        net = TwoLayer(2, H, 2, "tanh")
        err = sse_error
    else:
        net = TwoLayer(2, H, 4 * K, "tanh")
        err = mdn_error(K, 2)
    w0 = net.init(JSRandom(seed_w), 1.0)
    w = adam_train(net, w0, X, T, err, lr=lr, steps=steps)
    return err(net, w, X, T)[0] / N, w, net


# =========================================================================== figure helpers
def _box(ax):
    ax.set_xticks([])
    ax.set_yticks([])


def _cache(name):
    os.makedirs(CACHE, exist_ok=True)
    return os.path.join(CACHE, name)


# =========================================================================== figures 6.1-6.8
IRIS_COL = {0: BLUE, 1: RED, 2: GREEN}
TEST_PT = (6.1, 2.85)


def fig_6_1(out=None):
    """Iris data: sepal length and width of three species, with a test point."""
    X, y = iris_sepal()
    fig, ax = plt.subplots(figsize=(4.6, 3.6))
    for c in (0, 1, 2):
        ax.scatter(X[y == c, 0], X[y == c, 1], s=18, facecolors="none", edgecolors=IRIS_COL[c], linewidths=1.1)
    ax.plot(*TEST_PT, "x", color="k", ms=10, mew=2.2)
    ax.set_xlabel("sepal length (cm)")
    ax.set_ylabel("sepal width (cm)")
    ax.set_xlim(4.0, 8.2)
    ax.set_ylim(1.8, 4.6)
    savefig(fig, CH, "fig6-1", out)


def fig_6_2(out=None):
    """The grid classifier on the Iris sepal data: majority class per cell, empty cells white."""
    X, y = iris_sepal()
    lo, hi, k = (4.0, 1.8), (8.2, 4.6), 6
    fig, ax = plt.subplots(figsize=(4.6, 3.6))
    xs = np.linspace(lo[0], hi[0], k + 1)
    ys = np.linspace(lo[1], hi[1], k + 1)
    from matplotlib.colors import to_rgba
    for i in range(k):
        for j in range(k):
            cen = np.array([[(xs[i] + xs[i + 1]) / 2, (ys[j] + ys[j + 1]) / 2]])
            lab, _ = grid_classify(X[:, :2], y, cen, lo, hi, k)
            if lab[0] >= 0:
                ax.add_patch(plt.Rectangle((xs[i], ys[j]), xs[1] - xs[0], ys[1] - ys[0], fc=to_rgba(IRIS_COL[lab[0]], 0.18), ec="none"))
    for v in xs:
        ax.axvline(v, color="k", lw=0.6)
    for v in ys:
        ax.axhline(v, color="k", lw=0.6)
    for c in (0, 1, 2):
        ax.scatter(X[y == c, 0], X[y == c, 1], s=16, facecolors="none", edgecolors=IRIS_COL[c], linewidths=1.0)
    ax.plot(*TEST_PT, "x", color="k", ms=10, mew=2.2)
    ax.set_xlabel("sepal length (cm)")
    ax.set_ylabel("sepal width (cm)")
    ax.set_xlim(lo[0], hi[0])
    ax.set_ylim(lo[1], hi[1])
    savefig(fig, CH, "fig6-2", out)


def fig_6_3(out=None):
    """A regular grid with 3 cells per axis has 3, 9 and 27 cells in D = 1, 2, 3."""
    fig = plt.figure(figsize=(8.4, 2.7))
    ax = fig.add_subplot(1, 3, 1)
    for v in np.linspace(0, 1, 4):
        ax.plot([v, v], [-0.04, 0.04], "k", lw=1)
    ax.plot([0, 1], [0, 0], "k", lw=1)
    ax.set_xlim(-0.05, 1.05)
    ax.set_ylim(-0.5, 0.5)
    ax.axis("off")
    ax.text(0.5, -0.25, "$x_1$", ha="center")
    ax.set_title("$D = 1$: 3 cells")
    ax = fig.add_subplot(1, 3, 2)
    for v in np.linspace(0, 1, 4):
        ax.plot([v, v], [0, 1], "k", lw=1)
        ax.plot([0, 1], [v, v], "k", lw=1)
    ax.set_aspect("equal")
    ax.axis("off")
    ax.text(0.5, -0.12, "$x_1$", ha="center")
    ax.text(-0.12, 0.5, "$x_2$", va="center")
    ax.set_title("$D = 2$: 9 cells")
    ax = fig.add_subplot(1, 3, 3, projection="3d")
    filled = np.zeros((3, 3, 3), bool)
    filled[:, :, 0] = True
    filled[0, :, :] = True
    filled[:, 2, :] = True
    ax.voxels(filled, facecolors=(0.12, 0.37, 0.75, 0.18), edgecolors="k", linewidth=0.5)
    ax.set_xlabel("$x_1$", labelpad=-12)
    ax.set_ylabel("$x_2$", labelpad=-12)
    ax.set_zlabel("$x_3$", labelpad=-12)
    ax.set_xticks([])
    ax.set_yticks([])
    ax.set_zticks([])
    ax.view_init(22, -60)
    ax.set_title("$D = 3$: 27 cells (some shown)")
    savefig(fig, CH, "fig6-3", out)


def fig_6_4(out=None):
    """Fraction of the volume of a unit ball within eps of its surface (6.5)."""
    eps = np.linspace(0, 1, 400)
    fig, ax = plt.subplots(figsize=(4.4, 3.4))
    for D, c in zip((1, 2, 5, 20), (BLUE, GREEN, ORANGE, RED)):
        ax.plot(eps, shell_fraction(eps, D), color=c, label="$D = %d$" % D)
    ax.set_xlabel(r"$\epsilon$")
    ax.set_ylabel("volume fraction")
    ax.set_xlim(0, 1)
    ax.set_ylim(0, 1)
    ax.legend(loc="lower right", frameon=False)
    savefig(fig, CH, "fig6-4", out)


def fig_6_5(out=None):
    """Radial density p(r) of a standard Gaussian in D = 1, 2, 20 dimensions (6.58)."""
    r = np.linspace(1e-4, 5, 600)
    fig, ax = plt.subplots(figsize=(4.4, 3.2))
    for D, c in zip((1, 2, 20), (BLUE, GREEN, RED)):
        ax.plot(r, gauss_radial_density(r, D), color=c, label="$D = %d$" % D)
    ax.set_xlabel("$r$")
    ax.set_ylabel("$p(r)$")
    ax.set_xlim(0, 5)
    ax.set_ylim(0, 2)
    ax.legend(frameon=False)
    savefig(fig, CH, "fig6-5", out)


def fig_6_6(out=None):
    """Two classes linearly separable in (x1, x2) but overlapping in x1 alone."""
    rng = np.random.default_rng(6)
    n = 40
    x1g = rng.uniform(0.05, 0.95, n)
    x2g = 0.9 * x1g + 0.35 + rng.uniform(0.0, 0.5, n)
    x1r = rng.uniform(0.05, 0.95, n)
    x2r = 0.9 * x1r + 0.15 - rng.uniform(0.0, 0.5, n)
    fig, axes = plt.subplots(1, 2, figsize=(7.6, 3.2), gridspec_kw={"width_ratios": [1, 1]})
    ax = axes[0]
    ax.scatter(x1g, x2g, s=22, facecolors="none", edgecolors=GREEN, linewidths=1.2)
    ax.scatter(x1r, x2r, s=22, facecolors="none", edgecolors=RED, linewidths=1.2)
    xx = np.linspace(0, 1, 2)
    ax.plot(xx, 0.9 * xx + 0.25, "k--", lw=1)
    ax.set_xlabel("$x_1$")
    ax.set_ylabel("$x_2$")
    _box(ax)
    panel_label(ax, "a")
    ax = axes[1]
    ax.scatter(x1g, np.zeros(n) + 0.03, s=22, facecolors="none", edgecolors=GREEN, linewidths=1.2)
    ax.scatter(x1r, np.zeros(n) - 0.03, s=22, facecolors="none", edgecolors=RED, linewidths=1.2)
    ax.set_ylim(-0.5, 0.5)
    ax.set_xlabel("$x_1$")
    _box(ax)
    panel_label(ax, "b")
    savefig(fig, CH, "fig6-6", out)


def _a_digit(label=3, index=0):
    X, y = common.mnist(train=False)
    return X[np.where(y == label)[0][index]]


def fig_6_7(out=None):
    """One handwritten digit shifted and rotated: points on a 3-D manifold in image space."""
    img = _a_digit(4, 4)
    params = [(-5, -3, -25), (4, -4, 10), (-2, 4, 35), (5, 3, -40), (0, 0, 0), (-4, 1, 60)]
    fig, axes = plt.subplots(1, len(params), figsize=(8.4, 1.6))
    for ax, (dx, dy, a) in zip(axes, params):
        ax.imshow(warp(img, dx, dy, a), cmap="gray_r", vmin=0, vmax=1)
        _box(ax)
    savefig(fig, CH, "fig6-7", out)


def fig_6_8(out=None):
    """Real images (MNIST digits) against images of independent uniform pixels, and the
    correlation of horizontally adjacent pixels in each."""
    X, y = common.mnist(train=False)
    rng = np.random.default_rng(8)
    idx = rng.choice(len(X), 6, replace=False)
    R = rng.random((6, 784))
    fig = plt.figure(figsize=(8.6, 3.2))
    gs = fig.add_gridspec(2, 8)
    for i in range(6):
        ax = fig.add_subplot(gs[0, i])
        ax.imshow(X[idx[i]].reshape(28, 28), cmap="gray_r", vmin=0, vmax=1)
        _box(ax)
        ax = fig.add_subplot(gs[1, i])
        ax.imshow(R[i].reshape(28, 28), cmap="gray_r", vmin=0, vmax=1)
        _box(ax)
    ax = fig.add_subplot(gs[:, 6:])
    big = X[:2000].reshape(-1, 28, 28)
    rb = rng.random((2000, 28, 28))
    c_real = np.corrcoef(big[:, :, :-1].ravel(), big[:, :, 1:].ravel())[0, 1]
    c_rand = np.corrcoef(rb[:, :, :-1].ravel(), rb[:, :, 1:].ravel())[0, 1]
    ax.bar([0, 1], [c_real, c_rand], color=[BLUE, GREY], width=0.6)
    ax.set_xticks([0, 1])
    ax.set_xticklabels(["digits", "random"])
    ax.set_ylim(-0.05, 1)
    ax.set_title("adjacent-pixel\ncorrelation", fontsize=9.5)
    for k, v in enumerate((c_real, c_rand)):
        ax.text(k, v + 0.03, "%.2f" % v, ha="center", fontsize=9)
    savefig(fig, CH, "fig6-8", out)
    return c_real, c_rand


# =========================================================================== figures 6.10-6.12
def fig_6_10(out=None):
    """Two-layer networks with three tanh hidden units fitted to x^2, sin, |x| and a step."""
    fig, axes = plt.subplots(2, 2, figsize=(6.4, 5.0))
    res = {}
    xx = np.linspace(-1, 1, 400)[:, None]
    for ax, fn, lab in zip(axes.ravel(), ("x2", "sin", "abs", "step"), "abcd"):
        X, T = approx_data(fn)
        net = TwoLayer(1, 3, 1, "tanh")
        w, E = fit_lbfgs(net, sse_error, X, T, starts=20, seed=10, sd1=2.0)
        res[fn] = math.sqrt(2 * E / len(X))
        _, z, a2 = net.forward(w, xx)
        lo, hi = T.min(), T.max()
        for j, c in enumerate((GREEN, MAGENTA, ORANGE)):
            ax.plot(xx[:, 0], lo + (hi - lo) * (z[:, j] + 1) / 2, "--", color=c, lw=1.1)
        ax.plot(xx[:, 0], a2[:, 0], color=RED, lw=1.8)
        ax.plot(X[:, 0], T[:, 0], "o", color=BLUE, ms=2.6)
        ax.set_xlim(-1, 1)
        pad = 0.08 * (hi - lo)
        ax.set_ylim(lo - pad, hi + pad)
        _box(ax)
        panel_label(ax, lab, "upper left" if fn != "x2" else "lower right")
    savefig(fig, CH, "fig6-10", out)
    return res


def fig11_data(seed=11, n=50):
    rng = np.random.default_rng(seed)
    blue = rng.normal([-0.6, 0.0], [0.7, 1.2], size=(n, 2))
    comp = rng.random(n) < 0.5
    red = np.where(comp[:, None], rng.normal([1.0, 1.2], [0.5, 0.6], size=(n, 2)), rng.normal([1.1, -0.9], [0.5, 0.6], size=(n, 2)))
    X = np.vstack([red, blue])
    t = np.concatenate([np.ones(n), np.zeros(n)])
    return X, t


def fig11_posterior(X):
    """True p(red | x) for the generating distributions of fig11_data (equal priors)."""
    from scipy.stats import norm
    pb = norm.pdf(X[:, 0], -0.6, 0.7) * norm.pdf(X[:, 1], 0.0, 1.2)
    pr = 0.5 * norm.pdf(X[:, 0], 1.0, 0.5) * norm.pdf(X[:, 1], 1.2, 0.6) + 0.5 * norm.pdf(X[:, 0], 1.1, 0.5) * norm.pdf(X[:, 1], -0.9, 0.6)
    return pr / (pr + pb)


def fig_6_11(out=None):
    """Two-class problem, network with two tanh hidden units and a logistic-sigmoid output."""
    X, t = fig11_data()
    net = TwoLayer(2, 2, 1, "tanh")
    w, E = fit_lbfgs(net, bce_error, X, t[:, None], starts=20, seed=3, sd1=1.0, wd=1e-3)
    g = np.linspace(-2.6, 2.6, 300)
    gx, gy = np.meshgrid(g, np.linspace(-2.6, 3.2, 300))
    P = np.stack([gx.ravel(), gy.ravel()], 1)
    a1, z, a2 = net.forward(w, P)
    fig, ax = plt.subplots(figsize=(4.6, 4.4))
    for j in range(2):
        ax.contour(gx, gy, a1[:, j].reshape(gx.shape), levels=[0], colors=BLUE, linestyles="--", linewidths=1)
    ax.contour(gx, gy, a2[:, 0].reshape(gx.shape), levels=[0], colors=RED, linewidths=1.6)
    ax.contour(gx, gy, fig11_posterior(P).reshape(gx.shape), levels=[0.5], colors=GREEN, linewidths=1.6)
    ax.plot(X[t == 1, 0], X[t == 1, 1], "x", color=RED, ms=5)
    ax.scatter(X[t == 0, 0], X[t == 0, 1], s=22, facecolors="none", edgecolors=BLUE, linewidths=1.1)
    ax.set_xlim(-2.6, 2.6)
    ax.set_ylim(-2.6, 3.2)
    savefig(fig, CH, "fig6-11", out)
    pred = (net.forward(w, X)[2][:, 0] > 0).astype(float)
    bayes = (fig11_posterior(X) > 0.5).astype(float)
    return {"train_err_net": float(np.mean(pred != t)), "train_err_bayes": float(np.mean(bayes != t))}


def fig_6_12(out=None):
    """Six activation functions: tanh, hard tanh, softplus, ReLU, leaky ReLU, absolute value."""
    a = np.linspace(-3, 3, 601)
    names = [("tanh", "tanh"), ("hardtanh", "hard tanh"), ("softplus", "softplus"), ("relu", "ReLU"), ("leaky", "leaky ReLU"), ("abs", "absolute")]
    fig, axes = plt.subplots(2, 3, figsize=(7.8, 4.6))
    for ax, (k, lab), pl in zip(axes.ravel(), names, "abcdef"):
        ax.axhline(0, color=GREY, lw=0.6)
        ax.axvline(0, color=GREY, lw=0.6)
        ax.plot(a, ACT[k][0](a), color=RED, lw=2)
        ax.set_xlim(-3, 3)
        ax.set_ylim(-3, 3)
        ax.set_xticks([-2.5, 0, 2.5])
        ax.set_yticks([-2.5, 0, 2.5])
        ax.set_title(lab)
        panel_label(ax, pl)
    fig.tight_layout()
    savefig(fig, CH, "fig6-12", out)


def fig_ex6_5(out=None):
    """Swish x sigma(beta x) and its derivative for beta = 0.1, 1, 10 (Exercise 6.5)."""
    x = np.linspace(-3, 3, 601)
    fig, axes = plt.subplots(1, 3, figsize=(8.0, 2.8))
    for ax, b, pl in zip(axes, (0.1, 1.0, 10.0), "abc"):
        h, dh = swish(x, b)
        ax.axhline(0, color=GREY, lw=0.6)
        ax.axvline(0, color=GREY, lw=0.6)
        ax.plot(x, np.maximum(x, 0), color=GREY, lw=1, ls=":", label="ReLU")
        ax.plot(x, h, color=RED, lw=2, label="swish")
        ax.plot(x, dh, color=BLUE, lw=1.4, ls="--", label="derivative")
        ax.set_title(r"$\beta = %g$" % b)
        ax.set_xlim(-3, 3)
        ax.set_ylim(-1.5, 3)
        panel_label(ax, pl)
    axes[0].legend(loc="upper left", bbox_to_anchor=(0.0, 0.88), frameon=False, fontsize=8)
    fig.tight_layout()
    savefig(fig, CH, "fig6-ex5", out)


def fig_approx_rate(out=None):
    """Constructive universal approximation of f(x) = sin(2 pi x) + 0.5 x on [0, 1]: maximum error of
    the sigmoid staircase network and of the ReLU interpolant against the number of hidden units."""
    f = lambda x: np.sin(2 * np.pi * np.asarray(x)) + 0.5 * np.asarray(x)  # noqa: E731
    xx = np.linspace(0, 1, 20001)
    ns = np.array([2, 4, 8, 16, 32, 64, 128, 256])
    e_sig = [np.abs(staircase_network(f, n, 40 * n)(xx) - f(xx)).max() for n in ns]
    e_relu = [np.abs(relu_interpolant(f, n)(xx) - f(xx)).max() for n in ns]
    fig, axes = plt.subplots(1, 2, figsize=(8.0, 3.2))
    ax = axes[0]
    ax.plot(xx, f(xx), color="k", lw=1, label="$f$")
    ax.plot(xx, staircase_network(f, 8, 320)(xx), color=RED, lw=1.5, label="sigmoid, 8 units")
    ax.plot(xx, relu_interpolant(f, 8)(xx), color=BLUE, lw=1.5, ls="--", label="ReLU, 8 units")
    ax.legend(frameon=False, fontsize=8, loc="lower left")
    ax.set_xlabel("$x$")
    panel_label(ax, "a", "upper right")
    ax = axes[1]
    ax.loglog(ns, e_sig, "o-", color=RED, label="sigmoid staircase")
    ax.loglog(ns, e_relu, "s-", color=BLUE, label="ReLU interpolant")
    ax.loglog(ns, 2 * np.pi / ns, ":", color=RED, lw=1, label=r"$\propto 1/M$")
    ax.loglog(ns, 6 / ns ** 2, ":", color=BLUE, lw=1, label=r"$\propto 1/M^2$")
    ax.set_xlabel("hidden units $M$")
    ax.set_ylabel("max error on [0, 1]")
    ax.legend(frameon=False, fontsize=8)
    panel_label(ax, "b", "lower left")
    fig.tight_layout()
    savefig(fig, CH, "fig6-approx-rate", out)
    return dict(zip(ns.tolist(), zip(e_sig, e_relu)))


# =========================================================================== Section 6.3 figure
def fig_relu_regions(out=None):
    """Linear regions of ReLU networks on [-1, 1]^2 with 24 hidden units: one layer of 24, three
    layers of 8, six layers of 4; the sawtooth (2^L pieces from 2L units); regions against depth."""
    cfgs = [((24,), "1 layer x 24"), ((8, 8, 8), "3 layers x 8"), ((4,) * 6, "6 layers x 4")]
    G = 300
    fig = plt.figure(figsize=(10.4, 5.6))
    gs = fig.add_gridspec(2, 3)
    counts = {}
    rng_col = np.random.default_rng(0)
    for i, (wd, lab) in enumerate(cfgs):
        net = DeepReLU(2, wd, seed=7)
        _, pre = net.forward(grid2(G))
        ids, _ = activation_patterns(pre)
        n = ids.max() + 1
        counts[lab] = int(n)
        cols = rng_col.random((n, 3)) * 0.55 + 0.4
        ax = fig.add_subplot(gs[0, i])
        ax.imshow(cols[ids].reshape(G, G, 3), extent=(-1, 1, -1, 1))
        ax.set_title("%s: %d regions" % (lab, n), fontsize=9.5)
        _box(ax)
        panel_label(ax, "abc"[i])
    ax = fig.add_subplot(gs[1, 0:2])
    xx = np.linspace(0, 1, 4001)
    for L, c in zip((1, 2, 3, 4), (GREY, BLUE, GREEN, RED)):
        ax.plot(xx, sawtooth(xx, L), color=c, lw=1.3, label="$L = %d$: %d pieces" % (L, 2 ** L))
    ax.set_xlabel("$x$")
    ax.legend(frameon=False, fontsize=8, ncol=4, loc="upper center", bbox_to_anchor=(0.5, 1.18))
    panel_label(ax, "d", "lower left")
    ax = fig.add_subplot(gs[1, 2])
    depths = [1, 2, 3, 4, 6]
    mean_cnt = []
    for L in depths:
        n = 24 // L
        mean_cnt.append(np.mean([count_regions(DeepReLU(2, (n,) * L, seed=s), G=150) for s in range(1, 9)]))
    ax.plot(depths, mean_cnt, "o-", color=BLUE, label="random init (mean of 8)")
    ax.axhline(shallow_bound(24, 2), color=GREY, ls=":", lw=1)
    ax.text(1.0, shallow_bound(24, 2) * 1.04, "shallow maximum %d" % shallow_bound(24, 2), fontsize=8, color=GREY)
    ax.set_xlabel("depth $L$ (24 units in total)")
    ax.set_ylabel("regions in $[-1,1]^2$")
    ax.set_ylim(0, shallow_bound(24, 2) * 1.2)
    panel_label(ax, "e", "lower left")
    fig.tight_layout()
    savefig(fig, CH, "fig6-relu-regions", out)
    counts["depth_means"] = dict(zip(depths, mean_cnt))
    return counts


# =========================================================================== figures 6.16-6.19
def _draw_arm(ax, t1, t2, color, ls="-", lw=4, alpha=1.0):
    ex, ey = ARM[0] * math.cos(t1), ARM[0] * math.sin(t1)
    x1, x2 = robot_forward(t1, t2)
    ax.plot([0, ex, x1], [0, ey, x2], ls, color=color, lw=lw, alpha=alpha, solid_capstyle="round")
    ax.plot([ex], [ey], "o", color=color, ms=4, alpha=alpha)


def fig_6_16(out=None):
    """The two-link arm: forward kinematics, and the two inverse solutions for one target."""
    fig, axes = plt.subplots(1, 2, figsize=(7.2, 3.0))
    t1, t2 = 1.95, 1.05
    ax = axes[0]
    _draw_arm(ax, t1, t2, RED)
    x1, x2 = robot_forward(t1, t2)
    ax.plot([x1], [x2], "o", color=BLUE, ms=9)
    ax.text(x1 + 0.06, x2, "$(x_1, x_2)$", va="center")
    ex, ey = ARM[0] * math.cos(t1), ARM[0] * math.sin(t1)
    ax.text(ex / 2 - 0.2, ey / 2, "$L_1$")
    ax.text((ex + x1) / 2 - 0.1, (ey + x2) / 2 + 0.12, "$L_2$")
    from matplotlib.patches import Arc
    ax.add_patch(Arc((0, 0), 0.5, 0.5, theta1=0, theta2=math.degrees(t1), color="k", lw=0.8))
    ax.text(0.3, 0.22, r"$\theta_1$")
    ax.add_patch(Arc((ex, ey), 0.36, 0.36, theta1=math.degrees(t1 + math.pi), theta2=math.degrees(t1 + math.pi + t2), color="k", lw=0.8))
    ax.text(ex + 0.12, ey - 0.25, r"$\theta_2$")
    panel_label(ax, "a", "upper right")
    ax = axes[1]
    sols = robot_inverse(x1, x2)
    _draw_arm(ax, *sols[0], RED)
    _draw_arm(ax, *sols[1], RED, ls="--", lw=2.5)
    ax.plot([x1], [x2], "o", color=BLUE, ms=9)
    ax.text(-0.95, 0.55, "elbow\nup", fontsize=9)
    ax.text(0.15, 0.3, "elbow\ndown", fontsize=9)
    panel_label(ax, "b", "upper right")
    for ax in axes:
        ax.plot([-1.2, 1.2], [0, 0], color="k", lw=2)
        ax.set_xlim(-1.2, 1.2)
        ax.set_ylim(-0.1, 1.55)
        ax.set_aspect("equal")
        ax.axis("off")
    savefig(fig, CH, "fig6-16", out)


def _toy_fit_sse(x, t, seed):
    net = TwoLayer(1, 6, 1, "tanh")
    w, E = fit_lbfgs(net, sse_error, x[:, None], t[:, None], starts=8, seed=seed, sd1=3.0, wd=0.01)
    return net, w


def fig_6_17(out=None):
    """Forward and inverse toy problems fitted by a sum-of-squares network with 6 tanh units."""
    x, t = toy_inverse_data()
    fig, axes = plt.subplots(1, 2, figsize=(7.0, 3.3))
    xx = np.linspace(0, 1, 400)
    for ax, (inp, out_), pl in zip(axes, ((x, t), (t, x)), "ab"):
        net, w = _toy_fit_sse(inp, out_, 17)
        ax.plot(inp, out_, "o", ms=3.5, mfc="none", mec=GREEN, mew=0.9)
        ax.plot(xx, net.forward(w, xx[:, None])[2][:, 0], color=RED, lw=1.8)
        ax.set_xlim(0, 1)
        ax.set_ylim(0, 1)
        ax.set_xticks([0, 1])
        ax.set_yticks([0, 1])
    savefig(fig, CH, "fig6-17", out)


def fit_toy_mdn(K=3, H=5, starts=8):
    """Mixture density network for the inverse toy problem (cached): x is the old t.

    A weight decay of 0.1 (on the summed error) keeps L-BFGS away from the spiky optima in which
    one component collapses onto a few points; it changes the error per point by less than 0.01."""
    path = _cache("ch06_toy_mdn_K%d_H%d.npz" % (K, H))
    x, t = toy_inverse_data()
    X, T = t[:, None], x[:, None]
    net = TwoLayer(1, H, 3 * K, "tanh")
    if os.path.exists(path):
        return net, np.load(path)["w"], X, T
    err = mdn_error(K, 1)
    w, E = fit_lbfgs(net, err, X, T, starts=starts, seed=19, sd1=3.0, maxiter=4000, wd=0.1)
    np.savez(path, w=w)
    return net, w, X, T


def fig_6_19(out=None):
    """Mixture density network (K = 3, five tanh units) on the inverse problem."""
    K = 3
    net, w, X, T = fit_toy_mdn(K)
    xx = np.linspace(0, 1, 300)
    a = net.forward(w, xx[:, None])[2]
    pi, sig, mu = mdn_split(a, K, 1)
    # order the components by their mean at x = 0 so the colours are stable
    order = np.argsort(mu[0, :, 0])[::-1]
    cols = [RED, GREEN, BLUE]
    fig, axes = plt.subplots(2, 2, figsize=(6.6, 6.0))
    ax = axes[0, 0]
    for c, k in zip(cols, order):
        ax.plot(xx, pi[:, k], color=c)
    ax = axes[0, 1]
    for c, k in zip(cols, order):
        ax.plot(xx, mu[:, k, 0], color=c)
    ax = axes[1, 0]
    tt = np.linspace(0, 1, 300)
    gx, gt = np.meshgrid(xx, tt)
    lc = mdn_logcomp(np.repeat(a, len(tt), axis=0), np.tile(tt, len(xx)), K, 1)[0]
    dens = np.exp(common.logsumexp(lc, axis=1)).reshape(len(xx), len(tt)).T
    ax.contour(gx, gt, dens, levels=np.geomspace(0.4, 0.9 * dens.max(), 9), cmap="viridis", linewidths=0.9)
    ax = axes[1, 1]
    ax.plot(X[:, 0], T[:, 0], "o", ms=3.5, mfc="none", mec=GREEN, mew=0.9)
    kbest = np.argmax(pi, axis=1)
    xm = np.linspace(0, 1, 120)
    am = net.forward(w, xm[:, None])[2]
    pim, _, mum = mdn_split(am, K, 1)
    ax.plot(xm, mum[np.arange(len(xm)), np.argmax(pim, 1), 0], "o", color=RED, ms=2.6)
    for ax, pl in zip(axes.ravel(), "abcd"):
        ax.set_xlim(0, 1)
        ax.set_ylim(0, 1)
        ax.set_xticks([0, 1])
        ax.set_yticks([0, 1])
        ax.set_title("(%s)" % pl, y=-0.2, fontsize=10)
    fig.tight_layout()
    savefig(fig, CH, "fig6-19", out)
    E = mdn_error(K, 1)(net, w, X, T)[0]
    return {"nll_per_point": E / len(X)}


ROBOT = dict(N=400, seed_data=5, seed_w=3, H=16, lr=0.02, steps=3000)


def fit_robot(K=2, sse=False):
    """The robot-arm networks of the demo, trained with the demo's Adam settings (cached)."""
    tag = "sse" if sse else "K%d" % K
    path = _cache("ch06_robot_%s.npz" % tag)
    if os.path.exists(path):
        d = np.load(path)
        net = TwoLayer(2, ROBOT["H"], 2 if sse else 4 * K, "tanh")
        return float(d["E"]), d["w"], net
    E, w, net = robot_demo_run(K, ROBOT["H"], ROBOT["seed_data"], ROBOT["seed_w"], ROBOT["lr"], ROBOT["steps"], ROBOT["N"], sse=sse)
    np.savez(path, w=w, E=E)
    return E, w, net


def fig_robot_mdn(out=None):
    """Inverse kinematics of the arm: sum-of-squares network against a two-component MDN."""
    Es, ws, nets = fit_robot(sse=True)
    Em, wm, netm = fit_robot(K=2)
    targets = [(-0.3, 1.3), (0.5, 1.0), (-0.8, 0.8)]
    fig, axes = plt.subplots(1, 2, figsize=(8.4, 3.3))
    for ax, which in zip(axes, ("sse", "mdn")):
        for (x1, x2), c in zip(targets, (RED, BLUE, PURPLE)):
            if which == "sse":
                th = nets.forward(ws, np.array([[x1, x2]]))[2][0]
                _draw_arm(ax, th[0], th[1], c, lw=2.5)
            else:
                pi, sig, mu = mdn_split(netm.forward(wm, np.array([[x1, x2]]))[2], 2, 2)
                for k in range(2):
                    _draw_arm(ax, mu[0, k, 0], mu[0, k, 1], c, lw=2.5, alpha=0.25 + 0.75 * pi[0, k])
            ax.plot([x1], [x2], "o", color=c, ms=9, mfc="none", mew=2)
        ax.plot([-1.7, 1.7], [0, 0], color="k", lw=2)
        ax.set_xlim(-1.7, 1.7)
        ax.set_ylim(-0.1, 1.75)
        ax.set_aspect("equal")
        ax.axis("off")
        ax.set_title("sum-of-squares network" if which == "sse" else "mixture density network, K = 2", fontsize=10)
    savefig(fig, CH, "fig6-robot-mdn", out)
    return {"sse": Es, "mdn": Em}


# =========================================================================== demo data
def export_demo_data(out=None):
    """The Iris measurements for the grid-classifier panel of the geometry demo."""
    X, y = iris_sepal()
    os.makedirs(DATA_OUT, exist_ok=True)
    path = os.path.join(DATA_OUT, "ch06-iris.json")
    with open(path, "w") as f:
        json.dump({"source": "Iris data (Fisher 1936), as distributed with scikit-learn",
                   "features": ["sepal length", "sepal width", "petal length", "petal width"],
                   "species": ["setosa", "versicolor", "virginica"],
                   "X": np.round(X, 2).tolist(), "y": y.tolist()}, f, separators=(",", ":"))
    print("wrote", os.path.relpath(path, os.getcwd()))


FIGURES = {
    "6.1": fig_6_1, "6.2": fig_6_2, "6.3": fig_6_3, "6.4": fig_6_4, "6.5": fig_6_5, "6.6": fig_6_6,
    "6.7": fig_6_7, "6.8": fig_6_8, "6.10": fig_6_10, "6.11": fig_6_11, "6.12": fig_6_12,
    "ex6.5": fig_ex6_5, "approx-rate": fig_approx_rate, "relu-regions": fig_relu_regions,
    "6.16": fig_6_16, "6.17": fig_6_17, "6.19": fig_6_19, "robot-mdn": fig_robot_mdn,
    "data": export_demo_data,
}

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