"""Hastie, Tibshirani and Friedman (2009), Chapter 9: Additive Models, Trees, and Related Methods.

Reproduces the figures of Chapter 9 of T. Hastie, R. Tibshirani and J. Friedman, The Elements of
Statistical Learning, 2nd edition (Springer, 2009), pp. 295-336, written from scratch with numpy, scipy and
matplotlib. Every method the chapter is about is implemented here, meant to be read next to the lecture
notes (../ch09-additive-models-trees.html):

* Section 9.1, generalised additive models: SmoothingSpline (a weighted cubic smoothing spline in a
  B-spline basis, with all the knots or, for many distinct values, the reduced knot set of R's
  smooth.spline; lam_for_df finds lambda with trace S = df), backfit (Algorithm 9.1), backfit_modified
  (the linear parts fitted jointly, Buja, Hastie and Tibshirani 1989) and local_scoring (Algorithm 9.2,
  with lambda_j recomputed at every step so that trace S_j - 1 = df under the current weights, and step
  halving). spam_gam fits the additive logistic regression of Section 9.1.2; spam_gam_table gives
  Table 9.2 (linear parts, standard errors, Z scores and likelihood-ratio tests of nonlinearity);
  spam_linear_models the linear logistic comparisons.
* Section 9.2, trees: Tree (CART: greedy split search by cumulative sums with the deviance, Gini or
  squared error, the growing rules minsize 10 / mincut 5 / mindev 0.01, observation weights, weakest-link
  pruning in prune_sequence, subtree_at), cv_tree (cross-validation indexed by alpha), impurity (9.17),
  surrogate_splits, tree_instability (bootstrap trees), roc_points and auc_mann_whitney (Figure 9.6).
* Section 9.3, PRIM: prim_peel (top-down peeling) and prim_paste (bottom-up pasting), spam_prim.
* Section 9.4, MARS: class MARS (forward pass scoring every knot of a (parent, input) pair in one pass
  over the sorted data, Friedman's minspan and endspan, backward deletion and GCV (9.20) with
  M = r + c (r - 1)/2), spam_mars, mars_scenarios (Table 9.4).
* Section 9.5, hierarchical mixtures of experts: hme_fit (EM for a two-level HME of linear Gaussian
  experts with softmax gates; the gate M-steps are weighted multinomial logistic regressions solved by
  Newton-Raphson), hme_predict.
* Exercises: ozone_additive, additive_trace and ozone_methods (Exercise 9.6, New York ozone data),
  tree_df_simulation and tree_df_ye (Exercise 9.5), correlated_pair (Exercise 9.2 and the convergence
  of backfitting), Figure 9.S4 (Exercise 9.4).

Figures reproduced: 9.1, 9.2, 9.3, 9.4, 9.5, 9.6, 9.7, 9.8, 9.9, 9.11, 9.12, and the content of Tables
9.1-9.4 and of the PRIM rule tables (printed; the notes show them as HTML tables), plus four
supplementary figures: 9.S1 (the additive model for the ozone data, Exercise 9.6), 9.S2 (an HME fitted by
EM against a CART tree, Section 9.5), 9.S3 (degrees of freedom of regression trees, Exercise 9.5) and 9.S4
(convergence of backfitting with correlated inputs, and the same smoother twice, Exercises 9.2 and 9.4).
Run `python3 ch09_additive_models_trees.py --list`, `python3 ch09_additive_models_trees.py` (all
figures, Table 9.4 and the demonstration data: about 12 minutes the first time, two of them for the spam
MARS fit and six for the 57 refits of Table 9.2, which are cached in cache/; about two minutes afterwards)
or `python3 ch09_additive_models_trees.py --fig 9.4`. Files go to ../img/ch09/; the data the browser
demonstrations use are written to ../data/ by export_demo_data().

Figures not reproduced, and why:
* Figure 9.10 is a schematic of the MARS forward search (boxes for the candidate basis functions);
  nothing in it is computed.
* Figure 9.13 is a diagram of a two-level HME (gating networks and experts); nothing in it is computed.
  Figure 9.S2 shows an HME actually fitted by EM.

Settings chosen where the book gives none:
* Spam data: the training/test split of spam.traintest on the book's website (3065 / 1536 messages; 595
  of the test messages are spam). Every input is transformed to log(x + 0.1) for the additive model (as
  the book says) and for MARS (Figure 9.12); trees and PRIM use the raw inputs.
* Figure 9.1: the sixteen predictors of the book's figure, each plotted on its original scale.
* Figures 9.4-9.6: tree grown with the deviance, minsize 10, mincut 5, mindev 0.01 (the defaults of the
  R function tree(); with them the alpha breakpoints are the book's), pruned with the misclassification
  count; 10-fold cross-validation with folds drawn by numpy default_rng(2) over the training messages,
  fold trees pruned at the geometric midpoints of the breakpoints; error bars are one standard error over
  the folds. Figure 9.5 shows the 17-leaf member of the sequence, as the book does. The weighted tree of
  Figure 9.6 has weight 5 on email and is the largest member of its sequence with at most 17 leaves.
* Figures 9.7-9.8: 200 points uniform on the unit square from numpy default_rng(7); peeling alpha = 0.1,
  k = max(1, floor(alpha n)) observations per peel, down to 10 observations.
* PRIM on spam: alpha = 0.1; each box is the largest in its peeling sequence whose 10-fold cross-validated
  box mean is at least 0.95 (folds from default_rng(0) and default_rng(1)), followed by pasting with
  alpha = 0.01.
* Figure 9.11: knots x51 = 0.55 and x72 = 0.6 on the unit square.
* Figure 9.12: interactions of degree at most 2, forward pass to 101 terms, GCV cost c = 3 per knot.
* Table 9.4: 50 simulations (numpy default_rng(2009)) of each scenario, forward pass to max(21, 2p + 1)
  terms, interactions of degree at most 2, c = 3; mean, standard error and median of R^2 are reported.
* Figure 9.S2: 400 draws from a two-level HME with soft gates (seed 3), six random EM starts.
* Figure 9.S3: 100 fixed observations of 10 Gaussian inputs (seed 5); trees with exactly m leaves grown
  best-first; 10 and 400 simulated responses.
"""
import json
import os
import sys

import numpy as np
import scipy.linalg

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

CH = 9
HERE = os.path.dirname(os.path.abspath(__file__))
JSON_DIR = os.path.normpath(os.path.join(HERE, "..", "data"))
CACHE_DIR = os.path.join(HERE, "cache")

# Seeds and settings chosen where the book gives none (see the module docstring)
TREE_SEED = 2          # folds of the 10-fold cross-validation of the spam tree (Figure 9.4)
PRIM_SEED = 0          # folds of the cross-validation that chooses the PRIM boxes
PRIM_TARGET = 0.95     # a PRIM box is the largest one whose cross-validated box mean is at least this
MARS_SIM_SEED = 2009   # Table 9.4
TREEDF_SEED = 5        # Exercise 9.5
PRIM_SIM_SEED = 7      # the 200 points of Figures 9.7-9.8
HME_SEED = 3           # the simulated curve of Figure 9.S2
BF_SIM_SEED = 11       # the correlated inputs of Figure 9.S4 and the backfitting demonstration
MARS_DEMO_SEED = 21    # the sample of scenario (9.21) in the MARS demonstration

# The 57 spam features, named as in the book (Table 9.2, Figure 9.5): 48 word frequencies, 6 character
# frequencies (ch;, ch(, ch[, ch!, ch$, ch#) and 3 statistics of runs of capital letters.
SPAM_NAMES = ("make address all 3d our over remove internet order mail receive will people report addresses "
              "free business email you credit your font 000 money hp hpl george 650 lab labs telnet 857 data "
              "415 85 technology 1999 parts pm direct cs meeting original project re edu table conference "
              "ch; ch( ch[ ch! ch$ ch# CAPAVE CAPMAX CAPTOT").split()

# =========================================================================== data
def load_spam():
    """Spam data: X (4601 x 57), y (1 = spam, 0 = email), boolean test mask (spam.traintest == 1)."""
    A = np.loadtxt(common.esl_file("spam.data"))
    tt = np.loadtxt(common.esl_file("spam.traintest")).astype(int)
    return A[:, :57], A[:, 57].astype(int), tt == 1


def load_ozone():
    """New York ozone data (111 days): columns ozone, radiation, temperature, wind."""
    P = common.esl_data("ozone.data")
    return P[["ozone", "radiation", "temperature", "wind"]].to_numpy(float)


# =========================================================================== smoothing splines
def n_knots(n):
    """Number of knots used for n distinct values: all of them up to 49, then the slowly growing rule of
    R's smooth.spline (50 at n = 50, 100 at 200, 140 at 800, 200 at 3200)."""
    if n < 50:
        return n
    a1, a2, a3, a4 = np.log2([50, 100, 140, 200])
    if n < 200:
        return int(np.trunc(2 ** (a1 + (a2 - a1) * (n - 50) / 150)))
    if n < 800:
        return int(np.trunc(2 ** (a2 + (a3 - a2) * (n - 200) / 600)))
    if n < 3200:
        return int(np.trunc(2 ** (a3 + (a4 - a3) * (n - 800) / 2400)))
    return int(np.trunc(200 + (n - 3200) ** 0.2))


class SmoothingSpline:
    """Cubic smoothing spline with observation weights, in a cubic B-spline basis (Sections 5.4 and 5.9).

    Minimises sum_i w_i (r_i - f(x_i))^2 + lam int f''(t)^2 dt over cubic splines with knots at the distinct
    values of x (all of them if all_knots, otherwise n_knots(n) of them at evenly spaced ranks, as R's
    smooth.spline does). With all the knots this is exactly the smoothing spline of Section 5.4 (the
    minimiser is the natural cubic spline); with fewer it is its standard, numerically stable approximation.
    In the basis, f = B theta and (B^T W B + lam Omega) theta = B^T W r, Omega_kl = int B_k'' B_l''; both
    matrices are banded, so each fit costs O(n). For fixed weights, prepare(w) factorises the system once;
    trace S = sum_k 1/(1 + lam mu_k) with mu_k the generalised eigenvalues of (Omega, B^T W B)."""

    def __init__(self, x, all_knots=False):
        from scipy.interpolate import BSpline
        x = np.asarray(x, float)
        self.t, self.inv = np.unique(x, return_inverse=True)
        n = self.n = len(self.t)
        nk = n if all_knots else n_knots(n)
        kn = self.t[np.round(np.linspace(0, n - 1, nk)).astype(int)]
        self.knots = np.r_[[kn[0]] * 3, kn, [kn[-1]] * 3]
        self.nb = len(self.knots) - 4
        self.Bd = BSpline.design_matrix(self.t, self.knots, 3).tocsr()
        # Omega by 2-point Gauss-Legendre on each knot interval (B'' is linear there: exact)
        g = np.array([-1, 1]) / np.sqrt(3)
        lo, hi = kn[:-1], kn[1:]
        pts = (0.5 * (lo + hi)[:, None] + 0.5 * (hi - lo)[:, None] * g[None, :]).ravel()
        wts = np.repeat(0.5 * (hi - lo), 2)
        D2 = BSpline(self.knots, np.eye(self.nb), 3).derivative(2)(pts)
        self.Omega = (D2 * wts[:, None]).T @ D2
        self._w = None

    @staticmethod
    def _to_band(A, u=3):
        nb = A.shape[0]
        ab = np.zeros((u + 1, nb))
        for k in range(u + 1):
            ab[u - k, k:] = np.diagonal(A, k)
        return ab

    def aggregate(self, r, w):
        Wd = np.bincount(self.inv, weights=w, minlength=self.n)
        rbar = np.bincount(self.inv, weights=w * r, minlength=self.n) / np.maximum(Wd, 1e-300)
        return Wd, rbar

    def prepare(self, w):
        """Gram matrix B^T W B for the weights w (one per observation) and the generalised eigenvalues."""
        Wd = np.bincount(self.inv, weights=w, minlength=self.n)
        A = (self.Bd.T @ self.Bd.multiply(Wd[:, None])).toarray()
        A = 0.5 * (A + A.T)
        ridge = 1e-11 * np.trace(A) / self.nb + 1e-300
        mu = scipy.linalg.eigh(self.Omega, A + ridge * np.eye(self.nb), eigvals_only=True)
        mu = np.sort(np.maximum(mu, 0.0))
        mu[:2] = 0.0                                   # straight lines are not penalised
        self._w, self._A, self._mu, self._fact = w, A + ridge * np.eye(self.nb), mu, {}
        return self

    def _ensure(self, w):
        if self._w is None or (self._w is not w and not np.array_equal(self._w, w)):
            self.prepare(w)

    def df(self, lam, w=None):
        """trace S_lam = trace((B^T W B + lam Omega)^-1 B^T W B), computed exactly (banded solve)."""
        self._ensure(np.ones(len(self.inv)) if w is None else w)
        cf = scipy.linalg.cholesky_banded(self._to_band(self._A + lam * self.Omega))
        return float(np.trace(scipy.linalg.cho_solve_banded((cf, False), self._A)))

    def lam_for_df(self, df, w=None):
        """lam with trace S_lam = df under the weights w (df decreases strictly in lam: bisection)."""
        self._ensure(np.ones(len(self.inv)) if w is None else w)
        mu = self._mu
        f = lambda u: np.sum(1.0 / (1.0 + np.exp(u) * mu)) - df
        lo = -np.log(max(np.max(mu), 1e-300))
        while f(lo) < 0:
            lo -= 10.0
        hi = lo + 10.0
        while f(hi) > 0:
            hi += 10.0
        for _ in range(200):
            mid = 0.5 * (lo + hi)
            if f(mid) > 0:
                lo = mid
            else:
                hi = mid
            if hi - lo < 1e-12:
                break
        # the eigenvalues give a very good start; polish with the exact trace (secant steps on log lam)
        u0 = 0.5 * (lo + hi)
        u1 = u0 + 1e-3
        g = lambda u: self.df(np.exp(u), self._w) - df
        e0, e1 = g(u0), g(u1)
        for _ in range(20):
            if abs(e1) < 1e-10 or e1 == e0:
                break
            u0, u1, e0 = u1, u1 - e1 * (u1 - u0) / (e1 - e0), e1
            e1 = g(u1)
        return float(np.exp(u1))

    def coef(self, r, w, lam):
        """B-spline coefficients of the weighted smoothing-spline fit to r."""
        self._ensure(w)
        if lam not in self._fact:
            self._fact[lam] = scipy.linalg.cholesky_banded(self._to_band(self._A + lam * self.Omega))
        Wd, rbar = self.aggregate(r, w)
        return scipy.linalg.cho_solve_banded((self._fact[lam], False), self.Bd.T @ (Wd * rbar))

    def smooth(self, r, w, lam):
        """Fitted values at the N observations."""
        return (self.Bd @ self.coef(r, w, lam))[self.inv]

    def curve(self, theta, grid):
        """The fitted spline on grid, continued linearly beyond the data (as a natural spline)."""
        from scipy.interpolate import BSpline
        f = BSpline(self.knots, theta, 3)
        grid = np.asarray(grid, float)
        a, b = self.t[0], self.t[-1]
        out = f(np.clip(grid, a, b))
        out = out + np.where(grid < a, (grid - a) * f(a, 1), 0.0) + np.where(grid > b, (grid - b) * f(b, 1), 0.0)
        return out

    def matrix(self, w, lam):
        """The N x N smoother matrix (small problems only)."""
        N = len(self.inv)
        return np.column_stack([self.smooth(e, w, lam) for e in np.eye(N)])


