"""James et al. (2021, 2023), Chapter 7: Moving Beyond Linearity.

Reproduces the figures of Chapter 7 of G. James, D. Witten, T. Hastie and R. Tibshirani, An Introduction
to Statistical Learning with Applications in R, 2nd edition (Springer, 2021), pp. 289-326 (the same
figures appear in the Python edition of 2023, with J. Taylor), written from scratch with numpy, scipy,
statsmodels and matplotlib. The bases and smoothers come from ch07_lab.py (poly_basis, bs_basis,
ns_basis, SmoothSpline, loess, gam_fit); this file adds:

* fit_with_se: least squares on a basis with the pointwise standard errors sqrt(l0' C l0) of Section 7.1;
* logistic_with_se: logistic regression on a basis, with bands made on the logit scale;
* truncated_power: the bases of Figure 7.3 (piecewise, continuous, cubic and linear splines);
* cv_mse: K-fold cross-validation with the folds fixed by row number (row i is in fold i mod K);
* additive_fit: the penalised least-squares (Gaussian) or penalised IRLS (logistic) solution of an
  additive model with smoothing-spline terms, solved directly (all terms at once) so that the
  pointwise standard errors of every term are available; it equals the backfitting fixed point.

Figures reproduced: 7.1-7.14 (all of them; Figure 7.9 uses simulated data, as in the book).
Run `python3 ch07_moving_beyond_linearity.py --list`, or `--fig 7.8`, or `--fig demos` to write the data
of the three demonstrations to ../data/ch07-*.json and print the numbers quoted in the notes.

Settings chosen where the book gives none:
* Figures 7.3 and 7.4: a random subset of 100 men (numpy default_rng(7)); knot at age 50 in 7.3,
  knots at ages 25, 40 and 60 in 7.4 (the boundary knots of the natural spline are the subset's range).
* Figure 7.6: tenfold cross-validation with row i in fold (i mod 10). For the cubic spline,
  df = 1 and 2 are the polynomials of degree 1 and 2 (a cubic spline needs at least 3 df).
* Figure 7.8: R's knot subset (52 knots at the 61 distinct ages), as in smooth.spline(); LOOCV by the
  shortcut formula over a fine grid of lambda.
* Figure 7.9: x ~ U(0, 1) (100 points), y = sin(4 x) + N(0, 0.3^2), numpy default_rng(4); span 0.3,
  tricube weights, target points 0.05 and 0.45.
* Figure 7.10: local LINEAR fits with spans 0.2 and 0.7, df = trace of the smoother matrix
  (the book's 16.4 and 5.3 are R's 'enp' of local QUADRATIC fits; see the notes).
* Figures 7.11-7.14: terms centred to mean zero over the data; bands are +/- 2 pointwise standard
  errors from the exact linear operator of the fit (the penalised least-squares sandwich for the
  logistic GAMs). In the logistic GAM of Figure 7.13 the "< HS Grad" effect has no finite maximum
  (no high earners in that group); the fit is stopped by the same rule as R's gam() (relative change in
  deviance below 1e-7), so its value and huge standard error depend on that rule.
"""
import json
import os

import numpy as np
import pandas as pd

import common
from common import BLUE, GREEN, GREY, ORANGE, RED, savefig
from ch07_lab import (SmoothSpline, bs_basis, gam_fit, loess, ns_basis, poly_basis,
                      pointwise_se, _bspline_design)

HERE = os.path.dirname(os.path.abspath(__file__))
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
DARK_BLUE = "#1f3fbf"


def wage_data():
    W = common.isl_data("Wage")
    return W, W["age"].to_numpy(float), W["wage"].to_numpy(float)


AGE_GRID = np.linspace(18, 80, 125)


# ======================================================================== helpers
def fit_with_se(Xtr, y, Xnew):
    """Least squares on the columns of Xtr (intercept included); fitted values and pointwise SEs at Xnew."""
    beta, *_ = np.linalg.lstsq(Xtr, y, rcond=None)
    r = y - Xtr @ beta
    n, p = Xtr.shape
    sigma2 = r @ r / (n - p)
    C = sigma2 * np.linalg.pinv(Xtr.T @ Xtr)
    return Xnew @ beta, pointwise_se(Xnew, C), beta, r @ r


def logistic_with_se(Xtr, y, Xnew, maxit=100):
    """Logistic regression by IRLS; probabilities at Xnew and the band from +/- 2 SE on the logit scale."""
    beta = np.zeros(Xtr.shape[1])
    for _ in range(maxit):
        eta = Xtr @ beta
        mu = 1 / (1 + np.exp(-np.clip(eta, -700, 700)))
        w = mu * (1 - mu)
        z = eta + (y - mu) / w
        new = np.linalg.lstsq(Xtr * np.sqrt(w)[:, None], z * np.sqrt(w), rcond=None)[0]
        if np.max(np.abs(new - beta)) < 1e-12 * (1 + np.max(np.abs(beta))):
            beta = new
            break
        beta = new
    mu = 1 / (1 + np.exp(-(Xtr @ beta)))
    C = np.linalg.pinv(Xtr.T @ ((mu * (1 - mu))[:, None] * Xtr))
    eta0 = Xnew @ beta
    se = pointwise_se(Xnew, C)
    expit = lambda a: 1 / (1 + np.exp(-a))
    return expit(eta0), expit(eta0 - 2 * se), expit(eta0 + 2 * se), beta


