"""Murphy (2023), Chapter 19: Beyond the iid assumption.

Companion code for Chapter 19 of K. P. Murphy, Probabilistic Machine Learning: Advanced Topics
(MIT Press, 2023; December 2025 draft), pp. 735-770, written from scratch with numpy, scipy,
scikit-learn and PyTorch, to be read next to the lecture notes (../ch19-beyond-iid.html).
The supplement's Chapter 19 consists of the chapter title page only.

Methods
* 19.2 the four kinds of distribution shift (simulated, Figure 19.4); sensitivity of a classifier to
  input noise and noise augmentation (stand-in for Figure 19.1, a digits classifier).
* 19.3 OOD detection: likelihood versus likelihood ratio (stand-in for Figure 19.7); selective
  prediction with a plug-in network and with SGLD (Figures 19.8, 19.9); a conformal threshold on the
  OOD score (conformal_threshold).
* 19.4 data augmentation (Figure 19.1 stand-in) and distributionally robust optimisation.
* 19.5 weighted ERM for covariate shift with exact and classifier-estimated density ratios
  (logistic_newton, density_ratio_logistic, weighted_least_squares; Figure 19.10); fine-tuning as
  shrinkage towards the source solution (finetune_ridge); blackbox shift estimation and its EM
  relative for label shift (bbse, mlls_em; own Figure 19.28); the marginal-entropy objective of MEMO.
* 19.6 invariant risk minimisation on the exact moments of a spurious-feature model (own Figure 19.29);
  prototypical networks equal a Gaussian classifier with shared identity covariance.
* 19.7 continual learning: catastrophic forgetting, EWC and replay on permuted digits with the
  forward and backward transfer scores (19.41, 19.42) (own Figure 19.30); online learning,
  prequential log loss, and regret of online gradient descent (own Figure 19.31).
* 19.8 adversarial examples: the fast gradient sign method and exact worst-case margins of linear
  classifiers, adversarial training in closed form (own Figure 19.32), and the concentration-of-measure
  relation (19.52) (own Figure 19.33).

Skipped figures, with reasons: Figures 19.1 (a pretrained ResNet-50 on ImageNet), 19.2, 19.23 to 19.26
(photographs and attacks on large pretrained networks), 19.7 (a Glow model on CIFAR-10) and 19.27b
(InceptionV3) need models or images that are not available on a CPU in minutes, so own small stand-ins
replace Figures 19.1 and 19.7; Figures 19.3, 19.5, 19.6, 19.11 to 19.15, 19.16 to 19.19, 19.22 (graphical
models and schematics) contain nothing computed; Figures 19.20 and 19.21 are schematic performance
profiles, and Figure 19.30 computes the real thing for a small network.

Data: scikit-learn digits, MNIST and the Fashion-MNIST test set (cached under ~/.cache/prml-repro), and simulation
(seeds fixed in the code). Figure numbers 19.28 to 19.33 are my own extra figures.
"""
import json
import os
import sys

import numpy as np
from scipy import optimize, special, stats

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

CH = 19
HERE = os.path.dirname(os.path.abspath(__file__))
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
WORK = os.path.join(HERE, "cache", "ch19-work")
os.makedirs(WORK, exist_ok=True)


# ------------------------------------------------------------------ small numerical helpers
def logistic_newton(Phi, y, l2=1e-8, iters=50, tol=1e-10, sample_weight=None):
    """Logistic regression (labels y in {0,1}) by Newton's method (IRLS); returns the weight vector.

    Phi is the n x d design matrix (include a column of ones for the intercept); the optional
    sample_weight multiplies each log-likelihood term; l2 is a tiny ridge that keeps the Hessian
    invertible. This is the density-ratio classifier of (19.17)."""
    n, d = Phi.shape
    sw = np.ones(n) if sample_weight is None else np.asarray(sample_weight, float)
    w = np.zeros(d)
    for _ in range(iters):
        p = sigmoid(Phi @ w)
        g = Phi.T @ (sw * (p - y)) + l2 * w
        H = (Phi * (sw * p * (1 - p))[:, None]).T @ Phi + l2 * np.eye(d)
        step = np.linalg.solve(H, g)
        w = w - step
        if np.max(np.abs(step)) < tol:
            break
    return w


def poly_features(x, deg):
    """Columns 1, x, ..., x^deg."""
    return np.vander(np.asarray(x, float).ravel(), deg + 1, increasing=True)


def density_ratio_logistic(x_src, x_tgt, deg=2):
    """Estimate w(x) = q(x)/p(x) from samples by logistic regression of the domain label, (19.17)-(19.18).

    Source points get label 0 and target points label 1. With n_p source and n_q target points the
    classifier logit h(x) satisfies q(x)/p(x) = (n_p/n_q) exp(h(x)); for n_p = n_q this is (19.18).
    Returns a function w(x)."""
    Phi = np.vstack([poly_features(x_src, deg), poly_features(x_tgt, deg)])
    lab = np.r_[np.zeros(len(x_src)), np.ones(len(x_tgt))]
    beta = logistic_newton(Phi, lab, l2=1e-6)
    ratio = len(x_src) / len(x_tgt)
    return lambda x: ratio * np.exp(poly_features(x, deg) @ beta)


def weighted_least_squares(Phi, y, w=None, ridge=0.0):
    """argmin sum_n w_n (y_n - Phi_n beta)^2 + ridge ||beta||^2 (weighted ERM for squared loss, (19.15))."""
    w = np.ones(len(y)) if w is None else np.asarray(w, float)
    A = (Phi * w[:, None]).T @ Phi + ridge * np.eye(Phi.shape[1])
    return np.linalg.solve(A, (Phi * w[:, None]).T @ y)


def ess_fraction(w):
    """Effective sample size (sum w)^2 / (n sum w^2) as a fraction of n."""
    w = np.asarray(w, float)
    return float(w.sum() ** 2 / (len(w) * (w ** 2).sum()))


def finetune_ridge(Phi, y, beta_src, lam):
    """Fine-tuning (19.10) with squared loss and a squared distance to the source solution:
    argmin ||y - Phi b||^2 + lam ||b - beta_src||^2 = (Phi'Phi + lam I)^{-1}(Phi'y + lam beta_src)."""
    d = Phi.shape[1]
    return np.linalg.solve(Phi.T @ Phi + lam * np.eye(d), Phi.T @ y + lam * np.asarray(beta_src))


# ------------------------------------------------------------------ 19.2 the four kinds of shift
def shift_samples(kind, n, rng, mu=(0.9, 0.9)):
    """Samples (X, y) for the two-class Gaussian world used in Figure 19.4.

    Source world: x | y ~ N(+-mu, I), P(y=1) = 1/2, so p(y=1 | x) = sigmoid(2 mu.x) exactly.
    kind: 'original' / 'none' (a fresh draw), 'label' (P(y=1) becomes 0.9), 'concept' (the boundary
    normal is rotated by 90 degrees: p(y=1 | x) = sigmoid(2 mu_rot.x) with the source x marginal),
    'covariate' (x is drawn from a shifted, wider cloud, same p(y | x))."""
    mu = np.asarray(mu, float)
    mu_rot = np.array([-mu[1], mu[0]])

    def source_x(m):
        z = rng.integers(0, 2, m) * 2 - 1
        return z[:, None] * mu + rng.normal(size=(m, 2))

    if kind in ("original", "none"):
        y = rng.integers(0, 2, n)
        X = (2 * y - 1)[:, None] * mu + rng.normal(size=(n, 2))
        return X, y
    if kind == "label":
        y = (rng.uniform(size=n) < 0.9).astype(int)
        X = (2 * y - 1)[:, None] * mu + rng.normal(size=(n, 2))
        return X, y
    if kind == "concept":
        X = source_x(n)
        y = (rng.uniform(size=n) < sigmoid(2 * X @ mu_rot)).astype(int)
        return X, y
    if kind == "covariate":
        X = np.array([1.2, -1.2]) + 1.3 * rng.normal(size=(n, 2))
        y = (rng.uniform(size=n) < sigmoid(2 * X @ mu)).astype(int)
        return X, y
    raise ValueError(kind)


def fig_19_4(out=None):
    """Figure 19.4: the four kinds of distribution shift for a 2-d binary problem (simulated)."""
    rng = np.random.default_rng(4)
    kinds = [("original", "Original data"), ("label", "Label shift: p(y) changes"),
             ("concept", "Concept shift: p(y|x) changes"), ("covariate", "Covariate shift: p(x) changes"),
             ("none", "No data shift (new draw)")]
    mu = np.array([0.9, 0.9])
    fig, axes = plt.subplots(1, 5, figsize=(13.2, 2.9), sharex=True, sharey=True)
    xs = np.linspace(-4, 4, 5)
    for ax, (k, title) in zip(axes, kinds):
        X, y = shift_samples(k, 250, rng)
        ax.scatter(X[y == 0, 0], X[y == 0, 1], s=7, c=RED, alpha=.7, linewidths=0)
        ax.scatter(X[y == 1, 0], X[y == 1, 1], s=7, c=BLUE, alpha=.7, linewidths=0)
        ax.plot(xs, -mu[0] / mu[1] * xs, "k--", lw=.9)      # the source boundary mu.x = 0
        if k == "concept":
            ax.plot(xs, xs, color=GREEN, lw=1.2)             # the new boundary mu_rot.x = 0
        ax.set_title(title, fontsize=8.6)
        ax.set_xlim(-4, 4); ax.set_ylim(-4, 4); ax.set_xticks([]); ax.set_yticks([])
    fig.subplots_adjust(wspace=0.06)
    savefig(fig, CH, "fig19-4", out)


