"""Chapter 6. Linear Model Selection and Regularization: the figures.

Course: Applied Statistical Learning in R and Python, following James, Witten, Hastie and
Tibshirani (2021), An Introduction to Statistical Learning with Applications in R, 2nd edition,
and James, Witten, Hastie, Tibshirani and Taylor (2023), the Python edition, Chapter 6.

Reproduces all 24 figures of the chapter:
  6.1   RSS and R^2 of all 2047 subset models of the Credit data
  6.2   Cp, BIC and adjusted R^2 of the best model of each size (Credit)
  6.3   square root of BIC, validation-set error and 10-fold CV error by size (Credit)
  6.4   standardised ridge coefficients on the Credit data against lambda and the l2 ratio
  6.5   squared bias, variance and test MSE of ridge regression (simulation, n = 50, p = 45)
  6.6   standardised lasso coefficients on the Credit data
  6.7   RSS contours and the lasso and ridge constraint regions (two predictors of the Hitters data)
  6.8   bias, variance and MSE of the lasso, and lasso against ridge, on the data of 6.5
  6.9   the same when only 2 of the 45 predictors affect the response
  6.10  ridge and lasso estimates against least squares when X = I (6.14)-(6.15)
  6.11  the Gaussian and the double-exponential (Laplace) prior densities
  6.12  leave-one-out CV error of ridge regression on the Credit data, and the coefficients
  6.13  10-fold CV error and coefficients of the lasso on one sparse simulated data set
  6.14  population and ad spending for 100 cities with the two principal component directions
  6.15  the first principal component: projections, and the rotated scatter
  6.16  first principal component scores against pop and ad
  6.17  second principal component scores against pop and ad
  6.18  bias, variance and MSE of principal components regression on the data of 6.8 and 6.9
  6.19  PCR, ridge and the lasso when the response depends on the first five components only
  6.20  PCR on the Credit data: standardised coefficients and 10-fold CV MSE against M
  6.21  first partial least squares direction against the first principal component direction
  6.22  least squares with n = 20 and with n = 2 observations
  6.23  R^2, training MSE and test MSE as unrelated features are added (n = 20)
  6.24  test MSE of the lasso with p = 20, 50 and 2000 features, 20 of them related (n = 100)
None is skipped. Two figures of the book use data that are not distributed with it, and are
redrawn from documented substitutes:
  * Figures 6.14-6.17 and 6.21 use "pop" and "ad" for 100 cities (not the Advertising data).
    We simulate 100 cities whose first principal component direction is close to the book's
    loadings (0.839, 0.544), and a sales response that depends mainly on pop.
  * Figure 6.7 is a schematic in the book; here the ellipses are the true RSS contours of the
    Hitters data restricted to the standardised predictors Hits and CRBI, and the marked points
    are the exact constrained solutions (6.8)-(6.9) for the budget s shown.
The simulations of Figures 6.5, 6.8, 6.9, 6.18 and 6.19 follow the book's description (n = 50,
p = 45, fixed inputs, noise variance 25, the error variance being the dashed line); bias and
variance are computed at the 50 training inputs, exactly for ridge and PCR (linear smoothers) and
by 400 Monte Carlo replicates for the lasso. The book's coefficients are not published, so the
curves have the book's shapes but not exactly its values.

Penalty scales. Ridge and lasso penalties are on the scale of (6.5) and (6.7), RSS + lambda * penalty,
with predictors standardised by (6.6). The lab (ch06_lab.py) uses glmnet's scale instead.

It also writes the JSON files for the three demonstrations:
  ../data/ch06-selection.json  Credit and Hitters: data, best subset / forward / backward models, CV by size
  ../data/ch06-shrinkage.json  Hitters: data, folds, CV curves of ridge and the lasso, 2-predictor geometry
  ../data/ch06-pcr-pls.json    Hitters: data and CV curves of PCR and PLS; the simulated cities

Run: python3 ch06_model_selection_regularization.py            (all figures and the JSON files)
     python3 ch06_model_selection_regularization.py --fig 6.4  (one figure)
The code is my own.
"""
import os

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

import itertools
import json
import warnings

import numpy as np
from sklearn.linear_model import lasso_path
from sklearn.cross_decomposition import PLSRegression

from common import (isl_data, savefig, run, plt, panel_grid, RED, BLUE, GREEN, MAGENTA, ORANGE,
                    PURPLE, GREY, HERE)

warnings.filterwarnings("ignore")
CH = 6
CACHE_DIR = os.path.join(HERE, "cache")
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
BLACK = "k"
VAR_C, BIAS_C, MSE_C = "#1b9e77", "black", "#c45bb5"     # the book's green / black / purple

# =========================================================================== data
def credit():
    """Credit data: X with 11 columns (Own, Student, Married as 0/1, Region as two dummies), y = Balance."""
    df = isl_data("Credit")
    X = df[["Income", "Limit", "Rating", "Cards", "Age", "Education"]].astype(float).copy()
    X["Own"] = (df["Own"] == "Yes").astype(float)
    X["Student"] = (df["Student"] == "Yes").astype(float)
    X["Married"] = (df["Married"] == "Yes").astype(float)
    X["South"] = (df["Region"] == "South").astype(float)
    X["West"] = (df["Region"] == "West").astype(float)
    return X.to_numpy(), df["Balance"].to_numpy(float), list(X.columns)


def hitters():
    """Hitters without the 59 missing salaries: X (263 x 19, R's model.matrix order), y = Salary."""
    df = isl_data("Hitters").dropna()
    num = ["AtBat", "Hits", "HmRun", "Runs", "RBI", "Walks", "Years", "CAtBat", "CHits", "CHmRun",
           "CRuns", "CRBI", "CWalks"]
    X = df[num].astype(float).copy()
    X["LeagueN"] = (df["League"] == "N").astype(float)
    X["DivisionW"] = (df["Division"] == "W").astype(float)
    for c in ["PutOuts", "Assists", "Errors"]:
        X[c] = df[c].astype(float)
    X["NewLeagueN"] = (df["NewLeague"] == "N").astype(float)
    return X.to_numpy(), df["Salary"].to_numpy(float), list(X.columns)


def standardize(X):
    """Centre and divide by the 1/n standard deviation, (6.6). Returns Z, means, sds."""
    m, s = X.mean(0), X.std(0)
    return (X - m) / s, m, s


# =========================================================================== subset selection
def all_subsets(X, y):
    """RSS (with an intercept) of every non-empty subset of the columns, by size.

    Uses RSS(S) = y_c'y_c - b_S' G_SS^{-1} b_S with G = Z'Z, b = Z'y_c for centred, scaled Z.
    Returns ({k: (combos array, rss array)}, TSS)."""
    Z, _, _ = standardize(X)
    yc = y - y.mean()
    G, b, tss = Z.T @ Z, Z.T @ yc, yc @ yc
    out = {}
    for k in range(1, X.shape[1] + 1):
        combos = np.array(list(itertools.combinations(range(X.shape[1]), k)))
        rss = np.empty(len(combos))
        for a in range(0, len(combos), 20000):
            c = combos[a:a + 20000]
            sol = np.linalg.solve(G[c[:, :, None], c[:, None, :]], b[c][..., None])[..., 0]
            rss[a:a + 20000] = tss - (b[c] * sol).sum(1)
        out[k] = (combos, rss)
    return out, tss


def best_subsets(X, y):
    """[(sorted column list, RSS)] for sizes 1..p (Algorithm 6.1, step 2), and TSS."""
    allc, tss = all_subsets(X, y)
    best = []
    for k in sorted(allc):
        c, r = allc[k]
        i = int(np.argmin(r))
        best.append((sorted(int(j) for j in c[i]), float(r[i])))
    return best, tss


def ols_fit(X, y, cols):
    """Intercept and coefficients of the least squares fit on the given columns."""
    A = np.column_stack([np.ones(len(y))] + [X[:, j] for j in cols])
    coef = np.linalg.lstsq(A, y, rcond=None)[0]
    return coef


