"""Wasserman (2004), Chapter 20: Nonparametric Curve Estimation.

Companion code for Chapter 20 of L. Wasserman, All of Statistics: A Concise Course in Statistical
Inference (Springer, 2004), pp. 303-326, written from scratch with numpy, scipy and matplotlib. The
functions are short and meant to be read next to the lecture notes
(../ch20-nonparametric-curve-estimation.html):

* Section 20.2, histograms: hist_counts, hist_density, hist_cv (the cross-validation score by the
  shortcut (20.14), in its corrected form) and hist_cv_loo (the same score by brute-force leave-one-out),
  hist_band (the confidence envelope (20.17) for the "histogramised" density).
* Section 20.3, kernel density estimation: kde (Gaussian or Epanechnikov kernel), kde_cv (the exact
  leave-one-out score (20.24), all pairs at once) and kde_cv_approx (the approximation (20.25)),
  kde_band (the band (20.27)), kde_nd (the d-dimensional product-kernel estimator (20.28)).
* Section 20.4, nonparametric regression: nw_matrix / nw_fit (the Nadaraya-Watson estimator
  (20.31)-(20.32)), ll_matrix (local linear regression, the boundary-corrected relative of
  Nadaraya-Watson), loo_score (the leave-one-out score (20.34) by the one-fit shortcut (20.35)),
  loo_brute (by refitting n times), sigma2_diff (the difference estimator (20.36)), reg_band (the band
  (20.37)), backfit (the backfitting algorithm for additive models (20.38)).
* Exact risks for Normal-mixture densities, used for Figure 20.2, the rates of Figure 20.S1 and the
  smoothing-rates demo: MIXTURES, mix_pdf, mix_cdf, mix_R (integrals of products of derivatives),
  kde_mise_exact (exact bias and variance of the Gaussian kernel estimator), hist_mise_exact (exact
  bias and variance of a histogram with bins anchored at 0), the asymptotic forms (20.10) and (20.22),
  opt_h (the minimiser, found the same way in the browser), and kde_mise_nd / silverman_n (the curse of
  dimensionality: Silverman's sample-size table, recomputed exactly).
* JSRandom, js_uniforms: the seeded generator of the browser demonstrations (DK.rng in
  courses/demo-kit.js), so that the demonstrations' simulated samples are reproduced here number for
  number; sample_mixture, hist_ise and kde_ise_binned are the simulation steps of the demos.

Data. The astronomy (galaxy redshift) data of Example 20.2 are the 1266 redshifts below 0.2 in the
third column of redshift.dat on the book's website; the CMB data of Example 20.23 are replaced by the
WMAP power spectrum (wmap.dat on the same website; the BOOMERaNG, Maxima and DASI points plotted in the
book are not there), restricted to multipoles l <= 700 (beyond that the measurement error explodes).
Exercises 20.2 and 20.3 use glass.dat; the motorcycle data (motor.dat) appear in the regression demo.

Figures. Figure 20.1 is a labelled sketch of the notation g_n(x) with nothing computed, and is skipped.
Figure 20.2 is a schematic in the book; here it is computed exactly (the squared bias, variance and
risk of a kernel density estimate for a known density). Figures 20.3-20.9 are reproduced on the data.
Six supplementary figures illustrate gaps filled in the notes:
  20.S1 the rates n^(-2/3) and n^(-4/5): exact risks and simulation (Theorems 20.4 and 20.14);
  20.S2 the curse of dimensionality: Silverman's table recomputed, and the rate n^(-4/(4+d));
  20.S3 rounded data and cross-validation (Example 20.17), and the exact unbiasedness of the score;
  20.S4 confidence bands cover the smoothed curve, not the curve (Section 20.5), by simulation;
  20.S5 the design bias of Nadaraya-Watson and the boundary, against local linear regression;
  20.S6 Exercises 20.2 and 20.3 on the glass data.
Run `python3 ch20_nonparametric_curve_estimation.py --list`, `python3
ch20_nonparametric_curve_estimation.py` (all fourteen figures, about a minute on one CPU thread) or
`python3 ch20_nonparametric_curve_estimation.py --fig 20.3`. Files go to ../img/ch20/; the data used
by the browser demonstrations are written to ../data/ch20-*.json by export_json() (run with the figures).
"""
import json
import math
import os

import numpy as np
from scipy import optimize, stats

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

CH = 20
M32 = 0xFFFFFFFF
SQ2PI = math.sqrt(2.0 * math.pi)
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")


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


class JSRandom:
    """The seeded random numbers of the browser demos (DK.rng in courses/demo-kit.js): u() is
    mulberry32 and norm() the Box-Muller transform that returns r cos(t) and keeps r sin(t) for the
    next call, exactly as in JavaScript."""

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

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

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


def js_uniforms(seed, n, start=0):
    """Uniforms number start+1, ..., start+n of DK.rng(seed), vectorised (mulberry32 adds a constant
    to its state at each call, so the j-th output is a hash of seed + j * 0x6D2B79F5 mod 2^32)."""
    j = np.arange(start + 1, start + n + 1, dtype=np.uint64)
    m = np.uint64(M32)
    a = (np.uint64(int(seed) & M32) + j * np.uint64(0x6D2B79F5)) & m
    t = ((a ^ (a >> np.uint64(15))) * (np.uint64(1) | a)) & m
    t = ((t + (((t ^ (t >> np.uint64(7))) * (np.uint64(61) | t)) & m)) & m) ^ t
    return ((t ^ (t >> np.uint64(14))) & m).astype(np.float64) / 4294967296.0


# =========================================================================== the book's data
def redshift():
    """The astronomy data of Example 20.2: the 1266 galaxy redshifts below 0.2 (third column of
    redshift.dat), sorted. A redshift is a proxy for distance along the 'pencil beam'."""
    X = np.loadtxt(common.aos_file("redshift.dat"))
    return np.sort(X[X[:, 2] < 0.2, 2])


def wmap(lmax=700):
    """WMAP estimate of the CMB power spectrum (wmap.dat): multipole l and power C_l, for l <= lmax."""
    D = np.loadtxt(common.aos_file("wmap.dat"), comments="#", skiprows=5)
    keep = D[:, 0] <= lmax
    return D[keep, 0], D[keep, 1]


def motor():
    """The motorcycle data (motor.dat): time since impact (ms) and head acceleration (g), n = 94."""
    d = common.aos_data("motor.dat", sep=r"\s+", comment="#")
    return d["times"].to_numpy(float), d["accel"].to_numpy(float)


def glass():
    """The glass fragments data (glass.dat): refractive index RI (as recorded, a shifted and scaled
    index) and aluminium content Al, n = 214."""
    d = common.aos_data("glass.dat")
    return d["RI"].to_numpy(float), d["Al"].to_numpy(float)


# ranges used for the histograms and bands (the book uses [0, 0.2] for the redshifts)
GALAXY_AB = (0.0, 0.2)
GLASS_AB = (-7.0, 16.0)


# =========================================================================== 20.2 histograms
def hist_counts(x, m, a, b):
    """Counts nu_j in the m bins [a + (j-1)h, a + jh) of width h = (b - a)/m (the last bin closed)."""
    x = np.asarray(x, float)
    h = (b - a) / m
    j = np.floor((x - a) / h).astype(int)
    j = np.clip(j, 0, m - 1)
    return np.bincount(j, minlength=m)


def hist_density(x, m, a, b):
    """Bin edges and heights p_j / h of the histogram estimator (20.8)."""
    n = len(x)
    h = (b - a) / m
    return a + h * np.arange(m + 1), hist_counts(x, m, a, b) / (n * h)


def hist_cv(x, m, a, b):
    """Cross-validation score J(h) by the shortcut (20.14) as corrected in the author's errata:
    2/((n-1)h) - (n+1)/((n-1)h) * sum p_j^2."""
    n = len(x)
    h = (b - a) / m
    p = hist_counts(x, m, a, b) / n
    return 2.0 / ((n - 1) * h) - (n + 1) / ((n - 1) * h) * np.sum(p * p)


def hist_cv_curve(x, a, b, ms):
    return np.array([hist_cv(x, m, a, b) for m in ms])


def hist_cv_loo(x, m, a, b):
    """The definition (20.13), by brute force: integral of the squared histogram minus (2/n) times the
    sum of the leave-one-out histograms at the left-out points."""
    x = np.asarray(x, float)
    n = len(x)
    h = (b - a) / m
    nu = hist_counts(x, m, a, b)
    j = np.clip(np.floor((x - a) / h).astype(int), 0, m - 1)
    int_sq = np.sum((nu / (n * h)) ** 2) * h
    loo = np.empty(n)
    for i in range(n):
        nu_i = nu.copy()
        nu_i[j[i]] -= 1
        loo[i] = nu_i[j[i]] / ((n - 1) * h)
    return int_sq - 2.0 * loo.mean()