# ------------------------------------------------------------------ Figure 19.1 stand-in: noise and augmentation
def digits_split(seed=0):
    from sklearn.datasets import load_digits
    from sklearn.model_selection import train_test_split
    d = load_digits()
    return train_test_split(d.data / 16.0, d.target, test_size=0.4, random_state=seed, stratify=d.target)


def noise_curve(sigmas, train_noise=0.0, seeds=(0, 1, 2, 3, 4), hidden=64):
    """Test accuracy of an MLP on digits as Gaussian noise of sd sigma is added to the test pixels.

    train_noise > 0 trains on 5 noisy copies of every training image (data augmentation, Section 19.4.1)."""
    from sklearn.neural_network import MLPClassifier
    accs = np.zeros((len(seeds), len(sigmas)))
    for i, s in enumerate(seeds):
        Xtr, Xte, ytr, yte = digits_split(s)
        rng = np.random.default_rng(100 + s)
        if train_noise > 0:
            Xa = np.vstack([Xtr] + [Xtr + train_noise * rng.normal(size=Xtr.shape) for _ in range(5)])
            ya = np.tile(ytr, 6)
        else:
            Xa, ya = Xtr, ytr
        clf = MLPClassifier((hidden,), max_iter=400, random_state=s, alpha=1e-4).fit(Xa, ya)
        for j, sg in enumerate(sigmas):
            accs[i, j] = (clf.predict(Xte + sg * rng.normal(size=Xte.shape)) == yte).mean()
    return accs


def fig_19_1(out=None):
    """Figure 19.1 (stand-in): accuracy of a digits classifier as input noise grows, with and without noise augmentation."""
    sig = np.linspace(0, 1.0, 11)
    a0 = noise_curve(sig, 0.0)
    a1 = noise_curve(sig, 0.4)
    fig, axes = plt.subplots(1, 2, figsize=(8.6, 3.0), gridspec_kw=dict(width_ratios=[1.0, 1.5]))
    from sklearn.datasets import load_digits
    d = load_digits()
    rng = np.random.default_rng(1)
    img = d.data[3] / 16.0
    strip = np.hstack([np.clip(img + s * rng.normal(size=64), -0.5, 1.5).reshape(8, 8) for s in (0, 0.2, 0.4, 0.8)])
    axes[0].imshow(strip, cmap="gray_r", vmin=-0.5, vmax=1.5)
    axes[0].set_xticks([4 + 8 * k for k in range(4)]); axes[0].set_xticklabels(["0", "0.2", "0.4", "0.8"])
    axes[0].set_yticks([]); axes[0].set_xlabel("noise sd"); axes[0].set_title("one test image", fontsize=9.5)
    ax = axes[1]
    for a, c, lab in [(a0, RED, "trained on clean images"), (a1, BLUE, "trained with noise augmentation")]:
        m, s = a.mean(0), a.std(0)
        ax.plot(sig, m, "o-", color=c, ms=3.5, label=lab)
        ax.fill_between(sig, m - s, m + s, color=c, alpha=.18)
    ax.axhline(0.1, color=GREY, ls=":", lw=1)
    ax.set_xlabel("sd of Gaussian noise added to the test pixels"); ax.set_ylabel("test accuracy")
    ax.legend(loc="lower left", fontsize=8); ax.set_title("accuracy against input noise (mean and sd, 5 splits)", fontsize=9.5)
    fig.subplots_adjust(wspace=0.28)
    savefig(fig, CH, "fig19-1", out)


# ------------------------------------------------------------------ 19.5.2 covariate shift (Figure 19.10)
CS = dict(mp=0.0, sp=1.0, mq=1.5, sq=0.8, noise=0.25)


def cs_truth(x):
    """The regression function of the covariate-shift illustration (the same for source and target)."""
    return np.sin(1.2 * x) + 0.25 * x


def covariate_shift_experiment(n=120, seed=0, deg_w=2, cs=CS):
    """Source n points ~ N(mp, sp^2), unlabeled target n points ~ N(mq, sq^2); the labels follow cs_truth + noise.

    Fits a line by (i) ordinary least squares on the source, (ii) importance-weighted least squares with the
    exact ratio q/p, (iii) with the classifier ratio (19.17)-(19.18), (iv) the oracle: ordinary least squares on
    target data. Returns a dict with samples, fits, target mean squared errors and effective sample sizes."""
    rng = np.random.default_rng(seed)
    xs = cs["mp"] + cs["sp"] * rng.normal(size=n)
    ys = cs_truth(xs) + cs["noise"] * rng.normal(size=n)
    xt = cs["mq"] + cs["sq"] * rng.normal(size=n)
    yt = cs_truth(xt) + cs["noise"] * rng.normal(size=n)
    P = poly_features(xs, 1)
    w_exact = stats.norm.pdf(xs, cs["mq"], cs["sq"]) / stats.norm.pdf(xs, cs["mp"], cs["sp"])
    wfun = density_ratio_logistic(xs, xt, deg_w)
    w_hat = wfun(xs)
    fits = dict(ols=weighted_least_squares(P, ys), iw_exact=weighted_least_squares(P, ys, w_exact),
                iw_clf=weighted_least_squares(P, ys, w_hat), oracle=weighted_least_squares(poly_features(xt, 1), yt))
    # target mean squared error of the fitted functions by quadrature over q (noise-free f; add noise var for risk)
    g = np.linspace(cs["mq"] - 8 * cs["sq"], cs["mq"] + 8 * cs["sq"], 4001)
    q = stats.norm.pdf(g, cs["mq"], cs["sq"])
    mse = {k: float(np.trapz(q * (poly_features(g, 1) @ b - cs_truth(g)) ** 2, g)) for k, b in fits.items()}
    return dict(xs=xs, ys=ys, xt=xt, yt=yt, w_exact=w_exact, w_hat=w_hat, fits=fits, mse=mse,
                ess_exact=ess_fraction(w_exact), ess_clf=ess_fraction(w_hat))


def fig_19_10(out=None):
    """Figure 19.10: covariate shift, and a linear model refitted with importance weights."""
    r = covariate_shift_experiment(n=120, seed=3)
    cs = CS
    g = np.linspace(-3.5, 4.2, 400)
    fig, axes = plt.subplots(1, 2, figsize=(9.2, 3.2), sharex=True)
    ax = axes[0]
    ax.fill_between(g, 0, stats.norm.pdf(g, cs["mp"], cs["sp"]), color="#cfcfcf", alpha=.8, label="source p(x)")
    ax.fill_between(g, 0, stats.norm.pdf(g, cs["mq"], cs["sq"]), color="#6b6b6b", alpha=.6, label="target q(x)")
    ax.plot(g, cs_truth(g) / 3 + 0.0, color=GREEN, lw=1.5, label="f(x), rescaled (the same in both)")
    ax.set_title("(a) the input distribution moves, f does not", fontsize=9.5)
    ax.legend(fontsize=7.5, loc="upper left"); ax.set_xlabel("x"); ax.set_yticks([])
    ax = axes[1]
    ax.scatter(r["xs"], r["ys"], s=7, c="#9a9a9a", alpha=.7, label="source data", linewidths=0)
    ax.scatter(r["xt"], r["yt"], s=7, c="k", alpha=.55, label="target data", linewidths=0)
    ax.plot(g, cs_truth(g), color=GREEN, lw=1.2)
    for k, c, lab in [("ols", RED, "fit on source"), ("iw_exact", BLUE, "importance-weighted fit"), ("oracle", "k", "fit on target")]:
        ax.plot(g, poly_features(g, 1) @ r["fits"][k], color=c, lw=1.6, ls="-" if k != "oracle" else "--",
                label="%s (target MSE %.3f)" % (lab, r["mse"][k]))
    ax.set_ylim(-1.9, 2.2); ax.set_xlabel("x"); ax.legend(fontsize=7, loc="lower left")
    ax.set_title("(b) a line fitted to the source, and refitted with weights q/p", fontsize=9.5)
    fig.subplots_adjust(wspace=0.18)
    savefig(fig, CH, "fig19-10", out)
    return r


# ------------------------------------------------------------------ 19.5.4 label shift: blackbox shift estimation
def bbse(conf, mu_hat, clip=True):
    """Blackbox shift estimation (19.22): solve C q = mu for q; clip negatives and renormalise if clip.

    conf[i, j] = p(yhat = i | y = j) estimated on held-out source data; mu_hat[i] the fraction of target
    points predicted as i."""
    q = np.linalg.solve(conf, mu_hat)
    if clip:
        q = np.maximum(q, 0)
        q = q / q.sum()
    return q