def truncated_power(x, kind, knot=50.0):
    """Design matrices of Figure 7.3 (intercept included)."""
    x = np.asarray(x, float)
    p = lambda e: np.where(x > knot, (x - knot) ** e, 0.0)
    cubic = [np.ones_like(x), x, x ** 2, x ** 3]
    if kind == "piecewise":           # 8 df: a separate cubic on each side
        right = (x > knot).astype(float)
        return np.column_stack(cubic + [c * right for c in cubic])
    if kind == "continuous":          # 7 df: (x-k)_+, (x-k)_+^2, (x-k)_+^3 keep f continuous only
        return np.column_stack(cubic + [p(1), p(2), p(3)])
    if kind == "cubic":               # 5 df: (7.10), one truncated cubic per knot
        return np.column_stack(cubic + [p(3)])
    if kind == "linear":              # 3 df
        return np.column_stack([np.ones_like(x), x, p(1)])
    raise ValueError(kind)


def cv_mse(make_X, x, y, K=10):
    """K-fold CV error; make_X(x_train, x_eval) builds both design matrices from the training x only."""
    fold = np.arange(len(y)) % K
    err = 0.0
    for k in range(K):
        tr, te = fold != k, fold == k
        Xtr, Xte = make_X(x[tr], x[te])
        beta, *_ = np.linalg.lstsq(Xtr, y[tr], rcond=None)
        err += np.sum((y[te] - Xte @ beta) ** 2)
    return err / len(y)


def ns_design(df):
    def make(xtr, xev):
        if df == 1:
            return np.column_stack([np.ones_like(xtr), xtr]), np.column_stack([np.ones_like(xev), xev])
        B, s = ns_basis(xtr, df=df)
        return (np.column_stack([np.ones(len(xtr)), B]),
                np.column_stack([np.ones(len(xev)), ns_basis(xev, s["knots"], boundary=s["boundary"])[0]]))
    return make


def bs_design(df):
    def make(xtr, xev):
        if df < 3:
            pw = lambda v: np.column_stack([v ** k for k in range(df + 1)])
            return pw(xtr), pw(xev)
        B, s = bs_basis(xtr, df=df)
        # the training basis at the held-out x (beyond the boundary the end cubic pieces continue, as in R)
        return (np.column_stack([np.ones(len(xtr)), B]),
                np.column_stack([np.ones(len(xev)), bs_basis(xev, s["knots"], boundary=s["boundary"])[0]]))
    return make


# ======================================================================= additive models, solved directly
def _smooth_block(x, all_knots=False):
    """B-spline design (expanded to all observations) and penalty for a smoothing-spline term."""
    ss = SmoothSpline(x, np.zeros(len(x)), all_knots=all_knots)
    return ss.B[ss.inv], ss.Omega, ss


def additive_fit(y, terms, family="gaussian", eps=1e-7, maxit=60):
    """Penalised least squares / IRLS for alpha + sum_j f_j. terms: list of ("smooth", x, df) or
    ("linear", X). The penalties lam_j are set so that the smoother of term j alone has tr(S) = df + 1
    with the current weights (gam::s() convention). Returns term values with pointwise SEs at the data,
    the deviance, and the per-term pieces needed to evaluate the terms on a grid."""
    n = len(y)
    blocks, pens, info = [np.ones((n, 1))], [np.zeros((1, 1))], []
    for t in terms:
        if t[0] == "smooth":
            B, Om, ss = _smooth_block(t[1])
            blocks.append(B)
            pens.append(Om)
            info.append(("smooth", ss, t[2]))
        else:
            X = np.asarray(t[1], float).reshape(n, -1)
            blocks.append(X)
            pens.append(np.zeros((X.shape[1], X.shape[1])))
            info.append(("linear", X))
    X = np.hstack(blocks)
    sizes = [b.shape[1] for b in blocks]
    starts = np.cumsum([0] + sizes)
    w = np.ones(n)
    eta = np.zeros(n) if family == "gaussian" else np.full(n, np.log(y.mean() / (1 - y.mean())))
    dev_old = np.inf
    for it in range(maxit):
        if family == "binomial":
            mu = 1 / (1 + np.exp(-np.clip(eta, -700, 700)))
            w = np.maximum(mu * (1 - mu), 1e-10)
            z = eta + (y - mu) / w
        else:
            z = y
        P = np.zeros((X.shape[1], X.shape[1]))
        for j, inf in enumerate(info):
            if inf[0] == "smooth":
                ss = inf[1]
                tmp = SmoothSpline(ss.x, np.zeros(n), w=w)
                lam = tmp.lam_for_df(inf[2] + 1)
                m = starts[j + 2] - starts[j + 1]
                # lam * Omega, plus a penalty on the sum of the coefficients: the B-splines sum to 1, so
                # their constant is the intercept's and this only removes that redundancy (Omega 1 = 0)
                P[starts[j + 1]:starts[j + 2], starts[j + 1]:starts[j + 2]] = lam * pens[j + 1] + np.ones((m, m)) * w.mean()
        A = X.T @ (w[:, None] * X) + P
        Ainv = np.linalg.inv(A)
        theta = Ainv @ (X.T @ (w * z))
        eta = X @ theta
        if family == "gaussian":
            dev = np.sum((y - eta) ** 2)
            break
        mu = 1 / (1 + np.exp(-np.clip(eta, -700, 700)))
        dev = -2 * np.sum(np.where(y == 1, np.log(np.clip(mu, 1e-300, 1)), np.log(np.clip(1 - mu, 1e-300, 1))))
        if abs(dev_old - dev) / (dev + 0.1) < eps:
            break
        dev_old = dev
    # covariance of theta: sigma^2 Ainv X'X Ainv (Gaussian), Ainv X'WX Ainv (logistic, unit dispersion)
    XtWX = X.T @ (w[:, None] * X)
    H = X @ Ainv @ (X.T * w)                    # hat matrix of the final (weighted) fit
    df_total = np.trace(H)
    sigma2 = dev / (n - df_total) if family == "gaussian" else 1.0
    Ctheta = sigma2 * Ainv @ XtWX @ Ainv
    out = {"theta": theta, "C": Ctheta, "starts": starts, "info": info, "deviance": dev, "df": df_total,
           "eta": eta, "w": w, "terms": []}
    for j, inf in enumerate(info):
        sl = slice(starts[j + 1], starts[j + 2])
        Xj = X[:, sl]
        cbar = np.average(Xj, axis=0, weights=None)
        out["terms"].append({"slice": sl, "mean": cbar})
    return out


