"""Bishop and Bishop (2024), Chapter 3: Standard Distributions.

Reproduces the figures of Chapter 3 of C. M. Bishop and H. Bishop, Deep Learning: Foundations and
Concepts (Springer, 2024), pp. 65-110, written from scratch with numpy, scipy and matplotlib.
Every algorithm is a small function meant to be read next to the lecture notes
(../ch03-standard-distributions.html):

* Section 3.1, discrete variables: bernoulli_ml, binomial_pmf, multinomial_ml (3.1)-(3.24).
* Section 3.2, the multivariate Gaussian: gauss_pdf, eigen_geometry (3.28)-(3.40),
  partitioned_inverse (3.60)-(3.61), conditional_gaussian (both the precision form (3.57), (3.59)
  and the covariance form (3.65), (3.66)), marginal_gaussian (3.76)-(3.77), linear_gaussian
  ((3.83)-(3.101): the joint, the marginal p(y) and the posterior p(x|y)), gaussian_ml
  ((3.105), (3.106), (3.109)), sequential_mean (3.110), gmm_logpdf, responsibilities (3.115) and
  gmm_em (the maximum likelihood mixture of Figure 3.6(b), found by expectation maximization).
* Section 3.3, periodic variables: circular_mean (3.117)-(3.119), vonmises_pdf (3.129),
  bessel_ratio A(m) (3.136), inverse_bessel_ratio (Newton's method for A(m) = r), vonmises_ml
  ((3.134), (3.135)) and vonmises_sample (the Best and Fisher (1979) rejection sampler).
* Section 3.4, the exponential family: EXPFAM (Bernoulli, Gaussian mean, Gaussian precision and
  von Mises concentration, each with natural parameter eta, sufficient statistic u(x) and
  psi(eta) = -ln g(eta)), expfam_ml_newton (the moment-matching equation (3.174) solved by Newton's
  method), softmax_params (3.157).
* Section 3.5, nonparametric methods: histogram_density (3.175), kde (3.183)-(3.184),
  knn_density (3.180) and knn_classify (3.190).
* JSRandom: the seeded generator DK.rng of the browser demos (mulberry32 uniforms and Box-Muller
  normals). The von Mises samples and data sets of the demos use only these numbers, so
  von-mises-demo.html, exponential-family-demo.html and gaussian-partition-demo.html reproduce
  the Python numbers digit for digit.

Figures: all sixteen figures of the chapter, 3.1 to 3.16. Figures 3.3, 3.9 and 3.10 are
explanatory sketches in the book; here they are drawn from an actual Gaussian, an actual set of
angles and an actual isotropic Gaussian, so they are computed rather than copied. Run
`python3 ch03_standard_distributions.py --list`, `python3 ch03_standard_distributions.py`
(all figures, under a minute) or `python3 ch03_standard_distributions.py --fig 3.5 3.11`.
Files go to ../img/ch03/.

Settings chosen where the book gives none (the book's own numbers are used where it states them):
* Figure 3.1: N = 10, mu = 0.25, as stated.
* Figure 3.2: 200000 draws of the mean of N uniforms on [0, 1] for N = 1, 2, 10 (numpy seed 2).
* Figures 3.3 and 3.4: mu = (0, 0); general Sigma = [[1.2, 0.7], [0.7, 0.8]]; the diagonal and
  isotropic cases keep the diagonal of Sigma and its mean variance.
* Figure 3.5: mu = (0.5, 0.55), standard deviations 0.15 and 0.12, correlation 0.85, x_b = 0.7.
* Figure 3.6: the 272 Old Faithful eruptions (common.old_faithful()); panel (b) is the maximum
  likelihood two-component mixture with full covariances, found by EM from a k-means start.
* Figures 3.7 and 3.8: mixtures chosen to look like the book's (parameters in MIX1D and MIX2D).
* Figure 3.9: four angles 0.35, 0.75, 1.2 and 1.85 radians.
* Figure 3.10: an isotropic Gaussian with mean (1.2, 1.2) and sigma = 0.35.
* Figure 3.11: m = 5, theta_0 = pi/4 and m = 1, theta_0 = 3 pi/4, as stated.
* Figures 3.13-3.15: N = 50 points (numpy seed 3) from 0.3 N(0.3, 0.06^2) + 0.7 N(0.75, 0.08^2)
  restricted to [0, 1]; the smoothing parameters are the book's (Delta = 0.04, 0.08, 0.25;
  h = 0.005, 0.07, 0.2; K = 1, 5, 30).
* Figure 3.16: 14 red and 14 blue points (numpy seed 16) in the unit square.
"""
import math
import os
import sys

import numpy as np
from scipy import special

sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
import common  # noqa: E402
import matplotlib.pyplot as plt  # noqa: E402

CH = 3
M32 = 0xFFFFFFFF


# =========================================================================== the demos' generator
def _imul(a, b):
    return (a * b) & M32


class JSRandom:
    """The seeded random numbers of the browser demos (DK.rng in courses/demo-kit.js).

    u() is the mulberry32 generator on 32-bit unsigned integers; norm() is the basic Box-Muller
    transform that caches the second normal of each pair, exactly as the JavaScript does.
    """

    def __init__(self, seed):
        self.a = int(seed) & M32
        self.spare = None

    def u(self):
        a = (self.a + 0x6D2B79F5) & M32
        self.a = a
        t = _imul(a ^ (a >> 15), 1 | a)
        t = ((t + _imul(t ^ (t >> 7), 61 | t)) & M32) ^ t
        return ((t ^ (t >> 14)) & M32) / 4294967296.0

    def _pos(self):
        x = 0.0
        while x == 0.0:
            x = self.u()
        return x

    def norm(self):
        if self.spare is not None:
            s, self.spare = self.spare, None
            return s
        r = math.sqrt(-2.0 * math.log(self._pos()))
        th = 2.0 * math.pi * self.u()
        self.spare = r * math.sin(th)
        return r * math.cos(th)


# =========================================================================== 3.1 discrete variables
def bernoulli_ml(x):
    """(3.7): the maximum likelihood estimate is the sample mean (the fraction of ones)."""
    return float(np.mean(x))


