"""Hastie, Tibshirani and Friedman (2009), Chapter 18: High-Dimensional Problems: p >> N.

Reproduces the figures of Chapter 18 of T. Hastie, R. Tibshirani and J. Friedman, The Elements of
Statistical Learning (2nd edition, Springer, 2009), pp. 649-698, written from scratch with numpy, scipy
and matplotlib. Every method is a small function meant to be read next to the lecture notes
(../ch18-high-dimensional-problems.html):

* Section 18.1: ridge_sim() draws model (18.1); ridge_svd() fits ridge through the SVD of the centred
  inputs (the N x N route), ridge_direct() through the p x p normal equations (18.14), ridge_reduced()
  through X = R V^T (18.15); rel_test_error() is the exact relative test error and bayes_rel_error()
  the Bayes risk (ridge at lambda = sigma^2 is the posterior mean); ridge_study() runs Figure 18.1.
* Section 18.2: NSC is nearest shrunken centroids ((18.2)-(18.8): contrasts d_kj, soft or hard
  thresholding, shrunken centroids, discriminant scores and class probabilities); nsc_cv() is its
  cross-validation; khan() loads the SRBCT data.
* Section 18.3: svd_reduce() is (18.12)-(18.13); multinomial_ridge() fits (18.10)-(18.11) and
  logistic_ridge() its two-class version; RDA is (18.9) computed without p x p matrices; knn_predict()
  and svm_ova_predict() (one-versus-all, from inner products) complete table_18_1() on the 14-cancer
  data, which uses the R package glmnet (through Rscript) for the lasso and elastic-net rows.
* Section 18.4: logistic_enet_path() is penalised logistic regression by coordinate descent on the
  IRLS approximation along a lambda path (the glmnet algorithm); leukemia_paths() runs Figures 18.5-18.6
  on the Golub training data (golub(), exported once from the R package multtest). tv_denoise() solves
  1-D total-variation denoising through its dual (L-BFGS-B plus an exact active-set step), flsa() is the
  fused lasso signal approximator (18.24) as soft-thresholded total variation, flsa_direct() solves it
  directly; cgh_sim() simulates a copy-number profile.
* Section 18.5: protein_sim() simulates protein sequences, spectrum_features() and string_kernel() are
  the m-spectrum kernel (18.25)-(18.26); kernel_sqdist(), kernel_centroid_score() and kernel_nn_score()
  are (18.27), (18.28) and (18.57); double_centre() is (18.31) and kernel_pca_scores() is (18.58).
* Section 18.6: survival_sim() simulates censored survival data from the latent-variable model
  (18.32)-(18.33); kaplan_meier(), logrank(), cox_scores() (the score statistic of every gene) and
  cox_fit() (one-covariate Cox model) are the survival tools; survival_spc() is Algorithm 18.1 with Cox
  scores. spc_sim() draws model (18.37); uni_scores(), spc_predict() and tpls_predict() are supervised
  principal components and thresholded PLS; spc_study() and precondition_example() run Figures
  18.16-18.17 (the lasso path from scikit-learn's lars_path).
* Section 18.7: tstats() is (18.38)-(18.39); radsens_permutations() computes the permutation
  distribution (pooled counts for (18.41), per-gene counts for (18.40), the SAM expected order
  statistics); bh() is Algorithm 18.2, plugin_fdr() Algorithm 18.3, sam_cutpoints() the SAM rule.
* Exercises: max_data_piling() and exercise_18_9_table() (Exercises 18.8-18.9), exercise_18_19().
* Demonstrations: export_khan_json() writes ../data/ch18-khan.json; demo_nsc(), demo_ridge() and
  demo_spc() compute what the three demos show (the ridge and supervised-PC demos generate their data
  with the course's seeded generator, js_normals()).

Figures reproduced: 18.1, 18.2, 18.3, 18.4, 18.5, 18.6, 18.8, 18.9, 18.12, 18.14, 18.15, 18.16, 18.17,
18.18, 18.19, 18.20. Table 18.1 is recomputed (table_18_1(), cached; about 20 minutes the first time).
Run `python3 ch18_high_dimensional_problems.py --list`, `python3 ch18_high_dimensional_problems.py`
(all figures, a few minutes once the caches exist) or `python3 ch18_high_dimensional_problems.py --fig 18.4`.

Figures not reproduced by code:
* 18.7 (average protein mass spectra of Adam et al. 2002) and Table 18.2: the data are not on the
  book's website.
* 18.10 and Table 18.3 (the abstracts example): the data are not on the book's website.
* 18.11 (follow-up of four patients) and 18.13 (the two-cell-type model): schematic drawings.

Data substitutions (the book's data are not on its website):
* Figures 18.5-18.6: the 38 training samples of Golub et al. (1999) with the 3051 genes of Dudoit,
  Fridlyand and Speed (2002) (R package multtest) instead of 7129 genes with a 34-sample test set; no
  test curve in Figure 18.6.
* Figure 18.8: a simulated CGH profile (cgh_sim()).
* Figure 18.9: simulated protein sequences with planted family motifs (protein_sim()), 45 positives
  and 1663 negatives as in the book; the kernel is the normalised 4-spectrum kernel.
* Figures 18.12 and 18.14: simulated survival data with 240 patients and 7399 genes (survival_sim()).

Settings chosen where the book gives none:
* Figure 18.1: 100 data sets per p (numpy seed 181); the intercept is unpenalised; the test error is
  computed exactly from the coefficients; the Bayes risk uses sigma^2 = p / 2.
* Figure 18.4: 10 folds balanced by class (numpy seed 1810); s0 = median(s_j); the score (18.2) uses
  s_j + s0; priors are the class proportions.
* Table 18.1: 8 folds balanced by class (numpy seed 1801), the same for all methods; NSC with 60
  thresholds; RDA gamma in {0.001, ..., 0.99}; SVM with C = 100; k = 1..10; L2 multinomial lambda in
  {0.01, ..., 1000}; elastic-net alpha in {0.05, 0.1, 0.2, ..., 1}; ties at the CV minimum average the
  test errors, as in the book.
* Figures 18.5-18.6: glmnet scaling of the penalty, paths of up to 100 lambda values down to 1e-4 times
  the largest, stopped when 99.9% of the null deviance is explained; 10 folds (numpy seed 1806).
* Figure 18.8: (lam1, lam2) = (0.4, 6) in the half-scaled form.
* Figure 18.14: the number of genes is chosen from SURV_KS by 10-fold CV of the likelihood-ratio
  statistic of a Cox model fitted to the pooled held-out supervised-PC scores.
* Figure 18.16: 100 realisations (numpy seed 1816), test sets of the same design, one component.
* Figure 18.17: one realisation (numpy seed 1817); the supervised-PC threshold of the pre-conditioning
  step is chosen by 10-fold CV.
* Figures 18.18-18.20: 1000 random permutations (numpy seed 1807); pooled p-values (18.41).
"""
import base64
import json
import math
import os
import subprocess
import time

import numpy as np
from scipy import linalg, optimize, stats

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

CH = 18
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"))
EXTRA = os.path.join(common.CACHE, "esl-extra")      # data exported from R (Golub leukemia)
RSCRIPT = os.environ.get("RSCRIPT", "/usr/local/bin/Rscript")
M32 = 0xFFFFFFFF
SRBCT = ["BL", "EWS", "NB", "RMS"]


def _cache(name):
    os.makedirs(CACHE_DIR, exist_ok=True)
    return os.path.join(CACHE_DIR, name)


# =========================================================================== the demos' generator
def js_uniforms(seed, n, start=0):
    """Uniforms number start+1, ..., start+n of DK.rng(seed) (courses/demo-kit.js), vectorised:
    mulberry32 adds the constant 0x6D2B79F5 to its state at each call and outputs a hash of the state."""
    j = np.arange(start + 1, start + n + 1, dtype=np.uint64)
    m = np.uint64(M32)
    a = (np.uint64(int(seed) & M32) + j * np.uint64(0x6D2B79F5)) & m
    t = ((a ^ (a >> np.uint64(15))) * (np.uint64(1) | a)) & m
    t = ((t + (((t ^ (t >> np.uint64(7))) * (np.uint64(61) | t)) & m)) & m) ^ t
    return ((t ^ (t >> np.uint64(14))) & m).astype(np.float64) / 4294967296.0


def js_normals(seed, n):
    """The first n values of DK.rng(seed).norm() (Box-Muller pairs: r cos(theta), then r sin(theta))."""
    npair = (n + 1) // 2
    u = js_uniforms(seed, 2 * npair)
    u1, u2 = u[0::2], u[1::2]
    if np.any(u1 == 0.0):
        raise RuntimeError("a zero uniform: this stream needs the one-at-a-time generator")
    r = np.sqrt(-2.0 * np.log(u1))
    th = 2.0 * np.pi * u2
    out = np.empty(2 * npair)
    out[0::2] = r * np.cos(th)
    out[1::2] = r * np.sin(th)
    return out[:n]


# =========================================================================== data
def _read_matrix(name):
    return np.loadtxt(common.esl_file(name))


def _read_labels(name):
    with open(common.esl_file(name)) as f:
        return np.array(f.read().split())


def khan():
    """The SRBCT microarray data of Khan et al. (2001) from the book's website: 2308 genes, 63 training
    and 20 test samples (the five unlabelled test samples are dropped). Rows are samples. Classes are
    coded 1-4 = BL, EWS, NB, RMS (8, 23, 12 and 20 training samples)."""
    Xtr = _read_matrix("khan.xtrain").T
    Xte = _read_matrix("khan.xtest").T
    gtr = _read_labels("khan.ytrain").astype(int)
    lab = _read_labels("khan.ytest")
    keep = lab != "NA"
    return Xtr, gtr, Xte[keep], lab[keep].astype(int)


def cancer14(standardize=True):
    """The 14-cancer microarray data of Ramaswamy et al. (2001): 16,063 genes, 144 training and 54 test
    samples (rows). With standardize=True each sample is centred and scaled to unit standard deviation
    across its genes, as in Section 18.3."""
    Xtr = _read_matrix("14cancer.xtrain").T
    Xte = _read_matrix("14cancer.xtest").T
    gtr = _read_labels("14cancer.ytrain").astype(int)
    gte = _read_labels("14cancer.ytest").astype(int)
    if standardize:
        Xtr = (Xtr - Xtr.mean(1, keepdims=True)) / Xtr.std(1, ddof=1, keepdims=True)
        Xte = (Xte - Xte.mean(1, keepdims=True)) / Xte.std(1, ddof=1, keepdims=True)
    return Xtr, gtr, Xte, gte


def radsens():
    """The radiation-sensitivity data of Rieger et al. (2004): a 12,625 x 58 matrix (genes in rows) and
    the group of each patient, 1 = normal reaction (44), 2 = radiation sensitive (14)."""
    return _read_matrix("radsens.x"), _read_labels("radsens.y").astype(int)


def golub():
    """The 38 training samples of the leukemia data of Golub et al. (1999) (27 ALL, coded 0, and 11 AML,
    coded 1), with the 3051 genes kept by the preprocessing of Dudoit, Fridlyand and Speed (2002), as
    shipped with the R package multtest; exported once to the data cache. The book's leukemia data
    (7129 genes and a test set of 34) are not on its website."""
    fx, fy = os.path.join(EXTRA, "golub_train_x.csv"), os.path.join(EXTRA, "golub_train_y.csv")
    if not (os.path.exists(fx) and os.path.exists(fy)):
        os.makedirs(EXTRA, exist_ok=True)
        code = ('suppressMessages(library(multtest)); data(golub); '
                'write.table(t(golub), "%s", sep=",", row.names=FALSE, col.names=FALSE); '
                'write.table(golub.cl, "%s", row.names=FALSE, col.names=FALSE)' % (fx, fy))
        subprocess.run([RSCRIPT, "-e", code], check=True)
    return np.loadtxt(fx, delimiter=","), np.loadtxt(fy).astype(int)


def stratified_folds(g, K, seed):
    """Fold labels 0..K-1 balanced within each class: the members of each class are shuffled and the
    classes laid end to end, then fold = position mod K (numpy seed `seed`)."""
    rng = np.random.default_rng(seed)
    order = np.concatenate([rng.permutation(np.flatnonzero(g == k)) for k in np.unique(g)])
    folds = np.empty(len(g), dtype=int)
    folds[order] = np.arange(len(g)) % K
    return folds


# =========================================================================== 18.1: ridge when p >> N
RHO = 0.2


def ridge_sim(p, rng, N=100, rho=RHO, snr=2.0):
    """One data set of the simulation of Section 18.1, model (18.1): N standard Gaussian features with
    pairwise correlation rho (x = sqrt(1 - rho) z + sqrt(rho) w with a shared w), coefficients
    beta_j ~ N(0, 1), and sigma^2 = beta^T Sigma beta / snr, so that Var E(Y|X) / sigma^2 = snr."""
    X = math.sqrt(1 - rho) * rng.standard_normal((N, p)) + math.sqrt(rho) * rng.standard_normal((N, 1))
    beta = rng.standard_normal(p)
    signal = (1 - rho) * beta @ beta + rho * beta.sum() ** 2
    s2 = signal / snr
    y = X @ beta + math.sqrt(s2) * rng.standard_normal(N)
    return X, y, beta, s2


def ridge_svd(X, y, lams):
    """Ridge regression with an unpenalised intercept for each lambda in lams, through the SVD of the
    centred inputs, X_c = U D V^T (the N x N computation of Section 18.3.5): beta(lambda) =
    V diag(d / (d^2 + lambda)) U^T y_c. Returns (betas [len(lams), p], intercepts, effective df (3.50))."""
    xm, ym = X.mean(0), y.mean()
    U, d, Vt = linalg.svd(X - xm, full_matrices=False)
    uy = U.T @ (y - ym)
    lams = np.atleast_1d(lams)
    B = np.array([Vt.T @ (d / (d ** 2 + lam) * uy) for lam in lams])
    df = np.array([np.sum(d ** 2 / (d ** 2 + lam)) for lam in lams])
    return B, ym - B @ xm, df


def ridge_direct(X, y, lam):
    """The same ridge fit by the p x p route, (X_c^T X_c + lambda I)^{-1} X_c^T y_c (18.14), Cholesky."""
    xm, ym = X.mean(0), y.mean()
    Xc = X - xm
    A = Xc.T @ Xc + lam * np.eye(X.shape[1])
    b = linalg.cho_solve(linalg.cho_factor(A), Xc.T @ (y - ym))
    return b, ym - b @ xm


def ridge_reduced(X, y, lam):
    """Ridge through the reduction of (18.12)-(18.15): X_c = R V^T with R = U D (N x N), ridge on the
    rows of R, and beta = V theta."""
    xm, ym = X.mean(0), y.mean()
    U, d, Vt = linalg.svd(X - xm, full_matrices=False)
    R = U * d
    theta = linalg.solve(R.T @ R + lam * np.eye(R.shape[1]), R.T @ (y - ym), assume_a="pos")
    b = Vt.T @ theta
    return b, ym - b @ xm


