"""Hastie, Tibshirani and Friedman (2009), Chapter 3: Linear Methods for Regression.

Reproduces the figures and tables of Chapter 3 of T. Hastie, R. Tibshirani and J. Friedman, The
Elements of Statistical Learning, 2nd edition (Springer, 2009), pp. 43-99, written from scratch with
numpy, scipy and matplotlib. Every method is a small function meant to be read next to the lecture
notes (../ch03-linear-regression.html):

* Section 3.2, least squares: ols_fit (coefficients, standard errors, Z-scores (3.12), sigma-hat^2),
  f_test (3.13), gram_schmidt (Algorithm 3.1, regression by successive orthogonalisation, giving the
  QR decomposition (3.31) and the coefficients by back-substitution, Exercise 3.4).
* Section 3.3, subset selection: all_subsets (every one of the 2^p models, Figure 3.5),
  forward_stepwise (QR updating, Exercise 3.9), backward_stepwise (drop the smallest |Z|, Exercise
  3.10), forward_stagewise (Section 3.3.3), best_subset_leaps (the leaps-and-bounds search of R's leaps
  package, used only for the 31-variable simulation of Figure 3.6).
* Section 3.4, shrinkage: ridge_svd and ridge_df ((3.44), (3.47), (3.50)), lam_for_df, lasso_cd
  (pathwise coordinate descent, (3.84)), lars (Algorithm 3.2 least angle regression with the
  lasso modification 3.2a and the FS0 modification 3.2b, exact step lengths of Exercise 3.25),
  lasso_at_s (the lasso at a given shrinkage factor s = t / sum |beta_j^ls|).
* Section 3.5, derived inputs: pcr (3.61)-(3.62) and pls (Algorithm 3.3, with the coefficients
  recovered from the sequence of transformations).
* Section 3.8: incremental_fs (Algorithm 3.4), scad_penalty (3.82), group_lasso_bcd (3.80),
  dantzig (3.78 as a linear programme).
* cross_validate: K-fold cross-validation with the one-standard-error rule (Figure 3.7).
* Exercises with computation: band_simulation (Exercise 3.2) and spam_table (Exercise 3.17);
  `--fig tables` prints Tables 3.1-3.3 and these results, and writes the demonstrations' data.

The prostate cancer data (Stamey et al. 1989) are read from the book's website. As in the book, the
eight predictors are standardised to unit variance (with the mean and standard deviation of all 97
men), the model is fitted to the 67 training cases and assessed on the 30 test cases. This reproduces
Tables 3.1-3.3 to the printed digits (see the notes for the few exceptions).

Figures reproduced: 3.1-3.20 and the panel of Table 3.4 (saved as tab3-4). Figures 3.2 and 3.4 are
geometric pictures, drawn here from explicitly computed vectors and projections. Run
`python3 ch03_linear_regression.py --list`, `python3 ch03_linear_regression.py` (all figures, about
five minutes; the simulations of Figures 3.6 and 3.16 are cached in cache/) or
`python3 ch03_linear_regression.py --fig 3.8 3.10`. Files go to ../img/ch03/.

Settings chosen where the book gives none:
* Figure 3.1: N = 60 points, X uniform on [0, 1]^2, Y = 1 + 2 X1 + 1.5 X2 + N(0, 0.35^2) noise.
* Figures 3.2 and 3.4: x1 = (1, 0.15, 0), x2 = (0.4, 1, 0.1), y = (0.8, 0.6, 1.0) in R^3.
* Figure 3.6: equicorrelated Gaussian inputs, X = sqrt(0.15) Z + sqrt(0.85) w 1^T, ten coefficients
  N(0, 0.4) at random positions, noise variance 6.25, 50 replicates (numpy seed 2009 + replicate).
  The vertical axis is the model error E[(beta_hat - beta)^T Sigma (beta_hat - beta)], i.e. the mean
  squared error of the fitted regression function at a new input: with the stated settings this is the
  only reading of the book's axis that matches its values (see the notes).
* Figure 3.7: tenfold cross-validation on the training set with folds from numpy seed 13 (the one-SE choices vary with the folds; seed 13 gives the most common choice for each method over seeds 1-20); the lasso
  is evaluated at s = 0, 1/8, ..., 1 and ridge at df = 0, 1, ..., 8.
* Figure 3.19: steps of eps = 0.01 on the scale of the standardised predictors (unit variance).
* Figure 3.9: 200 points from a bivariate Gaussian with standard deviations 2 and 0.6 along axes
  rotated by 35 degrees.
* Figures 3.14 and 3.15: N = 60, six Gaussian inputs with a random correlation matrix
  (lars_sim_data, numpy seed 28), standardised to mean 0 and variance 1; the absolute correlations
  are |<x_j, r>| / N. The seed was chosen so that a coefficient passes through zero, as in the book.
* Figure 3.16: as Figure 3.6 with N = 100.
* Figure 3.18: the population version, X^T X = [[1, rho], [rho, 1]] and X^T y = X^T X beta with
  beta = (4, 2), so that least squares is exactly (4, 2).
"""
import itertools
import json
import os
import subprocess
import tempfile

import numpy as np
from scipy import stats
from scipy.optimize import brentq, linprog, nnls

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

CH = 3
HERE = os.path.dirname(os.path.abspath(__file__))
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
CACHE_DIR = os.path.join(HERE, "cache")
NAMES = ["lcavol", "lweight", "age", "lbph", "svi", "lcp", "gleason", "pgg45"]
PCOL = [RED, BLUE, GREEN, ORANGE, PURPLE, CYAN, MAGENTA, "#8c564b"]
RSCRIPT = "/usr/local/bin/Rscript"


# =========================================================================== the prostate data
def load_prostate():
    """The prostate cancer data, standardised as in the book.

    Returns a dict with Z (97 x 8 predictors scaled to mean 0 and standard deviation 1 over all 97
    men), y (lpsa), train (boolean mask of the 67 training cases) and the training quantities
    Xtr, ytr, Xte, yte."""
    df = common.esl_data("prostate.data")
    X = df[NAMES].values.astype(float)
    y = df["lpsa"].values.astype(float)
    tr = (df["train"] == "T").values
    Z = (X - X.mean(0)) / X.std(0, ddof=1)
    return dict(X=X, Z=Z, y=y, train=tr, Xtr=Z[tr], ytr=y[tr], Xte=Z[~tr], yte=y[~tr])


def centred(Xtr, ytr):
    """Centre the training inputs and output: returns Xc, yc, xbar, ybar (Exercise 3.5)."""
    xm, ym = Xtr.mean(0), ytr.mean()
    return Xtr - xm, ytr - ym, xm, ym


def test_error(beta, Xtr, ytr, Xte, yte):
    """Intercept from the centred fit (beta0 = ybar - xbar^T beta), test mean squared error and
    its standard error (the last two lines of Table 3.3)."""
    b0 = ytr.mean() - Xtr.mean(0) @ beta
    e = (yte - b0 - Xte @ beta) ** 2
    return b0, e.mean(), e.std(ddof=1) / np.sqrt(len(e))


# =========================================================================== Section 3.2: least squares
def ols_fit(X, y, intercept=True):
    """Least squares (3.6) with sigma-hat^2, standard errors and Z-scores (3.12)."""
    A = np.column_stack([np.ones(len(y)), X]) if intercept else X
    Q, R = np.linalg.qr(A)
    beta = np.linalg.solve(R, Q.T @ y)
    res = y - A @ beta
    dfres = len(y) - A.shape[1]
    rss = res @ res
    s2 = rss / dfres
    Rinv = np.linalg.inv(R)
    v = (Rinv ** 2).sum(1)                    # diagonal of (A^T A)^{-1} = R^{-1} R^{-T}
    se = np.sqrt(s2 * v)
    return dict(beta=beta, se=se, z=beta / se, rss=rss, sigma2=s2, df=dfres, v=v, fitted=A @ beta, resid=res)


def f_test(X, y, drop):
    """F statistic (3.13) for dropping the columns `drop` (indices into X) and its p-value."""
    big = ols_fit(X, y)
    keep = [j for j in range(X.shape[1]) if j not in drop]
    small = ols_fit(X[:, keep], y)
    p1, p0 = X.shape[1], len(keep)
    F = ((small["rss"] - big["rss"]) / (p1 - p0)) / (big["rss"] / (len(y) - p1 - 1))
    return dict(F=F, p=stats.f.sf(F, p1 - p0, len(y) - p1 - 1), rss0=small["rss"], rss1=big["rss"], df1=p1 - p0, df2=len(y) - p1 - 1)


def gram_schmidt(X, y):
    """Algorithm 3.1 on the columns of X (X should contain the column of ones first if wanted).

    Returns Z (orthogonal residual vectors z_j), Gamma (unit upper triangular, X = Z Gamma (3.30)),
    the QR factors Q = Z D^{-1}, R = D Gamma (3.31), and the full coefficient vector obtained in the
    same pass: beta_p from (3.28), then back-substitution R beta = Q^T y (Exercise 3.4)."""
    N, p = X.shape
    Z = np.zeros((N, p))
    G = np.eye(p)
    for j in range(p):
        z = X[:, j].astype(float).copy()
        for k in range(j):
            G[k, j] = Z[:, k] @ X[:, j] / (Z[:, k] @ Z[:, k])
            z -= G[k, j] * Z[:, k]
        Z[:, j] = z
    D = np.sqrt((Z ** 2).sum(0))
    Q = Z / D
    R = D[:, None] * G
    theta = Z.T @ y / D ** 2                  # univariate coefficients of y on each z_j
    beta = np.zeros(p)
    for j in range(p - 1, -1, -1):           # Gamma beta = theta, back-substitution
        beta[j] = theta[j] - G[j, j + 1:] @ beta[j + 1:]
    return dict(Z=Z, Gamma=G, Q=Q, R=R, beta=beta, beta_last=(Z[:, -1] @ y) / (Z[:, -1] @ Z[:, -1]))


