"""Chapter 5 of Hastie, Tibshirani and Friedman (2009), The Elements of Statistical Learning:
"Basis Expansions and Regularization". Every figure of the chapter is reproduced from scratch.

usage:
    python3 ch05_basis_expansions.py            # all figures
    python3 ch05_basis_expansions.py --fig 5.7  # one figure
    python3 ch05_basis_expansions.py --list

What is implemented here (no spline or wavelet library is used for the figures):

* spline bases: the truncated power basis, B-splines by the Cox-de Boor recursion (with
  derivatives), natural cubic splines both in the form (5.4)-(5.5) and as B-splines with the
  natural boundary constraints projected out (the construction behind R's ns());
* the cubic smoothing spline by the Reinsch algorithm (Q and R matrices, penalty matrix K,
  ties handled by weights), its smoother matrix, the Demmler-Reinsch eigen-decomposition,
  effective degrees of freedom, df -> lambda inversion, the leave-one-out shortcut (5.27) and
  generalised cross-validation, and evaluation of the fitted natural spline anywhere;
* logistic regression by iteratively reweighted least squares, with an optional quadratic
  penalty (used for the natural-spline models of Sections 5.2.2 and 5.2.3, the tensor-product
  models of Figure 5.11, and the penalised Newton update (5.33)-(5.34) of Section 5.6);
* a low-rank thin-plate spline on a lattice of knots (Section 5.7);
* Gaussian-kernel eigen-analysis and the Nystrom extension of the eigenvectors (Section 5.8);
* orthonormal wavelets: the Daubechies symmlet-8 filter derived by spectral factorisation,
  the periodised pyramid algorithm (forward and inverse, O(N)), the cascade algorithm for
  the scaling function and wavelet, soft thresholding and SureShrink (Section 5.9).

Figures reproduced: 5.1 to 5.20 (all twenty), plus two supplementary figures:
  5.S1  mean and pointwise quantiles of the smoothing spline (Exercise 5.10);
  5.S2  nonparametric logistic regression (Section 5.6) on the heart disease data.
Data notes: Figures 5.17 and 5.19 (top) use a nuclear magnetic resonance spectrum that is not
distributed with the book's data sets; a synthetic spectrum of the same kind (smooth baseline,
isolated sharp peaks, noise; N = 1024) is used instead. Figure 5.1 and 5.2 use artificial
data, as in the book, from a function of our own choice. No figure is skipped.
"""
import os

for _v in ("OPENBLAS_NUM_THREADS", "MKL_NUM_THREADS", "OMP_NUM_THREADS"):
    os.environ.setdefault(_v, "1")

import itertools
import json
from math import comb

import numpy as np
from scipy import linalg, optimize, stats
import matplotlib.pyplot as plt
from matplotlib.colors import LinearSegmentedColormap

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

CH = 5
HERE = os.path.dirname(os.path.abspath(__file__))
CACHE_DIR = os.path.join(HERE, "cache")
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
YELLOW = "#f5d76e"


# =========================================================================== spline bases
def tpower_basis(x, knots, M=4):
    """Truncated power basis of order M (degree M-1): 1, x, ..., x^(M-1), (x - xi_l)_+^(M-1).

    For M = 1 the truncated term is the step I(x >= xi_l)."""
    x = np.asarray(x, float)
    cols = [x ** j for j in range(M)]
    for k in knots:
        cols.append((x >= k).astype(float) if M == 1 else np.maximum(x - k, 0.0) ** (M - 1))
    return np.column_stack(cols)


def augmented_knots(interior, lo, hi, M):
    """The knot sequence tau of the Appendix: M copies of each boundary knot around the interior."""
    return np.r_[[lo] * M, np.asarray(interior, float), [hi] * M]


def _bs_rec(x, t, m, d):
    """Order-m B-splines (or their d-th derivatives) on the knot sequence t, by Cox-de Boor."""
    nt = len(t)
    if d == 0 and m == 1:
        B = np.zeros((len(x), nt - 1))
        nonempty = [i for i in range(nt - 1) if t[i] < t[i + 1]]
        for i in nonempty:
            B[:, i] = (x >= t[i]) & (x < t[i + 1])
        last = nonempty[-1]
        B[x == t[last + 1], last] = 1.0          # close the last interval on the right
        return B
    Bm = _bs_rec(x, t, m - 1, max(d - 1, 0) if d > 0 else 0)
    out = np.zeros((len(x), nt - m))
    for i in range(nt - m):
        d1, d2 = t[i + m - 1] - t[i], t[i + m] - t[i + 1]
        a = Bm[:, i] / d1 if d1 > 0 else 0.0
        b = Bm[:, i + 1] / d2 if d2 > 0 else 0.0
        if d > 0:                                 # derivative recursion
            out[:, i] = (m - 1) * (a - b)
        else:                                     # (5.78)
            out[:, i] = (x - t[i]) * a + (t[i + m] - x) * b
    return out


def bspline_basis(x, interior, lo, hi, M=4, deriv=0):
    """N x (K+M) matrix of the order-M B-splines B_{i,M} (5.77)-(5.78) for interior knots `interior`
    and boundary knots lo < hi, or of their `deriv`-th derivatives. Zero outside [lo, hi]."""
    x = np.atleast_1d(np.asarray(x, float))
    t = augmented_knots(interior, lo, hi, M)
    if deriv >= M:
        return np.zeros((len(x), len(t) - M))
    return _bs_rec(x, t, M, deriv)


def ns_basis(x, interior, lo, hi, intercept=False):
    """Natural cubic spline basis: cubic B-splines with the two constraints f''(lo) = f''(hi) = 0
    projected out (an orthonormal basis of the null space of the constraint matrix, as in R's ns()).
    K interior knots give K + 2 functions (K + 1 without the intercept). Linear beyond the boundary."""
    x = np.atleast_1d(np.asarray(x, float))
    xc = np.clip(x, lo, hi)
    B = bspline_basis(xc, interior, lo, hi, 4)
    C = bspline_basis([lo, hi], interior, lo, hi, 4, deriv=2)
    if not intercept:
        B, C = B[:, 1:], C[:, 1:]
    Q, _ = np.linalg.qr(C.T, mode="complete")
    Z = Q[:, 2:]
    out = B @ Z
    for side, b in ((x < lo, lo), (x > hi, hi)):
        if side.any():                              # linear extrapolation
            D1 = bspline_basis([b], interior, lo, hi, 4, deriv=1)
            if not intercept:
                D1 = D1[:, 1:]
            out[side] = (bspline_basis([b], interior, lo, hi, 4)[:, (0 if intercept else 1):] @ Z
                         + (x[side] - b)[:, None] * (D1 @ Z))
    return out


def ns_quantile(x, df, intercept=False):
    """ns(x, df=df): df - 1 + intercept interior knots at equally spaced quantiles of x,
    boundary knots at the range of x. Returns (basis matrix, (interior, lo, hi))."""
    x = np.asarray(x, float)
    nint = df - 1 + int(intercept)
    probs = np.linspace(0, 1, nint + 2)[1:-1]
    interior = np.quantile(x, probs)
    lo, hi = x.min(), x.max()
    return ns_basis(x, interior, lo, hi, intercept), (interior, lo, hi)


def ncs_basis_tp(x, knots):
    """The natural cubic spline basis (5.4)-(5.5): N1 = 1, N2 = X, N_{k+2} = d_k - d_{K-1}."""
    x = np.asarray(x, float)
    xi = np.asarray(knots, float)
    K = len(xi)

    def dk(k):
        return (np.maximum(x - xi[k], 0) ** 3 - np.maximum(x - xi[K - 1], 0) ** 3) / (xi[K - 1] - xi[k])
    cols = [np.ones_like(x), x] + [dk(k) - dk(K - 2) for k in range(K - 2)]
    return np.column_stack(cols)


# =========================================================================== smoothing splines
def reinsch_QR(t):
    """Q (n x (n-2)) and R ((n-2) x (n-2)) of Green and Silverman (1994) for sorted distinct t:
    the natural cubic spline with values g has second derivatives gamma = R^{-1} Q^T g at the
    interior knots, and int g''^2 = g^T K g with K = Q R^{-1} Q^T."""
    t = np.asarray(t, float)
    n = len(t)
    h = np.diff(t)
    Q = np.zeros((n, n - 2))
    R = np.zeros((n - 2, n - 2))
    for j in range(1, n - 1):
        c = j - 1
        Q[j - 1, c] = 1.0 / h[j - 1]
        Q[j, c] = -1.0 / h[j - 1] - 1.0 / h[j]
        Q[j + 1, c] = 1.0 / h[j]
        R[c, c] = (h[j - 1] + h[j]) / 3.0
        if c + 1 < n - 2:
            R[c, c + 1] = R[c + 1, c] = h[j] / 6.0
    return Q, R


def ncs_eval(t, g, gamma_int, x0):
    """Evaluate at x0 the natural cubic spline with knots t, values g and interior second
    derivatives gamma_int (gamma_1 = gamma_n = 0); linear beyond the boundary knots."""
    t = np.asarray(t, float)
    g = np.asarray(g, float)
    n = len(t)
    gam = np.r_[0.0, gamma_int, 0.0]
    h = np.diff(t)
    x0 = np.atleast_1d(np.asarray(x0, float))
    out = np.empty(len(x0))
    i = np.clip(np.searchsorted(t, x0, side="right") - 1, 0, n - 2)
    inside = (x0 >= t[0]) & (x0 <= t[-1])
    xi, hi = x0[inside], h[i[inside]]
    a, b = xi - t[i[inside]], t[i[inside] + 1] - xi
    gi, gi1 = g[i[inside]], g[i[inside] + 1]
    ci, ci1 = gam[i[inside]], gam[i[inside] + 1]
    out[inside] = (a * gi1 + b * gi) / hi - a * b / 6.0 * ((1 + a / hi) * ci1 + (1 + b / hi) * ci)
    left, right = x0 < t[0], x0 > t[-1]
    d0 = (g[1] - g[0]) / h[0] - h[0] * gam[1] / 6.0
    dn = (g[-1] - g[-2]) / h[-1] + h[-1] * gam[-2] / 6.0
    out[left] = g[0] + (x0[left] - t[0]) * d0
    out[right] = g[-1] + (x0[right] - t[-1]) * dn
    return out


