"""Murphy (2022), Chapter 16: Exemplar-based Methods.

Companion code for Chapter 16 of K. P. Murphy, Probabilistic Machine Learning: An Introduction
(MIT Press, 2022; April 2025 draft), pp. 547-565, written from scratch with numpy, scipy, matplotlib
and (only for the deep metric learning experiment) PyTorch, to be read next to the lecture notes
(../ch16-exemplar-based-methods.html). scikit-learn is used to load the wine and digits data and to
confirm the implementations.

Methods
* Section 16.1, K nearest neighbours: the predictive distribution (16.1) with a Mahalanobis metric
  (16.2) and a deterministic tie rule (knn_proba, knn_predict), the whole error curve against K in one
  pass (knn_error_curve), the 1-NN Voronoi cells, the edge length of a hypercube that captures a
  fraction p of the data (16.3b), an exact k-d tree with a count of the distance evaluations (KDTree1,
  the cost of exact search against the dimension), random-hyperplane locality-sensitive hashing
  (lsh_collision), the asymptotic 1-NN and K-NN error against the Cover-Hart bound, and open-set
  recognition by thresholding the nearest-exemplar distance.
* Section 16.2, learning distance metrics: large margin nearest neighbours by projected gradient
  descent on M (lmnn_fit, objective (16.4)-(16.5)); neighbourhood components analysis with the gradient
  of the expected number of correct leave-one-out classifications (nca_obj_grad, nca_fit, (16.6));
  latent coincidence analysis with the closed-form marginal likelihood and an exact EM algorithm
  (lca_loglik, lca_em); the losses of deep metric learning (contrastive (16.10), triplet (16.11),
  N-pairs / InfoNCE (16.12)-(16.13), temperature-scaled version), the triplet taxonomy of Figure 16.6a
  (triplet_category), the proxy upper bound (16.20)-(16.22) (proxy_bound_terms) and a small training
  experiment on the digits data (dml_experiment).
* Section 16.3, kernel density estimation: the density kernels of Table 16.1 (KERNELS), the Parzen
  estimator (16.33) (kde), the Gaussian-reference bandwidth with a robust scale (16.3.3) (silverman_h),
  the exact mean integrated squared error of a Gaussian KDE under a Gaussian truth (gauss_kde_mise), the
  Nadaraya-Watson mean (16.39) and variance (16.45) (nw_fit, nw_var), and local linear regression
  (16.47) (loess_fit).

Data. The wine and digits data come from scikit-learn. The three-class 2-D data of Figures 16.1 and
16.2, the 1-D regression data of Figure 16.10, and the uniform-cube data of the curse-of-dimensionality
experiments are simulated (seeds fixed in the code), because the book's own point sets are not
available offline; those figures are close stand-ins, not copies. The six points of Figure 16.9 are the
ones of the standard textbook example for the Parzen estimator.

Figures. Reproduced here: 16.1 (a, b), 16.2 (a to d), 16.3b, 16.6a (redrawn with computed points),
16.8, 16.9, 16.10. Skipped, with the reason:
  16.3a  a hand-drawn sketch of a small cube inside the unit cube (nothing is computed);
  16.4   the graphical model of latent coincidence analysis (a hand-drawn diagram; the model is
         implemented in lca_loglik and lca_em instead);
  16.5   the Siamese and triplet network diagrams (hand-drawn architecture sketches);
  16.6b  the proxy-loss counting diagram (its numbers, 8 x 3 x 4 = 96 against 8 x 2 = 16, are
         arithmetic stated in the notes);
  16.7   the spherical embedding constraint sketch (a hand-drawn illustration).
Supplementary figures for the gaps filled in the notes (names fig16-s1, ...):
  16.S1  asymptotic 1-NN and K-NN error against the Bayes error and the Cover-Hart bound;
  16.S2  the curse of dimensionality for KNN: nuisance coordinates, and a metric that ignores them;
  16.S3  exact k-d tree search cost against the dimension, and the collision probability of random
         hyperplane hashing;
  16.S4  metric learning: NCA and LMNN on a 2-D toy problem and on the wine data;
  16.S5  latent coincidence analysis: the monotone EM log-likelihood and the learned projection;
  16.S6  open-set recognition on the digits: nearest-exemplar distance, ROC curve;
  16.S7  deep metric learning on the digits (contrastive, triplet, N-pairs) and retrieval of unseen
         classes;
  16.S8  kernel regression: the Nadaraya-Watson boundary bias against local linear regression, and
         the predictive standard deviation (16.45);
  16.S9  the exact MISE of a Gaussian KDE against the bandwidth, with the rule of 16.3.3.
Run `python3 ch16_exemplar_based_methods.py --list`, `python3 ch16_exemplar_based_methods.py` (all
figures, several minutes) or `python3 ch16_exemplar_based_methods.py --fig 16.2`. Files go to
../img/ch16/; the data used by the browser demonstrations go to ../data/ch16-*.json.
"""
import json
import math
import os
import sys

os.environ.setdefault("OPENBLAS_NUM_THREADS", "1")

import numpy as np
from scipy import integrate, optimize, special, stats

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

CH = 16
HERE = os.path.dirname(os.path.abspath(__file__))
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
CACHE_DIR = os.path.join(HERE, "cache")
CLS3 = (RED, BLUE, GREEN)


def _r(a, nd=4):
    return np.round(np.asarray(a, float), nd).tolist()


# =========================================================================== data
def three_class_2d(n_train=120, n_test=3000, seed=16):
    """Simulated 2-D, three-class data in the ranges of Figure 16.2 (x in [-20, 20], y in [-20, 30]):
    every class is a mixture of two Gaussians, and the classes overlap, so that K = 1 interpolates
    the noise and a moderate K is best."""
    rng = np.random.default_rng(seed)
    comps = {0: [((-9, 14), (6.5, 6.0)), ((5, -8), (7.0, 5.5))],
             1: [((10, 10), (6.0, 7.0)), ((-10, -9), (6.0, 6.5))],
             2: [((0, 1), (6.0, 6.0)), ((17, -9), (3.5, 5.0))]}

    def draw(n):
        y = np.arange(n) % 3
        X = np.zeros((n, 2))
        for c in range(3):
            idx = np.where(y == c)[0]
            which = rng.integers(0, 2, len(idx))
            for k, i in enumerate(idx):
                mu, sd = comps[c][which[k]]
                X[i] = rng.normal(mu, sd)
        perm = rng.permutation(n)
        return X[perm], y[perm]
    Xtr, ytr = draw(n_train)
    Xte, yte = draw(n_test)
    return Xtr, ytr, Xte, yte


def disc_cube(n, D, rng, radius2=0.1):
    """Points uniform in [0,1]^D; class 1 iff (x1-.5)^2 + (x2-.5)^2 < radius2 (only two coordinates
    carry information). Used for the curse-of-dimensionality experiments (Section 16.1.2)."""
    X = rng.random((n, D))
    y = (((X[:, 0] - .5) ** 2 + (X[:, 1] - .5) ** 2) < radius2).astype(int)
    return X, y


# =========================================================================== Section 16.1: KNN
def sqdist(A, B):
    """Matrix of squared Euclidean distances between the rows of A and the rows of B."""
    D = (A * A).sum(1)[:, None] + (B * B).sum(1)[None, :] - 2.0 * A @ B.T
    return np.maximum(D, 0.0)


def apply_metric(M_or_W, X, kind="W"):
    """Rows of X mapped to W x, so that Euclidean distance after the map is the Mahalanobis distance
    (16.2) with M = W'W. kind='M' factors a positive semi-definite M by its eigendecomposition."""
    if M_or_W is None:
        return X
    if kind == "M":
        w, V = np.linalg.eigh(M_or_W)
        W = (V * np.sqrt(np.maximum(w, 0.0))).T
    else:
        W = M_or_W
    return X @ W.T


def knn_order(Xtr, Xq, W=None):
    """Indices of the training points sorted by distance from every query (stable: ties go to the
    lower index)."""
    if W is not None:
        Xtr, Xq = Xtr @ W.T, Xq @ W.T
    return np.argsort(sqdist(Xq, Xtr), axis=1, kind="stable")


def knn_proba(Xtr, ytr, Xq, K, C=None, W=None, order=None):
    """Equation (16.1): p(y = c | x, D) = (1/K) sum_{n in N_K(x)} 1(y_n = c)."""
    C = C or int(ytr.max()) + 1
    order = knn_order(Xtr, Xq, W) if order is None else order
    P = np.zeros((len(Xq), C))
    for r in range(K):
        np.add.at(P, (np.arange(len(Xq)), ytr[order[:, r]]), 1.0)
    return P / K


def _decide(cnt, first):
    """Class with the largest count; ties go to the tied class that owns the nearest neighbour
    (the smallest rank of its first member)."""
    top = cnt == cnt.max(1, keepdims=True)
    return np.where(top, first, np.inf).argmin(1)


def knn_predict(Xtr, ytr, Xq, K, C=None, W=None, order=None):
    """Majority label of (16.1); a tie between classes is broken in favour of the tied class that owns
    the nearest of the K neighbours."""
    C = C or int(ytr.max()) + 1
    order = knn_order(Xtr, Xq, W) if order is None else order
    n = len(Xq)
    cnt = np.zeros((n, C))
    first = np.full((n, C), np.inf)
    for r in range(K):
        lab = ytr[order[:, r]]
        np.add.at(cnt, (np.arange(n), lab), 1.0)
        cur = first[np.arange(n), lab]
        first[np.arange(n), lab] = np.minimum(cur, r)
    return _decide(cnt, first)


def knn_error_curve(Xtr, ytr, Xq, yq, Ks, C=None, W=None, loo=False):
    """Misclassification rate of K-NN for every K in Ks (the same tie rule as knn_predict), in one pass over
    the neighbours. With loo=True the query points are the training points and each one is excluded from its
    own neighbourhood."""
    C = C or int(ytr.max()) + 1
    order = knn_order(Xtr, Xq, W)
    if loo:
        order = order[:, 1:]
    n = len(Xq)
    cnt = np.zeros((n, C))
    first = np.full((n, C), np.inf)
    err = {}
    for r in range(max(Ks)):
        lab = ytr[order[:, r]]
        np.add.at(cnt, (np.arange(n), lab), 1.0)
        first[np.arange(n), lab] = np.minimum(first[np.arange(n), lab], r)
        if r + 1 in Ks:
            err[r + 1] = float(np.mean(_decide(cnt, first) != yq))
    return err


