"""Murphy (2022), Chapter 17: Kernel Methods.

Companion code for Chapter 17 of K. P. Murphy, Probabilistic Machine Learning: An Introduction
(MIT Press, 2022; April 2025 draft), pp. 567-602, written from scratch with numpy, scipy and
matplotlib, to be read next to the lecture notes (../ch17-kernel-methods.html). scikit-learn is
only used to load the iris data; the methods themselves are implemented here and compared with
the library versions in a separate test script.

Methods
* Section 17.1, Mercer kernels: squared exponential and ARD (17.3), (17.7)-(17.9), Matern for any
  nu (17.10) and its closed forms (17.11)-(17.13), periodic (17.14), cosine (17.15), linear
  (17.56) and polynomial kernels, sums and products (17.25)-(17.26) (kernel_*), sampling a
  Gaussian process prior (gp_sample).
* Section 17.2, Gaussian processes: the posterior by Cholesky factorisation (17.28)-(17.38) and
  (17.47)-(17.49) (gp_posterior), the log marginal likelihood and its gradient for the SE kernel
  (17.52)-(17.54) (se_logml), maximisation with restarts (fit_se_hyper), GP classification by
  Markov chain Monte Carlo over the latent function and the kernel parameters (gpc_mcmc:
  elliptical slice sampling of the whitened latent vector and random-walk Metropolis for the
  kernel parameters, a substitute for the Hamiltonian Monte Carlo used in the book), random
  Fourier features (17.58)-(17.60), orthogonal random features and positive random features
  (17.61) (random_features), with a copy of the browser's seeded generator (mulberry32) so that
  the demonstration draws the same features.
* Section 17.3, support vector machines: a sequential minimal optimisation (SMO) solver for the
  generic dual  min 1/2 a'Qa + p'a  s.t. z'a = 0, 0 <= a <= C  with second-order working-set
  selection (smo), used for the soft-margin classifier (17.83)-(17.88) (svc_fit) and for
  epsilon-insensitive regression (17.110)-(17.117) (svr_fit); Platt scaling (17.95) (platt);
  kernel ridge regression (17.101)-(17.108) (krr_fit); k-fold cross-validation (cv_error).
* Section 17.4, sparse vector machines: l2- and l1-penalised logistic regression on the kernel
  features (17.118) (logreg_l2, logreg_l1 by Newton and by FISTA), ridge and lasso regression on
  the same features (lasso_cd by coordinate descent), and the relevance vector machine for
  regression and classification by evidence maximisation (rvm_regression, rvm_classification).

Data. The iris measurements come from scikit-learn (Fisher, 1936). The mixture data of Figure
17.18 are the simulated mixture of Hastie, Tibshirani and Friedman (2009, Section 2.3), read
from the companion course's data file ../../esl/data/ch02-mixture.json. Everything else is
simulated with fixed seeds: the book's own point sets (the 7 and 20 points of Figures 17.8-17.9,
the fictitious "space flu" data of Figure 17.11, the toy data of Figures 17.14, 17.17, 17.20 and
17.21) are not available offline, so those figures are close stand-ins, as their captions say.

Figures. Reproduced here: 17.1, 17.2, 17.3, 17.4, 17.5, 17.7, 17.8, 17.9, 17.10, 17.11, 17.14,
17.15, 17.17, 17.18, 17.19, 17.20, 17.21, 17.22, 17.23. Skipped, with the reason:
  17.6   a graphical-model diagram of a Gaussian process (nothing is computed);
  17.12  a hand-drawn sketch of a large and a small margin;
  17.13  hand-drawn geometry of a linear decision boundary and of slack variables (the same
         quantities are computed and drawn on real fits in Figures 17.17 and 17.19b);
  17.16  hand-drawn sketches of one-versus-rest and one-versus-one ambiguity regions.
Figure 17.4 and 17.5 (kernel products and sums) are redrawn with my own kernels and samples.
Supplementary figures for the gaps filled in the notes:
  17.S1 random Fourier features: the kernel estimate with its exact standard deviation, and the
        Gram-matrix error against the number of features for i.i.d., orthogonal and positive
        features;
  17.S2 Matern kernels and their spectral densities as nu grows, against the SE kernel.
Run `python3 ch17_kernel_methods.py --list`, `python3 ch17_kernel_methods.py` (all figures,
a few minutes) or `python3 ch17_kernel_methods.py --fig 17.9`. Files go to ../img/ch17/; the
data used by the browser demonstrations go to ../data/ch17-*.json.
"""
import json
import math
import os
import sys
import time

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

import numpy as np
from scipy import linalg, optimize, special

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

CH = 17
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")
sigmoid = common.sigmoid


# =========================================================================== kernels (17.1)
def sqdist(A, B, ell=1.0):
    """Matrix of squared distances ||a_i/ell - b_j/ell||^2 (ell may be a vector: ARD scaling)."""
    A = np.atleast_2d(np.asarray(A, float)) / ell
    B = np.atleast_2d(np.asarray(B, float)) / ell
    d = (A ** 2).sum(1)[:, None] + (B ** 2).sum(1)[None, :] - 2 * A @ B.T
    return np.maximum(d, 0.0)


def as_col(x):
    x = np.asarray(x, float)
    return x[:, None] if x.ndim == 1 else x


def kernel_se(A, B, ell=1.0, sf2=1.0):
    """Squared exponential (RBF) kernel (17.3); a vector ell gives the ARD kernel (17.8)."""
    return sf2 * np.exp(-0.5 * sqdist(as_col(A), as_col(B), ell))


def matern_closed(r, nu, ell=1.0):
    """The Matern kernel for nu = 1/2, 3/2, 5/2 in closed form (17.11)-(17.13)."""
    s = np.asarray(r, float) / ell
    if nu == 0.5:
        return np.exp(-s)
    if nu == 1.5:
        return (1 + math.sqrt(3) * s) * np.exp(-math.sqrt(3) * s)
    if nu == 2.5:
        return (1 + math.sqrt(5) * s + 5 * s ** 2 / 3) * np.exp(-math.sqrt(5) * s)
    raise ValueError("closed form only for nu in {1/2, 3/2, 5/2}")


def matern(r, nu, ell=1.0):
    """The Matern kernel (17.10) for any nu > 0, with K(0) = 1 (modified Bessel function K_nu)."""
    r = np.abs(np.asarray(r, float))
    z = math.sqrt(2 * nu) * r / ell
    out = np.ones_like(z)
    pos = z > 0
    zp = z[pos]
    out[pos] = np.exp((1 - nu) * math.log(2) - special.gammaln(nu) + nu * np.log(zp) + np.log(special.kve(nu, zp)) - zp)
    return out


def kernel_matern(A, B, nu, ell=1.0, sf2=1.0):
    r = np.sqrt(sqdist(as_col(A), as_col(B)))
    if nu in (0.5, 1.5, 2.5):
        return sf2 * matern_closed(r, nu, ell)
    return sf2 * matern(r, nu, ell)


def kernel_periodic(A, B, ell=1.0, period=1.0, sf2=1.0):
    """Periodic kernel (17.14) on scalar inputs: exp(-2 sin^2(pi r / p) / ell^2)."""
    r = as_col(A)[:, :1] - as_col(B)[:, :1].T
    return sf2 * np.exp(-2.0 * np.sin(np.pi * r / period) ** 2 / ell ** 2)


def kernel_cosine(A, B, period=1.0):
    """Cosine kernel (17.15) on scalar inputs."""
    r = as_col(A)[:, :1] - as_col(B)[:, :1].T
    return np.cos(2 * np.pi * r / period)


def kernel_linear(A, B, c=0.0, sf2=1.0):
    """Linear kernel (x - c)'(x' - c) (17.56)."""
    return sf2 * (as_col(A) - c) @ (as_col(B) - c).T


def kernel_poly(A, B, degree=2, c=0.0):
    """Polynomial kernel (x'x' + c)^M (17.21)-(17.22)."""
    return (as_col(A) @ as_col(B).T + c) ** degree


def chol_jitter(K, jitter=1e-10):
    """Cholesky factor of K + jitter I, raising the jitter until it succeeds."""
    n = K.shape[0]
    j = jitter * max(1.0, float(np.mean(np.diag(K))))
    for _ in range(12):
        try:
            return np.linalg.cholesky(K + j * np.eye(n))
        except np.linalg.LinAlgError:
            j *= 10
    raise np.linalg.LinAlgError("matrix is not positive definite")


def gp_sample(K, n_samples, rng, jitter=1e-8):
    """Draws from N(0, K) as columns, via a Cholesky factor."""
    L = chol_jitter(K, jitter)
    return L @ rng.standard_normal((K.shape[0], n_samples))


# =========================================================================== GP regression (17.2)
def gp_posterior(X, y, Xs, kern, sigma_y2, mean0=0.0):
    """Posterior of f at Xs given y = f(X) + noise (17.34)-(17.38), computed as in (17.47)-(17.49).

    kern(A, B) returns the kernel matrix. sigma_y2 = 0 gives the noise-free case (17.28)-(17.30)
    (a tiny jitter keeps the Cholesky factor defined). Returns mean, covariance and log p(y | X).
    """
    X, Xs = as_col(X), as_col(Xs)
    y = np.asarray(y, float) - mean0
    N = len(y)
    K = kern(X, X) + max(sigma_y2, 1e-10) * np.eye(N)
    L = np.linalg.cholesky(K)
    alpha = linalg.solve_triangular(L.T, linalg.solve_triangular(L, y, lower=True), lower=False)
    Ks = kern(X, Xs)
    mu = Ks.T @ alpha + mean0
    V = linalg.solve_triangular(L, Ks, lower=True)
    cov = kern(Xs, Xs) - V.T @ V
    logml = -0.5 * y @ alpha - np.log(np.diag(L)).sum() - 0.5 * N * math.log(2 * math.pi)
    return mu, cov, logml


def se_logml(theta, X, y, grad=True):
    """Log marginal likelihood (17.52) of the SE kernel (17.50) plus noise, and its gradient (17.54).

    theta = (log ell, log sigma_f, log sigma_y). The gradient uses
    d/dtheta_j log p = 1/2 tr((alpha alpha' - K^-1) dK/dtheta_j), with
    dK/dlog ell = K_f * D2/ell^2, dK/dlog sigma_f = 2 K_f, dK/dlog sigma_y = 2 sigma_y^2 I.
    """
    X = as_col(X)
    y = np.asarray(y, float)
    ell, sf, sy = np.exp(theta)
    D2 = sqdist(X, X)
    Kf = sf ** 2 * np.exp(-0.5 * D2 / ell ** 2)
    N = len(y)
    K = Kf + sy ** 2 * np.eye(N)
    try:
        L = np.linalg.cholesky(K)
    except np.linalg.LinAlgError:
        return (-np.inf, np.zeros(3)) if grad else -np.inf
    alpha = linalg.cho_solve((L, True), y)
    val = -0.5 * y @ alpha - np.log(np.diag(L)).sum() - 0.5 * N * math.log(2 * math.pi)
    if not grad:
        return val
    Kinv = linalg.cho_solve((L, True), np.eye(N))
    Wm = np.outer(alpha, alpha) - Kinv
    dK = [Kf * D2 / ell ** 2, 2 * Kf, 2 * sy ** 2 * np.eye(N)]
    g = np.array([0.5 * np.sum(Wm * d) for d in dK])
    return val, g


