"""Hastie, Tibshirani and Friedman (2009), Chapter 7: Model Assessment and Selection.

Reproduces the figures of Chapter 7 of T. Hastie, R. Tibshirani and J. Friedman, The Elements of
Statistical Learning, 2nd edition (Springer, 2009), pp. 219-260, written from scratch with numpy,
scipy and matplotlib. The methods the chapter is about are small functions meant to be read next to
the lecture notes (../ch07-model-assessment.html):

* Sections 7.2-7.3, test error and the bias-variance decomposition: knn_fits (k-nearest-neighbour
  fits for every k at once), subset_fits (least squares on the best subset of each size),
  bias_variance (squared bias, variance and prediction error over repeated training sets).
* Sections 7.4-7.6, optimism and in-sample estimates: optimism_mc (Monte Carlo estimate of the
  average optimism and of df = sum Cov(yhat_i, y_i) / sigma^2, (7.21) and (7.33)), cp_aic_bic
  ((7.26), (7.30), (7.36)), and the AIC of a logistic regression with a natural-spline coefficient
  function (phoneme_aic, (7.29)).
* Sections 7.7-7.8, BIC and MDL: bic_posterior (the model probabilities (7.41)).
* Section 7.9, VC dimension: vc_eps, vc_bound_class and vc_bound_reg ((7.46)), vc_bound_practical
  ((7.47)), and shatter_alpha (the frequency that shatters 10^-1, ..., 10^-l, Exercise 7.8).
* Section 7.10, cross-validation: cv_folds, the K-fold and leave-one-out estimates for k-NN and best
  subsets, loo_shortcut and gcv ((7.51)-(7.52)), the wrong and right way to cross-validate after
  screening (screen_cv), and decision stumps (stump_fit, stump_cv) for Section 7.10.3.
* Section 7.11, the bootstrap: the leave-one-out bootstrap (7.56), the .632 estimator (7.57), the
  no-information rate (7.58)-(7.59) and the .632+ estimator (7.60)-(7.61) in boot632.
* Best-subset search: leaps_batch sends many data sets to R's leaps package (the leaps-and-bounds
  search of Furnival and Wilson 1974) in one call; small problems use the exhaustive best_subsets.

The four simulated scenarios of Figures 7.3, 7.7, 7.9 and 7.13-7.15 (Section 7.3.1): N = 80 training
points with 20 inputs uniform on [0, 1]^20; "knn": Y = 1 if X_1 > 1/2 and 0 otherwise, fitted by
k-nearest neighbours (k = 1, ..., 50); "linear": Y = 1 if X_1 + ... + X_10 > 5 and 0 otherwise,
fitted by best-subset linear regression of size p = 1, ..., 20. "reg" uses squared error and "class"
the 0-1 loss of the rule I(fhat > 1/2) (a tie fhat = 1/2, possible for even k, costs 1/2: the
expected loss of a fair coin). 100 training sets (numpy.random.default_rng(7000 + r)) and one test
sample of 10,000 points (default_rng(7999)). The whole study is computed once by scenario_study()
(about two minutes, mostly the best-subset searches) and cached in cache/ch07_scenarios.npz.

Figures reproduced: 7.1, 7.3, 7.4, 7.5, 7.6, 7.7, 7.9, 7.10, 7.11, 7.13, 7.14, 7.15, plus two
supplementary figures: 7.S1 (an actual learning curve, standing in for the hypothetical Figure 7.8)
and 7.S2 (AIC, BIC, cross-validation and the .632 bootstrap for best subsets on the prostate data,
Exercise 7.9). Run `python3 ch07_model_assessment.py --list`, `python3 ch07_model_assessment.py`
(all figures, about two and a half minutes the first time) or `python3 ch07_model_assessment.py --fig 7.10`.
Files go to ../img/ch07/; the data of the browser demonstrations go to ../data/ (export_demo_data).

Figures not reproduced, and why:
* Figure 7.2 is a schematic drawing of the model space, the truth and the shrunken fit; nothing in
  it is computed.
* Figure 7.8 is a hypothetical learning curve drawn by hand; Figure 7.S1 computes a real one.
* Figure 7.12 is a schematic of the bootstrap process.

Settings chosen where the book gives none:
* Figure 7.1: N = 50 training points, p = 60 inputs with independent N(0, 1) entries, coefficients
  beta_j = 0.5 * 0.85^(j-1), noise standard deviation 0.45, the lasso path computed by LARS with
  the lasso modification (scikit-learn's lars_path); df is the number of nonzero coefficients (an
  unbiased estimate of the lasso's degrees of freedom, Zou, Hastie and Tibshirani 2007); test errors
  on 5,000 new points; 100 training sets (default_rng(701)).
* Figure 7.3: bias and variance over the 100 training sets at the 10,000 test points; Y has no noise
  in these scenarios, so the irreducible error is 0.
* Figure 7.4: phoneme "aa" against "ao", 1000 random training cases (default_rng(1)) and the other
  717 as test set; the coefficient function is expanded in M = 2, 4, ..., 256 natural cubic splines
  with knots equally spaced over the frequencies 1..256 (M = 256 is the unrestricted fit); d = M + 1
  with the intercept. For the 0-1 panel sigma^2 = 1/4, the largest variance of a 0/1 response.
* Figure 7.7: d = N/k for k-NN and d = p for subsets; sigma^2 = [N / (N - d)] err for k = 5 and for
  p = 20; SRM with h = d, a1 = a2 = 1, c = 1 and eta = min(1, 4 / sqrt(N)).
* Figure 7.9: the first of the 100 training sets of the "class/linear" scenario.
* Figure 7.10: N = 50 (25 per class), p = 5000 standard Gaussian inputs, the 100 inputs with the
  largest absolute correlation with the labels, 1-nearest neighbour, 5-fold cross-validation,
  50 simulations (default_rng(710 + s)); the correlations in the histogram are multiplied by the
  sign of the correlation used for the selection, so that "no information" is 0.
* Figure 7.11: N = 20 (10 per class), p = 500, stumps minimise the training misclassification
  (split points halfway between consecutive values), 5-fold cross-validation, 50 data sets. The
  4/5 - 1/5 partition of the top-right and bottom-left panels is the first random one on which the
  full-data stump of the best predictor is perfect on the held-out fifth and the refitted stump is
  not (as in the book's illustration).
* Figure 7.13: 10-fold cross-validation and the .632+ bootstrap with B = 50 bootstrap samples.
"""
import json
import math
import os
import subprocess
import tempfile

import numpy as np

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

CH = 7
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")
RSCRIPT = "/usr/local/bin/Rscript"
M32 = 0xFFFFFFFF

# the four scenarios of Section 7.3.1
N_SC = 80          # training-set size
P_SC = 20          # number of inputs
NREP = 100         # training sets
NTEST = 10000      # test points
KS = np.arange(1, 51)          # neighbourhood sizes
SIZES = np.arange(1, P_SC + 1)  # subset sizes
B_BOOT = 50


# =========================================================================== the demos' generator
def _imul(a, b):
    """32-bit integer multiplication with wrap-around, as Math.imul (result as unsigned)."""
    return (a * b) & M32


class JSRandom:
    """The seeded random numbers of the browser demos (DK.rng in courses/demo-kit.js), one call at a
    time: u() is mulberry32 and norm() the Box-Muller transform that returns r cos(theta) and keeps
    r sin(theta) for the next call, exactly as in JavaScript."""

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

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

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


def js_uniforms(seed, n, start=0):
    """Uniforms number start+1, ..., start+n of DK.rng(seed), vectorised: mulberry32 adds a constant
    to its state at each call, so the j-th output is a hash of seed + j * 0x6D2B79F5 (mod 2^32)."""
    j = np.arange(start + 1, start + n + 1, dtype=np.uint64)
    m = np.uint64(M32)
    a = (np.uint64(int(seed) & M32) + j * np.uint64(0x6D2B79F5)) & m
    t = ((a ^ (a >> np.uint64(15))) * (np.uint64(1) | a)) & m
    t = ((t + (((t ^ (t >> np.uint64(7))) * (np.uint64(61) | t)) & m)) & m) ^ t
    return ((t ^ (t >> np.uint64(14))) & m).astype(np.float64) / 4294967296.0


def js_normals(seed, n, start=0):
    """n consecutive DK.rng(seed).norm() values, the first drawn after `start` uniforms with no
    normal cached (Box-Muller pairs: cos first, then the cached sin). n must be even when more
    draws follow, so that no normal is left in the cache."""
    npair = (n + 1) // 2
    u = js_uniforms(seed, 2 * npair, start)
    u1, u2 = u[0::2], u[1::2]
    if np.any(u1 == 0.0):
        raise RuntimeError("a zero uniform: use JSRandom for this stream")
    r = np.sqrt(-2.0 * np.log(u1))
    th = 2.0 * np.pi * u2
    out = np.empty(2 * npair)
    out[0::2] = r * np.cos(th)
    out[1::2] = r * np.sin(th)
    return out[:n]


# =========================================================================== small linear algebra
def ols(X, y, intercept=True):
    """Least-squares coefficients (intercept first when intercept=True)."""
    A = np.column_stack([np.ones(len(y)), X]) if intercept else X
    return np.linalg.lstsq(A, y, rcond=None)[0]


def hat_matrix(X, intercept=True):
    A = np.column_stack([np.ones(len(X)), X]) if intercept else X
    Q, _ = np.linalg.qr(A)
    return Q @ Q.T


def ridge_smoother(X, lam):
    """Smoother matrix of ridge regression on centred X with an unpenalised intercept."""
    N = len(X)
    Xc = X - X.mean(0)
    S = Xc @ np.linalg.solve(Xc.T @ Xc + lam * np.eye(X.shape[1]), Xc.T)
    return S + np.ones((N, N)) / N


def loo_shortcut(y, S):
    """Leave-one-out residuals of a linear smoother from one fit, (7.64): (y - Sy) / (1 - S_ii)."""
    return (y - S @ y) / (1 - np.diag(S))


def gcv(y, S):
    """Generalised cross-validation (7.52)."""
    r = y - S @ y
    return float(np.mean((r / (1 - np.trace(S) / len(y))) ** 2))


# =========================================================================== best subsets
def best_subsets(X, y, kmax=None):
    """Exhaustive best subset of each size (with intercept), for small p: list of (subset, RSS)
    for sizes 0..kmax. Uses the Gram matrix and a Cholesky solve per subset."""
    import itertools
    N, p = X.shape
    kmax = p if kmax is None else kmax
    Xc = X - X.mean(0)
    yc = y - y.mean()
    G = Xc.T @ Xc
    c = Xc.T @ yc
    tss = float(yc @ yc)
    out = [((), tss)]
    for k in range(1, kmax + 1):
        best = (None, np.inf)
        for S in itertools.combinations(range(p), k):
            idx = list(S)
            b = np.linalg.solve(G[np.ix_(idx, idx)], c[idx])
            rss = tss - float(c[idx] @ b)
            if rss < best[1] - 1e-12:
                best = (S, rss)
        out.append(best)
    return out


