"""Hastie, Tibshirani and Friedman (2009), Chapter 12: Support Vector Machines and Flexible Discriminants.

Reproduces the figures of Chapter 12 of T. Hastie, R. Tibshirani and J. Friedman, The Elements of
Statistical Learning (2nd edition, Springer, 2009), pp. 417-458, written from scratch with numpy, scipy
and matplotlib. Every method is a small function meant to be read next to the lecture notes
(../ch12-svm-flexible-discriminants.html):

* Kernels (12.22): kernel() gives the linear, polynomial (1 + <x, x'>)^d, radial exp(-gamma ||x - x'||^2)
  and tanh kernels; poly2_features() is the explicit feature map (12.23).
* The support vector classifier, Section 12.2: svm_smo() solves the dual (12.13)/(12.19) by sequential
  minimal optimisation (pairs chosen by maximal violation with second-order information);
  svm_intercept() recovers beta_0 from the KKT conditions (12.14)-(12.16); svm_polish() solves the KKT
  system exactly once the active sets are known; SVC wraps them.
* The SVM path, Section 12.3.5 (Hastie, Rosset, Tibshirani and Zhu 2004): svm_path() follows the
  piecewise-linear multipliers a_i(lambda) of the loss + penalty form (12.25)/(12.34) from the largest
  lambda down to lambda_min, event by event; path_at() and path_decision() read the solution at any
  lambda = 1/C. The figures use the path, which is exact at every C (the SMO solver and LIBSVM agree
  with it where they converge).
* Kernel logistic regression (12.31)-(12.32): kernel_logistic() is Newton's method with step halving.
* Losses: hinge, binomial deviance, squared error, the Huberised square hinge (Figure 12.4, Table 12.1,
  population_minimiser()), the epsilon-insensitive loss (12.37) and Huber's loss (12.38).
* Flexible discriminant analysis, Sections 12.5-12.6: OptimalScoring is the computation of Section 12.5.1
  for any linear (optionally penalised, (12.57)) regression operator: regression of the indicator (or
  blurred) responses on a basis, the eigen-decomposition of Y^T Yhat with Theta^T D_pi Theta = I, and the
  distances (12.54) with the weights (12.55). Bases: ns_basis() (natural cubic splines (5.4)-(5.5)),
  additive_ns_basis(), poly_basis(), and MARS (a compact multi-response MARS, Chapter 9, with knots
  at quantiles and GCV pruning). LDA and QDA are fitted directly for comparison.
* Penalised discriminant analysis: diff_penalty() (roughness of a coefficient sequence) and
  image_penalty() (of a 16 x 16 coefficient image); lam_for_df() sets the penalty from an effective
  number of degrees of freedom.
* Mixture discriminant analysis, Section 12.7: MDAGauss runs EM (12.59)-(12.62) directly, with the
  within-class k-means start of the book (kmeans_js(), whose random starts use the demos' generator
  ch02.JSRandom); MDAScoring does the M-step by (penalised) optimal scoring on the blurred response
  matrix (12.63), which equals MDAGauss for the plain linear regression.
* Data: the mixture data of Chapter 2 (through ch02_overview_supervised_learning, with its 10,000-point
  test set), vowel, zip-code digits and phoneme data from the book's website, the waveform model
  (12.64) (waveform_sample()) and the 'skin of the orange' simulation of Section 12.3.4
  (orange_sample()).
* Exercises: phoneme_split() and exercise_12_5() (smooth k-means prototypes),
  kernel_ridge_with_intercept() (Exercise 12.3), kernel_lda_two_class() (Exercise 12.10) and mda2_em()
  (Exercise 12.11).

Figures reproduced: 12.1-12.15. Tables printed: 12.2 (orange_table(), cached), 12.3 (vowel_table()),
12.4 (by fig_12_15, cached). Run `python3 ch12_svm_flexible_discriminants.py --list`,
`python3 ch12_svm_flexible_discriminants.py` (all figures, about two minutes once the tables are
cached; the two simulation tables take several minutes the first time) or
`python3 ch12_svm_flexible_discriminants.py --fig 12.6`. Files go to ../img/ch12/; the demos' data go to
../data/ch12-vowel.json (the SVM and MDA demos read ../data/ch02-mixture.json).

Figures not reproduced by code: none. Figure 12.1 is a schematic in the book; here it is drawn from a
computed hard-margin and soft-margin fit on two small simulated clouds.

Settings chosen where the book gives none:
* Mixture figures (12.2, 12.3, 12.5, 12.6, 12.13): test errors on the 10,000-point test set of Chapter 2;
  the Bayes rate is the integral of Chapter 2 (0.208; the book prints 0.210).
* Figure 12.5: the penalty of the kernel logistic regression is lambda = 1 = 1/C, the value of
  Figure 12.3; the broken curves are the 0.25 and 0.75 probability contours.
* Figure 12.6: C on a grid of 101 values from 0.1 to 10^4, read off the exact path.
* Figure 12.7: twelve points of our own (numpy seed 12), shown at lambda = 1.
* Figure 12.9: 50 points per class (numpy seed 129).
* Figure 12.10 and Table 12.3: the adaptive additive splines (BRUTO) of the book are replaced by additive
  natural cubic splines with 4 df per input (knots at training quantiles), unpenalised; MARS uses 20
  knots per input, at most 41 (degree 1) or 61 (degree 2) terms.
* Figures 12.11-12.12: PDA with the second-difference roughness penalty of the coefficient image,
  lambda = 3000 (pixel values as given, in [-1, 1]).
* Figure 12.13: MARS with degree 2, 20 knots per input, at most 21 terms, GCV penalty 2; MDA with five
  subclasses per class from the k-means start with seed 1.
* Table 12.4 and Figures 12.14-12.15: ten training sets of 300 and test sets of 500 (numpy seed 2009);
  'penalised to 4 df' is lambda such that tr[Xc (Xc^T Xc + lambda Omega)^{-1} Xc^T] = 4 with Omega the
  second-difference penalty on j = 1..21 (the book does not define its df; rows with 8 df are added);
  CART is a scikit-learn tree pruned by 10-fold cross-validation.
* Table 12.2: 50 simulations, 100 training points per class and 500 test points per class (numpy seed
  12); the SVMs use LIBSVM through scikit-learn with C picked from 13 values between 10^-3 and 10^3 by
  test error, as in the book; BRUTO is replaced by additive natural splines with 4 df per input.
"""
import json
import math
import os

import numpy as np
from scipy import linalg

import common
from common import BLUE, GREEN, GREY, ORANGE, PURPLE, RED, savefig
import ch02_overview_supervised_learning as ch02

CH = 12
HERE = os.path.dirname(os.path.abspath(__file__))
CACHE_DIR = os.path.join(HERE, "cache")
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
MIX_BLUE, MIX_ORANGE = ch02.MIX_BLUE, ch02.MIX_ORANGE


# =========================================================================== data
def mixture():
    """The mixture data of Section 2.3 with labels coded -1 (BLUE) / +1 (ORANGE), the 20 means, the
    book's plotting grid, and the 10,000-point test set of Chapter 2 (numpy seed 2009)."""
    d = ch02.mixture()
    Xt, gt = ch02.mixture_test(d["means"])
    d = dict(d)
    d["ypm"] = 2.0 * d["y"] - 1.0
    d["Xt"], d["yt"] = Xt, 2.0 * gt - 1.0
    return d


def bayes_prob(P, means):
    return ch02.bayes_prob(P, means)


def vowel():
    """Vowel data: (Xtr, gtr, Xte, gte), classes coded 0..10."""
    tr, te = common.esl_data("vowel.train"), common.esl_data("vowel.test")
    cols = ["x.%d" % j for j in range(1, 11)]
    return (tr[cols].values.astype(float), tr["y"].values - 1,
            te[cols].values.astype(float), te["y"].values - 1)


def zip_digits():
    """Zip-code digits: (Xtr, gtr, Xte, gte), 16 x 16 grey levels in [-1, 1] stored row by row."""
    tr = np.loadtxt(common.esl_file("zip.train.gz"))
    te = np.loadtxt(common.esl_file("zip.test.gz"))
    return tr[:, 1:], tr[:, 0].astype(int), te[:, 1:], te[:, 0].astype(int)


def error_rate(pred, g):
    return float(np.mean(np.asarray(pred) != np.asarray(g)))


# =========================================================================== kernels (12.22)
def kernel(A, B, kind="linear", degree=2, gamma=1.0, coef0=1.0, kappa=(1.0, 0.0)):
    """Kernel matrix K(a_i, b_j). 'poly' is (coef0 + <x, x'>)^degree, (12.22) with coef0 = 1;
    'rbf' is exp(-gamma ||x - x'||^2); 'tanh' is tanh(kappa1 <x, x'> + kappa2)."""
    A, B = np.atleast_2d(A), np.atleast_2d(B)
    G = A @ B.T
    if kind == "linear":
        return G
    if kind == "poly":
        return (coef0 + G) ** degree
    if kind == "rbf":
        d2 = (A * A).sum(1)[:, None] + (B * B).sum(1)[None, :] - 2 * G
        return np.exp(-gamma * np.maximum(d2, 0.0))
    if kind == "tanh":
        return np.tanh(kappa[0] * G + kappa[1])
    raise ValueError(kind)


def poly2_features(X):
    """The explicit feature map of the degree-2 polynomial kernel in two inputs, (12.23):
    h = (1, sqrt2 x1, sqrt2 x2, x1^2, x2^2, sqrt2 x1 x2), so that <h(x), h(x')> = (1 + <x, x'>)^2."""
    x1, x2 = X[:, 0], X[:, 1]
    r2 = math.sqrt(2.0)
    return np.column_stack([np.ones(len(X)), r2 * x1, r2 * x2, x1 ** 2, x2 ** 2, r2 * x1 * x2])


# =========================================================================== the support vector classifier
def svm_smo(K, y, C, tol=1e-9, max_iter=500000):
    """Solve the dual (12.13)/(12.19): maximise sum(a) - a^T Q a / 2 with Q = (y y^T) * K, subject to
    0 <= a_i <= C and sum a_i y_i = 0, by sequential minimal optimisation (pairs chosen by maximal
    violation with second-order information, as in LIBSVM). Returns (alpha, beta0)."""
    y = np.asarray(y, float)
    N = len(y)
    Q = (y[:, None] * y[None, :]) * K
    a = np.zeros(N)
    G = -np.ones(N)                   # gradient of the minimisation form a^T Q a / 2 - sum(a)
    dK = np.diag(K).copy()
    for _ in range(max_iter):
        up = ((y > 0) & (a < C)) | ((y < 0) & (a > 0))
        low = ((y > 0) & (a > 0)) | ((y < 0) & (a < C))
        mG = -y * G
        iu = np.flatnonzero(up)
        i = iu[np.argmax(mG[iu])]
        m_up = mG[i]
        il = np.flatnonzero(low)
        if m_up - mG[il].min() < tol:
            break
        cand = il[mG[il] < m_up]
        b = m_up - mG[cand]
        aa = np.maximum(dK[i] + dK[cand] - 2 * K[i, cand], 1e-12)
        j = cand[np.argmax(b * b / aa)]
        # analytic update of the pair (i, j) along the constraint y_i a_i + y_j a_j = const
        quad = max(K[i, i] + K[j, j] - 2 * K[i, j], 1e-12)
        if y[i] != y[j]:
            delta = (-G[i] - G[j]) / quad
            diff = a[i] - a[j]
            ai, aj = a[i] + delta, a[j] + delta
            if diff > 0:
                if aj < 0:
                    aj, ai = 0.0, diff
            else:
                if ai < 0:
                    ai, aj = 0.0, -diff
            if diff > 0:
                if ai > C:
                    ai, aj = C, C - diff
            else:
                if aj > C:
                    aj, ai = C, C + diff
        else:
            delta = (G[i] - G[j]) / quad
            s = a[i] + a[j]
            ai, aj = a[i] - delta, a[j] + delta
            if s > C:
                if ai > C:
                    ai, aj = C, s - C
            else:
                if aj < 0:
                    aj, ai = 0.0, s
            if s > C:
                if aj > C:
                    aj, ai = C, s - C
            else:
                if ai < 0:
                    ai, aj = 0.0, s
        dai, daj = ai - a[i], aj - a[j]
        a[i], a[j] = ai, aj
        G += Q[:, i] * dai + Q[:, j] * daj
    return a, svm_intercept(K, y, a, C)


def svm_intercept(K, y, a, C, rel=1e-8):
    """beta_0 from (12.14): the average of y_i - sum_j a_j y_j K_ij over the margin points
    0 < a_i < C; if there are none, the midpoint of the interval of values allowed by the KKT
    conditions."""
    g = K @ (a * y)
    free = (a > rel * C) & (a < C * (1 - rel))
    if free.any():
        return float(np.mean(y[free] - g[free]))
    lo, hi = -np.inf, np.inf
    for yi, gi, ai in zip(y, g, a):
        r = yi - gi
        at_zero, at_c = ai <= rel * C, ai >= C * (1 - rel)
        # a_i = 0 needs y_i f_i >= 1; a_i = C needs y_i f_i <= 1
        if (at_zero and yi > 0) or (at_c and yi < 0):
            lo = max(lo, r)
        else:
            hi = min(hi, r)
    return float(0.5 * (lo + hi))


