"""Hastie, Tibshirani and Friedman (2009), Chapter 16: Ensemble Learning.

Reproduces the figures of Chapter 16 of T. Hastie, R. Tibshirani and J. Friedman, The Elements of
Statistical Learning, 2nd edition (Springer, 2009), pp. 605-624, written from scratch with numpy,
scipy and matplotlib (scikit-learn supplies only the CART base learners, the random forests of
Figures 16.6 and 16.8, and, for the post-processing of thousands of trees in Figures 16.6-16.8
and 16.10, a compiled lasso solver that our own coordinate descent lasso_cd_gram reproduces). Every method the chapter is about is a small function meant to be
read next to the lecture notes (../ch16-ensemble-learning.html):

* Section 16.2.1, the lasso and forward stagewise paths: lars_gram (least angle regression on the
  Gram matrix, with the lasso modification and the FS0 modification, exact step lengths),
  nnls_gram (the sign-constrained direction of FS0, a Lawson-Hanson active-set solver written in
  Gram form), fs_eps_gram (Algorithm 16.1 with the original variables as the dictionary),
  lasso_cd_gram (pathwise coordinate descent on a Gram matrix, used for post-processing).
* Section 16.2.2, the bet-on-sparsity simulation of Figure 16.2 and Exercise 16.4: bos_draw,
  bos_scale (the scaling that gives a target noise-to-signal ratio, by bisection for the logistic
  case), the exact test errors of a linear fit under Gaussian inputs (pe_regression,
  err_classification; no test sample is needed), best_lasso and best_ridge (the best test error
  along the whole path, minimised exactly segment by segment for the lasso).
* Section 16.2.3, the block-correlated simulation of Figures 16.3-16.4 and Exercise 16.1
  (block_data), and the L1 margin (16.7) of boosted trees on the mixture data (Figure 16.5,
  boost_exponential: gradient boosting with the exponential loss of AdaBoost, Newton leaf values,
  shrinkage 0.02, and lp_max_margin, the largest L1 margin attainable with the same trees).
* Section 16.3, learning ensembles: isle_generate (Algorithm 16.2; with nu = 0 and sampling with
  replacement it is bagging, with eta = 1 it is gradient boosting, with eta < 1 stochastic gradient
  boosting), post_process (the lasso path (16.9) on the trees' outputs), rule_matrix and rulefit
  (Section 16.3.2: every node of every tree becomes a 0/1 rule (16.14), optionally with winsorised
  linear terms, and the lasso picks a few, with lambda chosen by 5-fold cross-validation).
* The browser demonstrations: demo_block_data, demo_bos_data and demo_isle_data draw the demos' data
  with the demos' own seeded generator (JSRandom, the port of DK.rng in ch10_boosting), and
  ls_tree_demo / isle_demo grow exactly the trees the ISLE demonstration grows, so the Python
  functions give the same numbers as stagewise-lasso-demo.html, bet-on-sparsity-demo.html and
  isle-postprocessing-demo.html.

Figures reproduced: 16.1, 16.2, 16.3, 16.4, 16.5, 16.6, 16.7, 16.8, 16.10. Run
`python3 ch16_ensemble_learning.py --list`, `python3 ch16_ensemble_learning.py` (all figures, about
twenty minutes the first time; ensembles are cached in cache/) or
`python3 ch16_ensemble_learning.py --fig 16.2`. Files go to ../img/ch16/.

Figures not reproduced, and why:
* Figure 16.9 is a drawing of a small tree with made-up split values (nothing is computed). Its rule
  set (16.14) is checked numerically instead (Exercise 16.3).
* Table 16.1 shows part of a 15-bit code matrix from Dietterich and Bakiri (1995) without the rows
  needed to reproduce it.

Settings chosen where the book gives none:
* Figure 16.1: the prostate training data (67 men), predictors standardised over all 97 men as in
  Chapter 3, centred; forward stagewise with eps = 0.01 run for 250 steps (the text says 250, the
  caption 220).
* Figure 16.2: per scenario and noise-to-signal ratio, 20 independent draws (numpy
  default_rng(1602)) of X (50 x 300, independent N(0, 1) entries) and of the nonzero coefficients
  (independent N(0, 1)); the test error is the exact population error of the fitted linear function
  (Gaussian inputs make it a closed form for regression and a one-dimensional integral for
  classification), the 'infinite test set' of the book. Lasso: the best error over the entire
  piecewise-linear path. Ridge: the best error over 200 log-spaced penalties together with the
  least-squares limit lambda -> 0 (from df = 1 to the maximum, 49 after centring). Percentage of
  error explained: 1 - PE / PE(constant) for regression, PE(constant) = Var(Y); 1 - err / 0.5 for
  classification.
* Figures 16.3-16.4: N = 60, p = 1000 in 50 blocks of 20 with within-block correlation 0.95, one
  nonzero N(0, 1) coefficient per block at a random position, noise variance 0.72 times the
  population variance of the linear predictor; default_rng(163). Coefficients are for the
  predictors standardised to unit sample variance. The test mean squared error of Figure 16.4 is
  the exact population error E(f_hat(X) - f(X))^2 (no noise), computed from the block covariance.
* Figure 16.5: the mixture data of Chapter 2 (200 points), trees with 4 terminal nodes, shrinkage
  0.02, 10,000 trees, the exponential loss with Newton leaf values; the test error is on the
  10,000-point test sample of Chapter 2. The margin (16.7) treats every shrunken tree nu*T_m as one
  dictionary element scaled to have largest absolute value 1, so sum |alpha_k| = nu * sum_m
  max_j |gamma_jm|.
* Figures 16.6-16.7: the spam data with the book's training/test split. Random forest: 1000 trees,
  m = 7, grown to maximum depth (scikit-learn, random_state=166). The 'Random Forest (5%, 6)'
  ensemble: each tree on a 5% subsample drawn without replacement, 6 terminal nodes, m = 7.
  Gradient boosting: binomial deviance, 5 terminal nodes, nu = 0.1, eta = 1 (Figure 16.6) and the
  ISLE generator eta = 1/2, nu = 0.05, 2500 trees (Figure 16.7). Post-processing: the lasso path
  (16.9) with squared-error loss on the 0/1 response (as the book does for the classification
  problems of Figure 16.2), trees' outputs used unstandardised, classify by f > 1/2; 100 penalties
  down to 1/1000 of the largest.
* Figure 16.8: the model (16.13), N = 1000 training and 500 test points (default_rng(168)),
  sigma = 1.3; boosted trees have 6 terminal nodes and 2500 trees; the random forest has 1000
  trees with m = 33 (p/3) grown to maximum depth; 'ISLE GB' post-processes GBM(0.1, 0.01) and
  'ISLE RF' the random forest, plotted against the number of trees with nonzero coefficients.
* Figure 16.10: 20 realisations of (16.13) (training sets from default_rng(1610 + r), test sets of
  5000 points); rule ensembles grown by Algorithm 16.2 with eta = min(1/2, (100 + 6 sqrt(N))/N),
  nu = 0.01, tree sizes 2 + floor(an exponential draw with mean 2) (about 3.5 terminal nodes on average),
  enough trees for about 2000 rules; 'Rules + Linear' adds the 100 inputs winsorised at their 2.5% and
  97.5% quantiles and scaled to standard deviation 0.4; lambda by 5-fold cross-validation.
"""
import json
import math
import os
import pickle

import numpy as np

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

CH = 16
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")
JSRandom = ch10.JSRandom
PNAMES = ["lcavol", "lweight", "age", "lbph", "svi", "lcp", "gleason", "pgg45"]
PCOL = [RED, BLUE, GREEN, ORANGE, PURPLE, CYAN, MAGENTA, "#8c564b"]


def _cache(name, build):
    """Load cache/ch16_<name>.pkl or build it (slow results only)."""
    path = os.path.join(CACHE_DIR, "ch16_%s.pkl" % name)
    if os.path.exists(path):
        with open(path, "rb") as f:
            return pickle.load(f)
    obj = build()
    os.makedirs(CACHE_DIR, exist_ok=True)
    with open(path, "wb") as f:
        pickle.dump(obj, f)
    return obj


# =========================================================================== Section 16.2.1: paths
def nnls_gram(Q, b, tol=1e-12, max_iter=500):
    """argmin_{c >= 0} 1/2 c^T Q c - b^T c by the Lawson-Hanson active-set method, written with the
    Gram matrix Q (positive semidefinite) instead of the design matrix. With Q = S X_A^T X_A S and
    b = 1 this is the direction of the FS0 modification of least angle regression."""
    k = len(b)
    x = np.zeros(k)
    P = np.zeros(k, bool)
    w = b - Q @ x
    for _ in range(max_iter):
        Z = ~P
        if not Z.any() or w[Z].max() <= tol:
            break
        j = int(np.flatnonzero(Z)[np.argmax(w[Z])])
        P[j] = True
        while True:
            idx = np.flatnonzero(P)
            z = np.zeros(k)
            z[idx] = np.linalg.lstsq(Q[np.ix_(idx, idx)], b[idx], rcond=None)[0]
            if np.all(z[idx] > tol):
                x = z
                break
            neg = idx[z[idx] <= tol]
            alpha = np.min(x[neg] / (x[neg] - z[neg]))
            x = x + alpha * (z - x)
            P &= x > tol
            x[~P] = 0.0
        w = b - Q @ x
    return x