def fit_se_hyper(X, y, starts, fix_sf=None):
    """Maximise se_logml from several starts (L-BFGS on log parameters); returns all local optima.

    With fix_sf the signal standard deviation is held fixed (as in Figure 17.9)."""
    out = []
    for s in starts:
        s = np.log(np.asarray(s, float))
        if fix_sf is not None:
            def f(t2):
                v, g = se_logml(np.array([t2[0], math.log(fix_sf), t2[1]]), X, y)
                return -v, -g[[0, 2]]
            r = optimize.minimize(f, s[[0, 2]], jac=True, method="L-BFGS-B",
                                  bounds=[(-4, 6), (-7, 3)], options=dict(gtol=1e-10, ftol=1e-14))
            th = np.array([r.x[0], math.log(fix_sf), r.x[1]])
        else:
            def f(t):
                v, g = se_logml(t, X, y)
                return -v, -g
            r = optimize.minimize(f, s, jac=True, method="L-BFGS-B",
                                  bounds=[(-4, 6), (-5, 5), (-7, 3)], options=dict(gtol=1e-10, ftol=1e-14))
            th = r.x
        out.append(dict(theta=th, params=np.exp(th), logml=-r.fun))
    return out


# =========================================================================== GP classification (17.2.7)
def gpc_mcmc(x, y, xgrid, kern_fn, theta0, log_prior, n_iter=6000, burn=2000, thin=4, step=0.25, seed=0, jitter=1e-6):
    """MCMC for a GP classifier with a Bernoulli-logit likelihood (17.55).

    The latent function at the training inputs and at the grid points is written f = L_theta nu
    with nu ~ N(0, I) (the 'whitened' parametrisation). Each iteration does one elliptical slice
    sampling update of nu given theta (Murray, Adams and MacKay, 2010) and one random-walk
    Metropolis update of the unconstrained kernel parameters theta given nu. The joint target is
    N(nu | 0, I) p(theta) prod_n Ber(y_n | sigmoid(f_n)), whose (f, theta)-marginal is the posterior.
    kern_fn(theta, A, B) returns kernel matrices; log_prior(theta) includes any Jacobian.
    Returns the kept draws of theta and of sigmoid(f) on the grid, and the acceptance rate.
    """
    rng = np.random.default_rng(seed)
    xa = np.concatenate([x, xgrid])
    N = len(x)
    n = len(xa)

    def chol(theta):
        return np.linalg.cholesky(kern_fn(theta, xa, xa) + jitter * np.eye(n))

    def loglik(f):
        fN = f[:N]
        return float(np.sum(y * fN - np.logaddexp(0, fN)))

    theta = np.array(theta0, float)
    L = chol(theta)
    nu = rng.standard_normal(n) * 0.1
    f = L @ nu
    ll = loglik(f)
    lp = log_prior(theta)
    keep_theta, keep_p = [], []
    acc = 0
    for it in range(n_iter):
        # elliptical slice sampling of nu (prior N(0, I))
        nu_p = rng.standard_normal(n)
        logy = ll + math.log(rng.uniform())
        a = rng.uniform(0, 2 * math.pi)
        lo, hi = a - 2 * math.pi, a
        while True:
            nu_new = nu * math.cos(a) + nu_p * math.sin(a)
            f_new = L @ nu_new
            ll_new = loglik(f_new)
            if ll_new > logy:
                nu, f, ll = nu_new, f_new, ll_new
                break
            if a < 0:
                lo = a
            else:
                hi = a
            a = rng.uniform(lo, hi)
        # Metropolis step on theta with nu fixed
        th_new = theta + step * rng.standard_normal(theta.shape)
        lp_new = log_prior(th_new)
        if np.isfinite(lp_new):
            try:
                L_new = chol(th_new)
                f_new = L_new @ nu
                ll_new = loglik(f_new)
                if math.log(rng.uniform()) < ll_new + lp_new - ll - lp:
                    theta, L, f, ll, lp = th_new, L_new, f_new, ll_new, lp_new
                    acc += 1
            except np.linalg.LinAlgError:
                pass
        if it >= burn and (it - burn) % thin == 0:
            keep_theta.append(theta.copy())
            keep_p.append(sigmoid(f[N:]))
    return np.array(keep_theta), np.array(keep_p), acc / n_iter


def crossing(xg, p, level=0.5, near=None):
    """Point where the curve p(xg) crosses `level` (linear interpolation): the first one, or the one
    nearest to `near`; nan if there is none."""
    s = np.sign(p - level)
    idx = np.where(s[:-1] * s[1:] < 0)[0]
    if len(idx) == 0:
        return np.nan
    xs = xg[idx] + (level - p[idx]) * (xg[idx + 1] - xg[idx]) / (p[idx + 1] - p[idx])
    return xs[0] if near is None else xs[np.argmin(np.abs(xs - near))]


# =========================================================================== random features (17.2.9.3)
class Mulberry32:
    """The seeded generator of the browser demonstrations (DK.rng in demo-kit.js), bit for bit:
    mulberry32 uniforms and Box-Muller normals with a cached spare."""

    M = 0xFFFFFFFF

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

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

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

    def normals(self, shape):
        n = int(np.prod(shape))
        return np.array([self.norm() for _ in range(n)]).reshape(shape)


def gram_schmidt(G):
    """Orthonormalise the rows of a square matrix (classical Gram-Schmidt, as in the browser)."""
    Q = np.array(G, float)
    for i in range(Q.shape[0]):
        for j in range(i):
            Q[i] -= (Q[i] @ Q[j]) * Q[j]
        Q[i] /= np.linalg.norm(Q[i])
    return Q


def rff_omega(T, D, sigma, kind="iid", seed=1):
    """T frequency vectors (rows) for the RBF kernel of bandwidth sigma: N(0, I/sigma^2) rows
    ('iid'), or blocks of D orthogonal rows with chi-distributed lengths ('orth', Yu et al. 2016).
    Uses the browser's generator so that the demonstration draws the same matrix."""
    g = Mulberry32(seed)
    if kind != "orth":
        return g.normals((T, D)) / sigma
    rows = []
    while len(rows) < T:
        G = g.normals((D, D))
        Q = gram_schmidt(G)
        lens = np.sqrt((g.normals((D, D)) ** 2).sum(1))
        for i in range(D):
            rows.append(Q[i] * lens[i])
    return np.array(rows[:T]) / sigma


def random_features(X, Omega, kind="trig", sigma=1.0):
    """Feature map whose inner products estimate the RBF kernel exp(-||x-x'||^2 / (2 sigma^2)).

    'trig': phi(x) = [sin(Omega x), cos(Omega x)] / sqrt(T) (17.59)-(17.60).
    'pos':  phi(x) = exp(-||x||^2 / sigma^2) exp(Omega x) / sqrt(T): positive features. The
            prefactor exp(-||x||^2/2) printed in (17.61) gives instead the 'softmax' kernel
            exp(x'x') for sigma = 1 (see the notes); this version estimates the RBF kernel.
    """
    X = as_col(X)
    A = X @ Omega.T
    T = Omega.shape[0]
    if kind == "trig":
        return np.hstack([np.sin(A), np.cos(A)]) / math.sqrt(T)
    return np.exp(A - (X ** 2).sum(1, keepdims=True) / sigma ** 2) / math.sqrt(T)


def rff_variance(k, T):
    """Exact variance of the paired sin/cos estimate of an RBF kernel value k with T frequencies:
    (1 - k^2)^2 / (2T)."""
    return (1 - k ** 2) ** 2 / (2 * T)


# =========================================================================== SVMs (17.3)
def smo(Q, p, z, C, tol=1e-8, max_iter=200000):
    """Minimise 1/2 a'Qa + p'a subject to z'a = 0 and 0 <= a <= C (C scalar or vector), z in {-1, 1}.

    Sequential minimal optimisation with second-order working-set selection (Fan, Chen and Lin,
    2005). At each step the pair (i, j) is the maximal violating pair chosen by the largest
    guaranteed decrease; moving a_i by z_i t and a_j by -z_j t keeps z'a fixed, and the step t is
    the one-dimensional Newton step clipped to the box. Stops when the KKT gap m(a) - M(a) < tol.
    Returns a and rho, where the bias of the decision function is -rho.
    """
    n = len(p)
    C = np.broadcast_to(np.asarray(C, float), (n,)).copy()
    a = np.zeros(n)
    G = p.astype(float).copy()
    diag = np.diag(Q).copy()
    it = 0
    for it in range(max_iter):
        zG = -z * G
        up = ((z > 0) & (a < C)) | ((z < 0) & (a > 0))
        low = ((z < 0) & (a < C)) | ((z > 0) & (a > 0))
        zu = np.where(up, zG, -np.inf)
        i = int(np.argmax(zu))
        m = zu[i]
        zl = np.where(low, zG, np.inf)
        Mlow = zl.min()
        if m - Mlow < tol:
            break
        b = m - zG
        cand = low & (b > 0)
        aij = diag[i] + diag - 2 * z[i] * z * Q[i]
        aij = np.where(aij > 1e-12, aij, 1e-12)
        score = np.where(cand, -b ** 2 / aij, np.inf)
        j = int(np.argmin(score))
        t = b[j] / aij[j]
        ti = C[i] - a[i] if z[i] > 0 else a[i]
        tj = a[j] if z[j] > 0 else C[j] - a[j]
        t = min(t, ti, tj)
        a[i] += z[i] * t
        a[j] -= z[j] * t
        a[i] = min(max(a[i], 0.0), C[i])
        a[j] = min(max(a[j], 0.0), C[j])
        G += t * (z[i] * Q[i] - z[j] * Q[j])
    # rho from the free variables (KKT: z_t G_t = rho for 0 < a_t < C_t)
    free = (a > 1e-12 * C) & (a < C * (1 - 1e-12))
    zG = z * G
    if free.any():
        rho = float(zG[free].mean())
    else:   # midpoint of the feasible interval for rho (as in libsvm)
        at_up = a >= C * (1 - 1e-12)
        at_lo = ~at_up
        lb_set = (at_up & (z > 0)) | (at_lo & (z < 0))
        ub_set = (at_up & (z < 0)) | (at_lo & (z > 0))
        lb = zG[lb_set].max() if lb_set.any() else -np.inf
        ub = zG[ub_set].min() if ub_set.any() else np.inf
        rho = 0.5 * (lb + ub) if np.isfinite(lb) and np.isfinite(ub) else (lb if np.isfinite(lb) else ub)
    return a, rho, it


def svc_fit(K, y, C, tol=1e-8):
    """Soft-margin SVM classifier (17.83) from its dual (17.85)-(17.87) solved by smo.

    y in {-1, +1}. Returns dict with alpha, b, the support set and the dual objective (17.85)."""
    y = np.asarray(y, float)
    Q = (y[:, None] * y[None, :]) * K
    a, rho, it = smo(Q, -np.ones(len(y)), y, C, tol)
    b = -rho
    coef = a * y
    dual = a.sum() - 0.5 * a @ Q @ a
    return dict(alpha=a, coef=coef, b=b, sv=np.where(a > 1e-8 * max(C, 1))[0], dual=dual, iters=it)