def edge_length(p, D):
    """Expected edge length p^(1/D) of the hypercube that holds a fraction p of uniform data (16.3b)."""
    return np.asarray(p, float) ** (1.0 / D)


def nn_distance_median(N, D):
    """Median distance from the origin to the closest of N points uniform in the unit D-ball:
    (1 - 2^(-1/N))^(1/D)."""
    return (1.0 - 0.5 ** (1.0 / N)) ** (1.0 / D)


# === an exact k-d tree that counts its work -------------------------------------------------
class KDTree1:
    """A median-split k-d tree (leaf size 1) with exact nearest-neighbour search by branch and bound.
    search() returns the neighbour index and the number of distance evaluations performed, which is the
    cost the notes compare with the N evaluations of a linear scan."""

    def __init__(self, X):
        self.X = X
        self.root = self._build(np.arange(len(X)), 0)

    def _build(self, idx, depth):
        if len(idx) == 1:
            return ("leaf", int(idx[0]))
        spread = self.X[idx].max(0) - self.X[idx].min(0)
        dim = int(np.argmax(spread))
        order = idx[np.argsort(self.X[idx, dim], kind="stable")]
        m = len(order) // 2
        return ("node", dim, float(self.X[order[m], dim]), self._build(order[:m], depth + 1), self._build(order[m:], depth + 1))

    def search(self, q):
        best = [np.inf, -1]
        cnt = [0]

        def rec(node):
            if node[0] == "leaf":
                d = float(((self.X[node[1]] - q) ** 2).sum())
                cnt[0] += 1
                if d < best[0]:
                    best[0], best[1] = d, node[1]
                return
            _, dim, split, left, right = node
            near, far = (left, right) if q[dim] < split else (right, left)
            rec(near)
            if (q[dim] - split) ** 2 < best[0]:
                rec(far)
        rec(self.root)
        return best[1], cnt[0]


def lsh_collision(theta, ntrial=20000, D=20, seed=0):
    """Empirical probability that two vectors at angle theta get the same bit from a random hyperplane
    (sign of g'x with g standard normal). Equals 1 - theta/pi."""
    rng = np.random.default_rng(seed)
    u = np.zeros(D)
    u[0] = 1.0
    v = np.zeros(D)
    v[0], v[1] = math.cos(theta), math.sin(theta)
    G = rng.standard_normal((ntrial, D))
    return float(np.mean(np.sign(G @ u) == np.sign(G @ v)))


# === asymptotic error of the nearest-neighbour rule ----------------------------------------
def gauss_bayes_error(delta):
    """Bayes error of two equal-prior unit-covariance Gaussians whose means are delta apart: Phi(-delta/2)."""
    return float(stats.norm.cdf(-delta / 2.0))


def gauss_1nn_limit(delta):
    """N -> infinity error of the 1-NN rule for the same two Gaussians: E[2 eta (1 - eta)], with eta the
    posterior probability of class 1 (a function of the coordinate along the mean difference)."""
    def eta(t):
        return 1.0 / (1.0 + np.exp(-(delta * t - delta ** 2 / 2.0)))

    def f(t):
        # t is the coordinate along the mean difference; the marginal density is the equal mixture
        p = 0.5 * stats.norm.pdf(t) + 0.5 * stats.norm.pdf(t - delta)
        e = eta(t)
        return p * 2 * e * (1 - e)
    return float(integrate.quad(f, -12, 12 + delta)[0])


def two_gauss(n, delta, D, rng):
    y = (rng.random(n) < 0.5).astype(int)
    X = rng.standard_normal((n, D))
    X[:, 0] += delta * y
    return X, y


# === open-set recognition (16.1.4) -----------------------------------------------------------
def open_set_scores(Xgal, Xq):
    """Distance from every query to its nearest gallery exemplar (large = more likely novel)."""
    return np.sqrt(sqdist(Xq, Xgal).min(1))


def roc_curve(score_neg, score_pos):
    """ROC points and AUC for 'positive = novel' with larger score meaning novel."""
    s = np.r_[score_neg, score_pos]
    lab = np.r_[np.zeros(len(score_neg)), np.ones(len(score_pos))]
    o = np.argsort(-s, kind="stable")
    tp = np.cumsum(lab[o]) / lab.sum()
    fp = np.cumsum(1 - lab[o]) / (1 - lab).sum()
    fp = np.r_[0, fp]
    tp = np.r_[0, tp]
    return fp, tp, float(np.trapz(tp, fp))


# =========================================================================== Section 16.2: metric learning
def mahalanobis_sq(X, Y, M):
    """Squared Mahalanobis distances (16.3) between the rows of X and the rows of Y."""
    L = np.linalg.cholesky(M + 1e-12 * np.eye(len(M)))
    return sqdist(X @ L, Y @ L)


def target_neighbours(X, y, Kt):
    """For every point the Kt nearest points of its own class in Euclidean distance (LMNN, 16.2.1.1)."""
    D = sqdist(X, X)
    np.fill_diagonal(D, np.inf)
    T = np.zeros((len(X), Kt), int)
    for c in np.unique(y):
        idx = np.where(y == c)[0]
        sub = D[np.ix_(idx, idx)]
        T[idx] = idx[np.argsort(sub, axis=1, kind="stable")[:, :Kt]]
    return T


def lmnn_obj_grad(M, X, y, T, lam=0.5, margin=1.0):
    """LMNN objective L(M) = (1 - lam) L_pull + lam L_push of (16.4)-(16.5) and its gradient in M.
    The gradient of d_M(x_i, x_j)^2 = (x_i - x_j)' M (x_i - x_j) is C_ij = (x_i - x_j)(x_i - x_j)'."""
    N, D = X.shape
    Kt = T.shape[1]
    G = np.zeros((D, D))
    pull = 0.0
    push = 0.0
    q = np.einsum("nd,de,ne->n", X, M, X)
    dil = q[:, None] + q[None, :] - 2 * X @ M @ X.T      # d_M(x_i, x_l)^2 for all pairs
    for k in range(Kt):
        diff = X - X[T[:, k]]
        dij = np.einsum("nd,de,ne->n", diff, M, diff)
        pull += dij.sum()
        G += (1 - lam) * diff.T @ diff
        viol = margin + dij[:, None] - dil
        mask = (y[:, None] != y[None, :]) & (viol > 0)
        push += (viol * mask).sum()
        # gradient of the active hinges: C_ij - C_il
        w_il = mask.astype(float)
        cnt = w_il.sum(1)
        G += lam * ((diff * cnt[:, None]).T @ diff)
        # sum over active l of (x_i - x_l)(x_i - x_l)' = sum_i [cnt_i x_i x_i' - x_i s_i' - s_i x_i' + sum_l x_l x_l']
        S = w_il @ X
        for_i = (X * cnt[:, None]).T @ X - X.T @ S - S.T @ X + (w_il.sum(0)[:, None] * X).T @ X
        G -= lam * for_i
    return (1 - lam) * pull + lam * push, G


def psd_project(M):
    w, V = np.linalg.eigh((M + M.T) / 2)
    return (V * np.maximum(w, 0.0)) @ V.T


def lmnn_fit(X, y, Kt=3, lam=0.5, margin=1.0, iters=200, step=None, M0=None):
    """LMNN by projected gradient descent on the convex objective over the cone of positive
    semi-definite matrices (16.2.1.1). Returns M and the objective trace."""
    N, D = X.shape
    T = target_neighbours(X, y, Kt)
    M = np.eye(D) if M0 is None else M0.copy()
    f0, G = lmnn_obj_grad(M, X, y, T, lam, margin)
    if step is None:
        step = 0.5 / (np.linalg.norm(G) + 1e-12)
    trace = [f0]
    for it in range(iters):
        f, G = lmnn_obj_grad(M, X, y, T, lam, margin)
        s = step
        for _ in range(30):                      # backtracking: take the step only if it descends
            Mn = psd_project(M - s * G)
            fn, _ = lmnn_obj_grad(Mn, X, y, T, lam, margin)
            if fn <= f:
                break
            s *= 0.5
        else:
            Mn, fn = M, f
        M = Mn
        trace.append(fn)
        step = min(2.0 * s, step * 4)
    return M, np.array(trace)


def nca_obj_grad(W, X, y):
    """Neighbourhood components analysis (16.6): p_ij = softmax_j(-||W x_i - W x_j||^2) over j != i,
    J(W) = sum_i sum_{j: y_j = y_i} p_ij, and its gradient
        dJ/dW = 2 W sum_i [ p_i sum_k p_ik x_ik x_ik' - sum_{j in C_i} p_ij x_ij x_ij' ],
    where x_ij = x_i - x_j and p_i = sum_{j in C_i} p_ij."""
    Z = X @ W.T
    D = sqdist(Z, Z)
    np.fill_diagonal(D, np.inf)
    A = -D
    A -= A.max(1, keepdims=True)
    E = np.exp(A)
    np.fill_diagonal(E, 0.0)
    P = E / E.sum(1, keepdims=True)
    same = (y[:, None] == y[None, :])
    np.fill_diagonal(same, False)
    pi = (P * same).sum(1)
    J = pi.sum()
    # sum_i sum_j a_ij x_ij x_ij' = X' diag(rowsum + colsum) X - X' (A + A') X  for weights a_ij
    def wsum(Aw):
        return X.T @ (np.diag(Aw.sum(1) + Aw.sum(0)) - Aw - Aw.T) @ X
    Aw1 = pi[:, None] * P
    Aw2 = P * same
    Gm = 2 * W @ (wsum(Aw1) - wsum(Aw2))
    return J, Gm


