"""Bishop and Bishop (2024), Chapter 15: Discrete Latent Variables.

Reproduces the figures of Chapter 15 of C. M. Bishop and H. Bishop, Deep Learning: Foundations and
Concepts (Springer, 2024), pp. 459-493, written from scratch with numpy and matplotlib, and supplies
the data and reference numbers of the three browser demonstrations. Every algorithm is a short
function meant to be read next to the lecture notes (ch15-discrete-latent-variables.html):

* Section 15.1, K-means: the distortion J (15.1), the E step (15.2) and M step (15.4), batch K-means
  (Algorithm 15.1) and its sequential form (15.5); vector quantisation of images, pixel by pixel or in
  2 x 2 blocks, with the bit count 24K + N ceil(log2 K) of Section 15.1.1 (vq_kmeans, vq_bits).
* Section 15.2, Gaussian mixtures: the log likelihood (15.13), responsibilities (15.12), EM
  (Algorithm 15.2) with an optional inverse-Wishart-style ridge, ancestral sampling, the
  singularity (15.14) and two-moons density estimation.
* Section 15.3, the latent-variable view: complete-data likelihood (15.25)-(15.30), the K-means limit
  of EM with covariances eps I (15.31)-(15.33), and mixtures of Bernoulli distributions (15.34)-(15.50)
  on binarised MNIST digits.
* Section 15.4, the evidence lower bound: L(q, theta) and KL(q||p) of (15.52)-(15.54) for a
  one-dimensional Gaussian mixture, EM as coordinate ascent on L, exact and partial E steps,
  exact, ECM and gradient M steps, a prior on the variances (MAP-EM, (15.59)), and incremental EM
  (15.60)-(15.61) with the covariance and mixing-coefficient updates of Exercise 15.24.
* JSRandom: the seeded generator DK.rng of the browser demos (mulberry32 uniforms and Box-Muller
  normals). vq_kmeans (kmeans-quantisation-demo.html), em1d_run (em-elbo-steps-demo.html) and bern_em_js
  (bernoulli-mixture-demo.html) use only that generator, so the pages reproduce them number for
  number.

Figures reproduced: 15.1, 15.2, 15.3, 15.5, 15.6, 15.7, 15.8, 15.12, 15.13, 15.14, 15.15 and 15.16.
* 15.1, 15.2, 15.7: standardised Old Faithful data; initial centres read off the book's Figure 15.1(a),
  initial covariances 0.6 I for EM.
* 15.3: the book's photograph is not reproduced. We draw our own 240 x 180 test image procedurally
  (landscape(), so it has exactly the book's 43,200 pixels and the bit counts of p. 466 apply) and run
  K-means from k-means++ starting centres chosen with the demo's seeded generator.
* 15.5: 500 samples from the three-component mixture of our Figure 3.8 (ch03 MIX2D).
* 15.6: computed for seven points (the book's picture is a sketch).
* 15.8: our own two-moons data (300 points), K = 16 components, EM from K-means with a small ridge.
* 15.12: the first 200 training images of each of the digits 2, 3, 4, binarised at 0.5, K = 3,
  10 EM iterations, initialised as the book describes (pi_k = 1/K, mu_ki uniform on (0.25, 0.75),
  then normalised) with the demo's seeded generator.
* 15.13-15.15: the book's bar diagrams, computed: the actual values of ln p(X|theta), L(q, theta)
  and KL(q||p) for the one-dimensional data of em-elbo-steps-demo.html (preset 1).
* 15.16: the book's sketch, computed: ln p(X|theta) and the two bounds along the straight line in
  parameter space through theta_old and theta_new for the same data and model.
Skipped: Figures 15.4, 15.9, 15.10 and 15.11 (graphical-model diagrams; they contain no data).

Supplementary figures (our own, numbered 15.S1-15.S4 in the order they appear in the notes):
15.S1 rate and distortion of vector quantisation, pixels against 2 x 2 blocks;
15.S2 held-out log likelihood of Gaussian mixtures on two moons against K;
15.S3 K-means as the eps -> 0 limit of EM: responsibilities, the scaled Q function and the centres;
15.S4 variants of EM on Old Faithful: batch, incremental, ECM and gradient M steps, partial E steps.

Run `python3 ch15_discrete_latent_variables.py --list`, `python3 ch15_discrete_latent_variables.py`
(all figures, under a minute on one CPU thread) or `... --fig 15.3 15.S1`. Files go to ../img/ch15/.
"""
import base64
import json
import math
import os

for _v in ("OPENBLAS_NUM_THREADS", "MKL_NUM_THREADS", "OMP_NUM_THREADS"):
    os.environ.setdefault(_v, "1")

import numpy as np  # noqa: E402
import matplotlib.pyplot as plt  # noqa: E402
from matplotlib.colors import LinearSegmentedColormap  # noqa: E402
from matplotlib.patches import Ellipse  # noqa: E402

import common  # noqa: E402
from common import savefig, run, logsumexp  # noqa: E402

HERE = os.path.dirname(os.path.abspath(__file__))
WEB_DATA = os.path.normpath(os.path.join(HERE, "..", "data"))
CH = 15
M32 = 0xFFFFFFFF
BOOK_CENTRES = np.array([[1.4, -1.0], [-1.4, 1.0]])  # Figure 15.1(a): red (mu_1), then blue (mu_2)
BOOK_COV = 0.6                                        # Figure 15.7(a): initial covariances 0.6 I
LIM = (-2.5, 2.5)


