"""Wasserman (2004), Chapter 22: Classification.

Companion code for Chapter 22 of L. Wasserman, All of Statistics: A Concise Course in Statistical
Inference (Springer, 2004), pp. 349-379, written from scratch with numpy, scipy and matplotlib. The
functions are short and meant to be read next to the lecture notes (../ch22-classification.html):

* Data: coris (the South African heart disease data of Examples 22.2-22.15), spam (Exercises 22.3, 22.5,
  22.8, 22.11, 22.12) and glass from the book's website; iris (Exercises 22.6 and 22.9; the book's
  website no longer carries it, so the copy bundled with scikit-learn is used, Fisher 1936).
* Sections 22.2-22.3, the Bayes rule and Gaussian classifiers: lda_fit and qda_fit (the plug-in rules
  (22.12)-(22.17) with the maximum likelihood estimates of the book), discriminants, fisher_direction
  (Theorem 22.10) and confusion.
* Section 22.4, regression: logistic_fit (Newton-Raphson, i.e. reweighted least squares, with aliased
  columns dropped as R does) and linreg_fit (least squares on the 0/1 labels).
* Section 22.6, naive Bayes: nb_fit (Gaussian or kernel density estimates of each coordinate).
* Section 22.7, trees: grow_tree (greedy binary splits by deviance or by the size-weighted Gini index,
  with the stopping rules of R's tree package), prune_sequence (weakest-link pruning by
  misclassification), tree_cv (K-fold cross-validation of the tree size) and draw_tree.
* Section 22.8, error rates: kfold_ids, cv_error, hoeffding_eps (Hoeffding, and Hoeffding with the
  union bound, Theorems 22.16-22.17), vc_eps (Theorems 22.18-22.19), shatter coefficients (exact for
  half-lines, intervals, unions of k intervals and half-planes; Sauer's bound, Theorem 22.21) and the
  union-of-intervals experiment of the second demonstration (erm_runs, sup_deviation).
* Sections 22.9-22.10, support vector machines and kernels: smo (the dual (22.40)/(22.43) by sequential
  minimal optimisation with the maximal violating pair), svm_offset, the duality bounds, kernels and
  kernel_fisher (the kernelised Fisher discriminant of Section 22.10).
* Section 22.11, other classifiers: knn_predict, bagged trees and adaboost (stumps).
* Exercises: median_nn_radius (Exercise 22.10) and friedman_error (Exercise 22.13).
* JSRandom and js_normals: the seeded generator of the browser demonstrations (DK.rng in
  courses/demo-kit.js), so that their simulations can be reproduced here number for number.

Figures. Reproduced from data or simulation: 22.1 (simulated, linearly separable data and a linear
rule), 22.4 (the CORIS tree on tobacco and age), 22.5 (training and cross-validated error of 18 nested
logistic models), 22.7 (the CORIS tree pruned to six leaves by cross-validation), 22.8 (the maximum
margin hyperplane, simulated) and 22.9 (a quadratic feature map makes elliptical classes linearly
separable, simulated). Skipped, because nothing in them is computed: 22.2 and 22.3 (a hypothetical
two-split tree and its partition, drawn by hand to explain the idea) and 22.6 (a diagram of the
training and validation sets).
Supplementary figures:
  22.S1 Example 22.2: LDA, QDA and logistic boundaries for systolic blood pressure and tobacco;
  22.S2 the Bayes rule against LDA, QDA and logistic regression, and their excess risk (demo 1);
  22.S3 empirical risk minimisation over unions of k intervals: the union and VC guarantees (demo 2);
  22.S4 the hard-margin dual solved by SMO: lower and upper bounds closing on the optimum (demo 3);
  22.S5 cross-validation of the tree size, and the root split under three impurity criteria (Example 22.15);
  22.S6 the spam data: bagging and boosting against a single tree (Exercises 22.11 and 22.12);
  22.S7 nearest neighbours: the curse of dimensionality (Exercise 22.10) and k chosen by
        cross-validation on the iris and glass data (Exercise 22.9);
  22.S8 the classification bias-variance formula of Exercise 22.13.
Run `python3 ch22_classification.py --list`, `python3 ch22_classification.py` (the JSON file and all
fourteen figures: about 20 seconds on one CPU thread once the spam computations are cached in
cache/ch22_spam.json, about 90 seconds the first time) or `python3 ch22_classification.py --fig 22.5`.
Files go to ../img/ch22/. The data used by the demonstrations go to ../data/ch22-svm.json
(export_json); the other two demonstrations simulate their data.
"""
import json
import math
import os

import numpy as np
from scipy import linalg, stats

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

CH = 22
HERE = os.path.dirname(os.path.abspath(__file__))
CACHE_DIR = os.path.join(HERE, "cache")
M32 = 0xFFFFFFFF


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


class JSRandom:
    """The seeded random numbers of the browser demos (DK.rng in courses/demo-kit.js): u() is
    mulberry32 and norm() the Box-Muller transform that returns r cos(t) and keeps r sin(t) 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)


# =========================================================================== data
CORIS_NAMES = ["sbp", "tobacco", "ldl", "adiposity", "famhist", "typea", "obesity", "alcohol", "age"]


def coris():
    """The CORIS data: (X, y, names), X the 9 covariates (462 x 9), y = chd (0/1)."""
    import pandas as pd
    d = pd.read_csv(common.aos_file("coris.dat"), skiprows=4, header=None)
    d = d.iloc[:, 1:].to_numpy(float)
    return d[:, :9], d[:, 9].astype(int), list(CORIS_NAMES)


def spam():
    """The spam data (4601 messages, 57 covariates; y = 1 for spam, the last column)."""
    d = np.loadtxt(common.aos_file("spam.dat"))
    return d[:, :57], d[:, 57].astype(int)


def iris():
    """Fisher's iris data (150 x 4, three species), the copy bundled with scikit-learn."""
    from sklearn.datasets import load_iris
    d = load_iris()
    return d.data.astype(float), d.target.astype(int)


def glass():
    """The glass data of the book's website: 214 fragments, 9 covariates, 6 types (coded 0..5)."""
    import pandas as pd
    d = pd.read_csv(common.aos_file("glass.dat"), sep=r"\s+", engine="python")
    X = d.iloc[:, :9].to_numpy(float)
    types = sorted(d["type"].unique())
    y = np.array([types.index(t) for t in d["type"]])
    return X, y, types


# =========================================================================== 22.2-22.3 Gaussian classifiers
def lda_fit(X, y, mle=True):
    """Plug-in LDA (22.13)-(22.17): class proportions, class means and the pooled covariance
    S = sum_k n_k S_k / n (the MLE, as in the book) or with divisor n - K (mle=False)."""
    X = np.asarray(X, float)
    cl = np.unique(y)
    n = len(y)
    mus = np.array([X[y == k].mean(0) for k in cl])
    pis = np.array([np.mean(y == k) for k in cl])
    R = X - mus[np.searchsorted(cl, y)]
    S = R.T @ R / (n if mle else n - len(cl))
    return {"classes": cl, "mus": mus, "pis": pis, "S": S, "Sinv": np.linalg.inv(S)}


def lda_scores(fit, X):
    """delta_k(x) = x' S^{-1} mu_k - mu_k' S^{-1} mu_k / 2 + log pi_k, the (corrected) (22.17)."""
    Si, mus = fit["Sinv"], fit["mus"]
    return np.asarray(X, float) @ Si @ mus.T - 0.5 * np.einsum("kj,jl,kl->k", mus, Si, mus) + np.log(fit["pis"])


def qda_fit(X, y):
    """Plug-in QDA (22.12)/(22.16) with the maximum likelihood estimates S_k (divisor n_k)."""
    X = np.asarray(X, float)
    cl = np.unique(y)
    out = {"classes": cl, "mus": [], "pis": [], "S": []}
    for k in cl:
        Xk = X[y == k]
        mu = Xk.mean(0)
        out["mus"].append(mu)
        out["pis"].append(len(Xk) / len(y))
        out["S"].append((Xk - mu).T @ (Xk - mu) / len(Xk))
    return out


def qda_scores(fit, X):
    """delta_k(x) = -log|S_k|/2 - (x - mu_k)' S_k^{-1} (x - mu_k)/2 + log pi_k  (22.16)."""
    X = np.asarray(X, float)
    cols = []
    for mu, S, p in zip(fit["mus"], fit["S"], fit["pis"]):
        L = np.linalg.cholesky(S)
        Z = linalg.solve_triangular(L, (X - mu).T, lower=True)
        cols.append(-np.log(np.diag(L)).sum() - 0.5 * (Z ** 2).sum(0) + np.log(p))
    return np.column_stack(cols)


def predict_scores(fit, D):
    return fit["classes"][np.argmax(D, 1)]


def confusion(y, yhat, labels=(0, 1)):
    """Rows: true class; columns: predicted class (the book's 2 x 2 tables)."""
    return np.array([[int(np.sum((y == a) & (yhat == b))) for b in labels] for a in labels])


def fisher_direction(X, y):
    """Theorem 22.10: w = S_W^{-1}(xbar_0 - xbar_1) with the unbiased pooled S_W of (22.18), and the
    projected midpoint m = w'(xbar_0 + xbar_1)/2. The rule assigns class 0 when w'x >= m."""
    X0, X1 = X[y == 0], X[y == 1]
    n0, n1 = len(X0), len(X1)
    m0, m1 = X0.mean(0), X1.mean(0)
    SW = ((n0 - 1) * np.cov(X0.T) + (n1 - 1) * np.cov(X1.T)) / (n0 + n1 - 2)
    w = np.linalg.solve(SW, m0 - m1)
    return w, 0.5 * w @ (m0 + m1), SW


def rayleigh(w, X, y):
    """J(w) = w' S_B w / w' S_W w of (22.18)."""
    X0, X1 = X[y == 0], X[y == 1]
    d = X0.mean(0) - X1.mean(0)
    n0, n1 = len(X0), len(X1)
    SW = ((n0 - 1) * np.cov(X0.T) + (n1 - 1) * np.cov(X1.T)) / (n0 + n1 - 2)
    return (w @ d) ** 2 / (w @ SW @ w)


# =========================================================================== 22.4 regression
def drop_aliased(A, tol=1e-7):
    """Indices of a maximal set of linearly independent columns of A (pivoted QR, R's rule)."""
    Q, R, piv = linalg.qr(A, mode="economic", pivoting=True)
    d = np.abs(np.diag(R))
    r = int(np.sum(d > tol * d[0]))
    return np.sort(piv[:r])


