"""Hastie, Tibshirani and Friedman (2009), Chapter 6: Kernel Smoothing Methods.

Reproduces the figures of Chapter 6 of T. Hastie, R. Tibshirani and J. Friedman, The Elements of
Statistical Learning, 2nd edition (Springer, 2009), pp. 191-218, written from scratch with numpy,
scipy and matplotlib. Every method the chapter is about is implemented here as a small function
meant to be read next to the lecture notes (../ch06-kernel-smoothing.html):

* Section 6.1, one-dimensional kernel smoothers: the kernels D(t) of (6.4) and (6.6) and the Gaussian
  (KERNELS), metric and nearest-neighbour window widths (window_width, kernel_weights), the
  k-nearest-neighbour running mean (6.1) and the Nadaraya-Watson average (6.2).
* Sections 6.1.1-6.1.2, local polynomial regression: equivalent_kernel returns the weights l_i(x0)
  of (6.8)-(6.9) for any degree (0 = Nadaraya-Watson, 1 = local linear (6.7), 2 = local quadratic
  (6.11)); local_poly_fit evaluates the fit on a grid; smoother_matrix is S_lambda of Section 6.2;
  kernel_moments are the sums b_j(x0) of Exercise 6.2.
* Section 6.2, selecting the width: effective degrees of freedom trace(S), the leave-one-out
  shortcut of Exercise 6.7 (loocv_local_poly), generalised cross-validation and C_p (6.35); the
  smoothing-spline smoother matrix (spline_smoother) calibrated to the same degrees of freedom.
* Section 6.3, local regression in R^p: local_linear_2d (radial tri-cube kernel, nearest-neighbour
  window, local plane), used on the galaxy data.
* Section 6.4, structured local regression: varying_coefficient fits (6.17), with local linear terms
  in the conditioning variable if asked (Exercise 6.6) and pointwise standard errors.
* Section 6.5, local likelihood: local_logistic maximises the kernel-weighted log-likelihood (6.19)
  for two classes by Newton-Raphson (degree 0 or 1), with sandwich standard errors.
* Section 6.6, kernel density estimation and classification: kde (6.22)-(6.23), Silverman's rules,
  least-squares and likelihood cross-validation for the bandwidth (lscv_gauss, lcv_gauss), the
  kernel density classifier (6.25) and a kernel naive Bayes classifier (6.26)-(6.27).
* Section 6.7, radial basis functions: rbf_basis, with and without the renormalisation (6.30).
* Section 6.8, mixture models: em_gauss_1d fits the one-dimensional Gaussian mixture (6.32) by EM
  and returns the responsibilities (6.33).
* Exercise 6.12: local_lda (local linear discriminant analysis with Gaussian kernel weights),
  run on the zip-code data. The weights use Euclidean distances between the 256-pixel images; the
  discriminant functions are computed in the space of the first 40 principal components of the
  training images (a weighted 256 x 256 covariance at each of thousands of query points would be
  slow and, for narrow kernels, singular). lambda = 4, 6, 8, 12 and infinity (ordinary LDA).

Figures reproduced: 6.1, 6.2, 6.3, 6.4, 6.5, 6.6, 6.7, 6.8, 6.9, 6.12, 6.13, 6.14, 6.15, 6.16,
6.17, plus two supplementary figures: 6.S1 (a varying-coefficient model on the Los Angeles ozone
data, standing in for Figures 6.10-6.11) and 6.S2 (training and test error of local linear
discriminant analysis on the zip-code data, Exercise 6.12). Run `python3 ch06_kernel_smoothing.py
--list`, `python3 ch06_kernel_smoothing.py` (all figures, about two minutes the first time; the
zip-code computation is cached in cache/) or `python3 ch06_kernel_smoothing.py --fig 6.12`.
Files go to ../img/ch06/. The data the browser demonstrations use are written to ../data/ by
export_demo_data() (called from Figures 6.1 and 6.12).

Figures not reproduced, and why:
* Figures 6.10 and 6.11 (aorta diameter against age, with coefficients varying with depth and
  gender) use measurements of the human aorta that are not distributed with the book. Figure 6.S1
  shows the same kind of varying-coefficient fit (6.17) on the book's Los Angeles ozone data.

Settings chosen where the book gives none:
* Figures 6.1-6.6: N = 100, X ~ U[0, 1], Y = sin(4X) + eps with eps ~ N(0, (1/3)^2) (standard
  deviation 1/3, which matches the scatter in the book's figure), drawn with
  numpy.random.default_rng(6). Figure 6.1: target x0 = 0.5, 30 nearest neighbours, Epanechnikov
  lambda = 0.2. Figures 6.3-6.4: Epanechnikov (Nadaraya-Watson) and tri-cube (local linear)
  kernels with lambda = 0.2 at the boundary target x0 = 0.05 and the interior target x0 = 0.4.
  Figure 6.5: tri-cube kernel, lambda = 0.25, x0 = 0.4. Figure 6.6: tri-cube, lambda = 0.2.
* Figure 6.7: local linear regression with a tri-cube kernel and a nearest-neighbour window of 40%
  of the data (span 0.4, as in the book) on the x of Figure 6.1; the smoothing spline is
  scipy.interpolate.make_smoothing_spline with its penalty chosen so that both smoothers have the
  same trace(S). Target points: the smallest x and the x nearest 0.6.
* Figure 6.8: tri-cube kernel, nearest-neighbour window of 15% of the 323 points (49 neighbours),
  east-west and north-south coordinates unscaled (both are in the same units).
* Figure 6.9: four overlapping intervals per conditioning variable, each covering 40% of its range
  and starting at 0%, 20%, 40%, 60% of the range; in each panel a local linear fit with a tri-cube
  kernel and a nearest-neighbour window containing all of the panel's points (span 1).
* Figure 6.12: local linear logistic regression, tri-cube kernel, nearest-neighbour window of 30%
  of the 462 subjects; the band is plus or minus one standard error on the logit scale.
* Figures 6.13-6.14: Gaussian kernel with Silverman's rule-of-thumb bandwidth
  0.9 min(sd, IQR/1.34) N^(-1/5) in each group; in Figure 6.13 each kernel is drawn as
  phi_lambda(x - x_i)/10.
* Figure 6.15: class densities f_1(x) = c_1 h(x) s(x), f_2(x) = c_2 h(x) (1 - s(x)), with h a
  three-bump mixture and s a logistic curve, so that the posterior is exactly logistic.
* Figure 6.16: four Gaussian basis functions phi((x - xi_j)/lambda)/lambda with lambda = 0.05 and
  centres 0.1, 0.55, 0.7, 0.9.
* Figure 6.17: EM for a two-component Gaussian mixture on Age (all 462 subjects), started from the
  two halves of the sorted data, run to convergence (relative change of the log-likelihood below
  1e-12).
"""
import json
import math
import os

import numpy as np

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

CH = 6
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")
YELLOW = "#f5df6b"
SINE_SEED = 6
SINE_N = 100
SINE_SD = 1.0 / 3.0


# =========================================================================== kernels (6.3)-(6.6)
def d_epanechnikov(t):
    """Epanechnikov kernel (6.4): 3/4 (1 - t^2) on |t| <= 1."""
    t = np.asarray(t, dtype=float)
    return np.where(np.abs(t) <= 1, 0.75 * (1 - t * t), 0.0)


def d_tricube(t):
    """Tri-cube kernel (6.6): (1 - |t|^3)^3 on |t| <= 1 (not normalised; its integral is 81/70)."""
    a = np.abs(np.asarray(t, dtype=float))
    return np.where(a <= 1, (1 - a ** 3) ** 3, 0.0)


def d_gauss(t):
    """Standard normal density, the noncompact kernel of Section 6.1."""
    t = np.asarray(t, dtype=float)
    return np.exp(-0.5 * t * t) / math.sqrt(2 * math.pi)


def d_box(t):
    """Uniform ('box') kernel 1/2 on |t| <= 1: the running mean."""
    t = np.asarray(t, dtype=float)
    return np.where(np.abs(t) <= 1, 0.5, 0.0)


KERNELS = {"epanechnikov": d_epanechnikov, "tricube": d_tricube, "gauss": d_gauss, "box": d_box}


# =========================================================================== data
def sine_data(seed=SINE_SEED, N=SINE_N, sd=SINE_SD):
    """The simulated data of Figures 6.1-6.7: X ~ U[0,1], Y = sin(4X) + N(0, sd^2), sorted by x."""
    r = np.random.default_rng(seed)
    x = r.uniform(0, 1, N)
    y = np.sin(4 * x) + sd * r.normal(size=N)
    o = np.argsort(x)
    return x[o], y[o]


def saheart():
    """South African heart disease data (Section 4.4.2): pandas DataFrame, famhist coded 0/1."""
    df = common.esl_data("SAheart.data")
    if "row.names" in df.columns:
        df = df.drop(columns=["row.names"])
    df["famhist"] = (df["famhist"] == "Present").astype(int)
    return df


# =========================================================================== windows and weights
def window_width(x0, x, lam=None, k=None):
    """h_lambda(x0) of (6.5): the constant lambda (metric window) or, if k is given, the distance from
    x0 to its k-th nearest x_i (nearest-neighbour window). x0 may be a vector of targets."""
    x0 = np.atleast_1d(np.asarray(x0, dtype=float))
    if k is None:
        return np.full(x0.shape, float(lam))
    d = np.abs(x[None, :] - x0[:, None])
    return np.partition(d, k - 1, axis=1)[:, k - 1]


