"""Murphy (2022), Chapter 11: Linear Regression.

Companion code for Chapter 11 of K. P. Murphy, Probabilistic Machine Learning: An Introduction
(MIT Press, 2022; April 2025 draft), pp. 371-413, written from scratch with numpy, scipy and
matplotlib, to be read next to the lecture notes (../ch11-linear-regression.html). scikit-learn
and scipy are only used to confirm the implementations.

Methods (all implemented here)
* Section 11.2, least squares: ols_normal, ols_qr (QR and back-substitution, (11.19)-(11.21)),
  ols_svd, weighted least squares wls (11.24), centred solution (11.25)-(11.26), the recursive
  estimator for simple regression online_simple (11.33)-(11.40), R^2 and RMSE (11.50)-(11.51).
* Section 11.3, ridge: ridge_fit (11.57), ridge_qr (virtual data, (11.58)-(11.64)), ridge_svd
  ((11.65)-(11.71)), effective degrees of freedom ridge_dof (11.71).
* Section 11.4, lasso: soft_threshold (11.89), lasso_cd (the shooting algorithm, Algorithm 11.1),
  lasso_fista (ISTA/FISTA, (11.105)), lars_lasso (the homotopy algorithm of Section 11.4.9.4, with
  the lasso modification), elastic_net_cd (11.101), group_fista with the block-l2 and block-linf
  proximal operators (11.97), (11.100), best_subset.
* Section 11.5, splines: bspline_basis (Cox-de Boor recursion), spline_design.
* Section 11.6, robust regression: laplace_lp (linear programme (11.109)-(11.115)), huber_irls (11.117),
  student_em (11.116).
* Section 11.7, Bayesian linear regression: posterior (11.120)-(11.122), predictive (11.124),
  the exact posterior of the multicollinear legs example (the weights integrated out, the noise
  scale on a grid).

Data. The prostate cancer data (Stamey et al. 1989, 97 men, 67 for training and 30 for testing, as in
Hastie, Tibshirani and Friedman 2009) is a small CSV in data/ch11-prostate.csv. The book's other
data sets are not available offline, so these figures use close stand-ins, stated in the notes:
the 21-point polynomial data (Figures 11.1, 11.2, 11.5, 11.6, 11.4) and the outlier data (11.19) are
simulated with a fixed seed; the cherry blossom series of Figure 11.18 is replaced by the annual
flow of the river Nile (statsmodels, 1871-1970); the leg-length data (11.23, 11.24) are simulated as
described in the book.

Figures. Reproduced here: 11.1-11.2, 11.4-11.24, and 11.3 (the least squares projection, drawn in 3-D from
computed numbers). Table 11.1 and Figure 11.11 are computed by lars_lasso and the cross-validation
code and printed by `python3 ch11_linear_regression.py --fig 11.10 11.11`. Skipped, with the reason:
  (none of the book's computed figures is skipped.)
Supplementary figures for gaps filled in the notes:
  11.S1 the grouping effect of the elastic net against the lasso for two identical features;
  11.S2 ridge shrinkage factors sigma_j^2/(sigma_j^2 + lambda) and the degrees of freedom curve.
Run `python3 ch11_linear_regression.py --list`, `python3 ch11_linear_regression.py` (all figures,
a few minutes) or `python3 ch11_linear_regression.py --fig 11.13`. Files go to ../img/ch11/; the data
used by the browser demonstrations go to ../data/ch11-*.json.
"""
import json
import os
import sys

os.environ.setdefault("OPENBLAS_NUM_THREADS", "1")

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

sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
import common  # noqa: E402
from common import BLUE, CYAN, GREEN, GREY, MAGENTA, ORANGE, PURPLE, RED, plt, savefig  # noqa: E402

CH = 11
HERE = os.path.dirname(os.path.abspath(__file__))
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))


# =========================================================================== 11.2 least squares
def add_ones(X):
    X = np.asarray(X, dtype=float)
    return np.column_stack([np.ones(len(X)), X])


def ols_normal(X, y):
    """Normal equations (11.8): solve X'X w = X'y by a Cholesky factorisation."""
    A = X.T @ X
    return linalg.solve(A, X.T @ y, assume_a="pos")


def ols_qr(X, y):
    """QR route (11.19)-(11.21): X = QR, then back-substitution on R w = Q'y."""
    Q, R = np.linalg.qr(X)
    return linalg.solve_triangular(R, Q.T @ y)


def ols_svd(X, y):
    """SVD route: w = V S^{-1} U' y, dropping singular values below a tolerance (pseudo-inverse)."""
    U, s, Vt = np.linalg.svd(X, full_matrices=False)
    keep = s > s.max() * max(X.shape) * np.finfo(float).eps
    return Vt[keep].T @ ((U[:, keep].T @ y) / s[keep])


def wls(X, y, lam_diag):
    """Weighted least squares (11.24): w = (X' L X)^{-1} X' L y with L = diag(lam_diag)."""
    XtL = X.T * lam_diag
    return np.linalg.solve(XtL @ X, XtL @ y)


def centred_ols(X, y):
    """(11.25)-(11.26): slopes from the centred data, then the intercept."""
    xm, ym = X.mean(0), y.mean()
    Xc, yc = X - xm, y - ym
    w = np.linalg.solve(Xc.T @ Xc, Xc.T @ yc)
    return ym - xm @ w, w


def online_simple(x, y):
    """Recursive estimates for simple regression, (11.33)-(11.40).

    Keeps the means and the (1/n)-normalised second moments; returns arrays w0[n], w1[n] for n = 2..N.
    """
    xb = yb = Cxx = Cxy = 0.0
    w0s, w1s = [], []
    for n, (xn, yn) in enumerate(zip(x, y)):      # n points seen before this one
        xb2 = xb + (xn - xb) / (n + 1)
        yb2 = yb + (yn - yb) / (n + 1)
        Cxy2 = (xn * yn + n * Cxy + n * xb * yb - (n + 1) * xb2 * yb2) / (n + 1)       # (11.40)
        Cxx2 = (xn * xn + n * Cxx + n * xb * xb - (n + 1) * xb2 * xb2) / (n + 1)
        xb, yb, Cxy, Cxx = xb2, yb2, Cxy2, Cxx2
        if n >= 1 and Cxx > 1e-12:
            w1 = Cxy / Cxx
            w0s.append(yb - w1 * xb)
            w1s.append(w1)
        elif n >= 1:
            w0s.append(np.nan)
            w1s.append(np.nan)
    return np.array(w0s), np.array(w1s)


def r2_score(y, yhat):
    return 1.0 - np.sum((y - yhat) ** 2) / np.sum((y - y.mean()) ** 2)       # (11.51)


def poly_feats(x, deg):
    return np.vander(np.asarray(x, dtype=float), deg + 1, increasing=True)


def poly_truth(x):
    return 0.1 * (np.asarray(x) - 5.0) ** 2 - 9.0


def poly_data(seed=3, n=21, ntest=500, sd=2.5):
    """21 equally spaced inputs on [0, 20] with a quadratic truth and N(0, sd^2) noise (a stand-in for
    the book's 21 points), plus a large noise-free-input test set from the same law."""
    rng = np.random.default_rng(seed)
    x = np.linspace(0, 20, n)
    y = poly_truth(x) + sd * rng.standard_normal(n)
    xt = rng.uniform(0, 20, ntest)
    yt = poly_truth(xt) + sd * rng.standard_normal(ntest)
    return x, y, xt, yt


# =========================================================================== 11.3 ridge
def ridge_fit(X, y, lam, penalize_first=False):
    """(11.57): w = (X'X + lam I)^{-1} X'y; the first column (the offset) is not penalised unless asked."""
    D = X.shape[1]
    P = np.eye(D) * lam
    if not penalize_first:
        P[0, 0] = 0.0
    return np.linalg.solve(X.T @ X + P, X.T @ y)


def ridge_qr(X, y, lam):
    """Ridge as ordinary least squares on virtual data, (11.58)-(11.64) with sigma = 1, Lambda = lam I."""
    D = X.shape[1]
    Xt = np.vstack([X, np.sqrt(lam) * np.eye(D)])
    yt = np.concatenate([y, np.zeros(D)])
    return ols_qr(Xt, yt)


def ridge_svd(X, y, lam):
    """The N x N route (11.65) for D > N: w = V (R'R + lam I)^{-1} R' y with R = U S."""
    U, s, Vt = np.linalg.svd(X, full_matrices=False)
    R = U * s
    return Vt.T @ np.linalg.solve(R.T @ R + lam * np.eye(len(s)), R.T @ y)


def ridge_dof(X, lam):
    """Effective degrees of freedom (11.71): sum_j s_j^2 / (s_j^2 + lam)."""
    s = np.linalg.svd(X, compute_uv=False)
    return float(np.sum(s ** 2 / (s ** 2 + lam)))


# =========================================================================== 11.4 lasso
def soft_threshold(x, d):
    """sign(x) (|x| - d)_+, (11.89)."""
    return np.sign(x) * np.maximum(np.abs(x) - d, 0.0)