# =========================================================================== backfitting (Algorithm 9.1)
def backfit(X, y, smoothers, w=None, F=None, tol=1e-8, maxit=200, center=True, history=False):
    """Weighted backfitting for the additive model y = alpha + sum_j f_j(x_j) + eps (Algorithm 9.1).

    smoothers: list of callables S_j(r, w) -> fitted values at the N observations (a linear smoother
    applied to the partial residual r with observation weights w). F (N x p) are starting values.
    Each cycle visits j = 1..p, replaces f_j by S_j applied to the partial residual
    y - alpha - sum_{k != j} f_k, and (if center) subtracts its weighted mean. Stops when the relative
    change of the fitted functions in a cycle is below tol. Returns alpha, F, the number of cycles and
    (if history) the residual sum of squares after every single update."""
    N, p = X.shape
    w = np.ones(N) if w is None else np.asarray(w, float)
    sw = w.sum()
    alpha = float(np.sum(w * y) / sw)
    F = np.zeros((N, p)) if F is None else F.copy()
    fit = alpha + F.sum(1)
    hist = []
    for it in range(1, maxit + 1):
        Fold = F.copy()
        for j in range(p):
            partial = y - fit + F[:, j]
            fj = smoothers[j](partial, w)
            if center:
                fj = fj - np.sum(w * fj) / sw
            fit += fj - F[:, j]
            F[:, j] = fj
            if history:
                hist.append(float(np.sum(w * (y - fit) ** 2)))
        num = np.sqrt(np.sum(w[:, None] * (F - Fold) ** 2))
        den = np.sqrt(np.sum(w[:, None] * F ** 2)) + 1e-12
        if num / den < tol:
            break
    return dict(alpha=alpha, F=F, cycles=it, history=hist)


def backfit_modified(X, y, smoothers, w=None, F=None, tol=1e-8, maxit=500):
    """Modified backfitting (Buja, Hastie and Tibshirani 1989) for smoothers that reproduce straight lines.

    The linear parts of all the terms are fitted jointly, by weighted least squares of the partial residual
    on (1, x_1, ..., x_p) (the projection H); each smoother is then applied to its partial residual and its
    own straight-line part is removed (S~_j = S_j - H_j, H_j the weighted line on x_j). The fixed point
    solves the same estimating equations as Algorithm 9.1, but the slowly converging linear directions are
    solved exactly at every cycle. Returns alpha, F (each column a whole term f_j, centred), the linear
    coefficients, the nonlinear parts and the number of cycles."""
    N, p = X.shape
    w = np.ones(N) if w is None else np.asarray(w, float)
    sw = w.sum()
    sq = np.sqrt(w)
    D = np.column_stack([np.ones(N), X])
    Qd, Rd = np.linalg.qr(D * sq[:, None])
    xm = (w @ X) / sw
    Xc = X - xm
    sxx = np.maximum(np.sum(w[:, None] * Xc ** 2, 0), 1e-300)
    if F is None:
        G = np.zeros((N, p))
    else:                                   # nonlinear parts of the starting functions
        G = F - Xc * (np.sum(w[:, None] * Xc * F, 0) / sxx)
    for it in range(1, maxit + 1):
        Gold = G.copy()
        r = y - G.sum(1)
        coef = scipy.linalg.solve_triangular(Rd, Qd.T @ (sq * r))
        lin = D @ coef
        for j in range(p):
            partial = y - lin - G.sum(1) + G[:, j]
            s = smoothers[j](partial, w)
            s = s - np.sum(w * s) / sw
            s = s - Xc[:, j] * (np.sum(w * Xc[:, j] * s) / sxx[j])
            G[:, j] = s
        num = np.sqrt(np.sum(w[:, None] * (G - Gold) ** 2))
        den = np.sqrt(np.sum(w[:, None] * G ** 2)) + 1e-12 * np.sqrt(np.sum(w * y ** 2))
        if num / den < tol:
            break
    r = y - G.sum(1)
    coef = scipy.linalg.solve_triangular(Rd, Qd.T @ (sq * r))
    F = G + Xc * coef[1:]
    alpha = coef[0] + float(coef[1:] @ xm)
    return dict(alpha=alpha, F=F, coef=coef, G=G, cycles=it)


def spline_smoothers(X, lams, all_knots=False):
    """Backfitting smoothers: a SmoothingSpline for each column with fixed lam_j."""
    sps = [SmoothingSpline(X[:, j], all_knots) for j in range(X.shape[1])]
    return sps, [(lambda r, w, s=s, l=l: s.smooth(r, w, l)) for s, l in zip(sps, lams)]


# =========================================================================== local scoring (Algorithm 9.2)
def local_scoring(X, y, sps, df=None, lams=None, tol=1e-9, maxit=100, bf_tol=1e-6, bf_maxit=60, prior_w=None,
                  start=None, verbose=False):
    """Additive logistic regression (9.8) by local scoring (Algorithm 9.2).

    Starting from alpha = logit(ybar), f_j = 0 (or from `start`), iterate: eta = alpha + sum f_j,
    p = 1/(1 + e^-eta), working response z = eta + (y - p)/(p(1 - p)), weights w = p(1 - p); fit a weighted
    additive model to z by backfitting (warm-started at the current functions). Each term is a cubic
    smoothing spline: with df given (a number or one per term), its lam_j is recomputed at every
    iteration so that trace S_j(lam_j) - 1 = df_j under the current weights (the book's 'nominal four
    degrees of freedom'); with lams given, the lam_j stay fixed. df_j = 1 makes term j linear.
    prior_w multiplies the weights (observation weights for unequal losses). Stops when the change of the
    deviance is below tol (relative)."""
    N, p = X.shape
    pw = np.ones(N) if prior_w is None else np.asarray(prior_w, float)
    if start is None:
        ybar = np.sum(pw * y) / pw.sum()
        alpha, F = np.log(ybar / (1 - ybar)), np.zeros((N, p))
    else:
        alpha, F = start["alpha"], start["F"].copy()
    dfs = None if df is None else (np.full(p, float(df)) if np.isscalar(df) else np.asarray(df, float))
    lam = None if lams is None else np.asarray(lams, float).copy()
    dev_old = np.inf
    for it in range(1, maxit + 1):
        eta = alpha + F.sum(1)
        pr = np.clip(expit(eta), 1e-10, 1 - 1e-10)
        wk = pr * (1 - pr)
        z = eta + (y - pr) / wk
        ww = pw * wk
        if dfs is not None:
            lam = np.array([np.inf if dfs[j] <= 1 else sps[j].lam_for_df(dfs[j] + 1, ww) for j in range(p)])
        smoothers = [_linear_smoother(X[:, j]) if not np.isfinite(lam[j]) else
                     (lambda r, w, s=sps[j], l=lam[j]: s.smooth(r, w, l)) for j in range(p)]
        bf = backfit_modified(X, z, smoothers, w=ww, F=F, tol=bf_tol, maxit=bf_maxit)
        a_new, F_new = bf["alpha"], bf["F"]
        dev = binomial_deviance(y, a_new + F_new.sum(1), pw)
        halvings = 0
        while np.isfinite(dev_old) and dev > dev_old * (1 + 1e-3) and halvings < 30:
            # step halving: the Newton step overshot, move half way back towards the previous fit
            a_new, F_new = 0.5 * (a_new + alpha), 0.5 * (F_new + F)
            dev = binomial_deviance(y, a_new + F_new.sum(1), pw)
            halvings += 1
        alpha, F = a_new, F_new
        if verbose:
            print("    local scoring %2d: deviance %.5f (%d backfitting cycles)" % (it, dev, bf["cycles"]))
        if abs(dev_old - dev) < tol * (abs(dev) + 0.1):
            break
        dev_old = dev
    eta = alpha + F.sum(1)
    pr = np.clip(expit(eta), 1e-10, 1 - 1e-10)
    return dict(alpha=alpha, F=F, eta=eta, prob=pr, weights=pw * pr * (1 - pr), prior_w=pw, iters=it,
                deviance=dev, lams=lam)


def _linear_smoother(x):
    """Weighted least-squares straight line, as a backfitting smoother (a term with df = 1)."""
    def S(r, w):
        sw = w.sum()
        xm, rm = np.sum(w * x) / sw, np.sum(w * r) / sw
        b = np.sum(w * (x - xm) * (r - rm)) / max(np.sum(w * (x - xm) ** 2), 1e-300)
        return rm + b * (x - xm)
    return S


def expit(a):
    return 0.5 * (1.0 + np.tanh(0.5 * np.asarray(a, float)))


def binomial_deviance(y, eta, w=None):
    w = np.ones(len(y)) if w is None else w
    # -2 log-likelihood, computed stably: log(1 + e^eta) - y eta
    return float(2 * np.sum(w * (np.logaddexp(0, eta) - y * eta)))
# =========================================================================== trees (Section 9.2)
def impurity(counts, kind):
    """Node impurity (9.17) from (weighted) class counts; counts has the classes on the last axis.
    kind: 'misclass' 1 - max p, 'gini' sum p(1 - p), 'deviance' (cross-entropy) -sum p log p."""
    counts = np.asarray(counts, float)
    n = counts.sum(-1, keepdims=True)
    p = counts / np.where(n > 0, n, 1.0)
    if kind == "misclass":
        return 1.0 - p.max(-1)
    if kind == "gini":
        return np.sum(p * (1 - p), -1)
    with np.errstate(divide="ignore", invalid="ignore"):
        return -np.sum(np.where(p > 0, p * np.log(p), 0.0), -1)