def rel_test_error(bhat, beta, s2, rho=RHO):
    """Expected test error at a new X of the fit with slope bhat (the intercept is exactly zero in the
    population and the fitted one is ignored here, as it is O(1/N)), divided by the Bayes error sigma^2:
    1 + (bhat - beta)^T Sigma (bhat - beta) / sigma^2 with Sigma = (1 - rho) I + rho 1 1^T."""
    e = bhat - beta
    return 1.0 + ((1 - rho) * e @ e + rho * e.sum() ** 2) / s2


def bayes_rel_error(X, p, rho=RHO, snr=2.0):
    """The Bayes risk of model (18.1) given the inputs, with beta ~ N(0, I) and sigma^2 at its average
    value p / snr: the posterior mean is ridge without intercept at lambda = sigma^2, and its relative
    error is 1 + trace(Sigma (X^T X + sigma^2 I)^{-1}). No estimator has a smaller average."""
    s2 = p / snr
    N = X.shape[0]
    # trace(Sigma (X^T X + s2 I)^{-1}) through the N x N matrix: (X^T X + s2 I)^{-1} = (I - X^T (X X^T + s2 I)^{-1} X) / s2
    G = linalg.solve(X @ X.T + s2 * np.eye(N), X, assume_a="pos")       # (XX^T + s2 I)^{-1} X
    one = np.ones(p)
    tr_I = (p - np.sum(X * G)) / s2
    v = X @ one
    tr_11 = (p - v @ linalg.solve(X @ X.T + s2 * np.eye(N), v, assume_a="pos")) / s2   # 1^T (.)^{-1} 1
    return 1.0 + (1 - rho) * tr_I + rho * tr_11


FIG18_1_LAMS = (0.001, 100.0, 1000.0)


def ridge_study(nsim=100, seed=181):
    """Figure 18.1: for p = 20, 100, 1000, nsim data sets of model (18.1); relative test errors and
    effective degrees of freedom of ridge at lambda = 0.001, 100, 1000, the number of 'significant'
    univariate coefficients (|t| >= 2), and the Bayes risk of each data set. Cached."""
    path = _cache("ch18_ridge_study_%d_%d.npz" % (nsim, seed))
    if os.path.exists(path):
        z = np.load(path)
        return {k: z[k] for k in z.files}
    rng = np.random.default_rng(seed)
    P = (20, 100, 1000)
    err = np.zeros((3, 3, nsim))
    dfs = np.zeros((3, 3, nsim))
    nsig = np.zeros((3, nsim))
    bayes = np.zeros((3, nsim))
    for a, p in enumerate(P):
        for r in range(nsim):
            X, y, beta, s2 = ridge_sim(p, rng)
            B, _, df = ridge_svd(X, y, FIG18_1_LAMS)
            err[a, :, r] = [rel_test_error(b, beta, s2) for b in B]
            dfs[a, :, r] = df
            Xc, yc = X - X.mean(0), y - y.mean()
            sxx = (Xc ** 2).sum(0)
            bj = Xc.T @ yc / sxx
            rss = (yc ** 2).sum() - bj ** 2 * sxx
            se = np.sqrt(rss / (len(y) - 2) / sxx)
            nsig[a, r] = np.sum(np.abs(bj / se) >= 2)
            bayes[a, r] = bayes_rel_error(X, p)
    out = dict(p=np.array(P), lams=np.array(FIG18_1_LAMS), err=err, df=dfs, nsig=nsig, bayes=bayes)
    np.savez(path, **out)
    return out


def fig_18_1(out_dir=None):
    """Boxplots of the relative test error of ridge regression for p = 20, 100, 1000 (Figure 18.1)."""
    import matplotlib.pyplot as plt
    S = ridge_study()
    fig, axes = plt.subplots(1, 3, figsize=(9.6, 3.5))
    top = 3.2
    for a, ax in enumerate(axes):
        p = int(S["p"][a])
        data = [np.minimum(S["err"][a, k], top + 1) for k in range(3)]
        bp = ax.boxplot(data, widths=0.55, patch_artist=True, showfliers=True,
                        medianprops=dict(color="black", lw=1.5), flierprops=dict(marker="o", ms=3, mfc="none", mec=GREY))
        for b in bp["boxes"]:
            b.set(facecolor="#1b9e77", alpha=0.85, edgecolor="black")
        ax.axhline(S["bayes"][a].mean(), color=PURPLE, ls="--", lw=1.1)
        ax.set_xticks([1, 2, 3])
        ax.set_xticklabels(["%.0f" % S["df"][a, k].mean() for k in range(3)])
        ax.set_ylim(0.9, top)
        ax.set_title("%d features" % p)
        for k in range(3):
            med = np.median(S["err"][a, k])
            if med > top:
                ax.annotate("median %.0f\n(off scale)" % med, xy=(k + 1, top - 0.02), xytext=(k + 1, top - 0.55),
                            ha="center", fontsize=8, arrowprops=dict(arrowstyle="->", lw=0.8))
        print("  p = %4d: df %s, median relative error %s, mean %s, Bayes risk %.3f, significant univariate %.1f"
              % (p, np.round(S["df"][a].mean(1), 1), np.round(np.median(S["err"][a], 1), 3),
                 np.round(S["err"][a].mean(1), 3), S["bayes"][a].mean(), S["nsig"][a].mean()))
    axes[0].set_ylabel("Relative test error")
    axes[1].set_xlabel("Effective degrees of freedom (average)  [lambda = 0.001, 100, 1000]")
    axes[2].plot([], [], color=PURPLE, ls="--", label="Bayes risk")
    axes[2].legend(loc="lower left", frameon=False, fontsize=8)
    fig.tight_layout()
    savefig(fig, CH, "fig18-1", out_dir)
    return S


# =========================================================================== 18.2: nearest shrunken centroids
def soft_threshold(d, delta):
    """sign(d) (|d| - delta)_+, (18.5)."""
    return np.sign(d) * np.maximum(np.abs(d) - delta, 0.0)


def hard_threshold(d, delta):
    """d I(|d| >= delta), (18.6)."""
    return d * (np.abs(d) >= delta)


class NSC:
    """Nearest shrunken centroids, Section 18.2 (Tibshirani et al. 2002).

    fit() computes the overall means xbar_j, the class centroids xbar_kj, the pooled within-class
    standard deviations s_j (divisor N - K), s0 = median(s_j) (or a given value), m_k =
    sqrt(1/N_k - 1/N) and the standardised contrasts d_kj of (18.4). For a threshold Delta the shrunken
    contrasts are (18.5) (or (18.6) with hard=True), the shrunken centroids (18.7), and a sample is
    scored by delta_k(x) = -sum_j (x_j - xbar'_kj)^2 / (s_j + s0)^2 + 2 log pi_k, i.e. (18.2) with s_j
    replaced by s_j + s0, as in the shrunken-centroid classifier. Priors pi_k are the class proportions.
    """

    def fit(self, X, g, s0="median", classes=None):
        self.classes = np.unique(g) if classes is None else np.asarray(classes)
        N = len(g)
        self.Nk = np.array([np.sum(g == k) for k in self.classes])
        self.xbar = X.mean(0)
        self.cent = np.array([X[g == k].mean(0) for k in self.classes])
        ss = sum(((X[g == k] - self.cent[i]) ** 2).sum(0) for i, k in enumerate(self.classes))
        self.s = np.sqrt(ss / (N - len(self.classes)))
        self.s0 = float(np.median(self.s)) if s0 == "median" else float(s0)
        self.mk = np.sqrt(1.0 / self.Nk - 1.0 / N)
        self.scale = self.s + self.s0
        self.d = (self.cent - self.xbar) / (self.mk[:, None] * self.scale)
        self.prior = self.Nk / N
        return self

    def shrunk(self, delta, hard=False):
        return (hard_threshold if hard else soft_threshold)(self.d, delta)

    def centroids(self, delta, hard=False):
        """Shrunken centroids xbar'_kj, (18.7)."""
        return self.xbar + self.mk[:, None] * self.scale * self.shrunk(delta, hard)

    def n_genes(self, delta, hard=False):
        return int(np.sum(np.any(self.shrunk(delta, hard) != 0, axis=0)))

    def scores(self, X, delta, hard=False):
        """Discriminant scores delta_k(x) for the rows of X, (18.2) with the shrunken centroids."""
        C = self.centroids(delta, hard)
        Z = X / self.scale
        Cz = C / self.scale
        sq = (Z ** 2).sum(1)[:, None] - 2 * Z @ Cz.T + (Cz ** 2).sum(1)[None, :]
        return -sq + 2 * np.log(self.prior)

    def predict(self, X, delta, hard=False):
        return self.classes[np.argmax(self.scores(X, delta, hard), axis=1)]

    def posterior(self, X, delta, hard=False):
        """Class probabilities (18.8): softmax of delta_k / 2."""
        s = 0.5 * self.scores(X, delta, hard)
        s -= s.max(1, keepdims=True)
        e = np.exp(s)
        return e / e.sum(1, keepdims=True)


def nsc_cv(X, g, deltas, folds, hard=False, s0="median"):
    """Cross-validated misclassification counts of nearest shrunken centroids for each threshold in
    deltas (the fit, s_j and s0 recomputed without the held-out fold)."""
    errs = np.zeros(len(deltas), dtype=int)
    for k in np.unique(folds):
        tr, te = folds != k, folds == k
        m = NSC().fit(X[tr], g[tr], s0=s0, classes=np.unique(g))
        for a, dl in enumerate(deltas):
            errs[a] += np.sum(m.predict(X[te], dl, hard) != g[te])
    return errs


KHAN_FOLD_SEED = 1810
KHAN_DELTAS = np.round(np.arange(0, 8.0001, 0.05), 2)


def khan_curves(deltas=KHAN_DELTAS):
    """Training, 10-fold CV and test errors of NSC on the SRBCT data over a grid of thresholds."""
    Xtr, gtr, Xte, gte = khan()
    m = NSC().fit(Xtr, gtr)
    folds = stratified_folds(gtr, 10, KHAN_FOLD_SEED)
    cv = nsc_cv(Xtr, gtr, deltas, folds)
    tr = np.array([np.sum(m.predict(Xtr, dl) != gtr) for dl in deltas])
    te = np.array([np.sum(m.predict(Xte, dl) != gte) for dl in deltas])
    ng = np.array([m.n_genes(dl) for dl in deltas])
    return dict(deltas=deltas, train=tr, cv=cv, test=te, ngenes=ng, model=m, folds=folds)


def fig_18_2(out_dir=None):
    """The soft-thresholding function (Figure 18.2)."""
    import matplotlib.pyplot as plt
    x = np.linspace(-3, 3, 601)
    dl = 1.0
    fig, ax = plt.subplots(figsize=(4.0, 3.6))
    ax.plot(x, x, color=RED, lw=1.2, label="45-degree line")
    ax.plot(x, soft_threshold(x, dl), color=ORANGE, lw=2.4, label=r"sign$(x)(|x|-\Delta)_+$")
    ax.axhline(0, color=GREY, lw=0.6)
    ax.axvline(0, color=GREY, lw=0.6)
    ax.annotate("", xy=(dl, -0.25), xytext=(0, -0.25), arrowprops=dict(arrowstyle="<->", lw=0.9))
    ax.text(dl / 2, -0.55, r"$\Delta$", ha="center", fontsize=12)
    ax.text(0.08, 0.12, "(0,0)", fontsize=9)
    ax.set_xlim(-3, 3)
    ax.set_ylim(-3, 3)
    ax.set_xticks([])
    ax.set_yticks([])
    ax.legend(loc="upper left", frameon=False, fontsize=8.5)
    fig.tight_layout()
    savefig(fig, CH, "fig18-2", out_dir)


def _hclust_order(A):
    """Leaf order of average-linkage hierarchical clustering of the rows of A (correlation distance)."""
    from scipy.cluster.hierarchy import leaves_list, linkage
    if A.shape[0] < 3:
        return np.arange(A.shape[0])
    return leaves_list(linkage(A, method="average", metric="correlation"))


def khan_selected(delta=4.34):
    """The genes kept by NSC at threshold delta on the SRBCT training data, each assigned to the class
    with the largest shrunken contrast d'_kj."""
    Xtr, gtr, _, _ = khan()
    m = NSC().fit(Xtr, gtr)
    dp = m.shrunk(delta)
    genes = np.flatnonzero(np.any(dp != 0, axis=0))
    cls = np.argmax(dp[:, genes], axis=0)
    return m, genes, cls


def fig_18_3(out_dir=None, delta=4.34):
    """Heat map of the genes kept by nearest shrunken centroids on the SRBCT data (Figure 18.3)."""
    import matplotlib.pyplot as plt
    from matplotlib.colors import LinearSegmentedColormap
    Xtr, gtr, _, _ = khan()
    m, genes, cls = khan_selected(delta)
    Z = Xtr[:, genes]
    Z = (Z - Z.mean(0)) / Z.std(0)
    rows = []
    for k in range(4):
        gk = np.flatnonzero(cls == k)
        rows.append(gk[_hclust_order(Z[:, gk].T)])
    cols = []
    for k in range(4):
        sk = np.flatnonzero(gtr == k + 1)
        cols.append(sk[_hclust_order(Z[sk])])
    H = Z[np.concatenate(cols)][:, np.concatenate(rows)].T
    cmap = LinearSegmentedColormap.from_list("by", ["#2040ff", "#101060", "#000000", "#606010", "#ffff20"])
    fig, ax = plt.subplots(figsize=(6.4, 4.4))
    ax.imshow(np.clip(H, -2.5, 2.5), aspect="auto", cmap=cmap, vmin=-2.5, vmax=2.5, interpolation="nearest")
    pos = 0
    for k in range(3):
        pos += len(cols[k])
        ax.axvline(pos - 0.5, color="white", lw=1.5)
    pos = 0
    for k in range(3):
        pos += len(rows[k])
        ax.axhline(pos - 0.5, color="white", lw=1.5)
    c0 = 0
    for k in range(4):
        ax.text(c0 + len(cols[k]) / 2 - 0.5, -1.2, SRBCT[k], ha="center", va="bottom", fontsize=9)
        c0 += len(cols[k])
    ax.set_xticks([])
    ax.set_yticks([])
    ax.set_xlabel("Samples (63 training samples, by class)")
    ax.set_ylabel("%d genes" % len(genes))
    fig.tight_layout()
    savefig(fig, CH, "fig18-3", out_dir)
    print("  %d genes at Delta = %.2f; per class block: %s" % (len(genes), delta, [len(r) for r in rows]))
    return genes


