"""James et al. (2021, 2023), Chapter 5: Resampling Methods.

Reproduces the figures of Chapter 5 of G. James, D. Witten, T. Hastie and R. Tibshirani, An
Introduction to Statistical Learning with Applications in R, 2nd edition (Springer, 2021), whose
text and figures are shared with the Python edition (James, Witten, Hastie, Tibshirani and Taylor,
2023). Written from scratch with numpy, scipy and matplotlib; every method is a small function meant
to be read next to the lecture notes (../ch05-resampling-methods.html):

* Section 5.1, cross-validation: OrthoPoly (orthogonal polynomials, as R's poly()), validation_mse
  (the validation set approach), loocv_shortcut (formula (5.2), leverages from a QR decomposition),
  loocv_brute (definition (5.1), n refits), kfold_cv ((5.3), and the fold-size weighted variant used
  by R's cv.glm), SmoothingSpline (the cubic smoothing spline by the Reinsch algorithm, with its
  smoother matrix, degrees of freedom and the LOOCV shortcut for linear smoothers), logistic_fit
  (Newton's method for logistic regression on polynomial features, (5.5)), knn_predict.
* Section 5.2, the bootstrap: alpha_hat ((5.7)), bootstrap ((5.8)), alpha_se_normal (the exact
  standard error of alpha-hat under bivariate normality, via its least-squares form),
  inclusion_prob and distinct_count_pmf (Exercise 5.2: the chance that an observation is in a
  bootstrap sample, and the exact distribution of the number of distinct observations).
* Studies behind the "Filling the gap" boxes of the notes: ols_expected_error (the expected test
  error of least squares with m Gaussian training points), cv_study (bias and spread of CV(k) for
  k = 2, 5, 10, n against the true error, by simulation), sandwich_se (the heteroscedasticity-robust
  standard errors that the pairs bootstrap approximates).

Figures reproduced: 5.2, 5.4, 5.6, 5.7, 5.8, 5.9 and 5.10, plus two exercise figures (Exercise 5.2(g),
saved as fig5-ex2, and Exercise 5.8(b), saved as fig5-ex8). Figures 5.1, 5.3, 5.5 and 5.11 are
schematic drawings of how the observations are split or resampled, with no data or computation in
them, and are skipped. Run `python3 ch05_resampling_methods.py --list`, `python3
ch05_resampling_methods.py` (all figures, about a minute) or `python3 ch05_resampling_methods.py
--fig 5.4`. Files go to ../img/ch05/; `--fig data` writes the demonstrations' data to ../data/.

Data: Auto (the 392 cars with a recorded horsepower) and Portfolio, read by common.isl_data().

Settings chosen where the book gives none:
* Figure 5.2: the eleven training/validation splits (one on the left, ten on the right) are random
  halves of the 392 cars drawn with numpy default_rng(2021); Figure 5.4: the nine 10-fold partitions
  come from default_rng(2023) (folds of 40 or 39 cars).
* Figure 5.6: the three simulated data sets of Figures 2.9-2.11 are not published. Here each has
  n = 50 inputs uniform on [0, 100] (default_rng(29), (30), (31)) and noise N(0, 1), with truths
  f1(x) = 4.5 + 5 sin^2(pi x / 130) (a smooth bump), f2(x) = 2.5 + 0.1 x + 0.3 sin(x / 15) (almost
  linear) and f3(x) = 10 + 18.5 u^3 - 1.5 u^2 with u = (50 - x) / 50 (strongly nonlinear). Flexibility
  is the degrees of freedom of a cubic smoothing spline; the true test MSE is 1 + the average of
  (f - f_hat)^2 over a fine grid; 10-fold CV uses the lambda of the full-data fit in every fold.
* Figures 5.7-5.8: the two-class data of Figure 2.13 are not published either. Here each class is an
  equal mixture of ten Gaussians N(c_k, 0.22 I) with centres c_k drawn once (default_rng(50)) from
  N((-0.5, 0.8), I) and N((0.8, -0.5), I); 100 training points per class (default_rng(510), chosen among
  seeds 500-529 as a typical sample: its CV curves neither over- nor underestimate the test error on
  average; with other seeds the CV curves move up or down by a few points, Section 5.1.3); the test
  error is measured on 50,000 fresh points; the Bayes rule uses the known densities. Degree d means the
  terms X1, ..., X1^d, X2, ..., X2^d without interactions, as in (5.5). KNN breaks a tied vote in
  favour of the nearest neighbour's class.
* Figures 5.9-5.10: the first data set of Figure 5.9 is the Portfolio data (alpha-hat = 0.576, as in
  the book); the other three, and the 1,000 data sets of Figure 5.10, are drawn from the population
  sigma_X^2 = 1, sigma_Y^2 = 1.25, sigma_XY = 0.5 (alpha = 0.6) with default_rng(510); the 1,000
  bootstrap samples of Portfolio use default_rng(1).
"""
import json
import os

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

import numpy as np
from scipy import interpolate, optimize, special

import common
from common import BLUE, GREY, ORANGE, PURPLE, RED, savefig

plt = common.plt
CH = 5
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")
BOOK_ORANGE = "#e69f00"
CURVE_COLS = ["#1b9e77", "#d95f02", "#7570b3", "#e7298a", "#66a61e", "#e6ab02", "#a6761d", "#666666",
              "#1f78b4", "#b2182b"]


# =========================================================================== data
def load_auto():
    """The Auto data without the five cars whose horsepower is missing: 392 rows, as in the book."""
    return common.isl_data("Auto", na_values="?").dropna().reset_index(drop=True)


