"""Murphy (2022), Chapter 5: Decision Theory.

Companion code for Chapter 5 of K. P. Murphy, Probabilistic Machine Learning: An Introduction (MIT Press,
2022), written from scratch with numpy, scipy and matplotlib, to be read next to the lecture notes
(../ch05-decision-theory.html). Library routines (scikit-learn ROC curves, scipy distributions) are only
used to confirm the implementations.

Methods
* Section 5.1.1: bayes_action (5.1)-(5.3), covid_policy (Tables 5.1 and 5.2 recomputed from the
  Bayes-rule posterior of the book's COVID-19 example: prevalence 0.1, sensitivity 0.875, specificity 0.975).
* Section 5.1.2: cost_threshold (5.9)-(5.10), chow_rule (5.12)-(5.15), the reject option.
* Section 5.1.3-5.1.4: roc_points, pr_points, auc_trapz, auc_rank (the Mann-Whitney form), eer, fbeta,
  average_precision (interpolated), precision_at_prevalence (5.28), fbeta_from_rates (5.31).
* Section 5.1.5: l2, l1, huber losses (5.32), (5.35), (5.36).
* Section 5.1.6: kl, cross_entropy, brier (5.44) and the properness of the log and Brier scores.
* Section 5.2: coin_logml (5.47), poly_log_evidence and poly_eb_fit (empirical-Bayes evidence of a
  polynomial regression, Figures 5.5 and 5.6), gauss_evidence_density (the Occam picture of Figure 5.7),
  bic, aic, waic (computed from posterior draws), bayes_t (5.2.6.1), prob_theta1_gt_theta2 (5.2.6.2).
* Section 5.3: risk_* (5.67)-(5.73) for the five estimators of Figure 5.8, median_var_exact, the
  James-Stein estimator and its exact risk (Stein's paradox, Section 5.3.3).
* Section 5.4: hoeffding_bound (5.93) and its simulation, optimism of the training error.
* Section 5.5: np_threshold, power curves, p_value_wald, permutation_pvalue, p_h0_given_significant
  (5.108)-(5.110), sbb_lower_bound (the "30 per cent" of Section 5.5.4).

Data. The book's figures use hypothetical systems and simulated data, so everything here is simulated with
fixed seeds, except the supplementary breast-cancer classifier used by the browser demonstration (the
scikit-learn breast-cancer data, a logistic regression, held-out test set).

Figures. Reproduced: 5.1 (reject option, computed analogue), 5.2, 5.3, 5.4, 5.5, 5.6, 5.7 (Occam picture,
computed with Gaussian models instead of the schematic), 5.8, 5.9, 5.10. Skipped: 5.11 (a cartoon, nothing
computed). Supplementary figures for the gaps filled in the notes:
  5.S1 ROC and precision-recall curves of the same classifier at three prevalences (Section 5.1.4.4);
  5.S2 the posterior of the difference in left-handedness rates and the Bayesian chi-square test (5.2.6.2);
  5.S3 the Stein paradox: exact risk of the James-Stein estimator (5.3.3);
  5.S4 the bound (5.93) against simulation (5.4.4.1);
  5.S5 p-values and posteriors: the lower bound on p(H0|D), the 36 per cent of (5.110), the Lindley paradox (5.5.4).
Run `python3 ch05_decision_theory.py --list`, `python3 ch05_decision_theory.py` (all figures, about one minute
on one CPU thread) or `python3 ch05_decision_theory.py --fig 5.2`. Files go to ../img/ch05/; the data used by
the browser demonstrations go to ../data/ch05-*.json.
"""
import functools
import json
import math
import os

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

import common
from common import BLUE, GREEN, GREY, MAGENTA, ORANGE, PURPLE, RED, panel_grid, panel_label, savefig
import matplotlib.pyplot as plt

CH = 5
HERE = os.path.dirname(os.path.abspath(__file__))
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
Phi_ = stats.norm.cdf


# =========================================================================== 5.1.1 Bayesian decision theory
def bayes_action(loss, post):
    """Equations (5.1)-(5.2). loss[h, a] is the loss of action a in state h, post[h] = p(h|x).
    Returns (risks rho(a|x), index of the optimal action)."""
    rho = np.asarray(post) @ np.asarray(loss)
    return rho, int(np.argmin(rho))


def covid_posterior(prev=0.1, sens=0.875, spec=0.975):
    """p(covid | test positive) and p(covid | test negative) by Bayes' rule (Section 2.3.1 of the book)."""
    pos = sens * prev / (sens * prev + (1 - spec) * (1 - prev))
    neg = (1 - sens) * prev / ((1 - sens) * prev + spec * (1 - prev))
    return pos, neg


def covid_policy(drug_cost=8.0, qaly_young=60.0, qaly_old=10.0, prev=0.1, sens=0.875, spec=0.975):
    """Table 5.2: one row (test, age, p(covid), cost of nothing, cost of the drug, action) per observation."""
    pos, neg = covid_posterior(prev, sens, spec)
    rows = []
    for test, p in ((0, neg), (1, pos)):
        for age, q in ((0, qaly_young), (1, qaly_old)):
            # loss matrix over the two disease states (no covid, covid): nothing costs 0 or q; the drug costs drug_cost
            L = np.array([[0.0, drug_cost], [q, drug_cost]])
            rho, a = bayes_action(L, np.array([1 - p, p]))
            rows.append((test, age, p, rho[0], rho[1], a))
    return rows


# =========================================================================== 5.1.2 classification
def cost_threshold(l00, l01, l10, l11):
    """The threshold on p1 = p(y=1|x) below which label 0 is chosen, from (5.9) with general l00, l11.
    l_ij: true class i, predicted class j."""
    return (l01 - l00) / ((l01 - l00) + (l10 - l11))


def chow_rule(post, lam_r, lam_e):
    """Equations (5.12)-(5.15). post: (n, C) posteriors; returns labels in 0..C-1 or -1 for reject."""
    post = np.asarray(post)
    ystar = post.argmax(1)
    pstar = post.max(1)
    thr = 1 - lam_r / lam_e
    return np.where(pstar > thr, ystar, -1)