# =========================================================================== 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).

    Uniforms come from the mulberry32 generator and normals from the Box-Muller transform, the
    second normal of each pair being cached, exactly as in JavaScript.
    """

    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)


# =========================================================================== 15.1 K-means
def distortion(X, r, mu):
    """J of (15.1); r[n] is the cluster index of x_n (r_nk = 1 for k = r[n])."""
    return float(((X - mu[r]) ** 2).sum())


def kmeans_e(X, mu):
    """E step (15.2): the index of the nearest centre (ties go to the lowest index)."""
    d2 = ((X[:, None, :] - mu[None, :, :]) ** 2).sum(-1)
    return d2.argmin(1)


def kmeans_m(X, r, mu_old):
    """M step (15.4): each centre moves to the mean of its points; an empty cluster keeps its centre."""
    mu = mu_old.copy()
    for k in range(len(mu)):
        if np.any(r == k):
            mu[k] = X[r == k].mean(0)
    return mu


def kmeans(X, mu0, max_iter=100):
    """Batch K-means (Algorithm 15.1). Returns a list of steps, one per E-M cycle, each a dict with the
    assignments r, the centres before ('mu_old') and after ('mu') the M step, and J after the E and M steps."""
    mu = np.array(mu0, dtype=float)
    hist, r_old = [], None
    for _ in range(max_iter):
        r = kmeans_e(X, mu)
        JE = distortion(X, r, mu)
        mu_new = kmeans_m(X, r, mu)
        hist.append(dict(r=r, mu_old=mu, mu=mu_new, JE=JE, JM=distortion(X, r, mu_new)))
        mu = mu_new
        if r_old is not None and np.array_equal(r, r_old):
            break
        r_old = r
    return hist


def kmeans_sequential(X, mu0):
    """Sequential K-means (15.5): each point, in the order given, moves its nearest prototype by
    (x_n - mu_k)/N_k, where N_k counts the points used so far for mu_k (including this one).
    Returns the prototypes, the counts and the assignment made for each point."""
    mu = np.array(mu0, dtype=float)
    Nk = np.zeros(len(mu))
    assign = np.zeros(len(X), dtype=int)
    for n, x in enumerate(X):
        k = int(((mu - x) ** 2).sum(1).argmin())
        Nk[k] += 1
        mu[k] = mu[k] + (x - mu[k]) / Nk[k]
        assign[n] = k
    return mu, Nk, assign


# ================================================================ test images (Figure 15.3, demo)
def _value_noise(H, W, scale, rng):
    gh, gw = H // scale + 2, W // scale + 2
    g = rng.random((gh, gw))
    y, x = np.arange(H) / scale, np.arange(W) / scale
    y0, x0 = y.astype(int), x.astype(int)
    fy, fx = (y - y0)[:, None], (x - x0)[None, :]
    fy, fx = fy * fy * (3 - 2 * fy), fx * fx * (3 - 2 * fx)
    a, b = g[y0][:, x0], g[y0][:, x0 + 1]
    c, d = g[y0 + 1][:, x0], g[y0 + 1][:, x0 + 1]
    return a * (1 - fy) * (1 - fx) + b * (1 - fy) * fx + c * fy * (1 - fx) + d * fy * fx


def _fbm(H, W, rng, scales=(48, 24, 12, 6, 3)):
    out, amp, tot = np.zeros((H, W)), 1.0, 0.0
    for s in scales:
        out += amp * _value_noise(H, W, s, rng)
        tot += amp
        amp *= 0.55
    return out / tot


def landscape(H=180, W=240, seed=7):
    """Our own 240 x 180 test image (sky, clouds, sun, mountains, hills, lake, flowers, a house, trees),
    drawn procedurally so that no photograph is needed. Returns uint8 RGB of shape (H, W, 3)."""
    rng = np.random.default_rng(seed)
    yy, xx = np.mgrid[0:H, 0:W].astype(float)
    t = yy / H
    top, bot = np.array([0.20, 0.42, 0.78]), np.array([0.80, 0.88, 0.96])
    img = top + (bot - top) * (t[..., None] / 0.55).clip(0, 1)
    cl = _fbm(H, W, rng)
    cm = ((cl - 0.55) * 6).clip(0, 1)[..., None] * (yy < 70)[..., None]
    img = img * (1 - 0.8 * cm) + 0.97 * 0.8 * cm
    sun = np.clip(1 - (np.hypot(xx - 190, yy - 32) - 13) / 2, 0, 1)[..., None]
    img = img * (1 - sun) + np.array([1.0, 0.86, 0.35]) * sun
    ridge1 = 78 - 30 * _fbm(1, W, rng, (40, 20, 10, 5))[0] - 10 * np.sin(xx[0] / 37)
    m1 = yy > ridge1[None, :]
    img[m1] = np.array([0.45, 0.47, 0.62]) + 0.05 * (yy[m1, None] - 60) / 40
    img[m1 & (yy < ridge1[None, :] + 6) & (ridge1[None, :] < 62)] = [0.93, 0.94, 0.98]
    ridge2 = 108 - 18 * _fbm(1, W, rng, (60, 30, 15))[0] + 6 * np.sin(xx[0] / 23 + 1)
    m2 = yy > ridge2[None, :]
    tex = _fbm(H, W, rng, (8, 4, 2))
    img[m2] = np.stack([0.25 + 0.15 * tex, 0.52 + 0.2 * tex, 0.18 + 0.08 * tex], -1)[m2]
    lake = (yy > 135) & (((xx - 70) / 95) ** 2 + ((yy - 158) / 26) ** 2 < 1)
    rip = 0.04 * np.sin(yy * 1.7 + 2 * np.sin(xx / 9))
    img[lake] = np.stack([0.18 + rip, 0.42 + rip, 0.70 + rip], -1)[lake]
    fl = (yy > 140) & ~lake & (rng.random((H, W)) < 0.10)
    cols = np.where(rng.random((H, W))[..., None] < 0.5, np.array([0.85, 0.15, 0.15]), np.array([0.98, 0.85, 0.2]))
    img[fl] = cols[fl]
    img[(xx > 160) & (xx < 196) & (yy > 112) & (yy < 136)] = [0.93, 0.88, 0.75]
    img[(yy > 92) & (yy <= 112) & (np.abs(xx - 178) < (yy - 92) * 1.15 + 2)] = [0.70, 0.16, 0.12]
    img[(xx > 174) & (xx < 182) & (yy > 122) & (yy < 136)] = [0.35, 0.22, 0.12]
    img[(((xx > 164) & (xx < 171)) | ((xx > 186) & (xx < 193))) & (yy > 117) & (yy < 124)] = [0.30, 0.55, 0.85]
    for cx, cy, rr in [(30, 112, 13), (52, 118, 10), (218, 120, 12)]:
        img[(np.abs(xx - cx) < 2) & (yy > cy) & (yy < cy + rr + 12)] = [0.38, 0.25, 0.14]
        crown = np.hypot(xx - cx, (yy - cy) * 1.2) < rr
        img[crown] = np.array([0.10, 0.35, 0.12]) + 0.12 * tex[crown][:, None]
    img = img + 0.015 * rng.standard_normal(img.shape)
    return (np.clip(img, 0, 1) * 255).round().astype(np.uint8)


def still_life(H=180, W=240, seed=11):
    """A second procedural test image: shaded fruit in a bowl on a wooden table."""
    rng = np.random.default_rng(seed)
    yy, xx = np.mgrid[0:H, 0:W].astype(float)
    img = np.broadcast_to(np.array([0.20, 0.45, 0.48]), (H, W, 3)) + 0.04 * _fbm(H, W, rng)[..., None]
    img = np.array(img)
    grain = np.sin(xx / 3 + 6 * _fbm(H, W, rng, (30, 15))) * 0.05
    table = yy > 110
    img[table] = np.stack([0.55 + grain, 0.35 + grain, 0.18 + grain / 2], -1)[table]

    def ball(cx, cy, r, col, hl=0.35):
        m = np.hypot(xx - cx, yy - cy) < r
        shade = (1 - 0.55 * np.hypot(xx - cx + 0.4 * r, yy - cy + 0.4 * r) / (1.6 * r)).clip(0.25, 1)
        c = np.array(col)[None, None, :] * shade[..., None]
        c = c + hl * np.exp(-((xx - cx + 0.35 * r) ** 2 + (yy - cy + 0.4 * r) ** 2) / (0.03 * r * r))[..., None]
        img[m] = c[m]
    img[(yy > 112) & (yy < 150) & (((xx - 120) / 80) ** 2 + ((yy - 112) / 38) ** 2 < 1)] = [0.88, 0.88, 0.92]
    ball(78, 100, 24, [0.85, 0.12, 0.10])
    ball(120, 92, 26, [1.0, 0.55, 0.05])
    ball(162, 102, 22, [0.55, 0.78, 0.15])
    ball(100, 70, 16, [0.45, 0.10, 0.45])
    ball(146, 66, 15, [0.98, 0.85, 0.20])
    for cx in (210, 222, 216):
        for cy in (125, 137):
            ball(cx + (cy - 125) / 3, cy, 7, [0.30, 0.15, 0.40], 0.25)
    img = img + 0.012 * rng.standard_normal(img.shape)
    return (np.clip(img, 0, 1) * 255).round().astype(np.uint8)


IMAGES = {"landscape": landscape, "still": still_life}


def image_vectors(img, block=1):
    """Rows of the data matrix for vector quantisation: one RGB triple in [0, 1] per pixel (block = 1),
    or one 12-vector per 2 x 2 block (block = 2; order: row, column, channel)."""
    H, W, _ = img.shape
    v = img.astype(float) / 255.0
    if block == 1:
        return v.reshape(H * W, 3)
    return v.reshape(H // 2, 2, W // 2, 2, 3).transpose(0, 2, 1, 3, 4).reshape(H * W // 4, 12)


def vectors_image(V, H, W, block=1):
    if block == 1:
        return V.reshape(H, W, 3)
    return V.reshape(H // 2, W // 2, 2, 2, 3).transpose(0, 2, 1, 3, 4).reshape(H, W, 3)


def _sqdist(V, mu, chunk=4096):
    """Squared distances, computed directly as sum_d (v_d - mu_d)^2 in chunks (the demo's arithmetic)."""
    out = np.empty((len(V), len(mu)))
    for s in range(0, len(V), chunk):
        out[s:s + chunk] = ((V[s:s + chunk, None, :] - mu[None, :, :]) ** 2).sum(-1)
    return out


def _sqdist_fast(V, mu):
    return np.maximum((V * V).sum(1)[:, None] - 2 * V @ mu.T + (mu * mu).sum(1)[None, :], 0.0)


def vq_init(V, K, init, seed):
    """Starting centres of the demo: 'random' = K pixels drawn with replacement, 'pp' = k-means++
    (Arthur and Vassilvitskii, 2007): each further centre is a point drawn with probability
    proportional to its squared distance to the nearest centre chosen so far."""
    rng = JSRandom(seed)
    N = len(V)
    if init == "random":
        return np.array([V[int(rng.u() * N)] for _ in range(K)])
    idx = [int(rng.u() * N)]
    d2 = ((V - V[idx[0]]) ** 2).sum(1)
    for _ in range(1, K):
        cum = np.cumsum(d2)
        r = rng.u() * cum[-1]
        j = int(np.searchsorted(cum, r, side="right"))
        j = min(j, N - 1)
        idx.append(j)
        d2 = np.minimum(d2, ((V - V[j]) ** 2).sum(1))
    return V[idx].copy()


def vq_kmeans(V, K, init="pp", seed=1, max_iter=60, fast=False, mu0=None):
    """K-means for vector quantisation, as in kmeans-quantisation-demo.html. Returns (mu, r, Js) where
    Js lists J after every half step: [J after E1, J after M1, J after E2, ...]."""
    mu = vq_init(V, K, init, seed) if mu0 is None else np.array(mu0, float)
    Js, r_old = [], None
    dist = _sqdist_fast if fast else _sqdist
    D = V.shape[1]
    for _ in range(max_iter):
        d2 = dist(V, mu)
        r = d2.argmin(1)
        Js.append(float(np.cumsum(d2[np.arange(len(V)), r])[-1]))
        if r_old is not None and np.array_equal(r, r_old):
            break
        cnt = np.bincount(r, minlength=K)
        new = mu.copy()
        for d in range(D):
            s = np.bincount(r, weights=V[:, d], minlength=K)
            new[cnt > 0, d] = s[cnt > 0] / cnt[cnt > 0]
        mu = new
        Js.append(float(np.cumsum(((V - mu[r]) ** 2).sum(1))[-1]))
        r_old = r
    return mu, r, Js


def vq_bits(N, K, block=1):
    """Bits to send an image of N pixels: the codebook (8 bits per number) plus ceil(log2 K) bits per code."""
    per = 0 if K == 1 else math.ceil(math.log2(K) - 1e-12)
    return 24 * block * block * K + (N // (block * block)) * per


def psnr(J, N):
    """Peak signal-to-noise ratio (dB) of a quantised image with distortion J over N pixels (values in [0, 1])."""
    return 10 * math.log10(1.0 / (J / (3 * N)))


# =========================================================================== 15.2 Gaussian mixtures
def gmm_logjoint(X, pi, mu, Sig):
    """(N, K) matrix of ln pi_k + ln N(x_n | mu_k, Sigma_k)."""
    return np.stack([math.log(pi[k]) + common.gauss_logpdf(X, mu[k], Sig[k]) for k in range(len(pi))], 1)


def gmm_loglik(X, pi, mu, Sig):
    """ln p(X | pi, mu, Sigma), (15.13), via log-sum-exp."""
    return float(logsumexp(gmm_logjoint(X, pi, mu, Sig), axis=1).sum())


def gmm_resp(X, pi, mu, Sig):
    """Responsibilities gamma(z_nk), (15.12), and the log likelihood."""
    A = gmm_logjoint(X, pi, mu, Sig)
    l = logsumexp(A, axis=1, keepdims=True)
    return np.exp(A - l), float(l.sum())


def gmm_m(X, G, reg=0.0):
    """M step (15.16)-(15.18), (15.21); reg adds reg * I to every covariance (a simple guard against
    the singularities of Section 15.2.1)."""
    Nk = G.sum(0)
    mu = (G.T @ X) / Nk[:, None]
    Sig = []
    for k in range(G.shape[1]):
        Dx = X - mu[k]
        Sig.append((G[:, k, None] * Dx).T @ Dx / Nk[k] + reg * np.eye(X.shape[1]))
    return Nk / len(X), mu, np.array(Sig)


def gmm_em(X, pi, mu, Sig, iters, reg=0.0):
    """EM for a Gaussian mixture (Algorithm 15.2). Returns a list with one entry per parameter value
    theta_0, theta_1, ...: the parameters, the responsibilities computed from them and ln p(X|theta)."""
    pi, mu, Sig = np.array(pi, float), np.array(mu, float), np.array(Sig, float)
    hist = []
    for it in range(iters + 1):
        G, ll = gmm_resp(X, pi, mu, Sig)
        hist.append(dict(pi=pi, mu=mu, Sig=Sig, gamma=G, loglik=ll))
        if it < iters:
            pi, mu, Sig = gmm_m(X, G, reg)
    return hist


def kmeanspp_np(X, K, rng):
    idx = [int(rng.integers(len(X)))]
    d2 = ((X - X[idx[0]]) ** 2).sum(1)
    for _ in range(1, K):
        j = int(rng.choice(len(X), p=d2 / d2.sum()))
        idx.append(j)
        d2 = np.minimum(d2, ((X - X[j]) ** 2).sum(1))
    return X[idx].copy()


def gmm_fit(X, K, rng, iters=200, reg=1e-3, tol=1e-8):
    """EM from a K-means start (centres by k-means++, covariances and weights from the clusters), as
    recommended on p. 473; returns (pi, mu, Sig, loglik)."""
    km = kmeans(X, kmeanspp_np(X, K, rng), max_iter=100)
    r, mu = km[-1]["r"], km[-1]["mu"]
    D = X.shape[1]
    pi = np.array([max(np.mean(r == k), 1e-3) for k in range(K)])
    pi /= pi.sum()
    Sig = np.array([np.cov(X[r == k].T, bias=True) + reg * np.eye(D) if np.sum(r == k) > 1 else np.eye(D) * 0.1
                    for k in range(K)])
    ll_old = -np.inf
    for _ in range(iters):
        G, ll = gmm_resp(X, pi, mu, Sig)
        pi, mu, Sig = gmm_m(X, G, reg)
        if ll - ll_old < tol * abs(ll):
            break
        ll_old = ll
    return pi, mu, Sig, gmm_loglik(X, pi, mu, Sig)


def gmm_sample(n, pi, mu, Sig, rng):
    """Ancestral sampling (Section 14.2.5): z ~ p(z), then x ~ p(x|z)."""
    z = rng.choice(len(pi), size=n, p=pi)
    L = [np.linalg.cholesky(S) for S in Sig]
    x = np.array([mu[k] + L[k] @ rng.standard_normal(len(mu[k])) for k in z])
    return x, z


def two_moons(n, noise, rng):
    """Two interleaved half circles (our own generator): half the points on each moon."""
    n1 = n // 2
    t1, t2 = rng.uniform(0, np.pi, n1), rng.uniform(0, np.pi, n - n1)
    X = np.vstack([np.c_[np.cos(t1), np.sin(t1)], np.c_[1 - np.cos(t2), 0.5 - np.sin(t2)]])
    return X + noise * rng.standard_normal(X.shape)


# =========================================================================== 15.3.2 the K-means limit
def resp_eps(X, mu, eps, pi=None):
    """Responsibilities (15.32) for shared covariance eps I."""
    K = len(mu)
    pi = np.full(K, 1.0 / K) if pi is None else pi
    A = np.log(pi)[None, :] - ((X[:, None, :] - mu[None]) ** 2).sum(-1) / (2 * eps)
    return np.exp(A - logsumexp(A, axis=1, keepdims=True))


def em_eps(X, mu0, eps, iters=200):
    """EM with covariances fixed at eps I and equal mixing weights: only the means move (15.16)."""
    mu = np.array(mu0, float)
    for _ in range(iters):
        G = resp_eps(X, mu, eps)
        mu = (G.T @ X) / G.sum(0)[:, None]
    return mu


# =========================================================================== 15.3.3 Bernoulli mixtures
EPS_B = 1e-10


def bern_logjoint(X, pi, mu):
    """(N, K) matrix of ln pi_k + ln p(x_n | mu_k), (15.38); logs of mu are clipped to [1e-10, 1 - 1e-10]."""
    m = np.clip(mu, EPS_B, 1 - EPS_B)
    return np.log(pi)[None, :] + X @ np.log(m).T + (1 - X) @ np.log(1 - m).T


def bern_em(X, pi, mu, iters):
    """EM for a Bernoulli mixture: E step (15.46), M step (15.47)-(15.50). Returns (pi, mu, gamma, lls)
    where lls[t] is ln p(X) (15.41) after t M steps."""
    pi, mu = np.array(pi, float), np.array(mu, float)
    lls = []
    for it in range(iters + 1):
        A = bern_logjoint(X, pi, mu)
        l = logsumexp(A, axis=1, keepdims=True)
        lls.append(float(l.sum()))
        G = np.exp(A - l)
        if it == iters:
            break
        Nk = G.sum(0)
        mu = (G.T @ X) / Nk[:, None]
        pi = Nk / len(X)
    return pi, mu, G, lls


def bern_init_js(K, D, init, seed):
    """Starting values of bernoulli-mixture-demo.html: pi_k = 1/K and mu_ki = 0.25 + 0.5 u (u from the
    seeded generator, k-major). 'book' then divides each row by its sum (as printed on p. 484), and
    'equal' copies the first row to all components (the degenerate start of Exercise 15.15)."""
    rng = JSRandom(seed)
    mu = np.array([[0.25 + 0.5 * rng.u() for _ in range(D)] for _ in range(K)])
    if init == "book":
        mu = mu / mu.sum(1, keepdims=True)
    elif init == "equal":
        mu = np.repeat(mu[:1], K, 0)
    return np.full(K, 1.0 / K), mu


def bern_em_js(X, K, init="uniform", seed=1, iters=10):
    pi, mu = bern_init_js(K, X.shape[1], init, seed)
    return bern_em(X, pi, mu, iters)


def digits(which=(2, 3, 4), n_each=200):
    """The first n_each MNIST training images of each digit in `which`, binarised at 0.5 (Section 15.3.3)."""
    X, y = common.mnist(train=True)
    keep = np.concatenate([np.nonzero(y == d)[0][:n_each] for d in which])
    return (X[keep] > 0.5).astype(float), y[keep]


# =========================================================================== 15.4 the ELBO, 1-D mixtures
# The data sets of em-elbo-steps-demo.html: n points drawn from a mixture with the demo's generator.
EM1D_DATA = {
    "two": dict(n=60, pi=[0.55, 0.45], mu=[-1.6, 1.4], sd=[0.7, 0.9], seed=3),
    "three": dict(n=90, pi=[0.4, 0.35, 0.25], mu=[-2.5, 0.0, 2.4], sd=[0.6, 0.5, 0.8], seed=5),
    "overlap": dict(n=80, pi=[0.5, 0.5], mu=[-0.6, 0.8], sd=[1.0, 0.6], seed=7),
}
LOG2PI = math.log(2 * math.pi)
VFLOOR = 1e-10
PRIOR = (2.0, 0.1)   # inverse-gamma prior IG(a0, b0) on each variance (MAP-EM)


def em1d_data(name):
    d = EM1D_DATA[name]
    rng = JSRandom(d["seed"])
    K = len(d["pi"])
    x = []
    for _ in range(d["n"]):
        u, k, c = rng.u(), 0, d["pi"][0]
        while u > c and k < K - 1:
            k += 1
            c += d["pi"][k]
        x.append(d["mu"][k] + d["sd"][k] * rng.norm())
    return x


def _logn(x, m, v):
    return -0.5 * (LOG2PI + math.log(v)) - (x - m) * (x - m) / (2 * v)


def em1d_init(x, K, init, seed=1, theta0=None):
    """Starting parameters: 'spread' puts the means at mean + sd * (2(k + 1/2)/K - 1), all variances at
    the data variance and pi_k = 1/K; 'random' uses K data points (seeded) as means; theta0 overrides."""
    if theta0 is not None:
        return dict(pi=list(theta0["pi"]), mu=list(theta0["mu"]), v=list(theta0["v"]))
    n = len(x)
    m = 0.0
    for xi in x:
        m += xi
    m /= n
    s = 0.0
    for xi in x:
        s += (xi - m) * (xi - m)
    var = s / n
    sd = math.sqrt(var)
    if init == "random":
        rng = JSRandom(seed)
        mu = [x[int(rng.u() * n)] for _ in range(K)]
    else:
        mu = [m + sd * (2 * (k + 0.5) / K - 1) for k in range(K)]
    return dict(pi=[1.0 / K] * K, mu=mu, v=[var] * K)


def em1d_logjoint(x, th):
    K = len(th["pi"])
    return [[math.log(th["pi"][k]) + _logn(xi, th["mu"][k], th["v"][k]) for k in range(K)] for xi in x]


def em1d_post(x, th):
    """Posterior responsibilities and ln p(X|theta) for the 1-D mixture (the demo's arithmetic)."""
    A = em1d_logjoint(x, th)
    G, ll = [], 0.0
    for a in A:
        m = max(a)
        s = 0.0
        for ak in a:
            s += math.exp(ak - m)
        l = m + math.log(s)
        ll += l
        G.append([math.exp(ak - l) for ak in a])
    return G, ll


def em1d_elbo(x, th, q):
    """L(q, theta) of (15.53) for factorised q: sum_n sum_k q_nk (ln p(x_n, z_nk = 1) - ln q_nk)."""
    A = em1d_logjoint(x, th)
    L = 0.0
    for a, qn in zip(A, q):
        for ak, qk in zip(a, qn):
            if qk > 0:
                L += qk * (ak - math.log(qk))
    return L


def em1d_logprior(th, prior):
    if not prior:
        return 0.0
    a0, b0 = PRIOR
    s = 0.0
    for v in th["v"]:
        s += -(a0 + 1) * math.log(v) - b0 / v
    return s


def em1d_mstep(x, q, th, mode="exact", prior=False, step=0, eta=0.5):
    """M step with q fixed. 'exact': (15.16), (15.18), (15.21) (with the inverse-gamma prior if asked);
    'ecm': only one block per step, cycling means, variances, weights (step selects the block);
    'grad': one gradient-ascent step of size eta/N on L(q, theta) + ln p(theta) in the coordinates
    (mu_k, ln v_k, logit_k)."""
    n, K = len(x), len(th["pi"])
    a0, b0 = PRIOR
    Nk = [0.0] * K
    for qn in q:
        for k in range(K):
            Nk[k] += qn[k]
    pi, mu, v = list(th["pi"]), list(th["mu"]), list(th["v"])
    if mode == "grad":
        gm, gs = [0.0] * K, [0.0] * K
        for xi, qn in zip(x, q):
            for k in range(K):
                d = xi - mu[k]
                gm[k] += qn[k] * d / v[k]
                gs[k] += qn[k] * (-0.5 + d * d / (2 * v[k]))
        if prior:
            for k in range(K):
                gs[k] += -(a0 + 1) + b0 / v[k]
        lg = [math.log(p) for p in pi]
        new_lg = [lg[k] + eta / n * (Nk[k] - n * pi[k]) for k in range(K)]
        mx = max(new_lg)
        e = [math.exp(t - mx) for t in new_lg]
        se = sum(e)
        return dict(pi=[t / se for t in e], mu=[mu[k] + eta / n * gm[k] for k in range(K)],
                    v=[max(v[k] * math.exp(eta / n * gs[k]), VFLOOR) for k in range(K)])
    block = step % 3 if mode == "ecm" else -1
    if block in (-1, 0):
        for k in range(K):
            s = 0.0
            for xi, qn in zip(x, q):
                s += qn[k] * xi
            mu[k] = s / Nk[k]
    if block in (-1, 1):
        for k in range(K):
            s = 0.0
            for xi, qn in zip(x, q):
                s += qn[k] * (xi - mu[k]) * (xi - mu[k])
            v[k] = max((s + 2 * b0) / (Nk[k] + 2 * (a0 + 1)) if prior else s / Nk[k], VFLOOR)
    if block in (-1, 2):
        pi = [Nk[k] / n for k in range(K)]
    return dict(pi=pi, mu=mu, v=v)


def em1d_run(x, K, init="spread", seed=1, halfsteps=20, emode="exact", lam=1.0, mmode="exact", eta=0.5,
             prior=False, theta0=None):
    """The run of em-elbo-steps-demo.html: start from theta_0 and q_0 = uniform (1/K), then alternate E and
    M half steps. Returns a list of records (kind, theta, q, lnp, L, KL) where lnp and L include ln p(theta)
    when the prior is on; KL = lnp - L. The E step sets q to the posterior ('exact') or moves it a
    fraction lam of the way ('partial', Neal and Hinton, 1999)."""
    th = em1d_init(x, K, init, seed, theta0)
    q = [[1.0 / K] * K for _ in x]

    def rec(kind):
        G, ll = em1d_post(x, th)
        lp = em1d_logprior(th, prior)
        L = em1d_elbo(x, th, q) + lp
        return dict(kind=kind, theta=dict(pi=list(th["pi"]), mu=list(th["mu"]), v=list(th["v"])),
                    q=[list(r) for r in q], lnp=ll + lp, L=L, KL=ll + lp - L)
    out = [rec("init")]
    msteps = 0
    for h in range(halfsteps):
        if h % 2 == 0:
            G, _ = em1d_post(x, th)
            if emode == "exact":
                q = G
            else:
                q = [[(1 - lam) * qk + lam * gk for qk, gk in zip(qn, gn)] for qn, gn in zip(q, G)]
            out.append(rec("E"))
        else:
            th = em1d_mstep(x, q, th, mmode, prior, msteps, eta)
            msteps += 1
            out.append(rec("M"))
    return out


def _coords(th):
    lg = [math.log(p) for p in th["pi"]]
    return np.array(list(th["mu"]) + [math.log(v) for v in th["v"]] + lg)


def _theta_from(c, K):
    mu, lv, lg = c[:K], c[K:2 * K], c[2 * K:]
    e = np.exp(lg - lg.max())
    return dict(pi=list(e / e.sum()), mu=list(mu), v=list(np.exp(lv)))


def em1d_slice(x, th_old, th_new, q_old, q_new, ts):
    """ln p(X|theta(t)) and the bounds L(q_old, theta(t)), L(q_new, theta(t)) along the straight line
    theta(t) = theta_old + t (theta_new - theta_old) in the coordinates (mu_k, ln v_k, ln pi_k)
    (Figure 15.16): t = 0 is theta_old, t = 1 is theta_new."""
    K = len(th_old["pi"])
    c0, c1 = _coords(th_old), _coords(th_new)
    lp, b0, b1 = [], [], []
    for t in ts:
        th = _theta_from(c0 + t * (c1 - c0), K)
        lp.append(em1d_post(x, th)[1])
        b0.append(em1d_elbo(x, th, q_old))
        b1.append(em1d_elbo(x, th, q_new))
    return np.array(lp), np.array(b0), np.array(b1)


# =========================================================================== 15.4.5 incremental EM (2-D)
def suff_stats(X, G):
    """Sufficient statistics of the M step: N_k, sum_n gamma x_n, sum_n gamma x_n x_n^T."""
    return G.sum(0), G.T @ X, np.einsum("nk,ni,nj->kij", G, X, X)


def params_from_stats(S0, S1, S2, N, reg=0.0):
    mu = S1 / S0[:, None]
    Sig = S2 / S0[:, None, None] - np.einsum("ki,kj->kij", mu, mu)
    if reg:
        Sig = Sig + reg * np.eye(S1.shape[1])
    return S0 / N, mu, Sig


def incremental_mean_update(mu_old, Nk_old, g_old, g_new, xm):
    """(15.60)-(15.61): the new mean and effective count after point m's responsibility changes."""
    Nk_new = Nk_old + g_new - g_old
    return mu_old + (g_new - g_old) / Nk_new * (xm - mu_old), Nk_new


def incremental_cov_update(Sig_old, mu_old, Nk_old, g_old, g_new, xm):
    """Exercise 15.24: the covariance after the change, from the old mean and covariance only."""
    mu_new, Nk_new = incremental_mean_update(mu_old, Nk_old, g_old, g_new, xm)
    d = g_new - g_old
    S2 = Nk_old * (Sig_old + np.outer(mu_old, mu_old)) + d * np.outer(xm, xm)
    return S2 / Nk_new - np.outer(mu_new, mu_new), mu_new, Nk_new


def em_incremental(X, pi, mu, Sig, passes, rng):
    """Incremental EM (Section 15.4.5): after one full E step, each step recomputes one point's
    responsibilities and updates the statistics; parameters are refreshed after every point.
    Returns ln p(X) at the end of each pass (index 0 = after the initial full E and M step)."""
    N = len(X)
    G, _ = gmm_resp(X, pi, mu, Sig)
    S0, S1, S2 = suff_stats(X, G)
    pi, mu, Sig = params_from_stats(S0, S1, S2, N)
    lls = [gmm_loglik(X, pi, mu, Sig)]
    for _ in range(passes):
        for m in rng.permutation(N):
            g, _ = gmm_resp(X[m:m + 1], pi, mu, Sig)
            d = g[0] - G[m]
            S0 = S0 + d
            S1 = S1 + d[:, None] * X[m]
            S2 = S2 + d[:, None, None] * np.outer(X[m], X[m])
            G[m] = g[0]
            pi, mu, Sig = params_from_stats(S0, S1, S2, N)
        lls.append(gmm_loglik(X, pi, mu, Sig))
    return lls


# =========================================================================== exports for the demos
def export_images_json(path=None):
    """../data/ch15-images.json: the two test images of kmeans-quantisation-demo.html (uint8 RGB, base64)."""
    d = {"W": 240, "H": 180, "images": {}}
    for k, f in IMAGES.items():
        d["images"][k] = base64.b64encode(f().tobytes()).decode("ascii")
    path = path or os.path.join(WEB_DATA, "ch15-images.json")
    os.makedirs(os.path.dirname(path), exist_ok=True)
    with open(path, "w") as fh:
        json.dump(d, fh, separators=(",", ":"))
    print("wrote", path, "(%d bytes)" % os.path.getsize(path))


def export_digits_json(path=None, n_each=200):
    """../data/ch15-digits.json: the first 200 training images of each digit 0-9, binarised at 0.5 and
    packed 8 pixels per byte (row-major, most significant bit first), for bernoulli-mixture-demo.html."""
    X, y = digits(tuple(range(10)), n_each)
    packed = np.packbits(X.astype(np.uint8), axis=1)
    d = {"n_each": n_each, "D": 784, "labels": y.tolist(), "bits": base64.b64encode(packed.tobytes()).decode("ascii")}
    path = path or os.path.join(WEB_DATA, "ch15-digits.json")
    with open(path, "w") as fh:
        json.dump(d, fh, separators=(",", ":"))
    print("wrote", path, "(%d bytes)" % os.path.getsize(path))


# =========================================================================== figures
def _square(ax, lim=LIM):
    ax.set_xlim(*lim)
    ax.set_ylim(*lim)
    ax.set_aspect("equal")
    ax.set_xticks([-2, 0, 2])
    ax.set_yticks([-2, 0, 2])


def _ellipse(ax, mu, S, col, nsd=1.0, lw=1.8, fill=False, alpha=1.0):
    x, y = common.ellipse_xy(mu, S, nsd)
    if fill:
        ax.fill(x, y, color=col, alpha=alpha, lw=0)
    else:
        ax.plot(x, y, color=col, lw=lw)


def _mix_colours(G, cols):
    rgb = np.array([plt.matplotlib.colors.to_rgb(c) for c in cols])
    return np.clip(G @ rgb, 0, 1)


def fig_15_1(out_dir=None):
    """Figure 15.1: K-means on the standardised Old Faithful data, E and M steps in turn."""
    X = common.old_faithful(standardize=True)
    hist = kmeans(X, BOOK_CENTRES)
    fig, axes = plt.subplots(3, 3, figsize=(8.0, 8.0))
    cols = np.array([common.RED, common.BLUE])
    panels = [("init", 0)] + [(s, i) for i in range(4) for s in ("E", "M")]
    for ax, (lab, (kind, i)) in zip(axes.ravel(), zip("abcdefghi", panels)):
        if kind == "init":
            ax.scatter(X[:, 0], X[:, 1], s=9, c=common.GREEN, lw=0)
            mu = BOOK_CENTRES
        else:
            h = hist[min(i, len(hist) - 1)]
            ax.scatter(X[:, 0], X[:, 1], s=9, c=cols[h["r"]], lw=0)
            mu = h["mu_old"] if kind == "E" else h["mu"]
            if kind == "E":   # perpendicular bisector of the two centres
                a, b = mu
                mid, d = (a + b) / 2, b - a
                t = np.linspace(-6, 6, 2)
                p = mid[None, :] + t[:, None] * np.array([-d[1], d[0]])
                ax.plot(p[:, 0], p[:, 1], color=common.MAGENTA, lw=1.6)
        for k in range(2):
            ax.plot(*mu[k], "x", color="white", ms=12, mew=4.5)
            ax.plot(*mu[k], "x", color=cols[k], ms=11, mew=2.2)
        common.panel_label(ax, lab)
        _square(ax)
    fig.tight_layout()
    savefig(fig, CH, "fig15-1", out_dir)
    print("  J after E and M steps:", [(round(h["JE"], 2), round(h["JM"], 2)) for h in hist])


def fig_15_2(out_dir=None):
    """Figure 15.2: the distortion J after each E step (blue) and M step (red) of Figure 15.1."""
    X = common.old_faithful(standardize=True)
    hist = kmeans(X, BOOK_CENTRES)[:4]
    J = [v for h in hist for v in (h["JE"], h["JM"])]
    x = np.arange(1, len(J) + 1)
    fig, ax = plt.subplots(figsize=(4.6, 2.8))
    ax.plot(x, J, color="0.6", lw=1.2, zorder=1)
    ax.scatter(x[0::2], J[0::2], s=50, color=common.BLUE, zorder=2, label="after E step")
    ax.scatter(x[1::2], J[1::2], s=50, color=common.RED, zorder=2, label="after M step")
    ax.set_xticks(np.arange(1.5, 9, 2), [1, 2, 3, 4])
    ax.set_xlabel("E-M cycle")
    ax.set_ylabel("$J$")
    ax.set_ylim(0, 1100)
    ax.legend(frameon=False)
    savefig(fig, CH, "fig15-2", out_dir)
    print("  J:", [round(v, 2) for v in J])


FIG3_SEED = 2


def fig15_3_results():
    img = landscape()
    V = image_vectors(img)
    res = {}
    for K in (2, 3, 10):
        mu, r, Js = vq_kmeans(V, K, "pp", FIG3_SEED, max_iter=300)
        res[K] = (mu, r, Js)
    return img, V, res


def fig_15_3(out_dir=None):
    """Figure 15.3: K-means segmentation and vector quantisation of our 240 x 180 test image, K = 2, 3, 10."""
    img, V, res = fig15_3_results()
    H, W, _ = img.shape
    fig, axes = plt.subplots(1, 4, figsize=(10.6, 2.45))
    N = H * W
    for ax, K in zip(axes[:3], (2, 3, 10)):
        mu, r, Js = res[K]
        ax.imshow(vectors_image(mu[r], H, W))
        b = vq_bits(N, K)
        ax.set_title("$K = %d$: %s bits (%.1f%%)" % (K, format(b, ","), 100 * b / (24 * N)), fontsize=9.5)
    axes[3].imshow(img)
    axes[3].set_title("original: %s bits" % format(24 * N, ","), fontsize=9.5)
    for ax in axes:
        ax.set_xticks([])
        ax.set_yticks([])
    fig.tight_layout()
    savefig(fig, CH, "fig15-3", out_dir)
    for K in (2, 3, 10):
        print("  K=%d: J=%.3f after %d half steps, PSNR %.2f dB, bits %d" % (K, res[K][2][-1], len(res[K][2]), psnr(res[K][2][-1], N), vq_bits(N, K)))


def vq_rate_distortion(img, Ks=(2, 4, 8, 16, 32, 64, 128, 256), seed=1, max_iter=40):
    H, W, _ = img.shape
    N = H * W
    out = {}
    for block in (1, 2):
        V = image_vectors(img, block)
        rows = []
        for K in Ks:
            mu, r, Js = vq_kmeans(V, K, "pp", seed, max_iter=max_iter, fast=True)
            J = float(((V - mu[r]) ** 2).sum())
            rows.append((K, vq_bits(N, K, block) / N, psnr(J, N)))
        out[block] = rows
    return out


def fig_15_s1(out_dir=None):
    """Figure 15.S1 (ours): rate-distortion of K-means vector quantisation, pixels against 2 x 2 blocks."""
    img = landscape()
    H, W, _ = img.shape
    rd = vq_rate_distortion(img)
    fig, axes = plt.subplots(1, 3, figsize=(10.4, 2.9), gridspec_kw=dict(width_ratios=[1.25, 1, 1]))
    ax = axes[0]
    for block, col, lab in ((1, common.BLUE, "single pixels ($D=3$)"), (2, common.RED, "2 x 2 blocks ($D=12$)")):
        rows = rd[block]
        ax.plot([r[1] for r in rows], [r[2] for r in rows], "o-", color=col, label=lab, ms=4)
        for K, bpp, p in rows:
            if K in (4, 16, 256):
                ax.annotate("$K=%d$" % K, (bpp, p), textcoords="offset points", xytext=(4, -10), fontsize=8, color=col)
    ax.set_xlabel("bits per pixel")
    ax.set_ylabel("PSNR (dB)")
    ax.legend(frameon=False, loc="lower right", fontsize=8.5)
    for ax, block, K in ((axes[1], 1, 4), (axes[2], 2, 256)):
        V = image_vectors(img, block)
        mu, r, Js = vq_kmeans(V, K, "pp", 1, max_iter=40, fast=True)
        J = float(((V - mu[r]) ** 2).sum())
        ax.imshow(np.clip(vectors_image(mu[r], H, W, block), 0, 1))
        ax.set_title("%s, $K=%d$: %.2f bits/pixel, %.1f dB" % ("pixels" if block == 1 else "2 x 2 blocks", K,
                     vq_bits(H * W, K, block) / (H * W), psnr(J, H * W)), fontsize=8.5)
        ax.set_xticks([])
        ax.set_yticks([])
    common.panel_label(axes[0], "a", "upper left")
    fig.tight_layout()
    savefig(fig, CH, "fig15-s1", out_dir)
    for b in (1, 2):
        print("  block %d:" % b, [(K, round(bpp, 3), round(p, 2)) for K, bpp, p in rd[b]])


def mix2d():
    from ch03_standard_distributions import MIX2D
    return MIX2D["pi"], np.array(MIX2D["mu"]), np.array(MIX2D["S"])


def fig_15_5(out_dir=None):
    """Figure 15.5: 500 samples from a three-component mixture: complete data, incomplete data and responsibilities."""
    pi, mu, S = mix2d()
    rng = np.random.default_rng(5)
    X, z = gmm_sample(500, pi, mu, S, rng)
    G, _ = gmm_resp(X, pi, mu, S)
    cols = [common.RED, common.GREEN, common.BLUE]
    fig, axes = plt.subplots(1, 3, figsize=(9.0, 3.1))
    axes[0].scatter(X[:, 0], X[:, 1], s=7, c=np.array(cols)[z], lw=0)
    axes[1].scatter(X[:, 0], X[:, 1], s=7, c="k", lw=0)
    axes[2].scatter(X[:, 0], X[:, 1], s=7, c=_mix_colours(G, cols), lw=0)
    for ax, lab in zip(axes, "abc"):
        ax.set_xlim(0, 1)
        ax.set_ylim(0, 1)
        ax.set_aspect("equal")
        ax.set_xticks([0, 0.5, 1])
        ax.set_yticks([0, 0.5, 1])
        common.panel_label(ax, lab)
    fig.tight_layout()
    savefig(fig, CH, "fig15-5", out_dir)
    print("  component counts", np.bincount(z, minlength=3).tolist(), "; fraction of points whose largest responsibility is the true component %.3f"
          % np.mean(G.argmax(1) == z))


FIG6_X = np.array([-1.6, -1.1, -0.7, -0.2, 0.3, 0.9, 1.8])


def fig_15_6(out_dir=None):
    """Figure 15.6: a two-component mixture in which one component collapses onto a data point."""
    x = FIG6_X
    m, s = x.mean(), x.std()
    t = np.linspace(-3, 3.5, 1500)
    fig, axes = plt.subplots(1, 2, figsize=(8.6, 2.9))
    ax = axes[0]
    for sj, ls in ((0.15, "-"),):
        p = 6 / 7 * np.exp(-(t - m) ** 2 / (2 * s * s)) / (s * math.sqrt(2 * math.pi)) + \
            1 / 7 * np.exp(-(t - x[-1]) ** 2 / (2 * sj * sj)) / (sj * math.sqrt(2 * math.pi))
        ax.plot(t, p, color=common.BLUE, ls=ls)
    ax.plot(x, np.zeros_like(x), "o", color=common.RED, ms=6, clip_on=False, zorder=3)
    ax.set_xlabel("$x$")
    ax.set_ylabel("$p(x)$")
    ax.set_ylim(0, None)
    ax.set_yticks([])
    common.panel_label(ax, "a")
    ax = axes[1]
    sig = np.logspace(-4, 0, 60)
    lm = [float(np.sum(np.log(6 / 7 * np.exp(-(x - m) ** 2 / (2 * s * s)) / (s * math.sqrt(2 * math.pi)) +
                              1 / 7 * np.exp(-(x - x[-1]) ** 2 / (2 * q * q)) / (q * math.sqrt(2 * math.pi))))) for q in sig]
    l1 = [float(np.sum(-0.5 * np.log(2 * np.pi * q * q) - (x - x[-1]) ** 2 / (2 * q * q))) for q in sig]
    ax.semilogx(sig, lm, color=common.BLUE, label="mixture: one component on $x_7$")
    ax.semilogx(sig, np.maximum(l1, -60), color=common.GREEN, ls="--", label="single Gaussian on $x_7$")
    ax.set_xlabel(r"$\sigma_j$")
    ax.set_ylabel(r"$\ln p(\mathbf{X})$")
    ax.set_ylim(-60, 20)
    ax.legend(frameon=False, fontsize=8.5, loc="lower left")
    common.panel_label(ax, "b", "upper right")
    fig.tight_layout()
    savefig(fig, CH, "fig15-6", out_dir)
    print("  ln p at sigma_j = 1e-2, 1e-4: %.2f, %.2f" % (lm[np.argmin(abs(sig - 1e-2))], lm[0]))


def fig_15_7(out_dir=None):
    """Figure 15.7: EM for a two-component Gaussian mixture on Old Faithful (L = 1, 2, 5, 20)."""
    X = common.old_faithful(standardize=True)
    hist = gmm_em(X, [0.5, 0.5], BOOK_CENTRES, [BOOK_COV * np.eye(2)] * 2, 20)
    cols = [common.RED, common.BLUE]
    fig, axes = plt.subplots(2, 3, figsize=(8.0, 5.5))
    spec = [("a", 0, None), ("b", 0, 0), ("c", 1, 0), ("d", 2, 1), ("e", 5, 4), ("f", 20, 19)]
    for ax, (lab, L, gL) in zip(axes.ravel(), spec):
        st = hist[L]
        ax.scatter(X[:, 0], X[:, 1], s=9, lw=0, c=common.GREEN if gL is None else _mix_colours(hist[gL]["gamma"], cols))
        for k in range(2):
            _ellipse(ax, st["mu"][k], st["Sig"][k], cols[k])
        if L:
            ax.text(0.95, 0.06, "$L = %d$" % L, transform=ax.transAxes, ha="right", fontsize=10)
        common.panel_label(ax, lab)
        _square(ax)
    fig.tight_layout()
    savefig(fig, CH, "fig15-7", out_dir)
    print("  ln p(X) at L = 0, 1, 2, 5, 20:", [round(hist[L]["loglik"], 3) for L in (0, 1, 2, 5, 20)])


MOONS_SEED = 8


def fig_15_8(out_dir=None):
    """Figure 15.8: a 16-component Gaussian mixture fitted to two-moons data."""
    rng = np.random.default_rng(MOONS_SEED)
    X = two_moons(300, 0.06, rng)
    pi, mu, Sig, ll = gmm_fit(X, 16, rng)
    fig, ax = plt.subplots(figsize=(5.0, 3.4))
    for k in range(16):
        _ellipse(ax, mu[k], Sig[k], common.BLUE, nsd=1.5, fill=True, alpha=0.35)
    ax.scatter(X[:, 0], X[:, 1], s=8, color=common.RED, lw=0, zorder=3)
    ax.set_aspect("equal")
    ax.set_xlabel("$x_1$")
    ax.set_ylabel("$x_2$")
    ax.set_xticks([])
    ax.set_yticks([])
    savefig(fig, CH, "fig15-8", out_dir)
    print("  ln p(X)/N = %.3f; weights from %.3f to %.3f" % (ll / len(X), pi.min(), pi.max()))


def moons_heldout(Ks=range(1, 31), n_train=300, n_test=3000, restarts=3):
    rng = np.random.default_rng(MOONS_SEED + 1)
    Xtr, Xte = two_moons(n_train, 0.06, rng), two_moons(n_test, 0.06, rng)
    rows = []
    for K in Ks:
        best = None
        for _ in range(restarts):
            pi, mu, Sig, ll = gmm_fit(Xtr, K, rng)
            if best is None or ll > best[3]:
                best = (pi, mu, Sig, ll)
        rows.append((K, best[3] / n_train, gmm_loglik(Xte, *best[:3]) / n_test))
    return rows


def fig_15_s2(out_dir=None):
    """Figure 15.S2 (ours): training and held-out log likelihood per point of mixtures on two moons, against K."""
    rows = moons_heldout()
    K = [r[0] for r in rows]
    fig, ax = plt.subplots(figsize=(5.2, 3.0))
    ax.plot(K, [r[1] for r in rows], "o-", ms=3.5, color=common.BLUE, label="training data (300 points)")
    ax.plot(K, [r[2] for r in rows], "s-", ms=3.5, color=common.RED, label="held-out data (3000 points)")
    best = max(rows, key=lambda r: r[2])
    ax.axvline(best[0], color="0.6", ls=":", lw=1)
    ax.set_xlabel("number of components $K$")
    ax.set_ylabel(r"$\ln p(\mathbf{x})$ per point")
    ax.legend(frameon=False, fontsize=8.5, loc="lower right")
    savefig(fig, CH, "fig15-s2", out_dir)
    print("  best held-out K = %d (%.3f); K=1: %.3f, K=16: %.3f, K=30: train %.3f test %.3f"
          % (best[0], best[2], rows[0][2], rows[15][2], rows[-1][1], rows[-1][2]))


FIG12_SEED = 4


def fig_15_12(out_dir=None):
    """Figure 15.12: a mixture of three Bernoulli distributions fitted by 10 EM iterations to binarised digits 2, 3, 4."""
    X, y = digits()
    pi, mu, G, lls = bern_em_js(X, 3, "book", FIG12_SEED, 10)
    lab = G.argmax(1)
    major = [int(np.bincount(y[lab == k], minlength=5)[2:].argmax() + 2) if np.any(lab == k) else 9 for k in range(3)]
    order = np.argsort(major)
    agree = sum(int(np.sum((lab == k) & (y == major[k]))) for k in range(3))
    cmap = LinearSegmentedColormap.from_list("ink", ["#ffffff", "#1a1aa8"])
    fig = plt.figure(figsize=(7.6, 3.4))
    ex = [0, 210, 420, 120, 330]
    for i, n in enumerate(ex):
        ax = fig.add_axes([0.01 + 0.198 * i, 0.53, 0.18, 0.44])
        ax.imshow(X[n].reshape(28, 28), cmap=cmap, vmin=0, vmax=1, interpolation="nearest")
    imgs = [mu[k] for k in order] + [X.mean(0)]
    for i, im in enumerate(imgs):
        ax = fig.add_axes([0.01 + 0.198 * i + (0.198 if i == 3 else 0), 0.03, 0.18, 0.44])
        ax.imshow(im.reshape(28, 28), cmap=cmap, vmin=0, vmax=1, interpolation="nearest")
    for ax in fig.axes:
        ax.set_xticks([])
        ax.set_yticks([])
    savefig(fig, CH, "fig15-12", out_dir)
    print("  ln p(X) after 0..10 M steps:", [round(v, 2) for v in lls])
    print("  pi (display order) %s, digits %s, %d of 600 in their digit's component"
          % (np.round(pi[order], 4).tolist(), [major[k] for k in order], agree))


# ==== Figures 15.13 to 15.16: the ELBO for the data of em-elbo-steps-demo.html, preset 1
ELBO_PRESET = dict(data="two", K=2, init="theta0",
                   theta0=dict(pi=[0.3, 0.7], mu=[-2.5, 0.5], v=[0.5, 3.0]))


def elbo_preset_run(halfsteps=12):
    x = em1d_data(ELBO_PRESET["data"])
    return x, em1d_run(x, ELBO_PRESET["K"], "spread", 1, halfsteps, theta0=ELBO_PRESET["theta0"])


def _elbo_fig(name, idx, title, out_dir):
    """One of the bar diagrams 15.13-15.15: ln p(X|theta) (grey), L(q, theta) (blue) and KL(q||p) (red)."""
    x, recs = elbo_preset_run()
    r = recs[idx]
    lnp, L, KL = r["lnp"], r["L"], max(r["KL"], 0.0)
    old = recs[idx - 1]["lnp"] if r["kind"] == "M" else None
    lo = min(L, old if old is not None else L)
    span = max(lnp - lo, 8.0)
    base, top = lo - 0.45 * span, lnp + 0.3 * span
    fig, ax = plt.subplots(figsize=(3.5, 3.4))
    w = 0.5
    ax.bar(0, lnp - base, w, bottom=base, color="#cfd8e6", edgecolor="k", lw=0.8)
    ax.bar(1, L - base, w, bottom=base, color=common.BLUE, alpha=0.85, edgecolor="k", lw=0.8)
    if KL > 1e-9:
        ax.bar(1, KL, w, bottom=L, color=common.RED, alpha=0.85, edgecolor="k", lw=0.8)
    ax.text(0, lnp + 0.03 * span, r"$\ln p(\mathbf{X}|\theta)$" + "\n%.2f" % lnp, ha="center", va="bottom", fontsize=8.5)
    ax.text(1, base + 0.05 * span, r"$\mathcal{L}(q,\theta)$" + "\n%.2f" % L, ha="center", va="bottom", fontsize=8.5, color="white")
    ax.annotate(r"KL$(q\|p)$" + "\n= %.2f" % KL, (1 + w / 2, L + KL / 2), xytext=(1.33, L + KL / 2), fontsize=8.5,
                va="center", color=common.RED)
    if old is not None:
        ax.axhline(old, color="0.35", ls=":", lw=1)
        ax.text(-0.45, old - 0.02 * span, r"old $\ln p$ = %.2f" % old, fontsize=7.5, va="top", color="0.3")
    ax.set_xlim(-0.5, 2.2)
    ax.set_ylim(base, top)
    ax.set_xticks([])
    ax.set_ylabel("nats")
    ax.set_title(title, fontsize=9.5)
    savefig(fig, CH, name, out_dir)
    print("  %s: ln p = %.4f, L = %.4f, KL = %.4f" % (r["kind"], lnp, L, KL))


def fig_15_13(out_dir=None):
    """Figure 15.13: ln p(X|theta) = L(q, theta) + KL(q||p), computed for q = uniform responsibilities."""
    _elbo_fig("fig15-13", 0, r"any $q$ (here $q_{nk}=1/2$)", out_dir)


def fig_15_14(out_dir=None):
    """Figure 15.14: after the E step q is the posterior and the KL term vanishes."""
    _elbo_fig("fig15-14", 1, "after the E step", out_dir)


def fig_15_15(out_dir=None):
    """Figure 15.15: after the M step both terms have grown; KL is positive again."""
    _elbo_fig("fig15-15", 2, "after the M step", out_dir)


def fig_15_16(out_dir=None):
    """Figure 15.16: ln p(X|theta) (red) and the bounds at theta_old (blue) and theta_new (green) along a line in parameter space."""
    x, recs = elbo_preset_run()
    E1, M1, E2 = recs[1], recs[2], recs[3]
    ts = np.linspace(-0.6, 2.2, 281)
    lp, b0, b1 = em1d_slice(x, E1["theta"], M1["theta"], E1["q"], E2["q"], ts)
    fig, ax = plt.subplots(figsize=(5.2, 3.3))
    ax.plot(ts, lp, color=common.RED, lw=2, label=r"$\ln p(\mathbf{X}|\theta)$")
    ax.plot(ts, b0, color=common.BLUE, label=r"$\mathcal{L}(q_{\rm old},\theta)$")
    ax.plot(ts, b1, color=common.GREEN, label=r"$\mathcal{L}(q_{\rm new},\theta)$")
    for t, lab in ((0, r"$\theta^{\rm old}$"), (1, r"$\theta^{\rm new}$")):
        ax.axvline(t, color="0.5", ls=":", lw=1)
        ax.text(t, 1.01, lab, ha="center", va="bottom", fontsize=9, transform=ax.get_xaxis_transform())
    lo = max(min(lp.min(), b0.min(), b1.min()), lp.max() - 40)
    ax.set_ylim(lo, lp.max() + 4)
    ax.set_xlabel(r"position $t$ on the line $\theta(t)=\theta^{\rm old}+t(\theta^{\rm new}-\theta^{\rm old})$")
    ax.set_ylabel("nats")
    ax.legend(frameon=False, fontsize=8.5, loc="lower center")
    savefig(fig, CH, "fig15-16", out_dir)
    i0, i1 = np.argmin(abs(ts)), np.argmin(abs(ts - 1))
    print("  at t=0: ln p %.4f, L_old %.4f; at t=1: ln p %.4f, L_old %.4f, L_new %.4f; argmax L_old at t=%.3f"
          % (lp[i0], b0[i0], lp[i1], b0[i1], b1[i1], ts[np.argmax(b0)]))


def fig_15_s3(out_dir=None):
    """Figure 15.S3 (ours): K-means as the eps -> 0 limit of EM with covariances eps I."""
    X = common.old_faithful(standardize=True)
    km = kmeans(X, BOOK_CENTRES)
    mu_km, r = km[-1]["mu"], km[-1]["r"]
    eps = np.logspace(-6, 0.5, 50)
    gap = [np.abs(resp_eps(X, mu_km, e) - np.eye(2)[r]).max() for e in eps]
    J = distortion(X, r, mu_km)
    Qs = []
    for e in eps:
        G = resp_eps(X, mu_km, e)
        Q = np.sum(G * (np.log(0.5) - X.shape[1] / 2 * np.log(2 * np.pi * e)
                        - ((X[:, None, :] - mu_km[None]) ** 2).sum(-1) / (2 * e)))
        Qs.append(e * Q)
    fig, axes = plt.subplots(1, 3, figsize=(10.6, 3.0))
    ax = axes[0]
    ax.loglog(eps, np.maximum(gap, 1e-17), color=common.BLUE)
    ax.set_xlabel(r"$\epsilon$")
    ax.set_ylabel(r"$\max_{n,k}|\gamma(z_{nk})-r_{nk}|$")
    ax.set_ylim(1e-17, 2)
    ax = axes[1]
    ax.semilogx(eps, Qs, color=common.BLUE, label=r"$\epsilon\,Q$")
    ax.axhline(-J / 2, color=common.RED, ls="--", label=r"$-J/2$")
    ax.set_ylim(-J / 2 - 60, -J / 2 + 15)
    ax.set_xlabel(r"$\epsilon$")
    ax.legend(frameon=False, fontsize=8.5)
    ax = axes[2]
    X0 = X
    ax.scatter(X0[:, 0], X0[:, 1], s=5, c="0.75", lw=0)
    for e, col in ((1.0, common.GREEN), (0.3, common.ORANGE), (0.1, common.PURPLE), (0.01, common.BLUE)):
        m = em_eps(X, BOOK_CENTRES, e, 300)
        ax.plot(m[:, 0], m[:, 1], "o", color=col, ms=6, label=r"EM, $\epsilon=%g$" % e)
    ax.plot(mu_km[:, 0], mu_km[:, 1], "x", color=common.RED, ms=11, mew=2.2, label="K-means")
    ax.legend(frameon=False, fontsize=7.5, loc="upper left")
    _square(ax)
    for a, lab in zip(axes, "abc"):
        common.panel_label(a, lab, "upper right" if lab != "c" else "lower right")
    fig.tight_layout()
    savefig(fig, CH, "fig15-s3", out_dir)
    print("  max |gamma - r| at eps = 0.1, 0.01: %.2e, %.2e; eps Q at eps=1e-6: %.4f vs -J/2 = %.4f"
          % (gap[np.argmin(abs(eps - 0.1))], gap[np.argmin(abs(eps - 0.01))], Qs[0], -J / 2))


def em_variants_oldfaithful(passes=25, seed=0):
    """ln p(X) per pass for batch EM, incremental EM, ECM (one block per M step) and a gradient M step,
    all from the Figure 15.7 start."""
    X = common.old_faithful(standardize=True)
    N = len(X)
    pi0, mu0, S0 = np.array([0.5, 0.5]), BOOK_CENTRES.astype(float), np.array([BOOK_COV * np.eye(2)] * 2)
    batch = [h["loglik"] for h in gmm_em(X, pi0, mu0, S0, passes)]
    inc = em_incremental(X, pi0, mu0, S0, passes, np.random.default_rng(seed))
    # ECM: E step, then means only; E step, then covariances only; E step, then weights only; ...
    pi, mu, Sig = pi0.copy(), mu0.copy(), S0.copy()
    ecm = [gmm_loglik(X, pi, mu, Sig)]
    for t in range(passes):
        G, _ = gmm_resp(X, pi, mu, Sig)
        p2, m2, s2 = gmm_m(X, G)
        if t % 3 == 0:
            mu = m2
        elif t % 3 == 1:
            Nk = G.sum(0)
            Sig = np.array([(G[:, k, None] * (X - mu[k])).T @ (X - mu[k]) / Nk[k] for k in range(2)])
        else:
            pi = p2
        ecm.append(gmm_loglik(X, pi, mu, Sig))
    # GEM: the means move a fraction eta of the way to their exact M-step value (a gradient step on Q
    # preconditioned by Sigma_k/N_k); 0 < eta < 2 still increases Q. Covariances and weights exactly.
    grads = {}
    for eta in (0.3, 1.8):
        pi, mu, Sig = pi0.copy(), mu0.copy(), S0.copy()
        out = [gmm_loglik(X, pi, mu, Sig)]
        for t in range(passes):
            G, _ = gmm_resp(X, pi, mu, Sig)
            Nk = G.sum(0)
            xbar = (G.T @ X) / Nk[:, None]
            mu = mu + eta * (xbar - mu)
            Sig = np.array([(G[:, k, None] * (X - mu[k])).T @ (X - mu[k]) / Nk[k] for k in range(2)])
            pi = Nk / N
            out.append(gmm_loglik(X, pi, mu, Sig))
        grads[eta] = out
    return dict(batch=batch, incremental=inc, ecm=ecm, grad=grads)


def fig_15_s4(out_dir=None):
    """Figure 15.S4 (ours): batch, incremental, ECM and gradient-M-step EM on Old Faithful."""
    r = em_variants_oldfaithful()
    best = max(max(r["batch"]), max(r["incremental"]))
    fig, axes = plt.subplots(1, 2, figsize=(9.6, 3.1))
    for ax, logy in ((axes[0], False), (axes[1], True)):
        for key, col, lab in (("batch", common.BLUE, "batch EM (Algorithm 15.2)"),
                              ("incremental", common.RED, "incremental EM (15.60)"),
                              ("ecm", common.GREEN, "ECM: one block per M step")):
            v = np.array(r[key])
            y = best - v + 1e-12 if logy else v
            ax.plot(np.arange(len(v)), y, "o-", ms=3, color=col, label=lab)
        for eta, ls in ((0.3, ":"), (1.8, "--")):
            v = np.array(r["grad"][eta])
            ax.plot(np.arange(len(v)), best - v + 1e-12 if logy else v, ls, color=common.PURPLE,
                    label=r"partial M step for the means, $\eta=%g$" % eta)
        ax.set_xlabel("passes through the data")
        if logy:
            ax.set_yscale("log")
            ax.set_ylabel(r"$\ln p^\star-\ln p(\mathbf{X}|\theta)$")
        else:
            ax.set_ylabel(r"$\ln p(\mathbf{X}|\theta)$")
            ax.set_ylim(r["batch"][1] - 40, best + 10)
    axes[0].legend(frameon=False, fontsize=7.5, loc="lower right")
    fig.tight_layout()
    savefig(fig, CH, "fig15-s4", out_dir)
    for key in ("batch", "incremental", "ecm"):
        print("  %s: after 1, 3, 10 passes %s" % (key, [round(r[key][i], 3) for i in (1, 3, 10)]))


FIGURES = {"15.1": fig_15_1, "15.2": fig_15_2, "15.3": fig_15_3, "15.S1": fig_15_s1, "15.5": fig_15_5,
           "15.6": fig_15_6, "15.7": fig_15_7, "15.8": fig_15_8, "15.S2": fig_15_s2, "15.S3": fig_15_s3,
           "15.12": fig_15_12, "15.13": fig_15_13, "15.14": fig_15_14, "15.15": fig_15_15, "15.16": fig_15_16,
           "15.S4": fig_15_s4}

if __name__ == "__main__":
    import sys
    if "--export" in sys.argv:
        export_images_json()
        export_digits_json()
    else:
        run(FIGURES, CH)
