"""Hastie, Tibshirani and Friedman (2009), Chapter 17: Undirected Graphical Models.

Reproduces the figures of Chapter 17 of T. Hastie, R. Tibshirani and J. Friedman, The Elements of
Statistical Learning (2nd edition, Springer, 2009), pp. 625-648, written from scratch with numpy, scipy
and matplotlib. Every method is a small function meant to be read next to the lecture notes
(../ch17-undirected-graphical-models.html):

* Graphs, Section 17.2: adjacency(), maximal_cliques() (Bron-Kerbosch with pivoting), separates()
  (does C separate A from B: breadth-first search that may not enter C), minimal_separators(),
  and draw_graph() for the circular layouts of the book.
* Gaussian graphical models, Section 17.3: gauss_loglik() is the partially maximised log-likelihood
  (17.11); partial_correlations() reads -theta_jk / sqrt(theta_jj theta_kk) off the precision matrix;
  modified_regression() is Algorithm 17.1 (the constrained maximum-likelihood fit for a known graph);
  lasso_cd() is the coordinate-descent lasso (17.26)-(17.27) on a cross-product matrix;
  graphical_lasso() is Algorithm 17.2 (penalised diagonal as in the book, or unpenalised as in the
  book's footnote 3) and glasso_path() follows it over a grid of penalties with warm starts;
  neighbourhood_selection() is the approach of Meinshausen and Buhlmann (2006) with the 'or' and
  'and' rules; em_missing() is the EM algorithm of Exercise 17.9 with Algorithm 17.1 as the M-step.
* Discrete graphical models, Section 17.4: the Ising model (17.28) with node terms on the diagonal
  (x_j^2 = x_j); all_states() enumerates {0,1}^p, ising_moments() gives E(X_j X_k) under the model
  (17.33) by enumeration, ising_fit_newton() is the exact maximum-likelihood fit (Newton's method on the
  concave log-likelihood (17.31)), ising_ipf() is iterative proportional fitting (each step solves one
  gradient equation (17.34) in closed form), mean_field() and gibbs_moments() are the two
  approximations of Section 17.4.1, poisson_loglinear() is the Poisson regression of Exercise 17.12,
  ising_l1() is the exact L1-penalised fit (proximal gradient) and wainwright() the node-wise L1 logistic
  regressions with 'min' and 'max' symmetrisation of Section 17.4.3.
* Restricted Boltzmann machines, Section 17.4.4: rbm_loglik() and rbm_grad_exact() sum the hidden units
  out in closed form and enumerate the visible ones; train_boltzmann() fits a fully visible Boltzmann
  machine or an RBM by exact gradients or by contrastive divergence CD-k, with the random numbers of the
  browser demos (JSStream, the generator DK.rng of courses/demo-kit.js), drawn in the same order as the
  demo draws them; mnist_rbm() trains the joint-density RBM of pixels and labels of Figure 17.7 by CD-1 and
  classifies by comparing free energies.
* Data: the flow-cytometry data of Sachs et al. (2003) from the book's website (sachs.data, 7466 cells by
  11 proteins, and sachs.covmatrix, which is var(data)/1000 and is what the book's penalties refer to);
  binarised at the protein medians for the discrete models; MNIST for Figure 17.7.

Figures reproduced: 17.1, 17.2, 17.4, 17.5, 17.6, 17.7, 17.8; supplementary figures 17.S1 (the
graphical-lasso path of the partial correlations), 17.S2 (an L1-penalised binary Markov network for the
dichotomised flow data: the exact fit against the 'min' and 'max' approximations) and 17.S3 (exact
gradients against contrastive divergence, the reference run of the Boltzmann-machine demo).
Run `python3 ch17_undirected_graphical_models.py --list`, `python3 ch17_undirected_graphical_models.py`
(all figures; about three minutes the first time, for the MNIST machine, which is then cached in
cache/ch17_rbm_mnist.npz) or `python3 ch17_undirected_graphical_models.py --fig 17.5`. Files go to
../img/ch17/; the demos' data go to ../data/ch17-sachs.json.

Figures not reproduced by code: Figure 17.3 (a single triangle on three nodes; nothing is computed).
Figures 17.2, 17.6 and 17.8 are schematic graphs in the book; here they are drawn by code, with the
maximal cliques of 17.2 and 17.8 found by maximal_cliques(). Figure 17.4 is drawn from the computed
Algorithm 17.1 fit of its covariance matrix. Figure 17.7 shows a joint-density RBM of our own size
(500 hidden units, one layer, CD-1), not the three-layer model of Hinton et al. (2006).

Settings chosen where the book gives none:
* Figures 17.1, 17.5, 17.S1: the penalties refer to the book's sachs.covmatrix (the scale on which the
  book's lambda = 0, 7, 14, 27, 36 give its graphs); the diagonal is penalised as in Algorithm 17.2.
  An edge is drawn when |theta_jk| > 1e-8.
* Discrete models: each protein is coded 1 above its median and 0 otherwise.
* Figure 17.7: binary pixels (intensity > 0.5), 500 hidden units, 15 epochs of CD-1 with minibatches
  of 100, learning rate 0.05, momentum 0.5 then 0.9, weight decay 1e-4 (numpy seed 17).
"""
import json
import math
import os

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.patches import Circle, Polygon, FancyBboxPatch

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

CH = 17
HERE = os.path.dirname(os.path.abspath(__file__))
CACHE_DIR = os.path.join(HERE, "cache")
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
PROTEINS = ["Raf", "Mek", "Plcg", "PIP2", "PIP3", "Erk", "Akt", "PKA", "PKC", "P38", "Jnk"]
EDGE_TOL = 1e-8
M32 = 0xFFFFFFFF


# =========================================================================== data
def sachs_cov():
    """The book's 11 x 11 covariance matrix of the flow-cytometry data (sachs.covmatrix = var(data)/1000)."""
    return np.loadtxt(common.esl_file("sachs.covmatrix"))


def sachs_data():
    """The 7466 x 11 flow-cytometry measurements (sachs.data; the columns are in the order PROTEINS)."""
    return np.loadtxt(common.esl_file("sachs.data"))


def sachs_binary():
    """The flow-cytometry data coded 1 above each protein's median, 0 otherwise (7466 x 11 integers)."""
    X = sachs_data()
    return (X > np.median(X, axis=0)).astype(int)


def cell_counts(Xb):
    """Counts of the 2^p cells of a binary data matrix, in the order of all_states(p)."""
    p = Xb.shape[1]
    idx = Xb @ (1 << np.arange(p))
    return np.bincount(idx, minlength=2 ** p).astype(float)


# =========================================================================== graphs (Section 17.2)
def adjacency(p, edges):
    """Boolean p x p adjacency matrix of an undirected graph given as a list of pairs (0-based)."""
    A = np.zeros((p, p), bool)
    for j, k in edges:
        A[j, k] = A[k, j] = True
    return A


def edges_of(A):
    p = A.shape[0]
    return [(j, k) for j in range(p) for k in range(j + 1, p) if A[j, k]]


def maximal_cliques(A):
    """All maximal cliques of the graph with adjacency A (Bron-Kerbosch with pivoting), sorted."""
    p = A.shape[0]
    nb = [set(np.flatnonzero(A[v])) for v in range(p)]
    out = []

    def bk(R, P, X):
        if not P and not X:
            out.append(sorted(R))
            return
        u = max(P | X, key=lambda v: len(nb[v] & P))
        for v in list(P - nb[u]):
            bk(R | {v}, P & nb[v], X & nb[v])
            P = P - {v}
            X = X | {v}

    bk(set(), set(range(p)), set())
    return sorted(out, key=lambda c: (len(c) == 1, c))


