"""Hastie, Tibshirani and Friedman (2009), Chapter 13: Prototype Methods and Nearest-Neighbors.

Reproduces the figures of Chapter 13 of T. Hastie, R. Tibshirani and J. Friedman, The Elements of
Statistical Learning (2nd edition, Springer, 2009), pp. 459-483, written from scratch with numpy, scipy
and matplotlib. Every method is a small function meant to be read next to the lecture notes
(../ch13-prototypes-nearest-neighbors.html):

* Prototype methods, Section 13.2: kmeans_js() (Lloyd's algorithm with random starts drawn with the demos'
  generator, so the browser demo starts from the same centres), kmeans_prototypes() (R centres per class),
  nearest_prototype(); lvq1() is Algorithm 13.1 (LVQ1, learning rate decreasing linearly to zero) and
  lvq1_fixed_point() the batch fixed-point map that explains where LVQ1 moves a prototype; the Gaussian
  mixture classifier with a common covariance is Chapter 12's MDAGauss, started from the K-means solution.
* k-nearest neighbours, Section 13.3: knn_order(), knn_topk(), knn_vote() (majority vote with a
  deterministic tie rule), knn_cv() (V-fold cross-validation with standard errors).
* Cover and Hart, (13.2)-(13.5) and (13.12): bayes_cond_error(), nn_asymptotic_cond_error(),
  cover_hart_cond_bound(), cover_hart_bound(), knn_asymptotic_cond_error() (the N -> infinity error of the
  k-NN vote for fixed k); the spiral problem of cover-hart-demo.html (spiral_probs(), spiral_sample(),
  spiral_integrals(), spiral_knn_errors()).
* The comparative study (13.6): study_sample(), study_results() (Figure 13.5 and Exercise 13.7).
* Tangent distance, Section 13.3.3 and Exercise 13.4: smooth_eval() and smooth_images() (a Gaussian kernel
  smoother of the 16 x 16 image and its two spatial derivatives), tangents() (the seven tangent vectors:
  two translations, rotation, scaling, two hyperbolic deformations and thickness, by the chain rule),
  rotate_image(), tangent_distance() (one- and two-sided, by least squares) and tangent_nn() (1-NN on the
  zip-code data); zip_table() is Table 13.1.
* The median radius (13.7): median_radius() and median_radius_mc().
* DANN, Section 13.4: local_wb() (local within and between covariances), dann_metric() ((13.8)-(13.9)),
  dann_predict(), shell_sample() (the ten-dimensional example of Section 13.4.1), dann_global_subspace()
  ((13.10)-(13.11)) and global_reduction_example() (nested spheres in four of ten dimensions).
* Editing and condensing, Section 13.5: multiedit() (Devijver and Kittler 1982) and condense() (Hart 1968).
* Exercises: em_scalar() and exercise_13_1() (EM with covariance sigma^2 I against K-means as sigma -> 0),
  signatures() and shape_averages() (Exercise 13.6, on the signature data of the book's website),
  ex137_summary() (Exercise 13.7), rotation_sample(), exercise_13_8() and rotation_bayes_rate()
  (Exercise 13.8).

Figures reproduced: 13.1, 13.2, 13.3, 13.4, 13.5, 13.9, 13.10, 13.12, 13.13, 13.14 and 13.15, Table 13.1,
and three supplementary figures: 13.S1 (Exercise 13.6, shape averages), 13.S2 (Exercise 13.7, CV against
the AIC-like criterion) and 13.S3 (the Cover-Hart bound on a simulated problem). Run
`python3 ch13_prototypes_nearest_neighbors.py --list`, `python3 ch13_prototypes_nearest_neighbors.py`
(all figures; about three minutes the first time, when the comparative study, the ten-dimensional example,
the median radii and Table 13.1 are computed and cached in cache/, under a minute afterwards) or
`python3 ch13_prototypes_nearest_neighbors.py --fig 13.4`. Files go to ../img/ch13/; Figure 13.14 also
writes the demos' data ../data/ch13-prototypes.json and ../data/ch13-dann.json (the prototype demo also
reads ../data/ch02-mixture.json).

Figures not reproduced, and why:
* Figure 13.6 (the LANDSAT scene in four spectral bands, with the true and the 5-NN predicted land use):
  the 82 x 100 pixel scene of the STATLOG project is not among the book's data sets.
* Figure 13.7 is a diagram of a pixel and its eight neighbours (nothing is computed).
* Figure 13.8 plots test errors published by the STATLOG project (Michie et al. 1994) for methods and
  software that are not available here; nothing in it can be recomputed without the LANDSAT data.
* Figure 13.11 is a schematic of two invariance curves and their tangent lines; Figure 13.10 (computed)
  shows the same idea for a real digit.

Settings chosen where the book gives none:
* Figures 13.1 and 13.3: the book does not give its three-class simulation. Here class k is an equal
  mixture of five Gaussians N(m_kl, 0.16 I) with the centres SIM3_CENTRES; 100 training points per class
  (numpy seed 13) and 3000 test points per class (seed 1313); the Bayes rate 0.168 is computed by
  integration. LVQ: learning rate 0.05 decreasing linearly to zero over 20 passes (6000 steps), from the
  K-means prototypes (K-means within each class, five random starts, demo generator seeds 1, 102, 203).
* Figure 13.2: K-means with the start of Chapter 12's MDA (seed 1); the Gaussian mixture is that MDA fit.
* Figure 13.4: ten folds from numpy seed 13; standard error = sd of the ten fold errors / sqrt(10).
* Figure 13.5: k = 1, 5, ..., 69; R = 1, 2, 3, 4, 6, 8, 10, 13, 16, 20, 25, 30 prototypes per class;
  LVQ with learning rate 0.05 over 40 passes from the K-means prototypes; numpy seeds 2009 and 2010.
* Figure 13.10 and Table 13.1: images are smoothed by a Gaussian kernel with bandwidth 0.9 pixels (ink in
  [0, 1]); the tangent distance is two-sided with the seven tangents, without a penalty, and is computed
  for each test digit against its 100 nearest training digits in Euclidean distance.
* Figure 13.12: lines are (13.7), dashed where the value exceeds 1/2 (the ball then leaves the cube and
  (13.7) is only approximate); dots are Monte Carlo medians (600 replications, 300 for N = 10,000).
* Figure 13.13: 26 uniform points; numpy seed 5 is the first for which the Euclidean neighbourhood of
  the target (0.43, 0.52) is dominated by the wrong class.
* Figure 13.14: a two-dimensional analogue of Section 13.4.1 (class 0 is N(0, I) conditioned on
  4 < ||x||^2 < 9, class 1 is N(0, I), 200 each, numpy seed 14); metric from 50 neighbours, eps = 1.
* Figure 13.15: 250 training and 250 test points per class per realisation (numpy seed 1996); LVQ with 50
  prototypes per class (K-means start), learning rate 0.05 over 20 passes; DANN with 50 neighbours for
  the metric, eps = 1 and a single pass (no iteration of the metric).
"""
import json
import math
import os

import numpy as np
from scipy import special

import common
from common import BLUE, GREEN, GREY, ORANGE, PURPLE, RED, savefig
import ch02_overview_supervised_learning as ch02
import ch12_svm_flexible_discriminants as ch12

CH = 13
HERE = os.path.dirname(os.path.abspath(__file__))
CACHE_DIR = os.path.join(HERE, "cache")
os.makedirs(CACHE_DIR, exist_ok=True)
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
MIX_BLUE, MIX_ORANGE = ch02.MIX_BLUE, ch02.MIX_ORANGE
TEAL = "#1a9e77"
SIM3_COLOURS = (TEAL, MIX_ORANGE, MIX_BLUE)
JSRandom = ch02.JSRandom


def error_rate(pred, g):
    return float(np.mean(np.asarray(pred) != np.asarray(g)))


def sqdist(A, B):
    """Squared Euclidean distances between the rows of A and the rows of B: from exact differences in up
    to three dimensions (as the browser demos compute them), otherwise from ||a||^2 - 2 a.b + ||b||^2."""
    if A.shape[1] <= 3:
        return ((A[:, None, :] - B[None, :, :]) ** 2).sum(-1)
    D = (A ** 2).sum(1)[:, None] - 2 * A @ B.T + (B ** 2).sum(1)[None, :]
    return np.maximum(D, 0.0)


# =========================================================================== data
def mixture():
    """The mixture data of Section 2.3: X (200 x 2), g (0 = BLUE, 1 = ORANGE), the 20 means, the book's
    plotting grid, the 10,000-point test set of Chapter 2 and the Bayes rate."""
    d = ch12.mixture_cached()
    return dict(X=d["X"], g=d["y"], means=d["means"], xnew=d["xnew"], Xt=d["Xt"],
                gt=((d["yt"] + 1) / 2).astype(int), bayes=d["bayes_rate"])


# The three-class simulation of Figures 13.1 and 13.3. The book does not give its generating model, only
# that each class is a mixture of Gaussians. Here class k has five centres m_kl and an observation is
# m_kl + N(0, s^2 I) with l chosen uniformly; so the class densities, the Bayes rule and the Bayes rate
# are known exactly.
SIM3_CENTRES = np.array([
    [[-1.6, 1.5], [-0.6, 1.9], [-1.2, 0.6], [0.4, 1.3], [-0.4, 0.0]],      # class 1 (teal)
    [[0.0, 0.6], [0.9, 1.0], [-0.1, -0.5], [1.5, 0.2], [0.6, -0.1]],        # class 2 (orange)
    [[-1.0, -0.9], [0.4, -1.4], [1.4, -0.9], [-0.2, -2.0], [2.0, -0.2]],    # class 3 (blue)
])
SIM3_S2 = 0.16
SIM3_N = 100          # training points per class
SIM3_NTEST = 3000     # test points per class
SIM3_LIM = ((-2.7, 3.0), (-3.0, 2.8))


def sim3_sample(n, rng):
    """n points from each of the three classes (numpy Generator rng): X (3n x 2), g in {0, 1, 2}."""
    X, g = [], []
    for k in range(3):
        l = rng.integers(0, 5, n)
        X.append(SIM3_CENTRES[k][l] + rng.normal(size=(n, 2)) * math.sqrt(SIM3_S2))
        g.append(np.full(n, k))
    return np.round(np.vstack(X), 4), np.concatenate(g)


def sim3():
    """Training (100 per class, numpy seed 13) and test (3000 per class, seed 1313) data of Figures 13.1
    and 13.3, with the Bayes rate."""
    X, g = sim3_sample(SIM3_N, np.random.default_rng(13))
    Xt, gt = sim3_sample(SIM3_NTEST, np.random.default_rng(1313))
    return dict(X=X, g=g, Xt=Xt, gt=gt, bayes=sim3_bayes_rate())


def sim3_logdens(P):
    """log of the three class densities at the rows of P (N x 3)."""
    P = np.atleast_2d(P)
    out = np.empty((len(P), 3))
    for k in range(3):
        d2 = sqdist(P, SIM3_CENTRES[k])
        out[:, k] = common.logsumexp(-d2 / (2 * SIM3_S2), axis=1) - math.log(5 * 2 * math.pi * SIM3_S2)
    return out


def sim3_bayes_rate(h=0.01):
    """1 - integral of max_k f_k / 3 (equal priors), by a Riemann sum on a wide grid."""
    gx = np.arange(-5, 5.5 + h / 2, h)
    gy = np.arange(-5, 5 + h / 2, h)
    tot = 0.0
    for a in gx:
        P = np.column_stack([np.full(gy.size, a), gy])
        tot += np.exp(sim3_logdens(P)).max(1).sum()
    return 1.0 - tot * h * h / 3.0


def zip_digits():
    """Zip-code digits: (Xtr, gtr, Xte, gte), 16 x 16 grey levels in [-1, 1] stored row by row."""
    return ch12.zip_digits()


