"""Wasserman (2004), Chapter 19: Log-Linear Models.

Companion code for Chapter 19 of L. Wasserman, All of Statistics: A Concise Course in Statistical
Inference (Springer, 2004), pp. 291-301, written from scratch with numpy, scipy and matplotlib. The
functions are short and meant to be read next to the lecture notes (../ch19-log-linear-models.html):

* Section 19.1, the log-linear expansion: psi_terms (the corner-point expansion of Theorem 19.1 by
  Moebius inversion: psi_A(x) = sum over B in A of (-1)^{|A - B|} log f(x_B, 0 elsewhere)), expand (the
  sum back), beta_vector (the free parameters, prod_{j in A}(r_j - 1) per term), and ci_by_terms (the
  criterion of Theorem 19.4: no psi-term meets both b and c).
* Sections 19.2 to 19.4, graphical, hierarchical and generated models: terms are tuples of 0-based
  variable indices; closure (the hierarchical model of a generator such as "1.2+2.3"), parse and
  generator_string (the book's notation), is_hierarchical, term_graph (the graph of a model: an edge for
  every pair inside a term), complete_sets, is_graphical (the terms are exactly the complete sets of
  their graph), maximal_cliques and hierarchical_models (all hierarchical models on m variables).
* Section 19.5, fitting: design (corner-point dummy coding, as R's glm with treatment contrasts),
  newton_poisson (Newton-Raphson for the Poisson log-linear model, with standard errors from the inverse
  Fisher information; confirmed against statsmodels), ipf (iterative proportional fitting: Algorithm
  19.A of the notes, with its full history), closed_form (the explicit MLE of a decomposable three-way
  model), fit_model (log-likelihood, deviance, degrees of freedom, AIC and BIC in the book's convention
  ell - |M| and ell - |M| log(n) / 2), backward_search (backward elimination over hierarchical models,
  as in Example 19.15) and select (every hierarchical model of a three-way table, scored).
* Data: BREAST, the breast cancer table of Example 19.15 (Morrison et al., 1973), and coris_table, a
  2 x 2 x 3 table from the book's coris.dat (coronary heart disease by family history and age group).
* JSRandom and js_multinomial: the seeded generator of the browser demonstrations (DK.rng in
  courses/demo-kit.js) and its multinomial sampler, so that the demos' simulated tables are reproduced
  here count for count.

Figures. The five figures of the chapter are drawings of graphs. They are redrawn from their edge
lists, and each drawing carries what is computed from the graph and the model it illustrates (its
maximal cliques, the generator of its graphical model, whether the book's model is hierarchical and
graphical, and for Figure 19.5 the fit of the selected model). Nothing is skipped. Four
supplementary figures illustrate gaps filled in the notes:
  19.S1 iterative proportional fitting: one cycle for a decomposable model, linear convergence for the
        no-three-way model, and slow convergence to the boundary when the MLE does not exist;
  19.S2 model selection across the nine hierarchical models of the breast cancer table (deviance, AIC);
  19.S3 the deviance and the likelihood ratio between nested models against their chi-squared limits;
  19.S4 how often AIC, BIC and deviance testing recover a weak interaction, as the sample size grows.
Run `python3 ch19_log_linear_models.py --list`, `python3 ch19_log_linear_models.py` (all nine
figures, under a minute on one CPU thread) or `python3 ch19_log_linear_models.py --fig 19.S1`.
Files go to ../img/ch19/; the tables used by the demonstrations are written to
../data/ch19-tables.json by export_json() (run with the figures).
"""
import itertools
import json
import math
import os

import numpy as np
from scipy import stats

import common
from common import BLUE, GREEN, GREY, MAGENTA, ORANGE, PURPLE, RED, savefig

CH = 19
M32 = 0xFFFFFFFF

# The breast cancer data of Example 19.15 (Morrison et al., 1973), axes (centre, grade, survival):
# centre 0 = Boston, 1 = Glamorgan; grade 0 = malignant, 1 = benign; survival 0 = died, 1 = survived.
# Level 0 of each variable is R's default reference level, so the corner-point parameters below are the
# coefficients printed in the book.
BREAST = np.array([[[35, 59], [47, 112]], [[42, 77], [26, 76]]], dtype=float)
BREAST_VARS = ["centre", "grade", "survival"]
BREAST_LEVELS = [["Boston", "Glamorgan"], ["malignant", "benign"], ["died", "survived"]]

# The nine hierarchical models of a three-way table that keep all three main effects, in the book's
# generator notation, from the smallest to the saturated model.
NINE = ["1+2+3", "1.2+3", "1.3+2", "2.3+1", "1.2+1.3", "1.2+2.3", "1.3+2.3", "1.2+1.3+2.3", "1.2.3"]


