"""Murphy (2023), Chapter 28: Latent factor models (and Supplement Chapter 28).

Companion code for Chapter 28 of K. P. Murphy, Probabilistic Machine Learning: Advanced Topics
(MIT Press, 2023; December 2025 draft), pp. 929-978, and the supplement, pp. 213-218. Written from
scratch with numpy, scipy, matplotlib and scikit-learn (for data and a few library cross-checks),
to be read next to the lecture notes (../ch28-latent-factor-models.html).

Methods implemented here (all of them by hand; the library versions are used only to confirm them)
* Section 28.2: Gaussian mixtures by EM (gmm_em), mixtures of Bernoullis (bmm_em), Gaussian scale
  mixtures (gsm_density, gsm_posterior_mean), the expected-patch-log-likelihood prior of Zoran and Weiss
  with half-quadratic splitting for denoising and inpainting (epll_restore).
* Section 28.3: mixture of factor analysers and of PPCA models by EM (MFA, with the likelihood computed
  through the matrix inversion and determinant lemmas), imputation with a mixture (28.94)-(28.96), binary PCA by
  variational EM with the Jaakkola-Jordan bound (binary_pca), the GP latent variable model (gplvm).
* Section 28.4: non-negative matrix factorisation by the multiplicative Poisson-EM updates (nmf_kl).
* Section 28.5 and Supplement 28.1: latent Dirichlet allocation by collapsed Gibbs sampling (lda_gibbs),
  batch and online variational Bayes (lda_vb_batch, lda_vb_online).
* Section 28.6: FastICA (fastica), the maximum-likelihood ICA objective on whitened data (ica_nll),
  dictionary learning for sparse coding with FISTA (sparse_dictionary).

Data. The book's data sets are not bundled, so each stand-in is named in the caption: scikit-learn's two
sample photographs (natural image patches) for Figures 28.4, 28.5 and 28.34; scikit-learn's 8x8 digits
for the mixture of factor analysers (28.11-28.14) and the GP-LVM (28.19); MNIST for Figures 28.3 and
28.21; the 20 newsgroups corpus for Figure S28.3; simulation elsewhere.

Skipped figures, with reasons: 28.7, 28.15 to 28.17, 28.20, 28.23, 28.28, 28.30 and S28.1 are diagrams (graphical models and
schematics); 28.9 and 28.10 are a picture and a table from a variational-Bayes ARD mixture of factor analysers (Beal 2003)
whose code and runs are not in the book; 28.22 (US Senate roll calls of 2003), 28.24 to 28.27, 28.29 and 28.31 and Table 28.2
(the TASA, Science and NIPS text corpora and published topic displays) need data that are not available. Figures 28.11 to 28.14
(CelebA faces, 12,288 pixels, 300 components, GPU training) are reproduced as stand-ins on the 8x8 digits, Figure 28.19
(motion capture) on digits, Figure 28.21 (faces) on MNIST, Figure S28.3 (Wikipedia) on 20 newsgroups, and Figures 28.4, 28.5 and
28.34 on scikit-learn's sample photographs.

Own figures (not in the book), named as in the notes: x28.1 (scale mixtures: log densities and shrinkage rules), x28.2 (the ICA
objective as a function of the rotation angle) and x28.3 (a full-covariance mixture against mixtures of factor analysers:
held-out likelihood against the training-set size, and parameter counts).
"""
import os
import sys
import json
import time

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

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

CH = 28
CACHE_DIR = os.path.join(HERE, "cache", "ch28")
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
os.makedirs(CACHE_DIR, exist_ok=True)
os.makedirs(DATA_OUT, exist_ok=True)
logsumexp = special.logsumexp


def _out(out_dir=None):
    return out_dir


def save_json(name, obj):
    path = os.path.join(DATA_OUT, name)
    with open(path, "w") as f:
        json.dump(obj, f, separators=(",", ":"))
    print("wrote", os.path.relpath(path, os.getcwd()), "(%.0f kB)" % (os.path.getsize(path) / 1e3))


def gray(img):
    """Luminance in [0, 1] of an RGB uint8 image."""
    return (img[..., :3] @ np.array([0.299, 0.587, 0.114])) / 255.0


def sample_images():
    from sklearn.datasets import load_sample_images
    ims = load_sample_images().images
    return [gray(i) for i in ims]          # china, flower


def extract_patches(img, p, n, rng):
    """n random p x p patches of a grey image, as rows."""
    H, W = img.shape
    ii = rng.integers(0, H - p, n)
    jj = rng.integers(0, W - p, n)
    return np.stack([img[i:i + p, j:j + p].ravel() for i, j in zip(ii, jj)])


# =========================================================================== mixtures (28.2)
def kmeans_pp(X, K, rng):
    """K-means++ seeding followed by 10 Lloyd steps; returns the centres."""
    N = len(X)
    C = [X[rng.integers(N)]]
    for _ in range(K - 1):
        d2 = np.min(((X[:, None, :] - np.array(C)[None]) ** 2).sum(-1), axis=1)
        C.append(X[rng.choice(N, p=d2 / d2.sum())])
    C = np.array(C)
    for _ in range(10):
        a = np.argmin(((X[:, None, :] - C[None]) ** 2).sum(-1), axis=1)
        for k in range(K):
            if np.any(a == k):
                C[k] = X[a == k].mean(0)
    return C


def gauss_logpdf_chol(X, mu, S):
    L = np.linalg.cholesky(S)
    Z = linalg.solve_triangular(L, (X - mu).T, lower=True)
    return -0.5 * (X.shape[1] * np.log(2 * np.pi) + (Z ** 2).sum(0)) - np.log(np.diag(L)).sum()


def gmm_em(X, K, iters=100, seed=0, reg=1e-6, zero_mean=False, init=None, tol=1e-9, verbose=False):
    """EM for a Gaussian mixture with full covariances (28.7), (28.8). Returns a dict with pi, mu, S, ll (the
    log-likelihood after every iteration). zero_mean=True fixes every mean at 0 (used for image patches)."""
    rng = np.random.default_rng(seed)
    N, D = X.shape
    if init is None:
        mu = kmeans_pp(X, K, rng) if not zero_mean else np.zeros((K, D))
        if zero_mean:   # random responsibilities
            R = rng.dirichlet(np.ones(K), N)
        else:
            d2 = ((X[:, None, :] - mu[None]) ** 2).sum(-1)
            R = np.eye(K)[np.argmin(d2, 1)] * 0.9 + 0.1 / K
    else:
        R = init
    ll_hist = []
    pi = mu = S = None
    for it in range(iters):
        # M step from responsibilities R
        Nk = R.sum(0) + 1e-12
        pi = Nk / N
        mu = np.zeros((K, D)) if zero_mean else (R.T @ X) / Nk[:, None]
        S = np.empty((K, D, D))
        for k in range(K):
            Xc = X - mu[k]
            S[k] = (R[:, k, None] * Xc).T @ Xc / Nk[k] + reg * np.eye(D)
        # E step
        logp = np.stack([np.log(pi[k]) + gauss_logpdf_chol(X, mu[k], S[k]) for k in range(K)], 1)
        lse = logsumexp(logp, axis=1)
        R = np.exp(logp - lse[:, None])
        ll_hist.append(lse.sum())
        if verbose and it % 10 == 0:
            print(it, ll_hist[-1])
        if it > 0 and abs(ll_hist[-1] - ll_hist[-2]) < tol * abs(ll_hist[-1]):
            break
    return dict(pi=pi, mu=mu, S=S, ll=np.array(ll_hist), R=R)


def gmm_logpdf(X, g):
    return logsumexp(np.stack([np.log(g["pi"][k]) + gauss_logpdf_chol(X, g["mu"][k], g["S"][k])
                               for k in range(len(g["pi"]))], 1), axis=1)


def bmm_em(X, K, iters=60, seed=0, eps=1e-3):
    """EM for a mixture of Bernoullis (28.11) on binary rows X. Returns pi (K), mu (K, D), ll history.
    A tiny Beta(1+eps, 1+eps)-style smoothing keeps the probabilities away from 0 and 1."""
    rng = np.random.default_rng(seed)
    N, D = X.shape
    mu = rng.uniform(0.25, 0.75, (K, D))
    pi = np.ones(K) / K
    hist = []
    for it in range(iters):
        logp = np.log(pi)[None] + X @ np.log(mu).T + (1 - X) @ np.log(1 - mu).T
        lse = logsumexp(logp, axis=1)
        R = np.exp(logp - lse[:, None])
        hist.append(lse.sum())
        Nk = R.sum(0)
        pi = Nk / N
        mu = np.clip((R.T @ X + eps) / (Nk[:, None] + 2 * eps), 1e-4, 1 - 1e-4)
    return dict(pi=pi, mu=mu, ll=np.array(hist), R=R)


# ===== Gaussian scale mixtures
def gsm_density(x, family, **p):
    """Marginal density of x = eps*z, z ~ N(0, 1) (sigma_0 = 1), for the scale laws of Section 28.2.3.
    family: 'gauss' (eps = 1), 'student' (eps^2 ~ IG(nu/2, nu/2)), 'laplace' (eps^2 ~ Exp(rate lam^2/2)),
    'spike' (eps ~ Ber(pi), plus a spike of mass 1-pi at 0, returned as the slab density only), 'horseshoe'
    (eps ~ half-Cauchy(1), by numerical integration)."""
    x = np.asarray(x, float)
    if family == "gauss":
        return stats.norm.pdf(x)
    if family == "student":
        nu = p["nu"]
        return stats.t.pdf(x, nu)
    if family == "laplace":
        lam = p["lam"]
        return 0.5 * lam * np.exp(-lam * np.abs(x))
    if family == "horseshoe":
        from scipy import integrate
        out = np.empty_like(x)
        for i, xi in np.ndenumerate(x):
            xi = max(abs(xi), 1e-3)            # the horseshoe density is infinite at 0 (logarithmic spike)
            g = lambda u: stats.norm.pdf(xi, scale=np.exp(u)) * 2 * np.exp(u) / (np.pi * (1 + np.exp(2 * u)))
            out[i] = integrate.quad(g, -25, 25, limit=400)[0]
        return out
    raise ValueError(family)


def gsm_marginal_by_integration(x, family, **p):
    """The same marginals computed from the definition (28.12), p(x) = int N(x|0, eps^2) p(eps) d eps."""
    from scipy import integrate
    x = np.atleast_1d(np.asarray(x, float))
    out = np.empty_like(x)
    for i, xi in enumerate(x):
        if family == "student":
            nu = p["nu"]
            f = lambda v: stats.norm.pdf(xi, scale=np.sqrt(v)) * stats.invgamma.pdf(v, nu / 2, scale=nu / 2)
        elif family == "laplace":
            lam = p["lam"]
            f = lambda v: stats.norm.pdf(xi, scale=np.sqrt(v)) * (lam ** 2 / 2) * np.exp(-lam ** 2 * v / 2)
        elif family == "horseshoe":
            f = lambda e: stats.norm.pdf(xi, scale=e) * 2 / (np.pi * (1 + e * e))
        out[i] = integrate.quad(f, 0, np.inf, limit=400)[0]
    return out


