"""Chapter 5 (Information theory) of the course "Probabilistic Machine Learning: Advanced Topics",
following Murphy (2023), Chapter 5 and Supplement Chapter 5.

Reproduces the computed figures of the chapter:
  5.1   forward vs reverse KL for a bimodal target and a Gaussian q
  5.2   forward vs reverse KL for a correlated 2-D Gaussian and a diagonal q
  5.4   entropy of a Bernoulli variable
  5.5   differential entropy of a height-like bimodal density in three units (stand-in data)
  5.8   a 4-class bag-of-words matrix (stand-in for the book's newsgroup subset)
  5.9   relevance network of pairwise mutual information between words
  5.10  rate-distortion plane (closed-form Gaussian example)
  5.11  posterior over codewords of the 3-bit parity code
  5.13  2-D embeddings of MNIST digits: deterministic bottleneck vs variational information bottleneck
and four original figures that illustrate results proved in the notes:
  5.S1  the asymptotic equipartition property
  5.S2  InfoNCE saturates at log K
  5.S3  the information-bottleneck curve for word-class counts
  5.S4  Solomonoff's total-error bound

Not reproduced (hand-drawn diagrams, nothing computed): Figure 5.3 (Bregman divergence sketch),
Figures 5.6 and 5.7 (information diagrams), Figures 5.12 and 5.14 (information diagrams for the
bottlenecks).

Stand-ins for data that the book takes from outside sources: Figure 5.5 uses a two-component Gaussian
mixture with typical adult male/female height parameters (the book uses a published height data set);
Figures 5.8, 5.9 and S3 use the public 20-newsgroups corpus downloaded by scikit-learn, grouped into the
four families comp, rec, sci, talk, with the 100 words most informative about the family (the book uses a
different, preprocessed 16242 x 100 binary matrix).

Run:  python ch05_information_theory.py [--fig 5.1 5.2 ...]
"""
import os
import json
import math
import itertools
from fractions import Fraction

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

import common
from common import RED, BLUE, GREEN, ORANGE, PURPLE, GREY, MAGENTA, CYAN, savefig, run, plt, ellipse_xy

CH = 5
HERE = os.path.dirname(os.path.abspath(__file__))
CACHE_DIR = os.path.join(HERE, "cache")
DATA_JSON = os.path.normpath(os.path.join(HERE, "..", "data"))
LN2 = math.log(2.0)


# ============================================================================ discrete information measures
def entropy(p, base=2.0):
    """Shannon entropy of a probability vector (any shape), 0 log 0 = 0."""
    p = np.asarray(p, float).ravel()
    p = p[p > 0]
    return float(-(p * np.log(p)).sum() / math.log(base))


def cross_entropy(p, q, base=2.0):
    p = np.asarray(p, float).ravel()
    q = np.asarray(q, float).ravel()
    m = p > 0
    if np.any(q[m] <= 0):
        return float("inf")
    return float(-(p[m] * np.log(q[m])).sum() / math.log(base))


def kl(p, q, base=2.0):
    """D_KL(p || q) for two probability vectors (arrays of any shape)."""
    p = np.asarray(p, float).ravel()
    q = np.asarray(q, float).ravel()
    m = p > 0
    if np.any(q[m] <= 0):
        return float("inf")
    return float((p[m] * np.log(p[m] / q[m])).sum() / math.log(base))


def mutual_information(pxy, base=2.0):
    """I(X;Y) from a joint table."""
    pxy = np.asarray(pxy, float)
    px = pxy.sum(1, keepdims=True)
    py = pxy.sum(0, keepdims=True)
    return kl(pxy, px * py, base)


def cond_entropy(pxy, base=2.0):
    """H(Y|X) from the joint table pxy[x, y]."""
    return entropy(pxy, base) - entropy(pxy.sum(1), base)


def cond_mutual_information(pxyz, base=2.0):
    """I(X;Y|Z) from a 3-D joint table pxyz[x, y, z]."""
    pz = pxyz.sum((0, 1))
    return sum(pz[z] * mutual_information(pxyz[:, :, z] / pz[z], base) for z in range(pxyz.shape[2]) if pz[z] > 0)


def total_correlation(pjoint, base=2.0):
    """Multi-information D(p || prod of marginals) for an n-D table."""
    pjoint = np.asarray(pjoint, float)
    h = 0.0
    for ax in range(pjoint.ndim):
        other = tuple(a for a in range(pjoint.ndim) if a != ax)
        h += entropy(pjoint.sum(other), base)
    return h - entropy(pjoint, base)


def coinformation3(pxyz, base=2.0):
    """I(X;Y;Z) = I(X;Y) - I(X;Y|Z) (Murphy 5.124)."""
    return mutual_information(pxyz.sum(2), base) - cond_mutual_information(pxyz, base)


def binary_entropy(t):
    t = np.asarray(t, float)
    out = np.zeros_like(t)
    m = (t > 0) & (t < 1)
    out[m] = -(t[m] * np.log2(t[m]) + (1 - t[m]) * np.log2(1 - t[m]))
    return out


def kl_bernoulli(a, b, base=math.e):
    return kl([a, 1 - a], [b, 1 - b], base)


# ============================================================================ Gaussians
def kl_gauss(m1, S1, m2, S2):
    """D_KL(N(m1,S1) || N(m2,S2)) in nats, Murphy (5.77)."""
    m1, m2 = np.atleast_1d(m1).astype(float), np.atleast_1d(m2).astype(float)
    S1, S2 = np.atleast_2d(S1).astype(float), np.atleast_2d(S2).astype(float)
    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 entropy_gauss(S):
    S = np.atleast_2d(S)
    return 0.5 * np.linalg.slogdet(2 * math.pi * math.e * S)[1]