def hist_band(x, m, a, b, alpha=0.05):
    """The envelope (20.17)-(20.18) for the histogramised density fbar = p_j/h: on the square-root scale
    sqrt(fhat) +/- c with c = z_{alpha/(2m)} / (2 sqrt(n h)) (which is (20.18) when [a, b] = [0, 1])."""
    n = len(x)
    h = (b - a) / m
    edges, f = hist_density(x, m, a, b)
    c = stats.norm.isf(alpha / (2 * m)) / (2.0 * math.sqrt(n * h))
    lo = np.maximum(np.sqrt(f) - c, 0.0) ** 2
    up = (np.sqrt(f) + c) ** 2
    return edges, f, lo, up, c


# =========================================================================== 20.3 kernel density estimation
def k_gauss(u):
    return np.exp(-0.5 * u * u) / SQ2PI


def k_epan(u):
    """The Epanechnikov kernel in the book's scaling (20.20): support |u| < sqrt 5, variance 1."""
    s5 = math.sqrt(5.0)
    return np.where(np.abs(u) < s5, 0.75 * (1.0 - u * u / 5.0) / s5, 0.0)


def kde(x, grid, h, kernel=k_gauss, chunk=400):
    """The kernel density estimator (20.21) at the points of grid."""
    x = np.asarray(x, float)
    grid = np.asarray(grid, float)
    out = np.empty(len(grid))
    for s in range(0, len(grid), chunk):
        g = grid[s:s + chunk]
        out[s:s + chunk] = kernel((g[:, None] - x[None, :]) / h).sum(1) / (len(x) * h)
    return out


def _pair_diffs(x):
    x = np.asarray(x, float)
    i, j = np.triu_indices(len(x), 1)
    return x[j] - x[i]


def kde_cv(x, hs, d=None):
    """The exact leave-one-out score (20.24) for the Gaussian kernel, for every h in hs:
    J(h) = (1/(n^2 h)) sum_{i,j} K2((Xi - Xj)/h) - (2/(n(n-1)h)) sum_{i != j} K((Xi - Xj)/h),
    where K2 is the N(0, 2) density (K convolved with itself)."""
    n = len(x)
    d = _pair_diffs(x) if d is None else d
    out = []
    for h in np.atleast_1d(hs):
        u2 = (d / h) ** 2
        s2 = 2.0 * np.sum(np.exp(-u2 / 4.0)) / math.sqrt(4 * math.pi) + n / math.sqrt(4 * math.pi)
        s1 = 2.0 * np.sum(np.exp(-u2 / 2.0)) / SQ2PI
        out.append(s2 / (n * n * h) - 2.0 * s1 / (n * (n - 1) * h))
    return np.array(out)


def kde_cv_approx(x, hs, d=None):
    """The approximation (20.25): (1/(h n^2)) sum_{i,j} Kstar((Xi - Xj)/h) + 2 K(0)/(n h), with
    Kstar = K2 - 2K."""
    n = len(x)
    d = _pair_diffs(x) if d is None else d
    out = []
    for h in np.atleast_1d(hs):
        u2 = (d / h) ** 2
        kstar = np.exp(-u2 / 4.0) / math.sqrt(4 * math.pi) - 2.0 * np.exp(-u2 / 2.0) / SQ2PI
        tot = 2.0 * np.sum(kstar) + n * (1.0 / math.sqrt(4 * math.pi) - 2.0 / SQ2PI)
        out.append(tot / (h * n * n) + 2.0 / (SQ2PI * n * h))
    return np.array(out)


def kde_cv_brute(x, h):
    """(20.24) by refitting: integral of fhat^2 (closed form for the Gaussian kernel) minus (2/n) sum of
    the leave-one-out estimates at the left-out points."""
    x = np.asarray(x, float)
    n = len(x)
    D = x[:, None] - x[None, :]
    int_sq = np.sum(np.exp(-D * D / (4 * h * h))) / (math.sqrt(4 * math.pi) * h * n * n)
    K = k_gauss(D / h) / h
    np.fill_diagonal(K, 0.0)
    loo = K.sum(1) / (n - 1)
    return int_sq - 2.0 * loo.mean()


def kde_band(x, grid, h, a, b, alpha=0.05, omega_mult=3.0):
    """The band (20.27) for fbar_h = E fhat: fhat +/- q se(x), se = s(x)/sqrt(n) where s(x) is the sample
    standard deviation of Y_i(x) = K((x - X_i)/h)/h, q = Phi^{-1}((1 + (1-alpha)^(1/m))/2),
    m = (b - a)/omega and omega = 3h for the Normal kernel."""
    x = np.asarray(x, float)
    n = len(x)
    Y = k_gauss((np.asarray(grid)[:, None] - x[None, :]) / h) / h
    f = Y.mean(1)
    s = Y.std(1, ddof=1)
    m = (b - a) / (omega_mult * h)
    q = stats.norm.ppf((1.0 + (1.0 - alpha) ** (1.0 / m)) / 2.0)
    se = s / math.sqrt(n)
    return f, f - q * se, f + q * se, q, m


def kde_nd(X, grid, h):
    """The d-dimensional product-kernel estimator (20.28)-(20.29) with Gaussian K and bandwidths h_j."""
    X = np.atleast_2d(X)
    grid = np.atleast_2d(grid)
    h = np.broadcast_to(np.asarray(h, float), (X.shape[1],))
    U = (grid[:, None, :] - X[None, :, :]) / h
    return np.prod(k_gauss(U), axis=2).sum(1) / (len(X) * np.prod(h))


# =========================================================================== 20.4 nonparametric regression
def nw_matrix(x, grid, h, kernel=k_gauss):
    """Weights w_i(g) of the Nadaraya-Watson estimator (20.32), one row per point g of grid."""
    K = kernel((np.asarray(grid, float)[:, None] - np.asarray(x, float)[None, :]) / h)
    return K / K.sum(1, keepdims=True)


def ll_matrix(x, grid, h, kernel=k_gauss):
    """Weights of local linear regression: at each g, weighted least squares of Y on (1, x - g) with
    weights K((x - g)/h); the fitted intercept is sum_i l_i(g) Y_i."""
    x = np.asarray(x, float)
    g = np.asarray(grid, float)[:, None]
    K = kernel((x[None, :] - g) / h)
    dx = x[None, :] - g
    S1 = (K * dx).sum(1, keepdims=True)
    S2 = (K * dx * dx).sum(1, keepdims=True)
    W = K * (S2 - dx * S1)
    return W / W.sum(1, keepdims=True)


def nw_fit(x, y, grid, h):
    return nw_matrix(x, grid, h) @ np.asarray(y, float)


def loo_score(x, y, h, method="nw"):
    """The leave-one-out score (20.34) from one fit, (20.35): sum_i ((Y_i - rhat(x_i))/(1 - L_ii))^2.
    For Nadaraya-Watson L_ii = K(0)/sum_j K((x_i - x_j)/h); the identity also holds for local linear."""
    with np.errstate(invalid="ignore", divide="ignore"):
        L = (nw_matrix if method == "nw" else ll_matrix)(x, x, h)
    r = L @ np.asarray(y, float)
    d = 1.0 - np.diag(L)
    if not np.all(np.isfinite(r)) or np.min(d) < 1e-10:   # some point cannot be predicted from the others
        return math.inf
    return float(np.sum(((y - r) / d) ** 2))


def loo_brute(x, y, h, method="nw"):
    """(20.34) by refitting without each point in turn."""
    x = np.asarray(x, float)
    y = np.asarray(y, float)
    n = len(x)
    tot = 0.0
    for i in range(n):
        keep = np.arange(n) != i
        L = (nw_matrix if method == "nw" else ll_matrix)(x[keep], [x[i]], h)
        tot += (y[i] - float(L @ y[keep])) ** 2
    return tot


def sigma2_diff(x, y):
    """The difference estimator (20.36): sum of squared successive differences (x sorted) over 2(n-1)."""
    o = np.argsort(x, kind="stable")
    d = np.diff(np.asarray(y, float)[o])
    return float(np.sum(d * d) / (2.0 * (len(d))))


def reg_band(x, y, grid, h, alpha=0.05, method="nw", omega_mult=3.0, sigma2=None):
    """The band (20.37) for rbar = E rhat: rhat +/- q sigmahat sqrt(sum_i w_i(x)^2), with q as in
    (20.27), m = (b - a)/omega, omega = 3h, and sigmahat from (20.36)."""
    L = (nw_matrix if method == "nw" else ll_matrix)(x, grid, h)
    r = L @ np.asarray(y, float)
    s2 = sigma2_diff(x, y) if sigma2 is None else sigma2
    se = math.sqrt(s2) * np.sqrt((L * L).sum(1))
    m = (np.max(x) - np.min(x)) / (omega_mult * h)
    q = stats.norm.ppf((1.0 + (1.0 - alpha) ** (1.0 / m)) / 2.0)
    return r, r - q * se, r + q * se, q, m, math.sqrt(s2)


