"""Hastie, Tibshirani and Friedman (2009), Chapter 10: Boosting and Additive Trees.

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

* Section 10.1, AdaBoost.M1 (Algorithm 10.1): adaboost_m1 with exact weighted-error decision stumps
  (fit_stump: every threshold of every input is tried, using sorted cumulative sums), or with any
  weighted classifier (for instance a scikit-learn classification tree, with which it reproduces
  scikit-learn's two-class AdaBoost exactly). real_adaboost_stumps gives each side of the stump
  the exponential-loss leaf value (10.32) with its factor 1/2 ('Real AdaBoost' with stumps); it is
  the version that reproduces the numbers the book quotes for Figures 10.2 and 10.3.
  The nested-spheres simulation (10.2) is nested_spheres.
* Sections 10.4-10.6, the loss functions of Figures 10.4 and 10.5 (LOSSES_CLASS, huber) and the
  exponential-loss leaf value (10.32) of Exercise 10.7 (exp_leaf_value).
* Sections 10.9-10.10, gradient tree boosting (Algorithm 10.3) for squared, absolute and Huber
  loss and the binomial deviance, and its K-class version (Algorithm 10.4): GradientBoosting.
  The regression trees with J terminal nodes (grow_tree) are grown best-first, as in MART: the
  leaf whose best split most reduces the squared error is split next, until there are J leaves.
  Split search uses histograms of the inputs: each input is cut at the midpoints between its
  distinct values, or, when there are more than 256 distinct values, at 255 midpoints chosen at its
  quantiles (Binner). With at most 256 distinct values per input the trees are exactly the
  least-squares trees (confirmed against scikit-learn), and the binning is only an approximation
  for the continuous inputs of the simulations. Leaf values are the line searches (10.30):
  the mean (squared error), the median (absolute error), Friedman's one-step Huber estimate, a
  Newton step for the deviance, and the (K-1)/K-scaled step of Algorithm 10.4 for K classes.
* Section 10.12, shrinkage (10.41) and subsampling: the arguments nu and subsample.
* Section 10.13, interpretation: relative_importance ((10.42)-(10.46), from the squared-error
  improvements of the splits), partial dependence (10.47)-(10.48) by brute force
  (pd_brute), by an exact one-pass-per-tree method (pd_trees, Exercise 10.11) and by the data-free
  weighted traversal of the trees (pd_traversal), and the conditional expectation (10.49).
* Section 10.14, the illustrations: California housing (Huber loss, Figures 10.13-10.17) and the
  demographics (marketing) data (Algorithm 10.4 with K = 9 occupations, Figures 10.22-10.25).

Figures reproduced: 10.2, 10.3, 10.4, 10.5, 10.6, 10.7, 10.8, 10.9, 10.10, 10.11, 10.12, 10.13,
10.14, 10.15, 10.16, 10.17, 10.22, 10.23, 10.24, 10.25, plus one supplementary figure: 10.S1
(Exercise 10.4: a long AdaBoost run on (10.2), and the overlapping-classes version of
Exercise 10.4(d)). Run `python3 ch10_boosting.py --list`, `python3 ch10_boosting.py` (all
figures, about ten minutes the first time; fitted models are cached in cache/) or
`python3 ch10_boosting.py --fig 10.2`. Files go to ../img/ch10/. The data the browser
demonstrations use are written to ../data/ by export_demo_data() (called from Figure 10.6).

Figures not reproduced, and why:
* Figure 10.1 is a schematic diagram of AdaBoost with nothing computed.
* Figures 10.18-10.21 (the New Zealand fish survey: map of trawls, deviance and ROC curves,
  relative influence and partial dependence, prediction maps) use trawl data that are not
  distributed with the book. The same tools (deviance curves, relative importance, partial
  dependence) are shown on the spam, California housing and demographics data.

Settings chosen where the book gives none:
* The simulation (10.2): N = 2000 training and 10000 test points, numpy default_rng(10) for the
  training set and default_rng(11) for the test set, Y = +1 outside the sphere of squared radius
  chi2_10(0.5) = 9.342 and -1 inside. The 244-node tree of Figure 10.2 is a scikit-learn
  classification tree (Gini splits) grown best-first to 244 leaves.
* Figure 10.9: binomial deviance, no shrinkage (nu = 1), trees with 2, 10 and 100 leaves.
* Figure 10.11: as labelled in the book, nu = 0.2 for stumps and nu = 0.6 for 6-node trees, plus
  nu = 0.06 for 6-node trees (the curve that looks like the book's).
* Figure 10.12: 4-node trees; nu = 0.1 and/or 50% subsamples drawn afresh at every iteration
  (numpy default_rng(12)); the regression version codes Y as 0/1 and uses squared error.
* Deviance is reported, as in the book's figures, as -2 times the mean binomial log-likelihood.
* Spam data (Figures 10.6-10.8): the book's training/test split (spam.traintest); J = 5 leaves,
  nu = 0.1, binomial deviance, M chosen by 5-fold cross-validation on the training set
  (default_rng(13) folds). The J = 2 (additive) model uses the same settings.
* California housing (Figures 10.13-10.17): scikit-learn's copy of the data of Pace and Barry
  (1997) (20640 block groups; downloaded once), a random 80/20 split (default_rng(14)), J = 6,
  nu = 0.1, Huber loss with delta the 0.9 quantile of the absolute residuals, M = 800.
* Demographics (Figures 10.22-10.25): the book's marketing data (8993 questionnaires, the extract
  on the book's website; the book used a 9243-questionnaire version), occupation as the
  response (rows with occupation missing dropped), the other 13 variables as predictors with a
  missing value coded as its own lowest category; a random 80/20 split (default_rng(15)), J = 6,
  nu = 0.1, M (rounds of K = 9 trees) chosen by 5-fold cross-validated deviance (default_rng(16) folds).
* Partial dependence plots are centred to have mean zero over the training data.

Browser demonstrations: js_spheres, js_regression and js_subsampler draw the demos' data and
subsamples with the demos' own seeded generator (JSRandom, a port of DK.rng), so that the Python
functions above give the same numbers as the pages adaboost-spheres-demo.html,
gradient-boosting-demo.html and spam-partial-dependence-demo.html.
"""
import json
import math
import os
import pickle

import numpy as np

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

CH = 10
HERE = os.path.dirname(os.path.abspath(__file__))
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
CACHE_DIR = os.path.join(HERE, "cache")
CHI2_10_MEDIAN = 9.341817765591966   # scipy.stats.chi2.ppf(0.5, 10)
M32 = 0xFFFFFFFF


# =========================================================================== the demos' generator
def _imul(a, b):
    """32-bit integer multiplication with wrap-around, as Math.imul (result as unsigned)."""
    return (a * b) & M32


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

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

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

    def _pos(self):
        x = 0.0
        while x == 0.0:
            x = self.u()
        return x

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


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


def js_normals(seed, n, start=0):
    """n consecutive DK.rng(seed).norm() values drawn after `start` uniforms (Box-Muller pairs)."""
    npair = (n + 1) // 2
    u = js_uniforms(seed, 2 * npair, start)
    u1, u2 = u[0::2], u[1::2]
    if np.any(u1 == 0.0):
        raise RuntimeError("a zero uniform: use JSRandom for this stream")
    r = np.sqrt(-2.0 * np.log(u1))
    th = 2.0 * np.pi * u2
    out = np.empty(2 * npair)
    out[0::2] = r * np.cos(th)
    out[1::2] = r * np.sin(th)
    return out[:n]


# =========================================================================== data
def nested_spheres(N, seed, p=10):
    """The simulation (10.2): X ~ N(0, I_p), Y = +1 if sum X_j^2 > chi2_p(0.5), else -1."""
    from scipy.stats import chi2
    rng = np.random.default_rng(seed)
    X = rng.standard_normal((N, p))
    y = np.where((X ** 2).sum(1) > chi2.ppf(0.5, p), 1, -1)
    return X, y


def spheres_train_test():
    Xtr, ytr = nested_spheres(2000, 10)
    Xte, yte = nested_spheres(10000, 11)
    return Xtr, ytr, Xte, yte


