"""Murphy (2023), Chapter 33: Interpretability.

Companion code for Chapter 33 of K. P. Murphy, Probabilistic Machine Learning: Advanced Topics
(MIT Press, 2023; December 2025 draft), pp. 1073-1104, and the (title-only) supplement chapter. Written from
scratch with numpy, scipy, scikit-learn and PyTorch, to be read next to the lecture notes
(../ch33-interpretability.html). The chapter has almost no equations: it is a framework (context, end-task,
method, metrics, properties), so the code makes the book's examples concrete and computes the properties the
chapter names.

What is implemented
* Section 33.1.2, the lemonade-stand example: the two models (33.1) and (33.2); the "flip" explanation (does
  setting a feature to its extreme change the prediction?) and the "derivative" explanation (mean absolute
  partial derivative); the dependence of the second on the units of the inputs.
* Section 33.2.3, local explanations: a weighted least-squares local linear surrogate (the limit of LIME with
  infinitely many perturbations), its fidelity, its agreement with the gradient and its stability.
* Section 33.2.1 and 33.5, inherently interpretable models and the supposed accuracy trade-off: a surrogate
  (mimic) decision tree of a random forest, sparse logistic regression, and shallow trees against black boxes.
* Section 33.2.1, sparse models and correlated features: ordinary least squares, ridge and lasso weights over
  bootstrap resamples.
* Section 33.4.1, computational evaluation: the model-parameter randomisation sanity check (cascading
  randomisation of a small network), insertion and deletion curves, and the interaction failure of the
  insertion test.
* Section 33.4.2, user studies: power of between- and within-subject designs (exact noncentral t), sample
  size, family-wise error rate of uncorrected, Bonferroni and Holm testing.

Data. The book's figures use image classifiers and published saliency maps, which need pre-trained networks and
image data that are not available here. Stand-ins are named in each caption: scikit-learn's 8x8 digits for the
randomisation test, scikit-learn's breast-cancer, wine and digits data for the model comparisons, simulation
elsewhere.

Skipped figures, with reasons: 33.1 (the interpretable-ML ecosystem) is a diagram. 33.3 (foreground objects on
backgrounds, Yang and Kim 2019) is a set of photographs of a purpose-built image data set. 33.4 (cascading
randomisation of a pre-trained ImageNet network) needs that network, so the same test is made on a small
network for digits (own figure x33.3). 33.5 (top row from Dabkowski and Gal, bottom row from Ghorbani et al.)
shows saliency patches on photographs from published runs. 33.6 (a trained and an untrained saliency map of a
bird) is a pair of photographs; its message (the human visual system parses wholes, not pixel values) is
quantified by the rank correlation of figure x33.3.

Own figures (not in the book), named as in the notes: x33.1 (two explanation methods disagree on the two
lemonade models), x33.2 (a local linear surrogate: fidelity against locality), x33.3 (randomisation sanity
check), x33.4 (insertion and deletion curves, and their failure with an interaction), x33.5 (a mimic tree and the
no-trade-off comparison), x33.6 (correlated features and unstable weights), x33.7 (power of user-study designs
and multiple-testing correction).
"""
import os
import sys
import json

import numpy as np
from scipy import stats, special

HERE = os.path.dirname(os.path.abspath(__file__))
sys.path.insert(0, HERE)
import common  # noqa: E402
from common import BLUE, CYAN, GREEN, GREY, ORANGE, PURPLE, RED, MAGENTA, plt, savefig, panel_grid, panel_label  # noqa: E402

CH = 33
CACHE_DIR = os.path.join(HERE, "cache", "ch33")
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
os.makedirs(CACHE_DIR, exist_ok=True)
os.makedirs(DATA_OUT, exist_ok=True)


def save_json(name, obj):
    path = os.path.join(DATA_OUT, name)
    with open(path, "w") as f:
        json.dump(obj, f, separators=(",", ":"))
    print("wrote", os.path.relpath(path, os.getcwd()), "(%.0f kB)" % (os.path.getsize(path) / 1e3))


sigmoid = common.sigmoid


# =============================================================================== lemonade stand (33.1.2)
PHI1, PHI2 = 0.7548776662466927, 0.5698402909980532    # additive-recurrence (low-discrepancy) constants


def lemonade_design(n=400):
    """n training days (temperature in degrees F in [50, 100), sidewalk cleanliness in [0, 1)), a deterministic
    low-discrepancy design, so the browser demonstration uses exactly the same points."""
    i = np.arange(1, n + 1)
    T = np.round(50.0 + 50.0 * ((i * PHI1) % 1.0), 6)
    c = np.round((i * PHI2) % 1.0, 6)
    return T, c


def model1(T, c, w=0.0):
    """Model 1, Equation (33.1): p = 0.9 * 1[T > 75] + 0.1 * c; with w > 0 the step is smoothed to a logistic
    ramp of width w degrees (the step is recovered as w -> 0)."""
    step = (np.asarray(T) > 75.0).astype(float) if w <= 0 else sigmoid((np.asarray(T) - 75.0) / w)
    return 0.9 * step + 0.1 * np.asarray(c)


def model2(T, c, k=1.0, maxT=100.0):
    """Model 2, Equation (33.2): p = sigmoid(0.9 (T - 75)/maxT + 0.1 (c - 0.5)); the factor k multiplies the
    argument (k = 1 is the book's model)."""
    return sigmoid(k * (0.9 * (np.asarray(T) - 75.0) / maxT + 0.1 * (np.asarray(c) - 0.5)))