def svr_fit(K, y, C, eps, tol=1e-8):
    """epsilon-insensitive support vector regression (17.111) from its dual (2N variables).

    Variables (a+, a-) with z = (1,..,1, -1,..,-1), linear term (eps - y, eps + y); the fitted
    function is f(x) = sum_n (a+_n - a-_n) K(x_n, x) + b. Returns coefficients beta = a+ - a-."""
    y = np.asarray(y, float)
    N = len(y)
    z = np.r_[np.ones(N), -np.ones(N)]
    Kb = np.block([[K, K], [K, K]])
    Q = (z[:, None] * z[None, :]) * Kb
    p = np.r_[eps - y, eps + y]
    a, rho, it = smo(Q, p, z, C, tol)
    beta = a[:N] - a[N:]
    dual = -(0.5 * beta @ K @ beta + eps * a.sum() - y @ beta)
    return dict(beta=beta, b=-rho, sv=np.where(np.abs(beta) > 1e-8 * max(C, 1))[0], dual=dual, a=a, iters=it)


def svc_decision(Kx, fit):
    """f(x) = sum_n alpha_n y_n K(x_n, x) + b (17.93) for the rows Kx = K(x, X)."""
    return Kx @ fit["coef"] + fit["b"]


def platt(f, y01, iters=100):
    """Platt scaling (17.95): fit p(y=1|f) = sigmoid(a f + b) by Newton's method on held-out scores."""
    f = np.asarray(f, float)
    y01 = np.asarray(y01, float)
    w = np.zeros(2)
    Xd = np.column_stack([f, np.ones_like(f)])
    for _ in range(iters):
        mu = sigmoid(Xd @ w)
        g = Xd.T @ (mu - y01)
        H = Xd.T @ (Xd * (mu * (1 - mu))[:, None]) + 1e-10 * np.eye(2)
        step = np.linalg.solve(H, g)
        w -= step
        if np.abs(step).max() < 1e-12:
            break
    return w


def krr_fit(K, y, lam):
    """Kernel ridge regression (17.107): alpha = (K + lam I)^-1 y."""
    return np.linalg.solve(K + lam * np.eye(len(y)), y)


def kfold_indices(N, k, seed=0):
    rng = np.random.default_rng(seed)
    perm = rng.permutation(N)
    return [np.sort(perm[i::k]) for i in range(k)]


def cv_error(K, y, C, folds):
    """k-fold cross-validated 0-1 error of the SVM classifier for a precomputed kernel matrix."""
    errs = 0
    N = len(y)
    for te in folds:
        tr = np.setdiff1d(np.arange(N), te)
        fit = svc_fit(K[np.ix_(tr, tr)], y[tr], C, tol=1e-5)
        f = K[np.ix_(te, tr)] @ fit["coef"] + fit["b"]
        errs += np.sum(np.sign(f) != y[te])
    return errs / N


# =========================================================================== sparse vector machines (17.4)
def logreg_l2(Phi, y01, C, iters=100):
    """Minimise sum_n log(1 + exp(-yt_n f_n)) + ||w||^2 / (2C), f = Phi w + b (bias not penalised),
    by Newton's method. Returns (w, b)."""
    N, M = Phi.shape
    Xb = np.hstack([Phi, np.ones((N, 1))])
    w = np.zeros(M + 1)
    pen = np.r_[np.ones(M) / C, 0.0]
    for _ in range(iters):
        a = Xb @ w
        mu = sigmoid(a)
        g = Xb.T @ (mu - y01) + pen * w
        H = Xb.T @ (Xb * (mu * (1 - mu))[:, None]) + np.diag(pen) + 1e-12 * np.eye(M + 1)
        step = np.linalg.solve(H, g)
        w -= step
        if np.abs(step).max() < 1e-10:
            break
    return w[:M], w[M]


def logreg_obj(w, b, Phi, y01, C, l1):
    a = Phi @ w + b
    loss = np.sum(np.logaddexp(0, a) - y01 * a)
    return loss + (np.abs(w).sum() / C if l1 else (w @ w) / (2 * C))


def logreg_l1(Phi, y01, C, iters=20000, tol=1e-10):
    """Minimise sum_n log(1 + exp(-yt_n f_n)) + ||w||_1 / C (bias not penalised) by FISTA
    (proximal gradient with Nesterov momentum; the prox of the l1 norm is soft thresholding)."""
    N, M = Phi.shape
    Xb = np.hstack([Phi, np.ones((N, 1))])
    Lc = 0.25 * np.linalg.norm(Xb, 2) ** 2
    step = 1.0 / Lc
    w = np.zeros(M + 1)
    v = w.copy()
    t = 1.0
    thr = np.r_[np.ones(M), 0.0] * step / C
    for _ in range(iters):
        g = Xb.T @ (sigmoid(Xb @ v) - y01)
        u = v - step * g
        w_new = np.sign(u) * np.maximum(np.abs(u) - thr, 0.0)
        t_new = 0.5 * (1 + math.sqrt(1 + 4 * t * t))
        v = w_new + (t - 1) / t_new * (w_new - w)
        if np.abs(w_new - w).max() < tol:
            w = w_new
            break
        w, t = w_new, t_new
    return w[:M], w[M]


def lasso_cd(Phi, y, lam, iters=200000, tol=1e-12):
    """Minimise 1/2 ||y - Phi w - b||^2 + lam ||w||_1 (bias not penalised) by cyclic coordinate
    descent on centred data, with active-set cycling: sweep the nonzero coordinates until they
    settle, then do one full sweep, and stop when a full sweep changes nothing."""
    xm = Phi.mean(0)
    ym = y.mean()
    Xc = Phi - xm
    yc = y - ym
    M = Phi.shape[1]
    w = np.zeros(M)
    r = yc.copy()
    nrm = (Xc ** 2).sum(0)

    def sweep(idx):
        wmax = 0.0
        for j in idx:
            if nrm[j] == 0:
                continue
            old = w[j]
            rho = Xc[:, j] @ r + nrm[j] * old
            new = np.sign(rho) * max(abs(rho) - lam, 0.0) / nrm[j]
            if new != old:
                r[:] -= Xc[:, j] * (new - old)
                w[j] = new
                wmax = max(wmax, abs(new - old))
        return wmax

    full = np.arange(M)
    for _ in range(200):
        if sweep(full) < tol:
            break
        for _ in range(iters):
            if sweep(np.flatnonzero(w)) < tol:
                break
    return w, ym - xm @ w


def ridge_bias(Phi, y, lam):
    """Minimise ||y - Phi w - b||^2 + lam ||w||^2 (bias not penalised)."""
    xm = Phi.mean(0)
    ym = y.mean()
    Xc = Phi - xm
    w = np.linalg.solve(Xc.T @ Xc + lam * np.eye(Phi.shape[1]), Xc.T @ (y - ym))
    return w, ym - xm @ w


def rvm_regression(Phi, y, max_iter=2000, prune=1e9, tol=1e-7):
    """Relevance vector machine for regression (Tipping, 2001) by the re-estimation rules
    alpha_i <- gamma_i / mu_i^2, beta <- (N - sum gamma) / ||y - Phi mu||^2, gamma_i = 1 - alpha_i Sigma_ii,
    pruning basis functions whose alpha exceeds `prune`. Returns kept indices, mu, Sigma, alpha, beta."""
    N, M = Phi.shape
    keep = np.arange(M)
    alpha = np.ones(M)
    beta = 1.0 / max(np.var(y) * 0.1, 1e-6)
    for it in range(max_iter):
        P = Phi[:, keep]
        S = np.linalg.inv(beta * P.T @ P + np.diag(alpha))
        mu = beta * S @ P.T @ y
        gamma = 1 - alpha * np.diag(S)
        a_new = gamma / np.maximum(mu ** 2, 1e-300)
        resid = y - P @ mu
        beta = (N - gamma.sum()) / max(resid @ resid, 1e-300)
        ok = a_new < prune
        change = np.max(np.abs(np.log(a_new[ok]) - np.log(alpha[ok]))) if ok.any() else 0.0
        keep, alpha = keep[ok], a_new[ok]
        if ok.all() and change < tol:
            break
    P = Phi[:, keep]
    S = np.linalg.inv(beta * P.T @ P + np.diag(alpha))
    mu = beta * S @ P.T @ y
    return dict(keep=keep, mu=mu, Sigma=S, alpha=alpha, beta=beta, iters=it)


def rvm_logev(Phi, y, alpha, beta):
    """Log marginal likelihood of the RVM regression model, log N(y | 0, beta^-1 I + Phi A^-1 Phi')."""
    C = np.eye(len(y)) / beta + (Phi / alpha) @ Phi.T
    L = np.linalg.cholesky(C)
    z = linalg.solve_triangular(L, y, lower=True)
    return -0.5 * z @ z - np.log(np.diag(L)).sum() - 0.5 * len(y) * math.log(2 * math.pi)


def rvm_classification(Phi, y01, max_iter=500, prune=1e9, tol=1e-6):
    """Relevance vector machine for binary classification (Tipping, 2001): Laplace approximation
    of the weight posterior at its mode (Newton's method) and the re-estimation rule
    alpha_i <- gamma_i / mu_i^2, pruning large alphas. Returns kept indices, mode, covariance, alpha."""
    N, M = Phi.shape
    keep = np.arange(M)
    alpha = np.ones(M)
    w = np.zeros(M)
    for it in range(max_iter):
        P = Phi[:, keep]
        for _ in range(50):          # Newton for the mode of the penalised log-likelihood
            mu_ = sigmoid(P @ w)
            g = P.T @ (mu_ - y01) + alpha * w
            H = P.T @ (P * (mu_ * (1 - mu_))[:, None]) + np.diag(alpha)
            step = np.linalg.solve(H, g)
            w = w - step
            if np.abs(step).max() < 1e-9:
                break
        mu_ = sigmoid(P @ w)
        H = P.T @ (P * (mu_ * (1 - mu_))[:, None]) + np.diag(alpha)
        S = np.linalg.inv(H)
        gamma = 1 - alpha * np.diag(S)
        a_new = gamma / np.maximum(w ** 2, 1e-300)
        ok = a_new < prune
        change = np.max(np.abs(np.log(a_new[ok]) - np.log(alpha[ok]))) if ok.any() else 0.0
        keep, alpha, w = keep[ok], a_new[ok], w[ok]
        if ok.all() and change < tol:
            break
    return dict(keep=keep, w=w, Sigma=S if ok.all() else None, alpha=alpha, iters=it)


# =========================================================================== data
def iris_setosa_versicolor():
    """Sepal length and the label 1 = versicolor, 0 = setosa (100 flowers)."""
    from sklearn.datasets import load_iris
    d = load_iris()
    keep = d.target < 2
    return d.data[keep, 0], d.target[keep].astype(float)


def moons(n, noise, seed):
    """Two interleaving half circles (n points, half in each class) plus Gaussian noise; my own
    generator of the familiar 'two moons' toy data. Labels in {-1, +1}."""
    rng = np.random.default_rng(seed)
    n1 = n // 2
    n2 = n - n1
    t1 = np.pi * rng.uniform(size=n1)
    t2 = np.pi * rng.uniform(size=n2)
    A = np.column_stack([np.cos(t1), np.sin(t1)])
    B = np.column_stack([1 - np.cos(t2), 0.5 - np.sin(t2)])
    X = np.vstack([A, B]) + noise * rng.standard_normal((n, 2))
    y = np.r_[-np.ones(n1), np.ones(n2)]
    return X, y


def esl_mixture():
    """The simulated mixture data of Hastie, Tibshirani and Friedman (2009, Section 2.3)."""
    path = os.path.normpath(os.path.join(HERE, "..", "..", "esl", "data", "ch02-mixture.json"))
    d = json.load(open(path))
    X = np.array(d["x"])
    y = 2 * np.array(d["y"], float) - 1
    return X, y, d