def mi_gauss(rho):
    """I(X;Y) in nats for a standard bivariate Gaussian with correlation rho."""
    return -0.5 * math.log(1 - rho ** 2)


# ============================================================================ forward / reverse KL (Section 5.1.4)
BIMODAL = dict(w=0.5, m1=1.0, s1=1.0, m2=10.0, s2=1.5)


def bimodal_pdf(x, w=0.5, m1=1.0, s1=1.0, m2=10.0, s2=1.5):
    return w * stats.norm.pdf(x, m1, s1) + (1 - w) * stats.norm.pdf(x, m2, s2)


def _grid(par, n=6001, k=7.0):
    lo = min(par["m1"] - k * par["s1"], par["m2"] - k * par["s2"])
    hi = max(par["m1"] + k * par["s1"], par["m2"] + k * par["s2"])
    return np.linspace(lo, hi, n)


def mixture_moments(par):
    w, m1, s1, m2, s2 = (par[k] for k in ("w", "m1", "s1", "m2", "s2"))
    m = w * m1 + (1 - w) * m2
    v = w * (s1 ** 2 + m1 ** 2) + (1 - w) * (s2 ** 2 + m2 ** 2) - m ** 2
    return m, v


def kl_grid(f, g, x):
    """Trapezoid estimate of int f log(f/g) dx for densities on a grid (f log f/g = 0 where f = 0)."""
    with np.errstate(divide="ignore", invalid="ignore"):
        integrand = np.where(f > 1e-300, f * (np.log(np.maximum(f, 1e-300)) - np.log(np.maximum(g, 1e-300))), 0.0)
    return np.trapz(integrand, x)


def reverse_kl_gauss_fit(par, starts=None):
    """Minimise D(q||p) over q = N(m, s^2) for the mixture p. Returns a list of local minima (m, s, KL),
    sorted by KL (Murphy Section 5.1.4.3)."""
    x = _grid(par)
    p = bimodal_pdf(x, **par)

    def obj(th):
        m, ls = th
        q = stats.norm.pdf(x, m, math.exp(ls))
        return kl_grid(q, p, x)

    mm, vv = mixture_moments(par)
    if starts is None:
        starts = [(par["m1"], math.log(par["s1"])), (par["m2"], math.log(par["s2"])), (mm, 0.5 * math.log(vv))]
    sols = []
    for s0 in starts:
        r = optimize.minimize(obj, s0, method="Nelder-Mead", options=dict(xatol=1e-7, fatol=1e-12, maxiter=2000))
        sol = (float(r.x[0]), float(math.exp(r.x[1])), float(r.fun))
        if not any(abs(sol[0] - t[0]) < 1e-3 and abs(sol[1] - t[1]) < 1e-3 for t in sols):
            sols.append(sol)
    sols.sort(key=lambda t: t[2])
    return sols


def forward_kl_gauss_fit(par):
    """Moment matching: the minimiser of D(p||q) over Gaussians q (Murphy 5.1.4.2)."""
    m, v = mixture_moments(par)
    x = _grid(par)
    p = bimodal_pdf(x, **par)
    return m, math.sqrt(v), kl_grid(p, stats.norm.pdf(x, m, math.sqrt(v)), x)


# == 2-D Gaussian target with a diagonal q
def diag_projections(Sigma):
    """(forward diagonal covariance, reverse diagonal covariance) for p = N(0, Sigma): the first matches
    the marginal variances, the second the marginal precisions (Murphy 5.39 and Supp. 5.9)."""
    Sigma = np.asarray(Sigma, float)
    Lam = np.linalg.inv(Sigma)
    return np.diag(np.diag(Sigma)), np.diag(1.0 / np.diag(Lam))


# ============================================================================ entropy and units (Section 5.2)
def height_mixture():
    """Stand-in for the adult-height density of Murphy's Figure 5.5 (centimetres)."""
    return dict(w=0.5, m1=164.7, s1=7.1, m2=178.4, s2=7.6)


def differential_entropy_bits(scale=1.0, par=None):
    """Differential entropy in bits of scale * X, X the height mixture in centimetres."""
    par = par or height_mixture()
    x = np.linspace(100, 250, 300001)
    p = bimodal_pdf(x, **par)
    h = -np.trapz(np.where(p > 0, p * np.log2(np.maximum(p, 1e-300)), 0.0), x)
    return h + math.log2(scale)


# ============================================================================ typical sets (Section 5.2.3)
def typical_set_stats(theta, N, eps):
    """For N iid Bernoulli(theta) trials: probability of the eps-typical set and log2 of its size / N."""
    k = np.arange(N + 1)
    logp_seq = k * np.log2(theta) + (N - k) * np.log2(1 - theta)          # log2 p(x^N), depends on k only
    H = float(binary_entropy(np.array([theta]))[0])
    typ = (-logp_seq / N >= H - eps) & (-logp_seq / N <= H + eps)
    pk = stats.binom.pmf(k, N, theta)
    prob = float(pk[typ].sum())
    log2size = float(special.logsumexp(special.gammaln(N + 1) - special.gammaln(k[typ] + 1) - special.gammaln(N - k[typ] + 1)) / LN2) if typ.any() else -np.inf
    return prob, log2size / N, H


