"""Chapter 1 (Introduction) of "Probabilistic Machine Learning: An Introduction".

Reproduces the computed figures of Murphy (2022), Chapter 1, from scratch:

    1.3   pairwise scatter plot of the Iris data
    1.4   a depth-2 decision tree on petal length and petal width (own Gini tree)
    1.5   least-squares line and its residuals on 1d data
    1.6   linear and quadratic regression on 2d data (a simulated stand-in for the room-temperature data)
    1.7   polynomial regression of degree 2, 14, 20 and train / test MSE against degree
    1.8   K-means (K = 3) on the Iris petal features (own Lloyd algorithm)
    1.9   PCA of the first three Iris features onto a 2d plane (own SVD)
    1.12  the first 25 MNIST training digits (panel a only)
    1.15  a TF-IDF term-document matrix (a small corpus written for this course)

and two extra figures used by the notes and the demos:

    1.S1  missing data: MCAR, MAR and NMAR and the bias of mean imputation (Section 1.5.5)
    1.S2  optimism of the training error, 2 sigma^2 p / N (Section 1.2.3)

Skipped (nothing computed, or the data cannot be obtained offline):
    1.1   photographs of three Iris flowers
    1.2   a schematic of the image classification problem
    1.10  screenshots of an Atari game and a simulated robot
    1.11  the "layer cake" diagram
    1.12b the EMNIST letters (not available offline)
    1.13  Fashion-MNIST and CIFAR-10 sample images (not available offline)
    1.14  ImageNet sample images and the results of a competition (copied from a paper)
Tables 1.1 and 1.2 are reproduced in the notes as HTML tables; Tables 1.3 and 1.4 are text.

Data: Iris comes with scikit-learn; MNIST is read through common.mnist(); the 1d regression data,
the room-temperature field and the missing-data sample are simulated (the book's own samples are
not available), and the notes say so wherever they are used.

Run:  python3 ch01_introduction.py [--fig 1.7 1.8 ...]   (about one minute in all)
"""
import json
import os
import sys

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.patches import FancyBboxPatch
from numpy.polynomial import chebyshev as Cheb

sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
import common  # noqa: E402
from common import savefig, run, RED, BLUE, GREEN, GREY, ORANGE, PURPLE, sigmoid  # noqa: E402

CH = 1
HERE = os.path.dirname(os.path.abspath(__file__))
DATA_JSON = os.path.normpath(os.path.join(HERE, "..", "data"))
IRIS_NAMES = ["setosa", "versicolor", "virginica"]
IRIS_FEATS = ["sepal length (cm)", "sepal width (cm)", "petal length (cm)", "petal width (cm)"]
CLS = (ORANGE, GREEN, PURPLE)


def iris():
    from sklearn.datasets import load_iris
    d = load_iris()
    return d.data.copy(), d.target.copy()


# ====================================================================== loss and risk
def empirical_risk(y, yhat, L=None):
    """(1.4): average loss; with L None this is the misclassification rate (1.2).
    L[c, k] is the loss of predicting k when the truth is c (Table 1.2)."""
    y = np.asarray(y)
    yhat = np.asarray(yhat)
    if L is None:
        return float(np.mean(y != yhat))
    return float(np.mean(np.asarray(L)[y, yhat]))


LOSS_TABLE_1_2 = np.array([[0, 1, 1], [1, 0, 1], [10, 10, 0]], dtype=float)


def bayes_decision(p, L):
    """Minimiser of the posterior expected loss sum_c p(c) L[c, k] over k; p has shape (..., C)."""
    return np.argmin(np.asarray(p) @ np.asarray(L), axis=-1)


# ====================================================================== a Gini decision tree
def gini(counts):
    n = counts.sum()
    return 0.0 if n == 0 else 1.0 - float(((counts / n) ** 2).sum())