# =========================================================================== 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): u() is
    mulberry32, exactly as in JavaScript."""

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

    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 js_multinomial(p, n, seed):
    """n draws from the cell probabilities p (any shape) by inversion of the cumulative sum, one u() per
    draw, as the selection demo does; returns counts of the same shape."""
    flat = np.asarray(p, dtype=float).ravel()
    cum = np.cumsum(flat / flat.sum())
    rng = JSRandom(seed)
    out = np.zeros(flat.size)
    for _ in range(int(n)):
        u = rng.u()
        k = 0
        while k < flat.size - 1 and u >= cum[k]:
            k += 1
        out[k] += 1
    return out.reshape(np.shape(p))


# =========================================================================== terms and models
def subsets(S):
    """All subsets of the tuple S, ordered by size and then lexicographically (the empty set first)."""
    S = tuple(sorted(S))
    return [c for k in range(len(S) + 1) for c in itertools.combinations(S, k)]


def all_terms(m):
    return subsets(range(m))


def closure(gens):
    """The hierarchical model generated by gens: every subset of every generator (with the empty term)."""
    out = {()}
    for g in gens:
        out.update(subsets(g))
    return sorted(out, key=lambda t: (len(t), t))


def parse(gen):
    """The book's generator notation, e.g. '1.2+2.3' (1-based) -> [(0, 1), (1, 2)]."""
    return [tuple(sorted(int(v) - 1 for v in part.split("."))) for part in gen.replace(" ", "").split("+")]


def maximal(terms):
    """The terms not contained in another term (the generators of a hierarchical model)."""
    T = [tuple(t) for t in terms if len(t)]
    return sorted([t for t in T if not any(set(t) < set(u) for u in T)], key=lambda t: (-len(t), t))


def generator_string(terms):
    g = maximal(terms)
    if not g:
        return "(uniform)"
    return " + ".join(".".join(str(v + 1) for v in t) for t in sorted(g, key=lambda t: (-len(t), t)))


def is_hierarchical(terms):
    T = set(map(tuple, terms)) | {()}
    return all(set(subsets(t)) <= T for t in T)


def term_graph(terms, m):
    """Edges (i, j), i < j, of the graph of a model: i and j are joined when some term contains both."""
    E = set()
    for t in terms:
        for i, j in itertools.combinations(sorted(t), 2):
            E.add((i, j))
    return sorted(E)


def complete_sets(edges, m):
    """Every subset of {0..m-1} (with the empty set) whose pairs are all edges."""
    E = set(map(tuple, edges))
    return [A for A in all_terms(m) if all((i, j) in E for i, j in itertools.combinations(A, 2))]


def is_graphical(terms, m):
    """Definition 19.6: the terms are exactly the complete sets of the model's graph."""
    T = set(map(tuple, terms)) | {()}
    return T == set(complete_sets(term_graph(terms, m), m))


def maximal_cliques(edges, m):
    return maximal(complete_sets(edges, m)) or []


def hierarchical_models(m, all_main=False):
    """Every hierarchical model on m variables as a sorted list of terms (down-sets of the subset lattice
    containing the empty set); with all_main, only those with every main effect."""
    nonempty = [t for t in all_terms(m) if t]
    out = []
    for mask in range(1 << len(nonempty)):
        T = [()] + [nonempty[k] for k in range(len(nonempty)) if mask >> k & 1]
        if is_hierarchical(T) and (not all_main or all((v,) in T for v in range(m))):
            out.append(sorted(T, key=lambda t: (len(t), t)))
    return out


def ci_by_terms(terms, a, b, c):
    """Theorem 19.4: X_b indep X_c given X_a holds for every f in the model when no term meets both b and c."""
    return not any(set(t) & set(b) and set(t) & set(c) for t in terms)


# =========================================================================== the log-linear expansion
def _corner(logf, B):
    """log f(x_B, 0 elsewhere) as an array over x_B (axes in increasing order of B)."""
    idx = tuple(slice(None) if j in B else 0 for j in range(logf.ndim))
    return logf[idx]


def psi_terms(logf):
    """The corner-point log-linear expansion (Theorem 19.1): a dict A -> array over x_A with
    psi_A(x_A) = sum_{B in A} (-1)^{|A|-|B|} log f(x_B, 0_{S-B}). Zero whenever some x_j = 0, j in A."""
    logf = np.asarray(logf, dtype=float)
    m = logf.ndim
    out = {}
    for A in all_terms(m):
        shp = [logf.shape[j] for j in A]
        tot = np.zeros(shp)
        for B in subsets(A):
            v = _corner(logf, B)                      # array over x_B
            shape_b = [logf.shape[j] if j in B else 1 for j in A]
            tot = tot + (-1) ** (len(A) - len(B)) * v.reshape(shape_b)
        out[A] = tot
    return out


def expand(psi, shape):
    """Sum of the psi-terms as a full table over x (the inverse of psi_terms)."""
    m = len(shape)
    tot = np.zeros(shape)
    for A, v in psi.items():
        tot = tot + np.asarray(v).reshape([shape[j] if j in A else 1 for j in range(m)])
    return tot


def beta_vector(psi, shape):
    """The free parameters beta_A: the values of psi_A at x_A with every coordinate non-zero, term by
    term (the empty term first), as R orders a saturated glm with treatment contrasts."""
    names, vals = [], []
    for A in sorted(psi, key=lambda t: (len(t), t)):
        v = np.asarray(psi[A])
        for lev in itertools.product(*[range(1, shape[j]) for j in A]):
            names.append((A, lev))
            vals.append(float(v[lev]) if A else float(v))
    return names, np.array(vals)