def geom_grid(lo, hi, k):
    """k geometrically spaced values from lo to hi (the bandwidth grids of the demos)."""
    return lo * (hi / lo) ** (np.arange(k) / (k - 1.0))


def cv_bandwidth(x, y, hs, method="nw"):
    J = np.array([loo_score(x, y, h, method) for h in hs])
    return hs[int(np.argmin(J))], J


def backfit(X, y, h, iters=50, tol=1e-10):
    """Backfitting (Section 20.4) for the additive model (20.38) with a Nadaraya-Watson smoother for each
    coordinate; returns the intercept and the n x p matrix of fitted component values (centred)."""
    X = np.atleast_2d(X)
    n, p = X.shape
    hs = np.broadcast_to(np.asarray(h, float), (p,))
    S = [nw_matrix(X[:, j], X[:, j], hs[j]) for j in range(p)]
    a = float(np.mean(y))
    R = np.zeros((n, p))
    for _ in range(iters):
        old = R.copy()
        for j in range(p):
            part = y - a - R.sum(1) + R[:, j]
            R[:, j] = S[j] @ part
            R[:, j] -= R[:, j].mean()
        if np.max(np.abs(R - old)) < tol:
            break
    return a, R


# =========================================================================== exact risks for Normal mixtures
# (weights, means, standard deviations); the last three are from Marron and Wand (1992)
MIXTURES = {
    "normal": ([1.0], [0.0], [1.0]),
    "bimodal": ([0.5, 0.5], [-1.0, 1.0], [2.0 / 3.0, 2.0 / 3.0]),
    "skewed": ([0.2, 0.2, 0.6], [0.0, 0.5, 13.0 / 12.0], [1.0, 2.0 / 3.0, 5.0 / 9.0]),
    "kurtotic": ([2.0 / 3.0, 1.0 / 3.0], [0.0, 0.0], [1.0, 0.1]),
}


def _mix(name):
    w, mu, s = MIXTURES[name] if isinstance(name, str) else name
    return np.asarray(w, float), np.asarray(mu, float), np.asarray(s, float)


def mix_pdf(name, x):
    w, mu, s = _mix(name)
    x = np.asarray(x, float)[..., None]
    return np.sum(w * stats.norm.pdf(x, mu, s), axis=-1)


def mix_cdf(name, x):
    w, mu, s = _mix(name)
    x = np.asarray(x, float)[..., None]
    return np.sum(w * stats.norm.cdf(x, mu, s), axis=-1)


def _phi_deriv(d, var, k):
    """k-th derivative (k = 0, 2, 4) of the N(0, var) density at d."""
    s2 = var
    p = np.exp(-0.5 * d * d / s2) / np.sqrt(2 * np.pi * s2)
    if k == 0:
        return p
    if k == 2:
        return p * (d * d - s2) / s2 ** 2
    if k == 4:
        return p * (d ** 4 - 6 * d * d * s2 + 3 * s2 * s2) / s2 ** 4
    raise ValueError(k)


def mix_R(name, k=0, extra=0.0):
    """Integral of (f^(k))^2 for a Normal mixture f (k = 0, 1, 2); with extra = t, of the product of the
    mixture smoothed by N(0, t/2) with itself (used in the exact risks)."""
    w, mu, s = _mix(name)
    D = mu[:, None] - mu[None, :]
    V = s[:, None] ** 2 + s[None, :] ** 2 + extra
    WW = w[:, None] * w[None, :]
    sign = (-1) ** k
    return float(np.sum(WW * sign * _phi_deriv(D, V, 2 * k)))


def _cross(name, t):
    """sum_ij w_i w_j phi_{sqrt(s_i^2 + s_j^2 + t)}(mu_i - mu_j)."""
    w, mu, s = _mix(name)
    D = mu[:, None] - mu[None, :]
    V = s[:, None] ** 2 + s[None, :] ** 2 + t
    return float(np.sum(w[:, None] * w[None, :] * _phi_deriv(D, V, 0)))


def kde_mise_exact(name, n, h, parts=False):
    """Exact MISE of the Gaussian kernel estimator for a Normal-mixture density (Marron and Wand, 1992):
    integrated variance n^{-1}[(2 sqrt(pi) h)^{-1} - int (K_h * f)^2] plus integrated squared bias
    int (K_h * f - f)^2."""
    Rf = _cross(name, 0.0)
    a2 = _cross(name, 2 * h * h)        # int (K_h * f)^2
    a1 = _cross(name, h * h)            # int (K_h * f) f
    var = (1.0 / (2 * math.sqrt(math.pi) * h) - a2) / n
    bias2 = a2 - 2 * a1 + Rf
    return (bias2, var, bias2 + var) if parts else bias2 + var


def hist_bin_probs(name, h, origin=0.0, span=12.0):
    """Probabilities p_j of the bins [origin + jh, origin + (j+1)h) covering the mixture's support."""
    w, mu, s = _mix(name)
    lo = np.min(mu - span * s)
    hi = np.max(mu + span * s)
    j0 = math.floor((lo - origin) / h)
    j1 = math.ceil((hi - origin) / h)
    edges = origin + h * np.arange(j0, j1 + 1)
    c = mix_cdf(name, edges)
    return np.diff(c)


def hist_mise_exact(name, n, h, origin=0.0, parts=False):
    """Exact MISE of the histogram with bins of width h anchored at origin:
    integrated squared bias int f^2 - sum p_j^2/h and integrated variance (1 - sum p_j^2)/(n h)."""
    p = hist_bin_probs(name, h, origin)
    sp2 = float(np.sum(p * p))
    bias2 = _cross(name, 0.0) - sp2 / h
    var = (1.0 - sp2) / (n * h)
    return (bias2, var, bias2 + var) if parts else bias2 + var


def hist_amise(name, n, h):
    """The approximation (20.10): h^2/12 int f'^2 + 1/(n h)."""
    return h * h / 12.0 * mix_R(name, 1) + 1.0 / (n * h)


def kde_amise(name, n, h):
    """The approximation (20.22) for the Gaussian kernel (sigma_K = 1, int K^2 = 1/(2 sqrt pi))."""
    return 0.25 * h ** 4 * mix_R(name, 2) + 1.0 / (2 * math.sqrt(math.pi) * n * h)


def hist_hstar(name, n):
    """(20.11): h* = (6 / int f'^2)^(1/3) n^(-1/3)."""
    return (6.0 / mix_R(name, 1)) ** (1.0 / 3.0) * n ** (-1.0 / 3.0)


def kde_hstar(name, n):
    """(20.23) for the Gaussian kernel: c1 = 1, c2 = 1/(2 sqrt pi), c3 = int f''^2."""
    return (1.0 / (2 * math.sqrt(math.pi)) / mix_R(name, 2)) ** 0.2 * n ** (-0.2)


def opt_h(fun, h_guess, k=161, span=2.0, iters=80):
    """Minimise fun(h) over log h: a grid of k points on [log h_guess - span, log h_guess + span], then
    golden-section search between the neighbours of the best grid point. The browser demo uses the same
    algorithm, so the two agree to rounding."""
    lg = math.log(h_guess)
    xs = [lg - span + 2 * span * i / (k - 1) for i in range(k)]
    vals = [fun(math.exp(v)) for v in xs]
    i = int(np.argmin(vals))
    a = xs[max(i - 1, 0)]
    b = xs[min(i + 1, k - 1)]
    gr = (math.sqrt(5) - 1) / 2
    c = b - gr * (b - a)
    d = a + gr * (b - a)
    fc, fd = fun(math.exp(c)), fun(math.exp(d))
    for _ in range(iters):
        if fc < fd:
            b, d, fd = d, c, fc
            c = b - gr * (b - a)
            fc = fun(math.exp(c))
        else:
            a, c, fc = c, d, fd
            d = a + gr * (b - a)
            fd = fun(math.exp(d))
    x = 0.5 * (a + b)
    return math.exp(x), fun(math.exp(x))


def best_hist(name, n):
    return opt_h(lambda h: hist_mise_exact(name, n, h), hist_hstar(name, n))


def best_kde(name, n):
    return opt_h(lambda h: kde_mise_exact(name, n, h), kde_hstar(name, n))


