"""Murphy (2022), Chapter 18: Trees, Forests, Bagging, and Boosting.

Companion code for Chapter 18 of K. P. Murphy, Probabilistic Machine Learning: An Introduction
(MIT Press, 2022; April 2025 draft), pp. 603-623, written from scratch with numpy, to be read next
to the lecture notes (../ch18-trees-forests-boosting.html). scikit-learn is used to load data, to
run the large experiments (spam e-mail, MNIST) and to confirm the implementations.

Methods (all in this file)
* Section 18.1, classification and regression trees: one greedy CART learner (class CART) with
  the Gini index (18.8), the entropy (18.9), the misclassification rate and the mean squared error
  (18.6) as node costs, the exhaustive threshold search (18.5) done in one sorted pass per feature,
  leaf values (18.3), a random subset of candidate features per node (Section 18.4), sample weights
  (used for bootstrap counts and for boosting), cost-complexity pruning (prune_path), and the
  split-gain importance (18.57) (importance).
* Section 18.2-18.4, ensembles: majority-vote probability (18.11) (vote_prob), bagging and random
  forests with out-of-bag predictions (class Forest), stacking weights (stack_weights).
* Section 18.5, boosting: forward stagewise fitting by squared loss (class GBM with loss="ls"),
  discrete AdaBoost (Algorithm 18.1) (adaboost), LogitBoost (Algorithm 18.2) (logitboost), gradient
  boosting for squared, absolute, exponential and log loss (class GBM, Algorithm 18.3), and the
  second-order regularised trees of XGBoost, (18.46)-(18.56) (class XGB).
* Section 18.6, interpretation: split-gain feature importance (18.57)-(18.58) and the partial
  dependence functions (18.59)-(18.60) (pdp1, pdp2).

Conventions. Class labels in the trees are integers 0..C-1. For two classes the boosting code
works with the log-odds a(x) = log p(y=1|x)/p(y=0|x); the book's f is half of it, f = a/2, so that
p(y=1|x) = 1/(1+exp(-2 f)) as in (18.20). Thresholds are placed halfway between consecutive
sorted values (the partition is the same as with the book's rule "x <= t", t a data value).

Data. Iris (Fisher, 1936) and the two-moons simulator come from scikit-learn; the spam data (4601
e-mails, 57 features; Hastie et al., 2009, p. 301) are the UCI data as shipped in the R package
kernlab, exported once to code/cache/spam.csv by a call to Rscript; MNIST is read by common.mnist
(cached). The book fixes a 3065/1536 train/test split of the spam data that is not reproduced
here: a random split with the same sizes is used (seed in the code), so test errors differ in the
third digit. The two-moons data of Figure 18.4 are simulated (500 points, noise 0.3) because the
book's own random sample is not available.

Figures. Reproduced here: 18.1 (the tree diagram and the piecewise constant surface, redrawn from
the thresholds in the text), 18.3, 18.4, 18.5, 18.6, 18.7, 18.8, 18.9, 18.10. Skipped, with the
reason:
  18.2  a hand-drawn set of coloured shapes and a hypothetical tree on them (nothing is computed).
Supplementary figures for the gaps filled in the notes:
  18.S1 the majority-vote probability (18.11) against the ensemble size, for independent voters and
        for voters with a shared error (a beta-binomial model);
  18.S2 variance reduction by averaging correlated trees: the formula rho s^2 + (1-rho) s^2 / B
        against a simulation, and the variance of bagged trees and random forests against B;
  18.S3 AdaBoost: training error, exponential loss and the bound prod 2 sqrt(err (1 - err));
  18.S4 XGBoost: the split gain (18.56) against the threshold for several lambda and gamma, and the
        shrinkage of a leaf weight (18.54);
  18.S5 the three impurity measures of a two-class node, and the split of Exercise 18.1;
  18.S6 impurity-based importance is biased towards features with many distinct values;
  18.S7 partial dependence hides an interaction that the two-dimensional version shows;
  18.S8 cost-complexity pruning path on the two-moons data;
  18.S9 trees are insensitive to a monotone transformation of an input.
Run `python3 ch18_trees_forests_boosting.py --list`, `python3 ch18_trees_forests_boosting.py` (all
figures, several minutes) or `python3 ch18_trees_forests_boosting.py --fig 18.4`. Files go to
../img/ch18/; the data used by the browser demonstrations go to ../data/ch18-*.json.
"""
import json
import os
import subprocess
import sys

os.environ.setdefault("OPENBLAS_NUM_THREADS", "1")

import numpy as np
from scipy import special, stats

sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
import common  # noqa: E402
from common import BLUE, CYAN, GREEN, GREY, MAGENTA, ORANGE, PURPLE, RED, plt, savefig  # noqa: E402

CH = 18
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")
sigmoid = common.sigmoid


# =========================================================================== Section 18.1: CART
class CART:
    """A greedy binary tree (Section 18.1.2) for classification, regression or second-order boosting.

    task = "class":  integer labels; criterion in {"gini", "entropy", "misclass"}; leaf value is the
                     class distribution (18.7).
    task = "reg":    real response; node cost is the sum of squared errors (18.6); leaf value (18.3).
    task = "newton": the regularised tree of XGBoost; fit with gradients g and hessians h; leaf value
                     -G/(H+lam) (18.54), split gain (18.56) with the per-leaf penalty gamma.

    Options: max_depth, min_samples_leaf, min_gain (a split must reduce the total cost by more than
    this), max_features (number of features tried per node, the rest are tried only if none of those
    gives a valid split), rng (a numpy Generator, needed when max_features is set).
    Attributes after fit, one entry per node (node 0 is the root): feature, thr, left, right (-1 at
    a leaf), value (leaf prediction, also stored for internal nodes), n (training rows), w (total
    weight), cost (the cost of the node treated as a leaf), gain (cost reduction of its split).
    The cost is weighted: W_t * impurity(t) for classification, so the cost-complexity pruning of
    prune_path and the importance (18.57) use the same units as the book's (18.5).
    """

    def __init__(self, task="class", criterion="gini", max_depth=None, min_samples_leaf=1,
                 min_samples_split=2, min_gain=1e-12, max_features=None, rng=None,
                 n_classes=None, lam=0.0, gamma=0.0):
        self.task, self.criterion = task, criterion
        self.max_depth = np.inf if max_depth is None else max_depth
        self.msl, self.mss, self.min_gain = min_samples_leaf, min_samples_split, min_gain
        self.max_features, self.rng, self.C = max_features, rng, n_classes
        self.lam, self.gamma = lam, gamma

    # -- node costs, vectorised over rows of the statistics matrix S
    def _cost(self, S):
        S = np.atleast_2d(S)
        if self.task == "class":
            W = S.sum(1)
            Ws = np.where(W > 0, W, 1.0)
            if self.criterion == "gini":
                return W - (S ** 2).sum(1) / Ws
            if self.criterion == "entropy":
                with np.errstate(divide="ignore", invalid="ignore"):
                    t = np.where(S > 0, S * np.log(S / Ws[:, None]), 0.0)
                return -t.sum(1)
            if self.criterion == "misclass":
                return W - S.max(1)
            raise ValueError(self.criterion)
        if self.task == "reg":                      # statistics (w, w y, w y^2): SSE
            w = np.where(S[:, 0] > 0, S[:, 0], 1.0)
            return S[:, 2] - S[:, 1] ** 2 / w
        G, H = S[:, 0], S[:, 1]                     # newton: -1/2 G^2/(H+lam) + gamma
        return -0.5 * G ** 2 / (H + self.lam) + self.gamma

    def _stats(self, X, y, w, g, h):
        if self.task == "class":
            S = np.zeros((len(y), self.C))
            S[np.arange(len(y)), y] = w
            return S
        if self.task == "reg":
            return np.stack([w, w * y, w * y * y], 1)
        return np.stack([g, h], 1)

    def _leaf(self, s):
        if self.task == "class":
            return s / max(s.sum(), 1e-300)
        if self.task == "reg":
            return np.array([s[1] / s[0] if s[0] > 0 else 0.0])
        return np.array([-s[0] / (s[1] + self.lam)])

    def fit(self, X, y=None, sample_weight=None, g=None, h=None):
        X = np.asarray(X, float)
        n, p = X.shape
        w = np.ones(n) if sample_weight is None else np.asarray(sample_weight, float)
        if self.task == "class":
            y = np.asarray(y, int)
            self.C = int(y.max()) + 1 if self.C is None else self.C
        elif self.task == "reg":
            y = np.asarray(y, float)
        S = self._stats(X, y, w, g, h)
        self.p = p
        self.feature, self.thr, self.left, self.right = [], [], [], []
        self.value, self.n, self.w, self.cost, self.gain, self.depth = [], [], [], [], [], []
        self._grow(X, S, w, np.flatnonzero(w > 0) if self.task != "newton" else np.arange(n), 0)
        for name in ("feature", "thr", "left", "right", "n", "w", "cost", "gain", "depth"):
            setattr(self, name, np.array(getattr(self, name)))
        self.value = np.array(self.value)
        return self

    def _new_node(self, S_tot, nrows, depth):
        k = len(self.feature)
        self.feature.append(-1)
        self.thr.append(np.nan)
        self.left.append(-1)
        self.right.append(-1)
        self.value.append(self._leaf(S_tot))
        self.n.append(nrows)
        self.w.append(S_tot.sum() if self.task == "class" else S_tot[0])
        self.cost.append(float(self._cost(S_tot)[0]))
        self.gain.append(0.0)
        self.depth.append(depth)
        return k

    def _best_split(self, X, S, idx, tot, parent_cost):
        p = X.shape[1]
        order = np.arange(p)
        if self.max_features is not None and self.max_features < p:
            order = self.rng.permutation(p)
        best = None                                  # (cost after split, feature, threshold)
        tried = 0
        for j in order:
            if best is not None and self.max_features is not None and tried >= self.max_features:
                break
            tried += 1
            xj = X[idx, j]
            o = np.argsort(xj, kind="stable")
            xs = xj[o]
            cum = np.cumsum(S[idx][o], axis=0)
            nl = np.arange(1, len(idx))
            valid = (xs[1:] > xs[:-1]) & (nl >= self.msl) & (len(idx) - nl >= self.msl)
            if not valid.any():
                continue
            Ls, Rs = cum[:-1][valid], tot[None, :] - cum[:-1][valid]
            c = self._cost(Ls) + self._cost(Rs)
            i = int(np.argmin(c))
            if best is None or c[i] < best[0] - 1e-12 * max(1.0, abs(parent_cost)):
                pos = np.flatnonzero(valid)[i]
                best = (float(c[i]), int(j), 0.5 * (xs[pos] + xs[pos + 1]))
        return best

    def _grow(self, X, S, w, idx, depth):
        tot = S[idx].sum(0)
        node = self._new_node(tot, len(idx), depth)
        if depth >= self.max_depth or len(idx) < self.mss or len(idx) < 2 * self.msl:
            return node
        parent_cost = self.cost[node]
        if self.task != "newton" and parent_cost <= 1e-12 * max(1.0, tot.sum() if self.task == "class" else abs(tot[2])):
            return node                              # pure node
        best = self._best_split(X, S, idx, tot, parent_cost)
        if best is None:
            return node
        gain = parent_cost - best[0]
        if gain <= self.min_gain:
            return node
        _, j, t = best
        self.feature[node], self.thr[node], self.gain[node] = j, t, gain
        mask = X[idx, j] <= t
        self.left[node] = self._grow(X, S, w, idx[mask], depth + 1)
        self.right[node] = self._grow(X, S, w, idx[~mask], depth + 1)
        return node

    # -- prediction
    def apply(self, X):
        """Index of the leaf node that each row falls in."""
        X = np.atleast_2d(X)
        node = np.zeros(len(X), int)
        while True:
            f = self.feature[node]
            internal = f >= 0
            if not internal.any():
                return node
            go_left = X[np.arange(len(X)), np.where(internal, f, 0)] <= self.thr[node]
            nxt = np.where(go_left, self.left[node], self.right[node])
            node = np.where(internal, nxt, node)

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

    def predict_proba(self, X):
        return self.predict_value(X)

    def predict(self, X):
        v = self.predict_value(X)
        return v.argmax(1) if self.task == "class" else v[:, 0]

    @property
    def n_leaves(self):
        """Number of leaves of the (possibly pruned) tree: the reachable nodes without children."""
        return sum(1 for k in _reachable(self) if self.left[k] < 0)

    def path(self, x):
        """Nodes visited by one input, from the root to its leaf."""
        k, out = 0, [0]
        while self.feature[k] >= 0:
            k = self.left[k] if x[self.feature[k]] <= self.thr[k] else self.right[k]
            out.append(k)
        return out

    def as_dict(self, k=0):
        """Nested dictionary of the tree, for draw_tree."""
        d = dict(value=self.value[k], n=int(self.n[k]), w=float(self.w[k]), feature=int(self.feature[k]),
                 thr=float(self.thr[k]), cost=float(self.cost[k]))
        if self.feature[k] >= 0:
            d["left"], d["right"] = self.as_dict(self.left[k]), self.as_dict(self.right[k])
        return d