def flip_importance(f, T, c):
    """Explanation 1 of the book: for each training point set one feature at a time to its minimum and to its
    maximum over the training set; the importance of a feature is the fraction of points whose predicted class
    (1[p > 1/2]) changes for at least one of the two extremes. Returns (temperature, cleanliness)."""
    pred = f(T, c) > 0.5
    ch_T = (f(np.full_like(T, T.min()), c) > 0.5) != pred
    ch_T |= (f(np.full_like(T, T.max()), c) > 0.5) != pred
    ch_c = (f(T, np.full_like(c, c.min())) > 0.5) != pred
    ch_c |= (f(T, np.full_like(c, c.max())) > 0.5) != pred
    return ch_T.mean(), ch_c.mean()


def grad_importance(f, T, c, scale_T=1.0, eps=1e-5):
    """Explanation 2 of the book: the mean absolute partial derivative of the output with respect to each input,
    over the training points (central differences). scale_T = maxT measures temperature in units of maxT (a
    rescaling that leaves the model unchanged but changes the derivative by that factor)."""
    dT = (f(T + eps, c) - f(T - eps, c)) / (2 * eps) * scale_T
    dc = (f(T, c + eps) - f(T, c - eps)) / (2 * eps)
    return np.abs(dT).mean(), np.abs(dc).mean()


def lemonade_summary(T, c):
    """The numbers behind figure x33.1."""
    out = {}
    cases = {
        "Model 1": (lambda T_, c_: model1(T_, c_), 1.0),
        "Model 2": (lambda T_, c_: model2(T_, c_), 1.0),
        "Model 2, T/maxT": (lambda T_, c_: model2(T_, c_), 100.0),
    }
    for name, (f, sc) in cases.items():
        out[name] = {"flip": flip_importance(f, T, c), "grad": grad_importance(f, T, c, sc)}
    return out


def fig_33_2(out_dir=None):
    """Figure 33.2: the two lemonade-stand models (33.1) and (33.2)."""
    T, c = lemonade_design()
    TT, CC = np.meshgrid(np.linspace(50, 100, 200), np.linspace(0, 1, 100))
    fig, axes = panel_grid(1, 2, size=(3.6, 3.0), sharey=True)
    for ax, (f, title) in zip(axes[0], [(model1, "Model 1: $0.9\\cdot 1[T>75]+0.1c$"),
                                        (model2, "Model 2: $\\sigma(0.9(T-75)/100+0.1(c-0.5))$")]):
        im = ax.pcolormesh(TT, CC, f(TT, CC), cmap="viridis", vmin=0, vmax=1, shading="auto", rasterized=True)
        ax.contour(TT, CC, f(TT, CC), levels=[0.5], colors="white", linewidths=1.4)
        ax.scatter(T[:60], c[:60], s=5, c="white", edgecolors="k", linewidths=0.2, alpha=0.8)
        ax.set_xlabel("temperature (degrees F)")
        ax.set_title(title, fontsize=9)
    axes[0][0].set_ylabel("sidewalk cleanliness")
    cb = fig.colorbar(im, ax=axes.ravel().tolist(), shrink=0.9, pad=0.02)
    cb.set_label("p(profit)")
    panel_label(axes[0][0], "a", "lower left")
    panel_label(axes[0][1], "b", "lower left")
    savefig(fig, CH, "fig33-2", out_dir)


def fig_x33_1(out_dir=None):
    """Own figure: the two explanation methods disagree on the lemonade models."""
    T, c = lemonade_design()
    s = lemonade_summary(T, c)
    names = list(s)
    labels = ["Model 1", "Model 2\n(T in degrees F)", "Model 2\n(T in units of maxT)"]
    fig, axes = panel_grid(1, 2, size=(4.3, 2.9))
    x = np.arange(3)
    wd = 0.36
    flipT = [s[n]["flip"][0] for n in names]
    flipc = [s[n]["flip"][1] for n in names]
    axes[0][0].bar(x - wd / 2, flipT, wd, color=BLUE, label="temperature")
    axes[0][0].bar(x + wd / 2, flipc, wd, color=ORANGE, label="cleanliness")
    axes[0][0].set_ylabel("fraction of days flipped")
    axes[0][0].set_title("Explanation 1: flip to the extremes", fontsize=9.5)
    gT = np.array([s[n]["grad"][0] for n in names])
    gc = np.array([s[n]["grad"][1] for n in names])
    share = gT / (gT + gc)
    axes[0][1].bar(x - wd / 2, share, wd, color=BLUE, label="temperature")
    axes[0][1].bar(x + wd / 2, 1 - share, wd, color=ORANGE, label="cleanliness")
    axes[0][1].set_ylabel("share of mean |derivative|")
    axes[0][1].set_title("Explanation 2: derivatives", fontsize=9.5)
    for ax in axes[0]:
        ax.set_xticks(x)
        ax.set_xticklabels(labels, fontsize=8)
        ax.set_ylim(0, 1.25)
    axes[0][0].legend(loc="upper right", fontsize=8, ncol=2)
    panel_label(axes[0][0], "a", "upper left")
    panel_label(axes[0][1], "b", "upper left")
    fig.tight_layout()
    savefig(fig, CH, "figx33-1", out_dir)