# =========================================================================== 5.1.3-5.1.4 ROC, PR, F
def roc_points(score, y):
    """ROC curve of the rule 'predict 1 iff score >= t' for all thresholds t, from (0,0) to (1,1)."""
    score = np.asarray(score, float)
    y = np.asarray(y).astype(int)
    order = np.argsort(-score, kind="mergesort")
    s, yy = score[order], y[order]
    distinct = np.r_[np.flatnonzero(np.diff(s)), len(s) - 1]       # last index of each tie group
    tp = np.cumsum(yy)[distinct]
    fp = (distinct + 1) - tp
    P, N = y.sum(), (1 - y).sum()
    return np.r_[0, fp / N], np.r_[0, tp / P], np.r_[np.inf, s[distinct]]


def auc_trapz(fpr, tpr):
    return float(np.sum(np.diff(fpr) * (tpr[1:] + tpr[:-1]) / 2))


def auc_rank(score, y):
    """AUC as P(S_1 > S_0) + P(S_1 = S_0)/2 (the Mann-Whitney statistic)."""
    score = np.asarray(score, float)
    y = np.asarray(y).astype(int)
    r = stats.rankdata(score)
    n1, n0 = y.sum(), (1 - y).sum()
    return float((r[y == 1].sum() - n1 * (n1 + 1) / 2) / (n1 * n0))


def eer(fpr, tpr):
    """Equal error rate: the value of FPR = FNR = 1 - TPR (linear interpolation along the curve)."""
    d = fpr - (1 - tpr)
    i = int(np.argmax(d >= 0))
    if i == 0:
        return float(fpr[0])
    t = -d[i - 1] / (d[i] - d[i - 1])
    return float(fpr[i - 1] + t * (fpr[i] - fpr[i - 1]))


def pr_points(score, y):
    """Precision-recall curve: recall and precision at every threshold, in increasing recall."""
    fpr, tpr, thr = roc_points(score, y)
    y = np.asarray(y).astype(int)
    P, N = y.sum(), (1 - y).sum()
    tp, fp = tpr[1:] * P, fpr[1:] * N
    return tpr[1:], tp / (tp + fp)


def average_precision(score, y):
    """Mean of the interpolated precision: the area under the interpolated PR curve (Section 5.1.4.2)."""
    rec, prec = pr_points(score, y)
    interp = np.maximum.accumulate(prec[::-1])[::-1]               # max precision at recall >= r
    r = np.r_[0, rec]
    return float(np.sum(np.diff(r) * interp))


def fbeta(prec, rec, beta=1.0):
    return (1 + beta ** 2) * prec * rec / (beta ** 2 * prec + rec)


def fbeta_counts(tp, fp, fn, beta=1.0):
    """Second form of (5.25)."""
    return (1 + beta ** 2) * tp / ((1 + beta ** 2) * tp + beta ** 2 * fn + fp)


def precision_at_prevalence(tpr, fpr, r):
    """(5.28): precision from the two rates and the ratio r = P/N."""
    return tpr / (tpr + fpr / r)


def fbeta_from_rates(tpr, fpr, r, beta=1.0):
    """(5.31)."""
    return (1 + beta ** 2) * tpr / (tpr + fpr / r + beta ** 2)


def binormal_scores(n_pos, n_neg, dprime, rng):
    """Scores of a hypothetical classifier: N(0,1) for negatives and N(dprime,1) for positives."""
    s = np.r_[rng.standard_normal(n_neg), dprime + rng.standard_normal(n_pos)]
    y = np.r_[np.zeros(n_neg, int), np.ones(n_pos, int)]
    return s, y


def binormal_roc(dprime, x):
    """Exact ROC of the binormal model at score thresholds x: (FPR, TPR)."""
    return 1 - Phi_(x), 1 - Phi_(x - dprime)


# =========================================================================== 5.1.5 losses
def l2(h, a):
    return (h - a) ** 2


def l1(h, a):
    return np.abs(h - a)


def huber(h, a, delta=1.5):
    r = np.abs(h - a)
    return np.where(r <= delta, r ** 2 / 2, delta * r - delta ** 2 / 2)


# =========================================================================== 5.1.6 probabilistic prediction
def entropy(p):
    p = np.asarray(p, float)
    nz = p > 0
    return float(-(p[nz] * np.log(p[nz])).sum())


def cross_entropy(p, q):
    p, q = np.asarray(p, float), np.asarray(q, float)
    nz = p > 0
    return float(-(p[nz] * np.log(q[nz])).sum())


def kl(p, q):
    return cross_entropy(p, q) - entropy(p)


def brier(q, y_onehot):
    """(5.44): mean over examples of the squared distance between predicted and one-hot vectors."""
    return float(np.mean(np.sum((np.asarray(q) - np.asarray(y_onehot)) ** 2, axis=1)))


# =========================================================================== 5.2 model choice
def coin_logml(n1, n0, a1=1.0, a0=1.0):
    """log p(D|M1) of a particular sequence with n1 heads and n0 tails, Beta(a1, a0) prior (5.47)."""
    return special.betaln(a1 + n1, a0 + n0) - special.betaln(a1, a0)


def coin_logml0(n1, n0):
    """log p(D|M0) for the fair coin (5.46)."""
    return (n1 + n0) * math.log(0.5)


def coin_bic_logml(n1, n0):
    """BIC approximation (5.59) to log p(D|M1): log p(D | MLE) - (1/2) log N."""
    n = n1 + n0
    th = n1 / n
    ll = (n1 * math.log(th) if n1 else 0.0) + (n0 * math.log(1 - th) if n0 else 0.0)
    return ll - 0.5 * math.log(n)


def bic(loglik, k, n):
    """(5.60)."""
    return -2 * loglik + k * math.log(n)


def aic(loglik, k):
    """(5.61)."""
    return -2 * loglik + 2 * k


def poly_design(x, deg, centre=5.0, scale=5.0):
    u = (np.asarray(x, float) - centre) / scale
    return np.vander(u, deg + 1, increasing=True)


def poly_log_evidence(y, Phi, alpha, beta):
    """log N(y | 0, I/beta + Phi Phi^T / alpha): the marginal likelihood of Bayesian linear regression with
    prior w ~ N(0, I/alpha) and noise precision beta."""
    n = len(y)
    C = np.eye(n) / beta + Phi @ Phi.T / alpha
    L = np.linalg.cholesky(C)
    z = np.linalg.solve(L, y)
    return float(-0.5 * (n * math.log(2 * math.pi) + 2 * np.log(np.diag(L)).sum() + z @ z))