def gsm_posterior_mean(y, family, noise=1.0, **p):
    """Shrinkage rule E[x | y] for y = x + N(0, noise^2), x from a scale-mixture prior with sigma_0 = 1:
    computed by one-dimensional quadrature (for the spike and slab prior in closed form)."""
    y = np.atleast_1d(np.asarray(y, float))
    if family == "spike":
        pi = p["pi"]
        s2 = 1.0
        # slab: x ~ N(0, 1): y ~ N(0, 1 + noise^2); spike: y ~ N(0, noise^2)
        a = pi * stats.norm.pdf(y, scale=np.sqrt(s2 + noise ** 2))
        b = (1 - pi) * stats.norm.pdf(y, scale=noise)
        w = a / (a + b)
        return w * y * s2 / (s2 + noise ** 2)
    if family == "gauss":
        return y / (1 + noise ** 2)
    if family == "horseshoe":
        # E[x | y] = y E[kappa(eps) | y] with p(eps | y) proportional to p(eps) N(y | 0, eps^2 + s^2): a smooth integral in u = log eps
        u = np.linspace(-25, 25, 4001)
        e2 = np.exp(2 * u)
        w0 = 2 * np.exp(u) / (np.pi * (1 + e2))
        out = np.empty_like(y)
        for i, yi in enumerate(y):
            w = w0 * stats.norm.pdf(yi, scale=np.sqrt(e2 + noise ** 2))
            out[i] = yi * (w * e2 / (e2 + noise ** 2)).sum() / w.sum()
        return out
    xs = np.linspace(-40, 40, 40001)
    prior = gsm_density(xs, family, **p)
    xg = xs
    out = np.empty_like(y)
    for i, yi in enumerate(y):
        lik = stats.norm.pdf(yi - xg, scale=noise)
        w = prior * lik
        out[i] = (w * xg).sum() / w.sum()
    return out


# ===== the patch prior of Section 28.2.4
def epll_fit(patches, K, seed=0, iters=30):
    """GMM prior for zero-mean patches: the DC component is removed first, so the prior is on the patch minus
    its mean, with K zero-mean full-covariance components (Zoran and Weiss 2011)."""
    P = patches - patches.mean(1, keepdims=True)
    g = gmm_em(P, K, iters=iters, seed=seed, zero_mean=True, reg=1e-5)
    return g


def _patch_idx(H, W, p):
    ii, jj = np.meshgrid(np.arange(H - p + 1), np.arange(W - p + 1), indexing="ij")
    r = (ii.ravel()[:, None, None] + np.arange(p)[None, :, None])
    c = (jj.ravel()[:, None, None] + np.arange(p)[None, None, :])
    return (r * W + c).reshape(len(ii.ravel()), p * p)


def epll_patch_step(Xp, g, beta):
    """One 'patch step': for each (mean-removed) patch pick the MAP component c* = argmax p(c) N(x_i | 0, S_c + I/beta)
    ((28.17) with W = I and noise variance 1/beta) and return the Wiener estimate S_c (S_c + I/beta)^{-1} x_i (28.18)."""
    N, D = Xp.shape
    K = len(g["pi"])
    best = np.full(N, -np.inf)
    arg = np.zeros(N, int)
    est = np.zeros_like(Xp)
    for k in range(K):
        lam, V = np.linalg.eigh(g["S"][k])
        lam = np.maximum(lam, 1e-9)
        T = Xp @ V
        v = lam + 1.0 / beta
        ll = np.log(g["pi"][k]) - 0.5 * (np.log(v).sum() + (T ** 2 / v).sum(1))
        better = ll > best
        best = np.where(better, ll, best)
        arg = np.where(better, k, arg)
        est[better] = ((lam / v) * T[better]) @ V.T
    return est, arg


def epll_restore(y, g, sigma, mask=None, p=8, betas=None, x0=None, stride=1):
    """EPLL restoration by half-quadratic splitting. Objective (28.19): ||W x - y||^2/(2 sigma^2) - EPLL(x), with
    W = I (denoising) or W = diag(mask) (inpainting). Each outer step: patch step above, then the x step
    x = (lam M + beta c)^{-1} (lam M y + beta sum_i P_i^T z_i), where c counts how many patches cover each pixel."""
    H, Wd = y.shape
    idx = _patch_idx(H, Wd, p)[::stride]
    cover = np.zeros(H * Wd)
    np.add.at(cover, idx.ravel(), 1.0)
    lam = 1.0 / sigma ** 2
    M = np.ones(H * Wd) if mask is None else mask.ravel().astype(float)
    yv = y.ravel() * M
    x = (yv.copy() if x0 is None else x0.ravel().copy())
    if betas is None:
        betas = np.array([1, 4, 8, 16, 32, 64, 128]) / sigma ** 2
    for b in betas:
        Xp = x[idx]
        mean = Xp.mean(1, keepdims=True)
        est, _ = epll_patch_step(Xp - mean, g, b)
        Z = est + mean
        num = np.zeros(H * Wd)
        np.add.at(num, idx.ravel(), Z.ravel())
        x = (lam * M * yv + b * num) / (lam * M + b * cover)
    return x.reshape(H, Wd)


# =========================================================================== factor analysis (28.3)
def fa_loglik(X, mu, W, psi):
    """Log-likelihood of the rows of X under N(mu, W W^T + diag(psi)), computed with the matrix
    inversion lemma (28.47), (28.49) and the determinant lemma (28.50): O(N L D + L^3) instead of O(D^3)."""
    D, L = W.shape
    Xc = X - mu
    Wp = W / psi[:, None]                       # Psi^{-1} W
    Mm = np.eye(L) + W.T @ Wp                   # I + W^T Psi^{-1} W   (the matrix called L in the book)
    Lc = np.linalg.cholesky(Mm)
    T = Xc / psi                                # Psi^{-1} x
    u = linalg.solve_triangular(Lc, (Wp.T @ Xc.T), lower=True)      # L^{-1} W^T Psi^{-1} x
    maha = (Xc * T).sum(1) - (u ** 2).sum(0)
    logdet = 2 * np.log(np.diag(Lc)).sum() + np.log(psi).sum()
    return -0.5 * (D * np.log(2 * np.pi) + logdet + maha)


class MFA:
    """Mixture of factor analysers (Section 28.3.3) fitted by EM, (28.80)-(28.93): component k has mean mu_k and
    loading matrix W_k (D x L), the noise covariance Psi is shared and diagonal (iso=True: Psi = sigma^2 I, the mixture of
    PPCA models). K = 1 is ordinary factor analysis (PPCA when iso)."""

    def __init__(self, K, L, iso=False, seed=0, psi_min=1e-4):
        self.K, self.L, self.iso, self.seed, self.psi_min = K, L, iso, seed, psi_min

    def _init(self, X):
        rng = np.random.default_rng(self.seed)
        N, D = X.shape
        K, L = self.K, self.L
        self.mu = kmeans_pp(X, K, rng) if K > 1 else X.mean(0, keepdims=True)
        a = np.argmin(((X[:, None, :] - self.mu[None]) ** 2).sum(-1), 1)
        self.W = np.zeros((K, D, L))
        resid = np.zeros(D)
        for k in range(K):
            Xk = X[a == k] if np.sum(a == k) > L + 1 else X
            ev, U = np.linalg.eigh(np.cov(Xk.T) + 1e-6 * np.eye(D))
            ev, U = ev[::-1], U[:, ::-1]
            s2 = max(ev[L:].mean(), 1e-4)
            self.W[k] = U[:, :L] * np.sqrt(np.maximum(ev[:L] - s2, 1e-6))
            resid += s2
        self.psi = np.full(D, resid / K) if self.iso else np.maximum(np.var(X - self.mu[a], 0), 1e-3)
        self.pi = np.ones(K) / K

    def component_loglik(self, X):
        return np.stack([np.log(self.pi[k]) + fa_loglik(X, self.mu[k], self.W[k], self.psi) for k in range(self.K)], 1)

    def loglik(self, X):
        return logsumexp(self.component_loglik(X), axis=1)

    def fit(self, X, iters=100, tol=1e-8):
        N, D = X.shape
        K, L = self.K, self.L
        self._init(X)
        self.ll = []
        for it in range(iters):
            lp = self.component_loglik(X)                      # E step: responsibilities (28.86)
            lse = logsumexp(lp, axis=1)
            R = np.exp(lp - lse[:, None])
            self.ll.append(lse.sum())
            if it > 0 and abs(self.ll[-1] - self.ll[-2]) < tol * abs(self.ll[-1]):
                break
            newW = np.zeros_like(self.W)
            newmu = np.zeros_like(self.mu)
            acc = np.zeros(D)
            for k in range(K):
                Wp = self.W[k] / self.psi[:, None]
                Mm = np.eye(L) + self.W[k].T @ Wp
                Minv = np.linalg.inv(Mm)
                B = Minv @ Wp.T                                  # B_k = W^T (Psi + W W^T)^{-1}
                Ez = (X - self.mu[k]) @ B.T                      # N x L, E[z | x, k]
                r = R[:, k]
                rs = r.sum()
                Ezt = np.hstack([Ez, np.ones((N, 1))])
                S_xz = (X * r[:, None]).T @ Ezt                  # sum r x E[z~]^T  (D x (L+1))
                S_zz = np.zeros((L + 1, L + 1))
                S_zz[:L, :L] = rs * Minv + (Ez * r[:, None]).T @ Ez
                S_zz[:L, L] = S_zz[L, :L] = (Ez * r[:, None]).sum(0)
                S_zz[L, L] = rs
                Wt = S_xz @ np.linalg.inv(S_zz + 1e-10 * np.eye(L + 1))          # (28.89)
                newW[k], newmu[k] = Wt[:, :L], Wt[:, L]
                # (28.92): diag of sum_i r_ik (x_i - W~ E[z~]) x_i^T = diag(sum r x x^T) - diag(W~ S_xz^T)
                acc += ((X ** 2) * r[:, None]).sum(0) - (Wt * S_xz).sum(1)
            self.W, self.mu = newW, newmu
            self.pi = R.mean(0)
            psi = np.maximum(acc / N, self.psi_min)
            self.psi = np.full(D, psi.mean()) if self.iso else psi
        return self

    def responsibilities(self, X):
        lp = self.component_loglik(X)
        return np.exp(lp - logsumexp(lp, axis=1)[:, None])

    def sample(self, n, rng):
        k = rng.choice(self.K, n, p=self.pi)
        D = self.mu.shape[1]
        z = rng.standard_normal((n, self.L))
        x = np.einsum("nl,ndl->nd", z, self.W[k]) + self.mu[k] + rng.standard_normal((n, D)) * np.sqrt(self.psi)
        return x, k

    def impute(self, x, obs):
        """Most probable component and conditional-mean completion given the observed coordinates obs (28.94)-(28.96).
        Returns (completed vector with the observed entries kept, k*, E[z | x_obs, k*])."""
        o = np.asarray(obs, bool)
        best, kb = -np.inf, 0
        for k in range(self.K):
            Wk = self.W[k][o]
            val = np.log(self.pi[k]) + fa_loglik(x[o][None], self.mu[k][o], Wk, self.psi[o])[0]
            if val > best:
                best, kb = val, k
        Wo = self.W[kb][o] / self.psi[o][:, None]
        Sig = np.linalg.inv(np.eye(self.L) + self.W[kb][o].T @ Wo)       # (28.60)
        zhat = Sig @ (Wo.T @ (x[o] - self.mu[kb][o]))                     # (28.61)
        full = self.W[kb] @ zhat + self.mu[kb]
        out = np.where(o, x, full)
        return out, kb, zhat


# ===== binary PCA (28.3.5.1)
def jj_lambda(xi):
    xi = np.maximum(np.abs(xi), 1e-8)
    return (special.expit(xi) - 0.5) / (2 * xi)