# =============================================================================== local surrogate (33.2.3)
def bb_logit(x1, x2):
    """A two-feature black box used for local explanations: its logit has an interaction (x1 x2) and a sine."""
    return 2.0 * np.sin(1.4 * x1) + 1.5 * x2 - 1.2 * x1 * x2


def bb(x1, x2):
    return sigmoid(bb_logit(x1, x2))


def bb_grad(x1, x2):
    """Exact gradient of the black box output (chain rule through the logistic)."""
    p = bb(x1, x2)
    g1 = 2.0 * 1.4 * np.cos(1.4 * x1) - 1.2 * x2
    g2 = 1.5 - 1.2 * x1
    return np.array([p * (1 - p) * g1, p * (1 - p) * g2])


def local_surrogate(x0, h, nq=41, span=4.0, f=bb):
    """Weighted least-squares fit of a plane a + b1 u1 + b2 u2 (u = x - x0) to the black box, with Gaussian
    locality weights exp(-|u|^2/(2h^2)) on an nq x nq grid of perturbations over [-span h, span h]^2. This is the
    infinite-sample limit of LIME with a Gaussian kernel (quadrature instead of random perturbations).
    Returns coefficients (a, b1, b2), weighted R^2, weighted class agreement and the weighted rmse."""
    x0 = np.asarray(x0, dtype=float)
    u = np.linspace(-span * h, span * h, nq)
    U1, U2 = np.meshgrid(u, u, indexing="ij")
    w = np.exp(-(U1 ** 2 + U2 ** 2) / (2 * h * h)).ravel()
    X = np.stack([np.ones(nq * nq), U1.ravel(), U2.ravel()], axis=1)
    y = f(x0[0] + U1.ravel(), x0[1] + U2.ravel())
    A = X.T @ (w[:, None] * X)
    beta = np.linalg.solve(A, X.T @ (w * y))
    yh = X @ beta
    ybar = (w * y).sum() / w.sum()
    sse = (w * (y - yh) ** 2).sum()
    sst = (w * (y - ybar) ** 2).sum()
    r2 = 1.0 - sse / sst
    agree = (w * ((yh > 0.5) == (y > 0.5))).sum() / w.sum()
    return beta, r2, agree, np.sqrt(sse / w.sum())


def cosine(a, b):
    a, b = np.asarray(a, float), np.asarray(b, float)
    return float(a @ b / (np.linalg.norm(a) * np.linalg.norm(b)))


def local_report(x0, h, delta=(0.3, 0.0)):
    """Everything the local-surrogate demonstration shows at x0 with kernel width h."""
    beta, r2, agree, rmse = local_surrogate(x0, h)
    g = bb_grad(*x0)
    x1 = np.asarray(x0) + np.asarray(delta)
    beta1, _, _, _ = local_surrogate(x1, h)
    return {"a": beta[0], "b1": beta[1], "b2": beta[2], "r2": r2, "agree": agree, "rmse": rmse,
            "cos_grad": cosine(beta[1:], g), "stab": cosine(beta[1:], beta1[1:]), "f": float(bb(*x0)),
            "g1": g[0], "g2": g[1]}


def fig_x33_2(out_dir=None):
    """Own figure: a local linear surrogate, fidelity against the kernel width."""
    x0 = np.array([0.5, 0.2])
    hs = [0.15, 0.6, 2.0]
    g = np.linspace(-3, 3, 220)
    G1, G2 = np.meshgrid(g, g, indexing="ij")
    P = bb(G1, G2)
    fig, axes = panel_grid(1, 4, size=(3.0, 2.8))
    for ax, h in zip(axes[0][:3], hs):
        ax.pcolormesh(G1, G2, P, cmap="coolwarm", vmin=0, vmax=1, shading="auto", rasterized=True, alpha=0.75)
        ax.contour(G1, G2, P, levels=[0.5], colors="k", linewidths=1.4)
        beta, r2, agree, _ = local_surrogate(x0, h)
        plane = beta[0] + beta[1] * (G1 - x0[0]) + beta[2] * (G2 - x0[1])
        ax.contour(G1, G2, plane, levels=[0.5], colors=[GREEN], linewidths=2.0, linestyles="--")
        th = np.linspace(0, 2 * np.pi, 100)
        ax.plot(x0[0] + h * np.cos(th), x0[1] + h * np.sin(th), color="white", lw=1.2)
        ax.plot(*x0, "o", color="k", ms=5, mec="white")
        ax.set_xlim(-3, 3)
        ax.set_ylim(-3, 3)
        ax.set_title("h = %.2f,  $R^2$ = %.2f" % (h, r2), fontsize=9)
        ax.set_xlabel("$x_1$")
    axes[0][0].set_ylabel("$x_2$")
    hh = np.geomspace(0.05, 3.0, 40)
    rows = [local_report(x0, h) for h in hh]
    ax = axes[0][3]
    ax.semilogx(hh, [r["r2"] for r in rows], color=BLUE, label="weighted $R^2$")
    ax.semilogx(hh, [r["agree"] for r in rows], color=GREEN, label="class agreement")
    ax.semilogx(hh, [r["cos_grad"] for r in rows], color=ORANGE, label="cos(coef, gradient)")
    ax.semilogx(hh, [r["stab"] for r in rows], color=RED, ls="--", label="stability, shift 0.3")
    ax.set_xlabel("kernel width h")
    ax.set_ylim(-0.1, 1.05)
    ax.legend(fontsize=7.5, loc="lower left")
    for i, ax2 in enumerate(axes[0]):
        panel_label(ax2, "abcd"[i], "upper left" if i == 3 else "lower left")
    fig.tight_layout()
    savefig(fig, CH, "figx33-2", out_dir)