def overlap_spheres(N, seed, thresh=12.0, p=10):
    """Exercise 10.4(d): class -1 is N(0, I_p); class +1 is N(0, I_p) conditioned on
    sum X_j^2 > thresh (by rejection). N/2 points per class."""
    rng = np.random.default_rng(seed)
    n1 = N // 2
    X1 = rng.standard_normal((N - n1, p))
    out = []
    while sum(len(o) for o in out) < n1:
        Z = rng.standard_normal((4 * n1, p))
        out.append(Z[(Z ** 2).sum(1) > thresh])
    X2 = np.vstack(out)[:n1]
    X = np.vstack([X1, X2])
    y = np.r_[-np.ones(N - n1, int), np.ones(n1, int)]
    perm = rng.permutation(N)
    return X[perm], y[perm]


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", ";", "(", "[", "!",
              "$", "#", "CAPAVE", "CAPMAX", "CAPTOT"]


def spam():
    """The spam data with the book's split: (Xtr, ytr, Xte, yte) with y = 1 for spam."""
    D = np.loadtxt(common.esl_file("spam.data"))
    test = np.loadtxt(common.esl_file("spam.traintest")).astype(bool)
    X, y = D[:, :57], D[:, 57].astype(int)
    return X[~test], y[~test], X[test], y[test]


CAL_NAMES = ["MedInc", "HouseAge", "AveRooms", "AveBedrms", "Population", "AveOccup", "Latitude", "Longitude"]


def california():
    """California housing (Pace and Barry 1997), median house value in units of $100,000;
    random 80/20 split. Returns Xtr, ytr, Xte, yte."""
    from sklearn.datasets import fetch_california_housing
    d = fetch_california_housing()
    X, y = d.data, d.target
    perm = np.random.default_rng(14).permutation(len(y))
    ntr = int(round(0.8 * len(y)))
    tr, te = perm[:ntr], perm[ntr:]
    return X[tr], y[tr], X[te], y[te]


MKT_COLS = ["income", "sex", "mar-stat", "age", "edu", "occupation", "yrs-BA", "mar-dlinc", "num-hsld",
            "children", "hsld-stat", "typ-home", "ethnic", "lang"]
OCCUPATIONS = ["Prof/Man", "Sales", "Labor", "Clerical", "Homemaker", "Student", "Military", "Retired", "Unemployed"]


def marketing():
    """The demographics (marketing) data: X (13 predictors, NaN = missing), occupation 0..8,
    predictor names, random 80/20 split. Returns Xtr, ytr, Xte, yte, names."""
    import pandas as pd
    D = pd.read_csv(common.esl_file("marketing.data"), sep=r"\s+", header=None, na_values="NA").to_numpy(float)
    occ = D[:, 5]
    keep = ~np.isnan(occ)
    D = D[keep]
    y = D[:, 5].astype(int) - 1
    cols = [c for c in range(14) if c != 5]
    X = D[:, cols]
    names = [MKT_COLS[c] for c in cols]
    perm = np.random.default_rng(15).permutation(len(y))
    ntr = int(round(0.8 * len(y)))
    tr, te = perm[:ntr], perm[ntr:]
    return X[tr], y[tr], X[te], y[te], names


def js_spheres(N, seed, setting="spheres", noise=0.0, p=10):
    """The data of the AdaBoost demo, drawn with the demo's generator DK.rng (JSRandom).

    setting 'spheres' is (10.2): every point is p standard normals (drawn in row order) and
    y = +1 when the squared radius exceeds chi2_p(0.5). Setting 'overlap' is Exercise 10.4(d):
    even-numbered points are class -1, N(0, I); odd-numbered points are class +1, drawn again and
    again until the squared radius exceeds 12. With noise q, each label is flipped when a uniform
    from DK.rng(seed + 2) is below q (one uniform per point, so the data do not depend on q).
    Returns X, y (labels used for training) and the indicator of flipped labels."""
    rng = JSRandom(seed)
    X = np.empty((N, p))
    y = np.empty(N, dtype=int)
    for i in range(N):
        if setting == "spheres":
            x = [rng.norm() for _ in range(p)]
            r2 = sum(v * v for v in x)
            y[i] = 1 if r2 > CHI2_10_MEDIAN else -1
        else:
            if i % 2 == 0:
                x = [rng.norm() for _ in range(p)]
                y[i] = -1
            else:
                while True:
                    x = [rng.norm() for _ in range(p)]
                    if sum(v * v for v in x) > 12.0:
                        break
                y[i] = 1
        X[i] = x
    flip = np.zeros(N, bool)
    if noise > 0:
        rn = JSRandom(seed + 2)
        for i in range(N):
            flip[i] = rn.u() < noise
    return X, np.where(flip, -y, y), flip


def gb_demo_truth(x):
    """The regression function of the gradient-boosting demo: sin(2 pi x) plus a jump of 1 at 0.6."""
    return np.sin(2 * np.pi * x) + (x > 0.6)


def js_regression(N, seed, outliers=0.0):
    """The data of the gradient-boosting demo, drawn with DK.rng: x_i = u(), y_i = f(x_i) + 0.3 norm(),
    and, from the stream DK.rng(seed + 3) (three uniforms per point, used or not), an outlier of size
    3 + 3u and random sign added with probability `outliers`. Returns x, y, outlier indicator."""
    rng = JSRandom(seed)
    x = np.empty(N)
    e = np.empty(N)
    for i in range(N):
        x[i] = rng.u()
        e[i] = 0.3 * rng.norm()
    y = gb_demo_truth(x) + e
    ro = JSRandom(seed + 3)
    out = np.zeros(N, bool)
    for i in range(N):
        a, b, c = ro.u(), ro.u(), ro.u()
        if a < outliers:
            out[i] = True
            y[i] += (-1.0 if c < 0.5 else 1.0) * (3.0 + 3.0 * b)
    return x, y, out


def js_subsampler(seed):
    """The demo's subsampling: at every iteration a partial Fisher-Yates shuffle of 0..N-1 driven by
    DK.rng(seed + 5) (one stream for the whole run), keeping the first n."""
    rng = JSRandom(seed + 5)

    def sample(m, N, n):
        idx = list(range(N))
        for k in range(n):
            j = k + int(math.floor(rng.u() * (N - k)))
            idx[k], idx[j] = idx[j], idx[k]
        return np.array(idx[:n])
    return sample


# =========================================================================== AdaBoost.M1 (Algorithm 10.1)
class StumpFitter:
    """Exact weighted-error decision stumps G(x) = s if x_j > t else -s, s in {-1, +1}.

    The inputs are sorted once. For each input j, after the k smallest points (k = 0..N) the
    weighted error of s = +1 is (weight of y=+1 on the left) + (weight of y=-1 on the right), and
    of s = -1 the complement; both come from cumulative sums. Ties are broken by the first minimum
    in the order (input, k, s = +1 before -1), the same order as the browser demo.
    """

    def __init__(self, X):
        self.X = X
        self.order = np.argsort(X, axis=0, kind="stable")
        self.xs = np.take_along_axis(X, self.order, axis=0)
        N = X.shape[0]
        self.thr = np.vstack([np.full((1, X.shape[1]), -np.inf), 0.5 * (self.xs[:-1] + self.xs[1:]), np.full((1, X.shape[1]), np.inf)])
        self.N = N

    def fit(self, y, w):
        best = (np.inf, 0, 0, 1)
        for j in range(self.X.shape[1]):
            o = self.order[:, j]
            wp = np.where(y[o] > 0, w[o], 0.0)
            wm = np.where(y[o] > 0, 0.0, w[o])
            Lp = np.r_[0.0, np.cumsum(wp)]
            Lm = np.r_[0.0, np.cumsum(wm)]
            Wp, Wm = Lp[-1], Lm[-1]
            e_pos = Lp + (Wm - Lm)          # predict +1 on the right (x > t), -1 on the left
            e_neg = Lm + (Wp - Lp)          # predict -1 on the right
            E = np.empty(2 * len(e_pos))
            E[0::2], E[1::2] = e_pos, e_neg
            a = int(np.argmin(E))
            if E[a] < best[0]:
                best = (E[a], j, a // 2, 1 if a % 2 == 0 else -1)
        err, j, k, s = best
        return j, self.thr[k, j], s, err


def stump_predict(X, j, t, s):
    return np.where(X[:, j] > t, s, -s)


def adaboost_m1(X, y, M, Xtest=None, ytest=None, learner=None, record_weights=()):
    """AdaBoost.M1 (Algorithm 10.1) with exact stumps (learner=None) or any weighted classifier
    learner(X, y, w) -> predict function. Weights are renormalised to sum 1 after each update
    (this does not change the algorithm). Returns a dict with the stumps, the alphas, the
    weighted errors, and per-round training error, test error and training exponential loss
    (1/N) sum exp(-y f) with f = sum_m beta_m G_m, beta_m = alpha_m / 2 (Section 10.4)."""
    N = len(y)
    w = np.full(N, 1.0 / N)
    sf = StumpFitter(X) if learner is None else None
    F = np.zeros(N)
    Ft = np.zeros(len(ytest)) if ytest is not None else None
    out = {"stumps": [], "alpha": [], "err": [], "train_err": [], "test_err": [], "exp_loss": [], "weights": {}}
    for m in range(1, M + 1):
        if learner is None:
            j, t, s, _ = sf.fit(y, w)
            G = stump_predict(X, j, t, s)
            out["stumps"].append((j, t, s))
            pred_t = (lambda Z, j=j, t=t, s=s: stump_predict(Z, j, t, s))
        else:
            pred_t = learner(X, y, w)
            G = pred_t(X)
        miss = G != y
        cs = np.cumsum(w)
        err = float(np.cumsum(np.where(miss, w, 0.0))[-1] / cs[-1])
        err = min(max(err, 1e-16), 1 - 1e-16)
        alpha = math.log((1 - err) / err)
        w = w * np.exp(alpha * miss)
        w = w / np.cumsum(w)[-1]
        F += 0.5 * alpha * G
        out["alpha"].append(alpha)
        out["err"].append(err)
        out["train_err"].append(float(np.mean(np.sign(F) != y)))
        out["exp_loss"].append(float(np.mean(np.exp(-y * F))))
        if ytest is not None:
            Ft += 0.5 * alpha * pred_t(Xtest)
            out["test_err"].append(float(np.mean(np.sign(Ft) != ytest)))
        if m in record_weights:
            out["weights"][m] = w.copy()
    out["F"] = F
    out["Ftest"] = Ft
    out["w"] = w
    for k in ("alpha", "err", "train_err", "test_err", "exp_loss"):
        out[k] = np.array(out[k])
    return out


def real_adaboost_stumps(X, y, M, Xtest=None, ytest=None, eps=1e-10):
    """Boosting stumps with exponential loss and unrestricted leaf values, (10.31)-(10.32) with the
    factor 1/2 of Exercise 10.7 ('Real AdaBoost' of Friedman et al. 2000 with stumps). At each
    round the split minimises the weighted exponential criterion, which for a split into regions
    with weights (W+_L, W-_L), (W+_R, W-_R) is 2(sqrt(W+_L W-_L) + sqrt(W+_R W-_R)); each side gets
    gamma = (1/2) log((W+ + eps)/(W- + eps)). Returns the same records as adaboost_m1."""
    N = len(y)
    w = np.full(N, 1.0 / N)
    sf = StumpFitter(X)
    F = np.zeros(N)
    Ft = np.zeros(len(ytest)) if ytest is not None else None
    out = {"stumps": [], "train_err": [], "test_err": [], "exp_loss": []}
    for m in range(1, M + 1):
        best = (np.inf, 0, 0, 0.0, 0.0)
        for j in range(X.shape[1]):
            o = sf.order[:, j]
            Lp = np.r_[0.0, np.cumsum(np.where(y[o] > 0, w[o], 0.0))]
            Lm = np.r_[0.0, np.cumsum(np.where(y[o] > 0, 0.0, w[o]))]
            Rp, Rm = Lp[-1] - Lp, Lm[-1] - Lm
            Z = np.sqrt(Lp * Lm) + np.sqrt(Rp * Rm)
            k = int(np.argmin(Z))
            if Z[k] < best[0]:
                best = (Z[k], j, k, 0.5 * math.log((Lp[k] + eps) / (Lm[k] + eps)), 0.5 * math.log((Rp[k] + eps) / (Rm[k] + eps)))
        _, j, k, gl, gr = best
        t = sf.thr[k, j]
        h = np.where(X[:, j] > t, gr, gl)
        out["stumps"].append((j, t, gl, gr))
        F += h
        w = w * np.exp(-y * h)
        w = w / np.cumsum(w)[-1]
        out["train_err"].append(float(np.mean(np.sign(F) != y)))
        out["exp_loss"].append(float(np.mean(np.exp(-y * F))))
        if ytest is not None:
            Ft += np.where(Xtest[:, j] > t, gr, gl)
            out["test_err"].append(float(np.mean(np.sign(Ft) != ytest)))
    for k in ("train_err", "test_err", "exp_loss"):
        out[k] = np.array(out[k])
    out["F"], out["Ftest"] = F, Ft
    return out


def stump_coordinate_functions(stumps, betas, grid, p=10):
    """For an additive model sum_m beta_m G_m(x) of stumps, the function of each x_j:
    f_j(x_j) = sum over the stumps on input j of beta_m s_m sign(x_j - t_m). Returns (p, len(grid))."""
    out = np.zeros((p, len(grid)))
    for (j, t, s), b in zip(stumps, betas):
        out[j] += b * np.where(grid > t, s, -s)
    return out


# =========================================================================== loss functions (Figs 10.4, 10.5)
def loss_misclass(m):
    return (m < 0).astype(float)


def loss_exponential(m):
    return np.exp(-m)


def loss_deviance(m):
    """Binomial deviance log(1 + exp(-2 y f)) (10.18), as a function of the margin m = y f."""
    return np.logaddexp(0.0, -2.0 * m)


def loss_squared_margin(m):
    """(y - f)^2 = (1 - y f)^2 for y = +-1."""
    return (1.0 - m) ** 2


def loss_hinge(m):
    return np.maximum(0.0, 1.0 - m)


def huber(r, delta):
    """Huber loss (10.23) of the residual r = y - f."""
    a = np.abs(r)
    return np.where(a <= delta, r ** 2, 2 * delta * a - delta ** 2)


def exp_leaf_value(y, w):
    """Exercise 10.7: the constant gamma minimising sum_i w_i exp(-y_i gamma) over a region,
    gamma = (1/2) log(sum_{y=1} w / sum_{y=-1} w) (the book's (10.32) omits the factor 1/2)."""
    return 0.5 * math.log(w[y > 0].sum() / w[y < 0].sum())


# =========================================================================== regression trees on binned inputs
class Binner:
    """Cut points for each input: midpoints between distinct values (all of them if there are at
    most max_bins distinct values, otherwise max_bins - 1 of them chosen at quantiles). code(x) is
    the number of cut points below x, so that x <= edges[b] exactly when code <= b. A missing
    value (NaN) gets code 0, i.e. it is treated as a category below all observed values."""

    def __init__(self, X, max_bins=256):
        self.edges = []
        X = np.asarray(X, float)
        for j in range(X.shape[1]):
            v = X[:, j]
            u = np.unique(v[~np.isnan(v)])
            mids = 0.5 * (u[:-1] + u[1:])
            if np.isnan(v).any():
                mids = np.r_[u[0] - 1.0, mids]   # a cut that separates missing values from the rest
            if len(mids) > max_bins - 1:
                q = np.quantile(v[~np.isnan(v)], np.arange(1, max_bins) / max_bins, method="lower")
                idx = np.unique(np.searchsorted(u, q))
                idx = idx[idx < len(u) - 1]
                mids = 0.5 * (u[idx] + u[idx + 1])
                if np.isnan(v).any():
                    mids = np.r_[u[0] - 1.0, mids]
            self.edges.append(mids)
        self.nbins = np.array([len(e) + 1 for e in self.edges])
        self.B = int(self.nbins.max())

    def code(self, X):
        X = np.asarray(X, float)
        C = np.empty(X.shape, dtype=np.int32)
        for j, e in enumerate(self.edges):
            v = X[:, j]
            c = np.searchsorted(e, v, side="left")
            c[np.isnan(v)] = 0
            C[:, j] = c
        return C

    def threshold(self, j, b):
        return self.edges[j][b]


class Tree:
    """A binary regression tree stored in arrays: internal node t splits input feat[t] at bin
    thr_bin[t] (go left when code <= thr_bin, i.e. x <= thr[t]); leaves carry value[t]."""

    def __init__(self):
        self.feat, self.thr_bin, self.thr, self.left, self.right = [], [], [], [], []
        self.value, self.n, self.gain, self.depth = [], [], [], []

    def add(self, n, depth):
        for a, v in ((self.feat, -1), (self.thr_bin, -1), (self.thr, np.nan), (self.left, -1), (self.right, -1),
                     (self.value, 0.0), (self.gain, 0.0)):
            a.append(v)
        self.n.append(n)
        self.depth.append(depth)
        return len(self.n) - 1

    def finish(self):
        for k in ("feat", "thr_bin", "left", "right", "n", "depth"):
            setattr(self, k, np.array(getattr(self, k), dtype=np.int64))
        for k in ("thr", "value", "gain"):
            setattr(self, k, np.array(getattr(self, k), dtype=float))
        self.is_leaf = self.left < 0
        return self

    def apply_codes(self, C):
        node = np.zeros(C.shape[0], dtype=np.int64)
        while True:
            internal = ~self.is_leaf[node]
            if not internal.any():
                return node
            idx = np.nonzero(internal)[0]
            nd = node[idx]
            go_left = C[idx, self.feat[nd]] <= self.thr_bin[nd]
            node[idx] = np.where(go_left, self.left[nd], self.right[nd])

    def apply(self, X):
        """Leaf of each row of raw inputs X (x <= thr goes left; NaN goes left, as code 0)."""
        node = np.zeros(X.shape[0], dtype=np.int64)
        while True:
            internal = ~self.is_leaf[node]
            if not internal.any():
                return node
            idx = np.nonzero(internal)[0]
            nd = node[idx]
            xv = X[idx, self.feat[nd]]
            go_left = (xv <= self.thr[nd]) | np.isnan(xv)
            node[idx] = np.where(go_left, self.left[nd], self.right[nd])

    def predict(self, X):
        return self.value[self.apply(X)]

    def leaves(self):
        return np.nonzero(self.is_leaf)[0]

    def paths(self):
        """For each leaf, the list of conditions (feature, threshold, goes_left) on its path."""
        out = {}
        stack = [(0, [])]
        while stack:
            t, cond = stack.pop()
            if self.is_leaf[t]:
                out[t] = cond
            else:
                stack.append((self.left[t], cond + [(self.feat[t], self.thr[t], True)]))
                stack.append((self.right[t], cond + [(self.feat[t], self.thr[t], False)]))
        return out


def _best_split(Cn, g, nbins, B):
    """Best least-squares split of one node: returns (gain, feature, bin) or None.
    gain = GL^2/nL + GR^2/nR - G^2/n, the decrease of the sum of squares (10.42's improvement)."""
    n, p = Cn.shape
    idx = (Cn + (np.arange(p) * B)[None, :]).ravel()
    G = np.bincount(idx, weights=np.repeat(g, p), minlength=p * B).reshape(p, B)
    Nc = np.bincount(idx, minlength=p * B).reshape(p, B).astype(float)
    GL = np.cumsum(G, axis=1)[:, :-1]
    NL = np.cumsum(Nc, axis=1)[:, :-1]
    Gt = np.cumsum(G, axis=1)[:, -1:]
    GR = Gt - GL
    NR = n - NL
    valid = (NL > 0) & (NR > 0) & (np.arange(B - 1)[None, :] < (nbins[:, None] - 1))
    with np.errstate(divide="ignore", invalid="ignore"):
        gain = np.where(valid, GL ** 2 / NL + GR ** 2 / NR - Gt ** 2 / n, -np.inf)
    a = int(np.argmax(gain))
    j, b = divmod(a, B - 1)
    if not np.isfinite(gain[j, b]) or gain[j, b] <= 0.0:
        return None
    return float(gain[j, b]), j, b


def grow_tree(C, g, J, binner, rows=None):
    """Least-squares regression tree with (at most) J leaves on the targets g, grown best-first.
    C are the binned inputs. Returns the tree and the leaf of each row used."""
    rows = np.arange(C.shape[0]) if rows is None else rows
    T = Tree()
    root = T.add(len(rows), 0)
    members = {root: rows}
    cand = {}

    def consider(t):
        r = members[t]
        if len(r) < 2:
            return
        s = _best_split(C[r], g[r], binner.nbins, binner.B)
        if s is not None:
            cand[t] = s

    consider(root)
    nleaves = 1
    while nleaves < J and cand:
        t = max(cand, key=lambda k: (cand[k][0], -k))
        gain, j, b = cand.pop(t)
        r = members.pop(t)
        left_mask = C[r, j] <= b
        L = T.add(int(left_mask.sum()), T.depth[t] + 1)
        R = T.add(int((~left_mask).sum()), T.depth[t] + 1)
        T.feat[t], T.thr_bin[t], T.thr[t], T.left[t], T.right[t], T.gain[t] = j, b, binner.threshold(j, b), L, R, gain
        members[L], members[R] = r[left_mask], r[~left_mask]
        consider(L)
        consider(R)
        nleaves += 1
    T.finish()
    return T, members


# =========================================================================== gradient boosting (Algorithms 10.3, 10.4)
def _sigmoid(f):
    return 0.5 * (1.0 + np.tanh(0.5 * f))


def deviance_binomial(y01, F):
    """-2 x mean binomial log-likelihood, F = log-odds."""
    return float(np.mean(2.0 * (np.logaddexp(0.0, F) - y01 * F)))


def deviance_multinomial(y, F):
    from scipy.special import logsumexp
    return float(np.mean(2.0 * (logsumexp(F, axis=1) - F[np.arange(len(y)), y])))


class GradientBoosting:
    """Gradient tree boosting, Algorithm 10.3 (loss = 'ls', 'lad', 'huber', 'bernoulli') and
    Algorithm 10.4 (loss = 'multinomial', y in 0..K-1), with shrinkage nu (10.41) and subsampling
    (a fraction `subsample` of the rows drawn without replacement at each iteration).

    For 'bernoulli' y is 0/1 and f is the log-odds; the pseudo-residuals and leaf values are
    those of Table 10.2 and (10.30): mean, median, Friedman's one-step Huber estimate, the Newton
    step sum r / sum p(1-p), and the K-class step of Algorithm 10.4.
    `evals` maps a name to (X, y); `metrics` maps a metric name to f(y, F); the metric of every
    eval set is recorded after every iteration in self.history[name][metric] (index 0 = f_0).
    `sampler(m, N, n)` returns the subsample rows (default: numpy default_rng(seed).choice).
    """

    def __init__(self, loss="ls", J=6, nu=0.1, M=100, subsample=1.0, huber_alpha=0.9, seed=0, max_bins=256,
                 sampler=None, K=None):
        self.loss, self.J, self.nu, self.M, self.subsample = loss, J, nu, M, subsample
        self.huber_alpha, self.seed, self.max_bins, self.sampler, self.K = huber_alpha, seed, max_bins, sampler, K

    # initial constant f_0 = argmin sum L(y, gamma)
    def _init(self, y):
        if self.loss == "ls":
            return float(np.mean(y))
        if self.loss in ("lad", "huber"):
            return float(np.median(y))
        if self.loss == "bernoulli":
            p = np.mean(y)
            return float(np.log(p / (1 - p)))
        return np.zeros(self.K)

    def _leaf_value(self, r_leaf, y_leaf, F_leaf, delta):
        """Line search (10.30) in one leaf; r_leaf are the pseudo-residuals of the leaf."""
        if self.loss == "ls":
            return float(np.mean(r_leaf))
        if self.loss == "lad":
            return float(np.median(y_leaf - F_leaf))
        if self.loss == "huber":
            res = y_leaf - F_leaf
            med = float(np.median(res))
            d = res - med
            return med + float(np.mean(np.sign(d) * np.minimum(delta, np.abs(d))))
        if self.loss == "bernoulli":
            p = y_leaf - r_leaf
            den = float(np.sum(p * (1 - p)))
            return float(np.sum(r_leaf)) / den if den > 1e-150 else 0.0
        raise ValueError(self.loss)

    def fit(self, X, y, evals=None, metrics=None, verbose=False):
        X = np.asarray(X, float)
        self.binner = Binner(X, self.max_bins)
        C = self.binner.code(X)
        N = X.shape[0]
        rng = np.random.default_rng(self.seed)
        evals = evals or {}
        metrics = metrics or {}
        multi = self.loss == "multinomial"
        if multi:
            K = self.K
            Y = np.eye(K)[y]
            self.f0 = np.zeros(K)
            F = np.zeros((N, K))
        else:
            self.f0 = self._init(y)
            F = np.full(N, self.f0)
        Fe = {k: (np.zeros((len(v[1]), self.K)) if multi else np.full(len(v[1]), self.f0)) for k, v in evals.items()}
        self.history = {k: {mn: [mf(v[1], Fe[k])] for mn, mf in metrics.items()} for k, v in evals.items()}
        self.history["train"] = {mn: [mf(y, F)] for mn, mf in metrics.items()}
        self.trees = []
        n_sub = int(math.floor(self.subsample * N))
        for m in range(1, self.M + 1):
            if self.subsample < 1:
                rows = np.sort(self.sampler(m, N, n_sub) if self.sampler else rng.choice(N, n_sub, replace=False))
            else:
                rows = np.arange(N)
            if multi:
                P = np.exp(F - F.max(1, keepdims=True))
                P /= P.sum(1, keepdims=True)
                trees_m = []
                for k in range(K):
                    r = Y[:, k] - P[:, k]
                    T, members = grow_tree(C, r, self.J, self.binner, rows)
                    for t, rr in members.items():
                        rk = r[rr]
                        den = float(np.sum(np.abs(rk) * (1 - np.abs(rk))))
                        T.value[t] = self.nu * (K - 1) / K * float(np.sum(rk)) / den if den > 1e-150 else 0.0
                    trees_m.append(T)
                for k, T in enumerate(trees_m):
                    F[:, k] += T.value[T.apply_codes(C)]
                    for name, (Xe, ye) in evals.items():
                        Fe[name][:, k] += T.predict(Xe)
                self.trees.append(trees_m)
            else:
                if self.loss == "ls":
                    r = y - F
                elif self.loss == "lad":
                    r = np.sign(y - F)
                elif self.loss == "huber":
                    res = y - F
                    delta = float(np.quantile(np.abs(res[rows]), self.huber_alpha))
                    r = np.where(np.abs(res) <= delta, res, delta * np.sign(res))
                elif self.loss == "bernoulli":
                    r = y - _sigmoid(F)
                delta = delta if self.loss == "huber" else None
                T, members = grow_tree(C, r, self.J, self.binner, rows)
                for t, rr in members.items():
                    T.value[t] = self.nu * self._leaf_value(r[rr], y[rr], F[rr], delta)
                F += T.value[T.apply_codes(C)]
                for name, (Xe, ye) in evals.items():
                    Fe[name] += T.predict(Xe)
                self.trees.append(T)
            for name, (Xe, ye) in evals.items():
                for mn, mf in metrics.items():
                    self.history[name][mn].append(mf(ye, Fe[name]))
            for mn, mf in metrics.items():
                self.history["train"][mn].append(mf(y, F))
            if verbose and m % 100 == 0:
                print("   iteration", m)
        for name in self.history:
            for mn in self.history[name]:
                self.history[name][mn] = np.array(self.history[name][mn])
        self.F_train = F
        return self

    def decision_function(self, X, M=None):
        """f_M(x) (log-odds for 'bernoulli'; N x K for 'multinomial')."""
        X = np.asarray(X, float)
        M = len(self.trees) if M is None else M
        if self.loss == "multinomial":
            F = np.zeros((X.shape[0], self.K))
            for trees_m in self.trees[:M]:
                for k, T in enumerate(trees_m):
                    F[:, k] += T.predict(X)
            return F
        F = np.full(X.shape[0], self.f0)
        for T in self.trees[:M]:
            F += T.predict(X)
        return F

    def tree_list(self, k=None, M=None):
        """The trees of the model (for class k in the K-class case)."""
        M = len(self.trees) if M is None else M
        if self.loss == "multinomial":
            return [t[k] for t in self.trees[:M]]
        return self.trees[:M]


# =========================================================================== interpretation (Section 10.13)
def relative_importance(trees, p):
    """(10.42)-(10.43): I_l^2 = (1/M) sum_m sum over the splits of tree m on input l of the
    squared-error improvement; returns the relevances sqrt(I_l^2) scaled so that the largest is 100."""
    I2 = np.zeros(p)
    for T in trees:
        internal = ~T.is_leaf
        np.add.at(I2, T.feat[internal], T.gain[internal])
    I2 /= max(len(trees), 1)
    rel = np.sqrt(I2)
    return 100 * rel / rel.max(), I2


def relative_importance_multiclass(model, p):
    """(10.45)-(10.46): per-class I_lk^2 and their class average I_l^2; both returned as relevances
    scaled to a maximum of 100 (per class, and overall)."""
    I2k = np.array([relative_importance(model.tree_list(k), p)[1] for k in range(model.K)])
    I2 = I2k.mean(0)
    per = 100 * np.sqrt(I2k) / np.sqrt(I2k).max(1, keepdims=True)
    return 100 * np.sqrt(I2) / np.sqrt(I2).max(), per


def pd_brute(predict, X, S, grid):
    """(10.48) by brute force: for each row g of grid (values of X_S), the average over the
    training rows of predict(x with x_S replaced by g)."""
    S = list(S)
    grid = np.atleast_2d(np.asarray(grid, float))
    if grid.shape[1] != len(S):
        grid = grid.T
    out = np.empty(grid.shape[0])
    Z = np.array(X, float, copy=True)
    for a, gv in enumerate(grid):
        Z[:, S] = gv
        out[a] = float(np.mean(predict(Z)))
    return out


def _cond_mask(X, cond):
    feat, thr, left = cond
    v = X[:, feat]
    go_left = (v <= thr) | np.isnan(v)
    return go_left if left else ~go_left


def pd_trees(trees, X, S, grid, f0=0.0):
    """Exercise 10.11, exact and fast: for a sum of trees, (10.48) equals
    f0 + sum over trees and leaves of value(leaf) * [x_S satisfies the leaf's conditions on S]
    * (fraction of training rows whose x_C satisfies the leaf's conditions on C).
    The fractions need one pass over the data per tree and do not depend on x_S."""
    Sl = list(S)
    S = set(Sl)
    grid = np.atleast_2d(np.asarray(grid, float))
    if grid.shape[1] != len(Sl):
        grid = grid.T
    G = np.full((grid.shape[0], X.shape[1]), np.nan)
    G[:, Sl] = grid
    out = np.full(grid.shape[0], float(f0))
    for T in trees:
        for leaf, conds in T.paths().items():
            cC = [c for c in conds if c[0] not in S]
            cS = [c for c in conds if c[0] in S]
            mass = 1.0
            if cC:
                ok = np.ones(X.shape[0], bool)
                for c in cC:
                    ok &= _cond_mask(X, c)
                mass = ok.mean()
            if mass == 0:
                continue
            inS = np.ones(grid.shape[0], bool)
            for c in cS:
                inS &= _cond_mask(G, c)
            out += T.value[leaf] * mass * inS
    return out


def pd_traversal(trees, S, grid, f0=0.0):
    """Partial dependence from the trees alone (Friedman 2001): send the point down each tree; at
    a split on an input in S follow its branch, at a split on an input in C follow both branches
    with weights n(child)/n(node). Exact for (10.48) only in special cases (see the notes)."""
    S = list(S)
    grid = np.atleast_2d(np.asarray(grid, float))
    if grid.shape[1] != len(S):
        grid = grid.T
    pos = {s: a for a, s in enumerate(S)}
    out = np.full(grid.shape[0], float(f0))
    for T in trees:
        stack = [(0, np.ones(grid.shape[0]))]
        while stack:
            t, wt = stack.pop()
            if T.is_leaf[t]:
                out += wt * T.value[t]
                continue
            j = T.feat[t]
            if j in pos:
                gl = grid[:, pos[j]] <= T.thr[t]
                stack.append((T.left[t], wt * gl))
                stack.append((T.right[t], wt * ~gl))
            else:
                nl, nr = T.n[T.left[t]], T.n[T.right[t]]
                stack.append((T.left[t], wt * nl / (nl + nr)))
                stack.append((T.right[t], wt * nr / (nl + nr)))
    return out


def conditional_expectation_bins(x, fvals):
    """(10.49) estimated by binning: cut x at its distinct deciles; for each non-empty bin return the
    mean of x and the mean of f(x_i) over the training rows in the bin."""
    edges = np.unique(np.quantile(x, np.arange(1, 10) / 10))
    b = np.searchsorted(edges, x, side="right")
    xm, fm = [], []
    for k in range(len(edges) + 1):
        sel = b == k
        if sel.any():
            xm.append(float(np.mean(x[sel])))
            fm.append(float(np.mean(fvals[sel])))
    return np.array(xm), np.array(fm)


def interaction_h(trees, X, j, k, rows, f0=0.0):
    """Friedman and Popescu's H statistic for the pair (j, k), evaluated at the training rows `rows`:
    H^2 = sum (PD_jk - PD_j - PD_k)^2 / sum PD_jk^2, each partial dependence centred over those rows.
    It is 0 exactly when the two-variable partial dependence is additive."""
    Z = X[rows]
    pjk = pd_trees(trees, X, [j, k], Z[:, [j, k]], f0)
    pj = pd_trees(trees, X, [j], Z[:, j], f0)
    pk = pd_trees(trees, X, [k], Z[:, k], f0)
    pjk, pj, pk = pjk - pjk.mean(), pj - pj.mean(), pk - pk.mean()
    return float(np.sqrt(np.sum((pjk - pj - pk) ** 2) / np.sum(pjk ** 2)))


def deciles(x):
    return np.quantile(x, np.arange(1, 10) / 10)


# pickled models refer to this module by name, also when it is run as a script
for _cls in (StumpFitter, Binner, Tree, GradientBoosting):
    _cls.__module__ = "ch10_boosting"


# =========================================================================== caching
def _cache(name, build):
    os.makedirs(CACHE_DIR, exist_ok=True)
    path = os.path.join(CACHE_DIR, name)
    if os.path.exists(path):
        with open(path, "rb") as f:
            return pickle.load(f)
    obj = build()
    with open(path + ".part", "wb") as f:
        pickle.dump(obj, f, protocol=4)
    os.replace(path + ".part", path)
    return obj


# =========================================================================== the simulation (10.2): models
def _err01(y, F):
    return float(np.mean((F > 0) != y))


def spheres_models():
    """All the boosting runs on (10.2) used by Figures 10.2, 10.3, 10.9-10.12 (cached)."""
    def build():
        from sklearn.tree import DecisionTreeClassifier
        Xtr, ytr, Xte, yte = spheres_train_test()
        y01, yte01 = (ytr > 0).astype(int), (yte > 0).astype(int)
        R = {}
        ab = adaboost_m1(Xtr, ytr, 2000, Xte, yte)
        R["ab"] = {k: ab[k] for k in ("train_err", "test_err", "exp_loss", "err", "alpha")}
        R["ab"]["stumps"] = ab["stumps"]
        rb = real_adaboost_stumps(Xtr, ytr, 400, Xte, yte)
        R["real"] = {k: rb[k] for k in ("train_err", "test_err", "exp_loss")}
        big = DecisionTreeClassifier(max_leaf_nodes=244, random_state=0).fit(Xtr, ytr)
        R["tree244"] = float(np.mean(big.predict(Xte) != yte))
        R["stump"] = float(ab["test_err"][0])
        met = {"err": _err01, "dev": deviance_binomial}
        ev = {"test": (Xte, yte01)}

        def gb(loss, J, nu, M, sub=1.0, y=y01, yt=yte01, metrics=met, seed=12):
            g = GradientBoosting(loss, J=J, nu=nu, M=M, subsample=sub, seed=seed).fit(Xtr, y, evals={"test": (Xte, yt)}, metrics=metrics)
            return g
        R["J"] = {}
        for J in (2, 10, 100):
            g = gb("bernoulli", J, 1.0, 400)
            R["J"][J] = g.history["test"]["err"]
            if J == 2:
                R["stump_model"] = [(T.feat[0], T.thr[0], T.value[T.left[0]], T.value[T.right[0]]) for T in g.trees]
                R["stump_f0"] = g.f0
        R["shrink"] = {}
        for J, nus in ((2, (0.2,)), (6, (0.6, 0.06))):
            for v in (1.0,) + nus:
                g = gb("bernoulli", J, v, 2000)
                R["shrink"][(J, v)] = {"dev": g.history["test"]["dev"], "err": g.history["test"]["err"]}
        R["sub"] = {}
        absm = {"abs": lambda y, F: float(np.mean(np.abs(y - F)))}
        for nu, sub in ((1.0, 1.0), (0.1, 1.0), (1.0, 0.5), (0.1, 0.5)):
            g = gb("bernoulli", 4, nu, 1000, sub)
            g2 = gb("ls", 4, nu, 1000, sub, y=y01.astype(float), yt=yte01.astype(float), metrics=absm)
            R["sub"][(nu, sub)] = {"dev": g.history["test"]["dev"], "abs": g2.history["test"]["abs"]}
        return R
    return _cache("ch10_spheres.pkl", build)


def exercise_10_4():
    """Exercise 10.4(c)-(d): a long AdaBoost.M1 run on (10.2), and AdaBoost on overlapping classes."""
    def build():
        Xtr, ytr, Xte, yte = spheres_train_test()
        long = adaboost_m1(Xtr, ytr, 10000, Xte, yte)
        Xo, yo = overlap_spheres(2000, 16)
        Xot, yot = overlap_spheres(10000, 17)
        ov = adaboost_m1(Xo, yo, 5000, Xot, yot)
        gbo = GradientBoosting("bernoulli", J=2, nu=0.1, M=5000).fit(Xo, (yo > 0).astype(int), evals={"test": (Xot, (yot > 0).astype(int))},
                                                                     metrics={"err": _err01})
        from scipy.stats import chi2
        bayes = 0.5 * chi2.sf(12.0, 10)
        return {"long": {k: long[k] for k in ("train_err", "test_err", "exp_loss")},
                "overlap": {k: ov[k] for k in ("train_err", "test_err", "exp_loss")}, "bayes": bayes,
                "overlap_gb": gbo.history["test"]["err"][1:], "overlap_gb_train": gbo.history["train"]["err"][1:]}
    return _cache("ch10_ex10_4.pkl", build)


# =========================================================================== figures: the simulation
def _iters(n, start=1):
    return np.arange(start, start + n)


def fig_10_2(out_dir=None):
    """Test error of AdaBoost with stumps on the simulation (10.2)."""
    import matplotlib.pyplot as plt
    R = spheres_models()
    fig, ax = plt.subplots(figsize=(5.2, 4.0))
    ax.plot(_iters(400), R["ab"]["test_err"][:400], color=ORANGE, lw=1.4, label="AdaBoost.M1 (Algorithm 10.1)")
    ax.plot(_iters(400), R["real"]["test_err"][:400], color=BLUE, lw=1.4, ls="--", label="stumps with leaf values (10.32)")
    for v, lab in ((R["stump"], "Single stump"), (R["tree244"], "244-node tree")):
        ax.axhline(v, color=GREY, ls=":", lw=1)
        ax.text(200, v + 0.008, lab, ha="center", fontsize=9)
    ax.set_xlabel("Boosting iterations")
    ax.set_ylabel("Test error")
    ax.set_xlim(-5, 405)
    ax.set_ylim(0, 0.5)
    ax.legend(frameon=False, loc="upper right", bbox_to_anchor=(1, 0.83), fontsize=8.5)
    print("  single stump %.4f, 244-node tree %.4f, AdaBoost.M1 at 400 %.4f, real-valued stumps at 400 %.4f (at 250: %.4f)"
          % (R["stump"], R["tree244"], R["ab"]["test_err"][399], R["real"]["test_err"][399], R["real"]["test_err"][249]))
    savefig(fig, CH, "fig10-2", out_dir)


def fig_10_3(out_dir=None):
    """Training misclassification rate and exponential loss of AdaBoost with stumps."""
    import matplotlib.pyplot as plt
    R = spheres_models()
    fig, ax = plt.subplots(figsize=(5.2, 4.0))
    ax.plot(_iters(400), R["ab"]["train_err"][:400], color=ORANGE, lw=1.4, label="misclassification rate")
    ax.plot(_iters(400), R["ab"]["exp_loss"][:400], color=CYAN, lw=1.4, label="exponential loss")
    ax.plot(_iters(400), R["real"]["train_err"][:400], color=ORANGE, lw=1.1, ls="--", label="misclassification, leaf values (10.32)")
    ax.plot(_iters(400), R["real"]["exp_loss"][:400], color=CYAN, lw=1.1, ls="--", label="exponential loss, leaf values (10.32)")
    ax.set_xlabel("Boosting iterations")
    ax.set_ylabel("Training error")
    ax.set_ylim(0, 1)
    ax.legend(frameon=False, fontsize=8.5)
    z = np.nonzero(R["real"]["train_err"] == 0)[0]
    print("  AdaBoost.M1: training error at 250 / 400 = %.4f / %.4f, exp loss %.4f; real-valued stumps: first zero training error at %s"
          % (R["ab"]["train_err"][249], R["ab"]["train_err"][399], R["ab"]["exp_loss"][399], z[0] + 1 if len(z) else None))
    savefig(fig, CH, "fig10-3", out_dir)


def fig_10_9(out_dir=None):
    """Boosting (binomial deviance) with trees of different sizes on (10.2), and AdaBoost."""
    import matplotlib.pyplot as plt
    R = spheres_models()
    fig, ax = plt.subplots(figsize=(5.2, 4.2))
    for J, c, lab in ((2, GREEN, "Stumps"), (10, CYAN, "10 node"), (100, ORANGE, "100 node")):
        ax.plot(_iters(400), R["J"][J][1:], color=c, lw=1.3, label=lab)
    ax.plot(_iters(400), R["ab"]["test_err"][:400], color=GREY, lw=1.0, label="AdaBoost.M1 (stumps)")
    ax.set_xlabel("Number of terms")
    ax.set_ylabel("Test error")
    ax.set_ylim(0, 0.45)
    ax.legend(frameon=False)
    print("  test error at 400 terms: stumps %.4f, 10-node %.4f, 100-node %.4f, AdaBoost %.4f"
          % (R["J"][2][400], R["J"][10][400], R["J"][100][400], R["ab"]["test_err"][399]))
    savefig(fig, CH, "fig10-9", out_dir)


def fig_10_10(out_dir=None):
    """Coordinate functions f_j(x_j) of the boosted-stumps model of Figure 10.9."""
    import matplotlib.pyplot as plt
    R = spheres_models()
    Xtr, ytr, _, _ = spheres_train_test()
    grid = np.linspace(-3.5, 3.5, 701)
    fig, axes = plt.subplots(2, 5, figsize=(10.0, 4.2), sharey=True)
    out = []
    for j in range(10):
        f = np.zeros_like(grid)
        ftr = np.zeros(len(ytr))
        for (jj, t, vl, vr) in R["stump_model"]:
            if jj == j:
                f += np.where(grid <= t, vl, vr)
                ftr += np.where(Xtr[:, j] <= t, vl, vr)
        c0 = ftr.mean()
        f -= c0
        ftr -= c0
        q = Xtr[:, j] ** 2 - 1
        b = float(q @ ftr / (q @ q))     # least-squares scale of the quadratic x^2 - 1
        ax = axes.flat[j]
        ax.plot(grid, f, color=BLUE, lw=1.3, drawstyle="steps-post")
        ax.plot(grid, b * (grid ** 2 - 1), color=RED, lw=0.9)
        ax.set_title(r"$f_{%d}(x_{%d})$" % (j + 1, j + 1), fontsize=10)
        ax.set_xticks([-2, 0, 2])
        ax.set_ylim(-3, 6)
        out.append(b)
    fig.suptitle("Coordinate functions for additive logistic trees", fontsize=10.5)
    fig.tight_layout()
    print("  least-squares scale of x_j^2 - 1 per coordinate:", np.round(out, 3))
    savefig(fig, CH, "fig10-10", out_dir)


def fig_10_11(out_dir=None):
    """Shrinkage: test deviance and misclassification error for stumps and 6-node trees."""
    import matplotlib.pyplot as plt
    R = spheres_models()
    fig, axes = plt.subplots(2, 2, figsize=(8.6, 7.0))
    for row, (J, nu, name) in enumerate(((2, 0.2, "Stumps"), (6, 0.6, "6-node trees"))):
        for col, (key, ylab, ylim) in enumerate((("dev", "Test set deviance", 2.0), ("err", "Test set misclassification error", 0.5))):
            ax = axes[row, col]
            curves = [(1.0, RED, "No shrinkage"), (nu, BLUE, "Shrinkage = %g" % nu)]
            if J == 6:
                curves.append((0.06, GREEN, "Shrinkage = 0.06"))
            for v, c, lab in curves:
                h = R["shrink"][(J, v)][key]
                ax.plot(np.arange(len(h)), h, color=c, lw=1.2, label=lab)
            ax.set_ylim(0, ylim)
            ax.set_xlabel("Boosting iterations")
            ax.set_ylabel(ylab)
            ax.set_title("%s: %s" % (name, "deviance" if key == "dev" else "misclassification error"))
            ax.legend(frameon=False)
    fig.tight_layout()
    for (J, v), h in R["shrink"].items():
        print("  J=%d nu=%g: min test deviance %.4f at %d, deviance at 2000 %.4f, error at 2000 %.4f"
              % (J, v, h["dev"].min(), h["dev"].argmin(), h["dev"][-1], h["err"][-1]))
    savefig(fig, CH, "fig10-11", out_dir)


def fig_10_12(out_dir=None):
    """Subsampling and shrinkage with 4-node trees: test deviance and test absolute error."""
    import matplotlib.pyplot as plt
    R = spheres_models()
    fig, axes = plt.subplots(1, 2, figsize=(9.0, 3.9))
    styles = {(1.0, 1.0): (ORANGE, "No shrinkage"), (0.1, 1.0): (CYAN, "Shrink = 0.1"),
              (1.0, 0.5): (BLUE, "Sample = 0.5"), (0.1, 0.5): ("#333333", "Shrink = 0.1, Sample = 0.5")}
    for ax, key, ylab, ylim, title in ((axes[0], "dev", "Test set deviance", (0.3, 1.5), "Deviance"),
                                       (axes[1], "abs", "Test set absolute error", (0.25, 0.5), "Absolute error")):
        for k, (c, lab) in styles.items():
            h = R["sub"][k][key]
            ax.plot(np.arange(len(h)), h, color=c, lw=1.2, label=lab)
        ax.set_ylim(*ylim)
        ax.set_xlabel("Boosting iterations")
        ax.set_ylabel(ylab)
        ax.set_title(title)
    axes[1].legend(frameon=False, fontsize=8.5)
    fig.suptitle("4-node trees", fontsize=10.5)
    fig.tight_layout()
    for k, h in R["sub"].items():
        print("  nu=%g sample=%g: min deviance %.4f at %d (%.4f at 1000); min abs error %.4f at %d (%.4f at 1000)"
              % (k[0], k[1], h["dev"].min(), h["dev"].argmin(), h["dev"][-1], h["abs"].min(), h["abs"].argmin(), h["abs"][-1]))
    savefig(fig, CH, "fig10-12", out_dir)


def fig_10_s1(out_dir=None):
    """Supplementary (Exercise 10.4): long AdaBoost run on (10.2); overlapping classes (10.4(d))."""
    import matplotlib.pyplot as plt
    E = exercise_10_4()
    fig, axes = plt.subplots(1, 2, figsize=(9.4, 3.8))
    L = E["long"]
    it = _iters(len(L["test_err"]))
    axes[0].plot(it, L["train_err"], color=GREEN, lw=1.1, label="training error")
    axes[0].plot(it, L["test_err"], color=ORANGE, lw=1.2, label="test error")
    axes[0].set_xscale("log")
    axes[0].set_ylim(0, 0.5)
    axes[0].set_title("(10.2): 10,000 rounds of AdaBoost.M1")
    O = E["overlap"]
    it2 = _iters(len(O["test_err"]))
    axes[1].plot(it2, O["train_err"], color=GREEN, lw=1.1, label="training error")
    axes[1].plot(it2, O["test_err"], color=ORANGE, lw=1.2, label="test error")
    axes[1].plot(it2, E["overlap_gb"], color=BLUE, lw=1.1, ls="--", label="test error, deviance stumps, $\\nu=0.1$")
    axes[1].axhline(E["bayes"], color=GREY, ls=":", lw=1)
    axes[1].text(1.5, E["bayes"] + 0.01, "Bayes error %.3f" % E["bayes"], fontsize=9)
    axes[1].set_xscale("log")
    axes[1].set_ylim(0, 0.5)
    axes[1].set_title("Exercise 10.4(d): overlapping classes")
    for ax in axes:
        ax.set_xlabel("Boosting iterations (log scale)")
        ax.set_ylabel("Error rate")
        ax.legend(frameon=False)
    fig.tight_layout()
    a = int(np.argmin(L["test_err"]))
    b = int(np.argmin(O["test_err"]))
    print("  long run: min test error %.4f at %d, at 10000 %.4f, training error at 10000 %.4f, first zero training error %s"
          % (L["test_err"][a], a + 1, L["test_err"][-1], L["train_err"][-1], (np.nonzero(L["train_err"] == 0)[0][:1] + 1).tolist()))
    print("  overlap: min test error %.4f at %d, at 5000 %.4f, training error at 5000 %.4f, Bayes %.4f"
          % (O["test_err"][b], b + 1, O["test_err"][-1], O["train_err"][-1], E["bayes"]))
    g = E["overlap_gb"]
    print("  overlap, binomial deviance stumps nu=0.1: min test error %.4f at %d, at 5000 %.4f, training error at 5000 %.4f"
          % (g.min(), g.argmin() + 1, g[-1], E["overlap_gb_train"][-1]))
    savefig(fig, CH, "fig10-S1", out_dir)


# =========================================================================== figures: loss functions
def fig_10_4(out_dir=None):
    """Loss functions for two-class classification against the margin y f."""
    import matplotlib.pyplot as plt
    m = np.linspace(-2, 2, 801)
    fig, ax = plt.subplots(figsize=(5.2, 4.0))
    ax.plot(m, loss_misclass(m), color=GREY, lw=1.4, drawstyle="steps-mid", label="Misclassification")
    ax.plot(m, loss_exponential(m), color=CYAN, lw=1.4, label="Exponential")
    ax.plot(m, loss_deviance(m) / math.log(2), color=ORANGE, lw=1.4, label="Binomial deviance")
    ax.plot(m, loss_squared_margin(m), color=RED, lw=1.4, label="Squared error")
    ax.plot(m, loss_hinge(m), color=BLUE, lw=1.4, label="Support vector")
    ax.set_ylim(0, 3)
    ax.set_xlabel(r"$y\cdot f$")
    ax.set_ylabel("Loss")
    ax.legend(frameon=False)
    savefig(fig, CH, "fig10-4", out_dir)


def fig_10_5(out_dir=None):
    """Squared, absolute and Huber loss for regression against y - f."""
    import matplotlib.pyplot as plt
    r = np.linspace(-3, 3, 601)
    fig, ax = plt.subplots(figsize=(5.2, 4.0))
    ax.plot(r, r ** 2, color=ORANGE, lw=1.4, label="Squared error")
    ax.plot(r, np.abs(r), color=CYAN, lw=1.4, label="Absolute error")
    ax.plot(r, huber(r, 1.0), color=GREEN, lw=1.4, label=r"Huber ($\delta=1$)")
    ax.set_ylim(0, 9)
    ax.set_xlabel(r"$y-f$")
    ax.set_ylabel("Loss")
    ax.legend(frameon=False)
    savefig(fig, CH, "fig10-5", out_dir)



# =========================================================================== spam data (Section 10.8)
def cv_folds(N, K, seed):
    perm = np.random.default_rng(seed).permutation(N)
    return [perm[k::K] for k in range(K)]


def spam_models():
    """Gradient boosting with binomial deviance on the spam data, J = 5 and J = 2, nu = 0.1, M chosen
    by 5-fold cross-validated deviance (cached). Returns a dict per J with the model (truncated at the
    chosen M), the CV curve, the test curves and the test error."""
    def build():
        Xtr, ytr, Xte, yte = spam()
        out = {}
        for J, Mmax in ((5, 1000), (2, 2000)):
            cv = np.zeros(Mmax + 1)
            for k, fold in enumerate(cv_folds(len(ytr), 5, 13)):
                tr = np.setdiff1d(np.arange(len(ytr)), fold)
                g = GradientBoosting("bernoulli", J=J, nu=0.1, M=Mmax).fit(Xtr[tr], ytr[tr], evals={"v": (Xtr[fold], ytr[fold])},
                                                                         metrics={"dev": deviance_binomial})
                cv += g.history["v"]["dev"] * len(fold) / len(ytr)
            Mstar = int(np.argmin(cv))
            g = GradientBoosting("bernoulli", J=J, nu=0.1, M=Mmax).fit(Xtr, ytr, evals={"test": (Xte, yte)},
                                                                     metrics={"dev": deviance_binomial, "err": _err01})
            hist = g.history
            g.trees = g.trees[:Mstar]
            out[J] = {"model": g, "M": Mstar, "cv": cv, "test_dev": hist["test"]["dev"], "test_err": hist["test"]["err"],
                      "err": float(hist["test"]["err"][Mstar]), "pred_test": (g.decision_function(Xte) > 0).astype(int)}
        return out
    return _cache("ch10_spam.pkl", build)


def mcnemar(b, c):
    """McNemar's test from the two discordant counts: chi-squared statistic (b - c)^2 / (b + c) on
    1 df (no continuity correction), its p-value, the corrected version and the exact binomial p."""
    from scipy.stats import chi2, binom
    x2 = (b - c) ** 2 / (b + c)
    x2c = (abs(b - c) - 1) ** 2 / (b + c)
    exact = min(1.0, 2 * binom.cdf(min(b, c), b + c, 0.5))
    return x2, chi2.sf(x2, 1), x2c, chi2.sf(x2c, 1), exact


def _pd_grid(x, n=60, qhi=0.98):
    return np.linspace(0.0 if x.min() >= 0 else x.min(), np.quantile(x, qhi), n)


def _rug(ax, x):
    for d in deciles(x):
        ax.axvline(d, ymin=0, ymax=0.04, color=RED, lw=1.2)


def fig_10_6(out_dir=None):
    """Relative importance of the 57 predictors for the spam data (J = 5 model)."""
    import matplotlib.pyplot as plt
    S = spam_models()
    g = S[5]["model"]
    rel, _ = relative_importance(g.trees, 57)
    o = np.argsort(rel)
    fig, ax = plt.subplots(figsize=(4.8, 8.6))
    ax.barh(np.arange(57), rel[o], color=RED, height=0.7)
    ax.set_yticks(np.arange(57))
    ax.set_yticklabels([SPAM_NAMES[k] for k in o], fontsize=7)
    ax.set_ylim(-0.7, 56.7)
    ax.set_xlabel("Relative importance")
    ax.set_xlim(0, 100)
    print("  J=5: M chosen by CV = %d, test error %.4f; J=2: M = %d, test error %.4f"
          % (S[5]["M"], S[5]["err"], S[2]["M"], S[2]["err"]))
    print("  top 6:", [(SPAM_NAMES[k], round(float(rel[k]), 1)) for k in o[::-1][:6]], " bottom 4:", [SPAM_NAMES[k] for k in o[:4]])
    savefig(fig, CH, "fig10-6", out_dir)
    export_demo_data()


SPAM_PD_VARS = ("!", "remove", "edu", "hp")


def spam_pd_curves(J=5, n=60):
    S = spam_models()
    Xtr = spam()[0]
    g = S[J]["model"]
    out = {}
    for name in SPAM_PD_VARS:
        j = SPAM_NAMES.index(name)
        grid = _pd_grid(Xtr[:, j], n)
        pd = pd_trees(g.trees, Xtr, [j], grid, g.f0)
        centre = float(np.mean(pd_trees(g.trees, Xtr, [j], Xtr[:, j], g.f0)))
        out[name] = (grid, pd - centre)
    return out


def fig_10_7(out_dir=None):
    """Partial dependence of the log-odds of spam on four predictors."""
    import matplotlib.pyplot as plt
    Xtr = spam()[0]
    P = spam_pd_curves()
    fig, axes = plt.subplots(2, 2, figsize=(7.6, 6.0))
    for ax, name in zip(axes.flat, SPAM_PD_VARS):
        grid, pd = P[name]
        ax.plot(grid, pd, color=GREEN, lw=1.4, drawstyle="steps-post")
        _rug(ax, Xtr[:, SPAM_NAMES.index(name)])
        ax.set_xlabel(name)
        ax.set_ylabel("Partial dependence")
        print("  %s: partial dependence from %.3f to %.3f" % (name, pd.min(), pd.max()))
    fig.tight_layout()
    savefig(fig, CH, "fig10-7", out_dir)


def fig_10_8(out_dir=None):
    """Two-variable partial dependence of the log-odds of spam on hp and !."""
    import matplotlib.pyplot as plt
    S = spam_models()
    Xtr = spam()[0]
    g = S[5]["model"]
    jh, je = SPAM_NAMES.index("hp"), SPAM_NAMES.index("!")
    gh, ge = np.linspace(0, 3, 31), np.linspace(0, 1, 26)
    H, E = np.meshgrid(gh, ge)
    pd = pd_trees(g.trees, Xtr, [jh, je], np.c_[H.ravel(), E.ravel()], g.f0).reshape(H.shape)
    pd -= np.mean(pd_trees(g.trees, Xtr, [jh, je], Xtr[:, [jh, je]], g.f0))
    fig = plt.figure(figsize=(6.4, 5.0))
    ax = fig.add_subplot(111, projection="3d")
    ax.plot_surface(H, E, pd, cmap="cool", edgecolor="k", linewidth=0.2, rstride=1, cstride=1, alpha=0.95)
    ax.set_xlabel("hp")
    ax.set_ylabel("!")
    ax.set_zlabel("partial dependence")
    ax.view_init(elev=28, azim=125)
    print("  2-D partial dependence ranges from %.3f to %.3f" % (pd.min(), pd.max()))
    savefig(fig, CH, "fig10-8", out_dir)


def _compact(a, d=4):
    return [float(round(float(v), d)) for v in a]


def export_demo_data():
    """Data for the browser demonstrations: the spam training set and the two fitted models
    (trees as flat arrays) for the partial-dependence demo."""
    os.makedirs(DATA_OUT, exist_ok=True)
    S = spam_models()
    Xtr, ytr, Xte, yte = spam()
    used = sorted(set().union(*[set(T.feat[~T.is_leaf].tolist()) for J in (5, 2) for T in S[J]["model"].trees]))
    models = {}
    for J in (5, 2):
        g = S[J]["model"]
        trees = []
        for T in g.trees:
            trees.append({"f": T.feat.tolist(), "t": [None if np.isnan(v) else float(v) for v in T.thr],
                          "l": T.left.tolist(), "r": T.right.tolist(), "v": [float(repr_round(v)) for v in T.value],
                          "n": T.n.tolist()})
        rel, I2 = relative_importance(g.trees, 57)
        models[str(J)] = {"J": J, "M": S[J]["M"], "f0": g.f0, "trees": trees, "test_err": S[J]["err"],
                          "rel": _compact(rel, 3)}
    # the inputs: values of the spam data have at most 3 decimals (CAPAVE) and are stored exactly
    cols = {SPAM_NAMES[j]: [float(v) if v != int(v) else int(v) for v in Xtr[:, j]] for j in range(57)}
    D = {"names": SPAM_NAMES, "X": cols, "y": ytr.tolist(), "models": models, "used": used,
         "note": "Spam training set (3065 e-mails, book split) and gradient-boosted models, binomial deviance, nu = 0.1, "
                 "J = 5 and J = 2 leaves, M chosen by 5-fold cross-validation (Hastie, Tibshirani and Friedman 2009, Section 10.8)."}
    path = os.path.join(DATA_OUT, "ch10-spam-gbm.json")
    with open(path, "w") as f:
        json.dump(D, f, separators=(",", ":"))
    print("  wrote", os.path.relpath(path, os.getcwd()), "(%.0f kB)" % (os.path.getsize(path) / 1024))


def repr_round(v):
    """Round to 12 significant digits (the demo reproduces the Python values to about 1e-10)."""
    return float("%.12g" % v)


# =========================================================================== California housing (Section 10.14.1)
def california_model():
    def build():
        Xtr, ytr, Xte, yte = california()
        aae = {"aae": lambda y, F: float(np.mean(np.abs(y - F)))}
        g = GradientBoosting("huber", J=6, nu=0.1, M=800, huber_alpha=0.9).fit(Xtr, ytr, evals={"test": (Xte, yte)}, metrics=aae)
        F = g.decision_function(Xte)
        r2 = 1 - np.mean((yte - F) ** 2) / np.var(yte)
        gl = GradientBoosting("huber", J=6, nu=0.1, M=800, huber_alpha=0.9).fit(Xtr, np.log(ytr))
        Fl = gl.decision_function(Xte)
        r2log = 1 - np.mean((np.log(yte) - Fl) ** 2) / np.var(np.log(yte))
        return {"model": g, "hist": g.history, "r2": float(r2), "r2log": float(r2log),
                "aae_median": float(np.mean(np.abs(yte - np.median(ytr))))}
    return _cache("ch10_california.pkl", build)


def fig_10_13(out_dir=None):
    """Training and test average absolute error against M for the California housing data."""
    import matplotlib.pyplot as plt
    C = california_model()
    h = C["hist"]
    fig, ax = plt.subplots(figsize=(5.4, 4.0))
    ax.plot(np.arange(len(h["train"]["aae"])), h["train"]["aae"], color=GREEN, lw=1.3, label="Train error")
    ax.plot(np.arange(len(h["test"]["aae"])), h["test"]["aae"], color=ORANGE, lw=1.3, label="Test error")
    ax.set_xlabel("Iterations M")
    ax.set_ylabel("Absolute error")
    ax.set_title("Training and test absolute error")
    ax.set_ylim(0, 0.9)
    ax.legend(frameon=False)
    print("  AAE at M=800: train %.3f, test %.3f; median predictor %.3f; R^2 = %.3f; log-scale R^2 = %.3f"
          % (h["train"]["aae"][-1], h["test"]["aae"][-1], C["aae_median"], C["r2"], C["r2log"]))
    savefig(fig, CH, "fig10-13", out_dir)


def fig_10_14(out_dir=None):
    """Relative importance of the predictors for the California housing data."""
    import matplotlib.pyplot as plt
    g = california_model()["model"]
    rel, _ = relative_importance(g.trees, 8)
    o = np.argsort(rel)
    fig, ax = plt.subplots(figsize=(5.0, 3.4))
    ax.barh(np.arange(8), rel[o], color=RED, height=0.65)
    ax.set_yticks(np.arange(8))
    ax.set_yticklabels([CAL_NAMES[k] for k in o])
    ax.set_xlabel("Relative importance")
    ax.set_xlim(0, 100)
    print("  ", [(CAL_NAMES[k], round(float(rel[k]), 1)) for k in o[::-1]])
    savefig(fig, CH, "fig10-14", out_dir)


CAL_PD = (("MedInc", (1.0, 10.0)), ("AveOccup", (1.5, 5.0)), ("HouseAge", (2.0, 52.0)), ("AveRooms", (2.5, 10.0)))


def fig_10_15(out_dir=None):
    """Partial dependence of house value on the non-location variables."""
    import matplotlib.pyplot as plt
    g = california_model()["model"]
    Xtr = california()[0]
    fig, axes = plt.subplots(2, 2, figsize=(7.6, 6.0), sharey=True)
    for ax, (name, (lo, hi)) in zip(axes.flat, CAL_PD):
        j = CAL_NAMES.index(name)
        grid = np.linspace(lo, hi, 120)
        pd = pd_trees(g.trees, Xtr, [j], grid, g.f0)
        centre = float(np.mean(pd_trees(g.trees, Xtr, [j], Xtr[:, j], g.f0)))
        ax.plot(grid, pd - centre, color=GREEN, lw=1.4, drawstyle="steps-post")
        for d in deciles(Xtr[:, j]):
            if lo <= d <= hi:
                ax.axvline(d, ymin=0, ymax=0.04, color=RED, lw=1.2)
        ax.set_xlabel(name)
        ax.set_ylabel("Partial dependence")
        ax.set_ylim(-1.0, 2.0)
        print("  %s: %.3f to %.3f" % (name, (pd - centre).min(), (pd - centre).max()))
    fig.tight_layout()
    savefig(fig, CH, "fig10-15", out_dir)


def fig_10_16(out_dir=None):
    """Two-variable partial dependence of house value on HouseAge and AveOccup."""
    import matplotlib.pyplot as plt
    g = california_model()["model"]
    Xtr = california()[0]
    ja, jo = CAL_NAMES.index("HouseAge"), CAL_NAMES.index("AveOccup")
    go_, ga = np.linspace(1.5, 5.0, 36), np.linspace(2, 52, 26)
    O, A = np.meshgrid(go_, ga)
    pd = pd_trees(g.trees, Xtr, [jo, ja], np.c_[O.ravel(), A.ravel()], g.f0).reshape(O.shape)
    pd -= np.mean(pd_trees(g.trees, Xtr, [jo, ja], Xtr[:, [jo, ja]], g.f0))
    fig = plt.figure(figsize=(6.2, 4.9))
    ax = fig.add_subplot(111, projection="3d")
    ax.plot_surface(O, A, pd, cmap="cool", edgecolor="k", linewidth=0.2, alpha=0.95)
    ax.set_xlabel("AveOccup")
    ax.set_ylabel("HouseAge")
    ax.set_zlabel("partial dependence")
    ax.view_init(elev=25, azim=-130)
    lo, hi = pd[:, go_ < 2].ptp(axis=0).mean(), pd[:, go_ > 3].ptp(axis=0).mean()
    print("  range over HouseAge: %.3f for AveOccup < 2, %.3f for AveOccup > 3" % (lo, hi))
    savefig(fig, CH, "fig10-16", out_dir)


def fig_10_17(out_dir=None):
    """Partial dependence of house value on location, evaluated at every block group."""
    import matplotlib.pyplot as plt
    g = california_model()["model"]
    Xtr, ytr, Xte, yte = california()
    jl, jo = CAL_NAMES.index("Longitude"), CAL_NAMES.index("Latitude")
    Xall = np.vstack([Xtr, Xte])
    pts = np.unique(Xall[:, [jl, jo]], axis=0)
    pd = pd_trees(g.trees, Xtr, [jl, jo], pts, g.f0)
    pd -= np.mean(pd_trees(g.trees, Xtr, [jl, jo], Xtr[:, [jl, jo]], g.f0))
    fig, ax = plt.subplots(figsize=(5.6, 5.4))
    sc = ax.scatter(pts[:, 0], pts[:, 1], c=np.clip(pd, -1, 1), s=2, cmap="cool", vmin=-1, vmax=1, rasterized=True)
    fig.colorbar(sc, ax=ax, shrink=0.8)
    ax.set_xlabel("Longitude")
    ax.set_ylabel("Latitude")
    ax.set_aspect(1.2)
    print("  %d locations; partial dependence from %.3f to %.3f" % (len(pts), pd.min(), pd.max()))
    savefig(fig, CH, "fig10-17", out_dir)


# =========================================================================== demographics data (Section 10.14.3)
def marketing_model():
    """Algorithm 10.4 (K = 9 occupations), J = 6, nu = 0.1, M chosen by 5-fold cross-validated
    multinomial deviance on the training set (cached)."""
    def build():
        Xtr, ytr, Xte, yte, names = marketing()
        Mmax = 200
        cv = np.zeros(Mmax + 1)
        for fold in cv_folds(len(ytr), 5, 16):
            tr = np.setdiff1d(np.arange(len(ytr)), fold)
            g = GradientBoosting("multinomial", J=6, nu=0.1, M=Mmax, K=9).fit(Xtr[tr], ytr[tr], evals={"v": (Xtr[fold], ytr[fold])},
                                                                            metrics={"dev": deviance_multinomial})
            cv += g.history["v"]["dev"] * len(fold) / len(ytr)
        Mstar = int(np.argmin(cv))
        g = GradientBoosting("multinomial", J=6, nu=0.1, M=Mmax, K=9).fit(
            Xtr, ytr, evals={"test": (Xte, yte)},
            metrics={"err": lambda y, F: float(np.mean(np.argmax(F, 1) != y)), "dev": deviance_multinomial})
        hist = g.history
        g.trees = g.trees[:Mstar]
        pred = np.argmax(g.decision_function(Xte), 1)
        return {"model": g, "hist": hist, "pred": pred, "M": Mstar, "cv": cv}
    return _cache("ch10_marketing.pkl", build)


def fig_10_22(out_dir=None):
    """Error rate for each occupation in the demographics data."""
    import matplotlib.pyplot as plt
    R = marketing_model()
    _, _, _, yte, _ = marketing()
    rates = np.array([np.mean(R["pred"][yte == k] != k) for k in range(9)])
    o = np.argsort(rates)[::-1]
    overall = float(np.mean(R["pred"] != yte))
    null = 1 - np.bincount(yte, minlength=9).max() / len(yte)
    fig, ax = plt.subplots(figsize=(5.2, 3.6))
    ax.barh(np.arange(9), rates[o], color=RED, height=0.65)
    ax.set_yticks(np.arange(9))
    ax.set_yticklabels([OCCUPATIONS[k] for k in o])
    ax.set_xlim(0, 1)
    ax.set_xlabel("Error rate")
    ax.set_title("Overall error rate = %.3f" % overall)
    print("  overall test error %.4f (null rate %.4f); per class:" % (overall, null),
          {OCCUPATIONS[k]: round(float(rates[k]), 3) for k in o[::-1]})
    h = R["hist"]["test"]
    print("  M chosen by CV = %d; test error at M=50/100/200: %.4f %.4f %.4f; min %.4f at %d"
          % (R["M"], h["err"][50], h["err"][100], h["err"][200], h["err"].min(), h["err"].argmin()))
    savefig(fig, CH, "fig10-22", out_dir)


def _marketing_importance():
    R = marketing_model()
    names = marketing()[4]
    rel, per = relative_importance_multiclass(R["model"], len(names))
    return rel, per, names


def fig_10_23(out_dir=None):
    """Relative importance of the predictors averaged over the classes (10.46)."""
    import matplotlib.pyplot as plt
    rel, per, names = _marketing_importance()
    o = np.argsort(rel)
    fig, ax = plt.subplots(figsize=(5.0, 3.9))
    ax.barh(np.arange(len(o)), rel[o], color=RED, height=0.65)
    ax.set_yticks(np.arange(len(o)))
    ax.set_yticklabels([names[k] for k in o])
    ax.set_xlim(0, 100)
    ax.set_xlabel("Relative importance")
    print("  ", [(names[k], round(float(rel[k]), 1)) for k in o[::-1]])
    savefig(fig, CH, "fig10-23", out_dir)


def fig_10_24(out_dir=None):
    """Per-class relative importances (10.45) for the four best-predicted classes."""
    import matplotlib.pyplot as plt
    R = marketing_model()
    _, _, _, yte, _ = marketing()
    rates = np.array([np.mean(R["pred"][yte == k] != k) for k in range(9)])
    best = np.argsort(rates)[:4]
    rel, per, names = _marketing_importance()
    fig, axes = plt.subplots(2, 2, figsize=(8.0, 6.6))
    for ax, k in zip(axes.flat, best):
        o = np.argsort(per[k])
        ax.barh(np.arange(len(o)), per[k][o], color=RED, height=0.65)
        ax.set_yticks(np.arange(len(o)))
        ax.set_yticklabels([names[i] for i in o], fontsize=8)
        ax.set_xlim(0, 100)
        ax.set_xlabel("Relative importance")
        ax.set_title("Class = %s" % OCCUPATIONS[k])
        print("  %s: top 3 %s" % (OCCUPATIONS[k], [names[i] for i in o[::-1][:3]]))
    fig.tight_layout()
    savefig(fig, CH, "fig10-24", out_dir)


def marketing_age_pd():
    """Partial dependence on age (codes 1..7) of f_k - mean_l f_l (10.52) for every class."""
    R = marketing_model()
    Xtr, _, _, _, names = marketing()
    g = R["model"]
    j = names.index("age")
    grid = np.arange(1, 8, dtype=float)
    pds = np.array([pd_trees(g.tree_list(k), Xtr, [j], grid) for k in range(9)])
    return grid, pds - pds.mean(0, keepdims=True)


def fig_10_25(out_dir=None):
    """Partial dependence of the log-odds (10.52) of three occupations on age."""
    import matplotlib.pyplot as plt
    grid, pds = marketing_age_pd()
    fig, axes = plt.subplots(1, 3, figsize=(9.6, 3.2))
    for ax, name in zip(axes, ("Retired", "Student", "Prof/Man")):
        k = OCCUPATIONS.index(name)
        v = pds[k] - pds[k].mean()
        ax.bar(grid, v, color=GREEN, width=0.6)
        ax.axhline(0, color=GREY, lw=0.8)
        ax.set_xlabel("age (code)")
        ax.set_ylabel("Partial dependence")
        ax.set_title(name)
        print("  %s: %s" % (name, np.round(v, 2)))
    fig.tight_layout()
    savefig(fig, CH, "fig10-25", out_dir)


FIGURES = {"10.2": fig_10_2, "10.3": fig_10_3, "10.4": fig_10_4, "10.5": fig_10_5, "10.6": fig_10_6, "10.7": fig_10_7,
           "10.8": fig_10_8, "10.9": fig_10_9, "10.10": fig_10_10, "10.11": fig_10_11, "10.12": fig_10_12,
           "10.13": fig_10_13, "10.14": fig_10_14, "10.15": fig_10_15, "10.16": fig_10_16, "10.17": fig_10_17,
           "10.22": fig_10_22, "10.23": fig_10_23, "10.24": fig_10_24, "10.25": fig_10_25, "10.S1": fig_10_s1}

if __name__ == "__main__":
    # run the figures from the importable module, so that cached (pickled) models refer to
    # ch10_boosting rather than __main__
    import ch10_boosting
    common.run(ch10_boosting.FIGURES, CH)
