"""Bishop and Bishop (2024), Chapter 11: Structured Distributions.

Reproduces the figures of Chapter 11 of C. M. Bishop and H. Bishop, Deep Learning: Foundations and
Concepts (Springer, 2024) that are computed from a model, written from scratch with numpy and
matplotlib, and supplies every computation used in the lecture notes
(../ch11-structured-distributions.html) and the three browser demos:

* Section 11.1, directed graphs: DiscreteBN (a discrete Bayesian network stored as conditional
  probability tables, with the joint table (11.6) by einsum, conditionals, marginals and ancestral
  sampling), is_acyclic / topological_order (Exercise 11.2), the parameter counts of Section 11.1.3
  (n_params_*), noisy_or (Exercise 11.5), and the linear-Gaussian model of Section 11.1.4:
  lg_mean_recursion and lg_cov_recursion ((11.12), (11.13)), lg_moments (the closed form
  mu = (I - W)^{-1} b, Sigma = (I - W)^{-1} V (I - W)^{-T}), lg_precision, lg_from_cov (every
  covariance comes from a fully connected graph, Exercise 11.8), lg_block_moments (vector-valued
  nodes, (11.16), Exercise 11.10) and lg_sample_js (ancestral sampling with the demos' generator).
* Section 11.2, conditional independence: d_separated (the reachability form of the d-separation
  criterion), trails (every path between two nodes with the node at which it is blocked),
  markov_blanket, cond_mutual_info (the brute-force test of a conditional independence on a joint
  table), fuel_network (the car fuel system of Section 11.2.2 and the driver of Exercise 11.14),
  table_11_1 (Exercises 11.3 and 11.4), naive_bayes_fit (Exercise 11.15) and the naive Bayes
  densities of Figure 11.23.
* Section 11.3, sequence models: Markov chains of order k on text (ngram_counts, ngram_prob,
  ngram_cross_entropy, ngram_sample), the corpus loader alice() and its cleaning rule clean_text(),
  and the hidden Markov model of Section 11.3.1 (hmm_seq_prob, hmm_predictive, hmm_lag_cmi): the
  observed sequence of a state-space model is not Markov at any order (Exercise 11.19).
* JSRandom: the seeded generator DK.rng of the browser demos (mulberry32 uniforms, Box-Muller
  normals). explaining-away-demo.html, linear-gaussian-dag-demo.html and markov-text-demo.html use
  only its numbers, so they reproduce this module's values.

Figures reproduced: 11.23 (naive Bayes: class-conditional and marginal densities). Every other figure
of the chapter is a graph diagram. The diagrams that carry an argument are redrawn here, with the
statements they illustrate computed by the code rather than drawn by hand: 11.2 (the seven-node
graph), 11.14 (Figures 11.14 to 11.19: the three three-node graphs, with and without observing c,
each labelled by the d-separation test), 11.20 (the fuel system, with the posterior probabilities
(11.32) to (11.35)), 11.21 (d-separation, with the blocking nodes found by trails()), 11.25 (the
Markov blanket found by markov_blanket()), 11.29 (Figures 11.29 and 11.30: first- and second-order
Markov chains) and 11.31 (the state-space model). Five supplementary figures for the notes:
s1 (parameter counts), s2 (explaining away, with the driver of Exercise 11.14), s3 (ancestral
samples of a linear-Gaussian graph against the derived mean and covariance, and its precision
matrix), s4 (Markov models of text of order k: held-out cross-entropy and number of parameters) and
s5 (a hidden Markov model is not Markov at any order).
Skipped, with the reason:
* Figures 11.1, 11.3 to 11.13, 11.22, 11.24, 11.26 to 11.28 and 11.32: small schematic graphs
  (two to four nodes, a plate, or the "filter" cartoon) with no computation; the notes state each
  one as its factorisation or in words.

Settings chosen where the book gives none:
* Figure 11.23: class C1 has mean (0.33, 0.42) and standard deviations (0.055, 0.1); class C2 mean
  (0.6, 0.62) and standard deviations (0.11, 0.055); equal priors. Both are axis-aligned Gaussians.
* The text corpus is Lewis Carroll, Alice's Adventures in Wonderland (1865), public domain, from the
  first chapter heading to the end, cleaned by clean_text() to 28 symbols (space, full stop, a to z)
  and bundled as data/ch11_alice.txt (136,418 characters). The first 90% (to the nearest space) is
  the training text, the rest the held-out text.

Run `python3 ch11_structured_distributions.py --list`, `python3 ch11_structured_distributions.py`
(all figures, about half a minute) or `python3 ch11_structured_distributions.py --fig 11.23`. Files go
to ../img/ch11/; demo data to ../data/ch11-*.json.
"""
import itertools
import json
import math
import os
import re
import string
import sys
from collections import deque

import numpy as np

HERE = os.path.dirname(os.path.abspath(__file__))
sys.path.insert(0, HERE)
import common  # noqa: E402
from common import BLUE, GREEN, RED, ORANGE, PURPLE, GREY, plt, savefig, panel_label  # noqa: E402
from matplotlib.patches import Circle, FancyArrowPatch, Rectangle  # noqa: E402

CH = 11
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
M32 = 0xFFFFFFFF
OBS_FILL = "#c9d8f0"     # observed nodes: shaded, as in the book
MB_FILL = "#f6d7a7"      # Markov blanket highlight


# =========================================================================== the demos' generator
def _imul(a, b):
    return (a * b) & M32