def lasso_cd(X, y, lam, w0=None, tol=1e-12, max_sweeps=10000, l2=0.0):
    """Coordinate descent (the shooting algorithm, Algorithm 11.1) for
    0.5 ||y - Xw||^2 + lam ||w||_1 + 0.5 * l2 ||w||^2.  With l2 > 0 this is the elastic net (11.101)
    in the 0.5 / lam1, l2 parametrisation."""
    N, D = X.shape
    w = np.zeros(D) if w0 is None else w0.copy()
    a = (X ** 2).sum(0) + l2
    r = y - X @ w
    for sweep in range(max_sweeps):
        dmax = 0.0
        for d in range(D):
            if a[d] == 0:
                continue
            c = X[:, d] @ r + (X[:, d] @ X[:, d]) * w[d]         # c_d of (11.83)
            wn = soft_threshold(c, lam) / a[d]                   # (11.88)
            if wn != w[d]:
                r -= X[:, d] * (wn - w[d])
                dmax = max(dmax, abs(wn - w[d]))
                w[d] = wn
        if dmax < tol:
            break
    return w


def lasso_fista(X, y, lam, iters=2000, w0=None, L=None):
    """ISTA with Nesterov momentum (FISTA), (11.105), for 0.5 ||y - Xw||^2 + lam ||w||_1."""
    D = X.shape[1]
    L = np.linalg.norm(X, 2) ** 2 if L is None else L
    w = np.zeros(D) if w0 is None else w0.copy()
    z, t = w.copy(), 1.0
    for _ in range(iters):
        g = X.T @ (X @ z - y)
        wn = soft_threshold(z - g / L, lam / L)
        tn = 0.5 * (1 + np.sqrt(1 + 4 * t * t))
        z = wn + (t - 1) / tn * (wn - w)
        w, t = wn, tn
    return w


def lasso_ista(X, y, lam, iters=2000, L=None):
    D = X.shape[1]
    L = np.linalg.norm(X, 2) ** 2 if L is None else L
    w = np.zeros(D)
    for _ in range(iters):
        w = soft_threshold(w - X.T @ (X @ w - y) / L, lam / L)
    return w


def lasso_objective(X, y, w, lam):
    return 0.5 * np.sum((y - X @ w) ** 2) + lam * np.abs(w).sum()


def lars_lasso(X, y, tol=1e-10):
    """The homotopy (LARS with the lasso modification) path of 0.5 ||y - Xw||^2 + lam ||w||_1.

    X must have centred columns and y be centred. Returns (lams, W): the critical values of lam in
    decreasing order (lams[0] = ||X'y||_inf, lams[-1] = 0) and the coefficient vectors at them (rows);
    between two critical values the path is linear in lam (Efron et al. 2004).
    """
    N, D = X.shape
    w = np.zeros(D)
    c = X.T @ y
    lam = np.abs(c).max()
    lams, W = [lam], [w.copy()]
    active = [int(np.argmax(np.abs(c)))]
    for _ in range(8 * D):
        A = active
        sA = np.sign(c[A])
        XA = X[:, A]
        d = np.linalg.solve(XA.T @ XA, sA)           # dw_A / d(-lam)
        a = X.T @ (XA @ d)                           # change of the correlations per unit step
        step, kind, who = lam, None, None            # at most to lam = 0
        for j in range(D):
            if j in A:
                continue
            for num, den in ((lam - c[j], 1 - a[j]), (lam + c[j], 1 + a[j])):
                if abs(den) > 1e-14:
                    t = num / den
                    if tol < t < step:
                        step, kind, who = t, "add", j
        for k, i in enumerate(A):
            if abs(d[k]) > 1e-14:
                t = -w[i] / d[k]
                if tol < t < step:
                    step, kind, who = t, "drop", i
        w = w.copy()
        w[A] += step * d
        c = c - step * a
        lam = lam - step
        lams.append(lam)
        W.append(w.copy())
        if kind == "add":
            active = A + [who]
        elif kind == "drop":
            w[who] = 0.0
            W[-1] = w.copy()
            active = [i for i in A if i != who]
        else:
            break
        if lam <= tol:
            break
    return np.array(lams), np.array(W)


def path_at(lams, W, lam):
    """Evaluate the piecewise linear lasso path at lam (linear interpolation between critical values)."""
    lam = float(np.clip(lam, lams[-1], lams[0]))
    out = np.empty(W.shape[1])
    for j in range(W.shape[1]):
        out[j] = np.interp(lam, lams[::-1], W[::-1, j])
    return out


def elastic_net_cd(X, y, lam1, lam2, **kw):
    """Minimise ||y - Xw||^2 + lam2 ||w||_2^2 + lam1 ||w||_1 (11.101) by coordinate descent."""
    return lasso_cd(X, y, lam1 / 2.0, l2=lam2, **kw)


def best_subset(X, y, K):
    """Exhaustive best subset of size K (least squares on the chosen columns); returns the full-length weights."""
    import itertools
    D = X.shape[1]
    best, bw = np.inf, None
    for S in itertools.combinations(range(D), K):
        S = list(S)
        w = np.zeros(D)
        if S:
            w[S] = np.linalg.lstsq(X[:, S], y, rcond=None)[0]
        rss = np.sum((y - X @ w) ** 2)
        if rss < best:
            best, bw = rss, w
    return bw


# group lasso (Section 11.4.7)
def prox_block_l2(v, t, groups):
    """Block soft thresholding: prox of t * sum_g ||w_g||_2, the operator behind (11.97)."""
    out = v.copy()
    for g in groups:
        n = np.linalg.norm(v[g])
        out[g] = 0.0 if n <= t else (1 - t / n) * v[g]
    return out


def proj_l1_ball(v, radius):
    """Euclidean projection onto {u : ||u||_1 <= radius}."""
    if np.abs(v).sum() <= radius:
        return v.copy()
    u = np.sort(np.abs(v))[::-1]
    css = np.cumsum(u)
    k = np.nonzero(u * np.arange(1, len(u) + 1) > (css - radius))[0][-1]
    theta = (css[k] - radius) / (k + 1)
    return np.sign(v) * np.maximum(np.abs(v) - theta, 0.0)


def prox_block_linf(v, t, groups):
    """Prox of t * sum_g ||w_g||_inf by the Moreau decomposition: v - projection onto the l1 ball of radius t."""
    out = v.copy()
    for g in groups:
        out[g] = v[g] - proj_l1_ball(v[g], t)
    return out


def group_fista(X, y, tau, groups, prox, iters=600, L=None):
    """FISTA for 0.5 ||y - Xw||^2 + tau * sum_g phi(w_g), with phi the l2 or linf norm."""
    D = X.shape[1]
    L = np.linalg.norm(X, 2) ** 2 if L is None else L
    w = np.zeros(D)
    z, t = w.copy(), 1.0
    for _ in range(iters):
        g = X.T @ (X @ z - y)
        wn = prox(z - g / L, tau / L, groups)
        tn = 0.5 * (1 + np.sqrt(1 + 4 * t * t))
        z = wn + (t - 1) / tn * (wn - w)
        w, t = wn, tn
    return w


def debias(X, y, w, thresh=1e-8):
    """Re-fit by least squares on the support of w (Section 11.4.3)."""
    S = np.abs(w) > thresh
    out = np.zeros_like(w)
    if S.any():
        out[S] = np.linalg.lstsq(X[:, S], y, rcond=None)[0]
    return out


# =========================================================================== 11.5 splines
def bspline_basis(x, interior, degree, lo=0.0, hi=1.0):
    """All K + degree + 1 B-spline basis functions on [lo, hi] with the given interior knots
    (clamped ends: the boundary knots repeated degree + 1 times), by the Cox-de Boor recursion.
    Returns an array of shape (len(x), K + degree + 1); each row sums to 1 on [lo, hi]."""
    x = np.asarray(x, dtype=float)
    t = np.concatenate([[lo] * (degree + 1), np.sort(np.asarray(interior, dtype=float)), [hi] * (degree + 1)])
    m = len(t) - degree - 1
    # degree 0 pieces, right-closed on the last non-empty interval so that x = hi is covered
    B = np.zeros((len(x), len(t) - 1))
    for i in range(len(t) - 1):
        if t[i] < t[i + 1]:
            B[:, i] = (x >= t[i]) & (x < t[i + 1])
            if t[i + 1] == hi:
                B[:, i] = (x >= t[i]) & (x <= hi)
    for p in range(1, degree + 1):
        Bn = np.zeros((len(x), len(t) - 1 - p))
        for i in range(len(t) - 1 - p):
            if t[i + p] > t[i]:
                Bn[:, i] += (x - t[i]) / (t[i + p] - t[i]) * B[:, i]
            if t[i + p + 1] > t[i + 1]:
                Bn[:, i] += (t[i + p + 1] - x) / (t[i + p + 1] - t[i + 1]) * B[:, i + 1]
        B = Bn
    return B[:, :m]


def spline_design(x, nknots, degree, lo=None, hi=None, quantile_knots=True):
    """Design matrix of a spline basis with nknots interior knots at quantiles of x (or equally spaced)."""
    x = np.asarray(x, dtype=float)
    lo = x.min() if lo is None else lo
    hi = x.max() if hi is None else hi
    if quantile_knots:
        knots = np.quantile(x, np.linspace(0, 1, nknots + 2)[1:-1])
    else:
        knots = np.linspace(lo, hi, nknots + 2)[1:-1]
    return bspline_basis(x, knots, degree, lo, hi), knots


# =========================================================================== 11.6 robust
def laplace_lp(X, y):
    """Least absolute deviations by the linear programme of (11.109)-(11.115)."""
    N, D = X.shape
    c = np.concatenate([np.zeros(D), np.ones(N)])
    I = np.eye(N)
    A = np.vstack([np.hstack([X, -I]), np.hstack([-X, -I])])
    b = np.concatenate([y, -y])
    res = optimize.linprog(c, A_ub=A, b_ub=b, bounds=[(None, None)] * D + [(0, None)] * N, method="highs")
    return res.x[:D]