def noisy_sinc(n=100, noise=0.1, seed=17):
    """y = sinc(x) + noise on a regular grid of n points in [-1.5, 1.5] (sinc(x) = sin(pi x)/(pi x))."""
    rng = np.random.default_rng(seed)
    x = np.linspace(-1.5, 1.5, n)
    return x, np.sinc(x) + noise * rng.standard_normal(n)


def gp_toy(n, seed, lo=-7.0, hi=7.0, ell=1.0, sf=1.0, sy=0.1):
    """n inputs uniform on [lo, hi] (sorted), f drawn from the SE-kernel GP, y = f + N(0, sy^2)."""
    rng = np.random.default_rng(seed)
    x = np.sort(rng.uniform(lo, hi, n))
    K = kernel_se(x, x, ell, sf ** 2)
    f = chol_jitter(K, 1e-10) @ rng.standard_normal(n)
    return x, f + sy * rng.standard_normal(n)


FIG9_SEED = 9210    # the 7-point data set of Figure 17.9 (a seed whose data show two local optima)
FIG8_SEED = 3       # the 20-point data set of Figure 17.8


def cached(name, fn):
    """Compute fn() once and keep the result (a dict of arrays) in cache/<name>.npz."""
    os.makedirs(CACHE_DIR, exist_ok=True)
    path = os.path.join(CACHE_DIR, name + ".npz")
    if os.path.exists(path):
        z = np.load(path, allow_pickle=False)
        return {k: z[k] for k in z.files}
    out = fn()
    np.savez_compressed(path, **out)
    return out


# =========================================================================== figures: 17.1
def fig_17_1(out=None):
    """Functions sampled from a GP prior with an ARD kernel in 2-D: l1 = l2 = 1, and l1 = 1, l2 = 5."""
    g = np.linspace(-3, 3, 26)
    G1, G2 = np.meshgrid(g, g)
    Xg = np.column_stack([G1.ravel(), G2.ravel()])
    fig = plt.figure(figsize=(8.4, 3.6))
    for k, (ells, lab) in enumerate([((1.0, 1.0), "a"), ((1.0, 5.0), "b")]):
        rng = np.random.default_rng(11)
        K = kernel_se(Xg, Xg, np.array(ells))
        f = gp_sample(K, 1, rng, jitter=1e-8)[:, 0].reshape(G1.shape)
        ax = fig.add_subplot(1, 2, k + 1, projection="3d")
        ax.plot_surface(G1, G2, f, cmap="viridis", linewidth=0.2, edgecolor="k", alpha=0.95, rasterized=True)
        ax.set_xlabel("input $x_1$")
        ax.set_ylabel("input $x_2$")
        ax.set_zlabel("output $y$")
        ax.set_title(r"(%s) $\ell_1=%g,\ \ell_2=%g$" % (lab, ells[0], ells[1]))
        ax.view_init(28, -60)
    savefig(fig, CH, "fig17-1", out)


def _stacked_samples(ax, x, F, title, offset=3.0):
    cols = [BLUE, ORANGE, GREEN, RED]
    for i in range(F.shape[1]):
        ax.plot(x, F[:, i] + offset * (F.shape[1] - 1 - i), color=cols[i % 4], lw=1.0)
    ax.set_yticks([])
    ax.set_title(title)
    ax.set_xlabel("$x$")


def fig_17_2(out=None):
    """Samples from GPs with Matern kernels, nu = 5/2 and nu = 1/2 (length scale 1)."""
    x = np.linspace(0, 10, 500)
    fig, axes = common.panel_grid(1, 2, size=(3.6, 3.0))
    for ax, nu, lab in zip(axes[0], (2.5, 0.5), "ab"):
        rng = np.random.default_rng(2)
        F = gp_sample(kernel_matern(x, x, nu, 1.0), 4, rng)
        _stacked_samples(ax, x, F, r"(%s) Matern, $\nu=%s$" % (lab, "5/2" if nu == 2.5 else "1/2"))
    fig.tight_layout()
    savefig(fig, CH, "fig17-2", out)


def fig_17_3(out=None):
    """Samples from GPs with the periodic kernel (17.14) and the cosine kernel (17.15)."""
    x = np.linspace(0, 10, 500)
    fig, axes = common.panel_grid(1, 2, size=(3.6, 3.0))
    rng = np.random.default_rng(4)
    F = gp_sample(kernel_periodic(x, x, ell=1.0, period=3.0), 4, rng)
    _stacked_samples(axes[0, 0], x, F, r"(a) periodic, $\ell=1,\ p=3$")
    rng = np.random.default_rng(5)
    F = gp_sample(kernel_cosine(x, x, period=3.0), 4, rng, jitter=1e-8)
    _stacked_samples(axes[0, 1], x, F, r"(b) cosine, $p=3$")
    fig.tight_layout()
    savefig(fig, CH, "fig17-3", out)


def _kernel_structure_figure(specs, name, out):
    """Top row: the kernel against x with x' = 1 (or against x - x'); bottom row: two GP samples."""
    x = np.linspace(-3, 3, 300)
    fig, axes = common.panel_grid(2, 4, size=(2.25, 1.85))
    for c, (title, kfun, stationary, desc) in enumerate(specs):
        ax = axes[0, c]
        if stationary:
            ax.plot(x, kfun(x, np.zeros(1))[:, 0], "k")
            ax.set_xlabel(r"$x-x'$")
        else:
            ax.plot(x, kfun(x, np.ones(1))[:, 0], "k")
            ax.set_xlabel(r"$x$ (with $x'=1$)")
        ax.axhline(0, color=GREY, lw=0.5)
        ax.set_yticks([0])
        ax.set_title(title)
        ax2 = axes[1, c]
        rng = np.random.default_rng(10 + c)
        F = gp_sample(kfun(x, x), 2, rng, jitter=1e-8)
        ax2.plot(x, F[:, 0], color=BLUE, lw=1.1)
        ax2.plot(x, F[:, 1], color=RED, lw=1.1)
        ax2.set_yticks([])
        ax2.set_xlabel(desc)
    fig.tight_layout()
    savefig(fig, CH, name, out)


def _lin(A, B):
    return kernel_linear(A, B, c=0.0)


def _per(A, B):
    return kernel_periodic(A, B, ell=1.0, period=1.0)


def _se(A, B):
    return kernel_se(A, B, 1.0)


def fig_17_4(out=None):
    """Structures from products of kernels: Lin x Lin, SE x Per, Lin x SE, Lin x Per."""
    specs = [("Lin $\\times$ Lin", lambda A, B: _lin(A, B) ** 2, False, "quadratic functions"),
             ("SE $\\times$ Per", lambda A, B: kernel_se(A, B, 2.0) * _per(A, B), True, "locally periodic"),
             ("Lin $\\times$ SE", lambda A, B: _lin(A, B) * _se(A, B), False, "increasing variation"),
             ("Lin $\\times$ Per", lambda A, B: _lin(A, B) * _per(A, B), False, "growing amplitude")]
    _kernel_structure_figure(specs, "fig17-4", out)


def fig_17_5(out=None):
    """Structures from sums of kernels: Lin + Per, SE + Per, SE + Lin, SE(long) + SE(short)."""
    specs = [("Lin + Per", lambda A, B: 0.3 * _lin(A, B) + 0.3 * _per(A, B), False, "periodic plus trend"),
             ("SE + Per", lambda A, B: kernel_se(A, B, 0.15, 0.15) + _per(A, B), True, "periodic plus noise"),
             ("SE + Lin", lambda A, B: 0.3 * _se(A, B) + _lin(A, B), False, "linear plus variation"),
             ("SE$^{\\rm long}$ + SE$^{\\rm short}$", lambda A, B: kernel_se(A, B, 2.0) + kernel_se(A, B, 0.15, 0.06), True, "slow and fast variation")]
    _kernel_structure_figure(specs, "fig17-5", out)


# =========================================================================== figures: 17.2
def _gp_band(ax, x, mu, sd, colour=BLUE):
    ax.fill_between(x, mu - 2 * sd, mu + 2 * sd, color=colour, alpha=0.18, lw=0)
    ax.plot(x, mu, color="k", lw=1.6)


FIG7_X = np.array([-1.0, 2.5, -3.5, 0.8])


def fig7_data():
    rng = np.random.default_rng(21)
    K = kernel_se(FIG7_X, FIG7_X, 1.0)
    return chol_jitter(K, 1e-12) @ rng.standard_normal(4)


def fig_17_7(out=None):
    """GP prior samples (SE kernel) and posteriors after 1, 2 and 4 noise-free observations."""
    xs = np.linspace(-5, 5, 300)
    f_obs = fig7_data()
    fig, axes = common.panel_grid(1, 4, size=(2.6, 2.4))
    kern = lambda A, B: kernel_se(A, B, 1.0)
    rng = np.random.default_rng(3)
    for k, n in enumerate([0, 1, 2, 4]):
        ax = axes[0, k]
        if n == 0:
            mu, cov = np.zeros_like(xs), kern(xs, xs)
        else:
            mu, cov, _ = gp_posterior(FIG7_X[:n], f_obs[:n], xs, kern, 0.0)
        sd = np.sqrt(np.maximum(np.diag(cov), 0))
        _gp_band(ax, xs, mu, sd)
        F = mu[:, None] + chol_jitter(cov, 1e-9) @ rng.standard_normal((len(xs), 3))
        for j, c in enumerate([BLUE, ORANGE, GREEN]):
            ax.plot(xs, F[:, j], color=c, lw=0.9)
        if n:
            ax.plot(FIG7_X[:n], f_obs[:n], "k+", ms=10, mew=2)
        ax.set_title("prior" if n == 0 else "$N=%d$" % n)
        common.panel_label(ax, "abcd"[k], "lower left")
        ax.set_ylim(-3, 3)
    fig.tight_layout()
    savefig(fig, CH, "fig17-7", out)


def fig8_data():
    return gp_toy(20, FIG8_SEED, lo=-7.5, hi=7.5)


def fig_17_8(out=None):
    """1-D GP regression on 20 noisy points with hyper-parameters (1, 1, 0.1) and (3, 1.16, 0.89)."""
    x, y = fig8_data()
    xs = np.linspace(-10, 10, 400)
    fig, axes = common.panel_grid(1, 2, size=(3.8, 2.9))
    for ax, (ell, sf, sy), lab in zip(axes[0], [(1.0, 1.0, 0.1), (3.0, 1.16, 0.89)], "ab"):
        kern = lambda A, B, ell=ell, sf=sf: kernel_se(A, B, ell, sf ** 2)
        mu, cov, lml = gp_posterior(x, y, xs, kern, sy ** 2)
        sd = np.sqrt(np.maximum(np.diag(cov), 0) + sy ** 2)
        _gp_band(ax, xs, mu, sd)
        ax.plot(x, y, "k+", ms=8, mew=1.5)
        ax.set_title(r"$(\ell,\sigma_f,\sigma_y)=(%g, %g, %g)$" % (ell, sf, sy) + "\nlog marginal lik. %.2f" % lml, fontsize=9.5)
        common.panel_label(ax, lab, "lower left")
    fig.tight_layout()
    savefig(fig, CH, "fig17-8", out)


def fig9_data():
    return gp_toy(7, FIG9_SEED)


def fig9_surface(n=70):
    x, y = fig9_data()
    ells = np.logspace(-0.5, 1.6, n)
    sys_ = np.logspace(-1.6, 0.3, n)
    Z = np.array([[se_logml(np.log([l, 1.0, s]), x, y, grad=False) for l in ells] for s in sys_])
    return ells, sys_, Z