def rss_cols(X, y, cols):
    A = np.column_stack([np.ones(len(y))] + [X[:, j] for j in cols])
    r = y - A @ np.linalg.lstsq(A, y, rcond=None)[0]
    return float(r @ r)


def forward_path(X, y):
    """Algorithm 6.2: list of models (column lists) of sizes 0..p, and the number of models fitted."""
    path, left, fitted = [[]], list(range(X.shape[1])), 1
    while left:
        scores = [(rss_cols(X, y, path[-1] + [j]), j) for j in left]
        fitted += len(scores)
        j = min(scores)[1]
        path.append(path[-1] + [j])
        left.remove(j)
    return path, fitted


def backward_path(X, y):
    """Algorithm 6.3: list of models of sizes 0..p (index = size), and the number of models fitted."""
    path, fitted = [list(range(X.shape[1]))], 1
    while path[-1]:
        cur = path[-1]
        scores = [(rss_cols(X, y, [c for c in cur if c != j]), j) for j in cur]
        fitted += len(scores)
        j = min(scores)[1]
        path.append([c for c in cur if c != j])
    return path[::-1], fitted


def criteria(rss, tss, n, sigma2):
    """Cp (6.2), BIC (6.3), adjusted R^2 (6.4) for models with d = 1..len(rss) predictors."""
    rss = np.asarray(rss)
    d = np.arange(1, len(rss) + 1)
    return {"Cp": (rss + 2 * d * sigma2) / n,
            "BIC": (rss + np.log(n) * d * sigma2) / n,
            "adjR2": 1 - (rss / (n - d - 1)) / (tss / (n - 1)),
            "R2": 1 - rss / tss}


def subset_cv(X, y, folds, method="best"):
    """K-fold CV error of the best d-variable model, the selection redone inside every fold.
    Returns (mean over folds, standard error) for d = 1..p."""
    K = folds.max() + 1
    p = X.shape[1]
    err = np.zeros((K, p))
    for k in range(K):
        tr, te = folds != k, folds == k
        if method == "best":
            models = [c for c, _ in best_subsets(X[tr], y[tr])[0]]
        else:
            models = forward_path(X[tr], y[tr])[0][1:]
        for i, cols in enumerate(models):
            coef = ols_fit(X[tr], y[tr], cols)
            pred = coef[0] + X[te][:, cols] @ coef[1:]
            err[k, i] = np.mean((y[te] - pred) ** 2)
    return err.mean(0), err.std(0, ddof=1) / np.sqrt(K)


def make_folds(n, K, seed):
    rng = np.random.default_rng(seed)
    return rng.permutation(np.arange(n) % K)


# =========================================================================== shrinkage
def ridge_path(Z, y, lams):
    """Ridge coefficients (6.5) for standardised Z and centred response: rows = lambdas."""
    U, d, Vt = np.linalg.svd(Z, full_matrices=False)
    uty = U.T @ (y - y.mean())
    return np.array([Vt.T @ (d / (d ** 2 + lam) * uty) for lam in lams])


def lasso_coefs(Z, y, lams, tol=1e-12):
    """Lasso coefficients (6.7), RSS + lambda * sum |beta_j|, for each lambda (rows).
    scikit-learn minimises RSS/(2n) + alpha*|beta|_1, so alpha = lambda / (2n)."""
    n = len(y)
    lams = np.asarray(lams, float)
    order = np.argsort(-lams)                                 # lasso_path wants decreasing alphas
    _, coefs, _ = lasso_path(Z, y - y.mean(), alphas=lams[order] / (2 * n), tol=tol, max_iter=200000)
    out = np.empty((len(lams), Z.shape[1]))
    out[order] = coefs.T
    return out


def soft_threshold(y, lam):
    """(6.15): the lasso estimate when X = I, minimising (y - b)^2 + lam |b|."""
    return np.sign(y) * np.maximum(np.abs(y) - lam / 2, 0.0)


def ridge_identity(y, lam):
    """(6.14): the ridge estimate when X = I, minimising (y - b)^2 + lam b^2."""
    return y / (1 + lam)


def hard_threshold(y, lam):
    """Best subset with penalty lam * #nonzero when X = I: keep y_j when y_j^2 > lam."""
    return np.where(y ** 2 > lam, y, 0.0)


def constrained_2d(Z2, y, s, kind):
    """Minimise RSS over (b1, b2) subject to |b1|+|b2| <= s (lasso) or b1^2+b2^2 <= s^2 (ridge,
    radius s), by bisection on the multiplier of the penalised form. Returns the solution."""
    yc = y - y.mean()
    ls = np.linalg.solve(Z2.T @ Z2, Z2.T @ yc)
    def norm(b):
        return np.abs(b).sum() if kind == "lasso" else np.sqrt(b @ b)
    if norm(ls) <= s:
        return ls
    def solve(lam):
        if kind == "lasso":
            return lasso_coefs(Z2, y, [lam])[0]
        return np.linalg.solve(Z2.T @ Z2 + lam * np.eye(2), Z2.T @ yc)
    lo, hi = 0.0, 1.0
    while norm(solve(hi)) > s:
        hi *= 2
    for _ in range(80):
        mid = 0.5 * (lo + hi)
        if norm(solve(mid)) > s:
            lo = mid
        else:
            hi = mid
    return solve(hi)


# =========================================================================== simulations
SIG2 = 25.0              # noise variance of the n = 50, p = 45 simulations (the dashed line)
N_SIM, P_SIM = 50, 45
N_MC = 400               # Monte Carlo replicates for the lasso


def sim_inputs(seed=2021, factors=False):
    """Fixed 50 x 45 standardised inputs. With factors=True the columns share five latent factors,
    so that the first five principal components carry most of the variance (Figure 6.19)."""
    rng = np.random.default_rng(seed)
    if factors:
        F = rng.standard_normal((N_SIM, 5)) * np.array([5.0, 4.0, 3.5, 3.0, 2.5])
        X = F @ rng.standard_normal((5, P_SIM)) / np.sqrt(5) + rng.standard_normal((N_SIM, P_SIM))
    else:
        X = rng.standard_normal((N_SIM, P_SIM))
    return standardize(X)[0]


def sim_truth(kind, Z, seed=7):
    """The noiseless response f at the 50 training inputs.
    dense: all 45 coefficients nonzero; sparse: only the first two; pcs: f lies in the span of the
    first five principal component score vectors. Scaled so that mean (f - mean f)^2 is 33 (dense,
    pcs) or 100 (sparse), the squared bias of the intercept-only model."""
    rng = np.random.default_rng(seed)
    if kind == "dense":
        f = Z @ rng.standard_normal(P_SIM)
        target = 33.0
    elif kind == "sparse":
        f = Z[:, 0] + Z[:, 1]
        target = 100.0
    else:
        U = np.linalg.svd(Z, full_matrices=False)[0]
        f = U[:, :5] @ np.array([1.0, -0.8, 0.7, 0.6, -0.5])
        target = 33.0
    f = f - f.mean()
    return 5.0 + f * np.sqrt(target / np.mean(f ** 2))


def ridge_bias_var(Z, f, lams, sig2=SIG2):
    """Exact in-sample squared bias, variance and expected test MSE of ridge regression."""
    n = len(f)
    U, d, _ = np.linalg.svd(Z, full_matrices=False)
    fc = f - f.mean()
    utf = U.T @ fc
    out = []
    for lam in lams:
        sh = d ** 2 / (d ** 2 + lam)
        resid = fc - U @ (sh * utf)
        b2 = resid @ resid / n
        v = sig2 * (1 + np.sum(sh ** 2)) / n
        out.append((b2, v, sig2 + b2 + v))
    return np.array(out)


def pcr_bias_var(Z, f, Ms, sig2=SIG2):
    """Exact in-sample squared bias, variance and test MSE of PCR with M = 0, 1, ... components."""
    n = len(f)
    U = np.linalg.svd(Z, full_matrices=False)[0]
    fc = f - f.mean()
    out = []
    for M in Ms:
        r = fc - U[:, :M] @ (U[:, :M].T @ fc)
        out.append((r @ r / n, sig2 * (M + 1) / n, sig2 + r @ r / n + sig2 * (M + 1) / n))
    return np.array(out)