# =========================================================================== Section 3.3: subset selection
def all_subsets(X, y):
    """Residual sum of squares of every subset (with intercept): list of (size, subset, RSS)."""
    p = X.shape[1]
    out = []
    for k in range(p + 1):
        for S in itertools.combinations(range(p), k):
            A = np.column_stack([np.ones(len(y))] + [X[:, j] for j in S])
            b = np.linalg.lstsq(A, y, rcond=None)[0]
            r = y - A @ b
            out.append((k, S, float(r @ r)))
    return out


def best_subsets(X, y):
    """The best subset of each size (lowest RSS), from all_subsets: dict k -> (subset, RSS)."""
    best = {}
    for k, S, rss in all_subsets(X, y):
        if k not in best or rss < best[k][1]:
            best[k] = (S, rss)
    return best


def subset_coef(X, y, S):
    """Least-squares coefficients (centred, intercept absorbed) on the subset S, zeros elsewhere."""
    Xc, yc, _, _ = centred(X, y)
    b = np.zeros(X.shape[1])
    if len(S):
        b[list(S)] = np.linalg.lstsq(Xc[:, list(S)], yc, rcond=None)[0]
    return b


def forward_stepwise(X, y, kmax=None):
    """Forward-stepwise selection (Section 3.3.2) with the QR updating of Exercise 3.9.

    With Q the orthonormal basis of the current (centred) model and r the residual, adding x_j
    reduces the RSS by (r^T z_j)^2 / ||z_j||^2 with z_j = x_j - Q Q^T x_j; the winner is appended to
    Q by one Gram-Schmidt step. Returns the sequence of active sets and coefficient vectors."""
    Xc, yc, _, _ = centred(X, y)
    N, p = Xc.shape
    kmax = min(p, N - 1) if kmax is None else kmax
    Q = np.zeros((N, 0))
    r = yc.copy()
    active, sets, coefs = [], [()], [np.zeros(p)]
    for _ in range(kmax):
        best, bj, bz = -1.0, None, None
        for j in range(p):
            if j in active:
                continue
            z = Xc[:, j] - Q @ (Q.T @ Xc[:, j])
            nz = z @ z
            if nz < 1e-12 * (Xc[:, j] @ Xc[:, j]):
                continue
            gain = (r @ z) ** 2 / nz
            if gain > best:
                best, bj, bz = gain, j, z
        if bj is None:
            break
        q = bz / np.linalg.norm(bz)
        Q = np.column_stack([Q, q])
        r = r - (q @ r) * q
        active.append(bj)
        sets.append(tuple(active))
        coefs.append(subset_coef(X, y, active))
    return sets, coefs


def backward_stepwise(X, y):
    """Backward-stepwise selection: drop the variable with the smallest |Z|-score (Exercise 3.10)."""
    p = X.shape[1]
    active = list(range(p))
    sets, coefs = [tuple(active)], [subset_coef(X, y, active)]
    while active:
        if len(active) == 1:
            active = []
        else:
            fit = ols_fit(X[:, active], y)
            drop = active[int(np.argmin(np.abs(fit["z"][1:])))]
            active = [j for j in active if j != drop]
        sets.append(tuple(active))
        coefs.append(subset_coef(X, y, active))
    return sets[::-1], coefs[::-1]


def forward_stagewise(X, y, tol=1e-4, max_steps=20000):
    """Forward-stagewise regression (Section 3.3.3), the 'FS' of Figures 3.6 and 3.16.

    Inputs are centred and scaled to unit norm; at each step the variable most correlated with the
    residual receives its full simple-regression coefficient on the residual, and nothing else is
    adjusted. Stops when every |correlation| < tol. Returns the sequence of coefficient vectors on
    the original scale of X."""
    Xc, yc, _, _ = centred(X, y)
    nrm = np.linalg.norm(Xc, axis=0)
    U = Xc / nrm
    b = np.zeros(X.shape[1])
    r = yc.copy()
    path = [b.copy()]
    ny = np.linalg.norm(yc)
    for _ in range(max_steps):
        c = U.T @ r
        j = int(np.argmax(np.abs(c)))
        if abs(c[j]) / max(np.linalg.norm(r), 1e-300) < tol or abs(c[j]) < 1e-12 * ny:
            break
        b[j] += c[j]
        r -= c[j] * U[:, j]
        path.append(b.copy())
    return [v / nrm for v in path]


def best_subset_leaps(Xs, ys):
    """Best subsets of every size for a list of data sets, by R's leaps (leaps and bounds,
    Furnival and Wilson 1974). Returns, per data set, a list of subsets (tuples) of sizes 1..p."""
    with tempfile.TemporaryDirectory() as td:
        for i, (X, y) in enumerate(zip(Xs, ys)):
            np.savetxt(os.path.join(td, "x%d.csv" % i), np.column_stack([y, X]), delimiter=",")
        script = (
            "suppressMessages(library(leaps)); n <- %d\n"
            "for (i in 0:(n-1)) { d <- as.matrix(read.csv(file.path('%s', paste0('x', i, '.csv')), header=FALSE))\n"
            "  f <- regsubsets(d[, -1], d[, 1], nvmax=ncol(d)-1, method='exhaustive', really.big=TRUE)\n"
            "  w <- summary(f)$which[, -1, drop=FALSE] * 1\n"
            "  write.table(w, file.path('%s', paste0('w', i, '.txt')), row.names=FALSE, col.names=FALSE) }\n"
        ) % (len(Xs), td, td)
        with open(os.path.join(td, "run.R"), "w") as f:
            f.write(script)
        env = dict(os.environ, OPENBLAS_NUM_THREADS="1")
        subprocess.run([RSCRIPT, os.path.join(td, "run.R")], check=True, env=env, capture_output=True)
        out = []
        for i in range(len(Xs)):
            W = np.loadtxt(os.path.join(td, "w%d.txt" % i), ndmin=2)
            out.append([tuple(np.flatnonzero(row)) for row in W])
    return out


# =========================================================================== Section 3.4.1: ridge regression
def ridge_svd(X, y, lam):
    """Ridge coefficients (3.44) for centred X, y, via the SVD: V diag(d / (d^2 + lam)) U^T y."""
    U, d, Vt = np.linalg.svd(X, full_matrices=False)
    lam = np.atleast_1d(lam)
    B = np.array([Vt.T @ (d / (d ** 2 + l) * (U.T @ y)) for l in lam])
    return B if len(B) > 1 else B[0]


def ridge_df(X, lam):
    """Effective degrees of freedom (3.50): sum_j d_j^2 / (d_j^2 + lam)."""
    d = np.linalg.svd(X, compute_uv=False)
    return np.array([np.sum(d ** 2 / (d ** 2 + l)) for l in np.atleast_1d(lam)])


def lam_for_df(X, df):
    """The lam >= 0 with df(lam) = df (0 < df <= rank); df = 0 gives +inf, df = rank gives 0."""
    d = np.linalg.svd(X, compute_uv=False)
    d = d[d > 1e-10 * d[0]]
    if df <= 0:
        return np.inf
    if df >= len(d) - 1e-12:
        return 0.0
    f = lambda l: np.sum(d ** 2 / (d ** 2 + l)) - df
    hi = d[0] ** 2
    while f(hi) > 0:
        hi *= 10
    return brentq(f, 0.0, hi, xtol=1e-14, rtol=1e-14)


# =========================================================================== Section 3.4.2: the lasso
def soft(z, a):
    """Soft thresholding S(z, a) = sign(z)(|z| - a)_+ (Table 3.4)."""
    return np.sign(z) * np.maximum(np.abs(z) - a, 0.0)


def lasso_cd(X, y, lam, beta0=None, tol=1e-13, max_sweeps=100000):
    """Coordinate descent (3.84) for (3.52) without intercept: 1/2 ||y - X b||^2 + lam ||b||_1.

    Columns need not have unit norm: the update is b_j = S(x_j^T r_j, lam) / ||x_j||^2 with r_j the
    partial residual. Stops when a full sweep changes no coefficient by more than tol."""
    p = X.shape[1]
    b = np.zeros(p) if beta0 is None else beta0.astype(float).copy()
    sq = (X ** 2).sum(0)
    r = y - X @ b
    for _ in range(max_sweeps):
        dmax = 0.0
        for j in range(p):
            rho = X[:, j] @ r + sq[j] * b[j]
            nb = soft(rho, lam) / sq[j]
            d = nb - b[j]
            if d != 0.0:
                r -= d * X[:, j]
                b[j] = nb
                dmax = max(dmax, abs(d))
        if dmax < tol:
            break
    return b


def lasso_path_cd(X, y, lams):
    """Pathwise coordinate descent with warm starts from lam_max = max |x_j^T y| downwards."""
    B, b = [], None
    for l in lams:
        b = lasso_cd(X, y, l, b)
        B.append(b.copy())
    return np.array(B)