def kernel_weights(x0, x, kernel="epanechnikov", lam=None, k=None, span=None):
    """K_lambda(x0, x_i) = D(|x_i - x0| / h(x0)) for every target in x0 (rows) and every x_i (columns).

    span (a fraction of N) is converted to k = floor(span N), as in loess. For the nearest-neighbour
    window the k-th nearest point gets weight D(1), which is 0 for the compact kernels; the window is
    widened by a factor 1 + 1e-10 so that it still contributes a tiny weight and ties are handled
    symmetrically."""
    x0 = np.atleast_1d(np.asarray(x0, dtype=float))
    if span is not None:
        k = int(math.floor(span * len(x)))
    h = window_width(x0, x, lam, k)
    if k is not None:
        h = h * (1 + 1e-10)
    return KERNELS[kernel]((x[None, :] - x0[:, None]) / h[:, None])


def knn_mean(x0, x, y, k):
    """The k-nearest-neighbour running mean (6.1)."""
    x0 = np.atleast_1d(np.asarray(x0, dtype=float))
    d = np.abs(x[None, :] - x0[:, None])
    idx = np.argsort(d, axis=1, kind="stable")[:, :k]
    return y[idx].mean(1)


def nadaraya_watson(x0, x, y, kernel="epanechnikov", lam=None, k=None, span=None):
    """Nadaraya-Watson kernel-weighted average (6.2)."""
    K = kernel_weights(x0, x, kernel, lam, k, span)
    return (K @ y) / K.sum(1)


# =========================================================================== local polynomials
def equivalent_kernel(x0, x, degree=1, kernel="tricube", lam=None, k=None, span=None, K=None):
    """The weights l_i(x0) of (6.9) for local polynomial regression of the given degree.

    With centred regressors b(x_i) = (1, x_i - x0, ..., (x_i - x0)^d) the fit at x0 is the intercept,
    so l(x0)^T = e_1^T (B^T W B)^{-1} B^T W, which is (6.8) (centring changes the basis, not the fit).
    Returns an array (len(x0), N). Degree 0 gives the Nadaraya-Watson weights K_i / sum K."""
    x0 = np.atleast_1d(np.asarray(x0, dtype=float))
    if K is None:
        K = kernel_weights(x0, x, kernel, lam, k, span)
    U = x[None, :] - x0[:, None]                                  # (m, N)
    P = np.stack([U ** j for j in range(degree + 1)], axis=2)     # (m, N, d+1)
    A = np.einsum("mn,mni,mnj->mij", K, P, P)                     # B^T W B for every target
    e1 = np.zeros(degree + 1)
    e1[0] = 1.0
    c = np.linalg.solve(A, np.broadcast_to(e1, (len(x0), degree + 1))[..., None])[..., 0]
    return K * np.einsum("mnj,mj->mn", P, c)


def local_poly_fit(x0, x, y, degree=1, **kw):
    """Local polynomial fit at the targets x0, returning (fhat, L) with L the equivalent kernels."""
    L = equivalent_kernel(x0, x, degree, **kw)
    return L @ y, L


def kernel_moments(L, x0, x, jmax=3):
    """b_j(x0) = sum_i (x_i - x0)^j l_i(x0) for j = 0..jmax (Exercise 6.2); rows follow x0."""
    x0 = np.atleast_1d(np.asarray(x0, dtype=float))
    U = x[None, :] - x0[:, None]
    return np.stack([(U ** j * L).sum(1) for j in range(jmax + 1)], axis=1)


def smoother_matrix(x, degree=1, **kw):
    """S_lambda with {S}_ij = l_j(x_i): row i is the equivalent kernel at the i-th observation."""
    return equivalent_kernel(x, x, degree, **kw)


def loocv_local_poly(x, y, degree=1, **kw):
    """Leave-one-out CV residual sum of squares for a local polynomial with a metric window
    (Exercise 6.7): the i-th deleted residual is (y_i - fhat_i) / (1 - S_ii)."""
    S = smoother_matrix(x, degree, **kw)
    r = (y - S @ y) / (1 - np.diag(S))
    return float(np.mean(r ** 2)), S


def loocv_brute(x, y, degree=1, **kw):
    """The same by refitting N times without the i-th point (for checking the shortcut)."""
    N = len(x)
    out = np.empty(N)
    for i in range(N):
        keep = np.arange(N) != i
        f, _ = local_poly_fit(x[i:i + 1], x[keep], y[keep], degree, **kw)
        out[i] = y[i] - f[0]
    return float(np.mean(out ** 2))


def gcv(y, S):
    """Generalised cross-validation: mean squared residual / (1 - trace(S)/N)^2."""
    N = len(y)
    return float(np.mean((y - S @ y) ** 2) / (1 - np.trace(S) / N) ** 2)


def cp_statistic(y, S, sigma2):
    """C_lambda = ASR + 2 sigma^2 trace(S) / N of (6.35)."""
    N = len(y)
    return float(np.mean((y - S @ y) ** 2) + 2 * sigma2 * np.trace(S) / N)


def spline_smoother(x, lam):
    """Smoother matrix of the cubic smoothing spline with penalty lam (columns = fits to unit vectors)."""
    from scipy.interpolate import make_smoothing_spline
    N = len(x)
    S = np.empty((N, N))
    E = np.eye(N)
    for j in range(N):
        S[:, j] = make_smoothing_spline(x, E[:, j], lam=lam)(x)
    return S


def spline_with_df(x, df):
    """Smoothing-spline smoother matrix whose trace equals df (bisection on log lambda)."""
    lo, hi = -14.0, 2.0
    for _ in range(60):
        mid = 0.5 * (lo + hi)
        if np.trace(spline_smoother(x, 10 ** mid)) > df:
            lo = mid
        else:
            hi = mid
    lam = 10 ** (0.5 * (lo + hi))
    return spline_smoother(x, lam), lam


# =========================================================================== local regression in R^p
def local_linear_2d(Q, X, y, span=0.15, degree=1):
    """Local linear (or constant) regression in R^2 at the query points Q (m, 2): radial tri-cube kernel
    (6.13) with a nearest-neighbour window containing floor(span N) points, fit (6.12)."""
    N = len(X)
    k = int(math.floor(span * N))
    D = np.sqrt(((Q[:, None, :] - X[None, :, :]) ** 2).sum(2))
    h = np.partition(D, k - 1, axis=1)[:, k - 1] * (1 + 1e-10)
    K = d_tricube(D / h[:, None])
    U = X[None, :, :] - Q[:, None, :]
    if degree == 0:
        P = np.ones(U.shape[:2] + (1,))
    else:
        P = np.concatenate([np.ones(U.shape[:2] + (1,)), U], axis=2)
    A = np.einsum("mn,mni,mnj->mij", K, P, P)
    rhs = np.einsum("mn,mni,n->mi", K, P, y)
    return np.linalg.solve(A, rhs[..., None])[:, 0, 0]


# =========================================================================== varying coefficients
def varying_coefficient(z0, z, X, y, kernel="tricube", lam=None, span=None, local_linear=True):
    """Fit (6.17) at each z0: f(x) = alpha(z) + sum_j beta_j(z) x_j by kernel-weighted least squares.

    With local_linear=True every coefficient is itself linear in z near z0 (the monomials
    1, x_j, (z - z0), x_j (z - z0); Exercise 6.6), which removes the first-order bias in z.
    Returns (coef (m, q+1), se (m, q+1), L) where L (m, q+1, N) maps y to the coefficients."""
    z0 = np.atleast_1d(np.asarray(z0, dtype=float))
    X = np.atleast_2d(X.T).T if X.ndim == 1 else X
    N, q = X.shape
    Xc = np.column_stack([np.ones(N), X])                         # (N, q+1)
    K = kernel_weights(z0, z, kernel, lam, span=span)
    coef, L = [], []
    for m in range(len(z0)):
        if local_linear:
            B = np.column_stack([Xc, Xc * (z - z0[m])[:, None]])
        else:
            B = Xc
        BW = B * K[m][:, None]
        Lm = np.linalg.solve(B.T @ BW, BW.T)[: q + 1]             # rows: coefficient as linear map of y
        L.append(Lm)
        coef.append(Lm @ y)
    L = np.array(L)
    coef = np.array(coef)
    # residual variance from the fitted values at the observations
    Kn = kernel_weights(z, z, kernel, lam, span=span)
    fit = np.empty(N)
    S = np.empty((N, N))
    for i in range(N):
        B = np.column_stack([Xc, Xc * (z - z[i])[:, None]]) if local_linear else Xc
        BW = B * Kn[i][:, None]
        Li = np.linalg.solve(B.T @ BW, BW.T)[: q + 1]
        S[i] = Xc[i] @ Li
    fit = S @ y
    dfres = N - 2 * np.trace(S) + np.trace(S.T @ S)
    sigma2 = float(np.sum((y - fit) ** 2) / dfres)
    se = np.sqrt(sigma2 * np.einsum("mjn,mjn->mj", L, L))
    return coef, se, dict(L=L, sigma2=sigma2, df=float(np.trace(S)), S=S)