def auto_xy():
    A = load_auto()
    return A["horsepower"].to_numpy(float), A["mpg"].to_numpy(float)


def load_portfolio():
    P = common.isl_data("Portfolio")
    return P["X"].to_numpy(float), P["Y"].to_numpy(float)


# =========================================================================== least squares
class OrthoPoly:
    """Orthogonal polynomials on the training values (the three-term recurrence of R's poly()).
    transform() returns the n x (d+1) design with the intercept first; its columns span the same
    space as 1, x, ..., x^d, so fits and predictions are those of ordinary polynomial regression."""

    def __init__(self, degree):
        self.degree = degree

    def fit(self, x):
        x = np.asarray(x, float)
        d = self.degree
        self.alpha, self.norm2 = np.zeros(d), np.zeros(d + 2)
        self.norm2[0], self.norm2[1] = 1.0, len(x)
        p_old, p = np.zeros_like(x), np.ones_like(x)
        for k in range(d):
            self.alpha[k] = np.sum(x * p ** 2) / np.sum(p ** 2)
            p_old, p = p, (x - self.alpha[k]) * p - self.norm2[k + 1] / self.norm2[k] * p_old
            self.norm2[k + 2] = np.sum(p ** 2)
        return self

    def transform(self, x):
        x = np.asarray(x, float)
        Z = [np.ones_like(x), x - self.alpha[0]]
        for k in range(1, self.degree):
            Z.append((x - self.alpha[k]) * Z[k] - self.norm2[k + 1] / self.norm2[k] * Z[k - 1])
        Z = np.column_stack(Z[1:self.degree + 1]) / np.sqrt(self.norm2[2:])
        return np.column_stack([np.ones_like(x), Z])


def poly_design(x, degree, ref=None):
    """Design matrix of a degree-d polynomial at x, with the basis fitted on ref (default x)."""
    return OrthoPoly(degree).fit(x if ref is None else ref).transform(x)


def lstsq(X, y):
    return np.linalg.lstsq(X, y, rcond=None)[0]


def leverages(X):
    """Diagonal of the hat matrix X (X^T X)^{-1} X^T: squared row norms of Q in X = QR."""
    Q, _ = np.linalg.qr(X)
    return np.sum(Q ** 2, axis=1)


def poly_fit_predict(xtr, ytr, xte, degree):
    P = OrthoPoly(degree).fit(xtr)
    return P.transform(xte) @ lstsq(P.transform(xtr), ytr)


def validation_mse(x, y, train, degree):
    """Validation set approach: fit on the rows in train, MSE on the others."""
    mask = np.zeros(len(y), bool)
    mask[train] = True
    pred = poly_fit_predict(x[mask], y[mask], x[~mask], degree)
    return np.mean((y[~mask] - pred) ** 2)


def loocv_shortcut(X, y):
    """LOOCV by formula (5.2): one fit, residuals divided by 1 - h_i."""
    Q, _ = np.linalg.qr(X)
    h = np.sum(Q ** 2, axis=1)
    r = y - Q @ (Q.T @ y)
    return np.mean((r / (1 - h)) ** 2)


def loocv_brute(X, y):
    """LOOCV by its definition (5.1): n refits."""
    n = len(y)
    e = np.empty(n)
    for i in range(n):
        keep = np.arange(n) != i
        e[i] = (y[i] - X[i] @ lstsq(X[keep], y[keep])) ** 2
    return e.mean()


def fold_labels(n, K, rng):
    """A random partition into K folds of sizes floor(n/K) or ceil(n/K)."""
    return rng.permutation(np.arange(n) % K)


def kfold_cv(x, y, degree, labels, weighted=False):
    """k-fold CV (5.3) for a polynomial fit: the plain average of the fold MSEs, or (weighted=True)
    the average weighted by fold size, i.e. the MSE over all held-out points (R's cv.glm)."""
    mses, sizes = [], []
    for k in np.unique(labels):
        te = labels == k
        pred = poly_fit_predict(x[~te], y[~te], x[te], degree)
        mses.append(np.mean((y[te] - pred) ** 2))
        sizes.append(te.sum())
    mses, sizes = np.array(mses), np.array(sizes)
    return float(np.sum(mses * sizes) / sizes.sum()) if weighted else float(mses.mean())


def sandwich_se(X, resid):
    """Heteroscedasticity-robust (HC0) standard errors (X^T X)^{-1} X^T diag(e^2) X (X^T X)^{-1}."""
    B = np.linalg.inv(X.T @ X)
    M = (X * resid[:, None] ** 2).T @ X
    return np.sqrt(np.diag(B @ M @ B))


def ols_se(X, y):
    """Least-squares coefficients and the textbook standard errors sqrt(sigma^2 (X^T X)^{-1})."""
    b = lstsq(X, y)
    r = y - X @ b
    s2 = r @ r / (len(y) - X.shape[1])
    return b, np.sqrt(np.diag(s2 * np.linalg.inv(X.T @ X))), r


def ols_expected_error(m, p, sigma2=1.0):
    """Expected test MSE of least squares with an intercept and p Gaussian inputs, trained on m
    points: sigma^2 (1 + 1/m + (1 + 1/m) p / (m - p - 2))  (Filling the gap 5.1)."""
    return sigma2 * (1 + 1 / m + (1 + 1 / m) * p / (m - p - 2))