def huber_loss(r, delta):
    a = np.abs(r)
    return np.where(a <= delta, 0.5 * r ** 2, delta * a - 0.5 * delta ** 2)       # (11.117)


def huber_irls(X, y, delta=1.0, iters=200):
    """Minimise sum huber_loss(y - Xw, delta) by iteratively reweighted least squares (weights min(1, delta/|r|))."""
    w = np.linalg.lstsq(X, y, rcond=None)[0]
    for _ in range(iters):
        r = y - X @ w
        u = np.minimum(1.0, delta / np.maximum(np.abs(r), 1e-12))
        wn = wls(X, y, u)
        if np.max(np.abs(wn - w)) < 1e-12:
            w = wn
            break
        w = wn
    return w


def student_em(X, y, nu=1.0, iters=500, w0=None):
    """MLE of w and sigma^2 for the Student-t likelihood (11.116) with fixed nu, by EM (scale-mixture weights)."""
    w = np.linalg.lstsq(X, y, rcond=None)[0] if w0 is None else w0.copy()
    r = y - X @ w
    s2 = np.mean(r ** 2)
    for _ in range(iters):
        r = y - X @ w
        u = (nu + 1.0) / (nu + r ** 2 / s2)
        wn = wls(X, y, u)
        r = y - X @ wn
        s2n = np.mean(u * r ** 2)
        if np.max(np.abs(wn - w)) < 1e-13 and abs(s2n - s2) < 1e-13:
            w, s2 = wn, s2n
            break
        w, s2 = wn, s2n
    return w, s2


def student_nll(X, y, w, s2, nu):
    r = y - X @ w
    return -np.sum(stats.t.logpdf(r / np.sqrt(s2), nu) - 0.5 * np.log(s2))


def ransac_line(X, y, trials=200, thresh=1.0, seed=0, min_pts=2):
    """RANSAC (Section 11.6.4): fit lines to random minimal samples, keep the model with most inliers, refit."""
    rng = np.random.default_rng(seed)
    best_in = None
    for _ in range(trials):
        idx = rng.choice(len(y), min_pts, replace=False)
        w = np.linalg.lstsq(X[idx], y[idx], rcond=None)[0]
        inl = np.abs(y - X @ w) < thresh
        if best_in is None or inl.sum() > best_in.sum():
            best_in = inl
    return np.linalg.lstsq(X[best_in], y[best_in], rcond=None)[0], best_in


# =========================================================================== 11.7 Bayesian
def posterior(X, y, sigma2, m0, S0):
    """(11.120)-(11.122): posterior mean and covariance of w for a N(m0, S0) prior and known sigma^2."""
    S0i = np.linalg.inv(S0)
    Sn = np.linalg.inv(S0i + X.T @ X / sigma2)
    mn = Sn @ (S0i @ m0 + X.T @ y / sigma2)
    return mn, Sn


def predictive(Xs, mn, Sn, sigma2):
    """(11.124): mean and variance of y at the rows of Xs."""
    return Xs @ mn, sigma2 + np.einsum("ij,jk,ik->i", Xs, Sn, Xs)


def sample_post_legs(X, y, prior_var, nsamp, rng, sigma_grid=None):
    """Exact posterior samples of (w, sigma) for y ~ N(Xw, sigma^2 I), w ~ N(0, prior_var I), sigma ~ Expon(1):
    the weights are integrated out analytically, sigma is drawn from its grid posterior, then w | sigma is Gaussian."""
    N, D = X.shape
    sg = np.linspace(0.01, 6.0, 4000) if sigma_grid is None else sigma_grid
    XXt = prior_var * X @ X.T
    logp = np.empty(len(sg))
    for i, s in enumerate(sg):
        C = s ** 2 * np.eye(N) + XXt
        sign, ld = np.linalg.slogdet(C)
        logp[i] = -0.5 * ld - 0.5 * y @ np.linalg.solve(C, y) - s       # Expon(1) prior on sigma
    p = np.exp(logp - logp.max())
    p /= p.sum()
    sig = rng.choice(sg, size=nsamp, p=p)
    W = np.empty((nsamp, D))
    for i, s in enumerate(sig):
        mn, Sn = posterior(X, y, s ** 2, np.zeros(D), prior_var * np.eye(D))
        W[i] = rng.multivariate_normal(mn, Sn)
    return W, sig


def hdi(samples, prob=0.95):
    """Highest density interval of a 1-D sample."""
    s = np.sort(samples)
    n = len(s)
    k = int(np.ceil(prob * n))
    widths = s[k - 1:] - s[:n - k + 1]
    i = int(np.argmin(widths))
    return s[i], s[i + k - 1]


# =========================================================================== data
def prostate(standardize="train"):
    """Prostate cancer data (Stamey et al. 1989): returns names, X (97 x 8), y (lpsa), train mask.

    standardize='train' centres and scales the predictors with the 67 training cases (ddof = 1);
    'all' uses all 97; None leaves the raw values.
    """
    import pandas as pd
    df = pd.read_csv(common.pml_file("ch11-prostate.csv"))
    names = list(df.columns[:8])
    X = df[names].values.astype(float)
    y = df["lpsa"].values.astype(float)
    tr = df["train"].values == 1
    if standardize == "train":
        X = (X - X[tr].mean(0)) / X[tr].std(0, ddof=1)
    elif standardize == "all":
        X = (X - X.mean(0)) / X.std(0, ddof=1)
    return names, X, y, tr


def kfold_ids(n, K, seed=0):
    rng = np.random.default_rng(seed)
    ids = np.arange(n) % K
    rng.shuffle(ids)
    return ids


def cv_curve(fit, X, y, params, K=10, seed=0):
    """K-fold CV mean and standard error of the squared error for each parameter in params;
    fit(Xtr, ytr, p) returns (intercept, weights)."""
    ids = kfold_ids(len(y), K, seed)
    err = np.zeros((len(params), len(y)))
    for k in range(K):
        te, tr = ids == k, ids != k
        for i, p in enumerate(params):
            b, w = fit(X[tr], y[tr], p)
            err[i, te] = (y[te] - b - X[te] @ w) ** 2
    m = err.mean(1)
    se = err.std(1, ddof=1) / np.sqrt(len(y))
    return m, se


def one_se_pick(m, se, order):
    """Simplest model within one standard error of the best; order lists indices from simplest to most complex."""
    i = int(np.argmin(m))
    for j in order:
        if m[j] <= m[i] + se[i]:
            return j
    return i


# =========================================================================== figures
def _out(out):
    return out


def fig_11_1(out=None):
    """Polynomials of degree 1 and 2 fitted to 21 points."""
    x, y, xt, yt = poly_data()
    xs = np.linspace(0, 20, 300)
    fig, axes = common.panel_grid(1, 2, size=(3.4, 2.7))
    for ax, deg, lab in zip(axes[0], (1, 2), "ab"):
        w = ols_qr(poly_feats(x, deg), y)
        ax.plot(xs, poly_feats(xs, deg) @ w, color=BLUE)
        ax.plot(x, y, "o", color=RED, ms=4)
        ax.set_title("degree %d" % deg)
        ax.set_xlabel("x")
        common.panel_label(ax, lab, "lower left")
    axes[0][0].set_ylabel("y")
    fig.tight_layout()
    savefig(fig, CH, "fig11-1", out)


def _rss_surface(x, y, g0, g1):
    X = poly_feats(x, 1)
    W0, W1 = np.meshgrid(g0, g1)
    R = np.empty_like(W0)
    for i in range(W0.shape[0]):
        for j in range(W0.shape[1]):
            r = y - X @ np.array([W0[i, j], W1[i, j]])
            R[i, j] = 0.5 * r @ r
    return W0, W1, R


def fig_11_2(out=None):
    """Contours and surface of the RSS for the straight-line fit of Figure 11.1a."""
    x, y, _, _ = poly_data()
    w = ols_qr(poly_feats(x, 1), y)
    g0 = np.linspace(w[0] - 9, w[0] + 9, 120)
    g1 = np.linspace(w[1] - 0.9, w[1] + 0.9, 120)
    W0, W1, R = _rss_surface(x, y, g0, g1)
    fig = plt.figure(figsize=(8.6, 3.4))
    ax = fig.add_subplot(1, 2, 1)
    cs = ax.contour(W0, W1, R, levels=12, cmap="viridis")
    ax.plot(*w, "x", color=BLUE, ms=9, mew=2)
    ax.set_xlabel(r"$w_0$")
    ax.set_ylabel(r"$w_1$")
    common.panel_label(ax, "a", "upper left")
    ax3 = fig.add_subplot(1, 2, 2, projection="3d")
    ax3.plot_surface(W0, W1, R, cmap="viridis", linewidth=0, antialiased=True, rstride=3, cstride=3)
    ax3.set_xlabel(r"$w_0$")
    ax3.set_ylabel(r"$w_1$")
    ax3.set_zlabel("RSS", labelpad=4)
    ax3.view_init(28, -60)
    fig.tight_layout()
    savefig(fig, CH, "fig11-2", out)