def n_params(shape, terms):
    """|M| = sum over terms A of prod_{j in A} (r_j - 1), the empty term counting 1 (as the book does)."""
    return int(sum(np.prod([shape[j] - 1 for j in t]) if t else 1 for t in set(map(tuple, terms)) | {()}))


# =========================================================================== Poisson log-linear fit
def design(shape, terms):
    """Corner-point design matrix: one row per cell (C order), one column per (term, non-zero levels)."""
    cells = list(np.ndindex(*shape))
    cols, names = [], []
    for A in sorted(set(map(tuple, terms)) | {()}, key=lambda t: (len(t), t)):
        for lev in itertools.product(*[range(1, shape[j]) for j in A]):
            cols.append([float(all(x[j] == l for j, l in zip(A, lev))) for x in cells])
            names.append((A, lev))
    return np.array(cols).T, names


def newton_poisson(y, X, tol=1e-12, maxit=100):
    """Maximise sum y log mu - mu with log mu = X beta by Newton-Raphson (= Fisher scoring here, since
    the log link is canonical). Returns beta, its covariance (inverse Fisher information), iterations."""
    y = np.asarray(y, dtype=float)
    beta = np.zeros(X.shape[1])
    beta[0] = math.log(max(y.mean(), 1e-12))
    for it in range(1, maxit + 1):
        mu = np.exp(X @ beta)
        grad = X.T @ (y - mu)
        info = X.T @ (mu[:, None] * X)
        step = np.linalg.solve(info, grad)
        beta = beta + step
        if np.max(np.abs(step)) < tol:
            break
    mu = np.exp(X @ beta)
    cov = np.linalg.inv(X.T @ (mu[:, None] * X))
    return beta, cov, it


def fit_glm(counts, terms):
    """Coefficient table (beta, se, Wald W, two-sided p) of a Poisson log-linear model with corner-point
    coding, as R's summary(glm(..., family = poisson)) prints it."""
    counts = np.asarray(counts, dtype=float)
    X, names = design(counts.shape, terms)
    beta, cov, it = newton_poisson(counts.ravel(), X)
    se = np.sqrt(np.diag(cov))
    W = beta / se
    p = 2 * stats.norm.sf(np.abs(W))
    return {"names": names, "beta": beta, "se": se, "W": W, "p": p, "cov": cov, "iters": it,
            "fitted": np.exp(X @ beta).reshape(counts.shape)}


def term_label(A, lev, var_names):
    if not A:
        return "(Intercept)"
    return "×".join(var_names[j] for j in A)


# =========================================================================== iterative proportional fitting
def margin(t, A):
    """The A-margin of a table, kept with singleton axes so that it broadcasts."""
    axes = tuple(j for j in range(t.ndim) if j not in A)
    return t.sum(axis=axes, keepdims=True) if axes else t


def loglik(counts, m):
    """Multinomial log-likelihood sum n_x log(m_x / n) at fitted values m (with 0 log 0 = 0)."""
    counts = np.asarray(counts, dtype=float)
    n = counts.sum()
    pos = counts > 0
    with np.errstate(divide="ignore"):
        return float(np.sum(counts[pos] * np.log(m[pos] / n)))


def deviance(counts, m):
    counts = np.asarray(counts, dtype=float)
    pos = counts > 0
    return float(2 * np.sum(counts[pos] * np.log(counts[pos] / m[pos])))


def pearson(counts, m):
    pos = m > 0
    return float(np.sum((counts[pos] - m[pos]) ** 2 / m[pos]))


def margin_error(counts, m, gens):
    return max(float(np.max(np.abs(margin(m, C) - margin(counts, C)))) for C in gens)


def ipf(counts, gens, tol=1e-10, maxit=10000, start=None, history=False):
    """Iterative proportional fitting (Algorithm 19.A of the notes). Starts from the uniform table with
    the right total (or from `start`), and cycles through the generators C, rescaling the fitted table so
    that its C-margin equals the observed one: m <- m * n_C / m_C. Stops when every generator margin is
    within tol. With history=True, also returns the log-likelihood and the largest margin error after
    every single adjustment."""
    counts = np.asarray(counts, dtype=float)
    gens = [tuple(g) for g in gens]
    m = np.full(counts.shape, counts.sum() / counts.size) if start is None else np.array(start, dtype=float)
    hist = {"ll": [loglik(counts, m)], "err": [margin_error(counts, m, gens)], "gen": [None]}
    cycles = 0
    for cycles in range(1, maxit + 1):
        for C in gens:
            mc, nc = margin(m, C), margin(counts, C)
            with np.errstate(divide="ignore", invalid="ignore"):
                ratio = np.where(mc > 0, nc / mc, 0.0)
            m = m * ratio
            if history:
                hist["ll"].append(loglik(counts, m))
                hist["err"].append(margin_error(counts, m, gens))
                hist["gen"].append(C)
        if margin_error(counts, m, gens) < tol:
            break
    return (m, cycles, hist) if history else (m, cycles)