# =========================================================================== K-means prototypes (13.2.1)
def kmeans_js(X, R, seed, starts=5, iters=100):
    """K-means (Lloyd's algorithm) with R centres and `starts` random starts; the starting centres are
    distinct training points drawn with the demos' generator (DK.rng, mirrored by JSRandom). Returns
    (centres, labels) of the start with the smallest within-cluster sum of squares. Same algorithm and
    random numbers as kmeans_js of Chapter 12 (which returns only the labels)."""
    rng = JSRandom(seed)
    N = len(X)
    best = (np.inf, None, None)
    for _ in range(starts):
        idx = []
        while len(idx) < R:
            j = int(math.floor(rng.u() * N))
            if j not in idx:
                idx.append(j)
        C = X[idx].copy()
        lab = None
        for _ in range(iters):
            new = np.argmin(sqdist(X, C), axis=1)
            if lab is not None and np.array_equal(new, lab):
                break
            lab = new
            for r in range(R):
                if (lab == r).any():
                    C[r] = X[lab == r].mean(0)
        ss = float(((X - C[lab]) ** 2).sum())
        if ss < best[0] - 1e-12:
            best = (ss, C.copy(), lab.copy())
    return best[1], best[2]


def kmeans_prototypes(X, g, R, K=None, seed=1, starts=5):
    """K-means classifier of Section 13.2.1: R centres per class from K-means run within each class (seed
    seed + 101 k for class k, the start used by MDA in Chapter 12). Returns (M, Mg): prototypes and
    their class labels."""
    K = K or int(g.max()) + 1
    M, Mg = [], []
    for k in range(K):
        Xk = X[g == k]
        if R == 1:
            C = Xk.mean(0, keepdims=True)
        else:
            C, _ = kmeans_js(Xk, R, seed + 101 * k, starts)
        M.append(C)
        Mg.append(np.full(len(C), k))
    return np.vstack(M), np.concatenate(Mg)


def nearest_prototype(M, Mg, P):
    """Class of the nearest prototype (the first one if two are equally near)."""
    return Mg[np.argmin(sqdist(P, M), axis=1)]


def prototype_scores(M, Mg, P, K):
    """Score of class k at P = minus the squared distance to the nearest class-k prototype."""
    D = sqdist(P, M)
    return np.column_stack([-D[:, Mg == k].min(1) for k in range(K)])


# =========================================================================== LVQ (Algorithm 13.1)
def lvq1(X, g, M0, Mg, eps0=0.05, epochs=20, seed=1, trace_every=None):
    """LVQ1, Algorithm 13.1: T = epochs * N steps; at step t (t = 0..T-1) draw i uniformly (with
    replacement, with the demos' generator), find the nearest prototype j and move it by
    +eps_t (x_i - m_j) if its class is g_i and by -eps_t (x_i - m_j) otherwise, with the learning rate
    decreasing linearly to zero, eps_t = eps0 (1 - t / T). Returns the prototypes (and their positions
    every trace_every steps if asked)."""
    rng = JSRandom(seed)
    M = np.array(M0, dtype=float).copy()
    N = len(X)
    T = int(epochs * N)
    trace = [M.copy()] if trace_every else None
    for t in range(T):
        i = int(math.floor(rng.u() * N))
        eps = eps0 * (1.0 - t / T)
        x = X[i]
        j = int(np.argmin(((M - x) ** 2).sum(1)))
        s = 1.0 if Mg[j] == g[i] else -1.0
        M[j] += s * eps * (x - M[j])
        if trace_every and (t + 1) % trace_every == 0:
            trace.append(M.copy())
    return (M, trace) if trace_every else M


def lvq1_fixed_point(X, g, M, Mg):
    """The batch (mean-field) LVQ1 fixed-point map: for each prototype j with Voronoi cell V_j, the point
    with sum_{i in V_j} s_ij (x_i - m) = 0, s_ij = +1 (same class) or -1, i.e.
    m = (S_same - S_other) / (n_same - n_other) (Gap 13.3). Returns the map applied once (cells with
    n_same <= n_other are left unchanged)."""
    lab = np.argmin(sqdist(X, M), axis=1)
    out = M.copy()
    for j in range(len(M)):
        idx = lab == j
        s = np.where(g[idx] == Mg[j], 1.0, -1.0)
        if s.sum() > 0:
            out[j] = (s[:, None] * X[idx]).sum(0) / s.sum()
    return out


# =========================================================================== k-nearest neighbours (13.3)
def knn_order(Xtr, Xq, chunk=500):
    """Training indices sorted by distance for each query row (stable sort: ties to the lower index)."""
    out = []
    for a in range(0, len(Xq), chunk):
        out.append(np.argsort(sqdist(Xq[a:a + chunk], Xtr), axis=1, kind="stable"))
    return np.vstack(out)


def knn_vote(order, gtr, k, K):
    """Majority vote among the k nearest (rows of order). A tie goes to the tied class whose nearest
    member comes first, which is the vote of the smallest k' < k without a tie among those classes.
    (The book breaks ties at random; this rule is deterministic, and for two classes with odd k there
    are no ties.)"""
    n = len(order)
    counts = np.zeros((n, K))
    first = np.full((n, K), k, dtype=float)
    lab = gtr[order[:, :k]]
    rows = np.arange(n)
    for r in range(k - 1, -1, -1):
        first[rows, lab[:, r]] = r
    for r in range(k):
        counts[rows, lab[:, r]] += 1
    return np.argmax(counts * (k + 1) - first, axis=1)


def knn_topk(Xtr, Xq, k, chunk=1000):
    """The k nearest training indices of each query row, nearest first (partial sort)."""
    out = []
    for a in range(0, len(Xq), chunk):
        D = sqdist(Xq[a:a + chunk], Xtr)
        if k < D.shape[1]:
            idx = np.argpartition(D, k - 1, axis=1)[:, :k]
        else:
            idx = np.tile(np.arange(D.shape[1]), (len(D), 1))
        dd = np.take_along_axis(D, idx, 1)
        o = np.lexsort((idx, dd), axis=1)
        out.append(np.take_along_axis(idx, o, 1))
    return np.vstack(out)


def knn_predict(Xtr, gtr, Xq, k, K=None, order=None):
    K = K or int(gtr.max()) + 1
    order = knn_topk(Xtr, Xq, k) if order is None else order
    return knn_vote(order, gtr, k, K)


def knn_cv(X, g, ks, folds=10, seed=13, K=None):
    """V-fold cross-validation of the k-NN rule: (mean error, standard error) for each k, with the
    standard error = sd of the V fold errors / sqrt(V)."""
    K = K or int(g.max()) + 1
    rng = np.random.default_rng(seed)
    fold = rng.permutation(np.arange(len(X)) % folds)
    E = np.zeros((folds, len(ks)))
    for v in range(folds):
        tr, te = fold != v, fold == v
        order = knn_order(X[tr], X[te])
        for j, k in enumerate(ks):
            E[v, j] = error_rate(knn_vote(order, g[tr], k, K), g[te])
    return E.mean(0), E.std(0, ddof=1) / math.sqrt(folds), E


# =========================================================================== Cover and Hart (13.2)-(13.5), (13.12)
def bayes_cond_error(P):
    """1 - max_k p_k(x) (13.2), for rows of class probabilities P."""
    return 1.0 - np.max(P, axis=1)


def nn_asymptotic_cond_error(P):
    """sum_k p_k (1 - p_k) (13.3): the asymptotic conditional error of the 1-NN rule."""
    return (P * (1 - P)).sum(1)


def cover_hart_cond_bound(P):
    """Right side of (13.5): 2 (1 - p_k*) - K/(K-1) (1 - p_k*)^2."""
    K = P.shape[1]
    e = bayes_cond_error(P)
    return 2 * e - K / (K - 1) * e ** 2


def cover_hart_bound(Estar, K):
    """(13.12): E* (2 - K/(K-1) E*)."""
    return Estar * (2 - K / (K - 1) * Estar)