def lars_gram(G, b, method="lasso", maxrank=None, tol=1e-11, max_steps=20000):
    """Least angle regression from the Gram matrix G = X^T X and b = X^T y of centred data, with exact
    step lengths. method 'lar' (Algorithm 3.2), 'lasso' (modification 3.2a: a coefficient that
    reaches zero leaves the active set; the lasso path of (16.2) with lambda = max_j |c_j|), or
    'fs0' (modification 3.2b: the direction is the sign-constrained least-squares fit, the limit of
    Algorithm 16.1 as eps -> 0). Returns the coefficients at the knots (rows), lam = max |c| at each
    knot, and the events."""
    p = len(b)
    maxrank = maxrank or p
    beta = np.zeros(p)
    c = b.astype(float).copy()
    C = float(np.max(np.abs(c)))
    C0 = C
    A = [int(np.argmax(np.abs(c)))]
    betas, lams, events = [beta.copy()], [C], [("enter", A[0])]
    last_drop = None
    for _ in range(max_steps):
        if C <= tol * max(1.0, C0):
            break
        s = np.sign(c[A])
        if method == "fs0":
            GA = G[np.ix_(A, A)] * np.outer(s, s)
            cc = nnls_gram(GA, np.ones(len(A)))
            keep = cc > 1e-10 * max(1.0, cc.max())
            A = [A[i] for i in range(len(A)) if keep[i]]
            w = s[keep] * cc[keep]
        else:
            w = np.linalg.solve(G[np.ix_(A, A)], s)
        a = G[:, A] @ w
        gam, nxt, kind = C, None, "end"
        if len(A) < maxrank:
            inact = np.ones(p, bool)
            inact[A] = False
            if last_drop is not None:
                inact[last_drop] = False
            with np.errstate(divide="ignore", invalid="ignore"):
                g1 = np.where(1 - a > 1e-15, (C - c) / (1 - a), np.inf)
                g2 = np.where(1 + a > 1e-15, (C + c) / (1 + a), np.inf)
            g = np.minimum(np.where(g1 > tol, g1, np.inf), np.where(g2 > tol, g2, np.inf))
            g[~inact] = np.inf
            j = int(np.argmin(g))
            if g[j] < gam:
                gam, nxt, kind = float(g[j]), j, "enter"
        last_drop = None
        if method == "lasso":
            bA = beta[A]
            with np.errstate(divide="ignore", invalid="ignore"):
                gd = np.where((w != 0) & (bA != 0), -bA / w, np.inf)
            gd[gd <= tol] = np.inf
            i = int(np.argmin(gd))
            if gd[i] < gam - 1e-14:
                gam, nxt, kind = float(gd[i]), A[i], "drop"
        beta[A] += gam * w
        C = C - gam
        if kind == "drop":
            beta[nxt] = 0.0
            A = [j for j in A if j != nxt]
            last_drop = nxt
        c = b - G @ beta
        if kind == "enter":
            A = A + [nxt]
        betas.append(beta.copy())
        lams.append(max(C, 0.0))
        events.append((kind, nxt))
        if kind == "end":
            break
    return dict(beta=np.array(betas), lam=np.array(lams), events=events)


def fs_eps_gram(G, b, eps, nsteps):
    """Algorithm 16.1 (incremental forward stagewise) with the columns of X as the dictionary, from
    G = X^T X and b = X^T y. At each step the column with the largest |inner product| with the
    residual (the best single-term least-squares fit when the columns have equal norms) moves by
    eps in the direction of that inner product. Returns the coefficients after each step (rows)."""
    p = len(b)
    beta = np.zeros(p)
    c = b.astype(float).copy()
    out = np.empty((nsteps + 1, p))
    out[0] = beta
    for t in range(nsteps):
        j = int(np.argmax(np.abs(c)))
        d = eps * (1.0 if c[j] > 0 else -1.0 if c[j] < 0 else 0.0)
        beta[j] += d
        c -= d * G[:, j]
        out[t + 1] = beta
    return out


def arc_length(B):
    """Cumulative L1 arc length (16.16) along the rows of B."""
    return np.r_[0.0, np.cumsum(np.abs(np.diff(B, axis=0)).sum(1))]


def path_at(B, t, x):
    """Linear interpolation of the rows of B (knots at increasing x) at the points t."""
    B = np.asarray(B)
    return np.array([np.interp(t, x, B[:, j]) for j in range(B.shape[1])]).T


def soft(z, a):
    return np.sign(z) * np.maximum(np.abs(z) - a, 0.0)


def lasso_cd_gram(G, g, lams, tol=1e-12, max_sweeps=200000, beta0=None):
    """Pathwise coordinate descent for min_b 1/2 b^T G b - g^T b + lam ||b||_1 at each lam (in the
    given, decreasing order, with warm starts). With G = X^T X / N and g = X^T y / N for centred
    data this is the lasso (1/2N) ||y - X b||^2 + lam ||b||_1. Each lam: sweeps over the active set
    until no coefficient moves by more than tol (in the scale sqrt(G_jj)), then a check of the
    optimality conditions over all coordinates; violators join the active set. Returns the
    coefficients (rows) and the number of sweeps used."""
    M = len(g)
    d = np.diag(G).copy()
    beta = np.zeros(M) if beta0 is None else beta0.astype(float).copy()
    q = G @ beta
    out = np.empty((len(lams), M))
    sweeps = 0
    for k, lam in enumerate(lams):
        active = list(np.flatnonzero(beta))
        while True:
            for _ in range(max_sweeps):
                sweeps += 1
                dmax = 0.0
                for j in active:
                    bj = beta[j]
                    z = g[j] - q[j] + d[j] * bj
                    nb = (z - lam if z > lam else z + lam if z < -lam else 0.0) / d[j]
                    if nb != bj:
                        q += (nb - bj) * G[:, j]
                        beta[j] = nb
                        dmax = max(dmax, abs(nb - bj) * math.sqrt(d[j]))
                if dmax < tol:
                    break
            z = g - q + d * beta
            viol = np.flatnonzero((beta == 0) & (np.abs(z) > lam * (1 + 1e-12)) & (d > 0))
            if len(viol) == 0:
                break
            active = sorted(set(active) | set(viol.tolist()))
        out[k] = beta
    return out, sweeps


def lam_grid(lmax, n=100, ratio=1e-3):
    """n log-spaced penalties from lmax down to ratio * lmax."""
    return lmax * np.exp(np.linspace(0.0, math.log(ratio), n))


# =========================================================================== Section 16.2.2: bet on sparsity
def bos_draw(rng, N=50, p=300, k=300):
    """One draw for Figure 16.2: X with independent N(0, 1) entries and beta with k nonzero N(0, 1)
    coefficients (the first k; with independent inputs the positions do not matter)."""
    X = rng.normal(size=(N, p))
    beta = np.zeros(p)
    beta[:k] = rng.normal(size=k)
    return X, beta


def logistic_nsr(v, scale="probability", grid=None):
    """Noise-to-signal ratio of a Bernoulli response with logit eta ~ N(0, v) (a Riemann sum on
    3601 points over [-9, 9] standard deviations, or the given grid; Gauss-Hermite rules are not
    accurate here, because sigma(eta) is nearly a step when v is large). The noise is the average conditional variance E[p(1 - p)], p = sigma(eta).
    scale='probability': the signal is Var(p) = Var E(Y | X), the analogue of Var(eta) in regression
    (this is the reading that reproduces Figure 16.2); scale='logit': the signal is Var(eta) = v."""
    z, w = (_ZG, _WZ) if grid is None else grid
    pr = 0.5 * (1.0 + np.tanh(0.5 * math.sqrt(v) * z))
    noise = float((w * pr * (1 - pr)).sum())
    signal = float((w * pr * pr).sum()) - 0.25 if scale == "probability" else v
    return noise / signal


def bos_scale(beta, nsr, kind="regression", scale="probability", grid=None):
    """The factor s that gives eta = s x^T beta the noise-to-signal ratio nsr, for N(0, 1) noise
    (regression: NSR = 1 / (s^2 ||beta||^2)) or a Bernoulli response with logit eta (classification:
    logistic_nsr(v) = nsr with v = s^2 ||beta||^2, solved by bisection in log v; the ratio
    decreases in v)."""
    b2 = float(beta @ beta)
    if kind == "regression":
        return 1.0 / math.sqrt(nsr * b2)
    lo, hi = -20.0, 20.0
    for _ in range(200):
        mid = 0.5 * (lo + hi)
        if logistic_nsr(math.exp(mid), scale, grid) > nsr:
            lo = mid
        else:
            hi = mid
    return math.sqrt(math.exp(0.5 * (lo + hi)) / b2)


def pe_regression(b0, bhat, btrue, sigma2=1.0):
    """Exact expected squared prediction error of b0 + x^T bhat for Y = x^T btrue + eps, x ~ N(0, I),
    Var(eps) = sigma2: sigma2 + b0^2 + ||bhat - btrue||^2."""
    return sigma2 + b0 ** 2 + float(((bhat - btrue) ** 2).sum())


