"""James et al. (2021, 2023), Chapter 10: Deep Learning.

Reproduces the figures and tables of Chapter 10 of G. James, D. Witten, T. Hastie and R. Tibshirani,
An Introduction to Statistical Learning with Applications in R, 2nd edition (Springer, 2021),
pp. 403-460 (the same figures appear in the Python edition of 2023, with J. Taylor), written from
scratch with numpy, scipy, scikit-learn, PyTorch (CPU, one thread) and matplotlib.

Figures reproduced:
* 10.2  the sigmoid and ReLU activations;
* 10.3  MNIST digits, three of them enlarged to show the 28 x 28 pixels;
* 10.7  convolution with a vertical and a horizontal stripe filter (on MNIST digits, see below);
* 10.9  data augmentation (on an MNIST digit);
* 10.14 the three NYSE series; 10.15 the autocorrelation of log volume; 10.16 the RNN forecast;
* 10.17 gradient descent on a one-dimensional nonconvex function;
* 10.18 training and validation loss and error of the MNIST network, by epoch;
* 10.20 double descent of minimum-norm natural splines; 10.21 four of the fitted splines;
* Tables 10.1 (MNIST test errors), 10.2 and 10.3 (Hitters), with `--fig tables`;
* the figure of applied Exercise 6 (gradient descent on sin(beta) + beta/10), `--fig ex6`.
Run `python3 ch10_deep_learning.py --list`, or `--fig 10.20`, or `--fig demos` to write the data of the
three demonstrations to ../data/ch10-*.json and print their reference numbers.

Figures skipped, and why:
* 10.1, 10.4, 10.8, 10.12, 10.19: diagrams of network architectures, not computed from data;
* 10.6: a cartoon of a tiger, not data;
* 10.5 (CIFAR100 images): the CIFAR100 data are a 160 MB download that the course does not need;
* 10.10 (ResNet50 predictions): needs the pretrained ResNet50 weights, distributed with torchvision,
  which is not used here; the six photographs are on the book's website;
* 10.11 (IMDb lasso and network accuracy): needs the IMDb corpus, not distributed with the data;
* 10.13 (one-hot and embedded words): a schematic made from random numbers.
The tiger photograph of Figures 10.7 and 10.9 is not distributed with the book's data, so those two
figures show the same operations on MNIST digits (a 3 x 3 mosaic of digits for Figure 10.7).

Settings chosen where the book gives none:
* Figure 10.17: R(theta) is a quartic with minima at -0.46 and 1.02 and a maximum at 0.18 (the book
  gives only the two minima); gradient descent starts at 0.3 with the step size that reaches the
  global minimum in 7 steps.
* Figure 10.18 and Table 10.1: the network of Figure 10.4 (784-256-128-10, ReLU), RMSprop with
  learning rate 0.001, minibatches of 128, 30 epochs, the last 12000 training images as the
  validation set. Dropout 0.4 and 0.3, as in the lab; the ridge network penalises W1 and W2 with
  lambda per minibatch-mean loss chosen on the validation set from 1e-3, 1e-4, 1e-5 (1e-5 won). The
  training curves are the averages over the minibatches of each epoch (with dropout on), as keras reports
  them; the validation curves are computed at the end of each epoch. LDA is scikit-learn's (SVD solver).
* Table 10.2: the test set of the R lab (set.seed(13)); the lasso uses ten fixed folds (training row i
  in fold i mod 10) on glmnet's scale; the network has 64 ReLU units, 10% dropout, RMSprop (0.001),
  minibatches of 32, 1000 epochs, as described in footnote 21 of the book.
* Figures 10.20-10.21: n = 20, X ~ U(-5, 5), Y = sin(X) + N(0, 0.3^2), numpy default_rng(SEED_DD).
  A natural spline with d degrees of freedom has d basis functions, the constant included, and d knots
  at the d equi-probability quantiles of the training x (so it interpolates at d = n = 20). The basis is
  the natural-spline subspace of the cubic B-splines, with orthonormal coefficients (as R's
  ns(..., intercept = TRUE)); the minimum-norm solution does not depend on which orthonormal basis of
  that subspace is used. The test error is the expected squared error at a new point,
  sigma^2 + average of (sin(x) - f_d(x))^2 over a grid of 2001 points on [-5, 5]; this removes the
  noise of a finite test set. The seed SEED_DD gives a training set whose curve resembles the book's;
  the median over 100 training sets is drawn as well.
"""
import json
import os

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

import numpy as np
import pandas as pd

import common
from common import BLUE, GREY, ORANGE, RED, plt, savefig
from ch10_lab import TESTID, hitters_matrix, lasso_glmnet, load_nyse

HERE = os.path.dirname(os.path.abspath(__file__))
CACHE = os.path.join(HERE, "cache")
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
CH = 10
SEED_DD = 6
SIGMA_DD = 0.3
GRID_DD = np.linspace(-5, 5, 2001)
D_VALUES = np.arange(2, 81)


# ======================================================================== natural splines and minimum norm
def _bs_design(x, t, deriv=0):
    """All cubic B-splines with knot vector t (or their derivatives) at x, as a dense matrix."""
    from scipy.interpolate import BSpline
    m = len(t) - 4
    if deriv == 0:
        return BSpline.design_matrix(x, t, 3, extrapolate=True).toarray()
    return np.column_stack([BSpline(t, np.eye(m)[j], 3).derivative(deriv)(x) for j in range(m)])