class Tree:
    """A CART tree (Breiman et al. 1984) grown by greedy binary splitting (Section 9.2).

    Nodes are stored in arrays: var[k] and thr[k] (go left when x[var] < thr; thr is the midpoint
    between two consecutive distinct values, as in the book's Figure 9.5), left[k], right[k] (-1 for
    a leaf), parent[k], and per-node summaries of the training data: weighted class counts (classification)
    or the weighted mean and sum of squares (regression).

    Growing (grow): a node with at least minsize observations is split by the variable and split point
    that minimise the total impurity of the two children, N_L Q_L + N_R Q_R (the criterion (9.13) for
    regression, with Q = squared error; 'deviance' or 'gini' for classification), subject to each child
    having at least mincut observations; a node is not split if its deviance is below mindev times that
    of the root (these are the defaults of the R function tree(): minsize 10, mincut 5, mindev 0.01).
    Splits are tried in the order of the variables and of the split points, and the first minimiser is
    kept. max_leaves stops growing once the tree has that many leaves (nodes are split best-first, by the
    decrease of the criterion).
    """

    def __init__(self, task="class", criterion="deviance", minsize=10, mincut=5, mindev=0.01, K=2,
                 max_leaves=None):
        self.task, self.criterion, self.minsize, self.mincut, self.mindev = task, criterion, minsize, mincut, mindev
        self.K, self.max_leaves = K, max_leaves

    # ================================================================== node statistics
    def _node_stats(self, idx):
        w = self.w[idx]
        if self.task == "class":
            c = np.bincount(self.y[idx], weights=w, minlength=self.K)
            return c
        sw = w.sum()
        m = np.sum(w * self.y[idx]) / sw
        return np.array([sw, m, np.sum(w * (self.y[idx] - m) ** 2)])

    def _node_dev(self, stats):
        if self.task == "class":
            n = stats.sum()
            return float(2 * n * impurity(stats, "deviance")) if n > 0 else 0.0
        return float(stats[2])

    def _best_split(self, idx):
        """Best (criterion value, var, threshold) over all variables for the node with rows idx."""
        mask = np.zeros(self.N, bool)
        mask[idx] = True
        best = (np.inf, -1, np.nan, -1)
        nt = len(idx)
        for j in range(self.p):
            o = self.order[j][mask[self.order[j]]]
            xs = self.X[o, j]
            ok = np.zeros(nt - 1, bool)
            ok[:] = xs[1:] > xs[:-1]                          # a split between two distinct values
            cnt = np.arange(1, nt)
            ok &= (cnt >= self.mincut) & (nt - cnt >= self.mincut)
            if not ok.any():
                continue
            w = self.w[o]
            if self.task == "class":
                Y = np.zeros((nt, self.K))
                Y[np.arange(nt), self.y[o]] = w
                L = np.cumsum(Y, 0)[:-1]
                R = L[-1:] * 0 + (np.sum(Y, 0) - L)
                nL, nR = L.sum(1), R.sum(1)
                if self.criterion == "gini":
                    crit = nL * impurity(L, "gini") + nR * impurity(R, "gini")
                else:
                    crit = 2 * (nL * impurity(L, "deviance") + nR * impurity(R, "deviance"))
            else:
                yw = w * self.y[o]
                sw, sy, syy = np.cumsum(w)[:-1], np.cumsum(yw)[:-1], np.cumsum(yw * self.y[o])[:-1]
                tw, ty, tyy = w.sum(), yw.sum(), np.sum(yw * self.y[o])
                crit = (syy - sy ** 2 / sw) + ((tyy - syy) - (ty - sy) ** 2 / (tw - sw))
            crit = np.where(ok, crit, np.inf)
            k = int(np.argmin(crit))
            if best[1] < 0 or crit[k] < best[0] - 1e-9 * max(1.0, abs(best[0])):
                best = (float(crit[k]), j, 0.5 * (xs[k] + xs[k + 1]), k)
        return best

    # ================================================================== growing
    def grow(self, X, y, w=None):
        self.X = np.asarray(X, float)
        self.y = np.asarray(y, int if self.task == "class" else float)
        self.N, self.p = self.X.shape
        self.w = np.ones(self.N) if w is None else np.asarray(w, float)
        self.order = [np.argsort(self.X[:, j], kind="stable") for j in range(self.p)]
        self.var, self.thr, self.left, self.right, self.parent, self.stats, self.rows = [], [], [], [], [], [], []
        root = self._new(np.arange(self.N), -1)
        self.root_dev = self._node_dev(self.stats[root])
        frontier = [root]
        cand = {}
        n_leaves = 1
        while frontier:
            # best-first: evaluate the candidate split of every open leaf, split the best one
            for k in frontier:
                if k not in cand:
                    cand[k] = self._candidate(k)
            frontier = [k for k in frontier if cand[k] is not None]
            if not frontier or (self.max_leaves is not None and n_leaves >= self.max_leaves):
                break
            if self.max_leaves is None:
                k = frontier.pop(0)
            else:
                k = max(frontier, key=lambda kk: cand[kk][0])
                frontier.remove(k)
            gain, j, t = cand.pop(k)
            idx = self.rows[k]
            go_left = self.X[idx, j] < t
            self.var[k], self.thr[k] = j, t
            a = self._new(idx[go_left], k)
            b = self._new(idx[~go_left], k)
            self.left[k], self.right[k] = a, b
            frontier += [a, b]
            n_leaves += 1
        self._finish()
        return self

    def _candidate(self, k):
        idx = self.rows[k]
        dev = self._node_dev(self.stats[k])
        if len(idx) < self.minsize or dev <= self.mindev * self.root_dev or dev <= 1e-12:
            return None
        crit, j, t, _ = self._best_split(idx)
        if j < 0:
            return None
        node_crit = dev if (self.task == "reg" or self.criterion == "deviance") else \
            float(self.stats[k].sum() * impurity(self.stats[k], "gini"))
        return (node_crit - crit, j, t)

    def _new(self, idx, parent):
        self.var.append(-1); self.thr.append(np.nan); self.left.append(-1); self.right.append(-1)
        self.parent.append(parent); self.stats.append(self._node_stats(idx)); self.rows.append(idx)
        return len(self.var) - 1

    def _finish(self):
        self.var = np.array(self.var); self.thr = np.array(self.thr)
        self.left = np.array(self.left); self.right = np.array(self.right); self.parent = np.array(self.parent)
        self.stats = np.array(self.stats)
        self.n_nodes = len(self.var)
        self.count = np.array([len(r) for r in self.rows])
        if self.task == "class":
            self.pred = np.argmax(self.stats, 1)                   # majority (weighted) class, first if tied
            n = self.stats.sum(1)
            self.risk = n - self.stats.max(1)                     # weighted misclassification count R(t)
            self.prob = self.stats / np.where(n > 0, n, 1)[:, None]
        else:
            self.pred = self.stats[:, 1]
            self.risk = self.stats[:, 2]                          # sum of squares, N_m Q_m
        self.depth = np.zeros(self.n_nodes, int)
        for k in range(1, self.n_nodes):
            self.depth[k] = self.depth[self.parent[k]] + 1

    # ================================================================== using a (sub)tree
    def leaf_of(self, X, active=None):
        """Index of the leaf reached by each row of X in the subtree whose internal nodes are `active`
        (boolean over nodes; default: the full tree)."""
        X = np.asarray(X, float)
        act = (self.left >= 0) if active is None else active
        node = np.zeros(len(X), int)
        while True:
            internal = act[node]
            if not internal.any():
                return node
            ii = np.where(internal)[0]
            k = node[ii]
            goleft = X[ii, self.var[k]] < self.thr[k]
            node[ii] = np.where(goleft, self.left[k], self.right[k])

    def predict(self, X, active=None):
        return self.pred[self.leaf_of(X, active)]

    def n_leaves(self, active=None):
        act = (self.left >= 0) if active is None else active
        return int(np.sum(self._reachable(act) & ~act))

    def _reachable(self, act):
        r = np.zeros(self.n_nodes, bool)
        r[0] = True
        for k in range(self.n_nodes):          # parents precede children
            if r[k] and act[k]:
                r[self.left[k]] = r[self.right[k]] = True
        return r

    # ================================================================== cost-complexity pruning
    def prune_sequence(self, risk=None):
        """Weakest-link pruning (Breiman et al. 1984): the nested subtrees T_0 > T_1 > ... > root and the
        breakpoints alpha_0 = 0 <= alpha_1 < alpha_2 < ... For alpha in [alpha_k, alpha_{k+1}) the subtree
        T_k is the smallest minimiser of C_alpha(T) = sum of R over the leaves + alpha |T| (9.16).
        risk: R(t) per node (default: misclassification count, or the sum of squares for regression).
        Returns a list of (alpha_k, active-mask_k, number of leaves)."""
        R = self.risk if risk is None else np.asarray(risk, float)
        act = self.left >= 0
        seq, alpha = [], 0.0
        while True:
            reach = self._reachable(act)
            RT, nl = R.copy(), np.ones(self.n_nodes)
            for k in range(self.n_nodes - 1, -1, -1):          # children have larger indices
                if act[k] and reach[k]:
                    RT[k] = RT[self.left[k]] + RT[self.right[k]]
                    nl[k] = nl[self.left[k]] + nl[self.right[k]]
            internal = np.where(act & reach)[0]
            if len(internal) == 0:
                seq.append((alpha, act.copy(), 1))
                return seq
            g = (R[internal] - RT[internal]) / (nl[internal] - 1)
            gmin = g.min()
            tol = 1e-9 * max(1.0, abs(gmin))
            if gmin > alpha + tol:                 # the current tree is optimal on [alpha, gmin)
                seq.append((alpha, act.copy(), int(nl[0])))
                alpha = float(gmin)
            act[internal[g <= gmin + tol]] = False   # collapse every weakest link at once

    def subtree_at(self, alpha, seq=None):
        """Active-mask of the optimal subtree T_alpha (the member of the sequence for alpha)."""
        seq = self.prune_sequence() if seq is None else seq
        best = seq[0][1]
        for a, m, s in seq:
            if a <= alpha + 1e-12:
                best = m
        return best

    def subtree_size(self, size, seq=None):
        """The largest member of the pruning sequence with at most `size` leaves."""
        seq = self.prune_sequence() if seq is None else seq
        for a, m, s in seq:
            if s <= size:
                return m
        return seq[-1][1]


def cv_tree(X, y, folds, alphas, w=None, **kw):
    """K-fold cross-validation of cost-complexity pruning, indexed by alpha (as in Figure 9.4): for
    every fold a tree is grown on the other folds and pruned at each alpha in `alphas`; returns the
    held-out misclassification (or squared error) for every fold and alpha (array folds x alphas)."""
    K = folds.max() + 1
    out = np.zeros((K, len(alphas)))
    for f in range(K):
        tr, te = folds != f, folds == f
        T = Tree(**kw).grow(X[tr], y[tr], None if w is None else w[tr])
        seq = T.prune_sequence()
        for a_i, a in enumerate(alphas):
            pred = T.predict(X[te], T.subtree_at(a, seq))
            if T.task == "class":
                out[f, a_i] = np.sum((pred != y[te]) * (1.0 if w is None else w[te]))
            else:
                out[f, a_i] = np.sum((pred - y[te]) ** 2)
    return out


def roc_points(score, y):
    """Sensitivity and specificity for every threshold on score (predict 1 when score >= threshold),
    and the area under the ROC curve (trapezoid rule, which counts ties as one half)."""
    s = np.asarray(score, float)
    thr = np.unique(s)[::-1]
    P, Nn = np.sum(y == 1), np.sum(y == 0)
    sens = np.array([0.0] + [np.sum((s >= t) & (y == 1)) / P for t in thr])
    spec = np.array([1.0] + [np.sum((s < t) & (y == 0)) / Nn for t in thr])
    fpr = 1 - spec
    auc = float(np.sum(np.diff(fpr) * (sens[1:] + sens[:-1]) / 2))
    return sens, spec, auc


def auc_mann_whitney(score, y):
    """Area under the ROC curve as the Mann-Whitney statistic Pr(score_spam > score_email) + ties/2."""
    from scipy.stats import rankdata
    r = rankdata(score)
    n1, n0 = np.sum(y == 1), np.sum(y == 0)
    return float((r[y == 1].sum() - n1 * (n1 + 1) / 2) / (n1 * n0))


# =========================================================================== PRIM (Section 9.3, Algorithm 9.3)
def _peel_count(n, alpha):
    return max(1, int(np.floor(alpha * n)))


def prim_peel(X, y, alpha=0.1, min_count=10, inside=None):
    """Top-down peeling of PRIM (steps 1-3 of Algorithm 9.3).

    The box is a set of closed bounds lo_j <= x_j <= hi_j (initially infinite). At each step, for every
    input and both of its faces, the candidate peel moves the face to the (k+1)-th smallest (or largest)
    value of x_j in the box, k = max(1, floor(alpha n)): it removes the k observations with the smallest
    (largest) x_j, or fewer if there are ties at the new bound (none at all if more than n - k values are
    tied at the end, as with the many zero frequencies of the spam data). The peel giving the largest mean
    of y in the remaining box is made. Stops when no peel leaves at least min_count observations.
    Returns the list of boxes (dict lo, hi, n, mean, inside, face)."""
    X = np.asarray(X, float)
    N, p = X.shape
    inside = np.ones(N, bool) if inside is None else inside.copy()
    lo, hi = np.full(p, -np.inf), np.full(p, np.inf)
    boxes = [dict(lo=lo.copy(), hi=hi.copy(), n=int(inside.sum()), mean=float(y[inside].mean()), inside=inside.copy(),
                  face=None)]
    while True:
        idx = np.where(inside)[0]
        n = len(idx)
        k = _peel_count(n, alpha)
        if n - k < min_count:
            return boxes
        best = None
        for j in range(p):
            xj = X[idx, j]
            xs = np.sort(xj)
            for side in (0, 1):
                q = xs[k] if side == 0 else xs[n - 1 - k]
                keep = (xj >= q) if side == 0 else (xj <= q)
                m = int(keep.sum())
                if m == n or m < min_count:
                    continue
                mean = float(y[idx[keep]].mean())
                if best is None or mean > best[0] + 1e-12:
                    best = (mean, j, side, q, keep)
        if best is None:
            return boxes
        mean, j, side, q, keep = best
        if side == 0:
            lo[j] = q
        else:
            hi[j] = q
        inside = np.zeros(N, bool)
        inside[idx[keep]] = True
        boxes.append(dict(lo=lo.copy(), hi=hi.copy(), n=int(inside.sum()), mean=mean, inside=inside.copy(),
                          face=(j, side)))


def box_inside(X, lo, hi, active=None):
    X = np.asarray(X, float)
    m = np.all((X >= lo) & (X <= hi), axis=1)
    return m if active is None else (m & active)


def prim_paste(X, y, box, alpha=0.01, active=None):
    """Bottom-up pasting (step 4 of Algorithm 9.3): enlarge the box along whichever face gives the
    largest increase of the box mean, by moving that face out to bring back the max(1, floor(alpha n))
    nearest observations beyond it (with any ties) that satisfy the other bounds; stop when no
    enlargement increases the mean. `active` restricts the data (for later boxes)."""
    X = np.asarray(X, float)
    N, p = X.shape
    act = np.ones(N, bool) if active is None else active
    lo, hi = box["lo"].copy(), box["hi"].copy()
    while True:
        inside = box_inside(X, lo, hi, act)
        n, mean0 = int(inside.sum()), float(y[inside].mean())
        k = _peel_count(n, alpha)
        best = None
        for j in range(p):
            others = act.copy()
            for jj in range(p):
                if jj != j:
                    others &= (X[:, jj] >= lo[jj]) & (X[:, jj] <= hi[jj])
            for side in (0, 1):
                cand = others & ((X[:, j] < lo[j]) if side == 0 else (X[:, j] > hi[j]))
                if not cand.any():
                    continue
                v = np.sort(X[cand, j])
                if side == 0:
                    v = v[::-1]
                nb = v[min(k, len(v)) - 1]
                add = cand & ((X[:, j] >= nb) if side == 0 else (X[:, j] <= nb))
                mean = float(y[inside | add].mean())
                if mean > mean0 + 1e-12 and (best is None or mean > best[0] + 1e-12):
                    best = (mean, j, side, nb)
        if best is None:
            return dict(lo=lo, hi=hi, n=n, mean=mean0, inside=inside)
        _, j, side, nb = best
        if side == 0:
            lo[j] = nb
        else:
            hi[j] = nb


# =========================================================================== MARS (Section 9.4)
def mars_spans(p, n_support, alpha=0.05):
    """Friedman's (1991) minimum spacing between knots (minspan, counted in observations) for a parent
    with n_support nonzero values, and the number of observations kept free of knots at each end."""
    minspan = int(max(1, round(-np.log2(-np.log(1 - alpha) / (p * max(n_support, 1))) / 2.5)))
    endspan = int(max(1, round(3 - np.log2(alpha / p))))
    return minspan, endspan


