"""Hastie, Tibshirani and Friedman (2009), Chapter 2: Overview of Supervised Learning.

Reproduces the figures of Chapter 2 of T. Hastie, R. Tibshirani and J. Friedman, The Elements of
Statistical Learning (2nd edition, Springer, 2009), pp. 9-41, written from scratch with numpy and
matplotlib. Every method is a small function meant to be read next to the lecture notes
(../ch02-overview-supervised-learning.html):

* The simulated mixture data of Section 2.3 (ESL.mixture.rda from the book's website, read once with
  Rscript and cached as CSV in cache/): mixture() returns the 200 training points, the 20 cluster
  means and the book's plotting grid. class_density() and bayes_prob() evaluate the two class
  densities (each an equal mixture of ten N(m_k, I/5) components) and Pr(ORANGE | x);
  bayes_error() integrates the Bayes risk numerically; mixture_test() simulates the 10,000 test
  points of Figure 2.4 from the same generative model.
* Section 2.3.1, least squares: ls_fit() solves the normal equations (2.5)-(2.6) with an intercept,
  and the classifier thresholds the fitted value at 0.5 (2.7).
* Section 2.3.2, nearest neighbours: knn_order() sorts the training points by distance to each query
  (stable sort, so ties are broken by the index), and knn_fraction() turns the sorted labels into the
  k-nearest-neighbour average (2.8) for every k at once with a cumulative sum. knn_smoother() is the
  N x N smoother matrix of k-NN regression, whose trace N/k is the effective number of parameters.
* Section 2.5, the curse of dimensionality: edge_length() is e_p(r) = r^(1/p); nn_median_distance()
  is (2.24) and nn_mean_distance() its mean (a beta function); one_nn_origin_mc() is the simulation of
  Figures 2.7 and 2.8 and one_nn_bump_exact() the exact bias and variance for Figure 2.7;
  epe_ratio_mc() is Figure 2.9 (1-NN against least squares at x0 = 0).
* Section 2.9, the bias-variance trade-off for k-NN regression with a fixed design:
  knn_bias_variance() evaluates (2.46)-(2.47) exactly, and knn_train_test_exact() the expected
  training and test errors averaged over the design points, used for the computed version of
  Figure 2.11.
* JSRandom and js_uniforms() / js_normals(): the seeded generator DK.rng of the browser demos
  (mulberry32 uniforms and Box-Muller normals, the second normal of each pair cached). Because the
  state of mulberry32 advances by a constant, the n-th uniform is a fixed hash of seed + n * constant,
  so long streams can be generated with numpy and give the same numbers as the demos.
* Exercise 2.8: zip_two_three() runs least squares and k-NN on the 2s and 3s of the zip-code data.

Figures reproduced: 2.1, 2.2, 2.3, 2.4, 2.5, 2.6, 2.7, 2.8, 2.9, 2.10, 2.11. Run
`python3 ch02_overview_supervised_learning.py --list`, `python3 ch02_overview_supervised_learning.py`
(all figures, about a minute) or `python3 ch02_overview_supervised_learning.py --fig 2.4`.
Files go to ../img/ch02/; the demos' data go to ../data/ch02-mixture.json.

Figures not reproduced by code: none. Two of them are schematic in the book and are drawn here as
follows:
* Figure 2.6, left panel (a sub-cube inside the unit cube) is drawn as a line sketch; the right panel
  is computed.
* Figure 2.11 (training and test error against model complexity) is a schematic in the book; here it
  is computed exactly for k-nearest-neighbour regression with a fixed design (Section 2.9).

Settings chosen where the book gives none:
* Figure 2.4: the test set has 5,000 points from each class (10,000 in all), simulated with
  numpy.random.default_rng(2009) from the model of Section 2.3.3 and rounded to 4 decimals (the
  rounded values are used everywhere, including the demo). The k values are 1, 3, 5, ..., 151 as in
  the book's top axis. The Bayes rate is the integral of min(f_BLUE, f_ORANGE) / 2 over a grid of
  step 0.01 on [-5, 7]^2.
* Figures 2.1-2.3 and 2.5: the coloured dots are the book's own plotting grid (xnew in the .rda file,
  69 x 99 points); the boundary is the 0.5 contour of the fitted value on a 600 x 450 grid.
* Figures 2.7 and 2.8: N = 1000 training points uniform on [-1, 1]^p, x0 = 0, 2000 simulated training
  sets per dimension (numpy seed 7); the two illustrative top panels use 20 points.
* Figure 2.9: N = 500, sigma = 1, 2000 training sets per dimension (numpy seed 11); the expectation
  over the noise is taken exactly given the inputs (a conditioning argument), which removes most of
  the Monte Carlo noise.
* Figure 2.10: 60 points uniform on [0, 1]^2 with y = f(x) + noise, f a smooth surface, fitted by
  least squares with the six quadratic basis functions 1, x1, x2, x1^2, x1 x2, x2^2.
* Figure 2.11: the design of knn-bias-variance-demo.html: N = 100 inputs x_i ~ U(0, 1) from
  JSRandom(21), f(x) = sin(2 pi x), sigma = 0.5; expected errors exact, plus 20 simulated training sets.
"""
import json
import math
import os
import subprocess

import numpy as np

import common
from common import GREEN, GREY, ORANGE, PURPLE, RED, savefig

CH = 2
HERE = os.path.dirname(os.path.abspath(__file__))
CACHE_DIR = os.path.join(HERE, "cache")
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
RSCRIPT = "/usr/local/bin/Rscript"

MIX_BLUE = "#2b8fd6"      # the book's BLUE class
MIX_ORANGE = "#f08c00"    # the book's ORANGE class
CURVE_BLUE = "#2fb5d9"    # training-error curves (cyan, as in Figure 2.4)
SIG2 = 0.2                # each mixture component is N(m_k, I/5)
M32 = 0xFFFFFFFF


# =========================================================================== the demos' generator
def _imul(a, b):
    """32-bit integer multiplication with wrap-around, as Math.imul (result as unsigned)."""
    return (a * b) & M32