# =============================================================================== randomisation sanity check (33.4.1)
def _digits_mlp(seed=0):
    from sklearn.datasets import load_digits
    from sklearn.model_selection import train_test_split
    torch = common.torch_setup(seed)
    X, y = load_digits(return_X_y=True)
    X = X / 16.0
    Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.3, random_state=seed, stratify=y)
    Xtr_t, ytr_t = torch.tensor(Xtr, dtype=torch.float32), torch.tensor(ytr)

    def make():
        return torch.nn.Sequential(torch.nn.Linear(64, 48), torch.nn.ReLU(), torch.nn.Linear(48, 32), torch.nn.ReLU(),
                                   torch.nn.Linear(32, 10))
    net = make()
    opt = torch.optim.Adam(net.parameters(), lr=5e-3)
    for _ in range(300):
        opt.zero_grad()
        loss = torch.nn.functional.cross_entropy(net(Xtr_t), ytr_t)
        loss.backward()
        opt.step()
    acc = (net(torch.tensor(Xte, dtype=torch.float32)).argmax(1).numpy() == yte).mean()
    return torch, net, make, Xte, yte, float(acc)


def _input_grad(torch, net, X, target):
    x = torch.tensor(X, dtype=torch.float32, requires_grad=True)
    out = net(x)
    sel = out[torch.arange(len(X)), torch.tensor(target)].sum()
    sel.backward()
    return x.grad.numpy()


def explanation_maps(torch, net, X, target):
    """Three explanations of the logit of class `target` for each row of X (8x8 images flattened):
    gradient, gradient times input, and a model-independent edge map (gradient magnitude of the image)."""
    g = _input_grad(torch, net, X, target)
    out = {"gradient": np.abs(g), "gradient x input": np.abs(g * X)}
    edge = []
    for x in X:
        im = x.reshape(8, 8)
        gy, gx = np.gradient(im)
        edge.append(np.hypot(gx, gy).ravel())
    out["edge detector (ignores the model)"] = np.array(edge)
    return out


def randomisation_experiment(seed=0, n_img=200):
    torch, net, make, Xte, yte, acc = _digits_mlp(seed)
    X = Xte[:n_img]
    with torch.no_grad():
        pred = net(torch.tensor(X, dtype=torch.float32)).argmax(1).numpy()
    base = explanation_maps(torch, net, X, pred)
    layers = [m for m in net if isinstance(m, torch.nn.Linear)]
    fresh = make()
    freshlayers = [m for m in fresh if isinstance(m, torch.nn.Linear)]
    import copy
    stages = {}
    corr = {k: [1.0] for k in base}
    maps = {0: base}
    rnd = copy.deepcopy(net)
    rl = [m for m in rnd if isinstance(m, torch.nn.Linear)]
    for stage in range(1, 4):
        idx = len(rl) - stage                          # randomise from the logits downwards, cumulatively
        rl[idx].weight.data = freshlayers[idx].weight.data.clone()
        rl[idx].bias.data = freshlayers[idx].bias.data.clone()
        m = explanation_maps(torch, rnd, X, pred)
        maps[stage] = m
        for k in base:
            rs = [stats.spearmanr(base[k][i], m[k][i])[0] for i in range(n_img)]
            corr[k].append(float(np.nanmean(rs)))
    return {"acc": acc, "corr": corr, "maps": maps, "X": X, "pred": pred, "yte": yte[:n_img]}


def fig_x33_3(out_dir=None):
    """Own figure: the model-parameter randomisation test on a digits network."""
    res = randomisation_experiment()
    names = list(res["corr"])
    idx = 0
    fig = plt.figure(figsize=(9.6, 3.9))
    gs = fig.add_gridspec(len(names) + 1, 6, width_ratios=[1, 1, 1, 1, 0.7, 2.6], wspace=0.15, hspace=0.12)
    titles = ["trained", "logits layer\nrandomised", "+ second layer\nrandomised", "all layers\nrandomised"]
    for r in range(len(names) + 1):
        for s in range(4):
            ax = fig.add_subplot(gs[r, s])
            if r == 0:
                ax.imshow(res["X"][idx].reshape(8, 8), cmap="gray_r")
                ax.set_title(titles[s], fontsize=7.5)
            else:
                ax.imshow(res["maps"][s][names[r - 1]][idx].reshape(8, 8), cmap="magma")
            ax.set_xticks([])
            ax.set_yticks([])
            if s == 0:
                ax.set_ylabel("image" if r == 0 else ["gradient", "grad x\ninput", "edge map"][r - 1], fontsize=7.5)
    ax = fig.add_subplot(gs[:, 5])
    for nm, col in zip(names, [BLUE, GREEN, RED]):
        ax.plot(range(4), res["corr"][nm], "o-", color=col, label=nm)
    ax.set_xticks(range(4))
    ax.set_xticklabels(["trained", "1 layer", "2 layers", "3 layers"], fontsize=8)
    ax.set_ylabel("rank correlation with the\nexplanation of the trained network", fontsize=8.5)
    ax.set_xlabel("layers randomised, from the logits down", fontsize=8.5)
    ax.set_ylim(-0.15, 1.05)
    ax.legend(fontsize=7.5, loc="center right")
    ax.axhline(0, color="k", lw=0.5)
    savefig(fig, CH, "figx33-3", out_dir)
    save_json("ch33-sanity-check.json", {"test_accuracy": res["acc"], "rank_correlation": res["corr"]})


