"""Bishop and Bishop (2024), Chapter 18: Normalizing Flows.

Reproduces the computed figures of Chapter 18 of C. M. Bishop and H. Bishop, Deep Learning:
Foundations and Concepts (Springer, 2024), pp. 547-561, written from scratch with numpy, scipy
(root finding and the normal CDF only), PyTorch (training only) and matplotlib, and supplies the
reference numbers and weights of the three browser demonstrations. Every algorithm is a short
function meant to be read next to the lecture notes (ch18-normalizing-flows.html):

* Data: two_moons(), the 'two moons' data of Figure 18.3, standardised to zero mean and unit
  variance per coordinate.
* Section 18.1, coupling flows: a real NVP flow (18.10)-(18.14) with four affine coupling layers
  that alternate between the vertical and the horizontal coordinate. train_realnvp() fits it by
  maximum likelihood (18.4) with PyTorch; CouplingFlow is a plain numpy version (forward map,
  inverse map, log-determinants, the density after each layer) that the page coupling-flow-demo.html
  reproduces number for number from data/ch18-coupling.json.
* Section 18.2, autoregressive flows: a MADE conditioner (masked weights, Germain et al. 2015) used
  as a masked autoregressive flow (MAF, (18.17)-(18.18)) and as an inverse autoregressive flow (IAF,
  (18.19)-(18.20)); each operation reports how many sequential network passes it needs
  (made_init, maf_density, maf_sample, iaf_sample, iaf_density). autoregressive-flows-demo.html
  reproduces them from the same seeded weights.
* Section 18.3.1, neural ODEs: an adaptive Dormand-Prince 5(4) integrator (dopri5) that records
  where it evaluates the network, and a fixed-step fourth-order Runge-Kutta integrator (rk4).
* Section 18.3.2, the adjoint method: a two-dimensional neural ODE whose loss gradient is computed
  three ways (back-propagation through the solver, the adjoint equations (18.25)-(18.26)
  integrated backwards, finite differences), and the discrete adjoint of the Euler residual network
  (18.38) used in Exercises 18.6 and 18.7.
* Section 18.3.3, continuous flows: the one-dimensional flow of Figure 18.6 built from a
  Gaussian-mixture path whose velocity field is obtained from the continuity equation
  (quantile_flow, velocity_1d); a two-dimensional continuous normalizing flow trained on the two
  moons by flow matching (Lipman et al. 2022) (train_cnf), whose density is computed by integrating
  the instantaneous change of variables (18.28) with the exact trace or with Hutchinson's
  estimator (18.29)-(18.30) (cnf_logp). continuous-flow-demo.html reproduces these numbers from
  data/ch18-cnf.json.
* JSRandom: the seeded generator DK.rng of the browser demos (mulberry32 uniforms, Box-Muller
  normals), so that the pages and this code draw the same noise.

Figures reproduced: 18.3 (real NVP on the two moons: the density after each coupling layer),
18.5 (a residual network with five layers against a neural ODE solved by an adaptive integrator;
the book reprints the figure from Chen et al. (2018), here the phenomenon is reproduced with our own
scalar network), and 18.6 (a one-dimensional continuous flow from a Gaussian to a three-mode
mixture, with flow lines drawn as quantiles, as described in Exercise 18.9).
Skipped: Figure 18.1 (a schematic of one real NVP layer), Figure 18.2 (a schematic of two coupled
layers), Figure 18.4 (the graph structures of MAF and IAF; its content is computed in Figure 18.S2
and shown live in autoregressive-flows-demo.html) and Figure 18.7 (a schematic for Exercise 18.8).
None of them is computed from data or a model.

Supplementary figures (our own, numbered 18.S1-18.S5 in the order they appear in the notes):
18.S1 the trained real NVP: training curve, samples, inverse map and log-determinant;
18.S2 autoregressive flows: Jacobian patterns and the cost in sequential passes of MAF and IAF;
18.S3 the adjoint method: adjoint trajectories, gradients and their error against the step size;
18.S4 Hutchinson's trace estimator: Gaussian against Rademacher probes, variance against M;
18.S5 a continuous normalizing flow trained by flow matching: trajectories, the density by (18.28),
and the error of the Hutchinson estimate of the log density.

Run `python3 ch18_normalizing_flows.py --list`, `python3 ch18_normalizing_flows.py` (all figures,
about two minutes on one CPU thread the first time, when the two flows are trained and cached in
cache/) or `python3 ch18_normalizing_flows.py --fig 18.3`. Files go to ../img/ch18/.
"""
import json
import math
import os
import time

for _v in ("OPENBLAS_NUM_THREADS", "MKL_NUM_THREADS", "OMP_NUM_THREADS"):
    os.environ.setdefault(_v, "1")

import numpy as np  # noqa: E402
import matplotlib.pyplot as plt  # noqa: E402
from scipy import stats, optimize  # noqa: E402

import common  # noqa: E402
from common import savefig, run  # noqa: E402

HERE = os.path.dirname(os.path.abspath(__file__))
WEB_DATA = os.path.normpath(os.path.join(HERE, "..", "data"))
CACHE = os.path.join(HERE, "cache")
CH = 18
M32 = 0xFFFFFFFF
LOG2PI = math.log(2 * math.pi)


# =========================================================================== 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 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)


def _g8(a):
    """Round to 8 significant digits (the precision of the exported weights)."""
    return [float("%.8g" % v) for v in np.ravel(a)]


# =========================================================================== data
def two_moons(n, seed=1, noise=0.08):
    """n points of the 'two moons' data (half on each moon, then shuffled), in raw coordinates.

    Upper moon: (cos t, sin t); lower moon: (1 - cos t, 1/2 - sin t), t uniform on (0, pi);
    isotropic Gaussian noise of standard deviation `noise` is added.
    """
    rng = np.random.default_rng(seed)
    n1 = n // 2
    t1 = rng.uniform(0, np.pi, n1)
    t2 = rng.uniform(0, np.pi, n - n1)
    X = np.r_[np.c_[np.cos(t1), np.sin(t1)], np.c_[1 - np.cos(t2), 0.5 - np.sin(t2)]]
    X = X + noise * rng.standard_normal(X.shape)
    return X[rng.permutation(n)]


def moons_data():
    """(train, test) two-moons sets of 5000 and 1000 points, standardised with the training mean
    and standard deviation (returned too)."""
    X = two_moons(6000)
    tr, te = X[:5000], X[5000:]
    mu, sd = tr.mean(0), tr.std(0)
    return (tr - mu) / sd, (te - mu) / sd, mu, sd


# =========================================================================== 18.1 coupling flows (numpy)
def _tanh_mlp(u, W1, b1, W2, b2, W3, b3):
    """Conditioner network 1 -> H -> H -> 2 with tanh hidden units; u has shape (n,)."""
    h1 = np.tanh(np.outer(u, W1[:, 0]) + b1)
    h2 = np.tanh(h1 @ W2.T + b2)
    o = h2 @ W3.T + b3
    return o[:, 0], o[:, 1]


