"""Murphy (2023), Chapter 10: Variational inference (with Supplement Chapter 10).

Companion code for Chapter 10 of K. P. Murphy, Probabilistic Machine Learning: Advanced Topics
(MIT Press, 2023; December 2025 draft), pp. 439-482 of the book and Supplement Chapter 10, written
from scratch with numpy, scipy, matplotlib and (for the stochastic-gradient fits) PyTorch on the CPU,
to be read next to the lecture notes (../ch10-variational-inference.html).

Methods (each is a plain function below)
* Section 10.1, the ELBO: exact Gaussian posterior for the mean of a 2d Gaussian, Gaussian VI with
  full, diagonal and rank-one-plus-diagonal covariance (gvi_fit, a reparameterised stochastic-gradient
  fitter for any differentiable log density, with optional fixed noise for deterministic ADVI).
* Section 10.2, gradient-based VI: reparameterised SVI for a Bayesian GMM with a Normal-Gamma-Dirichlet
  mean-field posterior (svi_gmm), ADVI for a GMM with a Gaussian posterior on unconstrained parameters
  (advi_gmm), the score-function (REINFORCE) estimator with the optimal control variate (bbvi_grads).
* Section 10.3, coordinate ascent VI: mean-field Ising denoising (ising_meanfield), VB for a univariate
  Gaussian (vb_unigauss, normal_gamma_logpdf, vb_unigauss_bound), VBEM for a Gaussian mixture with
  its lower bound (vbgmm), the digamma shrinkage dynamics of Figure 10.11 (vb_count_dynamics).
* Section 10.5, tighter bounds: the ELBO, the IWAE bound and the EUBO on a toy model with a bimodal
  posterior (toy_logjoint, iwae_bound, eubo).
* Section 10.7, expectation propagation: EP, damped EP, power EP and ADF for a one-parameter logistic
  model (ep_logistic_1d), the tilted distribution of Figure 10.15.
* Supplement 10.1, more Gaussian VI: Bayesian linear regression with a uniform prior on sigma, HMC
  (hmc, written here) against diagonal and full Gaussian ADVI; Bayesian logistic regression with full and
  rank-one Gaussian VI against random-walk Metropolis.
* Supplement 10.2, Bayesian gradient descent (bgd_update).
* Supplement 10.3, conjugate-computation VI for logistic regression (cvi_logistic).
* Supplement 10.4, VI for graphical models: exact log Z of a small Ising grid by enumeration, naive
  mean field, loopy BP with the Bethe free energy, tree-reweighted BP with spanning-tree edge
  probabilities (ising_logz_methods).

Data. Old Faithful (Figures 10.7, 10.12 to 10.14; the 272 eruptions shipped with R as datasets::faithful,
standardised). The supplement's Africa ruggedness data are not bundled with any library available here,
so Figures S10.1 to S10.3 use a stand-in with the same structure: scikit-learn's diabetes data, log
disease progression regressed on body-mass index (BMI), sex and their interaction. Everything else is
simulated with fixed seeds (Figure 10.9 uses a synthetic binary image of the letter A).

Figures. Reproduced here: 10.2, 10.6, 10.7, 10.9, 10.10, 10.11, 10.12, 10.13, 10.14, 10.15 and, from the
supplement, S10.1, S10.2, S10.3, S10.4. Extra figures for gaps filled in the notes: x10-a (variance of the
score-function gradient with and without the control variate), x10-b (ELBO, IWAE and EUBO against the
number of samples), x10-c (mean field, Bethe and tree-reweighted approximations of log Z on an Ising grid).
Skipped, with the reason:
  10.1   the variational family as an oval in parameter space (a hand-drawn schematic);
  10.3, 10.5  graphical models of local and global latent variables (diagrams);
  10.4   the reparameterisation trick as a computation graph (a diagram);
  10.8   the grid MRF with local evidence nodes (a diagram);
  S10.5  factorial HMM and its two variational approximations (diagrams);
  S10.6  a graph and three spanning trees (a diagram; the edge appearance probabilities it explains are
         computed in ising_logz_methods).
Run `python3 ch10_variational_inference.py --list`, `python3 ch10_variational_inference.py` (all
figures) or `python3 ch10_variational_inference.py --fig 10.9`. Files go to ../img/ch10/; the data used
by the browser demonstrations go to ../data/ch10-*.json.
"""
import itertools
import json
import os
import sys

os.environ.setdefault("OPENBLAS_NUM_THREADS", "1")
import numpy as np
from scipy import optimize, special, stats

import common
from common import (BLUE, GREEN, GREY, ORANGE, PURPLE, RED, ellipse_xy, logsumexp, panel_grid, panel_label,
                    savefig, sigmoid)
import matplotlib.pyplot as plt

CH = 10
HERE = os.path.dirname(os.path.abspath(__file__))
CACHE_DIR = os.path.join(HERE, "cache", "ch10")
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
os.makedirs(CACHE_DIR, exist_ok=True)

def old_faithful():
    """The 272 Old Faithful eruptions (duration, waiting time), standardised. The same CSV ships with the
    companion courses; the copy in this course's data folder is used when present."""
    for path in (os.path.join(HERE, "data", "faithful.csv"),
                 os.path.normpath(os.path.join(HERE, "..", "..", "ml", "code", "data", "faithful.csv"))):
        if os.path.exists(path):
            X = np.loadtxt(path, delimiter=",", skiprows=1)
            return (X - X.mean(0)) / X.std(0)
    raise FileNotFoundError("faithful.csv")



# =========================================================================== seeded generator of the demos
class KitRng:
    """The seeded generator of the browser demonstrations (mulberry32 with Box-Muller), so that a page
    and this module draw exactly the same random numbers from the same seed."""

    def __init__(self, seed):
        self.a = seed & 0xFFFFFFFF
        self.spare = None

    def u(self):
        self.a = (self.a + 0x6D2B79F5) & 0xFFFFFFFF
        a = self.a
        t = ((a ^ (a >> 15)) * (1 | a)) & 0xFFFFFFFF
        t = (t + (((t ^ (t >> 7)) * (61 | t)) & 0xFFFFFFFF) ^ t) & 0xFFFFFFFF
        return ((t ^ (t >> 14)) & 0xFFFFFFFF) / 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 = np.sqrt(-2.0 * np.log(self.pos()))
        th = 2.0 * np.pi * self.u()
        self.spare = r * np.sin(th)
        return r * np.cos(th)


# =========================================================================== 10.1 Gaussian example
def gauss2d_problem():
    """The 2d example of Section 10.1.2: prior N(m0, V0), N observations x_n ~ N(z, Sigma).
    Returns the data summary and the exact posterior (mean, covariance)."""
    rng = np.random.default_rng(3)
    m0, V0 = np.zeros(2), np.eye(2)
    Sigma = np.array([[1.0, 0.9], [0.9, 1.0]])
    ztrue = np.array([0.5, 1.8])
    N = 12
    X = rng.multivariate_normal(ztrue, Sigma, size=N)
    Prec = np.linalg.inv(V0) + N * np.linalg.inv(Sigma)
    Vn = np.linalg.inv(Prec)
    mn = Vn @ (np.linalg.solve(V0, m0) + N * np.linalg.solve(Sigma, X.mean(0)))
    return dict(m0=m0, V0=V0, Sigma=Sigma, X=X, N=N, mn=mn, Vn=Vn)


def gauss_kl(m1, S1, m2, S2):
    """KL(N(m1,S1) || N(m2,S2))."""
    D = len(m1)
    S2i = np.linalg.inv(S2)
    d = m2 - m1
    return 0.5 * (np.trace(S2i @ S1) + d @ S2i @ d - D + np.linalg.slogdet(S2)[1] - np.linalg.slogdet(S1)[1])


def gvi_fit(logp, D, family="full", rank=1, steps=3000, lr=0.02, S=8, seed=0, fixed_eps=None, init_mu=None,
            init_logs=-1.0, record=False):
    """Gaussian VI by reparameterised stochastic gradients on the ELBO (Section 10.2.1).

    logp maps a (S, D) torch tensor of samples to (S,) log joint values. family is 'full' (Cholesky
    factor, (10.51)-(10.55)), 'diag' (mean field, (10.43)-(10.47)) or 'lowrank' (Sigma = B B^T + C^2,
    (10.56)). With fixed_eps (an (S, D) array) the noise is held fixed: deterministic ADVI [Ing20], here
    optimised by L-BFGS. Returns a dict with mu, Sigma and the final ELBO estimate.
    """
    torch = common.torch_setup(seed)
    tt = torch.float64
    mu = torch.tensor(np.zeros(D) if init_mu is None else np.asarray(init_mu, float), dtype=tt, requires_grad=True)
    logs = torch.full((D,), float(init_logs), dtype=tt, requires_grad=True)
    params = [mu, logs]
    if family == "full":
        Lraw = torch.zeros((D, D), dtype=tt, requires_grad=True)
        params.append(Lraw)
    elif family == "lowrank":
        g = np.random.default_rng(seed)
        B = torch.tensor(0.1 * g.standard_normal((D, rank)), dtype=tt, requires_grad=True)
        params.append(B)
    mask = torch.tril(torch.ones(D, D, dtype=tt), -1)

    def sample_and_entropy(eps):
        s = torch.exp(logs)
        if family == "diag":
            z = mu + s * eps
            ent = logs.sum()
        elif family == "full":
            L = mask * Lraw + torch.diag(s)      # (10.54): diagonal of L is sigma
            z = mu + eps @ L.T
            ent = logs.sum()                     # (10.55)
        else:
            Sig = B @ B.T + torch.diag(s ** 2)
            L = torch.linalg.cholesky(Sig)
            z = mu + eps @ L.T
            ent = torch.log(torch.diagonal(L)).sum()
        return z, ent + 0.5 * D * (1.0 + np.log(2 * np.pi))

    def neg_elbo(eps):
        z, ent = sample_and_entropy(eps)
        return -(logp(z).mean() + ent)

    hist = []
    if fixed_eps is not None:
        eps = torch.tensor(fixed_eps, dtype=tt)
        opt = torch.optim.LBFGS(params, lr=1.0, max_iter=steps, tolerance_grad=1e-10, tolerance_change=1e-14,
                                history_size=50, line_search_fn="strong_wolfe")

        def closure():
            opt.zero_grad()
            l = neg_elbo(eps)
            l.backward()
            return l
        opt.step(closure)
    else:
        opt = torch.optim.Adam(params, lr=lr)
        gen = torch.Generator().manual_seed(seed)
        for it in range(steps):
            eps = torch.randn((S, D), dtype=tt, generator=gen)
            opt.zero_grad()
            l = neg_elbo(eps)
            l.backward()
            opt.step()
            if record:
                hist.append(-l.item())
    with torch.no_grad():
        s = torch.exp(logs)
        if family == "diag":
            Sig = torch.diag(s ** 2)
        elif family == "full":
            L = mask * Lraw + torch.diag(s)
            Sig = L @ L.T
        else:
            Sig = B @ B.T + torch.diag(s ** 2)
        eps = torch.randn((4000, D), dtype=tt, generator=torch.Generator().manual_seed(seed + 1))
        elbo = -neg_elbo(eps).item()
    return dict(mu=mu.detach().numpy().copy(), Sigma=Sig.numpy().copy(), elbo=elbo, hist=np.array(hist))