def fig_18_4(out_dir=None, delta=4.34):
    """NSC on the SRBCT data: error curves against Delta, and the centroids and shrunken centroids
    (Figure 18.4)."""
    import matplotlib.pyplot as plt
    c = khan_curves()
    m = c["model"]
    Xtr, gtr, Xte, gte = khan()
    fig = plt.figure(figsize=(8.6, 8.4))
    ax = fig.add_axes([0.1, 0.62, 0.86, 0.3])
    dl = c["deltas"]
    ax.plot(dl, c["train"] / len(gtr), "o-", color=GREEN, ms=2.5, lw=1, label="Training")
    ax.plot(dl, c["cv"] / len(gtr), "o-", color=ORANGE, ms=2.5, lw=1, label="10-fold CV")
    ax.plot(dl, c["test"] / len(gte), "o-", color=BLUE, ms=2.5, lw=1, label="Test")
    ax.axvline(delta, color=GREY, ls=":", lw=1)
    ax.set_xlabel(r"Amount of shrinkage $\Delta$")
    ax.set_ylabel("Misclassification error")
    ax.set_xlim(-0.2, 8.1)
    ax.set_ylim(-0.02, 0.8)
    ax.legend(loc="upper left", frameon=False)
    top = ax.twiny()
    top.set_xlim(ax.get_xlim())
    ticks = [0, 1, 2, 3, 4, delta, 5, 6, 7, 8]
    top.set_xticks(ticks)
    top.set_xticklabels([str(m.n_genes(t)) for t in ticks], fontsize=8)
    top.set_xlabel("Number of genes", fontsize=9)
    raw = m.cent - m.xbar
    shr = m.centroids(delta) - m.xbar
    p = raw.shape[1]
    for k in range(4):
        a = fig.add_axes([0.1 + k * 0.225, 0.07, 0.19, 0.44])
        a.barh(np.arange(p), raw[k], height=1.0, color="#b0b0b0", lw=0)
        nz = np.flatnonzero(shr[k])
        a.barh(nz, shr[k, nz], height=14, color=BLUE, lw=0)
        a.axvline(0, color=PURPLE, lw=0.8)
        a.set_xlim(-1.1, 1.1)
        a.set_ylim(-20, p + 20)
        a.set_title(SRBCT[k], fontsize=9)
        a.tick_params(labelsize=7)
        if k:
            a.set_yticklabels([])
        else:
            a.set_ylabel("Gene")
    fig.text(0.53, 0.015, "Centroids: average expression centred at the overall centroid", ha="center", fontsize=9)
    savefig(fig, CH, "fig18-4", out_dir)
    i0 = int(np.argmin(np.abs(dl - delta)))
    best = dl[c["cv"] == c["cv"].min()]
    print("  Delta = 0 (diagonal LDA): train %d, CV %d, test %d errors; Delta = %.2f: %d genes, train %d, CV %d, test %d"
          % (c["train"][0], c["cv"][0], c["test"][0], delta, m.n_genes(delta), c["train"][i0], c["cv"][i0], c["test"][i0]))
    print("  CV minimum %d at Delta in [%.2f, %.2f]; zero test errors for Delta in %s"
          % (c["cv"].min(), best.min(), best.max(), _runs(dl[c["test"] == 0])))
    return c


def _runs(v, step=0.05):
    """Compact text for the sorted values v as runs [a, b]."""
    if len(v) == 0:
        return "none"
    out, a, b = [], v[0], v[0]
    for x in v[1:]:
        if x - b > step * 1.5:
            out.append("[%.2f, %.2f]" % (a, b))
            a = x
        b = x
    out.append("[%.2f, %.2f]" % (a, b))
    return ", ".join(out)



# =========================================================================== 18.3: quadratic regularisation
def svd_reduce(X):
    """X = U D V^T = R V^T with R = U D (N x N) and V (p x N) with orthonormal columns, (18.12)-(18.13)."""
    U, d, Vt = linalg.svd(X, full_matrices=False)
    return U * d, Vt.T


def softmax_rows(F):
    F = F - F.max(1, keepdims=True)
    E = np.exp(F)
    return E / E.sum(1, keepdims=True)


def multinomial_ridge(X, g, lam, classes=None, B0=None, tol=1e-10):
    """The symmetric multinomial model (18.10) fitted by maximising the penalised log-likelihood (18.11),
    sum_i log Pr(g_i | x_i) - (lam / 2) sum_k ||beta_k||^2 (intercepts unpenalised, one of them fixed at
    zero), by L-BFGS. Returns (intercepts [K], coefficients [K, p]). With p >> N call it on the reduced
    inputs R of svd_reduce() and map back with V (the theorem of Section 18.3.5)."""
    classes = np.unique(g) if classes is None else np.asarray(classes)
    K, (N, p) = len(classes), X.shape
    Y = (g[:, None] == classes[None, :]).astype(float)

    def f(w):
        b0 = np.r_[0.0, w[:K - 1]]
        B = w[K - 1:].reshape(K, p)
        F = b0 + X @ B.T
        lse = F.max(1) + np.log(np.exp(F - F.max(1, keepdims=True)).sum(1))
        val = -(np.sum(Y * F) - lse.sum()) + 0.5 * lam * np.sum(B * B)
        P = softmax_rows(F)
        G = P - Y
        return val, np.r_[G.sum(0)[1:], (G.T @ X + lam * B).ravel()]

    w0 = np.zeros(K - 1 + K * p) if B0 is None else B0
    r = optimize.minimize(f, w0, jac=True, method="L-BFGS-B", options=dict(maxiter=20000, gtol=tol, ftol=1e-15))
    return np.r_[0.0, r.x[:K - 1]], r.x[K - 1:].reshape(K, p)


def logistic_ridge(X, y, lam, tol=1e-12, maxit=100):
    """Two-class logistic regression with penalty (lam / 2) ||beta||^2 (intercept unpenalised), y in
    {0, 1}, by Newton-Raphson. Use on the N x N reduced inputs when p >> N."""
    N, p = X.shape
    A = np.column_stack([np.ones(N), X])
    w = np.zeros(p + 1)
    P = lam * np.eye(p + 1)
    P[0, 0] = 0.0
    for _ in range(maxit):
        mu = common.sigmoid(A @ w)
        grad = A.T @ (y - mu) - P @ w
        H = (A * (mu * (1 - mu))[:, None]).T @ A + P
        step = linalg.solve(H, grad, assume_a="pos")
        w = w + step
        if np.abs(step).max() < tol:
            break
    return w[0], w[1:]


class RDA:
    """Regularised discriminant analysis (18.9): the within-class covariance is shrunk towards its
    diagonal, Sigma(gamma) = gamma Sigma + (1 - gamma) diag(Sigma), 0 <= gamma < 1. Computed without
    any p x p matrix (Exercise 18.6): with D = diag(Sigma) and the scaled within-class residuals
    W = (X - centroids) D^{-1/2} / sqrt(N - K) = U S V^T, Sigma(gamma)^{-1} = D^{-1/2} [V diag(1 / (gamma s^2 +
    1 - gamma) - 1 / (1 - gamma)) V^T + I / (1 - gamma)] D^{-1/2}."""

    def fit(self, X, g):
        self.classes = np.unique(g)
        N, K = len(g), len(self.classes)
        self.mu = np.array([X[g == k].mean(0) for k in self.classes])
        W = X - self.mu[np.searchsorted(self.classes, g)]
        self.dsd = np.sqrt((W ** 2).sum(0) / (N - K))
        self.dsd[self.dsd == 0] = 1.0
        _, s, Vt = linalg.svd(W / self.dsd / math.sqrt(N - K), full_matrices=False)
        self.s2, self.Vt = s ** 2, Vt
        self.prior = np.array([np.mean(g == k) for k in self.classes])
        self.mut = self.mu / self.dsd
        return self

    def _apply_inv(self, A, gamma):
        """A Sigma~(gamma)^{-1} for the rows of A (in the scaled coordinates)."""
        c = 1.0 / (gamma * self.s2 + 1 - gamma) - 1.0 / (1 - gamma)
        return (A @ self.Vt.T * c) @ self.Vt + A / (1 - gamma)

    def scores(self, X, gamma):
        M = self._apply_inv(self.mut, gamma)                       # K x p
        return (X / self.dsd) @ M.T - 0.5 * np.sum(M * self.mut, 1) + np.log(self.prior)

    def predict(self, X, gamma):
        return self.classes[np.argmax(self.scores(X, gamma), 1)]


def knn_predict(Xtr, gtr, Xte, k):
    """k-nearest-neighbour vote (ties broken by the nearer neighbours: the class of the first among
    the tied classes in distance order)."""
    D = (Xte ** 2).sum(1)[:, None] - 2 * Xte @ Xtr.T + (Xtr ** 2).sum(1)[None, :]
    idx = np.argsort(D, axis=1, kind="stable")[:, :k]
    out = np.empty(len(Xte), dtype=gtr.dtype)
    for i, row in enumerate(idx):
        labs = gtr[row]
        vals, cnt = np.unique(labs, return_counts=True)
        best = vals[cnt == cnt.max()]
        out[i] = next(l for l in labs if l in best)
    return out


def svm_ova_predict(Ktr, gtr, Kte, C=100.0):
    """One-versus-all linear support vector classifiers on a precomputed inner-product matrix; the
    class with the largest decision value wins (Section 18.3.3)."""
    from sklearn.svm import SVC
    classes = np.unique(gtr)
    F = np.column_stack([SVC(kernel="precomputed", C=C, tol=1e-6).fit(Ktr, np.where(gtr == k, 1, -1)).decision_function(Kte)
                         for k in classes])
    return classes[np.argmax(F, 1)]


def _cv_summary(errs, test, n):
    """CV errors (counts out of n, with the standard error of the fold average), and the test errors
    averaged over all parameter values tied at the CV minimum, as in Table 18.1."""
    tot = errs.sum(0)
    best = np.flatnonzero(tot == tot.min())
    nf = errs.shape[0]
    se = errs[:, best[0]].std(ddof=1) * nf / math.sqrt(nf)
    return dict(cv=int(tot.min()), se=float(se), test=float(np.mean(test[best])), best=best.tolist())


_R_GLMNET = r'''
suppressMessages(library(glmnet)); suppressMessages(library(jsonlite))
args <- commandArgs(TRUE)
X <- as.matrix(read.csv(args[1], header=FALSE)); Xt <- as.matrix(read.csv(args[2], header=FALSE))
g <- scan(args[3], quiet=TRUE); gt <- scan(args[4], quiet=TRUE); fold <- scan(args[5], quiet=TRUE) + 1
K <- sort(unique(g)); nf <- max(fold); out <- list()
summ <- function(errs, test, ngenes, extra=list()) {
  tot <- colSums(errs); best <- which(tot == min(tot))
  c(list(cv=min(tot), se=sd(errs[, best[1]]) * nf / sqrt(nf), test=mean(test[best]), genes=mean(ngenes[best]),
         nbest=length(best)), extra)
}
## line 4: lasso regression, one versus all, common lambda grid
lam <- exp(seq(log(1), log(1e-3), length.out=60))
ova <- function(Xa, ga, Xb) {
  F <- sapply(K, function(k) { f <- glmnet(Xa, ifelse(ga == k, 1, -1), lambda=lam); predict(f, Xb) }, simplify="array")
  F
}
nz4 <- sapply(K, function(k) { f <- glmnet(X, ifelse(g == k, 1, -1), lambda=lam); as.matrix(f$beta != 0) }, simplify="array")
genes4 <- apply(nz4, 2, function(m) sum(rowSums(m) > 0))
Ft <- ova(X, g, Xt); test4 <- apply(Ft, 2, function(F) sum(K[max.col(F, "first")] != gt))
errs4 <- t(sapply(1:nf, function(f) { Fv <- ova(X[fold != f, ], g[fold != f], X[fold == f, , drop=FALSE]);
  apply(Fv, 2, function(F) sum(K[max.col(matrix(F, ncol=length(K)), "first")] != g[fold == f])) }))
out$lasso_ova <- summ(errs4, test4, genes4)
## lines 7-8: L1 and elastic-net penalised multinomial over a grid of alpha
mult <- function(alpha) {
  f <- glmnet(X, factor(g), family="multinomial", alpha=alpha, nlambda=100, lambda.min.ratio=1e-4)
  lam <- f$lambda
  nz <- Reduce(`|`, lapply(f$beta, function(b) as.matrix(b != 0)))
  genes <- colSums(nz)
  test <- colSums(predict(f, Xt, type="class") != gt)
  errs <- t(sapply(1:nf, function(k) { fk <- glmnet(X[fold != k, ], factor(g[fold != k]), family="multinomial", alpha=alpha, lambda=lam);
    pr <- predict(fk, X[fold == k, , drop=FALSE], type="class"); r <- colSums(pr != g[fold == k]);
    c(r, rep(NA, length(lam) - length(r))) }))
  errs[is.na(errs)] <- nrow(X)
  list(errs=errs, test=test, genes=genes, lam=lam)
}
alphas <- as.numeric(strsplit(args[7], ",")[[1]]); res <- list()
for (a in alphas) res[[as.character(a)]] <- mult(a)
r1 <- res[["1"]]; out$l1_mult <- summ(r1$errs, r1$test, r1$genes, list(lambda=r1$lam[which.min(colSums(r1$errs))]))
allerr <- do.call(cbind, lapply(res, function(r) r$errs)); alltest <- unlist(lapply(res, function(r) r$test))
allgenes <- unlist(lapply(res, function(r) r$genes))
alab <- unlist(lapply(names(res), function(a) rep(as.numeric(a), length(res[[a]]$test))))
s <- summ(allerr, alltest, allgenes); tot <- colSums(allerr); best <- which(tot == min(tot))
s$alpha <- sort(unique(alab[best])); out$enet_mult <- s
out$enet_by_alpha <- lapply(res, function(r) { tot <- colSums(r$errs); b <- which(tot == min(tot)); list(cv=min(tot), test=mean(r$test[b])) })
writeLines(toJSON(out, auto_unbox=TRUE, digits=8), args[6])
'''

TABLE18_1_ALPHAS = (0.05, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0)