def nca_fit(X, y, W0=None, iters=200, step=0.01, L=None, seed=0):
    """Gradient ascent on J(W) with a fixed step (the iteration used in the demonstration), or L-BFGS
    for the polished fit when step is None. Returns W and the objective trace."""
    D = X.shape[1]
    if W0 is None:
        W0 = np.eye(D) if L is None else np.random.default_rng(seed).standard_normal((L, D)) * 0.1
    W = W0.copy()
    if step is None:
        def f(w):
            J, G = nca_obj_grad(w.reshape(W0.shape), X, y)
            return -J, -G.ravel()
        r = optimize.minimize(f, W.ravel(), jac=True, method="L-BFGS-B", options=dict(maxiter=iters))
        return r.x.reshape(W0.shape), np.array([-r.fun])
    tr = []
    for it in range(iters):
        J, G = nca_obj_grad(W, X, y)
        tr.append(J)
        W = W + step * G
    tr.append(nca_obj_grad(W, X, y)[0])
    return W, np.array(tr)


# === latent coincidence analysis (16.2.1.3) --------------------------------------------------
def lca_p1(W, sig2, kap2, X, Xp):
    """Marginal p(y = 1 | x, x') of LCA with the Gaussian coincidence kernel exp(-||z - z'||^2 / (2 kap2)):
    (1 + 2 sig2/kap2)^(-L/2) exp(-||W (x - x')||^2 / (2 (kap2 + 2 sig2)))."""
    L = W.shape[0]
    m = (X - Xp) @ W.T
    return (1.0 + 2.0 * sig2 / kap2) ** (-L / 2.0) * np.exp(-(m ** 2).sum(1) / (2.0 * (kap2 + 2.0 * sig2)))


def lca_loglik(W, sig2, kap2, X, Xp, y):
    p = np.clip(lca_p1(W, sig2, kap2, X, Xp), 1e-300, 1 - 1e-12)
    return float(np.sum(np.where(y == 1, np.log(p), np.log1p(-p))))


def lca_em(X, Xp, y, L, iters=50, kap2=1.0, seed=0, W0=None, sig2=1.0):
    """EM for LCA. With u = z - z' and v = z + z' the latent pair splits into independent Gaussians
    u ~ N(W d, 2 sig2 I), v ~ N(W s, 2 sig2 I) (d = x - x', s = x + x'); y depends on u only.
    E step: the posterior of u is N(m1, s2 I) for y = 1 and the signed mixture
    [N(u; m, 2 sig2 I) - A N(u; m1, s2 I)] / (1 - A) for y = 0, with A = p(y = 1 | x, x').
    M step: the weighted least-squares problem for W and the closed-form sig2 update.
    Returns W, sig2 and the log-likelihood trace (monotone non-decreasing)."""
    N, D = X.shape
    rng = np.random.default_rng(seed)
    W = (rng.standard_normal((L, D)) * 0.3) if W0 is None else W0.copy()
    d = X - Xp
    s = X + Xp
    ll = []
    for it in range(iters):
        ll.append(lca_loglik(W, sig2, kap2, X, Xp, y))
        m = d @ W.T                                   # (N, L): prior mean of u
        A = lca_p1(W, sig2, kap2, X, Xp)
        s2 = 1.0 / (1.0 / (2 * sig2) + 1.0 / kap2)    # posterior variance of u given y = 1
        m1 = m * (s2 / (2 * sig2))                    # posterior mean of u given y = 1
        Eu1 = m1
        Eu0 = (m - A[:, None] * m1) / np.maximum(1 - A, 1e-12)[:, None]
        Eu = np.where((y == 1)[:, None], Eu1, Eu0)
        # E ||u - m||^2 given y
        e1 = L * s2 + ((m1 - m) ** 2).sum(1)
        e_prior = 2 * sig2 * L
        e0 = (e_prior - A * (L * s2 + ((m1 - m) ** 2).sum(1))) / np.maximum(1 - A, 1e-12)
        Euu = np.where(y == 1, e1, e0)
        Ez = 0.5 * ((s @ W.T) + Eu)                   # E[z]  = (E v + E u) / 2, E v = W s
        Ezp = 0.5 * ((s @ W.T) - Eu)
        # weighted least squares: W = (sum E[z] x' + E[z'] x'^T) (sum x x' + x'' x''')^-1
        W_prev = W
        num = Ez.T @ X + Ezp.T @ Xp
        den = X.T @ X + Xp.T @ Xp
        W = np.linalg.solve(den.T, num.T).T
        # sig2 = S / (2 N L) with S = sum_n E||z - W x||^2 + E||z' - W x'||^2 evaluated at the new W; by the
        # parallelogram law S_n = (1/2)(E||u - W d||^2 + E||v - W s||^2), and v keeps its prior N(W_old s, 2 sig2 I)
        W_old = W_prev
        m_new = d @ W.T
        Eu_dev = Euu + 2 * ((Eu - m) * (m - m_new)).sum(1) + ((m - m_new) ** 2).sum(1)
        Ev_dev = 2 * sig2 * L + (((W_old - W) @ s.T) ** 2).sum(0)
        sig2 = float(0.5 * (Eu_dev + Ev_dev).sum() / (2 * N * L))
    ll.append(lca_loglik(W, sig2, kap2, X, Xp, y))
    return W, sig2, np.array(ll)


# === ranking losses (16.2.4) -----------------------------------------------------------------
def l2n(E):
    return E / np.linalg.norm(E, axis=-1, keepdims=True)


def contrastive_loss(d, same, m):
    """(16.10): d^2 for similar pairs, [m - d]_+^2 for dissimilar pairs."""
    return np.where(same, d ** 2, np.maximum(m - d, 0.0) ** 2)


def triplet_loss(dp, dn, m, squared=True):
    """(16.11): [d(a,p)^2 - d(a,n)^2 + m]_+ (arguments are the distances d, squared inside); with
    squared=False the version [d(a,p) - d(a,n) + m]_+ whose zero set and range match (16.16) exactly."""
    return np.maximum(dp ** 2 - dn ** 2 + m, 0.0) if squared else np.maximum(dp - dn + m, 0.0)


def triplet_category(dp, dn, m):
    """Easy, semi-hard or hard negative (Figure 16.6a, (16.16)), from the distances d(a,p), d(a,n)."""
    if dn < dp:
        return "hard"
    if dn < dp + m:
        return "semi-hard"
    return "easy"


def npairs_loss(ea, ep, en, tau=1.0):
    """(16.12)-(16.13) with a temperature: -log exp(s+/tau) / (exp(s+/tau) + sum_k exp(s_k/tau)) for the
    unit-norm embedding of the anchor ea, the positive ep and the rows en of negatives."""
    sp = ea @ ep / tau
    sn = en @ ea / tau
    return float(np.logaddexp(0.0, special.logsumexp(sn) - sp))


def proxy_bound_terms(E, y, Cen):
    """Brute-force sum of the triplet loss l_t of (16.17) over all (i, j, k) with y_i = y_j != y_k, j != i,
    and of its upper bound l_u of (16.20), for embeddings E (rows) and class centroids Cen (rows)."""
    N = len(y)
    Lt = Lu = 0.0
    for i in range(N):
        for j in range(N):
            if j == i or y[j] != y[i]:
                continue
            for k in range(N):
                if y[k] == y[i]:
                    continue
                Lt += np.linalg.norm(E[i] - E[j]) - np.linalg.norm(E[i] - E[k])
                Lu += (np.linalg.norm(E[i] - Cen[y[i]]) - np.linalg.norm(E[i] - Cen[y[k]])
                       + np.linalg.norm(E[j] - Cen[y[i]]) + np.linalg.norm(E[k] - Cen[y[k]]))
    return Lt, Lu


def proxy_bound_closed(E, y, Cen):
    """The O(NC) form (16.22) of the same sum, for a balanced training set (N/C points per class)."""
    N = len(y)
    C = len(Cen)
    n = N // C
    Cp = 3 * (C - 1) * (n - 1) * n
    tot = 0.0
    for i in range(N):
        dall = np.linalg.norm(E[i] - Cen, axis=1)
        tot += dall[y[i]] - (dall.sum() - dall[y[i]]) / (3 * (C - 1))
    return Cp * tot


# =========================================================================== Section 16.3: KDE
def _gauss(x):
    return np.exp(-0.5 * x * x) / math.sqrt(2 * math.pi)


KERNELS = {
    "boxcar": lambda x: 0.5 * (np.abs(x) <= 1),
    "gaussian": _gauss,
    "epanechnikov": lambda x: 0.75 * (1 - x * x) * (np.abs(x) <= 1),
    "tricube": lambda x: (70.0 / 81.0) * (1 - np.abs(x) ** 3) ** 3 * (np.abs(x) <= 1),
}
# second moment (sigma_K^2) and roughness R(K) of every kernel, used by the bias-variance formulas
KERNEL_MOMENTS = {"boxcar": (1 / 3, 1 / 2), "gaussian": (1.0, 1 / (2 * math.sqrt(math.pi))),
                  "epanechnikov": (1 / 5, 3 / 5), "tricube": (35 / 243, 175 / 247)}


def kde(xg, data, h, kernel="gaussian"):
    """Parzen window estimator (16.33): (1/N) sum_n K_h(x - x_n) with K_h(u) = K(u/h)/h."""
    K = KERNELS[kernel]
    return K((np.asarray(xg)[:, None] - np.asarray(data)[None, :]) / h).mean(1) / h


def mad_sigma(x):
    """Robust scale estimate 1.4826 * median |x - median(x)| (Section 16.3.3)."""
    x = np.asarray(x, float)
    return 1.4826 * float(np.median(np.abs(x - np.median(x))))


def silverman_h(x):
    """Bandwidth sigma (4 / (3 N))^(1/5) of Section 16.3.3 with the MAD estimate of sigma."""
    x = np.asarray(x, float)
    return mad_sigma(x) * (4.0 / (3.0 * len(x))) ** 0.2


def gauss_kde_mise(h, N, sigma=1.0):
    """Exact MISE of the Gaussian-kernel KDE when the data are N(0, sigma^2):
    1/(2 sqrt(pi) N h) + (1 - 1/N) / (2 sqrt(pi) sqrt(sigma^2 + h^2)) - 2 / (sqrt(2 pi) sqrt(2 sigma^2 + h^2))
    + 1 / (2 sqrt(pi) sigma)."""
    s = 2 * math.sqrt(math.pi)
    return (1.0 / (s * N * h) + (1 - 1.0 / N) / (s * np.sqrt(sigma ** 2 + h ** 2))
            - 2.0 / (math.sqrt(2 * math.pi) * np.sqrt(2 * sigma ** 2 + h ** 2)) + 1.0 / (s * sigma))