def lars(X, y, method="lar", tol=1e-11, max_steps=500, centred_data=True):
    """Least angle regression, Algorithm 3.2, with exact step lengths (Exercise 3.25).

    X, y should be centred (Algorithm 3.2 also scales X to unit norm; any scaling works, the
    'correlations' are then the inner products c = X^T r). method:
      'lar'   - Algorithm 3.2;
      'lasso' - with the modification 3.2a (a variable whose coefficient hits 0 leaves the active
                set), which gives the lasso path of (3.52) with lam = max_j |c_j|;
      'fs0'   - with the modification 3.2b (the direction is the sign-constrained least-squares
                fit of the residual on the tied variables), the infinitesimal forward stagewise path.
    Returns a dict with the coefficients at the knots (rows), the maximal |c| at each knot
    (lam), the inner products c at each knot, the active sets and the events. With
    centred_data=False the rank bound is min(N, p) instead of min(N - 1, p) (for the 'population'
    data of Figure 3.18, which are not centred)."""
    N, p = X.shape
    beta = np.zeros(p)
    r = y.astype(float).copy()
    c = X.T @ r
    C = np.max(np.abs(c))
    A = [int(np.argmax(np.abs(c)))]
    betas, lams, cs, actives, events = [beta.copy()], [C], [c.copy()], [list(A)], [("enter", A[0])]
    maxrank = min(N - 1, p) if centred_data else min(N, p)
    for _ in range(max_steps):
        if C <= tol * max(1.0, lams[0]):
            break
        s = np.sign(c[A])
        XA = X[:, A]
        if method == "fs0":
            bb, _ = nnls(XA * s, r)            # min ||r - X_A diag(s) b|| subject to b >= 0
            w = s * bb / C                     # direction per unit decrease of C
            moving = [A[i] for i in range(len(A)) if bb[i] > 1e-12 * max(1.0, bb.max())]
            if len(moving) < len(A):           # tied but not moving: their correlation drops faster
                w = w[[A.index(j) for j in moving]]
                A = moving
                XA = X[:, A]
            u = XA @ w
        else:
            G = XA.T @ XA
            w = np.linalg.solve(G, s)          # X_A^T u = s: the correlations of A fall at equal rate
            u = XA @ w
        a = X.T @ u
        # step length: next variable to tie (Exercise 3.25)
        gam, nxt, kind = C, None, "end"
        if len(A) < maxrank:
            for j in range(p):
                if j in A:
                    continue
                for g in ((C - c[j]) / (1.0 - a[j]) if 1.0 - a[j] > 1e-15 else np.inf,
                          (C + c[j]) / (1.0 + a[j]) if 1.0 + a[j] > 1e-15 else np.inf):
                    if tol < g < gam:
                        gam, nxt, kind = g, j, "enter"
        if method == "lasso":                  # modification 3.2a: a coefficient reaching zero
            for i, j in enumerate(A):
                if w[i] != 0:
                    g = -beta[j] / w[i]
                    if tol < g < gam - 1e-14 and beta[j] != 0:
                        gam, nxt, kind = g, j, "drop"
        beta[A] += gam * w
        r = y - X @ beta
        c = X.T @ r
        C = C - gam
        if kind == "drop":
            beta[nxt] = 0.0
            A = [j for j in A if j != nxt]
            r = y - X @ beta
            c = X.T @ r
        elif kind == "enter":
            A = A + [nxt]
        betas.append(beta.copy())
        lams.append(max(C, 0.0))
        cs.append(c.copy())
        actives.append(list(A))
        events.append((kind, nxt))
        if kind == "end":
            break
    return dict(beta=np.array(betas), lam=np.array(lams), c=np.array(cs), active=actives, events=events)


def arc_length(B):
    """Cumulative L1 arc length (footnote 2, Section 3.4.4) along a sequence of coefficient vectors."""
    return np.r_[0.0, np.cumsum(np.abs(np.diff(B, axis=0)).sum(1))]


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


def lasso_at_s(X, y, s):
    """The lasso solution at shrinkage factor s = ||b||_1 / ||b_ls||_1 (Figure 3.10), 0 <= s <= 1."""
    P = lars(X, y, "lasso")
    l1 = np.abs(P["beta"]).sum(1)
    return path_at(P["beta"], np.atleast_1d(s) * l1[-1], l1)


# =========================================================================== Section 3.5: derived inputs
def pcr(X, y, M):
    """Principal components regression (3.61)-(3.62) on centred X, y: sum_{m<=M} theta_m v_m."""
    U, d, Vt = np.linalg.svd(X, full_matrices=False)
    theta = (U.T @ y) / d
    return Vt[:M].T @ theta[:M]


def pls(X, y, M):
    """Partial least squares, Algorithm 3.3, on centred X, y. Returns the coefficient vectors
    beta_pls(m), m = 0..M (rows), recovered from the sequence of transformations: with
    X^(m-1) = X T, the direction z_m = X^(m-1) phi_m = X (T phi_m)."""
    N, p = X.shape
    T = np.eye(p)
    Xm = X.copy()
    beta = np.zeros(p)
    out = [beta.copy()]
    for _ in range(M):
        phi = Xm.T @ y
        z = Xm @ phi
        zz = z @ z
        if zz < 1e-20:
            out.append(beta.copy())
            continue
        theta = z @ y / zz
        wvec = T @ phi
        beta = beta + theta * wvec
        coef = (z @ Xm) / zz
        T = T - np.outer(wvec, coef)
        Xm = Xm - np.outer(z, coef)
        out.append(beta.copy())
    return np.array(out)


# =========================================================================== Section 3.8
def incremental_fs(X, y, eps, nsteps):
    """Incremental forward stagewise FS_eps, Algorithm 3.4 (X centred; inner products as
    correlations). Returns the coefficient vectors after each step (rows)."""
    b = np.zeros(X.shape[1])
    r = y.astype(float).copy()
    out = [b.copy()]
    for _ in range(nsteps):
        c = X.T @ r
        j = int(np.argmax(np.abs(c)))
        d = eps * np.sign(c[j])
        b[j] += d
        r -= d * X[:, j]
        out.append(b.copy())
    return np.array(out)


def scad_penalty(beta, lam=1.0, a=4.0):
    """The SCAD penalty J_a(beta, lam) whose derivative is (3.82), integrated from 0."""
    b = np.abs(beta)
    out = np.where(b <= lam, lam * b,
                   np.where(b <= a * lam, (2 * a * lam * b - b ** 2 - lam ** 2) / (2 * (a - 1)),
                            lam ** 2 * (a + 1) / 2))
    return out


def group_lasso_bcd(X, y, groups, lam, tol=1e-12, max_sweeps=20000):
    """Grouped lasso (3.80) without intercept by block coordinate descent, for groups whose
    columns are orthonormal (X_l^T X_l = I): beta_l = (1 - lam sqrt(p_l) / (2 ||s_l||))_+ s_l with
    s_l = X_l^T r_l, the exact block minimiser of ||y - X b||^2 + lam sum sqrt(p_l) ||b_l||."""
    b = np.zeros(X.shape[1])
    r = y - X @ b
    for _ in range(max_sweeps):
        dmax = 0.0
        for g in groups:
            Xg = X[:, g]
            sg = Xg.T @ r + b[g]
            ns = np.linalg.norm(sg)
            nb = max(0.0, 1.0 - lam * np.sqrt(len(g)) / (2 * ns)) * sg if ns > 0 else 0 * sg
            d = nb - b[g]
            r -= Xg @ d
            b[g] = nb
            dmax = max(dmax, np.abs(d).max())
        if dmax < tol:
            break
    return b


def dantzig(X, y, s):
    """The Dantzig selector (3.78), min ||b||_1 subject to ||X^T (y - X b)||_inf <= s, as a linear
    programme in (b+, b-) >= 0."""
    p = X.shape[1]
    G, g = X.T @ X, X.T @ y
    A = np.block([[G, -G], [-G, G]])
    rhs = np.r_[s + g, s - g]
    res = linprog(np.ones(2 * p), A_ub=A, b_ub=rhs, bounds=[(0, None)] * (2 * p), method="highs")
    return res.x[:p] - res.x[p:]


# =========================================================================== cross-validation
def folds_for(N, K=10, seed=13):
    """Fold labels 0..K-1 for N cases (a seeded random permutation)."""
    rng = np.random.default_rng(seed)
    return np.arange(N)[rng.permutation(N)] % K


def cross_validate(fit, grid, X, y, K=10, seed=13):
    """K-fold CV error of fit(Xc, yc, g) -> beta for each g in grid (inputs and output centred on
    the training folds). Returns the mean squared error, its standard error (sd of the K fold
    errors over sqrt(K)) and the one-standard-error choice (the first, least complex, grid point
    whose CV error is within one SE of the minimum)."""
    lab = folds_for(len(y), K, seed)
    E = np.zeros((K, len(grid)))
    for k in range(K):
        tr, va = lab != k, lab == k
        Xc, yc, xm, ym = centred(X[tr], y[tr])
        for i, g in enumerate(grid):
            b = fit(Xc, yc, g)
            E[k, i] = np.mean((y[va] - ym - (X[va] - xm) @ b) ** 2)
    cv, se = E.mean(0), E.std(0, ddof=1) / np.sqrt(K)
    i0 = int(np.argmin(cv))
    pick = int(np.flatnonzero(cv <= cv[i0] + se[i0])[0])
    return dict(cv=cv, se=se, best=i0, pick=pick, folds=E)