def importance(tree, normalize=True):
    """Feature importance of one tree, (18.57): the sum over internal nodes of the cost reduction of
    the nodes that split on the feature (here the weighted impurity decrease, so it is comparable
    between trees); normalised to sum to one when normalize is true."""
    r = np.zeros(tree.p)
    for k in np.flatnonzero(tree.feature >= 0):
        r[tree.feature[k]] += tree.gain[k]
    if normalize and r.sum() > 0:
        r = r / r.sum()
    return r


def prune_path(tree):
    """Cost-complexity pruning (weakest-link, Breiman et al., 1984) of a fitted CART.

    Returns (alphas, n_leaves, risks): alpha_0 = 0 for the full tree and for each k the effective
    alpha at which the k-th weakest link is cut, the number of leaves and the total cost
    sum_leaves cost(t) of the pruned tree, where the cost of a node is as in the CART class
    (weighted impurity)."""
    L, R = tree.left.copy(), tree.right.copy()
    cost = tree.cost.copy()
    alive = np.ones(len(L), bool)

    def sub(k):                                      # (sum of leaf costs, number of leaves) below k
        if L[k] < 0:
            return cost[k], 1
        a = sub(L[k])
        b = sub(R[k])
        return a[0] + b[0], a[1] + b[1]

    alphas, leaves, risks = [0.0], [], []
    tot, nl = sub(0)
    leaves.append(nl)
    risks.append(tot)
    while L[0] >= 0:
        best, bk = np.inf, -1
        for k in np.flatnonzero(alive & (L >= 0)):
            r, nlf = sub(k)
            a = (cost[k] - r) / (nlf - 1)
            if a < best - 1e-12:
                best, bk = a, k
        L[bk] = R[bk] = -1
        tot, nl = sub(0)
        alphas.append(max(best, alphas[-1]))
        leaves.append(nl)
        risks.append(tot)
    return np.array(alphas), np.array(leaves), np.array(risks)


def cart_tree_pruned(tree, alpha):
    """Predictions of the subtree that minimises cost + alpha * (number of leaves): returns a copy of
    tree whose left/right arrays have the weak links cut (smallest minimising subtree)."""
    import copy
    t = copy.deepcopy(tree)

    def sub(k):
        if t.left[k] < 0:
            return t.cost[k], 1
        a, b = sub(t.left[k]), sub(t.right[k])
        return a[0] + b[0], a[1] + b[1]

    changed = True
    while changed and t.left[0] >= 0:
        changed = False
        best, bk = np.inf, -1
        for k in range(len(t.left)):
            if t.left[k] >= 0 and k in _reachable(t):
                r, nlf = sub(k)
                a = (t.cost[k] - r) / (nlf - 1)
                if a < best - 1e-12:
                    best, bk = a, k
        if best <= alpha + 1e-12 and bk >= 0:
            t.left[bk] = t.right[bk] = -1
            t.feature[bk] = -1
            changed = True
    return t


def _reachable(t):
    out, stack = set(), [0]
    while stack:
        k = stack.pop()
        out.add(k)
        if t.left[k] >= 0:
            stack += [t.left[k], t.right[k]]
    return out


# =========================================================================== Section 18.2-18.4
def vote_prob(M, theta):
    """Probability that a majority vote of M independent voters, each correct with probability theta,
    is correct: Pr(S > M/2) with S ~ Binomial(M, theta), (18.11). Ties (M even, S = M/2) count as
    wrong, as in the book's strict inequality."""
    M = np.asarray(M)
    return stats.binom.sf(np.floor(M / 2), M, theta)


def vote_prob_shared(M, a, b):
    """Majority vote when the voters are conditionally independent given a shared accuracy
    Theta ~ Beta(a, b) (exchangeable, positively correlated votes): Pr(S > M/2) under the
    beta-binomial law. As M grows it tends to Pr(Theta > 1/2), not to 1."""
    M = np.asarray(M)
    return stats.betabinom.sf(np.floor(M / 2), M, a, b)


def bootstrap_counts(n, rng):
    """Multiplicity of each of n items in one bootstrap sample of size n (Section 18.3)."""
    return np.bincount(rng.integers(0, n, n), minlength=n)


class Forest:
    """Bagging (Section 18.3) and random forests (Section 18.4) with CART trees of any task.

    max_features=None gives bagging; an integer m gives a random forest whose every node searches a
    random subset of m features. Each tree is fitted to a bootstrap sample (as case weights).
    oob_predict returns the average of the trees that did not see each training row."""

    def __init__(self, B=50, task="class", max_features=None, max_depth=None, min_samples_leaf=1,
                 criterion="gini", bootstrap=True, seed=0):
        self.B, self.task, self.m, self.depth, self.msl = B, task, max_features, max_depth, min_samples_leaf
        self.criterion, self.bootstrap, self.seed = criterion, bootstrap, seed

    def fit(self, X, y):
        X = np.asarray(X, float)
        n = len(X)
        rng = np.random.default_rng(self.seed)
        self.C = int(np.max(y)) + 1 if self.task == "class" else None
        self.trees, self.counts = [], []
        for _ in range(self.B):
            c = bootstrap_counts(n, rng) if self.bootstrap else np.ones(n, int)
            t = CART(self.task, self.criterion, self.depth, self.msl, max_features=self.m,
                     rng=rng, n_classes=self.C)
            t.fit(X, y, sample_weight=c.astype(float))
            self.trees.append(t)
            self.counts.append(c)
        self.counts = np.array(self.counts)
        return self

    def predict_value(self, X, upto=None):
        """Average of the trees' values (class probabilities or means), as in (18.10)."""
        T = self.trees[:upto]
        return np.mean([t.predict_value(X) for t in T], axis=0)

    def predict(self, X, upto=None):
        v = self.predict_value(X, upto)
        return v.argmax(1) if self.task == "class" else v[:, 0]

    def vote(self, X, upto=None):
        """Majority vote of the hard decisions (committee), classification only."""
        T = self.trees[:upto]
        votes = np.zeros((len(X), self.C))
        for t in T:
            votes[np.arange(len(X)), t.predict(X)] += 1
        return votes.argmax(1)

    def oob_predict(self, X):
        """Out-of-bag average value for each training row (rows in every bag get nan)."""
        out = np.zeros((len(X), self.trees[0].value.shape[1]))
        cnt = np.zeros(len(X))
        for t, c in zip(self.trees, self.counts):
            oob = c == 0
            if oob.any():
                out[oob] += t.predict_value(X[oob])
                cnt[oob] += 1
        with np.errstate(invalid="ignore", divide="ignore"):
            return out / cnt[:, None]


def stack_weights(P, y, nonneg=True):
    """Stacking weights (18.12): least squares of y on the columns of P (base-model predictions),
    optionally constrained to w >= 0 (non-negative least squares)."""
    if nonneg:
        from scipy.optimize import nnls
        return nnls(P, y)[0]
    return np.linalg.lstsq(P, y, rcond=None)[0]