def _zgrid(lim, n):
    z = np.linspace(-lim, lim, n)
    return z, np.exp(-0.5 * z ** 2) / math.sqrt(2 * math.pi) * (z[1] - z[0])


_ZG, _WZ = _zgrid(9.0, 3601)
DEMO_GRID = _zgrid(8.0, 801)          # the coarser rule of bet-on-sparsity-demo.html


def _pnorm(x):
    from scipy.special import ndtr
    return ndtr(x)


def err_classification(b0, bhat, btrue, thresh=0.5, grid=None):
    """Exact misclassification rate of the rule 'Y = 1 iff b0 + x^T bhat > thresh' when x ~ N(0, I)
    and Pr(Y = 1 | x) = sigma(x^T btrue): with eta = x^T btrue ~ N(0, v1) and x^T bhat | eta normal,
    the error is a one-dimensional integral over eta (a Riemann sum on [-9, 9] standard deviations,
    3601 points, or the given grid)."""
    ZG, WZ = (_ZG, _WZ) if grid is None else grid
    v1 = float(btrue @ btrue)
    v2 = float(bhat @ bhat)
    c12 = float(btrue @ bhat)
    s1 = math.sqrt(v1)
    eta = s1 * ZG
    mu = b0 + (c12 / v1) * eta
    sd = math.sqrt(max(v2 - c12 ** 2 / v1, 0.0))
    if sd < 1e-14:
        q = (mu > thresh).astype(float)
    else:
        q = _pnorm((mu - thresh) / sd)
    pr = 0.5 * (1.0 + np.tanh(0.5 * eta))
    return float((WZ * (pr * (1 - q) + (1 - pr) * q)).sum())


def best_lasso(X, y, btrue, kind="regression", nsub=20, grid=None):
    """The smallest test error along the entire lasso path of (X, y) (centred internally, intercept
    b0 = ybar - xbar^T b). Regression: the error is a quadratic function along each linear segment of
    the path, minimised exactly. Classification: nsub points per segment."""
    xm, ym = X.mean(0), y.mean()
    Xc, yc = X - xm, y - ym
    P = lars_gram(Xc.T @ Xc, Xc.T @ yc, "lasso", maxrank=min(X.shape[0] - 1, X.shape[1]))
    B = P["beta"]
    best = np.inf
    for k in range(len(B) - 1):
        b1, b2 = B[k], B[k + 1]
        if kind == "regression":
            # e(t) = 1 + (ym - xm^T b(t))^2 + ||b(t) - btrue||^2, b(t) = b1 + t (b2 - b1)
            d = b2 - b1
            u0, u1 = ym - xm @ b1, -(xm @ d)
            r0 = b1 - btrue
            qa = u1 ** 2 + d @ d
            qb = 2 * (u0 * u1 + r0 @ d)
            ts = [0.0, 1.0]
            if qa > 0:
                ts.append(min(1.0, max(0.0, -qb / (2 * qa))))
            for t in ts:
                b = b1 + t * d
                best = min(best, pe_regression(ym - xm @ b, b, btrue))
        else:
            for t in np.linspace(0, 1, nsub + 1)[:-1] if k < len(B) - 2 else np.linspace(0, 1, nsub + 1):
                b = b1 + t * (b2 - b1)
                best = min(best, err_classification(ym - xm @ b, b, btrue, grid=grid))
    return best, P


def best_ridge(X, y, btrue, kind="regression", nlam=200, grid=None):
    """The smallest test error of ridge regression over 200 log-spaced penalties (df from about 1
    to the maximum) and the least-squares limit lambda -> 0 (the minimum-norm interpolant)."""
    xm, ym = X.mean(0), y.mean()
    Xc, yc = X - xm, y - ym
    U, dsv, Vt = np.linalg.svd(Xc, full_matrices=False)
    keep = dsv ** 2 > 1e-10 * dsv[0] ** 2      # drops the null direction created by centring
    U, dsv, Vt = U[:, keep], dsv[keep], Vt[keep]
    uy = U.T @ yc
    lams = np.r_[np.exp(np.linspace(math.log(1e4 * dsv[0] ** 2), math.log(1e-4 * dsv[-1] ** 2), nlam)), 0.0]
    best = np.inf
    for lam in lams:
        b = Vt.T @ (dsv / (dsv ** 2 + lam) * uy)
        b0 = ym - xm @ b
        e = pe_regression(b0, b, btrue) if kind == "regression" else err_classification(b0, b, btrue, grid=grid)
        best = min(best, e)
    return best


def bos_one(rng, k, nsr, kind, N=50, p=300):
    """One realisation of Figure 16.2: returns (lasso, ridge) percentages of error explained."""
    X, beta = bos_draw(rng, N, p, k)
    s = bos_scale(beta, nsr, kind)
    bt = s * beta
    eta = X @ bt
    if kind == "regression":
        y = eta + rng.normal(size=N)
        base = 1.0 + bt @ bt
    else:
        y = (rng.random(N) < 0.5 * (1.0 + np.tanh(0.5 * eta))).astype(float)
        base = 0.5
    el, _ = best_lasso(X, y, bt, kind)
    er = best_ridge(X, y, bt, kind)
    return 1 - el / base, 1 - er / base


BOS_SCEN = (("Gaussian", 300), ("Subset 10", 10), ("Subset 30", 30))
BOS_NSR = (0.1, 0.2, 0.3, 0.4, 0.5)


def bos_simulation(nrep=20):
    """All of Figure 16.2: dict[(kind, scenario, nsr)] = array (nrep, 2) of (lasso, ridge)."""
    def build():
        rng = np.random.default_rng(1602)
        out = {}
        for kind in ("regression", "classification"):
            for name, k in BOS_SCEN:
                for nsr in BOS_NSR:
                    out[(kind, name, nsr)] = np.array([bos_one(rng, k, nsr, kind) for _ in range(nrep)])
        return out
    return _cache("bos", build)


# =========================================================================== Section 16.2.3: block data
def block_cov(p, block, rho):
    """Population covariance: unit variances, correlation rho within consecutive blocks."""
    S = np.zeros((p, p))
    for s in range(0, p, block):
        S[s:s + block, s:s + block] = rho
    np.fill_diagonal(S, 1.0)
    return S


def block_data(N=60, p=1000, block=20, rho=0.95, nsr=0.72, seed=163):
    """The simulation of Section 16.2.3 (Exercise 16.1). Each observation has, for each block b, a
    shared factor Z_b ~ N(0, 1), and X_j = sqrt(rho) Z_b + sqrt(1 - rho) E_j with independent
    E_j ~ N(0, 1): unit variances, correlation rho inside a block, 0 across blocks. One variable per
    block (at a random position) gets a N(0, 1) coefficient; Y = X^T beta + sigma eps with
    sigma^2 = nsr * beta^T Sigma beta."""
    rng = np.random.default_rng(seed)
    nb = p // block
    Z = rng.normal(size=(N, nb))
    X = math.sqrt(rho) * np.repeat(Z, block, axis=1) + math.sqrt(1 - rho) * rng.normal(size=(N, p))
    beta = np.zeros(p)
    pos = np.arange(nb) * block + rng.integers(0, block, nb)
    beta[pos] = rng.normal(size=nb)
    Sigma = block_cov(p, block, rho)
    sig2 = nsr * float(beta @ Sigma @ beta)
    y = X @ beta + math.sqrt(sig2) * rng.normal(size=N)
    return dict(X=X, y=y, beta=beta, Sigma=Sigma, sigma2=sig2, block=block, rho=rho)


def standardise(X, y):
    """Centre X and y and scale the columns of X to unit (1/N) variance; returns Xs, yc, xm, xs, ym."""
    xm, ym = X.mean(0), y.mean()
    xs = X.std(0)
    return (X - xm) / xs, y - ym, xm, xs, ym


def mse_true(Bstd, xm, xs, ym, beta, Sigma):
    """Exact E(f_hat(X) - f(X))^2 for each row of Bstd (coefficients of standardised inputs), with
    X ~ N(0, Sigma), f(x) = x^T beta, f_hat(x) = b0 + x^T b, b = Bstd / xs, b0 = ym - xm^T b."""
    Braw = Bstd / xs
    b0 = ym - Braw @ xm
    D = Braw - beta
    return b0 ** 2 + np.einsum("ij,jk,ik->i", D, Sigma, D)


# =========================================================================== Section 16.3: ISLE
def _sigmoid(f):
    return 0.5 * (1.0 + np.tanh(0.5 * f))


