"""Murphy (2023), Chapter 4: Graphical models.

Companion code for Chapter 4 of K. P. Murphy, Probabilistic Machine Learning: Advanced Topics (MIT Press,
2023; December 2025 draft), pp. 143-217, and its supplement (Supplementary Chapter 4), written from scratch
with numpy, scipy and matplotlib, to be read next to the lecture notes (../ch04-graphical-models.html).

Methods implemented (the notes use these functions by name)
* Directed models (Section 4.2): graph utilities (ancestors, descendants, moralisation, the ancestral
  graph), d-separation by the reachability ("Bayes ball") rule and, independently, by separation in the
  moralised ancestral graph (d_separated, d_separated_moral); discrete Bayes nets with tabular CPDs
  (DiscreteBN: joint table, posterior marginals by enumeration, ancestral sampling, conditional mutual
  information, counts, maximum likelihood and Dirichlet posterior-mean CPTs (4.45)-(4.48), EM with a hidden
  node (4.52)-(4.55), the Fisher-identity gradient (4.62)); the student network (Figure 4.2) and the water
  sprinkler network (Supplement 4.1.1); Gaussian Bayes nets (4.11)-(4.16) with their precision matrix;
  noisy-OR CPDs (Supplement 4.1.3) and Haldane's recombination probability (Supplement 4.1.4).
* Undirected models (Sections 4.3-4.4): Ising and Potts models sampled by checkerboard Gibbs sampling
  (4.75)-(4.86), exact enumeration for small lattices, the Hopfield network with the outer-product rule
  and the ICM update (4.87)-(4.90), restricted Boltzmann machines trained by contrastive divergence
  (4.91), (Supplement 4.8)-(4.15), Gaussian MRFs in information form (4.101)-(4.107), mean field
  inference for an Ising image prior with Gaussian noise (4.117), log-linear MRFs with exact moment
  matching (4.118)-(4.123) and iterative proportional fitting, maximum pseudolikelihood (4.127), chain
  CRFs by the forward algorithm and Viterbi (4.138), the maximum-entropy Markov model (4.139) and the
  label-bias effect, Markov logic networks (4.182).
* Comparisons and extensions (Sections 4.5-4.7): moralisation, perfect maps, the dummy-node conversion
  of an undirected model, sum-product networks, and structural causal models (do-operator, additive
  intervention, abduction-action-prediction counterfactuals).

Data. Everything is simulated or built from the numbers printed in the book (the student and sprinkler
CPTs); seeds are fixed in the code. The binary images of Figure 4.19 are synthetic stand-ins (the book's
photographs are not available); the MNIST digits of Figure 4.21 are read through common.mnist (cached).
The noisy image of Figure 4.27 is a synthetic 64 x 64 shape with Gaussian noise (sigma = 2), as in the text.

Figures. Reproduced here: 4.6, 4.8, 4.17, 4.18, 4.19, 4.21, 4.23, 4.25, 4.27, 4.37, 4.38, 4.44. Skipped, with
the reason:
  4.1, 4.3, 4.4, 4.5, 4.7, 4.9-4.15, 4.20, 4.22, 4.24, 4.26, 4.29, 4.33, 4.36, 4.40-4.43, 4.45-4.52, 4.54, 4.55
         hand-drawn diagrams and schematics with nothing computed (graph templates, plate notation, Bayes
         ball rules, factor graphs, relational templates, causal diagrams);
  4.2    the student network with its CPTs: shown as tables in the notes (the numbers are inputs);
  4.16   the two ground states of an antiferromagnet (a hand drawing; the checkerboard is checked in code);
  4.28   the pseudolikelihood neighbourhood diagram;
  4.30-4.32, 4.34, 4.35  natural-language and vision pipelines that need trained neural networks or
         annotated corpora (not feasible on a CPU in the time budget, and the book's data are not public);
  4.53   the education SCM diagram (the model is simulated in 4.S4).
Supplementary figures for the gaps filled in the notes:
  4.S1   AR(1) precision (sparse) against covariance (dense), with the exact inverse of (4.106);
  4.S2   magnetisation of the Ising model against J: Gibbs estimates and Onsager's exact curve;
  4.S3   label bias: MEMM against CRF posterior of the first tag;
  4.S4   seeing against doing in the education structural equation model;
  4.S5   Hopfield retrieval against the load P/N.
Run `python3 ch04_graphical_models.py --list`, `python3 ch04_graphical_models.py` (all figures, a few
minutes) or `python3 ch04_graphical_models.py --fig 4.6`. Files go to ../img/ch04/; the data used by the
browser demonstrations go to ../data/ch04-*.json.
"""
import itertools
import json
import os
import sys

os.environ.setdefault("OPENBLAS_NUM_THREADS", "1")

import numpy as np
from scipy import special, stats

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

CH = 4
HERE = os.path.dirname(os.path.abspath(__file__))
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))


# =========================================================================== graph utilities
# A DAG is a dict {node: list of parents}; an undirected graph is a dict {node: set of neighbours}.
def dag_children(dag):
    ch = {v: [] for v in dag}
    for v, ps in dag.items():
        for p in ps:
            ch[p].append(v)
    return ch


def dag_ancestors(dag, nodes):
    """All ancestors of `nodes` (the nodes themselves are included)."""
    out, stack = set(nodes), list(nodes)
    while stack:
        v = stack.pop()
        for p in dag[v]:
            if p not in out:
                out.add(p)
                stack.append(p)
    return out


def dag_descendants(dag, v):
    """Strict descendants of v."""
    ch = dag_children(dag)
    out, stack = set(), [v]
    while stack:
        u = stack.pop()
        for c in ch[u]:
            if c not in out:
                out.add(c)
                stack.append(c)
    return out


def topological_order(dag):
    order, seen = [], set()

    def visit(v):
        if v in seen:
            return
        seen.add(v)
        for p in dag[v]:
            visit(p)
        order.append(v)
    for v in dag:
        visit(v)
    return order


def moralize(dag, keep=None):
    """Moral graph of the DAG (restricted to the node set `keep`): marry the parents of each node, drop arrows."""
    keep = set(dag) if keep is None else set(keep)
    ug = {v: set() for v in keep}
    for v in keep:
        fam = [p for p in dag[v] if p in keep]
        for p in fam:
            ug[v].add(p)
            ug[p].add(v)
        for a, b in itertools.combinations(fam, 2):
            ug[a].add(b)
            ug[b].add(a)
    return ug


def ancestral_graph(dag, nodes):
    """The sub-DAG induced on the ancestors of `nodes` (including the nodes themselves)."""
    keep = dag_ancestors(dag, nodes)
    return {v: [p for p in dag[v] if p in keep] for v in keep}


def separated(ug, A, B, C):
    """True if C separates A from B in the undirected graph ug (removing C leaves no path from A to B)."""
    A, B, C = set(A), set(B), set(C)
    seen, stack = set(A - C), list(A - C)
    while stack:
        v = stack.pop()
        if v in B:
            return False
        for w in ug[v]:
            if w not in C and w not in seen:
                seen.add(w)
                stack.append(w)
    return not (seen & B)


def d_separated_moral(dag, A, B, C):
    """d-separation through the moralised ancestral graph (Section 4.3.6.2)."""
    U = set(A) | set(B) | set(C)
    return separated(moralize(dag, dag_ancestors(dag, U)), A, B, C)


def d_separated(dag, A, B, C):
    """d-separation by the reachability ("Bayes ball") rules of Section 4.2.4.1.

    Walks over (node, direction) pairs: 'up' means we arrived from a child, 'down' from a parent.
    A node in C blocks chains and forks; a collider passes only if it, or a descendant, is in C.
    """
    A, B, C = set(A), set(B), set(C)
    ch = dag_children(dag)
    anc_C = dag_ancestors(dag, C)
    todo = [(a, "up") for a in A]
    seen, reach = set(), set()
    while todo:
        v, d = todo.pop()
        if (v, d) in seen:
            continue
        seen.add((v, d))
        if v not in C:
            reach.add(v)
        if d == "up" and v not in C:
            todo += [(p, "up") for p in dag[v]] + [(c, "down") for c in ch[v]]
        elif d == "down":
            if v not in C:
                todo += [(c, "down") for c in ch[v]]
            if v in anc_C:       # v or a descendant of v is observed: the collider is "open"
                todo += [(p, "up") for p in dag[v]]
    return not (reach & B)


def markov_blanket_dag(dag, i):
    ch = dag_children(dag)
    mb = set(dag[i]) | set(ch[i])
    for c in ch[i]:
        mb |= set(dag[c])
    mb.discard(i)
    return mb


def ci_statements(dag, max_cond=None):
    """All statements x _||_ y | Z (x < y single nodes, Z any subset of the others) implied by the DAG."""
    nodes = sorted(dag)
    out = []
    for x, y in itertools.combinations(nodes, 2):
        rest = [v for v in nodes if v not in (x, y)]
        for r in range(len(rest) + 1):
            if max_cond is not None and r > max_cond:
                break
            for Z in itertools.combinations(rest, r):
                if d_separated(dag, [x], [y], Z):
                    out.append((x, y, tuple(Z)))
    return out


def count_cpt_parameters(dag, card):
    """Free parameters of a Bayes net with tabular CPDs: sum_i (K_i - 1) prod_{p in pa(i)} K_p."""
    return sum((card[v] - 1) * int(np.prod([card[p] for p in dag[v]])) for v in dag)


def random_dag(n, p, rng):
    """Random DAG on nodes 0..n-1: edge i -> j (i < j) with probability p."""
    return {j: [i for i in range(j) if rng.random() < p] for j in range(n)}


