"""Murphy (2023), Chapter 14: Predictive models: an overview.

Companion code for Chapter 14 of K. P. Murphy, Probabilistic Machine Learning: Advanced Topics
(MIT Press, 2023; December 2025 draft), pp. 575-590, written from scratch with numpy, scipy and
matplotlib (scikit-learn is used only to build features and to confirm my isotonic regression
and quantile regression), to be read next to the lecture notes (../ch14-predictive-models-overview.html).

Methods
* Section 14.2.1 proper scoring rules: log score and Brier score (log_score, brier_score).
* Section 14.2.2 calibration: reliability bins and the expected calibration error (reliability,
  ece), temperature scaling (fit_temperature), Platt scaling (fit_platt), histogram binning
  (hist_binning), isotonic regression by pool adjacent violators (isotonic_pav), the
  scaling-binning calibrator (scaling_binning). Figures 14.1 (stand-in), 14.2 and 14.3.
* Section 14.3 conformal prediction: split conformal quantile (conformal_quantile) with the
  finite-sample correction, quantile (pinball) loss, conformalised quantile regression, and the
  exact distribution of the coverage over calibration sets. Figures 14.5b, 14.5c and an own figure.

Skipped figures, with reasons: Figure 14.1 in the book uses a ResNet trained on CIFAR-100 (a
GPU-scale model); I reproduce its message with synthetic over-confident scores (right ranking,
logits three times too large), and say so in the caption. Figure 14.4 and 14.5a (ImageNet prediction sets) need a
large pretrained network and are skipped.

Data: simulated (seeds fixed in the code).
"""
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, GREEN, GREY, ORANGE, PURPLE, RED, plt, savefig, run, sigmoid  # noqa: E402

CH = 14


# ------------------------------------------------------------------ scoring rules
def log_score(p, y):
    """Mean log score of categorical predictions p (n x C) for integer labels y."""
    return float(np.mean(np.log(p[np.arange(len(y)), y])))


def brier_score(p, y):
    """Negative Brier score (larger is better), -mean_n sum_c (p_nc - 1[y_n=c])^2, as in Murphy's convention."""
    Y = np.eye(p.shape[1])[y]
    return float(-np.mean(np.sum((p - Y) ** 2, axis=1)))


# ------------------------------------------------------------------ calibration
def reliability(conf, correct, n_bins=10):
    """Uniform-width bins on the confidence; returns (centres, accuracy, confidence, counts)."""
    edges = np.linspace(0, 1, n_bins + 1)
    idx = np.clip(np.digitize(conf, edges[1:-1], right=True), 0, n_bins - 1)
    acc = np.full(n_bins, np.nan); cf = np.full(n_bins, np.nan); cnt = np.zeros(n_bins, int)
    for b in range(n_bins):
        m = idx == b
        cnt[b] = m.sum()
        if cnt[b]:
            acc[b] = correct[m].mean(); cf[b] = conf[m].mean()
    return 0.5 * (edges[:-1] + edges[1:]), acc, cf, cnt


def ece(conf, correct, n_bins=10):
    """Expected calibration error: sum_b |B_b|/n * |acc(B_b) - conf(B_b)|."""
    _, acc, cf, cnt = reliability(conf, correct, n_bins)
    m = cnt > 0
    return float(np.sum(cnt[m] / cnt.sum() * np.abs(acc[m] - cf[m])))


def softmax(z, T=1.0):
    return special.softmax(np.asarray(z, float) / T, axis=-1)


def fit_temperature(logits, y):
    """Temperature scaling q = softmax(z/T): T minimises the validation NLL (1-d convex problem in 1/T)."""
    def nll(logT):
        ls = special.log_softmax(np.asarray(logits, float) / np.exp(logT), axis=1)
        return -float(np.mean(ls[np.arange(len(y)), y]))
    r = optimize.minimize_scalar(nll, bounds=(-3, 4), method="bounded", options={"xatol": 1e-8})
    return float(np.exp(r.x))