def binomial_pmf(m, N, mu):
    """Bin(m | N, mu) of (3.9)-(3.10)."""
    m = np.asarray(m)
    return special.comb(N, m) * mu ** m * (1 - mu) ** (N - m)


def multinomial_ml(X):
    """(3.18), (3.22): counts m_k of the one-hot rows of X and mu_k = m_k / N."""
    X = np.asarray(X, dtype=float)
    m = X.sum(0)
    return m / X.shape[0], m


def multinomial_pmf(m, mu):
    """Mult(m_1, ..., m_K | mu, N) of (3.23)-(3.24)."""
    m = np.asarray(m)
    N = int(m.sum())
    logc = special.gammaln(N + 1) - special.gammaln(m + 1).sum()
    return float(np.exp(logc + (m * np.log(mu)).sum()))


# =========================================================================== 3.2 the Gaussian
def gauss_pdf(X, mu, Sigma):
    """N(x | mu, Sigma) of (3.26) for each row of X."""
    return np.exp(common.gauss_logpdf(np.atleast_2d(X), np.asarray(mu, float), np.asarray(Sigma, float)))


def eigen_geometry(Sigma):
    """(3.28)-(3.35): eigenvalues lambda_i (ascending) and the matrix U whose rows are u_i^T."""
    lam, V = np.linalg.eigh(Sigma)
    return lam, V.T


def mahalanobis2(X, mu, Sigma):
    """The squared Mahalanobis distance Delta^2 of (3.27) for each row of X."""
    D = np.atleast_2d(X) - mu
    return np.einsum("ni,ij,nj->n", D, np.linalg.inv(Sigma), D)


def partitioned_inverse(A, B, C, D):
    """(3.60)-(3.61): the inverse of [[A, B], [C, D]] through the Schur complement M = (A - B D^-1 C)^-1."""
    Di = np.linalg.inv(D)
    M = np.linalg.inv(A - B @ Di @ C)
    return np.block([[M, -M @ B @ Di], [-Di @ C @ M, Di + Di @ C @ M @ B @ Di]])


def conditional_gaussian(mu, Sigma, ia, xb, form="covariance"):
    """Mean and covariance of p(x_a | x_b) for x ~ N(mu, Sigma); ia lists the indices of x_a.

    form='covariance' uses (3.65)-(3.66); form='precision' uses (3.57) and (3.59).
    """
    mu = np.asarray(mu, float)
    Sigma = np.asarray(Sigma, float)
    ia = np.asarray(ia)
    ib = np.setdiff1d(np.arange(len(mu)), ia)
    xb = np.asarray(xb, float)
    if form == "covariance":
        Saa, Sab, Sbb = Sigma[np.ix_(ia, ia)], Sigma[np.ix_(ia, ib)], Sigma[np.ix_(ib, ib)]
        K = Sab @ np.linalg.inv(Sbb)
        return mu[ia] + K @ (xb - mu[ib]), Saa - K @ Sab.T
    Lam = np.linalg.inv(Sigma)
    Laa, Lab = Lam[np.ix_(ia, ia)], Lam[np.ix_(ia, ib)]
    C = np.linalg.inv(Laa)
    return mu[ia] - C @ Lab @ (xb - mu[ib]), C


def marginal_gaussian(mu, Sigma, ia):
    """(3.76)-(3.77): p(x_a) = N(mu_a, Sigma_aa)."""
    ia = np.asarray(ia)
    return np.asarray(mu, float)[ia], np.asarray(Sigma, float)[np.ix_(ia, ia)]


def linear_gaussian(mu, Lam, A, b, L):
    """The linear-Gaussian model p(x) = N(mu, Lam^-1), p(y|x) = N(Ax + b, L^-1), (3.83)-(3.101).

    Returns a dict with the joint precision R (3.88), the joint covariance (3.89) and mean (3.92),
    the marginal of y (3.93)-(3.94) and a function post(y) giving the mean and covariance of
    p(x | y) from (3.100)-(3.101).
    """
    mu, Lam, A, b, L = (np.atleast_1d(np.asarray(v, float)) for v in (mu, Lam, A, b, L))
    Lam, A, L = np.atleast_2d(Lam), np.atleast_2d(A), np.atleast_2d(L)
    Li, Lami = np.linalg.inv(L), np.linalg.inv(Lam)
    R = np.block([[Lam + A.T @ L @ A, -A.T @ L], [-L @ A, L]])
    cov = np.block([[Lami, Lami @ A.T], [A @ Lami, Li + A @ Lami @ A.T]])
    mean = np.concatenate([mu, A @ mu + b])
    S = np.linalg.inv(Lam + A.T @ L @ A)

    def post(y):
        return S @ (A.T @ L @ (np.atleast_1d(y) - b) + Lam @ mu), S

    return {"R": R, "cov": cov, "mean": mean, "y_mean": A @ mu + b, "y_cov": Li + A @ Lami @ A.T,
            "post": post, "S": S}


def gaussian_ml(X, unbiased=False):
    """(3.105)-(3.106), or the bias-corrected (3.109) with unbiased=True."""
    X = np.asarray(X, float)
    mu = X.mean(0)
    D = X - mu
    return mu, D.T @ D / (len(X) - (1 if unbiased else 0))


def sequential_mean(X):
    """(3.110): mu^(N) = mu^(N-1) + (x_N - mu^(N-1)) / N; returns every intermediate estimate."""
    X = np.atleast_2d(np.asarray(X, float))
    if X.shape[0] == 1:
        X = X.T
    out = np.zeros_like(X)
    m = np.zeros(X.shape[1])
    for n, x in enumerate(X, start=1):
        m = m + (x - m) / n
        out[n - 1] = m
    return out


def gmm_logpdf(X, pi, mus, Sigmas):
    """ln of the mixture (3.111) for each row of X."""
    X = np.atleast_2d(X)
    L = np.stack([math.log(p) + common.gauss_logpdf(X, m, S) for p, m, S in zip(pi, mus, Sigmas)], 1)
    return common.logsumexp(L, axis=1)