def confusion_matrix_pred(yhat, y, K):
    """C[i, j] = fraction of points with true class j predicted as class i."""
    C = np.zeros((K, K))
    for j in range(K):
        m = y == j
        C[:, j] = np.bincount(yhat[m], minlength=K) / max(m.sum(), 1)
    return C


def mlls_em(P_src_probs, prior_src, iters=500, tol=1e-10):
    """Maximum-likelihood label-shift estimate by EM (Saerens et al. 2002; the likelihood-based alternative the
    book cites for (19.22)): q <- mean_n of the posterior reweighted by q/p, started at the source prior.

    P_src_probs[n, k] = p(y = k | x_n) from a calibrated source classifier on the target points."""
    q = np.asarray(prior_src, float).copy()
    for _ in range(iters):
        post = P_src_probs * (q / prior_src)
        post = post / post.sum(1, keepdims=True)
        q_new = post.mean(0)
        if np.abs(q_new - q).max() < tol:
            q = q_new
            break
        q = q_new
    return q


LS_MEANS = np.array([[-1.6, 0.0], [1.6, 0.0], [0.0, 2.2]])


def label_shift_world(rng, n, prior):
    y = rng.choice(3, size=n, p=prior)
    return LS_MEANS[y] + rng.normal(size=(n, 2)), y


def label_shift_experiment(ns=(50, 100, 200, 500, 1000, 2000, 5000), reps=300, p=(0.45, 0.45, 0.10), q=(0.10, 0.30, 0.60), seed=0, n_val=20000):
    """A 3-class Gaussian world; a multinomial logistic regression is trained on source data (prior p); the target has
    prior q with the same p(x|y). Compares the target class-prior estimators over replications."""
    from sklearn.linear_model import LogisticRegression
    p, q = np.asarray(p, float), np.asarray(q, float)
    rng = np.random.default_rng(seed)
    Xtr, ytr = label_shift_world(rng, 4000, p)
    clf = LogisticRegression(C=10.0, max_iter=1000).fit(Xtr, ytr)
    Xv, yv = label_shift_world(rng, n_val, p)
    C = confusion_matrix_pred(clf.predict(Xv), yv, 3)
    p_src = np.bincount(ytr, minlength=3) / len(ytr)
    res = {k: np.zeros((len(ns), reps)) for k in ("bbse", "naive", "em")}
    acc = {k: np.zeros((len(ns), reps)) for k in ("raw", "corrected", "bayes")}
    # Bayes-optimal classifier under the target prior (oracle), via the class-conditional Gaussians
    for a, n in enumerate(ns):
        for r in range(reps):
            X, y = label_shift_world(rng, n, q)
            pr = clf.predict_proba(X)
            yhat = pr.argmax(1)
            mu = np.bincount(yhat, minlength=3) / n
            qb = bbse(C, mu)
            res["bbse"][a, r] = np.abs(qb - q).sum()
            res["naive"][a, r] = np.abs(mu - q).sum()
            res["em"][a, r] = np.abs(mlls_em(pr, p_src) - q).sum()
            acc["raw"][a, r] = (yhat == y).mean()
            acc["corrected"][a, r] = ((pr * (qb / p)).argmax(1) == y).mean()
            ll = -0.5 * ((X[:, None, :] - LS_MEANS[None]) ** 2).sum(2) + np.log(q)
            acc["bayes"][a, r] = (ll.argmax(1) == y).mean()
    return dict(ns=np.array(ns), err=res, acc=acc, C=C, clf=clf, p=p, q=q)


def fig_19_28(out=None):
    """Own Figure 19.28: label shift, blackbox shift estimation against the naive estimate and EM."""
    r = label_shift_experiment()
    ns = r["ns"]
    fig, axes = plt.subplots(1, 3, figsize=(11.2, 3.0))
    ax = axes[0]
    rng = np.random.default_rng(0)
    for k, c in enumerate((RED, BLUE, GREEN)):
        Xk = LS_MEANS[k] + rng.normal(size=(150, 2))
        ax.scatter(Xk[:, 0], Xk[:, 1], s=6, c=c, alpha=.7, linewidths=0)
    ax.set_title("(a) three classes, source prior (0.45, 0.45, 0.10),\ntarget prior (0.10, 0.30, 0.60)", fontsize=8.5)
    ax.set_xticks([]); ax.set_yticks([])
    ax = axes[1]
    for k, c, lab in [("naive", GREY, "predicted-label fractions"), ("bbse", BLUE, "BBSE  C^{-1} mu"), ("em", MAGENTA, "EM (maximum likelihood)")]:
        ax.loglog(ns, r["err"][k].mean(1), "o-", ms=3.5, color=c, label=lab)
    ax.loglog(ns, 1.0 * (ns / ns[0]) ** -0.5 * r["err"]["bbse"].mean(1)[0], "k:", lw=.8, label="slope -1/2")
    ax.set_xlabel("number of unlabeled target points"); ax.set_ylabel("L1 error of the estimated q"); ax.legend(fontsize=7.5)
    ax.set_title("(b) estimating the target prior", fontsize=9)
    ax = axes[2]
    for k, c, lab in [("raw", GREY, "source classifier"), ("corrected", BLUE, "prior-corrected (19.23)"), ("bayes", GREEN, "Bayes rule, true q")]:
        ax.semilogx(ns, r["acc"][k].mean(1), "o-", ms=3.5, color=c, label=lab)
    ax.set_xlabel("number of unlabeled target points"); ax.set_ylabel("target accuracy"); ax.legend(fontsize=7.5, loc="lower right")
    ax.set_title("(c) accuracy on the target", fontsize=9)
    fig.subplots_adjust(wspace=0.32)
    savefig(fig, CH, "fig19-28", out)
    return r


# ------------------------------------------------------------------ 19.6.3 invariant risk minimisation (exact moments)
IRM_SY = 0.5       # sd of the label noise: y = x_c + e_y, so the best invariant predictor x_c has risk IRM_SY^2


def env_moments(beta, se, sy=IRM_SY):
    """Exact second moments of one environment of the spurious-feature model.

    x_c ~ N(0, 1), y = x_c + e_y (e_y ~ N(0, sy^2)), x_s = beta y + e_e (e_e ~ N(0, se^2)); x = (x_c, x_s).
    Returns (Sigma = E[x x'], c = E[x y], Ey2 = E[y^2])."""
    vy = 1 + sy ** 2
    S = np.array([[1.0, beta * 1.0], [beta * 1.0, beta ** 2 * vy + se ** 2]])
    c = np.array([1.0, beta * vy])
    return S, c, vy


def env_risk(theta, env):
    S, c, vy = env
    return float(theta @ S @ theta - 2 * theta @ c + vy)


def env_irm_penalty(theta, env):
    """Squared derivative of the environment risk of the scalar head w * (theta.x) at w = 1 (the IRMv1 penalty)."""
    S, c, vy = env
    g = 2 * (theta @ S @ theta - theta @ c)
    return float(g ** 2)


def erm_solution(envs):
    S = sum(e[0] for e in envs) / len(envs)
    c = sum(e[1] for e in envs) / len(envs)
    return np.linalg.solve(S, c)


def irm_solution(envs, lam, theta0=None):
    """Minimise the mean risk plus lam times the mean IRMv1 penalty over the environments (exact moments)."""
    f = lambda th: np.mean([env_risk(th, e) for e in envs]) + lam * np.mean([env_irm_penalty(th, e) for e in envs])
    best = None
    for t0 in ([theta0] if theta0 is not None else []) + [np.array([0.5, 0.5]), np.array([1.0, 0.0]), np.array([0.2, 0.8])]:
        r = optimize.minimize(f, np.asarray(t0, float), method="BFGS", options=dict(gtol=1e-12, maxiter=2000))
        if best is None or r.fun < best.fun:
            best = r
    return best.x


TRAIN_ENVS = [env_moments(1.0, 0.3), env_moments(1.0, 1.0)]