class JSRandom:
    """The seeded random numbers of the browser demos (DK.rng in courses/demo-kit.js), one call at a
    time: u() is mulberry32, norm() the Box-Muller transform that returns r cos(theta) and caches
    r sin(theta) for the next call, exactly as in JavaScript."""

    def __init__(self, seed):
        self.a = int(seed) & M32
        self.spare = None

    def u(self):
        a = (self.a + 0x6D2B79F5) & M32
        self.a = a
        t = _imul(a ^ (a >> 15), 1 | a)
        t = ((t + _imul(t ^ (t >> 7), 61 | t)) & M32) ^ t
        return ((t ^ (t >> 14)) & M32) / 4294967296.0

    def _pos(self):
        x = 0.0
        while x == 0.0:
            x = self.u()
        return x

    def norm(self):
        if self.spare is not None:
            s, self.spare = self.spare, None
            return s
        r = math.sqrt(-2.0 * math.log(self._pos()))
        th = 2.0 * math.pi * self.u()
        self.spare = r * math.sin(th)
        return r * math.cos(th)


def js_uniforms(seed, n, start=0):
    """Uniforms number start+1, ..., start+n of DK.rng(seed), vectorised.

    mulberry32 adds the constant 0x6D2B79F5 to its state at every call and outputs a hash of the
    new state, so the j-th output (j = 1, 2, ...) is hash(seed + j * constant mod 2^32)."""
    j = np.arange(start + 1, start + n + 1, dtype=np.uint64)
    a = (np.uint64(int(seed) & M32) + j * np.uint64(0x6D2B79F5)) & np.uint64(M32)
    m = np.uint64(M32)
    t = ((a ^ (a >> np.uint64(15))) * (np.uint64(1) | a)) & m
    t = ((t + (((t ^ (t >> np.uint64(7))) * (np.uint64(61) | t)) & m)) & m) ^ t
    return ((t ^ (t >> np.uint64(14))) & m).astype(np.float64) / 4294967296.0


def js_normals(seed, n, start=0):
    """n consecutive DK.rng(seed).norm() values when the first of them is drawn after `start`
    uniforms and no normal is cached (Box-Muller pairs: cos first, then the cached sin).
    A uniform exactly 0 (probability 2^-32 per draw) would shift the stream; it is checked."""
    npair = (n + 1) // 2
    u = js_uniforms(seed, 2 * npair, start)
    u1, u2 = u[0::2], u[1::2]
    if np.any(u1 == 0.0):
        raise RuntimeError("a zero uniform: use JSRandom for this stream")
    r = np.sqrt(-2.0 * np.log(u1))
    th = 2.0 * np.pi * u2
    out = np.empty(2 * npair)
    out[0::2] = r * np.cos(th)
    out[1::2] = r * np.sin(th)
    return out[:n]


# =========================================================================== the mixture data
def _export_mixture_csv():
    """Read ESL.mixture.rda with R and write three CSV files to cache/ (done once)."""
    os.makedirs(CACHE_DIR, exist_ok=True)
    rda = common.esl_file("ESL.mixture.rda")
    code = (
        'load("%s"); m <- ESL.mixture; d <- "%s";'
        'write.csv(data.frame(x1=m$x[,1], x2=m$x[,2], y=m$y), file.path(d, "mixture_train.csv"), row.names=FALSE);'
        'write.csv(data.frame(m1=m$means[,1], m2=m$means[,2], cls=rep(0:1, each=10)), file.path(d, "mixture_means.csv"), row.names=FALSE);'
        'write.csv(data.frame(x1=m$xnew[,1], x2=m$xnew[,2], prob=m$prob, marginal=m$marginal), file.path(d, "mixture_grid.csv"), row.names=FALSE)'
    ) % (rda, CACHE_DIR)
    subprocess.run([RSCRIPT, "-e", code], check=True)


def mixture():
    """The simulated two-class data of Section 2.3 (Figures 2.1-2.5).

    Returns a dict with X (200 x 2), y (0 = BLUE, 1 = ORANGE; 100 of each), means (20 x 2: rows
    0-9 generate BLUE, rows 10-19 ORANGE), and the book's plotting grid xnew (6831 x 2) with the
    book's prob = Pr(ORANGE | x) on it."""
    files = [os.path.join(CACHE_DIR, f) for f in ("mixture_train.csv", "mixture_means.csv", "mixture_grid.csv")]
    if not all(os.path.exists(f) for f in files):
        _export_mixture_csv()
    tr = np.loadtxt(files[0], delimiter=",", skiprows=1)
    mu = np.loadtxt(files[1], delimiter=",", skiprows=1)
    gr = np.loadtxt(files[2], delimiter=",", skiprows=1)
    return dict(X=tr[:, :2], y=tr[:, 2].astype(int), means=mu[:, :2], xnew=gr[:, :2], prob=gr[:, 2])


def class_density(P, means):
    """Density at the rows of P of an equal-weight mixture of N(m_k, I/5), m_k the rows of means."""
    P = np.atleast_2d(P)
    d2 = ((P[:, None, :] - means[None, :, :]) ** 2).sum(-1)
    return np.exp(-d2 / (2 * SIG2)).mean(1) / (2 * np.pi * SIG2)


def bayes_prob(P, means):
    """Pr(ORANGE | x) for equal class priors (Bayes' theorem with the two mixture densities)."""
    f0 = class_density(P, means[:10])
    f1 = class_density(P, means[10:])
    return f1 / (f0 + f1)


def bayes_error(means, h=0.01, lo=-5.0, hi=7.0):
    """The Bayes rate: the integral of min(f_BLUE, f_ORANGE) / 2 (Riemann sum, step h)."""
    g = np.arange(lo, hi + h / 2, h)
    tot = 0.0
    for a in g:
        P = np.column_stack([np.full(g.size, a), g])
        tot += np.minimum(class_density(P, means[:10]), class_density(P, means[10:])).sum()
    return 0.5 * tot * h * h


def mixture_sample(n, means, rng):
    """n points from one class: pick one of the ten means at random, then add N(0, I/5) noise."""
    k = rng.integers(0, len(means), n)
    return means[k] + rng.normal(size=(n, 2)) * math.sqrt(SIG2)


def mixture_test(means, n_per_class=5000, seed=2009):
    """The test set of Figure 2.4: n_per_class points from each class, rounded to 4 decimals."""
    rng = np.random.default_rng(seed)
    X0 = mixture_sample(n_per_class, means[:10], rng)
    X1 = mixture_sample(n_per_class, means[10:], rng)
    X = np.round(np.vstack([X0, X1]), 4)
    y = np.r_[np.zeros(n_per_class, int), np.ones(n_per_class, int)]
    return X, y