def fig9_optima():
    x, y = fig9_data()
    return fit_se_hyper(x, y, [(1.0, 1.0, 0.2), (10.0, 1.0, 0.8)], fix_sf=1.0)


def fig_17_9(out=None):
    """Log marginal likelihood against length scale and noise level (sigma_f = 1) for 7 points:
    two local optima, and the fits they give."""
    x, y = fig9_data()
    ells, sys_, Z = fig9_surface()
    opts = fig9_optima()
    fig, axes = common.panel_grid(1, 3, size=(3.0, 2.8))
    ax = axes[0, 0]
    top = Z.max()
    lev = top - np.array([12, 8, 5, 3, 2, 1.2, 0.6, 0.25])
    ax.contour(ells, sys_, Z, levels=lev, cmap="viridis")
    for o in opts:
        ax.plot(o["params"][0], o["params"][2], "k+", ms=10, mew=1.8)
    ax.set_xscale("log")
    ax.set_yscale("log")
    ax.set_xlabel(r"length scale $\ell$")
    ax.set_ylabel(r"noise s.d. $\sigma_y$")
    common.panel_label(ax, "a", "lower right")
    xs = np.linspace(-7.5, 7.5, 300)
    for ax, o, lab in zip(axes[0, 1:], opts, "bc"):
        ell, sf, sy = o["params"]
        kern = lambda A, B, ell=ell: kernel_se(A, B, ell, 1.0)
        mu, cov, _ = gp_posterior(x, y, xs, kern, sy ** 2)
        sd = np.sqrt(np.maximum(np.diag(cov), 0) + sy ** 2)
        _gp_band(ax, xs, mu, sd, GREY)
        ax.plot(x, y, "k+", ms=9, mew=1.8)
        ax.set_ylim(-2.6, 2.6)
        ax.set_title(r"$\ell=%.2f,\ \sigma_y=%.2f$" % (ell, sy) + "\nlog $p(y)=%.3f$" % o["logml"], fontsize=9.5)
        common.panel_label(ax, lab, "lower left")
    fig.tight_layout()
    savefig(fig, CH, "fig17-9", out)


# ================================================================ GP classification
GA_SHAPE, GA_RATE = 2.0, 0.5       # Ga(2, 0.5) prior on the length scale (shape, rate), as in the book


def _iris_gpc(kind):
    x, y = iris_setosa_versicolor()
    xg = np.linspace(4.0, 7.2, 81)
    if kind == "se":
        def kfun(th, A, B):
            return kernel_se(A, B, math.exp(th[0]))

        def lprior(th):
            ell = math.exp(th[0])
            return (GA_SHAPE - 1) * math.log(ell) - GA_RATE * ell + th[0]      # + log Jacobian
        th0 = [math.log(1.0)]
    else:
        def kfun(th, A, B):
            ell, tau, c = math.exp(th[0]), math.exp(th[1]), th[2]
            return tau * kernel_linear(A, B, c) + kernel_se(A, B, ell)

        def lprior(th):
            ell, tau, c = math.exp(th[0]), math.exp(th[1]), th[2]
            lp = (GA_SHAPE - 1) * math.log(ell) - GA_RATE * ell + th[0]
            lp += -math.log1p((tau / 5.0) ** 2) + th[1]                       # half-Cauchy(0, 5) on tau
            lp += -0.5 * (c - 5.4) ** 2                                         # c ~ N(5.4, 1)
            return lp
        th0 = [math.log(1.0), math.log(5.0), 5.4]
    th, P, acc = gpc_mcmc(x, y, xg, kfun, th0, lprior, n_iter=8000, burn=2000, thin=6, step=0.3, seed=1)
    return dict(x=x, y=y, xg=xg, theta=th, P=P, acc=np.array(acc))


def _gpc_panel(ax, r, xlabel, ylab=("0", "1")):
    x, y, xg, P = r["x"], r["y"], r["xg"], r["P"]
    bnd = np.array([crossing(xg, p, near=x.mean()) for p in P])     # the crossing in the data region
    rng = np.random.default_rng(0)
    jit = 0.02 * rng.standard_normal(len(x))
    lo, hi = np.percentile(P, [2.5, 97.5], axis=0)
    b = bnd[np.isfinite(bnd)]
    blo, bmed, bhi = np.percentile(b, [2.5, 50, 97.5])
    ax.axvspan(blo, bhi, color="k", alpha=0.35, lw=0)
    ax.axvline(bmed, color="k", lw=1.2)
    ax.fill_between(xg, lo, hi, color=GREEN, alpha=0.35, lw=0)
    ax.plot(xg, P.mean(0), color=BLUE, lw=1.6)
    ax.scatter(x[y == 1], 1 + jit[y == 1], s=8, color=ORANGE, zorder=3)
    ax.scatter(x[y == 0], 0 + jit[y == 0], s=8, color=BLUE, zorder=3)
    ax.set_xlabel(xlabel)
    ax.set_ylim(-0.08, 1.08)
    return blo, bmed, bhi


def fig_17_10(out=None):
    """GP classifier for setosa (0) against versicolor (1) from sepal length, by MCMC: SE kernel,
    and SE plus linear kernel."""
    fig, axes = common.panel_grid(1, 2, size=(3.8, 2.9))
    for ax, kind, lab in zip(axes[0], ("se", "selin"), "ab"):
        r = cached("ch17_gpc_iris_%s" % kind, lambda kind=kind: _iris_gpc(kind))
        blo, bmed, bhi = _gpc_panel(ax, r, "sepal length")
        ax.set_title("(%s) %s: boundary %.2f [%.2f, %.2f]" % (lab, "SE" if kind == "se" else "SE + linear", bmed, blo, bhi), fontsize=9)
    fig.tight_layout()
    savefig(fig, CH, "fig17-10", out)


def spaceflu_data():
    """Fictitious 'space flu' data in the spirit of the book's example: 60 people, ages 0 to 80,
    the young and the old more often sick (my own simulation)."""
    rng = np.random.default_rng(8)
    age = np.sort(rng.uniform(0, 80, 60))
    logit = 3.0 - 0.45 * age + 0.0 * age
    logit = np.where(age < 40, 3.0 - 0.3 * age, -6.0 + 0.12 * age)
    sick = (rng.uniform(size=60) < sigmoid(logit)).astype(float)
    return age, sick


def _spaceflu_gpc():
    x, y = spaceflu_data()
    xg = np.linspace(0, 80, 81)

    def kfun(th, A, B):
        return kernel_se(A, B, math.exp(th[0]), math.exp(2 * th[1]))

    def lprior(th):
        ell, sf = math.exp(th[0]), math.exp(th[1])
        return (GA_SHAPE - 1) * math.log(ell) - 0.1 * ell + th[0] - 0.5 * (sf / 3.0) ** 2 + th[1]
    th, P, acc = gpc_mcmc(x, y, xg, kfun, [math.log(10.0), math.log(2.0)], lprior, n_iter=8000, burn=2000, thin=6, step=0.3, seed=2)
    return dict(x=x, y=y, xg=xg, theta=th, P=P, acc=np.array(acc))


def fig_17_11(out=None):
    """Fictitious 'space flu' data and the GP classifier (SE kernel) fitted by MCMC."""
    r = cached("ch17_gpc_spaceflu", _spaceflu_gpc)
    x, y, xg, P = r["x"], r["y"], r["xg"], r["P"]
    fig, axes = common.panel_grid(1, 2, size=(3.8, 2.7))
    ax = axes[0, 0]
    ax.scatter(x, y, c=np.where(y == 1, RED, BLUE), s=14)
    ax.set_yticks([0, 1])
    ax.set_yticklabels(["healthy", "sick"])
    ax.set_xlabel("age")
    ax.set_ylim(-0.3, 1.3)
    ax.set_title("(a) data")
    ax = axes[0, 1]
    lo, hi = np.percentile(P, [2.5, 97.5], axis=0)
    ax.fill_between(xg, lo, hi, color=GREEN, alpha=0.35, lw=0)
    ax.plot(xg, P.mean(0), color=BLUE, lw=1.6)
    ax.scatter(x, y, c=np.where(y == 1, RED, BLUE), s=14, zorder=3)
    ax.set_yticks([0, 0.5, 1])
    ax.set_xlabel("age")
    ax.set_ylabel("p(sick)")
    ax.set_title("(b) GP classifier, SE kernel")
    fig.tight_layout()
    savefig(fig, CH, "fig17-11", out)


# =========================================================================== figures: 17.3
def rbf(A, B, gamma):
    """RBF kernel in the SVM convention exp(-gamma ||x - x'||^2), gamma = 1 / (2 sigma^2)."""
    return np.exp(-gamma * sqdist(as_col(A), as_col(B)))


FIG14_X = np.array([[1.0, 58.0], [4.5, 22.0], [2.5, 82.0], [5.5, 63.0]])
FIG14_Y = np.array([-1.0, -1.0, 1.0, 1.0])


def _linear_svm_panel(ax, X, y, C=1e4):
    K = X @ X.T
    fit = svc_fit(K, y, C)
    w = fit["coef"] @ X
    b = fit["b"]
    x0 = np.linspace(X[:, 0].min() - 0.15 * np.ptp(X[:, 0]) - 0.3, X[:, 0].max() + 0.15 * np.ptp(X[:, 0]) + 0.3, 50)
    for off, ls in [(0, "-"), (1, "--"), (-1, "--")]:
        ax.plot(x0, (off - b - w[0] * x0) / w[1], "k", ls=ls, lw=1.2 if off == 0 else 0.9)
    ax.scatter(X[y > 0, 0], X[y > 0, 1], marker="s", color=BLUE, s=30, zorder=3)
    ax.scatter(X[y < 0, 0], X[y < 0, 1], marker="o", color=RED, s=30, zorder=3)
    ax.scatter(X[fit["sv"], 0], X[fit["sv"], 1], s=180, facecolors="none", edgecolors=GREY, lw=1.2)
    return fit, w, b


def fig_17_14(out=None):
    """A hard-margin linear SVM on four points before and after standardising the two features."""
    X, y = FIG14_X, FIG14_Y
    fig, axes = common.panel_grid(1, 2, size=(3.9, 3.0))
    ax = axes[0, 0]
    fit, w, b = _linear_svm_panel(ax, X, y)
    ax.set_ylim(0, 100)
    ax.set_xlim(0, 6.5)
    ax.set_xlabel("$x_1$")
    ax.set_ylabel("$x_2$")
    ax.set_title("unscaled: margin %.2f" % (1 / np.linalg.norm(w)))
    Xs = (X - X.mean(0)) / X.std(0)
    ax = axes[0, 1]
    fit, w, b = _linear_svm_panel(ax, Xs, y)
    ax.set_xlim(-2, 2)
    ax.set_ylim(-2, 2)
    ax.set_aspect("equal")
    ax.set_xlabel("$x_1'$ (standardised)")
    ax.set_ylabel("$x_2'$")
    ax.set_title("scaled: margin %.2f" % (1 / np.linalg.norm(w)))
    fig.tight_layout()
    savefig(fig, CH, "fig17-14", out)


def tipping_data(n=1000, seed=0):
    """Tipping's example: y ~ Ber(1/2), x | y=0 ~ Unif(0, 1), x | y=1 ~ Unif(0.5, 1.5)."""
    rng = np.random.default_rng(seed)
    y = (rng.uniform(size=n) < 0.5).astype(float)
    x = rng.uniform(size=n) + 0.5 * y
    return x, y