def kde_mise_nd(d, n, h):
    """Exact MISE of the Gaussian product-kernel estimator with common bandwidth h for N(0, I_d)."""
    t = lambda v: (2 * math.pi * v) ** (-d / 2.0)
    return (t(2 * h * h) / n + (1 - 1.0 / n) * t(2 * h * h + 2) - 2 * t(h * h + 2) + t(2.0))


def rel_mse0(d, n, h):
    """Exact relative MSE at 0 of the Gaussian product-kernel estimator for N(0, I_d)."""
    f0 = (2 * math.pi) ** (-d / 2.0)
    m = (2 * math.pi * (1 + h * h)) ** (-d / 2.0)
    ek2 = ((2 * math.sqrt(math.pi) * h) ** -1 * (2 * math.pi * (1 + h * h / 2)) ** -0.5) ** d
    return ((ek2 - m * m) / n + (m - f0) ** 2) / f0 ** 2


def silverman_n(d, target=0.1):
    """The sample size at which the smallest (over h) relative MSE at 0 equals target, for N(0, I_d):
    Silverman (1986), Table 4.2, as quoted in Section 20.3."""
    def best(ln):
        n = math.exp(ln)
        r = optimize.minimize_scalar(lambda lh: rel_mse0(d, n, math.exp(lh)), bounds=(-8, 3),
                                     method="bounded", options={"xatol": 1e-11})
        return r.fun - target
    return math.exp(optimize.brentq(best, 0.0, 25.0, xtol=1e-12))


# =========================================================================== simulation steps of the demos
def sample_mixture(name, n, seed):
    """n draws from a Normal mixture with DK.rng(seed): for each draw one uniform picks the component
    and one Normal (Box-Muller, as in the browser) gives the value."""
    w, mu, s = _mix(name)
    cw = np.cumsum(w)
    g = JSRandom(seed)
    out = np.empty(n)
    for i in range(n):
        u = g.u()
        k = 0
        while k < len(cw) - 1 and u > cw[k]:
            k += 1
        out[i] = mu[k] + s[k] * g.norm()
    return out


def sample_truncated(name, n, seed, lo=-4.0, hi=4.0):
    """n draws from a Normal mixture restricted to (lo, hi), by rejection with DK.rng(seed): the
    simulated data of the histogram demo."""
    w, mu, s = _mix(name)
    cw = np.cumsum(w)
    g = JSRandom(seed)
    out = []
    while len(out) < n:
        u = g.u()
        k = 0
        while k < len(cw) - 1 and u > cw[k]:
            k += 1
        v = mu[k] + s[k] * g.norm()
        if lo < v < hi:
            out.append(v)
    return np.array(out)


def hist_expected_cv(name, n, m, lo=-4.0, hi=4.0):
    """E Jhat(h) = E J(h) = 1/(n h) - (1 + 1/n) sum p_j^2 / h for the m-bin histogram on (lo, hi) of the
    mixture restricted to (lo, hi): the exact risk minus the constant int f^2."""
    h = (hi - lo) / m
    c = mix_cdf(name, lo + h * np.arange(m + 1))
    p = np.diff(c) / (c[-1] - c[0])
    return 1.0 / (n * h) - (1.0 + 1.0 / n) * float(np.sum(p * p)) / h


def hist_ise(name, x, h, origin=0.0):
    """Exact integrated squared error of the histogram (bins anchored at origin) of the sample x:
    sum_j phat_j^2/h - 2 sum_j phat_j p_j/h + int f^2 (only occupied bins enter the sums)."""
    n = len(x)
    j = np.floor((np.asarray(x) - origin) / h).astype(np.int64)
    uj, cnt = np.unique(j, return_counts=True)
    ph = cnt / n
    p = mix_cdf(name, origin + (uj + 1) * h) - mix_cdf(name, origin + uj * h)
    return float(np.sum(ph * ph) / h - 2 * np.sum(ph * p) / h + _cross(name, 0.0))


KDE_GRID = 2048


def kde_grid_range(name):
    w, mu, s = _mix(name)
    return float(np.min(mu - 6 * s)), float(np.max(mu + 6 * s))


def kde_ise_binned(name, x, h, G=KDE_GRID):
    """Integrated squared error of the Gaussian kernel estimate, computed on a grid of G points over the
    mixture's mean +/- 6 sd: linear binning of the sample, the kernel truncated at 6h, and a Riemann sum.
    This is the computation of the smoothing-rates demo."""
    lo, hi = kde_grid_range(name)
    dl = (hi - lo) / (G - 1)
    n = len(x)
    pos = (np.clip(np.asarray(x), lo, hi) - lo) / dl
    i0 = np.minimum(np.floor(pos).astype(np.int64), G - 2)
    fr = pos - i0
    c = np.bincount(i0, weights=1 - fr, minlength=G) + np.bincount(i0 + 1, weights=fr, minlength=G)
    L = int(math.ceil(6 * h / dl))
    kk = np.exp(-0.5 * (np.arange(-L, L + 1) * dl / h) ** 2) / (SQ2PI * h)
    fh = np.convolve(c, kk, mode="full")[L:L + G] / n
    gx = lo + dl * np.arange(G)
    return float(np.sum((fh - mix_pdf(name, gx)) ** 2) * dl)


def kde_ise_exact(name, x, h):
    """Exact ISE of the Gaussian kernel estimate (O(n^2)): int fhat^2 - 2 int fhat f + int f^2."""
    x = np.asarray(x, float)
    n = len(x)
    w, mu, s = _mix(name)
    D = x[:, None] - x[None, :]
    a = np.sum(stats.norm.pdf(D, 0, math.sqrt(2) * h)) / n ** 2
    b = np.sum(w * stats.norm.pdf(x[:, None], mu, np.sqrt(h * h + s * s))) / n
    return float(a - 2 * b + _cross(name, 0.0))


# the simulation of the smoothing-rates demo: sample sizes and the seed of replicate r at size n
RATE_NS = [100, 200, 500, 1000, 2000, 5000, 10000]
RATE_SEED = 20000


def rate_seed(n_index, r):
    return RATE_SEED + 1000 * n_index + r


def rate_sim(name, R, ns=RATE_NS):
    """ISE of the histogram and of the kernel estimate at their exact-optimal widths, R replicates per n,
    with the demo's seeds."""
    out = {"hist": np.zeros((len(ns), R)), "kde": np.zeros((len(ns), R))}
    for k, n in enumerate(ns):
        hh = best_hist(name, n)[0]
        hk = best_kde(name, n)[0]
        for r in range(R):
            x = sample_mixture(name, n, rate_seed(k, r))
            out["hist"][k, r] = hist_ise(name, x, hh)
            out["kde"][k, r] = kde_ise_binned(name, x, hk)
    return out


def loglog_slope(ns, v):
    A = np.vstack([np.ones(len(ns)), np.log(ns)]).T
    return float(np.linalg.lstsq(A, np.log(v), rcond=None)[0][1])


# =========================================================================== reference numbers
def galaxy_summary():
    z = redshift()
    a, b = GALAXY_AB
    ms = np.arange(1, 1267)
    J = hist_cv_curve(z, a, b, ms)
    m_cv = int(ms[np.argmin(J)])
    near = ms[J <= J.min() + 0.03 * abs(J.min())]
    hs = geom_grid(1e-4, 1e-2, 121)
    Jk = kde_cv(z, hs)
    return dict(n=len(z), m_cv=m_cv, J_min=float(J.min()), J73=float(J[72]), near=(int(near.min()), int(near.max())),
                h_kde=float(hs[np.argmin(Jk)]), hs=hs, Jk=Jk, J=J, ms=ms)


def wmap_summary():
    x, y = wmap()
    hs = geom_grid(2.0, 150.0, 121)
    h_cv, J = cv_bandwidth(x, y, hs)
    return dict(x=x, y=y, hs=hs, J=J, h_cv=float(h_cv), sigma=math.sqrt(sigma2_diff(x, y)))


# =========================================================================== figures
def _style(ax):
    ax.spines["top"].set_visible(False)
    ax.spines["right"].set_visible(False)


def fig_20_2(out_dir=None):
    """The bias-variance trade-off, computed exactly for a kernel density estimate (n = 200, bimodal)."""
    name, n = "bimodal", 200
    hs = np.geomspace(0.03, 1.5, 300)
    P = np.array([kde_mise_exact(name, n, h, parts=True) for h in hs])
    hb, rb = best_kde(name, n)
    fig, ax = common.plt.subplots(figsize=(5.6, 3.4))
    ax.plot(hs, P[:, 2], color="k", lw=2, label="risk (MISE)")
    ax.plot(hs, P[:, 0], color=RED, lw=1.6, ls="--", label=r"integrated bias$^2$")
    ax.plot(hs, P[:, 1], color=BLUE, lw=1.6, ls="-.", label="integrated variance")
    ax.axvline(hb, color=GREY, lw=1)
    ax.set_xscale("log")
    ax.set_ylim(0, 0.06)
    ax.set_xlabel("bandwidth $h$ (log scale): more smoothing to the right")
    ax.set_ylabel("integrated squared error")
    ax.text(hb * 1.06, 0.055, "optimal $h$ = %.3f" % hb, fontsize=9, color=GREY)
    ax.legend(frameon=False, loc="upper center")
    _style(ax)
    savefig(fig, CH, "fig20-2", out_dir)