# =========================================================================== discrete Bayes nets
class DiscreteBN:
    """A Bayes net with tabular CPDs.  nodes: list of names; card: {name: K}; parents: {name: [names]};
    cpt[name]: array with one axis per parent (in the order of parents[name]) and a last axis for the node,
    each row summing to one (Section 4.2.2.2, the row-stochastic matrix theta_ijk of (4.7))."""

    def __init__(self, nodes, card, parents, cpt):
        self.nodes = list(nodes)
        self.card = dict(card)
        self.parents = {v: list(parents.get(v, [])) for v in self.nodes}
        self.cpt = {v: np.asarray(cpt[v], float) for v in self.nodes}
        self.idx = {v: i for i, v in enumerate(self.nodes)}

    def joint(self):
        """The joint probability table p(x_1, ..., x_N) = prod_i p(x_i | x_pa(i)) (4.2) as an N-way array."""
        letters = "abcdefghijklmnopqrstuvwxyz"
        subs = []
        for v in self.nodes:
            axes = [self.idx[p] for p in self.parents[v]] + [self.idx[v]]
            subs.append("".join(letters[a] for a in axes))
        spec = ",".join(subs) + "->" + letters[:len(self.nodes)]
        return np.einsum(spec, *[self.cpt[v] for v in self.nodes])

    def marginal(self, query, evidence=None):
        """Posterior marginal p(query | evidence) by enumeration; evidence is {node: state index}."""
        P = self.joint()
        for v, s in (evidence or {}).items():
            sl = [slice(None)] * len(self.nodes)
            sl[self.idx[v]] = s
            Q = np.zeros_like(P)
            Q[tuple(sl)] = P[tuple(sl)]
            P = Q
        axes = tuple(i for i in range(len(self.nodes)) if i != self.idx[query])
        m = P.sum(axis=axes)
        return m / m.sum()

    def dag(self):
        return {v: list(self.parents[v]) for v in self.nodes}

    def sample(self, n, rng):
        """Ancestral sampling (Section 4.2.5): visit nodes in topological order."""
        order = topological_order(self.dag())
        out = np.zeros((n, len(self.nodes)), dtype=int)
        for v in order:
            pa = [self.idx[p] for p in self.parents[v]]
            for r in range(n):
                row = self.cpt[v][tuple(out[r, pa])] if pa else self.cpt[v]
                out[r, self.idx[v]] = rng.choice(len(row), p=row)
        return out

    def log_lik(self, data):
        return float(sum(np.log(self.cpt[v][tuple(data[:, [self.idx[p] for p in self.parents[v]] + [self.idx[v]]].T)]).sum()
                         for v in self.nodes))


def cond_mi(P, X, Y, Z):
    """Conditional mutual information I(X; Y | Z) (nats) from a joint table P (one axis per variable);
    X, Y, Z are lists of axis numbers."""
    n = P.ndim
    keep = lambda s: tuple(i for i in range(n) if i not in s)
    pxyz = P.sum(axis=keep(set(X) | set(Y) | set(Z)))
    # reorder the kept axes as X, Y, Z
    allv = sorted(set(X) | set(Y) | set(Z))
    perm = [allv.index(a) for a in list(X) + list(Y) + list(Z)]
    pxyz = np.transpose(pxyz, perm)
    nx, ny = len(X), len(Y)
    shp = pxyz.shape
    A = pxyz.reshape(int(np.prod(shp[:nx])), int(np.prod(shp[nx:nx + ny])), -1)
    pz = A.sum((0, 1), keepdims=True)
    pxz = A.sum(1, keepdims=True)
    pyz = A.sum(0, keepdims=True)
    with np.errstate(divide="ignore", invalid="ignore"):
        t = np.where(A > 0, A * np.log(A * pz / (pxz * pyz)), 0.0)
    return float(t.sum())


# ---- the student network of Figure 4.2 (states: D easy/hard, I low/high, G A/B/C, S bad/good, L bad/good)
def student_bn():
    nodes = ["D", "I", "G", "S", "L"]
    card = dict(D=2, I=2, G=3, S=2, L=2)
    parents = dict(D=[], I=[], G=["I", "D"], S=["I"], L=["G"])
    cpt = dict(
        D=[0.6, 0.4],
        I=[0.7, 0.3],
        G=[[[0.3, 0.4, 0.3], [0.05, 0.25, 0.7]], [[0.9, 0.08, 0.02], [0.5, 0.3, 0.2]]],   # [I][D][G]
        S=[[0.95, 0.05], [0.2, 0.8]],
        L=[[0.1, 0.9], [0.4, 0.6], [0.99, 0.01]],
    )
    return DiscreteBN(nodes, card, parents, cpt)


STUDENT_STATES = dict(D=["Easy", "Hard"], I=["Low", "High"], G=["A", "B", "C"], S=["Bad", "Good"], L=["Bad", "Good"])


def sprinkler_bn():
    """Water sprinkler of Supplement 4.1.1. The book prints only the CPT of W (Figure 4.1); the other CPTs are
    the standard ones for this example (p(C=1)=0.5, p(S=1|C)=0.5 or 0.1, p(R=1|C)=0.2 or 0.8) and reproduce the
    numbers quoted in the text, p(R=1)=0.5, p(R=1|W=1)=0.7079, p(R=1|W=1,S=1)=0.3204.  The slippery node L has
    p(L=1|W)=0 or 0.9, our choice (the book does not print it)."""
    nodes = ["C", "S", "R", "W", "L"]
    card = {v: 2 for v in nodes}
    parents = dict(C=[], S=["C"], R=["C"], W=["S", "R"], L=["W"])
    cpt = dict(
        C=[0.5, 0.5],
        S=[[0.5, 0.5], [0.9, 0.1]],
        R=[[0.8, 0.2], [0.2, 0.8]],
        W=[[[1.0, 0.0], [0.1, 0.9]], [[0.1, 0.9], [0.01, 0.99]]],     # [S][R][W]
        L=[[1.0, 0.0], [0.1, 0.9]],
    )
    return DiscreteBN(nodes, card, parents, cpt)


# ---- learning CPTs (Sections 4.2.7.2-4.2.7.5)
def cpt_counts(bn, data):
    """Sufficient statistics N_ijk (4.46): for each node an array of counts with the shape of its CPT."""
    out = {}
    for v in bn.nodes:
        cols = [bn.idx[p] for p in bn.parents[v]] + [bn.idx[v]]
        N = np.zeros(bn.cpt[v].shape)
        np.add.at(N, tuple(data[:, cols].T), 1)
        out[v] = N
    return out


def cpt_mle(counts):
    """theta_ijk = N_ijk / sum_k' N_ijk' (4.47) (rows with no data are left undefined: nan)."""
    return {v: N / N.sum(-1, keepdims=True) for v, N in counts.items()}


def cpt_posterior_mean(counts, alpha=1.0):
    """(N_ijk + alpha_ijk) / sum_k' (N_ijk' + alpha_ijk') (4.48), the posterior mean under a Dir(alpha) prior."""
    return {v: (N + alpha) / (N + alpha).sum(-1, keepdims=True) for v, N in counts.items()}


STUDENT_TABLE_4_2 = np.array([  # columns I, D, G, S, L (Table 4.2)
    [0, 0, 2, 0, 0], [0, 1, 2, 0, 0], [0, 0, 1, 1, 1], [1, 1, 1, 1, 0], [1, 0, 0, 1, 1], [0, 0, 0, 0, 1], [1, 1, 2, 1, 1]])


def student_data_bn_order(table=STUDENT_TABLE_4_2):
    """Table 4.2 re-ordered to the column order D, I, G, S, L of student_bn()."""
    return table[:, [1, 0, 2, 3, 4]]


def em_latent_class(X, K, iters, rng, alpha=0.0, theta0=None):
    """EM (4.52)-(4.55) for the DPGM  z -> x_1, ..., x_D  with a hidden class z in {0..K-1} and binary x_d:
    returns pi, theta (K x D = p(x_d=1|z=k)) and the log-likelihood after every iteration (non-decreasing).
    alpha is a Dirichlet/Beta pseudocount added to the expected counts (MAP-style, alpha-1 omitted for clarity)."""
    N, D = X.shape
    pi = np.full(K, 1.0 / K)
    theta = rng.uniform(0.25, 0.75, (K, D)) if theta0 is None else theta0.copy()
    hist = []
    for _ in range(iters):
        logp = np.log(pi)[None] + X @ np.log(theta).T + (1 - X) @ np.log(1 - theta).T       # N x K
        ll = special.logsumexp(logp, axis=1)
        hist.append(float(ll.sum()))
        r = np.exp(logp - ll[:, None])                                                       # E step: family marginals
        Nk = r.sum(0)
        pi = (Nk + alpha) / (N + K * alpha)                                                  # M step (4.55)
        theta = (r.T @ X + alpha) / (Nk[:, None] + 2 * alpha)
    logp = np.log(pi)[None] + X @ np.log(theta).T + (1 - X) @ np.log(1 - theta).T
    hist.append(float(special.logsumexp(logp, axis=1).sum()))
    return pi, theta, np.array(hist)


def latent_class_loglik_grad(X, pi_logits, theta_logits):
    """Gradient of the marginal log-likelihood of the latent-class model with respect to the logits, written as
    the posterior-weighted complete-data gradient (Fisher's identity (4.62))."""
    N, D = X.shape
    pi = special.softmax(pi_logits)
    th = special.expit(theta_logits)
    logp = np.log(pi)[None] + X @ np.log(th).T + (1 - X) @ np.log(1 - th).T
    r = np.exp(logp - special.logsumexp(logp, axis=1, keepdims=True))
    g_pi = r.sum(0) - N * pi
    g_th = r.T @ X - r.sum(0)[:, None] * th
    return g_pi, g_th


def latent_class_loglik(X, pi_logits, theta_logits):
    pi = special.softmax(pi_logits)
    th = special.expit(theta_logits)
    logp = np.log(pi)[None] + X @ np.log(th).T + (1 - X) @ np.log(1 - th).T
    return float(special.logsumexp(logp, axis=1).sum())