# =========================================================================== Section 18.5: boosting
def adaboost(X, y, M, depth=1):
    """Discrete AdaBoost (Algorithm 18.1) with depth-`depth` trees; y in {-1, +1}.

    Returns a dict with the trees, the weights alpha_m, the errors err_m and, for each round, the
    normalised data weights used to fit the tree (weights[m]) and the training exponential loss
    and 0-1 error of the ensemble after the round."""
    X = np.asarray(X, float)
    n = len(y)
    w = np.full(n, 1.0 / n)
    f = np.zeros(n)
    out = dict(trees=[], alpha=[], err=[], weights=[], exp_loss=[], train_err=[])
    for m in range(M):
        t = CART("class", "gini", depth, n_classes=2).fit(X, (y > 0).astype(int), sample_weight=w)
        pred = 2 * t.predict(X) - 1
        err = float(np.sum(w * (pred != y)) / np.sum(w))
        err = min(max(err, 1e-12), 1 - 1e-12)
        alpha = np.log((1 - err) / err)
        out["weights"].append(w / w.sum())
        w = w * np.exp(alpha * (pred != y))
        w = w / w.sum()
        f = f + alpha * pred
        out["trees"].append(t)
        out["alpha"].append(alpha)
        out["err"].append(err)
        out["exp_loss"].append(float(np.mean(np.exp(-y * f / 2))))
        out["train_err"].append(float(np.mean(np.sign(f) != y)))
    return out


def adaboost_predict(model, X, upto=None):
    """Sum_m alpha_m F_m(x) of Algorithm 18.1 (twice the book's f; sign is the class)."""
    T = model["trees"][:upto]
    return sum(a * (2 * t.predict(X) - 1) for a, t in zip(model["alpha"][:upto], T))


def logitboost(X, y01, M, depth=1):
    """LogitBoost (Algorithm 18.2) with regression trees of the given depth; y01 in {0, 1}.
    Returns the list of trees and the final f(x) on the training set; f(x) = 1/2 sum_m F_m(x)."""
    X = np.asarray(X, float)
    n = len(y01)
    f = np.zeros(n)
    pi = np.full(n, 0.5)
    trees = []
    for _ in range(M):
        w = np.maximum(pi * (1 - pi), 1e-10)
        z = np.clip((y01 - pi) / w, -4, 4)
        t = CART("reg", max_depth=depth).fit(X, z, sample_weight=w)
        f = f + 0.5 * t.predict(X)
        pi = 1 / (1 + np.exp(-2 * f))
        trees.append(t)
    return trees, f


def logitboost_predict(trees, X):
    return 0.5 * sum(t.predict(X) for t in trees)


class GBM:
    """Gradient boosting (Algorithm 18.3) with regression trees.

    loss: "ls" (squared error: residual fitting, least-squares boosting of Section 18.5.2),
          "lad" (absolute error: leaf values are medians of the residuals),
          "huber" (the Huber loss with threshold delta times the median absolute residual),
          "exp" (exponential loss, y in {-1,+1}; f is half the log-odds, so this is the gradient
                 version of AdaBoost) and
          "log" (binary log loss; y in {0,1}; the function a(x) is the log-odds and the leaf values are
                 one Newton step sum(r)/sum(p(1-p)) as in Friedman, 2001).
    nu is the shrinkage (learning rate), subsample < 1 gives stochastic gradient boosting. The model
    is F_M(x) = f_0 + nu * sum_m F_m(x); the trees' leaf values are re-solved as in (18.45).
    """

    def __init__(self, loss="ls", M=100, nu=0.1, depth=2, subsample=1.0, min_samples_leaf=1, seed=0, delta=1.35):
        self.loss, self.M, self.nu, self.depth = loss, M, nu, depth
        self.subsample, self.msl, self.seed, self.delta = subsample, min_samples_leaf, seed, delta

    def _neg_grad(self, y, f):
        if self.loss == "ls":
            return y - f
        if self.loss == "lad":
            return np.sign(y - f)
        if self.loss == "huber":
            r = y - f
            d = self._d
            return np.where(np.abs(r) <= d, r, d * np.sign(r))
        if self.loss == "exp":
            return y * np.exp(-y * f)
        return y - sigmoid(f)

    def _init(self, y):
        if self.loss in ("ls",):
            return float(np.mean(y))
        if self.loss in ("lad", "huber"):
            return float(np.median(y))
        if self.loss == "exp":
            p = np.clip(np.mean(y > 0), 1e-6, 1 - 1e-6)
            return 0.5 * np.log(p / (1 - p))
        p = np.clip(np.mean(y), 1e-6, 1 - 1e-6)
        return float(np.log(p / (1 - p)))

    def _leaf_values(self, tree, leaf, y, f, idx):
        """Re-solve the leaf weights (18.45) for the rows in idx."""
        vals = {}
        for k in np.unique(leaf):
            rows = idx[leaf == k]
            r = y[rows] - f[rows]
            if self.loss == "ls":
                v = r.mean()
            elif self.loss == "lad":
                v = np.median(r)
            elif self.loss == "huber":
                med = np.median(r)
                v = med + np.mean(np.clip(r - med, -self._d, self._d))
            elif self.loss == "exp":
                e = np.exp(-y[rows] * f[rows])
                v = np.sum(y[rows] * e) / max(np.sum(e), 1e-12)
            else:
                p = sigmoid(f[rows])
                v = np.sum(y[rows] - p) / max(np.sum(p * (1 - p)), 1e-12)
            vals[k] = v
        for k, v in vals.items():
            tree.value[k] = [v]

    def fit(self, X, y, X_test=None, y_test=None):
        X = np.asarray(X, float)
        y = np.asarray(y, float)
        n = len(y)
        rng = np.random.default_rng(self.seed)
        self.f0 = self._init(y)
        f = np.full(n, self.f0)
        self.trees = []
        self.train_loss, self.test_loss = [], []
        if X_test is not None:
            ft = np.full(len(X_test), self.f0)
        for m in range(self.M):
            if self.loss == "huber":
                self._d = self.delta * np.median(np.abs(y - f)) + 1e-12
            r = self._neg_grad(y, f)
            idx = np.arange(n) if self.subsample >= 1 else np.sort(rng.choice(n, max(2, int(self.subsample * n)), replace=False))
            t = CART("reg", max_depth=self.depth, min_samples_leaf=self.msl).fit(X[idx], r[idx])
            leaf = t.apply(X[idx])
            self._leaf_values(t, leaf, y, f, idx)
            f = f + self.nu * t.predict(X)
            self.trees.append(t)
            self.train_loss.append(self.loss_value(y, f))
            if X_test is not None:
                ft = ft + self.nu * t.predict(X_test)
                self.test_loss.append(self.loss_value(y_test, ft))
        return self

    def loss_value(self, y, f):
        if self.loss == "ls":
            return float(np.mean((y - f) ** 2))
        if self.loss == "lad":
            return float(np.mean(np.abs(y - f)))
        if self.loss == "huber":
            r = np.abs(y - f)
            d = getattr(self, "_d", self.delta)
            return float(np.mean(np.where(r <= d, 0.5 * r ** 2, d * (r - 0.5 * d))))
        if self.loss == "exp":
            return float(np.mean(np.exp(-y * f)))
        return float(np.mean(np.logaddexp(0, f) - y * f))

    def decision(self, X, upto=None):
        """F_m(x) after `upto` trees (all by default)."""
        X = np.asarray(X, float)
        f = np.full(len(X), self.f0)
        for t in self.trees[:upto]:
            f = f + self.nu * t.predict(X)
        return f

    def staged(self, X):
        """F_m(x) for m = 1..M as an (M, n) array."""
        X = np.asarray(X, float)
        f = np.full(len(X), self.f0)
        out = []
        for t in self.trees:
            f = f + self.nu * t.predict(X)
            out.append(f.copy())
        return np.array(out)


class XGB:
    """The regularised, second-order boosted trees of XGBoost (Section 18.5.5.2).

    Objective sum_i loss(y_i, f(x_i)) + gamma J + (lam/2) sum_j w_j^2 per tree, solved greedily with
    the gain (18.56) and the leaf weights (18.54). loss: "ls" (g = f - y, h = 1; the book's squared
    error up to a factor 2) or "log" (y in {0,1}; g = p - y, h = p(1-p), f = log-odds). eta is the
    shrinkage."""

    def __init__(self, loss="ls", M=50, eta=0.3, depth=3, lam=1.0, gamma=0.0, min_child_weight=0.0, seed=0):
        self.loss, self.M, self.eta, self.depth = loss, M, eta, depth
        self.lam, self.gamma, self.mcw, self.seed = lam, gamma, min_child_weight, seed

    def _gh(self, y, f):
        if self.loss == "ls":
            return f - y, np.ones_like(y)
        p = sigmoid(f)
        return p - y, np.maximum(p * (1 - p), 1e-12)

    def fit(self, X, y):
        X = np.asarray(X, float)
        y = np.asarray(y, float)
        if self.loss == "log":
            p0 = np.clip(y.mean(), 1e-6, 1 - 1e-6)
            self.f0 = float(np.log(p0 / (1 - p0)))
        else:
            self.f0 = float(y.mean())
        f = np.full(len(y), self.f0)
        self.trees = []
        for _ in range(self.M):
            g, h = self._gh(y, f)
            t = CART("newton", max_depth=self.depth, lam=self.lam, gamma=self.gamma,
                     min_gain=0.0).fit(X, g=g, h=h)
            f = f + self.eta * t.predict(X)
            self.trees.append(t)
        return self

    def decision(self, X, upto=None):
        X = np.asarray(X, float)
        f = np.full(len(X), self.f0)
        for t in self.trees[:upto]:
            f = f + self.eta * t.predict(X)
        return f