def fit_platt(z, y):
    """Platt scaling q = sigma(a z + b) for binary logits z, by damped Newton's method (logistic regression on z)."""
    X = np.c_[z, np.ones_like(z)]

    def nll(w):
        a = X @ w
        return float(np.sum(np.logaddexp(0, a) - y * a))
    w = np.array([1.0, 0.0])
    for _ in range(100):
        p = sigmoid(X @ w)
        g = X.T @ (p - y)
        H = (X * (p * (1 - p))[:, None]).T @ X + 1e-10 * np.eye(2)
        step = np.linalg.solve(H, g)
        t = 1.0
        while nll(w - t * step) > nll(w) + 1e-12 and t > 1e-8:     # step halving keeps Newton monotone
            t *= 0.5
        w = w - t * step
        if np.max(np.abs(t * step)) < 1e-11:
            break
    return w


def hist_binning(p, y, n_bins):
    """Histogram binning: replace p by the label average in its bin (equal-width bins on [0,1]).
    Returns a function."""
    edges = np.linspace(0, 1, n_bins + 1)
    idx = np.clip(np.digitize(p, edges[1:-1], right=True), 0, n_bins - 1)
    q = np.array([y[idx == b].mean() if np.any(idx == b) else 0.5 * (edges[b] + edges[b + 1]) for b in range(n_bins)])

    def f(pnew):
        i = np.clip(np.digitize(pnew, edges[1:-1], right=True), 0, n_bins - 1)
        return q[i]
    return f


def isotonic_pav(x, y):
    """Isotonic regression (non-decreasing) of y on x by pool adjacent violators.
    Returns the fitted values in the original order of x."""
    order = np.argsort(x, kind="stable")
    ys = y[order].astype(float)
    vals, wts = [], []
    for v in ys:
        vals.append(v); wts.append(1.0)
        while len(vals) > 1 and vals[-2] > vals[-1]:
            w = wts[-2] + wts[-1]
            v2 = (vals[-2] * wts[-2] + vals[-1] * wts[-1]) / w
            vals[-2:] = [v2]; wts[-2:] = [w]
    fit_sorted = np.repeat(vals, np.array(wts, int))
    out = np.empty_like(fit_sorted)
    out[order] = fit_sorted
    return out


def scaling_binning(z_cal_scale, y_cal_scale, z_bin, n_bins, z_new):
    """Scaling-binning calibrator: Platt scaling fitted on one split, then bins whose output is the
    average of the *scaled probabilities* of a second split."""
    a, b = fit_platt(z_cal_scale, y_cal_scale)
    s_bin = sigmoid(a * z_bin + b)
    edges = np.linspace(0, 1, n_bins + 1)
    idx = np.clip(np.digitize(s_bin, edges[1:-1], right=True), 0, n_bins - 1)
    q = np.array([s_bin[idx == k].mean() if np.any(idx == k) else 0.5 * (edges[k] + edges[k + 1]) for k in range(n_bins)])
    s_new = sigmoid(a * z_new + b)
    return q[np.clip(np.digitize(s_new, edges[1:-1], right=True), 0, n_bins - 1)]


# ------------------------------------------------------------------ conformal prediction
def conformal_quantile(scores, alpha):
    """The ceil((n+1)(1-alpha))/n empirical quantile of the calibration scores (the k-th smallest,
    k = ceil((n+1)(1-alpha))); +inf if k > n."""
    n = len(scores)
    k = int(np.ceil((n + 1) * (1 - alpha)))
    if k > n:
        return np.inf
    return float(np.sort(scores)[k - 1])


def pinball(y, t, gamma):
    """Quantile (pinball) loss rho_gamma(y - t) = max(gamma (y-t), (gamma-1)(y-t))."""
    u = y - t
    return np.maximum(gamma * u, (gamma - 1) * u)