class CouplingFlow:
    """A real NVP flow on R^2 made of affine coupling layers (18.10)-(18.11).

    layers is a list of dicts with keys act (the coordinate that is transformed, 0 or 1) and the
    conditioner weights W1 (H x 1), b1, W2 (H x H), b2, W3 (2 x H), b3. The conditioner output is
    (s, b). Layer k maps its input u to its output v by
        v[pas] = u[pas],   v[act] = exp(s(u[pas])) * u[act] + b(u[pas]),
    and layers are applied in list order in the generative direction z -> x.
    """

    def __init__(self, layers):
        self.layers = []
        for L in layers:
            H = len(L["b1"])
            self.layers.append(dict(act=int(L["act"]), W1=np.array(L["W1"], float).reshape(H, 1),
                                    b1=np.array(L["b1"], float), W2=np.array(L["W2"], float).reshape(H, H),
                                    b2=np.array(L["b2"], float), W3=np.array(L["W3"], float).reshape(2, H),
                                    b3=np.array(L["b3"], float)))

    def cond(self, k, u):
        L = self.layers[k]
        return _tanh_mlp(u, L["W1"], L["b1"], L["W2"], L["b2"], L["W3"], L["b3"])

    def forward(self, z, upto=None):
        """x = f(z) after the first `upto` layers (all by default), with ln|det dx/dz| = sum of s."""
        x = np.array(z, float, copy=True)
        ld = np.zeros(len(x))
        for k in range(len(self.layers) if upto is None else upto):
            a = self.layers[k]["act"]
            s, b = self.cond(k, x[:, 1 - a])
            x[:, a] = np.exp(s) * x[:, a] + b
            ld += s
        return x, ld

    def inverse(self, x, upto=None):
        """z = g(x) through the first `upto` layers, inverted in reverse order (18.12)-(18.13), with
        ln|det dz/dx| = minus the sum of s (the log of the product of the diagonal of (18.14))."""
        z = np.array(x, float, copy=True)
        ld = np.zeros(len(z))
        K = len(self.layers) if upto is None else upto
        for k in reversed(range(K)):
            a = self.layers[k]["act"]
            s, b = self.cond(k, z[:, 1 - a])
            z[:, a] = (z[:, a] - b) * np.exp(-s)
            ld -= s
        return z, ld

    def log_prob(self, x, upto=None):
        """ln p(x) by the change of variables (18.1) with a standard Gaussian base."""
        z, ld = self.inverse(x, upto)
        return -0.5 * (z ** 2).sum(1) - LOG2PI + ld

    def path(self, x):
        """The point x and its images after inverting layer K, K-1, ..., 1, with the s value of each
        inverted layer (used by the demo's probe)."""
        z = np.array(x, float, copy=True).reshape(1, 2)
        pts, ss = [z.copy()], []
        for k in reversed(range(len(self.layers))):
            a = self.layers[k]["act"]
            s, b = self.cond(k, z[:, 1 - a])
            z[:, a] = (z[:, a] - b) * np.exp(-s)
            pts.append(z.copy())
            ss.append(float(s[0]))
        return np.vstack(pts), ss


def coupling_jacobian_fd(flow, x, h=1e-6):
    """Central-difference Jacobian dz/dx of the inverse map at one point x (2 x 2)."""
    J = np.zeros((2, 2))
    for j in range(2):
        e = np.zeros(2)
        e[j] = h
        J[:, j] = (flow.inverse((x + e)[None])[0][0] - flow.inverse((x - e)[None])[0][0]) / (2 * h)
    return J


# =========================================================================== 18.1 coupling flows (training)
def _torch_realnvp(H, L, torch):
    class Cond(torch.nn.Module):
        def __init__(s):
            super().__init__()
            s.l1 = torch.nn.Linear(1, H)
            s.l2 = torch.nn.Linear(H, H)
            s.l3 = torch.nn.Linear(H, 2)
            torch.nn.init.zeros_(s.l3.weight)   # every layer starts as the identity map
            torch.nn.init.zeros_(s.l3.bias)

        def forward(s, u):
            o = s.l3(torch.tanh(s.l2(torch.tanh(s.l1(u)))))
            return o[:, 0], o[:, 1]

    return torch.nn.ModuleList([Cond() for _ in range(L)]).double()


def _realnvp_layers(nets, L):
    out = []
    for k in range(L):
        c = nets[k]
        out.append(dict(act=1 if k % 2 == 0 else 0,
                        W1=_g8(c.l1.weight.detach().numpy()), b1=_g8(c.l1.bias.detach().numpy()),
                        W2=_g8(c.l2.weight.detach().numpy()), b2=_g8(c.l2.bias.detach().numpy()),
                        W3=_g8(c.l3.weight.detach().numpy()), b3=_g8(c.l3.bias.detach().numpy())))
    return out


def train_realnvp(H=32, L=4, steps=4000, batch=512, lr=3e-3, seed=0, snapshots=(0, 100, 500, 4000), force=False):
    """Train the four-layer real NVP of Figure 18.3 by maximum likelihood (18.4) with Adam.

    Layer 1 transforms the vertical coordinate given the horizontal one, layer 2 the horizontal
    given the vertical, and so on (as in panels (b)-(e) of Figure 18.3). Returns a dict with the
    weights (rounded to 8 significant digits) at the requested iterations and the training
    history (train and test negative log likelihood per point). Cached in cache/ch18_realnvp.json.
    """
    path = os.path.join(CACHE, "ch18_realnvp.json")
    if os.path.exists(path) and not force:
        with open(path) as f:
            return json.load(f)
    torch = common.torch_setup(seed, threads=1)
    Xtr, Xte, mu, sd = moons_data()
    Xt, Xv = torch.tensor(Xtr), torch.tensor(Xte)
    nets = _torch_realnvp(H, L, torch)

    def nll(x):
        ld = torch.zeros(x.shape[0], dtype=torch.float64)
        for k in reversed(range(L)):
            a = 1 if k % 2 == 0 else 0
            s, b = nets[k](x[:, 1 - a:2 - a])
            x = x.clone()
            x[:, a] = (x[:, a] - b) * torch.exp(-s)
            ld = ld - s
        return (0.5 * (x ** 2).sum(1) + LOG2PI - ld).mean()

    opt = torch.optim.Adam(nets.parameters(), lr=lr)
    sched = torch.optim.lr_scheduler.CosineAnnealingLR(opt, steps)
    g = torch.Generator().manual_seed(seed)
    snaps, hist = {}, {"it": [], "train": [], "test": []}
    t0 = time.time()
    for it in range(steps + 1):
        if it in snapshots:
            snaps[str(it)] = _realnvp_layers(nets, L)
        if it % 50 == 0:
            with torch.no_grad():
                hist["it"].append(it)
                hist["train"].append(float(nll(Xt)))
                hist["test"].append(float(nll(Xv)))
        if it == steps:
            break
        idx = torch.randint(0, len(Xt), (batch,), generator=g)
        loss = nll(Xt[idx])
        opt.zero_grad()
        loss.backward()
        opt.step()
        sched.step()
    res = dict(H=H, L=L, steps=steps, batch=batch, lr=lr, seed=seed, snapshots=snaps, hist=hist,
               mu=list(mu), sd=list(sd), seconds=time.time() - t0)
    os.makedirs(CACHE, exist_ok=True)
    with open(path, "w") as f:
        json.dump(res, f)
    return res


def realnvp_final():
    r = train_realnvp()
    return CouplingFlow(r["snapshots"][str(r["steps"])])


# =========================================================================== 18.2 autoregressive flows
def made_init(D, H=None, seed=7, scale=0.9):
    """A MADE conditioner for D variables with one hidden layer of H tanh units (default 2D, at
    least 8). Hidden unit k has degree m_k = 1 + (k mod (D-1)); input d (1-based) feeds unit k only
    if m_k >= d and unit k feeds output i only if i > m_k, so output i depends on inputs 1..i-1.
    Outputs are (mu_i, alpha_i) for each i. Weights are JSRandom normals drawn in the order W1
    (row by row), b1, W2, b2, as in autoregressive-flows-demo.html."""
    H = H or max(8, 2 * D)
    rng = JSRandom(seed)
    m = np.array([1 + (k % max(D - 1, 1)) for k in range(H)])
    M1 = (m[:, None] >= np.arange(1, D + 1)[None, :]).astype(float)
    Mo = (np.arange(1, D + 1)[:, None] > m[None, :]).astype(float)
    M2 = np.r_[Mo, Mo]
    W1 = np.array([[rng.norm() for _ in range(D)] for _ in range(H)]) * (scale / math.sqrt(D))
    b1 = np.array([rng.norm() for _ in range(H)]) * 0.5
    W2 = np.array([[rng.norm() for _ in range(H)] for _ in range(2 * D)]) * (scale / math.sqrt(H))
    b2 = np.array([rng.norm() for _ in range(2 * D)]) * 0.3
    return dict(D=D, H=H, m=m, M1=M1, M2=M2, W1=W1 * M1, b1=b1, W2=W2 * M2, b2=b2)