def fig_20_3(out_dir=None):
    """Histograms of the astronomy data with 10, 73 and 1000 bins, and the cross-validation score."""
    z = redshift()
    a, b = GALAXY_AB
    S = galaxy_summary()
    fig, axes = common.panel_grid(2, 2, size=(3.4, 2.7))
    for ax, m, lab in ((axes[0, 0], 10, "Oversmoothed (m = 10)"), (axes[0, 1], 73, "Just right (m = 73)"),
                       (axes[1, 0], 1000, "Undersmoothed (m = 1000)")):
        e, f = hist_density(z, m, a, b)
        ax.stairs(f, e, fill=True, color="#c9d6ea", edgecolor="k", lw=0.5)
        ax.set_title(lab)
        ax.set_xlim(a, b)
        _style(ax)
    ax = axes[1, 1]
    ax.plot(S["ms"], S["J"], color="k", lw=0.9)
    ax.axvline(S["m_cv"], color=RED, lw=1, ls="--")
    ax.axvline(73, color=BLUE, lw=1, ls=":")
    ax.set_ylim(-15, -5)
    ax.set_xlabel("number of bins $m$")
    ax.set_ylabel(r"cross-validation score $\widehat J$")
    ax.text(1250, -7.0, "minimum at m = %d" % S["m_cv"], color=RED, fontsize=8.5, ha="right")
    ax.text(1250, -8.0, "book's choice m = 73", color=BLUE, fontsize=8.5, ha="right")
    _style(ax)
    for ax in axes[:, 0]:
        ax.set_ylabel("density")
    for ax in (axes[0, 0], axes[0, 1], axes[1, 0]):
        ax.set_xlabel("redshift")
    fig.tight_layout()
    savefig(fig, CH, "fig20-3", out_dir)


def fig_20_4(out_dir=None):
    """95 percent envelope (20.17) for the histogramised density of the astronomy data, m = 73."""
    z = redshift()
    a, b = GALAXY_AB
    e, f, lo, up, c = hist_band(z, 73, a, b)
    fig, ax = common.plt.subplots(figsize=(5.8, 3.2))
    ax.stairs(up, e, baseline=lo, fill=True, color="#f4c7c3", lw=0)
    ax.stairs(up, e, color=RED, lw=0.8)
    ax.stairs(lo, e, color=RED, lw=0.8)
    ax.stairs(f, e, color="k", lw=1.0)
    ax.set_xlim(a, b)
    ax.set_ylim(0, None)
    ax.set_xlabel("redshift")
    ax.set_ylabel("density")
    _style(ax)
    savefig(fig, CH, "fig20-4", out_dir)


def fig_20_5(out_dir=None):
    """A kernel density estimate as the average of kernels centred at the data (8 points, h = 1)."""
    g = JSRandom(2005)
    x = np.array([-6 + 3.2 * g.norm() if i < 5 else 4 + 1.6 * g.norm() for i in range(8)])
    grid = np.linspace(-10, 10, 800)
    h = 1.0
    fig, ax = common.plt.subplots(figsize=(5.8, 2.8))
    for xi in x:
        ax.plot(grid, k_gauss((grid - xi) / h) / (len(x) * h), color=BLUE, lw=0.9, ls="--")
    ax.plot(grid, kde(x, grid, h), color="k", lw=2)
    ax.plot(x, np.full(len(x), -0.004), "|", color="k", ms=12, mew=1.4)
    ax.set_xlim(-10, 10)
    ax.set_yticks([])
    ax.set_xlabel("$x$")
    _style(ax)
    ax.spines["left"].set_visible(False)
    savefig(fig, CH, "fig20-5", out_dir)


def fig_20_6(out_dir=None):
    """Kernel density estimates of the astronomy data and the cross-validation curve."""
    z = redshift()
    S = galaxy_summary()
    hcv = S["h_kde"]
    grid = np.linspace(0, 0.2, 1200)
    fig, axes = common.panel_grid(2, 2, size=(3.4, 2.6))
    for ax, h, lab in ((axes[0, 0], 0.005, "Oversmoothed (h = 0.005)"),
                       (axes[0, 1], hcv, "Just right (h = %.5f, by CV)" % hcv),
                       (axes[1, 0], 0.0001, "Undersmoothed (h = 0.0001)")):
        ax.plot(grid, kde(z, grid, h), color="k", lw=0.9)
        ax.set_title(lab)
        ax.set_xlim(0, 0.2)
        ax.set_ylim(0, None)
        ax.set_xlabel("redshift")
        _style(ax)
    ax = axes[1, 1]
    ax.plot(S["hs"], S["Jk"], color="k", lw=1.2)
    ax.axvline(hcv, color=RED, lw=1, ls="--")
    ax.set_xscale("log")
    ax.set_ylim(S["Jk"].min() - 0.3, S["Jk"].min() + 4)
    ax.set_xlabel("bandwidth $h$ (log scale)")
    ax.set_ylabel(r"$\widehat J(h)$")
    _style(ax)
    fig.tight_layout()
    savefig(fig, CH, "fig20-6", out_dir)


def fig_20_7(out_dir=None):
    """95 percent band (20.27) for the smoothed density of the astronomy data, h from cross-validation."""
    z = redshift()
    h = galaxy_summary()["h_kde"]
    grid = np.linspace(0, 0.2, 1200)
    f, lo, up, q, m = kde_band(z, grid, h, *GALAXY_AB)
    fig, ax = common.plt.subplots(figsize=(5.8, 3.2))
    ax.fill_between(grid, np.maximum(lo, 0), up, color="#f4c7c3", lw=0)
    ax.plot(grid, f, color="k", lw=0.8)
    ax.set_xlim(0, 0.2)
    ax.set_ylim(0, None)
    ax.set_xlabel("redshift")
    ax.set_ylabel("density")
    ax.text(0.005, 0.93 * ax.get_ylim()[1], "h = %.5f, m = %.0f, q = %.2f" % (h, m, q), fontsize=9)
    _style(ax)
    savefig(fig, CH, "fig20-7", out_dir)


def fig_20_8(out_dir=None):
    """Nadaraya-Watson fits to the CMB (WMAP) data: undersmoothed, oversmoothed, cross-validated, and
    the estimated risk."""
    W = wmap_summary()
    x, y = W["x"], W["y"]
    grid = np.linspace(x.min(), x.max(), 600)
    fig, axes = common.panel_grid(2, 2, size=(3.4, 2.7))
    for ax, h, lab in ((axes[0, 0], 3.0, "Undersmoothed (h = 3)"), (axes[0, 1], 60.0, "Oversmoothed (h = 60)"),
                       (axes[1, 0], W["h_cv"], "Just right (h = %.1f, by CV)" % W["h_cv"])):
        ax.plot(x, y, ".", color=GREY, ms=2.5)
        ax.plot(grid, nw_fit(x, y, grid, h), color="k", lw=1.4)
        ax.set_title(lab)
        ax.set_xlabel("multipole $\\ell$")
        ax.set_ylim(-3000, 9500)
        _style(ax)
    ax = axes[1, 1]
    ax.plot(W["hs"], W["J"] / len(x), color="k", lw=1.2)
    ax.set_ylim(0.97 * W["J"].min() / len(x), 1.6 * W["J"].min() / len(x))
    ax.axvline(W["h_cv"], color=RED, lw=1, ls="--")
    ax.set_xscale("log")
    ax.set_xlabel("bandwidth $h$ (log scale)")
    ax.set_ylabel(r"$\widehat J(h)/n$")
    _style(ax)
    for a in axes[:, 0]:
        a.set_ylabel("power")
    fig.tight_layout()
    savefig(fig, CH, "fig20-8", out_dir)


def fig_20_9(out_dir=None):
    """95 percent band (20.37) for the smoothed CMB power spectrum."""
    W = wmap_summary()
    x, y = W["x"], W["y"]
    grid = np.linspace(x.min(), x.max(), 600)
    r, lo, up, q, m, s = reg_band(x, y, grid, W["h_cv"])
    fig, ax = common.plt.subplots(figsize=(5.8, 3.3))
    ax.plot(x, y, ".", color=GREY, ms=2.2)
    ax.fill_between(grid, lo, up, color="#c9d6ea", lw=0, alpha=0.9)
    ax.plot(grid, lo, color=BLUE, lw=1)
    ax.plot(grid, up, color=BLUE, lw=1)
    ax.plot(grid, r, color="k", lw=1)
    ax.set_ylim(-3000, 9500)
    ax.set_xlabel("multipole $\\ell$")
    ax.set_ylabel("power")
    ax.text(30, 8600, "h = %.1f, $\\hat\\sigma$ = %.0f, m = %.1f, q = %.2f" % (W["h_cv"], s, m, q), fontsize=9)
    _style(ax)
    savefig(fig, CH, "fig20-9", out_dir)