def ns_basis_full(x, knots):
    """Natural cubic spline basis with all its d = len(knots) functions (the constant included).

    The cubic B-splines on the knots (boundary knots repeated four times) are combined into the
    d-dimensional subspace whose second derivative is zero at both boundary knots, through an
    orthonormal basis of the null space of the 2 x (d + 2) constraint matrix. Beyond the boundary
    knots the functions continue linearly, as natural splines do.
    """
    x = np.atleast_1d(np.asarray(x, float))
    knots = np.asarray(knots, float)
    lo, hi = knots[0], knots[-1]
    t = np.r_[[lo] * 4, knots[1:-1], [hi] * 4]
    C = _bs_design(np.array([lo, hi]), t, deriv=2)
    Q, _ = np.linalg.qr(C.T, mode="complete")
    xin = np.clip(x, lo, hi)
    B = _bs_design(xin, t)
    if np.any(x != xin):
        D1 = _bs_design(np.array([lo, hi]), t, deriv=1)
        B = B + np.where(x < lo, x - lo, 0)[:, None] * D1[0] + np.where(x > hi, x - hi, 0)[:, None] * D1[1]
    return B @ Q[:, 2:]


def dd_knots(x, d):
    return np.quantile(x, np.linspace(0, 1, d))


def min_norm_fit(B, y, lam=0.0):
    """Minimum-norm least squares: the pseudo-inverse solution, computed from the eigenvectors of the
    smaller of the two Gram matrices (B'B when d < n, BB' = B(B'B)^+B' otherwise); with lam > 0 the ridge
    solution B'(BB' + lam I)^{-1} y. Eigenvalues below 1e-13 times the largest count as zero."""
    n, d = B.shape
    if lam > 0:
        return B.T @ np.linalg.solve(B @ B.T + lam * np.eye(n), y)
    if d < n:
        w, V = np.linalg.eigh(B.T @ B)
        keep = w > 1e-13 * w.max()
        return V[:, keep] @ ((V[:, keep].T @ (B.T @ y)) / w[keep])
    w, V = np.linalg.eigh(B @ B.T)
    keep = w > 1e-13 * w.max()
    return B.T @ (V[:, keep] @ ((V[:, keep].T @ y) / w[keep]))


def dd_data(seed, n=20):
    rng = np.random.default_rng(seed)
    x = rng.uniform(-5, 5, n)
    return x, np.sin(x) + SIGMA_DD * rng.standard_normal(n)


def dd_curve(x, y, ds=D_VALUES, lam=0.0):
    """Training error, test error and coefficient norm of the min-norm natural spline for each d."""
    out = []
    for d in ds:
        kn = dd_knots(x, d)
        b = min_norm_fit(ns_basis_full(x, kn), y, lam)
        fg = ns_basis_full(GRID_DD, kn) @ b
        out.append((d, np.mean((y - ns_basis_full(x, kn) @ b) ** 2),
                    SIGMA_DD ** 2 + np.mean((np.sin(GRID_DD) - fg) ** 2), np.linalg.norm(b)))
    return np.array(out)


def dd_median(nsim=100):
    path = os.path.join(CACHE, "ch10-dd-median.npz")
    if os.path.exists(path):
        return np.load(path)["med"]
    errs = np.array([dd_curve(*dd_data(1000 + s))[:, 2] for s in range(nsim)])
    med = np.median(errs, axis=0)
    os.makedirs(CACHE, exist_ok=True)
    np.savez(path, med=med)
    return med


def fig_10_20(out=None):
    """Double descent: training and test error of minimum-norm natural splines against d."""
    x, y = dd_data(SEED_DD)
    c = dd_curve(x, y)
    med = dd_median()
    fig, ax = plt.subplots(figsize=(6.4, 4.0))
    ax.plot(c[:, 0], c[:, 1], "o-", color=ORANGE, ms=3, lw=1, label="Training error")
    ax.plot(c[:, 0], c[:, 2], "o-", color="#3fa7e0", ms=3, lw=1, label="Test error")
    ax.plot(D_VALUES, med, "--", color=GREY, lw=1, label="Test error, median of 100 data sets")
    ax.axvline(20, color=GREY, lw=0.8, ls=":")
    ax.set(xscale="log", ylim=(0, 2), xlabel="Degrees of freedom", ylabel="Error")
    ax.set_xticks([2, 5, 10, 20, 50]); ax.set_xticklabels(["2", "5", "10", "20", "50"])
    ax.legend(frameon=False, loc="upper right", fontsize=8.5)
    savefig(fig, CH, "fig10-20", out)