def poly_eb_fit(y, Phi):
    """Empirical Bayes: maximise the evidence over (alpha, beta). Returns (logev, alpha, beta)."""
    f = lambda t: -poly_log_evidence(y, Phi, math.exp(t[0]), math.exp(t[1]))
    best = None
    for a0 in (-2.0, 0.0, 2.0):
        for b0 in (-3.0, 0.0, 2.0):
            r = optimize.minimize(f, [a0, b0], method="L-BFGS-B", bounds=[(-12, 12), (-12, 12)])
            if best is None or r.fun < best.fun:
                best = r
    return -float(best.fun), math.exp(best.x[0]), math.exp(best.x[1])


def poly_posterior(y, Phi, alpha, beta):
    """Posterior mean and covariance of the weights."""
    S = np.linalg.inv(alpha * np.eye(Phi.shape[1]) + beta * Phi.T @ Phi)
    return beta * S @ Phi.T @ y, S


def poly_true(x):
    u = (np.asarray(x, float) - 5.0) / 5.0
    return 22.0 + 17.0 * u + 12.0 * u ** 2


def poly_data(n, seed, sigma=4.0):
    rng = np.random.default_rng(seed)
    x = np.sort(rng.uniform(0.0, 10.0, n))
    return x, poly_true(x) + sigma * rng.standard_normal(n)


def poly_model_posterior(x, y, degrees=(1, 2, 3)):
    """Uniform prior over the degrees; returns (log evidences, posterior probabilities, fits)."""
    logev, fits = [], []
    for d in degrees:
        Phi = poly_design(x, d)
        le, a, b = poly_eb_fit(y, Phi)
        logev.append(le)
        fits.append((a, b))
    logev = np.array(logev)
    post = np.exp(logev - special.logsumexp(logev))
    return logev, post, fits


def gauss_evidence_density(xbar, tau, n):
    """Model M_tau: theta ~ N(0, tau^2), x_i ~ N(theta, 1) iid. The sufficient statistic xbar has marginal
    density N(0, tau^2 + 1/n): the 'predictive distribution over data sets' of Figure 5.7."""
    return stats.norm.pdf(xbar, 0.0, math.sqrt(tau ** 2 + 1.0 / n))


def waic(loglik_draws):
    """Watanabe-Akaike criterion from posterior draws; loglik_draws[s, n] = log p(y_n | theta_s).
    Returns (lppd, p_waic, WAIC deviance scale -2 (lppd - p_waic)). The complexity term is the sum over data
    points of the variance over draws of the log likelihood (Gelman et al. 2014)."""
    lppd = float(np.sum(special.logsumexp(loglik_draws, axis=0) - math.log(loglik_draws.shape[0])))
    pw = float(np.sum(np.var(loglik_draws, axis=0, ddof=1)))
    return lppd, pw, -2 * (lppd - pw)


def bayes_t(d):
    """Posterior of the mean difference under the prior 1/sigma^2: Student T_{N-1}(mu, s^2/N) (Section 5.2.6.1)."""
    d = np.asarray(d, float)
    n = len(d)
    return stats.t(df=n - 1, loc=d.mean(), scale=d.std(ddof=1) / math.sqrt(n))


def prob_theta1_gt_theta2(y1, n1, y2, n2, eps=0.0):
    """p(theta1 - theta2 > eps | D) with uniform priors, by numerical integration (5.63)."""
    b1 = stats.beta(y1 + 1, n1 - y1 + 1)
    b2 = stats.beta(y2 + 1, n2 - y2 + 1)
    f = lambda t: b1.pdf(t) * b2.cdf(t - eps)
    return integrate.quad(f, eps, 1.0, epsabs=1e-12, epsrel=1e-12, limit=200)[0]


def delta_density(d, y1, n1, y2, n2):
    """Posterior density of Delta = theta1 - theta2 at d (the convolution of the two Beta densities)."""
    b1 = stats.beta(y1 + 1, n1 - y1 + 1)
    b2 = stats.beta(y2 + 1, n2 - y2 + 1)
    lo, hi = max(0.0, d), min(1.0, 1.0 + d)
    if hi <= lo:
        return 0.0
    return integrate.quad(lambda t: b1.pdf(t) * b2.pdf(t - d), lo, hi, limit=200)[0]


# =========================================================================== 5.3 frequentist risk
def risk_mle(theta, n, sigma2=1.0):
    return np.full_like(np.asarray(theta, float), sigma2 / n)


@functools.lru_cache(maxsize=None)
def median_var_exact(n):
    """Exact variance of the sample median of n standard normal draws (numerical integration)."""
    if n % 2 == 1:
        k = (n + 1) // 2
        c = special.factorial(n) / (special.factorial(k - 1) * special.factorial(n - k))
        f = lambda x: x * x * c * Phi_(x) ** (k - 1) * (1 - Phi_(x)) ** (n - k) * stats.norm.pdf(x)
        return integrate.quad(f, -12, 12, limit=200)[0]
    k = n // 2
    lc = special.gammaln(n + 1) - special.gammaln(k) - special.gammaln(n - k)
    # E[((X_(k) + X_(k+1))/2)^2] over a < b, by tensor Gauss-Legendre quadrature on b = a + (8 - a) s
    z, w = np.polynomial.legendre.leggauss(400)
    a = 8.0 * z - 0.0
    wa = 8.0 * w                                        # a in [-8, 8]
    s_ = 0.5 * (z + 1)
    ws = 0.5 * w
    A = a[:, None]
    B = A + (8.0 - A) * s_[None, :]
    jac = (8.0 - A) * ws[None, :] * wa[:, None]
    PA, PB = Phi_(A), Phi_(B)
    logd = lc + (k - 1) * np.log(PA) + stats.norm.logpdf(A) + stats.norm.logpdf(B) + (n - k - 1) * np.log1p(-np.minimum(PB, 1 - 1e-300))
    return float(np.sum(((A + B) / 2) ** 2 * np.exp(logd) * jac))


def risk_median(theta, n, exact=True):
    v = median_var_exact(n) if exact else math.pi / (2 * n)
    return np.full_like(np.asarray(theta, float), v)