def leaps_batch(datasets):
    """Best subsets of every size for a list of (X, y) data sets, by R's leaps package
    (leaps and bounds, exhaustive, with an intercept), in a single R session.

    Returns, per data set, a boolean array W with W[k - 1] the best subset of size k."""
    if not datasets:
        return []
    with tempfile.TemporaryDirectory() as td:
        fin, fout = os.path.join(td, "in.bin"), os.path.join(td, "out.bin")
        with open(fin, "wb") as f:
            np.array([len(datasets)], np.int32).tofile(f)
            for X, y in datasets:
                np.array(X.shape, np.int32).tofile(f)
                np.asarray(y, np.float64).tofile(f)
                np.asarray(X, np.float64).ravel(order="F").tofile(f)
        script = (
            "suppressMessages(library(leaps))\n"
            "con <- file('%s', 'rb'); out <- file('%s', 'wb'); n <- readBin(con, integer(), 1, size=4)\n"
            "for (i in seq_len(n)) { dm <- readBin(con, integer(), 2, size=4); N <- dm[1]; p <- dm[2]\n"
            "  y <- readBin(con, double(), N); X <- matrix(readBin(con, double(), N * p), N, p)\n"
            "  f <- regsubsets(X, y, nvmax=p, method='exhaustive', really.big=TRUE)\n"
            "  w <- summary(f)$which[, -1, drop=FALSE] * 1L\n"
            "  writeBin(as.integer(c(nrow(w), p)), out, size=4); writeBin(as.integer(t(w)), out, size=4) }\n"
            "close(con); close(out)\n") % (fin, fout)
        with open(os.path.join(td, "run.R"), "w") as f:
            f.write(script)
        env = dict(os.environ, OPENBLAS_NUM_THREADS="1")
        subprocess.run([RSCRIPT, os.path.join(td, "run.R")], check=True, env=env, capture_output=True)
        raw = np.fromfile(fout, dtype=np.int32)
    out, pos = [], 0
    for X, _ in datasets:
        nr, p = raw[pos], raw[pos + 1]
        pos += 2
        W = raw[pos:pos + nr * p].reshape(nr, p).astype(bool)
        pos += nr * p
        if nr < p:   # sizes that could not be fitted: repeat the largest one found
            W = np.vstack([W, np.repeat(W[-1:], p - nr, 0)])
        out.append(W)
    return out


def subset_fits(Xtr, ytr, W, Xq):
    """Predictions at Xq of least squares (with intercept) on each subset W[k-1]: (nq, len(W))."""
    F = np.empty((len(Xq), len(W)))
    for k, w in enumerate(W):
        b = ols(Xtr[:, w], ytr)
        F[:, k] = b[0] + Xq[:, w] @ b[1:]
    return F


# =========================================================================== k-nearest neighbours
def knn_fits(Xtr, ytr, Xq, ks=KS):
    """k-NN regression fits at Xq for every k in ks at once: (nq, len(ks)). A training point
    queried at itself is its own nearest neighbour (distance 0)."""
    D = ((Xq ** 2).sum(1)[:, None] - 2 * Xq @ Xtr.T + (Xtr ** 2).sum(1)[None, :])
    order = np.argsort(D, axis=1, kind="stable")
    cs = np.cumsum(ytr[order], axis=1)
    ks = np.asarray(ks)
    return cs[:, ks - 1] / ks


def loss01(F, y):
    """0-1 loss of the rule I(F > 1/2) against y in {0, 1}, with a tie F = 1/2 costing 1/2."""
    y = np.asarray(y)[:, None] if np.ndim(F) == 2 else np.asarray(y)
    return np.where(np.abs(F - 0.5) < 1e-12, 0.5, ((F > 0.5) != (y > 0.5)).astype(float))


def sqloss(F, y):
    y = np.asarray(y)[:, None] if np.ndim(F) == 2 else np.asarray(y)
    return (F - y) ** 2


# =========================================================================== the scenarios of 7.3.1
def scenario_train(r, N=N_SC, p=P_SC):
    """Training set r: X uniform on [0,1]^p, y_knn = I(X1 > 1/2), y_lin = I(X1 + ... + X10 > 5)."""
    X = np.random.default_rng(7000 + r).random((N, p))
    return X, (X[:, 0] > 0.5).astype(float), (X[:, :10].sum(1) > 5).astype(float)


def scenario_test(n=NTEST, p=P_SC):
    X = np.random.default_rng(7999).random((n, p))
    return X, (X[:, 0] > 0.5).astype(float), (X[:, :10].sum(1) > 5).astype(float)


def cv_folds(N, K, rng):
    """A random assignment of N observations to K folds of (nearly) equal size."""
    return rng.permutation(np.arange(N) % K)


def gamma_hat_reg(y, f):
    """No-information error (7.58) for squared error: mean over all pairs (i, i') of (y_i - f_i')^2."""
    return float(np.mean(y ** 2) - 2 * y.mean() * f.mean() + np.mean(f ** 2))


def gamma_hat_cls(y, f):
    """No-information error (7.59) for 0-1 loss: p1 (1 - q1) + (1 - p1) q1, with q1 the proportion
    of predictions equal to 1 (ties count 1/2)."""
    p1 = float(np.mean(y))
    q1 = float(np.mean(np.where(np.abs(f - 0.5) < 1e-12, 0.5, (f > 0.5).astype(float))))
    return p1 * (1 - q1) + (1 - p1) * q1


def plus632(err, err1, gamma):
    """The .632+ estimator (7.61) with the two safeguards of Efron and Tibshirani (1997):
    Err(1) is capped at gamma, and the relative overfitting rate R is set to 0 unless
    Err(1) > err and gamma > err (and is then at most 1)."""
    err, err1, gamma = map(np.asarray, (err, err1, gamma))
    e1 = np.minimum(err1, gamma)
    ok = (e1 > err) & (gamma > err)
    R = np.where(ok, (e1 - err) / np.where(ok, gamma - err, 1.0), 0.0)
    w = 0.632 / (1 - 0.368 * R)
    return (1 - w) * err + w * e1, R, w


def boot632(err, err1):
    """The .632 estimator (7.57)."""
    return 0.368 * np.asarray(err) + 0.632 * np.asarray(err1)


def _scenario_rep(r, Xte, ykte, ylte, W_full, W_folds, W_loo, W_boot, folds, boots):
    """All error estimates for training set r of the four scenarios (see scenario_study)."""
    X, yk, yl = scenario_train(r)
    N = len(yk)
    res = {}
    # ==== fits on the whole training set
    Fk_te, Fk_tr = knn_fits(X, yk, Xte), knn_fits(X, yk, X)
    Fl_te, Fl_tr = subset_fits(X, yl, W_full, Xte), subset_fits(X, yl, W_full, X)
    res["Fk_te"], res["Fl_te"] = Fk_te, Fl_te
    for name, Fte, Ftr, yte, ytr in (("knn", Fk_te, Fk_tr, ykte, yk), ("lin", Fl_te, Fl_tr, ylte, yl)):
        res[name + "_test_reg"] = sqloss(Fte, yte).mean(0)
        res[name + "_test_cls"] = loss01(Fte, yte).mean(0)
        res[name + "_train_reg"] = sqloss(Ftr, ytr).mean(0)
        res[name + "_train_cls"] = loss01(Ftr, ytr).mean(0)
        res[name + "_gamma_reg"] = np.array([gamma_hat_reg(ytr, Ftr[:, j]) for j in range(Ftr.shape[1])])
        res[name + "_gamma_cls"] = np.array([gamma_hat_cls(ytr, Ftr[:, j]) for j in range(Ftr.shape[1])])
    # ==== 10-fold cross-validation (fold-wise errors kept for the standard errors of Figure 7.9)
    K = folds.max() + 1
    cvk, cvl = np.zeros((N, len(KS))), np.zeros((N, len(SIZES)))
    for k in range(K):
        te = folds == k
        cvk[te] = knn_fits(X[~te], yk[~te], X[te])
        cvl[te] = subset_fits(X[~te], yl[~te], W_folds[k], X[te])
    for name, F, y in (("knn", cvk, yk), ("lin", cvl, yl)):
        Lr, Lc = sqloss(F, y), loss01(F, y)
        res[name + "_cv10_reg"], res[name + "_cv10_cls"] = Lr.mean(0), Lc.mean(0)
        res[name + "_cv10_cls_fold"] = np.array([Lc[folds == k].mean(0) for k in range(K)])
        res[name + "_cv10_reg_fold"] = np.array([Lr[folds == k].mean(0) for k in range(K)])
    # ==== leave-one-out cross-validation
    lok, lol = np.zeros((N, len(KS))), np.zeros((N, len(SIZES)))
    for i in range(N):
        m = np.arange(N) != i
        lok[i] = knn_fits(X[m], yk[m], X[i:i + 1])[0]
        lol[i] = subset_fits(X[m], yl[m], W_loo[i], X[i:i + 1])[0]
    for name, F, y in (("knn", lok, yk), ("lin", lol, yl)):
        res[name + "_loo_reg"], res[name + "_loo_cls"] = sqloss(F, y).mean(0), loss01(F, y).mean(0)
    # ==== leave-one-out bootstrap (7.56)
    for name, y, fitter in (("knn", yk, None), ("lin", yl, None)):
        num_r = np.zeros((N, len(KS) if name == "knn" else len(SIZES)))
        num_c = np.zeros_like(num_r)
        cnt = np.zeros(N)
        for b, idx in enumerate(boots):
            oob = np.setdiff1d(np.arange(N), idx)
            if len(oob) == 0:
                continue
            if name == "knn":
                F = knn_fits(X[idx], y[idx], X[oob])
            else:
                F = subset_fits(X[idx], y[idx], W_boot[b], X[oob])
            num_r[oob] += sqloss(F, y[oob])
            num_c[oob] += loss01(F, y[oob])
            cnt[oob] += 1
        ok = cnt > 0
        res[name + "_boot1_reg"] = (num_r[ok] / cnt[ok, None]).mean(0)
        res[name + "_boot1_cls"] = (num_c[ok] / cnt[ok, None]).mean(0)
    return res