def nw_fit(xg, x, y, h, kernel="gaussian"):
    """Nadaraya-Watson estimator (16.39)-(16.40)."""
    K = KERNELS[kernel]((np.asarray(xg)[:, None] - np.asarray(x)[None, :]) / h)
    W = K / np.maximum(K.sum(1, keepdims=True), 1e-300)
    return W @ y, W


def nw_var(xg, x, y, h, sigma2_y, kernel="gaussian"):
    """Predictive variance (16.45): sigma^2 + sum_n w_n(x) y_n^2 - mu(x)^2, sigma^2 the variance of the
    Gaussian kernel used for y."""
    mu, W = nw_fit(xg, x, y, h, kernel)
    return sigma2_y + W @ (y ** 2) - mu ** 2


def loess_fit(xg, x, y, h, kernel="gaussian", degree=1):
    """Locally weighted polynomial regression (16.47): for every x0 solve the weighted least-squares
    problem with features [1, x - x0, ...] and return the intercept (the fit at x0)."""
    out = np.zeros(len(xg))
    Wt = KERNELS[kernel]((np.asarray(xg)[:, None] - np.asarray(x)[None, :]) / h)
    for i, x0 in enumerate(xg):
        B = np.vander(x - x0, degree + 1, increasing=True)
        w = Wt[i]
        A = B.T @ (B * w[:, None])
        b = B.T @ (w * y)
        out[i] = np.linalg.solve(A + 1e-12 * np.eye(degree + 1), b)[0]
    return out


def regression_truth(x):
    """The regression function of the simulated 1-D data of Figure 16.10 and the notes."""
    return np.exp(-1.5 * x ** 2) * 0.9 + 0.1 * np.sin(2.5 * x)


def regression_data(n, seed=10, noise=0.1, hetero=False, sort=True):
    rng = np.random.default_rng(seed)
    x = rng.uniform(-1.5, 1.5, n)
    x = np.sort(x) if sort else x
    sd = noise * (0.4 + 1.2 * np.abs(x) / 1.5) if hetero else noise * np.ones(n)
    return x, regression_truth(x) + sd * rng.standard_normal(n)


# =========================================================================== figures (book)
def _two_class_scene(seed):
    rng = np.random.default_rng(seed)
    X = np.vstack([rng.normal([0.38, 0.42], 0.13, (16, 2)), rng.normal([0.62, 0.62], 0.13, (16, 2))])
    y = np.r_[np.zeros(16, int), np.ones(16, int)]
    return X, y


def fig_16_1(out=None):
    """Figure 16.1: K-NN with K = 5 at a test point (a) and the Voronoi tessellation of 1-NN (b)."""
    q = np.array([[0.52, 0.5]])
    for seed in range(200):
        X, y = _two_class_scene(seed)
        o = knn_order(X, q)[0, :5]
        if y[o].sum() == 3:                       # three neighbours of class 1 and two of class 0
            break
    fig, axes = plt.subplots(1, 2, figsize=(7.2, 3.5))
    ax = axes[0]
    ax.scatter(*X[y == 0].T, marker="o", s=22, c=RED, label="y = 0")
    ax.scatter(*X[y == 1].T, marker="s", s=22, c=BLUE, label="y = 1")
    r = np.sqrt(sqdist(q, X[o]).max())
    ax.add_patch(plt.Circle(q[0], r, fill=False, ec="k", lw=1.0, ls="--"))
    for i in o:
        ax.plot([q[0, 0], X[i, 0]], [q[0, 1], X[i, 1]], c="k", lw=0.7)
    ax.scatter(*q.T, marker="x", s=70, c="k", zorder=5, linewidths=2)
    ax.set_xlim(0, 1)
    ax.set_ylim(0, 1)
    ax.set_aspect("equal")
    ax.set_title("K = 5: labels %s, p(y=1|x) = 3/5" % sorted(y[o].tolist(), reverse=True))
    ax.legend(loc="lower right", fontsize=8)
    common.panel_label(ax, "a", "upper left")
    # (b) Voronoi cells of 14 points
    from scipy.spatial import Voronoi, voronoi_plot_2d
    rng = np.random.default_rng(4)
    P = rng.random((16, 2))
    lab = (P[:, 0] + 0.5 * P[:, 1] + 0.2 * rng.standard_normal(16) > 0.75).astype(int)
    ax = axes[1]
    g = np.linspace(0, 1, 300)
    GX, GY = np.meshgrid(g, g)
    cell = np.argmin(sqdist(np.c_[GX.ravel(), GY.ravel()], P), axis=1).reshape(GX.shape)
    ax.imshow(lab[cell], origin="lower", extent=(0, 1, 0, 1), cmap=plt.matplotlib.colors.ListedColormap(["#f6c9c9", "#c9d9f6"]), alpha=0.9)
    voronoi_plot_2d(Voronoi(P), ax=ax, show_vertices=False, show_points=False, line_colors="k", line_width=0.8)
    ax.scatter(*P[lab == 0].T, marker="o", s=22, c=RED)
    ax.scatter(*P[lab == 1].T, marker="s", s=22, c=BLUE)
    ax.set_xlim(0, 1)
    ax.set_ylim(0, 1)
    ax.set_aspect("equal")
    ax.set_title("1-NN: Voronoi cells")
    common.panel_label(ax, "b", "upper left")
    fig.tight_layout()
    return savefig(fig, CH, "fig16-1", out)


def _regions(ax, Xtr, ytr, K, xlim=(-22, 26), ylim=(-22, 30), n=170):
    gx = np.linspace(*xlim, n)
    gy = np.linspace(*ylim, n)
    GX, GY = np.meshgrid(gx, gy)
    G = np.c_[GX.ravel(), GY.ravel()]
    pred = knn_predict(Xtr, ytr, G, K, 3).reshape(GX.shape)
    ax.imshow(pred, origin="lower", extent=(*xlim, *ylim), aspect="auto",
              cmap=plt.matplotlib.colors.ListedColormap(["#f6c9c9", "#c9d9f6", "#cdeccd"]), vmin=0, vmax=2, interpolation="nearest")
    for c, mk in zip(range(3), ("o", "s", "^")):
        ax.scatter(*Xtr[ytr == c].T, marker=mk, s=14, c=CLS3[c], edgecolors="none")
    ax.set_xlim(*xlim)
    ax.set_ylim(*ylim)


def fig_16_2(out=None):
    """Figure 16.2: K-NN decision regions for K = 1, 2, 5 and the train and test error against K."""
    Xtr, ytr, Xte, yte = three_class_2d()
    fig, axes = plt.subplots(2, 2, figsize=(7.2, 6.4))
    for ax, K, lab in zip(axes.ravel()[:3], (1, 2, 5), "abc"):
        _regions(ax, Xtr, ytr, K)
        ax.set_title("K = %d" % K)
        common.panel_label(ax, lab, "upper left")
    Ks = list(range(1, 81))
    tr = knn_error_curve(Xtr, ytr, Xtr, ytr, Ks, 3)
    te = knn_error_curve(Xtr, ytr, Xte, yte, Ks, 3)
    ax = axes[1, 1]
    ax.plot(Ks, [tr[k] for k in Ks], c=BLUE, label="train")
    ax.plot(Ks, [te[k] for k in Ks], c=RED, label="test")
    ax.set_xlabel("K")
    ax.set_ylabel("misclassification rate")
    ax.set_ylim(0, 0.6)
    ax.legend()
    common.panel_label(ax, "d", "lower right")
    kb = min(te, key=te.get)
    print("  K=1 train error %.3f, test error %.3f; best K = %d (test error %.3f); K=80 test error %.3f" % (tr[1], te[1], kb, te[kb], te[80]))
    fig.tight_layout()
    return savefig(fig, CH, "fig16-2", out)


def fig_16_3(out=None):
    """Figure 16.3b: edge length of the hypercube that holds a fraction p of uniform data, D = 1, 3, 5, 7, 10."""
    p = np.linspace(0, 1, 401)
    fig, ax = plt.subplots(figsize=(4.4, 3.4))
    for D, c in zip((1, 3, 5, 7, 10), (RED, ORANGE, GREEN, BLUE, PURPLE)):
        ax.plot(p, edge_length(p, D), c=c, label="D = %d" % D)
    ax.plot([0.1, 0.1], [0, 0.794], c=GREY, ls=":", lw=1)
    ax.plot([0.01, 0.01], [0, 0.631], c=GREY, ls=":", lw=1)
    ax.scatter([0.1, 0.01], [0.1 ** 0.1, 0.01 ** 0.1], c="k", s=12, zorder=5)
    ax.annotate("p = 0.1: edge %.2f" % 0.1 ** 0.1, (0.1, 0.1 ** 0.1), (0.3, 0.7), fontsize=8, arrowprops=dict(arrowstyle="-", lw=0.6))
    ax.annotate("p = 0.01: edge %.2f" % 0.01 ** 0.1, (0.01, 0.01 ** 0.1), (0.3, 0.55), fontsize=8, arrowprops=dict(arrowstyle="-", lw=0.6))
    ax.set_xlabel("fraction of data in the neighbourhood, p")
    ax.set_ylabel("edge length of the cube, $p^{1/D}$")
    ax.set_xlim(0, 1)
    ax.set_ylim(0, 1)
    ax.legend(loc="lower right")
    fig.tight_layout()
    return savefig(fig, CH, "fig16-3", out)