def fig_19_29(out=None):
    """Own Figure 19.29: ERM uses the spurious feature, IRM does not; risk when the spurious link flips."""
    th_erm = erm_solution(TRAIN_ENVS)
    lams = np.logspace(-1, 4, 26)
    ths = np.array([irm_solution(TRAIN_ENVS, l) for l in lams])
    betas = np.linspace(-1.5, 1.5, 121)
    fig, axes = plt.subplots(1, 3, figsize=(11.4, 3.0))
    ax = axes[0]
    ax.semilogx(lams, ths[:, 0], "o-", ms=3, color=BLUE, label="weight on the causal feature x_c")
    ax.semilogx(lams, ths[:, 1], "s-", ms=3, color=RED, label="weight on the spurious feature x_s")
    ax.axhline(th_erm[1], color=RED, ls=":", lw=1); ax.axhline(th_erm[0], color=BLUE, ls=":", lw=1)
    ax.set_xlabel("penalty weight (dotted: ERM)"); ax.legend(fontsize=7.5); ax.set_title("(a) IRM weights against the penalty", fontsize=9)
    ax = axes[1]
    for th, c, lab, ls in [(th_erm, RED, "ERM", "-"), (irm_solution(TRAIN_ENVS, 1e4), BLUE, "IRM (penalty 1e4)", "-"), (np.array([1.0, 0.0]), "k", "invariant predictor x_c", ":")]:
        risks = [env_risk(th, env_moments(b, 0.5)) for b in betas]
        ax.plot(betas, risks, color=c, ls=ls, label=lab)
    ax.axvline(1.0, color=GREY, lw=.8, ls="--")
    ax.set_xlabel("spurious link beta at test time (training: 1)"); ax.set_ylabel("test risk"); ax.legend(fontsize=7.5)
    ax.set_title("(b) risk when the spurious link changes", fontsize=9)
    ax = axes[2]
    se = np.linspace(0.1, 2.0, 40)
    for th, c, lab in [(th_erm, RED, "ERM"), (irm_solution(TRAIN_ENVS, 1e4), BLUE, "IRM")]:
        ax.plot(se, [env_risk(th, env_moments(1.0, s)) for s in se], color=c, label=lab)
    ax.axhline(IRM_SY ** 2, color="k", ls=":", lw=1)
    ax.set_xlabel("noise sd of x_s at test time (beta = 1)"); ax.set_ylabel("test risk"); ax.legend(fontsize=7.5)
    ax.set_title("(c) risk when only the noise level changes", fontsize=9)
    fig.subplots_adjust(wspace=0.3)
    savefig(fig, CH, "fig19-29", out)


# ------------------------------------------------------------------ 19.7.5 online learning
def kt_regret(bits, a=0.5):
    """Prequential log-loss regret (nats) of the Beta(a, a) Bayesian predictor against the best constant theta in hindsight.

    Predictive probability of a 1 after k ones in t trials: (k + a)/(t + 2a). Returns the cumulative regret after each step."""
    bits = np.asarray(bits, int)
    t = np.arange(len(bits))
    k = np.concatenate([[0], np.cumsum(bits)[:-1]])
    p1 = (k + a) / (t + 2 * a)
    loss = -np.log(np.where(bits == 1, p1, 1 - p1))
    cum = np.cumsum(loss)
    kk = np.cumsum(bits)
    n = t + 1
    th = kk / n
    with np.errstate(divide="ignore", invalid="ignore"):
        best = -(kk * np.log(th) + (n - kk) * np.log(1 - th))
    best = np.nan_to_num(best, nan=0.0, posinf=0.0)
    return cum - best


def ogd_run(X, y, eta, radius):
    """Online gradient descent on the logistic loss over the ball ||w|| <= radius.

    Returns the cumulative loss and the iterates (w_1, ..., w_T), where w_t is used to predict x_t."""
    T, d = X.shape
    w = np.zeros(d)
    losses = np.zeros(T)
    W = np.zeros((T, d))
    for t in range(T):
        W[t] = w
        m = y[t] * (X[t] @ w)
        losses[t] = np.logaddexp(0, -m)
        g = -y[t] * X[t] * sigmoid(-m)
        w = w - eta * g
        nw = np.linalg.norm(w)
        if nw > radius:
            w = w * radius / nw
    return np.cumsum(losses), W


def best_fixed_loss(X, y, radius):
    """min over ||w|| <= radius of the cumulative logistic loss (convex; by projected L-BFGS-style search)."""
    f = lambda w: np.logaddexp(0, -y * (X @ w)).sum()
    g = lambda w: -(X * (y * sigmoid(-y * (X @ w)))[:, None]).sum(0)
    cons = [{"type": "ineq", "fun": lambda w: radius ** 2 - w @ w, "jac": lambda w: -2 * w}]
    best = None
    for w0 in (np.zeros(X.shape[1]), np.ones(X.shape[1]) * radius / np.sqrt(X.shape[1])):
        r = optimize.minimize(f, w0, jac=g, constraints=cons, method="SLSQP", options=dict(ftol=1e-12, maxiter=500))
        if best is None or r.fun < best.fun:
            best = r
    return best.fun, best.x


def discounted_bernoulli_losses(bits, gamma, a=1.0):
    """Per-step log loss of a Beta predictor whose counts decay by gamma each step (gamma = 1: no forgetting)."""
    n1, n0 = 0.0, 0.0
    loss = np.zeros(len(bits))
    for t, b in enumerate(bits):
        p1 = (n1 + a) / (n1 + n0 + 2 * a)
        loss[t] = -np.log(p1 if b == 1 else 1 - p1)
        n1 = gamma * n1 + (b == 1)
        n0 = gamma * n0 + (b == 0)
    return loss


def fig_19_31(out=None):
    """Own Figure 19.31: prequential log loss, regret of the Bayesian and online-gradient predictors, and drift."""
    rng = np.random.default_rng(31)
    T = 2000
    fig, axes = plt.subplots(1, 3, figsize=(11.4, 3.1))
    ax = axes[0]
    reps = 200
    R = np.array([kt_regret(rng.uniform(size=T) < 0.3) for _ in range(reps)])
    t = np.arange(1, T + 1)
    ax.semilogx(t, R.mean(0), color=BLUE, label="Bayes, Beta(1/2, 1/2): mean")
    ax.fill_between(t, np.percentile(R, 10, 0), np.percentile(R, 90, 0), color=BLUE, alpha=.18)
    ax.semilogx(t, 0.5 * np.log(t) + 0.5 * np.log(np.pi / 2), color="k", ls=":", label="(1/2) ln t + (1/2) ln(pi/2)")
    Rl = np.array([kt_regret(rng.uniform(size=T) < 0.3, a=1.0) for _ in range(reps)])
    ax.semilogx(t, Rl.mean(0), color=ORANGE, label="Bayes, uniform prior: mean")
    ax.set_xlabel("t"); ax.set_ylabel("cumulative log-loss regret (nats)"); ax.legend(fontsize=7.5)
    ax.set_title("(a) prequential regret, Bayes predictor", fontsize=9)
    ax = axes[1]
    Ts = np.unique(np.logspace(1.3, 3.3, 14).astype(int))
    d, rad = 3, 2.0
    wstar = np.array([1.0, -1.0, 0.5])
    reg_mean, reg_sd = [], []
    for Tt in Ts:
        vals = []
        for r_ in range(8):
            X = rng.normal(size=(Tt, d)); X = X / np.maximum(1, np.linalg.norm(X, axis=1, keepdims=True))   # ||x|| <= 1
            yy = np.where(rng.uniform(size=Tt) < sigmoid(3 * X @ wstar), 1, -1)
            eta = rad / np.sqrt(Tt)
            cum, _ = ogd_run(X, yy, eta, rad)
            vals.append(cum[-1] - best_fixed_loss(X, yy, rad)[0])
        reg_mean.append(np.mean(vals)); reg_sd.append(np.std(vals))
    reg_mean = np.array(reg_mean)
    ax.loglog(Ts, reg_mean, "o-", color=BLUE, ms=3.5, label="online gradient descent (mean of 8)")
    ax.loglog(Ts, rad * 1.0 * np.sqrt(Ts) * 1.0, color="k", ls=":", label="bound  D G sqrt(T)  (G = 1, D = 2)")
    ax.set_xlabel("T"); ax.set_ylabel("regret"); ax.legend(fontsize=7.5)
    ax.set_title("(b) online gradient descent, logistic loss", fontsize=9)
    ax = axes[2]
    Tc, tc = 1200, 600
    bits = np.concatenate([rng.uniform(size=tc) < 0.2, rng.uniform(size=Tc - tc) < 0.8]).astype(int)
    for gam, c, lab in [(1.0, RED, "no forgetting"), (0.99, BLUE, "discount 0.99"), (0.95, GREEN, "discount 0.95")]:
        L = np.mean([discounted_bernoulli_losses(np.concatenate([rng.uniform(size=tc) < 0.2, rng.uniform(size=Tc - tc) < 0.8]).astype(int), gam) for _ in range(100)], 0)
        sm = np.convolve(L, np.ones(20) / 20, mode="valid")
        ax.plot(np.arange(len(sm)) + 20, sm, color=c, label=lab)
    ax.axvline(tc, color=GREY, ls="--", lw=.8)
    ax.set_xlabel("t (success probability 0.2, then 0.8 after t = 600)"); ax.set_ylabel("log loss per step"); ax.legend(fontsize=7.5)
    ax.set_title("(c) a piecewise-constant stream", fontsize=9)
    fig.subplots_adjust(wspace=0.32)
    savefig(fig, CH, "fig19-31", out)