def fig_20_S1(out_dir=None):
    """The rates n^(-2/3) (histogram) and n^(-4/5) (kernel): exact risks at the optimal width and
    simulated integrated squared errors."""
    fig, axes = common.panel_grid(1, 2, size=(3.6, 3.2))
    ns = np.geomspace(20, 1e6, 40)
    for ax, name, title in ((axes[0, 0], "normal", "N(0, 1)"), (axes[0, 1], "bimodal", "bimodal mixture")):
        mh = np.array([best_hist(name, n)[1] for n in ns])
        mk = np.array([best_kde(name, n)[1] for n in ns])
        ax.loglog(ns, mh, color=RED, lw=1.8, label="histogram, exact")
        ax.loglog(ns, mk, color=BLUE, lw=1.8, label="kernel, exact")
        Rh = (0.75) ** (2 / 3) * mix_R(name, 1) ** (1 / 3) * ns ** (-2 / 3)
        Rk = 1.25 * (1 / (2 * math.sqrt(math.pi))) ** 0.8 * mix_R(name, 2) ** 0.2 * ns ** (-0.8)
        ax.loglog(ns, Rh, color=RED, lw=1, ls="--", label="(20.12)")
        ax.loglog(ns, Rk, color=BLUE, lw=1, ls="--", label="$c_4 n^{-4/5}$")
        sim = rate_sim(name, 50)
        nn = np.array(RATE_NS)
        for key, col in (("hist", RED), ("kde", BLUE)):
            mu = sim[key].mean(1)
            se = sim[key].std(1, ddof=1) / math.sqrt(sim[key].shape[1])
            ax.errorbar(nn, mu, yerr=2 * se, fmt="o", ms=3.5, color=col, mfc="white", lw=1)
        sh = loglog_slope(ns[ns >= 1e3], mh[ns >= 1e3])
        sk = loglog_slope(ns[ns >= 1e3], mk[ns >= 1e3])
        ax.set_title("%s: slopes %.3f and %.3f" % (title, sh, sk), fontsize=9.5)
        ax.set_xlabel("$n$")
        _style(ax)
    axes[0, 0].set_ylabel("MISE at the optimal width")
    axes[0, 0].legend(frameon=False, fontsize=8, loc="lower left")
    fig.tight_layout()
    savefig(fig, CH, "fig20-S1", out_dir)


SILVERMAN_TABLE = [4, 19, 67, 223, 768, 2790, 10700, 43700, 187000, 842000]


def fig_20_S2(out_dir=None):
    """The curse of dimensionality: Silverman's table recomputed and the exact optimal MISE in d dims."""
    fig, axes = common.panel_grid(1, 2, size=(3.6, 3.2))
    ds = np.arange(1, 11)
    nreq = np.array([silverman_n(d) for d in ds])
    ax = axes[0, 0]
    ax.semilogy(ds, np.ceil(nreq), "o-", color=BLUE, ms=4, label="recomputed (exact MSE)")
    ax.semilogy(ds, SILVERMAN_TABLE, "x", color=RED, ms=7, label="table in Section 20.3")
    ax.set_xlabel("dimension $d$")
    ax.set_ylabel("sample size needed")
    ax.legend(frameon=False, fontsize=8)
    _style(ax)
    ax = axes[0, 1]
    ns = np.geomspace(10, 1e7, 30)
    cols = [RED, ORANGE, GREEN, BLUE, PURPLE]
    for d, col in zip((1, 2, 4, 6, 10), cols):
        v = []
        for n in ns:
            h0 = n ** (-1.0 / (4 + d))
            v.append(opt_h(lambda h: kde_mise_nd(d, n, h) * (4 * math.pi) ** (d / 2.0), h0)[1])
        v = np.array(v)
        ax.loglog(ns, v, color=col, lw=1.6, label="d = %d (slope %.2f)" % (d, loglog_slope(ns[-10:], v[-10:])))
    ax.set_xlabel("$n$")
    ax.set_ylabel(r"optimal MISE / $\int f^2$")
    ax.legend(frameon=False, fontsize=7.5, loc="lower left")
    _style(ax)
    fig.tight_layout()
    savefig(fig, CH, "fig20-S2", out_dir)


def fig_20_S3(out_dir=None):
    """Rounded data and cross-validation: the score for the redshifts as recorded, rounded to 0.001,
    and rounded then jittered; and the exact expectation of the score against simulated scores."""
    z = redshift()
    hs = geom_grid(1e-6, 1e-2, 101)
    zr = np.round(z, 3)
    g = JSRandom(2017)
    zj = zr + 0.0005 * np.array([g.norm() for _ in range(len(z))])
    fig, axes = common.panel_grid(1, 2, size=(3.6, 3.2))
    ax = axes[0, 0]
    for data, col, lab in ((z, "k", "as recorded"), (zr, RED, "rounded to 0.001"), (zj, BLUE, "rounded, then jittered")):
        J = kde_cv(data, hs)
        ax.semilogx(hs, J, color=col, lw=1.4, label=lab)
        i = int(np.argmin(J))
        ax.plot(hs[i], J[i], "o", color=col, ms=4)
    ax.set_ylim(-40, 30)
    ax.set_xlabel("bandwidth $h$ (log scale)")
    ax.set_ylabel(r"$\widehat J(h)$")
    ax.legend(frameon=False, fontsize=8, loc="upper right")
    _style(ax)
    ax = axes[0, 1]
    name, n = "bimodal", 200
    hs2 = np.geomspace(0.05, 1.5, 40)
    EJ = np.array([kde_mise_exact(name, n, h) - _cross(name, 0.0) for h in hs2])
    sims = []
    for r in range(200):
        x = sample_mixture(name, n, 70000 + r)
        sims.append(kde_cv(x, hs2))
    sims = np.array(sims)
    for r in range(8):
        ax.semilogx(hs2, sims[r], color=GREY, lw=0.6)
    ax.semilogx(hs2, sims.mean(0), color=BLUE, lw=1.6, ls="--", label="average of 200 scores")
    ax.semilogx(hs2, EJ, color="k", lw=1.6, label=r"exact $\mathbb{E}J(h)$ = MISE $-\int f^2$")
    ax.set_xlabel("bandwidth $h$ (log scale)")
    ax.set_ylabel(r"$\widehat J(h)$")
    ax.legend(frameon=False, fontsize=8, loc="upper center")
    _style(ax)
    fig.tight_layout()
    savefig(fig, CH, "fig20-S3", out_dir)


COVER_A, COVER_B = -3.0, 3.0       # the interval (a, b) of the coverage study (bimodal mixture)
COVER_X = 1.0                      # a mode of the bimodal mixture (f'' < 0 there)


def _bimodal_sample(rng, n):
    w, mu, s = _mix("bimodal")
    comp = rng.choice(len(w), size=n, p=w)
    x = mu[comp] + s[comp] * rng.standard_normal(n)
    return x[(x > COVER_A) & (x < COVER_B)]


def kde_fbar(name, x, h):
    """fbar_h = K_h * f for a Normal mixture and the Gaussian kernel."""
    w, mu, s = _mix(name)
    return np.sum(w * stats.norm.pdf(np.asarray(x, float)[..., None], mu, np.sqrt(s * s + h * h)), axis=-1)


def pointwise_limit(name, x0, alpha=0.05):
    """Large-n coverage of fhat(x0) +/- z se for f(x0) when h = h* (20.23): the bias-to-sd ratio tends to
    b = (h*^2 f''/2) / sqrt(f int K^2/(n h*)), a constant, and the coverage to P(|Z + b| <= z)."""
    w, mu, s = _mix(name)
    f0 = float(mix_pdf(name, x0))
    f2 = float(np.sum(w * _phi_deriv(x0 - mu, s * s, 2)))
    c = (1.0 / (2 * math.sqrt(math.pi)) / mix_R(name, 2)) ** 0.2     # h* = c n^(-1/5)
    b = (c * c * f2 / 2.0) / math.sqrt(f0 / (2 * math.sqrt(math.pi)) / c)
    z = stats.norm.isf(alpha / 2)
    return float(stats.norm.cdf(z - b) - stats.norm.cdf(-z - b)), b