def isle_generate(X, y, M, eta=1.0, nu=0.1, J=6, loss="ls", mtry=None, replace=False, seed=0,
                  Xtest=None, max_depth=None, tree_sizes=None, store=True, store_test=None, keep_trees=False,
                  callback=None):
    """Algorithm 16.2 (ISLE ensemble generation) with CART regression trees as the basis functions.

    f_0 is the best constant; at step m a subsample S_m of round(eta N) observations (without
    replacement unless replace=True) is drawn, a tree with J terminal nodes is fitted by least squares
    to the negative gradient of the loss on S_m, its leaf values are the loss-minimising (Newton)
    updates on S_m, and f_m = f_{m-1} + nu b(x; gamma_m). loss: 'ls' (squared error), 'bernoulli'
    (binomial deviance, y in {0, 1}), 'exponential' (AdaBoost's loss, y in {-1, 1}).
    nu = 0 with replace=True is bagging; eta = 1 is gradient boosting; mtry < p picks the split
    variable among mtry random inputs at every node, as random forests do.

    Returns f0, the unshrunken trees' outputs on the training (Btr, N x M) and test inputs (Bte), the
    largest absolute leaf value of each tree, and the final F. callback(m, F, Ft) is called after
    every tree."""
    from sklearn.tree import DecisionTreeRegressor
    rng = np.random.default_rng(seed)
    N = len(y)
    n = N if eta >= 1 and not replace else max(2, int(math.floor(eta * N + 0.5)))
    if loss == "ls":
        f0 = float(y.mean())
    elif loss == "bernoulli":
        pb = float(y.mean())
        f0 = math.log(pb / (1 - pb))
    else:
        f0 = 0.5 * math.log((y > 0).sum() / (y < 0).sum())
    F = np.full(N, f0)
    Ft = np.full(len(Xtest), f0) if Xtest is not None else None
    Btr = np.empty((N, M)) if store else None
    store_test = store if store_test is None else store_test
    Bte = np.empty((len(Xtest), M)) if (store_test and Xtest is not None) else None
    gmax = np.empty(M)
    trees = []
    for m in range(M):
        if n == N and not replace:
            idx = np.arange(N)
        else:
            idx = np.sort(rng.choice(N, n, replace=replace))
        if loss == "ls":
            r = y - F
        elif loss == "bernoulli":
            pr = _sigmoid(F)
            r = y - pr
        else:
            w = np.exp(-y * F)
            r = y * w
        Jm = J if tree_sizes is None else int(tree_sizes[m])
        tr = DecisionTreeRegressor(max_leaf_nodes=Jm, max_features=mtry, max_depth=max_depth,
                                   random_state=int(rng.integers(2 ** 31 - 1))).fit(X[idx], r[idx])
        leaf = tr.apply(X)
        if loss == "ls":
            gam = tr.tree_.value[:, 0, 0].copy()
        else:
            li = leaf[idx]
            K = tr.tree_.node_count
            num = np.bincount(li, weights=r[idx], minlength=K)
            den = np.bincount(li, weights=(pr * (1 - pr))[idx] if loss == "bernoulli" else w[idx], minlength=K)
            gam = np.where(den > 0, num / np.where(den > 0, den, 1.0), 0.0)
        b = gam[leaf]
        F += nu * b
        is_leaf = tr.tree_.children_left == -1
        gmax[m] = np.abs(gam[is_leaf]).max()
        if store:
            Btr[:, m] = b
        if Xtest is not None:
            bt = gam[tr.apply(Xtest)]
            Ft += nu * bt
            if store_test:
                Bte[:, m] = bt
        if keep_trees:
            trees.append((tr, gam))
        if callback is not None:
            callback(m, F, Ft)
    return dict(f0=f0, Btr=Btr, Bte=Bte, gmax=gmax, F=F, Ft=Ft, trees=trees, n=n)


def post_process(Btr, ytr, Bte=None, nlam=100, ratio=1e-3, tol=1e-9, lams=None, solver="own"):
    """The lasso path (16.9) with squared-error loss on the dictionary of the trees' outputs (the
    columns of Btr, unstandardised) plus an intercept. Returns the penalties, coefficients, intercepts,
    number of nonzero coefficients and the test predictions (one row per penalty).
    solver='own' uses lasso_cd_gram; solver='sklearn' uses scikit-learn's compiled coordinate descent
    on the same Gram matrix (same solutions, much faster for thousands of highly correlated trees;
    used for the spam and simulation figures)."""
    N = len(ytr)
    bm, ym = Btr.mean(0), float(ytr.mean())
    Bc = Btr - bm
    G = Bc.T @ Bc / N
    g = Bc.T @ (ytr - ym) / N
    if lams is None:
        lams = lam_grid(float(np.abs(g).max()), nlam, ratio)
    if solver == "own":
        coefs, sweeps = lasso_cd_gram(G, g, lams, tol)
    else:
        from sklearn.linear_model import lasso_path
        _, C, _ = lasso_path(Bc, ytr - ym, alphas=lams, precompute=Bc.T @ Bc, Xy=Bc.T @ (ytr - ym), tol=1e-6, max_iter=20000)
        coefs, sweeps = C.T, None
    b0 = ym - coefs @ bm
    out = dict(lams=lams, coefs=coefs, b0=b0, nnz=(coefs != 0).sum(1), sweeps=sweeps)
    if Bte is not None:
        out["Fte"] = b0[:, None] + coefs @ Bte.T
    return out


# =========================================================================== Section 16.3.2: rules
def rule_matrix(trees, X):
    """The 0/1 rules (16.14) of a list of fitted trees: every node except the root defines the rule
    'x reaches this node', the product of the indicators along the path from the root. Returns the
    N x K matrix (the decision_path columns without the roots)."""
    cols = []
    for tr, _ in trees:
        P = tr.decision_path(X).toarray()
        cols.append(P[:, 1:])
    return np.hstack(cols).astype(float)


def clean_rules(R):
    """Drop rules that are constant on the training data and exact duplicates; returns the kept
    column indices."""
    s = R.mean(0)
    keep = np.flatnonzero((s > 0) & (s < 1))
    _, first = np.unique(R[:, keep].T, axis=0, return_index=True)
    return keep[np.sort(first)]


def winsorised_linear(Xtr, X, q=0.025):
    """Linear terms of RuleFit (Friedman and Popescu 2008): each input winsorised at its q and 1-q
    training quantiles and scaled to standard deviation 0.4 (the typical scale of a rule)."""
    lo, hi = np.quantile(Xtr, q, axis=0), np.quantile(Xtr, 1 - q, axis=0)
    Wtr = np.clip(Xtr, lo, hi)
    sd = Wtr.std(0)
    return np.clip(X, lo, hi) * (0.4 / sd)


def friedman_1613(X):
    """The regression function (16.13)."""
    return 10.0 * np.exp(-2.0 * X[:, :5] ** 2).prod(1) + X[:, 5:35].sum(1)


def sim_1613(N, seed, sigma=1.3, p=100):
    rng = np.random.default_rng(seed)
    X = rng.random((N, p))
    f = friedman_1613(X)
    return X, f, f + sigma * rng.normal(size=N)


def rulefit_tree_sizes(M, rng, mean_leaves=4):
    """Tree sizes of RuleFit: 2 + floor(an exponential draw with mean mean_leaves - 2) terminal nodes."""
    return 2 + np.floor(rng.exponential(mean_leaves - 2, M)).astype(int)


def rulefit(Xtr, ytr, Xte, seed, nrules=2000, nfold=5, nlam=30, ratio=1e-2):
    """Rule ensembles (Section 16.3.2): an ISLE tree ensemble (eta = min(1/2, (100 + 6 sqrt(N))/N),
    nu = 0.01, random tree sizes with mean about 3.5 terminal nodes) is turned into its rules; the lasso
    (squared error) then post-processes either the rules alone or the rules plus the winsorised
    linear terms, with lambda chosen by nfold-fold cross-validation over nlam penalties from the
    largest useful one down to ratio times it. The lasso paths here use scikit-learn's coordinate
    descent (with the Gram matrix), which our lasso_cd_gram reproduces. Returns, for 'rules' and
    'rules+linear', the test predictions and a summary."""
    from sklearn.linear_model import lasso_path
    rng = np.random.default_rng(seed)
    N = len(ytr)
    eta = min(0.5, (100 + 6 * math.sqrt(N)) / N)
    sizes = rulefit_tree_sizes(4 * nrules, rng)
    M = int(np.searchsorted(np.cumsum(2 * (sizes - 1)), nrules)) + 1
    E = isle_generate(Xtr, ytr, M, eta=eta, nu=0.01, loss="ls", seed=int(rng.integers(2 ** 31 - 1)),
                      tree_sizes=sizes[:M], store=False, keep_trees=True)
    Rtr = rule_matrix(E["trees"], Xtr)
    keep = clean_rules(Rtr)
    Rtr = Rtr[:, keep]
    Rte = rule_matrix(E["trees"], Xte)[:, keep]
    folds = np.array_split(rng.permutation(N), nfold)

    def path(A, yy, lams=None):
        am, ym = A.mean(0), yy.mean()
        Ac = A - am
        Xy = Ac.T @ (yy - ym)
        if lams is None:
            lams = lam_grid(float(np.abs(Xy).max()) / len(yy), nlam, ratio)
        _, C, _ = lasso_path(Ac, yy - ym, alphas=lams, precompute=Ac.T @ Ac, Xy=Xy, tol=1e-4, max_iter=5000)
        C = C.T
        return lams, C, ym - C @ am

    out = {}
    for name, (Atr, Ate) in (("rules", (Rtr, Rte)),
                             ("rules+linear", (np.hstack([Rtr, winsorised_linear(Xtr, Xtr)]),
                                               np.hstack([Rte, winsorised_linear(Xtr, Xte)])))):
        lams, C, b0 = path(Atr, ytr)
        cv = np.zeros(len(lams))
        for f in folds:
            trn = np.setdiff1d(np.arange(N), f)
            _, Cf, b0f = path(Atr[trn], ytr[trn], lams)
            cv += ((ytr[f][None, :] - b0f[:, None] - Cf @ Atr[f].T) ** 2).sum(1)
        k = int(np.argmin(cv))
        out[name] = (b0[k] + Ate @ C[k], dict(M=M, nterms=Atr.shape[1], lam=lams[k], k=k, nnz=int((C[k] != 0).sum())))
    return out