# ---- noisy-OR (Supplement 4.1.3) and Haldane's recombination probability (Supplement 4.1.4)
def noisy_or_p_off(z, theta, leak):
    """p(x=0 | z) = leak * prod_k theta_k^{z_k} (the leak node z_0 is always on)."""
    return leak * np.prod(np.where(np.asarray(z) == 1, theta, 1.0), axis=-1)


def haldane(d):
    """theta(d) = (1 - exp(-2 d)) / 2: probability of an odd number of crossovers over map distance d (Morgans)."""
    return 0.5 * (1.0 - np.exp(-2.0 * np.asarray(d, float)))


# =========================================================================== Gaussian models
def gaussian_bn_moments(W, s, mu):
    """Mean, covariance and precision of the Gaussian Bayes net x = mu + W (x - mu) + diag(s) z (4.12)-(4.16).
    W is strictly lower triangular in a topological order, s the conditional standard deviations."""
    n = len(mu)
    Ui = np.eye(n) - W
    U = np.linalg.inv(Ui)
    S2 = np.diag(np.asarray(s, float) ** 2)
    Sigma = U @ S2 @ U.T
    Lam = Ui.T @ np.diag(1.0 / np.asarray(s, float) ** 2) @ Ui
    return np.asarray(mu, float), Sigma, Lam


def ar1_precision(T, rho, tau=1.0):
    """The tridiagonal precision matrix (4.106) of a stationary AR(1) process x_t = rho x_{t-1} + tau e_t."""
    L = np.zeros((T, T))
    for t in range(T):
        L[t, t] = 1 + rho ** 2
        if t + 1 < T:
            L[t, t + 1] = L[t + 1, t] = -rho
    L[0, 0] = 1.0
    L[-1, -1] = 1.0
    return L / tau ** 2


def ar1_covariance(T, rho, tau=1.0):
    """Sigma_ij = tau^2 rho^|i-j| / (1 - rho^2): the exact inverse of ar1_precision (corrects (4.107))."""
    i = np.arange(T)
    return tau ** 2 * rho ** np.abs(i[:, None] - i[None, :]) / (1 - rho ** 2)


def partial_correlation(Lam):
    """Partial correlations of every pair given all the others: -Lambda_ij / sqrt(Lambda_ii Lambda_jj)."""
    d = np.sqrt(np.diag(Lam))
    R = -Lam / np.outer(d, d)
    np.fill_diagonal(R, 1.0)
    return R


def truncated_normal_var(c, mean=0.0, sd=1.0):
    """Variance of N(mean, sd^2) truncated to (c, inf)."""
    a = (c - mean) / sd
    lam = stats.norm.pdf(a) / stats.norm.sf(a)
    return sd ** 2 * (1 + a * lam - lam ** 2)


def berkson_corr(c):
    """Exact corr(x, y | z > c) in x ~ N(-5,1), y ~ N(5,1), z | x,y ~ N(x+y, 1) (4.25).

    Given z, (x, y) is Gaussian with covariance [[2,-1],[-1,2]]/3 and means shifted by z/3, so by the law of
    total covariance cov(x,y | z>c) = -1/3 + var(z | z>c)/9 and var(x | z>c) = 2/3 + var(z | z>c)/9, with z ~ N(0,3)."""
    v = truncated_normal_var(c, 0.0, np.sqrt(3.0))
    return (-1 / 3 + v / 9) / (2 / 3 + v / 9)


# =========================================================================== Ising and Potts models (Sections 4.3.2.1-4.3.2.2)
def _colour_masks(shape):
    r, c = np.indices(shape)
    m = ((r + c) % 2 == 0)
    return m, ~m


def ising_energy(x, J, h=0.0):
    """E(x) = -J sum_{i~j} x_i x_j - h sum_i x_i (4.78), (4.82) on a periodic lattice (each bond counted once)."""
    return -J * np.sum(x * np.roll(x, 1, 0) + x * np.roll(x, 1, 1)) - h * np.sum(x)


def ising_gibbs(L, J, sweeps, rng, h=0.0, x0=None, record=None):
    """Checkerboard Gibbs sampler for p(x) ~ exp(J sum_{i~j} x_i x_j + h sum_i x_i), x_i = +-1, on an L x L torus.

    L must be even (on an odd torus the wrap-around joins sites of one colour). Sites of one colour have no neighbours of the same
    colour, so they are conditionally independent given the other colour and can be updated together: p(x_i = +1 | rest) = sigma(2 (J sum_{j~i} x_j + h)).
    `record` (a function of x) is evaluated after every sweep and the list of values returned with the final state."""
    x = rng.choice([-1, 1], size=(L, L)) if x0 is None else x0.copy()
    masks = _colour_masks(x.shape)
    vals = []
    for _ in range(sweeps):
        for m in masks:
            s = np.roll(x, 1, 0) + np.roll(x, -1, 0) + np.roll(x, 1, 1) + np.roll(x, -1, 1)
            p = common.sigmoid(2 * (J * s + h))
            x = np.where(m, np.where(rng.random(x.shape) < p, 1, -1), x)
        if record is not None:
            vals.append(record(x))
    return (x, vals) if record is not None else x


def potts_gibbs(L, K, J, sweeps, rng, alpha=None, x0=None):
    """Checkerboard Gibbs sampler for the Potts model p(x) ~ exp(J sum_{i~j} I(x_i = x_j) + sum_i alpha_{x_i}) (4.84), (4.86)."""
    x = rng.integers(0, K, size=(L, L)) if x0 is None else x0.copy()
    al = np.zeros(K) if alpha is None else np.asarray(alpha, float)
    masks = _colour_masks(x.shape)
    nb = lambda a: (np.roll(a, 1, 0), np.roll(a, -1, 0), np.roll(a, 1, 1), np.roll(a, -1, 1))
    for _ in range(sweeps):
        for m in masks:
            nbs = nb(x)
            logits = np.empty((K,) + x.shape)
            for k in range(K):
                logits[k] = J * sum((a == k) for a in nbs) + al[k]
            # Gumbel-max sampling from softmax(logits) at every site
            g = -np.log(-np.log(rng.random(logits.shape)))
            x = np.where(m, np.argmax(logits + g, axis=0), x)
    return x


def ising_exact_small(Lr, Lc, J, h=0.0):
    """Exact log Z, mean energy per site, mean |m| and mean m^2 of the Lr x Lc periodic Ising lattice by enumeration."""
    n = Lr * Lc
    states = ((np.arange(2 ** n)[:, None] >> np.arange(n)[None, :]) & 1) * 2 - 1
    X = states.reshape(-1, Lr, Lc)
    bond = (X * np.roll(X, 1, 1)).sum((1, 2)) + (X * np.roll(X, 1, 2)).sum((1, 2))
    mag = states.sum(1)
    logw = J * bond + h * mag
    lz = special.logsumexp(logw)
    w = np.exp(logw - lz)
    return dict(logZ=float(lz), energy=float((w * (-J * bond - h * mag)).sum() / n),
                abs_m=float((w * np.abs(mag)).sum() / n), m2=float((w * (mag / n) ** 2).sum()), bonds=float((w * bond).sum() / n))


def onsager_critical_J():
    """J_c = (1/2) log(1 + sqrt 2) = 0.4407 for the square-lattice Ising model (4.79), Onsager (1944)."""
    return 0.5 * np.log1p(np.sqrt(2.0))


def onsager_magnetisation(J):
    """Spontaneous magnetisation (1 - sinh(2J)^-4)^(1/8) for J > J_c, 0 otherwise (Onsager 1944, Yang 1952)."""
    J = np.asarray(J, float)
    s = np.sinh(2 * J)
    return np.where(J > onsager_critical_J(), np.clip(1 - s ** -4.0, 0, None) ** 0.125, 0.0)


def potts_critical_J(K):
    return float(np.log1p(np.sqrt(K)))


# =========================================================================== Hopfield networks (Section 4.3.2.4)
def hopfield_weights(P):
    """Outer-product rule (4.90): W = (1/N_patterns) sum_n x_n x_n^T - I for patterns P (rows, entries +-1), dense."""
    P = np.asarray(P, float)
    return P.T @ P / len(P) - np.eye(P.shape[1])


def hopfield_field(P, x):
    """W x for the outer-product weights without forming the N x N matrix: (1/n) P^T (P x) - x."""
    return P.T @ (P @ x) / len(P) - x


def hopfield_sync(P, x0, iters):
    """Synchronous ICM x <- sgn(W x) (4.89); a zero field keeps the current value. Returns the final state and the
    number of pixels that changed at each iteration."""
    x = x0.astype(float).copy()
    ch = []
    for _ in range(iters):
        f = hopfield_field(P, x)
        xn = np.where(f > 0, 1.0, np.where(f < 0, -1.0, x))
        ch.append(int((xn != x).sum()))
        x = xn
    return x, ch


def hopfield_async(W, x0, sweeps, rng):
    """Asynchronous ICM with a dense symmetric W (zero diagonal): one site at a time, in random order. The energy
    E = -x^T W x / 2 never increases. Returns the final state and the energy after each sweep."""
    x = x0.astype(float).copy()
    E = [float(-0.5 * x @ W @ x)]
    for _ in range(sweeps):
        for i in rng.permutation(len(x)):
            f = W[i] @ x
            if f != 0:
                x[i] = 1.0 if f > 0 else -1.0
        E.append(float(-0.5 * x @ W @ x))
    return x, np.array(E)