def binary_pca(X, L, iters=60, seed=0):
    """Variational EM for p(x_d = 1 | z) = sigmoid(w_d^T z + b_d), z ~ N(0, I_L), with the Jaakkola-Jordan
    bound log sigmoid(s a) >= log sigmoid(xi) + (s a - xi)/2 - lam(xi)(a^2 - xi^2), s = 2x - 1.
    The E step gives a Gaussian q(z_n) = N(m_n, S_n) and updates xi_nd; the M step updates [w_d, b_d]. Returns a
    dict with W (D x L), b, m (N x L), S (N x L x L) and the bound after every iteration."""
    rng = np.random.default_rng(seed)
    N, D = X.shape
    s = 2 * X - 1
    W = 0.3 * rng.standard_normal((D, L))
    b = np.zeros(D)
    xi = np.ones((N, D))
    bound = []
    for it in range(iters):
        lam = jj_lambda(xi)
        S = np.empty((N, L, L))
        m = np.empty((N, L))
        for n in range(N):
            P = np.eye(L) + 2 * (W.T * lam[n]) @ W
            S[n] = np.linalg.inv(P)
            m[n] = S[n] @ (W.T @ (s[n] / 2 - 2 * lam[n] * b))
        # variational parameters xi^2 = E[a^2]
        a_mean = m @ W.T + b
        a_var = np.einsum("dl,nlk,dk->nd", W, S, W)
        xi = np.sqrt(a_mean ** 2 + a_var)
        lam = jj_lambda(xi)
        # M step for [w_d, b_d]
        for d in range(D):
            Ez2 = np.zeros((L + 1, L + 1))
            Ez2[:L, :L] = (lam[:, d, None, None] * (S + m[:, :, None] * m[:, None, :])).sum(0)
            Ez2[:L, L] = Ez2[L, :L] = (lam[:, d, None] * m).sum(0)
            Ez2[L, L] = lam[:, d].sum()
            rhs = np.concatenate([(0.5 * s[:, d, None] * m).sum(0), [0.5 * s[:, d].sum()]])
            sol = np.linalg.solve(2 * Ez2 + 1e-8 * np.eye(L + 1), rhs)
            W[d], b[d] = sol[:L], sol[L]
        # the bound
        a_mean = m @ W.T + b
        a_var = np.einsum("dl,nlk,dk->nd", W, S, W)
        Ea2 = a_mean ** 2 + a_var
        ll = (np.log(special.expit(xi)) + (s * a_mean - xi) / 2 - lam * (Ea2 - xi ** 2)).sum()
        kl = 0.5 * sum(np.trace(S[n]) + m[n] @ m[n] - L - np.linalg.slogdet(S[n])[1] for n in range(N))
        bound.append(ll - kl)
    return dict(W=W, b=b, m=m, S=S, bound=np.array(bound))


def binary_pca_predict(res, n_samples=400, seed=0):
    """p(x_nd = 1 | x_n) = int sigmoid(w_d^T z + b_d) q(z_n) dz by Monte Carlo (28.119)."""
    rng = np.random.default_rng(seed)
    N, L = res["m"].shape
    out = np.zeros((N, len(res["b"])))
    for n in range(N):
        Z = rng.multivariate_normal(res["m"][n], res["S"][n], n_samples)
        out[n] = special.expit(Z @ res["W"].T + res["b"]).mean(0)
    return out


# ===== GP-LVM (28.3.7)
def gplvm(Y, Q=2, kernel="ard", iters=300, seed=0, init=None, lr=0.05, lin_sigma=None):
    """Maximum likelihood GP-LVM (Lawrence 2005): maximise log p(Y | Z, theta) of (28.125)-(28.126) over the latent
    points Z (N x Q) and the kernel hyperparameters. Y is centred; the kernel is an ARD squared exponential
    (kernel='ard') or the linear kernel Z Z^T + sigma^2 I (kernel='linear', the dual of PPCA). Returns Z, parameters, the
    log-likelihood history. PyTorch is used only for the gradient."""
    import torch
    torch.manual_seed(seed)
    N, D = Y.shape
    Yt = torch.as_tensor(Y - Y.mean(0), dtype=torch.float64)
    Z0 = init if init is not None else linalg.svd(Y - Y.mean(0), full_matrices=False)[0][:, :Q] * 1.0
    Z = torch.nn.Parameter(torch.as_tensor(Z0 / Z0.std(0), dtype=torch.float64) * 1.0)
    log_ls = torch.nn.Parameter(torch.zeros(Q, dtype=torch.float64))
    log_sf = torch.nn.Parameter(torch.zeros((), dtype=torch.float64))
    log_sn = torch.nn.Parameter(torch.tensor(-1.0, dtype=torch.float64))
    params = [Z] + ([log_ls, log_sf, log_sn] if kernel == "ard" else [])
    if kernel == "linear":
        log_sn = torch.tensor(np.log(lin_sigma or 0.5), dtype=torch.float64)
    opt = torch.optim.Adam(params, lr=lr)

    def K_mat():
        if kernel == "linear":
            return Z @ Z.T + torch.exp(2 * log_sn) * torch.eye(N, dtype=torch.float64)
        Zs = Z / torch.exp(log_ls)
        d2 = ((Zs[:, None, :] - Zs[None]) ** 2).sum(-1)
        return torch.exp(2 * log_sf) * torch.exp(-0.5 * d2) + (torch.exp(2 * log_sn) + 1e-6) * torch.eye(N, dtype=torch.float64)

    def nll():
        K = K_mat()
        Lc = torch.linalg.cholesky(K)
        A = torch.cholesky_solve(Yt, Lc)
        return 0.5 * D * 2 * torch.log(torch.diagonal(Lc)).sum() + 0.5 * (Yt * A).sum() + 0.5 * N * D * np.log(2 * np.pi)

    hist = []
    for it in range(iters):
        opt.zero_grad()
        loss = nll()
        loss.backward()
        opt.step()
        hist.append(-loss.item())
    out = dict(Z=Z.detach().numpy(), ll=np.array(hist))
    if kernel == "ard":
        out.update(ls=np.exp(log_ls.detach().numpy()), sf=float(np.exp(log_sf.item())), sn=float(np.exp(log_sn.item())))
    return out


def gplvm_loglik_linear(Y, Z, sigma):
    """log p(Y | Z, sigma^2) of (28.126) for the linear kernel, evaluated directly."""
    N, D = Y.shape
    Yc = Y - Y.mean(0)
    K = Z @ Z.T + sigma ** 2 * np.eye(N)
    sign, ld = np.linalg.slogdet(K)
    return -0.5 * (N * D * np.log(2 * np.pi) + D * ld + np.trace(np.linalg.solve(K, Yc @ Yc.T)))


# =========================================================================== non-negative matrix factorisation (28.4.1)
def nmf_kl(X, K, iters=200, seed=0, eps=1e-10):
    """Multiplicative updates for the generalised KL divergence, which are the EM updates of the Poisson model
    x_nd ~ Poi(sum_k z_nk w_kd) (Lee and Seung 2001; Cemgil 2009). X is N x D; returns Z (N x K), W (K x D) and the
    divergence after every iteration."""
    rng = np.random.default_rng(seed)
    N, D = X.shape
    Z = rng.uniform(0.5, 1.5, (N, K)) * np.sqrt(X.mean() / K)
    W = rng.uniform(0.5, 1.5, (K, D)) * np.sqrt(X.mean() / K)
    hist = []
    for it in range(iters):
        R = X / (Z @ W + eps)
        Z *= (R @ W.T) / (W.sum(1)[None, :] + eps)
        R = X / (Z @ W + eps)
        W *= (Z.T @ R) / (Z.sum(0)[:, None] + eps)
        M = Z @ W + eps
        hist.append(float((X * np.log((X + eps) / M) - X + M).sum()))
    return Z, W, np.array(hist)


# =========================================================================== topic models (28.5, Supplement 28.1)
def lda_sample(rng, D, V, K, alpha, beta, length, topics=None):
    """Draw D documents from LDA. Returns the list of word-index arrays, the true topics (K x V) and proportions."""
    Wt = rng.dirichlet(np.full(V, beta), K) if topics is None else topics
    Th = rng.dirichlet(np.full(K, alpha), D)
    docs = []
    for d in range(D):
        Ld = length if np.isscalar(length) else int(rng.integers(*length))
        z = rng.choice(K, Ld, p=Th[d])
        docs.append(np.array([rng.choice(V, p=Wt[k]) for k in z]))
    return docs, Wt, Th


def lda_gibbs(docs, V, K, alpha, beta, sweeps, seed=0, record=()):
    """Collapsed Gibbs sampling for LDA, Supplement (28.8): the topic of word l of document i is drawn from
    p(m_il = k | rest) proportional to (N_vk^- + beta)/(N_k^- + V beta) * (N_ik^- + alpha). Returns the final state, the count
    matrices and the log of the collapsed joint p(x, m) after every sweep. record: sweeps at which to keep the
    assignments."""
    rng = np.random.default_rng(seed)
    Nd = len(docs)
    m = [rng.integers(0, K, len(d)) for d in docs]
    Nvk = np.zeros((V, K))
    Nik = np.zeros((Nd, K))
    for i, d in enumerate(docs):
        for w, k in zip(d, m[i]):
            Nvk[w, k] += 1
            Nik[i, k] += 1
    Nk = Nvk.sum(0)
    snaps, logj = {}, []
    if 0 in record:
        snaps[0] = [a.copy() for a in m]
    for sweep in range(1, sweeps + 1):
        for i, d in enumerate(docs):
            for l, w in enumerate(d):
                k = m[i][l]
                Nvk[w, k] -= 1
                Nik[i, k] -= 1
                Nk[k] -= 1
                p = (Nvk[w] + beta) / (Nk + V * beta) * (Nik[i] + alpha)
                k = rng.choice(K, p=p / p.sum())
                m[i][l] = k
                Nvk[w, k] += 1
                Nik[i, k] += 1
                Nk[k] += 1
        logj.append(lda_collapsed_logjoint(Nvk, Nik, alpha, beta))
        if sweep in record:
            snaps[sweep] = [a.copy() for a in m]
    return dict(m=m, Nvk=Nvk, Nik=Nik, Nk=Nk, logjoint=np.array(logj), snaps=snaps)


def lda_collapsed_logjoint(Nvk, Nik, alpha, beta):
    """log p(x, m | alpha, beta) from Supplement (28.5) and (28.7) (the multinomial coefficients of the words are omitted)."""
    V, K = Nvk.shape
    Nd = Nik.shape[0]
    Li = Nik.sum(1)
    lp_m = Nd * (special.gammaln(K * alpha) - K * special.gammaln(alpha)) + (special.gammaln(Nik + alpha).sum()
                                                                            - special.gammaln(Li + K * alpha).sum())
    Nk = Nvk.sum(0)
    lp_x = K * (special.gammaln(V * beta) - V * special.gammaln(beta)) + (special.gammaln(Nvk + beta).sum()
                                                                          - special.gammaln(Nk + V * beta).sum())
    return lp_m + lp_x


def lda_gibbs_estimates(res, alpha, beta):
    Nvk, Nk = res["Nvk"], res["Nk"]
    V = Nvk.shape[0]
    return ((Nvk + beta) / (Nk + V * beta)).T          # K x V, p(word | topic)


def _doc_estep(ids, cts, expElogW, alpha, iters=100, tol=1e-4, rng=None):
    """Mean-field E step for one document in the count version, Supplement (28.15), (28.16): iterate
    gamma_k = alpha + sum_d x_d phi_dk with phi_dk proportional to W_dk exp(E log z_k). expElogW is V x K (W for EM, exp E[log W] for VB)."""
    K = expElogW.shape[1]
    gam = np.full(K, alpha + cts.sum() / K) if rng is None else rng.gamma(100.0, 0.01, K)
    Ew = expElogW[ids]
    for _ in range(iters):
        old = gam
        eElogz = np.exp(special.digamma(gam) - special.digamma(gam.sum()))
        phinorm = Ew @ eElogz + 1e-100
        gam = alpha + eElogz * (Ew.T @ (cts / phinorm))
        if np.mean(np.abs(gam - old)) < tol:
            break
    eElogz = np.exp(special.digamma(gam) - special.digamma(gam.sum()))
    phinorm = Ew @ eElogz + 1e-100
    return gam, phinorm, eElogz