def _fit_subset(Xc, yc, k):
    if k == 0:
        return np.zeros(Xc.shape[1])
    S = best_subsets(Xc, yc)[k][0]
    return subset_coef(Xc, yc, S)


def _fit_ridge_df(Xc, yc, df):
    lam = lam_for_df(Xc, df)
    return np.zeros(Xc.shape[1]) if np.isinf(lam) else ridge_svd(Xc, yc, lam)


def _fit_lasso_s(Xc, yc, s):
    return lasso_at_s(Xc, yc, s)[0]


def _fit_pcr(Xc, yc, M):
    return pcr(Xc, yc, M)


def _fit_pls(Xc, yc, M):
    return pls(Xc, yc, M)[M]


CV_METHODS = [
    ("All Subsets", "Subset size", _fit_subset, list(range(9))),
    ("Ridge Regression", "Degrees of freedom", _fit_ridge_df, list(range(9))),
    ("Lasso", "Shrinkage factor s", _fit_lasso_s, list(np.linspace(0, 1, 9))),
    ("Principal Components Regression", "Number of directions", _fit_pcr, list(range(9))),
    ("Partial Least Squares", "Number of directions", _fit_pls, list(range(9))),
]


# =========================================================================== Table 3.3 settings
BOOK_TUNING = dict(subset=2, ridge_df=5.0, lasso_s=0.36, pcr_M=7, pls_M=2)


def table_3_3(tuning=BOOK_TUNING):
    """Coefficients and test errors of Table 3.3 at given complexity values."""
    D = load_prostate()
    Xc, yc, _, _ = centred(D["Xtr"], D["ytr"])
    cols = {}
    cols["LS"] = np.linalg.lstsq(Xc, yc, rcond=None)[0]
    cols["Best Subset"] = subset_coef(D["Xtr"], D["ytr"], best_subsets(D["Xtr"], D["ytr"])[tuning["subset"]][0])
    cols["Ridge"] = ridge_svd(Xc, yc, lam_for_df(Xc, tuning["ridge_df"]))
    cols["Lasso"] = lasso_at_s(Xc, yc, tuning["lasso_s"])[0]
    cols["PCR"] = pcr(Xc, yc, tuning["pcr_M"])
    cols["PLS"] = pls(Xc, yc, tuning["pls_M"])[tuning["pls_M"]]
    out = {}
    for k, b in cols.items():
        b0, te, se = test_error(b, D["Xtr"], D["ytr"], D["Xte"], D["yte"])
        out[k] = dict(beta=b, intercept=b0, test=te, se=se)
    return out


# =========================================================================== simulations of Figs 3.6, 3.16
def sim_data(N, seed, p=31, rho=0.85, nz=10, coef_var=0.4, noise_var=6.25):
    """One replicate of the simulation of Figure 3.6: equicorrelated N(0, 1) inputs, nz nonzero
    coefficients N(0, coef_var) at random positions, noise N(0, noise_var)."""
    rng = np.random.default_rng(seed)
    X = np.sqrt(1 - rho) * rng.standard_normal((N, p)) + np.sqrt(rho) * rng.standard_normal((N, 1))
    beta = np.zeros(p)
    beta[rng.choice(p, nz, replace=False)] = rng.normal(0, np.sqrt(coef_var), nz)
    y = X @ beta + rng.normal(0, np.sqrt(noise_var), N)
    Sigma = (1 - rho) * np.eye(p) + rho * np.ones((p, p))
    return X, y, beta, Sigma


def model_error(b, beta, Sigma):
    d = b - beta
    return float(d @ Sigma @ d)


def sim_fig_3_6(nrep=50, N=300, use_cache=True):
    """Average model error and squared coefficient error against subset size for best subset,
    forward stepwise, backward stepwise and forward stagewise (Figure 3.6)."""
    path = os.path.join(CACHE_DIR, "ch03_fig3_6_N%d_R%d.npz" % (N, nrep))
    if use_cache and os.path.exists(path):
        return dict(np.load(path))
    p = 31
    data = [sim_data(N, 2009 + i) for i in range(nrep)]
    subsets = best_subset_leaps([d[0] for d in data], [d[1] for d in data])
    me = {k: np.zeros((nrep, p + 1)) for k in ("best", "fwd", "bwd", "fs")}
    se = {k: np.zeros((nrep, p + 1)) for k in me}
    for i, (X, y, beta, S) in enumerate(data):
        seqs = {"best": [np.zeros(p)] + [subset_coef(X, y, s) for s in subsets[i]],
                "fwd": forward_stepwise(X, y)[1], "bwd": backward_stepwise(X, y)[1]}
        fs = forward_stagewise(X, y, tol=1e-4)
        last = {}
        for b in fs:                            # the last FS step with k nonzero coefficients
            last[int(np.sum(b != 0))] = b
        seqs["fs"] = [last.get(k, None) for k in range(p + 1)]
        for k, seq in seqs.items():
            for j, b in enumerate(seq):
                if b is None:
                    me[k][i, j] = se[k][i, j] = np.nan
                else:
                    me[k][i, j] = model_error(b, beta, S)
                    se[k][i, j] = float(np.sum((b - beta) ** 2))
    out = {"me_" + k: v for k, v in me.items()}
    out.update({"se_" + k: v for k, v in se.items()})
    os.makedirs(CACHE_DIR, exist_ok=True)
    np.savez(path, **out)
    return out


def sim_fig_3_16(nrep=50, N=100, ngrid=21, use_cache=True):
    """Average model error against the fraction of L1 arc length for forward stepwise, LAR, lasso,
    forward stagewise and FS0 (Figure 3.16)."""
    path = os.path.join(CACHE_DIR, "ch03_fig3_16_N%d_R%d.npz" % (N, nrep))
    if use_cache and os.path.exists(path):
        return dict(np.load(path))
    grid = np.linspace(0, 1, ngrid)
    keys = ("fwd", "lar", "lasso", "fs", "fs0")
    me = {k: np.zeros((nrep, ngrid)) for k in keys}
    for i in range(nrep):
        X, y, beta, S = sim_data(N, 2009 + i)
        Xc, yc, _, _ = centred(X, y)
        paths = {"fwd": np.array(forward_stepwise(X, y)[1]),
                 "lar": lars(Xc, yc, "lar")["beta"], "lasso": lars(Xc, yc, "lasso")["beta"],
                 "fs": np.array(forward_stagewise(X, y, tol=1e-4)), "fs0": lars(Xc, yc, "fs0")["beta"]}
        for k, B in paths.items():
            al = arc_length(B)
            Bg = path_at(B, grid * al[-1], al)
            me[k][i] = [model_error(b, beta, S) for b in Bg]
    out = {"grid": grid}
    out.update({"me_" + k: v for k, v in me.items()})
    os.makedirs(CACHE_DIR, exist_ok=True)
    np.savez(path, **out)
    return out


# =========================================================================== exercises with computation
def band_simulation(nrep=2000, N=40, sigma=1.0, seed=7, level=0.95):
    """Exercise 3.2: pointwise intervals for f(x0) = a^T beta against the band generated by the
    confidence set (3.15), for a cubic fit on x ~ U(-1, 1) (fixed design), true f = 1 + x - x^2 + x^3.
    Returns the band half-widths (in units of sigma-hat) and the pointwise and simultaneous coverages
    of both bands on a grid of 101 points."""
    rng = np.random.default_rng(seed)
    x = np.sort(rng.uniform(-1, 1, N))
    X = np.vander(x, 4, increasing=True)
    beta = np.array([1.0, 1.0, -1.0, 1.0])
    g = np.linspace(-1, 1, 101)
    A = np.vander(g, 4, increasing=True)
    XtXi = np.linalg.inv(X.T @ X)
    h = np.sqrt(np.einsum("ij,jk,ik->i", A, XtXi, A))
    z = stats.norm.isf((1 - level) / 2)
    c = np.sqrt(stats.chi2.isf(1 - level, 4))
    cov_pt = np.zeros((2, len(g)))
    sim = np.zeros(2)
    for _ in range(nrep):
        y = X @ beta + sigma * rng.standard_normal(N)
        b = XtXi @ X.T @ y
        s = np.sqrt(np.sum((y - X @ b) ** 2) / (N - 4))
        err = np.abs(A @ (b - beta))
        ins = np.array([err <= z * s * h, err <= c * s * h])
        cov_pt += ins
        sim += ins.all(1)
    return dict(z=z, c=c, pointwise=cov_pt / nrep, simultaneous=sim / nrep)


def load_spam():
    """Spam data with log(x + 0.1) inputs standardised over all cases, response 0/1 and the
    book's train/test split (spam.traintest: 1 = test)."""
    D = np.loadtxt(common.esl_file("spam.data"))
    test = np.loadtxt(common.esl_file("spam.traintest")).astype(bool)
    X = np.log(D[:, :57] + 0.1)
    X = (X - X.mean(0)) / X.std(0, ddof=1)
    return X[~test], D[~test, 57], X[test], D[test, 57]