def responsibilities(X, pi, mus, Sigmas):
    """gamma_k(x) = p(k | x) of (3.115), one row per data point."""
    X = np.atleast_2d(X)
    L = np.stack([math.log(p) + common.gauss_logpdf(X, m, S) for p, m, S in zip(pi, mus, Sigmas)], 1)
    return np.exp(L - common.logsumexp(L, axis=1, keepdims=True))


def gmm_em(X, K, iters=300, seed=0, tol=1e-10):
    """Maximum likelihood for the mixture (3.116) by expectation maximization (Chapter 15).

    Starts from a few k-means iterations; returns pi, mus, Sigmas and the log likelihood after
    every iteration (which never decreases).
    """
    X = np.asarray(X, float)
    N, D = X.shape
    rng = np.random.default_rng(seed)
    C = X[rng.choice(N, K, replace=False)]
    for _ in range(20):
        z = np.argmin(((X[:, None, :] - C[None]) ** 2).sum(-1), 1)
        C = np.array([X[z == k].mean(0) if np.any(z == k) else C[k] for k in range(K)])
    pi = np.array([np.mean(z == k) for k in range(K)])
    mus = list(C)
    Sigmas = [np.cov(X[z == k].T, bias=True) + 1e-6 * np.eye(D) for k in range(K)]
    ll = []
    for _ in range(iters):
        G = responsibilities(X, pi, mus, Sigmas)
        Nk = G.sum(0)
        pi = Nk / N
        mus = [G[:, k] @ X / Nk[k] for k in range(K)]
        Sigmas = [((X - mus[k]).T * G[:, k]) @ (X - mus[k]) / Nk[k] for k in range(K)]
        ll.append(float(gmm_logpdf(X, pi, mus, Sigmas).sum()))
        if len(ll) > 1 and ll[-1] - ll[-2] < tol:
            break
    return pi, mus, Sigmas, np.array(ll)


# =========================================================================== 3.3 periodic variables
def circular_mean(theta):
    """(3.117)-(3.119): the angle and the length r of the mean of the unit vectors (cos, sin)."""
    c, s = np.mean(np.cos(theta)), np.mean(np.sin(theta))
    return math.atan2(s, c) % (2 * math.pi), math.hypot(c, s)


def vonmises_pdf(theta, theta0, m):
    """(3.129) with I0 from (3.130); i0e(m) = exp(-m) I0(m) keeps large m stable."""
    theta = np.asarray(theta, float)
    return np.exp(m * (np.cos(theta - theta0) - 1)) / (2 * math.pi * special.i0e(m))


def bessel_ratio(m):
    """A(m) = I1(m) / I0(m) of (3.136)."""
    return special.i1e(m) / special.i0e(m)


def inverse_bessel_ratio(r, iters=60):
    """Solve A(m) = r for m >= 0 (0 <= r < 1) by Newton's method; A'(m) = 1 - A/m - A^2."""
    if r <= 0:
        return 0.0
    # a standard starting value (Best and Fisher's approximation), then Newton
    m = r * (2 - r * r) / (1 - r * r)
    for _ in range(iters):
        A = bessel_ratio(m)
        dA = 1 - A / m - A * A
        step = (A - r) / dA
        m = max(m - step, m / 10)
        if abs(step) < 1e-14 * max(1.0, m):
            break
    return float(m)


def vonmises_ml(theta):
    """(3.134)-(3.135): theta0_ML is the circular mean and m_ML solves A(m) = r (Exercise 3.34)."""
    t0, r = circular_mean(theta)
    return t0, inverse_bessel_ratio(r), r


def vonmises_sample(n, theta0, m, rng):
    """n draws from the von Mises distribution by Best and Fisher's (1979) wrapped-Cauchy rejection.

    rng is a JSRandom (or any object with u()); the browser demo runs the same steps.
    Returns angles in [0, 2 pi).
    """
    out = []
    if m < 1e-8:
        return np.array([(2 * math.pi * rng.u()) % (2 * math.pi) for _ in range(n)])
    s = 0.5 / m
    r = s + math.sqrt(1 + s * s)
    while len(out) < n:
        z = math.cos(math.pi * rng.u())
        W = (1 + r * z) / (r + z)
        y = m * (r - W)
        V = rng.u()
        if y * (2 - y) - V >= 0 or (V > 0 and y > 0 and math.log(y / V) + 1 - y >= 0):
            a = math.acos(max(-1.0, min(1.0, W)))
            if rng.u() < 0.5:
                a = -a
            out.append((theta0 + a) % (2 * math.pi))
    return np.array(out)


# =========================================================================== 3.4 exponential family
# Each family: eta -> psi(eta) = -ln g(eta) (up to a constant), its first two derivatives
# (= E[u] and var[u] by (3.172) and (3.218)), and u(x).
def _vm_psi(e):
    return math.log(special.i0e(abs(e))) + abs(e)


EXPFAM = {
    "bernoulli": {  # (3.141)-(3.147): u = x, g = sigma(-eta)
        "psi": lambda e: math.log1p(math.exp(-abs(e))) + max(e, 0.0),
        "d1": lambda e: float(common.sigmoid(e)),
        "d2": lambda e: float(common.sigmoid(e) * (1 - common.sigmoid(e))),
        "u": lambda x: np.asarray(x, float),
    },
    "gauss_mean": {  # N(x | eta, 1): u = x, psi = eta^2 / 2
        "psi": lambda e: 0.5 * e * e,
        "d1": lambda e: e,
        "d2": lambda e: 1.0,
        "u": lambda x: np.asarray(x, float),
    },
    "gauss_precision": {  # N(x | 0, sigma^2) with eta = -1/(2 sigma^2) < 0, u = x^2, psi = -ln(-2 eta)/2
        "psi": lambda e: -0.5 * math.log(-2 * e),
        "d1": lambda e: -0.5 / e,
        "d2": lambda e: 0.5 / (e * e),
        "u": lambda x: np.asarray(x, float) ** 2,
    },
    "vonmises": {  # concentration with theta0 = 0 known: eta = m, u = cos(theta), psi = ln I0(eta)
        "psi": _vm_psi,
        "d1": lambda e: math.copysign(float(bessel_ratio(abs(e))), e),
        "d2": lambda e: 1 - float(bessel_ratio(abs(e))) / abs(e) - float(bessel_ratio(abs(e))) ** 2 if abs(e) > 1e-8 else 0.5,
        "u": lambda x: np.cos(np.asarray(x, float)),
    },
}