def best_split(X, y, C):
    """Best (feature, threshold) by weighted Gini impurity, or None. Thresholds are midpoints."""
    n, D = X.shape
    parent = gini(np.bincount(y, minlength=C))
    best = (parent - 1e-12, None, None)
    for j in range(D):
        o = np.argsort(X[:, j], kind="stable")
        xs, ys = X[o, j], y[o]
        left = np.zeros(C)
        right = np.bincount(ys, minlength=C).astype(float)
        for i in range(n - 1):
            left[ys[i]] += 1
            right[ys[i]] -= 1
            if xs[i] == xs[i + 1]:
                continue
            nl = i + 1
            imp = (nl * gini(left) + (n - nl) * gini(right)) / n
            if imp < best[0] - 1e-12:
                best = (imp, j, 0.5 * (xs[i] + xs[i + 1]))
    return None if best[1] is None else (best[1], best[2])


def grow_tree(X, y, depth, C=3, min_leaf=1):
    """Greedy tree: node = dict(counts, feat, thr, left, right). Leaves have feat None."""
    counts = np.bincount(y, minlength=C)
    node = dict(counts=counts, feat=None, thr=None, left=None, right=None)
    if depth == 0 or (counts > 0).sum() == 1 or len(y) < 2 * min_leaf:
        return node
    s = best_split(X, y, C)
    if s is None:
        return node
    j, t = s
    m = X[:, j] <= t
    node.update(feat=j, thr=t, left=grow_tree(X[m], y[m], depth - 1, C, min_leaf),
                right=grow_tree(X[~m], y[~m], depth - 1, C, min_leaf))
    return node


def tree_predict_proba(node, X):
    X = np.atleast_2d(X)
    out = np.zeros((len(X), len(node["counts"])))
    for i, x in enumerate(X):
        nd = node
        while nd["feat"] is not None:
            nd = nd["left"] if x[nd["feat"]] <= nd["thr"] else nd["right"]
        out[i] = nd["counts"] / nd["counts"].sum()
    return out


def tree_leaves(node):
    return 1 if node["feat"] is None else tree_leaves(node["left"]) + tree_leaves(node["right"])


# ====================================================================== polynomial regression
def f_true_1d(x):
    """Quadratic through (0, 2), (7, -5), (20, 9.5): the mean function of the stand-in data of Figure 1.5."""
    a = 0.1057692307692308
    b = -1.7403846153846154
    return a * x ** 2 + b * x + 2.0


SIGMA_1D = 2.0


def poly_data(seed=2022):
    """Stand-in for the book's 21 points (Figure 1.5): x = 0, 1, ..., 20 and y = f(x) + 2 z,
    plus a test set of 500 points at random inputs on [0, 20] and a pool of 200 random training points."""
    rng = np.random.default_rng(seed)
    x21 = np.arange(21.0)
    z21 = rng.standard_normal(21)
    xp = rng.uniform(0, 20, 200)
    zp = rng.standard_normal(200)
    xt = rng.uniform(0, 20, 500)
    zt = rng.standard_normal(500)
    return dict(x21=x21, z21=z21, xpool=xp, zpool=zp, xtest=xt, ztest=zt)


def poly_fit(x, y, deg):
    """Least-squares polynomial of the given degree. The basis is Chebyshev polynomials of
    t = x/10 - 1 (well conditioned up to degree 20 on [0, 20]); the fitted function is the same as
    for the monomial basis because the two bases span the same space."""
    V = Cheb.chebvander(np.asarray(x) / 10 - 1, deg)
    c = np.linalg.lstsq(V, y, rcond=None)[0]
    return c


def poly_eval(c, x):
    return Cheb.chebval(np.asarray(x) / 10 - 1, c)


def mse(y, yhat):
    return float(np.mean((np.asarray(y) - np.asarray(yhat)) ** 2))


# ====================================================================== K-means and PCA
def kmeans(X, K, seed=0, restarts=10, iters=200):
    """Lloyd's algorithm with random-point starts; returns the best (centres, labels, distortion)."""
    rng = np.random.default_rng(seed)
    best = None
    for _ in range(restarts):
        mu = X[rng.choice(len(X), K, replace=False)].copy()
        prev = np.inf
        for _ in range(iters):
            d = ((X[:, None, :] - mu[None]) ** 2).sum(-1)
            z = d.argmin(1)
            J = d[np.arange(len(X)), z].sum()
            for k in range(K):
                if (z == k).any():
                    mu[k] = X[z == k].mean(0)
            if prev - J < 1e-12:
                break
            prev = J
        d = ((X[:, None, :] - mu[None]) ** 2).sum(-1)
        z = d.argmin(1)
        J = d[np.arange(len(X)), z].sum()
        if best is None or J < best[2] - 1e-12:
            best = (mu.copy(), z.copy(), J)
    return best