# ------------------------------------------------------------------ 19.8 adversarial examples
def dual_norm_w(w, p):
    """Dual norm ||w||_q of the weight vector for an l_p ball of perturbations: p = inf -> l1, p = 2 -> l2, p = 1 -> linf."""
    return {np.inf: np.abs(w).sum(), 2: np.sqrt((w ** 2).sum()), 1: np.abs(w).max()}[p]


def linear_worst_case_margin(w, b, X, y, eps, p=np.inf):
    """Exact worst-case margin min_{||d||_p <= eps} y (w.(x + d) + b) = y (w.x + b) - eps ||w||_q, y in {-1,+1}.

    (the linearisation that the fast gradient sign method uses is exact for a linear classifier.)"""
    return y * (X @ w + b) - eps * dual_norm_w(w, p)


def linear_robust_accuracy(w, b, X, y, eps, p=np.inf):
    """Fraction of points whose label survives every perturbation in the l_p ball of radius eps."""
    return float(np.mean(linear_worst_case_margin(w, b, X, y, eps, p) > 0))


def fgs_attack(w, X, y, eps):
    """Fast gradient sign perturbation (19.49)-(19.50) against a linear logistic model with labels in {-1, +1}:
    the gradient of the loss logistic(-y w.x) with respect to x is -y sigma(-m) w, so the step is -eps y sign(w)."""
    return X - eps * (y[:, None] * np.sign(w)[None, :])


def fit_logistic_pm(X, y, l2=1e-3, eps=0.0, p=np.inf, w0=None):
    """Logistic regression with labels in {-1, +1} by L-BFGS; with eps > 0 it is adversarial training against
    l_p perturbations, using the closed-form inner maximum: loss log(1 + exp(-(y f(x) - eps ||w||_q)))."""
    n, d = X.shape
    tiny = 1e-8

    def fun(theta):
        w, b = theta[:-1], theta[-1]
        if p == np.inf:
            nq, gq = np.sqrt(w ** 2 + tiny).sum(), w / np.sqrt(w ** 2 + tiny)
        else:
            nq = np.sqrt((w ** 2).sum() + tiny); gq = w / nq
        m = y * (X @ w + b) - eps * nq
        L = np.logaddexp(0, -m).mean() + 0.5 * l2 * (w @ w)
        s = sigmoid(-m)
        gw = -(X * (y * s)[:, None]).mean(0) + eps * s.mean() * gq + l2 * w
        gb = -(y * s).mean()
        return L, np.r_[gw, gb]

    t0 = np.zeros(d + 1) if w0 is None else w0
    r = optimize.minimize(fun, t0, jac=True, method="L-BFGS-B", options=dict(maxiter=3000, ftol=1e-13, gtol=1e-9))
    return r.x[:-1], r.x[-1]


def mnist_pair(a=3, b=8, n_train=4000, n_test=1500, seed=0):
    """MNIST digits a (label +1) and b (label -1), pixels in [0, 1]."""
    Xa, ya = mnist(True, digits=(a, b))
    Xt, yt = mnist(False, digits=(a, b))
    rng = np.random.default_rng(seed)
    i, j = rng.permutation(len(ya))[:n_train], rng.permutation(len(yt))[:n_test]
    return Xa[i], np.where(ya[i] == a, 1, -1), Xt[j], np.where(yt[j] == a, 1, -1)


def fig_19_32(out=None):
    """Own Figure 19.32: adversarial perturbations of a linear classifier, with and without adversarial training."""
    Xtr, ytr, Xte, yte = mnist_pair()
    w0, b0 = fit_logistic_pm(Xtr, ytr, l2=1e-3)
    w1, b1 = fit_logistic_pm(Xtr, ytr, l2=1e-3, eps=0.1, w0=np.r_[w0, b0])
    eps = np.linspace(0, 0.3, 61)
    rng = np.random.default_rng(0)
    fig = plt.figure(figsize=(11.2, 3.0))
    gs = fig.add_gridspec(1, 5, width_ratios=[2.3, 0.9, 0.9, 0.9, 0.9], wspace=0.12)
    ax = fig.add_subplot(gs[0])
    ax.plot(eps, [linear_robust_accuracy(w0, b0, Xte, yte, e) for e in eps], color=RED, label="standard model, worst case")
    ax.plot(eps, [linear_robust_accuracy(w1, b1, Xte, yte, e) for e in eps], color=BLUE, label="adversarially trained (eps = 0.1), worst case")
    acc_rand = [np.mean(np.sign(((Xte + e * rng.choice([-1, 1], Xte.shape)) @ w0 + b0)) == yte) for e in eps]
    ax.plot(eps, acc_rand, color=GREY, ls="--", label="standard model, random sign noise")
    ax.set_xlabel("l-infinity perturbation size eps (pixels in [0, 1])"); ax.set_ylabel("test accuracy, 3 versus 8")
    ax.legend(fontsize=7, loc="lower left"); ax.set_title("(a) accuracy against perturbation size", fontsize=9)
    # images
    k = int(np.where((yte == 1) & (yte * (Xte @ w0 + b0) > 0))[0][2])
    x = Xte[k]
    e = 1.2 * float(yte[k] * (x @ w0 + b0)) / dual_norm_w(w0, np.inf)       # 20% beyond the exact flipping size
    xa = fgs_attack(w0, x[None], yte[k:k + 1], e)[0]
    panels = [(x, "clean, label 3\nscore %+.1f" % (x @ w0 + b0), "gray_r", (0, 1)),
              (xa, "eps = %.3f\nscore %+.1f" % (e, xa @ w0 + b0), "gray_r", (-0.2, 1.2)),
              (w0, "weights, standard", "RdBu_r", (-np.abs(w0).max(), np.abs(w0).max())),
              (w1, "weights, adv. trained", "RdBu_r", (-np.abs(w1).max(), np.abs(w1).max()))]
    for i, (im, ttl, cm, (lo, hi)) in enumerate(panels):
        a = fig.add_subplot(gs[i + 1])
        a.imshow(im.reshape(28, 28), cmap=cm, vmin=lo, vmax=hi); a.set_xticks([]); a.set_yticks([]); a.set_title(ttl, fontsize=7.8)
    savefig(fig, CH, "fig19-32", out)
    return dict(eps_flip=e)


def distance_to_error(sigma, mu):
    """Equation (19.52): the distance from x0 to a halfspace of errors that has probability mu under N(x0, sigma^2 I)."""
    return -sigma * stats.norm.ppf(mu)


def fig_19_33(out=None):
    """Own Figure 19.33: concentration of measure, adversarial distance against the size of random noise."""
    sigma = 0.2
    ns = np.unique(np.logspace(0, 5.3, 40).astype(int))
    fig, axes = plt.subplots(1, 2, figsize=(8.8, 3.1))
    ax = axes[0]
    ax.loglog(ns, sigma * np.sqrt(ns), color=BLUE, lw=1.8, label="typical noise: sigma sqrt(n)")
    for mu, c in [(0.1, GREEN), (0.01, ORANGE), (1e-4, RED)]:
        ax.loglog(ns, np.full(len(ns), distance_to_error(sigma, mu)), color=c, lw=1.4, label="distance to a halfspace of errors, mu = %g" % mu)
    nimg = 224 * 224 * 3
    ax.plot([nimg], [sigma * np.sqrt(nimg)], "o", color=BLUE, mfc="white", label="a 224 x 224 x 3 image: %.1f" % (sigma * np.sqrt(nimg)))
    ax.plot([nimg], [distance_to_error(sigma, 0.01)], "o", color=ORANGE, mfc="white", label="the same image, mu = 0.01: %.2f" % distance_to_error(sigma, 0.01))
    ax.set_xlabel("input dimension n"); ax.set_ylabel("l2 distance"); ax.legend(fontsize=6.8, loc="upper left")
    ax.set_title("(a) distances, sigma = 0.2", fontsize=9)
    ax = axes[1]
    rng = np.random.default_rng(1)
    mu = 0.01
    d = distance_to_error(sigma, mu)
    nn = ns[ns <= 20000]
    emp, band = [], []
    for n in nn:
        m = 40000 if n <= 100 else (8000 if n <= 3000 else 1500)
        a = np.zeros(n); a[0] = 1.0
        Z = sigma * rng.normal(size=(m, n))
        emp.append(np.mean(Z @ a >= d)); band.append(1.96 * np.sqrt(mu * (1 - mu) / m))
    emp, band = np.array(emp), np.array(band)
    ax.semilogx(nn, emp, "o", color=ORANGE, ms=3, label="error rate under noise (simulated)")
    ax.fill_between(nn, mu - band, mu + band, color="k", alpha=.12, label="95% band around mu = 0.01")
    ax.set_ylim(0, 0.02)
    ax.set_xlabel("input dimension n"); ax.set_ylabel("error rate under noise")
    ax.set_title("(b) noise hits the error set at the same rate for every n,\nwhile the noise grows as sqrt(n) (ratio %.0f at n = 150528)" % (sigma * np.sqrt(nimg) / d), fontsize=8.2)
    ax.legend(fontsize=7, loc="upper left")
    fig.subplots_adjust(wspace=0.3)
    savefig(fig, CH, "fig19-33", out)