# =========================================================================== Section 16.2.3: margins
def l1_margin(y, F, gmax, nu):
    """The normalised L1 margin (16.7) after each tree: min_i y_i f_m(x_i) / sum_k |alpha_k|, where
    each shrunken tree nu*T_m is a dictionary element scaled to sup norm 1, so that
    sum_k |alpha_k| = nu * sum_{l <= m} max_j |gamma_jl|. F: (M, N) staged fits."""
    return (y[None, :] * F).min(1) / (nu * np.cumsum(gmax))


def lp_max_margin(Btr, y):
    """The largest L1 margin attainable by any combination of the given trees (each scaled to sup
    norm 1): maximise m subject to y_i sum_k alpha_k T_k(x_i) >= m, sum_k |alpha_k| <= 1 (a linear
    programme with alpha = alpha+ - alpha-)."""
    from scipy.optimize import linprog
    T = Btr / np.abs(Btr).max(0)
    N, K = T.shape
    YT = y[:, None] * T
    # variables: alpha+ (K), alpha- (K), m
    c = np.r_[np.zeros(2 * K), -1.0]
    A = np.hstack([-YT, YT, np.ones((N, 1))])
    A = np.vstack([A, np.r_[np.ones(2 * K), 0.0][None, :]])
    b = np.r_[np.zeros(N), 1.0]
    res = linprog(c, A_ub=A, b_ub=b, bounds=[(0, None)] * (2 * K) + [(None, None)], method="highs")
    return -res.fun


# =========================================================================== demos: the browser's data
def demo_block_data(seed, rho, N=60, p=200, block=20, nsr=0.72):
    """Data of stagewise-lasso-demo.html, drawn with DK.rng(seed): for each row, for each block, one
    shared normal then the block's 20 inputs sqrt(rho) Z + sqrt(1 - rho) E; then for each block a
    position (floor(u * 20)) and a N(0, 1) coefficient; then the noise. Same as block_data otherwise."""
    g = JSRandom(seed)
    nb = p // block
    X = np.empty((N, p))
    a, b = math.sqrt(rho), math.sqrt(1 - rho)
    for i in range(N):
        for k in range(nb):
            z = g.norm()
            for j in range(block):
                X[i, k * block + j] = a * z + b * g.norm()
    beta = np.zeros(p)
    for k in range(nb):
        pos = int(math.floor(g.u() * block))
        beta[k * block + pos] = g.norm()
    Sigma = block_cov(p, block, rho)
    sig2 = nsr * float(beta @ Sigma @ beta)
    eps = np.array([g.norm() for _ in range(N)])
    y = X @ beta + math.sqrt(sig2) * eps
    return dict(X=X, y=y, beta=beta, Sigma=Sigma, sigma2=sig2)


def demo_bos_data(seed, k, nsr, kind, N=50, p=300):
    """One realisation of bet-on-sparsity-demo.html, drawn with DK.rng(seed): X row by row, then the
    k nonzero coefficients, then N noise normals (regression) or N uniforms (classification)."""
    g = JSRandom(seed)
    X = np.array([[g.norm() for _ in range(p)] for _ in range(N)])
    beta = np.zeros(p)
    beta[:k] = [g.norm() for _ in range(k)]
    bt = bos_scale(beta, nsr, kind, grid=DEMO_GRID) * beta
    eta = X @ bt
    if kind == "regression":
        y = eta + np.array([g.norm() for _ in range(N)])
    else:
        u = np.array([g.u() for _ in range(N)])
        y = (u < _sigmoid(eta)).astype(float)
    return X, y, bt


def demo_bos_seed(base, k, r):
    """The DK.rng seed of realisation r (0-based) with k nonzero coefficients in the demo."""
    return 100000 * base + 1000 * k + r


def demo_bos_one(base, k, r, nsr, kind):
    """(lasso, ridge) percentages of error explained for one realisation of bet-on-sparsity-demo.html
    (classification: the 801-point integration rule and 10 points per lasso segment, as the page)."""
    X, y, bt = demo_bos_data(demo_bos_seed(base, k, r), k, nsr, kind)
    if kind == "regression":
        base_err = 1.0 + bt @ bt
        el, _ = best_lasso(X, y, bt, "regression")
        er = best_ridge(X, y, bt, "regression")
    else:
        base_err = 0.5
        el, _ = best_lasso(X, y, bt, "classification", nsub=10, grid=DEMO_GRID)
        er = best_ridge(X, y, bt, "classification", grid=DEMO_GRID)
    return 1 - el / base_err, 1 - er / base_err


def demo_isle_data(seed, N=500, Nt=500, p=100, sigma=1.3):
    """Data of isle-postprocessing-demo.html, drawn with DK.rng(seed): the training inputs row by row
    (uniforms), the test inputs, then the training noise; the model is (16.13)."""
    U = ch10.js_uniforms(seed, (N + Nt) * p)
    Xtr = U[:N * p].reshape(N, p)
    Xte = U[N * p:].reshape(Nt, p)
    eps = ch10.js_normals(seed, N, start=(N + Nt) * p)
    ftr, fte = friedman_1613(Xtr), friedman_1613(Xte)
    return dict(Xtr=Xtr, ytr=ftr + sigma * eps, ftr=ftr, Xte=Xte, fte=fte)


def _partial_shuffle(g, n, k):
    """The first k entries of a partial Fisher-Yates shuffle of 0..n-1 with JSRandom g, sorted."""
    a = list(range(n))
    for i in range(k):
        j = i + int(math.floor(g.u() * (n - i)))
        a[i], a[j] = a[j], a[i]
    return sorted(a[:k])


class DemoTree:
    """The least-squares regression tree of the ISLE demonstration: grown best-first to J terminal
    nodes (the leaf whose best split most reduces the squared error is split next), at least
    min_leaf observations per leaf, thresholds at midpoints, split variables among mtry inputs drawn
    at random when a node is created (all p when mtry = p). Ties go to the earlier position, to the
    earlier input (unless a later one is better by a relative 1e-10) and to the earlier leaf, exactly
    as in the page's JavaScript."""

    def __init__(self, X, order, r, rows, J, mtry, g, min_leaf=5):
        N, p = X.shape
        self.feat, self.thr, self.left, self.right, self.value = [], [], [], [], []
        inode = np.full(N, -1)
        inode[rows] = 0
        self._new_node()
        leaves = [0]
        best = {0: self._best(X, order, r, inode, 0, mtry, g, min_leaf)}
        while len(leaves) < J:
            k, bd = -1, 0.0
            for i, nd in enumerate(leaves):
                if best[nd] is not None and best[nd][0] > bd:
                    k, bd = i, best[nd][0]
            if k < 0:
                break
            nd = leaves.pop(k)
            _, j, t = best[nd]
            L, R = self._new_node(), self._new_node()
            self.feat[nd], self.thr[nd], self.left[nd], self.right[nd] = j, t, L, R
            mem = inode == nd
            inode[mem & (X[:, j] < t)] = L
            inode[mem & (X[:, j] >= t)] = R
            leaves += [L, R]
            best[L] = self._best(X, order, r, inode, L, mtry, g, min_leaf)
            best[R] = self._best(X, order, r, inode, R, mtry, g, min_leaf)
        for nd in leaves:
            idx = np.flatnonzero(inode == nd)
            s = 0.0
            for i in idx:
                s += r[i]
            self.value[nd] = s / len(idx)

    def _new_node(self):
        for a, v in ((self.feat, -1), (self.thr, 0.0), (self.left, -1), (self.right, -1), (self.value, 0.0)):
            a.append(v)
        return len(self.feat) - 1

    @staticmethod
    def _best(X, order, r, inode, nd, mtry, g, min_leaf):
        p = X.shape[1]
        feats = list(range(p)) if mtry >= p else _partial_shuffle(g, p, mtry)
        n = int((inode == nd).sum())
        if n < 2 * min_leaf:
            return None
        best = None
        for j in feats:
            o = order[j]
            o = o[inode[o] == nd]
            cs = np.cumsum(r[o])
            S = cs[-1]                                       # the node total, summed in this input's order
            nl = np.arange(1, n + 1, dtype=float)
            k = np.arange(min_leaf - 1, n - min_leaf)        # split after position k (0-based)
            if len(k) == 0:
                return None
            SL = cs[k]
            SR = S - SL
            dl = (SL * SL) / nl[k] + (SR * SR) / (n - nl[k]) - (S * S) / n
            i = int(np.argmax(dl))
            # a later input must beat the best so far by a relative 1e-10: two inputs that induce the same
            # partition of a small node tie exactly, and rounding must not decide between them
            if best is None or dl[i] > best[0] + 1e-10 * abs(best[0]):
                xs = X[o, j]
                best = (float(dl[i]), j, 0.5 * (xs[k[i]] + xs[k[i] + 1]))
        return best

    def predict(self, X):
        out = np.empty(len(X))
        for i, x in enumerate(X):
            nd = 0
            while self.feat[nd] >= 0:
                nd = self.left[nd] if x[self.feat[nd]] < self.thr[nd] else self.right[nd]
            out[i] = self.value[nd]
        return out