# =========================================================================== local likelihood (6.19)
def expit(a):
    return common.sigmoid(a)


def local_logistic(x0, x, y, degree=1, kernel="tricube", span=None, lam=None, iters=50, tol=1e-12):
    """Local polynomial logistic regression (two-class (6.19)) at the targets x0.

    Maximises sum_i K_i [y_i eta_i - log(1 + exp(eta_i))] with eta_i = beta_0 + beta_1 (x_i - x0)
    (degree 1) or eta_i = beta_0 (degree 0) by Newton-Raphson, started at beta = (logit(ybar), 0).
    Returns dict(p, eta, se, slope, iters) where se is the sandwich standard error of eta-hat(x0) = beta_0:
    A^{-1} B A^{-1}, A = sum K_i p_i (1 - p_i) b_i b_i^T, B = sum K_i^2 p_i (1 - p_i) b_i b_i^T."""
    x0 = np.atleast_1d(np.asarray(x0, dtype=float))
    K = kernel_weights(x0, x, kernel, lam, span=span)
    eta, se, its, slope = np.empty(len(x0)), np.empty(len(x0)), np.empty(len(x0), dtype=int), np.full(len(x0), np.nan)
    for m in range(len(x0)):
        w = K[m]
        B = np.column_stack([(x - x0[m]) ** j for j in range(degree + 1)])
        ybar = np.sum(w * y) / np.sum(w)
        ybar = min(max(ybar, 1e-3), 1 - 1e-3)
        beta = np.zeros(degree + 1)
        beta[0] = math.log(ybar / (1 - ybar))
        for it in range(iters):
            p = expit(B @ beta)
            g = B.T @ (w * (y - p))
            A = B.T @ (B * (w * p * (1 - p))[:, None])
            step = np.linalg.solve(A, g)
            beta = beta + step
            if np.max(np.abs(step)) < tol:
                break
        p = expit(B @ beta)
        A = B.T @ (B * (w * p * (1 - p))[:, None])
        Bm = B.T @ (B * (w * w * p * (1 - p))[:, None])
        Ai = np.linalg.inv(A)
        V = Ai @ Bm @ Ai
        eta[m], se[m], its[m] = beta[0], math.sqrt(V[0, 0]), it + 1
        if degree >= 1:
            slope[m] = beta[1]
    return dict(eta=eta, p=expit(eta), se=se, iters=its, slope=slope)


def logistic_fit(X, y, iters=100):
    """Ordinary (global) logistic regression by Newton-Raphson; X without the intercept column."""
    X = np.column_stack([np.ones(len(y)), np.atleast_2d(X.T).T if np.ndim(X) == 1 else X])
    b = np.zeros(X.shape[1])
    for _ in range(iters):
        p = expit(X @ b)
        step = np.linalg.solve(X.T @ (X * (p * (1 - p))[:, None]), X.T @ (y - p))
        b += step
        if np.max(np.abs(step)) < 1e-12:
            break
    return b


# =========================================================================== kernel density estimation
def kde(x0, x, h, kernel="gauss"):
    """Parzen estimate (6.22): (1 / (N h)) sum_i D((x0 - x_i) / h); with the Gaussian D this is (6.23)."""
    x0 = np.atleast_1d(np.asarray(x0, dtype=float))
    D = KERNELS[kernel]
    return D((x0[:, None] - x[None, :]) / h).sum(1) / (len(x) * h)


def bw_silverman(x):
    """Silverman's rule of thumb 0.9 min(sd, IQR / 1.34) N^(-1/5) (R's bw.nrd0)."""
    x = np.asarray(x, dtype=float)
    q75, q25 = np.percentile(x, [75, 25])
    s = min(np.std(x, ddof=1), (q75 - q25) / 1.34)
    return 0.9 * s * len(x) ** (-0.2)


def bw_normal_reference(x):
    """The AMISE-optimal bandwidth when f is normal: (4/3)^(1/5) sd N^(-1/5) = 1.06 sd N^(-1/5)."""
    x = np.asarray(x, dtype=float)
    return (4.0 / 3.0) ** 0.2 * np.std(x, ddof=1) * len(x) ** (-0.2)


def lscv_gauss(x, h):
    """Least-squares cross-validation score for the Gaussian KDE:
    int fhat^2 - (2/N) sum_i fhat_{-i}(x_i), with int fhat^2 = (1/N^2) sum_ij phi_{sqrt2 h}(x_i - x_j)."""
    x = np.asarray(x, dtype=float)
    N = len(x)
    D = x[:, None] - x[None, :]
    h = np.atleast_1d(h)
    out = []
    for hh in h:
        a = np.exp(-D ** 2 / (4 * hh * hh)).sum() / (N * N * 2 * hh * math.sqrt(math.pi))
        Kd = np.exp(-D ** 2 / (2 * hh * hh)) / (hh * math.sqrt(2 * math.pi))
        loo = (Kd.sum(1) - Kd.diagonal()) / (N - 1)
        out.append(a - 2 * loo.mean())
    return np.array(out)


def lcv_gauss(x, h):
    """Likelihood cross-validation: (1/N) sum_i log fhat_{-i}(x_i) (to be maximised)."""
    x = np.asarray(x, dtype=float)
    N = len(x)
    D = x[:, None] - x[None, :]
    out = []
    for hh in np.atleast_1d(h):
        Kd = np.exp(-D ** 2 / (2 * hh * hh)) / (hh * math.sqrt(2 * math.pi))
        loo = (Kd.sum(1) - Kd.diagonal()) / (N - 1)
        out.append(np.mean(np.log(np.maximum(loo, 1e-300))))
    return np.array(out)


def ise_gauss_mixture(x, h, w, mu, sd):
    """Integrated squared error int (fhat - f)^2 of the Gaussian KDE when f is a Gaussian mixture
    sum_k w_k N(mu_k, sd_k^2), in closed form (all three terms are Gaussian convolutions)."""
    x = np.asarray(x, dtype=float)
    w, mu, sd = map(np.asarray, (w, mu, sd))
    N = len(x)

    def phi(d, s):
        return np.exp(-0.5 * (d / s) ** 2) / (s * math.sqrt(2 * math.pi))
    t1 = phi(x[:, None] - x[None, :], math.sqrt(2) * h).sum() / N ** 2
    t2 = (w[None, :] * phi(x[:, None] - mu[None, :], np.sqrt(h * h + sd[None, :] ** 2))).sum() / N
    t3 = (w[:, None] * w[None, :] * phi(mu[:, None] - mu[None, :], np.sqrt(sd[:, None] ** 2 + sd[None, :] ** 2))).sum()
    return float(t1 - 2 * t2 + t3)


def mise_gauss_mixture(N, h, w, mu, sd):
    """Exact mean integrated squared error E int (fhat - f)^2 of the Gaussian KDE from N points of the
    mixture sum_k w_k N(mu_k, sd_k^2): 1/(2 sqrt(pi) N h) + w^T [(1 - 1/N) O_2 - 2 O_1 + O_0] w, where
    O_a has entries phi_{sqrt(a h^2 + sd_k^2 + sd_l^2)}(mu_k - mu_l)."""
    w, mu, sd = map(np.asarray, (w, mu, sd))

    def Om(a):
        s = np.sqrt(a * h * h + sd[:, None] ** 2 + sd[None, :] ** 2)
        return np.exp(-0.5 * ((mu[:, None] - mu[None, :]) / s) ** 2) / (s * math.sqrt(2 * math.pi))
    return float(1 / (2 * math.sqrt(math.pi) * N * h) + w @ ((1 - 1 / N) * Om(2) - 2 * Om(1) + Om(0)) @ w)


def int_f2_gauss_mixture(w, mu, sd):
    """int f^2 for a Gaussian mixture (the constant that separates LSCV from the ISE)."""
    w, mu, sd = map(np.asarray, (w, mu, sd))
    s = np.sqrt(sd[:, None] ** 2 + sd[None, :] ** 2)
    return float(w @ (np.exp(-0.5 * ((mu[:, None] - mu[None, :]) / s) ** 2) / (s * math.sqrt(2 * math.pi))) @ w)


# The simulated density of the bandwidth demonstration and the rounding unit of each SAheart variable
KDE_SIM = dict(w=(0.7, 0.3), mu=(0.0, 2.5), sd=(1.0, 0.5), sizes=(50, 200, 500), seed=66)
SA_UNITS = dict(sbp=2.0, age=1.0, obesity=0.01, tobacco=0.01, ldl=0.01, adiposity=0.01, typea=1.0, alcohol=0.01)


def kde_sim_sample(N):
    """N points from the KDE_SIM mixture (numpy.random.default_rng(seed + N))."""
    P = KDE_SIM
    r = np.random.default_rng(P["seed"] + N)
    k = (r.uniform(size=N) < P["w"][1]).astype(int)
    return np.asarray(P["mu"])[k] + np.asarray(P["sd"])[k] * r.normal(size=N)


def kde_bandwidth_grid(x, n=241):
    """The bandwidth grid of the demonstration: n log-spaced values from sd/100 to 2 sd."""
    s = np.std(x, ddof=1)
    return np.exp(np.linspace(math.log(s / 100), math.log(2 * s), n))


