"""Chapter 7 lab: non-linear modelling (Python version).

Course: Applied Statistical Learning in R and Python, following James, Witten, Hastie, Tibshirani and
Taylor (2023), An Introduction to Statistical Learning with Applications in Python, Section 7.8, and
the R lab of James et al. (2021), Section 7.8.

The lab fits the same models as ch07_lab.R on the Wage data, with numpy, pandas, scipy and
statsmodels only. The spline bases, the smoothing spline, local regression and backfitting are
written out below as short functions, so that every step can be read:

    poly_basis       orthogonal polynomials, the same basis as R's poly()
    bs_basis         B-spline basis of a cubic regression spline, as R's splines::bs()
    ns_basis         natural cubic spline basis, as R's splines::ns()
    smooth_spline    penalised regression spline with the knots of R's smooth.spline(); df and LOOCV
    loess            local polynomial regression with tricube weights (R's loess, exact surface)
    gam_fit          backfitting (Gaussian) and local scoring (logistic) for additive models

Run from the code/ folder:  python3 ch07_lab.py
Figures go to ../img/ch07/lab-py-*.svg and the key numbers to cache/ch07_lab_py.csv.
"""
import os

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

import numpy as np
import pandas as pd
import statsmodels.api as sm
from scipy import optimize, stats
from scipy.interpolate import BSpline
from statsmodels.stats.anova import anova_lm

HERE = os.path.dirname(os.path.abspath(__file__))


# ======================================================================== bases
def poly_basis(x, degree, coefs=None):
    """Orthogonal polynomials of degree 1..degree in x (the columns of R's poly(x, degree)).

    The columns are p_1(x), ..., p_d(x) from the three-term recurrence
    p_{k+1}(x) = (x - a_k) p_k(x) - (n_k / n_{k-1}) p_{k-1}(x), scaled to unit length on the
    training data. Pass coefs (returned by the first call) to evaluate the same basis at new x.
    """
    x = np.asarray(x, float)
    if coefs is None:                       # Stieltjes procedure on the training x
        P = [np.ones_like(x)]
        alpha, norm2 = [], [1.0, float(len(x))]
        for k in range(degree):
            a = np.sum(x * P[k] ** 2) / np.sum(P[k] ** 2)
            alpha.append(a)
            nxt = (x - a) * P[k] - (norm2[k + 1] / norm2[k] * P[k - 1] if k > 0 else 0.0)
            P.append(nxt)
            norm2.append(np.sum(nxt ** 2))
        coefs = {"alpha": np.array(alpha), "norm2": np.array(norm2)}
    alpha, norm2 = coefs["alpha"], coefs["norm2"]
    Z = np.ones((len(x), degree + 1))
    Z[:, 1] = x - alpha[0]
    for k in range(1, degree):
        Z[:, k + 1] = (x - alpha[k]) * Z[:, k] - (norm2[k + 1] / norm2[k]) * Z[:, k - 1]
    return Z[:, 1:] / np.sqrt(norm2[2:]), coefs


def _bspline_design(x, t, k=3, deriv=0):
    """Matrix of all B-splines of degree k with knot vector t (and their derivatives) at x."""
    m = len(t) - k - 1
    out = np.empty((len(np.atleast_1d(x)), m))
    for j in range(m):
        c = np.zeros(m)
        c[j] = 1.0
        b = BSpline(t, c, k, extrapolate=True)
        out[:, j] = b.derivative(deriv)(x) if deriv else b(x)
    return out


def _quantile_knots(x, n_inner):
    """n_inner interior knots at equally spaced quantiles of x (R's default, type 7)."""
    return np.quantile(x, np.linspace(0, 1, n_inner + 2)[1:-1])


def bs_basis(x, knots=None, df=None, degree=3, boundary=None):
    """B-spline basis without the intercept column, as R's bs(x, knots, df, degree)."""
    x = np.asarray(x, float)
    if knots is None:
        knots = _quantile_knots(x, df - degree)
    knots = np.asarray(knots, float)
    lo, hi = boundary if boundary is not None else (x.min(), x.max())
    t = np.r_[[lo] * (degree + 1), knots, [hi] * (degree + 1)]
    B = _bspline_design(x, t, degree)
    spec = {"knots": knots, "boundary": (lo, hi), "degree": degree}
    return B[:, 1:], spec


def ns_basis(x, knots=None, df=None, boundary=None):
    """Natural cubic spline basis without the intercept column, as R's ns(x, knots, df).

    Start from the cubic B-splines on the knots and keep the combinations whose second derivative
    is zero at both boundary knots: those are linear beyond the boundary knots.
    """
    x = np.asarray(x, float)
    if knots is None:
        knots = _quantile_knots(x, df - 1)
    knots = np.asarray(knots, float)
    lo, hi = boundary if boundary is not None else (x.min(), x.max())
    t = np.r_[[lo] * 4, knots, [hi] * 4]
    C = _bspline_design(np.array([lo, hi]), t, 3, deriv=2)[:, 1:]     # 2 x m: f''(lo), f''(hi)
    Q, _ = np.linalg.qr(C.T, mode="complete")                          # last m-2 columns span null(C)
    xin = np.clip(x, lo, hi)
    B = _bspline_design(xin, t, 3)[:, 1:]
    if np.any(x != xin):                                               # beyond the boundary: linear
        D1 = _bspline_design(np.array([lo, hi]), t, 3, deriv=1)[:, 1:]
        B = B + np.where(x < lo, x - lo, 0)[:, None] * D1[0] + np.where(x > hi, x - hi, 0)[:, None] * D1[1]
    spec = {"knots": knots, "boundary": (lo, hi)}
    return B @ Q[:, 2:], spec