class SVC:
    """Support vector classifier / machine fitted by svm_smo: f(x) = sum_i a_i y_i K(x, x_i) + beta_0,
    (12.20) and (12.24). Labels y in {-1, +1}."""

    def __init__(self, C=1.0, kind="linear", **kw):
        self.C, self.kind, self.kw = C, kind, kw

    def fit(self, X, y):
        self.X, self.y = np.asarray(X, float), np.asarray(y, float)
        K = kernel(self.X, self.X, self.kind, **self.kw)
        self.alpha, self.b0 = svm_smo(K, self.y, self.C)
        self.f_train = K @ (self.alpha * self.y) + self.b0
        return self

    def decision(self, P):
        return kernel(np.asarray(P, float), self.X, self.kind, **self.kw) @ (self.alpha * self.y) + self.b0

    def beta(self):
        """beta = sum_i a_i y_i x_i (12.17), linear kernel only."""
        return (self.alpha * self.y) @ self.X

    def support(self, rel=1e-7):
        return self.alpha > rel * self.C

    def on_margin(self, rel=1e-7):
        return (self.alpha > rel * self.C) & (self.alpha < self.C * (1 - rel))


def svm_primal_objective(K, y, a, b0, C):
    """(12.8) at the dual solution: ||beta||^2 / 2 + C sum xi_i with xi_i = [1 - y_i f_i]_+."""
    f = K @ (a * y) + b0
    return 0.5 * float((a * y) @ K @ (a * y)) + C * float(np.maximum(0, 1 - y * f).sum())


def svm_dual_objective(K, y, a):
    """L_D of (12.13)/(12.19)."""
    return float(a.sum() - 0.5 * (a * y) @ K @ (a * y))


def svm_polish(K, y, a, C, rel=1e-6, rounds=20):
    """Refine an approximate dual solution exactly: fix the points at the bounds 0 and C, solve the
    linear KKT system (12.10)-(12.14) for the margin points and beta_0, and repeat while the bound
    sets change. Returns (alpha, beta0) or None if the sets do not settle."""
    y = np.asarray(y, float)
    for _ in range(rounds):
        F = (a > rel * C) & (a < C * (1 - rel))
        U = a >= C * (1 - rel)
        if not F.any():
            return a, svm_intercept(K, y, a, C)
        iF = np.flatnonzero(F)
        n = len(iF)
        A = np.zeros((n + 1, n + 1))
        A[:n, :n] = K[np.ix_(iF, iF)] * y[iF][:, None] * y[iF][None, :]
        A[:n, n] = y[iF]
        A[n, :n] = y[iF]
        rhs = np.r_[1.0 - y[iF] * (K[np.ix_(iF, np.flatnonzero(U))] @ (C * y[U])), -C * y[U].sum()]
        sol = np.linalg.lstsq(A, rhs, rcond=None)[0]
        new = np.where(U, C, 0.0)
        new[iF] = sol[:n]
        b0 = sol[n]
        f = K @ (new * y) + b0
        yf = y * f
        bad = (new < -1e-10 * C) | (new > C * (1 + 1e-10)) | ((new <= rel * C) & (yf < 1 - 1e-7)) | ((new >= C * (1 - rel)) & (yf > 1 + 1e-7))
        if not bad.any():
            return np.clip(new, 0, C), float(b0)
        a = np.clip(new, 0, C)
    return None


# =========================================================================== the SVM path (Section 12.3.5)
def svm_path(K, y, lam_min=1e-4, max_steps=20000, tol=1e-11):
    """The entire regularisation path of the SVM in the loss + penalty form (12.25), Hastie, Rosset,
    Tibshirani and Zhu (2004): f_lambda(x) = (sum_i a_i y_i K(x, x_i) + a_0) / lambda (12.34) with
    a_i in [0, 1]. Starts at the largest lambda where the solution is determined (all a_i = 1; needs
    balanced classes) and decreases lambda to lam_min. Between breakpoints every a_i and a_0 are
    linear in lambda, so the path is stored at its breakpoints only.

    Returns dict(lam = breakpoints (decreasing), alpha (n_knots x N), alpha0, event = description)."""
    y = np.asarray(y, float)
    N = len(y)
    if (y > 0).sum() != (y < 0).sum():
        raise ValueError("this implementation starts the path for balanced classes only")
    a = np.ones(N)
    g = K @ y
    ip = np.flatnonzero(y > 0)[np.argmax(g[y > 0])]
    im = np.flatnonzero(y < 0)[np.argmin(g[y < 0])]
    lam = 0.5 * (g[ip] - g[im])
    a0 = -0.5 * (g[ip] + g[im])
    state = np.full(N, "L", dtype="<U1")      # L: y f < 1 (a = 1); E: y f = 1; R: y f > 1 (a = 0)
    state[[ip, im]] = "E"
    lams, alphas, a0s, events = [lam], [a.copy()], [a0], ["start: points %d and %d reach the margin" % (ip, im)]
    for step in range(max_steps):
        E = np.flatnonzero(state == "E")
        h = K @ (a * y) + a0                       # h_i = lambda f(x_i)
        if len(E) == 0:
            res = _empty_elbow(K, y, a, state, lam, lam_min)
            if res is None:
                break
            lam, a0, pair = res
            state[list(pair)] = "E"
            lams.append(lam); alphas.append(a.copy()); a0s.append(a0)
            events.append("empty elbow: points %d and %d reach the margin" % pair)
            continue
        # derivatives b = da/dlambda (elbow), b0 = da0/dlambda, from y_i h_i = lambda on the elbow
        n = len(E)
        A = np.zeros((n + 1, n + 1))
        A[:n, :n] = K[np.ix_(E, E)] * y[E][None, :]
        A[:n, n] = 1.0
        A[n, :n] = y[E]
        rhs = np.r_[y[E], 0.0]
        try:
            sol = np.linalg.solve(A, rhs)
        except np.linalg.LinAlgError:
            sol = np.linalg.lstsq(A, rhs, rcond=None)[0]
        b, b0 = sol[:n], sol[n]
        dh = K[:, E] @ (y[E] * b) + b0             # dh_i / dlambda
        # lambda decreases by delta: a_E -> a_E - delta b, h -> h - delta dh
        cands = []
        for k, j in enumerate(E):
            if b[k] > tol:
                cands.append((a[j] / b[k], j, "R"))
            elif b[k] < -tol:
                cands.append(((a[j] - 1.0) / b[k], j, "L"))
        out = np.flatnonzero(state != "E")
        den = 1.0 - y[out] * dh[out]
        num = lam - y[out] * h[out]
        with np.errstate(divide="ignore", invalid="ignore"):
            dl = num / den
        for i, dlt, nm, dn in zip(out, dl, num, den):
            if state[i] == "L" and dn > tol and dlt > -1e-12:
                cands.append((max(dlt, 0.0), i, "E"))
            elif state[i] == "R" and dn < -tol and dlt > -1e-12:
                cands.append((max(dlt, 0.0), i, "E"))
        cands.append((lam - lam_min, -1, "stop"))
        delta, j, to = min(cands, key=lambda c: c[0])
        lam_new = lam - delta
        a[E] = np.clip(a[E] - delta * b, 0.0, 1.0)
        a0 = a0 - delta * b0
        lam = lam_new
        if to == "stop":
            lams.append(lam); alphas.append(a.copy()); a0s.append(a0); events.append("stop at lambda_min")
            break
        if to == "E":
            events.append("point %d (%s) reaches the margin" % (j, state[j]))
            state[j] = "E"
        else:
            a[j] = 0.0 if to == "R" else 1.0
            state[j] = to
            events.append("point %d leaves the margin to %s" % (j, to))
        lams.append(lam); alphas.append(a.copy()); a0s.append(a0)
        if lam <= lam_min * (1 + 1e-12):
            break
    return dict(lam=np.array(lams), alpha=np.array(alphas), alpha0=np.array(a0s), event=events)


def _empty_elbow(K, y, a, state, lam, lam_min):
    """With no point on the margin the a_i stay fixed and a_0 is free within an interval that shrinks
    as lambda decreases; find the largest lambda' <= lambda at which it collapses (two points, one of
    each class, reach their margins together)."""
    g = K @ (a * y)

    def gap(l):
        lo, hi = -np.inf, np.inf
        for i in range(len(y)):
            if state[i] == "L":     # y (g + a0) <= l
                if y[i] > 0:
                    hi = min(hi, l - g[i])
                else:
                    lo = max(lo, -l - g[i])
            else:                   # R: y (g + a0) >= l
                if y[i] > 0:
                    lo = max(lo, l - g[i])
                else:
                    hi = min(hi, -l - g[i])
        return hi - lo, lo, hi
    if gap(lam_min)[0] >= 0:
        return None
    lo_l, hi_l = lam_min, lam
    for _ in range(200):
        mid = 0.5 * (lo_l + hi_l)
        if gap(mid)[0] >= 0:
            hi_l = mid
        else:
            lo_l = mid
    l = hi_l
    _, lo, hi = gap(l)
    a0 = 0.5 * (lo + hi)
    yh = y * (g + a0)
    order = np.argsort(np.abs(yh - l))
    i1 = order[0]
    i2 = next(i for i in order[1:] if y[i] != y[i1])
    return l, a0, (int(i1), int(i2))


def path_at(path, lam):
    """(alpha, alpha0) at any lambda, by linear interpolation between breakpoints (exact)."""
    L = path["lam"]
    if lam >= L[0]:
        return path["alpha"][0].copy(), path["alpha0"][0]      # above lambda_0 we return the start
    k = np.searchsorted(-L, -lam)            # L[k-1] > lam >= L[k]
    k = min(max(k, 1), len(L) - 1)
    t = (L[k - 1] - lam) / (L[k - 1] - L[k])
    return (1 - t) * path["alpha"][k - 1] + t * path["alpha"][k], (1 - t) * path["alpha0"][k - 1] + t * path["alpha0"][k]


def path_decision(path, Kq, y, lam):
    """f_lambda at query points, Kq = K(query, training) (12.34)."""
    a, a0 = path_at(path, lam)
    return (Kq @ (a * y) + a0) / lam


# =========================================================================== kernel logistic regression (12.31)
def kernel_logistic(K, y, lam, tol=1e-12, maxit=100):
    """Minimise sum_i log(1 + exp(-y_i f_i)) + (lam / 2) a^T K a with f = b0 + K a (the binomial
    loss in (12.29) in place of the hinge). Newton's method on the stationarity equations
    p - t + lam a = 0, sum(p - t) = 0 (t = (1 + y) / 2, p = Pr(Y = +1 | x)), whose solution is also the
    unique minimiser of the convex criterion in f; step halving keeps the criterion decreasing.
    Returns (a, b0)."""
    y = np.asarray(y, float)
    N = len(y)
    t = 0.5 * (1 + y)
    a, b0 = np.zeros(N), 0.0

    def crit(a, b0):
        f = b0 + K @ a
        return float(np.logaddexp(0, -y * f).sum() + 0.5 * lam * a @ K @ a)
    obj = crit(a, b0)
    for _ in range(maxit):
        f = b0 + K @ a
        p = common.sigmoid(f)
        w = p * (1 - p)
        F = np.r_[p - t + lam * a, (p - t).sum()]
        J = np.zeros((N + 1, N + 1))
        J[:N, :N] = w[:, None] * K + lam * np.eye(N)
        J[:N, N] = w
        J[N, :N] = w @ K
        J[N, N] = w.sum()
        step = np.linalg.solve(J, -F)
        s = 1.0
        while True:
            a1, b1 = a + s * step[:N], b0 + s * step[N]
            o1 = crit(a1, b1)
            if o1 <= obj + 1e-12 * abs(obj) or s < 1e-8:
                break
            s *= 0.5
        a, b0, obj = a1, b1, o1
        if np.abs(F).max() < tol:
            break
    return a, float(b0)


# =========================================================================== loss functions (Figure 12.4, Table 12.1)
def loss_hinge(m):
    return np.maximum(0.0, 1.0 - m)


def loss_deviance(m):
    """Binomial deviance log(1 + e^{-m}); its left-tail slope is already -1."""
    return np.logaddexp(0.0, -m)


def loss_squared(m):
    return (1.0 - m) ** 2


def loss_huber_sq_hinge(m):
    """The 'Huberised' squared hinge of Rosset and Zhu (2007): -4m for m < -1, [1 - m]_+^2 otherwise."""
    m = np.asarray(m, float)
    return np.where(m < -1, -4 * m, np.maximum(0.0, 1 - m) ** 2)


