"""James et al. (2021, 2023), Chapter 9: Support Vector Machines.

Reproduces the figures of Chapter 9 of G. James, D. Witten, T. Hastie and R. Tibshirani, An Introduction
to Statistical Learning with Applications in R, 2nd edition (Springer, 2021), pp. 367-402 (the same
figures appear in the Python edition of 2023, with J. Taylor), written from scratch with numpy, scipy,
scikit-learn and matplotlib. scikit-learn's SVC (LIBSVM, the same solver as R's e1071::svm) fits the
support vector classifiers and machines; this file adds:

* hard_margin: the maximal margin hyperplane (9.9)-(9.11), solved directly as the quadratic programme
  min ||beta||^2 / 2 subject to y_i (beta_0 + x_i' beta) >= 1 (Filling the gap 9.2 of the notes);
* budget_fit: the support vector classifier in the book's budget form (9.12)-(9.15): the cost C' of
  LIBSVM that spends exactly the budget C = sum_i eps_i, found by bisection, with M = 1/||beta||;
* budget_direct: (9.12)-(9.15) solved as written (variables beta, eps, M, constraint ||beta|| = 1), used
  to confirm that the two forms give the same hyperplane;
* hinge_fit and ridge_logistic: the loss + penalty problems (9.25) with the hinge and the logistic loss;
* roc_points and auc: ROC curves and their area for any score.

Figures reproduced: 9.1-9.12 (all of them). The data of Figures 9.2-9.9 are not published; they are
simulated here (numpy default_rng, seeds in the code) to look like the book's. Figures 9.10 and 9.11
use the Heart data: the 297 complete cases, 16 columns (11 numeric, ChestPain and Thal as dummies),
standardised with the training means and standard deviations, a random split (default_rng(1)) into
207 training and 90 test patients, LDA, a support vector classifier (cost 1) and radial SVMs (cost 1)
with gamma = 0.001, 0.01 and 0.1. Run `python3 ch09_support_vector_machines.py --list`, or `--fig 9.7`,
or `--fig demos` to write the data of the three demonstrations to ../data/ch09-*.json and print the
numbers quoted in the notes.
"""
import os

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

import json

import numpy as np
import pandas as pd
from scipy.optimize import minimize
from sklearn.svm import SVC

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

HERE = os.path.dirname(os.path.abspath(__file__))
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
PURPLE = "#b13fbf"                           # the book's purple class (more distinct from blue than common.PURPLE)
TOL = 1e-7                                  # LIBSVM stopping tolerance used for the exact figures


# ======================================================================== solvers
def svc(X, y, cost, **kw):
    """LIBSVM through scikit-learn, with a tight tolerance; kernel defaults to linear."""
    kw.setdefault("kernel", "linear")
    return SVC(C=cost, tol=TOL, **kw).fit(X, y)


def coef(model):
    """beta_0, beta of a fitted linear SVC (positive f predicts the larger label)."""
    return model.intercept_[0], (model.dual_coef_ @ model.support_vectors_).ravel()


def hard_margin(X, y):
    """Maximal margin hyperplane: minimise ||beta||^2/2 subject to y_i (beta_0 + x_i'beta) >= 1.
    Returns beta_0, beta (in the canonical scaling, margin M = 1/||beta||). Requires separable data."""
    p = X.shape[1]
    cons = {"type": "ineq", "fun": lambda w: y * (w[0] + X @ w[1:]) - 1, "jac": lambda w: y[:, None] * np.column_stack([np.ones(len(y)), X])}
    res = minimize(lambda w: 0.5 * w[1:] @ w[1:], np.zeros(p + 1), jac=lambda w: np.r_[0, w[1:]],
                   constraints=[cons], method="SLSQP", options={"ftol": 1e-14, "maxiter": 500})
    if not res.success:
        raise RuntimeError("no separating hyperplane: " + res.message)
    return res.x[0], res.x[1:]


def slacks(b0, beta, X, y):
    """eps_i = max(0, 1 - y_i f(x_i)) for the canonical scaling: the slack variables of (9.14)."""
    return np.maximum(0, 1 - y * (b0 + X @ beta))