def fig_11_3(out=None):
    """Least squares as orthogonal projection onto the column space of A (m = 3, n = 2)."""
    A = np.array([[1.0, 0.1], [0.1, 1.0], [0.0, 0.2]])
    b = np.array([0.5, 0.8, 0.9])
    w = ols_qr(A, b)
    bh = A @ w
    fig = plt.figure(figsize=(4.4, 3.6))
    ax = fig.add_subplot(111, projection="3d")
    s, t = np.meshgrid(np.linspace(-0.3, 1.2, 8), np.linspace(-0.3, 1.2, 8))
    P = s[..., None] * A[:, 0] + t[..., None] * A[:, 1]
    ax.plot_surface(P[..., 0], P[..., 1], P[..., 2], color="#9ec5f4", alpha=0.35, linewidth=0)
    for v, lab, c in ((A[:, 0], r"$a_1$", BLUE), (A[:, 1], r"$a_2$", GREEN), (b, r"$b$", RED), (bh, r"$\hat b$", MAGENTA)):
        ax.plot([0, v[0]], [0, v[1]], [0, v[2]], color=c, lw=2)
        ax.text(*(v * 1.06), lab, color=c, fontsize=11)
    ax.plot([b[0], bh[0]], [b[1], bh[1]], [b[2], bh[2]], color=GREY, ls="--", lw=1.4)
    ax.set_axis_off()
    ax.view_init(22, -38)
    fig.tight_layout()
    savefig(fig, CH, "fig11-3", out)


def fig_11_4(out=None):
    """Recursive least squares estimates of the intercept and slope as the data arrive, against the batch answer."""
    x, y, _, _ = poly_data()
    # the first 21 points arrive in a shuffled order so the path is not monotone in x
    order = np.random.default_rng(5).permutation(len(x))
    xs, ys = x[order], y[order]
    w0, w1 = online_simple(xs, ys)
    wb = ols_qr(poly_feats(x, 1), y)
    fig, ax = plt.subplots(figsize=(4.8, 3.0))
    t = np.arange(2, len(x) + 1)
    ax.plot(t, w0, color=RED, label=r"$w_0$")
    ax.plot(t, w1, color=BLUE, label=r"$w_1$")
    ax.axhline(wb[0], color=RED, ls="--", lw=1, label=r"$w_0$ batch")
    ax.axhline(wb[1], color=BLUE, ls="--", lw=1, label=r"$w_1$ batch")
    ax.set_xlabel("number of points seen")
    ax.set_ylabel("estimate")
    ax.set_ylim(-30, 6)
    ax.legend(frameon=False, ncol=2, fontsize=8, loc="lower right")
    fig.tight_layout()
    savefig(fig, CH, "fig11-4", out)


def fig_11_5(out=None):
    """Residual plots for the degree 1 and degree 2 fits."""
    x, y, _, _ = poly_data()
    fig, axes = common.panel_grid(1, 2, size=(3.4, 2.5))
    for ax, deg, lab in zip(axes[0], (1, 2), "ab"):
        w = ols_qr(poly_feats(x, deg), y)
        r = y - poly_feats(x, deg) @ w
        ax.plot(x, r, "o", color=BLUE, ms=4)
        ax.axhline(0, color="k", lw=0.8)
        ax.set_ylim(-8, 8)
        ax.set_xlabel("x")
        ax.set_title("degree %d, training residuals" % deg)
        common.panel_label(ax, lab, "lower left")
    axes[0][0].set_ylabel("residual")
    fig.tight_layout()
    savefig(fig, CH, "fig11-5", out)


def fig_11_6(out=None):
    """Predicted against true values on a test set, with the test R^2."""
    x, y, xt, yt = poly_data()
    fig, axes = common.panel_grid(1, 2, size=(3.3, 3.3))
    for ax, deg, lab in zip(axes[0], (1, 2), "ab"):
        w = ols_qr(poly_feats(x, deg), y)
        yh = poly_feats(xt, deg) @ w
        ax.plot(yt, yh, "o", color=BLUE, ms=2.5, alpha=0.6)
        lim = [min(yt.min(), yh.min()) - 1, max(yt.max(), yh.max()) + 1]
        ax.plot(lim, lim, color=RED, lw=1)
        ax.set_xlim(lim)
        ax.set_ylim(lim)
        ax.set_xlabel("true y")
        ax.set_title(r"degree %d, test $R^2=%.3f$" % (deg, r2_score(yt, yh)), fontsize=9.5)
        common.panel_label(ax, lab, "lower right")
    axes[0][0].set_ylabel("predicted y")
    fig.tight_layout()
    savefig(fig, CH, "fig11-6", out)


def _ellipse_xy(center, A, level, n=200):
    """Points with (w - c)' A (w - c) = level."""
    t = np.linspace(0, 2 * np.pi, n)
    L = np.linalg.cholesky(A)
    z = np.sqrt(level) * np.vstack([np.cos(t), np.sin(t)])
    p = linalg.solve_triangular(L.T, z, lower=False)
    return p[0] + center[0], p[1] + center[1]


def fig_11_7(out=None):
    """Geometry of ridge regression: the likelihood ellipse, the prior circle and the MAP estimate."""
    A = np.array([[0.25, 0.0], [0.0, 3.0]])           # X'X: w1 poorly determined, w2 well determined
    wml = np.array([2.2, 1.6])
    lam = 1.3
    wmap = np.linalg.solve(A + lam * np.eye(2), A @ wml)
    fig, axes = common.panel_grid(1, 2, size=(3.4, 3.4))
    for ax, lab, rot in zip(axes[0], "ab", (0.0, 0.5)):
        R = np.array([[np.cos(rot), -np.sin(rot)], [np.sin(rot), np.cos(rot)]])
        Ar = R @ A @ R.T
        wm = R @ wml
        wp = np.linalg.solve(Ar + lam * np.eye(2), Ar @ wm)
        for lev in (0.4, 1.2, 2.6, 4.6):
            ax.plot(*_ellipse_xy(wm, Ar, lev * 1.0), color=BLUE, lw=1.2)
        th = np.linspace(0, 2 * np.pi, 200)
        for rr in (np.linalg.norm(wp), 0.5 * np.linalg.norm(wp)):
            ax.plot(rr * np.cos(th), rr * np.sin(th), color=RED, lw=1.2)
        ax.plot(0, 0, "o", color=RED, ms=5)
        ax.plot(*wm, "x", color=BLUE, ms=8, mew=2)
        ax.plot(*wp, "s", color="k", ms=5)
        ax.annotate("prior mean", (0, 0), (0.15, -0.55), fontsize=8, color=RED)
        ax.annotate("ML", wm, (wm[0] + 0.12, wm[1] + 0.1), fontsize=8, color=BLUE)
        ax.annotate("MAP", wp, (wp[0] + 0.12, wp[1] - 0.45), fontsize=8)
        ax.set_aspect("equal")
        ax.set_xlim(-2.8, 3.6)
        ax.set_ylim(-1.5, 3.2)
        ax.set_xlabel(r"$w_1$")
        common.panel_label(ax, lab, "upper left")
    axes[0][0].set_ylabel(r"$w_2$")
    fig.tight_layout()
    savefig(fig, CH, "fig11-7", out)


def _constrained_min(A, wml, kind, B, n=40001):
    """Minimise (w - wml)'A(w - wml) over the l1 ball (kind=1) or l2 ball (kind=2) of radius B by scanning the boundary."""
    t = np.linspace(0, 2 * np.pi, n)
    if kind == 2:
        P = B * np.vstack([np.cos(t), np.sin(t)])
    else:
        c, s = np.cos(t), np.sin(t)
        r = B / (np.abs(c) + np.abs(s))
        P = np.vstack([r * c, r * s])
    d = P - wml[:, None]
    f = np.einsum("in,ij,jn->n", d, A, d)
    i = np.argmin(f)
    return P[:, i], f[i]


def fig_11_8(out=None):
    """l1 against l2 constraints: the corner of the l1 ball gives a sparse solution."""
    A = np.array([[1.0, 0.0], [0.0, 1.0]])
    R = np.array([[np.cos(0.55), -np.sin(0.55)], [np.sin(0.55), np.cos(0.55)]])
    A = R @ np.diag([2.6, 0.35]) @ R.T
    wml = np.array([2.0, 0.9])
    B1 = 1.25
    B2 = 1.35
    fig, axes = common.panel_grid(1, 2, size=(3.4, 3.4))
    for ax, kind, B, lab in zip(axes[0], (1, 2), (B1, B2), "ab"):
        wmin, fmin = _constrained_min(A, wml, kind, B)
        t = np.linspace(0, 2 * np.pi, 400)
        if kind == 1:
            ax.fill([B, 0, -B, 0], [0, B, 0, -B], color="#f6c9c9", ec=RED)
        else:
            ax.fill(B * np.cos(t), B * np.sin(t), color="#f6c9c9", ec=RED)
        for lev in (fmin, 2.0 * fmin + 0.3, 4.0 * fmin + 1.0):
            ax.plot(*_ellipse_xy(wml, A, lev), color=BLUE, lw=1.2)
        ax.plot(*wml, "x", color=BLUE, ms=8, mew=2)
        ax.plot(*wmin, "o", color="k", ms=5)
        ax.axhline(0, color="k", lw=0.5)
        ax.axvline(0, color="k", lw=0.5)
        ax.set_aspect("equal")
        ax.set_xlim(-2.0, 3.2)
        ax.set_ylim(-2.0, 2.4)
        ax.set_xlabel(r"$w_1$")
        ax.set_title(r"$\ell_%d$ constraint" % kind)
        common.panel_label(ax, lab, "upper left")
    axes[0][0].set_ylabel(r"$w_2$")
    fig.tight_layout()
    savefig(fig, CH, "fig11-8", out)