def population_minimiser(loss, p, grid=np.linspace(-3, 3, 600001)):
    """argmin_f p L(f) + (1 - p) L(-f) by a fine grid search (Table 12.1)."""
    v = p * loss(grid) + (1 - p) * loss(-grid)
    return float(grid[np.argmin(v)])


def eps_insensitive(r, eps):
    """V_epsilon(r) of (12.37)."""
    return np.maximum(0.0, np.abs(r) - eps)


def huber(r, c):
    """V_H(r) of (12.38)."""
    r = np.abs(r)
    return np.where(r <= c, 0.5 * r * r, c * r - 0.5 * c * c)


# =========================================================================== mixture-data panels
XLIM, YLIM = (-2.75, 4.35), (-2.1, 3.0)


def _grid(n1=420, n2=320):
    gx = np.linspace(XLIM[0], XLIM[1], n1)
    gy = np.linspace(YLIM[0], YLIM[1], n2)
    XX, YY = np.meshgrid(gx, gy)
    return XX, YY, np.column_stack([XX.ravel(), YY.ravel()])


def mixture_panel(ax, d, f, title=None, margins=True, sv=None, on_margin=None, prob_levels=None,
                  text=None, centres=None):
    """The style of Figures 12.2-12.3, 12.5 and 12.13: the book's dot grid coloured by the sign of
    f, the boundary f = 0 (solid), the margins f = +-1 (dashed), the Bayes boundary (purple dashes),
    the training points, the margin points as black dots and a box with the error rates.
    prob_levels draws extra contours of f (e.g. the logits of 0.25 and 0.75)."""
    G = d["xnew"]
    cls = f(G) > 0
    ax.scatter(G[~cls, 0], G[~cls, 1], s=0.5, color=MIX_BLUE, lw=0, rasterized=True)
    ax.scatter(G[cls, 0], G[cls, 1], s=0.5, color=MIX_ORANGE, lw=0, rasterized=True)
    XX, YY, P = _grid()
    Z = f(P).reshape(XX.shape)
    ax.contour(XX, YY, Z, levels=[0.0], colors="black", linewidths=1.2)
    if margins:
        ax.contour(XX, YY, Z, levels=[-1.0, 1.0], colors="black", linewidths=0.9, linestyles="dashed")
    if prob_levels is not None:
        ax.contour(XX, YY, Z, levels=sorted(prob_levels), colors="black", linewidths=0.9, linestyles="dashed")
    B = bayes_prob(P, d["means"]).reshape(XX.shape)
    ax.contour(XX, YY, B, levels=[0.5], colors=PURPLE, linewidths=1.1, linestyles=[(0, (4, 3))])
    X, y = d["X"], d["ypm"]
    ax.scatter(X[y < 0, 0], X[y < 0, 1], s=20, facecolors="none", edgecolors=MIX_BLUE, linewidths=1.0)
    ax.scatter(X[y > 0, 0], X[y > 0, 1], s=20, facecolors="none", edgecolors=MIX_ORANGE, linewidths=1.0)
    if on_margin is not None and on_margin.any():
        ax.scatter(X[on_margin, 0], X[on_margin, 1], s=16, color="black", zorder=5)
    if centres is not None:
        for c, col in centres:
            ax.scatter(c[:, 0], c[:, 1], s=70, marker="o", color=col, edgecolors="black", linewidths=1.2, zorder=6)
    if text:
        ax.text(0.03, 0.03, text, transform=ax.transAxes, fontsize=8.3, va="bottom", ha="left",
                bbox=dict(boxstyle="round,pad=0.25", fc="white", ec="none", alpha=0.85), family="monospace")
    ax.set_xlim(*XLIM)
    ax.set_ylim(*YLIM)
    ax.set_xticks([])
    ax.set_yticks([])
    if title:
        ax.set_title(title)


def err_text(train, test, bayes=0.210, digits=3):
    fmt = "%." + str(digits) + "f"
    return ("Training Error: " + fmt + "\nTest Error:     " + fmt + "\nBayes Error:    " + fmt) % (train, test, bayes)


_MIX_CACHE = {}


def mixture_cached():
    if "d" not in _MIX_CACHE:
        d = mixture()
        d["bayes_rate"] = ch02.bayes_error(d["means"])
        _MIX_CACHE["d"] = d
    return _MIX_CACHE["d"]


def svm_on_mixture(kind, C, **kw):
    """Exact SVM on the mixture data at cost C (from the path at lambda = 1/C), with its errors."""
    d = mixture_cached()
    X, y = d["X"], d["ypm"]
    K = kernel(X, X, kind, **kw)
    P = svm_path(K, y, lam_min=min(1e-4, 0.5 / C))
    lam = 1.0 / C
    a, a0 = path_at(P, lam)
    ftr = (K @ (a * y) + a0) / lam

    def f(Q):
        return (kernel(Q, X, kind, **kw) @ (a * y) + a0) / lam
    return dict(f=f, alpha=a * C, b0=a0 / lam, ftr=ftr, train=error_rate(np.sign(ftr), y),
                test=error_rate(np.sign(f(d["Xt"])), d["yt"]),
                sv=(a > 1e-9), margin=np.abs(y * ftr - 1) < 1e-7, path=P, K=K)


# =========================================================================== Figures 12.1-12.7
def toy_two_class(n=10, sep=2.4, seed=3):
    """Two small Gaussian clouds in the plane (for Figures 12.1)."""
    rng = np.random.default_rng(seed)
    X = np.vstack([rng.normal(size=(n, 2)) * 0.75 + [0, 0], rng.normal(size=(n, 2)) * 0.75 + [sep, sep * 0.55]])
    y = np.r_[-np.ones(n), np.ones(n)]
    return X, y


def fig_12_1(out_dir=None):
    """Support vector classifiers on toy data: separable (hard margin) and overlapping (soft margin, slacks)."""
    import matplotlib.pyplot as plt
    from matplotlib.patches import Polygon
    fig, axes = plt.subplots(1, 2, figsize=(9.2, 4.3))
    cases = [(toy_two_class(10, 3.4, 3), None, "Separable: maximal margin"),
             (toy_two_class(11, 2.0, 5), 1.0, "Overlapping: soft margin, C = 1")]
    out = []
    for ax, ((X, y), C, title) in zip(axes, cases):
        K = kernel(X, X, "linear")
        P = svm_path(K, y, lam_min=1e-6)
        lam = 1e-6 if C is None else 1.0 / C
        a, a0 = path_at(P, lam)
        beta = (a * y) @ X / lam
        b0 = a0 / lam
        M = 1.0 / np.linalg.norm(beta)
        f = X @ beta + b0
        xs = np.array([-3.0, 6.0])
        # the band between f = -1 and f = +1, shaded
        u = beta / np.linalg.norm(beta) ** 2
        d = np.array([-beta[1], beta[0]])
        d /= np.linalg.norm(d)
        pts = []
        for lev in (-1, 1):
            p0 = (lev - b0) * u
            pts.append([p0 - 8 * d, p0 + 8 * d])
        poly = [pts[0][0], pts[0][1], pts[1][1], pts[1][0]]
        ax.add_patch(Polygon(poly, closed=True, color="#f2e7c9", zorder=0))
        for lev, ls in ((0, "-"), (-1, "--"), (1, "--")):
            p0 = (lev - b0) * u
            seg = np.array([p0 - 8 * d, p0 + 8 * d])
            ax.plot(seg[:, 0], seg[:, 1], ls, color="black", lw=1.2 if lev == 0 else 0.9)
        ax.scatter(X[y < 0, 0], X[y < 0, 1], s=34, color=MIX_BLUE, edgecolors="black", linewidths=0.4, zorder=3)
        ax.scatter(X[y > 0, 0], X[y > 0, 1], s=34, color=MIX_ORANGE, edgecolors="black", linewidths=0.4, zorder=3)
        xi = np.maximum(0, 1 - y * f)
        k = 0
        for i in np.flatnonzero(xi > 1e-8):
            # the foot of the perpendicular from x_i to its own margin y f = 1
            foot = X[i] - ((f[i] - y[i]) / (beta @ beta)) * beta
            ax.annotate("", xy=foot, xytext=X[i], arrowprops=dict(arrowstyle="-", color=RED, lw=1.0))
            k += 1
            ax.text(*(0.5 * (X[i] + foot) + 0.08), r"$\xi^*_{%d}$" % k, color=RED, fontsize=9)
        # the margin M = 1 / ||beta|| drawn as an arrow from the boundary
        c = -b0 * u + 1.2 * d
        ax.annotate("", xy=c + beta / np.linalg.norm(beta) * M, xytext=c, arrowprops=dict(arrowstyle="<->", color="black", lw=0.9))
        ax.text(*(c + beta / np.linalg.norm(beta) * M * 0.5 + 0.12 * d), r"$M=1/\|\beta\|$", fontsize=9)
        ax.set_xlim(-2.5, 5.2)
        ax.set_ylim(-2.4, 4.0)
        ax.set_aspect("equal")
        ax.set_xticks([])
        ax.set_yticks([])
        ax.set_title(title)
        nsv = int((a > 1e-9).sum())
        out.append(dict(M=M, nsv=nsv, sum_xi_star=float((xi * M).sum()), n_slack=int((xi > 1e-8).sum())))
        print("  %s: M = %.3f, %d support points, %d points with xi > 0, sum xi* = %.3f" % (title, M, nsv, out[-1]["n_slack"], out[-1]["sum_xi_star"]))
    fig.tight_layout()
    savefig(fig, CH, "fig12-1", out_dir)
    return out


def fig_12_2(out_dir=None):
    """Linear support vector classifier on the mixture data, C = 10000 and C = 0.01."""
    import matplotlib.pyplot as plt
    d = mixture_cached()
    fig, axes = plt.subplots(2, 1, figsize=(4.6, 7.4))
    res = {}
    for ax, C, dg in zip(axes, (10000.0, 0.01), (3, 2)):
        r = svm_on_mixture("linear", C)
        mixture_panel(ax, d, r["f"], sv=r["sv"], on_margin=r["margin"], text=err_text(r["train"], r["test"], d["bayes_rate"], dg))
        ax.set_xlabel("C = %g" % C)
        res[C] = dict(train=r["train"], test=r["test"], sv_frac=float(r["sv"].mean()), n_margin=int(r["margin"].sum()))
        print("  C = %g: training error %.3f, test error %.4f, support points %.0f%%, on the margin %d"
              % (C, r["train"], r["test"], 100 * r["sv"].mean(), r["margin"].sum()))
    fig.tight_layout()
    savefig(fig, CH, "fig12-2", out_dir)
    return res


def fig_12_3(out_dir=None):
    """Nonlinear SVMs on the mixture data: degree-4 polynomial kernel and radial kernel (gamma = 1), C = 1."""
    import matplotlib.pyplot as plt
    d = mixture_cached()
    fig, axes = plt.subplots(2, 1, figsize=(4.6, 7.6))
    res = {}
    for ax, (kind, kw, title) in zip(axes, [("poly", dict(degree=4), "SVM: degree-4 polynomial in feature space"),
                                            ("rbf", dict(gamma=1.0), "SVM: radial kernel in feature space")]):
        r = svm_on_mixture(kind, 1.0, **kw)
        mixture_panel(ax, d, r["f"], title=title, text=err_text(r["train"], r["test"], d["bayes_rate"]))
        res[kind] = dict(train=r["train"], test=r["test"], nonsv=float(1 - r["sv"].mean()))
        print("  %s: training error %.3f, test error %.4f, non-support points %.0f%%" % (kind, r["train"], r["test"], 100 * (1 - r["sv"].mean())))
    fig.tight_layout()
    savefig(fig, CH, "fig12-3", out_dir)
    return res


def fig_12_4(out_dir=None):
    """The hinge loss against the binomial deviance, squared error and the Huberised squared hinge."""
    import matplotlib.pyplot as plt
    m = np.linspace(-3, 3, 1201)
    fig, ax = plt.subplots(figsize=(5.4, 4.0))
    ax.plot(m, loss_hinge(m), color=RED, label="Hinge loss")
    ax.plot(m, loss_deviance(m), color=GREEN, label="Binomial deviance")
    ax.plot(m, loss_squared(m) / 4, color=ORANGE, label="Squared error (/4)")
    ax.plot(m, loss_huber_sq_hinge(m) / 4, color=BLUE, label="Huberised square hinge (/4)")
    ax.axvline(0, color=GREY, ls=":", lw=1)
    ax.axhline(0, color=GREY, ls=":", lw=1)
    ax.set_ylim(-0.1, 3.1)
    ax.set_xlabel("$yf$")
    ax.set_ylabel("Loss")
    ax.legend(fontsize=8.5)
    fig.tight_layout()
    savefig(fig, CH, "fig12-4", out_dir)