def fig_10_21(out=None):
    """The fitted natural splines with 8, 20, 42 and 80 degrees of freedom."""
    x, y = dd_data(SEED_DD)
    fig, axes = common.panel_grid(2, 2, size=(3.3, 2.6))
    for ax, d in zip(axes.ravel(), (8, 20, 42, 80)):
        kn = dd_knots(x, d)
        b = min_norm_fit(ns_basis_full(x, kn), y)
        ax.plot(GRID_DD, np.sin(GRID_DD), color="black", lw=1)
        ax.plot(GRID_DD, ns_basis_full(GRID_DD, kn) @ b, color=ORANGE, lw=1.1)
        ax.scatter(x, y, s=16, facecolor="none", edgecolor="black", lw=0.8, zorder=3)
        ax.plot(x, np.full_like(x, -2.95), "|", color="black", ms=5)
        ax.set(ylim=(-3, 3), xlim=(-5.2, 5.2), title="%d Degrees of Freedom" % d)
    fig.tight_layout()
    savefig(fig, CH, "fig10-21", out)


# ======================================================================== activations, digits, convolution
def fig_10_2(out=None):
    """The sigmoid and the ReLU (scaled down by 5) activation functions."""
    z = np.linspace(-4, 4, 401)
    fig, ax = plt.subplots(figsize=(5.2, 3.4))
    ax.plot(z, common.sigmoid(z), color=BLUE, label="sigmoid")
    ax.plot(z, np.maximum(z, 0) / 5, color=ORANGE, label="ReLU / 5")
    ax.set(xlabel="$z$", ylabel="$g(z)$", ylim=(-0.02, 1.02))
    ax.legend(frameon=False, loc="upper left")
    savefig(fig, CH, "fig10-2", out)


