"""Hastie, Tibshirani and Friedman (2009), Chapter 11: Neural Networks.

Reproduces the figures of Chapter 11 of T. Hastie, R. Tibshirani and J. Friedman, The Elements of
Statistical Learning, 2nd edition (Springer, 2009), pp. 389-416, written from scratch with numpy,
scipy, matplotlib and (for the convolutional ZIP code networks only) PyTorch. Every method the
chapter is about is implemented here as a small function meant to be read next to the lecture
notes (../ch11-neural-networks.html):

* Rng: the seeded generator (mulberry32 uniforms, Box-Muller normals rounded to 8 decimals) shared
  with the browser demonstrations, so that page and code draw the same simulated data and the
  same random starting weights.
* Section 11.2, projection pursuit regression: bspline_design and RidgeSmoother (a penalised cubic
  spline with the smoothing-spline penalty and fixed degrees of freedom, with derivatives),
  ppr_single (alternating smoothing and the Gauss-Newton step (11.3)-(11.4) with step halving),
  ppr_fit (forward stagewise terms with backfitting of the ridge functions), ppr_predict.
* Sections 11.3-11.4, the single-hidden-layer network (11.5): class Net (sum-of-squares or
  softmax/cross-entropy outputs, weight decay (11.16) on all weights, gradients by
  back-propagation (11.12)-(11.15)); vmmin, the variable-metric (BFGS) minimiser with the
  backtracking line search of Nash (1990) that R's optim and the nnet package use (it reproduces
  nnet's fits from the same starting weights); backprop_gd, plain batch back-propagation (11.13).
* Section 11.5.2: the mixture example of Chapter 2 (mixture, mixture_nets, mixture_errors).
* Section 11.6: the sum-of-sigmoids and radial models (sim_data, var_sigmoid_model,
  radial_moments) and the experiments over hidden units, weight decay and ten random starts
  (sim_experiment, sim_results; cached in cache/).
* Section 11.7: the five ZIP code networks of Le Cun (1989) (zip_layers, zip_counts, zip_torch_net
  with locally connected and weight-shared layers, zip_train by on-line back-propagation,
  zip_forward_np), at CPU scale (zip_subsets).
* Section 11.9: a Bayesian neural network (BayesNet: two hidden layers, ARD priors, hybrid Monte
  Carlo for the weights and Gibbs steps for the precisions), boosted networks (boosted_nets),
  and the comparison of Section 11.9.2 on a small Madelon-like problem (nips_data, nips_results).
* Exercises 11.5-11.7: ex5_data, ex5_results (back-propagation curves, hidden units, PPR terms),
  spam_data, spam_gam (the additive model of Section 9.1.2, fitted with R's gam package),
  spam_results.

Figures reproduced: 11.1, 11.3, 11.4, 11.5, 11.6, 11.7, 11.8, 11.9 and 11.11, plus seven
supplementary figures: 11.S1 (averaging the predictions of ten starts against the best start and
against averaged weights, Section 11.5.5), 11.S2 (two-term projection pursuit fit, Section 11.2),
11.S3 and 11.S4 (Bayesian, boosted and bagged networks, boosted trees and random forests with
screened and ARD-selected features, and what screening and ARD see; Section 11.9, standing in for
Figure 11.12), 11.S5 and 11.S6 (Exercises 11.5 and 11.6) and 11.S7 (Exercise 11.7). Run
`python3 ch11_neural_networks.py --list`, `python3 ch11_neural_networks.py` (all figures; about
12 minutes the first time, seconds afterwards, as the slow fits are cached in cache/) or
`python3 ch11_neural_networks.py --fig 11.6`. Files go to ../img/ch11/; export_demo_data()
(called with Figure 11.11) writes the data the browser demonstrations use to ../data/.

Figures not reproduced, and why:
* Figures 11.2 and 11.10 are schematic diagrams of network architectures (nothing is computed);
  the five architectures of Figure 11.10 are drawn live in the ZIP code demonstration.
* Figure 11.12 shows the published test errors of entries to the NIPS 2003 challenge on its five
  data sets, rerun by the book's authors with programs and computing time not available here.
  Figures 11.S3 and 11.S4 repeat the comparison at CPU scale on one simulated Madelon-like problem.

Settings chosen where the book gives none:
* Networks of Sections 11.5-11.6 are fitted like nnet: logistic hidden units, criterion RSS (or
  cross-entropy) plus lambda times the sum of all squared weights (biases included), starting
  weights uniform on [-0.7, 0.7], BFGS with nnet's tolerances (abstol 1e-4, reltol 1e-8). Section
  11.6 runs to convergence (at most 5000 iterations; nnet's default limit of 100 stops many fits
  early); Figure 11.4 uses at most 500 iterations and keeps the best of ten starts.
* Section 11.6: N = 100 training and 10,000 test points; noise variance Var f / 4 (SNR 4); the radial
  function prod phi(X_m) has variance about 3e-11, so it is rescaled to unit variance before the
  noise is added (relative errors are unchanged by rescaling; without it any weight decay shrinks
  the network to a constant). Seeds: Rng(1106)/(1107) and Rng(1108)/(1109); starting weights for M
  hidden units and start s from Rng(7000 + 100 M + s). The test error is reported relative to
  sigma^2 as 1 + mean (f - f_hat)^2 / sigma^2 over the test inputs.
* Figure 11.4: ten hidden units, softmax outputs, cross-entropy, decay 0 and 0.02, the raw inputs.
* Section 11.7: Le Cun's 320/160 digit set is not distributed with the book. As in his set,
  digits are shifted horizontally at random (-2 to 2 pixels): 160 digits of zip.train (16 per
  class) each appear twice with independent shifts (320 training images); every digit of
  zip.test is shifted once (2007 test images). tanh hidden units, logistic outputs, squared error
  on 0/1 targets, starting weights uniform on +-2.4/fan-in, on-line back-propagation with learning
  rate 0.05 for 30 epochs, five runs per network. Inputs are padded with -1 (background).
* Section 11.9: 500 training and 2000 test cases, 100 features (5 informative, 10 linear
  combinations, 85 probes); screening keeps the 20 largest |t|; the Bayesian network has hidden
  layers of 20 and 8 tanh units, Gamma(0.5, 0.05) hyperpriors on the precisions, 1000 hybrid Monte
  Carlo iterations of 40 leapfrog steps (500 burn-in, every second kept); ARD keeps the inputs whose
  posterior median sigma_j exceeds half the largest.
* Exercise 11.5: the response is standardised for training; batch back-propagation with learning
  rate 0.001 for 100,000 epochs; part (c) fits 1-10 units to convergence with decay 1e-4, best of
  five starts. Exercise 11.6: smoothers with 5, 8, 12 and 16 df, 1-4 terms. Exercise 11.7: inputs
  log(x + 0.1), standardised; ten units, softmax; decay chosen by five-fold cross-validation.
"""
import json
import math
import os

import numpy as np

import common
from common import BLUE, GREEN, GREY, MAGENTA, ORANGE, PURPLE, RED, savefig

CH = 11
HERE = os.path.dirname(os.path.abspath(__file__))
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
CACHE_DIR = os.path.join(HERE, "cache")
os.makedirs(CACHE_DIR, exist_ok=True)


# =========================================================================== random numbers
class Rng:
    """mulberry32 uniforms and Box-Muller normals.

    The same generator runs in the browser demonstrations, so a page and this module draw
    exactly the same simulated data and the same random starting weights from the same seed.
    Normal variates are rounded to 8 decimals (half up), which removes the last-bit
    differences between the two languages' log and cos functions.
    """
    M32 = 0xFFFFFFFF

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

    def u(self):
        M = self.M32
        a = (self.a + 0x6D2B79F5) & M
        self.a = a
        t = ((a ^ (a >> 15)) * (1 | a)) & M
        t = ((t + (((t ^ (t >> 7)) * (61 | t)) & M)) & M) ^ t
        return ((t ^ (t >> 14)) & M) / 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 = r8(r * math.sin(th))
        return r8(r * math.cos(th))

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

    def uniforms(self, n, lo=0.0, hi=1.0):
        return np.array([lo + (hi - lo) * self.u() for _ in range(n)])


def r8(x):
    """Round half up to 8 decimals (the browser uses Math.round(x * 1e8) / 1e8)."""
    return math.floor(x * 1e8 + 0.5) / 1e8


def start_weights(n, seed, rang=0.7):
    """n starting weights uniform on [-rang, rang] (Section 11.5.3), from Rng(seed)."""
    g = Rng(seed)
    return np.array([rang * (2.0 * g.u() - 1.0) for _ in range(n)])


def sigmoid(v):
    v = np.asarray(v, dtype=float)
    out = np.empty_like(v)
    pos = v >= 0
    out[pos] = 1.0 / (1.0 + np.exp(-v[pos]))
    e = np.exp(v[~pos])
    out[~pos] = e / (1.0 + e)
    return out


# =========================================================================== quasi-Newton (BFGS)
def vmmin(fn, gr, b0, maxit=100, abstol=1e-4, reltol=1e-8):
    """Variable-metric (BFGS) minimiser with a backtracking line search.

    This is the algorithm of Nash (1990, Algorithm 21), the one R's optim(method = "BFGS") and the
    nnet package use: the inverse Hessian approximation B starts at the identity, the step along
    t = -B g is shrunk by 0.2 until the Armijo condition with constant 1e-4 holds, B gets the BFGS
    update when the curvature t'c is positive and is reset to the identity otherwise, and the
    run stops when the relative decrease of the objective falls below reltol, the objective
    falls below abstol, or after maxit iterations. Returns (b, f, iterations, converged).
    """
    b = np.array(b0, dtype=float)
    n = b.size
    f = fn(b)
    if not np.isfinite(f):
        raise ValueError("initial value is not finite")
    fmin = f
    g = gr(b)
    it = 1
    funcount = gradcount = 1
    ilast = gradcount
    B = np.eye(n)
    while True:
        if ilast == gradcount:
            B = np.eye(n)
        X = b.copy()
        c = g.copy()
        t = -B @ g
        gradproj = float(t @ g)
        if gradproj < 0.0:
            steplength = 1.0
            accpoint = False
            while True:
                b = X + steplength * t
                count = int(np.sum(10.0 + X == 10.0 + b))
                if count < n:
                    f = fn(b)
                    funcount += 1
                    accpoint = np.isfinite(f) and f <= fmin + gradproj * steplength * 1e-4
                    if not accpoint:
                        steplength *= 0.2
                if count == n or accpoint:
                    break
            enough = (f > abstol) and abs(f - fmin) > reltol * (abs(fmin) + reltol)
            if not enough:
                count = n
                fmin = f
            if count < n:
                fmin = f
                g = gr(b)
                gradcount += 1
                it += 1
                t = steplength * t
                c = g - c
                D1 = float(t @ c)
                if D1 > 0:
                    Xv = B @ c
                    D2 = 1.0 + float(Xv @ c) / D1
                    B = B + (D2 * np.outer(t, t) - np.outer(Xv, t) - np.outer(t, Xv)) / D1
                else:
                    ilast = gradcount
            else:
                if ilast < gradcount:
                    count = 0
                    ilast = gradcount
        else:
            count = 0
            if ilast == gradcount:
                count = n
            else:
                ilast = gradcount
        if it >= maxit:
            break
        if gradcount - ilast > 2 * n:
            ilast = gradcount
        if count == n and ilast == gradcount:
            break
    return b, fmin, it, it < maxit