def fig_12_5(out_dir=None):
    """Kernel logistic regression with the kernels of Figure 12.3 and lambda = 1/C = 1."""
    import matplotlib.pyplot as plt
    d = mixture_cached()
    X, y = d["X"], d["ypm"]
    fig, axes = plt.subplots(2, 1, figsize=(4.6, 7.6))
    res = {}
    for ax, (kind, kw, title) in zip(axes, [("poly", dict(degree=4), "Logistic regression: degree-4 polynomial"),
                                            ("rbf", dict(gamma=1.0), "Logistic regression: radial kernel")]):
        K = kernel(X, X, kind, **kw)
        a, b0 = kernel_logistic(K, y, 1.0)

        def f(Q, a=a, b0=b0, kind=kind, kw=kw):
            return kernel(Q, X, kind, **kw) @ a + b0
        tr = error_rate(np.sign(K @ a + b0), y)
        te = error_rate(np.sign(f(d["Xt"])), d["yt"])
        mixture_panel(ax, d, f, title=title, margins=False, prob_levels=[math.log(3), -math.log(3)],
                      text=err_text(tr, te, d["bayes_rate"]))
        res[kind] = dict(train=tr, test=te)
        print("  %s: training error %.3f, test error %.4f" % (kind, tr, te))
    fig.tight_layout()
    savefig(fig, CH, "fig12-5", out_dir)
    return res


GAMMAS_12_6 = (5.0, 1.0, 0.5, 0.1)


def test_error_curves(gammas=GAMMAS_12_6, Cs=None):
    """Test error of the radial-kernel SVM on the mixture data along the exact path, at the costs Cs."""
    d = mixture_cached()
    X, y = d["X"], d["ypm"]
    Cs = np.logspace(-1, 4, 101) if Cs is None else Cs
    out = {}
    for gm in gammas:
        K = kernel(X, X, "rbf", gamma=gm)
        Kt = kernel(d["Xt"], X, "rbf", gamma=gm)
        P = svm_path(K, y, lam_min=1e-4)
        errs = []
        for C in Cs:
            a, a0 = path_at(P, 1.0 / C)
            errs.append(error_rate(np.sign(Kt @ (a * y) + a0), d["yt"]))
        out[gm] = np.array(errs)
    return Cs, out


def fig_12_6(out_dir=None):
    """Test error against C for the radial-kernel SVM, gamma = 5, 1, 0.5, 0.1."""
    import matplotlib.pyplot as plt
    d = mixture_cached()
    Cs, errs = test_error_curves()
    fig, axes = plt.subplots(1, 4, figsize=(10.0, 3.0), sharey=True)
    for ax, gm in zip(axes, GAMMAS_12_6):
        ax.plot(Cs, errs[gm], ".", color=ORANGE, ms=3.5)
        ax.axhline(d["bayes_rate"], color=PURPLE, ls="--", lw=1)
        ax.set_xscale("log")
        ax.set_title(r"$\gamma = %g$" % gm)
        ax.set_xlabel("C")
        k = int(np.argmin(errs[gm]))
        print("  gamma = %g: test error %.4f at C = 0.1, minimum %.4f at C = %.3g, %.4f at C = 10^4" % (gm, errs[gm][0], errs[gm][k], Cs[k], errs[gm][-1]))
    axes[0].set_ylabel("Test error")
    axes[0].set_ylim(0.19, 0.36)
    fig.suptitle("Test error curves: SVM with radial kernel", fontsize=10.5)
    fig.tight_layout()
    savefig(fig, CH, "fig12-6", out_dir)
    return Cs, errs


def toy_path_data():
    """Twelve points for Figure 12.7: 1-6 are the class -1 (blue), 7-12 the class +1 (orange)."""
    rng = np.random.default_rng(12)
    Xm = rng.normal(size=(6, 2)) * [0.75, 0.5] + [0.6, -0.45]
    Xp = rng.normal(size=(6, 2)) * [0.75, 0.5] + [0.35, 0.75]
    return np.vstack([Xm, Xp]), np.r_[-np.ones(6), np.ones(6)]


def fig_12_7(out_dir=None, lam_show=1.0):
    """The SVM path on twelve points: the fit at lambda = 1 and the piecewise-linear a_i(lambda)."""
    import matplotlib.pyplot as plt
    X, y = toy_path_data()
    K = kernel(X, X, "linear")
    P = svm_path(K, y, lam_min=1e-3)
    a, a0 = path_at(P, lam_show)
    beta = (a * y) @ X / lam_show
    b0 = a0 / lam_show
    f = X @ beta + b0
    fig, (ax, ax2) = plt.subplots(1, 2, figsize=(9.0, 4.4), gridspec_kw=dict(width_ratios=[1.6, 1]))
    xs = np.array([X[:, 0].min() - 0.4, X[:, 0].max() + 0.4])
    for lev, ls in ((0, "-"), (1, "--"), (-1, "--")):
        ax.plot(xs, (lev - b0 - beta[0] * xs) / beta[1], ls, color="black" if lev == 0 else GREY, lw=1.1)
    elbow = np.abs(y * f - 1) < 1e-8
    for i in range(12):
        col = MIX_BLUE if y[i] < 0 else MIX_ORANGE
        ax.scatter(*X[i], s=60 if elbow[i] else 40, marker="s" if elbow[i] else "o", color=col, edgecolors="black", linewidths=0.5, zorder=3)
        ax.text(X[i, 0] + 0.04, X[i, 1] - 0.13, str(i + 1), fontsize=8.5)
    xm = xs[1] - 0.25
    ax.text(xm, (1 - b0 - beta[0] * xm) / beta[1] + 0.06, "$f(x)=+1$", fontsize=9, ha="right")
    ax.text(xm, (-b0 - beta[0] * xm) / beta[1] + 0.06, "$f(x)=0$", fontsize=9, ha="right")
    ax.text(xm, (-1 - b0 - beta[0] * xm) / beta[1] + 0.06, "$f(x)=-1$", fontsize=9, ha="right")
    ax.set_title(r"$\lambda = %g$: margin $1/\|\beta\| = %.3f$" % (lam_show, 1 / np.linalg.norm(beta)))
    ax.set_xlim(*xs)
    groups = dict(R=np.flatnonzero(y * f > 1 + 1e-9) + 1, E=np.flatnonzero(elbow) + 1, L=np.flatnonzero(y * f < 1 - 1e-9) + 1)
    labels = {}
    for i in range(12):
        col = MIX_BLUE if y[i] < 0 else MIX_ORANGE
        ax2.plot(P["alpha"][:, i], P["lam"], color=col, lw=1.0)
        # label each profile where it first leaves alpha = 1 (points leaving together share a label)
        k = next((k for k in range(len(P["lam"])) if P["alpha"][k, i] < 1 - 1e-9), None)
        lab_l = round(float(P["lam"][k - 1] if k is not None else P["lam"][-1]), 1)
        labels.setdefault(lab_l, []).append(str(i + 1))
    for lab_l, names in labels.items():
        ax2.text(1.015, lab_l, ",".join(names), color="black", fontsize=7.5, va="center")
    ax2.axhline(lam_show, color="black", ls="--", lw=0.9)
    ax2.set_xlabel(r"$\alpha_i(\lambda)$")
    ax2.set_ylabel(r"$\lambda$")
    ax2.set_ylim(0, P["lam"][0] * 1.05)
    ax2.set_xlim(-0.03, 1.16)
    fig.tight_layout()
    savefig(fig, CH, "fig12-7", out_dir)
    print("  lambda_0 = %.3f, %d breakpoints; at lambda = %g: margin 1/||beta|| = %.3f, outside %s, on the margin %s, inside %s"
          % (P["lam"][0], len(P["lam"]), lam_show, 1 / np.linalg.norm(beta), list(groups["R"]), list(groups["E"]), list(groups["L"])))
    return P, groups


# =========================================================================== bases for FDA
def ns_basis(x, knots):
    """Natural cubic spline basis with the given knots (truncated-power form (5.4)-(5.5)), without the
    constant: N_1 = x, N_{k+1} = d_k - d_{K-1}, d_k = ((x - xi_k)^3_+ - (x - xi_K)^3_+) / (xi_K - xi_k).
    Returns len(knots) - 1 columns."""
    x = np.asarray(x, float)
    k = np.asarray(knots, float)
    K = len(k)

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


def additive_ns_knots(X, df):
    """Knots for an additive natural-spline expansion with df columns per input: df + 1 knots at
    equally spaced quantiles of each training column (boundary knots at the extremes)."""
    qs = np.linspace(0, 1, df + 1)
    return [np.quantile(X[:, j], qs) for j in range(X.shape[1])]


def additive_ns_basis(X, knots, scale=None):
    """The additive natural-spline basis h(x) (no constant), columns scaled to unit training s.d.
    when scale is given (a vector of column scales)."""
    H = np.column_stack([ns_basis(X[:, j], kn) for j, kn in enumerate(knots)])
    return H if scale is None else H / scale


def poly_basis(X, degree=2):
    """All monomials of total degree 1..degree (no constant)."""
    from itertools import combinations_with_replacement
    cols = []
    for d in range(1, degree + 1):
        for c in combinations_with_replacement(range(X.shape[1]), d):
            cols.append(np.prod(X[:, list(c)], axis=1))
    return np.column_stack(cols)


# =========================================================================== MARS (Chapter 9), multi-response
class MARS:
    """A compact multivariate adaptive regression spline fit (Friedman 1991) for several responses at
    once, used as the regression method inside FDA (Section 12.5). Forward pass: add the reflected
    pair B_m(x)(x_v - t)_+, B_m(x)(t - x_v)_+ that most reduces the residual sum of squares summed over
    the responses, with knots t at n_knots quantiles of each input and interaction order at most
    `degree`; backward pass: delete terms one at a time and keep the subset with the smallest GCV,
    RSS / (1 - C(M)/N)^2 with C(M) = M + penalty (M - 1) / 2."""

    def __init__(self, max_terms=21, degree=1, n_knots=20, penalty=None):
        self.max_terms, self.degree, self.n_knots = max_terms, degree, n_knots
        self.penalty = (2.0 if degree == 1 else 3.0) if penalty is None else penalty

    def _col(self, X, term):
        b = np.ones(len(X))
        for v, t, s in term:
            b = b * np.maximum(s * (X[:, v] - t), 0.0)
        return b

    def basis(self, X, terms=None):
        terms = self.terms if terms is None else terms
        return np.column_stack([self._col(X, t) for t in terms])

    def fit(self, X, Y):
        X = np.asarray(X, float)
        Y = np.asarray(Y, float).reshape(len(X), -1)
        N, p = X.shape
        knots = [np.unique(np.quantile(X[:, v], np.linspace(0, 1, self.n_knots + 2)[1:-1])) for v in range(p)]
        terms = [()]
        Bcols = [np.ones(N)]
        Q = np.ones((N, 1)) / math.sqrt(N)
        R = Y - Q @ (Q.T @ Y)
        while len(terms) + 2 <= self.max_terms:
            best = (0.0, None)
            for m, term in enumerate(terms):
                if len(term) >= self.degree:
                    continue
                used = {v for v, _, _ in term}
                for v in range(p):
                    if v in used:
                        continue
                    kn = knots[v]
                    C1 = Bcols[m][:, None] * np.maximum(X[:, v][:, None] - kn[None, :], 0)
                    C2 = Bcols[m][:, None] * np.maximum(kn[None, :] - X[:, v][:, None], 0)
                    C1 -= Q @ (Q.T @ C1)
                    C2 -= Q @ (Q.T @ C2)
                    a = (C1 * C1).sum(0)
                    c = (C2 * C2).sum(0)
                    b = (C1 * C2).sum(0)
                    r1 = C1.T @ R
                    r2 = C2.T @ R
                    det = a * c - b * b
                    tiny = 1e-10 * (a + c + 1e-300) ** 2
                    ok = det > tiny
                    red = np.zeros(len(kn))
                    # two-column projection where the pair is well conditioned
                    red[ok] = ((c[ok, None] * r1[ok] ** 2 - 2 * b[ok, None] * r1[ok] * r2[ok] + a[ok, None] * r2[ok] ** 2) / det[ok, None]).sum(1)
                    # otherwise one column only (e.g. a knot at the edge of the parent's support)
                    one = ~ok
                    if one.any():
                        s1 = np.where(a[one] > 1e-10, (r1[one] ** 2).sum(1) / np.maximum(a[one], 1e-300), 0)
                        s2 = np.where(c[one] > 1e-10, (r2[one] ** 2).sum(1) / np.maximum(c[one], 1e-300), 0)
                        red[one] = np.maximum(s1, s2)
                    j = int(np.argmax(red))
                    if red[j] > best[0] * (1 + 1e-12):
                        best = (red[j], (m, v, kn[j]))
            if best[1] is None or best[0] < 1e-10 * (Y ** 2).sum():
                break
            m, v, t = best[1]
            for s in (+1, -1):
                term = terms[m] + ((v, t, s),)
                col = self._col(X, term)
                q = col - Q @ (Q.T @ col)
                nq = np.linalg.norm(q)
                if nq < 1e-8 * max(np.linalg.norm(col), 1e-300):
                    continue
                terms.append(term)
                Bcols.append(col)
                Q = np.column_stack([Q, q / nq])
            R = Y - Q @ (Q.T @ Y)
        self.forward_terms = list(terms)
        # backward deletion with GCV
        B = np.column_stack(Bcols)
        active = list(range(len(terms)))

        def rss(cols):
            coef = np.linalg.lstsq(B[:, cols], Y, rcond=None)[0]
            return float(((Y - B[:, cols] @ coef) ** 2).sum())

        def gcv(cols, r):
            M = len(cols)
            CM = M + self.penalty * (M - 1) / 2.0
            return r / (N * (1 - CM / N) ** 2) if CM < N else np.inf
        r = rss(active)
        best_set, best_gcv = list(active), gcv(active, r)
        while len(active) > 1:
            trials = [(rss([c for c in active if c != k]), k) for k in active if k != 0]
            r, k = min(trials)
            active = [c for c in active if c != k]
            g = gcv(active, r)
            if g < best_gcv:
                best_gcv, best_set = g, list(active)
        self.terms = [terms[k] for k in best_set]
        self.gcv = best_gcv
        Bs = self.basis(X)
        self.coef = np.linalg.lstsq(Bs, Y, rcond=None)[0]
        return self

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