# ======================================================================== least squares with standard errors
def ols(X, y):
    """Least squares with an intercept column already in X; returns beta, its covariance, sigma^2."""
    beta, *_ = np.linalg.lstsq(X, y, rcond=None)
    resid = y - X @ beta
    n, p = X.shape
    sigma2 = resid @ resid / (n - p)
    C = sigma2 * np.linalg.inv(X.T @ X)
    return beta, C, sigma2


def pointwise_se(L0, C):
    """sqrt(l0' C l0) for every row l0 of L0: the standard error of the fitted value l0' beta."""
    return np.sqrt(np.einsum("ij,jk,ik->i", L0, C, L0))


# ======================================================================== smoothing splines
def _nknots_smspl(n):
    """Number of knots R's smooth.spline() uses for n distinct x values."""
    if n < 50:
        return n
    a1, a2, a3, a4 = np.log2(50), np.log2(100), np.log2(140), np.log2(200)
    if n < 200:
        v = 2 ** (a1 + (a2 - a1) * (n - 50) / 150)
    elif n < 800:
        v = 2 ** (a2 + (a3 - a2) * (n - 200) / 600)
    elif n < 3200:
        v = 2 ** (a3 + (a4 - a3) * (n - 800) / 2400)
    else:
        v = 200 + (n - 3200) ** 0.2
    return int(v)


def _penalty_matrix(t, k=3):
    """Omega_jl = integral of B_j''(u) B_l''(u) du, exact (two Gauss points per knot interval)."""
    brk = np.unique(t)
    g = np.array([-1, 1]) / np.sqrt(3)
    mid, half = (brk[1:] + brk[:-1]) / 2, (brk[1:] - brk[:-1]) / 2
    u = (mid[:, None] + half[:, None] * g).ravel()
    w = np.repeat(half, 2)
    D2 = _bspline_design(u, t, k, deriv=2)
    return D2.T @ (w[:, None] * D2)


class SmoothSpline:
    """Cubic smoothing spline: minimise sum_i w_i (y_i - g(x_i))^2 + lam * integral g''(u)^2 du.

    x is rescaled to [0, 1] (as in R, so lam does not depend on the units of x). Ties in x are
    collapsed to their weighted means with summed weights. all_knots=True puts a knot at every
    distinct x, which gives the exact minimiser over all functions (a natural cubic spline);
    otherwise the knots are R's subset (52 of the 61 distinct ages for the Wage data).
    """

    def __init__(self, x, y, w=None, all_knots=False):
        x, y = np.asarray(x, float), np.asarray(y, float)
        w = np.ones_like(x) if w is None else np.asarray(w, float)
        self.ux, inv = np.unique(x, return_inverse=True)
        self.wbar = np.bincount(inv, w)
        self.ybar = np.bincount(inv, w * y) / self.wbar
        self.x, self.y, self.w, self.inv = x, y, w, inv
        self.lo, self.range = self.ux[0], self.ux[-1] - self.ux[0]
        xs = (self.ux - self.lo) / self.range
        nx = len(xs)
        nk = nx if all_knots else _nknots_smspl(nx)
        idx = np.floor(1.0 + np.arange(nk) * ((nx - 1.0) / (nk - 1.0))).astype(int) - 1
        idx[-1] = nx - 1
        self.t = np.r_[[xs[0]] * 3, xs[idx], [xs[-1]] * 3]
        self.B = _bspline_design(xs, self.t)
        self.Omega = _penalty_matrix(self.t)
        self.BtWB = self.B.T @ (self.wbar[:, None] * self.B)
        self.BtWy = self.B.T @ (self.wbar * self.ybar)

    def fit(self, lam):
        """Coefficients, fitted values at the distinct x, and leverages (diagonal of S on distinct x)."""
        A = self.BtWB + lam * self.Omega
        coef = np.linalg.solve(A, self.BtWy)
        Ainv_Bt = np.linalg.solve(A, self.B.T)
        lev = self.wbar * np.einsum("ij,ji->i", self.B, Ainv_Bt)
        return coef, self.B @ coef, lev

    def df(self, lam):
        """Effective degrees of freedom tr(S_lam) (7.13); between 2 and the number of distinct x."""
        return self.fit(lam)[2].sum()

    def lam_for_df(self, df):
        """The lam with df(lam) = df: df is strictly decreasing in lam, so a root search works."""
        f = lambda s: self.df(10.0 ** s) - df
        lo = -12.0
        while not np.isfinite(f(lo)) or f(lo) < 0:      # very small lam can be numerically singular
            lo += 1.0
        return 10.0 ** optimize.brentq(f, lo, 6, xtol=1e-12)

    def loocv(self, lam):
        """Leave-one-out CV error per observation from one fit: the shortcut formula of Section 7.5.2."""
        _, g, lev = self.fit(lam)
        s_ii = lev / self.wbar                  # diagonal of the n x n smoother matrix, observation by observation
        r = (self.y - g[self.inv]) / (1 - s_ii[self.inv])
        return np.average(r ** 2, weights=self.w)

    def lam_by_cv(self, grid=np.linspace(-8, 2, 201)):
        cv = np.array([self.loocv(10.0 ** s) for s in grid])
        k = int(np.argmin(cv))
        res = optimize.minimize_scalar(lambda s: self.loocv(10.0 ** s), bounds=(grid[max(k - 1, 0)], grid[min(k + 1, len(grid) - 1)]),
                                       method="bounded", options={"xatol": 1e-9})
        return 10.0 ** res.x

    def predict(self, lam, xnew, coef=None):
        """g at new x; beyond the data range the natural spline continues as a straight line."""
        coef = self.fit(lam)[0] if coef is None else coef
        xs = (np.asarray(xnew, float) - self.lo) / self.range
        xin = np.clip(xs, 0, 1)
        g = _bspline_design(xin, self.t) @ coef
        if np.any(xs != xin):
            d1 = _bspline_design(np.array([0.0, 1.0]), self.t, deriv=1) @ coef
            g = g + np.where(xs < 0, xs, 0) * d1[0] + np.where(xs > 1, xs - 1, 0) * d1[1]
        return g