# =========================================================================== smoothing splines
class SmoothingSpline:
    """Cubic smoothing spline on distinct knots t (the sorted training x), by the Reinsch algorithm:
    the fit minimises ||y - f||^2 + lam f^T K f with K = Q R^{-1} Q^T, so f_hat = S(lam) y with
    S(lam) = (I + lam K)^{-1} = U diag(1 / (1 + lam d)) U^T (Demmler-Reinsch eigenbasis)."""

    def __init__(self, x):
        order = np.argsort(x)
        self.order, self.t = order, np.asarray(x, float)[order]
        n, h = len(self.t), np.diff(self.t)
        Q = np.zeros((n, n - 2))
        R = np.zeros((n - 2, n - 2))
        for j in range(1, n - 1):
            Q[j - 1, j - 1] = 1 / h[j - 1]
            Q[j, j - 1] = -1 / h[j - 1] - 1 / h[j]
            Q[j + 1, j - 1] = 1 / h[j]
            R[j - 1, j - 1] = (h[j - 1] + h[j]) / 3
            if j < n - 2:
                R[j - 1, j] = R[j, j - 1] = h[j] / 6
        K = Q @ np.linalg.solve(R, Q.T)
        d, U = np.linalg.eigh((K + K.T) / 2)
        self.d, self.U = np.maximum(d, 0.0), U

    def df(self, lam):
        return float(np.sum(1 / (1 + lam * self.d)))

    def lam_for_df(self, df):
        """The lambda with trace S(lam) = df (2 < df < n), by root finding on log lambda."""
        return float(np.exp(optimize.brentq(lambda a: self.df(np.exp(a)) - df, -40, 60, xtol=1e-12)))

    def smoother(self, lam):
        return (self.U / (1 + lam * self.d)) @ self.U.T

    def fit(self, y, lam):
        """Fitted values at the knots (sorted order) and the spline function."""
        f = self.smoother(lam) @ np.asarray(y, float)[self.order]
        return f, natural_spline(self.t, f)


def natural_spline(t, f):
    """The natural cubic spline through (t_i, f_i), extended linearly outside [t_1, t_n]."""
    cs = interpolate.CubicSpline(t, f, bc_type="natural")
    d0, d1 = cs(t[0], 1), cs(t[-1], 1)

    def g(x):
        x = np.asarray(x, float)
        out = cs(np.clip(x, t[0], t[-1]))
        out = np.where(x < t[0], f[0] + d0 * (x - t[0]), out)
        return np.where(x > t[-1], f[-1] + d1 * (x - t[-1]), out)
    return g


def spline_loocv(ss, y, lam):
    """LOOCV of a smoothing spline by the linear-smoother shortcut (y_i - f_i) / (1 - S_ii)."""
    S = ss.smoother(lam)
    ys = np.asarray(y, float)[ss.order]
    return float(np.mean(((ys - S @ ys) / (1 - np.diag(S))) ** 2))


def spline_loocv_brute(x, y, lam):
    """LOOCV of a smoothing spline by n refits (to confirm the shortcut)."""
    n, e = len(y), []
    for i in range(n):
        keep = np.arange(n) != i
        _, g = SmoothingSpline(x[keep]).fit(y[keep], lam)
        e.append((y[i] - g(x[i])) ** 2)
    return float(np.mean(e))


def spline_kfold(x, y, lam, labels):
    e = []
    for k in np.unique(labels):
        te = labels == k
        _, g = SmoothingSpline(x[~te]).fit(y[~te], lam)
        e.append(np.mean((y[te] - g(x[te])) ** 2))
    return float(np.mean(e))


TRUTHS = {
    "fig2-9": lambda x: 4.5 + 5 * np.sin(np.pi * x / 130) ** 2,
    "fig2-10": lambda x: 2.5 + 0.1 * x + 0.3 * np.sin(x / 15),
    "fig2-11": lambda x: 10 + 18.5 * ((50 - x) / 50) ** 3 - 1.5 * ((50 - x) / 50) ** 2,
}
TRUTH_SEEDS = {"fig2-9": 29, "fig2-10": 30, "fig2-11": 31}


def sim_regression(name, n=50, sigma=1.0):
    rng = np.random.default_rng(TRUTH_SEEDS[name])
    x = rng.uniform(0, 100, n)
    return x, TRUTHS[name](x) + sigma * rng.normal(size=n)


def fig_5_6_curves(name, dfs=None):
    """True test MSE, LOOCV and 10-fold CV for smoothing splines of the given degrees of freedom."""
    x, y = sim_regression(name)
    dfs = np.geomspace(2.0001, 40, 40) if dfs is None else dfs
    ss, grid = SmoothingSpline(x), np.linspace(0, 100, 2001)
    labels = fold_labels(len(y), 10, np.random.default_rng(TRUTH_SEEDS[name] + 100))
    out = {"df": dfs, "true": [], "loocv": [], "cv10": []}
    for df in dfs:
        lam = ss.lam_for_df(df)
        _, g = ss.fit(y, lam)
        out["true"].append(1.0 + np.mean((TRUTHS[name](grid) - g(grid)) ** 2))
        out["loocv"].append(spline_loocv(ss, y, lam))
        out["cv10"].append(spline_kfold(x, y, lam, labels))
    return {k: np.asarray(v) for k, v in out.items()}


# =========================================================================== classification
CLASS_S2 = 0.22


def class_centres():
    r = np.random.default_rng(50)
    return r.normal([-0.5, 0.8], 1.0, (10, 2)), r.normal([0.8, -0.5], 1.0, (10, 2))


def class_sample(n_per_class, rng):
    c0, c1 = class_centres()
    X, y = [], []
    for cls, C in ((0, c0), (1, c1)):
        k = rng.integers(0, 10, n_per_class)
        X.append(C[k] + rng.normal(0, np.sqrt(CLASS_S2), (n_per_class, 2)))
        y.append(np.full(n_per_class, cls))
    return np.vstack(X), np.concatenate(y)