def spam_table(seed=13):
    """Exercise 3.17: Table 3.3 for the spam data. The 0/1 response is regressed on the 57 inputs;
    each method's complexity is chosen by tenfold CV with the one-SE rule. Best-subset search over
    2^57 models is out of reach, so forward stepwise selection takes its place. Returns, per method,
    the chosen complexity, the number of nonzero coefficients, the test mean squared error (with
    its standard error) and the test misclassification rate of the rule yhat > 0.5."""
    Xtr, ytr, Xte, yte = load_spam()
    p = Xtr.shape[1]

    def fwd(Xc, yc, k):
        return forward_stepwise(Xc, yc, kmax=k)[1][k] if k else np.zeros(Xc.shape[1])

    methods = [("LS", None, None),
               ("Forward stepwise", fwd, list(range(0, p + 1, 3)) + [p]),
               ("Ridge", _fit_ridge_df, list(range(0, p + 1, 3)) + [p]),
               ("Lasso", _fit_lasso_s, list(np.linspace(0, 1, 21))),
               ("PCR", _fit_pcr, list(range(0, p + 1, 3)) + [p]),
               ("PLS", _fit_pls, list(range(0, 21)))]
    out = {}
    Xc, yc, _, _ = centred(Xtr, ytr)
    for name, f, grid in methods:
        if f is None:
            b, g = np.linalg.lstsq(Xc, yc, rcond=None)[0], p
        else:
            R = cross_validate(f, grid, Xtr, ytr, seed=seed)
            g = grid[R["pick"]]
            b = f(Xc, yc, g)
        b0, te, se = test_error(b, Xtr, ytr, Xte, yte)
        yhat = b0 + Xte @ b
        out[name] = dict(param=g, nonzero=int(np.sum(np.abs(b) > 1e-12)), test=te, se=se,
                         misclass=float(np.mean((yhat > 0.5) != (yte > 0.5))))
    return out


# =========================================================================== small data sets
def lars_sim_data(seed=28, N=60, p=6):
    """The simulated data of Figures 3.14 and 3.15 (and of lars-lasso-demo.html): six Gaussian
    inputs with a random correlation matrix, coefficients N(0, 4), noise N(0, 4); the inputs are
    standardised to mean 0 and variance 1 and the response is centred. With seed 28 one LAR
    coefficient passes through zero, so that the LAR and lasso paths differ."""
    rng = np.random.default_rng(seed)
    A = rng.standard_normal((p, p))
    S = A @ A.T + 0.3 * np.eye(p)
    d = np.sqrt(np.diag(S))
    L = np.linalg.cholesky(S / np.outer(d, d))
    X = rng.standard_normal((N, p)) @ L.T
    beta = rng.normal(0, 2, p)
    y = X @ beta + 2.0 * rng.standard_normal(N)
    X = (X - X.mean(0)) / X.std(0)
    return X, y - y.mean()


def export_demo_data():
    """JSON for the browser demonstrations (courses/esl/data/ch03-*.json)."""
    os.makedirs(DATA_OUT, exist_ok=True)
    D = load_prostate()
    obj = dict(names=NAMES, Z=np.round(D["Z"], 12).tolist(), y=np.round(D["y"], 10).tolist(),
               train=[bool(t) for t in D["train"]],
               note="Prostate cancer data (Stamey et al. 1989) from the book's website; predictors standardised over all 97 cases.")
    with open(os.path.join(DATA_OUT, "ch03-prostate.json"), "w") as f:
        json.dump(obj, f, separators=(",", ":"))
    X, y = lars_sim_data()
    with open(os.path.join(DATA_OUT, "ch03-lars-sim.json"), "w") as f:
        json.dump(dict(X=np.round(X, 12).tolist(), y=np.round(y, 12).tolist(),
                       note="Simulated data of Figures 3.14 and 3.15: N = 60, six correlated inputs (mean 0, variance 1), centred response."),
                  f, separators=(",", ":"))
    print("wrote ../data/ch03-prostate.json and ../data/ch03-lars-sim.json")


# =========================================================================== figures
import matplotlib.pyplot as plt  # noqa: E402  (common has selected the Agg backend)


def _label_paths(ax, x, B, names=NAMES, dx=0.02, gap=None):
    """Write the variable names at the right end of the profiles, nudged apart vertically."""
    yv = B[-1].astype(float).copy()
    gap = gap if gap is not None else 0.045 * (B.max() - B.min())
    order = np.argsort(yv)
    pos = yv[order].copy()
    for i in range(1, len(pos)):
        pos[i] = max(pos[i], pos[i - 1] + gap)
    pos -= max(0.0, (pos - yv[order]).mean())
    for i in range(1, len(pos)):
        pos[i] = max(pos[i], pos[i - 1] + gap)
    for k, j in enumerate(order):
        ax.text(x + dx, pos[k], names[j], fontsize=8, va="center", color=PCOL[j % len(PCOL)])


def fig_3_1(out_dir=None):
    """Least-squares plane through points with two inputs (simulated)."""
    rng = np.random.default_rng(1)
    N = 60
    X = rng.uniform(0, 1, (N, 2))
    y = 1 + 2 * X[:, 0] + 1.5 * X[:, 1] + rng.normal(0, 0.35, N)
    fit = ols_fit(X, y)
    b = fit["beta"]
    fig = plt.figure(figsize=(5.2, 4.4))
    ax = fig.add_subplot(111, projection="3d")
    g = np.linspace(0, 1, 12)
    G1, G2 = np.meshgrid(g, g)
    ax.plot_surface(G1, G2, b[0] + b[1] * G1 + b[2] * G2, color=BLUE, alpha=0.18, edgecolor="none")
    ax.plot_wireframe(G1, G2, b[0] + b[1] * G1 + b[2] * G2, color=BLUE, linewidth=0.3, alpha=0.5)
    yh = fit["fitted"]
    for i in range(N):
        ax.plot([X[i, 0]] * 2, [X[i, 1]] * 2, [y[i], yh[i]], color=GREY, lw=0.6)
    above = y >= yh
    ax.scatter(X[above, 0], X[above, 1], y[above], color=RED, s=10, depthshade=False)
    ax.scatter(X[~above, 0], X[~above, 1], y[~above], color="#7a1010", s=10, depthshade=False)
    ax.set_xlabel("$X_1$")
    ax.set_ylabel("$X_2$")
    ax.set_zlabel("$Y$")
    ax.view_init(elev=18, azim=-58)
    ax.set_xticklabels([]); ax.set_yticklabels([]); ax.set_zticklabels([])
    savefig(fig, CH, "fig3-1", out_dir)
    return b


def _arrow3(ax, a, b, color, lw=1.8, ls="-"):
    ax.plot([a[0], b[0]], [a[1], b[1]], [a[2], b[2]], color=color, lw=lw, ls=ls)
    ax.scatter([b[0]], [b[1]], [b[2]], color=color, s=12, depthshade=False)


GEO = dict(x1=np.array([1.0, 0.15, 0.0]), x2=np.array([0.4, 1.0, 0.1]), y=np.array([0.8, 0.6, 1.0]))


def _geometry_axes(fig):
    ax = fig.add_subplot(111, projection="3d")
    x1, x2 = GEO["x1"], GEO["x2"]
    s, t = np.meshgrid(np.linspace(-0.2, 1.3, 2), np.linspace(-0.2, 1.3, 2))
    P = s[..., None] * x1 + t[..., None] * x2
    ax.plot_surface(P[..., 0], P[..., 1], P[..., 2], color="#9fb8d8", alpha=0.25, edgecolor="none")
    ax.set_axis_off()
    ax.view_init(elev=22, azim=-62)
    return ax


def fig_3_2(out_dir=None):
    """The N-dimensional geometry of least squares (N = 3, two inputs)."""
    x1, x2, y = GEO["x1"], GEO["x2"], GEO["y"]
    X = np.column_stack([x1, x2])
    b = np.linalg.lstsq(X, y, rcond=None)[0]
    yh = X @ b
    fig = plt.figure(figsize=(4.6, 4.0))
    ax = _geometry_axes(fig)
    o = np.zeros(3)
    _arrow3(ax, o, x1, BLUE); _arrow3(ax, o, x2, BLUE)
    _arrow3(ax, o, y, RED); _arrow3(ax, o, yh, GREEN)
    ax.plot(*np.column_stack([yh, y]), color=GREY, ls="--", lw=1)
    for v, s, c in ((x1, "$\\mathbf{x}_1$", BLUE), (x2, "$\\mathbf{x}_2$", BLUE), (y, "$\\mathbf{y}$", RED), (yh, "$\\hat{\\mathbf{y}}$", GREEN)):
        ax.text(*(v * 1.06), s, color=c, fontsize=12)
    savefig(fig, CH, "fig3-2", out_dir)
    return dict(beta=b, resid_dot=[float((y - yh) @ x1), float((y - yh) @ x2)])


def fig_3_3(out_dir=None):
    """Tail probabilities Pr(|Z| > z) of t_30, t_100 and N(0, 1)."""
    z = np.linspace(2, 3, 300)
    fig, ax = plt.subplots(figsize=(4.6, 3.6))
    for dist, lab, col in ((stats.t(30), "$t_{30}$", RED), (stats.t(100), "$t_{100}$", GREEN), (stats.norm(), "normal", BLUE)):
        ax.plot(z, 2 * dist.sf(z), color=col, label=lab)
        for a in (0.05, 0.01):
            q = dist.isf(a / 2)
            ax.plot([q, q], [0, a], color=col, lw=0.8, ls=":")
    for a in (0.05, 0.01):
        ax.axhline(a, color=GREY, lw=0.6, ls="--")
    ax.set_xlabel("$z$")
    ax.set_ylabel("Tail probabilities $\\Pr(|Z|>z)$")
    ax.set_xlim(2, 3); ax.set_ylim(0, 0.065)
    ax.legend(frameon=False)
    savefig(fig, CH, "fig3-3", out_dir)
    return {lab: (stats.t(df).isf(0.025) if df else stats.norm.isf(0.025)) for lab, df in (("t30", 30), ("t100", 100), ("z", None))}