def pca(X, K):
    """Mean, principal axes W (D x K), scores Z (N x K) and singular values of the centred data."""
    mu = X.mean(0)
    U, s, Vt = np.linalg.svd(X - mu, full_matrices=False)
    W = Vt[:K].T
    return mu, W, (X - mu) @ W, s


# ====================================================================== text: TF-IDF
CORPUS = [
    "heavy rain and strong wind hit the coast overnight",
    "the storm brought rain and flooding to the coast",
    "sunny weather and light wind are expected tomorrow",
    "cold wind and snow cover the mountain passes",
    "simmer the tomato sauce and add basil and garlic",
    "bake the bread until the crust is golden",
    "chop the garlic and fry the onion in olive oil",
    "add garlic and tomato to the pasta sauce",
    "the striker scored a late goal in the final match",
    "the team won the match after a penalty goal",
    "the coach praised the defence after the match",
    "a late penalty decided the final",
]
STOP = {"the", "and", "a", "to", "in", "of", "are", "is", "after", "until"}


def tokens(doc):
    return [w for w in doc.lower().split() if w not in STOP]


def tfidf(docs):
    """(1.37)-(1.38): rows are terms, columns documents; TFIDF_ij = log(TF_ij + 1) * IDF_i with IDF_i = log(N / (1 + DF_i))."""
    toks = [tokens(d) for d in docs]
    vocab = sorted({w for t in toks for w in t})
    TF = np.array([[t.count(w) for t in toks] for w in vocab], dtype=float)
    N = len(docs)
    DF = (TF > 0).sum(1)
    IDF = np.log(N / (1.0 + DF))
    return vocab, TF, IDF, np.log(TF + 1.0) * IDF[:, None]


# ====================================================================== missing data
def missing_sample(n=2000, rho=0.7, seed=11):
    """The two-variable sample of Section 1.5.5: x1 ~ N(0, 1), x2 = 2 + rho x1 + sqrt(1 - rho^2) e.
    The standard normals and the uniforms that decide missingness are stored so that the browser
    demo uses exactly the same numbers."""
    rng = np.random.default_rng(seed)
    z1 = np.round(rng.standard_normal(n), 8)
    z2 = np.round(rng.standard_normal(n), 8)
    u = np.round(rng.uniform(size=n), 8)
    return dict(z1=z1, z2=z2, u=u, rho=rho)


def missing_probability(kind, x1, x2, strength, base):
    """P(x2 is missing): MCAR constant; MAR depends on x1; NMAR on x2 itself (all logistic)."""
    if kind == "mcar":
        return np.full_like(x1, sigmoid(base))
    if kind == "mar":
        return sigmoid(strength * x1 + base)
    return sigmoid(strength * (x2 - 2.0) + base)


def missing_summary(S, kind, strength, base):
    z1, z2, u, rho = S["z1"], S["z2"], S["u"], S["rho"]
    x1 = z1
    x2 = 2.0 + rho * z1 + np.sqrt(1 - rho ** 2) * z2
    miss = u < missing_probability(kind, x1, x2, strength, base)
    obs = ~miss
    mean_cc = x2[obs].mean()
    # regression imputation: fit x2 on x1 among complete cases (valid under MAR)
    A = np.c_[np.ones(obs.sum()), x1[obs]]
    b = np.linalg.lstsq(A, x2[obs], rcond=None)[0]
    x2_reg = np.where(miss, b[0] + b[1] * x1, x2)
    x2_mean = np.where(miss, mean_cc, x2)
    return dict(frac_missing=float(miss.mean()), true_mean=float(x2.mean()), mean_cc=float(mean_cc),
                mean_reg=float(x2_reg.mean()), sd_true=float(x2.std(ddof=1)), sd_meanimp=float(x2_mean.std(ddof=1)),
                corr_true=float(np.corrcoef(x1, x2)[0, 1]), corr_meanimp=float(np.corrcoef(x1, x2_mean)[0, 1]),
                corr_reg=float(np.corrcoef(x1, x2_reg)[0, 1]))