def class_density(X, C):
    d2 = ((X[:, None, :] - C[None, :, :]) ** 2).sum(-1)
    return np.mean(np.exp(-d2 / (2 * CLASS_S2)), axis=1) / (2 * np.pi * CLASS_S2)


def bayes_rule(X):
    c0, c1 = class_centres()
    return (class_density(X, c1) > class_density(X, c0)).astype(int)


def class_data():
    Xtr, ytr = class_sample(100, np.random.default_rng(510))
    Xte, yte = class_sample(25000, np.random.default_rng(514))
    return Xtr, ytr, Xte, yte


def poly2_features(X, degree, ref):
    """X1, ..., X1^d, X2, ..., X2^d (orthogonal polynomials fitted on ref), intercept first."""
    A = OrthoPoly(degree).fit(ref[:, 0]).transform(X[:, 0])
    B = OrthoPoly(degree).fit(ref[:, 1]).transform(X[:, 1])
    return np.column_stack([A, B[:, 1:]])


def logistic_fit(X, y, ridge=1e-8, tol=1e-10, max_iter=200):
    """Logistic regression by Newton's method (iteratively reweighted least squares) with
    step halving; the tiny ridge only guards against an exactly singular Hessian."""
    beta = np.zeros(X.shape[1])

    def nll(b):
        eta = X @ b
        return np.sum(np.logaddexp(0, eta) - y * eta) + 0.5 * ridge * b[1:] @ b[1:]
    f = nll(beta)
    for _ in range(max_iter):
        p = common.sigmoid(X @ beta)
        g = X.T @ (p - y)
        g[1:] += ridge * beta[1:]
        Hm = (X * (p * (1 - p))[:, None]).T @ X
        Hm[1:, 1:] += ridge * np.eye(X.shape[1] - 1)
        step = np.linalg.solve(Hm, g)
        t = 1.0
        while nll(beta - t * step) > f + 1e-12 and t > 1e-8:
            t /= 2
        beta = beta - t * step
        fnew = nll(beta)
        if f - fnew < tol * (1 + abs(f)):
            f = fnew
            break
        f = fnew
    return beta


def logistic_errors(degree, Xtr, ytr, Xte, yte, labels):
    """Training, test and 10-fold CV misclassification rates of polynomial logistic regression."""
    F = poly2_features(Xtr, degree, Xtr)
    b = logistic_fit(F, ytr)
    train = np.mean((F @ b > 0) != ytr)
    test = np.mean((poly2_features(Xte, degree, Xtr) @ b > 0) != yte)
    cv = []
    for k in range(10):
        te = labels == k
        Fk = poly2_features(Xtr[~te], degree, Xtr[~te])
        bk = logistic_fit(Fk, ytr[~te])
        cv.append(np.mean((poly2_features(Xtr[te], degree, Xtr[~te]) @ bk > 0) != ytr[te]))
    return train, test, float(np.mean(cv)), b


def knn_order(Xtr, Xq):
    """Training indices sorted by distance from each query point."""
    d2 = ((Xq[:, None, :] - Xtr[None, :, :]) ** 2).sum(-1)
    return np.argsort(d2, axis=1)


def knn_predict(ytr, order, K):
    """K-nearest-neighbour majority vote from the neighbour order; a tie goes to the class of
    the nearest neighbour."""
    idx = order[:, :K]
    frac = ytr[idx].mean(axis=1)
    return np.where(frac > 0.5, 1, np.where(frac < 0.5, 0, ytr[idx[:, 0]]))


def knn_errors(Ks, Xtr, ytr, Xte, yte, labels):
    o_tr, o_te = knn_order(Xtr, Xtr), knn_order(Xtr, Xte[:, :])
    folds = [(labels != k, labels == k) for k in range(10)]
    o_cv = [knn_order(Xtr[a], Xtr[b]) for a, b in folds]
    out = {"train": [], "test": [], "cv": []}
    for K in Ks:
        out["train"].append(np.mean(knn_predict(ytr, o_tr, K) != ytr))
        out["test"].append(np.mean(knn_predict(ytr, o_te, K) != yte))
        out["cv"].append(np.mean([np.mean(knn_predict(ytr[a], o, K) != ytr[b]) for (a, b), o in zip(folds, o_cv)]))
    return {k: np.array(v) for k, v in out.items()}


# =========================================================================== the bootstrap
SIGMA = np.array([[1.0, 0.5], [0.5, 1.25]])     # the population of Section 5.2: alpha = 0.6


def alpha_hat(x, y):
    """The plug-in minimum-variance allocation (5.7), with the usual (n - 1) covariances."""
    c = np.cov(x, y)
    return (c[1, 1] - c[0, 1]) / (c[0, 0] + c[1, 1] - 2 * c[0, 1])


def alpha_true(S=SIGMA):
    return (S[1, 1] - S[0, 1]) / (S[0, 0] + S[1, 1] - 2 * S[0, 1])


def min_variance(S=SIGMA):
    """Var(alpha X + (1 - alpha) Y) at the optimum: sigma_X^2 sigma_Y^2 (1 - rho^2) / Var(X - Y)."""
    return (S[0, 0] * S[1, 1] - S[0, 1] ** 2) / (S[0, 0] + S[1, 1] - 2 * S[0, 1])


def alpha_se_normal(n, S=SIGMA):
    """Exact SD of alpha-hat for n bivariate normal pairs. alpha-hat is the least-squares slope of
    -Y on X - Y, so given the X - Y values it is normal with variance sigma_P^2 / sum (d_i - dbar)^2;
    averaging 1 / chi^2_{n-1} gives sigma_P^2 / ((n - 3) Var(X - Y))  (Filling the gap 5.6)."""
    vd = S[0, 0] + S[1, 1] - 2 * S[0, 1]
    return float(np.sqrt(min_variance(S) / ((n - 3) * vd)))