TIP_GAMMA = 1 / (2 * 0.1 ** 2)      # Gaussian kernel of width 0.1


def _tipping_fits():
    x, y = tipping_data()
    yt = 2 * y - 1
    K = rbf(x, x, TIP_GAMMA)
    folds = kfold_indices(len(x), 5, 1)
    Cs = np.array([0.1, 1.0, 10.0, 100.0])
    cv = np.array([cv_error(K, yt, C, folds) for C in Cs])
    C = Cs[np.argmin(cv)]
    svm = svc_fit(K, yt, C, tol=1e-6)
    Phi = np.hstack([np.ones((len(x), 1)), K])
    rvm = rvm_classification(Phi, y)
    return dict(C=np.array(C), cv=cv, Cs=Cs, coef=svm["coef"], b=np.array(svm["b"]), nsv=np.array(len(svm["sv"])),
                keep=rvm["keep"], w=rvm["w"])


def tipping_predict(fits, xs):
    x, _ = tipping_data()
    f_svm = rbf(xs, x, TIP_GAMMA) @ fits["coef"] + fits["b"]
    Phi = np.hstack([np.ones((len(xs), 1)), rbf(xs, x, TIP_GAMMA)])
    f_rvm = Phi[:, fits["keep"]] @ fits["w"]
    return f_svm, f_rvm


def fig_17_15(out=None):
    """Log-odds against x for Tipping's overlapping-uniform data: truth, RVM and SVM."""
    fits = cached("ch17_tipping", _tipping_fits)
    xs = np.linspace(0.4, 1.2, 801)
    f_svm, f_rvm = tipping_predict(fits, xs)
    xt, yt = tipping_data(20000, 99)
    s_t, r_t = tipping_predict(fits, xt)
    err_svm = np.mean((s_t > 0) != (yt > 0.5))
    err_rvm = np.mean((r_t > 0) != (yt > 0.5))
    fig, ax = plt.subplots(figsize=(4.6, 3.3))
    ax.plot([0.4, 0.5, 0.5, 1.0, 1.0, 1.2], [-6, -6, 0, 0, 6, 6], "k", lw=2.2, label="correct log-odds")
    ax.plot(xs, f_rvm, color=RED, lw=1.4, label="RVM $f(x)$ (%d vectors)" % len(fits["keep"]))
    ax.plot(xs, f_svm, color=BLUE, lw=1.4, ls="--", label="SVM $f(x)$ (%d vectors)" % int(fits["nsv"]))
    ax.set_ylim(-6.5, 6.5)
    ax.set_xlabel("$x$")
    ax.legend(loc="upper left", fontsize=8)
    ax.set_title("test error: RVM %.3f, SVM %.3f" % (err_rvm, err_svm), fontsize=9.5)
    fig.tight_layout()
    savefig(fig, CH, "fig17-15", out)


FIG17_MOONS = dict(n=100, noise=0.15, seed=42)


def _decision_panel(ax, X, y, f_grid, G1, G2, sv=None, levels=(-1, 0, 1)):
    ax.contourf(G1, G2, f_grid, levels=[-1e9, 0, 1e9], colors=["#f6d5d5", "#d6e3f6"], alpha=0.9)
    ax.contour(G1, G2, f_grid, levels=list(levels), colors="k", linestyles=["--", "-", "--"][:len(levels)] if len(levels) == 3 else "-", linewidths=[0.8, 1.3, 0.8][:len(levels)] if len(levels) == 3 else 1.3)
    ax.scatter(X[y < 0, 0], X[y < 0, 1], s=12, color=RED, marker="o", zorder=3)
    ax.scatter(X[y > 0, 0], X[y > 0, 1], s=12, color=BLUE, marker="s", zorder=3)
    if sv is not None and len(sv):
        ax.scatter(X[sv, 0], X[sv, 1], s=60, facecolors="none", edgecolors=GREEN, lw=1.0, zorder=4)


def fig_17_17(out=None):
    """RBF-kernel SVM on two-moons data for gamma in {0.1, 5} and C in {0.001, 1000}."""
    X, y = moons(**FIG17_MOONS)
    g1 = np.linspace(-1.5, 2.5, 160)
    g2 = np.linspace(-1.0, 1.5, 110)
    G1, G2 = np.meshgrid(g1, g2)
    Xg = np.column_stack([G1.ravel(), G2.ravel()])
    fig, axes = common.panel_grid(2, 2, size=(3.5, 2.6))
    for k, (gam, C) in enumerate([(0.1, 0.001), (0.1, 1000), (5, 0.001), (5, 1000)]):
        ax = axes.ravel()[k]
        K = rbf(X, X, gam)
        fit = svc_fit(K, y, C)
        f = (rbf(Xg, X, gam) @ fit["coef"] + fit["b"]).reshape(G1.shape)
        _decision_panel(ax, X, y, f, G1, G2, fit["sv"])
        err = np.mean(np.sign(K @ fit["coef"] + fit["b"]) != y)
        ax.set_title(r"$\gamma=%g,\ C=%g$: %d SVs, train err %.2f" % (gam, C, len(fit["sv"]), err), fontsize=9)
        if k >= 2:
            ax.set_xlabel("$x_1$")
        if k % 2 == 0:
            ax.set_ylabel("$x_2$")
    fig.tight_layout()
    savefig(fig, CH, "fig17-17", out)


def svm_cv_grid(X, y, logC, logG, k=5, seed=0):
    """5-fold CV error of the RBF SVM over a grid of (log C, log gamma) (natural logs).

    For speed the grid uses scikit-learn's SVC (libsvm), which solves the same dual (17.85)-(17.87)
    as smo above (their solutions agree, see the notes); the folds are fixed by `seed`."""
    from sklearn.svm import SVC
    folds = kfold_indices(len(y), k, seed)
    N = len(y)
    E = np.zeros((len(logG), len(logC)))
    for a, lg in enumerate(logG):
        K = rbf(X, X, math.exp(lg))
        for b, lc in enumerate(logC):
            errs = 0
            for te in folds:
                tr = np.setdiff1d(np.arange(N), te)
                s = SVC(kernel="precomputed", C=math.exp(lc), tol=1e-4, cache_size=50).fit(K[np.ix_(tr, tr)], y[tr])
                errs += np.sum(s.predict(K[np.ix_(te, tr)]) != y[te])
            E[a, b] = errs / N
    return E


MIX_LOGC = np.arange(-2.0, 8.01, 1.0)
MIX_LOGG = np.arange(-2.0, 2.01, 0.5)


def _mixture_cv():
    X, y, d = esl_mixture()
    E = svm_cv_grid(X, y, MIX_LOGC, MIX_LOGG)
    Cs = np.logspace(-1, 3.5, 19)
    slice_ = svm_cv_grid(X, y, np.log(Cs), np.array([math.log(5.0)]))[0]
    return dict(E=E, Cs=Cs, slice=slice_)


def fig_17_18(out=None):
    """5-fold CV error of an RBF SVM on the mixture data over (C, gamma), and the slice gamma = 5."""
    r = cached("ch17_mixture_cv", _mixture_cv)
    _, _, d = esl_mixture()
    bayes = d["bayes_rate"]
    fig, axes = common.panel_grid(1, 2, size=(4.2, 3.1))
    ax = axes[0, 0]
    im = ax.imshow(r["E"], origin="lower", aspect="auto", cmap="viridis",
                   extent=[MIX_LOGC[0] - 0.5, MIX_LOGC[-1] + 0.5, MIX_LOGG[0] - 0.25, MIX_LOGG[-1] + 0.25])
    fig.colorbar(im, ax=ax, label="CV error", fraction=0.05)
    i, j = np.unravel_index(np.argmin(r["E"]), r["E"].shape)
    ax.plot(MIX_LOGC[j], MIX_LOGG[i], "w+", ms=10, mew=2)
    ax.set_xlabel(r"$\log C$")
    ax.set_ylabel(r"$\log\gamma$")
    ax.set_title("(a) CV error, min %.3f" % r["E"].min(), fontsize=9.5)
    ax = axes[0, 1]
    ax.semilogx(r["Cs"], r["slice"], "o-", color=BLUE, ms=4, label="CV error")
    ax.axhline(bayes, color=ORANGE, lw=1.5, label="Bayes error %.3f" % bayes)
    jbest = np.argmin(r["slice"])
    ax.axvline(r["Cs"][jbest], color=GREY, ls="--", lw=1, label="lowest point")
    ax.set_xlabel("$C$")
    ax.set_ylabel("CV error")
    ax.set_title(r"(b) slice at $\gamma=5$", fontsize=9.5)
    ax.legend(fontsize=7.5)
    fig.tight_layout()
    savefig(fig, CH, "fig17-18", out)


def huber(r, delta):
    a = np.abs(r)
    return np.where(a <= delta, 0.5 * r ** 2, delta * a - 0.5 * delta ** 2)


def eps_insensitive(r, eps):
    return np.maximum(np.abs(r) - eps, 0.0)


def tube_data():
    rng = np.random.default_rng(5)
    x = np.sort(rng.uniform(0, 1, 25))
    return x, np.sin(2 * np.pi * x) + 0.3 * rng.standard_normal(25)


def fig_17_19(out=None):
    """(a) l2, Huber and epsilon-insensitive losses (epsilon = delta = 1.5); (b) an epsilon tube
    around a fitted support vector regression, with the slack of the points outside it."""
    fig, axes = common.panel_grid(1, 2, size=(3.7, 3.0))
    ax = axes[0, 0]
    r = np.linspace(-3, 3, 401)
    ax.plot(r, r ** 2, color=RED, label="$\\ell_2$")
    ax.plot(r, eps_insensitive(r, 1.5), color=BLUE, ls="--", label="$\\epsilon$-insensitive")
    ax.plot(r, huber(r, 1.5), color=GREEN, ls="-.", label="Huber")
    ax.set_ylim(-0.5, 5)
    ax.set_xlabel("residual $y-\\hat y$")
    ax.legend(fontsize=8, loc="upper center")
    common.panel_label(ax, "a", "lower left")
    ax = axes[0, 1]
    x, y = tube_data()
    eps = 0.25
    gam = 1 / (2 * 0.15 ** 2)
    fit = svr_fit(rbf(x, x, gam), y, 2.0, eps)
    xs = np.linspace(0, 1, 300)
    fs = rbf(xs, x, gam) @ fit["beta"] + fit["b"]
    ax.plot(xs, fs, "r", lw=1.4, label="$f(x)$")
    ax.plot(xs, fs + eps, "r--", lw=0.8)
    ax.plot(xs, fs - eps, "r--", lw=0.8)
    fx = rbf(x, x, gam) @ fit["beta"] + fit["b"]
    above, below = y > fx + eps + 1e-9, y < fx - eps - 1e-9
    inside = ~(above | below)
    ax.scatter(x[inside], y[inside], s=14, color=GREY, zorder=3)
    ax.scatter(x[above], y[above], s=18, color=BLUE, zorder=3, label=r"$\xi^+>0$")
    ax.scatter(x[below], y[below], s=18, color=GREEN, zorder=3, label=r"$\xi^->0$")
    for i in np.where(above | below)[0]:
        ax.plot([x[i], x[i]], [y[i], fx[i] + (eps if above[i] else -eps)], color=GREY, lw=0.8)
    ax.set_xlabel("$x$")
    ax.legend(fontsize=7.5, loc="upper right")
    common.panel_label(ax, "b", "lower left")
    fig.tight_layout()
    savefig(fig, CH, "fig17-19", out)