def made_pass(P, u):
    """One network pass: (mu, alpha) for every i from the vector u (shape (D,) or (n, D))."""
    u = np.atleast_2d(u)
    h = np.tanh(u @ P["W1"].T + P["b1"])
    o = h @ P["W2"].T + P["b2"]
    D = P["D"]
    return o[:, :D], o[:, D:]


def maf_density(P, x):
    """MAF (18.18): z_i = (x_i - mu_i(x_<i)) exp(-alpha_i(x_<i)) for all i at once.
    Returns z, ln p(x) and the number of sequential network passes (1)."""
    x = np.atleast_2d(x)
    mu, al = made_pass(P, x)
    z = (x - mu) * np.exp(-al)
    lp = -0.5 * (z ** 2).sum(1) - 0.5 * P["D"] * LOG2PI - al.sum(1)
    return z, lp, 1


def maf_sample(P, z):
    """MAF (18.17): x_i = mu_i(x_<i) + exp(alpha_i(x_<i)) z_i, one variable per pass (D passes)."""
    z = np.atleast_2d(z)
    x = np.zeros_like(z)
    for i in range(P["D"]):
        mu, al = made_pass(P, x)
        x[:, i] = mu[:, i] + np.exp(al[:, i]) * z[:, i]
    return x, P["D"]


def iaf_sample(P, z):
    """IAF (18.19): x_i = mu_i(z_<i) + exp(alpha_i(z_<i)) z_i for all i at once (1 pass); the log
    density of the sample is available from the same pass."""
    z = np.atleast_2d(z)
    mu, al = made_pass(P, z)
    x = mu + np.exp(al) * z
    lp = -0.5 * (z ** 2).sum(1) - 0.5 * P["D"] * LOG2PI - al.sum(1)
    return x, lp, 1


def iaf_density(P, x):
    """IAF inverse (18.20): z_i = (x_i - mu_i(z_<i)) exp(-alpha_i(z_<i)), one variable per pass."""
    x = np.atleast_2d(x)
    z = np.zeros_like(x)
    al_all = np.zeros_like(x)
    for i in range(P["D"]):
        mu, al = made_pass(P, z)
        z[:, i] = (x[:, i] - mu[:, i]) * np.exp(-al[:, i])
        al_all[:, i] = al[:, i]
    lp = -0.5 * (z ** 2).sum(1) - 0.5 * P["D"] * LOG2PI - al_all.sum(1)
    return z, lp, P["D"]


def jacobian_fd(fun, x, h=1e-6):
    """Central-difference Jacobian of fun: R^D -> R^D at x."""
    x = np.asarray(x, float)
    D = len(x)
    J = np.zeros((D, D))
    for j in range(D):
        e = np.zeros(D)
        e[j] = h
        J[:, j] = (fun(x + e) - fun(x - e)) / (2 * h)
    return J


def made_torch(D, H, seed, torch):
    """A MADE in PyTorch with the same masks (for timing and autograd Jacobians)."""
    P = made_init(D, H, seed)
    W1 = torch.tensor(P["W1"])
    b1 = torch.tensor(P["b1"])
    W2 = torch.tensor(P["W2"])
    b2 = torch.tensor(P["b2"])

    def f(u):
        o = torch.tanh(u @ W1.T + b1) @ W2.T + b2
        return o[:, :D], o[:, D:]
    return f


def ar_timing(Ds=(2, 4, 8, 16, 32, 64), n=256, reps=5, seed=0):
    """Wall-clock seconds (best of reps) for one batch of n points: MAF density, MAF sampling,
    IAF sampling, IAF density of an external point, with MADE conditioners of width 4D."""
    torch = common.torch_setup(seed, threads=1)
    out = {k: [] for k in ("maf_density", "maf_sample", "iaf_sample", "iaf_density")}
    for D in Ds:
        f = made_torch(D, 4 * D, 7, torch)
        X = torch.randn(n, D, dtype=torch.float64)

        def maf_d():
            mu, al = f(X)
            return (X - mu) * torch.exp(-al)

        def seq(inp_is_z):
            u = torch.zeros(n, D, dtype=torch.float64)
            for i in range(D):
                mu, al = f(u)
                if inp_is_z:   # MAF sampling: u is x being filled in
                    u[:, i] = mu[:, i] + torch.exp(al[:, i]) * X[:, i]
                else:          # IAF density: u is z being filled in
                    u[:, i] = (X[:, i] - mu[:, i]) * torch.exp(-al[:, i])
            return u

        def iaf_s():
            mu, al = f(X)
            return mu + torch.exp(al) * X

        with torch.no_grad():
            for key, fn in (("maf_density", maf_d), ("maf_sample", lambda: seq(True)),
                            ("iaf_sample", iaf_s), ("iaf_density", lambda: seq(False))):
                best = 1e9
                for _ in range(reps):
                    t0 = time.perf_counter()
                    fn()
                    best = min(best, time.perf_counter() - t0)
                out[key].append(best)
    return dict(D=list(Ds), **out)


# =========================================================================== 18.3.1 ODE integrators
DP_C = np.array([0, 1 / 5, 3 / 10, 4 / 5, 8 / 9, 1, 1])
DP_A = [[], [1 / 5], [3 / 40, 9 / 40], [44 / 45, -56 / 15, 32 / 9],
        [19372 / 6561, -25360 / 2187, 64448 / 6561, -212 / 729],
        [9017 / 3168, -355 / 33, 46732 / 5247, 49 / 176, -5103 / 18656],
        [35 / 384, 0, 500 / 1113, 125 / 192, -2187 / 6784, 11 / 84]]
DP_B5 = np.array([35 / 384, 0, 500 / 1113, 125 / 192, -2187 / 6784, 11 / 84, 0])
DP_B4 = np.array([5179 / 57600, 0, 7571 / 16695, 393 / 640, -92097 / 339200, 187 / 2100, 1 / 40])


def dopri5(f, y0, t0, t1, rtol=1e-5, atol=1e-7, h0=None):
    """Adaptive Dormand-Prince 5(4) integration of dy/dt = f(t, y) from t0 to t1.

    Returns the accepted times and states and the list of times at which f was evaluated
    (including rejected steps), the quantity that 'replaces depth' in Section 18.3.1.
    """
    y = np.atleast_1d(np.array(y0, float))
    t, h = t0, h0 or 0.1 * (t1 - t0)
    ts, ys, evals = [t], [y.copy()], []
    k1 = f(t, y)
    evals.append(t)
    while t < t1 - 1e-12:
        h = min(h, t1 - t)
        K = [k1]
        for s in range(1, 7):
            yy = y + h * sum(a * k for a, k in zip(DP_A[s], K))
            K.append(f(t + DP_C[s] * h, yy))
            evals.append(t + DP_C[s] * h)
        y5 = y + h * sum(b * k for b, k in zip(DP_B5, K))
        y4 = y + h * sum(b * k for b, k in zip(DP_B4, K))
        sc = atol + rtol * np.maximum(np.abs(y), np.abs(y5))
        err = math.sqrt(np.mean(((y5 - y4) / sc) ** 2))
        if err <= 1.0:
            t, y, k1 = t + h, y5, K[6]       # first-same-as-last: K[6] = f(t + h, y5)
            ts.append(t)
            ys.append(y.copy())
        h = h * min(5.0, max(0.2, 0.9 * (err + 1e-16) ** -0.2))
    return np.array(ts), np.array(ys), np.array(evals)


def rk4(f, y0, t0, t1, n):
    """Classical fourth-order Runge-Kutta with n equal steps; returns the n+1 states."""
    y = np.array(y0, float)
    h = (t1 - t0) / n
    out = [y.copy()]
    t = t0
    for _ in range(n):
        k1 = f(t, y)
        k2 = f(t + h / 2, y + h / 2 * k1)
        k3 = f(t + h / 2, y + h / 2 * k2)
        k4 = f(t + h, y + h * k3)
        y = y + h / 6 * (k1 + 2 * k2 + 2 * k3 + k4)
        t += h
        out.append(y.copy())
    return np.array(out)