def fig_3_4(out_dir=None):
    """Least squares by orthogonalisation of the inputs (Figure 3.2 with z = x2 adjusted for x1)."""
    x1, x2, y = GEO["x1"], GEO["x2"], GEO["y"]
    z = x2 - (x1 @ x2) / (x1 @ x1) * x1
    yh = (x1 @ y) / (x1 @ x1) * x1 + (z @ y) / (z @ z) * z
    fig = plt.figure(figsize=(4.6, 4.0))
    ax = _geometry_axes(fig)
    o = np.zeros(3)
    _arrow3(ax, o, x1, BLUE); _arrow3(ax, o, x2, BLUE); _arrow3(ax, o, z, ORANGE)
    _arrow3(ax, o, y, RED); _arrow3(ax, o, yh, GREEN)
    ax.plot(*np.column_stack([yh, y]), color=GREY, ls="--", lw=1)
    proj = (x1 @ x2) / (x1 @ x1) * x1
    ax.plot(*np.column_stack([proj, x2]), color=ORANGE, ls=":", lw=1)
    for v, s, c in ((x1, "$\\mathbf{x}_1$", BLUE), (x2, "$\\mathbf{x}_2$", BLUE), (z, "$\\mathbf{z}$", ORANGE), (y, "$\\mathbf{y}$", RED), (yh, "$\\hat{\\mathbf{y}}$", GREEN)):
        ax.text(*(v * 1.07), s, color=c, fontsize=12)
    savefig(fig, CH, "fig3-4", out_dir)
    X = np.column_stack([x1, x2])
    return dict(beta2_gs=(z @ y) / (z @ z), beta2_ls=np.linalg.lstsq(X, y, rcond=None)[0][1])


def fig_3_5(out_dir=None):
    """RSS of all 256 subset models of the prostate training data."""
    D = load_prostate()
    allm = all_subsets(D["Xtr"], D["ytr"])
    best = best_subsets(D["Xtr"], D["ytr"])
    fig, ax = plt.subplots(figsize=(4.6, 3.8))
    k = np.array([m[0] for m in allm]); r = np.array([m[2] for m in allm])
    ax.scatter(k + np.random.default_rng(0).uniform(-0.12, 0.12, len(k)), r, s=9, color=GREY, alpha=0.8)
    ks = sorted(best)
    ax.plot(ks, [best[q][1] for q in ks], color=RED, marker="o", ms=4)
    ax.set_xlabel("Subset size $k$")
    ax.set_ylabel("Residual sum-of-squares")
    ax.set_ylim(0, 100)
    savefig(fig, CH, "fig3-5", out_dir)
    return {q: (tuple(NAMES[j] for j in best[q][0]), best[q][1]) for q in ks}


def fig_3_6(out_dir=None):
    """Subset-selection methods on simulated data, N = 300, p = 31 (50 replicates)."""
    R = sim_fig_3_6()
    k = np.arange(32)
    fig, axes = plt.subplots(1, 2, figsize=(8.6, 3.6))
    for ax, pre, lab in ((axes[0], "me_", "Model error $E[(\\hat\\beta(k)-\\beta)^T\\Sigma(\\hat\\beta(k)-\\beta)]$"),
                         (axes[1], "se_", "$E\\|\\hat\\beta(k)-\\beta\\|^2$")):
        for key, name, col in (("best", "Best Subset", "k"), ("fwd", "Forward Stepwise", ORANGE),
                               ("bwd", "Backward Stepwise", CYAN), ("fs", "Forward Stagewise", GREEN)):
            m = np.nanmean(R[pre + key], 0)
            ax.plot(k[1:], m[1:], "o", ms=3.2, color=col, label=name)
        ax.set_xlabel("Subset size $k$")
        ax.set_ylabel(lab, fontsize=9)
    axes[1].set_yscale("log")
    axes[0].legend(frameon=False, fontsize=8)
    common.panel_label(axes[0], "a", "upper right"); common.panel_label(axes[1], "b", "upper right")
    fig.tight_layout()
    savefig(fig, CH, "fig3-6", out_dir)
    return {key: np.nanmean(R["me_" + key], 0) for key in ("best", "fwd", "bwd", "fs")}


def cv_all(seed=13):
    """The five cross-validation curves of Figure 3.7 on the prostate training data."""
    D = load_prostate()
    return [(name, xl, grid, cross_validate(f, grid, D["Xtr"], D["ytr"], seed=seed)) for name, xl, f, grid in CV_METHODS]


def fig_3_7(out_dir=None):
    """Tenfold cross-validation error curves with standard errors and the one-SE choices."""
    res = cv_all()
    fig, axes = common.panel_grid(3, 2, size=(3.6, 2.7))
    for ax, (name, xl, grid, R) in zip(axes.flat, res):
        g = np.array(grid, float)
        ax.errorbar(g, R["cv"], yerr=R["se"], color=ORANGE, ecolor=CYAN, marker="o", ms=4, capsize=2, lw=1.2)
        ax.axhline(R["cv"][R["best"]] + R["se"][R["best"]], color=PURPLE, ls=":", lw=0.9)
        ax.axvline(g[R["pick"]], color=PURPLE, ls="--", lw=0.9)
        ax.set_title(name)
        ax.set_xlabel(xl)
        ax.set_ylabel("CV error")
        ax.set_ylim(0.4, 1.9)
    axes.flat[-1].axis("off")
    fig.tight_layout()
    savefig(fig, CH, "fig3-7", out_dir)
    return {name: (grid[R["pick"]], grid[R["best"]], R["cv"], R["se"]) for name, xl, grid, R in res}


def fig_3_8(out_dir=None):
    """Ridge coefficient profiles for the prostate data against df(lambda)."""
    D = load_prostate()
    Xc, yc, _, _ = centred(D["Xtr"], D["ytr"])
    lams = np.r_[np.inf, np.logspace(4, -3, 200), 0.0]
    B = np.array([np.zeros(8) if np.isinf(l) else ridge_svd(Xc, yc, l) for l in lams])
    df = np.r_[0.0, ridge_df(Xc, lams[1:])]
    fig, ax = plt.subplots(figsize=(5.0, 4.0))
    for j in range(8):
        ax.plot(df, B[:, j], color=PCOL[j], lw=1.3)
    _label_paths(ax, df[-1], B, dx=0.1)
    ax.axhline(0, color=GREY, lw=0.6, ls="--")
    ax.axvline(5.0, color=RED, lw=0.9, ls="--")
    ax.set_xlabel("df($\\lambda$)")
    ax.set_ylabel("Coefficients")
    ax.set_xlim(0, 9.3)
    savefig(fig, CH, "fig3-8", out_dir)
    return dict(lam5=lam_for_df(Xc, 5.0))


def fig_3_9(out_dir=None):
    """Principal components of a two-dimensional point cloud."""
    rng = np.random.default_rng(5)
    th = np.deg2rad(35)
    Rm = np.array([[np.cos(th), -np.sin(th)], [np.sin(th), np.cos(th)]])
    X = rng.standard_normal((200, 2)) * [2.0, 0.6] @ Rm.T
    X -= X.mean(0)
    U, d, Vt = np.linalg.svd(X, full_matrices=False)
    fig, ax = plt.subplots(figsize=(4.2, 4.2))
    ax.scatter(X[:, 0], X[:, 1], s=10, facecolors="none", edgecolors=BLUE, lw=0.7)
    for k, (lab, col) in enumerate((("Largest principal component", RED), ("Smallest principal component", GREEN))):
        v = Vt[k] * 2.2 * d[k] / np.sqrt(len(X))
        ax.plot([-v[0], v[0]], [-v[1], v[1]], color=col, lw=2.2)
        ax.text(*((-3.2, 3.6) if k == 0 else (2.4, -3.6)), lab, color=col, fontsize=8.5, ha="center")
    ax.set_xlim(-5, 5); ax.set_ylim(-5, 5)
    ax.set_aspect("equal")
    ax.set_xlabel("$X_1$"); ax.set_ylabel("$X_2$")
    savefig(fig, CH, "fig3-9", out_dir)
    return d ** 2 / len(X)


def fig_3_10(out_dir=None):
    """Lasso coefficient profiles for the prostate data against s = t / sum |beta_ls|."""
    D = load_prostate()
    Xc, yc, _, _ = centred(D["Xtr"], D["ytr"])
    P = lars(Xc, yc, "lasso")
    l1 = np.abs(P["beta"]).sum(1)
    s = l1 / l1[-1]
    fig, ax = plt.subplots(figsize=(5.0, 4.0))
    for j in range(8):
        ax.plot(s, P["beta"][:, j], color=PCOL[j], lw=1.3, marker="o", ms=2.5)
    _label_paths(ax, 1.0, P["beta"])
    ax.axhline(0, color=GREY, lw=0.6, ls="--")
    ax.axvline(0.36, color=RED, lw=0.9, ls="--")
    ax.set_xlabel("Shrinkage factor $s$")
    ax.set_ylabel("Coefficients")
    ax.set_xlim(0, 1.17)
    savefig(fig, CH, "fig3-10", out_dir)
    return dict(knots_s=s, events=P["events"])