def alpha_se_regression(x, y):
    """The textbook least-squares standard error of alpha-hat, from the regression of -Y on X - Y."""
    d, w = x - y, -y
    b, se, _ = ols_se(np.column_stack([np.ones_like(d), d]), w)
    return float(se[1])


def bootstrap(stat, n, B, rng):
    """B bootstrap replicates of stat(idx), idx a resample of 0..n-1 with replacement."""
    return np.array([stat(rng.integers(0, n, n)) for _ in range(B)])


def inclusion_prob(n):
    """P(observation j is in a bootstrap sample of size n) = 1 - (1 - 1/n)^n (Exercise 5.2)."""
    n = np.asarray(n, float)
    with np.errstate(divide="ignore"):          # n = 1 gives log(0) = -inf and probability 1
        return -np.expm1(n * np.log1p(-1 / n))


def distinct_count_pmf(n):
    """Exact distribution of the number of distinct observations in a bootstrap sample of size n:
    P(D = k) = C(n, k) k! S(n, k) / n^n, computed by the occupancy recursion (one draw at a time)."""
    p = np.zeros(n + 1)
    p[0] = 1.0
    for _ in range(n):
        q = np.zeros(n + 1)
        k = np.arange(n + 1)
        q += p * k / n                          # the draw repeats an observation already seen
        q[1:] += p[:-1] * (n - k[:-1]) / n      # the draw is new
        p = q
    return p