def f_scalar(t, z):
    """The scalar 'network' of Figure 18.5: f(z, t) = 1.2 tanh(2 z) sin(1.3 t) - 0.35 z + 0.25 cos(3 z)."""
    return 1.2 * np.tanh(2 * z) * np.sin(1.3 * t) - 0.35 * z + 0.25 * np.cos(3 * z)


# =========================================================================== 18.3.2 the adjoint method
def node_params(seed=3, H=8):
    """A small two-dimensional neural ODE f(z, w) = A tanh(B z + c) + d (time-independent)."""
    rng = np.random.default_rng(seed)
    return dict(A=rng.normal(0, 0.8, (2, H)), B=rng.normal(0, 0.8, (H, 2)), c=rng.normal(0, 0.5, H), d=rng.normal(0, 0.2, 2))


def node_f(P, z):
    return P["A"] @ np.tanh(P["B"] @ z + P["c"]) + P["d"]


def node_dfdz(P, z):
    s = 1 - np.tanh(P["B"] @ z + P["c"]) ** 2
    return P["A"] @ (s[:, None] * P["B"])


def node_aT_dfdw(P, z, a):
    """a^T df/dw for every parameter (a dict of arrays shaped like the parameters)."""
    h = np.tanh(P["B"] @ z + P["c"])
    s = 1 - h ** 2
    g = (P["A"].T @ a) * s                      # a^T A diag(s), a vector over hidden units
    return dict(A=np.outer(a, h), B=np.outer(g, z), c=g, d=a.copy())


def _flat(dct, keys=("A", "B", "c", "d")):
    return np.concatenate([np.ravel(dct[k]) for k in keys])


def _unflat(v, P, keys=("A", "B", "c", "d")):
    out, i = {}, 0
    for k in keys:
        n = np.size(P[k])
        out[k] = v[i:i + n].reshape(np.shape(P[k]))
        i += n
    return out


def node_loss(P, z0, y, T=2.0, n=200):
    """L = ||z(T) - y||^2 / 2 with z(T) from RK4 with n steps."""
    zT = rk4(lambda t, z: node_f(P, z), z0, 0.0, T, n)[-1]
    return 0.5 * np.sum((zT - y) ** 2), zT


def node_adjoint_grad(P, z0, y, T=2.0, n=200, record=False):
    """The adjoint method of Section 18.3.2: integrate z forwards to z(T), then integrate the
    augmented state (z, a, g) backwards from t = T to t = 0 with
        dz/dt = f,  da/dt = -a^T df/dz  (18.25),  dg/dt = -a^T df/dw,
    starting from a(T) = dL/dz(T), g(T) = 0. Then dL/dw = g(0) = int_0^T a^T df/dw dt and
    dL/dz(0) = a(0). The state z is recomputed backwards, not stored."""
    zT = rk4(lambda t, z: node_f(P, z), z0, 0.0, T, n)[-1]
    aT = zT - y
    nz, nw = 2, len(_flat(P))

    def aug(t, s):
        z, a = s[:nz], s[nz:2 * nz]
        dz = node_f(P, z)
        da = -a @ node_dfdz(P, z)
        dg = -_flat(node_aT_dfdw(P, z, a))
        return np.concatenate([dz, da, dg])

    s0 = np.concatenate([zT, aT, np.zeros(nw)])
    traj = rk4(aug, s0, T, 0.0, n)            # negative step: from T back to 0
    sF = traj[-1]
    out = dict(dLdw=sF[2 * nz:], dLdz0=sF[nz:2 * nz], z0_rec=sF[:nz], zT=zT)
    if record:
        out["t"] = np.linspace(T, 0.0, n + 1)
        out["z"] = traj[:, :nz]
        out["a"] = traj[:, nz:2 * nz]
    return out


def node_backprop_grad(P, z0, y, T=2.0, n=200):
    """dL/dw by differentiating through every RK4 step (reverse-mode automatic differentiation)."""
    torch = common.torch_setup(0, threads=1)
    Pt = {k: torch.tensor(v, requires_grad=True) for k, v in P.items()}

    def f(z):
        return Pt["A"] @ torch.tanh(Pt["B"] @ z + Pt["c"]) + Pt["d"]
    z = torch.tensor(z0, dtype=torch.float64)
    h = T / n
    for _ in range(n):
        k1 = f(z)
        k2 = f(z + h / 2 * k1)
        k3 = f(z + h / 2 * k2)
        k4 = f(z + h * k3)
        z = z + h / 6 * (k1 + 2 * k2 + 2 * k3 + k4)
    L = 0.5 * ((z - torch.tensor(y)) ** 2).sum()
    L.backward()
    return _flat({k: v.grad.numpy() for k, v in Pt.items()})


def euler_resnet_grads(P, z0, y, T=2.0, n=20):
    """Residual network (18.38) z_{t+eps} = z_t + eps f(z_t) with eps = T/n. Returns the discrete
    adjoints a_k = dL/dz_k by the backward recursion a_k = a_{k+1} (I + eps df/dz(z_k)) and the
    weight gradient sum_k eps a_{k+1}^T df/dw(z_k) (Exercises 18.6 and 18.7)."""
    eps = T / n
    zs = [np.array(z0, float)]
    for _ in range(n):
        zs.append(zs[-1] + eps * node_f(P, zs[-1]))
    a = [None] * (n + 1)
    a[n] = zs[n] - y
    g = np.zeros(len(_flat(P)))
    for k in range(n - 1, -1, -1):
        g += eps * _flat(node_aT_dfdw(P, zs[k], a[k + 1]))
        a[k] = a[k + 1] @ (np.eye(2) + eps * node_dfdz(P, zs[k]))
    return np.array(zs), np.array(a), g


# =========================================================================== 18.3.3 a 1-D continuous flow (Figure 18.6)
MIX1D = dict(pi=np.array([0.3, 0.4, 0.3]), m=np.array([-2.2, 0.2, 2.3]), s=np.array([0.35, 0.4, 0.3]))


def path_1d(t):
    """The probability path p_t of Figure 18.6: the law of (1-t) z0 + t x1 with z0 ~ N(0, 1) and x1
    from the three-component mixture MIX1D. Component k is N(t m_k, (1-t)^2 + t^2 s_k^2), so p_0 is
    N(0, 1) and p_1 is the mixture. Returns (weights, means, standard deviations)."""
    sd = np.sqrt((1 - t) ** 2 + t ** 2 * MIX1D["s"] ** 2)
    return MIX1D["pi"], t * MIX1D["m"], sd


def pdf_1d(z, t):
    w, m, s = path_1d(t)
    z = np.asarray(z, float)[..., None]
    return (w * stats.norm.pdf(z, m, s)).sum(-1)


def cdf_1d(z, t):
    w, m, s = path_1d(t)
    z = np.asarray(z, float)[..., None]
    return (w * stats.norm.cdf(z, m, s)).sum(-1)


def dcdf_dt_1d(z, t):
    """d/dt of the CDF at fixed z: for each component, d/dt Phi((z - mu)/sd) = -phi(u) d/dt[(z - mu)/sd]."""
    w, m, s = path_1d(t)
    dm = MIX1D["m"]
    ds = (-(1 - t) + t * MIX1D["s"] ** 2) / s
    z = np.asarray(z, float)[..., None]
    u = (z - m) / s
    du = (-dm * s - (z - m) * ds) / s ** 2
    return (w * stats.norm.pdf(u) * du).sum(-1)


def velocity_1d(z, t):
    """The unique velocity field that transports p_t (continuity equation with decay at infinity):
    f(z, t) = -(d/dt F_t(z)) / p_t(z)."""
    return -dcdf_dt_1d(z, t) / pdf_1d(z, t)


def fm_velocity_1d(z, t):
    """The flow-matching marginal velocity E[x1 - z0 | (1-t) z0 + t x1 = z], in closed form
    (Gaussian conditioning within each component, weighted by the component posterior)."""
    w, m, s = path_1d(t)
    z = np.asarray(z, float)[..., None]
    cov = t * MIX1D["s"] ** 2 - (1 - t)
    cond = MIX1D["m"] + cov / s ** 2 * (z - m)
    r = w * stats.norm.pdf(z, m, s)
    return (r * cond).sum(-1) / r.sum(-1)