class SmoothingSpline:
    """Cubic smoothing spline for data (x_i, y_i) with optional weights, minimising
    sum_i w_i (y_i - f(x_i))^2 + lam * int f''(t)^2 dt (5.9)/(5.73).

    Tied x values are merged: the unique values carry the summed weights and the weighted mean
    responses (Exercise 5.12). The fit lives on the n unique values t_1 < ... < t_n."""

    def __init__(self, x, y, w=None):
        x = np.asarray(x, float)
        y = np.asarray(y, float)
        w = np.ones_like(x) if w is None else np.asarray(w, float)
        self.x, self.y, self.w = x, y, w
        t, inv = np.unique(x, return_inverse=True)
        self.t, self.inv = t, inv
        W = np.bincount(inv, weights=w)
        self.W = W
        self.ybar = np.bincount(inv, weights=w * y) / W
        self.Q, self.R = reinsch_QR(t)
        self.K = self.Q @ np.linalg.solve(self.R, self.Q.T)
        self.K = 0.5 * (self.K + self.K.T)
        # Demmler-Reinsch: eigen-decomposition of W^{-1/2} K W^{-1/2}
        s = 1.0 / np.sqrt(W)
        d, U = np.linalg.eigh(s[:, None] * self.K * s[None, :])
        d[:2] = 0.0                                   # the two null directions (linear functions)
        self.d, self.U = np.maximum(d, 0.0), U

    @property
    def n(self):
        return len(self.t)

    def df(self, lam):
        return float(np.sum(1.0 / (1.0 + lam * self.d)))

    def lam_for_df(self, df):
        """lambda with trace(S_lambda) = df, by root finding on log lambda (df is monotone)."""
        if not 2.0 < df < self.n:
            raise ValueError("df must lie in (2, n)")
        f = lambda ll: self.df(np.exp(ll)) - df
        lo, hi = -60.0, 60.0
        return float(np.exp(optimize.brentq(f, lo, hi, xtol=1e-13, rtol=1e-14, maxiter=500)))

    def smoother(self, lam):
        """n x n smoother on the unique values: g = S ybar, S = (W + lam K)^{-1} W."""
        return np.linalg.solve(np.diag(self.W) + lam * self.K, np.diag(self.W))

    def fit(self, lam):
        """Fitted values g at the unique x and the interior second derivatives gamma."""
        g = np.linalg.solve(np.diag(self.W) + lam * self.K, self.W * self.ybar)
        gamma = np.linalg.solve(self.R, self.Q.T @ g)
        return g, gamma

    def predict(self, lam, x0):
        g, gamma = self.fit(lam)
        return ncs_eval(self.t, g, gamma, x0)

    def operator_at(self, lam, x0):
        """Matrix L (len(x0) x n) with fhat(x0) = L @ ybar (the equivalent kernels at x0)."""
        S = self.smoother(lam)
        G = np.linalg.solve(self.R, self.Q.T @ S)
        return np.column_stack([ncs_eval(self.t, S[:, j], G[:, j], x0) for j in range(self.n)])

    def fitted_full(self, lam):
        g, _ = self.fit(lam)
        return g[self.inv]

    def leverages(self, lam):
        """Diagonal S_lambda(i, i) of the smoother acting on the N original observations."""
        A = np.linalg.inv(np.diag(self.W) + lam * self.K)
        return np.diag(A)[self.inv] * self.w

    def loocv(self, lam):
        """Leave-one-out CV (5.27), computed from one fit (Exercise 5.13)."""
        r = (self.y - self.fitted_full(lam)) / (1.0 - self.leverages(lam))
        return float(np.mean(self.w * r ** 2) / np.mean(self.w))

    def gcv(self, lam):
        r = self.y - self.fitted_full(lam)
        N = len(self.y)
        return float(np.mean(r ** 2) / (1.0 - self.df(lam) / N) ** 2)

    def eig(self, lam):
        """Eigenvalues rho_k (descending) and eigenvectors (columns, as functions of t) of S."""
        rho = 1.0 / (1.0 + lam * self.d)
        V = self.U / np.sqrt(self.W)[:, None]
        V = V / np.linalg.norm(V, axis=0)
        return rho, V


def smoothing_spline_brute(x, y, lam):
    """Direct solution of (5.11)-(5.12) in the natural-spline basis (5.4)-(5.5) with knots at
    the (distinct) x, with Omega_N computed by exact quadrature. Used to confirm the Reinsch
    algorithm; only sensible for small N (the truncated power basis is ill conditioned)."""
    t = np.sort(np.asarray(x, float))
    N = ncs_basis_tp(t, t)
    Om = omega_ncs(t)
    theta = np.linalg.solve(N.T @ N + lam * Om, N.T @ y[np.argsort(x)])
    return N @ theta, theta


def omega_ncs(t):
    """{Omega_N}_jk = int N_j'' N_k'' for the basis (5.4)-(5.5): the second derivatives are
    piecewise linear, so Simpson's rule on each knot interval is exact."""
    t = np.asarray(t, float)
    K = len(t)

    def d2(x):
        def dk2(k):
            return 6 * (np.maximum(x - t[k], 0) - np.maximum(x - t[K - 1], 0)) / (t[K - 1] - t[k])
        return np.column_stack([np.zeros_like(x), np.zeros_like(x)] + [dk2(k) - dk2(K - 2) for k in range(K - 2)])
    Om = np.zeros((K, K))
    for a, b in zip(t[:-1], t[1:]):
        xs = np.array([a, 0.5 * (a + b), b])
        D = d2(xs)
        wts = (b - a) / 6.0 * np.array([1.0, 4.0, 1.0])
        Om += D.T @ (wts[:, None] * D)
    return Om


def smoothing_spline_bspline(x, y, lam):
    """The B-spline route of the Appendix / Exercise 5.8: N + 2 cubic B-splines with the N - 2
    interior data points as knots, Omega_B by Gauss-Legendre quadrature (exact), and
    gamma = (B^T B + lam Omega_B)^{-1} B^T y (5.79). Returns fitted values at sorted x."""
    t = np.sort(np.asarray(x, float))
    ys = np.asarray(y, float)[np.argsort(x)]
    interior, lo, hi = t[1:-1], t[0], t[-1]
    B = bspline_basis(t, interior, lo, hi, 4)
    gx, gw = np.polynomial.legendre.leggauss(3)
    Om = np.zeros((B.shape[1], B.shape[1]))
    for a, b in zip(t[:-1], t[1:]):
        xs = 0.5 * (b - a) * gx + 0.5 * (a + b)
        D = bspline_basis(xs, interior, lo, hi, 4, deriv=2)
        Om += D.T @ ((0.5 * (b - a) * gw)[:, None] * D)
    gam = np.linalg.solve(B.T @ B + lam * Om, B.T @ ys)
    return B @ gam, B, Om


# =========================================================================== logistic regression
def logistic_irls(H, y, P=None, tol=1e-10, maxit=100):
    """Logistic regression by Newton-Raphson / IRLS. H includes any intercept column.
    With a penalty matrix P the criterion is loglik - theta^T P theta / 2 (as in (5.30)-(5.33)).
    Returns theta, the inverse Hessian, the deviance -2 loglik and the number of iterations."""
    H = np.asarray(H, float)
    y = np.asarray(y, float)
    p = H.shape[1]
    P = np.zeros((p, p)) if P is None else P
    theta = np.zeros(p)
    dev_old = np.inf
    for it in range(1, maxit + 1):
        eta = H @ theta
        mu = common.sigmoid(eta)
        w = np.maximum(mu * (1 - mu), 1e-12)
        z = eta + (y - mu) / w                                  # working response
        A = H.T @ (w[:, None] * H) + P
        theta = np.linalg.solve(A, H.T @ (w * z))               # (5.33)
        eta = H @ theta
        dev = -2 * np.sum(y * eta - np.logaddexp(0, eta))
        if abs(dev_old - dev) < tol * (1 + abs(dev)):
            break
        dev_old = dev
    mu = common.sigmoid(H @ theta)
    w = mu * (1 - mu)
    cov = np.linalg.inv(H.T @ (w[:, None] * H) + P)
    return theta, cov, float(dev), it


def nonparametric_logistic(x, y, df=None, lam=None, maxit=50, tol=1e-10):
    """Penalised logistic regression (5.30) by the local scoring update (5.34): each Newton step
    is a weighted smoothing spline of the working response z. Returns (spline object, lam, f at
    unique x, number of steps). With df given, lam is re-chosen at each step to keep
    trace(S_{lam,w}) = df, which is how df-specified fits are usually computed."""
    x = np.asarray(x, float)
    y = np.asarray(y, float)
    t, inv = np.unique(x, return_inverse=True)
    f = np.full(len(x), np.log(y.mean() / (1 - y.mean())))
    for it in range(1, maxit + 1):
        p = common.sigmoid(f)
        w = p * (1 - p)
        z = f + (y - p) / w
        ss = SmoothingSpline(x, z, w)
        lam_it = ss.lam_for_df(df) if df is not None else lam
        fnew = ss.fitted_full(lam_it)
        if np.max(np.abs(fnew - f)) < tol:
            f = fnew
            break
        f = fnew
    return ss, lam_it, f, it


# =========================================================================== thin-plate splines
def tps_eta(r):
    """The radial function r^2 log r of (5.39) and (5.66) (0 at r = 0)."""
    r = np.asarray(r, float)
    out = np.zeros_like(r)
    m = r > 0
    out[m] = r[m] ** 2 * np.log(r[m])
    return out


class ThinPlate:
    """Low-rank thin-plate spline in two dimensions with knots kappa_1..kappa_K:
    f(x) = b0 + b^T x + sum_k a_k eta(||x - kappa_k||), with T_kappa^T a = 0 (Exercise 5.14) and
    penalty J(f) = a^T E a (E_kl = eta(||kappa_k - kappa_l||), up to the constant 8 pi absorbed
    in lambda). The constraint is removed by a = Z c with Z a basis of the null space of T^T."""

    def __init__(self, X, y, knots):
        self.X, self.y, self.knots = np.asarray(X, float), np.asarray(y, float), np.asarray(knots, float)
        Tk = np.column_stack([np.ones(len(knots)), knots])
        Qf, _ = np.linalg.qr(Tk, mode="complete")
        self.Z = Qf[:, 3:]
        self.D = self.design(self.X)
        E = tps_eta(np.linalg.norm(knots[:, None, :] - knots[None, :, :], axis=2))
        Om = np.zeros((self.D.shape[1],) * 2)
        Om[3:, 3:] = self.Z.T @ E @ self.Z
        self.Om = 0.5 * (Om + Om.T)

    def design(self, X):
        X = np.asarray(X, float)
        E = tps_eta(np.linalg.norm(X[:, None, :] - self.knots[None, :, :], axis=2))
        return np.column_stack([np.ones(len(X)), X, E @ self.Z])

    def fit(self, lam):
        A = self.D.T @ self.D + lam * self.Om
        self.coef = np.linalg.solve(A, self.D.T @ self.y)
        return self.coef

    def df(self, lam):
        A = self.D.T @ self.D + lam * self.Om
        return float(np.trace(np.linalg.solve(A, self.D.T @ self.D)))

    def lam_for_df(self, df):
        f = lambda ll: self.df(np.exp(ll)) - df
        return float(np.exp(optimize.brentq(f, -30, 40, xtol=1e-12)))

    def predict(self, X):
        return self.design(X) @ self.coef