# =========================================================================== CV study
def cv_study(n=50, p=10, reps=2000, seed=55, use_cache=True):
    """Bias and spread of CV estimates for least squares (Filling the gap 5.3).
    Data: y = 1 + x^T beta + N(0, 1), x ~ N(0, I_p), beta = (1, ..., 1) / sqrt(p). For each data
    set: the true conditional error Err_T = 1 + (b0 - 1)^2 + ||b - beta||^2, the validation estimate
    (half and half), CV(2), CV(5), CV(10) with random folds, and LOOCV by (5.2)."""
    path = os.path.join(CACHE_DIR, "ch05_cv_study.npz")
    if use_cache and os.path.exists(path):
        z = np.load(path)
        return {k: z[k] for k in z.files}
    rng = np.random.default_rng(seed)
    beta = np.ones(p) / np.sqrt(p)
    keys = ["err", "val", "cv2", "cv5", "cv10", "loocv"]
    out = {k: np.empty(reps) for k in keys}
    for r in range(reps):
        X = rng.normal(size=(n, p))
        y = 1 + X @ beta + rng.normal(size=n)
        Xd = np.column_stack([np.ones(n), X])
        b = lstsq(Xd, y)
        out["err"][r] = 1 + (b[0] - 1) ** 2 + np.sum((b[1:] - beta) ** 2)
        perm = rng.permutation(n)
        tr, te = perm[: n // 2], perm[n // 2:]
        out["val"][r] = np.mean((y[te] - Xd[te] @ lstsq(Xd[tr], y[tr])) ** 2)
        for K in (2, 5, 10):
            lab = fold_labels(n, K, rng)
            e = [np.mean((y[lab == k] - Xd[lab == k] @ lstsq(Xd[lab != k], y[lab != k])) ** 2) for k in range(K)]
            out["cv%d" % K][r] = np.mean(e)
        out["loocv"][r] = loocv_shortcut(Xd, y)
    os.makedirs(CACHE_DIR, exist_ok=True)
    np.savez(path, **out)
    return out


def summarise_cv_study(S=None, n=50, p=10):
    S = cv_study() if S is None else S
    rows = {}
    for k, m in (("val", n // 2), ("cv2", n // 2), ("cv5", 4 * n // 5), ("cv10", 9 * n // 10), ("loocv", n - 1)):
        rows[k] = {"train_size": m, "mean": float(S[k].mean()), "sd": float(S[k].std(ddof=1)),
                   "expected_err_at_m": ols_expected_error(m, p),
                   "rmse_vs_errT": float(np.sqrt(np.mean((S[k] - S["err"]) ** 2))),
                   "corr_with_errT": float(np.corrcoef(S[k], S["err"])[0, 1])}
    rows["err"] = {"mean": float(S["err"].mean()), "sd": float(S["err"].std(ddof=1)),
                   "expected": ols_expected_error(n, p)}
    return rows


# =========================================================================== figures
def _auto_ax(ax, ylim=(16, 28)):
    ax.set_xlabel("Degree of Polynomial")
    ax.set_ylabel("Mean Squared Error")
    ax.set_xlim(0.6, 10.4)
    ax.set_ylim(*ylim)
    ax.set_xticks([2, 4, 6, 8, 10])


def fig_5_2_splits():
    """The eleven random halves used in Figure 5.2 (indices of the 196 training cars)."""
    rng = np.random.default_rng(2021)
    return [np.sort(rng.permutation(392)[:196]) for _ in range(11)]


def fig_5_2_curves():
    x, y = auto_xy()
    return np.array([[validation_mse(x, y, tr, d) for d in range(1, 11)] for tr in fig_5_2_splits()])


def fig_5_2(out_dir=None):
    """Validation set approach on Auto: one split (left) and ten splits (right)."""
    V = fig_5_2_curves()
    fig, axes = plt.subplots(1, 2, figsize=(8.4, 3.7))
    d = np.arange(1, 11)
    axes[0].plot(d, V[0], "-o", color=RED, ms=4)
    for k in range(10):
        axes[1].plot(d, V[k + 1], color=CURVE_COLS[k], lw=1.4)
    for ax in axes:
        _auto_ax(ax)
    fig.tight_layout()
    return savefig(fig, CH, "fig5-2", out_dir)


def fig_5_4_folds():
    rng = np.random.default_rng(2023)
    return [fold_labels(392, 10, rng) for _ in range(9)]


def fig_5_4_curves():
    x, y = auto_xy()
    loo = np.array([loocv_shortcut(poly_design(x, d), y) for d in range(1, 11)])
    cv = np.array([[kfold_cv(x, y, d, lab) for d in range(1, 11)] for lab in fig_5_4_folds()])
    return loo, cv


def fig_5_4(out_dir=None):
    """LOOCV (left) and nine runs of 10-fold CV (right) on Auto."""
    loo, cv = fig_5_4_curves()
    fig, axes = plt.subplots(1, 2, figsize=(8.4, 3.7))
    d = np.arange(1, 11)
    axes[0].plot(d, loo, "-o", color=BLUE, ms=4)
    axes[0].set_title("LOOCV")
    for k in range(9):
        axes[1].plot(d, cv[k], color=CURVE_COLS[k], lw=1.4)
    axes[1].set_title("10-fold CV")
    for ax in axes:
        _auto_ax(ax)
    fig.tight_layout()
    return savefig(fig, CH, "fig5-4", out_dir)


def fig_5_6(out_dir=None):
    """True test MSE, LOOCV and 10-fold CV for smoothing splines on the data of Figures 2.9-2.11."""
    fig, axes = plt.subplots(1, 3, figsize=(10.5, 3.5))
    for ax, name, ylim in zip(axes, ("fig2-9", "fig2-10", "fig2-11"), ((0, 3), (0, 3), (0, 20))):
        c = fig_5_6_curves(name)
        ax.plot(c["df"], c["true"], color=BLUE, lw=1.8)
        ax.plot(c["df"], c["loocv"], "--", color="black", lw=1.6)
        ax.plot(c["df"], c["cv10"], color=ORANGE, lw=1.6)
        for key, col in (("true", BLUE), ("loocv", "black"), ("cv10", ORANGE)):
            i = int(np.argmin(c[key]))
            ax.plot(c["df"][i], c[key][i], "x", color=col, ms=11, mew=2)
        ax.set_xscale("log")
        ax.set_xticks([2, 5, 10, 20])
        ax.set_xticklabels(["2", "5", "10", "20"])
        ax.set_ylim(*ylim)
        ax.set_xlabel("Flexibility")
        ax.set_ylabel("Mean Squared Error")
    fig.tight_layout()
    return savefig(fig, CH, "fig5-6", out_dir)


def _grid(Xtr, m=200):
    lo, hi = Xtr.min(0) - 0.3, Xtr.max(0) + 0.3
    g1, g2 = np.meshgrid(np.linspace(lo[0], hi[0], m), np.linspace(lo[1], hi[1], m))
    return g1, g2, np.column_stack([g1.ravel(), g2.ravel()])


def bayes_error():
    _, _, Xte, yte = class_data()
    return float(np.mean(bayes_rule(Xte) != yte))


def fig_5_7(out_dir=None):
    """Logistic regression with polynomials of degree 1-4 on the two-class data, with the Bayes boundary."""
    Xtr, ytr, Xte, yte = class_data()
    g1, g2, G = _grid(Xtr)
    c0, c1 = class_centres()
    bayes = (np.log(class_density(G, c1)) - np.log(class_density(G, c0))).reshape(g1.shape)
    fig, axes = plt.subplots(2, 2, figsize=(7.6, 7.2))
    for ax, d in zip(axes.ravel(), (1, 2, 3, 4)):
        b = logistic_fit(poly2_features(Xtr, d, Xtr), ytr)
        eta = (poly2_features(G, d, Xtr) @ b).reshape(g1.shape)
        test = np.mean((poly2_features(Xte, d, Xtr) @ b > 0) != yte)
        ax.scatter(Xtr[ytr == 0, 0], Xtr[ytr == 0, 1], s=16, facecolors="none", edgecolors=BOOK_ORANGE, lw=1)
        ax.scatter(Xtr[ytr == 1, 0], Xtr[ytr == 1, 1], s=16, facecolors="none", edgecolors=BLUE, lw=1)
        ax.contour(g1, g2, bayes, levels=[0], colors=[PURPLE], linestyles="--", linewidths=1.6)
        ax.contour(g1, g2, eta, levels=[0], colors=["black"], linewidths=1.6)
        ax.set_title("Degree = %d (test error %.3f)" % (d, test))
        ax.set_xticks([])
        ax.set_yticks([])
        ax.set_xlim(g1.min(), g1.max())
        ax.set_ylim(g2.min(), g2.max())
    fig.tight_layout()
    return savefig(fig, CH, "fig5-7", out_dir)


def fig_5_8_results(use_cache=True):
    path = os.path.join(CACHE_DIR, "ch05_fig5_8.npz")
    if use_cache and os.path.exists(path):
        z = np.load(path)
        return {k: z[k] for k in z.files}
    Xtr, ytr, Xte, yte = class_data()
    labels = fold_labels(len(ytr), 10, np.random.default_rng(58))
    L = np.array([logistic_errors(d, Xtr, ytr, Xte, yte, labels)[:3] for d in range(1, 11)])
    Ks = np.arange(1, 101)
    Kn = knn_errors(Ks, Xtr, ytr, Xte, yte, labels)
    out = {"logit_train": L[:, 0], "logit_test": L[:, 1], "logit_cv": L[:, 2], "K": Ks,
           "knn_train": Kn["train"], "knn_test": Kn["test"], "knn_cv": Kn["cv"]}
    os.makedirs(CACHE_DIR, exist_ok=True)
    np.savez(path, **out)
    return out


def fig_5_8(out_dir=None):
    """Training, test and 10-fold CV error: polynomial logistic regression (left), KNN (right)."""
    R = fig_5_8_results()
    BROWN = "#c98a00"
    fig, axes = plt.subplots(1, 2, figsize=(8.6, 3.8))
    d = np.arange(1, 11)
    axes[0].plot(d, R["logit_test"], color=BROWN, lw=1.8)
    axes[0].plot(d, R["logit_train"], color="#2b9fe0", lw=1.8)
    axes[0].plot(d, R["logit_cv"], color="black", lw=1.8)
    for key, col in (("logit_test", BROWN), ("logit_cv", "black")):
        i = int(np.argmin(R[key]))
        axes[0].plot(d[i], R[key][i], "x", color=col, ms=9, mew=2)
    axes[0].set_xlabel("Order of Polynomials Used")
    inv = 1 / R["K"]
    axes[1].plot(inv, R["knn_test"], color=BROWN, lw=1.8)
    axes[1].plot(inv, R["knn_train"], color="#2b9fe0", lw=1.8)
    axes[1].plot(inv, R["knn_cv"], color="black", lw=1.8)
    for key, col in (("knn_test", BROWN), ("knn_cv", "black")):
        i = int(np.argmin(R[key]))
        axes[1].plot(inv[i], R[key][i], "x", color=col, ms=9, mew=2)
    axes[1].set_xscale("log")
    axes[1].set_xticks([0.01, 0.02, 0.05, 0.1, 0.2, 0.5, 1])
    axes[1].set_xticklabels(["0.01", "0.02", "0.05", "0.10", "0.20", "0.50", "1.00"])
    axes[1].set_xlabel("1/K")
    lo = min(R["logit_train"].min(), 0.1) - 0.01
    for ax in axes:
        ax.set_ylabel("Error Rate")
        ax.set_ylim(max(0.0, lo), 0.24)
    fig.tight_layout()
    return savefig(fig, CH, "fig5-8", out_dir)


def fig_5_9_data():
    """Portfolio, then three simulated data sets of 100 pairs from the population."""
    x, y = load_portfolio()
    rng = np.random.default_rng(510)
    sets = [(x, y)]
    for _ in range(3):
        Z = rng.multivariate_normal([0, 0], SIGMA, 100)
        sets.append((Z[:, 0], Z[:, 1]))
    return sets


def fig_5_9(out_dir=None):
    """Four data sets of 100 returns (X, Y) and their estimates of alpha."""
    fig, axes = plt.subplots(2, 2, figsize=(6.8, 6.6))
    for ax, (x, y) in zip(axes.ravel(), fig_5_9_data()):
        ax.scatter(x, y, s=14, color=GREEN_ISH, alpha=0.85)
        ax.set_title(r"$\hat\alpha$ = %.3f" % alpha_hat(x, y))
        ax.set_xlabel("X")
        ax.set_ylabel("Y")
        ax.set_xlim(-3.3, 3.3)
        ax.set_ylim(-3.3, 3.3)
    fig.tight_layout()
    return savefig(fig, CH, "fig5-9", out_dir)


GREEN_ISH = "#2e8b57"


def fig_5_10_values(nsim=1000, B=1000):
    rng = np.random.default_rng(510)
    for _ in range(3):                               # skip the three data sets of Figure 5.9
        rng.multivariate_normal([0, 0], SIGMA, 100)
    sim = np.empty(nsim)
    for r in range(nsim):
        Z = rng.multivariate_normal([0, 0], SIGMA, 100)
        sim[r] = alpha_hat(Z[:, 0], Z[:, 1])
    x, y = load_portfolio()
    boot = bootstrap(lambda i: alpha_hat(x[i], y[i]), 100, B, np.random.default_rng(1))
    return sim, boot


def fig_5_10(out_dir=None):
    """The sampling distribution of alpha-hat (1,000 simulated data sets) and the bootstrap
    distribution (1,000 resamples of Portfolio), as histograms and boxplots."""
    sim, boot = fig_5_10_values()
    fig, axes = plt.subplots(1, 3, figsize=(10.5, 3.5))
    bins = np.linspace(0.25, 0.95, 29)
    axes[0].hist(sim, bins=bins, color="#f0b37e", edgecolor="black", lw=0.5)
    axes[1].hist(boot, bins=bins, color="#7db6e8", edgecolor="black", lw=0.5)
    for ax in axes[:2]:
        ax.axvline(0.6, color=MAGENTA_ISH, lw=2)
        ax.set_xlabel(r"$\alpha$")
        ax.set_ylim(0, 200)
    axes[2].boxplot([sim, boot], widths=0.6, patch_artist=True,
                    boxprops=dict(facecolor="#f3f3f3"), medianprops=dict(color="black"))
    axes[2].set_xticks([1, 2])
    axes[2].set_xticklabels(["True", "Bootstrap"])
    axes[2].axhline(0.6, color=MAGENTA_ISH, lw=2)
    axes[2].set_ylabel(r"$\alpha$")
    axes[2].set_ylim(0.25, 0.95)
    fig.tight_layout()
    return savefig(fig, CH, "fig5-10", out_dir)


MAGENTA_ISH = "#e75480"


def fig_ex_2(out_dir=None):
    """Exercise 5.2(g): the probability that observation j is in a bootstrap sample, n = 1..100,000."""
    n = np.arange(1, 100001)
    fig, ax = plt.subplots(figsize=(6.2, 3.5))
    ax.plot(n, inclusion_prob(n), color=BLUE, lw=1.6)
    ax.axhline(1 - np.exp(-1), color=RED, ls="--", lw=1.2)
    ax.text(3e3, 1 - np.exp(-1) + 0.02, r"$1-1/e = 0.632$", color=RED)
    ax.set_xscale("log")
    ax.set_xlabel("n (log scale)")
    ax.set_ylabel("P(observation j is in the sample)")
    ax.set_ylim(0.6, 1.02)
    fig.tight_layout()
    return savefig(fig, CH, "fig5-ex2", out_dir)


def ex8_data():
    rng = np.random.default_rng(1)
    x = rng.normal(size=100)
    return x, x - 2 * x ** 2 + rng.normal(size=100)


def fig_ex_8(out_dir=None):
    """Exercise 5.8(b): the simulated data y = x - 2x^2 + noise, with the true curve."""
    x, y = ex8_data()
    g = np.linspace(x.min() - 0.1, x.max() + 0.1, 300)
    fig, ax = plt.subplots(figsize=(5.0, 3.6))
    ax.scatter(x, y, s=14, color=GREY)
    ax.plot(g, g - 2 * g ** 2, color=RED, lw=1.6, label=r"$x-2x^2$")
    ax.set_xlabel("x")
    ax.set_ylabel("y")
    ax.legend(frameon=False)
    fig.tight_layout()
    return savefig(fig, CH, "fig5-ex8", out_dir)


# =========================================================================== demo data
def export_demo_data(out_dir=None):
    """Write data/ch05-auto.json and data/ch05-portfolio.json for the demonstrations."""
    x, y = auto_xy()
    V = fig_5_2_curves()
    loo, cv = fig_5_4_curves()
    auto = {"hp": x.astype(int).tolist(), "mpg": y.tolist(),
            "val_splits": [s.tolist() for s in fig_5_2_splits()],
            "val_curves": np.round(V, 6).tolist(),
            "cv_folds": [f.tolist() for f in fig_5_4_folds()],
            "cv_curves": np.round(cv, 6).tolist(), "loocv": np.round(loo, 6).tolist()}
    px, py = load_portfolio()
    sim, boot = fig_5_10_values()
    port = {"X": np.round(px, 6).tolist(), "Y": np.round(py, 6).tolist(),
            "alpha_hat": alpha_hat(px, py), "alpha_true": alpha_true(),
            "sigma": SIGMA.tolist(), "se_normal": alpha_se_normal(100),
            "se_regression": alpha_se_regression(px, py),
            "sim_sd": float(sim.std(ddof=1)), "sim_mean": float(sim.mean())}
    os.makedirs(DATA_OUT, exist_ok=True)
    for name, obj in (("ch05-auto.json", auto), ("ch05-portfolio.json", port)):
        path = os.path.join(DATA_OUT, name)
        with open(path, "w") as f:
            json.dump(obj, f, separators=(",", ":"))
        print("wrote", os.path.relpath(path, os.getcwd()), "(%d bytes)" % os.path.getsize(path))


def report(out_dir=None):
    """Print the numbers quoted in the notes (no figure)."""
    x, y = auto_xy()
    loo, cv = fig_5_4_curves()
    print("LOOCV degrees 1-10:", np.round(loo, 4))
    print("10-fold CV, nine runs, degree 2: min %.3f max %.3f" % (cv[:, 1].min(), cv[:, 1].max()))
    V = fig_5_2_curves()
    print("validation, eleven splits, degree 2: min %.3f max %.3f" % (V[:, 1].min(), V[:, 1].max()))
    print("Bayes error %.4f" % bayes_error())
    R = fig_5_8_results()
    print("logistic test", np.round(R["logit_test"], 4))
    print("logistic cv  ", np.round(R["logit_cv"], 4))
    print("logistic train", np.round(R["logit_train"], 4))
    i, j = int(np.argmin(R["knn_test"])), int(np.argmin(R["knn_cv"]))
    print("KNN best test K=%d (%.4f), best CV K=%d (%.4f)" % (R["K"][i], R["knn_test"][i], R["K"][j], R["knn_cv"][j]))
    for name in ("fig2-9", "fig2-10", "fig2-11"):
        c = fig_5_6_curves(name)
        print(name, "argmin df: true %.2f loocv %.2f cv10 %.2f; min true %.3f" % tuple(
            [c["df"][int(np.argmin(c[k]))] for k in ("true", "loocv", "cv10")] + [c["true"].min()]))
    sim, boot = fig_5_10_values()
    px, py = load_portfolio()
    print("alpha-hat Portfolio %.4f; Figure 5.10 sim mean %.4f sd %.4f; bootstrap SE %.4f; exact normal SD %.4f;"
          " regression SE %.4f" % (alpha_hat(px, py), sim.mean(), sim.std(ddof=1), boot.std(ddof=1),
                                   alpha_se_normal(100), alpha_se_regression(px, py)))
    for k, (a, b) in enumerate(fig_5_9_data()):
        print("Figure 5.9 panel %d alpha-hat %.3f" % (k + 1, alpha_hat(a, b)))
    print("inclusion n=5, 100, 10000:", inclusion_prob([5, 100, 10000]))
    print("CV study:", json.dumps(summarise_cv_study(), indent=1))


FIGURES = {"5.2": fig_5_2, "5.4": fig_5_4, "5.6": fig_5_6, "5.7": fig_5_7, "5.8": fig_5_8,
           "5.9": fig_5_9, "5.10": fig_5_10, "E2": fig_ex_2, "E8": fig_ex_8,
           "data": export_demo_data, "report": report}

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