def risk_fixed(theta, theta0=0.0):
    return (np.asarray(theta, float) - theta0) ** 2


def risk_postmean(theta, n, kappa, theta0=0.0, sigma2=1.0):
    """(5.73)."""
    return (n * sigma2 + kappa ** 2 * (theta0 - np.asarray(theta, float)) ** 2) / (n + kappa) ** 2


def bayes_risk_postmean(n, kappa, sigma2=1.0):
    """Bayes risk of delta_kappa under its own prior N(theta0, sigma2/kappa): 1/(n + kappa) when sigma2 = 1."""
    return sigma2 / (n + kappa)


def js_risk(theta_norm2, d):
    """Exact risk E||delta_JS(X) - theta||^2 of the James-Stein estimator (1 - (d-2)/||X||^2) X for
    X ~ N(theta, I_d): d - (d-2)^2 E[1/||X||^2], with ||X||^2 noncentral chi-square(d, lambda = ||theta||^2)
    and E[1/||X||^2] = sum_k Pois(k; lambda/2) / (d + 2k - 2)."""
    lam = np.atleast_1d(np.asarray(theta_norm2, float))
    if d <= 2:                                  # the estimator is not defined for d < 3; for d = 2 the gain is 0
        return np.full_like(lam, float(d))
    k = np.arange(0, 400)
    out = []
    for l in lam:
        w = stats.poisson.pmf(k, l / 2.0)
        out.append(d - (d - 2) ** 2 * float(np.sum(w / (d + 2 * k - 2))))
    return np.array(out)


def js_estimate(x):
    d = x.shape[-1]
    return (1 - (d - 2) / np.sum(x ** 2, axis=-1, keepdims=True)) * x


# =========================================================================== 5.4 ERM and learning theory
def hoeffding_bound(n, eps, size=1):
    """(5.93): 2 |H| exp(-2 n eps^2)."""
    return 2 * size * np.exp(-2 * np.asarray(n, float) * eps ** 2)


def hoeffding_sample_size(eps, delta, size=1):
    """Smallest N with 2|H| exp(-2 N eps^2) <= delta."""
    return math.ceil(math.log(2 * size / delta) / (2 * eps ** 2))


# =========================================================================== 5.5 hypothesis testing
def np_threshold(mu0, sigma, n, alpha):
    """x* = mu0 + z_alpha sigma / sqrt(n) (below (5.103))."""
    return mu0 + stats.norm.isf(alpha) * sigma / math.sqrt(n)


def power_one_sided(mu0, mu1, sigma, n, alpha):
    return float(stats.norm.sf((np_threshold(mu0, sigma, n, alpha) - mu1) * math.sqrt(n) / sigma))


def power_two_sided(mu, sigma, n, alpha):
    z = stats.norm.isf(alpha / 2)
    s = np.sqrt(n) * np.asarray(mu, float) / sigma
    return Phi_(-z + s) + Phi_(-z - s)


def p_value_wald(theta_hat, theta0, se):
    """Two-sided Wald p-value 2 Phi(-|z|) (Section 5.5.3)."""
    return float(2 * Phi_(-abs((theta_hat - theta0) / se)))


def permutation_pvalue(x, y, n_perm=20000, seed=0):
    """Permutation test for equality of two distributions with statistic |mean(x) - mean(y)|."""
    rng = np.random.default_rng(seed)
    z = np.r_[x, y]
    m = len(x)
    obs = abs(np.mean(x) - np.mean(y))
    cnt = 0
    for _ in range(n_perm):
        p = rng.permutation(z)
        cnt += abs(p[:m].mean() - p[m:].mean()) >= obs
    return (cnt + 1) / (n_perm + 1)


def p_h0_given_significant(alpha, beta, prior_h0):
    """(5.108)-(5.110)."""
    return alpha * prior_h0 / (alpha * prior_h0 + (1 - beta) * (1 - prior_h0))


def sbb_lower_bound(p, prior_h0=0.5):
    """Sellke, Bayarri and Berger (2001): for p < 1/e, the Bayes factor of H0 against any alternative of the
    form 'p-value density decreasing in p' is at least -e p ln p; hence p(H0|D) >= (1 + 1/(-e p ln p))^{-1}
    for equal prior odds (here with general prior odds)."""
    p = np.asarray(p, float)
    bf = -math.e * p * np.log(p)
    po = prior_h0 / (1 - prior_h0) * bf
    return po / (1 + po)


def coin_pvalue(n1, n):
    """Exact two-sided binomial p-value for a fair coin."""
    return float(stats.binomtest(int(n1), int(n), 0.5).pvalue)


def coin_bf01(n1, n, a=1.0):
    """Bayes factor p(D|M0)/p(D|M1) for n1 heads in n tosses with a Beta(a, a) prior under M1."""
    return math.exp(coin_logml0(n1, n - n1) - coin_logml(n1, n - n1, a, a))


# =========================================================================== exercises
def newsvendor_expected_profit(Q, P, C, mu, sigma):
    """Exercise 5.2: expected profit (5.112) when the demand D is N(mu, sigma^2), by numerical integration."""
    Q = float(Q)
    f = stats.norm(mu, sigma).pdf
    t1 = (P - C) * Q * stats.norm(mu, sigma).sf(Q)
    t2 = integrate.quad(lambda D: (P - C) * D * f(D), 0, Q)[0]
    t3 = integrate.quad(lambda D: C * (Q - D) * f(D), 0, Q)[0]
    return t1 + t2 - t3


def newsvendor_Q(P, C, mu, sigma):
    """Exercise 5.2: the optimal order quantity F(Q*) = (P - C)/P (5.113) for normal demand."""
    return float(stats.norm(mu, sigma).ppf((P - C) / P))


def loo_press_residuals(X, y, lam=0.0):
    """Leave-one-out residuals of ridge regression without refitting: e_i / (1 - H_ii), H = X (X'X + lam I)^-1 X'.
    (Section 5.4.3: the leave-one-out score of a linear smoother is available in closed form.)"""
    A = X.T @ X + lam * np.eye(X.shape[1])
    Hd = np.einsum("ij,ij->i", X @ np.linalg.inv(A), X)
    resid = y - X @ np.linalg.solve(A, X.T @ y)
    return resid / (1 - Hd)


