"""Murphy (2023), Chapter 20: Generative models: an overview.

Companion code for Chapter 20 of K. P. Murphy, Probabilistic Machine Learning: Advanced Topics
(MIT Press, 2023; December 2025 draft), pp. 773-790, written from scratch with numpy, scipy and
matplotlib (scikit-learn only draws the two-moons data and confirms my Gaussian mixture), to be read
next to the lecture notes (../ch20-generative-models-overview.html).

Methods
* Section 20.3.2 density estimation: kernel (Parzen) density estimator with uniform and Gaussian
  kernels (kde, Figure 20.5); Gaussian mixtures by EM (gmm_em).
* Section 20.4.1 likelihood: NLL, perplexity, bits per dimension (bits_per_dim), the mixture
  argument showing that log-likelihood hardly sees a bad sampler (own figure).
* Sections 20.4.2 and 20.4.3 feature-space metrics: the Inception-score identity
  log IS = H(p(y)) - E H(p(y|x)) (inception_score), the Frechet distance between Gaussians (fid),
  k-nearest-neighbour precision and recall (precision_recall), applied to raw 2-d data instead of
  the features of a pretrained network.
* An own comparison of model families on the two-moons data (own figure 20.2).

Skipped figures, with reasons: Figure 20.1 is a diagram; Table 20.1 is a table; Figures 20.2 to
20.4 are samples of very large pretrained text-to-image diffusion models; Figure 20.6 (mean
imputation) is a small table with nothing to compute; Figure 20.7 (flow-cytometry network learning)
needs the book's data set and a structure-learning code; Figures 20.8 to 20.10 (latent-space
interpolation and arithmetic with a beta-VAE on MNIST and CelebA) need a trained VAE and a face
data set, and VAEs are the subject of Chapter 21; Figure 20.11 is a schematic.

Data: simulated (seeds fixed in the code).
"""
import os
import sys

import numpy as np
from scipy import linalg, 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, logsumexp  # noqa: E402

CH = 20


# ------------------------------------------------------------------ density estimation
def kde(x, data, h, kernel="gauss"):
    """Parzen estimator p(x) = (1/N) sum_n K_h(x - x_n) for 1-d data; kernels 'gauss' and 'box'."""
    u = (np.asarray(x)[:, None] - np.asarray(data)[None, :]) / h
    if kernel == "gauss":
        k = np.exp(-0.5 * u ** 2) / np.sqrt(2 * np.pi)
    else:
        k = 0.5 * (np.abs(u) <= 1)
    return k.mean(1) / h


def kde_nd(x, data, h):
    """Gaussian KDE in d dimensions with isotropic bandwidth h: log density at the rows of x."""
    d = data.shape[1]
    sq = ((x[:, None, :] - data[None, :, :]) ** 2).sum(-1)
    return logsumexp(-0.5 * sq / h ** 2, axis=1) - np.log(len(data)) - d * np.log(h) - 0.5 * d * np.log(2 * np.pi)


def gmm_init_idx(n, K, seed=0):
    """The K data points used as initial means by gmm_em (exported so the browser demo starts identically)."""
    return np.random.default_rng(seed).choice(n, K, replace=False)


def gmm_em(X, K, n_iter=200, seed=0, reg=1e-4):
    """Gaussian mixture by EM, full covariances, k-means++-style random start. Returns (w, mu, Sigma, loglik trace)."""
    n, d = X.shape
    mu = X[gmm_init_idx(n, K, seed)].copy()
    Sig = np.array([np.cov(X.T) + reg * np.eye(d) for _ in range(K)])
    w = np.ones(K) / K
    trace = []
    for _ in range(n_iter):
        lp = np.stack([np.log(w[k]) + gmm_comp_logpdf(X, mu[k], Sig[k]) for k in range(K)], 1)
        ll = logsumexp(lp, axis=1)
        trace.append(ll.sum())
        R = np.exp(lp - ll[:, None])
        Nk = R.sum(0) + 1e-12
        w = Nk / n
        mu = (R.T @ X) / Nk[:, None]
        for k in range(K):
            D = X - mu[k]
            Sig[k] = (R[:, k, None] * D).T @ D / Nk[k] + reg * np.eye(d)
    return w, mu, Sig, np.array(trace)


def gmm_comp_logpdf(X, mu, S):
    d = X.shape[1]
    L = np.linalg.cholesky(S)
    z = np.linalg.solve(L, (X - mu).T)
    return -0.5 * (d * np.log(2 * np.pi) + 2 * np.log(np.diag(L)).sum() + (z ** 2).sum(0))


def gmm_logpdf(X, w, mu, Sig):
    return logsumexp(np.stack([np.log(w[k]) + gmm_comp_logpdf(X, mu[k], Sig[k]) for k in range(len(w))], 1), axis=1)