def smooth_binary_patterns(n_pat, size, seed=0, sigma=9.0):
    """Synthetic binary images (+-1): thresholded smooth Gaussian random fields. They stand in for the photographs of
    Figure 4.19 and are close to orthogonal, so the storage load is the only thing that limits recall."""
    from scipy.ndimage import gaussian_filter
    rng = np.random.default_rng(seed)
    out = []
    for _ in range(n_pat):
        f = gaussian_filter(rng.standard_normal((size, size)), sigma, mode="wrap")
        out.append(np.where(f > np.median(f), 1.0, -1.0))
    return np.array(out)


# =========================================================================== restricted Boltzmann machines (Section 4.3.3.2, Supplement 4.3)
class BinaryRBM:
    """Binary RBM with energy E(x, z) = -(x^T W z + b^T x + c^T z) (Supplement (4.8)-(4.10))."""

    def __init__(self, D, K, rng, scale=0.01):
        self.W = scale * rng.standard_normal((D, K))
        self.b = np.zeros(D)
        self.c = np.zeros(K)
        self.rng = rng

    def p_h(self, X):
        return common.sigmoid(X @ self.W + self.c)        # E[z | x] = sigma(W^T x + c) (4.14)

    def p_v(self, H):
        return common.sigmoid(H @ self.W.T + self.b)      # E[x | z] = sigma(W z + b) (4.15)

    def free_energy(self, X):
        """F(x) = -b^T x - sum_k log(1 + exp(c_k + w_k^T x)); p(x) = exp(-F(x)) / Z."""
        return -(X @ self.b) - np.logaddexp(0.0, X @ self.W + self.c).sum(1)

    def cd1_epoch(self, X, lr, batch, momentum=0.5):
        """One epoch of contrastive divergence with one Gibbs step (CD-1) over the rows of X."""
        rng = self.rng
        order = rng.permutation(len(X))
        vW, vb, vc = (np.zeros_like(self.W), np.zeros_like(self.b), np.zeros_like(self.c))
        for s in range(0, len(X), batch):
            v0 = X[order[s:s + batch]]
            ph0 = self.p_h(v0)
            h0 = (rng.random(ph0.shape) < ph0).astype(float)
            pv1 = self.p_v(h0)
            v1 = (rng.random(pv1.shape) < pv1).astype(float)
            ph1 = self.p_h(v1)
            m = len(v0)
            gW = (v0.T @ ph0 - v1.T @ ph1) / m
            gb = (v0 - v1).mean(0)
            gc = (ph0 - ph1).mean(0)
            vW, vb, vc = momentum * vW + lr * gW, momentum * vb + lr * gb, momentum * vc + lr * gc
            self.W += vW
            self.b += vb
            self.c += vc

    def reconstruct(self, X):
        """Mean-field reconstruction: x -> hidden probabilities (sampled) -> E[x | z]."""
        ph = self.p_h(X)
        h = (self.rng.random(ph.shape) < ph).astype(float)
        return self.p_v(h)


def rbm_logZ_bruteforce(W, b, c):
    """log Z of a small RBM by summing over all visible states and, per state, the hidden units analytically (cost K 2^D D)."""
    D = len(b)
    X = ((np.arange(2 ** D)[:, None] >> np.arange(D)[None, :]) & 1).astype(float)
    return float(special.logsumexp(X @ b + np.logaddexp(0.0, X @ W + c).sum(1)))


def rbm_logZ_over_hidden(W, b, c):
    """The same log Z summing over the 2^K hidden states and factorising over the visible units (cost D 2^K)."""
    K = len(c)
    H = ((np.arange(2 ** K)[:, None] >> np.arange(K)[None, :]) & 1).astype(float)
    return float(special.logsumexp(H @ c + np.logaddexp(0.0, H @ W.T + b).sum(1)))


def rbm_logZ_joint(W, b, c):
    """log Z by brute force over (x, z) jointly (cost 2^(D+K))."""
    D, K = W.shape
    X = ((np.arange(2 ** D)[:, None] >> np.arange(D)[None, :]) & 1).astype(float)
    H = ((np.arange(2 ** K)[:, None] >> np.arange(K)[None, :]) & 1).astype(float)
    return float(special.logsumexp((X @ W @ H.T) + (X @ b)[:, None] + (H @ c)[None, :]))


# =========================================================================== Gaussian MRF, log-linear MRFs, pseudolikelihood, mean field
def gaussian_mrf_logZ(Lam, eta):
    """log Z of exp(eta^T x - x^T Lam x / 2): (D/2) log 2 pi - (1/2) log|Lam| + (1/2) eta^T Lam^{-1} eta.
    (Eq. (4.104) in the book is this with eta = 0.)"""
    D = len(eta)
    sign, ld = np.linalg.slogdet(Lam)
    return 0.5 * D * np.log(2 * np.pi) - 0.5 * ld + 0.5 * eta @ np.linalg.solve(Lam, eta)


class LogLinearMRF:
    """p(x) = exp(theta^T phi(x)) / Z(theta) on {0,1}^n (or +-1) by exhaustive enumeration, for exact checks."""

    def __init__(self, n, phi, spins=False):
        S = ((np.arange(2 ** n)[:, None] >> np.arange(n)[None, :]) & 1).astype(float)
        self.states = S * 2 - 1 if spins else S
        self.Phi = np.array([phi(s) for s in self.states])           # 2^n x d

    def logZ(self, th):
        return float(special.logsumexp(self.Phi @ th))

    def probs(self, th):
        a = self.Phi @ th
        return np.exp(a - special.logsumexp(a))

    def mean_phi(self, th):
        return self.probs(th).T @ self.Phi

    def cov_phi(self, th):
        p = self.probs(th)
        m = p @ self.Phi
        return (self.Phi * p[:, None]).T @ self.Phi - np.outer(m, m)

    def loglik(self, th, mean_phi_data):
        return float(mean_phi_data @ th - self.logZ(th))

    def fit(self, mean_phi_data, iters=60, th0=None):
        """Maximum likelihood by Newton's method: gradient (4.122), Hessian = -cov(phi) (concave objective)."""
        th = np.zeros(self.Phi.shape[1]) if th0 is None else th0.copy()
        for _ in range(iters):
            g = mean_phi_data - self.mean_phi(th)
            H = self.cov_phi(th) + 1e-12 * np.eye(len(th))
            th = th + np.linalg.solve(H, g)
            if np.linalg.norm(g) < 1e-13:
                break
        return th


def ipf(table_shape, cliques, targets, iters=20):
    """Iterative proportional fitting: start from the uniform table and rescale, clique by clique, so that its
    marginal on each clique equals the target marginal (the moment-matching equations (4.123) for tabular potentials)."""
    p = np.full(table_shape, 1.0 / np.prod(table_shape))
    n = len(table_shape)
    hist = []
    for _ in range(iters):
        for cl, tgt in zip(cliques, targets):
            other = tuple(i for i in range(n) if i not in cl)
            cur = p.sum(axis=other, keepdims=True)
            tg = tgt.reshape([table_shape[i] if i in cl else 1 for i in range(n)])
            with np.errstate(divide="ignore", invalid="ignore"):
                p = p * np.where(cur > 0, tg / cur, 0.0)
        hist.append(p.copy())
    return p, hist


def ising_pseudolik(J, X, edges_nbrs):
    """Mean log pseudolikelihood (4.127) of a pairwise Ising model with a single coupling J on graph neighbours
    edges_nbrs[d] (list of neighbour indices): log p(x_d | x_-d) = x_d a_d - log 2cosh(a_d), a_d = J sum_nbr x_j."""
    tot = 0.0
    for d, nb in enumerate(edges_nbrs):
        a = J * X[:, nb].sum(1)
        tot += np.mean(X[:, d] * a - np.logaddexp(a, -a))
    return tot


def mean_field_ising_denoise(y, J, sigma, sweeps, mu0=None):
    """Coordinate-ascent mean field for the posterior of an Ising prior (coupling J, 4-neighbour torus) with Gaussian
    evidence y_i ~ N(z_i, sigma^2), z_i = +-1 (4.117): mu_i <- tanh(J sum_{j~i} mu_j + y_i / sigma^2).
    Sites of one checkerboard colour are updated together (coordinate ascent on the ELBO). Returns mu after each sweep."""
    mu = np.zeros_like(y) if mu0 is None else mu0.copy()
    masks = _colour_masks(y.shape)
    out = []
    for _ in range(sweeps):
        for m in masks:
            s = np.roll(mu, 1, 0) + np.roll(mu, -1, 0) + np.roll(mu, 1, 1) + np.roll(mu, -1, 1)
            mu = np.where(m, np.tanh(J * s + y / sigma ** 2), mu)
        out.append(mu.copy())
    return out


def ising_denoise_gibbs(y, J, sigma, sweeps, burn, rng):
    """Posterior mean of the same model by Gibbs sampling: p(z_i = +1 | rest) = sigma(2 (J sum z_j + y_i / sigma^2))."""
    L = y.shape[0]
    z = np.where(y > 0, 1, -1)
    masks = _colour_masks(y.shape)
    acc = np.zeros(y.shape)
    for t in range(sweeps):
        for m in masks:
            s = np.roll(z, 1, 0) + np.roll(z, -1, 0) + np.roll(z, 1, 1) + np.roll(z, -1, 1)
            p = common.sigmoid(2 * (J * s + y / sigma ** 2))
            z = np.where(m, np.where(rng.random(y.shape) < p, 1, -1), z)
        if t >= burn:
            acc += z
    return acc / (sweeps - burn)


def denoise_problem(L=64, sigma=2.0, seed=4):
    """A clean +-1 image (a ring, a bar and a block) on an L x L grid and its noisy version y = z + sigma * noise."""
    rng = np.random.default_rng(seed)
    r, c = np.indices((L, L))
    z = -np.ones((L, L))
    d = np.hypot(r - 0.38 * L, c - 0.36 * L)
    z[(d < 0.27 * L) & (d > 0.15 * L)] = 1
    z[int(0.62 * L):int(0.9 * L), int(0.5 * L):int(0.58 * L)] = 1
    z[int(0.7 * L):int(0.9 * L), int(0.7 * L):int(0.92 * L)] = 1
    y = np.round(z + sigma * rng.standard_normal((L, L)), 4)
    return z, y