# ====================================================================== figures
def _out(out):
    return out


def fig_1_3(out=None):
    """Pairwise scatter plot of the Iris data."""
    from scipy.stats import gaussian_kde
    X, y = iris()
    D = 4
    fig, ax = plt.subplots(D, D, figsize=(8.2, 7.6))
    for i in range(D):
        for j in range(D):
            a = ax[i, j]
            if i == j:
                lo, hi = X[:, i].min(), X[:, i].max()
                g = np.linspace(lo - 0.3 * (hi - lo), hi + 0.3 * (hi - lo), 200)
                for c in range(3):
                    a.fill_between(g, gaussian_kde(X[y == c, i])(g), color=CLS[c], alpha=0.35, lw=0)
                    a.plot(g, gaussian_kde(X[y == c, i])(g), color=CLS[c], lw=1.3)
                a.set_yticks([])
            else:
                for c in range(3):
                    a.scatter(X[y == c, j], X[y == c, i], s=9, color=CLS[c], alpha=0.85, label=IRIS_NAMES[c])
            if i == D - 1:
                a.set_xlabel(IRIS_FEATS[j])
            else:
                a.set_xticklabels([])
            if j == 0:
                a.set_ylabel(IRIS_FEATS[i])
            elif i != j:
                a.set_yticklabels([])
    h, l = ax[0, 1].get_legend_handles_labels()
    fig.legend(h, l, loc="upper center", ncol=3, frameon=False, bbox_to_anchor=(0.5, 1.0))
    fig.tight_layout(rect=(0, 0, 1, 0.96))
    return savefig(fig, CH, "fig1-3", out)


def draw_tree(ax, tree, names):
    """A depth-2 tree diagram: boxes with feature test, sample counts and majority class."""
    def box(x, y, nd, w=0.25, h=0.2):
        c = nd["counts"]
        cls = int(c.argmax())
        leaf = nd["feat"] is None
        col = {0: "#fbd28a", 1: "#9fd9a0", 2: "#c3a3ec"}[cls] if leaf else "white"
        ax.add_patch(FancyBboxPatch((x - w / 2, y - h / 2), w, h, boxstyle="round,pad=0.01,rounding_size=0.02", fc=col, ec="#444", lw=0.9))
        lines = []
        if not leaf:
            lines.append("%s <= %.2f" % (names[nd["feat"]].replace(" (cm)", ""), nd["thr"]))
        lines += ["samples = %d" % c.sum(), "value = [%s]" % ", ".join(str(int(v)) for v in c), "class = %s" % IRIS_NAMES[cls]]
        ax.text(x, y, "\n".join(lines), ha="center", va="center", fontsize=6.6)

    def rec(nd, x, y, dx):
        box(x, y, nd)
        if nd["feat"] is not None:
            for sgn, ch, lab in ((-1, nd["left"], "yes"), (1, nd["right"], "no")):
                xc, yc = x + sgn * dx, y - 0.34
                ax.plot([x + sgn * 0.02, xc], [y - 0.1, yc + 0.1], color="#444", lw=0.9)
                ax.text((x + xc) / 2 + sgn * 0.02, (y + yc) / 2, lab, fontsize=7, ha="center", color="#444")
                rec(ch, xc, yc, dx * 0.54)
    ax.set_xlim(-0.01, 1.03)
    ax.set_ylim(0.0, 1.0)
    ax.axis("off")
    rec(tree, 0.5, 0.88, 0.25)