class JSRandom:
    """The seeded random numbers of the browser demos (DK.rng in courses/demo-kit.js).

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

    def __init__(self, seed):
        self.a = int(seed) & M32
        self.spare = None

    def u(self):
        a = (self.a + 0x6D2B79F5) & M32
        self.a = a
        t = _imul(a ^ (a >> 15), 1 | a)
        t = ((t + _imul(t ^ (t >> 7), 61 | t)) & M32) ^ t
        return ((t ^ (t >> 14)) & M32) / 4294967296.0

    def _pos(self):
        x = 0.0
        while x == 0.0:
            x = self.u()
        return x

    def norm(self):
        if self.spare is not None:
            s, self.spare = self.spare, None
            return s
        r = math.sqrt(-2.0 * math.log(self._pos()))
        th = 2.0 * math.pi * self.u()
        self.spare = r * math.sin(th)
        return r * math.cos(th)


# =========================================================================== Section 11.1: graphs
def topological_order(parents):
    """A topological order of the graph {node: [parents]} (Kahn's algorithm), or None if it has a cycle.

    Exercise 11.2: a directed graph has no directed cycle if and only if such an order exists.
    """
    nodes = list(parents)
    children = {n: [] for n in nodes}
    indeg = {n: len(parents[n]) for n in nodes}
    for n in nodes:
        for p in parents[n]:
            children[p].append(n)
    queue = deque(n for n in nodes if indeg[n] == 0)
    order = []
    while queue:
        n = queue.popleft()
        order.append(n)
        for c in children[n]:
            indeg[c] -= 1
            if indeg[c] == 0:
                queue.append(c)
    return order if len(order) == len(nodes) else None


def is_acyclic(parents):
    """True if no directed cycle, checked independently of topological_order by depth-first search."""
    state = {}

    def visit(n):
        state[n] = 1
        for p in parents[n]:
            if state.get(p) == 1 or (state.get(p) is None and not visit(p)):
                return False
        state[n] = 2
        return True

    return all(state.get(n) == 2 or visit(n) for n in parents)


def children_of(parents):
    ch = {n: [] for n in parents}
    for n, ps in parents.items():
        for p in ps:
            ch[p].append(n)
    return ch


def descendants(parents, node):
    ch = children_of(parents)
    out, stack = set(), [node]
    while stack:
        for c in ch[stack.pop()]:
            if c not in out:
                out.add(c)
                stack.append(c)
    return out


def ancestors(parents, nodes):
    out, stack = set(nodes), list(nodes)
    while stack:
        for p in parents[stack.pop()]:
            if p not in out:
                out.add(p)
                stack.append(p)
    return out


class DiscreteBN:
    """A Bayesian network over discrete variables: the factorisation (11.6) with tables.

    parents: {name: [parent names]} in any order; card: {name: number of states};
    cpt[name] is an array of shape (card of each parent, in order) + (card of name,) holding
    p(name | parents); each row sums to one.
    """

    def __init__(self, parents, card, cpt):
        self.parents = {n: list(p) for n, p in parents.items()}
        self.order = topological_order(self.parents)
        if self.order is None:
            raise ValueError("graph has a directed cycle")
        self.nodes = list(parents)
        self.card = dict(card)
        self.cpt = {n: np.asarray(cpt[n], dtype=float) for n in self.nodes}

    @classmethod
    def random(cls, parents, card=2, rng=None, low=0.1, high=0.9):
        """Random tables: for binary nodes p(x = 1 | parents) uniform on (low, high); otherwise Dirichlet(1)."""
        rng = rng or np.random.default_rng(0)
        cards = {n: card for n in parents} if np.isscalar(card) else dict(card)
        cpt = {}
        for n, ps in parents.items():
            shape = tuple(cards[p] for p in ps)
            if cards[n] == 2:
                q = rng.uniform(low, high, size=shape)
                cpt[n] = np.stack([1 - q, q], axis=-1)
            else:
                cpt[n] = rng.dirichlet(np.ones(cards[n]), size=shape)
        return cls(parents, cards, cpt)

    def joint(self):
        """The joint table p(x_1, ..., x_K) = prod_k p(x_k | pa_k), axes in self.nodes order (11.6)."""
        letters = string.ascii_letters
        idx = {n: letters[i] for i, n in enumerate(self.nodes)}
        subs = ",".join("".join(idx[p] for p in self.parents[n]) + idx[n] for n in self.nodes)
        out = "".join(idx[n] for n in self.nodes)
        return np.einsum(subs + "->" + out, *[self.cpt[n] for n in self.nodes])

    def n_params(self):
        """Free parameters: (K_k - 1) times the number of parent configurations, summed over nodes."""
        return int(sum((self.card[n] - 1) * np.prod([self.card[p] for p in self.parents[n]], dtype=int)
                       for n in self.nodes))

    def sample(self, n, rng):
        """Ancestral sampling: draw each node from its table given its already-drawn parents."""
        out = {k: np.zeros(n, dtype=int) for k in self.nodes}
        for k in self.order:
            tab = self.cpt[k][tuple(out[p] for p in self.parents[k])] if self.parents[k] else \
                np.broadcast_to(self.cpt[k], (n, self.card[k]))
            u = rng.random(n)[:, None]
            out[k] = (u > np.cumsum(tab, axis=1)).sum(1)
        return out


def marginal(J, nodes, keep):
    """Marginal table of the variables `keep` (in that order) from a joint table J with axes `nodes`."""
    ax = tuple(i for i, n in enumerate(nodes) if n not in keep)
    M = J.sum(axis=ax)
    rest = [n for n in nodes if n in keep]
    return np.transpose(M, [rest.index(k) for k in keep])


def conditional(J, nodes, query, evidence):
    """p(query | evidence) as an array over the states of `query`; evidence is {name: value}."""
    if query in evidence:
        e = np.zeros(J.shape[nodes.index(query)])
        e[evidence[query]] = 1.0
        return e
    sl =tuple(evidence.get(n, slice(None)) for n in nodes)
    rest = [n for n in nodes if n not in evidence]
    sub = J[sl]
    m = sub.sum(axis=tuple(i for i, n in enumerate(rest) if n != query))
    return m / m.sum()


def cond_mutual_info(J, nodes, A, B, C=()):
    """I(A; B | C) in nats from a joint table: zero iff A and B are independent given C (11.23)."""
    A, B, C = list(A), list(B), list(C)
    keep = A + B + C
    P = marginal(J, nodes, keep)
    a, b = len(A), len(B)
    Pc = P.sum(axis=tuple(range(a + b)), keepdims=True)
    Pac = P.sum(axis=tuple(range(a, a + b)), keepdims=True)
    Pbc = P.sum(axis=tuple(range(a)), keepdims=True)
    with np.errstate(divide="ignore", invalid="ignore"):
        t = np.where(P > 0, P * (np.log(P) + np.log(Pc) - np.log(Pac) - np.log(Pbc)), 0.0)
    return float(max(t.sum(), 0.0))


# =========================================================================== parameter counts (11.1.3)
def n_params_full(K, M):
    """A general joint distribution of M K-state variables: K^M - 1."""
    return K ** M - 1


def n_params_independent(K, M):
    return M * (K - 1)


def n_params_chain(K, M):
    """The chain of Figure 11.4: K - 1 + (M - 1) K (K - 1)."""
    return K - 1 + (M - 1) * K * (K - 1)


def n_params_shared_chain(K):
    """The chain of Figure 11.5 with all transition tables tied: K^2 - 1, whatever M."""
    return K - 1 + K * (K - 1)


def n_params_markov_order(K, M):
    """One table p(x_n | x_{n-M}, ..., x_{n-1}) of an Mth-order chain: K^M (K - 1) (the book prints K^{M-1}(K-1))."""
    return K ** M * (K - 1)


def noisy_or(x, mu, mu0):
    """p(y = 1 | x) for the noisy-OR (11.49): 1 - (1 - mu0) prod_i (1 - mu_i)^{x_i}."""
    x = np.asarray(x, dtype=float)
    return 1.0 - (1.0 - mu0) * np.prod((1.0 - np.asarray(mu)) ** x, axis=-1)


# =========================================================================== linear-Gaussian models (11.1.4)
def lg_mean_recursion(W, b):
    """E[x_i] = sum_{j in pa(i)} w_ij E[x_j] + b_i (11.12), nodes numbered so that parents come first."""
    D = len(b)
    mu = np.zeros(D)
    for i in range(D):
        mu[i] = sum(W[i, j] * mu[j] for j in range(i)) + b[i]
    return mu


def lg_cov_recursion(W, v):
    """cov[x_i, x_j] = sum_{k in pa(j)} w_jk cov[x_i, x_k] + I_ij v_j (11.13), applied for i <= j only.

    The recursion is valid when x_i is not a descendant of x_j (for instance i <= j in a topological
    numbering); the entries below the diagonal follow by symmetry.
    """
    D = len(v)
    S = np.zeros((D, D))
    for j in range(D):
        for i in range(j + 1):
            S[i, j] = sum(W[j, k] * S[i, k] for k in range(j)) + (v[j] if i == j else 0.0)
            S[j, i] = S[i, j]
    return S


def lg_cov_recursion_unrestricted(W, v):
    """(11.13) read literally for every pair (i, j), using the true covariance on the right-hand side.

    This shows why the restriction i <= j matters: for i a descendant of j it returns a wrong value.
    """
    S = lg_moments(W, np.zeros(len(v)), v)[1]
    D = len(v)
    return np.array([[sum(W[j, k] * S[i, k] for k in range(D)) + (v[j] if i == j else 0.0)
                      for j in range(D)] for i in range(D)])


def lg_moments(W, b, v):
    """x = W x + b + diag(sqrt(v)) eps  =>  mu = (I - W)^{-1} b,  Sigma = (I - W)^{-1} V (I - W)^{-T}."""
    D = len(b)
    A = np.linalg.inv(np.eye(D) - W)
    return A @ b, A @ np.diag(v) @ A.T


def lg_precision(W, v):
    """Precision matrix read off (11.11): Lambda = (I - W)^T V^{-1} (I - W)."""
    D = len(v)
    B = np.eye(D) - W
    return B.T @ np.diag(1.0 / np.asarray(v)) @ B


def lg_from_cov(Sigma):
    """Weights and variances of a fully connected linear-Gaussian graph with covariance Sigma.

    w_i = Sigma[:i, :i]^{-1} Sigma[:i, i] (regression of x_i on x_1..x_{i-1}) and v_i the residual
    variance: D(D - 1)/2 weights and D variances, D(D + 1)/2 numbers in all (Exercise 11.8).
    """
    D = Sigma.shape[0]
    W, v = np.zeros((D, D)), np.zeros(D)
    for i in range(D):
        if i:
            W[i, :i] = np.linalg.solve(Sigma[:i, :i], Sigma[:i, i])
        v[i] = Sigma[i, i] - W[i, :i] @ Sigma[:i, i]
    return W, v


def lg_block_moments(blocks, b, Sig):
    """Vector-valued linear-Gaussian graph (11.16): blocks[(i, j)] = W_ij (j a parent of i).

    Returns the joint mean and covariance by the block recursions
    mu_i = sum_j W_ij mu_j + b_i and cov[x_i, x_j] = sum_{k in pa(j)} cov[x_i, x_k] W_jk^T + I_ij Sigma_j.
    """
    D = len(b)
    mu = [None] * D
    C = {}
    for i in range(D):
        mu[i] = b[i] + sum((blocks[(i, j)] @ mu[j] for j in range(i) if (i, j) in blocks), np.zeros(len(b[i])))
    for j in range(D):
        for i in range(j + 1):
            acc = Sig[j].copy() if i == j else np.zeros((len(b[i]), len(b[j])))
            for k in range(j):
                if (j, k) in blocks:
                    acc = acc + C[(i, k)] @ blocks[(j, k)].T
            C[(i, j)] = acc
            C[(j, i)] = acc.T
    return np.concatenate(mu), np.block([[C[(i, j)] for j in range(D)] for i in range(D)])


def lg_sample_js(W, b, v, N, seed):
    """Ancestral sampling of a linear-Gaussian graph with the demos' generator (same order of operations)."""
    rng = JSRandom(seed)
    D = len(b)
    X = np.zeros((N, D))
    for n in range(N):
        x = [0.0] * D
        for i in range(D):
            s = 0.0
            for j in range(i):
                s += W[i][j] * x[j]
            x[i] = s + b[i] + math.sqrt(v[i]) * rng.norm()
        X[n] = x
    return X


def sample_moments(X):
    """Sample mean and covariance with divisor N, accumulated in the same order as the demo."""
    N, D = X.shape
    m = [0.0] * D
    for n in range(N):
        for i in range(D):
            m[i] += X[n, i]
    m = [mi / N for mi in m]
    S = [[0.0] * D for _ in range(D)]
    for n in range(N):
        for i in range(D):
            for j in range(D):
                S[i][j] += (X[n, i] - m[i]) * (X[n, j] - m[j])
    return np.array(m), np.array(S) / N


FIG_11_7 = dict(W=np.array([[0, 0, 0], [0.8, 0, 0], [0, -1.2, 0]], float), b=np.array([1.0, -1.0, 0.5]),
                v=np.array([1.0, 0.5, 0.3]))


def fig_11_7_closed_form(w21, w32, b, v):
    """(11.14) and (11.15) for the chain x1 -> x2 -> x3 of Figure 11.7."""
    b1, b2, b3 = b
    v1, v2, v3 = v
    mu = np.array([b1, b2 + w21 * b1, b3 + w32 * b2 + w32 * w21 * b1])
    s22 = v2 + w21 ** 2 * v1
    S = np.array([[v1, w21 * v1, w32 * w21 * v1],
                  [w21 * v1, s22, w32 * s22],
                  [w32 * w21 * v1, w32 * s22, v3 + w32 ** 2 * s22]])
    return mu, S


# =========================================================================== Section 11.2
def d_separated(parents, A, B, C):
    """True if every path from A to B is blocked by C (Section 11.2.3), by the reachability algorithm.

    A path enters a node either from a child (moving against an arrow, 'up') or from a parent ('down').
    From an unobserved node reached 'up' we may continue to parents and children; from an unobserved
    node reached 'down' only to children (head-to-tail); from a node reached 'down' that is in C or has
    a descendant in C (a head-to-head node that is unblocked) we may turn back up to its parents.
    """
    A, B, C = set(A), set(B), set(C)
    ch = children_of(parents)
    anc = ancestors(parents, C)          # C and its ancestors: exactly the colliders that are unblocked
    seen, reach = set(), set()
    queue = deque((a, "up") for a in A)
    while queue:
        node, d = queue.popleft()
        if (node, d) in seen:
            continue
        seen.add((node, d))
        if node not in C:
            reach.add(node)
        if d == "up" and node not in C:
            queue.extend((p, "up") for p in parents[node])
            queue.extend((c, "down") for c in ch[node])
        elif d == "down":
            if node not in C:
                queue.extend((c, "down") for c in ch[node])
            if node in anc:
                queue.extend((p, "up") for p in parents[node])
    return not (reach & B)


def trails(parents, a, b, C):
    """Every simple path between a and b, ignoring arrow directions, with the node that blocks it.

    Returns a list of (path, kinds, blocker): kinds[i] is 'tt' (tail-to-tail), 'ht' (head-to-tail)
    or 'hh' (head-to-head) for each interior node, and blocker is the first blocking node or None.
    """
    C = set(C)
    ch = children_of(parents)
    nbr = {n: set(parents[n]) | set(ch[n]) for n in parents}
    out = []

    def kind(prev, node, nxt):
        into_from_prev = prev in parents[node]
        into_from_next = nxt in parents[node]
        if into_from_prev and into_from_next:
            return "hh"
        if not into_from_prev and not into_from_next:
            return "tt"
        return "ht"

    def walk(path):
        node = path[-1]
        if node == b:
            kinds, blocker = [], None
            for i in range(1, len(path) - 1):
                k = kind(path[i - 1], path[i], path[i + 1])
                kinds.append(k)
                if blocker is None:
                    if k == "hh":
                        if path[i] not in C and not (descendants(parents, path[i]) & C):
                            blocker = path[i]
                    elif path[i] in C:
                        blocker = path[i]
            out.append((list(path), kinds, blocker))
            return
        for m in sorted(nbr[node]):
            if m not in path:
                walk(path + [m])

    walk([a])
    return out


def markov_blanket(parents, node):
    """Parents, children and co-parents of `node` (Section 11.2.6)."""
    ch = children_of(parents)[node]
    mb = set(parents[node]) | set(ch)
    for c in ch:
        mb |= set(parents[c])
    mb.discard(node)
    return mb


# =========================================================================== the car fuel system (11.2.2)
def fuel_network(pB=0.9, pF=0.9, g=(0.1, 0.2, 0.2, 0.8), driver=None):
    """B (battery), F (fuel) -> G (gauge) [-> D (driver's report)]; state 1 = charged / full.

    g = p(G=1 | B, F) for (B, F) = (0,0), (0,1), (1,0), (1,1). driver = (p(D=1|G=1), p(D=0|G=0)).
    """
    parents = {"B": [], "F": [], "G": ["B", "F"]}
    tabG = np.array([[g[0], g[1]], [g[2], g[3]]])
    cpt = {"B": [1 - pB, pB], "F": [1 - pF, pF], "G": np.stack([1 - tabG, tabG], -1)}
    if driver is not None:
        parents["D"] = ["G"]
        d1, d0 = driver
        cpt["D"] = np.array([[d0, 1 - d0], [1 - d1, d1]])
    return DiscreteBN(parents, {n: 2 for n in parents}, cpt)


def fuel_numbers(driver=None):
    """The probabilities (11.32) to (11.35), and with a driver those of Exercise 11.14."""
    bn = fuel_network(driver=driver)
    J, nodes = bn.joint(), bn.nodes
    obs = "D" if driver else "G"
    out = {"p(F=0)": conditional(J, nodes, "F", {})[0],
           "p(%s=0)" % obs: marginal(J, nodes, [obs])[0],
           "p(%s=0|F=0)" % obs: conditional(J, nodes, obs, {"F": 0})[0],
           "p(F=0|%s=0)" % obs: conditional(J, nodes, "F", {obs: 0})[0],
           "p(F=0|%s=0,B=0)" % obs: conditional(J, nodes, "F", {obs: 0, "B": 0})[0]}
    return out


# =========================================================================== Table 11.1 (Exercises 11.3, 11.4)
TABLE_11_1 = np.array([0.192, 0.144, 0.048, 0.216, 0.192, 0.064, 0.048, 0.096]).reshape(2, 2, 2)   # [a, b, c]


def table_11_1_factors():
    """p(a), p(c | a), p(b | c) of Table 11.1 and the product p(a) p(c|a) p(b|c) (Exercise 11.4)."""
    P = TABLE_11_1
    pa = P.sum((1, 2))
    pac = P.sum(1)
    pc_a = pac / pa[:, None]
    pbc = P.sum(0)
    pb_c = pbc / pbc.sum(0, keepdims=True)
    prod = np.einsum("a,ac,bc->abc", pa, pc_a, pb_c)
    return pa, pc_a, pb_c, prod


# =========================================================================== naive Bayes (11.2.4)
NB_PARAMS = {"mu": np.array([[0.33, 0.42], [0.6, 0.62]]), "sd": np.array([[0.055, 0.1], [0.11, 0.055]]),
             "prior": np.array([0.5, 0.5])}


def nb_class_density(X, k, P=NB_PARAMS):
    """p(x | C_k) = prod_l N(x_l | mu_kl, sd_kl^2) (11.37), (11.40)."""
    z = (X - P["mu"][k]) / P["sd"][k]
    return np.prod(np.exp(-0.5 * z ** 2) / (np.sqrt(2 * np.pi) * P["sd"][k]), axis=-1)


def naive_bayes_fit(X, y, K):
    """Maximum likelihood for a Gaussian naive Bayes model (Exercise 11.15): per class and per feature.

    Returns class fractions, per-class feature means and per-class feature variances (divisor N_k).
    """
    pri = np.array([np.mean(y == k) for k in range(K)])
    mu = np.array([X[y == k].mean(0) for k in range(K)])
    var = np.array([X[y == k].var(0) for k in range(K)])
    return pri, mu, var


def nb_loglik(X, y, pri, mu, var):
    ll = 0.0
    for k in range(len(pri)):
        Z = X[y == k]
        ll += len(Z) * np.log(pri[k]) - 0.5 * np.sum(np.log(2 * np.pi * var[k]) + (Z - mu[k]) ** 2 / var[k])
    return ll


# =========================================================================== Section 11.3: text
ALPHABET = " .abcdefghijklmnopqrstuvwxyz"
K_TEXT = len(ALPHABET)
PROMPT = "alice was beginning to get very tired "


def clean_text(raw):
    """The cleaning rule used for the bundled corpus: 28 symbols (space, full stop, a to z).

    Lower case; apostrophes removed (so "don't" becomes "dont"); ! ? ; : become full stops; dashes and
    white space become single spaces; every other character is dropped; a full stop is followed by a
    space and never preceded by one.
    """
    t = raw.lower().replace("ù", "u")
    t = re.sub("[’‘']", "", t)
    t = re.sub(r"[!?;:]", ".", t)
    t = re.sub("[-\u2014\\s]+", " ", t)
    t = re.sub(r"[^a-z. ]", "", t)
    t = re.sub(r" +", " ", t)
    t = re.sub(r" ?\.( ?\.)*", ".", t)
    t = re.sub(r"\.(?=[a-z])", ". ", t)
    return t.strip()


def alice():
    """The cleaned text and the index where the held-out part starts (the last 10%, at a space)."""
    with open(os.path.join(HERE, "data", "ch11_alice.txt")) as f:
        t = f.read().strip()
    split = t.index(" ", int(0.9 * len(t))) + 1
    return t, split


def ngram_counts(text, end, k):
    """Counts n(context, next symbol) for an order-k Markov model, from the positions k..end-1 of text.

    The maximum likelihood transition table is these counts normalised per context (gap in notes).
    """
    idx = {c: i for i, c in enumerate(ALPHABET)}
    counts = {}
    for i in range(k, end):
        ctx = text[i - k:i]
        row = counts.get(ctx)
        if row is None:
            row = counts[ctx] = [0] * K_TEXT
        row[idx[text[i]]] += 1
    return counts


def ngram_prob(counts, ctx, alpha, backoff=None):
    """p(next | ctx) with additive smoothing (n + alpha) / (N + K alpha).

    counts is the table of one order. An unseen context has no counts: with alpha > 0 its row is
    uniform, with alpha = 0 it is set to uniform. With backoff = [counts of order 0, 1, ..., k] an
    unseen context instead borrows the row of its longest suffix that was seen (a form of parameter
    tying: the model is still an order-k Markov chain with normalised conditionals).
    """
    row = counts.get(ctx)
    if row is None and backoff is not None:
        for j in range(len(ctx) - 1, -1, -1):
            row = backoff[j].get(ctx[len(ctx) - j:])
            if row is not None:
                break
    if row is None:
        row = [0] * K_TEXT
    n = 0
    for c in row:
        n += c
    if n == 0 and alpha == 0:
        return [1.0 / K_TEXT] * K_TEXT
    den = n + K_TEXT * alpha
    return [(c + alpha) / den for c in row]


def ngram_cross_entropy(text, counts, k, alpha, start, end, backoff=None):
    """Average -log2 p(x_i | x_{i-k..i-1}) over positions start..end-1 (inf if a probability is zero)."""
    idx = {c: i for i, c in enumerate(ALPHABET)}
    tot = 0.0
    for i in range(max(start, k), end):
        p = ngram_prob(counts, text[i - k:i], alpha, backoff)[idx[text[i]]]
        if p <= 0:
            return math.inf
        tot -= math.log(p)
    return tot / ((end - max(start, k)) * math.log(2))


def ngram_sample(counts, k, alpha, length, seed, prompt=PROMPT, backoff=None):
    """Generate `length` symbols after the prompt, one at a time, with the demos' generator."""
    rng = JSRandom(seed)
    g = prompt
    for _ in range(length):
        ctx = g[len(g) - k:] if k > 0 else ""
        p = ngram_prob(counts, ctx, alpha, backoff)
        u = rng.u()
        cum, j = 0.0, K_TEXT - 1
        for jj in range(K_TEXT):
            cum += p[jj]
            if u < cum:
                j = jj
                break
        g += ALPHABET[j]
    return g[len(prompt):]


TEXT_SETTINGS = ((1.0, False), (0.1, False), (0.01, False), (0.1, True))


def text_table(kmax=10, settings=TEXT_SETTINGS):
    """Held-out and training cross-entropy (bits per symbol) for orders 0..kmax.

    settings lists (alpha, back off?) pairs; the key of each entry is e.g. 'test_0.1' or 'test_0.1_bo'.
    """
    t, split = alice()
    counts = [ngram_counts(t, split, k) for k in range(kmax + 1)]
    rows = []
    for k in range(kmax + 1):
        row = {"k": k, "contexts": len(counts[k]), "params": n_params_markov_order(K_TEXT, k)}
        for a, bo in settings:
            key = "%g%s" % (a, "_bo" if bo else "")
            row["test_" + key] = ngram_cross_entropy(t, counts[k], k, a, split, len(t), counts if bo else None)
            row["train_" + key] = ngram_cross_entropy(t, counts[k], k, a, 0, split, counts if bo else None)
        rows.append(row)
    return rows


# =========================================================================== Section 11.3.1: hidden Markov model
HMM_DEFAULT = dict(pi=np.array([0.5, 0.5]), A=np.array([[0.95, 0.05], [0.05, 0.95]]),
                   E=np.array([[0.8, 0.2], [0.2, 0.8]]))   # E[z, x] = p(x | z)


def hmm_seq_prob(pi, A, E, xs):
    """p(x_1, ..., x_N) of a hidden Markov model (11.48) by the forward recursion."""
    a = pi * E[:, xs[0]]
    for x in xs[1:]:
        a = (a @ A) * E[:, x]
    return float(a.sum())


def hmm_seq_prob_brute(pi, A, E, xs):
    """The same by summing (11.48) over every latent path (for checking)."""
    tot = 0.0
    for zs in itertools.product(range(len(pi)), repeat=len(xs)):
        p = pi[zs[0]] * E[zs[0], xs[0]]
        for n in range(1, len(xs)):
            p *= A[zs[n - 1], zs[n]] * E[zs[n], xs[n]]
        tot += p
    return tot


def hmm_predictive(pi, A, E, xs):
    """p(x_{n+1} | x_1..x_n) by the normalised forward (filtering) recursion: a recurrent state update."""
    alpha = pi * E[:, xs[0]]
    alpha = alpha / alpha.sum()
    for x in xs[1:]:
        alpha = (alpha @ A) * E[:, x]
        alpha = alpha / alpha.sum()
    return (alpha @ A) @ E


def hmm_lag_cmi(pi, A, E, k):
    """I(x_{n+1}; x_{n-k} | x_{n-k+1}, ..., x_n) in nats, by enumerating every binary sequence of length k + 2.

    A Markov chain of order k has this equal to zero; for a hidden Markov model it is positive for every k.
    """
    L = k + 2
    P = np.zeros((2,) * L)
    for xs in itertools.product((0, 1), repeat=L):
        P[xs] = hmm_seq_prob(pi, A, E, list(xs))
    nodes = list(range(L))
    return cond_mutual_info(P, nodes, [L - 1], [0], list(range(1, L - 1)))


def stationary(A):
    vals, vecs = np.linalg.eig(A.T)
    v = np.real(vecs[:, np.argmin(np.abs(vals - 1))])
    return v / v.sum()


# =========================================================================== drawing graphs
def draw_graph(ax, pos, edges, observed=(), fills=None, r=0.3, labels=None, curved=None, fs=12,
               colour=RED, lw=1.4, edge_colours=None):
    """Draw a directed graph in the book's style: red circles, shaded when observed, arrows between them."""
    fills = fills or {}
    curved = curved or {}
    edge_colours = edge_colours or {}
    for (u, w) in edges:
        p0, p1 = np.array(pos[u], float), np.array(pos[w], float)
        rad = curved.get((u, w), 0.0)
        d = p1 - p0
        ctrl = (p0 + p1) / 2 + rad * np.array([d[1], -d[0]])      # the control point of matplotlib's arc3
        t0, t1 = ctrl - p0, p1 - ctrl
        a0 = p0 + r * t0 / np.linalg.norm(t0)                      # leave and enter on the circles
        a1 = p1 - r * t1 / np.linalg.norm(t1)
        arr = FancyArrowPatch(tuple(a0), tuple(a1), arrowstyle="-|>", mutation_scale=13, lw=lw,
                              color=edge_colours.get((u, w), colour),
                              connectionstyle="arc3,rad=%g" % rad, shrinkA=0, shrinkB=0, zorder=1)
        ax.add_patch(arr)
    for n, (x, y) in pos.items():
        fc = fills.get(n, OBS_FILL if n in observed else "white")
        ax.add_patch(Circle((x, y), r, fc=fc, ec=colour, lw=lw, zorder=2))
        ax.text(x, y, (labels or {}).get(n, n), ha="center", va="center", fontsize=fs, zorder=3)
    ax.set_aspect("equal")
    ax.axis("off")


def _limits(ax, pos, pad=0.5):
    xs, ys = [p[0] for p in pos.values()], [p[1] for p in pos.values()]
    ax.set_xlim(min(xs) - pad, max(xs) + pad)
    ax.set_ylim(min(ys) - pad, max(ys) + pad)


def _tex(n):
    m = re.match(r"([a-zA-Z]+)(\d+)$", n)
    return "$%s_{%s}$" % m.groups() if m else "$%s$" % n


# =========================================================================== figures
FIG_11_2_PARENTS = {"x1": [], "x2": [], "x3": [], "x4": ["x1", "x2", "x3"], "x5": ["x1", "x3"],
                    "x6": ["x4"], "x7": ["x4", "x5"]}


def fig_11_2(out=None):
    """The seven-node directed graph whose factorisation is (11.5)."""
    pos = {"x1": (0.4, 3.0), "x2": (2.0, 3.4), "x3": (3.4, 2.7), "x4": (1.3, 1.8), "x5": (3.1, 1.4),
           "x6": (0.7, 0.4), "x7": (2.4, 0.2)}
    edges = [(p, n) for n, ps in FIG_11_2_PARENTS.items() for p in ps]
    fig, ax = plt.subplots(figsize=(3.6, 3.3))
    draw_graph(ax, pos, edges, labels={n: _tex(n) for n in pos})
    _limits(ax, pos, 0.45)
    savefig(fig, CH, "fig11-2", out)


THREE_GRAPHS = {"tail-to-tail": {"a": ["c"], "b": ["c"], "c": []},
                "head-to-tail": {"a": [], "c": ["a"], "b": ["c"]},
                "head-to-head": {"a": [], "b": [], "c": ["a", "b"]}}


def fig_11_14(out=None):
    """Figures 11.14 to 11.19: the three three-node graphs, without and with c observed."""
    fig, axes = plt.subplots(2, 3, figsize=(8.4, 4.4))
    pos = {"a": (0, 0), "c": (1, 0.8), "b": (2, 0)}
    names = list(THREE_GRAPHS)
    book = [["11.14", "11.16", "11.18"], ["11.15", "11.17", "11.19"]]
    for col, name in enumerate(names):
        par = THREE_GRAPHS[name]
        edges = [(p, n) for n, ps in par.items() for p in ps]
        for row, C in enumerate(([], ["c"])):
            ax = axes[row, col]
            draw_graph(ax, pos, edges, observed=C, labels={n: "$%s$" % n for n in pos})
            _limits(ax, pos, 0.4)
            ax.set_ylim(-0.75, 1.25)
            sep = d_separated(par, ["a"], ["b"], C)
            txt = ("$a \\perp\\!\\!\\!\\perp b \\mid %s$" % ("c" if C else "\\emptyset")) if sep else \
                ("$a \\not\\perp\\!\\!\\!\\perp b \\mid %s$" % ("c" if C else "\\emptyset"))
            ax.text(1, -0.55, txt, ha="center", fontsize=11, color=GREEN if sep else RED)
            ax.set_title("%s%s (Fig. %s)" % (name, ", c observed" if C else "", book[row][col]), fontsize=9)
    savefig(fig, CH, "fig11-14", out)


def fig_11_20(out=None):
    """The fuel system: no observation, the gauge reads empty, and also the battery is flat."""
    bn = fuel_network()
    J, nodes = bn.joint(), bn.nodes
    pos = {"B": (0, 1), "F": (2, 1), "G": (1, 0)}
    edges = [("B", "G"), ("F", "G")]
    cases = [({}, "no observation"), ({"G": 0}, "G = 0 observed"), ({"G": 0, "B": 0}, "G = 0 and B = 0 observed")]
    fig, axes = plt.subplots(1, 3, figsize=(8.4, 2.7))
    for ax, (ev, title) in zip(axes, cases):
        draw_graph(ax, pos, edges, observed=list(ev), labels={n: "$%s$" % n for n in pos})
        _limits(ax, pos, 0.45)
        ax.set_ylim(-0.95, 1.45)
        pF0 = conditional(J, nodes, "F", ev)[0]
        ax.text(1, -0.75, "$p(F{=}0\\mid\\cdot)=%.3f$" % pF0, ha="center", fontsize=10.5)
        ax.set_title(title, fontsize=9.5)
    savefig(fig, CH, "fig11-20", out)


FIG_11_21_PARENTS = {"a": [], "f": [], "e": ["a", "f"], "b": ["f"], "c": ["e"]}


def fig_11_21(out=None):
    """d-separation on a five-node graph: conditioning on c (left) and on f (right)."""
    par = FIG_11_21_PARENTS
    pos = {"a": (0, 2), "f": (2, 2), "e": (1, 1), "b": (3, 1), "c": (1, 0)}
    edges = [(p, n) for n, ps in par.items() for p in ps]
    fig, axes = plt.subplots(1, 2, figsize=(7.4, 3.5))
    for ax, C, lab in zip(axes, (["c"], ["f"]), "ab"):
        tr = trails(par, "a", "b", C)
        blockers = {bl for _, _, bl in tr if bl}
        fills = {n: OBS_FILL for n in C}
        draw_graph(ax, pos, edges, observed=C, fills=fills, labels={n: "$%s$" % n for n in pos})
        for n in blockers:
            x, y = pos[n]
            ax.add_patch(Circle((x, y), 0.42, fc="none", ec=GREY, lw=1.0, ls="--", zorder=2))
        _limits(ax, pos, 0.5)
        ax.set_ylim(-1.05, 2.5)
        sep = d_separated(par, ["a"], ["b"], C)
        path = " - ".join(tr[0][0])
        ax.text(1.5, -0.8, "path %s: %s\n$a %s b \\mid %s$" % (
            path, ("blocked at " + ", ".join(sorted(blockers))) if blockers else "not blocked",
            "\\perp\\!\\!\\!\\perp" if sep else "\\not\\perp\\!\\!\\!\\perp", C[0]),
            ha="center", fontsize=9.5, color=GREEN if sep else RED)
        panel_label(ax, lab)
    savefig(fig, CH, "fig11-21", out)


FIG_11_25_PARENTS = {"g": [], "p1": ["g"], "p2": [], "q1": ["o"], "q2": [], "o": [], "xi": ["p1", "p2"],
                     "c1": ["xi", "q1"], "c2": ["xi", "q2"], "d": ["c1"], "s": ["p2"]}


def fig_11_25(out=None):
    """The Markov blanket of x_i (parents, children, co-parents), found by markov_blanket()."""
    par = FIG_11_25_PARENTS
    pos = {"g": (0.6, 4.1), "p1": (1.2, 3.0), "p2": (2.8, 3.0), "s": (3.9, 3.9), "o": (-0.4, 2.2),
           "q1": (0.2, 1.4), "xi": (2.0, 2.0), "q2": (3.9, 1.4), "c1": (1.2, 0.8), "c2": (2.8, 0.8), "d": (1.2, -0.4)}
    mb = markov_blanket(par, "xi")
    fills = {n: MB_FILL for n in mb}
    fills["xi"] = OBS_FILL
    edges = [(p, n) for n, ps in par.items() for p in ps]
    labels = {n: _tex(n) for n in pos}
    labels.update({"xi": "$x_i$", "c1": "$c_1$", "c2": "$c_2$", "p1": "$p_1$", "p2": "$p_2$", "q1": "$q_1$", "q2": "$q_2$"})
    fig, ax = plt.subplots(figsize=(4.0, 4.3))
    draw_graph(ax, pos, edges, fills=fills, labels=labels, r=0.3, fs=11)
    _limits(ax, pos, 0.45)
    ax.add_patch(Rectangle((0, 0), 0, 0, fc=MB_FILL, ec=RED, label="Markov blanket (%d nodes)" % len(mb)))
    ax.legend(loc="lower right", fontsize=8.5, frameon=False, bbox_to_anchor=(1.05, -0.04))
    savefig(fig, CH, "fig11-25", out)


def fig_11_29(out=None):
    """First-order (Figure 11.29) and second-order (Figure 11.30) Markov chains."""
    fig, axes = plt.subplots(2, 1, figsize=(6.4, 2.9))
    pos = {"x%d" % i: (1.3 * i, 0) for i in range(1, 6)}
    labels = {n: _tex(n) for n in pos}
    labels["x5"] = "$\\cdots$"
    e1 = [("x%d" % i, "x%d" % (i + 1)) for i in range(1, 5)]
    e2 = e1 + [("x%d" % i, "x%d" % (i + 2)) for i in range(1, 4)]
    curved = {("x%d" % i, "x%d" % (i + 2)): -0.45 for i in range(1, 4)}
    for ax, edges, t in ((axes[0], e1, "first order (11.44)"), (axes[1], e2, "second order (11.46)")):
        draw_graph(ax, pos, edges, labels=labels, curved=curved, fills={"x5": "white"})
        ax.set_xlim(0.8, 7.0)
        ax.set_ylim(-0.45, 1.05)
        ax.text(0.85, 0.75, t, fontsize=9.5, ha="left")
    savefig(fig, CH, "fig11-29", out)


def fig_11_31(out=None):
    """The state-space model (11.48): a Markov chain of latent z_n, each emitting an observed x_n."""
    fig, ax = plt.subplots(figsize=(5.6, 2.4))
    pos, edges, labels = {}, [], {}
    for i, lab in enumerate(["1", "2", "3", "N"]):
        x = 1.4 * i
        pos["z" + lab], pos["x" + lab] = (x, 1.2), (x, 0)
        labels["z" + lab], labels["x" + lab] = "$z_{%s}$" % lab, "$x_{%s}$" % lab
        edges.append(("z" + lab, "x" + lab))
    edges += [("z1", "z2"), ("z2", "z3"), ("z3", "zN")]
    draw_graph(ax, pos, edges, observed=["x1", "x2", "x3", "xN"], labels=labels)
    ax.text(3.5, 1.2, "$\\cdots$", ha="center", va="center", fontsize=14, color=RED,
            bbox=dict(fc="white", ec="none", pad=0.5))
    _limits(ax, pos, 0.45)
    savefig(fig, CH, "fig11-31", out)


def fig_11_23(out=None):
    """Naive Bayes: axis-aligned Gaussian class conditionals factorise, their mixture p(x) does not."""
    g = np.linspace(0.0, 1.0, 300)
    X1, X2 = np.meshgrid(g, g)
    X = np.stack([X1, X2], -1)
    p1, p2 = nb_class_density(X, 0), nb_class_density(X, 1)
    px = NB_PARAMS["prior"][0] * p1 + NB_PARAMS["prior"][1] * p2
    post = NB_PARAMS["prior"][0] * p1 / px
    fig, axes = plt.subplots(1, 3, figsize=(9.6, 3.3))
    levels = lambda Z: np.max(Z) * np.array([0.03, 0.1, 0.2, 0.35, 0.5, 0.7, 0.9])
    axes[0].contour(X1, X2, p1, levels=levels(p1), cmap="Reds", vmin=-0.5 * p1.max(), vmax=p1.max())
    axes[0].contour(X1, X2, p2, levels=levels(p2), cmap="Blues", vmin=-0.5 * p2.max(), vmax=p2.max())
    axes[0].text(0.36, 0.10, "$p(\\mathbf{x}\\mid\\mathcal{C}_1)$", fontsize=10, color=RED)
    axes[0].text(0.62, 0.42, "$p(\\mathbf{x}\\mid\\mathcal{C}_2)$", fontsize=10, color=BLUE)
    axes[1].contour(X1, X2, px, levels=levels(px), cmap="Greens", vmin=-0.5 * px.max(), vmax=px.max())
    axes[1].text(0.68, 0.36, "$p(\\mathbf{x})$", fontsize=10, color=GREEN)
    cs = axes[2].contourf(X1, X2, post, levels=np.linspace(0, 1, 11), cmap="RdBu_r", alpha=0.85)
    axes[2].contour(X1, X2, post, levels=[0.5], colors="k", linewidths=1.2)
    axes[2].set_title("$p(\\mathcal{C}_1\\mid\\mathbf{x})$ (black: 0.5)", fontsize=9.5)
    for ax, lab in zip(axes, "abc"):
        ax.set_xlim(0.0, 1.0)
        ax.set_ylim(0.05, 0.95)
        ax.set_xlabel("$x_1$")
        ax.set_ylabel("$x_2$")
        ax.set_xticks([])
        ax.set_yticks([])
        ax.set_aspect("equal")
        panel_label(ax, lab)
    fig.colorbar(cs, ax=axes[2], fraction=0.046, pad=0.04)
    savefig(fig, CH, "fig11-23", out)


def fig_s1(out=None):
    """Parameter counts: joint tables against graphs, tables against parametric conditionals, Markov order."""
    fig, axes = plt.subplots(1, 3, figsize=(10.2, 3.2))
    M = np.arange(1, 21)
    K = 3
    ax = axes[0]
    ax.semilogy(M, [n_params_full(K, m) for m in M], "o-", color=RED, ms=3, label="fully connected $K^M-1$")
    ax.semilogy(M, [n_params_chain(K, m) for m in M], "s-", color=BLUE, ms=3, label="chain (Fig. 11.4)")
    ax.semilogy(M, [n_params_shared_chain(K)] * len(M), "-", color=GREEN, label="tied chain $K^2-1$")
    ax.semilogy(M, [n_params_independent(K, m) for m in M], "--", color=GREY, label="no links $M(K-1)$")
    ax.set_xlabel("number of variables $M$ ($K=3$ states)")
    ax.set_ylabel("free parameters")
    ax.legend(fontsize=7.5)
    ax = axes[1]
    ax.semilogy(M, 2.0 ** M, "o-", color=RED, ms=3, label="table $2^M$")
    ax.semilogy(M, M + 1, "s-", color=BLUE, ms=3, label="logistic (11.8): $M+1$")
    ax.semilogy(M, M + 1, ":", color=ORANGE, lw=2.5, label="noisy-OR (11.49): $M+1$")
    ax.set_xlabel("number of binary parents $M$")
    ax.set_ylabel("parameters of $p(y\\mid x_1,\\ldots,x_M)$")
    ax.legend(fontsize=7.5)
    ax = axes[2]
    ks = np.arange(0, 11)
    ax.semilogy(ks, [n_params_markov_order(K_TEXT, k) for k in ks], "o-", color=RED, ms=3, label="$K^k(K-1)$, $K=28$")
    t, split = alice()
    seen = [len(ngram_counts(t, split, k)) * (K_TEXT - 1) for k in ks]
    ax.semilogy(ks, seen, "s-", color=BLUE, ms=3, label="(contexts seen in the text) $\\times (K-1)$")
    ax.axhline(split, color=GREY, ls="--", lw=1)
    ax.text(0.2, split * 1.6, "training characters", fontsize=8, color=GREY)
    ax.set_xlabel("Markov order $k$")
    ax.set_ylabel("parameters of the transition table")
    ax.legend(fontsize=7.5, loc="lower right")
    for a, lab, loc in zip(axes, "abc", ("lower right", "lower right", "upper left")):
        panel_label(a, lab, loc)
    fig.tight_layout()
    savefig(fig, CH, "fig11-s1", out)


def fig_s2(out=None):
    """Explaining away: p(F = 0 | evidence) for the gauge (11.32)-(11.35) and for the driver (Exercise 11.14)."""
    J, nodes = fuel_network(driver=(0.9, 0.9)).joint(), fuel_network(driver=(0.9, 0.9)).nodes
    cases = [("none", {}), ("G=0", {"G": 0}), ("G=0, B=0", {"G": 0, "B": 0}), ("D=0", {"D": 0}),
             ("D=0, B=0", {"D": 0, "B": 0}), ("G=0, B=1", {"G": 0, "B": 1})]
    vals = [conditional(J, nodes, "F", ev)[0] for _, ev in cases]
    valsB = [np.nan if "B" in ev else conditional(J, nodes, "B", ev)[0] for _, ev in cases]
    fig, ax = plt.subplots(figsize=(7.2, 3.1))
    x = np.arange(len(cases))
    ax.bar(x - 0.19, vals, 0.38, color=RED, label="$p(F{=}0\\mid$ evidence$)$: tank empty")
    ax.bar(x + 0.19, valsB, 0.38, color=BLUE, alpha=0.75, label="$p(B{=}0\\mid$ evidence$)$: battery flat")
    for xi, v in zip(x, vals):
        ax.text(xi - 0.19, v + 0.012, "%.3f" % v, ha="center", fontsize=8)
    for xi, v, (_, ev) in zip(x, valsB, cases):
        if "B" not in ev:
            ax.text(xi + 0.19, v + 0.012, "%.3f" % v, ha="center", fontsize=8)
    ax.set_xticks(x)
    ax.set_xticklabels(["evidence: " + c[0] if i == 0 else c[0] for i, c in enumerate(cases)], fontsize=8.5)
    ax.set_ylim(0, 1.08)
    ax.set_ylabel("posterior probability")
    ax.legend(fontsize=8, loc="upper left")
    savefig(fig, CH, "fig11-s2", out)
    return vals


def fig_s3(out=None, N=2000, seed=7):
    """Ancestral samples of the Figure 11.7 chain against the derived mean and covariance; the precision matrix."""
    W, b, v = FIG_11_7["W"], FIG_11_7["b"], FIG_11_7["v"]
    X = lg_sample_js(W, b, v, N, seed)
    mu, S = lg_moments(W, b, v)
    Lam = lg_precision(W, v)
    fig, axes = plt.subplots(1, 4, figsize=(11.2, 2.9))
    for ax, (i, j) in zip(axes, [(0, 1), (1, 2), (0, 2)]):
        ax.plot(X[:, i], X[:, j], ".", ms=1.6, color=GREY, alpha=0.5)
        for nsd, ls in ((1, "-"), (2, "--")):
            ex, ey = common.ellipse_xy(mu[[i, j]], S[np.ix_([i, j], [i, j])], nsd)
            ax.plot(ex, ey, ls, color=RED, lw=1.5)
        ms, Ss = sample_moments(X)
        ex, ey = common.ellipse_xy(ms[[i, j]], Ss[np.ix_([i, j], [i, j])], 2)
        ax.plot(ex, ey, ":", color=BLUE, lw=1.5)
        ax.set_xlabel("$x_%d$" % (i + 1))
        ax.set_ylabel("$x_%d$" % (j + 1))
        r = S[i, j] / np.sqrt(S[i, i] * S[j, j])
        ax.set_title("$\\rho_{%d%d}=%.2f$" % (i + 1, j + 1, r), fontsize=9.5)
    ax = axes[3]
    ax.imshow(Lam, cmap="RdBu_r", vmin=-np.abs(Lam).max(), vmax=np.abs(Lam).max())
    for i in range(3):
        for j in range(3):
            ax.text(j, i, "%.2f" % Lam[i, j], ha="center", va="center", fontsize=9)
    ax.set_xticks(range(3))
    ax.set_yticks(range(3))
    ax.set_xticklabels(["$x_1$", "$x_2$", "$x_3$"])
    ax.set_yticklabels(["$x_1$", "$x_2$", "$x_3$"])
    ax.set_title("precision $\\Lambda=\\Sigma^{-1}$", fontsize=9.5)
    fig.tight_layout()
    savefig(fig, CH, "fig11-s3", out)
    return X


def fig_s4(out=None):
    """Order-k Markov models of text: held-out and training cross-entropy against k and against the parameter count."""
    rows = text_table(10)
    ks = [r["k"] for r in rows]
    fig, axes = plt.subplots(1, 2, figsize=(9.4, 3.4))
    ax = axes[0]
    style = {"1": (RED, "o-", "$\\alpha=1$"), "0.1": (ORANGE, "o-", "$\\alpha=0.1$"), "0.01": (BLUE, "o-", "$\\alpha=0.01$"),
             "0.1_bo": (GREEN, "s--", "$\\alpha=0.1$, back off")}
    for key, (c, ls, lab) in style.items():
        ax.plot(ks, [r["test_" + key] for r in rows], ls, color=c, ms=3.5, label=lab)
        ax.plot(ks, [r["train_" + key] for r in rows], ":", color=c, lw=1.2)
    ax.axhline(math.log2(K_TEXT), color=GREY, ls="--", lw=1)
    ax.text(5.6, math.log2(K_TEXT) + 0.08, "uniform: $\\log_2 28$", fontsize=8, color=GREY)
    ax.set_xlabel("Markov order $k$")
    ax.set_ylabel("bits per character")
    ax.set_ylim(0, 5.2)
    ax.legend(fontsize=7.5, loc="lower left", title="held out (dotted: training)", title_fontsize=7.5)
    ax = axes[1]
    t, split = alice()
    for key in ("1", "0.01", "0.1_bo"):
        c, ls, lab = style[key]
        best = min(rows, key=lambda r: r["test_" + key])
        ax.plot([r["params"] for r in rows[1:]], [r["test_" + key] for r in rows[1:]], ls, color=c, ms=3.5,
                label="%s (best $k=%d$)" % (lab, best["k"]))
    ax.set_xscale("log")
    ax.axvline(split, color=GREY, ls="--", lw=1)
    ax.text(split * 1.3, 3.9, "number of\ntraining\ncharacters", fontsize=8, color=GREY)
    ax.set_xlabel("parameters $K^k(K-1)$ of the order-$k$ table")
    ax.set_ylabel("held-out bits per character")
    ax.legend(fontsize=7.5, loc="lower right")
    for a, lab in zip(axes, "ab"):
        panel_label(a, lab, "upper right")
    fig.tight_layout()
    savefig(fig, CH, "fig11-s4", out)
    return rows


def fig_s5(out=None):
    """A hidden Markov model is not Markov at any order: I(x_{n+1}; x_{n-k} | the k symbols between) > 0."""
    fig, axes = plt.subplots(1, 2, figsize=(9.4, 3.2))
    ks = np.arange(1, 11)
    ax = axes[0]
    for stay, c in ((0.8, BLUE), (0.95, RED), (0.99, PURPLE)):
        A = np.array([[stay, 1 - stay], [1 - stay, stay]])
        cmi = [hmm_lag_cmi(HMM_DEFAULT["pi"], A, HMM_DEFAULT["E"], int(k)) for k in ks]
        ax.semilogy(ks, cmi, "o-", color=c, ms=3.5, label="HMM, $p(z_{n}=z_{n-1})=%g$" % stay)
    ax.set_xlabel("order $k$ of the Markov approximation")
    ax.set_ylabel("$I(x_{n+1}; x_{n-k}\\mid x_{n-k+1:n})$ (nats)")
    ax.legend(fontsize=7.5)
    ax.set_title("a $k$th-order chain would give 0 for every $k$", fontsize=9)
    ax = axes[1]
    pi, A, E = HMM_DEFAULT["pi"], HMM_DEFAULT["A"], HMM_DEFAULT["E"]
    n, gaps = 40, range(1, 21)
    pr = {}
    for first in (1, 0):
        pr[first] = np.array([hmm_predictive(pi, A, E, [0] * (n - g - 6) + [first] * 6 + [0] * g)[1] for g in gaps])
    ax.semilogy(list(gaps), pr[1] - pr[0], "o-", ms=3.5, color=RED)
    ax.set_xlabel("$g$: zeros observed since the block of six symbols")
    ax.set_ylabel("difference in $p(x_{n+1}=1\\mid x_{1:n})$")
    ax.set_title("history $\\ldots 0\\,111111\\,0^g$ minus history $\\ldots 0\\,000000\\,0^g$", fontsize=9)
    for a, lab in zip(axes, "ab"):
        panel_label(a, lab, "upper right")
    fig.tight_layout()
    savefig(fig, CH, "fig11-s5", out)


# =========================================================================== demo data
def export_demo_data(out=None):
    """The cleaned text for markov-text-demo.html."""
    t, split = alice()
    os.makedirs(DATA_OUT, exist_ok=True)
    path = os.path.join(DATA_OUT, "ch11-alice.json")
    with open(path, "w") as f:
        json.dump({"source": "Lewis Carroll, Alice's Adventures in Wonderland (1865), public domain; "
                             "cleaned to 28 symbols by clean_text() in ch11_structured_distributions.py",
                   "alphabet": ALPHABET, "split": split, "prompt": PROMPT, "text": t}, f, separators=(",", ":"))
    print("wrote", os.path.relpath(path, os.getcwd()))


FIGURES = {
    "11.2": fig_11_2, "11.14": fig_11_14, "11.20": fig_11_20, "11.21": fig_11_21, "11.23": fig_11_23,
    "11.25": fig_11_25, "11.29": fig_11_29, "11.31": fig_11_31,
    "s1": fig_s1, "s2": fig_s2, "s3": fig_s3, "s4": fig_s4, "s5": fig_s5,
    "data": export_demo_data,
}

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