# =============================================================================== insertion and deletion (33.4.1)
def cv_acc(model_fn, X, y, folds=5, seed=0):
    from sklearn.model_selection import StratifiedKFold, cross_val_score
    return cross_val_score(model_fn(), X, y, cv=StratifiedKFold(folds, shuffle=True, random_state=seed)).mean()


def insertion_curve(order, X, y, model_fn, kmax):
    """Accuracy of a model refitted on the top-k features of a ranking, k = 1..kmax (insertion test)."""
    return np.array([cv_acc(model_fn, X[:, order[:k]], y) for k in range(1, kmax + 1)])


def deletion_curve(order, X, y, model_fn, kmax):
    """Accuracy of a model refitted after removing the top-k features of a ranking (deletion test)."""
    return np.array([cv_acc(model_fn, X[:, order[k:]], y) for k in range(0, kmax)])


def permutation_importance(model, X, y, n_rep=10, seed=0):
    """Drop in accuracy when one column is permuted (own implementation)."""
    rng = np.random.default_rng(seed)
    base = (model.predict(X) == y).mean()
    imp = np.zeros(X.shape[1])
    for j in range(X.shape[1]):
        d = []
        for _ in range(n_rep):
            Xp = X.copy()
            Xp[:, j] = rng.permutation(Xp[:, j])
            d.append(base - (model.predict(Xp) == y).mean())
        imp[j] = np.mean(d)
    return imp


def interaction_data(n=2000, seed=0):
    """y = 1[0.8 A + 2 B C + noise > 0] with features A, B, C and two noise features: B and C matter only jointly."""
    rng = np.random.default_rng(seed)
    X = rng.standard_normal((n, 5))
    z = 0.8 * X[:, 0] + 2.0 * X[:, 1] * X[:, 2] + 0.3 * rng.standard_normal(n)
    return X, (z > 0).astype(int)


def additive_data(n=1500, p=12, seed=0):
    """Independent standard-normal features and a logistic additive model with decaying weights 2, 1.7, ..., which
    satisfies the no-interaction, no-redundancy assumption of the insertion test."""
    rng = np.random.default_rng(seed)
    w = 2.0 * 0.78 ** np.arange(p)
    X = rng.standard_normal((n, p))
    y = (rng.random(n) < sigmoid(X @ w)).astype(int)
    return X, y, w


def forward_greedy(X, y, model_fn, kmax):
    """Greedy forward selection by cross-validated accuracy (a strong reference ranking)."""
    chosen = []
    for _ in range(kmax):
        best = max((j for j in range(X.shape[1]) if j not in chosen), key=lambda j: cv_acc(model_fn, X[:, chosen + [j]], y))
        chosen.append(best)
    return chosen