# =========================================================================== least squares and k-NN
def design(X):
    """The input matrix with a leading column of ones (the intercept, 'bias')."""
    return np.column_stack([np.ones(len(X)), X])


def ls_fit(X, y):
    """Least squares with intercept: solve the normal equations X^T X beta = X^T y (2.5)-(2.6)."""
    A = design(X)
    return np.linalg.solve(A.T @ A, A.T @ y)


def ls_predict(beta, X):
    return design(X) @ beta


def knn_order(Xtr, Xq):
    """For each query row, the training indices sorted by squared Euclidean distance (stable, so ties
    go to the lower index; the demo sorts the same way)."""
    D = ((Xq[:, None, :] - Xtr[None, :, :]) ** 2).sum(-1)
    return np.argsort(D, axis=1, kind="stable")


def knn_fraction(order, ytr, k):
    """The k-NN average (2.8) of the 0/1 responses: the fraction of ORANGE among the k nearest."""
    return ytr[order[:, :k]].mean(1)


def knn_error_curve(order, ytr, ytrue, kmax=None):
    """Misclassification rate of the k-NN majority vote, rule (2.7) (ORANGE iff fraction > 0.5), for
    k = 1, ..., kmax at once."""
    kmax = kmax or order.shape[1]
    cs = np.cumsum(ytr[order[:, :kmax]], axis=1)
    ks = np.arange(1, kmax + 1)
    pred = (cs / ks[None, :]) > 0.5
    return (pred != ytrue[:, None].astype(bool)).mean(0)


def knn_smoother(X, k):
    """The N x N smoother matrix S of k-NN regression at the training inputs: f_hat = S y,
    S_ij = 1/k if x_j is one of the k nearest neighbours of x_i (x_i itself included)."""
    order = knn_order(X, X)
    S = np.zeros((len(X), len(X)))
    rows = np.repeat(np.arange(len(X)), k)
    S[rows, order[:, :k].ravel()] = 1.0 / k
    return S


def mixture_results():
    """Training and test errors on the mixture data for least squares, every k and the Bayes rule."""
    d = mixture()
    X, y, mu = d["X"], d["y"], d["means"]
    Xt, yt = mixture_test(mu)
    beta = ls_fit(X, y)
    res = dict(beta=beta,
               ls_train=float(np.mean((ls_predict(beta, X) > 0.5) != y)),
               ls_test=float(np.mean((ls_predict(beta, Xt) > 0.5) != yt)),
               knn_train=knn_error_curve(knn_order(X, X), y, y),
               knn_test=knn_error_curve(knn_order(X, Xt), y, yt),
               bayes_test=float(np.mean((bayes_prob(Xt, mu) > 0.5) != yt)),
               bayes_rate=bayes_error(mu))
    return d, Xt, yt, res


def export_mixture_json(d=None, Xt=None, yt=None, res=None):
    """data/ch02-mixture.json for least-squares-knn-demo.html."""
    if d is None:
        d, Xt, yt, res = mixture_results()
    out = {
        "note": "Simulated mixture data of Hastie, Tibshirani and Friedman (2009), Section 2.3 (ESL.mixture.rda), "
                "and a test set of 10000 points simulated from the same model (numpy seed 2009, rounded to 4 decimals).",
        "x": [[float(a), float(b)] for a, b in d["X"]], "y": [int(v) for v in d["y"]],
        "means": [[float(a), float(b)] for a, b in d["means"]], "sigma2": SIG2,
        "xtest": [[float(a), float(b)] for a, b in Xt], "ytest": [int(v) for v in yt],
        "bayes_rate": round(float(res["bayes_rate"]), 5),
    }
    os.makedirs(DATA_OUT, exist_ok=True)
    path = os.path.join(DATA_OUT, "ch02-mixture.json")
    with open(path, "w") as f:
        json.dump(out, f, separators=(",", ":"))
    print("wrote", os.path.relpath(path, os.getcwd()), "(%.0f kB)" % (os.path.getsize(path) / 1024))
    return path


def _mixture_panel(ax, d, score, title, levels=0.5):
    """One panel in the style of Figures 2.1-2.3 and 2.5: the book's grid of small dots coloured by
    the predicted class, the decision boundary, and the training points as open circles.
    score(P) returns the fitted value (or probability) whose 0.5 contour is the boundary."""
    G = d["xnew"]
    cls = score(G) > 0.5
    ax.scatter(G[~cls, 0], G[~cls, 1], s=0.6, color=MIX_BLUE, lw=0, rasterized=True)
    ax.scatter(G[cls, 0], G[cls, 1], s=0.6, color=MIX_ORANGE, lw=0, rasterized=True)
    gx = np.linspace(-2.6, 4.2, 600)
    gy = np.linspace(-2.0, 2.9, 450)
    XX, YY = np.meshgrid(gx, gy)
    Z = score(np.column_stack([XX.ravel(), YY.ravel()])).reshape(XX.shape)
    ax.contour(XX, YY, Z, levels=[levels], colors="black", linewidths=1.1)
    X, y = d["X"], d["y"]
    ax.scatter(X[y == 0, 0], X[y == 0, 1], s=22, facecolors="none", edgecolors=MIX_BLUE, linewidths=1.1)
    ax.scatter(X[y == 1, 0], X[y == 1, 1], s=22, facecolors="none", edgecolors=MIX_ORANGE, linewidths=1.1)
    ax.set_xlim(-2.75, 4.35)
    ax.set_ylim(-2.1, 3.0)
    ax.set_xticks([])
    ax.set_yticks([])
    ax.set_title(title)


def _mixture_fig(score, title, name, out_dir):
    import matplotlib.pyplot as plt
    d = mixture()
    fig, ax = plt.subplots(figsize=(4.6, 3.6))
    _mixture_panel(ax, d, score(d), title)
    fig.tight_layout()
    savefig(fig, CH, name, out_dir)
    return d