# ======================================================================== local regression
def loess(x, y, xnew, span, degree=2, w=None):
    """Local polynomial regression (Algorithm 7.1 with a local polynomial of the given degree).

    At each target x0: take the q = floor(span * n) nearest x_i, give them tricube weights
    (1 - (d / d_q)^3)^3 where d_q is the distance to the q-th nearest, and fit weighted least squares.
    """
    x, y = np.asarray(x, float), np.asarray(y, float)
    w = np.ones_like(x) if w is None else np.asarray(w, float)
    q = int(np.floor(span * len(x)))
    out = np.empty(len(np.atleast_1d(xnew)))
    for i, x0 in enumerate(np.atleast_1d(xnew)):
        d = np.abs(x - x0)
        h = np.partition(d, q - 1)[q - 1]
        k = w * np.clip(1 - (d / h) ** 3, 0, None) ** 3
        X = np.vander(x - x0, degree + 1, increasing=True)
        sw = np.sqrt(k)
        beta = np.linalg.lstsq(X * sw[:, None], y * sw, rcond=None)[0]
        out[i] = beta[0]                        # the fitted value at x0 is the local intercept
    return out


# ======================================================================== additive models
def _wls_projection(X, w):
    """The weighted least-squares fit on [1, X] as a function: r -> X1 (X1'WX1)^{-1} X1'W r.

    The constant column makes the block reproduce constants, as a smoothing spline does; the fitted
    term is then centred, and the intercept is carried by alpha.
    """
    X = np.column_stack([np.ones(len(X)), X])
    XtW = (X * w[:, None]).T
    M = np.linalg.solve(XtW @ X, XtW)
    return lambda r: X @ (M @ r)


def gam_fit(y, terms, family="gaussian", tol=1e-10, maxit=200):
    """Additive model y ~ alpha + sum_j f_j by backfitting; logistic models by local scoring.

    terms: list of dicts, each either {"type": "linear", "X": matrix} (a parametric block, fitted
    by least squares on the partial residual) or {"type": "smooth", "x": x, "df": df} (a smoothing
    spline with tr(S) = df + 1, the convention of gam::s()). Returns the intercept, the fitted
    term contributions (each centred to weighted mean 0), the linear predictor and the deviance.
    """
    y = np.asarray(y, float)
    n = len(y)
    eta = np.zeros(n)
    if family == "binomial":
        p0 = y.mean()
        eta[:] = np.log(p0 / (1 - p0))
    fs = [np.zeros(n) for _ in terms]
    alpha = eta.mean()
    for outer in range(100):
        if family == "binomial":                # local scoring: working response and weights
            mu = 1 / (1 + np.exp(-eta))
            w = np.maximum(mu * (1 - mu), 1e-10)
            z = eta + (y - mu) / w
        else:
            w, z = np.ones(n), y
        smoothers, makers = [], []
        for term in terms:
            if term["type"] == "linear":
                smoothers.append(_wls_projection(term["X"], w))
                X1 = np.column_stack([np.ones(n), term["X"]])
                makers.append(lambda r, X1=X1: ("linear", np.linalg.lstsq(X1 * np.sqrt(w)[:, None], r * np.sqrt(w), rcond=None)[0]))
            else:
                ss = SmoothSpline(term["x"], np.zeros(n), w=w, all_knots=term.get("all_knots", False))
                lam = ss.lam_for_df(term["df"] + 1)
                A = np.linalg.solve(ss.BtWB + lam * ss.Omega, ss.B.T)
                def smooth(r, ss=ss, A=A):
                    rbar = np.bincount(ss.inv, ss.w * r) / ss.wbar
                    return (ss.B @ (A @ (ss.wbar * rbar)))[ss.inv]
                smoothers.append(smooth)
                makers.append(lambda r, ss=ss, A=A, lam=lam: ("smooth", ss, A @ (ss.wbar * np.bincount(ss.inv, ss.w * r) / ss.wbar), lam))
        alpha = np.average(z - sum(fs), weights=w)
        for it in range(maxit):                  # backfitting (Algorithm in Section 7.7)
            change = 0.0
            for j, S in enumerate(smoothers):
                partial = z - alpha - sum(fs[k] for k in range(len(fs)) if k != j)
                new = S(partial)
                new -= np.average(new, weights=w)
                change = max(change, np.max(np.abs(new - fs[j])))
                fs[j] = new
            alpha = np.average(z - sum(fs), weights=w)
            if change < tol * (1 + np.max(np.abs(z))):
                break
        eta_new = alpha + sum(fs)
        if family == "gaussian":
            eta = eta_new
            break
        conv = np.max(np.abs(eta_new - eta)) < 1e-9
        eta = eta_new
        if conv:
            break
    if family == "gaussian":
        dev = np.sum((y - eta) ** 2)
    else:
        mu = 1 / (1 + np.exp(-eta))
        dev = -2 * np.sum(y * np.log(np.clip(mu, 1e-300, 1)) + (1 - y) * np.log(np.clip(1 - mu, 1e-300, 1)))
    # the fitted term functions, for prediction at new inputs: f_j = (smoother applied to its partial
    # residual) minus its weighted mean
    parts = []
    for j, mk in enumerate(makers):
        partial = z - alpha - sum(fs[k] for k in range(len(fs)) if k != j)
        made = mk(partial)
        shift = np.average(smoothers[j](partial), weights=w)
        parts.append(made + (shift,))
    return {"alpha": alpha, "f": fs, "eta": eta, "deviance": dev, "parts": parts}