class MARS:
    """Multivariate adaptive regression splines (Friedman 1991; Section 9.4), written from scratch.

    A basis function is a product of hinge factors (x_v - t)_+ or (t - x_v)_+ (the reflected pairs of
    (9.18)), each input at most once; term 0 is the constant. Forward pass: at each step every product of
    a term already in the model (with fewer than `degree` factors) and a reflected pair on a new input,
    with the knot t at an observed value, is scored by the decrease of the residual sum of squares when the
    pair is added (both coefficients refitted with all the others by least squares); the best pair joins
    the model, until max_terms terms. The score of every knot of one (parent, input) is computed in O(N r)
    operations, r the number of terms, by keeping an orthonormal basis Q of the model and accumulating
    sums along the sorted input (the 'O(1) update per knot' of the book, p. 327). Backward pass: delete,
    one at a time, the term whose removal increases RSS least (RSS increase beta_j^2 / [(B^T B)^-1]_jj),
    giving a nested sequence of models; GCV (9.20) with M = r + c (r - 1)/2 effective parameters (c per
    knot, c = 3, or 2 for an additive model) picks one."""

    def __init__(self, max_terms=21, degree=1, penalty=None, minspan="auto", endspan="auto", tol=1e-9):
        self.max_terms, self.degree = max_terms, degree
        self.penalty = (3.0 if degree > 1 else 2.0) if penalty is None else penalty
        self.minspan, self.endspan, self.tol = minspan, endspan, tol

    @staticmethod
    def term_values(X, term):
        v = np.ones(len(X))
        for (j, t, s) in term:
            v = v * np.maximum(s * (X[:, j] - t), 0.0)
        return v

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

    def _add_column(self, Q, b):
        bt = b - Q @ (Q.T @ b)
        bt = bt - Q @ (Q.T @ bt)
        nb = np.linalg.norm(bt)
        if nb <= 1e-8 * max(np.linalg.norm(b), 1e-300):
            return Q, False
        return np.column_stack([Q, bt / nb]), True

    def fit(self, X, y, verbose=False):
        X = np.asarray(X, float)
        y = np.asarray(y, float)
        N, p = X.shape
        self.p = p
        order = [np.argsort(X[:, j], kind="stable") for j in range(p)]
        es = mars_spans(p, N)[1] if self.endspan == "auto" else int(self.endspan)
        # knots must lie between the es-th smallest and es-th largest value of each input (endspan)
        self._ends = [(X[order[j][min(es, N - 1)], j], X[order[j][max(N - 1 - es, 0)], j]) for j in range(p)]
        terms = [()]
        B = [np.ones(N)]
        Q = np.ones((N, 1)) / np.sqrt(N)
        r = y - Q @ (Q.T @ y)
        self.forward_rss = [float(r @ r)]
        self.forward_steps = []
        while len(terms) < self.max_terms:
            best = None
            for m, term in enumerate(terms):
                if len(term) >= self.degree:
                    continue
                h = B[m]
                used = {f[0] for f in term}
                nz = h != 0
                ns = int(nz.sum())
                if ns < 3:
                    continue
                minspan = mars_spans(p, ns)[0] if self.minspan == "auto" else int(self.minspan)
                for v in range(p):
                    if v in used:
                        continue
                    res = self._score(X[:, v], h, nz, order[v], Q, r, minspan, self._ends[v])
                    if res is not None and (best is None or res[0] > best[0] * (1 + 1e-12)):
                        best = (res[0], m, v, res[1], res[2])
            if best is None or best[0] <= self.tol * self.forward_rss[0]:
                break
            gain, m, v, t, which = best
            added = []
            for s in (1, -1):
                if (s == 1 and which[0]) or (s == -1 and which[1]):
                    term = terms[m] + ((v, t, s),)
                    b = self.term_values(X, term)
                    Q, ok = self._add_column(Q, b)
                    if ok:
                        terms.append(term)
                        B.append(b)
                        added.append(term)
                    if len(terms) >= self.max_terms:
                        break
            if not added:
                break
            r = y - Q @ (Q.T @ y)
            self.forward_rss.append(float(r @ r))
            self.forward_steps.append(dict(parent=m, var=v, knot=t, added=added, rss=float(r @ r)))
            if verbose:
                print("    forward step %2d: parent %d, x%d, knot %.4g, terms %d, RSS %.5g" % (
                    len(self.forward_steps), m, v, t, len(terms), r @ r))
        self.forward_terms = terms
        self.Bfull = np.column_stack(B)
        self._backward(y)
        return self

    def _score(self, x, h, nz, order_v, Q, r, minspan, ends):
        o = order_v[nz[order_v]]
        n = len(o)
        xs, hs = x[o], h[o]
        # candidate knots: the parent's sorted values of x at every minspan-th position, inside the endspan
        # limits of x and below the parent's largest value (so that (x - t)_+ is not identically 0)
        knots = np.unique(xs[np.arange(0, n, minspan)])
        knots = knots[(knots >= ends[0]) & (knots <= ends[1]) & (knots < xs[-1])]
        if len(knots) == 0:
            return None
        U = Q[o] * hs[:, None]
        Ux = U * xs[:, None]
        z = np.zeros((1, U.shape[1]))
        Fc_U, Fc_Ux = np.vstack([z, np.cumsum(U, 0)]), np.vstack([z, np.cumsum(Ux, 0)])
        TU, TUx = Fc_U[-1], Fc_Ux[-1]
        rh = r[o] * hs
        Fr, Frx = np.r_[0, np.cumsum(rh)], np.r_[0, np.cumsum(rh * xs)]
        h2 = hs ** 2
        F0, F1, F2 = np.r_[0, np.cumsum(h2)], np.r_[0, np.cumsum(h2 * xs)], np.r_[0, np.cumsum(h2 * xs ** 2)]
        jr = np.searchsorted(xs, knots, "right")       # x > t from position jr on
        jl = np.searchsorted(xs, knots, "left")        # x < t before position jl
        t = knots[:, None]
        c_plus = (TUx - Fc_Ux[jr]) - t * (TU - Fc_U[jr])           # Q^T b+   (K x r)
        c_minus = t * Fc_U[jl] - Fc_Ux[jl]                          # Q^T b-
        tt = knots
        g_plus = (Frx[-1] - Frx[jr]) - tt * (Fr[-1] - Fr[jr])       # r^T b+
        g_minus = tt * Fr[jl] - Frx[jl]
        n_plus = (F2[-1] - F2[jr]) - 2 * tt * (F1[-1] - F1[jr]) + tt ** 2 * (F0[-1] - F0[jr])
        n_minus = tt ** 2 * F0[jl] - 2 * tt * F1[jl] + F2[jl]
        a11 = n_plus - np.sum(c_plus ** 2, 1)
        a22 = n_minus - np.sum(c_minus ** 2, 1)
        a12 = -np.sum(c_plus * c_minus, 1)
        okp = a11 > 1e-9 * np.maximum(n_plus, 1e-300)
        okm = a22 > 1e-9 * np.maximum(n_minus, 1e-300)
        det = a11 * a22 - a12 ** 2
        both = okp & okm & (det > 1e-9 * np.maximum(a11 * a22, 1e-300))
        with np.errstate(divide="ignore", invalid="ignore"):
            red_both = (a22 * g_plus ** 2 - 2 * a12 * g_plus * g_minus + a11 * g_minus ** 2) / det
            red_p = g_plus ** 2 / a11
            red_m = g_minus ** 2 / a22
        red = np.where(both, red_both, np.where(okp, red_p, np.where(okm, red_m, -np.inf)))
        red = np.where(np.isfinite(red), red, -np.inf)
        k = int(np.argmax(red))
        if not np.isfinite(red[k]) or red[k] <= 0:
            return None
        which = (bool(okp[k]), bool(okm[k])) if both[k] else (bool(okp[k]), bool(okm[k] and not okp[k]))
        return float(red[k]), float(knots[k]), which

    def _backward(self, y):
        B = self.Bfull
        N, M = B.shape
        G = B.T @ B
        By = B.T @ y
        yy = float(y @ y)
        S = list(range(M))
        self.path = []
        while True:
            Gi = np.linalg.pinv(G[np.ix_(S, S)])
            beta = Gi @ By[S]
            rss = max(yy - float(beta @ By[S]), 0.0)
            r = len(S)
            C = r + self.penalty * (r - 1) / 2.0
            gcv = rss / N / (1 - C / N) ** 2 if C < N else np.inf
            self.path.append(dict(terms=list(S), rss=rss, gcv=gcv, beta=beta, C=C))
            if r == 1:
                break
            d = np.diag(Gi)[1:]
            inc = beta[1:] ** 2 / np.where(d > 0, d, np.inf)
            S.pop(1 + int(np.argmin(inc)))
        k = int(np.argmin([q["gcv"] for q in self.path]))
        self.best = self.path[k]
        self.terms = [self.forward_terms[i] for i in self.best["terms"]]
        self.coef = self.best["beta"]

    def predict(self, X, path_index=None):
        sel = self.best if path_index is None else self.path[path_index]
        terms = [self.forward_terms[i] for i in sel["terms"]]
        return self.basis(X, terms) @ sel["beta"]


# =========================================================================== hierarchical mixtures of experts (Section 9.5)
def softmax_rows(A):
    A = A - A.max(1, keepdims=True)
    E = np.exp(A)
    return E / E.sum(1, keepdims=True)


def _weighted_multilogit(X, R, w, Gam, iters=10, ridge=1e-6):
    """M-step for a gating network: maximise sum_i w_i sum_k R_ik log g_k(x_i) over the softmax
    coefficients Gam (p x K, last column fixed at 0) by Newton-Raphson; R are soft targets (rows sum 1)."""
    N, p = X.shape
    K = R.shape[1]
    for _ in range(iters):
        P = softmax_rows(X @ Gam)
        grad = X.T @ (w[:, None] * (R - P))[:, :K - 1]
        H = np.zeros(((K - 1) * p, (K - 1) * p))
        for a in range(K - 1):
            for b in range(K - 1):
                wab = w * P[:, a] * ((a == b) - P[:, b])
                H[a * p:(a + 1) * p, b * p:(b + 1) * p] = X.T @ (wab[:, None] * X)
        H += ridge * np.eye(len(H))
        step = np.linalg.solve(H, grad.T.reshape(-1))
        Gam[:, :K - 1] += step.reshape(K - 1, p).T
        if np.max(np.abs(step)) < 1e-10:
            break
    return Gam


def hme_fit(X, y, K=2, iters=200, seed=0, init=None, tol=1e-10):
    """Two-level hierarchical mixture of linear-Gaussian experts (9.25)-(9.30) fitted by EM.

    X must contain a column of ones. Top gate g_j(x) = softmax(gamma_j^T x), second-level gates
    g_{l|j}(x) = softmax(gamma_{jl}^T x), experts y ~ N(beta_{jl}^T x, sigma_{jl}^2). E-step: posterior
    path probabilities h_{jl} (the expected values of Delta_j Delta_{l|j}); M-step: weighted least squares
    for each expert (weights h_{jl}), and weighted multinomial logistic regressions for the gates with the
    soft targets h_j = sum_l h_{jl} and h_{jl}/h_j (weights h_j). Returns parameters, the log-likelihood
    trace (non-decreasing up to the Newton tolerance of the gate updates) and the responsibilities."""
    X = np.asarray(X, float)
    N, p = X.shape
    rng = np.random.default_rng(seed)
    if init is None:
        G1 = rng.normal(0, 0.5, (p, K)); G1[:, -1] = 0
        G2 = [rng.normal(0, 0.5, (p, K)) for _ in range(K)]
        for g in G2:
            g[:, -1] = 0
        beta = rng.normal(0, 1, (K, K, p))
        sig2 = np.full((K, K), np.var(y))
    else:
        G1, G2, beta, sig2 = [np.array(a, float) if not isinstance(a, list) else [np.array(b, float) for b in a]
                              for a in init]
    trace = []
    for it in range(iters):
        g1 = softmax_rows(X @ G1)
        g2 = [softmax_rows(X @ G2[j]) for j in range(K)]
        logdens = np.zeros((N, K, K))
        for j in range(K):
            for l in range(K):
                mu = X @ beta[j, l]
                logdens[:, j, l] = (np.log(g1[:, j] + 1e-300) + np.log(g2[j][:, l] + 1e-300)
                                    - 0.5 * np.log(2 * np.pi * sig2[j, l]) - 0.5 * (y - mu) ** 2 / sig2[j, l])
        ll_i = common.logsumexp(logdens.reshape(N, -1), axis=1)
        trace.append(float(ll_i.sum()))
        if it > 0 and abs(trace[-1] - trace[-2]) < tol * abs(trace[-1]):
            break
        H = np.exp(logdens - ll_i[:, None, None])                 # E-step: h_{jl}(x_i, y_i)
        hj = H.sum(2)
        for j in range(K):
            for l in range(K):
                w = H[:, j, l]
                A = X.T @ (w[:, None] * X) + 1e-9 * np.eye(p)
                beta[j, l] = np.linalg.solve(A, X.T @ (w * y))
                sig2[j, l] = max(np.sum(w * (y - X @ beta[j, l]) ** 2) / max(w.sum(), 1e-12), 1e-6)
        G1 = _weighted_multilogit(X, hj, np.ones(N), G1)
        for j in range(K):
            G2[j] = _weighted_multilogit(X, H[:, j, :] / np.maximum(hj[:, j:j + 1], 1e-300), hj[:, j], G2[j])
    return dict(G1=G1, G2=G2, beta=beta, sig2=sig2, loglik=trace, H=H)


def hme_predict(fit, X):
    """Mean prediction sum_j g_j sum_l g_{l|j} beta_{jl}^T x, and the gate probabilities."""
    K = fit["beta"].shape[0]
    g1 = softmax_rows(X @ fit["G1"])
    out = np.zeros(len(X))
    for j in range(K):
        g2 = softmax_rows(X @ fit["G2"][j])
        for l in range(K):
            out += g1[:, j] * g2[:, l] * (X @ fit["beta"][j, l])
    return out, g1


# =========================================================================== the spam analyses
_MEMO = {}


def spam_split():
    X, y, te = load_spam()
    return X, y, ~te, te


def theta_of(sp, values):
    """B-spline coefficients of a function given by its values at the observations (it lies in the
    spline space: each backfitted term is a smoothing spline plus a straight line)."""
    v = np.zeros(sp.n)
    v[sp.inv] = values
    return np.linalg.lstsq(sp.Bd.toarray(), v, rcond=None)[0]


def gam_eta(G, Xnew):
    """Additive predictor alpha + sum_j f_j(x_j) of a fitted GAM at new inputs (already transformed)."""
    eta = np.full(len(Xnew), G["alpha"])
    for j, sp in enumerate(G["sps"]):
        eta += sp.curve(G["theta"][j], Xnew[:, j])
    return eta


def spam_gam(df=4, prior_w=None, tag="", verbose=False):
    """The additive logistic regression of Section 9.1.2 on the spam training data: every input
    log-transformed, log(x + 0.1), each term a cubic smoothing spline with trace S_j - 1 = df (recomputed
    under the current weights at every local-scoring step). Returns the fit, the per-term B-spline
    coefficients, the test-set predictor and the final per-term degrees of freedom. Cached."""
    key = ("gam", df, tag)
    if key in _MEMO:
        return _MEMO[key]
    X, y, tr, te = spam_split()
    L = np.log(X + 0.1)
    sps = [SmoothingSpline(L[tr, j]) for j in range(L.shape[1])]
    path = os.path.join(CACHE_DIR, "ch09_spam_gam%s.npz" % tag)
    if os.path.exists(path):
        z = np.load(path)
        fit = dict(alpha=float(z["alpha"]), F=z["F"], lams=z["lams"], weights=z["weights"], deviance=float(z["deviance"]),
                   iters=int(z["iters"]))
    else:
        fit = local_scoring(L[tr], y[tr], sps, df=df, prior_w=None if prior_w is None else prior_w[tr], tol=1e-6,
                            verbose=verbose)
        os.makedirs(CACHE_DIR, exist_ok=True)
        np.savez(path, alpha=fit["alpha"], F=fit["F"], lams=fit["lams"], weights=fit["weights"],
                 deviance=fit["deviance"], iters=fit["iters"])
    theta = [theta_of(sp, fit["F"][:, j]) for j, sp in enumerate(sps)]
    G = dict(fit=fit, sps=sps, theta=theta, alpha=fit["alpha"], L=L, y=y, tr=tr, te=te)
    G["eta_test"] = gam_eta(G, L[te])
    wts = np.maximum(fit["weights"], 1e-10 * fit["weights"].max())
    G["df"] = np.array([sps[j].df(fit["lams"][j], wts) - 1 for j in range(len(sps))])
    _MEMO[key] = G
    return G


def confusion_percent(pred, y):
    """2 x 2 table of percentages: rows true class (email, spam), columns predicted class."""
    T = np.array([[np.sum((y == a) & (pred == b)) for b in (0, 1)] for a in (0, 1)])
    return 100.0 * T / len(y), T