def fig_2_1(out_dir=None):
    """Linear regression of the 0/1 response: the boundary x^T beta = 0.5."""
    def score(d):
        beta = ls_fit(d["X"], d["y"])
        print("  least squares: beta =", np.round(beta, 4), " training error = %.3f" % np.mean((ls_predict(beta, d["X"]) > 0.5) != d["y"]))
        return lambda P: ls_predict(beta, P)
    _mixture_fig(score, "Linear regression of 0/1 response", "fig2-1", out_dir)


def _knn_score(k):
    def score(d):
        X, y = d["X"], d["y"]
        print("  %d-NN training error = %.3f" % (k, np.mean((knn_fraction(knn_order(X, X), y, k) > 0.5) != y)))
        return lambda P: knn_fraction(knn_order(X, P), y, k)
    return score


def fig_2_2(out_dir=None):
    """15-nearest-neighbour classifier on the mixture data."""
    _mixture_fig(_knn_score(15), "15-nearest neighbour classifier", "fig2-2", out_dir)


def fig_2_3(out_dir=None):
    """1-nearest-neighbour classifier on the mixture data (a Voronoi tessellation)."""
    _mixture_fig(_knn_score(1), "1-nearest neighbour classifier", "fig2-3", out_dir)


def fig_2_5(out_dir=None):
    """The Bayes decision boundary, from the 20 known cluster means."""
    def score(d):
        mu = d["means"]
        print("  max |Pr(ORANGE|x) recomputed - prob in the .rda file| = %.1e" % np.abs(bayes_prob(d["xnew"], mu) - d["prob"]).max())
        return lambda P: bayes_prob(P, mu)
    _mixture_fig(score, "Bayes optimal classifier", "fig2-5", out_dir)


K_FIG24 = list(range(151, 0, -2))   # 151, 149, ..., 3, 1 (plotted at a subset, as in the book)
K_SHOW = [151, 101, 69, 45, 31, 21, 11, 7, 5, 3, 1]


def fig_2_4(out_dir=None):
    """Training and test misclassification of k-NN against N/k, least squares and the Bayes rate."""
    import matplotlib.pyplot as plt
    d, Xt, yt, res = mixture_results()
    export_mixture_json(d, Xt, yt, res)
    N = len(d["y"])
    ks = np.array([151, 125, 101, 83, 69, 55, 45, 37, 31, 25, 21, 17, 15, 13, 11, 9, 7, 5, 3, 1])
    tr, te = res["knn_train"][ks - 1], res["knn_test"][ks - 1]
    df = N / ks
    fig, ax = plt.subplots(figsize=(5.4, 4.0))
    ax.plot(df, tr, "-o", color=CURVE_BLUE, ms=3.2, lw=1.1, label="Train")
    ax.plot(df, te, "-o", color=ORANGE, ms=3.2, lw=1.1, label="Test")
    ax.axhline(res["bayes_rate"], color=PURPLE, lw=1.3, label="Bayes")
    ax.plot([3], [res["ls_train"]], "s", color=CURVE_BLUE, ms=8)
    ax.plot([3], [res["ls_test"]], "s", color=ORANGE, ms=8)
    ax.annotate("Linear", (3, res["ls_test"]), xytext=(2.6, res["ls_test"] + 0.022), fontsize=9)
    ax.set_xscale("log")
    ax.set_xticks([2, 3, 5, 8, 12, 18, 29, 67, 200])
    ax.set_xticklabels(["2", "3", "5", "8", "12", "18", "29", "67", "200"])
    ax.minorticks_off()
    ax.set_xlim(1.15, 240)
    ax.set_ylim(0.0, 0.35)
    ax.set_xlabel("Degrees of freedom, N/k")
    ax.set_ylabel("Test error")
    top = ax.secondary_xaxis("top", functions=(lambda x: N / np.maximum(x, 1e-9), lambda k: N / np.maximum(k, 1e-9)))
    top.set_xticks(K_SHOW)
    top.set_xticklabels([str(k) for k in K_SHOW])
    top.set_xlabel("k, number of nearest neighbours")
    ax.legend(loc="lower left", fontsize=8.5, frameon=True)
    fig.tight_layout()
    savefig(fig, CH, "fig2-4", out_dir)
    kbest = int(np.argmin(res["knn_test"])) + 1
    print("  least squares: train %.3f test %.4f; Bayes rate %.4f (test set %.4f); best k = %d (test %.4f)"
          % (res["ls_train"], res["ls_test"], res["bayes_rate"], res["bayes_test"], kbest, res["knn_test"][kbest - 1]))
    return res


# =========================================================================== the curse of dimensionality
def edge_length(r, p):
    """e_p(r) = r^(1/p): edge of the sub-cube holding a fraction r of uniform data in the unit cube."""
    return np.asarray(r, float) ** (1.0 / p)


def nn_median_distance(p, N):
    """(2.24): median distance from the origin to the nearest of N points uniform in the unit p-ball."""
    return (1.0 - 0.5 ** (1.0 / N)) ** (1.0 / p)


def nn_mean_distance(p, N):
    """Mean of the same distance: integral of (1 - r^p)^N over (0, 1) = B(1/p, N + 1) / p."""
    from scipy.special import betaln
    return math.exp(betaln(1.0 / p, N + 1.0)) / p


def unit_ball_volume(p):
    return math.pi ** (p / 2) / math.gamma(p / 2 + 1)


def bump(X):
    """f(x) = exp(-8 ||x||^2) of Figure 2.7."""
    return np.exp(-8.0 * (X ** 2).sum(-1))


def cubic1(X):
    """f(x) = (x1 + 1)^3 / 2 of Figures 2.8 and 2.9."""
    return 0.5 * (X[..., 0] + 1.0) ** 3


def one_nn_origin_mc(f, p, N=1000, reps=2000, seed=7, chunk=250):
    """Monte Carlo of Figures 2.7-2.8: N training points uniform on [-1, 1]^p, no noise, 1-NN
    prediction at x0 = 0. Returns the mean NN distance, MSE, variance and squared bias."""
    rng = np.random.default_rng(seed + 100 * p)
    yhat, dist = [], []
    left = reps
    while left > 0:
        m = min(chunk, left)
        X = rng.uniform(-1, 1, size=(m, N, p))
        r2 = (X ** 2).sum(-1)
        i = np.argmin(r2, axis=1)
        xnn = X[np.arange(m), i]
        yhat.append(f(xnn))
        dist.append(np.sqrt(r2[np.arange(m), i]))
        left -= m
    yhat, dist = np.concatenate(yhat), np.concatenate(dist)
    f0 = float(f(np.zeros((1, p)))[0])
    var = yhat.var()
    bias2 = (yhat.mean() - f0) ** 2
    return dict(dist=dist.mean(), mse=((yhat - f0) ** 2).mean(), var=var, bias2=bias2)