def knn_asymptotic_cond_error(p, k):
    """Asymptotic (N -> infinity, k fixed and odd) conditional error of the two-class k-NN majority vote
    at a point with Pr(class 1 | x) = p: the k neighbours' labels become k independent Bernoulli(p)
    draws, so the vote is wrong with probability p Pr(Bin(k, p) < k/2) + (1 - p) Pr(Bin(k, p) > k/2)."""
    from scipy import stats
    p = np.asarray(p, dtype=float)
    lo = stats.binom.cdf((k - 1) // 2, k, p)          # Pr(majority for class 0)
    return p * lo + (1 - p) * (1 - lo)


# =========================================================================== the comparative study (13.6)
def study_sample(n, problem, rng, p=10):
    """n points with p independent U(0, 1) features and the 0/1 target (13.6): problem 'easy' is
    I(X1 > 1/2), 'difficult' is I(sign(prod_{j<=3} (X_j - 1/2)) > 0)."""
    X = rng.random((n, p))
    if problem == "easy":
        y = (X[:, 0] > 0.5).astype(int)
    else:
        y = (np.prod(X[:, :3] - 0.5, axis=1) > 0).astype(int)
    return X, y


STUDY_KS = list(range(1, 70, 4))
STUDY_RS = [1, 2, 3, 4, 6, 8, 10, 13, 16, 20, 25, 30]
STUDY_LVQ = dict(eps0=0.05, epochs=40)


def study_results(n_rep=10, seed=2009):
    """Figure 13.5 (and Exercise 13.7): for each problem, ten realisations of 100 training and 1000 test
    points; test error of k-NN for k in STUDY_KS and of K-means and LVQ prototypes for R per class in
    STUDY_RS; also, for Exercise 13.7, the five-fold CV error and the training error of k-NN. Cached."""
    path = os.path.join(CACHE_DIR, "ch13_study.json")
    if os.path.exists(path):
        with open(path) as f:
            return json.load(f)
    out = {}
    for problem in ("easy", "difficult"):
        rng = np.random.default_rng(seed + (0 if problem == "easy" else 1))
        R = dict(knn=[], km=[], lvq=[], cv5=[], train=[])
        for rep in range(n_rep):
            X, y = study_sample(100, problem, rng)
            Xt, yt = study_sample(1000, problem, rng)
            order = knn_order(X, Xt)
            R["knn"].append([error_rate(knn_vote(order, y, k, 2), yt) for k in STUDY_KS])
            otr = knn_order(X, X)
            R["train"].append([error_rate(knn_vote(otr, y, k, 2), y) for k in STUDY_KS])
            cv, _, _ = knn_cv(X, y, STUDY_KS, folds=5, seed=seed + 7 * rep)
            R["cv5"].append(list(cv))
            km, lv = [], []
            for Rr in STUDY_RS:
                M, Mg = kmeans_prototypes(X, y, Rr, 2, seed=1 + rep)
                km.append(error_rate(nearest_prototype(M, Mg, Xt), yt))
                M2 = lvq1(X, y, M, Mg, seed=100 + rep, **STUDY_LVQ)
                lv.append(error_rate(nearest_prototype(M2, Mg, Xt), yt))
            R["km"].append(km)
            R["lvq"].append(lv)
        out[problem] = R
    with open(path, "w") as f:
        json.dump(out, f)
    return out


# =========================================================================== invariance and tangent distance (13.3.3)
SMOOTH_H = 0.9     # bandwidth (pixels) of the Gaussian kernel smoother of the images (Exercise 13.4)
TANGENT_NAMES = ["x-translation", "y-translation", "rotation", "scaling", "parallel hyperbolic",
                 "diagonal hyperbolic", "thickness"]
PIX = np.arange(16) - 7.5      # pixel centres, origin at the centre of the image


def _kernel_mats(h=SMOOTH_H):
    """K[a, b] = phi_h(a - b) and D[a, b] = phi_h'(a - b) on the 16 pixel positions (1-D Gaussian)."""
    t = PIX[:, None] - PIX[None, :]
    Kz = np.exp(-0.5 * (t / h) ** 2) / (h * math.sqrt(2 * math.pi))
    return Kz, -t / h ** 2 * Kz


def as_image(v):
    """A zip digit (256 grey levels in [-1, 1], row by row) as a 16 x 16 ink image in [0, 1]
    (background 0), rows = vertical position (downwards), columns = horizontal position."""
    return (np.asarray(v, dtype=float).reshape(16, 16) + 1.0) / 2.0


def smooth_eval(I, pts, h=SMOOTH_H):
    """The kernel-smoothed image F(u) = sum_q phi_h(u - u_q) I_q at arbitrary points u = (x, y) (x to
    the right, y downwards, origin at the image centre). Also returns dF/dx and dF/dy."""
    pts = np.atleast_2d(pts)
    tx = pts[:, 0, None] - PIX[None, :]          # (n, 16) over columns
    ty = pts[:, 1, None] - PIX[None, :]          # (n, 16) over rows
    kx = np.exp(-0.5 * (tx / h) ** 2) / (h * math.sqrt(2 * math.pi))
    ky = np.exp(-0.5 * (ty / h) ** 2) / (h * math.sqrt(2 * math.pi))
    dkx, dky = -tx / h ** 2 * kx, -ty / h ** 2 * ky
    F = np.einsum("nr,rc,nc->n", ky, I, kx)
    Fx = np.einsum("nr,rc,nc->n", ky, I, dkx)
    Fy = np.einsum("nr,rc,nc->n", dky, I, kx)
    return F, Fx, Fy


def smooth_images(V, h=SMOOTH_H):
    """Smoothed images and their two spatial derivatives at the pixel centres, for a stack of digits
    V (n x 256): returns S, Fx, Fy, each n x 256."""
    Kz, Dz = _kernel_mats(h)
    I = (np.asarray(V, dtype=float).reshape(-1, 16, 16) + 1.0) / 2.0
    S = np.einsum("ra,nab,cb->nrc", Kz, I, Kz)
    Fx = np.einsum("ra,nab,cb->nrc", Kz, I, Dz)
    Fy = np.einsum("ra,nab,cb->nrc", Dz, I, Kz)
    n = len(I)
    return S.reshape(n, 256), Fx.reshape(n, 256), Fy.reshape(n, 256)


def tangents(V, h=SMOOTH_H, which=None):
    """The seven tangent vectors of Simard et al. (1993) for each digit (n x 256 x 7): derivatives of the
    smoothed image under x- and y-translation, rotation, scaling, the two hyperbolic deformations
    (Exercise 13.4) and line thickness, all by the chain rule from the two spatial derivatives."""
    S, Fx, Fy = smooth_images(V, h)
    YY, XX = np.meshgrid(PIX, PIX, indexing="ij")
    x, y = XX.ravel()[None, :], YY.ravel()[None, :]
    T = np.stack([Fx, Fy, y * Fx - x * Fy, x * Fx + y * Fy, x * Fx - y * Fy, y * Fx + x * Fy,
                  Fx ** 2 + Fy ** 2], axis=2)
    if which is not None:
        T = T[:, :, which]
    return S, T


def rotate_image(I, deg, h=SMOOTH_H):
    """The smoothed image rotated by deg degrees about its centre, sampled at the pixel centres:
    G(u) = F(R(-theta) u)."""
    th = math.radians(deg)
    YY, XX = np.meshgrid(PIX, PIX, indexing="ij")
    u = np.column_stack([XX.ravel(), YY.ravel()])
    c, s = math.cos(th), math.sin(th)
    src = np.column_stack([c * u[:, 0] + s * u[:, 1], -s * u[:, 0] + c * u[:, 1]])
    return smooth_eval(I, src, h)[0]


def tangent_distance(x, Tx, y, Ty, two_sided=True, lam=0.0):
    """Tangent distance between images x and y with tangent matrices Tx, Ty (256 x m): the minimum of
    ||x + Tx a - y - Ty b||^2 (+ lam (||a||^2 + ||b||^2)) over a and b, by least squares. One-sided:
    only y's tangent plane."""
    d = x - y
    A = np.column_stack([Tx, -Ty]) if two_sided else -Ty
    G = A.T @ A + lam * np.eye(A.shape[1])
    r = A.T @ d
    return float(d @ d - r @ np.linalg.solve(G, r))


def tangent_nn(Str, Ttr, gtr, Ste, Tte, n_cand=100, two_sided=True, lam=0.0, chunk=200):
    """1-NN with tangent distance; for each test image the tangent distance is computed to its n_cand
    nearest training images in Euclidean distance (the tangent distance is never larger than the
    Euclidean distance, and the nearest image in tangent distance is almost always among them).
    Returns (predictions, index of the nearest training image)."""
    m = Ttr.shape[2]
    GTr = np.einsum("npi,npj->nij", Ttr, Ttr)
    TxX = np.einsum("npi,np->ni", Ttr, Str)
    sq_tr = (Str ** 2).sum(1)
    pred = np.empty(len(Ste), int)
    best = np.empty(len(Ste), int)
    for a in range(0, len(Ste), chunk):
        Y = Ste[a:a + chunk]
        D = sq_tr[None, :] - 2 * Y @ Str.T + (Y ** 2).sum(1)[:, None]
        cand = np.argpartition(D, n_cand, axis=1)[:, :n_cand]
        for q in range(len(Y)):
            c = cand[q]
            y, Ty = Y[q], Tte[a + q]
            Tc = Ttr[c]                                   # (n_cand, 256, m)
            d2 = D[q, c]
            TyY = Ty.T @ y
            if two_sided:
                Cxy = np.einsum("npi,pj->nij", Tc, Ty)    # Tx^T Ty
                G = np.zeros((len(c), 2 * m, 2 * m))
                G[:, :m, :m] = GTr[c]
                G[:, :m, m:] = -Cxy
                G[:, m:, :m] = -np.transpose(Cxy, (0, 2, 1))
                G[:, m:, m:] = Ty.T @ Ty
                rx = TxX[c] - np.einsum("npi,p->ni", Tc, y)           # Tx^T (x - y)
                ry = -(Str[c] @ Ty - TyY[None, :])                    # -Ty^T (x - y)
                r = np.concatenate([rx, ry], axis=1)
            else:
                G = np.broadcast_to(Ty.T @ Ty, (len(c), m, m)).copy()
                r = -(Str[c] @ Ty - TyY[None, :])
            if lam:
                G = G + lam * np.eye(G.shape[1])[None]
            sol = np.linalg.solve(G, r[:, :, None])[:, :, 0]
            td = d2 - (r * sol).sum(1)
            j = c[np.argmin(td)]
            best[a + q] = j
            pred[a + q] = gtr[j]
    return pred, best


def zip_table(n_cand=100):
    """Table 13.1: test error of 1-NN with Euclidean distance (raw and smoothed images) and with
    one- and two-sided tangent distance on the zip-code data (7291 training, 2007 test digits). Cached."""
    path = os.path.join(CACHE_DIR, "ch13_zip_table.json")
    if os.path.exists(path):
        with open(path) as f:
            return json.load(f)
    Xtr, gtr, Xte, gte = zip_digits()
    res = {}
    pr = knn_predict(Xtr, gtr, Xte, 1, 10)
    res["euclid_raw"] = error_rate(pr, gte)
    Str, Ttr = tangents(Xtr)
    Ste, Tte = tangents(Xte)
    pr = knn_predict(Str, gtr, Ste, 1, 10)
    res["euclid_smooth"] = error_rate(pr, gte)
    p1, _ = tangent_nn(Str, Ttr, gtr, Ste, Tte, n_cand=n_cand, two_sided=False)
    res["tangent_one_sided"] = error_rate(p1, gte)
    p2, _ = tangent_nn(Str, Ttr, gtr, Ste, Tte, n_cand=n_cand, two_sided=True)
    res["tangent_two_sided"] = error_rate(p2, gte)
    p3, _ = tangent_nn(Str, Ttr[:, :, :3], gtr, Ste, Tte[:, :, :3], n_cand=n_cand, two_sided=True)
    res["tangent_translation_rotation"] = error_rate(p3, gte)
    res["n_cand"] = n_cand
    with open(path, "w") as f:
        json.dump(res, f)
    return res


# =========================================================================== median radius (13.7)
def unit_ball_volume(p):
    """v_p = pi^(p/2) / Gamma(p/2 + 1): the volume of the unit ball in p dimensions."""
    return math.exp(0.5 * p * math.log(math.pi) - special.gammaln(0.5 * p + 1))


def median_radius(p, N):
    """(13.7): median distance from the origin to the nearest of N uniform points in [-1/2, 1/2]^p. Exact
    while the value is at most 1/2 (the ball then lies inside the cube)."""
    return unit_ball_volume(p) ** (-1.0 / p) * (1 - 0.5 ** (1.0 / N)) ** (1.0 / p)


def median_radius_mc(p, N, reps=1000, seed=1, chunk=50):
    """Monte Carlo median of the nearest-neighbour distance from the origin (exact for every p)."""
    rng = np.random.default_rng(seed)
    out = []
    for a in range(0, reps, chunk):
        m = min(chunk, reps - a)
        U = rng.random((m, N, p)) - 0.5
        out.append(np.sqrt((U ** 2).sum(2).min(1)))
    return float(np.median(np.concatenate(out)))


# =========================================================================== DANN (13.8)-(13.9)
def local_wb(Xn, gn, K):
    """Within (pooled, sum_k pi_k W_k) and between (sum_k pi_k (xbar_k - xbar)(xbar_k - xbar)^T)
    covariance matrices of a neighbourhood, with pi_k the class proportions (divisor n)."""
    n, p = Xn.shape
    xbar = Xn.mean(0)
    W = np.zeros((p, p))
    B = np.zeros((p, p))
    for k in range(K):
        idx = gn == k
        nk = idx.sum()
        if nk == 0:
            continue
        mk = Xn[idx].mean(0)
        D = Xn[idx] - mk
        W += D.T @ D / n
        B += nk / n * np.outer(mk - xbar, mk - xbar)
    return W, B


def dann_metric(X, g, x0, K=2, km=50, eps=1.0, ridge=1e-8):
    """The DANN metric (13.9) at x0, from the km nearest training points in Euclidean distance:
    Sigma = W^(-1/2) [W^(-1/2) B W^(-1/2) + eps I] W^(-1/2). Returns Sigma, W, B and the neighbours."""
    d = ((X - x0) ** 2).sum(1)
    nb = np.argsort(d, kind="stable")[:km]
    W, B = local_wb(X[nb], g[nb], K)
    vals, vecs = np.linalg.eigh(W + ridge * np.trace(W) / len(W) * np.eye(len(W)))
    Wmh = (vecs / np.sqrt(vals)) @ vecs.T
    Bs = Wmh @ B @ Wmh
    Sigma = Wmh @ (Bs + eps * np.eye(len(W))) @ Wmh
    return Sigma, W, B, nb


def dann_predict(X, g, Q, k=5, K=2, km=50, eps=1.0):
    """DANN classification: at each query point the metric (13.8) from its km Euclidean neighbours, then
    a k-NN majority vote in that metric."""
    out = np.empty(len(Q), int)
    for q, x0 in enumerate(Q):
        S = dann_metric(X, g, x0, K, km, eps)[0]
        D = X - x0
        dist = np.einsum("ij,jk,ik->i", D, S, D)
        order = np.argsort(dist, kind="stable")[None, :]
        out[q] = knn_vote(order, g, k, K)[0]
    return out


def dann_global_subspace(X, g, K=2, km=50, sphere=False):
    """Global dimension reduction (13.10): average over the training points x_i of the between-class
    matrices B_i of their km nearest neighbours (in the coordinates sphered by the local W if sphere),
    then its eigen-decomposition (13.11). Returns eigenvalues (descending), eigenvectors and B-bar."""
    p = X.shape[1]
    Bbar = np.zeros((p, p))
    for x0 in X:
        d = ((X - x0) ** 2).sum(1)
        nb = np.argsort(d, kind="stable")[:km]
        W, B = local_wb(X[nb], g[nb], K)
        if sphere:
            vals, vecs = np.linalg.eigh(W)
            Wmh = (vecs / np.sqrt(vals)) @ vecs.T
            B = Wmh @ B @ Wmh
        Bbar += B
    Bbar /= len(X)
    vals, vecs = np.linalg.eigh(Bbar)
    return vals[::-1], vecs[:, ::-1], Bbar


def global_reduction_example(n=250, seed=1342, L=4, k=5):
    """Section 13.4.2 example: nested spheres in four dimensions plus six noise features (n per class).
    Returns the eigenvalues of B-bar, the squared cosines between the leading-L eigenvectors and the
    signal subspace, and the test errors of k-NN in all ten dimensions, in the leading L, and in the
    true four signal coordinates."""
    rng = np.random.default_rng(seed)
    X, g = nested_spheres_sample(n, rng)
    Xt, gt = nested_spheres_sample(1000, rng)
    vals, vecs, _ = dann_global_subspace(X, g)
    E = vecs[:, :L]
    cos2 = np.linalg.svd(E[:4, :], compute_uv=False) ** 2
    return dict(eig=list(vals), cos2=list(cos2),
                full=error_rate(knn_predict(X, g, Xt, k, 2), gt),
                reduced=error_rate(knn_predict(X @ E, g, Xt @ E, k, 2), gt),
                oracle=error_rate(knn_predict(X[:, :4], g, Xt[:, :4], k, 2), gt))


def shell_sample(n, rng, p=10, lo=22.4, hi=40.0):
    """Section 13.4.1: n points of class 0, independent N(0, 1) features conditioned on lo < ||x||^2 < hi
    (by rejection), and n of class 1, independent N(0, 1) without restriction."""
    out = np.empty((0, p))
    while len(out) < n:
        Z = rng.normal(size=(40 * n, p))
        r2 = (Z ** 2).sum(1)
        out = np.vstack([out, Z[(r2 > lo) & (r2 < hi)]])
    X = np.vstack([out[:n], rng.normal(size=(n, p))])
    return X, np.r_[np.zeros(n, int), np.ones(n, int)]


def nested_spheres_sample(n, rng, p_noise=6):
    """Section 13.4.2: two nested spheres in four dimensions plus six noise features, the 'skin of the
    orange' of Chapter 12: class 0 is N(0, I_4), class 1 is N(0, I_4) conditioned on 9 <= ||x||^2 <= 16;
    both have p_noise extra N(0, 1) features. Labels 0/1."""
    X, y = ch12.orange_sample(n, rng, noise=p_noise)
    return X, (y > 0).astype(int)


# =========================================================================== editing and condensing (13.5)
def multiedit(X, g, n_split=3, seed=1, max_rounds=50, K=None):
    """Multi-edit (Devijver and Kittler 1982): repeat until nothing changes for max(3, ...) rounds:
    split the current set at random into n_split parts, classify part s by 1-NN on part s+1 (cyclically)
    and delete the misclassified points. Returns the indices kept."""
    K = K or int(g.max()) + 1
    rng = np.random.default_rng(seed)
    keep = np.arange(len(X))
    quiet = 0
    for _ in range(max_rounds):
        part = rng.permutation(np.arange(len(keep)) % n_split)
        bad = np.zeros(len(keep), bool)
        for s in range(n_split):
            te, tr = part == s, part == (s + 1) % n_split
            if tr.sum() == 0 or te.sum() == 0:
                continue
            pr = knn_predict(X[keep[tr]], g[keep[tr]], X[keep[te]], 1, K)
            bad[np.flatnonzero(te)[pr != g[keep[te]]]] = True
        if bad.any():
            keep = keep[~bad]
            quiet = 0
        else:
            quiet += 1
            if quiet >= 3:
                break
    return keep


def condense(X, g, seed=1, K=None):
    """Hart's (1968) condensing: start from one random point; pass through the data in random order,
    adding a point whenever 1-NN on the current store misclassifies it; repeat passes until a full pass
    adds nothing. Returns the indices of the store (1-NN on it classifies every point of X correctly
    when X has no duplicated inputs with different labels)."""
    K = K or int(g.max()) + 1
    rng = np.random.default_rng(seed)
    perm = rng.permutation(len(X))
    store = [int(perm[0])]
    changed = True
    while changed:
        changed = False
        for i in perm:
            if i in store:
                continue
            j = store[int(np.argmin(((X[store] - X[i]) ** 2).sum(1)))]
            if g[j] != g[i]:
                store.append(int(i))
                changed = True
    return np.array(store)


# =========================================================================== plotting helpers
def _grid(lim, n1, n2):
    gx = np.linspace(lim[0][0], lim[0][1], n1)
    gy = np.linspace(lim[1][0], lim[1][1], n2)
    XX, YY = np.meshgrid(gx, gy)
    return XX, YY, np.column_stack([XX.ravel(), YY.ravel()])


def boundary_lines(ax, XX, YY, S, **kw):
    """Draw the boundaries of the rule argmax_k S[:, k] (S on the grid XX, YY): for each pair (j, k), the
    zero contour of S_j - S_k where j and k are the two largest scores."""
    K = S.shape[1]
    top = np.argsort(-S, axis=1)[:, :2]
    for j in range(K):
        for k in range(j + 1, K):
            if K == 2:
                Z = S[:, j] - S[:, k]
            else:
                pair = ((top[:, 0] == j) & (top[:, 1] == k)) | ((top[:, 0] == k) & (top[:, 1] == j))
                Z = np.where(pair, S[:, j] - S[:, k], np.nan)
            Z = Z.reshape(XX.shape)
            if np.isfinite(Z).sum() > 3 and np.nanmin(Z) < 0 < np.nanmax(Z):
                ax.contour(XX, YY, Z, levels=[0.0], **kw)


def class_panel(ax, X, g, colours, score, lim, bayes_score=None, protos=None, text=None, title=None,
                dots=(78, 72), lines=True):
    """The book's style for Figures 13.1-13.4: a lattice of small dots coloured by the predicted class,
    the decision boundary (black), the Bayes boundary (purple dashes), the training points (open
    circles) and prototypes (filled discs with a black edge)."""
    _, _, Pd = _grid(lim, *dots)
    cl = np.argmax(score(Pd), axis=1)
    for k, c in enumerate(colours):
        ax.scatter(Pd[cl == k, 0], Pd[cl == k, 1], s=0.7, color=c, lw=0, rasterized=True)
    XX, YY, P = _grid(lim, 400, 400)
    if lines:
        boundary_lines(ax, XX, YY, score(P), colors="black", linewidths=1.1)
    if bayes_score is not None:
        boundary_lines(ax, XX, YY, bayes_score(P), colors=PURPLE, linewidths=1.1, linestyles=[(0, (4, 3))])
    for k, c in enumerate(colours):
        ax.scatter(X[g == k, 0], X[g == k, 1], s=18, facecolors="none", edgecolors=c, linewidths=0.9)
    if protos is not None:
        M, Mg = protos
        for k, c in enumerate(colours):
            ax.scatter(M[Mg == k, 0], M[Mg == k, 1], s=62, color=c, edgecolors="black", linewidths=1.3, zorder=6)
    if text:
        ax.text(0.03, 0.03, text, transform=ax.transAxes, fontsize=8.3, va="bottom", ha="left",
                bbox=dict(boxstyle="round,pad=0.25", fc="white", ec="none", alpha=0.85), family="monospace")
    ax.set_xlim(*lim[0])
    ax.set_ylim(*lim[1])
    ax.set_xticks([])
    ax.set_yticks([])
    if title:
        ax.set_title(title)


def err_text(train, test, bayes, digits=3):
    f = "%." + str(digits) + "f"
    return ("Training Error: " + f + "\nTest Error:     " + f + "\nBayes Error:    " + f) % (train, test, bayes)


MIX_LIM = (ch12.XLIM, ch12.YLIM)


def mixture_bayes_score(means):
    def s(P):
        p = ch02.bayes_prob(P, means)
        return np.column_stack([1 - p, p])
    return s


# =========================================================================== Figure 13.1
LVQ_SIM3 = dict(eps0=0.05, epochs=20, seed=1)


def sim3_fits():
    d = sim3()
    M, Mg = kmeans_prototypes(d["X"], d["g"], 5, 3, seed=1)
    M2 = lvq1(d["X"], d["g"], M, Mg, **LVQ_SIM3)
    return d, (M, Mg), (M2, Mg)


def fig_13_1(out_dir=None):
    """Three-class simulation: K-means prototypes (five per class) and LVQ started from them."""
    import matplotlib.pyplot as plt
    d, km, lv = sim3_fits()
    fig, axes = plt.subplots(2, 1, figsize=(4.7, 9.0))
    res = {}
    for ax, (M, Mg), title in zip(axes, [km, lv], ["K-means - 5 Prototypes per Class", "LVQ - 5 Prototypes per Class"]):
        tr = error_rate(nearest_prototype(M, Mg, d["X"]), d["g"])
        te = error_rate(nearest_prototype(M, Mg, d["Xt"]), d["gt"])
        class_panel(ax, d["X"], d["g"], SIM3_COLOURS, lambda P, M=M, Mg=Mg: prototype_scores(M, Mg, P, 3), SIM3_LIM,
                    bayes_score=sim3_logdens, protos=(M, Mg), title=title, text=err_text(tr, te, d["bayes"]))
        res[title] = (tr, te)
        print("  %s: training error %.3f, test error %.4f (Bayes %.4f)" % (title, tr, te, d["bayes"]))
    fig.tight_layout()
    savefig(fig, CH, "fig13-1", out_dir)
    return res


# =========================================================================== Figure 13.2
def mixture_fits(R=5, seed=1):
    """K-means prototypes (R per class, the within-class K-means start of Chapter 12's MDA with seed 1)
    and the Gaussian mixture with a common covariance (MDA) fitted by EM from that start."""
    d = mixture()
    M, Mg = kmeans_prototypes(d["X"], d["g"], R, 2, seed=seed)
    md = ch12.MDAGauss([R, R], seed=seed).fit(d["X"], d["g"])
    return d, (M, Mg), md


def fig_13_2(out_dir=None):
    """Mixture data: K-means classifier (5 prototypes per class) and Gaussian mixtures (5 subclasses per
    class, common covariance, EM from the K-means start)."""
    import matplotlib.pyplot as plt
    d, (M, Mg), md = mixture_fits()
    fig, axes = plt.subplots(2, 1, figsize=(4.6, 7.6))
    res = {}
    bs = mixture_bayes_score(d["means"])
    km_score = lambda P: prototype_scores(M, Mg, P, 2)
    gm_score = md.class_scores
    for ax, sc, title, pro in [(axes[0], km_score, "K-means - 5 Prototypes per Class", (M, Mg)),
                               (axes[1], gm_score, "Gaussian Mixtures - 5 Subclasses per Class", (md.mu, md.cls))]:
        tr = error_rate(np.argmax(sc(d["X"]), 1), d["g"])
        te = error_rate(np.argmax(sc(d["Xt"]), 1), d["gt"])
        class_panel(ax, d["X"], d["g"], (MIX_BLUE, MIX_ORANGE), sc, MIX_LIM, bayes_score=bs, protos=pro,
                    title=title, text=err_text(tr, te, d["bayes"]))
        res[title] = (tr, te)
        print("  %s: training error %.3f, test error %.4f" % (title, tr, te))
    fig.tight_layout()
    savefig(fig, CH, "fig13-2", out_dir)
    return res


# =========================================================================== Figure 13.3
def knn_scores(Xtr, gtr, k, K):
    """Score function for class_panel: one-hot of the k-NN vote."""
    def s(P):
        lab = knn_predict(Xtr, gtr, P, k, K)
        return np.eye(K)[lab]
    return s


def fig_13_3(out_dir=None):
    """k-nearest-neighbour classifiers (k = 15 and k = 1) on the three-class simulation."""
    import matplotlib.pyplot as plt
    d = sim3()
    fig, axes = plt.subplots(2, 1, figsize=(4.7, 9.0))
    res = {}
    for ax, k in zip(axes, [15, 1]):
        tr = error_rate(knn_predict(d["X"], d["g"], d["X"], k, 3), d["g"])
        te = error_rate(knn_predict(d["X"], d["g"], d["Xt"], k, 3), d["gt"])
        class_panel(ax, d["X"], d["g"], SIM3_COLOURS, knn_scores(d["X"], d["g"], k, 3), SIM3_LIM,
                    bayes_score=sim3_logdens, title="%d-Nearest Neighbor%s" % (k, "s" if k > 1 else ""),
                    text=err_text(tr, te, d["bayes"]))
        res[k] = (tr, te)
        print("  %d-NN: training error %.3f, test error %.4f" % (k, tr, te))
    fig.tight_layout()
    savefig(fig, CH, "fig13-3", out_dir)
    return res


# =========================================================================== Figure 13.4
FIG134_KS = list(range(1, 30, 2))


def mixture_knn_curves(ks=FIG134_KS, folds=10, seed=13):
    """Training, test and ten-fold CV error (with standard errors) of k-NN on the mixture data."""
    d = mixture()
    X, g = d["X"], d["g"]
    otr, ote = knn_order(X, X), knn_order(X, d["Xt"])
    train = [error_rate(knn_vote(otr, g, k, 2), g) for k in ks]
    test = [error_rate(knn_vote(ote, g, k, 2), d["gt"]) for k in ks]
    cv, se, _ = knn_cv(X, g, ks, folds, seed)
    return d, dict(ks=list(ks), train=train, test=test, cv=list(cv), se=list(se))


def fig_13_4(out_dir=None):
    """k-NN on the mixture data: errors against k (with ten-fold CV and its standard errors) and the
    7-NN rule."""
    import matplotlib.pyplot as plt
    d, c = mixture_knn_curves()
    fig, axes = plt.subplots(2, 1, figsize=(4.6, 8.4), gridspec_kw=dict(height_ratios=[0.85, 1]))
    ax = axes[0]
    ks = np.array(c["ks"])
    ax.plot(ks, c["test"], "-o", color=MIX_ORANGE, ms=3.5, label="Test Error")
    ax.errorbar(ks, c["cv"], yerr=c["se"], fmt="-o", color=BLUE, ms=3.5, capsize=2.5, lw=1.3, label="10-fold CV")
    ax.plot(ks, c["train"], "-o", color=GREEN, ms=3.5, label="Training Error")
    ax.axhline(d["bayes"], color=PURPLE, ls="--", lw=1.2, label="Bayes Error")
    ax.set_xlabel("Number of Neighbors")
    ax.set_ylabel("Misclassification Errors")
    ax.set_xlim(0, 31)
    ax.set_ylim(0, 0.32)
    ax.legend(loc="lower right", frameon=False, fontsize=8.5)
    k = 7
    tr = error_rate(knn_predict(d["X"], d["g"], d["X"], k, 2), d["g"])
    te = error_rate(knn_predict(d["X"], d["g"], d["Xt"], k, 2), d["gt"])
    class_panel(axes[1], d["X"], d["g"], (MIX_BLUE, MIX_ORANGE), knn_scores(d["X"], d["g"], k, 2), MIX_LIM,
                bayes_score=mixture_bayes_score(d["means"]), title="7-Nearest Neighbors",
                text=err_text(tr, te, d["bayes"]))
    print("  7-NN: training error %.3f, test error %.4f" % (tr, te))
    j = int(np.argmin(c["cv"]))
    print("  CV minimum at k = %d (%.3f +- %.3f); test minimum at k = %d (%.4f)" % (ks[j], c["cv"][j], c["se"][j], ks[int(np.argmin(c["test"]))], min(c["test"])))
    fig.tight_layout()
    savefig(fig, CH, "fig13-4", out_dir)
    return c


# =========================================================================== Figure 13.5
def fig_13_5(out_dir=None):
    """The comparative study (13.6): mean +- one standard error over ten realisations of the test error
    of k-NN, K-means and LVQ on the 'easy' and 'difficult' problems."""
    import matplotlib.pyplot as plt
    S = study_results()
    fig, axes = plt.subplots(2, 2, figsize=(7.4, 6.6))
    for row, problem in enumerate(("easy", "difficult")):
        R = S[problem]
        ylim = (0.05, 0.55) if problem == "easy" else (0.38, 0.62)
        A = np.array(R["knn"])
        ax = axes[row, 0]
        ax.errorbar(STUDY_KS, A.mean(0), yerr=A.std(0, ddof=1) / math.sqrt(len(A)), color=BLUE, capsize=2, lw=1.3)
        ax.set_title("Nearest Neighbors / %s" % problem.capitalize())
        ax.set_xlabel("Number of Neighbors")
        ax.set_ylabel("Misclassification Error")
        ax.set_ylim(*ylim)
        ax = axes[row, 1]
        for key, col in (("km", BLUE), ("lvq", RED)):
            A = np.array(R[key])
            ax.errorbar(STUDY_RS, A.mean(0), yerr=A.std(0, ddof=1) / math.sqrt(len(A)), color=col, capsize=2,
                        lw=1.3, label="K-means" if key == "km" else "LVQ")
        ax.set_title("K-means & LVQ / %s" % problem.capitalize())
        ax.set_xlabel("Number of Prototypes per Class")
        ax.set_ylabel("Misclassification Error")
        ax.set_ylim(*ylim)
        ax.legend(frameon=False, fontsize=8.5, loc="upper right" if problem == "difficult" else "lower right")
        kn = np.array(R["knn"]).mean(0)
        print("  %s: k-NN error at k = 1: %.3f, best %.3f at k = %d; K-means best %.3f, LVQ best %.3f" % (
            problem, kn[0], kn.min(), STUDY_KS[int(np.argmin(kn))], np.array(R["km"]).mean(0).min(), np.array(R["lvq"]).mean(0).min()))
    fig.tight_layout()
    savefig(fig, CH, "fig13-5", out_dir)
    return S


# =========================================================================== Figures 13.9 and 13.10
def fig_13_9(out_dir=None):
    """Examples of the zip-code digits (16 x 16 grey levels)."""
    import matplotlib.pyplot as plt
    Xtr, gtr, _, _ = zip_digits()
    rng = np.random.default_rng(9)
    fig, axes = plt.subplots(4, 10, figsize=(7.4, 3.2))
    for c in range(10):
        idx = rng.choice(np.flatnonzero(gtr == c), 4, replace=False)
        for r in range(4):
            ax = axes[r, c]
            ax.imshow(Xtr[idx[r]].reshape(16, 16), cmap="gray_r", vmin=-1, vmax=1, interpolation="nearest")
            ax.set_xticks([])
            ax.set_yticks([])
    fig.subplots_adjust(wspace=0.08, hspace=0.08, left=0.01, right=0.99, top=0.99, bottom=0.01)
    savefig(fig, CH, "fig13-9", out_dir)


ZIP_THREE = 0     # which '3' of the training set Figure 13.10 shows (index among the 3s)


def three_and_tangent(idx=ZIP_THREE):
    Xtr, gtr, _, _ = zip_digits()
    v = Xtr[np.flatnonzero(gtr == 3)[idx]]
    S, T = tangents(v[None, :])
    return v, S[0], T[0, :, 2]


def fig_13_10(out_dir=None):
    """A '3' rotated by -15, -7.5, 0, 7.5 and 15 degrees (the invariance curve), the tangent line at the
    original image, images on the tangent line, and a two-dimensional view of the curve in pixel space."""
    import matplotlib.pyplot as plt
    from matplotlib.patches import Rectangle
    v, S, t = three_and_tangent()
    I = as_image(v)
    angles = [-15, -7.5, 0, 7.5, 15]
    alphas = [-0.2, -0.1, 0.0, 0.1, 0.2]
    fig = plt.figure(figsize=(6.4, 8.0))
    vmax = max(S.max(), 1e-9)

    def show(ax, img, edge, label):
        ax.imshow(img.reshape(16, 16), cmap="gray_r", vmin=0, vmax=vmax, interpolation="nearest")
        ax.add_patch(Rectangle((-0.5, -0.5), 16, 16, fill=False, ec=edge, lw=3))
        ax.set_xticks([])
        ax.set_yticks([])
        ax.set_xlabel(label, fontsize=9)
    for j, a in enumerate(angles):
        ax = fig.add_axes([0.04 + j * 0.19, 0.80, 0.16, 0.16])
        show(ax, rotate_image(I, a), "black" if a == 0 else GREEN, "%g°" % a)
    # the curve of rotated images in pixel space, seen in the plane of its tangent and curvature
    th = np.linspace(-30, 30, 121)
    curve = np.array([rotate_image(I, a) for a in th])
    e1 = t / np.linalg.norm(t)
    acc = curve[np.argmin(np.abs(th - 4))] + curve[np.argmin(np.abs(th + 4))] - 2 * S
    e2 = acc - (acc @ e1) * e1
    e2 /= np.linalg.norm(e2)
    C = (curve - S) @ np.column_stack([e1, e2])
    ax = fig.add_axes([0.12, 0.33, 0.78, 0.40])
    ax.plot(C[:, 0], C[:, 1], color=GREEN, lw=2, label="rotations of the 3 (invariance manifold)")
    s = np.array([-0.3, 0.3]) * np.linalg.norm(t)
    ax.plot(s, 0 * s, color=RED, lw=2, label="tangent line  3 + α · tangent")
    for a in angles:
        q = (rotate_image(I, a) - S) @ np.column_stack([e1, e2])
        ax.plot(*q, "o", color=GREEN if a else "black", ms=5)
    for al in alphas:
        ax.plot(al * np.linalg.norm(t), 0, "s", color=RED, ms=4)
    ax.set_xlabel("pixel space: direction of the tangent")
    ax.set_ylabel("orthogonal direction")
    ax.legend(frameon=False, fontsize=8.5, loc="upper center")
    ax.set_aspect("equal", adjustable="datalim")
    for j, al in enumerate(alphas):
        ax = fig.add_axes([0.04 + j * 0.19, 0.12, 0.16, 0.16])
        show(ax, S + al * t, "black" if al == 0 else RED, "α = %g" % al)
    ax = fig.add_axes([0.30, 0.0, 0.12, 0.10])
    show(ax, S, "black", "")
    ax = fig.add_axes([0.52, 0.0, 0.12, 0.10])
    ax.imshow(t.reshape(16, 16), cmap="RdBu_r", vmin=-np.abs(t).max(), vmax=np.abs(t).max(), interpolation="nearest")
    ax.set_xticks([])
    ax.set_yticks([])
    fig.text(0.46, 0.05, "+ α ·", fontsize=12, ha="center", va="center")
    fig.text(0.68, 0.05, "(α in radians)", fontsize=9, ha="left", va="center")
    savefig(fig, CH, "fig13-10", out_dir)


# =========================================================================== Figure 13.12
FIG1312_NS = (100, 1000, 10000)
FIG1312_MC_P = (1, 2, 3, 5, 8, 10, 12, 15)


def median_radius_table(reps=600):
    """Formula (13.7) and Monte Carlo medians of the 1-NN radius for N = 100, 1000, 10000. Cached."""
    path = os.path.join(CACHE_DIR, "ch13_median_radius.json")
    if os.path.exists(path):
        with open(path) as f:
            return json.load(f)
    out = {}
    for N in FIG1312_NS:
        out[str(N)] = {str(p): [median_radius(p, N), median_radius_mc(p, N, reps=reps if N < 10000 else reps // 2, seed=p,
                                                                    chunk=max(1, 200000 // (N * p)))]
                       for p in FIG1312_MC_P}
    with open(path, "w") as f:
        json.dump(out, f)
    return out


def fig_13_12(out_dir=None):
    """Median radius of a 1-nearest-neighbourhood for N uniform points in the cube [-1/2, 1/2]^p: formula
    (13.7) (lines) and Monte Carlo (dots)."""
    import matplotlib.pyplot as plt
    tab = median_radius_table()
    fig, ax = plt.subplots(figsize=(4.8, 3.9))
    ps = np.linspace(1, 15, 281)
    for N, col in zip(FIG1312_NS, (RED, GREEN, BLUE)):
        r = np.array([median_radius(p, N) for p in ps])
        inside = r <= 0.5
        ax.plot(ps[inside], r[inside], color=col, lw=1.6, label="N=%s" % format(N, ","))
        j = max(np.flatnonzero(inside).max(), 0)
        ax.plot(ps[j:], r[j:], color=col, lw=1.4, ls="--")
        mc = tab[str(N)]
        ax.plot([int(p) for p in mc], [v[1] for v in mc.values()], "o", color=col, ms=4, mfc="white")
    ax.axhline(0.5, color=GREY, lw=0.8, ls=":")
    ax.set_xlabel("Dimension")
    ax.set_ylabel("Median Radius")
    ax.set_ylim(0, 0.8)
    ax.set_xlim(0, 16)
    ax.legend(frameon=False, loc="upper left")
    fig.tight_layout()
    savefig(fig, CH, "fig13-12", out_dir)
    return tab


# =========================================================================== Figure 13.13
def strip_example(seed=None, n=26, x0=(0.43, 0.52)):
    """Figure 13.13: n points uniform in the unit square, class 0 (green) left of x = 1/2, class 1 (red)
    right; the target x0. Returns X, g, the 5 nearest neighbours in Euclidean distance and the 5 nearest
    in the horizontal coordinate only. With seed None the first seed (from 1) is used for which the
    Euclidean neighbourhood is dominated by the wrong class and the strip is not."""
    x0 = np.array(x0)
    s = 1 if seed is None else seed
    while True:
        rng = np.random.default_rng(s)
        X = rng.random((n, 2))
        g = (X[:, 0] > 0.5).astype(int)
        nb_e = np.argsort(((X - x0) ** 2).sum(1))[:5]
        nb_h = np.argsort(np.abs(X[:, 0] - x0[0]))[:5]
        if seed is not None or (g[nb_e].sum() >= 3 and g[nb_h].sum() <= 2):
            return dict(X=X, g=g, x0=x0, nb_e=nb_e, nb_h=nb_h, seed=s)
        s += 1


def fig_13_13(out_dir=None):
    """Five-nearest neighbourhoods at a target point near a vertical class boundary: the Euclidean disc
    and the strip found with the horizontal coordinate only."""
    import matplotlib.pyplot as plt
    from matplotlib.patches import Circle, Rectangle
    e = strip_example()
    X, g, x0 = e["X"], e["g"], e["x0"]
    fig, ax = plt.subplots(figsize=(4.2, 4.3))
    r = math.sqrt(((X[e["nb_e"]] - x0) ** 2).sum(1).max())
    w = np.abs(X[e["nb_h"], 0] - x0[0]).max()
    ax.add_patch(Rectangle((x0[0] - w, 0), 2 * w, 1, fc=(0.3, 0.6, 0.9, 0.18), ec=BLUE, lw=1.0))
    ax.add_patch(Circle(x0, r, fc=(0.9, 0.6, 0.2, 0.15), ec=ORANGE, lw=1.2))
    ax.axvline(0.5, color="black", lw=1.0)
    for k, c in enumerate((GREEN, RED)):
        ax.scatter(X[g == k, 0], X[g == k, 1], s=26, facecolors="none", edgecolors=c, linewidths=1.2)
    ax.plot(*x0, "o", color="black", ms=7)
    ax.set_xlim(0, 1)
    ax.set_ylim(0, 1)
    ax.set_aspect("equal")
    ax.set_xticks([])
    ax.set_yticks([])
    ax.set_title("5-Nearest Neighborhoods")
    print("  seed %d; Euclidean 5-NN: %d of 5 red; strip: %d of 5 red" % (e["seed"], g[e["nb_e"]].sum(), g[e["nb_h"]].sum()))
    fig.tight_layout()
    savefig(fig, CH, "fig13-13", out_dir)
    return e


# =========================================================================== Figure 13.14
RING2 = dict(lo=4.0, hi=9.0, n=200, seed=14)


def ring2_data(n=RING2["n"], seed=RING2["seed"], lo=RING2["lo"], hi=RING2["hi"]):
    """Two-dimensional analogue of Section 13.4.1: class 0 (orange) is N(0, I) conditioned on
    lo < ||x||^2 < hi, class 1 (blue) is N(0, I); n points each (numpy seed), rounded to 4 decimals."""
    X, g = shell_sample(n, np.random.default_rng(seed), p=2, lo=lo, hi=hi)
    return np.round(X, 4), g


FIG1314_QUERIES = np.round(np.array([[0.0, 0.0], [0.6, -0.9]] + [[2.0 * math.cos(math.radians(a)), 2.0 * math.sin(math.radians(a))]
                                                                   for a in (10, 75, 130, 190, 245, 300)]), 3)


def dann_ellipse(X, g, x0, k=15, km=50, eps=1.0, K=2):
    """The k-nearest neighbourhood of x0 in the DANN metric: (Sigma, radius^2, neighbour indices)."""
    S = dann_metric(X, g, x0, K, km, eps)[0]
    D = X - x0
    dist = np.einsum("ij,jk,ik->i", D, S, D)
    nb = np.argsort(dist, kind="stable")[:k]
    return S, dist[nb].max(), nb


def fig_13_14(out_dir=None):
    """DANN neighbourhoods (15 nearest in the metric estimated from 50 neighbours, eps = 1) at several
    query points, for two classes one surrounding the other."""
    import matplotlib.pyplot as plt
    X, g = ring2_data()
    fig, ax = plt.subplots(figsize=(4.8, 4.8))
    ax.scatter(X[g == 0, 0], X[g == 0, 1], s=16, facecolors="none", edgecolors=MIX_ORANGE, linewidths=0.9)
    ax.scatter(X[g == 1, 0], X[g == 1, 1], s=16, facecolors="none", edgecolors=MIX_BLUE, linewidths=0.9)
    t = np.linspace(0, 2 * np.pi, 200)
    for x0 in FIG1314_QUERIES:
        S, r2, nb = dann_ellipse(X, g, x0)
        vals, vecs = np.linalg.eigh(S)
        circ = np.stack([np.cos(t), np.sin(t)])
        pts = vecs @ (np.sqrt(r2 / vals)[:, None] * circ)
        ax.plot(pts[0] + x0[0], pts[1] + x0[1], color=TEAL, lw=1.1)
        ax.plot(*x0, "+", color="black", ms=9, mew=1.4)
    ax.set_aspect("equal")
    lim = 3.4
    ax.set_xlim(-lim, lim)
    ax.set_ylim(-lim, lim)
    ax.set_xticks([])
    ax.set_yticks([])
    fig.tight_layout()
    savefig(fig, CH, "fig13-14", out_dir)
    export_demo_data()


# =========================================================================== Figure 13.15
SHELL = dict(n=250, ntest=250, reps=10, seed=1996)
SHELL_LVQ = dict(eps0=0.05, epochs=20)


def shell_results():
    """Figure 13.15: ten realisations of the ten-dimensional example of Section 13.4.1 (250 training and
    250 test points per class): test errors of 5-NN, LVQ with 50 prototypes per class (from a K-means
    start) and DANN 5-NN (metric from 50 neighbours, eps = 1). Cached."""
    path = os.path.join(CACHE_DIR, "ch13_shell.json")
    if os.path.exists(path):
        with open(path) as f:
            return json.load(f)
    rng = np.random.default_rng(SHELL["seed"])
    out = dict(knn=[], lvq=[], dann=[])
    for rep in range(SHELL["reps"]):
        X, g = shell_sample(SHELL["n"], rng)
        Xt, gt = shell_sample(SHELL["ntest"], rng)
        out["knn"].append(error_rate(knn_predict(X, g, Xt, 5, 2), gt))
        M, Mg = kmeans_prototypes(X, g, 50, 2, seed=1 + rep, starts=1)
        M2 = lvq1(X, g, M, Mg, seed=100 + rep, **SHELL_LVQ)
        out["lvq"].append(error_rate(nearest_prototype(M2, Mg, Xt), gt))
        out["dann"].append(error_rate(dann_predict(X, g, Xt, k=5, km=50, eps=1.0), gt))
    with open(path, "w") as f:
        json.dump(out, f)
    return out


def shell_bayes_rate(p=10, lo=22.4, hi=40.0):
    """Bayes rate of Section 13.4.1 (equal priors): inside the shell the shell class has the larger density,
    so the errors are the class-1 points that fall in the shell: (1/2) Pr(lo < chi^2_p < hi)."""
    from scipy import stats
    return 0.5 * (stats.chi2.cdf(hi, p) - stats.chi2.cdf(lo, p))


def fig_13_15(out_dir=None):
    """Boxplots of the test error over ten realisations: 5-NN, LVQ (50 per class) and DANN 5-NN."""
    import matplotlib.pyplot as plt
    R = shell_results()
    fig, ax = plt.subplots(figsize=(3.8, 3.8))
    bp = ax.boxplot([R["knn"], R["lvq"], R["dann"]], tick_labels=["5NN", "LVQ", "DANN"], widths=0.5, patch_artist=True,
                    medianprops=dict(color="black"))
    for b in bp["boxes"]:
        b.set_facecolor("#7fd36f")
    ax.set_ylabel("Test Error")
    ax.set_ylim(0, 0.45)
    for key in ("knn", "lvq", "dann"):
        print("  %s: mean test error %.3f (sd %.3f)" % (key, np.mean(R[key]), np.std(R[key], ddof=1)))
    print("  Bayes rate %.4f" % shell_bayes_rate())
    fig.tight_layout()
    savefig(fig, CH, "fig13-15", out_dir)
    return R


def editing_condensing(seed=1):
    """Section 13.5 on the mixture data: 1-NN test error and the number of points kept with the full
    training set, after multi-edit, after multi-edit then condensing, and after condensing alone."""
    d = mixture()
    X, g, Xt, gt = d["X"], d["g"], d["Xt"], d["gt"]
    out = {"full": (len(X), error_rate(knn_predict(X, g, Xt, 1, 2), gt))}
    ke = multiedit(X, g, seed=seed)
    out["edited"] = (len(ke), error_rate(knn_predict(X[ke], g[ke], Xt, 1, 2), gt))
    kc = ke[condense(X[ke], g[ke], seed=seed)]
    out["edited+condensed"] = (len(kc), error_rate(knn_predict(X[kc], g[kc], Xt, 1, 2), gt))
    k2 = condense(X, g, seed=seed)
    out["condensed"] = (len(k2), error_rate(knn_predict(X[k2], g[k2], Xt, 1, 2), gt))
    out["idx"] = dict(edited=[int(i) for i in ke], edited_condensed=[int(i) for i in kc], condensed=[int(i) for i in k2])
    return out


# =========================================================================== exercises
def em_scalar(X, M0, sigma, iters=200, tol=1e-12):
    """Exercise 13.1: EM for a Gaussian mixture with R components, equal weights 1/R and fixed scalar
    covariance sigma^2 I (only the means are estimated), from the means M0. Returns (means,
    responsibilities)."""
    M = np.array(M0, dtype=float).copy()
    for _ in range(iters):
        L = -sqdist(X, M) / (2 * sigma ** 2)
        L -= L.max(1, keepdims=True)
        Rr = np.exp(L)
        Rr /= Rr.sum(1, keepdims=True)
        new = (Rr.T @ X) / np.maximum(Rr.sum(0), 1e-300)[:, None]
        if np.abs(new - M).max() < tol:
            M = new
            break
        M = new
    return M, Rr


def kmeans_from(X, M0, iters=200):
    """Lloyd's K-means from given centres (no restarts). Returns (centres, labels)."""
    M = np.array(M0, dtype=float).copy()
    lab = None
    for _ in range(iters):
        new = np.argmin(sqdist(X, M), axis=1)
        if lab is not None and np.array_equal(new, lab):
            break
        lab = new
        for r in range(len(M)):
            if (lab == r).any():
                M[r] = X[lab == r].mean(0)
    return M, lab


def exercise_13_1(sigmas=(1.0, 0.5, 0.3, 0.2, 0.1, 0.05, 0.02)):
    """EM with scalar covariance sigma^2 I against K-means from the same start (the blue class of the
    mixture data, R = 5): the largest distance between the two sets of centres, for each sigma."""
    d = mixture()
    Xb = d["X"][d["g"] == 0]
    C0, _ = kmeans_js(Xb, 5, 1, starts=1, iters=1)
    Mk, _ = kmeans_from(Xb, C0)
    out = []
    for s in sigmas:
        Me, Rr = em_scalar(Xb, C0, s)
        out.append((s, float(np.abs(Me - Mk).max()), float(1 - Rr.max(1).min())))
    return out


def signatures():
    """The three signatures of the book's website (96 points each, already time-warped into
    correspondence): a list of three 96 x 2 arrays."""
    import pandas as pd
    D = pd.read_csv(common.esl_file("signatureData.csv"), index_col=0).values
    return [D[:, 2 * j:2 * j + 2].astype(float) for j in range(3)]


def shape_averages(Ls, center=True):
    """Exercise 13.6. Criterion 1: min over V (V^T V = I) of sum_j min_A ||L_j - V A||^2, solved by the
    two leading eigenvectors of sum_j L_j L_j^T. Criterion 2 (affine invariant): min over V of
    sum_j min_A ||L_j A - V||^2, solved by the two leading eigenvectors of sum_j H_j with H_j the
    projection onto the column space of L_j. Returns (V1, V2, values of the two criteria at the
    solutions, eigenvalues)."""
    Ls = [L - L.mean(0) if center else L for L in Ls]
    S1 = sum(L @ L.T for L in Ls)
    S2 = sum(L @ np.linalg.solve(L.T @ L, L.T) for L in Ls)
    w1, U1 = np.linalg.eigh(S1)
    w2, U2 = np.linalg.eigh(S2)
    V1, V2 = U1[:, ::-1][:, :2], U2[:, ::-1][:, :2]
    c1 = sum(float(((L - V1 @ (V1.T @ L)) ** 2).sum()) for L in Ls)
    c2 = 0.0
    for L in Ls:
        A = np.linalg.lstsq(L, V2, rcond=None)[0]
        c2 += float(((L @ A - V2) ** 2).sum())
    return V1, V2, (c1, c2), (w1[::-1], w2[::-1])


def ex137_summary(S=None):
    """Exercise 13.7: for each problem, k chosen by test error, by five-fold CV and by the AIC-like
    criterion training error + 2 (N/k) / N; with the test error at each choice (means over the ten
    realisations, and per realisation)."""
    S = S or study_results()
    out = {}
    ks = np.array(STUDY_KS)
    for problem in ("easy", "difficult"):
        R = S[problem]
        te, cv, tr = np.array(R["knn"]), np.array(R["cv5"]), np.array(R["train"])
        aic = tr + 2.0 / ks[None, :]
        per = dict(cv=[], aic=[])
        for r in range(len(te)):
            per["cv"].append(te[r, int(np.argmin(cv[r]))])
            per["aic"].append(te[r, int(np.argmin(aic[r]))])
        out[problem] = dict(k_test=int(ks[np.argmin(te.mean(0))]), k_cv=int(ks[np.argmin(cv.mean(0))]),
                            k_aic=int(ks[np.argmin(aic.mean(0))]), test_min=float(te.mean(0).min()),
                            err_cv=float(np.mean(per["cv"])), err_aic=float(np.mean(per["aic"])),
                            curves=dict(test=list(te.mean(0)), cv=list(cv.mean(0)), aic=list(aic.mean(0))))
    return out


def rotation_sample(n, rng, mu0=(-1.0, -1.0), mu1=(1.0, 1.0)):
    """Exercise 13.8: n points per class, class 0 ~ N(mu0, I), class 1 ~ N(mu1, I), each point then
    rotated about the origin by its own angle theta ~ U(0, 2 pi)."""
    X = np.vstack([rng.normal(size=(n, 2)) + np.asarray(mu0, float), rng.normal(size=(n, 2)) + np.asarray(mu1, float)])
    th = rng.uniform(0, 2 * np.pi, 2 * n)
    c, s = np.cos(th), np.sin(th)
    X = np.column_stack([c * X[:, 0] - s * X[:, 1], s * X[:, 0] + c * X[:, 1]])
    return X, np.r_[np.zeros(n, int), np.ones(n, int)]


def _rot_dist(kind, A, B):
    """Squared distances between rows of A (queries) and B (training) for Exercise 13.8: Euclidean,
    invariant (| ||a|| - ||b|| |^2, the distance between the two orbits under rotation about the origin)
    or one-sided tangent distance to the tangent line of each training point b (the squared component of
    a - b along b / ||b||)."""
    if kind == "invariant":
        return (np.linalg.norm(A, axis=1)[:, None] - np.linalg.norm(B, axis=1)[None, :]) ** 2
    if kind == "tangent":
        u = B / np.linalg.norm(B, axis=1, keepdims=True)
        return (A @ u.T - (B * u).sum(1)[None, :]) ** 2
    return sqdist(A, B)


def _rot_knn_err(kind, X, g, Xq, gq, ks, groups=None):
    D = _rot_dist(kind, Xq, X)
    order = np.argsort(D, axis=1, kind="stable")
    return [error_rate(knn_vote(order, g, k, 2), gq) for k in ks]


def exercise_13_8(mu0=(-1.0, -1.0), mu1=(1.0, 1.0), reps=20, seed=138, ks=tuple(range(1, 32, 2)), n_hint=10):
    """Exercise 13.8: four nearest-neighbour classifiers (plain, with hints = ten rotated copies of each
    training point, invariant metric, one-sided tangent distance), k by ten-fold CV; 50 training and
    500 test points per class; mean test error (and sd) over reps realisations."""
    rng = np.random.default_rng(seed)
    res = {m: [] for m in ("nn", "hints", "invariant", "tangent")}
    for rep in range(reps):
        X, g = rotation_sample(50, rng, mu0, mu1)
        Xt, gt = rotation_sample(500, rng, mu0, mu1)
        fold = rng.permutation(np.arange(len(X)) % 10)
        th = rng.uniform(0, 2 * np.pi, (len(X), n_hint))

        def hints(Xs, gs, ths):
            c, s = np.cos(ths), np.sin(ths)
            R = np.stack([c * Xs[:, None, 0] - s * Xs[:, None, 1], s * Xs[:, None, 0] + c * Xs[:, None, 1]], -1)
            return np.vstack([Xs, R.reshape(-1, 2)]), np.r_[gs, np.repeat(gs, ths.shape[1])]
        for m in res:
            cv = np.zeros(len(ks))
            for v in range(10):
                tr, te = fold != v, fold == v
                Xa, ga = (hints(X[tr], g[tr], th[tr]) if m == "hints" else (X[tr], g[tr]))
                cv += np.array(_rot_knn_err("euclid" if m in ("nn", "hints") else m, Xa, ga, X[te], g[te], ks))
            kbest = ks[int(np.argmin(cv))]
            Xa, ga = (hints(X, g, th) if m == "hints" else (X, g))
            res[m].append(_rot_knn_err("euclid" if m in ("nn", "hints") else m, Xa, ga, Xt, gt, [kbest])[0])
    return {m: (float(np.mean(v)), float(np.std(v, ddof=1))) for m, v in res.items()}


def rotation_bayes_rate(mu0=(-1.0, -1.0), mu1=(1.0, 1.0), n=200000):
    """Bayes rate of Exercise 13.8 by numerical integration over the radius: after a uniform random
    rotation the class densities depend on x only through r = ||x||, and r has the Rice density with
    parameter ||mu_k|| in class k; returns 1/2 integral of min(f0, f1) dr."""
    from scipy import stats
    r = np.linspace(1e-6, 15, n)
    f0 = stats.rice.pdf(r, np.linalg.norm(mu0))
    f1 = stats.rice.pdf(r, np.linalg.norm(mu1))
    return 0.5 * float(np.trapz(np.minimum(f0, f1), r))


# =========================================================================== the Cover-Hart demonstration
SPIRAL_OMEGA = 5.0       # twist of the spiral problem
SPIRAL_GRID = 200        # midpoint grid for the integrals over [0, 1]^2
SPIRAL_TEST_SEED = 777
SPIRAL_NTEST = 2000


def spiral_probs(P, beta, K):
    """Class probabilities of the spiral problem of cover-hart-demo.html: x uniform on [0, 1]^2,
    z = 2x - 1 = r (cos t, sin t), score s_k = beta r cos(t - 2 pi k / K - omega r), p = softmax(s)."""
    P = np.atleast_2d(P)
    z = 2 * P - 1
    r = np.hypot(z[:, 0], z[:, 1])
    t = np.arctan2(z[:, 1], z[:, 0])
    S = np.column_stack([beta * r * np.cos(t - 2 * np.pi * k / K - SPIRAL_OMEGA * r) for k in range(K)])
    S -= S.max(1, keepdims=True)
    E = np.exp(S)
    return E / E.sum(1, keepdims=True)


def spiral_sample(N, beta, K, seed):
    """N training points drawn with the demos' generator: three uniforms per point (x1, x2, then the
    class by inversion of the cumulative class probabilities)."""
    U = ch02.js_uniforms(seed, 3 * N).reshape(N, 3)
    X = U[:, :2]
    Pc = np.cumsum(spiral_probs(X, beta, K), axis=1)
    g = (U[:, 2:3] >= Pc).sum(1)
    return X, np.minimum(g, K - 1)


def spiral_test_points():
    return ch02.js_uniforms(SPIRAL_TEST_SEED, 2 * SPIRAL_NTEST).reshape(SPIRAL_NTEST, 2)


def spiral_integrals(beta, K, kmax=51):
    """E* (Bayes rate), E1 (asymptotic 1-NN rate, the mean of (13.3)), the Cover-Hart bound (13.12) and,
    for K = 2, the asymptotic k-NN rates for odd k <= kmax, by the midpoint rule on SPIRAL_GRID^2 cells."""
    h = 1.0 / SPIRAL_GRID
    c = (np.arange(SPIRAL_GRID) + 0.5) * h
    XX, YY = np.meshgrid(c, c)
    P = spiral_probs(np.column_stack([XX.ravel(), YY.ravel()]), beta, K)
    Es = float(bayes_cond_error(P).mean())
    E1 = float(nn_asymptotic_cond_error(P).mean())
    out = dict(bayes=Es, nn1=E1, bound=cover_hart_bound(Es, K), bound_pointwise=float(cover_hart_cond_bound(P).mean()))
    if K == 2:
        out["knn_inf"] = {k: float(knn_asymptotic_cond_error(P[:, 1], k).mean()) for k in range(1, kmax + 1, 2)}
    return out


def spiral_knn_errors(N, beta, K, seed, ks):
    """Expected test error (the mean over the fixed test points of 1 - p_{predicted}(x)) of the k-NN rule
    for each k in ks, trained on spiral_sample(N, beta, K, seed)."""
    X, g = spiral_sample(N, beta, K, seed)
    T = spiral_test_points()
    P = spiral_probs(T, beta, K)
    order = knn_topk(X, T, max(ks))
    return [float(1 - P[np.arange(len(T)), knn_vote(order, g, k, K)].mean()) for k in ks]


# =========================================================================== exports for the demonstrations
def export_demo_data():
    """../data/ch13-prototypes.json (three-class simulation) and ../data/ch13-dann.json (the two-dimensional
    ring data of Figure 13.14 and the strip data of Figure 13.13, with test sets)."""
    os.makedirs(DATA_OUT, exist_ok=True)
    d = sim3()
    r4 = lambda A: [[round(float(a), 4) for a in row] for row in A]
    out = {"note": "Three-class simulation of the course's Figures 13.1 and 13.3 (Hastie, Tibshirani and Friedman 2009, "
                   "Section 13.2): class k is an equal mixture of N(m_kl, s2 I), l = 1..5; 100 training and 3000 test points per class.",
           "x": r4(d["X"]), "y": [int(v) for v in d["g"]], "xtest": r4(d["Xt"]), "ytest": [int(v) for v in d["gt"]],
           "centres": SIM3_CENTRES.tolist(), "s2": SIM3_S2, "bayes_rate": round(float(d["bayes"]), 5),
           "lim": [list(SIM3_LIM[0]), list(SIM3_LIM[1])]}
    with open(os.path.join(DATA_OUT, "ch13-prototypes.json"), "w") as f:
        json.dump(out, f, separators=(",", ":"))
    X, g = ring2_data()
    Xt, gt = ring2_data(n=500, seed=RING2["seed"] + 1)
    e = strip_data()
    out = {"note": "Two-dimensional examples of Hastie, Tibshirani and Friedman (2009), Section 13.4: 'ring' (class 0 is N(0, I) "
                   "conditioned on 4 < |x|^2 < 9, class 1 is N(0, I); 200 training and 500 test points per class) and 'strip' "
                   "(uniform on the unit square, class 0 left of x1 = 1/2 with probability 0.9; 200 training and 2000 test points).",
           "ring": {"x": r4(X), "y": [int(v) for v in g], "xtest": r4(Xt), "ytest": [int(v) for v in gt]},
           "strip": {"x": r4(e[0]), "y": [int(v) for v in e[1]], "xtest": r4(e[2]), "ytest": [int(v) for v in e[3]]}}
    with open(os.path.join(DATA_OUT, "ch13-dann.json"), "w") as f:
        json.dump(out, f, separators=(",", ":"))
    print("wrote ../data/ch13-prototypes.json and ../data/ch13-dann.json")


def strip_data(n=200, ntest=2000, seed=1313, flip=0.1):
    """Uniform points on the unit square; class 0 if x1 < 1/2, class 1 otherwise, each label flipped with
    probability flip (so the Bayes rate is flip). Training and test sets, rounded to 4 decimals."""
    rng = np.random.default_rng(seed)
    out = []
    for m in (n, ntest):
        X = np.round(rng.random((m, 2)), 4)
        g = (X[:, 0] >= 0.5).astype(int)
        g = np.where(rng.random(m) < flip, 1 - g, g)
        out += [X, g]
    return out


def dann_demo_state(data, x0, k=15, km=50, eps=1.0):
    """What dann-demo.html shows at query x0: the metric, the DANN and Euclidean k-NN neighbourhoods and
    their votes, and the test errors of DANN and plain k-NN on the data set's test points."""
    X, g = np.array(data["x"]), np.array(data["y"])
    Xt, gt = np.array(data["xtest"]), np.array(data["ytest"])
    S, W, B, nb = dann_metric(X, g, np.asarray(x0, float), 2, km, eps)
    D = X - x0
    dd = np.einsum("ij,jk,ik->i", D, S, D)
    nbd = np.argsort(dd, kind="stable")[:k]
    nbe = np.argsort((D ** 2).sum(1), kind="stable")[:k]
    return dict(Sigma=S, W=W, B=B, nb_dann=nbd, nb_euclid=nbe,
                err_dann=error_rate(dann_predict(X, g, Xt, k=k, km=km, eps=eps), gt),
                err_knn=error_rate(knn_predict(X, g, Xt, k, 2), gt))


# =========================================================================== supplementary figures
def fig_13_s1(out_dir=None):
    """Exercise 13.6: the three signatures, their average under criterion 1 (two leading eigenvectors of
    sum L L^T) and under the affine-invariant criterion 2 (sum of projections), each shown after the
    best affine map back to the scale of the first signature."""
    import matplotlib.pyplot as plt
    Ls = signatures()
    Lc = [L - L.mean(0) for L in Ls]
    scaled = [Lc[0], Lc[1], 3.0 * Lc[2]]          # make one letter big, to show the difference
    fig, axes = plt.subplots(1, 3, figsize=(8.4, 2.9))
    for j, L in enumerate(scaled):
        axes[0].plot(L[:, 0], L[:, 1], lw=1.2, color=(BLUE, ORANGE, GREEN)[j], label="signature %d%s" % (j + 1, " (x3)" if j == 2 else ""))
    axes[0].set_title("Data (third one enlarged)")
    axes[0].legend(frameon=False, fontsize=7.5)
    V1, V2, _, _ = shape_averages(scaled)
    for ax, V, title in [(axes[1], V1, "Criterion 1: eig of sum L L^T"), (axes[2], V2, "Criterion 2: eig of sum of projections")]:
        for j, L in enumerate(scaled):
            A = np.linalg.lstsq(L, V, rcond=None)[0]
            Z = L @ A
            ax.plot(Z[:, 0], Z[:, 1], lw=0.8, color=(BLUE, ORANGE, GREEN)[j], alpha=0.6)
        ax.plot(V[:, 0], V[:, 1], color="black", lw=1.8)
        ax.set_title(title, fontsize=9)
    for ax in axes:
        ax.set_aspect("equal", adjustable="datalim")
        ax.set_xticks([])
        ax.set_yticks([])
    fig.tight_layout()
    savefig(fig, CH, "fig13-s1", out_dir)


def fig_13_s2(out_dir=None):
    """Exercise 13.7: test error, five-fold CV error and the AIC-like penalised training error of k-NN
    against k on the easy and difficult problems (means over ten realisations)."""
    import matplotlib.pyplot as plt
    E = ex137_summary()
    fig, axes = plt.subplots(1, 2, figsize=(7.4, 3.2))
    for ax, problem in zip(axes, ("easy", "difficult")):
        c = E[problem]["curves"]
        ax.plot(STUDY_KS, c["test"], "-o", color=BLUE, ms=3, label="test error")
        ax.plot(STUDY_KS, c["cv"], "-o", color=RED, ms=3, label="5-fold CV")
        ax.plot(STUDY_KS, c["aic"], "-o", color=GREEN, ms=3, label="training + 2/k")
        ax.set_title("Nearest Neighbors / %s" % problem.capitalize())
        ax.set_xlabel("Number of Neighbors")
        ax.set_ylabel("Misclassification Error")
        ax.set_ylim(0, 0.75)
        ax.legend(frameon=False, fontsize=8)
        print("  %s: k by test %d, by CV %d, by AIC %d; mean test error at CV choice %.3f, at AIC choice %.3f (best %.3f)" % (
            problem, E[problem]["k_test"], E[problem]["k_cv"], E[problem]["k_aic"], E[problem]["err_cv"], E[problem]["err_aic"], E[problem]["test_min"]))
    fig.tight_layout()
    savefig(fig, CH, "fig13-s2", out_dir)
    return E


SPIRAL_FIG = dict(beta=6.0, K=2, Ns=(100, 1000, 10000), seed=1)


def fig_13_s3(out_dir=None):
    """The Cover-Hart bound on the spiral problem of cover-hart-demo.html: the class probability, and the
    expected test error of k-NN against k for three training sizes, with the asymptotic k-NN errors,
    the Bayes rate E*, the asymptotic 1-NN rate E1 and the bound E*(2 - 2E*)."""
    import matplotlib.pyplot as plt
    b, K = SPIRAL_FIG["beta"], SPIRAL_FIG["K"]
    I = spiral_integrals(b, K)
    ks = list(range(1, 52, 2))
    fig, axes = plt.subplots(1, 2, figsize=(8.2, 3.7), gridspec_kw=dict(width_ratios=[0.8, 1.2]))
    c = np.linspace(0, 1, 300)
    XX, YY = np.meshgrid(c, c)
    P = spiral_probs(np.column_stack([XX.ravel(), YY.ravel()]), b, K)[:, 1].reshape(XX.shape)
    ax = axes[0]
    ax.imshow(P, origin="lower", extent=(0, 1, 0, 1), cmap="RdBu_r", vmin=0, vmax=1)
    ax.contour(XX, YY, P, levels=[0.5], colors="black", linewidths=1)
    X, g = spiral_sample(500, b, K, SPIRAL_FIG["seed"])
    ax.scatter(X[:, 0], X[:, 1], s=5, c=np.where(g == 1, RED, BLUE), lw=0)
    ax.set_title("Pr(class 2 | x) and 500 training points", fontsize=9)
    ax.set_xticks([])
    ax.set_yticks([])
    ax = axes[1]
    for N, col in zip(SPIRAL_FIG["Ns"], (ORANGE, GREEN, BLUE)):
        e = np.mean([spiral_knn_errors(N, b, K, SPIRAL_FIG["seed"] + r, ks) for r in range(3)], axis=0)
        ax.plot(ks, e, "-o", ms=2.5, color=col, label="N = %s" % format(N, ","))
    ax.plot(ks, [I["knn_inf"][k] for k in ks], color="black", lw=1.5, label="N = ∞ (k fixed)")
    ax.axhline(I["bayes"], color=PURPLE, ls="--", lw=1.2, label="Bayes rate E* = %.3f" % I["bayes"])
    ax.axhline(I["bound"], color=RED, ls=":", lw=1.4, label="bound 2E*(1-E*) = %.3f" % I["bound"])
    ax.set_xlabel("Number of Neighbors k")
    ax.set_ylabel("Expected test error")
    ax.legend(frameon=False, fontsize=7.5, loc="upper right")
    ax.set_ylim(0.0, max(0.5, I["bound"] + 0.05))
    print("  E* = %.4f, E1 = %.4f, bound = %.4f" % (I["bayes"], I["nn1"], I["bound"]))
    fig.tight_layout()
    savefig(fig, CH, "fig13-s3", out_dir)
    return I


# =========================================================================== driver
FIGURES = {
    "13.1": fig_13_1, "13.2": fig_13_2, "13.3": fig_13_3, "13.4": fig_13_4, "13.5": fig_13_5,
    "13.9": fig_13_9, "13.10": fig_13_10, "13.12": fig_13_12, "13.13": fig_13_13, "13.14": fig_13_14,
    "13.15": fig_13_15, "13.S1": fig_13_s1, "13.S2": fig_13_s2, "13.S3": fig_13_s3,
}


def table_13_1(out_dir=None):
    """Table 13.1: 1-NN with Euclidean and tangent distance on the zip-code data (printed)."""
    r = zip_table()
    for k, v in r.items():
        print("  %-30s %s" % (k, v))
    return r


FIGURES["T13.1"] = table_13_1


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