def separates(A, S1, S2, C):
    """True if every path from a node of S1 to a node of S2 meets C (17.2): search from S1 avoiding C."""
    C = set(C)
    seen = set(S1) - C
    stack = list(seen)
    while stack:
        v = stack.pop()
        for w in np.flatnonzero(A[v]):
            if w not in seen and w not in C:
                seen.add(w)
                stack.append(w)
    return not (seen & set(S2))


def minimal_separators(A, j, k):
    """The minimal sets C (not containing j, k) that separate the non-adjacent nodes j and k."""
    from itertools import combinations
    p = A.shape[0]
    others = [v for v in range(p) if v not in (j, k)]
    found = []
    for r in range(len(others) + 1):
        for C in combinations(others, r):
            if separates(A, [j], [k], C) and not any(set(F) <= set(C) for F in found):
                found.append(C)
    return found


def circle_layout(p, start=90.0):
    """Positions of p nodes on the unit circle, counter-clockwise from the angle `start` (degrees)."""
    ang = np.deg2rad(start + 360.0 * np.arange(p) / p)
    return np.c_[np.cos(ang), np.sin(ang)]


def draw_graph(ax, pos, A, labels, widths=None, colours=None, node_style="ring", node_size=0.075,
               cliques=None, fs=10, label_out=None):
    """Draw an undirected graph: edges, nodes (small rings as in the book, or filled discs), labels,
    and optionally shaded maximal cliques."""
    p = len(labels)
    if cliques:
        pal = ["#bfe3bf", "#cfd9f7", "#f7d9b5", "#ecc8e8", "#d8ecf2"]
        for c_i, c in enumerate(cliques):
            if len(c) >= 3:
                P = pos[c]
                cen = P.mean(0)
                order = np.argsort(np.arctan2(P[:, 1] - cen[1], P[:, 0] - cen[0]))
                ax.add_patch(Polygon(P[order], closed=True, fc=pal[c_i % len(pal)], ec="none", alpha=0.85, zorder=0))
            elif len(c) == 2:
                (x0, y0), (x1, y1) = pos[c[0]], pos[c[1]]
                ax.plot([x0, x1], [y0, y1], color=pal[c_i % len(pal)], lw=14, solid_capstyle="round", zorder=0)
    for e_i, (j, k) in enumerate(edges_of(A)):
        lw = 1.0 if widths is None else widths[e_i]
        col = BLUE if colours is None else colours[e_i]
        ax.plot([pos[j, 0], pos[k, 0]], [pos[j, 1], pos[k, 1]], color=col, lw=lw, zorder=1)
    for v in range(p):
        if node_style == "ring":
            ax.add_patch(Circle(pos[v], node_size * 0.35, fc="white", ec="black", lw=0.8, zorder=3))
            d = pos[v] / max(np.linalg.norm(pos[v]), 1e-9) if label_out is None else label_out[v]
            ax.text(pos[v, 0] + 0.13 * d[0], pos[v, 1] + 0.11 * d[1], labels[v], ha="center", va="center", fontsize=fs, zorder=4)
        else:
            ax.add_patch(Circle(pos[v], node_size, fc="#5cd65c", ec="#2b8a2b", lw=1.0, zorder=3))
            ax.text(pos[v, 0], pos[v, 1], labels[v], ha="center", va="center", fontsize=fs, zorder=4, style="italic")
    ax.set_aspect("equal")
    ax.axis("off")


# =========================================================================== Gaussian models (17.3)
def gauss_loglik(Theta, S):
    """The partially maximised log-likelihood (17.11), log det Theta - trace(S Theta) (per observation, up to
    constants)."""
    sign, ld = np.linalg.slogdet(Theta)
    return ld - np.sum(S * Theta) if sign > 0 else -np.inf


def glasso_objective(Theta, S, lam, penalize_diagonal=True):
    """The penalised log-likelihood (17.21)."""
    pen = np.abs(Theta).sum() if penalize_diagonal else np.abs(Theta).sum() - np.abs(np.diag(Theta)).sum()
    return gauss_loglik(Theta, S) - lam * pen


def partial_correlations(Theta):
    """rho_{jk|rest} = -theta_jk / sqrt(theta_jj theta_kk) (Exercise 17.3), with ones on the diagonal."""
    d = 1.0 / np.sqrt(np.diag(Theta))
    R = -Theta * np.outer(d, d)
    np.fill_diagonal(R, 1.0)
    return R


def theta_from_regressions(W, B):
    """Step 3 of Algorithms 17.1 and 17.2: theta_22 = 1/(w_22 - w_12^T beta), theta_12 = -beta theta_22,
    row by row (B[j] is the coefficient vector of node j on the others)."""
    p = W.shape[0]
    Th = np.zeros((p, p))
    for j in range(p):
        o = np.r_[0:j, j + 1:p]
        t22 = 1.0 / (W[j, j] - W[o, j] @ B[j])
        Th[j, j] = t22
        Th[o, j] = -B[j] * t22
    return 0.5 * (Th + Th.T)


def modified_regression(S, A, tol=1e-12, max_sweeps=1000, record=False):
    """Algorithm 17.1: the maximum-likelihood W = Sigma-hat and Theta = W^{-1} of a Gaussian graphical
    model whose missing edges (A[j, k] False) are constrained to theta_jk = 0.

    Each step solves W*_11 beta* = s*_12 on the neighbours of node j (17.19), pads beta with zeros and
    sets w_12 = W_11 beta. Returns dict(W, Theta, B, sweeps, history) where history holds the
    log-likelihood (17.11) and the largest change of W after each sweep (if record)."""
    p = S.shape[0]
    W = S.copy()
    B = np.zeros((p, p - 1))
    hist = []
    for sweep in range(1, max_sweeps + 1):
        Wold = W.copy()
        for j in range(p):
            o = np.r_[0:j, j + 1:p]
            nb = np.flatnonzero(A[j, o])
            W11 = W[np.ix_(o, o)]
            beta = np.zeros(p - 1)
            if len(nb):
                beta[nb] = np.linalg.solve(W11[np.ix_(nb, nb)], S[o, j][nb])
            B[j] = beta
            w12 = W11 @ beta
            W[o, j] = w12
            W[j, o] = w12
        change = np.abs(W - Wold).max()
        if record:
            hist.append((gauss_loglik(theta_from_regressions(W, B), S), change))
        if change < tol:
            break
    Th = theta_from_regressions(W, B)
    Th[~A & ~np.eye(p, dtype=bool)] = 0.0
    return dict(W=W, Theta=Th, B=B, sweeps=sweep, history=hist)


def soft_threshold(x, t):
    """S(x, t) = sign(x)(|x| - t)_+ (17.27)."""
    return np.sign(x) * np.maximum(np.abs(x) - t, 0.0)


def lasso_cd(V, s, lam, beta=None, tol=1e-12, max_sweeps=100000):
    """Coordinate descent (17.26) for min_beta 1/2 beta^T V beta - s^T beta + lam ||beta||_1, whose
    stationarity conditions are V beta - s + lam Sign(beta) = 0 (17.23)/(17.25). Returns (beta, sweeps)."""
    q = len(s)
    beta = np.zeros(q) if beta is None else np.array(beta, float)
    for sweep in range(1, max_sweeps + 1):
        dmax = 0.0
        for k in range(q):
            r = s[k] - V[k] @ beta + V[k, k] * beta[k]
            b = math.copysign(max(abs(r) - lam, 0.0), r) / V[k, k]
            dmax = max(dmax, abs(b - beta[k]))
            beta[k] = b
        if dmax < tol:
            break
    return beta, sweep