def quantile_1d(u, t):
    """F_t^{-1}(u) by Brent's method."""
    return np.array([optimize.brentq(lambda z: cdf_1d(z, t) - ui, -12, 12, xtol=1e-13) for ui in np.atleast_1d(u)])


def quantile_flow(us, ts):
    """Flow lines of Figure 18.6: z(t) = F_t^{-1}(u) for each u (rows) and t (columns)."""
    return np.array([[quantile_1d(u, t)[0] for t in ts] for u in us])


# =========================================================================== 18.3.3 a 2-D continuous normalizing flow
def train_cnf(H=32, steps=20000, batch=512, lr=3e-3, seed=0, force=False):
    """A continuous normalizing flow on the two moons, trained by (conditional) flow matching:
    regress v(x_t, t) on x1 - x0 with x0 ~ N(0, I), x1 a data point, x_t = (1-t) x0 + t x1, t ~ U(0,1).
    v is a tanh network 3 -> H -> H -> 2. Cached in cache/ch18_cnf.json (weights rounded to 8
    significant digits, the precision of data/ch18-cnf.json)."""
    path = os.path.join(CACHE, "ch18_cnf.json")
    if os.path.exists(path) and not force:
        with open(path) as f:
            return json.load(f)
    torch = common.torch_setup(seed, threads=1)
    Xtr, Xte, mu, sd = moons_data()
    Xt = torch.tensor(Xtr)
    net = torch.nn.Sequential(torch.nn.Linear(3, H), torch.nn.Tanh(), torch.nn.Linear(H, H), torch.nn.Tanh(),
                              torch.nn.Linear(H, 2)).double()
    opt = torch.optim.Adam(net.parameters(), lr=lr)
    sched = torch.optim.lr_scheduler.CosineAnnealingLR(opt, steps)
    g = torch.Generator().manual_seed(seed)
    hist = []
    t0 = time.time()
    for it in range(steps):
        idx = torch.randint(0, len(Xt), (batch,), generator=g)
        x1 = Xt[idx]
        x0 = torch.randn(batch, 2, generator=g, dtype=torch.float64)
        t = torch.rand(batch, 1, generator=g, dtype=torch.float64)
        xt = (1 - t) * x0 + t * x1
        loss = ((net(torch.cat([xt, t], 1)) - (x1 - x0)) ** 2).sum(1).mean()
        opt.zero_grad()
        loss.backward()
        opt.step()
        sched.step()
        if it % 100 == 0:
            hist.append(float(loss.detach()))
    W = [p.detach().numpy() for p in net.parameters()]
    res = dict(H=H, steps=steps, batch=batch, lr=lr, seed=seed, W1=_g8(W[0]), b1=_g8(W[1]), W2=_g8(W[2]),
               b2=_g8(W[3]), W3=_g8(W[4]), b3=_g8(W[5]), loss=hist, mu=list(mu), sd=list(sd), seconds=time.time() - t0)
    os.makedirs(CACHE, exist_ok=True)
    with open(path, "w") as f:
        json.dump(res, f)
    return res


class CNF:
    """The trained velocity field v(x, t) = W3 tanh(W2 tanh(W1 [x, t] + b1) + b2) + b3 with its exact
    Jacobian dv/dx = W3 diag(1 - h2^2) W2 diag(1 - h1^2) W1[:, :2]."""

    def __init__(self, d):
        H = d["H"]
        self.H = H
        self.W1 = np.array(d["W1"]).reshape(H, 3)
        self.b1 = np.array(d["b1"])
        self.W2 = np.array(d["W2"]).reshape(H, H)
        self.b2 = np.array(d["b2"])
        self.W3 = np.array(d["W3"]).reshape(2, H)
        self.b3 = np.array(d["b3"])

    def vel_jac(self, x, t):
        x = np.atleast_2d(x)
        h1 = np.tanh(x @ self.W1[:, :2].T + t * self.W1[:, 2] + self.b1)
        h2 = np.tanh(h1 @ self.W2.T + self.b2)
        v = h2 @ self.W3.T + self.b3
        A = np.einsum("kj,nj,ji->nki", self.W2, 1 - h1 ** 2, self.W1[:, :2])
        J = np.einsum("ik,nk,nkj->nij", self.W3, 1 - h2 ** 2, A)
        return v, J

    def vel(self, x, t):
        return self.vel_jac(x, t)[0]

    def _rhs(self, x, t, eps):
        """Velocity and the trace term: exact trace, or the Hutchinson average over the probes eps
        (shape (n, M, 2)) of eps^T J eps."""
        v, J = self.vel_jac(x, t)
        if eps is None:
            tr = J[:, 0, 0] + J[:, 1, 1]
        else:
            tr = np.einsum("nmi,nij,nmj->nm", eps, J, eps).mean(1)
        return v, tr

    def push(self, z, t1=1.0, n=20, t0=0.0, eps=None, keep=False):
        """Integrate dx/dt = v and d ln p/dt = -tr(dv/dx) (18.28) from t0 to t1 with RK4 (n steps).
        Returns the end points, the integral of the trace, and optionally the trajectory."""
        x = np.array(np.atleast_2d(z), float)
        h = (t1 - t0) / n
        acc = np.zeros(len(x))
        t = t0
        traj = [x.copy()]
        for _ in range(n):
            v1, d1 = self._rhs(x, t, eps)
            v2, d2 = self._rhs(x + h / 2 * v1, t + h / 2, eps)
            v3, d3 = self._rhs(x + h / 2 * v2, t + h / 2, eps)
            v4, d4 = self._rhs(x + h * v3, t + h, eps)
            x = x + h / 6 * (v1 + 2 * v2 + 2 * v3 + v4)
            acc = acc + h / 6 * (d1 + 2 * d2 + 2 * d3 + d4)
            t += h
            if keep:
                traj.append(x.copy())
        return (x, acc, np.array(traj)) if keep else (x, acc)

    def logp(self, x, t=1.0, n=20, eps=None):
        """ln p_t(x): integrate backwards from t to 0 and use ln p_t(x) = ln N(z(0)) - int_0^t tr dt'."""
        z, acc = self.push(x, t1=0.0, t0=t, n=n, eps=eps)
        # acc = int_t^0 tr dt' = -int_0^t tr dt'
        return -0.5 * (z ** 2).sum(1) - LOG2PI + acc, z


def cnf_final():
    return CNF(train_cnf())


def hutch_probes(n, M, kind, seed):
    """Probe vectors for n points and M probes each, drawn from JSRandom in the order
    point, probe, coordinate: Gaussian (norm()) or Rademacher (u() < 0.5 gives -1, else +1)."""
    rng = JSRandom(seed)
    E = np.zeros((n, M, 2))
    for p in range(n):
        for m in range(M):
            for i in range(2):
                E[p, m, i] = rng.norm() if kind == "gauss" else (-1.0 if rng.u() < 0.5 else 1.0)
    return E


def hutch_var(A, kind):
    """Exact variance of the single-probe estimator eps^T A eps: with S = (A + A^T)/2 and probes with
    independent coordinates of mean 0, variance 1 and fourth moment mu4,
    var = 2 ||S||_F^2 + (mu4 - 3) sum_i S_ii^2 (Gaussian: mu4 = 3; Rademacher: mu4 = 1)."""
    S = 0.5 * (A + A.T)
    mu4 = 3.0 if kind == "gauss" else 1.0
    return 2 * np.sum(S ** 2) + (mu4 - 3) * np.sum(np.diag(S) ** 2)


# =========================================================================== JSON exports for the demos
def coupling_test_points():
    return np.array([[0.0, 0.0], [-1.0, 0.8], [1.2, -0.9], [0.4, 1.4], [-1.5, -1.0]])