def fig_1_4(out=None):
    """Depth-2 decision tree on petal length and petal width."""
    X, y = iris()
    Xp = X[:, 2:4]
    tree = grow_tree(Xp, y, 2)
    fig, (a, b) = plt.subplots(1, 2, figsize=(9.2, 3.8), gridspec_kw=dict(width_ratios=[1.15, 1]))
    draw_tree(a, tree, IRIS_FEATS[2:4])
    a.text(0.5, 0.0, "(a)", ha="center", fontsize=10)
    g1, g2 = np.meshgrid(np.linspace(-0.2, 7.6, 300), np.linspace(-0.6, 3.1, 300))
    P = tree_predict_proba(tree, np.c_[g1.ravel(), g2.ravel()]).argmax(1).reshape(g1.shape)
    from matplotlib.colors import ListedColormap
    b.imshow(P, extent=(-0.2, 7.6, -0.6, 3.1), origin="lower", aspect="auto", cmap=ListedColormap(["#fbd28a", "#9fd9a0", "#c3a3ec"]), vmin=0, vmax=2)
    for c, m in zip(range(3), "o^s"):
        b.scatter(Xp[y == c, 0], Xp[y == c, 1], s=14, marker=m, color="k", facecolor="none" if c == 0 else "k", label=IRIS_NAMES[c], lw=0.8)
    b.set_xlabel(IRIS_FEATS[2])
    b.set_ylabel(IRIS_FEATS[3])
    b.legend(loc="upper left", fontsize=7)
    panel_note = "(b)"
    b.set_title(panel_note, y=-0.3, fontsize=10)
    fig.tight_layout()
    return savefig(fig, CH, "fig1-4", out)


def fig_1_5(out=None):
    """Least squares line on the 1d data, and its residuals."""
    D = poly_data()
    x, y = D["x21"], f_true_1d(D["x21"]) + SIGMA_1D * D["z21"]
    A = np.c_[np.ones_like(x), x]
    b0, w = np.linalg.lstsq(A, y, rcond=None)[0]
    yh = b0 + w * x
    fig, ax = plt.subplots(1, 2, figsize=(8.4, 3.0), sharey=True)
    for k in range(2):
        a = ax[k]
        a.scatter(x, y, s=22, color=BLUE, zorder=3)
        a.set_xlabel("x")
        a.set_ylim(-9, 13)
    ax[0].plot(x, yh, color=RED, lw=1.5)
    ax[0].set_ylabel("y")
    ax[1].vlines(x, y, yh, color="k", lw=0.9)
    ax[1].plot(x, yh, "x", color=RED, ms=6)
    ax[1].plot(x, yh, color=RED, lw=0.8, alpha=0.6)
    for a, t in zip(ax, "(a)", ):
        pass
    ax[0].set_title("(a) fitted line, w = %.3f, b = %.3f" % (w, b0), fontsize=9)
    ax[1].set_title("(b) residuals, MSE = %.2f" % mse(y, yh), fontsize=9)
    fig.tight_layout()
    return savefig(fig, CH, "fig1-5", out)


def temperature_field(seed=5):
    """Stand-in for the room-temperature readings of Figure 1.6: 54 sensors at random places in a
    40 x 30 room, a dome-shaped true temperature (hottest in the middle) plus noise of sd 0.35."""
    rng = np.random.default_rng(seed)
    P = np.c_[rng.uniform(0, 40, 54), rng.uniform(0, 30, 54)]
    def f(x1, x2):
        return 18.7 - 0.0042 * (x1 - 20) ** 2 - 0.0070 * (x2 - 15) ** 2 - 0.5
    T = f(P[:, 0], P[:, 1]) + 0.35 * rng.standard_normal(54)
    return P, T, f


def fig_1_6(out=None):
    """Linear and quadratic regression on 2d (simulated) temperature data."""
    P, T, _ = temperature_field()
    x1, x2 = P[:, 0], P[:, 1]
    A1 = np.c_[np.ones(54), x1, x2]
    A2 = np.c_[np.ones(54), x1, x2, x1 ** 2, x2 ** 2]
    w1 = np.linalg.lstsq(A1, T, rcond=None)[0]
    w2 = np.linalg.lstsq(A2, T, rcond=None)[0]
    g1, g2 = np.meshgrid(np.linspace(0, 40, 41), np.linspace(0, 30, 31))
    S1 = w1[0] + w1[1] * g1 + w1[2] * g2
    S2 = w2[0] + w2[1] * g1 + w2[2] * g2 + w2[3] * g1 ** 2 + w2[4] * g2 ** 2
    fig = plt.figure(figsize=(9.4, 4.0))
    for k, (S, lab) in enumerate(((S1, "(a) plane, w0 + w1 x1 + w2 x2"), (S2, "(b) quadratic, five weights"))):
        a = fig.add_subplot(1, 2, k + 1, projection="3d")
        a.plot_surface(g1, g2, S, cmap="turbo", alpha=0.85, linewidth=0, antialiased=True, rstride=1, cstride=1)
        a.scatter(x1, x2, T, color=RED, s=8, depthshade=False)
        a.set_zlim(14.5, 19.5)
        a.set_xlabel("x1")
        a.set_ylabel("x2")
        a.set_zlabel("temperature")
        a.set_title(lab, fontsize=9, y=-0.12)
        a.view_init(28, -60)
    fig.tight_layout()
    return savefig(fig, CH, "fig1-6", out)