def fig_16_6(out=None):
    """Figure 16.6a: easy, semi-hard and hard negatives for an anchor a, a positive p and margin m."""
    m = 0.6
    a = np.zeros(2)
    p = np.array([1.0, 0.0])
    dp = 1.0
    negs = {"n1": (0.62, 120), "n2": (1.35, 70), "n3": (2.1, -50), "n4": (0.85, -110), "n5": (1.55, 200), "n6": (2.4, 150)}
    fig, ax = plt.subplots(figsize=(4.8, 4.4))
    th = np.linspace(0, 2 * np.pi, 200)
    ax.plot(dp * np.cos(th), dp * np.sin(th), c=GREY, lw=0.9, ls="--")
    ax.plot((dp + m) * np.cos(th), (dp + m) * np.sin(th), c=GREY, lw=0.9, ls=":")
    colours = {"hard": RED, "semi-hard": ORANGE, "easy": GREEN}
    seen = set()
    for name, (r, ang) in negs.items():
        pt = r * np.array([math.cos(math.radians(ang)), math.sin(math.radians(ang))])
        cat = triplet_category(dp, r, m)
        ax.scatter(*pt, marker="s", s=34, c=colours[cat], label=None if cat in seen else cat + " negative", zorder=4)
        seen.add(cat)
        ax.annotate(name, pt, (pt[0] + 0.06, pt[1] + 0.06), fontsize=8)
        print("  %s: d(a,n) = %.2f -> %s (hinge loss %.2f)" % (name, r, cat, triplet_loss(dp, r, m, squared=False)))
    ax.scatter(*a, c="k", s=40, zorder=5)
    ax.annotate("a", a, (0.05, 0.07), fontsize=10)
    ax.scatter(*p, c=BLUE, s=40, zorder=5, marker="o")
    ax.annotate("p", p, (1.05, 0.08), fontsize=10)
    ax.text(0, -dp - 0.12, "radius d(a,p)", fontsize=8, color=GREY, ha="center", va="top")
    ax.text(0, -(dp + m) - 0.12, "radius d(a,p)+m", fontsize=8, color=GREY, ha="center", va="top")
    ax.set_aspect("equal")
    ax.set_xlim(-2.7, 2.7)
    ax.set_ylim(-2.7, 2.7)
    ax.legend(loc="upper right", fontsize=8)
    ax.set_title("Anchor a, positive p, margin m = %.1f" % m)
    fig.tight_layout()
    return savefig(fig, CH, "fig16-6", out)


def fig_16_8(out=None):
    """Figure 16.8: the four normalised kernels of Table 16.1."""
    x = np.linspace(-1.5, 1.5, 601)
    fig, ax = plt.subplots(figsize=(4.8, 3.4))
    for (name, K), c in zip(KERNELS.items(), (BLUE, RED, GREEN, MAGENTA)):
        ax.plot(x, K(x), c=c, label=name.capitalize())
        print("  %-12s integral = %.6f" % (name, integrate.quad(K, -1.0 if name != "gaussian" else -12, 1.0 if name != "gaussian" else 12)[0]))
    ax.set_xlabel("x")
    ax.set_ylabel("K(x)")
    ax.set_ylim(0, 0.95)
    ax.legend()
    fig.tight_layout()
    return savefig(fig, CH, "fig16-8", out)


PARZEN_PTS = np.array([-2.1, -1.3, -0.4, 1.9, 5.1, 6.2])


def fig_16_9(out=None):
    """Figure 16.9: a Parzen window estimate from 6 points, uniform (boxcar) and Gaussian kernel, h = 1, 2."""
    x = np.linspace(-5, 10, 1201)
    fig, axes = plt.subplots(2, 2, figsize=(7.0, 5.0))
    for ax, (kern, h), lab in zip(axes.ravel(), (("boxcar", 1.0), ("boxcar", 2.0), ("gaussian", 1.0), ("gaussian", 2.0)), "abcd"):
        K = KERNELS[kern]
        for xn in PARZEN_PTS:
            ax.plot(x, K((x - xn) / h) / h / len(PARZEN_PTS), c=GREY, lw=0.6, ls="--")
        ax.plot(x, kde(x, PARZEN_PTS, h, kern), c=BLUE)
        ax.scatter(PARZEN_PTS, np.zeros(6), marker="x", c=RED, s=25, zorder=5, clip_on=False)
        ax.set_title("%s, h = %.0f" % ("unif" if kern == "boxcar" else "gauss", h))
        ax.set_xlim(-5, 10)
        ax.set_ylim(bottom=0)
        common.panel_label(ax, lab, "upper right")
        print("  %s h=%g: integral %.5f" % (kern, h, np.trapz(kde(x, PARZEN_PTS, h, kern), x)))
    fig.tight_layout()
    return savefig(fig, CH, "fig16-9", out)


def fig_16_10(out=None):
    """Figure 16.10: kernel regression (Nadaraya-Watson) with a Gaussian kernel on a 1-D example."""
    x, y = regression_data(50, seed=10)
    xg = np.linspace(-1.5, 1.5, 400)
    mu, _ = nw_fit(xg, x, y, 0.12)
    fig, ax = plt.subplots(figsize=(4.8, 3.4))
    ax.plot(xg, regression_truth(xg), c=GREEN, label="true")
    ax.scatter(x, y, marker="x", c=BLUE, s=22, label="data")
    ax.plot(xg, mu, c=RED, label="estimate")
    ax.set_xlim(-1.5, 1.5)
    ax.legend()
    fig.tight_layout()
    return savefig(fig, CH, "fig16-10", out)


# =========================================================================== supplementary experiments
def metric_toy(n=80, seed=6, angle_deg=35.0, sep=0.8, sd_in=0.5, sd_out=6.0):
    """A 2-D two-class problem for metric learning: the classes differ only along the direction u (angle
    angle_deg) with a small spread, while the orthogonal direction carries a large irrelevant spread, so that
    Euclidean neighbours are dominated by the nuisance direction."""
    rng = np.random.default_rng(seed)
    y = np.arange(n) % 2
    a = (2 * y - 1) * sep + sd_in * rng.standard_normal(n)
    b = sd_out * rng.standard_normal(n)
    t = math.radians(angle_deg)
    u = np.array([math.cos(t), math.sin(t)])
    v = np.array([-math.sin(t), math.cos(t)])
    X = a[:, None] * u[None, :] + b[:, None] * v[None, :]
    perm = rng.permutation(n)
    return np.round(X[perm], 3), y[perm]


def wine_split(seed=0, frac=0.6):
    from sklearn.datasets import load_wine
    d = load_wine()
    X, y = d.data, d.target
    rng = np.random.default_rng(seed)
    tr = []
    for c in range(3):
        idx = np.where(y == c)[0]
        rng.shuffle(idx)
        tr += idx[:int(round(frac * len(idx)))].tolist()
    tr = np.array(sorted(tr))
    te = np.setdiff1d(np.arange(len(y)), tr)
    mu, sd = X[tr].mean(0), X[tr].std(0)
    return X[tr], y[tr], X[te], y[te], mu, sd


def fig_16_s1(out=None):
    """16.S1: the error of K-NN against N for two Gaussian classes, with the Bayes error and the Cover-Hart bound."""
    from scipy.spatial import cKDTree
    delta, D = 2.0, 2
    Ns = [10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000]
    reps = 30
    rng = np.random.default_rng(1)
    res = {"1-NN": [], "K = 5": [], "K = sqrt(N)": []}
    for N in Ns:
        e = {k: [] for k in res}
        for r in range(reps if N <= 2000 else 8):
            X, y = two_gauss(N, delta, D, rng)
            Xt, yt = two_gauss(3000, delta, D, rng)
            tree = cKDTree(X)
            for name, K in (("1-NN", 1), ("K = 5", min(5, N)), ("K = sqrt(N)", max(1, int(round(math.sqrt(N)))))):
                _, idx = tree.query(Xt, k=K)
                idx = idx.reshape(len(Xt), K)
                votes = y[idx].mean(1)
                pred = (votes > 0.5).astype(int)
                tie = votes == 0.5
                pred[tie] = y[idx[tie, 0]]
                e[name].append(np.mean(pred != yt))
        for k in res:
            res[k].append(np.mean(e[k]))
    Rb = gauss_bayes_error(delta)
    R1 = gauss_1nn_limit(delta)
    fig, ax = plt.subplots(figsize=(5.2, 3.7))
    for (k, v), c in zip(res.items(), (RED, ORANGE, BLUE)):
        ax.plot(Ns, v, "o-", ms=3.5, c=c, label=k)
    ax.axhline(Rb, c="k", lw=1, label="Bayes error %.3f" % Rb)
    ax.axhline(R1, c=RED, lw=0.9, ls="--", label="1-NN limit %.3f" % R1)
    ax.axhline(2 * Rb * (1 - Rb), c=GREY, lw=0.9, ls=":", label="bound $2R^*(1-R^*)$ = %.3f" % (2 * Rb * (1 - Rb)))
    ax.set_xscale("log")
    ax.set_xlabel("training set size N")
    ax.set_ylabel("test error")
    ax.legend(fontsize=8)
    fig.tight_layout()
    print("  Bayes %.4f, 1-NN limit %.4f, bound %.4f; 1-NN at N=10000: %.4f; sqrt(N) at 10000: %.4f" % (Rb, R1, 2 * Rb * (1 - Rb), res["1-NN"][-1], res["K = sqrt(N)"][-1]))
    return savefig(fig, CH, "fig16-s1", out)


CURSE_DIMS = [0, 1, 2, 3, 5, 8, 12, 18, 28]


def curse_pool(seed=21, ntr=400, nte=400, Dmax=30):
    rng = np.random.default_rng(seed)
    Xtr, ytr = disc_cube(ntr, Dmax, rng)
    Xte, yte = disc_cube(nte, Dmax, rng)
    return np.round(Xtr, 3), ytr, np.round(Xte, 3), yte


def curse_errors(Xtr, ytr, Xte, yte, N, K, nuis):
    """Test error of K-NN on the first 2 + nuis coordinates (Euclidean) and on the 2 informative ones only."""
    e_all = knn_error_curve(Xtr[:N, :2 + nuis], ytr[:N], Xte[:, :2 + nuis], yte, [K], 2)[K]
    e_inf = knn_error_curve(Xtr[:N, :2], ytr[:N], Xte[:, :2], yte, [K], 2)[K]
    return e_all, e_inf