def scenario_study(nrep=NREP, B=B_BOOT, refresh=False):
    """The simulation behind Figures 7.3, 7.7, 7.9 and 7.13-7.15, cached in cache/ch07_scenarios.npz.

    For each training set r: training and test errors for every k and subset size, 10-fold and
    leave-one-out cross-validation, the leave-one-out bootstrap with B samples, and the
    no-information rates; plus the test-point fits needed for the bias and variance."""
    path = os.path.join(CACHE_DIR, "ch07_scenarios.npz")
    if os.path.exists(path) and not refresh:
        z = np.load(path)
        return {k: z[k] for k in z.files}
    Xte, ykte, ylte = scenario_test()
    keys, acc = None, {}
    sum_fk, sum_fk2 = np.zeros((NTEST, len(KS))), np.zeros((NTEST, len(KS)))
    sum_fl, sum_fl2 = np.zeros((NTEST, len(SIZES))), np.zeros((NTEST, len(SIZES)))
    chunk = 10
    for r0 in range(0, nrep, chunk):
        reps = list(range(r0, min(nrep, r0 + chunk)))
        plan, jobs = {}, []
        for r in reps:
            X, yk, yl = scenario_train(r)
            N = len(yl)
            rng = np.random.default_rng(7100 + r)
            folds = cv_folds(N, 10, rng)
            boots = [rng.integers(0, N, N) for _ in range(B)]
            sl = {"full": len(jobs)}
            jobs.append((X, yl))
            sl["folds"] = len(jobs)
            jobs += [(X[folds != k], yl[folds != k]) for k in range(10)]
            sl["loo"] = len(jobs)
            jobs += [(np.delete(X, i, 0), np.delete(yl, i)) for i in range(N)]
            sl["boot"] = len(jobs)
            jobs += [(X[idx], yl[idx]) for idx in boots]
            plan[r] = (sl, folds, boots)
        W = leaps_batch(jobs)
        for r in reps:
            sl, folds, boots = plan[r]
            res = _scenario_rep(r, Xte, ykte, ylte, W[sl["full"]], W[sl["folds"]:sl["folds"] + 10],
                                W[sl["loo"]:sl["loo"] + N_SC], W[sl["boot"]:sl["boot"] + B], folds, boots)
            Fk, Fl = res.pop("Fk_te"), res.pop("Fl_te")
            sum_fk += Fk
            sum_fk2 += Fk ** 2
            sum_fl += Fl
            sum_fl2 += Fl ** 2
            if keys is None:
                keys = list(res)
                acc = {k: [] for k in keys}
            for k in keys:
                acc[k].append(res[k])
        print("  scenario study: %d of %d training sets" % (reps[-1] + 1, nrep), flush=True)
    out = {k: np.array(v) for k, v in acc.items()}
    for name, s, s2, yte in (("knn", sum_fk, sum_fk2, ykte), ("lin", sum_fl, sum_fl2, ylte)):
        mean = s / nrep
        var = np.maximum(s2 / nrep - mean ** 2, 0)
        out[name + "_bias2"] = ((mean - yte[:, None]) ** 2).mean(0)
        out[name + "_var"] = var.mean(0)
    os.makedirs(CACHE_DIR, exist_ok=True)
    np.savez(path, **out)
    return out


# =========================================================================== Section 7.4-7.6: optimism
def optimism_mc(X, f, sigma, fit, R=2000, seed=0):
    """Monte Carlo over y = f + sigma * eps (fixed X): the average optimism (7.20) and the
    degrees of freedom sum_i Cov(yhat_i, y_i) / sigma^2 of (7.33), for a fitting rule
    fit(X, y) -> fitted values. Returns dict(omega, df, err, errin)."""
    rng = np.random.default_rng(seed)
    N = len(f)
    Y = f[None, :] + sigma * rng.standard_normal((R, N))
    Fh = np.array([fit(X, y) for y in Y])
    err = ((Y - Fh) ** 2).mean(1)
    errin = sigma ** 2 + ((f[None, :] - Fh) ** 2).mean(1)      # in-sample error (7.18), exactly
    cov = ((Fh - Fh.mean(0)) * (Y - f[None, :])).sum(0) / (R - 1)
    return dict(omega=float((errin - err).mean()), df=float(cov.sum() / sigma ** 2),
                err=float(err.mean()), errin=float(errin.mean()))


def cp_aic_bic(err, d, N, sigma2):
    """C_p = AIC (7.26), (7.30) and BIC in the scale of (7.36) divided by N/sigma^2."""
    d = np.asarray(d, float)
    return dict(cp=err + 2 * d / N * sigma2, bic=err + math.log(N) * d / N * sigma2)


def bic_posterior(bic):
    """Approximate posterior model probabilities (7.41) from BIC = -2 loglik + d log N."""
    b = np.asarray(bic, float)
    w = np.exp(-0.5 * (b - b.min()))
    return w / w.sum()


# =========================================================================== Section 7.9: VC bounds
def vc_eps(h, N, eta, a1=1.0, a2=1.0):
    """epsilon of (7.46): a1 [h (log(a2 N / h) + 1) - log(eta / 4)] / N."""
    h = np.asarray(h, float)
    return a1 * (h * (np.log(a2 * N / h) + 1) - math.log(eta / 4)) / N


def vc_bound_class(err, h, N, eta, a1=1.0, a2=1.0):
    """Binary classification bound (7.46): err + eps/2 (1 + sqrt(1 + 4 err / eps))."""
    e = vc_eps(h, N, eta, a1, a2)
    return err + e / 2 * (1 + np.sqrt(1 + 4 * np.asarray(err) / e))


def vc_bound_reg(err, h, N, eta, a1=1.0, a2=1.0, c=1.0):
    """Regression bound (7.46): err / (1 - c sqrt(eps))_+ (infinite when the bracket is <= 0)."""
    e = vc_eps(h, N, eta, a1, a2)
    den = 1 - c * np.sqrt(e)
    return np.where(den > 0, np.asarray(err) / np.where(den > 0, den, 1.0), np.inf)


def vc_bound_practical(err, h, N):
    """The tuning-free regression bound (7.47), rho = h / N."""
    rho = np.asarray(h, float) / N
    den = 1 - np.sqrt(rho - rho * np.log(rho) + math.log(N) / (2 * N))
    return np.where(den > 0, np.asarray(err) / np.where(den > 0, den, 1.0), np.inf)


def shatter_alpha(labels):
    """Exercise 7.8: alpha = pi (1 + sum_i (1 - y_i) 10^i) makes I(sin(alpha z_i) > 0) = y_i at
    z_i = 10^-i, i = 1..l. Returned as an exact integer multiplier m with alpha = pi * m."""
    return 1 + sum((1 - int(y)) * 10 ** i for i, y in enumerate(labels, start=1))


# =========================================================================== Figure 7.1: lasso
LASSO_P, LASSO_SD = 60, 0.45
LASSO_BETA = 0.5 * 0.85 ** np.arange(LASSO_P)


def lasso_study(R=100, N=50, dmax=35, seed=701):
    """Training and test error along the lasso path for R training sets (Figure 7.1), indexed by
    the number of nonzero coefficients d = 0..dmax (the first point of the path with d nonzeros)."""
    import warnings
    from sklearn.linear_model import lars_path
    rng = np.random.default_rng(seed)
    Xt = rng.standard_normal((5000, LASSO_P))
    yt = Xt @ LASSO_BETA + LASSO_SD * rng.standard_normal(5000)
    tr = np.full((R, dmax + 1), np.nan)
    te = np.full((R, dmax + 1), np.nan)
    for r in range(R):
        X = rng.standard_normal((N, LASSO_P))
        y = X @ LASSO_BETA + LASSO_SD * rng.standard_normal(N)
        xm, ym = X.mean(0), y.mean()
        with warnings.catch_warnings():
            warnings.simplefilter("ignore")
            _, _, coefs = lars_path(X - xm, y - ym, method="lasso")
        for j in range(coefs.shape[1]):
            b = coefs[:, j]
            d = int(np.count_nonzero(b))
            if d <= dmax and np.isnan(tr[r, d]):
                b0 = ym - xm @ b
                tr[r, d] = np.mean((y - b0 - X @ b) ** 2)
                te[r, d] = np.mean((yt - b0 - Xt @ b) ** 2)
    return tr, te


# =========================================================================== Figure 7.4: phoneme
def ns_basis(x, n_basis, lo, hi):
    """Natural cubic spline basis with n_basis functions (n_basis - 2 interior knots equally
    spaced on [lo, hi]; the intercept is included): cubic B-splines with the constraints
    f''(lo) = f''(hi) = 0 projected out."""
    from scipy.interpolate import BSpline
    x = np.asarray(x, float)
    K = n_basis - 2
    interior = np.linspace(lo, hi, K + 2)[1:-1]
    t = np.r_[[lo] * 4, interior, [hi] * 4]
    nb = len(t) - 4
    B = BSpline.design_matrix(x, t, 3).toarray()
    C = np.zeros((2, nb))
    for r, b in enumerate((lo, hi)):
        for j in range(nb):
            c = np.zeros(nb)
            c[j] = 1
            C[r, j] = BSpline(t, c, 3).derivative(2)(b)
    _, _, Vt = np.linalg.svd(C)
    Z = Vt[2:].T
    return B @ Z


def logistic_newton(A, y, maxit=100, tol=1e-10):
    """Logistic regression by Newton-Raphson; A includes the intercept column. Returns the
    coefficients and the fitted probabilities."""
    th = np.zeros(A.shape[1])
    dev_old = np.inf
    for _ in range(maxit):
        eta = A @ th
        mu = common.sigmoid(eta)
        w = np.maximum(mu * (1 - mu), 1e-10)
        H = A.T @ (w[:, None] * A)
        th = th + np.linalg.solve(H + 1e-10 * np.eye(len(th)), A.T @ (y - mu))
        eta = A @ th
        dev = -2 * np.sum(y * eta - np.logaddexp(0, eta))
        if abs(dev_old - dev) < tol * (1 + abs(dev)):
            break
        dev_old = dev
    return th, common.sigmoid(A @ th)


PHONEME_M = (2, 4, 8, 16, 32, 64, 128, 256)


def phoneme_data(seed=1):
    d = common.esl_data("phoneme.data")
    d = d[d.g.isin(["aa", "ao"])].reset_index(drop=True)
    X = d[["x.%d" % i for i in range(1, 257)]].to_numpy(float)
    y = (d.g == "aa").to_numpy(float)
    perm = np.random.default_rng(seed).permutation(len(y))
    return X, y, perm[:1000], perm[1000:]