def fig_1_7(out=None):
    """Polynomials of degree 2, 14, 20 and train and test MSE against degree."""
    D = poly_data()
    x = D["x21"]
    y = f_true_1d(x) + SIGMA_1D * D["z21"]
    xt = D["xtest"]
    yt = f_true_1d(xt) + SIGMA_1D * D["ztest"]
    g = np.linspace(0, 20, 400)
    fig, ax = plt.subplots(2, 2, figsize=(8.0, 6.2))
    for a, d, lab in zip(ax.ravel()[:3], (2, 14, 20), "abc"):
        c = poly_fit(x, y, d)
        a.plot(g, poly_eval(c, g), color=BLUE, lw=1.6)
        a.scatter(x, y, s=22, color=BLUE, zorder=3)
        a.set_ylim(-10, 15)
        a.set_title("degree %d" % d)
        a.set_xlabel("(%s)" % lab)
    degs = np.arange(1, 16)
    tr, te = [], []
    for d in degs:
        c = poly_fit(x, y, d)
        tr.append(mse(y, poly_eval(c, x)))
        te.append(mse(yt, poly_eval(c, xt)))
    a = ax[1, 1]
    a.plot(degs, te, "x-", color=RED, label="test")
    a.plot(degs, tr, "s-", color=BLUE, ms=4, label="train")
    a.axhline(SIGMA_1D ** 2, color=GREY, ls=":", lw=1)
    a.set_title("mse vs degree")
    a.set_xlabel("(d) degree")
    a.set_ylim(0, 25)
    a.legend()
    fig.tight_layout()
    return savefig(fig, CH, "fig1-7", out)


def fig_1_8(out=None):
    """K-means with K = 3 on the Iris petal features."""
    X, y = iris()
    P = X[:, 2:4]
    mu, z, J = kmeans(P, 3, seed=1)
    fig, ax = plt.subplots(1, 2, figsize=(8.4, 3.4), sharey=True)
    ax[0].scatter(P[:, 0], P[:, 1], s=14, color="#444")
    cols = [BLUE, RED, GREEN]
    order = np.argsort(mu[:, 0])
    for r, k in enumerate(order):
        ax[1].scatter(P[z == k, 0], P[z == k, 1], s=14, color=cols[r], label="cluster %d" % r)
    ax[1].scatter(mu[order, 0], mu[order, 1], marker="*", s=140, color="k", zorder=5)
    for a, t in zip(ax, ("(a) no labels", "(b) K-means, K = 3, distortion %.1f" % J)):
        a.set_xlabel(IRIS_FEATS[2])
        a.set_title(t, fontsize=9)
    ax[0].set_ylabel(IRIS_FEATS[3])
    ax[1].legend(loc="upper left", fontsize=8)
    fig.tight_layout()
    return savefig(fig, CH, "fig1-8", out)


def fig_1_9(out=None):
    """PCA of the first three Iris features: a 2d plane through 3d data."""
    X, y = iris()
    X3 = X[:, :3]
    mu, W, Z, s = pca(X3, 2)
    Xh = Z @ W.T + mu
    fig = plt.figure(figsize=(9.0, 4.2))
    a = fig.add_subplot(1, 2, 1, projection="3d")
    for c in range(3):
        a.scatter(*X3[y == c].T, s=10, color=CLS[c], label=IRIS_NAMES[c], depthshade=False)
    a.set_xlabel("sepal length")
    a.set_ylabel("sepal width")
    a.set_zlabel("petal length")
    a.legend(fontsize=7, loc="upper left")
    a.set_title("(a) the data, coloured by class", fontsize=9, y=-0.1)
    b = fig.add_subplot(1, 2, 2, projection="3d")
    b.scatter(*X3.T, s=8, color=RED, depthshade=False)
    b.scatter(*Xh.T, s=8, color="k", depthshade=False)
    g = np.array([[-1, -1], [1, -1], [1, 1], [-1, 1]]) * 2.2
    corners = mu + g @ W.T
    from mpl_toolkits.mplot3d.art3d import Poly3DCollection
    b.add_collection3d(Poly3DCollection([corners], alpha=0.15, color=BLUE))
    b.set_xlabel("sepal length")
    b.set_ylabel("sepal width")
    b.set_zlabel("petal length")
    b.set_title("(b) fitted plane: data (red), x = Wz + mu (black)", fontsize=9, y=-0.1)
    for ax_ in (a, b):
        ax_.view_init(18, -55)
    fig.tight_layout()
    return savefig(fig, CH, "fig1-9", out)