def gam_predict(fit, new_terms):
    """Linear predictor at new data; new_terms lists, term by term, the new x (smooth) or X (linear)."""
    eta = fit["alpha"]
    for part, new in zip(fit["parts"], new_terms):
        if part[0] == "linear":
            beta, shift = part[1], part[2]
            eta = eta + np.column_stack([np.ones(len(new)), new]) @ beta - shift
        else:
            ss, coef, lam, shift = part[1], part[2], part[3], part[4]
            eta = eta + ss.predict(lam, new, coef=coef) - shift
    return eta



# ======================================================================== applied exercises (Section 7.9)
def fold_id(n, K=10):
    """Row i (counting from 0) is in fold i mod K: the same folds as the R solutions."""
    return np.arange(n) % K


def cv_mse(design, x, y, K=10):
    """K-fold CV error; design(x_train, x_eval) returns both design matrices built from x_train."""
    fold = fold_id(len(y), K)
    sse = 0.0
    for k in range(K):
        tr, te = fold != k, fold == k
        Xtr, Xte = design(x[tr], x[te])
        beta = np.linalg.lstsq(Xtr, y[tr], rcond=None)[0]
        sse += np.sum((y[te] - Xte @ beta) ** 2)
    return sse / len(y)


def poly_design(d):
    def make(a, b):
        Pa, pc = poly_basis(a, d)
        return np.column_stack([np.ones(len(a)), Pa]), np.column_stack([np.ones(len(b)), poly_basis(b, d, pc)[0]])
    return make


def bs_design(df):
    def make(a, b):
        Ba, spec = bs_basis(a, df=df)
        Bb = bs_basis(b, spec["knots"], boundary=spec["boundary"])[0]
        return np.column_stack([np.ones(len(a)), Ba]), np.column_stack([np.ones(len(b)), Bb])
    return make


def anova_f(dev_small, df_small, dev_big, df_big):
    """F test of a smaller model against a larger one (residual deviances and residual df)."""
    F = (dev_small - dev_big) / (df_small - df_big) / (dev_big / df_big)
    return F, stats.f.sf(F, df_small - df_big, df_big)


def forward_stepwise(X, y, names):
    """Forward stepwise selection by RSS (with an intercept); returns the order and the RSS of each size."""
    n = len(y)
    chosen, rss = [], []
    for _ in range(X.shape[1]):
        best = None
        for j in range(X.shape[1]):
            if j in chosen:
                continue
            Xs = np.column_stack([np.ones(n), X[:, chosen + [j]]])
            r = y - Xs @ np.linalg.lstsq(Xs, y, rcond=None)[0]
            if best is None or r @ r < best[1]:
                best = (j, r @ r)
        chosen.append(best[0])
        rss.append(best[1])
    return [names[j] for j in chosen], np.array(rss)