# =========================================================================== FDA by optimal scoring (Section 12.5.1)
def indicator(g, K):
    Y = np.zeros((len(g), K))
    Y[np.arange(len(g)), g] = 1.0
    return Y


class OptimalScoring:
    """Flexible / penalised discriminant analysis by optimal scoring (Sections 12.5-12.6).

    The regression is linear in a basis H (N x M, without the constant; the constant is added and not
    penalised): coefficients (H1^T H1 + lam Omega1)^{-1} H1^T Z, with Z the N x R indicator matrix (or
    the blurred responses of MDA, (12.63)). The optimal scores are the eigenvectors of
    Z^T Zhat / N with respect to D_pi = diag(Z^T 1) / N, normalised Theta^T D_pi Theta = I; the first
    (constant score, eigenvalue 1) is dropped. The discriminant functions are eta_l(x) = h1(x)^T B theta_l,
    with eigenvalues alpha_l^2 = 1 - r_l^2, r_l^2 the (penalised) mean squared residual of the l-th
    optimally scored fit, and the weights w_l = 1 / (r_l^2 (1 - r_l^2)) of (12.55)."""

    def __init__(self, lam=0.0, Omega=None):
        self.lam, self.Omega = lam, Omega

    def fit(self, H, Z):
        N, M = H.shape
        H1 = np.column_stack([np.ones(N), H])
        A = H1.T @ H1
        if self.Omega is not None and self.lam > 0:
            A[1:, 1:] += self.lam * self.Omega
        self.B = linalg.solve(A, H1.T @ Z, assume_a="pos")
        S = Z.T @ (H1 @ self.B) / N
        S = 0.5 * (S + S.T)
        d = Z.sum(0) / N
        self.prior = d
        dm = 1.0 / np.sqrt(d)
        ev, V = np.linalg.eigh(dm[:, None] * S * dm[None, :])
        order = np.argsort(ev)[::-1]
        ev, V = ev[order], V[:, order]
        Theta = dm[:, None] * V
        # the leading eigenvector is the constant score (eigenvalue 1); drop it
        self.alpha2_all = ev
        # keep the nontrivial functions: eigenvalue strictly between 0 and 1 (at most min(R - 1, M))
        keep = (ev[1:] > 1e-10) & (ev[1:] < 1 - 1e-12)
        self.Theta = Theta[:, 1:][:, keep]
        self.alpha2 = ev[1:][keep]
        self.r2 = 1.0 - self.alpha2
        self.w = 1.0 / (self.r2 * (1.0 - self.r2))
        E = H1 @ self.B @ self.Theta
        self.centroids = (Z.T @ E) / Z.sum(0)[:, None]
        return self

    def eta(self, H):
        return np.column_stack([np.ones(len(H)), H]) @ self.B @ self.Theta

    def dist(self, H, L=None):
        """Squared distances (12.54) to each centroid, using the first L discriminant functions."""
        L = self.Theta.shape[1] if L is None else min(L, self.Theta.shape[1])
        E = self.eta(H)[:, :L]
        w = self.w[:L]
        return (((E[:, None, :] - self.centroids[None, :, :L]) ** 2) * w).sum(-1)

    def predict(self, H, L=None, priors=True):
        D = self.dist(H, L)
        if priors:
            D = D - 2 * np.log(self.prior)[None, :]
        return np.argmin(D, axis=1)


def fda(H, g, K, lam=0.0, Omega=None):
    return OptimalScoring(lam, Omega).fit(H, indicator(g, K))


# =========================================================================== LDA and QDA (Chapter 4), for comparison
class LDA:
    """Gaussian classes with a common covariance; the maximum-likelihood within-class covariance
    (divisor N) by default, so that it matches optimal scoring exactly."""

    def __init__(self, divisor="N"):
        self.divisor = divisor

    def fit(self, X, g, K=None):
        K = int(g.max()) + 1 if K is None else K
        N, p = X.shape
        self.mu = np.array([X[g == k].mean(0) for k in range(K)])
        self.prior = np.array([(g == k).mean() for k in range(K)])
        R = X - self.mu[g]
        self.W = R.T @ R / (N if self.divisor == "N" else N - K)
        Wi = np.linalg.inv(self.W)
        self.Wi = Wi
        # discriminant coordinates: B v = l W v, normalised v^T W v = 1
        mbar = self.prior @ self.mu
        Bm = (self.mu - mbar).T @ (self.prior[:, None] * (self.mu - mbar))
        ev, V = linalg.eigh(Bm, self.W)
        o = np.argsort(ev)[::-1]
        self.eig, self.V = ev[o], V[:, o]
        return self

    def dist(self, X):
        D = X[:, None, :] - self.mu[None, :, :]
        return np.einsum("nkp,pq,nkq->nk", D, self.Wi, D)

    def predict(self, X):
        return np.argmin(self.dist(X) - 2 * np.log(self.prior)[None, :], axis=1)

    def coords(self, X, L=2):
        return X @ self.V[:, :L]


class QDA:
    def fit(self, X, g, K=None, reg=0.0):
        K = int(g.max()) + 1 if K is None else K
        self.mu, self.S, self.prior = [], [], []
        for k in range(K):
            Xk = X[g == k]
            self.mu.append(Xk.mean(0))
            S = np.cov(Xk.T, bias=False) + reg * np.eye(X.shape[1])
            self.S.append(S)
            self.prior.append(len(Xk) / len(X))
        return self

    def predict(self, X):
        sc = np.column_stack([common.gauss_logpdf(X, m, S) + math.log(p) for m, S, p in zip(self.mu, self.S, self.prior)])
        return np.argmax(sc, axis=1)


# =========================================================================== MDA (Section 12.7)
def kmeans_js(X, R, seed, starts=5, iters=100):
    """k-means with R centres and `starts` random starts, the starting centres drawn as distinct
    training points with the demos' generator (DK.rng, mirrored by ch02.JSRandom), so that the browser
    demo gets the same initial partition. Returns the labels of the best start (smallest within SS)."""
    rng = ch02.JSRandom(seed)
    N = len(X)
    best = (np.inf, None)
    for _ in range(starts):
        idx = []
        while len(idx) < R:
            j = int(math.floor(rng.u() * N))
            if j not in idx:
                idx.append(j)
        C = X[idx].copy()
        lab = None
        for _ in range(iters):
            D = ((X[:, None, :] - C[None, :, :]) ** 2).sum(-1)
            new = np.argmin(D, axis=1)
            if lab is not None and np.array_equal(new, lab):
                break
            lab = new
            for r in range(R):
                if (lab == r).any():
                    C[r] = X[lab == r].mean(0)
        ss = float(((X - C[lab]) ** 2).sum())
        if ss < best[0] - 1e-12:
            best = (ss, lab.copy())
    return best[1]


def mda_init(X, g, Rk, seed=1, starts=5):
    """Initial responsibilities: a separate k-means partition within each class (0/1 weights)."""
    K = len(Rk)
    offs = np.r_[0, np.cumsum(Rk)]
    W = np.zeros((len(X), offs[-1]))
    for k in range(K):
        ik = np.flatnonzero(g == k)
        lab = kmeans_js(X[ik], Rk[k], seed + 101 * k, starts) if Rk[k] > 1 else np.zeros(len(ik), int)
        W[ik, offs[k] + lab] = 1.0
    return W


class MDAGauss:
    """Mixture discriminant analysis with Gaussian subclasses sharing one covariance, fitted by EM
    (12.59)-(12.62) directly: the M-step is a weighted LDA (subclass means, pooled covariance,
    mixing proportions); the E-step apportions each observation among its own class's subclasses."""

    def __init__(self, Rk, seed=1, starts=5, iters=100, tol=1e-10):
        self.Rk, self.seed, self.starts, self.iters, self.tol = list(Rk), seed, starts, iters, tol

    def mstep(self, X, g, W):
        N = len(X)
        nk = W.sum(0)
        self.mu = (W.T @ X) / nk[:, None]
        S = np.zeros((X.shape[1], X.shape[1]))
        for r in range(W.shape[1]):
            D = X - self.mu[r]
            S += (W[:, r, None] * D).T @ D
        self.Sigma = S / N
        self.pi = nk / np.array([np.sum(g == self.cls[r]) for r in range(W.shape[1])])
        self.Pi = np.array([np.mean(g == k) for k in range(len(self.Rk))])

    def logdens(self, X):
        """log pi_kr + log phi(x; mu_kr, Sigma) for every subclass (columns)."""
        return np.column_stack([math.log(max(self.pi[r], 1e-300)) + common.gauss_logpdf(X, self.mu[r], self.Sigma) for r in range(len(self.mu))])

    def fit(self, X, g, W0=None):
        K = len(self.Rk)
        self.cls = np.repeat(np.arange(K), self.Rk)
        W = mda_init(X, g, self.Rk, self.seed, self.starts) if W0 is None else W0
        self.loglik = []
        own = self.cls[None, :] == g[:, None]
        for it in range(self.iters):
            self.mstep(X, g, W)
            Ld = self.logdens(X)
            Ld = np.where(own, Ld, -np.inf)
            lse = common.logsumexp(Ld, axis=1)
            ll = float(lse.sum() + np.log(self.Pi[g]).sum())
            self.loglik.append(ll)
            W = np.exp(Ld - lse[:, None])
            if it > 0 and abs(self.loglik[-1] - self.loglik[-2]) < self.tol * abs(ll):
                break
        self.mstep(X, g, W)
        self.W = W
        return self

    def class_scores(self, X):
        Ld = self.logdens(X)
        K = len(self.Rk)
        return np.column_stack([common.logsumexp(Ld[:, self.cls == k], axis=1) + math.log(self.Pi[k]) for k in range(K)])

    def predict(self, X):
        return np.argmax(self.class_scores(X), axis=1)

    def prob(self, X):
        s = self.class_scores(X)
        return np.exp(s - common.logsumexp(s, axis=1)[:, None])


class MDAScoring:
    """MDA with the M-step done by (penalised) optimal scoring on the blurred response matrix Z
    (12.63): Zhat = S Z, Z^T Zhat = Theta D Theta^T, then update the subclass proportions. The E-step
    uses the distances (12.54) in the discriminant space (first L functions). With the plain linear
    regression and full rank this is exactly MDAGauss."""

    def __init__(self, Rk, lam=0.0, Omega=None, L=None, seed=1, starts=5, iters=100, tol=1e-10):
        self.Rk, self.lam, self.Omega, self.L = list(Rk), lam, Omega, L
        self.seed, self.starts, self.iters, self.tol = seed, starts, iters, tol

    def _scores(self, H):
        D = self.os.dist(H, self.L)
        return -0.5 * D + np.log(np.maximum(self.pi, 1e-300))[None, :]

    def fit(self, H, g, W0=None, X_for_init=None):
        K = len(self.Rk)
        self.cls = np.repeat(np.arange(K), self.Rk)
        W = mda_init(H if X_for_init is None else X_for_init, g, self.Rk, self.seed, self.starts) if W0 is None else W0
        own = self.cls[None, :] == g[:, None]
        self.Pi = np.array([np.mean(g == k) for k in range(K)])
        prev = None
        for it in range(self.iters):
            self.os = OptimalScoring(self.lam, self.Omega).fit(H, W)
            nk = W.sum(0)
            self.pi = nk / np.array([np.sum(g == c) for c in self.cls])
            Sc = np.where(own, self._scores(H), -np.inf)
            lse = common.logsumexp(Sc, axis=1)
            Wn = np.exp(Sc - lse[:, None])
            ch = np.abs(Wn - W).max()
            W = Wn
            if ch < 1e-9:
                break
        self.os = OptimalScoring(self.lam, self.Omega).fit(H, W)
        self.pi = W.sum(0) / np.array([np.sum(g == c) for c in self.cls])
        self.W = W
        return self

    def class_scores(self, H):
        Sc = self._scores(H)
        K = len(self.Rk)
        return np.column_stack([common.logsumexp(Sc[:, self.cls == k], axis=1) + math.log(self.Pi[k]) for k in range(K)])

    def predict(self, H):
        return np.argmax(self.class_scores(H), axis=1)