def lasso_xy(X, y, lam, **kw):
    """The lasso (17.24), 1/2 ||y - X beta||^2 + lam ||beta||_1, by coordinate descent on (X^T X, X^T y)."""
    return lasso_cd(X.T @ X, X.T @ y, lam, **kw)[0]


def graphical_lasso(S, lam, penalize_diagonal=True, tol=1e-10, max_sweeps=500, W0=None, B0=None,
                    inner_tol=1e-12):
    """Algorithm 17.2, the graphical lasso, for the penalised log-likelihood (17.21).

    W starts at S + lam I (diagonal fixed there; with penalize_diagonal=False at S, the variant of the
    book's footnote 3). For each node j the modified lasso W_11 beta - s_12 + lam Sign(beta) = 0 is solved
    by coordinate descent (17.26) from the previous beta (warm start), then w_12 = W_11 beta. Stops when
    a whole sweep changes W by less than tol times the mean absolute off-diagonal of S. Returns
    dict(W, Theta, B, sweeps)."""
    p = S.shape[0]
    if W0 is None:
        W = S + (lam * np.eye(p) if penalize_diagonal else 0.0)
    else:
        W = W0.copy()
        np.fill_diagonal(W, np.diag(S) + (lam if penalize_diagonal else 0.0))
    B = np.zeros((p, p - 1)) if B0 is None else B0.copy()
    scale = np.abs(S[~np.eye(p, dtype=bool)]).mean()
    for sweep in range(1, max_sweeps + 1):
        Wold = W.copy()
        for j in range(p):
            o = np.r_[0:j, j + 1:p]
            W11 = W[np.ix_(o, o)]
            beta, _ = lasso_cd(W11, S[o, j], lam, B[j], tol=inner_tol)
            B[j] = beta
            w12 = W11 @ beta
            W[o, j] = w12
            W[j, o] = w12
        if np.abs(W - Wold).max() < tol * scale:
            break
    Th = theta_from_regressions(W, B)
    Th[np.abs(Th) < 1e-14] = 0.0
    return dict(W=W, Theta=Th, B=B, sweeps=sweep)


def glasso_path(S, lams, **kw):
    """graphical_lasso() at each penalty of `lams` (any order; computed from the largest down with warm
    starts). Returns a list of results in the order of `lams`."""
    order = np.argsort(-np.asarray(lams, float))
    out = [None] * len(lams)
    W0 = B0 = None
    for i in order:
        r = graphical_lasso(S, float(lams[i]), W0=W0, B0=B0, **kw)
        out[i] = r
        W0, B0 = r["W"], r["B"]
    return out


def edge_matrix(Theta, tol=EDGE_TOL):
    A = np.abs(Theta) > tol
    np.fill_diagonal(A, False)
    return A


def lambda_max(S):
    """The smallest penalty at which the graphical lasso has no edges: max_{j != k} |s_jk|."""
    p = S.shape[0]
    return np.abs(S[~np.eye(p, dtype=bool)]).max()


def neighbourhood_selection(S, lam, rule="or"):
    """Meinshausen and Buhlmann (2006): the lasso of each variable on the others, computed from the
    covariance matrix (1/(2N)||y - Z beta||^2 + lam||beta||_1 has the cross-products S_11 and s_12), and an
    edge j-k when the coefficient of k for j or (rule 'or') and (rule 'and') that of j for k is nonzero.
    Returns (adjacency, coefficient matrix C with C[j, k] the coefficient of k in the regression of j)."""
    p = S.shape[0]
    Cf = np.zeros((p, p))
    for j in range(p):
        o = np.r_[0:j, j + 1:p]
        beta, _ = lasso_cd(S[np.ix_(o, o)], S[o, j], lam)
        Cf[j, o] = beta
    nz = np.abs(Cf) > EDGE_TOL
    A = (nz | nz.T) if rule == "or" else (nz & nz.T)
    np.fill_diagonal(A, False)
    return A, Cf


def em_missing(X, miss, A, iters=200, tol=1e-10):
    """Exercise 17.9: EM for a Gaussian graphical model with graph A when the entries miss[i, j] of X
    are missing. E-step: impute each missing block by its conditional mean (17.43) and record its
    conditional covariance; M-step: the mean of the completed data, and Algorithm 17.1 applied to
    their covariance plus the average conditional covariance (17.44). Returns dict(mu, W, Theta, Xhat,
    loglik) where loglik is the observed-data log-likelihood after each iteration."""
    N, p = X.shape
    Xh = np.where(miss, np.nan, X)
    mu = np.nanmean(Xh, axis=0)
    Xh = np.where(miss, mu, X)
    Sig = modified_regression(np.cov(Xh.T, bias=True), A, tol=1e-13)["W"]   # start inside the model
    patterns = {}
    for i in range(N):
        key = tuple(np.flatnonzero(miss[i]))
        patterns.setdefault(key, []).append(i)
    ll_hist = []
    Theta = np.linalg.inv(Sig)
    for it in range(iters):
        C = np.zeros((p, p))
        ll = 0.0
        for key, rows in patterns.items():
            rows = np.array(rows)
            m = np.array(key, int)
            o = np.setdiff1d(np.arange(p), m)
            Soo = Sig[np.ix_(o, o)]
            d = X[np.ix_(rows, o)] - mu[o]
            L = np.linalg.cholesky(Soo)
            z = np.linalg.solve(L, d.T)
            ll += -0.5 * (len(rows) * (len(o) * np.log(2 * np.pi) + 2 * np.log(np.diag(L)).sum()) + (z ** 2).sum())
            if len(m):
                K = np.linalg.solve(Soo, Sig[np.ix_(o, m)])          # Soo^{-1} Sigma_om
                Xh[np.ix_(rows, m)] = mu[m] + d @ K
                C[np.ix_(m, m)] += len(rows) * (Sig[np.ix_(m, m)] - Sig[np.ix_(m, o)] @ K)
        ll_hist.append(ll)
        mu = Xh.mean(0)
        R = Xh - mu
        Stil = (R.T @ R + C) / N
        fit = modified_regression(Stil, A, tol=1e-13)
        Sig, Theta = fit["W"], fit["Theta"]
        if it > 2 and abs(ll_hist[-1] - ll_hist[-2]) < tol * abs(ll_hist[-1]):
            break
    return dict(mu=mu, W=Sig, Theta=Theta, Xhat=Xh, loglik=ll_hist)


def figure_17_1_graph():
    """The edges of Figure 17.1 (graphical lasso at lambda = 14 on sachs.covmatrix), as an adjacency matrix."""
    return edge_matrix(graphical_lasso(sachs_cov(), 14.0)["Theta"])


# =========================================================================== discrete models (17.4)
def all_states(p):
    """All 2^p binary vectors as rows; row r has x_j = bit j of r."""
    r = np.arange(2 ** p)
    return ((r[:, None] >> np.arange(p)) & 1).astype(float)


def ising_energy(Xs, Th):
    """sum_{j<k} theta_jk x_j x_k + sum_j theta_jj x_j for each row x (diagonal = node terms theta_j0,
    since x_j^2 = x_j for binary x)."""
    U = np.triu(Th, 1)
    return np.einsum("ij,jk,ik->i", Xs, U, Xs) + Xs @ np.diag(Th)


def ising_logZ(Th, Xs=None):
    """Phi(Theta) (17.29), by enumeration."""
    Xs = all_states(Th.shape[0]) if Xs is None else Xs
    return common.logsumexp(ising_energy(Xs, Th))


def ising_probs(Th, Xs=None):
    Xs = all_states(Th.shape[0]) if Xs is None else Xs
    e = ising_energy(Xs, Th)
    w = np.exp(e - e.max())
    return w / w.sum()