def budget_fit(X, y, budget, lo=-5.0, hi=3.0):
    """Support vector classifier with budget C (9.12)-(9.15). The cost form min ||beta||^2/2 + C' sum xi_i
    has the same solutions; its total slack sum xi_i falls as C' grows, so bisect on log C' until the slack
    equals the budget. Returns a dict with beta_0, beta (canonical), M, eps, cost and the support vectors."""
    def total(lc):
        m = svc(X, y, 10 ** lc)
        b0, b = coef(m)
        return slacks(b0, b, X, y).sum(), m
    for _ in range(80):
        mid = 0.5 * (lo + hi)
        s, m = total(mid)
        if s > budget:
            lo = mid
        else:
            hi = mid
        if hi - lo < 1e-7:
            break
    s, m = total(0.5 * (lo + hi))
    if s > budget + 1e-4 * max(1.0, budget):
        raise ValueError("budget %g is below the smallest feasible total slack %g" % (budget, s))
    b0, b = coef(m)
    return {"b0": b0, "beta": b, "M": 1 / np.linalg.norm(b), "eps": slacks(b0, b, X, y), "cost": 10 ** (0.5 * (lo + hi)),
            "sv": np.sort(m.support_), "spent": s}


def budget_direct(X, y, budget, start=None):
    """(9.12)-(9.15) as written: maximise M over (beta_0, beta, eps, M) with ||beta|| = 1,
    y_i (beta_0 + x_i'beta) >= M (1 - eps_i), eps_i >= 0, sum eps_i <= budget. Solved by SLSQP."""
    n, p = X.shape
    if start is None:
        start = np.r_[0.0, np.ones(p) / np.sqrt(p), np.full(n, budget / n), 0.1]
    cons = [{"type": "eq", "fun": lambda w: w[1:p + 1] @ w[1:p + 1] - 1},
            {"type": "ineq", "fun": lambda w: y * (w[0] + X @ w[1:p + 1]) - w[-1] * (1 - w[p + 1:p + 1 + n])},
            {"type": "ineq", "fun": lambda w: budget - w[p + 1:p + 1 + n].sum()}]
    bounds = [(None, None)] * (p + 1) + [(0, None)] * n + [(0, None)]
    res = minimize(lambda w: -w[-1], start, constraints=cons, bounds=bounds, method="SLSQP",
                   options={"ftol": 1e-13, "maxiter": 2000})
    w = res.x
    return {"b0": w[0], "beta": w[1:p + 1], "eps": w[p + 1:p + 1 + n], "M": w[-1], "ok": res.success}


def hinge_fit(X, y, lam):
    """(9.25): minimise sum_i max(0, 1 - y_i f(x_i)) + lam ||beta||^2, i.e. LIBSVM with cost 1/(2 lam)."""
    return coef(svc(X, y, 1 / (2 * lam)))


def ridge_logistic(X, y, lam, iters=100):
    """The logistic analogue of (9.25): minimise sum_i log(1 + exp(-y_i f(x_i))) + lam ||beta||^2
    (intercept not penalised), by Newton's method. y in {-1, +1}."""
    n, p = X.shape
    A = np.column_stack([np.ones(n), X])
    w = np.zeros(p + 1)
    P = 2 * lam * np.diag(np.r_[0, np.ones(p)])
    for _ in range(iters):
        m = y * (A @ w)
        s = 1 / (1 + np.exp(m))                        # = 1 - sigma(y f): each point's pull
        g = -A.T @ (y * s) + P @ w
        Hm = A.T @ (A * (s * (1 - s))[:, None]) + P
        step = np.linalg.solve(Hm, g)
        w -= step
        if np.max(np.abs(step)) < 1e-13:
            break
    return w[0], w[1:]


def roc_points(score, positive):
    """False and true positive rates over all thresholds (predict positive when score >= t)."""
    order = np.argsort(-score, kind="mergesort")
    s, pos = score[order], positive[order].astype(float)
    tp, fp = np.cumsum(pos), np.cumsum(1 - pos)
    last = np.r_[np.diff(s) != 0, True]                 # keep one point per distinct score
    return np.r_[0, fp[last] / fp[-1]], np.r_[0, tp[last] / tp[-1]]


def auc(score, positive):
    """Area under the ROC curve = Pr(score of a random positive > score of a random negative), ties 1/2."""
    from scipy.stats import rankdata
    r = rankdata(score)
    n1 = positive.sum()
    return (r[positive].sum() - n1 * (n1 + 1) / 2) / (n1 * (len(score) - n1))