def fig_x33_4(out_dir=None):
    """Own figure: insertion/deletion curves (additive simulation, breast-cancer data) and the interaction failure."""
    from sklearn.datasets import load_breast_cancer
    from sklearn.linear_model import LogisticRegression
    from sklearn.ensemble import GradientBoostingClassifier
    from sklearn.preprocessing import StandardScaler
    lr = lambda: LogisticRegression(C=1.0, max_iter=2000)
    rng = np.random.default_rng(0)
    # (a), (b): independent additive model
    Xs, ys, w = additive_data()
    ords = np.argsort(-np.abs(w))
    kmax = 11
    ins_top = insertion_curve(ords, Xs, ys, lr, kmax)
    ins_bot = insertion_curve(ords[::-1], Xs, ys, lr, kmax)
    ins_rnd = np.mean([insertion_curve(rng.permutation(12), Xs, ys, lr, kmax) for _ in range(8)], axis=0)
    del_top = deletion_curve(ords, Xs, ys, lr, kmax)
    del_bot = deletion_curve(ords[::-1], Xs, ys, lr, kmax)
    del_rnd = np.mean([deletion_curve(rng.permutation(12), Xs, ys, lr, kmax) for _ in range(8)], axis=0)
    # (c): breast cancer, correlated features
    Xb, yb = load_breast_cancer(return_X_y=True)
    Xb = StandardScaler().fit_transform(Xb)
    full = LogisticRegression(C=1.0, max_iter=2000).fit(Xb, yb)
    order = np.argsort(-np.abs(full.coef_[0]))
    kb = 8
    bc_coef = insertion_curve(order, Xb, yb, lr, kb)
    bc_rnd = np.mean([insertion_curve(rng.permutation(30), Xb, yb, lr, kb) for _ in range(8)], axis=0)
    bc_greedy = insertion_curve(np.array(forward_greedy(Xb, yb, lr, kb)), Xb, yb, lr, kb)
    # (d): interaction
    Xi, yi = interaction_data()
    gb = lambda: GradientBoostingClassifier(n_estimators=60, max_depth=3, random_state=0)
    marg = np.array([abs(np.corrcoef(Xi[:, j], yi)[0, 1]) for j in range(5)])
    model = gb().fit(Xi, yi)
    pimp = permutation_importance(model, Xi, yi)
    ins_marg = insertion_curve(np.argsort(-marg), Xi, yi, gb, 5)
    ins_perm = insertion_curve(np.argsort(-pimp), Xi, yi, gb, 5)
    fig, axes = panel_grid(1, 4, size=(3.1, 2.8))
    k = np.arange(1, kmax + 1)
    ax = axes[0][0]
    ax.plot(k, ins_top, "o-", color=BLUE, ms=3.5, label="largest weight first")
    ax.plot(k, ins_rnd, "s--", color=GREY, ms=3, label="random order")
    ax.plot(k, ins_bot, "^-", color=RED, ms=3.5, label="smallest weight first")
    ax.set_xlabel("features inserted"); ax.set_ylabel("cross-validated accuracy")
    ax.set_title("insertion, independent features", fontsize=9)
    ax.legend(fontsize=7, loc="lower right")
    ax = axes[0][1]
    ax.plot(np.arange(0, kmax), del_top, "o-", color=BLUE, ms=3.5)
    ax.plot(np.arange(0, kmax), del_rnd, "s--", color=GREY, ms=3)
    ax.plot(np.arange(0, kmax), del_bot, "^-", color=RED, ms=3.5)
    ax.set_xlabel("features deleted"); ax.set_title("deletion, independent features", fontsize=9)
    ax = axes[0][2]
    kb_ = np.arange(1, kb + 1)
    ax.plot(kb_, bc_coef, "o-", color=BLUE, ms=3.5, label="ranked by |weight|")
    ax.plot(kb_, bc_rnd, "s--", color=GREY, ms=3, label="random order")
    ax.plot(kb_, bc_greedy, "d-", color=GREEN, ms=3.5, label="greedy forward selection")
    ax.set_xlabel("features inserted"); ax.set_title("insertion, breast-cancer data", fontsize=9)
    ax.legend(fontsize=7, loc="lower right")
    ax = axes[0][3]
    kx = np.arange(1, 6)
    ax.plot(kx, ins_marg, "o-", color=RED, label="marginal correlation")
    ax.plot(kx, ins_perm, "s-", color=BLUE, label="permutation importance")
    ax.set_xticks(kx); ax.set_xlabel("features inserted"); ax.set_title("features B and C interact", fontsize=9)
    ax.legend(fontsize=7, loc="lower right")
    for i, a in enumerate(axes[0]):
        panel_label(a, "abcd"[i], "upper left" if i != 1 else "upper right")
    fig.tight_layout()
    savefig(fig, CH, "figx33-4", out_dir)
    return {"ins_top": ins_top, "del_top": del_top, "bc_coef": bc_coef, "bc_greedy": bc_greedy, "ins_marg": ins_marg, "ins_perm": ins_perm}


# =============================================================================== mimic tree, no trade-off (33.2, 33.5)
def mimic_trees(seed=0):
    from sklearn.datasets import load_breast_cancer
    from sklearn.ensemble import RandomForestClassifier
    from sklearn.tree import DecisionTreeClassifier
    from sklearn.model_selection import train_test_split
    X, y = load_breast_cancer(return_X_y=True)
    Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.3, random_state=seed, stratify=y)
    rf = RandomForestClassifier(n_estimators=200, random_state=seed).fit(Xtr, ytr)
    rng = np.random.default_rng(seed)
    sd = Xtr.std(0)
    aug = np.vstack([Xtr] + [Xtr + 0.25 * sd * rng.standard_normal(Xtr.shape) for _ in range(6)])
    rf_lab = rf.predict(aug)
    rows = []
    for d in range(1, 9):
        mimic = DecisionTreeClassifier(max_depth=d, random_state=seed).fit(aug, rf_lab)
        direct = DecisionTreeClassifier(max_depth=d, random_state=seed).fit(Xtr, ytr)
        rows.append({"depth": d, "leaves": mimic.get_n_leaves(),
                     "fidelity": float((mimic.predict(Xte) == rf.predict(Xte)).mean()),
                     "acc_mimic": float((mimic.predict(Xte) == yte).mean()),
                     "acc_direct": float((direct.predict(Xte) == yte).mean())})
    return rows, float((rf.predict(Xte) == yte).mean())


def tradeoff_table(seed=0):
    from sklearn.datasets import load_breast_cancer, load_wine, load_digits, load_iris
    from sklearn.ensemble import RandomForestClassifier, GradientBoostingClassifier
    from sklearn.linear_model import LogisticRegressionCV
    from sklearn.tree import DecisionTreeClassifier
    from sklearn.preprocessing import StandardScaler
    from sklearn.pipeline import make_pipeline
    out = {}
    for name, loader in [("breast cancer", load_breast_cancer), ("wine", load_wine), ("iris", load_iris), ("digits", load_digits)]:
        X, y = loader(return_X_y=True)
        sparse = lambda: make_pipeline(StandardScaler(), LogisticRegressionCV(Cs=8, penalty="l1", solver="saga", max_iter=3000, cv=3, random_state=seed, tol=1e-3))
        tree3 = lambda: DecisionTreeClassifier(max_depth=3, random_state=seed)
        rf = lambda: RandomForestClassifier(n_estimators=150, random_state=seed)
        gbm = lambda: GradientBoostingClassifier(n_estimators=100, max_depth=3, random_state=seed)
        if name == "digits":
            sparse = lambda: make_pipeline(StandardScaler(), LogisticRegressionCV(Cs=5, penalty="l1", solver="saga", max_iter=800, cv=3, random_state=seed, tol=1e-2))
            gbm = lambda: GradientBoostingClassifier(n_estimators=40, max_depth=3, random_state=seed)
        out[name] = {"sparse logistic": cv_acc(sparse, X, y, 5, seed), "depth-3 tree": cv_acc(tree3, X, y, 5, seed),
                     "random forest": cv_acc(rf, X, y, 5, seed), "boosting": cv_acc(gbm, X, y, 5, seed)}
    return out