def ising_moments(Th, Xs=None):
    """E_Theta(X_j X_k) for all j, k (diagonal: E X_j) (17.33), by enumeration."""
    Xs = all_states(Th.shape[0]) if Xs is None else Xs
    P = ising_probs(Th, Xs)
    return (Xs * P[:, None]).T @ Xs


def data_moments(counts, Xs):
    """E-hat(X_j X_k) (17.35) from cell counts."""
    w = counts / counts.sum()
    return (Xs * w[:, None]).T @ Xs


def ising_loglik(Th, counts, Xs=None):
    """The average log-likelihood (17.31)/N from cell counts."""
    Xs = all_states(Th.shape[0]) if Xs is None else Xs
    return (counts @ ising_energy(Xs, Th)) / counts.sum() - ising_logZ(Th, Xs)


def _pairs(p):
    return [(j, j) for j in range(p)] + [(j, k) for j in range(p) for k in range(j + 1, p)]


def ising_fit_newton(counts, A=None, tol=1e-12, max_iter=100):
    """Exact maximum likelihood for the Ising model with node terms and the edges of A (all pairs if None):
    Newton's method on the average log-likelihood, whose gradient is E-hat(T) - E_Theta(T) (17.34) and
    whose Hessian is -Cov_Theta(T), T = the sufficient statistics x_j x_k. Step halving keeps the
    likelihood increasing. Returns (Theta, iterations)."""
    p = int(round(math.log2(len(counts))))
    Xs = all_states(p)
    prs = [(j, k) for (j, k) in _pairs(p) if j == k or A is None or A[j, k]]
    T = np.stack([Xs[:, j] * Xs[:, k] for j, k in prs], 1)
    that = (counts / counts.sum()) @ T
    th = np.zeros(len(prs))

    def unpack(v):
        Th = np.zeros((p, p))
        for val, (j, k) in zip(v, prs):
            Th[j, k] = Th[k, j] = val
        return Th

    f = ising_loglik(unpack(th), counts, Xs)
    for it in range(1, max_iter + 1):
        P = ising_probs(unpack(th), Xs)
        m = P @ T
        g = that - m
        Hm = (T * P[:, None]).T @ T - np.outer(m, m)
        step = np.linalg.solve(Hm + 1e-14 * np.eye(len(th)), g)
        t = 1.0
        while True:
            fn = ising_loglik(unpack(th + t * step), counts, Xs)
            if fn >= f - 1e-15 or t < 1e-8:
                break
            t /= 2
        th = th + t * step
        f = fn
        if np.abs(g).max() < tol:
            break
    return unpack(th), it


def ising_ipf(counts, sweeps=50, A=None, record=False):
    """Iterative proportional fitting for the Ising model: cycle over the node terms and edges; each
    update makes one gradient equation (17.34) exact. Raising theta_jk by delta multiplies the probability
    of every x with x_j x_k = 1 by e^delta, so E(X_j X_k) = m becomes m e^delta / (1 - m + m e^delta); this
    equals the data value q when e^delta = q (1 - m) / (m (1 - q)). Returns (Theta, history of the
    average log-likelihood after each sweep)."""
    p = int(round(math.log2(len(counts))))
    Xs = all_states(p)
    q = data_moments(counts, Xs)
    Th = np.zeros((p, p))
    prs = [(j, k) for (j, k) in _pairs(p) if j == k or A is None or A[j, k]]
    hist = []
    for s in range(sweeps):
        for j, k in prs:
            m = (ising_probs(Th, Xs) @ (Xs[:, j] * Xs[:, k]))
            delta = math.log(q[j, k] * (1 - m) / (m * (1 - q[j, k])))
            Th[j, k] += delta
            if j != k:
                Th[k, j] = Th[j, k]
        if record:
            hist.append(ising_loglik(Th, counts, Xs))
    return Th, hist


def mean_field(Th, iters=500, damping=0.5):
    """Naive mean field: m_j = sigma(theta_jj + sum_{k != j} theta_jk m_k), and E(X_j X_k) ~ m_j m_k."""
    p = Th.shape[0]
    m = np.full(p, 0.5)
    off = Th - np.diag(np.diag(Th))
    for _ in range(iters):
        m = damping * m + (1 - damping) * common.sigmoid(np.diag(Th) + off @ m)
    M = np.outer(m, m)
    np.fill_diagonal(M, m)
    return M


def gibbs_moments(Th, n_sweeps=20000, burn=500, seed=0):
    """Estimate E_Theta(X_j X_k) by Gibbs sampling: sweep the nodes, drawing each from its logistic
    conditional (17.30)."""
    rng = np.random.default_rng(seed)
    p = Th.shape[0]
    off = Th - np.diag(np.diag(Th))
    x = (rng.random(p) < 0.5).astype(float)
    acc = np.zeros((p, p))
    for s in range(n_sweeps + burn):
        for j in range(p):
            x[j] = float(rng.random() < common.sigmoid(Th[j, j] + off[j] @ x))
        if s >= burn:
            acc += np.outer(x, x)
    return acc / n_sweeps


def poisson_loglinear(counts, A=None):
    """Exercise 17.12: the Poisson regression of the 2^p cell counts on the intercept, the p node
    indicators and the edge products x_j x_k (statsmodels GLM). Returns (theta_00, Theta)."""
    import statsmodels.api as sm
    p = int(round(math.log2(len(counts))))
    Xs = all_states(p)
    prs = [(j, k) for (j, k) in _pairs(p) if j == k or A is None or A[j, k]]
    Z = np.column_stack([np.ones(len(Xs))] + [Xs[:, j] * Xs[:, k] for j, k in prs])
    res = sm.GLM(counts, Z, family=sm.families.Poisson()).fit(tol=1e-13, maxiter=200)
    Th = np.zeros((p, p))
    for val, (j, k) in zip(res.params[1:], prs):
        Th[j, k] = Th[k, j] = val
    return res.params[0], Th


def ising_l1(counts, lam, Th0=None, iters=5000, tol=1e-10):
    """The exact L1-penalised Ising fit: maximise the average log-likelihood minus lam sum_{j<k}|theta_jk|
    (node terms unpenalised) by accelerated proximal gradient with exact gradients (17.34)."""
    p = int(round(math.log2(len(counts))))
    Xs = all_states(p)
    q = data_moments(counts, Xs)
    Th = np.zeros((p, p)) if Th0 is None else Th0.copy()
    Y, t, L = Th.copy(), 1.0, 4.0      # step 1/L (the largest eigenvalue of Cov(T) here is about 3)
    off = ~np.eye(p, dtype=bool)
    for it in range(iters):
        G = q - ising_moments(Y, Xs)
        Z = Y + G / L
        Z[off] = soft_threshold(Z[off], lam / L / 1.0)
        tn = 0.5 * (1 + math.sqrt(1 + 4 * t * t))
        Yn = Z + (t - 1) / tn * (Z - Th)
        if np.abs(Z - Th).max() < tol:
            Th = Z
            break
        Th, Y, t = Z, Yn, tn
    return Th


def wainwright(Xb, lam, rule="min"):
    """Section 17.4.3: an L1-penalised logistic regression of each node on the others (17.30) with
    criterion -(1/N) log-likelihood + lam ||theta||_1 (intercept unpenalised), then the 'min' or 'max'
    symmetrisation of the two estimates of each edge. Returns the symmetric matrix of edge estimates."""
    from sklearn.linear_model import LogisticRegression
    N, p = Xb.shape
    Tt = np.zeros((p, p))
    for j in range(p):
        o = np.r_[0:j, j + 1:p]
        m = LogisticRegression(penalty="l1", C=1.0 / (N * lam), solver="liblinear", tol=1e-10,
                               intercept_scaling=1e4, max_iter=10000).fit(Xb[:, o], Xb[:, j])
        Tt[j, o] = m.coef_[0]
    a, b = Tt, Tt.T
    pick_a = np.abs(a) <= np.abs(b) if rule == "min" else np.abs(a) >= np.abs(b)
    T = np.where(pick_a, a, b)
    np.fill_diagonal(T, 0.0)
    return T