def mc_fits(Z, f, lams, kind, n_mc=N_MC, seed=11, sig2=SIG2):
    """Monte Carlo over the noise: in-sample bias^2, variance, test MSE, mean training R^2 and the
    mean l1 (lasso) or l2 (ridge) norm ratio to least squares, for each lambda."""
    rng = np.random.default_rng(seed)
    n, L = len(f), len(lams)
    s1, s2 = np.zeros((L, n)), np.zeros((L, n))
    r2, ratio = np.zeros(L), np.zeros(L)
    for _ in range(n_mc):
        y = f + np.sqrt(sig2) * rng.standard_normal(n)
        B = lasso_coefs(Z, y, lams, tol=1e-9) if kind == "lasso" else ridge_path(Z, y, lams)
        ls = np.linalg.lstsq(Z, y - y.mean(), rcond=None)[0]
        F = y.mean() + B @ Z.T
        s1 += F
        s2 += F ** 2
        tss = np.sum((y - y.mean()) ** 2)
        r2 += 1 - ((y[None, :] - F) ** 2).sum(1) / tss
        if kind == "lasso":
            ratio += np.abs(B).sum(1) / np.abs(ls).sum()
        else:
            ratio += np.sqrt((B ** 2).sum(1)) / np.sqrt(ls @ ls)
    mean = s1 / n_mc
    var = (s2 / n_mc - mean ** 2).mean(1)
    bias2 = ((mean - f[None, :]) ** 2).mean(1)
    return {"bias2": bias2, "var": var, "mse": sig2 + bias2 + var, "r2": r2 / n_mc, "ratio": ratio / n_mc}


def cached(name, fn):
    """Compute fn() once and keep the arrays in cache/ch06-<name>.npz."""
    path = os.path.join(CACHE_DIR, "ch06-%s.npz" % name)
    if os.path.exists(path):
        z = np.load(path)
        return {k: z[k] for k in z.files}
    res = fn()
    os.makedirs(CACHE_DIR, exist_ok=True)
    np.savez(path, **res)
    return res


RIDGE_LAMS = 10 ** np.linspace(-2, 4, 61)
LASSO_LAMS = 10 ** np.linspace(-1.3, 3.3, 47)


def sim_results(kind):
    """Bias/variance/MSE curves for ridge (exact and Monte Carlo) and the lasso (Monte Carlo)."""
    def fn():
        Z = sim_inputs(factors=(kind == "pcs"))
        f = sim_truth(kind, Z)
        ex = ridge_bias_var(Z, f, RIDGE_LAMS)
        rmc = mc_fits(Z, f, RIDGE_LAMS, "ridge")
        lmc = mc_fits(Z, f, LASSO_LAMS, "lasso")
        pc = pcr_bias_var(Z, f, range(0, P_SIM + 1))
        return {"ridge_exact": ex, "ridge_r2": rmc["r2"], "ridge_ratio": rmc["ratio"],
                "ridge_mc": np.column_stack([rmc["bias2"], rmc["var"], rmc["mse"]]),
                "lasso": np.column_stack([lmc["bias2"], lmc["var"], lmc["mse"]]),
                "lasso_r2": lmc["r2"], "lasso_ratio": lmc["ratio"], "pcr": pc}
    return cached("sim-" + kind, fn)


def popad(seed=91):
    """Simulated pop (tens of thousands) and ad spending (thousands of dollars) for 100 cities,
    and sales; stands in for the data of Figures 6.14-6.17 and 6.21 (not distributed with the book)."""
    rng = np.random.default_rng(seed)
    u = np.array([0.839, 0.544])
    v = np.array([0.544, -0.839])
    z1 = rng.standard_normal(100) * 11.0
    z2 = rng.standard_normal(100) * 2.6
    X = np.array([38.0, 16.0]) + z1[:, None] * u + z2[:, None] * v
    sales = 2.0 + 0.30 * (X[:, 0] - 38) + 0.05 * (X[:, 1] - 16) + rng.standard_normal(100) * 1.5
    return X, sales


def pca2(X):
    """Principal component directions (columns, sign fixed so the first entry is positive) and
    scores of the centred, unstandardised data."""
    Xc = X - X.mean(0)
    vals, vecs = np.linalg.eigh(np.cov(Xc.T))
    vecs = vecs[:, ::-1]
    vecs = vecs * np.sign(vecs[0])
    return vecs, Xc @ vecs, vals[::-1]


# =========================================================================== figure helpers
def best_cross(ax, x, yv, color=BLUE):
    ax.plot([x], [yv], "x", color=color, ms=11, mew=2.2)


def bvm(ax, x, arr, ls="-", lw=1.5):
    ax.plot(x, arr[:, 0], color=BIAS_C, ls=ls, lw=lw)
    ax.plot(x, arr[:, 1], color=VAR_C, ls=ls, lw=lw)
    ax.plot(x, arr[:, 2], color=MSE_C, ls=ls, lw=lw)


def coef_colours(names):
    special = {"Income": "k", "Limit": RED, "Rating": BLUE, "Student": ORANGE}
    styles = {"Income": "-", "Limit": "--", "Rating": ":", "Student": "-."}
    return [(special.get(nm, "#bbbbbb"), styles.get(nm, "-"), 1.6 if nm in special else 0.9) for nm in names]


def draw_coefs(ax, x, B, names, legend=True):
    for j, (c, ls, lw) in enumerate(coef_colours(names)):
        ax.plot(x, B[:, j], color=c, ls=ls, lw=lw, label=names[j] if c != "#bbbbbb" else None)
    if legend:
        ax.legend(loc="upper right", fontsize=8, frameon=False)


# =========================================================================== Figures 6.1-6.3
def credit_subsets():
    X, y, names = credit()
    allc, tss = all_subsets(X, y)
    best, _ = best_subsets(X, y)
    return X, y, names, allc, tss, best


def fig6_1(out=None):
    """RSS and R^2 for all subsets of the Credit predictors."""
    X, y, names, allc, tss, best = credit_subsets()
    fig, axes = panel_grid(1, 2, size=(3.6, 3.2))
    rng = np.random.default_rng(0)
    for ax, kind in zip(axes[0], ["RSS", "R2"]):
        for k, (c, r) in allc.items():
            vals = r if kind == "RSS" else 1 - r / tss
            ax.plot(k + rng.uniform(-0.12, 0.12, len(vals)), vals, "o", ms=2.2, color="#9a9a9a", alpha=0.6)
        fr = [b[1] for b in best]
        ax.plot(range(1, 12), fr if kind == "RSS" else 1 - np.array(fr) / tss, "-o", color=RED, ms=3.5, lw=1.6)
        ax.set_xlabel("Number of predictors")
        ax.set_xticks(range(2, 12, 2))
    axes[0, 0].set_ylabel("Residual sum of squares")
    axes[0, 1].set_ylabel("$R^2$")
    axes[0, 1].set_ylim(0, 1)
    fig.tight_layout()
    savefig(fig, CH, "fig6-1", out)


def fig6_2(out=None):
    """Cp, BIC and adjusted R^2 of the best model of each size (Credit)."""
    X, y, names, allc, tss, best = credit_subsets()
    n = len(y)
    sigma2 = best[-1][1] / (n - X.shape[1] - 1)
    cr = criteria([b[1] for b in best], tss, n, sigma2)
    d = np.arange(1, 12)
    fig, axes = panel_grid(1, 3, size=(2.7, 2.7))
    for ax, key, lab in zip(axes[0], ["Cp", "BIC", "adjR2"], ["$C_p$", "BIC", "Adjusted $R^2$"]):
        ax.plot(d, cr[key], "-o", color=PURPLE, ms=3)
        i = int(np.argmax(cr[key]) if key == "adjR2" else np.argmin(cr[key]))
        best_cross(ax, d[i], cr[key][i])
        ax.set_xlabel("Number of predictors")
        ax.set_ylabel(lab)
        ax.set_xticks(range(2, 12, 2))
        if key != "adjR2":
            ax.set_ylim(8000, 31000)
        else:
            ax.set_ylim(0.86, 0.96)
    fig.tight_layout()
    savefig(fig, CH, "fig6-2", out)


