"""James et al. (2021, 2023), Chapter 2: Statistical Learning.

Reproduces the figures of Chapter 2 of G. James, D. Witten, T. Hastie and R. Tibshirani, An
Introduction to Statistical Learning with Applications in R, 2nd edition (Springer, 2021), and of the
Python edition with J. Taylor (Springer, 2023), which share the chapter. Written from scratch with
numpy, scipy and matplotlib, to be read next to the lecture notes (../ch02-statistical-learning.html):

* Section 2.1: the Advertising data with simple least-squares lines (Figure 2.1); the Income data
  with a smooth stand-in for the unknown true f (Figures 2.2 and 2.3), a least-squares plane (Figure
  2.4) and two thin-plate splines, one smooth and one interpolating (Figures 2.5 and 2.6,
  `thin_plate_fit`); three simulated groups for clustering (Figure 2.8).
* Section 2.2.1-2.2.2: a cubic smoothing spline written out in full (`reinsch_matrices`,
  `spline_eval_matrix`, `SmoothingSpline`: the Reinsch form g = (I + lambda K)^(-1) y, the degrees of
  freedom tr S, the natural cubic spline between the knots), and the exact expected training MSE,
  test MSE, squared bias and variance of a linear smoother with a fixed design (`exact_curves`) for
  the three simulated examples of Figures 2.9-2.12.
* Section 2.2.3: a two-class Gaussian-mixture simulation with a known Bayes classifier
  (`bayes_prob`, `bayes_error`), K-nearest neighbours (`knn_cumcounts`, `knn_predict`,
  `knn_error_curve`) and Figures 2.13-2.17.
* Exercise 2.3: the five curves of the sketch, computed exactly for the first example (fig2-S1).
* `--fig data` writes the JSON used by the three demonstrations (../data/ch02-*.json).

Figures reproduced: 2.1, 2.2, 2.3, 2.4, 2.5, 2.6, 2.8, 2.9, 2.10, 2.11, 2.12, 2.13, 2.14, 2.15,
2.16, 2.17 and the Exercise 2.3 sketch. Skipped: Figure 2.7 (a schematic of flexibility against
interpretability with method names placed by hand; it is not computed from anything; the notes give
the same information as a table).

Settings chosen where the book gives none (the book's simulations are not published):
* Figures 2.2-2.3: the Income data are simulated by the authors, who do not publish the true f. As a
  stand-in, Figure 2.2 uses the logistic curve a + b / (1 + exp(-(x - c) / s)) fitted by least squares
  to Income1, and Figure 2.3 the surface a + b / (1 + exp(-(edu - c) / s)) + d * seniority fitted to
  Income2.
* Figures 2.5-2.6: thin-plate splines (scipy RBFInterpolator, kernel thin_plate_spline, linear
  part) on inputs rescaled to [0, 1]; the smooth fit uses the smoothing value chosen by generalised
  cross-validation, the rough one smoothing 0 (interpolation).
* Figure 2.8: 50 points around each of three centres, standard deviation 1 (left) and 1.6 (right).
* Figures 2.9-2.12: n = 50 inputs on [0, 100], one in the middle 70% of each of 50 equal bins (numpy
  seed 2021), kept fixed; Y = f(X) + eps with Var(eps) = 1. The three true functions are polynomials
  in u = X/100 (TRUTHS below) shaped like the book's black curves. Test MSE is the expected squared
  error at a new input uniform on [0, 100] (500 equally spaced points), computed exactly, so it is
  Var(eps) + bias^2 + variance as in (2.7). Flexibility is the degrees of freedom tr S of the
  smoothing spline, from 2 (the least-squares line) to 30.
* Figures 2.13-2.17: each class is an equal mixture of ten Gaussians N(m_k, 0.2 I); the BLUE centres
  are N((1, 0), I) and the ORANGE centres N((0, 1), I) draws (numpy seed 40, chosen so that the Bayes
  error rate is close to the book's 0.133). Training set: 100 points per class (seed 15); test set:
  2,500 per class (seed 99). All coordinates rounded to 4 decimals. K-NN uses Euclidean distance,
  ties in distance go to the lower-numbered training point, and a vote of exactly one half goes to the
  class of the nearest neighbour.

Run `python3 ch02_statistical_learning.py --list`, `python3 ch02_statistical_learning.py` (all
figures and the demonstration data, under a minute) or `python3 ch02_statistical_learning.py --fig 2.9`.
Files go to ../img/ch02/.
"""
import json
import os

import numpy as np
from scipy.interpolate import RBFInterpolator
from scipy.optimize import curve_fit, minimize_scalar

import common
from common import BLUE, GREEN, GREY, ORANGE, PURPLE, RED, savefig
import matplotlib.pyplot as plt

CH = 2
HERE = os.path.dirname(os.path.abspath(__file__))
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
SKY = "#29a3d6"          # the book's light blue (smoothing spline / training error)
TEAL = "#119c8a"         # the book's green (most flexible fit)
BOOK_ORANGE = "#e69f00"
CLASS_BLUE = "#1f5fbf"
CLASS_ORANGE = "#f08a00"


