"""Chapter 8 of Hastie, Tibshirani and Friedman (2009), The Elements of Statistical Learning:
"Model Inference and Averaging". Every figure of the chapter that is computed is reproduced
from scratch.

usage:
    python3 ch08_model_inference_averaging.py            # all figures
    python3 ch08_model_inference_averaging.py --fig 8.2  # one figure
    python3 ch08_model_inference_averaging.py --list

What is implemented here (no statistical-learning library is used for the figures):

* cubic B-splines by the Cox-de Boor recursion; least squares, the delta-method (maximum
  likelihood) band, the nonparametric and parametric bootstrap (percentile bands), the Gaussian
  prior on the spline coefficients and its posterior, and a bootstrap that re-chooses the number
  of knots by leave-one-out cross-validation in every sample (Sections 8.2-8.3);
* the bootstrap and the Bayesian (Dirichlet) bootstrap of Section 8.4;
* EM for the two-component Gaussian mixture (Algorithm 8.1), the function F of Section 8.5.3,
  and Gibbs sampling for the mixture: Algorithm 8.4 as printed, the exact full conditional, and a
  full Gibbs sampler with conjugate priors (Section 8.6);
* classification trees grown by the deviance criterion with the stopping rules of the R package
  tree (mincut 5, minsize 10, mindev 0.01), bagging by votes and by averaged probabilities,
  decision stumps and AdaBoost (Section 8.7);
* stacking with leave-one-out predictions, unconstrained and on the simplex, and BIC weights
  (Section 8.8); bumping of a four-leaf tree (Section 8.9);
* the seeded generator of the course's browser demos (mulberry32 with Box-Muller), so that the
  demos' bootstrap samples, Gibbs chains and simulated data sets are reproduced here exactly.

Figures reproduced: 8.1 to 8.13 (all thirteen). Data notes: the 50 points of the smoothing
example (Figures 8.1-8.4) are not distributed with the book, so artificial data of the same kind
are used (N = 50, x uniform on [0, 3], a smooth curve with one dip and two bumps, Gaussian noise);
the twenty points of the mixture example are Table 8.1 of the book. Figure 8.7 is a schematic in
the book; here it is computed exactly for the mixture data, with the latent-data distribution
indexed by the parameter at which the responsibilities are evaluated. Figures 8.10-8.13 use
simulated data generated as the book describes. No figure is skipped.
Supplementary figures:
  8.S1  nonparametric bootstrap against the Bayesian (Dirichlet) bootstrap (Section 8.4);
  8.S2  the Gibbs sampler of Algorithm 8.4 with the exact full conditional for the means;
  8.S3  multiclass versions of the losses of Figure 10.4 (Exercise 8.5);
  8.S4  bone mineral density: smoothing spline bands, posterior bands, bootstrap (Exercise 8.6);
  8.S5  stacking against least-squares weights and BIC weights for best-subset regressions on
        the prostate data (Section 8.8).
"""
import os

for _v in ("OPENBLAS_NUM_THREADS", "MKL_NUM_THREADS", "OMP_NUM_THREADS"):
    os.environ.setdefault(_v, "1")

import json
import math
from itertools import combinations

import numpy as np
from scipy import linalg, optimize, stats
import matplotlib.pyplot as plt

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

CH = 8
HERE = os.path.dirname(os.path.abspath(__file__))
CACHE_DIR = os.path.join(HERE, "cache")
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
TEAL = "#1a9e8f"
LIME = "#22c322"