# ============================================================================ mutual information bounds (Section 5.3.6)
def gauss_critic_logratio(x, y, rho):
    """log p(x,y)/(p(x)p(y)) for the standard bivariate Gaussian with correlation rho."""
    return -0.5 * np.log(1 - rho ** 2) - (rho ** 2 * (x ** 2 + y ** 2) - 2 * rho * x * y) / (2 * (1 - rho ** 2))


def logZ_scaled_critic(lam, rho):
    """log E_{p(x)p(y)} exp(lam * f*(x,y)) in closed form (needs lam < (1+rho)/rho)."""
    r2 = rho ** 2
    a = 1 + lam * r2 / (1 - r2)
    det = a * a - (lam * rho / (1 - r2)) ** 2
    return -0.5 * lam * math.log(1 - r2) - 0.5 * math.log(det)


def dv_bound(lam, rho):
    """Donsker-Varadhan bound (5.148) with critic lam * f* (Gaussian pair), nats."""
    return lam * mi_gauss(rho) - logZ_scaled_critic(lam, rho)


def nwj_bound(lam, c, rho):
    """NWJ bound (5.150) with critic lam * f* + c, nats."""
    return lam * mi_gauss(rho) + c - math.exp(logZ_scaled_critic(lam, rho) + c) / math.e


def ba_bound(a, tau2, rho):
    """Barber-Agakov lower bound (5.144) with q(x|y) = N(a y, tau2), nats (x, y standard)."""
    e_logq = -0.5 * math.log(2 * math.pi * tau2) - (1 + a * a - 2 * a * rho) / (2 * tau2)
    return e_logq + 0.5 * math.log(2 * math.pi * math.e)


def upper_bound(s2, rho):
    """Variational upper bound (5.141) with q(y) = N(0, s2), nats."""
    return 0.5 * (math.log(s2 / (1 - rho ** 2)) + 1.0 / s2 - 1.0)


def infonce_mc(rho, K, batches, seed=0, lam=1.0):
    """Monte Carlo estimate of I_NCE (5.151) with critic lam * f*; returns (mean, standard error), nats."""
    rng = np.random.default_rng(seed)
    x = rng.standard_normal((batches, K))
    y = rho * x + math.sqrt(1 - rho ** 2) * rng.standard_normal((batches, K))
    f = lam * gauss_critic_logratio(x[:, :, None], y[:, None, :], rho)         # f[b, i, j] = f(x_i, y_j)
    # (5.151): average over i of log( e^{f_ii} / (1/K sum_j e^{f_ij}) ), scores of x_i against all y_j
    lse = special.logsumexp(f, axis=2) - math.log(K)
    per = np.einsum("bii->bi", f) - lse
    v = per.mean(1)
    return float(v.mean()), float(v.std(ddof=1) / math.sqrt(batches))


# ============================================================================ coding (Sections 5.4, 5.5)
def huffman_lengths(p):
    """Code lengths of a binary Huffman code for the probability vector p."""
    import heapq
    p = list(map(float, p))
    heap = [(pi, i, [i]) for i, pi in enumerate(p)]
    heapq.heapify(heap)
    lengths = [0] * len(p)
    cnt = len(p)
    while len(heap) > 1:
        a = heapq.heappop(heap)
        b = heapq.heappop(heap)
        for s in a[2] + b[2]:
            lengths[s] += 1
        heapq.heappush(heap, (a[0] + b[0], cnt, a[2] + b[2]))
        cnt += 1
    return lengths


def arithmetic_encode(seq, probs):
    """Exact (Fraction) arithmetic coding of a symbol sequence under the iid model probs.
    Returns the bit string of a shortest dyadic interval inside the final interval and the interval."""
    probs = [Fraction(p).limit_denominator(10 ** 6) for p in probs]
    cum = [Fraction(0)]
    for p in probs:
        cum.append(cum[-1] + p)
    lo, width = Fraction(0), Fraction(1)
    for s in seq:
        lo = lo + width * cum[s]
        width = width * probs[s]
    # shortest bit string b with [0.b, 0.b + 2^-len) inside [lo, lo + width)
    L = 1
    while True:
        scale = 2 ** L
        k = math.ceil(lo * scale)
        if Fraction(k, scale) + Fraction(1, scale) <= lo + width:
            return format(k, "0%db" % L), (lo, lo + width), width
        L += 1


def arithmetic_decode(bits, n, probs):
    probs = [Fraction(p).limit_denominator(10 ** 6) for p in probs]
    cum = [Fraction(0)]
    for p in probs:
        cum.append(cum[-1] + p)
    v = Fraction(int(bits, 2), 2 ** len(bits))
    lo, width = Fraction(0), Fraction(1)
    out = []
    for _ in range(n):
        for s in range(len(probs)):
            a = lo + width * cum[s]
            b = lo + width * cum[s + 1]
            if a <= v < b:
                out.append(s)
                lo, width = a, width * probs[s]
                break
    return out


def parity_code_posterior(y, alpha=0.2):
    """Posterior over the 8 words of the length-3 even-parity code (Murphy Figure 5.11): returns an array over
    the 8 binary strings 000..111 (zero for non-codewords)."""
    post = np.zeros(8)
    for x1 in (0, 1):
        for x2 in (0, 1):
            x = (x1, x2, x1 ^ x2)
            like = 1.0
            for xi, yi in zip(x, y):
                like *= (1 - alpha) if xi == yi else alpha
            post[x[0] * 4 + x[1] * 2 + x[2]] = 0.25 * like
    return post / post.sum()