def coverage_pmf_params(n, alpha):
    """Coverage of split conformal given the calibration set is Beta(k, n+1-k), k = ceil((n+1)(1-alpha))."""
    k = int(np.ceil((n + 1) * (1 - alpha)))
    return k, n + 1 - k


# ------------------------------------------------------------------ data for the figures
def overconfident_scores(n, rng, n_classes=10, inflate=3.0):
    """Synthetic scores of an over-confident classifier: the true class logits ell are N(0, 1.5^2),
    the label is drawn from softmax(ell), and the model reports z = inflate * ell + noise, i.e. the
    right ranking with logits that are too large (as for a deep net trained to zero training loss)."""
    ell = 1.5 * rng.standard_normal((n, n_classes))
    p = special.softmax(ell, axis=1)
    y = np.array([rng.choice(n_classes, p=pi) for pi in p])
    z = inflate * ell + 0.5 * rng.standard_normal((n, n_classes))
    return z, y


def scores_split(seed=0):
    rng = np.random.default_rng(seed)
    return overconfident_scores(2000, rng), overconfident_scores(8000, rng)


# ------------------------------------------------------------------ figures
def fig_14_1(out=None):
    """Figure 14.1 (stand-in): reliability diagrams of over-confident synthetic scores and three recalibrations."""
    (zva, yva), (zte, yte) = scores_split()
    pte = softmax(zte)
    T = fit_temperature(zva, yva)
    conf_va, cor_va = softmax(zva).max(1), (zva.argmax(1) == yva)
    conf_te, cor_te = pte.max(1), (zte.argmax(1) == yte)
    # histogram binning and isotonic regression on the top-label confidence
    hb = hist_binning(conf_va, cor_va.astype(float), 10)
    iso_fit = isotonic_pav(conf_va, cor_va.astype(float))
    xs = np.sort(conf_va)
    iso_sorted = iso_fit[np.argsort(conf_va)]

    def iso(c):
        return np.interp(c, xs, iso_sorted)
    variants = [("uncalibrated", conf_te), ("temperature scaling (T = %.2f)" % T, softmax(zte, T).max(1)),
                ("histogram binning", hb(conf_te)), ("isotonic regression", iso(conf_te))]
    fig, ax = plt.subplots(1, 4, figsize=(12, 3.1), sharey=True)
    for a, (name, conf) in zip(ax, variants):
        c, acc, cf, cnt = reliability(conf, cor_te, 10)
        m = cnt > 0
        a.bar(c[m], acc[m], width=0.09, color=BLUE, alpha=0.8, label="accuracy")
        a.bar(c[m], (cf - acc)[m], bottom=acc[m], width=0.09, color=RED, alpha=0.35, label="gap")
        a.plot([0, 1], [0, 1], "k--", lw=0.9)
        a.set_title("%s\nECE = %.3f" % (name, ece(conf, cor_te)), fontsize=9)
        a.set_xlabel("confidence")
        a.set_xlim(0, 1); a.set_ylim(0, 1)
    ax[0].set_ylabel("accuracy"); ax[0].legend(fontsize=7, loc="upper left")
    fig.tight_layout()
    savefig(fig, CH, "fig14-1", out)


def binary_scores(seed=2, n=120):
    """Simulated 1-d logits for a binary problem: true logit slope 1, the model's logits are inflated by 3x."""
    rng = np.random.default_rng(seed)
    zt = rng.normal(0, 1.6, n)
    y = (rng.uniform(size=n) < sigmoid(zt)).astype(float)
    return 3.0 * zt, y, zt