def convex_hull_mask(P, hull_pts):
    """Boolean mask of the points P inside the convex hull of hull_pts."""
    from scipy.spatial import Delaunay
    return Delaunay(hull_pts).find_simplex(P) >= 0


# =========================================================================== wavelets
def daubechies_filter(p, symmlet=True):
    """Low-pass filter h (length 2p, sum sqrt 2) of the Daubechies wavelet with p vanishing moments,
    by spectral factorisation: |H(w)|^2 = 2 cos^{2p}(w/2) P(sin^2(w/2)), P(y) = sum_{k<p} C(p-1+k, k) y^k.
    Each root of P gives a reciprocal pair of z-roots; the extremal-phase choice keeps the roots
    inside the unit circle, the symmlet choice picks the combination whose phase is closest to linear."""
    c = [comb(p - 1 + k, k) for k in range(p)]
    yr = np.roots(c[::-1]) if p > 1 else np.array([])
    zin = []
    for y in yr:
        zz = np.roots([1, -(2 - 4 * y), 1])
        zin.append(zz[np.argmin(np.abs(zz))])
    groups, used = [], set()
    for i, z in enumerate(zin):
        if i in used:
            continue
        if abs(z.imag) < 1e-10:
            groups.append([i]); used.add(i); continue
        j = min((j for j in range(len(zin)) if j not in used and j != i), key=lambda j: abs(zin[j] - np.conj(z)))
        groups.append([i, j]); used |= {i, j}

    def build(choice):
        h = np.array([1.0 + 0j])
        for _ in range(p):
            h = np.convolve(h, [1, 1])
        for g, ch in zip(groups, choice):
            for i in g:
                h = np.convolve(h, [1, -(zin[i] if ch == 0 else 1 / zin[i])])
        h = np.real(h)
        return h * np.sqrt(2) / h.sum()
    if not symmlet:
        return build([0] * len(groups))
    w = np.linspace(0, np.pi, 512)[1:-1]
    best = None
    for choice in itertools.product([0, 1], repeat=len(groups)):
        h = build(choice)
        H = np.exp(-1j * np.outer(w, np.arange(len(h)))) @ h
        ph = np.unwrap(np.angle(H))
        A = np.column_stack([w, np.ones_like(w)])
        res = ph - A @ np.linalg.lstsq(A, ph, rcond=None)[0]
        s = float(res @ res)
        if best is None or s < best[0] - 1e-12:
            best = (s, h)
    return best[1]


HAAR = np.array([1.0, 1.0]) / np.sqrt(2)


def wavelet_filters(name):
    h = HAAR if name == "haar" else daubechies_filter(8, symmlet=True)
    L = len(h)
    g = np.array([(-1) ** (k + 1) * h[L - 1 - k] for k in range(L)])
    return h, g