def closed_form(counts, gens):
    """Explicit MLE of the decomposable models of a three-way table (every hierarchical model on three
    variables except 1.2+1.3+2.3): the product of the generator margins, divided by the margin of each
    variable shared by two generators and by n once for each extra connected component; a variable that
    appears in no term is uniform, so its r_v cells share each fitted count equally."""
    counts = np.asarray(counts, dtype=float)
    n = counts.sum()
    G = maximal(closure([tuple(g) for g in gens]))
    if (0, 1, 2) in G:
        return counts.copy()
    if all(e in G for e in ((0, 1), (0, 2), (1, 2))):
        raise ValueError("1.2+1.3+2.3 has no closed form")
    m = np.ones(counts.shape)
    for g in G:
        m = m * margin(counts, g)
    for v in range(counts.ndim):
        for _ in range(max(sum(v in g for g in G) - 1, 0)):
            m = m / margin(counts, (v,))
    comps = []
    for g in G:
        hit = [c for c in comps if c & set(g)]
        comps = [c for c in comps if c not in hit] + [set(g).union(*hit)]
    m = m / n ** (len(comps) - 1)
    for v in range(counts.ndim):
        if not any(v in g for g in G):
            m = m / counts.shape[v]
    return m


def fit_model(counts, gens, tol=1e-10):
    """Everything Section 19.5 reports for one model: fitted values, ell (multinomial), |M|, deviance,
    residual degrees of freedom, p-value against the saturated model, the book's AIC = ell - |M| and
    BIC = ell - |M| log(n)/2, Pearson's X^2, and R's AIC (-2 x Poisson log-likelihood + 2|M|)."""
    counts = np.asarray(counts, dtype=float)
    G = parse(gens) if isinstance(gens, str) else [tuple(g) for g in gens]
    terms = closure(G)
    m, cycles = ipf(counts, maximal(terms) or [()], tol=tol)
    n = counts.sum()
    k = n_params(counts.shape, terms)
    ll = loglik(counts, m)
    dev = deviance(counts, m)
    df = counts.size - k
    llP = float(np.sum(stats.poisson.logpmf(counts, m)))
    return {"gens": generator_string(terms), "terms": terms, "fitted": m, "cycles": cycles, "ll": ll, "k": k,
            "dev": dev, "df": df, "p": float(stats.chi2.sf(dev, df)) if df > 0 else float("nan"),
            "aic": ll - k, "bic": ll - k * math.log(n) / 2, "X2": pearson(counts, m), "aicR": -2 * llP + 2 * k}


def select(counts, models=NINE):
    return [fit_model(counts, g) for g in models]


def backward_search(counts, crit="aic"):
    """Backward elimination over hierarchical models, as in Example 19.15: start from the saturated model
    and repeatedly remove the maximal term whose removal increases the criterion most (the book's
    convention: larger is better); stop when no removal helps. Returns the path of fits."""
    m = counts.ndim
    terms = all_terms(m)
    cur = fit_model(counts, maximal(terms))
    path = [cur]
    while True:
        best = None
        for A in maximal(cur["terms"]):
            T = [t for t in cur["terms"] if t != A]
            cand = fit_model(counts, maximal(T) or [()])
            if best is None or cand[crit] > best[crit]:
                best = cand
        if best is None or best[crit] <= cur[crit]:
            return path
        cur = best
        path.append(cur)


# =========================================================================== data
def coris_table():
    """coris.dat as a 2 x 2 x 3 table: coronary heart disease (no, yes) x family history (absent,
    present) x age group (15-39, 40-54, 55-64)."""
    import pandas as pd
    df = pd.read_csv(common.aos_file("coris.dat"), skiprows=[1, 2, 3], skipinitialspace=True)
    age = np.digitize(df["age"].to_numpy(), [40, 55])
    t = np.zeros((2, 2, 3))
    for c, f, a in zip(df["chd"].astype(int), df["famhist"].astype(int), age):
        t[c, f, a] += 1
    return t


CORIS_VARS = ["CHD", "family history", "age"]
CORIS_LEVELS = [["no", "yes"], ["absent", "present"], ["15-39", "40-54", "55-64"]]

# A table with two sampling zeros at opposite corners: every two-way margin is positive, but the MLE of
# the no-three-way model does not exist (Filling the gap 19.8); the breast cancer counts elsewhere.
ZEROS = BREAST.copy()
ZEROS[0, 0, 0] = 0
ZEROS[1, 1, 1] = 0

# Exercise 19.5: probabilities proportional to these values, axes (x1, x2, x3).
EX5 = np.array([[[2, 8], [4, 16]], [[16, 128], [32, 256]]], dtype=float)