def credit_cv_curves():
    """Square root of BIC, validation-set error (3/4 training) and 10-fold CV error by size."""
    def fn():
        X, y, names, allc, tss, best = credit_subsets()
        n = len(y)
        sigma2 = best[-1][1] / (n - 12)
        bic = criteria([b[1] for b in best], tss, n, sigma2)["BIC"]
        rng = np.random.default_rng(3)
        tr = np.zeros(n, bool)
        tr[rng.choice(n, 300, replace=False)] = True
        bt, _ = best_subsets(X[tr], y[tr])
        val, val_se = [], []
        for cols, _ in bt:
            coef = ols_fit(X[tr], y[tr], cols)
            e = (y[~tr] - coef[0] - X[~tr][:, cols] @ coef[1:]) ** 2
            val.append(e.mean())
            val_se.append(e.std(ddof=1) / np.sqrt(len(e)))
        cv, cv_se = subset_cv(X, y, make_folds(n, 10, 4))
        return {"bic": bic, "val": np.array(val), "val_se": np.array(val_se), "cv": cv, "cv_se": cv_se}
    return cached("credit-cv", fn)


def one_se(err, se):
    """Smallest size whose error is within one standard error of the minimum."""
    i = int(np.argmin(err))
    return int(np.nonzero(err <= err[i] + se[i])[0][0]) + 1


def fig6_3(out=None):
    """sqrt(BIC), validation error and 10-fold CV error for the best model of each size (Credit)."""
    R = credit_cv_curves()
    d = np.arange(1, 12)
    fig, axes = panel_grid(1, 3, size=(2.7, 2.7))
    for ax, vals, lab in zip(axes[0], [np.sqrt(R["bic"]), np.sqrt(R["val"]), np.sqrt(R["cv"])],
                             ["Square root of BIC", "Validation set error", "Cross-validation error"]):
        ax.plot(d, vals, "-o", color=PURPLE, ms=3)
        i = int(np.argmin(vals))
        best_cross(ax, d[i], vals[i])
        ax.set_xlabel("Number of predictors")
        ax.set_ylabel(lab)
        ax.set_ylim(90, 240)
        ax.set_xticks(range(2, 12, 2))
    fig.tight_layout()
    savefig(fig, CH, "fig6-3", out)


# =========================================================================== Figures 6.4, 6.6, 6.12, 6.20
CREDIT_RIDGE_LAMS = 10 ** np.linspace(-2, 5, 141)


def fig6_4(out=None):
    """Standardised ridge coefficients for the Credit data against lambda and the l2 ratio."""
    X, y, names = credit()
    Z, _, _ = standardize(X)
    B = ridge_path(Z, y, CREDIT_RIDGE_LAMS)
    ls = ridge_path(Z, y, [0.0])[0]
    ratio = np.sqrt((B ** 2).sum(1)) / np.sqrt(ls @ ls)
    fig, axes = panel_grid(1, 2, size=(3.7, 3.2))
    draw_coefs(axes[0, 0], CREDIT_RIDGE_LAMS, B, names)
    axes[0, 0].set_xscale("log")
    axes[0, 0].set_xlabel(r"$\lambda$")
    draw_coefs(axes[0, 1], ratio, B, names, legend=False)
    axes[0, 1].set_xlabel(r"$\|\hat\beta^R_\lambda\|_2\,/\,\|\hat\beta\|_2$")
    for ax in axes[0]:
        ax.set_ylabel("Standardized coefficients")
        ax.set_ylim(-320, 470)
    fig.tight_layout()
    savefig(fig, CH, "fig6-4", out)


def credit_lasso():
    X, y, names = credit()
    Z, _, _ = standardize(X)
    lmax = 2 * np.max(np.abs(Z.T @ (y - y.mean())))          # smallest lambda with all coefficients 0
    lams = lmax * 10 ** np.linspace(0, -4, 161)
    B = lasso_coefs(Z, y, lams)
    ls = ridge_path(Z, y, [0.0])[0]
    return lams, B, np.abs(B).sum(1) / np.abs(ls).sum(), names, lmax


def entry_order(lams, B, names):
    """The order in which coefficients first become nonzero as lambda decreases."""
    first = {}
    for i in np.argsort(-lams):
        for j in np.nonzero(B[i])[0]:
            first.setdefault(names[j], lams[i])
    return sorted(first.items(), key=lambda t: -t[1])


def fig6_6(out=None):
    """Standardised lasso coefficients for the Credit data against lambda and the l1 ratio."""
    lams, B, ratio, names, lmax = credit_lasso()
    fig, axes = panel_grid(1, 2, size=(3.7, 3.2))
    draw_coefs(axes[0, 0], lams, B, names)
    axes[0, 0].set_xscale("log")
    axes[0, 0].set_xlim(lams.min(), lmax * 1.2)
    axes[0, 0].set_xlabel(r"$\lambda$")
    draw_coefs(axes[0, 1], ratio, B, names, legend=False)
    axes[0, 1].set_xlabel(r"$\|\hat\beta^L_\lambda\|_1\,/\,\|\hat\beta\|_1$")
    for ax in axes[0]:
        ax.set_ylabel("Standardized coefficients")
        ax.set_ylim(-320, 470)
    fig.tight_layout()
    savefig(fig, CH, "fig6-6", out)


def credit_ridge_loocv(lams=10 ** np.linspace(-3, 1, 81)):
    """Exact leave-one-out CV for ridge on the Credit data, via the diagonal of the hat matrix."""
    X, y, names = credit()
    Z, _, _ = standardize(X)
    n = len(y)
    U, d, Vt = np.linalg.svd(Z, full_matrices=False)
    cv = []
    for lam in lams:
        sh = d ** 2 / (d ** 2 + lam)
        H = np.ones((n, n)) / n + (U * sh) @ U.T
        cv.append(np.mean(((y - H @ y) / (1 - np.diag(H))) ** 2))
    return lams, np.array(cv), ridge_path(Z, y, lams), names


def fig6_12(out=None):
    """Leave-one-out CV error of ridge regression on the Credit data, and the coefficients."""
    lams, cv, B, names = credit_ridge_loocv()
    i = int(np.argmin(cv))
    fig, axes = panel_grid(1, 2, size=(3.7, 3.1))
    axes[0, 0].plot(lams, cv, color=BLUE)
    axes[0, 0].set_ylabel("Leave-one-out CV error (MSE)")
    draw_coefs(axes[0, 1], lams, B, names)
    axes[0, 1].set_ylabel("Standardized coefficients")
    for ax in axes[0]:
        ax.set_xscale("log")
        ax.set_xlabel(r"$\lambda$")
        ax.axvline(lams[i], color=GREY, ls=":", lw=1.2)
    fig.tight_layout()
    savefig(fig, CH, "fig6-12", out)


def credit_pcr(folds_seed=5):
    """PCR on the standardised Credit data: coefficients on the standardised scale for M = 1..11
    and 10-fold CV MSE for M = 0..11 (standardisation and PCA redone inside every fold)."""
    X, y, names = credit()
    Z, _, _ = standardize(X)
    yc = y - y.mean()
    U, d, Vt = np.linalg.svd(Z, full_matrices=False)
    coefs = np.array([Vt[:M].T @ ((U[:, :M].T @ yc) / d[:M]) for M in range(1, 12)])
    folds = make_folds(len(y), 10, folds_seed)
    err = np.zeros((10, 12))
    for k in range(10):
        tr, te = folds != k, folds == k
        Zt, m, s = standardize(X[tr])
        Ut, dt, Vtt = np.linalg.svd(Zt, full_matrices=False)
        yt = y[tr] - y[tr].mean()
        Ze = (X[te] - m) / s
        for M in range(0, 12):
            b = Vtt[:M].T @ ((Ut[:, :M].T @ yt) / dt[:M]) if M else np.zeros(X.shape[1])
            err[k, M] = np.mean((y[te] - y[tr].mean() - Ze @ b) ** 2)
    return coefs, err.mean(0), names