def logistic_fit(A, y, tol=1e-10, maxit=100):
    """Logistic regression (22.24) by Newton-Raphson (reweighted least squares) with step halving.
    A is the design matrix with its intercept column; aliased columns get coefficient 0 (as R's NA).
    Columns are standardised internally, which does not change the fitted probabilities."""
    A = np.asarray(A, float)
    keep = drop_aliased(A)
    B = A[:, keep]
    const = B.std(0) == 0                  # the intercept column (all ones)
    sc = np.where(const, 1.0, B.std(0))
    ce = np.where(const, 0.0, B.mean(0))
    Z = (B - ce) / sc
    b = np.zeros(Z.shape[1])

    def ll(b):
        eta = Z @ b
        return np.sum(y * eta - np.logaddexp(0, eta))
    cur = ll(b)
    for it in range(maxit):
        p = common.sigmoid(Z @ b)
        W = p * (1 - p) + 1e-12
        g = Z.T @ (y - p)
        H = (Z * W[:, None]).T @ Z
        step = np.linalg.solve(H + 1e-12 * np.eye(len(b)), g)
        t = 1.0
        while True:
            new = ll(b + t * step)
            if new >= cur - 1e-12 or t < 1e-8:
                break
            t /= 2
        b = b + t * step
        done = abs(new - cur) < tol * (abs(cur) + 1)
        cur = new
        if done:
            break
    # undo the standardisation: eta = sum_j b_j (B_j - c_j)/s_j, the constant column absorbing the shift
    lin = b / sc
    ci = np.where(const)[0]
    if len(ci):
        lin[ci[0]] = (b[ci[0]] - np.sum(lin * ce)) / B[0, ci[0]]
    beta = np.zeros(A.shape[1])
    beta[keep] = lin
    return beta, cur


def logistic_prob(beta, A):
    return common.sigmoid(np.asarray(A, float) @ beta)


def add_intercept(X):
    return np.column_stack([np.ones(len(X)), X])


def linreg_fit(A, y):
    """Least squares on the 0/1 labels (22.23); classify by r(x) > 1/2 (22.22)."""
    return np.linalg.lstsq(A, y, rcond=None)[0]


def figure_22_5_designs(X):
    """The 18 nested designs of Example 22.14: covariates 1..j (j = 1..9), then all nine plus the
    squares of covariates 1..s (s = 1..9). Returns the list of design matrices (with intercept)."""
    out = []
    for j in range(1, 10):
        out.append(add_intercept(X[:, :j]))
    for s in range(1, 10):
        out.append(add_intercept(np.column_stack([X, X[:, :s] ** 2])))
    return out


# =========================================================================== 22.6 naive Bayes
def nb_fit(X, y, kind="gauss", bw=None):
    """Naive Bayes: product of one-dimensional density estimates within each class (Gaussian, or a
    Gaussian kernel density estimate with the normal reference bandwidth)."""
    cl = np.unique(y)
    return {"classes": cl, "kind": kind, "pis": np.array([np.mean(y == k) for k in cl]),
            "data": [X[y == k] for k in cl], "bw": bw}


def nb_scores(fit, X):
    X = np.asarray(X, float)
    out = []
    for Xk, p in zip(fit["data"], fit["pis"]):
        s = np.log(p) * np.ones(len(X))
        for j in range(X.shape[1]):
            v = Xk[:, j]
            if fit["kind"] == "gauss":
                sd = v.std() + 1e-9
                s += stats.norm.logpdf(X[:, j], v.mean(), sd)
            else:
                h = fit["bw"] or 1.06 * (v.std() + 1e-9) * len(v) ** (-0.2)
                s += common.logsumexp(stats.norm.logpdf((X[:, j][:, None] - v[None, :]) / h), axis=1) - np.log(len(v) * h)
        out.append(s)
    return np.column_stack(out)


# =========================================================================== 22.7 trees
def _impurity(counts, criterion):
    """Node impurity times node size: deviance -2 sum n_k log(n_k/n), or size-weighted Gini n (1 - sum p_k^2)."""
    n = counts.sum(-1)
    with np.errstate(divide="ignore", invalid="ignore"):
        p = np.where(n[..., None] > 0, counts / np.maximum(n[..., None], 1), 0)
        if criterion == "deviance":
            t = np.where(counts > 0, counts * np.log(np.where(p > 0, p, 1)), 0)
            return -2 * t.sum(-1)
        if criterion == "gini":
            return n * (1 - (p ** 2).sum(-1))
        if criterion == "gini_unweighted":   # the book's (22.29)-(22.30), taken literally
            return 1 - (p ** 2).sum(-1)
    raise ValueError(criterion)


def grow_tree(X, y, K=2, criterion="deviance", minsize=10, mincut=5, mindev=0.01, w=None, max_depth=99):
    """Greedy binary tree with the stopping rules of R's tree(): a node is split only if it has at
    least `minsize` cases and its best split lowers the deviance by more than `mindev` times the
    root's deviance (with the Gini index: lowers it at all); each child must have at least `mincut`
    cases; splits are midpoints between consecutive distinct values. Returns a nested dict."""
    X = np.asarray(X, float)
    y = np.asarray(y, int)
    w = np.ones(len(y)) if w is None else np.asarray(w, float)
    root_dev = _impurity(np.bincount(y, weights=w, minlength=K), "deviance")

    def node(idx, depth):
        counts = np.bincount(y[idx], weights=w[idx], minlength=K)
        nd = {"n": len(idx), "counts": counts, "yval": int(np.argmax(counts)),
              "dev": float(_impurity(counts, "deviance")), "idx": idx}
        if len(idx) < minsize or depth >= max_depth or np.count_nonzero(counts) < 2:
            return nd
        parent = _impurity(counts, criterion)
        # R's rule: with the deviance, split only if it falls by more than mindev x root deviance
        target = parent - mindev * root_dev if criterion == "deviance" else parent - 1e-12
        best = None
        for j in range(X.shape[1]):
            o = idx[np.argsort(X[idx, j], kind="mergesort")]
            xs = X[o, j]
            oh = np.zeros((len(o), K))
            oh[np.arange(len(o)), y[o]] = w[o]
            left = np.cumsum(oh, 0)[:-1]
            right = counts - left
            nl = np.arange(1, len(o))
            ok = (xs[1:] > xs[:-1]) & (nl >= mincut) & (len(o) - nl >= mincut)
            if not ok.any():
                continue
            imp = _impurity(left, criterion) + _impurity(right, criterion)
            imp = np.where(ok, imp, np.inf)
            i = int(np.argmin(imp))
            if best is None or imp[i] < best[0] - 1e-12:
                best = (imp[i], j, 0.5 * (xs[i] + xs[i + 1]))
        if best is None or (criterion != "gini_unweighted" and best[0] >= target):
            return nd
        _, j, t = best
        L = idx[X[idx, j] < t]
        R = idx[X[idx, j] >= t]
        nd.update(var=j, thr=t, left=node(L, depth + 1), right=node(R, depth + 1))
        return nd

    return node(np.arange(len(y)), 0)


def leaves(nd):
    return [nd] if "var" not in nd else leaves(nd["left"]) + leaves(nd["right"])


def n_leaves(nd):
    return len(leaves(nd))


def tree_predict(nd, X):
    X = np.asarray(X, float)
    out = np.empty(len(X), int)

    def go(nd, idx):
        if "var" not in nd:
            out[idx] = nd["yval"]
            return
        m = X[idx, nd["var"]] < nd["thr"]
        go(nd["left"], idx[m])
        go(nd["right"], idx[~m])
    go(nd, np.arange(len(X)))
    return out


def _miscount(nd):
    return float(nd["counts"].sum() - nd["counts"].max())


def _copy(nd):
    c = dict(nd)
    if "var" in nd:
        c["left"], c["right"] = _copy(nd["left"]), _copy(nd["right"])
    return c


def prune_sequence(tree):
    """Weakest-link (cost-complexity) pruning by misclassification count, as R's prune.misclass:
    returns [(alpha, subtree)] with nested subtrees from the full tree down to the root. At each step
    every internal node attaining the smallest g(t) = (R(t) - R(T_t)) / (|T_t| - 1) is collapsed."""
    T = _copy(tree)
    seq = [(-np.inf, _copy(T))]

    def internal(nd):
        return [] if "var" not in nd else [nd] + internal(nd["left"]) + internal(nd["right"])

    def subtree_cost(nd):
        return sum(_miscount(l) for l in leaves(nd))
    while "var" in T:
        g = [((_miscount(t) - subtree_cost(t)) / (n_leaves(t) - 1), t) for t in internal(T)]
        a = min(v for v, _ in g)
        for v, t in g:
            if v <= a + 1e-9 and "var" in t:
                for key in ("var", "thr", "left", "right"):
                    t.pop(key, None)
        seq.append((a, _copy(T)))
    # merge consecutive entries with the same alpha (all ties collapsed together)
    out = []
    for a, t in seq:
        if out and abs(out[-1][0] - a) < 1e-9:
            out[-1] = (a, t)
        else:
            out.append((a, t))
    return out


def subtree_at(seq, alpha):
    """The subtree of a pruning sequence that is optimal for penalty alpha."""
    best = seq[0][1]
    for a, t in seq:
        if a <= alpha + 1e-9:
            best = t
    return best


def kfold_ids(n, K, seed):
    """Fold labels 0..K-1, balanced, randomly permuted with numpy's generator."""
    rng = np.random.default_rng(seed)
    return rng.permutation(np.arange(n) % K)


def tree_cv(X, y, K=10, seed=0, criterion="deviance"):
    """Cross-validated misclassification count for each subtree of the full-data pruning sequence
    (R's cv.tree with FUN = prune.misclass): for each fold, grow on the rest, prune at the same
    penalties (the geometric means of consecutive alphas) and count errors on the fold."""
    full = grow_tree(X, y, criterion=criterion)
    seq = prune_sequence(full)
    alphas = [a for a, _ in seq]
    sizes = [n_leaves(t) for _, t in seq]
    mids = []
    for i, a in enumerate(alphas):
        nxt = alphas[i + 1] if i + 1 < len(alphas) else np.inf
        if not np.isfinite(a):
            mids.append(-np.inf)
        elif not np.isfinite(nxt):
            mids.append(a)
        else:
            mids.append(math.sqrt(max(a, 0) * nxt) if a > 0 else 0.5 * nxt)
    fold = kfold_ids(len(y), K, seed)
    errs = np.zeros(len(seq))
    for k in range(K):
        tr, te = fold != k, fold == k
        s = prune_sequence(grow_tree(X[tr], y[tr], criterion=criterion))
        for i, a in enumerate(mids):
            errs[i] += np.sum(tree_predict(subtree_at(s, a), X[te]) != y[te])
    return sizes, alphas, errs, seq


def tree_describe(nd, names, depth=0):
    if "var" not in nd:
        return "  " * depth + "leaf: %d (n=%d, %s)\n" % (nd["yval"], nd["n"], nd["counts"].astype(int).tolist())
    s = "  " * depth + "%s < %.4g (n=%d)\n" % (names[nd["var"]], nd["thr"], nd["n"])
    return s + tree_describe(nd["left"], names, depth + 1) + tree_describe(nd["right"], names, depth + 1)


def tree_signature(nd):
    """(var, rounded threshold) in preorder, and leaf classes: used to compare trees."""
    if "var" not in nd:
        return ("leaf", nd["yval"])
    return (nd["var"], round(nd["thr"], 4), tree_signature(nd["left"]), tree_signature(nd["right"]))


# =========================================================================== 22.8 error rates
def cv_error(fitpred, X, y, K, seed):
    """K-fold cross-validation (22.33): the average of the K fold error rates. fitpred(Xtr, ytr, Xte)
    returns predicted labels."""
    fold = kfold_ids(len(y), K, seed)
    errs = []
    for k in range(K):
        tr, te = fold != k, fold == k
        errs.append(np.mean(fitpred(X[tr], y[tr], X[te]) != y[te]))
    return float(np.mean(errs)), np.array(errs)