def table_3_4_fig(out_dir=None):
    """The three thresholding rules of Table 3.4 (orthonormal inputs)."""
    b = np.linspace(-3, 3, 601)
    M, lam = 1.0, 1.0
    rules = (("Best Subset", np.where(np.abs(b) >= M, b, 0.0), "$|\\hat\\beta_{(M)}|$"),
             ("Ridge", b / (1 + lam), None), ("Lasso", soft(b, lam), "$\\lambda$"))
    fig, axes = plt.subplots(1, 3, figsize=(8.4, 2.9))
    for ax, (name, f, lab) in zip(axes, rules):
        ax.plot(b, b, color=GREY, lw=0.8)
        ax.plot(b, f, color=RED, ls="--", lw=1.8)
        ax.axhline(0, color="k", lw=0.5); ax.axvline(0, color="k", lw=0.5)
        ax.set_title(name)
        ax.set_aspect("equal")
        ax.set_xticks([]); ax.set_yticks([])
        if lab:
            ax.annotate(lab, (1.0, 0), (1.15, -0.9), fontsize=9)
        ax.text(0.1, -0.4, "(0,0)", fontsize=7)
    savefig(fig, CH, "tab3-4", out_dir)


def fig_3_11(out_dir=None):
    """Lasso (diamond) and ridge (disk) constraint regions with the elliptical RSS contours."""
    bhat = np.array([1.6, 0.9])
    H = np.array([[1.0, 0.55], [0.55, 0.8]])
    t = 1.0
    fig, axes = plt.subplots(1, 2, figsize=(7.6, 3.8))
    g = np.linspace(-1.6, 2.6, 400)
    B1, B2 = np.meshgrid(g, g)
    Q = H[0, 0] * (B1 - bhat[0]) ** 2 + 2 * H[0, 1] * (B1 - bhat[0]) * (B2 - bhat[1]) + H[1, 1] * (B2 - bhat[1]) ** 2
    sols = []
    for ax, kind in zip(axes, ("lasso", "ridge")):
        reg = (np.abs(B1) + np.abs(B2) <= t) if kind == "lasso" else (B1 ** 2 + B2 ** 2 <= t ** 2)
        ax.contourf(B1, B2, reg, levels=[0.5, 1.5], colors=["#5b8fd6"], alpha=0.7)
        # constrained minimiser on the boundary
        th = np.linspace(-np.pi, np.pi, 200001)
        if kind == "lasso":
            rr = t / (np.abs(np.cos(th)) + np.abs(np.sin(th)))
        else:
            rr = t * np.ones_like(th)
        pts = np.column_stack([rr * np.cos(th), rr * np.sin(th)])
        d = pts - bhat
        q = np.einsum("ij,jk,ik->i", d, H, d)
        sol = pts[np.argmin(q)]
        sols.append(sol)
        lev = q.min() * np.array([1.0, 1.9, 3.2, 5.0])
        ax.contour(B1, B2, Q, levels=lev, colors=RED, linewidths=1)
        ax.plot(*bhat, "ko", ms=3); ax.text(bhat[0] + 0.07, bhat[1] + 0.07, "$\\hat\\beta$")
        ax.plot(*sol, "o", color=GREEN, ms=4)
        ax.axhline(0, color="k", lw=0.5); ax.axvline(0, color="k", lw=0.5)
        ax.set_aspect("equal"); ax.set_xlim(-1.6, 2.6); ax.set_ylim(-1.6, 2.6)
        ax.set_xlabel("$\\beta_1$"); ax.set_ylabel("$\\beta_2$")
        ax.set_title("Lasso" if kind == "lasso" else "Ridge")
    fig.tight_layout()
    savefig(fig, CH, "fig3-11", out_dir)
    return sols


def fig_3_12(out_dir=None):
    """Contours of sum |beta_j|^q for q = 4, 2, 1, 0.5, 0.1."""
    qs = (4, 2, 1, 0.5, 0.1)
    fig, axes = plt.subplots(1, 5, figsize=(9.6, 2.2))
    g = np.linspace(-1.25, 1.25, 801)
    B1, B2 = np.meshgrid(g, g)
    for ax, q in zip(axes, qs):
        F = np.abs(B1) ** q + np.abs(B2) ** q
        ax.contour(B1, B2, F, levels=[1.0], colors=BLUE, linewidths=1.6)
        ax.axhline(0, color=GREY, lw=0.5); ax.axvline(0, color=GREY, lw=0.5)
        ax.set_aspect("equal"); ax.set_xticks([]); ax.set_yticks([])
        ax.set_title("$q=%s$" % q)
    savefig(fig, CH, "fig3-12", out_dir)


def fig_3_13(out_dir=None):
    """|beta|^1.2 contours against the elastic-net penalty with alpha = 0.2."""
    g = np.linspace(-1.25, 1.25, 1201)
    B1, B2 = np.meshgrid(g, g)
    fig, axes = plt.subplots(1, 2, figsize=(5.4, 2.8))
    F1 = np.abs(B1) ** 1.2 + np.abs(B2) ** 1.2
    a = 0.2
    F2 = a * (B1 ** 2 + B2 ** 2) + (1 - a) * (np.abs(B1) + np.abs(B2))
    for ax, F, title in ((axes[0], F1, "$L_q$, $q=1.2$"), (axes[1], F2, "Elastic net, $\\alpha=0.2$")):
        ax.contour(B1, B2, F, levels=[1.0], colors=BLUE, linewidths=1.6)
        ax.axhline(0, color=GREY, lw=0.5); ax.axvline(0, color=GREY, lw=0.5)
        ax.set_aspect("equal"); ax.set_xticks([]); ax.set_yticks([])
        ax.set_title(title)
    savefig(fig, CH, "fig3-13", out_dir)


def fig_3_14(out_dir=None):
    """Absolute correlations |<x_j, r>| / N along the LAR path (simulated data, six inputs)."""
    X, y = lars_sim_data()
    N = len(y)
    P = lars(X, y, "lar")
    al = arc_length(P["beta"])
    fig, ax = plt.subplots(figsize=(5.4, 3.8))
    cols = [BLUE, ORANGE, RED, "k", GREEN, PURPLE]
    for j in range(6):
        ax.plot(al, np.abs(P["c"][:, j]) / N, color=cols[j], lw=1.3)
    top = np.abs(P["c"][0]).max() / N
    for n, (k, (kind, j)) in enumerate([(k, e) for k, e in enumerate(P["events"]) if e[0] == "enter"]):
        ax.axvline(al[k], color=GREY, lw=0.6, ls=":")
        ax.text(al[k], top * (1.03 + 0.06 * (n % 3)), "v%d" % (j + 1), ha="center", fontsize=8)
    ax.axvline(al[-1], color=GREY, lw=0.6, ls=":")
    ax.set_xlabel("$L_1$ arc length")
    ax.set_ylabel("Absolute correlations")
    ax.set_ylim(0, (np.abs(P["c"][0]).max() / N) * 1.22)
    savefig(fig, CH, "fig3-14", out_dir)
    return dict(order=[j + 1 for kind, j in P["events"] if kind == "enter"], arc=al)


def fig_3_15(out_dir=None):
    """LAR and lasso coefficient profiles on the simulated data against L1 arc length."""
    X, y = lars_sim_data()
    cols = [BLUE, ORANGE, RED, "k", GREEN, PURPLE]
    fig, axes = plt.subplots(1, 2, figsize=(8.0, 3.6), sharey=True)
    out = {}
    for ax, method, title in ((axes[0], "lar", "Least Angle Regression"), (axes[1], "lasso", "Lasso")):
        P = lars(X, y, method)
        al = arc_length(P["beta"])
        for j in range(6):
            ax.plot(al, P["beta"][:, j], color=cols[j], lw=1.3)
        for a in al:
            ax.axvline(a, color=GREY, lw=0.4, ls=":")
        ax.axhline(0, color=GREY, lw=0.6, ls="--")
        ax.set_title(title)
        ax.set_xlabel("$L_1$ arc length")
        out[method] = P
    axes[0].set_ylabel("Coefficients")
    fig.tight_layout()
    savefig(fig, CH, "fig3-15", out_dir)
    return out


def fig_3_16(out_dir=None):
    """LAR, lasso, forward stepwise, forward stagewise and FS0 on simulated data, N = 100."""
    R = sim_fig_3_16()
    g = R["grid"]
    fig, ax = plt.subplots(figsize=(5.4, 4.0))
    for key, name, col, ls in (("fwd", "Forward Stepwise", "k", "-"), ("lar", "LAR", "#56b4e9", ":"),
                               ("lasso", "Lasso", ORANGE, ":"), ("fs", "Forward Stagewise", "#e6c229", ":"),
                               ("fs0", "Incremental Forward Stagewise", GREEN, ":")):
        ax.plot(g, R["me_" + key].mean(0), marker="o", ms=3.5, color=col, ls=ls, lw=0.9, label=name)
    ax.set_xlabel("Fraction of $L_1$ arc-length")
    ax.set_ylabel("Model error $E[(\\hat\\beta-\\beta)^T\\Sigma(\\hat\\beta-\\beta)]$", fontsize=9)
    ax.legend(frameon=False, fontsize=8)
    savefig(fig, CH, "fig3-16", out_dir)
    return {k: R["me_" + k].mean(0) for k in ("fwd", "lar", "lasso", "fs", "fs0")}


