"""Murphy (2022), Chapter 9: Linear Discriminant Analysis.

Companion code for Chapter 9 of K. P. Murphy, Probabilistic Machine Learning: An Introduction
(MIT Press, 2022; April 2025 draft), pp. 323-338, written from scratch with numpy, scipy and
matplotlib, to be read next to the lecture notes (../ch09-linear-discriminant-analysis.html).
scikit-learn is only used to confirm the implementations and to run the logistic regression
that Section 9.4 compares with.

Methods
* Section 9.2, Gaussian discriminant analysis: gda_fit (the maximum likelihood estimates (9.19)-(9.21)
  with full, tied, diagonal or tied diagonal covariances, and the regularised estimate (9.22)),
  gda_discriminant (9.4), lda_weights (9.6)-(9.8), binary_lda (9.13)-(9.15), nearest_centroid (9.23),
  fisher_binary (9.42), fisher_multi (9.45), flda_scatter (9.31)-(9.32), (9.43)-(9.44).
* Section 9.3, naive Bayes: nb_bernoulli_fit (9.53), nb_gauss_fit (9.54)-(9.55), the Laplace-smoothed
  Bayesian estimate (9.57)-(9.58), nb_bernoulli_logpost (9.47), nb_linear_form (9.60)-(9.62).
* Section 9.4, generative against discriminative classifiers, and missing features (9.63)-(9.65):
  gda_logpost_missing, nb_logpost_missing.

Data. Figures 9.1 to 9.3 and 9.8 use simulated data (the book's own points are not available, so the
panels are close stand-ins, not copies). Figure 9.4 uses the Davis height and weight of 199 adults
(Davis 1990; R package carData), standardised, in place of the book's height and weight data set.
Figure 9.5 uses the 11-class vowel data (Hastie, Tibshirani and Friedman, 2009), the same data as the
book, read from the copy cached by the companion course on The Elements of Statistical Learning (the
file is not part of this site). Figures 9.6 and 9.7 use MNIST (LeCun et al., 1998) binarised at 0.5 and
fitted with the exact Bernoulli naive Bayes of the text.

Figures. Reproduced here: 9.1, 9.2, 9.3 (computed version of the geometric sketch), 9.4, 9.5, 9.6, 9.7, 9.8.
Supplementary figures for the gaps filled in the notes:
  9.S1 learning curves of naive Bayes, LDA and logistic regression (generative against discriminative);
  9.S2 test error of regularised discriminant analysis against the shrinkage weight in (9.22);
  9.S3 calibration of naive Bayes and logistic regression (Section 9.4.1);
  9.S4 marginalising out missing features against imputing them (Section 9.4.3);
  9.S5 a simulated data set on which the PCA direction fails and Fisher's direction works (Section 9.2.6).
No figure is skipped.
Run `python3 ch09_linear_discriminant_analysis.py --list`, `python3 ch09_linear_discriminant_analysis.py`
(all figures, a few minutes) or `python3 ch09_linear_discriminant_analysis.py --fig 9.4`. Files go to
../img/ch09/; the data used by the browser demonstrations go to ../data/ch09-*.json.
"""
import json
import os
import subprocess
import sys

os.environ.setdefault("OPENBLAS_NUM_THREADS", "1")

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

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

CH = 9
HERE = os.path.dirname(os.path.abspath(__file__))
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
CACHE_DIR = os.path.join(HERE, "cache")
COLS = (RED, GREEN, BLUE)
LIGHT = ("#f6c9c9", "#cfe9cf", "#c6d8f2")


# =========================================================================== Section 9.2: GDA
def gda_fit(X, y, cov="full", lam=0.0, ridge=1e-9):
    """Maximum likelihood estimates (9.19)-(9.21) of a Gaussian discriminant analysis model.

    cov: 'full' (QDA), 'tied' (LDA), 'diag' (Gaussian naive Bayes), 'tieddiag' (diagonal LDA).
    lam: weight of the regularised estimate (9.22): Sigma = lam * diag(Sigma_mle) + (1 - lam) * Sigma_mle,
         applied to the tied covariance (for 'tied') or to each class covariance (for 'full').
    ridge: a tiny multiple of the identity added so that Cholesky factors exist when N_c <= D.
    Returns a dict with the class labels, priors pi (N_c / N), means mu (C x D) and covariances
    Sigma (C x D x D; tied estimates are repeated for each class).
    """
    X = np.asarray(X, float)
    classes = np.unique(y)
    C, D = len(classes), X.shape[1]
    N = len(X)
    pi = np.array([(y == c).mean() for c in classes])
    mu = np.array([X[y == c].mean(0) for c in classes])
    S = np.array([(X[y == c] - mu[i]).T @ (X[y == c] - mu[i]) / (y == c).sum() for i, c in enumerate(classes)])
    if cov == "full":
        Sig = S.copy()
    elif cov == "diag":
        Sig = np.array([np.diag(np.diag(s)) for s in S])
    else:
        T = (pi[:, None, None] * S).sum(0)          # (9.21): pooled covariance, = sum_c N_c S_c / N
        if cov == "tieddiag":
            T = np.diag(np.diag(T))
        Sig = np.repeat(T[None], C, axis=0)
    if lam:
        Sig = np.array([lam * np.diag(np.diag(s)) + (1 - lam) * s for s in Sig])
    Sig = Sig + ridge * np.eye(D)[None]
    return dict(classes=classes, pi=pi, mu=mu, Sigma=Sig, cov=cov)


def gda_discriminant(m, X):
    """log pi_c + log N(x | mu_c, Sigma_c) for every row of X and every class: (N x C), eq. (9.4)."""
    X = np.atleast_2d(X)
    return np.stack([np.log(m["pi"][c]) + common.gauss_logpdf(X, m["mu"][c], m["Sigma"][c])
                     for c in range(len(m["pi"]))], axis=1)