def phoneme_aic(Ms=PHONEME_M):
    """Training, test and AIC values for the logistic regression with an M-term natural spline
    coefficient function (Figure 7.4). Log-likelihood loss is the deviance per observation,
    -2/N loglik; AIC = -2/N loglik + 2d/N (7.29) with d = M + 1."""
    path = os.path.join(CACHE_DIR, "ch07_phoneme.json")
    if os.path.exists(path):
        with open(path) as f:
            return json.load(f)
    X, y, tr, te = phoneme_data()
    freqs = np.arange(1, 257, dtype=float)
    N = len(tr)
    out = {k: [] for k in ("M", "d", "dev_tr", "dev_te", "aic", "err_tr", "err_te", "pq")}
    for M in Ms:
        H = ns_basis(freqs, M, 1, 256)
        Z = X @ H
        A = np.column_stack([np.ones(len(y)), Z])
        th, _ = logistic_newton(A[tr], y[tr])
        eta = A @ th
        dev = -2 * (y * eta - np.logaddexp(0, eta))
        p = common.sigmoid(eta)
        d = M + 1
        out["M"].append(M)
        out["d"].append(d)
        out["dev_tr"].append(float(dev[tr].mean()))
        out["dev_te"].append(float(dev[te].mean()))
        out["aic"].append(float(dev[tr].mean() + 2 * d / N))
        out["err_tr"].append(float(np.mean((p[tr] > 0.5) != y[tr])))
        out["err_te"].append(float(np.mean((p[te] > 0.5) != y[te])))
        out["pq"].append(float(np.mean(p[tr] * (1 - p[tr]))))
    os.makedirs(CACHE_DIR, exist_ok=True)
    with open(path, "w") as f:
        json.dump(out, f)
    return out


# =========================================================================== Section 7.10.2: screening
def corr_with_labels(X, y):
    """Pearson correlation of every column of X with y."""
    Xc = X - X.mean(0)
    yc = y - y.mean()
    return (Xc.T @ yc) / np.sqrt((Xc ** 2).sum(0) * (yc @ yc))


def top_by_corr(X, y, m):
    """Indices of the m columns with the largest absolute correlation with y, and their signs."""
    c = corr_with_labels(X, y)
    idx = np.argsort(-np.abs(c), kind="stable")[:m]
    return idx, np.sign(c[idx])


def nn1_predict(Xtr, ytr, Xq):
    D = (Xq ** 2).sum(1)[:, None] - 2 * Xq @ Xtr.T + (Xtr ** 2).sum(1)[None, :]
    return ytr[np.argmin(D, axis=1)]


def screen_cv(X, y, m=100, K=5, folds=None, rng=None):
    """Cross-validated error of 'screen the m best inputs, then 1-nearest neighbour', the wrong
    way (screening once on all the data) and the right way (screening inside every fold)."""
    N = len(y)
    if folds is None:
        folds = cv_folds(N, K, rng)
    sel, _ = top_by_corr(X, y, m)
    wrong = right = 0
    for k in range(K):
        te = folds == k
        wrong += np.sum(nn1_predict(X[~te][:, sel], y[~te], X[te][:, sel]) != y[te])
        s2, _ = top_by_corr(X[~te], y[~te], m)
        right += np.sum(nn1_predict(X[~te][:, s2], y[~te], X[te][:, s2]) != y[te])
    return wrong / N, right / N