# =========================================================================== figures
def fig_5_1(out=None):
    """Figure 5.1: the reject region where the class posteriors are uncertain."""
    x = np.linspace(-3.5, 5.5, 600)
    p1 = stats.norm.pdf(x, 0, 1)
    p2 = stats.norm.pdf(x, 2, 1)
    post1 = p1 / (p1 + p2)
    post2 = 1 - post1
    lam = 1 - 0.2                                    # lambda* = 1 - lambda_r / lambda_e with lambda_r / lambda_e = 0.2
    rej = np.maximum(post1, post2) < lam
    fig, ax = plt.subplots(figsize=(5.4, 3.1))
    ax.fill_between(x, 0, 1, where=rej, color="#cfd8e6", alpha=0.8, lw=0, label="reject region")
    ax.plot(x, post1, color=RED, label=r"$p(y=1\mid x)$")
    ax.plot(x, post2, color=BLUE, label=r"$p(y=2\mid x)$")
    ax.axhline(lam, color="k", ls="--", lw=1)
    ax.text(5.4, lam + 0.015, r"threshold $\lambda^*=0.8$", ha="right", fontsize=9)
    ax.set_xlabel("$x$")
    ax.set_ylabel("class posterior")
    ax.set_ylim(0, 1.05)
    ax.legend(loc="center right", frameon=False)
    fig.tight_layout()
    savefig(fig, CH, "fig5-1", out)


def systems_AB(seed=3):
    rng = np.random.default_rng(seed)
    sA, y = binormal_scores(300, 700, 2.4, rng)
    sB, _ = binormal_scores(300, 700, 1.4, np.random.default_rng(seed + 1))
    return (sA, y), (sB, y)


def fig_5_2(out=None):
    """Figure 5.2: ROC and precision-recall curves of two hypothetical classifiers."""
    (sA, y), (sB, _) = systems_AB()
    fig, axes = panel_grid(1, 2, size=(3.3, 3.2))
    ax = axes[0, 0]
    for s, col, lab in ((sA, RED, "A"), (sB, BLUE, "B")):
        f, t, _ = roc_points(s, y)
        ax.plot(f, t, color=col)
        e = eer(f, t)
        ax.plot([e], [1 - e], "o", color=col, ms=5)
        if lab == "B":
            ax.fill_between(f, 0, t, color=col, alpha=0.12, lw=0)
    ax.plot([0, 1], [1, 0], color=GREY, lw=0.6, ls=":")
    ax.text(0.5, 0.78, "A", color=RED, fontsize=11)
    ax.text(0.5, 0.55, "B", color=BLUE, fontsize=11)
    ax.set_xlabel("FPR")
    ax.set_ylabel("TPR")
    ax.set_xlim(0, 1)
    ax.set_ylim(0, 1.02)
    panel_label(ax, "a", "lower right")
    ax = axes[0, 1]
    for s, col in ((sA, RED), (sB, BLUE)):
        r, p = pr_points(s, y)
        ax.plot(r, p, color=col)
    ax.set_xlabel("recall")
    ax.set_ylabel("precision")
    ax.set_xlim(0, 1)
    ax.set_ylim(0, 1.02)
    panel_label(ax, "b", "lower left")
    fig.tight_layout()
    savefig(fig, CH, "fig5-2", out)


def fig_5_3(out=None):
    """Figure 5.3: squared, absolute and Huber loss (delta = 1.5)."""
    r = np.linspace(-3, 3, 400)
    fig, ax = plt.subplots(figsize=(4.6, 3.0))
    ax.plot(r, l2(r, 0), color=BLUE, label=r"$\ell_2$")
    ax.plot(r, l1(r, 0), color=RED, ls="--", label=r"$\ell_1$")
    ax.plot(r, huber(r, 0, 1.5), color=GREEN, ls="-.", label=r"Huber, $\delta=1.5$")
    ax.set_ylim(-0.3, 5)
    ax.set_xlabel(r"$r=h-a$")
    ax.set_ylabel("loss")
    ax.legend(frameon=False)
    fig.tight_layout()
    savefig(fig, CH, "fig5-3", out)


def fig_5_4(out=None):
    """Figure 5.4: log marginal likelihood of each of the 32 sequences of five tosses, and its BIC approximation."""
    n = 5
    seqs = sorted(range(2 ** n), key=lambda s: (bin(s).count("1"), s))
    n1s = np.array([bin(s).count("1") for s in seqs])
    fig, axes = panel_grid(1, 2, size=(3.7, 2.8))
    lm = np.array([coin_logml(k, n - k) for k in n1s]) / math.log(10)
    bi = np.array([coin_bic_logml(k, n - k) for k in n1s]) / math.log(10)
    for ax, v, lab in ((axes[0, 0], lm, r"$\log_{10}\,p(D\mid M_1)$"), (axes[0, 1], bi, "BIC approx. to $\\log_{10}\\,p(D\\mid M_1)$")):
        ax.bar(np.arange(32), v - v.min() + 0.0, bottom=v.min(), color=BLUE, width=0.8)
        ax.axhline(n * math.log10(0.5), color=RED, ls="--", lw=1)
        ax.set_xticks(np.arange(32))
        ax.set_xticklabels([str(k) for k in n1s], fontsize=5)
        ax.set_ylabel(lab)
        ax.set_xlabel("number of heads in the sequence")
    ymin = min(lm.min(), bi.min()) - 0.1
    for ax in axes[0]:
        ax.set_ylim(ymin, 0.05)
    axes[0, 0].text(16, n * math.log10(0.5) + 0.05, r"$\log_{10}p(D\mid M_0)$", color=RED, ha="center", fontsize=8)
    panel_label(axes[0, 0], "a", "upper center")
    panel_label(axes[0, 1], "b", "upper center")
    fig.tight_layout()
    savefig(fig, CH, "fig5-4", out)