# =========================================================================== 2.2.1: smoothing splines
def reinsch_matrices(t):
    """Matrices of the Reinsch form of a natural cubic spline with knots t (sorted, distinct).

    Q is n x (n-2) and R is (n-2) x (n-2) tridiagonal (Green and Silverman 1994, Section 2.1); a vector
    g of values at the knots defines a natural cubic spline whose second derivatives at the interior
    knots are gamma = R^(-1) Q^T g, and whose roughness is  int g''(x)^2 dx = g^T K g  with
    K = Q R^(-1) Q^T. Returns K and M = R^(-1) Q^T.
    """
    t = np.asarray(t, float)
    n = len(t)
    h = np.diff(t)
    Q = np.zeros((n, n - 2))
    R = np.zeros((n - 2, n - 2))
    for j in range(1, n - 1):
        c = j - 1
        Q[j - 1, c] = 1.0 / h[j - 1]
        Q[j, c] = -1.0 / h[j - 1] - 1.0 / h[j]
        Q[j + 1, c] = 1.0 / h[j]
        R[c, c] = (h[j - 1] + h[j]) / 3.0
        if c + 1 < n - 2:
            R[c, c + 1] = R[c + 1, c] = h[j] / 6.0
    M = np.linalg.solve(R, Q.T)
    return Q @ M, M


def spline_eval_matrix(t, M, x0):
    """Matrix A with  g(x0) = A @ g  for the natural cubic spline through the values g at the knots t
    (linear beyond the boundary knots)."""
    t = np.asarray(t, float)
    n = len(t)
    h = np.diff(t)
    G = np.vstack([np.zeros(n), M, np.zeros(n)])      # second derivatives at all n knots
    A = np.zeros((len(x0), n))
    for r, x in enumerate(np.asarray(x0, float)):
        if x <= t[0]:
            d = x - t[0]                                # g(t1) + d g'(t1), g'(t1) = (g2 - g1)/h1 - h1 gamma2 / 6
            A[r, 0] += 1 - d / h[0]
            A[r, 1] += d / h[0]
            A[r] += -d * h[0] / 6 * G[1]
        elif x >= t[-1]:
            d = x - t[-1]                               # g'(tn) = (gn - g_{n-1})/h + h gamma_{n-1} / 6
            A[r, -1] += 1 + d / h[-1]
            A[r, -2] += -d / h[-1]
            A[r] += d * h[-1] / 6 * G[n - 2]
        else:
            i = min(int(np.searchsorted(t, x, side="right")) - 1, n - 2)
            a, b, hh = x - t[i], t[i + 1] - x, h[i]
            A[r, i] += b / hh
            A[r, i + 1] += a / hh
            A[r] += -a * b / 6 * ((1 + a / hh) * G[i + 1] + (1 + b / hh) * G[i])
    return A


class SmoothingSpline:
    """Cubic smoothing spline with knots at the (distinct, sorted) inputs x.

    It minimises  sum_i (y_i - g(x_i))^2 + lambda int g''(t)^2 dt  over all functions g; the solution
    is the natural cubic spline with values  g = S y,  S = (I + lambda K)^(-1)  at the knots. With the
    eigen-decomposition K = U diag(d) U^T,  S = U diag(1 / (1 + lambda d)) U^T  and the degrees of
    freedom are  tr S = sum_k 1 / (1 + lambda d_k), which falls from n (lambda = 0, interpolation) to 2
    (lambda -> infinity: two eigenvalues are 0, and the fit is the least-squares line).
    """

    def __init__(self, x):
        self.x = np.asarray(x, float)
        self.n = len(self.x)
        self.K, self.M = reinsch_matrices(self.x)
        d, U = np.linalg.eigh(self.K)
        d[:2] = 0.0                                     # the two exact zeros (constant and linear)
        self.d, self.U = d, U
        X1 = np.column_stack([np.ones(self.n), self.x])
        self.H_line = X1 @ np.linalg.solve(X1.T @ X1, X1.T)

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

    def lam_for_df(self, df):
        """lambda with tr S = df (bisection on log lambda); None means the least-squares line."""
        if df <= 2.0 + 1e-9:
            return None
        lo, hi = -40.0, 40.0
        for _ in range(200):
            mid = 0.5 * (lo + hi)
            if self.df(np.exp(mid)) > df:
                lo = mid
            else:
                hi = mid
        return float(np.exp(0.5 * (lo + hi)))

    def smoother(self, df):
        lam = self.lam_for_df(df)
        if lam is None:
            return self.H_line
        return (self.U * (1.0 / (1.0 + lam * self.d))) @ self.U.T

    def fit(self, y, df):
        return self.smoother(df) @ np.asarray(y, float)


# =========================================================================== 2.2: the three simulated examples
N_REG = 50
SIGMA2 = 1.0
GRID_M = 500
X_GRID = (np.arange(GRID_M) + 0.5) / GRID_M * 100.0     # the "very large test set" of inputs
# polynomials in u = x / 100, highest power first (numpy.polyval order), rounded so that the browser
# demonstrations evaluate exactly the same functions
_ANCHORS = {
    1: ([(0, 4.5), (15, 4.8), (30, 6.0), (50, 7.9), (70, 9.4), (85, 8.6), (100, 6.2)], 4),
    3: ([(0, 26), (10, 19), (25, 13), (40, 12.3), (55, 13), (65, 13.6), (80, 8), (90, 2), (100, -10)], 5),
}
TRUTHS = {}
for _k, (_pts, _deg) in _ANCHORS.items():
    _p = np.array(_pts, float)
    TRUTHS[_k] = [round(float(c), 6) for c in np.polyfit(_p[:, 0] / 100, _p[:, 1], _deg)]