# ------------------------------------------------------------------ 19.3.3 selective prediction: SGD against SGLD
def fashion_test(n=None):
    """The Fashion-MNIST test images (pixels in [0, 1]) and labels, downloaded once into the cache."""
    import gzip
    import struct
    from common import _download
    base = os.path.join(CACHE, "fashion")
    names = ("t10k-images-idx3-ubyte.gz", "t10k-labels-idx1-ubyte.gz")
    for nm in names:
        path = os.path.join(base, nm)
        if not os.path.exists(path):
            _download(["https://github.com/zalandoresearch/fashion-mnist/raw/master/data/fashion/" + nm], path)
    with gzip.open(os.path.join(base, names[0]), "rb") as f:
        _, m, r, c = struct.unpack(">IIII", f.read(16))
        X = np.frombuffer(f.read(), dtype=np.uint8).reshape(m, r * c)
    with gzip.open(os.path.join(base, names[1]), "rb") as f:
        f.read(8)
        y = np.frombuffer(f.read(), dtype=np.uint8)
    return X.astype(np.float32) / 255.0, y.astype(int)


def mlp_sgd_sgld(mode, steps=6000, bs=1000, hidden=100, lr=1e-3, eps=3e-6, prior_sd=1.0, n_snap=10, seed=0):
    """Fit a one-hidden-layer MLP (ReLU) to the 60,000 MNIST training images.

    mode 'sgd': RMSprop on the mean cross-entropy (the plug-in approach). mode 'sgld': stochastic gradient Langevin
    dynamics (Section 12.7.1), theta <- theta + (eps/2) [grad log prior + N grad_batch log lik] + sqrt(eps) noise, with the
    minibatch gradient scaled up by N; n_snap parameter snapshots, evenly spaced over the last 1000 steps, form the
    Bayesian posterior predictive. Returns a function mapping a numpy image array to class probabilities."""
    torch = torch_setup(seed, 1)
    Xtr, ytr = mnist(True)
    Xtr, ytr = torch.tensor(Xtr, dtype=torch.float32), torch.tensor(ytr)
    N = len(ytr)
    g = torch.Generator().manual_seed(seed + 1)
    gi = torch.Generator().manual_seed(seed)
    P = [(torch.randn(784, hidden, generator=gi) / np.sqrt(784)).requires_grad_(), torch.zeros(hidden, requires_grad=True),
         (torch.randn(hidden, 10, generator=gi) / np.sqrt(hidden)).requires_grad_(), torch.zeros(10, requires_grad=True)]
    fwd = lambda Q, x: torch.relu(x @ Q[0] + Q[1]) @ Q[2] + Q[3]
    sq = [torch.zeros_like(p) for p in P]
    snaps = []
    every = 1000 // n_snap
    for t in range(steps):
        idx = torch.randint(0, N, (bs,), generator=g)
        loss = torch.nn.functional.cross_entropy(fwd(P, Xtr[idx]), ytr[idx])
        gr = torch.autograd.grad(loss, P)
        with torch.no_grad():
            for i, p in enumerate(P):
                if mode == "sgd":
                    sq[i] = 0.9 * sq[i] + 0.1 * gr[i] ** 2
                    p -= lr * gr[i] / (sq[i].sqrt() + 1e-8)
                else:
                    p += 0.5 * eps * (-(N * gr[i] + p / prior_sd ** 2)) + np.sqrt(eps) * torch.randn(p.shape, generator=g)
        if mode == "sgld" and t >= steps - 1000 and (t - (steps - 1000)) % every == every - 1:
            snaps.append([p.detach().clone() for p in P])
    models = snaps if mode == "sgld" else [[p.detach() for p in P]]

    def predict(X):
        with torch.no_grad():
            Xt = torch.tensor(np.asarray(X, dtype=np.float32))
            return torch.stack([torch.softmax(fwd(Q, Xt), 1) for Q in models]).mean(0).numpy()
    return predict


def selective_curves(prob, y, thresholds):
    """For each threshold t: the fraction of points whose top class probability is at least t, and the accuracy among them."""
    conf, pred = prob.max(1), prob.argmax(1)
    frac = np.array([(conf >= t).mean() for t in thresholds])
    acc = np.array([(pred[conf >= t] == y[conf >= t]).mean() if (conf >= t).any() else np.nan for t in thresholds])
    return frac, acc


def bnn_results(force=False):
    """Train the two MLPs once and cache the class probabilities on one MNIST test batch and one Fashion-MNIST batch."""
    path = os.path.join(WORK, "bnn_probs.npz")
    if os.path.exists(path) and not force:
        z = np.load(path)
        return {k: z[k] for k in z.files}
    Xte, yte = mnist(False)
    Xf, yf = fashion_test()
    out = dict(y_mnist=yte[:1000], y_fashion=yf[:1000])
    for mode in ("sgd", "sgld"):
        pr = mlp_sgd_sgld(mode)
        out[mode + "_mnist"] = pr(Xte[:1000])
        out[mode + "_fashion"] = pr(Xf[:1000])
    np.savez(path, **out)
    return out


def fig_19_8_9(out=None):
    """Figures 19.8 and 19.9: accuracy and fraction predicted against the confidence threshold, MNIST and Fashion-MNIST."""
    r = bnn_results()
    th = np.linspace(0, 1, 101)
    for fig_id, dset, ttl in (("fig19-8", "mnist", "MNIST test batch"), ("fig19-9", "fashion", "Fashion-MNIST batch")):
        fig, axes = plt.subplots(1, 2, figsize=(8.6, 2.9))
        for ax, mode, name in zip(axes, ("sgd", "sgld"), ("(a) plug-in: RMSprop", "(b) Bayesian: SGLD, 10 samples")):
            frac, acc = selective_curves(r[mode + "_" + dset], r["y_" + dset], th)
            ax.plot(th, acc, color=BLUE)
            ax.set_xlabel("certainty threshold"); ax.set_title(name + ", " + ttl, fontsize=8.4)
            ax.set_ylabel("accuracy" if mode == "sgd" else "", color=BLUE)
            ax2 = ax.twinx()
            ax2.plot(th, frac, color=GREEN)
            ax2.set_ylim(0, 1.03)
            if mode == "sgld":
                ax2.set_ylabel("fraction of predictions made", color=GREEN)
        fig.subplots_adjust(wspace=0.55)
        savefig(fig, CH, fig_id, out)


# ------------------------------------------------------------------ 19.3.2.4 likelihood against likelihood ratio (Figure 19.7 stand-in)
def bernoulli_loglik(X, theta):
    """log prod_i theta_i^x_i (1 - theta_i)^(1 - x_i) for each row of the binary matrix X."""
    return X @ np.log(theta) + (1 - X) @ np.log(1 - theta)


def auroc(score_id, score_ood):
    """Area under the ROC curve for detecting ID (positive) against OOD, higher score = more in-distribution."""
    from sklearn.metrics import roc_auc_score
    return float(roc_auc_score(np.r_[np.ones(len(score_id)), np.zeros(len(score_ood))], np.r_[score_id, score_ood]))


def ood_experiment(n_fit=6000, n_eval=4000, thresh=0.5):
    """An independent-pixel Bernoulli model fitted to binarised Fashion-MNIST, evaluated on held-out Fashion-MNIST
    (in-distribution) and on MNIST (out-of-distribution). The background model for the ratio is the same model with
    all pixels sharing one rate, i.e. fitted to pixel-shuffled images. Also the reverse direction."""
    Xf, _ = fashion_test()
    Xm, _ = mnist(False)
    Fb, Mb = (Xf > thresh).astype(float), (Xm > thresh).astype(float)
    Ftr, Fte, Mte = Fb[:n_fit], Fb[n_fit:n_fit + n_eval], Mb[:n_eval]
    th_f = np.clip(Ftr.mean(0), 1e-3, 1 - 1e-3)
    bg = np.full(784, Ftr.mean())
    res = dict(lp_id=bernoulli_loglik(Fte, th_f), lp_ood=bernoulli_loglik(Mte, th_f))
    res["R_id"] = res["lp_id"] - bernoulli_loglik(Fte, bg)
    res["R_ood"] = res["lp_ood"] - bernoulli_loglik(Mte, bg)
    Mtr = Mb[n_fit:n_fit + n_fit] if len(Mb) >= 2 * n_fit else Mb[:n_fit]
    Mho = Mb[-n_eval:]
    th_m = np.clip(Mtr.mean(0), 1e-3, 1 - 1e-3)
    res["rev_id"], res["rev_ood"] = bernoulli_loglik(Mho, th_m), bernoulli_loglik(Fb[:n_eval], th_m)
    res["ink_f"], res["ink_m"] = Fte.mean(1), Mte.mean(1)
    for k in ("lp", "R"):
        res["auroc_" + k] = auroc(res[k + "_id"], res[k + "_ood"])
    res["auroc_rev"] = auroc(res["rev_id"], res["rev_ood"])
    return res