def fig_11_9(out=None):
    """Soft and hard thresholding, with the least squares line."""
    lam = 1.0
    c = np.linspace(-3, 3, 601)
    fig, axes = common.panel_grid(1, 2, size=(3.3, 2.8))
    for ax, lab, kind in zip(axes[0], "ab", ("soft", "hard")):
        ax.plot(c, c, color=GREY, ls=":", lw=1.2, label="least squares")
        ax.plot(c, soft_threshold(c, lam) if kind == "soft" else np.where(np.abs(c) > lam, c, 0.0), color=RED, label=kind + " threshold")
        ax.axvspan(-lam, lam, color="#fff2cc", alpha=0.6, lw=0)
        ax.set_xlabel(r"$c_d / a_d$")
        ax.set_xlim(-3, 3)
        ax.set_ylim(-3, 3)
        ax.legend(frameon=False, fontsize=8, loc="upper left")
        common.panel_label(ax, lab, "lower right")
    axes[0][0].set_ylabel(r"$\hat w_d$")
    fig.tight_layout()
    savefig(fig, CH, "fig11-9", out)


PROSTATE_CACHE = {}


def prostate_paths():
    """Everything Figures 11.10-11.12 and Table 11.1 need, computed once."""
    if PROSTATE_CACHE:
        return PROSTATE_CACHE
    names, X, y, tr = prostate("train")
    Xt, yt = X[tr], y[tr]
    xm, ym = Xt.mean(0), yt.mean()          # Xt is centred by construction
    Xc, yc = Xt - xm, yt - ym
    lams, W = lars_lasso(Xc, yc)
    wols = np.linalg.solve(Xc.T @ Xc, Xc.T @ yc)
    PROSTATE_CACHE.update(names=names, X=X, y=y, tr=tr, Xc=Xc, yc=yc, lams=lams, W=W, wols=wols, ym=ym)
    return PROSTATE_CACHE


def table_11_1():
    """Lasso coefficients at the critical values of lambda (Table 11.1)."""
    P = prostate_paths()
    return P["lams"], P["W"]


def fig_11_10(out=None):
    """Ridge and lasso regularisation paths on the prostate data (training cases, standardised)."""
    P = prostate_paths()
    Xc, yc, names = P["Xc"], P["yc"], P["names"]
    lam_grid = np.logspace(-3, 3.2, 200)
    ridge_w = np.array([np.linalg.solve(Xc.T @ Xc + l * np.eye(8), Xc.T @ yc) for l in lam_grid])
    dof = np.array([ridge_dof(Xc, l) for l in lam_grid])

    def ridge_fit_ic(X, y, l):
        xm, ym = X.mean(0), y.mean()
        w = np.linalg.solve((X - xm).T @ (X - xm) + l * np.eye(X.shape[1]), (X - xm).T @ (y - ym))
        return ym - xm @ w, w
    cvm, cvse = cv_curve(ridge_fit_ic, P["X"][P["tr"]], P["y"][P["tr"]], lam_grid, K=5)
    ipick = one_se_pick(cvm, cvse, order=list(np.argsort(-lam_grid)))
    fig, axes = common.panel_grid(1, 2, size=(4.2, 3.2))
    ax = axes[0][0]
    cols = plt.get_cmap("tab10")(np.arange(8))
    for j in range(8):
        ax.plot(dof, ridge_w[:, j], color=cols[j], label=names[j])
    ax.axvline(dof[ipick], color="k", ls="--", lw=0.9)
    ax.set_xlabel(r"effective degrees of freedom $\mathrm{dof}(\lambda)$")
    ax.set_ylabel("coefficient")
    ax.legend(frameon=False, fontsize=7, ncol=2, loc="upper left")
    common.panel_label(ax, "a", "lower right")
    ax = axes[0][1]
    lams, W = P["lams"], P["W"]
    s = np.abs(W).sum(1) / np.abs(P["wols"]).sum()
    for j in range(8):
        ax.plot(s, W[:, j], color=cols[j], marker=".", ms=3, label=names[j])
    for v in s[1:-1]:
        ax.axvline(v, color=GREY, lw=0.4)
    ax.set_xlabel(r"shrinkage factor $s=\|\hat w\|_1/\|\hat w_{\rm ols}\|_1$")
    common.panel_label(ax, "b", "lower right")
    fig.tight_layout()
    savefig(fig, CH, "fig11-10", out)
    print("ridge 5-fold CV one-SE pick: lambda = %.3f, dof = %.2f" % (lam_grid[ipick], dof[ipick]))


def prostate_comparison(seed=0):
    """OLS, best subset, ridge and lasso on the prostate data (Figure 11.11, Table of test errors).

    Predictors are standardised with all 97 cases (as in the Hastie-Tibshirani-Friedman comparison); tuning
    parameters are chosen by 10-fold CV on the 67 training cases with the one-standard-error rule."""
    names, X, y, tr = prostate("all")
    Xt, yt, Xs, ys = X[tr], y[tr], X[~tr], y[~tr]

    def ols_f(Xa, ya, _):
        xm, ym = Xa.mean(0), ya.mean()
        w = np.linalg.solve((Xa - xm).T @ (Xa - xm), (Xa - xm).T @ (ya - ym))
        return ym - xm @ w, w

    def ridge_f(Xa, ya, l):
        xm, ym = Xa.mean(0), ya.mean()
        w = np.linalg.solve((Xa - xm).T @ (Xa - xm) + l * np.eye(8), (Xa - xm).T @ (ya - ym))
        return ym - xm @ w, w

    def lasso_f(Xa, ya, l):
        xm, ym = Xa.mean(0), ya.mean()
        w = lasso_cd(Xa - xm, ya - ym, l)
        return ym - xm @ w, w

    def subset_f(Xa, ya, K):
        xm, ym = Xa.mean(0), ya.mean()
        w = best_subset(Xa - xm, ya - ym, int(K))
        return ym - xm @ w, w
    res = {}
    lam_r = np.logspace(-2, 3, 60)
    m, se = cv_curve(ridge_f, Xt, yt, lam_r, K=10, seed=seed)
    ir = one_se_pick(m, se, order=list(np.argsort(-lam_r)))
    lmax = np.abs((Xt - Xt.mean(0)).T @ (yt - yt.mean())).max()
    lam_l = np.linspace(lmax, 0.0, 61)[:-1]
    m2, se2 = cv_curve(lasso_f, Xt, yt, lam_l, K=10, seed=seed)
    il = one_se_pick(m2, se2, order=list(range(len(lam_l))))
    Ks = list(range(0, 9))
    m3, se3 = cv_curve(subset_f, Xt, yt, Ks, K=10, seed=seed)
    isub = one_se_pick(m3, se3, order=list(range(len(Ks))))
    fits = {"LS": ols_f(Xt, yt, None), "Best subset": subset_f(Xt, yt, Ks[isub]),
            "Ridge": ridge_f(Xt, yt, lam_r[ir]), "Lasso": lasso_f(Xt, yt, lam_l[il])}
    for k, (b, w) in fits.items():
        e = ys - b - Xs @ w
        res[k] = dict(b=b, w=w, abs_err=np.abs(e), mse=float(np.mean(e ** 2)), se=float(np.std(e ** 2, ddof=1) / np.sqrt(len(e))))
    res["_choice"] = dict(ridge_lambda=float(lam_r[ir]), lasso_lambda=float(lam_l[il]), subset_size=int(Ks[isub]))
    return names, res


def fig_11_11(out=None):
    """Table: coefficients and test error of OLS, best subset, ridge and lasso on the prostate data (a printed table)."""
    names, res = prostate_comparison()
    print("%-10s" % "term", *["%11s" % k for k in ("LS", "Best subset", "Ridge", "Lasso")])
    print("%-10s" % "intercept", *["%11.3f" % res[k]["b"] for k in ("LS", "Best subset", "Ridge", "Lasso")])
    for j, nm in enumerate(names):
        print("%-10s" % nm, *["%11.3f" % res[k]["w"][j] for k in ("LS", "Best subset", "Ridge", "Lasso")])
    print("%-10s" % "test MSE", *["%11.3f" % res[k]["mse"] for k in ("LS", "Best subset", "Ridge", "Lasso")])
    print("%-10s" % "std error", *["%11.3f" % res[k]["se"] for k in ("LS", "Best subset", "Ridge", "Lasso")])
    print(res["_choice"])
    lam, W = table_11_1()
    print("Table 11.1 (critical lambda, coefficients):")
    for l, w in zip(lam, W):
        print("%8.3f" % l, " ".join("%7.4f" % v for v in w))


def fig_11_12(out=None):
    """Box plot of the absolute test errors of the four methods on the prostate data."""
    names, res = prostate_comparison()
    keys = ("LS", "Best subset", "Ridge", "Lasso")
    fig, ax = plt.subplots(figsize=(4.4, 3.0))
    ax.boxplot([res[k]["abs_err"] for k in keys], tick_labels=list(keys), medianprops=dict(color=RED))
    ax.set_ylabel("absolute test error")
    fig.tight_layout()
    savefig(fig, CH, "fig11-12", out)