# =========================================================================== drawing
def draw_graph(ax, names, edges, pos, shade=True, fs=12, r_lab=0.17):
    P = np.array([pos[k] for k in range(len(names))], dtype=float)
    if shade:
        for C in maximal_cliques(edges, len(names)):
            if len(C) >= 3:
                pts = P[list(C)]
                c0 = pts.mean(0)
                pts = pts[np.argsort(np.arctan2(pts[:, 1] - c0[1], pts[:, 0] - c0[0]))]
                ax.fill(pts[:, 0], pts[:, 1], color="#7f8fb0", alpha=0.25, lw=0)
    for i, j in edges:
        ax.plot([P[i, 0], P[j, 0]], [P[i, 1], P[j, 1]], color="k", lw=2.0, solid_capstyle="round", zorder=1)
    ax.scatter(P[:, 0], P[:, 1], s=40, color="k", zorder=3)
    y0, y1 = P[:, 1].min(), P[:, 1].max()
    for k, nm in enumerate(names):
        up = y1 - y0 < 1e-9 or P[k, 1] >= (y0 + y1) / 2
        ax.text(P[k, 0], P[k, 1] + (r_lab if up else -r_lab), nm, ha="center", va="center", fontsize=fs)
    ax.set_aspect("equal")
    ax.axis("off")
    span = max(np.ptp(P[:, 0]), np.ptp(P[:, 1]), 1.0)
    pad = 0.22 * span
    ax.set_xlim(P[:, 0].min() - pad, P[:, 0].max() + pad)
    ax.set_ylim(P[:, 1].min() - pad, P[:, 1].max() + pad)


def _xnames(m):
    return [r"$X_{%d}$" % (k + 1) for k in range(m)]


def _gen_tex(terms):
    return generator_string(terms).replace(" + ", r" $+$ ")


def _graph_figure(name, m, terms, pos, lines, size=(6.4, 2.3), split=0.45, names=None):
    edges = term_graph(terms, m)
    fig = common.plt.figure(figsize=size)
    ax = fig.add_axes([0.0, 0.0, split, 1.0])
    draw_graph(ax, names or _xnames(m), edges, pos)
    tx = fig.add_axes([split + 0.03, 0.0, 0.97 - split, 1.0])
    tx.axis("off")
    y = 0.92
    for ln in lines:
        tx.text(0.0, y, ln, fontsize=9.5, va="top", transform=tx.transAxes)
        y -= 0.135
    return savefig(fig, CH, name, None)


def _yes(b):
    return "yes" if b else "no"


def _clq(C):
    return r"$\{" + ",".join(str(v + 1) for v in C) + r"\}$"


# =========================================================================== book figures
EX197 = parse("1.2+2.3.5+3.4.5")


def fig_19_1(out_dir=None):
    """Figure 19.1: the graph of Example 19.7 and its graphical log-linear model."""
    m = 5
    terms = closure(EX197)
    edges = term_graph(terms, m)
    pos = {0: (0, 0), 1: (1, 0), 2: (2, 0), 3: (2, 1), 4: (1, 1)}
    missing = [(i, j) for i, j in itertools.combinations(range(m), 2) if (i, j) not in edges]
    nothree = closure([e for e in edges])
    lines = ["Maximal cliques: " + ", ".join(_clq(C) for C in maximal_cliques(edges, m)),
             "Graphical model: generator " + _gen_tex(terms),
             r"   %d of the $2^5=32$ $\psi$-terms (with $\psi_\emptyset$)" % len(terms),
             "Missing edges: " + ", ".join("%d%d" % (i + 1, j + 1) for i, j in missing),
             "Without the triangles: " + _gen_tex(nothree),
             r"   same graph, hierarchical %s, graphical %s" % (_yes(is_hierarchical(nothree)),
                                                                 _yes(is_graphical(nothree, m)))]
    fig = _graph_figure("fig19-1", m, terms, pos, lines, size=(7.0, 2.5), split=0.36)
    return fig


def fig_19_2(out_dir=None):
    """Figure 19.2: the graph of Example 19.10 (generator 1.2 + 1.3)."""
    terms = closure(parse("1.2+1.3"))
    pos = {1: (0, 0), 0: (1, 0), 2: (2, 0)}
    lines = ["Model: " + _gen_tex(terms),
             "hierarchical: %s, graphical: %s" % (_yes(is_hierarchical(terms)), _yes(is_graphical(terms, 3))),
             r"No term contains both 2 and 3:",
             r"   $X_2\perp\!\!\!\perp X_3\mid X_1$ (Theorem 19.4)"]
    return _graph_figure("fig19-2", 3, terms, pos, lines, size=(6.2, 1.7), split=0.42)


def fig_19_3(out_dir=None):
    """Figure 19.3: the complete graph of Example 19.11; its model 1.2+1.3+2.3 is hierarchical, not graphical."""
    terms = closure(parse("1.2+1.3+2.3"))
    pos = {0: (0, 1), 1: (1.2, 1), 2: (0.6, 0)}
    sat = closure(parse("1.2.3"))
    lines = ["Model: " + _gen_tex(terms),
             "hierarchical: %s, graphical: %s" % (_yes(is_hierarchical(terms)), _yes(is_graphical(terms, 3))),
             r"Graphical model of this graph: " + _gen_tex(sat),
             r"   (adds $\psi_{123}$; graphical: %s)" % _yes(is_graphical(sat, 3))]
    return _graph_figure("fig19-3", 3, terms, pos, lines, size=(6.2, 2.2), split=0.36)