def lda_vb_batch(Xcsr, K, alpha, beta, iters, seed=0, init_lambda=None, callback=None):
    """Batch variational Bayes for LDA, Algorithm S28.1. Xcsr: scipy CSR matrix of counts (docs x V).
    q(w_k) = Dir(lambda_k). Returns lambda (K x V)."""
    rng = np.random.default_rng(seed)
    N, V = Xcsr.shape
    lam = rng.gamma(100.0, 0.01, (K, V)) if init_lambda is None else init_lambda.copy()
    for it in range(iters):
        expElogW = np.exp(special.digamma(lam) - special.digamma(lam.sum(1, keepdims=True))).T      # V x K
        ss = np.zeros((K, V))
        for n in range(N):
            ids = Xcsr.indices[Xcsr.indptr[n]:Xcsr.indptr[n + 1]]
            cts = Xcsr.data[Xcsr.indptr[n]:Xcsr.indptr[n + 1]].astype(float)
            gam, phinorm, eElogz = _doc_estep(ids, cts, expElogW, alpha)
            ss[:, ids] += np.outer(eElogz, cts / phinorm)
        lam = beta + ss * expElogW.T
        if callback:
            callback(it + 1, lam)
    return lam


def lda_vb_online(Xcsr, K, alpha, beta, n_steps, batch=64, tau0=1.0, kappa=0.7, seed=0, callback=None, check=()):
    """Online variational Bayes for LDA, Algorithm S28.2 (Hoffman, Blei and Bach 2010): lambda <- (1 - rho_t) lambda +
    rho_t (beta + (N/|B|) sum_{n in B} x_nd phi_ndk), rho_t = (tau0 + t)^(-kappa)."""
    rng = np.random.default_rng(seed)
    N, V = Xcsr.shape
    lam = rng.gamma(100.0, 0.01, (K, V))
    for t in range(n_steps):
        rho = (tau0 + t) ** (-kappa)
        idx = rng.integers(0, N, batch)
        expElogW = np.exp(special.digamma(lam) - special.digamma(lam.sum(1, keepdims=True))).T
        ss = np.zeros((K, V))
        for n in idx:
            ids = Xcsr.indices[Xcsr.indptr[n]:Xcsr.indptr[n + 1]]
            cts = Xcsr.data[Xcsr.indptr[n]:Xcsr.indptr[n + 1]].astype(float)
            gam, phinorm, eElogz = _doc_estep(ids, cts, expElogW, alpha)
            ss[:, ids] += np.outer(eElogz, cts / phinorm)
        lam = (1 - rho) * lam + rho * (beta + (N / batch) * ss * expElogW.T)
        if callback and (t + 1) in check:
            callback(t + 1, lam)
    return lam


def lda_heldout_perplexity(lam, alpha, Xobs, Xheld):
    """Document-completion perplexity: infer gamma from the observed half of each test document, predict the held-out half
    with E[theta] E[W]."""
    K, V = lam.shape
    expElogW = np.exp(special.digamma(lam) - special.digamma(lam.sum(1, keepdims=True))).T
    Ew = (lam / lam.sum(1, keepdims=True))
    tot, nw = 0.0, 0
    for n in range(Xobs.shape[0]):
        ids = Xobs.indices[Xobs.indptr[n]:Xobs.indptr[n + 1]]
        cts = Xobs.data[Xobs.indptr[n]:Xobs.indptr[n + 1]].astype(float)
        if len(ids) == 0:
            continue
        gam, _, _ = _doc_estep(ids, cts, expElogW, alpha)
        theta = gam / gam.sum()
        hid = Xheld.indices[Xheld.indptr[n]:Xheld.indptr[n + 1]]
        hc = Xheld.data[Xheld.indptr[n]:Xheld.indptr[n + 1]].astype(float)
        if len(hid) == 0:
            continue
        p = theta @ Ew[:, hid]
        tot += (hc * np.log(p + 1e-300)).sum()
        nw += hc.sum()
    return float(np.exp(-tot / nw))


# =========================================================================== independent components analysis (28.6)
def whiten(X):
    """Centre and whiten the rows of X (the SVD route of Section 28.6.3): returns Xw with identity covariance, the mean, and the
    matrix Wh with Xw = (X - mean) Wh^T."""
    mu = X.mean(0)
    Xc = X - mu
    ev, U = np.linalg.eigh(np.cov(Xc.T, bias=True))
    Wh = (U / np.sqrt(ev)).T
    return Xc @ Wh.T, mu, Wh


def logcosh_nll(z):
    """-log of the unit-variance logistic density (28.147), summed over components, per observation."""
    s = np.sqrt(3) / np.pi
    return (2 * np.log(np.cosh(z / (2 * s))) + np.log(4 * s)).sum(-1)


def ica_nll(V, Xw, nll=logcosh_nll):
    """Average negative log-likelihood (28.150) of an orthogonal unmixing matrix V on whitened data (rows)."""
    return float(np.mean(nll(Xw @ V.T)))


def _sym_decorr(W):
    ev, U = np.linalg.eigh(W @ W.T)
    return (U / np.sqrt(ev)) @ U.T @ W


def fastica(X, n_comp=None, iters=200, tol=1e-9, seed=0, nonlin="logcosh"):
    """Symmetric FastICA (Hyvarinen and Oja 2000): on whitened data the fixed-point step is w <- E[x g(w^T x)] - E[g'(w^T x)] w
    followed by symmetric decorrelation, g = tanh (logcosh) or g(u) = u^3 (kurtosis). Returns the sources S (N x D), the
    orthogonal V and the whitening."""
    rng = np.random.default_rng(seed)
    Xw, mu, Wh = whiten(X)
    N, D = Xw.shape
    Wm = _sym_decorr(rng.standard_normal((D, D)))
    for it in range(iters):
        U = Xw @ Wm.T
        if nonlin == "logcosh":
            g, gp = np.tanh(U), 1 - np.tanh(U) ** 2
        else:
            g, gp = U ** 3, 3 * U ** 2
        Wn = (g.T @ Xw) / N - gp.mean(0)[:, None] * Wm
        Wn = _sym_decorr(Wn)
        lim = np.max(np.abs(np.abs(np.sum(Wn * Wm, 1)) - 1))
        Wm = Wn
        if lim < tol:
            break
    return dict(S=Xw @ Wm.T, V=Wm, Wh=Wh, mu=mu, iters=it + 1)


def amari_error(P):
    """Amari index of a global matrix P = (estimated unmixing) x (true mixing): 0 iff P is a scaled permutation."""
    P = np.abs(P)
    D = P.shape[0]
    r = (P.sum(1) / P.max(1) - 1).sum()
    c = (P.sum(0) / P.max(0) - 1).sum()
    return float((r + c) / (2 * D * (D - 1)))


# =========================================================================== sparse coding (28.6.5)
def fista_lasso(Wd, X, lam, iters=100, Z0=None):
    """Minimise 0.5 ||x_n - W z_n||^2 + lam ||z_n||_1 for every row x_n of X (FISTA). Wd: D x K dictionary. Returns Z (N x K)."""
    N = X.shape[0]
    K = Wd.shape[1]
    G = Wd.T @ Wd
    Lc = np.linalg.eigvalsh(G).max()
    B = X @ Wd
    Z = np.zeros((N, K)) if Z0 is None else Z0.copy()
    Y, t = Z.copy(), 1.0
    for _ in range(iters):
        grad = Y @ G - B
        Zn = Y - grad / Lc
        Zn = np.sign(Zn) * np.maximum(np.abs(Zn) - lam / Lc, 0)
        tn = (1 + np.sqrt(1 + 4 * t * t)) / 2
        Y = Zn + (t - 1) / tn * (Zn - Z)
        Z, t = Zn, tn
    return Z


def sparse_dictionary(X, K, lam, outer=25, inner=60, seed=0, hist=None):
    """Dictionary learning for (28.160): alternate the sparse-coding step (an l1-regularised least squares problem for every
    example, FISTA) and the dictionary step (least squares, then the columns are rescaled to unit norm, which removes the
    scale ambiguity W -> cW, Z -> Z/c). Returns W (D x K) and the codes Z (N x K)."""
    rng = np.random.default_rng(seed)
    N, D = X.shape
    W = X[rng.choice(N, K, replace=False)].T.copy()
    W /= np.linalg.norm(W, axis=0)
    Z = np.zeros((N, K))
    for it in range(outer):
        Z = fista_lasso(W, X, lam, inner, Z0=Z)
        A = Z.T @ Z + 1e-6 * np.eye(K)
        W = np.linalg.solve(A, Z.T @ X).T
        nrm = np.linalg.norm(W, axis=0)
        dead = nrm < 1e-8
        W[:, dead] = rng.standard_normal((D, dead.sum()))
        nrm = np.linalg.norm(W, axis=0)
        W /= nrm
        if hist is not None:
            Zc = fista_lasso(W, X, lam, 30, Z0=Z)
            hist.append(0.5 * ((X - Zc @ W.T) ** 2).sum() / N + lam * np.abs(Zc).sum() / N)
    return W, Z


# =========================================================================== figures: mixtures
def montage(imgs, nrow, ncol, shape, pad=1, bg=1.0, vmin=None, vmax=None, centre=False):
    """Tile images (rows of imgs reshaped to shape) into one array; with centre=True every image is scaled by its own
    maximum absolute value so that 0 is mid-grey."""
    h, w = shape
    out = np.full((nrow * (h + pad) + pad, ncol * (w + pad) + pad), bg)
    for t, im in enumerate(imgs[:nrow * ncol]):
        r, c = divmod(t, ncol)
        a = im.reshape(shape)
        if centre:
            a = 0.5 + 0.5 * a / (np.abs(a).max() + 1e-12)
        elif vmin is not None:
            a = (a - vmin) / (vmax - vmin)
        out[pad + r * (h + pad):pad + r * (h + pad) + h, pad + c * (w + pad):pad + c * (w + pad) + w] = a
    return out


def three_blobs(rng, n=300):
    mus = np.array([[0.0, 0.0], [3.0, 2.5], [-2.0, 3.5]])
    Ss = [np.array([[1.0, 0.7], [0.7, 0.8]]), np.array([[0.7, -0.4], [-0.4, 0.5]]), np.array([[0.5, 0.0], [0.0, 1.2]])]
    pis = np.array([0.4, 0.35, 0.25])
    z = rng.choice(3, n, p=pis)
    X = np.stack([rng.multivariate_normal(mus[k], Ss[k]) for k in z])
    return X, mus, Ss, pis


def fig_28_1(out_dir=None):
    """Figure 28.1: a mixture of three Gaussians in 2-d: contours of the components and the density surface."""
    mus = np.array([[0.30, 0.65], [0.72, 0.35], [0.45, 0.28]])
    Ss = [np.array([[0.020, 0.012], [0.012, 0.015]]), np.array([[0.012, -0.005], [-0.005, 0.016]]), np.array([[0.008, 0.0], [0.0, 0.008]])]
    pis = np.array([0.5, 0.3, 0.2])
    xs = np.linspace(0, 1, 120)
    G = np.stack(np.meshgrid(xs, xs), -1).reshape(-1, 2)
    dens = sum(pis[k] * np.exp(gauss_logpdf_chol(G, mus[k], Ss[k])) for k in range(3)).reshape(120, 120)
    fig = plt.figure(figsize=(7.4, 3.2))
    ax = fig.add_subplot(1, 2, 1)
    for k, c in zip(range(3), (RED, BLUE, GREEN)):
        dk = np.exp(gauss_logpdf_chol(G, mus[k], Ss[k])).reshape(120, 120)
        ax.contour(xs, xs, dk, levels=np.array([0.2, 0.5, 0.8]) * dk.max(), colors=c, linewidths=1.2)
    ax.set_xlabel("$x_1$")
    ax.set_ylabel("$x_2$")
    ax.set_aspect("equal")
    panel_label(ax, "a", "lower right")
    ax3 = fig.add_subplot(1, 2, 2, projection="3d")
    X, Y = np.meshgrid(xs[::3], xs[::3])
    ax3.plot_surface(X, Y, dens[::3, ::3], cmap="viridis", linewidth=0, antialiased=True, rasterized=True)
    ax3.set_xlabel("$x_1$")
    ax3.set_ylabel("$x_2$")
    ax3.set_zticks([])
    ax3.view_init(30, -60)
    ax3.text2D(0.03, 0.9, "(b)", transform=ax3.transAxes)
    savefig(fig, CH, "fig28-1", out_dir)