def gauss2d_fits(steps=4000):
    P = gauss2d_problem()
    torch = common.torch_setup(0)
    Lam = torch.tensor(np.linalg.inv(P["Vn"]))
    mn = torch.tensor(P["mn"])

    def logp(z):    # log posterior up to a constant (the target is Gaussian)
        d = z - mn
        return -0.5 * ((d @ Lam) * d).sum(1)
    fits = {fam: gvi_fit(logp, 2, fam, steps=steps, lr=0.02, S=16, seed=1, init_mu=[0.0, 0.0])
            for fam in ("full", "diag", "lowrank")}
    return P, fits


def fig_10_2(out=None):
    """Gaussian VI for the posterior of a 2d Gaussian mean: full, diagonal, rank-one-plus-diagonal."""
    P, fits = gauss2d_fits()
    fig, ax = plt.subplots(figsize=(4.4, 4.0))
    for (lab, m, S, c, ls) in [("analytic", P["mn"], P["Vn"], "k", "-"),
                               ("mean field", fits["diag"]["mu"], fits["diag"]["Sigma"], GREEN, "-"),
                               ("low rank", fits["lowrank"]["mu"], fits["lowrank"]["Sigma"], RED, "--"),
                               ("full rank", fits["full"]["mu"], fits["full"]["Sigma"], BLUE, ":")]:
        for k, nsd in enumerate((1.0, 2.0)):
            x, y = ellipse_xy(m, S, nsd)
            ax.plot(x, y, color=c, ls=ls, lw=1.6, label=lab if k == 0 else None)
    ax.set_xlabel(r"$z_1$")
    ax.set_ylabel(r"$z_2$")
    ax.legend(loc="lower right", frameon=False)
    ax.set_aspect("equal", adjustable="datalim")
    savefig(fig, CH, "fig10-2", out)


# =========================================================================== 10.2.1.5 SVI for a GMM
def gmm3_data(N=3000, seed=0):
    rng = np.random.default_rng(seed)
    mus = np.array([[2.0, 0.0], [-2.0, -4.0], [-2.0, 4.0]])
    z = rng.integers(0, 3, N)
    return mus[z] + rng.standard_normal((N, 2)), mus


def svi_gmm(X, K=3, epochs=1000, batch=500, lr=0.01, seed=0):
    """Algorithm 10.2: reparameterised SVI for the Bayesian GMM (10.58)-(10.61) with mean-field posterior
    N(mu_kd | m, s) Ga(lambda_kd | alpha, beta) Dir(pi | c); minibatches scaled by N/B, one sample of theta."""
    torch = common.torch_setup(seed)
    D = torch.distributions
    tt = torch.float64
    Xt = torch.tensor(X, dtype=tt)
    N, Dd = X.shape
    g = np.random.default_rng(seed)
    m = torch.tensor(X[g.choice(N, K, replace=False)], dtype=tt, requires_grad=True)
    log_s = torch.full((K, Dd), -2.0, dtype=tt, requires_grad=True)
    log_a = torch.full((K, Dd), np.log(5.0), dtype=tt, requires_grad=True)
    log_b = torch.full((K, Dd), np.log(5.0), dtype=tt, requires_grad=True)
    log_c = torch.zeros(K, dtype=tt, requires_grad=True)
    params = [m, log_s, log_a, log_b, log_c]
    opt = torch.optim.Adam(params, lr=lr)
    pmu, plam, ppi = D.Normal(0.0, 1.0), D.Gamma(torch.tensor(5.0, dtype=tt), torch.tensor(5.0, dtype=tt)), \
        D.Dirichlet(torch.ones(K, dtype=tt))
    gen = torch.Generator().manual_seed(seed)
    trace = []
    for ep in range(epochs):
        perm = torch.randperm(N, generator=gen)
        for b0 in range(0, N, batch):
            xb = Xt[perm[b0:b0 + batch]]
            qmu, qlam, qpi = D.Normal(m, torch.exp(log_s)), D.Gamma(torch.exp(log_a), torch.exp(log_b)), \
                D.Dirichlet(torch.exp(log_c))
            mu, lam, pi = qmu.rsample(), qlam.rsample(), qpi.rsample()
            # log p(x | theta) for each point and component, diagonal precisions
            ll = (0.5 * torch.log(lam / (2 * np.pi)) - 0.5 * lam * (xb[:, None, :] - mu[None]) ** 2).sum(-1)
            lik = torch.logsumexp(torch.log(pi)[None] + ll, 1).sum() * (N / xb.shape[0])
            lprior = pmu.log_prob(mu).sum() + plam.log_prob(lam).sum() + ppi.log_prob(pi)
            lq = qmu.log_prob(mu).sum() + qlam.log_prob(lam).sum() + qpi.log_prob(pi)
            loss = -(lik + lprior - lq)          # line 6 of Algorithm 10.2
            opt.zero_grad()
            loss.backward()
            opt.step()
        trace.append(-loss.item())
    with torch.no_grad():
        res = dict(m=m.numpy().copy(), s=torch.exp(log_s).numpy().copy(), a=torch.exp(log_a).numpy().copy(),
                   b=torch.exp(log_b).numpy().copy(), c=torch.exp(log_c).numpy().copy(), trace=np.array(trace))
    return res


def _svi_gmm_cached():
    path = os.path.join(CACHE_DIR, "svi_gmm.npz")
    if os.path.exists(path):
        z = np.load(path)
        return {k: z[k] for k in z.files}
    X, _ = gmm3_data()
    r = svi_gmm(X)
    np.savez(path, **r)
    return r


def fig_10_6(out=None):
    """SVI for a mixture of 3 Gaussians in 2d: data, fitted density, posterior of one mean."""
    X, mus = gmm3_data()
    r = _svi_gmm_cached()
    pi = r["c"] / r["c"].sum()
    lam = r["a"] / r["b"]
    fig, axes = panel_grid(1, 3, size=(3.1, 2.9))
    ax = axes[0, 0]
    ax.scatter(X[:, 0], X[:, 1], s=2, color=BLUE, alpha=0.4)
    ax.set_xlim(-8, 8)
    ax.set_ylim(-8, 8)
    panel_label(ax, "a")
    ax = axes[0, 1]
    g = np.linspace(-7, 7, 160)
    G1, G2 = np.meshgrid(g, g)
    pts = np.c_[G1.ravel(), G2.ravel()]
    dens = np.zeros(len(pts))
    for k in range(3):
        sd = 1 / np.sqrt(lam[k])
        dens += pi[k] * stats.norm.pdf(pts[:, 0], r["m"][k, 0], sd[0]) * stats.norm.pdf(pts[:, 1], r["m"][k, 1], sd[1])
    cs = ax.contourf(G1, G2, dens.reshape(G1.shape), levels=12, cmap="viridis")
    fig.colorbar(cs, ax=ax, fraction=0.046, pad=0.03)
    panel_label(ax, "b")
    ax = axes[0, 2]
    # the component whose posterior mean is near (-2,-4) (the book's mu_1 matched mu*_2 by label switching)
    k = int(np.argmin(((r["m"] - mus[1]) ** 2).sum(1)))
    rng = np.random.default_rng(7)
    S = r["m"][k] + r["s"][k] * rng.standard_normal((10000, 2))
    kde = stats.gaussian_kde(S.T)
    a1 = np.linspace(S[:, 0].min(), S[:, 0].max(), 80)
    a2 = np.linspace(S[:, 1].min(), S[:, 1].max(), 80)
    A1, A2 = np.meshgrid(a1, a2)
    ax.contourf(A1, A2, kde(np.c_[A1.ravel(), A2.ravel()].T).reshape(A1.shape), levels=10, cmap="viridis")
    ax.set_xlabel(r"$\mu_{k,1}$")
    ax.set_ylabel(r"$\mu_{k,2}$")
    panel_label(ax, "c")
    fig.tight_layout()
    savefig(fig, CH, "fig10-6", out)
    return r


# =========================================================================== 10.2.2.3 ADVI for a GMM
def advi_gmm(X, K=10, steps=6000, lr=0.02, S=4, seed=0, map_only=False):
    """ADVI (Section 10.2.2) for a K-component 2d GMM with full covariances.

    Constrained parameters and bijections: pi = softmax([u, 0]) on the simplex (additive log ratio, with
    its log Jacobian), log sigma_kd (log-normal prior N(0, 1) on the log scale), rho_k = tanh(v_k) (the
    LKJ(1) prior on a 2x2 correlation is uniform on (-1, 1)), mu_kd ~ N(0, 3^2); pi ~ Dir(1).
    The posterior on the unconstrained vector u is a Gaussian with one full block per component plus a
    block for the weights (block-diagonal, as in the book). map_only=True fixes Sigma = 0 (MAP)."""
    torch = common.torch_setup(seed)
    tt = torch.float64
    Xt = torch.tensor(X, dtype=tt)
    g = np.random.default_rng(seed)
    blocks = [K - 1] + [5] * K            # weights, then (mu1, mu2, log s1, log s2, v) per component
    Dtot = sum(blocks)
    init = np.zeros(Dtot)
    init[K - 1:] = np.concatenate([np.r_[X[g.integers(len(X))], -1.0, -1.0, 0.0] for _ in range(K)])
    mu = torch.tensor(init, dtype=tt, requires_grad=True)
    Ls = [torch.zeros((b, b), dtype=tt, requires_grad=True) for b in blocks]
    logd = torch.full((Dtot,), -3.0, dtype=tt, requires_grad=True)
    params = [mu] if map_only else [mu, logd] + Ls
    opt = torch.optim.Adam(params, lr=lr)
    gen = torch.Generator().manual_seed(seed)
    offs = np.cumsum([0] + blocks)

    def logjoint(u):                       # u: (S, Dtot); returns log p(D, T^{-1}(u)) + log|J|
        uw = u[:, :K - 1]
        logits = torch.cat([uw, torch.zeros(u.shape[0], 1, dtype=tt)], 1)
        logpi = logits - torch.logsumexp(logits, 1, keepdim=True)
        # Dir(1) density is constant on the simplex; log|J| of the additive log-ratio map = sum_k log pi_k
        lj = logpi.sum(1)
        P = u[:, K - 1:].reshape(u.shape[0], K, 5)
        m, ls, v = P[..., :2], P[..., 2:4], P[..., 4]
        s, rho = torch.exp(ls), torch.tanh(v)
        lpr = (-0.5 * (m / 3.0) ** 2).sum((1, 2)) + (-0.5 * ls ** 2).sum((1, 2)) + torch.log1p(-rho ** 2 + 1e-12).sum(1)
        d = (Xt[None, :, None, :] - m[:, None]) / s[:, None]          # (S, N, K, 2)
        q = (d[..., 0] ** 2 - 2 * rho[:, None] * d[..., 0] * d[..., 1] + d[..., 1] ** 2) / (1 - rho[:, None] ** 2)
        lnorm = -np.log(2 * np.pi) - ls.sum(-1) - 0.5 * torch.log(1 - rho ** 2)
        ll = torch.logsumexp(logpi[:, None] + lnorm[:, None] - 0.5 * q, 2).sum(1)
        return ll + lpr + lj

    for it in range(steps):
        if map_only:
            l = -logjoint(mu[None])[0]
        else:
            eps = torch.randn((S, Dtot), dtype=tt, generator=gen)
            zs, ent = [], 0.0
            for j, b in enumerate(blocks):
                L = torch.tril(Ls[j], -1) + torch.diag(torch.exp(logd[offs[j]:offs[j + 1]]))
                zs.append(eps[:, offs[j]:offs[j + 1]] @ L.T)
            u = mu + torch.cat(zs, 1)
            l = -(logjoint(u).mean() + logd.sum())
        opt.zero_grad()
        l.backward()
        opt.step()
    with torch.no_grad():
        Lfull = np.zeros((Dtot, Dtot))
        for j, b in enumerate(blocks):
            L = torch.tril(Ls[j], -1) + torch.diag(torch.exp(logd[offs[j]:offs[j + 1]]))
            Lfull[offs[j]:offs[j + 1], offs[j]:offs[j + 1]] = L.numpy()
    return dict(mu=mu.detach().numpy().copy(), L=Lfull if not map_only else np.zeros((Dtot, Dtot)), K=K)