def spam_gam_table(G, alpha_level=0.01):
    """Table 9.2: for every term the linear part of f_j (weighted least-squares slope of the fitted curve
    on x_j, with the final local-scoring weights), its standard error from the weighted least-squares fit
    of all the linear parts, the Z score, and a test of nonlinearity: the increase of the deviance when term
    j alone is made linear (its df set to 1, the other smoothing parameters fixed), referred to chi-squared
    with df_j - 1 degrees of freedom. Rows significant at alpha_level by either test are flagged. Cached."""
    from scipy.stats import chi2, norm
    path = os.path.join(CACHE_DIR, "ch09_spam_gam_table.json")
    fit, sps = G["fit"], G["sps"]
    tr = G["tr"]
    L, y = G["L"][tr], G["y"][tr]
    w = fit["weights"]
    if os.path.exists(path):
        with open(path) as f:
            dev_lin = json.load(f)["dev_lin"]
    else:
        dev_lin = []
        for j in range(L.shape[1]):
            lams = fit["lams"].copy()
            lams[j] = np.inf
            r = local_scoring(L, y, sps, lams=lams, start=dict(alpha=fit["alpha"], F=fit["F"]), tol=1e-8, bf_tol=1e-7)
            dev_lin.append(r["deviance"])
        with open(path, "w") as f:
            json.dump(dict(dev_lin=dev_lin), f)
    D = np.column_stack([np.ones(len(L)), L])
    cov = np.linalg.inv(D.T @ (w[:, None] * D))
    rows = []
    for j in range(L.shape[1]):
        x = L[:, j]
        xm = np.sum(w * x) / w.sum()
        b = np.sum(w * (x - xm) * fit["F"][:, j]) / np.sum(w * (x - xm) ** 2)
        se = float(np.sqrt(cov[j + 1, j + 1]))
        z = b / se
        dd = max(dev_lin[j] - fit["deviance"], 0.0)
        pnl = float(chi2.sf(dd, max(G["df"][j] - 1, 0.5)))
        plin = float(2 * norm.sf(abs(z)))
        rows.append(dict(name=SPAM_NAMES[j], num=j + 1, df=float(G["df"][j]), coef=float(b), se=se, z=float(z),
                         p_lin=plin, dev_change=float(dd), p_nonlin=pnl,
                         significant=bool(plin < alpha_level or pnl < alpha_level)))
    return rows


def spam_linear_models():
    """Test errors of linear logistic regressions on the spam data (Section 9.1.2): on the raw inputs
    (the book's 7.6%) and on the log-transformed inputs; on indicators of a zero frequency for the 54
    frequencies (with the three capital-run inputs); on the indicators together with the inputs."""
    X, y, tr, te = spam_split()
    L = np.log(X + 0.1)
    Z = (X[:, :54] == 0).astype(float)
    out = {}
    for name, A in (("linear_raw", X), ("linear_log", L), ("zero_indicators", np.column_stack([Z, X[:, 54:]])),
                    ("indicators_and_linear_raw", np.column_stack([Z, X])),
                    ("indicators_and_linear_log", np.column_stack([Z, L]))):
        beta = logistic_irls(A[tr], y[tr])
        eta = beta[0] + A[te] @ beta[1:]
        out[name] = float(np.mean((eta > 0) != y[te]))
    return out


def logistic_irls(A, y, w=None, iters=100, ridge=1e-8):
    """Linear logistic regression by iteratively reweighted least squares (Section 4.4.1)."""
    N = len(y)
    D = np.column_stack([np.ones(N), A])
    pw = np.ones(N) if w is None else w
    beta = np.zeros(D.shape[1])
    for _ in range(iters):
        eta = D @ beta
        p = np.clip(expit(eta), 1e-10, 1 - 1e-10)
        W = pw * p * (1 - p)
        z = eta + (y - p) / (p * (1 - p))
        new = np.linalg.solve(D.T @ (W[:, None] * D) + ridge * np.eye(D.shape[1]), D.T @ (W * z))
        if np.max(np.abs(new - beta)) < 1e-10:
            beta = new
            break
        beta = new
    return beta


def spam_tree(seed=TREE_SEED):
    """The classification tree of Section 9.2.5: grown on the training data with the deviance (minimum
    node size 10, children of at least 5, node deviance at least 1% of the root's), pruned by
    misclassification cost-complexity; 10-fold cross-validation indexed by alpha (geometric midpoints of
    the breakpoints), with the folds drawn by numpy default_rng(seed). Memoised."""
    key = ("tree", seed)
    if key in _MEMO:
        return _MEMO[key]
    X, y, tr, te = spam_split()
    T = Tree().grow(X[tr], y[tr])
    seq = T.prune_sequence()
    al = np.array([a for a, _, _ in seq])
    sizes = np.array([s for _, _, s in seq])
    mids = np.r_[0.0, np.sqrt(al[1:-1] * al[2:]), al[-1] + 1.0]
    folds = np.random.default_rng(seed).permutation(np.arange(tr.sum()) % 10)
    E = cv_tree(X[tr], y[tr], folds, mids)
    nf = np.bincount(folds)
    cv = E.sum(0) / tr.sum()
    se = (E / nf[:, None]).std(0, ddof=1) / np.sqrt(10)
    test = np.array([np.mean(T.predict(X[te], m) != y[te]) for _, m, _ in seq])
    train = np.array([np.mean(T.predict(X[tr], m) != y[tr]) for _, m, _ in seq])
    kmin = int(np.argmin(cv))
    k1se = int(np.max(np.where(cv <= cv[kmin] + se[kmin])[0]))      # smallest tree within one SE
    R = dict(T=T, seq=seq, alphas=al, sizes=sizes, mids=mids, folds=folds, cv=cv, se=se, test=test, train=train,
             kmin=kmin, k1se=k1se, X=X, y=y, tr=tr, te=te)
    _MEMO[key] = R
    return R


def spam_weighted_tree(L01=5.0, size=17):
    """The tree grown with observation weights L01 for email (class 0) and 1 for spam, pruned to `size`
    leaves by weighted misclassification cost-complexity (Section 9.2.5)."""
    X, y, tr, te = spam_split()
    w = np.where(y[tr] == 0, L01, 1.0)
    T = Tree().grow(X[tr], y[tr], w)
    return T, T.subtree_size(size)


def leaf_scores(T, act, X):
    """Training proportion of class 1 in the leaf reached by each row of X (unweighted counts)."""
    leaf = T.leaf_of(X, act)
    cnt = np.array([np.bincount(T.y[r], minlength=2) for r in T.rows], float)
    return cnt[leaf, 1] / cnt[leaf].sum(1)


def surrogate_splits(T, node, k=3):
    """Surrogate splits for an internal node (Section 9.2.4): for every other input the split x_j < s or
    x_j >= s that sends the most training observations of the node the same way as the primary split,
    ranked by that agreement; the baseline is the majority direction."""
    idx = T.rows[node]
    X = T.X[idx]
    goes_left = X[:, T.var[node]] < T.thr[node]
    base = max(goes_left.mean(), 1 - goes_left.mean())
    out = []
    for j in range(T.p):
        if j == T.var[node]:
            continue
        o = np.argsort(X[:, j], kind="stable")
        xs, gl = X[o, j], goes_left[o]
        n = len(o)
        cl = np.r_[0, np.cumsum(gl)]                 # number going left among the first i
        i = np.arange(1, n)
        ok = xs[1:] > xs[:-1]
        if not ok.any():
            continue
        agree_lt = (cl[i] + ((n - i) - (cl[n] - cl[i]))) / n          # x_j < s sends left
        agree_ge = ((i - cl[i]) + (cl[n] - cl[i])) / n                # x_j < s sends right
        a1 = np.where(ok, agree_lt, -1)
        a2 = np.where(ok, agree_ge, -1)
        if a1.max() >= a2.max():
            ii = int(np.argmax(a1)); out.append((float(a1[ii]), j, 0.5 * (xs[ii] + xs[ii + 1]), "<"))
        else:
            ii = int(np.argmax(a2)); out.append((float(a2[ii]), j, 0.5 * (xs[ii] + xs[ii + 1]), ">="))
    out.sort(key=lambda r: -r[0])
    return base, out[:k]


def tree_instability(B=100, seed=0):
    """Instability of trees (Section 9.2.4): grow the spam tree on B bootstrap samples of the training
    data and record the root split, the variables of the two second-level splits and the test error of
    the 17-leaf pruned member."""
    X, y, tr, te = spam_split()
    Xt, yt = X[tr], y[tr]
    rng = np.random.default_rng(seed)
    roots, second, errs, sizes = [], [], [], []
    for b in range(B):
        i = rng.integers(0, len(yt), len(yt))
        T = Tree().grow(Xt[i], yt[i])
        roots.append((SPAM_NAMES[T.var[0]], round(float(T.thr[0]), 4)))
        second.append(tuple(SPAM_NAMES[T.var[c]] if T.var[c] >= 0 else "-" for c in (T.left[0], T.right[0])))
        act = T.subtree_size(17)
        errs.append(float(np.mean(T.predict(X[te], act) != y[te])))
    return dict(roots=roots, second=second, errs=np.array(errs))


def prim_cv_curve(X, y, alpha=0.1, min_count=10, folds=None, grid=None):
    """Cross-validated box mean along the peeling sequence: for each fold, peel on the other folds and
    record the mean of y over the held-out observations in the box whose training support is closest
    to each support level of `grid`."""
    K = folds.max() + 1
    out = np.full((K, len(grid)), np.nan)
    cnt = np.zeros((K, len(grid)))
    for f in range(K):
        trn, hold = folds != f, folds == f
        bx = prim_peel(X[trn], y[trn], alpha, min_count)
        sup = np.array([b["n"] for b in bx]) / trn.sum()
        for g, s in enumerate(grid):
            b = bx[int(np.argmin(np.abs(sup - s)))]
            ins = box_inside(X[hold], b["lo"], b["hi"])
            if ins.any():
                out[f, g] = np.mean(y[hold][ins])
                cnt[f, g] = ins.sum()
    with np.errstate(invalid="ignore"):
        mean = np.nansum(out * cnt, 0) / cnt.sum(0)
    return mean, out


def prim_box_rules(X, y, box, names):
    """The rules of a box, ordered by importance: the drop of the box mean when the bound is removed."""
    rules = []
    base = y[box_inside(X, box["lo"], box["hi"])].mean()
    for j in range(X.shape[1]):
        for side, b in ((0, box["lo"][j]), (1, box["hi"][j])):
            if not np.isfinite(b):
                continue
            lo, hi = box["lo"].copy(), box["hi"].copy()
            if side == 0:
                lo[j] = -np.inf
            else:
                hi[j] = np.inf
            drop = base - y[box_inside(X, lo, hi)].mean()
            rules.append((float(drop), names[j], ">=" if side == 0 else "<=", float(b)))
    rules.sort(key=lambda r: -r[0])
    return rules


def spam_prim(alpha=0.1, min_count=10, target=PRIM_TARGET, seed=PRIM_SEED):
    """PRIM on the spam data (Section 9.3), response 1 for spam. Box 1: peel the training data, paste,
    and choose the largest box of the peeling sequence whose 10-fold cross-validated box mean is at least
    `target`; box 2: the same on the training data left outside box 1. Memoised."""
    key = ("prim", alpha, target)
    if key in _MEMO:
        return _MEMO[key]
    X, y, tr, te = spam_split()
    yf = y.astype(float)
    Xt, yt = X[tr], yf[tr]
    active = np.ones(len(yt), bool)
    out = []
    for b in range(2):
        bx = prim_peel(Xt, yt, alpha, min_count, inside=active)
        sup = np.array([q["n"] for q in bx]) / active.sum()
        idx = np.where(active)[0]
        folds = np.random.default_rng(seed + b).permutation(np.arange(len(idx)) % 10)
        cvm, _ = prim_cv_curve(Xt[idx], yt[idx], alpha, min_count, folds, sup)
        ok = np.where(cvm >= target)[0]
        k = int(ok.min()) if len(ok) else int(np.nanargmax(cvm))
        box = prim_paste(Xt, yt, bx[k], alpha=0.01, active=active)
        ins_tr = box_inside(Xt, box["lo"], box["hi"], active)
        prev_te = np.ones(te.sum(), bool) if b == 0 else ~out[0]["in_test"]
        ins_te = box_inside(X[te], box["lo"], box["hi"]) & prev_te
        out.append(dict(seq=bx, cv=cvm, k=k, box=box, rules=prim_box_rules(Xt[active], yt[active], box, SPAM_NAMES),
                        remain_mean_train=float(yt[active].mean()), remain_mean_test=float(yf[te][prev_te].mean()),
                        mean_train=float(yt[ins_tr].mean()), mean_test=float(yf[te][ins_te].mean()),
                        support_train=float(ins_tr.mean()), support_test=float(ins_te.mean()), in_test=ins_te))
        active = active & ~ins_tr
    _MEMO[key] = out
    return out


def spam_mars(degree=2, max_terms=101, log_inputs=False):
    """MARS on the spam data (Section 9.4.1), squared-error loss on the 0/1 response, interactions of
    degree 2, a forward pass to max_terms terms, backward deletion; test misclassification (threshold 1/2)
    along the backward sequence. The forward pass takes about two minutes; the result is cached."""
    tag = "_log" if log_inputs else ""
    path = os.path.join(CACHE_DIR, "ch09_spam_mars%s.json" % tag)
    X, y, tr, te = spam_split()
    A = np.log(X + 0.1) if log_inputs else X
    if os.path.exists(path):
        with open(path) as f:
            R = json.load(f)
        R["forward_terms"] = [tuple(tuple(fct) for fct in t) for t in R["forward_terms"]]
        return R
    M = MARS(max_terms=max_terms, degree=degree).fit(A[tr], y[tr].astype(float))
    rank, err, gcv = [], [], []
    for i, q in enumerate(M.path):
        rank.append(len(q["terms"]))
        err.append(float(np.mean((M.predict(A[te], i) > 0.5) != y[te])))
        gcv.append(float(q["gcv"]))
    best = [M.forward_terms[i] for i in M.best["terms"]]
    R = dict(rank=rank, err=err, gcv=gcv, best_rank=len(best), forward_terms=[list(map(list, t)) for t in M.forward_terms],
             best_terms=M.best["terms"], interactions=[[SPAM_NAMES[t[0][0]], SPAM_NAMES[t[1][0]]] for t in best if len(t) == 2])
    os.makedirs(CACHE_DIR, exist_ok=True)
    with open(path, "w") as f:
        json.dump(R, f)
    return R


# =========================================================================== simulations
def mars_scenarios(n_sims=50, N=100, n_test=1000, seed=MARS_SIM_SEED):
    """Table 9.4: proportional decrease in model error R^2 (9.24) of MARS (degree 2) in the three
    scenarios (9.21)-(9.22), n_sims simulations each; returns mean, standard error and the values."""
    rng = np.random.default_rng(seed)

    def mu(X, sc):
        if sc < 3:
            return np.maximum(X[:, 0] - 1, 0) + np.maximum(X[:, 0] - 1, 0) * np.maximum(X[:, 1] - 0.8, 0)
        s = lambda t: 1 / (1 + np.exp(-t))
        return s(X[:, :5].sum(1)) + s(X[:, 5] - X[:, 6] + X[:, 7] - X[:, 8] + X[:, 9])
    out = {}
    for sc, p in ((1, 2), (2, 20), (3, 10)):
        R = []
        for _ in range(n_sims):
            X, Xt = rng.normal(size=(N, p)), rng.normal(size=(n_test, p))
            y = mu(X, sc) + 0.12 * rng.normal(size=N)
            M = MARS(max_terms=max(21, 2 * p + 1), degree=2).fit(X, y)
            mse = np.mean((M.predict(Xt) - mu(Xt, sc)) ** 2)
            mse0 = np.mean((y.mean() - mu(Xt, sc)) ** 2)
            R.append((mse0 - mse) / mse0)
        R = np.array(R)
        out[sc] = dict(mean=float(R.mean()), se=float(R.std(ddof=1) / np.sqrt(n_sims)), median=float(np.median(R)),
                       values=R.tolist())
    return out