def fig_10_3(out=None):
    """MNIST digits; the first 3, 5 and 8 enlarged with their pixel values."""
    X, g = common.mnist(train=True)
    fig = plt.figure(figsize=(9, 4.2))
    gs = fig.add_gridspec(4, 13, width_ratios=[1] * 10 + [0.3, 3.2, 0.1], wspace=0.08, hspace=0.08)
    for i in range(40):
        ax = fig.add_subplot(gs[i // 10, i % 10])
        ax.imshow(X[i].reshape(28, 28), cmap="gray_r", vmin=0, vmax=1)
        ax.set_axis_off()
    sub = gs[:, 11].subgridspec(3, 1, hspace=0.12)
    for k, digit in enumerate((3, 5, 8)):
        ax = fig.add_subplot(sub[k])
        img = (X[np.argmax(g == digit)] * 255).round().reshape(28, 28)
        ax.imshow(img, cmap="gray_r", vmin=0, vmax=255)
        ax.set_xticks(np.arange(-0.5, 28, 1), minor=True); ax.set_yticks(np.arange(-0.5, 28, 1), minor=True)
        ax.grid(which="minor", color="#c8d0dc", lw=0.25)
        ax.tick_params(which="both", length=0, labelbottom=False, labelleft=False)
        ax.set_ylabel("digit %d" % digit, fontsize=8)
    savefig(fig, CH, "fig10-3", out)


def conv2d_valid(img, filt):
    """The convolution of Section 10.3.1 (no flip, no padding): out[i, j] = sum_{a,b} img[i+a, j+b] filt[a, b]."""
    H, W = img.shape
    h, w = filt.shape
    out = np.zeros((H - h + 1, W - w + 1))
    for a in range(h):
        for b in range(w):
            out += filt[a, b] * img[a:a + H - h + 1, b:b + W - w + 1]
    return out


def max_pool(img, k=2):
    H, W = img.shape[0] // k * k, img.shape[1] // k * k
    return img[:H, :W].reshape(H // k, k, W // k, k).max(axis=(1, 3))


def stripe_filter(size=7, vertical=True, width=1):
    f = np.zeros((size, size))
    mid = size // 2
    if vertical:
        f[:, mid - width // 2: mid + width // 2 + 1] = 1
    else:
        f[mid - width // 2: mid + width // 2 + 1, :] = 1
    return f


def digit_mosaic():
    X, _ = common.mnist(train=False)
    return np.block([[X[3 * r + c].reshape(28, 28) for c in range(3)] for r in range(3)])


def fig_10_7(out=None):
    """Convolution of an image (a mosaic of nine test digits) with a vertical and a horizontal stripe filter."""
    img = digit_mosaic()
    fig = plt.figure(figsize=(8.2, 4.2))
    gs = fig.add_gridspec(2, 3, width_ratios=[2, 0.7, 1.4], wspace=0.15, hspace=0.15)
    ax = fig.add_subplot(gs[:, 0])
    ax.imshow(img, cmap="gray"); ax.set_axis_off(); ax.set_title("input image (84 x 84)", fontsize=9)
    for r, vertical in enumerate((True, False)):
        f = stripe_filter(7, vertical)
        axf = fig.add_subplot(gs[r, 1])
        axf.imshow(f, cmap="gray", vmin=0, vmax=1); axf.set_xticks([]); axf.set_yticks([])
        axf.set_title("%s filter (7 x 7)" % ("vertical" if vertical else "horizontal"), fontsize=8)
        axc = fig.add_subplot(gs[r, 2])
        axc.imshow(conv2d_valid(img, f), cmap="gray"); axc.set_axis_off()
        axc.set_title("convolved image (78 x 78)", fontsize=8)
    savefig(fig, CH, "fig10-7", out)


def augment(img, rng):
    """One random natural distortion of a digit: zoom, shift, shear and a small rotation (no flips)."""
    from scipy import ndimage
    ang = np.deg2rad(rng.uniform(-15, 15))
    zoom = rng.uniform(0.85, 1.15)
    shear = rng.uniform(-0.25, 0.25)
    A = np.array([[np.cos(ang), -np.sin(ang)], [np.sin(ang), np.cos(ang)]]) @ np.array([[1, shear], [0, 1]]) / zoom
    c = np.array([13.5, 13.5])
    shift = rng.uniform(-2.5, 2.5, 2)
    return ndimage.affine_transform(img, A, offset=c - A @ c - shift, order=1, mode="constant")


def fig_10_9(out=None):
    """Data augmentation: a digit and six random natural distortions of it."""
    X, _ = common.mnist(train=False)
    img = X[0].reshape(28, 28)
    rng = np.random.default_rng(9)
    fig, axes = plt.subplots(1, 7, figsize=(9, 1.6))
    for k, ax in enumerate(axes):
        ax.imshow(img if k == 0 else augment(img, rng), cmap="gray_r", vmin=0, vmax=1)
        ax.set_axis_off()
        ax.set_title("original" if k == 0 else "distorted %d" % k, fontsize=8)
    savefig(fig, CH, "fig10-9", out)


# ======================================================================== NYSE
def nyse_frame():
    """The standardised series (R's scale()), the lagged frame of the lab, and the training indicator."""
    N = load_nyse()
    cols = ["DJ_return", "log_volume", "log_volatility"]
    xd = (N[cols] - N[cols].mean()) / N[cols].std()
    ar = pd.DataFrame({"log_volume": xd["log_volume"]})
    for lag in range(1, 6):
        for c in cols:
            ar["L%d.%s" % (lag, c)] = xd[c].shift(lag)
    return N, ar.iloc[5:], N["train"].to_numpy(bool)[5:]


def fig_10_14(out=None):
    """The three NYSE series, training period to the left of the red line."""
    N = load_nyse()
    dates = pd.to_datetime(N["date"])
    fig, axes = plt.subplots(3, 1, figsize=(7, 6.2), sharex=True)
    for ax, col, lab in zip(axes, ["log_volume", "DJ_return", "log_volatility"],
                            ["Log(Trading Volume)", "Dow Jones Return", "Log(Volatility)"]):
        ax.plot(dates, N[col], color="black", lw=0.35)
        ax.axvline(pd.Timestamp("1980-01-02"), color=RED, lw=1.2)
        ax.set_ylabel(lab, fontsize=9)
    fig.tight_layout()
    savefig(fig, CH, "fig10-14", out)


def acf(v, nlags=37):
    """Sample autocorrelations as R's acf(): sum_t (v_t - mean)(v_{t+k} - mean) / sum_t (v_t - mean)^2."""
    v = np.asarray(v, float) - np.mean(v)
    return np.array([np.sum(v[:len(v) - k] * v[k:]) for k in range(nlags + 1)]) / np.sum(v * v)


def fig_10_15(out=None):
    """The autocorrelation function of log volume, lags 0 to 37."""
    r = acf(load_nyse()["log_volume"])
    fig, ax = plt.subplots(figsize=(6.2, 3.2))
    ax.vlines(np.arange(len(r)), 0, r, color="black", lw=1.4)
    ax.axhline(0, color="black", lw=0.6)
    ax.set(xlabel="Lag", ylabel="Autocorrelation Function", ylim=(-0.05, 1.02))
    savefig(fig, CH, "fig10-15", out)


def rnn_forecast():
    """Fit the RNN of Section 10.5.2 (12 tanh units, lag 5) once; cache the test predictions."""
    path = os.path.join(CACHE, "ch10-rnn.npz")
    if os.path.exists(path):
        return dict(np.load(path))
    torch = common.torch_setup(0, 1)
    nn = torch.nn
    N, ar, istrain = nyse_frame()
    yv = ar["log_volume"].to_numpy()
    X = ar.drop(columns="log_volume").to_numpy().reshape(-1, 5, 3)[:, ::-1, :].copy()

    class RNN(nn.Module):
        def __init__(self):
            super().__init__()
            self.rnn, self.drop, self.dense = nn.RNN(3, 12, batch_first=True), nn.Dropout(0.1), nn.Linear(12, 1)

        def forward(self, x):
            return self.dense(self.drop(self.rnn(x)[0][:, -1])).flatten()

    m = RNN()
    opt = torch.optim.RMSprop(m.parameters(), lr=0.001)
    Xt, Yt = torch.tensor(X[istrain], dtype=torch.float32), torch.tensor(yv[istrain], dtype=torch.float32)
    gen = torch.Generator().manual_seed(0)
    for _ in range(200):
        m.train()
        perm = torch.randperm(len(Yt), generator=gen)
        for s in range(0, len(Yt), 64):
            idx = perm[s:s + 64]
            opt.zero_grad(); ((m(Xt[idx]) - Yt[idx]) ** 2).mean().backward(); opt.step()
    m.eval()
    with torch.no_grad():
        pred = m(torch.tensor(X[~istrain], dtype=torch.float32)).numpy()
    obs = yv[~istrain]
    res = {"pred": pred, "obs": obs, "r2": 1 - np.mean((pred - obs) ** 2) / obs.var(ddof=1),
           "r2_naive": 1 - np.mean((ar["L1.log_volume"].to_numpy()[~istrain] - obs) ** 2) / obs.var(ddof=1)}
    os.makedirs(CACHE, exist_ok=True)
    np.savez(path, **res)
    return res


def fig_10_16(out=None):
    """The RNN forecast of log volume on the test period, 1980-1986."""
    res = rnn_forecast()
    N, ar, istrain = nyse_frame()
    dates = pd.to_datetime(N["date"].iloc[5:][~istrain])
    fig, ax = plt.subplots(figsize=(7, 3.2))
    ax.plot(dates, res["obs"], color="black", lw=0.5)
    ax.plot(dates, res["pred"], color=ORANGE, lw=0.6)
    ax.set(ylabel="log(Trading Volume)")
    ax.text(0.01, 0.04, "test $R^2$ = %.2f" % res["r2"], transform=ax.transAxes, fontsize=9)
    savefig(fig, CH, "fig10-16", out)
    print("RNN test R2 %.4f; yesterday's value as the forecast: R2 %.4f" % (res["r2"], res["r2_naive"]))


# ======================================================================== gradient descent
GD_ROOTS = (-0.46, 0.18, 1.02)


def gd_objective():
    """R(theta) = c * integral of (t + 0.46)(t - 0.18)(t - 1.02), shifted so that R(1.02) = 0.5;
    c is chosen so that R(-0.46) = 1.45 (the shape of the book's Figure 10.17)."""
    a, b, d = GD_ROOTS
    s1, s2, s3 = a + b + d, a * b + a * d + b * d, a * b * d
    P = lambda t: t ** 4 / 4 - s1 * t ** 3 / 3 + s2 * t ** 2 / 2 - s3 * t
    c = (1.45 - 0.5) / (P(a) - P(d))
    R = lambda t: c * (P(t) - P(d)) + 0.5
    dR = lambda t: c * (t - a) * (t - b) * (t - d)
    return R, dR


def gd_path(theta0=0.3, steps=7):
    """Gradient descent from theta0 with the smallest constant step size rho whose 7th iterate is
    within 0.005 of the global minimum 1.02."""
    R, dR = gd_objective()

    def run(rho):
        th = [theta0]
        for _ in range(steps):
            th.append(th[-1] - rho * dR(th[-1]))
        return np.array(th)
    rhos = np.linspace(0.01, 3, 3000)
    rho = next(r for r in rhos if abs(run(r)[-1] - 1.02) < 0.005)
    return run(rho), rho


def fig_10_17(out=None):
    """Gradient descent on a nonconvex R(theta) with a local and a global minimum."""
    R, _ = gd_objective()
    th, rho = gd_path()
    t = np.linspace(-1, 1.4, 400)
    fig, ax = plt.subplots(figsize=(6.2, 3.4))
    ax.plot(t, R(t), color=ORANGE, lw=1.6)
    for k in range(8):
        col = "black" if k < 7 else RED
        ax.plot(th[k], R(th[k]), "o", color=col, ms=4, zorder=3)
        ax.annotate(r"$\theta^{%d}$" % k, (th[k], R(th[k])), xytext=(4, 6), textcoords="offset points",
                    fontsize=8.5, color=col)
    ax.set(xlabel=r"$\theta$", ylabel=r"$R(\theta)$", ylim=(0, 6.2))
    savefig(fig, CH, "fig10-17", out)
    print("gradient descent: rho = %.3f, iterates %s" % (rho, np.round(th, 3)))


def fig_ex6(out=None):
    """Exercise 6: gradient descent on R(beta) = sin(beta) + beta/10 from 2.3 and from 1.4."""
    b = np.linspace(-6, 6, 600)
    fig, ax = plt.subplots(figsize=(6.4, 3.4))
    ax.plot(b, np.sin(b) + b / 10, color="black", lw=1.2)
    for b0, col in ((2.3, RED), (1.4, BLUE)):
        path = [b0]
        for _ in range(60):
            path.append(path[-1] - 0.1 * (np.cos(path[-1]) + 0.1))
        path = np.array(path)
        ax.plot(path, np.sin(path) + path / 10, "o", color=col, ms=3, label=r"$\beta^0$ = %.1f" % b0)
    ax.set(xlabel=r"$\beta$", ylabel=r"$R(\beta)$")
    ax.legend(frameon=False)
    savefig(fig, CH, "ex10-6", out)


# ======================================================================== MNIST: Figure 10.18 and Table 10.1
def mnist_results():
    path = os.path.join(CACHE, "ch10-mnist.json")
    if os.path.exists(path):
        with open(path) as fh:
            return json.load(fh)
    torch = common.torch_setup(0, 1)
    nn = torch.nn
    X, g = common.mnist(train=True)
    Xte, gte = common.mnist(train=False)
    Xt, gt = torch.tensor(X, dtype=torch.float32), torch.tensor(g)
    Xte_t, gte_t = torch.tensor(Xte, dtype=torch.float32), torch.tensor(gte)
    tr, va = slice(0, 48000), slice(48000, 60000)

    def net(dropout):
        return nn.Sequential(nn.Linear(784, 256), nn.ReLU(), nn.Dropout(dropout[0]), nn.Linear(256, 128), nn.ReLU(),
                             nn.Dropout(dropout[1]), nn.Linear(128, 10))

    def train(model, lam=0.0, epochs=30, seed=0):
        torch.manual_seed(seed)
        gen = torch.Generator().manual_seed(seed)
        opt = torch.optim.RMSprop(model.parameters(), lr=0.001)
        weights = [model[0].weight, model[3].weight] if lam > 0 else []
        hist = []
        for ep in range(epochs):
            model.train()
            perm = torch.randperm(48000, generator=gen)
            tot_loss, tot_err = 0.0, 0.0
            for s in range(0, 48000, 128):
                idx = perm[s:s + 128]
                out = model(Xt[tr][idx])
                loss = nn.functional.cross_entropy(out, gt[tr][idx])
                obj = loss + lam * sum((w ** 2).sum() for w in weights)
                opt.zero_grad(); obj.backward(); opt.step()
                tot_loss += loss.item() * len(idx)
                tot_err += float((out.argmax(1) != gt[tr][idx]).float().sum())
            model.eval()
            with torch.no_grad():
                out = model(Xt[va])
                hist.append([ep + 1, tot_loss / 48000, tot_err / 48000,
                             float(nn.functional.cross_entropy(out, gt[va])), float((out.argmax(1) != gt[va]).float().mean())])
        with torch.no_grad():
            test_err = float((model(Xte_t).argmax(1) != gte_t).float().mean())
        return hist, test_err

    res = {}
    torch.manual_seed(0)
    res["dropout_hist"], res["dropout_test"] = train(net((0.4, 0.3)))
    ridge = {}
    for lam in (1e-3, 1e-4, 1e-5):
        torch.manual_seed(0)
        h, te = train(net((0.0, 0.0)), lam=lam)
        ridge[str(lam)] = {"valid_err": h[-1][4], "test": te}
    best = min(ridge, key=lambda k: ridge[k]["valid_err"])
    res["ridge"], res["ridge_lambda"], res["ridge_test"] = ridge, float(best), ridge[best]["test"]
    torch.manual_seed(0)
    mlr = nn.Sequential(nn.Linear(784, 10))
    gen = torch.Generator().manual_seed(0)
    opt = torch.optim.RMSprop(mlr.parameters(), lr=0.001)
    for ep in range(30):
        perm = torch.randperm(48000, generator=gen)
        for s in range(0, 48000, 128):
            idx = perm[s:s + 128]
            opt.zero_grad(); nn.functional.cross_entropy(mlr(Xt[tr][idx]), gt[tr][idx]).backward(); opt.step()
    with torch.no_grad():
        res["mlr_test"] = float((mlr(Xte_t).argmax(1) != gte_t).float().mean())
    from sklearn.discriminant_analysis import LinearDiscriminantAnalysis
    lda = LinearDiscriminantAnalysis(solver="svd").fit(X, g)
    res["lda_test"] = float(np.mean(lda.predict(Xte) != gte))
    os.makedirs(CACHE, exist_ok=True)
    with open(path, "w") as fh:
        json.dump(res, fh)
    return res


def fig_10_18(out=None):
    """Training and validation objective and classification error of the MNIST network, by epoch."""
    h = np.array(mnist_results()["dropout_hist"])
    fig, axes = plt.subplots(1, 2, figsize=(8.4, 3.4))
    for ax, (ktr, kva, lab) in zip(axes, [(1, 3, "Value of Objective Function"), (2, 4, "Classification Error")]):
        ax.plot(h[:, 0], h[:, ktr], color="#3fa7e0", label="Training Set")
        ax.plot(h[:, 0], h[:, kva], color=ORANGE, label="Validation Set")
        ax.set(xlabel="Epochs", ylabel=lab)
    axes[0].legend(frameon=False)
    fig.tight_layout()
    savefig(fig, CH, "fig10-18", out)


# ======================================================================== Hitters: Tables 10.2 and 10.3
def hitters_results():
    path = os.path.join(CACHE, "ch10-hitters.json")
    if os.path.exists(path):
        with open(path) as fh:
            return json.load(fh)
    import statsmodels.api as sm
    torch = common.torch_setup(0, 1)
    nn = torch.nn
    H = common.isl_data("Hitters").dropna().reset_index(drop=True)
    test = np.zeros(len(H), bool)
    test[TESTID - 1] = True
    y = H["Salary"].to_numpy()
    yte = y[test]
    r2 = lambda p: 1 - np.mean((yte - p) ** 2) / yte.var(ddof=1)
    res = {}
    Xlm = sm.add_constant(pd.get_dummies(H.drop(columns="Salary"), drop_first=True, dtype=float))
    lm = sm.OLS(y[~test], Xlm[~test]).fit()
    p = lm.predict(Xlm[test])
    res["lm"] = {"params": int(len(lm.params)), "mae": float(np.mean(np.abs(yte - p))), "r2": float(r2(p))}
    M = hitters_matrix(H)
    X = ((M - M.mean()) / M.std()).to_numpy()
    lambdas, _, _ = lasso_glmnet(X[~test], y[~test])
    fold = np.arange((~test).sum()) % 10
    err = np.zeros(((~test).sum(), len(lambdas)))
    for k in range(10):
        _, b0, B = lasso_glmnet(X[~test][fold != k], y[~test][fold != k], lambdas)
        err[fold == k] = np.abs(y[~test][fold == k, None] - (b0 + X[~test][fold == k] @ B))
    best = int(np.argmin(err.mean(0)))
    _, b0, B = lasso_glmnet(X[~test], y[~test], lambdas)
    p = b0[best] + X[test] @ B[:, best]
    res["lasso"] = {"params": int(np.sum(B[:, best] != 0)), "mae": float(np.mean(np.abs(yte - p))), "r2": float(r2(p)),
                    "lambda": float(lambdas[best])}
    torch.manual_seed(0)
    net = nn.Sequential(nn.Linear(20, 64), nn.ReLU(), nn.Dropout(0.1), nn.Linear(64, 1))
    opt = torch.optim.RMSprop(net.parameters(), lr=0.001)
    Xt, Yt = torch.tensor(X[~test], dtype=torch.float32), torch.tensor(y[~test], dtype=torch.float32)
    gen = torch.Generator().manual_seed(0)
    for _ in range(1000):
        net.train()
        perm = torch.randperm(len(Yt), generator=gen)
        for s in range(0, len(Yt), 32):
            idx = perm[s:s + 32]
            opt.zero_grad(); ((net(Xt[idx]).flatten() - Yt[idx]) ** 2).mean().backward(); opt.step()
    net.eval()
    with torch.no_grad():
        p = net(torch.tensor(X[test], dtype=torch.float32)).flatten().numpy()
    res["nn"] = {"params": int(sum(q.numel() for q in net.parameters())), "mae": float(np.mean(np.abs(yte - p))),
                 "r2": float(r2(p))}
    four = ["Hits", "Walks", "CRuns", "PutOuts"]
    X4 = sm.add_constant(H[four].astype(float))
    f4 = sm.OLS(y[~test], X4[~test]).fit()
    res["relaxed4_mae"] = float(np.mean(np.abs(yte - f4.predict(X4[test]))))
    t3 = sm.OLS(yte, X4[test]).fit()
    res["table_10_3"] = {"coef": t3.params.tolist(), "se": t3.bse.tolist(), "t": t3.tvalues.tolist(),
                         "p": t3.pvalues.tolist()}
    os.makedirs(CACHE, exist_ok=True)
    with open(path, "w") as fh:
        json.dump(res, fh)
    return res


def tables(out=None):
    """Print Tables 10.1, 10.2 and 10.3 (recomputed)."""
    m = mnist_results()
    print("Table 10.1 (MNIST test error): network + ridge (lambda %g) %.2f%%, network + dropout %.2f%%, "
          "multinomial logistic regression %.2f%%, LDA %.2f%%"
          % (m["ridge_lambda"], 100 * m["ridge_test"], 100 * m["dropout_test"], 100 * m["mlr_test"], 100 * m["lda_test"]))
    h = hitters_results()
    print("Table 10.2 (Hitters test set):")
    for k, lab in (("lm", "Linear Regression"), ("lasso", "Lasso"), ("nn", "Neural Network")):
        print("  %-18s parameters %5d  MAE %.1f  R2 %.2f" % (lab, h[k]["params"], h[k]["mae"], h[k]["r2"]))
    print("Relaxed lasso on Hits, Walks, CRuns, PutOuts, fitted on the training data: test MAE %.1f" % h["relaxed4_mae"])
    t = h["table_10_3"]
    print("Table 10.3 (fitted on the test data):")
    for i, lab in enumerate(["Intercept", "Hits", "Walks", "CRuns", "PutOuts"]):
        print("  %-10s %9.3f %8.3f %7.2f %.4f" % (lab, t["coef"][i], t["se"][i], t["t"][i], t["p"][i]))


# ======================================================================== the demonstrations' data
def mulberry32(seed):
    """The seeded generator of the demonstrations (DK.rng in demo-kit.js), bit for bit."""
    state = [seed & 0xFFFFFFFF]

    def imul(a, b):
        return (a * b) & 0xFFFFFFFF

    def u():
        a = (state[0] + 0x6D2B79F5) & 0xFFFFFFFF
        state[0] = a
        t = imul(a ^ (a >> 15), 1 | a)
        t = ((t + imul(t ^ (t >> 7), 61 | t)) & 0xFFFFFFFF) ^ t
        return ((t ^ (t >> 14)) & 0xFFFFFFFF) / 4294967296.0
    return u


def demo_net_init(K, p, seed):
    """Initial weights of the Hitters demonstration: U(-1/sqrt(fan_in), 1/sqrt(fan_in)), drawn in the
    order W1 (row by row, K x p), b1, beta (K), beta0, from mulberry32(seed)."""
    u = mulberry32(seed)
    s1, s2 = 1 / np.sqrt(p), 1 / np.sqrt(K)
    W1 = np.array([[(2 * u() - 1) * s1 for _ in range(p)] for _ in range(K)])
    b1 = np.array([(2 * u() - 1) * s1 for _ in range(K)])
    beta = np.array([(2 * u() - 1) * s2 for _ in range(K)])
    beta0 = (2 * u() - 1) * s2
    return W1, b1, beta, beta0


def demo_net_train(X, y, K, epochs, lr, seed, Xte=None, yte=None, every=50):
    """Full-batch RMSprop (alpha 0.99, eps 1e-8) on the mean squared error, no dropout: the deterministic
    reference run of the Hitters demonstration. Returns (epoch, test MAE, training MAE) every `every` epochs,
    computed after that epoch's update."""
    W1, b1, beta, beta0 = demo_net_init(K, X.shape[1], seed)
    params = [W1, b1, beta, np.array([beta0])]
    V = [np.zeros_like(q) for q in params]
    n, out = len(y), []
    for ep in range(1, epochs + 1):
        Z = X @ W1.T + b1
        A = np.maximum(Z, 0)
        f = A @ beta + beta0
        r = 2 * (f - y) / n                             # dLoss/df for the mean squared error
        g_beta, g_beta0 = A.T @ r, np.array([r.sum()])   # (10.29)
        dZ = np.outer(r, beta) * (Z > 0)                 # (10.30): residual share * beta_k * g'(z_ik)
        grads = [dZ.T @ X, dZ.sum(0), g_beta, g_beta0]
        for q, g, v in zip(params, grads, V):
            v *= 0.99
            v += 0.01 * g * g
            q -= lr * g / (np.sqrt(v) + 1e-8)
        beta0 = params[3][0]
        if Xte is not None and ep % every == 0:
            pte = np.maximum(Xte @ W1.T + b1, 0) @ beta + beta0
            ptr = np.maximum(X @ W1.T + b1, 0) @ beta + beta0
            out.append((ep, float(np.mean(np.abs(pte - yte))), float(np.mean(np.abs(ptr - y)))))
    return out


def demos(out=None):
    os.makedirs(DATA_OUT, exist_ok=True)
    # 1. Hitters network
    H = common.isl_data("Hitters").dropna().reset_index(drop=True)
    test = np.zeros(len(H), bool)
    test[TESTID - 1] = True
    M = hitters_matrix(H)
    X = ((M - M.mean()) / M.std()).to_numpy()
    y = H["Salary"].to_numpy()
    h = hitters_results()
    ref = demo_net_train(X[~test], y[~test], K=50, epochs=1000, lr=0.01, seed=1, Xte=X[test], yte=y[test], every=100)
    J = {"cols": list(M.columns), "X": np.round(X, 6).tolist(), "y": y.tolist(), "test": (TESTID - 1).tolist(),
         "lm_mae": h["lm"]["mae"], "lasso_mae": h["lasso"]["mae"], "lasso_nz": h["lasso"]["params"], "ref": {"K": 50, "lr": 0.01, "seed": 1, "trace": ref}}
    with open(os.path.join(DATA_OUT, "ch10-hitters.json"), "w") as fh:
        json.dump(J, fh, separators=(",", ":"))
    print("Hitters demo: reference full-batch RMSprop (K = 50, lr 0.01, seed 1): test MAE by epoch",
          [(e, round(m, 3)) for e, m, _ in ref])
    # 2. MNIST digits for the convolution demo
    Xm, gm = common.mnist(train=False)
    idx = [int(np.argmax(gm == d)) for d in range(10)] + list(range(10, 30))
    imgs = (Xm[idx] * 255).round().astype(int)
    filt = stripe_filter(3, True)
    conv = conv2d_valid(np.pad(imgs[0].reshape(28, 28) / 255, 1), filt)
    pooled = max_pool(np.maximum(conv, 0))
    with open(os.path.join(DATA_OUT, "ch10-digits.json"), "w") as fh:
        json.dump({"labels": gm[idx].tolist(), "pixels": imgs.tolist()}, fh, separators=(",", ":"))
    print("conv demo: digit %d, 3x3 vertical stripe, same padding: conv sum %.4f, max %.4f; pooled sum %.4f"
          % (gm[idx[0]], conv.sum(), conv.max(), pooled.sum()))
    # 3. double descent
    sets = []
    for s in (SEED_DD, 13, 17, 25, 1):
        x, yy = dd_data(s)
        c = dd_curve(x, yy)
        sets.append({"seed": int(s), "x": np.round(x, 10).tolist(), "y": np.round(yy, 10).tolist()})
        if s == SEED_DD:
            print("double descent (seed %d): test error at d = 8, 20, 42, 80:" % s,
                  np.round(c[[6, 18, 40, 78], 2], 4), " norms", np.round(c[[6, 18, 40, 78], 3], 3))
    with open(os.path.join(DATA_OUT, "ch10-double-descent.json"), "w") as fh:
        json.dump({"sigma": SIGMA_DD, "sets": sets, "median": np.round(dd_median(), 5).tolist()}, fh, separators=(",", ":"))


FIGURES = {
    "10.2": fig_10_2, "10.3": fig_10_3, "10.7": fig_10_7, "10.9": fig_10_9, "10.14": fig_10_14, "10.15": fig_10_15,
    "10.16": fig_10_16, "10.17": fig_10_17, "10.18": fig_10_18, "10.20": fig_10_20, "10.21": fig_10_21,
    "ex6": fig_ex6, "tables": tables, "demos": demos,
}

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