def xgb_gain(G_L, H_L, G_R, H_R, lam, gamma):
    """The gain (18.56) of splitting a node into a left and right part."""
    f = lambda G, H: G * G / (H + lam)
    return 0.5 * (f(G_L, H_L) + f(G_R, H_R) - f(G_L + G_R, H_L + H_R)) - gamma


# =========================================================================== Section 18.6
def pdp1(predict, X, k, grid):
    """Partial dependence (18.59) of the function `predict` on feature k over `grid`: the average of
    predict(x_n with x_{n,k} replaced by v) over the rows of X."""
    out = np.empty(len(grid))
    Z = X.copy()
    for i, v in enumerate(grid):
        Z[:, k] = v
        out[i] = predict(Z).mean()
    return out


def pdp2(predict, X, j, k, gj, gk):
    """Joint partial dependence (18.60) on a grid gj x gk (rows index gj)."""
    out = np.empty((len(gj), len(gk)))
    Z = X.copy()
    for a, u in enumerate(gj):
        for b, v in enumerate(gk):
            Z[:, j], Z[:, k] = u, v
            out[a, b] = predict(Z).mean()
    return out


# =========================================================================== data
def iris_petal():
    """Iris petal length and width (cm) and the species 0 = setosa, 1 = versicolor, 2 = virginica."""
    from sklearn.datasets import load_iris
    d = load_iris()
    return d.data[:, 2:4].copy(), d.target.copy()


def moons(n=500, noise=0.3, seed=42):
    from sklearn.datasets import make_moons
    X, y = make_moons(n_samples=n, noise=noise, random_state=seed)
    return X, y


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"]


def load_spam():
    """The spam data: (X, y), X of shape (4601, 57) with the book's column order, y = 1 for spam.

    The file code/cache/spam.csv is written on first use from the R package kernlab (which ships the
    UCI data set); the 58th column is the label."""
    path = os.path.join(CACHE_DIR, "spam.csv")
    if not os.path.exists(path):
        os.makedirs(CACHE_DIR, exist_ok=True)
        subprocess.run(["/usr/local/bin/Rscript", "-e",
                        'library(kernlab); data(spam); spam$type <- as.integer(spam$type=="spam"); '
                        'write.table(spam, "%s", sep=",", row.names=FALSE, col.names=FALSE)' % path], check=True)
    D = np.loadtxt(path, delimiter=",")
    return D[:, :57], D[:, 57].astype(int)


def spam_split(seed=1):
    """A random 3065/1536 split of the spam data, the sizes used by the book (and Hastie et al.)."""
    X, y = load_spam()
    rng = np.random.default_rng(seed)
    p = rng.permutation(len(y))
    tr, te = p[:3065], p[3065:]
    return X[tr], y[tr], X[te], y[te]


# =========================================================================== drawing helpers
def _tree_layout(d, depth=0, pos=None, counter=None):
    """x position of every node of a nested tree dict (leaves evenly spaced, parents centred)."""
    if counter is None:
        counter = [0]
    if "left" not in d:
        d["_x"] = counter[0]
        counter[0] += 1
    else:
        _tree_layout(d["left"], depth + 1, None, counter)
        _tree_layout(d["right"], depth + 1, None, counter)
        d["_x"] = 0.5 * (d["left"]["_x"] + d["right"]["_x"])
    d["_d"] = depth
    return d


def draw_tree(ax, d, node_text, leaf_text, leaf_colour=None, edge_labels=("yes", "no"), fs=7.5, dx=1.0, dy=1.0):
    """Draw a nested tree dict (CART.as_dict, or a hand-made one) with boxes: internal nodes show
    node_text(d), leaves leaf_text(d); the left branch is labelled edge_labels[0]."""
    _tree_layout(d)
    maxd = [0]

    def walk(n):
        maxd[0] = max(maxd[0], n["_d"])
        for c in ("left", "right"):
            if c in n:
                walk(n[c])
    walk(d)

    def rec(n):
        x, y = n["_x"] * dx, -n["_d"] * dy
        for c, lab in (("left", edge_labels[0]), ("right", edge_labels[1])):
            if c in n:
                x2, y2 = n[c]["_x"] * dx, -n[c]["_d"] * dy
                ax.plot([x, x2], [y - 0.12, y2 + (0.27 if "left" not in n[c] else 0.12)], color="#555555", lw=0.8, zorder=1)
                ax.text(0.5 * (x + x2) + (-0.08 if c == "left" else 0.08), 0.5 * (y + y2) + 0.02, lab, fontsize=fs - 1.5,
                        ha="right" if c == "left" else "left", color="#555555")
                rec(n[c])
        leaf = "left" not in n
        txt = leaf_text(n) if leaf else node_text(n)
        fc = (leaf_colour(n) if leaf_colour and leaf else "#ffffff")
        ax.text(x, y, txt, ha="center", va="center", fontsize=fs, zorder=3,
                bbox=dict(boxstyle="round,pad=0.25", fc=fc, ec="#333333", lw=0.8))
    rec(d)
    ax.set_xlim(-0.7 * dx, (max_leaf_x(d) + 0.7) * dx)
    ax.set_ylim(-(maxd[0] + 0.55) * dy, 0.5 * dy)
    ax.axis("off")


def max_leaf_x(d):
    if "left" not in d:
        return d["_x"]
    return max(max_leaf_x(d["left"]), max_leaf_x(d["right"]))


def decision_image(ax, predict, xlim, ylim, n=260, colours=None, alpha=0.30):
    """Shade the plane by the predicted class (colours = list of RGB-like colours)."""
    gx = np.linspace(*xlim, n)
    gy = np.linspace(*ylim, n)
    XX, YY = np.meshgrid(gx, gy)
    Z = predict(np.c_[XX.ravel(), YY.ravel()]).reshape(XX.shape)
    from matplotlib.colors import ListedColormap
    cols = colours or [RED, BLUE, GREEN]
    nc = len(cols)
    ax.imshow(Z, extent=(xlim[0], xlim[1], ylim[0], ylim[1]), origin="lower", aspect="auto",
              cmap=ListedColormap(cols), vmin=-0.5, vmax=nc - 0.5, alpha=alpha, interpolation="nearest")
    ax.set_xlim(xlim)
    ax.set_ylim(ylim)
    return Z


def scatter_classes(ax, X, y, cols=None, markers="osD^", s=14, edge=True):
    cols = cols or [RED, BLUE, GREEN]
    for c in np.unique(y):
        m = y == c
        ax.scatter(X[m, 0], X[m, 1], s=s, c=cols[int(c)], marker=markers[int(c)], edgecolors="k" if edge else "none",
                   linewidths=0.4, zorder=3)


# =========================================================================== Figure 18.1
def fig_18_1(out=None):
    """Figure 18.1: a regression tree on two inputs and its piecewise constant surface."""
    t1, t2, t3, t4 = 5.0, 7.0, 3.0, 3.0
    tree = dict(feature=0, thr=t1,
                left=dict(feature=1, thr=t2, left=dict(name="R1", y=2),
                          right=dict(feature=0, thr=t3, left=dict(name="R4", y=8), right=dict(name="R5", y=10))),
                right=dict(feature=1, thr=t4, left=dict(name="R2", y=4), right=dict(name="R3", y=6)))
    fig = plt.figure(figsize=(8.4, 3.5))
    ax = fig.add_axes([0.0, 0.0, 0.5, 1.0])
    draw_tree(ax, tree, lambda n: "$x_%d \\leq t=%g$" % (n["feature"] + 1, n["thr"]),
              lambda n: "%s\n$y=%d$" % (n["name"], n["y"]), leaf_colour=lambda n: plt.cm.viridis((n["y"] - 2) / 8 * 0.9 + 0.05), fs=8)
    common.panel_label(ax, "a", "upper left")

    def surf(P):
        x1, x2 = P[:, 0], P[:, 1]
        return np.where(x1 <= t1, np.where(x2 <= t2, 2, np.where(x1 <= t3, 8, 10)), np.where(x2 <= t4, 4, 6)).astype(float)

    from mpl_toolkits.mplot3d import Axes3D  # noqa: F401
    ax3 = fig.add_axes([0.5, 0.02, 0.5, 0.96], projection="3d")
    # the thresholds are integers, so the surface is exact on a grid of unit cells (one bar per cell)
    cx, cy = np.meshgrid(np.arange(10) + 0.5, np.arange(10) + 0.5)
    Z = surf(np.c_[cx.ravel(), cy.ravel()])
    ax3.bar3d(cx.ravel() - 0.5, cy.ravel() - 0.5, np.zeros(100), 1, 1, Z, color=plt.cm.viridis((Z - 2) / 8 * 0.9 + 0.05), shade=True, edgecolor="none")
    ax3.set_xlabel("$x_1$")
    ax3.set_ylabel("$x_2$")
    ax3.set_zlabel("$y$")
    ax3.set_zlim(0, 10.5)
    ax3.view_init(elev=28, azim=-60)
    ax3.text2D(0.02, 0.92, "(b)", transform=ax3.transAxes, fontsize=10)
    return savefig(fig, CH, "fig18-1")


# =========================================================================== Figure 18.3
def _drop(X, y, i):
    keep = np.ones(len(y), bool)
    keep[i] = False
    return X[keep], y[keep]


IRIS_XLIM, IRIS_YLIM = (0, 7.2), (-0.1, 2.9)
IRIS_DEPTH = 3      # the book uses depth 2; at depth 2 no single deletion moves the surface by more than 2%


def iris_tree_probe():
    """The depth-2 tree on all of iris and the single deleted point whose removal changes the
    decision surface the most (largest fraction of a grid whose predicted class changes)."""
    X, y = iris_petal()
    full = CART("class", "gini", IRIS_DEPTH).fit(X, y)
    gx, gy = np.meshgrid(np.linspace(*IRIS_XLIM, 120), np.linspace(*IRIS_YLIM, 60))
    G = np.c_[gx.ravel(), gy.ravel()]
    base = full.predict(G)
    best = (0.0, None)
    for i in range(len(y)):
        Xi, yi = _drop(X, y, i)
        d = np.mean(CART("class", "gini", IRIS_DEPTH).fit(Xi, yi).predict(G) != base)
        if d > best[0] + 1e-12:
            best = (d, i)
    return full, best[1], best[0]