def hoeffding_eps(n, alpha, m=1):
    """Half-width of the Hoeffding interval for one classifier (m = 1) or, with the union bound, for
    the empirical risk minimiser over m classifiers (Theorem 22.17): sqrt(log(2m/alpha)/(2n))."""
    return math.sqrt(math.log(2 * m / alpha) / (2 * n))


def vc_eps(n, log_s, alpha):
    """Theorem 22.19: eps_n = sqrt(32/n log(8 s(H, n)/alpha)), with log_s = log s(H, n)."""
    return math.sqrt(32.0 / n * (math.log(8 / alpha) + log_s))


def lchoose(n, k):
    return math.lgamma(n + 1) - math.lgamma(k + 1) - math.lgamma(n - k + 1)


def log_sum_choose(N, ks):
    """log sum_{k in ks, 0 <= k <= N} C(N, k)."""
    v = [lchoose(N, k) for k in ks if 0 <= k <= N]
    m = max(v)
    return m + math.log(sum(math.exp(t - m) for t in v))


def log_shatter_unions(n, k):
    """Exact log shatter coefficient of unions of at most k intervals on the line:
    sum_{j=0}^{k} C(n+1, 2j) labelings of n ordered points with at most k runs of ones."""
    return log_sum_choose(n + 1, [2 * j for j in range(k + 1)])


def shatter_halfplanes(n):
    """Cover's count of the dichotomies of n points in general position in R^2 by half-planes:
    2 sum_{i=0}^{2} C(n-1, i) (equal to 2^n for n <= 3)."""
    return 2 * sum(math.comb(n - 1, i) for i in range(3)) if n >= 1 else 1


def sauer_bound(n, v):
    """Sauer's lemma: s(A, n) <= sum_{i=0}^{v} C(n, i) <= n^v + 1 (Theorem 22.21)."""
    return sum(math.comb(n, i) for i in range(v + 1))


# ---------------------------------------------------------------- demo 2: unions of k intervals
REGRESSION_FUNCTIONS = ("bumps", "wave", "noise")


def r_cells(kind, G, eta):
    """Integrals q1_c = int_c r(x) dx of the regression function over the G equal cells of [0, 1]
    (X ~ Uniform(0, 1)), exactly. bumps: r = 1 - eta on [0.2, 0.35) and [0.6, 0.8), eta elsewhere;
    wave: r = 1/2 + (1/2 - eta) sin(5 pi x); noise: r = 1/2."""
    e = np.arange(G + 1) / G
    if kind == "bumps":
        inside = lambda a, b: np.clip(np.minimum(b, 0.35) - np.maximum(a, 0.2), 0, None) + np.clip(np.minimum(b, 0.8) - np.maximum(a, 0.6), 0, None)
        ins = inside(e[:-1], e[1:])
        return (1 - eta) * ins + eta * (1.0 / G - ins)
    if kind == "wave":
        amp = 0.5 - eta
        return 0.5 / G + amp * (np.cos(5 * np.pi * e[:-1]) - np.cos(5 * np.pi * e[1:])) / (5 * np.pi)
    return 0.5 / G * np.ones(G)


def r_value(kind, x, eta):
    x = np.asarray(x, float)
    if kind == "bumps":
        ins = ((x >= 0.2) & (x < 0.35)) | ((x >= 0.6) & (x < 0.8))
        return np.where(ins, 1 - eta, eta)
    if kind == "wave":
        return 0.5 + (0.5 - eta) * np.sin(5 * np.pi * x)
    return 0.5 * np.ones_like(x)


def sample_intervals(kind, n, eta, seed, G):
    """The demo's data: x_i = u(), y_i = 1{u() < r(x_i)} from DK.rng(seed); returns per-cell counts."""
    g = JSRandom(seed)
    xs, ys = np.empty(n), np.empty(n, int)
    for i in range(n):
        x = g.u()
        xs[i] = x
        ys[i] = 1 if g.u() < float(r_value(kind, x, eta)) else 0
    c = np.minimum((xs * G).astype(int), G - 1)
    n1 = np.bincount(c, weights=ys, minlength=G)
    n0 = np.bincount(c, weights=1 - ys, minlength=G)
    return xs, ys, n0, n1


def runs_dp(gain1, gain0, K, sense=-1):
    """Dynamic programme over cells for labels h_c in {0, 1}: V[j, l] is the best signed value of
    sum_c [h_c gain1_c + (1 - h_c) gain0_c] (sign s = -1 to minimise, +1 to maximise) over labelings
    of the cells so far that use exactly j runs of ones and end with label l; back holds the argmax.
    One pass serves every k <= K."""
    G = len(gain1)
    s = 1.0 if sense > 0 else -1.0
    V0 = np.full(K + 1, -np.inf)
    V1 = np.full(K + 1, -np.inf)
    V0[0] = 0.0
    back0 = np.zeros((G, K + 1), int)     # previous label for label 0 (same j)
    back1 = np.zeros((G, K + 1), int)     # 1: continue a run (same j); 0: start run j from (j-1, 0)
    for c in range(G):
        W0 = np.where(V0 >= V1, V0, V1)
        back0[c] = np.where(V0 >= V1, 0, 1)
        start = np.concatenate([[-np.inf], V0[:-1]])
        W1 = np.where(V1 >= start, V1, start)
        back1[c] = np.where(V1 >= start, 1, 0)
        V0 = W0 + s * gain0[c]
        V1 = W1 + s * gain1[c]
    return V0, V1, back0, back1, s


def runs_select(V0, V1, back0, back1, s, k):
    """Best labeling with at most k runs from runs_dp: the largest value; at equal values (1e-12)
    the fewest runs, then label 0 at the last cell. Returns (value, labels)."""
    best = max(V0[:k + 1].max(), V1[:k + 1].max())
    j, l = 0, 0
    for jj in range(k + 1):
        if V0[jj] >= best - 1e-12:
            j, l = jj, 0
            break
        if V1[jj] >= best - 1e-12:
            j, l = jj, 1
            break
    G = back0.shape[0]
    lab = np.zeros(G, int)
    for c in range(G - 1, -1, -1):
        lab[c] = l
        if l == 0:
            l = back0[c, j]
        elif back1[c, j] == 0:
            j, l = j - 1, 0
    return s * best, lab


def best_runs(gain1, gain0, k, sense=-1):
    """Minimise (sense = -1) or maximise (+1) sum_c [h_c gain1_c + (1 - h_c) gain0_c] over labelings
    with at most k runs of ones. Returns (value, labels)."""
    return runs_select(*runs_dp(gain1, gain0, k, sense), k)


def erm_runs(n0, n1, q1, k, dp=None):
    """ERM over unions of at most k cell-intervals: returns training error, true error, labels."""
    n = n0.sum() + n1.sum()
    G = len(q1)
    q0 = 1.0 / G - q1
    tr, lab = runs_select(*(dp or runs_dp(n0 / n, n1 / n, k, -1)), k)
    true = float(np.sum(np.where(lab == 1, q0, q1)))
    return float(tr), true, lab


def sup_deviation(n0, n1, q1, k, dps=None):
    """sup over unions of at most k cell-intervals of |L_n(h) - L(h)|, exactly (both DP signs)."""
    n = n0.sum() + n1.sum()
    G = len(q1)
    q0 = 1.0 / G - q1
    g1 = n0 / n - q0
    g0 = n1 / n - q1
    hi = runs_select(*(dps[0] if dps else runs_dp(g1, g0, k, +1)), k)[0]
    lo = runs_select(*(dps[1] if dps else runs_dp(g1, g0, k, -1)), k)[0]
    return max(hi, -lo)


def interval_dps(n0, n1, q1, K):
    """The three dynamic programmes of one data set, for every k <= K at once."""
    n = n0.sum() + n1.sum()
    G = len(q1)
    q0 = 1.0 / G - q1
    g1, g0 = n0 / n - q0, n1 / n - q1
    return runs_dp(n0 / n, n1 / n, K, -1), (runs_dp(g1, g0, K, +1), runs_dp(g1, g0, K, -1))


DEMO2_G, DEMO2_K = 500, 20


def intervals_experiment(kind="bumps", n=200, eta=0.15, seed=1, G=DEMO2_G, kmax=DEMO2_K, alpha=0.05):
    """Everything the second demonstration shows for one data set: for k = 1..kmax, the training and
    true error of the ERM over unions of at most k cell-intervals, the exact uniform deviation, and
    the half-widths of the finite-class (Hoeffding + union) and VC guarantees."""
    xs, ys, n0, n1 = sample_intervals(kind, n, eta, seed, G)
    q1 = r_cells(kind, G, eta)
    dp, dps = interval_dps(n0, n1, q1, kmax)
    out = {"train": [], "true": [], "sup": [], "eps_fin": [], "eps_vc": [], "labels": [], "logm": [], "logs": []}
    for k in range(1, kmax + 1):
        tr, te, lab = erm_runs(n0, n1, q1, k, dp)
        out["train"].append(tr)
        out["true"].append(te)
        out["labels"].append(lab)
        out["sup"].append(sup_deviation(n0, n1, q1, k, dps))
        logm = log_shatter_unions(G, k)    # labelings of G cells with <= k runs: sum C(G+1, 2j)
        logs = log_shatter_unions(n, k)    # the exact shatter coefficient of unions of k intervals
        out["logm"].append(logm)
        out["logs"].append(logs)
        out["eps_fin"].append(math.sqrt((math.log(2 / alpha) + logm) / (2 * n)))
        out["eps_vc"].append(vc_eps(n, logs, alpha))
    q0 = 1.0 / G - q1
    out["bayes"] = float(np.sum(np.minimum(q0, q1)))
    out["xs"], out["ys"] = xs, ys
    return out


def demo2_seed(base, r):
    return base * 1009 + r


def intervals_repeat(kind="bumps", n=200, eta=0.15, base=1, R=200, G=DEMO2_G, kmax=DEMO2_K, alpha=0.05):
    """Data sets r = 1..R of the second demonstration: for each k, the fraction with
    sup_h |L_n(h) - L(h)| <= eps_fin(k), the fraction with L(h_k) <= L_n(h_k) + eps_fin(k), and the
    means of the uniform deviation, the training error and the true error of the ERM."""
    q1 = r_cells(kind, G, eta)
    eps = [math.sqrt((math.log(2 / alpha) + log_shatter_unions(G, k)) / (2 * n)) for k in range(1, kmax + 1)]
    acc = {key: np.zeros(kmax) for key in ("cov_sup", "cov_bound", "sup", "train", "true")}
    for r in range(1, R + 1):
        _, _, n0, n1 = sample_intervals(kind, n, eta, demo2_seed(base, r), G)
        dp, dps = interval_dps(n0, n1, q1, kmax)
        for k in range(1, kmax + 1):
            tr, te, _ = erm_runs(n0, n1, q1, k, dp)
            sd = sup_deviation(n0, n1, q1, k, dps)
            acc["cov_sup"][k - 1] += (sd <= eps[k - 1]) / R
            acc["cov_bound"][k - 1] += (te <= tr + eps[k - 1]) / R
            acc["sup"][k - 1] += sd / R
            acc["train"][k - 1] += tr / R
            acc["true"][k - 1] += te / R
    return {key: v.tolist() for key, v in acc.items()}