# =========================================================================== penalty matrices
def diff_penalty(p, order=2):
    """Omega = D^T D with D the order-th difference matrix: penalises roughness of a coefficient
    vector indexed by 1..p (Section 12.6; the waveform index j)."""
    D = np.diff(np.eye(p), n=order, axis=0)
    return D.T @ D


def image_penalty(n=16, order=2):
    """Roughness of a coefficient image on an n x n grid (pixels stored row by row): the sum of squared
    order-th differences along the rows and along the columns, Omega = A (x) I + I (x) A, A = D^T D."""
    D = np.diff(np.eye(n), n=order, axis=0)
    A = D.T @ D
    I = np.eye(n)
    return np.kron(A, I) + np.kron(I, A)


def ridge_df(X, Omega, lam):
    """Effective degrees of freedom tr[Xc (Xc^T Xc + lam Omega)^{-1} Xc^T] (centred X, intercept excluded)."""
    Xc = X - X.mean(0)
    A = Xc.T @ Xc
    return float(np.trace(linalg.solve(A + lam * Omega, A, assume_a="pos")))


def lam_for_df(X, Omega, df, lo=1e-6, hi=1e9):
    """The penalty giving the requested effective degrees of freedom (bisection on log lambda)."""
    a, b = math.log(lo), math.log(hi)
    for _ in range(80):
        m = 0.5 * (a + b)
        if ridge_df(X, Omega, math.exp(m)) > df:
            a = m
        else:
            b = m
    return math.exp(0.5 * (a + b))


# =========================================================================== Figures 12.8-12.10
def fig_12_8(out_dir=None, eps=1.0, c=1.345):
    """The epsilon-insensitive loss of support vector regression and Huber's loss."""
    import matplotlib.pyplot as plt
    r = np.linspace(-4, 4, 801)
    fig, axes = plt.subplots(1, 2, figsize=(8.4, 3.4))
    axes[0].plot(r, eps_insensitive(r, eps), color=RED)
    axes[0].set_title(r"$V_\epsilon(r)$, $\epsilon = %g$" % eps)
    axes[1].plot(r, huber(r, c), color=BLUE)
    axes[1].plot(r, 0.5 * r * r, color=GREY, ls=":", lw=1)
    axes[1].set_title(r"$V_H(r)$, $c = %g$" % c)
    for ax, t in zip(axes, (eps, c)):
        for v in (-t, t):
            ax.axvline(v, color=GREY, ls="--", lw=0.8)
        ax.set_xlabel("$r$")
        ax.set_ylim(-0.2, 4.2)
    axes[0].set_xticks([-4, -2, -eps, 0, eps, 2, 4])
    axes[0].set_xticklabels(["-4", "-2", r"$-\epsilon$", "0", r"$\epsilon$", "2", "4"])
    axes[1].set_xticks([-4, -2, -c, 0, c, 2, 4])
    axes[1].set_xticklabels(["-4", "-2", "$-c$", "0", "$c$", "2", "4"])
    fig.tight_layout()
    savefig(fig, CH, "fig12-8", out_dir)


def two_gaussians(n=50, c=9 / 4, seed=129):
    """n points from N(0, I) (class 0) and n from N(0, c I) (class 1) in the plane (Figure 12.9)."""
    rng = np.random.default_rng(seed)
    X = np.vstack([rng.normal(size=(n, 2)), math.sqrt(c) * rng.normal(size=(n, 2))])
    return X, np.r_[np.zeros(n, int), np.ones(n, int)]


def bayes_radius(c, p=2):
    """Radius of the Bayes boundary between N(0, I) and N(0, c I) with equal priors:
    ||x||^2 = p c log c / (c - 1)."""
    return math.sqrt(p * c * math.log(c) / (c - 1))


def fig_12_9(out_dir=None):
    """FDA with degree-2 polynomial regression on N(0, I) against N(0, 9/4 I)."""
    import matplotlib.pyplot as plt
    X, g = two_gaussians()
    H = poly_basis(X, 2)
    f = fda(H, g, 2)
    gx = np.linspace(-4.2, 4.2, 400)
    XX, YY = np.meshgrid(gx, gx)
    P = np.column_stack([XX.ravel(), YY.ravel()])
    D = f.dist(poly_basis(P, 2)) - 2 * np.log(f.prior)[None, :]
    Z = (D[:, 0] - D[:, 1]).reshape(XX.shape)
    fig, ax = plt.subplots(figsize=(4.6, 4.6))
    ax.scatter(X[g == 0, 0], X[g == 0, 1], s=16, facecolors="none", edgecolors=MIX_ORANGE)
    ax.scatter(X[g == 1, 0], X[g == 1, 1], s=16, facecolors="none", edgecolors=MIX_BLUE)
    ax.contour(XX, YY, Z, levels=[0.0], colors="black", linewidths=1.4)
    rb = bayes_radius(9 / 4)
    t = np.linspace(0, 2 * np.pi, 400)
    ax.plot(rb * np.cos(t), rb * np.sin(t), color=PURPLE, ls="--", lw=1.3)
    ax.set_xlim(-4.2, 4.2)
    ax.set_ylim(-4.2, 4.2)
    ax.set_aspect("equal")
    fig.tight_layout()
    savefig(fig, CH, "fig12-9", out_dir)
    tr = error_rate(f.predict(H), g)
    # the boundary in the enlarged space is linear: LDA on (x, x^2, x1 x2) gives the same rule
    lda = LDA().fit(H, g)
    agree = float(np.mean(lda.predict(poly_basis(P, 2)) == np.argmin(D, axis=1)))
    print("  Bayes radius %.4f (the book's formula p c log c / (2(c - 1)) gives %.4f); FDA training error %.3f; "
          "agreement with LDA on the quadratic features %.4f" % (rb, 2 * (9 / 4) * math.log(9 / 4) / (2 * (9 / 4 - 1)), tr, agree))
    return dict(radius=rb, train=tr, agree=agree)


VOWEL_COLOURS = ["#000000", "#d62728", "#2ca02c", "#1f3fbf", "#17becf", "#c2185b", "#c9b200",
                 "#7f7f7f", "#ff7f0e", "#7b1fa2", "#8c4a1f"]
VOWEL_DF = 4


def vowel_fda(df=VOWEL_DF):
    """FDA on the vowel data with additive natural cubic splines (df columns per input, unpenalised),
    our stand-in for the adaptive additive splines (BRUTO) of the book."""
    Xtr, gtr, Xte, gte = vowel()
    kn = additive_ns_knots(Xtr, df)
    H = additive_ns_basis(Xtr, kn)
    sc = H.std(0)
    H, Ht = H / sc, additive_ns_basis(Xte, kn) / sc
    return fda(H, gtr, 11), H, Ht, kn, sc


def fig_12_10(out_dir=None):
    """Vowel training data: the first two LDA canonical variates and the first two FDA functions."""
    import matplotlib.pyplot as plt
    Xtr, gtr, Xte, gte = vowel()
    lda = fda(Xtr, gtr, 11)          # optimal scoring with linear regression = LDA
    f, H, Ht, kn, sc = vowel_fda()
    fig, axes = plt.subplots(1, 2, figsize=(9.6, 4.6))
    for ax, (Z, C, title) in zip(axes, [(lda.eta(Xtr), lda.centroids, "Linear discriminant analysis"),
                                        (f.eta(H), f.centroids, "Flexible discriminant analysis: additive splines")]):
        # scale each coordinate by sqrt(w_l) so that Euclidean distance is the discriminant distance
        w = np.sqrt((lda if C is lda.centroids else f).w[:2])
        Z2, C2 = Z[:, :2] * w, C[:, :2] * w
        for k in range(11):
            ax.scatter(Z2[gtr == k, 0], Z2[gtr == k, 1], s=9, facecolors="none", edgecolors=VOWEL_COLOURS[k], lw=0.7)
        for k in range(11):
            ax.scatter(C2[k, 0], C2[k, 1], s=70, color=VOWEL_COLOURS[k], edgecolors="white", lw=1.2, zorder=5)
        ax.set_xlabel("Coordinate 1 for training data")
        ax.set_ylabel("Coordinate 2 for training data")
        ax.set_title(title)
    fig.tight_layout()
    savefig(fig, CH, "fig12-10", out_dir)


def vowel_table(mars_cache=True):
    """Table 12.3: training and test error rates on the vowel data for the methods we fit."""
    Xtr, gtr, Xte, gte = vowel()
    rows = []
    lda = LDA().fit(Xtr, gtr)
    rows.append(("LDA", error_rate(lda.predict(Xtr), gtr), error_rate(lda.predict(Xte), gte)))
    q = QDA().fit(Xtr, gtr)
    rows.append(("QDA", error_rate(q.predict(Xtr), gtr), error_rate(q.predict(Xte), gte)))
    f, H, Ht, kn, sc = vowel_fda()
    rows.append(("FDA/additive splines (df %d)" % VOWEL_DF, error_rate(f.predict(H), gtr), error_rate(f.predict(Ht), gte)))
    best = min(range(1, 11), key=lambda L: error_rate(f.predict(Ht, L), gte))
    rows.append(("  best reduced dimension (=%d)" % best, error_rate(f.predict(H, best), gtr), error_rate(f.predict(Ht, best), gte)))
    for deg, mt in ((1, 41), (2, 61)):
        ma = MARS(max_terms=mt, degree=deg, n_knots=20).fit(Xtr, indicator(gtr, 11))
        Hm, Hmt = ma.basis(Xtr)[:, 1:], ma.basis(Xte)[:, 1:]
        fm = fda(Hm, gtr, 11)
        rows.append(("FDA/MARS (degree = %d)" % deg, error_rate(fm.predict(Hm), gtr), error_rate(fm.predict(Hmt), gte)))
        best = min(range(1, fm.Theta.shape[1] + 1), key=lambda L: error_rate(fm.predict(Hmt, L), gte))
        rows.append(("  best reduced dimension (=%d)" % best, error_rate(fm.predict(Hm, best), gtr), error_rate(fm.predict(Hmt, best), gte)))
    for r in rows:
        print("    %-34s %.3f  %.3f" % r)
    return rows


# =========================================================================== zip digits: PDA (Figures 12.11-12.12)
PDA_ZIP_LAM = 3000.0


def zip_pda(lam=PDA_ZIP_LAM):
    """LDA (lam = 0) and PDA (penalty lam * Omega, Omega the second-difference image roughness) on the
    zip-code digits, by optimal scoring with the 256 pixels as the basis."""
    Xtr, gtr, Xte, gte = zip_digits()
    Om = image_penalty(16, 2)
    lda = fda(Xtr, gtr, 10)
    pda = fda(Xtr, gtr, 10, lam=lam, Omega=Om)
    return lda, pda, (Xtr, gtr, Xte, gte)


def zip_pda_errors(lams=(0.0, 30.0, 100.0, 300.0, 1000.0, 3000.0, 10000.0, 30000.0)):
    Xtr, gtr, Xte, gte = zip_digits()
    Om = image_penalty(16, 2)
    out = []
    for lam in lams:
        f = fda(Xtr, gtr, 10, lam=lam, Omega=Om if lam > 0 else None)
        out.append((lam, error_rate(f.predict(Xtr), gtr), error_rate(f.predict(Xte), gte)))
    return out


def fig_12_11(out_dir=None):
    """The nine discriminant coefficient images of LDA and of PDA (smooth) for the zip-code digits."""
    import matplotlib.pyplot as plt
    lda, pda, (Xtr, gtr, Xte, gte) = zip_pda()
    fig, axes = plt.subplots(3, 6, figsize=(9.0, 4.9))
    for l in range(9):
        r, c = divmod(l, 3)
        for k, (f, nm) in enumerate(((lda, "LDA"), (pda, "PDA"))):
            beta = (f.B[1:] @ f.Theta[:, l]).reshape(16, 16)
            v = np.abs(beta).max()
            ax = axes[r, 2 * c + k]
            ax.imshow(beta, cmap="RdBu_r", vmin=-v, vmax=v)
            ax.set_xticks([])
            ax.set_yticks([])
            ax.set_title("%s: coefficient %d" % (nm, l + 1), fontsize=8)
    fig.tight_layout()
    savefig(fig, CH, "fig12-11", out_dir)
    e = [(error_rate(f.predict(Xtr), gtr), error_rate(f.predict(Xte), gte)) for f in (lda, pda)]
    print("  LDA training / test error %.4f / %.4f; PDA (lambda = %g) %.4f / %.4f" % (e[0] + (PDA_ZIP_LAM,) + e[1]))
    return e