def export_coupling_json(path=None):
    """data/ch18-coupling.json: the real NVP weights at four training iterations, 600 data points,
    the training history and reference values (log densities of test points, inverse images, and
    forward images of 5 base samples drawn from JSRandom(5)) for the browser demo."""
    r = train_realnvp()
    Xtr, Xte, mu, sd = moons_data()
    ref = {}
    P = coupling_test_points()
    rng = JSRandom(5)
    Z = np.array([[rng.norm(), rng.norm()] for _ in range(5)])
    for it, layers in r["snapshots"].items():
        fl = CouplingFlow(layers)
        z, ld = fl.inverse(P)
        x, ldf = fl.forward(Z)
        ref[it] = dict(logp=list(fl.log_prob(P)), z=z.tolist(), ld=list(ld), xs=x.tolist(), ldf=list(ldf),
                       stage_logp=[list(fl.log_prob(P, upto=k)) for k in range(5)])
    d = dict(H=r["H"], L=r["L"], snapshots=r["snapshots"], iters=sorted(int(k) for k in r["snapshots"]),
             data=np.round(Xtr[:600], 4).tolist(), hist=dict(it=r["hist"]["it"][::4], train=_g8(r["hist"]["train"][::4]),
                                                              test=_g8(r["hist"]["test"][::4])),
             test=P.tolist(), base5=Z.tolist(), ref=ref)
    path = path or os.path.join(WEB_DATA, "ch18-coupling.json")
    os.makedirs(os.path.dirname(path), exist_ok=True)
    with open(path, "w") as f:
        json.dump(d, f, separators=(",", ":"))
    print("wrote", os.path.relpath(path), "(%.0f kB)" % (os.path.getsize(path) / 1e3))


def cnf_test_points():
    return np.array([[0.0, 0.0], [-1.0, 0.8], [1.2, -0.9], [0.4, 1.4], [-1.5, -1.0], [1.0, 1.0]])


def export_cnf_json(path=None):
    """data/ch18-cnf.json: the flow-matching velocity field, 600 data points and reference values
    (log densities by the exact trace and by Hutchinson's estimator, and pushed-forward samples)."""
    r = train_cnf()
    cnf = CNF(r)
    Xtr, Xte, mu, sd = moons_data()
    P = cnf_test_points()
    ref = {}
    for n in (5, 20):
        lp, z = cnf.logp(P, n=n)
        ref["exact%d" % n] = dict(logp=list(lp), z=z.tolist())
    for kind in ("gauss", "rad"):
        E = hutch_probes(len(P), 1, kind, seed=11)
        lp, _ = cnf.logp(P, n=20, eps=E)
        ref["hutch_" + kind] = dict(logp=list(lp))
    rng = JSRandom(9)
    Z = np.array([[rng.norm(), rng.norm()] for _ in range(4)])
    x, acc = cnf.push(Z, n=20)
    ref["push"] = dict(z=Z.tolist(), x=x.tolist(), acc=list(acc))
    d = dict(H=r["H"], W1=r["W1"], b1=r["b1"], W2=r["W2"], b2=r["b2"], W3=r["W3"], b3=r["b3"],
             data=np.round(Xtr[:600], 4).tolist(), test=P.tolist(), ref=ref)
    path = path or os.path.join(WEB_DATA, "ch18-cnf.json")
    with open(path, "w") as f:
        json.dump(d, f, separators=(",", ":"))
    print("wrote", os.path.relpath(path), "(%.0f kB)" % (os.path.getsize(path) / 1e3))


# =========================================================================== figures
GRID = (-2.6, 2.6, -2.6, 2.6)


def _grid(n=161, box=GRID):
    xs = np.linspace(box[0], box[1], n)
    ys = np.linspace(box[2], box[3], n)
    XX, YY = np.meshgrid(xs, ys)
    return xs, ys, np.c_[XX.ravel(), YY.ravel()]


def fig_18_3(out_dir=None):
    """Figure 18.3: real NVP on the two moons; the density after each coupling layer."""
    fl = realnvp_final()
    Xtr = moons_data()[0]
    xs, ys, G = _grid()
    fig, axes = plt.subplots(2, 3, figsize=(8.4, 5.7))
    titles = ["base density", "after layer 1 (vertical)", "after layer 2 (horizontal)",
              "after layer 3 (vertical)", "after layer 4 (horizontal)", "training data"]
    for k, ax in enumerate(axes.ravel()):
        if k < 5:
            p = np.exp(fl.log_prob(G, upto=k)).reshape(len(ys), len(xs))
            ax.imshow(p, origin="lower", extent=GRID, cmap="viridis", aspect="equal", interpolation="bilinear")
        else:
            ax.scatter(Xtr[:1500, 0], Xtr[:1500, 1], s=1.5, color=common.BLUE, alpha=0.6, lw=0)
            ax.set_xlim(GRID[:2])
            ax.set_ylim(GRID[2:])
            ax.set_aspect("equal")
        ax.set_xticks([])
        ax.set_yticks([])
        ax.set_title(titles[k], fontsize=9)
        common.panel_label(ax, "abcdef"[k])
    fig.tight_layout()
    return savefig(fig, CH, "fig18-3", out_dir)


def fig_18_5(out_dir=None):
    """Figure 18.5: a residual network with five layers against a neural ODE solved adaptively."""
    z0s = np.linspace(-1.6, 1.6, 9)
    fig, axes = plt.subplots(1, 2, figsize=(9.0, 3.6), sharey=True)
    ax = axes[0]
    for z0 in z0s:
        zs = [z0]
        for t in range(5):
            zs.append(zs[-1] + f_scalar(t, zs[-1]))
        ax.plot(range(6), zs, "-o", color=common.BLUE, ms=3.5, lw=1)
    ax.set_xlabel("depth (layer $t$)")
    ax.set_ylabel("$z$")
    ax.set_title("residual network (18.21), 5 layers", fontsize=9.5)
    ax = axes[1]
    counts = []
    for z0 in z0s:
        ts, ysol, ev = dopri5(f_scalar, [z0], 0.0, 5.0, rtol=1e-3, atol=1e-5)
        fine = rk4(f_scalar, [z0], 0.0, 5.0, 500)[:, 0]
        ax.plot(np.linspace(0, 5, 501), fine, color=common.BLUE, lw=1)
        zev = np.interp(ev, np.linspace(0, 5, 501), fine)
        ax.plot(ev, zev, "o", color=common.RED, ms=2.2, alpha=0.8)
        counts.append(len(ev))
    ax.set_xlabel("time $t$")
    ax.set_title("neural ODE (18.22), adaptive Dormand-Prince", fontsize=9.5)
    ax.text(0.03, 0.40, "red: where $f$ is evaluated\n(%d to %d evaluations per input)" % (min(counts), max(counts)),
            transform=ax.transAxes, fontsize=8, va="bottom")
    fig.tight_layout()
    return savefig(fig, CH, "fig18-5", out_dir)


def fig_18_6(out_dir=None):
    """Figure 18.6: a one-dimensional continuous flow from N(0,1) to a three-mode mixture."""
    ts = np.linspace(0, 1, 101)
    zg = np.linspace(-3.6, 3.6, 361)
    P = np.array([pdf_1d(zg, t) for t in ts]).T
    us = np.linspace(0.02, 0.98, 25)
    Q = quantile_flow(us, ts)
    fig = plt.figure(figsize=(8.6, 3.9))
    gs = fig.add_gridspec(1, 3, width_ratios=[1, 5, 1], wspace=0.05)
    a0, a1, a2 = fig.add_subplot(gs[0]), fig.add_subplot(gs[1]), fig.add_subplot(gs[2])
    a1.imshow(P, origin="lower", extent=(0, 1, zg[0], zg[-1]), aspect="auto", cmap="Blues", alpha=0.85)
    for q in Q:
        a1.plot(ts, q, color=common.RED, lw=0.8)
    a1.set_yticks([])
    a1.set_xlabel("time $t$ (here $T=1$)")
    a1.set_title("flow lines $z(t)=F_t^{-1}(u)$ on the density $p(z(t))$", fontsize=9.5)
    a0.plot(pdf_1d(zg, 0.0), zg, color=common.BLUE)
    a0.fill_betweenx(zg, 0, pdf_1d(zg, 0.0), color=common.BLUE, alpha=0.2)
    a0.invert_xaxis()
    a0.set_ylim(zg[0], zg[-1])
    a0.set_xticks([])
    a0.set_ylabel("$z$")
    a0.set_title("$p(z(0))$", fontsize=9.5)
    a2.plot(pdf_1d(zg, 1.0), zg, color=common.BLUE)
    a2.fill_betweenx(zg, 0, pdf_1d(zg, 1.0), color=common.BLUE, alpha=0.2)
    a2.set_ylim(zg[0], zg[-1])
    a2.set_xticks([])
    a2.set_yticks([])
    a2.set_title("$p(z(T))$", fontsize=9.5)
    return savefig(fig, CH, "fig18-6", out_dir)