# =========================================================================== 22.9-22.10 SVM and kernels
def kernel_matrix(A, B, kind="linear", par=None):
    A, B = np.atleast_2d(A).astype(float), np.atleast_2d(B).astype(float)
    if kind == "linear":
        return A @ B.T
    if kind == "quad":                      # <x, x'>^2, the book's phi(x) = (x1^2, sqrt2 x1 x2, x2^2)
        return (A @ B.T) ** 2
    if kind == "poly":                      # (1 + <x, x'>)^p
        return (1 + A @ B.T) ** par
    if kind == "gauss":
        d2 = (A ** 2).sum(1)[:, None] + (B ** 2).sum(1)[None, :] - 2 * A @ B.T
        return np.exp(-np.maximum(d2, 0) / (2 * par ** 2))
    raise ValueError(kind)


def smo(K, y, C=np.inf, tol=1e-9, maxit=100000, record=False, blowup=1e7):
    """Sequential minimal optimisation for the SVM dual (22.40)/(22.43): minimise
    f(a) = a'Qa/2 - sum(a), Q_ij = y_i y_j K_ij, subject to y'a = 0 and 0 <= a_i <= C (C = inf: hard
    margin). Each step moves the maximal violating pair (Keerthi et al. 2001) along
    a_i += y_i t, a_j -= y_j t by the exact line minimiser, clipped to the box. Returns the dual
    solution, the number of steps, a status ('optimal', 'maxit' or 'unbounded') and, if record, the
    history of every iterate. The same arithmetic runs in the third demonstration."""
    y = np.asarray(y, float)
    n = len(y)
    Q = (y[:, None] * y[None, :]) * K
    a = np.zeros(n)
    G = -np.ones(n)
    hist = [a.copy()] if record else None
    status = "maxit"
    it = 0
    for it in range(maxit):
        up = ((y > 0) & (a < C)) | ((y < 0) & (a > 0))
        low = ((y < 0) & (a < C)) | ((y > 0) & (a > 0))
        v = -y * G
        vu = np.where(up, v, -np.inf)
        vl = np.where(low, v, np.inf)
        i, j = int(np.argmax(vu)), int(np.argmin(vl))
        gap = vu[i] - vl[j]
        if gap < tol:
            status = "optimal"
            break
        eta = K[i, i] + K[j, j] - 2 * K[i, j]
        if eta <= 1e-12:
            eta = 1e-12
        t = gap / eta
        bi = C - a[i] if y[i] > 0 else a[i]
        bj = C - a[j] if y[j] < 0 else a[j]
        t = min(t, bi, bj)
        a[i] += y[i] * t
        a[j] -= y[j] * t
        G += t * (y[i] * Q[:, i] - y[j] * Q[:, j])
        if record:
            hist.append(a.copy())
        if a.sum() > blowup:
            status = "unbounded"
            break
    return {"alpha": a, "steps": it + (1 if status != "optimal" else 0), "status": status, "hist": hist}


def dual_value(a, K, y):
    """The dual objective (22.40): sum a - a'Qa/2."""
    ay = a * y
    return float(a.sum() - 0.5 * ay @ K @ ay)


def svm_offset(a, K, y):
    """For the direction w = sum a_i y_i phi(x_i): scores s_i = w'phi(x_i), the offset a0 that
    maximises the smallest functional margin, a0 = -(min_{y=+1} s + max_{y=-1} s)/2, and that margin
    gamma = (min_{y=+1} s - max_{y=-1} s)/2 (positive iff the direction separates the data)."""
    s = K @ (a * y)
    hi, lo = s[y > 0].min(), s[y < 0].max()
    return -(hi + lo) / 2, (hi - lo) / 2, s


def duality_bounds(a, K, y):
    """Weak duality sandwich for the hard margin: D(a) <= P* <= U(a) = |w|^2/(2 gamma^2) when the
    direction w(a) separates (gamma > 0), where P* = 1/(2 rho*^2) and rho* is the maximal margin."""
    ay = a * y
    w2 = float(ay @ K @ ay)
    a0, gam, _ = svm_offset(a, K, y)
    U = w2 / (2 * gam ** 2) if gam > 0 and w2 > 0 else np.inf
    return dual_value(a, K, y), U, a0, gam


def svm_kkt_offset(a, K, y, tol=1e-8):
    """a0 from complementary slackness, a_i (y_i (w'x_i + a0) - 1) = 0, averaged over support vectors."""
    sv = a > tol * max(a.max(), 1e-300)
    s = K @ (a * y)
    return float(np.mean(y[sv] - s[sv]))


def kernel_fisher(K, y, b=1e-3):
    """Kernel Fisher discriminant (Section 22.10, Mika et al. 1999): maximise a'Ma / a'Na with
    M = (M0 - M1)(M0 - M1)', M_j(i) = sum_{s: y_s = j} K(x_i, x_s)/n_j and
    N = sum_j K_j (I - 1/n_j) K_j' (K_j: the n x n_j columns of class j). Solution a = (N + bI)^{-1}(M0 - M1)."""
    n = len(y)
    Ms, N = [], np.zeros((n, n))
    for j in (0, 1):
        Kj = K[:, y == j]
        nj = Kj.shape[1]
        Ms.append(Kj.mean(1))
        N += Kj @ (np.eye(nj) - np.ones((nj, nj)) / nj) @ Kj.T
    a = np.linalg.solve(N + b * np.eye(n), Ms[0] - Ms[1])
    return a, Ms, N


# =========================================================================== 22.11 other classifiers
def knn_predict(Xtr, ytr, Xte, k):
    """Majority vote of the k nearest training points (Euclidean); ties go to the smallest label."""
    d2 = (Xte ** 2).sum(1)[:, None] + (Xtr ** 2).sum(1)[None, :] - 2 * Xte @ Xtr.T
    idx = np.argsort(d2, axis=1, kind="stable")[:, :k]
    K = int(ytr.max()) + 1
    votes = np.zeros((len(Xte), K))
    for c in range(K):
        votes[:, c] = (ytr[idx] == c).sum(1)
    return votes.argmax(1)


def bagged_trees(Xtr, ytr, Xte, B, seed, **kw):
    """Bagging: majority vote of trees grown on B bootstrap samples. Returns the running vote
    fraction for class 1 after b = 1..B trees, for the test points."""
    rng = np.random.default_rng(seed)
    n = len(ytr)
    acc = np.zeros(len(Xte))
    out = []
    for b in range(B):
        i = rng.integers(0, n, n)
        acc += tree_predict(grow_tree(Xtr[i], ytr[i], **kw), Xte)
        out.append(acc / (b + 1))
    return np.array(out)


def stump_fit(X, y, w):
    """The weighted-error-minimising one-split tree (a stump) for labels y in {-1, +1}."""
    best = (np.inf, 0, 0.0, 1)
    W = w.sum()
    for j in range(X.shape[1]):
        o = np.argsort(X[:, j], kind="mergesort")
        xs, ys, ws = X[o, j], y[o], w[o]
        # predict +s on the right (x >= t), -s on the left
        cpos = np.concatenate([[0], np.cumsum(ws * (ys > 0))])   # weight of +1 to the left
        cneg = np.concatenate([[0], np.cumsum(ws * (ys < 0))])
        totn = cneg[-1]
        err_s1 = cpos + (totn - cneg)    # s = +1: left predicted -1 (wrong for +1), right +1 (wrong for -1)
        err_s0 = W - err_s1
        valid = np.concatenate([[True], xs[1:] > xs[:-1], [True]])
        for errs, s in ((err_s1, 1), (err_s0, -1)):
            e = np.where(valid, errs, np.inf)
            i = int(np.argmin(e))
            if e[i] < best[0] - 1e-12:
                t = -np.inf if i == 0 else (np.inf if i == len(xs) else 0.5 * (xs[i - 1] + xs[i]))
                best = (e[i], j, t, s)
    return best


def stump_predict(st, X):
    _, j, t, s = st
    return np.where(X[:, j] >= t, s, -s)


def adaboost(Xtr, ytr, Xte, J):
    """AdaBoost as on p. 376 of the book, with stumps; y in {0, 1} is recoded to {-1, +1}. Returns the
    running scores sum_j alpha_j h_j(x) for training and test points after every round."""
    y = 2 * ytr - 1
    n = len(y)
    w = np.ones(n) / n
    Ftr, Fte = np.zeros(n), np.zeros(len(Xte))
    hist_tr, hist_te, Ls = [], [], []
    for _ in range(J):
        st = stump_fit(Xtr, y, w)
        h = stump_predict(st, Xtr)
        L = np.sum(w * (h != y)) / w.sum()
        L = min(max(L, 1e-12), 1 - 1e-12)
        a = math.log((1 - L) / L)
        w = w * np.exp(a * (h != y))
        w = w / w.sum()
        Ftr += a * h
        Fte += a * stump_predict(st, Xte)
        hist_tr.append(Ftr.copy())
        hist_te.append(Fte.copy())
        Ls.append(L)
    return np.array(hist_tr), np.array(hist_te), np.array(Ls)


# =========================================================================== exercises
def unit_ball_volume(d):
    return math.pi ** (d / 2) / math.gamma(d / 2 + 1)


def median_nn_radius(d, n):
    """Exercise 22.10: median distance from the origin to the nearest of n uniform points in the cube
    [-1/2, 1/2]^d, ((1 - 2^{-1/n}) / v_d(1))^{1/d}; exact while it is at most 1/2."""
    return ((1 - 0.5 ** (1.0 / n)) / unit_ball_volume(d)) ** (1.0 / d)


def friedman_error(r, rbar, sigma):
    """Exercise 22.13: P(Y != h(x)) for h = 1{rhat >= 1/2} with rhat ~ N(rbar, sigma^2), Y ~ Bern(r)."""
    p1 = 1 - stats.norm.cdf((0.5 - rbar) / sigma)       # P(h = 1)
    return r * (1 - p1) + (1 - r) * p1


def friedman_formula(r, rbar, sigma):
    """The book's form: min(r, 1-r) + |2r - 1| (1 - Phi(sign(r - 1/2)(rbar - 1/2)/sigma))."""
    return min(r, 1 - r) + abs(2 * r - 1) * (1 - stats.norm.cdf(np.sign(r - 0.5) * (rbar - 0.5) / sigma))


# =========================================================================== demo 1: Bayes rule against plug-in rules
GRID_LO, GRID_H, GRID_N = -7.2, 0.08, 181          # x_i = -7.2 + 0.08 i, i = 0..180, on both axes
S_BASE = ((1.0, 0.5), (0.5, 1.0))
GAUSS_SCENARIOS = {
    # class 0 and class 1 covariances; class 0 may have a far 'satellite' cluster (weight sat)
    "equal": {"S0": S_BASE, "S1": S_BASE, "sat": 0.0},
    "unequal": {"S0": S_BASE, "S1": ((0.3, 0.0), (0.0, 2.5)), "sat": 0.0},
    "satellite": {"S0": S_BASE, "S1": S_BASE, "sat": 0.15, "far": (-4.0, 4.5), "farsd": 0.5},
}


def chol2(S):
    l11 = math.sqrt(S[0][0])
    l21 = S[1][0] / l11
    return (l11, l21, math.sqrt(S[1][1] - l21 * l21))


def gauss_scenario(name, delta=2.0, pi=0.5):
    sc = dict(GAUSS_SCENARIOS[name])
    sc.update(name=name, delta=delta, pi=pi, mu0=(-delta / 2, 0.0), mu1=(delta / 2, 0.0))
    return sc