def gmm_sample(n, w, mu, Sig, rng):
    k = rng.choice(len(w), n, p=w)
    return np.array([rng.multivariate_normal(mu[j], Sig[j]) for j in k])


# ------------------------------------------------------------------ evaluation metrics
def bits_per_dim(nll_nats, D):
    """Bits per dimension from a total NLL in nats for a D-dimensional vector: NLL / (D ln 2)."""
    return nll_nats / (D * np.log(2.0))


def perplexity(nll_nats_per_token):
    """Perplexity 2^H with H in bits, equivalently exp of the NLL per token in nats."""
    return float(np.exp(nll_nats_per_token))


def inception_score(p_y_given_x):
    """exp E_x KL(p(y|x) || p(y)) for classifier outputs (n x C), p(y) the average; also returns the entropy identity."""
    py = p_y_given_x.mean(0)
    kl = np.sum(p_y_given_x * (np.log(p_y_given_x + 1e-300) - np.log(py + 1e-300)), axis=1)
    h_marg = -np.sum(py * np.log(py + 1e-300))
    h_cond = -np.mean(np.sum(p_y_given_x * np.log(p_y_given_x + 1e-300), axis=1))
    return float(np.exp(kl.mean())), float(h_marg), float(h_cond)


def fid(mu1, S1, mu2, S2):
    """Frechet distance |mu1-mu2|^2 + tr(S1 + S2 - 2 (S1 S2)^{1/2}) between two Gaussians."""
    mu1, mu2 = np.atleast_1d(mu1), np.atleast_1d(mu2)
    S1, S2 = np.atleast_2d(S1), np.atleast_2d(S2)
    covmean = linalg.sqrtm(S1 @ S2)
    covmean = covmean.real
    return float(np.sum((mu1 - mu2) ** 2) + np.trace(S1 + S2 - 2 * covmean))


def fid_samples(A, B):
    return fid(A.mean(0), np.cov(A.T), B.mean(0), np.cov(B.T))


def knn_radii(F, k):
    """Distance from each row of F to its k-th nearest neighbour in F (excluding itself)."""
    D = np.sqrt(((F[:, None, :] - F[None, :, :]) ** 2).sum(-1))
    D.sort(axis=1)
    return D[:, k]


def precision_recall(real, fake, k=3):
    """k-NN manifold precision and recall: precision = fraction of fake points inside the k-NN ball of some real
    point; recall = fraction of real points inside the k-NN ball of some fake point."""
    rr, rf = knn_radii(real, k), knn_radii(fake, k)
    Dfr = np.sqrt(((fake[:, None, :] - real[None, :, :]) ** 2).sum(-1))
    prec = np.mean((Dfr <= rr[None, :]).any(1))
    Drf = Dfr.T
    rec = np.mean((Drf <= rf[None, :]).any(1))
    return float(prec), float(rec)


# ------------------------------------------------------------------ data and the model-family comparison
def moons(n, noise=0.08, seed=0):
    from sklearn.datasets import make_moons
    X, _ = make_moons(n, noise=noise, random_state=seed)
    return X


def compare_families(seed=0, n=500):
    """Fit KDE and GMM models of several complexities to two moons; return rows of metrics and samples."""
    rng = np.random.default_rng(seed)
    Xtr, Xte = moons(n, seed=seed), moons(n, seed=seed + 100)
    rows, samples = [], {}
    specs = [("single Gaussian", "gmm", 1), ("GMM, K = 2", "gmm", 2), ("GMM, K = 10", "gmm", 10),
             ("KDE, h = 0.5", "kde", 0.5), ("KDE, h = 0.1", "kde", 0.1), ("KDE, h = 0.01", "kde", 0.01)]
    for name, kind, par in specs:
        if kind == "gmm":
            w, mu, Sig, _ = gmm_em(Xtr, par, seed=seed)
            nll = -gmm_logpdf(Xte, w, mu, Sig).mean()
            S = gmm_sample(n, w, mu, Sig, rng)
        else:
            nll = -kde_nd(Xte, Xtr, par).mean()
            S = Xtr[rng.integers(0, n, n)] + par * rng.standard_normal((n, 2))
        p, r = precision_recall(Xte, S, 3)
        rows.append((name, nll, fid_samples(S, Xte), p, r))
        samples[name] = S
    return Xtr, Xte, rows, samples