def isle_demo(D, M, eta, nu, J, mtry, seed):
    """Algorithm 16.2 exactly as isle-postprocessing-demo.html runs it (squared error; the subsample
    and the split-variable draws come from DK.rng(seed)). Returns the trees' outputs and the
    generator's own test MSE after each tree (f_m for nu > 0; f_0 plus the average of the trees, as
    in bagging, for nu = 0)."""
    Xtr, ytr, Xte, fte = D["Xtr"], D["ytr"], D["Xte"], D["fte"]
    N, p = Xtr.shape
    g = JSRandom(seed)
    order = [np.argsort(Xtr[:, j], kind="stable") for j in range(p)]
    s = 0.0
    for v in ytr:
        s += v
    f0 = s / N
    F = np.full(N, f0)
    Ft = np.full(len(Xte), f0)
    n = N if eta >= 1 else int(math.floor(eta * N + 0.5))
    Btr, Bte, mse = np.empty((N, M)), np.empty((len(Xte), M)), np.empty(M)
    for m in range(M):
        rows = list(range(N)) if n == N else _partial_shuffle(g, N, n)
        tr = DemoTree(Xtr, order, ytr - F, rows, J, mtry, g)
        b, bt = tr.predict(Xtr), tr.predict(Xte)
        Btr[:, m], Bte[:, m] = b, bt
        if nu > 0:
            F = F + nu * b
            Ft = Ft + nu * bt
            pred = Ft
        else:
            pred = f0 + Bte[:, :m + 1].mean(1)
        mse[m] = float(((pred - fte) ** 2).mean())
    return dict(f0=f0, Btr=Btr, Bte=Bte, mse=mse)


# =========================================================================== figures
def prostate_paths(eps=0.01, nsteps=250):
    """Lasso knots and forward-stagewise steps on the prostate training data (Figure 16.1)."""
    import ch03_linear_regression as ch03
    D = ch03.load_prostate()
    Xc, yc, _, _ = ch03.centred(D["Xtr"], D["ytr"])
    G, b = Xc.T @ Xc, Xc.T @ yc
    P = lars_gram(G, b, "lasso", maxrank=8)
    B = fs_eps_gram(G, b, eps, nsteps)
    return P, B, Xc, yc


def _label_ends(ax, x, vals, names, colors, dx, gap):
    order = np.argsort(vals)
    ys = np.array(vals, float)[order]
    for k in range(1, len(ys)):
        ys[k] = max(ys[k], ys[k - 1] + gap)
    for k, j in enumerate(order):
        ax.text(x + dx, ys[k], names[j], fontsize=7.5, color=colors[j], va="center")


def fig_16_1(out_dir=None):
    """Lasso and forward stagewise (eps = 0.01) coefficient profiles on the prostate data."""
    import matplotlib.pyplot as plt
    P, B, _, _ = prostate_paths()
    t = np.abs(P["beta"]).sum(1)
    fig, axes = plt.subplots(1, 2, figsize=(8.6, 3.9), sharey=True)
    for j in range(8):
        axes[0].plot(t, P["beta"][:, j], color=PCOL[j], lw=1.3, marker="o", ms=2.5)
        axes[1].plot(np.arange(len(B)), B[:, j], color=PCOL[j], lw=1.2)
    _label_ends(axes[0], t[-1], P["beta"][-1], PNAMES, PCOL, 0.04, 0.035)
    _label_ends(axes[1], len(B) - 1, B[-1], PNAMES, PCOL, 4, 0.035)
    axes[0].set_title("Lasso")
    axes[1].set_title("Forward Stagewise")
    axes[0].set_xlabel(r"$t=\sum_k|\alpha_k|$")
    axes[1].set_xlabel("Iteration")
    axes[0].set_ylabel("Coefficients")
    axes[0].set_xlim(0, t[-1] * 1.22)
    axes[1].set_xlim(0, (len(B) - 1) * 1.2)
    for ax in axes:
        ax.axhline(0, color=GREY, lw=0.6, ls="--")
    fig.tight_layout()
    savefig(fig, CH, "fig16-1", out_dir)
    print("  lasso: %d knots, final t = %.3f; FS after %d steps: L1 = %.3f, max |FS - LS| = %.3f"
          % (len(t), t[-1], len(B) - 1, np.abs(B[-1]).sum(), np.abs(B[-1] - P["beta"][-1]).max()))


def fig_16_2(out_dir=None):
    """The bet-on-sparsity simulation: lasso against ridge, regression and classification."""
    import matplotlib.pyplot as plt
    S = bos_simulation()
    fig, axes = plt.subplots(3, 4, figsize=(9.6, 8.2), sharey=True)
    for c, kind in enumerate(("regression", "classification")):
        col = GREEN if kind == "regression" else MAGENTA
        for r, (name, _) in enumerate(BOS_SCEN):
            for h, meth in enumerate(("Lasso", "Ridge")):
                ax = axes[r, 2 * c + h]
                data = [S[(kind, name, nsr)][:, h] for nsr in BOS_NSR]
                bp = ax.boxplot(data, widths=0.6, patch_artist=True, medianprops=dict(color="k", lw=1.2),
                                flierprops=dict(marker="o", ms=2.5, mfc="none", mec="k", mew=0.6))
                for bx in bp["boxes"]:
                    bx.set(facecolor=col, alpha=0.75, edgecolor="k", lw=0.6)
                ax.set_xticks(range(1, 6))
                ax.set_xticklabels([str(v) for v in BOS_NSR], fontsize=7.5)
                ax.set_ylim(-0.05, 1.0)
                ax.set_title("%s/%s" % (meth, name), fontsize=8.5)
                if r == 2:
                    ax.set_xlabel("Noise-to-signal ratio", fontsize=8.5)
        axes[0, 2 * c].text(1.0, 1.18, kind.capitalize(), transform=axes[0, 2 * c].transAxes, ha="center", fontsize=10.5)
    axes[1, 0].set_ylabel("Percentage of squared prediction error explained")
    axes[1, 2].set_ylabel("Percentage of misclassification error explained")
    axes[1, 2].yaxis.set_tick_params(labelleft=True)
    fig.tight_layout()
    savefig(fig, CH, "fig16-2", out_dir)
    for kind in ("regression", "classification"):
        for name, _ in BOS_SCEN:
            med = np.array([np.median(S[(kind, name, v)], 0) for v in BOS_NSR])
            print("  %-14s %-9s lasso %s ridge %s" % (kind, name, np.round(med[:, 0], 2), np.round(med[:, 1], 2)))


BLOCK_SEED = 1


def block_paths():
    """Lasso and FS0 paths for the block-correlated data of Figures 16.3-16.4 (cached)."""
    def build():
        d = block_data(seed=BLOCK_SEED)
        Xs, yc, xm, xs, ym = standardise(d["X"], d["y"])
        G, b = Xs.T @ Xs, Xs.T @ yc
        L = lars_gram(G, b, "lasso", maxrank=59)
        F = lars_gram(G, b, "fs0", maxrank=59)
        return dict(d=d, xm=xm, xs=xs, ym=ym, lasso=L["beta"], fs0=F["beta"],
                    ev_lasso=L["events"], ev_fs0=F["events"])
    return _cache("block_paths", build)