def _ldens(x, y, mu, S):
    det = S[0][0] * S[1][1] - S[0][1] * S[1][0]
    a, b, c = S[1][1] / det, -S[0][1] / det, S[0][0] / det
    dx, dy = x - mu[0], y - mu[1]
    return np.exp(-0.5 * (a * dx * dx + 2 * b * dx * dy + c * dy * dy)) / (2 * math.pi * math.sqrt(det))


def grid_xy():
    g = GRID_LO + GRID_H * np.arange(GRID_N)
    return np.meshgrid(g, g, indexing="xy")


def gauss_truth(sc):
    """pi f1 and (1 - pi) f0 on the quadrature grid, the Bayes rule and the Bayes error."""
    gx, gy = grid_xy()
    f0 = (1 - sc["sat"]) * _ldens(gx, gy, sc["mu0"], sc["S0"])
    if sc["sat"] > 0:
        v = sc["farsd"] ** 2
        f0 = f0 + sc["sat"] * _ldens(gx, gy, sc["far"], ((v, 0), (0, v)))
    f1 = _ldens(gx, gy, sc["mu1"], sc["S1"])
    a1, a0 = sc["pi"] * f1, (1 - sc["pi"]) * f0
    h2 = GRID_H * GRID_H
    return {"a1": a1, "a0": a0, "bayes": a1 > a0, "w": np.abs(a1 - a0) * h2,
            "L_bayes": float(np.sum(np.minimum(a1, a0)) * h2), "gx": gx, "gy": gy}


def gauss_sample(sc, n, seed):
    """n1 = round(n pi) points of class 1 and n - n1 of class 0 from DK.rng(seed), class 0 first;
    each point uses one uniform (the satellite draw) and two normals, as in the demo."""
    g = JSRandom(seed)
    n1 = int(math.floor(n * sc["pi"] + 0.5))
    n0 = n - n1
    L0, L1 = chol2(sc["S0"]), chol2(sc["S1"])
    X = np.empty((n, 2))
    y = np.empty(n, int)
    for i in range(n):
        k = 0 if i < n0 else 1
        c = g.u()
        z1 = g.norm()
        z2 = g.norm()
        if k == 0 and c < sc["sat"]:
            X[i] = (sc["far"][0] + sc["farsd"] * z1, sc["far"][1] + sc["farsd"] * z2)
        else:
            mu, L = (sc["mu0"], L0) if k == 0 else (sc["mu1"], L1)
            X[i] = (mu[0] + L[0] * z1, mu[1] + L[1] * z1 + L[2] * z2)
        y[i] = k
    return X, y


def _solve3(A, b):
    """Gaussian elimination with partial pivoting (the demo's solver)."""
    M = [list(A[i]) + [b[i]] for i in range(3)]
    for c in range(3):
        p = max(range(c, 3), key=lambda r: abs(M[r][c]))
        M[c], M[p] = M[p], M[c]
        for r in range(c + 1, 3):
            f = M[r][c] / M[c][c]
            for k in range(c, 4):
                M[r][k] -= f * M[c][k]
    x = [0.0, 0.0, 0.0]
    for r in (2, 1, 0):
        x[r] = (M[r][3] - sum(M[r][k] * x[k] for k in range(r + 1, 3))) / M[r][r]
    return x


def logit2_fit(X, y, maxit=60):
    """Newton-Raphson with step halving for logistic regression on two covariates (the demo's
    algorithm: same steps, same stopping rule, 3 x 3 systems solved by elimination)."""
    Z = np.column_stack([np.ones(len(y)), X])
    b = np.zeros(3)

    def ll(b):
        e = Z @ b
        return float(np.sum(y * e - np.logaddexp(0, e)))
    cur = ll(b)
    for _ in range(maxit):
        with np.errstate(over="ignore"):
            p = 1 / (1 + np.exp(-(Z @ b)))
        w = p * (1 - p) + 1e-12
        g = Z.T @ (y - p)
        H = (Z * w[:, None]).T @ Z
        st = np.array(_solve3(H.tolist(), g.tolist()))
        t = 1.0
        while True:
            nb = b + t * st
            new = ll(nb)
            if new >= cur - 1e-12 or t < 1e-8:
                break
            t /= 2
        b = nb
        done = abs(new - cur) < 1e-12 * (abs(cur) + 1)
        cur = new
        if done:
            break
    return b.tolist()


def plugin_rules(X, y):
    """LDA, QDA (pooled covariance for a class with fewer than 3 points) and logistic regression
    fitted to one demo data set; each rule is a function (gx, gy) -> boolean 'class 1'."""
    lda = lda_fit(X, y)
    m0, m1, Si, p1 = lda["mus"][0], lda["mus"][1], lda["Sinv"], lda["pis"][1]
    w = Si @ (m1 - m0)
    c = -0.5 * (m1 @ Si @ m1 - m0 @ Si @ m0) + math.log(p1 / (1 - p1))
    rules = {"lda": lambda gx, gy: w[0] * gx + w[1] * gy + c > 0}
    qd = qda_fit(X, y)
    pars = []
    for k in (0, 1):
        S = qd["S"][k] if np.sum(y == k) >= 3 else lda["S"]
        det = S[0, 0] * S[1, 1] - S[0, 1] * S[1, 0]
        pars.append((qd["mus"][k], S[1, 1] / det, -S[0, 1] / det, S[0, 0] / det, -0.5 * math.log(det) + math.log(qd["pis"][k])))

    def qrule(gx, gy):
        d = []
        for mu, a, b_, cc, k0 in pars:
            dx, dy = gx - mu[0], gy - mu[1]
            d.append(k0 - 0.5 * (a * dx * dx + 2 * b_ * dx * dy + cc * dy * dy))
        return d[1] > d[0]
    rules["qda"] = qrule
    b = logit2_fit(X, y)
    rules["logistic"] = lambda gx, gy: b[0] + b[1] * gx + b[2] * gy > 0
    return rules, {"lda": (w, c), "logistic": b}


def excess_risks(truth, rules):
    """L(h) - L(h*) = int |pi f1 - (1 - pi) f0| 1{h != h*} dx, by quadrature (Theorem 22.5's identity)."""
    out = {}
    for k, r in rules.items():
        h = r(truth["gx"], truth["gy"])
        out[k] = float(np.sum(truth["w"][h != truth["bayes"]]))
    return out


DEMO1_NS = (20, 50, 100, 200, 500, 1000)


def demo1_seed(base, rep, n):
    return base * 7919 + rep * 1009 + n


def learning_curve(sc, ns=DEMO1_NS, R=40, base=1):
    """Mean excess risk of LDA, QDA and logistic regression over R data sets for each n."""
    truth = gauss_truth(sc)
    out = {k: [] for k in ("lda", "qda", "logistic")}
    for n in ns:
        acc = {k: 0.0 for k in out}
        for rep in range(R):
            X, y = gauss_sample(sc, n, demo1_seed(base, rep, n))
            e = excess_risks(truth, plugin_rules(X, y)[0])
            for k in out:
                acc[k] += e[k] / R
        for k in out:
            out[k].append(acc[k])
    return out, truth["L_bayes"]


# =========================================================================== demo 3: the SVM data sets
def svm_datasets():
    """The fixed data sets of the third demonstration (rounded to two decimals)."""
    rng = np.random.default_rng(2208)
    sets = {}
    # Figure 22.8: two small separable clouds
    A = rng.normal([-1.6, -0.9], 0.75, (8, 2))
    B = rng.normal([1.4, 1.1], 0.75, (7, 2))
    X = np.round(np.vstack([A, B]), 2)
    y = np.r_[-np.ones(8), np.ones(7)]
    sets["fig228"] = (X, y, "linear")
    # Figure 22.9: inside an ellipse (-1) against a ring outside it (+1)
    t = rng.uniform(0, 2 * np.pi, 14)
    rr = np.sqrt(rng.uniform(0, 1, 14)) * 0.85
    inner = np.column_stack([1.6 * rr * np.cos(t), 0.9 * rr * np.sin(t)])
    t = rng.uniform(0, 2 * np.pi, 18)
    rr = rng.uniform(1.25, 1.9, 18)
    outer = np.column_stack([1.6 * rr * np.cos(t), 0.9 * rr * np.sin(t)])
    sets["ellipse"] = (np.round(np.vstack([inner, outer]), 2), np.r_[-np.ones(14), np.ones(18)], "quad")
    # Exercise 22.7: points on a line, y = +1 when |x| <= 1
    xs = np.round(np.sort(rng.uniform(-2.4, 2.4, 14)), 2)
    xs = xs[np.abs(np.abs(xs) - 1) > 0.12]
    sets["ex7"] = (np.column_stack([xs, np.zeros(len(xs))]), np.where(np.abs(xs) <= 1, 1.0, -1.0), "ex7")
    # XOR: separable with a Gaussian kernel only
    C = rng.normal(0, 0.45, (16, 2)) + np.repeat([[1.2, 1.2], [-1.2, -1.2], [1.2, -1.2], [-1.2, 1.2]], 4, axis=0)
    sets["xor"] = (np.round(C, 2), np.repeat([1.0, 1.0, -1.0, -1.0], 4), "gauss")
    return sets


def demo_kernel(name, A, B, sigma=1.0):
    """The kernels of the third demonstration, with the same floating-point operations as the page."""
    if name == "ex7":
        return np.outer(A[:, 0], B[:, 0]) + np.outer(A[:, 0] * A[:, 0], B[:, 0] * B[:, 0])
    if name == "gauss":
        dx = A[:, 0][:, None] - B[:, 0][None, :]
        dy = A[:, 1][:, None] - B[:, 1][None, :]
        return np.exp(-(dx * dx + dy * dy) / (2 * sigma * sigma))
    lin = np.outer(A[:, 0], B[:, 0]) + np.outer(A[:, 1], B[:, 1])
    return lin * lin if name == "quad" else lin


# =========================================================================== figure helpers
def draw_tree(ax, tree, names, labels=None):
    """Draw a fitted tree as in the book: split variable at each node, the two conditions on the
    branches, the predicted class at each leaf."""
    labels = labels or {}
    lv = leaves(tree)
    pos = {}
    order = {id(l): i for i, l in enumerate(lv)}

    def place(nd, depth):
        if "var" not in nd:
            pos[id(nd)] = (order[id(nd)], -depth)
        else:
            place(nd["left"], depth + 1)
            place(nd["right"], depth + 1)
            pos[id(nd)] = (0.5 * (pos[id(nd["left"])][0] + pos[id(nd["right"])][0]), -depth)

    place(tree, 0)

    def fmt_thr(v, t):
        if v in labels:
            return labels[v]
        return ("< %g" % round(t, 3), "≥ %g" % round(t, 3))

    def draw(nd):
        x, yv = pos[id(nd)]
        if "var" not in nd:
            ax.text(x, yv - 0.05, str(nd["yval"]), ha="center", va="top", fontsize=11, weight="bold",
                    color=RED if nd["yval"] == 1 else BLUE)
            ax.text(x, yv - 0.32, "%d/%d" % (int(nd["counts"][1]), nd["n"]), ha="center", va="top", fontsize=7.5, color=GREY)
            return
        ax.text(x, yv + 0.08, names[nd["var"]], ha="center", va="bottom", fontsize=9.5)
        lo, hi = fmt_thr(nd["var"], nd["thr"])
        for ch, lab in ((nd["left"], lo), (nd["right"], hi)):
            cx, cy = pos[id(ch)]
            ax.plot([x, x, cx, cx], [yv, yv - 0.3, yv - 0.3, cy + (0.0 if "var" not in ch else 0.45)], color="k", lw=1.6)
            ax.text(cx, yv - 0.38, lab, ha="center", va="top", fontsize=8.5,
                    bbox=dict(boxstyle="round,pad=0.12", fc="white", ec="none"))
            draw(ch)

    draw(tree)
    depth = max(-p[1] for p in pos.values())
    ax.set_xlim(-0.7, len(lv) - 0.3)
    ax.set_ylim(-depth - 0.7, 0.5)
    ax.axis("off")