def fig_1_12(out=None):
    """The first 25 MNIST training digits."""
    X, y = common.mnist(train=True)
    fig, ax = plt.subplots(5, 5, figsize=(3.9, 4.1))
    for i, a in enumerate(ax.ravel()):
        a.imshow(X[i].reshape(28, 28), cmap="gray_r")
        a.set_title(str(y[i]), fontsize=8, pad=1)
        a.axis("off")
    fig.tight_layout()
    return savefig(fig, CH, "fig1-12", out)


def fig_1_15(out=None):
    """A TF-IDF term-document matrix for a small corpus of twelve sentences."""
    vocab, TF, IDF, M = tfidf(CORPUS)
    # order terms by the document in which they peak, to show the block structure
    peak = M.argmax(1)
    o = np.lexsort((np.arange(len(vocab)), peak))
    fig, ax = plt.subplots(figsize=(6.4, 7.6))
    im = ax.imshow(M[o], cmap="Greys", aspect="auto")
    ax.set_yticks(range(len(vocab)))
    ax.set_yticklabels([vocab[i] for i in o], fontsize=7)
    ax.set_xticks(range(len(CORPUS)))
    ax.set_xticklabels(["d%d" % (j + 1) for j in range(len(CORPUS))], fontsize=8)
    ax.set_xlabel("document (1-4 weather, 5-8 cooking, 9-12 football)")
    fig.colorbar(im, ax=ax, fraction=0.04, pad=0.02, label="TF-IDF")
    fig.tight_layout()
    return savefig(fig, CH, "fig1-15", out)


def fig_1_S1(out=None):
    """Missing data: three mechanisms and what mean imputation does to the mean of x2."""
    S = missing_sample()
    x1 = S["z1"]
    x2 = 2.0 + S["rho"] * S["z1"] + np.sqrt(1 - S["rho"] ** 2) * S["z2"]
    cfg = [("mcar", "MCAR", 0.0, -0.4), ("mar", "MAR (depends on x1)", 2.0, -0.5), ("nmar", "NMAR (depends on x2)", 2.0, -0.5)]
    fig, ax = plt.subplots(2, 3, figsize=(9.6, 5.6), gridspec_kw=dict(height_ratios=[1.3, 1]))
    for k, (kind, lab, st, ba) in enumerate(cfg):
        miss = S["u"] < missing_probability(kind, x1, x2, st, ba)
        R = missing_summary(S, kind, st, ba)
        a = ax[0, k]
        a.scatter(x1[~miss], x2[~miss], s=5, color=BLUE, alpha=0.6, label="observed")
        a.scatter(x1[miss], x2[miss], s=5, color=RED, alpha=0.6, label="x2 missing")
        a.set_title("%s: %.0f%% missing" % (lab, 100 * R["frac_missing"]), fontsize=9)
        a.set_xlabel("x1")
        a.set_ylabel("x2")
        if k == 0:
            a.legend(fontsize=7, markerscale=2)
        b = ax[1, k]
        vals = [R["true_mean"], R["mean_cc"], R["mean_reg"]]
        b.bar(["full data", "observed\nmean", "regression\non x1"], vals, color=[GREY, ORANGE, GREEN])
        b.axhline(R["true_mean"], color="k", lw=0.8, ls=":")
        b.set_ylim(1.2, 2.4)
        b.set_ylabel("estimate of E x2")
        b.tick_params(axis="x", labelsize=6.5)
    fig.tight_layout()
    return savefig(fig, CH, "fig1-S1", out)