def fig_18_3(out=None):
    """Figure 18.3: depth-2 tree on the iris petal data, its surface, the fit with one point removed
    and the average of the two."""
    X, y = iris_petal()
    names = ["setosa", "versicolor", "virginica"]
    feat = ["petal length", "petal width"]
    full, drop, frac = iris_tree_probe()
    Xd, yd = _drop(X, y, drop)
    t2 = CART("class", "gini", IRIS_DEPTH, n_classes=3).fit(Xd, yd)
    fig = plt.figure(figsize=(9.2, 6.4))
    ax = fig.add_axes([0.0, 0.52, 1.0, 0.48])
    d = full.as_dict()
    draw_tree(ax, d, lambda n: "%s $\\leq$ %.2f\nn=%d, %s" % (feat[n["feature"]], n["thr"], n["n"], _counts(n, full)),
              lambda n: "n=%d\n%s\n%s" % (n["n"], _counts(n, full), names[int(np.argmax(n["value"]))]),
              leaf_colour=lambda n: [RED, BLUE, GREEN][int(np.argmax(n["value"]))] + "55", fs=8, dx=1.9, dy=1.0)
    common.panel_label(ax, "a")
    axes = [fig.add_axes([0.07 + 0.325 * i, 0.07, 0.29, 0.34]) for i in range(3)]
    ens = lambda P: (full.predict_value(P) + t2.predict_value(P)).argmax(1)
    panels = [("b", lambda P: full.predict(P), X, y), ("c", lambda P: t2.predict(P), X, y), ("d", ens, X, y)]
    for ax_, (lab, f, XX_, yy_) in zip(axes, panels):
        decision_image(ax_, f, IRIS_XLIM, IRIS_YLIM)
        scatter_classes(ax_, XX_, yy_)
        if lab == "c":
            ax_.scatter(*X[drop], marker="*", s=130, c="none", edgecolors="k", linewidths=1.2, zorder=4)
            ax_.scatter(*X[drop], marker="*", s=70, c="yellow", edgecolors="k", linewidths=0.6, zorder=5)
        ax_.set_xlabel("petal length (cm)")
        if lab == "b":
            ax_.set_ylabel("petal width (cm)")
        common.panel_label(ax_, lab, "upper left")
    return savefig(fig, CH, "fig18-3")


def _counts(n, tree):
    """Class counts (n_0, n_1, n_2) in a node dict of a classification tree."""
    return "[%s]" % ", ".join("%d" % round(v * n["w"]) for v in n["value"])


# =========================================================================== Figure 18.4
def moons_split(seed=42, n_train=250):
    """Two-moons data for Figure 18.4: 250 training points and 750 test points, noise 0.3."""
    X, y = moons(1000, 0.3, seed)
    return X[:n_train], y[:n_train], X[n_train:], y[n_train:]


def fig_18_4(out=None):
    """Figure 18.4: one tree, a bag of 10 and of 50 trees, and a random forest of 50 trees."""
    Xtr, ytr, Xte, yte = moons_split()
    models = [("a", "Decision tree", Forest(1, bootstrap=False).fit(Xtr, ytr)),
              ("b", "Bag of 10 decision trees", Forest(10, seed=1).fit(Xtr, ytr)),
              ("c", "Bag of 50 decision trees", Forest(50, seed=1).fit(Xtr, ytr)),
              ("d", "Random forest of 50 trees", Forest(50, max_features=1, seed=1).fit(Xtr, ytr))]
    fig, axes = common.panel_grid(1, 4, size=(3.0, 2.8))
    for ax, (lab, name, m) in zip(axes[0], models):
        decision_image(ax, m.predict, (-1.6, 2.6), (-1.1, 1.6), colours=[RED, BLUE])
        scatter_classes(ax, Xtr, ytr, cols=[RED, BLUE], markers="os", s=8)
        acc = np.mean(m.predict(Xte) == yte)
        ax.set_title("%s\ntest accuracy %.3f" % (name, acc), fontsize=8.5)
        ax.set_xlabel("$x_1$")
        if lab == "a":
            ax.set_ylabel("$x_2$")
        common.panel_label(ax, lab)
    return savefig(fig, CH, "fig18-4")


# =========================================================================== Figure 18.5, 18.9, 18.10
def spam_ensembles(B=500, seed=1):
    """Test error against the number of trees for bagging, a random forest and gradient boosting on
    the spam data, plus the fitted boosting model (used by Figures 18.9 and 18.10). Cached."""
    import pickle
    path = os.path.join(CACHE_DIR, "ch18_spam_ensembles_d6_%d_%d.pkl" % (B, seed))
    if os.path.exists(path):
        with open(path, "rb") as f:
            return pickle.load(f)
    from sklearn.ensemble import GradientBoostingClassifier, RandomForestClassifier
    Xtr, ytr, Xte, yte = spam_split(seed)
    res = {}
    for name, mf in (("bagging", None), ("rf", 7)):
        rf = RandomForestClassifier(n_estimators=B, max_features=mf, random_state=seed, n_jobs=1).fit(Xtr, ytr)
        acc = np.zeros(len(yte))
        err = []
        for m, t in enumerate(rf.estimators_, 1):
            acc += t.predict_proba(Xte)[:, 1]
            err.append(float(np.mean((acc / m > 0.5) != yte)))
        res[name] = np.array(err)
    gb = GradientBoostingClassifier(n_estimators=B, learning_rate=0.1, max_depth=6, subsample=1.0, random_state=seed).fit(Xtr, ytr)
    res["boosting"] = np.array([float(np.mean(p != yte)) for p in gb.staged_predict(Xte)])
    res["gb"] = gb
    with open(path, "wb") as f:
        pickle.dump(res, f)
    return res


def fig_18_5(out=None):
    """Figure 18.5: test error against the number of trees for bagging, random forests and boosting."""
    R = spam_ensembles()
    fig, ax = plt.subplots(figsize=(5.0, 3.5))
    n = np.arange(1, len(R["rf"]) + 1)
    ax.plot(n, R["rf"], color=GREEN, label="RF ($m=7$)")
    ax.plot(n, R["boosting"], color=RED, label="Boosting (log loss, depth 6)")
    ax.plot(n, R["bagging"], color=BLUE, label="Bagging")
    ax.set_xlabel("Number of trees")
    ax.set_ylabel("Test error")
    ax.set_ylim(0.035, 0.085)
    ax.legend()
    return savefig(fig, CH, "fig18-5")


def fig_18_9(out=None):
    """Figure 18.9: relative importance of the 57 features for boosted trees on the spam data (top 30)."""
    R = spam_ensembles()
    imp = R["gb"].feature_importances_
    imp = 100 * imp / imp.max()
    o = np.argsort(imp)[::-1][:30]
    fig, ax = plt.subplots(figsize=(4.4, 5.6))
    ax.barh(np.arange(len(o))[::-1], imp[o], color=BLUE, height=0.7)
    ax.set_yticks(np.arange(len(o))[::-1])
    ax.set_yticklabels([SPAM_NAMES[i] for i in o], fontsize=7.5)
    ax.set_xlabel("Relative importance")
    ax.set_xlim(0, 105)
    return savefig(fig, CH, "fig18-9")


def fig_18_10(out=None):
    """Figure 18.10: partial dependence of the log-odds of spam on four features and on (hp, !)."""
    R = spam_ensembles()
    gb = R["gb"]
    Xtr, ytr, _, _ = spam_split()
    sub = Xtr[np.random.default_rng(0).choice(len(Xtr), 600, replace=False)]
    feats = [SPAM_NAMES.index(s) for s in ("ch!", "remove", "edu", "hp")]
    fig = plt.figure(figsize=(9.0, 3.0))
    ax0 = fig.add_axes([0.05, 0.16, 0.55, 0.74])
    ax0.axis("off")
    for i, k in enumerate(feats):
        ax = fig.add_axes([0.05 + 0.14 * i, 0.16, 0.115, 0.74])
        q = np.quantile(Xtr[:, k], np.linspace(0.0, 0.99, 40))
        grid = np.unique(q)
        pd_ = pdp1(gb.decision_function, sub, k, grid)
        ax.plot(grid, pd_, color=BLUE)
        dec = np.quantile(Xtr[:, k], np.linspace(0.1, 0.9, 9))
        ax.plot(dec, np.full_like(dec, ax.get_ylim()[0]), "|", color=RED, ms=7)
        ax.set_xlabel(SPAM_NAMES[k])
        if i == 0:
            ax.set_ylabel("partial dependence (log-odds)")
        if i == 0:
            common.panel_label(ax, "a", "upper left")
    ax = fig.add_axes([0.70, 0.16, 0.27, 0.74])
    j, k = SPAM_NAMES.index("hp"), SPAM_NAMES.index("ch!")
    gj, gk = np.linspace(0, 3, 25), np.linspace(0, 1, 25)
    Z = pdp2(gb.decision_function, sub, j, k, gj, gk)
    cs = ax.contourf(gk, gj, Z, 14, cmap="coolwarm")
    ax.set_xlabel("ch!")
    ax.set_ylabel("hp")
    fig.colorbar(cs, ax=ax, pad=0.02)
    common.panel_label(ax, "b", "upper left")
    return savefig(fig, CH, "fig18-10")


# =========================================================================== Figure 18.6
def regr_data(n=100, seed=42):
    """Noisy quadratic y = 3 (x - 0.5)^2-type data, x in [-0.5, 0.5], used by Figure 18.6."""
    rng = np.random.default_rng(seed)
    x = rng.random(n) - 0.5
    y = 3 * x ** 2 + 0.05 * rng.standard_normal(n)
    return x[:, None], y