def term_curve(fit, j, Xj_new):
    """Centred term j evaluated on new rows of its block, with pointwise SEs."""
    t = fit["terms"][j]
    D = Xj_new - t["mean"]
    th = fit["theta"][t["slice"]]
    C = fit["C"][t["slice"], t["slice"]]
    return D @ th, pointwise_se(D, C)


def smooth_rows(fit, j, xnew):
    ss = fit["info"][j][1]
    xs = (np.asarray(xnew, float) - ss.lo) / ss.range
    return _bspline_design(np.clip(xs, 0, 1), ss.t)


# ======================================================================== figures
def _scatter(ax, x, y, s=5):
    ax.scatter(x, y, s=s, facecolors="none", edgecolors="0.65", linewidths=0.5)


def _rug(ax, x, high, top=0.2, rng=None):
    rng = rng or np.random.default_rng(1)
    jit = x + rng.uniform(-0.3, 0.3, len(x))
    ax.plot(jit[high], np.full(high.sum(), top * 0.99), "|", color="0.5", ms=6, mew=0.4)
    ax.plot(jit[~high], np.full((~high).sum(), top * 0.01), "|", color="0.5", ms=6, mew=0.4)


def _two_panel(title_left, fitX, y, high, age, colour=BLUE, knots=None):
    """Left: least squares with 2 SE bands; right: logistic regression for wage > 250 with bands."""
    Xtr, Xnew = fitX
    fig, ax = common.panel_grid(1, 2, size=(4.1, 3.6))
    ax = ax[0]
    f, se, _, _ = fit_with_se(Xtr, y, Xnew)
    _scatter(ax[0], age, y)
    ax[0].plot(AGE_GRID, f, color=colour, lw=2)
    ax[0].plot(AGE_GRID, f - 2 * se, "--", color=colour, lw=1)
    ax[0].plot(AGE_GRID, f + 2 * se, "--", color=colour, lw=1)
    ax[0].set(xlabel="Age", ylabel="Wage", ylim=(20, 330))
    p, lo, hi, _ = logistic_with_se(Xtr, high.astype(float), Xnew)
    _rug(ax[1], age, high)
    ax[1].plot(AGE_GRID, p, color=colour, lw=2)
    ax[1].plot(AGE_GRID, lo, "--", color=colour, lw=1)
    ax[1].plot(AGE_GRID, np.minimum(hi, 0.3), "--", color=colour, lw=1)
    ax[1].set(xlabel="Age", ylabel="Pr(Wage > 250 | Age)", ylim=(0, 0.2))
    if knots is not None:
        for a in ax:
            for k in knots:
                a.axvline(k, color="0.4", ls=":", lw=1)
    fig.suptitle(title_left, fontsize=11)
    fig.tight_layout()
    return fig, (f, se, p, lo, hi)


def fig_7_1(out=None):
    """Degree-4 polynomial for wage and for Pr(wage > 250), with 2 SE bands."""
    W, age, y = wage_data()
    P, pc = poly_basis(age, 4)
    Xtr = np.column_stack([np.ones(len(age)), P])
    Xnew = np.column_stack([np.ones(len(AGE_GRID)), poly_basis(AGE_GRID, 4, pc)[0]])
    fig, _ = _two_panel("Degree-4 Polynomial", (Xtr, Xnew), y, y > 250, age)
    savefig(fig, 7, "fig7-1", out)


def _cut_design(x, breaks):
    idx = np.clip(np.searchsorted(breaks, x, side="left") - 1, 0, len(breaks) - 2)
    D = np.zeros((len(x), len(breaks) - 1))
    D[np.arange(len(x)), idx] = 1
    return D


def fig_7_2(out=None):
    """Step functions (four equal-width age bins, as R's cut(age, 4))."""
    W, age, y = wage_data()
    r = age.max() - age.min()
    br = np.linspace(age.min(), age.max(), 5)
    br[0] -= r / 1000
    br[-1] += r / 1000
    Xtr = _cut_design(age, br)
    Xnew = _cut_design(AGE_GRID, br)
    fig, _ = _two_panel("Piecewise Constant", (Xtr, Xnew), y, y > 250, age, colour=GREEN)
    savefig(fig, 7, "fig7-2", out)


def wage_subset(n=100, seed=7):
    W, age, y = wage_data()
    idx = np.sort(np.random.default_rng(seed).choice(len(y), n, replace=False))
    return age[idx], y[idx]