def block_error_map(codewords, alpha):
    """Exact block error probability of minimum-distance (MAP) decoding of a code over the binary symmetric
    channel with flip probability alpha < 1/2, uniform prior on the codewords; ties broken by the first word."""
    cw = np.array(codewords)
    n = cw.shape[1]
    ok = 0.0
    for y in itertools.product((0, 1), repeat=n):
        d = (cw != np.array(y)).sum(1)
        like = alpha ** d * (1 - alpha) ** (n - d)
        ok += like[int(np.argmax(like))] / len(cw)
    return 1.0 - ok


# ============================================================================ information bottleneck (Section 5.6)
def ib_init(nx, nz):
    """Deterministic start used by the demo as well: p(z|x) proportional to 1 + 0.5 sin(1 + 7 x + 3 z)."""
    a = np.array([[1 + 0.5 * math.sin(1 + 7 * (x + 1) + 3 * (z + 1)) for z in range(nz)] for x in range(nx)])
    return a / a.sum(1, keepdims=True)


def ib_objective(pxy, pzx, beta):
    """beta I(Z;X) - I(Z;Y) for the Markov chain Z - X - Y (Murphy 5.165), nats."""
    px = pxy.sum(1)
    pzxjoint = pzx * px[:, None]                  # p(x, z)
    pyx = pxy / px[:, None]
    pzy = pzxjoint.T @ pyx                         # p(z, y)
    return beta * mutual_information(pzxjoint, math.e) - mutual_information(pzy, math.e)


def ib_fit(pxy, beta, nz, pzx=None, iters=500):
    """Self-consistent information-bottleneck iteration for min beta I(Z;X) - I(Z;Y):
    p(z|x) proportional to m(z) exp(-KL(p(y|x) || p(y|z)) / beta); see gap 5.22."""
    pxy = np.asarray(pxy, float)
    px = pxy.sum(1)
    pyx = pxy / px[:, None]
    if pzx is None:
        pzx = ib_init(len(px), nz)
    for _ in range(iters):
        m = px @ pzx                                              # m(z)
        pxz = pzx * px[:, None] / np.maximum(m[None, :], 1e-300)  # p(x|z)
        pyz = pxz.T @ pyx                                         # p(y|z), rows z
        # KL(p(y|x)||p(y|z)) for all x,z
        with np.errstate(divide="ignore", invalid="ignore"):
            lr = np.where(pyx[:, None, :] > 0, pyx[:, None, :] * (np.log(np.maximum(pyx[:, None, :], 1e-300)) - np.log(np.maximum(pyz[None, :, :], 1e-300))), 0.0)
        D = lr.sum(2)
        logit = np.log(np.maximum(m, 1e-300))[None, :] - D / beta
        logit -= logit.max(1, keepdims=True)
        pzx = np.exp(logit)
        pzx /= pzx.sum(1, keepdims=True)
    return pzx


def ib_information(pxy, pzx):
    px = pxy.sum(1)
    pyx = pxy / px[:, None]
    pzxj = pzx * px[:, None]
    return mutual_information(pzxj, math.e), mutual_information(pzxj.T @ pyx, math.e)


def ib_curve(pxy, nz, betas):
    """Information-plane points (I(Z;X), I(Z;Y)) for decreasing betas with warm starts."""
    pzx = None
    out = []
    for b in betas:
        pzx = ib_fit(pxy, b, nz, pzx, iters=400)
        out.append(ib_information(pxy, pzx))
    return np.array(out)


# ============================================================================ Solomonoff (Section 5.7.2)
def solomonoff_total_error(theta_star, thetas, w, n):
    """Exact expected cumulative squared error S_n of the Bayes mixture predictor over a finite class of
    Bernoulli models when the data are iid Bernoulli(theta_star) (Murphy 5.196 and 5.197).
    Returns the array S_1..S_n."""
    thetas = np.asarray(thetas, float)
    w = np.asarray(w, float)
    S = np.zeros(n)
    acc = 0.0
    for t in range(1, n + 1):
        k = np.arange(t)                                           # ones among the t-1 earlier symbols
        logpost = np.log(w)[None, :] + k[:, None] * np.log(thetas)[None, :] + (t - 1 - k)[:, None] * np.log(1 - thetas)[None, :]
        post = np.exp(logpost - special.logsumexp(logpost, axis=1, keepdims=True))
        xi1 = post @ thetas                                        # xi(x_t = 1 | past)
        st = (theta_star - xi1) ** 2 * 2                           # (mu1-xi1)^2 + (mu0-xi0)^2
        acc += float((stats.binom.pmf(k, t - 1, theta_star) * st).sum())
        S[t - 1] = acc
    return S


# ============================================================================ data: newsgroups stand-in
FAMILY = {"comp": "comp", "rec": "rec", "sci": "sci", "talk": "talk"}