def exercises(keep):
    import common
    Wage = common.isl_data("Wage")
    y = Wage["wage"].to_numpy()
    age = Wage["age"].to_numpy(float)
    n = len(y)
    edu = pd.get_dummies(pd.Categorical(Wage["education"]), drop_first=True, dtype=float).to_numpy()

    # Exercise 6(a): degree of the polynomial by CV
    cv_poly = np.array([cv_mse(poly_design(d), age, y) for d in range(1, 11)])
    print(np.round(cv_poly, 2), " Exercise 6(a): CV chooses degree", 1 + int(np.argmin(cv_poly)))
    keep("ex6_cv_poly", cv_poly)
    # Exercise 6(b): number of equal-width bins, breaks from the whole range of age
    cv_cut = []
    for k in range(2, 11):
        br = np.linspace(age.min(), age.max(), k + 1)
        br[0] -= 1
        br[-1] += 1
        bins = np.searchsorted(br, age, side="left") - 1        # bins (br[j], br[j+1]], as R's cut()
        D = np.eye(k)[bins]
        cv_cut.append(cv_mse(lambda a, b, D=D: (D[a.astype(int)], D[b.astype(int)]), np.arange(n, dtype=float), y))
    cv_cut = np.array(cv_cut)
    print(np.round(cv_cut, 2), " Exercise 6(b): CV chooses", 2 + int(np.argmin(cv_cut)), "bins")
    keep("ex6_cv_cut", cv_cut)

    # Exercise 7: job class and marital status
    job = (Wage["jobclass"].str.startswith("2")).to_numpy(float)[:, None]
    mar = pd.get_dummies(pd.Categorical(Wage["maritl"]), drop_first=True, dtype=float).to_numpy()
    s_age = {"type": "smooth", "x": age, "df": 5}
    as_linear = lambda M_: {"type": "linear", "X": M_}
    d7 = [gam_fit(y, t)["deviance"] for t in ([s_age, as_linear(edu)], [s_age, as_linear(edu), as_linear(job)], [s_age, as_linear(edu), as_linear(job), as_linear(mar)])]
    r7 = [n - 1 - 5 - 4, n - 1 - 5 - 4 - 1, n - 1 - 5 - 4 - 1 - 4]
    F7 = [((d7[0] - d7[1]) / 1) / (d7[2] / r7[2]), ((d7[1] - d7[2]) / 4) / (d7[2] / r7[2])]   # scale from the largest model, as anova()
    print("Exercise 7: deviances", np.round(d7, 1), " F", np.round(F7, 3))
    keep("ex7_dev", d7); keep("ex7_F", F7)

    # Exercise 8: Auto
    Auto = common.isl_data("Auto", na_values="?").dropna()
    mpg, hp = Auto["mpg"].to_numpy(float), Auto["horsepower"].to_numpy(float)
    cv_auto = np.array([cv_mse(poly_design(d), hp, mpg) for d in range(1, 7)])
    print("Exercise 8: CV for degree 1..6", np.round(cv_auto, 3))
    keep("ex8_cv_poly", cv_auto)
    org = pd.get_dummies(pd.Categorical(Auto["origin"]), drop_first=True, dtype=float).to_numpy()
    wt, yr = Auto["weight"].to_numpy(float), Auto["year"].to_numpy(float)
    a_lin = gam_fit(mpg, [as_linear(hp[:, None]), as_linear(wt[:, None]), as_linear(yr[:, None]), as_linear(org)])
    a_gam = gam_fit(mpg, [{"type": "smooth", "x": v, "df": 4} for v in (hp, wt, yr)] + [as_linear(org)])
    na = len(mpg)
    F8 = anova_f(a_lin["deviance"], na - 6, a_gam["deviance"], na - 15)[0]
    print("Exercise 8: deviance linear %.1f, additive %.1f, F = %.2f" % (a_lin["deviance"], a_gam["deviance"], F8))
    keep("ex8_dev", [a_lin["deviance"], a_gam["deviance"]]); keep("ex8_F", F8)

    # Exercise 9: Boston
    Boston = common.isl_data("Boston", index_col=0)
    nox, dis = Boston["nox"].to_numpy(float), Boston["dis"].to_numpy(float)
    P3 = poly_basis(dis, 3)[0]
    b3 = sm.OLS(nox, np.column_stack([np.ones(len(nox)), P3])).fit()
    print("Exercise 9(a):", b3.params.round(6))
    keep("ex9_cubic_coef", b3.params)
    rss_poly = np.array([sm.OLS(nox, np.column_stack([np.ones(len(nox)), poly_basis(dis, d)[0]])).fit().ssr for d in range(1, 11)])
    keep("ex9_rss_poly", rss_poly)
    cv_bpoly = np.array([cv_mse(poly_design(d), dis, nox) for d in range(1, 11)])
    print("Exercise 9(b), (c): RSS", np.round(rss_poly, 4), " CV chooses degree", 1 + int(np.argmin(cv_bpoly)))
    keep("ex9_cv_poly", cv_bpoly)
    B4, spec = bs_basis(dis, df=4)
    b4 = sm.OLS(nox, np.column_stack([np.ones(len(nox)), B4])).fit()
    print("Exercise 9(d): knot", spec["knots"], " coefficients", b4.params.round(6))
    keep("ex9_bs4_coef", b4.params)
    rss_bs = np.array([sm.OLS(nox, np.column_stack([np.ones(len(nox)), bs_basis(dis, df=d)[0]])).fit().ssr for d in range(3, 17)])
    keep("ex9_rss_bs", rss_bs)
    cv_bbs = np.array([cv_mse(bs_design(d), dis, nox) for d in range(3, 17)])
    print("Exercise 9(e), (f): RSS", np.round(rss_bs, 4), " CV chooses df", 3 + int(np.argmin(cv_bbs)))
    keep("ex9_cv_bs", cv_bbs)

    # Exercise 10: College
    College = common.isl_data("College", index_col=0)
    train = fold_id(len(College), 2) == 0
    Xc = College.drop(columns="Outstate").copy()
    Xc["Private"] = (Xc["Private"] == "Yes").astype(float)
    names = list(Xc.columns)
    yc = College["Outstate"].to_numpy(float)
    order, rss = forward_stepwise(Xc.to_numpy(float)[train], yc[train], names)
    nt = train.sum()
    bic = nt * np.log(rss / nt) + np.log(nt) * np.arange(1, len(rss) + 1)
    size = 1 + int(np.argmin(bic))
    vars10 = order[:size]
    print("Exercise 10(a): forward stepwise order", order[:size], "(BIC chooses %d)" % size)
    keep("ex10_bic", bic - bic[0])
    num = [v for v in names if v in vars10 and v != "Private"]           # in the data's column order, as R
    Xl = np.column_stack([np.ones(nt)] + [Xc[v].to_numpy(float)[train] for v in ["Private"] + num])
    lin10 = np.linalg.lstsq(Xl, yc[train], rcond=None)[0]
    Xl_te = np.column_stack([np.ones((~train).sum())] + [Xc[v].to_numpy(float)[~train] for v in ["Private"] + num])
    g_terms = [as_linear(Xc["Private"].to_numpy(float)[train][:, None])] + [{"type": "smooth", "x": Xc[v].to_numpy(float)[train], "df": 4} for v in num]
    gam10 = gam_fit(yc[train], g_terms)
    pred = gam_predict(gam10, [Xc["Private"].to_numpy(float)[~train][:, None]] + [Xc[v].to_numpy(float)[~train] for v in num])
    test = [np.mean((yc[~train] - Xl_te @ lin10) ** 2), np.mean((yc[~train] - pred) ** 2)]
    print("Exercise 10(c): test MSE linear %.0f, additive %.0f" % tuple(test))
    keep("ex10_test", test); keep("ex10_gam_dev", gam10["deviance"])
    nl_p = []
    df_full = nt - 1 - 1 - 4 * len(num)
    for v in num:
        t0 = [g_terms[0]] + [as_linear(Xc[u].to_numpy(float)[train][:, None]) if u == v else {"type": "smooth", "x": Xc[u].to_numpy(float)[train], "df": 4} for u in num]
        nl_p.append(anova_f(gam_fit(yc[train], t0)["deviance"], df_full + 3, gam10["deviance"], df_full)[1])
    print("Exercise 10(d): p-values for non-linearity", dict(zip(num, np.round(nl_p, 4))))
    keep("ex10_nl_p", nl_p)

    # Exercise 11: backfitting with two inputs (deterministic toy data, the same as in R)
    i = np.arange(1, 101, dtype=float)
    x1 = np.sin(i)
    x2 = 0.6 * x1 + 0.8 * np.cos(2.7 * i)
    y11 = 1 + 2 * x1 - 1.5 * x2 + 0.5 * np.sin(17.3 * i ** 1.5)

    def simple_reg(outcome, feature):
        """Intercept and slope of a simple linear regression."""
        slope = np.cov(feature, outcome, bias=True)[0, 1] / np.var(feature)
        return outcome.mean() - slope * feature.mean(), slope

    beta1, path = 10.0, []
    for it in range(1000):
        beta0, beta2 = simple_reg(y11 - beta1 * x1, x2)
        beta0, beta1 = simple_reg(y11 - beta2 * x2, x1)
        path.append((beta0, beta1, beta2))
    path = np.array(path)
    ls11 = np.linalg.lstsq(np.column_stack([np.ones(100), x1, x2]), y11, rcond=None)[0]
    err11 = np.max(np.abs(path - ls11), axis=1)
    it11 = 1 + int(np.argmax(err11 < 1e-6))
    print("Exercise 11: least squares", ls11.round(5), " iterations to 1e-6:", it11)
    keep("ex11_ls", ls11); keep("ex11_iter", it11); keep("ex11_first", path[0])

    # Exercise 12: p = 100
    I, J = np.meshgrid(np.arange(1, 1001, dtype=float), np.arange(1, 101, dtype=float), indexing="ij")
    X12 = np.sin(0.7 * I * J + 1.3 * J + 0.11 * I)
    beta12 = ((-1.0) ** np.arange(1, 101)) * np.arange(1, 101) / 50
    y12 = X12 @ beta12 + 0.5 * np.sin(5.7 * np.arange(1, 1001))
    ls12 = np.linalg.lstsq(np.column_stack([np.ones(1000), X12]), y12, rcond=None)[0]
    b, b0, err12 = np.zeros(100), 0.0, []
    fit_all = X12 @ b
    for it in range(50):
        for j in range(100):
            r = y12 - (fit_all - X12[:, j] * b[j])
            b0, bj = simple_reg(r, X12[:, j])
            fit_all += X12[:, j] * (bj - b[j])
            b[j] = bj
        err12.append(np.max(np.abs(np.r_[b0, b] - ls12)))
    err12 = np.array(err12)
    print("Exercise 12: max error after sweeps 1..10", np.array2string(err12[:10], precision=3), " sweeps to 1e-6:", 1 + int(np.argmax(err12 < 1e-6)))
    keep("ex12_err", err12[:10]); keep("ex12_iter", 1 + int(np.argmax(err12 < 1e-6)))