# Example 2 is close to linear: 2.4 + 9.5 u plus the gentle bend 4.8 u (2u - 1)(u - 1), a cubic in u
TRUTHS[2] = [9.6, -14.4, 14.3, 2.4]
DF_FITS = {1: (2, 5.4, 25), 2: (2, 3.4, 25), 3: (2, 8.7, 25)}   # the three fits drawn in each left panel


def truth(example, x):
    return np.polyval(TRUTHS[example], np.asarray(x, float) / 100.0)


def design_x(n=N_REG, seed=2021):
    """One input in the middle 70% of each of n equal bins of [0, 100], rounded to 4 decimals."""
    rng = np.random.default_rng(seed)
    u = rng.uniform(size=n)
    return np.round(100.0 * (np.arange(n) + 0.5 + 0.7 * (u - 0.5)) / n, 4)


def training_sample(example, x, seed=None):
    rng = np.random.default_rng(100 + example if seed is None else seed)
    return np.round(truth(example, x) + rng.normal(scale=np.sqrt(SIGMA2), size=len(x)), 4)


_SETUP = {}


def regression_setup():
    """The fixed design, its smoothing-spline machinery and the evaluation matrix on the test grid."""
    if not _SETUP:
        x = design_x()
        ss = SmoothingSpline(x)
        A = spline_eval_matrix(x, ss.M, X_GRID)
        _SETUP.update(x=x, ss=ss, A=A)
    return _SETUP


def exact_curves(example, dfs):
    """Exact expectations over the noise, with the design fixed, for a smoothing spline with each df:
    training MSE (1/n)(||(I-S)f||^2 + sigma^2 tr((I-S)^T (I-S))), and at a new input X0 uniform on the
    grid the squared bias Ave(E fhat(x0) - f(x0))^2, the variance sigma^2 Ave ||l(x0)||^2 and the test
    MSE sigma^2 + bias^2 + variance."""
    st = regression_setup()
    x, ss, A = st["x"], st["ss"], st["A"]
    F, F0 = truth(example, x), truth(example, X_GRID)
    n = len(x)
    out = {k: [] for k in ("train", "test", "bias2", "var")}
    for df in dfs:
        S = ss.smoother(df)
        L = A @ S
        R = np.eye(n) - S
        out["train"].append((np.sum((R @ F) ** 2) + SIGMA2 * np.sum(R * R)) / n)
        b2 = float(np.mean((L @ F - F0) ** 2))
        v = float(SIGMA2 * np.mean(np.sum(L * L, axis=1)))
        out["bias2"].append(b2)
        out["var"].append(v)
        out["test"].append(SIGMA2 + b2 + v)
    return {k: np.array(v) for k, v in out.items()}


def sample_mse(example, y, df):
    """Training MSE of one fit, and its test MSE on a very large test set: with new responses
    y0 = f(x0) + eps, Ave (y0 - fhat(x0))^2 tends to sigma^2 + Ave (fhat(x0) - f(x0))^2."""
    st = regression_setup()
    S = st["ss"].smoother(df)
    g = S @ y
    train = float(np.mean((y - g) ** 2))
    test = float(SIGMA2 + np.mean((st["A"] @ g - truth(example, X_GRID)) ** 2))
    return train, test


DF_CURVE = np.exp(np.linspace(np.log(2.0), np.log(30.0), 121))


def best_df(example):
    dfs = np.exp(np.linspace(np.log(2.0), np.log(30.0), 1201))
    te = exact_curves(example, dfs)["test"]
    k = int(np.argmin(te))
    return float(dfs[k]), float(te[k])


# =========================================================================== 2.2.3: the classification simulation
S2_CLS = 0.2


def mixture_means(seed=40):
    rng = np.random.default_rng(seed)
    mb = rng.normal(size=(10, 2)) + [1.0, 0.0]
    mo = rng.normal(size=(10, 2)) + [0.0, 1.0]
    return np.round(mb, 4), np.round(mo, 4)


def mixture_sample(n_per_class, seed):
    """n points per class; y = 0 for BLUE, 1 for ORANGE."""
    mb, mo = mixture_means()
    rng = np.random.default_rng(seed)

    def draw(M):
        k = rng.integers(0, 10, n_per_class)
        return M[k] + rng.normal(scale=np.sqrt(S2_CLS), size=(n_per_class, 2))
    X = np.vstack([draw(mb), draw(mo)])
    y = np.r_[np.zeros(n_per_class, int), np.ones(n_per_class, int)]
    return np.round(X, 4), y


def class_data():
    Xtr, ytr = mixture_sample(100, 15)
    Xte, yte = mixture_sample(2500, 99)
    return Xtr, ytr, Xte, yte


def _mix_density(P, M):
    P = np.atleast_2d(P)
    d2 = ((P[:, None, :] - M[None, :, :]) ** 2).sum(-1)
    return np.exp(-d2 / (2 * S2_CLS)).sum(1) / (len(M) * 2 * np.pi * S2_CLS)


def bayes_prob(P):
    """Pr(Y = ORANGE | X = x) under the known model (equal class probabilities)."""
    mb, mo = mixture_means()
    fb, fo = _mix_density(P, mb), _mix_density(P, mo)
    return fo / (fb + fo)