def gda_predict(m, X):
    return m["classes"][np.argmax(gda_discriminant(m, X), axis=1)]


def gda_posterior(m, X):
    a = gda_discriminant(m, X)
    return np.exp(a - common.logsumexp(a, axis=1, keepdims=True))


def lda_weights(m):
    """beta_c = Sigma^{-1} mu_c and gamma_c = log pi_c - mu_c' Sigma^{-1} mu_c / 2, eqs. (9.6)-(9.7)."""
    Sinv = np.linalg.inv(m["Sigma"][0])
    beta = m["mu"] @ Sinv                                   # row c is (Sigma^{-1} mu_c)'
    gamma = np.log(m["pi"]) - 0.5 * np.einsum("cd,cd->c", beta, m["mu"])
    return beta, gamma


def binary_lda(m):
    """w, x0 and the threshold of the two-class rule (9.13)-(9.16): p(y=1|x) = sigmoid(w'(x - x0))."""
    Sinv = np.linalg.inv(m["Sigma"][0])
    d = m["mu"][1] - m["mu"][0]
    w = Sinv @ d
    x0 = 0.5 * (m["mu"][1] + m["mu"][0]) - d * np.log(m["pi"][1] / m["pi"][0]) / (d @ Sinv @ d)
    return w, x0, float(w @ x0)


def nearest_centroid(X, mu, Sigma=None):
    """(9.23): the class whose mean is nearest in (squared) Mahalanobis distance."""
    X = np.atleast_2d(X)
    Sinv = np.eye(X.shape[1]) if Sigma is None else np.linalg.inv(Sigma)
    d2 = np.stack([np.einsum("nd,de,ne->n", X - m, Sinv, X - m) for m in mu], axis=1)
    return np.argmin(d2, axis=1)