def tree_df_simulation(sizes=(1, 5, 10), reps=10, N=100, p=10, seed=TREEDF_SEED):
    """Exercise 9.5: degrees of freedom sum_i cov(y_i, yhat_i)/sigma^2 of regression trees with a fixed
    number of leaves (grown best-first), for fixed Gaussian inputs and pure-noise responses (sigma = 1),
    estimated from `reps` simulated response vectors: df = sum_i ave_r (yhat_ri - mean)(y_ri - mean)."""
    rng = np.random.default_rng(seed)
    X = rng.normal(size=(N, p))
    Y = rng.normal(size=(reps, N))
    out = {}
    for m in sizes:
        Yh = np.array([Tree(task="reg", mindev=0.0, max_leaves=m).grow(X, Y[r]).predict(X) for r in range(reps)])
        cov = np.sum(np.mean((Yh - Yh.mean(0)) * (Y - Y.mean(0)), 0)) * reps / (reps - 1)
        out[m] = float(cov)
    return out


def tree_df_ye(m, X, y, tau=0.5, R=200, seed=0):
    """Exercise 9.5(e): an approximate smoother matrix for a regression tree of m leaves, by perturbing the
    response (y + delta, delta ~ N(0, tau^2 I)) and regressing each fitted value on the perturbations
    (Ye 1998); returns trace(S_hat) and the trace of the fixed-partition projection (= m)."""
    rng = np.random.default_rng(seed)
    N = len(y)
    D = tau * rng.normal(size=(R, N))
    Yh = np.array([Tree(task="reg", mindev=0.0, max_leaves=m).grow(X, y + D[r]).predict(X) for r in range(R)])
    Dc, Yc = D - D.mean(0), Yh - Yh.mean(0)
    slopes = np.sum(Dc * Yc, 0) / np.sum(Dc ** 2, 0)
    leaf = Tree(task="reg", mindev=0.0, max_leaves=m).grow(X, y).leaf_of(X)
    return float(slopes.sum()), int(len(np.unique(leaf)))


# =========================================================================== figures
BOOK_GAM_TERMS = ["our", "over", "remove", "internet", "free", "business", "hp", "hpl", "george", "1999", "re",
                  "edu", "ch!", "ch$", "CAPMAX", "CAPTOT"]


def fig_9_1(out_dir=None):
    """Spam: the fitted functions of the additive logistic regression for 16 predictors."""
    import matplotlib.pyplot as plt
    G = spam_gam(verbose=True)
    X, y, tr, te = spam_split()
    fig, axes = common.panel_grid(4, 4, size=(2.25, 2.0))
    for a, name in zip(axes.ravel(), BOOK_GAM_TERMS):
        j = SPAM_NAMES.index(name)
        xr = X[tr, j]
        grid = np.linspace(0, xr.max(), 400)
        f = G["sps"][j].curve(G["theta"][j], np.log(grid + 0.1))
        a.plot(grid, f, color=BLUE, lw=1.4)
        a.vlines(np.unique(xr), 0.0, 0.05, color=ORANGE, lw=0.5, transform=a.get_xaxis_transform())
        lo, hi = f.min(), f.max()
        pad = max(1.0, 0.15 * (hi - lo))
        a.set_ylim(min(lo - pad, -2), max(hi + pad, 2))
        a.set_xlabel(name, fontsize=9)
        a.set_ylabel(r"$\hat f$(%s)" % name.replace("$", r"\$"), fontsize=9)
    fig.tight_layout()
    savefig(fig, CH, "fig9-1", out_dir)
    pred = (G["eta_test"] > 0).astype(int)
    P, T = confusion_percent(pred, y[te])
    print("  local scoring: %d iterations, deviance %.3f; per-term df (trace S - 1) from %.2f to %.2f"
          % (G["fit"]["iters"], G["fit"]["deviance"], G["df"].min(), G["df"].max()))
    print("  Table 9.1 (rows true email/spam, columns predicted; %% of the 1536 test messages):", P.round(1).tolist(),
          "counts", T.tolist(), "test error %.4f" % np.mean(pred != y[te]))
    print("  linear logistic regressions:", {k: round(v, 4) for k, v in spam_linear_models().items()})
    p = expit(G["eta_test"])
    for lab, pr in (("threshold 10/11", (p > 10 / 11).astype(int)),):
        print("  %s: email error %.4f, spam error %.4f" % (lab, np.mean(pr[y[te] == 0] == 1), np.mean(pr[y[te] == 1] == 0)))
    Gw = spam_gam(prior_w=np.where(y == 0, 10.0, 1.0), tag="_w10")
    pw = (Gw["eta_test"] > 0).astype(int)
    print("  weights 10 on email, threshold 1/2: email error %.4f, spam error %.4f"
          % (np.mean(pw[y[te] == 0] == 1), np.mean(pw[y[te] == 1] == 0)))
    rows = spam_gam_table(G)
    print("  Table 9.2 (significant at 0.01 by the linear or the nonlinear test):")
    for r in rows:
        if r["significant"]:
            print("    %-8s %2d  df %.1f  coef %7.3f  se %.3f  Z %7.3f  nonlinear P %.3f"
                  % (r["name"], r["num"], r["df"], r["coef"], r["se"], r["z"], r["p_nonlin"]))
    return G


def fig_9_2(out_dir=None):
    """Partitions and CART: a general partition, a recursive binary partition, its tree and the surface."""
    import matplotlib.pyplot as plt
    from matplotlib.patches import Rectangle
    t1, t2, t3, t4 = 0.4, 0.35, 0.6, 0.65
    c = {1: -5, 2: -7, 3: 0, 4: 2, 5: 4}
    fig = plt.figure(figsize=(8.2, 7.6))
    a = fig.add_subplot(2, 2, 1)
    # a partition into boxes that no sequence of binary splits produces (a 'pinwheel')
    for (x0, y0, x1, y1) in [(0.0, 0.0, 0.6, 0.35), (0.6, 0.0, 1.0, 0.6), (0.4, 0.6, 1.0, 1.0), (0.0, 0.35, 0.4, 1.0),
                             (0.4, 0.35, 0.6, 0.6)]:
        a.add_patch(Rectangle((x0, y0), x1 - x0, y1 - y0, fill=False, lw=1.0))
    a.set_xlim(0, 1); a.set_ylim(0, 1); a.set_xticks([]); a.set_yticks([])
    a.set_xlabel("$X_1$"); a.set_ylabel("$X_2$")
    b = fig.add_subplot(2, 2, 2)
    b.plot([t1, t1], [0, 1], "k", lw=1); b.plot([0, t1], [t2, t2], "k", lw=1); b.plot([t3, t3], [0, 1], "k", lw=1)
    b.plot([t3, 1], [t4, t4], "k", lw=1)
    for lab, (x, y) in {"$R_1$": (t1 / 2, t2 / 2), "$R_2$": (t1 / 2, (1 + t2) / 2), "$R_3$": ((t1 + t3) / 2, 0.5),
                        "$R_4$": ((t3 + 1) / 2, t4 / 2), "$R_5$": ((t3 + 1) / 2, (1 + t4) / 2)}.items():
        b.text(x, y, lab, ha="center", va="center")
    b.set_xlim(0, 1); b.set_ylim(0, 1)
    b.set_xticks([t1, t3]); b.set_xticklabels(["$t_1$", "$t_3$"]); b.set_yticks([t2]); b.set_yticklabels(["$t_2$"])
    b.text(1.02, t4, "$t_4$", va="center", transform=b.get_yaxis_transform())
    b.set_xlabel("$X_1$"); b.set_ylabel("$X_2$")
    d = fig.add_subplot(2, 2, 3)
    d.axis("off")
    nodes = {"r": (0.5, 0.92), "a": (0.25, 0.65), "b": (0.72, 0.65), "c": (0.85, 0.38)}
    leaves = {"$R_1$": (0.12, 0.38), "$R_2$": (0.38, 0.38), "$R_3$": (0.58, 0.38), "$R_4$": (0.74, 0.1), "$R_5$": (0.96, 0.1)}
    labels = {"r": r"$X_1\leq t_1$", "a": r"$X_2\leq t_2$", "b": r"$X_1\leq t_3$", "c": r"$X_2\leq t_4$"}
    kids = {"r": ("a", "b"), "a": ("$R_1$", "$R_2$"), "b": ("$R_3$", "c"), "c": ("$R_4$", "$R_5$")}
    pos = dict(nodes, **leaves)
    for k, (l, r) in kids.items():
        x, y = pos[k]
        for ch in (l, r):
            xc, yc = pos[ch]
            d.plot([x, x, xc, xc], [y - 0.04, y - 0.08, y - 0.08, yc + 0.03], "k", lw=1)
        d.text(x, y, labels[k], ha="center", va="bottom", fontsize=10)
    for k, (x, y) in leaves.items():
        d.text(x, y, k, ha="center", va="top", fontsize=10)
    d.set_xlim(0, 1.05); d.set_ylim(0, 1)
    e = fig.add_subplot(2, 2, 4, projection="3d")
    g = np.linspace(0, 1, 61)
    X1, X2 = np.meshgrid(g, g)
    Z = np.where(X1 <= t1, np.where(X2 <= t2, c[1], c[2]), np.where(X1 <= t3, c[3], np.where(X2 <= t4, c[4], c[5])))
    e.plot_surface(X1, X2, Z, cmap="cool", rstride=1, cstride=1, linewidth=0, antialiased=False, alpha=0.95)
    e.set_xlabel("$X_1$"); e.set_ylabel("$X_2$"); e.set_zticks([])
    e.set_xticks([]); e.set_yticks([])
    e.view_init(elev=28, azim=-120)
    fig.tight_layout()
    savefig(fig, CH, "fig9-2", out_dir)


def fig_9_3(out_dir=None):
    """Node impurity measures for two classes as functions of the class-2 proportion p."""
    import matplotlib.pyplot as plt
    p = np.linspace(0, 1, 501)
    with np.errstate(divide="ignore", invalid="ignore"):
        ent = -np.where(p > 0, p * np.log(p), 0) - np.where(p < 1, (1 - p) * np.log(1 - p), 0)
    fig, ax = plt.subplots(figsize=(5.2, 3.8))
    ax.plot(p, ent / (2 * np.log(2)), color=RED, label="Entropy (scaled)")
    ax.plot(p, 2 * p * (1 - p), color=GREEN, label="Gini index")
    ax.plot(p, 1 - np.maximum(p, 1 - p), color=BLUE, label="Misclassification error")
    ax.set_xlabel("$p$"); ax.set_ylim(0, 0.52)
    ax.legend(frameon=False)
    fig.tight_layout()
    savefig(fig, CH, "fig9-3", out_dir)


def fig_9_4(out_dir=None):
    """Spam: 10-fold CV and test misclassification rate against the size of the pruned tree."""
    import matplotlib.pyplot as plt
    R = spam_tree()
    s, cv, se, test = R["sizes"], R["cv"], R["se"], R["test"]
    fig, ax = plt.subplots(figsize=(6.0, 4.3))
    ax.errorbar(s, cv, yerr=se, fmt="o-", color=BLUE, ms=3.5, lw=1.2, capsize=2.5, label="10-fold cross-validation")
    ax.plot(s, test, "o-", color=ORANGE, ms=3, lw=1.2, label="test error")
    ax.axhline(cv[R["kmin"]] + se[R["kmin"]], color=GREY, lw=0.8, ls=":")
    ax.set_xlabel("Tree size (number of terminal nodes)"); ax.set_ylabel("Misclassification rate")
    ax.set_ylim(0, 0.42)
    top = ax.secondary_xaxis("top")
    keep = [k for k in range(len(s)) if R["alphas"][k] in (0, 2, 3, 5, 7, 21, 176)]
    top.set_xticks([s[k] for k in keep])
    top.set_xticklabels(["%g" % R["alphas"][k] for k in keep], fontsize=8)
    top.set_xlabel(r"$\alpha$")
    ax.legend(frameon=False, loc="upper right")
    fig.tight_layout()
    savefig(fig, CH, "fig9-4", out_dir)
    print("  pruning sequence (alpha: size):", ", ".join("%g: %d" % (a, n) for a, n in zip(R["alphas"], s)))
    print("  CV minimum at %d leaves (%.4f +- %.4f); one-SE rule: %d leaves" % (s[R["kmin"]], cv[R["kmin"]], se[R["kmin"]],
                                                                          s[R["k1se"]]))
    k17 = list(s).index(17)
    print("  17 leaves: CV %.4f, test %.4f, training %.4f" % (cv[k17], test[k17], R["train"][k17]))


def _draw_tree(ax, T, act, Xte, yte, names, classes=("email", "spam")):
    reach = T._reachable(act)
    kids = {k: (T.left[k], T.right[k]) for k in range(T.n_nodes) if act[k] and reach[k]}
    order = []

    def walk(k):
        if k in kids:
            walk(kids[k][0]); walk(kids[k][1])
        else:
            order.append(k)
    walk(0)
    xpos = {k: i for i, k in enumerate(order)}

    def place(k):
        if k in kids:
            xpos[k] = 0.5 * (place(kids[k][0]) + place(kids[k][1]))
        return xpos[k]
    place(0)
    leaf_te = T.leaf_of(Xte, act)
    # test-set membership of every node: an observation is in node k if k is on its path
    member = {}
    for k in range(T.n_nodes):
        if reach[k]:
            member[k] = np.zeros(len(Xte), bool)
    node = np.zeros(len(Xte), int)
    member[0][:] = True
    for _ in range(T.depth.max() + 1):
        inn = np.array([kk in kids for kk in node])
        if not inn.any():
            break
        ii = np.where(inn)[0]
        k = node[ii]
        gl = Xte[ii, T.var[k]] < T.thr[k]
        node[ii] = np.where(gl, T.left[k], T.right[k])
        for i, kk in zip(ii, node[ii]):
            member[kk][i] = True
    col = {0: GREEN, 1: RED}
    for k in xpos:
        x, yv = xpos[k], -T.depth[k]
        if k in kids:
            for side, ch in enumerate(kids[k]):
                xc, yc = xpos[ch], -T.depth[ch]
                ax.plot([x, xc], [yv, yc], color="k", lw=0.6, zorder=1)
                v, t = names[T.var[k]], T.thr[k]
                lab = "%s%s%.4g" % (v, "<" if side == 0 else ">", t)
                ax.text(0.35 * x + 0.65 * xc + (-0.08 if side == 0 else 0.08), 0.35 * yv + 0.65 * yc + 0.12, lab, color=BLUE,
                        fontsize=5.4, ha="right" if side == 0 else "left", va="center")
        cls = T.pred[k]
        m = member[k]
        err = int(np.sum(m & (yte != cls)))
        ax.text(x, yv, classes[cls], color=col[cls], fontsize=6.2, ha="center", va="center", zorder=3,
                bbox=dict(boxstyle="round,pad=0.25" if k in kids else "square,pad=0.25", fc="white", ec=col[cls], lw=0.6))
        ax.text(x, yv - 0.32, "%d/%d" % (err, int(m.sum())), fontsize=5.6, ha="center", va="center", zorder=3)
    ax.set_xlim(-0.8, len(order) - 0.2)
    ax.set_ylim(-T.depth[list(xpos)].max() - 0.7, 0.5)
    ax.axis("off")