def fig_28_2(out_dir=None):
    """Figure 28.2: two-dimensional data and a clustering with K = 5 components fitted by EM."""
    rng = np.random.default_rng(3)
    mus = np.array([[0, 0], [4, 1], [-3, 3.5], [2.5, 5], [-3, -3]], float)
    Ss = [np.array([[1.2, 0.8], [0.8, 0.9]]), np.array([[0.6, -0.4], [-0.4, 0.9]]), np.array([[1.0, 0.0], [0.0, 0.4]]),
          np.array([[0.5, 0.2], [0.2, 0.5]]), np.array([[0.8, 0.3], [0.3, 1.0]])]
    sizes = [120, 90, 80, 70, 90]
    X = np.vstack([rng.multivariate_normal(mus[k], Ss[k], sizes[k]) for k in range(5)])
    g = gmm_em(X, 5, iters=200, seed=1)
    lab = np.argmax(g["R"], 1)
    fig, ax = panel_grid(1, 2, size=(3.6, 3.3))
    ax[0, 0].scatter(*X.T, s=8, c=GREY)
    cols = [RED, BLUE, GREEN, ORANGE, PURPLE]
    for k in range(5):
        ax[0, 1].scatter(*X[lab == k].T, s=8, c=cols[k])
        ex, ey = common.ellipse_xy(g["mu"][k], g["S"][k], 2.0)
        ax[0, 1].plot(ex, ey, c="k", lw=1)
    for a, l in zip(ax[0], "ab"):
        a.set_xlabel("$x_1$")
        a.set_ylabel("$x_2$")
        panel_label(a, l, "lower right")
    savefig(fig, CH, "fig28-2", out_dir)


def fig_28_3(out_dir=None):
    """Figure 28.3: a mixture of 20 Bernoullis fitted to binarised MNIST digits (no labels used)."""
    X, y = common.mnist(True)
    Xb = (X[:15000] > 0.5).astype(float)
    r = bmm_em(Xb, 20, iters=60, seed=3)
    order = np.argsort(-r["pi"])
    fig, axes = plt.subplots(4, 5, figsize=(6.2, 5.2))
    for a, k in zip(axes.ravel(), order):
        a.imshow(r["mu"][k].reshape(28, 28), cmap="gray_r", vmin=0, vmax=1)
        a.set_title("%.2f" % r["pi"][k], fontsize=9, pad=2)
        a.axis("off")
    savefig(fig, CH, "fig28-3", out_dir)
    print("  BMM final average log-likelihood per image %.1f" % (r["ll"][-1] / len(Xb)))


_EPLL_FILE = os.path.join(CACHE_DIR, "epll_gmm.npz")


def epll_prior():
    """The patch prior used for Figures 28.4 and 28.5: K = 20 zero-mean components on 8x8 patches of one sample photograph."""
    if os.path.exists(_EPLL_FILE):
        z = np.load(_EPLL_FILE)
        return dict(pi=z["pi"], mu=z["mu"], S=z["S"])
    china, _ = sample_images()
    rng = np.random.default_rng(0)
    P = extract_patches(china, 8, 40000, rng)
    g = epll_fit(P, 20, seed=0, iters=40)
    np.savez(_EPLL_FILE, pi=g["pi"], mu=g["mu"], S=g["S"])
    return g


def psnr(a, b):
    return 10 * np.log10(1.0 / np.mean((a - b) ** 2))


def fig_28_4(out_dir=None):
    """Figure 28.4: image restoration with the GMM patch prior (EPLL, half-quadratic splitting): denoising (top) and
    inpainting (bottom). Stand-in photographs from scikit-learn."""
    g = epll_prior()
    _, flower = sample_images()
    crop = flower[100:228, 180:308]
    rng = np.random.default_rng(1)
    sigma = 0.1
    noisy = crop + sigma * rng.standard_normal(crop.shape)
    den = epll_restore(noisy, g, sigma)
    mask = rng.random(crop.shape) > 0.5
    obs = crop * mask
    x0 = np.where(mask, crop, crop[mask].mean())
    inp = epll_restore(obs, g, 0.01, mask=mask, x0=x0, betas=np.array([20, 40, 80, 160, 320, 640, 1280, 2560.]))
    shown_in = np.where(mask, crop, 0.0)
    fig, ax = panel_grid(2, 3, size=(2.2, 2.2))
    rows = [(crop, noisy, den, "noisy", "denoised"), (crop, shown_in, inp, "50% of pixels missing", "inpainted")]
    for r, (a, b, c, tb, tc) in enumerate(rows):
        for j, (im, t) in enumerate(((a, "original"), (b, tb), (c, tc))):
            ax[r, j].imshow(np.clip(im, 0, 1), cmap="gray", vmin=0, vmax=1)
            ax[r, j].axis("off")
            extra = "" if j == 0 else "  (%.1f dB)" % psnr(crop, np.clip(im, 0, 1) if r == 0 else (im if j == 2 else np.where(mask, crop, crop[mask].mean())))
            ax[r, j].set_title(t + extra, fontsize=8.5)
    savefig(fig, CH, "fig28-4", out_dir)
    print("  PSNR: noisy %.2f, denoised %.2f; inpainting (mean fill) %.2f -> %.2f" % (psnr(crop, noisy), psnr(crop, den), psnr(crop, x0), psnr(crop, inp)))


def fig_28_5(out_dir=None):
    """Figure 28.5: the first 24 eigenvectors of the covariance of three components of the patch GMM (decreasing eigenvalue)."""
    g = epll_prior()
    pick = [int(k) for k in np.argsort(-g["pi"])[[0, 4, 9]]]
    fig, axes = plt.subplots(1, 3, figsize=(7.4, 2.8))
    for a, k in zip(axes, pick):
        lam, V = np.linalg.eigh(g["S"][k])
        V = V[:, ::-1][:, :24].T
        a.imshow(montage(V, 3, 8, (8, 8), pad=1, bg=0.5, centre=True), cmap="gray", vmin=0, vmax=1)
        a.set_title("component %d, weight %.2f" % (k, g["pi"][k]), fontsize=9)
        a.axis("off")
    savefig(fig, CH, "fig28-5", out_dir)


def fig_28_6(out_dir=None):
    """Figure 28.6: the generative process of factor analysis with L = 1 latent and D = 2 observed dimensions."""
    rng = np.random.default_rng(0)
    mu = np.array([0.0, 0.0])
    w = np.array([1.6, 0.9])
    sig = 0.45
    fig, ax = plt.subplots(1, 2, figsize=(7.2, 3.3))
    a = ax[0]
    zs = np.linspace(-2.2, 2.2, 5)
    t = np.linspace(0, 2 * np.pi, 100)
    a.plot([mu[0] + w[0] * -2.4, mu[0] + w[0] * 2.4], [mu[1] + w[1] * -2.4, mu[1] + w[1] * 2.4], c=GREY, lw=1, ls="--")
    for z in zs:
        c = mu + z * w
        a.plot(c[0] + sig * np.cos(t), c[1] + sig * np.sin(t), c=BLUE, lw=1.1)
        a.plot(*c, "o", c=RED, ms=3)
    a.annotate("", xy=(w[0], w[1]), xytext=(0, 0), arrowprops=dict(arrowstyle="->", color=RED))
    a.text(w[0] + 0.05, w[1] - 0.25, "$w$", color=RED)
    a.set_xlabel("$x_1$")
    a.set_ylabel("$x_2$")
    a.set_aspect("equal")
    a.set_title("$p(x\\mid z)=N(\\mu+zw,\\sigma^2 I)$ for five $z$", fontsize=9)
    b = ax[1]
    z = rng.standard_normal(600)
    X = mu + z[:, None] * w + sig * rng.standard_normal((600, 2))
    b.scatter(*X.T, s=5, c=GREY, alpha=0.7)
    C = np.outer(w, w) + sig ** 2 * np.eye(2)
    for ns in (1, 2):
        ex, ey = common.ellipse_xy(mu, C, ns)
        b.plot(ex, ey, c=RED, lw=1.3)
    b.set_xlabel("$x_1$")
    b.set_ylabel("$x_2$")
    b.set_aspect("equal")
    b.set_title("sliding along $z$: $N(\\mu,ww^T+\\sigma^2 I)$", fontsize=9)
    savefig(fig, CH, "fig28-6", out_dir)


def curve_data(n=300, seed=0):
    rng = np.random.default_rng(seed)
    t = rng.uniform(-1, 1, n)
    X = np.stack([2.0 * t, 1.2 * np.sin(2.6 * t) * np.cos(1.0 * t)], 1) + 0.06 * rng.standard_normal((n, 2))
    return X


def fig_28_8(out_dir=None):
    """Figure 28.8: a mixture of PPCA models with L = 1 on 2-d data with K = 1 and K = 10 components."""
    X = curve_data()
    fig, ax = panel_grid(1, 2, size=(3.6, 2.8))
    for a, K, l in zip(ax[0], (1, 10), "ab"):
        m = MFA(K, 1, iso=True, seed=2).fit(X, iters=300)
        a.scatter(*X.T, s=6, c=GREY, alpha=0.8)
        for k in range(K):
            c, w = m.mu[k], m.W[k][:, 0]
            a.plot([c[0] - 2 * w[0], c[0] + 2 * w[0]], [c[1] - 2 * w[1], c[1] + 2 * w[1]], c=RED, lw=1.5)
            a.plot(*c, "o", c=BLUE, ms=3)
        a.set_xlabel("$x_1$")
        a.set_ylabel("$x_2$")
        a.set_title("K = %d, log-lik per point %.2f" % (K, m.ll[-1] / len(X)), fontsize=8.5)
        panel_label(a, l, "lower right")
    savefig(fig, CH, "fig28-8", out_dir)


# ===== mixture of factor analysers on digits (Figures 28.11 to 28.14)
_MFA_FILE = os.path.join(CACHE_DIR, "mfa_digits.npz")


def digits_split():
    from sklearn.datasets import load_digits
    d = load_digits()
    X = d.data / 16.0
    rng = np.random.default_rng(0)
    p = rng.permutation(len(X))
    ntr = 1500
    return X[p[:ntr]], d.target[p[:ntr]], X[p[ntr:]], d.target[p[ntr:]]


def mfa_digits():
    """K = 10 components, L = 4, shared diagonal noise, fitted to 1500 training digits (the stand-in for 300 components, L = 10 on CelebA)."""
    Xtr, ytr, Xte, yte = digits_split()
    m = MFA(10, 4, iso=False, seed=1, psi_min=0.01).fit(Xtr, iters=200)
    return m, Xtr, Xte, yte


def fig_28_11(out_dir=None):
    """Figure 28.11: random samples from the mixture of factor analysers fitted to digits (stand-in for CelebA faces)."""
    m, Xtr, Xte, yte = mfa_digits()
    rng = np.random.default_rng(0)
    S, k = m.sample(60, rng)
    S = np.clip(S, 0, 1)
    fig, ax = plt.subplots(figsize=(5.6, 3.6))
    ax.imshow(montage(S, 6, 10, (8, 8), pad=1, bg=1.0), cmap="gray_r", vmin=0, vmax=1)
    ax.axis("off")
    savefig(fig, CH, "fig28-11", out_dir)
    print("  MFA(10, 4) test log-likelihood per image %.2f, training %.2f" % (m.loglik(Xte).mean(), m.loglik(Xtr).mean()))