def kde_cv_choice(x, unit=0.0):
    """Bandwidths chosen on kde_bandwidth_grid: LSCV and likelihood CV, unrestricted and restricted to
    h >= unit (the rounding unit of the data), plus the two rules of thumb."""
    hs = kde_bandwidth_grid(x)
    ls, lc = lscv_gauss(x, hs), lcv_gauss(x, hs)
    ok = hs >= unit
    return dict(h_lscv=float(hs[np.argmin(ls)]), h_lcv=float(hs[np.argmax(lc)]),
                h_lscv_r=float(hs[ok][np.argmin(ls[ok])]), h_lcv_r=float(hs[ok][np.argmax(lc[ok])]),
                h_silverman=float(bw_silverman(x)), h_normal=float(bw_normal_reference(x)), hs=hs, lscv=ls, lcv=lc)


def kde_classifier(x0, xs, priors, hs):
    """Posterior probabilities (6.25) from class-wise Gaussian KDEs: xs, hs, priors are per class."""
    F = np.stack([pi * kde(x0, xc, h) for xc, pi, h in zip(xs, priors, hs)], axis=1)
    return F / F.sum(1, keepdims=True)


def naive_bayes_fit(X, y, discrete=()):
    """Kernel naive Bayes (6.26): one-dimensional Gaussian KDEs (Silverman bandwidths) for continuous
    columns and relative frequencies (with add-one smoothing) for discrete ones, in each class."""
    classes = np.unique(y)
    model = dict(classes=classes, prior=[], cols=[])
    for c in classes:
        Xc = X[y == c]
        model["prior"].append(len(Xc) / len(X))
        cols = []
        for j in range(X.shape[1]):
            if j in discrete:
                vals = np.unique(X[:, j])
                cnt = np.array([(Xc[:, j] == v).sum() for v in vals]) + 1.0
                cols.append(("d", vals, cnt / cnt.sum()))
            else:
                cols.append(("c", Xc[:, j].copy(), bw_silverman(Xc[:, j])))
        model["cols"].append(cols)
    return model


def naive_bayes_logpost(model, X):
    """log pi_j + sum_k log f_jk(x_k), the additive form (6.27), for every row of X and class j."""
    out = []
    for pi, cols in zip(model["prior"], model["cols"]):
        s = np.full(len(X), math.log(pi))
        for j, col in enumerate(cols):
            if col[0] == "d":
                vals, pr = col[1], col[2]
                s += np.log(np.array([pr[np.searchsorted(vals, v)] for v in X[:, j]]))
            else:
                s += np.log(np.maximum(kde(X[:, j], col[1], col[2]), 1e-300))
        out.append(s)
    return np.stack(out, axis=1)


def cv_folds(N, K=10, seed=0):
    r = np.random.default_rng(seed)
    return r.permutation(N) % K


def naive_bayes_vs_logistic(K=10, seed=0):
    """10-fold cross-validated error of kernel naive Bayes and linear logistic regression on SAheart
    (all nine predictors; famhist discrete)."""
    df = saheart()
    cols = ["sbp", "tobacco", "ldl", "adiposity", "famhist", "typea", "obesity", "alcohol", "age"]
    X = df[cols].to_numpy(float)
    y = df["chd"].to_numpy(int)
    fold = cv_folds(len(y), K, seed)
    err_nb, err_lr = 0, 0
    for f in range(K):
        tr, te = fold != f, fold == f
        m = naive_bayes_fit(X[tr], y[tr], discrete=(4,))
        err_nb += np.sum(np.argmax(naive_bayes_logpost(m, X[te]), 1) != y[te])
        mu, sd = X[tr].mean(0), X[tr].std(0)
        b = logistic_fit((X[tr] - mu) / sd, y[tr])
        p = expit(b[0] + ((X[te] - mu) / sd) @ b[1:])
        err_lr += np.sum((p > 0.5) != y[te])
    return err_nb / len(y), err_lr / len(y)


# =========================================================================== radial basis functions
def rbf_basis(x, centres, lam, normalise=False):
    """Gaussian radial basis functions D(|x - xi_j| / lambda) / lambda (6.28), or their renormalised
    version (6.30), as columns."""
    H = d_gauss((np.asarray(x)[:, None] - np.asarray(centres)[None, :]) / lam) / lam
    if normalise:
        H = H / H.sum(1, keepdims=True)
    return H


# =========================================================================== Gaussian mixtures
def em_gauss_1d(x, M=2, init=None, tol=1e-12, maxit=5000, fixed_sd=None):
    """EM for the one-dimensional Gaussian mixture (6.32). init = (alpha, mu, var); with fixed_sd the
    variances are held at fixed_sd^2 (the setting of the remark that follows (6.32)).
    Returns dict(alpha, mu, var, loglik, resp (6.33), iters)."""
    x = np.asarray(x, dtype=float)
    N = len(x)
    if init is None:
        xs = np.sort(x)
        parts = np.array_split(xs, M)
        alpha = np.array([len(p) / N for p in parts])
        mu = np.array([p.mean() for p in parts])
        var = np.array([p.var() + 1e-6 for p in parts])
    else:
        alpha, mu, var = (np.array(a, dtype=float) for a in init)
    if fixed_sd is not None:
        var = np.full(M, fixed_sd ** 2)
    old = -np.inf
    for it in range(maxit):
        logd = -0.5 * np.log(2 * np.pi * var)[None, :] - 0.5 * (x[:, None] - mu[None, :]) ** 2 / var[None, :]
        la = np.log(np.maximum(alpha, 1e-300))[None, :] + logd
        ll = common.logsumexp(la, axis=1)
        loglik = float(ll.sum())
        r = np.exp(la - ll[:, None])
        Nk = r.sum(0)
        alpha = Nk / N
        mu = (r * x[:, None]).sum(0) / Nk
        if fixed_sd is None:
            var = (r * (x[:, None] - mu[None, :]) ** 2).sum(0) / Nk
        if abs(loglik - old) <= tol * abs(loglik):
            break
        old = loglik
    logd = -0.5 * np.log(2 * np.pi * var)[None, :] - 0.5 * (x[:, None] - mu[None, :]) ** 2 / var[None, :]
    la = np.log(alpha)[None, :] + logd
    ll = common.logsumexp(la, axis=1)
    return dict(alpha=alpha, mu=mu, var=var, loglik=float(ll.sum()), resp=np.exp(la - ll[:, None]), iters=it + 1)


def mixture_mle_fixed_sd(x, sd, tol=1e-14, maxit=20000, merge=0.5):
    """Maximum likelihood for the N-component mixture (6.32) with every standard deviation fixed at sd,
    started at the kernel density estimate (alpha_m = 1/N, mu_m = x_m). Returns the log-likelihoods of
    the KDE and of the EM limit, and the support points of the limit (means closer than `merge` pooled)."""
    x = np.asarray(x, dtype=float)
    N = len(x)
    kde_ll = mixture_loglik(x, np.full(N, 1.0 / N), x.copy(), np.full(N, float(sd)))
    r = em_gauss_1d(x, N, init=(np.full(N, 1.0 / N), x.copy(), np.full(N, sd * sd)), fixed_sd=sd, tol=tol, maxit=maxit)
    support = []
    for m_, a_ in sorted(zip(r["mu"], r["alpha"])):
        if support and abs(m_ - support[-1][0]) < merge:
            w = support[-1][1] + a_
            support[-1] = [(support[-1][0] * support[-1][1] + m_ * a_) / w, w]
        else:
            support.append([m_, a_])
    support = [(float(m_), float(a_)) for m_, a_ in support if a_ > 1e-3]
    return dict(kde_loglik=kde_ll, mle_loglik=r["loglik"], support=support, iters=r["iters"])