def fig_7_3(out=None):
    """Piecewise cubic, continuous piecewise cubic, cubic spline and linear spline with a knot at 50."""
    x, y = wage_subset()
    grid = np.linspace(x.min(), x.max(), 400)
    fig, ax = common.panel_grid(2, 2, size=(3.9, 3.2))
    specs = [("piecewise", "Piecewise Cubic", BLUE), ("continuous", "Continuous Piecewise Cubic", GREEN),
             ("cubic", "Cubic Spline", RED), ("linear", "Linear Spline", "#8b1a1a")]
    for a, (kind, title, col) in zip(ax.ravel(), specs):
        X = truncated_power(x, kind)
        beta, *_ = np.linalg.lstsq(X, y, rcond=None)
        G = truncated_power(grid, kind)
        f = G @ beta
        _scatter(a, x, y, s=9)
        if kind == "piecewise":
            left = grid <= 50
            a.plot(grid[left], f[left], color=col, lw=1.8)
            a.plot(grid[~left], f[~left], color=col, lw=1.8)
        else:
            a.plot(grid, f, color=col, lw=1.8)
        a.axvline(50, color="0.5", ls=":", lw=1)
        a.set(title=title, xlabel="Age", ylabel="Wage", ylim=(30, 290))
    fig.tight_layout()
    savefig(fig, 7, "fig7-3", out)


def fig_7_4(out=None):
    """Cubic spline and natural cubic spline with knots at 25, 40, 60 on the subset, 2 SE bands."""
    x, y = wage_subset()
    grid = np.linspace(x.min(), x.max(), 300)
    knots = [25, 40, 60]
    Bc, sc = bs_basis(x, knots=knots)
    Nn, sn = ns_basis(x, knots=knots)
    one = lambda v: np.ones((len(v), 1))
    Xc = np.hstack([one(x), Bc])
    Gc = np.hstack([one(grid), bs_basis(grid, knots, boundary=sc["boundary"])[0]])
    Xn = np.hstack([one(x), Nn])
    Gn = np.hstack([one(grid), ns_basis(grid, knots, boundary=sn["boundary"])[0]])
    fig, ax = common.panel_grid(1, 1, size=(5.6, 4.0))
    ax = ax[0, 0]
    _scatter(ax, x, y, s=10)
    for X, G, col, lab in [(Xc, Gc, BLUE, "Cubic Spline"), (Xn, Gn, RED, "Natural Cubic Spline")]:
        f, se, _, _ = fit_with_se(X, y, G)
        ax.plot(grid, f, color=col, lw=2, label=lab)
        ax.plot(grid, f - 2 * se, "--", color=col, lw=1)
        ax.plot(grid, f + 2 * se, "--", color=col, lw=1)
    for k in knots:
        ax.axvline(k, color="0.4", ls=":", lw=1)
    ax.set(xlabel="Age", ylabel="Wage", ylim=(30, 290))
    ax.legend(loc="upper right", fontsize=8)
    savefig(fig, 7, "fig7-4", out)


def fig_7_5(out=None):
    """Natural cubic spline with 4 df (knots at the quartiles of age): wage and Pr(wage > 250)."""
    W, age, y = wage_data()
    N, s = ns_basis(age, df=4)
    Xtr = np.column_stack([np.ones(len(age)), N])
    Xnew = np.column_stack([np.ones(len(AGE_GRID)), ns_basis(AGE_GRID, s["knots"], boundary=s["boundary"])[0]])
    fig, _ = _two_panel("Natural Cubic Spline", (Xtr, Xnew), y, y > 250, age, colour=RED, knots=s["knots"])
    savefig(fig, 7, "fig7-5", out)


def cv_curves():
    W, age, y = wage_data()
    dfs = np.arange(1, 11)
    ns_cv = np.array([cv_mse(ns_design(d), age, y) for d in dfs])
    bs_cv = np.array([cv_mse(bs_design(d), age, y) for d in dfs])
    return dfs, ns_cv, bs_cv


def fig_7_6(out=None):
    """Tenfold CV error against df for natural cubic splines and cubic splines."""
    dfs, ns_cv, bs_cv = cv_curves()
    fig, ax = common.panel_grid(1, 2, size=(4.0, 3.3))
    for a, v, col, lab in [(ax[0, 0], ns_cv, RED, "Natural Spline"), (ax[0, 1], bs_cv, BLUE, "Cubic Spline")]:
        a.plot(dfs, v, "o-", color=col, ms=4, lw=1.2)
        a.set(xlabel="Degrees of Freedom of " + lab, ylabel="Mean Squared Error", ylim=(1585, 1685))
    fig.tight_layout()
    savefig(fig, 7, "fig7-6", out)


def fig_7_7(out=None):
    """Natural cubic spline with 15 df against a degree-15 polynomial."""
    W, age, y = wage_data()
    N, s = ns_basis(age, df=15)
    fn, *_ = fit_with_se(np.column_stack([np.ones(len(age)), N]), y,
                         np.column_stack([np.ones(len(AGE_GRID)), ns_basis(AGE_GRID, s["knots"], boundary=s["boundary"])[0]]))
    P, pc = poly_basis(age, 15)
    fp, *_ = fit_with_se(np.column_stack([np.ones(len(age)), P]), y,
                         np.column_stack([np.ones(len(AGE_GRID)), poly_basis(AGE_GRID, 15, pc)[0]]))
    fig, ax = common.panel_grid(1, 1, size=(5.6, 4.0))
    ax = ax[0, 0]
    _scatter(ax, age, y)
    ax.plot(AGE_GRID, fn, color=RED, lw=2, label="Natural Cubic Spline")
    ax.plot(AGE_GRID, fp, color=BLUE, lw=2, label="Polynomial")
    ax.set(xlabel="Age", ylabel="Wage", ylim=(20, 330))
    ax.legend(loc="upper right", fontsize=8)
    savefig(fig, 7, "fig7-7", out)


def smoothing_spline_numbers():
    W, age, y = wage_data()
    ss = SmoothSpline(age, y)
    lam16 = ss.lam_for_df(16)
    lamcv = ss.lam_by_cv()
    return ss, lam16, lamcv