# =========================================================================== conditional random fields (Section 4.4)
def chain_crf_logZ(node, edge):
    """log Z(x) of a chain CRF (4.138): node is T x K (log node potentials), edge is K x K (log edge potentials),
    by the forward algorithm in O(T K^2)."""
    a = node[0].copy()
    for t in range(1, len(node)):
        a = node[t] + special.logsumexp(a[:, None] + edge, axis=0)
    return float(special.logsumexp(a))


def chain_crf_marginals(node, edge):
    """Posterior marginals p(y_t | x) by forward-backward; returns T x K."""
    T, K = node.shape
    al = np.zeros((T, K))
    be = np.zeros((T, K))
    al[0] = node[0]
    for t in range(1, T):
        al[t] = node[t] + special.logsumexp(al[t - 1][:, None] + edge, axis=0)
    for t in range(T - 2, -1, -1):
        be[t] = special.logsumexp(edge + (node[t + 1] + be[t + 1])[None, :], axis=1)
    lg = al + be
    return np.exp(lg - special.logsumexp(lg, axis=1, keepdims=True))


def chain_crf_viterbi(node, edge):
    T, K = node.shape
    dl = node[0].copy()
    bp = np.zeros((T, K), int)
    for t in range(1, T):
        sc = dl[:, None] + edge
        bp[t] = sc.argmax(0)
        dl = node[t] + sc.max(0)
    path = [int(dl.argmax())]
    for t in range(T - 1, 0, -1):
        path.append(int(bp[t][path[-1]]))
    return path[::-1], float(dl.max())


def memm_marginal_first(node, edge):
    """Posterior p(y_1 | x) of the locally normalised chain (MEMM, (4.139)) whose conditionals are the softmax of the
    same scores: p(y_1 | x_1) ~ exp(node[0]) and p(y_t | y_{t-1}, x_t) ~ exp(node[t, y_t] + edge[y_{t-1}, y_t]). Because every
    conditional sums to one the later observations cannot change p(y_1 | x)."""
    p = special.softmax(node[0])
    return p


def memm_joint_log(node, edge, y):
    lp = np.log(special.softmax(node[0]))[y[0]]
    for t in range(1, len(y)):
        lp += special.log_softmax(node[t] + edge[y[t - 1]])[y[t]]
    return float(lp)


# =========================================================================== Markov logic network (Section 4.6.4.2)
def mln_two_people(w1, w2):
    """Distribution (4.182) over the 2^8 worlds of the smoking example with weights w1 (Sm => Ca) and w2
    (Fr(x,y) & Sm(x) => Sm(y)). Atoms: Fr(A,A), Fr(A,B), Fr(B,A), Fr(B,B), Sm(A), Sm(B), Ca(A), Ca(B).
    Returns (worlds, probs, n1, n2) with n_i the number of true groundings of clause i."""
    W = ((np.arange(256)[:, None] >> np.arange(8)[None, :]) & 1).astype(int)
    fr = W[:, :4].reshape(-1, 2, 2)      # fr[w, x, y]
    sm = W[:, 4:6]
    ca = W[:, 6:8]
    n1 = ((1 - sm) | ca).sum(1)
    n2 = np.zeros(256, int)
    for x in range(2):
        for y in range(2):
            n2 += ((1 - fr[:, x, y]) | (1 - sm[:, x]) | sm[:, y])
    a = w1 * n1 + w2 * n2
    p = np.exp(a - special.logsumexp(a))
    return W, p, n1, n2


# =========================================================================== structural causal models (Section 4.7)
def education_sem(n, rng, params=None, do_z=None):
    """The education example (4.186)-(4.188): X = Ux, Z = cz + wxz X + Uz, Y = cy + wxy X + wzy Z + Uy with Gaussian noise.
    With do_z not None the mechanism of Z is replaced by Z = do_z (graph surgery)."""
    q = dict(mux=1.0, sx=1.0, cz=0.0, wxz=1.5, sz=0.5, cy=1.0, wxy=2.0, wzy=-1.0, sy=0.5)
    if params:
        q.update(params)
    X = q["mux"] + q["sx"] * rng.standard_normal(n)
    Z = q["cz"] + q["wxz"] * X + q["sz"] * rng.standard_normal(n) if do_z is None else np.full(n, float(do_z))
    Y = q["cy"] + q["wxy"] * X + q["wzy"] * Z + q["sy"] * rng.standard_normal(n)
    return X, Z, Y, q


def counterfactual_monotone(p0, p1):
    """P(Y^0 = 1 | A = 1, Y = 1) in the SCM Y^a = 1[U < p_a], U ~ Unif(0,1) (monotone coupling)."""
    return min(1.0, p0 / p1)


def counterfactual_antitone(p0, p1):
    """The same probability in the SCM Y^0 = 1[U > 1 - p0], Y^1 = 1[U < p1] (antitone coupling): same p(Y^a), different answer."""
    return max(0.0, p0 + p1 - 1.0) / p1


# =========================================================================== drawing helpers
def _draw_graph(ax, pos, directed=(), undirected=(), dashed=(), colors=None, node_r=0.16, fs=9, labels=None, shade=()):
    """Draw nodes as circles, directed edges as arrows, undirected edges as lines (dashed ones in red)."""
    from matplotlib.patches import Circle
    colors = colors or {}
    for (a, b) in undirected:
        (x0, y0), (x1, y1) = pos[a], pos[b]
        dash = (a, b) in dashed or (b, a) in dashed
        ax.plot([x0, x1], [y0, y1], color=RED if dash else "k", lw=1.1, ls="--" if dash else "-", zorder=1)
    for (a, b) in directed:
        (x0, y0), (x1, y1) = np.array(pos[a], float), np.array(pos[b], float)
        d = np.array([x1 - x0, y1 - y0])
        d = d / np.hypot(*d)
        ax.annotate("", xy=(x1 - d[0] * node_r, y1 - d[1] * node_r), xytext=(x0 + d[0] * node_r, y0 + d[1] * node_r),
                    arrowprops=dict(arrowstyle="-|>", color="k", lw=1.1, shrinkA=0, shrinkB=0, mutation_scale=9), zorder=1)
    for v, (x, y) in pos.items():
        ax.add_patch(Circle((x, y), node_r, fc=("#cfd8e6" if v in shade else colors.get(v, "white")), ec="k", lw=1.0, zorder=3))
        ax.text(x, y, (labels or {}).get(v, str(v)), ha="center", va="center", fontsize=fs, zorder=4)
    xs, ys = zip(*pos.values())
    ax.set_xlim(min(xs) - 0.5, max(xs) + 0.5)
    ax.set_ylim(min(ys) - 0.5, max(ys) + 0.5)
    ax.set_aspect("equal")
    ax.axis("off")


def _dag_edges(dag):
    return [(p, v) for v, ps in dag.items() for p in ps]


def _ug_edges(ug):
    return sorted({tuple(sorted((a, b))) for a, nb in ug.items() for b in nb})


# the 7-node DAG of Figure 4.23 (read off the figure and checked against the text: nd(3) = {1,2,4}, mb(5) = {2,3,4,6,7})
DAG_4_23 = {1: [], 2: [1], 3: [1], 4: [2], 5: [2, 3], 6: [3, 5], 7: [4, 5, 6]}
POS_4_23 = {1: (0, 0.5), 2: (1, 1), 3: (1, 0), 4: (2.1, 1), 5: (2.5, 0.5), 6: (2.1, 0), 7: (3.5, 0.5)}

DAG_STUDENT_FULL = {"C": [], "D": ["C"], "I": [], "G": ["I", "D"], "S": ["I"], "L": ["G"], "J": ["L", "S"], "H": ["G", "J"]}
POS_STUDENT_FULL = {"C": (0, 3), "D": (0, 2), "I": (2, 3), "S": (3.2, 2), "G": (1, 1.4), "L": (0, 0.4), "J": (2.2, 0.7), "H": (1, -0.4)}


# =========================================================================== figures
def fig_4_6(out=None):
    """Berkson's paradox in x ~ N(-5,1), y ~ N(5,1), z | x,y ~ N(x+y,1): unconditional and conditional on z > 2.5."""
    rng = np.random.default_rng(0)
    n = 1000
    x = rng.normal(-5, 1, n)
    y = rng.normal(5, 1, n)
    z = rng.normal(x + y, 1)
    sel = z > 2.5
    fig, axes = common.panel_grid(2, 2, size=(3.5, 2.8))
    for ax, (xs, ys, zs), lab in ((axes[0, 0], (x, y, z), "a"), (axes[1, 0], (x[sel], y[sel], z[sel]), "c")):
        bins = np.linspace(-9, 9, 37)
        for v, col, nm in ((xs, RED, "x"), (ys, BLUE, "y"), (zs, GREEN, "z")):
            ax.hist(v, bins=bins, color=col, alpha=0.6, label=nm)
        ax.set_xlabel("value")
        ax.set_ylabel("number of samples")
        ax.legend(loc="upper left", fontsize=8)
        common.panel_label(ax, lab, "upper right")
    for ax, xs, ys, lab in ((axes[0, 1], x, y, "b"), (axes[1, 1], x[sel], y[sel], "d")):
        ax.scatter(xs, ys, s=6, color=MAGENTA, alpha=0.6, lw=0)
        ax.set_xlim(-9, -1)
        ax.set_ylim(1, 9)
        ax.set_xlabel("x")
        ax.set_ylabel("y")
        r = np.corrcoef(xs, ys)[0, 1]
        ax.set_title("sample correlation %.2f" % r, fontsize=9)
        common.panel_label(ax, lab, "upper right")
    axes[0, 0].set_title("unconditional", fontsize=9)
    axes[1, 0].set_title("conditional on $z>2.5$ (%d samples)" % sel.sum(), fontsize=9)
    fig.tight_layout()
    savefig(fig, CH, "fig4-6", out)