def fig_3_17(out_dir=None):
    """Shrinkage factors of ridge (df = 5) and PCR (M = 7) along the principal components."""
    D = load_prostate()
    Xc, yc, _, _ = centred(D["Xtr"], D["ytr"])
    d = np.linalg.svd(Xc, compute_uv=False)
    lam = lam_for_df(Xc, 5.0)
    fr = d ** 2 / (d ** 2 + lam)
    fp = (np.arange(8) < 7).astype(float)
    idx = np.arange(1, 9)
    fig, ax = plt.subplots(figsize=(4.6, 3.6))
    ax.plot(idx, fr, "o-", color=GREEN, label="ridge", ms=5)
    ax.plot(idx, fp, "o-", color=ORANGE, label="pcr", ms=5)
    ax.set_xlabel("Index")
    ax.set_ylabel("Shrinkage factor")
    ax.set_ylim(-0.05, 1.08)
    ax.legend(frameon=False)
    savefig(fig, CH, "fig3-17", out_dir)
    return fr


def two_input_paths(rho, beta=(4.0, 2.0)):
    """Population coefficient paths of Figure 3.18: G = X^T X = [[1, rho], [rho, 1]], c = G beta."""
    G = np.array([[1.0, rho], [rho, 1.0]])
    beta = np.asarray(beta, float)
    c = G @ beta
    # Cholesky 'data' with X^T X = G and X^T y = c, so the sample algorithms apply unchanged
    L = np.linalg.cholesky(G)
    X = L.T                                     # 2 x 2 with X^T X = G
    y = np.linalg.solve(X.T, c)                # X^T y = c
    out = {}
    lams = np.r_[np.logspace(4, -4, 400), 0.0]
    out["ridge"] = np.array([np.linalg.solve(G + l * np.eye(2), c) for l in lams])
    out["lasso"] = lars(X, y, "lasso", centred_data=False)["beta"]
    j = int(np.argmax(np.abs(c)))
    b1 = np.zeros(2); b1[j] = c[j] / G[j, j]
    out["best"] = np.array([[0, 0], b1, beta])
    w, V = np.linalg.eigh(G)
    v1 = V[:, np.argmax(w)]
    out["pcr"] = np.array([[0, 0], v1 * (v1 @ c) / w.max(), beta])
    out["pls"] = pls(X, y, 2)
    out["ls"] = beta
    return out


def fig_3_18(out_dir=None):
    """Coefficient paths for two inputs with correlation +0.5 and -0.5, beta = (4, 2)."""
    fig, axes = plt.subplots(2, 1, figsize=(4.8, 7.6))
    res = {}
    for ax, rho in zip(axes, (0.5, -0.5)):
        P = two_input_paths(rho)
        res[rho] = P
        for key, name, col, ls in (("ridge", "Ridge", RED, "-"), ("best", "Best Subset", BLUE, "-"),
                                   ("pcr", "PCR", PURPLE, "-"), ("pls", "PLS", ORANGE, "--"), ("lasso", "Lasso", GREEN, "--")):
            B = P[key]
            ax.plot(B[:, 0], B[:, 1], color=col, lw=1.6, ls=ls, label=name)
        ax.plot(4, 2, "ko", ms=4); ax.text(4.12, 1.95, "Least Squares", fontsize=8)
        ax.axhline(0, color=GREY, lw=0.6, ls="--"); ax.axvline(0, color=GREY, lw=0.6, ls="--")
        ax.set_xlim(-0.5, 6.5); ax.set_ylim(-1.5, 3.3)
        ax.set_title("$\\rho = %s$" % rho)
        ax.set_xlabel("$\\beta_1$"); ax.set_ylabel("$\\beta_2$")
    axes[0].legend(frameon=False, fontsize=8, loc="center right")
    fig.tight_layout()
    savefig(fig, CH, "fig3-18", out_dir)
    return res


def fig_3_19(out_dir=None):
    """Incremental forward stagewise (eps = 0.01) and FS0 profiles on the prostate data."""
    D = load_prostate()
    Xc, yc, _, _ = centred(D["Xtr"], D["ytr"])
    # steps of eps = 0.01 on the scale of the standardised (unit-variance) predictors, as the book's
    # axis suggests; all columns have the same norm, so the largest inner product is the largest
    # correlation and Algorithm 3.4 is unchanged
    B = incremental_fs(Xc, yc, 0.01, 300)
    P = lars(Xc, yc, "fs0")
    al = arc_length(P["beta"])
    fig, axes = plt.subplots(1, 2, figsize=(8.4, 3.8), sharey=True)
    for j in range(8):
        axes[0].plot(np.arange(len(B)), B[:, j], color=PCOL[j], lw=1.2)
        axes[1].plot(al, P["beta"][:, j], color=PCOL[j], lw=1.2)
    _label_paths(axes[0], len(B) - 1, B, dx=3)
    _label_paths(axes[1], al[-1], P["beta"], dx=0.03)
    for ax, t in zip(axes, ("FS$_\\epsilon$", "FS$_0$")):
        ax.axhline(0, color=GREY, lw=0.6, ls="--")
        ax.set_title(t)
    axes[0].set_xlabel("Iteration"); axes[1].set_xlabel("$L_1$ arc-length of coefficients")
    axes[0].set_ylabel("Coefficients")
    axes[0].set_xlim(0, 300); axes[1].set_xlim(0, al[-1] * 1.22)
    fig.tight_layout()
    savefig(fig, CH, "fig3-19", out_dir)
    return dict(fs_eps=B, fs0=P)


def fig_3_20(out_dir=None):
    """The lasso penalty |beta|, SCAD (lambda = 1, a = 4) and |beta|^(1 - nu) with nu = 1/2."""
    b = np.linspace(-4, 4, 801)
    fig, axes = plt.subplots(1, 3, figsize=(8.4, 2.7))
    for ax, f, t in ((axes[0], np.abs(b), "$|\\beta|$"), (axes[1], scad_penalty(b), "SCAD"),
                     (axes[2], np.abs(b) ** 0.5, "$|\\beta|^{1-\\nu}$")):
        ax.plot(b, f, color=BLUE, lw=1.6)
        ax.set_title(t); ax.set_xlabel("$\\beta$")
    fig.tight_layout()
    savefig(fig, CH, "fig3-20", out_dir)


def print_tables():
    """Tables 3.1, 3.2, 3.3 and the F test (3.16), printed."""
    D = load_prostate()
    C = np.corrcoef(D["Xtr"].T)
    print("Table 3.1 (training correlations)")
    for i in range(1, 8):
        print("%8s " % NAMES[i] + " ".join("%6.3f" % C[i, j] for j in range(i)))
    fit = ols_fit(D["Xtr"], D["ytr"])
    print("Table 3.2")
    for n, b, s, z in zip(["Intercept"] + NAMES, fit["beta"], fit["se"], fit["z"]):
        print("%10s %6.2f %5.2f %6.2f" % (n, b, s, z))
    F = f_test(D["Xtr"], D["ytr"], [2, 5, 6, 7])
    print("F test (3.16): RSS0 %.2f RSS1 %.2f F %.3f p %.3f" % (F["rss0"], F["rss1"], F["F"], F["p"]))
    T = table_3_3()
    print("Table 3.3 (book tuning)")
    print("%10s " % "" + " ".join("%8s" % k[:8] for k in T))
    print("%10s " % "Intercept" + " ".join("%8.3f" % T[k]["intercept"] for k in T))
    for j in range(8):
        print("%10s " % NAMES[j] + " ".join("%8.3f" % T[k]["beta"][j] for k in T))
    print("%10s " % "Test" + " ".join("%8.3f" % T[k]["test"] for k in T))
    print("%10s " % "SE" + " ".join("%8.3f" % T[k]["se"] for k in T))


def tables(out_dir=None):
    """Print Tables 3.1-3.3, the computations of Exercises 3.2 and 3.17, and export the
    demonstration data (no figure)."""
    print_tables()
    B = band_simulation()
    print("Exercise 3.2: half-widths %.3f (pointwise) and %.3f (from (3.15)) times sigma-hat * sqrt(a^T (X^T X)^-1 a);"
          " pointwise coverage %.3f / %.3f, simultaneous coverage %.3f / %.3f"
          % (B["z"], B["c"], B["pointwise"][0].mean(), B["pointwise"][1].mean(), B["simultaneous"][0], B["simultaneous"][1]))
    print("Exercise 3.17 (spam data):")
    for k, v in spam_table().items():
        print("  %-17s param %-6s nonzero %2d  test MSE %.4f (%.4f)  misclassification %.4f"
              % (k, ("%.3g" % v["param"]), v["nonzero"], v["test"], v["se"], v["misclass"]))
    export_demo_data()


FIGURES = {"3.1": fig_3_1, "3.2": fig_3_2, "3.3": fig_3_3, "3.4": fig_3_4, "3.5": fig_3_5, "3.6": fig_3_6,
           "3.7": fig_3_7, "3.8": fig_3_8, "3.9": fig_3_9, "3.10": fig_3_10, "T3.4": table_3_4_fig,
           "3.11": fig_3_11, "3.12": fig_3_12, "3.13": fig_3_13, "3.14": fig_3_14, "3.15": fig_3_15,
           "3.16": fig_3_16, "3.17": fig_3_17, "3.18": fig_3_18, "3.19": fig_3_19, "3.20": fig_3_20,
           "tables": tables}

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