def fig_18_s1(out_dir=None):
    """Figure 18.S1: the trained real NVP: training curve, samples, inverse map, log-determinant."""
    r = train_realnvp()
    fl = realnvp_final()
    Xtr, Xte, _, _ = moons_data()
    fig, axes = plt.subplots(1, 4, figsize=(12.6, 3.2))
    ax = axes[0]
    ax.plot(r["hist"]["it"], r["hist"]["train"], color=common.BLUE, label="training set")
    ax.plot(r["hist"]["it"], r["hist"]["test"], color=common.RED, ls="--", label="test set")
    ax.set_ylim(1.5, 3.0)
    ax.set_xlabel("Adam iteration")
    ax.set_ylabel("negative log likelihood per point")
    ax.legend(fontsize=8, frameon=False)
    ax.set_title("training by maximum likelihood (18.4)", fontsize=9)
    ax = axes[1]
    rng = np.random.default_rng(4)
    x, _ = fl.forward(rng.standard_normal((1500, 2)))
    ax.scatter(Xte[:, 0], Xte[:, 1], s=1.5, color=common.GREY, alpha=0.5, lw=0, label="test data")
    ax.scatter(x[:, 0], x[:, 1], s=1.5, color=common.BLUE, lw=0, label="samples $f(z)$")
    ax.set_xlim(GRID[:2])
    ax.set_ylim(GRID[2:])
    ax.set_aspect("equal")
    ax.legend(fontsize=7, frameon=False, loc="lower left", markerscale=4)
    ax.set_title("sampling: forward map", fontsize=9)
    ax = axes[2]
    z, _ = fl.inverse(Xte)
    ax.scatter(z[:, 0], z[:, 1], s=1.5, color=common.GREEN, lw=0)
    tt = np.linspace(0, 2 * np.pi, 200)
    for rr in (1, 2, 3):
        ax.plot(rr * np.cos(tt), rr * np.sin(tt), color="k", lw=0.6, ls=":")
    ax.set_xlim(-3.6, 3.6)
    ax.set_ylim(-3.6, 3.6)
    ax.set_aspect("equal")
    ax.set_title("test data mapped back: $g(x)$", fontsize=9)
    ax = axes[3]
    xs, ys, G = _grid(121)
    _, ld = fl.inverse(G)
    im = ax.imshow(ld.reshape(len(ys), len(xs)), origin="lower", extent=GRID, cmap="RdBu_r", vmin=-4, vmax=4)
    ax.set_aspect("equal")
    fig.colorbar(im, ax=ax, fraction=0.046, pad=0.03)
    ax.set_title(r"$\ln|\det J(x)|=-\sum_k s_k$", fontsize=9)
    fig.tight_layout()
    return savefig(fig, CH, "fig18-s1", out_dir)


def fig_18_s2(out_dir=None):
    """Figure 18.S2: autoregressive flows: Jacobian patterns and sequential cost of MAF and IAF."""
    D = 8
    P = made_init(D)
    rng = np.random.default_rng(0)
    x0 = rng.standard_normal(D)
    Jm = jacobian_fd(lambda x: maf_density(P, x)[0][0], x0)
    Ji = jacobian_fd(lambda x: iaf_sample(P, x)[0][0], x0)
    # an affine coupling layer on R^8 (first 4 copied), with a random conditioner
    Wc = rng.normal(0, 0.6, (8, 4))

    def coup(x):
        s, b = np.tanh(Wc[:4] @ x[:4]), np.tanh(Wc[4:] @ x[:4])
        return np.r_[x[:4], (x[4:] - b) * np.exp(-s)]
    Jc = jacobian_fd(coup, x0)
    tim = ar_timing()
    fig, axes = plt.subplots(1, 4, figsize=(13.0, 3.2), gridspec_kw=dict(width_ratios=[1, 1, 1, 1.35]))
    for ax, J, title in zip(axes[:3], (Jm, Ji, Jc), ("MAF inverse: $\\partial z_i/\\partial x_j$",
                                                       "IAF forward: $\\partial x_i/\\partial z_j$",
                                                       "coupling layer: $\\partial z_i/\\partial x_j$")):
        A = np.abs(J)
        ax.imshow(np.where(A > 1e-9, np.log10(A + 1e-12), np.nan), cmap="viridis", vmin=-3, vmax=0.7)
        ax.set_xticks(range(D))
        ax.set_yticks(range(D))
        ax.set_xticklabels(range(1, D + 1), fontsize=7)
        ax.set_yticklabels(range(1, D + 1), fontsize=7)
        ax.set_title(title, fontsize=9)
        ax.set_xlabel("$j$")
    axes[0].set_ylabel("$i$")
    ax = axes[3]
    Ds = np.array(tim["D"])
    for key, col, ls, lab in (("maf_density", common.BLUE, "-", "MAF density (1 pass)"),
                              ("maf_sample", common.BLUE, "--", "MAF sampling ($D$ passes)"),
                              ("iaf_sample", common.RED, "-", "IAF sampling (1 pass)"),
                              ("iaf_density", common.RED, "--", "IAF density ($D$ passes)")):
        ax.loglog(Ds, 1e3 * np.array(tim[key]), ls, color=col, marker="o", ms=3, label=lab)
    ax.set_xlabel("dimension $D$")
    ax.set_ylabel("ms per batch of 256 (one CPU thread)")
    ax.legend(fontsize=7, frameon=False)
    ax.set_title("cost of the two directions", fontsize=9)
    fig.tight_layout()
    return savefig(fig, CH, "fig18-s2", out_dir)


def adjoint_setup():
    P = node_params()
    return P, np.array([0.8, -0.5]), np.array([0.3, 1.1])


def fig_18_s3(out_dir=None):
    """Figure 18.S3: the adjoint method on a two-dimensional neural ODE."""
    P, z0, y = adjoint_setup()
    out = node_adjoint_grad(P, z0, y, n=200, record=True)
    fwd = rk4(lambda t, z: node_f(P, z), z0, 0.0, 2.0, 200)
    ref = node_adjoint_grad(P, z0, y, n=4000)["dLdw"]
    ns = np.array([5, 10, 20, 40, 80, 160])
    e_adj = [np.abs(node_adjoint_grad(P, z0, y, n=n)["dLdw"] - ref).max() for n in ns]
    e_bp = [np.abs(node_backprop_grad(P, z0, y, n=n) - ref).max() for n in ns]
    e_eul = [np.abs(euler_resnet_grads(P, z0, y, n=n)[2] - ref).max() for n in ns]
    fig, axes = plt.subplots(1, 3, figsize=(12.0, 3.4))
    ax = axes[0]
    ax.plot(fwd[:, 0], fwd[:, 1], color=common.BLUE, label="forward $z(t)$")
    ax.plot(out["z"][:, 0], out["z"][:, 1], color=common.ORANGE, ls="--", lw=2, label="recomputed backwards")
    ax.plot(*z0, "o", color="k", ms=4)
    ax.plot(*y, "*", color=common.RED, ms=9, label="target $y$")
    ax.set_xlabel("$z_1$")
    ax.set_ylabel("$z_2$")
    ax.legend(fontsize=7, frameon=False)
    ax.set_title("state: forwards, then backwards", fontsize=9)
    ax = axes[1]
    ax.plot(out["t"], out["a"][:, 0], color=common.GREEN, label="$a_1(t)$")
    ax.plot(out["t"], out["a"][:, 1], color=common.PURPLE, label="$a_2(t)$")
    ax.set_xlabel("$t$ (integrated from $T=2$ down to 0)")
    ax.legend(fontsize=8, frameon=False)
    ax.set_title(r"adjoint $a(t)=\partial L/\partial z(t)$, (18.25)", fontsize=9)
    ax = axes[2]
    ax.loglog(2.0 / ns, e_adj, "o-", color=common.BLUE, label="adjoint (RK4 backwards)")
    ax.loglog(2.0 / ns, e_bp, "s--", color=common.RED, ms=4, label="backprop through RK4")
    ax.loglog(2.0 / ns, e_eul, "^-", color=common.GREY, ms=4, label="Euler residual net, exact backprop")
    hh = 2.0 / ns
    ax.loglog(hh, 0.6 * e_adj[-1] * (hh / hh[-1]) ** 4, ":", color="k", lw=0.8, label="slope 4")
    ax.loglog(hh, 0.6 * e_eul[-1] * (hh / hh[-1]), "-.", color="k", lw=0.8, label="slope 1")
    ax.set_xlabel("step size $h$")
    ax.set_ylabel(r"max error in $\nabla_w L$")
    ax.legend(fontsize=6.5, frameon=False)
    ax.set_title("gradient error against the exact ODE gradient", fontsize=9)
    fig.tight_layout()
    return savefig(fig, CH, "fig18-s3", out_dir)