def student_posterior_panels(bn):
    """Posterior marginals for the two evidence sets of Figure 4.8: {G=C} and {G=C, S=Good}."""
    return [{v: bn.marginal(v, ev) for v in bn.nodes} for ev in ({"G": 2}, {"G": 2, "S": 1})]


def fig_4_8(out=None):
    """Belief updating in the student network: posterior marginals after observing Grade = C, then also SAT = Good."""
    bn = student_bn()
    panels = student_posterior_panels(bn)
    evs = [{"G"}, {"G", "S"}]
    names = dict(D="Diff", I="Intel", G="Grade", S="SAT", L="Letter")
    fig, axes = common.panel_grid(2, 5, size=(1.6, 1.9))
    for r in range(2):
        for c, v in enumerate(bn.nodes):
            ax = axes[r, c]
            p = panels[r][v]
            col = ORANGE if v in evs[r] else BLUE
            ax.bar(range(len(p)), p, color=col, width=0.7)
            ax.set_ylim(0, 1.18)
            ax.set_xticks(range(len(p)))
            ax.set_xticklabels(STUDENT_STATES[v], fontsize=8)
            ax.set_yticks([0, 0.5, 1])
            for k, pk in enumerate(p):
                ax.text(k, pk + 0.03, "%.2f" % pk, ha="center", fontsize=7)
            ax.set_title(names[v], fontsize=9, fontweight="bold" if v in evs[r] else "normal")
            if c:
                ax.set_yticklabels([])
        axes[r, 0].set_ylabel("(%s)" % "ab"[r], rotation=0, labelpad=12, fontsize=10)
    fig.tight_layout()
    savefig(fig, CH, "fig4-8", out)


def _show_binary(ax, x, title=None):
    ax.imshow(x, cmap="gray", vmin=-1, vmax=1, interpolation="nearest", rasterized=True)
    ax.set_xticks([])
    ax.set_yticks([])
    if title:
        ax.set_title(title, fontsize=9)


def fig_4_17(out=None):
    """Samples from a 100 x 100 associative Ising model for J = 0.2, 0.4, 10 (checkerboard Gibbs sampling)."""
    rng = np.random.default_rng(1)
    fig, axes = common.panel_grid(1, 3, size=(2.7, 2.9))
    for ax, J, lab in zip(axes[0], (0.2, 0.4, 10.0), "abc"):
        x = ising_gibbs(100, J, 500, rng)
        _show_binary(ax, x, "$J=%g$" % J)
        common.panel_label(ax, lab, "upper right")
    fig.tight_layout()
    savefig(fig, CH, "fig4-17", out)


def fig_4_18(out=None):
    """Samples from a 10-state Potts model on a 128 x 128 lattice just below, at and just above J_c = log(1 + sqrt 10) = 1.426."""
    rng = np.random.default_rng(2)
    fig, axes = common.panel_grid(1, 3, size=(2.9, 3.0))
    for ax, J, lab in zip(axes[0], (1.40, 1.43, 1.46), "abc"):
        x = potts_gibbs(128, 10, J, 600, rng)
        ax.imshow(x, cmap="tab10", interpolation="nearest", rasterized=True)
        ax.set_xticks([])
        ax.set_yticks([])
        ax.set_title("$J=%.2f$" % J, fontsize=9)
        common.panel_label(ax, lab, "upper right")
    fig.tight_layout()
    savefig(fig, CH, "fig4-18", out)