def table_18_1(refresh=False):
    """Table 18.1 on the 14-cancer data: 8-fold cross-validated errors (out of 144) with standard
    errors, test errors (out of 54) and genes used, for nearest shrunken centroids, RDA (18.9), the
    one-versus-all linear SVM, k-nearest neighbours and the L2-penalised multinomial (all computed
    here, the last three through the N x N reduction of Section 18.3.5) and, through the R package
    glmnet, the one-versus-all lasso and the L1 and elastic-net penalised multinomial. Cached."""
    path = _cache("ch18_table18_1.json")
    if os.path.exists(path) and not refresh:
        with open(path) as f:
            return json.load(f)
    Xtr, gtr, Xte, gte = cancer14()
    N, p = Xtr.shape
    folds = stratified_folds(gtr, 8, 1801)
    nf = 8
    out = {}
    # 1. nearest shrunken centroids
    m = NSC().fit(Xtr, gtr)
    deltas = np.linspace(0, np.abs(m.d).max(), 60)
    errs = np.zeros((nf, len(deltas)), dtype=int)
    for k in range(nf):
        mk = NSC().fit(Xtr[folds != k], gtr[folds != k], classes=np.unique(gtr))
        for a, dl in enumerate(deltas):
            errs[k, a] = np.sum(mk.predict(Xtr[folds == k], dl) != gtr[folds == k])
    test = np.array([np.sum(m.predict(Xte, dl) != gte) for dl in deltas])
    s = _cv_summary(errs, test, N)
    s["genes"] = float(np.mean([m.n_genes(deltas[b]) for b in s["best"]]))
    s["delta"] = [float(deltas[b]) for b in s["best"]]
    out["nsc"] = s
    # 2. RDA, gamma by CV
    gammas = np.array([0.001, 0.002, 0.005, 0.01, 0.02, 0.05, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.95, 0.99])
    errs = np.zeros((nf, len(gammas)), dtype=int)
    for k in range(nf):
        r = RDA().fit(Xtr[folds != k], gtr[folds != k])
        for a, gm in enumerate(gammas):
            errs[k, a] = np.sum(r.predict(Xtr[folds == k], gm) != gtr[folds == k])
    r = RDA().fit(Xtr, gtr)
    test = np.array([np.sum(r.predict(Xte, gm) != gte) for gm in gammas])
    s = _cv_summary(errs, test, N)
    s["genes"] = p
    s["gamma"] = [float(gammas[b]) for b in s["best"]]
    out["rda"] = s
    # 3. one-versus-all linear SVM through the inner-product matrix
    Kall = Xtr @ Xtr.T
    Kte = Xte @ Xtr.T
    errs = np.zeros((nf, 1), dtype=int)
    for k in range(nf):
        tr, te = folds != k, folds == k
        errs[k, 0] = np.sum(svm_ova_predict(Kall[np.ix_(tr, tr)], gtr[tr], Kall[np.ix_(te, tr)]) != gtr[te])
    test = np.array([np.sum(svm_ova_predict(Kall, gtr, Kte) != gte)])
    s = _cv_summary(errs, test, N)
    s["genes"] = p
    out["svm"] = s
    # 5. k-nearest neighbours
    ks = np.arange(1, 11)
    errs = np.zeros((nf, len(ks)), dtype=int)
    for k in range(nf):
        tr, te = folds != k, folds == k
        for a, kk in enumerate(ks):
            errs[k, a] = np.sum(knn_predict(Xtr[tr], gtr[tr], Xtr[te], kk) != gtr[te])
    test = np.array([np.sum(knn_predict(Xtr, gtr, Xte, kk) != gte) for kk in ks])
    s = _cv_summary(errs, test, N)
    s["genes"] = p
    s["k"] = [int(ks[b]) for b in s["best"]]
    out["knn"] = s
    # 6. L2-penalised multinomial on R = U D: one reduction for all folds (Exercise 18.12)
    R, V = svd_reduce(Xtr)
    Rte = Xte @ V
    lams = np.array([0.01, 0.1, 1.0, 10.0, 100.0, 1000.0])
    errs = np.zeros((nf, len(lams)), dtype=int)
    classes = np.unique(gtr)
    for k in range(nf):
        tr, te = folds != k, folds == k
        for a, lam in enumerate(lams):
            b0, B = multinomial_ridge(R[tr], gtr[tr], lam, classes=classes, tol=1e-7)
            errs[k, a] = np.sum(classes[np.argmax(b0 + R[te] @ B.T, 1)] != gtr[te])
    test = []
    for lam in lams:
        b0, B = multinomial_ridge(R, gtr, lam, classes=classes, tol=1e-7)
        test.append(np.sum(classes[np.argmax(b0 + Rte @ B.T, 1)] != gte))
    s = _cv_summary(errs, np.array(test), N)
    s["genes"] = p
    s["lambda"] = [float(lams[b]) for b in s["best"]]
    out["l2_mult"] = s
    # 4, 7, 8 through glmnet
    tmp = _cache("ch18_t181")
    os.makedirs(tmp, exist_ok=True)
    np.savetxt(os.path.join(tmp, "x.csv"), Xtr, delimiter=",", fmt="%.7g")
    np.savetxt(os.path.join(tmp, "xt.csv"), Xte, delimiter=",", fmt="%.7g")
    np.savetxt(os.path.join(tmp, "g.txt"), gtr, fmt="%d")
    np.savetxt(os.path.join(tmp, "gt.txt"), gte, fmt="%d")
    np.savetxt(os.path.join(tmp, "fold.txt"), folds, fmt="%d")
    with open(os.path.join(tmp, "glmnet.R"), "w") as f:
        f.write(_R_GLMNET)
    res = os.path.join(tmp, "glmnet.json")
    subprocess.run([RSCRIPT, os.path.join(tmp, "glmnet.R")] + [os.path.join(tmp, n) for n in ("x.csv", "xt.csv", "g.txt", "gt.txt", "fold.txt")]
                   + [res, ",".join("%g" % a for a in TABLE18_1_ALPHAS)], check=True)
    with open(res) as f:
        out.update(json.load(f))
    for n in ("x.csv", "xt.csv"):                          # the large temporary inputs are not kept
        os.remove(os.path.join(tmp, n))
    with open(path, "w") as f:
        json.dump(out, f, indent=1)
    return out


def print_table_18_1():
    t = table_18_1()
    rows = [("1. Nearest shrunken centroids", "nsc"), ("2. L2-penalised discriminant analysis", "rda"),
            ("3. Support vector classifier (ova)", "svm"), ("4. Lasso regression (one vs all)", "lasso_ova"),
            ("5. k-nearest neighbours", "knn"), ("6. L2-penalised multinomial", "l2_mult"),
            ("7. L1-penalised multinomial", "l1_mult"), ("8. Elastic-net penalised multinomial", "enet_mult")]
    print("  %-40s %14s %10s %10s" % ("Method", "CV errors (SE)", "Test", "Genes"))
    for lab, k in rows:
        r = t[k]
        print("  %-40s %8.1f (%.1f) %10.1f %10.0f" % (lab, r["cv"], r["se"], r["test"], r["genes"]))
    return t


# =========================================================================== 18.4: L1 regularisation
def logistic_enet_path(X, y, alpha=1.0, lambdas=None, nlambda=100, ratio=1e-4, tol=1e-8, dev_stop=0.999):
    """Penalised two-class logistic regression along a decreasing sequence of lambda, by cyclical
    coordinate descent on the IRLS quadratic approximation (Friedman, Hastie and Tibshirani 2010),
    written to be read: minimise

        -(1/N) loglik(beta_0, beta) + lambda [alpha ||beta||_1 + (1 - alpha) ||beta||_2^2 / 2]

    (the glmnet scaling of (18.19)-(18.20)), with the inputs standardised (divisor N) inside and the
    coefficients returned on the original scale. y in {0, 1}. Warm starts along the path; each
    coordinate update is the soft-thresholded weighted least-squares step; the active set is cycled
    until it converges, then the optimality condition of every coefficient at zero is checked at once
    (one matrix-vector product) and any violators join the active set. As in glmnet the path stops
    when the fraction of null deviance explained exceeds dev_stop (the data are separable when p > N, and
    the coefficients diverge as lambda -> 0, Exercise 18.11).
    Returns dict(lam, b0 [L], beta [L, p], df [L], dev_ratio [L])."""
    N, p = X.shape
    mx, sx = X.mean(0), X.std(0)
    sx[sx == 0] = 1.0
    Zt = np.ascontiguousarray(((X - mx) / sx).T)          # p x N, one row per input
    ybar = y.mean()
    if lambdas is None:
        lmax = np.max(np.abs(Zt @ (y - ybar))) / N / max(alpha, 1e-3)
        lambdas = lmax * np.logspace(0, math.log10(ratio), nlambda)
    lambdas = np.asarray(lambdas, dtype=float)
    null_dev = -2 * N * (ybar * math.log(ybar) + (1 - ybar) * math.log(1 - ybar))
    b0, b = math.log(ybar / (1 - ybar)), np.zeros(p)
    L0, B, D, R = [], [], [], []
    for lam in lambdas:
        l1, l2 = lam * alpha, lam * (1 - alpha)
        for _ in range(200):                                       # IRLS (outer) loop
            eta = b0 + b @ Zt
            mu = common.sigmoid(eta)
            w = np.maximum(mu * (1 - mu), 1e-5)
            r = (y - mu) / w                                       # working residual z - eta
            xw2 = (Zt ** 2) @ w / N
            b_start, b0_start = b.copy(), b0
            active = np.flatnonzero(b)
            while True:
                while True:                                    # cycle over the active set
                    dmax = 0.0
                    for j in active:
                        zj = Zt[j]
                        bj = b[j]
                        gj = (w * r) @ zj / N + xw2[j] * bj
                        new = (math.copysign(max(abs(gj) - l1, 0.0), gj)) / (xw2[j] + l2)
                        if new != bj:
                            r -= (new - bj) * zj
                            b[j] = new
                            dmax = max(dmax, xw2[j] * (new - bj) ** 2)
                    d0 = (w @ r) / w.sum()
                    b0 += d0
                    r -= d0
                    dmax = max(dmax, w.sum() / N * d0 * d0)
                    if dmax < tol:
                        break
                # optimality check for every input at zero, in one product: |gradient| <= lam * alpha
                grad = Zt @ (w * r) / N
                viol = np.flatnonzero((b == 0) & (np.abs(grad) > l1 * (1 + 1e-9)))
                if len(viol) == 0:
                    break
                active = np.union1d(active, viol)
            if max(np.abs(b - b_start).max() if p else 0, abs(b0 - b0_start)) < 1e-6:
                break
        eta = b0 + b @ Zt
        mu = np.clip(common.sigmoid(eta), 1e-15, 1 - 1e-15)
        dev = -2 * np.sum(y * np.log(mu) + (1 - y) * np.log(1 - mu))
        beta = b / sx
        L0.append(b0 - beta @ mx)
        B.append(beta.copy())
        D.append(dev)
        R.append(1 - dev / null_dev)
        if R[-1] > dev_stop:
            break
    k = len(B)
    return dict(lam=lambdas[:k], b0=np.array(L0), beta=np.array(B), df=np.array([np.sum(v != 0) for v in B]),
                dev_ratio=np.array(R), dev=np.array(D))


def leukemia_paths(refresh=False):
    """Figures 18.5-18.6: lasso (alpha = 1) and elastic-net (alpha = 0.8) logistic paths on the Golub
    training data, and 10-fold CV of the lasso path (misclassification and deviance). Cached."""
    path = _cache("ch18_leukemia.npz")
    if os.path.exists(path) and not refresh:
        z = np.load(path)
        return {k: z[k] for k in z.files}
    X, y = golub()
    out = {}
    for name, a in (("lasso", 1.0), ("enet", 0.8)):
        P = logistic_enet_path(X, y, alpha=a)
        for k, v in P.items():
            out[name + "_" + k] = v
    lam = out["lasso_lam"]
    folds = stratified_folds(y, 10, 1806)
    L = len(lam)
    cv_err, cv_dev = np.zeros(L), np.zeros(L)
    for k in range(10):
        tr, te = folds != k, folds == k
        P = logistic_enet_path(X[tr], y[tr], alpha=1.0, lambdas=lam)
        for i in range(L):
            j = min(i, len(P["lam"]) - 1)                  # a path stopped early keeps its last fit
            mu = np.clip(common.sigmoid(P["b0"][j] + X[te] @ P["beta"][j]), 1e-15, 1 - 1e-15)
            cv_err[i] += np.sum((mu > 0.5) != y[te])
            cv_dev[i] += -2 * np.sum(y[te] * np.log(mu) + (1 - y[te]) * np.log(1 - mu))
    tr_err = np.array([np.sum(((out["lasso_b0"][i] + X @ out["lasso_beta"][i]) > 0) != y) for i in range(L)])
    out.update(cv_err=cv_err, cv_dev=cv_dev, train_err=tr_err, folds=folds)
    np.savez(path, **out)
    return out


def fig_18_5(out_dir=None):
    """Lasso and elastic-net logistic regression paths on the leukemia data (Figure 18.5)."""
    import matplotlib.pyplot as plt
    S = leukemia_paths()
    fig, axes = plt.subplots(1, 2, figsize=(9.6, 4.0), sharey=True)
    cmap = plt.get_cmap("tab10")
    for ax, name, title in ((axes[0], "lasso", "Lasso"), (axes[1], "enet", r"Elastic net, $\alpha = 0.8$")):
        lam, B = S[name + "_lam"], S[name + "_beta"]
        used = np.flatnonzero(np.any(B != 0, 0))
        for c, j in enumerate(used):
            ax.plot(np.log(lam), B[:, j], color=cmap(c % 10), lw=0.9)
        ax.axhline(0, color=GREY, lw=0.6)
        ax.set_xlabel(r"$\log(\lambda)$")
        ax.set_title(title)
        ax.invert_xaxis()
        ax.text(0.03, 0.95, "%d non-zero at the end" % S[name + "_df"][-1], transform=ax.transAxes, va="top", fontsize=9)
        print("  %s: %d lambda values from %.3g to %.3g; %d non-zero at the end (deviance explained %.4f); %d genes ever enter"
              % (name, len(lam), lam[0], lam[-1], S[name + "_df"][-1], S[name + "_dev_ratio"][-1], len(used)))
    axes[0].set_ylabel("Coefficients")
    fig.tight_layout()
    savefig(fig, CH, "fig18-5", out_dir)


def fig_18_6(out_dir=None):
    """Training and 10-fold CV curves of the lasso logistic regression on the leukemia data
    (Figure 18.6): misclassification error and binomial deviance."""
    import matplotlib.pyplot as plt
    S = leukemia_paths()
    X, y = golub()
    lam = S["lasso_lam"]
    N = len(y)
    fig, axes = plt.subplots(1, 2, figsize=(9.6, 3.8))
    ll = np.log(lam)
    axes[0].plot(ll, S["train_err"] / N, color=GREEN, label="Training")
    axes[0].plot(ll, S["cv_err"] / N, color=ORANGE, label="10-fold CV")
    axes[0].set_ylabel("Misclassification error")
    axes[0].legend(frameon=False)
    axes[1].plot(ll, S["lasso_dev"] / N, color=GREEN, label="Training")
    axes[1].plot(ll, S["cv_dev"] / N, color=ORANGE, label="10-fold CV")
    axes[1].set_ylabel("Deviance per observation")
    for ax in axes:
        ax.set_xlabel(r"$\log(\lambda)$")
        ax.invert_xaxis()
    fig.tight_layout()
    savefig(fig, CH, "fig18-6", out_dir)
    i = int(np.argmin(S["cv_dev"]))
    print("  CV misclassification at the end of the path %d/38 (minimum %d/38); CV deviance minimum %.2f per obs at log lambda %.2f (end %.2f)"
          % (S["cv_err"][-1], S["cv_err"].min(), S["cv_dev"][i] / N, ll[i], S["cv_dev"][-1] / N))