def fig_14_2(out=None):
    """Figure 14.2: Platt scaling, histogram binning and the scaling-binning calibrator."""
    z, y, _ = binary_scores(n=80)
    zb, yb, _ = binary_scores(seed=5, n=400)
    zs = np.linspace(z.min(), z.max(), 400)
    a, b = fit_platt(z, y)
    ps = sigmoid(a * zs + b)
    fig, ax = plt.subplots(1, 3, figsize=(11, 2.9), sharey=True)
    for k, t in enumerate(["(a) Platt scaling", "(b) histogram binning, 3 bins", "(c) scaling-binning calibrator"]):
        ax[k].plot(z, y, "k+", ms=5)
        ax[k].set_title(t, fontsize=9.5); ax[k].set_xlabel("model logit")
    ax[0].plot(zs, ps, color=RED)
    pm = sigmoid(z)   # uncalibrated probabilities
    hb = hist_binning(sigmoid(zs), None, 3) if False else None
    # histogram binning in probability space on the uncalibrated sigmoid(z)
    f = hist_binning(sigmoid(z), y, 3)
    ax[1].step(zs, f(sigmoid(zs)), where="mid", color=RED)
    sb = scaling_binning(z, y, zb, 3, zs)
    ax[2].step(zs, sb, where="mid", color=RED)
    ax[2].plot(zs, ps, color=GREY, lw=0.8)
    ax[0].set_ylabel("calibrated probability")
    fig.tight_layout()
    savefig(fig, CH, "fig14-2", out)


def fig_14_3(out=None):
    """Figure 14.3: the softmax at temperatures 100, 2 and 1 for logits (3, 0, 1)."""
    a = np.array([3.0, 0.0, 1.0])
    fig, ax = plt.subplots(1, 3, figsize=(7.6, 2.4), sharey=True)
    for k, T in enumerate((100, 2, 1)):
        ax[k].bar([1, 2, 3], softmax(a, T), color=BLUE)
        ax[k].set_title("$T=%d$" % T); ax[k].set_xticks([1, 2, 3]); ax[k].set_ylim(0, 1)
    ax[0].set_ylabel("$\\mathrm{softmax}(a/T)$")
    fig.tight_layout()
    savefig(fig, CH, "fig14-3", out)


def hetero_data(n, rng):
    x = rng.uniform(0, 6, n)
    sd = 0.2 + 0.35 * np.abs(np.sin(x))
    y = np.sin(1.5 * x) + sd * rng.standard_normal(n)
    return x, y


def rbf_features(x, centres=np.linspace(0, 6, 13), width=0.6):
    return np.exp(-0.5 * ((np.asarray(x)[:, None] - centres[None, :]) / width) ** 2)


def fit_quantile_regression(x, y, gamma, alpha_reg=1e-4):
    """Linear quantile regression on RBF features, solving the pinball-loss linear programme with scipy HiGHS."""
    Phi = np.c_[np.ones(len(x)), rbf_features(x)]
    n, d = Phi.shape
    # min  sum gamma u+ + (1-gamma) u-  s.t.  y - Phi w = u+ - u-,  u+, u- >= 0 ; w free (+ tiny l1 on w excluded)
    c = np.r_[np.zeros(d), gamma * np.ones(n), (1 - gamma) * np.ones(n)]
    A = np.c_[Phi, np.eye(n), -np.eye(n)]
    res = optimize.linprog(c, A_eq=A, b_eq=y, bounds=[(None, None)] * d + [(0, None)] * (2 * n), method="highs")
    w = res.x[:d]
    return lambda xn: np.c_[np.ones(len(xn)), rbf_features(xn)] @ w


def cqr(x_tr, y_tr, x_cal, y_cal, alpha):
    lo = fit_quantile_regression(x_tr, y_tr, alpha / 2)
    hi = fit_quantile_regression(x_tr, y_tr, 1 - alpha / 2)
    s = np.maximum(lo(x_cal) - y_cal, y_cal - hi(x_cal))
    q = conformal_quantile(s, alpha)
    return lo, hi, q