def dwt_step(a, h, g):
    """One level of the periodised pyramid: approximation and detail of length N/2 (O(N))."""
    N, L = len(a), len(h)
    idx = (2 * np.arange(N // 2)[:, None] + L // 2 - np.arange(L)[None, :]) % N
    return a[idx] @ h, a[idx] @ g


def idwt_step(ca, cd, h, g):
    N, L = 2 * len(ca), len(h)
    out = np.zeros(N)
    k = np.arange(N // 2)
    for n in range(L):
        np.add.at(out, (2 * k + L // 2 - n) % N, h[n] * ca + g[n] * cd)
    return out


def dwt(y, name="sym8", j0=0):
    """Wavelet transform y* = W^T y down to level j0 (2^j0 scaling coefficients).
    Returns [V_j0, W_j0, W_{j0+1}, ..., W_{J-1}] as a list of arrays."""
    h, g = wavelet_filters(name)
    a = np.asarray(y, float)
    J = int(round(np.log2(len(a))))
    details = []
    for _ in range(J - j0):
        a, d = dwt_step(a, h, g)
        details.append(d)
    return [a] + details[::-1]


def idwt(coefs, name="sym8"):
    h, g = wavelet_filters(name)
    a = coefs[0]
    for d in coefs[1:]:
        a = idwt_step(a, d, h, g)
    return a


def wavelet_vector(N, j, k, name="sym8", j0=0, father=False):
    """Column of W: the discrete wavelet psi_{j,k} (or scaling function phi_{j,k}) on N points."""
    J = int(round(np.log2(N)))
    coefs = [np.zeros(2 ** j0)] + [np.zeros(2 ** jj) for jj in range(j0, J)]
    if father:
        coefs[0][k] = 1.0
    else:
        coefs[1 + j - j0][k] = 1.0
    return idwt(coefs, name)


def cascade(h, levels=10):
    """Scaling function phi and wavelet psi on [0, L-1] by the cascade (subdivision) algorithm:
    phi is the limit of S^n(delta), with S(c) = sqrt2 (upsampled c) * h, and psi = S^(n-1)(sqrt2 g),
    since psi(x) = sqrt2 sum_k g_k phi(2x - k). Values on the grid j / 2^levels."""
    L = len(h)
    g = np.array([(-1) ** (k + 1) * h[L - 1 - k] for k in range(L)])

    def S(c):
        up = np.zeros(2 * len(c) - 1)
        up[::2] = c
        return np.sqrt(2) * np.convolve(up, h)
    phi, psi = np.array([1.0]), np.sqrt(2) * g
    for i in range(levels):
        phi = S(phi)
        if i < levels - 1:
            psi = S(psi)
    x = np.arange(len(phi)) / 2.0 ** levels
    return x, phi, psi[: len(phi)]


def soft(z, lam):
    return np.sign(z) * np.maximum(np.abs(z) - lam, 0.0)


def sure_threshold(y, sigma):
    """SureShrink threshold for one level (Donoho and Johnstone 1995): minimise Stein's unbiased
    risk estimate SURE(t) = n - 2 #{|x_i| <= t} + sum min(|x_i|, t)^2 for x = y/sigma over
    t in [0, sqrt(2 log n)], with the hybrid rule that uses the universal threshold when the
    level is very sparse. Returns the threshold on the scale of y."""
    x = np.abs(np.asarray(y, float)) / sigma
    n = len(x)
    univ = np.sqrt(2 * np.log(n))
    eta = (np.sum(x ** 2) - n) / n
    crit = np.log2(n) ** 1.5 / np.sqrt(n)
    if eta <= crit:
        return sigma * univ
    xs = np.sort(x)
    cand = np.r_[0.0, xs[xs <= univ]]
    risks = [n - 2 * np.sum(x <= t) + np.sum(np.minimum(x, t) ** 2) for t in cand]
    return sigma * float(cand[int(np.argmin(risks))])


def mad_sigma(d):
    return float(np.median(np.abs(d - np.median(d))) / 0.6745)


def hard(z, lam):
    return np.where(np.abs(z) > lam, z, 0.0)


def wavelet_shrink(y, name="sym8", j0=4, rule="sure", lam=None, mode="soft"):
    """Wavelet smoothing: transform, threshold (soft by default, or hard) the detail coefficients of
    levels j0..J-1 (the 2^j0 coarse scaling coefficients are kept), invert. sigma from the finest
    level (MAD); lam, if given, is the threshold in units of sigma."""
    c = dwt(y, name, j0)
    sigma = mad_sigma(c[-1])
    out = [c[0].copy()]
    lams = []
    for d in c[1:]:
        if lam is not None:
            t = lam * sigma
        elif rule == "universal":
            t = sigma * np.sqrt(2 * np.log(len(y)))
        else:
            t = sure_threshold(d, sigma)
        lams.append(t)
        out.append(soft(d, t) if mode == "soft" else hard(d, t))
    return idwt(out, name), c, out, sigma, lams


def nmr_like_signal(N=1024):
    """A synthetic stand-in for the NMR spectrum of Figures 5.17 and 5.19: a slowly varying
    baseline, a broad hump and isolated sharp Lorentzian peaks (the true signal, without noise)."""
    t = np.arange(N) / N
    base = -8 + 4 * np.exp(-((t - 0.45) / 0.09) ** 2) + 14 * np.exp(-((t - 0.47) / 0.06) ** 2) \
        + 4 * np.exp(-((t - 0.70) / 0.05) ** 2) + 3 * t
    peaks = [(0.38, 10, 0.004), (0.42, 14, 0.003), (0.46, 12, 0.002), (0.475, 45, 0.0012),
             (0.52, 9, 0.003), (0.56, 12, 0.003), (0.60, 10, 0.004), (0.66, 6, 0.004), (0.77, 6, 0.003)]
    for c0, a, w in peaks:
        base = base + a / (1 + ((t - c0) / w) ** 2)
    return base


def dj_signal(name, N=1024):
    """Test functions of Donoho and Johnstone (1994) on t = i/N."""
    t = np.arange(1, N + 1) / N
    tj = np.array([.1, .13, .15, .23, .25, .40, .44, .65, .76, .78, .81])
    if name == "bumps":
        hj = np.array([4, 5, 3, 4, 5, 4.2, 2.1, 4.3, 3.1, 5.1, 4.2])
        wj = np.array([.005, .005, .006, .01, .01, .03, .01, .01, .005, .008, .005])
        return np.sum(hj[:, None] * (1 + np.abs((t[None, :] - tj[:, None]) / wj[:, None])) ** -4, axis=0)
    if name == "blocks":
        hj = np.array([4, -5, 3, -4, 5, -4.2, 2.1, 4.3, -3.1, 2.1, -4.2])
        return np.sum(hj[:, None] * (1 + np.sign(t[None, :] - tj[:, None])) / 2, axis=0)
    if name == "heavisine":
        return 4 * np.sin(4 * np.pi * t) - np.sign(t - 0.3) - np.sign(0.72 - t)
    if name == "doppler":
        return np.sqrt(t * (1 - t)) * np.sin(2 * np.pi * 1.05 / (t + 0.05))
    raise ValueError(name)


# =========================================================================== data
def f522(x):
    """The test function (5.22)."""
    return np.sin(12 * (x + 0.2)) / (x + 0.2)


def sim_522(N=100, seed=5):
    rng = np.random.default_rng(seed)
    x = np.sort(rng.uniform(0, 1, N))
    y = f522(x) + rng.normal(0, 1, N)
    return x, y


def f_artificial(x):
    """Smooth function behind the artificial data of Figures 5.1 and 5.2 (our choice)."""
    return 0.55 + 0.45 * np.cos(1.75 * np.pi * (x - 0.05)) + 0.15 * x


def artificial_data(N=50, seed=11):
    rng = np.random.default_rng(seed)
    x = np.sort(rng.uniform(0, 1, N))
    y = f_artificial(x) + rng.normal(0, 0.2, N)
    return x, y


def ozone_data():
    d = common.esl_data("LAozone.data")
    return d.dpg.to_numpy(float), d.ozone.to_numpy(float)


def bone_data():
    d = common.esl_data("bone.data")
    return d


def saheart():
    d = common.esl_data("SAheart.data")
    d["famhist"] = (d["famhist"] == "Present").astype(float)
    return d


def phoneme_aa_ao(seed=1):
    """aa and ao log-periodograms; a random training sample of 1000 and the rest as test set."""
    d = common.esl_data("phoneme.data")
    d = d[d.g.isin(["aa", "ao"])].reset_index(drop=True)
    X = d[["x.%d" % i for i in range(1, 257)]].to_numpy(float)
    y = (d.g == "aa").to_numpy(float)
    rng = np.random.default_rng(seed)
    perm = rng.permutation(len(y))
    tr, te = perm[:1000], perm[1000:]
    return X, y, tr, te


def mixture():
    """The simulated mixture data of Chapter 2 (ESL.mixture.rda, exported once with Rscript)."""
    path = os.path.join(CACHE_DIR, "ch05_mixture.npz")
    if not os.path.exists(path):
        import subprocess
        import tempfile
        os.makedirs(CACHE_DIR, exist_ok=True)
        rda = common.esl_file("ESL.mixture.rda")
        tmp = tempfile.mkdtemp()
        code = ('load("%s"); m <- ESL.mixture; for (nm in c("x","y","xnew","prob","marginal","px1","px2","means")) '
                'write.table(as.matrix(m[[nm]]), file.path("%s", paste0(nm, ".csv")), sep=",", row.names=FALSE, col.names=FALSE)'
                % (rda, tmp))
        subprocess.check_call(["/usr/local/bin/Rscript", "-e", code])
        arrs = {nm: np.loadtxt(os.path.join(tmp, nm + ".csv"), delimiter=",")
                for nm in ("x", "y", "xnew", "prob", "marginal", "px1", "px2", "means")}
        np.savez(path, **arrs)
    z = np.load(path)
    return {k: z[k] for k in z.files}


def mixture_errors(pred_fn, m):
    """Training error, test error (integrated over the true marginal density on the grid) and
    the Bayes error for a classifier pred_fn(X) -> {0,1}."""
    tr = float(np.mean(pred_fn(m["x"]) != m["y"]))
    pg = pred_fn(m["xnew"])
    wts = m["marginal"] / m["marginal"].sum()
    test = float(np.sum(wts * np.where(pg == 1, 1 - m["prob"], m["prob"])))
    bayes = float(np.sum(wts * np.minimum(m["prob"], 1 - m["prob"])))
    return tr, test, bayes


# =========================================================================== small plotting helpers
def rug(ax, x, color="k", h=0.03):
    ylo, yhi = ax.get_ylim()
    ax.vlines(x, ylo, ylo + h * (yhi - ylo), color=color, lw=0.5)
    ax.set_ylim(ylo, yhi)


def knot_lines(ax, knots):
    for k in knots:
        ax.axvline(k, color="k", ls="--", lw=0.8)


# =========================================================================== Figures 5.1 - 5.3
def fig_5_1(out=None):
    """Piecewise constant and piecewise linear fits, and a piecewise-linear basis function."""
    x, y = artificial_data()
    k1, k2 = 1 / 3, 2 / 3
    grid = np.linspace(0, 1, 401)
    I1 = lambda v: (v < k1).astype(float)
    I2 = lambda v: ((v >= k1) & (v < k2)).astype(float)
    I3 = lambda v: (v >= k2).astype(float)
    Hc = lambda v: np.column_stack([I1(v), I2(v), I3(v)])
    Hl = lambda v: np.column_stack([Hc(v), Hc(v) * v[:, None]])
    Hcl = lambda v: np.column_stack([np.ones_like(v), v, np.maximum(v - k1, 0), np.maximum(v - k2, 0)])
    fig, axes = common.panel_grid(2, 2, size=(3.4, 2.7))
    titles = ["Piecewise Constant", "Piecewise Linear", "Continuous Piecewise Linear", "Piecewise-linear Basis Function"]
    for ax, H, tt in zip(axes.flat[:3], (Hc, Hl, Hcl), titles):
        beta = np.linalg.lstsq(H(x), y, rcond=None)[0]
        ax.axvspan(0, k1, color=YELLOW, alpha=0.45, lw=0)
        ax.axvspan(k1, k2, color="#c9b458", alpha=0.45, lw=0)
        ax.axvspan(k2, 1, color=YELLOW, alpha=0.45, lw=0)
        ax.plot(grid, f_artificial(grid), color=BLUE)
        fit = H(grid) @ beta
        if H is Hc or H is Hl:
            for lo, hi in ((0, k1), (k1, k2), (k2, 1.0001)):
                m = (grid >= lo) & (grid < hi)
                ax.plot(grid[m], fit[m], color=GREEN, lw=2)
        else:
            ax.plot(grid, fit, color=GREEN, lw=2)
        ax.plot(x, y, "o", mfc="none", mec="k", ms=4, mew=0.6)
        ax.set_title(tt)
    ax = axes[1, 1]
    ax.axvspan(0, k1, color=YELLOW, alpha=0.45, lw=0)
    ax.axvspan(k1, k2, color="#c9b458", alpha=0.45, lw=0)
    ax.axvspan(k2, 1, color=YELLOW, alpha=0.45, lw=0)
    ax.plot(grid, np.maximum(grid - k1, 0), color=GREEN, lw=2)
    ax.plot(x, np.maximum(x - k1, 0), "k.", ms=5)
    ax.text(0.42, 0.42, r"$(X-\xi_1)_+$", fontsize=11)
    ax.set_title(titles[3])
    for ax in axes.flat:
        knot_lines(ax, (k1, k2))
        ax.set_xticks([k1, k2]); ax.set_xticklabels([r"$\xi_1$", r"$\xi_2$"])
        ax.set_yticks([]); ax.set_xlim(0, 1)
    savefig(fig, CH, "fig5-1", out)


def fig_5_2(out=None):
    """Piecewise cubic polynomials with increasing orders of continuity at two knots."""
    x, y = artificial_data()
    k1, k2 = 1 / 3, 2 / 3
    grid = np.linspace(0, 1, 401)
    reg = lambda v: [(v < k1), (v >= k1) & (v < k2), (v >= k2)]

    def disc(v):
        return np.column_stack([r * v ** j for r in reg(v) for j in range(4)]).astype(float)

    def cont(order):          # continuous derivatives up to `order` at both knots
        def H(v):
            cols = [v ** j for j in range(4)]
            for k in (k1, k2):
                cols += [np.maximum(v - k, 0) ** j * (v >= k) for j in range(order + 1, 4)]
            return np.column_stack(cols).astype(float)
        return H
    designs = [(disc, "Discontinuous"), (cont(0), "Continuous"), (cont(1), "Continuous First Derivative"),
               (cont(2), "Continuous Second Derivative")]
    fig, axes = common.panel_grid(2, 2, size=(3.4, 2.7))
    for ax, (H, tt) in zip(axes.flat, designs):
        beta = np.linalg.lstsq(H(x), y, rcond=None)[0]
        ax.axvspan(0, k1, color=YELLOW, alpha=0.45, lw=0)
        ax.axvspan(k1, k2, color="#c9b458", alpha=0.45, lw=0)
        ax.axvspan(k2, 1, color=YELLOW, alpha=0.45, lw=0)
        ax.plot(grid, f_artificial(grid), color=BLUE)
        fit = H(grid) @ beta
        for lo, hi in ((0, k1), (k1, k2), (k2, 1.0001)):
            m = (grid >= lo) & (grid < hi)
            ax.plot(grid[m], fit[m], color=GREEN, lw=2)
        ax.plot(x, y, "o", mfc="none", mec="k", ms=4, mew=0.6)
        ax.set_title(tt)
        knot_lines(ax, (k1, k2))
        ax.set_xticks([k1, k2]); ax.set_xticklabels([r"$\xi_1$", r"$\xi_2$"])
        ax.set_yticks([]); ax.set_xlim(0, 1)
    fig.suptitle("Piecewise Cubic Polynomials", y=1.01)
    savefig(fig, CH, "fig5-2", out)


def fig53_bases():
    """The four design matrices of Figure 5.3 as functions."""
    ncs_knots = np.r_[0.1, np.linspace(0.1, 0.9, 6)[1:-1], 0.9]
    return {
        "Global Linear": lambda v: tpower_basis(v, [], 2),
        "Global Cubic Polynomial": lambda v: tpower_basis(v, [], 4),
        "Cubic Spline - 2 knots": lambda v: tpower_basis(v, [0.33, 0.66], 4),
        "Natural Cubic Spline - 6 knots": lambda v: ncs_basis_tp(v, ncs_knots),
    }


def pointwise_variance(H, x, grid):
    """sigma^2 = 1: Var fhat(x0) = h(x0)^T (H^T H)^{-1} h(x0)."""
    Hx = H(x)
    A = np.linalg.inv(Hx.T @ Hx)
    G = H(grid)
    return np.einsum("ij,jk,ik->i", G, A, G), np.einsum("ij,jk,ik->i", Hx, A, Hx)


def fig_5_3(out=None):
    """Pointwise variance curves of four least-squares fits (Exercise 5.3)."""
    rng = np.random.default_rng(3)
    x = np.sort(rng.uniform(0, 1, 50))
    grid = np.linspace(0, 1, 401)
    fig, ax = plt.subplots(figsize=(5.6, 4.2))
    cols = [ORANGE, RED, GREEN, BLUE]
    for (lab, H), c in zip(fig53_bases().items(), cols):
        vg, vx = pointwise_variance(H, x, grid)
        ax.plot(grid, vg, color=c, lw=1.2, label=lab)
        ax.plot(x, vx, "o", color=c, ms=3.5)
    ax.set_xlabel("X"); ax.set_ylabel("Pointwise Variances")
    ax.set_ylim(0, 0.6); ax.set_xlim(0, 1)
    ax.legend(loc="upper center")
    savefig(fig, CH, "fig5-3", out)


# =========================================================================== Figure 5.4, Table 5.1
SA_TERMS = ["sbp", "tobacco", "ldl", "famhist", "obesity", "alcohol", "age"]   # the predictors of Section 4.4.2


def sa_design(d, terms, df=4):
    blocks, cols = {}, [np.ones(len(d))]
    pos = 1
    for tm in terms:
        if tm == "famhist":
            B = d[tm].to_numpy(float)[:, None]
        else:
            B, _ = ns_quantile(d[tm].to_numpy(float), df)
        blocks[tm] = slice(pos, pos + B.shape[1])
        pos += B.shape[1]
        cols.append(B)
    return np.column_stack(cols), blocks


def sa_stepwise(d=None):
    """Backward deletion of whole natural-spline terms by AIC (Section 5.2.2). Returns the
    final terms, the full-model deviance and the drop-one table of the final model."""
    d = saheart() if d is None else d
    y = d.chd.to_numpy(float)
    terms = list(SA_TERMS)
    history = []

    def dev_of(tt):
        H, _ = sa_design(d, tt)
        return logistic_irls(H, y)[2], H.shape[1]
    while True:
        dev0, p0 = dev_of(terms)
        aic0 = dev0 + 2 * p0
        rows = []
        for tm in terms:
            dv, pp = dev_of([u for u in terms if u != tm])
            rows.append((tm, p0 - pp, dv, dv + 2 * pp, dv - dev0))
        best = min(rows, key=lambda r: r[3])
        history.append((list(terms), dev0, aic0))
        if best[3] < aic0:
            terms.remove(best[0])
        else:
            break
    table = [(r[0], r[1], r[2], r[3], r[4], float(stats.chi2.sf(r[4], r[1]))) for r in rows]
    return terms, dev0, aic0, table, history


def fig_5_4(out=None):
    """Fitted natural-spline terms of the final logistic model for the heart disease data."""
    d = saheart()
    terms, dev0, aic0, table, _ = sa_stepwise(d)
    y = d.chd.to_numpy(float)
    H, blocks = sa_design(d, terms)
    theta, cov, dev, _ = logistic_irls(H, y)
    order = ["sbp", "tobacco", "ldl", "famhist", "obesity", "age"]
    order = [t for t in order if t in terms] + [t for t in terms if t not in order]
    fig, axes = common.panel_grid(3, 2, size=(3.4, 2.5))
    for ax, tm in zip(axes.flat, order):
        sl = blocks[tm]
        if tm == "famhist":
            Hj = H[:, sl]
            vals = np.array([0.0, 1.0])
            hb = Hj.mean(0)
            G = vals[:, None] - hb
            f = G @ theta[sl]
            se = np.sqrt(np.einsum("ij,jk,ik->i", G, cov[sl, sl], G))
            for v, fv, s in zip(vals, f, se):
                ax.hlines(fv, v - 0.3, v + 0.3, color=GREEN, lw=2)
                ax.fill_between([v - 0.3, v + 0.3], fv - 2 * s, fv + 2 * s, color=YELLOW, alpha=0.7)
            ax.set_xticks([0, 1]); ax.set_xticklabels(["Absent", "Present"])
        else:
            xv = d[tm].to_numpy(float)
            grid = np.linspace(xv.min(), xv.max(), 200)
            _, (kn, lo, hi) = ns_quantile(xv, 4)
            Hj = H[:, sl]
            G = ns_basis(grid, kn, lo, hi) - Hj.mean(0)
            f = G @ theta[sl]
            se = np.sqrt(np.einsum("ij,jk,ik->i", G, cov[sl, sl], G))
            ax.fill_between(grid, f - 2 * se, f + 2 * se, color=YELLOW, alpha=0.7, lw=0)
            ax.plot(grid, f, color=GREEN, lw=2)
            rng = np.random.default_rng(0)
            jit = xv + rng.uniform(-0.25, 0.25, len(xv)) * (np.ptp(xv) / 200)
            rug(ax, jit, h=0.04)
        ax.set_xlabel(tm); ax.set_ylabel(r"$\hat f$(%s)" % tm)
    fig.tight_layout()
    savefig(fig, CH, "fig5-4", out)
    return terms, dev0, aic0, table


# =========================================================================== Figure 5.5
def phoneme_fits(seed=1, M=12):
    X, y, tr, te = phoneme_aa_ao(seed)
    freqs = np.arange(1, 257, dtype=float)
    H = ns_basis(freqs, np.linspace(1, 256, M)[1:-1], 1, 256, intercept=True)   # 256 x M
    raw = logistic_irls(np.column_stack([np.ones(len(tr)), X[tr]]), y[tr], maxit=200)
    Xs = X @ H                                                                 # filtered inputs x* = H^T x
    smo = logistic_irls(np.column_stack([np.ones(len(tr)), Xs[tr]]), y[tr])
    err = lambda th, Z, idx: float(np.mean(((np.column_stack([np.ones(len(idx)), Z[idx]]) @ th) > 0) != y[idx]))
    res = {"raw": (err(raw[0], X, tr), err(raw[0], X, te)), "smooth": (err(smo[0], Xs, tr), err(smo[0], Xs, te)),
           "beta_raw": raw[0][1:], "beta_smooth": H @ smo[0][1:], "H": H, "raw_iter": raw[3]}
    return X, y, tr, te, res


def fig_5_5(out=None):
    """Phoneme log-periodograms and raw versus smooth logistic regression coefficients."""
    X, y, tr, te, res = phoneme_fits()
    rng = np.random.default_rng(2)
    fig, (a1, a2) = plt.subplots(2, 1, figsize=(6.4, 6.2))
    f = np.arange(1, 257)
    for cls, col, lab in ((1, GREEN, "aa"), (0, ORANGE, "ao")):
        idx = rng.choice(np.where(y == cls)[0], 15, replace=False)
        for i, j in enumerate(idx):
            a1.plot(f, X[j], color=col, lw=0.7, label=lab if i == 0 else None)
    a1.set_title("Phoneme Examples"); a1.set_xlabel("Frequency"); a1.set_ylabel("Log-periodogram")
    a1.legend(loc="upper right")
    a2.plot(f, res["beta_raw"], color="0.6", lw=0.8)
    a2.plot(f, res["beta_smooth"], color=RED, lw=2)
    a2.axhline(0, color="k", lw=0.5)
    a2.set_ylim(-0.45, 0.45)
    a2.set_title("Phoneme Classification: Raw and Restricted Logistic Regression")
    a2.set_xlabel("Frequency"); a2.set_ylabel("Logistic Regression Coefficients")
    fig.tight_layout()
    savefig(fig, CH, "fig5-5", out)
    return res


# =========================================================================== Figures 5.6 - 5.9
def fig_5_6(out=None):
    """Smoothing splines with 12 degrees of freedom for males and females (bone density)."""
    d = bone_data()
    fig, ax = plt.subplots(figsize=(5.8, 4.2))
    lams = {}
    for sex, col, lab in (("male", BLUE, "Male"), ("female", RED, "Female")):
        s = d[d.gender == sex]
        ss = SmoothingSpline(s.age.to_numpy(float), s.spnbmd.to_numpy(float))
        lam = ss.lam_for_df(12)
        lams[sex] = lam
        grid = np.linspace(ss.t[0], ss.t[-1], 400)
        ax.plot(s.age, s.spnbmd, "o", color=col, ms=3, alpha=0.8)
        ax.plot(grid, ss.predict(lam, grid), color=col, lw=2, label=lab)
    ax.axhline(0, color="k", lw=0.5, ls=":")
    ax.set_xlabel("Age"); ax.set_ylabel("Relative Change in Spinal BMD")
    ax.legend()
    savefig(fig, CH, "fig5-6", out)
    return lams


def fig_5_7(out=None):
    """Smoothing splines on the ozone data with 5 and 11 df; eigenvalues and eigenvectors of S."""
    x, y = ozone_data()
    ss = SmoothingSpline(x, y)
    l5, l11 = ss.lam_for_df(5), ss.lam_for_df(11)
    grid = np.linspace(ss.t[0], ss.t[-1], 400)
    fig = plt.figure(figsize=(7.4, 7.6))
    gs = fig.add_gridspec(2, 2, height_ratios=[1.1, 1])
    ax = fig.add_subplot(gs[0, :])
    ax.plot(x, y, "k.", ms=4)
    ax.plot(grid, ss.predict(l5, grid), color=RED, lw=2, label=r"df$_\lambda$ = 5")
    ax.plot(grid, ss.predict(l11, grid), color=GREEN, lw=2, label=r"df$_\lambda$ = 11")
    ax.set_xlabel("Daggot Pressure Gradient"); ax.set_ylabel("Ozone Concentration"); ax.legend()
    ax = fig.add_subplot(gs[1, 0])
    k = np.arange(1, 26)
    for lam, col, lab in ((l5, RED, "df=5"), (l11, GREEN, "df=11")):
        rho, _ = ss.eig(lam)
        ax.plot(k, rho[::-1][:25] if rho[0] < rho[-1] else rho[:25], "o-", color=col, ms=3.5, lw=0.8, label=lab)
    ax.axhline(1, color="k", ls=":", lw=0.7); ax.axhline(0, color="k", ls=":", lw=0.7)
    ax.set_ylim(-0.2, 1.2); ax.set_xlabel("Order"); ax.set_ylabel("Eigenvalues"); ax.legend()
    sub = gs[1, 1].subgridspec(2, 2, hspace=0.08, wspace=0.08)
    rho5, V = ss.eig(l5)
    order = np.argsort(-rho5)
    for i, kk in enumerate(range(2, 6)):
        a = fig.add_subplot(sub[i // 2, i % 2])
        u = V[:, order[kk]]
        if u[np.argmax(np.abs(u))] < 0:
            u = -u
        a.plot(ss.t, u, color=BLUE, lw=1.2)
        a.plot(ss.t, rho5[order[kk]] * u, color=RED, lw=1.2)
        a.axhline(0, color="k", lw=0.4, ls=":")
        a.set_xticks([] if i < 2 else [-50, 0, 50, 100]); a.set_yticks([])
        rug(a, ss.t, color=BLUE, h=0.06)
        a.text(0.03, 0.9, "k = %d" % (kk + 1), transform=a.transAxes, fontsize=8)
    fig.tight_layout()
    savefig(fig, CH, "fig5-7", out)
    return ss, l5, l11


def fig_5_8(out=None):
    """The smoother matrix of the 5-df ozone smoothing spline, and its equivalent kernels."""
    x, y = ozone_data()
    ss = SmoothingSpline(x, y)
    lam = ss.lam_for_df(5)
    # weight given to each single observation: the N x N smoother is P A P^T with A = (W + lam K)^{-1},
    # so A (symmetric) holds the equivalent-kernel weights between the 128 distinct x values
    S = np.linalg.inv(np.diag(ss.W) + lam * ss.K)
    rows = [12, 25, 50, 75, 100, 115]
    fig = plt.figure(figsize=(8.2, 6.2))
    gs = fig.add_gridspec(len(rows), 2, width_ratios=[1.05, 1], wspace=0.25)
    ax = fig.add_subplot(gs[1:5, 0])
    cmap = LinearSegmentedColormap.from_list("rg", ["#2ecc40", "#a0a020", "#c0392b"])
    vmax = np.median(np.diag(S))
    ax.imshow(np.clip(S, -0.15 * vmax, vmax), cmap=cmap, vmin=-0.15 * vmax, vmax=vmax, interpolation="nearest")
    ax.set_title("Smoother Matrix")
    ax.set_yticks([r - 1 for r in rows]); ax.set_yticklabels([str(r) for r in rows]); ax.set_xticks([])
    for i, r in enumerate(rows):
        a = fig.add_subplot(gs[i, 1])
        a.plot(ss.t, S[r - 1], ".", color=CYAN, ms=2.5)
        a.plot(ss.t, S[r - 1], color=CYAN, lw=0.6)
        a.axvline(ss.t[r - 1], color="k", ls=":", lw=0.8)
        a.axhline(0, color="k", ls="--", lw=0.6)
        a.set_xticks([]); a.set_yticks([])
        a.set_title("Row %d" % r, fontsize=8, pad=2, backgroundcolor="#fde3c8")
        if i == 0:
            a.text(0.5, 1.6, "Equivalent Kernels", transform=a.transAxes, ha="center", fontsize=10.5)
    savefig(fig, CH, "fig5-8", out)
    return S


def epe_curve(x, y, dfs, sigma=1.0, ngrid=2001):
    """For the design x (fixed): EPE(df) = sigma^2 + int_0^1 [bias^2 + var] dx0 for X ~ U[0,1],
    computed exactly from the equivalent kernels L(x0) (fhat(x0) = L(x0) y), and CV(df)."""
    ss = SmoothingSpline(x, y)
    g = np.linspace(0, 1, ngrid)
    fx, fg = f522(x), f522(g)
    epe, cv, lams = [], [], []
    for df in dfs:
        lam = ss.lam_for_df(df)
        L = ss.operator_at(lam, g)
        bias = fg - L @ fx
        var = sigma ** 2 * np.sum(L ** 2, axis=1)
        epe.append(sigma ** 2 + np.trapz(bias ** 2 + var, g))
        cv.append(ss.loocv(lam))
        lams.append(lam)
    return np.array(epe), np.array(cv), np.array(lams)


def fig_5_9(out=None):
    """EPE and CV curves for the smoothing spline on data from (5.22), and fits with 5, 9, 15 df."""
    x, y = sim_522()
    dfs = np.linspace(5.5, 15, 16)
    epe, cv, _ = epe_curve(x, y, dfs)
    ss = SmoothingSpline(x, y)
    grid = np.linspace(0, 1, 400)
    fig, axes = common.panel_grid(2, 2, size=(3.5, 3.0))
    ax = axes[0, 0]
    ax.plot(dfs, cv, "o", color=ORANGE, ms=4, label="CV")
    ax.plot(dfs, epe, "o", color=CYAN, ms=4, label="EPE")
    ax.axvline(dfs[np.argmin(cv)], color="k", lw=0.7)
    ax.set_xlabel(r"df$_\lambda$"); ax.set_ylabel(r"EPE($\lambda$) and CV($\lambda$)")
    ax.set_title("Cross-Validation"); ax.legend()
    for ax, df in zip([axes[0, 1], axes[1, 0], axes[1, 1]], (5, 9, 15)):
        lam = ss.lam_for_df(df)
        L = ss.operator_at(lam, grid)
        fit = L @ y
        se = np.sqrt(np.sum(L ** 2, axis=1))
        ax.fill_between(grid, fit - 2 * se, fit + 2 * se, color=YELLOW, alpha=0.8, lw=0)
        ax.plot(x, y, "o", mfc="none", mec="#7e8fb5", ms=3.5, mew=0.6)
        ax.plot(grid, f522(grid), color=PURPLE, lw=1.6)
        ax.plot(grid, fit, color="#2ed12e", lw=2)
        ax.set_title(r"df$_\lambda$ = %d" % df); ax.set_xlabel("X"); ax.set_ylabel("y"); ax.set_ylim(-4.5, 3.6)
    fig.tight_layout()
    savefig(fig, CH, "fig5-9", out)
    return dfs, epe, cv


def fig_5_S1(out=None):
    """Exercise 5.10: mean and pointwise quantiles of fhat_lambda over repeated samples (fixed x)."""
    x, y = sim_522()
    ss = SmoothingSpline(x, y)
    grid = np.linspace(0, 1, 400)
    fig, axes = common.panel_grid(1, 3, size=(3.3, 3.0))
    for ax, df in zip(axes.flat, (5, 9, 15)):
        lam = ss.lam_for_df(df)
        L = ss.operator_at(lam, grid)
        mean = L @ f522(x)
        sd = np.sqrt(np.sum(L ** 2, axis=1))
        for q, a in ((0.025, 0.25), (0.1, 0.35), (0.25, 0.5)):
            z = stats.norm.ppf(1 - q)
            ax.fill_between(grid, mean - z * sd, mean + z * sd, color=GREEN, alpha=a, lw=0)
        ax.plot(grid, f522(grid), color=PURPLE, lw=1.6, label="true f")
        ax.plot(grid, mean, color="k", lw=1.6, label=r"E $\hat f_\lambda$")
        ax.set_title(r"df$_\lambda$ = %d" % df); ax.set_xlabel("X"); ax.set_ylim(-4, 3)
        if df == 5:
            ax.legend(loc="lower right", fontsize=8)
    savefig(fig, CH, "fig5-S1", out)


# =========================================================================== Section 5.6
def fig_5_S2(out=None):
    """Nonparametric logistic regression (5.30) of coronary heart disease on age (SA heart data)."""
    d = saheart()
    x, y = d.age.to_numpy(float), d.chd.to_numpy(float)
    ss, lam, f, it = nonparametric_logistic(x, y, df=4)
    grid = np.linspace(x.min(), x.max(), 300)
    g, gamma = ss.fit(lam)
    fg = ncs_eval(ss.t, g, gamma, grid)
    L = ss.operator_at(lam, grid)
    p = common.sigmoid(f)
    # standard errors from the final weighted smoother: Var(fhat) ~ L W^{-1} L^T on the unique values
    se = np.sqrt(np.einsum("ij,j,ij->i", L, 1.0 / ss.W, L))
    th, cov, _, _ = logistic_irls(np.column_stack([np.ones_like(x), x]), y)
    fig, ax = plt.subplots(figsize=(5.8, 4.0))
    ax.fill_between(grid, common.sigmoid(fg - 2 * se), common.sigmoid(fg + 2 * se), color=YELLOW, alpha=0.8, lw=0)
    ax.plot(grid, common.sigmoid(fg), color=GREEN, lw=2, label="smoothing spline, 4 df")
    ax.plot(grid, common.sigmoid(th[0] + th[1] * grid), color=BLUE, lw=1.4, ls="--", label="linear logistic")
    rng = np.random.default_rng(0)
    ax.plot(x, y + rng.uniform(-0.02, 0.02, len(y)), "k|", ms=6, alpha=0.5)
    ax.set_xlabel("age"); ax.set_ylabel("Pr(chd | age)"); ax.legend(loc="upper left")
    savefig(fig, CH, "fig5-S2", out)
    return lam, it


# =========================================================================== Figures 5.10 - 5.12
def fig_5_10(out=None):
    """A tensor-product basis of cubic B-splines: selected pairs and their marginals."""
    from mpl_toolkits.mplot3d import Axes3D  # noqa: F401
    interior = np.linspace(0, 1, 6)[1:-1]
    g = np.linspace(0, 1, 41)
    B = bspline_basis(g, interior, 0, 1, 4)                   # 41 x 8
    rows, cols = [0, 2, 4, 6], [1, 3, 5, 7]
    fig = plt.figure(figsize=(8.2, 8.0))
    gs = fig.add_gridspec(5, 5, width_ratios=[0.7, 1, 1, 1, 1], height_ratios=[0.6, 1, 1, 1, 1], wspace=0.0, hspace=0.0)
    for j, c in enumerate(cols):
        a = fig.add_subplot(gs[0, j + 1])
        a.plot(g, B[:, c], color="#2a9df4", lw=1.5); a.axis("off")
    G1, G2 = np.meshgrid(g, g)
    for i, r in enumerate(rows):
        a = fig.add_subplot(gs[i + 1, 0])
        a.plot(-B[:, r], g, color="#2a9df4", lw=1.5); a.axis("off")
        for j, c in enumerate(cols):
            a = fig.add_subplot(gs[i + 1, j + 1], projection="3d")
            Z = np.outer(B[:, r], B[:, c])
            a.plot_wireframe(G2, G1, Z, rstride=2, cstride=2, color="#444", lw=0.3)
            a.set_zlim(0, 0.5); a.set_axis_off(); a.view_init(30, -60)
            a.set_box_aspect((1, 1, 0.55))
    savefig(fig, CH, "fig5-10", out)


def mixture_spline_models(m=None):
    """Additive (1 + 3 + 3 = 7 df) and tensor-product (4 x 4 = 16 df) natural-spline logistic
    models for the mixture data; each coordinate has a 4-dimensional natural spline basis
    (constant plus ns(x, df = 3))."""
    m = mixture() if m is None else m
    X, y = m["x"], m["y"]
    specs = [ns_quantile(X[:, j], 3)[1] for j in range(2)]
    basis = lambda Z, j: ns_basis(Z[:, j], *specs[j])
    add = lambda Z: np.column_stack([np.ones(len(Z)), basis(Z, 0), basis(Z, 1)])

    def tens(Z):
        A = np.column_stack([np.ones(len(Z)), basis(Z, 0)])
        Bm = np.column_stack([np.ones(len(Z)), basis(Z, 1)])
        return np.einsum("ni,nj->nij", A, Bm).reshape(len(Z), -1)
    out = {}
    for name, H in (("additive", add), ("tensor", tens)):
        th = logistic_irls(H(X), y)[0]
        pred = lambda Z, H=H, th=th: (H(Z) @ th > 0).astype(float)
        out[name] = (th, H, mixture_errors(pred, m))
    return out


def fig_5_11(out=None):
    """Decision boundaries of additive and tensor-product natural-spline logistic models."""
    m = mixture()
    res = mixture_spline_models(m)
    px1, px2 = m["px1"], m["px2"]
    G = np.array([[a, b] for b in px2 for a in px1])
    fine1, fine2 = np.linspace(px1[0], px1[-1], 250), np.linspace(px2[0], px2[-1], 250)
    F1, F2 = np.meshgrid(fine1, fine2)
    Fg = np.column_stack([F1.ravel(), F2.ravel()])
    prob = m["prob"].reshape(len(px2), len(px1))
    fig, axes = plt.subplots(2, 1, figsize=(5.2, 10.0))
    titles = {"additive": "Additive Natural Cubic Splines - 4 df each",
              "tensor": "Natural Cubic Splines - Tensor Product - 4 df each"}
    for ax, name in zip(axes, ("additive", "tensor")):
        th, H, (tr, te, by) = res[name]
        fg = (H(Fg) @ th).reshape(F1.shape)
        cls = (H(G) @ th > 0)
        ax.scatter(G[:, 0], G[:, 1], s=0.6, c=np.where(cls, ORANGE, "#2a9df4"), lw=0, rasterized=True)
        ax.contour(F1, F2, fg, levels=[0], colors="k", linewidths=1.2)
        ax.contour(px1, px2, prob, levels=[0.5], colors=PURPLE, linewidths=1.2, linestyles="--")
        yy = m["y"]
        ax.scatter(m["x"][:, 0], m["x"][:, 1], s=22, facecolors="none",
                   edgecolors=np.where(yy == 1, ORANGE, "#2a9df4"), linewidths=1.1)
        ax.set_title(titles[name])
        ax.text(0.02, 0.03, "Training Error: %.3f\nTest Error:       %.3f\nBayes Error:    %.3f" % (tr, te, by),
                transform=ax.transAxes, fontsize=8.5, family="monospace",
                bbox=dict(fc="white", ec="0.6", alpha=0.9))
        ax.set_xticks([]); ax.set_yticks([])
        ax.set_xlim(px1[0], px1[-1]); ax.set_ylim(px2[0], px2[-1])
    savefig(fig, CH, "fig5-11", out)
    return {k: v[2] for k, v in res.items()}


def thin_plate_sbp(df=15, nlat=10):
    d = saheart()
    X = d[["age", "obesity"]].to_numpy(float)
    y = d.sbp.to_numpy(float)
    g1 = np.linspace(X[:, 0].min(), X[:, 0].max(), nlat)
    g2 = np.linspace(X[:, 1].min(), X[:, 1].max(), nlat)
    lattice = np.array([[a, b] for a in g1 for b in g2])
    inside = convex_hull_mask(lattice, X)
    tp = ThinPlate(X, y, lattice[inside])
    lam = tp.lam_for_df(df)
    tp.fit(lam)
    return X, y, lattice, inside, tp, lam


def fig_5_12(out=None):
    """Thin-plate spline (df = 15) of systolic blood pressure on age and obesity."""
    X, y, lattice, inside, tp, lam = thin_plate_sbp()
    a = np.linspace(X[:, 0].min() - 1, X[:, 0].max() + 1, 160)
    b = np.linspace(X[:, 1].min() - 1, X[:, 1].max() + 1, 160)
    A, Bg = np.meshgrid(a, b)
    P = np.column_stack([A.ravel(), Bg.ravel()])
    Z = tp.predict(P)
    Z[~convex_hull_mask(P, X)] = np.nan
    Z = Z.reshape(A.shape)
    fig, ax = plt.subplots(figsize=(6.0, 6.0))
    cmap = LinearSegmentedColormap.from_list("mc", ["#ff00ff", "#ffd0f0", "#d0f8ff", "#00e5ff"])
    cf = ax.contourf(A, Bg, Z, levels=12, cmap=cmap)
    cs = ax.contour(A, Bg, Z, levels=cf.levels[1:-1:2], colors="k", linewidths=0.7)
    ax.clabel(cs, fmt="%d", fontsize=7)
    ax.plot(X[:, 0], X[:, 1], "k.", ms=2.5)
    ax.plot(lattice[inside, 0], lattice[inside, 1], "o", color=RED, ms=4)
    ax.plot(lattice[~inside, 0], lattice[~inside, 1], "o", color=GREEN, ms=4)
    fig.colorbar(cf, ax=ax, shrink=0.8)
    ax.set_xlabel("Age"); ax.set_ylabel("Obesity"); ax.set_title("Systolic Blood Pressure")
    savefig(fig, CH, "fig5-12", out)
    return lam, tp.df(lam), int(inside.sum())


# =========================================================================== Figures 5.13 - 5.15
def mixture_kernel(nu=1.0):
    m = mixture()
    x1 = m["x"][:, 0]
    K = np.exp(-nu * (x1[:, None] - x1[None, :]) ** 2)
    gam, Phi = np.linalg.eigh(K)
    o = np.argsort(-gam)
    return x1, K, gam[o], Phi[:, o], m["y"]


def nystrom(x1, gam, Phi, xg, nu=1.0, k=16):
    """Exercise 5.17: phi_l(x) = (1 / gamma_l) sum_i K(x, x_i) Phi_{il} extends the l-th
    eigenvector to any x (it reproduces Phi_{il} at x = x_i)."""
    Kg = np.exp(-nu * (xg[:, None] - x1[None, :]) ** 2)
    return Kg @ Phi[:, :k] / gam[:k]


def fig_5_13(out=None):
    """Five Gaussian radial kernels K(., x_m) (nu = 1) for the first coordinate of the mixture data."""
    x1, K, gam, Phi, y = mixture_kernel()
    # five of the 200 points, spread over the range (closest to five equally spaced quantiles)
    idx = [int(np.argmin(np.abs(x1 - q))) for q in np.quantile(x1, [0.05, 0.3, 0.5, 0.7, 0.95])]
    g = np.linspace(x1.min() - 0.3, x1.max() + 0.3, 400)
    fig, ax = plt.subplots(figsize=(6.0, 3.6))
    for c, i in zip([RED, GREEN, BLUE, ORANGE, PURPLE], idx):
        ax.plot(g, np.exp(-(g - x1[i]) ** 2), color=c, lw=1.5)
    ax.set_ylim(0, 1.05)
    rug(ax, x1, color="0.3", h=0.05)
    ax.set_xlabel("X"); ax.set_ylabel(r"$K(\cdot, x_m)$"); ax.set_title(r"Radial Kernel in $\mathbb{R}^1$")
    savefig(fig, CH, "fig5-13", out)


def fig_5_14(out=None):
    """First 16 eigenvectors of the 200 x 200 kernel matrix as functions, and their rescaled versions."""
    x1, K, gam, Phi, y = mixture_kernel()
    g = np.linspace(x1.min(), x1.max(), 400)
    F = nystrom(x1, gam, Phi, g)
    fig = plt.figure(figsize=(9.2, 4.6))
    outer = fig.add_gridspec(1, 2, wspace=0.08)
    hmax = np.max(np.abs(np.sqrt(gam[:16]) * F))
    for side in range(2):
        sub = outer[side].subgridspec(4, 4, hspace=0.0, wspace=0.0)
        for l in range(16):
            a = fig.add_subplot(sub[l // 4, l % 4])
            sc = 1.0 if side == 0 else np.sqrt(gam[l])
            col = BLUE if side == 0 else RED
            a.plot(g, sc * F[:, l], color=col, lw=0.8)
            a.plot(x1, sc * Phi[:, l], ".", color=col, ms=1.3)
            a.axhline(0, color="k", lw=0.3, ls=":")
            if side == 1:
                a.set_ylim(-hmax, hmax)
            a.set_xticks([]); a.set_yticks([])
        fig.text(0.29 if side == 0 else 0.71, 0.93, r"Orthonormal Basis $\Phi$" if side == 0 else r"Feature Space $H$",
                 ha="center", fontsize=11)
    savefig(fig, CH, "fig5-14", out)


def fig_5_15(out=None):
    """The largest 50 eigenvalues of the kernel matrix (log scale)."""
    x1, K, gam, Phi, y = mixture_kernel()
    fig, ax = plt.subplots(figsize=(5.0, 3.6))
    ax.semilogy(np.arange(1, 51), np.maximum(gam[:50], 1e-17), "o", color=RED, ms=3.5)
    ax.axhline(np.finfo(float).eps * gam[0] * len(x1), color="k", ls=":", lw=0.7)
    ax.set_xlabel("Index"); ax.set_ylabel("Eigenvalue")
    savefig(fig, CH, "fig5-15", out)
    return gam


# =========================================================================== Figures 5.16 - 5.20
FIG516 = [(1, 0), (2, 1), (2, 3), (3, 2), (3, 5), (4, 4), (4, 9), (5, 1), (5, 15), (6, 15), (6, 35)]


def fig_5_16(out=None):
    """Selected Haar and symmlet-8 wavelets psi_{j,k} at several scales and translations."""
    N = 1024
    t = np.arange(N) / N
    cols = ["k", RED, GREEN, GREEN, BLUE, BLUE, ORANGE, ORANGE, MAGENTA, MAGENTA, PURPLE]
    fig, axes = plt.subplots(1, 2, figsize=(7.6, 6.4), sharey=True)
    for ax, name, tt in zip(axes, ("haar", "sym8"), ("Haar Wavelets", "Symmlet-8 Wavelets")):
        for i, ((j, k), c) in enumerate(zip(FIG516, cols)):
            v = wavelet_vector(N, j, k, name)
            v = v / np.max(np.abs(v)) * 0.4
            ax.axhline(i, color="0.6", lw=0.5, ls=":")
            if name == "haar":
                ax.step(t, i + v, color=c, lw=1.1, where="post")
            else:
                ax.plot(t, i + v, color=c, lw=1.1)
        ax.set_title(tt); ax.set_xlabel("Time"); ax.set_xlim(0, 1)
    axes[0].set_yticks(range(len(FIG516)))
    axes[0].set_yticklabels([r"$\psi_{%d,%d}$" % jk for jk in FIG516])
    axes[1].yaxis.tick_right()
    axes[1].set_yticks(range(len(FIG516)))
    axes[1].set_yticklabels([r"$\psi_{%d,%d}$" % jk for jk in FIG516])
    savefig(fig, CH, "fig5-16", out)


def nmr_data(seed=21, sigma=1.6):
    f = nmr_like_signal(1024)
    y = f + np.random.default_rng(seed).normal(0, sigma, len(f))
    return f, y


def fig_5_17(out=None):
    """A synthetic NMR-type signal, its symmlet-8 wavelet transform down to V4, and SureShrink."""
    f, y = nmr_data()
    fhat, c, cs, sigma, lams = wavelet_shrink(y, "sym8", 4, "sure")
    fig = plt.figure(figsize=(8.0, 8.4))
    gs = fig.add_gridspec(2, 2, height_ratios=[1, 1.25], hspace=0.3)
    ax = fig.add_subplot(gs[0, :])
    ax.plot(y, color="k", lw=0.6)
    ax.plot(fhat, color=GREEN, lw=1.2)
    ax.set_title("Synthetic NMR-type Signal (stand-in for the book's NMR spectrum)")
    for col, (coefs, tt) in enumerate(((c, "Wavelet Transform - Original Signal"), (cs, "Wavelet Transform - WaveShrunk Signal"))):
        a = fig.add_subplot(gs[1, col])
        labels = ["V4"] + ["W%d" % j for j in range(4, 10)]
        scale = 0.45 / np.max(np.abs(np.concatenate(c[1:])))
        for r, (arr, lab) in enumerate(zip(coefs, labels)):
            n = len(arr)
            pos = (np.arange(n) + 0.5) * 1024 / n
            sc = scale if r > 0 else 0.45 / np.max(np.abs(c[0]))
            a.vlines(pos, r, r + sc * arr, color="k", lw=0.6)
            a.axhline(r, color="0.7", lw=0.4)
        rec = idwt(coefs, "sym8")
        a.plot(np.arange(1024), len(coefs) + 0.2 + 0.6 * (rec - rec.min()) / np.ptp(rec), color="k", lw=0.5)
        a.set_yticks(range(len(coefs) + 1)); a.set_yticklabels(labels + ["Signal"])
        a.set_title(tt, fontsize=9.5); a.set_xlim(0, 1024)
    savefig(fig, CH, "fig5-17", out)
    return sigma, lams


def fig_5_18(out=None):
    """Haar and symmlet-8 scaling function phi and mother wavelet psi (cascade algorithm)."""
    fig, axes = common.panel_grid(2, 2, size=(3.4, 2.4))
    xs = np.linspace(0, 1, 401)
    phi_h = ((xs >= 0) & (xs < 1)).astype(float)
    psi_h = np.where(xs < 0.5, 1.0, -1.0)
    axes[0, 0].step(xs, phi_h, color=RED, where="post"); axes[0, 0].set_title("Haar Basis")
    axes[1, 0].step(xs, psi_h, color=BLUE, where="post")
    h, _ = wavelet_filters("sym8")
    x, phi, psi = cascade(h, 9)
    axes[0, 1].plot(x, phi, color=RED); axes[0, 1].set_title("Symmlet Basis")
    axes[1, 1].plot(x, psi, color=BLUE)
    for a, lab in zip(axes.flat, [r"$\phi(x)$", r"$\phi(x)$", r"$\psi(x)$", r"$\psi(x)$"]):
        a.axhline(0, color="k", lw=0.4); a.set_ylabel(lab)
    savefig(fig, CH, "fig5-18", out)


def fig_5_19(out=None):
    """SureShrink wavelet fits against cross-validated smoothing splines on two examples."""
    f, y = nmr_data()
    t = np.arange(len(y), dtype=float)
    w1 = wavelet_shrink(y, "sym8", 4, "sure")[0]
    ss = SmoothingSpline(t / len(t), y)
    lam1 = optimize.minimize_scalar(lambda ll: ss.loocv(np.exp(ll)), bounds=(-30, 0), method="bounded").x
    s1 = ss.fitted_full(np.exp(lam1))
    # smooth function: (5.22) on 128 equally spaced points, noise sd 1
    n2 = 128
    x2 = np.arange(n2) / n2
    rng = np.random.default_rng(7)
    y2 = f522(x2) + rng.normal(0, 1, n2)
    w2 = wavelet_shrink(y2, "sym8", 3, "sure")[0]
    ss2 = SmoothingSpline(x2, y2)
    lam2 = optimize.minimize_scalar(lambda ll: ss2.loocv(np.exp(ll)), bounds=(-30, 5), method="bounded").x
    s2 = ss2.fitted_full(np.exp(lam2))
    fig, (a1, a2) = plt.subplots(2, 1, figsize=(6.4, 7.4))
    a1.plot(t, y, color="0.75", lw=0.5)
    a1.plot(t, s1, color=CYAN, lw=1.0, label="spline")
    a1.plot(t, w1, color=ORANGE, lw=1.0, label="wavelet")
    a1.set_xlabel("Synthetic NMR-type Signal"); a1.legend()
    a2.plot(x2, y2, "o", color="0.5", ms=2.5)
    a2.plot(x2, s2, color=CYAN, lw=1.4, label="spline")
    a2.plot(x2, w2, color=ORANGE, lw=1.4, label="wavelet")
    a2.plot(x2, f522(x2), color="#b8a000", lw=1.0, label="true")
    a2.set_xlabel("Smooth Function (Simulated)"); a2.legend(loc="lower center")
    savefig(fig, CH, "fig5-19", out)
    mse = lambda a, b: float(np.mean((a - b) ** 2))
    return {"nmr": (mse(w1, f), mse(s1, f), ss.df(np.exp(lam1))), "smooth": (mse(w2, f522(x2)), mse(s2, f522(x2)), ss2.df(np.exp(lam2)))}


def fig_5_20(out=None):
    """B-splines of orders 1 to 4 with knots at 0, 0.1, ..., 1 (the Cox-de Boor recursion)."""
    interior = np.linspace(0, 1, 11)[1:-1]
    g = np.linspace(0, 1, 801)
    fig, axes = plt.subplots(4, 1, figsize=(6.0, 8.2))
    pal = plt.cm.tab10(np.linspace(0, 1, 10))
    for ax, M in zip(axes, (1, 2, 3, 4)):
        B = bspline_basis(g, interior, 0, 1, M)
        for i in range(B.shape[1]):
            ax.plot(g, B[:, i], color=pal[i % 10], lw=1.3)
        ax.set_title("B-splines of Order %d" % M); ax.set_ylim(-0.05, 1.15); ax.set_xlim(0, 1)
        for k in np.linspace(0, 1, 11):
            ax.axvline(k, color="0.85", lw=0.5, zorder=0)
    fig.tight_layout()
    savefig(fig, CH, "fig5-20", out)


# =========================================================================== exercises
def exercise_5_5(seed=1, folds=10):
    """QDA on natural-spline filtered phoneme features (aa versus ao); five knot choices fixed in
    advance, chosen by tenfold CV on the training sample, then evaluated on the test sample."""
    X, y, tr, te = phoneme_aa_ao(seed)
    f = np.arange(1, 257, dtype=float)
    choices = {
        "M=4 uniform": np.linspace(1, 256, 4),
        "M=8 uniform": np.linspace(1, 256, 8),
        "M=12 uniform": np.linspace(1, 256, 12),
        "M=20 uniform": np.linspace(1, 256, 20),
        "M=12 log-spaced": np.exp(np.linspace(0, np.log(256), 12)),
    }

    def qda_fit(Z, yy):
        pars = []
        for c in (0, 1):
            Zc = Z[yy == c]
            mu = Zc.mean(0)
            S = np.cov(Zc.T, bias=False)
            pars.append((mu, S, np.log(np.mean(yy == c))))
        return pars

    def qda_pred(pars, Z):
        sc = [common.gauss_logpdf(Z, mu, S) + lp for mu, S, lp in pars]
        return (sc[1] > sc[0]).astype(float)
    rng = np.random.default_rng(seed + 100)
    fold = rng.permutation(len(tr)) % folds
    out = {}
    for name, kn in choices.items():
        H = ns_basis(f, kn[1:-1], kn[0], kn[-1], intercept=True)
        Z = X @ H
        cv = np.mean([np.mean(qda_pred(qda_fit(Z[tr][fold != k], y[tr][fold != k]), Z[tr][fold == k]) != y[tr][fold == k])
                      for k in range(folds)])
        test = np.mean(qda_pred(qda_fit(Z[tr], y[tr]), Z[te]) != y[te])
        out[name] = (float(cv), float(test))
    raw_test = float(np.mean(qda_pred(qda_fit(X[tr], y[tr]), X[te]) != y[te]))
    return out, raw_test


# =========================================================================== JSON for the demos
def export_demo_data():
    os.makedirs(DATA_OUT, exist_ok=True)
    x, y = ozone_data()
    bd = bone_data()
    xs, ys = sim_522()
    sm = {"ozone": {"x": x.tolist(), "y": y.tolist(), "xlab": "Daggot pressure gradient", "ylab": "Ozone concentration"},
          "bone_male": {"x": bd[bd.gender == "male"].age.round(4).tolist(), "y": bd[bd.gender == "male"].spnbmd.round(7).tolist(),
                        "xlab": "Age", "ylab": "Relative change in spinal BMD"},
          "bone_female": {"x": bd[bd.gender == "female"].age.round(4).tolist(), "y": bd[bd.gender == "female"].spnbmd.round(7).tolist(),
                          "xlab": "Age", "ylab": "Relative change in spinal BMD"},
          "sim522": {"x": np.round(xs, 6).tolist(), "y": np.round(ys, 6).tolist(), "xlab": "X", "ylab": "y"}}
    with open(os.path.join(DATA_OUT, "ch05-smoothing.json"), "w") as fh:
        json.dump(sm, fh, separators=(",", ":"))
    xa, ya = artificial_data()
    xb, yb = sim_522()
    rs = {"artificial": {"x": np.round(xa, 6).tolist(), "y": np.round(ya, 6).tolist()},
          "sim522": {"x": np.round(xb, 6).tolist(), "y": np.round(yb, 6).tolist()}}
    with open(os.path.join(DATA_OUT, "ch05-regression-splines.json"), "w") as fh:
        json.dump(rs, fh, separators=(",", ":"))
    h, _ = wavelet_filters("sym8")
    f, yn = nmr_data()
    wv = {"sym8": h.tolist(), "nmr": {"f": np.round(f, 5).tolist(), "y": np.round(yn, 5).tolist()}}
    with open(os.path.join(DATA_OUT, "ch05-wavelets.json"), "w") as fh:
        json.dump(wv, fh, separators=(",", ":"))
    print("wrote demo data to", DATA_OUT)


FIGURES = {
    "5.1": fig_5_1, "5.2": fig_5_2, "5.3": fig_5_3, "5.4": fig_5_4, "5.5": fig_5_5,
    "5.6": fig_5_6, "5.7": fig_5_7, "5.8": fig_5_8, "5.9": fig_5_9, "5.10": fig_5_10,
    "5.11": fig_5_11, "5.12": fig_5_12, "5.13": fig_5_13, "5.14": fig_5_14, "5.15": fig_5_15,
    "5.16": fig_5_16, "5.17": fig_5_17, "5.18": fig_5_18, "5.19": fig_5_19, "5.20": fig_5_20,
    "5.S1": fig_5_S1, "5.S2": fig_5_S2,
}

if __name__ == "__main__":
    import sys
    if "--export" in sys.argv:
        export_demo_data()
    else:
        common.run(FIGURES, CH)
        if not any(a.startswith("--fig") or a == "--list" for a in sys.argv[1:]):
            export_demo_data()