# =========================================================================== figures
def fig_22_1(out_dir=None):
    """Figure 22.1: two covariates, linearly separable classes and a linear decision rule."""
    rng = np.random.default_rng(221)
    X = rng.uniform(0, 1, (400, 2))
    s = X[:, 1] - (0.85 - 0.8 * X[:, 0])
    keep = np.abs(s) > 0.05
    X, s = X[keep][:100], s[keep][:100]
    y = np.where(s < 0, 1, -1)
    K = X @ X.T
    r = smo(K, y.astype(float))
    a = r["alpha"]
    w = (a * y) @ X
    a0 = svm_kkt_offset(a, K, y.astype(float))
    fig, ax = common.plt.subplots(figsize=(4.6, 3.9))
    ax.scatter(X[y == 1, 0], X[y == 1, 1], marker="^", s=26, facecolors="none", edgecolors=RED, label="Y = 1")
    ax.scatter(X[y == -1, 0], X[y == -1, 1], marker="s", s=22, facecolors="none", edgecolors=BLUE, label="Y = 0")
    xx = np.array([0, 1])
    ax.plot(xx, -(a0 + w[0] * xx) / w[1], "k--", lw=1.6, label="linear rule")
    ax.set_xlim(0, 1)
    ax.set_ylim(0, 1)
    ax.set_xlabel("$x_1$")
    ax.set_ylabel("$x_2$")
    ax.legend(loc="upper right", fontsize=8, framealpha=0.9)
    savefig(fig, CH, "fig22-1", out_dir)
    return {"w": w, "a0": a0, "n": len(y), "n1": int(np.sum(y == 1))}


def coris_tree_two():
    X, y, names = coris()
    return grow_tree(X[:, [1, 8]], y), X[:, [1, 8]], y


def fig_22_4(out_dir=None):
    """Figure 22.4: classification tree for the heart disease data using tobacco and age."""
    t, X2, y = coris_tree_two()
    fig, ax = common.plt.subplots(figsize=(6.0, 3.6))
    draw_tree(ax, t, ["tobacco", "age"])
    savefig(fig, CH, "fig22-4", out_dir)
    return t


def fig_22_5_data(K=10, seeds=(1, 2, 3, 4, 5)):
    X, y, _ = coris()
    D = figure_22_5_designs(X)
    train = []
    cvs = {s: [] for s in seeds}
    for A in D:
        b, _ = logistic_fit(A, y)
        train.append(float(np.mean((A @ b > 0) != y)))
        for s in seeds:
            fold = kfold_ids(len(y), K, s)
            errs = []
            for k in range(K):
                tr, te = fold != k, fold == k
                bk, _ = logistic_fit(A[tr], y[tr])
                errs.append(np.mean((A[te] @ bk > 0) != y[te]))
            cvs[s].append(float(np.mean(errs)))
    return train, cvs


def fig_22_5(out_dir=None):
    """Figure 22.5: training error and 10-fold cross-validation error for 18 nested logistic models."""
    train, cvs = fig_22_5_data()
    k = np.arange(1, 19)
    fig, ax = common.plt.subplots(figsize=(5.4, 3.6))
    for s, v in cvs.items():
        if s != 1:
            ax.plot(k, v, color=GREY, lw=0.8, alpha=0.6)
    ax.plot(k, cvs[1], "--", color=RED, lw=1.8, label="10-fold cross-validation")
    ax.plot(k, train, "-", color="k", lw=1.8, label="training error")
    ax.axhline(160 / 462, color=GREY, ls=":", lw=1)
    ax.text(18, 160 / 462 + 0.003, "always predict 0: 160/462", ha="right", va="bottom", fontsize=8, color=GREY)
    ax.axvline(14, color=GREY, lw=0.8, ls=":")
    ax.text(14.2, 0.335, "famhist$^2$ = famhist\nenters (aliased)", fontsize=7.5, color=GREY, va="top")
    ax.set_xlabel("number of terms in model")
    ax.set_ylabel("error rate")
    ax.set_xticks([1, 5, 9, 14, 18])
    ax.set_ylim(0.22, 0.36)
    ax.legend(loc="lower left", fontsize=8)
    savefig(fig, CH, "fig22-5", out_dir)
    return train, cvs


def fig_22_7(out_dir=None):
    """Figure 22.7: the tree pruned to six leaves (size chosen by cross-validation)."""
    X, y, names = coris()
    seq = prune_sequence(grow_tree(X, y))
    t6 = [t for _, t in seq if n_leaves(t) == 6][0]
    fig, ax = common.plt.subplots(figsize=(6.0, 4.2))
    draw_tree(ax, t6, ["sbp", "tobacco", "ldl", "adiposity", "family history", "type A", "obesity", "alcohol", "age"],
              labels={4: ("no", "yes")})
    savefig(fig, CH, "fig22-7", out_dir)
    return t6


def fig228_solution():
    X, y, _ = svm_datasets()["fig228"]
    K = X @ X.T
    r = smo(K, y)
    a = r["alpha"]
    w = (a * y) @ X
    a0 = svm_kkt_offset(a, K, y)
    return X, y, a, w, a0, r


def fig_22_8(out_dir=None):
    """Figure 22.8: the maximum margin hyperplane, its margin and the support vectors."""
    X, y, a, w, a0, _ = fig228_solution()
    fig, ax = common.plt.subplots(figsize=(4.8, 4.0))
    xx = np.linspace(-3.6, 3.4, 2)
    for off, st in ((0, "-"), (1, ":"), (-1, ":")):
        ax.plot(xx, (off - a0 - w[0] * xx) / w[1], st, color="k", lw=2.0 if off == 0 else 1.4)
    ax.scatter(X[y < 0, 0], X[y < 0, 1], s=34, color="k", label="$Y=-1$", zorder=3)
    ax.scatter(X[y > 0, 0], X[y > 0, 1], s=34, facecolors="white", edgecolors="k", label="$Y=+1$", zorder=3)
    sv = a > 1e-8
    ax.scatter(X[sv, 0], X[sv, 1], s=170, facecolors="none", edgecolors=RED, lw=1.3, label="support vectors", zorder=2)
    # the margin: from the boundary to the +1 margin line along w
    p0 = np.array([(-a0 + 2.0 * w[1]) / w[0], -2.0])          # the boundary at x2 = -2
    p1 = p0 + w / (w @ w)
    ax.annotate("", xy=p1, xytext=p0, arrowprops=dict(arrowstyle="<->", color=BLUE, lw=1.3))
    ax.text(p1[0] + 0.12, p1[1] - 0.1, "margin $1/\\|a\\|$", color=BLUE, fontsize=8.5, va="top")
    ax.text(-3.4, -2.95, "$H(x)=a_0+a^Tx=0$ (solid)", fontsize=8.5)
    ax.set_xlim(-3.6, 3.4)
    ax.set_ylim(-3.2, 3.4)
    ax.set_aspect("equal")
    ax.set_xlabel("$x_1$")
    ax.set_ylabel("$x_2$")
    ax.legend(loc="upper left", fontsize=7.5, framealpha=0.9)
    savefig(fig, CH, "fig22-8", out_dir)
    return {"margin": 1 / np.linalg.norm(w), "nsv": int(sv.sum())}


def fig_22_9(out_dir=None):
    """Figure 22.9: the map phi(x) = (x1^2, sqrt2 x1 x2, x2^2) makes an elliptical boundary linear."""
    X, y, _ = svm_datasets()["ellipse"]
    K = kernel_matrix(X, X, "quad")
    r = smo(K, y)
    a = r["alpha"]
    a0 = svm_kkt_offset(a, K, y)
    Z = np.column_stack([X[:, 0] ** 2, math.sqrt(2) * X[:, 0] * X[:, 1], X[:, 1] ** 2])
    wz = (a * y) @ Z
    fig = common.plt.figure(figsize=(8.4, 3.8))
    ax = fig.add_subplot(1, 2, 1)
    ax.scatter(X[y > 0, 0], X[y > 0, 1], marker="+", s=50, color=RED, label="$Y=+1$")
    ax.scatter(X[y < 0, 0], X[y < 0, 1], marker="o", s=26, facecolors="none", edgecolors=BLUE, label="$Y=-1$")
    g = np.linspace(-3.4, 3.4, 300)
    gx, gy = np.meshgrid(g, g)
    H = a0 + wz[0] * gx ** 2 + wz[1] * math.sqrt(2) * gx * gy + wz[2] * gy ** 2
    ax.contour(gx, gy, H, levels=[0], colors="k", linewidths=1.6)
    ax.axhline(0, color=GREY, lw=0.6)
    ax.axvline(0, color=GREY, lw=0.6)
    ax.set_aspect("equal")
    ax.set_xlabel("$x_1$")
    ax.set_ylabel("$x_2$")
    ax.set_title("covariate space $\\mathcal{X}=\\mathbb{R}^2$")
    ax.legend(loc="upper right", fontsize=7.5)
    ax3 = fig.add_subplot(1, 2, 2, projection="3d")
    ax3.scatter(Z[y > 0, 0], Z[y > 0, 1], Z[y > 0, 2], marker="+", s=40, color=RED)
    ax3.scatter(Z[y < 0, 0], Z[y < 0, 1], Z[y < 0, 2], marker="o", s=20, facecolors="none", edgecolors=BLUE)
    u = np.linspace(0, Z[:, 0].max(), 10)
    v = np.linspace(Z[:, 1].min(), Z[:, 1].max(), 10)
    U, V = np.meshgrid(u, v)
    W3 = -(a0 + wz[0] * U + wz[1] * V) / wz[2]
    W3 = np.where((W3 >= 0) & (W3 <= Z[:, 2].max() * 1.1), W3, np.nan)
    ax3.plot_surface(U, V, W3, alpha=0.25, color=GREY)
    ax3.set_xlabel("$z_1=x_1^2$", fontsize=8)
    ax3.set_ylabel("$z_2=\\sqrt{2}x_1x_2$", fontsize=8)
    ax3.set_zlabel("$z_3=x_2^2$", fontsize=8)
    ax3.set_title("feature space $\\mathcal{Z}=\\mathbb{R}^3$: a plane separates")
    ax3.view_init(elev=18, azim=-58)
    ax3.tick_params(labelsize=7)
    savefig(fig, CH, "fig22-9", out_dir)
    return {"wz": wz, "a0": a0, "min_margin": float(np.min(y * (Z @ wz + a0)))}