def fig_18_6(out=None):
    """Figure 18.6: three rounds of least-squares boosting with depth-2 regression trees."""
    X, y = regr_data()
    g = np.linspace(-0.5, 0.5, 300)[:, None]
    fig, axes = common.panel_grid(3, 2, size=(3.4, 2.3), sharex=True)
    f_tr, f_g = np.zeros(len(y)), np.zeros(len(g))
    for m in range(3):
        r = y - f_tr
        t = CART("reg", max_depth=2).fit(X, r)
        a, b = axes[m]
        a.scatter(X[:, 0], r, s=9, c=BLUE, label="Residuals" if m else "Training set")
        a.plot(g[:, 0], t.predict(g), color=GREEN, label="$F_%d(x_1)$" % (m + 1))
        a.set_ylabel("$y$")
        a.legend(loc="upper center", fontsize=7.5)
        f_tr, f_g = f_tr + t.predict(X), f_g + t.predict(g)
        b.scatter(X[:, 0], y, s=9, c=BLUE, label="Training set")
        b.plot(g[:, 0], f_g, color=RED, label="$f_%d(x_1)$" % (m + 1))
        b.legend(loc="upper center", fontsize=7.5)
        if m == 0:
            a.set_title("Residuals and tree predictions", fontsize=9)
            b.set_title("Ensemble predictions", fontsize=9)
    axes[2][0].set_xlabel("$x_1$")
    axes[2][1].set_xlabel("$x_1$")
    return savefig(fig, CH, "fig18-6")


# =========================================================================== Figure 18.7
def fig_18_7(out=None):
    """Figure 18.7: loss functions for binary classification against the margin."""
    m = np.linspace(-2, 2, 801)
    fig, ax = plt.subplots(figsize=(4.8, 3.4))
    ax.plot(m, (m < 0).astype(float), color=BLUE, label="0-1 loss")
    ax.plot(m, np.maximum(0, 1 - m), color=GREEN, ls="--", label="hinge loss")
    ax.plot(m, np.log2(1 + np.exp(-m)), color=RED, ls="-.", label="log loss (base 2)")
    ax.plot(m, np.exp(-m), color=MAGENTA, ls=":", label="exp loss")
    ax.set_ylim(0, 3)
    ax.set_xlabel("margin $m=\\tilde y F(x)$")
    ax.set_ylabel("loss")
    ax.legend()
    return savefig(fig, CH, "fig18-7")


# =========================================================================== Figure 18.8
def mnist_rf_importance(n_trees=100, seed=0):
    """Random forest on MNIST digits 0 versus 8: pixel importance (mean decrease in impurity). Cached."""
    path = os.path.join(CACHE_DIR, "ch18_mnist08_imp.npz")
    if os.path.exists(path):
        z = np.load(path)
        return z["imp"], float(z["acc"])
    from sklearn.ensemble import RandomForestClassifier
    X, y = common.mnist(True, digits=(0, 8))
    Xt, yt = common.mnist(False, digits=(0, 8))
    rf = RandomForestClassifier(n_estimators=n_trees, max_features="sqrt", n_jobs=1, random_state=seed).fit(X, (y == 8).astype(int))
    acc = rf.score(Xt, (yt == 8).astype(int))
    os.makedirs(CACHE_DIR, exist_ok=True)
    np.savez(path, imp=rf.feature_importances_, acc=acc)
    return rf.feature_importances_, acc


def fig_18_8(out=None):
    """Figure 18.8: pixel importance of a random forest that tells 0 from 8."""
    imp, acc = mnist_rf_importance()
    fig, ax = plt.subplots(figsize=(3.8, 3.5))
    im = ax.imshow(imp.reshape(28, 28), cmap="hot")
    ax.axis("off")
    cb = fig.colorbar(im, ax=ax, ticks=[imp.min(), imp.max()], fraction=0.046, pad=0.03)
    cb.ax.set_yticklabels(["Not important", "Very important"], fontsize=8)
    return savefig(fig, CH, "fig18-8")


# =========================================================================== supplementary figures
def fig_18_S1(out=None):
    """Figure 18.S1: the majority-vote probability against the number of voters."""
    M = np.unique(np.round(np.logspace(0, 4.3, 160)).astype(int) | 1)
    fig, axes = plt.subplots(1, 2, figsize=(8.2, 3.2))
    ax = axes[0]
    for th, c in ((0.51, RED), (0.55, BLUE), (0.60, GREEN)):
        ax.semilogx(M, vote_prob(M, th), color=c, label="$\\theta=%.2f$" % th)
    ax.axhline(0.5, color=GREY, lw=0.6)
    ax.plot([1000, 10000], [vote_prob(1000, 0.51), vote_prob(10001, 0.51)], "ko", ms=4)
    ax.set_xlabel("number of voters $M$ (odd)")
    ax.set_ylabel("Pr(majority correct)")
    ax.set_title("independent voters", fontsize=9.5)
    ax.legend()
    common.panel_label(ax, "a", "lower right")
    ax = axes[1]
    for (a, b), c in (((51, 49), RED), ((5.5, 4.5), BLUE), ((2.55, 2.45), GREEN)):
        ax.semilogx(M, vote_prob_shared(M, a, b), color=c, label="Beta(%g, %g)" % (a, b))
        ax.axhline(stats.beta.sf(0.5, a, b), color=c, lw=0.6, ls=":")
    ax.set_xlabel("number of voters $M$ (odd)")
    ax.set_title("voters with a shared accuracy $\\Theta$", fontsize=9.5)
    ax.legend(loc="lower right")
    common.panel_label(ax, "b", "upper left")
    return savefig(fig, CH, "fig18-S1")


def reg_task(seed, n=200, p=10):
    """Regression problem for the variance experiment: Friedman's first benchmark with p features."""
    rng = np.random.default_rng(seed)
    X = rng.random((n, p))
    y = 10 * np.sin(np.pi * X[:, 0] * X[:, 1]) + 20 * (X[:, 2] - 0.5) ** 2 + 10 * X[:, 3] + 5 * X[:, 4] + rng.standard_normal(n)
    return X, y


def variance_experiment(R=50, B=60, ms=(10, 3, 1), n=200, n_probe=30, seed=0):
    """For R independent training sets, fit a forest of B trees with each m (candidate features per
    node; m=10 is bagging) and record the predictions at n_probe fixed points after every number of
    trees. Returns {m: array (B, R, n_probe)} holding the average of the first b+1 trees. Cached."""
    path = os.path.join(CACHE_DIR, "ch18_variance_R%d_B%d_n%d.npz" % (R, B, n))
    if os.path.exists(path):
        z = np.load(path)
        return {int(m): z["m%d" % m] for m in ms}
    rng0 = np.random.default_rng(seed + 999)
    probe = rng0.random((n_probe, 10))
    pred = {m: np.zeros((B, R, n_probe)) for m in ms}
    for r in range(R):
        X, y = reg_task(seed + r, n)
        for m in ms:
            F = Forest(B, "reg", max_features=m, min_samples_leaf=3, seed=seed * 1000 + r).fit(X, y)
            P = np.array([t.predict(probe) for t in F.trees])
            pred[m][:, r, :] = np.cumsum(P, 0) / np.arange(1, B + 1)[:, None]
    os.makedirs(CACHE_DIR, exist_ok=True)
    np.savez(path, **{"m%d" % m: pred[m] for m in ms})
    return pred


def fig_18_S2(out=None):
    """Figure 18.S2: variance of an average of B correlated trees."""
    rng = np.random.default_rng(0)
    fig, axes = plt.subplots(1, 2, figsize=(8.2, 3.2))
    ax = axes[0]
    Bs = np.arange(1, 101)
    for rho, c in ((0.0, BLUE), (0.2, GREEN), (0.5, ORANGE), (0.8, RED)):
        ax.plot(Bs, rho + (1 - rho) / Bs, color=c, label="$\\rho=%.1f$" % rho)
        # simulation: equicorrelated Gaussians with unit variance
        sims = []
        for b in (1, 2, 5, 10, 30, 100):
            Z = np.sqrt(rho) * rng.standard_normal((20000, 1)) + np.sqrt(1 - rho) * rng.standard_normal((20000, b))
            sims.append(Z.mean(1).var())
        ax.plot((1, 2, 5, 10, 30, 100), sims, "o", color=c, ms=3.5)
    ax.set_xscale("log")
    ax.set_xlabel("number of trees $B$")
    ax.set_ylabel("variance / $\\sigma^2$")
    ax.set_title("$\\rho\\sigma^2+(1-\\rho)\\sigma^2/B$ (dots: simulation)", fontsize=9)
    ax.legend(fontsize=8)
    common.panel_label(ax, "a", "upper right")
    ax = axes[1]
    pred = variance_experiment()
    for m, c, lab in ((10, BLUE, "bagging ($m=10$)"), (3, GREEN, "$m=3$"), (1, RED, "$m=1$")):
        P = pred[m]                                   # (B, R, probe)
        v = P.var(1, ddof=1).mean(1)
        ax.plot(np.arange(1, len(v) + 1), v, color=c, label=lab)
    ax.set_xscale("log")
    ax.set_xlabel("number of trees $B$")
    ax.set_ylabel("variance of the forest prediction")
    ax.set_title("simulated regression task, 50 training sets", fontsize=9)
    ax.legend(fontsize=8)
    common.panel_label(ax, "b", "upper right")
    return savefig(fig, CH, "fig18-S2")


def adaboost_data(seed=3, n=200, noise=0.3, flip=0.0):
    """Two-moons training and test sets with labels in {-1, +1} (fraction `flip` of training labels flipped)."""
    X, y = moons(n + 1000, noise, seed)
    y = 2 * y - 1
    ytr = y[:n].copy()
    if flip > 0:
        rng = np.random.default_rng(seed)
        k = rng.choice(n, int(flip * n), replace=False)
        ytr[k] = -ytr[k]
    return X[:n], ytr, X[n:], y[n:]