def tied_pairs(x):
    """Number T of pairs i < j with x_i = x_j."""
    _, c = np.unique(np.asarray(x), return_counts=True)
    return int((c * (c - 1) // 2).sum())


def lscv_small_h_coefficient(x):
    """Coefficient c in LSCV(h) = c / h + o(1/h) as h -> 0 for the Gaussian kernel:
    c = (N + 2T) / (2 sqrt(pi) N^2) - 4T / (sqrt(2 pi) N (N - 1)), T = number of tied pairs.
    When c < 0 the LSCV criterion tends to minus infinity as h -> 0."""
    N, T = len(x), tied_pairs(x)
    return (N + 2 * T) / (2 * math.sqrt(math.pi) * N * N) - 4 * T / (math.sqrt(2 * math.pi) * N * (N - 1))


def mixture_loglik(x, alpha, mu, sd):
    x = np.asarray(x, dtype=float)
    la = np.log(alpha)[None, :] - 0.5 * np.log(2 * np.pi * sd ** 2)[None, :] - 0.5 * (x[:, None] - mu[None, :]) ** 2 / sd[None, :] ** 2
    return float(common.logsumexp(la, axis=1).sum())


# =========================================================================== local LDA (Exercise 6.12)
ZIP_PCS = 40
LDA_LAMBDAS = (4.0, 6.0, 8.0, 12.0, np.inf)


def zip_data():
    """Zip-code digits (Section 11.7): training and test arrays (pixels in [-1, 1]) and labels."""
    import gzip
    out = []
    for name in ("zip.train.gz", "zip.test.gz"):
        with gzip.open(common.esl_file(name), "rt") as f:
            A = np.loadtxt(f)
        out += [A[:, 1:], A[:, 0].astype(int)]
    return out


def local_lda(Q, Zq, Xtr, Ztr, ytr, lam, ridge=1e-3, batch=256):
    """Local linear discriminant analysis (Exercise 6.12).

    For each query (rows of Q in the original pixel space, Zq the same queries in the reduced space)
    the training points get Gaussian weights w_i = exp(-||x_i - x_0||^2 / (2 lam^2)); the class priors,
    class means and the pooled within-class covariance of Section 4.3 are computed as w-weighted
    averages in the reduced space, and x_0 is assigned to the class with the largest linear
    discriminant (4.10). lam = inf is ordinary LDA. ridge * (trace / p) is added to the covariance."""
    n, p = Ztr.shape
    G = int(ytr.max()) + 1
    Y = np.eye(G)[ytr]                                            # (n, G)
    XX = (Ztr[:, :, None] * Ztr[:, None, :]).reshape(n, p * p)    # outer products, one row each
    sq = (Xtr ** 2).sum(1)
    pred = np.empty(len(Q), dtype=int)
    for s in range(0, len(Q), batch):
        q = Q[s:s + batch]
        if np.isinf(lam):
            W = np.ones((len(q), n))
        else:
            d2 = (q ** 2).sum(1)[:, None] + sq[None, :] - 2 * q @ Xtr.T
            d2 = np.maximum(d2, 0)
            W = np.exp(-(d2 - d2.min(1, keepdims=True)) / (2 * lam * lam))   # rescaling does not change LDA
        Wk = W @ Y                                                # (b, G) class weights
        S1 = np.einsum("bn,ng,np->bgp", W, Y, Ztr)                # weighted class sums
        tot = W.sum(1)
        S2 = (W @ XX).reshape(len(q), p, p)
        for b in range(len(q)):
            ok = Wk[b] > 1e-12 * tot[b]
            mu = np.zeros((G, p))
            mu[ok] = S1[b, ok] / Wk[b, ok, None]
            Sw = (S2[b] - np.einsum("g,gi,gj->ij", Wk[b, ok], mu[ok], mu[ok])) / tot[b]
            Sw += ridge * np.trace(Sw) / p * np.eye(p)
            Si = np.linalg.solve(Sw, mu.T)                        # (p, G)
            z = Zq[s + b]
            disc = z @ Si - 0.5 * np.einsum("gp,pg->g", mu, Si) + np.log(np.maximum(Wk[b] / tot[b], 1e-300))
            disc[~ok] = -np.inf
            pred[s + b] = int(np.argmax(disc))
    return pred


LDA_TRAIN_EVAL = 1000


def local_lda_errors(lams=LDA_LAMBDAS, n_train_eval=LDA_TRAIN_EVAL):
    """Training and test error of local LDA on the zip-code data for each lambda (cached).

    The test error uses all 2007 test digits; the training error is measured on a fixed random
    subset of n_train_eval training digits (numpy.random.default_rng(12)) to keep the run short.
    All 7291 training digits are used to fit at every query point."""
    os.makedirs(CACHE_DIR, exist_ok=True)
    path = os.path.join(CACHE_DIR, "ch06_local_lda.json")
    if os.path.exists(path):
        with open(path) as f:
            res = json.load(f)
        if res.get("lams") == [str(l) for l in lams] and res.get("pcs") == ZIP_PCS and res.get("n_train_eval") == n_train_eval:
            return res
    Xtr, ytr, Xte, yte = zip_data()
    mu = Xtr.mean(0)
    _, _, Vt = np.linalg.svd(Xtr - mu, full_matrices=False)
    V = Vt[:ZIP_PCS].T
    Ztr, Zte = (Xtr - mu) @ V, (Xte - mu) @ V
    sub = np.sort(np.random.default_rng(12).choice(len(ytr), n_train_eval, replace=False))
    out = dict(lams=[str(l) for l in lams], pcs=ZIP_PCS, n_train_eval=n_train_eval, train=[], test=[])
    for lam in lams:
        ptr = local_lda(Xtr[sub], Ztr[sub], Xtr, Ztr, ytr, lam)
        pte = local_lda(Xte, Zte, Xtr, Ztr, ytr, lam)
        out["train"].append(float(np.mean(ptr != ytr[sub])))
        out["test"].append(float(np.mean(pte != yte)))
        print("  local LDA lambda = %s: training error %.4f, test error %.4f" % (lam, out["train"][-1], out["test"][-1]))
    with open(path, "w") as f:
        json.dump(out, f)
    return out


# =========================================================================== demo data
def export_demo_data():
    """Write the small JSON files the browser demonstrations read."""
    os.makedirs(DATA_OUT, exist_ok=True)
    x, y = sine_data()
    with open(os.path.join(DATA_OUT, "ch06-sine.json"), "w") as f:
        json.dump(dict(note="Simulated data of Figures 6.1-6.6: X ~ U[0,1], Y = sin(4X) + N(0, 1/9).",
                       x=[round(float(v), 10) for v in x], y=[round(float(v), 10) for v in y]), f)
    P = KDE_SIM
    with open(os.path.join(DATA_OUT, "ch06-kde-sim.json"), "w") as f:
        json.dump(dict(note="Samples from the mixture 0.7 N(0, 1) + 0.3 N(2.5, 0.5^2).", w=P["w"], mu=P["mu"], sd=P["sd"],
                       samples={str(N): [round(float(v), 8) for v in kde_sim_sample(N)] for N in P["sizes"]}), f, separators=(",", ":"))
    df = saheart()
    cols = ["sbp", "tobacco", "ldl", "adiposity", "famhist", "typea", "obesity", "alcohol", "age", "chd"]
    with open(os.path.join(DATA_OUT, "ch06-saheart.json"), "w") as f:
        json.dump(dict(note="South African heart disease data (book website), 462 subjects.",
                       cols=cols, data={c: [float(v) if c not in ("famhist", "chd", "typea", "age") else int(v)
                                            for v in df[c]] for c in cols}), f, separators=(",", ":"))


# =========================================================================== figures
def _sine_panel(ax, x, y, title):
    g = np.linspace(0, 1, 401)
    ax.scatter(x, y, s=14, facecolors="none", edgecolors="#8fa3bf", linewidths=0.7, zorder=2)
    ax.plot(g, np.sin(4 * g), color=BLUE, lw=1.4, zorder=3)
    ax.set_xlim(-0.02, 1.02)
    ax.set_ylim(-1.15, 1.65)
    ax.set_title(title)
    return g


def _weights_band(ax, x0, w, scale, base=-1.15):
    """Yellow region showing the (rescaled) weights of a kernel at x0."""
    order = np.argsort(x0)
    ax.fill_between(x0[order], base, base + scale * w[order], color=YELLOW, alpha=0.75, lw=0, zorder=1)


def fig_6_1(out_dir=None):
    """30-nearest-neighbour running mean and Epanechnikov Nadaraya-Watson average (Figure 6.1)."""
    import matplotlib.pyplot as plt
    export_demo_data()
    x, y = sine_data()
    x0 = 0.5
    fig, axes = plt.subplots(1, 2, figsize=(8.6, 3.5))
    for ax, which in zip(axes, ("knn", "epa")):
        g = _sine_panel(ax, x, y, "Nearest-Neighbor Kernel" if which == "knn" else "Epanechnikov Kernel")
        if which == "knn":
            f = knn_mean(g, x, y, 30)
            d = np.abs(x - x0)
            idx = np.argsort(d, kind="stable")[:30]
            lo, hi = x[idx].min(), x[idx].max()
            ax.fill_between([lo, hi], -1.15, [1.3, 1.3], color=YELLOW, alpha=0.75, lw=0, zorder=1)
            used = np.zeros(len(x), bool)
            used[idx] = True
            fx0 = y[idx].mean()
        else:
            f = nadaraya_watson(g, x, y, "epanechnikov", lam=0.2)
            K = kernel_weights(np.array([x0]), x, "epanechnikov", lam=0.2)[0]
            gg = np.linspace(x0 - 0.2, x0 + 0.2, 201)
            ax.fill_between(gg, -1.15, -1.15 + 3.2 * d_epanechnikov((gg - x0) / 0.2), color=YELLOW, alpha=0.75, lw=0, zorder=1)
            used = K > 0
            fx0 = float(nadaraya_watson(np.array([x0]), x, y, "epanechnikov", lam=0.2)[0])
        ax.scatter(x[used], y[used], s=14, facecolors="none", edgecolors=RED, linewidths=0.8, zorder=4)
        ax.plot(g, f, color=GREEN, lw=1.5, zorder=5)
        ax.plot([x0, x0], [-1.15, fx0], color=RED, lw=0.8, zorder=5)
        ax.plot([x0], [fx0], "o", color=RED, ms=5, zorder=6)
        ax.text(x0 + 0.02, fx0 + 0.12, r"$\hat f(x_0)$", fontsize=10)
        ax.set_xticks([0, 0.2, 0.4, 0.6, 0.8, 1.0])
        ax.set_xlabel(r"$x$ (target $x_0=0.5$)")
    fig.tight_layout()
    savefig(fig, CH, "fig6-1", out_dir)


def fig_6_2(out_dir=None):
    """The Epanechnikov, tri-cube and Gaussian kernels, each normalised to integrate to one (Figure 6.2)."""
    import matplotlib.pyplot as plt
    t = np.linspace(-3, 3, 1201)
    fig, ax = plt.subplots(figsize=(6.0, 2.8))
    ax.plot(t, d_epanechnikov(t), color=ORANGE, label="Epanechnikov")
    ax.plot(t, 70.0 / 81.0 * d_tricube(t), color=GREEN, label="Tri-cube")
    ax.plot(t, d_gauss(t), color=CYAN, label="Gaussian")
    ax.set_ylabel(r"$K_\lambda(x_0,x)$")
    ax.set_xlabel(r"$(x-x_0)/\lambda$")
    ax.set_yticks([0, 0.4, 0.8])
    ax.legend(frameon=True, fontsize=8.5)
    fig.tight_layout()
    savefig(fig, CH, "fig6-2", out_dir)


def _boundary_panel(ax, x, y, x0, degree, kernel, lam, title, show_equiv=False):
    g = _sine_panel(ax, x, y, title)
    K = kernel_weights(np.array([x0]), x, kernel, lam=lam)[0]
    gg = np.linspace(max(0, x0 - lam), min(1, x0 + lam), 201)
    ax.fill_between(gg, -1.15, -1.15 + 2.6 * KERNELS[kernel]((gg - x0) / lam) / KERNELS[kernel](0.0),
                    color=YELLOW, alpha=0.75, lw=0, zorder=1)
    used = K > 0
    ax.scatter(x[used], y[used], s=14, facecolors="none", edgecolors=RED, linewidths=0.8, zorder=4)
    lo, hi = (0.0, 1.0)
    gfit = g[(g >= lo) & (g <= hi)]
    f, _ = local_poly_fit(gfit, x, y, degree, kernel=kernel, lam=lam)
    ax.plot(gfit, f, color=GREEN, lw=1.5, zorder=5)
    fx0, L = local_poly_fit(np.array([x0]), x, y, degree, kernel=kernel, lam=lam)
    fx0 = float(fx0[0])
    if degree >= 1 and not show_equiv:
        # the local line (or quadratic) fitted at x0, drawn over the window
        Kx = K
        B = np.column_stack([(x - x0) ** j for j in range(degree + 1)])
        beta = np.linalg.solve(B.T @ (B * Kx[:, None]), B.T @ (Kx * y))
        gl = np.linspace(max(0, x0 - lam), min(1, x0 + lam), 50)
        ax.plot(gl, sum(beta[j] * (gl - x0) ** j for j in range(degree + 1)), color=RED, lw=1.0, zorder=5)
    if show_equiv:
        l = L[0]
        ax.plot(x, -0.6 + 2.0 * l / np.abs(l).max(), "o", color=GREEN, ms=2.6, zorder=6)
        ax.axhline(-0.6, color=GREEN, lw=0.5, ls=":")
    ax.plot([x0, x0], [-1.15, fx0], color=RED, lw=0.8, zorder=5)
    ax.plot([x0], [fx0], "o", color=RED, ms=5, zorder=7)
    ax.text(x0 + 0.02, fx0 + 0.15, r"$\hat f(x_0)$", fontsize=10)
    ax.set_xticks([0, 0.2, 0.4, 0.6, 0.8, 1.0])
    return fx0


def fig_6_3(out_dir=None):
    """Nadaraya-Watson against local linear regression at the boundary (Figure 6.3)."""
    import matplotlib.pyplot as plt
    x, y = sine_data()
    fig, axes = plt.subplots(1, 2, figsize=(8.6, 3.5))
    a = _boundary_panel(axes[0], x, y, 0.05, 0, "epanechnikov", 0.2, "N-W Kernel at Boundary")
    b = _boundary_panel(axes[1], x, y, 0.05, 1, "epanechnikov", 0.2, "Local Linear Regression at Boundary")
    for ax in axes:
        ax.set_xlabel(r"$x$ (target $x_0=0.05$)")
    fig.tight_layout()
    savefig(fig, CH, "fig6-3", out_dir)
    print("  f(0.05) = %.4f; Nadaraya-Watson %.4f, local linear %.4f" % (math.sin(0.2), a, b))


def fig_6_4(out_dir=None):
    """Equivalent kernels of local linear regression at the boundary and in the interior (Figure 6.4)."""
    import matplotlib.pyplot as plt
    x, y = sine_data()
    fig, axes = plt.subplots(1, 2, figsize=(8.6, 3.5))
    _boundary_panel(axes[0], x, y, 0.05, 1, "tricube", 0.2, "Local Linear Equivalent Kernel at Boundary", True)
    _boundary_panel(axes[1], x, y, 0.4, 1, "tricube", 0.2, "Local Linear Equivalent Kernel in Interior", True)
    axes[0].set_xlabel(r"$x$ (target $x_0=0.05$)")
    axes[1].set_xlabel(r"$x$ (target $x_0=0.4$)")
    fig.tight_layout()
    savefig(fig, CH, "fig6-4", out_dir)


def fig_6_5(out_dir=None):
    """Local linear against local quadratic regression in a region of curvature (Figure 6.5)."""
    import matplotlib.pyplot as plt
    x, y = sine_data()
    fig, axes = plt.subplots(1, 2, figsize=(8.6, 3.5))
    a = _boundary_panel(axes[0], x, y, 0.4, 1, "tricube", 0.25, "Local Linear in Interior")
    b = _boundary_panel(axes[1], x, y, 0.4, 2, "tricube", 0.25, "Local Quadratic in Interior")
    for ax in axes:
        ax.set_xlabel(r"$x$ (target $x_0=0.4$)")
    fig.tight_layout()
    savefig(fig, CH, "fig6-5", out_dir)
    print("  f(0.4) = %.4f; local linear %.4f, local quadratic %.4f" % (math.sin(1.6), a, b))


def variance_curves(x, g, lam=0.2, kernel="tricube", degrees=(0, 1, 2)):
    """||l(x0)||^2 on the grid g for each degree (the variance of fhat(x0) when sigma^2 = 1)."""
    return {d: (equivalent_kernel(g, x, d, kernel=kernel, lam=lam) ** 2).sum(1) for d in degrees}


def fig_6_6(out_dir=None):
    """Variance functions ||l(x)||^2 of local constant, linear and quadratic fits (Figure 6.6)."""
    import matplotlib.pyplot as plt
    x, _ = sine_data()
    g = np.linspace(0, 1, 501)
    V = variance_curves(x, g)
    fig, ax = plt.subplots(figsize=(5.6, 3.3))
    for d, c, lab in zip((0, 1, 2), (ORANGE, CYAN, GREEN), ("Constant", "Linear", "Quadratic")):
        ax.plot(g, V[d], color=c, label=lab)
    ax.plot(x, np.full_like(x, -0.012), "|", color="black", ms=7)
    ax.set_ylim(-0.025, 0.6)
    ax.set_ylabel("Variance")
    ax.set_xlabel(r"$x$")
    ax.legend(frameon=True, loc="upper center")
    fig.tight_layout()
    savefig(fig, CH, "fig6-6", out_dir)
    for d in (0, 1, 2):
        print("  degree %d: ||l||^2 at x=0: %.4f, at x=0.5: %.4f, at x=1: %.4f" % (d, V[d][0], V[d][250], V[d][-1]))


def fig_6_7(out_dir=None):
    """Equivalent kernels of a local linear smoother (span 40%) and a smoothing spline of equal df (Figure 6.7)."""
    import matplotlib.pyplot as plt
    x, _ = sine_data()
    S = smoother_matrix(x, 1, kernel="tricube", span=0.4)
    df = float(np.trace(S))
    Ssp, lam = spline_with_df(x, df)
    fig, axes = plt.subplots(1, 2, figsize=(8.0, 2.8))
    for ax, i in zip(axes, (0, int(np.argmin(np.abs(x - 0.6))))):
        ax.plot(x, S[i], "o--", color=ORANGE, ms=2.6, lw=0.9, label="local linear (tri-cube)")
        ax.plot(x, Ssp[i], "o:", color=CYAN, ms=2.6, lw=1.0, label="smoothing spline")
        ax.axhline(0, color="black", ls="--", lw=0.6)
        ax.axvline(x[i], color="black", lw=1.0, ymax=0.08)
        ax.set_xlabel(r"$x$ (target $x_0=%.3f$)" % x[i])
        ax.set_yticks([])
    axes[0].legend(fontsize=8, frameon=False)
    fig.suptitle("Equivalent kernels, df = trace(S) = %.2f" % df, fontsize=10)
    fig.tight_layout()
    savefig(fig, CH, "fig6-7", out_dir)
    print("  span 0.4 local linear: df = %.3f; smoothing spline lambda = %.3g has df = %.3f" % (df, lam, np.trace(Ssp)))
    return df


def galaxy():
    df = common.esl_data("galaxy.data")
    return df["east.west"].to_numpy(float), df["north.south"].to_numpy(float), df["velocity"].to_numpy(float)


def fig_6_8(out_dir=None):
    """The galaxy data and their local linear regression surface in R^2 (Figure 6.8)."""
    import matplotlib.pyplot as plt
    ew, ns, v = galaxy()
    X = np.column_stack([ew, ns])
    ge = np.linspace(ew.min(), ew.max(), 31)
    gn = np.linspace(ns.min(), ns.max(), 31)
    E, Nn = np.meshgrid(ge, gn)
    F = local_linear_2d(np.column_stack([E.ravel(), Nn.ravel()]), X, v, span=0.15).reshape(E.shape)
    fig = plt.figure(figsize=(9.0, 4.2))
    ax1 = fig.add_subplot(1, 2, 1, projection="3d")
    ax1.scatter(ew, ns, v, s=4, color=GREEN, depthshade=False)
    ax2 = fig.add_subplot(1, 2, 2, projection="3d")
    ax2.plot_surface(E, Nn, F, cmap="cool", rstride=1, cstride=1, linewidth=0.2, edgecolor="#333333", alpha=0.95)
    for ax in (ax1, ax2):
        ax.set_xlabel("East-West", fontsize=8, labelpad=-2)
        ax.set_ylabel("South-North", fontsize=8, labelpad=-2)
        ax.set_zlabel("Velocity", fontsize=8, labelpad=0)
        ax.tick_params(labelsize=6, pad=0)
        ax.view_init(elev=24, azim=-60)
        ax.set_zlim(v.min(), v.max())
    fig.tight_layout()
    savefig(fig, CH, "fig6-8", out_dir)
    print("  fitted surface range %.0f to %.0f km/s (data %.0f to %.0f)" % (F.min(), F.max(), v.min(), v.max()))


def ny_ozone():
    df = common.esl_data("ozone.data")
    return (df["ozone"].to_numpy(float) ** (1 / 3), df["radiation"].to_numpy(float),
            df["temperature"].to_numpy(float), df["wind"].to_numpy(float))


def shingle(v, n=4, width=0.4):
    """n overlapping intervals, each width x range long, starting at 0, (1-width)/(n-1), ... of the range."""
    lo, hi = v.min(), v.max()
    R = hi - lo
    return [(lo + R * s, lo + R * (s + width)) for s in np.linspace(0, 1 - width, n)]


def fig_6_9(out_dir=None):
    """Trellis display: cube-root ozone against radiation, conditioned on temperature and wind (Figure 6.9)."""
    import matplotlib.pyplot as plt
    oz, rad, temp, wind = ny_ozone()
    ti, wi = shingle(temp), shingle(wind)
    fig, axes = plt.subplots(4, 4, figsize=(8.4, 8.4), sharex=True, sharey=True)
    counts = []
    for r in range(4):            # row 0 at the top = highest wind interval
        w_lo, w_hi = wi[3 - r]
        for c in range(4):
            t_lo, t_hi = ti[c]
            ax = axes[r, c]
            sel = (temp >= t_lo) & (temp <= t_hi) & (wind >= w_lo) & (wind <= w_hi)
            counts.append(int(sel.sum()))
            ax.scatter(rad[sel], oz[sel], s=12, facecolors="none", edgecolors=CYAN, linewidths=0.8)
            if sel.sum() >= 5:
                g = np.linspace(rad[sel].min(), rad[sel].max(), 60)
                f, _ = local_poly_fit(g, rad[sel], oz[sel], 1, kernel="tricube", span=1.0)
                ax.plot(g, f, color="black", lw=1.0)
            # strips showing the conditioning intervals
            for k, (lo, hi, v, col, lab) in enumerate(((w_lo, w_hi, wind, GREEN, "Wind"), (t_lo, t_hi, temp, ORANGE, "Temp"))):
                y0 = 1.0 + 0.09 * (1 - k)
                ax.add_patch(plt.Rectangle((0, y0), 1, 0.09, transform=ax.transAxes, clip_on=False, fc="#fbe9d0" if k else "#dff5d8", ec="black", lw=0.5))
                a = (lo - v.min()) / (v.max() - v.min())
                b = (hi - v.min()) / (v.max() - v.min())
                ax.add_patch(plt.Rectangle((a, y0), b - a, 0.09, transform=ax.transAxes, clip_on=False, fc=col, ec="none", alpha=0.85))
                ax.text(0.5, y0 + 0.045, lab, transform=ax.transAxes, ha="center", va="center", fontsize=7)
            ax.set_ylim(0.8, 5.8)
            ax.tick_params(labelsize=7)
    fig.supxlabel("Solar Radiation (langleys)", fontsize=10)
    fig.supylabel("Cube Root Ozone (cube root ppb)", fontsize=10)
    fig.tight_layout(h_pad=1.6)
    savefig(fig, CH, "fig6-9", out_dir)
    print("  points per panel: min %d, max %d" % (min(counts), max(counts)))


def la_ozone():
    df = common.esl_data("LAozone.data")
    return df


def fig_6_s1(out_dir=None):
    """Supplementary: a varying-coefficient model (6.17) on the Los Angeles ozone data
    (cube-root ozone linear in temperature, with intercept and slope varying with day of year)."""
    import matplotlib.pyplot as plt
    df = la_ozone()
    y = df["ozone"].to_numpy(float) ** (1 / 3)
    temp = df["temp"].to_numpy(float)
    doy = df["doy"].to_numpy(float)
    tc = temp - temp.mean()
    g = np.linspace(doy.min(), doy.max(), 120)
    coef, se, info = varying_coefficient(g, doy, tc[:, None], y, kernel="tricube", span=0.3, local_linear=True)
    b_global = np.linalg.lstsq(np.column_stack([np.ones(len(y)), tc]), y, rcond=None)[0]
    fig, axes = plt.subplots(1, 2, figsize=(8.4, 3.2))
    labs = (r"intercept $\alpha(z)$ (cube-root ozone at mean temperature)", r"temperature slope $\beta(z)$ (per $^\circ$F)")
    for j, ax in enumerate(axes):
        ax.fill_between(g, coef[:, j] - se[:, j], coef[:, j] + se[:, j], color=YELLOW, alpha=0.8, lw=0)
        ax.plot(g, coef[:, j], color=GREEN)
        ax.axhline(b_global[j], color=GREY, ls="--", lw=0.8)
        ax.set_xlabel("day of year $z$")
        ax.set_title(labs[j], fontsize=9)
    fig.tight_layout()
    savefig(fig, CH, "fig6-S1", out_dir)
    print("  slope ranges from %.3f to %.3f (global %.3f); df = %.2f, sigma = %.3f"
          % (coef[:, 1].min(), coef[:, 1].max(), b_global[1], info["df"], math.sqrt(info["sigma2"])))
    return coef, se, info


SA_SPAN = 0.3


def fig_6_12(out_dir=None):
    """Local linear logistic regression of CHD on systolic blood pressure and on obesity (Figure 6.12)."""
    import matplotlib.pyplot as plt
    export_demo_data()
    df = saheart()
    y = df["chd"].to_numpy(float)
    fig, axes = plt.subplots(1, 2, figsize=(7.6, 3.4))
    out = {}
    for ax, var, lab in zip(axes, ("sbp", "obesity"), ("Systolic Blood Pressure", "Obesity")):
        x = df[var].to_numpy(float)
        g = np.linspace(x.min(), x.max(), 120)
        r = local_logistic(g, x, y, degree=1, kernel="tricube", span=SA_SPAN)
        lo, hi = expit(r["eta"] - r["se"]), expit(r["eta"] + r["se"])
        ax.fill_between(g, lo, hi, color=YELLOW, alpha=0.85, lw=0)
        ax.plot(g, r["p"], color=GREEN, lw=1.6)
        ax.plot(x[y == 1], np.full((y == 1).sum(), 0.99), "|", color=RED, ms=7, mew=0.6)
        ax.plot(x[y == 0], np.full((y == 0).sum(), 0.01), "|", color=RED, ms=7, mew=0.6)
        ax.set_ylim(0, 1)
        ax.set_xlabel(lab)
        ax.set_ylabel("Prevalence CHD")
        out[var] = (g, r)
        print("  %s: fitted prevalence from %.3f to %.3f; Newton iterations at most %d"
              % (var, r["p"].min(), r["p"].max(), r["iters"].max()))
    fig.tight_layout()
    savefig(fig, CH, "fig6-12", out_dir)
    return out


def fig_6_13(out_dir=None):
    """Gaussian kernel density estimate of systolic blood pressure in the CHD group (Figure 6.13)."""
    import matplotlib.pyplot as plt
    df = saheart()
    x = df.loc[df["chd"] == 1, "sbp"].to_numpy(float)
    h = bw_silverman(x)
    g = np.linspace(100, 220, 600)
    fig, ax = plt.subplots(figsize=(6.0, 3.4))
    for xi in x:
        ax.plot(g, d_gauss((g - xi) / h) / h / 10, color="#9db4d6", lw=0.5, alpha=0.7)
    ax.plot(g, kde(g, x, h), color=RED, lw=1.6)
    ax.plot(x, np.full_like(x, 0.0), "|", color=GREEN, ms=8)
    ax.set_xlabel("Systolic Blood Pressure (for CHD group)")
    ax.set_ylabel("Density Estimate")
    fig.tight_layout()
    savefig(fig, CH, "fig6-13", out_dir)
    print("  N = %d, Silverman bandwidth %.3f; peak of the estimate %.4f at %.1f" % (len(x), h, kde(g, x, h).max(), g[np.argmax(kde(g, x, h))]))
    return h


def fig_6_14(out_dir=None):
    """Class-wise Gaussian KDEs of systolic blood pressure and the posterior (6.25) (Figure 6.14)."""
    import matplotlib.pyplot as plt
    df = saheart()
    x1 = df.loc[df["chd"] == 1, "sbp"].to_numpy(float)
    x0 = df.loc[df["chd"] == 0, "sbp"].to_numpy(float)
    h1, h0 = bw_silverman(x1), bw_silverman(x0)
    pi1 = len(x1) / (len(x1) + len(x0))
    g = np.linspace(100, 220, 600)
    post = kde_classifier(g, [x0, x1], [1 - pi1, pi1], [h0, h1])[:, 1]
    fig, axes = plt.subplots(1, 2, figsize=(8.4, 3.2))
    axes[0].plot(g, kde(g, x1, h1), color=ORANGE, label="CHD")
    axes[0].plot(g, kde(g, x0, h0), color=CYAN, label="no CHD")
    axes[0].plot(x1, np.full_like(x1, -0.0006), "|", color=ORANGE, ms=6)
    axes[0].plot(x0, np.full_like(x0, 0.0262), "|", color=CYAN, ms=6)
    axes[0].legend(frameon=True, fontsize=8)
    axes[0].set_ylabel("Density Estimates")
    axes[1].plot(g, post, color=PURPLE)
    axes[1].axhline(0.5, color="black", ls="--", lw=0.8)
    axes[1].set_ylim(0, 1)
    axes[1].set_ylabel("Posterior Estimate")
    for ax in axes:
        ax.set_xlabel("Systolic Blood Pressure")
    fig.tight_layout()
    savefig(fig, CH, "fig6-14", out_dir)
    print("  bandwidths: CHD %.3f, no CHD %.3f; prior %.4f; posterior at 220 = %.3f" % (h1, h0, pi1, post[-1]))


FIG615 = dict(w=(0.45, 0.35, 0.20), mu=(0.12, 0.45, 0.85), sd=(0.05, 0.12, 0.04), a=-6.0, b=12.0)


def fig615_densities(g):
    """The constructed class densities of Figure 6.15 and the exact posterior."""
    P = FIG615
    h = sum(w * d_gauss((g - m) / s) / s for w, m, s in zip(P["w"], P["mu"], P["sd"]))
    s = expit(P["a"] + P["b"] * g)
    f1, f2 = h * (1 - s), h * s
    dg = g[1] - g[0]
    f1, f2 = f1 / (f1.sum() * dg), f2 / (f2.sum() * dg)
    return f1, f2


def fig_6_15(out_dir=None):
    """Multimodal class densities whose posterior is a smooth logistic curve (Figure 6.15)."""
    import matplotlib.pyplot as plt
    g = np.linspace(0, 1, 801)
    f1, f2 = fig615_densities(g)
    post = f2 / (f1 + f2)
    fig, axes = plt.subplots(1, 2, figsize=(8.0, 2.6))
    axes[0].plot(g, f1, color=CYAN)
    axes[0].plot(g, f2, color=ORANGE)
    axes[0].set_yticks([])
    axes[0].set_title("class densities", fontsize=9)
    axes[1].plot(g, post, color=PURPLE)
    axes[1].axhline(0.5, color="black", ls="--", lw=0.8)
    axes[1].set_ylim(0, 1.02)
    axes[1].set_title("posterior probability of the orange class", fontsize=9)
    fig.tight_layout()
    savefig(fig, CH, "fig6-15", out_dir)


RBF_CENTRES = (0.1, 0.55, 0.7, 0.9)
RBF_LAMBDA = 0.05


def fig_6_16(out_dir=None):
    """Gaussian radial basis functions of fixed width and their renormalised versions (Figure 6.16)."""
    import matplotlib.pyplot as plt
    g = np.linspace(0, 1, 801)
    H = rbf_basis(g, RBF_CENTRES, RBF_LAMBDA)
    Hn = rbf_basis(g, RBF_CENTRES, RBF_LAMBDA, normalise=True)
    cols = ("black", ORANGE, CYAN, GREEN)
    fig, axes = plt.subplots(2, 1, figsize=(6.4, 4.0), sharex=True)
    for j in range(4):
        axes[0].plot(g, H[:, j], color=cols[j])
        axes[1].plot(g, Hn[:, j], color=cols[j])
    axes[0].set_yticks([0, 2, 4, 6, 8])
    axes[1].set_yticks([0, 0.4, 0.8, 1.2])
    axes[1].set_xlabel(r"$x$")
    fig.tight_layout()
    savefig(fig, CH, "fig6-16", out_dir)
    print("  largest gap: sum of unnormalised bases at x = 0.32 is %.2e" % H[np.argmin(np.abs(g - 0.32))].sum())


def fig617_fit():
    df = saheart()
    age = df["age"].to_numpy(float)
    chd = df["chd"].to_numpy(int)
    fit = em_gauss_1d(age, 2)
    k2 = int(np.argmax(fit["mu"]))          # the older component plays the role of component 2
    delta = (fit["resp"][:, k2] > 0.5).astype(int)
    tab = np.array([[np.sum((chd == a) & (delta == b)) for b in (0, 1)] for a in (0, 1)])
    b = logistic_fit(age, chd.astype(float))
    lr_err = float(np.mean((expit(b[0] + b[1] * age) > 0.5) != chd))
    return dict(fit=fit, k2=k2, table=tab, err=float((tab[0, 1] + tab[1, 0]) / len(chd)), lr_err=lr_err, age=age, chd=chd)


def fig_6_17(out_dir=None):
    """Histograms of Age by CHD group and a two-component Gaussian mixture fitted by EM (Figure 6.17)."""
    import matplotlib.pyplot as plt
    R = fig617_fit()
    fit, age, chd, k2 = R["fit"], R["age"], R["chd"], R["k2"]
    k1 = 1 - k2
    fig, axes = plt.subplots(2, 3, figsize=(9.0, 5.2))
    bins = np.arange(14.5, 65.5, 2)
    for ax, sel, col, title in zip(axes[0], (chd == 0, chd == 1, np.ones(len(chd), bool)), (ORANGE, CYAN, GREEN), ("No CHD", "CHD", "Combined")):
        ax.hist(age[sel], bins=bins, color=col, edgecolor="black", lw=0.4)
        ax.set_title(title)
        ax.set_xlabel("Age")
        ax.set_ylabel("Count")
    g = np.linspace(15, 65, 400)
    phi = [d_gauss((g - fit["mu"][k]) / math.sqrt(fit["var"][k])) / math.sqrt(fit["var"][k]) for k in range(2)]
    axes[1, 0].plot(g, phi[k1], color=ORANGE)
    axes[1, 1].plot(g, phi[k2], color=CYAN)
    axes[1, 2].plot(g, phi[k1], color=ORANGE)
    axes[1, 2].plot(g, phi[k2], color=CYAN)
    axes[1, 2].plot(g, fit["alpha"][k1] * phi[k1] + fit["alpha"][k2] * phi[k2], color=GREEN)
    for ax in axes[1]:
        ax.set_ylim(0, 0.11)
        ax.set_xlabel("Age")
        ax.set_ylabel("Mixture Estimate")
    fig.tight_layout()
    savefig(fig, CH, "fig6-17", out_dir)
    print("  mu = (%.2f, %.2f), var = (%.2f, %.2f), alpha = (%.3f, %.3f), %d EM iterations"
          % (fit["mu"][k1], fit["mu"][k2], fit["var"][k1], fit["var"][k2], fit["alpha"][k1], fit["alpha"][k2], fit["iters"]))
    print("  table (rows CHD no/yes, columns delta 0/1):", R["table"].tolist(), "error %.3f; logistic regression on age %.3f" % (R["err"], R["lr_err"]))
    return R


def fig_6_s2(out_dir=None):
    """Supplementary (Exercise 6.12): training and test error of local LDA on the zip-code data."""
    import matplotlib.pyplot as plt
    res = local_lda_errors()
    labs = [("%g" % float(l)) if l != "inf" else r"$\infty$ (LDA)" for l in res["lams"]]
    fig, ax = plt.subplots(figsize=(5.0, 3.0))
    xs = np.arange(len(labs))
    ax.plot(xs, res["train"], "o-", color=BLUE, label="training error")
    ax.plot(xs, res["test"], "s-", color=RED, label="test error")
    ax.set_xticks(xs)
    ax.set_xticklabels(labs)
    ax.set_xlabel(r"kernel width $\lambda$")
    ax.set_ylabel("misclassification rate")
    ax.set_ylim(0, None)
    ax.legend(frameon=False)
    fig.tight_layout()
    savefig(fig, CH, "fig6-S2", out_dir)


FIGURES = {"6.1": fig_6_1, "6.2": fig_6_2, "6.3": fig_6_3, "6.4": fig_6_4, "6.5": fig_6_5, "6.6": fig_6_6,
           "6.7": fig_6_7, "6.8": fig_6_8, "6.9": fig_6_9, "6.S1": fig_6_s1, "6.12": fig_6_12, "6.13": fig_6_13,
           "6.14": fig_6_14, "6.15": fig_6_15, "6.16": fig_6_16, "6.17": fig_6_17, "6.S2": fig_6_s2}

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