# =========================================================================== the demos' generator
class DemoRNG:
    """The seeded generator of the course's browser demos (DK.rng in demo-kit.js): mulberry32 for
    uniforms and the Box-Muller transform, keeping the spare normal. Same seed, same numbers."""

    M32 = 0xFFFFFFFF

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

    @staticmethod
    def _imul(x, y):
        return (x * y) & 0xFFFFFFFF

    def u(self):
        a = (self.a + 0x6D2B79F5) & self.M32
        self.a = a
        t = self._imul(a ^ (a >> 15), 1 | a)
        t = ((t + self._imul(t ^ (t >> 7), 61 | t)) & self.M32) ^ t
        return ((t ^ (t >> 14)) & self.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 randint(self, n):
        """floor(u * n), as the demos draw an index in 0..n-1."""
        return int(math.floor(self.u() * n))


# =========================================================================== B-splines
def bspline_basis(x, interior, lo, hi, degree=3):
    """Cubic (by default) B-spline basis on [lo, hi] with the given interior knots, by the
    Cox-de Boor recursion; returns len(x) x (len(interior) + degree + 1)."""
    x = np.atleast_1d(np.asarray(x, float))
    M = degree + 1
    t = np.r_[[lo] * M, np.asarray(interior, float), [hi] * M]
    nb = len(t) - M

    def basis(order):
        # order-1 indicator functions; the last non-empty interval is closed on the right
        B = np.zeros((len(x), len(t) - 1))
        for i in range(len(t) - 1):
            if t[i] < t[i + 1]:
                B[:, i] = (x >= t[i]) & (x < t[i + 1])
        last = np.max(np.nonzero(t[:-1] < t[1:])[0])
        B[x == t[-1], last] = 1.0
        for m in range(2, order + 1):
            Bn = np.zeros((len(x), len(t) - m))
            for i in range(len(t) - m):
                d1, d2 = t[i + m - 1] - t[i], t[i + m] - t[i + 1]
                a = (x - t[i]) / d1 * B[:, i] if d1 > 0 else 0.0
                b = (t[i + m] - x) / d2 * B[:, i + 1] if d2 > 0 else 0.0
                Bn[:, i] = a + b
            B = Bn
        return B

    return basis(M)[:, :nb]


# =========================================================================== Section 8.2: smoothing example
def mu_true(x):
    """The curve behind the artificial smoothing data (our own choice)."""
    x = np.asarray(x, float)
    return (1.3 * np.exp(-((x - 0.55) / 0.38) ** 2) - 0.9 * np.exp(-((x - 1.55) / 0.4) ** 2)
            + 3.0 * np.exp(-((x - 2.72) / 0.38) ** 2) + 0.1)


def smoothing_data(N=50, seed=1, sigma=0.55):
    """N = 50 artificial pairs of the kind shown in Figure 8.1 (the book's are not distributed)."""
    rng = np.random.default_rng(seed)
    x = np.sort(rng.uniform(0, 3, N))
    y = mu_true(x) + sigma * rng.standard_normal(N)
    return np.round(x, 4), np.round(y, 4)


def quartile_knots(x, K=3):
    """K interior knots at the j/(K+1) quantiles of x (three knots: the quartiles)."""
    return np.quantile(x, np.arange(1, K + 1) / (K + 1))


class SplineLS:
    """Least squares on a cubic B-spline basis: (8.2)-(8.4) and the maximum likelihood fit (8.21)."""

    def __init__(self, x, y, knots, lo=None, hi=None):
        self.x, self.y = np.asarray(x, float), np.asarray(y, float)
        self.lo = self.x.min() if lo is None else lo
        self.hi = self.x.max() if hi is None else hi
        self.knots = np.asarray(knots, float)
        self.H = self.basis(self.x)
        self.HtH = self.H.T @ self.H
        self.beta = linalg.solve(self.HtH, self.H.T @ self.y, assume_a="pos")
        self.resid = self.y - self.H @ self.beta
        self.sigma2 = float(self.resid @ self.resid) / len(self.y)       # MLE, divisor N

    def basis(self, x):
        return bspline_basis(np.clip(x, self.lo, self.hi), self.knots, self.lo, self.hi)

    def predict(self, x):
        return self.basis(x) @ self.beta

    def se(self, x):
        """(8.4): [h(x)^T (H^T H)^{-1} h(x)]^{1/2} sigma_hat."""
        h = self.basis(x)
        return np.sqrt(np.einsum("ij,ij->i", h, linalg.solve(self.HtH, h.T, assume_a="pos").T) * self.sigma2)

    def posterior(self, tau, Sigma=None, sigma2=None):
        """(8.27): posterior mean and covariance of beta under beta ~ N(0, tau Sigma)."""
        s2 = self.sigma2 if sigma2 is None else sigma2
        p = self.H.shape[1]
        Sinv = np.eye(p) if Sigma is None else linalg.inv(Sigma)
        A = self.HtH + s2 / tau * Sinv
        mean = linalg.solve(A, self.H.T @ self.y, assume_a="pos")
        cov = linalg.inv(A) * s2
        return mean, cov


def bootstrap_curves(x, y, knots, grid, B=200, seed=1, kind="nonparametric", rng=None, adaptive=False):
    """B bootstrap B-spline fits evaluated on grid. kind 'nonparametric' resamples pairs;
    'parametric' adds N(0, sigma_hat^2) noise to the fitted values (8.6). With rng a DemoRNG the
    draws are the browser demo's. adaptive=True re-chooses the number of knots by LOOCV."""
    base = SplineLS(x, y, knots)
    N = len(x)
    out = np.empty((B, len(grid)))
    if rng is None and kind == "nonparametric":
        r = np.random.default_rng(seed)
    for b in range(B):
        if kind == "nonparametric":
            if isinstance(rng, DemoRNG):
                idx = np.array([rng.randint(N) for _ in range(N)])
            else:
                idx = r.integers(0, N, N)
            xb, yb = x[idx], y[idx]
        else:
            if isinstance(rng, DemoRNG):
                e = np.array([rng.norm() for _ in range(N)])
            else:
                e = np.random.default_rng(seed + b).standard_normal(N)
            xb, yb = x, base.H @ base.beta + math.sqrt(base.sigma2) * e
        kn = knots
        if adaptive:
            kn = quartile_knots(xb, choose_K_loocv(xb, yb, base.lo, base.hi))
        try:
            f = SplineLS(xb, yb, kn, base.lo, base.hi)
            out[b] = f.predict(grid)
        except (linalg.LinAlgError, ValueError):
            out[b] = np.nan
    return out


def percentile_band(curves, lower=0.025, upper=0.975, B=None):
    """Pointwise percentile band. For B = 200 and 95% the book takes the fifth smallest and the
    fifth largest values; this is the order statistic k = floor(B * 0.025 + 1/2) from each end."""
    C = np.sort(curves[~np.isnan(curves).any(1)], axis=0)
    B = len(C)
    k = max(1, int(math.floor(B * lower + 0.5)))
    return C[k - 1], C[B - k]


def loocv_spline(x, y, knots, lo, hi):
    """Leave-one-out CV of a least-squares spline from one fit: mean ((y - yhat)/(1 - h_ii))^2."""
    H = bspline_basis(x, knots, lo, hi)
    Q, _ = np.linalg.qr(H)
    h = (Q ** 2).sum(1)
    r = y - Q @ (Q.T @ y)
    return float(np.mean((r / (1 - h)) ** 2))


def choose_K_loocv(x, y, lo, hi, Ks=range(1, 9)):
    """Number of interior knots (at quantiles) minimising leave-one-out CV."""
    best, bK = np.inf, 1
    for K in Ks:
        kn = quartile_knots(x, K)
        if len(np.unique(x)) < K + 6:
            continue
        try:
            v = loocv_spline(x, y, kn, lo, hi)
        except np.linalg.LinAlgError:
            continue
        if v < best - 1e-12:
            best, bK = v, K
    return bK


# =========================================================================== Section 8.4
def bayes_bootstrap_vs_bootstrap(z, B=4000, seed=0):
    """Draws of the mean of z under the nonparametric bootstrap (multinomial weights / N) and under
    the Bayesian bootstrap (Dirichlet(1,...,1) weights), the a -> 0 posterior of (8.34)."""
    rng = np.random.default_rng(seed)
    N = len(z)
    W_boot = rng.multinomial(N, np.full(N, 1.0 / N), size=B) / N
    W_bayes = rng.dirichlet(np.ones(N), size=B)
    return W_boot @ z, W_bayes @ z


# =========================================================================== Section 8.5: EM
MIX_Y = np.array([-0.39, 0.12, 0.94, 1.67, 1.76, 2.44, 3.72, 4.28, 4.92, 5.53,
                  0.06, 0.48, 1.01, 1.68, 1.80, 3.25, 4.12, 4.60, 5.28, 6.22])   # Table 8.1


def npdf(y, mu, var):
    return np.exp(-0.5 * (y - mu) ** 2 / var) / np.sqrt(2 * np.pi * var)


def mix_loglik(theta, y=MIX_Y):
    """(8.39); theta = (pi, mu1, var1, mu2, var2), pi = Pr(Delta = 1) = weight of component 2."""
    pi, m1, v1, m2, v2 = theta
    return float(np.sum(np.log((1 - pi) * npdf(y, m1, v1) + pi * npdf(y, m2, v2))))


def responsibilities(theta, y=MIX_Y):
    """(8.42): gamma_i = Pr(Delta_i = 1 | theta, y_i)."""
    pi, m1, v1, m2, v2 = theta
    a, b = (1 - pi) * npdf(y, m1, v1), pi * npdf(y, m2, v2)
    return b / (a + b)


def m_step(g, y=MIX_Y):
    """Step 3 of Algorithm 8.1: weighted means and variances, and pi = mean responsibility."""
    w1, w2 = 1 - g, g
    m1 = (w1 @ y) / w1.sum()
    m2 = (w2 @ y) / w2.sum()
    v1 = (w1 @ (y - m1) ** 2) / w1.sum()
    v2 = (w2 @ (y - m2) ** 2) / w2.sum()
    return (float(g.mean()), float(m1), float(v1), float(m2), float(v2))


def em_mixture(theta0, n_iter=20, y=MIX_Y, tol=None):
    """Algorithm 8.1. Returns the list of parameter vectors after each iteration (index 0 is the
    start) and the observed-data log-likelihoods."""
    th = tuple(theta0)
    path, ll = [th], [mix_loglik(th, y)]
    for _ in range(n_iter):
        th = m_step(responsibilities(th, y), y)
        path.append(th)
        ll.append(mix_loglik(th, y))
        if tol is not None and abs(ll[-1] - ll[-2]) < tol:
            break
    return path, np.array(ll)


def em_start(i1=6, i2=3, y=MIX_Y):
    """The book's recipe: the means are two of the y_i, both variances the overall sample variance
    (divisor N), pi = 0.5. We start from y_7 = 3.72 and y_4 = 1.67."""
    v = float(np.var(y))
    return (0.5, float(y[i1]), v, float(y[i2]), v)


def em_mle(y=MIX_Y):
    """Best of the EM runs started from all ordered pairs of data points (the global maximiser
    among the local maxima with positive variances), run to convergence."""
    best = None
    for i in range(len(y)):
        for j in range(len(y)):
            if i == j:
                continue
            p, ll = em_mixture(em_start(i, j, y), 3000, y, tol=1e-13)
            th = p[-1]
            if best is None or ll[-1] > best[1]:
                best = (th, ll[-1])
    th = best[0]
    if th[1] < th[3]:      # component 2 is the left one in the book (mu2 = 1.06)
        th = (1 - th[0], th[3], th[4], th[1], th[2])
    return th, best[1]


def F_function(theta_prime, gamma, y=MIX_Y):
    """(8.48): F(theta', P~) = E_P~[l0(theta'; T)] - E_P~[log P~(Zm)] for independent Bernoulli(gamma_i)."""
    pi, m1, v1, m2, v2 = theta_prime
    g = np.clip(gamma, 1e-300, 1 - 1e-16)
    q = (1 - g) * (np.log(1 - pi) + np.log(npdf(y, m1, v1))) + g * (np.log(pi) + np.log(npdf(y, m2, v2)))
    ent = -(g * np.log(g) + (1 - g) * np.log1p(-g))
    return float(np.sum(q + ent))


# =========================================================================== Section 8.6: Gibbs
def gibbs_mixture(theta_hat, n_iter=200, mu0=None, seed=0, mode="printed", rng=None, y=MIX_Y,
                  prior=None):
    """Gibbs sampling for the two-component mixture.

    mode 'printed': Algorithm 8.4 as printed (variances and pi fixed at theta_hat; mu_k drawn from
                    N(mean of the class-k points, sigma_k^2));
    mode 'exact':   the same with the exact full conditional under a flat prior,
                    mu_k ~ N(mean of the class-k points, sigma_k^2 / n_k);
    mode 'full':    also samples pi ~ Beta and sigma_k^2 ~ inverse gamma under the conjugate prior
                    prior = dict(m0, k0, a0, b0, alpha), mu_k | sigma_k^2 ~ N(m0, sigma_k^2 / k0).
    An empty class makes mu_k a draw from the prior (modes 'printed' and 'exact' then keep mu_k).
    rng may be a DemoRNG (the browser demo's draws). Returns dict of arrays."""
    pi, m1, v1, m2, v2 = theta_hat
    if mu0 is not None:
        m1, m2 = mu0
    if rng is None:
        rng = DemoRNG(seed)
    N = len(y)
    out = {k: [] for k in ("mu1", "mu2", "v1", "v2", "pi", "prop")}
    P = prior or dict(m0=float(np.mean(y)), k0=0.01, a0=2.0, b0=1.0, alpha=1.0)
    for _ in range(n_iter):
        g = responsibilities((pi, m1, v1, m2, v2), y)
        D = np.array([1.0 if rng.u() < g[i] else 0.0 for i in range(N)])
        n2 = D.sum()
        n1 = N - n2
        if mode in ("printed", "exact"):
            if n1 > 0:
                yb1 = float(((1 - D) @ y) / n1)
                m1 = yb1 + math.sqrt(v1 / (1 if mode == "printed" else n1)) * rng.norm()
            if n2 > 0:
                yb2 = float((D @ y) / n2)
                m2 = yb2 + math.sqrt(v2 / (1 if mode == "printed" else n2)) * rng.norm()
        else:
            # pi | Delta ~ Beta(alpha + n2, alpha + n1), drawn as a ratio of gammas
            ga = gamma_draw(rng, P["alpha"] + n2)
            gb = gamma_draw(rng, P["alpha"] + n1)
            pi = ga / (ga + gb)
            new = []
            for (w, nk) in ((1 - D, n1), (D, n2)):
                ybar = float(w @ y) / nk if nk > 0 else 0.0
                ss = float(w @ (y - ybar) ** 2) if nk > 0 else 0.0
                kn = P["k0"] + nk
                mn = (P["k0"] * P["m0"] + nk * ybar) / kn
                an = P["a0"] + nk / 2.0
                bn = P["b0"] + 0.5 * ss + 0.5 * P["k0"] * nk / kn * (ybar - P["m0"]) ** 2
                var = bn / gamma_draw(rng, an)
                mu = mn + math.sqrt(var / kn) * rng.norm()
                new.append((mu, var))
            (m1, v1), (m2, v2) = new
        for k, v in (("mu1", m1), ("mu2", m2), ("v1", v1), ("v2", v2), ("pi", pi), ("prop", n2 / N)):
            out[k].append(v)
    return {k: np.array(v) for k, v in out.items()}


def gamma_draw(rng, a):
    """Gamma(a, 1) by Marsaglia and Tsang (a >= 1; boosted for a < 1), with the demo generator."""
    if a < 1:
        return gamma_draw(rng, a + 1) * rng.pos() ** (1.0 / a)
    d = a - 1.0 / 3.0
    c = 1.0 / math.sqrt(9 * d)
    while True:
        x = rng.norm()
        v = 1 + c * x
        if v <= 0:
            continue
        v = v * v * v
        u = rng.pos()
        if math.log(u) < 0.5 * x * x + d - d * v + d * math.log(v):
            return d * v


def rao_blackwell_density(grid, D_draws, y, var, which=2, flat=True):
    """(8.50): average over draws of the full conditional density of mu_k given Delta (exact
    sampler, flat prior: N(mean of class-k points, var / n_k))."""
    acc = np.zeros_like(grid)
    n = 0
    for D in D_draws:
        w = D if which == 2 else 1 - D
        nk = w.sum()
        if nk == 0:
            continue
        acc += npdf(grid, float(w @ y) / nk, var / nk)
        n += 1
    return acc / max(n, 1)


# =========================================================================== Section 8.7: trees
class Tree:
    """A binary classification tree grown on the deviance criterion with the default stopping rules
    of the R package tree: a node is split only if it has at least minsize cases and deviance at
    least mindev times the root's, and each child must keep at least mincut cases. Cut points are
    midpoints between consecutive distinct values. max_leaves (best-first) caps the size."""

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

    @staticmethod
    def _dev(n1, n):
        """deviance -2 sum n_k log(n_k / n) of a node with n1 of n cases in class 1 (two classes)."""
        n1 = np.asarray(n1, float)
        n = np.asarray(n, float)
        n0 = n - n1
        with np.errstate(divide="ignore", invalid="ignore"):
            t1 = np.where(n1 > 0, n1 * np.log(np.where(n1 > 0, n1, 1) / np.where(n > 0, n, 1)), 0.0)
            t0 = np.where(n0 > 0, n0 * np.log(np.where(n0 > 0, n0, 1) / np.where(n > 0, n, 1)), 0.0)
        return -2.0 * (t1 + t0)

    def _imp(self, n1, n):
        if self.criterion == "deviance":
            return self._dev(n1, n)
        if self.criterion == "gini":
            p = np.where(n > 0, n1 / np.where(n > 0, n, 1), 0)
            return 2 * n * p * (1 - p)
        if self.criterion == "error":
            return np.minimum(n1, n - n1).astype(float)
        raise ValueError(self.criterion)

    def _best_split(self, idx):
        X, y = self.X, self.y
        n = len(idx)
        n1 = y[idx].sum()
        parent = float(self._imp(n1, n))
        best = (0.0, None, None)
        for j in range(X.shape[1]):
            xs = X[idx, j]
            o = np.argsort(xs, kind="mergesort")
            xs, ys = xs[o], y[idx][o]
            c1 = np.cumsum(ys)[:-1]
            nl = np.arange(1, n)
            ok = (xs[1:] > xs[:-1]) & (nl >= self.mincut) & (n - nl >= self.mincut)
            if not ok.any():
                continue
            gain = parent - self._imp(c1, nl) - self._imp(n1 - c1, n - nl)
            gain = np.where(ok, gain, -np.inf)
            k = int(np.argmax(gain))
            if gain[k] > best[0] + 1e-12:
                best = (float(gain[k]), j, 0.5 * (xs[k] + xs[k + 1]))
        return best

    def fit(self, X, y):
        self.X, self.y = np.asarray(X, float), np.asarray(y, int)
        root = self._node(np.arange(len(self.y)), 0)
        self.root_dev = float(self._dev(self.y.sum(), len(self.y)))
        self.nodes = [root]
        frontier = [root]
        nleaves = 1
        while frontier:
            # best-first when max_leaves is set; otherwise every splittable node is split
            if self.max_leaves is not None:
                cand = [(nd["gain"], i) for i, nd in enumerate(frontier) if nd["gain"] > 0]
                if not cand or nleaves >= self.max_leaves:
                    break
                nd = frontier.pop(max(cand)[1])
            else:
                nd = frontier.pop(0)
                if nd["gain"] <= 0:
                    continue
            j, c = nd["var"], nd["cut"]
            L = nd["idx"][self.X[nd["idx"], j] < c]
            R = nd["idx"][self.X[nd["idx"], j] >= c]
            nd["left"], nd["right"] = self._node(L, nd["depth"] + 1), self._node(R, nd["depth"] + 1)
            nd["leaf"] = False
            frontier += [nd["left"], nd["right"]]
            nleaves += 1
        del self.X, self.y
        return self

    def _node(self, idx, depth):
        n = len(idx)
        n1 = int(self.y[idx].sum())
        nd = dict(idx=idx, n=n, n1=n1, p=n1 / n if n else 0.5, leaf=True, depth=depth, gain=0.0,
                  var=None, cut=None)
        dev = float(self._dev(n1, n))
        rootdev = getattr(self, "root_dev", None)
        if rootdev is None:
            rootdev = dev
        if (n >= self.minsize and dev > 0 and dev >= self.mindev * rootdev
                and (self.max_depth is None or depth < self.max_depth)):
            g, j, c = self._best_split(idx)
            if j is not None:
                nd["gain"], nd["var"], nd["cut"] = g, j, c
        return nd

    def predict_proba(self, X):
        X = np.asarray(X, float)
        out = np.empty(len(X))
        stack = [(self.nodes[0], np.arange(len(X)))]
        while stack:
            nd, ii = stack.pop()
            if nd["leaf"]:
                out[ii] = nd["p"]
                continue
            m = X[ii, nd["var"]] < nd["cut"]
            stack.append((nd["left"], ii[m]))
            stack.append((nd["right"], ii[~m]))
        return out

    def predict(self, X):
        """Majority class in the leaf (ties go to class 1, as when p >= 0.5)."""
        return (self.predict_proba(X) >= 0.5).astype(int)

    def leaves(self):
        out, stack = [], [self.nodes[0]]
        while stack:
            nd = stack.pop()
            if nd["leaf"]:
                out.append(nd)
            else:
                stack += [nd["right"], nd["left"]]
        return out

    def splits(self):
        """List of (depth, variable, cut) in depth-first order."""
        out, stack = [], [self.nodes[0]]
        while stack:
            nd = stack.pop()
            if not nd["leaf"]:
                out.append((nd["depth"], nd["var"], nd["cut"]))
                stack += [nd["right"], nd["left"]]
        return out


def sim_corr_data(N, rng, p=5, rho=0.95):
    """Section 8.7.1: p standard Gaussian features with pairwise correlation rho;
    Pr(Y = 1 | x1 <= 0.5) = 0.2 and Pr(Y = 1 | x1 > 0.5) = 0.8. With a DemoRNG the draws are the
    demo's: X = sqrt(rho) z0 + sqrt(1 - rho) z_j, then Y = I(u < p(x1))."""
    if isinstance(rng, DemoRNG):
        X = np.empty((N, p))
        y = np.empty(N, int)
        for i in range(N):
            z0 = rng.norm()
            for j in range(p):
                X[i, j] = math.sqrt(rho) * z0 + math.sqrt(1 - rho) * rng.norm()
            y[i] = 1 if rng.u() < (0.8 if X[i, 0] > 0.5 else 0.2) else 0
        return X, y
    z0 = rng.standard_normal((N, 1))
    X = math.sqrt(rho) * z0 + math.sqrt(1 - rho) * rng.standard_normal((N, p))
    y = (rng.uniform(size=N) < np.where(X[:, 0] > 0.5, 0.8, 0.2)).astype(int)
    return X, y


def bagging_curves(X, y, Xte, B=200, rng=None, seed=0, tree_kw=None, bayes=None):
    """Bag trees: returns the original tree's test predictions and, for b = 1..B, the bagged
    predictions by majority vote and by averaged probabilities; also the trees. bayes(Xte) gives
    the Bayes class, used for the exact conditional error 0.2 + 0.6 * Pr(disagree with Bayes)."""
    tree_kw = tree_kw or {}
    if rng is None:
        rng = np.random.default_rng(seed)
    N = len(y)
    t0 = Tree(**tree_kw).fit(X, y)
    votes = np.zeros(len(Xte))
    probs = np.zeros(len(Xte))
    vote_pred, prob_pred, trees = [], [], []
    for b in range(B):
        if isinstance(rng, DemoRNG):
            idx = np.array([rng.randint(N) for _ in range(N)])
        else:
            idx = rng.integers(0, N, N)
        t = Tree(**tree_kw).fit(X[idx], y[idx])
        trees.append(t)
        pb = t.predict_proba(Xte)
        votes += (pb >= 0.5)
        probs += pb
        vote_pred.append((votes / (b + 1) > 0.5).astype(int))     # ties go to class 0
        prob_pred.append((probs / (b + 1) > 0.5).astype(int))
    return t0, np.array(vote_pred), np.array(prob_pred), trees


def stump_fit(X, y, w=None, rng=None):
    """Single axis-oriented split minimising the (weighted) misclassification error; labels in {0,1}.
    Among tied cut points the middle one of the first run of minimisers is taken; a tie between the
    two features is broken at random when rng is given (otherwise the first feature wins)."""
    N, p = X.shape
    w = np.full(N, 1.0 / N) if w is None else w
    best = (np.inf, None)
    for j in (rng.permutation(p) if rng is not None else range(p)):
        o = np.argsort(X[:, j], kind="mergesort")
        xs, ys, ws = X[o, j], y[o], w[o]
        # left predicts c, right predicts 1-c; error as a function of the cut position k (left = first k)
        wl1 = np.r_[0, np.cumsum(ws * ys)]
        wl0 = np.r_[0, np.cumsum(ws * (1 - ys))]
        tot1, tot0 = wl1[-1], wl0[-1]
        e_c0 = wl1 + (tot0 - wl0)       # left -> 0, right -> 1
        e_c1 = wl0 + (tot1 - wl1)       # left -> 1, right -> 0
        valid = np.r_[True, xs[1:] > xs[:-1], True]
        for c, e in ((0, e_c0), (1, e_c1)):
            e = np.where(valid, e, np.inf)
            m = e.min()
            if m < best[0] - 1e-12:
                ks = np.nonzero(e <= m + 1e-12)[0]
                # first contiguous run of minimisers among valid positions
                run = [ks[0]]
                for k in ks[1:]:
                    if np.all(~valid[run[-1] + 1:k]) or k == run[-1] + 1:
                        run.append(k)
                    else:
                        break
                k = run[len(run) // 2]
                cut = (-np.inf if k == 0 else np.inf if k == N else 0.5 * (xs[k - 1] + xs[k]))
                best = (m, (j, cut, c))
    return best[1]


def stump_predict(st, X):
    j, cut, c = st
    left = X[:, j] < cut
    return np.where(left, c, 1 - c)


def adaboost_stumps(X, y, M=400):
    """AdaBoost.M1 (Algorithm 10.1) with stumps; returns list of (alpha, stump)."""
    N = len(y)
    w = np.full(N, 1.0 / N)
    out = []
    for _ in range(M):
        st = stump_fit(X, y, w)
        miss = stump_predict(st, X) != y
        err = float(w @ miss) / w.sum()
        err = min(max(err, 1e-12), 1 - 1e-12)
        a = math.log((1 - err) / err)
        w = w * np.exp(a * miss)
        w /= w.sum()
        out.append((a, st))
    return out


def adaboost_predict(model, X):
    s = np.zeros(len(X))
    for a, st in model:
        s += a * (2 * stump_predict(st, X) - 1)
    return (s > 0).astype(int)


def wisdom_of_crowds(P, n_sims=50, n_voters=50, n_cat=10, n_nom=4, n_inf=15, seed=0):
    """Figure 8.11: for each category n_inf voters chosen at random pick the correct nominee with
    probability P (else one of the others at random); the rest vote uniformly. Returns arrays of
    the consensus number correct (plurality, ties at random) per simulation and of every
    individual's number correct."""
    rng = np.random.default_rng(seed)
    cons, indiv = [], []
    for _ in range(n_sims):
        correct_ind = np.zeros(n_voters)
        c_cons = 0
        for _c in range(n_cat):
            informed = np.zeros(n_voters, bool)
            informed[rng.choice(n_voters, n_inf, replace=False)] = True
            votes = rng.integers(0, n_nom, n_voters)                      # nominee 0 is correct
            right = rng.uniform(size=n_voters) < P
            wrong = 1 + rng.integers(0, n_nom - 1, n_voters)
            votes = np.where(informed, np.where(right, 0, wrong), votes)
            correct_ind += votes == 0
            cnt = np.bincount(votes, minlength=n_nom)
            winners = np.nonzero(cnt == cnt.max())[0]
            c_cons += rng.choice(winners) == 0
        cons.append(c_cons)
        indiv.append(correct_ind)
    return np.array(cons), np.array(indiv)


def bump_tree(X, y, B=20, rng=None, max_leaves=4):
    """Bumping (Section 8.9): grow a tree with max_leaves leaves on the training data and on B
    bootstrap samples; keep the one with the smallest misclassification error on the training data
    (the original sample is included, so the method may keep the original tree)."""
    rng = rng or np.random.default_rng(0)
    N = len(y)
    cands = [Tree(mincut=1, minsize=2, mindev=0.0, max_leaves=max_leaves).fit(X, y)]
    for _ in range(B):
        idx = rng.integers(0, N, N)
        cands.append(Tree(mincut=1, minsize=2, mindev=0.0, max_leaves=max_leaves).fit(X[idx], y[idx]))
    errs = np.array([np.mean(t.predict(X) != y) for t in cands])
    k = int(np.argmin(errs))
    return cands[0], cands[k], errs, k


# =========================================================================== figures: Sections 8.2-8.3
DEMO_SEED = 1          # the bootstrap demo's default seed: Figure 8.2 uses the same bootstrap samples


def _smooth_setup():
    x, y = smoothing_data()
    kn = quartile_knots(x)
    f = SplineLS(x, y, kn)
    grid = np.linspace(x.min(), x.max(), 301)
    return x, y, kn, f, grid


def _data_ax(ax, x, y, ylab="y"):
    ax.plot(x, y, "o", ms=3.2, color=RED, zorder=4)
    ax.set_xlabel("x")
    ax.set_ylabel(ylab)
    ax.set_xlim(-0.08, 3.08)
    ax.set_ylim(-2.1, 4.0)


def fig_8_1(out=None):
    """Data for the smoothing example and the seven cubic B-spline basis functions."""
    x, y, kn, f, grid = _smooth_setup()
    fig, axes = plt.subplots(1, 2, figsize=(8.4, 3.4))
    _data_ax(axes[0], x, y)
    H = bspline_basis(grid, kn, x.min(), x.max())
    cols = [RED, GREEN, BLUE, PURPLE, ORANGE, CYAN, GREY]
    for j in range(7):
        axes[1].plot(grid, H[:, j], color=cols[j], lw=1.4)
    for k in kn:
        axes[1].axvline(k, color=GREY, ls="--", lw=0.9)
    axes[1].set_xlabel("x")
    axes[1].set_ylabel("B-spline basis")
    axes[1].set_ylim(0, 1.02)
    fig.tight_layout()
    return savefig(fig, CH, "fig8-1", out)


def fig_8_2(out=None):
    """Least squares fit, delta-method band, ten bootstrap fits, bootstrap percentile band."""
    x, y, kn, f, grid = _smooth_setup()
    mu, se = f.predict(grid), f.se(grid)
    curves = bootstrap_curves(x, y, kn, grid, B=200, rng=DemoRNG(DEMO_SEED))
    lo, hi = percentile_band(curves)
    fig, axes = plt.subplots(2, 2, figsize=(8.4, 6.6))
    for ax in axes.flat:
        _data_ax(ax, x, y)
    axes[0, 0].plot(grid, mu, color=LIME, lw=2)
    axes[0, 1].plot(grid, mu, color=LIME, lw=2)
    axes[0, 1].plot(grid, mu + 1.96 * se, "--", color="#555", lw=1)
    axes[0, 1].plot(grid, mu - 1.96 * se, "--", color="#555", lw=1)
    for b in range(10):
        axes[1, 0].plot(grid, curves[b], color=CYAN, lw=1)
    axes[1, 1].plot(grid, mu, color=LIME, lw=2)
    axes[1, 1].plot(grid, lo, "--", color="#555", lw=1)
    axes[1, 1].plot(grid, hi, "--", color="#555", lw=1)
    for ax, lab in zip(axes.flat, "abcd"):
        common.panel_label(ax, lab)
    fig.tight_layout()
    return savefig(fig, CH, "fig8-2", out)


def fig_8_3(out=None):
    """Ten draws from the Gaussian prior beta ~ N(0, I) for mu(x)."""
    x, y, kn, f, grid = _smooth_setup()
    H = f.basis(grid)
    rng = np.random.default_rng(83)
    fig, ax = plt.subplots(figsize=(5.6, 3.6))
    for _ in range(10):
        ax.plot(grid, H @ rng.standard_normal(7), color=LIME, lw=1.1)
    ax.axhline(0, color="k", ls="--", lw=0.8)
    ax.set_xlabel("x")
    ax.set_ylabel(r"$\mu(x)$")
    ax.set_ylim(-3.2, 3.2)
    fig.tight_layout()
    return savefig(fig, CH, "fig8-3", out)


def fig_8_4(out=None):
    """Ten posterior draws of mu(x) for tau = 1 and tau = 1000, with the posterior means."""
    x, y, kn, f, grid = _smooth_setup()
    H = f.basis(grid)
    rng = np.random.default_rng(84)
    fig, axes = plt.subplots(1, 2, figsize=(8.4, 3.6))
    for ax, tau in zip(axes, (1.0, 1000.0)):
        mean, cov = f.posterior(tau)
        L = np.linalg.cholesky(cov)
        _data_ax(ax, x, y, r"$\mu(x)$")
        for _ in range(10):
            ax.plot(grid, H @ (mean + L @ rng.standard_normal(7)), color=LIME, lw=1)
        ax.plot(grid, H @ mean, color=PURPLE, lw=2)
        ax.set_title(r"$\tau = %g$" % tau)
    fig.tight_layout()
    return savefig(fig, CH, "fig8-4", out)


def fig_8_s1(out=None):
    """Supplementary: bootstrap against Bayesian bootstrap for the mean of the Table 8.1 data."""
    zb, zbb = bayes_bootstrap_vs_bootstrap(MIX_Y, B=20000, seed=81)
    fig, ax = plt.subplots(figsize=(5.6, 3.4))
    bins = np.linspace(1.3, 4.3, 61)
    ax.hist(zb, bins=bins, density=True, histtype="stepfilled", alpha=0.45, color=ORANGE, label="bootstrap (multinomial)")
    ax.hist(zbb, bins=bins, density=True, histtype="step", lw=1.6, color=BLUE, label="Bayesian bootstrap (Dirichlet)")
    s = np.std(MIX_Y)
    g = np.linspace(1.3, 4.3, 300)
    ax.plot(g, npdf(g, MIX_Y.mean(), s ** 2 / len(MIX_Y)), "k--", lw=1, label=r"$N(\bar z, \hat\sigma^2/N)$")
    ax.set_xlabel("mean of the 20 values")
    ax.set_ylabel("density")
    ax.legend(frameon=False, fontsize=8, loc="upper left")
    ax.set_ylim(0, 1.3 * ax.get_ylim()[1])
    fig.tight_layout()
    return savefig(fig, CH, "fig8-s1", out)


# =========================================================================== figures: Sections 8.5-8.6
def mle_and_path():
    th_hat, ll_hat = em_mle()
    path, ll = em_mixture(em_start(), 20)
    return th_hat, ll_hat, path, ll


def fig_8_5(out=None):
    """Histogram of the mixture data; ML mixture density and responsibility of the left component."""
    th, _, _, _ = mle_and_path()
    y = MIX_Y
    fig, axes = plt.subplots(1, 2, figsize=(8.4, 3.4))
    axes[0].hist(y, bins=np.arange(-1, 7, 0.5), density=True, color=RED, edgecolor="white")
    axes[0].set_ylim(0, 1)
    axes[0].set_xlabel("y")
    axes[0].set_ylabel("density")
    g = np.linspace(-1, 6.6, 400)
    pi, m1, v1, m2, v2 = th
    axes[1].plot(g, (1 - pi) * npdf(g, m1, v1) + pi * npdf(g, m2, v2), color=RED, lw=1.6, label="ML mixture density")
    axes[1].plot(g, responsibilities(th, g), ":", color=GREEN, lw=1.6, label="responsibility of the left component")
    axes[1].plot(y, responsibilities(th, y), "o", ms=3.5, color=GREEN)
    axes[1].plot(y, np.zeros_like(y), "|", color=PURPLE, ms=8)
    axes[1].set_ylim(-0.02, 1.05)
    axes[1].set_xlabel("y")
    axes[1].set_ylabel("density")
    axes[1].legend(frameon=False, fontsize=8, loc="center right")
    fig.tight_layout()
    return savefig(fig, CH, "fig8-5", out)


def fig_8_6(out=None):
    """Observed-data log-likelihood over the EM iterations."""
    th, llh, path, ll = mle_and_path()
    fig, ax = plt.subplots(figsize=(5.2, 3.6))
    it = np.arange(1, len(ll))
    ax.plot(it, ll[1:], "o", color=GREEN, mfc="none", ms=5)
    ax.axhline(llh, color=GREY, ls="--", lw=0.8)
    ax.set_xlabel("Iteration")
    ax.set_ylabel("Observed data log-likelihood")
    ax.set_xticks([5, 10, 15, 20])
    fig.tight_layout()
    return savefig(fig, CH, "fig8-6", out)


def mm_view(mu_start=3.6, n_steps=6):
    """The function F of (8.48) on a grid for the mixture data, with only mu2 free (the other
    parameters at their ML values); the latent-data distribution is P~_t = Pr(Delta | y, mu2 = t).
    Returns the grid, F, the EM path as (t, mu2) points and the profile curve."""
    th, _ = em_mle()
    pi, m1, v1, _, v2 = th
    th_of = lambda mu2: (pi, m1, v1, mu2, v2)   # noqa: E731
    mus = np.linspace(-0.5, 4.5, 161)
    ts = np.linspace(-0.5, 4.5, 161)
    G = {t: responsibilities(th_of(t)) for t in ts}
    Fg = np.array([[F_function(th_of(mu), G[t]) for t in ts] for mu in mus])
    pts = [(mu_start, mu_start)]
    mu = mu_start
    # start with an E step from a deliberately poor latent distribution (t0) as in the book
    t = mu_start
    path = [(t, mu)]
    for _ in range(n_steps):
        g = responsibilities(th_of(t))
        mu = float((g @ MIX_Y) / g.sum())          # M step: argmax over mu2 of F(., P~_t)
        path.append((t, mu))
        t = mu                                       # E step: argmax over t is t = mu2
        path.append((t, mu))
    return mus, ts, Fg, path, th


def fig_8_7(out=None):
    """Maximisation-maximisation view of EM, computed for the mixture data with mu2 free."""
    mus, ts, Fg, path, th = mm_view(mu_start=4.0)
    fig, ax = plt.subplots(figsize=(5.4, 4.6))
    top = Fg.max()
    levels = top - np.array([12, 8, 5, 3, 1.8, 1.0, 0.5, 0.2])
    cs = ax.contour(ts, mus, Fg, levels=levels, colors="k", linewidths=0.8, linestyles="solid")
    ax.clabel(cs, fmt=lambda v: "%.1f" % v, fontsize=7)
    ax.plot(ts, ts, color=RED, lw=1.4, label=r"profile $\max_{\tilde P}F$ (here $t=\mu_2'$)")
    P = np.array(path)
    for k in range(len(P) - 1):
        (t0, m0), (t1, m1) = P[k], P[k + 1]
        if abs(t1 - t0) < 1e-12 and abs(m1 - m0) < 1e-12:
            continue
        col = GREEN if t1 == t0 else BLUE
        ax.annotate("", xy=(t1, m1), xytext=(t0, m0), arrowprops=dict(arrowstyle="->", color=col, lw=1.3))
        if k < 4:
            ax.text((t0 + t1) / 2 + (0.08 if t1 == t0 else 0), (m0 + m1) / 2 + (0.08 if t1 != t0 else 0),
                    "M" if t1 == t0 else "E", color=col, fontsize=9)
    ax.set_xlabel(r"latent-data parameter $t$ (responsibilities at $\mu_2=t$)")
    ax.set_ylabel(r"model parameter $\mu_2'$")
    ax.set_xlim(-0.5, 4.5)
    ax.set_ylim(-0.5, 4.5)
    ax.legend(frameon=False, fontsize=8, loc="lower right")
    fig.tight_layout()
    return savefig(fig, CH, "fig8-7", out)


GIBBS_SEED = 14


def fig_8_8(out=None):
    """Algorithm 8.4 as printed: 200 Gibbs iterations of the two means and of the proportion."""
    th, _ = em_mle()
    start = em_start()
    G = gibbs_mixture(th, 200, mu0=(start[1], start[3]), rng=DemoRNG(GIBBS_SEED), mode="printed")
    gam = responsibilities(th)
    fig, axes = plt.subplots(1, 2, figsize=(8.4, 3.5))
    it = np.arange(1, 201)
    axes[0].plot(it, G["mu1"], color=ORANGE, lw=0.9)
    axes[0].plot(it, G["mu2"], color="#3a9ad9", lw=0.9)
    axes[0].axhline(th[1], color=GREY, ls="--", lw=0.8)
    axes[0].axhline(th[3], color=GREY, ls="--", lw=0.8)
    axes[0].set_ylim(-1, 8.5)
    axes[0].set_xlabel("Gibbs iteration")
    axes[0].set_ylabel("Mean parameters")
    axes[1].plot(it, G["prop"], color=PURPLE, lw=0.9, drawstyle="steps-mid")
    axes[1].axhline(gam.mean(), color=GREY, ls="--", lw=0.8)
    axes[1].set_ylim(0.25, 0.8)
    axes[1].set_xlabel("Gibbs iteration")
    axes[1].set_ylabel("Mixing proportion")
    fig.tight_layout()
    return savefig(fig, CH, "fig8-8", out)


def fig_8_s2(out=None):
    """Supplementary: the exact full conditional for the means, and the Rao-Blackwell density (8.50)."""
    th, _ = em_mle()
    start = em_start()
    rng = DemoRNG(GIBBS_SEED)
    n_iter = 5000
    G = gibbs_mixture(th, n_iter, mu0=(start[1], start[3]), rng=rng, mode="exact")
    # rerun to collect the Delta draws for (8.50)
    rng2 = DemoRNG(GIBBS_SEED)
    D_draws = []
    pi, m1, v1, m2, v2 = th
    m1, m2 = start[1], start[3]
    for t in range(n_iter):
        g = responsibilities((pi, m1, v1, m2, v2))
        D = np.array([1.0 if rng2.u() < g[i] else 0.0 for i in range(len(MIX_Y))])
        n2 = D.sum()
        n1 = len(D) - n2
        if n1 > 0:
            m1 = float((1 - D) @ MIX_Y) / n1 + math.sqrt(v1 / n1) * rng2.norm()
        if n2 > 0:
            m2 = float(D @ MIX_Y) / n2 + math.sqrt(v2 / n2) * rng2.norm()
        D_draws.append(D)
    burn = 100
    fig, axes = plt.subplots(1, 2, figsize=(8.4, 3.5))
    it = np.arange(1, 201)
    axes[0].plot(it, G["mu1"][:200], color=ORANGE, lw=0.9)
    axes[0].plot(it, G["mu2"][:200], color="#3a9ad9", lw=0.9)
    axes[0].axhline(th[1], color=GREY, ls="--", lw=0.8)
    axes[0].axhline(th[3], color=GREY, ls="--", lw=0.8)
    axes[0].set_ylim(-1, 8.5)
    axes[0].set_xlabel("Gibbs iteration")
    axes[0].set_ylabel("Mean parameters")
    grid = np.linspace(-0.5, 2.8, 300)
    axes[1].hist(G["mu2"][burn:], bins=50, range=(-0.5, 2.8), density=True, color="#3a9ad9", alpha=0.4,
                 label="histogram of draws")
    axes[1].plot(grid, rao_blackwell_density(grid, D_draws[burn:], MIX_Y, v2, which=2), color="k", lw=1.5,
                 label="(8.50): average of conditionals")
    axes[1].axvline(th[3], color=GREY, ls="--", lw=0.8)
    axes[1].set_xlabel(r"$\mu_2$")
    axes[1].set_ylabel("posterior density")
    axes[1].legend(frameon=False, fontsize=8, loc="upper left")
    axes[1].set_ylim(0, 1.25 * axes[1].get_ylim()[1])
    fig.tight_layout()
    return savefig(fig, CH, "fig8-s2", out)


# =========================================================================== figures: Section 8.7
BAG_SEED = 2           # the bagging demo's default seed: Figures 8.9-8.10 use the same data and samples


def bagging_example(seed=BAG_SEED, B=200, N=30, Ntest=2000, rho=0.95, tree_kw=None):
    """Section 8.7.1 with the demo generator: training data from DemoRNG(seed), test data from
    DemoRNG(seed + 1000), bootstrap samples from DemoRNG(seed + 2000)."""
    X, y = sim_corr_data(N, DemoRNG(seed), rho=rho)
    Xt, yt = sim_corr_data(Ntest, DemoRNG(seed + 1000), rho=rho)
    t0, V, P, trees = bagging_curves(X, y, Xt, B=B, rng=DemoRNG(seed + 2000), tree_kw=tree_kw)
    bayes = (Xt[:, 0] > 0.5).astype(int)
    out = dict(X=X, y=y, Xt=Xt, yt=yt, t0=t0, trees=trees, bayes=bayes)
    out["err0"] = float(np.mean(t0.predict(Xt) != yt))
    out["err_vote"] = np.mean(V != yt[None, :], axis=1)
    out["err_prob"] = np.mean(P != yt[None, :], axis=1)
    # exact conditional error given the test inputs: 0.2 + 0.6 Pr(disagree with the Bayes rule)
    out["cerr0"] = 0.2 + 0.6 * float(np.mean(t0.predict(Xt) != bayes))
    out["cerr_vote"] = 0.2 + 0.6 * np.mean(V != bayes[None, :], axis=1)
    out["cerr_prob"] = 0.2 + 0.6 * np.mean(P != bayes[None, :], axis=1)
    return out


def draw_tree(ax, tree, title, names=None):
    """Draw a fitted Tree: internal nodes at the mean position of their leaves, the root split
    annotated, leaves labelled by their majority class."""
    leaves = tree.leaves()
    pos = {id(nd): i for i, nd in enumerate(leaves)}
    maxd = max(nd["depth"] for nd in leaves)

    def place(nd):
        if nd["leaf"]:
            return pos[id(nd)]
        xl, xr = place(nd["left"]), place(nd["right"])
        nd["_x"] = 0.5 * (xl + xr)
        return nd["_x"]

    place(tree.nodes[0])

    def xy(nd):
        return (pos[id(nd)] if nd["leaf"] else nd["_x"]), -nd["depth"]

    def walk(nd):
        if nd["leaf"]:
            x, yv = xy(nd)
            ax.text(x, -maxd - 0.35, "1" if nd["p"] >= 0.5 else "0", ha="center", va="top", fontsize=8)
            return
        x, yv = xy(nd)
        for ch in (nd["left"], nd["right"]):
            cx, cy = xy(ch)
            cy = -maxd if ch["leaf"] else cy
            ax.plot([x, cx, cx], [yv, yv, cy], color="k", lw=0.8)
            walk(ch)

    walk(tree.nodes[0])
    root = tree.nodes[0]
    if not root["leaf"]:
        nm = (names or ["x.%d" % (j + 1) for j in range(5)])[root["var"]]
        ax.text(xy(root)[0], 0.12, "%s < %.3f" % (nm, root["cut"]), ha="center", va="bottom", fontsize=8)
    ax.set_xlim(-0.6, len(leaves) - 0.4)
    ax.set_ylim(-maxd - 1.0, 0.75)
    ax.set_title(title, fontsize=9)
    ax.axis("off")


def fig_8_9(out=None):
    """The original tree and eleven trees grown on bootstrap samples."""
    ex = bagging_example()
    fig, axes = plt.subplots(3, 4, figsize=(9.6, 7.2))
    draw_tree(axes[0, 0], ex["t0"], "Original tree")
    for b, ax in enumerate(axes.flat[1:]):
        draw_tree(ax, ex["trees"][b], "b = %d" % (b + 1))
    fig.tight_layout()
    return savefig(fig, CH, "fig8-9", out)


def fig_8_10(out=None):
    """Test error of the original and the bagged tree against the number of bootstrap samples."""
    ex = bagging_example()
    B = len(ex["err_vote"])
    b = np.arange(1, B + 1)
    fig, ax = plt.subplots(figsize=(6.2, 4.2))
    ax.plot(b, ex["err_vote"], "-o", color=ORANGE, ms=3, mfc="none", lw=0.8, label="Consensus")
    ax.plot(b, ex["err_prob"], "-o", color=TEAL, ms=3, mfc="none", lw=0.8, label="Probability")
    ax.axhline(ex["err0"], color=TEAL, ls="--", lw=1)
    ax.axhline(0.2, color=TEAL, ls="--", lw=1)
    ax.text(100, ex["err0"] + 0.005, "Original Tree", ha="center", fontsize=9)
    ax.text(15, 0.205, "Bayes", fontsize=9)
    ax.text(120, ex["err_vote"][-1] + 0.02, "Bagged Trees", fontsize=9)
    ax.set_ylim(0.18, 0.5)
    ax.set_xlabel("Number of Bootstrap Samples")
    ax.set_ylabel("Test Error")
    ax.legend(frameon=True, fontsize=8, loc="upper right")
    fig.tight_layout()
    return savefig(fig, CH, "fig8-10", out)


def bagging_pointwise(R=60, B=50, N=30, Ntest=1000, seed=500, rho=0.95):
    """For the Section 8.7.1 model: over R training sets, the probability at each test input that
    the single tree and the bagged tree (vote) agree with the Bayes rule."""
    Xt, _ = sim_corr_data(Ntest, np.random.default_rng(seed), rho=rho)
    bayes = (Xt[:, 0] > 0.5).astype(int)
    rng = np.random.default_rng(seed + 1)
    a0 = np.zeros(Ntest)
    ab = np.zeros(Ntest)
    for _ in range(R):
        X, y = sim_corr_data(N, rng, rho=rho)
        t0, V, _, _ = bagging_curves(X, y, Xt, B=B, rng=rng)
        a0 += t0.predict(Xt) == bayes
        ab += V[-1] == bayes
    return Xt, a0 / R, ab / R


def fig_8_s6(out=None):
    """Supplementary: bagging helps where the tree is usually right and hurts where it is usually
    wrong (0-1 loss, Section 8.7)."""
    cache = os.path.join(CACHE_DIR, "ch08_bag_pointwise.npz")
    if os.path.exists(cache):
        z = np.load(cache)
        Xt, a0, ab = z["Xt"], z["a0"], z["ab"]
    else:
        Xt, a0, ab = bagging_pointwise()
        os.makedirs(CACHE_DIR, exist_ok=True)
        np.savez(cache, Xt=Xt, a0=a0, ab=ab)
    fig, axes = plt.subplots(1, 2, figsize=(8.4, 3.6))
    axes[0].scatter(a0, ab, s=6, c=np.abs(Xt[:, 0] - 0.5), cmap="viridis_r", alpha=0.7)
    axes[0].plot([0, 1], [0, 1], "k--", lw=0.8)
    axes[0].axvline(0.5, color=GREY, lw=0.6)
    axes[0].set_xlabel("Pr(single tree agrees with Bayes rule)")
    axes[0].set_ylabel("Pr(bagged tree agrees)")
    order = np.argsort(Xt[:, 0])
    k = 50
    xs = np.convolve(Xt[order, 0], np.ones(k) / k, "valid")
    axes[1].plot(xs, 0.2 + 0.6 * (1 - np.convolve(a0[order], np.ones(k) / k, "valid")), color=TEAL, label="single tree")
    axes[1].plot(xs, 0.2 + 0.6 * (1 - np.convolve(ab[order], np.ones(k) / k, "valid")), color=ORANGE, label="bagged (B = 50)")
    axes[1].axvline(0.5, color=GREY, lw=0.6)
    axes[1].axhline(0.2, color=GREY, ls="--", lw=0.8)
    axes[1].set_xlabel(r"$x_1$ of the test point")
    axes[1].set_ylabel("expected error at x")
    axes[1].legend(frameon=False, fontsize=8)
    fig.tight_layout()
    return savefig(fig, CH, "fig8-s6", out)


def fig_8_11(out=None):
    """Wisdom of crowds: expected number correct out of 10, consensus against individuals."""
    Ps = np.arange(0.25, 1.0001, 0.05)
    rows = []
    for k, P in enumerate(Ps):
        cons, ind = wisdom_of_crowds(P, seed=811 + k)
        rows.append((cons.mean(), cons.std(), ind.mean(), ind.std()))
    R = np.array(rows)
    fig, ax = plt.subplots(figsize=(6.0, 4.2))
    ax.errorbar(Ps, R[:, 0], yerr=R[:, 1], fmt="-o", color="#d95f02", ms=4, lw=0.8, capsize=3, label="Consensus")
    ax.errorbar(Ps, R[:, 2], yerr=R[:, 3], fmt="--o", color="#1b9e77", ms=4, lw=0.8, capsize=3, label="Individual")
    ax.plot(Ps, 10 * (0.3 * Ps + 0.7 * 0.25), ":", color="k", lw=0.8)
    ax.set_ylim(0, 10.4)
    ax.set_xlabel("P, probability that an informed voter is correct")
    ax.set_ylabel("Expected correct out of 10")
    ax.set_title("Wisdom of crowds")
    ax.legend(frameon=True, fontsize=8, loc="upper left")
    fig.tight_layout()
    return savefig(fig, CH, "fig8-11", out)


def linear_boundary_data(N, rng):
    X = rng.uniform(size=(N, 2))
    return X, (X.sum(1) > 1).astype(int)


def fig812_fits(B=50, M=400, seed=812):
    rng = np.random.default_rng(seed)
    X, y = linear_boundary_data(100, rng)
    Xt, yt = linear_boundary_data(20000, np.random.default_rng(seed + 1))
    stumps = []
    for _ in range(B):
        idx = rng.integers(0, 100, 100)
        stumps.append(stump_fit(X[idx], y[idx], rng=rng))
    bag_vote = lambda Z: (np.mean([stump_predict(s, Z) for s in stumps], 0) > 0.5).astype(int)  # noqa: E731
    ada = adaboost_stumps(X, y, M)
    return X, y, Xt, yt, bag_vote, ada


def fig_8_12(out=None):
    """Bagged and boosted decision stumps on data with a diagonal boundary."""
    X, y, Xt, yt, bag_vote, ada = fig812_fits()
    e_bag = np.mean(bag_vote(Xt) != yt)
    e_ada = np.mean(adaboost_predict(ada, Xt) != yt)
    g = np.linspace(0, 1, 301)
    GX, GY = np.meshgrid(g, g)
    Z = np.c_[GX.ravel(), GY.ravel()]
    fig, axes = plt.subplots(1, 2, figsize=(8.0, 4.2))
    for ax, pred, ttl, e in ((axes[0], bag_vote, "Bagged decision rule", e_bag),
                             (axes[1], lambda Q: adaboost_predict(ada, Q), "Boosted decision rule", e_ada)):
        ax.contour(GX, GY, pred(Z).reshape(GX.shape), levels=[0.5], colors=[BLUE], linewidths=1.2)
        ax.plot([0, 1], [1, 0], color="#555", lw=1)
        ax.scatter(X[:, 0], X[:, 1], s=7, c=np.where(y == 1, TEAL, ORANGE))
        ax.set_title("%s (test error %.3f)" % (ttl, e), fontsize=9.5)
        ax.set_xticks([])
        ax.set_yticks([])
        ax.set_xlim(0, 1)
        ax.set_ylim(0, 1)
        ax.set_aspect("equal")
    fig.tight_layout()
    return savefig(fig, CH, "fig8-12", out)


# =========================================================================== figures: Section 8.9
def xor_data(N=200, seed=813):
    rng = np.random.default_rng(seed)
    X = rng.uniform(-1, 1, size=(N, 2))
    return X, (X[:, 0] * X[:, 1] > 0).astype(int)


def bump_xor(seed=813, B=20):
    X, y = xor_data(seed=seed)
    t_reg, t_bump, errs, k = bump_tree(X, y, B=B, rng=np.random.default_rng(seed + 1))
    return X, y, t_reg, t_bump, errs, k


def _draw_partition(ax, tree):
    """Draw the cut lines of a two-feature tree, each restricted to its node's cell."""
    def walk(nd, box, first):
        if nd["leaf"]:
            return
        (x0, x1, y0, y1) = box
        st = dict(color=GREY, lw=1.6, ls="-" if first else "--")
        if nd["var"] == 0:
            ax.plot([nd["cut"]] * 2, [y0, y1], **st)
            walk(nd["left"], (x0, nd["cut"], y0, y1), False)
            walk(nd["right"], (nd["cut"], x1, y0, y1), False)
        else:
            ax.plot([x0, x1], [nd["cut"]] * 2, **st)
            walk(nd["left"], (x0, x1, y0, nd["cut"]), False)
            walk(nd["right"], (x0, x1, nd["cut"], y1), False)
    walk(tree.nodes[0], (-1, 1, -1, 1), True)


def fig_8_13(out=None):
    """XOR data: greedy four-leaf tree against the bumped four-leaf tree (B = 20)."""
    X, y, t_reg, t_bump, errs, k = bump_xor()
    fig, axes = plt.subplots(1, 2, figsize=(8.0, 4.2))
    for ax, t, ttl, e in ((axes[0], t_reg, "Regular 4-node tree", errs[0]), (axes[1], t_bump, "Bumped 4-node tree", errs[k])):
        ax.scatter(X[:, 0], X[:, 1], s=7, c=np.where(y == 1, CYAN, ORANGE))
        _draw_partition(ax, t)
        ax.set_title("%s (training error %.3f)" % (ttl, e), fontsize=9.5)
        ax.set_xlim(-1, 1)
        ax.set_ylim(-1, 1)
        ax.set_xticks([])
        ax.set_yticks([])
        ax.set_aspect("equal")
    fig.tight_layout()
    return savefig(fig, CH, "fig8-13", out)


# =========================================================================== exercises and Section 8.8
def multiclass_losses(m, K=3):
    """Losses of Exercise 8.5 along the symmetric ray f = (a, -a/(K-1), ..., -a/(K-1)) (sum-to-zero
    scores, true class first), as functions of the multiclass margin m = f_y - max_{k != y} f_k =
    a K/(K-1); each is scaled to equal 1 at m = 0."""
    a = m * (K - 1) / K
    f_other = -a / (K - 1)
    dev = np.log1p((K - 1) * np.exp(f_other - a)) / np.log(K)        # multinomial deviance
    expo = np.exp(-a / (K - 1))                                       # exp(-y~^T f / K), y~ = (1, -1/(K-1), ...)
    hinge = np.maximum(0.0, 1.0 - m)                                  # max(0, 1 - margin)
    sq = (1 - a) ** 2                                                 # squared error to y~, scaled
    mis = (m < 0).astype(float)
    return dict(misclassification=mis, exponential=expo, deviance=dev, squared=sq, hinge=hinge)


def multiclass_losses_split(m, d, K=3):
    """K = 3: true-class score margin m over the larger wrong score, the two wrong scores d apart."""
    f = np.stack([np.full_like(d, m), np.zeros_like(d), -d], 1)
    f = f - f.mean(1, keepdims=True)
    y = np.array([1.0, -0.5, -0.5])
    dev = (np.log(np.exp(f).sum(1)) - f[:, 0]) / np.log(3)
    expo = np.exp(-(f @ y) / 3)
    hinge = np.maximum(0, 1 - (f[:, 0] - f[:, 1:].max(1)))
    llw = np.maximum(0, f[:, 1:] + 0.5).sum(1)                      # Lee, Lin and Wahba (2004)
    return dict(deviance=dev, exponential=expo, hinge=hinge, llw=llw)


def fig_8_s3(out=None):
    """Supplementary (Exercise 8.5): multiclass losses as functions of the margin."""
    mg = np.linspace(-2, 2, 401)
    L = multiclass_losses(mg)
    fig, axes = plt.subplots(1, 2, figsize=(8.6, 3.6))
    cols = dict(misclassification="k", exponential=CYAN, deviance=ORANGE, squared=BLUE, hinge=GREEN)
    labs = dict(misclassification="Misclassification", exponential="Exponential", deviance="Multinomial deviance",
                squared="Squared error", hinge="Multiclass hinge")
    for k, v in L.items():
        axes[0].plot(mg, v, color=cols[k], lw=1.5, label=labs[k])
    axes[0].set_ylim(0, 3)
    axes[0].set_xlabel(r"margin $f_y-\max_{k\neq y}f_k$ (other scores equal)")
    axes[0].set_ylabel("loss")
    axes[0].legend(frameon=False, fontsize=7.5)
    d = np.linspace(0, 3, 301)
    S = multiclass_losses_split(0.5, d)
    for k, c, lab in (("deviance", ORANGE, "Multinomial deviance"), ("exponential", CYAN, "Exponential"),
                      ("hinge", GREEN, "Multiclass hinge"), ("llw", PURPLE, "Sum of hinges")):
        axes[1].plot(d, S[k], color=c, lw=1.5, label=lab)
    axes[1].set_xlabel("gap between the two wrong-class scores (margin 0.5)")
    axes[1].set_ylabel("loss")
    axes[1].legend(frameon=False, fontsize=7.5)
    fig.tight_layout()
    return savefig(fig, CH, "fig8-s3", out)


def bspline_penalty(knots_all, lo, hi):
    """Omega_jk = int B_j''(t) B_k''(t) dt for the cubic B-splines with interior knots knots_all,
    by 4-point Gauss-Legendre quadrature on each interval (exact: the integrand is quadratic)."""
    from scipy.interpolate import BSpline
    t = np.r_[[lo] * 4, knots_all, [hi] * 4]
    nb = len(t) - 4
    br = np.unique(np.r_[lo, knots_all, hi])
    gx, gw = np.polynomial.legendre.leggauss(4)
    Om = np.zeros((nb, nb))
    for a, b in zip(br[:-1], br[1:]):
        xs = 0.5 * (b - a) * gx + 0.5 * (a + b)
        D = np.column_stack([BSpline(t, np.eye(nb)[j], 3).derivative(2)(xs) for j in range(nb)])
        Om += D.T @ (D * (0.5 * (b - a) * gw)[:, None])
    return Om


class PenalisedSpline:
    """Cubic smoothing spline as a B-spline expansion with knots at the distinct x values and the
    penalty lambda beta^T Omega beta (the same minimiser as the natural-spline form of Chapter 5)."""

    def __init__(self, x, y, lam=None, df=None):
        self.x, self.y = np.asarray(x, float), np.asarray(y, float)
        self.lo, self.hi = self.x.min(), self.x.max()
        u = np.unique(self.x)
        self.kn = u[1:-1]
        self.H = self.basis(self.x)
        self.Om = bspline_penalty(self.kn, self.lo, self.hi)
        self.HtH = self.H.T @ self.H
        if lam is None:
            lam = self.lam_for_df(df)
        self.set_lam(lam)

    def basis(self, x):
        return bspline_basis(np.clip(x, self.lo, self.hi), self.kn, self.lo, self.hi)

    def set_lam(self, lam):
        self.lam = lam
        self.A = self.HtH + lam * self.Om
        self.Ainv = linalg.inv(self.A)
        self.beta = self.Ainv @ (self.H.T @ self.y)
        self.S = self.H @ self.Ainv @ self.H.T
        self.df = float(np.trace(self.S))
        r = self.y - self.H @ self.beta
        self.rss = float(r @ r)
        self.sigma2 = self.rss / (len(self.y) - self.df)
        self.loocv = float(np.mean((r / (1 - np.diag(self.S))) ** 2))
        return self

    def df_of(self, lam):
        return float(np.trace(linalg.solve(self.HtH + lam * self.Om, self.HtH, assume_a="pos")))

    def lam_for_df(self, df):
        return float(np.exp(optimize.brentq(lambda L: self.df_of(np.exp(L)) - df, -25, 25)))

    def predict(self, x):
        return self.basis(x) @ self.beta

    def var_freq(self, x):
        """sigma^2 h^T A^{-1} H^T H A^{-1} h: sampling variance of the fit (bias ignored)."""
        h = self.basis(x) @ self.Ainv
        return self.sigma2 * np.einsum("ij,jk,ik->i", h, self.HtH, h)

    def var_post(self, x):
        """(8.28) with Sigma^{-1} = Omega and tau = sigma^2 / lambda: sigma^2 h^T A^{-1} h."""
        h = self.basis(x)
        return self.sigma2 * np.einsum("ij,jk,ik->i", h, self.Ainv, h)


def bone_females():
    d = common.esl_data("bone.data")
    d = d[d.gender == "female"]
    return d.age.to_numpy(float), d.spnbmd.to_numpy(float)


def bone_exercise(B=100, seed=86):
    x, y = bone_females()
    sp0 = PenalisedSpline(x, y, lam=1.0)
    # choose lambda by leave-one-out CV over a grid of df, then refine
    dfs = np.linspace(3, 20, 69)
    cvs = []
    for df in dfs:
        sp0.set_lam(sp0.lam_for_df(df))
        cvs.append(sp0.loocv)
    k = int(np.argmin(cvs))
    res = optimize.minimize_scalar(lambda L: sp0.set_lam(np.exp(L)).loocv,
                                   bounds=(np.log(sp0.lam_for_df(dfs[min(k + 1, len(dfs) - 1)])),
                                           np.log(sp0.lam_for_df(dfs[max(k - 1, 0)]))), method="bounded")
    sp = sp0.set_lam(float(np.exp(res.x)))
    grid = np.linspace(x.min(), x.max(), 200)
    fit = sp.predict(grid)
    z = stats.norm.ppf(0.95)
    sf, sb = np.sqrt(sp.var_freq(grid)), np.sqrt(sp.var_post(grid))
    rng = np.random.default_rng(seed)
    curves = np.empty((B, len(grid)))
    for b in range(B):
        idx = rng.integers(0, len(x), len(x))
        xb, yb = x[idx], y[idx]
        # same lambda, basis on the original knots (evaluation outside the resample's range is fine)
        Hb = sp.basis(xb)
        beta = linalg.solve(Hb.T @ Hb + sp.lam * sp.Om, Hb.T @ yb, assume_a="pos")
        curves[b] = sp.basis(grid) @ beta
    lo, hi = np.percentile(curves, [5, 95], axis=0)
    return dict(x=x, y=y, sp=sp, grid=grid, fit=fit, freq=(fit - z * sf, fit + z * sf),
                post=(fit - z * sb, fit + z * sb), boot=(lo, hi), curves=curves, dfs=dfs, cvs=np.array(cvs),
                sf=sf, sb=sb)


def fig_8_s4(out=None):
    """Supplementary (Exercise 8.6): smoothing spline for female spinal BMD with 90% bands."""
    E = bone_exercise()
    fig, axes = plt.subplots(1, 3, figsize=(11.4, 3.6), sharey=True)
    for ax in axes:
        ax.plot(E["x"], E["y"], "o", ms=2, color=GREY, alpha=0.6)
        ax.plot(E["grid"], E["fit"], color=RED, lw=1.6)
        ax.set_xlabel("age")
        ax.axhline(0, color="k", lw=0.5)
    axes[0].set_ylabel("relative change in spinal BMD")
    axes[0].fill_between(E["grid"], *E["freq"], color=BLUE, alpha=0.25, lw=0)
    axes[0].set_title("(a) df = %.1f by LOOCV; 90%% sampling band" % E["sp"].df, fontsize=9)
    axes[1].fill_between(E["grid"], *E["post"], color=GREEN, alpha=0.25, lw=0)
    axes[1].plot(E["grid"], E["freq"][0], "--", color=BLUE, lw=0.8)
    axes[1].plot(E["grid"], E["freq"][1], "--", color=BLUE, lw=0.8)
    axes[1].set_title("(b) 90% posterior band (8.28); dashed: (a)", fontsize=9)
    for c in E["curves"]:
        axes[2].plot(E["grid"], c, color=CYAN, lw=0.4, alpha=0.5)
    axes[2].plot(E["grid"], E["boot"][0], "--", color="k", lw=0.9)
    axes[2].plot(E["grid"], E["boot"][1], "--", color="k", lw=0.9)
    axes[2].plot(E["grid"], E["fit"], color=RED, lw=1.6)
    axes[2].set_title("(c) 100 bootstrap fits, 5% and 95% points", fontsize=9)
    axes[0].set_ylim(-0.08, 0.22)
    fig.tight_layout()
    return savefig(fig, CH, "fig8-s4", out)


def prostate_split():
    d = common.esl_data("prostate.data")
    if "Unnamed: 0" in d.columns:
        d = d.drop(columns="Unnamed: 0")
    names = ["lcavol", "lweight", "age", "lbph", "svi", "lcp", "gleason", "pgg45"]
    X = d[names].to_numpy(float)
    y = d["lpsa"].to_numpy(float)
    tr = (d["train"] == "T").to_numpy()
    mu, sd = X[tr].mean(0), X[tr].std(0, ddof=1)
    X = (X - mu) / sd
    return X[tr], y[tr], X[~tr], y[~tr], names


def best_subsets(X, y):
    """For each size k = 0..p, the subset with the smallest residual sum of squares (intercept always in)."""
    N, p = X.shape
    out = {0: ()}
    for k in range(1, p + 1):
        best = None
        for S in combinations(range(p), k):
            A = np.c_[np.ones(N), X[:, S]]
            r = y - A @ np.linalg.lstsq(A, y, rcond=None)[0]
            rss = float(r @ r)
            if best is None or rss < best[0]:
                best = (rss, S)
        out[k] = best[1]
    return out


def stacking_example():
    """Section 8.8 on the prostate data: models m = best subset of size m (m = 0..8, subsets chosen
    on the training data and held fixed); weights from (i) least squares on the fitted values,
    (ii) stacking (8.59), unconstrained, (iii) stacking with w >= 0 and sum w = 1, (iv) BIC."""
    X, y, Xt, yt, names = prostate_split()
    N = len(y)
    subs = best_subsets(X, y)
    F, Floo, Ft, bic = [], [], [], []
    for k in range(len(subs)):
        A = np.c_[np.ones(N), X[:, list(subs[k])]]
        At = np.c_[np.ones(len(yt)), Xt[:, list(subs[k])]]
        beta = np.linalg.lstsq(A, y, rcond=None)[0]
        Hm = A @ np.linalg.pinv(A)
        f = A @ beta
        F.append(f)
        Floo.append(y - (y - f) / (1 - np.diag(Hm)))
        Ft.append(At @ beta)
        s2 = float((y - f) @ (y - f)) / N
        bic.append(N * np.log(s2) + np.log(N) * (A.shape[1] + 1))
    F, Floo, Ft, bic = (np.array(v).T for v in (F, Floo, Ft, bic))
    bic = bic.ravel()
    w_ls = np.linalg.lstsq(F, y, rcond=None)[0]
    w_st = np.linalg.lstsq(Floo, y, rcond=None)[0]
    M = F.shape[1]
    cons = ({"type": "eq", "fun": lambda w: w.sum() - 1},)
    obj = lambda w: float(np.sum((y - Floo @ w) ** 2))   # noqa: E731
    grad = lambda w: -2 * Floo.T @ (y - Floo @ w)          # noqa: E731
    r = optimize.minimize(obj, np.full(M, 1.0 / M), jac=grad, bounds=[(0, 1)] * M, constraints=cons,
                          method="SLSQP", options=dict(ftol=1e-14, maxiter=1000))
    w_sc = np.maximum(r.x, 0)
    w_sc /= w_sc.sum()
    w_bic = np.exp(-0.5 * (bic - bic.min()))
    w_bic /= w_bic.sum()
    loo = np.mean((y[:, None] - Floo) ** 2, 0)
    k_loo = int(np.argmin(loo))
    te = lambda w: float(np.mean((yt - Ft @ w) ** 2))      # noqa: E731
    one = lambda k: np.eye(M)[k]                            # noqa: E731
    return dict(subs=subs, names=names, w_ls=w_ls, w_st=w_st, w_sc=w_sc, w_bic=w_bic, loo=loo, k_loo=k_loo,
                test=dict(full=te(one(M - 1)), loo_choice=te(one(k_loo)), stack=te(w_st), stack_simplex=te(w_sc),
                          bic=te(w_bic), ls=te(w_ls)),
                F=F, Floo=Floo, Ft=Ft, y=y, yt=yt, bic=bic)


def fig_8_s5(out=None):
    """Supplementary (Section 8.8): model weights for the best-subset models on the prostate data."""
    S = stacking_example()
    M = len(S["w_ls"])
    k = np.arange(M)
    fig, ax = plt.subplots(figsize=(7.2, 3.6))
    wd = 0.2
    for j, (key, c, lab) in enumerate((("w_ls", GREY, "least squares on fitted values"),
                                       ("w_st", ORANGE, "stacking (8.59)"),
                                       ("w_sc", TEAL, "stacking, w >= 0, sum 1"),
                                       ("w_bic", PURPLE, "BIC weights"))):
        ax.bar(k + (j - 1.5) * wd, S[key], width=wd, color=c,
               label="%s (test MSE %.3f)" % (lab, S["test"][{"w_ls": "ls", "w_st": "stack", "w_sc": "stack_simplex", "w_bic": "bic"}[key]]))
    ax.axhline(0, color="k", lw=0.6)
    ax.set_ylim(-0.45, 1.25)
    for kk, v in enumerate(S["w_st"]):
        if abs(v) > 1.2:   # unconstrained stacking weights that run off the plot
            ax.text(kk - 0.5 * wd - 0.12, 1.12 if v > 0 else -0.38, "%+.2f" % v, ha="right", fontsize=7, color=ORANGE)
    ax.set_xticks(k)
    ax.set_xlabel("model: best subset of size m")
    ax.set_ylabel("weight")
    ax.legend(frameon=False, fontsize=7.5, loc="upper left")
    fig.tight_layout()
    return savefig(fig, CH, "fig8-s5", out)


# =========================================================================== data for the demos
def export_demo_data():
    os.makedirs(DATA_OUT, exist_ok=True)
    x, y = smoothing_data()
    th, ll = em_mle()
    out = dict(note="Artificial smoothing data of the kind of Hastie, Tibshirani and Friedman (2009), Figure 8.1, "
                    "and the twenty points of their Table 8.1.",
               x=[float(v) for v in x], y=[float(v) for v in y],
               mixture=[float(v) for v in MIX_Y], em_start=list(em_start()), mle=list(th), mle_loglik=ll)
    path = os.path.join(DATA_OUT, "ch08-inference.json")
    with open(path, "w") as f:
        json.dump(out, f, separators=(",", ":"))
    print("wrote", os.path.relpath(path, os.getcwd()))


FIGURES = {
    "8.1": fig_8_1, "8.2": fig_8_2, "8.3": fig_8_3, "8.4": fig_8_4, "8.S1": fig_8_s1,
    "8.5": fig_8_5, "8.6": fig_8_6, "8.7": fig_8_7, "8.8": fig_8_8, "8.S2": fig_8_s2,
    "8.9": fig_8_9, "8.10": fig_8_10, "8.S6": fig_8_s6, "8.11": fig_8_11, "8.12": fig_8_12, "8.13": fig_8_13,
    "8.S3": fig_8_s3, "8.S4": fig_8_s4, "8.S5": fig_8_s5,
}

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