def fig_18_S3(out=None):
    """Figure 18.S3: AdaBoost with stumps on two-moons data."""
    Xtr, ytr, Xte, yte = adaboost_data()
    M = 150
    mod = adaboost(Xtr, ytr, M, 1)
    err = np.array(mod["err"])
    bound = np.cumprod(2 * np.sqrt(err * (1 - err)))
    test = [float(np.mean(np.sign(adaboost_predict(mod, Xte, m)) != yte)) for m in range(1, M + 1)]
    fig, axes = plt.subplots(1, 3, figsize=(10.6, 3.1), gridspec_kw=dict(wspace=0.32))
    ax = axes[0]
    k = np.arange(1, M + 1)
    ax.semilogy(k, mod["train_err"], color=BLUE, label="training error")
    ax.semilogy(k, mod["exp_loss"], color=RED, label="exp. loss (mean of $e^{-\\tilde y f}$)")
    ax.semilogy(k, bound, color=GREEN, ls="--", label="$\\prod_m 2\\sqrt{\\mathrm{err}_m(1-\\mathrm{err}_m)}$")
    ax.semilogy(k, test, color=GREY, label="test error")
    ax.set_xlabel("rounds $m$")
    ax.legend(fontsize=7, loc="upper right")
    common.panel_label(ax, "a", "lower left")
    ax = axes[1]
    ax.plot(k, err, color=ORANGE)
    ax.axhline(0.5, color=GREY, lw=0.6)
    ax.set_xlabel("rounds $m$")
    ax.set_ylabel("weighted error of round $m$")
    common.panel_label(ax, "b", "lower right")
    ax = axes[2]
    decision_image(ax, lambda P: (adaboost_predict(mod, P) > 0).astype(int), (-1.6, 2.6), (-1.1, 1.6), colours=[RED, BLUE])
    scatter_classes(ax, Xtr, (ytr > 0).astype(int), cols=[RED, BLUE], markers="os", s=8)
    ax.set_xlabel("$x_1$")
    ax.set_ylabel("$x_2$")
    common.panel_label(ax, "c")
    return savefig(fig, CH, "fig18-S3")


def fig_18_S4(out=None):
    """Figure 18.S4: the gain (18.56) of a split along a 1-D feature, and the shrinkage of a leaf weight."""
    X, y = regr_data(60, 5)
    x = X[:, 0]
    o = np.argsort(x)
    x, y = x[o], y[o]
    f0 = y.mean()
    g, h = f0 - y, np.ones_like(y)                     # squared loss at f = f_0: g = f - y, h = 1
    thr = 0.5 * (x[1:] + x[:-1])
    cg, ch = np.cumsum(g)[:-1], np.cumsum(h)[:-1]
    G, H = g.sum(), h.sum()
    fig, axes = plt.subplots(1, 2, figsize=(8.2, 3.2))
    ax = axes[0]
    for (lam, gam), c in (((0, 0), BLUE), ((10, 0), GREEN), ((10, 0.15), ORANGE), ((40, 0.15), RED)):
        ax.plot(thr, xgb_gain(cg, ch, G - cg, H - ch, lam, gam), color=c, label="$\\lambda=%g,\\ \\gamma=%g$" % (lam, gam))
    ax.axhline(0, color="k", lw=0.6)
    ax.set_xlabel("threshold $t$")
    ax.set_ylabel("gain (18.56)")
    ax.legend(fontsize=7.5)
    common.panel_label(ax, "a", "upper left")
    ax = axes[1]
    lam = np.linspace(0, 40, 200)
    for n_leaf, c in ((2, RED), (5, ORANGE), (20, GREEN), (100, BLUE)):
        ax.plot(lam, n_leaf / (n_leaf + lam), color=c, label="%d points in the leaf" % n_leaf)
    ax.set_xlabel("$\\lambda$")
    ax.set_ylabel("$w^*/\\bar r$, the fraction of the mean residual kept")
    ax.legend(fontsize=7.5)
    common.panel_label(ax, "b", "upper right")
    return savefig(fig, CH, "fig18-S4")


def fig_18_S5(out=None):
    """Figure 18.S5: Gini, entropy and misclassification of a two-class node, and a split on which they disagree."""
    p = np.linspace(1e-9, 1 - 1e-9, 400)
    fig, axes = plt.subplots(1, 2, figsize=(8.2, 3.2))
    ax = axes[0]
    ax.plot(p, 2 * p * (1 - p), color=BLUE, label="Gini $\\times 2$")
    ax.plot(p, -(p * np.log2(p) + (1 - p) * np.log2(1 - p)), color=RED, label="entropy (bits)")
    ax.plot(p, 1 - np.maximum(p, 1 - p), color=GREEN, label="misclassification rate")
    ax.set_xlabel("proportion $\\hat\\pi$ of class 1 in the node")
    ax.legend(fontsize=8, loc="lower center")
    common.panel_label(ax, "a", "upper left")
    ax = axes[1]
    # Exercise 18.1: a node (400, 400) split in two ways
    A = [(300, 100), (100, 300)]
    B = [(200, 400), (200, 0)]
    cost = {"misclassification": lambda a, b: min(a, b) / (a + b),
            "Gini": lambda a, b: 2 * a * b / (a + b) ** 2,
            "entropy": lambda a, b: 0.0 if min(a, b) == 0 else -(a / (a + b) * np.log2(a / (a + b)) + b / (a + b) * np.log2(b / (a + b)))}
    names = list(cost)
    tot = lambda S, f: sum((a + b) / 800 * f(a, b) for a, b in S)
    xs = np.arange(len(names))
    parent = [cost[k](400, 400) for k in names]
    ga = [parent[i] - tot(A, cost[k]) for i, k in enumerate(names)]
    gb = [parent[i] - tot(B, cost[k]) for i, k in enumerate(names)]
    ax.bar(xs - 0.2, ga, 0.38, color=BLUE, label="split A: (300,100) | (100,300)")
    ax.bar(xs + 0.2, gb, 0.38, color=ORANGE, label="split B: (200,400) | (200,0)")
    ax.set_xticks(xs)
    ax.set_xticklabels(names, fontsize=8)
    ax.set_ylabel("impurity decrease of the split")
    ax.set_ylim(0, 0.42)
    ax.legend(fontsize=7.5, loc="upper left")
    common.panel_label(ax, "b", "upper right")
    return savefig(fig, CH, "fig18-S5")


def importance_bias_sim(n=1000, reps=30, seed=0):
    """Mean impurity-based (MDI) and permutation importance of: an informative binary feature, and three
    pure-noise features with 2, 10 and 1000 distinct values (random forests of 100 trees)."""
    from sklearn.ensemble import RandomForestClassifier
    rng = np.random.default_rng(seed)
    mdi = np.zeros((reps, 4))
    perm = np.zeros((reps, 4))
    for r in range(reps):
        x0 = rng.integers(0, 2, n)
        y = (rng.random(n) < 0.5 + 0.2 * (x0 - 0.5) * 2).astype(int)
        Xf = np.c_[x0, rng.integers(0, 2, n), rng.integers(0, 10, n), rng.random(n)].astype(float)
        Xt = np.c_[rng.integers(0, 2, n), rng.integers(0, 2, n), rng.integers(0, 10, n), rng.random(n)].astype(float)
        x0t = Xt[:, 0]
        yt = (rng.random(n) < 0.5 + 0.2 * (x0t - 0.5) * 2).astype(int)
        rf = RandomForestClassifier(100, min_samples_leaf=1, random_state=r, n_jobs=1).fit(Xf, y)
        mdi[r] = rf.feature_importances_
        base = np.mean(rf.predict(Xt) != yt)
        for j in range(4):
            Z = Xt.copy()
            Z[:, j] = rng.permutation(Z[:, j])
            perm[r, j] = np.mean(rf.predict(Z) != yt) - base
    return mdi, perm


def fig_18_S6(out=None):
    """Figure 18.S6: impurity importance is biased towards features with many distinct values."""
    mdi, perm = importance_bias_sim()
    lab = ["informative\nbinary", "noise\nbinary", "noise\n10 values", "noise\ncontinuous"]
    fig, axes = plt.subplots(1, 2, figsize=(8.2, 3.2))
    for ax, v, t, c in ((axes[0], mdi, "impurity decrease (mean over trees)", BLUE), (axes[1], perm, "permutation importance (test error increase)", GREEN)):
        ax.bar(range(4), v.mean(0), yerr=v.std(0) / np.sqrt(len(v)) * 2, color=c, capsize=3)
        ax.set_xticks(range(4))
        ax.set_xticklabels(lab, fontsize=8)
        ax.set_title(t, fontsize=9)
    common.panel_label(axes[0], "a", "upper right")
    common.panel_label(axes[1], "b", "upper right")
    return savefig(fig, CH, "fig18-S6")


def fig_18_S7(out=None):
    """Figure 18.S7: partial dependence of f(x1, x2) = x1 x2 on one feature is flat, on two it shows the interaction."""
    rng = np.random.default_rng(0)
    X = rng.uniform(-1, 1, (400, 2))
    f = lambda Z: Z[:, 0] * Z[:, 1]
    g = np.linspace(-1, 1, 41)
    fig, axes = plt.subplots(1, 2, figsize=(7.6, 3.2))
    ax = axes[0]
    ax.plot(g, pdp1(f, X, 0, g), color=BLUE, label="$\\bar f_1(x_1)$")
    ax.plot(g, pdp1(f, X, 1, g), color=RED, ls="--", label="$\\bar f_2(x_2)$")
    ax.set_xlabel("feature value")
    ax.set_ylabel("partial dependence")
    ax.set_ylim(-1, 1)
    ax.legend()
    common.panel_label(ax, "a", "lower right")
    ax = axes[1]
    Z = pdp2(f, X, 0, 1, g, g)
    cs = ax.contourf(g, g, Z.T, 15, cmap="coolwarm")
    fig.colorbar(cs, ax=ax)
    ax.set_xlabel("$x_1$")
    ax.set_ylabel("$x_2$")
    common.panel_label(ax, "b", "upper left")
    return savefig(fig, CH, "fig18-S7")