# =========================================================================== single-hidden-layer network (11.5)
class Net:
    """The single-hidden-layer network (11.5) with logistic hidden units.

    Weights are stored in one vector in the order the nnet package uses: for each hidden unit m its
    bias alpha_0m and input weights alpha_m; then for each output k its bias beta_0k and hidden
    weights beta_k. out = "linear" gives g_k(T) = T_k with the sum-of-squares error (11.9);
    out = "softmax" gives (11.6) with the cross-entropy (11.10). M = 0 means no hidden layer
    (outputs are linear in the inputs: least squares, or multinomial logistic regression).
    The fitting criterion is R(theta) + lambda J(theta) with J the sum of all squared weights,
    biases included (11.16), as in nnet.
    """

    def __init__(self, p, M, K=1, out="linear"):
        self.p, self.M, self.K, self.out = p, M, K, out
        self.nw = M * (p + 1) + K * ((M if M > 0 else p) + 1)

    def unpack(self, w):
        p, M, K = self.p, self.M, self.K
        if M == 0:
            return None, w.reshape(K, p + 1)
        A = w[: M * (p + 1)].reshape(M, p + 1)
        Bm = w[M * (p + 1):].reshape(K, M + 1)
        return A, Bm

    def forward(self, w, X):
        A, Bm = self.unpack(w)
        if A is None:
            Z = X
        else:
            Z = sigmoid(A[:, 0] + X @ A[:, 1:].T)
        T = Bm[:, 0] + Z @ Bm[:, 1:].T
        if self.out == "softmax":
            T = T - T.max(1, keepdims=True)
            E = np.exp(T)
            F = E / E.sum(1, keepdims=True)
        else:
            F = T
        return Z, F

    def predict(self, w, X):
        return self.forward(w, X)[1]

    def loss(self, w, X, Y, lam):
        F = self.predict(w, X)
        if self.out == "softmax":
            R = -np.sum(Y * np.log(np.maximum(F, 1e-300)))
        else:
            R = np.sum((Y - F) ** 2)
        return float(R + lam * np.sum(w * w))

    def grad(self, w, X, Y, lam):
        """Back-propagation (11.12)-(11.15): output errors delta_ki, hidden errors s_mi."""
        A, Bm = self.unpack(w)
        Z, F = self.forward(w, X)
        D = (F - Y) if self.out == "softmax" else -2.0 * (Y - F)     # delta_ki (N x K)
        gB = np.column_stack([D.sum(0), D.T @ Z])                    # dR/dbeta_0k, dR/dbeta_km
        if A is None:
            g = gB.ravel()
        else:
            S = (D @ Bm[:, 1:]) * Z * (1 - Z)                         # s_mi = sigma' sum_k beta_km delta_ki
            gA = np.column_stack([S.sum(0), S.T @ X])
            g = np.concatenate([gA.ravel(), gB.ravel()])
        return g + 2.0 * lam * w

    def fit(self, X, Y, lam=0.0, w0=None, seed=1, rang=0.7, maxit=100, abstol=1e-4, reltol=1e-8):
        Y = np.asarray(Y, dtype=float)
        if Y.ndim == 1:
            Y = Y[:, None]
        if w0 is None:
            w0 = start_weights(self.nw, seed, rang)
        w, f, it, conv = vmmin(lambda v: self.loss(v, X, Y, lam), lambda v: self.grad(v, X, Y, lam),
                               w0, maxit=maxit, abstol=abstol, reltol=reltol)
        self.w, self.value, self.iters, self.converged = w, f, it, conv
        return self


def fit_net(X, y, M, lam, seed, maxit=500, out="linear", K=1):
    """Convenience wrapper: one network fit from the starting weights of Rng(seed)."""
    net = Net(X.shape[1], M, K=K, out=out)
    return net.fit(X, y, lam=lam, seed=seed, maxit=maxit)


# =========================================================================== Section 11.6: simulated data
SIM_SEEDS = {"sigmoid": (1106, 1107), "radial": (1108, 1109)}
SIM_N, SIM_NTEST = 100, 10000
A1, A2 = np.array([3.0, 3.0]), np.array([3.0, -3.0])


def var_sigmoid_model():
    """Var f(X) for f = sigma(a1'X) + sigma(a2'X), X ~ N(0, I_2), a1 = (3,3), a2 = (3,-3).

    a1'X and a2'X are independent N(0, 18), so Var f = 2 Var sigma(3 sqrt(2) Z) =
    2 (E sigma(3 sqrt(2) Z)^2 - 1/4), by symmetry of sigma about 1/2."""
    from scipy.integrate import quad
    c = 3.0 * math.sqrt(2.0)
    e2 = quad(lambda z: (1.0 / (1.0 + math.exp(-c * z))) ** 2 * math.exp(-0.5 * z * z) / math.sqrt(2 * math.pi),
              -12, 12, epsabs=1e-14, epsrel=1e-14, limit=200)[0]
    return 2.0 * (e2 - 0.25)


def radial_moments():
    """Mean and variance of f(X) = prod_{m=1}^{10} phi(X_m), X ~ N(0, I_10) (closed form).

    E phi(X) = int phi^2 = 1/(2 sqrt(pi)); E phi(X)^2 = int phi^3 = 1/(2 pi sqrt(3))."""
    m1 = 1.0 / (2.0 * math.sqrt(math.pi))
    m2 = 1.0 / (2.0 * math.pi * math.sqrt(3.0))
    return m1 ** 10, m2 ** 10 - m1 ** 20


def sim_f(model, X):
    if model == "sigmoid":
        return sigmoid(X @ A1) + sigmoid(X @ A2)
    phi = np.exp(-0.5 * X * X) / math.sqrt(2 * math.pi)
    _, v = radial_moments()
    return np.prod(phi, axis=1) / math.sqrt(v)       # rescaled to unit variance (see the notes)


def sim_data(model):
    """Training set (N = 100) and test inputs (10,000) for the two models of Section 11.6.

    Sum of sigmoids: p = 2, Y = sigma(a1'X) + sigma(a2'X) + eps. Radial: p = 10,
    Y = prod phi(X_m) / sd + eps, the radial function rescaled to unit variance. In both, the
    noise variance is Var f / 4 (signal-to-noise ratio (11.18) equal to 4). Returns a dict with
    X, y, f (training), Xte, fte (test inputs and true means) and the noise variance s2."""
    p = 2 if model == "sigmoid" else 10
    s_tr, s_te = SIM_SEEDS[model]
    vf = var_sigmoid_model() if model == "sigmoid" else 1.0
    s2 = vf / 4.0
    g = Rng(s_tr)
    X = g.normals(SIM_N * p).reshape(SIM_N, p)
    f = sim_f(model, X)
    y = f + math.sqrt(s2) * g.normals(SIM_N)
    gt = Rng(s_te)
    Xte = gt.normals(SIM_NTEST * p).reshape(SIM_NTEST, p)
    return dict(model=model, p=p, X=X, y=y, f=f, Xte=Xte, fte=sim_f(model, Xte), s2=s2, varf=vf)


def start_seed(M, start):
    """Seed of the starting weights for a network with M hidden units, start = 1..10."""
    return 7000 + 100 * M + start


def rel_test_error(net, D, w=None):
    """Expected test error relative to the Bayes error: 1 + mean (f - f_hat)^2 / sigma^2 over
    the 10,000 test inputs (the noise of a test response adds sigma^2 to the squared error)."""
    fh = net.predict(net.w if w is None else w, D["Xte"])[:, 0]
    return 1.0 + float(np.mean((D["fte"] - fh) ** 2)) / D["s2"]


# =========================================================================== Section 11.5.2: the mixture example
def mixture():
    """The simulated mixture data of Chapter 2 (ESL.mixture.rda from the book's website), read
    once with Rscript and cached: x (200 x 2), y, the grid xnew with the true probabilities prob
    and the marginal density, the grid axes px1, px2."""
    path = os.path.join(CACHE_DIR, "ch11_mixture.npz")
    if not os.path.exists(path):
        import subprocess
        import tempfile
        rda = common.esl_file("ESL.mixture.rda")
        tmp = tempfile.mkdtemp()
        code = ('load("%s"); m <- ESL.mixture; for (nm in c("x","y","xnew","prob","marginal","px1","px2")) '
                'write.table(as.matrix(m[[nm]]), file.path("%s", paste0(nm, ".csv")), sep=",", row.names=FALSE, col.names=FALSE)'
                % (rda, tmp))
        subprocess.check_call(["/usr/local/bin/Rscript", "-e", code])
        arrs = {nm: np.loadtxt(os.path.join(tmp, nm + ".csv"), delimiter=",")
                for nm in ("x", "y", "xnew", "prob", "marginal", "px1", "px2")}
        np.savez(path, **arrs)
    z = np.load(path)
    return {k: z[k] for k in z.files}


def mixture_errors(pred_class, m):
    """Training error, test error and Bayes error of a classifier on the mixture data. The test
    error integrates the true conditional probability over the marginal density on the grid."""
    tr = float(np.mean(pred_class(m["x"]) != m["y"]))
    pg = pred_class(m["xnew"])
    wts = m["marginal"] / m["marginal"].sum()
    test = float(np.sum(wts * np.where(pg == 1, 1 - m["prob"], m["prob"])))
    bayes = float(np.sum(wts * np.minimum(m["prob"], 1 - m["prob"])))
    return tr, test, bayes


# =========================================================================== Section 11.2: projection pursuit regression
def bspline_design(v, knots, deriv=0):
    """Cubic B-spline basis (and its derivatives) at the points v for the full knot vector
    `knots` (boundary knots repeated four times), by the Cox-de Boor recursion. Points outside
    the boundary knots are not handled here (see RidgeSmoother.eval)."""
    v = np.asarray(v, dtype=float)
    t = np.asarray(knots, dtype=float)
    nb = len(t) - 4
    # degree-0 indicator functions on [t_i, t_{i+1}), with the last nonempty interval closed
    last = np.max(np.nonzero(t[1:] > t[:-1])[0])
    B = np.zeros((v.size, len(t) - 1))
    for i in range(len(t) - 1):
        if t[i + 1] > t[i]:
            B[:, i] = (v >= t[i]) & ((v < t[i + 1]) | ((i == last) & (v == t[i + 1])))
    for k in range(1, 4):
        Bn = np.zeros((v.size, len(t) - 1 - k))
        for i in range(len(t) - 1 - k):
            d1, d2 = t[i + k] - t[i], t[i + k + 1] - t[i + 1]
            a = np.zeros(v.size) if d1 == 0 else (v - t[i]) / d1 * B[:, i]
            b = np.zeros(v.size) if d2 == 0 else (t[i + k + 1] - v) / d2 * B[:, i + 1]
            if deriv > 0 and k > 3 - deriv:
                # derivative step: B'_{i,k} = k [B_{i,k-1}/d1 - B_{i+1,k-1}/d2]
                a = np.zeros(v.size) if d1 == 0 else k / d1 * B[:, i]
                b = np.zeros(v.size) if d2 == 0 else -k / d2 * B[:, i + 1]
            Bn[:, i] = a + b
        B = Bn
    return B[:, :nb]


class RidgeSmoother:
    """Penalised cubic regression spline with the smoothing-spline penalty int g''(v)^2 dv.

    nk equally spaced interior knots over the range of v (a reduced knot set, as R's
    smooth.spline uses for larger N); the penalty is fixed by the effective degrees of freedom
    df = trace S (found by bisection on log lambda). The fit is centred to mean zero over the
    training points. Outside the range of the training v the function continues linearly.
    """

    def __init__(self, df=5.0, nk=10):
        self.df, self.nk = float(df), int(nk)

    def fit(self, v, r):
        v = np.asarray(v, float)
        vs = np.sort(v)
        n = len(vs)
        lo, hi = float(vs[0]), float(vs[-1])
        # interior knots at equally spaced ranks of the data, so every knot interval holds data
        inner = [float(vs[int(math.floor((j + 1) * (n - 1) / (self.nk + 1) + 0.5))]) for j in range(self.nk)]
        self.knots = np.array([lo] * 4 + inner + [hi] * 4)
        self.lo, self.hi = lo, hi
        B = bspline_design(v, self.knots)
        nb = B.shape[1]
        # Omega_jk = int B_j'' B_k'': B'' is linear between knots, so Simpson's rule is exact
        brk = np.array([lo] + inner + [hi])
        a, b = brk[:-1], brk[1:]
        eps = 1e-12 * (b - a)
        pts = np.column_stack([a + eps, 0.5 * (a + b), b - eps]).ravel()
        D2 = bspline_design(pts, self.knots, deriv=2)
        wq = (np.repeat((b - a) / 6.0, 3) * np.tile([1.0, 4.0, 1.0], len(a)))
        Om = D2.T @ (wq[:, None] * D2)
        BtB = B.T @ B
        scale = np.trace(BtB) / np.trace(Om)
        target = min(max(self.df, 2.0001), nb - 1e-3)

        def dfof(lr):
            A = BtB + math.exp(lr) * scale * Om
            return float(np.trace(np.linalg.solve(A, BtB)))
        a, b = -25.0, 25.0
        for _ in range(80):
            mid = 0.5 * (a + b)
            if dfof(mid) > target:
                a = mid
            else:
                b = mid
        self.lam = math.exp(0.5 * (a + b)) * scale
        A = BtB + self.lam * Om
        self.coef = np.linalg.solve(A, B.T @ r)
        self.dfit = float(np.trace(np.linalg.solve(A, BtB)))
        self.shift = float(np.mean(B @ self.coef))
        return self

    def eval(self, v, deriv=0):
        v = np.asarray(v, float)
        vc = np.clip(v, self.lo, self.hi)
        g = bspline_design(vc, self.knots) @ self.coef - self.shift
        g1 = bspline_design(vc, self.knots, deriv=1) @ self.coef
        if deriv == 1:
            return g1
        return g + g1 * (v - vc)            # linear continuation outside the data