def expfam_ml_newton(family, ubar, eta0, steps=8):
    """Newton's method for the moment-matching equation psi'(eta) = ubar, i.e. (3.174).

    The log likelihood per point is eta ubar - psi(eta), concave because psi'' = var[u] > 0, so
    Newton's step eta <- eta + (ubar - psi'(eta)) / psi''(eta) is the ML update. Returns the iterates.
    For the Gaussian precision the step is damped to keep eta < 0.
    """
    F = EXPFAM[family]
    path = [float(eta0)]
    e = float(eta0)
    for _ in range(steps):
        new = e + (ubar - F["d1"](e)) / F["d2"](e)
        if family == "gauss_precision" and new >= 0:
            new = e / 2
        e = new
        path.append(e)
    return path


def softmax_params(eta):
    """(3.157): mu_k = exp(eta_k) / (1 + sum_j exp(eta_j)) for the K - 1 free parameters; adds mu_K."""
    eta = np.asarray(eta, float)
    den = 1 + np.exp(eta).sum()
    return np.append(np.exp(eta) / den, 1 / den)


def expfam_demo_data(family, eta, N, seed):
    """The data of exponential-family-demo.html: N draws with natural parameter eta from JSRandom(seed)."""
    rng = JSRandom(seed)
    if family == "bernoulli":
        mu = float(common.sigmoid(eta))
        return np.array([1.0 if rng.u() < mu else 0.0 for _ in range(N)])
    if family == "gauss_mean":
        return np.array([eta + rng.norm() for _ in range(N)])
    if family == "gauss_precision":
        sd = math.sqrt(-0.5 / eta)
        return np.array([sd * rng.norm() for _ in range(N)])
    return vonmises_sample(N, 0.0, eta, rng)


def gauss_demo_sample(mu, Sigma, N, seed):
    """The samples of gaussian-partition-demo.html: x = mu + L z with L the Cholesky factor of Sigma and
    z = (z1, z2) two successive JSRandom normals."""
    rng = JSRandom(seed)
    L = np.linalg.cholesky(np.asarray(Sigma, float))
    Z = np.array([[rng.norm(), rng.norm()] for _ in range(N)])
    return np.asarray(mu, float) + Z @ L.T


# =========================================================================== 3.5 nonparametric methods
MIXD_W = np.array([0.3, 0.7])
MIXD_MU = np.array([0.3, 0.75])
MIXD_SD = np.array([0.06, 0.08])


def density_mixture_pdf(x):
    """The green curve of Figures 3.13-3.15 (a two-Gaussian mixture; its mass outside [0, 1] is negligible)."""
    x = np.asarray(x, float)
    return sum(w * np.exp(-0.5 * ((x - m) / s) ** 2) / (s * math.sqrt(2 * math.pi))
               for w, m, s in zip(MIXD_W, MIXD_MU, MIXD_SD))


def density_data(N=50, seed=3):
    rng = np.random.default_rng(seed)
    out = []
    while len(out) < N:
        k = rng.choice(2, p=MIXD_W)
        v = rng.normal(MIXD_MU[k], MIXD_SD[k])
        if 0 <= v <= 1:
            out.append(v)
    return np.array(out)


def histogram_density(x, delta, lo=0.0, hi=1.0):
    """(3.175): p_i = n_i / (N Delta) on bins of width delta starting at lo; returns edges and heights."""
    nb = int(round((hi - lo) / delta))
    edges = lo + delta * np.arange(nb + 1)
    n, _ = np.histogram(x, edges)
    return edges, n / (len(x) * delta)


def kde(xq, x, h, kernel="gauss"):
    """(3.183) with the Gaussian kernel (3.184) or the unit-cube Parzen window (3.181); 1-D or D-D."""
    xq = np.atleast_2d(np.asarray(xq, float).T).T
    x = np.atleast_2d(np.asarray(x, float).T).T
    D = x.shape[1]
    U = (xq[:, None, :] - x[None, :, :]) / h
    if kernel == "gauss":
        k = np.exp(-0.5 * (U ** 2).sum(-1)) / (2 * math.pi) ** (D / 2)
    else:
        k = np.all(np.abs(U) <= 0.5, axis=-1).astype(float)
    return k.mean(1) / h ** D


def knn_density(xq, x, K):
    """(3.180) with V the volume of the smallest sphere around x holding K points (1-D: V = 2 r)."""
    xq = np.atleast_2d(np.asarray(xq, float).T).T
    x = np.atleast_2d(np.asarray(x, float).T).T
    D = x.shape[1]
    d = np.sqrt(((xq[:, None, :] - x[None, :, :]) ** 2).sum(-1))
    rK = np.sort(d, 1)[:, K - 1]
    VD = math.pi ** (D / 2) / math.gamma(D / 2 + 1)
    return K / (len(x) * VD * rK ** D)


def knn_classify(xq, X, y, K, nclass=2):
    """(3.190): p(C_k | x) = K_k / K over the K nearest training points; returns posteriors and labels."""
    xq = np.atleast_2d(xq)
    d = ((xq[:, None, :] - X[None]) ** 2).sum(-1)
    idx = np.argsort(d, 1, kind="stable")[:, :K]
    P = np.stack([(y[idx] == c).mean(1) for c in range(nclass)], 1)
    return P, np.argmax(P, 1)


def knn_class_data(seed=16, n=14):
    rng = np.random.default_rng(seed)
    red = rng.normal([0.32, 0.62], 0.17, size=(n, 2))
    blue = rng.normal([0.66, 0.36], 0.17, size=(n, 2))
    X = np.clip(np.vstack([red, blue]), 0.03, 0.97)
    return X, np.r_[np.zeros(n, int), np.ones(n, int)]