def load_newsgroups_binary(nwords=100, vocab=2000, seed=0):
    """Binary bag-of-words for four newsgroup families (comp, rec, sci, talk).
    Returns X (docs x nwords, 0/1), y (family index), words. The words are the nwords with the highest
    mutual information with the family among the `vocab` most frequent non-stop words (cached)."""
    os.makedirs(CACHE_DIR, exist_ok=True)
    path = os.path.join(CACHE_DIR, "ch05_news_binary.npz")
    if os.path.exists(path):
        z = np.load(path, allow_pickle=True)
        return z["X"], z["y"], list(z["words"])
    from sklearn.datasets import fetch_20newsgroups
    from sklearn.feature_extraction.text import CountVectorizer
    d = fetch_20newsgroups(subset="all", remove=("headers", "footers", "quotes"))
    fam = []
    keep = []
    for i, t in enumerate(d.target):
        name = d.target_names[t].split(".")[0]
        if name in FAMILY:
            keep.append(i)
            fam.append(list(FAMILY).index(name))
    docs = [d.data[i] for i in keep]
    y = np.array(fam)
    cv = CountVectorizer(binary=True, stop_words="english", token_pattern=r"(?u)\b[a-zA-Z]{3,}\b", max_features=vocab, min_df=20)
    X = cv.fit_transform(docs).toarray().astype(np.uint8)
    words = np.array(cv.get_feature_names_out())
    # mutual information of each word column with the family label
    mi = np.zeros(X.shape[1])
    for j in range(X.shape[1]):
        tab = np.zeros((2, 4))
        for c in range(4):
            col = X[y == c, j]
            tab[1, c] = col.sum()
            tab[0, c] = len(col) - col.sum()
        mi[j] = mutual_information(tab / tab.sum())
    top = np.argsort(-mi)[:nwords]
    np.savez_compressed(path, X=X[:, top], y=y, words=words[top])
    return X[:, top], y, list(words[top])


def pairwise_mi_binary(X):
    """Pairwise mutual information in bits between the columns of a 0/1 matrix."""
    X = X.astype(float)
    n, d = X.shape
    n11 = X.T @ X
    c1 = X.sum(0)
    M = np.zeros((d, d))
    for i in range(d):
        for j in range(i + 1, d):
            a = n11[i, j]
            tab = np.array([[n - c1[i] - c1[j] + a, c1[j] - a], [c1[i] - a, a]]) / n
            M[i, j] = M[j, i] = mutual_information(tab)
    return M


# ============================================================================ figures
def _out(out):
    return dict(out_dir=out) if out else {}


def fig_5_1(out=None):
    """Figure 5.1: forward vs reverse KL for a bimodal p and a Gaussian q"""
    par = BIMODAL
    x = np.linspace(-8, 22, 3001)
    p = bimodal_pdf(x, **par)
    mf, sf, _ = forward_kl_gauss_fit(par)
    rev = reverse_kl_gauss_fit(par)
    mr, sr, _ = rev[0]
    fig, ax = plt.subplots(figsize=(5.6, 2.5))
    ax.plot(x, p, color=BLUE, label="$p$")
    ax.plot(x, stats.norm.pdf(x, mf, sf), "--", color=ORANGE, label=r"$\min_q D_{\mathrm{KL}}(p\,\|\,q)$")
    ax.plot(x, stats.norm.pdf(x, mr, sr), "-.", color=GREEN, label=r"$\min_q D_{\mathrm{KL}}(q\,\|\,p)$")
    ax.set_xlabel("$x$")
    ax.set_ylabel("density")
    ax.legend(frameon=False, loc="upper left", fontsize=8)
    return savefig(fig, CH, "fig5-1", **_out(out))


def fig_5_2(out=None):
    """Figure 5.2: forward vs reverse KL for a correlated Gaussian and a diagonal q"""
    Sigma = np.array([[1.0, 0.9], [0.9, 1.0]]) * 0.25
    Sf, Sr = diag_projections(Sigma)
    fig, axes = common.panel_grid(1, 2, size=(2.9, 2.9))
    for ax, S, lab in zip(axes[0], (Sf, Sr), ("a", "b")):
        for ns in (0.5, 1.0, 1.5, 2.0, 2.5):
            ax.plot(*ellipse_xy(np.zeros(2), Sigma, ns), color=BLUE, lw=0.9)
            ax.plot(*ellipse_xy(np.zeros(2), S, ns), color=RED, lw=0.9)
        ax.set_xlim(-1, 1)
        ax.set_ylim(-1, 1)
        ax.set_aspect("equal")
        ax.set_xticks([-1, 0, 1])
        ax.set_yticks([-1, 0, 1])
        common.panel_label(ax, lab, "lower right")
    axes[0][0].set_title(r"$\min D_{\mathrm{KL}}(p\|q)$", fontsize=9)
    axes[0][1].set_title(r"$\min D_{\mathrm{KL}}(q\|p)$", fontsize=9)
    return savefig(fig, CH, "fig5-2", **_out(out))


def fig_5_4(out=None):
    """Figure 5.4: entropy of a Bernoulli variable"""
    t = np.linspace(0, 1, 501)
    fig, ax = plt.subplots(figsize=(3.6, 2.5))
    ax.plot(t, binary_entropy(t), color=BLUE)
    ax.set_xlabel("$p(X=1)$")
    ax.set_ylabel("$H(X)$ (bits)")
    ax.set_xlim(0, 1)
    ax.set_ylim(0, 1.05)
    ax.axvline(0.5, color=GREY, lw=0.6, ls=":")
    return savefig(fig, CH, "fig5-4", **_out(out))


def fig_5_5(out=None):
    """Figure 5.5: the differential entropy of a height density depends on the units"""
    par = height_mixture()
    fig, ax = plt.subplots(figsize=(5.2, 2.5))
    x = np.linspace(130, 220, 600)
    ax.plot(x, bimodal_pdf(x, **par), color=BLUE)
    ax.fill_between(x, bimodal_pdf(x, **par), color=BLUE, alpha=0.15)
    ax.set_xlabel("height (cm)")
    ax.set_ylabel("density per cm")
    sec = ax.secondary_xaxis("top", functions=(lambda c: c / 30.48, lambda f: f * 30.48))
    sec.set_xlabel("height (ft)")
    txt = "h = %.2f bits (feet)\nh = %.2f bits (cm)\nh = %.2f bits (m)" % (
        differential_entropy_bits(1 / 30.48), differential_entropy_bits(1.0), differential_entropy_bits(0.01))
    ax.text(0.02, 0.97, txt, transform=ax.transAxes, va="top", fontsize=8.5)
    return savefig(fig, CH, "fig5-5", **_out(out))