def svr_toy():
    """60 points, x ~ Unif(-1, 1), y = 0.2 + 0.1 x + 0.5 x^2 + N(0, 0.1^2) (my own simulation)."""
    rng = np.random.default_rng(42)
    x = rng.uniform(-1, 1, 60)
    return x, 0.2 + 0.1 * x + 0.5 * x ** 2 + 0.1 * rng.standard_normal(60)


def fig_17_20(out=None):
    """Support vector regression with an RBF kernel (gamma = 1) for C in {100, 0.01} and
    epsilon in {0.1, 0.05}."""
    x, y = svr_toy()
    xs = np.linspace(-1, 1, 300)
    K = rbf(x, x, 1.0)
    fig, axes = common.panel_grid(2, 2, size=(3.3, 2.4))
    for k, (C, eps) in enumerate([(100, 0.1), (0.01, 0.1), (100, 0.05), (0.01, 0.05)]):
        ax = axes.ravel()[k]
        fit = svr_fit(K, y, C, eps)
        fs = rbf(xs, x, 1.0) @ fit["beta"] + fit["b"]
        ax.plot(xs, fs, color="k", lw=1.5)
        ax.plot(xs, fs + eps, "k--", lw=0.8)
        ax.plot(xs, fs - eps, "k--", lw=0.8)
        ax.scatter(x, y, s=10, color=BLUE, zorder=3)
        ax.scatter(x[fit["sv"]], y[fit["sv"]], s=55, facecolors="none", edgecolors=MAGENTA, lw=1.0, zorder=4)
        ax.set_title(r"$C=%g,\ \epsilon=%g$: %d SVs" % (C, eps, len(fit["sv"])), fontsize=9.5)
        ax.set_ylim(-0.1, 1.05)
        if k >= 2:
            ax.set_xlabel("$x_1$")
        if k % 2 == 0:
            ax.set_ylabel("$y$")
    fig.tight_layout()
    savefig(fig, CH, "fig17-20", out)


# =========================================================================== figures: 17.4
FIG21_MOONS = dict(n=200, noise=0.3, seed=10)
FIG21_GAMMA = 1 / (2 * 0.3 ** 2)


def _fig21_fits():
    X, y = moons(**FIG21_MOONS)
    y01 = (y > 0).astype(float)
    K = rbf(X, X, FIG21_GAMMA)
    Cs = 2.0 ** np.linspace(-5, 5, 10)
    folds = kfold_indices(len(y), 5, 0)
    cv = np.array([cv_error(K, y, C, folds) for C in Cs])
    C = Cs[np.argmin(cv)]
    w2, b2 = logreg_l2(K, y01, C)
    w1, b1 = logreg_l1(K, y01, C)
    svm = svc_fit(K, y, C)
    Phi = np.hstack([np.ones((len(y), 1)), K])
    rvm = rvm_classification(Phi, y01)
    return dict(C=np.array(C), Cs=Cs, cv=cv, w2=w2, b2=np.array(b2), w1=w1, b1=np.array(b1),
                svm_coef=svm["coef"], svm_b=np.array(svm["b"]), svm_sv=svm["sv"], rvm_keep=rvm["keep"], rvm_w=rvm["w"])


def fig21_predict(r, Xq):
    X, _ = moons(**FIG21_MOONS)
    Kq = rbf(Xq, X, FIG21_GAMMA)
    Phi = np.hstack([np.ones((len(Xq), 1)), Kq])
    return dict(l2=Kq @ r["w2"] + r["b2"], l1=Kq @ r["w1"] + r["b1"], rvm=Phi[:, r["rvm_keep"]] @ r["rvm_w"],
                svm=Kq @ r["svm_coef"] + r["svm_b"])


def fig_17_21(out=None):
    """Nonlinear classification with an RBF kernel (sigma = 0.3): L2VM, L1VM, RVM and SVM."""
    r = cached("ch17_fig21", _fig21_fits)
    X, y = moons(**FIG21_MOONS)
    g1 = np.linspace(-2.2, 3.2, 170)
    g2 = np.linspace(-1.8, 2.3, 130)
    G1, G2 = np.meshgrid(g1, g2)
    Xg = np.column_stack([G1.ravel(), G2.ravel()])
    pg = fig21_predict(r, Xg)
    ptr = fig21_predict(r, X)
    sup = dict(l2=None, l1=np.where(np.abs(r["w1"]) > 1e-8)[0], rvm=r["rvm_keep"][r["rvm_keep"] > 0] - 1, svm=r["svm_sv"])
    names = dict(l2="L2VM", l1="L1VM", rvm="RVM", svm="SVM")
    fig, axes = common.panel_grid(2, 2, size=(3.4, 2.8))
    for k, key in enumerate(["l2", "l1", "rvm", "svm"]):
        ax = axes.ravel()[k]
        _decision_panel(ax, X, y, pg[key].reshape(G1.shape), G1, G2, sup[key], levels=(0,))
        nerr = int(np.sum(np.sign(ptr[key]) != y))
        t = "%s, nerr=%d" % (names[key], nerr)
        if sup[key] is not None:
            t += ", nsupport=%d" % len(sup[key])
        ax.set_title(t, fontsize=9.5)
        common.panel_label(ax, "abcd"[k], "lower left")
    fig.tight_layout()
    savefig(fig, CH, "fig17-21", out)


SINC_GAMMA = 1 / (2 * 0.3 ** 2)
SINC_LAM = 0.5
SINC_EPS = 0.1


def _sinc_fits():
    x, y = noisy_sinc()
    K = rbf(x, x, SINC_GAMMA)
    w2, b2 = ridge_bias(K, y, SINC_LAM)
    w1, b1 = lasso_cd(K, y, SINC_LAM)
    Phi = np.hstack([np.ones((len(x), 1)), K])
    rvm = rvm_regression(Phi, y)
    Cs = np.array([0.1, 0.3, 1.0, 3.0, 10.0, 30.0, 100.0])
    folds = kfold_indices(len(x), 5, 0)
    cv = []
    for C in Cs:
        e = 0.0
        for te in folds:
            tr = np.setdiff1d(np.arange(len(x)), te)
            f = svr_fit(K[np.ix_(tr, tr)], y[tr], C, SINC_EPS, tol=1e-6)
            e += np.sum((K[np.ix_(te, tr)] @ f["beta"] + f["b"] - y[te]) ** 2)
        cv.append(e / len(x))
    C = Cs[int(np.argmin(cv))]
    svr = svr_fit(K, y, C, SINC_EPS)
    return dict(w2=w2, b2=np.array(b2), w1=w1, b1=np.array(b1), rvm_keep=rvm["keep"], rvm_mu=rvm["mu"],
                rvm_beta=np.array(rvm["beta"]), C=np.array(C), Cs=Cs, cv=np.array(cv), svr_beta=svr["beta"],
                svr_b=np.array(svr["b"]), svr_sv=svr["sv"])


def sinc_predict(r, xq):
    x, _ = noisy_sinc()
    Kq = rbf(xq, x, SINC_GAMMA)
    Phi = np.hstack([np.ones((len(xq), 1)), Kq])
    return dict(l2=Kq @ r["w2"] + r["b2"], l1=Kq @ r["w1"] + r["b1"], rvm=Phi[:, r["rvm_keep"]] @ r["rvm_mu"],
                svm=Kq @ r["svr_beta"] + r["svr_b"])


def fig_17_22(out=None):
    """Kernel regression of the noisy sinc function (RBF, sigma = 0.3): L2VM, L1VM, RVM, SVM regression."""
    r = cached("ch17_sinc", _sinc_fits)
    x, y = noisy_sinc()
    xs = np.linspace(-1.5, 1.5, 400)
    p = sinc_predict(r, xs)
    keep = dict(l2=np.arange(len(x)), l1=np.where(np.abs(r["w1"]) > 1e-8)[0],
                rvm=r["rvm_keep"][r["rvm_keep"] > 0] - 1, svm=r["svr_sv"])
    names = dict(l2="L2VM ($\\lambda=0.5$)", l1="L1VM ($\\lambda=0.5$)", rvm="RVM", svm="SVM ($C=%g$)" % float(r["C"]))
    fig, axes = common.panel_grid(2, 2, size=(3.3, 2.5))
    for k, key in enumerate(["l2", "l1", "rvm", "svm"]):
        ax = axes.ravel()[k]
        ax.scatter(x, y, s=8, color=GREY, zorder=2)
        ax.plot(xs, np.sinc(xs), color=GREEN, lw=1, ls=":")
        ax.plot(xs, p[key], color=BLUE, lw=1.6)
        if key != "l2":
            ax.scatter(x[keep[key]], y[keep[key]], s=40, facecolors="none", edgecolors=RED, lw=1.0, zorder=3)
        ax.set_title("%s: %d kept" % (names[key], len(keep[key])), fontsize=9.5)
        ax.set_ylim(-0.45, 1.15)
        common.panel_label(ax, "abcd"[k], "lower left")
    fig.tight_layout()
    savefig(fig, CH, "fig17-22", out)


def fig_17_23(out=None):
    """The coefficients of the four fits of Figure 17.22."""
    r = cached("ch17_sinc", _sinc_fits)
    fig, axes = common.panel_grid(2, 2, size=(3.3, 2.3))
    rv = np.zeros(101)
    rv[r["rvm_keep"]] = r["rvm_mu"]
    data = [("L2VM", r["w2"]), ("L1VM", r["w1"]), ("RVM (index 0 = bias)", rv), ("SVM", r["svr_beta"])]
    for k, (name, w) in enumerate(data):
        ax = axes.ravel()[k]
        idx = np.arange(len(w))
        nz = np.abs(w) > 1e-8
        ax.vlines(idx[nz], 0, w[nz], color=BLUE, lw=0.9)
        ax.plot(idx[nz], w[nz], "o", color=BLUE, ms=2.5)
        ax.axhline(0, color=RED, lw=0.8)
        ax.set_title("%s: %d nonzero" % (name, nz.sum()), fontsize=9.5)
        common.panel_label(ax, "abcd"[k], "lower left")
    fig.tight_layout()
    savefig(fig, CH, "fig17-23", out)