def lda_score(Xtr, ytr, X):
    """LDA log-odds of class 1 against class 0 (pooled covariance, divisor n - 2, priors n_k / n)."""
    mu = [Xtr[ytr == k].mean(0) for k in (0, 1)]
    S = sum((Xtr[ytr == k] - mu[k]).T @ (Xtr[ytr == k] - mu[k]) for k in (0, 1)) / (len(ytr) - 2)
    a = np.linalg.solve(S, mu[1] - mu[0])
    pi1 = ytr.mean()
    return X @ a - 0.5 * (mu[1] + mu[0]) @ a + np.log(pi1 / (1 - pi1))


# ======================================================================== data
def separable_data(n=20, seed=3):
    """Two classes of n/2 points in [-1, 3]^2 that a line separates (blue above, purple below)."""
    rng = np.random.default_rng(seed)
    while True:
        X = rng.uniform(-1, 3, size=(4 * n, 2))
        d = X[:, 1] - 0.9 * X[:, 0] - 0.4                  # signed position relative to a line
        blue, purple = X[d > 0.35][: n // 2], X[d < -0.35][: n // 2]
        if len(blue) == n // 2 and len(purple) == n // 2:
            return np.vstack([blue, purple]), np.r_[np.ones(n // 2), -np.ones(n // 2)]


def overlapping_data(n=20, seed=11, shift=1.0):
    rng = np.random.default_rng(seed)
    X = rng.standard_normal((n, 2)) * 0.8
    y = np.r_[np.ones(n // 2), -np.ones(n - n // 2)]
    X[y == 1] += [0.0, shift]
    X[y == -1] += [shift, -0.2]
    return X + [1.2, 0.5], y


def figure7_data():
    """40 points for Figure 9.7 (default_rng(7)); separable, but only just."""
    rng = np.random.default_rng(7)
    X = rng.standard_normal((40, 2))
    y = np.r_[np.ones(20), -np.ones(20)]
    X[y == 1] += [-0.5, 1.5]
    X[y == -1] += [1.5, -0.83]
    return X, y


def nonlinear_data(n=100, seed=8):
    """Figures 9.8 and 9.9: points along the diagonal; purple in the middle, blue at both ends."""
    rng = np.random.default_rng(seed)
    t = rng.uniform(-4.2, 4.2, n)
    X = np.column_stack([t, t]) + rng.normal(0, 0.75, (n, 2))
    y = np.where(np.abs(t) > 1.9, 1, -1)
    return X, y


def heart_data(seed=1, ntrain=207):
    """Heart data: 297 complete cases, 16 standardised columns, random 207 / 90 split."""
    H = common.isl_data("Heart").dropna().reset_index(drop=True)
    y = (H["AHD"] == "Yes").to_numpy().astype(int)
    Xdf = pd.get_dummies(H.drop(columns=[H.columns[0], "AHD"]), columns=["ChestPain", "Thal"], drop_first=True, dtype=float)
    X = Xdf.to_numpy(float)
    perm = np.random.default_rng(seed).permutation(len(y))
    tr = np.zeros(len(y), bool)
    tr[perm[:ntrain]] = True
    m, s = X[tr].mean(0), X[tr].std(0, ddof=1)
    return (X - m) / s, y, tr, list(Xdf.columns)


# ======================================================================== drawing helpers
COL = {1: BLUE, -1: PURPLE}


def _points(ax, X, y, s=26, sv=None):
    for c in (1, -1):
        m = y == c
        ax.scatter(X[m, 0], X[m, 1], s=s, color=COL[c], zorder=3, edgecolors="none")
    if sv is not None:
        ax.scatter(X[sv, 0], X[sv, 1], s=s * 3.2, facecolors="none", edgecolors="k", linewidths=1.0, zorder=4)


def _line(ax, b0, beta, xlim, level=0.0, **kw):
    """Draw beta_0 + beta'x = level across xlim."""
    xs = np.array(xlim, float)
    ax.plot(xs, (level - b0 - beta[0] * xs) / beta[1], **kw)


def _grid_shade(ax, f, xlim, ylim, n=34):
    g1, g2 = np.meshgrid(np.linspace(*xlim, n), np.linspace(*ylim, n))
    v = f(np.column_stack([g1.ravel(), g2.ravel()]))
    ax.scatter(g1.ravel(), g2.ravel(), s=2.0, c=np.where(v > 0, BLUE, PURPLE), alpha=0.6, zorder=1, edgecolors="none")


def _box(ax, xlim, ylim):
    ax.set(xlim=xlim, ylim=ylim, xlabel="$X_1$", ylabel="$X_2$")


# ======================================================================== figures
def fig_9_1(out=None):
    """Figure 9.1: the hyperplane 1 + 2 X1 + 3 X2 = 0 and its two half-planes."""
    fig, ax = plt.subplots(figsize=(4.2, 4.0))
    lim = (-1.5, 1.5)
    _grid_shade(ax, lambda G: 1 + 2 * G[:, 0] + 3 * G[:, 1], lim, lim, n=40)
    _line(ax, 1.0, np.array([2.0, 3.0]), lim, color="k", lw=2)
    ax.text(0.8, 1.1, r"$1+2X_1+3X_2>0$", color=BLUE, ha="center", fontsize=9, bbox=dict(fc="white", ec="none", alpha=0.85))
    ax.text(-0.75, -1.25, r"$1+2X_1+3X_2<0$", color=PURPLE, ha="center", fontsize=9, bbox=dict(fc="white", ec="none", alpha=0.85))
    _box(ax, lim, lim)
    savefig(fig, 9, "fig9-1", out)


def fig_9_2(out=None):
    """Figure 9.2: three separating hyperplanes; the classifier of one of them."""
    X, y = separable_data()
    b0, beta = hard_margin(X, y)
    lim = (-1, 3)
    fig, ax = plt.subplots(1, 2, figsize=(8.2, 4.0))
    # three separating lines: the maximal margin one, and two tilted/shifted ones, each checked to separate
    lines = [(b0, beta)]
    for ang, sh in ((0.18, 0.25), (-0.22, -0.2)):
        R = np.array([[np.cos(ang), -np.sin(ang)], [np.sin(ang), np.cos(ang)]])
        bb = R @ beta
        b = b0 + sh * np.linalg.norm(beta) - (bb - beta) @ X.mean(0)
        assert np.all(y * (b + X @ bb) > 0), "line does not separate"
        lines.append((b, bb))
    for b, bb in lines:
        _line(ax[0], b, bb, lim, color="k", lw=1.6)
    _points(ax[0], X, y)
    _box(ax[0], lim, lim)
    b, bb = lines[1]
    _grid_shade(ax[1], lambda G: b + G @ bb, lim, lim)
    _line(ax[1], b, bb, lim, color="k", lw=1.6)
    _points(ax[1], X, y)
    _box(ax[1], lim, lim)
    savefig(fig, 9, "fig9-2", out)


def fig_9_3(out=None):
    """Figure 9.3: the maximal margin hyperplane, its margins and support vectors."""
    X, y = separable_data()
    b0, beta = hard_margin(X, y)
    lim = (-1, 3)
    M = 1 / np.linalg.norm(beta)
    on = np.abs(y * (b0 + X @ beta) - 1) < 1e-6
    fig, ax = plt.subplots(figsize=(4.2, 4.0))
    _grid_shade(ax, lambda G: b0 + G @ beta, lim, lim)
    _line(ax, b0, beta, lim, color="k", lw=2)
    _line(ax, b0, beta, lim, level=1, color="k", lw=1, ls="--")
    _line(ax, b0, beta, lim, level=-1, color="k", lw=1, ls="--")
    _points(ax, X, y)
    u = beta / np.linalg.norm(beta)
    for x0, c in zip(X[on], y[on]):
        foot = x0 - c * M * u
        ax.annotate("", xy=foot, xytext=x0, arrowprops=dict(arrowstyle="<->", color="k", lw=0.9))
    _box(ax, lim, lim)
    savefig(fig, 9, "fig9-3", out)
    return {"M": M, "n_sv": int(on.sum()), "beta0": b0, "beta": beta}


def fig_9_4(out=None):
    """Figure 9.4: two classes that no hyperplane separates."""
    X, y = overlapping_data()
    fig, ax = plt.subplots(figsize=(4.2, 4.0))
    _points(ax, X, y)
    ax.set(xlabel="$X_1$", ylabel="$X_2$")
    savefig(fig, 9, "fig9-4", out)


def fig_9_5(out=None):
    """Figure 9.5: one added observation moves the maximal margin hyperplane a lot."""
    X, y = separable_data()
    b0, beta = hard_margin(X, y)
    lim = (-1, 3)
    # a new blue point just above the old hyperplane, still separable
    new = np.array([2.35, 2.12])
    X2, y2 = np.vstack([X, new]), np.r_[y, 1]
    c0, gamma = hard_margin(X2, y2)
    fig, ax = plt.subplots(1, 2, figsize=(8.2, 4.0))
    _line(ax[0], b0, beta, lim, color="k", lw=2)
    _line(ax[0], b0, beta, lim, level=1, color="k", lw=1, ls="--")
    _line(ax[0], b0, beta, lim, level=-1, color="k", lw=1, ls="--")
    _points(ax[0], X, y)
    _box(ax[0], lim, lim)
    _line(ax[1], b0, beta, lim, color="k", lw=1.2, ls="--")
    _line(ax[1], c0, gamma, lim, color="k", lw=2)
    _points(ax[1], X2, y2)
    ax[1].scatter(*new, s=90, facecolors="none", edgecolors=BLUE, linewidths=1.4)
    _box(ax[1], lim, lim)
    savefig(fig, 9, "fig9-5", out)
    return {"M_before": 1 / np.linalg.norm(beta), "M_after": 1 / np.linalg.norm(gamma)}


def fig_9_6(out=None):
    """Figure 9.6: a support vector classifier on ten numbered points; then with points 11 and 12."""
    rng = np.random.default_rng(6)
    purple = rng.normal([1.0, 0.4], [0.75, 0.65], (6, 2))
    blue = rng.normal([1.1, 2.6], [0.75, 0.6], (4, 2))
    X = np.vstack([purple, blue])
    y = np.r_[-np.ones(6), np.ones(4)]
    X12 = np.vstack([X, [[1.6, 2.9], [0.6, 0.6]]])       # 11 purple among the blue, 12 blue among the purple
    y12 = np.r_[y, -1, 1]
    info = []
    fig, ax = plt.subplots(1, 2, figsize=(8.2, 4.0))
    for a, (XX, yy) in zip(ax, [(X, y), (X12, y12)]):
        m = svc(XX, yy, 0.3)
        b0, beta = coef(m)
        xlim, ylim = (-1.2, 2.6), (-0.8, 4.2)
        _line(a, b0, beta, xlim, color="k", lw=2)
        _line(a, b0, beta, xlim, level=1, color="k", lw=1, ls="--")
        _line(a, b0, beta, xlim, level=-1, color="k", lw=1, ls="--")
        for i, (pt, c) in enumerate(zip(XX, yy)):
            a.text(pt[0], pt[1], str(i + 1), color=COL[c], ha="center", va="center", fontsize=10, fontweight="bold")
        _box(a, xlim, ylim)
        e = slacks(b0, beta, XX, yy)
        info.append({"eps": e.round(3).tolist(), "sv": (np.sort(m.support_) + 1).tolist()})
    savefig(fig, 9, "fig9-6", out)
    return info


def fig_9_7(out=None):
    """Figure 9.7: the support vector classifier for four values of the budget C (largest top left)."""
    X, y = figure7_data()
    budgets = [16.0, 8.0, 4.0, 2.0]
    fig, axes = plt.subplots(2, 2, figsize=(7.6, 7.6))
    fig.subplots_adjust(hspace=0.38, wspace=0.28)
    info = []
    for a, B in zip(axes.ravel(), budgets):
        r = budget_fit(X, y, B)
        xlim, ylim = (-2.6, 3.6), (-3.2, 3.8)
        _line(a, r["b0"], r["beta"], xlim, color="k", lw=2)
        _line(a, r["b0"], r["beta"], xlim, level=1, color="k", lw=1, ls="--")
        _line(a, r["b0"], r["beta"], xlim, level=-1, color="k", lw=1, ls="--")
        _points(a, X, y, sv=r["sv"])
        a.set_title("budget C = %g: M = %.2f, %d support vectors" % (B, r["M"], len(r["sv"])), fontsize=9.5)
        _box(a, xlim, ylim)
        info.append({"budget": B, "M": r["M"], "n_sv": len(r["sv"]), "cost": r["cost"], "wrong_side": int(np.sum(r["eps"] > 1))})
    savefig(fig, 9, "fig9-7", out)
    return info


def fig_9_8(out=None):
    """Figure 9.8: a non-linear boundary; the support vector classifier fails."""
    X, y = nonlinear_data()
    m = svc(X, y, 1.0)
    b0, beta = coef(m)
    lim = (-5, 5)
    fig, ax = plt.subplots(1, 2, figsize=(8.2, 4.0))
    _points(ax[0], X, y)
    _box(ax[0], lim, lim)
    _grid_shade(ax[1], lambda G: b0 + G @ beta, lim, lim)
    _line(ax[1], b0, beta, lim, color="k", lw=2)
    _line(ax[1], b0, beta, lim, level=1, color="k", lw=1, ls="--")
    _line(ax[1], b0, beta, lim, level=-1, color="k", lw=1, ls="--")
    _points(ax[1], X, y)
    _box(ax[1], lim, lim)
    savefig(fig, 9, "fig9-8", out)
    return {"train_err_linear": float(np.mean(m.predict(X) != y))}


def fig_9_9(out=None):
    """Figure 9.9: an SVM with a degree-3 polynomial kernel (left) and a radial kernel (right)."""
    X, y = nonlinear_data()
    lim = (-5, 5)
    models = [svc(X, y, 1.0, kernel="poly", degree=3, gamma=1, coef0=1),
              svc(X, y, 1.0, kernel="rbf", gamma=0.5)]
    fig, ax = plt.subplots(1, 2, figsize=(8.2, 4.0))
    g1, g2 = np.meshgrid(np.linspace(*lim, 300), np.linspace(*lim, 300))
    G = np.column_stack([g1.ravel(), g2.ravel()])
    errs = []
    for a, m in zip(ax, models):
        f = m.decision_function(G).reshape(g1.shape)
        _grid_shade(a, m.decision_function, lim, lim)
        a.contour(g1, g2, f, levels=[-1, 0, 1], colors="k", linestyles=["--", "-", "--"], linewidths=[1, 2, 1])
        _points(a, X, y)
        _box(a, lim, lim)
        errs.append(float(np.mean(m.predict(X) != y)))
    savefig(fig, 9, "fig9-9", out)
    return {"train_err_poly3": errs[0], "train_err_radial": errs[1]}


def heart_scores():
    """Scores of LDA, the support vector classifier and the three radial SVMs on the Heart data."""
    Z, y, tr, _ = heart_data()
    out = {"lda": lda_score(Z[tr], y[tr], Z)}
    m = svc(Z[tr], y[tr], 1.0)
    out["svc"] = m.decision_function(Z)
    nsv = {"svc": int(m.n_support_.sum())}
    for g in (1e-3, 1e-2, 1e-1):
        m = svc(Z[tr], y[tr], 1.0, kernel="rbf", gamma=g)
        out["rbf%g" % g] = m.decision_function(Z)
        nsv["rbf%g" % g] = int(m.n_support_.sum())
    return out, y, tr, nsv


def _roc_figure(name, use_train, out):
    sc, y, tr, _ = heart_scores()
    rows = tr if use_train else ~tr
    fig, ax = plt.subplots(1, 2, figsize=(8.2, 4.0))
    res = {}
    specs = [[("svc", "Support Vector Classifier", RED, "-"), ("lda", "LDA", BLUE, "-")],
             [("svc", "Support Vector Classifier", RED, "-"), ("rbf0.001", r"SVM: $\gamma=10^{-3}$", "k", "-"),
              ("rbf0.01", r"SVM: $\gamma=10^{-2}$", "#2ca02c", "-"), ("rbf0.1", r"SVM: $\gamma=10^{-1}$", BLUE, "-")]]
    for a, spec in zip(ax, specs):
        for key, lab, col, ls in spec:
            fpr, tpr = roc_points(sc[key][rows], y[rows] == 1)
            A = auc(sc[key][rows], y[rows] == 1)
            res[key] = A
            a.plot(fpr, tpr, color=col, ls=ls, lw=1.8, label="%s (AUC %.3f)" % (lab, A))
        a.plot([0, 1], [0, 1], ":", color=GREY, lw=1)
        a.set(xlabel="False positive rate", ylabel="True positive rate", xlim=(0, 1), ylim=(0, 1.01))
        a.legend(loc="lower right", fontsize=8.5)
    savefig(fig, 9, name, out)
    return res


def fig_9_10(out=None):
    """Figure 9.10: ROC curves on the Heart training data."""
    return _roc_figure("fig9-10", True, out)


def fig_9_11(out=None):
    """Figure 9.11: ROC curves on the Heart test data."""
    return _roc_figure("fig9-11", False, out)


def fig_9_12(out=None):
    """Figure 9.12: the hinge loss and the logistic regression loss against y f(x)."""
    u = np.linspace(-6, 2, 401)
    fig, ax = plt.subplots(figsize=(4.8, 3.9))
    ax.plot(u, np.maximum(0, 1 - u), color=BLUE, lw=2, label="SVM loss (hinge)")
    ax.plot(u, np.log1p(np.exp(-u)), color=RED, lw=2, label="logistic regression loss")
    ax.axvline(1, color=GREY, lw=0.8, ls=":")
    ax.set(xlabel=r"$y_i(\beta_0+\beta_1x_{i1}+\dots+\beta_px_{ip})$", ylabel="Loss", ylim=(0, 8))
    ax.legend(loc="upper right")
    savefig(fig, 9, "fig9-12", out)


# ======================================================================== demonstrations
def r_lab_data():
    """The R lab's 20 points (written by ch09_lab.R): original and shifted by 0.5 (barely separable)."""
    d = pd.read_csv(os.path.join(HERE, "cache", "ch09_rlab_linear.csv"))
    X, y = d[["x1", "x2"]].to_numpy(), d["y"].to_numpy().astype(float)
    Xs = X.copy()
    Xs[y == 1] += 0.5
    return X, Xs, y


def python_lab_data():
    """The Python lab's 50 points (default_rng(1)), Section 9.6.1 of James et al. (2023)."""
    rng = np.random.default_rng(1)
    X = rng.standard_normal((50, 2))
    y = np.array([-1.0] * 25 + [1.0] * 25)
    X[y == 1] += 1
    return X, y


def demos(out=None):
    os.makedirs(DATA_OUT, exist_ok=True)
    r4 = lambda a: np.round(np.asarray(a, float), 6).tolist()
    # == budget demo: the R lab's data
    X, Xs, y = r_lab_data()
    refs = {}
    for name, XX, budgets in (("orig", X, (6.5, 8, 10, 12)), ("sep", Xs, (0.5, 1, 2, 4, 8))):
        rows = []
        for B in budgets:
            r = budget_fit(XX, y, B)
            rows.append({"budget": B, "M": r["M"], "cost": r["cost"], "nsv": len(r["sv"]), "b0": r["b0"], "beta": r4(r["beta"])})
        refs[name] = rows
    b0, beta = hard_margin(Xs, y)
    refs["sep_hard"] = {"M": 1 / np.linalg.norm(beta), "b0": b0, "beta": r4(beta),
                        "nsv": int(np.sum(np.abs(y * (b0 + Xs @ beta) - 1) < 1e-6))}
    m = svc(X, y, 1e3)                                   # the hinge minimiser is reached by cost 10 on these data
    refs["orig_min_budget"] = float(slacks(*coef(m), X, y).sum())
    J = {"x": r4(X), "y": y.astype(int).tolist(), "shift": 0.5, "ref": refs}
    with open(os.path.join(DATA_OUT, "ch09-budget.json"), "w") as fh:
        json.dump(J, fh, separators=(",", ":"))
    print("budget demo: separable data, maximal margin M = %.4f with %d support vectors" % (refs["sep_hard"]["M"], refs["sep_hard"]["nsv"]))
    print("  original data: smallest budget %.4f;" % refs["orig_min_budget"],
          "; ".join("C=%g: M=%.4f cost=%.4g nsv=%d" % (q["budget"], q["M"], q["cost"], q["nsv"]) for q in refs["orig"]))
    print("  separable data:", "; ".join("C=%g: M=%.4f cost=%.4g nsv=%d" % (q["budget"], q["M"], q["cost"], q["nsv"]) for q in refs["sep"]))

    # == Heart demo
    Z, yh, tr, names = heart_data()
    sc = {}
    for g in (1e-3, 1e-2, 1e-1, 1.0):
        for cst in (0.1, 1.0, 10.0):
            mm = svc(Z[tr], yh[tr], cst, kernel="rbf", gamma=g)
            f = mm.decision_function(Z)
            sc["rbf_%g_%g" % (g, cst)] = {"auc_tr": auc(f[tr], yh[tr] == 1), "auc_te": auc(f[~tr], yh[~tr] == 1),
                                          "nsv": int(mm.n_support_.sum()), "f5": r4(f[:5]),
                                          "err_tr": float(np.mean((f[tr] > 0) != (yh[tr] == 1))),
                                          "err_te": float(np.mean((f[~tr] > 0) != (yh[~tr] == 1)))}
    for cst in (0.01, 1.0):
        mm = svc(Z[tr], yh[tr], cst)
        f = mm.decision_function(Z)
        sc["lin_%g" % cst] = {"auc_tr": auc(f[tr], yh[tr] == 1), "auc_te": auc(f[~tr], yh[~tr] == 1), "nsv": int(mm.n_support_.sum()), "f5": r4(f[:5])}
    fl = lda_score(Z[tr], yh[tr], Z)
    sc["lda"] = {"auc_tr": auc(fl[tr], yh[tr] == 1), "auc_te": auc(fl[~tr], yh[~tr] == 1), "f5": r4(fl[:5])}
    J = {"x": np.round(Z, 6).tolist(), "y": yh.tolist(), "train": tr.astype(int).tolist(), "names": names, "ref": sc}
    with open(os.path.join(DATA_OUT, "ch09-heart.json"), "w") as fh:
        json.dump(J, fh, separators=(",", ":"))
    for k, v in sc.items():
        print("Heart %-14s AUC train %.4f test %.4f" % (k, v["auc_tr"], v["auc_te"]), " SVs", v.get("nsv", "-"))

    # == hinge versus logistic demo: the Python lab's data
    Xp, yp = python_lab_data()
    hl = {}
    for lam in (0.05, 0.5, 2.0, 5.0):
        hb0, hb = hinge_fit(Xp, yp, lam)
        lb0, lb = ridge_logistic(Xp, yp, lam)
        hl["%g" % lam] = {"hinge": r4(np.r_[hb0, hb]), "logistic": r4(np.r_[lb0, lb])}
    # push every point with y f(x) > 1.5 (well beyond the margin) a distance 2 further from the boundary
    hb0, hb = hinge_fit(Xp, yp, 0.5)
    far = yp * (hb0 + Xp @ hb) > 1.5
    Xf = Xp + (far * yp)[:, None] * 2.0 * hb / np.linalg.norm(hb)
    hl["push"] = {"lam": 0.5, "far": far.astype(int).tolist(),
                  "hinge": r4(np.r_[hinge_fit(Xf, yp, 0.5)]), "logistic": r4(np.r_[ridge_logistic(Xf, yp, 0.5)])}
    J = {"x": r4(Xp), "y": yp.astype(int).tolist(), "ref": hl}
    with open(os.path.join(DATA_OUT, "ch09-hinge.json"), "w") as fh:
        json.dump(J, fh, separators=(",", ":"))
    for k, v in hl.items():
        print("hinge/logistic lambda %s: hinge %s  logistic %s" % (k, v["hinge"], v["logistic"]))


def numbers(out=None):
    """Print the numbers quoted in the notes for Figures 9.3-9.11."""
    print("Figure 9.3:", fig_9_3(out))
    print("Figure 9.5:", fig_9_5(out))
    print("Figure 9.6:", fig_9_6(out))
    for q in fig_9_7(out):
        print("Figure 9.7:", q)
    print("Figure 9.8:", fig_9_8(out))
    print("Figure 9.9:", fig_9_9(out))
    print("Figure 9.10 (training AUC):", fig_9_10(out))
    print("Figure 9.11 (test AUC):", fig_9_11(out))
    print("support vectors on the Heart data:", heart_scores()[3])


FIGURES = {
    "9.1": fig_9_1, "9.2": fig_9_2, "9.3": fig_9_3, "9.4": fig_9_4, "9.5": fig_9_5, "9.6": fig_9_6,
    "9.7": fig_9_7, "9.8": fig_9_8, "9.9": fig_9_9, "9.10": fig_9_10, "9.11": fig_9_11, "9.12": fig_9_12,
    "demos": demos, "numbers": numbers,
}

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