def fig_5_8(out=None):
    """Figure 5.8: binary bag-of-words matrix for four newsgroup families (stand-in data)"""
    X, y, words = load_newsgroups_binary()
    rng = np.random.default_rng(0)
    idx = np.sort(rng.choice(len(y), 1000, replace=False))
    order = np.argsort(y[idx], kind="stable")
    idx = idx[order]
    fig, ax = plt.subplots(figsize=(4.6, 4.4))
    ax.imshow(X[idx], aspect="auto", cmap="gray_r", interpolation="nearest")
    ys = y[idx]
    for c in range(1, 4):
        ax.axhline(np.argmax(ys >= c) - 0.5, color=RED, lw=1.2)
    ax.set_xlabel("words")
    ax.set_ylabel("documents (1000 of %d, sorted by family)" % len(y))
    return savefig(fig, CH, "fig5-8", **_out(out))


def relevance_edges(X, words, frac=0.2):
    M = pairwise_mi_binary(X)
    thr = frac * M.max()
    ii, jj = np.where(np.triu(M >= thr, 1))
    return M, thr, list(zip(ii, jj))


def fig_5_9(out=None):
    """Figure 5.9: relevance network of the words (edges: MI at least 20 percent of the maximum)"""
    import networkx as nx
    X, y, words = load_newsgroups_binary()
    M, thr, edges = relevance_edges(X, words)
    G = nx.Graph()
    G.add_edges_from(edges)
    deg = dict(G.degree())
    keep = sorted(deg, key=lambda k: -deg[k])[:30]
    H = G.subgraph(keep).copy()
    pos = nx.spring_layout(H, seed=3, k=0.9)
    fig, ax = plt.subplots(figsize=(5.4, 4.6))
    nx.draw_networkx_edges(H, pos, ax=ax, edge_color=GREY, width=0.9)
    nx.draw_networkx_nodes(H, pos, ax=ax, node_color="#cfe0ff", edgecolors=BLUE, node_size=260)
    nx.draw_networkx_labels(H, pos, {i: words[i] for i in H.nodes}, ax=ax, font_size=6.5)
    ax.set_axis_off()
    return savefig(fig, CH, "fig5-9", **_out(out))


def rd_gaussian_curves(s2):
    """Rate and distortion (nats) of the Gaussian encoder z = x + noise(s2) for x ~ N(0,1):
    returns dict with the matched design (optimal decoder and marginal), and two mismatched ones."""
    s2 = np.asarray(s2, float)
    H = 0.5 * math.log(2 * math.pi * math.e)
    R = 0.5 * np.log((1 + s2) / s2)                 # = I(x;z) when m is the true marginal
    D_opt = 0.5 * np.log(2 * math.pi * math.e * s2 / (1 + s2))
    # decoder with a fixed (too small) variance vd, optimal mean c z with c = 1/(1+s2)
    vd = 0.05
    err = s2 / (1 + s2)
    D_fixed = 0.5 * math.log(2 * math.pi * vd) + err / (2 * vd)
    # marginal with a wrong variance vm = 4 (rate rises, distortion unchanged)
    vm = 4.0
    R_wrong = 0.5 * (np.log(vm / s2) + (s2 + 1) / vm - 1)
    return dict(H=H, R=R, D_opt=D_opt, D_fixed=D_fixed, R_wrong=R_wrong)


def fig_5_10(out=None):
    """Figure 5.10: the rate-distortion plane, closed-form Gaussian example"""
    s2 = np.logspace(-2.2, 2.0, 400)
    c = rd_gaussian_curves(s2)
    H = c["H"]
    fig, ax = plt.subplots(figsize=(4.8, 3.4))
    Rg = np.linspace(0, 3.6, 100)
    ax.fill_between(Rg, H - Rg, 4.5, color="#eef3fb", zorder=0)
    ax.plot(Rg, H - Rg, "k-", lw=1.4, label=r"$D=H-R$ (non-parametric limit)")
    ax.plot(c["R"], c["D_opt"], color=BLUE, ls=":", lw=1.2, label="matched decoder and marginal")
    ax.plot(c["R"], c["D_fixed"], color=RED, label="decoder variance fixed at 0.05")
    ax.plot(c["R_wrong"], c["D_opt"], color=GREEN, label="marginal variance fixed at 4")
    ax.axhline(H, color=GREY, lw=0.6, ls="--")
    ax.text(3.55, H + 0.05, "$H$", ha="right", fontsize=8)
    ax.set_xlim(0, 3.6)
    ax.set_ylim(-1.8, 3.2)
    ax.set_xlabel("rate $R$ (nats)")
    ax.set_ylabel("distortion $D$ (nats)")
    ax.legend(frameon=False, fontsize=7, loc="upper right")
    return savefig(fig, CH, "fig5-10", **_out(out))