# =========================================================================== Boltzmann machines (17.4.4)
class JSStream:
    """The uniform random numbers of DK.rng (mulberry32) in courses/demo-kit.js. u() gives one number,
    block(n) the next n at once (the state advances by a constant per draw, so a block is computed in one
    vectorised step); norm() is the Box-Muller transform of DK.rng."""
    C = 0x6D2B79F5

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

    @staticmethod
    def _hash(a):
        a = a.astype(np.uint64)
        t = ((a ^ (a >> np.uint64(15))) * (a | np.uint64(1))) & np.uint64(M32)
        t2 = ((t ^ (t >> np.uint64(7))) * (t | np.uint64(61))) & np.uint64(M32)
        t = ((t + t2) & np.uint64(M32)) ^ t
        return ((t ^ (t >> np.uint64(14))) & np.uint64(M32)).astype(float) / 4294967296.0

    def block(self, n):
        k = np.arange(1, n + 1, dtype=np.uint64)
        a = (np.uint64(self.a) + k * np.uint64(self.C)) & np.uint64(M32)
        self.a = int(a[-1]) if n else self.a
        return self._hash(a)

    def u(self):
        return float(self.block(1)[0])

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


def _sig(a):
    return 1.0 / (1.0 + np.exp(-a))


def rbm_free_energy_terms(V, b, c, W):
    """log of the unnormalised marginal of v: b^T v + sum_j log(1 + exp(c_j + v^T W_j))."""
    return V @ b + np.logaddexp(0.0, V @ W + c).sum(1)


def rbm_loglik(counts, b, c, W, Xs=None):
    """Exact average log-likelihood of an RBM with visible biases b, hidden biases c, weights W (p x H):
    the hidden units are summed out in closed form and the visible ones enumerated."""
    p = len(b)
    Xs = all_states(p) if Xs is None else Xs
    F = rbm_free_energy_terms(Xs, b, c, W)
    return (counts @ F) / counts.sum() - common.logsumexp(F)


def rbm_grad_exact(counts, b, c, W, Xs=None):
    """Exact gradient of the average log-likelihood (17.37): data term (hidden units imputed by their
    conditional means, (17.38)) minus model term (by enumeration of the visible units)."""
    p = len(b)
    Xs = all_states(p) if Xs is None else Xs
    F = rbm_free_energy_terms(Xs, b, c, W)
    P = np.exp(F - F.max())
    P /= P.sum()
    w = counts / counts.sum()
    Hm = _sig(Xs @ W + c)
    gW = (Xs * w[:, None]).T @ Hm - (Xs * P[:, None]).T @ Hm
    gb = w @ Xs - P @ Xs
    gc = w @ Hm - P @ Hm
    return gb, gc, gW


def expand_counts(counts, Xs):
    """The data rows in cell order (cell 0 first), the order the demo uses."""
    return np.repeat(Xs, counts.astype(int), axis=0)


def train_boltzmann(counts, model="ising", H=2, method="exact", k=1, eta=0.5, iters=200, seed=1,
                    init_scale=0.1):
    """Fit a fully visible Boltzmann machine (model 'ising', (17.28)) or an RBM with H hidden units
    (model 'rbm') to binary data given by cell counts, by gradient ascent on the average log-likelihood with
    step eta, using exact gradients ('exact') or contrastive divergence CD-k ('cd': the model term is
    replaced by its value at the end of k Gibbs sweeps started at every data row).

    Random numbers come from JSStream(seed) in the same order as the browser demo: the RBM's initial
    weights (init_scale times standard normals, row by row), then for every iteration the uniforms of the
    Gibbs sweeps (Ising: node by node, each over all N rows; RBM: hidden states row by row, then visible,
    then hidden). Returns dict(params, loglik) with the exact average log-likelihood after every
    iteration (index 0 = the start)."""
    p = int(round(math.log2(len(counts))))
    Xs = all_states(p)
    rng = JSStream(seed)
    V0 = expand_counts(counts, Xs)
    N = len(V0)
    if model == "ising":
        Th = np.zeros((p, p))
        q = data_moments(counts, Xs)
        ll = [ising_loglik(Th, counts, Xs)]
        for it in range(iters):
            if method == "exact":
                M = ising_moments(Th, Xs)
            else:
                V = V0.copy()
                off = Th - np.diag(np.diag(Th))
                for s in range(k):
                    for j in range(p):
                        u = rng.block(N)
                        a = Th[j, j] + V @ off[j]
                        V[:, j] = (u < _sig(a)).astype(float)
                M = V.T @ V / N
            G = q - M
            Th = Th + eta * G
            Th = 0.5 * (Th + Th.T)
            ll.append(ising_loglik(Th, counts, Xs))
        return dict(params=dict(Theta=Th), loglik=np.array(ll))
    W = np.array([[init_scale * rng.norm() for _ in range(H)] for _ in range(p)])
    rng.spare = None
    b = np.zeros(p)
    c = np.zeros(H)
    ll = [rbm_loglik(counts, b, c, W, Xs)]
    for it in range(iters):
        if method == "exact":
            gb, gc, gW = rbm_grad_exact(counts, b, c, W, Xs)
        else:
            ph0 = _sig(V0 @ W + c)
            h = (rng.block(N * H).reshape(N, H) < ph0).astype(float)
            for s in range(k):
                pv = _sig(h @ W.T + b)
                V = (rng.block(N * p).reshape(N, p) < pv).astype(float)
                ph = _sig(V @ W + c)
                if s < k - 1:
                    h = (rng.block(N * H).reshape(N, H) < ph).astype(float)
            gW = (V0.T @ ph0 - V.T @ ph) / N
            gb = (V0 - V).mean(0)
            gc = (ph0 - ph).mean(0)
        W = W + eta * gW
        b = b + eta * gb
        c = c + eta * gc
        ll.append(rbm_loglik(counts, b, c, W, Xs))
    return dict(params=dict(b=b, c=c, W=W), loglik=np.array(ll))