def one_nn_bump_exact(p, N=1000):
    """Exact bias and variance of the 1-NN estimate of f(0) = 1 for f(x) = exp(-8||x||^2), N points
    uniform on [-1, 1]^p (Figure 2.7). With R the nearest-neighbour distance, the estimate is
    exp(-8 R^2) and, for r <= 1, P(R > r) = (1 - V_p r^p / 2^p)^N. Then
        E exp(-8 m R^2) = 1 - int_0^inf 16 m r exp(-8 m r^2) P(R > r) dr,
    where the part of the integral beyond r = 1 lies in [0, exp(-8 m) P(R > 1)]; it is bounded,
    not computed, and the returned 'err' is the resulting bound on the moments."""
    from scipy.integrate import quad
    c = unit_ball_volume(p) / 2.0 ** p

    def surv(r):
        return (1.0 - c * r ** p) ** N

    mom, err = [], 0.0
    for m in (1, 2):
        I, _ = quad(lambda r: 16 * m * r * math.exp(-8 * m * r * r) * surv(r), 0, 1, limit=400, points=[0.01, 0.05, 0.1, 0.3])
        mom.append(1.0 - I)
        err = max(err, math.exp(-8 * m) * surv(1.0))
    e1, e2 = mom
    return dict(mean=e1, var=e2 - e1 ** 2, bias2=(1 - e1) ** 2, mse=1 - 2 * e1 + e2, err=err, p_far=surv(0.5))


def epe_ratio_mc(f, p, N=500, sigma=1.0, reps=2000, seed=11):
    """Figure 2.9: EPE at x0 = 0 of 1-NN divided by that of least squares (with intercept), for
    Y = f(X) + eps, X uniform on [-1, 1]^p, eps ~ N(0, sigma^2). Given the inputs, the expectation
    over the noise is exact:
        least squares: (l^T f(X) - f(0))^2 + sigma^2 ||l||^2, l = X (X^T X)^{-1} x0,
        1-NN:          (f(x_nn) - f(0))^2 + sigma^2,
    and EPE adds sigma^2 for the new response. Returns (EPE_1NN, EPE_LS)."""
    rng = np.random.default_rng(seed + 100 * p)
    x0 = np.r_[1.0, np.zeros(p)]
    f0 = float(f(np.zeros((1, p)))[0])
    e_nn = e_ls = 0.0
    for _ in range(reps):
        X = rng.uniform(-1, 1, size=(N, p))
        fx = f(X)
        A = design(X)
        l = A @ np.linalg.solve(A.T @ A, x0)
        e_ls += (l @ fx - f0) ** 2 + sigma ** 2 * (l @ l)
        i = np.argmin((X ** 2).sum(1))
        e_nn += (fx[i] - f0) ** 2 + sigma ** 2
    return sigma ** 2 + e_nn / reps, sigma ** 2 + e_ls / reps


def curse_demo_ball(N, seed=500, M=500, pmax=20):
    """curse-of-dimensionality-demo.html, top right: M training sets of N points uniform in the unit
    p-ball drawn from DK.rng(seed); the nearest distance to the origin is (min_i U_i)^(1/p), because the
    radius of a uniform point is U^(1/p). Returns the median over the M sets for p = 1..pmax."""
    mins = js_uniforms(seed, M * N).reshape(M, N).min(1)
    return np.array([np.median(mins ** (1.0 / p)) for p in range(1, pmax + 1)])


def curse_demo_cube(N, seed=700, reps=200, pmax=10):
    """curse-of-dimensionality-demo.html, bottom: for p = 1..pmax, reps training sets of N points
    uniform on [-1, 1]^p from DK.rng(seed + p) (coordinates drawn point by point), the 1-NN
    prediction at 0 of the bump and of the cubic, and the mean nearest distance."""
    out = {"bump": [], "cubic": [], "dist": []}
    for p in range(1, pmax + 1):
        X = 2.0 * js_uniforms(seed + p, reps * N * p).reshape(reps, N, p) - 1.0
        r2 = X[..., 0] * X[..., 0]
        for j in range(1, p):            # summed in the same order as the demo
            r2 = r2 + X[..., j] * X[..., j]
        i = np.argmin(r2, axis=1)
        best = r2[np.arange(reps), i]
        x1 = X[np.arange(reps), i, 0]
        for key, yhat, f0 in (("bump", np.exp(-8.0 * best), 1.0), ("cubic", 0.5 * (x1 + 1.0) ** 3, 0.5)):
            m = yhat.mean()
            out[key].append(dict(mse=((yhat - f0) ** 2).mean(), var=((yhat - m) ** 2).mean(), bias2=(m - f0) ** 2))
        out["dist"].append(np.sqrt(best).mean())
    return out