def fig_18_S8(out=None):
    """Figure 18.S8: cost-complexity pruning of a full tree on two-moons data."""
    Xtr, ytr, Xte, yte = moons_split()
    full = CART("class", "gini", n_classes=2).fit(Xtr, ytr)
    al, nl, rk = prune_path(full)
    te = []
    for a in al:
        t = cart_tree_pruned(full, a)
        te.append(float(np.mean(t.predict(Xte) != yte)))
    tr = [float(np.mean(cart_tree_pruned(full, a).predict(Xtr) != ytr)) for a in al]
    fig, axes = plt.subplots(1, 2, figsize=(8.2, 3.2))
    ax = axes[0]
    ax.step(nl, te, where="post", color=RED, label="test error")
    ax.step(nl, tr, where="post", color=BLUE, label="training error")
    ax.set_xlabel("number of leaves")
    ax.invert_xaxis()
    ax.legend()
    common.panel_label(ax, "a", "upper left")
    ax = axes[1]
    ax.step(al, nl, where="post", color=GREEN)
    ax.set_xlabel("$\\alpha$ (penalty per leaf)")
    ax.set_ylabel("leaves of the minimising subtree")
    ax.set_xscale("symlog", linthresh=0.01)
    common.panel_label(ax, "b", "upper right")
    i = int(np.argmin(te))
    axes[0].plot(nl[i], te[i], "k*", ms=9)
    return savefig(fig, CH, "fig18-S8")


def fig_18_S9(out=None):
    """Figure 18.S9: a tree is unchanged by a monotone transformation of an input; a linear model is not."""
    X, y = iris_petal()
    Xt = X.copy()
    Xt[:, 0] = np.exp(Xt[:, 0] / 2)
    ta = CART("class", "gini", 2).fit(X, y)
    tb = CART("class", "gini", 2).fit(Xt, y)
    fig, axes = plt.subplots(1, 2, figsize=(8.0, 3.1))
    for ax, t, XX_, ttl, lab in ((axes[0], ta, X, "petal length", "a"), (axes[1], tb, Xt, "exp(petal length / 2)", "b")):
        lo, hi = XX_[:, 0].min() - 0.3, XX_[:, 0].max() + 0.3
        decision_image(ax, t.predict, (lo, hi), IRIS_YLIM)
        scatter_classes(ax, XX_, y)
        ax.set_xlabel(ttl)
        common.panel_label(ax, lab)
    axes[0].set_ylabel("petal width")
    return savefig(fig, CH, "fig18-S9")


# =========================================================================== data for the demonstrations
def xor_data(n=400, seed=7):
    """Four Gaussian clusters at the corners (+-1, +-1) with labels equal to the product of signs
    (the XOR problem of Section 18.1.3), n points in total."""
    rng = np.random.default_rng(seed)
    c = rng.integers(0, 4, n)
    cx = np.array([[-1, -1], [1, 1], [-1, 1], [1, -1]], float)[c]
    X = cx + 0.45 * rng.standard_normal((n, 2))
    y = (c < 2).astype(int)
    return X, y


def boost_1d_data(seed=42):
    """Training (100) and test (200) data of Figure 18.6 and the outlier-contaminated variant used by
    the gradient-boosting demo: y = 3 x^2 + noise (sd 0.05); the contaminated copy replaces five
    training responses by values 0.5 above or below the curve."""
    X, y = regr_data(100, seed)
    Xt, yt = regr_data(200, seed + 1)
    yo = y.copy()
    idx = np.array([7, 23, 41, 66, 88])
    yo[idx] = y[idx] + np.array([0.6, -0.5, 0.7, -0.6, 0.5])
    return X, y, yo, idx, Xt, yt


def export_json():
    """Write the small JSON files used by the demonstrations, with the reference numbers they must reproduce."""
    r = lambda a, d=5: np.round(np.asarray(a, float), d).tolist()
    os.makedirs(DATA_OUT, exist_ok=True)
    # ---- the CART demonstration: iris petals and the XOR clusters
    X, y = iris_petal()
    Xx, yx = xor_data()
    ref = {}
    for crit in ("gini", "entropy", "misclass"):
        for d in (1, 2, 3):
            t = CART("class", crit, d).fit(X, y)
            ref["%s_d%d" % (crit, d)] = dict(leaves=t.n_leaves, feature=t.feature.tolist(), thr=r(np.nan_to_num(t.thr, nan=-1), 4),
                                             train_err=float(np.mean(t.predict(X) != y)))
    full, drop, frac = iris_tree_probe()
    tdrop = CART("class", "gini", IRIS_DEPTH, n_classes=3).fit(*_drop(X, y, drop))
    ref["drop"] = dict(index=int(drop), frac_changed=float(frac), feature=tdrop.feature.tolist(), thr=r(np.nan_to_num(tdrop.thr, nan=-1), 4))
    tx = CART("class", "gini", 1).fit(Xx, yx)
    ref["xor_root_gain_gini"] = float(tx.gain[0] / tx.cost[0])
    ref["iris_root_gain_gini"] = float(full.gain[0] / full.cost[0])
    with open(os.path.join(DATA_OUT, "ch18-cart.json"), "w") as f:
        json.dump(dict(iris=dict(X=r(X, 2), y=y.tolist()), xor=dict(X=r(Xx, 4), y=yx.tolist()), ref=ref), f, separators=(",", ":"))
    # ---- bagging and random forests: the two-moons data of Figure 18.4
    Xtr, ytr, Xte, yte = moons_split()
    t1 = CART("class", "gini", n_classes=2).fit(Xtr, ytr)
    ref = dict(single_tree_test_acc=float(np.mean(t1.predict(Xte) == yte)), single_tree_leaves=t1.n_leaves)
    seeds = range(20)
    for name, B, m in (("bag10", 10, None), ("bag50", 50, None), ("rf50_m1", 50, 1)):
        a = [np.mean(Forest(B, max_features=m, seed=s).fit(Xtr, ytr).predict(Xte) == yte) for s in seeds]
        ref[name + "_test_acc_mean"], ref[name + "_test_acc_sd"] = float(np.mean(a)), float(np.std(a))
    with open(os.path.join(DATA_OUT, "ch18-moons.json"), "w") as f:
        json.dump(dict(Xtr=r(Xtr, 4), ytr=ytr.tolist(), Xte=r(Xte, 4), yte=yte.tolist(), ref=ref), f, separators=(",", ":"))
    # ---- AdaBoost on two-moons
    Xa, ya, Xat, yat = adaboost_data()
    mod = adaboost(Xa, ya, 150, 1)
    err = np.array(mod["err"])
    ref = dict(err=r(err[:20]), alpha=r(mod["alpha"][:20]), train_err=r(mod["train_err"], 5), exp_loss=r(mod["exp_loss"], 6),
               test_err=r([float(np.mean(np.sign(adaboost_predict(mod, Xat, m)) != yat)) for m in range(1, 151)], 5),
               bound=r(np.cumprod(2 * np.sqrt(err * (1 - err))), 6))
    mod2 = adaboost(Xa, ya, 50, 2)
    ref["depth2_train_err"] = r(mod2["train_err"], 5)
    with open(os.path.join(DATA_OUT, "ch18-adaboost.json"), "w") as f:
        json.dump(dict(Xtr=r(Xa, 4), ytr=ya.tolist(), Xte=r(Xat, 4), yte=yat.tolist(), ref=ref), f, separators=(",", ":"))
    # ---- gradient boosting on the one-dimensional data
    X1, y1, yo, idx, Xt1, yt1 = boost_1d_data()
    grid = np.linspace(-0.5, 0.5, 11)[:, None]
    ref = {}
    for name, kw in (("ls_d2_nu1", dict(loss="ls", M=3, nu=1.0, depth=2)), ("ls_d2_nu0.1", dict(loss="ls", M=100, nu=0.1, depth=2)),
                     ("ls_d4_nu1", dict(loss="ls", M=100, nu=1.0, depth=4)), ("lad_d2_nu0.1", dict(loss="lad", M=100, nu=0.1, depth=2))):
        for tag, yy in (("clean", y1), ("outliers", yo)):
            g = GBM(**kw).fit(X1, yy, Xt1, yt1)
            ref["%s_%s" % (name, tag)] = dict(f_grid=r(g.decision(grid)), train_loss=r(g.train_loss[-1], 6), test_mse=float(np.mean((g.decision(Xt1) - yt1) ** 2)))
    for lam, gam in ((0.0, 0.0), (10.0, 0.0), (1.0, 0.002)):
        xg = XGB("ls", M=50, eta=0.3, depth=3, lam=lam, gamma=gam).fit(X1, y1)
        ref["xgb_lam%g_gam%g" % (lam, gam)] = dict(f_grid=r(xg.decision(grid)), leaves=[t.n_leaves for t in xg.trees[:5]],
                                                   train_mse=float(np.mean((xg.decision(X1) - y1) ** 2)))
    with open(os.path.join(DATA_OUT, "ch18-boost1d.json"), "w") as f:
        json.dump(dict(X=r(X1[:, 0], 5), y=r(y1, 5), yout=r(yo, 5), out_idx=idx.tolist(), Xte=r(Xt1[:, 0], 5), yte=r(yt1, 5), grid=r(grid[:, 0]), ref=ref),
                  f, separators=(",", ":"))
    print("wrote ch18-*.json")


FIGURES = {"18.1": fig_18_1, "18.3": fig_18_3, "18.4": fig_18_4, "18.5": fig_18_5, "18.6": fig_18_6,
           "18.7": fig_18_7, "18.8": fig_18_8, "18.9": fig_18_9, "18.10": fig_18_10,
           "18.S1": fig_18_S1, "18.S2": fig_18_S2, "18.S3": fig_18_S3, "18.S4": fig_18_S4, "18.S5": fig_18_S5,
           "18.S6": fig_18_S6, "18.S7": fig_18_S7, "18.S8": fig_18_S8, "18.S9": fig_18_S9}


if __name__ == "__main__":
    if "--json" in sys.argv:
        export_json()
    else:
        common.run(FIGURES, CH)
        if "--fig" not in sys.argv and "--list" not in sys.argv:
            export_json()