def bayes_error(m=1600, pad=3.5):
    """Bayes error rate (2.11), 1 - E max_j Pr(Y = j | X) = int min(f_BLUE, f_ORANGE) / 2 dx,
    by the midpoint rule on an m x m grid."""
    mb, mo = mixture_means()
    allm = np.vstack([mb, mo])
    lo, hi = allm.min(0) - pad, allm.max(0) + pad
    gx = lo[0] + (np.arange(m) + 0.5) * (hi[0] - lo[0]) / m
    gy = lo[1] + (np.arange(m) + 0.5) * (hi[1] - lo[1]) / m
    cell = (hi[0] - lo[0]) * (hi[1] - lo[1]) / m ** 2
    tot = 0.0
    for j in range(0, m, 200):                         # in strips, to keep memory small
        P = np.array(np.meshgrid(gx, gy[j:j + 200])).reshape(2, -1).T
        tot += np.minimum(_mix_density(P, mb), _mix_density(P, mo)).sum() / 2
    return float(tot * cell)


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


def knn_cumcounts(Xtr, ytr, Xq):
    """Running number of ORANGE among the 1, 2, ..., N nearest training points of each query point."""
    o = knn_order(Xtr, Xq)
    return np.cumsum(ytr[o], axis=1), o


def knn_predict(Xtr, ytr, Xq, K):
    """K-nearest-neighbour classifier (2.12): ORANGE if the fraction of ORANGE among the K nearest
    points exceeds 1/2, BLUE if it is below; an exact tie goes to the nearest neighbour's class."""
    c, o = knn_cumcounts(Xtr, ytr, Xq)
    p = c[:, K - 1] / K
    return np.where(p > 0.5, 1, np.where(p < 0.5, 0, ytr[o[:, 0]])), p


def knn_error_curve(Xtr, ytr, Xq, yq, Kmax=100):
    """Misclassification rate of K-NN on (Xq, yq) for K = 1, ..., Kmax (index K - 1)."""
    c, o = knn_cumcounts(Xtr, ytr, Xq)
    nn = ytr[o[:, 0]]
    err = []
    for K in range(1, Kmax + 1):
        p = c[:, K - 1] / K
        pred = np.where(p > 0.5, 1, np.where(p < 0.5, 0, nn))
        err.append(float(np.mean(pred != yq)))
    return np.array(err)


CLS_BOX = (-2.2, 3.4, -2.0, 3.2)                       # plotting window (x0, x1, y0, y1)


def _class_grid(ng=161):
    x0, x1, y0, y1 = CLS_BOX
    gx, gy = np.linspace(x0, x1, ng), np.linspace(y0, y1, ng)
    P = np.array(np.meshgrid(gx, gy)).reshape(2, -1).T
    return gx, gy, P


# the small example of Figure 2.14: six BLUE and six ORANGE points and a test point
TOY_X = np.array([[0.66, 0.24], [0.80, 0.42], [0.48, 0.12], [0.88, 0.18], [0.35, 0.40], [0.70, 0.62],
                  [0.20, 0.82], [0.40, 0.66], [0.12, 0.55], [0.55, 0.88], [0.80, 0.86], [0.18, 0.25]])
TOY_Y = np.array([0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1])
TOY_CROSS = np.array([0.50, 0.50])


# =========================================================================== demonstration data
def export_demo_data(out=None):
    """JSON for the browser demonstrations (courses/isl/data/ch02-*.json)."""
    os.makedirs(DATA_OUT, exist_ok=True)
    st = regression_setup()
    reg = dict(x=st["x"].tolist(), sigma2=SIGMA2, grid_m=GRID_M, truths={str(k): v for k, v in TRUTHS.items()},
               y={str(k): training_sample(k, st["x"]).tolist() for k in (1, 2, 3)},
               df_fits={str(k): list(v) for k, v in DF_FITS.items()})
    with open(os.path.join(DATA_OUT, "ch02-flexibility.json"), "w") as f:
        json.dump(reg, f, separators=(",", ":"))
    Xtr, ytr, Xte, yte = class_data()
    mb, mo = mixture_means()
    cls = dict(s2=S2_CLS, means_blue=mb.tolist(), means_orange=mo.tolist(), x=Xtr.tolist(), y=ytr.tolist(),
               xtest=Xte.tolist(), ytest=yte.tolist(), bayes_rate=round(bayes_error(), 6), box=list(CLS_BOX),
               toy_x=TOY_X.tolist(), toy_y=TOY_Y.tolist(), toy_cross=TOY_CROSS.tolist())
    with open(os.path.join(DATA_OUT, "ch02-classification.json"), "w") as f:
        json.dump(cls, f, separators=(",", ":"))
    print("wrote ../data/ch02-flexibility.json and ../data/ch02-classification.json")


# =========================================================================== figures: Section 2.1
def _ls_line(x, y):
    b1 = np.sum((x - x.mean()) * (y - y.mean())) / np.sum((x - x.mean()) ** 2)
    return y.mean() - b1 * x.mean(), b1


def fig_2_1(out_dir=None):
    """Advertising: sales against TV, radio and newspaper budgets, with least-squares lines."""
    adv = common.isl_data("Advertising", index_col=0)
    fig, axes = common.panel_grid(1, 3, size=(2.9, 2.7))
    for ax, col, lab in zip(axes[0], ["TV", "radio", "newspaper"], ["TV", "Radio", "Newspaper"]):
        x, y = adv[col].to_numpy(), adv["sales"].to_numpy()
        b0, b1 = _ls_line(x, y)
        ax.scatter(x, y, s=12, facecolors="none", edgecolors=RED, linewidths=0.8)
        xx = np.linspace(x.min(), x.max(), 2)
        ax.plot(xx, b0 + b1 * xx, color=BLUE, lw=2.2)
        ax.set_xlabel(lab)
        ax.set_ylabel("Sales")
        ax.set_title("slope %.4f" % b1, fontsize=9)
    fig.tight_layout()
    savefig(fig, CH, "fig2-1", out_dir)