def fig_9_5(out_dir=None):
    """Spam: the 17-leaf pruned tree, with test misclassifications in every node."""
    import matplotlib.pyplot as plt
    R = spam_tree()
    T = R["T"]
    act = T.subtree_size(17, R["seq"])
    fig, ax = plt.subplots(figsize=(10.0, 6.4))
    _draw_tree(ax, T, act, R["X"][R["te"]], R["y"][R["te"]], SPAM_NAMES)
    fig.tight_layout()
    savefig(fig, CH, "fig9-5", out_dir)
    pred = T.predict(R["X"][R["te"]], act)
    P, C = confusion_percent(pred, R["y"][R["te"]])
    print("  Table 9.3 (17-leaf tree, % of test messages):", P.round(1).tolist(), "error %.4f" % np.mean(pred != R["y"][R["te"]]))
    print("  sensitivity %.4f, specificity %.4f" % (C[1, 1] / C[1].sum(), C[0, 0] / C[0].sum()))
    base, sur = surrogate_splits(T, 0)
    print("  surrogates for the root split (majority rule %.4f):" % base,
          ["%s %s %.4g (%.4f)" % (SPAM_NAMES[j], s, t, a) for a, j, t, s in sur])


def fig_9_6(out_dir=None):
    """Spam: ROC curves of the 17-leaf tree, the additive logistic model and the weighted tree."""
    import matplotlib.pyplot as plt
    R = spam_tree()
    X, y, tr, te = spam_split()
    T = R["T"]
    act = T.subtree_size(17, R["seq"])
    sc_tree = leaf_scores(T, act, X[te])
    G = spam_gam()
    sc_gam = G["eta_test"]
    Tw, actw = spam_weighted_tree()
    sc_w = leaf_scores(Tw, actw, X[te])
    fig, ax = plt.subplots(figsize=(5.4, 5.0))
    res = {}
    for lab, sc, col in (("Tree", sc_tree, GREEN), ("GAM", sc_gam, CYAN), ("Weighted Tree", sc_w, ORANGE)):
        sens, spec, auc = roc_points(sc, y[te])
        res[lab] = auc
        ax.plot(spec, sens, "-", color=col, lw=1.3, label="%s (%.2f)" % (lab, auc))
        if lab != "GAM":
            ax.plot(spec, sens, "o", color=col, ms=2.5)
    ax.set_xlim(-0.02, 1.02); ax.set_ylim(-0.02, 1.02)
    ax.set_xlabel("Specificity"); ax.set_ylabel("Sensitivity")
    ax.legend(frameon=False, loc="center left")
    fig.tight_layout()
    savefig(fig, CH, "fig9-6", out_dir)
    print("  areas under the ROC curves:", {k: round(v, 4) for k, v in res.items()},
          "Mann-Whitney check (GAM): %.4f" % auc_mann_whitney(sc_gam, y[te]))
    pw = Tw.predict(X[te], actw)
    print("  weighted tree (17 leaves) at its own Bayes rule: email error %.4f, spam error %.4f"
          % (np.mean(pw[y[te] == 0] == 1), np.mean(pw[y[te] == 1] == 0)))


def prim_example(seed=PRIM_SIM_SEED):
    """The 200 points of Figure 9.7: uniform on the unit square, y = 1 inside (0.5, 0.8) x (0.4, 0.6)."""
    rng = np.random.default_rng(seed)
    X = rng.uniform(size=(200, 2))
    y = ((X[:, 0] > 0.5) & (X[:, 0] < 0.8) & (X[:, 1] > 0.4) & (X[:, 1] < 0.6)).astype(float)
    return X, y


def fig_9_7(out_dir=None):
    """PRIM: the boxes found by top-down peeling (alpha = 0.1) at 12 stages."""
    import matplotlib.pyplot as plt
    from matplotlib.patches import Rectangle
    X, y = prim_example()
    boxes = prim_peel(X, y, alpha=0.1, min_count=10)
    stages = [1, 2, 3, 4, 5, 6, 7, 8, 12, 17, 22, len(boxes) - 1]
    fig, axes = common.panel_grid(3, 4, size=(2.0, 2.0))
    for a, k in zip(axes.ravel(), stages):
        b = boxes[k]
        a.scatter(X[y == 0, 0], X[y == 0, 1], s=9, facecolors="none", edgecolors=BLUE, lw=0.6)
        a.scatter(X[y == 1, 0], X[y == 1, 1], s=9, facecolors="none", edgecolors=RED, lw=0.6)
        lo = np.where(np.isfinite(b["lo"]), b["lo"], 0.0)
        hi = np.where(np.isfinite(b["hi"]), b["hi"], 1.0)
        a.add_patch(Rectangle((lo[0], lo[1]), hi[0] - lo[0], hi[1] - lo[1], fill=False, ls="--", lw=1.3, color="k"))
        a.set_xlim(-0.02, 1.02); a.set_ylim(-0.02, 1.02); a.set_xticks([]); a.set_yticks([])
        a.set_title(str(k), fontsize=9)
    fig.tight_layout()
    savefig(fig, CH, "fig9-7", out_dir)
    print("  %d peels; final box %s x %s with %d points, mean %.3f" % (len(boxes) - 1, np.round([boxes[-1]["lo"][0], boxes[-1]["hi"][0]], 3),
                                                              np.round([boxes[-1]["lo"][1], boxes[-1]["hi"][1]], 3), boxes[-1]["n"], boxes[-1]["mean"]))


def fig_9_8(out_dir=None):
    """PRIM: box mean against the number of observations in the box, along the peeling sequence."""
    import matplotlib.pyplot as plt
    X, y = prim_example()
    boxes = prim_peel(X, y, alpha=0.1, min_count=10)
    fig, ax = plt.subplots(figsize=(5.0, 3.6))
    ax.plot([b["n"] for b in boxes], [b["mean"] for b in boxes], "o", color=ORANGE, ms=4)
    ax.set_xlabel("Number of observations in box"); ax.set_ylabel("Box mean")
    fig.tight_layout()
    savefig(fig, CH, "fig9-8", out_dir)


def fig_9_9(out_dir=None):
    """The MARS reflected pair (x - t)_+ and (t - x)_+ with t = 0.5."""
    import matplotlib.pyplot as plt
    x = np.linspace(0, 1, 201)
    fig, ax = plt.subplots(figsize=(4.6, 3.0))
    ax.plot(x, np.maximum(x - 0.5, 0), color=ORANGE, label="$(x-t)_+$")
    ax.plot(x, np.maximum(0.5 - x, 0), "--", color=BLUE, label="$(t-x)_+$")
    ax.set_xticks([0, 0.5, 1]); ax.set_xticklabels(["0", "$t$", "1"])
    ax.set_xlabel("$x$"); ax.set_ylabel("Basis function"); ax.set_ylim(-0.02, 0.6)
    ax.legend(frameon=False, loc="upper center")
    fig.tight_layout()
    savefig(fig, CH, "fig9-9", out_dir)


def fig_9_11(out_dir=None):
    """The product h(X1, X2) = (X1 - x51)_+ (x72 - X2)_+ of two MARS hinge functions."""
    import matplotlib.pyplot as plt
    g = np.linspace(0, 1, 41)
    X1, X2 = np.meshgrid(g, g)
    a, b = 0.55, 0.6
    Z = np.maximum(X1 - a, 0) * np.maximum(b - X2, 0)
    fig = plt.figure(figsize=(5.4, 4.4))
    ax = fig.add_subplot(1, 1, 1, projection="3d")
    ax.plot_surface(X1, X2, Z, cmap="cool", rstride=1, cstride=1, linewidth=0.2, edgecolor="k", alpha=0.95)
    ax.set_xlabel("$X_1$"); ax.set_ylabel("$X_2$"); ax.set_zlabel("$h(X_1,X_2)$")
    ax.set_xticks([]); ax.set_yticks([]); ax.set_zticks([])
    ax.view_init(elev=25, azim=-130)
    fig.tight_layout()
    savefig(fig, CH, "fig9-11", out_dir)


def fig_9_12(out_dir=None):
    """Spam: test misclassification of MARS against the rank of the model along the backward pass."""
    import matplotlib.pyplot as plt
    R = spam_mars(log_inputs=True)
    fig, ax = plt.subplots(figsize=(5.6, 3.8))
    ax.plot(R["rank"], R["err"], "o", color=GREEN, ms=2.6)
    ax.axvline(R["best_rank"], color="k", lw=0.8)
    ax.text(R["best_rank"], 0.12, "GCV choice", ha="center", fontsize=9, bbox=dict(fc="white", ec="none"))
    lev = float(np.mean([e for r, e in zip(R["rank"], R["err"]) if r >= 50]))
    ax.axhline(lev, color=BLUE, lw=0.8, ls=":")
    ax.text(1, lev, "%.3f" % lev, color=BLUE, va="bottom", fontsize=8)
    ax.set_xlabel("Rank of model"); ax.set_ylabel("Test misclassification error")
    ax.set_ylim(0, 0.42)
    fig.tight_layout()
    savefig(fig, CH, "fig9-12", out_dir)
    k = R["rank"].index(R["best_rank"])
    print("  GCV chooses %d terms, test error %.4f; mean test error for ranks >= 50: %.4f" % (R["best_rank"], R["err"][k], lev))
    print("  interactions in the chosen model:", R["interactions"][:8])


# =========================================================================== supplementary figures
def ozone_data():
    """Exercise 9.6: cube root of ozone (ppb) against temperature (F), wind speed (mph), radiation (langleys)."""
    A = load_ozone()
    return A[:, [2, 3, 1]], np.cbrt(A[:, 0]), ["temperature", "wind", "radiation"]


def ozone_additive(df=4.0, tol=1e-10, history=False):
    """The additive model for the cube root of ozone fitted by Algorithm 9.1 with exact smoothing splines
    (all knots) of df_j = trace S_j = df (unit weights)."""
    X, y, names = ozone_data()
    sps = [SmoothingSpline(X[:, j], all_knots=True) for j in range(3)]
    lams = [sp.lam_for_df(df) for sp in sps]
    smoothers = [(lambda r, w, s=s, l=l: s.smooth(r, w, l)) for s, l in zip(sps, lams)]
    bf = backfit(X, y, smoothers, tol=tol, maxit=1000, history=history)
    return dict(bf=bf, sps=sps, lams=lams, X=X, y=y, names=names)


def fig_9_s1(out_dir=None):
    """Supplementary (Exercise 9.6a): the additive model for the cube root of ozone, with partial residuals."""
    import matplotlib.pyplot as plt
    A = ozone_additive()
    X, y, F = A["X"], A["y"], A["bf"]["F"]
    res = y - A["bf"]["alpha"] - F.sum(1)
    fig, axes = common.panel_grid(1, 3, size=(2.9, 2.6))
    for j, a in enumerate(axes[0]):
        o = np.argsort(X[:, j])
        a.plot(X[:, j], F[:, j] + res, "o", color=GREY, ms=2.5, alpha=0.7)
        a.plot(X[o, j], F[o, j], color=BLUE, lw=1.6)
        a.set_xlabel(A["names"][j]); a.set_ylabel(r"$\hat f$(%s)" % A["names"][j])
    fig.tight_layout()
    savefig(fig, CH, "fig9-S1", out_dir)
    rss = float(np.sum(res ** 2))
    print("  ozone additive model: %d cycles, RSS %.4f, R^2 %.4f" % (A["bf"]["cycles"], rss, 1 - rss / np.sum((y - y.mean()) ** 2)))
    print("  trace of the additive-model smoother: %.4f (1 + sum of (trace S_j - 1) = %.1f)" % (additive_trace(A), 1 + 3 * 3.0))
    print("  Exercise 9.6(b):", ozone_methods())


def additive_trace(A):
    """trace of the N x N matrix R with yhat = R y for the fitted additive model (backfit each unit vector)."""
    X = A["X"]
    sm = [(lambda r, w, s=s, l=l: s.smooth(r, w, l)) for s, l in zip(A["sps"], A["lams"])]
    N = len(X)
    tr = 0.0
    for i in range(N):
        e = np.zeros(N); e[i] = 1.0
        b = backfit(X, e, sm, tol=1e-12, maxit=2000)
        tr += b["alpha"] + b["F"][i].sum()
    return tr


def ozone_methods(seed=0):
    """Exercise 9.6: 10-fold cross-validated mean squared error (cube-root scale) of the additive model,
    a pruned regression tree (pruning by 10-fold CV inside each fold would be costly; the subtree size is
    chosen by CV on the whole data and the folds are reused), MARS of degree 1 and 2, and the linear model."""
    X, y, names = ozone_data()
    N = len(y)
    folds = np.random.default_rng(seed).permutation(np.arange(N) % 10)
    T = Tree(task="reg", mindev=0.0, minsize=10, mincut=5).grow(X, y)
    seq = T.prune_sequence()
    al = np.array([a for a, _, _ in seq])
    mids = np.r_[0.0, np.sqrt(al[1:-1] * al[2:]), al[-1] + 1.0]
    E = cv_tree(X, y, folds, mids, task="reg", mindev=0.0)
    cvt = E.sum(0) / N
    ktree = int(np.argmin(cvt))
    out = dict(tree_cv=float(cvt[ktree]), tree_size=int(seq[ktree][2]))
    err = {"additive": [], "mars1": [], "mars2": [], "linear": []}
    for f in range(10):
        trn, tst = folds != f, folds == f
        sps = [SmoothingSpline(X[trn, j], all_knots=True) for j in range(3)]
        lams = [sp.lam_for_df(4.0) for sp in sps]
        bf = backfit(X[trn], y[trn], [(lambda r, w, s=s, l=l: s.smooth(r, w, l)) for s, l in zip(sps, lams)], tol=1e-10, maxit=1000)
        G = dict(alpha=bf["alpha"], sps=sps, theta=[theta_of(sps[j], bf["F"][:, j]) for j in range(3)])
        err["additive"].append(np.sum((y[tst] - gam_eta(G, X[tst])) ** 2))
        for d in (1, 2):
            M = MARS(max_terms=21, degree=d).fit(X[trn], y[trn])
            err["mars%d" % d].append(np.sum((y[tst] - M.predict(X[tst])) ** 2))
        D = np.column_stack([np.ones(trn.sum()), X[trn]])
        b = np.linalg.lstsq(D, y[trn], rcond=None)[0]
        err["linear"].append(np.sum((y[tst] - np.column_stack([np.ones(tst.sum()), X[tst]]) @ b) ** 2))
    for k, v in err.items():
        out[k + "_cv"] = float(np.sum(v) / N)
    out["variance"] = float(np.var(y))
    M = MARS(max_terms=21, degree=2).fit(X, y)
    out["mars2_terms"] = [mars_term_text(term, names) for term in M.terms[1:]]
    P = prim_peel(X, y, alpha=0.1, min_count=10)
    b = P[min(len(P) - 1, int(np.argmin([abs(q["n"] / N - 0.2) for q in P])))]
    out["prim_box"] = dict(n=b["n"], mean=round(b["mean"], 3), lo=[round(v, 2) for v in b["lo"]], hi=[round(v, 2) for v in b["hi"]])
    return out