def sparse_problem(D=4096, N=1024, nz=160, noise=0.01, seed=7):
    """The sparse signal recovery problem of Figure 11.13: random +-1 spikes, an orthonormal-row random design."""
    rng = np.random.default_rng(seed)
    w = np.zeros(D)
    idx = rng.choice(D, nz, replace=False)
    w[idx] = rng.choice([-1.0, 1.0], nz)
    Q, _ = np.linalg.qr(rng.standard_normal((D, N)))
    X = Q.T                                                    # N x D, rows orthonormal
    y = X @ w + noise * rng.standard_normal(N)
    return X, y, w


def fig_11_13(out=None):
    """Sparse signal recovery: the true signal, the lasso, the debiased lasso and the minimum norm solution."""
    X, y, w = sparse_problem()
    lmax = np.abs(X.T @ y).max()
    lam = 0.1 * lmax
    wl = lasso_fista(X, y, lam, iters=1500, L=1.0)
    wd = debias(X, y, wl)
    wmn = X.T @ y                                              # pinv(X) y, as X X' = I
    rows = [(w, "Original (D = 4096, number of nonzeros = %d)" % int((w != 0).sum())),
            (wl, r"$\ell_1$ reconstruction ($\lambda=%.4f$, MSE = %.2g)" % (lam, np.mean((wl - w) ** 2))),
            (wd, "Debiased (MSE = %.2e)" % np.mean((wd - w) ** 2)),
            (wmn, "Minimum norm solution (MSE = %.3f)" % np.mean((wmn - w) ** 2))]
    fig, axes = plt.subplots(4, 1, figsize=(6.4, 6.0), sharex=True)
    for ax, (v, t) in zip(axes, rows):
        ax.plot(v, color=BLUE, lw=0.6)
        ax.set_title(t, fontsize=9)
        ax.set_ylim(-1.3, 1.3)
    axes[-1].set_xlabel("index d")
    fig.tight_layout()
    savefig(fig, CH, "fig11-13", out)
    print("lambda_max = %.4f; lasso MSE %.3g, debiased MSE %.3g, min norm MSE %.3g" % (
        lmax, np.mean((wl - w) ** 2), np.mean((wd - w) ** 2), np.mean((wmn - w) ** 2)))


def group_problem(kind, seed=11, D=4096, G=64, active=8, N=1024, sd=0.01):
    rng = np.random.default_rng(seed)
    gs = D // G
    groups = [np.arange(g * gs, (g + 1) * gs) for g in range(G)]
    w = np.zeros(D)
    for g in rng.choice(G, active, replace=False):
        w[groups[g]] = rng.standard_normal(gs) if kind == "gauss" else 1.0
    Q, _ = np.linalg.qr(rng.standard_normal((D, N)))
    X = Q.T
    y = X @ w + sd * rng.standard_normal(N)
    return X, y, w, groups


def _group_figure(kind, name, tau, out):
    X, y, w, groups = group_problem(kind)
    est = {}
    est["Standard L1"] = lasso_fista(X, y, tau, iters=800, L=1.0)
    est["Block-L2"] = group_fista(X, y, tau, groups, prox_block_l2, iters=800, L=1.0)
    est["Block-Linf"] = group_fista(X, y, tau, groups, prox_block_linf, iters=800, L=1.0)
    fig, axes = plt.subplots(4, 1, figsize=(6.4, 6.0), sharex=True)
    axes[0].plot(w, color=BLUE, lw=0.7)
    axes[0].set_title("Original (D = 4096, number of groups = 64, active groups = 8)", fontsize=9)
    stats_out = {}
    for ax, (k, v) in zip(axes[1:], est.items()):
        wd = debias(X, y, v)
        mse = np.mean((wd - w) ** 2)
        stats_out[k] = mse
        ax.plot(wd, color=BLUE, lw=0.7)
        ax.set_title(r"%s (debiased, $\tau=%.3g$, MSE = %.3g)" % (k, tau, mse), fontsize=9)
    axes[-1].set_xlabel("index d")
    lim = np.abs(w).max() * 1.15
    for ax in axes:
        ax.set_ylim(-lim if kind == "gauss" else -0.1, lim)
    fig.tight_layout()
    savefig(fig, CH, name, out)
    print({k: float("%.3g" % v) for k, v in stats_out.items()})


def fig_11_14(out=None):
    """Group lasso, piecewise Gaussian signal: l1, block-l2 and block-linf."""
    _group_figure("gauss", "fig11-14", 0.35, out)


def fig_11_15(out=None):
    """Group lasso, piecewise constant signal."""
    _group_figure("const", "fig11-15", 0.35, out)


def fig_11_16(out=None):
    """B-spline bases of degree 0, 1 and 3 with knots at 0.25, 0.5 and 0.75, and random weighted combinations."""
    xs = np.linspace(0, 1, 400)
    knots = [0.25, 0.5, 0.75]
    rng = np.random.default_rng(2)
    fig, axes = common.panel_grid(2, 3, size=(2.6, 2.1))
    for j, (deg, ttl) in enumerate(((0, "Piecewise constant"), (1, "Piecewise linear"), (3, "Cubic spline"))):
        B = bspline_basis(xs, knots, deg)
        for i in range(B.shape[1]):
            axes[0][j].plot(xs, B[:, i], lw=1.3)
        for k in knots:
            axes[0][j].plot(k, 0, "ko", ms=3, clip_on=False)
        axes[0][j].set_title(ttl)
        w = rng.standard_normal(B.shape[1])
        axes[1][j].plot(xs, B @ w, color="k")
        for k in knots:
            axes[1][j].axvline(k, color=GREY, lw=0.5)
    fig.tight_layout()
    savefig(fig, CH, "fig11-16", out)


def fig_11_17(out=None):
    """Design matrices of the degree 0, 1 and 3 B-spline bases on 20 equally spaced inputs."""
    x = np.linspace(0, 1, 20)
    fig, axes = common.panel_grid(1, 3, size=(2.5, 3.6))
    for ax, deg, lab, ttl in zip(axes[0], (0, 1, 3), "abc", ("Piecewise constant", "Piecewise linear", "Cubic spline")):
        B = bspline_basis(x, [0.25, 0.5, 0.75], deg)
        ax.imshow(B, aspect="auto", cmap="gray_r", vmin=0, vmax=1)
        ax.set_title(ttl)
        ax.set_xlabel("basis function")
        ax.set_xticks(range(B.shape[1]))
        common.panel_label(ax, lab, "lower right")
    axes[0][0].set_ylabel("input (row)")
    fig.tight_layout()
    savefig(fig, CH, "fig11-17", out)


def nile_data():
    from statsmodels.datasets import nile
    d = nile.load_pandas().data
    return d["year"].values.astype(float), d["volume"].values.astype(float) / 100.0


def fig_11_18(out=None):
    """A cubic regression spline with 15 knots at the quantiles of the inputs (stand-in series: Nile flow)."""
    x, y = nile_data()
    B, knots = spline_design(x, 15, 3)
    lam = 1e-3
    w = ridge_fit(B, y, lam, penalize_first=True)
    xs = np.linspace(x.min(), x.max(), 600)
    Bs = bspline_basis(xs, knots, 3, x.min(), x.max())
    fig, ax = plt.subplots(figsize=(5.2, 3.0))
    ax.plot(x, y, "o", color=GREY, ms=3)
    ax.plot(xs, Bs @ w, color=BLUE)
    for k in knots:
        ax.axvline(k, color="#cccccc", lw=0.5, zorder=0)
    ax.set_xlabel("year")
    ax.set_ylabel(r"annual flow ($10^{10}\,\mathrm{m^3}$)")
    fig.tight_layout()
    savefig(fig, CH, "fig11-18", out)


def robust_data(seed=4, n=30, n_out=8):
    rng = np.random.default_rng(seed)
    x = np.sort(rng.uniform(0, 1, n))
    y = -1.0 + 4.0 * x + 0.35 * rng.standard_normal(n)
    out = rng.choice(np.where((x > 0.1) & (x < 0.95))[0], n_out, replace=False)
    y[out] -= rng.uniform(3.5, 6.0, n_out)
    return x, y, out


def robust_fits(x, y):
    X = poly_feats(x, 1)
    w_ls = ols_qr(X, y)
    w_lap = laplace_lp(X, y)
    w_hub = huber_irls(X, y, 1.0)
    w_st, s2 = student_em(X, y, nu=1.0, w0=w_lap)
    return dict(ls=w_ls, laplace=w_lap, huber=w_hub, student=w_st, student_s2=s2)


def fig_11_19(out=None):
    """Robust linear regression: least squares, Laplace, Student and Huber fits to data with outliers; the loss functions."""
    x, y, out_idx = robust_data()
    F = robust_fits(x, y)
    xs = np.linspace(0, 1, 100)
    Xs = poly_feats(xs, 1)
    fig, axes = common.panel_grid(1, 2, size=(4.0, 3.1))
    ax = axes[0][0]
    ax.plot(x, y, "o", color=BLUE, ms=4, mfc="none")
    ax.plot(xs, Xs @ F["ls"], color=RED, ls=":", label="least squares")
    ax.plot(xs, Xs @ F["laplace"], color="k", ls="--", label="Laplace")
    ax.plot(xs, Xs @ F["student"], color=GREEN, ls="-.", label=r"Student, $\nu=1$")
    ax.plot(xs, Xs @ F["huber"], color=ORANGE, label=r"Huber, $\delta=1$")
    ax.set_xlabel("x")
    ax.set_ylabel("y")
    ax.legend(frameon=False, fontsize=7.5, loc="lower right")
    common.panel_label(ax, "a", "upper left")
    ax = axes[0][1]
    r = np.linspace(-3, 3, 400)
    ax.plot(r, 0.5 * r ** 2, color=RED, ls=":", label=r"$\ell_2$")
    ax.plot(r, np.abs(r), color="k", ls="--", label=r"$\ell_1$")
    ax.plot(r, huber_loss(r, 1.5), color=ORANGE, label="Huber")
    ax.set_xlabel("residual r")
    ax.set_ylim(-0.3, 5)
    ax.legend(frameon=False, fontsize=8)
    common.panel_label(ax, "b", "upper center")
    fig.tight_layout()
    savefig(fig, CH, "fig11-19", out)