def fig_x33_5(out_dir=None):
    """Own figure: fidelity of a mimic tree against its size; interpretable models against black boxes."""
    rows, rf_acc = mimic_trees()
    tab = tradeoff_table()
    fig, axes = panel_grid(1, 2, size=(4.4, 3.0))
    ax = axes[0][0]
    lv = [r["leaves"] for r in rows]
    ax.plot(lv, [r["fidelity"] for r in rows], "o-", color=BLUE, label="fidelity to the forest")
    ax.plot(lv, [r["acc_mimic"] for r in rows], "s--", color=GREEN, label="accuracy of the mimic")
    ax.plot(lv, [r["acc_direct"] for r in rows], "^:", color=ORANGE, label="tree fitted to the labels")
    ax.axhline(rf_acc, color=GREY, lw=1, ls="-.")
    ax.text(2.1, rf_acc - 0.003, "random forest", ha="left", va="top", fontsize=8, color=GREY)
    ax.set_xscale("log"); ax.set_xlabel("leaves of the tree"); ax.set_ylabel("test accuracy / agreement")
    ax.set_ylim(0.8, 0.975)
    ax.legend(fontsize=7.5, loc="lower right")
    panel_label(ax, "a", "upper left")
    ax = axes[0][1]
    names = list(tab)
    models = ["sparse logistic", "depth-3 tree", "random forest", "boosting"]
    cols = [GREEN, ORANGE, BLUE, PURPLE]
    x = np.arange(len(names))
    for j, (m, col) in enumerate(zip(models, cols)):
        ax.bar(x + (j - 1.5) * 0.2, [tab[n][m] for n in names], 0.2, color=col, label=m)
    ax.set_xticks(x); ax.set_xticklabels(names, fontsize=8.5)
    ax.set_ylim(0.4, 1.0); ax.set_ylabel("5-fold cross-validated accuracy")
    ax.legend(fontsize=7, loc="lower center", ncol=4, bbox_to_anchor=(0.5, 1.0), handlelength=1.2, columnspacing=0.8)
    panel_label(ax, "b", "lower left")
    fig.tight_layout()
    savefig(fig, CH, "figx33-5", out_dir)


# =============================================================================== correlated features (33.2.1)
def correlated_weights(rho, n=100, sigma=1.0, B=300, seed=0, lam_lasso=0.15, lam_ridge=5.0):
    """Bootstrap distribution of the two weights of OLS, ridge and lasso when y = x1 + x2 + noise and corr(x1, x2) = rho."""
    from sklearn.linear_model import Lasso, Ridge, LinearRegression
    rng = np.random.default_rng(seed)
    cov = np.array([[1, rho], [rho, 1.0]])
    X = rng.multivariate_normal([0, 0], cov, size=n)
    y = X.sum(1) + sigma * rng.standard_normal(n)
    out = {"OLS": [], "ridge": [], "lasso": []}
    for _ in range(B):
        i = rng.integers(0, n, n)
        out["OLS"].append(LinearRegression().fit(X[i], y[i]).coef_)
        out["ridge"].append(Ridge(alpha=lam_ridge).fit(X[i], y[i]).coef_)
        out["lasso"].append(Lasso(alpha=lam_lasso, max_iter=20000).fit(X[i], y[i]).coef_)
    return {k: np.array(v) for k, v in out.items()}, X, y


def fig_x33_6(out_dir=None):
    """Own figure: correlated features make weights unstable; sparsity picks one of them."""
    fig, axes = panel_grid(1, 3, size=(3.3, 3.0), sharex=True, sharey=True)
    res, X, y = correlated_weights(0.98)
    for ax, (k, col) in zip(axes[0], [("OLS", RED), ("ridge", BLUE), ("lasso", GREEN)]):
        W = res[k]
        ax.scatter(W[:, 0], W[:, 1], s=7, color=col, alpha=0.5)
        ax.plot([1], [1], "k*", ms=9)
        ax.plot([-1, 3], [3, -1], color=GREY, lw=0.8, ls=":")
        ax.set_title("%s: sd(w1) = %.2f" % (k, W[:, 0].std()), fontsize=9)
        ax.set_xlabel("$w_1$")
    axes[0][0].set_ylabel("$w_2$")
    axes[0][0].set_xlim(-1, 3); axes[0][0].set_ylim(-1, 3)
    for i, a in enumerate(axes[0]):
        panel_label(a, "abc"[i], "upper right")
    fig.tight_layout()
    savefig(fig, CH, "figx33-6", out_dir)