# ------------------------------------------------------------------ figures
def fig_20_5(out=None):
    """Figure 20.5: Parzen estimators of 6 points with uniform and Gaussian kernels, h = 1 and h = 2."""
    data = np.array([-2.1, -1.3, -0.4, 1.9, 5.1, 6.2])
    x = np.linspace(-8, 12, 1000)
    fig, ax = plt.subplots(2, 2, figsize=(7.6, 5.0), sharex=True, sharey=True)
    for i, kern in enumerate(("box", "gauss")):
        for j, h in enumerate((1.0, 2.0)):
            a = ax[i, j]
            if kern == "gauss":
                for xn in data:
                    a.plot(x, stats.norm.pdf(x, xn, h) / len(data), color=GREY, lw=0.7)
            else:
                for xn in data:
                    a.plot(x, 0.5 * (np.abs(x - xn) <= h) / h / len(data), color=GREY, lw=0.7)
            a.plot(x, kde(x, data, h, kern), color=BLUE, lw=1.6)
            a.plot(data, np.zeros_like(data), "x", color=RED, ms=6)
            a.set_title("%s kernel, $h=%d$" % ("uniform" if kern == "box" else "Gaussian", h), fontsize=9.5)
    for a in ax[1]:
        a.set_xlabel("$x$")
    fig.tight_layout()
    savefig(fig, CH, "fig20-5", out)


def fig_own_20_1(out=None):
    """Own figure: log-likelihood barely changes when 99% of the samples are noise (Theis et al.'s argument)."""
    Ds = np.array([1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 3000])
    rng = np.random.default_rng(0)
    gap = []
    for D in Ds:
        # q0 = N(0, 0.1^2 I) fits the data x ~ q0, q1 = N(0, I) is a bad (diffuse) model
        x = 0.1 * rng.standard_normal((2000, D))
        lq0 = stats.norm.logpdf(x, 0, 0.1).sum(1)
        lq1 = stats.norm.logpdf(x, 0, 1.0).sum(1)
        lq2 = np.logaddexp(np.log(0.01) + lq0, np.log(0.99) + lq1)
        gap.append((lq0 - lq2).mean() / D)
    fig, ax = plt.subplots(1, 2, figsize=(7.8, 2.8))
    ax[0].semilogx(Ds, gap, "o-", color=BLUE)
    ax[0].axhline(0, color="k", lw=0.8)
    ax[0].set_xlabel("dimension $D$"); ax[0].set_ylabel("loss in log-lik. per dimension (nats)")
    ax[0].set_title("(a) $\\log q_0 - \\log q_2$, per dimension", fontsize=9.5)
    ax[1].semilogx(Ds, np.array(gap) * Ds, "o-", color=RED, label="total loss $\\log q_0-\\log q_2$")
    ax[1].axhline(np.log(100), color="k", ls="--", lw=1, label="bound $\\log 100$")
    ax[1].set_xlabel("dimension $D$"); ax[1].legend(fontsize=8)
    ax[1].set_title("(b) the total loss never exceeds $\\log 100$", fontsize=9.5)
    fig.tight_layout()
    savefig(fig, CH, "own20-1", out)


def fig_own_20_2(out=None):
    """Own figure: six density models of the two-moons data, with test NLL, FID, precision and recall."""
    Xtr, Xte, rows, samples = compare_families()
    fig, ax = plt.subplots(2, 3, figsize=(9.6, 6.1), sharex=True, sharey=True)
    for a, (name, nll, f, p, r) in zip(ax.ravel(), rows):
        a.plot(Xte[:, 0], Xte[:, 1], ".", color=GREY, ms=3, alpha=0.5)
        S = samples[name]
        a.plot(S[:, 0], S[:, 1], ".", color=RED, ms=3, alpha=0.7)
        a.set_title("%s\ntest NLL %.2f, FID %.3f\nprecision %.2f, recall %.2f" % (name, nll, f, p, r), fontsize=8.5)
    fig.tight_layout()
    savefig(fig, CH, "own20-2", out)


def blobs(n, seed=0):
    """Three Gaussian clusters with standard deviation 0.6."""
    rng = np.random.default_rng(seed)
    cen = np.array([[-2.0, -1.0], [2.0, -1.0], [0.0, 2.0]])
    return cen[rng.integers(0, 3, n)] + 0.6 * rng.standard_normal((n, 2))


def export_demo_data():
    """Small JSON for the browser demo: 400 train and 400 test points of two data sets, and the EM start points."""
    import json
    out = {"moons": {}, "blobs": {}, "init": {}}
    for name, f in (("moons", lambda n, sd: moons(n, seed=sd)), ("blobs", lambda n, sd: blobs(n, seed=sd))):
        tr, te = np.round(f(400, 7), 4), np.round(f(400, 8), 4)
        out[name] = {"train": tr.tolist(), "test": te.tolist()}
        out["init"][name] = {str(K): gmm_init_idx(400, K).tolist() for K in range(1, 13)}
    path = os.path.normpath(os.path.join(os.path.dirname(os.path.abspath(__file__)), "..", "data", "ch20-gen-eval.json"))
    os.makedirs(os.path.dirname(path), exist_ok=True)
    with open(path, "w") as fh:
        json.dump(out, fh, separators=(",", ":"))
    print("wrote", path)


FIGURES = {"20.5": fig_20_5, "own20.1": fig_own_20_1, "own20.2": fig_own_20_2}

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