def fig_16_s2(out=None):
    """16.S2: KNN with nuisance coordinates (Section 16.1.2), and with a metric that ignores them."""
    Xtr, ytr, Xte, yte = curse_pool()
    fig, axes = plt.subplots(1, 2, figsize=(7.4, 3.3))
    ax = axes[0]
    for N, c in ((100, RED), (400, BLUE)):
        ea = [curse_errors(Xtr, ytr, Xte, yte, N, 5, d)[0] for d in CURSE_DIMS]
        ei = [curse_errors(Xtr, ytr, Xte, yte, N, 5, d)[1] for d in CURSE_DIMS]
        ax.plot([2 + d for d in CURSE_DIMS], ea, "o-", c=c, ms=3.5, label="Euclidean, N = %d" % N)
        ax.axhline(ei[0], c=c, ls="--", lw=1, label="informative coordinates only, N = %d" % N)
    prior = float(np.mean(ytr[:400] == 0))
    ax.axhline(min(prior, 1 - prior), c=GREY, ls=":", lw=1)
    ax.text(30, min(prior, 1 - prior) + 0.01, "majority-class error", fontsize=7, ha="right", color=GREY)
    ax.set_xlabel("dimension D (2 informative + nuisance)")
    ax.set_ylabel("5-NN test error")
    ax.legend(fontsize=6.5, loc="lower right")
    common.panel_label(ax, "a", "upper left")
    ax = axes[1]
    Ds = [2, 3, 5, 8, 12, 20, 30]
    for N, c in ((100, RED), (400, BLUE)):
        d5 = []
        for D in Ds:
            o = knn_order(Xtr[:N, :D], Xte[:200, :D])
            d5.append(np.sqrt(sqdist(Xte[:200, :D], Xtr[:N, :D])[np.arange(200), o[:, 4]]).mean())
        ax.plot(Ds, d5, "o-", c=c, ms=3.5, label="mean distance to the 5th neighbour, N = %d" % N)
    ax.plot(Ds, [math.sqrt(D / 6.0) for D in Ds], c=GREY, ls=":", label="typical distance between two points")
    ax.set_xlabel("dimension D")
    ax.set_ylabel("distance")
    ax.legend(fontsize=7, loc="upper left")
    common.panel_label(ax, "b", "lower right")
    fig.tight_layout()
    return savefig(fig, CH, "fig16-s2", out)


def fig_16_s3(out=None):
    """16.S3: exact k-d tree search cost against the dimension, and random-hyperplane hashing."""
    fig, axes = plt.subplots(1, 2, figsize=(7.4, 3.3))
    ax = axes[0]
    rng = np.random.default_rng(3)
    Ds = [1, 2, 3, 4, 6, 8, 10, 12, 16, 20]
    for N, c in ((1000, RED), (8000, BLUE)):
        frac = []
        for D in Ds:
            X = rng.random((N, D))
            tree = KDTree1(X)
            cnt = [tree.search(q)[1] for q in rng.random((60, D))]
            frac.append(np.mean(cnt) / N)
        ax.plot(Ds, frac, "o-", c=c, ms=3.5, label="N = %d" % N)
    ax.axhline(1.0, c=GREY, ls=":", lw=1)
    ax.set_yscale("log")
    ax.set_xlabel("dimension D")
    ax.set_ylabel("distance evaluations / N")
    ax.legend(fontsize=8, loc="lower right")
    ax.set_title("exact k-d tree search, uniform data", fontsize=9.5)
    common.panel_label(ax, "a", "upper left")
    ax = axes[1]
    th = np.linspace(0.05, math.pi - 0.05, 14)
    ax.plot(np.degrees(th), 1 - th / math.pi, c=BLUE, label="$1-\\theta/\\pi$")
    ax.scatter(np.degrees(th), [lsh_collision(t, 20000, 20, i) for i, t in enumerate(th)], c=RED, s=14, zorder=4, label="simulation (20 000 hyperplanes)")
    ax.set_xlabel("angle between the two vectors (degrees)")
    ax.set_ylabel("probability of the same hash bit")
    ax.legend(fontsize=8)
    ax.set_title("random hyperplane hashing", fontsize=9.5)
    common.panel_label(ax, "b", "lower left")
    fig.tight_layout()
    return savefig(fig, CH, "fig16-s3", out)


NCA_STEP = 0.002
NCA_ITERS = 1000
NCA_TRACE_AT = (0, 1, 2, 5, 10, 20, 50, 100, 200, 500, 1000)


def nca_demo_run(X, y, step=NCA_STEP, iters=NCA_ITERS):
    return nca_fit(X, y, W0=np.eye(X.shape[1]), iters=iters, step=step)


def fig_16_s4(out=None):
    """16.S4: metric learning on the toy problem and on the wine data."""
    X, y = metric_toy()
    Ks = [1, 3, 5]
    err0 = knn_error_curve(X, y, X, y, Ks, 2, loo=True)
    Wn, trn = nca_demo_run(X, y)
    errn = knn_error_curve(X, y, X, y, Ks, 2, W=Wn, loo=True)
    M, trl = lmnn_fit(X, y, Kt=3, lam=0.5, margin=1.0, iters=150)
    Wl = np.linalg.cholesky(M + 1e-9 * np.eye(2)).T
    errl = knn_error_curve(X, y, X, y, Ks, 2, W=Wl, loo=True)
    print("  toy LOO 3-NN error: Euclid %.3f, NCA %.3f, LMNN %.3f" % (err0[3], errn[3], errl[3]))
    fig, axes = plt.subplots(2, 3, figsize=(8.0, 5.2))
    for ax, (Z, ttl, e) in zip(axes[0], ((X, "Euclidean", err0), (X @ Wn.T, "NCA space", errn), (X @ Wl.T, "LMNN space", errl))):
        for c, mk in ((0, "o"), (1, "s")):
            ax.scatter(*Z[y == c].T, marker=mk, s=14, c=CLS3[c], edgecolors="none")
        ax.set_title("%s: LOO 3-NN error %.2f" % (ttl, e[3]), fontsize=9)
        ax.set_aspect("equal", adjustable="datalim")
    ax = axes[1, 0]
    ax.plot(trn, c=BLUE)
    ax.set_xlabel("iteration")
    ax.set_ylabel("NCA objective J(W)")
    ax = axes[1, 1]
    ax.plot(trl, c=RED)
    ax.set_xlabel("iteration")
    ax.set_ylabel("LMNN objective L(M)")
    # wine
    Xtr, ytr, Xte, yte, mu, sd = wine_split()
    Ztr, Zte = (Xtr - mu) / sd, (Xte - mu) / sd
    accs = {}
    accs["raw"] = 1 - knn_error_curve(Xtr, ytr, Xte, yte, [5], 3)[5]
    accs["standardised"] = 1 - knn_error_curve(Ztr, ytr, Zte, yte, [5], 3)[5]
    Wn2, _ = nca_fit(Ztr, ytr, W0=np.random.default_rng(0).standard_normal((3, 13)) * 0.1, iters=150, step=None)
    accs["NCA (L = 3)"] = 1 - knn_error_curve(Ztr, ytr, Zte, yte, [5], 3, W=Wn2)[5]
    Ml, _ = lmnn_fit(Ztr, ytr, Kt=3, lam=0.5, margin=1.0, iters=60)
    Wl2 = np.linalg.cholesky(Ml + 1e-9 * np.eye(13)).T
    accs["LMNN"] = 1 - knn_error_curve(Ztr, ytr, Zte, yte, [5], 3, W=Wl2)[5]
    ax = axes[1, 2]
    ax.bar(range(len(accs)), list(accs.values()), color=[GREY, BLUE, RED, GREEN])
    ax.set_xticks(range(len(accs)))
    ax.set_xticklabels(list(accs), rotation=25, ha="right", fontsize=8)
    ax.set_ylim(0.5, 1.0)
    ax.set_ylabel("wine, 5-NN test accuracy")
    print("  wine 5-NN test accuracy: " + ", ".join("%s %.3f" % kv for kv in accs.items()))
    fig.tight_layout()
    return savefig(fig, CH, "fig16-s4", out)


def lca_pairs(X, y, n_pairs=800, seed=0):
    rng = np.random.default_rng(seed)
    i = rng.integers(0, len(X), n_pairs)
    j = rng.integers(0, len(X), n_pairs)
    keep = i != j
    i, j = i[keep], j[keep]
    return X[i], X[j], (y[i] == y[j]).astype(int)


def fig_16_s5(out=None):
    """16.S5: latent coincidence analysis fitted by EM on pairs from the toy problem."""
    X, y = metric_toy()
    Xa, Xb, yp = lca_pairs(X, y)
    W, s2, ll = lca_em(Xa, Xb, yp, L=1, iters=2000, seed=1)
    # direct maximisation of the same marginal likelihood
    def negll(w):
        return -lca_loglik(w[:2].reshape(1, 2), math.exp(w[2]), 1.0, Xa, Xb, yp)
    r = optimize.minimize(negll, np.r_[W.ravel(), 0.0], method="Nelder-Mead", options=dict(xatol=1e-7, fatol=1e-10, maxiter=4000))
    t = math.radians(35.0)
    cosang = abs(W[0] @ np.array([math.cos(t), math.sin(t)])) / np.linalg.norm(W)
    print("  LCA: loglik EM %.4f (sig2 = %.2e), direct %.4f, min increment %.2e; |cos(angle to informative direction)| = %.4f" % (ll[-1], s2, -r.fun, np.diff(ll).min(), cosang))
    fig, axes = plt.subplots(1, 2, figsize=(7.2, 3.2))
    ax = axes[0]
    ax.plot(np.arange(len(ll)) + 1, ll, c=BLUE)
    ax.axhline(-r.fun, c=GREY, ls=":", lw=1)
    ax.set_xscale("log")
    ax.set_xlabel("EM iteration")
    ax.set_ylabel("log marginal likelihood")
    common.panel_label(ax, "a", "lower right")
    ax = axes[1]
    p = np.clip(lca_p1(W, s2, 1.0, Xa, Xb), 0, 1)
    proj = np.abs((Xa - Xb) @ W.T).ravel()
    ax.scatter(proj[yp == 0], p[yp == 0], s=5, c=RED, alpha=0.5, label="different class")
    ax.scatter(proj[yp == 1], p[yp == 1], s=5, c=BLUE, alpha=0.5, label="same class")
    ax.set_xlabel("$|W(x - x')|$")
    ax.set_ylabel("$p(y=1\\mid x, x')$")
    ax.legend(fontsize=8, markerscale=2)
    common.panel_label(ax, "b", "upper right")
    fig.tight_layout()
    return savefig(fig, CH, "fig16-s5", out)