def unit(w):
    w = np.asarray(w, float)
    w = w / np.linalg.norm(w)
    k = 0 if abs(w[0]) > 1e-12 else 1
    return w if w[k] >= 0 else -w


def ppr_single(X, r, w0, df=5.0, maxit=30, tol=1e-8):
    """One ridge term: alternate the smoother for g given omega and the Gauss-Newton step
    (11.3)-(11.4) for omega given g, with step halving. Returns omega, the smoother, the RSS and
    the path of directions (for the demonstrations)."""
    w = unit(w0)
    g = RidgeSmoother(df).fit(X @ w, r)
    rss = float(np.sum((r - g.eval(X @ w)) ** 2))
    path = [w.copy()]
    for it in range(maxit):
        v = X @ w
        gv, d = g.eval(v), g.eval(v, deriv=1)
        # weighted least squares: target v_i + (r_i - g(v_i))/g'(v_i), weights g'(v_i)^2, no intercept
        Xd = X * d[:, None]
        rhs = d * v + (r - gv)
        try:
            wn = np.linalg.solve(Xd.T @ Xd, Xd.T @ rhs)
        except np.linalg.LinAlgError:
            break
        if not np.all(np.isfinite(wn)) or np.linalg.norm(wn) < 1e-12:
            break
        wn = unit(wn)
        if wn @ w < 0:
            wn = -wn
        h, accepted = 1.0, False
        for _ in range(12):
            wt = unit(w + h * (wn - w))
            gt = RidgeSmoother(df).fit(X @ wt, r)
            rt = float(np.sum((r - gt.eval(X @ wt)) ** 2))
            if rt < rss:
                accepted = True
                break
            h *= 0.5
        if not accepted:
            break
        done = (rss - rt) <= tol * rss
        w, g, rss = wt, gt, rt
        path.append(w.copy())
        if done:
            break
    return dict(w=w, g=g, rss=rss, path=path, iters=len(path) - 1)


def ppr_starts(X, r):
    """Starting directions: the least-squares direction of r on X, then (for p = 2) eight angles
    k pi / 8 on the half circle, or (for p > 2) the coordinate axes."""
    p = X.shape[1]
    Xc = np.column_stack([np.ones(len(r)), X])
    b = np.linalg.lstsq(Xc, r, rcond=None)[0][1:]
    out = [b] if np.linalg.norm(b) > 1e-8 else []
    if p == 2:
        out += [np.array([math.cos(k * math.pi / 8), math.sin(k * math.pi / 8)]) for k in range(8)]
    else:
        out += [np.eye(p)[j] for j in range(p)]
    return out


def ppr_fit(X, y, M=2, df=5.0, backfit=True, starts=None, maxit=30, nback=20, first_start=None):
    """Projection pursuit regression (11.1) by forward stagewise fitting of M ridge terms.

    Term m is fitted to the residuals of terms 1..m-1 from each starting direction (the lowest RSS
    wins); then, if backfit, the ridge functions g_1..g_m are readjusted by backfitting with the
    directions held fixed (Section 11.2). first_start, if given, is the only starting direction
    of the first term. Returns a dict with the mean, directions and smoothers."""
    ybar = float(np.mean(y))
    terms = []
    fitted = np.zeros(len(y))
    for m in range(M):
        r = y - ybar - fitted
        best = None
        cand = [first_start] if (m == 0 and first_start is not None) else (starts if starts is not None else ppr_starts(X, r))
        for w0 in cand:
            res = ppr_single(X, r, w0, df=df, maxit=maxit)
            if best is None or res["rss"] < best["rss"] - 1e-12:
                best = res
        terms.append(best)
        if backfit and m > 0:
            for _ in range(nback):
                change = 0.0
                for k, tk in enumerate(terms):
                    others = sum(tj["g"].eval(X @ tj["w"]) for j, tj in enumerate(terms) if j != k)
                    old = tk["g"].eval(X @ tk["w"])
                    tk["g"] = RidgeSmoother(df).fit(X @ tk["w"], y - ybar - others)
                    change = max(change, float(np.max(np.abs(tk["g"].eval(X @ tk["w"]) - old))))
                if change < 1e-8:
                    break
        fitted = sum(tk["g"].eval(X @ tk["w"]) for tk in terms)
    return dict(ybar=ybar, terms=terms, rss=float(np.sum((y - ybar - fitted) ** 2)))


def ppr_predict(fit, X):
    return fit["ybar"] + sum(t["g"].eval(X @ t["w"]) for t in fit["terms"])


PPR_DEMO = {"single": (1123, 1124, 0.1), "product": (1121, 1122, 0.2)}


def ppr_demo_data(name):
    """Data of the projection pursuit demonstration (N = 100, X ~ N(0, I_2)): 'single', the ridge
    function on the left of Figure 11.1 plus N(0, 0.1^2) noise; 'product', X1 X2 plus N(0, 0.2^2);
    'ex115', the model of Exercise 11.5; 'sigmoids', the sum of sigmoids of Section 11.6."""
    if name == "ex115":
        D = ex5_data()
        return dict(X=D["X"], y=D["y"], Xte=D["Xte"], fte=D["fte"], s2=0.09)
    if name == "sigmoids":
        D = sim_data("sigmoid")
        return dict(X=D["X"], y=D["y"], Xte=D["Xte"], fte=D["fte"], s2=D["s2"])
    s1, s2_, sd = PPR_DEMO[name]
    fn = (lambda X: 1.0 / (1.0 + np.exp(-5.0 * ((X[:, 0] + X[:, 1]) / math.sqrt(2.0) - 0.5)))) if name == "single" else (lambda X: X[:, 0] * X[:, 1])
    g = Rng(s1)
    X = g.normals(200).reshape(100, 2)
    y = fn(X) + sd * g.normals(100)
    Xte = Rng(s2_).normals(4000).reshape(2000, 2)
    return dict(X=X, y=y, Xte=Xte, fte=fn(Xte), s2=sd * sd)


# =========================================================================== Section 11.7: ZIP code networks
ZIP_NTRAIN_PER_CLASS = 32          # 320 training digits, the size of the book's training set
ZIP_EPOCHS = 30
ZIP_SEEDS = (1, 2, 3, 4, 5)
ZIP_LR = 0.05
NETS = ("Net-1", "Net-2", "Net-3", "Net-4", "Net-5")


def zip_data():
    """zip.train and zip.test (7291 and 2007 digits, 16 x 16 grey levels in [-1, 1])."""
    import gzip
    out = []
    for name in ("zip.train.gz", "zip.test.gz"):
        with gzip.open(common.esl_file(name), "rt") as f:
            a = np.loadtxt(f)
        out += [a[:, 1:], a[:, 0].astype(int)]
    return out


def hshift(img, d):
    """Shift a 16 x 16 image d pixels to the right (left if d < 0), filling with background -1."""
    a = np.asarray(img, float).reshape(16, 16)
    out = np.full((16, 16), -1.0)
    if d >= 0:
        out[:, d:] = a[:, :16 - d]
    else:
        out[:, :16 + d] = a[:, -d:]
    return out.ravel()