def band_coverage(seed=2050):
    """Simulated coverage, bimodal mixture on (-3, 3).
    sim: simultaneous coverage over [-2.5, 2.5] of the histogram envelope (20.17) for fbar (h near the
    optimal width), and of the kernel band (20.27) for fbar_h and for f (h = h*); R = 300 per n.
    pt: pointwise coverage at the mode x = 1 of fhat(1) +/- z_{0.025} se(1), for fbar_h(1) and f(1) at
    h = h*, and for f(1) at the undersmoothed h* n^(-1/10); R = 2000 per n."""
    cache = os.path.join(CACHE_DIR, "ch20_band_coverage_s%d.npz" % seed)
    if os.path.exists(cache):
        d = np.load(cache)
        return {k: d[k] for k in d.files}
    name = "bimodal"
    a, b = COVER_A, COVER_B
    rng = np.random.default_rng(seed)
    ns_sim = np.array([250, 1000, 4000])
    ns_pt = np.array([250, 1000, 4000, 16000])
    grid = np.linspace(-2.5, 2.5, 101)
    ftrue = mix_pdf(name, grid)
    sim = np.zeros((len(ns_sim), 3))
    for k, n in enumerate(ns_sim):
        m = int(round((b - a) / hist_hstar(name, n)))
        hh = (b - a) / m
        edges = a + hh * np.arange(m + 1)
        fbar_hist = np.diff(mix_cdf(name, edges)) / hh
        mid = 0.5 * (edges[1:] + edges[:-1])
        inner = (mid > -2.5) & (mid < 2.5)
        hk = kde_hstar(name, n)
        fbar = kde_fbar(name, grid, hk)
        R = 300
        for r in range(R):
            x = _bimodal_sample(rng, n)
            e, f, lo, up, c = hist_band(x, m, a, b)
            sim[k, 0] += np.all((lo <= fbar_hist)[inner] & (fbar_hist <= up)[inner])
            fk, lo2, up2, q, mm = kde_band(x, grid, hk, a, b)
            sim[k, 1] += np.all((lo2 <= fbar) & (fbar <= up2))
            sim[k, 2] += np.all((lo2 <= ftrue) & (ftrue <= up2))
        sim[k] /= R
    pt = np.zeros((len(ns_pt), 3))
    z = stats.norm.isf(0.025)
    f1 = float(mix_pdf(name, COVER_X))
    for k, n in enumerate(ns_pt):
        hk = kde_hstar(name, n)
        R = 2000
        for t, h in enumerate((hk, hk * n ** (-0.1))):
            fb = float(kde_fbar(name, COVER_X, h))
            for r in range(R):
                x = _bimodal_sample(rng, n)
                Y = k_gauss((COVER_X - x) / h) / h
                est, se = Y.mean(), Y.std(ddof=1) / math.sqrt(len(x))
                if t == 0:
                    pt[k, 0] += abs(est - fb) <= z * se
                    pt[k, 1] += abs(est - f1) <= z * se
                else:
                    pt[k, 2] += abs(est - f1) <= z * se
        pt[k] /= R
    out = {"ns_sim": ns_sim, "sim": sim, "ns_pt": ns_pt, "pt": pt}
    os.makedirs(CACHE_DIR, exist_ok=True)
    np.savez(cache, **out)
    return out


REG_R = lambda t: np.sin(2 * np.pi * t) + 2 * t
REG_SIGMA = 0.5
REG_X0 = 0.25                       # a maximum of sin(2 pi x): r'' = -(2 pi)^2 there


def reg_hstar(n):
    """Asymptotically optimal h for the Gaussian-kernel smoother, uniform design on [0, 1]:
    (sigma^2 int K^2 / (n int r''^2))^(1/5) with int r''^2 = (2 pi)^4 / 2."""
    return (REG_SIGMA ** 2 / (2 * math.sqrt(math.pi)) / (n * (2 * np.pi) ** 4 * 0.5)) ** 0.2


def reg_coverage(seed=2051):
    """Pointwise coverage at x = 0.25 of rhat(x) +/- z sigmahat sqrt(sum w_i^2) for rbar(x) and r(x)
    (h = h*, and undersmoothed h* n^(-1/10)), and simultaneous coverage of the band (20.37) for rbar
    on [0.1, 0.9]; equally spaced design, sigma = 0.5, R = 1000 per n."""
    cache = os.path.join(CACHE_DIR, "ch20_reg_coverage_s%d.npz" % seed)
    if os.path.exists(cache):
        d = np.load(cache)
        return {k: d[k] for k in d.files}
    rng = np.random.default_rng(seed)
    ns = np.array([100, 400, 1600, 6400])
    z = stats.norm.isf(0.025)
    out = np.zeros((len(ns), 4))
    grid = np.linspace(0.1, 0.9, 81)
    for k, n in enumerate(ns):
        x = (np.arange(n) + 0.5) / n
        R = 1000
        for t, h in enumerate((reg_hstar(n), reg_hstar(n) * n ** (-0.1))):
            w0 = nw_matrix(x, [REG_X0], h)[0]
            rb0 = float(w0 @ REG_R(x))
            sw = math.sqrt(float(w0 @ w0))
            if t == 0:
                L = nw_matrix(x, grid, h)
                rbar = L @ REG_R(x)
                swg = np.sqrt((L * L).sum(1))
                mm = (x.max() - x.min()) / (3 * h)
                q = stats.norm.ppf((1 + 0.95 ** (1 / mm)) / 2)
            for r in range(R):
                y = REG_R(x) + REG_SIGMA * rng.standard_normal(n)
                s = math.sqrt(sigma2_diff(x, y))
                est = float(w0 @ y)
                if t == 0:
                    out[k, 0] += abs(est - rb0) <= z * s * sw
                    out[k, 1] += abs(est - REG_R(REG_X0)) <= z * s * sw
                    rr = L @ y
                    out[k, 3] += np.all(np.abs(rr - rbar) <= q * s * swg)
                else:
                    out[k, 2] += abs(est - REG_R(REG_X0)) <= z * s * sw
        out[k] /= R
    res = {"ns": ns, "cov": out}
    os.makedirs(CACHE_DIR, exist_ok=True)
    np.savez(cache, **res)
    return res


def reg_pointwise_limit(alpha=0.05):
    """Large-n coverage for r(0.25) at h = h*: bias h^2 r''/2 over sd sigma sqrt(int K^2/(n h))."""
    c = reg_hstar(1)
    b = (c * c * (-(2 * np.pi) ** 2) / 2.0) / (REG_SIGMA * math.sqrt(1 / (2 * math.sqrt(math.pi)) / c))
    z = stats.norm.isf(alpha / 2)
    return float(stats.norm.cdf(z - b) - stats.norm.cdf(-z - b)), b


def fig_20_S4(out_dir=None):
    """Confidence bands cover the smoothed curve, not the curve: simulated coverage."""
    B = band_coverage()
    Rg = reg_coverage()
    lim_d, bd = pointwise_limit("bimodal", COVER_X)
    lim_r, br = reg_pointwise_limit()
    fig, axes = common.panel_grid(1, 3, size=(2.95, 3.1))
    ax = axes[0, 0]
    ns = B["ns_sim"]
    ax.semilogx(ns, B["sim"][:, 0], "o-", color=PURPLE, label=r"histogram (20.17), $\bar f_n$")
    ax.semilogx(ns, B["sim"][:, 1], "s-", color=BLUE, label=r"kernel (20.27), $\bar f_n$")
    ax.semilogx(ns, B["sim"][:, 2], "^--", color=RED, label="kernel (20.27), $f$")
    ax.set_title("whole band on [-2.5, 2.5]", fontsize=9)
    ax.set_ylabel("coverage")
    ax = axes[0, 1]
    ns = B["ns_pt"]
    ax.semilogx(ns, B["pt"][:, 0], "o-", color=BLUE, label=r"$\bar f_n(1)$, $h = h^*$")
    ax.semilogx(ns, B["pt"][:, 1], "s--", color=RED, label="$f(1)$, $h = h^*$")
    ax.semilogx(ns, B["pt"][:, 2], "^:", color=GREEN, label="$f(1)$, $h = h^* n^{-1/10}$")
    ax.axhline(lim_d, color=RED, lw=0.8, ls=(0, (1, 2)))
    ax.set_title("kernel density, at the mode $x = 1$", fontsize=9)
    ax = axes[0, 2]
    nr = Rg["ns"]
    ax.semilogx(nr, Rg["cov"][:, 0], "o-", color=BLUE, label=r"$\bar r_n(0.25)$, $h = h^*$")
    ax.semilogx(nr, Rg["cov"][:, 1], "s--", color=RED, label="$r(0.25)$, $h = h^*$")
    ax.semilogx(nr, Rg["cov"][:, 2], "^:", color=GREEN, label="$r(0.25)$, undersmoothed")
    ax.semilogx(nr, Rg["cov"][:, 3], "d-", color=GREY, label=r"band (20.37), $\bar r_n$")
    ax.axhline(lim_r, color=RED, lw=0.8, ls=(0, (1, 2)))
    ax.set_title("regression, at the peak $x = 0.25$", fontsize=9)
    for a_ in axes[0]:
        a_.axhline(0.95, color="k", lw=0.7, ls="--")
        a_.set_ylim(0.6, 1.02)
        a_.set_xlabel("$n$")
        _style(a_)
        a_.legend(frameon=False, fontsize=7, loc="lower right")
    fig.tight_layout()
    savefig(fig, CH, "fig20-S4", out_dir)