def _poly_figure(n, seed, name):
    x, y = poly_data(n, seed)
    logev, post, fits = poly_model_posterior(x, y)
    fig, axes = panel_grid(2, 2, size=(3.3, 2.6))
    xs = np.linspace(-2, 12, 300)
    for i, d in enumerate((1, 2, 3)):
        ax = axes[i // 2, i % 2]
        a, b = fits[i]
        Phi = poly_design(x, d)
        m, S = poly_posterior(y, Phi, a, b)
        Px = poly_design(xs, d)
        mean = Px @ m
        sd = np.sqrt(1.0 / b + np.einsum("ij,jk,ik->i", Px, S, Px))
        ax.plot(xs, poly_true(xs), color=GREEN, lw=1.4)
        ax.plot(xs, mean, color=RED, ls="--")
        ax.plot(xs, mean + 2 * sd, color=BLUE, ls=":", lw=1)
        ax.plot(xs, mean - 2 * sd, color=BLUE, ls=":", lw=1)
        ax.plot(x, y, "ko", ms=3.5)
        lo, hi = min(y.min(), (mean - 2 * sd)[(xs > -1) & (xs < 11)].min()), max(y.max(), (mean + 2 * sd)[(xs > -1) & (xs < 11)].max())
        ax.set_ylim(lo - 0.05 * (hi - lo), hi + 0.05 * (hi - lo))
        ax.set_title("deg=%d | logev=%.2f" % (d, logev[i]), fontsize=9)
        panel_label(ax, "abc"[i], "upper left")
    ax = axes[1, 1]
    ax.bar([1, 2, 3], post, color=BLUE, width=0.6)
    ax.set_xticks([1, 2, 3])
    ax.set_xlabel("$M$ (degree)")
    ax.set_ylabel("$p(M|D)$")
    ax.set_ylim(0, 1.05)
    panel_label(ax, "d", "upper right")
    fig.tight_layout()
    return fig, logev, post


POLY_SEED = {5: 0, 30: 0}


def fig_5_5(out=None):
    """Figure 5.5: Bayesian model selection for polynomial regression, N = 5 (synthetic data, see the notes)."""
    fig, _, _ = _poly_figure(5, POLY_SEED[5], "fig5-5")
    savefig(fig, CH, "fig5-5", out)


def fig_5_6(out=None):
    """Figure 5.6: the same with N = 30."""
    fig, _, _ = _poly_figure(30, POLY_SEED[30], "fig5-6")
    savefig(fig, CH, "fig5-6", out)


def fig_5_7(out=None):
    """Figure 5.7: the Bayesian Occam's razor, as the marginal density of the data under three models."""
    n = 10
    xb = np.linspace(-4, 4, 800)
    fig, ax = plt.subplots(figsize=(5.2, 3.0))
    for tau, col, lab in ((0.1, BLUE, r"$M_1$: $\tau=0.1$"), (1.0, RED, r"$M_2$: $\tau=1$"), (10.0, GREEN, r"$M_3$: $\tau=10$")):
        ax.plot(xb, gauss_evidence_density(xb, tau, n), color=col, label=lab)
    ax.axvline(0.9, color="k", ls="--", lw=1)
    ax.text(0.95, 1.05, r"$D_0$", fontsize=10)
    ax.set_xlabel(r"data sets, indexed by the sample mean $\bar x$ ($n=%d$)" % n)
    ax.set_ylabel(r"$p(D\mid M)$")
    ax.set_ylim(0, 1.35)
    ax.legend(frameon=False, loc="upper left", fontsize=8)
    fig.tight_layout()
    savefig(fig, CH, "fig5-7", out)


def fig_5_8(out=None):
    """Figure 5.8: risk functions of five estimators of a Gaussian mean, N = 5 and N = 20."""
    th = np.linspace(-2, 2, 401)
    fig, axes = panel_grid(1, 2, size=(3.6, 3.0))
    for j, n in enumerate((5, 20)):
        ax = axes[0, j]
        ax.plot(th, risk_mle(th, n), color="#14337a", label="mle")
        ax.plot(th, risk_median(th, n), color=RED, ls="--", label="median")
        ax.plot(th, risk_fixed(th), color="k", label="fixed")
        ax.plot(th, risk_postmean(th, n, 1), color=GREEN, label="postmean1")
        ax.plot(th, risk_postmean(th, n, 5), color=CYAN_(), label="postmean5")
        ax.set_xlabel(r"$\theta^*$")
        ax.set_ylabel(r"$R(\theta^*,\delta)$")
        ax.set_ylim(0, 0.5 if n == 5 else 0.18)
        ax.set_title("risk functions for N=%d" % n, fontsize=9)
        panel_label(ax, "ab"[j], "upper center")
        if j == 0:
            ax.legend(frameon=False, fontsize=7, loc="upper right", bbox_to_anchor=(1.0, 0.97))
    fig.tight_layout()
    savefig(fig, CH, "fig5-8", out)


def CYAN_():
    return "#4fb3d9"


def fig_5_9(out=None):
    """Figure 5.9: a minimax estimator (the sample mean) against an estimator better in the middle."""
    th = np.linspace(-3, 3, 400)
    n = 5
    fig, ax = plt.subplots(figsize=(4.6, 3.0))
    r1, r2 = risk_mle(th, n), risk_postmean(th, n, 1)
    ax.plot(th, r1, color=RED, label=r"$\delta_1$: sample mean")
    ax.plot(th, r2, color=BLUE, ls="--", label=r"$\delta_2$: posterior mean, $\kappa=1$")
    ax.fill_between(th, r2, r1, where=r2 < r1, color=BLUE, alpha=0.12, lw=0)
    ax.axhline(r1.max(), color=RED, lw=0.6, ls=":")
    ax.text(-2.95, r1.max() + 0.012, r"$R_{\max}(\delta_1)$", fontsize=8, color=RED)
    ax.text(2.95, r2.max() + 0.012, r"$R_{\max}(\delta_2)$ (on $[-3,3]$)", fontsize=8, color=BLUE, ha="right")
    ax.set_xlabel(r"$\theta$")
    ax.set_ylabel(r"$R(\theta,\delta)$")
    ax.set_ylim(0, 0.45)
    ax.legend(frameon=False, fontsize=8, loc="upper center")
    fig.tight_layout()
    savefig(fig, CH, "fig5-9", out)


def fig_5_10(out=None):
    """Figure 5.10: (a) the Neyman-Pearson picture for two Gaussian means, (b) two power curves."""
    fig, axes = panel_grid(1, 2, size=(3.7, 2.9))
    ax = axes[0, 0]
    mu0, mu1, se, alpha = 0.0, 2.0, 1.0, 0.05
    xs = np.linspace(-3.5, 5.5, 600)
    xstar = np_threshold(mu0, se, 1, alpha)
    ax.plot(xs, stats.norm.pdf(xs, mu0, se), color=BLUE)
    ax.plot(xs, stats.norm.pdf(xs, mu1, se), color=RED)
    ax.fill_between(xs, 0, stats.norm.pdf(xs, mu0, se), where=xs >= xstar, color=BLUE, alpha=0.35, lw=0)
    ax.fill_between(xs, 0, stats.norm.pdf(xs, mu1, se), where=xs <= xstar, color=RED, alpha=0.25, lw=0)
    ax.axvline(xstar, color="k", ls="--", lw=1)
    ax.text(xstar + 0.1, 0.43, r"$x^*$", fontsize=10)
    ax.text(-2.8, 0.37, r"$H_0$", color=BLUE)
    ax.text(3.7, 0.37, r"$H_1$", color=RED)
    ax.text(2.2, 0.07, r"$\alpha$", color=BLUE, fontsize=9)
    ax.text(0.75, 0.045, r"$\beta$", color=RED, fontsize=9)
    ax.set_xlabel(r"$\bar x$")
    ax.set_ylabel("density")
    panel_label(ax, "a", "upper right")
    ax = axes[0, 1]
    mu = np.linspace(-1.2, 1.2, 400)
    ax.plot(mu, power_two_sided(mu, 1.0, 10, 0.05), color=RED, label="A: $N=10$")
    ax.plot(mu, power_two_sided(mu, 1.0, 40, 0.05), color=BLUE, label="B: $N=40$")
    ax.axhline(0.05, color=GREY, lw=0.6, ls=":")
    ax.set_xlabel(r"true mean $\mu$")
    ax.set_ylabel("power")
    ax.legend(frameon=False, fontsize=8, loc="lower right")
    ax.set_ylim(0, 1.02)
    panel_label(ax, "b", "upper left")
    fig.tight_layout()
    savefig(fig, CH, "fig5-10", out)


def fig_5_S1(out=None):
    """Supplementary: ROC (unchanged) and PR curves of one classifier at prevalences 50%, 10%, 1%."""
    d = 2.0
    x = np.linspace(-5, 8, 4000)
    fpr, tpr = binormal_roc(d, x)
    fig, axes = panel_grid(1, 3, size=(3.0, 3.0))
    axes[0, 0].plot(fpr, tpr, color=BLUE)
    axes[0, 0].set_xlabel("FPR")
    axes[0, 0].set_ylabel("TPR")
    axes[0, 0].set_title("ROC (any prevalence)", fontsize=9)
    cols = (BLUE, GREEN, RED)
    for pi, col in zip((0.5, 0.1, 0.01), cols):
        r = pi / (1 - pi)
        prec = precision_at_prevalence(tpr[1:], fpr[1:], r)
        axes[0, 1].plot(tpr[1:], prec, color=col, label="prevalence %g" % pi)
        f1 = fbeta_from_rates(tpr, fpr, r)
        axes[0, 2].plot(x, f1, color=col)
    axes[0, 1].set_xlabel("recall")
    axes[0, 1].set_ylabel("precision")
    axes[0, 1].legend(frameon=False, fontsize=8)
    axes[0, 1].set_title("PR curves", fontsize=9)
    axes[0, 2].set_xlabel("score threshold")
    axes[0, 2].set_ylabel("$F_1$")
    axes[0, 2].set_title("$F_1$ against threshold", fontsize=9)
    for ax in axes[0]:
        ax.set_ylim(0, 1.02)
    fig.tight_layout()
    savefig(fig, CH, "fig5-S1", out)


def fig_5_S2(out=None):
    """Supplementary: posterior of the difference in left-handedness rates (Table 5.7)."""
    y1, n1, y2, n2 = 9, 52, 4, 48
    ds = np.linspace(-0.15, 0.5, 261)
    dens = np.array([delta_density(d, y1, n1, y2, n2) for d in ds])
    p = prob_theta1_gt_theta2(y1, n1, y2, n2)
    fig, ax = plt.subplots(figsize=(4.8, 3.0))
    ax.plot(ds, dens, color=BLUE)
    ax.fill_between(ds, 0, dens, where=ds > 0, color=BLUE, alpha=0.2, lw=0)
    ax.axvspan(-0.01, 0.01, color=GREY, alpha=0.25, lw=0)
    ax.text(0.3, dens.max() * 0.6, r"$p(\Delta>0\mid D)=%.3f$" % p, fontsize=9)
    ax.set_xlabel(r"$\Delta=\theta_1-\theta_2$")
    ax.set_ylabel(r"$p(\Delta\mid D)$")
    fig.tight_layout()
    savefig(fig, CH, "fig5-S2", out)


def fig_5_S3(out=None):
    """Supplementary: risk of the James-Stein estimator against the sample mean (risk d)."""
    t2 = np.linspace(0, 60, 300)
    fig, ax = plt.subplots(figsize=(4.8, 3.0))
    for d, col in ((3, BLUE), (5, GREEN), (10, RED)):
        ax.plot(np.sqrt(t2), js_risk(t2, d) / d, color=col, label="$d=%d$" % d)
    ax.axhline(1, color="k", ls="--", lw=1)
    ax.set_xlabel(r"$\|\theta\|$")
    ax.set_ylabel(r"risk / $d$")
    ax.text(7.5, 1.02, "sample mean", fontsize=8, ha="right")
    ax.set_ylim(0, 1.15)
    ax.legend(frameon=False, fontsize=8, loc="lower right")
    fig.tight_layout()
    savefig(fig, CH, "fig5-S3", out)


def fig_5_S4(out=None):
    """Supplementary: the union-bound guarantee (5.93) against simulation (|H| independent hypotheses)."""
    rng = np.random.default_rng(5)
    eps, H, p = 0.1, 20, 0.3
    ns = np.array([20, 40, 80, 120, 160, 200, 240, 280])
    sim = []
    for n in ns:
        e = rng.binomial(n, p, size=(40000, H)) / n
        sim.append(np.mean(np.max(np.abs(e - p), axis=1) > eps))
    fig, ax = plt.subplots(figsize=(4.8, 3.0))
    ax.semilogy(ns, np.minimum(hoeffding_bound(ns, eps, H), 1), color=RED, label=r"bound $2|H|e^{-2N\epsilon^2}$")
    ax.semilogy(ns, sim, "o-", color=BLUE, label="simulated probability")
    ax.set_xlabel("$N$")
    ax.set_ylabel("probability of a deviation $>\\epsilon$")
    ax.set_ylim(1e-4, 1.5)
    ax.legend(frameon=False, fontsize=8)
    fig.tight_layout()
    savefig(fig, CH, "fig5-S4", out)


def fig_5_S5(out=None):
    """Supplementary: p-values against posterior probabilities of the null."""
    fig, axes = panel_grid(1, 3, size=(3.1, 3.0))
    p = np.linspace(0.001, 0.3, 300)
    ax = axes[0, 0]
    ax.plot(p, sbb_lower_bound(p), color=RED, label="lower bound")
    ax.plot(p, p, color=GREY, ls="--", label="$p$-value")
    ax.set_xlabel("$p$-value")
    ax.set_ylabel(r"$p(H_0\mid D)$")
    ax.legend(frameon=False, fontsize=8)
    ax.set_title("equal prior odds", fontsize=9)
    ax = axes[0, 1]
    pr = np.linspace(0.01, 0.99, 200)
    ax.plot(pr, p_h0_given_significant(0.05, 0.2, pr), color=BLUE)
    ax.axvline(0.9, color=GREY, ls=":", lw=1)
    ax.plot([0.9], [p_h0_given_significant(0.05, 0.2, 0.9)], "o", color=BLUE)
    ax.set_xlabel(r"prior $p(H_0)$")
    ax.set_ylabel(r"$p(H_0\mid\mathrm{significant})$")
    ax.set_title(r"$\alpha=0.05$, $\beta=0.2$", fontsize=9)
    ax = axes[0, 2]
    ns = np.unique(np.round(np.logspace(1.2, 6, 60)).astype(int))
    z = 1.96
    bf = []
    for n in ns:
        n1 = n / 2 + z * math.sqrt(n) / 2
        lm0 = n * math.log(0.5)
        lm1 = special.gammaln(n + 2) * 0 + (special.betaln(n1 + 1, n - n1 + 1))      # continuous n1 is fine for the picture
        bf.append(math.exp(lm0 - lm1))
    ax.loglog(ns, bf, color=PURPLE)
    ax.axhline(1, color=GREY, ls="--", lw=1)
    ax.set_xlabel("$N$ (at fixed $z=1.96$, $p\\approx0.05$)")
    ax.set_ylabel(r"$B_{0,1}=p(D|M_0)/p(D|M_1)$")
    ax.set_title("Lindley paradox", fontsize=9)
    fig.tight_layout()
    savefig(fig, CH, "fig5-S5", out)


FIGURES = {"5.1": fig_5_1, "5.2": fig_5_2, "5.3": fig_5_3, "5.4": fig_5_4, "5.5": fig_5_5, "5.6": fig_5_6,
           "5.7": fig_5_7, "5.8": fig_5_8, "5.9": fig_5_9, "5.10": fig_5_10,
           "5.S1": fig_5_S1, "5.S2": fig_5_S2, "5.S3": fig_5_S3, "5.S4": fig_5_S4, "5.S5": fig_5_S5}


# =========================================================================== demo data
def breast_cancer_scores():
    """Held-out predicted probabilities of 'malignant' from a logistic regression on the standardised
    scikit-learn breast-cancer data (569 patients, 30 features; 1/3 held out)."""
    from sklearn.datasets import load_breast_cancer
    from sklearn.linear_model import LogisticRegression
    from sklearn.model_selection import train_test_split
    from sklearn.preprocessing import StandardScaler
    X, t = load_breast_cancer(return_X_y=True)
    y = 1 - t                                           # 1 = malignant
    Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=1 / 3, random_state=0, stratify=y)
    sc = StandardScaler().fit(Xtr)
    m = LogisticRegression(C=0.1, max_iter=5000).fit(sc.transform(Xtr), ytr)
    return m.predict_proba(sc.transform(Xte))[:, 1], yte