def fig_7_8(out=None):
    """Smoothing splines with 16 df and with lambda chosen by LOOCV."""
    W, age, y = wage_data()
    ss, lam16, lamcv = smoothing_spline_numbers()
    fig, ax = common.panel_grid(1, 1, size=(5.6, 4.0))
    ax = ax[0, 0]
    _scatter(ax, age, y)
    ax.plot(AGE_GRID, ss.predict(lam16, AGE_GRID), color=RED, lw=2, label="16 Degrees of Freedom")
    ax.plot(AGE_GRID, ss.predict(lamcv, AGE_GRID), color=BLUE, lw=2, label="%.1f Degrees of Freedom (LOOCV)" % ss.df(lamcv))
    ax.set(xlabel="Age", ylabel="Wage", ylim=(0, 330), title="Smoothing Spline")
    ax.legend(loc="upper right", fontsize=8)
    savefig(fig, 7, "fig7-8", out)


def fig_7_9(out=None):
    """Local linear regression on simulated data, at a target near 0.05 and one near 0.45."""
    rng = np.random.default_rng(4)
    x = np.sort(rng.uniform(0, 1, 100))
    y = np.sin(4 * x) + rng.normal(0, 0.3, 100)
    grid = np.linspace(0, 1, 300)
    span = 0.3
    fhat = loess(x, y, grid, span, degree=1)
    fig, ax = common.panel_grid(1, 2, size=(3.9, 3.4))
    for a, x0 in zip(ax[0], (0.05, 0.45)):
        d = np.abs(x - x0)
        q = int(np.floor(span * len(x)))
        h = np.sort(d)[q - 1]
        k = np.clip(1 - (d / h) ** 3, 0, None) ** 3
        inn = k > 0
        tt = np.linspace(x0 - h, x0 + h, 200)
        bell = np.clip(1 - (np.abs(tt - x0) / h) ** 3, 0, None) ** 3
        a.fill_between(tt, -0.0, bell, color="#e3e35a", alpha=0.75, lw=0)
        a.scatter(x[~inn], y[~inn], s=16, facecolors="none", edgecolors="#7f9fbf", linewidths=0.8)
        a.scatter(x[inn], y[inn], s=16, facecolors="none", edgecolors="#c8641e", linewidths=1.0)
        a.plot(grid, np.sin(4 * grid), color="#1e9fdf", lw=1.6)
        a.plot(grid, fhat, color="#e8a33c", lw=1.6)
        X = np.column_stack([np.ones(len(x)), x])
        sw = np.sqrt(k)
        b = np.linalg.lstsq(X * sw[:, None], y * sw, rcond=None)[0]
        seg = np.linspace(max(x0 - h, 0), min(x0 + h, 1), 2)
        a.plot(seg, b[0] + b[1] * seg, color="#d2541e", lw=1.6)
        a.plot([x0, x0], [-1.1, b[0] + b[1] * x0], color="#d2541e", lw=1)
        a.plot([x0], [b[0] + b[1] * x0], "o", color="#d2541e", ms=6)
        a.set(xlim=(-0.02, 1.02), ylim=(-1.1, 1.65))
    fig.suptitle("Local Regression", fontsize=11)
    fig.tight_layout()
    savefig(fig, 7, "fig7-9", out)


def loess_trace(x, span, degree):
    """tr(S) and tr(S'S) of the local polynomial smoother at the data points."""
    n = len(x)
    q = int(np.floor(span * n))
    ux, inv = np.unique(x, return_inverse=True)
    rows = np.zeros((len(ux), n))
    for i, x0 in enumerate(ux):
        d = np.abs(x - x0)
        h = np.partition(d, q - 1)[q - 1]
        k = np.clip(1 - (d / h) ** 3, 0, None) ** 3
        X = np.vander(x - x0, degree + 1, increasing=True)
        A = np.linalg.solve(X.T @ (k[:, None] * X), (X * k[:, None]).T)
        rows[i] = A[0]
    S = rows[inv]
    return np.trace(S), np.sum(S * S)


def fig_7_10(out=None):
    """Local linear regression with spans 0.2 and 0.7."""
    W, age, y = wage_data()
    fig, ax = common.panel_grid(1, 1, size=(5.6, 4.0))
    ax = ax[0, 0]
    _scatter(ax, age, y)
    for span, col in ((0.2, RED), (0.7, BLUE)):
        f = loess(age, y, AGE_GRID, span, degree=1)
        tr, _ = loess_trace(age, span, 1)
        ax.plot(AGE_GRID, f, color=col, lw=2, label="Span is %.1f (%.1f Degrees of Freedom)" % (span, tr))
    ax.set(xlabel="Age", ylabel="Wage", ylim=(0, 330), title="Local Linear Regression")
    ax.legend(loc="upper right", fontsize=8)
    savefig(fig, 7, "fig7-10", out)


EDU_SHORT = ["<HS", "HS", "<Coll", "Coll", ">Coll"]