DESIGN_DENS = lambda t: 1.5 - t        # design density on [0, 1] (decreasing), integrates to 1


def design_points(n):
    """Fixed design with density 1.5 - x on [0, 1]: x_i = G^{-1}((i - 1/2)/n), G(x) = 1.5x - x^2/2."""
    u = (np.arange(n) + 0.5) / n
    return 1.5 - np.sqrt(2.25 - 2 * u)


def fig_20_S5(out_dir=None):
    """Exact bias E rhat - r of Nadaraya-Watson and local linear regression on a non-uniform design,
    with the asymptotic bias h^2 (r''/2 + r' f'/f) of (20.33) and its local linear form h^2 r''/2."""
    n, h = 400, 0.06
    x = design_points(n)
    rfun = lambda t: np.sin(2 * np.pi * t) + 2 * t
    r1 = lambda t: 2 * np.pi * np.cos(2 * np.pi * t) + 2
    r2 = lambda t: -(2 * np.pi) ** 2 * np.sin(2 * np.pi * t)
    grid = np.linspace(0, 1, 401)
    bn = nw_matrix(x, grid, h) @ rfun(x) - rfun(grid)
    bl = ll_matrix(x, grid, h) @ rfun(x) - rfun(grid)
    an = h * h * (0.5 * r2(grid) + r1(grid) * (-1.0) / DESIGN_DENS(grid))
    al = h * h * 0.5 * r2(grid)
    fig, axes = common.panel_grid(1, 2, size=(3.6, 3.1))
    ax = axes[0, 0]
    ax.plot(grid, bn, color=RED, lw=1.8, label="Nadaraya-Watson, exact")
    ax.plot(grid, an, color=RED, lw=1, ls="--", label=r"$h^2(r''/2 + r'f'/f)$")
    ax.plot(grid, bl, color=BLUE, lw=1.8, label="local linear, exact")
    ax.plot(grid, al, color=BLUE, lw=1, ls="--", label=r"$h^2 r''/2$")
    ax.axhline(0, color=GREY, lw=0.6)
    ax.set_xlabel("$x$")
    ax.set_ylabel(r"bias $\mathbb{E}\,\hat r(x) - r(x)$")
    ax.set_title("design density $1.5 - x$, $n$ = 400, $h$ = 0.06", fontsize=9)
    ax.legend(frameon=False, fontsize=7.5, loc="lower left")
    _style(ax)
    ax = axes[0, 1]
    xm, ym = motor()
    hs = geom_grid(0.5, 10.0, 121)
    hn, Jn = cv_bandwidth(xm, ym, hs, "nw")
    hl, Jl = cv_bandwidth(xm, ym, hs, "ll")
    g2 = np.linspace(xm.min(), xm.max(), 500)
    ax.plot(xm, ym, ".", color=GREY, ms=3.5)
    ax.plot(g2, nw_matrix(xm, g2, hn) @ ym, color=RED, lw=1.5, label="Nadaraya-Watson, h = %.2f" % hn)
    ax.plot(g2, ll_matrix(xm, g2, hl) @ ym, color=BLUE, lw=1.5, label="local linear, h = %.2f" % hl)
    ax.set_xlabel("time after impact (ms)")
    ax.set_ylabel("acceleration (g)")
    ax.set_title("motorcycle data, h by cross-validation", fontsize=9)
    ax.legend(frameon=False, fontsize=7.5, loc="lower right")
    _style(ax)
    fig.tight_layout()
    savefig(fig, CH, "fig20-S5", out_dir)


def glass_summary():
    ri, al = glass()
    a, b = GLASS_AB
    ms = np.arange(1, 201)
    J = hist_cv_curve(ri, a, b, ms)
    m_cv = int(ms[np.argmin(J)])
    hs = geom_grid(0.02, 3.0, 121)
    Jk = kde_cv(ri, hs)
    h_kde = float(hs[np.argmin(Jk)])
    hr = geom_grid(0.03, 1.5, 121)
    h_reg, Jr = cv_bandwidth(al, ri, hr)
    return dict(ri=ri, al=al, ms=ms, J=J, m_cv=m_cv, hs=hs, Jk=Jk, h_kde=h_kde, hr=hr, Jr=Jr, h_reg=float(h_reg))


def fig_20_S6(out_dir=None):
    """Exercises 20.2 and 20.3: the glass data, histogram and kernel estimates of the refractive index
    with cross-validation and 95 percent bands, and the regression of refractive index on aluminium."""
    G = glass_summary()
    ri, al = G["ri"], G["al"]
    a, b = GLASS_AB
    fig, axes = common.panel_grid(1, 3, size=(3.1, 3.0))
    ax = axes[0, 0]
    e, f, lo, up, c = hist_band(ri, G["m_cv"], a, b)
    ax.stairs(up, e, baseline=lo, fill=True, color="#f4c7c3", lw=0)
    ax.stairs(f, e, color="k", lw=1)
    grid = np.linspace(a, b, 800)
    fk, lk, uk, q, m = kde_band(ri, grid, G["h_kde"], a, b)
    ax.set_title("histogram, m = %d by CV" % G["m_cv"], fontsize=9)
    ax.set_xlabel("refractive index (RI)")
    ax.set_ylabel("density")
    ax = axes[0, 1]
    ax.fill_between(grid, np.maximum(lk, 0), uk, color="#c9d6ea", lw=0)
    ax.plot(grid, fk, color="k", lw=1)
    ax.set_title("kernel, h = %.3f by CV" % G["h_kde"], fontsize=9)
    ax.set_xlabel("refractive index (RI)")
    ax = axes[0, 2]
    g2 = np.linspace(al.min(), al.max(), 400)
    r, lo2, up2, q2, m2, s = reg_band(al, ri, g2, G["h_reg"])
    ax.plot(al, ri, ".", color=GREY, ms=3)
    ax.fill_between(g2, lo2, up2, color="#c9d6ea", lw=0, alpha=0.9)
    ax.plot(g2, r, color="k", lw=1.3)
    ax.set_title("RI on Al, h = %.3f by CV" % G["h_reg"], fontsize=9)
    ax.set_xlabel("aluminium (Al)")
    ax.set_ylabel("RI")
    for a_ in axes[0]:
        _style(a_)
    fig.tight_layout()
    savefig(fig, CH, "fig20-S6", out_dir)


# =========================================================================== data for the demos
def export_json():
    os.makedirs(DATA_OUT, exist_ok=True)
    z = redshift()
    ri, al = glass()
    with open(os.path.join(DATA_OUT, "ch20-densities.json"), "w") as f:
        json.dump({"galaxy": [round(float(v), 6) for v in z], "glassRI": [float(v) for v in ri]}, f, separators=(",", ":"))
    xw, yw = wmap()
    xm, ym = motor()
    with open(os.path.join(DATA_OUT, "ch20-regression.json"), "w") as f:
        json.dump({"wmap": {"x": [float(v) for v in xw], "y": [round(float(v), 4) for v in yw]},
                   "motor": {"x": [float(v) for v in xm], "y": [float(v) for v in ym]},
                   "glass": {"x": [float(v) for v in al], "y": [float(v) for v in ri]}}, f, separators=(",", ":"))
    print("wrote ../data/ch20-densities.json and ../data/ch20-regression.json")


def _all_with_export(fun):
    def wrapped(out_dir=None):
        fun(out_dir)
        export_json()
    wrapped.__doc__ = fun.__doc__
    return wrapped


FIGURES = {
    "20.2": fig_20_2, "20.3": fig_20_3, "20.4": fig_20_4, "20.5": fig_20_5, "20.6": fig_20_6,
    "20.7": fig_20_7, "20.8": fig_20_8, "20.9": _all_with_export(fig_20_9),
    "20.S1": fig_20_S1, "20.S2": fig_20_S2, "20.S3": fig_20_S3, "20.S4": fig_20_S4, "20.S5": fig_20_S5,
    "20.S6": fig_20_S6,
}

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