def fig_19_4(out_dir=None):
    """Figure 19.4: the graph of Example 19.12; the model psi_0 + psi_3 + psi_12 is not hierarchical."""
    terms = [(), (2,), (0, 1)]
    pos = {0: (0, 0), 1: (1, 0), 2: (2, 0)}
    missing = [t for t in closure(maximal(terms)) if t not in terms]
    lines = [r"Model: $\psi_\emptyset+\psi_3+\psi_{12}$",
             "hierarchical: %s, graphical: %s" % (_yes(is_hierarchical(terms)), _yes(is_graphical(terms, 3))),
             r"Missing for hierarchy: " + ", ".join(r"$\psi_{%s}$" % "".join(str(v + 1) for v in t) for t in missing),
             "Hierarchical closure: " + _gen_tex(closure(maximal(terms)))]
    return _graph_figure("fig19-4", 3, terms, pos, lines, size=(6.2, 1.7), split=0.40)


def fig_19_5(out_dir=None):
    """Figure 19.5: the graph of the model selected for the breast cancer data (Example 19.15)."""
    path = backward_search(BREAST)
    best = path[-1]
    m = 3
    edges = term_graph(best["terms"], m)
    pos = {0: (0, 0), 1: (1.4, 0), 2: (2.8, 0)}
    fig = common.plt.figure(figsize=(6.6, 1.9))
    ax = fig.add_axes([0.0, 0.0, 0.5, 1.0])
    draw_graph(ax, ["Centre", "Grade", "Survival"], edges, pos, fs=11, r_lab=0.3)
    tx = fig.add_axes([0.53, 0.0, 0.47, 1.0])
    tx.axis("off")
    lines = ["Backward search by AIC: " + " $\\to$ ".join(p["gens"] for p in path),
             r"Selected: %s, $|M|=%d$" % (best["gens"], best["k"]),
             r"deviance %.2f on %d df, $p=%.3f$" % (best["dev"], best["df"], best["p"]),
             r"Centre $\perp\!\!\!\perp$ Survival $\mid$ Grade"]
    y = 0.9
    for ln in lines:
        tx.text(0.0, y, ln, fontsize=8.6, va="top", transform=tx.transAxes)
        y -= 0.21
    return savefig(fig, CH, "fig19-5", out_dir)