# =========================================================================== figures
def _box(ax):
    ax.set_xticks([])
    ax.set_yticks([])


def fig3_1(out_dir=None):
    """Figure 3.1: the binomial distribution Bin(m | N = 10, mu = 0.25)."""
    m = np.arange(11)
    fig, ax = plt.subplots(figsize=(4.0, 2.8))
    ax.bar(m, binomial_pmf(m, 10, 0.25), width=0.8, color=common.BLUE, edgecolor="k", lw=0.6)
    ax.set_xticks(m)
    ax.set_xlabel("$m$")
    ax.set_ylim(0, 0.32)
    ax.set_yticks([0, 0.1, 0.2, 0.3])
    common.savefig(fig, CH, "fig3-1", out_dir)


def fig3_2(out_dir=None):
    """Figure 3.2: histograms of the mean of N uniform numbers for N = 1, 2, 10 (central limit theorem)."""
    rng = np.random.default_rng(2)
    fig, axes = common.panel_grid(1, 3, size=(2.5, 2.2))
    for ax, N in zip(axes[0], (1, 2, 10)):
        x = rng.random((200000, N)).mean(1)
        ax.hist(x, bins=np.linspace(0, 1, 41), density=True, color=common.BLUE, edgecolor="white", lw=0.3)
        t = np.linspace(0, 1, 300)
        if N == 10:
            ax.plot(t, np.exp(-0.5 * (t - 0.5) ** 2 * 12 * N) * math.sqrt(12 * N / (2 * math.pi)), color=common.RED, lw=1.3)
        ax.set_xlim(0, 1)
        ax.set_ylim(0, 3.6)
        ax.set_xticks([0, 0.5, 1])
        ax.set_yticks([0, 1, 2, 3])
        ax.set_title("$N = %d$" % N)
    common.savefig(fig, CH, "fig3-2", out_dir)


SIG_GENERAL = np.array([[1.2, 0.7], [0.7, 0.8]])


def fig3_3(out_dir=None):
    """Figure 3.3: the exp(-1/2) contour of a 2-D Gaussian, its eigenvectors and axis lengths sqrt(lambda_i)."""
    mu = np.array([0.0, 0.0])
    lam, U = eigen_geometry(SIG_GENERAL)
    fig, ax = plt.subplots(figsize=(4.0, 3.4))
    x, y = common.ellipse_xy(mu, SIG_GENERAL, 1.0)
    ax.plot(x, y, color=common.RED, lw=1.8)
    order = [1, 0]  # u1 = the long axis, as in the book
    for i, k in enumerate(order):
        u = U[k]
        if (i == 0 and u[0] < 0) or (i == 1 and u[1] < 0):
            u = -u
        L = math.sqrt(lam[k])
        ax.annotate("", xy=mu + 2.0 * u, xytext=mu - 2.0 * u, arrowprops=dict(arrowstyle="->", color=common.GREY, lw=0.9))
        ax.text(*(mu + 2.05 * u + np.array([0.05, 0.02])), "$y_%d$" % (i + 1), fontsize=10)
        ax.annotate("", xy=mu + L * u, xytext=mu, arrowprops=dict(arrowstyle="<->", color=common.BLUE, lw=1.4))
        off = np.array([-u[1], u[0]]) * (0.2 if i == 0 else 0.28)
        ax.text(*(mu + 0.5 * L * u + off), r"$\lambda_%d^{1/2}$" % (i + 1), color=common.BLUE, ha="center", va="center", fontsize=10)
        ax.annotate("", xy=mu + 0.45 * u + np.array([1.6, -1.1]), xytext=np.array([1.6, -1.1]),
                    arrowprops=dict(arrowstyle="->", color="k", lw=1.0))
        ax.text(*(np.array([1.6, -1.1]) + 0.55 * u), "$\\mathbf{u}_%d$" % (i + 1), fontsize=10)
    ax.plot(*mu, "k.", ms=5)
    ax.text(mu[0] + 0.1, mu[1] - 0.3, r"$\boldsymbol{\mu}$", fontsize=11)
    ax.set_xlim(-2.3, 2.6)
    ax.set_ylim(-1.9, 1.9)
    ax.set_aspect("equal")
    ax.set_xlabel("$x_1$")
    ax.set_ylabel("$x_2$")
    _box(ax)
    common.savefig(fig, CH, "fig3-3", out_dir)


def fig3_4(out_dir=None):
    """Figure 3.4: contours for a general, a diagonal and an isotropic covariance matrix."""
    S = SIG_GENERAL
    cases = [S, np.diag(np.diag(S)), np.eye(2) * np.trace(S) / 2]
    fig, axes = common.panel_grid(1, 3, size=(2.3, 2.3))
    g = np.linspace(-3, 3, 161)
    GX, GY = np.meshgrid(g, g)
    P = np.c_[GX.ravel(), GY.ravel()]
    for ax, C, lab in zip(axes[0], cases, "abc"):
        Z = gauss_pdf(P, [0, 0], C).reshape(GX.shape)
        ax.contour(GX, GY, Z, levels=np.max(Z) * np.exp(-0.5 * np.array([2.5, 1.6, 1.0, 0.5, 0.15]) ** 2), colors=common.RED, linewidths=1.1)
        ax.set_aspect("equal")
        _box(ax)
        ax.set_xlabel("$x_1$")
        ax.set_ylabel("$x_2$")
        ax.set_title("(%s)" % lab)
    common.savefig(fig, CH, "fig3-4", out_dir)


FIG5_MU = np.array([0.5, 0.55])
FIG5_SD = np.array([0.15, 0.12])
FIG5_RHO = 0.85
FIG5_XB = 0.7


def fig5_sigma():
    s = FIG5_SD
    return np.array([[s[0] ** 2, FIG5_RHO * s[0] * s[1]], [FIG5_RHO * s[0] * s[1], s[1] ** 2]])