def fig_2_6(out_dir=None):
    """The edge length e_p(r) = r^(1/p) of a sub-cube capturing a fraction r of uniform data."""
    import matplotlib.pyplot as plt
    fig, (a, b) = plt.subplots(1, 2, figsize=(8.2, 3.6), gridspec_kw=dict(width_ratios=[1, 1.15]))
    # left: a line sketch of the unit cube with a small sub-cube in one corner (oblique projection)
    ox, oy = 0.42, 0.26

    def P(x, y, z):
        return (x + ox * z, y + oy * z)

    def cube(s, col, lw):
        V = [(i, j, l) for i in (0, s) for j in (0, s) for l in (0, s)]
        for u in V:
            for v in V:
                if sum(abs(u[t] - v[t]) > 0 for t in range(3)) == 1 and u < v:
                    (x1, y1), (x2, y2) = P(*u), P(*v)
                    a.plot([x1, x2], [y1, y2], color=col, lw=lw)
    cube(1.0, "#555555", 0.9)
    cube(0.36, ORANGE, 1.4)
    a.text(*P(0.5, 1.12, 1), "Unit cube", ha="center", color=GREEN, fontsize=9.5)
    a.annotate("Neighbourhood", xy=P(0.2, 0.0, 0.0), xytext=(0.05, -0.32), color=GREEN, fontsize=9.5,
               arrowprops=dict(arrowstyle="->", color=GREEN, lw=0.9))
    a.text(-0.06, 0.0, "0", ha="right", va="center", fontsize=9)
    a.text(-0.06, 1.0, "1", ha="right", va="center", fontsize=9)
    a.text(1.0, -0.07, "1", ha="center", va="top", fontsize=9)
    a.set_xlim(-0.2, 1.55)
    a.set_ylim(-0.42, 1.45)
    a.set_aspect("equal")
    a.axis("off")
    # right: the computed curves
    r = np.linspace(0, 0.6, 400)
    for p, col in ((1, "#1b9e77"), (2, "#1b9e77"), (3, "#1b9e77"), (10, "#1b9e77")):
        b.plot(r, edge_length(r, p), color=col, lw=1.3)
        b.text(0.605, edge_length(0.6, p), "p=%d" % p, va="center", fontsize=9)
    for rv in (0.1, 0.3):
        b.axvline(rv, color="#7fb3d5", ls="--", lw=0.9)
    b.set_xlim(-0.02, 0.68)
    b.set_ylim(0, 1.02)
    b.set_xlabel("Fraction of volume")
    b.set_ylabel("Distance")
    b.set_xticks([0, 0.2, 0.4, 0.6])
    fig.tight_layout()
    savefig(fig, CH, "fig2-6", out_dir)
    print("  e_10(0.01) = %.3f, e_10(0.1) = %.3f" % (edge_length(0.01, 10), edge_length(0.1, 10)))


def _one_nn_top_left(ax, f, ylim, seed=3):
    rng = np.random.default_rng(seed)
    x = np.sort(rng.uniform(-1, 1, 20))
    xs = np.linspace(-1, 1, 400)
    ax.plot(xs, f(xs[:, None]), color=GREEN if f is bump else CURVE_BLUE, lw=1.3)
    i = np.argmin(np.abs(x))
    ax.plot(x, np.full(x.size, ylim[0] + 0.0), "|", color=RED, ms=9)
    ax.plot([x[i]], [ylim[0]], "|", color="#1f3fbf", ms=12, mew=2)
    yv = float(f(np.array([[x[i]]]))[0])
    ax.plot([x[i], x[i]], [ylim[0], yv], color="#1f3fbf", lw=0.8, ls=":")
    ax.plot([0, x[i]], [yv, yv], color="#1f3fbf", lw=0.8, ls=":")
    ax.plot([0], [yv], "o", color="#1f3fbf", ms=3.5)
    ax.axvline(0, color=GREY, lw=0.6)
    ax.set_xlim(-1.05, 1.05)
    ax.set_ylim(*ylim)
    ax.set_xlabel("X")
    ax.set_ylabel("f(X)")
    ax.set_title("1-NN in one dimension")


DIMS = np.arange(1, 11)


def fig_2_7(out_dir=None):
    """1-NN estimation of f(0) for f(x) = exp(-8||x||^2): distance, MSE, bias and variance against p."""
    import matplotlib.pyplot as plt
    from matplotlib.patches import Circle, Rectangle
    fig, axes = plt.subplots(2, 2, figsize=(7.6, 7.0))
    _one_nn_top_left(axes[0, 0], bump, (-0.02, 1.05))
    # top right: one sample in two dimensions, 1-NN neighbourhoods in 1-D (x1 only) and 2-D
    a = axes[0, 1]
    rng = np.random.default_rng(21)
    X = rng.uniform(-1, 1, size=(24, 2))
    d1 = np.abs(X[:, 0]).min()
    d2 = np.sqrt((X ** 2).sum(1)).min()
    a.add_patch(Rectangle((-d1, -1), 2 * d1, 2, facecolor="none", edgecolor=ORANGE, hatch="////", lw=1.0))
    a.add_patch(Circle((0, 0), d2, facecolor="none", edgecolor="#1f3fbf", hatch="--", lw=1.0))
    a.scatter(X[:, 0], X[:, 1], s=14, color=GREEN, zorder=3)
    a.plot([0], [0], "ko", ms=3.5)
    a.set_xlim(-1.05, 1.05)
    a.set_ylim(-1.05, 1.05)
    a.set_aspect("equal")
    a.set_xlabel("X1")
    a.set_ylabel("X2")
    a.set_title("1-NN in one vs. two dimensions")
    res = [one_nn_origin_mc(bump, p) for p in DIMS]
    ex = [one_nn_bump_exact(p) for p in DIMS]
    a = axes[1, 0]
    a.plot(DIMS, [r["dist"] for r in res], "o", color=RED, ms=4)
    a.plot(DIMS, [r["dist"] for r in res], "--", color=RED, lw=0.7, alpha=0.6)
    a.set_xlabel("Dimension")
    a.set_ylabel("Average distance to nearest neighbour")
    a.set_title("Distance to 1-NN vs. dimension")
    a.set_ylim(0, 1.0)
    a = axes[1, 1]
    a.plot(DIMS, [e["mse"] for e in ex], color=GREY, lw=0.7)
    a.plot(DIMS, [r["mse"] for r in res], "o", color=RED, ms=4, label="MSE")
    a.plot(DIMS, [r["var"] for r in res], "o-", color=GREEN, ms=4, lw=0.8, label="Variance")
    a.plot(DIMS, [r["bias2"] for r in res], "o", color="#1f3fbf", ms=2.6, label="Sq. bias")
    a.set_xlabel("Dimension")
    a.set_ylabel("MSE")
    a.set_ylim(-0.02, 1.05)
    a.set_title("MSE vs. dimension")
    a.legend(loc="upper left", fontsize=8.5)
    for ax in axes[1]:
        ax.set_xticks([2, 4, 6, 8, 10])
    fig.tight_layout()
    savefig(fig, CH, "fig2-7", out_dir)
    for p, r, e in zip(DIMS, res, ex):
        print("  p=%2d  dist %.3f  MSE %.4f (exact %.4f)  var %.4f (exact %.4f)  bias^2 %.4f (exact %.4f)"
              % (p, r["dist"], r["mse"], e["mse"], r["var"], e["var"], r["bias2"], e["bias2"]))
    return res, ex