# =========================================================================== fused lasso
def _tv_dual_polish(y, lam, u):
    """Exact solution of the dual of 1-D total-variation denoising from a near-optimal start: fix the
    multipliers at their bounds and solve the tridiagonal system for the free ones; repeat until the
    signs and bounds are consistent (a primal-dual active-set step)."""
    n = len(y)
    m = n - 1
    Dy = np.diff(y)
    for _ in range(50):
        at = np.abs(np.abs(u) - lam) < 1e-9 * max(1.0, lam)
        free = ~at
        ub = np.where(at, np.sign(u) * lam, 0.0)
        # D D^T is tridiagonal with 2 on the diagonal and -1 off it; solve (DD^T)_ff u_f = Dy_f - (DD^T)_fb u_b
        if free.any():
            fi = np.flatnonzero(free)
            DDt_ub = 2 * ub - np.r_[ub[1:], 0] - np.r_[0, ub[:-1]]
            rhs = Dy[fi] - DDt_ub[fi]
            k = len(fi)
            diag = 2 * np.ones(k)
            off = -1.0 * (np.diff(fi) == 1)
            ab = np.zeros((3, k))
            ab[0, 1:] = off
            ab[1] = diag
            ab[2, :-1] = off
            uf = linalg.solve_banded((1, 1), ab, rhs)
            unew = ub.copy()
            unew[fi] = uf
        else:
            unew = ub
        b = y - _DT(unew)
        g = np.diff(b)                                   # primal differences = minus the dual gradient
        viol_free = np.abs(unew) > lam * (1 + 1e-12)
        # a multiplier at its bound u_i = lam s_i needs s_i (b_{i+1} - b_i) >= 0
        viol_bound = at & (np.sign(u) * g < -1e-10)
        if not viol_free.any() and not viol_bound.any():
            return unew
        u = np.clip(unew, -lam, lam)
        u[viol_bound] = 0.5 * u[viol_bound]
    return np.clip(u, -lam, lam)


def _DT(u):
    """D^T u for the first-difference matrix D (rows e_{i+1} - e_i)."""
    out = np.zeros(len(u) + 1)
    out[:-1] -= u
    out[1:] += u
    return out


def tv_denoise(y, lam):
    """min_b (1/2) ||y - b||^2 + lam sum_i |b_{i+1} - b_i| (the fused lasso signal approximator with
    lambda_1 = 0), through its dual min_u (1/2) ||y - D^T u||^2 subject to |u_i| <= lam, b = y - D^T u:
    L-BFGS-B, then an exact active-set polish."""
    y = np.asarray(y, dtype=float)
    if lam <= 0:
        return y.copy()

    def f(u):
        rres = y - _DT(u)
        return 0.5 * rres @ rres, -np.diff(rres) * 1.0

    r = optimize.minimize(f, np.zeros(len(y) - 1), jac=True, method="L-BFGS-B",
                          bounds=[(-lam, lam)] * (len(y) - 1), options=dict(maxiter=50000, gtol=1e-12, ftol=1e-16))
    u = _tv_dual_polish(y, lam, r.x)
    return y - _DT(u)


def flsa(y, lam1, lam2):
    """The fused lasso signal approximator in the (1/2)-scaled form
    min_b (1/2) ||y - b||^2 + lam1 sum |b_i| + lam2 sum |b_{i+1} - b_i|. By the result of Friedman et al.
    (2007) the solution is the soft-thresholded solution with lam1 = 0. (The book's (18.24) has no 1/2
    and an intercept: its (lambda_1, lambda_2) are (2 lam1, 2 lam2) here, and beta_0 is dropped.)"""
    return soft_threshold(tv_denoise(y, lam2), lam1)


def flsa_direct(y, lam1, lam2):
    """The same problem solved directly through its dual with both penalties (for checking):
    min (1/2) ||y - D^T u - v||^2 subject to |u_i| <= lam2, |v_i| <= lam1; b = y - D^T u - v."""
    n = len(y)

    def f(z):
        u, v = z[:n - 1], z[n - 1:]
        rres = y - _DT(u) - v
        return 0.5 * rres @ rres, np.r_[-np.diff(rres), -rres]

    r = optimize.minimize(f, np.zeros(2 * n - 1), jac=True, method="L-BFGS-B",
                          bounds=[(-lam2, lam2)] * (n - 1) + [(-lam1, lam1)] * n, options=dict(maxiter=100000, gtol=1e-13, ftol=1e-17))
    u, v = r.x[:n - 1], r.x[n - 1:]
    return y - _DT(u) - v


def cgh_sim(seed=188, n=1000):
    """A simulated copy-number (CGH) profile in genome order: log2 ratios with three gains and one
    loss of different lengths and heights, Gaussian noise (sd 0.6) and a few outliers. (The book's
    CGH sample of Tibshirani and Wang (2008) is not on its website.)"""
    rng = np.random.default_rng(seed)
    truth = np.zeros(n)
    for a, b, h in ((150, 260, 1.4), (420, 560, -1.1), (700, 718, 3.0), (840, 950, 0.7)):
        truth[a:b] = h
    y = truth + 0.6 * rng.standard_normal(n)
    out = rng.choice(n, 8, replace=False)
    y[out] += rng.choice([-1, 1], 8) * rng.uniform(2, 3, 8)
    return y, truth


CGH_LAMS = (0.4, 6.0)   # (lam1, lam2) in the (1/2)-form; the book's (18.24) scale is twice these


def fig_18_8(out_dir=None):
    """The fused lasso signal approximator on a simulated CGH profile (Figure 18.8)."""
    import matplotlib.pyplot as plt
    y, truth = cgh_sim()
    fit = flsa(y, *CGH_LAMS)
    fig, ax = plt.subplots(figsize=(8.0, 3.6))
    ax.plot(np.arange(len(y)), y, "o", ms=2.2, color="#707070", alpha=0.8)
    ax.plot(truth, color=BLUE, lw=0.9, ls="--", label="true copy-number signal")
    ax.plot(fit, color="#8b0000", lw=2.0, label="fused lasso estimate")
    ax.axhline(0, color=GREY, lw=0.6)
    ax.set_xlabel("Genome order")
    ax.set_ylabel(r"$\log_2$ ratio")
    ax.legend(frameon=False, fontsize=8.5, loc="lower left")
    fig.tight_layout()
    savefig(fig, CH, "fig18-8", out_dir)
    segs = 1 + np.sum(np.abs(np.diff(fit)) > 1e-8)
    print("  lam1 = %g, lam2 = %g (half-scaled); %d constant pieces, %d of %d positions non-zero; mean abs error to the truth %.3f (raw data %.3f)"
          % (CGH_LAMS[0], CGH_LAMS[1], segs, np.sum(np.abs(fit) > 1e-10), len(y), np.abs(fit - truth).mean(), np.abs(y - truth).mean()))


# =========================================================================== 18.5: features unavailable
AMINO = "ACDEFGHIKLMNPQRSTVWY"


def protein_sim(seed=185, n_neg=1663, n_pos=45, motif_len=9, mut=0.4):
    """Simulated protein sequences standing in for the data of Leslie et al. (2004) (not reproduced
    here): strings over the 20 amino acids with lengths uniform on 75-160. Every sequence belongs to a
    family with three short 'family motifs' (length motif_len) planted at random positions, each
    letter mutated with probability mut; the positive class is one family of size n_pos, the negatives
    come from 40 other families. Background letters follow a fixed non-uniform composition."""
    rng = np.random.default_rng(seed)
    comp = rng.dirichlet(np.full(20, 4.0))
    fams = [[rng.choice(20, motif_len, p=comp) for _ in range(3)] for _ in range(41)]
    labels = np.r_[np.zeros(n_neg, dtype=int), np.ones(n_pos, dtype=int)]
    fam_of = np.r_[rng.integers(1, 41, n_neg), np.zeros(n_pos, dtype=int)]
    seqs = []
    for f in fam_of:
        L = int(rng.integers(75, 161))
        s = rng.choice(20, L, p=comp)
        for mot in fams[f]:
            m = mot.copy()
            flip = rng.random(motif_len) < mut
            m[flip] = rng.choice(20, flip.sum(), p=comp)
            at = int(rng.integers(0, L - motif_len))
            s[at:at + motif_len] = m
        seqs.append("".join(AMINO[c] for c in s))
    return seqs, labels


def spectrum_features(seqs, m):
    """The m-spectrum feature map (18.25) as a sparse N x 20^m count matrix: phi_a(x) is the number of
    times the length-m string a occurs in x (overlapping occurrences counted)."""
    from scipy import sparse
    idx = {c: i for i, c in enumerate(AMINO)}
    rows, cols = [], []
    for i, s in enumerate(seqs):
        code = np.array([idx[c] for c in s])
        h = np.zeros(len(code) - m + 1, dtype=np.int64)
        for t in range(m):
            h = h * 20 + code[t:len(code) - m + 1 + t]
        rows.append(np.full(len(h), i))
        cols.append(h)
    rows, cols = np.concatenate(rows), np.concatenate(cols)
    return sparse.csr_matrix((np.ones(len(rows)), (rows, cols)), shape=(len(seqs), 20 ** m))


def string_kernel(seqs, m=4, normalise=True):
    """K_m(x, x') = <Phi_m(x), Phi_m(x')>, (18.26), for all pairs, through the sparse feature map (the
    20^m-dimensional vectors are never formed densely). With normalise=True, K(x, x') / sqrt(K(x, x)
    K(x', x')), which removes the effect of sequence length."""
    F = spectrum_features(seqs, m)
    K = (F @ F.T).toarray()
    if normalise:
        dg = np.sqrt(np.diag(K))
        K = K / np.outer(dg, dg)
    return K


def kernel_sqdist(K, rows, cols):
    """Squared distances ||x_i - x_j||^2 = K_ii + K_jj - 2 K_ij, (18.27)."""
    dg = np.diag(K)
    return dg[rows][:, None] + dg[cols][None, :] - 2 * K[np.ix_(rows, cols)]


def kernel_centroid_score(K, tr, ytr, te):
    """Nearest-centroid discriminant from inner products only, (18.28): ||x0 - xbar_-||^2 - ||x0 - xbar_+||^2."""
    out = []
    for c in (0, 1):
        idx = tr[ytr == c]
        d = np.diag(K)[te] - 2 * K[np.ix_(te, idx)].mean(1) + K[np.ix_(idx, idx)].mean()
        out.append(d)
    return out[0] - out[1]


def kernel_nn_score(K, tr, ytr, te):
    """Distance-weighted one-nearest-neighbour discriminant (18.57): log(d_-(x0) / d_+(x0)), with d_+
    and d_- the distances to the closest training point of each class."""
    D = np.sqrt(np.maximum(kernel_sqdist(K, te, tr), 1e-300))
    dm, dp = D[:, ytr == 0].min(1), D[:, ytr == 1].min(1)
    return np.log(dm) - np.log(dp)


def auc(score, y):
    """Area under the ROC curve = Pr(score of a positive > score of a negative) (ties count one half)."""
    r = stats.rankdata(score)
    n1 = y.sum()
    n0 = len(y) - n1
    return (r[y == 1].sum() - n1 * (n1 + 1) / 2) / (n1 * n0)


def roc_curve(score, y):
    """Sensitivity and specificity for every cut-point on score."""
    order = np.argsort(-score, kind="stable")
    ys = y[order]
    tp = np.r_[0, np.cumsum(ys)]
    fp = np.r_[0, np.cumsum(1 - ys)]
    return tp / ys.sum(), 1 - fp / (len(ys) - ys.sum())


def protein_cv(m=4, seed=185, C=1e6):
    """Figure 18.9: 10-fold cross-validated scores of the maximal-margin SVM, the nearest centroid and
    distance-weighted 1-NN on the spectrum kernel of the simulated proteins. Cached."""
    path = _cache("ch18_protein_%d_%d.npz" % (m, seed))
    if os.path.exists(path):
        z = np.load(path)
        return {k: z[k] for k in z.files}
    from sklearn.svm import SVC
    seqs, y = protein_sim(seed)
    K = string_kernel(seqs, m)
    folds = stratified_folds(y, 10, seed)
    S = {k: np.zeros(len(y)) for k in ("svm", "centroid", "nn")}
    for k in range(10):
        tr, te = np.flatnonzero(folds != k), np.flatnonzero(folds == k)
        svm = SVC(kernel="precomputed", C=C, tol=1e-6).fit(K[np.ix_(tr, tr)], y[tr])
        S["svm"][te] = svm.decision_function(K[np.ix_(te, tr)])
        S["centroid"][te] = kernel_centroid_score(K, tr, y[tr], te)
        S["nn"][te] = kernel_nn_score(K, tr, y[tr], te)
    out = dict(y=y, **S)
    np.savez(path, **out)
    return out


def fig_18_9(out_dir=None):
    """Cross-validated ROC curves for the string-kernel classifiers (Figure 18.9)."""
    import matplotlib.pyplot as plt
    S = protein_cv()
    y = S["y"]
    fig, ax = plt.subplots(figsize=(4.8, 4.6))
    for key, lab, col in (("svm", "SVM", ORANGE), ("centroid", "Nearest centroid", GREEN), ("nn", "One-nearest neighbour", BLUE)):
        se, sp = roc_curve(S[key], y)
        a = auc(S[key], y)
        ax.plot(sp, se, color=col, lw=1.6, label="%s  %.2f" % (lab, a))
        print("  %-22s AUC %.3f" % (lab, a))
    ax.plot([0, 1], [1, 0], color=GREY, lw=0.6, ls=":")
    ax.set_xlabel("Specificity")
    ax.set_ylabel("Sensitivity")
    ax.set_title("ROC curves for the string kernel (m = 4)")
    ax.legend(loc="lower left", frameon=False, fontsize=8.5)
    ax.set_xlim(0, 1.0)
    ax.set_ylim(0, 1.0)
    fig.tight_layout()
    savefig(fig, CH, "fig18-9", out_dir)


def double_centre(B):
    """(I - M) B (I - M) with M = 1 1^T / N, (18.31)."""
    return B - B.mean(0)[None, :] - B.mean(1)[:, None] + B.mean()


def kernel_pca_scores(K, k0=None, ncomp=2):
    """Principal-component scores from an uncentred inner-product matrix (Section 18.5.2): the
    eigen-decomposition (I - M) K (I - M) = U D^2 U^T gives Z = U D; a new point with inner products
    k0 (an n0 x N matrix) is projected by (18.58), z0 = D^{-1} U^T (I - M)(k0 - K 1 / N)."""
    N = K.shape[0]
    Kc = double_centre(K)
    w, U = linalg.eigh(Kc)
    idx = np.argsort(w)[::-1][:ncomp]
    d = np.sqrt(np.maximum(w[idx], 0))
    U = U[:, idx]
    Z = U * d
    if k0 is None:
        return Z
    k0 = np.atleast_2d(k0)
    c = k0 - K.mean(1)[None, :]
    c = c - c.mean(1, keepdims=True)
    return Z, (c @ U) / d