def fig_5_11(out=None):
    """Figure 5.11b: posterior over the 8 words of the parity code given y = (1,0,0), flip probability 0.2"""
    post = parity_code_posterior((1, 0, 0), 0.2)
    fig, ax = plt.subplots(figsize=(4.4, 2.4))
    ax.bar(range(8), post, color=BLUE)
    ax.set_xticks(range(8))
    ax.set_xticklabels([format(i, "03b") for i in range(8)], fontsize=8)
    ax.set_ylabel("$p(x\\mid y=1,0,0)$")
    return savefig(fig, CH, "fig5-11", **_out(out))


def train_bottleneck(vib, beta, seed=0, epochs=8, ntrain=30000, ntest=2000):
    """Train the 2-D-bottleneck MLP on MNIST (CPU); returns test embeddings (means, log-variances, labels)."""
    path = os.path.join(CACHE_DIR, "ch05_bottleneck_%s_%g.npz" % ("vib" if vib else "det", beta))
    if os.path.exists(path):
        z = np.load(path)
        return z["mu"], z["lv"], z["y"]
    os.makedirs(CACHE_DIR, exist_ok=True)
    torch = common.torch_setup(seed)
    nn = torch.nn
    X, y = common.mnist(True)
    Xt, yt = common.mnist(False)
    X, y = torch.tensor(X[:ntrain], dtype=torch.float32), torch.tensor(y[:ntrain])
    Xt, yt = torch.tensor(Xt[:ntest], dtype=torch.float32), torch.tensor(yt[:ntest])
    body = nn.Sequential(nn.Linear(784, 400), nn.ReLU(), nn.Linear(400, 200), nn.ReLU())
    head = nn.Linear(200, 4 if vib else 2)
    dec = nn.Sequential(nn.Linear(2, 10))
    params = list(body.parameters()) + list(head.parameters()) + list(dec.parameters())
    opt = torch.optim.Adam(params, lr=2e-3)
    g = torch.Generator().manual_seed(seed)
    for ep in range(epochs):
        perm = torch.randperm(len(X), generator=g)
        for i in range(0, len(X), 128):
            b = perm[i:i + 128]
            h = head(body(X[b]))
            if vib:
                mu, lv = h[:, :2], h[:, 2:]
                eps = torch.randn(mu.shape, generator=g)
                z = mu + torch.exp(0.5 * lv) * eps
                kl_term = 0.5 * (mu ** 2 + torch.exp(lv) - lv - 1).sum(1).mean()     # KL(N(mu,s^2) || N(0,I))
                loss = nn.functional.cross_entropy(dec(z), y[b]) + beta * kl_term
            else:
                loss = nn.functional.cross_entropy(dec(h), y[b])
            opt.zero_grad()
            loss.backward()
            opt.step()
    with torch.no_grad():
        h = head(body(Xt))
        if vib:
            mu, lv = h[:, :2].numpy(), h[:, 2:].numpy()
        else:
            mu, lv = h.numpy(), np.zeros_like(h.numpy())
        acc = (dec(torch.tensor(mu)).argmax(1) == yt).float().mean().item()
    print("  bottleneck vib=%s beta=%g test accuracy %.3f" % (vib, beta, acc))
    np.savez_compressed(path, mu=mu, lv=lv, y=yt.numpy())
    return mu, lv, yt.numpy()


VIB_BETA = 0.02


def fig_5_13(out=None):
    """Figure 5.13: 2-D embeddings of MNIST: deterministic bottleneck and VIB (means, standard deviations)"""
    mu0, _, y = train_bottleneck(False, 0.0)
    mu1, lv1, _ = train_bottleneck(True, VIB_BETA)
    cmap = plt.get_cmap("tab10")
    fig, axes = common.panel_grid(1, 3, size=(2.9, 2.9))
    axes[0][0].scatter(mu0[:, 0], mu0[:, 1], c=y, cmap=cmap, s=3, vmin=0, vmax=9)
    axes[0][1].scatter(mu1[:, 0], mu1[:, 1], c=y, cmap=cmap, s=3, vmin=0, vmax=9)
    sd = np.exp(0.5 * lv1)
    t = np.linspace(0, 2 * np.pi, 40)
    rng = np.random.default_rng(0)
    for i in rng.choice(len(y), 250, replace=False):
        axes[0][2].plot(mu1[i, 0] + sd[i, 0] * np.cos(t), mu1[i, 1] + sd[i, 1] * np.sin(t), color=cmap(y[i]), lw=0.5)
    for ax, lab in zip(axes[0], "abc"):
        common.panel_label(ax, lab, "upper left")
    axes[0][1].set_xlim(axes[0][1].get_xlim())
    axes[0][2].set_xlim(axes[0][1].get_xlim())
    axes[0][2].set_ylim(axes[0][1].get_ylim())
    return savefig(fig, CH, "fig5-13", **_out(out))


# == original figures
def fig_5_S1(out=None):
    """Figure 5.S1: the asymptotic equipartition property (Bernoulli(0.3), eps = 0.05)"""
    theta, eps = 0.3, 0.05
    Ns = np.unique(np.round(np.logspace(1, 3.3, 40)).astype(int))
    st = np.array([typical_set_stats(theta, int(N), eps) for N in Ns])
    H = st[0, 2]
    fig, axes = common.panel_grid(1, 2, size=(2.9, 2.5))
    axes[0][0].semilogx(Ns, st[:, 0], color=BLUE)
    axes[0][0].set_ylim(0, 1.02)
    axes[0][0].set_xlabel("$N$")
    axes[0][0].set_ylabel(r"$\Pr(A_\epsilon^N)$")
    axes[0][1].semilogx(Ns, st[:, 1], color=RED, label=r"$\frac{1}{N}\log_2|A_\epsilon^N|$")
    axes[0][1].axhline(H, color="k", lw=0.8, label="$H$")
    axes[0][1].axhline(H + eps, color=GREY, ls=":", lw=0.8)
    axes[0][1].axhline(H - eps, color=GREY, ls=":", lw=0.8)
    axes[0][1].axhline(1.0, color=GREEN, ls="--", lw=0.8, label=r"$\log_2 2$ (all sequences)")
    axes[0][1].set_xlabel("$N$")
    axes[0][1].legend(frameon=False, fontsize=7, loc="center right")
    return savefig(fig, CH, "fig5-S1", **_out(out))