# =========================================================================== supplementary
def fig_17_S1(out=None):
    """Random Fourier features: the kernel estimate with its exact sd, and the Gram-matrix error
    against the number of features for i.i.d., orthogonal and positive features."""
    fig, axes = common.panel_grid(1, 2, size=(3.8, 3.0))
    ax = axes[0, 0]
    r = np.linspace(0, 3.5, 200)
    k = np.exp(-r ** 2 / 2)
    T = 20
    Om = rff_omega(T, 1, 1.0, "iid", seed=3)
    est = (np.cos(np.outer(r, Om[:, 0]))).mean(1)
    sd = np.sqrt(rff_variance(k, T))
    ax.fill_between(r, k - 2 * sd, k + 2 * sd, color=BLUE, alpha=0.2, lw=0, label="exact $\\pm2$ sd")
    ax.plot(r, k, "k", label="RBF kernel")
    ax.plot(r, est, color=RED, label="one draw, $T=20$")
    ax.set_xlabel("$\\|x-x'\\|$ ($\\sigma=1$)")
    ax.legend(fontsize=8)
    common.panel_label(ax, "a", "lower left")
    ax = axes[0, 1]
    rng = np.random.default_rng(0)
    D, N = 8, 100
    X = 0.35 * rng.standard_normal((N, D))
    Kx = np.exp(-0.5 * sqdist(X, X))
    Ms = np.array([8, 16, 32, 64, 128, 256, 512])
    curves = {}
    for kind, fk, lab, c in [("iid", "trig", "i.i.d. trig", BLUE), ("orth", "trig", "orthogonal trig", GREEN), ("iid", "pos", "positive", ORANGE)]:
        errs = []
        for M in Ms:
            T = M // 2 if fk == "trig" else M
            e = []
            for s in range(12):
                Om = rff_omega(T, D, 1.0, kind, seed=100 + s)
                P = random_features(X, Om, fk, 1.0)
                e.append(np.linalg.norm(P @ P.T - Kx) / np.linalg.norm(Kx))
            errs.append(np.mean(e))
        curves[lab] = errs
        ax.loglog(Ms, errs, "o-", color=c, ms=3.5, label=lab)
    ax.loglog(Ms, curves["i.i.d. trig"][0] * np.sqrt(Ms[0] / Ms), "k:", lw=1, label="$\\propto M^{-1/2}$")
    ax.set_xlabel("number of features $M$")
    ax.set_ylabel("relative Gram error")
    ax.legend(fontsize=7.5)
    common.panel_label(ax, "b", "lower left")
    fig.tight_layout()
    savefig(fig, CH, "fig17-S1", out)


def matern_spectral(w, nu, ell=1.0):
    """1-D spectral density of the Matern kernel (normalised so that it integrates to K(0) = 1)."""
    a2 = 2 * nu / ell ** 2
    logc = special.gammaln(nu + 0.5) - special.gammaln(nu) - 0.5 * math.log(math.pi) + nu * math.log(a2)
    return np.exp(logc - (nu + 0.5) * np.log(a2 + w ** 2))


def fig_17_S2(out=None):
    """Matern kernels and their spectral densities for nu = 1/2, 3/2, 5/2, 10 against the SE kernel."""
    fig, axes = common.panel_grid(1, 2, size=(3.7, 2.9))
    r = np.linspace(0, 3, 300)
    w = np.linspace(0, 8, 400)
    cols = [RED, ORANGE, GREEN, PURPLE]
    for nu, c in zip([0.5, 1.5, 2.5, 10.0], cols):
        lab = r"$\nu=%s$" % {0.5: "1/2", 1.5: "3/2", 2.5: "5/2", 10.0: "10"}[nu]
        axes[0, 0].plot(r, matern(r, nu), color=c, label=lab)
        axes[0, 1].semilogy(w, matern_spectral(w, nu), color=c, label=lab)
    axes[0, 0].plot(r, np.exp(-r ** 2 / 2), "k--", label="SE")
    axes[0, 1].semilogy(w, np.exp(-w ** 2 / 2) / math.sqrt(2 * math.pi), "k--", label="SE")
    axes[0, 0].set_xlabel("$r$ ($\\ell=1$)")
    axes[0, 0].set_title("(a) kernels $K(r)$")
    axes[0, 1].set_xlabel("frequency $\\omega$")
    axes[0, 1].set_title("(b) spectral densities $S(\\omega)$")
    axes[0, 1].set_ylim(1e-8, 2)
    axes[0, 0].legend(fontsize=8)
    fig.tight_layout()
    savefig(fig, CH, "fig17-S2", out)


FIGURES = {"17.1": fig_17_1, "17.2": fig_17_2, "17.3": fig_17_3, "17.4": fig_17_4, "17.5": fig_17_5,
           "17.7": fig_17_7, "17.8": fig_17_8, "17.9": fig_17_9, "17.10": fig_17_10, "17.11": fig_17_11,
           "17.14": fig_17_14, "17.15": fig_17_15, "17.17": fig_17_17, "17.18": fig_17_18,
           "17.19": fig_17_19, "17.20": fig_17_20, "17.21": fig_17_21, "17.22": fig_17_22,
           "17.23": fig_17_23, "17.S1": fig_17_S1, "17.S2": fig_17_S2}


# =========================================================================== data for the browser demonstrations
def r4(a, d=4):
    return np.round(np.asarray(a, float), d).tolist()


DEMO_LOGC = np.arange(-7.0, 8.01, 1.0)
DEMO_LOGG = np.arange(-3.0, 3.01, 0.5)
SVM_PRESETS = [("moons", math.log(0.1), math.log(0.001)), ("moons", math.log(0.1), math.log(1000.0)),
               ("moons", math.log(5.0), math.log(0.001)), ("moons", math.log(5.0), math.log(1000.0)),
               ("mixture", 0.0, 0.0)]
RFF_LAM = 0.01


def svm_demo_data():
    """Rounded data, test sets and CV maps for the SVM demonstration, plus reference fits."""
    Xm, ym = moons(**FIG17_MOONS)
    Xmt, ymt = moons(1000, FIG17_MOONS["noise"], FIG17_MOONS["seed"] + 1)
    Xx, yx, d = esl_mixture()
    Xxt = np.array(d["xtest"][:2000])
    yxt = 2 * np.array(d["ytest"][:2000], float) - 1
    sets = {}
    for name, X, y, Xt, yt in [("moons", Xm, ym, Xmt, ymt), ("mixture", Xx, yx, Xxt, yxt)]:
        X, Xt = np.round(X, 4), np.round(Xt, 4)
        E = cached("ch17_cvmap_%s" % name, lambda X=X, y=y: dict(E=svm_cv_grid(X, y, DEMO_LOGC, DEMO_LOGG)))["E"]
        sets[name] = dict(X=X, y=y, Xt=Xt, yt=yt, E=E)
    i, j = np.unravel_index(np.argmin(sets["mixture"]["E"]), sets["mixture"]["E"].shape)
    best = (float(DEMO_LOGG[i]), float(DEMO_LOGC[j]))
    refs = []
    for name, lg, lc in SVM_PRESETS:
        if name == "mixture":
            lg, lc = best
        s = sets[name]
        K = rbf(s["X"], s["X"], math.exp(lg))
        fit = svc_fit(K, s["y"], math.exp(lc), tol=1e-6)
        ftr = K @ fit["coef"] + fit["b"]
        fte = rbf(s["Xt"], s["X"], math.exp(lg)) @ fit["coef"] + fit["b"]
        refs.append(dict(data=name, logG=lg, logC=lc, dual=fit["dual"], nsv=int(len(fit["sv"])),
                         nbound=int(np.sum(fit["alpha"] >= math.exp(lc) * (1 - 1e-9))), b=fit["b"],
                         train_err=float(np.mean(np.sign(ftr) != s["y"])), test_err=float(np.mean(np.sign(fte) != s["yt"]))))
    return sets, refs, d["bayes_rate"]


def rff_demo_reference():
    """Reference numbers for the random-features demonstration (same generator as the browser)."""
    x, y = noisy_sinc()
    x, y = np.round(x, 4), np.round(y, 4)
    xs = np.linspace(-1.5, 1.5, 121)
    out = []
    for M, sigma, kind, seed in [(4, 0.3, "iid", 1), (32, 0.3, "iid", 1), (512, 0.3, "iid", 1), (32, 0.3, "orth", 2), (64, 0.3, "pos", 1)]:
        fk = "pos" if kind == "pos" else "trig"
        T = M if fk == "pos" else M // 2
        Om = rff_omega(T, 1, sigma, "orth" if kind == "orth" else "iid", seed)
        P = random_features(x, Om, fk, sigma)
        Ps = random_features(xs, Om, fk, sigma)
        w = np.linalg.solve(P.T @ P + RFF_LAM * np.eye(P.shape[1]), P.T @ y)
        K = np.exp(-0.5 * sqdist(x[:, None], x[:, None]) / sigma ** 2)
        Ks = np.exp(-0.5 * sqdist(xs[:, None], x[:, None]) / sigma ** 2)
        exact = Ks @ krr_fit(K, y, RFF_LAM)
        approx = Ps @ w
        Kh = P @ P.T
        out.append(dict(M=M, sigma=sigma, kind=kind, seed=seed, omega0=float(Om[0, 0]),
                        gram_rel=float(np.linalg.norm(Kh - K) / np.linalg.norm(K)), gram_max=float(np.abs(Kh - K).max()),
                        fit_rmse=float(np.sqrt(np.mean((approx - exact) ** 2))), exact_at0=float(exact[60]), approx_at0=float(approx[60])))
    return out


def export_json():
    os.makedirs(DATA_OUT, exist_ok=True)
    # 1. GP marginal likelihood
    x9, y9 = fig9_data()
    x8, y8 = fig8_data()
    x9, y9, x8, y8 = (np.round(a, 4) for a in (x9, y9, x8, y8))
    opt9 = fit_se_hyper(x9, y9, [(1.0, 1.0, 0.2), (10.0, 1.0, 0.8)], fix_sf=1.0)
    opt8 = fit_se_hyper(x8, y8, [(1.0, 1.0, 0.1), (3.0, 1.16, 0.89)])
    pts = [(1.0, 1.0, 0.1), (3.0, 1.16, 0.89), (0.35, 1.0, 0.3), (5.0, 1.0, 1.5)]
    ref = dict(opt9=[dict(params=r4(o["params"], 6), logml=o["logml"]) for o in opt9],
               opt8=[dict(params=r4(o["params"], 6), logml=o["logml"]) for o in opt8],
               logml9={"%g_%g_%g" % p: se_logml(np.log(p), x9, y9, grad=False) for p in pts},
               logml8={"%g_%g_%g" % p: se_logml(np.log(p), x8, y8, grad=False) for p in pts},
               grad9_1_1_0p1=r4(se_logml(np.log([1.0, 1.0, 0.1]), x9, y9)[1], 8))
    mu, cov, _ = gp_posterior(x9, y9, np.array([0.0]), lambda A, B: kernel_se(A, B, 1.0), 0.04)
    ref["mean9_at0_1_1_0p2"] = float(mu[0])
    ref["sd9_at0_1_1_0p2"] = float(np.sqrt(cov[0, 0]))
    d1 = dict(fig9=dict(x=x9.tolist(), y=y9.tolist()), fig8=dict(x=x8.tolist(), y=y8.tolist()), ref=ref)
    with open(os.path.join(DATA_OUT, "ch17-gp.json"), "w") as f:
        json.dump(d1, f, separators=(",", ":"))
    # 2. SVM gamma and C
    sets, refs, bayes = svm_demo_data()
    d2 = dict(logC=DEMO_LOGC.tolist(), logG=DEMO_LOGG.tolist(), bayes=bayes, ref=refs, sets={})
    for name, s in sets.items():
        d2["sets"][name] = dict(X=r4(s["X"]), y=[int(v) for v in s["y"]], Xt=r4(s["Xt"]), yt=[int(v) for v in s["yt"]], cv=r4(s["E"], 4))
    with open(os.path.join(DATA_OUT, "ch17-svm.json"), "w") as f:
        json.dump(d2, f, separators=(",", ":"))
    # 3. random features
    x, y = noisy_sinc()
    rng = np.random.default_rng(0)
    cloud = 0.35 * rng.standard_normal((50, 16))
    d3 = dict(x=r4(x), y=r4(y), lam=RFF_LAM, cloud=r4(cloud), ref=rff_demo_reference())
    with open(os.path.join(DATA_OUT, "ch17-rff.json"), "w") as f:
        json.dump(d3, f, separators=(",", ":"))
    print("wrote ch17-*.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()