def fig3_5(out_dir=None):
    """Figure 3.5: contours of p(x_a, x_b), the marginal p(x_a) and the conditional p(x_a | x_b = 0.7)."""
    mu, S = FIG5_MU, fig5_sigma()
    fig, axes = common.panel_grid(1, 2, size=(3.3, 3.0))
    ax = axes[0, 0]
    g = np.linspace(0, 1, 201)
    GX, GY = np.meshgrid(g, g)
    Z = gauss_pdf(np.c_[GX.ravel(), GY.ravel()], mu, S).reshape(GX.shape)
    ax.contour(GX, GY, Z, levels=np.max(Z) * np.exp(-0.5 * np.array([2.0, 1.5, 1.0, 0.5]) ** 2), colors=common.GREEN, linewidths=1.1)
    ax.axhline(FIG5_XB, color=common.RED, lw=1.2)
    ax.text(0.04, FIG5_XB + 0.03, "$x_b = %.1f$" % FIG5_XB, color=common.RED)
    ax.text(0.62, 0.15, "$p(x_a, x_b)$", color=common.GREEN)
    ax.set_xlim(0, 1)
    ax.set_ylim(0, 1)
    ax.set_xticks([0, 0.5, 1])
    ax.set_yticks([0, 0.5, 1])
    ax.set_xlabel("$x_a$")
    ax.set_ylabel("$x_b$")
    common.panel_label(ax, "a")
    ax = axes[0, 1]
    ma, va = marginal_gaussian(mu, S, [0])
    mc, vc = conditional_gaussian(mu, S, [0], [FIG5_XB])
    ax.plot(g, gauss_pdf(g[:, None], ma, va), color=common.BLUE, label="$p(x_a)$")
    ax.plot(g, gauss_pdf(g[:, None], mc, vc), color=common.RED, label="$p(x_a|x_b = %.1f)$" % FIG5_XB)
    ax.set_xlim(0, 1)
    ax.set_ylim(0, 6)
    ax.set_xticks([0, 0.5, 1])
    ax.set_xlabel("$x_a$")
    ax.legend(loc="upper left", frameon=False)
    common.panel_label(ax, "b", "upper right")
    common.savefig(fig, CH, "fig3-5", out_dir)


def faithful_fits():
    X = common.old_faithful()
    mu, S = gaussian_ml(X)
    pi, mus, Sig, ll = gmm_em(X, 2, seed=1)
    return X, (mu, S), (pi, mus, Sig, ll)


def fig3_6(out_dir=None):
    """Figure 3.6: Old Faithful with (a) the ML Gaussian and (b) the ML mixture of two Gaussians."""
    X, (mu, S), (pi, mus, Sig, ll) = faithful_fits()
    fig, axes = common.panel_grid(1, 2, size=(3.2, 2.9))
    gx, gy = np.meshgrid(np.linspace(1, 6, 200), np.linspace(40, 100, 200))
    P = np.c_[gx.ravel(), gy.ravel()]
    for ax, Z, lab in ((axes[0, 0], gauss_pdf(P, mu, S), "a"), (axes[0, 1], np.exp(gmm_logpdf(P, pi, mus, Sig)), "b")):
        Z = Z.reshape(gx.shape)
        ax.plot(X[:, 0], X[:, 1], "o", ms=3, mfc=common.GREEN, mec="k", mew=0.4)
        ax.contour(gx, gy, Z, levels=np.max(Z) * np.array([0.05, 0.2, 0.45, 0.75]), colors=common.RED, linewidths=1.1)
        ax.set_xlim(1, 6)
        ax.set_ylim(40, 100)
        ax.set_xticks([1, 2, 3, 4, 5, 6])
        ax.set_yticks([40, 60, 80, 100])
        common.panel_label(ax, lab)
    common.savefig(fig, CH, "fig3-6", out_dir)


MIX1D = dict(w=np.array([0.3, 0.3, 0.4]), mu=np.array([0.2, 0.5, 0.8]), sd=np.array([0.06, 0.1, 0.05]))


def fig3_7(out_dir=None):
    """Figure 3.7: a mixture of three 1-D Gaussians (blue, scaled by pi_k) and their sum (red)."""
    t = np.linspace(0, 1, 500)
    comps = [w * np.exp(-0.5 * ((t - m) / s) ** 2) / (s * math.sqrt(2 * math.pi)) for w, m, s in zip(MIX1D["w"], MIX1D["mu"], MIX1D["sd"])]
    fig, ax = plt.subplots(figsize=(4.0, 2.4))
    for c in comps:
        ax.plot(t, c, color=common.BLUE, lw=1.2)
    ax.plot(t, sum(comps), color=common.RED, lw=1.8)
    ax.set_xlabel("$x$")
    ax.set_ylabel("$p(x)$")
    _box(ax)
    common.savefig(fig, CH, "fig3-7", out_dir)


MIX2D = dict(pi=np.array([0.5, 0.3, 0.2]),
             mu=[np.array([0.22, 0.38]), np.array([0.5, 0.5]), np.array([0.72, 0.72])],
             S=[np.array([[0.012, 0.007], [0.007, 0.012]]), np.array([[0.008, -0.006], [-0.006, 0.008]]),
                np.array([[0.008, 0.005], [0.005, 0.009]])])