def zip_subsets():
    """The data of the ZIP code example at CPU scale, built like Le Cun's (1989) set.

    Training: 160 digits of zip.train (16 of each class, fixed seed), each shown twice with a
    random horizontal shift of -2..2 pixels: 320 images, the size of the book's training set.
    Test: every digit of zip.test with one random horizontal shift (2007 images). The browser
    demonstration uses 300 of the test images (30 of each class). Returns Xtr, ytr, Xte, yte,
    demo (indices into the test set)."""
    Xa, ya, Xb, yb = zip_data()
    rng = np.random.default_rng(1989)
    base = np.concatenate([rng.choice(np.nonzero(ya == k)[0], ZIP_NTRAIN_PER_CLASS // 2, replace=False) for k in range(10)])
    Xtr, ytr = [], []
    for i in base:
        for _ in range(2):
            Xtr.append(hshift(Xa[i], int(rng.integers(-2, 3))))
            ytr.append(ya[i])
    perm = rng.permutation(len(ytr))
    Xtr, ytr = np.array(Xtr)[perm], np.array(ytr)[perm]
    Xte = np.array([hshift(x, int(rng.integers(-2, 3))) for x in Xb])
    demo = np.sort(np.concatenate([rng.choice(np.nonzero(yb == k)[0], 30, replace=False) for k in range(10)]))
    return Xtr, ytr, Xte, yb, demo


def zip_layers(name):
    """Layer list of each architecture of Figure 11.10 / Table 11.1.

    ("full", n_in, n_out): fully connected; ("local", C_in, H_in, C_out, H_out, k, stride): every
    output unit has its own k x k x C_in weights and bias (local connectivity, no sharing);
    ("shared", C_in, H_in, C_out, H_out, k, stride): one k x k x C_in kernel per output map, but
    every unit has its own bias (weight sharing, as in the book)."""
    if name == "Net-1":
        return [("full", 256, 10)]
    if name == "Net-2":
        return [("full", 256, 12), ("full", 12, 10)]
    if name == "Net-3":
        return [("local", 1, 16, 1, 8, 3, 2), ("local", 1, 8, 1, 4, 5, 2), ("full", 16, 10)]
    if name == "Net-4":
        return [("shared", 1, 16, 2, 8, 3, 2), ("local", 2, 8, 1, 4, 5, 2), ("full", 16, 10)]
    if name == "Net-5":
        return [("shared", 1, 16, 2, 8, 3, 2), ("shared", 2, 8, 4, 4, 5, 2), ("full", 64, 10)]
    raise KeyError(name)


def zip_counts(name):
    """(links, weights) of an architecture, counting a bias as one link and one weight (Table 11.1)."""
    links = weights = 0
    for L in zip_layers(name):
        if L[0] == "full":
            links += (L[1] + 1) * L[2]
            weights += (L[1] + 1) * L[2]
        else:
            _, cin, hin, cout, hout, k, s = L
            units = cout * hout * hout
            links += units * (cin * k * k + 1)
            weights += units * (cin * k * k + 1) if L[0] == "local" else cout * cin * k * k + units
    return links, weights


def _pad(x, k, value):
    import torch.nn.functional as F
    p = k // 2
    return F.pad(x, (p, p, p, p), value=value)


def zip_torch_net(name, seed):
    """The network as a torch module: tanh hidden units, logistic output units (Section 11.7).
    Starting weights uniform on +-2.4 / fan-in (Le Cun 1989). Inputs are padded with the
    background value -1, hidden maps with 0."""
    torch = common.torch_setup(seed)
    import torch.nn as nn
    import torch.nn.functional as F

    class ZipNet(nn.Module):
        def __init__(self):
            super().__init__()
            self.spec = zip_layers(name)
            self.params = nn.ParameterList()
            for L in self.spec:
                if L[0] == "full":
                    fan = L[1] + 1
                    W = torch.empty(L[2], L[1]).uniform_(-2.4 / fan, 2.4 / fan)
                    b = torch.empty(L[2]).uniform_(-2.4 / fan, 2.4 / fan)
                else:
                    _, cin, hin, cout, hout, k, s = L
                    fan = cin * k * k + 1
                    if L[0] == "local":
                        W = torch.empty(cout * hout * hout, cin * k * k).uniform_(-2.4 / fan, 2.4 / fan)
                    else:
                        W = torch.empty(cout, cin, k, k).uniform_(-2.4 / fan, 2.4 / fan)
                    b = torch.empty(cout, hout, hout).uniform_(-2.4 / fan, 2.4 / fan)
                self.params.append(nn.Parameter(W))
                self.params.append(nn.Parameter(b))

        def forward(self, x, hidden=False):
            h = x.view(-1, 1, 16, 16)
            acts = []
            for j, L in enumerate(self.spec):
                W, b = self.params[2 * j], self.params[2 * j + 1]
                last = j == len(self.spec) - 1
                if L[0] == "full":
                    h = h.reshape(h.shape[0], -1) @ W.T + b
                else:
                    _, cin, hin, cout, hout, k, s = L
                    hp = _pad(h, k, -1.0 if j == 0 else 0.0)
                    if L[0] == "shared":
                        h = F.conv2d(hp, W, stride=s) + b
                    else:
                        P = F.unfold(hp, k, stride=s)                  # (n, cin*k*k, hout*hout)
                        h = (P.transpose(1, 2) * W.view(1, hout * hout, -1)).sum(2).view(-1, cout, hout, hout) + b
                h = torch.sigmoid(h) if last else torch.tanh(h)
                acts.append(h)
            return (h, acts) if hidden else h

    return ZipNet()


def zip_train(name, seed, Xtr, ytr, Xte, yte, epochs=ZIP_EPOCHS, lr=ZIP_LR):
    """On-line back-propagation (one digit at a time, (11.13) with single summands) on the
    sum-of-squares error with 0/1 targets. Returns the test accuracy after each epoch (epoch 0 =
    starting weights), the training accuracy at the end and the final weights."""
    net = zip_torch_net(name, seed)
    torch = common.torch_setup(seed)
    xt = torch.tensor(Xtr, dtype=torch.float32)
    T = torch.zeros(len(ytr), 10)
    T[torch.arange(len(ytr)), torch.tensor(ytr)] = 1.0
    xe = torch.tensor(Xte, dtype=torch.float32)
    opt = torch.optim.SGD(net.parameters(), lr=lr)
    g = torch.Generator().manual_seed(seed)

    def acc(x, y):
        with torch.no_grad():
            return float((net(x).argmax(1).numpy() == y).mean())
    curve = [acc(xe, yte)]
    for ep in range(epochs):
        for i in torch.randperm(len(ytr), generator=g).tolist():
            opt.zero_grad()
            loss = ((net(xt[i:i + 1]) - T[i:i + 1]) ** 2).sum()
            loss.backward()
            opt.step()
        curve.append(acc(xe, yte))
    weights = [p.detach().numpy().astype(float).copy() for p in net.params]
    return dict(curve=curve, train_acc=acc(xt, ytr), weights=weights)


def zip_forward_np(name, weights, X):
    """Forward pass in numpy (double precision) from exported weights: the computation the
    browser demonstration repeats. Returns the outputs and the hidden-layer activations."""
    h = np.asarray(X, float).reshape(-1, 1, 16, 16)
    acts = []
    spec = zip_layers(name)
    for j, L in enumerate(spec):
        W, b = weights[2 * j], weights[2 * j + 1]
        last = j == len(spec) - 1
        if L[0] == "full":
            a = h.reshape(h.shape[0], -1) @ np.asarray(W).T + np.asarray(b)
        else:
            _, cin, hin, cout, hout, k, s = L
            p = k // 2
            hp = np.pad(h, ((0, 0), (0, 0), (p, p), (p, p)), constant_values=(-1.0 if j == 0 else 0.0))
            a = np.zeros((h.shape[0], cout, hout, hout))
            for r in range(hout):
                for c in range(hout):
                    patch = hp[:, :, s * r:s * r + k, s * c:s * c + k].reshape(h.shape[0], -1)   # (n, cin*k*k)
                    if L[0] == "shared":
                        a[:, :, r, c] = patch @ np.asarray(W).reshape(cout, -1).T
                    else:
                        Wl = np.asarray(W).reshape(cout, hout * hout, -1)[:, r * hout + c, :] if cout > 1 else np.asarray(W)[r * hout + c][None, :]
                        a[:, :, r, c] = patch @ Wl.T
            a = a + np.asarray(b)
        h = 1.0 / (1.0 + np.exp(-a)) if last else np.tanh(a)
        acts.append(h)
    return h, acts


def zip_results():
    """Train the five networks from each seed (cached in cache/ch11_zip.json)."""
    path = os.path.join(CACHE_DIR, "ch11_zip.json")
    if os.path.exists(path):
        with open(path) as f:
            return json.load(f)
    Xtr, ytr, Xte, yte, demo = zip_subsets()
    out = dict(curves={}, train_acc={}, weights={}, counts={})
    for name in NETS:
        out["curves"][name], out["train_acc"][name] = [], []
        out["counts"][name] = zip_counts(name)
        for s in ZIP_SEEDS:
            r = zip_train(name, s, Xtr, ytr, Xte, yte)
            out["curves"][name].append(r["curve"])
            out["train_acc"][name].append(r["train_acc"])
            if s == ZIP_SEEDS[0]:
                out["weights"][name] = [np.round(w, 6).tolist() for w in r["weights"]]
            print("  %s seed %d: test accuracy %.3f after %d epochs (training %.3f)" % (name, s, r["curve"][-1], ZIP_EPOCHS, r["train_acc"]))
    with open(path, "w") as f:
        json.dump(out, f)
    return out


# =========================================================================== Figures 11.1 and 11.3
def fig_11_1(out_dir=None):
    """Perspective plots of two ridge functions."""
    import matplotlib.pyplot as plt
    from matplotlib import cm
    g = np.linspace(0, 1, 61)
    X1, X2 = np.meshgrid(g, g)
    left = 1.0 / (1.0 + np.exp(-5.0 * ((X1 + X2) / math.sqrt(2.0) - 0.5)))
    V = X1
    right = (V + 0.1) * np.sin(1.0 / (V / 3.0 + 0.1))
    fig = plt.figure(figsize=(8.0, 3.7))
    for j, (Z, ttl) in enumerate([(left, r"$g(V)=1/[1+\exp(-5(V-0.5))]$, $V=(X_1+X_2)/\sqrt{2}$"),
                                  (right, r"$g(V)=(V+0.1)\sin(1/(V/3+0.1))$, $V=X_1$")]):
        ax = fig.add_subplot(1, 2, j + 1, projection="3d")
        ax.plot_surface(X1, X2, Z, cmap=cm.cool_r, linewidth=0.15, edgecolor="0.3", rstride=2, cstride=2, antialiased=True)
        ax.set_xlabel("$X_1$", labelpad=-8)
        ax.set_ylabel("$X_2$", labelpad=-8)
        ax.set_zlabel("$g(V)$", labelpad=-8)
        ax.set_xticklabels([]); ax.set_yticklabels([]); ax.set_zticklabels([])
        ax.view_init(elev=28, azim=-60 if j == 0 else -55)
        ax.set_title(ttl, fontsize=9)
    fig.subplots_adjust(left=0.0, right=1.0, top=0.92, bottom=0.02, wspace=0.0)
    savefig(fig, CH, "fig11-1", out_dir)


def fig_11_3(out_dir=None):
    """The sigmoid sigma(v) = 1/(1 + e^{-v}) and sigma(s v) for s = 1/2 and 10."""
    import matplotlib.pyplot as plt
    v = np.linspace(-10, 10, 801)
    fig, ax = plt.subplots(figsize=(5.2, 3.0))
    ax.plot(v, sigmoid(v), color=RED, label=r"$s=1$")
    ax.plot(v, sigmoid(0.5 * v), color=BLUE, label=r"$s=1/2$")
    ax.plot(v, sigmoid(10 * v), color=PURPLE, label=r"$s=10$")
    ax.set_xlabel(r"$v$")
    ax.set_ylabel(r"$1/(1+e^{-sv})$")
    ax.set_yticks([0, 0.5, 1.0])
    ax.legend(frameon=False, loc="upper left")
    fig.tight_layout()
    savefig(fig, CH, "fig11-3", out_dir)


# =========================================================================== Figures 11.4 and 11.5
MIX_LAMS = (0.0, 0.02)
MIX_STARTS = 10
MIX_MAXIT = 500


def mixture_nets():
    """Ten-unit softmax networks on the mixture data, without and with weight decay 0.02. For each
    decay value ten starts are fitted and the one with the smallest penalised criterion is kept
    (Section 11.5.5). Inputs are used as they are (both coordinates already have a spread of
    about one). Returns {lam: (net, errors, all start criteria)}."""
    mx = mixture()
    X, y = mx["x"], mx["y"].astype(int)
    Y = np.column_stack([1 - y, y])
    out = {}
    for lam in MIX_LAMS:
        best, crit = None, []
        for s in range(1, MIX_STARTS + 1):
            net = Net(2, 10, K=2, out="softmax").fit(X, Y, lam=lam, seed=1100 + s, maxit=MIX_MAXIT)
            crit.append(net.value)
            if best is None or net.value < best.value:
                best = net
        errs = mixture_errors(lambda Z, n=best: np.argmax(n.predict(n.w, Z), 1), mx)
        out[lam] = (best, errs, crit)
    return out


def fig_11_4(out_dir=None):
    """Ten-unit network on the mixture data, without and with weight decay."""
    import matplotlib.pyplot as plt
    mx = mixture()
    res = mixture_nets()
    px1, px2 = mx["px1"], mx["px2"]
    G = mx["xnew"]
    F1, F2 = np.meshgrid(np.linspace(px1[0], px1[-1], 250), np.linspace(px2[0], px2[-1], 250))
    Fg = np.column_stack([F1.ravel(), F2.ravel()])
    prob = mx["prob"].reshape(len(px2), len(px1))
    fig, axes = plt.subplots(2, 1, figsize=(5.2, 10.0))
    for ax, lam in zip(axes, MIX_LAMS):
        net, (tr, te, by), _ = res[lam]
        P = net.predict(net.w, Fg)[:, 1].reshape(F1.shape)
        cls = net.predict(net.w, G)[:, 1] > 0.5
        ax.scatter(G[:, 0], G[:, 1], s=0.6, c=np.where(cls, ORANGE, "#2a9df4"), lw=0, rasterized=True)
        ax.contour(F1, F2, P, levels=[0.5], colors="k", linewidths=1.2)
        ax.contour(px1, px2, prob, levels=[0.5], colors=PURPLE, linewidths=1.2, linestyles="--")
        yy = mx["y"]
        ax.scatter(mx["x"][:, 0], mx["x"][:, 1], s=22, facecolors="none",
                   edgecolors=np.where(yy == 1, ORANGE, "#2a9df4"), linewidths=1.1)
        ax.set_title("Neural Network - 10 Units, " + ("No Weight Decay" if lam == 0 else "Weight Decay=%g" % lam))
        ax.text(0.02, 0.03, "Training Error: %.3f\nTest Error:       %.3f\nBayes Error:    %.3f" % (tr, te, by),
                transform=ax.transAxes, fontsize=8.5, family="monospace", bbox=dict(fc="white", ec="0.6", alpha=0.9))
        ax.set_xticks([]); ax.set_yticks([])
        ax.set_xlim(px1[0], px1[-1]); ax.set_ylim(px2[0], px2[-1])
        print("  decay %g: training %.3f, test %.3f, Bayes %.3f; criterion %.3f (%d iterations)" % (lam, tr, te, by, net.value, net.iters))
    fig.tight_layout()
    savefig(fig, CH, "fig11-4", out_dir)


def fig_11_5(out_dir=None):
    """Heat maps of the fitted weights of the two networks of Figure 11.4."""
    import matplotlib.pyplot as plt
    from matplotlib.colors import LinearSegmentedColormap
    cmap = LinearSegmentedColormap.from_list("gr", ["#00e000", "#6e7a6e", "#ff1a1a"])
    res = mixture_nets()
    vmax = 8.0         # common colour scale, saturating at +-8 (the largest weight with decay is about 8.8)
    fig, axes = plt.subplots(2, 2, figsize=(8.2, 3.6), gridspec_kw=dict(height_ratios=[2, 3]))
    for j, lam in enumerate(MIX_LAMS):
        A, Bm = res[lam][0].unpack(res[lam][0].w)
        top, bot = axes[0, j], axes[1, j]
        top.imshow(Bm, cmap=cmap, vmin=-vmax, vmax=vmax, aspect="auto", origin="lower")
        top.set_yticks([0, 1]); top.set_yticklabels(["$y_1$", "$y_2$"])
        top.set_xticks(range(11)); top.set_xticklabels(["1"] + ["$z_{%d}$" % (m + 1) for m in range(10)], fontsize=9)
        top.set_title("No weight decay" if lam == 0 else "Weight decay")
        bot.imshow(A.T, cmap=cmap, vmin=-vmax, vmax=vmax, aspect="auto", origin="lower")
        bot.set_yticks([0, 1, 2]); bot.set_yticklabels(["1", "$x_1$", "$x_2$"])
        bot.set_xticks(range(10)); bot.set_xticklabels(["$z_{%d}$" % (m + 1) for m in range(10)], fontsize=9)
        print("  decay %g: largest |weight| %.2f, sum of squares %.2f" % (lam, np.max(np.abs(res[lam][0].w)), np.sum(res[lam][0].w ** 2)))
    fig.tight_layout()
    savefig(fig, CH, "fig11-5", out_dir)


# =========================================================================== Figures 11.6 - 11.8 and 11.S1
SIM_MAXIT = 5000
SIM_MS = tuple(range(11))
SIM_LAM_GRID = tuple(round(0.01 * k, 2) for k in range(16))


def sim_experiment(model, lam, Ms=SIM_MS, starts=10, keep_preds=False):
    """Relative test errors of networks with M hidden units fitted from `starts` starting weights.
    With keep_preds, also the error of the network with the smallest penalised criterion, of the
    average of the ten predictions, and of the network with the averaged weights."""
    D = sim_data(model)
    out = dict(err={}, best={}, avgpred={}, avgw={})
    for M in Ms:
        errs, preds, ws, vals = [], [], [], []
        for s in range(1, starts + 1):
            net = fit_net(D["X"], D["y"], M, lam, start_seed(M, s), maxit=SIM_MAXIT)
            errs.append(rel_test_error(net, D))
            if keep_preds:
                preds.append(net.predict(net.w, D["Xte"])[:, 0])
                ws.append(net.w)
                vals.append(net.value)
        out["err"][M] = errs
        if keep_preds:
            out["best"][M] = errs[int(np.argmin(vals))]
            fbar = np.mean(preds, axis=0)
            out["avgpred"][M] = 1.0 + float(np.mean((D["fte"] - fbar) ** 2)) / D["s2"]
            out["avgw"][M] = rel_test_error(net, D, w=np.mean(ws, axis=0))
    return out


def sim_results():
    """All the fits of Figures 11.6-11.8 and 11.S1 (cached in cache/ch11_sim.json)."""
    path = os.path.join(CACHE_DIR, "ch11_sim.json")
    if os.path.exists(path):
        with open(path) as f:
            R = json.load(f)
        for k in R:
            for kk in R[k]:
                R[k][kk] = {float(a) if k == "lam_sweep" else int(a): b for a, b in R[k][kk].items()} if isinstance(R[k][kk], dict) else R[k][kk]
        return R
    R = {}
    R["sig_0005"] = sim_experiment("sigmoid", 0.0005, keep_preds=True)
    R["rad_0005"] = sim_experiment("radial", 0.0005)
    R["sig_0"] = sim_experiment("sigmoid", 0.0)
    R["sig_01"] = sim_experiment("sigmoid", 0.1)
    sweep = {}
    for lam in SIM_LAM_GRID:
        sweep[lam] = sim_experiment("sigmoid", lam, Ms=(10,))["err"][10]
    R["lam_sweep"] = {"err": sweep}
    with open(path, "w") as f:
        json.dump(R, f)
    return sim_results()


def _boxes(ax, data, positions, ylim, color=BLUE):
    """Boxplots with the whiskers at the extremes (all ten starts are shown), clipped to ylim;
    values beyond the top are marked with a triangle and their value."""
    import matplotlib.pyplot as plt  # noqa: F401
    bp = ax.boxplot([np.minimum(d, ylim[1]) for d in data], positions=positions, widths=0.6 * (positions[1] - positions[0]) if len(positions) > 1 else 0.6,
                    whis=(0, 100), patch_artist=True, showfliers=False, medianprops=dict(color="k", lw=1.4))
    for b in bp["boxes"]:
        b.set(facecolor="#9ecae1", edgecolor="0.25")
    for x, d in zip(positions, data):
        hi = max(d)
        if hi > ylim[1]:
            ax.plot([x], [ylim[1] - 0.012 * (ylim[1] - ylim[0])], marker="^", color=RED, ms=5)
            ax.text(x, ylim[1] - 0.05 * (ylim[1] - ylim[0]), "%.0f" % hi if hi >= 10 else "%.1f" % hi, ha="center", va="top", fontsize=7, color=RED)
    ax.axhline(1.0, color="k", ls="--", lw=1)
    ax.set_ylim(*ylim)


def fig_11_6(out_dir=None):
    """Test error against the number of hidden units: sum of sigmoids and radial function."""
    import matplotlib.pyplot as plt
    R = sim_results()
    fig, axes = plt.subplots(1, 2, figsize=(8.4, 3.4))
    for ax, key, ttl, yl in ((axes[0], "sig_0005", "Sum of Sigmoids", (1.0, 3.0)), (axes[1], "rad_0005", "Radial", (0.0, 30.0))):
        _boxes(ax, [R[key]["err"][M] for M in SIM_MS], list(SIM_MS), yl)
        ax.set_xticks(list(SIM_MS)); ax.set_xticklabels([str(M) for M in SIM_MS])
        ax.set_xlabel("Number of Hidden Units"); ax.set_ylabel("Test Error"); ax.set_title(ttl)
        print("  %s: median relative test error by M:" % ttl, [round(float(np.median(R[key]["err"][M])), 2) for M in SIM_MS])
    fig.tight_layout()
    savefig(fig, CH, "fig11-6", out_dir)


def fig_11_7(out_dir=None):
    """Sum of sigmoids: no weight decay and weight decay 0.1."""
    import matplotlib.pyplot as plt
    R = sim_results()
    fig, axes = plt.subplots(1, 2, figsize=(8.4, 3.4))
    for ax, key, ttl in ((axes[0], "sig_0", "No Weight Decay"), (axes[1], "sig_01", "Weight Decay=0.1")):
        _boxes(ax, [R[key]["err"][M] for M in SIM_MS], list(SIM_MS), (1.0, 3.0))
        ax.set_xticks(list(SIM_MS)); ax.set_xticklabels([str(M) for M in SIM_MS])
        ax.set_xlabel("Number of Hidden Units"); ax.set_ylabel("Test Error"); ax.set_title(ttl)
        print("  %s: median by M:" % ttl, [round(float(np.median(R[key]["err"][M])), 2) for M in SIM_MS])
    fig.tight_layout()
    savefig(fig, CH, "fig11-7", out_dir)


def fig_11_8(out_dir=None):
    """Ten hidden units: test error against the weight decay parameter."""
    import matplotlib.pyplot as plt
    R = sim_results()
    sw = R["lam_sweep"]["err"]
    lams = sorted(sw)
    fig, ax = plt.subplots(figsize=(5.6, 3.4))
    _boxes(ax, [sw[l] for l in lams], lams, (1.0, 2.2))
    ax.set_xticks(lams[::2]); ax.set_xticklabels(["%.2f" % l for l in lams[::2]])
    ax.set_xlim(-0.008, lams[-1] + 0.008)
    ax.set_xlabel("Weight Decay Parameter"); ax.set_ylabel("Test Error"); ax.set_title("Sum of Sigmoids, 10 Hidden Unit Model")
    med = [float(np.median(sw[l])) for l in lams]
    print("  median relative test error by decay:", dict(zip(lams, np.round(med, 3))), "minimum at", lams[int(np.argmin(med))])
    fig.tight_layout()
    savefig(fig, CH, "fig11-8", out_dir)


def fig_11_s1(out_dir=None):
    """Supplementary (Section 11.5.5): averaging the predictions of the ten starts, against the
    single best start and against averaging the weights."""
    import matplotlib.pyplot as plt
    R = sim_results()["sig_0005"]
    fig, ax = plt.subplots(figsize=(5.8, 3.5))
    _boxes(ax, [R["err"][M] for M in SIM_MS], list(SIM_MS), (1.0, 3.0))
    Ms = list(SIM_MS)
    ax.plot(Ms, [min(R["avgw"][M], 2.97) for M in Ms], "s-", color=RED, ms=4, lw=1.2, label="averaged weights")
    ax.plot(Ms, [R["best"][M] for M in Ms], "^-", color=ORANGE, ms=4, lw=1.2, label="lowest penalised error")
    ax.plot(Ms, [R["avgpred"][M] for M in Ms], "o-", color=GREEN, ms=4, lw=1.6, label="averaged predictions")
    ax.set_xticks(Ms)
    ax.set_xlabel("Number of Hidden Units"); ax.set_ylabel("Test Error")
    ax.set_title(r"Sum of sigmoids, weight decay 0.0005: ten starts")
    ax.legend(frameon=False, fontsize=8, loc="upper right", bbox_to_anchor=(1.0, 0.93))
    print("  averaged predictions:", [round(R["avgpred"][M], 3) for M in Ms])
    print("  best start:", [round(R["best"][M], 3) for M in Ms])
    print("  averaged weights:", [round(R["avgw"][M], 3) for M in Ms])
    fig.tight_layout()
    savefig(fig, CH, "fig11-S1", out_dir)


# =========================================================================== Figures 11.9 and 11.11
def fig_11_9(out_dir=None):
    """Examples of training digits from the ZIP code data."""
    import matplotlib.pyplot as plt
    Xa, ya, _, _ = zip_data()
    rng = np.random.default_rng(9)
    fig, axes = plt.subplots(4, 10, figsize=(7.5, 3.1))
    for k in range(10):
        idx = rng.choice(np.nonzero(ya == k)[0], 4, replace=False)
        for r in range(4):
            ax = axes[r, k]
            ax.imshow(-Xa[idx[r]].reshape(16, 16), cmap="gray", vmin=-1, vmax=1, interpolation="nearest")
            ax.set_xticks([]); ax.set_yticks([])
            for sp in ax.spines.values():
                sp.set_visible(False)
    fig.subplots_adjust(left=0.01, right=0.99, top=0.99, bottom=0.01, wspace=0.08, hspace=0.08)
    savefig(fig, CH, "fig11-9", out_dir)


def fig_11_11(out_dir=None):
    """Test accuracy against training epochs for the five networks."""
    import matplotlib.pyplot as plt
    Z = zip_results()
    cols = {"Net-1": GREY, "Net-2": BLUE, "Net-3": GREEN, "Net-4": ORANGE, "Net-5": RED}
    fig, ax = plt.subplots(figsize=(5.8, 3.8))
    ep = np.arange(ZIP_EPOCHS + 1)
    for name in NETS:
        C = 100 * np.array(Z["curves"][name])
        ax.fill_between(ep, C.min(0), C.max(0), color=cols[name], alpha=0.15, lw=0)
        ax.plot(ep, C.mean(0), color=cols[name], label=name)
        L, W = Z["counts"][name]
        print("  %s: links %d, weights %d; test %% correct after %d epochs %.1f (seeds %s); training %% correct %.1f"
              % (name, L, W, ZIP_EPOCHS, C.mean(0)[-1], np.round(C[:, -1], 1).tolist(), 100 * np.mean(Z["train_acc"][name])))
    ax.set_xlim(0, ZIP_EPOCHS); ax.set_ylim(50, 100)
    ax.set_xlabel("Training Epochs"); ax.set_ylabel("% Correct on Test Data")
    ax.legend(frameon=False, loc="lower right")
    fig.tight_layout()
    savefig(fig, CH, "fig11-11", out_dir)
    export_demo_data()


# =========================================================================== Exercises 11.5 and 11.6: the model of Exercise 11.5
EX5_SEEDS = (1151, 1152)


def ex5_data(N=100, Ntest=1000):
    """Y = sigma(a1'X) + (a2'X)^2 + 0.30 Z, X ~ N(0, I_2), a1 = (3,3), a2 = (3,-3) (Exercise 11.5)."""
    g = Rng(EX5_SEEDS[0])
    X = g.normals(2 * N).reshape(N, 2)
    f = sigmoid(X @ A1) + (X @ A2) ** 2
    y = f + 0.3 * g.normals(N)
    gt = Rng(EX5_SEEDS[1])
    Xte = gt.normals(2 * Ntest).reshape(Ntest, 2)
    fte = sigmoid(Xte @ A1) + (Xte @ A2) ** 2
    yte = fte + 0.3 * gt.normals(Ntest)
    return dict(X=X, y=y, f=f, Xte=Xte, yte=yte, fte=fte, s2=0.09)


def ex5_interior(D):
    """Test points inside the training data's range along both true directions a1 and a2: there
    the error measures the fit, not the extrapolation of the quadratic beyond the data."""
    inside = np.ones(len(D["yte"]), bool)
    for a in (A1, A2):
        v, vt = D["X"] @ a, D["Xte"] @ a
        inside &= (vt >= v.min()) & (vt <= v.max())
    return inside


def backprop_gd(X, y, M, lam, epochs, lr, seed, Xte=None, yte=None, record=None):
    """Exercise 11.5(a): batch back-propagation, i.e. gradient descent (11.13) on R + lambda J
    with a fixed learning rate, one update per epoch. Returns the weights and, at the epochs in
    `record`, the training and test mean squared errors."""
    net = Net(X.shape[1], M)
    w = start_weights(net.nw, seed)
    Y = y[:, None]
    hist = []
    rec = set(record or [])
    inside = None if Xte is None else ex5_interior(dict(X=X, Xte=Xte, yte=yte))
    for ep in range(epochs + 1):
        if ep in rec:
            tr = float(np.mean((y - net.predict(w, X)[:, 0]) ** 2))
            r2 = (yte - net.predict(w, Xte)[:, 0]) ** 2 if Xte is not None else np.array([np.nan])
            hist.append((ep, tr, float(np.mean(r2)), float(np.mean(r2[inside])) if inside is not None else np.nan))
        if ep < epochs:
            w = w - lr * net.grad(w, X, Y, lam)
    net.w = w
    return net, hist


# =========================================================================== Section 11.9: Bayesian neural networks at CPU scale
NIPS_P, NIPS_INF, NIPS_RED = 100, 5, 10
NIPS_NTR, NIPS_NTE = 500, 2000
NIPS_SCREEN = 20
H1, H2 = 20, 8


def nips_data():
    """A small two-class problem built like the Madelon data of the NIPS 2003 challenge
    (Table 11.2): 5 informative features whose classes sit on clusters at the vertices of a
    hypercube, 10 linear combinations of them, and 85 'probes' (noise features independent of
    the class), 100 features in all, in random order; 500 training and 2000 test cases.
    Generated with scikit-learn's make_classification (an implementation of the Madelon recipe).
    Returns standardised Xtr, ytr, Xte, yte and the mask of real (non-probe) features."""
    from sklearn.datasets import make_classification
    X, y = make_classification(n_samples=NIPS_NTR + NIPS_NTE, n_features=NIPS_P, n_informative=NIPS_INF,
                               n_redundant=NIPS_RED, n_repeated=0, n_classes=2, n_clusters_per_class=4,
                               flip_y=0.02, class_sep=1.0, hypercube=True, shuffle=False, random_state=2003)
    rng = np.random.default_rng(2003)
    perm = rng.permutation(NIPS_P)
    real = np.zeros(NIPS_P, bool)
    real[: NIPS_INF + NIPS_RED] = True
    X, real = X[:, perm], real[perm]
    rows = rng.permutation(len(y))
    X, y = X[rows], y[rows]
    Xtr, ytr, Xte, yte = X[:NIPS_NTR], y[:NIPS_NTR], X[NIPS_NTR:], y[NIPS_NTR:]
    mu, sd = Xtr.mean(0), Xtr.std(0)
    return (Xtr - mu) / sd, ytr, (Xte - mu) / sd, yte, real


def tstats(X, y):
    """Two-sample t statistics (pooled variance) of each column of X between the classes."""
    a, b = X[y == 1], X[y == 0]
    na, nb = len(a), len(b)
    sp = np.sqrt(((na - 1) * a.var(0, ddof=1) + (nb - 1) * b.var(0, ddof=1)) / (na + nb - 2))
    return (a.mean(0) - b.mean(0)) / (sp * np.sqrt(1.0 / na + 1.0 / nb))


class BayesNet:
    """Two-hidden-layer tanh network (H1 = 20, H2 = 8 units) with a logistic output, as in Neal and
    Zhang (2006), with Gaussian priors whose precisions have Gamma hyperpriors. The input-to-hidden
    weights of input j share one precision tau_j: automatic relevance determination (ARD).
    Sampling alternates hybrid (Hamiltonian) Monte Carlo for the weights, with step sizes scaled by
    each weight's prior standard deviation, and Gibbs updates of the precisions."""

    def __init__(self, p, h1=H1, h2=H2):
        self.p, self.h1, self.h2 = p, h1, h2
        self.shapes = [(h1, p), (h1,), (h2, h1), (h2,), (h2,), (1,)]
        self.sizes = [int(np.prod(s)) for s in self.shapes]
        self.n = sum(self.sizes)
        # prior groups: one per input (ARD), then b1, W2, b2, w3; b3 has a fixed broad prior
        self.groups = np.concatenate([np.tile(np.arange(p), h1), np.full(h1, p), np.full(h2 * h1, p + 1),
                                      np.full(h2, p + 2), np.full(h2, p + 3), [p + 4]])

    def split(self, th):
        out, k = [], 0
        for s, n in zip(self.shapes, self.sizes):
            out.append(th[k:k + n].reshape(s))
            k += n
        return out

    def logit(self, th, X):
        W1, b1, W2, b2, w3, b3 = self.split(th)
        Z1 = np.tanh(X @ W1.T + b1)
        Z2 = np.tanh(Z1 @ W2.T + b2)
        return Z2 @ w3 + b3[0], Z1, Z2

    def nll_grad(self, th, X, y):
        W1, b1, W2, b2, w3, b3 = self.split(th)
        a, Z1, Z2 = self.logit(th, X)
        nll = float(np.sum(np.logaddexp(0.0, a) - y * a))
        d = sigmoid(a) - y                                  # dNLL/da
        g_w3, g_b3 = Z2.T @ d, np.array([d.sum()])
        D2 = np.outer(d, w3) * (1 - Z2 ** 2)
        g_W2, g_b2 = D2.T @ Z1, D2.sum(0)
        D1 = (D2 @ W2) * (1 - Z1 ** 2)
        g_W1, g_b1 = D1.T @ X, D1.sum(0)
        return nll, np.concatenate([g_W1.ravel(), g_b1, g_W2.ravel(), g_b2, g_w3, g_b3])

    def sample(self, X, y, iters=1000, burn=500, thin=2, L=40, seed=0, shape=0.5, rate=0.05, b3_sd=10.0):
        rng = np.random.default_rng(seed)
        ng = self.p + 5
        tau = np.ones(ng)
        tau[self.p + 4] = 1.0 / b3_sd ** 2
        th = rng.normal(0, 0.1, self.n)
        eps, acc_hist, samples, taus = 0.05, [], [], []
        for it in range(iters):
            prec = tau[self.groups]
            scale = 1.0 / np.sqrt(prec)

            def U(t):
                nll, g = self.nll_grad(t, X, y)
                return nll + 0.5 * np.sum(prec * t * t), g + prec * t
            e = eps * scale * rng.uniform(0.8, 1.2)
            u0, g0 = U(th)
            pm = rng.normal(size=self.n)
            H0 = u0 + 0.5 * pm @ pm
            t, g = th.copy(), g0
            pm = pm - 0.5 * e * g
            for step in range(L):
                t = t + e * pm
                u1, g = U(t)
                if step < L - 1:
                    pm = pm - e * g
            pm = pm - 0.5 * e * g
            H1_ = u1 + 0.5 * pm @ pm
            accept = np.isfinite(H1_) and np.log(rng.uniform()) < H0 - H1_
            if accept:
                th = t
            acc_hist.append(bool(accept))
            if it < burn and it % 10 == 9:          # adapt the global step during burn-in only
                ar = np.mean(acc_hist[-10:])
                eps *= 1.15 if ar > 0.8 else (0.8 if ar < 0.6 else 1.0)
            # Gibbs step for the precisions (conjugate Gamma updates)
            sq = np.bincount(self.groups, weights=th * th, minlength=ng)
            cnt = np.bincount(self.groups, minlength=ng)
            for k in range(ng - 1):
                tau[k] = rng.gamma(shape + 0.5 * cnt[k], 1.0 / (rate + 0.5 * sq[k]))
            if it >= burn and (it - burn) % thin == 0:
                samples.append(th.copy())
                taus.append(tau[: self.p].copy())
        self.samples, self.taus = np.array(samples), np.array(taus)
        self.accept = float(np.mean(acc_hist[burn:]))
        return self

    def predict_proba(self, X):
        return np.mean([sigmoid(self.logit(t, X)[0]) for t in self.samples], axis=0)


def boosted_nets(Xtr, ytr, Xte, M=4, rounds=200, nu=0.1, lam=0.01, seed=0):
    """Gradient boosting of the binomial deviance with single-hidden-layer networks of M units
    as base learners (each fitted by least squares to the current negative gradient, with weight
    decay lam and 100 quasi-Newton iterations, the nnet defaults). Returns test probabilities."""
    p0 = np.clip(ytr.mean(), 1e-6, 1 - 1e-6)
    Ftr = np.full(len(ytr), math.log(p0 / (1 - p0)))
    Fte = np.full(len(Xte), Ftr[0])
    for r in range(rounds):
        res = ytr - sigmoid(Ftr)
        net = Net(Xtr.shape[1], M).fit(Xtr, res, lam=lam, seed=seed * 1000 + r, maxit=100)
        Ftr = Ftr + nu * net.predict(net.w, Xtr)[:, 0]
        Fte = Fte + nu * net.predict(net.w, Xte)[:, 0]
    return sigmoid(Fte)


def nips_methods(Xtr, ytr, Xte, seed=0):
    """Test-set class probabilities and fitting times (minutes) of the five methods of
    Section 11.9.2 on one feature set."""
    import time
    import warnings
    from sklearn.ensemble import GradientBoostingClassifier, RandomForestClassifier
    from sklearn.exceptions import ConvergenceWarning
    from sklearn.neural_network import MLPClassifier
    warnings.filterwarnings("ignore", category=ConvergenceWarning)
    out = {}
    t0 = time.time()
    bn = BayesNet(Xtr.shape[1]).sample(Xtr, ytr.astype(float), seed=seed)
    out["Bayesian neural nets"] = (bn.predict_proba(Xte), (time.time() - t0) / 60, bn)
    t0 = time.time()
    gb = GradientBoostingClassifier(n_estimators=400, learning_rate=0.05, max_depth=4, subsample=0.8, random_state=seed).fit(Xtr, ytr)
    out["boosted trees"] = (gb.predict_proba(Xte)[:, 1], (time.time() - t0) / 60, None)
    t0 = time.time()
    out["boosted neural nets"] = (boosted_nets(Xtr, ytr.astype(float), Xte, seed=seed), (time.time() - t0) / 60, None)
    t0 = time.time()
    rf = RandomForestClassifier(n_estimators=500, random_state=seed).fit(Xtr, ytr)
    out["random forests"] = (rf.predict_proba(Xte)[:, 1], (time.time() - t0) / 60, None)
    t0 = time.time()
    rng = np.random.default_rng(seed)
    probs = []
    for b in range(25):
        idx = rng.integers(0, len(ytr), len(ytr))
        mlp = MLPClassifier(hidden_layer_sizes=(H1, H2), activation="tanh", solver="lbfgs", alpha=1.0, max_iter=500,
                            random_state=b).fit(Xtr[idx], ytr[idx])
        probs.append(mlp.predict_proba(Xte)[:, 1])
    out["bagged neural networks"] = (np.mean(probs, 0), (time.time() - t0) / 60, None)
    return out


NIPS_METHODS = ("Bayesian neural nets", "boosted trees", "boosted neural nets", "random forests", "bagged neural networks")


def nips_results():
    """Section 11.9.2 at CPU scale (cached in cache/ch11_nips.json): the five methods on the
    univariate-screened features (top 20 by |t|) and on the features kept by ARD (an ARD
    network fitted to all 100 features; keep the inputs whose posterior median prior standard
    deviation sigma_j is above half of the largest)."""
    path = os.path.join(CACHE_DIR, "ch11_nips.json")
    if os.path.exists(path):
        with open(path) as f:
            return json.load(f)
    import time
    Xtr, ytr, Xte, yte, real = nips_data()
    t = tstats(Xtr, ytr)
    screened = np.argsort(-np.abs(t))[:NIPS_SCREEN]
    t0 = time.time()
    ard = BayesNet(NIPS_P).sample(Xtr, ytr.astype(float), seed=11)
    ard_min = (time.time() - t0) / 60
    sig = np.median(1.0 / np.sqrt(ard.taus), axis=0)
    reduced = np.nonzero(sig > 0.5 * sig.max())[0]
    R = dict(real=real.tolist(), t=t.tolist(), screened=screened.tolist(), ard_sigma=sig.tolist(), reduced=reduced.tolist(),
             ard_minutes=ard_min, ard_accept=ard.accept, sets={})
    for name, cols in (("screened", screened), ("reduced", reduced)):
        res = nips_methods(Xtr[:, cols], ytr, Xte[:, cols])
        R["sets"][name] = {k: dict(err=float(np.mean((v[0] > 0.5) != yte)), minutes=v[1],
                                   wrong=np.nonzero((v[0] > 0.5) != yte)[0].tolist()) for k, v in res.items()}
        R["sets"][name]["Bayesian neural nets"]["accept"] = res["Bayesian neural nets"][2].accept
        print("  %s features (%d):" % (name, len(cols)), {k: round(v["err"], 4) for k, v in R["sets"][name].items()})
    with open(path, "w") as f:
        json.dump(R, f)
    return R


def fig_11_s3(out_dir=None):
    """Supplementary (Section 11.9.2, standing in for Figure 11.12): test error of the five
    methods on a Madelon-like problem, with screened and with ARD-reduced features."""
    import matplotlib.pyplot as plt
    R = nips_results()
    cols = [RED, BLUE, GREEN, ORANGE, PURPLE]
    marks = ["o", "s", "^", "D", "v"]
    fig, ax = plt.subplots(figsize=(6.0, 3.4))
    for j, name in enumerate(("screened", "reduced")):
        errs = [100 * R["sets"][name][k]["err"] for k in NIPS_METHODS]
        for i, (k, e) in enumerate(zip(NIPS_METHODS, errs)):
            ax.plot([j + (i - 2) * 0.08], [e], marker=marks[i], color=cols[i], ms=7, ls="none", label=k if j == 0 else None)
        pbar = np.mean(errs) / 100
        se = 100 * math.sqrt(2 * pbar * (1 - pbar) / NIPS_NTE)
        ax.errorbar([j + 0.3], [max(errs) + 1.0], yerr=[[se / 2], [se / 2]], color="k", capsize=4, lw=1.2)
        ranks = np.argsort(np.argsort(errs)) + 1
        print("  %s: errors %%" % name, dict(zip(NIPS_METHODS, np.round(errs, 2))), "ranks", ranks.tolist(),
              "SE of a difference %.2f%%" % se)
    ax.set_xticks([0, 1])
    ax.set_xticklabels(["screened\n(%d features)" % NIPS_SCREEN, "ARD reduced\n(%d features)" % len(R["reduced"])])
    ax.set_xlim(-0.5, 1.6)
    ax.set_ylabel("Test Error (%)")
    ax.legend(frameon=False, fontsize=8, loc="center left", bbox_to_anchor=(1.0, 0.5))
    fig.tight_layout()
    savefig(fig, CH, "fig11-S3", out_dir)


def fig_11_s4(out_dir=None):
    """Supplementary (Section 11.9.1): what ARD and the t-test see in each feature."""
    import matplotlib.pyplot as plt
    R = nips_results()
    real = np.array(R["real"])
    t, sig = np.abs(np.array(R["t"])), np.array(R["ard_sigma"])
    fig, axes = plt.subplots(1, 2, figsize=(8.4, 3.2))
    for ax, v, lab, thr in ((axes[0], t, r"$|t|$ (univariate screening)", np.sort(t)[-NIPS_SCREEN]),
                            (axes[1], sig, r"posterior median of $\sigma_j$ (ARD)", 0.5 * sig.max())):
        o = np.argsort(-v)
        ax.bar(np.arange(NIPS_P), v[o], color=np.where(real[o], RED, "0.6"), width=0.85)
        ax.axhline(thr, color="k", ls="--", lw=1)
        ax.set_xlabel("features, sorted"); ax.set_ylabel(lab)
        print("  %s: real features above the cut %d of %d selected" % (lab, int(np.sum(real[v >= thr])), int(np.sum(v >= thr))))
    axes[0].bar([0], [0], color=RED, label="real feature"); axes[0].bar([0], [0], color="0.6", label="probe")
    axes[0].legend(frameon=False, fontsize=8)
    fig.tight_layout()
    savefig(fig, CH, "fig11-S4", out_dir)


# =========================================================================== Figure 11.S2 (Section 11.2) and Exercises 11.5-11.6
def ex5_ppr_fit(M=2, df=12.0):
    D = ex5_data()
    return D, ppr_fit(D["X"], D["y"], M=M, df=df)


def fig_11_s2(out_dir=None):
    """Supplementary (Section 11.2): projection pursuit regression with two ridge terms on the
    model of Exercise 11.5, Y = sigma(a1'X) + (a2'X)^2 + 0.3 Z: the estimated directions and
    ridge functions against the true ones."""
    import matplotlib.pyplot as plt
    D, fit = ex5_ppr_fit()
    X, y = D["X"], D["y"]
    fig, axes = plt.subplots(1, 2, figsize=(8.4, 3.3))
    truth = {0: lambda v: 18.0 * v ** 2, 1: lambda v: sigmoid(3.0 * math.sqrt(2.0) * v)}
    for m_, (ax, t) in enumerate(zip(axes, fit["terms"])):
        v = X @ t["w"]
        others = sum(tj["g"].eval(X @ tj["w"]) for j, tj in enumerate(fit["terms"]) if j != m_)
        pr = y - fit["ybar"] - others
        grid = np.linspace(v.min(), v.max(), 300)
        gt = truth[m_](grid)
        gt = gt - np.mean(truth[m_](v))
        ax.scatter(v, pr, s=10, color="0.55", lw=0)
        ax.plot(grid, t["g"].eval(grid), color=RED, lw=2, label=r"fitted $\hat g_%d$" % (m_ + 1))
        ax.plot(grid, gt, color=BLUE, lw=1.4, ls="--", label="true ridge function")
        ax.set_xlabel(r"$v=\hat\omega_%d^T x$,  $\hat\omega_%d=(%.3f,\ %.3f)$" % (m_ + 1, m_ + 1, t["w"][0], t["w"][1]))
        ax.set_ylabel("partial residual")
        ax.legend(frameon=False, fontsize=8, loc="upper center")
        ax.set_title("Term %d" % (m_ + 1))
        print("  term %d: omega = %s, %d Gauss-Newton steps" % (m_ + 1, np.round(t["w"], 4), t["iters"]))
    print("  training RSS %.3f; test MSE %.4f (noise variance 0.09)" % (fit["rss"], np.mean((D["yte"] - ppr_predict(fit, D["Xte"])) ** 2)))
    fig.tight_layout()
    savefig(fig, CH, "fig11-S2", out_dir)


EX5_LAMS = (0.0, 0.001, 0.01, 0.1)
EX5_EPOCHS = 100000
EX5_LR = 0.001


def ex5_results():
    """Exercise 11.5 (cached in cache/ch11_ex5.json). (b): ten-unit networks trained by batch
    back-propagation (learning rate 0.001 on the summed squared error of the standardised
    response, 100,000 epochs) for four weight decays; (c): networks with 1-10 hidden units fitted to
    convergence by quasi-Newton (five starts, the lowest penalised error kept), decay 0.0001.
    Exercise 11.6: projection pursuit with 1-4 terms and smoothers of 5, 8, 12 and 16 df."""
    path = os.path.join(CACHE_DIR, "ch11_ex5.json")
    if os.path.exists(path):
        with open(path) as f:
            return json.load(f)
    D = ex5_data()
    my, sy = float(D["y"].mean()), float(D["y"].std())
    ys, yts = (D["y"] - my) / sy, (D["yte"] - my) / sy
    rec = sorted(set(int(round(v)) for v in np.logspace(0, 5, 41)) | {0})
    inside = ex5_interior(D)
    R = dict(inside=int(inside.sum()), ybar=my, sy=sy, curves={}, units={}, ppr={})
    for lam in EX5_LAMS:
        _, h = backprop_gd(D["X"], ys, 10, lam, EX5_EPOCHS, EX5_LR, start_seed(10, 1), D["Xte"], yts, rec)
        R["curves"][str(lam)] = h
    for M in range(1, 11):
        best = None
        for s in range(1, 6):
            net = fit_net(D["X"], ys, M, 1e-4, start_seed(M, s), maxit=3000)
            if best is None or net.value < best.value:
                best = net
        fh = my + sy * best.predict(best.w, D["Xte"])[:, 0]
        R["units"][M] = dict(test=float(np.mean((D["yte"] - fh) ** 2)), inner=float(np.mean(((D["yte"] - fh) ** 2)[inside])), train=float(np.mean((D["y"] - my - sy * best.predict(best.w, D["X"])[:, 0]) ** 2)))
    for df in (5, 8, 12, 16):
        R["ppr"][str(df)] = {}
        for M in range(1, 5):
            fit = ppr_fit(D["X"], D["y"], M=M, df=df)
            e2 = (D["yte"] - ppr_predict(fit, D["Xte"])) ** 2
            R["ppr"][str(df)][M] = dict(test=float(np.mean(e2)), inner=float(np.mean(e2[inside])),
                                       train=fit["rss"] / len(D["y"]), w=[t["w"].tolist() for t in fit["terms"]])
    with open(path, "w") as f:
        json.dump(R, f)
    return R


def fig_11_s5(out_dir=None):
    """Supplementary (Exercise 11.5(b)): training and test error against epochs of back-propagation
    for four values of the weight decay."""
    import matplotlib.pyplot as plt
    R = ex5_results()
    fig, axes = plt.subplots(1, 4, figsize=(10.0, 3.0), sharey=True)
    bayes = 0.09 / R["sy"] ** 2
    for ax, lam in zip(axes, EX5_LAMS):
        h = np.array(R["curves"][str(lam)])
        e = np.maximum(h[:, 0], 1)
        ax.loglog(e, h[:, 1], color=BLUE, label="training")
        ax.loglog(e, h[:, 2], color=RED, label="test, all")
        ax.loglog(e, h[:, 3], color=ORANGE, ls="--", label="test, inside the data")
        ax.axhline(bayes, color="k", ls=":", lw=1)
        ax.set_title(r"$\lambda=%g$" % lam)
        ax.set_xlabel("epochs")
        print("  decay %g: after %d epochs training %.5f, test %.5f (inside %.5f); smallest test error %.5f at epoch %d"
              % (lam, h[-1, 0], h[-1, 1], h[-1, 2], h[-1, 3], h[:, 2].min(), h[int(np.argmin(h[:, 2])), 0]))
    axes[0].set_ylabel("mean squared error\n(standardised response)")
    axes[0].legend(frameon=False, fontsize=7.5, loc="lower left")
    fig.tight_layout()
    savefig(fig, CH, "fig11-S5", out_dir)


def fig_11_s6(out_dir=None):
    """Supplementary (Exercises 11.5(c) and 11.6): test error of networks against the number of
    hidden units, and of projection pursuit against the number of terms."""
    import matplotlib.pyplot as plt
    R = ex5_results()
    fig, axes = plt.subplots(1, 2, figsize=(8.4, 3.3), sharey=True)
    Ms = list(range(1, 11))
    axes[0].semilogy(Ms, [R["units"][str(M)]["inner"] for M in Ms], "o-", color=RED, label="test, inside the data")
    axes[0].semilogy(Ms, [R["units"][str(M)]["test"] for M in Ms], "o:", color=RED, ms=3, label="test, all points")
    axes[0].semilogy(Ms, [R["units"][str(M)]["train"] for M in Ms], "s--", color=BLUE, ms=4, label="training")
    axes[0].set_xlabel("hidden units"); axes[0].set_ylabel("mean squared error"); axes[0].set_xticks(Ms)
    axes[0].set_title("Neural network (Exercise 11.5)")
    cols = {"5": BLUE, "8": GREEN, "12": RED, "16": PURPLE}
    for df, c in cols.items():
        T = R["ppr"][df]
        axes[1].semilogy([1, 2, 3, 4], [T[str(M)]["inner"] for M in (1, 2, 3, 4)], "o-", color=c, label="df = %s" % df)
    axes[1].set_xlabel("ridge terms"); axes[1].set_xticks([1, 2, 3, 4]); axes[1].set_title("Projection pursuit (Exercise 11.6)")
    for ax in axes:
        ax.axhline(0.09, color="k", ls="--", lw=1)
    axes[0].legend(frameon=False, fontsize=7.5); axes[1].legend(frameon=False, fontsize=8)
    print("  %d of 1000 test points inside the data" % R["inside"])
    print("  network test MSE inside / all by units:", {M: (round(R["units"][str(M)]["inner"], 4), round(R["units"][str(M)]["test"], 3)) for M in Ms})
    for df in cols:
        print("  PPR df %s test MSE inside / all by terms:" % df, {M: (round(R["ppr"][df][str(M)]["inner"], 4), round(R["ppr"][df][str(M)]["test"], 3)) for M in (1, 2, 3, 4)})
    fig.tight_layout()
    savefig(fig, CH, "fig11-S6", out_dir)


# =========================================================================== Exercise 11.7: the spam data
SPAM_NAMES = ("make address all 3d our over remove internet order mail receive will people report addresses "
              "free business email you credit your font 000 money hp hpl george 650 lab labs telnet 857 data "
              "415 85 technology 1999 parts pm direct cs meeting original project re edu table conference "
              "; ( [ ! $ # CAPAVE CAPMAX CAPTOT").split()
SPAM_LAMS = (0.01, 0.1, 0.5, 1.0, 2.0, 5.0, 10.0)
SPAM_SHOW = ("!", "$", "remove", "free", "hp", "george")


def spam_data():
    """Spam data with the transformation of Section 9.1.2, log(x + 0.1), standardised with the
    training means and standard deviations; the book's split (spam.traintest: 1 = test)."""
    A = np.loadtxt(common.esl_file("spam.data"))
    test = np.loadtxt(common.esl_file("spam.traintest")).astype(int) == 1
    L = np.log(A[:, :57] + 0.1)
    mu, sd = L[~test].mean(0), L[~test].std(0)
    return (L - mu) / sd, A[:, 57].astype(int), test, mu, sd


def spam_gam():
    """The additive logistic model of Section 9.1.2 (a cubic smoothing spline with 4 df for each
    log-transformed predictor), fitted with R's gam package. Returns the test predictions and,
    for the predictors in SPAM_SHOW, the fitted terms at the training points."""
    import subprocess
    import tempfile
    Z, y, test, _, _ = spam_data()
    tmp = tempfile.mkdtemp()
    np.savetxt(os.path.join(tmp, "x.csv"), Z, delimiter=",")
    np.savetxt(os.path.join(tmp, "y.csv"), y, fmt="%d")
    np.savetxt(os.path.join(tmp, "t.csv"), test.astype(int), fmt="%d")
    cols = [SPAM_NAMES.index(n) + 1 for n in SPAM_SHOW]
    code = ('suppressMessages(library(gam)); x <- as.matrix(read.csv(file.path("{d}","x.csv"), header=FALSE)); '
            'y <- scan(file.path("{d}","y.csv"), quiet=TRUE); te <- scan(file.path("{d}","t.csv"), quiet=TRUE) == 1; '
            'd <- data.frame(x); d$y <- y; f <- as.formula(paste("y ~", paste(sprintf("s(V%d, 4)", 1:57), collapse=" + "))); '
            'fit <- gam(f, family=binomial, data=d[!te,]); p <- predict(fit, d[te,], type="response"); '
            'write.table(p, file.path("{d}","p.csv"), row.names=FALSE, col.names=FALSE); '
            'tm <- predict(fit, d[!te,], type="terms"); write.table(tm[, c({c})], file.path("{d}","terms.csv"), sep=",", row.names=FALSE, col.names=FALSE)'
            ).format(d=tmp, c=",".join(str(c) for c in cols))
    subprocess.check_call(["/usr/local/bin/Rscript", "-e", code])
    p = np.loadtxt(os.path.join(tmp, "p.csv"))
    terms = np.loadtxt(os.path.join(tmp, "terms.csv"), delimiter=",")
    return p, terms


def spam_results():
    """Exercise 11.7 (cached in cache/ch11_spam.json): ten-unit softmax networks with the weight
    decay chosen by five-fold cross-validation, against the additive model."""
    path = os.path.join(CACHE_DIR, "ch11_spam.json")
    if os.path.exists(path):
        with open(path) as f:
            return json.load(f)
    Z, y, test, mu, sd = spam_data()
    Xtr, ytr, Xte, yte = Z[~test], y[~test], Z[test], y[test]
    Ytr = np.column_stack([1 - ytr, ytr])
    rng = np.random.default_rng(117)
    fold = rng.permutation(len(ytr)) % 5
    cv = {}
    for lam in SPAM_LAMS:
        errs = []
        for k in range(5):
            tr_, va = fold != k, fold == k
            net = Net(57, 10, K=2, out="softmax").fit(Xtr[tr_], Ytr[tr_], lam=lam, seed=1170 + k, maxit=500)
            errs.append(float(np.mean(np.argmax(net.predict(net.w, Xtr[va]), 1) != ytr[va])))
        cv[str(lam)] = [float(np.mean(errs)), float(np.std(errs, ddof=1) / math.sqrt(5))]
        print("  decay %g: CV error %.4f (se %.4f)" % (lam, cv[str(lam)][0], cv[str(lam)][1]))
    lam_best = min(SPAM_LAMS, key=lambda l: cv[str(l)][0])
    test_err = {}
    best = None
    for lam in SPAM_LAMS:
        nets = [Net(57, 10, K=2, out="softmax").fit(Xtr, Ytr, lam=lam, seed=1180 + s, maxit=500) for s in range(3)]
        net = min(nets, key=lambda n: n.value)
        test_err[str(lam)] = float(np.mean(np.argmax(net.predict(net.w, Xte), 1) != yte))
        if lam == lam_best:
            best = net
    # partial dependence of the network's logit on each shown predictor, over the training inputs
    pd_ = {}
    for name in SPAM_SHOW:
        j = SPAM_NAMES.index(name)
        grid = np.quantile(Xtr[:, j], np.linspace(0, 1, 40))
        vals = []
        for gv in grid:
            Xg = Xtr.copy()
            Xg[:, j] = gv
            P = best.predict(best.w, Xg)
            vals.append(float(np.mean(np.log(P[:, 1] / P[:, 0]))))
        pd_[name] = dict(grid=grid.tolist(), logit=vals)
    pg, terms = spam_gam()
    R = dict(cv=cv, lam_best=lam_best, test=test_err, gam_test=float(np.mean((pg > 0.5) != yte)), pd=pd_,
             gam_terms={n: dict(x=Xtr[:, SPAM_NAMES.index(n)].tolist(), f=terms[:, i].tolist()) for i, n in enumerate(SPAM_SHOW)},
             mu=mu.tolist(), sd=sd.tolist(), nweights=best.nw)
    with open(path, "w") as f:
        json.dump(R, f)
    return R


def fig_11_s7(out_dir=None):
    """Supplementary (Exercise 11.7): a ten-unit network on the spam data against the additive
    model: cross-validation over the weight decay, and partial dependence of the logit on six
    predictors against the additive model's fitted functions."""
    import matplotlib.pyplot as plt
    R = spam_results()
    _, _, _, mu, sd = spam_data()
    fig = plt.figure(figsize=(10.0, 5.2))
    gs = fig.add_gridspec(2, 4)
    ax = fig.add_subplot(gs[:, 0])
    lams = list(SPAM_LAMS)
    cvm = [100 * R["cv"][str(l)][0] for l in lams]
    cvs = [100 * R["cv"][str(l)][1] for l in lams]
    ax.errorbar(lams, cvm, yerr=cvs, fmt="o-", color=BLUE, ms=4, capsize=3, label="5-fold CV")
    ax.plot(lams, [100 * R["test"][str(l)] for l in lams], "s-", color=RED, ms=4, label="test")
    ax.axhline(100 * R["gam_test"], color=GREEN, ls="--", label="additive model, test")
    ax.set_xscale("log"); ax.set_xlabel(r"weight decay $\lambda$"); ax.set_ylabel("misclassification (%)")
    ax.legend(frameon=False, fontsize=8)
    ax.set_title("10 hidden units")
    for i, name in enumerate(SPAM_SHOW):
        a = fig.add_subplot(gs[i // 3, 1 + i % 3])
        j = SPAM_NAMES.index(name)
        g = np.array(R["pd"][name]["grid"])
        nn = np.array(R["pd"][name]["logit"])
        xg = np.exp(g * sd[j] + mu[j]) - 0.1
        xs = np.exp(np.array(R["gam_terms"][name]["x"]) * sd[j] + mu[j]) - 0.1
        o = np.argsort(xs)
        f = np.array(R["gam_terms"][name]["f"])
        a.plot(xs[o], f[o] - f.mean(), color=GREEN, lw=1.6, label="additive")
        a.plot(xg, nn - nn.mean(), color=RED, lw=1.6, label="network")
        a.set_xscale("symlog", linthresh=0.1)
        a.set_title(name, fontsize=10)
        if i % 3 == 0:
            a.set_ylabel("centred logit")
    fig.axes[1].legend(frameon=False, fontsize=8)
    print("  CV choice lambda = %g; network test error %.4f; additive model test error %.4f; %d weights"
          % (R["lam_best"], R["test"][str(R["lam_best"])], R["gam_test"], R["nweights"]))
    fig.tight_layout()
    savefig(fig, CH, "fig11-S7", out_dir)


# =========================================================================== data for the browser demonstrations
def export_demo_data():
    """Write ../data/ch11-sim.json (constants of the simulated models) and ../data/ch11-zip.json
    (the five trained ZIP code networks, their test curves and 300 test digits)."""
    os.makedirs(DATA_OUT, exist_ok=True)
    sim = dict(note="Constants of the simulated data of Hastie, Tibshirani and Friedman (2009), Section 11.6. The data "
                    "themselves are drawn in the page from the seeded generator (mulberry32 + Box-Muller, rounded to 8 decimals).",
               seeds={k: list(v) for k, v in SIM_SEEDS.items()}, N=SIM_N, Ntest=SIM_NTEST,
               sigmoid=dict(varf=var_sigmoid_model(), s2=var_sigmoid_model() / 4.0),
               radial=dict(sd=math.sqrt(radial_moments()[1]), mean=radial_moments()[0], s2=0.25),
               maxit=SIM_MAXIT, rang=0.7, lam_grid=list(SIM_LAM_GRID))
    with open(os.path.join(DATA_OUT, "ch11-sim.json"), "w") as f:
        json.dump(sim, f, separators=(",", ":"))
    Z = zip_results()
    _, _, Xte, yte, demo = zip_subsets()
    zj = dict(note="ZIP code networks of Hastie, Tibshirani and Friedman (2009), Section 11.7, trained on 320 shifted "
                   "digits of zip.train (first seed); 300 shifted test digits of zip.test, pixel values times 1000.",
              nets={n: dict(layers=[list(L) for L in zip_layers(n)], counts=Z["counts"][n], weights=Z["weights"][n],
                            curve=np.round(100 * np.mean(Z["curves"][n], 0), 2).tolist())
                    for n in NETS},
              digits=np.round(1000 * Xte[demo]).astype(int).tolist(), labels=yte[demo].tolist(), epochs=ZIP_EPOCHS)
    path = os.path.join(DATA_OUT, "ch11-zip.json")
    with open(path, "w") as f:
        json.dump(zj, f, separators=(",", ":"))
    print("wrote", os.path.relpath(path, os.getcwd()), "(%.0f kB)" % (os.path.getsize(path) / 1024))


def zip_demo_reference():
    """Outputs of the exported networks on the 300 exported digits (what the page computes)."""
    with open(os.path.join(DATA_OUT, "ch11-zip.json")) as f:
        zj = json.load(f)
    X = np.array(zj["digits"], float) / 1000.0
    out = {}
    for n in NETS:
        W = [np.array(w, float) for w in zj["nets"][n]["weights"]]
        o, acts = zip_forward_np(n, W, X)
        out[n] = (o, acts)
    return out, np.array(zj["labels"])


FIGURES = {"11.1": fig_11_1, "11.3": fig_11_3, "11.4": fig_11_4, "11.5": fig_11_5, "11.S1": fig_11_s1,
           "11.S2": fig_11_s2, "11.6": fig_11_6, "11.7": fig_11_7, "11.8": fig_11_8, "11.9": fig_11_9,
           "11.11": fig_11_11, "11.S3": fig_11_s3, "11.S4": fig_11_s4, "11.S5": fig_11_s5, "11.S6": fig_11_s6,
           "11.S7": fig_11_s7}

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