# =============================================================================== user studies (33.4.2)
def power_t_two_sided(lam, nu, alpha):
    """Exact power of the two-sided t-test with noncentrality lam and nu degrees of freedom."""
    tc = stats.t.ppf(1 - alpha / 2, nu)
    return float(stats.nct.sf(tc, nu, lam) + stats.nct.cdf(-tc, nu, lam))


def power_between(d, n, alpha=0.05):
    """Two arms of n participants each (independent samples, equal variances), standardised effect d."""
    return power_t_two_sided(d * np.sqrt(n / 2.0), 2 * n - 2, alpha)


def power_within(d, n, rho, alpha=0.05):
    """n participants each seeing both conditions, within-participant correlation rho (paired t-test)."""
    return power_t_two_sided(d * np.sqrt(n / (2.0 * (1.0 - rho))), n - 1, alpha)


def n_for_power(power_fn, target=0.8, nmax=2000):
    for n in range(3, nmax):
        if power_fn(n) >= target:
            return n
    return None


def holm_reject(p, alpha=0.05):
    """Holm's step-down procedure: boolean rejections for an array of p-values."""
    p = np.asarray(p)
    m = len(p)
    order = np.argsort(p)
    rej = np.zeros(m, bool)
    for r, i in enumerate(order):
        if p[i] <= alpha / (m - r):
            rej[i] = True
        else:
            break
    return rej


def simulate_corrections(m, n_true, d, n, alpha=0.05, reps=20000, seed=0):
    """z-test p-values for m independent comparisons, n_true of them with true effect d (n per arm).
    Returns FWER (some true null rejected) and average power on true effects for none/Bonferroni/Holm."""
    rng = np.random.default_rng(seed)
    lam = np.zeros(m)
    lam[:n_true] = d * np.sqrt(n / 2.0)
    z = rng.standard_normal((reps, m)) + lam
    p = 2 * stats.norm.sf(np.abs(z))
    out = {}
    rej = {"none": p <= alpha, "Bonferroni": p <= alpha / m, "Holm": np.array([holm_reject(r, alpha) for r in p])}
    for k, r in rej.items():
        out[k] = {"fwer": float(r[:, n_true:].any(1).mean()) if n_true < m else 0.0,
                  "power": float(r[:, :n_true].mean()) if n_true > 0 else 0.0}
    return out


def fig_x33_7(out_dir=None):
    """Own figure: power of between- and within-subject designs, and the cost of multiple comparisons."""
    d = 0.5
    ns = np.arange(4, 130)
    fig, axes = panel_grid(1, 3, size=(3.3, 2.9))
    ax = axes[0][0]
    ax.plot(ns, [power_between(d, n) for n in ns], color=RED, label="between (two groups)")
    for rho, col in [(0.0, GREY), (0.5, BLUE), (0.8, GREEN)]:
        ax.plot(ns, [power_within(d, n, rho) for n in ns], color=col, ls="--", label=r"within, $\rho$ = %.1f" % rho)
    ax.axhline(0.8, color="k", lw=0.6, ls=":")
    ax.set_xlabel("participants per group (or in total, within)"); ax.set_ylabel("power, d = 0.5")
    ax.legend(fontsize=7.2, loc="lower right")
    ms = np.arange(1, 21)
    ax = axes[0][1]
    ax.plot(ms, 1 - (1 - 0.05) ** ms, color=RED, label="no correction")
    ax.plot(ms, 1 - (1 - 0.05 / ms) ** ms, color=BLUE, label="Bonferroni or Holm")
    ax.axhline(0.05, color="k", lw=0.6, ls=":")
    ax.set_xlabel("number of comparisons m"); ax.set_ylabel("family-wise error rate")
    ax.legend(fontsize=7.5, loc="center right")
    ax = axes[0][2]
    pw = {k: [] for k in ["none", "Bonferroni", "Holm"]}
    mlist = [2, 4, 6, 8, 10, 12]
    for m in mlist:
        r = simulate_corrections(m, m // 2, 0.5, 64, reps=6000)
        for k in pw:
            pw[k].append(r[k]["power"])
    for k, col in zip(pw, [RED, BLUE, GREEN]):
        ax.plot(mlist, pw[k], "o-", color=col, ms=3.5, label=k)
    ax.set_xlabel("m comparisons, half with d = 0.5"); ax.set_ylabel("power per true effect (n = 64)")
    ax.legend(fontsize=7.5, loc="center right")
    for i, a in enumerate(axes[0]):
        panel_label(a, "abc"[i], "upper left" if i != 0 else "upper left")
    fig.tight_layout()
    savefig(fig, CH, "figx33-7", out_dir)


# =============================================================================== data for the demonstrations
def export_demo_data(out_dir=None):
    """Small files read by the demonstration pages."""
    T, c = lemonade_design()
    save_json("ch33-lemonade.json", {"T": [round(float(v), 6) for v in T], "c": [round(float(v), 6) for v in c]})


def data_demo(out_dir=None):
    export_demo_data()


FIGURES = {
    "33.2": fig_33_2, "x33.1": fig_x33_1, "x33.2": fig_x33_2, "x33.3": fig_x33_3, "x33.4": fig_x33_4,
    "x33.5": fig_x33_5, "x33.6": fig_x33_6, "x33.7": fig_x33_7, "data": data_demo,
}

if __name__ == "__main__":
    if len(sys.argv) == 1:
        common.run(FIGURES, CH, [])
    else:
        common.run(FIGURES, CH)