def fig_22_s1(out_dir=None):
    """Figure 22.S1: Example 22.2, LDA, QDA and logistic boundaries for blood pressure and tobacco."""
    X, y, _ = coris()
    X2 = X[:, :2]
    lda = lda_fit(X2, y)
    qda = qda_fit(X2, y)
    b, _ = logistic_fit(add_intercept(X2), y)
    g1 = np.linspace(95, 225, 300)
    g2 = np.linspace(-1, 33, 300)
    gx, gy = np.meshgrid(g1, g2)
    P = np.column_stack([gx.ravel(), gy.ravel()])
    Dl = lda_scores(lda, P)
    Dq = qda_scores(qda, P)
    fig, ax = common.plt.subplots(figsize=(5.6, 4.0))
    ax.scatter(X2[y == 0, 0], X2[y == 0, 1], s=9, color=BLUE, alpha=0.55, label="no heart disease ($Y=0$)")
    ax.scatter(X2[y == 1, 0], X2[y == 1, 1], s=12, marker="^", color=RED, alpha=0.6, label="heart disease ($Y=1$)")
    ax.contour(gx, gy, (Dl[:, 1] - Dl[:, 0]).reshape(gx.shape), levels=[0], colors="k", linewidths=1.8)
    ax.contour(gx, gy, (Dq[:, 1] - Dq[:, 0]).reshape(gx.shape), levels=[0], colors=GREEN, linewidths=1.6, linestyles="--")
    ax.contour(gx, gy, (b[0] + b[1] * gx + b[2] * gy), levels=[0], colors=ORANGE, linewidths=1.4, linestyles=":")
    ax.plot([], [], "k-", label="LDA (141 errors)")
    ax.plot([], [], "--", color=GREEN, label="QDA (143 errors)")
    nl = int(np.sum((add_intercept(X2) @ b > 0) != y))
    ax.plot([], [], ":", color=ORANGE, label="logistic (%d errors)" % nl)
    ax.set_xlabel("systolic blood pressure")
    ax.set_ylabel("cumulative tobacco (kg)")
    ax.set_xlim(95, 225)
    ax.set_ylim(-1, 33)
    ax.legend(loc="upper right", fontsize=7.5, framealpha=0.92)
    savefig(fig, CH, "fig22-S1", out_dir)
    return nl


def _draw_rules(ax, sc, X, y, title):
    truth = gauss_truth(sc)
    rules, _ = plugin_rules(X, y)
    gx, gy = truth["gx"], truth["gy"]
    ax.scatter(X[y == 0, 0], X[y == 0, 1], s=9, color=BLUE, alpha=0.6)
    ax.scatter(X[y == 1, 0], X[y == 1, 1], s=11, marker="^", color=RED, alpha=0.6)
    ax.contour(gx, gy, truth["a1"] - truth["a0"], levels=[0], colors="k", linewidths=2.0)
    for k, col, ls in (("lda", PURPLE, "--"), ("qda", GREEN, "-."), ("logistic", ORANGE, ":")):
        ax.contour(gx, gy, rules[k](gx, gy).astype(float) - 0.5, levels=[0], colors=col, linewidths=1.5, linestyles=ls)
    ax.set_xlim(-5.5, 5.5)
    ax.set_ylim(-5.5, 6.5)
    ax.set_aspect("equal")
    ax.set_title(title)


def fig_22_s2(out_dir=None):
    """Figure 22.S2: the Bayes rule against LDA, QDA and logistic regression (first demonstration)."""
    fig, axes = common.panel_grid(2, 2, size=(3.6, 3.3))
    res = {}
    for col, name in enumerate(("unequal", "satellite")):
        sc = gauss_scenario(name, 2.0, 0.5)
        X, y = gauss_sample(sc, 200, demo1_seed(1, 0, 200))
        _draw_rules(axes[0, col], sc, X, y, {"unequal": "unequal covariances, n = 200", "satellite": "class 0 has a far cluster, n = 200"}[name])
        lc, Lb = learning_curve(sc)
        res[name] = (lc, Lb)
        ax = axes[1, col]
        for k, c, mk in (("lda", PURPLE, "o"), ("qda", GREEN, "s"), ("logistic", ORANGE, "^")):
            ax.plot(DEMO1_NS, lc[k], marker=mk, color=c, lw=1.5, ms=4, label={"lda": "LDA", "qda": "QDA", "logistic": "logistic"}[k])
        ax.set_xscale("log")
        ax.set_yscale("log")
        ax.set_xlabel("sample size n")
        ax.set_ylabel("mean excess risk $L(\\hat h)-L(h^*)$")
        ax.set_title("Bayes error $L(h^*)$ = %.3f" % Lb)
        ax.legend(fontsize=7.5)
    axes[0, 0].plot([], [], "k-", label="Bayes rule")
    axes[0, 0].plot([], [], "--", color=PURPLE, label="LDA")
    axes[0, 0].plot([], [], "-.", color=GREEN, label="QDA")
    axes[0, 0].plot([], [], ":", color=ORANGE, label="logistic")
    axes[0, 0].legend(loc="upper left", fontsize=7)
    for ax, lab in zip(axes.ravel(), "abcd"):
        common.panel_label(ax, lab, "lower right" if lab in "ab" else "lower left")
    fig.tight_layout()
    savefig(fig, CH, "fig22-S2", out_dir)
    return res


def fig_22_s3(out_dir=None):
    """Figure 22.S3: empirical risk minimisation over unions of k intervals (second demonstration)."""
    o = intervals_experiment("bumps", 200, 0.15, demo2_seed(1, 0))
    ks = np.arange(1, DEMO2_K + 1)
    fig, axes = common.panel_grid(1, 3, size=(3.5, 3.0))
    ax = axes[0, 0]
    xx = np.linspace(0, 1, 801)
    ax.plot(xx, r_value("bumps", xx, 0.15), color="k", lw=1.4, label="$r(x)$")
    jit = np.random.default_rng(0).uniform(-0.03, 0.03, len(o["ys"]))
    ax.scatter(o["xs"], o["ys"] + jit, s=6, color=GREY, alpha=0.6)
    for k, c, off in ((2, BLUE, -0.12), (20, RED, -0.2)):
        lab = o["labels"][k - 1]
        for cidx in np.where(lab == 1)[0]:
            ax.plot([cidx / DEMO2_G, (cidx + 1) / DEMO2_G], [off, off], color=c, lw=4, solid_capstyle="butt")
        ax.plot([], [], color=c, lw=4, label="ERM, k = %d" % k)
    ax.set_ylim(-0.3, 1.1)
    ax.set_xlabel("x")
    ax.legend(fontsize=7, loc="center right")
    ax.set_title("data, $r(x)$ and the selected sets")
    ax = axes[0, 1]
    ax.plot(ks, o["train"], "o-", color="k", ms=3.5, label="training error $\\hat L_n(\\hat h_k)$")
    ax.plot(ks, o["true"], "s-", color=RED, ms=3.5, label="true error $L(\\hat h_k)$")
    ax.plot(ks, np.array(o["train"]) + np.array(o["eps_fin"]), "^--", color=BLUE, ms=3.5, label="finite-class bound")
    ax.axhline(o["bayes"], color=GREY, ls=":", lw=1)
    ax.text(DEMO2_K, o["bayes"] - 0.012, "Bayes error", ha="right", va="top", fontsize=7.5, color=GREY)
    ax.set_xlabel("k (largest number of intervals)")
    ax.set_ylim(0, 0.8)
    ax.legend(fontsize=7)
    ax.set_title("n = 200, 95% guarantee")
    ax = axes[0, 2]
    ax.plot(ks, o["sup"], "o-", color="k", ms=3.5, label="actual $\\sup_h|\\hat L_n(h)-L(h)|$")
    ax.plot(ks, o["eps_fin"], "^--", color=BLUE, ms=3.5, label="Hoeffding + union bound")
    ax.plot(ks, o["eps_vc"], "v-.", color=PURPLE, ms=3.5, label="VC bound (22.38)")
    ax.set_yscale("log")
    ax.set_ylim(0.08, 60)
    ax.set_xlabel("k")
    ax.legend(fontsize=7, loc="upper left")
    ax.set_title("uniform deviation and its bounds")
    for a_, lab in zip(axes.ravel(), "abc"):
        common.panel_label(a_, lab, "lower right" if lab == "c" else "upper left")
    fig.tight_layout()
    savefig(fig, CH, "fig22-S3", out_dir)
    return o


def fig_22_s4(out_dir=None):
    """Figure 22.S4: SMO on the hard-margin dual: weak duality closes on the optimum (third demonstration)."""
    X, y, _ = svm_datasets()["fig228"]
    K = X @ X.T
    r = smo(K, y, record=True)
    D, U = [], []
    for h in r["hist"]:
        d, u, _, _ = duality_bounds(h, K, y)
        D.append(d)
        U.append(u)
    a = r["alpha"]
    Pstar = D[-1]
    fig, axes = common.panel_grid(1, 2, size=(3.8, 3.1))
    ax = axes[0, 0]
    st = np.arange(len(D))
    Uf = np.where(np.isfinite(U), U, np.nan)
    ax.plot(st, D, "o-", color=BLUE, ms=3, label="dual value $D(\\alpha)$ (lower bound)")
    ax.plot(st, Uf, "s-", color=RED, ms=3, label="feasible rescaling $U(\\alpha)$ (upper bound)")
    ax.axhline(Pstar, color="k", ls=":", lw=1)
    ax.text(len(D) - 1, Pstar * 1.05, "$P^*=\\|a\\|^2/2$", ha="right", fontsize=8)
    ax.set_ylim(0, 3 * Pstar)
    ax.set_xlabel("SMO step")
    ax.legend(fontsize=7)
    ax = axes[0, 1]
    ax.bar(np.arange(len(a)), a, color=np.where(y > 0, RED, BLUE))
    ax.set_xlabel("data point i (blue: $Y=-1$, red: $Y=+1$)")
    ax.set_ylabel("$\\hat\\alpha_i$")
    ax.set_title("%d support vectors; $\\sum\\alpha_i=\\|a\\|^2$ = %.3f" % (int(np.sum(a > 1e-8)), a.sum()))
    for a_, lab in zip(axes.ravel(), "ab"):
        common.panel_label(a_, lab, "upper right")
    fig.tight_layout()
    savefig(fig, CH, "fig22-S4", out_dir)
    return D, U


def gini_root_curves(var=8):
    """Impurity of the root split of the CORIS data on one covariate, for every split point: the
    deviance, the size-weighted Gini index and the book's unweighted sum of Gini indices (22.29)."""
    X, y, _ = coris()
    x = X[:, var]
    vals = np.unique(x)
    ts = 0.5 * (vals[1:] + vals[:-1])
    out = {"t": ts, "deviance": [], "gini": [], "gini_unweighted": [], "nleft": []}
    for t in ts:
        L, R = y[x < t], y[x >= t]
        cl, cr = np.bincount(L, minlength=2).astype(float), np.bincount(R, minlength=2).astype(float)
        out["nleft"].append(len(L))
        for crit in ("deviance", "gini", "gini_unweighted"):
            out[crit].append(float(_impurity(cl, crit) + _impurity(cr, crit)))
    return out