def fig_12_12(out_dir=None):
    """The first two penalised canonical variates of the zip-code test data, with the class centroids."""
    import matplotlib.pyplot as plt
    lda, pda, (Xtr, gtr, Xte, gte) = zip_pda()
    E = pda.eta(Xte)[:, :2] * np.sqrt(pda.w[:2])
    C = pda.centroids[:, :2] * np.sqrt(pda.w[:2])
    cols = ["#000000", "#d62728", "#2ca02c", "#1f3fbf", "#17becf", "#c2185b", "#c9b200", "#7f7f7f", "#ff7f0e", "#7b1fa2"]
    fig, ax = plt.subplots(figsize=(5.8, 5.4))
    for k in range(10):
        ax.scatter(E[gte == k, 0], E[gte == k, 1], s=14, marker="$%d$" % k, color=cols[k], lw=0.3, alpha=0.75)
    for k in range(10):
        ax.scatter(C[k, 0], C[k, 1], s=260, facecolors="none", edgecolors="black", lw=1.6, zorder=5)
        ax.text(C[k, 0], C[k, 1], str(k), ha="center", va="center", fontsize=9, weight="bold", zorder=6)
    ax.set_xlabel("PDA: discriminant coordinate 1")
    ax.set_ylabel("PDA: discriminant coordinate 2")
    fig.tight_layout()
    savefig(fig, CH, "fig12-12", out_dir)


# =========================================================================== the waveform data (Section 12.7.1)
def waveform_h():
    """The three shifted triangles h1, h2, h3 on j = 1..21: h1(j) = max(6 - |j - 11|, 0),
    h2(j) = h1(j - 4), h3(j) = h1(j + 4)."""
    j = np.arange(1, 22)
    h1 = np.maximum(6 - np.abs(j - 11), 0.0)
    h2 = np.maximum(6 - np.abs(j - 4 - 11), 0.0)
    h3 = np.maximum(6 - np.abs(j + 4 - 11), 0.0)
    return h1, h2, h3


WAVE_PAIRS = ((0, 1), (0, 2), (1, 2))


def waveform_sample(n, rng, noise=True):
    """n draws from model (12.64), classes equally likely: class 1 mixes h1, h2; class 2 h1, h3;
    class 3 h2, h3, with weight U ~ U(0, 1), plus N(0, 1) noise at each j."""
    h = waveform_h()
    g = rng.integers(0, 3, n)
    U = rng.uniform(size=n)
    X = np.empty((n, 21))
    for i in range(n):
        a, b = WAVE_PAIRS[g[i]]
        X[i] = U[i] * h[a] + (1 - U[i]) * h[b]
    if noise:
        X += rng.normal(size=(n, 21))
    return X, g


def fig_12_14(out_dir=None, seed=14):
    """Examples of the three classes of waveforms before the noise is added."""
    import matplotlib.pyplot as plt
    rng = np.random.default_rng(seed)
    h = waveform_h()
    j = np.arange(1, 22)
    fig, axes = plt.subplots(1, 3, figsize=(9.4, 2.9), sharey=True)
    cols = (ORANGE, BLUE, GREEN)
    for k, ax in enumerate(axes):
        a, b = WAVE_PAIRS[k]
        for u in rng.uniform(size=5):
            ax.plot(j, u * h[a] + (1 - u) * h[b], color=cols[k], lw=1.0, marker="o", ms=2)
        ax.set_title("Class %d" % (k + 1))
        ax.set_xticks([1, 5, 11, 15, 21])
        ax.set_xlabel("$j$")
    axes[0].set_ylim(-0.3, 6.4)
    fig.tight_layout()
    savefig(fig, CH, "fig12-14", out_dir)