# ============================================================================= MNIST RBM (Figure 17.7)
def mnist_rbm(H=500, epochs=15, seed=17, cache=True):
    """A joint-density RBM of 784 binary pixels and a 10-way label unit with H hidden units, trained by
    CD-1 (Hinton 2002). Classification compares the free energies of the ten (image, label) pairs:
    p(y | x) is proportional to exp(-F(x, y)), with no partition function needed. Cached."""
    path = os.path.join(CACHE_DIR, "ch17_rbm_mnist.npz")
    if cache and os.path.exists(path):
        z = np.load(path)
        return {k: z[k] for k in z.files}
    X, y = common.mnist(True)
    Xb = (X > 0.5).astype(np.float32)
    Y = np.eye(10, dtype=np.float32)[y]
    rng = np.random.default_rng(seed)
    W = (0.01 * rng.standard_normal((794, H))).astype(np.float32)
    b = np.zeros(794, np.float32)
    b[:784] = np.log(np.clip(Xb.mean(0), 1e-3, 1 - 1e-3) / (1 - np.clip(Xb.mean(0), 1e-3, 1 - 1e-3)))
    c = np.zeros(H, np.float32)
    dW, db, dc = np.zeros_like(W), np.zeros_like(b), np.zeros_like(c)
    lr, bs, wd = 0.05, 100, 1e-4
    V = np.hstack([Xb, Y])
    for ep in range(epochs):
        mom = 0.5 if ep < 3 else 0.9
        perm = rng.permutation(len(V))
        for s in range(0, len(V), bs):
            v0 = V[perm[s:s + bs]]
            ph0 = _sig(v0 @ W + c)
            h0 = (rng.random(ph0.shape, dtype=np.float32) < ph0).astype(np.float32)
            a = h0 @ W.T + b
            pv = _sig(a[:, :784])
            al = a[:, 784:] - a[:, 784:].max(1, keepdims=True)
            el = np.exp(al)
            pl = el / el.sum(1, keepdims=True)
            lab = (rng.random((len(v0), 1), dtype=np.float32) > np.cumsum(pl, 1)).sum(1)
            v1 = np.hstack([(rng.random(pv.shape, dtype=np.float32) < pv).astype(np.float32),
                            np.eye(10, dtype=np.float32)[np.minimum(lab, 9)]])
            ph1 = _sig(v1 @ W + c)
            dW = mom * dW + lr * ((v0.T @ ph0 - v1.T @ ph1) / len(v0) - wd * W)
            db = mom * db + lr * (v0 - v1).mean(0)
            dc = mom * dc + lr * (ph0 - ph1).mean(0)
            W += dW
            b += db
            c += dc
    Xt, yt = common.mnist(False)
    Xtb = (Xt > 0.5).astype(np.float32)
    negF = rbm_class_scores(Xtb, W, b, c)
    out = dict(W=W, b=b, c=c, test_scores=negF.astype(np.float32), test_labels=yt)
    os.makedirs(CACHE_DIR, exist_ok=True)
    np.savez_compressed(path, **out)
    return out


def rbm_class_scores(Xb, W, b, c):
    """-F(x, y) for y = 0..9 (up to a common constant): b_y + sum_j log(1 + exp(c_j + x^T W_x,j + W_y,j))."""
    base = Xb @ W[:784] + c
    out = np.empty((len(Xb), 10))
    for yv in range(10):
        out[:, yv] = b[784 + yv] + np.logaddexp(0.0, base + W[784 + yv]).sum(1)
    return out


# =========================================================================== figures
def _protein_layout():
    return circle_layout(len(PROTEINS), 90.0)


def _protein_graph(ax, Theta, title=None, weighted=False):
    A = edge_matrix(Theta)
    pos = _protein_layout()
    widths = None
    if weighted:
        R = partial_correlations(Theta)
        widths = [0.6 + 4 * abs(R[j, k]) for j, k in edges_of(A)]
    draw_graph(ax, pos, A, PROTEINS, widths=widths, fs=9)
    ax.set_xlim(-1.32, 1.32)
    ax.set_ylim(-1.25, 1.3)
    if title:
        ax.set_title(title, fontsize=11)
    return A


def fig_17_1(out_dir=None):
    """Figure 17.1: the graphical-lasso graph of the flow-cytometry data at lambda = 14."""
    S = sachs_cov()
    r = graphical_lasso(S, 14.0)
    fig, ax = plt.subplots(figsize=(4.6, 4.4))
    A = _protein_graph(ax, r["Theta"])
    ax.text(0, -1.22, "%d edges (lambda = 14)" % len(edges_of(A)), ha="center", fontsize=9, color=GREY)
    savefig(fig, CH, "fig17-1", out_dir)


def fig_17_2(out_dir=None):
    """Figure 17.2: four small Markov graphs, with their maximal cliques shaded (computed)."""
    G = example_graphs()
    fig, axes = plt.subplots(2, 2, figsize=(6.4, 5.0))
    for ax, key in zip(axes.ravel(), "abcd"):
        labels, pos, A = G[key]
        cl = maximal_cliques(A)
        draw_graph(ax, pos, A, labels, node_style="disc", node_size=0.16, cliques=cl, colours=["black"] * len(edges_of(A)), fs=11)
        ax.set_xlim(pos[:, 0].min() - 0.35, pos[:, 0].max() + 0.35)
        ax.set_ylim(pos[:, 1].min() - 0.45, pos[:, 1].max() + 0.3)
        cs = ", ".join("{" + ",".join(labels[v] for v in c) + "}" for c in cl)
        ax.text(pos[:, 0].mean(), pos[:, 1].min() - 0.38, "(%s)  %s" % (key, cs), ha="center", fontsize=9)
    fig.tight_layout()
    savefig(fig, CH, "fig17-2", out_dir)


def example_graphs():
    """The graphs of Figure 17.2 as (labels, positions, adjacency)."""
    G = {}
    G["a"] = (["X", "Y", "Z"], np.array([[0, 0], [0.6, 0.8], [1.2, 0]]), adjacency(3, [(0, 1), (1, 2)]))
    G["b"] = (["X", "Y", "W", "Z"], np.array([[0, 0], [0, 0.8], [0.9, 0.8], [0.9, 0]]), adjacency(4, [(0, 1), (1, 2), (0, 2)]))
    G["c"] = (["X", "Y", "Z", "W"], np.array([[0, 0], [0, 0.8], [1.0, 0.8], [1.0, 0]]), adjacency(4, [(0, 1), (1, 2), (2, 3), (3, 0)]))
    G["d"] = (["X", "Y", "Z", "W"], np.array([[0, 0.4], [0.6, 0.4], [1.2, 0.4], [1.8, 0.4]]), adjacency(4, [(0, 1), (1, 2), (2, 3)]))
    return G


def whittaker_example():
    """The covariance matrix and graph of Figure 17.4 (missing edges 1-3 and 2-4)."""
    S = np.array([[10, 1, 5, 4], [1, 10, 2, 6], [5, 2, 10, 3], [4, 6, 3, 10.0]])
    A = adjacency(4, [(0, 1), (1, 2), (2, 3), (3, 0)])
    return S, A


def _matrix_panel(ax, M, title, fmt, hi=None, zero_mark=False):
    p = M.shape[0]
    ax.set_xlim(-0.5, p - 0.5)
    ax.set_ylim(p - 0.5, -0.5)
    for i in range(p):
        for j in range(p):
            col = "#fde2c8" if hi is not None and hi[i, j] else ("#e3ecfb" if zero_mark and abs(M[i, j]) < 1e-12 else "white")
            ax.add_patch(plt.Rectangle((j - 0.5, i - 0.5), 1, 1, fc=col, ec="#bbbbbb", lw=0.6))
            v = M[i, j]
            ax.text(j, i, fmt % (0.0 if abs(v) < 5e-13 else v), ha="center", va="center", fontsize=8.5)
    ax.set_xticks([])
    ax.set_yticks([])
    for s in ax.spines.values():
        s.set_visible(False)
    ax.set_title(title, fontsize=10)
    ax.set_aspect("equal")


def fig_17_4(out_dir=None):
    """Figure 17.4: the four-node graph and S, with the fitted Sigma-hat and Sigma-hat^{-1} of Algorithm 17.1."""
    S, A = whittaker_example()
    r = modified_regression(S, A)
    fig = plt.figure(figsize=(9.6, 2.7))
    ax0 = fig.add_axes([0.0, 0.05, 0.19, 0.85])
    pos = np.array([[0, 1], [1, 1], [1, 0], [0, 0.0]])
    draw_graph(ax0, pos, A, ["$X_1$", "$X_2$", "$X_3$", "$X_4$"], node_style="disc", node_size=0.17,
               colours=["black"] * 4, fs=10)
    ax0.set_xlim(-0.35, 1.35)
    ax0.set_ylim(-0.35, 1.35)
    changed = np.abs(r["W"] - S) > 1e-9
    for i, (M, t, f, h, z) in enumerate([(S, "S (data)", "%.0f", None, False),
                                         (r["W"], r"$\hat\Sigma$ (Algorithm 17.1)", "%.2f", changed, False),
                                         (r["Theta"], r"$\hat\Sigma^{-1}$", "%.3f", None, True)]):
        ax = fig.add_axes([0.21 + i * 0.265, 0.02, 0.25, 0.85])
        _matrix_panel(ax, M, t, f, hi=h, zero_mark=z)
    savefig(fig, CH, "fig17-4", out_dir)