# =========================================================================== supplementary figures
def fig_19_s1(out_dir=None):
    """Figure 19.S1: iterative proportional fitting, step by step, on three tables."""
    cases = [("breast cancer, 1.2 + 2.3 (decomposable)", BREAST, parse("1.2+2.3"), BLUE, "-"),
             ("breast cancer, 1.2 + 1.3 + 2.3", BREAST, parse("1.2+1.3+2.3"), RED, "-"),
             ("coris (2x2x3), 1.2 + 1.3 + 2.3", coris_table(), parse("1.2+1.3+2.3"), GREEN, "-"),
             ("zeros at 000 and 111, 1.2 + 1.3 + 2.3", ZEROS, parse("1.2+1.3+2.3"), ORANGE, "--")]
    fig, axes = common.panel_grid(1, 2, size=(3.6, 2.9))
    for lab, t, G, col, ls in cases:
        m, cyc, h = ipf(t, G, tol=0, maxit=1000 // len(G) + 1, history=True)
        # the maximum: the MLE when it exists; for the zeros table the fibre of non-negative tables with the
        # observed two-way margins is the observed table alone, so IPF converges to it (Filling the gap 19.8)
        llhat = loglik(t, t) if "zeros" in lab else fit_model(t, G, tol=1e-13)["ll"]
        k = np.arange(len(h["ll"]))
        gap = np.maximum(llhat - np.array(h["ll"]), 1e-16)
        axes[0, 0].loglog(k[1:1001], gap[1:1001], color=col, ls=ls, lw=1.4, label=lab)
        axes[0, 1].loglog(k[1:1001], np.maximum(h["err"][1:1001], 1e-16), color=col, ls=ls, lw=1.4)
    for ax, lab in ((axes[0, 0], r"$\hat\ell-\ell_t$"), (axes[0, 1], "largest margin error (counts)")):
        ax.set_xlim(1, 1000)
        ax.set_ylim(1e-14, 1e3)
        ax.set_xlabel("margin adjustments $t$")
        ax.set_ylabel(lab)
    common.panel_label(axes[0, 0], "a", "upper right")
    common.panel_label(axes[0, 1], "b", "upper right")
    fig.legend(*axes[0, 0].get_legend_handles_labels(), loc="lower center", ncol=2, fontsize=7.5, frameon=False,
               bbox_to_anchor=(0.5, -0.12))
    fig.tight_layout()
    return savefig(fig, CH, "fig19-S1", out_dir)


def hasse_positions():
    """Positions of the nine models of NINE for the lattice drawings (smallest at the bottom)."""
    return {"1+2+3": (0, 0), "1.2+3": (-1.6, 1), "1.3+2": (0, 1), "2.3+1": (1.6, 1),
            "1.2+1.3": (-1.6, 2), "1.2+2.3": (0, 2), "1.3+2.3": (1.6, 2), "1.2+1.3+2.3": (0, 3), "1.2.3": (0, 4)}


def hasse_edges():
    """Pairs (smaller, larger) of the nine models that differ by one term."""
    T = {g: set(closure(parse(g))) for g in NINE}
    return [(a, b) for a in NINE for b in NINE if T[a] < T[b] and len(T[b] - T[a]) == 1]


def fig_19_s2(out_dir=None):
    """Figure 19.S2: deviance and AIC of the nine hierarchical models of the breast cancer table."""
    fits = dict(zip(NINE, select(BREAST)))
    path = [p["gens"].replace(" ", "") for p in backward_search(BREAST)]
    best = max(NINE, key=lambda g: fits[g]["aic"])
    pos = hasse_positions()
    fig = common.plt.figure(figsize=(7.6, 3.5))
    ax = fig.add_axes([0.0, 0.02, 0.5, 0.96])
    for a, b in hasse_edges():
        on = a in path and b in path and abs(path.index(a) - path.index(b)) == 1
        ax.plot(*zip(pos[a], pos[b]), color=RED if on else "#bbbbbb", lw=2.2 if on else 0.8, zorder=1)
    for g in NINE:
        f = fits[g]
        x, y = pos[g]
        col = BLUE if g == best else ("#2b2b2b" if f["p"] >= 0.05 or f["df"] == 0 else GREY)
        ax.text(x, y, "%s\nAIC %.2f\ndev %.2f (%d)" % (g, f["aic"], f["dev"], f["df"]), ha="center", va="center",
                fontsize=7, color=col, bbox=dict(boxstyle="round,pad=0.25", fc="white",
                                                  ec=BLUE if g == best else ("#999999" if f["p"] < 0.05 else "k"),
                                                  lw=1.6 if g == best else 0.7), zorder=3)
    ax.set_xlim(-2.5, 2.5)
    ax.set_ylim(-0.5, 4.5)
    ax.axis("off")
    ax.set_title("(a) red: backward search by AIC; blue: selected", fontsize=8.5)
    bx = fig.add_axes([0.59, 0.15, 0.39, 0.75])
    for g in NINE:
        f = fits[g]
        bx.scatter(f["df"], f["dev"], s=22, color=BLUE if g == best else ("k" if f["p"] >= 0.05 or f["df"] == 0 else GREY),
                   zorder=3)
        bx.annotate(g, (f["df"], f["dev"]), xytext=(4, 2), textcoords="offset points", fontsize=6.5)
    d = np.linspace(0.5, 4.5, 50)
    bx.plot(d, stats.chi2.ppf(0.95, d), color=RED, lw=1.0, ls="--", label=r"$\chi^2_{\nu,0.05}$")
    bx.set_yscale("symlog", linthresh=1)
    bx.set_xlabel(r"residual degrees of freedom $\nu$")
    bx.set_ylabel("deviance")
    bx.set_xticks(range(5))
    bx.legend(fontsize=7.5, loc="upper left")
    bx.set_title("(b) deviance against its 5% critical value", fontsize=8.5)
    return savefig(fig, CH, "fig19-S2", out_dir)


def null_deviances(gens_small, gens_big, p_true, n, R, seed):
    """R tables of size n from p_true; the deviances of two nested models and their difference."""
    rng = np.random.default_rng(seed)
    G0, G1 = parse(gens_small), parse(gens_big)
    out = np.zeros((R, 2))
    for r in range(R):
        t = rng.multinomial(n, p_true.ravel()).reshape(p_true.shape).astype(float)
        m0, _ = ipf(t, G0, tol=1e-9)
        m1, _ = ipf(t, G1, tol=1e-9)
        out[r] = deviance(t, m0), deviance(t, m1)
    return out


def _null_sim():
    path = os.path.join(common.HERE, "cache", "ch19_null_dev_R4000.npy")
    if os.path.exists(path):
        return np.load(path)
    p0 = fit_model(BREAST, "1.2+2.3")["fitted"] / BREAST.sum()
    D = null_deviances("1.2+2.3", "1.2+1.3+2.3", p0, int(BREAST.sum()), 4000, 1915)
    os.makedirs(os.path.dirname(path), exist_ok=True)
    np.save(path, D)
    return D


def fig_19_s3(out_dir=None):
    """Figure 19.S3: the deviance of 1.2+2.3 and the likelihood ratio against 1.2+1.3+2.3, simulated under
    the fitted model 1.2+2.3 (n = 474), against their chi-squared limits (Theorem 19.14)."""
    D = _null_sim()
    dev = D[:, 0]
    lr = D[:, 0] - D[:, 1]
    fig, axes = common.panel_grid(1, 2, size=(3.5, 2.6))
    for ax, x, nu, lab in ((axes[0, 0], dev, 2, r"dev(1.2+2.3), $\nu=2$"), (axes[0, 1], lr, 1, r"dev(1.2+2.3) $-$ dev(1.2+1.3+2.3), $\nu=1$")):
        hi = 14
        ax.hist(x, bins=np.linspace(0, hi, 57), density=True, color="#9fb7dc", edgecolor="white", lw=0.3)
        g = np.linspace(0.02, hi, 300)
        ax.plot(g, stats.chi2.pdf(g, nu), color=RED, lw=1.5, label=r"$\chi^2_%d$ density" % nu)
        ax.set_xlim(0, hi)
        ax.set_ylim(0, 0.6 if nu == 2 else 1.0)
        rate = np.mean(x > stats.chi2.ppf(0.95, nu))
        ax.set_title(lab, fontsize=8.5)
        ax.text(0.97, 0.6, "rejection rate at 5%%:\n%.4f" % rate, transform=ax.transAxes, ha="right", fontsize=8)
        ax.legend(fontsize=7.5, loc="upper right")
    common.panel_label(axes[0, 0], "a", "upper left")
    common.panel_label(axes[0, 1], "b", "upper left")
    fig.tight_layout()
    return savefig(fig, CH, "fig19-S3", out_dir)


SEL_NS = (100, 250, 474, 1000, 2500, 5000)


def selection_frequencies(p_true, ns=SEL_NS, R=300, seed=1919, alpha=0.05):
    """For each n: how often AIC, BIC and the 'smallest model not rejected by its deviance test' pick
    each of the nine models when tables are drawn from p_true."""
    path = os.path.join(common.HERE, "cache", "ch19_selection_R%d_s%d.npz" % (R, seed))
    if os.path.exists(path):
        z = np.load(path)
        return z["freq"]
    rng = np.random.default_rng(seed)
    freq = np.zeros((len(ns), 3, len(NINE)))
    for a, n in enumerate(ns):
        for _ in range(R):
            t = rng.multinomial(n, p_true.ravel()).reshape(p_true.shape).astype(float)
            fits = select(t)
            freq[a, 0, int(np.argmax([f["aic"] for f in fits]))] += 1
            freq[a, 1, int(np.argmax([f["bic"] for f in fits]))] += 1
            ok = [i for i, f in enumerate(fits) if f["df"] == 0 or f["p"] >= alpha]
            kmin = min(fits[i]["k"] for i in ok)
            cand = [i for i in ok if fits[i]["k"] == kmin]
            freq[a, 2, max(cand, key=lambda i: fits[i]["p"])] += 1
    freq /= R
    os.makedirs(os.path.dirname(path), exist_ok=True)
    np.savez(path, freq=freq)
    return freq


def fig_19_s4(out_dir=None):
    """Figure 19.S4: selection frequencies when the truth is the no-three-way fit to the breast cancer data
    (a weak centre-survival interaction)."""
    p_true = fit_model(BREAST, "1.2+1.3+2.3")["fitted"] / BREAST.sum()
    freq = selection_frequencies(p_true)
    fig, axes = common.panel_grid(1, 3, size=(2.55, 2.4), sharey=True)
    i_true, i_simple = NINE.index("1.2+1.3+2.3"), NINE.index("1.2+2.3")
    for c, lab in enumerate(["AIC", "BIC", "smallest model not rejected"]):
        ax = axes[0, c]
        ax.plot(SEL_NS, freq[:, c, i_true], "o-", color=RED, ms=3.5, label="true: 1.2+1.3+2.3")
        ax.plot(SEL_NS, freq[:, c, i_simple], "s-", color=BLUE, ms=3.5, label="1.2+2.3")
        other = 1 - freq[:, c, i_true] - freq[:, c, i_simple]
        ax.plot(SEL_NS, other, "^-", color=GREY, ms=3.5, label="any other")
        ax.set_xscale("log")
        ax.set_title(lab, fontsize=9)
        ax.set_xlabel("sample size $n$")
        ax.axvline(474, color="k", lw=0.6, ls=":")
        ax.set_ylim(-0.03, 1.03)
    axes[0, 0].set_ylabel("frequency selected")
    axes[0, 0].legend(fontsize=7, loc="center left")
    fig.tight_layout()
    return savefig(fig, CH, "fig19-S4", out_dir)


# =========================================================================== data for the demos
def export_json(path=None):
    """Write the tables used by the demonstrations."""
    out = {"source": "Wasserman (2004), Example 19.15 (Morrison et al., 1973), and coris.dat from the book website",
           "tables": {
               "breast": {"label": "Breast cancer (Example 19.15)", "vars": BREAST_VARS, "levels": BREAST_LEVELS,
                          "shape": list(BREAST.shape), "counts": BREAST.ravel().astype(int).tolist()},
               "coris": {"label": "coris: CHD x family history x age", "vars": CORIS_VARS, "levels": CORIS_LEVELS,
                         "shape": [2, 2, 3], "counts": coris_table().ravel().astype(int).tolist()},
               "zeros": {"label": "Breast cancer with two zeros", "vars": BREAST_VARS, "levels": BREAST_LEVELS,
                         "shape": list(ZEROS.shape), "counts": ZEROS.ravel().astype(int).tolist()}}}
    path = path or os.path.join(common.HERE, "..", "data", "ch19-tables.json")
    with open(path, "w") as f:
        json.dump(out, f, separators=(",", ":"))
    print("wrote", os.path.relpath(path, os.getcwd()))
    return path


FIGURES = {"19.1": fig_19_1, "19.2": fig_19_2, "19.3": fig_19_3, "19.4": fig_19_4, "19.5": fig_19_5,
           "19.S1": fig_19_s1, "19.S2": fig_19_s2, "19.S3": fig_19_s3, "19.S4": fig_19_s4}

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