def optimism_experiment(reps=2000, seed=3, maxdeg=12):
    """Average train MSE and test MSE at the same inputs (fresh noise) for fixed design x = 0..20."""
    rng = np.random.default_rng(seed)
    x = np.arange(21.0)
    f = f_true_1d(x)
    tr = np.zeros(maxdeg + 1)
    te = np.zeros(maxdeg + 1)
    for _ in range(reps):
        y = f + SIGMA_1D * rng.standard_normal(21)
        yn = f + SIGMA_1D * rng.standard_normal(21)
        for d in range(maxdeg + 1):
            c = poly_fit(x, y, d)
            yh = poly_eval(c, x)
            tr[d] += mse(y, yh)
            te[d] += mse(yn, yh)
    return tr / reps, te / reps


def fig_1_S2(out=None):
    """Optimism of the training error: the gap is 2 sigma^2 p / N."""
    tr, te = optimism_experiment(reps=1500)
    d = np.arange(len(tr))
    p = d + 1
    fig, ax = plt.subplots(1, 2, figsize=(8.4, 3.2))
    ax[0].plot(d, te, "x-", color=RED, label="test (fresh noise, same x)")
    ax[0].plot(d, tr, "s-", color=BLUE, ms=4, label="train")
    ax[0].axhline(SIGMA_1D ** 2, color=GREY, ls=":", lw=1)
    ax[0].set_xlabel("degree")
    ax[0].set_ylabel("average MSE over 1500 data sets")
    ax[0].set_ylim(0, 20)
    ax[0].legend(fontsize=8)
    ax[1].plot(d, te - tr, "o", color=PURPLE, label="simulated gap")
    ax[1].plot(d, 2 * SIGMA_1D ** 2 * p / 21, "-", color="k", label=r"$2\sigma^2 p/N$")
    ax[1].set_xlabel("degree")
    ax[1].set_ylabel("test MSE minus train MSE")
    ax[1].legend(fontsize=8)
    fig.tight_layout()
    return savefig(fig, CH, "fig1-S2", out)


# ====================================================================== JSON for the demos
def export_json():
    os.makedirs(DATA_JSON, exist_ok=True)
    D = poly_data()
    out = {k: [round(float(v), 8) for v in D[k]] for k in D}
    out["sigma"] = SIGMA_1D
    out["f"] = dict(a=0.1057692307692308, b=-1.7403846153846154, c=2.0)
    with open(os.path.join(DATA_JSON, "ch01-poly.json"), "w") as fh:
        json.dump(out, fh, separators=(",", ":"))
    X, y = iris()
    rng = np.random.default_rng(7)
    split = np.zeros(150, int)       # 1 = test: 17, 17 and 16 flowers of the three classes (50 in all)
    for c, nt in zip(range(3), (17, 17, 16)):
        idx = np.where(y == c)[0]
        split[rng.choice(idx, nt, replace=False)] = 1
    with open(os.path.join(DATA_JSON, "ch01-iris.json"), "w") as fh:
        json.dump(dict(X=[[float(v) for v in r] for r in X], y=[int(v) for v in y], test=[int(v) for v in split],
                       names=IRIS_NAMES, features=IRIS_FEATS), fh, separators=(",", ":"))
    S = missing_sample()
    with open(os.path.join(DATA_JSON, "ch01-missing.json"), "w") as fh:
        json.dump(dict(z1=[float(v) for v in S["z1"]], z2=[float(v) for v in S["z2"]], u=[float(v) for v in S["u"]], rho=S["rho"]), fh, separators=(",", ":"))
    print("wrote data/ch01-poly.json, ch01-iris.json, ch01-missing.json")


def fig_data(out=None):
    """(not a figure) export the small JSON files the browser demos read."""
    export_json()


FIGURES = {"1.3": fig_1_3, "1.4": fig_1_4, "1.5": fig_1_5, "1.6": fig_1_6, "1.7": fig_1_7, "1.8": fig_1_8,
           "1.9": fig_1_9, "1.12": fig_1_12, "1.15": fig_1_15, "1.S1": fig_1_S1, "1.S2": fig_1_S2, "data": fig_data}

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