def digits_split(seed=0, noise=0.0):
    """The 8 x 8 digits scaled to [0, 1] and shuffled; noise > 0 adds N(0, noise^2) to every pixel."""
    from sklearn.datasets import load_digits
    d = load_digits()
    X, y = d.data / 16.0, d.target
    rng = np.random.default_rng(seed)
    perm = rng.permutation(len(y))
    X, y = X[perm], y[perm]
    if noise:
        X = X + noise * np.random.default_rng(seed + 100).standard_normal(X.shape)
    return X, y


def fig_16_s6(out=None):
    """16.S6: open-set recognition on the digits by thresholding the nearest-exemplar distance."""
    X, y = digits_split()
    known = np.arange(7)
    fig, axes = plt.subplots(1, 2, figsize=(7.4, 3.3))
    rows = []
    for g, c in ((1, RED), (5, ORANGE), (20, BLUE)):
        idx_g = np.concatenate([np.where(y == k)[0][:g] for k in known])
        rest = np.setdiff1d(np.arange(len(y)), idx_g)
        q_known = rest[np.isin(y[rest], known)]
        q_new = rest[~np.isin(y[rest], known)]
        sk = open_set_scores(X[idx_g], X[q_known])
        sn = open_set_scores(X[idx_g], X[q_new])
        fp, tp, auc = roc_curve(sk, sn)
        axes[1].plot(fp, tp, c=c, label="%d per class (AUC %.3f)" % (g, auc))
        pred = knn_predict(X[idx_g], y[idx_g], X[q_known], 1, 10)
        rows.append((g, auc, float(np.mean(pred == y[q_known]))))
        if g == 5:
            axes[0].hist(sk, bins=30, alpha=0.6, color=BLUE, density=True, label="known classes 0-6")
            axes[0].hist(sn, bins=30, alpha=0.6, color=RED, density=True, label="novel classes 7-9")
    axes[0].set_xlabel("distance to the nearest exemplar (5 per class)")
    axes[0].set_ylabel("density")
    axes[0].legend(fontsize=8)
    common.panel_label(axes[0], "a", "upper right")
    axes[1].plot([0, 1], [0, 1], c=GREY, ls=":", lw=1)
    axes[1].set_xlabel("false alarm rate (known flagged as novel)")
    axes[1].set_ylabel("detection rate (novel flagged)")
    axes[1].legend(fontsize=8, loc="lower right")
    common.panel_label(axes[1], "b", "upper left")
    for g, auc, acc in rows:
        print("  gallery %2d per class: novelty AUC %.3f, closed-set 1-NN accuracy on known classes %.3f" % (g, auc, acc))
    fig.tight_layout()
    return savefig(fig, CH, "fig16-s6", out)


# === deep metric learning on the digits -------------------------------------------------------
def dml_experiment(seed=0, L=16, epochs=60, verbose=True, noise=0.3):
    """Train a 64-128-L network on digits 0-6 with a classification loss, the contrastive loss (16.10),
    the triplet loss (16.11) with semi-hard negatives, or the N-pairs loss (16.12) with a temperature, and
    measure leave-one-out 1-NN retrieval accuracy in the embedding for held-out images of the seen classes and
    for the unseen classes 7-9. Returns a dict of accuracies."""
    torch = common.torch_setup(seed)
    import torch.nn as nn
    import torch.nn.functional as F
    X, y = digits_split(0, noise)
    seen = y < 7
    Xs, ys = X[seen], y[seen]
    n_tr = int(0.7 * len(ys))
    Xtr, ytr, Xho, yho = Xs[:n_tr], ys[:n_tr], Xs[n_tr:], ys[n_tr:]
    Xun, yun = X[~seen], y[~seen]
    Xtr_t, ytr_t = torch.tensor(Xtr, dtype=torch.float32), torch.tensor(ytr)

    def make():
        return nn.Sequential(nn.Linear(64, 128), nn.ReLU(), nn.Linear(128, L))

    def pair_loss(E, yb, kind):
        En = F.normalize(E, dim=1)
        D = torch.cdist(En, En)
        same = (yb[:, None] == yb[None, :])
        eye = torch.eye(len(yb), dtype=torch.bool)
        if kind == "contrastive":
            m = 1.0
            pos = same & ~eye
            neg = ~same
            return ((D[pos] ** 2).sum() + (F.relu(m - D[neg]) ** 2).sum()) / (pos.sum() + neg.sum())
        if kind == "triplet":
            m = 0.3
            tot, cnt = 0.0, 0
            S = D
            # all valid triplets, semi-hard negatives only
            ap = S[:, :, None]
            an = S[:, None, :]
            valid = (same & ~eye)[:, :, None] & (~same)[:, None, :]
            semi = valid & (an > ap) & (an < ap + m)
            hard = valid & (an <= ap)
            use = semi | hard
            if use.sum() == 0:
                return D.sum() * 0
            loss = F.relu(ap ** 2 - an ** 2 + m)
            return (loss * use).sum() / use.sum()
        if kind == "npairs":
            # every (anchor, positive) pair of the batch is one term of (16.12): log(1 + sum over the negatives of
            # exp((s_neg - s_pos)/tau)); the negatives are the batch items of other classes
            tau = 0.2
            sim = En @ En.T / tau
            pos = same & ~eye
            neg_lse = torch.logsumexp(sim.masked_fill(same, -1e9), dim=1, keepdim=True)
            return F.softplus(neg_lse - sim)[pos].mean()
        raise ValueError(kind)

    results = {}
    rng = np.random.default_rng(seed)
    for kind in ("classification", "contrastive", "triplet", "npairs"):
        torch.manual_seed(seed)
        net = make()
        head = nn.Linear(L, 7)
        params = list(net.parameters()) + (list(head.parameters()) if kind == "classification" else [])
        opt = torch.optim.Adam(params, lr=2e-3)
        for ep in range(epochs):
            perm = torch.tensor(rng.permutation(n_tr))
            for b in range(0, n_tr, 128):
                idx = perm[b:b + 128]
                E = net(Xtr_t[idx])
                if kind == "classification":
                    loss = F.cross_entropy(head(F.relu(E)), ytr_t[idx])
                else:
                    loss = pair_loss(E, ytr_t[idx], kind)
                opt.zero_grad()
                loss.backward()
                opt.step()
        with torch.no_grad():
            Eh = F.normalize(net(torch.tensor(Xho, dtype=torch.float32)), dim=1).numpy()
            Eu = F.normalize(net(torch.tensor(Xun, dtype=torch.float32)), dim=1).numpy()
        results[kind] = (loo_nn_accuracy(Eh, yho), loo_nn_accuracy(Eu, yun))
        if verbose:
            print("  %-15s held-out seen classes %.3f, unseen classes %.3f" % (kind, *results[kind]))
    # baselines: raw pixels and PCA-L (the same noise)
    mu = Xtr.mean(0)
    U, s, Vt = np.linalg.svd(Xtr - mu, full_matrices=False)
    P = Vt[:L].T
    results["pixels"] = (loo_nn_accuracy(Xho, yho), loo_nn_accuracy(Xun, yun))
    results["PCA"] = (loo_nn_accuracy((Xho - mu) @ P, yho), loo_nn_accuracy((Xun - mu) @ P, yun))
    if verbose:
        for k in ("pixels", "PCA"):
            print("  %-15s held-out seen classes %.3f, unseen classes %.3f" % (k, *results[k]))
    return results


def loo_nn_accuracy(E, y):
    """Leave-one-out 1-NN accuracy (retrieval of a same-class neighbour) for embeddings E."""
    D = sqdist(E, E)
    np.fill_diagonal(D, np.inf)
    return float(np.mean(y[D.argmin(1)] == y))


def fig_16_s7(out=None):
    """16.S7: deep metric learning on the digits: classification, contrastive, triplet and N-pairs losses."""
    cache = os.path.join(CACHE_DIR, "ch16_dml.json")
    if os.path.exists(cache):
        res = json.load(open(cache))
    else:
        accs = [dml_experiment(seed=s, L=16, noise=0.3) for s in range(3)]
        res = {k: [float(np.mean([a[k][i] for a in accs])) for i in range(2)] for k in accs[0]}
        os.makedirs(CACHE_DIR, exist_ok=True)
        json.dump(res, open(cache, "w"))
    names = ["pixels", "PCA", "classification", "contrastive", "triplet", "npairs"]
    labels = ["pixels (64-D)", "PCA (16-D)", "classification", "contrastive", "triplet", "N-pairs"]
    fig, ax = plt.subplots(figsize=(6.4, 3.3))
    w = 0.38
    xs = np.arange(len(names))
    ax.bar(xs - w / 2, [res[k][0] for k in names], w, color=BLUE, label="held-out images of seen classes 0-6")
    ax.bar(xs + w / 2, [res[k][1] for k in names], w, color=ORANGE, label="unseen classes 7-9")
    ax.set_xticks(xs)
    ax.set_xticklabels(labels, rotation=20, ha="right", fontsize=8.5)
    ax.set_ylim(0.4, 1.12)
    ax.set_ylabel("leave-one-out 1-NN accuracy")
    ax.legend(fontsize=8, loc="upper center", ncol=2)
    fig.tight_layout()
    return savefig(fig, CH, "fig16-s7", out)