def fig_16_3(out_dir=None):
    """Coefficient paths of the lasso and of FS0 on the block-correlated simulation."""
    import matplotlib.pyplot as plt
    R = block_paths()
    L, F = R["lasso"], R["fs0"]
    xl = np.abs(L).sum(1)
    xf = arc_length(F)
    cmap = plt.get_cmap("tab20")
    fig, axes = plt.subplots(1, 2, figsize=(8.6, 3.9), sharey=True)
    used = np.flatnonzero((np.abs(L).max(0) > 0) | (np.abs(F).max(0) > 0))
    for k, j in enumerate(used):
        axes[0].plot(xl / xl[-1], L[:, j], color=cmap(k % 20), lw=0.9)
        axes[1].plot(xf / xf[-1], F[:, j], color=cmap(k % 20), lw=0.9)
    axes[0].set_title("Lasso")
    axes[1].set_title("Forward Stagewise (FS$_0$)")
    axes[0].set_xlabel(r"$|\alpha(m)|\,/\,|\alpha(\infty)|$")
    axes[1].set_xlabel(r"arc length $/$ final arc length")
    axes[0].set_ylabel("Standardized coefficients")
    for ax in axes:
        ax.axhline(0, color=GREY, lw=0.6, ls="--")
    fig.tight_layout()
    savefig(fig, CH, "fig16-3", out_dir)
    sl = np.sign(np.diff(L, axis=0))
    rev_l = int(sum(((sl[:, j][sl[:, j] != 0][1:] * sl[:, j][sl[:, j] != 0][:-1]) < 0).sum() for j in range(L.shape[1])))
    sf = np.sign(np.diff(F, axis=0))
    rev_f = int(sum(((sf[:, j][sf[:, j] != 0][1:] * sf[:, j][sf[:, j] != 0][:-1]) < 0).sum() for j in range(F.shape[1])))
    nd = sum(1 for e in R["ev_lasso"] if e[0] == "drop")
    print("  lasso: %d knots (%d drops), %d variables ever active, |alpha(inf)| = %.1f, %d direction reversals"
          % (len(L), nd, int((np.abs(L).max(0) > 0).sum()), xl[-1], rev_l))
    print("  FS0:   %d knots, %d variables ever active, final arc length %.1f (L1 norm %.1f), %d direction reversals"
          % (len(F), int((np.abs(F).max(0) > 0).sum()), xf[-1], np.abs(F[-1]).sum(), rev_f))


def block_mse_curves(n=150):
    """Exact test MSE along the lasso path (against |alpha|) and the FS0 path (against arc length)."""
    R = block_paths()
    d = R["d"]
    L, F = R["lasso"], R["fs0"]
    xl, xf = np.abs(L).sum(1), arc_length(F)
    tl = np.linspace(0, xl[-1], n)
    tf = np.linspace(0, xf[-1], n)
    ml = mse_true(path_at(L, tl, xl), R["xm"], R["xs"], R["ym"], d["beta"], d["Sigma"])
    mf = mse_true(path_at(F, tf, xf), R["xm"], R["xs"], R["ym"], d["beta"], d["Sigma"])
    return tl, ml, tf, mf


def fig_16_4(out_dir=None):
    """Test mean squared error along the lasso and FS0 paths."""
    import matplotlib.pyplot as plt
    tl, ml, tf, mf = block_mse_curves(n=400)
    fig, ax = plt.subplots(figsize=(5.4, 4.0))
    ax.plot(tl, ml, "o", color=ORANGE, ms=2.6, mfc="none", label="Lasso")
    ax.plot(tf, mf, "o", color=CYAN, ms=2.6, mfc="none", label="Forward Stagewise (FS$_0$)")
    ax.set_xlim(0, max(tl[-1], tf[-1]) * 1.03)
    ax.set_xlabel(r"$|\alpha(m)|$ (lasso), arc length (FS$_0$)")
    ax.set_ylabel("Mean squared error")
    ax.legend(frameon=False)
    fig.tight_layout()
    savefig(fig, CH, "fig16-4", out_dir)
    print("  MSE at 0: %.2f; lasso min %.2f at |alpha| = %.1f; FS0 min %.2f at arc length %.1f; at 40: lasso %.2f, FS0 %.2f; ends: lasso %.2f, FS0 %.2f"
          % (ml[0], ml.min(), tl[np.argmin(ml)], mf.min(), tf[np.argmin(mf)], np.interp(40, tl, ml), np.interp(40, tf, mf), ml[-1], mf[-1]))


def mixture_boost(M=10000, nu=0.02, J=4):
    """Boosting with the exponential loss on the mixture data (Figure 16.5); cached."""
    def build():
        import ch02_overview_supervised_learning as ch02
        d = ch02.mixture()
        X, y = d["X"], 2.0 * d["y"] - 1
        Xt, yt = ch02.mixture_test(d["means"])
        yt = 2.0 * yt - 1
        rec = dict(minm=np.empty(M), err=np.empty(M), train=np.empty(M))

        def cb(m, F, Ft):
            rec["minm"][m] = (y * F).min()
            rec["train"][m] = np.mean(y * F <= 0)
            rec["err"][m] = np.mean(yt * Ft <= 0)
        E = isle_generate(X, y, M, eta=1.0, nu=nu, J=J, loss="exponential", seed=165, Xtest=Xt,
                          store=True, store_test=False, callback=cb)
        rec["margin"] = rec["minm"] / (nu * np.cumsum(E["gmax"]))
        rec["gmax"] = E["gmax"]
        rec["Btr"] = E["Btr"]
        rec["y"] = y
        return rec
    return _cache("mixture_boost", build)


def fig_16_5(out_dir=None):
    """L1 margin and test error of boosted 4-node trees (exponential loss) on the mixture data."""
    import matplotlib.pyplot as plt
    R = mixture_boost()
    m = np.arange(1, len(R["margin"]) + 1)
    fig, axes = plt.subplots(1, 2, figsize=(8.6, 3.5))
    axes[0].plot(m, R["margin"], color=CYAN, lw=1.3)
    axes[0].axhline(0, color=ORANGE, lw=0.8, ls="--")
    z = int(np.argmax(R["train"] == 0)) + 1 if np.any(R["train"] == 0) else None
    if z:
        axes[0].axvline(z, color=ORANGE, lw=0.8, ls="--")
    axes[0].set_ylim(-0.3, 0.1)
    axes[0].set_ylabel("Margin")
    axes[1].plot(m, R["err"], color=GREEN, lw=1.0)
    k = int(np.argmin(R["err"])) + 1
    axes[1].axvline(k, color=ORANGE, lw=0.8, ls="--")
    axes[1].set_ylabel("Test error")
    for ax in axes:
        ax.set_xlabel("Number of trees")
        ax.set_xticks([0, 2000, 4000, 6000, 8000, 10000])
        ax.set_xticklabels(["0", "2K", "4K", "6K", "8K", "10K"])
    fig.tight_layout()
    savefig(fig, CH, "fig16-5", out_dir)
    print("  margin after 1, 100, 10000 trees: %.3f %.3f %.4f; margin > 0 from tree %s; training error 0 from tree %s"
          % (R["margin"][0], R["margin"][99], R["margin"][-1], int(np.argmax(R["margin"] > 0)) + 1, z))
    print("  test error: min %.4f at %d trees; after 10000 trees %.4f" % (R["err"].min(), k, R["err"][-1]))


def spam_ensembles():
    """Everything Figures 16.6-16.7 need (cached): test errors of the random forests, of gradient
    boosting and of the lasso post-processed ensembles."""
    def build():
        from sklearn.ensemble import RandomForestClassifier
        Xtr, ytr, Xte, yte = ch10.spam()
        ytr = ytr.astype(float)
        out = {}
        rf = RandomForestClassifier(n_estimators=1000, max_features=7, random_state=166, n_jobs=1).fit(Xtr, ytr)
        out["rf_err"] = float(np.mean((rf.predict_proba(Xte)[:, 1] > 0.5) != yte))
        Btr = np.column_stack([t.predict_proba(Xtr)[:, 1] for t in rf.estimators_[:500]])
        Bte = np.column_stack([t.predict_proba(Xte)[:, 1] for t in rf.estimators_[:500]])
        P = post_process(Btr, ytr, Bte, nlam=100, ratio=1e-3, solver="sklearn")
        out["rf_pp"] = (P["nnz"], np.mean((P["Fte"] > 0.5) != yte[None, :], 1))
        del rf
        E = isle_generate(Xtr, ytr, 1000, eta=0.05, nu=0.0, J=6, loss="ls", mtry=7, seed=1661, Xtest=Xte)
        out["rf5_err"] = float(np.mean((E["f0"] + E["Bte"].mean(1) > 0.5) != yte))
        P = post_process(E["Btr"][:, :500], ytr, E["Bte"][:, :500], nlam=100, ratio=1e-3, solver="sklearn")
        out["rf5_pp"] = (P["nnz"], np.mean((P["Fte"] > 0.5) != yte[None, :], 1))
        errs = []
        isle_generate(Xtr, ytr, 500, eta=1.0, nu=0.1, J=5, loss="bernoulli", seed=1662, Xtest=Xte, store=False,
                      callback=lambda m, F, Ft: errs.append(np.mean((Ft > 0) != yte)))
        out["gb_err"] = np.array(errs)
        errs = []
        E = isle_generate(Xtr, ytr, 2500, eta=0.5, nu=0.05, J=5, loss="bernoulli", seed=1671, Xtest=Xte,
                          callback=lambda m, F, Ft: errs.append(np.mean((Ft > 0) != yte)))
        out["isle_gb_err"] = np.array(errs)
        P = post_process(E["Btr"], ytr, E["Bte"], nlam=100, ratio=1e-3, solver="sklearn")
        out["isle_pp"] = (P["nnz"], np.mean((P["Fte"] > 0.5) != yte[None, :], 1))
        return out
    return _cache("spam", build)


def _best_by_size(nnz, err):
    """For each number of nonzero coefficients reached on the path, the error at the last penalty
    with that many (the jagged curve of the book plots error against this count)."""
    order = np.argsort(nnz, kind="stable")
    return nnz[order], err[order]