def fig3_8(out_dir=None):
    """Figure 3.8: a mixture of three 2-D Gaussians: component contours, mixture contours and a surface plot."""
    g = np.linspace(0, 1, 160)
    GX, GY = np.meshgrid(g, g)
    P = np.c_[GX.ravel(), GY.ravel()]
    fig = plt.figure(figsize=(9.0, 3.0))
    ax = fig.add_subplot(1, 3, 1)
    for k, col in enumerate((common.RED, common.BLUE, common.GREEN)):
        Z = gauss_pdf(P, MIX2D["mu"][k], MIX2D["S"][k]).reshape(GX.shape)
        ax.contour(GX, GY, Z, levels=Z.max() * np.array([0.1, 0.3, 0.5, 0.7, 0.9]), colors=col, linewidths=1.0)
    for k, (col, xy) in enumerate(zip((common.RED, common.BLUE, common.GREEN), [(0.1, 0.08), (0.62, 0.28), (0.38, 0.9)])):
        ax.text(*xy, r"$\pi_%d = %.1f$" % (k + 1, MIX2D["pi"][k]), color=col)
    ax.set_aspect("equal")
    _box(ax)
    ax.set_xlabel("$x_1$")
    ax.set_ylabel("$x_2$")
    ax.set_title("(a)")
    Z = np.exp(gmm_logpdf(P, MIX2D["pi"], MIX2D["mu"], MIX2D["S"])).reshape(GX.shape)
    ax = fig.add_subplot(1, 3, 2)
    ax.contour(GX, GY, Z, levels=Z.max() * np.linspace(0.08, 0.92, 9), colors=common.RED, linewidths=1.0)
    ax.set_aspect("equal")
    _box(ax)
    ax.set_xlabel("$x_1$")
    ax.set_ylabel("$x_2$")
    ax.set_title("(b)")
    ax = fig.add_subplot(1, 3, 3, projection="3d")
    s = slice(None, None, 3)
    ax.plot_surface(GX[s, s], GY[s, s], Z[s, s], cmap="Reds", linewidth=0.2, edgecolor="k", rstride=1, cstride=1, alpha=0.95)
    ax.set_xticks([])
    ax.set_yticks([])
    ax.set_zticks([])
    ax.set_xlabel("$x_1$")
    ax.set_ylabel("$x_2$")
    ax.view_init(28, -60)
    ax.set_title("(c)")
    common.savefig(fig, CH, "fig3-8", out_dir)


FIG9_THETA = np.array([0.35, 0.75, 1.2, 1.85])


def fig3_9(out_dir=None):
    """Figure 3.9: angles as unit vectors x_n on the circle and their average, at radius r and angle theta-bar."""
    th = FIG9_THETA
    tb, r = circular_mean(th)
    fig, ax = plt.subplots(figsize=(3.6, 3.6))
    t = np.linspace(0, 2 * math.pi, 300)
    ax.plot(np.cos(t), np.sin(t), color=common.GREY, lw=1.0)
    ax.annotate("", xy=(1.35, 0), xytext=(-1.35, 0), arrowprops=dict(arrowstyle="->", lw=0.8))
    ax.annotate("", xy=(0, 1.35), xytext=(0, -1.35), arrowprops=dict(arrowstyle="->", lw=0.8))
    for n, a in enumerate(th):
        ax.annotate("", xy=(math.cos(a), math.sin(a)), xytext=(0, 0), arrowprops=dict(arrowstyle="->", color=common.BLUE, lw=1.1))
        ax.text(1.12 * math.cos(a), 1.12 * math.sin(a), "$\\mathbf{x}_%d$" % (n + 1), ha="center", va="center", color=common.BLUE)
    ax.annotate("", xy=(r * math.cos(tb), r * math.sin(tb)), xytext=(0, 0), arrowprops=dict(arrowstyle="->", color=common.RED, lw=1.8))
    ax.text(r * math.cos(tb) + 0.02, r * math.sin(tb) - 0.12, r"$\bar{\mathbf{x}}$", color=common.RED, fontsize=11)
    ax.text(0.5 * r * math.cos(tb) - 0.12, 0.5 * r * math.sin(tb) + 0.06, r"$\bar r$", color=common.RED)
    a = np.linspace(0, tb, 50)
    ax.plot(0.25 * np.cos(a), 0.25 * np.sin(a), color="k", lw=0.8)
    ax.text(0.3 * math.cos(tb / 2) + 0.02, 0.3 * math.sin(tb / 2), r"$\bar\theta$")
    ax.text(1.3, -0.15, "$x_1$")
    ax.text(0.05, 1.3, "$x_2$")
    ax.set_xlim(-1.4, 1.45)
    ax.set_ylim(-1.4, 1.45)
    ax.set_aspect("equal")
    ax.axis("off")
    common.savefig(fig, CH, "fig3-9", out_dir)


def fig3_10(out_dir=None):
    """Figure 3.10: an isotropic 2-D Gaussian (blue contours) and the unit circle on which it is conditioned."""
    mu, s = np.array([1.2, 1.2]), 0.35
    fig, ax = plt.subplots(figsize=(3.6, 3.6))
    t = np.linspace(0, 2 * math.pi, 300)
    for k in (0.6, 1.2, 1.8):
        ax.plot(mu[0] + k * s * np.cos(t), mu[1] + k * s * np.sin(t), color=common.BLUE, lw=1.2)
    ax.plot(np.cos(t), np.sin(t), color=common.RED, lw=1.5)
    ax.annotate("", xy=(2.2, 0), xytext=(-1.3, 0), arrowprops=dict(arrowstyle="->", lw=0.8))
    ax.annotate("", xy=(0, 2.2), xytext=(0, -1.3), arrowprops=dict(arrowstyle="->", lw=0.8))
    ax.text(-1.25, -1.2, "$r = 1$", color=common.RED)
    ax.text(mu[0] + 0.45, mu[1] + 0.55, r"$p(\mathbf{x})$", color=common.BLUE)
    ax.text(2.1, -0.2, "$x_1$")
    ax.text(0.07, 2.1, "$x_2$")
    ax.set_xlim(-1.35, 2.3)
    ax.set_ylim(-1.35, 2.3)
    ax.set_aspect("equal")
    ax.axis("off")
    common.savefig(fig, CH, "fig3-10", out_dir)


def fig3_11(out_dir=None):
    """Figure 3.11: the von Mises density for (m, theta0) = (5, pi/4) and (1, 3 pi/4), Cartesian and polar."""
    t = np.linspace(0, 2 * math.pi, 600)
    cases = [(5, math.pi / 4, common.RED), (1, 3 * math.pi / 4, common.BLUE)]
    fig = plt.figure(figsize=(7.4, 3.0))
    ax = fig.add_subplot(1, 2, 1)
    for m, t0, c in cases:
        ax.plot(t, vonmises_pdf(t, t0, m), color=c, label=r"$m = %d$, $\theta_0 = %s$" % (m, r"\pi/4" if t0 < 1 else r"3\pi/4"))
    ax.set_xlim(0, 2 * math.pi)
    ax.set_xticks([0, math.pi / 4, 3 * math.pi / 4, 2 * math.pi])
    ax.set_xticklabels(["0", r"$\pi/4$", r"$3\pi/4$", r"$2\pi$"])
    ax.set_xlabel(r"$\theta$")
    ax.set_ylabel(r"$p(\theta|\theta_0, m)$")
    ax.legend(frameon=False)
    ax = fig.add_subplot(1, 2, 2)
    ax.plot(np.cos(t), np.sin(t), color=common.GREY, lw=0.8, ls="--")
    for m, t0, c in cases:
        rr = 1 + vonmises_pdf(t, t0, m)
        ax.plot(rr * np.cos(t), rr * np.sin(t), color=c)
    ax.set_aspect("equal")
    ax.axis("off")
    common.savefig(fig, CH, "fig3-11", out_dir)