def fig_14_5(out=None):
    """Figure 14.5b and 14.5c: conformalised quantile regression and the pinball loss."""
    rng = np.random.default_rng(1)
    xt, yt = hetero_data(300, rng)
    xc, yc = hetero_data(300, rng)
    lo, hi, q = cqr(xt, yt, xc, yc, 0.1)
    fig, ax = plt.subplots(1, 2, figsize=(9.2, 3.1), gridspec_kw={"width_ratios": [1.6, 1]})
    xs = np.linspace(0, 6, 300)
    ax[0].plot(xc, yc, ".", color=GREY, ms=3)
    ax[0].plot(xs, lo(xs), color=GREY, lw=1.2, label="raw quantile fit (5% and 95%)")
    ax[0].plot(xs, hi(xs), color=GREY, lw=1.2)
    ax[0].plot(xs, lo(xs) - q, color=RED, lw=1.6, label="conformalised, $\\hat q=%.3f$" % q)
    ax[0].plot(xs, hi(xs) + q, color=RED, lw=1.6)
    ax[0].set_xlabel("$x$"); ax[0].set_ylabel("$y$"); ax[0].legend(fontsize=8, loc="lower left")
    ax[0].set_title("(b) conformalised quantile regression")
    u = np.linspace(-2, 2, 400)
    for g, c in ((0.5, BLUE), (0.9, RED), (0.1, GREEN)):
        ax[1].plot(u, pinball(u, 0.0, g), color=c, label="$\\gamma=%.1f$" % g)
    ax[1].set_xlabel("$y-\\hat t$"); ax[1].legend(fontsize=8); ax[1].set_title("(c) pinball loss")
    fig.tight_layout()
    savefig(fig, CH, "fig14-5", out)


def coverage_experiment(n=100, alpha=0.1, reps=4000, seed=0):
    """Exchangeable scores: coverage of the prediction set = P(s_{n+1} <= q_hat | calibration set).
    With i.i.d. continuous scores this is F(q_hat) = U_(k), the k-th order statistic of n uniforms."""
    rng = np.random.default_rng(seed)
    k = int(np.ceil((n + 1) * (1 - alpha)))
    U = np.sort(rng.uniform(size=(reps, n)), axis=1)
    return U[:, k - 1]


def fig_own_14_1(out=None):
    """Own figure: the distribution of the conditional coverage of split conformal prediction."""
    n, alpha = 100, 0.1
    cov = coverage_experiment(n, alpha)
    k, l = coverage_pmf_params(n, alpha)
    fig, ax = plt.subplots(1, 2, figsize=(7.8, 2.8))
    ax[0].hist(cov, bins=40, density=True, color=BLUE, alpha=0.6, label="4000 simulated calibration sets")
    g = np.linspace(0.75, 1, 400)
    ax[0].plot(g, stats.beta.pdf(g, k, l), color=RED, label="Beta$(%d,%d)$" % (k, l))
    ax[0].axvline(1 - alpha, color="k", ls="--", lw=1)
    ax[0].set_xlabel("coverage given the calibration set"); ax[0].legend(fontsize=7)
    ax[0].set_title("$n=%d$, $\\alpha=%.1f$" % (n, alpha))
    ns = np.array([10, 20, 50, 100, 200, 500, 1000, 5000])
    mean_cov = np.ceil((ns + 1) * (1 - alpha)) / (ns + 1)
    ax[1].semilogx(ns, mean_cov, "o-", color=BLUE, label="$\\lceil (n+1)(1-\\alpha)\\rceil/(n+1)$")
    ax[1].axhline(1 - alpha, color="k", ls="--", lw=1)
    ax[1].set_xlabel("calibration size $n$"); ax[1].set_ylabel("marginal coverage"); ax[1].legend(fontsize=8)
    fig.tight_layout()
    savefig(fig, CH, "own14-1", out)


FIGURES = {"14.1": fig_14_1, "14.2": fig_14_2, "14.3": fig_14_3, "14.5": fig_14_5, "own14.1": fig_own_14_1}

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