def fig_18_s4(out_dir=None):
    """Figure 18.S4: Hutchinson's trace estimator, Gaussian against Rademacher probes."""
    rng = np.random.default_rng(2)
    D = 16
    A = rng.standard_normal((D, D)) / math.sqrt(D) + np.diag(rng.normal(1.0, 1.0, D))
    tr = np.trace(A)
    R = 20000
    eg = rng.standard_normal((R, D))
    er = rng.choice([-1.0, 1.0], (R, D))
    est_g = np.einsum("ri,ij,rj->r", eg, A, eg)
    est_r = np.einsum("ri,ij,rj->r", er, A, er)
    fig, axes = plt.subplots(1, 3, figsize=(12.0, 3.3))
    ax = axes[0]
    bins = np.linspace(tr - 40, tr + 40, 121)
    ax.hist(est_g, bins=bins, density=True, color=common.BLUE, alpha=0.5, label="Gaussian, var %.1f (exact %.1f)" % (est_g.var(), hutch_var(A, "gauss")))
    ax.hist(est_r, bins=bins, density=True, color=common.RED, alpha=0.5, label="Rademacher, var %.1f (exact %.1f)" % (est_r.var(), hutch_var(A, "rad")))
    ax.axvline(tr, color="k", ls="--", lw=1, label="Tr(A) = %.2f" % tr)
    ax.set_xlabel(r"single-probe estimate $\epsilon^{T}A\epsilon$")
    ax.legend(fontsize=7, frameon=False)
    ax.set_title("$D=16$: both unbiased, different spread", fontsize=9)
    ax = axes[1]
    Ms = np.array([1, 2, 4, 8, 16, 32, 64])
    for E, col, kind in ((eg, common.BLUE, "gauss"), (er, common.RED, "rad")):
        est = np.einsum("ri,ij,rj->r", E, A, E)
        v = [est[:(R // M) * M].reshape(-1, M).mean(1).var() for M in Ms]
        ax.loglog(Ms, v, "o", color=col)
        ax.loglog(Ms, hutch_var(A, kind) / Ms, "-", color=col, lw=1, label=("Gaussian" if kind == "gauss" else "Rademacher") + ": var/M")
    ax.set_xlabel("probes $M$ in (18.30)")
    ax.set_ylabel("variance of the estimate")
    ax.legend(fontsize=7, frameon=False)
    ax.set_title("variance falls like $1/M$", fontsize=9)
    ax = axes[2]
    cnf = cnf_final()
    Xte = moons_data()[1][:300]
    lp_ex, _ = cnf.logp(Xte, n=20)
    rows = []
    for kind, col in (("gauss", common.BLUE), ("rad", common.RED)):
        for M in (1, 4, 16):
            E = hutch_probes(len(Xte), M, kind, seed=21)
            lp, _ = cnf.logp(Xte, n=20, eps=E)
            rows.append((kind, M, np.std(lp - lp_ex)))
        ax.loglog([1, 4, 16], [r_[2] for r_ in rows if r_[0] == kind], "o-", color=col,
                  label=("Gaussian" if kind == "gauss" else "Rademacher"))
    ax.set_xlabel("probes $M$ per data point")
    ax.set_ylabel(r"s.d. of the error in $\ln p(x)$")
    ax.legend(fontsize=7, frameon=False)
    ax.set_title("in the trained CNF of Figure 18.S5", fontsize=9)
    fig.tight_layout()
    return savefig(fig, CH, "fig18-s4", out_dir)


def fig_18_s5(out_dir=None):
    """Figure 18.S5: a continuous normalizing flow trained by flow matching on the two moons."""
    cnf = cnf_final()
    Xtr, Xte, _, _ = moons_data()
    rng = np.random.default_rng(6)
    Z = rng.standard_normal((1200, 2))
    x, acc, traj = cnf.push(Z, n=20, keep=True)
    fig, axes = plt.subplots(1, 3, figsize=(12.0, 3.7))
    ax = axes[0]
    for k in range(0, 1200, 12):
        ax.plot(traj[:, k, 0], traj[:, k, 1], color=common.GREY, lw=0.5, alpha=0.6)
    ax.scatter(Z[:, 0], Z[:, 1], s=1.2, color=common.GREEN, lw=0, label="$z(0)$")
    ax.scatter(x[:, 0], x[:, 1], s=1.2, color=common.BLUE, lw=0, label="$z(T)$")
    ax.set_xlim(-3, 3)
    ax.set_ylim(-3, 3)
    ax.set_aspect("equal")
    ax.legend(fontsize=7, frameon=False, markerscale=5, loc="lower left")
    ax.set_title("samples: integrate (18.27) from $t=0$ to $T=1$", fontsize=9)
    ax = axes[1]
    xs, ys, G = _grid(81)
    lp, _ = cnf.logp(G, n=20)
    p = np.exp(lp).reshape(len(ys), len(xs))
    ax.imshow(p, origin="lower", extent=GRID, cmap="viridis", interpolation="bilinear")
    mass = p.sum() * (xs[1] - xs[0]) * (ys[1] - ys[0])
    ax.set_title("density by (18.28), exact trace (mass %.3f)" % mass, fontsize=9)
    ax.set_xticks([])
    ax.set_yticks([])
    ax = axes[2]
    lpe, _ = cnf.logp(Xte[:400], n=20)
    E = hutch_probes(400, 1, "gauss", seed=21)
    lph, _ = cnf.logp(Xte[:400], n=20, eps=E)
    E = hutch_probes(400, 1, "rad", seed=21)
    lpr, _ = cnf.logp(Xte[:400], n=20, eps=E)
    bins = np.linspace(-6, 6, 61)
    ax.hist(lph - lpe, bins=bins, color=common.BLUE, alpha=0.5, label="Gaussian probe, s.d. %.3f" % np.std(lph - lpe))
    ax.hist(lpr - lpe, bins=bins, color=common.RED, alpha=0.5, label="Rademacher probe, s.d. %.3f" % np.std(lpr - lpe))
    ax.axvline(0, color="k", lw=0.8)
    ax.set_xlabel(r"Hutchinson $\ln p(x)$ minus exact (400 test points, $M=1$)")
    ax.legend(fontsize=7, frameon=False)
    ax.set_title("mean errors %.3f and %.3f" % (np.mean(lph - lpe), np.mean(lpr - lpe)), fontsize=9)
    fig.tight_layout()
    return savefig(fig, CH, "fig18-s5", out_dir)


def fig_data(out_dir=None):
    """Data files for coupling-flow-demo.html and continuous-flow-demo.html (no figure)."""
    export_coupling_json()
    export_cnf_json()


FIGURES = {"18.3": fig_18_3, "18.5": fig_18_5, "18.6": fig_18_6, "18.S1": fig_18_s1, "18.S2": fig_18_s2,
           "18.S3": fig_18_s3, "18.S4": fig_18_s4, "18.S5": fig_18_s5, "data": fig_data}


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