def fig6_20(out=None):
    """PCR on the Credit data: standardised coefficients and 10-fold CV MSE against M."""
    coefs, cv, names = credit_pcr()
    fig, axes = panel_grid(1, 2, size=(3.7, 3.1))
    draw_coefs(axes[0, 0], np.arange(1, 12), coefs, names)
    axes[0, 0].set_ylabel("Standardized coefficients")
    axes[0, 0].set_xlabel("Number of components")
    axes[0, 1].plot(np.arange(0, 12), cv, "-o", color=PURPLE, ms=3)
    axes[0, 1].set_xlabel("Number of components")
    axes[0, 1].set_ylabel("Cross-validation MSE")
    axes[0, 1].set_xlim(0.5, 11.5)
    axes[0, 1].set_ylim(0, max(cv[1:]) * 1.1)
    fig.tight_layout()
    savefig(fig, CH, "fig6-20", out)


# =========================================================================== Figures 6.5, 6.8, 6.9, 6.13, 6.18, 6.19
def fig6_5(out=None):
    """Squared bias, variance and test MSE of ridge regression on the dense simulation."""
    R = sim_results("dense")
    ex = R["ridge_exact"]
    fig, axes = panel_grid(1, 2, size=(3.6, 3.0))
    for ax, x in zip(axes[0], [RIDGE_LAMS, R["ridge_ratio"]]):
        bvm(ax, x, ex)
        ax.axhline(SIG2, color=GREY, ls="--", lw=1)
        i = int(np.argmin(ex[:, 2]))
        ax.plot(x[i], ex[i, 2], "x", color=MSE_C, ms=11, mew=2)
        ax.set_ylabel("Mean squared error")
        ax.set_ylim(0, 62)
    axes[0, 0].set_xscale("log")
    axes[0, 0].set_xlabel(r"$\lambda$")
    axes[0, 1].set_xlabel(r"$\|\hat\beta^R_\lambda\|_2\,/\,\|\hat\beta\|_2$")
    fig.tight_layout()
    savefig(fig, CH, "fig6-5", out)


def lasso_vs_ridge(kind, name, ylim, out=None):
    R = sim_results(kind)
    la = R["lasso"]
    fig, axes = panel_grid(1, 2, size=(3.6, 3.0))
    ax = axes[0, 0]
    bvm(ax, LASSO_LAMS, la)
    i = int(np.argmin(la[:, 2]))
    ax.plot(LASSO_LAMS[i], la[i, 2], "x", color=MSE_C, ms=11, mew=2)
    ax.set_xscale("log")
    ax.set_xlabel(r"$\lambda$")
    ax = axes[0, 1]
    bvm(ax, R["lasso_r2"], la)
    bvm(ax, R["ridge_r2"], R["ridge_mc"], ls=":")
    ax.plot(R["lasso_r2"][i], la[i, 2], "x", color=MSE_C, ms=11, mew=2)
    ax.set_xlabel("$R^2$ on training data")
    ax.set_xlim(0.4 if kind == "sparse" else 0.0, 1.0)
    for ax in axes[0]:
        ax.axhline(SIG2, color=GREY, ls="--", lw=1)
        ax.set_ylim(*ylim)
        ax.set_ylabel("Mean squared error")
    fig.tight_layout()
    savefig(fig, CH, name, out)


def fig6_8(out=None):
    """Lasso bias/variance/MSE on the dense simulation, and lasso (solid) against ridge (dotted)."""
    lasso_vs_ridge("dense", "fig6-8", (0, 62), out)


def fig6_9(out=None):
    """The same as Figure 6.8 when only 2 of the 45 predictors are related to the response."""
    lasso_vs_ridge("sparse", "fig6-9", (0, 102), out)


def sparse_cv_lasso(seed=21):
    """One data set from the sparse simulation: 10-fold CV of the lasso along its path."""
    Z = sim_inputs()
    f = sim_truth("sparse", Z)
    rng = np.random.default_rng(seed)
    y = f + np.sqrt(SIG2) * rng.standard_normal(N_SIM)
    lmax = 2 * np.max(np.abs(Z.T @ (y - y.mean())))
    lams = lmax * 10 ** np.linspace(0, -6, 151)
    B = lasso_coefs(Z, y, lams)
    ls = np.linalg.lstsq(Z, y - y.mean(), rcond=None)[0]
    ratio = np.abs(B).sum(1) / np.abs(ls).sum()
    folds = make_folds(N_SIM, 10, seed + 1)
    err = np.zeros((10, len(lams)))
    for k in range(10):
        tr, te = folds != k, folds == k
        Zt, m, s = standardize(Z[tr])
        Bt = lasso_coefs(Zt, y[tr], lams)
        pred = y[tr].mean() + ((Z[te] - m) / s) @ Bt.T
        err[k] = ((y[te][:, None] - pred) ** 2).mean(0)
    return lams, B, ratio, err.mean(0), ls, err.std(0, ddof=1) / np.sqrt(10)


def fig6_13(out=None):
    """10-fold CV error and coefficients of the lasso on one sparse simulated data set."""
    lams, B, ratio, cv, ls, se = sparse_cv_lasso()
    i = int(np.argmin(cv))
    i1 = int(np.nonzero(cv <= cv[i] + se[i])[0].min())         # one-standard-error rule
    fig, axes = panel_grid(1, 2, size=(3.6, 3.0))
    axes[0, 0].plot(ratio, cv, color=MSE_C)
    axes[0, 0].set_ylabel("Cross-validation error")
    for j in range(P_SIM - 1, -1, -1):
        axes[0, 1].plot(ratio, B[:, j], color=[RED, BLUE][j] if j < 2 else "#b0b0b0", lw=1.6 if j < 2 else 0.8)
    axes[0, 1].set_ylabel("Standardized coefficients")
    for ax in axes[0]:
        ax.axvline(ratio[i], color=GREY, ls=":", lw=1.2)
        ax.axvline(ratio[i1], color=GREY, ls="--", lw=1.0)
        ax.set_xlabel(r"$\|\hat\beta^L_\lambda\|_1\,/\,\|\hat\beta\|_1$")
    fig.tight_layout()
    savefig(fig, CH, "fig6-13", out)


def fig6_18(out=None):
    """PCR bias/variance/MSE on the dense (left) and sparse (right) simulations."""
    fig, axes = panel_grid(1, 2, size=(3.6, 3.0))
    for ax, kind, top in zip(axes[0], ["dense", "sparse"], [72, 155]):
        pc = sim_results(kind)["pcr"]
        bvm(ax, np.arange(0, P_SIM + 1), pc)
        ax.axhline(SIG2, color=GREY, ls="--", lw=1)
        ax.set_ylim(0, top)
        ax.set_xlabel("Number of components")
        ax.set_ylabel("Mean squared error")
    axes[0, 1].legend(["Squared bias", "Variance", "Test MSE"], fontsize=8, frameon=False, loc="upper right")
    fig.tight_layout()
    savefig(fig, CH, "fig6-18", out)


def fig6_19(out=None):
    """PCR (left), ridge (dotted) and lasso (solid) when f depends on the first five components."""
    R = sim_results("pcs")
    fig, axes = panel_grid(1, 2, size=(3.6, 3.0))
    ax = axes[0, 0]
    bvm(ax, np.arange(0, P_SIM + 1), R["pcr"])
    ax.set_xlabel("Number of components")
    ax.set_title("PCR")
    ax = axes[0, 1]
    bvm(ax, R["lasso_ratio"], R["lasso"])
    bvm(ax, R["ridge_ratio"], R["ridge_exact"], ls=":")
    ax.set_xlabel("Shrinkage factor")
    ax.set_title("Ridge regression and lasso")
    for ax in axes[0]:
        ax.axhline(SIG2, color=GREY, ls="--", lw=1)
        ax.set_ylim(0, 72)
        ax.set_ylabel("Mean squared error")
    fig.tight_layout()
    savefig(fig, CH, "fig6-19", out)