def mars_term_text(term, names):
    return " * ".join(("(%s - %.4g)+" % (names[j], t)) if s > 0 else ("(%.4g - %s)+" % (t, names[j])) for j, t, s in term)


HME_CENTRES = np.array([-2.25, -0.75, 0.75, 2.25])


def hme_truth(x):
    """A two-level HME with soft gates: top gate g_1(x) = sigma(-2x); second-level gates
    g_{1|1}(x) = sigma(-2(x + 1.5)), g_{1|2}(x) = sigma(-2(x - 1.5)); the four linear experts are the
    tangent lines of 2 sin(x) at -2.25, -0.75, 0.75, 2.25. Returns the gate probabilities of the four
    paths (N x 4), the expert means (N x 4) and the regression function."""
    g1 = expit(-2 * x)
    ga, gb = expit(-2 * (x + 1.5)), expit(-2 * (x - 1.5))
    P = np.column_stack([g1 * ga, g1 * (1 - ga), (1 - g1) * gb, (1 - g1) * (1 - gb)])
    c = HME_CENTRES
    M = 2 * np.sin(c)[None, :] + 2 * np.cos(c)[None, :] * (x[:, None] - c[None, :])
    return P, M, np.sum(P * M, 1)


def hme_example(seed=HME_SEED, N=400, sd=0.25):
    """N draws from the HME of hme_truth: x ~ U(-3, 3), a path drawn from the gates, y = expert mean + noise."""
    rng = np.random.default_rng(seed)
    x = np.sort(rng.uniform(-3, 3, N))
    P, M, f = hme_truth(x)
    path = np.array([rng.choice(4, p=p) for p in P])
    y = M[np.arange(N), path] + sd * rng.normal(size=N)
    return x, y, f


def fig_9_s2(out_dir=None):
    """Supplementary (Section 9.5): a two-level HME of linear experts fitted by EM, against a CART tree."""
    import matplotlib.pyplot as plt
    x, y, f = hme_example()
    X = np.column_stack([np.ones(len(x)), x])
    fits = [hme_fit(X, y, K=2, iters=1000, seed=s) for s in range(6)]
    best = max(fits, key=lambda r: r["loglik"][-1])
    grid = np.linspace(-3, 3, 400)
    Xg = np.column_stack([np.ones(len(grid)), grid])
    mu, g1 = hme_predict(best, Xg)
    T = Tree(task="reg", mindev=0.0).grow(x[:, None], y)
    al = np.array([a for a, _, _ in T.prune_sequence()])
    folds = np.random.default_rng(1).permutation(np.arange(len(x)) % 10)
    mids = np.r_[0.0, np.sqrt(al[1:-1] * al[2:]), al[-1] + 1.0]
    E = cv_tree(x[:, None], y, folds, mids, task="reg", mindev=0.0)
    act = T.subtree_at(mids[int(np.argmin(E.sum(0)))])
    fig, axes = common.panel_grid(1, 3, size=(2.9, 2.6))
    a = axes[0, 0]
    a.plot(x, y, "o", color=GREY, ms=2, alpha=0.6)
    a.plot(grid, mu, color=BLUE, lw=1.6, label="HME")
    a.plot(grid, hme_truth(grid)[2], color="k", lw=0.8, ls=":", label="true mean")
    a.step(grid, T.predict(grid[:, None], act), where="mid", color=ORANGE, lw=1.2, label="CART (%d leaves)" % T.n_leaves(act))
    a.legend(frameon=False, fontsize=7.5); a.set_xlabel("$x$"); a.set_ylabel("$y$")
    b = axes[0, 1]
    # probabilities of the four paths (top branch j, then branch l): fitted (solid) and true (dotted);
    # the hierarchy is only identified up to relabelling, so the fitted paths are ordered by location
    Pf = np.column_stack([g1[:, j] * softmax_rows(Xg @ best["G2"][j])[:, l] for j in range(2) for l in range(2)])
    Pf = Pf[:, np.argsort((Pf * grid[:, None]).sum(0) / Pf.sum(0))]
    Pt = hme_truth(grid)[0]
    for k, c in enumerate((PURPLE, CYAN, GREEN, MAGENTA)):
        b.plot(grid, Pf[:, k], color=c, lw=1.4)
        b.plot(grid, Pt[:, k], color=c, lw=0.9, ls=":")
    b.set_xlabel("$x$"); b.set_ylabel("path probability")
    b.set_ylim(-0.03, 1.03)
    c = axes[0, 2]
    for r in fits:
        c.plot(np.arange(1, len(r["loglik"]) + 1), r["loglik"], lw=1)
    c.set_xscale("log"); c.set_xlabel("EM iteration"); c.set_ylabel("log-likelihood")
    fig.tight_layout()
    savefig(fig, CH, "fig9-S2", out_dir)
    print("  HME log-likelihoods from 6 starts:", [round(r["loglik"][-1], 3) for r in fits],
          "monotone:", all(np.all(np.diff(r["loglik"]) > -1e-6) for r in fits))
    print("  mean squared error against the true curve: HME %.4f, CART %.4f" % (
        np.mean((hme_predict(best, X)[0] - f) ** 2), np.mean((T.predict(x[:, None], act) - f) ** 2)))


def fig_9_s3(out_dir=None):
    """Supplementary (Exercise 9.5): degrees of freedom of regression trees with m leaves on pure noise."""
    import matplotlib.pyplot as plt
    sizes = (1, 2, 3, 5, 7, 10, 15, 20)
    d10 = tree_df_simulation(sizes=(1, 5, 10), reps=10)
    dbig = tree_df_simulation(sizes=sizes, reps=400)
    rng = np.random.default_rng(TREEDF_SEED)
    X = rng.normal(size=(100, 10))
    y = rng.normal(size=100)
    ye = {m: tree_df_ye(m, X, y)[0] for m in (1, 5, 10)}
    fig, ax = plt.subplots(figsize=(5.0, 3.6))
    ax.plot(sizes, [dbig[m] for m in sizes], "o-", color=RED, label="covariance df (400 simulations)")
    ax.plot((1, 5, 10), [d10[m] for m in (1, 5, 10)], "s", color=ORANGE, label="covariance df (10 simulations)")
    ax.plot((1, 5, 10), [ye[m] for m in (1, 5, 10)], "^", color=GREEN, label="trace of perturbation $\\hat S$")
    ax.plot(sizes, sizes, "--", color=GREY, label="number of leaves $m$")
    ax.set_xlabel("number of terminal nodes $m$"); ax.set_ylabel("degrees of freedom")
    ax.legend(frameon=False, fontsize=8)
    fig.tight_layout()
    savefig(fig, CH, "fig9-S3", out_dir)
    print("  tree df, 10 simulations:", {k: round(v, 2) for k, v in d10.items()})
    print("  tree df, 400 simulations:", {k: round(v, 2) for k, v in dbig.items()})
    print("  perturbation estimate (tau = 0.5, 200 perturbations):", {k: round(v, 2) for k, v in ye.items()})


def correlated_pair(rho, seed=BF_SIM_SEED, N=100):
    """Two inputs with correlation rho and y = sin(2 x1) + x2^2 / 2 + noise (for the backfitting demo)."""
    rng = np.random.default_rng(seed)
    x1, z, e = rng.normal(size=N), rng.normal(size=N), rng.normal(size=N)
    x2 = rho * x1 + np.sqrt(1 - rho ** 2) * z
    return np.column_stack([x1, x2]), np.sin(2 * x1) + 0.5 * x2 ** 2 + 0.5 * e, (x1, z, e)


def fig_9_s4(out_dir=None):
    """Supplementary (Exercises 9.2 and 9.4): how fast backfitting converges, and the same smoother twice."""
    import matplotlib.pyplot as plt
    fig, axes = common.panel_grid(1, 2, size=(3.4, 2.8))
    a = axes[0, 0]
    rates = {}
    for rho, col in ((0.0, BLUE), (0.5, GREEN), (0.9, ORANGE), (0.99, RED)):
        X, y, _ = correlated_pair(rho)
        sps = [SmoothingSpline(X[:, j], all_knots=True) for j in range(2)]
        lams = [sp.lam_for_df(5.0) for sp in sps]
        sm = [(lambda r, w, s=s, l=l: s.smooth(r, w, l)) for s, l in zip(sps, lams)]
        ref = backfit(X, y, sm, tol=1e-14, maxit=20000)
        F = np.zeros_like(X)
        err = []
        for c in range(60):
            F = backfit(X, y, sm, F=F, tol=0, maxit=1)["F"]
            err.append(np.sqrt(np.sum((F - ref["F"]) ** 2)))
        a.semilogy(np.arange(1, 61), err, color=col, label=r"$\rho=%g$" % rho)
        e = np.array(err)
        good = np.where(e > 1e-9 * e[0])[0]
        seg = e[good[len(good) // 2]:good[-1] + 1] if len(good) > 3 else e[:3]
        rates[rho] = float(np.exp(np.mean(np.diff(np.log(seg)))))
    a.set_xlabel("backfitting cycle"); a.set_ylabel(r"$\|\hat f^{(k)}-\hat f\|$"); a.legend(frameon=False, fontsize=7.5)
    b = axes[0, 1]
    A = ozone_data()
    x, y = A[0][:, 0], A[1]
    sp = SmoothingSpline(x, all_knots=True)
    lam = sp.lam_for_df(5.0)
    S = sp.matrix(np.ones(len(x)), lam)
    f1, f2 = np.zeros(len(y)), np.zeros(len(y))
    rss = []
    yc = y - y.mean()
    for c in range(40):
        f1 = S @ (yc - f2); rss.append(np.sum((yc - f1 - f2) ** 2))
        f2 = S @ (yc - f1); rss.append(np.sum((yc - f1 - f2) ** 2))
    lim = (np.linalg.solve(np.eye(len(y)) + S, (np.eye(len(y)) - S) @ yc))
    single = yc - S @ yc
    b.plot(np.arange(1, len(rss) + 1) / 2, rss, color=BLUE, label="backfitting with S twice")
    b.axhline(np.sum(lim ** 2), color=RED, ls="--", lw=1, label=r"$\|(I+S)^{-1}(I-S)y\|^2$")
    b.axhline(np.sum(single ** 2), color=GREY, ls=":", lw=1, label="single fit by $S$")
    b.set_xlabel("backfitting cycle"); b.set_ylabel("residual sum of squares"); b.legend(frameon=False, fontsize=7)
    fig.tight_layout()
    savefig(fig, CH, "fig9-S4", out_dir)
    print("  convergence factor per cycle:", {k: round(v, 4) for k, v in rates.items()})
    print("  Exercise 9.4 on temperature: RSS after the first update %.3f, limit %.3f, single smoother %.3f"
          % (rss[0], np.sum(lim ** 2), np.sum(single ** 2)))


# =========================================================================== demo data
def export_demo_data():
    """Write ../data/ch09-ozone.json, ../data/ch09-spam.json and ../data/ch09-mars.json."""
    os.makedirs(JSON_DIR, exist_ok=True)
    X, y, names = ozone_data()
    _, _, (x1, z, e) = correlated_pair(0.0)
    oz = dict(names=names, X=[[round(float(v), 6) for v in X[:, j]] for j in range(3)], y=[round(float(v), 6) for v in y],
              sim=dict(x1=[round(float(v), 6) for v in x1], z=[round(float(v), 6) for v in z], e=[round(float(v), 6) for v in e]))
    with open(os.path.join(JSON_DIR, "ch09-ozone.json"), "w") as f:
        json.dump(oz, f, separators=(",", ":"))
    Xs, ys, te = load_spam()
    cols = []
    for j in range(Xs.shape[1]):
        nz = np.nonzero(Xs[:, j])[0]
        cols.append(dict(d=np.diff(np.r_[-1, nz]).tolist(), v=[float(("%.3f" % v).rstrip("0").rstrip(".")) for v in Xs[nz, j]]))
    R = spam_tree()
    sp = dict(names=SPAM_NAMES, N=int(len(ys)), cols=cols, y="".join(str(int(v)) for v in ys),
              test="".join("1" if t else "0" for t in te), folds="".join(str(int(v)) for v in R["folds"]))
    with open(os.path.join(JSON_DIR, "ch09-spam.json"), "w") as f:
        json.dump(sp, f, separators=(",", ":"))
    md = mars_demo_data()
    with open(os.path.join(JSON_DIR, "ch09-mars.json"), "w") as f:
        json.dump(md, f, separators=(",", ":"))
    for n in ("ch09-ozone.json", "ch09-spam.json", "ch09-mars.json"):
        print("wrote", os.path.relpath(os.path.join(JSON_DIR, n), os.getcwd()), "(%.0f kB)" % (os.path.getsize(os.path.join(JSON_DIR, n)) / 1e3))


def mars_demo_data(seed=MARS_DEMO_SEED):
    """Data sets of the MARS demonstration: a sample of scenario (9.21) (N = 100), the same with a
    smaller noise, and the ozone data (temperature and wind)."""
    rng = np.random.default_rng(seed)
    X = rng.normal(size=(100, 2))
    mu = np.maximum(X[:, 0] - 1, 0) + np.maximum(X[:, 0] - 1, 0) * np.maximum(X[:, 1] - 0.8, 0)
    e = rng.normal(size=100)
    Xo, yo, _ = ozone_data()
    r = lambda a: [round(float(v), 5) for v in a]
    return dict(tensor=dict(x1=r(X[:, 0]), x2=r(X[:, 1]), mu=r(mu), e=r(e)),
                ozone=dict(x1=r(Xo[:, 0]), x2=r(Xo[:, 1]), y=r(yo), names=["temperature", "wind"]))


FIGURES = {"9.1": fig_9_1, "9.2": fig_9_2, "9.3": fig_9_3, "9.4": fig_9_4, "9.5": fig_9_5, "9.6": fig_9_6,
           "9.7": fig_9_7, "9.8": fig_9_8, "9.9": fig_9_9, "9.11": fig_9_11, "9.12": fig_9_12,
           "9.S1": fig_9_s1, "9.S2": fig_9_s2, "9.S3": fig_9_s3, "9.S4": fig_9_s4}


def table_9_4():
    R = mars_scenarios()
    for sc, lab in ((1, "tensor product, p = 2"), (2, "tensor product, p = 20"), (3, "neural network")):
        print("  Table 9.4, scenario %d (%s): R^2 mean %.3f (se %.3f), median %.3f" % (sc, lab, R[sc]["mean"], R[sc]["se"], R[sc]["median"]))
    return R


def main():
    if "--demo-data" in sys.argv:
        export_demo_data()
        return
    if "--table-9-4" in sys.argv:
        table_9_4()
        return
    common.run(FIGURES, CH)
    if not any(a.startswith("--") for a in sys.argv[1:]):
        table_9_4()
        export_demo_data()


if __name__ == "__main__":
    main()