def screening_study(nsim=50, N=50, p=5000, m=100, K=5):
    """Section 7.10.2: wrong-way and right-way 5-fold CV error over nsim null data sets, and for
    the first data set the correlations (sign-adjusted) of the selected inputs with the labels
    in one held-out fold of 10 samples (Figure 7.10)."""
    path = os.path.join(CACHE_DIR, "ch07_screening.json")
    if os.path.exists(path):
        with open(path) as f:
            return json.load(f)
    y = np.repeat([0.0, 1.0], N // 2)
    wrong, right, mean_w, mean_r = [], [], [], []
    hist = None
    for s in range(nsim):
        rng = np.random.default_rng(710 + s)
        X = rng.standard_normal((N, p))
        folds = cv_folds(N, K, rng)
        w, r = screen_cv(X, y, m, K, folds)
        wrong.append(float(w))
        right.append(float(r))
        te = folds == 0                                   # one fold of 10 samples
        sel, sg = top_by_corr(X, y, m)
        cw = corr_with_labels(X[te][:, sel], y[te]) * sg
        sel2, sg2 = top_by_corr(X[~te], y[~te], m)
        cr = corr_with_labels(X[te][:, sel2], y[te]) * sg2
        mean_w.append(float(np.mean(cw)))
        mean_r.append(float(np.mean(cr)))
        if s == 0:
            hist = dict(wrong=cw.tolist(), right=cr.tolist())
    out = dict(wrong=wrong, right=right, mean_corr_wrong=mean_w, mean_corr_right=mean_r, hist=hist)
    os.makedirs(CACHE_DIR, exist_ok=True)
    with open(path, "w") as f:
        json.dump(out, f)
    return out


# =========================================================================== Section 7.10.3: stumps
def stump_errors(X, y):
    """For every column of X, the best single split (a 'stump'): the minimum number of training
    errors over split points halfway between consecutive sorted values and the two orientations.
    Returns (errors, split points, orientation): orientation +1 predicts class 1 above the split."""
    N, p = X.shape
    order = np.argsort(X, axis=0, kind="stable")
    ys = y[order]                                          # labels in sorted order, per column
    ones_left = np.cumsum(ys, axis=0)[:-1]                 # split after position i (i = 1..N-1)
    n_left = np.arange(1, N)[:, None]
    ones_tot = y.sum()
    err_up = ones_left + ((N - n_left) - (ones_tot - ones_left))   # left -> 0, right -> 1
    err_dn = N - err_up                                            # left -> 1, right -> 0
    e = np.minimum(err_up, err_dn)
    pos = np.argmin(e, axis=0)
    xs = np.take_along_axis(X, order, axis=0)
    cols = np.arange(p)
    split = 0.5 * (xs[pos, cols] + xs[pos + 1, cols])
    orient = np.where(err_up[pos, cols] <= err_dn[pos, cols], 1, -1)
    return e[pos, cols].astype(int), split, orient


def stump_predict(x, split, orient):
    return np.where(orient > 0, x > split, x <= split).astype(float)


def stump_cv(X, y, folds):
    """CV error of 'choose the best stump over all inputs' (re-selected inside every fold)."""
    wrong = 0
    for k in range(folds.max() + 1):
        te = folds == k
        e, sp, o = stump_errors(X[~te], y[~te])
        j = int(np.argmin(e))
        wrong += np.sum(stump_predict(X[te, j], sp[j], o[j]) != y[te])
    return wrong / len(y)


def stump_study(nsim=50, N=20, p=500, K=5):
    y = np.repeat([0.0, 1.0], N // 2)
    cv = []
    for s in range(nsim):
        rng = np.random.default_rng(720 + s)
        X = rng.standard_normal((N, p))
        folds = rng.permutation(np.repeat(np.arange(K), N // K))
        cv.append(float(stump_cv(X, y, folds)))
    return np.array(cv)


def binary_stump_cv(nsim=50, N=20, p=2 ** 20, K=5, seed=730):
    """Exercise 7.10: binary inputs (so no split points to estimate). Each input is a random bit
    pattern over the N samples (bit i = sample i), stored as an integer. The procedure picks the
    input with the fewest training errors (first one on ties, either orientation); 5-fold CV
    repeats the choice inside every fold. Returns (number of data sets with an input that splits
    all N samples perfectly, CV errors)."""
    y = np.repeat([0, 1], N // 2)
    ymask = int(sum(1 << i for i in range(N) if y[i]))
    full = (1 << N) - 1
    perfect, cv = 0, []
    for s in range(nsim):
        rng = np.random.default_rng(seed + s)
        V = rng.integers(0, 1 << N, size=p, dtype=np.int64)
        diff = V ^ ymask
        cnt = _popcount(diff)
        if np.any((cnt == 0) | (cnt == N)):
            perfect += 1
        folds = rng.permutation(np.repeat(np.arange(K), N // K))
        wrong = 0
        for k in range(K):
            trmask = int(sum(1 << i for i in range(N) if folds[i] != k))
            temask = full ^ trmask
            e_tr = _popcount(diff & trmask)
            ntr = int(N - N // K)
            err = np.minimum(e_tr, ntr - e_tr)
            j = int(np.argmin(err))
            flip = e_tr[j] > ntr - e_tr[j]                 # use the opposite orientation
            e_te = _popcount(np.array([diff[j] & temask]))[0]
            wrong += (N // K - e_te) if flip else e_te
        cv.append(wrong / N)
    return perfect, np.array(cv)


def _popcount(a):
    """Number of 1 bits in each entry of an int64 array (values below 2^32)."""
    a = np.asarray(a, dtype=np.int64)
    c = np.zeros(a.shape, dtype=np.int64)
    for sh in range(0, 32, 8):
        c += _POP8[(a >> sh) & 255]
    return c


_POP8 = np.array([bin(i).count("1") for i in range(256)], dtype=np.int64)


# =========================================================================== Exercise 7.9: prostate
PROSTATE_NAMES = ["lcavol", "lweight", "age", "lbph", "svi", "lcp", "gleason", "pgg45"]


def load_prostate():
    """Prostate data standardised over all 97 men as in the book; training mask of 67 cases."""
    df = common.esl_data("prostate.data")
    X = df[PROSTATE_NAMES].values.astype(float)
    y = df["lpsa"].values.astype(float)
    tr = (df["train"] == "T").values
    Z = (X - X.mean(0)) / X.std(0, ddof=1)
    return Z, y, tr


def best_subset_path(X, y):
    """Boolean masks of the best subset of sizes 0..p (exhaustive, for small p)."""
    p = X.shape[1]
    out = []
    for S, _ in best_subsets(X, y):
        w = np.zeros(p, bool)
        w[list(S)] = True
        out.append(w)
    return out


def masks_fits(Xtr, ytr, masks, Xq):
    F = np.empty((len(Xq), len(masks)))
    for k, w in enumerate(masks):
        b = ols(Xtr[:, w], ytr)
        F[:, k] = b[0] + Xq[:, w] @ b[1:]
    return F


def prostate_selection(B=200, seed=79):
    """Exercise 7.9: training error, AIC (= C_p), BIC, 5- and 10-fold CV, the .632 bootstrap and
    the test error for the best subsets of sizes 0..8 of the prostate data. sigma^2 is estimated
    by the residual variance of the full least-squares model (N - 9 degrees of freedom)."""
    Z, y, tr = load_prostate()
    X, yt, Xte, yte = Z[tr], y[tr], Z[~tr], y[~tr]
    N, p = X.shape
    masks = best_subset_path(X, yt)
    Ftr = masks_fits(X, yt, masks, X)
    err = ((Ftr - yt[:, None]) ** 2).mean(0)
    d = np.arange(p + 1) + 1.0                         # parameters including the intercept
    s2 = err[-1] * N / (N - p - 1)
    crit = cp_aic_bic(err, d, N, s2)
    test = ((masks_fits(X, yt, masks, Xte) - yte[:, None]) ** 2).mean(0)
    rng = np.random.default_rng(seed)
    out = dict(size=list(range(p + 1)), train=err.tolist(), aic=crit["cp"].tolist(), bic=crit["bic"].tolist(),
               test=test.tolist(), sigma2=s2, subsets=[[PROSTATE_NAMES[j] for j in np.flatnonzero(w)] for w in masks])
    for K in (5, 10):
        folds = cv_folds(N, K, rng)
        L = np.zeros((N, p + 1))
        for k in range(K):
            te = folds == k
            mk = best_subset_path(X[~te], yt[~te])
            L[te] = (masks_fits(X[~te], yt[~te], mk, X[te]) - yt[te][:, None]) ** 2
        fold_means = np.array([L[folds == k].mean(0) for k in range(K)])
        out["cv%d" % K] = L.mean(0).tolist()
        out["cv%d_se" % K] = (fold_means.std(0, ddof=1) / math.sqrt(K)).tolist()
    num, cnt = np.zeros((N, p + 1)), np.zeros(N)
    for b in range(B):
        idx = rng.integers(0, N, N)
        oob = np.setdiff1d(np.arange(N), idx)
        mk = best_subset_path(X[idx], yt[idx])
        num[oob] += (masks_fits(X[idx], yt[idx], mk, X[oob]) - yt[oob][:, None]) ** 2
        cnt[oob] += 1
    ok = cnt > 0
    e1 = (num[ok] / cnt[ok, None]).mean(0)
    out["boot1"] = e1.tolist()
    out["boot632"] = boot632(err, e1).tolist()
    return out


# =========================================================================== selection in the scenarios
SCEN = (("reg/KNN", "knn", "reg"), ("reg/linear", "lin", "reg"), ("class/KNN", "knn", "cls"), ("class/linear", "lin", "cls"))


def complexity(model):
    """d(alpha): N/k for k-NN (Exercise 7.6) and the subset size for best subsets."""
    return N_SC / KS if model == "knn" else SIZES.astype(float)


def selection_study(S=None, eta=None):
    """For each scenario and training set: the relative error 100 [Err_T(chosen) - min Err_T] /
    [max Err_T - min Err_T] of AIC, BIC, SRM, 10-fold CV and the .632+ bootstrap (Figures 7.7 and
    7.13), and the relative over-estimate (criterion - Err_T) / Err_T at the chosen model."""
    S = scenario_study() if S is None else S
    N = N_SC
    eta = min(1.0, 4 / math.sqrt(N)) if eta is None else eta
    out = {}
    for lab, model, loss in SCEN:
        test = S["%s_test_%s" % (model, loss)]
        train = S["%s_train_%s" % (model, loss)]
        d = complexity(model)
        j_lr = 4 if model == "knn" else len(SIZES) - 1          # k = 5, or p = 20
        s2 = N / (N - d[j_lr]) * train[:, j_lr]
        crit = {"AIC": train + 2 * d / N * s2[:, None], "BIC": train + math.log(N) * d / N * s2[:, None]}
        if loss == "reg":
            crit["SRM"] = vc_bound_reg(train, d, N, eta)
        else:
            crit["SRM"] = vc_bound_class(train, d, N, eta)
        crit["CV"] = S["%s_cv10_%s" % (model, loss)]
        gam = S["%s_gamma_%s" % (model, loss)]
        crit["Bootstrap"] = plus632(train, S["%s_boot1_%s" % (model, loss)], gam)[0]
        lo, hi = test.min(1), test.max(1)
        res = {}
        for name, C in crit.items():
            j = np.argmin(C, axis=1)
            e = test[np.arange(len(j)), j]
            res[name] = dict(rel=100 * (e - lo) / (hi - lo), over=100 * (C[np.arange(len(j)), j] - e) / e, chosen=j)
        out[lab] = res
    return out


# =========================================================================== figures
def _plt():
    import matplotlib.pyplot as plt
    return plt


def fig_7_1(out_dir=None):
    """Training error and conditional test error along the lasso path, 100 training sets."""
    plt = _plt()
    tr, te = lasso_study()
    d = np.arange(tr.shape[1])
    fig, ax = plt.subplots(figsize=(5.6, 4.0))
    for r in range(tr.shape[0]):
        ax.plot(d, te[r], color="#f4a3a3", lw=0.5, alpha=0.6)
        ax.plot(d, tr[r], color="#9ec3ef", lw=0.5, alpha=0.6)
    ax.plot(d, np.nanmean(te, 0), color=RED, lw=2.2, label=r"Err (mean of Err$_\mathcal{T}$)")
    ax.plot(d, np.nanmean(tr, 0), color=BLUE, lw=2.2, label=r"E[$\overline{\mathrm{err}}$]")
    ax.set_xlim(0, 35)
    ax.set_ylim(0, 1.25)
    ax.set_xlabel("Model complexity (df)")
    ax.set_ylabel("Prediction error")
    ax.annotate("", xy=(1, 1.19), xytext=(7, 1.19), arrowprops=dict(arrowstyle="->", lw=0.8))
    ax.text(1, 1.21, "High bias\nLow variance", fontsize=8, va="bottom")
    ax.annotate("", xy=(35, 1.19), xytext=(29, 1.19), arrowprops=dict(arrowstyle="->", lw=0.8))
    ax.text(35, 1.21, "Low bias\nHigh variance", fontsize=8, va="bottom", ha="right")
    ax.legend(loc="center right", frameon=False, fontsize=8.5)
    fig.tight_layout()
    savefig(fig, CH, "fig7-1", out_dir)
    m = np.nanmean(te, 0)
    print("  min mean test error %.3f at df %d; mean training error at df 35: %.3f" % (np.nanmin(m), np.nanargmin(m), np.nanmean(tr, 0)[35]))
    export_demo_data()


KNN_SHOW = np.array([1, 2, 3, 5, 7, 10, 15, 20, 30, 40, 50])


def fig_7_3(out_dir=None):
    """Expected prediction error, squared bias and variance for the four scenarios."""
    plt = _plt()
    S = scenario_study()
    fig, axes = plt.subplots(2, 2, figsize=(7.4, 6.4))
    for row, loss in enumerate(("reg", "cls")):
        for col, model in enumerate(("knn", "lin")):
            ax = axes[row, col]
            x = KS if model == "knn" else SIZES
            pe = S["%s_test_%s" % (model, loss)].mean(0)
            b2, v = S[model + "_bias2"], S[model + "_var"]
            sel = KNN_SHOW - 1 if model == "knn" else np.arange(len(SIZES))
            for yv, c, lab in ((pe, ORANGE, "prediction error"), (b2, GREEN, "squared bias"), (v, CYAN, "variance")):
                ax.plot(x[sel], yv[sel], "o-", color=c, ms=3.5, lw=1.4, label=lab)
            ax.set_ylim(-0.01, 0.42)
            if model == "knn":
                ax.set_xlim(52, -1)
                ax.set_xlabel("Number of neighbours k")
            else:
                ax.set_xlabel("Subset size p")
            ax.set_title("%s, %s" % ("k-NN" if model == "knn" else "Linear model",
                                     "regression" if loss == "reg" else "classification"))
            if row == 0 and col == 0:
                ax.legend(frameon=False, fontsize=8, loc="upper left")
    fig.tight_layout()
    savefig(fig, CH, "fig7-3", out_dir)
    for model in ("knn", "lin"):
        pe = S["%s_test_reg" % model].mean(0)
        print("  %s: max |PE - bias^2 - var| = %.1e" % (model, np.abs(pe - S[model + "_bias2"] - S[model + "_var"]).max()))


def fig_7_4(out_dir=None):
    """AIC for the phoneme logistic regression with M natural-spline basis functions."""
    plt = _plt()
    o = phoneme_aic()
    M = np.array(o["M"])
    d = np.array(o["d"], float)
    N = 1000
    s2 = 0.25
    aic01 = np.array(o["err_tr"]) + 2 * d / N * s2
    fig, (a1, a2) = plt.subplots(1, 2, figsize=(7.6, 3.6))
    for ax, tr, te, aic, title, yl in ((a1, o["dev_tr"], o["dev_te"], o["aic"], "Log-likelihood loss", "Deviance per observation"),
                                      (a2, o["err_tr"], o["err_te"], aic01, "0-1 loss", "Misclassification error")):
        ax.plot(M, tr, "o-", color=ORANGE, mfc="none", label="Train")
        ax.plot(M, te, "o-", color=CYAN, mfc="none", label="Test")
        ax.plot(M, aic, "o-", color=GREEN, mfc="none", label="AIC")
        ax.set_xscale("log", base=2)
        ax.set_xticks(M)
        ax.set_xticklabels([str(v) for v in M])
        ax.set_xlabel("Number of basis functions M")
        ax.set_ylabel(yl)
        ax.set_title(title)
    a1.legend(frameon=False, loc="upper left")
    fig.tight_layout()
    savefig(fig, CH, "fig7-4", out_dir)
    print("  AIC (log-lik) chooses M = %d, test deviance chooses M = %d; AIC (0-1) chooses M = %d, test error chooses M = %d"
          % (M[np.argmin(o["aic"])], M[np.argmin(o["dev_te"])], M[np.argmin(aic01)], M[np.argmin(o["err_te"])]))


def fig_7_5(out_dir=None):
    """sin(50 x) on [0, 1] and points labelled by I(sin(50 x) > 0)."""
    plt = _plt()
    x = np.linspace(0, 1, 2000)
    pts = np.random.default_rng(75).random(12)
    lab = np.sin(50 * pts) > 0
    fig, ax = plt.subplots(figsize=(6.0, 2.6))
    ax.plot(x, np.sin(50 * x), color="k", lw=1.0)
    ax.axhline(0, color=GREY, lw=0.6)
    ax.scatter(pts[lab], np.sin(50 * pts[lab]), s=36, color=GREEN, zorder=3)
    ax.scatter(pts[~lab], np.sin(50 * pts[~lab]), s=36, facecolor="white", edgecolor=BLUE, lw=1.4, zorder=3)
    ax.set_xlabel("x")
    ax.set_ylabel(r"$\sin(50x)$")
    ax.set_ylim(-1.15, 1.15)
    fig.tight_layout()
    savefig(fig, CH, "fig7-5", out_dir)


def separating_line(P, lab):
    """A line w0 + w^T x = 0 separating labelled points in the plane with margin, by linear
    programming; None if the labelling cannot be separated."""
    from scipy.optimize import linprog
    s = np.where(lab, 1.0, -1.0)
    A = -s[:, None] * np.column_stack([np.ones(len(P)), P])
    res = linprog(np.zeros(3), A_ub=A, b_ub=-np.ones(len(P)), bounds=[(None, None)] * 3, method="highs")
    return res.x if res.status == 0 else None


def fig_7_6(out_dir=None):
    """Lines in the plane shatter three points but not four."""
    plt = _plt()
    P3 = np.array([[0.2, 0.25], [0.8, 0.3], [0.45, 0.8]])
    P4 = np.array([[0.2, 0.2], [0.8, 0.2], [0.8, 0.8], [0.2, 0.8]])
    cases = [(P3, np.array([True, False, False])), (P3, np.array([False, True, False])),
             (P3, np.array([True, True, False])), (P4, np.array([True, False, True, False]))]
    fig, axes = plt.subplots(1, 4, figsize=(8.4, 2.3))
    g = np.linspace(-0.1, 1.1, 2)
    for ax, (P, lab) in zip(axes, cases):
        w = separating_line(P, lab)
        if w is not None:
            if abs(w[2]) > abs(w[1]):
                ax.plot(g, -(w[0] + w[1] * g) / w[2], color=RED, lw=1.4)
            else:
                ax.plot(-(w[0] + w[2] * g) / w[1], g, color=RED, lw=1.4)
        else:
            ax.text(0.5, 0.5, "no line", ha="center", va="center", fontsize=9, color=GREY)
        ax.scatter(P[lab, 0], P[lab, 1], s=60, color=BLUE, zorder=3)
        ax.scatter(P[~lab, 0], P[~lab, 1], s=60, facecolor="white", edgecolor=BLUE, lw=1.5, zorder=3)
        ax.set_xlim(0, 1)
        ax.set_ylim(0, 1)
        ax.set_xticks([])
        ax.set_yticks([])
        ax.set_aspect("equal")
    fig.tight_layout()
    savefig(fig, CH, "fig7-6", out_dir)


def _boxpanel(ax, data, labels, title):
    bp = ax.boxplot(data, patch_artist=True, widths=0.6, medianprops=dict(color="k"),
                    flierprops=dict(marker="o", ms=3, mfc="none", mec=GREY))
    for b in bp["boxes"]:
        b.set_facecolor("#9fd8d2")
    ax.set_xticks(range(1, len(labels) + 1))
    ax.set_xticklabels(labels, fontsize=8)
    ax.set_ylim(-3, 103)
    ax.set_ylabel("% increase over best")
    ax.set_title(title)


def fig_7_7(out_dir=None):
    """Relative error of the model chosen by AIC, BIC and SRM in the four scenarios."""
    plt = _plt()
    sel = selection_study()
    labs = [s[0] for s in SCEN]
    fig, axes = plt.subplots(1, 3, figsize=(9.6, 3.4))
    for ax, name in zip(axes, ("AIC", "BIC", "SRM")):
        _boxpanel(ax, [sel[l][name]["rel"] for l in labs], labs, name)
    fig.tight_layout()
    savefig(fig, CH, "fig7-7", out_dir)
    for name in ("AIC", "BIC", "SRM", "CV", "Bootstrap"):
        print("  %-9s median rel. error %s; mean over-estimate of chosen error %s %%" % (
            name, " ".join("%5.1f" % np.median(sel[l][name]["rel"]) for l in labs),
            " ".join("%5.1f" % np.mean(sel[l][name]["over"]) for l in labs)))


def fig_7_9(out_dir=None):
    """Test error and 10-fold CV curve (with standard errors) for one training set, class/linear."""
    plt = _plt()
    S = scenario_study()
    cv = S["lin_cv10_cls"][0]
    se = S["lin_cv10_cls_fold"][0].std(0, ddof=1) / math.sqrt(10)
    te = S["lin_test_cls"][0]
    fig, ax = plt.subplots(figsize=(5.4, 3.8))
    ax.plot(SIZES, te, "o-", color=ORANGE, ms=4, label=r"test error Err$_\mathcal{T}$")
    ax.errorbar(SIZES, cv, yerr=se, fmt="o-", color=BLUE, ms=4, capsize=2, lw=1.2, label="10-fold CV")
    j = int(np.argmin(cv))
    j1 = int(np.flatnonzero(cv <= cv[j] + se[j])[0])
    ax.axhline(cv[j] + se[j], color=GREY, lw=0.7, ls="--")
    ax.set_xlabel("Subset size p")
    ax.set_ylabel("Misclassification error")
    ax.set_ylim(0, 0.6)
    ax.legend(frameon=False)
    fig.tight_layout()
    savefig(fig, CH, "fig7-9", out_dir)
    print("  CV minimum at p = %d, one-standard-error rule p = %d, test-error minimum at p = %d"
          % (SIZES[j], SIZES[j1], SIZES[int(np.argmin(te))]))


def fig_7_10(out_dir=None):
    """Correlations of the selected inputs with the labels in a held-out fold, wrong and right way."""
    plt = _plt()
    s = screening_study()
    fig, axes = plt.subplots(2, 1, figsize=(5.4, 5.0), sharex=True)
    bins = np.linspace(-1, 1, 21)
    for ax, key, col, title in ((axes[0], "wrong", RED, "Wrong way"), (axes[1], "right", GREEN, "Right way")):
        ax.hist(s["hist"][key], bins=bins, color=col, alpha=0.8, edgecolor="white")
        ax.axvline(0, color="k", lw=0.6)
        ax.set_title(title)
        ax.set_ylabel("Frequency")
    axes[1].set_xlabel("Correlation of selected inputs with the labels (held-out fold)")
    fig.tight_layout()
    savefig(fig, CH, "fig7-10", out_dir)
    print("  mean CV error: wrong way %.3f, right way %.3f; mean held-out correlation: wrong %.3f, right %.3f"
          % (np.mean(s["wrong"]), np.mean(s["right"]), np.mean(s["mean_corr_wrong"]), np.mean(s["mean_corr_right"])))


def fig_7_11(out_dir=None):
    """Decision stumps on null data: CV behaves as it should."""
    plt = _plt()
    N, p = 20, 500
    y = np.repeat([0.0, 1.0], N // 2)
    rng = np.random.default_rng(711)
    X = rng.standard_normal((N, p))
    e, sp, o = stump_errors(X, y)
    best6 = np.argsort(e, kind="stable")[:6]
    cols = [BLUE, RED, GREEN, ORANGE, PURPLE, MAGENTA]
    j = best6[0]
    for t in range(1000):       # a 4/5 - 1/5 split on which the full-data stump is perfect but the refit is not
        folds = np.random.default_rng(7110 + t).permutation(np.repeat(np.arange(5), 4))
        te = folds == 0
        e4, sp4, o4 = stump_errors(X[~te], y[~te])
        if (np.sum(stump_predict(X[te, j], sp[j], o[j]) != y[te]) == 0
                and np.sum(stump_predict(X[te, j], sp4[j], o4[j]) != y[te]) >= 2):
            break
    e1 = np.array([np.sum(stump_predict(X[te, j], sp4[j], o4[j]) != y[te]) for j in range(p)])
    cvs = stump_study()
    fig, axes = plt.subplots(2, 2, figsize=(7.6, 6.2))
    a = axes[0, 0]
    a.scatter(np.arange(1, p + 1), e, s=6, color=GREY)
    for c, jj in zip(cols, best6):
        a.scatter(jj + 1, e[jj], s=30, color=c, zorder=3)
    a.set_xlabel("Predictor")
    a.set_ylabel("Errors on full training set")
    a = axes[0, 1]
    jit = np.random.default_rng(1).uniform(-0.15, 0.15, (2, p))
    a.scatter(e4 + jit[0], e1 + jit[1], s=6, color=GREY)
    for c, jj in zip(cols, best6):
        a.scatter(e4[jj], e1[jj], s=30, color=c, zorder=3)
    a.set_xlabel("Errors on 4/5")
    a.set_ylabel("Errors on 1/5")
    a = axes[1, 0]
    a.scatter(X[~te, j], y[~te], s=22, facecolor="white", edgecolor=GREY)
    a.scatter(X[te, j], y[te], s=30, color=[RED if v else GREEN for v in y[te]], zorder=3)
    a.axvline(sp[j], color=BLUE, lw=1.2)
    a.axvline(sp4[j], color=ORANGE, lw=1.2, ls="--")
    a.text(sp[j], 1.12, "full", color=BLUE, ha="center", fontsize=8)
    a.text(sp4[j], -0.2, "4/5", color=ORANGE, ha="center", fontsize=8)
    a.set_ylim(-0.3, 1.25)
    a.set_yticks([0, 1])
    a.set_xlabel("Predictor %d (blue)" % (j + 1))
    a.set_ylabel("Class label")
    a = axes[1, 1]
    bp = a.boxplot([cvs], widths=0.5, patch_artist=True, medianprops=dict(color="k"))
    bp["boxes"][0].set_facecolor("#9fd8d2")
    a.set_ylim(0, 1)
    a.set_xticks([1])
    a.set_xticklabels(["50 data sets"])
    a.set_ylabel("CV errors")
    fig.tight_layout()
    savefig(fig, CH, "fig7-11", out_dir)
    print("  best stump: predictor %d, %d training errors; split %d: refitted on 4/5 it makes %d of 4 errors on 1/5; "
          "mean 5-fold CV error over 50 data sets %.3f (sd %.3f)" % (j + 1, e[j], t, e1[j], cvs.mean(), cvs.std(ddof=1)))


def fig_7_13(out_dir=None):
    """Relative error of the model chosen by 10-fold CV and the .632+ bootstrap."""
    plt = _plt()
    sel = selection_study()
    labs = [s[0] for s in SCEN]
    fig, axes = plt.subplots(1, 2, figsize=(7.0, 3.4))
    for ax, name, title in zip(axes, ("CV", "Bootstrap"), ("Cross-validation", "Bootstrap (.632+)")):
        _boxpanel(ax, [sel[l][name]["rel"] for l in labs], labs, title)
    fig.tight_layout()
    savefig(fig, CH, "fig7-13", out_dir)


def fig_7_14(out_dir=None):
    """Conditional test error, 10-fold and leave-one-out CV curves for 100 training sets (reg/linear)."""
    plt = _plt()
    S = scenario_study()
    T, C10, CN = S["lin_test_reg"], S["lin_cv10_reg"], S["lin_loo_reg"]
    Err = T.mean(0)
    fig, axes = plt.subplots(2, 2, figsize=(7.4, 6.2))
    for ax, A, title in ((axes[0, 0], T, "Prediction error"), (axes[0, 1], C10, "10-fold CV error"),
                         (axes[1, 0], CN, "Leave-one-out CV error")):
        for r in range(len(A)):
            ax.plot(SIZES, A[r], color="#bbbbbb", lw=0.5)
        ax.plot(SIZES, Err, color=RED, lw=2.2)
        if A is not T:
            ax.plot(SIZES, A.mean(0), color="k", lw=2.0)
        ax.set_ylim(0.05, 0.45)
        ax.set_title(title)
        ax.set_xlabel("Subset size p")
        ax.set_ylabel("Error")
    ax = axes[1, 1]
    ax.plot(SIZES, np.abs(C10 - Err).mean(0), "o-", color=ORANGE, ms=3, label=r"E$|$CV$_{10}$ - Err$|$")
    ax.plot(SIZES, np.abs(C10 - T).mean(0), "o-", color=BLUE, ms=3, label=r"E$|$CV$_{10}$ - Err$_\mathcal{T}|$")
    ax.plot(SIZES, np.abs(CN - T).mean(0), "o-", color=GREEN, ms=3, label=r"E$|$CV$_N$ - Err$_\mathcal{T}|$")
    ax.set_title("Approximation error")
    ax.set_xlabel("Subset size p")
    ax.set_ylabel("Mean absolute deviation")
    ax.legend(frameon=False, fontsize=8)
    fig.tight_layout()
    savefig(fig, CH, "fig7-14", out_dir)
    print("  mean |CV10 - Err| %.4f, |CV10 - Err_T| %.4f, |CVN - Err_T| %.4f (averaged over sizes);"
          " sd over training sets at p = 10: Err_T %.4f, CV10 %.4f, CVN %.4f"
          % (np.abs(C10 - Err).mean(), np.abs(C10 - T).mean(), np.abs(CN - T).mean(),
             T[:, 9].std(ddof=1), C10[:, 9].std(ddof=1), CN[:, 9].std(ddof=1)))


def fig_7_15(out_dir=None):
    """CV estimates against the conditional error, and their correlation by subset size."""
    plt = _plt()
    S = scenario_study()
    T, C10, CN = S["lin_test_reg"], S["lin_cv10_reg"], S["lin_loo_reg"]
    Err = T.mean(0)
    fig, axes = plt.subplots(2, 2, figsize=(7.2, 6.6))
    for ax, p in zip((axes[0, 0], axes[0, 1], axes[1, 0]), (1, 5, 10)):
        j = p - 1
        ax.scatter(T[:, j], CN[:, j], s=10, color=GREEN, label="leave-one-out")
        ax.scatter(T[:, j], C10[:, j], s=10, color=BLUE, label="10-fold")
        ax.axvline(Err[j], color=GREY, ls="--", lw=0.8)
        ax.axhline(Err[j], color=GREY, ls="--", lw=0.8)
        ax.set_xlim(0.08, 0.42)
        ax.set_ylim(0.05, 0.45)
        ax.set_title("Subset size %d" % p)
        ax.set_xlabel(r"Prediction error Err$_\mathcal{T}$")
        ax.set_ylabel("CV error")
    axes[0, 0].legend(frameon=False, fontsize=8, loc="upper left")
    ax = axes[1, 1]
    cn = [np.corrcoef(T[:, j], CN[:, j])[0, 1] for j in range(len(SIZES))]
    c10 = [np.corrcoef(T[:, j], C10[:, j])[0, 1] for j in range(len(SIZES))]
    ax.plot(SIZES, cn, "o-", color=GREEN, ms=3, label="leave-one-out")
    ax.plot(SIZES, c10, "o-", color=BLUE, ms=3, label="10-fold")
    ax.axhline(0, color="k", lw=0.5)
    ax.set_xlabel("Subset size p")
    ax.set_ylabel("Correlation")
    ax.legend(frameon=False, fontsize=8)
    fig.tight_layout()
    savefig(fig, CH, "fig7-15", out_dir)
    print("  correlation(CV10, Err_T) by size:", " ".join("%.2f" % v for v in c10))
    print("  correlation(CVN, Err_T) by size: ", " ".join("%.2f" % v for v in cn))


def learning_curve(Ns=(12, 15, 20, 25, 30, 40, 50, 60, 80, 100, 120, 160, 200), R=200, K=5):
    """Supplementary to Figure 7.8: the expected error Err(N) of a linear-regression classifier on
    X_1..X_10 in the 'class/linear' scenario, and the expected K-fold CV estimate at each N."""
    path = os.path.join(CACHE_DIR, "ch07_learning.json")
    if os.path.exists(path):
        with open(path) as f:
            return json.load(f)
    Xte, _, yte = scenario_test()
    Xte = Xte[:, :10]
    err, cv = [], []
    for N in Ns:
        e, c = [], []
        for r in range(R):
            rng = np.random.default_rng(10000 * N + r)
            X = rng.random((N, 10))
            y = (X.sum(1) > 5).astype(float)
            b = ols(X, y)
            e.append(np.mean(((b[0] + Xte @ b[1:]) > 0.5) != yte))
            folds = cv_folds(N, K, rng)
            wrong = 0
            for k in range(K):
                t = folds == k
                bk = ols(X[~t], y[~t])
                wrong += np.sum(((bk[0] + X[t] @ bk[1:]) > 0.5) != y[t])
            c.append(wrong / N)
        err.append(float(np.mean(e)))
        cv.append(float(np.mean(c)))
    out = dict(N=list(Ns), err=err, cv=cv)
    os.makedirs(CACHE_DIR, exist_ok=True)
    with open(path, "w") as f:
        json.dump(out, f)
    return out


def fig_7_s1(out_dir=None):
    """Supplementary: a computed learning curve, and the bias of 5-fold CV along it."""
    plt = _plt()
    o = learning_curve()
    N = np.array(o["N"])
    fig, ax = plt.subplots(figsize=(5.4, 3.6))
    ax.plot(N, 1 - np.array(o["err"]), "o-", color=BLUE, ms=4, label="1 - Err(N)")
    ax.plot(N, 1 - np.array(o["cv"]), "s--", color=ORANGE, ms=4, label="1 - E[5-fold CV] at N")
    ax.set_xlabel("Size of training set N")
    ax.set_ylabel("1 - Err")
    ax.set_ylim(0.5, 1.0)
    ax.legend(frameon=False, loc="lower right")
    fig.tight_layout()
    savefig(fig, CH, "fig7-S1", out_dir)
    for n in (20, 50, 200):
        i = list(N).index(n)
        print("  N = %d: Err %.3f, E CV5 %.3f (bias %+.3f)" % (n, o["err"][i], o["cv"][i], o["cv"][i] - o["err"][i]))


def fig_7_s2(out_dir=None):
    """Supplementary (Exercise 7.9): error estimates for best subsets on the prostate data."""
    plt = _plt()
    o = prostate_selection()
    k = np.array(o["size"])
    fig, ax = plt.subplots(figsize=(6.0, 3.9))
    ax.plot(k, o["train"], "o-", color=GREY, ms=4, label="training error")
    ax.plot(k, o["aic"], "o-", color=GREEN, ms=4, label=r"AIC = $C_p$")
    ax.plot(k, o["bic"], "o-", color=PURPLE, ms=4, label="BIC")
    ax.errorbar(k + 0.06, o["cv10"], yerr=o["cv10_se"], fmt="o-", color=BLUE, ms=4, capsize=2, lw=1.2, label="10-fold CV")
    ax.plot(k, o["cv5"], "s--", color=CYAN, ms=4, label="5-fold CV")
    ax.plot(k, o["boot632"], "^-", color=ORANGE, ms=4, label=".632 bootstrap")
    ax.plot(k, o["test"], "D-", color=RED, ms=4, label="test error (30 cases)")
    ax.set_ylim(0.3, 1.0)
    ax.set_xlabel("Subset size k")
    ax.set_ylabel("Mean squared error")
    ax.legend(frameon=False, fontsize=7.5, ncol=2)
    fig.tight_layout()
    savefig(fig, CH, "fig7-S2", out_dir)
    for key in ("aic", "bic", "cv5", "cv10", "boot632", "test"):
        print("  %-8s chooses k = %d" % (key, int(np.argmin(o[key]))))


# =========================================================================== the demonstrations
# The three browser demonstrations draw their random numbers with DK.rng (demo-kit.js); the functions
# below repeat the same computations in Python with the same random streams (js_uniforms, js_normals).

# ==== optimism-cp-demo.html
OPT_ORDER = [0, 1, 4, 3, 7, 5, 2, 6]      # lcavol, lweight, svi, lbph, pgg45, lcp, age, gleason
OPT_NOISE_SEED = 7001
OPT_SEED = 7002
OPT_QMAX = 12


def optimism_design(q):
    """Prostate training inputs (67 x 8, standardised as in the book) followed by q pure-noise
    columns (DK.rng(7001), normals drawn row by row for 12 columns, of which the first q are used),
    and the 'truth' f: the full least-squares fit of lpsa on the 8 real inputs."""
    Z, y, tr = load_prostate()
    X8, y8 = Z[tr], y[tr]
    N = len(y8)
    E = js_normals(OPT_NOISE_SEED, N * OPT_QMAX).reshape(N, OPT_QMAX)
    X = np.column_stack([X8, E[:, :q]])
    b = ols(X8, y8)
    f = b[0] + X8 @ b[1:]
    sig = math.sqrt(np.sum((y8 - f) ** 2) / (N - 9))
    return X, f, sig


def forward_path(X, y):
    """Forward-stepwise fitted values for sizes 0..p (with intercept): the variable that most
    reduces the RSS enters (lowest index on ties), via Gram-Schmidt on centred columns."""
    N, p = X.shape
    Zc = X - X.mean(0)
    r = y - y.mean()
    fits = [np.full(N, y.mean())]
    used = np.zeros(p, bool)
    cur = fits[0].copy()
    for _ in range(p):
        best, bj = -1.0, -1
        for j in range(p):
            if used[j]:
                continue
            nz = Zc[:, j] @ Zc[:, j]
            if nz < 1e-10:
                continue
            g = (r @ Zc[:, j]) ** 2 / nz
            if g > best + 1e-12:
                best, bj = g, j
        if bj < 0:
            break
        q = Zc[:, bj] / math.sqrt(Zc[:, bj] @ Zc[:, bj])
        used[bj] = True
        a = q @ r
        cur = cur + a * q
        r = r - a * q
        fits.append(cur.copy())
        for j in range(p):
            if not used[j]:
                Zc[:, j] = Zc[:, j] - (q @ Zc[:, j]) * q
    return np.array(fits)


def optimism_demo(q=0, method="fixed", noise=1.0, R=400):
    """The Monte Carlo of the optimism demo: for sizes k = 0..8+q, the means over R simulated
    responses y = f + sigma eps of err, Err_in, C_p (known sigma^2), BIC, the estimated optimism
    and df = sum_i E[yhat_i (y_i - f_i)] / sigma^2, and how often C_p, BIC and the oracle
    (smallest Err_in) choose each k. eps from DK.rng(7002), R x N normals row by row."""
    X, f, sig0 = optimism_design(q)
    sigma = noise * sig0
    N, p = X.shape
    order = OPT_ORDER + list(range(8, 8 + q))
    H = [np.full((N, N), 1.0 / N)] + [hat_matrix(X[:, order[:k]]) for k in range(1, p + 1)]
    Eps = js_normals(OPT_SEED, R * N).reshape(R, N)
    d = np.arange(p + 1) + 1.0
    err = np.zeros((R, p + 1))
    errin = np.zeros((R, p + 1))
    s_fe, s_f = np.zeros((p + 1, N)), np.zeros((p + 1, N))
    s_e = np.zeros(N)
    for r in range(R):
        e = sigma * Eps[r]
        y = f + e
        F = np.array([h @ y for h in H]) if method == "fixed" else forward_path(X, y)
        err[r] = ((F - y) ** 2).mean(1)
        errin[r] = sigma ** 2 + ((F - f) ** 2).mean(1)
        s_fe += F * e
        s_f += F
        s_e += e
    cov = ((s_fe - s_f * s_e / R) / (R - 1)).sum(1)     # sum over i of the sample Cov(yhat_i, y_i)
    cp = err + 2 * d / N * sigma ** 2
    bic = err + math.log(N) * d / N * sigma ** 2
    pick = lambda A: np.bincount(np.argmin(A, axis=1), minlength=p + 1) / R  # noqa: E731
    return dict(err=err.mean(0), errin=errin.mean(0), cp=cp.mean(0), bic=bic.mean(0),
                omega=(errin - err).mean(0), theory=2 * d / N * sigma ** 2, df=cov / sigma ** 2,
                pick_cp=pick(cp), pick_bic=pick(bic), pick_oracle=pick(errin), sigma=sigma)


# ==== cv-screening-demo.html
SCR_N = 50


def _nn1_direct(Xtr, ytr, Xq):
    """1-nearest neighbour with distances summed coordinate by coordinate (as in the browser)."""
    D = ((Xq[:, None, :] - Xtr[None, :, :]) ** 2).sum(2)
    return ytr[np.argmin(D, axis=1)]


def screening_demo_run(s, p=5000, m=100, K=5, delta=0.0, rule="corr", seed=7100, ntest=200):
    """One simulated data set of the screening demo. Inputs: column by column, N = 50 normals per
    column from DK.rng(seed + s), class 1 (odd i) shifted by delta in the first 10 inputs; folds
    from a Fisher-Yates shuffle with the same generator (fold of perm[t] = t mod K). Returns the
    wrong-way and right-way CV errors, the test error of the final classifier (ntest points from
    DK.rng(seed + 50000 + s), only the selected inputs drawn), and the held-out correlations of
    fold 0 (wrong and right way, sign adjusted)."""
    N = SCR_N
    y = (np.arange(N) % 2).astype(float)
    X = js_normals(seed + s, N * p).reshape(p, N).T.copy()
    X[:, :10] += delta * y[:, None]
    u = js_uniforms(seed + s, N - 1, start=N * p)
    perm = np.arange(N)
    for t, i in enumerate(range(N - 1, 0, -1)):
        j = int(math.floor(u[t] * (i + 1)))
        perm[i], perm[j] = perm[j], perm[i]
    folds = np.empty(N, int)
    folds[perm] = np.arange(N) % K

    def select(Xs, ys):
        if rule == "corr":
            c = corr_with_labels(Xs, ys)
            idx = np.argsort(-np.abs(c), kind="stable")[:m]
            return idx, np.sign(c[idx])
        v = Xs.var(0)
        idx = np.argsort(-v, kind="stable")[:m]
        return idx, np.ones(m)

    sel, sg = select(X, y)
    wrong = right = 0
    hold = folds == 0
    cw = cr = None
    for k in range(K):
        te = folds == k
        wrong += np.sum(_nn1_direct(X[~te][:, sel], y[~te], X[te][:, sel]) != y[te])
        s2, sg2 = select(X[~te], y[~te])
        right += np.sum(_nn1_direct(X[~te][:, s2], y[~te], X[te][:, s2]) != y[te])
        if k == 0:
            cw = corr_with_labels(X[te][:, sel], y[te]) * sg
            cr = corr_with_labels(X[te][:, s2], y[te]) * sg2
    yt = (np.arange(ntest) % 2).astype(float)
    T = js_normals(seed + 50000 + s, ntest * m).reshape(ntest, m)
    T += delta * yt[:, None] * (sel < 10)[None, :]
    test = float(np.mean(_nn1_direct(X[:, sel], y, T) != yt))
    return dict(wrong=wrong / N, right=right / N, test=test, cw=cw, cr=cr, hold=int(hold.sum()))


# ==== bootstrap-632-demo.html
BOOT_SEED = 7300
BOOT_TEST_SEED = 7777
BOOT_NTEST = 5000


def mixture_means():
    """The 20 means of the simulated mixture of Chapter 2 (first 10: class 0, next 10: class 1)."""
    path = os.path.join(CACHE_DIR, "mixture_means.csv")
    if not os.path.exists(path):
        os.makedirs(CACHE_DIR, exist_ok=True)
        code = ('load("%s"); write.csv(ESL.mixture$means, "%s", row.names=FALSE)'
                % (common.esl_file("ESL.mixture.rda"), path))
        subprocess.check_call([RSCRIPT, "-e", code])
    M = np.loadtxt(path, delimiter=",", skiprows=1)
    return M[:, :2]


def mixture_draw(seed, n, null, start=0):
    """n points from DK.rng(seed): per point a uniform for the mean index and two normals (one
    Box-Muller pair); point i has label i mod 2 and mean index 10 (i mod 2) + floor(10 u) (or
    floor(20 u) when null, so that x is independent of the label). Standard deviation sqrt(0.2)."""
    M = mixture_means()
    u = js_uniforms(seed, 3 * n, start).reshape(n, 3)
    y = (np.arange(n) % 2).astype(int)
    idx = np.floor(20 * u[:, 0]).astype(int) if null else 10 * y + np.floor(10 * u[:, 0]).astype(int)
    r = np.sqrt(-2.0 * np.log(u[:, 1]))
    th = 2.0 * np.pi * u[:, 2]
    X = M[idx] + math.sqrt(0.2) * np.column_stack([r * np.cos(th), r * np.sin(th)])
    return X, y


def mixture_posterior(X, null):
    if null:
        return np.full(len(X), 0.5)
    M = mixture_means()
    D = ((X[:, None, :] - M[None, :, :]) ** 2).sum(2)
    W = np.exp(-(D - D.min(1, keepdims=True)) / (2 * 0.2))
    return W[:, 10:].sum(1) / W.sum(1)


def knn_vote(order, counts, ylab, k):
    """Majority vote of the k nearest points of a multiset (counts[j] copies of point j), walking
    the distance order of one query point; partial blocks count only the copies needed."""
    need, s = k, 0
    for j in order:
        c = counts[j]
        if c == 0:
            continue
        t = min(c, need)
        s += t * ylab[j]
        need -= t
        if need == 0:
            break
    return 1 if 2 * s > k else 0


def boot_demo_run(run, k=1, N=200, null=False, B=50):
    """One data set of the bootstrap demo: the training error, Err_boot (7.54), the leave-one-out
    bootstrap (7.56), .632 (7.57), gamma (7.59), R and .632+ (7.60)-(7.61), 10-fold CV with
    contiguous folds, leave-one-out CV, and the test error over 5000 points of DK.rng(7777) with
    the exact class probabilities."""
    X, y = mixture_draw(BOOT_SEED + run, N, null)
    D = ((X[:, None, :] - X[None, :, :]) ** 2).sum(2)
    order = np.argsort(D, axis=1, kind="stable")
    ones = np.ones(N, int)
    fit = np.array([knn_vote(order[i], ones, y, k) for i in range(N)])
    err = float(np.mean(fit != y))
    loo = np.array([knn_vote(order[i][order[i] != i], ones, y, k) for i in range(N)])
    folds = np.floor(np.arange(N) * 10 / N).astype(int)
    cv10 = np.array([knn_vote(order[i], (folds != folds[i]).astype(int), y, k) for i in range(N)])
    u = js_uniforms(BOOT_SEED + run, B * N, start=3 * N).reshape(B, N)
    tot = cnt_all = 0.0
    num1, cnt1 = np.zeros(N), np.zeros(N)
    for b in range(B):
        idx = np.floor(u[b] * N).astype(int)
        c = np.bincount(idx, minlength=N)
        for i in range(N):
            wrong = knn_vote(order[i], c, y, k) != y[i]
            tot += wrong
            cnt_all += 1
            if c[i] == 0:
                num1[i] += wrong
                cnt1[i] += 1
    ok = cnt1 > 0
    e1 = float(np.mean(num1[ok] / cnt1[ok]))
    p1, q1 = float(np.mean(y)), float(np.mean(fit))
    gam = p1 * (1 - q1) + (1 - p1) * q1
    e632p, Rr, w = plus632(err, e1, gam)
    Xt, _ = mixture_draw(BOOT_TEST_SEED, BOOT_NTEST, null)
    post = mixture_posterior(Xt, null)
    Dt = ((Xt[:, None, :] - X[None, :, :]) ** 2).sum(2)
    nn = np.argsort(Dt, axis=1, kind="stable")[:, :k]
    g = (2 * y[nn].sum(1) > k).astype(int)
    errT = float(np.mean(np.where(g == 1, 1 - post, post)))
    return dict(err=err, boot=tot / cnt_all, e1=e1, e632=float(boot632(err, e1)), gamma=gam, R=float(Rr),
                e632p=float(e632p), cv10=float(np.mean(cv10 != y)), loo=float(np.mean(loo != y)), errT=errT)


def export_demo_data():
    """Data files of the three demonstrations: the prostate training inputs and response, and the
    20 means of the Chapter 2 mixture."""
    os.makedirs(DATA_OUT, exist_ok=True)
    Z, y, tr = load_prostate()
    out = dict(note="Prostate cancer data (Stamey et al. 1989), training set of 67 men; the 8 inputs are standardised "
                    "over all 97 men as in Hastie, Tibshirani and Friedman (2009), Section 3.2.1.",
               names=PROSTATE_NAMES, X=Z[tr].tolist(), y=y[tr].tolist(), order=OPT_ORDER,
               noise_seed=OPT_NOISE_SEED)
    with open(os.path.join(DATA_OUT, "ch07-prostate.json"), "w") as f:
        json.dump(out, f, separators=(",", ":"))
    M = mixture_means()
    with open(os.path.join(DATA_OUT, "ch07-mixture.json"), "w") as f:
        json.dump(dict(note="Means of the simulated two-class mixture of Hastie, Tibshirani and Friedman (2009), "
                            "Section 2.3.3 (first 10: class 0, next 10: class 1); each point is a mean plus N(0, 0.2 I).",
                       means=M.tolist(), sigma2=0.2), f, separators=(",", ":"))
    print("wrote", os.path.relpath(os.path.join(DATA_OUT, "ch07-prostate.json"), os.getcwd()), "and ch07-mixture.json")


FIGURES = {"7.1": fig_7_1, "7.3": fig_7_3, "7.4": fig_7_4, "7.5": fig_7_5, "7.6": fig_7_6, "7.7": fig_7_7,
           "7.S1": fig_7_s1, "7.9": fig_7_9, "7.10": fig_7_10, "7.11": fig_7_11, "7.13": fig_7_13,
           "7.14": fig_7_14, "7.15": fig_7_15, "7.S2": fig_7_s2}

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