# ======================================================================== the lab
def main():
    import matplotlib
    matplotlib.use("Agg")
    import matplotlib.pyplot as plt
    import common

    key = {}

    def keep(name, value):
        key[name] = np.atleast_1d(np.asarray(value, float))

    Wage = common.isl_data("Wage")                      # the 3000 men of the Wage data
    y = Wage["wage"].to_numpy()
    age = Wage["age"].to_numpy(float)
    year = Wage["year"].to_numpy(float)
    edu = pd.Categorical(Wage["education"])
    E = pd.get_dummies(edu, drop_first=True, dtype=float).to_numpy()   # four dummies, "< HS Grad" is the baseline
    n = len(y)
    one = np.ones((n, 1))

    # ============================================================ 7.8.1 polynomials and step functions
    P4, pc = poly_basis(age, 4)
    X = np.column_stack([one, P4])
    M = sm.OLS(y, X).fit()
    print(pd.DataFrame({"coef": M.params, "std err": M.bse, "t": M.tvalues},
                       index=["intercept"] + ["poly(age, 4)[%d]" % k for k in range(1, 5)]).round(4))

    Xraw = np.column_stack([age ** k for k in range(5)])                 # 1, age, ..., age^4
    M2 = sm.OLS(y, Xraw).fit()
    print("raw-basis coefficients:", np.array2string(M2.params, precision=6))

    age_grid = np.arange(age.min(), age.max() + 1)
    G = np.column_stack([np.ones(len(age_grid)), poly_basis(age_grid, 4, pc)[0]])
    pred = M.get_prediction(G)
    fit, se = pred.predicted_mean, pred.se_mean
    bands = np.column_stack([fit + 2 * se, fit - 2 * se])
    Graw = np.column_stack([age_grid ** k for k in range(5)])
    print("largest difference between the two bases' fitted values: %.3g" % np.max(np.abs(fit - Graw @ M2.params)))
    se_hand = pointwise_se(Graw, M2.cov_params())                       # sqrt(l0' C l0), Section 7.1
    print("largest difference between get_prediction's and the hand-computed standard errors: %.3g" % np.max(np.abs(se_hand - se)))
    keep("poly4_coef", M.params); keep("poly4_se1", M.bse[1])
    keep("poly4_fit_age50", fit[age_grid == 50]); keep("poly4_se_age50", se[age_grid == 50])
    keep("poly4_se_age80", se[age_grid == 80])

    # nested F tests for the degree
    fits = [sm.OLS(y, np.column_stack([one, poly_basis(age, d)[0]])).fit() for d in range(1, 6)]
    av = anova_lm(*fits)
    print(av)
    M5 = fits[4]
    print("t^2 for the quadratic term: %.3f" % M5.tvalues[2] ** 2)
    keep("anova_rss", av["ssr"]); keep("anova_F", av["F"][1:]); keep("anova_p", av["Pr(>F)"][1:])

    fits_e = [sm.OLS(y, np.column_stack([one, E, poly_basis(age, d)[0]])).fit() for d in range(1, 4)]
    av2 = anova_lm(*fits_e)
    print(av2)
    keep("anova_edu_F", av2["F"][1:])

    # polynomial logistic regression for wage > 250
    high = (y > 250).astype(float)
    B = sm.GLM(high, X, family=sm.families.Binomial()).fit()
    print(pd.DataFrame({"coef": B.params, "std err": B.bse}).round(4))
    eta_hat = G @ B.params
    eta_se = pointwise_se(G, B.cov_params())                            # standard errors on the logit scale
    pfit = 1 / (1 + np.exp(-eta_hat))
    pband = 1 / (1 + np.exp(-np.column_stack([eta_hat + 2 * eta_se, eta_hat - 2 * eta_se])))
    keep("logit_coef", B.params); keep("logit_p_age50", pfit[age_grid == 50])
    keep("logit_band_age80", pband[age_grid == 80][0])

    fig, ax = plt.subplots(1, 2, figsize=(9, 4.2))
    ax[0].scatter(age, y, s=4, c="0.6")
    ax[0].plot(age_grid, fit, "b", lw=2)
    ax[0].plot(age_grid, bands, "b:", lw=1)
    ax[0].set(xlabel="age", ylabel="wage", title="Degree-4 polynomial")
    rng = np.random.default_rng(0)
    ax[1].scatter(age + 0.2 * rng.uniform(size=n), np.where(high == 1, 0.198, 0.002), c="0.6", marker="|", s=20)
    ax[1].plot(age_grid, pfit, "b", lw=2)
    ax[1].plot(age_grid, pband, "b:", lw=1)
    ax[1].set(xlabel="age", ylabel="Pr(wage > 250 | age)", ylim=(0, 0.2))
    common.savefig(fig, 7, "lab-py-poly", formats=("svg",))

    # step functions: four bins of equal width, as R's cut(age, 4)
    cut_age = pd.cut(age, 4)
    print(pd.Series(cut_age).value_counts(sort=False))
    S = pd.get_dummies(cut_age, drop_first=True, dtype=float).to_numpy()
    Ms = sm.OLS(y, np.column_stack([one, S])).fit()
    print("step-function coefficients:", Ms.params.round(4))
    keep("step_coef", Ms.params)

    # ============================================================ 7.8.2 splines
    Bs, bspec = bs_basis(age, knots=[25, 40, 60])
    Mbs = sm.OLS(y, np.column_stack([one, Bs])).fit()
    Gbs = np.column_stack([np.ones(len(age_grid)), bs_basis(age_grid, bspec["knots"], boundary=bspec["boundary"])[0]])
    pbs = Mbs.get_prediction(Gbs)
    print("bs basis:", Bs.shape, "  bs(df=6) knots:", bs_basis(age, df=6)[1]["knots"])
    keep("bs_coef", Mbs.params); keep("bs_fit_age50", pbs.predicted_mean[age_grid == 50])
    keep("bs_se_age80", pbs.se_mean[age_grid == 80])

    Ns4, nspec = ns_basis(age, df=4)
    Mns = sm.OLS(y, np.column_stack([one, Ns4])).fit()
    Gns = np.column_stack([np.ones(len(age_grid)), ns_basis(age_grid, nspec["knots"], boundary=nspec["boundary"])[0]])
    pns = Mns.get_prediction(Gns)
    print("ns(df=4) knots:", nspec["knots"])
    keep("ns4_coef", Mns.params); keep("ns4_se_age80", pns.se_mean[age_grid == 80])
    Mns5 = sm.OLS(y, np.column_stack([one, ns_basis(age, df=5)[0]])).fit()
    print("ns(df=5) coefficients:", Mns5.params.round(4))
    keep("ns5_coef", Mns5.params)

    # smoothing splines
    ss = SmoothSpline(age, y)
    lam16 = ss.lam_for_df(16)
    lam_cv = ss.lam_by_cv()
    print("df = 16: lambda = %.4g;  LOOCV: lambda = %.4g, df = %.4f, CV = %.2f" % (lam16, lam_cv, ss.df(lam_cv), ss.loocv(lam_cv)))
    keep("ss16_df", ss.df(lam16)); keep("ss16_lambda", lam16); keep("ss16_fit", ss.predict(lam16, [20, 40, 60, 80]))
    keep("sscv_df", ss.df(lam_cv)); keep("sscv_cv", ss.loocv(lam_cv)); keep("sscv_fit", ss.predict(lam_cv, [20, 40, 60, 80]))
    ssa = SmoothSpline(age, y, all_knots=True)
    keep("ss16all_fit", ssa.predict(ssa.lam_for_df(16), [20, 40, 60, 80]))

    fig, ax = plt.subplots(1, 2, figsize=(9, 4.2))
    ax[0].scatter(age, y, s=4, c="0.7")
    ax[0].plot(age_grid, pbs.predicted_mean, "k", lw=2, label="bs, knots 25, 40, 60")
    ax[0].plot(age_grid, pbs.conf_int(alpha=0.0455), "k--", lw=1)
    ax[0].plot(age_grid, pns.predicted_mean, "r", lw=2, label="ns, df = 4")
    ax[0].set(xlabel="age", ylabel="wage", title="Regression splines")
    ax[0].legend(fontsize=8)
    ax[1].scatter(age, y, s=4, c="0.7")
    ax[1].plot(age_grid, ss.predict(lam16, age_grid), "r", lw=2, label="16 DF")
    ax[1].plot(age_grid, ss.predict(lam_cv, age_grid), "b", lw=2, label="%.1f DF" % ss.df(lam_cv))
    ax[1].set(xlabel="age", ylabel="wage", title="Smoothing spline")
    ax[1].legend(fontsize=8)
    common.savefig(fig, 7, "lab-py-splines", formats=("svg",))

    # local regression: local quadratic fits (the default of R's loess), spans 0.2 and 0.5
    lo2, lo5 = loess(age, y, age_grid, 0.2), loess(age, y, age_grid, 0.5)
    fig, ax = plt.subplots(figsize=(4.6, 4.2))
    ax.scatter(age, y, s=4, c="0.7")
    ax.plot(age_grid, lo2, "r", lw=2, label="Span = 0.2")
    ax.plot(age_grid, lo5, "b", lw=2, label="Span = 0.5")
    ax.set(xlabel="age", ylabel="wage", title="Local regression")
    ax.legend(fontsize=8)
    common.savefig(fig, 7, "lab-py-loess", formats=("svg",))
    keep("lo2d_fit", loess(age, y, [20, 40, 60, 80], 0.2)); keep("lo5d_fit", loess(age, y, [20, 40, 60, 80], 0.5))
    keep("lo2d1_fit", loess(age, y, [20, 40, 60, 80], 0.2, degree=1))
    # the Python edition's lowess: local LINEAR fits with three robustness iterations by default
    lw = sm.nonparametric.lowess(y, age, frac=0.2, xvals=np.array([20.0, 40, 60, 80]))
    print("statsmodels lowess (frac 0.2, it = 3) at ages 20, 40, 60, 80:", np.round(lw, 2))

    # ============================================================ 7.8.3 generalised additive models
    Nyear = ns_basis(year, df=4)[0]
    Nage = ns_basis(age, df=5)[0]
    gam1 = sm.OLS(y, np.column_stack([one, Nyear, Nage, E])).fit()      # natural splines: one least-squares fit
    print("GAM with natural splines: RSS = %.1f" % gam1.ssr)
    keep("gam1_rss", gam1.ssr)

    lin = lambda M_: {"type": "linear", "X": M_}
    m3 = gam_fit(y, [{"type": "smooth", "x": year, "df": 4}, {"type": "smooth", "x": age, "df": 5}, lin(E)])
    m2 = gam_fit(y, [lin(year[:, None]), {"type": "smooth", "x": age, "df": 5}, lin(E)])
    m1 = gam_fit(y, [{"type": "smooth", "x": age, "df": 5}, lin(E)])
    dev = np.array([m1["deviance"], m2["deviance"], m3["deviance"]])
    resdf = np.array([n - 1 - 5 - 4, n - 1 - 1 - 5 - 4, n - 1 - 4 - 5 - 4])
    disp = dev[2] / resdf[2]                                             # dispersion of the largest model
    F = -np.diff(dev) / -np.diff(resdf) / disp
    p = stats.f.sf(F, -np.diff(resdf), resdf[2])
    print(pd.DataFrame({"Resid. Df": resdf, "Resid. Dev": dev.round(1), "F": np.r_[np.nan, F], "Pr(>F)": np.r_[np.nan, p]}))
    keep("gam_dev", dev); keep("gam_resdf", resdf); keep("gam_F", F); keep("gam_p", p)
    keep("gam_m3_fit", m3["eta"][:5]); keep("gam_m2_pred", m2["eta"][:5])

    fig, ax = plt.subplots(1, 3, figsize=(10, 3.6))
    for a_, xv, f, lab in [(ax[0], year, m3["f"][0], "year"), (ax[1], age, m3["f"][1], "age")]:
        o = np.argsort(xv)
        a_.plot(xv[o], f[o], "b", lw=2)
        a_.set(xlabel=lab, ylabel="f(%s)" % lab)
    levels = [s.split(". ")[1] for s in edu.categories]
    fe = [m3["f"][2][edu.codes == k][0] for k in range(5)]
    ax[2].plot(range(5), fe, "b_", ms=20, mew=2)
    ax[2].set_xticks(range(5), levels, rotation=20, fontsize=7)
    ax[2].set(ylabel="f(education)")
    common.savefig(fig, 7, "lab-py-gam", formats=("svg",))

    # logistic GAM for wage > 250, leaving out the "< HS Grad" group (no high earners there)
    print(pd.crosstab(Wage["education"], y > 250))
    keep_rows = edu.codes != 0
    E_s = pd.get_dummies(pd.Categorical(Wage["education"][keep_rows]), drop_first=True, dtype=float).to_numpy()
    lr_s = gam_fit(high[keep_rows], [lin(year[keep_rows, None]), {"type": "smooth", "x": age[keep_rows], "df": 5}, lin(E_s)],
                   family="binomial")
    print("logistic GAM without < HS Grad: deviance = %.3f" % lr_s["deviance"])
    keep("gamlrs_dev", lr_s["deviance"])

    exercises(keep)

    names, vals = [], []
    for k, v in key.items():
        names += [k] if len(v) == 1 else ["%s_%d" % (k, i + 1) for i in range(len(v))]
        vals += list(v)
    os.makedirs(os.path.join(HERE, "cache"), exist_ok=True)
    pd.DataFrame({"name": names, "value": vals}).to_csv(os.path.join(HERE, "cache", "ch07_lab_py.csv"), index=False, float_format="%.10g")
    print("wrote %d numbers to cache/ch07_lab_py.csv" % len(vals))


if __name__ == "__main__":
    main()