def fig_17_5(out_dir=None):
    """Figure 17.5: graphical-lasso graphs of the flow-cytometry data for lambda = 36, 27, 7, 0."""
    S = sachs_cov()
    lams = [36.0, 27.0, 7.0, 0.0]
    res = glasso_path(S, lams)
    fig, axes = plt.subplots(2, 2, figsize=(7.4, 7.2))
    for ax, lam, r in zip(axes.ravel(), lams, res):
        A = edge_matrix(r["Theta"])
        _protein_graph(ax, r["Theta"], r"$\lambda = %g$  (%d edges)" % (lam, len(edges_of(A))))
    fig.tight_layout()
    savefig(fig, CH, "fig17-5", out_dir)


def _layer(ax, x0, x1, y, n, col, label, r=0.12):
    xs = np.linspace(x0, x1, n)
    for x in xs:
        ax.add_patch(Circle((x, y), r, fc=col, ec="black", lw=0.8, zorder=3))
    ax.text(x1 + 0.35, y, label, va="center", fontsize=10)
    return xs


def fig_17_6(out_dir=None):
    """Figure 17.6: a restricted Boltzmann machine V1 <-> H <-> V2 (schematic drawn by code)."""
    fig, ax = plt.subplots(figsize=(6.0, 3.0))
    rs = np.random.default_rng(6)
    xh = _layer(ax, 0.6, 4.6, 2.0, 6, "#9ec5f0", "Hidden $H$")
    x1 = _layer(ax, 0.0, 2.6, 0.4, 6, "#f4c48c", "")
    x2 = _layer(ax, 3.6, 5.0, 0.4, 3, "#a5dba5", "")
    ax.text(1.3, -0.12, "Visible $V_1$ (features)", ha="center", va="top", fontsize=10)
    ax.text(4.3, -0.12, "Visible $V_2$ (labels)", ha="center", va="top", fontsize=10)
    for xv in np.r_[x1, x2]:
        for xx in xh:
            if rs.random() < 0.55:
                ax.plot([xv, xx], [0.4, 2.0], color=GREY, lw=0.6, zorder=1)
    ax.plot([x1[2], xh[1]], [0.4, 2.0], color=RED, lw=2.0, zorder=2)
    ax.text(x1[2] - 0.05, 0.62, "$X_j$", fontsize=10, ha="right")
    ax.text(xh[1] - 0.05, 2.22, "$X_k$", fontsize=10, ha="right")
    ax.text(0.5 * (x1[2] + xh[1]) + 0.08, 1.2, r"$\theta_{jk}$", color=RED, fontsize=11)
    ax.text(x2[1] + 0.12, 0.2, r"$X_\ell$", fontsize=10, va="top")
    ax.set_xlim(-0.4, 6.6)
    ax.set_ylim(-0.5, 2.5)
    ax.set_aspect("equal")
    ax.axis("off")
    savefig(fig, CH, "fig17-6", out_dir)