def _gam_terms_figure(curves, edu_levels, edu_vals, edu_se, colour, name, ylims=None, edu_ylim=None):
    fig, ax = common.panel_grid(1, 3, size=(3.3, 3.1))
    ax = ax[0]
    for a, (xg, f, se, lab, rug) in zip(ax[:2], curves):
        a.plot(xg, f, color=colour, lw=2)
        a.plot(xg, f - 2 * se, "--", color=colour, lw=0.9)
        a.plot(xg, f + 2 * se, "--", color=colour, lw=0.9)
        yl = a.get_ylim() if ylims is None else ylims[lab]
        ru = np.unique(rug)
        a.plot(ru, np.full(len(ru), yl[0]), "|", color="k", ms=7, mew=0.5)
        a.set(xlabel=lab, ylabel="f(%s)" % lab, ylim=yl)
    a = ax[2]
    xs = np.arange(len(edu_levels))
    for i in xs:
        a.plot([i - 0.3, i + 0.3], [edu_vals[i]] * 2, color=colour, lw=2)
        a.plot([i - 0.15, i + 0.15], [edu_vals[i] - 2 * edu_se[i]] * 2, color=colour, lw=0.9, ls="--")
        a.plot([i - 0.15, i + 0.15], [edu_vals[i] + 2 * edu_se[i]] * 2, color=colour, lw=0.9, ls="--")
        a.plot([i, i], [edu_vals[i] - 2 * edu_se[i], edu_vals[i] + 2 * edu_se[i]], color=colour, lw=0.6, ls=":")
    a.set_xticks(xs, edu_levels, fontsize=8)
    a.set(xlabel="education", ylabel="f(education)", xlim=(-0.6, len(xs) - 0.4))
    if edu_ylim is not None:
        a.set_ylim(edu_ylim)
    fig.tight_layout()
    return fig


def _edu_dummies(edu_codes, levels):
    return np.column_stack([(edu_codes == k).astype(float) for k in levels[1:]])


def gam_ns_terms():
    """Model (7.16) by least squares: ns(year, 4) + ns(age, 5) + education (Figure 7.11)."""
    W, age, y = wage_data()
    year = W["year"].to_numpy(float)
    codes = pd.Categorical(W["education"]).codes
    Ny, sy = ns_basis(year, df=4)
    Na, sa = ns_basis(age, df=5)
    E = _edu_dummies(codes, range(5))
    X = np.column_stack([np.ones(len(y)), Ny, Na, E])
    beta, *_ = np.linalg.lstsq(X, y, rcond=None)
    r = y - X @ beta
    C = (r @ r / (len(y) - X.shape[1])) * np.linalg.inv(X.T @ X)
    out = {}
    blocks = {"year": (slice(1, 5), Ny, lambda g: ns_basis(g, sy["knots"], boundary=sy["boundary"])[0]),
              "age": (slice(5, 10), Na, lambda g: ns_basis(g, sa["knots"], boundary=sa["boundary"])[0]),
              "education": (slice(10, 14), E, lambda g: _edu_dummies(np.asarray(g), range(5)))}
    grids = {"year": np.linspace(2003, 2009, 61), "age": AGE_GRID, "education": np.arange(5)}
    for name, (sl, Bdat, Bfun) in blocks.items():
        D = Bfun(grids[name]) - Bdat.mean(0)
        out[name] = (grids[name], D @ beta[sl], pointwise_se(D, C[sl, sl]))
    return out, r @ r


def fig_7_11(out=None):
    """GAM with natural splines for year (4 df) and age (5 df) and a step function for education."""
    W, age, y = wage_data()
    t, _ = gam_ns_terms()
    yl = {"year": (-30, 30), "age": (-50, 20)}
    fig = _gam_terms_figure([(t["year"][0], t["year"][1], t["year"][2], "year", W["year"].to_numpy(float) + 0.0),
                             (t["age"][0], t["age"][1], t["age"][2], "age", age)],
                            EDU_SHORT, t["education"][1], t["education"][2], RED, "fig7-11", ylims=yl, edu_ylim=(-35, 45))
    savefig(fig, 7, "fig7-11", out)


def gam_ss(y, year, age, codes, levels, family="gaussian", year_linear=False):
    terms = [("linear", year[:, None]) if year_linear else ("smooth", year, 4), ("smooth", age, 5),
             ("linear", _edu_dummies(codes, levels))]
    return additive_fit(y, terms, family=family)


def _ss_term_curves(fit, year, age, codes, levels, year_linear=False):
    yg = np.linspace(2003, 2009, 61)
    if year_linear:
        fy, sey = term_curve(fit, 0, yg[:, None])
    else:
        fy, sey = term_curve(fit, 0, smooth_rows(fit, 0, yg))
    fa, sea = term_curve(fit, 1, smooth_rows(fit, 1, AGE_GRID))
    fe, see = term_curve(fit, 2, _edu_dummies(np.asarray(levels), levels))
    return (yg, fy, sey), (AGE_GRID, fa, sea), (fe, see)


def fig_7_12(out=None):
    """GAM with smoothing splines for year (4 df) and age (5 df), fitted by backfitting."""
    W, age, y = wage_data()
    year = W["year"].to_numpy(float)
    codes = pd.Categorical(W["education"]).codes
    fit = gam_ss(y, year, age, codes, list(range(5)))
    (yg, fy, sey), (ag, fa, sea), (fe, see) = _ss_term_curves(fit, year, age, codes, list(range(5)))
    yl = {"year": (-30, 30), "age": (-50, 20)}
    fig = _gam_terms_figure([(yg, fy, sey, "year", year), (ag, fa, sea, "age", age)], EDU_SHORT, fe, see, BLUE, "fig7-12",
                            ylims=yl, edu_ylim=(-35, 45))
    savefig(fig, 7, "fig7-12", out)