def fig_16_6(out_dir=None):
    """Lasso post-processing of random forests on the spam data."""
    import matplotlib.pyplot as plt
    S = spam_ensembles()
    fig, ax = plt.subplots(figsize=(5.6, 4.2))
    ax.axhline(S["rf_err"], color=BLUE, lw=1.2)
    x, e = _best_by_size(*S["rf_pp"])
    ax.plot(x, e, color=BLUE, lw=1.0, label="Random Forest")
    ax.axhline(S["rf5_err"], color=ORANGE, lw=1.2)
    x, e = _best_by_size(*S["rf5_pp"])
    ax.plot(x, e, color=ORANGE, lw=1.0, label="Random Forest (5%, 6)")
    ax.plot(np.arange(1, len(S["gb_err"]) + 1), S["gb_err"], color=GREEN, lw=1.0, label="Gradient Boost (5 node)")
    ax.set_xlim(0, 500)
    ax.set_ylim(0.035, 0.09)
    ax.set_xlabel("Number of trees")
    ax.set_ylabel("Test error")
    ax.set_title("Spam data")
    ax.legend(frameon=False)
    fig.tight_layout()
    savefig(fig, CH, "fig16-6", out_dir)
    for key, lab in (("rf_pp", "RF"), ("rf5_pp", "RF(5%,6)")):
        nz, er = S[key]
        k = int(np.argmin(er))
        print("  %s: forest %.4f; post-processed min %.4f with %d trees" % (lab, S["rf_err" if key == "rf_pp" else "rf5_err"], er[k], nz[k]))
    print("  gradient boosting: %.4f after 500 trees, min %.4f" % (S["gb_err"][-1], S["gb_err"].min()))


def fig_16_7(out_dir=None):
    """ISLE on the spam data: stochastic gradient boosting and its lasso post-processing."""
    import matplotlib.pyplot as plt
    S = spam_ensembles()
    fig, ax = plt.subplots(figsize=(5.6, 4.2))
    ax.plot(np.arange(1, len(S["isle_gb_err"]) + 1), S["isle_gb_err"], color=ORANGE, lw=1.0, label="Gradient Boosting (5 node)")
    x, e = _best_by_size(*S["isle_pp"])
    ax.plot(x, e, color=GREEN, lw=1.0, label="Lasso post-processed")
    ax.set_xlim(0, 2500)
    ax.set_ylim(0.035, 0.065)
    ax.set_xlabel("Number of trees")
    ax.set_ylabel("Test error")
    ax.set_title("Spam data")
    ax.legend(frameon=False)
    fig.tight_layout()
    savefig(fig, CH, "fig16-7", out_dir)
    nz, er = S["isle_pp"]
    k = int(np.argmin(er))
    print("  boosting: %.4f after 2500 trees, min %.4f at %d; post-processed min %.4f with %d trees"
          % (S["isle_gb_err"][-1], S["isle_gb_err"].min(), int(np.argmin(S["isle_gb_err"])) + 1, er[k], nz[k]))


def regression_ensembles():
    """Everything Figure 16.8 needs (cached): the MSE curves of the generators and of the lasso
    post-processed ensembles on the simulation (16.13)."""
    def build():
        from sklearn.ensemble import RandomForestRegressor
        X, f, y = sim_1613(1000, 168)
        Xt, ft, _ = sim_1613(500, 1680)
        out = {}
        for key, eta, seed in (("gbm1", 1.0, 1681), ("gbm01", 0.1, 1682)):
            mse = []
            E = isle_generate(X, y, 2500, eta=eta, nu=0.01, J=6, seed=seed, Xtest=Xt, store=(key == "gbm01"),
                              callback=lambda m, F, Ft: mse.append(np.mean((Ft - ft) ** 2)))
            out[key] = np.array(mse)
            if key == "gbm01":
                P = post_process(E["Btr"], y, E["Bte"], nlam=100, ratio=1e-3, solver="sklearn")
                out["isle_gb"] = (P["nnz"], ((P["Fte"] - ft[None, :]) ** 2).mean(1))
        rf = RandomForestRegressor(n_estimators=1000, max_features=33, random_state=168, n_jobs=1).fit(X, y)
        Btr = np.column_stack([t.predict(X) for t in rf.estimators_])
        Bte = np.column_stack([t.predict(Xt) for t in rf.estimators_])
        out["rf"] = ((np.cumsum(Bte, 1) / np.arange(1, Bte.shape[1] + 1) - ft[:, None]) ** 2).mean(0)
        P = post_process(Btr, y, Bte, nlam=100, ratio=1e-3, solver="sklearn")
        out["isle_rf"] = (P["nnz"], ((P["Fte"] - ft[None, :]) ** 2).mean(1))
        out["var_f"] = float(np.var(friedman_1613(np.random.default_rng(1689).random((200000, 100)))))
        return out
    return _cache("regression", build)


def fig_16_8(out_dir=None):
    """Ensembles on the regression simulation (16.13): boosting, subsampled boosting, random forest
    and their lasso post-processed versions."""
    import matplotlib.pyplot as plt
    R = regression_ensembles()
    fig, ax = plt.subplots(figsize=(5.8, 4.3))
    ax.plot(np.arange(1, 2501), R["gbm1"], color=ORANGE, lw=1.1, label="GBM (1, 0.01)")
    ax.plot(np.arange(1, 2501), R["gbm01"], color=GREEN, lw=1.1, label="GBM (0.1, 0.01)")
    x, e = _best_by_size(*R["isle_gb"])
    ax.plot(x, e, color=PURPLE, lw=1.1, label="ISLE GB")
    x, e = _best_by_size(*R["isle_rf"])
    ax.plot(x, e, color=MAGENTA, lw=1.1, label="ISLE RF")
    ax.plot(np.arange(1, len(R["rf"]) + 1), R["rf"], color=BLUE, lw=1.1, label="Random Forest")
    ax.set_xlim(0, 2500)
    ax.set_ylim(0.8, 3.6)
    ax.set_xlabel("Number of trees")
    ax.set_ylabel("Mean squared error")
    ax.legend(frameon=False)
    fig.tight_layout()
    savefig(fig, CH, "fig16-8", out_dir)
    print("  Var f(X) = %.3f, signal-to-noise Var f / sigma^2 = %.2f" % (R["var_f"], R["var_f"] / 1.69))
    for key in ("gbm1", "gbm01", "rf"):
        print("  %s: min %.3f at %d trees, final %.3f" % (key, R[key].min(), int(np.argmin(R[key])) + 1, R[key][-1]))
    for key in ("isle_gb", "isle_rf"):
        nz, er = R[key]
        k = int(np.argmin(er))
        print("  %s: min %.3f with %d trees" % (key, er[k], nz[k]))


def rulefit_simulation(nrep=20):
    """Figure 16.10 (cached): test MSE of rule ensembles over nrep realisations of (16.13)."""
    def build():
        res = []
        Xt, ft, _ = sim_1613(5000, 16100)
        for r in range(nrep):
            X, f, y = sim_1613(1000, 1610 + r)
            o = rulefit(X, y, Xt, seed=16101 + r)
            row = [float(np.mean((o[key][0] - ft) ** 2)) for key in ("rules", "rules+linear")]
            res.append(row)
            print("    realisation %d: rules %.3f, rules + linear %.3f" % (r + 1, row[0], row[1]), flush=True)
        X, f, y = sim_1613(1000, 168)
        Xt8, ft8, _ = sim_1613(500, 1680)
        o = rulefit(X, y, Xt8, seed=1688)
        return dict(mse=np.array(res), fig168={k: float(np.mean((o[k][0] - ft8) ** 2)) for k in o},
                    info168={k: o[k][1] for k in o})
    return _cache("rulefit", build)


def fig_16_10(out_dir=None):
    """Boxplots of the test MSE of rule ensembles (rules; rules plus linear terms)."""
    import matplotlib.pyplot as plt
    R = rulefit_simulation()
    fig, ax = plt.subplots(figsize=(4.6, 3.8))
    bp = ax.boxplot([R["mse"][:, 0], R["mse"][:, 1]], widths=0.55, patch_artist=True,
                    medianprops=dict(color="k", lw=1.2), flierprops=dict(marker="o", ms=3, mfc="none", mec="k"))
    for bx in bp["boxes"]:
        bx.set(facecolor=GREEN, alpha=0.75, edgecolor="k", lw=0.6)
    ax.set_xticks([1, 2])
    ax.set_xticklabels(["Rules", "Rules + Linear"])
    ax.set_ylabel("Mean squared error")
    fig.tight_layout()
    savefig(fig, CH, "fig16-10", out_dir)
    med = np.median(R["mse"], 0)
    print("  medians: rules %.3f, rules + linear %.3f; ranges %s; Figure 16.8 training set: %s, %s"
          % (med[0], med[1], np.round([R["mse"].min(0), R["mse"].max(0)], 3).tolist(), R["fig168"], R["info168"]))


FIGURES = {"16.1": fig_16_1, "16.2": fig_16_2, "16.3": fig_16_3, "16.4": fig_16_4, "16.5": fig_16_5,
           "16.6": fig_16_6, "16.7": fig_16_7, "16.8": fig_16_8, "16.10": fig_16_10}

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