def fig_19_34(out=None):
    """Own Figure 19.34 (stand-in for Figure 19.7): a density model can prefer simpler out-of-distribution data."""
    r = ood_experiment()
    fig, axes = plt.subplots(1, 3, figsize=(11.4, 3.0))
    for ax, (a, b), ttl, xl in [(axes[0], (r["lp_id"], r["lp_ood"]), "(a) log-likelihood, model fitted to Fashion-MNIST\nAUROC %.2f" % r["auroc_lp"], "log p(x)"),
                                (axes[1], (r["R_id"], r["R_ood"]), "(b) log-likelihood ratio against the pixel-shuffled\nbackground model, AUROC %.2f" % r["auroc_R"], "log p(x) - log q(x)"),
                                (axes[2], (r["rev_id"], r["rev_ood"]), "(c) the reverse direction: fitted to MNIST,\nFashion-MNIST as OOD, AUROC %.2f" % r["auroc_rev"], "log p(x)")]:
        lo, hi = np.percentile(np.r_[a, b], [0.5, 99.5])
        bins = np.linspace(lo, hi, 50)
        ax.hist(a, bins, color=BLUE, alpha=.6, density=True, label="in-distribution")
        ax.hist(b, bins, color=RED, alpha=.6, density=True, label="out-of-distribution")
        ax.set_xlabel(xl); ax.set_yticks([]); ax.set_title(ttl, fontsize=8.4)
    axes[0].legend(fontsize=7.5, loc="upper left")
    fig.subplots_adjust(wspace=0.12)
    savefig(fig, CH, "fig19-34", out)
    return r


# ------------------------------------------------------------------ 19.3.2.3 a conformal threshold on the OOD score
def conformal_threshold(cal_scores, alpha):
    """The threshold lambda_1 such that a fresh in-distribution point is flagged OOD (score > lambda_1) with probability
    at most alpha: the ceil((n + 1)(1 - alpha))-th smallest calibration score (exchangeability, finite-sample valid)."""
    s = np.sort(np.asarray(cal_scores))
    k = int(np.ceil((len(s) + 1) * (1 - alpha)))
    return np.inf if k > len(s) else s[k - 1]


# ------------------------------------------------------------------ 19.7.3 / 19.7.4 continual learning on permuted digits
def cl_tasks(T=5, seed=0):
    """T permuted-digits tasks (task 1 is the identity); returns torch tensors (Xtr, ytr, Xte, yte) per task."""
    torch = torch_setup(0, 1)
    Xtr, Xte, ytr, yte = digits_split(0)
    rng = np.random.default_rng(seed)
    perms = [np.arange(64)] + [rng.permutation(64) for _ in range(T - 1)]
    f = lambda a: torch.tensor(a, dtype=torch.float32)
    return [(f(Xtr[:, p]), torch.tensor(ytr), f(Xte[:, p]), torch.tensor(yte)) for p in perms]


def _cl_net(torch, seed, hidden=100):
    torch.manual_seed(seed)
    return torch.nn.Sequential(torch.nn.Linear(64, hidden), torch.nn.ReLU(), torch.nn.Linear(hidden, 10))


def _cl_train(torch, m, Xt, yt, epochs=25, lr=0.02, bs=64, pen=None, replay=None):
    opt = torch.optim.SGD(m.parameters(), lr=lr)
    for _ in range(epochs):
        perm = torch.randperm(len(Xt))
        for i in range(0, len(Xt), bs):
            idx = perm[i:i + bs]
            xb, yb = Xt[idx], yt[idx]
            if replay is not None:
                xb, yb = torch.cat([xb, replay[0]]), torch.cat([yb, replay[1]])
            loss = torch.nn.functional.cross_entropy(m(xb), yb)
            if pen is not None:
                loss = loss + pen(m)
            opt.zero_grad(); loss.backward(); opt.step()


def _cl_fisher(torch, m, Xt, n=200):
    """Diagonal Fisher information: mean over n inputs of the squared score of a label drawn from the model itself."""
    ps = list(m.parameters())
    F = [torch.zeros_like(p) for p in ps]
    for i in torch.randperm(len(Xt))[:n]:
        lp = torch.log_softmax(m(Xt[i:i + 1]), 1)
        yy = torch.multinomial(lp.exp(), 1).item()
        for f, gg in zip(F, torch.autograd.grad(lp[0, yy], ps)):
            f += gg ** 2 / n
    return F


def continual_run(method, tasks, seed=0, lam=30.0, buf=60):
    """Train sequentially on the tasks and return R[i, j], the test accuracy on task j after training on task i.

    method: 'naive' (plain SGD), 'ewc' (diagonal-Fisher quadratic penalty with strength lam, anchored at the latest
    solution, Fishers of all earlier tasks summed), 'replay' (buf stored examples per earlier task are mixed into every minibatch)."""
    torch = torch_setup(seed, 1)
    T = len(tasks)
    m = _cl_net(torch, seed)
    R = np.zeros((T, T))
    Fs, anchor, mem = None, None, None
    for t in range(T):
        Xt, yt, _, _ = tasks[t]
        pen = None
        if method == "ewc" and Fs is not None:
            pen = lambda mm: 0.5 * lam * sum((f * (p - a) ** 2).sum() for f, p, a in zip(Fs, mm.parameters(), anchor))
        _cl_train(torch, m, Xt, yt, pen=pen, replay=mem if method == "replay" else None)
        with torch.no_grad():
            for j in range(T):
                R[t, j] = (m(tasks[j][2]).argmax(1) == tasks[j][3]).float().mean().item()
        if method == "ewc":
            F = _cl_fisher(torch, m, Xt)
            Fs = F if Fs is None else [a + b for a, b in zip(Fs, F)]
            anchor = [p.detach().clone() for p in m.parameters()]
        if method == "replay":
            idx = torch.randperm(len(Xt))[:buf]
            mem = (Xt[idx], yt[idx]) if mem is None else (torch.cat([mem[0], Xt[idx]]), torch.cat([mem[1], yt[idx]]))
    return R


def independent_accuracy(tasks, seed=0):
    """R_j^ind of (19.41): test accuracy on task j of a network trained on task j alone."""
    torch = torch_setup(seed, 1)
    out = []
    for Xt, yt, Xe, ye in tasks:
        m = _cl_net(torch, seed)
        _cl_train(torch, m, Xt, yt)
        with torch.no_grad():
            out.append((m(Xe).argmax(1) == ye).float().mean().item())
    return np.array(out)


def transfer_scores(R, R_ind):
    """Forward and backward transfer as printed in (19.41) and (19.42): FWT = mean_j (R_jj - R_j^ind),
    BWT = mean_j (R_Tj - R_jj) (the j = T term is 0)."""
    T = len(R_ind)
    return float(np.mean([R[j, j] - R_ind[j] for j in range(T)])), float(np.mean([R[T - 1, j] - R[j, j] for j in range(T)]))


def continual_results(force=False, seeds=(0, 1, 2)):
    path = os.path.join(WORK, "continual.npz")
    if os.path.exists(path) and not force:
        z = np.load(path)
        return {k: z[k] for k in z.files}
    tasks = cl_tasks()
    out = {}
    for name, meth, kw in (("naive", "naive", {}), ("ewc30", "ewc", dict(lam=30.0)), ("ewc100", "ewc", dict(lam=100.0)), ("replay", "replay", {})):
        out[name] = np.array([continual_run(meth, tasks, seed=s, **kw) for s in seeds])
    out["ind"] = np.array([independent_accuracy(tasks, seed=s) for s in seeds])
    np.savez(path, **out)
    return out


def fig_19_30(out=None):
    """Own Figure 19.30 (the real version of the schematics 19.20 and 19.21): permuted digits, five tasks."""
    r = continual_results()
    names = [("naive", "sequential SGD"), ("ewc30", "EWC, strength 30"), ("ewc100", "EWC, strength 100"), ("replay", "replay, 60 per task")]
    fig, axes = plt.subplots(1, 5, figsize=(13.4, 2.9), gridspec_kw=dict(width_ratios=[1, 1, 1, 1, 1.15]))
    T = 5
    for ax, (k, ttl) in zip(axes[:4], names):
        Rm = r[k].mean(0)
        im = ax.imshow(Rm, vmin=0, vmax=1, cmap="viridis")
        for i in range(T):
            for j in range(T):
                ax.text(j, i, "%.2f" % Rm[i, j], ha="center", va="center", fontsize=6.8, color="w" if Rm[i, j] < 0.6 else "k")
        ax.set_xticks(range(T)); ax.set_xticklabels(range(1, T + 1)); ax.set_yticks(range(T)); ax.set_yticklabels(range(1, T + 1))
        ax.set_xlabel("evaluated on task j"); ax.set_title(ttl, fontsize=8.6)
        if k == "naive":
            ax.set_ylabel("after training on task i")
    ax = axes[4]
    fw = np.array([[transfer_scores(r[k][s], r["ind"][s])[0] for s in range(len(r["ind"]))] for k, _ in names])
    bw = np.array([[transfer_scores(r[k][s], r["ind"][s])[1] for s in range(len(r["ind"]))] for k, _ in names])
    avg = np.array([[r[k][s][-1].mean() for s in range(len(r["ind"]))] for k, _ in names])
    x = np.arange(len(names))
    ax.bar(x - 0.27, avg.mean(1), 0.27, color=BLUE, label="final mean accuracy")
    ax.bar(x, bw.mean(1), 0.27, color=RED, label="BWT (19.42)")
    ax.bar(x + 0.27, fw.mean(1), 0.27, color=GREEN, label="FWT (19.41)")
    ax.set_xticks(x); ax.set_xticklabels(["naive", "EWC\n30", "EWC\n100", "replay"], fontsize=7.2)
    ax.axhline(0, color="k", lw=.6); ax.set_ylim(-0.3, 1.15); ax.legend(fontsize=6.5, loc="upper center", ncol=1); ax.set_title("scores (mean of 3 seeds)", fontsize=8.6)
    fig.subplots_adjust(wspace=0.32)
    savefig(fig, CH, "fig19-30", out)
    return r