def fig_28_12(out_dir=None):
    """Figure 28.12: parameters of the mixture of factor analysers: mean, noise variance and basis functions of two components
    (mu_k - w_i, 0.5 + w_i, mu_k + w_i), and a grid decoded from a 2-d slice of the latent space."""
    m, Xtr, Xte, yte = mfa_digits()
    kk = [int(i) for i in np.argsort(-m.pi)[:2]]
    fig = plt.figure(figsize=(8.2, 3.6))
    gs = fig.add_gridspec(1, 2, width_ratios=[2.3, 1], wspace=0.04)
    sub = gs[0, 0].subgridspec(1, 1)
    ax = fig.add_subplot(sub[0, 0])
    rows = []
    for k in kk:
        row = [m.mu[k], np.sqrt(m.psi)]
        for i in range(3):
            w = m.W[k][:, i]
            row += [m.mu[k] - w, 0.5 + w, m.mu[k] + w]
        rows.append(row)
    ncol = len(rows[0])
    flat = [clip for r in rows for clip in r]
    img = montage([np.clip(a, 0, 1) if (j % 11 != 1) else a / (a.max() + 1e-9) for r in rows for j, a in enumerate(r)], 2, ncol, (8, 8), pad=1, bg=1.0)
    ax.imshow(img, cmap="gray_r", vmin=0, vmax=1)
    ax.axis("off")
    ax.set_title("two components: mean, noise sd, then ($\\mu-w_i$, $0.5+w_i$, $\\mu+w_i$), $i=1,2,3$", fontsize=7.5)
    ax2 = fig.add_subplot(gs[0, 1])
    k = kk[0]
    zz = np.linspace(-2.5, 2.5, 7)
    imgs = []
    for z2 in zz[::-1]:
        for z1 in zz:
            imgs.append(np.clip(m.mu[k] + z1 * m.W[k][:, 0] + z2 * m.W[k][:, 1], 0, 1))
    ax2.imshow(montage(imgs, 7, 7, (8, 8), pad=1, bg=1.0), cmap="gray_r", vmin=0, vmax=1)
    ax2.axis("off")
    ax2.set_title("$\\mu_k+z_1w_1+z_2w_2$", fontsize=8)
    savefig(fig, CH, "fig28-12", out_dir)


def fig_28_13(out_dir=None):
    """Figure 28.13: the 20 test digits with the lowest log-likelihood under the mixture of factor analysers (outliers)."""
    m, Xtr, Xte, yte = mfa_digits()
    ll = m.loglik(Xte)
    order = np.argsort(ll)[:20]
    fig, ax = plt.subplots(figsize=(5.6, 2.4))
    ax.imshow(montage(Xte[order], 2, 10, (8, 8), pad=1, bg=1.0), cmap="gray_r", vmin=0, vmax=1)
    ax.axis("off")
    savefig(fig, CH, "fig28-13", out_dir)
    print("  lowest 20 log-likelihoods: %.1f to %.1f, median over the test set %.1f; labels of the 20: %s" % (ll[order[0]], ll[order[-1]], np.median(ll), list(yte[order])))


def occlusion_mask(kind, shape=(8, 8)):
    mk = np.ones(shape, bool)
    if kind == "bottom":
        mk[4:, :] = False
    elif kind == "right":
        mk[:, 4:] = False
    return mk.ravel()


def fig_28_14(out_dir=None):
    """Figure 28.14: image imputation with the mixture of factor analysers (28.94)-(28.96): original, occluded input and prediction;
    the last row uses a single factor analyser (K = 1) for comparison."""
    m, Xtr, Xte, yte = mfa_digits()
    m1 = MFA(1, 4, iso=False, seed=1, psi_min=0.01).fit(Xtr, iters=200)
    idx = [0, 1, 2, 3, 4, 5, 6, 7]
    rows = {"original": [], "input": [], "MFA": [], "FA (K=1)": []}
    errs = {"MFA": [], "FA": []}
    for t, i in enumerate(idx):
        obs = occlusion_mask("bottom" if t % 2 == 0 else "right")
        x = Xte[i]
        xh, kb, _ = m.impute(x, obs)
        xh1, _, _ = m1.impute(x, obs)
        rows["original"].append(x)
        rows["input"].append(np.where(obs, x, 0.5))
        rows["MFA"].append(np.clip(xh, 0, 1))
        rows["FA (K=1)"].append(np.clip(xh1, 0, 1))
        errs["MFA"].append(np.mean((xh[~obs] - x[~obs]) ** 2))
        errs["FA"].append(np.mean((xh1[~obs] - x[~obs]) ** 2))
    fig, ax = plt.subplots(figsize=(5.4, 2.6))
    ax.imshow(montage([a for r in rows.values() for a in r], 4, len(idx), (8, 8), pad=1, bg=1.0), cmap="gray_r", vmin=0, vmax=1)
    ax.set_yticks([1 + 9 * j + 4 for j in range(4)])
    ax.set_yticklabels(list(rows), fontsize=7.5)
    ax.set_xticks([])
    for s in ax.spines.values():
        s.set_visible(False)
    ax.tick_params(length=0)
    savefig(fig, CH, "fig28-14", out_dir)
    # imputation error over the whole test set, bottom half hidden
    obs = occlusion_mask("bottom")
    e1 = np.mean([np.mean((m.impute(x, obs)[0][~obs] - x[~obs]) ** 2) for x in Xte])
    e2 = np.mean([np.mean((m1.impute(x, obs)[0][~obs] - x[~obs]) ** 2) for x in Xte])
    e3 = np.mean([np.mean((Xtr.mean(0)[~obs] - x[~obs]) ** 2) for x in Xte])
    print("  imputation MSE of the hidden bottom half over the test set: MFA %.4f, FA %.4f, mean image %.4f" % (e1, e2, e3))


def fig_x28_3(out_dir=None):
    """Own figure x28.3: test log-likelihood against the training-set size for a Gaussian mixture with full covariances and for mixtures of
    factor analysers with L = 2 and 4 factors (K = 5 components, digits), and the number of parameters of each."""
    Xtr, ytr, Xte, yte = digits_split()
    keep = Xtr.std(0) > 0.02
    Xa, Xb = Xtr[:, keep], Xte[:, keep]
    D = Xa.shape[1]
    K = 5
    sizes = [100, 200, 400, 800, 1500]
    curves = {"full GMM": [], "MFA, L=2": [], "MFA, L=4": []}
    for n in sizes:
        g = gmm_em(Xa[:n], K, iters=100, seed=1, reg=1e-2)
        curves["full GMM"].append(gmm_logpdf(Xb, g).mean())
        for L in (2, 4):
            m = MFA(K, L, seed=1, psi_min=0.01).fit(Xa[:n], iters=150)
            curves["MFA, L=%d" % L].append(m.loglik(Xb).mean())
    fig, ax = panel_grid(1, 2, size=(3.7, 3.0))
    for (nm, v), c in zip(curves.items(), (GREY, BLUE, RED)):
        ax[0, 0].plot(sizes, v, "o-", c=c, label=nm)
    ax[0, 0].set_xscale("log")
    ax[0, 0].set_xlabel("training set size")
    ax[0, 0].set_ylabel("test log-likelihood per image")
    ax[0, 0].legend(fontsize=8)
    pc = [K * D * (D + 1) / 2 + K * D + K - 1, K * (D * 2 + D) + D + K - 1, K * (D * 4 + D) + D + K - 1]
    ax[0, 1].bar(["full GMM", "MFA L=2", "MFA L=4"], pc, color=[GREY, BLUE, RED])
    ax[0, 1].set_ylabel("number of parameters")
    ax[0, 1].set_yscale("log")
    savefig(fig, CH, "figx28-3", out_dir)
    for nm, v in curves.items():
        print("  %-9s test log-lik by training size %s" % (nm, [round(float(a), 1) for a in v]))
    print("  parameters: full GMM %d, MFA L=2 %d, MFA L=4 %d (D = %d)" % (pc[0], pc[1], pc[2], D))


# ===== binary PCA, GP-LVM (28.3.5, 28.3.7)
def bit_data(seed=0, n=150, d=16, flip=0.1):
    rng = np.random.default_rng(seed)
    proto = rng.integers(0, 2, (3, d))
    lab = np.sort(rng.integers(0, 3, n))[np.argsort(rng.random(n))]
    X = proto[lab].copy()
    X = np.where(rng.random(X.shape) < flip, 1 - X, X).astype(float)
    return X, lab, proto


def fig_28_18(out_dir=None):
    """Figure 28.18: binary PCA fitted by variational EM to 150 synthetic 16-bit vectors from three prototypes: data, 2-d embedding,
    predicted probabilities and thresholded (denoised) data."""
    X, lab, proto = bit_data()
    order = np.argsort(lab, kind="stable")
    r = binary_pca(X, 2, iters=60, seed=0)
    P = binary_pca_predict(r)
    fig, ax = plt.subplots(1, 4, figsize=(8.4, 3.1), gridspec_kw=dict(width_ratios=[0.6, 1.3, 0.6, 0.6]))
    ax[0].imshow(X[order], cmap="gray_r", aspect="auto", interpolation="nearest")
    for c, a in zip("abcd", ax):
        a.set_title("(%s)" % c, fontsize=9)
    for k, (col, mk) in enumerate(zip((RED, BLUE, GREEN), ("o", "s", "^"))):
        ax[1].scatter(*r["m"][lab == k].T, s=14, c=col, marker=mk)
    ax[1].set_xlabel("$E[z_1]$")
    ax[1].set_ylabel("$E[z_2]$")
    ax[2].imshow(P[order], cmap="gray_r", aspect="auto", vmin=0, vmax=1, interpolation="nearest")
    ax[3].imshow((P[order] > 0.5).astype(float), cmap="gray_r", aspect="auto", interpolation="nearest")
    for a in (ax[0], ax[2], ax[3]):
        a.set_xticks([])
        a.set_yticks([])
    savefig(fig, CH, "fig28-18", out_dir)
    print("  bits wrong: raw data %.3f, thresholded reconstruction %.3f (true prototype); bound %.1f -> %.1f" % (
        np.mean(X != proto[lab]), np.mean((P > 0.5) != proto[lab]), r["bound"][0], r["bound"][-1]))


def fig_28_19(out_dir=None):
    """Figure 28.19: a 2-d GP-LVM embedding (ARD squared-exponential kernel) of 8x8 digit images of three classes
    (stand-in for the motion-capture data), next to the PCA embedding, with two decoded points."""
    from sklearn.datasets import load_digits
    d = load_digits()
    sel = np.isin(d.target, (0, 1, 7))
    rng = np.random.default_rng(0)
    idx = np.concatenate([rng.choice(np.where(d.target == c)[0], 100, replace=False) for c in (0, 1, 7)])
    Y = d.data[idx] / 16.0
    y = d.target[idx]
    keep = Y.std(0) > 1e-3
    Y = Y[:, keep]
    res = gplvm(Y, Q=2, iters=400, seed=0)
    U, s, Vt = np.linalg.svd(Y - Y.mean(0), full_matrices=False)
    P = U[:, :2] * s[:2]
    fig, ax = panel_grid(1, 2, size=(3.7, 3.4))
    for c, col, mk in zip((0, 1, 7), (RED, BLUE, GREEN), ("o", "s", "^")):
        ax[0, 0].scatter(*res["Z"][y == c].T, s=12, c=col, marker=mk, label="digit %d" % c)
        ax[0, 1].scatter(*P[y == c].T, s=12, c=col, marker=mk)
    ax[0, 0].set_title("GP-LVM (ARD kernel)", fontsize=9)
    ax[0, 1].set_title("PCA", fontsize=9)
    ax[0, 0].legend(fontsize=7, loc="best")
    for a in ax[0]:
        a.set_xticks([])
        a.set_yticks([])
    savefig(fig, CH, "fig28-19", out_dir)
    print("  GP-LVM log-likelihood %.1f; ARD length scales %s; noise sd %.3f" % (res["ll"][-1], np.round(res["ls"], 2), res["sn"]))
    # nearest-neighbour class purity in the 2-d embeddings
    from sklearn.neighbors import KNeighborsClassifier
    for name, Z in (("GP-LVM", res["Z"]), ("PCA", P)):
        acc = KNeighborsClassifier(5).fit(Z[::2], y[::2]).score(Z[1::2], y[1::2])
        print("  5-NN accuracy in the 2-d %s embedding: %.3f" % (name, acc))