def fig_5_S2(out=None):
    """Figure 5.S2: InfoNCE with the optimal critic saturates at log K"""
    Ks = np.array([2, 4, 8, 16, 32, 64, 128, 256])
    fig, ax = plt.subplots(figsize=(4.6, 3.0))
    for rho, col in ((0.9, BLUE), (0.99, RED), (0.999, GREEN)):
        v = [infonce_mc(rho, int(K), 300 if K < 128 else 60, seed=1)[0] for K in Ks]
        ax.semilogx(Ks, v, "o-", color=col, ms=3, label=r"$\rho=%g$, $I=%.2f$" % (rho, mi_gauss(rho)))
        ax.axhline(mi_gauss(rho), color=col, ls=":", lw=0.8)
    ax.semilogx(Ks, np.log(Ks), "k--", lw=0.8, label=r"$\log K$")
    ax.set_xlabel("batch size $K$")
    ax.set_ylabel("$I_{\\mathrm{NCE}}$ (nats)")
    ax.legend(frameon=False, fontsize=7)
    return savefig(fig, CH, "fig5-S2", **_out(out))


def word_class_table(nwords=12):
    """p(word, family) from document counts for the nwords most informative words: returns (words, families, counts)."""
    X, y, words = load_newsgroups_binary()
    counts = np.array([[X[y == c, j].sum() for c in range(4)] for j in range(X.shape[1])], float)
    pw = counts / counts.sum()
    # keep the words with the largest contribution to I(word; family) among those with enough mass
    px = counts.sum(1) / counts.sum()
    pc = counts.sum(0) / counts.sum()
    contrib = (pw * np.log(np.maximum(pw, 1e-300) / np.outer(px, pc))).sum(1)
    top = np.argsort(-contrib)[:nwords]
    return [words[j] for j in top], list(FAMILY), counts[top]


def fig_5_S3(out=None):
    """Figure 5.S3: the information-bottleneck curve for 12 words and 4 newsgroup families"""
    words, fams, counts = word_class_table()
    pxy = counts / counts.sum()
    betas = np.logspace(1.0, -2.5, 44)
    pts = ib_curve(pxy, 12, betas)
    ixy = mutual_information(pxy, math.e)
    hx = entropy(pxy.sum(1), math.e)
    fig, ax = plt.subplots(figsize=(4.4, 3.2))
    ax.plot(pts[:, 0], pts[:, 1], "o-", color=BLUE, ms=3)
    ax.axhline(ixy, color=GREY, ls=":", lw=0.9)
    ax.plot([0, ixy], [0, ixy], color=RED, lw=0.9, ls="--")
    ax.set_xlabel("$I(Z;X)$ (nats)")
    ax.set_ylabel("$I(Z;Y)$ (nats)")
    ax.text(hx * 0.99, ixy * 1.02, "$I(X;Y)$", ha="right", fontsize=8)
    ax.set_xlim(0, hx)
    return savefig(fig, CH, "fig5-S3", **_out(out))


def fig_5_S4(out=None):
    """Figure 5.S4: Solomonoff's bound S_infty <= ln(1/w_mu) for a Bayes mixture over 9 Bernoulli models"""
    thetas = np.arange(1, 10) / 10
    n = 3000
    fig, ax = plt.subplots(figsize=(4.8, 3.0))
    for w, lab, col in ((np.ones(9) / 9, "uniform prior", BLUE), (2.0 ** -np.arange(1, 10) / (1 - 2.0 ** -9), r"$w_\nu\propto2^{-\mathrm{rank}}$", RED)):
        S = solomonoff_total_error(0.3, thetas, w, n)
        ax.plot(np.arange(1, n + 1), S, color=col, label=lab)
        ax.axhline(math.log(1 / w[2]), color=col, ls=":", lw=0.9)
    ax.set_xscale("log")
    ax.set_xlabel("$n$")
    ax.set_ylabel("$S_n$")
    ax.legend(frameon=False, fontsize=8, loc="upper left")
    return savefig(fig, CH, "fig5-S4", **_out(out))


# ============================================================================ data export for the demos
def export_data():
    os.makedirs(DATA_JSON, exist_ok=True)
    words, fams, counts = word_class_table()
    with open(os.path.join(DATA_JSON, "ch05-word-class.json"), "w") as f:
        json.dump({"words": words, "classes": fams, "counts": counts.astype(int).tolist(),
                   "note": "document counts of the 12 words most informative about the newsgroup family, 4 families"}, f)
    print("wrote ch05-word-class.json")


FIGURES = {"5.1": fig_5_1, "5.2": fig_5_2, "5.4": fig_5_4, "5.5": fig_5_5, "5.8": fig_5_8, "5.9": fig_5_9,
           "5.10": fig_5_10, "5.11": fig_5_11, "5.13": fig_5_13,
           "5.S1": fig_5_S1, "5.S2": fig_5_S2, "5.S3": fig_5_S3, "5.S4": fig_5_S4}

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