def fig_2_8(out_dir=None):
    """The same experiment with f(x) = (x1 + 1)^3 / 2: the variance dominates."""
    import matplotlib.pyplot as plt
    fig, axes = plt.subplots(1, 2, figsize=(7.6, 3.5))
    _one_nn_top_left(axes[0], cubic1, (-0.1, 4.2))
    res = [one_nn_origin_mc(cubic1, p) for p in DIMS]
    a = axes[1]
    a.plot(DIMS, [r["mse"] for r in res], "o-", color=RED, ms=4, lw=0.8, label="MSE")
    a.plot(DIMS, [r["var"] for r in res], "o-", color=CURVE_BLUE, ms=4, lw=0.8, label="Variance")
    a.plot(DIMS, [r["bias2"] for r in res], "o-", color=GREEN, ms=4, lw=0.8, label="Sq. bias")
    a.set_xticks([2, 4, 6, 8, 10])
    a.set_xlabel("Dimension")
    a.set_ylabel("MSE")
    a.set_title("MSE vs. dimension")
    a.legend(loc="upper left", fontsize=8.5)
    fig.tight_layout()
    savefig(fig, CH, "fig2-8", out_dir)
    for p, r in zip(DIMS, res):
        print("  p=%2d  MSE %.4f  var %.4f  bias^2 %.4f" % (p, r["mse"], r["var"], r["bias2"]))
    return res


def fig_2_9(out_dir=None):
    """EPE at x0 = 0 of 1-NN relative to least squares, for a linear and a cubic truth."""
    import matplotlib.pyplot as plt
    lin = lambda X: X[..., 0]  # noqa: E731
    rl = [epe_ratio_mc(lin, p) for p in DIMS]
    rc = [epe_ratio_mc(cubic1, p) for p in DIMS]
    fig, ax = plt.subplots(figsize=(5.2, 3.8))
    ax.plot(DIMS, [a / b for a, b in rl], "o-", color=ORANGE, ms=4, lw=0.8, label="Linear")
    ax.plot(DIMS, [a / b for a, b in rc], "o-", color=CURVE_BLUE, ms=4, lw=0.8, label="Cubic")
    ax.set_xticks([2, 4, 6, 8, 10])
    ax.set_xlabel("Dimension")
    ax.set_ylabel("EPE ratio")
    ax.set_title("Expected prediction error of 1-NN vs. OLS")
    ax.legend(loc="center left", fontsize=8.5)
    fig.tight_layout()
    savefig(fig, CH, "fig2-9", out_dir)
    for p, a, c in zip(DIMS, rl, rc):
        print("  p=%2d  linear: EPE 1NN %.4f LS %.4f ratio %.3f   cubic: 1NN %.4f LS %.4f ratio %.3f"
              % (p, a[0], a[1], a[0] / a[1], c[0], c[1], c[0] / c[1]))
    return rl, rc


# =========================================================================== function approximation
def surface_f(X):
    return 0.4 + 1.2 * X[:, 0] - 0.8 * X[:, 1] + 1.6 * X[:, 0] * X[:, 1] - 1.4 * X[:, 1] ** 2 + 0.6 * X[:, 0] ** 2


def quad_basis(X):
    x1, x2 = X[:, 0], X[:, 1]
    return np.column_stack([np.ones(len(X)), x1, x2, x1 ** 2, x1 * x2, x2 ** 2])


def fig_2_10(out_dir=None):
    """Least squares fit of a function of two inputs: the fitted surface and the vertical errors."""
    import matplotlib.pyplot as plt
    rng = np.random.default_rng(10)
    X = rng.uniform(0, 1, size=(60, 2))
    y = surface_f(X) + 0.15 * rng.normal(size=60)
    H = quad_basis(X)
    theta = np.linalg.solve(H.T @ H, H.T @ y)
    fig = plt.figure(figsize=(5.4, 4.6))
    ax = fig.add_subplot(111, projection="3d")
    g = np.linspace(0, 1, 25)
    G1, G2 = np.meshgrid(g, g)
    Z = (quad_basis(np.column_stack([G1.ravel(), G2.ravel()])) @ theta).reshape(G1.shape)
    ax.plot_surface(G1, G2, Z, color="#f5d7a8", alpha=0.55, edgecolor="#d9a05b", linewidth=0.25)
    fit = H @ theta
    for xi, yi, fi in zip(X, y, fit):
        ax.plot([xi[0], xi[0]], [xi[1], xi[1]], [fi, yi], color="#c0392b", lw=0.8)
    up = y >= fit
    ax.scatter(X[up, 0], X[up, 1], y[up], color="#c0392b", s=10, depthshade=False)
    ax.scatter(X[~up, 0], X[~up, 1], y[~up], color="#7f1d12", s=10, depthshade=False)
    ax.set_xlabel("$X_1$", labelpad=-8)
    ax.set_ylabel("$X_2$", labelpad=-8)
    ax.set_zlabel("$Y$", labelpad=-8)
    ax.set_xticklabels([])
    ax.set_yticklabels([])
    ax.set_zticklabels([])
    ax.view_init(elev=18, azim=-62)
    ax.set_box_aspect((1, 1, 0.8))
    savefig(fig, CH, "fig2-10", out_dir)
    print("  theta =", np.round(theta, 3), " RSS = %.4f" % ((y - fit) ** 2).sum())
    return theta


# =========================================================================== bias-variance for k-NN
BV_SEED_X, BV_SEED_Y = 21, 22


def bv_function(name):
    """The three regression functions of knn-bias-variance-demo.html."""
    if name == "sine":
        return lambda x: np.sin(2 * np.pi * x)
    if name == "wiggly":
        return lambda x: np.sin(6 * np.pi * x) * (1 - x) + x
    if name == "step":
        return lambda x: np.where(x < 0.5, 0.0, 1.0) + 0.5 * x
    raise ValueError(name)


def bv_design(N, seed=BV_SEED_X):
    """The fixed design of the demo: N uniforms from DK.rng(seed), in the order drawn."""
    return js_uniforms(seed, N)


def bv_responses(x, fname, sigma, seed=BV_SEED_Y):
    """One training set y_i = f(x_i) + sigma * eps_i, eps_i the first N normals of DK.rng(seed)."""
    return bv_function(fname)(x) + sigma * js_normals(seed, len(x))