def export_json():
    os.makedirs(DATA_OUT, exist_ok=True)
    p, y = breast_cancer_scores()
    f, t, _ = roc_points(p, y)
    d = dict(p=[round(float(v), 5) for v in p], y=[int(v) for v in y], auc=auc_rank(p, y),
             n_pos=int(y.sum()), n_neg=int((1 - y).sum()), ap=average_precision(p, y))
    path = os.path.join(DATA_OUT, "ch05-bcancer.json")
    with open(path, "w") as fh:
        json.dump(d, fh, separators=(",", ":"))
    print("wrote", os.path.relpath(path, os.getcwd()))
    ref = dict(
        covid=[[int(r[0]), int(r[1]), float(r[2]), float(r[3]), float(r[4]), int(r[5])] for r in covid_policy()],
        coin=dict(n=10, n1=8, bf01=coin_bf01(8, 10), p=coin_pvalue(8, 10)),
        lindley=dict(n=10000, n1=5100, bf01=coin_bf01(5100, 10000), p=coin_pvalue(5100, 10000)),
        trials=dict(h0=p_h0_given_significant(0.05, 0.2, 0.9)),
        js=dict(d=5, theta2=4.0, risk=float(js_risk(4.0, 5)[0])),
        risk=dict(n=5, median=median_var_exact(5), n20=median_var_exact(20)))
    medv = {str(n): median_var_exact(n) for n in range(2, 61)}
    with open(os.path.join(DATA_OUT, "ch05-median-var.json"), "w") as fh:
        json.dump(medv, fh, separators=(",", ":"))
    print("wrote ch05-median-var.json")
    path = os.path.join(DATA_OUT, "ch05-reference.json")
    with open(path, "w") as fh:
        json.dump(ref, fh, indent=1)
    print("wrote", os.path.relpath(path, os.getcwd()))


if __name__ == "__main__":
    import sys
    if "--json" in sys.argv:
        export_json()
    else:
        common.run(FIGURES, CH)
        if "--fig" not in sys.argv and "--list" not in sys.argv:
            export_json()