# =========================================================================== 18.6: survival and supervised PCs
def survival_sim(seed=186, N=240, p=7399, p1=40, p2=300, beta=0.8):
    """A simulated stand-in for the lymphoma data of Rosenwald et al. (2002) (not on the book's
    website), built from the latent-variable model of Section 18.6.1: a continuous 'cell type' u ~ N(0, 1)
    drives p1 genes (x_j = a_j u + noise, |a_j| ~ U(0.5, 1), random signs) and the hazard
    (proportional hazards, exp(beta u), baseline median about 8 months); a second factor v ~ N(0, 1),
    unrelated to survival, drives p2 genes with larger loadings U(1.5, 2.5) (it dominates the ordinary
    first principal component); the other genes are N(0, 1) noise. Censoring is uniform on 2-24 months.
    The first 160 patients form the training set and the last 80 the test set."""
    rng = np.random.default_rng(seed)
    u, v = rng.standard_normal(N), rng.standard_normal(N)
    X = rng.standard_normal((N, p))
    a = rng.uniform(0.5, 1.0, p1) * rng.choice([-1, 1], p1)
    b = rng.uniform(1.5, 2.5, p2)
    X[:, :p1] += np.outer(u, a)
    X[:, p1:p1 + p2] += np.outer(v, b)
    T = rng.exponential(1.0, N) / (math.log(2) / 8.0 * np.exp(beta * u))
    C = rng.uniform(2, 24, N)
    time_, event = np.minimum(T, C), (T <= C).astype(int)
    return dict(X=X, time=time_, event=event, u=u, v=v, tr=np.arange(160), te=np.arange(160, N), p1=p1, p2=p2)


def kaplan_meier(time_, event):
    """Kaplan-Meier estimate with Greenwood's standard error: event times t, S(t), se(t)."""
    order = np.argsort(time_, kind="stable")
    t, e = time_[order], event[order]
    ut = np.unique(t[e == 1])
    S, V, s, v = [], [], 1.0, 0.0
    for tt in ut:
        n = np.sum(t >= tt)
        d = np.sum((t == tt) & (e == 1))
        s *= 1 - d / n
        v += d / (n * (n - d)) if n > d else 0.0
        S.append(s)
        V.append(s * s * v)
    return ut, np.array(S), np.sqrt(np.array(V))


def logrank(time_, event, group):
    """Two-sample log-rank test: chi-square statistic (1 df) and p-value."""
    o_e, var = 0.0, 0.0
    for tt in np.unique(time_[event == 1]):
        at = time_ >= tt
        n, n1 = at.sum(), (at & (group == 1)).sum()
        d = np.sum((time_ == tt) & (event == 1))
        d1 = np.sum((time_ == tt) & (event == 1) & (group == 1))
        o_e += d1 - d * n1 / n
        if n > 1:
            var += d * (n1 / n) * (1 - n1 / n) * (n - d) / (n - 1)
    chi2 = o_e ** 2 / var
    return chi2, stats.chi2.sf(chi2, 1)


def cox_scores(X, time_, event):
    """Standardised Cox score statistics of every column at beta = 0 (no tied times): U_j / sqrt(I_j)
    with U_j = sum over deaths of (x_ij - risk-set mean) and I_j = sum over deaths of the risk-set
    variance (the score test of each gene alone)."""
    order = np.argsort(time_, kind="stable")
    Xs, e = X[order], event[order]
    n = np.arange(len(e), 0, -1)[:, None]                     # risk-set sizes
    S1 = np.cumsum(Xs[::-1], 0)[::-1] / n
    S2 = np.cumsum((Xs ** 2)[::-1], 0)[::-1] / n
    d = e == 1
    U = (Xs[d] - S1[d]).sum(0)
    I = (S2[d] - S1[d] ** 2).sum(0)
    return U / np.sqrt(I)


def cox_fit(x, time_, event):
    """Cox proportional-hazards fit with one covariate (no ties) by Newton's method: (beta, LR chi-square,
    p-value). The partial log-likelihood is sum over deaths of beta x_i - log sum over the risk set of
    exp(beta x_l)."""
    order = np.argsort(time_, kind="stable")
    xs, e = x[order], event[order] == 1

    def pl(b):
        eta = b * xs
        m = eta.max()
        w = np.exp(eta - m)
        R0 = np.cumsum(w[::-1])[::-1]
        R1 = np.cumsum((w * xs)[::-1])[::-1]
        R2 = np.cumsum((w * xs * xs)[::-1])[::-1]
        ll = np.sum(eta[e] - m - np.log(R0[e]))
        g = np.sum(xs[e] - R1[e] / R0[e])
        h = -np.sum(R2[e] / R0[e] - (R1[e] / R0[e]) ** 2)
        return ll, g, h

    b = 0.0
    l0 = pl(0.0)[0]
    for _ in range(100):
        ll, g, h = pl(b)
        step = -g / h
        while pl(b + step)[0] < ll - 1e-12 and abs(step) > 1e-12:
            step /= 2
        b += step
        if abs(step) < 1e-12:
            break
    lr = 2 * (pl(b)[0] - l0)
    return b, lr, stats.chi2.sf(lr, 1)


def spc_direction(X, k, scores, sign_ref=None):
    """Leading principal component of the k columns with the largest |score|: (columns, column means,
    loading v, singular value d). The sign of v is fixed by sign_ref(v) > 0 when given."""
    cols = np.argsort(-np.abs(scores), kind="stable")[:k]
    mu = X[:, cols].mean(0)
    U, d, Vt = linalg.svd(X[:, cols] - mu, full_matrices=False)
    v = Vt[0]
    if sign_ref is not None and sign_ref(cols, v) < 0:
        v = -v
    return cols, mu, v, d[0]


SURV_KS = (1, 2, 3, 5, 8, 12, 17, 22, 27, 35, 45, 60, 80, 110, 150, 200, 300, 500, 1000)


def survival_spc(seed=186):
    """Supervised principal components for the simulated survival data (Section 18.6, Algorithm 18.1
    with Cox scores): the number of genes is chosen by 10-fold cross-validation on the training set,
    maximising the likelihood-ratio statistic of a Cox model fitted to the pooled held-out supervised
    PC scores ('pre-validation'); each fold orients its component so that a higher score means a higher
    estimated risk. Returns everything Figures 18.12 and 18.14 need."""
    S = survival_sim(seed)
    X, t, e = S["X"], S["time"], S["event"]
    tr, te = S["tr"], S["te"]
    Xtr, ttr, etr = X[tr], t[tr], e[tr]
    folds = stratified_folds(etr, 10, seed)
    crit = []
    for k in SURV_KS:
        held = np.zeros(len(tr))
        for f in range(10):
            a, b = folds != f, folds == f
            z = cox_scores(Xtr[a], ttr[a], etr[a])
            cols, mu, v, d = spc_direction(Xtr[a], k, z, lambda c, v: np.sum(np.sign(z[c]) * v))
            held[b] = (Xtr[b][:, cols] - mu) @ v
        crit.append(cox_fit(held, ttr, etr)[1])
    kbest = SURV_KS[int(np.argmax(crit))]
    z = cox_scores(Xtr, ttr, etr)
    cols, mu, v, d = spc_direction(Xtr, kbest, z, lambda c, v: np.sum(np.sign(z[c]) * v))
    s_tr = (Xtr[:, cols] - mu) @ v
    s_te = (X[te][:, cols] - mu) @ v
    cutoff = np.sort(np.abs(z))[::-1][kbest - 1]
    # comparison 1: the best single gene, dichotomised at its training mean
    j = int(np.argmax(np.abs(z)))
    g1 = (np.sign(z[j]) * (X[te, j] - Xtr[:, j].mean()) > 0).astype(int)
    # comparison 2: the first principal component of all genes
    mall = Xtr.mean(0)
    _, _, Vt = linalg.svd(Xtr - mall, full_matrices=False)
    v0 = Vt[0] if cox_fit((Xtr - mall) @ Vt[0], ttr, etr)[0] > 0 else -Vt[0]
    pc_te = (X[te] - mall) @ v0
    groups = dict(single=g1, spc=(s_te > 0).astype(int), pc=(pc_te > 0).astype(int))
    tests = {k: logrank(t[te], e[te], g) for k, g in groups.items()}
    return dict(S=S, z=z, ks=np.array(SURV_KS), crit=np.array(crit), kbest=kbest, cols=cols, v=v, s_tr=s_tr, s_te=s_te,
                cutoff=cutoff, best_gene=j, groups=groups, tests=tests, cox_test=cox_fit(s_te, t[te], e[te]),
                cox_test_pc=cox_fit(pc_te, t[te], e[te]), corr_u=np.corrcoef(s_te, S["u"][te])[0, 1],
                corr_u_pc=np.corrcoef(pc_te, S["u"][te])[0, 1], corr_v_pc=np.corrcoef(pc_te, S["v"][te])[0, 1])


def fig_18_12(out_dir=None):
    """Kaplan-Meier estimate for the 80 test patients with one-standard-error curves (Figure 18.12)."""
    import matplotlib.pyplot as plt
    S = survival_sim()
    t, e = S["time"][S["te"]], S["event"][S["te"]]
    ut, s, se = kaplan_meier(t, e)
    fig, ax = plt.subplots(figsize=(5.2, 3.9))
    xs = np.r_[0, ut]
    ax.step(xs, np.r_[1, s], where="post", color=BLUE)
    ax.step(xs, np.r_[1, np.minimum(1, s + se)], where="post", color=BLUE, ls="--", lw=0.9)
    ax.step(xs, np.r_[1, np.maximum(0, s - se)], where="post", color=BLUE, ls="--", lw=0.9)
    cens = t[e == 0]
    sc = np.array([np.r_[1, s][np.searchsorted(ut, c, side="right")] for c in cens])
    ax.plot(cens, sc, "|", color="black", ms=7)
    ax.set_xlabel("Months t")
    ax.set_ylabel(r"$\Pr(T \geq t)$")
    ax.set_ylim(0, 1.02)
    ax.set_title("Survival function (simulated test set, 80 patients)")
    fig.tight_layout()
    savefig(fig, CH, "fig18-12", out_dir)
    print("  test set: %d deaths, %d censored; median survival %.1f months" % (e.sum(), (1 - e).sum(), ut[np.argmax(s <= 0.5)]))


def fig_18_14(out_dir=None):
    """Supervised principal components on the simulated survival data (Figure 18.14)."""
    import matplotlib.pyplot as plt
    from matplotlib.colors import LinearSegmentedColormap
    R = survival_spc()
    S = R["S"]
    X, t, e = S["X"], S["time"], S["event"]
    tr, te = S["tr"], S["te"]
    z = R["z"]
    order = np.argsort(-np.abs(z), kind="stable")
    rows = np.r_[order[:50], order[-50:]]
    colorder = np.argsort(R["s_tr"])
    H = X[tr][:, rows] - X[tr][:, rows].mean(0)
    H = (H / H.std(0) * np.sign(z[rows]))[colorder].T
    cmap = LinearSegmentedColormap.from_list("by", ["#2040ff", "#ffffff", "#e0c000"])
    fig = plt.figure(figsize=(10.0, 7.6))
    ax = fig.add_axes([0.06, 0.08, 0.36, 0.78])
    ax.imshow(np.clip(H, -2.5, 2.5), aspect="auto", cmap=cmap, vmin=-2.5, vmax=2.5, interpolation="nearest")
    ax.axhline(49.5, color="black", lw=2.5)
    ax.axhline(R["kbest"] - 0.5, color=RED, lw=1.2)
    ax.set_yticks([0, R["kbest"] - 1, 49.5, 99])
    ax.set_yticklabels(["1", str(R["kbest"]), "50 | %d" % (len(z) - 49), str(len(z))], fontsize=8)
    ax.set_xticks([0, 79, 159])
    ax.set_xticklabels(["1", "80", "160"], fontsize=8)
    ax.set_xlabel("Patients (ordered by the supervised PC)")
    ax.set_ylabel("Genes (top 50 and bottom 50 by |Cox score|)")
    bar = fig.add_axes([0.06, 0.87, 0.36, 0.03])
    bar.imshow(np.sort(R["s_tr"])[None, :], aspect="auto", cmap=cmap)
    bar.set_xticks([])
    bar.set_yticks([])
    bar.set_title("Supervised PC", fontsize=9)
    ax2 = fig.add_axes([0.44, 0.08, 0.1, 0.78])
    ax2.plot(np.abs(z[rows]), np.arange(100), "o", ms=2.5, color=CYAN)
    ax2.axvline(R["cutoff"], color=RED, ls="--", lw=1)
    ax2.axhline(R["kbest"] - 0.5, color=RED, lw=1.2)
    ax2.axhline(49.5, color="black", lw=2.5)
    ax2.set_ylim(99.5, -0.5)
    ax2.set_yticks([])
    ax2.set_xlabel("|Cox score|", fontsize=9)
    labels = dict(single="Best single gene", spc="Supervised principal component (%d genes)" % R["kbest"],
                  pc="Principal component (all %d genes)" % X.shape[1])
    for i, key in enumerate(("single", "spc", "pc")):
        a = fig.add_axes([0.63, 0.7 - i * 0.305, 0.35, 0.24])
        g = R["groups"][key]
        for val, col, lab in ((0, CYAN, "low score"), (1, ORANGE, "high score")):
            m = g == val
            ut, s, _ = kaplan_meier(t[te][m], e[te][m])
            a.step(np.r_[0, ut], np.r_[1, s], where="post", color=col, label=lab)
        a.set_ylim(0, 1.02)
        a.set_xlim(0, 24)
        a.set_title(labels[key], fontsize=9)
        a.text(0.04, 0.08, "P = %.2g" % R["tests"][key][1], transform=a.transAxes, fontsize=9)
        a.set_ylabel("Prob. of survival", fontsize=8)
        a.tick_params(labelsize=8)
        if i == 0:
            a.legend(frameon=False, fontsize=8, loc="upper right")
        if i == 2:
            a.set_xlabel("Months")
    savefig(fig, CH, "fig18-14", out_dir)
    print("  %d genes chosen by CV (|Cox score| >= %.2f; %d of them in the true set of %d); test Cox LR p = %.2g; log-rank p: single %.2g, SPC %.2g, PC %.2g"
          % (R["kbest"], R["cutoff"], np.sum(R["cols"] < S["p1"]), S["p1"], R["cox_test"][2], R["tests"]["single"][1], R["tests"]["spc"][1], R["tests"]["pc"][1]))
    print("  correlation with the latent u on the test set: SPC %.2f, ordinary PC %.2f (with the nuisance factor v: %.2f)" % (R["corr_u"], R["corr_u_pc"], R["corr_v_pc"]))
    return R