# =========================================================================== Figures 6.7, 6.10, 6.11
GEOM_COLS = ("Hits", "CRBI")
GEOM_FRAC = 0.18          # the budget s as a fraction of the least squares norm


def geometry_data():
    """Standardised Hits and CRBI of the Hitters data, Salary, the least squares fit and the
    budgets used in Figure 6.7 (18% of the least squares l1 and l2 norms)."""
    X, y, names = hitters()
    Z, _, _ = standardize(X[:, [names.index(c) for c in GEOM_COLS]])
    yc = y - y.mean()
    ls = np.linalg.solve(Z.T @ Z, Z.T @ yc)
    return Z, y, ls


def fig6_7(out=None):
    """RSS contours, the lasso diamond and the ridge disc, with the exact constrained solutions."""
    Z, y, ls = geometry_data()
    yc = y - y.mean()
    G, b = Z.T @ Z, Z.T @ yc
    rss_ls = yc @ yc - b @ ls
    s_l, s_r = GEOM_FRAC * np.abs(ls).sum(), GEOM_FRAC * np.sqrt(ls @ ls)
    sol_l, sol_r = constrained_2d(Z, y, s_l, "lasso"), constrained_2d(Z, y, s_r, "ridge")
    fig, axes = panel_grid(1, 2, size=(3.4, 3.4))
    g = np.linspace(-110, 330, 300)
    B1, B2 = np.meshgrid(g, g)
    D1, D2 = B1 - ls[0], B2 - ls[1]
    Q = G[0, 0] * D1 ** 2 + 2 * G[0, 1] * D1 * D2 + G[1, 1] * D2 ** 2   # RSS - RSS(ls)
    for ax, sol, kind in zip(axes[0], [sol_l, sol_r], ["lasso", "ridge"]):
        if kind == "lasso":
            ax.fill([s_l, 0, -s_l, 0], [0, s_l, 0, -s_l], color="#6fa8dc", alpha=0.85)
        else:
            t = np.linspace(0, 2 * np.pi, 200)
            ax.fill(s_r * np.cos(t), s_r * np.sin(t), color="#6fa8dc", alpha=0.85)
        d = sol - ls
        q0 = d @ G @ d
        ax.contour(B1, B2, Q, levels=q0 * np.array([0.12, 0.35, 0.65, 1.0]), colors=RED, linewidths=1.1)
        ax.plot(*ls, "k.", ms=6)
        ax.annotate(r"$\hat\beta$", ls, xytext=(5, 4), textcoords="offset points")
        ax.plot(*sol, "o", color="k", ms=4)
        ax.axhline(0, color=GREY, lw=0.6)
        ax.axvline(0, color=GREY, lw=0.6)
        ax.set_xlim(-110, 330)
        ax.set_ylim(-110, 330)
        ax.set_aspect("equal")
        ax.set_xlabel(r"$\beta_1$ (Hits)")
        ax.set_ylabel(r"$\beta_2$ (CRBI)")
        ax.set_title("Lasso" if kind == "lasso" else "Ridge regression")
    fig.tight_layout()
    savefig(fig, CH, "fig6-7", out)


def fig6_10(out=None):
    """Ridge and lasso estimates against least squares when n = p and X = I (lambda = 1)."""
    yv = np.linspace(-1.5, 1.5, 301)
    fig, axes = panel_grid(1, 2, size=(3.4, 3.1))
    for ax, est, lab in zip(axes[0], [ridge_identity(yv, 1.0), soft_threshold(yv, 1.0)], ["Ridge", "Lasso"]):
        ax.plot(yv, yv, color=GREY, ls="--", lw=1.2, label="Least squares")
        ax.plot(yv, est, color=RED, lw=1.8, label=lab)
        ax.axhline(0, color="#dddddd", lw=0.6)
        ax.set_xlabel("$y_j$")
        ax.set_ylabel("Coefficient estimate")
        ax.legend(loc="upper left", fontsize=8.5, frameon=False)
    fig.tight_layout()
    savefig(fig, CH, "fig6-10", out)


def fig6_11(out=None):
    """The Gaussian (ridge) and double-exponential (lasso) priors g(beta_j)."""
    b = np.linspace(-3, 3, 601)
    fig, axes = panel_grid(1, 2, size=(3.4, 3.0))
    axes[0, 0].plot(b, np.exp(-b ** 2 / 2) / np.sqrt(2 * np.pi), color=BLUE)
    axes[0, 1].plot(b, 0.5 * np.exp(-np.abs(b)), color=BLUE)
    for ax in axes[0]:
        ax.set_ylim(0, 0.7)
        ax.set_xlabel(r"$\beta_j$")
        ax.set_ylabel(r"$g(\beta_j)$")
    fig.tight_layout()
    savefig(fig, CH, "fig6-11", out)


# =========================================================================== Figures 6.14-6.17, 6.21
def fig6_14(out=None):
    """pop and ad for 100 simulated cities, with the two principal component directions."""
    X, _ = popad()
    V, S, _ = pca2(X)
    m = X.mean(0)
    fig, ax = plt.subplots(figsize=(4.2, 3.6))
    ax.plot(X[:, 0], X[:, 1], "o", mfc="none", mec=PURPLE, ms=5)
    t = np.array([-40, 40])
    ax.plot(m[0] + t * V[0, 0], m[1] + t * V[1, 0], color=GREEN, lw=2)
    ax.plot(m[0] + t * V[0, 1] / 2, m[1] + t * V[1, 1] / 2, color=BLUE, ls="--", lw=2)
    ax.set_xlim(8, 72)
    ax.set_ylim(0, 37)
    ax.set_xlabel("Population")
    ax.set_ylabel("Ad Spending")
    savefig(fig, CH, "fig6-14", out)


def popad_subset():
    X, _ = popad()
    idx = np.nonzero(np.abs(X[:, 0] - 38) < 14)[0][::2]
    return X, idx


def fig6_15(out=None):
    """A subset of the cities: projections on the first component, and the rotated scatter."""
    X, idx = popad_subset()
    V, S, _ = pca2(X)
    m = X.mean(0)
    fig, axes = panel_grid(1, 2, size=(3.6, 3.2))
    ax = axes[0, 0]
    ax.plot(X[idx, 0], X[idx, 1], "o", mfc="none", mec=PURPLE, ms=5)
    t = np.array([-30, 30])
    ax.plot(m[0] + t * V[0, 0], m[1] + t * V[1, 0], color=GREEN, lw=2)
    proj = m + S[idx, :1] * V[:, 0]
    for a, bpt in zip(X[idx], proj):
        ax.plot([a[0], bpt[0]], [a[1], bpt[1]], "k--", lw=0.7)
    ax.plot(proj[:, 0], proj[:, 1], "kx", ms=4)
    ax.plot(*m, "o", color=BLUE, ms=6)
    ax.set_xlabel("Population")
    ax.set_ylabel("Ad Spending")
    ax.set_xlim(18, 58)
    ax.set_ylim(1, 34)
    ax.set_aspect("equal")
    ax = axes[0, 1]
    ax.plot(S[idx, 0], S[idx, 1], "o", mfc="none", mec=PURPLE, ms=5)
    ax.axhline(0, color=GREEN, lw=2)
    ax.plot(S[idx, 0], np.zeros(len(idx)), "kx", ms=4)
    ax.set_xlabel("1st Principal Component")
    ax.set_ylabel("2nd Principal Component")
    ax.set_ylim(-11, 11)
    fig.tight_layout()
    savefig(fig, CH, "fig6-15", out)


def scores_vs(name, comp, out=None):
    X, idx = popad_subset()
    Xs = (X - X.mean(0)) / X.std(0, ddof=1)
    V, S, _ = pca2(Xs)                                        # standardised, as the book's footnote says
    fig, axes = panel_grid(1, 2, size=(3.4, 3.0))
    for j, (ax, lab) in enumerate(zip(axes[0], ["Population", "Ad Spending"])):
        ax.plot(S[idx, comp], X[idx, j], "o", mfc="none", mec=PURPLE, ms=5)
        ax.set_xlabel(["1st", "2nd"][comp] + " Principal Component")
        ax.set_ylabel(lab)
    fig.tight_layout()
    savefig(fig, CH, name, out)