def _logistic(x, a, b, c, s):
    return a + b / (1 + np.exp(-(x - c) / s))


def income1_truth():
    d = common.isl_data("Income1", index_col=0)
    x, y = d["Education"].to_numpy(), d["Income"].to_numpy()
    p, _ = curve_fit(_logistic, x, y, p0=[20, 60, 16, 1.5])
    return x, y, p


def fig_2_2(out_dir=None):
    """Income1: income against years of education, and a smooth stand-in for f with the errors."""
    x, y, p = income1_truth()
    xx = np.linspace(10, 22, 300)
    fig, axes = common.panel_grid(1, 2, size=(3.4, 3.0))
    for k, ax in enumerate(axes[0]):
        if k == 1:
            ax.vlines(x, y, _logistic(x, *p), color="black", lw=0.8)
            ax.plot(xx, _logistic(xx, *p), color=BLUE, lw=2)
        ax.scatter(x, y, s=14, color=RED, zorder=3)
        ax.set_xlabel("Years of Education")
        ax.set_ylabel("Income")
    fig.tight_layout()
    savefig(fig, CH, "fig2-2", out_dir)


def _surface_model(X, a, b, c, s, d):
    edu, sen = X
    return a + b / (1 + np.exp(-(edu - c) / s)) + d * sen


def income2():
    d = common.isl_data("Income2", index_col=0)
    return d["Education"].to_numpy(), d["Seniority"].to_numpy(), d["Income"].to_numpy()


def income2_truth():
    edu, sen, y = income2()
    p, _ = curve_fit(_surface_model, (edu, sen), y, p0=[20, 60, 16, 2, 0.2], maxfev=20000)
    return p


def income2_plane():
    edu, sen, y = income2()
    X = np.column_stack([np.ones_like(edu), edu, sen])
    beta = np.linalg.lstsq(X, y, rcond=None)[0]
    return beta


_E_RANGE, _S_RANGE = (10.0, 22.0), (20.0, 190.0)


def _scale_inputs(edu, sen):
    return np.column_stack([(edu - _E_RANGE[0]) / (_E_RANGE[1] - _E_RANGE[0]),
                            (sen - _S_RANGE[0]) / (_S_RANGE[1] - _S_RANGE[0])])


def thin_plate_fit(smoothing):
    """Thin-plate spline (with a linear part) of Income on (Education, Seniority) rescaled to [0, 1].
    Returns the fitted interpolator, the smoother matrix H (fitted values = H y) and tr H."""
    edu, sen, y = income2()
    Z = _scale_inputs(edu, sen)
    f = RBFInterpolator(Z, y, kernel="thin_plate_spline", smoothing=smoothing, degree=1)
    n = len(y)
    H = np.column_stack([RBFInterpolator(Z, np.eye(n)[:, j], kernel="thin_plate_spline", smoothing=smoothing,
                                         degree=1)(Z) for j in range(n)])
    return f, H, float(np.trace(H))


def thin_plate_gcv():
    """Smoothing value minimising GCV = n RSS / (n - tr H)^2 (searched on log10 scale)."""
    edu, sen, y = income2()
    n = len(y)

    def gcv(ls):
        _, H, tr = thin_plate_fit(10.0 ** ls)
        r = y - H @ y
        return n * np.sum(r ** 2) / (n - tr) ** 2
    res = minimize_scalar(gcv, bounds=(-6, 2), method="bounded", options={"xatol": 1e-4})
    return 10.0 ** res.x


def _surface_axes(fig, pos):
    ax = fig.add_subplot(pos, projection="3d")
    ax.set_xlabel("Years of Education", fontsize=8, labelpad=-2)
    ax.set_ylabel("Seniority", fontsize=8, labelpad=-2)
    ax.set_zlabel("Income", fontsize=8, labelpad=-4)
    ax.tick_params(labelsize=6, pad=-1)
    ax.view_init(elev=22, azim=-128)
    return ax


def _surface_figure(zfun, colour, name, out_dir, segments=True):
    edu, sen, y = income2()
    ge, gs = np.linspace(*_E_RANGE, 26), np.linspace(*_S_RANGE, 26)
    E, S = np.meshgrid(ge, gs)
    Z = zfun(E.ravel(), S.ravel()).reshape(E.shape)
    fig = plt.figure(figsize=(4.4, 3.9))
    ax = _surface_axes(fig, 111)
    ax.plot_surface(E, S, Z, color=colour, alpha=0.55, edgecolor="#555555", linewidth=0.25, shade=False)
    if segments:
        zf = zfun(edu, sen)
        for a, b, c, d in zip(edu, sen, y, zf):
            ax.plot([a, a], [b, b], [c, d], color="black", lw=0.6)
    ax.scatter(edu, sen, y, color=RED, s=10, depthshade=False)
    fig.subplots_adjust(left=0, right=0.97, bottom=0.02, top=1)
    savefig(fig, CH, name, out_dir)


def fig_2_3(out_dir=None):
    """Income2: a smooth stand-in for the true surface f(education, seniority), with the data."""
    p = income2_truth()
    _surface_figure(lambda e, s: _surface_model((e, s), *p), BLUE, "fig2-3", out_dir)


def fig_2_4(out_dir=None):
    """Income2: the least-squares plane income ~ education + seniority."""
    b = income2_plane()
    _surface_figure(lambda e, s: b[0] + b[1] * e + b[2] * s, "#f2d64b", "fig2-4", out_dir)