# ------------------------------------------------------------------ reference quantities for the demonstrations
GRID = np.linspace(-10.0, 10.0, 8001)


def truth_fn(name):
    return {"wavy": lambda x: np.sin(1.2 * x) + 0.25 * x, "quadratic": lambda x: 0.3 * x ** 2 - 0.2, "linear": lambda x: 0.8 * x}[name]


def cs_population(mp, sp, mq, sq, deg, truth):
    """Population (infinite-sample) quantities of the covariate-shift demo, by trapezoid quadrature on GRID.

    A polynomial of degree deg is fitted to f; beta_src minimises the source risk, beta_tgt the target risk, and
    importance weighting with the exact ratio q/p gives beta_tgt in the population. mse_* are the target mean squared
    errors of the fitted functions about f (add the noise variance for the risk). ess is 1/E_p[w^2] (0 if infinite)."""
    f = truth_fn(truth)(GRID)
    p, q = stats.norm.pdf(GRID, mp, sp), stats.norm.pdf(GRID, mq, sq)
    Phi = poly_features(GRID, deg)

    def solve(dens):
        A = np.trapz(dens[:, None, None] * Phi[:, :, None] * Phi[:, None, :], GRID, axis=0)
        b = np.trapz(dens[:, None] * Phi * f[:, None], GRID, axis=0)
        return np.linalg.solve(A, b)

    bs, bt = solve(p), solve(q)
    mse = lambda b: float(np.trapz(q * (Phi @ b - f) ** 2, GRID))
    a2, b2 = sp ** 2, sq ** 2
    if b2 < 2 * a2:
        A_ = (2 * a2 - b2) / (2 * a2 * b2)
        B_ = mq / b2 - mp / (2 * a2)
        ew2 = np.sqrt(2 * np.pi * a2) / (2 * np.pi * b2) * np.sqrt(np.pi / A_) * np.exp(B_ ** 2 / A_ - mq ** 2 / b2 + mp ** 2 / (2 * a2))
        ess = 1.0 / ew2
    else:
        ess = 0.0
    return dict(beta_src=bs.tolist(), beta_tgt=bt.tolist(), mse_src=mse(bs), mse_tgt=mse(bt), ess=float(ess))


def ls1d_boundaries(prior, d):
    """Decision boundaries of the Bayes classifier for x | y=k ~ N(mu_k, 1), mu = (-d, 0, d), under the class prior."""
    pr = np.asarray(prior, float)
    return np.log(pr[0] / pr[1]) / d - d / 2, np.log(pr[1] / pr[2]) / d + d / 2


def ls1d_confusion(prior, d):
    """C[i, j] = P(yhat = i | y = j) for the 1-d Bayes classifier under the given prior (intervals, exact)."""
    b1, b2 = ls1d_boundaries(prior, d)
    mu = np.array([-d, 0.0, d])
    edges = np.array([-np.inf, b1, b2, np.inf])
    if b1 >= b2:                     # the middle class is never chosen
        edges = np.array([-np.inf, 0.5 * (b1 + b2), 0.5 * (b1 + b2), np.inf])
    cdf = stats.norm.cdf(edges[:, None] - mu[None, :])
    return cdf[1:] - cdf[:-1]


def ls1d_exact(d, p, q, n):
    """Exact quantities of the label-shift demo: C, mu = C q, the asymptotic covariance of BBSE with n target points
    (known C), and the accuracies of the source classifier and of the classifier corrected with the true q (cond is the 1-norm condition number)."""
    p, q = np.asarray(p, float), np.asarray(q, float)
    C = ls1d_confusion(p, d)
    mu = C @ q
    Ci = np.linalg.inv(C)
    cov = Ci @ (np.diag(mu) - np.outer(mu, mu)) @ Ci.T / n
    acc_raw = float(np.sum(q * np.diag(C)))
    Cq = ls1d_confusion(q, d)
    acc_corr = float(np.sum(q * np.diag(Cq)))
    return dict(C=C.tolist(), mu=mu.tolist(), sd=np.sqrt(np.diag(cov)).tolist(), acc_raw=acc_raw, acc_corrected=acc_corr,
                cond=float(np.linalg.cond(C, 1)))


def export_reference():
    """Reference numbers of the demonstrations (written to ../data/ch19-reference.json)."""
    os.makedirs(DATA_OUT, exist_ok=True)
    cs_presets = [dict(mp=0.0, sp=1.0, mq=0.5, sq=1.0, deg=1, truth="wavy"), dict(mp=0.0, sp=1.0, mq=1.5, sq=0.8, deg=1, truth="wavy"),
                  dict(mp=0.0, sp=1.0, mq=1.5, sq=0.8, deg=1, truth="linear"), dict(mp=0.0, sp=1.0, mq=2.5, sq=0.6, deg=1, truth="quadratic"),
                  dict(mp=0.0, sp=1.0, mq=1.5, sq=0.8, deg=2, truth="quadratic")]
    ls_presets = [dict(d=2.0, p=[0.45, 0.45, 0.10], q=[0.45, 0.45, 0.10], n=500), dict(d=2.0, p=[0.45, 0.45, 0.10], q=[0.10, 0.30, 0.60], n=500),
                  dict(d=1.0, p=[0.45, 0.45, 0.10], q=[0.10, 0.30, 0.60], n=2000), dict(d=3.0, p=[0.45, 0.45, 0.10], q=[0.10, 0.30, 0.60], n=200)]
    ref = dict(covariate_shift=[dict(params=c, **cs_population(c["mp"], c["sp"], c["mq"], c["sq"], c["deg"], c["truth"])) for c in cs_presets],
               label_shift=[dict(params=c, **ls1d_exact(c["d"], c["p"], c["q"], c["n"])) for c in ls_presets],
               concentration=[dict(sigma=s, mu=m, d=float(distance_to_error(s, m))) for s, m in [(0.2, 0.01), (0.2, 0.1), (0.5, 0.001)]])
    with open(os.path.join(DATA_OUT, "ch19-reference.json"), "w") as f:
        json.dump(ref, f, indent=1)
    print("wrote data/ch19-reference.json")
    # real linear classifier: worst-case l-infinity accuracy curve for several adversarial-training strengths
    Xtr, ytr, Xte, yte = mnist_pair()
    eps = np.round(np.linspace(0, 0.3, 31), 4)
    models = {}
    w0, b0 = fit_logistic_pm(Xtr, ytr, l2=1e-3)
    for et in (0.0, 0.05, 0.1, 0.2):
        w, b = (w0, b0) if et == 0 else fit_logistic_pm(Xtr, ytr, l2=1e-3, eps=et, w0=np.r_[w0, b0])
        models[str(et)] = dict(acc=[round(linear_robust_accuracy(w, b, Xte, yte, e), 4) for e in eps],
                               l1=float(np.abs(w).sum()), l2=float(np.sqrt((w ** 2).sum())),
                               clean=round(linear_robust_accuracy(w, b, Xte, yte, 0.0), 4),
                               margins=np.round(np.quantile(yte * (Xte @ w + b), np.linspace(0.01, 0.99, 50)), 3).tolist())
    with open(os.path.join(DATA_OUT, "ch19-adversarial.json"), "w") as f:
        json.dump(dict(eps=eps.tolist(), models=models, task="MNIST 3 versus 8, logistic regression on 784 pixels in [0, 1]"), f)
    print("wrote data/ch19-adversarial.json")


def fig_export(out=None):
    """Export the JSON reference data used by the demonstrations."""
    export_reference()


FIGURES = {"19.1": fig_19_1, "19.4": fig_19_4, "19.8": fig_19_8_9, "19.10": fig_19_10,
           "19.28": fig_19_28, "19.29": fig_19_29, "19.30": fig_19_30, "19.31": fig_19_31, "19.32": fig_19_32,
           "19.33": fig_19_33, "19.34": fig_19_34, "data": fig_export}

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