def fig6_16(out=None):
    """First principal component scores (standardised data) against pop and ad."""
    scores_vs("fig6-16", 0, out)


def fig6_17(out=None):
    """Second principal component scores against pop and ad."""
    scores_vs("fig6-17", 1, out)


def pls_direction(X, y):
    """First PLS direction of the centred, unstandardised data: proportional to X_c' y_c."""
    w = (X - X.mean(0)).T @ (y - y.mean())
    return w / np.linalg.norm(w) * np.sign(w[0])


def fig6_21(out=None):
    """First PLS direction (solid) and first principal component direction (dotted)."""
    X, sales = popad()
    V, _, _ = pca2(X)
    w = pls_direction(X, sales)
    m = X.mean(0)
    fig, ax = plt.subplots(figsize=(4.2, 3.6))
    ax.plot(X[:, 0], X[:, 1], "o", mfc="none", mec=PURPLE, ms=5)
    t = np.array([-40, 40])
    ax.plot(m[0] + t * w[0], m[1] + t * w[1], color=GREEN, lw=2, label="first PLS direction")
    ax.plot(m[0] + t * V[0, 0], m[1] + t * V[1, 0], color="k", ls=":", lw=2, label="first PCR direction")
    ax.set_xlim(8, 72)
    ax.set_ylim(0, 37)
    ax.set_xlabel("Population")
    ax.set_ylabel("Ad Spending")
    ax.legend(loc="upper left", fontsize=8.5, frameon=False)
    savefig(fig, CH, "fig6-21", out)


# =========================================================================== Figures 6.22-6.24
def fig6_22(out=None):
    """Least squares with 20 observations (left) and with 2 (right)."""
    rng = np.random.default_rng(22)
    x = rng.uniform(-1.5, 1.0, 20)
    y = 1.5 + 3.0 * x + rng.standard_normal(20) * 3.0
    fig, axes = panel_grid(1, 2, size=(3.3, 3.0))
    for ax, idx in zip(axes[0], [np.arange(20), np.array([3, 11])]):
        b = np.polyfit(x[idx], y[idx], 1)
        ax.plot(x[idx], y[idx], "o", color=RED, ms=5)
        g = np.array([-1.6, 1.1])
        ax.plot(g, np.polyval(b, g), color="k", lw=1.6)
        ax.set_xlim(-1.6, 1.1)
        ax.set_ylim(-11, 11)
        ax.set_xlabel("X")
        ax.set_ylabel("Y")
    fig.tight_layout()
    savefig(fig, CH, "fig6-22", out)


def noise_features(seed=23, n=20, n_test=1000, pmax=19, n_rep=200):
    """Unrelated features added one at a time to least squares (n = 20, plus an intercept):
    medians over n_rep data sets of R^2, training MSE and test MSE, for p = 1..19."""
    rng = np.random.default_rng(seed)
    R = np.zeros((n_rep, pmax, 3))
    for r in range(n_rep):
        X = rng.standard_normal((n, pmax))
        y = rng.standard_normal(n)
        Xt = rng.standard_normal((n_test, pmax))
        yt = rng.standard_normal(n_test)
        for p in range(1, pmax + 1):
            A = np.column_stack([np.ones(n), X[:, :p]])
            b = np.linalg.lstsq(A, y, rcond=None)[0]
            res = y - A @ b
            te = yt - np.column_stack([np.ones(n_test), Xt[:, :p]]) @ b
            R[r, p - 1] = (1 - res @ res / np.sum((y - y.mean()) ** 2), res @ res / n, te @ te / n_test)
    return np.median(R, axis=0)


def fig6_23(out=None):
    """R^2, training MSE and test MSE against the number of unrelated features (n = 20)."""
    R = noise_features()
    p = np.arange(1, len(R) + 1)
    fig, axes = panel_grid(1, 3, size=(2.6, 2.6))
    axes[0, 0].plot(p, R[:, 0], color=RED)
    axes[0, 0].set_ylabel("$R^2$")
    axes[0, 1].plot(p, R[:, 1], color=RED)
    axes[0, 1].set_ylabel("Training MSE")
    axes[0, 2].plot(p, R[:, 2], color=RED)
    axes[0, 2].set_yscale("log")
    axes[0, 2].set_ylabel("Test MSE")
    for ax in axes[0]:
        ax.set_xlabel("Number of Variables")
    fig.tight_layout()
    savefig(fig, CH, "fig6-23", out)


HD_FRACS = {20: (1.01, 0.3, 0.001), 50: (1.01, 0.16, 0.001), 2000: (1.01, 0.2, 0.01)}


def high_dim_lasso(n_rep=40, seed=24, n=100, n_test=500):
    """Lasso with n = 100 and p = 20, 50, 2000 features, 20 of them related to y (sd of noise 1).
    lambda is set to three fixed fractions of lambda_max in each replicate; returns test MSEs and
    the mean degrees of freedom (number of nonzero coefficients plus one for the intercept)."""
    def fn():
        rng = np.random.default_rng(seed)
        beta20 = rng.choice([-1, 1], 20) * 0.3
        res = {}
        for p in (20, 50, 2000):
            mse, df = np.zeros((n_rep, 3)), np.zeros((n_rep, 3))
            for r in range(n_rep):
                X = rng.standard_normal((n, p))
                Xt = rng.standard_normal((n_test, p))
                y = X[:, :20] @ beta20 + rng.standard_normal(n)
                yt = Xt[:, :20] @ beta20 + rng.standard_normal(n_test)
                Z, m, s = standardize(X)
                lmax = 2 * np.max(np.abs(Z.T @ (y - y.mean())))
                B = lasso_coefs(Z, y, [f * lmax for f in HD_FRACS[p]], tol=1e-8)
                for i in range(3):
                    pred = y.mean() + ((Xt - m) / s) @ B[i]
                    mse[r, i] = np.mean((yt - pred) ** 2)
                    df[r, i] = 1 + np.count_nonzero(B[i])
            res["mse%d" % p], res["df%d" % p] = mse, df
        return res
    return cached("highdim", fn)


def fig6_24(out=None):
    """Test MSE of the lasso for p = 20, 50, 2000 at three amounts of regularisation."""
    R = high_dim_lasso()
    fig, axes = panel_grid(1, 3, size=(2.6, 2.8))
    for ax, p in zip(axes[0], (20, 50, 2000)):
        bp = ax.boxplot(R["mse%d" % p], patch_artist=True, widths=0.55, medianprops=dict(color="k", lw=2))
        for box in bp["boxes"]:
            box.set_facecolor("#5fd3e6")
        ax.set_xticks([1, 2, 3])
        ax.set_xticklabels(["%d" % round(v) for v in R["df%d" % p].mean(0)])
        ax.set_ylim(0, 5)
        ax.set_title("$p = %d$" % p)
        ax.set_xlabel("Degrees of Freedom")
    fig.tight_layout()
    savefig(fig, CH, "fig6-24", out)


# =========================================================================== demo data
def glmnet_ridge(X, y, lam):
    """Ridge on glmnet's scale (see ch06_lab.py): intercept and coefficients on the original scale."""
    Z, m, s = standardize(X)
    b = np.linalg.solve(Z.T @ Z + len(y) * lam / y.std() * np.eye(X.shape[1]), Z.T @ (y - y.mean()))
    beta = b / s
    return y.mean() - m @ beta, beta


def glmnet_lasso(X, y, lam):
    """Lasso on glmnet's scale: RSS/(2n) + lam |beta|_1 with standardised columns."""
    Z, m, s = standardize(X)
    b = lasso_coefs(Z, y, [2 * len(y) * lam])[0]
    beta = b / s
    return y.mean() - m @ beta, beta