def fig_22_s5(out_dir=None):
    """Figure 22.S5: cross-validated tree size (Example 22.15) and the root split under three criteria."""
    X, y, _ = coris()
    fig, axes = common.panel_grid(1, 2, size=(3.9, 3.1))
    ax = axes[0, 0]
    res = {}
    for s in range(1, 6):
        sizes, alphas, errs, _ = tree_cv(X, y, 10, s)
        res[s] = (sizes, errs.tolist())
        ax.plot(sizes, errs / len(y), "o-", ms=3, lw=1.2, color=RED if s == 1 else GREY, alpha=1 if s == 1 else 0.6,
                label="10-fold CV, split 1" if s == 1 else ("other splits" if s == 2 else None))
    tr = [np.mean(tree_predict(t, X) != y) for _, t in prune_sequence(grow_tree(X, y))]
    ax.plot(sizes, tr, "s-", color="k", ms=3, label="training error")
    ax.set_xlabel("number of leaves")
    ax.set_ylabel("misclassification rate")
    ax.legend(fontsize=7)
    ax = axes[0, 1]
    c = gini_root_curves(8)
    n = len(y)
    ax.plot(c["t"], np.array(c["gini"]) / n, color="k", lw=1.6, label="Gini, weighted by size")
    ax.plot(c["t"], np.array(c["gini_unweighted"]) / 2, color=RED, lw=1.4, ls="--", label="book's (22.29) / 2")
    ax.plot(c["t"], np.array(c["deviance"]) / (2 * n) / math.log(2) * 0.5, color=BLUE, lw=1.2, ls=":", label="deviance (rescaled)")
    ax.set_xlabel("split point t for age at the root")
    ax.set_ylabel("impurity of the split")
    ax.legend(fontsize=7)
    for a_, lab in zip(axes.ravel(), "ab"):
        common.panel_label(a_, lab, "lower left" if lab == "a" else "lower right")
    fig.tight_layout()
    savefig(fig, CH, "fig22-S5", out_dir)
    return res, c


# =========================================================================== the spam exercises (cached)
def spam_results(force=False):
    """Exercises 22.3, 22.5, 22.8, 22.11 and 22.12 on the spam data; cached as JSON."""
    path = os.path.join(CACHE_DIR, "ch22_spam.json")
    if os.path.exists(path) and not force:
        with open(path) as f:
            return json.load(f)
    from sklearn.svm import SVC
    X, y = spam()
    out = {}
    A = add_intercept(X)
    lda = lda_fit(X, y)
    qda = qda_fit(X, y)
    b, _ = logistic_fit(A, y)
    tr = grow_tree(X, y)
    preds = {"lda": predict_scores(lda, lda_scores(lda, X)), "qda": predict_scores(qda, qda_scores(qda, X)),
             "logistic": (A @ b > 0).astype(int), "tree": tree_predict(tr, X)}
    out["ex3a"] = {k: {"err": float(np.mean(p != y)), "table": confusion(y, p).tolist()} for k, p in preds.items()}
    out["ex3a"]["tree"]["leaves"] = n_leaves(tr)

    def f_lda(Xa, ya, Xb):
        f = lda_fit(Xa, ya)
        return predict_scores(f, lda_scores(f, Xb))

    def f_log(Xa, ya, Xb):
        bb, _ = logistic_fit(add_intercept(Xa), ya)
        return (add_intercept(Xb) @ bb > 0).astype(int)
    out["ex3b"] = {"lda": cv_error(f_lda, X, y, 5, 1)[0], "logistic": cv_error(f_log, X, y, 5, 1)[0]}
    t, pv = stats.ttest_ind(X[y == 1], X[y == 0], equal_var=False)
    top = np.argsort(pv, kind="stable")[:10]
    X10 = X[:, top]
    out["ex3c"] = {"cols": top.tolist(), "p": pv[top].tolist(),
                   "lda_train": float(np.mean(f_lda(X10, y, X10) != y)), "log_train": float(np.mean(f_log(X10, y, X10) != y)),
                   "lda_cv": cv_error(f_lda, X10, y, 5, 1)[0], "logistic_cv": cv_error(f_log, X10, y, 5, 1)[0]}
    Z = (X - X.mean(0)) / X.std(0)

    def f_svm(**kw):
        return lambda Xa, ya, Xb: SVC(C=1.0, **kw).fit(Xa, ya).predict(Xb)
    out["ex5"] = {"linear": cv_error(f_svm(kernel="linear"), Z, y, 5, 1)[0],
                  "gauss": cv_error(f_svm(kernel="rbf", gamma=1 / 57), Z, y, 5, 1)[0]}
    out["ex8"] = {str(p): cv_error(f_svm(kernel="poly", degree=p, gamma=1 / 57, coef0=1.0), Z, y, 5, 1)[0] for p in range(1, 7)}
    # Exercises 22.11 and 22.12: a random two-thirds / one-third split
    idx = np.random.default_rng(2211).permutation(len(y))
    itr, ite = idx[:3067], idx[3067:]
    single = grow_tree(X[itr], y[itr])
    out["ex11"] = {"tree_test": float(np.mean(tree_predict(single, X[ite]) != y[ite])), "tree_leaves": n_leaves(single)}
    vb = bagged_trees(X[itr], y[itr], X[ite], 60, 11)
    out["ex11"]["bag_test"] = [float(np.mean((v >= 0.5).astype(int) != y[ite])) for v in vb]
    htr, hte, Ls = adaboost(X[itr], y[itr], X[ite], 400)
    out["ex12"] = {"stump_test": float(np.mean((hte[0] > 0).astype(int) != y[ite])),
                   "train": [float(np.mean((h > 0).astype(int) != y[itr])) for h in htr],
                   "test": [float(np.mean((h > 0).astype(int) != y[ite])) for h in hte], "L": Ls.tolist()}
    os.makedirs(CACHE_DIR, exist_ok=True)
    with open(path, "w") as f:
        json.dump(out, f)
    return out


def fig_22_s6(out_dir=None):
    """Figure 22.S6: bagging and boosting on the spam data (Exercises 22.11 and 22.12)."""
    r = spam_results()
    fig, axes = common.panel_grid(1, 2, size=(3.8, 3.0))
    ax = axes[0, 0]
    B = np.arange(1, len(r["ex11"]["bag_test"]) + 1)
    ax.plot(B, r["ex11"]["bag_test"], color=RED, lw=1.5, label="bagged trees, test error")
    ax.axhline(r["ex11"]["tree_test"], color="k", ls="--", lw=1.2, label="single tree (%d leaves)" % r["ex11"]["tree_leaves"])
    ax.set_xlabel("number of bootstrap trees B")
    ax.set_ylabel("misclassification rate")
    ax.legend(fontsize=7.5)
    ax = axes[0, 1]
    J = np.arange(1, len(r["ex12"]["test"]) + 1)
    ax.plot(J, r["ex12"]["train"], color="k", lw=1.2, label="AdaBoost, training")
    ax.plot(J, r["ex12"]["test"], color=RED, lw=1.5, label="AdaBoost, test")
    ax.axhline(r["ex12"]["stump_test"], color=GREY, ls="--", lw=1.2, label="one stump, test")
    ax.set_xscale("log")
    ax.set_xlabel("number of boosting rounds J (stumps)")
    ax.legend(fontsize=7.5)
    for a_, lab in zip(axes.ravel(), "ab"):
        common.panel_label(a_, lab, "lower left")
    fig.tight_layout()
    savefig(fig, CH, "fig22-S6", out_dir)
    return r


def knn_cv_curve(X, y, ks, K=10, seed=1, standardise=True):
    if standardise:
        X = (X - X.mean(0)) / X.std(0)
    return [cv_error(lambda a, b, c: knn_predict(a, b, c, k), X, y, K, seed)[0] for k in ks]


def fig_22_s7(out_dir=None):
    """Figure 22.S7: the curse of dimensionality (Exercise 22.10) and k chosen by cross-validation (Exercise 22.9)."""
    fig, axes = common.panel_grid(1, 2, size=(3.8, 3.0))
    ax = axes[0, 0]
    ds = np.arange(1, 21)
    for n, c in ((100, BLUE), (1000, GREEN), (10000, RED)):
        ax.plot(ds, [median_nn_radius(d, n) for d in ds], "o-", ms=3, color=c, label="n = %d" % n)
    ax.axhline(0.5, color="k", ls="--", lw=1)
    ax.text(1, 0.52, "edge of the cube (1/2)", fontsize=7.5)
    ax.set_xlabel("dimension d")
    ax.set_ylabel("median distance to nearest neighbour")
    ax.legend(fontsize=7.5)
    ax = axes[0, 1]
    ks = list(range(1, 31))
    Xi, yi = iris()
    Xg, yg, _ = glass()
    ci = knn_cv_curve(Xi, yi, ks)
    cg = knn_cv_curve(Xg, yg, ks)
    ax.plot(ks, ci, "o-", ms=3, color=BLUE, label="iris")
    ax.plot(ks, cg, "s-", ms=3, color=RED, label="glass")
    ax.set_xlabel("number of neighbours k")
    ax.set_ylabel("10-fold CV error")
    ax.legend(fontsize=7.5)
    for a_, lab in zip(axes.ravel(), "ab"):
        common.panel_label(a_, lab, "lower right" if lab == "a" else "upper right")
    fig.tight_layout()
    savefig(fig, CH, "fig22-S7", out_dir)
    return ci, cg


def fig_22_s8(out_dir=None):
    """Figure 22.S8: Exercise 22.13, error at a point of a plug-in classifier with rhat ~ N(rbar, sigma^2)."""
    fig, ax = common.plt.subplots(figsize=(5.0, 3.4))
    rb = np.linspace(0, 1, 401)
    r = 0.7
    for sg, c in ((0.02, "k"), (0.1, BLUE), (0.25, RED)):
        ax.plot(rb, [friedman_error(r, v, sg) for v in rb], color=c, lw=1.5, label="$\\sigma(x)$ = %g" % sg)
    ax.axhline(min(r, 1 - r), color=GREY, ls=":", lw=1)
    ax.axvline(0.5, color=GREY, ls=":", lw=1)
    ax.text(0.02, 0.31, "Bayes error 0.3", fontsize=7.5, color=GREY)
    ax.set_xlabel("mean of the estimate, $\\bar r(x)$ (true $r(x)$ = 0.7)")
    ax.set_ylabel("$P(Y\\neq\\hat h(x))$")
    ax.legend(fontsize=7.5)
    savefig(fig, CH, "fig22-S8", out_dir)


# =========================================================================== JSON for the demos
def export_json():
    """Write the fixed data sets of the SVM demonstration to ../data/ch22-svm.json."""
    out = os.path.normpath(os.path.join(HERE, "..", "data"))
    os.makedirs(out, exist_ok=True)
    sets = svm_datasets()
    obj = {k: {"x": X.tolist(), "y": [int(v) for v in y], "kernel": kern} for k, (X, y, kern) in sets.items()}
    path = os.path.join(out, "ch22-svm.json")
    with open(path, "w") as f:
        json.dump(obj, f, separators=(",", ":"))
    print("wrote", path, os.path.getsize(path), "bytes")


FIGURES = {"22.1": fig_22_1, "22.4": fig_22_4, "22.5": fig_22_5, "22.7": fig_22_7, "22.8": fig_22_8, "22.9": fig_22_9,
           "22.S1": fig_22_s1, "22.S2": fig_22_s2, "22.S3": fig_22_s3, "22.S4": fig_22_s4, "22.S5": fig_22_s5,
           "22.S6": fig_22_s6, "22.S7": fig_22_s7, "22.S8": fig_22_s8}

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