def advi_unpack(u, K):
    logits = np.r_[u[:K - 1], 0.0]
    pi = np.exp(logits - logsumexp(logits))
    P = u[K - 1:].reshape(K, 5)
    out = []
    for k in range(K):
        s, rho = np.exp(P[k, 2:4]), np.tanh(P[k, 4])
        S = np.array([[s[0] ** 2, rho * s[0] * s[1]], [rho * s[0] * s[1], s[1] ** 2]])
        out.append((P[k, :2], S))
    return pi, out


def _advi_cached():
    path = os.path.join(CACHE_DIR, "advi_gmm.npz")
    if os.path.exists(path):
        z = np.load(path)
        return dict(mu=z["mu"], L=z["L"], K=10), dict(mu=z["mu_map"], L=None, K=10)
    X = old_faithful()
    full = advi_gmm(X, map_only=False)
    mp = advi_gmm(X, map_only=True, steps=4000)
    np.savez(path, mu=full["mu"], L=full["L"], mu_map=mp["mu"])
    return full, mp


def fig_10_7(out=None):
    """ADVI for a GMM with K = 10 on Old Faithful: the MAP fit and 3 posterior samples."""
    X = old_faithful()
    full, mp = _advi_cached()
    rng = np.random.default_rng(2)
    us = [mp["mu"]] + [full["mu"] + full["L"] @ rng.standard_normal(len(full["mu"])) for _ in range(3)]
    fig = plt.figure(figsize=(8.6, 6.0))
    outer = fig.add_gridspec(2, 2, wspace=0.28, hspace=0.32)
    cols = plt.cm.tab10(np.arange(10))
    for i, u in enumerate(us):
        sub = outer[i // 2, i % 2].subgridspec(1, 2, width_ratios=[3, 1.1], wspace=0.35)
        ax, axw = fig.add_subplot(sub[0]), fig.add_subplot(sub[1])
        pi, comps = advi_unpack(u, 10)
        ax.scatter(X[:, 0], X[:, 1], s=4, color="k", label="data")
        for k, (m, S) in enumerate(comps):
            for nsd in (1.0, 2.0):
                x, y = ellipse_xy(m, S, nsd)
                ax.fill(x, y, color=cols[k], alpha=min(0.9, 0.9 * pi[k] / pi.max()) * 0.35, lw=0)
            ax.plot(m[0], m[1], "^", color=RED, ms=4, label="loc" if k == 0 else None)
        ax.set_xlim(-2.2, 2.0)
        ax.set_ylim(-2.6, 2.4)
        ax.legend(loc="upper left", fontsize=7, frameon=False)
        axw.barh(np.arange(10), pi, color=cols)
        axw.set_ylim(9.6, -0.6)
        axw.set_yticks(range(10))
        axw.set_xlabel("weights", fontsize=8)
        axw.set_ylabel("mixture components", fontsize=8)
        axw.tick_params(labelsize=7)
        ax.set_title("(%s) %s" % ("abcd"[i], "MAP" if i == 0 else "posterior sample %d" % i), fontsize=9)
    savefig(fig, CH, "fig10-7", out)


# =========================================================================== 10.2.3 BBVI
def bbvi_grads(logjoint, mu, logs, S, rng, c=None):
    """Score-function (REINFORCE) gradient (10.67) of the ELBO of q = N(mu, e^{2 logs}) in 1d, naive and
    with the score as control variate (10.73); c=None uses the estimated optimal constant (10.74).
    Returns per-sample terms so the caller can average; shape (S, 2) for the two parameters."""
    s = np.exp(logs)
    z = mu + s * rng.standard_normal(S)
    Lt = logjoint(z) - stats.norm.logpdf(z, mu, s)
    g = np.stack([(z - mu) / s ** 2, ((z - mu) ** 2 / s ** 2 - 1.0)], 1)   # score wrt (mu, log s)
    naive = g * Lt[:, None]
    if c is None:
        gt = naive
        c = np.array([np.cov(gt[:, i], g[:, i])[0, 1] / np.var(g[:, i], ddof=1) for i in range(2)])
    cv = g * (Lt[:, None] - c[None])
    return naive, cv, c


def toy_bbvi_logjoint(z):
    """log p(x, z) for a Poisson-count model with a Gaussian prior on the log rate (not reparameterised
    in the blackbox setting): z ~ N(0, 1), x | z ~ Poi(e^z), x = 4."""
    x = 4
    return stats.norm.logpdf(z) + x * z - np.exp(z) - special.gammaln(x + 1)


def fig_x10_a(out=None):
    """Variance of the score-function gradient with and without the control variate, against S."""
    rng = np.random.default_rng(0)
    mu, logs = 0.5, np.log(0.5)
    Ss = [1, 2, 5, 10, 20, 50, 100, 200]
    reps = 400
    v_naive, v_cv, v_rep = [], [], []
    _, _, c_opt = bbvi_grads(toy_bbvi_logjoint, mu, logs, 200000, np.random.default_rng(99), c=None)   # pilot run
    for S in Ss:
        gn, gc, gr = [], [], []
        for r in range(reps):
            n, c, _ = bbvi_grads(toy_bbvi_logjoint, mu, logs, S, rng, c=c_opt)
            gn.append(n.mean(0)[0])
            gc.append(c.mean(0)[0])
            # reparameterised estimate of d/dmu: E[d/dz log p(x,z)]
            z = mu + np.exp(logs) * rng.standard_normal(S)
            gr.append(np.mean(-z + 4 - np.exp(z)))
        v_naive.append(np.var(gn))
        v_cv.append(np.var(gc))
        v_rep.append(np.var(gr))
    fig, ax = plt.subplots(figsize=(4.6, 3.4))
    ax.loglog(Ss, v_naive, "o-", color=RED, label="score function (10.67)")
    ax.loglog(Ss, v_cv, "s-", color=BLUE, label="with control variate (10.73)")
    ax.loglog(Ss, v_rep, "^-", color=GREEN, label="reparameterised (10.40)")
    ax.set_xlabel("samples S")
    ax.set_ylabel(r"variance of $\widehat{\partial \mathcal{L}/\partial\mu}$")
    ax.legend(frameon=False, fontsize=8)
    savefig(fig, CH, "figx10-a", out)
    return dict(S=Ss, naive=v_naive, cv=v_cv, rep=v_rep, c=c_opt)


# =========================================================================== 10.3.2 Ising mean field
def letter_a(n=64):
    """A binary image (values -1/+1) of the letter A on an n x n grid, drawn from line segments."""
    yy, xx = np.mgrid[0:n, 0:n] / (n - 1.0)
    img = -np.ones((n, n))

    def seg(p, q, w):
        p, q = np.array(p), np.array(q)
        d = q - p
        t = np.clip(((xx - p[0]) * d[0] + (yy - p[1]) * d[1]) / (d @ d), 0, 1)
        return (xx - p[0] - t * d[0]) ** 2 + (yy - p[1] - t * d[1]) ** 2 < w ** 2
    m = seg((0.5, 0.1), (0.2, 0.9), 0.075) | seg((0.5, 0.1), (0.8, 0.9), 0.075) | seg((0.33, 0.6), (0.67, 0.6), 0.06)
    img[m] = 1.0
    return img


def ising_noisy(img, sigma, seed):
    """x = z + sigma * eps with eps from the demo generator (row-major order), so pages can replay it."""
    rng = KitRng(seed)
    e = np.array([rng.norm() for _ in range(img.size)]).reshape(img.shape)
    return img + sigma * e


def ising_meanfield(x, W=1.0, sigma=2.0, lam=0.5, n_iter=15, parallel=True, mu0=None):
    """Mean-field CAVI for the Ising posterior (10.88)-(10.101) on a 4-neighbour grid with Gaussian
    local evidence N(x_i | z_i, sigma^2), for which 0.5 (L+ - L-) = x_i / sigma^2.
    Returns the list of mean images mu^t (t = 0..n_iter) and the ELBO after each sweep."""
    h = x / sigma ** 2
    mu = np.tanh(h) if mu0 is None else mu0.copy()     # initialise from the local evidence alone
    out, elbos = [mu.copy()], [ising_elbo(mu, x, W, sigma)]
    n0, n1 = x.shape
    for t in range(n_iter):
        if parallel:
            m = np.zeros_like(mu)
            m[1:] += mu[:-1]
            m[:-1] += mu[1:]
            m[:, 1:] += mu[:, :-1]
            m[:, :-1] += mu[:, 1:]
            mu = (1 - lam) * mu + lam * np.tanh(W * m + h)   # (10.101)
        else:
            for i in range(n0):
                for j in range(n1):
                    s = 0.0
                    if i > 0: s += mu[i - 1, j]
                    if i < n0 - 1: s += mu[i + 1, j]
                    if j > 0: s += mu[i, j - 1]
                    if j < n1 - 1: s += mu[i, j + 1]
                    mu[i, j] = (1 - lam) * mu[i, j] + lam * np.tanh(W * s + h[i, j])
        out.append(mu.copy())
        elbos.append(ising_elbo(mu, x, W, sigma))
    return out, np.array(elbos)


def ising_elbo(mu, x, W, sigma):
    """ELBO of the factorised q(z_i = +1) = (1 + mu_i)/2, up to the constant -log Z_0 of the prior:
    E_q[sum_edges W z_i z_j + sum_i L_i(z_i)] + sum_i H(q_i)."""
    pair = W * ((mu[1:] * mu[:-1]).sum() + (mu[:, 1:] * mu[:, :-1]).sum())
    p = np.clip((1 + mu) / 2, 1e-300, 1)
    qm = np.clip((1 - mu) / 2, 1e-300, 1)
    Lp = -0.5 * (x - 1) ** 2 / sigma ** 2
    Lm = -0.5 * (x + 1) ** 2 / sigma ** 2
    ent = -(p * np.log(p) + qm * np.log(qm)).sum()
    return pair + (p * Lp + qm * Lm).sum() + ent - x.size * np.log(np.sqrt(2 * np.pi) * sigma)


ISING_SEED = 2024
ISING_N = 64


def fig_10_9(out=None):
    """Mean-field image denoising with an Ising prior: means after 1, 3 and 15 parallel damped sweeps."""
    img = letter_a(ISING_N)
    x = ising_noisy(img, 2.0, ISING_SEED)
    mus, el = ising_meanfield(x, 1.0, 2.0, 0.5, 15)
    fig, axes = panel_grid(1, 4, size=(2.5, 2.5))
    panels = [(x, "noisy image, $\\sigma=2$"), (mus[1], "after 1 sweep"), (mus[3], "after 3 sweeps"),
              (mus[15], "mean after 15 sweeps")]
    for k, (a, t) in enumerate(panels):
        ax = axes[0, k]
        im = ax.imshow(a, cmap="gray", vmin=-1 if k else None, vmax=1 if k else None)
        ax.set_title(t, fontsize=9)
        ax.set_xticks([])
        ax.set_yticks([])
        if k:
            panel_label(ax, "abc"[k - 1])
    fig.tight_layout()
    savefig(fig, CH, "fig10-9", out)
    return mus, el


# =========================================================================== 10.3.4 VB for a univariate Gaussian
def unigauss_data(N=10, seed=1):
    rng = np.random.default_rng(seed)
    x = rng.normal(0.0, 1.0, N)
    return x - x.mean()     # centred so that the exact posterior is centred at zero, as in the book's figure


def normal_gamma_post(x, mu0, k0, a0, b0):
    N, xb = len(x), x.mean()
    kN = k0 + N
    mN = (k0 * mu0 + N * xb) / kN
    aN = a0 + N / 2
    bN = b0 + 0.5 * ((x - xb) ** 2).sum() + k0 * N * (xb - mu0) ** 2 / (2 * kN)
    return mN, kN, aN, bN


def normal_gamma_logpdf(mu, lam, mN, kN, aN, bN):
    return stats.norm.logpdf(mu, mN, 1 / np.sqrt(kN * lam)) + stats.gamma.logpdf(lam, aN, scale=1 / bN)


def vb_unigauss(x, mu0, k0, a0, b0, init, n_iter=5):
    """CAVI updates (10.119)-(10.122) for q(mu) q(lambda) = N(mu | muN, 1/kN) Ga(lambda | aN, bN), starting
    from init = (muN, kN, aN, bN). Returns the list of states: the initial one, then the state after each
    update of q(mu) and after each update of q(lambda)."""
    N, xb = len(x), x.mean()
    muN, kN, aN, bN = init
    states = [(muN, kN, aN, bN)]
    for it in range(n_iter):
        muN = (k0 * mu0 + N * xb) / (k0 + N)                              # (10.119)
        kN = (k0 + N) * aN / bN                                          # (10.120)
        states.append((muN, kN, aN, bN))
        Emu, Emu2 = muN, 1 / kN + muN ** 2                              # (10.116)-(10.117)
        aN = a0 + (N + 1) / 2.0                                          # (10.121)
        bN = b0 + 0.5 * k0 * (Emu2 + mu0 ** 2 - 2 * Emu * mu0) + 0.5 * np.sum(x ** 2 + Emu2 - 2 * Emu * x)   # (10.122)
        states.append((muN, kN, aN, bN))
    return states


def vb_unigauss_elbo(x, muN, kN, aN, bN, mu0, k0, a0, b0):
    """Exact ELBO of q(mu) q(lambda) = N(mu | muN, 1/kN) Ga(lambda | aN, bN) for the model (10.105)."""
    N = len(x)
    El, Ell = aN / bN, special.digamma(aN) - np.log(bN)
    Emu, Emu2 = muN, 1 / kN + muN ** 2
    EQ = k0 * (Emu2 - 2 * Emu * mu0 + mu0 ** 2) + np.sum(x ** 2 - 2 * Emu * x + Emu2)
    Elogjoint = (N / 2 * (Ell - np.log(2 * np.pi)) + 0.5 * (np.log(k0) + Ell - np.log(2 * np.pi)) - 0.5 * El * EQ
                 + a0 * np.log(b0) - special.gammaln(a0) + (a0 - 1) * Ell - b0 * El)
    Hmu = 0.5 * np.log(2 * np.pi * np.e / kN)
    Hlam = aN - np.log(bN) + special.gammaln(aN) + (1 - aN) * special.digamma(aN)
    return Elogjoint + Hmu + Hlam


def vb_unigauss_bound(x, kN, aN, bN, mu0, k0, a0, b0):
    """The closed form (10.124) with its constant written out (valid right after a q(lambda) update)."""
    N = len(x)
    const = -N / 2 * np.log(2 * np.pi) + 0.5 * np.log(k0) + a0 * np.log(b0) - special.gammaln(a0) + 0.5
    return const + 0.5 * np.log(1 / kN) + special.gammaln(aN) - aN * np.log(bN)


UNI_PRIOR = dict(mu0=0.0, k0=1.0, a0=1.0, b0=1.0)
UNI_INIT = (0.5, 4.0, 2.0, 1.0)


def fig_10_10(out=None):
    """Factored VB approximation to the Normal-Gamma posterior: initial guess, after updating q(mu),
    after updating q(lambda), at convergence."""
    x = unigauss_data()
    pr = UNI_PRIOR
    mN, kN, aN, bN = normal_gamma_post(x, pr["mu0"], pr["k0"], pr["a0"], pr["b0"])
    st = vb_unigauss(x, pr["mu0"], pr["k0"], pr["a0"], pr["b0"], UNI_INIT, n_iter=5)
    mus = np.linspace(-1.0, 1.0, 161)
    lams = np.linspace(0.01, 2.5, 161)
    M, L = np.meshgrid(mus, lams)
    P = np.exp(normal_gamma_logpdf(M, L, mN, kN, aN, bN))
    fig, axes = panel_grid(1, 4, size=(2.5, 2.4))
    for k, s in enumerate([st[0], st[1], st[2], st[-1]]):
        ax = axes[0, k]
        ax.contour(M, L, P, levels=5, colors=BLUE, linewidths=1.0)
        Q = stats.norm.pdf(M, s[0], 1 / np.sqrt(s[1])) * stats.gamma.pdf(L, s[2], scale=1 / s[3])
        ax.contour(M, L, Q, levels=5, colors=ORANGE, linewidths=1.0, linestyles="--")
        ax.set_xlabel(r"$\mu$")
        if k == 0:
            ax.set_ylabel(r"$\lambda$")
        panel_label(ax, "abcd"[k])
        if k == 0:
            ax.plot([], [], color=BLUE, label="exact")
            ax.plot([], [], color=ORANGE, ls="--", label="VB")
            ax.legend(loc="upper right", fontsize=7, frameon=False)
    fig.tight_layout()
    savefig(fig, CH, "fig10-10", out)
    return st


# =========================================================================== 10.3.6 VBEM for a GMM
def vb_count_dynamics(N0, n_iter=40, alpha0=0.0, N=None):
    """Figure 10.11b: VBEM updates of the counts ignoring the likelihood, r_nk = pi_tilde_k (10.153)."""
    Nk = np.array(N0, float)
    Ntot = Nk.sum() if N is None else N
    hist = [Nk.copy()]
    for t in range(n_iter):
        a = alpha0 + Nk
        pt = np.exp(special.digamma(np.maximum(a, 1e-300)) - special.digamma(a.sum()))
        Nk = Ntot * pt / pt.sum()
        hist.append(Nk.copy())
    return np.array(hist)


def fig_10_11(out=None):
    """(a) exp(digamma(x)) against x; (b) counts N_k under likelihood-free VBEM updates."""
    fig, axes = panel_grid(1, 2, size=(3.4, 2.9))
    ax = axes[0, 0]
    xs = np.linspace(1e-3, 2.0, 400)
    ax.plot(xs, np.exp(special.digamma(xs)), color=BLUE, label=r"$\exp(\psi(x))$")
    ax.plot(xs, xs, color=GREY, ls="--", label="$x$")
    ax.plot(xs, np.maximum(xs - 0.5, 0), color=RED, ls=":", label=r"$\max(x-1/2,\,0)$")
    ax.set_xlabel("$x$")
    ax.legend(frameon=False, fontsize=8)
    panel_label(ax, "a", "lower right")
    ax = axes[0, 1]
    H = vb_count_dynamics([0.9, 1.0, 1.3, 1.8], n_iter=30)
    for k in range(4):
        ax.plot(H[:, k], color=[RED, GREEN, BLUE, PURPLE][k], label="state %d" % (k + 1))
    ax.set_xlabel("iteration")
    ax.set_ylabel(r"$N_k$")
    ax.legend(frameon=False, fontsize=8)
    panel_label(ax, "b", "upper right")
    fig.tight_layout()
    savefig(fig, CH, "fig10-11", out)
    return H


def vbgmm(X, K, alpha0=1e-3, beta0=1.0, m0=None, W0=None, nu0=None, r0=None, n_iter=200, tol=0.0):
    """VBEM for a Bayesian GMM (Section 10.3.6; Bishop 2006, Section 10.2) with the full lower bound.

    Prior Dir(pi | alpha0) prod_k N(mu_k | m0, (beta0 Lambda_k)^{-1}) Wi(Lambda_k | W0, nu0) (kappa = beta0,
    L = W0 in the book's notation). r0 gives the initial responsibilities (N x K). Returns a dict with the
    posterior hyper-parameters after every iteration and the bound history."""
    N, D = X.shape
    m0 = np.zeros(D) if m0 is None else m0
    W0 = np.eye(D) if W0 is None else W0
    nu0 = float(D) if nu0 is None else nu0
    W0inv = np.linalg.inv(W0)
    r = r0.copy()
    hist, bounds = [], []

    def lnB(W, nu):
        return -0.5 * nu * np.linalg.slogdet(W)[1] - (0.5 * nu * D * np.log(2) + 0.25 * D * (D - 1) * np.log(np.pi)
                                                     + special.gammaln(0.5 * (nu + 1 - np.arange(1, D + 1))).sum())

    def lnC(a):
        return special.gammaln(a.sum()) - special.gammaln(a).sum()

    for it in range(n_iter):
        # variational M step (10.137)-(10.145)
        Nk = r.sum(0) + 1e-12
        xk = (r.T @ X) / Nk[:, None]
        Sk = np.stack([((r[:, k, None] * (X - xk[k])).T @ (X - xk[k])) / Nk[k] for k in range(K)])
        alpha = alpha0 + Nk
        beta = beta0 + Nk
        m = (beta0 * m0 + Nk[:, None] * xk) / beta[:, None]
        Winv = np.stack([W0inv + Nk[k] * Sk[k] + beta0 * Nk[k] / (beta0 + Nk[k]) * np.outer(xk[k] - m0, xk[k] - m0)
                         for k in range(K)])
        W = np.linalg.inv(Winv)
        nu = nu0 + Nk
        # expectations (10.147)-(10.150)
        Elnpi = special.digamma(alpha) - special.digamma(alpha.sum())
        ElnL = np.array([special.digamma(0.5 * (nu[k] + 1 - np.arange(1, D + 1))).sum() + D * np.log(2)
                         + np.linalg.slogdet(W[k])[1] for k in range(K)])
        Equad = np.stack([D / beta[k] + nu[k] * np.einsum("nd,de,ne->n", X - m[k], W[k], X - m[k]) for k in range(K)], 1)
        # lower bound (Bishop 2006, (10.70)-(10.77)) for the current q(Z) and the new q(theta)
        t1 = 0.5 * sum(Nk[k] * (ElnL[k] - D / beta[k] - nu[k] * np.trace(Sk[k] @ W[k])
                                - nu[k] * (xk[k] - m[k]) @ W[k] @ (xk[k] - m[k]) - D * np.log(2 * np.pi)) for k in range(K))
        t2 = (r * Elnpi).sum()
        t3 = lnC(np.full(K, alpha0)) + (alpha0 - 1) * Elnpi.sum()
        t4 = 0.5 * sum(D * np.log(beta0 / (2 * np.pi)) + ElnL[k] - D * beta0 / beta[k]
                       - beta0 * nu[k] * (m[k] - m0) @ W[k] @ (m[k] - m0) for k in range(K)) \
            + K * lnB(W0, nu0) + 0.5 * (nu0 - D - 1) * ElnL.sum() - 0.5 * sum(nu[k] * np.trace(W0inv @ W[k]) for k in range(K))
        t5 = (r * np.log(np.maximum(r, 1e-300))).sum()
        t6 = ((alpha - 1) * Elnpi).sum() + lnC(alpha)
        HW = np.array([-lnB(W[k], nu[k]) - 0.5 * (nu[k] - D - 1) * ElnL[k] + 0.5 * nu[k] * D for k in range(K)])
        t7 = sum(0.5 * ElnL[k] + 0.5 * D * np.log(beta[k] / (2 * np.pi)) - 0.5 * D - HW[k] for k in range(K))
        bounds.append(t1 + t2 + t3 + t4 - t5 - t6 - t7)
        hist.append(dict(alpha=alpha.copy(), beta=beta.copy(), m=m.copy(), W=W.copy(), nu=nu.copy()))
        # variational E step (10.146)-(10.151)
        lrho = Elnpi + 0.5 * ElnL - 0.5 * D * np.log(2 * np.pi) - 0.5 * Equad
        r = np.exp(lrho - logsumexp(lrho, axis=1, keepdims=True))
        if tol and it > 1 and abs(bounds[-1] - bounds[-2]) < tol:
            break
    return dict(hist=hist, bound=np.array(bounds), r=r)


def faithful_vbgmm(K=6, alpha0=1e-3, n_iter=100, seed=0):
    from sklearn.cluster import KMeans
    X = old_faithful()
    lab = KMeans(n_clusters=K, n_init=1, random_state=seed).fit(X).labels_
    r0 = np.eye(K)[lab]
    return X, vbgmm(X, K, alpha0=alpha0, beta0=1.0, r0=r0, n_iter=n_iter)


def _plot_vb_state(ax, X, h, title):
    ax.scatter(X[:, 0], X[:, 1], s=6, color=BLUE, alpha=0.6)
    w = h["alpha"] / h["alpha"].sum()
    for k in range(len(w)):
        S = np.linalg.inv(h["nu"][k] * h["W"][k])
        if w[k] > 1e-3:
            x, y = ellipse_xy(h["m"][k], S, 1.0)
            ax.fill(x, y, color=RED, alpha=min(1.0, 0.15 + 0.85 * w[k] / w.max()) * 0.6, lw=0)
            ax.plot(x, y, color=RED, lw=0.8)
            ax.text(h["m"][k][0], h["m"][k][1], str(k + 1), fontsize=8, ha="center", va="center")
        else:
            ax.plot(h["m"][k][0], h["m"][k][1], "o", color=RED, ms=4)
    ax.set_title(title, fontsize=9)
    ax.set_xlim(-2.2, 2.0)
    ax.set_ylim(-2.6, 2.4)


def fig_10_12(out=None):
    """VBEM for a 6-component GMM on Old Faithful: posterior mean parameters at the first and last iteration."""
    X, res = faithful_vbgmm()
    last = len(res["hist"]) - 1
    fig, axes = panel_grid(1, 2, size=(3.4, 3.2))
    _plot_vb_state(axes[0, 0], X, res["hist"][0], "iter 1")
    _plot_vb_state(axes[0, 1], X, res["hist"][last], "iter %d" % (last + 1))
    panel_label(axes[0, 0], "a", "lower right")
    panel_label(axes[0, 1], "b", "lower right")
    fig.tight_layout()
    savefig(fig, CH, "fig10-12", out)
    return res


def fig_10_13(out=None):
    """The Dirichlet posterior parameters alpha_k after the first and last VBEM iteration."""
    X, res = faithful_vbgmm()
    last = len(res["hist"]) - 1
    fig, axes = panel_grid(1, 2, size=(3.2, 2.6))
    for j, (it, lab) in enumerate([(0, "iter 1"), (last, "iter %d" % (last + 1))]):
        ax = axes[0, j]
        ax.bar(np.arange(1, 7), res["hist"][it]["alpha"], color=BLUE)
        ax.set_title(lab, fontsize=9)
        ax.set_xlabel("component $k$")
        if j == 0:
            ax.set_ylabel(r"$\hat\alpha_k$")
        panel_label(ax, "ab"[j], "upper left")
    fig.tight_layout()
    savefig(fig, CH, "fig10-13", out)


def fig_10_14(out=None):
    """The VBEM lower bound against iteration for the run of Figure 10.12."""
    X, res = faithful_vbgmm()
    fig, ax = plt.subplots(figsize=(4.6, 3.2))
    ax.plot(np.arange(1, len(res["bound"]) + 1), res["bound"], color=BLUE)
    ax.set_xlabel("iteration")
    ax.set_ylabel("lower bound on log marginal likelihood")
    ax.set_title("variational Bayes for a GMM on Old Faithful", fontsize=9)
    savefig(fig, CH, "fig10-14", out)


# =========================================================================== 10.5 tighter bounds
TOY = dict(x=2.0, sx=0.7)   # z ~ N(0,1), x | z ~ N(z^2, sx^2): a bimodal posterior at z = +-sqrt(x)


def toy_logjoint(z, x=None, sx=None):
    x = TOY["x"] if x is None else x
    sx = TOY["sx"] if sx is None else sx
    return -0.5 * z ** 2 - 0.5 * np.log(2 * np.pi) - 0.5 * ((x - z ** 2) / sx) ** 2 - np.log(np.sqrt(2 * np.pi) * sx)


TOY_GRID = np.linspace(-6, 6, 6001)


def toy_logZ(x=None, sx=None):
    lj = toy_logjoint(TOY_GRID, x, sx)
    return logsumexp(lj) + np.log(TOY_GRID[1] - TOY_GRID[0])


def toy_bounds_quadrature(m, s, x=None, sx=None):
    """ELBO and EUBO of q = N(m, s^2) by quadrature on a fine grid, with log p(x)."""
    z = TOY_GRID
    dz = z[1] - z[0]
    lj = toy_logjoint(z, x, sx)
    lZ = logsumexp(lj) + np.log(dz)
    lq = stats.norm.logpdf(z, m, s)
    q = np.exp(lq)
    p = np.exp(lj - lZ)
    elbo = np.sum(q * (lj - lq)) * dz
    eubo = lZ + np.sum(p * (lj - lZ - lq)) * dz
    return elbo, eubo, lZ


def iwae_bound(m, s, S, M, seed, x=None, sx=None):
    """Monte Carlo IWAE bound (10.167) with S importance samples, averaged over M independent draws.
    Uses the demo generator: for each of the M draws, S normals in order."""
    rng = KitRng(seed)
    vals = np.empty(M)
    for i in range(M):
        e = np.array([rng.norm() for _ in range(S)])
        z = m + s * e
        lw = toy_logjoint(z, x, sx) - stats.norm.logpdf(z, m, s)
        vals[i] = logsumexp(lw) - np.log(S)
    return vals.mean(), vals.std(ddof=1) / np.sqrt(M)


def toy_elbo_opt(x=None, sx=None, m0=1.0):
    f = lambda p: -toy_bounds_quadrature(p[0], np.exp(p[1]), x, sx)[0]
    r = optimize.minimize(f, [m0, np.log(0.5)], method="Nelder-Mead", options=dict(xatol=1e-10, fatol=1e-12, maxiter=4000))
    return r.x[0], np.exp(r.x[1])


def toy_moment_match(x=None, sx=None):
    z = TOY_GRID
    lj = toy_logjoint(z, x, sx)
    p = np.exp(lj - logsumexp(lj))
    m = (p * z).sum()
    return m, np.sqrt((p * (z - m) ** 2).sum())


def fig_x10_b(out=None):
    """ELBO <= IWAE_S <= log p(x) <= EUBO for the toy bimodal posterior, against S, for two choices of q."""
    lZ = toy_logZ()
    mE, sE = toy_elbo_opt()
    mF, sF = toy_moment_match()
    Ss = [1, 2, 5, 10, 20, 50, 100, 200, 500]
    fig, axes = panel_grid(1, 2, size=(3.6, 3.0))
    ax = axes[0, 0]
    z = TOY_GRID
    lj = toy_logjoint(z)
    ax.plot(z, np.exp(lj - lZ), color="k", label="posterior")
    ax.plot(z, stats.norm.pdf(z, mE, sE), color=RED, ls="--", label="ELBO optimum")
    ax.plot(z, stats.norm.pdf(z, mF, sF), color=BLUE, ls=":", label="moment match")
    ax.set_xlim(-3.5, 3.5)
    ax.set_xlabel("$z$")
    ax.legend(frameon=False, fontsize=7, loc="upper right")
    panel_label(ax, "a", "upper left")
    ax = axes[0, 1]
    res = {}
    for (m, s, c, lab) in [(mE, sE, RED, "ELBO-optimal q"), (mF, sF, BLUE, "moment-matched q")]:
        v = [iwae_bound(m, s, S, 400, 11)[0] for S in Ss]
        el, eu, _ = toy_bounds_quadrature(m, s)
        ax.semilogx(Ss, v, "o-", color=c, ms=3, label="IWAE, " + lab)
        res[lab] = dict(iwae=v, elbo=el, eubo=eu)
    ax.axhline(lZ, color="k", lw=1.2, label=r"$\log p(x)$")
    lo = min(min(r["iwae"]) for r in res.values())
    ax.set_ylim(lo - 0.15, lZ + 0.25)
    ax.text(0.97, 0.04, "EUBO: %.2f (ELBO-optimal q), %.2f (moment-matched q)" % (res["ELBO-optimal q"]["eubo"],
            res["moment-matched q"]["eubo"]), transform=ax.transAxes, ha="right", fontsize=6.5)
    ax.set_xlabel("samples S")
    ax.set_ylabel("nats")
    ax.legend(frameon=False, fontsize=7, loc="center right")
    panel_label(ax, "b", "upper left")
    fig.tight_layout()
    savefig(fig, CH, "figx10-b", out)
    return res, lZ


# =========================================================================== 10.7 expectation propagation
def ep_logistic_data(n=12, seed=5, theta=1.5):
    rng = KitRng(seed)
    x = np.array([2.0 * rng.norm() for _ in range(n)])
    y = np.array([1.0 if rng.u() < sigmoid(theta * xi) else -1.0 for xi in x])
    return x, y


EP_GRID = np.linspace(-8, 8, 3201)


def _log_sigmoid(a):
    return -np.logaddexp(0.0, -a)


def ep_exact_1d(x, y, v0):
    t = EP_GRID
    lp = stats.norm.logpdf(t, 0, np.sqrt(v0)) + _log_sigmoid(np.outer(y * x, t)).sum(0)
    dt = t[1] - t[0]
    lZ = logsumexp(lp) + np.log(dt)
    p = np.exp(lp - lZ)
    m = (p * t).sum() * dt
    return dict(p=p, lZ=lZ, mean=m, var=(p * (t - m) ** 2).sum() * dt)


def ep_logistic_1d(x, y, v0, n_sweeps=10, damping=1.0, alpha=1.0, adf=False):
    """EP (Section 10.7) for theta ~ N(0, v0), f_i(theta) = sigmoid(y_i x_i theta), with Gaussian sites in
    natural parameters (precision tau_i, precision-times-mean nu_i). Tilted moments by quadrature on a
    fine grid. damping is delta of (10.199); alpha < 1 gives power EP (Section 10.7.5); adf=True runs a
    single assumed-density-filtering pass (Section 10.7.3) instead. Returns the history of (m, v)."""
    n = len(x)
    t = EP_GRID
    dt = t[1] - t[0]
    tau, nu = np.zeros(n), np.zeros(n)
    Tq, Nq = 1.0 / v0, 0.0
    hist = [(Nq / Tq, 1 / Tq)]
    sweeps = 1 if adf else n_sweeps
    for s in range(sweeps):
        for i in range(n):
            Tc, Nc = Tq - alpha * tau[i], Nq - alpha * nu[i]        # cavity: divide out alpha of the site
            if Tc <= 0:
                continue
            lt = alpha * _log_sigmoid(y[i] * x[i] * t) - 0.5 * Tc * t ** 2 + Nc * t
            w = np.exp(lt - lt.max())
            w /= w.sum()
            m = (w * t).sum()
            v = (w * (t - m) ** 2).sum()
            Tp, Np = 1 / v, m / v                                    # projection = moment matching
            if adf:
                Tq, Nq = Tp, Np
                tau[i], nu[i] = Tp - Tc, Np - Nc
            else:
                tnew, nnew = (Tp - Tc) / alpha, (Np - Nc) / alpha     # (q_proj / q_cavity)^(1/alpha)
                tau[i] = (1 - damping) * tau[i] + damping * tnew     # (10.199) in natural parameters
                nu[i] = (1 - damping) * nu[i] + damping * nnew
                Tq, Nq = 1.0 / v0 + tau.sum(), nu.sum()
            hist.append((Nq / Tq, 1 / Tq))
    return dict(m=Nq / Tq, v=1 / Tq, tau=tau, nu=nu, hist=np.array(hist))


def vi_logistic_1d(x, y, v0):
    """Gaussian VI (reverse KL) for the same 1d posterior, by quadrature."""
    t = EP_GRID
    dt = t[1] - t[0]
    lj = stats.norm.logpdf(t, 0, np.sqrt(v0)) + _log_sigmoid(np.outer(y * x, t)).sum(0)

    def neg(p):
        q = stats.norm.pdf(t, p[0], np.exp(p[1]))
        return -(np.sum(q * lj) * dt + p[1] + 0.5 * np.log(2 * np.pi * np.e))
    ex = ep_exact_1d(x, y, v0)
    r = optimize.minimize(neg, [ex["mean"], 0.5 * np.log(ex["var"])], method="Nelder-Mead",
                          options=dict(xatol=1e-10, fatol=1e-13, maxiter=5000))
    return r.x[0], np.exp(2 * r.x[1]), -r.fun


def fig_10_15(out=None):
    """A logistic likelihood factor, a Gaussian cavity distribution and their (tilted) product."""
    t = np.linspace(-6, 6, 1201)
    cav_m, cav_s = 1.0, 1.4
    f = sigmoid(-2.5 * t)          # p(y_i | theta) for a point with y_i x_i = -2.5
    cav = stats.norm.pdf(t, cav_m, cav_s)
    til = f * cav
    til /= til.sum() * (t[1] - t[0])
    mt = (til * t).sum() * (t[1] - t[0])
    vt = (til * (t - mt) ** 2).sum() * (t[1] - t[0])
    fig, ax = plt.subplots(figsize=(4.8, 3.2))
    ax.plot(t, f * cav.max(), color=GREY, label=r"likelihood factor $p(y_i|\theta)$ (scaled)")
    ax.plot(t, cav, color=BLUE, label=r"cavity $q_{-i}(\theta)$")
    ax.plot(t, til, color=RED, label=r"tilted $p(y_i|\theta)q_{-i}(\theta)/Z_i$")
    ax.plot(t, stats.norm.pdf(t, mt, np.sqrt(vt)), color=RED, ls=":", label="its Gaussian projection")
    ax.set_xlabel(r"$\theta$")
    ax.legend(frameon=False, fontsize=7, loc="upper right")
    ax.set_ylim(0, 0.5)
    savefig(fig, CH, "fig10-15", out)
    return mt, vt


# =========================================================================== Supplement 10.1 more Gaussian VI
def diabetes_regression():
    """Stand-in for the Africa ruggedness data: y = log disease progression, x = (BMI z-score, sex
    indicator A, A * BMI)."""
    from sklearn.datasets import load_diabetes
    d = load_diabetes(scaled=False)
    bmi = d.data[:, 2]
    R = (bmi - bmi.mean()) / bmi.std()
    A = (d.data[:, 1] == 2).astype(float)
    return np.c_[R, A, A * R], np.log(d.target), R, A


def linreg_logpost_torch(Xt, yt):
    """log p(theta, D) + log|J| for theta = (alpha, beta1..3, tau), sigma = 10 sigmoid(tau) (Supp. (10.1)-(10.5))."""
    import torch

    def lp(u):
        a, b, tau = u[:, 0], u[:, 1:4], u[:, 4]
        sig = 10 * torch.sigmoid(tau)
        mu = a[:, None] + b @ Xt.T
        ll = (-0.5 * ((yt[None] - mu) / sig[:, None]) ** 2 - torch.log(sig)[:, None]).sum(1) - 0.5 * len(yt) * np.log(2 * np.pi)
        lpri = -0.5 * (a / 10.0) ** 2 - 0.5 * (b ** 2).sum(1) - np.log(10.0)      # sigma ~ U(0,10): density 1/10
        lj = np.log(10.0) + torch.nn.functional.logsigmoid(tau) + torch.nn.functional.logsigmoid(-tau)
        return ll + lpri + lj
    return lp


def hmc(logp_and_grad, x0, n_samples, eps, n_leap, seed=0, burn=500):
    """Plain Hamiltonian Monte Carlo with an identity mass matrix (leapfrog steps; Section 12.5)."""
    rng = np.random.default_rng(seed)
    x = np.array(x0, float)
    lp, g = logp_and_grad(x)
    out, acc = [], 0
    for it in range(n_samples + burn):
        p = rng.standard_normal(len(x))
        H0 = -lp + 0.5 * p @ p
        xn, gn, pn = x.copy(), g.copy(), p + 0.5 * eps * g
        for l in range(n_leap):
            xn = xn + eps * pn
            lpn, gn = logp_and_grad(xn)
            if l < n_leap - 1:
                pn = pn + eps * gn
        pn = pn + 0.5 * eps * gn
        H1 = -lpn + 0.5 * pn @ pn
        if np.log(rng.uniform()) < H0 - H1:
            x, lp, g = xn, lpn, gn
            if it >= burn:
                acc += 1
        if it >= burn:
            out.append(x.copy())
    return np.array(out), acc / n_samples


def supp_linreg_fits():
    path = os.path.join(CACHE_DIR, "supp_linreg.npz")
    if os.path.exists(path):
        z = np.load(path)
        return {k: z[k] for k in z.files}
    torch = common.torch_setup(0)
    X, y, R, A = diabetes_regression()
    Xt, yt = torch.tensor(X), torch.tensor(y)
    lp = linreg_logpost_torch(Xt, yt)

    def lpg(u):
        ut = torch.tensor(u[None], requires_grad=True)
        v = lp(ut)[0]
        v.backward()
        return v.item(), ut.grad.numpy()[0].copy()
    # start HMC at the posterior mode
    r = optimize.minimize(lambda u: -lpg(u)[0], np.r_[y.mean(), 0, 0, 0, -3.0], jac=lambda u: -lpg(u)[1], method="BFGS")
    H = np.linalg.inv(r.hess_inv) if False else None
    samp, acc = hmc(lpg, r.x, 4000, 0.02, 20, seed=0, burn=500)
    rng = np.random.default_rng(0)
    eps = rng.standard_normal((256, 5))
    full = gvi_fit(lp, 5, "full", steps=500, fixed_eps=eps, init_mu=r.x, init_logs=-3.0, seed=0)
    diag = gvi_fit(lp, 5, "diag", steps=500, fixed_eps=eps, init_mu=r.x, init_logs=-3.0, seed=0)
    res = dict(hmc=samp, acc=acc, mode=r.x, full_mu=full["mu"], full_S=full["Sigma"], full_elbo=full["elbo"],
               diag_mu=diag["mu"], diag_S=diag["Sigma"], diag_elbo=diag["elbo"])
    np.savez(path, **res)
    return res


SUPP_NAMES = ["bias", "weight 0 (BMI)", "weight 1 (sex)", "weight 2 (sex x BMI)"]


def fig_S10_1(out=None):
    """Posterior predictive of the linear model by group (stand-in data), from HMC."""
    X, y, R, A = diabetes_regression()
    res = supp_linreg_fits()
    S = res["hmc"][::4]
    sig = 10 * sigmoid(S[:, 4])
    rng = np.random.default_rng(1)
    fig, axes = panel_grid(1, 2, size=(3.6, 3.0))
    for j, (grp, title) in enumerate([(0.0, "sex 1"), (1.0, "sex 2")]):
        ax = axes[0, j]
        r = np.linspace(R.min(), R.max(), 60)
        mu = S[:, 0][:, None] + S[:, 1][:, None] * r + S[:, 2][:, None] * grp + S[:, 3][:, None] * grp * r
        yy = mu + sig[:, None] * rng.standard_normal(mu.shape)
        ax.fill_between(r, *np.percentile(yy, [2.5, 97.5], 0), color=ORANGE, alpha=0.2, lw=0)
        ax.fill_between(r, *np.percentile(mu, [2.5, 97.5], 0), color=ORANGE, alpha=0.6, lw=0)
        ax.plot(r, mu.mean(0), color="k", lw=1)
        sel = A == grp
        ax.scatter(R[sel], y[sel], s=5, color=BLUE)
        ax.set_title(title, fontsize=9)
        ax.set_xlabel("BMI (standardised)")
        if j == 0:
            ax.set_ylabel("log disease progression")
    fig.tight_layout()
    savefig(fig, CH, "figS10-1", out)


def fig_S10_2(out=None):
    """Posterior marginals of the regression coefficients: HMC against diagonal and full Gaussian VI."""
    res = supp_linreg_fits()
    S = res["hmc"]
    fig, axes = panel_grid(2, 4, size=(2.4, 2.0))
    for row, (key, lab) in enumerate([("diag", "diagonal"), ("full", "full")]):
        m, C = res[key + "_mu"], res[key + "_S"]
        for j in range(4):
            ax = axes[row, j]
            ax.hist(S[:, j], bins=40, density=True, color=BLUE, alpha=0.5, label="HMC")
            g = np.linspace(S[:, j].min(), S[:, j].max(), 200)
            ax.plot(g, stats.norm.pdf(g, m[j], np.sqrt(C[j, j])), color=ORANGE, lw=1.6, label=lab)
            ax.set_title(SUPP_NAMES[j], fontsize=8)
            ax.tick_params(labelsize=7)
            if j == 0:
                ax.legend(frameon=False, fontsize=7)
    fig.tight_layout()
    savefig(fig, CH, "figS10-2", out)


def fig_S10_3(out=None):
    """Joint posterior of two pairs of coefficients: HMC (contours of a KDE) against Gaussian VI."""
    res = supp_linreg_fits()
    S = res["hmc"]
    pairs = [(2, 1), (1, 3)]
    fig, axes = panel_grid(2, 2, size=(2.9, 2.6))
    for row, key in enumerate(["diag", "full"]):
        m, C = res[key + "_mu"], res[key + "_S"]
        for j, (a, b) in enumerate(pairs):
            ax = axes[row, j]
            kde = stats.gaussian_kde(S[:, [a, b]].T)
            ga = np.linspace(S[:, a].min(), S[:, a].max(), 70)
            gb = np.linspace(S[:, b].min(), S[:, b].max(), 70)
            GA, GB = np.meshgrid(ga, gb)
            ax.contour(GA, GB, kde(np.c_[GA.ravel(), GB.ravel()].T).reshape(GA.shape), levels=6, colors=BLUE, linewidths=0.8)
            sub = C[np.ix_([a, b], [a, b])]
            for nsd in (1, 2):
                x, yv = ellipse_xy(m[[a, b]], sub, nsd)
                ax.plot(x, yv, color=ORANGE, lw=1.4)
            ax.set_xlabel(SUPP_NAMES[a], fontsize=8)
            ax.set_ylabel(SUPP_NAMES[b], fontsize=8)
            ax.tick_params(labelsize=7)
            ax.set_title("HMC (blue) and %s Gaussian (orange)" % key, fontsize=8)
    fig.tight_layout()
    savefig(fig, CH, "figS10-3", out)


def biclusters(n=30, seed=0):
    rng = np.random.default_rng(seed)
    X0 = rng.normal([-1.0, -1.0], 0.7, (n, 2))
    X1 = rng.normal([1.2, 1.4], 0.7, (n, 2))
    X = np.r_[X0, X1]
    y = np.r_[np.zeros(n), np.ones(n)]
    return X, y


def logreg_logjoint_torch(X, y, delta=10.0):
    import torch
    Xa = torch.tensor(np.c_[np.ones(len(X)), X])
    yt = torch.tensor(y)

    def lp(w):
        a = w @ Xa.T
        return (yt * torch.nn.functional.logsigmoid(a) + (1 - yt) * torch.nn.functional.logsigmoid(-a)).sum(1) \
            - 0.5 * (w ** 2).sum(1) / delta
    return lp


def rw_metropolis(logp, x0, n, step, seed=0, burn=2000, thin=5):
    rng = np.random.default_rng(seed)
    x = np.array(x0, float)
    lp = logp(x)
    out = []
    for it in range(burn + n * thin):
        xn = x + step * rng.standard_normal(len(x))
        lpn = logp(xn)
        if np.log(rng.uniform()) < lpn - lp:
            x, lp = xn, lpn
        if it >= burn and (it - burn) % thin == 0:
            out.append(x.copy())
    return np.array(out)


def supp_logreg_fits():
    path = os.path.join(CACHE_DIR, "supp_logreg.npz")
    if os.path.exists(path):
        z = np.load(path)
        return {k: z[k] for k in z.files}
    import torch
    X, y = biclusters()
    lp = logreg_logjoint_torch(X, y)
    lpn = lambda w: lp(torch.tensor(w[None]))[0].item()
    mc = rw_metropolis(lpn, np.zeros(3), 6000, 0.6, seed=0)
    full = gvi_fit(lp, 3, "full", steps=4000, lr=0.02, S=16, seed=0)
    low = gvi_fit(lp, 3, "lowrank", rank=1, steps=4000, lr=0.02, S=16, seed=0)
    res = dict(mcmc=mc, full_mu=full["mu"], full_S=full["Sigma"], low_mu=low["mu"], low_S=low["Sigma"])
    np.savez(path, **res)
    return res


def fig_S10_4(out=None):
    """Posterior predictive of 2d Bayesian logistic regression: MCMC, full-covariance VI, rank-one VI."""
    X, y = biclusters()
    res = supp_logreg_fits()
    rng = np.random.default_rng(3)
    g = np.linspace(-3.5, 3.5, 90)
    G1, G2 = np.meshgrid(g, g)
    Ga = np.c_[np.ones(G1.size), G1.ravel(), G2.ravel()]
    W = {"MCMC": res["mcmc"],
         "full-covariance Gaussian VI": rng.multivariate_normal(res["full_mu"], res["full_S"], 4000),
         "rank-one Gaussian VI": rng.multivariate_normal(res["low_mu"], res["low_S"], 4000)}
    fig, axes = panel_grid(1, 3, size=(2.9, 2.8))
    for j, (k, Ws) in enumerate(W.items()):
        ax = axes[0, j]
        P = sigmoid(Ga @ Ws.T).mean(1).reshape(G1.shape)
        ax.contourf(G1, G2, P, levels=np.linspace(0, 1, 11), cmap="RdBu_r", alpha=0.85)
        ax.scatter(X[y == 0, 0], X[y == 0, 1], s=10, c="k")
        ax.scatter(X[y == 1, 0], X[y == 1, 1], s=10, c="w", edgecolors="k", linewidths=0.5)
        ax.set_title(k, fontsize=8.5)
        ax.set_xticks([])
        ax.set_yticks([])
        panel_label(ax, "abc"[j])
    fig.tight_layout()
    savefig(fig, CH, "figS10-4", out)


# =========================================================================== Supplement 10.2 Bayesian gradient descent
def bgd_update(mu, sig, grad_fn, K, rng, eta=1.0):
    """One step of Bayesian gradient descent (Supplement Algorithm 10.1); grad_fn(theta) is the gradient
    of the negative log likelihood of the new batch."""
    eps = rng.standard_normal((K, len(mu)))
    g = np.array([grad_fn(mu + sig * e) for e in eps])
    E1, E2 = g.mean(0), (g * eps).mean(0)
    mu_new = mu - eta * sig ** 2 * E1
    sig_new = sig * np.sqrt(1 + (0.5 * sig * E2) ** 2) - 0.5 * sig ** 2 * E2
    return mu_new, sig_new


# =========================================================================== Supplement 10.3.1 CVI
def gh_expect(fn, m, v, n=60):
    """E_{N(m, v)}[fn(z)] by Gauss-Hermite quadrature (vectorised over m, v)."""
    t, w = np.polynomial.hermite_e.hermegauss(n)
    z = m[..., None] + np.sqrt(v)[..., None] * t
    return (fn(z) * w).sum(-1) / np.sqrt(2 * np.pi)


def cvi_logistic(X, y, delta, n_iter=200, eta=0.5):
    """Conjugate-computation VI for Bayesian logistic regression (Supplement 10.3.1.2): Gaussianise each
    likelihood term with local natural parameters lambda_n = (l1, l2) and solve a Bayesian linear
    regression in the inner loop. y in {0, 1}; prior N(0, delta I)."""
    N, D = X.shape
    l1, l2 = np.zeros(N), np.zeros(N)
    ll = lambda z, yy: yy * _log_sigmoid(z) + (1 - yy) * _log_sigmoid(-z)
    for it in range(n_iter):
        Prec = np.eye(D) / delta + X.T @ (X * (-2 * l2)[:, None])
        S = np.linalg.inv(Prec)
        mw = S @ (X.T @ l1)
        m = X @ mw
        v = np.einsum("nd,de,ne->n", X, S, X)
        # gradients of E[log p(y|z)] wrt the mean parameters (m, m^2 + v): Bonnet and Price
        Eg = gh_expect(lambda z: (y[:, None] - sigmoid(z)), m, v)          # E[f'(z)]
        Eh = gh_expect(lambda z: -sigmoid(z) * (1 - sigmoid(z)), m, v)     # E[f''(z)]
        g2 = 0.5 * Eh
        g1 = Eg - 2 * g2 * m
        l1 = (1 - eta) * l1 + eta * g1                                     # (10.48)
        l2 = (1 - eta) * l2 + eta * g2
    return mw, S


def gvi_logistic_quadrature(X, y, delta):
    """Full-covariance Gaussian VI for the same model by L-BFGS on the exact (quadrature) ELBO."""
    N, D = X.shape
    il = np.tril_indices(D)

    def unpack(p):
        m = p[:D]
        L = np.zeros((D, D))
        L[il] = p[D:]
        L[np.diag_indices(D)] = np.exp(L[np.diag_indices(D)])
        return m, L

    def negelbo(p):
        m, L = unpack(p)
        S = L @ L.T
        mz, vz = X @ m, np.einsum("nd,de,ne->n", X, S, X)
        e = gh_expect(lambda z: y[:, None] * _log_sigmoid(z) + (1 - y[:, None]) * _log_sigmoid(-z), mz, vz).sum()
        e += -0.5 * (m @ m + np.trace(S)) / delta - 0.5 * D * np.log(2 * np.pi * delta)
        ent = np.log(np.diag(L)).sum() + 0.5 * D * (1 + np.log(2 * np.pi))
        return -(e + ent)
    p0 = np.zeros(D + len(il[0]))
    r = optimize.minimize(negelbo, p0, method="L-BFGS-B", options=dict(maxiter=5000, ftol=1e-15, gtol=1e-10))
    m, L = unpack(r.x)
    return m, L @ L.T, -r.fun


# =========================================================================== Supplement 10.4 VI for graphical models
def grid_edges(n):
    idx = lambda i, j: i * n + j
    E = []
    for i in range(n):
        for j in range(n):
            if i + 1 < n: E.append((idx(i, j), idx(i + 1, j)))
            if j + 1 < n: E.append((idx(i, j), idx(i, j + 1)))
    return E


def ising_exact_logZ(V, E, J, h):
    """log Z of p(x) prop. to exp(sum_edges J x_s x_t + sum_s h_s x_s), x in {-1,+1}^V, by enumeration;
    also returns the exact node marginals P(x_s = +1)."""
    E = np.array(E)
    X = np.array(list(itertools.product([-1, 1], repeat=V)), float)
    lw = J * (X[:, E[:, 0]] * X[:, E[:, 1]]).sum(1) + X @ h
    lZ = logsumexp(lw)
    w = np.exp(lw - lZ)
    return lZ, (w[:, None] * (X > 0)).sum(0)


def spanning_tree_edge_probs(V, E):
    """Edge appearance probabilities of the uniform distribution over the spanning trees of a graph:
    rho_e = effective resistance between the endpoints of e (Kirchhoff)."""
    Lg = np.zeros((V, V))
    for s, t in E:
        Lg[s, s] += 1; Lg[t, t] += 1; Lg[s, t] -= 1; Lg[t, s] -= 1
    Lp = np.linalg.pinv(Lg)
    return np.array([Lp[s, s] + Lp[t, t] - 2 * Lp[s, t] for s, t in E])


def pairwise_bp(V, E, J, h, rho=None, n_iter=2000, damp=0.5, tol=1e-12):
    """Loopy BP (rho = None or all ones) or tree-reweighted BP (Supplement (10.110)-(10.113)) on an Ising
    model with edges E, then the Bethe / TRW objective theta^T tau + H(tau). Returns (value, node marginals)."""
    nE = len(E)
    rho = np.ones(nE) if rho is None else rho
    xs = np.array([-1.0, 1.0])
    th_s = np.outer(h, xs)                           # (V, 2)
    th_st = J * np.outer(xs, xs)                     # (2, 2), same on every edge
    nbr = {v: [] for v in range(V)}
    for e, (s, t) in enumerate(E):
        nbr[s].append((t, e)); nbr[t].append((s, e))
    # messages m[(t->s)] as length-2 vectors, log domain
    msg = {}
    for e, (s, t) in enumerate(E):
        msg[(t, s)] = np.zeros(2); msg[(s, t)] = np.zeros(2)
    for it in range(n_iter):
        delta = 0.0
        new = {}
        for (t, s) in msg:
            e = [ee for (u, ee) in nbr[t] if u == s][0]
            pre = th_s[t] + sum(rho[ee] * msg[(u, t)] for (u, ee) in nbr[t] if u != s) - (1 - rho[e]) * msg[(s, t)]
            # sum over x_t of exp(theta_st(x_s, x_t)/rho + pre(x_t))
            mm = logsumexp(th_st / rho[e] + pre[None, :], axis=1)
            mm -= mm.max()
            new[(t, s)] = (1 - damp) * msg[(t, s)] + damp * mm
            delta = max(delta, np.abs(new[(t, s)] - msg[(t, s)]).max())
        msg = new
        if delta < tol:
            break
    # pseudo-marginals (10.111)-(10.112)
    tau_s = np.zeros((V, 2))
    for s in range(V):
        a = th_s[s] + sum(rho[e] * msg[(t, s)] for (t, e) in nbr[s])
        tau_s[s] = np.exp(a - logsumexp(a))
    val = 0.0
    H = -(tau_s * np.log(tau_s)).sum()
    val += (tau_s * th_s).sum()
    for e, (s, t) in enumerate(E):
        a_s = th_s[s] + sum(rho[ee] * msg[(u, s)] for (u, ee) in nbr[s] if u != t) - (1 - rho[e]) * msg[(t, s)]
        a_t = th_s[t] + sum(rho[ee] * msg[(u, t)] for (u, ee) in nbr[t] if u != s) - (1 - rho[e]) * msg[(s, t)]
        a = th_st / rho[e] + a_s[:, None] + a_t[None, :]
        tst = np.exp(a - logsumexp(a))
        val += (tst * th_st).sum()
        I = (tst * (np.log(tst) - np.log(np.outer(tau_s[s], tau_s[t])))).sum()
        H -= rho[e] * I
    return val + H, tau_s[:, 1]


def ising_meanfield_logZ(V, E, J, h, n_iter=3000, damp=0.5, init=None):
    """Naive mean field lower bound on log Z for the same Ising model (Supplement 10.4.2)."""
    A = np.zeros((V, V))
    for s, t in E:
        A[s, t] = A[t, s] = J
    mu = np.full(V, 0.1) if init is None else init.copy()
    for it in range(n_iter):
        mu = (1 - damp) * mu + damp * np.tanh(A @ mu + h)
    p = np.clip((1 + mu) / 2, 1e-300, 1)
    q = np.clip((1 - mu) / 2, 1e-300, 1)
    val = 0.5 * mu @ A @ mu + h @ mu - (p * np.log(p) + q * np.log(q)).sum()
    return val, p


def ising_logz_methods(n=3, J=0.5, h=None):
    h = np.full(n * n, 0.1) if h is None else h
    V, E = n * n, grid_edges(n)
    lZ, marg = ising_exact_logZ(V, E, J, h)
    mf, mfm = ising_meanfield_logZ(V, E, J, h)
    bethe, bm = pairwise_bp(V, E, J, h)
    trw, tm = pairwise_bp(V, E, J, h, rho=spanning_tree_edge_probs(V, E))
    return dict(exact=lZ, mf=mf, bethe=bethe, trw=trw, marg=marg, mf_marg=mfm, bethe_marg=bm, trw_marg=tm)


def fig_x10_c(out=None):
    """log Z of a 3x3 Ising grid against the coupling J: exact, mean field, Bethe (LBP), tree-reweighted."""
    rng = np.random.default_rng(4)
    h = rng.uniform(-0.3, 0.3, 9)
    Js = np.linspace(-1.0, 1.0, 21)
    R = [ising_logz_methods(3, J, h) for J in Js]
    fig, axes = panel_grid(1, 2, size=(3.5, 3.0))
    ax = axes[0, 0]
    for key, c, ls, lab in [("exact", "k", "-", "exact"), ("trw", RED, "--", "tree-reweighted (upper)"),
                            ("bethe", BLUE, "-.", "Bethe (loopy BP)"), ("mf", GREEN, ":", "mean field (lower)")]:
        ax.plot(Js, [r[key] for r in R], color=c, ls=ls, label=lab)
    ax.set_xlabel("coupling $J$")
    ax.set_ylabel(r"$\log Z$ and its approximations")
    ax.legend(frameon=False, fontsize=7)
    panel_label(ax, "a", "lower right")
    ax = axes[0, 1]
    for key, c, ls in [("trw", RED, "--"), ("bethe", BLUE, "-."), ("mf", GREEN, ":")]:
        ax.plot(Js, [r[key] - r["exact"] for r in R], color=c, ls=ls)
    ax.axhline(0, color="k", lw=0.8)
    ax.set_xlabel("coupling $J$")
    ax.set_ylabel(r"approximation $-\log Z$")
    panel_label(ax, "b", "lower left")
    fig.tight_layout()
    savefig(fig, CH, "figx10-c", out)
    return Js, R


# =========================================================================== JSON for the demonstrations
def export_json():
    os.makedirs(DATA_OUT, exist_ok=True)
    # Ising demo: the clean image (bits) and reference numbers
    img = letter_a(ISING_N)
    x = ising_noisy(img, 2.0, ISING_SEED)
    ref = {}
    for key, (W, sig, lam, T, par) in {"book": (1.0, 2.0, 0.5, 15, True), "nodamp": (1.0, 2.0, 1.0, 15, True),
                                       "seq": (1.0, 2.0, 1.0, 15, False), "weak": (0.2, 2.0, 0.5, 15, True),
                                       "lownoise": (1.0, 1.0, 0.5, 15, True)}.items():
        xx = ising_noisy(img, sig, ISING_SEED)
        mus, el = ising_meanfield(xx, W, sig, lam, T, parallel=par)
        ref[key] = dict(err=float(np.mean(np.sign(mus[-1]) != img)), elbo=float(el[-1]), mu00=float(mus[-1][0, 0]),
                        mumid=float(mus[-1][ISING_N // 2, ISING_N // 2]), meanabs=float(np.abs(mus[-1]).mean()))
    d = dict(n=ISING_N, seed=ISING_SEED, bits="".join("1" if v > 0 else "0" for v in img.ravel()), ref=ref)
    with open(os.path.join(DATA_OUT, "ch10-ising.json"), "w") as f:
        json.dump(d, f, separators=(",", ":"))
    # bounds demo: reference numbers
    lZ = toy_logZ()
    mE, sE = toy_elbo_opt()
    mF, sF = toy_moment_match()
    b = dict(x=TOY["x"], sx=TOY["sx"], logZ=lZ, elbo_opt=[mE, sE], mm=[mF, sF], ref={})
    for (m, s, S, x_, sx_) in [(mE, sE, 10, 2.0, 0.7), (mF, sF, 10, 2.0, 0.7), (0.0, 1.0, 50, 2.0, 0.7),
                               (1.0, 0.5, 1, 1.0, 0.5), (1.2, 0.3, 100, 2.0, 0.7)]:
        el, eu, lz = toy_bounds_quadrature(m, s, x_, sx_)
        iw, se = iwae_bound(m, s, S, 500, 7, x_, sx_)
        b["ref"]["%.4f_%.4f_%d_%g_%g" % (m, s, S, x_, sx_)] = dict(m=m, s=s, S=S, x=x_, sx=sx_, elbo=el, eubo=eu,
                                                                    logZ=lz, iwae=iw, se=se)
    with open(os.path.join(DATA_OUT, "ch10-bounds.json"), "w") as f:
        json.dump(b, f, separators=(",", ":"))
    # EP demo
    xs, ys = ep_logistic_data()
    e = dict(x=xs.tolist(), y=ys.tolist(), v0=10.0, ref={})
    ex = ep_exact_1d(xs, ys, 10.0)
    e["ref"]["exact"] = dict(mean=ex["mean"], var=ex["var"], logZ=ex["lZ"])
    for key, kw in {"ep": dict(n_sweeps=10), "adf": dict(adf=True), "damped": dict(n_sweeps=3, damping=0.3),
                    "power05": dict(n_sweeps=10, alpha=0.5)}.items():
        r = ep_logistic_1d(xs, ys, 10.0, **kw)
        e["ref"][key] = dict(m=r["m"], v=r["v"])
    mv, vv, el = vi_logistic_1d(xs, ys, 10.0)
    e["ref"]["vi"] = dict(m=mv, v=vv, elbo=el)
    with open(os.path.join(DATA_OUT, "ch10-ep.json"), "w") as f:
        json.dump(e, f, separators=(",", ":"))
    print("wrote ch10-*.json")


FIGURES = {
    "10.2": fig_10_2, "10.6": fig_10_6, "10.7": fig_10_7, "10.9": fig_10_9, "10.10": fig_10_10, "10.11": fig_10_11,
    "10.12": fig_10_12, "10.13": fig_10_13, "10.14": fig_10_14, "10.15": fig_10_15,
    "S10.1": fig_S10_1, "S10.2": fig_S10_2, "S10.3": fig_S10_3, "S10.4": fig_S10_4,
    "x10.a": fig_x10_a, "x10.b": fig_x10_b, "x10.c": fig_x10_c,
}


if __name__ == "__main__":
    if "--json" in sys.argv:
        export_json()
    else:
        common.run(FIGURES, CH)
        if "--fig" not in sys.argv and "--list" not in sys.argv:
            export_json()