def fig_17_7(out_dir=None):
    """Figure 17.7: a joint-density RBM of MNIST pixels and labels (CD-1), and difficult test digits it
    classifies correctly."""
    m = mnist_rbm()
    sc, yt = m["test_scores"].astype(float), m["test_labels"]
    pred = sc.argmax(1)
    err = (pred != yt).mean()
    P = np.exp(sc - sc.max(1, keepdims=True))
    P /= P.sum(1, keepdims=True)
    ok = np.flatnonzero(pred == yt)
    marg = P[ok, yt[ok]] - np.sort(P[ok], 1)[:, -2]
    pick = ok[np.argsort(marg)[:24]]
    Xt, _ = common.mnist(False)
    fig = plt.figure(figsize=(9.2, 3.5))
    ax = fig.add_axes([0.0, 0.0, 0.36, 1.0])
    for (y, lab, w, col) in [(2.6, "500 hidden units", 3.0, "#9ec5f0")]:
        ax.add_patch(FancyBboxPatch((0.3, y - 0.25), w, 0.5, boxstyle="round,pad=0.05", fc=col, ec="black"))
        ax.text(0.3 + w / 2, y, lab, ha="center", va="center", fontsize=10)
    ax.add_patch(FancyBboxPatch((0.0, 0.25), 2.3, 0.5, boxstyle="round,pad=0.05", fc="#f4c48c", ec="black"))
    ax.text(1.15, 0.5, "784 binary pixels", ha="center", va="center", fontsize=10)
    ax.add_patch(FancyBboxPatch((2.6, 0.25), 1.2, 0.5, boxstyle="round,pad=0.05", fc="#a5dba5", ec="black"))
    ax.text(3.2, 0.5, "10 labels", ha="center", va="center", fontsize=10)
    for x0, x1 in [(1.15, 1.4), (3.2, 2.6)]:
        ax.annotate("", xy=(x1, 2.3), xytext=(x0, 0.8), arrowprops=dict(arrowstyle="<->", lw=1.2))
    ax.text(1.95, 1.55, "symmetric\nweights", ha="center", fontsize=9, color=GREY)
    ax.text(1.9, -0.25, "test error %.2f%% (CD-1, 15 epochs)" % (100 * err), ha="center", fontsize=9)
    ax.set_xlim(-0.2, 4.0)
    ax.set_ylim(-0.5, 3.2)
    ax.axis("off")
    for i, idx in enumerate(pick):
        a = fig.add_axes([0.40 + (i % 8) * 0.075, 0.68 - (i // 8) * 0.32, 0.068, 0.27])
        a.imshow(Xt[idx].reshape(28, 28), cmap="gray_r", interpolation="nearest")
        a.set_xticks([])
        a.set_yticks([])
        a.set_title("%d" % pred[idx], fontsize=9, pad=1.5)
    savefig(fig, CH, "fig17-7", out_dir)


def exercise_graph():
    """The graph of Figure 17.8 (0-based nodes: X1..X6)."""
    pos = np.array([[0.5, 1.6], [-0.3, 0.75], [1.0, 0.72], [1.45, 1.25], [1.7, 0.35], [0.7, 0.1]])
    A = adjacency(6, [(0, 1), (0, 3), (0, 5), (1, 5), (2, 3), (4, 5)])
    return pos, A


def fig_17_8(out_dir=None):
    """Figure 17.8: the graph of Exercise 17.1, with its maximal cliques shaded (computed)."""
    pos, A = exercise_graph()
    cl = maximal_cliques(A)
    fig, ax = plt.subplots(figsize=(3.8, 3.2))
    draw_graph(ax, pos, A, ["$X_%d$" % (v + 1) for v in range(6)], node_style="disc", node_size=0.15,
               cliques=cl, colours=["black"] * len(edges_of(A)), fs=10)
    ax.set_xlim(-0.6, 2.0)
    ax.set_ylim(-0.2, 1.9)
    savefig(fig, CH, "fig17-8", out_dir)


def fig_17_s1(out_dir=None):
    """Figure 17.S1: the graphical-lasso path of the partial correlations, flow-cytometry data."""
    S = sachs_cov()
    lmax = lambda_max(S)
    lams = np.r_[0.0, np.logspace(-2, np.log10(lmax), 120)]
    res = glasso_path(S, lams)
    R = np.array([partial_correlations(r["Theta"]) for r in res])
    ne = [len(edges_of(edge_matrix(r["Theta"]))) for r in res]
    fig, axes = plt.subplots(1, 2, figsize=(9.0, 3.6), gridspec_kw=dict(width_ratios=[2.2, 1]))
    ax = axes[0]
    p = S.shape[0]
    pairs = [(j, k) for j in range(p) for k in range(j + 1, p)]
    last = {}
    for (j, k) in pairs:
        ax.plot(lams, R[:, j, k], lw=0.9, color=BLUE if abs(R[np.searchsorted(lams, 14.0), j, k]) > 0 else "#b8b8b8")
    top = sorted(pairs, key=lambda e: -abs(R[0, e[0], e[1]]))[:4]
    ys = sorted([R[0, j, k] for j, k in top], reverse=True)
    for i in range(1, len(ys)):
        ys[i] = min(ys[i], ys[i - 1] - 0.07)
    for y_lab, (j, k) in zip(ys, sorted(top, key=lambda e: -R[0, e[0], e[1]])):
        ax.text(0.012, y_lab + 0.035, "%s-%s" % (PROTEINS[j], PROTEINS[k]), ha="left", va="center", fontsize=7.5)
    for lv in [7, 14, 27, 36]:
        ax.axvline(lv, color=GREY, ls=":", lw=0.8)
    ax.set_xscale("symlog", linthresh=0.01, linscale=0.3)
    ax.set_xlim(0, lams[-1])
    ax.set_xlabel(r"$\lambda$ (logarithmic scale above 0.01)")
    ticks = [0, 0.01, 0.1, 1, 10]
    ax.set_xticks(ticks, ["0", "0.01", "0.1", "1", "10"])
    ax.set_ylabel("partial correlation")
    ax.set_title("graphical-lasso path (blue: edges present at $\\lambda=14$)", fontsize=10)
    ax2 = axes[1]
    ax2.step(lams, ne, where="post", color=RED)
    ax2.set_xscale("symlog", linthresh=0.01, linscale=0.3)
    ax2.set_xlim(0, lams[-1])
    ax2.set_xticks([0, 0.1, 10], ["0", "0.1", "10"])
    for lv in [7, 14, 27, 36]:
        ax2.axvline(lv, color=GREY, ls=":", lw=0.8)
    ax2.set_xlabel(r"$\lambda$")
    ax2.set_ylabel("number of edges")
    ax2.set_title("edges (max |s_jk| = %.1f)" % lmax)
    fig.tight_layout()
    savefig(fig, CH, "fig17-S1", out_dir)


S2_LAM = 0.02


def fig_17_s2(out_dir=None):
    """Figure 17.S2: an L1-penalised binary Markov network for the dichotomised flow data: the exact fit
    against the 'min' and 'max' node-wise approximations of Section 17.4.3."""
    Xb = sachs_binary()
    counts = cell_counts(Xb)
    lam = S2_LAM
    T_exact = ising_l1(counts, lam)
    T_min = wainwright(Xb, lam, "min")
    T_max = wainwright(Xb, lam, "max")
    fig, axes = plt.subplots(1, 3, figsize=(10.2, 3.7))
    pos = _protein_layout()
    Aex = edge_matrix(T_exact, 1e-6)
    for ax, T, tit in zip(axes, [T_exact, T_min, T_max], ["exact penalised likelihood", "'min' rule", "'max' rule"]):
        A = edge_matrix(T, 1e-6)
        cols = [BLUE if Aex[j, k] else RED for j, k in edges_of(A)]
        wid = [0.6 + 0.9 * min(abs(T[j, k]), 3.0) for j, k in edges_of(A)]
        draw_graph(ax, pos, A, PROTEINS, widths=wid, colours=cols, fs=8.5)
        ax.set_xlim(-1.32, 1.32)
        ax.set_ylim(-1.25, 1.3)
        both = int((A & Aex).sum() // 2)
        ax.set_title("%s: %d edges (%d shared)" % (tit, len(edges_of(A)), both), fontsize=10)
    fig.tight_layout()
    savefig(fig, CH, "fig17-S2", out_dir)


DEMO_RUNS = [  # (model, H, method, k, eta, iters, seed): the runs of Figure 17.S3 (presets 1 and 3 of the demo)
    ("ising", 0, "exact", 1, 0.5, 300, 1), ("ising", 0, "cd", 1, 0.5, 300, 1),
    ("rbm", 8, "exact", 1, 0.7, 400, 1), ("rbm", 8, "cd", 1, 0.7, 400, 1),
]


def fig_17_s3(out_dir=None):
    """Figure 17.S3: exact gradients against CD-1 for a fully visible Boltzmann machine (step 0.5) and an
    RBM with eight hidden units (step 0.7) on the dichotomised flow data (the exact average log-likelihood
    along the fits)."""
    counts = cell_counts(sachs_binary())
    Th_mle, _ = ising_fit_newton(counts)
    ll_mle = ising_loglik(Th_mle, counts)
    fig, axes = plt.subplots(1, 2, figsize=(9.0, 3.4))
    for ax, model in zip(axes, ["ising", "rbm"]):
        for (mo, H, meth, k, eta, iters, seed) in DEMO_RUNS:
            if mo != model:
                continue
            r = train_boltzmann(counts, mo, H, meth, k, eta, iters, seed)
            ax.plot(np.arange(iters + 1), r["loglik"], color=BLUE if meth == "exact" else ORANGE,
                    label="exact gradient" if meth == "exact" else "CD-%d" % k)
        if model == "ising":
            ax.axhline(ll_mle, color=GREY, ls="--", lw=1, label="maximum likelihood")
        ax.set_xlabel("iteration (step %g)" % [r_[4] for r_ in DEMO_RUNS if r_[0] == model][0])
        ax.set_ylabel("average log-likelihood")
        ax.set_title("fully visible Boltzmann machine" if model == "ising" else "RBM, 8 hidden units")
        ax.set_ylim(ll_mle - 0.85, ll_mle + 0.05)
        ax.legend(frameon=False, loc="lower right")
    fig.tight_layout()
    savefig(fig, CH, "fig17-S3", out_dir)


# =========================================================================== demo data
def export_demo_data():
    """../data/ch17-sachs.json: the book's covariance matrix, protein names, the counts of the 2^11 cells of
    the dichotomised data, and the exact maximum-likelihood log-likelihood of the Ising model."""
    S = sachs_cov()
    Xb = sachs_binary()
    counts = cell_counts(Xb)
    Th, _ = ising_fit_newton(counts)
    out = dict(names=PROTEINS, S=[[float("%.10g" % v) for v in row] for row in S], N=int(len(Xb)),
               counts=[int(c) for c in counts], ising_mle_loglik=float(ising_loglik(Th, counts)))
    os.makedirs(DATA_OUT, exist_ok=True)
    path = os.path.join(DATA_OUT, "ch17-sachs.json")
    with open(path, "w") as f:
        json.dump(out, f, separators=(",", ":"))
    print("wrote", os.path.relpath(path, os.getcwd()), "(%.0f kB)" % (os.path.getsize(path) / 1024))
    return path


def fig_data(out_dir=None):
    """Export the data of the demos (../data/ch17-sachs.json)."""
    export_demo_data()


# =========================================================================== driver
FIGURES = {
    "17.1": fig_17_1, "17.2": fig_17_2, "17.4": fig_17_4, "17.5": fig_17_5, "17.6": fig_17_6,
    "17.7": fig_17_7, "17.8": fig_17_8, "17.S1": fig_17_s1, "17.S2": fig_17_s2, "17.S3": fig_17_s3,
    "data": fig_data,
}


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