def waveform_methods(Xtr, gtr, Xte, gte, seed=0):
    """Error rates (train, test) of the methods of Table 12.4 on one waveform sample."""
    from sklearn.tree import DecisionTreeClassifier
    from sklearn.model_selection import cross_val_score
    out = {}
    lda = LDA().fit(Xtr, gtr, 3)
    out["LDA"] = (error_rate(lda.predict(Xtr), gtr), error_rate(lda.predict(Xte), gte))
    q = QDA().fit(Xtr, gtr, 3)
    out["QDA"] = (error_rate(q.predict(Xtr), gtr), error_rate(q.predict(Xte), gte))
    # CART: cost-complexity pruning chosen by 10-fold cross-validation
    path = DecisionTreeClassifier(random_state=seed).cost_complexity_pruning_path(Xtr, gtr)
    alphas = np.unique(path.ccp_alphas)[::max(1, len(path.ccp_alphas) // 25)]
    cv = [cross_val_score(DecisionTreeClassifier(random_state=seed, ccp_alpha=a), Xtr, gtr, cv=10).mean() for a in alphas]
    tree = DecisionTreeClassifier(random_state=seed, ccp_alpha=alphas[int(np.argmax(cv))]).fit(Xtr, gtr)
    out["CART"] = (error_rate(tree.predict(Xtr), gtr), error_rate(tree.predict(Xte), gte))
    for deg in (1, 2):
        ma = MARS(max_terms=21, degree=deg, n_knots=10).fit(Xtr, indicator(gtr, 3))
        f = fda(ma.basis(Xtr)[:, 1:], gtr, 3)
        out["FDA/MARS (degree = %d)" % deg] = (error_rate(f.predict(ma.basis(Xtr)[:, 1:]), gtr), error_rate(f.predict(ma.basis(Xte)[:, 1:]), gte))
    md = MDAGauss([3, 3, 3], seed=seed + 1).fit(Xtr, gtr)
    out["MDA (3 subclasses)"] = (error_rate(md.predict(Xtr), gtr), error_rate(md.predict(Xte), gte))
    Om = diff_penalty(21, 2)
    for df in (4, 8):
        lam = lam_for_df(Xtr, Om, float(df))
        mp = MDAScoring([3, 3, 3], lam=lam, Omega=Om, seed=seed + 1).fit(Xtr, gtr)
        out["MDA (3 subclasses, penalized %d df)" % df] = (error_rate(mp.predict(Xtr), gtr), error_rate(mp.predict(Xte), gte))
        pd_ = fda(Xtr, gtr, 3, lam=lam, Omega=Om)
        out["PDA (penalized %d df)" % df] = (error_rate(pd_.predict(Xtr), gtr), error_rate(pd_.predict(Xte), gte))
    return out


def waveform_table(nsim=10, ntr=300, nte=500, seed=2009):
    """Table 12.4: averages (standard errors) over nsim simulated training and test sets."""
    path = os.path.join(CACHE_DIR, "ch12_waveform_table.json")
    if os.path.exists(path):
        with open(path) as f:
            return json.load(f)
    rng = np.random.default_rng(seed)
    res = {}
    for s in range(nsim):
        Xtr, gtr = waveform_sample(ntr, rng)
        Xte, gte = waveform_sample(nte, rng)
        out = waveform_methods(Xtr, gtr, Xte, gte, seed=s)
        for k, v in out.items():
            res.setdefault(k, []).append(v)
    tab = {k: dict(train=float(np.mean([a for a, b in v])), train_se=float(np.std([a for a, b in v], ddof=1) / math.sqrt(nsim)),
                   test=float(np.mean([b for a, b in v])), test_se=float(np.std([b for a, b in v], ddof=1) / math.sqrt(nsim)))
           for k, v in res.items()}
    os.makedirs(CACHE_DIR, exist_ok=True)
    with open(path, "w") as f:
        json.dump(tab, f, indent=1)
    return tab


def fig_12_15(out_dir=None, seed=15):
    """Penalised MDA (3 subclasses per class, 4 df) on a waveform sample: test data in the first four
    canonical coordinates, with the subclass centres; prints Table 12.4."""
    import matplotlib.pyplot as plt
    rng = np.random.default_rng(seed)
    Xtr, gtr = waveform_sample(300, rng)
    Xte, gte = waveform_sample(500, rng)
    Om = diff_penalty(21, 2)
    lam = lam_for_df(Xtr, Om, 4.0)
    mp = MDAScoring([3, 3, 3], lam=lam, Omega=Om, seed=1).fit(Xtr, gtr)
    w = np.sqrt(mp.os.w)
    E = mp.os.eta(Xte) * w
    C = mp.os.centroids * w
    cols = (ORANGE, BLUE, GREEN)
    fig, axes = plt.subplots(1, 2, figsize=(9.4, 4.4))
    for ax, (i, j) in zip(axes, ((0, 1), (2, 3))):
        for k in range(3):
            ax.scatter(E[gte == k, i], E[gte == k, j], s=12, facecolors="none", edgecolors=cols[k], lw=0.8, label="Class %d" % (k + 1))
        for r in range(9):
            ax.scatter(C[r, i], C[r, j], s=80, color=cols[r // 3], edgecolors="black", lw=1.2, zorder=5)
        ax.set_xlabel("Discriminant var %d" % (i + 1))
        ax.set_ylabel("Discriminant var %d" % (j + 1))
        ax.set_title("3 subclasses per class, penalised 4 df")
    axes[0].legend(fontsize=8, loc="best")
    fig.tight_layout()
    savefig(fig, CH, "fig12-15", out_dir)
    a2 = mp.os.alpha2
    lam_ = a2 / (1 - a2)
    share = lam_ / lam_.sum()
    print("  this sample: penalised MDA training error %.3f, test error %.3f; between/within eigenvalues %s;"
          " share of the first two %.4f" % (error_rate(mp.predict(Xtr), gtr), error_rate(mp.predict(Xte), gte), np.round(lam_[:4], 3), share[:2].sum()))
    tab = waveform_table()
    print("  Table 12.4 (averages over 10 simulations; standard errors in parentheses):")
    for k, v in tab.items():
        print("    %-36s %.3f(%.3f)  %.3f(%.3f)" % (k, v["train"], v["train_se"], v["test"], v["test_se"]))
    return tab


# =========================================================================== mixture data: FDA/MARS and MDA (Figure 12.13)
MARS_MIX = dict(max_terms=21, degree=2, n_knots=20, penalty=2.0)


def fig_12_13(out_dir=None):
    """FDA with MARS (degree 2) and MDA with five subclasses per class on the mixture data."""
    import matplotlib.pyplot as plt
    d = mixture_cached()
    X, g, Xt = d["X"], d["y"], d["Xt"]
    gt = ((d["yt"] + 1) / 2).astype(int)
    ma = MARS(**MARS_MIX).fit(X, indicator(g, 2))
    f = fda(ma.basis(X)[:, 1:], g, 2)

    def score_fda(P):
        D = f.dist(ma.basis(P)[:, 1:]) - 2 * np.log(f.prior)[None, :]
        return 0.5 * (D[:, 0] - D[:, 1])
    md = MDAGauss([5, 5], seed=1).fit(X, g)

    def score_mda(P):
        s = md.class_scores(P)
        return s[:, 1] - s[:, 0]
    fig, axes = plt.subplots(2, 1, figsize=(4.6, 7.6))
    res = {}
    for ax, (sc, title, cen) in zip(axes, [(score_fda, "FDA / MARS, degree 2", None),
                                           (score_mda, "MDA, 5 subclasses per class", [(md.mu[:5], MIX_BLUE), (md.mu[5:], MIX_ORANGE)])]):
        tr = error_rate(sc(X) > 0, g)
        te = error_rate(sc(Xt) > 0, gt)
        mixture_panel(ax, d, sc, title=title, margins=False, centres=cen, text=err_text(tr, te, d["bayes_rate"]))
        res[title] = (tr, te)
        print("  %s: training error %.3f, test error %.4f" % (title, tr, te))
    print("  MARS kept %d basis functions" % len(ma.terms))
    fig.tight_layout()
    savefig(fig, CH, "fig12-13", out_dir)
    return res


# =========================================================================== skin of the orange (Table 12.2)
def orange_sample(n, rng, noise=0):
    """n points per class: class -1 four independent N(0, 1) features; class +1 the same conditioned
    on 9 <= sum X_j^2 <= 16 (by rejection); plus `noise` extra N(0, 1) features for both."""
    X1 = rng.normal(size=(n, 4))
    X2 = np.empty((0, 4))
    while len(X2) < n:
        Z = rng.normal(size=(4 * n, 4))
        r2 = (Z ** 2).sum(1)
        X2 = np.vstack([X2, Z[(r2 >= 9) & (r2 <= 16)]])
    X = np.vstack([X1, X2[:n]])
    if noise:
        X = np.column_stack([X, rng.normal(size=(2 * n, noise))])
    return X, np.r_[-np.ones(n), np.ones(n)]


def orange_bayes_error():
    """Bayes error: class -1 points that fall in the shell, P(9 <= chi^2_4 <= 16) / 2."""
    from scipy.stats import chi2
    return 0.5 * (chi2.cdf(16, 4) - chi2.cdf(9, 4))


ORANGE_CS = np.logspace(-3, 3, 13)


def orange_table(nsim=50, ntr=100, nte=500, seed=12):
    """Table 12.2: mean test error (standard error) over nsim simulations with and without six noise
    features. The SVMs use LIBSVM through scikit-learn (the solver was checked against our own on the
    mixture data) with the kernel (1 + <x, x'>)^d of (12.22), and C chosen to minimise the test error
    over a grid, as in the book; the additive model is least squares on natural splines with 4 df
    per input (in place of BRUTO), and MARS allows interactions of all orders."""
    path = os.path.join(CACHE_DIR, "ch12_orange_table.json")
    if os.path.exists(path):
        with open(path) as f:
            return json.load(f)
    from sklearn.svm import SVC as SKSVC
    rng = np.random.default_rng(seed)
    methods = ["SV classifier", "SVM/poly 2", "SVM/poly 5", "SVM/poly 10", "Additive splines (BRUTO stand-in)", "MARS"]
    res = {noise: {k: [] for k in methods} for noise in (0, 6)}
    for s in range(nsim):
        for noise in (0, 6):
            Xtr, ytr = orange_sample(ntr, rng, noise)
            Xte, yte = orange_sample(nte, rng, noise)
            for name, kw in zip(methods[:4], [dict(kernel="linear"), dict(kernel="poly", degree=2),
                                              dict(kernel="poly", degree=5), dict(kernel="poly", degree=10)]):
                errs = []
                for C in ORANGE_CS:
                    clf = SKSVC(C=C, gamma=1.0, coef0=1.0, max_iter=200000, **kw).fit(Xtr, ytr)
                    errs.append(error_rate(clf.predict(Xte), yte))
                res[noise][name].append(min(errs))
            kn = additive_ns_knots(Xtr, 4)
            H = additive_ns_basis(Xtr, kn)
            H1 = np.column_stack([np.ones(len(H)), H])
            b = np.linalg.lstsq(H1, ytr, rcond=None)[0]
            Ht = np.column_stack([np.ones(len(Xte)), additive_ns_basis(Xte, kn)])
            res[noise][methods[4]].append(error_rate(np.sign(Ht @ b), yte))
            ma = MARS(max_terms=21, degree=Xtr.shape[1], n_knots=10).fit(Xtr, ytr)
            res[noise][methods[5]].append(error_rate(np.sign(ma.predict(Xte)[:, 0]), yte))
    tab = {str(noise): {k: [float(np.mean(v)), float(np.std(v, ddof=1) / math.sqrt(len(v)))] for k, v in d.items()} for noise, d in res.items()}
    tab["bayes"] = orange_bayes_error()
    os.makedirs(CACHE_DIR, exist_ok=True)
    with open(path, "w") as f:
        json.dump(tab, f, indent=1)
    return tab


# =========================================================================== exercises
def phoneme_split(seed=5):
    """Phoneme data (log-periodograms at 256 frequencies, five classes), split 50-50 by speaker so
    that no speaker is in both halves. Returns (Xtr, gtr, Xte, gte, class names)."""
    d = common.esl_data("phoneme.data", sep=",")
    X = d[["x.%d" % j for j in range(1, 257)]].values.astype(float)
    names = sorted(d["g"].unique())
    g = np.array([names.index(v) for v in d["g"]])
    spk = np.array([".".join(s.split(".")[1:3]) for s in d["speaker"]])
    us = np.unique(spk)
    rng = np.random.default_rng(seed)
    tr_spk = set(rng.permutation(us)[: len(us) // 2])
    tr = np.array([s in tr_spk for s in spk])
    return X[tr], g[tr], X[~tr], g[~tr], names


def ns_orthobasis(n, J):
    """An orthonormal basis (n x J) for the natural cubic splines on 0..n-1 with J knots equally spaced
    from 0 to n-1 (boundary knots included): the constant plus J - 1 truncated-power columns, then QR."""
    t = np.arange(n, dtype=float)
    B = np.column_stack([np.ones(n), ns_basis(t / (n - 1), np.linspace(0, 1, J))])
    Q, _ = np.linalg.qr(B)
    return Q


def kmeans_from(Z, idx_sets, iters=200):
    """k-means started from each set of row indices in idx_sets; returns the best centres."""
    best = (np.inf, None)
    for idx in idx_sets:
        C = Z[list(idx)].copy()
        lab = None
        for _ in range(iters):
            D = ((Z[:, None, :] - C[None, :, :]) ** 2).sum(-1)
            new = D.argmin(1)
            if lab is not None and np.array_equal(new, lab):
                break
            lab = new
            for r in range(len(C)):
                if (lab == r).any():
                    C[r] = Z[lab == r].mean(0)
        ss = float(((Z - C[lab]) ** 2).sum())
        if ss < best[0]:
            best = (ss, C)
    return best[1]


def exercise_12_5(Ks=(1, 3, 5, 7), Js=(5, 10, 15), starts=5, seed=5):
    """Nearest-prototype classification of the phonemes with K k-means prototypes per class, each
    restricted to be smooth, m = B theta with B an orthonormal natural-spline basis with J knots.
    Because B^T B = I, ||x - B theta||^2 = ||x - B B^T x||^2 + ||B^T x - theta||^2 and the first term
    does not depend on the prototype: both the k-means fit and the classification can be done on the
    J coordinates z = B^T x. The starting rows are the same for every J. Returns {(K, J): test error},
    with J = 256 meaning unrestricted prototypes."""
    Xtr, gtr, Xte, gte, names = phoneme_split(seed)
    rng = np.random.default_rng(seed)
    starts_idx = {(k, K): [rng.choice(np.sum(gtr == k), K, replace=False) for _ in range(starts)] for k in range(5) for K in Ks}
    out = {}
    for J in tuple(Js) + (256,):
        Q = ns_orthobasis(256, J) if J < 256 else np.eye(256)
        Ztr, Zte = Xtr @ Q, Xte @ Q
        for K in Ks:
            protos, labs = [], []
            for k in range(5):
                C = kmeans_from(Ztr[gtr == k], starts_idx[(k, K)])
                protos.append(C)
                labs += [k] * K
            P = np.vstack(protos)
            labs = np.array(labs)
            D = ((Zte[:, None, :] - P[None, :, :]) ** 2).sum(-1)
            Dtr = ((Ztr[:, None, :] - P[None, :, :]) ** 2).sum(-1)
            out[(K, J)] = (error_rate(labs[D.argmin(1)], gte), error_rate(labs[Dtr.argmin(1)], gtr))
    return out


def kernel_ridge_with_intercept(K, y, lam):
    """Exercise 12.3: minimise sum (y_i - b0 - f(x_i))^2 + lam ||beta||^2 with f = h^T beta and the
    constant unpenalised. Solution: f(x) = b0 + sum_i a_i K(x, x_i), a = (K + lam I)^{-1}(y - b0 1),
    b0 = 1^T (K + lam I)^{-1} y / 1^T (K + lam I)^{-1} 1."""
    N = len(y)
    A = K + lam * np.eye(N)
    u = np.linalg.solve(A, y)
    v = np.linalg.solve(A, np.ones(N))
    b0 = u.sum() / v.sum()
    return u - b0 * v, float(b0)


def kernel_lda_two_class(K, y, gamma):
    """Exercise 12.10: two-class LDA on features h(x) with the regularised within-class covariance
    W_h + gamma I, computed from the kernel matrix K = H H^T only. The direction is beta = H^T c with
    (C K + gamma I) c = d, where C is the block-diagonal within-class centring matrix divided by N and
    d has entries 1/N_+ on class +1 and -1/N_- on class -1. Returns the discriminant values
    h(x_i)^T beta = (K c)_i on the training data and c."""
    N = len(y)
    cls = [np.flatnonzero(y == v) for v in (-1, 1)]
    # within-class scatter in the dual: W_h beta with beta = H^T c is H^T M c, M = sum_k (I_k - 1 1^T / N_k) restricted
    Mc = np.zeros((N, N))
    for idx in cls:
        Ck = np.zeros((N, N))
        Ck[np.ix_(idx, idx)] = np.eye(len(idx)) - 1.0 / len(idx)
        Mc += Ck
    Mc /= N
    # mean difference: H^T d with d = 1_{class +1}/N_+ - 1_{class -1}/N_-
    d = np.zeros(N)
    d[cls[1]] = 1.0 / len(cls[1])
    d[cls[0]] = -1.0 / len(cls[0])
    # (W_h + gamma I) beta = mu_+ - mu_-  with beta = H^T c  <=>  H^T (Mc K c + gamma c - d) = 0;
    # it suffices that Mc K c + gamma c = d
    c = np.linalg.solve(Mc @ K + gamma * np.eye(N), d)
    return K @ c, c


def mda2_em(X, g, R, K, W0, iters=200):
    """Exercise 12.11: EM for the MDA2 model P(G, X) = sum_r pi_r P_r(G) phi(X; mu_r, Sigma), in which
    every centre carries a class profile P_r(G). E-step: W_ir ∝ pi_r P_r(g_i) phi(x_i; mu_r, Sigma);
    M-step: pi_r = mean_i W_ir, P_r(k) = sum_{g_i = k} W_ir / sum_i W_ir, weighted means and pooled
    covariance. Returns (pi, P, mu, Sigma, W)."""
    N, p = X.shape
    W = W0.copy()
    for _ in range(iters):
        nr = W.sum(0)
        pi = nr / N
        Pk = np.array([[W[g == k, r].sum() / nr[r] for k in range(K)] for r in range(R)])
        mu = (W.T @ X) / nr[:, None]
        S = sum((W[:, r, None] * (X - mu[r])).T @ (X - mu[r]) for r in range(R)) / N
        L = np.column_stack([np.log(np.maximum(pi[r] * Pk[r, g], 1e-300)) + common.gauss_logpdf(X, mu[r], S) for r in range(R)])
        L = np.where(np.isfinite(L), L, -np.inf)
        W = np.exp(L - common.logsumexp(L, axis=1)[:, None])
    return pi, Pk, mu, S, W


# =========================================================================== data for the demos
def export_vowel_json():
    """data/ch12-vowel.json for fda-optimal-scoring-demo.html: the vowel training and test data and
    the natural-spline knots (equally spaced training quantiles) for 2..8 df per input."""
    Xtr, gtr, Xte, gte = vowel()
    out = {
        "note": "Vowel data of Hastie, Tibshirani and Friedman (2009), Sections 4.3 and 12.5 (vowel.train, vowel.test from the book's website).",
        "xtr": Xtr.tolist(), "gtr": gtr.tolist(), "xte": Xte.tolist(), "gte": gte.tolist(),
        "knots": {str(df): [[float("%.10g" % v) for v in k] for k in additive_ns_knots(Xtr, df)] for df in range(2, 9)},
    }
    os.makedirs(DATA_OUT, exist_ok=True)
    path = os.path.join(DATA_OUT, "ch12-vowel.json")
    with open(path, "w") as f:
        json.dump(out, f, separators=(",", ":"))
    print("wrote", os.path.relpath(path, os.getcwd()), "(%.0f kB)" % (os.path.getsize(path) / 1024))
    return path


def demo_vowel_fit(basis="ns", df=4, lam=0.0, L=None):
    """The fit of fda-optimal-scoring-demo.html: basis 'linear' (LDA), 'ns' (additive natural splines,
    df per input) or 'poly2' (all monomials of degree <= 2 of the standardised inputs); every column is
    divided by its training standard deviation, and lam adds the ridge penalty lam * ||beta||^2.
    Returns (training error, test error, alpha^2) at dimension L (default: all)."""
    Xtr, gtr, Xte, gte = vowel()
    if basis == "linear":
        H, Ht = Xtr, Xte
    elif basis == "ns":
        kn = additive_ns_knots(Xtr, df)
        H, Ht = additive_ns_basis(Xtr, kn), additive_ns_basis(Xte, kn)
    else:
        mu, sd = Xtr.mean(0), Xtr.std(0)
        H, Ht = poly_basis((Xtr - mu) / sd, 2), poly_basis((Xte - mu) / sd, 2)
    sc = H.std(0)
    H, Ht = H / sc, Ht / sc
    f = fda(H, gtr, 11, lam=lam, Omega=np.eye(H.shape[1]) if lam > 0 else None)
    return error_rate(f.predict(H, L), gtr), error_rate(f.predict(Ht, L), gte), f.alpha2


# =========================================================================== driver
FIGURES = {
    "12.1": fig_12_1, "12.2": fig_12_2, "12.3": fig_12_3, "12.4": fig_12_4, "12.5": fig_12_5,
    "12.6": fig_12_6, "12.7": fig_12_7, "12.8": fig_12_8, "12.9": fig_12_9, "12.10": fig_12_10,
    "12.11": fig_12_11, "12.12": fig_12_12, "12.13": fig_12_13, "12.14": fig_12_14, "12.15": fig_12_15,
}


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