def knn1d_order(x, x0):
    """Indices of the design points sorted by |x_i - x0| (stable: ties go to the lower index)."""
    return np.argsort(np.abs(np.asarray(x)[None, :] - np.atleast_1d(x0)[:, None]), axis=1, kind="stable")


def knn_bias_variance(x, f, sigma, x0, ks):
    """(2.46)-(2.47) at the point x0: for each k the squared bias [f(x0) - mean of f over the k
    nearest design points]^2, the variance sigma^2 / k, and EPE = sigma^2 + bias^2 + variance."""
    order = knn1d_order(x, x0)[0]
    fx = f(x)[order]
    ks = np.asarray(ks)
    mean_f = np.cumsum(fx)[ks - 1] / ks
    bias2 = (float(f(np.array([x0]))[0]) - mean_f) ** 2
    var = sigma ** 2 / ks
    return dict(bias2=bias2, var=var, epe=sigma ** 2 + bias2 + var)


def knn_train_test_exact(x, f, sigma, ks):
    """Expected training error and expected in-sample test error of k-NN regression with a fixed
    design, averaged over the N design points (x_i is its own nearest neighbour):
        E train = mean_i b_i(k)^2 + sigma^2 (1 - 1/k),   E test = sigma^2 + mean_i b_i(k)^2 + sigma^2 / k,
    b_i(k) = f(x_i) - mean of f over the k nearest neighbours of x_i. Their difference is the
    optimism 2 sigma^2 / k = 2 sigma^2 trace(S) / N."""
    order = knn1d_order(x, x)
    fx = f(x)
    cs = np.cumsum(fx[order], axis=1)
    ks = np.asarray(ks)
    b2 = ((fx[:, None] - cs[:, ks - 1] / ks[None, :]) ** 2).mean(0)
    return dict(bias2=b2, train=b2 + sigma ** 2 * (1 - 1.0 / ks), test=sigma ** 2 + b2 + sigma ** 2 / ks)


def knn_train_error_realised(x, y, ks):
    """Training error (1/N) sum (y_i - f_hat_k(x_i))^2 of one data set, for each k."""
    order = knn1d_order(x, x)
    cs = np.cumsum(y[order], axis=1)
    ks = np.asarray(ks)
    return ((y[:, None] - cs[:, ks - 1] / ks[None, :]) ** 2).mean(0)


def fig_2_11(out_dir=None, N=100, sigma=0.5, fname="sine"):
    """Training and test error against model complexity (computed for k-NN regression)."""
    import matplotlib.pyplot as plt
    x = bv_design(N)
    f = bv_function(fname)
    ks = np.arange(N, 0, -1)
    df = N / ks
    ex = knn_train_test_exact(x, f, sigma, ks)
    fig, ax = plt.subplots(figsize=(5.6, 3.9))
    rng = np.random.default_rng(111)
    for _ in range(20):
        y = f(x) + sigma * rng.normal(size=N)
        ynew = f(x) + sigma * rng.normal(size=N)
        order = knn1d_order(x, x)
        fit = np.cumsum(y[order], axis=1)[:, ks - 1] / ks[None, :]
        ax.plot(df, ((y[:, None] - fit) ** 2).mean(0), color=CURVE_BLUE, lw=0.5, alpha=0.45)
        ax.plot(df, ((ynew[:, None] - fit) ** 2).mean(0), color="#f4a39b", lw=0.5, alpha=0.55)
    ax.plot(df, ex["train"], color="#1f6fb2", lw=2.0, label="Training sample (expected)")
    ax.plot(df, ex["test"], color=RED, lw=2.0, label="Test sample (expected)")
    kb = int(np.argmin(ex["test"]))
    ax.axvline(df[kb], color=GREY, ls=":", lw=0.9)
    ax.set_xscale("log")
    ax.set_xlim(1, N)
    ax.set_ylim(0, 0.9)
    ax.set_xlabel("Model complexity: degrees of freedom N/k (k from %d down to 1)" % N)
    ax.set_ylabel("Prediction error")
    ax.text(1.12, 0.84, "High bias\nLow variance", fontsize=8.5, va="top")
    ax.text(N / 1.12, 0.84, "Low bias\nHigh variance", fontsize=8.5, va="top", ha="right")
    ax.legend(loc="upper center", fontsize=8.2, frameon=False)
    ax.set_xticks([1, 2, 5, 10, 20, 50, 100])
    ax.set_xticklabels(["1", "2", "5", "10", "20", "50", "100"])
    ax.minorticks_off()
    fig.tight_layout()
    savefig(fig, CH, "fig2-11", out_dir)
    print("  minimum expected test error %.4f at k = %d (N/k = %.2f); training error there %.4f"
          % (ex["test"][kb], ks[kb], df[kb], ex["train"][kb]))
    return ex


# =========================================================================== Exercise 2.8: zip code
def zip_two_three(ks=(1, 3, 5, 7, 15)):
    """Least squares and k-NN on the 2s and 3s of the zip-code data (Exercise 2.8): returns a dict of
    (training error, test error) pairs."""
    import gzip

    def load(name):
        with gzip.open(common.esl_file(name), "rt") as fh:
            A = np.loadtxt(fh)
        keep = np.isin(A[:, 0], (2, 3))
        return A[keep, 1:], (A[keep, 0] == 3).astype(int)
    Xtr, ytr = load("zip.train.gz")
    Xte, yte = load("zip.test.gz")
    beta = np.linalg.lstsq(design(Xtr), ytr, rcond=None)[0]
    out = {"LS": (float(np.mean((design(Xtr) @ beta > 0.5) != ytr)), float(np.mean((design(Xte) @ beta > 0.5) != yte)))}
    otr, ote = knn_order(Xtr, Xtr), knn_order(Xtr, Xte)
    etr, ete = knn_error_curve(otr, ytr, ytr, max(ks)), knn_error_curve(ote, ytr, yte, max(ks))
    for k in ks:
        out["%d-NN" % k] = (float(etr[k - 1]), float(ete[k - 1]))
    out["sizes"] = (len(ytr), len(yte))
    return out


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.7": fig_2_7, "2.8": fig_2_8, "2.9": fig_2_9, "2.10": fig_2_10, "2.11": fig_2_11}

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