def fig_2_5(out_dir=None):
    """Income2: a smooth thin-plate spline (smoothing chosen by GCV)."""
    f, _, _ = thin_plate_fit(thin_plate_gcv())
    _surface_figure(lambda e, s: f(_scale_inputs(np.asarray(e), np.asarray(s))), "#f2d64b", "fig2-5", out_dir)


def fig_2_6(out_dir=None):
    """Income2: a rough (interpolating) thin-plate spline, with zero training error."""
    f, _, _ = thin_plate_fit(0.0)
    _surface_figure(lambda e, s: f(_scale_inputs(np.asarray(e), np.asarray(s))), "#f2d64b", "fig2-6", out_dir)


def cluster_data(sd, seed=8):
    rng = np.random.default_rng(seed)
    centres = np.array([[3.0, 3.0], [7.5, 9.0], [10.5, 4.0]])
    return np.vstack([c + sd * rng.normal(size=(50, 2)) for c in centres]), np.repeat([0, 1, 2], 50)


def fig_2_8(out_dir=None):
    """Clustering: three groups, well separated (left) and overlapping (right)."""
    fig, axes = common.panel_grid(1, 2, size=(3.2, 3.0))
    marks = [("o", "#1f5fbf"), ("^", "#2ca02c"), ("s", "#f08a00")]
    for ax, sd in zip(axes[0], (0.9, 1.7)):
        X, g = cluster_data(sd)
        for k, (m, c) in enumerate(marks):
            ax.scatter(X[g == k, 0], X[g == k, 1], marker=m, s=16, facecolors="none", edgecolors=c, linewidths=0.9)
        ax.set_xlabel("$X_1$")
        ax.set_ylabel("$X_2$")
    fig.tight_layout()
    savefig(fig, CH, "fig2-8", out_dir)


# =========================================================================== figures: Section 2.2
def _flex_axis(ax):
    ax.set_xscale("log")
    ax.set_xticks([2, 5, 10, 20])
    ax.set_xticklabels(["2", "5", "10", "20"])
    ax.set_xlim(1.8, 33)
    ax.set_xlabel("Flexibility")


def _fig_flex(example, name, out_dir):
    st = regression_setup()
    x, ss, A = st["x"], st["ss"], st["A"]
    y = training_sample(example, x)
    cur = exact_curves(example, DF_CURVE)
    fig, axes = common.panel_grid(1, 2, size=(3.4, 3.1))
    ax = axes[0, 0]
    ax.scatter(x, y, s=14, facecolors="none", edgecolors="#444444", linewidths=0.8)
    ax.plot(X_GRID, truth(example, X_GRID), color="black", lw=2)
    cols = [BOOK_ORANGE, SKY, TEAL]
    for df, c in zip(DF_FITS[example], cols):
        ax.plot(X_GRID, A @ ss.fit(y, df), color=c, lw=1.6)
    ax.set_xlabel("X")
    ax.set_ylabel("Y")
    ax = axes[0, 1]
    ax.plot(DF_CURVE, cur["train"], color="#9aa7c0", lw=1.8, label="training MSE (expected)")
    ax.plot(DF_CURVE, cur["test"], color=RED, lw=1.8, label="test MSE (expected)")
    ax.axhline(SIGMA2, color=GREY, ls="--", lw=1)
    for df, c in zip(DF_FITS[example], cols):
        tr, te = sample_mse(example, y, df)
        ax.plot([df, df], [tr, te], "s", color=c, ms=6)
    _flex_axis(ax)
    ax.set_ylabel("Mean Squared Error")
    ax.set_ylim(bottom=0)
    fig.tight_layout()
    savefig(fig, CH, name, out_dir)


def fig_2_9(out_dir=None):
    """Example 1 (a non-linear f): fits of increasing flexibility and the training and test MSE."""
    _fig_flex(1, "fig2-9", out_dir)


def fig_2_10(out_dir=None):
    """Example 2 (f close to linear): as Figure 2.9."""
    _fig_flex(2, "fig2-10", out_dir)


def fig_2_11(out_dir=None):
    """Example 3 (f far from linear): as Figure 2.9."""
    _fig_flex(3, "fig2-11", out_dir)


def fig_2_12(out_dir=None):
    """Squared bias, variance, Var(eps) and test MSE for the three examples (exact, fixed design)."""
    fig, axes = common.panel_grid(1, 3, size=(2.9, 2.8))
    for ax, ex in zip(axes[0], (1, 2, 3)):
        cur = exact_curves(ex, DF_CURVE)
        ax.plot(DF_CURVE, cur["test"], color=RED, lw=1.8, label="MSE")
        ax.plot(DF_CURVE, cur["bias2"], color=SKY, lw=1.8, label="Bias$^2$")
        ax.plot(DF_CURVE, cur["var"], color=BOOK_ORANGE, lw=1.8, label="Var")
        ax.axhline(SIGMA2, color=GREY, ls="--", lw=1)
        ax.axvline(best_df(ex)[0], color="black", ls=":", lw=1)
        _flex_axis(ax)
        ax.set_ylim(bottom=0)
    axes[0, 0].legend(frameon=False, fontsize=8, loc="upper right")
    fig.tight_layout()
    savefig(fig, CH, "fig2-12", out_dir)