def n_parameters(C, D, cov):
    """Number of free parameters of the GDA variants (priors, means, covariances)."""
    base = (C - 1) + C * D
    return base + dict(full=C * D * (D + 1) // 2, tied=D * (D + 1) // 2, diag=C * D, tieddiag=D)[cov]


# =========================================================================== Section 9.2.6: Fisher
def flda_scatter(X, y):
    """Within-class and between-class scatter matrices, (9.32) and (9.44) (S_B with weights N_c)."""
    classes = np.unique(y)
    D = X.shape[1]
    m = X.mean(0)
    SW = np.zeros((D, D))
    SB = np.zeros((D, D))
    for c in classes:
        Xc = X[y == c]
        mc = Xc.mean(0)
        SW += (Xc - mc).T @ (Xc - mc)
        SB += len(Xc) * np.outer(mc - m, mc - m)
    return SW, SB


def fisher_binary(X, y):
    """The optimal projection direction w = S_W^{-1}(mu_2 - mu_1) of (9.42), scaled to unit length."""
    c = np.unique(y)
    SW, _ = flda_scatter(X, y)
    d = X[y == c[1]].mean(0) - X[y == c[0]].mean(0)
    w = np.linalg.solve(SW, d)
    return w / np.linalg.norm(w)


def fisher_ratio(w, X, y):
    """J(w) of (9.29): (m_2 - m_1)^2 / (s_1^2 + s_2^2) for two classes."""
    c = np.unique(y)
    z = X @ w
    m1, m2 = z[y == c[0]].mean(), z[y == c[1]].mean()
    s = ((z[y == c[0]] - m1) ** 2).sum() + ((z[y == c[1]] - m2) ** 2).sum()
    return (m2 - m1) ** 2 / s


def fisher_multi(X, y, K):
    """The K leading generalised eigenvectors of S_B w = lambda S_W w, normalised so W' S_W W = I.

    This is W = S_W^{-1/2} U of the text (U: eigenvectors of S_W^{-1/2} S_B S_W^{-1/2}), up to a rotation of the
    columns that does not change the criterion (9.45). Returns (W, eigenvalues), W of shape D x K.
    """
    SW, SB = flda_scatter(X, y)
    vals, vecs = linalg.eigh(SB, SW)                    # ascending
    order = np.argsort(vals)[::-1]
    return vecs[:, order[:K]], vals[order]


def pca_basis(X, K):
    Xc = X - X.mean(0)
    _, _, Vt = np.linalg.svd(Xc, full_matrices=False)
    return Vt[:K].T


# =========================================================================== Section 9.3: naive Bayes
def nb_bernoulli_fit(Xb, y, alpha=1.0):
    """pi_c = N_c / N and theta_dc = (N_dc + alpha) / (N_c + 2 alpha): (9.53), and Laplace smoothing (9.58) at alpha = 1."""
    classes = np.unique(y)
    Nc = np.array([(y == c).sum() for c in classes], float)
    Ndc = np.array([Xb[y == c].sum(0) for c in classes], float)
    theta = (Ndc + alpha) / (Nc[:, None] + 2 * alpha)
    return dict(classes=classes, pi=Nc / Nc.sum(), theta=np.clip(theta, 1e-12, 1 - 1e-12))


def nb_bernoulli_logjoint(m, Xb, observed=None):
    """log pi_c + sum_d log Ber(x_d | theta_dc), the numerator of (9.47). observed: boolean mask of the
    features that are seen; the others are dropped from the sum, which is the marginalisation (9.65)."""
    Xb = np.asarray(Xb, float)
    obs = np.ones(Xb.shape[1]) if observed is None else np.asarray(observed, float)
    L = np.log(m["theta"])
    L1 = np.log1p(-m["theta"])
    return np.log(m["pi"])[None] + (Xb * obs) @ L.T + ((1 - Xb) * obs) @ L1.T


def nb_bernoulli_predict(m, Xb, observed=None):
    return m["classes"][np.argmax(nb_bernoulli_logjoint(m, Xb, observed), axis=1)]


def nb_bernoulli_posterior(m, Xb, observed=None):
    a = nb_bernoulli_logjoint(m, Xb, observed)
    return np.exp(a - common.logsumexp(a, axis=1, keepdims=True))


def nb_linear_form(m):
    """beta_c, gamma_c of (9.62) for the Bernoulli model: logit weights log(theta/(1-theta)) and the offset
    log pi_c + sum_d log(1 - theta_dc)."""
    beta = np.log(m["theta"]) - np.log1p(-m["theta"])
    gamma = np.log(m["pi"]) + np.log1p(-m["theta"]).sum(1)
    return beta, gamma


def nb_gauss_fit(X, y):
    """(9.54)-(9.55): per-class, per-feature mean and 1/N_c variance."""
    classes = np.unique(y)
    pi = np.array([(y == c).mean() for c in classes])
    mu = np.array([X[y == c].mean(0) for c in classes])
    var = np.array([X[y == c].var(0) for c in classes])
    return dict(classes=classes, pi=pi, mu=mu, var=var)


def nb_gauss_logjoint(m, X):
    X = np.atleast_2d(X)
    out = []
    for c in range(len(m["pi"])):
        v = m["var"][c] + 1e-9
        out.append(np.log(m["pi"][c]) - 0.5 * (np.log(2 * np.pi * v) + (X - m["mu"][c]) ** 2 / v).sum(1))
    return np.stack(out, axis=1)


# =========================================================================== Section 9.4.3: missing features
def gda_logpost_missing(m, x, observed):
    """log p(y = c, x_obs | theta) for each class when only the coordinates in `observed` (boolean mask) are seen:
    the Gaussian marginal over the observed block is used (9.63)-(9.64)."""
    idx = np.where(observed)[0]
    out = []
    for c in range(len(m["pi"])):
        S = m["Sigma"][c][np.ix_(idx, idx)]
        out.append(np.log(m["pi"][c]) + common.gauss_logpdf(x[idx][None], m["mu"][c][idx], S)[0])
    return np.array(out)


# =========================================================================== data
def sim_three_classes(n=(60, 60, 60), seed=3):
    """Simulated 2-d data from three classes in the spirit of Figure 9.1: red spherical, green with unequal
    independent variances, blue correlated."""
    rng = np.random.default_rng(seed)
    mus = [np.array([-2.0, 1.0]), np.array([2.0, 3.0]), np.array([2.0, -1.5])]
    Sig = [np.array([[0.9, 0.0], [0.0, 0.9]]), np.array([[2.2, 0.0], [0.0, 0.5]]),
           np.array([[1.6, 1.3], [1.3, 1.6]])]
    X = np.vstack([rng.multivariate_normal(mus[c], Sig[c], n[c]) for c in range(3)])
    y = np.repeat(np.arange(3), n)
    return X, y, mus, Sig


def davis():
    """Height and weight of adults (R package carData::Davis), as a DataFrame (sex, weight, height).
    One row has weight and height swapped (166 kg, 57 cm) and is removed."""
    import pandas as pd
    os.makedirs(CACHE_DIR, exist_ok=True)
    path = os.path.join(CACHE_DIR, "ch09_davis.csv")
    if not os.path.exists(path):
        subprocess.run(["/usr/local/bin/Rscript", "-e",
                        "write.csv(carData::Davis[,c('sex','weight','height')],'%s',row.names=FALSE)" % path],
                       check=True, capture_output=True)
    df = pd.read_csv(path)
    return df[df.height > 100].reset_index(drop=True)


def vowel():
    """The 11-class vowel data of Hastie, Tibshirani and Friedman (2009): 528 training and 462 test rows, 10 features."""
    import pandas as pd
    base = os.path.join(os.path.expanduser("~"), ".cache", "prml-repro", "esl")
    tr = pd.read_csv(os.path.join(base, "vowel.train"), index_col=0)
    te = pd.read_csv(os.path.join(base, "vowel.test"), index_col=0)
    return tr.iloc[:, 1:].values, tr["y"].values, te.iloc[:, 1:].values, te["y"].values


def digits_binary(seed=0, ntrain=1000):
    """8 x 8 digits (scikit-learn), binarised at pixel > 8 (of 16), shuffled once; first ntrain rows train."""
    from sklearn.datasets import load_digits
    d = load_digits()
    p = np.random.default_rng(seed).permutation(len(d.target))
    X = (d.data[p] > 8).astype(float)
    y = d.target[p]
    return X[:ntrain], y[:ntrain], X[ntrain:], y[ntrain:], d.data[p]


def _seg(a, b):
    """x and y coordinates of the segment from a to b, for ax.plot(*_seg(a, b))."""
    return np.array([a[0], b[0]]), np.array([a[1], b[1]])


def _grid(ax, pad=0.5, n=260):
    x0, x1 = ax.get_xlim()
    y0, y1 = ax.get_ylim()
    gx, gy = np.meshgrid(np.linspace(x0, x1, n), np.linspace(y0, y1, n))
    return gx, gy, np.c_[gx.ravel(), gy.ravel()]


def _regions(ax, predict, n=260):
    gx, gy, G = _grid(ax, n=n)
    z = predict(G).reshape(gx.shape)
    ax.contourf(gx, gy, z, levels=np.arange(-0.5, 3.5, 1), colors=LIGHT, alpha=0.9, zorder=0)
    ax.contour(gx, gy, z, levels=np.arange(0.5, 2.5, 1), colors="k", linewidths=1.1, zorder=1)


# =========================================================================== figures
def fig_9_1(out=None):
    """Figure 9.1: three-class 2-d data and the fitted Gaussians."""
    X, y, mus, Sig = sim_three_classes()
    m = gda_fit(X, y, "full", ridge=0)
    fig, axes = common.panel_grid(1, 2, size=(3.4, 3.1))
    for k, ax in enumerate(axes[0]):
        for c, mk in zip(range(3), ("o", "s", "^")):
            ax.scatter(*X[y == c].T, s=14, color=COLS[c], marker=mk, alpha=0.85, lw=0)
        ax.set_xlim(-5, 6.5)
        ax.set_ylim(-5, 6.5)
        ax.set_aspect("equal")
        common.panel_label(ax, "ab"[k], "upper left")
    for c in range(3):
        for nsd in (1, 2):
            axes[0, 1].plot(*ellipse_xy(m["mu"][c], m["Sigma"][c], nsd), color=COLS[c], lw=1.4)
        axes[0, 1].plot(*m["mu"][c], "k+", ms=8)
    axes[0, 0].set_title("data from three classes")
    axes[0, 1].set_title("fitted Gaussians (1 and 2 sd)")
    return savefig(fig, CH, "fig9-1", out)


def fig_9_2(out=None):
    """Figure 9.2: QDA and LDA decision regions for the data of Figure 9.1."""
    X, y, _, _ = sim_three_classes()
    fig, axes = common.panel_grid(1, 2, size=(3.4, 3.1))
    for k, (cov, name) in enumerate((("full", "QDA"), ("tied", "LDA"))):
        ax = axes[0, k]
        m = gda_fit(X, y, cov, ridge=0)
        ax.set_xlim(-5, 6.5)
        ax.set_ylim(-5, 6.5)
        _regions(ax, lambda G, m=m: gda_predict(m, G))
        for c, mk in zip(range(3), ("o", "s", "^")):
            ax.scatter(*X[y == c].T, s=14, color=COLS[c], marker=mk, alpha=0.9, lw=0, zorder=3)
        ax.set_aspect("equal")
        ax.set_title("%s: train error %.1f%%" % (name, 100 * (gda_predict(m, X) != y).mean()))
        common.panel_label(ax, "ab"[k], "upper left")
    return savefig(fig, CH, "fig9-2", out)


def fig_9_3(out=None):
    """Figure 9.3: geometry of two-class LDA with Sigma = I, for equal and unequal priors."""
    mu0, mu1 = np.array([-1.6, -0.6]), np.array([1.4, 1.0])
    fig, axes = common.panel_grid(1, 2, size=(3.5, 3.2))
    for k, (pi1, ttl) in enumerate(((0.5, "equal priors"), (0.85, r"$\pi_1 = 0.85$: boundary moves towards $\mu_0$"))):
        ax = axes[0, k]
        m = dict(pi=np.array([1 - pi1, pi1]), mu=np.array([mu0, mu1]), Sigma=np.array([np.eye(2)] * 2))
        w, x0, _ = binary_lda(m)
        d = mu1 - mu0
        u = d / np.linalg.norm(d)
        t = np.array([-u[1], u[0]])
        ax.plot(*ellipse_xy(mu0, np.eye(2), 1), color=RED, lw=1.3)
        ax.plot(*ellipse_xy(mu1, np.eye(2), 1), color=BLUE, lw=1.3)
        ax.plot(*_seg(mu0 - 1.2 * u, mu1 + 1.2 * u), color=GREY, lw=1, ls=":")
        ax.plot(*_seg(x0 - 3 * t, x0 + 3 * t), color="k", lw=1.6)
        ax.plot(*mu0, "o", color=RED)
        ax.plot(*mu1, "o", color=BLUE)
        ax.plot(*x0, "ks", ms=5)
        ax.annotate("", xy=x0 + 1.1 * u, xytext=x0, arrowprops=dict(arrowstyle="->", color="k", lw=1.4))
        ax.text(*(x0 + 1.15 * u + 0.12 * t), r"$\mathbf{w}$", fontsize=10)
        xt = np.array([0.2, 1.9])
        proj = x0 + ((xt - x0) @ u) * u
        ax.plot(*xt, "x", color=GREEN, ms=7)
        ax.plot(*_seg(xt, proj), color=GREEN, lw=0.9, ls="--")
        ax.plot(*proj, ".", color=GREEN)
        ax.text(mu0[0] - 0.2, mu0[1] - 0.85, r"$\mu_0$", color=RED)
        ax.text(mu1[0] + 0.15, mu1[1] - 0.85, r"$\mu_1$", color=BLUE)
        ax.text(x0[0] + 0.12, x0[1] - 0.45, r"$x_0$")
        ax.set_xlim(-4, 4)
        ax.set_ylim(-3, 3.4)
        ax.set_aspect("equal")
        ax.set_title(ttl, fontsize=9.5)
        common.panel_label(ax, "ab"[k], "upper left")
    return savefig(fig, CH, "fig9-3", out)


def _davis_std():
    df = davis()
    X = df[["height", "weight"]].values.astype(float)
    X = (X - X.mean(0)) / X.std(0)
    y = (df["sex"] == "M").astype(int).values       # 0 = female, 1 = male
    return X, y


def _pca_vs_fisher(X, y, names, out, fname):
    w_f = fisher_binary(X, y)
    w_p = pca_basis(X, 1)[:, 0]
    if w_p @ w_f < 0:
        w_p = -w_p
    fig, axes = common.panel_grid(2, 2, size=(3.5, 3.0))
    fig.subplots_adjust(hspace=0.55, wspace=0.3)
    cen = X.mean(0)
    for k, (w, nm) in enumerate(((w_p, "PCA"), (w_f, "Fisher LDA"))):
        ax = axes[0, k]
        ax.scatter(*X[y == 1].T, s=10, color=BLUE, marker="o", alpha=0.7, lw=0, label=names[2])
        ax.scatter(*X[y == 0].T, s=12, color=RED, marker="x", alpha=0.7, lw=0.8, label=names[3])
        ax.plot(*_seg(cen - 3.2 * w, cen + 3.2 * w), color="k", lw=1.6, label=nm + " direction")
        ax.set_xlabel(names[0])
        ax.set_ylabel(names[1])
        lim = np.abs(X).max() * 1.1
        ax.set_xlim(-lim, lim)
        ax.set_ylim(-lim, lim)
        ax.set_aspect("equal")
        ax.legend(loc="lower right", fontsize=7.5)
        common.panel_label(ax, "ab"[k], "upper left")
        axb = axes[1, k]
        z = X @ w
        bins = np.linspace(z.min(), z.max(), 30)
        axb.hist(z[y == 0], bins=bins, color=RED, alpha=0.6, label=names[3])
        axb.hist(z[y == 1], bins=bins, color=BLUE, alpha=0.6, label=names[2])
        axb.set_xlabel("projection onto the %s direction" % nm.split()[0])
        axb.set_title("J(w) = %.4f" % fisher_ratio(w, X, y), fontsize=9)
        common.panel_label(axb, "cd"[k], "upper left")
    return savefig(fig, CH, fname, out)


def fig_9_4(out=None):
    """Figure 9.4: PCA against Fisher's LDA direction, height and weight of men and women."""
    X, y = _davis_std()
    return _pca_vs_fisher(X, y, ("standardised height", "standardised weight", "male", "female"), out, "fig9-4")


def pca_trap_data(n=150, seed=4):
    """Two classes whose means differ along the low-variance axis: the first principal component is useless."""
    rng = np.random.default_rng(seed)
    cov = np.array([[4.0, 1.2], [1.2, 0.5]])
    Z = np.vstack([rng.multivariate_normal([0, -0.55], cov, n), rng.multivariate_normal([0, 0.55], cov, n)])
    y = np.repeat([0, 1], n)
    return Z, y


def fig_9_S5(out=None):
    """Supplementary: a data set on which the PCA direction fails and Fisher's direction succeeds."""
    X, y = pca_trap_data()
    return _pca_vs_fisher(X, y, ("feature 1", "feature 2", "class 2", "class 1"), out, "fig9-S5")


def fig_9_5(out=None):
    """Figure 9.5: PCA against FLDA projection of the 11-class vowel data to 2-d."""
    Xtr, ytr, Xte, yte = vowel()
    P = pca_basis(Xtr, 2)
    W, _ = fisher_multi(Xtr, ytr, 2)
    cm = plt.get_cmap("turbo")
    fig, axes = common.panel_grid(1, 2, size=(4.0, 3.6))
    for k, (Z, nm) in enumerate((((Xtr - Xtr.mean(0)) @ P, "PCA"), ((Xtr - Xtr.mean(0)) @ W, "FLDA"))):
        ax = axes[0, k]
        for c in np.unique(ytr):
            sel = ytr == c
            ax.scatter(*Z[sel].T, s=11, color=cm((c - 1) / 10.0), lw=0,
                       marker="osd^v<>p*hH"[c - 1], alpha=0.85)
        ax.set_title("%s projection of the vowel data to 2d" % nm, fontsize=9.5)
        common.panel_label(ax, "ab"[k], "upper left")
    return savefig(fig, CH, "fig9-5", out)


def _mnist_nb():
    Xtr, ytr = common.mnist(True)
    Xte, yte = common.mnist(False)
    Xtr, Xte = (Xtr > 0.5).astype(float), (Xte > 0.5).astype(float)
    m = nb_bernoulli_fit(Xtr, ytr, alpha=1.0)
    return m, Xte, yte


def fig_9_6(out=None):
    """Figure 9.6: Bernoulli class-conditional densities (the parameters theta_dc) of a naive Bayes classifier on binarised MNIST."""
    m, Xte, yte = _mnist_nb()
    fig, axes = common.panel_grid(2, 5, size=(1.45, 1.55))
    for c in range(10):
        ax = axes[c // 5, c % 5]
        ax.imshow(m["theta"][c].reshape(28, 28), cmap="gray_r", vmin=0, vmax=1)
        ax.set_title("class %d" % c, fontsize=8.5)
        ax.axis("off")
    acc = (nb_bernoulli_predict(m, Xte) == yte).mean()
    print("  test accuracy of the Bernoulli naive Bayes classifier on MNIST: %.4f" % acc)
    return savefig(fig, CH, "fig9-6", out)


def fig_9_7(out=None):
    """Figure 9.7: predictions of the naive Bayes classifier on binarised MNIST test images."""
    m, Xte, yte = _mnist_nb()
    P = nb_bernoulli_posterior(m, Xte[:10])
    fig, axes = common.panel_grid(2, 5, size=(1.45, 1.7))
    for i in range(10):
        ax = axes[i // 5, i % 5]
        ax.imshow(Xte[i].reshape(28, 28), cmap="gray_r")
        ok = P[i].argmax() == yte[i]
        ax.set_title("pred %d (p=%.2f)" % (P[i].argmax(), P[i].max()), fontsize=8.5, color="k" if ok else RED)
        ax.axis("off")
    return savefig(fig, CH, "fig9-7", out)


def _one_d_densities():
    x = np.linspace(0, 1, 1001)
    p1 = 0.5 * stats.norm.pdf(x, 0.18, 0.06) + 0.5 * stats.norm.pdf(x, 0.38, 0.07)
    p2 = 0.45 * stats.norm.pdf(x, 0.58, 0.07) + 0.55 * stats.norm.pdf(x, 0.8, 0.07)
    return x, p1, p2


def fig_9_8(out=None):
    """Figure 9.8: class-conditional densities can be more complex than the posterior."""
    x, p1, p2 = _one_d_densities()
    post1 = p1 / (p1 + p2)
    fig, axes = common.panel_grid(1, 2, size=(3.5, 2.6))
    axes[0, 0].plot(x, p1, color=BLUE, label=r"$p(x|y=1)$")
    axes[0, 0].plot(x, p2, color=RED, ls="--", label=r"$p(x|y=2)$")
    axes[0, 0].set_xlabel("x")
    axes[0, 0].set_ylabel("class conditional densities")
    axes[0, 0].legend(loc="upper center", fontsize=8)
    axes[0, 1].plot(x, post1, color=BLUE, label=r"$p(y=1|x)$")
    axes[0, 1].plot(x, 1 - post1, color=RED, ls="--", label=r"$p(y=2|x)$")
    axes[0, 1].set_xlabel("x")
    axes[0, 1].set_ylim(-0.05, 1.05)
    axes[0, 1].legend(loc="center right", fontsize=8)
    for k in range(2):
        common.panel_label(axes[0, k], "ab"[k], "upper left" if k == 0 else "lower left")
    return savefig(fig, CH, "fig9-8", out)


# ------------------------------------------------------------------ supplementary
def _split_fit_error(Xtr, ytr, Xte, yte, kind, lr_C=1e4):
    if kind == "gnb":
        return (gda_predict(gda_fit(Xtr, ytr, "diag", ridge=1e-6), Xte) != yte).mean()
    if kind == "lda":
        return (gda_predict(gda_fit(Xtr, ytr, "tied", ridge=1e-3), Xte) != yte).mean()
    from sklearn.linear_model import LogisticRegression
    clf = LogisticRegression(C=lr_C, max_iter=2000).fit(Xtr, ytr)
    return (clf.predict(Xte) != yte).mean()


def _bc_data():
    from sklearn.datasets import load_breast_cancer
    d = load_breast_cancer()
    X = d.data[:, :20]
    return (X - X.mean(0)) / X.std(0), d.target


def _nb_world(n_total=4000, D=10, seed=7):
    """Two classes with independent unit-variance Gaussian features (the naive Bayes and LDA assumptions hold)."""
    rng = np.random.default_rng(seed)
    delta = rng.normal(0, 1.0, D)
    y = rng.integers(0, 2, n_total)
    X = rng.normal(size=(n_total, D)) + np.where(y[:, None] == 1, 0.5, -0.5) * delta
    return X, y


def learning_curves(which="bc", n_rep=60, sizes=(8, 12, 20, 30, 50, 80, 130, 200, 300), seed=0):
    X, y = _bc_data() if which == "bc" else _nb_world()
    rng = np.random.default_rng(seed)
    res = {k: np.zeros((n_rep, len(sizes))) for k in ("gnb", "lda", "lr")}
    nte = 200 if which == "bc" else 2000
    for r in range(n_rep):
        p = rng.permutation(len(y))
        te = p[:nte]
        for j, n in enumerate(sizes):
            tr = p[nte:nte + n]
            while len(np.unique(y[tr])) < 2:
                tr = p[nte:nte + len(tr) + 1]
            for k in res:
                res[k][r, j] = _split_fit_error(X[tr], y[tr], X[te], y[te], k)
    return sizes, res


def fig_9_S1(out=None):
    """Supplementary: learning curves of generative (naive Bayes, LDA) and discriminative (logistic) classifiers."""
    fig, axes = common.panel_grid(1, 2, size=(3.9, 3.0))
    for k0, (which, ttl) in enumerate((("bc", "(a) breast cancer data, correlated features"),
                                       ("sim", "(b) simulated data, independent Gaussian features"))):
        sizes, res = learning_curves(which, sizes=(8, 12, 20, 30, 50, 80, 130, 200, 300) if which == "bc" else (6, 10, 16, 30, 60, 120, 250))
        ax = axes[0, k0]
        for k, nm, c in (("gnb", "Gaussian naive Bayes", ORANGE), ("lda", "LDA (tied covariance)", GREEN),
                         ("lr", "logistic regression", BLUE)):
            mu = res[k].mean(0)
            se = res[k].std(0) / np.sqrt(res[k].shape[0])
            ax.plot(sizes, 100 * mu, "o-", color=c, ms=3.5, label=nm)
            ax.fill_between(sizes, 100 * (mu - se), 100 * (mu + se), color=c, alpha=0.2, lw=0)
        ax.set_xscale("log")
        ax.set_xlabel("number of training points")
        ax.set_ylabel("test error (%)")
        ax.set_title(ttl, fontsize=8.5)
        if k0 == 0:
            ax.legend(fontsize=7.5)
    return savefig(fig, CH, "fig9-S1", out)


def rda_curves(seed=0, reps=30, lams=None, per_class=20):
    from sklearn.datasets import load_digits
    d = load_digits()
    X, y = d.data / 16.0, d.target
    lams = np.linspace(0, 1, 21) if lams is None else lams
    rng = np.random.default_rng(seed)
    err = np.zeros((reps, len(lams)))
    for r in range(reps):
        tr = np.concatenate([rng.choice(np.where(y == c)[0], per_class, replace=False) for c in range(10)])
        te = np.setdiff1d(np.arange(len(y)), tr)
        for j, lam in enumerate(lams):
            m = gda_fit(X[tr], y[tr], "tied", lam=lam, ridge=1e-3)
            err[r, j] = (gda_predict(m, X[te]) != y[te]).mean()
    return lams, err


def fig_9_S2(out=None):
    """Supplementary: regularised discriminant analysis, test error against the shrinkage weight lambda of (9.22)."""
    lams, err = rda_curves()
    fig, axes = common.panel_grid(1, 1, size=(4.4, 3.0))
    ax = axes[0, 0]
    mu, se = err.mean(0), err.std(0) / np.sqrt(err.shape[0])
    ax.plot(lams, 100 * mu, "o-", color=BLUE, ms=3.5)
    ax.fill_between(lams, 100 * (mu - se), 100 * (mu + se), color=BLUE, alpha=0.2, lw=0)
    ax.set_xlabel(r"shrinkage weight $\lambda$ (0: MLE, 1: diagonal)")
    ax.set_ylabel("test error (%)")
    ax.set_title("digits, 20 training images per class, D = 64", fontsize=9)
    return savefig(fig, CH, "fig9-S2", out)


def calibration_data():
    from sklearn.linear_model import LogisticRegression
    Xtr, ytr, Xte, yte, _ = digits_binary()
    nb = nb_bernoulli_fit(Xtr, ytr, 1.0)
    pn = nb_bernoulli_posterior(nb, Xte)
    lr = LogisticRegression(C=1.0, max_iter=3000).fit(Xtr, ytr)
    pl = lr.predict_proba(Xte)
    return pn, pl, yte


def _reliability(P, y, bins=10):
    conf = P.max(1)
    ok = (P.argmax(1) == y).astype(float)
    edges = np.linspace(0, 1, bins + 1)
    idx = np.clip(np.digitize(conf, edges) - 1, 0, bins - 1)
    c, a, n = [], [], []
    for b in range(bins):
        s = idx == b
        if s.sum() > 0:
            c.append(conf[s].mean())
            a.append(ok[s].mean())
            n.append(s.sum())
    return np.array(c), np.array(a), np.array(n)


def fig_9_S3(out=None):
    """Supplementary: confidence histogram and reliability curve of naive Bayes against logistic regression."""
    pn, pl, y = calibration_data()
    fig, axes = common.panel_grid(1, 2, size=(3.5, 3.0))
    for P, nm, c in ((pn, "naive Bayes", ORANGE), (pl, "logistic regression", BLUE)):
        axes[0, 0].hist(P.max(1), bins=np.linspace(0.1, 1, 19), alpha=0.55, color=c, label=nm)
        cc, aa, nn = _reliability(P, y)
        axes[0, 1].plot(cc, aa, "o-", color=c, ms=4, label=nm)
    axes[0, 1].plot([0, 1], [0, 1], color=GREY, ls=":")
    axes[0, 0].set_xlabel("largest posterior probability")
    axes[0, 0].set_ylabel("test images")
    axes[0, 0].legend(fontsize=8, loc="upper left")
    axes[0, 1].set_xlabel("confidence")
    axes[0, 1].set_ylabel("accuracy")
    axes[0, 1].set_xlim(0.2, 1.02)
    axes[0, 1].set_ylim(0.2, 1.02)
    for k in range(2):
        common.panel_label(axes[0, k], "ab"[k], "upper right" if k == 0 else "lower right")
    return savefig(fig, CH, "fig9-S3", out)


def missing_curves(seed=0, reps=40):
    Xtr, ytr, Xte, yte = vowel()
    m = gda_fit(Xtr, ytr, "tied", ridge=0)
    mu_all = Xtr.mean(0)
    D = Xtr.shape[1]
    rng = np.random.default_rng(seed)
    ks = list(range(0, 9))
    out = {k: np.zeros((len(ks), 3)) for k in ("marg", "mean", "zero")}
    res = np.zeros((len(ks), 3))
    for j, k in enumerate(ks):
        acc = np.zeros(3)
        cnt = 0
        for r in range(reps if k else 1):
            obs = np.ones(D, bool)
            if k:
                obs[rng.choice(D, k, replace=False)] = False
            sel = rng.choice(len(Xte), 100, replace=False) if k else np.arange(len(Xte))
            for i in sel:
                x = Xte[i]
                pm = m["classes"][np.argmax(gda_logpost_missing(m, x, obs))]
                xi = np.where(obs, x, mu_all)
                pi_ = gda_predict(m, xi[None])[0]
                xz = np.where(obs, x, 0.0)
                pz = gda_predict(m, xz[None])[0]
                acc += np.array([pm == yte[i], pi_ == yte[i], pz == yte[i]])
                cnt += 1
        res[j] = acc / cnt
    return ks, res


def fig_9_S4(out=None):
    """Supplementary: marginalising missing features (9.63) against mean imputation and zero imputation."""
    ks, res = missing_curves()
    fig, axes = common.panel_grid(1, 1, size=(4.4, 3.0))
    ax = axes[0, 0]
    for j, nm, c in ((0, "marginalise (9.63)", GREEN), (1, "impute the training mean", ORANGE), (2, "impute zero", RED)):
        ax.plot(ks, 100 * (1 - res[:, j]), "o-", color=c, ms=3.5, label=nm)
    ax.set_xlabel("number of missing features (of 10)")
    ax.set_ylabel("test error (%)")
    ax.legend(fontsize=8)
    ax.set_title("LDA on the vowel data, features missing at random", fontsize=9)
    return savefig(fig, CH, "fig9-S4", out)


FIGURES = {"9.1": fig_9_1, "9.2": fig_9_2, "9.3": fig_9_3, "9.4": fig_9_4, "9.5": fig_9_5,
           "9.6": fig_9_6, "9.7": fig_9_7, "9.8": fig_9_8,
           "9.S1": fig_9_S1, "9.S2": fig_9_S2, "9.S3": fig_9_S3, "9.S4": fig_9_S4, "9.S5": fig_9_S5}


# =========================================================================== data for the browser demos
def _r(a, k=5):
    return np.round(np.asarray(a, float), k).tolist()


def export_json():
    os.makedirs(DATA_OUT, exist_ok=True)
    # ---- demo 1: three 2-d data sets for GDA
    from sklearn.datasets import load_iris
    rng = np.random.default_rng(11)
    X, y, _, _ = sim_three_classes((50, 50, 50), seed=5)
    Xt, yt, _, _ = sim_three_classes((200, 200, 200), seed=77)
    iris = load_iris()
    Xi = iris.data[:, [2, 3]]
    p = rng.permutation(150)
    sim_tied = []
    mus = [np.array([-2.0, 0.0]), np.array([2.0, 2.2]), np.array([1.5, -2.0])]
    Sg = np.array([[1.5, 0.9], [0.9, 1.2]])
    Xs = np.vstack([rng.multivariate_normal(m_, Sg, 50) for m_ in mus])
    ys = np.repeat(np.arange(3), 50)
    Xst = np.vstack([rng.multivariate_normal(m_, Sg, 200) for m_ in mus])
    yst = np.repeat(np.arange(3), 200)
    sets = {
        "sim": dict(name="Simulated, unequal covariances (Figure 9.1)", train=dict(x=_r(X, 4), y=y.tolist()),
                    test=dict(x=_r(Xt, 4), y=yt.tolist())),
        "tied": dict(name="Simulated, one shared covariance", train=dict(x=_r(Xs, 4), y=ys.tolist()),
                     test=dict(x=_r(Xst, 4), y=yst.tolist())),
        "iris": dict(name="Iris petal length and width", train=dict(x=_r(Xi[p[:90]], 3), y=iris.target[p[:90]].tolist()),
                     test=dict(x=_r(Xi[p[90:]], 3), y=iris.target[p[90:]].tolist())),
    }
    refs = {}
    for key, d in sets.items():
        Xa, ya = np.array(d["train"]["x"]), np.array(d["train"]["y"])
        Xb, yb = np.array(d["test"]["x"]), np.array(d["test"]["y"])
        r = {}
        for cov in ("full", "tied", "diag", "tieddiag"):
            m = gda_fit(Xa, ya, cov, ridge=0 if cov in ("full", "tied") else 0)
            r[cov] = dict(train=float((gda_predict(m, Xa) != ya).mean()), test=float((gda_predict(m, Xb) != yb).mean()))
        mr = gda_fit(Xa, ya, "tied", lam=0.5, ridge=0)
        r["tied_lam0.5"] = dict(train=float((gda_predict(mr, Xa) != ya).mean()), test=float((gda_predict(mr, Xb) != yb).mean()))
        refs[key] = r
        d["ref"] = r
    with open(os.path.join(DATA_OUT, "ch09-gda2d.json"), "w") as f:
        json.dump(sets, f, separators=(",", ":"))
    # ---- demo 2: Fisher direction (Davis height and weight, and a PCA-trap data set)
    def fisher_set(Xd, yd):
        wf = fisher_binary(Xd, yd)
        wp = pca_basis(Xd, 1)[:, 0]
        if wp @ wf < 0:
            wp = -wp
        ang = lambda w: float(np.degrees(np.arctan2(w[1], w[0])) % 180)
        return dict(x=_r(Xd, 4), y=yd.tolist(),
                    ref=dict(fisher_angle=ang(wf), pca_angle=ang(wp), J_fisher=fisher_ratio(wf, Xd, yd),
                             J_pca=fisher_ratio(wp, Xd, yd), J_at_0=fisher_ratio(np.array([1.0, 0.0]), Xd, yd),
                             J_at_90=fisher_ratio(np.array([0.0, 1.0]), Xd, yd)))
    Xd, yd = _davis_std()
    Xt, yt = pca_trap_data()
    d2 = dict(davis=dict(name="Height and weight of adults (standardised)", labels=["female", "male"], **fisher_set(Xd, yd)),
              trap=dict(name="Simulated: classes differ along the low-variance axis", labels=["class 1", "class 2"], **fisher_set(Xt, yt)))
    with open(os.path.join(DATA_OUT, "ch09-fisher.json"), "w") as f:
        json.dump(d2, f, separators=(",", ":"))
    # ---- demo 3: naive Bayes on 8 x 8 digits
    Xtr, ytr, Xte, yte, raw = digits_binary()
    perm = np.random.default_rng(5).permutation(64)
    refs = dict(alpha={}, ntrain={}, missing={})
    for a in (0.0, 0.1, 1.0, 5.0):
        m = nb_bernoulli_fit(Xtr, ytr, a)
        refs["alpha"][str(a)] = float((nb_bernoulli_predict(m, Xte) == yte).mean())
    for n in (30, 100, 300, 1000):
        m = nb_bernoulli_fit(Xtr[:n], ytr[:n], 1.0)
        refs["ntrain"][str(n)] = float((nb_bernoulli_predict(m, Xte) == yte).mean())
    m = nb_bernoulli_fit(Xtr, ytr, 1.0)
    for k in (0, 16, 32, 48):
        obs = np.ones(64)
        obs[perm[:k]] = 0
        marg = float((nb_bernoulli_predict(m, Xte, obs) == yte).mean())
        zero = float((nb_bernoulli_predict(m, Xte * obs) == yte).mean())
        refs["missing"][str(k)] = dict(marginalise=marg, zero=zero)
    d3 = dict(train=["".join(str(int(v)) for v in r) for r in Xtr], ytrain=ytr.tolist(),
              test=["".join(str(int(v)) for v in r) for r in Xte], ytest=yte.tolist(), perm=perm.tolist(), ref=refs)
    with open(os.path.join(DATA_OUT, "ch09-digits-nb.json"), "w") as f:
        json.dump(d3, f, separators=(",", ":"))
    print("wrote", os.path.join(DATA_OUT, "ch09-*.json"))


if __name__ == "__main__":
    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()