def fig_7_13(out=None):
    """Logistic GAM for wage > 250: linear in year, smoothing spline (5 df) in age, step in education."""
    W, age, y = wage_data()
    year = W["year"].to_numpy(float)
    codes = pd.Categorical(W["education"]).codes
    fit = gam_ss((y > 250).astype(float), year, age, codes, list(range(5)), family="binomial", year_linear=True)
    (yg, fy, sey), (ag, fa, sea), (fe, see) = _ss_term_curves(fit, year, age, codes, list(range(5)), year_linear=True)
    yl = {"year": (-4, 4), "age": (-8, 3)}
    fig = _gam_terms_figure([(yg, fy, sey, "year", year), (ag, fa, sea, "age", age)], EDU_SHORT, fe, see, GREEN, "fig7-13",
                            ylims=yl)
    savefig(fig, 7, "fig7-13", out)


def fig_7_14(out=None):
    """As Figure 7.13 without the men with less than a high-school education."""
    W, age, y = wage_data()
    keep = W["education"].to_numpy() != "1. < HS Grad"
    year = W["year"].to_numpy(float)[keep]
    codes = pd.Categorical(W["education"]).codes[keep]
    fit = gam_ss((y[keep] > 250).astype(float), year, age[keep], codes, [1, 2, 3, 4], family="binomial", year_linear=True)
    (yg, fy, sey), (ag, fa, sea), (fe, see) = _ss_term_curves(fit, year, age[keep], codes, [1, 2, 3, 4], year_linear=True)
    yl = {"year": (-4, 4), "age": (-8, 3)}
    fig = _gam_terms_figure([(yg, fy, sey, "year", year), (ag, fa, sea, "age", age[keep])], EDU_SHORT[1:], fe, see, GREEN,
                            "fig7-14", ylims=yl, edu_ylim=(-4, 4))
    savefig(fig, 7, "fig7-14", out)