def fig_ex2_3(out_dir=None):
    """Exercise 2.3: the five curves of the sketch, computed exactly for Example 1."""
    cur = exact_curves(1, DF_CURVE)
    fig, ax = plt.subplots(figsize=(4.6, 3.3))
    ax.plot(DF_CURVE, cur["test"], color=RED, lw=2, label="test error (expected)")
    ax.plot(DF_CURVE, cur["train"], color="#9aa7c0", lw=2, label="training error (expected)")
    ax.plot(DF_CURVE, cur["bias2"], color=SKY, lw=2, label="squared bias")
    ax.plot(DF_CURVE, cur["var"], color=BOOK_ORANGE, lw=2, label="variance")
    ax.axhline(SIGMA2, color=GREY, ls="--", lw=1.2, label="irreducible error Var($\\varepsilon$)")
    _flex_axis(ax)
    ax.set_ylabel("Mean squared error")
    ax.set_ylim(0, 2.2)
    ax.legend(frameon=False, fontsize=8, loc="upper center", ncol=2)
    fig.tight_layout()
    savefig(fig, CH, "fig2-S1", out_dir)


def _class_panel(ax, Xtr, ytr, prob_grid=None, boundary=None, bayes=True, dots=True):
    gx, gy, P = _class_grid()
    ng = len(gx)
    if dots and prob_grid is not None:
        sub = slice(None, None, 4)
        GX, GY = np.meshgrid(gx[sub], gy[sub])
        pg = prob_grid.reshape(ng, ng)[sub, sub]
        ax.scatter(GX[pg > 0.5], GY[pg > 0.5], s=0.6, color=CLASS_ORANGE, alpha=0.7, lw=0)
        ax.scatter(GX[pg <= 0.5], GY[pg <= 0.5], s=0.6, color=CLASS_BLUE, alpha=0.7, lw=0)
    if boundary is not None:
        ax.contour(gx, gy, boundary.reshape(ng, ng), levels=[0.5], colors="black", linewidths=1.4)
    if bayes:
        ax.contour(gx, gy, bayes_prob(P).reshape(ng, ng), levels=[0.5], colors=PURPLE, linewidths=1.4,
                   linestyles="dashed")
    ax.scatter(Xtr[ytr == 1, 0], Xtr[ytr == 1, 1], s=14, facecolors="none", edgecolors=CLASS_ORANGE, linewidths=0.9)
    ax.scatter(Xtr[ytr == 0, 0], Xtr[ytr == 0, 1], s=14, facecolors="none", edgecolors=CLASS_BLUE, linewidths=0.9)
    ax.set_xlim(CLS_BOX[0], CLS_BOX[1])
    ax.set_ylim(CLS_BOX[2], CLS_BOX[3])
    ax.set_xticks([])
    ax.set_yticks([])
    ax.set_xlabel("$X_1$")
    ax.set_ylabel("$X_2$")


def fig_2_13(out_dir=None):
    """The simulated two-class data, the Bayes decision boundary and the Bayes classifier's regions."""
    Xtr, ytr, _, _ = class_data()
    _, _, P = _class_grid()
    fig, ax = plt.subplots(figsize=(4.0, 3.8))
    _class_panel(ax, Xtr, ytr, prob_grid=bayes_prob(P))
    fig.tight_layout()
    savefig(fig, CH, "fig2-13", out_dir)


def _knn_grid(K):
    Xtr, ytr, _, _ = class_data()
    _, _, P = _class_grid()
    pred, p = knn_predict(Xtr, ytr, P, K)
    return pred.astype(float)


def fig_2_14(out_dir=None):
    """K = 3 on six BLUE and six ORANGE points: the neighbourhood of a test point, and the K-NN regions."""
    fig, axes = common.panel_grid(1, 2, size=(3.1, 3.1))
    o = knn_order(TOY_X, TOY_CROSS[None, :])[0]
    r = np.sqrt(((TOY_X[o[2]] - TOY_CROSS) ** 2).sum()) + 0.012
    ng = 241
    g = np.linspace(0, 1, ng)
    P = np.array(np.meshgrid(g, g)).reshape(2, -1).T
    pred, _ = knn_predict(TOY_X, TOY_Y, P, 3)
    for k, ax in enumerate(axes[0]):
        if k == 0:
            ax.add_patch(plt.Circle(TOY_CROSS, r, facecolor="#cfe3ff", edgecolor="#7a9cc6", alpha=0.7))
            ax.plot(*TOY_CROSS, "x", color="black", ms=9, mew=2)
        else:
            sub = slice(None, None, 8)
            GX, GY = np.meshgrid(g[sub], g[sub])
            pg = pred.reshape(ng, ng)[sub, sub]
            ax.scatter(GX[pg == 1], GY[pg == 1], s=1.2, color=CLASS_ORANGE, lw=0)
            ax.scatter(GX[pg == 0], GY[pg == 0], s=1.2, color=CLASS_BLUE, lw=0)
            ax.contour(g, g, pred.reshape(ng, ng).astype(float), levels=[0.5], colors="black", linewidths=1.3)
        ax.scatter(TOY_X[TOY_Y == 0, 0], TOY_X[TOY_Y == 0, 1], s=55, color=CLASS_BLUE, zorder=3)
        ax.scatter(TOY_X[TOY_Y == 1, 0], TOY_X[TOY_Y == 1, 1], s=55, color=CLASS_ORANGE, zorder=3)
        ax.set_xlim(0, 1)
        ax.set_ylim(0, 1)
        ax.set_xticks([])
        ax.set_yticks([])
        ax.set_aspect("equal")
    fig.tight_layout()
    savefig(fig, CH, "fig2-14", out_dir)