HIT_FOLDS_SEED = 61
HIT_RIDGE_LAMS = 10 ** np.linspace(5, -1, 61)
HIT_LASSO_LAMS = 10 ** np.linspace(2.6, -1, 61)


def hitters_lambda_cv():
    """10-fold CV (fixed folds) of ridge and the lasso on all 263 players, glmnet's lambda scale."""
    def fn():
        X, y, names = hitters()
        folds = make_folds(len(y), 10, HIT_FOLDS_SEED)
        out = {"folds": folds}
        for kind, lams, fit in [("ridge", HIT_RIDGE_LAMS, glmnet_ridge), ("lasso", HIT_LASSO_LAMS, glmnet_lasso)]:
            err = np.zeros((10, len(lams)))
            for k in range(10):
                tr, te = folds != k, folds == k
                for i, lam in enumerate(lams):
                    b0, b = fit(X[tr], y[tr], lam)
                    err[k, i] = np.mean((y[te] - b0 - X[te] @ b) ** 2)
            out[kind + "_cv"], out[kind + "_se"] = err.mean(0), err.std(0, ddof=1) / np.sqrt(10)
        return out
    return cached("hitters-lambda-cv", fn)


def hitters_pcr_pls_cv():
    """10-fold CV MSE (same folds) of PCR and PLS on all 263 players, M = 0..19; and the training
    fractions of X and y variance explained."""
    def fn():
        X, y, names = hitters()
        folds = make_folds(len(y), 10, HIT_FOLDS_SEED)
        p = X.shape[1]
        err = {"pcr": np.zeros((10, p + 1)), "pls": np.zeros((10, p + 1))}
        for k in range(10):
            tr, te = folds != k, folds == k
            for M in range(p + 1):
                for kind in ("pcr", "pls"):
                    pred = pcr_pls_predict(X[tr], y[tr], X[te], M, kind)
                    err[kind][k, M] = np.mean((y[te] - pred) ** 2)
        return {"pcr_cv": err["pcr"].mean(0), "pls_cv": err["pls"].mean(0)}
    return cached("hitters-pcr-pls-cv", fn)


def pcr_pls_fit(X, y, M, kind):
    """PCR or PLS (PLS1 by NIPALS) with M components on the standardised (1/n sd) columns.
    Returns (means, sds, beta on the standardised scale, X-variance fraction, y-variance fraction)."""
    Z, m, s = standardize(X)
    yc = y - y.mean()
    p = X.shape[1]
    if M == 0:
        return m, s, np.zeros(p), 0.0, 0.0
    if kind == "pcr":
        U, d, Vt = np.linalg.svd(Z, full_matrices=False)
        beta = Vt[:M].T @ ((U[:, :M].T @ yc) / d[:M])
        xfrac = np.sum(d[:M] ** 2) / np.sum(d ** 2)
    else:
        E, W, P, Q, T = Z.copy(), [], [], [], []
        f = yc.copy()
        for _ in range(M):
            w = E.T @ f
            w /= np.linalg.norm(w)
            t = E @ w
            tt = t @ t
            pl = E.T @ t / tt
            q = f @ t / tt
            E = E - np.outer(t, pl)
            f = f - q * t
            W.append(w), P.append(pl), Q.append(q), T.append(t)
        W, P, Q = np.array(W).T, np.array(P).T, np.array(Q)
        beta = W @ np.linalg.solve(P.T @ W, Q)
        xfrac = sum((t @ t) * (pl @ pl) for t, pl in zip(T, P.T)) / np.sum(Z ** 2)
    r = yc - Z @ beta
    return m, s, beta, float(xfrac), float(1 - r @ r / (yc @ yc))


def pcr_pls_predict(Xtr, ytr, Xte, M, kind):
    m, s, beta, _, _ = pcr_pls_fit(Xtr, ytr, M, kind)
    return ytr.mean() + ((Xte - m) / s) @ beta


def r4(a, d=4):
    return [round(float(v), d) for v in np.ravel(a)]


def selection_json(X, y, names, folds_seed):
    best, tss = best_subsets(X, y)
    fwd, nf = forward_path(X, y)
    bwd, nb = backward_path(X, y)
    folds = make_folds(len(y), 10, folds_seed)
    cv, se = subset_cv(X, y, folds)
    return {"names": names, "X": [r4(r, 3) for r in X], "y": r4(y, 3), "n": len(y), "tss": float(tss),
            "best": [[c, r] for c, r in best],
            "forward": [[sorted(c), rss_cols(X, y, c)] for c in fwd[1:]],
            "backward": [[sorted(c), rss_cols(X, y, c)] for c in bwd[1:]],
            "fitted": {"best": 2 ** X.shape[1], "forward": nf, "backward": nb},
            "cv": r4(cv, 1), "cv_se": r4(se, 1)}


def export_data(out=None):
    """Write the JSON files used by the three demonstrations."""
    os.makedirs(DATA_OUT, exist_ok=True)
    Xc, yc, nc = credit()
    Xh, yh, nh = hitters()
    sel = {"credit": selection_json(Xc, yc, nc, 4), "hitters": selection_json(Xh, yh, nh, HIT_FOLDS_SEED)}
    with open(os.path.join(DATA_OUT, "ch06-selection.json"), "w") as f:
        json.dump(sel, f, separators=(",", ":"))
    L = hitters_lambda_cv()
    Z2, y2, ls2 = geometry_data()
    shr = {"names": nh, "X": [r4(r, 3) for r in Xh], "y": r4(yh, 3),
           "ridge_lams": r4(HIT_RIDGE_LAMS, 6), "lasso_lams": r4(HIT_LASSO_LAMS, 6),
           "ridge_cv": r4(L["ridge_cv"], 1), "ridge_se": r4(L["ridge_se"], 1),
           "lasso_cv": r4(L["lasso_cv"], 1), "lasso_se": r4(L["lasso_se"], 1),
           "geom": {"cols": list(GEOM_COLS), "G": r4(Z2.T @ Z2, 6), "b": r4(Z2.T @ (y2 - y2.mean()), 6),
                    "yty": float(np.sum((y2 - y2.mean()) ** 2)), "ls": r4(ls2, 6)}}
    with open(os.path.join(DATA_OUT, "ch06-shrinkage.json"), "w") as f:
        json.dump(shr, f, separators=(",", ":"))
    P = hitters_pcr_pls_cv()
    Xp, sales = popad()
    pp = {"names": nh, "X": [r4(r, 3) for r in Xh], "y": r4(yh, 3),
          "pcr_cv": r4(P["pcr_cv"], 1), "pls_cv": r4(P["pls_cv"], 1),
          "cities": {"pop": r4(Xp[:, 0], 3), "ad": r4(Xp[:, 1], 3),
                     "pop_effect": 0.30, "ad_effect": 0.05, "noise": r4(sales - 2.0 - 0.30 * (Xp[:, 0] - 38)
                                                                        - 0.05 * (Xp[:, 1] - 16), 4)}}
    with open(os.path.join(DATA_OUT, "ch06-pcr-pls.json"), "w") as f:
        json.dump(pp, f, separators=(",", ":"))
    for nm in ("ch06-selection.json", "ch06-shrinkage.json", "ch06-pcr-pls.json"):
        print("wrote ../data/%s (%.0f kB)" % (nm, os.path.getsize(os.path.join(DATA_OUT, nm)) / 1024))


FIGURES = {
    "6.1": fig6_1, "6.2": fig6_2, "6.3": fig6_3, "6.4": fig6_4, "6.5": fig6_5, "6.6": fig6_6,
    "6.7": fig6_7, "6.8": fig6_8, "6.9": fig6_9, "6.10": fig6_10, "6.11": fig6_11, "6.12": fig6_12,
    "6.13": fig6_13, "6.14": fig6_14, "6.15": fig6_15, "6.16": fig6_16, "6.17": fig6_17,
    "6.18": fig6_18, "6.19": fig6_19, "6.20": fig6_20, "6.21": fig6_21, "6.22": fig6_22,
    "6.23": fig6_23, "6.24": fig6_24, "data": export_data,
}

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