BAYES_TRUE = np.array([-0.3, 0.5])
BAYES_SIGMA = 0.2
BAYES_ALPHA = 2.0


def bayes_data(n=100, seed=1):
    rng = np.random.default_rng(seed)
    x = rng.uniform(-1, 1, n)
    y = BAYES_TRUE[0] + BAYES_TRUE[1] * x + BAYES_SIGMA * rng.standard_normal(n)
    return x, y


def fig_11_20(out=None):
    """Sequential Bayesian inference for a straight line: likelihood of the latest point, posterior and sampled lines."""
    x, y = bayes_data()
    g = np.linspace(-1, 1, 120)
    W0, W1 = np.meshgrid(g, g)
    xs = np.linspace(-1, 1, 50)
    rng = np.random.default_rng(0)
    rows = (0, 1, 2, 100)
    fig, axes = plt.subplots(len(rows), 3, figsize=(7.4, 9.0))
    S0 = np.eye(2) / BAYES_ALPHA
    for r, n in enumerate(rows):
        X = poly_feats(x[:n], 1)
        mn, Sn = posterior(X, y[:n], BAYES_SIGMA ** 2, np.zeros(2), S0)
        ax = axes[r][0]
        if n > 0:
            lik = np.exp(-0.5 * (y[n - 1] - W0 - W1 * x[n - 1]) ** 2 / BAYES_SIGMA ** 2)
            ax.contourf(W0, W1, lik, 20, cmap="jet")
            ax.plot(*BAYES_TRUE, "+", color="w", ms=9, mew=2)
        else:
            ax.axis("off")
        ax2 = axes[r][1]
        Sinv = np.linalg.inv(Sn)
        d0, d1 = W0 - mn[0], W1 - mn[1]
        q = Sinv[0, 0] * d0 ** 2 + 2 * Sinv[0, 1] * d0 * d1 + Sinv[1, 1] * d1 ** 2
        ax2.contourf(W0, W1, np.exp(-0.5 * q), 20, cmap="jet")
        ax2.plot(*BAYES_TRUE, "+", color="w", ms=9, mew=2)
        ax3 = axes[r][2]
        for w in rng.multivariate_normal(mn, Sn, 6):
            ax3.plot(xs, w[0] + w[1] * xs, color=RED, lw=1)
        ax3.plot(x[:n], y[:n], "o", color=BLUE, ms=3)
        for a in (ax, ax2):
            a.set_xlim(-1, 1)
            a.set_ylim(-1, 1)
            a.set_xlabel(r"$w_0$", fontsize=8)
            a.set_ylabel(r"$w_1$", fontsize=8)
        ax3.set_xlim(-1, 1)
        ax3.set_ylim(-1, 1)
        ax3.set_xlabel("x", fontsize=8)
        ax3.set_ylabel("y", fontsize=8)
        ax3.set_title("N = %d" % n, fontsize=9)
    axes[0][0].set_title("likelihood", fontsize=9)
    axes[0][1].set_title("prior / posterior", fontsize=9)
    fig.tight_layout()
    savefig(fig, CH, "fig11-20", out)


def pred_data(seed=6, n=12):
    rng = np.random.default_rng(seed)
    x = np.sort(rng.uniform(-4, 4, n))
    y = 55.0 + 2.0 * x + 1.6 * x ** 2 + 6.0 * rng.standard_normal(n)
    return x, y


def fig_11_21(out=None):
    """Plug-in against posterior predictive for a quadratic fit, with sampled functions."""
    x, y = pred_data()
    deg = 2
    X = poly_feats(x, deg)
    wml = ols_qr(X, y)
    s2 = np.mean((y - X @ wml) ** 2)
    xs = np.linspace(-6, 6, 200)
    Xs = poly_feats(xs, deg)
    S0 = 1e4 * np.eye(3)
    mn, Sn = posterior(X, y, s2, np.zeros(3), S0)
    mu, var = predictive(Xs, mn, Sn, s2)
    rng = np.random.default_rng(3)
    fig, axes = common.panel_grid(2, 2, size=(3.3, 2.6))
    ax = axes[0][0]
    ax.plot(xs, Xs @ wml, color="k")
    ax.fill_between(xs, Xs @ wml - 2 * np.sqrt(s2), Xs @ wml + 2 * np.sqrt(s2), color="#cfd8e6")
    ax.set_title("Plug-in approximation", fontsize=9)
    ax = axes[0][1]
    ax.plot(xs, mu, color="k")
    ax.fill_between(xs, mu - 2 * np.sqrt(var), mu + 2 * np.sqrt(var), color="#cfd8e6")
    ax.set_title("Posterior predictive", fontsize=9)
    ax = axes[1][0]
    for _ in range(10):
        ax.plot(xs, Xs @ wml, color=RED, lw=1)
    ax.set_title("function drawn from plug-in", fontsize=9)
    ax = axes[1][1]
    for w in rng.multivariate_normal(mn, Sn, 10):
        ax.plot(xs, Xs @ w, color=RED, lw=1)
    ax.set_title("functions drawn from posterior", fontsize=9)
    for ax in axes.ravel():
        ax.plot(x, y, "o", color=BLUE, ms=4)
        ax.set_ylim(0, 140)
    for lab, ax in zip("abcd", axes.ravel()):
        common.panel_label(ax, lab, "upper center")
    fig.tight_layout()
    savefig(fig, CH, "fig11-21", out)


def centering_data(seed=2, n=20):
    rng = np.random.default_rng(seed)
    x = rng.uniform(4.0, 10.0, n)
    y = 1.0 + 0.8 * x + 1.0 * rng.standard_normal(n)
    return x, y


def fig_11_22(out=None):
    """Posterior samples of (w0, w1) for the original and the centred inputs."""
    x, y = centering_data()
    rng = np.random.default_rng(1)
    S0 = 100.0 * np.eye(2)
    fig, axes = common.panel_grid(1, 2, size=(3.4, 3.2))
    res = {}
    for ax, xx, lab, ttl in zip(axes[0], (x, x - x.mean()), "ab", ("original data", "centred data")):
        X = poly_feats(xx, 1)
        mn, Sn = posterior(X, y, 1.0, np.zeros(2), S0)
        W = rng.multivariate_normal(mn, Sn, 1500)
        ax.plot(W[:, 0], W[:, 1], ".", color=BLUE, ms=2, alpha=0.5)
        ax.set_xlabel(r"$w_0$")
        ax.set_title(ttl, fontsize=9.5)
        common.panel_label(ax, lab, "upper right")
        res[lab] = np.corrcoef(W.T)[0, 1]
    axes[0][0].set_ylabel(r"$w_1$")
    fig.tight_layout()
    savefig(fig, CH, "fig11-22", out)
    print("posterior correlation of (w0, w1): original %.3f, centred %.3f" % (res["a"], res["b"]))


def legs_data(seed=5, n=100):
    rng = np.random.default_rng(seed)
    h = rng.normal(10.0, 2.0, n)
    rho = rng.uniform(0.4, 0.5, n)
    l = rng.normal(rho * h, 0.02)
    r = rng.normal(rho * h, 0.02)
    return h, l, r


LEGS_CACHE = {}


def legs_posterior(nsamp=20000):
    if "W" not in LEGS_CACHE:
        h, l, r = legs_data()
        X = np.column_stack([np.ones(len(h)), l, r])
        rng = np.random.default_rng(0)
        W, sig = sample_post_legs(X, h, 100.0, nsamp, rng)
        LEGS_CACHE.update(W=W, sig=sig, h=h, l=l, r=r)
    return LEGS_CACHE


def fig_11_23(out=None):
    """Posterior marginals (with 95% HDI) of the intercept, the two leg coefficients and sigma."""
    L = legs_posterior()
    W, sig = L["W"], L["sig"]
    names = [r"$\alpha$", r"$\beta_l$", r"$\beta_r$", r"$\sigma$"]
    cols = np.column_stack([W, sig])
    fig, ax = plt.subplots(figsize=(4.6, 2.9))
    for i, (nm, v) in enumerate(zip(names, cols.T)):
        lo, hi = hdi(v, 0.95)
        ax.plot([lo, hi], [i, i], color=BLUE, lw=3)
        ax.plot(np.median(v), i, "o", color=BLUE, ms=5)
        ax.text(hi + 0.15, i, "mean %.2f" % v.mean(), va="center", fontsize=8)
    ax.set_yticks(range(4))
    ax.set_yticklabels(names)
    ax.axvline(0, color=GREY, lw=0.6)
    ax.set_xlim(-6, 9)
    ax.set_xlabel("posterior value (bar: 95% HDI, dot: median)")
    fig.tight_layout()
    savefig(fig, CH, "fig11-23", out)
    print("beta_l mean %.2f, beta_r mean %.2f, sum mean %.3f (sd %.3f), corr %.3f" % (
        W[:, 1].mean(), W[:, 2].mean(), (W[:, 1] + W[:, 2]).mean(), (W[:, 1] + W[:, 2]).std(), np.corrcoef(W[:, 1], W[:, 2])[0, 1]))