# =========================================================================== the simulation (18.37)
def spc_sim(rng, N=100, p=5000):
    """One data set from model (18.37): genes 1-50 shift by 1 between samples 1-50 and 51-100 and drive
    y = 2 * mean(x_1..x_50) + noise (sd 1.5); genes 51-250 shift by 4 between samples (1-25, 51-75)
    and (26-50, 76-100), unrelated to y; the other genes are N(0, 1) noise."""
    X = rng.standard_normal((N, p))
    i = np.arange(N)
    X[:, :50] += np.where(i < N // 2, 3.0, 4.0)[:, None]
    X[:, 50:250] += np.where((i % (N // 2)) < N // 4, 1.5, 5.5)[:, None]
    y = 2 * X[:, :50].mean(1) + 1.5 * rng.standard_normal(N)
    return X, y


def uni_scores(X, y):
    """Standardised univariate regression coefficients (correlations, up to a common factor)."""
    Xc = X - X.mean(0)
    yc = y - y.mean()
    return Xc.T @ yc / np.sqrt((Xc ** 2).sum(0) * (yc @ yc))


def spc_predict(Xtr, ytr, Xte, k, m=1, scores=None):
    """Supervised principal components (Algorithm 18.1, m components): keep the k columns with the
    largest |univariate score|, take the first m principal components of the centred kept columns,
    regress y on them by least squares; returns (fitted values, test predictions)."""
    s = uni_scores(Xtr, ytr) if scores is None else scores
    cols = np.argsort(-np.abs(s), kind="stable")[:k]
    mu = Xtr[:, cols].mean(0)
    U, d, Vt = linalg.svd(Xtr[:, cols] - mu, full_matrices=False)
    Z = U[:, :m] * d[:m]
    Z0 = (Xte[:, cols] - mu) @ Vt[:m].T
    g = Z.T @ (ytr - ytr.mean()) / (d[:m] ** 2)
    return ytr.mean() + Z @ g, ytr.mean() + Z0 @ g


def tpls_predict(Xtr, ytr, Xte, k, scores=None):
    """Thresholded PLS (one component): the same k columns, standardised, the first PLS variate
    z = sum_j <y, x_j> x_j (18.34), and the least-squares regression of y on z."""
    s = uni_scores(Xtr, ytr) if scores is None else scores
    cols = np.argsort(-np.abs(s), kind="stable")[:k]
    mu, sd = Xtr[:, cols].mean(0), Xtr[:, cols].std(0)
    Z = (Xtr[:, cols] - mu) / sd
    Z0 = (Xte[:, cols] - mu) / sd
    yc = ytr - ytr.mean()
    w = Z.T @ yc
    z, z0 = Z @ w, Z0 @ w
    g = z @ yc / (z @ z)
    return ytr.mean() + g * z, ytr.mean() + g * z0


SPC_KS = (1, 2, 5, 10, 15, 20, 25, 30, 40, 50, 60, 75, 100, 125, 150, 175, 200, 225, 250, 275, 300, 5000)


def spc_study(nsim=100, seed=1816):
    """Figure 18.16: relative root-mean-square test error of supervised PCs and thresholded PLS (one
    component) against the number of kept features, over nsim realisations of (18.37), each with an
    independent test set of the same design. Cached."""
    path = _cache("ch18_spc_study_%d_%d.npz" % (nsim, seed))
    if os.path.exists(path):
        z = np.load(path)
        return {k: z[k] for k in z.files}
    rng = np.random.default_rng(seed)
    E = np.zeros((2, nsim, len(SPC_KS)))
    for r in range(nsim):
        X, y = spc_sim(rng)
        Xt, yt = spc_sim(rng)
        s = uni_scores(X, y)
        for a, k in enumerate(SPC_KS):
            E[0, r, a] = np.sqrt(np.mean((spc_predict(X, y, Xt, k, scores=s)[1] - yt) ** 2)) / 1.5
            E[1, r, a] = np.sqrt(np.mean((tpls_predict(X, y, Xt, k, scores=s)[1] - yt) ** 2)) / 1.5
    out = dict(ks=np.array(SPC_KS), err=E)
    np.savez(path, **out)
    return out


def fig_18_15(out_dir=None):
    """Heat map of the outcome and the first 500 genes of one realisation of (18.37) (Figure 18.15)."""
    import matplotlib.pyplot as plt
    rng = np.random.default_rng(1815)
    X, y = spc_sim(rng)
    fig = plt.figure(figsize=(8.0, 4.4))
    a0 = fig.add_axes([0.06, 0.1, 0.035, 0.82])
    a0.imshow(((y - y.mean()) / y.std())[:, None], aspect="auto", cmap="RdBu_r", vmin=-2.5, vmax=2.5, interpolation="nearest")
    a0.set_xticks([0])
    a0.set_xticklabels(["y"])
    a0.set_ylabel("Samples")
    a1 = fig.add_axes([0.11, 0.1, 0.86, 0.82])
    Z = (X[:, :500] - X[:, :500].mean(0)) / X[:, :500].std(0)
    a1.imshow(Z, aspect="auto", cmap="RdBu_r", vmin=-2.5, vmax=2.5, interpolation="nearest")
    a1.set_yticks([])
    a1.set_xlabel("Genes 1-500 (genes 1-50 drive y; genes 51-250 carry a large effect unrelated to y)")
    savefig(fig, CH, "fig18-15", out_dir)


def fig_18_16(out_dir=None):
    """Relative RMS test error of supervised PCs and thresholded PLS against the number of features
    (Figure 18.16)."""
    import matplotlib.pyplot as plt
    S = spc_study()
    ks, E = S["ks"], S["err"]
    xpos = np.where(ks == 5000, 340, ks).astype(float)
    fig, ax = plt.subplots(figsize=(6.4, 4.0))
    for i, (lab, col) in enumerate((("Supervised principal components", ORANGE), ("Thresholded PLS", BLUE))):
        m = E[i].mean(0)
        se = E[i].std(0, ddof=1) / math.sqrt(E.shape[1])
        main = ks != 5000
        ax.errorbar(xpos[main], m[main], yerr=se[main], color=col, marker="o", ms=3, lw=1.2, capsize=2, label=lab)
        ax.errorbar(xpos[~main], m[~main], yerr=se[~main], color=col, marker="o", ms=4, lw=0, elinewidth=1.2, capsize=2)
        j = int(np.argmin(m))
        print("  %s: minimum %.3f at %d features; %.3f with all 5000 (%s)" % (lab, m[j], ks[j], m[-1], "PC regression" if i == 0 else "PLS"))
    ax.set_xticks([0, 50, 100, 150, 200, 250, 300, 340])
    ax.set_xticklabels(["0", "50", "100", "150", "200", "250", "300", "5000"])
    ax.axvline(320, color=GREY, lw=0.6, ls=":")
    ax.set_xlabel("Number of features")
    ax.set_ylabel("Relative root mean square test error")
    ax.legend(frameon=False, loc="upper center")
    fig.tight_layout()
    savefig(fig, CH, "fig18-16", out_dir)


def precondition_example(seed=1817):
    """Figure 18.17: one realisation of (18.37); test MSE of the lasso, supervised PCs and the
    pre-conditioned lasso (the lasso applied to the supervised-PC fitted values, the number of genes of
    the supervised PC chosen by 10-fold CV), indexed by the number of features in the model."""
    from sklearn.linear_model import lars_path
    rng = np.random.default_rng(seed)
    X, y = spc_sim(rng)
    Xt, yt = spc_sim(rng)
    s = uni_scores(X, y)
    ks = np.arange(1, 251)
    spc = np.array([np.mean((spc_predict(X, y, Xt, k, scores=s)[1] - yt) ** 2) for k in ks])
    folds = np.arange(len(y)) % 10
    rng.shuffle(folds)
    grid = np.array([5, 10, 15, 20, 25, 30, 40, 50, 60, 75, 100, 150, 200, 250])
    cv = np.zeros(len(grid))
    for f in range(10):
        a, b = folds != f, folds == f
        sf = uni_scores(X[a], y[a])
        for i, k in enumerate(grid):
            cv[i] += np.sum((spc_predict(X[a], y[a], X[b], k, scores=sf)[1] - y[b]) ** 2)
    kcv = int(grid[np.argmin(cv)])
    yhat = spc_predict(X, y, X, kcv, scores=s)[0]

    def lasso_curve(target):
        xm, tm = X.mean(0), target.mean()
        _, _, coefs = lars_path(X - xm, target - tm, method="lasso")
        nz = (coefs != 0).sum(0)
        err = np.array([np.mean((tm + (Xt - xm) @ c - yt) ** 2) for c in coefs.T])
        # one model per size: the last (least penalised) knot with that many non-zero coefficients
        last = {int(k): i for i, k in enumerate(nz)}
        keep = np.array([last[k] for k in sorted(last)])
        return nz[keep], err[keep]

    nz_l, err_l = lasso_curve(y)
    nz_p, err_p = lasso_curve(yhat)
    return dict(ks=ks, spc=spc, kcv=kcv, nz_l=nz_l, err_l=err_l, nz_p=nz_p, err_p=err_p)


def fig_18_17(out_dir=None):
    """Test error of the lasso, supervised PCs and the pre-conditioned lasso (Figure 18.17)."""
    import matplotlib.pyplot as plt
    R = precondition_example()
    fig, ax = plt.subplots(figsize=(6.4, 4.0))
    ax.plot(R["nz_l"], R["err_l"], color=GREEN, lw=1.3, label="Lasso")
    ax.plot(R["ks"], R["spc"], color=ORANGE, lw=1.3, label="Supervised principal components")
    ax.plot(R["nz_p"], R["err_p"], color=PURPLE, lw=1.3, label="Pre-conditioned lasso")
    ax.set_xlim(0, 250)
    ax.set_xlabel("Number of features in model")
    ax.set_ylabel("Mean test error")
    ax.legend(frameon=False)
    fig.tight_layout()
    savefig(fig, CH, "fig18-17", out_dir)
    print("  lasso: min %.2f at %d features (path reaches %d); SPC: min %.2f at %d; CV chose %d genes; pre-conditioned lasso: min %.2f at %d"
          % (R["err_l"].min(), R["nz_l"][np.argmin(R["err_l"])], R["nz_l"].max(), R["spc"].min(), R["ks"][np.argmin(R["spc"])], R["kcv"],
             R["err_p"].min(), R["nz_p"][np.argmin(R["err_p"])]))
    return R


# =========================================================================== 18.7: multiple testing
def tstats(X, g):
    """Two-sample t-statistics (18.38)-(18.39) for every row of X (genes in rows); group 2 minus group 1."""
    a, b = X[:, g == 1], X[:, g == 2]
    n1, n2 = a.shape[1], b.shape[1]
    s2 = (((a - a.mean(1, keepdims=True)) ** 2).sum(1) + ((b - b.mean(1, keepdims=True)) ** 2).sum(1)) / (n1 + n2 - 2)
    return (b.mean(1) - a.mean(1)) / np.sqrt(s2 * (1 / n1 + 1 / n2))


HIST_EDGES = np.linspace(-10, 10, 200001)


def radsens_permutations(K=1000, seed=1807):
    """t-statistics of the radiation-sensitivity data and K random permutations of the labels. Kept:
    the number of permuted |t| (over all genes and permutations) exceeding each observed |t_j| (exact,
    for (18.41) and Algorithm 18.3), the per-gene counts for (18.40), a fine histogram of the permuted
    t-values, and the average of the sorted permuted t-values (the SAM expected order statistics). Cached."""
    path = _cache("ch18_radsens_perm_%d_%d.npz" % (K, seed))
    if os.path.exists(path):
        z = np.load(path)
        return {k: z[k] for k in z.files}
    X, g = radsens()
    t = tstats(X, g)
    at = np.abs(t)
    order = np.argsort(at)
    sorted_at = at[order]
    n, n2 = len(g), int(np.sum(g == 2))
    S, SS = X.sum(1), (X ** 2).sum(1)
    rng = np.random.default_rng(seed)
    pooled = np.zeros(len(t), dtype=np.int64)        # #{(j', k): |t^k_j'| > |t_j|}
    own = np.zeros(len(t), dtype=np.int64)           # #{k: |t^k_j| > |t_j|}
    hist = np.zeros(len(HIST_EDGES) - 1, dtype=np.int64)
    sum_sorted = np.zeros(len(t))
    for _ in range(K):
        idx = rng.permutation(n)[:n2]
        sb, ssb = X[:, idx].sum(1), (X[:, idx] ** 2).sum(1)
        sa, ssa = S - sb, SS - ssb
        n1 = n - n2
        ma, mb = sa / n1, sb / n2
        s2 = (ssa - n1 * ma ** 2 + ssb - n2 * mb ** 2) / (n - 2)
        tk = (mb - ma) / np.sqrt(s2 * (1 / n1 + 1 / n2))
        ak = np.sort(np.abs(tk))
        pooled += len(ak) - np.searchsorted(ak, at, side="right")
        own += np.abs(tk) > at
        hist += np.histogram(tk, HIST_EDGES)[0]
        sum_sorted += np.sort(tk)
    out = dict(t=t, pooled=pooled, own=own, hist=hist, exp_order=sum_sorted / K, K=np.array(K))
    np.savez(path, **out)
    return out


def bh(p, alpha):
    """Benjamini-Hochberg, Algorithm 18.2: L = max{j : p_(j) < alpha j / M} (0 if none); reject the L
    hypotheses with the smallest p-values. Returns (L, boolean rejections)."""
    M = len(p)
    ps = np.sort(p)
    ok = np.flatnonzero(ps < alpha * np.arange(1, M + 1) / M)
    L = int(ok[-1] + 1) if len(ok) else 0
    rej = np.zeros(M, dtype=bool)
    if L:
        rej[np.argsort(p, kind="stable")[:L]] = True
    return L, rej


def plugin_fdr(P, C):
    """Algorithm 18.3 at cut-point C on |t| (C an observed |t| value or not): E(V) estimated by the
    average number of permuted |t| above C, divided by the observed number above C. Exact at
    observed values (from the pooled counts), from the fine histogram otherwise."""
    at = np.abs(P["t"])
    R = int(np.sum(at > C))
    if R == 0:
        return np.nan, 0, 0.0
    hit = np.flatnonzero(np.isclose(at, C, rtol=0, atol=1e-12))
    if len(hit):
        ev = P["pooled"][hit[0]] / float(P["K"])
    else:
        c = (HIST_EDGES[:-1] + HIST_EDGES[1:]) / 2
        ev = P["hist"][np.abs(c) > C].sum() / float(P["K"])
    return ev / R, R, ev


def fig_18_18(out_dir=None):
    """Histogram of the 12,625 t-statistics and of the permutation t-statistics (Figure 18.18)."""
    import matplotlib.pyplot as plt
    P = radsens_permutations()
    t, K = P["t"], int(P["K"])
    edges = np.linspace(-5.5, 5.5, 45)
    fig, ax = plt.subplots(figsize=(5.6, 4.0))
    ax.hist(t, edges, color=ORANGE, alpha=0.75, label="observed")
    fine_c = (HIST_EDGES[:-1] + HIST_EDGES[1:]) / 2
    ph = np.histogram(fine_c, edges, weights=P["hist"])[0] / K
    ax.step(edges, np.r_[ph, ph[-1]], where="post", color=BLUE, lw=1.6, label="permutations (per permutation)")
    ax.set_xlabel("t-statistics")
    ax.set_ylabel("Count")
    ax.legend(frameon=False, fontsize=8.5)
    fig.tight_layout()
    savefig(fig, CH, "fig18-18", out_dir)
    M = len(t)
    print("  t from %.2f to %.2f; %d with |t| >= 2 (binomial mean %.1f, sd %.1f); permutation: %.1f per permutation with |t| >= 2"
          % (t.min(), t.max(), np.sum(np.abs(t) >= 2), M * 0.05, math.sqrt(M * 0.05 * 0.95), P["hist"][np.abs(fine_c) >= 2].sum() / K))


def radsens_pvalues(P=None):
    """Pooled permutation p-values (18.41) and per-gene ones (18.40)."""
    P = radsens_permutations() if P is None else P
    M, K = len(P["t"]), float(P["K"])
    return P["pooled"] / (M * K), P["own"] / K


def fig_18_19(out_dir=None, alpha=0.15):
    """Ordered p-values and the Benjamini-Hochberg line (Figure 18.19)."""
    import matplotlib.pyplot as plt
    P = radsens_permutations()
    p, _ = radsens_pvalues(P)
    M = len(p)
    L, rej = bh(p, alpha)
    ps = np.sort(p)
    j = np.arange(1, 101)
    fig, ax = plt.subplots(figsize=(5.4, 4.2))
    ax.loglog(j, np.maximum(ps[:100], 1e-7), "o", ms=3.5, color="black", mfc="none")
    ax.loglog(j[:L], np.maximum(ps[:L], 1e-7), "o", ms=4, color=RED)
    ax.loglog(j, alpha * j / M, color=BLUE, lw=1.2, label=r"$\alpha\, j/M$, $\alpha = %.2f$" % alpha)
    ax.axvline(L, color=GREY, lw=0.8)
    ax.set_xlabel("Genes ordered by p-value")
    ax.set_ylabel("p-value")
    ax.legend(frameon=False, loc="upper left")
    fig.tight_layout()
    savefig(fig, CH, "fig18-19", out_dir)
    C = np.sort(np.abs(P["t"]))[::-1][L - 1]
    fdr, R, ev = plugin_fdr(P, C - 1e-9)
    print("  BH at alpha = %.2f rejects L = %d genes (p_(L) = %.2e, |t| >= %.3f); plug-in at that cut: %.0f permuted values above it, E(V) = %.3f, FDR-hat = %.3f"
          % (alpha, L, ps[L - 1], C, ev * float(P["K"]), ev, fdr))
    return L


def sam_cutpoints(t, texp, delta):
    """SAM, Section 18.7.2: with t_(1) <= ... <= t_(M) and the expected order statistics texp, the upper
    cut-point is the first place, moving right from the origin, where t_(j) - texp_(j) > delta, and
    every gene from there on is called; likewise to the left. Returns (C_low, C_hi, called mask in
    sorted order)."""
    ts = np.sort(t)
    M = len(ts)
    called = np.zeros(M, dtype=bool)
    up = np.flatnonzero((texp > 0) & (ts - texp > delta))
    lo = np.flatnonzero((texp < 0) & (texp - ts > delta))
    c_hi, c_lo = np.inf, -np.inf
    if len(up):
        called[up[0]:] = True
        c_hi = ts[up[0]]
    if len(lo):
        called[:lo[-1] + 1] = True
        c_lo = ts[lo[-1]]
    return c_lo, c_hi, called


def fig_18_20(out_dir=None, delta=0.71):
    """The SAM plot for the radiation-sensitivity data (Figure 18.20)."""
    import matplotlib.pyplot as plt
    P = radsens_permutations()
    t, texp = P["t"], P["exp_order"]
    ts = np.sort(t)
    c_lo, c_hi, called = sam_cutpoints(t, texp, delta)
    fig, ax = plt.subplots(figsize=(5.0, 4.8))
    ax.plot(texp[~called], ts[~called], ".", ms=2, color=BLUE)
    ax.plot(texp[called], ts[called], ".", ms=5, color=RED)
    lim = [-5.5, 5.5]
    ax.plot(lim, lim, color="black", lw=0.8)
    ax.plot(lim, [lim[0] + delta, lim[1] + delta], color=GREY, lw=0.6)
    ax.plot(lim, [lim[0] - delta, lim[1] - delta], color=GREY, lw=0.6)
    if np.isfinite(c_hi):
        ax.axhline(c_hi, color=GREY, ls="--", lw=0.8)
        ax.text(-0.3, c_hi + 0.15, r"$C_{hi}$", fontsize=10)
    ax.set_xlim(lim)
    ax.set_ylim(lim)
    ax.set_xlabel("Expected order statistics")
    ax.set_ylabel("t-statistic")
    fig.tight_layout()
    savefig(fig, CH, "fig18-20", out_dir)
    K = float(P["K"])
    c = (HIST_EDGES[:-1] + HIST_EDGES[1:]) / 2
    ev = (P["hist"][(c >= c_hi) | (c <= c_lo)]).sum() / K
    print("  Delta = %.2f: %d genes called (upper %d, lower %d); C_hi = %.3f, C_low = %s; plug-in FDR %.3f"
          % (delta, called.sum(), np.sum(called & (ts > 0)), np.sum(called & (ts < 0)), c_hi, "%.3f" % c_lo if np.isfinite(c_lo) else "-inf",
             ev / max(called.sum(), 1)))





# =========================================================================== exercises
def max_data_piling(X, y):
    """Exercise 18.8: the least-squares fit of y in {-1, +1} with an intercept and the minimum-norm
    slope beta0 = X_c^+ y_c (X_c centred); returns beta0 and the projections X beta0 (two values)."""
    xm = X.mean(0)
    b = np.linalg.pinv(X - xm) @ (y - y.mean())
    return b, (X - xm) @ b


def exercise_18_9(nsim=50, N=20, p=200, shift=0.3, seed=189):
    """Exercise 18.9: maximal data piling against the optimal separating hyperplane on two Gaussian
    classes (N/2 each, identity covariance, mean shift `shift` in every coordinate), p >> N. Returns,
    per simulation, the gap between the two piles along the data-piling direction (2 / ||beta0||), the
    SVM margin width (2 / ||w||), and the test errors of both rules (cut halfway between the classes)."""
    from sklearn.svm import SVC
    rng = np.random.default_rng(seed)
    out = []
    for _ in range(nsim):
        y = np.r_[-np.ones(N // 2), np.ones(N // 2)]
        X = rng.standard_normal((N, p)) + shift * (y[:, None] > 0)
        yt = np.r_[-np.ones(500), np.ones(500)]
        Xt = rng.standard_normal((1000, p)) + shift * (yt[:, None] > 0)
        b, proj = max_data_piling(X, y)
        cut = 0.5 * (proj[y > 0].mean() + proj[y < 0].mean())
        e_mdp = np.mean(np.sign((Xt - X.mean(0)) @ b - cut) != yt)
        svm = SVC(kernel="linear", C=1e4, tol=1e-6).fit(X, y)          # hard margin: all dual weights stay below C
        w = svm.coef_[0]
        e_svm = np.mean(np.sign(svm.decision_function(Xt)) != yt)
        out.append((2 / np.linalg.norm(b), 2 / np.linalg.norm(w), e_mdp, e_svm, np.ptp(proj[y > 0]) + np.ptp(proj[y < 0])))
    return np.array(out)



def exercise_18_9_table(ps=(22, 30, 50, 200), shift=0.5):
    """Exercise 18.9 for several p (N = 20): mean data-piling gap, mean SVM margin width, the range of
    their ratio, and the mean test errors."""
    rows = []
    for p in ps:
        E = exercise_18_9(p=p, shift=shift)
        r = E[:, 1] / E[:, 0]
        rows.append((p, E[:, 0].mean(), E[:, 1].mean(), r.min(), r.max(), E[:, 2].mean(), E[:, 3].mean()))
    return rows

def exercise_18_19(cuts=(2.0, 2.5, 3.0, 3.5, 4.0, 4.5), alphas=(0.05, 0.10, 0.15, 0.20, 0.25, 0.30)):
    """Exercise 18.19 on the radiation-sensitivity data: (a) the plug-in FDR at several cut-points,
    (b) BH at several levels with the pooled permutation p-values, and the equivalence: L_BH equals the
    largest j whose plug-in estimate at the cut-point |t|_(j) is below alpha, (c) pi0 from the
    quartiles of the permuted t-values, and the rescaled estimates."""
    P = radsens_permutations()
    t, M, K = P["t"], len(P["t"]), float(P["K"])
    at_sorted = np.sort(np.abs(t))[::-1]
    p, _ = radsens_pvalues(P)
    rows_a = []
    for C in cuts:
        fdr, R, ev = plugin_fdr(P, C)
        rows_a.append((C, R, ev, fdr))
    # plug-in FDR at the cut-point equal to the j-th largest |t| (|t| >= that value)
    order = np.argsort(-np.abs(t), kind="stable")
    fdr_j = P["pooled"][order] / K / np.arange(1, M + 1)
    rows_b = []
    for a in alphas:
        L, _ = bh(p, a)
        ok = np.flatnonzero(fdr_j < a)
        rows_b.append((a, L, int(ok[-1] + 1) if len(ok) else 0))
    c = (HIST_EDGES[:-1] + HIST_EDGES[1:]) / 2
    cum = np.cumsum(P["hist"]) / P["hist"].sum()
    q25, q75 = c[np.searchsorted(cum, 0.25)], c[np.searchsorted(cum, 0.75)]
    pi0 = min(np.sum((t > q25) & (t < q75)) / (0.5 * M), 1.0)
    return dict(a=rows_a, b=rows_b, q25=q25, q75=q75, pi0=pi0)


# =========================================================================== the demonstrations
KHAN_SCALE = 1000.0


def export_khan_json():
    """../data/ch18-khan.json for shrunken-centroids-demo.html: the SRBCT training and test matrices
    rounded to 0.001 and stored as little-endian int16 in base64 (samples in rows), the classes and the
    10 cross-validation folds of Figure 18.4."""
    Xtr, gtr, Xte, gte = khan()
    q = lambda A: base64.b64encode(np.round(A * KHAN_SCALE).astype("<i2").tobytes()).decode("ascii")
    out = dict(p=int(Xtr.shape[1]), ntr=int(len(gtr)), nte=int(len(gte)), scale=KHAN_SCALE, classes=SRBCT,
               gtr=gtr.tolist(), gte=gte.tolist(), folds=stratified_folds(gtr, 10, KHAN_FOLD_SEED).tolist(),
               xtr=q(Xtr), xte=q(Xte))
    os.makedirs(DATA_OUT, exist_ok=True)
    path = os.path.join(DATA_OUT, "ch18-khan.json")
    with open(path, "w") as f:
        json.dump(out, f, separators=(",", ":"))
    print("wrote", os.path.relpath(path, os.getcwd()), "(%.0f kB)" % (os.path.getsize(path) / 1024))
    return path


def khan_quantised():
    """The SRBCT data exactly as the demo reads them (rounded to 0.001)."""
    Xtr, gtr, Xte, gte = khan()
    return np.round(Xtr * KHAN_SCALE) / KHAN_SCALE, gtr, np.round(Xte * KHAN_SCALE) / KHAN_SCALE, gte


def demo_nsc(delta, hard=False, s0="median"):
    """What shrunken-centroids-demo.html shows at one setting: training and test errors, genes kept,
    the test posteriors (18.8), and the 10-fold CV error curve on the grid KHAN_DELTAS."""
    Xtr, gtr, Xte, gte = khan_quantised()
    m = NSC().fit(Xtr, gtr, s0=s0)
    folds = stratified_folds(gtr, 10, KHAN_FOLD_SEED)
    return dict(train=int(np.sum(m.predict(Xtr, delta, hard) != gtr)), test=int(np.sum(m.predict(Xte, delta, hard) != gte)),
                genes=m.n_genes(delta, hard), post=m.posterior(Xte, delta, hard), cv=nsc_cv(Xtr, gtr, KHAN_DELTAS, folds, hard, s0))


def demo_ridge_data(seed, p, N=100):
    """The data set of ridge-svd-demo.html: one DK.rng(seed) stream gives beta (p normals), then for each
    row the shared normal w_i followed by z_i1..z_ip, then the N noise values; model (18.1) with
    pairwise correlation 0.2 and signal-to-noise ratio 2."""
    z = js_normals(seed, p + N * (p + 1) + N)
    beta = z[:p]
    M = z[p:p + N * (p + 1)].reshape(N, p + 1)
    X = math.sqrt(1 - RHO) * M[:, 1:] + math.sqrt(RHO) * M[:, :1]
    s2 = ((1 - RHO) * beta @ beta + RHO * beta.sum() ** 2) / 2
    y = X @ beta + math.sqrt(s2) * z[p + N * (p + 1):]
    return X, y, beta, s2


DEMO_RIDGE_LAMS = 10.0 ** np.linspace(-3, 5, 81)


def demo_ridge(seed, p, lam):
    """Ridge on the demo's data at lam, and the curve over DEMO_RIDGE_LAMS: coefficients, effective
    df, relative test error, and the Bayes risk."""
    X, y, beta, s2 = demo_ridge_data(seed, p)
    B, b0, df = ridge_svd(X, y, [lam])
    Bc, _, dfc = ridge_svd(X, y, DEMO_RIDGE_LAMS)
    return dict(beta=B[0], b0=b0[0], df=df[0], err=rel_test_error(B[0], beta, s2), bayes=bayes_rel_error(X, p),
                curve_df=dfc, curve_err=np.array([rel_test_error(b, beta, s2) for b in Bc]))


def demo_spc_data(seed, N=100, p=5000):
    """The data of supervised-pc-demo.html: one DK.rng(seed) stream gives the training inputs (row by
    row), the training noise, the test inputs and the test noise of model (18.37)."""
    z = js_normals(seed, 2 * (N * p + N))
    i = np.arange(N)
    shift = np.zeros((N, p))
    shift[:, :50] = np.where(i < N // 2, 3.0, 4.0)[:, None]
    shift[:, 50:250] = np.where((i % (N // 2)) < N // 4, 1.5, 5.5)[:, None]
    X = z[:N * p].reshape(N, p) + shift
    y = 2 * X[:, :50].mean(1) + 1.5 * z[N * p:N * p + N]
    o = N * p + N
    Xt = z[o:o + N * p].reshape(N, p) + shift
    yt = 2 * Xt[:, :50].mean(1) + 1.5 * z[o + N * p:]
    return X, y, Xt, yt


def demo_spc(seed, k, m=1):
    """Relative RMS test errors of supervised PCs (m components) and thresholded PLS at k features on
    the demo's data, and the supervised-PC curve over SPC_KS."""
    X, y, Xt, yt = demo_spc_data(seed)
    s = uni_scores(X, y)
    r = lambda pred: math.sqrt(np.mean((pred - yt) ** 2)) / 1.5
    return dict(spc=r(spc_predict(X, y, Xt, k, m, scores=s)[1]), tpls=r(tpls_predict(X, y, Xt, k, scores=s)[1]),
                curve_spc=np.array([r(spc_predict(X, y, Xt, kk, m, scores=s)[1]) for kk in SPC_KS]),
                curve_tpls=np.array([r(tpls_predict(X, y, Xt, kk, scores=s)[1]) for kk in SPC_KS]),
                signal_kept=int(np.sum(np.argsort(-np.abs(s), kind="stable")[:k] < 50)))


FIGURES = {
    "18.1": fig_18_1, "18.2": fig_18_2, "18.3": fig_18_3, "18.4": fig_18_4, "18.5": fig_18_5, "18.6": fig_18_6,
    "18.8": fig_18_8, "18.9": fig_18_9, "18.12": fig_18_12, "18.14": fig_18_14, "18.15": fig_18_15,
    "18.16": fig_18_16, "18.17": fig_18_17, "18.18": fig_18_18, "18.19": fig_18_19, "18.20": fig_18_20,
}


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