def hopfield_experiment(size=150, n_pat=3, seed=1, iters=30):
    P = smooth_binary_patterns(n_pat, size, seed)
    flat = P.reshape(n_pat, -1)
    occl = []
    for k in range(n_pat):
        x0 = P[k].copy()
        if k == 0:
            x0[:, : size // 2] = -1                      # left half hidden
        elif k == 1:
            keep = np.zeros_like(x0, bool)
            keep[int(0.2 * size):int(0.8 * size), int(0.3 * size):int(0.8 * size)] = True
            x0 = np.where(keep, x0, -1)                  # only a window visible
        else:
            x0[:, size // 2:] = -1                       # right half hidden
        occl.append(x0)
    rec = [hopfield_sync(flat, o.ravel(), iters)[0].reshape(size, size) for o in occl]
    return P, np.array(occl), np.array(rec)


def fig_4_19(out=None):
    """Associative memory: three stored 150 x 150 binary images, partially visible inputs, and the state after 30 ICM iterations."""
    P, occl, rec = hopfield_experiment()
    fig, axes = common.panel_grid(3, 3, size=(2.0, 2.0))
    for c in range(3):
        _show_binary(axes[0, c], P[c], "stored image %d" % (c + 1))
        _show_binary(axes[1, c], occl[c], "partial input")
        ov = float((rec[c] * P[c]).mean())
        _show_binary(axes[2, c], rec[c], "recalled (overlap %.3f)" % ov)
    fig.tight_layout()
    savefig(fig, CH, "fig4-19", out)


def rbm_experiment(hidden=100, epochs=5, seed=0, n_show=10):
    X, _ = common.mnist(True)
    Xt, yt = common.mnist(False)
    Xb, Xtb = (X > 0.5).astype(float), (Xt > 0.5).astype(float)
    rng = np.random.default_rng(seed)
    rbm = BinaryRBM(784, hidden, rng)
    show = Xtb[:n_show]
    stages = {"initial": rbm.reconstruct(show)}
    err = [float(((rbm.p_v(rbm.p_h(Xtb[:2000])) - Xtb[:2000]) ** 2).mean())]
    for ep in range(epochs):
        rbm.cd1_epoch(Xb, 0.05, 100)
        err.append(float(((rbm.p_v(rbm.p_h(Xtb[:2000])) - Xtb[:2000]) ** 2).mean()))
        if ep in (0, epochs - 1):
            stages["epoch %d" % (ep + 1)] = rbm.reconstruct(show)
    return show, stages, err, rbm


def fig_4_21(out=None):
    """Binary RBM (100 hidden units) trained by CD-1 on binarised MNIST: reconstructions of test digits at initialisation, epoch 1 and epoch 5."""
    show, stages, err, _ = rbm_experiment()
    rows = [("test digits", show)] + list(stages.items())
    n = len(show)
    fig, axes = common.panel_grid(len(rows), n, size=(0.9, 0.95))
    for r, (nm, imgs) in enumerate(rows):
        for c in range(n):
            ax = axes[r, c]
            ax.imshow(imgs[c].reshape(28, 28), cmap="gray_r", vmin=0, vmax=1, rasterized=True)
            ax.set_xticks([])
            ax.set_yticks([])
            for s in ax.spines.values():
                s.set_visible(False)
        axes[r, 0].set_ylabel(nm, rotation=0, ha="right", va="center", fontsize=9)
    fig.tight_layout(h_pad=0.2, w_pad=0.1)
    savefig(fig, CH, "fig4-21", out)


def fig_4_23(out=None):
    """A DAG and its moralised undirected graph (7 nodes); X_1,X_2 are separated from X_6,X_7 by {X_3,X_4,X_5}."""
    ug = moralize(DAG_4_23)
    moral = {(a, b) for a, b in _ug_edges(ug)} - {tuple(sorted(e)) for e in _dag_edges(DAG_4_23)}
    fig, axes = common.panel_grid(1, 2, size=(3.4, 2.4))
    _draw_graph(axes[0, 0], POS_4_23, directed=_dag_edges(DAG_4_23))
    _draw_graph(axes[0, 1], POS_4_23, undirected=_ug_edges(ug), dashed=moral)
    axes[0, 0].set_title("(a) DAG", fontsize=9)
    axes[0, 1].set_title("(b) moral graph (added edges dashed)", fontsize=9)
    fig.tight_layout()
    savefig(fig, CH, "fig4-23", out)


def fig_4_25(out=None):
    """The ancestral graph of Figure 4.23(a) for U = {X2, X4, X5} and its moral graph: now X4 and X5 are separated by X2."""
    U = [2, 4, 5]
    anc = ancestral_graph(DAG_4_23, U)
    pos = {v: POS_4_23[v] for v in anc}
    ug = moralize(anc)
    added = {tuple(sorted(e)) for e in _ug_edges(ug)} - {tuple(sorted(e)) for e in _dag_edges(anc)}
    fig, axes = common.panel_grid(1, 2, size=(3.0, 2.3))
    _draw_graph(axes[0, 0], pos, directed=_dag_edges(anc), shade=U)
    _draw_graph(axes[0, 1], pos, undirected=_ug_edges(ug), dashed=added, shade=U)
    axes[0, 0].set_title("(a) ancestral graph of {2,4,5}", fontsize=9)
    axes[0, 1].set_title("(b) its moral graph", fontsize=9)
    fig.tight_layout()
    savefig(fig, CH, "fig4-25", out)


def fig_4_37(out=None):
    """A 4-cycle UPGM and two DAGs that fail to represent it: the independence statements each graph asserts, computed by separation / d-separation."""
    pos = {"A": (0, 1), "B": (1, 1), "C": (1, 0), "D": (0, 0)}
    ug = {"A": {"B", "D"}, "B": {"A", "C"}, "C": {"B", "D"}, "D": {"A", "C"}}
    dag_b = {"A": [], "B": ["A"], "D": ["A"], "C": ["B", "D"]}
    dag_c = {"B": [], "D": [], "A": ["B", "D"], "C": ["B", "D"]}

    def stm(items):
        return ["%s _||_ %s | %s" % (x, y, ",".join(z) if z else "-") for x, y, z in items]
    ci_u = [(x, y, tuple(sorted(Z))) for x, y in itertools.combinations(sorted(ug), 2)
            for r in range(3) for Z in itertools.combinations([v for v in sorted(ug) if v not in (x, y)], r) if separated(ug, [x], [y], Z)]
    sets = [ci_u, ci_statements(dag_b), ci_statements(dag_c)]
    fig, axes = common.panel_grid(1, 3, size=(2.9, 3.0))
    _draw_graph(axes[0, 0], pos, undirected=_ug_edges(ug))
    _draw_graph(axes[0, 1], pos, directed=_dag_edges(dag_b))
    _draw_graph(axes[0, 2], pos, directed=_dag_edges(dag_c))
    for ax, s, ttl in zip(axes[0], sets, ("(a) UPGM", "(b) DAG, wrong", "(c) DAG, wrong")):
        ax.set_title(ttl, fontsize=9)
        txt = "\n".join(t.replace("_||_", r"$\perp$") for t in stm(s))
        ax.text(0.5, 0.0, txt, transform=ax.transAxes, ha="center", va="top", fontsize=8)
    fig.tight_layout()
    savefig(fig, CH, "fig4-37", out)


def fig_4_38(out=None):
    """The full student DAG (8 nodes) and its moral graph; moralisation adds the edges D-I, G-J and L-S."""
    ug = moralize(DAG_STUDENT_FULL)
    added = {tuple(sorted(e)) for e in _ug_edges(ug)} - {tuple(sorted(e)) for e in _dag_edges(DAG_STUDENT_FULL)}
    fig, axes = common.panel_grid(1, 2, size=(3.4, 3.2))
    _draw_graph(axes[0, 0], POS_STUDENT_FULL, directed=_dag_edges(DAG_STUDENT_FULL), node_r=0.2)
    _draw_graph(axes[0, 1], POS_STUDENT_FULL, undirected=_ug_edges(ug), dashed=added, node_r=0.2)
    axes[0, 0].set_title("(a) DPGM", fontsize=9)
    axes[0, 1].set_title("(b) UPGM (moralisation arcs dashed)", fontsize=9)
    fig.tight_layout()
    savefig(fig, CH, "fig4-38", out)


VAR_A1 = np.array([[3 / 5, 0, 1 / 5, 0, 0], [0, 3 / 5, 0, -1 / 5, 0], [2 / 5, 1 / 3, 3 / 5, 0, 0],
                   [0, 0, 0, -1 / 2, 1 / 5], [0, 0, 1 / 5, 0, 2 / 5]])
VAR_A2 = np.array([[0, 0, -1 / 5, 0, 0], [0] * 5, [0] * 5, [0, 0, 1 / 5, 0, 1 / 3], [0, 0, 0, 0, -1 / 5]])
VAR_SIGMA = np.array([[1, 1 / 2, 1 / 3, 0, 0], [1 / 2, 1, -1 / 3, 0, 0], [1 / 3, -1 / 3, 1, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, 0, 1]])


def fig_4_44(out=None):
    """A VAR(2) process as a dynamic chain graph: arcs from the non-zeros of A1, A2; undirected edges from the non-zeros of Sigma^-1."""
    Lam = np.linalg.inv(VAR_SIGMA)
    T = 4
    pos = {(t, i): (t * 1.6, 4 - i) for t in range(T) for i in range(5)}
    fig, ax = plt.subplots(figsize=(7.2, 3.4))
    for t in range(T):
        for i in range(5):
            for j in range(i + 1, 5):
                if abs(Lam[i, j]) > 1e-9:
                    x = t * 1.6
                    ax.plot([x + 0.55, x + 0.55 + 0.0], [4 - i, 4 - j], color=RED, lw=1.2, alpha=0.0)
                    ax.annotate("", xy=(x + 0.3, 4 - j), xytext=(x + 0.3, 4 - i),
                                arrowprops=dict(arrowstyle="-", color=RED, lw=1.3, connectionstyle="arc3,rad=-0.55"), zorder=2)
    for A, lag, col in ((VAR_A1, 1, "0.35"), (VAR_A2, 2, GREEN)):
        for i in range(5):
            for j in range(5):
                if A[i, j] != 0:
                    for t in range(lag, T):
                        ax.annotate("", xy=(t * 1.6 - 0.16, 4 - i), xytext=((t - lag) * 1.6 + 0.16, 4 - j),
                                    arrowprops=dict(arrowstyle="-|>", color=col, lw=0.8, shrinkA=0, shrinkB=0, mutation_scale=7), zorder=1)
    for (t, i), (x, y) in pos.items():
        ax.add_patch(plt.Circle((x, y), 0.15, fc="white", ec="k", lw=0.9, zorder=3))
    for t in range(T):
        ax.text(t * 1.6, -0.55, "t-%d" % (T - 1 - t) if t < T - 1 else "t", ha="center", fontsize=9)
    for i in range(5):
        ax.text(-0.45, 4 - i, str(i + 1), ha="center", va="center", fontsize=9)
    ax.set_xlim(-0.7, 5.2)
    ax.set_ylim(-0.9, 4.5)
    ax.set_aspect("equal")
    ax.axis("off")
    ax.set_title("grey: lag-1 arcs (A1), green: lag-2 arcs (A2), red: non-zeros of $\\Sigma^{-1}$ within a slice", fontsize=8.5)
    fig.tight_layout()
    savefig(fig, CH, "fig4-44", out)


def fig_4_27(out=None):
    """Image denoising with an Ising prior (J = 1) and Gaussian noise (sigma = 2) by mean field inference: noisy image, mean after 15 sweeps, clean image."""
    z, y = denoise_problem()
    mus = mean_field_ising_denoise(y, 1.0, 2.0, 15)
    fig, axes = common.panel_grid(1, 3, size=(2.7, 2.7))
    for ax, img, ttl, lab, vm in ((axes[0, 0], y, "noisy image", "a", 5), (axes[0, 1], mus[-1], "mean after 15 sweeps", "b", 1), (axes[0, 2], z, "clean image", "c", 1)):
        im = ax.imshow(img, cmap="gray", vmin=-vm, vmax=vm, interpolation="nearest", rasterized=True)
        ax.set_xticks([])
        ax.set_yticks([])
        ax.set_title("(%s) %s" % (lab, ttl), fontsize=9)
    fig.tight_layout()
    savefig(fig, CH, "fig4-27", out)


def fig_4_S1(out=None):
    """AR(1) precision matrix (sparse, tridiagonal) and its exact inverse (dense), T = 7, rho = 0.6, tau = 1."""
    T, rho = 7, 0.6
    L = ar1_precision(T, rho)
    S = np.linalg.inv(L)
    fig, axes = common.panel_grid(1, 2, size=(3.4, 3.1))
    for ax, M, ttl, fmt in ((axes[0, 0], L, "precision $\\Lambda$ (4.106)", "%.2f"), (axes[0, 1], S, "covariance $\\Lambda^{-1}$", "%.2f")):
        ax.imshow(M, cmap="RdBu_r", vmin=-np.abs(M).max(), vmax=np.abs(M).max())
        for i in range(T):
            for j in range(T):
                ax.text(j, i, fmt % M[i, j], ha="center", va="center", fontsize=6.5, color="k" if abs(M[i, j]) < 0.6 * np.abs(M).max() else "white")
        ax.set_xticks(range(T))
        ax.set_xticklabels(range(1, T + 1))
        ax.set_yticks(range(T))
        ax.set_yticklabels(range(1, T + 1))
        ax.set_title(ttl, fontsize=9)
    fig.tight_layout()
    savefig(fig, CH, "fig4-S1", out)


def fig_4_S2(out=None):
    """Mean |magnetisation| of the 2-D Ising model against J: Gibbs estimates on a 32 x 32 torus and Onsager's exact infinite-lattice curve."""
    rng = np.random.default_rng(3)
    Js = np.round(np.arange(0.20, 0.8001, 0.04), 3)
    L = 32
    ms = []
    for J in Js:
        x0 = np.ones((L, L)) if J > 0.44 else None
        _, vals = ising_gibbs(L, J, 1500, rng, x0=x0, record=lambda x: abs(x.mean()))
        ms.append(np.mean(vals[500:]))
    Jg = np.linspace(0.2, 0.8, 300)
    fig, ax = plt.subplots(figsize=(4.4, 3.2))
    ax.plot(Jg, onsager_magnetisation(Jg), color=BLUE, label="Onsager, infinite lattice")
    ax.plot(Js, ms, "o", color=RED, ms=4, label="Gibbs, $32\\times32$ torus")
    ax.axvline(onsager_critical_J(), color=GREY, ls="--", lw=1)
    ax.text(onsager_critical_J() - 0.01, 0.55, "$J_c=0.4407$", fontsize=8, color=GREY, ha="right")
    ax.set_xlabel("coupling $J$")
    ax.set_ylabel("mean $|m|$")
    ax.legend(fontsize=8, loc="lower right")
    fig.tight_layout()
    savefig(fig, CH, "fig4-S2", out)


LABEL_BIAS = dict(node1=np.array([0.0, 0.0]), edge=np.array([[2.0, 0.0], [0.0, 2.0]]),
                  contexts={"later word favours tag 0": np.array([3.0, 0.0]), "later word favours tag 1": np.array([0.0, 3.0])})


def label_bias_numbers():
    out = {}
    for nm, n2 in LABEL_BIAS["contexts"].items():
        node = np.stack([LABEL_BIAS["node1"], n2])
        out[nm] = dict(crf=float(chain_crf_marginals(node, LABEL_BIAS["edge"])[0, 0]), memm=float(memm_marginal_first(node, LABEL_BIAS["edge"])[0]))
    return out


def fig_4_S3(out=None):
    """Label bias: posterior probability of tag 0 at position 1 in a CRF and in a locally normalised MEMM when the second observation changes."""
    nums = label_bias_numbers()
    fig, ax = plt.subplots(figsize=(4.6, 3.0))
    w = 0.35
    for k, (nm, v) in enumerate(nums.items()):
        ax.bar(k - w / 2, v["crf"], w, color=BLUE, label="CRF (global normalisation)" if k == 0 else None)
        ax.bar(k + w / 2, v["memm"], w, color=ORANGE, label="MEMM (local normalisation)" if k == 0 else None)
        ax.text(k - w / 2, v["crf"] + 0.02, "%.3f" % v["crf"], ha="center", fontsize=8)
        ax.text(k + w / 2, v["memm"] + 0.02, "%.3f" % v["memm"], ha="center", fontsize=8)
    ax.set_xticks(range(len(nums)))
    ax.set_xticklabels(list(nums), fontsize=8)
    ax.set_ylabel("$p(y_1 = 0\\,|\\,x_1, x_2)$")
    ax.set_ylim(0, 1.1)
    ax.legend(fontsize=8, loc="upper left")
    fig.tight_layout()
    savefig(fig, CH, "fig4-S3", out)


def fig_4_S4(out=None):
    """Seeing against doing in the education SEM (4.186)-(4.188): regression of Y on Z in observational data against the mean of Y under do(Z = z)."""
    rng = np.random.default_rng(5)
    X, Z, Y, q = education_sem(400, rng)
    b_obs = np.polyfit(Z, Y, 1)
    zg = np.linspace(Z.min(), Z.max(), 50)
    fig, ax = plt.subplots(figsize=(4.6, 3.3))
    ax.scatter(Z, Y, s=7, color=GREY, alpha=0.6, lw=0, label="observational data")
    ax.plot(zg, np.polyval(b_obs, zg), color=RED, label="$E[Y|Z=z]$, slope %.2f" % b_obs[0])
    ax.plot(zg, q["cy"] + q["wxy"] * q["mux"] + q["wzy"] * zg, color=BLUE, label="$E[Y|do(Z=z)]$, slope %.2f" % q["wzy"])
    ax.set_xlabel("debt $Z$")
    ax.set_ylabel("wealth $Y$")
    ax.legend(fontsize=8, loc="upper right")
    fig.tight_layout()
    savefig(fig, CH, "fig4-S4", out)


def hopfield_load_curve(N=800, loads=None, trials=6, flip=0.1, iters=25, seed=7):
    rng = np.random.default_rng(seed)
    loads = np.arange(0.02, 0.341, 0.02) if loads is None else loads
    res = []
    for a in loads:
        P = max(1, int(round(a * N)))
        ov = []
        for _ in range(trials):
            pats = rng.choice([-1.0, 1.0], size=(P, N))
            x0 = pats[0] * np.where(rng.random(N) < flip, -1.0, 1.0)
            xf, _ = hopfield_sync(pats, x0, iters)
            ov.append(float(xf @ pats[0] / N))
        res.append(np.mean(ov))
    return loads, np.array(res)


def fig_4_S5(out=None):
    """Hopfield retrieval against the load P/N for random patterns (N = 800, start with 10% of the bits flipped)."""
    loads, ov = hopfield_load_curve()
    fig, ax = plt.subplots(figsize=(4.4, 3.1))
    ax.plot(loads, ov, "o-", color=BLUE, ms=4)
    ax.axvline(0.138, color=RED, ls="--", lw=1)
    ax.text(0.145, 0.45, "$P/N\\approx0.14$", color=RED, fontsize=8)
    ax.set_xlabel("load $P/N$")
    ax.set_ylabel("overlap with stored pattern")
    ax.set_ylim(0, 1.05)
    fig.tight_layout()
    savefig(fig, CH, "fig4-S5", out)


FIGURES = {"4.6": fig_4_6, "4.8": fig_4_8, "4.17": fig_4_17, "4.18": fig_4_18, "4.19": fig_4_19, "4.21": fig_4_21,
           "4.23": fig_4_23, "4.25": fig_4_25, "4.27": fig_4_27, "4.37": fig_4_37, "4.38": fig_4_38, "4.44": fig_4_44,
           "4.S1": fig_4_S1, "4.S2": fig_4_S2, "4.S3": fig_4_S3, "4.S4": fig_4_S4, "4.S5": fig_4_S5}


# =========================================================================== JSON for the demonstrations
def export_json():
    os.makedirs(DATA_OUT, exist_ok=True)
    r = lambda a, k=6: [round(float(v), k) for v in np.ravel(a)]
    # 1. the student and sprinkler networks with reference posteriors
    st, sp = student_bn(), sprinkler_bn()
    ref = dict(
        student_prior={v: r(st.marginal(v)) for v in st.nodes},
        student_G_C={v: r(st.marginal(v, {"G": 2}), 8) for v in st.nodes},
        student_G_C_S_good={v: r(st.marginal(v, {"G": 2, "S": 1}), 8) for v in st.nodes},
        sprinkler_R_prior=r(sp.marginal("R"), 8), sprinkler_R_W=r(sp.marginal("R", {"W": 1}), 8),
        sprinkler_R_WS=r(sp.marginal("R", {"W": 1, "S": 1}), 8),
        berkson_corr={str(c): round(berkson_corr(c), 8) for c in (-2.0, 0.0, 2.5, 4.0)},
    )
    d1 = dict(student=dict(nodes=st.nodes, card=st.card, parents=st.parents, cpt={v: np.round(st.cpt[v], 8).tolist() for v in st.nodes}, states=STUDENT_STATES),
              sprinkler=dict(nodes=sp.nodes, card=sp.card, parents=sp.parents, cpt={v: np.round(sp.cpt[v], 8).tolist() for v in sp.nodes}), ref=ref)
    # 2. exact Ising numbers on the 4 x 4 torus and Onsager's curve
    Jg = [0.1, 0.2, 0.3, 0.4407, 0.6]
    ex = {str(J): ising_exact_small(4, 4, J) for J in Jg}
    ex_h = {str(J): ising_exact_small(4, 4, J, h=0.1) for J in (0.3, 0.6)}
    d2 = dict(exact_4x4={k: {a: round(b, 10) for a, b in v.items()} for k, v in ex.items()},
              exact_4x4_h0p1={k: {a: round(b, 10) for a, b in v.items()} for k, v in ex_h.items()},
              Jc=round(onsager_critical_J(), 10), onsager={str(J): round(float(onsager_magnetisation(J)), 8) for J in (0.45, 0.5, 0.6, 0.8)},
              potts_Jc={str(K): round(potts_critical_J(K), 8) for K in (2, 3, 4, 5, 10)})
    # 3. denoising problem and Python's mean-field result
    z, y = denoise_problem()
    mus = mean_field_ising_denoise(y, 1.0, 2.0, 15)
    d3 = dict(L=64, sigma=2.0, J=1.0, y=np.round(y, 4).ravel().tolist(), z=[int(v) for v in z.ravel()],
              ref=dict(mu_sum_sweep1=float(mus[0].sum()), mu_sum_sweep15=float(mus[-1].sum()), mu_mean_abs_15=float(np.abs(mus[-1]).mean()),
                       mu15_first8=r(mus[-1].ravel()[:8], 8), acc15=float((np.sign(mus[-1]) == z).mean()), acc_noisy=float((np.sign(y) == z).mean())))
    # 4. Gaussian-DAG reference numbers for the presets of the Gaussian demonstration
    d4 = gaussian_demo_reference()
    for name, d in (("student", d1), ("ising", d2), ("denoise", d3), ("gaussian", d4)):
        with open(os.path.join(DATA_OUT, "ch04-%s.json" % name), "w") as f:
            json.dump(d, f, separators=(",", ":"))
        print("wrote", "ch04-%s.json" % name)


# the presets of the Gaussian graphical model demonstration (nodes numbered 1..n in topological order)
GAUSSIAN_PRESETS = {
    "ar1": dict(n=7, edges=[(i, i + 1) for i in range(1, 7)], weights=[0.6] * 6, s=[1.25] + [1.0] * 6),   # stationary start: 1/sqrt(1-0.36) = 1.25
    "vstruct": dict(n=3, edges=[(1, 3), (2, 3)], weights=[1.0, 1.0], s=[1.0, 1.0, 1.0]),
    "chain": dict(n=3, edges=[(1, 2), (2, 3)], weights=[0.8, 0.8], s=[1.0, 1.0, 1.0]),
    "fork": dict(n=3, edges=[(1, 2), (1, 3)], weights=[0.8, 0.8], s=[1.0, 1.0, 1.0]),
    "fig423": dict(n=7, edges=[(1, 2), (1, 3), (2, 4), (2, 5), (3, 5), (3, 6), (5, 6), (4, 7), (5, 7), (6, 7)],
                   weights=[0.9, -0.7, 0.8, 0.6, 0.5, 0.7, -0.6, 0.5, 0.8, -0.4], s=[1.0] * 7),
}


def gaussian_from_edges(n, edges, weights, s):
    W = np.zeros((n, n))
    for (a, b), w in zip(edges, weights):
        W[b - 1, a - 1] = w
    return gaussian_bn_moments(W, s, np.zeros(n))


def gaussian_demo_reference():
    out = {}
    for k, p in GAUSSIAN_PRESETS.items():
        _, S, L = gaussian_from_edges(p["n"], p["edges"], p["weights"], p["s"])
        out[k] = dict(sigma_diag=[round(float(v), 8) for v in np.diag(S)], sigma_01=round(float(S[0, 1]), 8), lam_01=round(float(L[0, 1]), 8),
                      lam_trace=round(float(np.trace(L)), 8), logdet_sigma=round(float(np.linalg.slogdet(S)[1]), 8),
                      lam_nonzero=int((np.abs(L) > 1e-9).sum()), sigma_nonzero=int((np.abs(S) > 1e-9).sum()))
    return out


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()