# =========================================================================== figures: NMF, ICA, sparse coding
def fig_28_21(out_dir=None):
    """Figure 28.21: filters (columns of W), codes z for one test digit, and reconstruction for NMF (Poisson-EM), PCA and vector
    quantisation (K-means), each with 25 basis functions. MNIST digits stand in for the book's face images."""
    X, y = common.mnist(True)
    Xtr = X[:6000]
    Xte, _ = common.mnist(False)
    x = Xte[0]
    K = 25
    Z, W, hist = nmf_kl(Xtr, K, iters=250, seed=0)
    # code of a new image: Poisson-EM updates of z with W fixed
    z = np.full(K, x.mean() / W.sum(1).mean() * 2)
    for _ in range(300):
        z *= (W @ (x / (z @ W + 1e-10))) / (W.sum(1) + 1e-10)
    rec_nmf = z @ W
    mu = Xtr.mean(0)
    U, s, Vt = np.linalg.svd(Xtr - mu, full_matrices=False)
    Wp = Vt[:K]
    zp = Wp @ (x - mu)
    rec_pca = mu + zp @ Wp
    rng = np.random.default_rng(0)
    C = kmeans_pp(Xtr, K, rng)
    for _ in range(20):
        a = np.argmin(((Xtr[:, None, :] - C[None]) ** 2).sum(-1), 1)
        for k in range(K):
            if np.any(a == k):
                C[k] = Xtr[a == k].mean(0)
    kq = int(np.argmin(((x - C) ** 2).sum(1)))
    zq = np.eye(K)[kq]
    rec_vq = C[kq]
    fig, axes = plt.subplots(3, 3, figsize=(7.6, 7.2), gridspec_kw=dict(width_ratios=[1.5, 1.2, 0.8]))
    rows = [("NMF", W, z, rec_nmf, False), ("PCA", Wp, zp, rec_pca, True), ("VQ", C, zq, rec_vq, False)]
    for r, (nm, B, code, rec, centre) in enumerate(rows):
        axes[r, 0].imshow(montage(B, 5, 5, (28, 28), pad=2, bg=0.5 if centre else 1.0, centre=centre) if centre else
                          montage(B / (B.max(1, keepdims=True) + 1e-12), 5, 5, (28, 28), pad=2, bg=1.0), cmap="gray" if centre else "gray_r", vmin=0, vmax=1)
        axes[r, 0].axis("off")
        axes[r, 0].set_title(nm + ": basis functions", fontsize=9)
        axes[r, 1].bar(range(K), code, color=[BLUE if c >= 0 else RED for c in code])
        axes[r, 1].set_title("code $z$ of the test digit", fontsize=9)
        axes[r, 2].imshow(np.clip(rec, 0, 1).reshape(28, 28), cmap="gray_r", vmin=0, vmax=1)
        axes[r, 2].axis("off")
        axes[r, 2].set_title("reconstruction", fontsize=9)
    fig.tight_layout()
    savefig(fig, CH, "fig28-21", out_dir)
    sp = lambda c: float(np.mean(np.abs(c) < 1e-3 * np.abs(c).max()))
    print("  squared error of the reconstruction: NMF %.2f, PCA %.2f, VQ %.2f; fraction of (near-)zero code entries: NMF %.2f, PCA %.2f, VQ %.2f" % (
        ((x - rec_nmf) ** 2).sum(), ((x - rec_pca) ** 2).sum(), ((x - rec_vq) ** 2).sum(), sp(z), sp(zp), sp(zq)))


def ica_sources(rng, n=500):
    t = np.arange(n)
    S = np.stack([np.sin(2 * np.pi * t / 61.0), np.sign(np.sin(2 * np.pi * t / 37.0)), 2 * ((t / 53.0) % 1) - 1,
                  rng.laplace(size=n) / np.sqrt(2)], 1)
    return (S - S.mean(0)) / S.std(0)


def fig_28_32(out_dir=None):
    """Figure 28.32: ICA on 500 samples of a four-dimensional source (sine, square wave, sawtooth, Laplace noise): truth, mixtures,
    PCA (whitening) estimate and FastICA estimate."""
    rng = np.random.default_rng(1)
    S = ica_sources(rng)
    A = rng.standard_normal((4, 4))
    X = S @ A.T
    r = fastica(X, seed=0)
    Xw, mu, Wh = whiten(X)
    P_ica = r["V"] @ Wh @ A
    P_pca = Wh @ A
    fig, ax = plt.subplots(1, 4, figsize=(9.0, 3.2), sharey=False)
    for a, (D, t) in zip(ax, ((S, "(a) truth"), (X, "(b) observations"), (Xw, "(c) PCA estimate"), (r["S"], "(d) ICA estimate"))):
        for j in range(4):
            a.plot(D[:120, j] / (np.abs(D[:120]).max() + 1e-9) * 0.45 + j, lw=0.9, c=[BLUE, RED, GREEN, ORANGE][j])
        a.set_title(t, fontsize=9)
        a.set_yticks([])
        a.set_xlabel("sample")
    savefig(fig, CH, "fig28-32", out_dir)
    print("  Amari index: PCA (whitening) %.3f, FastICA %.4f" % (amari_error(P_pca), amari_error(P_ica)))


def uniform_mixture(n=100, seed=0):
    rng = np.random.default_rng(seed)
    S = rng.uniform(-np.sqrt(3), np.sqrt(3), (n, 2))
    A = 0.3 * np.array([[2.0, 3.0], [2.0, 1.0]])
    return S, A, S @ A.T


def fig_28_33(out_dir=None):
    """Figure 28.33: ICA and PCA on 100 samples of a two-dimensional uniform source: sources, mixtures, whitened data (PCA), ICA estimate."""
    S, A, X = uniform_mixture()
    Xw, mu, Wh = whiten(X)
    r = fastica(X, seed=0, iters=500)
    fig, ax = panel_grid(1, 4, size=(2.3, 2.3))
    for a, (D, t) in zip(ax[0], ((S, "(a) uniform data"), (X, "(b) after linear mixing"), (Xw, "(c) PCA estimate"), (r["S"], "(d) ICA estimate"))):
        a.scatter(*D.T, s=6, c=BLUE)
        a.set_title(t, fontsize=8.5)
        lim = 1.1 * np.abs(D).max()
        a.set_xlim(-lim, lim)
        a.set_ylim(-lim, lim)
        a.set_aspect("equal")
    savefig(fig, CH, "fig28-33", out_dir)
    print("  uniform sources: Amari index PCA %.3f, ICA %.4f" % (amari_error(Wh @ A), amari_error(r["V"] @ Wh @ A)))


def whitened_mix(kind, n=400, seed=0):
    """Whitened mixtures of two unit-variance sources of a given kind, used by Figure x28.2 and the ICA demo."""
    rng = np.random.default_rng(seed)
    if kind == "uniform":
        S = rng.uniform(-np.sqrt(3), np.sqrt(3), (n, 2))
    elif kind == "laplace":
        S = rng.laplace(size=(n, 2)) / np.sqrt(2)
    elif kind == "gauss":
        S = rng.standard_normal((n, 2))
    elif kind == "mixed":
        S = np.stack([rng.uniform(-np.sqrt(3), np.sqrt(3), n), rng.laplace(size=n) / np.sqrt(2)], 1)
    else:
        raise ValueError(kind)
    A = np.array([[1.0, 0.6], [0.3, 1.0]])
    X = S @ A.T
    Xw, mu, Wh = whiten(X)
    return S, A, Xw, Wh


def rotation(th):
    c, s = np.cos(th), np.sin(th)
    return np.array([[c, -s], [s, c]])


def true_angle_deg(kind, n=400, seed=0):
    """Angle (degrees, reduced to (-45, 45]) of the rotation that recovers the true unit-variance sources from the whitened mixtures
    of whitened_mix(kind, n, seed); the equivalent angles are this plus multiples of 90 (signed permutations)."""
    S, A, Xw, Wh = whitened_mix(kind, n, seed)
    Ss = (S - S.mean(0)) / S.std(0)
    Q = np.linalg.lstsq(Xw, Ss, rcond=None)[0].T
    th = np.degrees(np.arctan2(Q[1, 0], Q[0, 0]))
    return float((th + 45) % 90 - 45)


def ica_curve(Xw, n=361):
    ths = np.linspace(-np.pi / 2, np.pi / 2, n)
    return ths, np.array([ica_nll(rotation(t), Xw) for t in ths])


def fig_x28_2(out_dir=None):
    """Own figure x28.2: the ICA objective (28.150) with a logistic prior as a function of the rotation angle of the whitened data."""
    fig, ax = panel_grid(1, 4, size=(2.3, 2.3))
    for a, kind in zip(ax[0], ("uniform", "laplace", "mixed", "gauss")):
        S, A, Xw, Wh = whitened_mix(kind)
        ths, f = ica_curve(Xw)
        a.plot(np.degrees(ths), f, c=BLUE)
        t0 = true_angle_deg(kind)
        for j in range(-1, 2):
            a.axvline(t0 + 90 * j, c=RED, ls="--", lw=0.8)
        a.set_title(kind, fontsize=9)
        a.set_xlim(-90, 90)
        a.set_xlabel("rotation angle (degrees)", fontsize=8)
        a.set_ylim(f.min() - 0.01, f.min() + 0.08)
    ax[0, 0].set_ylabel("average NLL")
    savefig(fig, CH, "figx28-2", out_dir)
    for kind in ("uniform", "laplace", "mixed", "gauss"):
        S, A, Xw, Wh = whitened_mix(kind)
        ths, f = ica_curve(Xw)
        print("  %-8s range of the NLL over angles %.4f (min %.4f at %.1f deg)" % (kind, f.max() - f.min(), f.min(), np.degrees(ths[np.argmin(f)])))


_DICT_FILE = os.path.join(CACHE_DIR, "dict.npz")


def natural_patches(p=8, n=3000, seed=0):
    china, flower = sample_images()
    rng = np.random.default_rng(seed)
    P = np.vstack([extract_patches(china, p, n, rng), extract_patches(flower, p, n, rng)])
    P = P - P.mean(1, keepdims=True)
    P /= np.linalg.norm(P, axis=1, keepdims=True) + 1e-8
    keep = np.linalg.norm(P, axis=1) > 0.5
    return P[keep]


def fig_28_34(out_dir=None):
    """Figure 28.34: filters learned from natural image patches (centred, unit norm) by sparse coding (dictionary learning with an l1
    penalty, 100 atoms) and by PCA (the 63 non-trivial eigenvectors)."""
    P = natural_patches()
    if os.path.exists(_DICT_FILE):
        W = np.load(_DICT_FILE)["W"]
    else:
        W, _ = sparse_dictionary(P, 100, 0.1, outer=25, inner=40, seed=0)
        np.savez(_DICT_FILE, W=W)
    Zc = fista_lasso(W, P, 0.1, 200)
    U, s, Vt = np.linalg.svd(P - P.mean(0), full_matrices=False)
    fig, ax = plt.subplots(1, 2, figsize=(7.2, 3.6))
    ax[0].imshow(montage(W.T, 10, 10, (8, 8), pad=1, bg=0.5, centre=True), cmap="gray", vmin=0, vmax=1)
    ax[0].set_title("(a) sparse coding", fontsize=9)
    ax[1].imshow(montage(Vt[:63], 8, 8, (8, 8), pad=1, bg=0.5, centre=True), cmap="gray", vmin=0, vmax=1)
    ax[1].set_title("(b) PCA", fontsize=9)
    for a in ax:
        a.axis("off")
    savefig(fig, CH, "fig28-34", out_dir)
    err = np.mean(np.sum((P - Zc @ W.T) ** 2, 1))
    print("  sparse coding: relative error %.3f, fraction of non-zero codes %.3f; PCA with 8 components relative error %.3f" % (
        err, np.mean(np.abs(Zc) > 1e-6), np.mean(np.sum((P - P.mean(0) - ((P - P.mean(0)) @ Vt[:8].T) @ Vt[:8]) ** 2, 1))))