def fig_2_15(out_dir=None):
    """K-NN with K = 10 (black) against the Bayes boundary (dashed)."""
    Xtr, ytr, _, _ = class_data()
    g = _knn_grid(10)
    fig, ax = plt.subplots(figsize=(4.0, 3.8))
    _class_panel(ax, Xtr, ytr, prob_grid=g, boundary=g)
    ax.set_title("KNN: K=10")
    fig.tight_layout()
    savefig(fig, CH, "fig2-15", out_dir)


def fig_2_16(out_dir=None):
    """K-NN with K = 1 and K = 100 against the Bayes boundary."""
    Xtr, ytr, _, _ = class_data()
    fig, axes = common.panel_grid(1, 2, size=(3.6, 3.5))
    for ax, K in zip(axes[0], (1, 100)):
        g = _knn_grid(K)
        _class_panel(ax, Xtr, ytr, prob_grid=g, boundary=g)
        ax.set_title("KNN: K=%d" % K)
    fig.tight_layout()
    savefig(fig, CH, "fig2-16", out_dir)


def knn_errors():
    Xtr, ytr, Xte, yte = class_data()
    return knn_error_curve(Xtr, ytr, Xtr, ytr), knn_error_curve(Xtr, ytr, Xte, yte)


def fig_2_17(out_dir=None):
    """K-NN training error (200 points) and test error (5,000 points) against 1/K, with the Bayes rate."""
    tr, te = knn_errors()
    K = np.arange(1, 101)
    fig, ax = plt.subplots(figsize=(4.8, 3.4))
    ax.plot(1 / K, tr, "-o", color=SKY, ms=2.5, lw=1.4, label="Training Errors")
    ax.plot(1 / K, te, "-o", color=BOOK_ORANGE, ms=2.5, lw=1.4, label="Test Errors")
    ax.axhline(bayes_error(), color="black", ls="--", lw=1.4)
    ax.set_xscale("log")
    ax.set_xticks([0.01, 0.02, 0.05, 0.1, 0.2, 0.5, 1])
    ax.set_xticklabels(["0.01", "0.02", "0.05", "0.10", "0.20", "0.50", "1.00"])
    ax.set_xlabel("1/K")
    ax.set_ylabel("Error Rate")
    ax.set_ylim(0, 0.22)
    ax.legend(frameon=True, fontsize=8, loc="lower left")
    fig.tight_layout()
    savefig(fig, CH, "fig2-17", out_dir)


def numbers(out_dir=None):
    """Print the numbers quoted in the notes and write the demonstration data (no figure)."""
    adv = common.isl_data("Advertising", index_col=0)
    for col in ["TV", "radio", "newspaper"]:
        b0, b1 = _ls_line(adv[col].to_numpy(), adv["sales"].to_numpy())
        print("Figure 2.1  sales ~ %-9s intercept %.4f  slope %.4f" % (col, b0, b1))
    x, y, p = income1_truth()
    print("Figure 2.2  logistic stand-in a, b, c, s = %s; residual SD %.3f"
          % (np.round(p, 3), np.std(y - _logistic(x, *p), ddof=4)))
    b = income2_plane()
    print("Figure 2.4  plane: income = %.3f + %.3f education + %.4f seniority" % tuple(b))
    s = thin_plate_gcv()
    for lab, sm in (("smooth (GCV)", s), ("rough", 0.0)):
        f, H, tr = thin_plate_fit(sm)
        edu, sen, yy = income2()
        print("Figures 2.5-2.6  thin-plate %s: smoothing %.3g, df = tr H = %.2f, training MSE %.3f"
              % (lab, sm, tr, np.mean((yy - H @ yy) ** 2)))
    for ex in (1, 2, 3):
        dfb, teb = best_df(ex)
        c = exact_curves(ex, [2.0, dfb, 25.0])
        yv = training_sample(ex, regression_setup()["x"])
        line = ", ".join("df %.1f: train %.3f test %.3f" % ((d,) + sample_mse(ex, yv, d)) for d in DF_FITS[ex])
        print("Example %d: smallest expected test MSE %.3f at df %.2f; expected test MSE at df 2 / 25: %.3f / %.3f;"
              " bias^2 + var at best df: %.3f + %.3f" % (ex, teb, dfb, c["test"][0], c["test"][2], c["bias2"][1], c["var"][1]))
        print("    one training sample: " + line)
    tr, te = knn_errors()
    Xtr, ytr, Xte, yte = class_data()
    bt = float(np.mean((bayes_prob(Xte) > 0.5).astype(int) != yte))
    print("Bayes error rate (2.11): %.4f; Bayes classifier on the test set: %.4f" % (bayes_error(), bt))
    for K in (1, 3, 10, 100):
        print("K-NN K = %3d: training error %.4f, test error %.4f" % (K, tr[K - 1], te[K - 1]))
    kb = int(np.argmin(te)) + 1
    print("smallest test error %.4f at K = %d" % (te[kb - 1], kb))
    export_demo_data()


FIGURES = {"2.1": fig_2_1, "2.2": fig_2_2, "2.3": fig_2_3, "2.4": fig_2_4, "2.5": fig_2_5, "2.6": fig_2_6,
           "2.8": fig_2_8, "2.9": fig_2_9, "2.10": fig_2_10, "2.11": fig_2_11, "2.12": fig_2_12,
           "2.13": fig_2_13, "2.14": fig_2_14, "2.15": fig_2_15, "2.16": fig_2_16, "2.17": fig_2_17,
           "ex2.3": fig_ex2_3, "data": numbers}

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