def fig_11_24(out=None):
    """Joint posterior of (beta_l, beta_r) and the posterior of their sum."""
    L = legs_posterior()
    W = L["W"]
    fig, axes = common.panel_grid(1, 2, size=(3.5, 3.1))
    ax = axes[0][0]
    ax.plot(W[::10, 2], W[::10, 1], ".", color=BLUE, ms=2, alpha=0.5)
    ax.set_xlabel(r"$\beta_r$")
    ax.set_ylabel(r"$\beta_l$")
    common.panel_label(ax, "a", "upper right")
    ax = axes[0][1]
    s = W[:, 1] + W[:, 2]
    ax.hist(s, bins=60, density=True, color="#9ec5f4", ec="white")
    ax.set_xlabel(r"$\beta_l+\beta_r$")
    common.panel_label(ax, "b", "upper left")
    fig.tight_layout()
    savefig(fig, CH, "fig11-24", out)


def fig_11_S1(out=None):
    """Supplementary: lasso against elastic net for two identical features (the grouping effect)."""
    rng = np.random.default_rng(0)
    n = 60
    z = rng.standard_normal(n)
    X = np.column_stack([z, z, rng.standard_normal(n), rng.standard_normal(n)])
    X = (X - X.mean(0))
    y = 3 * z + 0.5 * rng.standard_normal(n)
    y -= y.mean()
    lmax = np.abs(X.T @ y).max()
    lams = np.linspace(lmax, 1.0, 40)
    fig, axes = common.panel_grid(1, 2, size=(3.6, 2.8))
    for ax, ttl, lab in zip(axes[0], ("lasso", "elastic net, lam2 = 20"), "ab"):
        W = []
        w = np.zeros(4)
        for l in lams:
            w = lasso_cd(X, y, l / 2 if lab == "a" else l / 2, w0=w, l2=0.0 if lab == "a" else 20.0 / 1.0)
            W.append(w.copy())
        W = np.array(W)
        for j, (c, s) in enumerate(((RED, "-"), (BLUE, "--"), (GREY, ":"), (GREY, ":"))):
            ax.plot(lams, W[:, j], color=c, ls=s, lw=1.6, label=r"$w_%d$" % (j + 1))
        ax.set_title(ttl, fontsize=9.5)
        ax.set_xlabel(r"$\lambda$")
        ax.invert_xaxis()
        ax.legend(frameon=False, fontsize=7.5)
    axes[0][0].set_ylabel("coefficient")
    fig.tight_layout()
    savefig(fig, CH, "fig11-S1", out)


def fig_11_S2(out=None):
    """Supplementary: the ridge shrinkage factors s_j^2/(s_j^2+lambda) of the prostate data and dof(lambda)."""
    P = prostate_paths()
    s = np.linalg.svd(P["Xc"], compute_uv=False)
    lam = np.logspace(-2, 3, 300)
    fig, axes = common.panel_grid(1, 2, size=(3.8, 2.8))
    ax = axes[0][0]
    for j, sj in enumerate(s):
        ax.semilogx(lam, sj ** 2 / (sj ** 2 + lam), label=r"$s_{%d}^2=%.1f$" % (j + 1, sj ** 2))
    ax.set_xlabel(r"$\lambda$")
    ax.set_ylabel(r"$s_j^2/(s_j^2+\lambda)$")
    ax.legend(frameon=False, fontsize=6.5, ncol=2)
    ax = axes[0][1]
    ax.semilogx(lam, [ridge_dof(P["Xc"], l) for l in lam], color=BLUE)
    ax.set_xlabel(r"$\lambda$")
    ax.set_ylabel(r"$\mathrm{dof}(\lambda)$")
    fig.tight_layout()
    savefig(fig, CH, "fig11-S2", out)


FIGURES = {
    "11.1": fig_11_1, "11.2": fig_11_2, "11.3": fig_11_3, "11.4": fig_11_4, "11.5": fig_11_5, "11.6": fig_11_6,
    "11.7": fig_11_7, "11.8": fig_11_8, "11.9": fig_11_9, "11.10": fig_11_10, "11.11": fig_11_11,
    "11.12": fig_11_12, "11.13": fig_11_13, "11.14": fig_11_14, "11.15": fig_11_15, "11.16": fig_11_16,
    "11.17": fig_11_17, "11.18": fig_11_18, "11.19": fig_11_19, "11.20": fig_11_20, "11.21": fig_11_21,
    "11.22": fig_11_22, "11.23": fig_11_23, "11.24": fig_11_24, "11.S1": fig_11_S1, "11.S2": fig_11_S2,
}


# =========================================================================== demo data
def _r(a, nd=5):
    return np.round(np.asarray(a, dtype=float), nd).tolist()


def export_json():
    """Data for the browser demonstrations, with the reference numbers the pages must reproduce."""
    os.makedirs(DATA_OUT, exist_ok=True)
    # 1. prostate paths
    P = prostate_paths()
    names, X, y, tr = P["names"], P["X"], P["y"], P["tr"]
    Xt, yt, Xs, ys = X[tr], y[tr], X[~tr], y[~tr]
    ref = {}
    lam_l = [float(v) for v in np.linspace(0.0, float(P["lams"][0]), 25)]
    ref["lasso_lams"] = _r(lam_l, 5)
    ref["lasso_w"] = _r([path_at(P["lams"], P["W"], l) for l in lam_l], 5)
    lam_r = [0.01, 1.0, 10.0, 100.0]
    ref["ridge_lams"] = lam_r
    ref["ridge_w"] = _r([np.linalg.solve(P["Xc"].T @ P["Xc"] + l * np.eye(8), P["Xc"].T @ P["yc"]) for l in lam_r], 5)
    enl = [(5.0, 5.0), (10.0, 20.0)]
    ref["enet"] = dict(pairs=enl, w=_r([elastic_net_cd(P["Xc"], P["yc"], a, b) for a, b in enl], 5))
    d = dict(names=names, Xtrain=_r(Xt, 5), ytrain=_r(yt, 5), Xtest=_r(Xs, 5), ytest=_r(ys, 5),
             note="Prostate cancer data (Stamey et al. 1989); predictors standardised with the 67 training cases.",
             ref=dict(ref, ols=_r(P["wols"], 5), critical_lams=_r(P["lams"], 5), critical_w=_r(P["W"], 5)))
    with open(os.path.join(DATA_OUT, "ch11-prostate.json"), "w") as f:
        json.dump(d, f, separators=(",", ":"))
    # 2. geometry demo: reference numbers for a fixed quadratic and the penalty families
    A = np.array([[2.0, 1.2], [1.2, 1.0]])
    wml = np.array([2.0, 1.0])
    rows = []
    for lam in (0.5, 1.5, 3.0):
        wr = np.linalg.solve(A + lam * np.eye(2), A @ wml)
        wl = lasso_cd_quad(A, A @ wml, lam)
        rows.append(dict(lam=lam, ridge=_r(wr), lasso=_r(wl)))
    d = dict(A=A.tolist(), wml=wml.tolist(), ref=rows)
    with open(os.path.join(DATA_OUT, "ch11-geometry.json"), "w") as f:
        json.dump(d, f, separators=(",", ":"))
    # 3. Bayesian demo: the book's data law and reference posteriors
    x, yb = bayes_data()
    ref = []
    for n in (0, 1, 2, 5, 100):
        mn, Sn = posterior(poly_feats(x[:n], 1), yb[:n], BAYES_SIGMA ** 2, np.zeros(2), np.eye(2) / BAYES_ALPHA)
        ref.append(dict(n=n, mean=_r(mn), cov=_r(Sn)))
    d = dict(x=_r(x, 5), y=_r(yb, 5), truth=BAYES_TRUE.tolist(), sigma=BAYES_SIGMA, alpha=BAYES_ALPHA, ref=ref)
    with open(os.path.join(DATA_OUT, "ch11-bayes.json"), "w") as f:
        json.dump(d, f, separators=(",", ":"))
    # 4. robust regression
    xr, yr, oi = robust_data()
    F = robust_fits(xr, yr)
    d = dict(x=_r(xr, 5), y=_r(yr, 5), outliers=[int(i) for i in oi],
             ref=dict(ls=_r(F["ls"]), laplace=_r(F["laplace"]), huber=_r(F["huber"]), student=_r(F["student"]),
                      student_s2=float(F["student_s2"])))
    with open(os.path.join(DATA_OUT, "ch11-robust.json"), "w") as f:
        json.dump(d, f, separators=(",", ":"))
    print("wrote ch11-*.json")


def lasso_cd_quad(A, b, lam, iters=5000):
    """Minimise 0.5 w'Aw - b'w + lam |w|_1 by coordinate descent (the quadratic form of the lasso; A = X'X, b = X'y)."""
    w = np.zeros(len(b))
    for _ in range(iters):
        for j in range(len(b)):
            c = b[j] - A[j] @ w + A[j, j] * w[j]
            w[j] = soft_threshold(c, lam) / A[j, j]
    return w


if __name__ == "__main__":
    if "--json" in sys.argv:
        export_json()
    else:
        common.run(FIGURES, CH)
        if "--fig" not in sys.argv and "--list" not in sys.argv:
            export_json()