# =========================================================================== figures: topic models
BANK = dict(vocab=["River", "Stream", "Bank", "Money", "Loan"],
            topics=np.array([[0, 0, 1 / 3, 1 / 3, 1 / 3], [1 / 3, 1 / 3, 1 / 3, 0, 0]]))


def bank_corpus(seed=3, n_docs=16):
    """16 short documents over {River, Stream, Bank, Money, Loan} from the two topics of Supplement Figure 28.2: topic 1 (money, loan, bank)
    and topic 2 (river, stream, bank)."""
    rng = np.random.default_rng(seed)
    docs, theta = [], []
    for i in range(n_docs):
        th = rng.dirichlet([0.4, 0.4])
        L = int(rng.integers(8, 16))
        z = rng.choice(2, L, p=th)
        w = np.array([rng.choice(5, p=BANK["topics"][k]) for k in z])
        docs.append(w)
        theta.append(th)
    return docs, np.array(theta)


def fig_S28_2(out_dir=None):
    """Supplement Figure 28.2: collapsed Gibbs sampling for LDA on 16 documents over 5 words and two topics: random initial assignments (a) and
    a sample after 64 sweeps (b); a dot is white for topic 1 and black for topic 2 (after fixing the label switch)."""
    docs, theta = bank_corpus()
    res = lda_gibbs(docs, 5, 2, 0.5, 0.5, 64, seed=1, record=(0, 64))
    Wt = BANK["topics"]
    est = lda_gibbs_estimates(res, 0.5, 0.5)
    swap = np.abs(est[0] - Wt[1]).sum() + np.abs(est[1] - Wt[0]).sum() < np.abs(est[0] - Wt[0]).sum() + np.abs(est[1] - Wt[1]).sum()
    fig, ax = panel_grid(1, 2, size=(3.4, 3.6))
    for a, key, l in zip(ax[0], (0, 64), "ab"):
        for i, d in enumerate(docs):
            cnt = np.zeros((5, 2), int)
            for w, k in zip(d, res["snaps"][key][i]):
                cnt[w, k if not swap else 1 - k] += 1
            for w in range(5):
                tot = cnt[w].sum()
                kk = [0] * cnt[w, 0] + [1] * cnt[w, 1]
                for j, k in enumerate(kk):
                    a.scatter(w + (j % 4 - 1.5) * 0.17, i + (j // 4 - 0.5) * 0.35, s=22, c="white" if k == 0 else "black", edgecolors="k", linewidths=0.7)
        a.set_xticks(range(5))
        a.set_xticklabels(BANK["vocab"], rotation=60, fontsize=8)
        a.set_yticks(range(0, 16, 3))
        a.set_yticklabels(range(1, 17, 3), fontsize=8)
        a.invert_yaxis()
        a.set_ylim(15.7, -0.7)
        a.set_title("(%s)" % l, fontsize=9)
        a.set_ylabel("document")
    savefig(fig, CH, "figS28-2", out_dir)
    print("  Gibbs estimate of p(word | topic) after 64 sweeps (rows: topic 1 = money/loan/bank, topic 2 = river/stream/bank):")
    e = est[::-1] if swap else est
    print("   ", np.round(e, 2).tolist(), "log joint %.1f -> %.1f" % (res["logjoint"][0], res["logjoint"][-1]))


def newsgroups_counts(n_train=1500, n_test=300, V=3000):
    from sklearn.datasets import fetch_20newsgroups
    from sklearn.feature_extraction.text import CountVectorizer
    cats = ["sci.space", "rec.sport.baseball", "talk.politics.guns", "comp.graphics", "sci.med", "rec.autos"]
    tr = fetch_20newsgroups(subset="train", remove=("headers", "footers", "quotes"), categories=cats)
    cv = CountVectorizer(max_features=V, stop_words="english", min_df=5)
    X = cv.fit_transform(tr.data).tocsr()
    X = X[np.asarray(X.sum(1)).ravel() > 30]
    Xtr, Xte = X[:n_train], X[n_train:n_train + n_test]
    return Xtr, Xte, np.array(cv.get_feature_names_out())


def split_halves(X, seed=0):
    """Randomly split the tokens of every document into two halves (observed, held out)."""
    rng = np.random.default_rng(seed)
    import scipy.sparse as sp
    A = X.copy().astype(float)
    B = X.copy().astype(float)
    for n in range(X.shape[0]):
        s, e = X.indptr[n], X.indptr[n + 1]
        c = X.data[s:e].astype(int)
        a = rng.binomial(c, 0.5)
        A.data[s:e] = a
        B.data[s:e] = c - a
    A.eliminate_zeros()
    B.eliminate_zeros()
    A = sp.csr_matrix(A)
    B = sp.csr_matrix(B)
    return A, B


def fig_S28_3(out_dir=None):
    """Supplement Figure 28.3: held-out perplexity against the number of training documents analysed, batch and online variational Bayes for
    LDA, 20 newsgroups (six groups, 1500 training documents, 3000 words, 20 topics)."""
    Xtr, Xte, vocab = newsgroups_counts()
    A, B = split_halves(Xte)
    K, alpha, beta = 20, 0.1, 0.01
    N = Xtr.shape[0]
    batch_pts, online_pts = [], []

    def cb_b(it, lam):
        batch_pts.append((it * N, lda_heldout_perplexity(lam, alpha, A, B)))
    lam_b = lda_vb_batch(Xtr, K, alpha, beta, 8, seed=0, callback=cb_b)
    steps = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512]

    def cb_o(t, lam):
        online_pts.append((t * 64, lda_heldout_perplexity(lam, alpha, A, B)))
    lam_o = lda_vb_online(Xtr, K, alpha, beta, max(steps), batch=64, tau0=64.0, kappa=0.7, seed=0, callback=cb_o, check=set(steps))
    fig, ax = plt.subplots(figsize=(4.4, 3.2))
    ax.plot(*zip(*batch_pts), "o-", c=RED, label="batch")
    ax.plot(*zip(*online_pts), "s-", c=BLUE, label="online (batch 64, $\\kappa=0.7$, $\\tau_0=64$)")
    ax.set_xscale("log")
    ax.set_xlabel("documents analysed (E steps)")
    ax.set_ylabel("held-out perplexity")
    ax.legend()
    savefig(fig, CH, "figS28-3", out_dir)
    print("  batch:", [(int(a), round(b, 1)) for a, b in batch_pts])
    print("  online:", [(int(a), round(b, 1)) for a, b in online_pts])
    top = {}
    for k in np.argsort(-lam_o.sum(1))[:6]:
        top[int(k)] = list(vocab[np.argsort(-lam_o[k])[:8]])
    print("  top words of six online topics:", top)
    return lam_b, lam_o


# =========================================================================== own figures
def fig_x28_1(out_dir=None):
    """Own figure x28.1: log densities of Gaussian scale mixtures (Student, Laplace, horseshoe; spike and slab marked) against the Gaussian,
    and the shrinkage rules E[x | y] for y = x + N(0, 1) noise."""
    xs = np.linspace(0, 8, 400)
    fams = [("Gaussian", "gauss", {}, "k"), ("Student $\\nu=2$", "student", dict(nu=2), BLUE), ("Laplace $\\lambda=1.4$", "laplace", dict(lam=1.4), RED),
            ("horseshoe", "horseshoe", {}, GREEN)]
    fig, ax = panel_grid(1, 2, size=(3.7, 3.0))
    for nm, fam, p, c in fams:
        d = gsm_density(xs, fam, **p) if fam != "horseshoe" else gsm_density(xs[::4], fam)
        xx = xs if fam != "horseshoe" else xs[::4]
        ax[0, 0].plot(xx, np.log(d), c=c, label=nm)
    ax[0, 0].set_xlabel("$x$")
    ax[0, 0].set_ylabel("$\\log p(x)$")
    ax[0, 0].set_ylim(-14, 0.5)
    ax[0, 0].legend(fontsize=7.5)
    ys = np.linspace(0, 8, 200)
    for nm, fam, p, c in fams + [("spike and slab $\\pi=0.2$", "spike", dict(pi=0.2), ORANGE)]:
        ax[0, 1].plot(ys, gsm_posterior_mean(ys, fam, 1.0, **p), c=c, label=nm)
    ax[0, 1].plot(ys, ys, c=GREY, ls=":")
    ax[0, 1].set_xlabel("$y$")
    ax[0, 1].set_ylabel("$E[x\\mid y]$")
    ax[0, 1].legend(fontsize=7, loc="upper left")
    savefig(fig, CH, "figx28-1", out_dir)


# =========================================================================== data for the demonstrations
def export_demo_data():
    out = {}
    for kind in ("uniform", "laplace", "gauss", "mixed"):
        S, A, Xw, Wh = whitened_mix(kind, n=400, seed=0)
        ths, f = ica_curve(Xw, 181)
        i = int(np.argmin(f))
        out[kind] = dict(true_deg=true_angle_deg(kind, 400, 0), X=np.round(Xw, 5).tolist(), theta_deg=np.round(np.degrees(ths), 3).tolist(), nll=np.round(f, 6).tolist(),
                         best_deg=float(np.degrees(ths[i])), best_nll=float(f[i]))
    save_json("ch28-ica.json", out)
    docs, theta = bank_corpus()
    rng = np.random.default_rng(7)
    init = [rng.integers(0, 2, len(d)) for d in docs]
    Nvk = np.zeros((5, 2))
    Nik = np.zeros((len(docs), 2))
    for i, d in enumerate(docs):
        for w, k in zip(d, init[i]):
            Nvk[w, k] += 1
            Nik[i, k] += 1
    ref = {a: float(lda_collapsed_logjoint(Nvk, Nik, a, 0.5)) for a in (0.1, 0.5, 1.0)}
    ref_g = {}
    for fam, p in (("student", dict(nu=2)), ("laplace", dict(lam=1.4)), ("horseshoe", {}), ("spike", dict(pi=0.2))):
        ref_g[fam] = float(gsm_posterior_mean(np.array([3.0]), fam, 1.0, **p)[0])
    save_json("ch28-lda.json", dict(vocab=BANK["vocab"], docs=[d.tolist() for d in docs], topics=BANK["topics"].tolist(),
                                    theta=np.round(theta, 4).tolist(), init=[a.tolist() for a in init], logjoint_init_beta05=ref))
    save_json("ch28-gsm-ref.json", dict(shrink_y3=ref_g))


def data_demo(out_dir=None):
    """Export the small data sets used by the demonstration pages."""
    export_demo_data()


FIGURES = {
    "28.1": fig_28_1, "28.2": fig_28_2, "28.3": fig_28_3, "28.4": fig_28_4, "28.5": fig_28_5, "28.6": fig_28_6, "28.8": fig_28_8,
    "28.11": fig_28_11, "28.12": fig_28_12, "28.13": fig_28_13, "28.14": fig_28_14, "28.18": fig_28_18, "28.19": fig_28_19,
    "28.21": fig_28_21, "28.32": fig_28_32, "28.33": fig_28_33, "28.34": fig_28_34, "S28.2": fig_S28_2, "S28.3": fig_S28_3,
    "x28.1": fig_x28_1, "x28.2": fig_x28_2, "x28.3": fig_x28_3, "data": data_demo,
}

if __name__ == "__main__":
    if len(sys.argv) == 1:
        common.run(FIGURES, CH, [])
    else:
        common.run(FIGURES, CH)