# ======================================================================== demonstrations' data and quoted numbers
def demos(out=None):
    """Write ../data/ch07-*.json for the three demonstrations and print the numbers quoted in the notes."""
    os.makedirs(DATA_OUT, exist_ok=True)
    W, age, y = wage_data()
    year = W["year"].to_numpy(float)
    codes = pd.Categorical(W["education"]).codes
    # 1. the Wage data for the basis-function demonstration, with reference fits
    ref = {}
    P, pc = poly_basis(age, 4)
    f, se, _, rss = fit_with_se(np.column_stack([np.ones(len(age)), P]), y,
                                np.column_stack([np.ones(3), poly_basis(np.array([18.0, 50, 80]), 4, pc)[0]]))
    ref["poly4"] = {"fit": f.tolist(), "se": se.tolist(), "rss": rss, "cv": cv_mse(lambda a, b: (
        np.column_stack([np.ones(len(a)), poly_basis(a, 4)[0]]),
        np.column_stack([np.ones(len(b)), poly_basis(b, 4, poly_basis(a, 4)[1])[0]])), age, y)}
    N, s = ns_basis(age, df=4)
    f, se, _, rss = fit_with_se(np.column_stack([np.ones(len(age)), N]), y,
                                np.column_stack([np.ones(3), ns_basis(np.array([18.0, 50, 80]), s["knots"], boundary=s["boundary"])[0]]))
    ref["ns4"] = {"fit": f.tolist(), "se": se.tolist(), "rss": rss, "cv": cv_mse(ns_design(4), age, y)}
    B, s = bs_basis(age, knots=[25, 40, 60])
    f, se, _, rss = fit_with_se(np.column_stack([np.ones(len(age)), B]), y,
                                np.column_stack([np.ones(3), bs_basis(np.array([18.0, 50, 80]), s["knots"], boundary=s["boundary"])[0]]))
    ref["bs3"] = {"fit": f.tolist(), "se": se.tolist(), "rss": rss}
    dfs, ns_cv, bs_cv = cv_curves()
    ref["cv_ns"] = ns_cv.tolist()
    ref["cv_bs"] = bs_cv.tolist()
    with open(os.path.join(DATA_OUT, "ch07-wage.json"), "w") as fh:
        json.dump({"age": age.astype(int).tolist(), "wage": y.tolist(), "year": year.astype(int).tolist(),
                   "edu": codes.tolist(), "edu_levels": EDU_SHORT, "ref": ref}, fh, separators=(",", ":"))
    print("degree-4 polynomial at ages 18, 50, 80:", np.round(ref["poly4"]["fit"], 2), "SE", np.round(ref["poly4"]["se"], 2),
          "10-fold CV", round(ref["poly4"]["cv"], 2))
    print("ns(df = 4) at ages 18, 50, 80:", np.round(ref["ns4"]["fit"], 2), "SE", np.round(ref["ns4"]["se"], 2), "CV", round(ref["ns4"]["cv"], 2))
    print("bs(knots 25, 40, 60) SE at 18, 50, 80:", np.round(ref["bs3"]["se"], 2))
    print("CV natural spline df 1..10:", np.round(ns_cv, 1))
    print("CV cubic spline   df 1..10:", np.round(bs_cv, 1))

    # 2. smoothing spline, exact (all distinct ages are knots), lambda on the original age scale
    ssa = SmoothSpline(age, y, all_knots=True)
    r3 = ssa.range ** 3
    lams = 10.0 ** np.linspace(-8, 0, 81)           # on the [0, 1] scale
    curve = [{"lam": l * r3, "df": ssa.df(l), "cv": ssa.loocv(l)} for l in lams]
    l16 = ssa.lam_for_df(16)
    lcv = ssa.lam_by_cv()
    ss, lam16, lamcv = smoothing_spline_numbers()
    _, g16, lev16 = ssa.fit(l16)
    gcv = lambda l: np.mean((y - ssa.fit(l)[1][ssa.inv]) ** 2) / (1 - ssa.df(l) / len(y)) ** 2
    lgcv = 10.0 ** __import__("scipy").optimize.minimize_scalar(lambda s: gcv(10.0 ** s), bounds=(-6, -1), method="bounded").x
    # brute-force leave-one-out at df = 16 for a few observations: refit without observation i
    brute = []
    for i in (0, 1, 2, 500, 2999):
        keep = np.ones(len(y), bool)
        keep[i] = False
        wts = keep.astype(float)
        s2 = SmoothSpline(age, y, w=wts, all_knots=True)
        coef = s2.fit(l16)[0]
        pred = (s2.B @ coef)[s2.inv[i]]
        short = (y[i] - g16[ssa.inv[i]]) / (1 - lev16[ssa.inv[i]] / ssa.wbar[ssa.inv[i]])
        brute.append([y[i] - pred, short])
    within = np.bincount(ssa.inv, (y - ssa.ybar[ssa.inv]) ** 2)       # sum of squares about each age's mean
    ssjson = {"ux": ssa.ux.tolist(), "w": ssa.wbar.tolist(), "ybar": ssa.ybar.tolist(), "within": within.tolist(),
              "ref": {"lam16": l16 * r3, "fit16": ssa.predict(l16, [20, 40, 60, 80]).tolist(), "lamcv": lcv * r3,
                      "dfcv": ssa.df(lcv), "cvmin": ssa.loocv(lcv), "fitcv": ssa.predict(lcv, [20, 40, 60, 80]).tolist(),
                      "cv16": ssa.loocv(l16), "dfgcv": ssa.df(lgcv), "curve": curve,
                      "row80_16": None}}
    # equivalent kernel (row of S) at age 80 and at age 40 for df = 16 on the distinct ages
    A = np.linalg.solve(ssa.BtWB + l16 * ssa.Omega, ssa.B.T)
    S = ssa.B @ A * ssa.wbar                          # S_u: fitted means at distinct ages from the means
    ssjson["ref"]["row40_16"] = S[np.searchsorted(ssa.ux, 40)].tolist()
    ssjson["ref"]["row80_16"] = S[-1].tolist()
    with open(os.path.join(DATA_OUT, "ch07-smoothing-spline.json"), "w") as fh:
        json.dump(ssjson, fh, separators=(",", ":"))
    print("smoothing spline (R's knots): df 16 at lambda %.4g; LOOCV lambda %.4g, df %.2f, CV %.2f" % (lam16, lamcv, ss.df(lamcv), ss.loocv(lamcv)))
    print("smoothing spline (all knots): LOOCV df %.3f, CV %.3f; GCV df %.3f; CV at df 16 %.3f" % (ssa.df(lcv), ssa.loocv(lcv), ssa.df(lgcv), ssa.loocv(l16)))
    print("brute-force versus shortcut LOO residuals:", np.round(brute, 6).tolist())

    # 3. GAM backfitting: exact smoothing splines (all distinct values are knots)
    E = _edu_dummies(codes, range(5))
    terms = [{"type": "smooth", "x": year, "df": 4, "all_knots": True}, {"type": "smooth", "x": age, "df": 5, "all_knots": True},
             {"type": "linear", "X": E}]
    m3 = gam_fit(y, terms)
    fit_direct = gam_ss(y, year, age, codes, list(range(5)))
    yr = np.unique(year)
    fy = [m3["f"][0][year == v][0] for v in yr]
    ua = np.unique(age)
    fa = [m3["f"][1][age == v][0] for v in ua]
    fe = [m3["f"][2][codes == k][0] for k in range(5)]
    gam_ref = {"m3": {"alpha": m3["alpha"], "fyear": fy, "fage": fa, "fedu": fe, "rss": m3["deviance"]}}
    for label, tt in [("m2", [{"type": "linear", "X": year[:, None]}, terms[1], terms[2]]), ("m1", [terms[1], terms[2]]),
                      ("age15", [terms[0], {"type": "smooth", "x": age, "df": 15, "all_knots": True}, terms[2]])]:
        gam_ref[label] = {"rss": gam_fit(y, tt)["deviance"]}
    one_sweep = gam_fit(y, terms, maxit=1)
    gam_ref["sweep1_rss"] = one_sweep["deviance"]
    with open(os.path.join(DATA_OUT, "ch07-gam.json"), "w") as fh:
        json.dump({"ref": gam_ref}, fh, separators=(",", ":"))
    print("GAM s(year,4) + s(age,5) + education: RSS backfitting %.2f, direct %.2f, after one sweep %.2f" % (m3["deviance"], fit_direct["deviance"], one_sweep["deviance"]))
    print("  M2 (year linear) %.2f, M1 (no year) %.2f, age df 15 %.2f" % (gam_ref["m2"]["rss"], gam_ref["m1"]["rss"], gam_ref["age15"]["rss"]))
    _, rss_ns = gam_ns_terms()
    print("GAM with natural splines (Figure 7.11): RSS %.1f" % rss_ns)
    for span in (0.2, 0.5, 0.7):
        for deg in (1, 2):
            tr, trss = loess_trace(age, span, deg)
            print("loess span %.1f degree %d: tr(S) = %.2f, tr(S'S) = %.2f" % (span, deg, tr, trss))


FIGURES = {
    "7.1": fig_7_1, "7.2": fig_7_2, "7.3": fig_7_3, "7.4": fig_7_4, "7.5": fig_7_5, "7.6": fig_7_6,
    "7.7": fig_7_7, "7.8": fig_7_8, "7.9": fig_7_9, "7.10": fig_7_10, "7.11": fig_7_11, "7.12": fig_7_12,
    "7.13": fig_7_13, "7.14": fig_7_14, "demos": demos,
}

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