def fig_16_s8(out=None):
    """16.S8: Nadaraya-Watson against local linear regression at the boundary, and the predictive spread (16.45)."""
    fig, axes = plt.subplots(1, 2, figsize=(7.4, 3.3))
    rng = np.random.default_rng(8)
    f = lambda x: 1.5 * x
    xg = np.linspace(0, 1, 101)
    h, N, reps = 0.15, 100, 300
    nw_all, ll_all = [], []
    for _ in range(reps):
        x = rng.random(N)
        y = f(x) + 0.2 * rng.standard_normal(N)
        nw_all.append(nw_fit(xg, x, y, h)[0])
        ll_all.append(loess_fit(xg, x, y, h))
    ax = axes[0]
    ax.plot(xg, f(xg), c="k", lw=1.2, label="truth $1.5x$")
    ax.plot(xg, np.mean(nw_all, 0), c=RED, label="Nadaraya-Watson (mean of 300 fits)")
    ax.plot(xg, np.mean(ll_all, 0), c=BLUE, label="local linear (mean of 300 fits)")
    ax.set_xlabel("x")
    ax.legend(fontsize=7.5, loc="upper left")
    common.panel_label(ax, "a", "lower right")
    print("  boundary bias at x = 0: NW %.4f, local linear %.4f; at x = 1: NW %.4f, local linear %.4f" % (
        np.mean(nw_all, 0)[0], np.mean(ll_all, 0)[0] - 0, np.mean(nw_all, 0)[-1] - 1.5, np.mean(ll_all, 0)[-1] - 1.5))
    ax = axes[1]
    x, y = regression_data(120, seed=11, noise=0.12, hetero=True)
    xg2 = np.linspace(-1.5, 1.5, 300)
    mu, _ = nw_fit(xg2, x, y, 0.15)
    sd = np.sqrt(np.maximum(nw_var(xg2, x, y, 0.15, 0.0), 0))
    ax.fill_between(xg2, mu - 2 * sd, mu + 2 * sd, color=BLUE, alpha=0.18, label="mean $\\pm 2$ sd of (16.45)")
    ax.plot(xg2, regression_truth(xg2), c=GREEN, label="true mean")
    ax.plot(xg2, mu, c=RED, label="Nadaraya-Watson")
    ax.scatter(x, y, s=8, c=GREY, marker="x")
    ax.set_xlabel("x")
    ax.legend(fontsize=7.5, loc="upper right")
    common.panel_label(ax, "b", "lower left")
    fig.tight_layout()
    return savefig(fig, CH, "fig16-s8", out)


def fig_16_s9(out=None):
    """16.S9: the exact MISE of a Gaussian KDE against the bandwidth, with the rule of Section 16.3.3."""
    hs = np.logspace(-1.6, 0.4, 200)
    fig, ax = plt.subplots(figsize=(5.0, 3.5))
    rng = np.random.default_rng(9)
    for N, c in ((50, RED), (500, BLUE)):
        m = gauss_kde_mise(hs, N)
        ax.plot(hs, m, c=c, label="N = %d, exact MISE" % N)
        hb = hs[np.argmin(m)]
        hr = (4.0 / (3.0 * N)) ** 0.2
        ax.axvline(hr, c=c, ls=":", lw=1)
        ax.scatter([hr], [gauss_kde_mise(hr, N)], c=c, s=25, zorder=5)
        # simulation at a few bandwidths
        hh = np.array([0.15, 0.3, 0.6]) if N == 50 else np.array([0.08, 0.2, 0.5])
        xg = np.linspace(-6, 6, 1201)
        sim = []
        for h in hh:
            v = []
            for _ in range(60):
                d = rng.standard_normal(N)
                v.append(np.trapz((kde(xg, d, h) - stats.norm.pdf(xg)) ** 2, xg))
            sim.append(np.mean(v))
        ax.scatter(hh, sim, marker="x", c=c, s=30, zorder=5)
        print("  N=%d: exact MISE minimiser h = %.4f, rule h = %.4f" % (N, hb, hr))
    ax.set_xscale("log")
    ax.set_yscale("log")
    ax.set_xlabel("bandwidth h")
    ax.set_ylabel("MISE")
    ax.legend(fontsize=8)
    ax.set_title("dots: rule $h=\\sigma(4/3N)^{1/5}$; crosses: simulation", fontsize=8.5)
    fig.tight_layout()
    return savefig(fig, CH, "fig16-s9", out)


FIGURES = {"16.1": fig_16_1, "16.2": fig_16_2, "16.3": fig_16_3, "16.6": fig_16_6, "16.8": fig_16_8, "16.9": fig_16_9,
           "16.10": fig_16_10, "16.S1": fig_16_s1, "16.S2": fig_16_s2, "16.S3": fig_16_s3, "16.S4": fig_16_s4,
           "16.S5": fig_16_s5, "16.S6": fig_16_s6, "16.S7": fig_16_s7, "16.S8": fig_16_s8, "16.S9": fig_16_s9}


def metric_xor(n=80, seed=3):
    """Four Gaussian blobs at (+-2, +-2) with the class given by the XOR of the signs: no linear metric helps."""
    rng = np.random.default_rng(seed)
    q = np.arange(n) % 4
    cx = np.array([2, -2, -2, 2])[q]
    cy = np.array([2, 2, -2, -2])[q]
    X = np.c_[cx, cy] + 0.9 * rng.standard_normal((n, 2))
    y = np.array([0, 1, 0, 1])[q]
    perm = rng.permutation(n)
    return np.round(X[perm], 3), y[perm]


def kernel_pool(seed=31, n=300):
    """Bimodal sample for the density-estimation panel of the kernel demonstration."""
    rng = np.random.default_rng(seed)
    comp = rng.random(n) < 0.4
    x = np.where(comp, rng.normal(-1.0, 0.4, n), rng.normal(1.2, 0.7, n))
    return np.round(x, 3)


def export_json():
    os.makedirs(DATA_OUT, exist_ok=True)

    def dump(name, d):
        with open(os.path.join(DATA_OUT, name), "w") as f:
            json.dump(d, f, separators=(",", ":"))
    # ---- 1. K-NN decision regions (demo knn-voronoi)
    Xtr, ytr, Xte, yte = three_class_2d()
    Xtr, Xte = np.round(Xtr, 3), np.round(Xte[:600], 3)
    yte = yte[:600]
    Ks = list(range(1, 81))
    ref = {}
    for s in (1.0, 0.5, 2.0):
        W = np.diag([1.0, s])
        tr = knn_error_curve(Xtr, ytr, Xtr, ytr, Ks, 3, W=W)
        te = knn_error_curve(Xtr, ytr, Xte, yte, Ks, 3, W=W)
        ref["s%g" % s] = dict(train=_r([tr[k] for k in Ks], 6), test=_r([te[k] for k in Ks], 6))
    q = np.array([[0.0, 0.0], [10.0, 5.0], [-8.0, 12.0]])
    ref["query"] = dict(points=q.tolist(), proba={str(K): knn_proba(Xtr, ytr, q, K, 3).tolist() for K in (1, 5, 15)})
    dump("ch16-knn.json", dict(Xtr=Xtr.tolist(), ytr=ytr.tolist(), Xte=Xte.tolist(), yte=yte.tolist(), ref=ref))
    # ---- 2. curse of dimensionality (demo knn-curse)
    Xtr2, ytr2, Xte2, yte2 = curse_pool()
    ref = []
    for N in (100, 400):
        for K in (1, 5, 15):
            for nu in CURSE_DIMS:
                ea, ei = curse_errors(Xtr2, ytr2, Xte2, yte2, N, K, nu)
                ref.append(dict(N=N, K=K, nuis=nu, err_all=round(ea, 6), err_inf=round(ei, 6)))
    dump("ch16-curse.json", dict(Xtr=Xtr2.tolist(), ytr=ytr2.tolist(), Xte=Xte2.tolist(), yte=yte2.tolist(), dims=CURSE_DIMS, ref=ref))
    # ---- 3. NCA (demo metric-learning)
    sets = {}
    for name, (X, y) in (("rotated", metric_toy()), ("xor", metric_xor())):
        W, tr = nca_fit(X, y, W0=np.eye(2), iters=NCA_ITERS, step=NCA_STEP)
        e0 = knn_error_curve(X, y, X, y, [1, 3, 5], 2, loo=True)
        e1 = knn_error_curve(X, y, X, y, [1, 3, 5], 2, W=W, loo=True)
        sets[name] = dict(X=X.tolist(), y=y.tolist(), ref=dict(J=_r([tr[i] for i in NCA_TRACE_AT], 6), W=_r(W, 6),
                          loo_before={str(k): v for k, v in e0.items()}, loo_after={str(k): v for k, v in e1.items()}))
    dump("ch16-nca.json", dict(step=NCA_STEP, iters=NCA_ITERS, trace_at=list(NCA_TRACE_AT), sets=sets))
    # ---- 4. kernel density and regression (demo kernel-smoothing)
    xs = kernel_pool()
    xr, yr = regression_data(200, seed=12, noise=0.1, hetero=True, sort=False)
    xr, yr = np.round(xr, 4), np.round(yr, 4)
    xg = np.array([-1.0, -0.2, 0.5, 1.2])
    ref = dict(kde_parzen={}, kde_pool={}, nw={}, ll={}, var={}, sil={})
    for kern in KERNELS:
        for h in (1.0, 2.0):
            ref["kde_parzen"]["%s_%g" % (kern, h)] = _r(kde(np.array([-1.0, 0.0, 2.0, 5.0]), PARZEN_PTS, h, kern), 6)
        for h in (0.1, 0.3, 0.6):
            ref["kde_pool"]["%s_%g" % (kern, h)] = _r(kde(xg, xs, h, kern), 6)
    for n in (30, 100, 300):
        ref["sil"][str(n)] = [round(silverman_h(xs[:n]), 6), round(mad_sigma(xs[:n]), 6)]
    xgr = np.array([-1.4, -0.7, 0.0, 0.7, 1.4])
    for n in (60, 200):
        for h in (0.08, 0.2):
            for kern in ("gaussian", "epanechnikov"):
                key = "%d_%g_%s" % (n, h, kern)
                ref["nw"][key] = _r(nw_fit(xgr, xr[:n], yr[:n], h, kern)[0], 6)
                ref["ll"][key] = _r(loess_fit(xgr, xr[:n], yr[:n], h, kern), 6)
                ref["var"][key] = _r(nw_var(xgr, xr[:n], yr[:n], h, 0.0, kern), 6)
    dump("ch16-kernel.json", dict(parzen=PARZEN_PTS.tolist(), pool=xs.tolist(), xr=xr.tolist(), yr=yr.tolist(), xgr=xgr.tolist(), xg=xg.tolist(), ref=ref))
    print("wrote ch16-*.json")


if __name__ == "__main__":
    if "--json" in sys.argv:
        export_json()
    else:
        common.run(FIGURES, CH)
        if "--fig" not in sys.argv and "--list" not in sys.argv:
            export_json()