def fig3_12(out_dir=None):
    """Figure 3.12: the Bessel function I0(m) and the ratio A(m) = I1(m) / I0(m)."""
    m = np.linspace(0, 10, 400)
    fig, axes = common.panel_grid(1, 2, size=(3.0, 2.4))
    axes[0, 0].plot(m, special.i0(m), color=common.RED)
    axes[0, 0].set_ylim(0, 3000)
    axes[0, 0].set_yticks([0, 1000, 2000, 3000])
    axes[0, 0].set_title(r"$I_0(m)$")
    axes[0, 1].plot(m, bessel_ratio(m), color=common.RED)
    axes[0, 1].set_ylim(0, 1)
    axes[0, 1].set_yticks([0, 0.5, 1])
    axes[0, 1].set_title(r"$A(m)$")
    for ax in axes[0]:
        ax.set_xlim(0, 10)
        ax.set_xticks([0, 5, 10])
        ax.set_xlabel("$m$")
    common.savefig(fig, CH, "fig3-12", out_dir)


def _density_panels(name, est_fn, params, labfmt, out_dir=None):
    x = density_data()
    t = np.linspace(0, 1, 800)
    fig, axes = common.panel_grid(3, 1, size=(3.6, 1.45))
    for ax, p in zip(axes[:, 0], params):
        est_fn(ax, x, t, p)
        ax.plot(t, density_mixture_pdf(t), color=common.GREEN, lw=1.6)
        ax.set_xlim(0, 1)
        ax.set_ylim(0, 5.5)
        ax.set_xticks([0, 0.5, 1])
        ax.set_yticks([0, 5])
        ax.text(0.03, 4.4, labfmt % p, fontsize=9)
    common.savefig(fig, CH, name, out_dir)


def fig3_13(out_dir=None):
    """Figure 3.13: histogram density estimates (3.175) with bin widths 0.04, 0.08 and 0.25."""
    def est(ax, x, t, d):
        e, h = histogram_density(x, d)
        ax.bar(e[:-1], h, width=d, align="edge", color=common.BLUE, alpha=0.75, edgecolor="k", lw=0.4)
    _density_panels("fig3-13", est, (0.04, 0.08, 0.25), r"$\Delta = %g$", out_dir)


def fig3_14(out_dir=None):
    """Figure 3.14: Gaussian kernel density estimates (3.184) with h = 0.005, 0.07 and 0.2."""
    def est(ax, x, t, h):
        ax.plot(t, kde(t, x, h), color=common.BLUE, lw=1.2)
    _density_panels("fig3-14", est, (0.005, 0.07, 0.2), r"$h = %g$", out_dir)


def fig3_15(out_dir=None):
    """Figure 3.15: K-nearest-neighbour density estimates (3.180) with K = 1, 5 and 30."""
    def est(ax, x, t, K):
        ax.plot(t, knn_density(t, x, K), color=common.BLUE, lw=1.2)
    _density_panels("fig3-15", est, (1, 5, 30), r"$K = %d$", out_dir)


def fig3_16(out_dir=None):
    """Figure 3.16: (a) the K = 3 nearest-neighbour vote for a new point; (b) the 1-NN decision boundary."""
    X, y = knn_class_data()
    cols = np.array([common.RED, common.BLUE])
    fig, axes = common.panel_grid(1, 2, size=(3.0, 3.0))
    q = np.array([0.52, 0.52])
    ax = axes[0, 0]
    d = ((X - q) ** 2).sum(1)
    nn = np.argsort(d)[:3]
    for i in nn:
        ax.plot([q[0], X[i, 0]], [q[1], X[i, 1]], color=common.GREEN, lw=1.2, zorder=1)
    ax.add_patch(plt.Circle(q, math.sqrt(d[nn[-1]]), fill=False, color=common.GREEN, ls="--", lw=0.8))
    ax.scatter(X[:, 0], X[:, 1], c=cols[y], s=14, zorder=2)
    ax.plot(*q, "D", mfc="none", mec="k", ms=6, zorder=3)
    ax.set_title("(a)")
    ax = axes[0, 1]
    g = np.linspace(0, 1, 401)
    GX, GY = np.meshgrid(g, g)
    _, lab = knn_classify(np.c_[GX.ravel(), GY.ravel()], X, y, 1)
    ax.contour(GX, GY, lab.reshape(GX.shape).astype(float), levels=[0.5], colors=common.GREEN, linewidths=1.3)
    ax.scatter(X[:, 0], X[:, 1], c=cols[y], s=14, zorder=2)
    ax.set_title("(b)")
    for ax in axes[0]:
        ax.set_xlim(0, 1)
        ax.set_ylim(0, 1)
        ax.set_aspect("equal")
        _box(ax)
        ax.set_xlabel("$x_1$")
        ax.set_ylabel("$x_2$")
    common.savefig(fig, CH, "fig3-16", out_dir)


FIGURES = {"3.1": fig3_1, "3.2": fig3_2, "3.3": fig3_3, "3.4": fig3_4, "3.5": fig3_5, "3.6": fig3_6,
           "3.7": fig3_7, "3.8": fig3_8, "3.9": fig3_9, "3.10": fig3_10, "3.11": fig3_11, "3.12": fig3_12,
           "3.13": fig3_13, "3.14": fig3_14, "3.15": fig3_15, "3.16": fig3_16}

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