"""Chapter 18, Gaussian processes: Python code for the figures of Murphy (2023), Probabilistic Machine
Learning: Advanced Topics, Chapter 18 (and Supplement 18).

Run `python3 ch18_gaussian_processes.py` for every figure, `--fig 18.7 18.15` for some, `--list` to list them.
Everything is written from scratch in numpy and PyTorch (double precision, CPU, single thread): kernels and
their compositions, exact GP regression by Cholesky, marginal-likelihood training, Laplace GP classification,
Poisson GP regression (HMC and Gaussian variational inference), the Nystroem, SOR, DTC, FITC and Titsias
(SGPR) approximations, hyper-parameter inference (grid, central composite design, HMC), additive kernels,
a kernel search, spectral mixture kernels, deep kernel learning, the NN-GP kernel and 2-layer and 4-layer deep
GPs fitted by Hamiltonian Monte Carlo.

Figures reproduced (book numbering): 18.2, 18.3, 18.4, 18.5, 18.6, 18.7, 18.8, 18.9, 18.10, 18.11 (stand-in
data), 18.14 (stand-in data), 18.15, 18.16, 18.17, 18.18, 18.20 (stand-in data), 18.22, 18.23, 18.24, 18.26,
18.28, 18.29, and from the supplement Figures 18.2, 18.3, 18.4 (files fig18-sup2 to fig18-sup4). Extra figures made for the "Filling the gap"
boxes: 18.S1 (random Fourier features), 18.S2 (SOR, DTC, FITC and VFE compared), 18.S3 (NN-GP kernels against
finite networks), 18.S4 (the neural tangent kernel), 18.S5 (a GP as a state space model).

Figures skipped (nothing computed, or data/compute out of reach):
 * 18.1, 18.12, 18.13, 18.19, 18.21, 18.25: hand-drawn diagrams (graphical models, kernel hierarchy, search tree,
   DKL architecture, DNA inducing points).
 * 18.27: Olivetti faces deep kernel matrices (needs the face data set and a large network).
 * Figure 18.11 uses the Finland heart-attack counts, which are not bundled: a synthetic lattice of expected
   and observed counts stands in. Figure 18.14 uses three large UCI regression sets: a synthetic regression
   problem stands in. Figure 18.20 uses the concrete-strength data: the bundled diabetes data stand in.
 * Figure 18.29 uses a longer Mauna Loa record than is bundled; the 1958-2001 record shipped with statsmodels
   is used, with a forecast of the held-out final years.
"""
import json
import os
import sys
import warnings

os.environ.setdefault("OPENBLAS_NUM_THREADS", "1")
os.environ.setdefault("OMP_NUM_THREADS", "1")
import numpy as np
import torch
from scipy import optimize, special, linalg as sla, stats

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

torch.set_num_threads(1)
torch.set_default_dtype(torch.float64)
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
WORK = os.path.join(HERE, "cache", "ch18-work")
os.makedirs(WORK, exist_ok=True)
os.makedirs(DATA_OUT, exist_ok=True)
CH = 18
JIT = 1e-8


# =========================================================================== kernels (torch)
def _t(x):
    x = x if torch.is_tensor(x) else torch.as_tensor(np.asarray(x), dtype=torch.float64)
    return x.reshape(-1, 1) if x.ndim == 1 else x


def np_(x):
    return x.detach().cpu().numpy()


def sqdist(X, Y):
    """Squared Euclidean distances between the rows of X and Y."""
    X, Y = _t(X), _t(Y)
    d = X[:, None, :] - Y[None, :, :]
    return (d * d).sum(-1)


def dist(X, Y):
    return torch.sqrt(torch.clamp(sqdist(X, Y), min=1e-30))


def k_se(X, Y, ell=1.0, var=1.0):
    """Squared exponential (18.8)."""
    return var * torch.exp(-0.5 * sqdist(X, Y) / ell ** 2)


def k_ard(X, Y, ell, var=1.0):
    """ARD kernel (18.10), diagonal Sigma."""
    X, Y = _t(X), _t(Y)
    ell = torch.as_tensor(ell, dtype=torch.float64)
    return var * torch.exp(-0.5 * sqdist(X / ell, Y / ell))


def k_matern(X, Y, nu=1.5, ell=1.0, var=1.0):
    """Matern kernels (18.14)-(18.16) for nu = 1/2, 3/2, 5/2."""
    r = dist(X, Y) / ell
    if nu == 0.5:
        return var * torch.exp(-r)
    if nu == 1.5:
        s = np.sqrt(3.0) * r
        return var * (1 + s) * torch.exp(-s)
    if nu == 2.5:
        s = np.sqrt(5.0) * r
        return var * (1 + s + s * s / 3.0) * torch.exp(-s)
    raise ValueError("nu must be 0.5, 1.5 or 2.5")


def k_periodic(X, Y, ell=1.0, period=1.0, var=1.0):
    """Periodic (exp-sine-squared) kernel (18.18)."""
    r = dist(X, Y)
    return var * torch.exp(-2.0 * torch.sin(np.pi * r / period) ** 2 / ell ** 2)


def k_cosine(X, Y, period=1.0, var=1.0):
    """Cosine kernel (18.19)."""
    return var * torch.cos(2 * np.pi * dist(X, Y) / period)


def k_rq(X, Y, ell=1.0, alpha=1.0, var=1.0):
    """Rational quadratic kernel (18.20)."""
    return var * (1 + sqdist(X, Y) / (2 * alpha * ell ** 2)) ** (-alpha)


def k_const(X, Y, var=1.0):
    return var * torch.ones(len(_t(X)), len(_t(Y)))


def k_lin(X, Y, var=1.0, c=0.0):
    X, Y = _t(X), _t(Y)
    return var * (X - c) @ (Y - c).T


def k_poly(X, Y, degree=2, scale=1.0, c=0.0):
    """Polynomial kernels (18.23), (18.25): (scale x^T x' + c)^degree."""
    X, Y = _t(X), _t(Y)
    return (scale * X @ Y.T + c) ** degree


def k_white(X, Y, var=1.0):
    """White noise: var * 1{x = x'}."""
    return var * (sqdist(X, Y) < 1e-24).to(torch.float64)


def k_sm(X, Y, w, mu, v):
    """Spectral mixture kernel (18.172) in 1d: sum_i w_i cos(2 pi mu_i r) exp(-2 pi^2 v_i r^2)."""
    r = _t(X) - _t(Y).T
    out = 0.0
    for wi, mi, vi in zip(w, mu, v):
        out = out + wi * torch.cos(2 * np.pi * mi * r) * torch.exp(-2 * np.pi ** 2 * vi * r * r)
    return out


def k_gibbs(X, Y, ell_fn, sig_fn=None):
    """Gibbs kernel (18.27), 1d."""
    X, Y = _t(X), _t(Y)
    lx, ly = ell_fn(X), ell_fn(Y).T
    s2 = lx ** 2 + ly ** 2
    out = torch.sqrt(2 * lx * ly / s2) * torch.exp(-(X - Y.T) ** 2 / s2)
    if sig_fn is not None:
        out = sig_fn(X) * sig_fn(Y).T * out
    return out


def kernel_matrix(k, X, Y=None, noise=0.0):
    K = k(X, X if Y is None else Y)
    if Y is None and noise:
        K = K + noise * torch.eye(len(K))
    return K


# =========================================================================== GP regression
def chol_safe(K, jitter=JIT):
    n = len(K)
    for j in range(8):
        try:
            return torch.linalg.cholesky(K + (jitter * 10 ** j) * torch.eye(n))
        except Exception:
            continue
    raise RuntimeError("Cholesky failed")


def gp_fit(K, y, noise_var):
    """Cholesky of K + noise I and alpha = (K + noise I)^{-1} y (eq. 18.75)."""
    L = chol_safe(K + noise_var * torch.eye(len(K)), 0.0 if noise_var > 0 else JIT)
    alpha = torch.cholesky_solve(_t(y).reshape(-1, 1), L)[:, 0]
    return L, alpha


def gp_predict(kfun, X, y, Xs, noise_var, full_cov=False):
    """Posterior mean and (co)variance of f(Xs) (18.52)-(18.53), via Cholesky (18.75)-(18.76); zero prior mean."""
    X, Xs = _t(X), _t(Xs)
    y = _t(y)[:, 0]
    L, alpha = gp_fit(kfun(X, X), y, noise_var)
    Ks = kfun(X, Xs)
    mu = Ks.T @ alpha
    V = torch.linalg.solve_triangular(L, Ks, upper=False)
    if full_cov:
        return mu, kfun(Xs, Xs) - V.T @ V
    return mu, torch.clamp(_diag_k(kfun, Xs) - (V * V).sum(0), min=0.0)


def _diag_k(kfun, Xs):
    """Diagonal of kfun(Xs, Xs) without forming big matrices where cheap."""
    return torch.diagonal(kfun(Xs, Xs))


def log_marglik(K, y, noise_var):
    """log N(y | 0, K + noise I) via (18.77)."""
    y = _t(y)[:, 0]
    L = chol_safe(K + noise_var * torch.eye(len(K)), 0.0)
    a = torch.cholesky_solve(y.reshape(-1, 1), L)[:, 0]
    return -0.5 * y @ a - torch.log(torch.diagonal(L)).sum() - 0.5 * len(y) * np.log(2 * np.pi)


def sample_prior(K, n, rng, jitter=1e-6):
    L = np.linalg.cholesky(np_(K) + jitter * np.eye(len(K)))
    return L @ rng.standard_normal((len(K), n))


def fit_theta(nll_fn, theta0, restarts=None, rng=None, bounds=None, maxiter=300):
    """Minimise nll_fn(theta_tensor) -> scalar tensor with L-BFGS-B and torch gradients.
    restarts: list of extra start vectors. Returns (best_theta, best_value, all_results)."""
    starts = [np.asarray(theta0, float)] + [np.asarray(s, float) for s in (restarts or [])]
    res = []
    for s in starts:
        def fun(th):
            t = torch.tensor(th, dtype=torch.float64, requires_grad=True)
            try:
                v = nll_fn(t)
                v.backward()
                g = t.grad.numpy().copy()
                if not np.all(np.isfinite(g)) or not np.isfinite(v.item()):
                    return 1e10, np.zeros_like(g)
                return v.item(), g
            except Exception:
                return 1e10, np.zeros_like(th)
        try:
            r = optimize.minimize(fun, s, jac=True, method="L-BFGS-B", bounds=bounds, options={"maxiter": maxiter})
            res.append((r.fun, r.x))
        except Exception:
            continue
    res.sort(key=lambda z: z[0])
    return res[0][1], res[0][0], res


def band(ax, x, mu, sd, color=BLUE, k=2.0, alpha=0.2):
    ax.fill_between(x, mu - k * sd, mu + k * sd, color=color, alpha=alpha, lw=0)


def _se_data(rng, n, ell=1.0, sf=1.0, sn=0.1, lo=-5, hi=5, x=None):
    x = rng.uniform(lo, hi, n) if x is None else x
    K = np_(k_se(x, x, ell, sf ** 2)) + 1e-8 * np.eye(len(x))
    f = np.linalg.cholesky(K) @ rng.standard_normal(len(x))
    return x, f + sn * rng.standard_normal(len(x)), f


# =========================================================================== Figures 18.2 to 18.8
def fig_18_2(out=None):
    """Function samples from a GP with an ARD kernel (2d)."""
    g = np.linspace(-2.5, 2.5, 24)
    X = np.array([[a, b] for a in g for b in g])
    rng = np.random.default_rng(2)
    z = rng.standard_normal(len(X))
    fig, axes = plt.subplots(1, 2, figsize=(7.2, 3.2))
    for ax, ell, lab in zip(axes, [(1, 1), (1, 5)], "ab"):
        K = np_(k_ard(X, X, ell)) + 1e-6 * np.eye(len(X))
        f = (np.linalg.cholesky(K) @ z).reshape(24, 24)
        im = ax.imshow(f.T, origin="lower", extent=[-2.5, 2.5, -2.5, 2.5], cmap="RdBu_r", vmin=-2.2, vmax=2.2)
        ax.set_xlabel("input $x_1$")
        ax.set_ylabel("input $x_2$")
        ax.set_title(r"$\ell_1=%g,\ \ell_2=%g$" % ell)
        panel_label(ax, lab, "lower left")
    fig.colorbar(im, ax=axes, shrink=0.8, label="output $y$")
    return savefig(fig, CH, "fig18-2", out)


KERNEL_ZOO = [
    ("Matern12", lambda X, Y: k_matern(X, Y, 0.5, 2.0)),
    ("Matern32", lambda X, Y: k_matern(X, Y, 1.5, 2.0)),
    ("Matern52", lambda X, Y: k_matern(X, Y, 2.5, 2.0)),
    ("Periodic", lambda X, Y: k_periodic(X, Y, 1.0, 5.0)),
    ("Cosine", lambda X, Y: k_cosine(X, Y, 5.0)),
    ("RBF", lambda X, Y: k_se(X, Y, 2.0)),
    ("Rational quadratic", lambda X, Y: k_rq(X, Y, 2.0, 1.0)),
    ("Constant", lambda X, Y: k_const(X, Y, 1.0)),
    ("Linear", lambda X, Y: k_lin(X, Y, 0.05)),
    ("Quadratic", lambda X, Y: k_poly(X, Y, 2, 0.15, 0.0)),
    ("Polynomial", lambda X, Y: k_poly(X, Y, 3, 0.05, 1.0)),
    ("White noise", lambda X, Y: k_white(X, Y, 1.0)),
]
_ANCHOR = {"Linear": 1.0, "Quadratic": 1.0, "Polynomial": 1.0}


def fig_18_3(out=None):
    """GP kernels evaluated at k(x, 0) (k(x, 1) for the three non-stationary ones)."""
    x = np.linspace(-10, 10, 401)
    fig, axes = plt.subplots(4, 3, figsize=(7.4, 7.4))
    for i, (ax, (name, k)) in enumerate(zip(axes.ravel(), KERNEL_ZOO)):
        a = _ANCHOR.get(name, 0.0)
        v = np_(k(x, np.array([a])))[:, 0]
        ax.plot(x, v, color=BLUE)
        ax.set_title("(%s) %s  $k(x,%.1f)$" % ("abcdefghijkl"[i], name, a), fontsize=9)
        ax.set_xlim(-10, 10)
    fig.tight_layout()
    return savefig(fig, CH, "fig18-3", out)


def fig_18_4(out=None):
    """GP samples drawn using different kernels."""
    x = np.linspace(-10, 10, 201)
    rng = np.random.default_rng(4)
    fig, axes = plt.subplots(4, 3, figsize=(7.4, 7.4))
    for i, (ax, (name, k)) in enumerate(zip(axes.ravel(), KERNEL_ZOO)):
        K = np_(k(x, x))
        w, V = np.linalg.eigh(K)
        S = (V * np.sqrt(np.maximum(w, 0))) @ rng.standard_normal((len(x), 3))
        for j in range(3):
            ax.plot(x, S[:, j], lw=1.2)
        ax.set_title("(%s) %s" % ("abcdefghijkl"[i], name), fontsize=9)
        ax.set_xlim(-10, 10)
    fig.tight_layout()
    return savefig(fig, CH, "fig18-4", out)


def _kfun_comb():
    lin = lambda X, Y: k_lin(X, Y, 0.1)
    se = lambda X, Y: k_se(X, Y, 3.0)
    per = lambda X, Y: k_periodic(X, Y, 1.0, 4.0)
    return lin, se, per


def _kernel_panels(specs, name, out, seed):
    x = np.linspace(-10, 10, 301)
    rng = np.random.default_rng(seed)
    fig, axes = plt.subplots(2, 4, figsize=(8.4, 4.2))
    for j, (title, k, sub) in enumerate(specs):
        v = np_(k(x, np.array([1.0])))[:, 0]
        axes[0, j].plot(x, v, color=BLUE)
        axes[0, j].set_title("%s\n%s" % (title, sub), fontsize=8.5)
        K = np_(k(x, x)) + 1e-6 * np.eye(len(x))
        w, V = np.linalg.eigh(K)
        S = (V * np.sqrt(np.maximum(w, 0))) @ rng.standard_normal((len(x), 3))
        for i in range(3):
            axes[1, j].plot(x, S[:, i], lw=1.1)
        axes[0, j].set_xlabel("$x$ (with $x'=1$)", fontsize=8)
        panel_label(axes[1, j], "abcd"[j], "upper left")
    fig.tight_layout()
    return savefig(fig, CH, name, out)


def fig_18_5(out=None):
    """Examples of 1d structures obtained by multiplying elementary kernels."""
    lin, se, per = _kfun_comb()
    specs = [("Lin x Lin", lambda X, Y: lin(X, Y) * lin(X, Y), "quadratic functions"),
             ("SE x Per", lambda X, Y: se(X, Y) * per(X, Y), "locally periodic"),
             ("Lin x SE", lambda X, Y: lin(X, Y) * se(X, Y), "increasing variation"),
             ("Lin x Per", lambda X, Y: lin(X, Y) * per(X, Y), "growing amplitude")]
    return _kernel_panels(specs, "fig18-5", out, 5)


def fig_18_6(out=None):
    """Examples of 1d structures obtained by summing elementary kernels."""
    lin, se, per = _kfun_comb()
    specs = [("Lin + Per", lambda X, Y: lin(X, Y) + per(X, Y), "periodic plus trend"),
             ("SE + Per", lambda X, Y: se(X, Y) + per(X, Y), "periodic plus smooth"),
             ("SE + Lin", lambda X, Y: se(X, Y) + lin(X, Y), "linear plus variation"),
             ("SE(long) + SE(short)", lambda X, Y: k_se(X, Y, 6.0) + k_se(X, Y, 0.6, 0.3), "slow and fast variation")]
    return _kernel_panels(specs, "fig18-6", out, 6)


def fig_18_7(out=None):
    """Prior samples, noise-free posterior samples and noisy posterior samples (SE kernel)."""
    rng = np.random.default_rng(7)
    xs = np.linspace(-5, 5, 200)
    xt = np.array([-4.0, -3.0, -1.0, 0.0, 2.0])
    k = lambda X, Y: k_se(X, Y, 1.0)
    Ks = np_(k(xs, xs))
    f_true = np.sin(xt) + 0.2 * xt * 0  # arbitrary smooth truth: values at the 5 inputs
    y_free = np.array([-0.3, 0.8, 0.5, -1.0, 0.7])
    fig, axes = plt.subplots(1, 3, figsize=(8.6, 2.7), sharey=True)
    # (a) prior
    S = sample_prior(torch.tensor(Ks), 3, rng, 1e-6)
    for i in range(3):
        axes[0].plot(xs, S[:, i], lw=1.2)
    band(axes[0], xs, 0 * xs, np.ones_like(xs), GREY, 2, 0.2)
    # (b) noise-free
    mu, C = gp_predict(k, xt, y_free, xs, 1e-10, full_cov=True)
    S = np_(mu)[:, None] + sample_prior(C, 3, rng, 1e-6)
    for i in range(3):
        axes[1].plot(xs, S[:, i], lw=1.2)
    band(axes[1], xs, np_(mu), np.sqrt(np.maximum(np.diag(np_(C)), 0)), GREY)
    axes[1].plot(xt, y_free, "o", color=RED, ms=5)
    # (c) noisy
    yn = y_free + 0.3 * rng.standard_normal(5)
    mu, C = gp_predict(k, xt, yn, xs, 0.3 ** 2, full_cov=True)
    S = np_(mu)[:, None] + sample_prior(C, 3, rng, 1e-6)
    for i in range(3):
        axes[2].plot(xs, S[:, i], lw=1.2)
    band(axes[2], xs, np_(mu), np.sqrt(np.maximum(np.diag(np_(C)), 0)), GREY)
    axes[2].plot(xt, yn, "o", color=RED, ms=5)
    for ax, lab in zip(axes, "abc"):
        ax.set_xlabel("$x$")
        panel_label(ax, lab, "lower left")
    axes[0].set_ylabel("$f$")
    fig.tight_layout()
    return savefig(fig, CH, "fig18-7", out)


def _per_white_nll(theta, X, y):
    """-log marginal likelihood of the periodic + white kernel, theta = log (ell, p, sigma_y^2)."""
    ell, p, s2 = torch.exp(theta)
    K = k_periodic(X, X, ell, p)
    return -log_marglik(K, y, s2)


def krr_fit_predict(Xtr, ytr, Xte, ell, p, lam):
    """Kernel ridge regression (18.98): f(x) = k(x)^T (K + lam I)^{-1} y."""
    K = k_periodic(Xtr, Xtr, ell, p)
    a = torch.linalg.solve(K + lam * torch.eye(len(K)), _t(ytr))
    return (k_periodic(Xte, Xtr, ell, p) @ a)[:, 0]


def krr_cv(x, y, grid, folds=5, seed=0):
    """Grid search with k-fold cross validation for (ell, p, lam)."""
    n = len(x)
    idx = np.random.default_rng(seed).permutation(n)
    parts = np.array_split(idx, folds)
    best, bestp = np.inf, None
    for ell in grid[0]:
        for p in grid[1]:
            for lam in grid[2]:
                err = 0.0
                for f in range(folds):
                    te = parts[f]
                    tr = np.concatenate([parts[g] for g in range(folds) if g != f])
                    pred = np_(krr_fit_predict(x[tr], y[tr], x[te], ell, p, lam))
                    err += ((pred - y[te]) ** 2).sum()
                if err < best:
                    best, bestp = err, (ell, p, lam)
    return bestp, best


def fig_18_8(out=None):
    """Kernel ridge regression compared to GP regression with the same (periodic + white) kernel."""
    rng = np.random.default_rng(8)
    x = np.sort(rng.uniform(0, 15, 60))
    truth = lambda t: 3.0 * np.sin(2 * np.pi * t / 6.5) + 0.8 * np.cos(2 * np.pi * t / 6.5)
    y = truth(x) + 0.7 * rng.standard_normal(60)
    xs = np.linspace(0, 20, 300)
    th0 = np.log([1.0, 6.0, 0.5])
    th, v, _ = fit_theta(lambda t: _per_white_nll(t, x, y), th0, restarts=[np.log([2.0, 6.5, 0.3]), np.log([0.7, 7.0, 1.0])])
    ell, p, s2 = np.exp(th)
    mu, var = gp_predict(lambda A, B: k_periodic(A, B, ell, p), x, y, xs, s2)
    grid = (np.array([0.5, 1.0, 2.0, 4.0]), np.array([5.5, 6.0, 6.5, 7.0, 7.5]), np.array([0.05, 0.2, 0.5, 1.0, 2.0]))
    (le, pe, lam), _ = krr_cv(x, y, grid)
    kr = np_(krr_fit_predict(x, y, xs, le, pe, lam))
    fig, ax = plt.subplots(figsize=(6.2, 3.3))
    ax.plot(x, y, "ko", ms=3.5, label="data")
    ax.plot(xs, truth(xs), color=GREY, lw=1.4, label="true")
    ax.plot(xs, kr, color=ORANGE, lw=1.6, label="KRR")
    ax.plot(xs, np_(mu), color=BLUE, lw=1.6, ls="--", label="GPR")
    ax.set_xlabel("data")
    ax.set_ylabel("target")
    ax.legend(ncol=4, fontsize=8, loc="upper center")
    ax.set_ylim(-5.5, 6)
    print("   GPR (ell, p, s2) = %.2f %.2f %.3f; KRR (ell, p, lam) = %.2f %.2f %.2f" % (ell, p, s2, le, pe, lam))
    return savefig(fig, CH, "fig18-8", out)


# =========================================================================== generic tools: HMC, Laplace, sparse GPs
def hmc(logp_grad, x0, n_samples, n_warmup, rng, n_leap=12, eps0=0.1, target=0.8, mass=None):
    """Hamiltonian Monte Carlo with leapfrog steps and a Robbins-Monro step-size adaptation during warm-up.
    logp_grad(x) -> (log density, gradient). Returns (samples, acceptance rate, final step size)."""
    x = np.array(x0, float)
    lp, g = logp_grad(x)
    eps = eps0
    m = np.ones_like(x) if mass is None else mass
    out = []
    acc_tot = 0
    for it in range(n_warmup + n_samples):
        p = rng.standard_normal(x.shape) * np.sqrt(m)
        xn, pn = x.copy(), p.copy()
        lpn, gn = lp, g
        pn = pn + 0.5 * eps * gn
        ok = True
        for s in range(n_leap):
            xn = xn + eps * pn / m
            lpn, gn = logp_grad(xn)
            if not np.isfinite(lpn):
                ok = False
                break
            pn = pn + (eps if s < n_leap - 1 else 0.5 * eps) * gn
        if ok:
            dH = (lpn - 0.5 * (pn ** 2 / m).sum()) - (lp - 0.5 * (p ** 2 / m).sum())
            a = float(np.exp(min(0.0, dH)))
        else:
            a = 0.0
        if rng.uniform() < a:
            x, lp, g = xn, lpn, gn
        if it < n_warmup:
            eps *= np.exp(0.05 * (a - target) / max(target, 1e-3) * 4)
            eps = float(np.clip(eps, 1e-4, 2.0))
        else:
            acc_tot += a
            out.append(x.copy())
    return np.array(out), acc_tot / max(n_samples, 1), eps


def sigmoid_(a):
    return 0.5 * (1.0 + np.tanh(0.5 * a))


def laplace_gp(K, loglik_gh, f0=None, iters=60, tol=1e-9):
    """Laplace approximation for a GP prior with a factorised likelihood (Rasmussen and Williams, Alg. 3.1).
    loglik_gh(f) -> (log p(y|f) summed, gradient g, W = -second derivative, diagonal). Newton iterations on
    Psi(f) = log p(y|f) - f^T K^{-1} f / 2 in the numerically stable B = I + W^{1/2} K W^{1/2} form (18.102)-(18.104).
    Returns dict with fhat, W, L (chol of B), a = K^{-1} fhat, and the Laplace log marginal likelihood."""
    n = len(K)
    f = np.zeros(n) if f0 is None else f0.copy()
    psi_old = -np.inf
    for it in range(iters):
        ll, g, W = loglik_gh(f)
        sW = np.sqrt(W)
        B = np.eye(n) + sW[:, None] * K * sW[None, :]
        L = np.linalg.cholesky(B)
        b = W * f + g
        t = sla.solve_triangular(L, sW * (K @ b), lower=True)
        a = b - sW * sla.solve_triangular(L.T, t, lower=False)
        f_new = K @ a
        f = f_new
        ll, g, W = loglik_gh(f)
        psi = ll - 0.5 * a @ f
        if abs(psi - psi_old) < tol:
            break
        psi_old = psi
    ll, g, W = loglik_gh(f)
    sW = np.sqrt(W)
    B = np.eye(n) + sW[:, None] * K * sW[None, :]
    L = np.linalg.cholesky(B)
    b = W * f + g
    t = sla.solve_triangular(L, sW * (K @ b), lower=True)
    a = b - sW * sla.solve_triangular(L.T, t, lower=False)
    f = K @ a
    ll, g, W = loglik_gh(f)
    logZ = -0.5 * a @ f + ll - np.log(np.diag(L)).sum()
    return dict(f=f, W=W, L=L, a=a, g=g, logZ=logZ)


def logistic_gh(y01):
    """Table 18.2, logistic: log p = log sigma(y f) with y in {-1,+1}; gradient t - pi; W = pi (1 - pi)."""
    def fn(f):
        pi = sigmoid_(f)
        ll = -np.logaddexp(0, -(2 * y01 - 1) * f).sum()
        return ll, y01 - pi, pi * (1 - pi)
    return fn


def laplace_predict(res, K, Kxs, kss_diag):
    """Latent predictive mean and variance of the Laplace approximation (Rasmussen and Williams Alg. 3.2)."""
    mu = Kxs.T @ res["g"]
    sW = np.sqrt(res["W"])
    v = sla.solve_triangular(res["L"], sW[:, None] * Kxs, lower=True)
    return mu, kss_diag - (v * v).sum(0)


def probit_approx(mu, var):
    """sigma(kappa(v) mu) with kappa^2 = 1 / (1 + pi v / 8)  (the approximation below (18.105))."""
    return sigmoid_(mu / np.sqrt(1 + np.pi * var / 8))


def sparse_gp(kfun, X, y, Z, Xs, s2, method="vfe", full=False):
    """The inducing-point approximations of Section 18.5.3 and the Titsias bound of Section 18.5.4.1 in numpy.

    method: 'sor', 'dtc', 'fitc' or 'vfe'. Returns predictive mean and latent variance at Xs and the
    training objective (the log marginal likelihood of the approximate model, minus the trace term for 'vfe').
    kfun(A, B) returns a numpy matrix. All methods cost O(N M^2 + M^3)."""
    Kzz = kfun(Z, Z) + 1e-8 * np.eye(len(Z))
    Lz = np.linalg.cholesky(Kzz)
    A = sla.solve_triangular(Lz, kfun(Z, X), lower=True)            # M x N, Q_XX = A^T A
    kxx = np.diag(kfun(X, X))
    qxx = (A * A).sum(0)
    if method == "fitc":
        Lam = np.maximum(kxx - qxx, 0) + s2
    else:
        Lam = np.full(len(X), s2)
    B = np.eye(len(Z)) + (A / Lam) @ A.T
    LB = np.linalg.cholesky(B)
    Ay = A @ (y / Lam)
    c = sla.cho_solve((LB, True), Ay)
    As = sla.solve_triangular(Lz, kfun(Z, Xs), lower=True)
    mu = As.T @ c
    W = sla.solve_triangular(LB, As, lower=True)
    kss = np.diag(kfun(Xs, Xs))
    qss = (As * As).sum(0)
    if method == "sor":
        var = (W * W).sum(0)
    else:
        var = kss - qss + (W * W).sum(0)
    # training objective: log N(y | 0, Q + diag(Lam)) (minus trace term for vfe)
    logdet = 2 * np.log(np.diag(LB)).sum() + np.log(Lam).sum()
    quad = (y * y / Lam).sum() - Ay @ c
    obj = -0.5 * (quad + logdet + len(X) * np.log(2 * np.pi))
    if method == "vfe":
        obj -= 0.5 / s2 * (kxx - qxx).sum()
    out = dict(mu=mu, var=var, obj=obj)
    if full:
        out.update(A=A, Lz=Lz, B=B, LB=LB, c=c)
    return out


def np_kernel(name, **kw):
    """numpy-returning kernel callable from the torch kernels above."""
    f = dict(se=k_se, matern=k_matern, periodic=k_periodic, rq=k_rq)[name]
    return lambda A, B: np_(f(A, B, **kw))


# =========================================================================== Figures 18.9 to 18.11
def fig_18_9(out=None):
    """Posterior predictive probability of a GP classifier with an SE kernel: manual and learned hyper-parameters."""
    rng = np.random.default_rng(9)
    X = rng.standard_normal((120, 2)) * 1.6
    y = ((X[:, 0] > 0) ^ (X[:, 1] > 0)).astype(float)
    flip = rng.uniform(size=len(y)) < 0.04
    y = np.where(flip, 1 - y, y)

    def kmat(ell, var, A, B):
        return np_(k_se(A, B, ell, var))

    def neg_logZ(th):
        ell, var = np.exp(th)
        K = kmat(ell, var, X, X) + 1e-8 * np.eye(len(X))
        try:
            return -laplace_gp(K, logistic_gh(y))["logZ"]
        except Exception:
            return 1e10

    r = optimize.minimize(neg_logZ, np.log([0.5, 10.0]), method="Nelder-Mead", options={"xatol": 1e-3, "fatol": 1e-4})
    learned = np.exp(r.x)
    g = np.linspace(-4.5, 4.5, 60)
    G = np.array([[a, b] for b in g for a in g])
    fig, axes = plt.subplots(1, 2, figsize=(7.4, 3.5))
    for ax, (ell, var), lab in zip(axes, [(0.5, 10.0), tuple(learned)], "ab"):
        K = kmat(ell, var, X, X) + 1e-8 * np.eye(len(X))
        res = laplace_gp(K, logistic_gh(y))
        mu, v = laplace_predict(res, K, kmat(ell, var, X, G), np.full(len(G), var))
        P = probit_approx(mu, v).reshape(60, 60)
        cs = ax.contourf(g, g, P, levels=np.linspace(0, 1, 11), cmap="RdBu_r", alpha=0.85)
        ax.contour(g, g, P, levels=[0.5], colors="k", linewidths=1.2)
        ax.scatter(X[y == 1, 0], X[y == 1, 1], c=RED, s=14, edgecolor="white", lw=0.4)
        ax.scatter(X[y == 0, 0], X[y == 0, 1], c=BLUE, s=14, edgecolor="white", lw=0.4)
        ax.set_title(r"$%.2f^2\cdot$RBF($\ell=%.2f$)" % (np.sqrt(var), ell), fontsize=10)
        panel_label(ax, lab, "upper left")
        ax.set_xlabel("$x_1$")
        ax.set_xlim(-4.5, 4.5)
        ax.set_ylim(-4.5, 4.5)
    axes[0].set_ylabel("$x_2$")
    fig.colorbar(cs, ax=axes, shrink=0.8, label=r"$p(y=1\mid x)$")
    print("   learned (ell, variance) = %.2f, %.2f; Laplace log evidence manual %.2f, learned %.2f" % (
        learned[0], learned[1], laplace_gp(kmat(0.5, 10., X, X) + 1e-8 * np.eye(len(X)), logistic_gh(y))["logZ"], -r.fun))
    return savefig(fig, CH, "fig18-9", out)


def poisson_data(seed=10, n=100):
    rng = np.random.default_rng(seed)
    x = np.linspace(-3, 3, n)
    rate = np.exp(1.2 + 0.9 * np.sin(1.6 * x) - 0.25 * x)
    y = rng.poisson(rate)
    return x, y, rate


def fig_18_10(out=None):
    """GP Poisson regression (Cox process): MCMC (HMC) and stochastic variational inference."""
    x, y, rate = poisson_data()
    n = len(x)
    K = np_(k_matern(x, x, 2.5, 1.0, 1.0)) + 2.0 + 1e-6 * np.eye(n)       # Matern 5/2 plus a constant (prior mean level)
    L = np.linalg.cholesky(K)

    def lpg(z):
        f = L @ z
        e = np.exp(np.clip(f, -30, 8))
        return (y * f - e).sum() - 0.5 * z @ z, L.T @ (y - e) - z

    rng = np.random.default_rng(10)
    Z, acc, eps = hmc(lpg, np.zeros(n), 1500, 700, rng, n_leap=15, eps0=0.05)
    F = Z @ L.T
    R = np.exp(F)
    # stochastic variational inference with q(f) = N(m, S)
    Kt = torch.tensor(K)
    Kinv = torch.linalg.inv(Kt)
    logdetK = torch.logdet(Kt)
    yt = torch.tensor(y.astype(float))
    m = torch.tensor(np.log(y + 0.5), requires_grad=True)
    P = torch.tensor(-2.5 * np.eye(n), requires_grad=True)       # softplus(-2.5) = 0.08 initial standard deviation
    opt = torch.optim.Adam([m, P], lr=0.03)
    sched = torch.optim.lr_scheduler.StepLR(opt, 1500, 0.3)

    def parts():
        Lq = torch.tril(P, -1) + torch.diag(torch.nn.functional.softplus(torch.diagonal(P)))
        S = Lq @ Lq.T
        return Lq, S

    for it in range(4500):
        opt.zero_grad()
        Lq, S = parts()
        sd2 = torch.diagonal(S)
        ell = (yt * m - torch.exp(m + 0.5 * sd2)).sum()
        kl = 0.5 * ((Kinv * S).sum() + m @ Kinv @ m - n + logdetK - 2 * torch.log(torch.diagonal(Lq)).sum())
        loss = -(ell - kl)
        loss.backward()
        opt.step()
        sched.step()
    Lq, S = parts()
    mq, vq = np_(m), np.diag(np_(S))
    fig, axes = plt.subplots(1, 3, figsize=(9.2, 2.8), sharey=True)
    axes[0].plot(x, y, "k.", ms=4, label="data")
    axes[0].plot(x, rate, color=ORANGE, lw=1.6, label="true rate")
    axes[0].legend(fontsize=8)
    qs = np.percentile(R, [2.5, 16, 84, 97.5], axis=0)
    axes[1].plot(x, y, "k.", ms=4)
    axes[1].plot(x, rate, color=ORANGE, lw=1.4)
    axes[1].plot(x, R.mean(0), color=BLUE, lw=1.6, label="MCMC mean rate")
    axes[1].fill_between(x, qs[0], qs[3], color=BLUE, alpha=0.18, lw=0)
    axes[1].fill_between(x, qs[1], qs[2], color=BLUE, alpha=0.28, lw=0)
    axes[1].legend(fontsize=8, loc="upper left")
    lo2, hi2 = np.exp(mq - 1.96 * np.sqrt(vq)), np.exp(mq + 1.96 * np.sqrt(vq))
    axes[2].plot(x, y, "k.", ms=4)
    axes[2].plot(x, rate, color=ORANGE, lw=1.4)
    axes[2].plot(x, np.exp(mq), color=GREEN, lw=1.6, label="VI median rate")
    axes[2].fill_between(x, lo2, hi2, color=GREEN, alpha=0.22, lw=0)
    axes[2].legend(fontsize=8, loc="upper left")
    for ax, lab in zip(axes, "abc"):
        ax.set_xlabel("$x$")
        panel_label(ax, lab, "upper right")
    axes[0].set_ylabel("counts")
    fig.tight_layout()
    print("   HMC acceptance %.2f, step %.3f; mean abs diff (HMC mean log-rate vs VI mean) %.3f" % (acc, eps, np.abs(F.mean(0) - mq).mean()))
    return savefig(fig, CH, "fig18-10", out)


def lattice_data(seed=11, nx=20, ny=30):
    rng = np.random.default_rng(seed)
    gx, gy = np.meshgrid(np.arange(nx), np.arange(ny), indexing="ij")
    P = np.stack([gx.ravel(), gy.ravel()], 1).astype(float)
    Kt = np_(k_matern(P, P, 1.5, 7.0, 0.5 ** 2)) + 1e-8 * np.eye(len(P))
    f = np.linalg.cholesky(Kt) @ rng.standard_normal(len(P)) + 0.9 * (P[:, 0] / nx - 0.5)
    e = 60.0 * np.exp(-P[:, 1] / 28.0) * (0.6 + 0.8 * rng.uniform(size=len(P)))      # expected counts: fewer people to the north
    y = rng.poisson(e * np.exp(f))
    return P, e, y, f


def poisson_offset_gh(y, e):
    def fn(f):
        mu = e * np.exp(np.clip(f, -30, 15))
        return (y * f - mu).sum(), y - mu, mu
    return fn


def fig_18_11(out=None):
    """Relative risk on a lattice: Poisson GP with Matern 3/2 kernel and Laplace approximation (synthetic stand-in)."""
    P, e, y, f_true = lattice_data()
    n = len(P)
    D = np_(dist(P, P))

    def Kmat(ell, sig):
        s = np.sqrt(3.0) * D / ell
        return sig ** 2 * (1 + s) * np.exp(-s) + 1e-8 * np.eye(n)

    best = None
    for ell in [3.0, 5.0, 7.0, 10.0]:
        for sig in [0.3, 0.5, 0.8]:
            try:
                r = laplace_gp(Kmat(ell, sig), poisson_offset_gh(y, e))
            except Exception:
                continue
            if best is None or r["logZ"] > best[0]:
                best = (r["logZ"], ell, sig, r)
    lz, ell, sig, res = best
    K = Kmat(ell, sig)
    mu = res["f"]
    sW = np.sqrt(res["W"])
    V = sla.solve_triangular(res["L"], sW[:, None] * K, lower=True)
    v = np.diag(K) - (V * V).sum(0)
    rr = np.exp(mu + 0.5 * v)
    fig, axes = plt.subplots(1, 2, figsize=(7.6, 3.5))
    for ax, field, ttl, lab in zip(axes, [rr, v], ["posterior mean relative risk", "posterior variance of log relative risk"], "ab"):
        im = ax.imshow(field.reshape(20, 30).T, origin="lower", cmap="viridis", aspect="equal")
        ax.set_title(ttl, fontsize=9)
        fig.colorbar(im, ax=ax, shrink=0.75)
        panel_label(ax, lab, "upper left")
    fig.tight_layout()
    print("   lattice: best (ell, sigma) = %.1f, %.1f; corr(posterior mean log RR, truth) = %.3f" % (ell, sig, np.corrcoef(mu, f_true)[0, 1]))
    return savefig(fig, CH, "fig18-11", out)


# =========================================================================== Figures 18.14 to 18.18, 18.20
def matern_feature_function(rng, d, ell, n_feat=1500, nu=1.5):
    """A fixed random function with (approximately) a Matern(nu) covariance, from random Fourier features with a
    Student-t spectral density (Section 18.2.1.6). Returns f(X) with unit variance."""
    z = rng.standard_normal((d, n_feat))
    u = rng.chisquare(2 * nu, n_feat)
    W = z / ell * np.sqrt(2 * nu / u)
    b = rng.uniform(0, 2 * np.pi, n_feat)
    a = rng.standard_normal(n_feat)
    return lambda X: np.sqrt(2.0 / n_feat) * (np.cos(np.asarray(X) @ W + b) @ a)


def scaling_experiment(ntot=6000, nte=1500, d=3, ell=0.35, noise=0.15, seed=14, sizes=(250, 500, 1000, 2000, 4000, 6000), ms=(32, 128)):
    """Stand-in for Figure 18.14: exact GP on random subsets against SGPR (collapsed Titsias bound) on all the data."""
    rng = np.random.default_rng(seed)
    f = matern_feature_function(rng, d, ell)
    X = rng.uniform(-1, 1, (ntot + nte, d))
    y = f(X) + noise * rng.standard_normal(len(X))
    Xtr, ytr, Xte, yte = X[:ntot], y[:ntot], X[ntot:], y[ntot:]
    kern = lambda A, B: np_(k_matern(A, B, 1.5, ell, 1.0))
    res = {"exact": [], "sgpr": {}}
    for n in sizes:
        Ktt = kern(Xtr[:n], Xtr[:n]) + noise ** 2 * np.eye(n)
        L = np.linalg.cholesky(Ktt)
        a = sla.cho_solve((L, True), ytr[:n])
        pred = kern(Xte, Xtr[:n]) @ a
        res["exact"].append((n, float(np.sqrt(np.mean((pred - yte) ** 2)))))
    for m in ms:
        Z = Xtr[rng.choice(ntot, m, replace=False)]
        out = sparse_gp(kern, Xtr, ytr, Z, Xte, noise ** 2, "vfe")
        res["sgpr"][m] = float(np.sqrt(np.mean((out["mu"] - yte) ** 2)))
    return res


def fig_18_14(out=None):
    """Test RMSE against training-set size: exact GP on subsets, against SGPR on all the data (synthetic stand-in)."""
    res = scaling_experiment()
    n, r = zip(*res["exact"])
    fig, ax = plt.subplots(figsize=(5.4, 3.3))
    ax.plot(n, r, "o-", color=GREEN, label="exact GP on a subset")
    for (m, v), c in zip(res["sgpr"].items(), [BLUE, ORANGE]):
        ax.axhline(v, color=c, ls="--", label="SGPR on all data, M=%d" % m)
    ax.axhline(0.15, color=GREY, ls=":", label="noise level")
    ax.set_xlabel("subsampled dataset size")
    ax.set_ylabel("test RMSE")
    ax.legend(fontsize=8)
    print("   exact:", res["exact"], "sgpr:", res["sgpr"])
    return savefig(fig, CH, "fig18-14", out)


def fig_18_15(out=None):
    """1d GPs with SE kernels but different hyper-parameters, fitted to 20 noisy observations."""
    rng = np.random.default_rng(15)
    x, y, f = _se_data(rng, 20, 1.0, 1.0, 0.1, -8, 8)
    xs = np.linspace(-10, 10, 300)
    fig, axes = plt.subplots(1, 2, figsize=(7.6, 3.0), sharey=True)
    for ax, (ell, sf, sn), lab in zip(axes, [(1.0, 1.0, 0.1), (3.0, 1.16, 0.89)], "ab"):
        mu, v = gp_predict(lambda A, B: k_se(A, B, ell, sf ** 2), x, y, xs, sn ** 2)
        mu, sd = np_(mu), np.sqrt(np_(v))
        ax.plot(xs, mu, color=BLUE, label="mean")
        ax.plot(x, y, "k+", ms=6, label="data")
        band(ax, xs, mu, sd, BLUE, 2)
        ax.set_title(r"$(\ell,\sigma_f,\sigma_y)=(%.1f,%.2f,%.2f)$" % (ell, sf, sn), fontsize=10)
        ax.set_xlabel("$x$")
        panel_label(ax, lab, "upper left")
    axes[0].set_ylabel("$f$")
    axes[0].legend(fontsize=8, loc="lower right")
    return savefig(fig, CH, "fig18-15", out)


def marglik_surface_data(seed):
    rng = np.random.default_rng(seed)
    x = rng.uniform(-6, 6, 7)
    K = np_(k_se(x, x, 1.0, 1.0)) + 1e-8 * np.eye(7)
    f = np.linalg.cholesky(K) @ rng.standard_normal(7)
    return x, f + np.sqrt(0.1) * rng.standard_normal(7)


def marglik_grid(x, y, ells, s2s):
    out = np.zeros((len(s2s), len(ells)))
    for i, s2 in enumerate(s2s):
        for j, ell in enumerate(ells):
            out[i, j] = log_marglik(k_se(x, x, ell, 1.0), y, s2).item()
    return out


def find_two_optima(seed_range=range(0, 400)):
    """Find a 7-point data set whose (ell, noise) likelihood surface has two separated local maxima."""
    ells = np.exp(np.linspace(np.log(0.1), np.log(12), 60))
    s2s = np.exp(np.linspace(np.log(0.01), np.log(2.0), 60))
    for sd in seed_range:
        x, y = marglik_surface_data(sd)
        Z = marglik_grid(x, y, ells, s2s)
        loc = []
        for i in range(1, 59):
            for j in range(1, 59):
                if Z[i, j] == Z[i - 1:i + 2, j - 1:j + 2].max():
                    loc.append((Z[i, j], i, j))
        loc.sort(reverse=True)
        if len(loc) >= 2 and np.log(ells[loc[0][2]]) - np.log(ells[loc[1][2]]) < -1.2 or (len(loc) >= 2 and abs(np.log(ells[loc[0][2]] / ells[loc[1][2]])) > 1.5 and 0.3 < loc[0][0] - loc[1][0] < 1.5):
            return sd, x, y, ells, s2s, Z, loc[:2]
    raise RuntimeError("no data set with two optima")


def fig_18_16(out=None):
    """Local optima of the marginal likelihood (7 data points, SE kernel with sigma_f = 1)."""
    sd, x, y, ells, s2s, Z, loc = find_two_optima()
    xs = np.linspace(-8, 8, 300)
    fig = plt.figure(figsize=(9.2, 3.0))
    ax0 = fig.add_subplot(1, 3, 1)
    cs = ax0.contour(ells, np.sqrt(s2s), Z, levels=np.sort(Z.max() - np.array([0.1, 0.4, 0.8, 1.5, 2.5, 4, 6, 9, 14, 25])), cmap="viridis")
    ax0.set_xscale("log")
    ax0.set_yscale("log")
    ax0.set_xlabel("length scale (log scale)")
    ax0.set_ylabel("noise std dev (log scale)")
    panel_label(ax0, "a", "upper left")
    print("   seed %d, optima:" % sd, [(round(float(v), 2), round(float(ells[j]), 2), round(float(np.sqrt(s2s[i])), 3)) for v, i, j in loc])
    for k, ((v, i, j), lab) in enumerate(zip(loc, "bc")):
        ax0.plot(ells[j], np.sqrt(s2s[i]), "r+", ms=10, mew=2)
        ax = fig.add_subplot(1, 3, 2 + k)
        mu, var = gp_predict(lambda A, B: k_se(A, B, ells[j], 1.0), x, y, xs, s2s[i])
        mu, sdv = np_(mu), np.sqrt(np_(var))
        ax.plot(xs, mu, color=BLUE)
        ax.plot(x, y, "k+", ms=7)
        band(ax, xs, mu, sdv, BLUE, 2)
        ax.set_xlabel("$x$")
        ax.set_title(r"$\ell=%.2f,\ \sigma_y^2=%.2f$, log ML $%.2f$" % (ells[j], s2s[i], v), fontsize=9)
        panel_label(ax, lab, "upper left")
    fig.tight_layout()
    return savefig(fig, CH, "fig18-16", out)


def fig_18_17(out=None):
    """Three approximations to the posterior over (log length scale, log magnitude): grid, Monte Carlo, central composite design."""
    rng = np.random.default_rng(17)
    x, y, _ = _se_data(rng, 12, 1.5, 0.5, 0.2, -5, 5)
    sy2 = 0.2 ** 2

    def logpost(th):
        ell, sf = np.exp(th)
        # weakly informative log-normal priors on both
        lp = -0.5 * ((th[0] - 0.5) / 1.5) ** 2 - 0.5 * ((th[1] + 0.5) / 1.5) ** 2
        return log_marglik(k_se(x, x, ell, sf ** 2), y, sy2).item() + lp
    a = np.linspace(-1.0, 2.6, 61)
    b = np.linspace(-2.8, 1.2, 61)
    Z = np.array([[logpost(np.array([u, v])) for u in a] for v in b])
    r = optimize.minimize(lambda t: -logpost(t), np.array([0.5, -0.3]), method="Nelder-Mead")
    mode = r.x
    # Hessian by finite differences
    h = 1e-2
    H = np.zeros((2, 2))
    f0 = logpost(mode)
    for i in range(2):
        for j in range(2):
            ei, ej = np.eye(2)[i] * h, np.eye(2)[j] * h
            H[i, j] = (logpost(mode + ei + ej) - logpost(mode + ei - ej) - logpost(mode - ei + ej) + logpost(mode - ei - ej)) / (4 * h * h)
    cov = np.linalg.inv(-H)
    w, V = np.linalg.eigh(cov)
    ccd = [mode] + [mode + s * np.sqrt(w[i]) * V[:, i] for i in range(2) for s in (-1, 1)]
    # grid-based: coarse regular grid on the region of high posterior
    ga = np.linspace(mode[0] - 2.5 * np.sqrt(cov[0, 0]), mode[0] + 2.5 * np.sqrt(cov[0, 0]), 7)
    gb = np.linspace(mode[1] - 2.5 * np.sqrt(cov[1, 1]), mode[1] + 2.5 * np.sqrt(cov[1, 1]), 7)
    grid = np.array([[u, v] for u in ga for v in gb])
    lw = np.array([logpost(p) for p in grid])
    wgt = np.exp(lw - lw.max())
    grid = grid[wgt > 1e-3 * wgt.max()]
    # Monte Carlo: random-walk Metropolis
    chain = [mode.copy()]
    cur, lc = mode.copy(), f0
    L = np.linalg.cholesky(cov) * 2.0
    for it in range(3000):
        prop = cur + L @ rng.standard_normal(2)
        lpn = logpost(prop)
        if np.log(rng.uniform()) < lpn - lc:
            cur, lc = prop, lpn
        chain.append(cur.copy())
    chain = np.array(chain[500:])
    fig, axes = plt.subplots(1, 3, figsize=(9.4, 3.1), sharex=True, sharey=True)
    for ax, pts, lab, ttl in zip(axes, [grid, chain[::15], np.array(ccd)], "abc", ["grid", "Monte Carlo", "central composite design"]):
        ax.contour(a, b, np.exp(Z - Z.max()), levels=8, colors=GREY, linewidths=0.8)
        ax.plot(pts[:, 0], pts[:, 1], "o", color=BLUE if lab != "c" else RED, ms=3.2)
        ax.set_title(ttl, fontsize=10)
        ax.set_xlabel("log(length-scale)")
        panel_label(ax, lab, "upper left")
    axes[0].set_ylabel("log(magnitude)")
    fig.tight_layout()
    print("   mode", mode, "cov diag", np.diag(cov), "chain mean", chain.mean(0))
    return savefig(fig, CH, "fig18-17", out)


# kernel of (18.167) in torch: sigma1^2 SE(tau) cos(rho1) + sigma_s^2 Matern32(rho2)
def k_18_167(X, Y, th):
    s1, tau, rho1, ss, rho2 = th[0], th[1], th[2], th[3], th[4]
    return k_se(X, Y, tau, s1 ** 2) * torch.cos(2 * np.pi * dist(X, Y) / rho1) + k_matern(X, Y, 1.5, rho2, ss ** 2)


def kernel_opt_vs_inference_data(seed=18):
    rng = np.random.default_rng(seed)
    truth = lambda x: 1.2 * np.sin(2 * np.pi * x / 3.1) * np.exp(-0.06 * x) + 0.5 * np.sin(2 * np.pi * x / 0.9) + 0.3
    x = np.sort(rng.uniform(0, 6.5, 28))
    y = truth(x) + 0.25 * rng.standard_normal(len(x))
    return x, y, truth


def fig_18_18(out=None):
    """Kernel hyper-parameters by empirical Bayes (point estimate) against posterior inference (HMC)."""
    x, y, truth = kernel_opt_vs_inference_data()
    xs = np.linspace(0, 10, 250)
    ym = y.mean()
    yc = y - ym

    def nll(t):
        th = torch.exp(t[:5])
        return -log_marglik(k_18_167(x, x, th), yc, torch.exp(2 * t[5]))

    rng = np.random.default_rng(18)
    starts = [np.log([1.0, 3.0, 3.0, 0.3, 1.0, 0.3])] + [np.log([rng.uniform(.3, 2), rng.uniform(1, 6), rng.uniform(.5, 5), rng.uniform(.1, 1), rng.uniform(.3, 3), rng.uniform(.1, .6)]) for _ in range(5)]
    th_eb, v, allr = fit_theta(nll, starts[0], starts[1:], bounds=[(-4, 3.2)] * 6, maxiter=200)
    print("   EB: nll %.3f  theta %s" % (v, np.round(np.exp(th_eb), 3)))

    def pred(t):
        th = torch.exp(torch.tensor(t[:5]))
        mu, var = gp_predict(lambda A, B: k_18_167(A, B, th), x, yc, xs, float(np.exp(2 * t[5])))
        return np_(mu) + ym, np.sqrt(np_(var))
    mu_eb, sd_eb = pred(th_eb)

    # posterior inference with HMC, N(0, 1.5^2) priors on the log parameters
    def lpg(t):
        try:
            tt = torch.tensor(t, requires_grad=True)
            lp = -nll(tt) - 0.5 * (((tt - torch.tensor(np.log([1.0, 3.0, 2.5, 0.4, 1.0, 0.3]))) / 1.2) ** 2).sum()
            lp.backward()
            return lp.item(), tt.grad.numpy().copy()
        except Exception:
            return -np.inf, np.zeros_like(t)
    S, acc, eps = hmc(lpg, np.log([1.0, 3.0, 2.5, 0.4, 1.0, 0.3]), 400, 300, rng, n_leap=15, eps0=0.02)
    mus = []
    for t in S[::4]:
        try:
            m_, s_ = pred(t)
            mus.append((m_, s_))
        except Exception:
            pass
    M = np.array([m for m, s in mus])
    SD = np.array([s for m, s in mus])
    mu_b = M.mean(0)
    var_b = (SD ** 2).mean(0) + M.var(0)
    fig, axes = plt.subplots(1, 2, figsize=(8.6, 3.1), sharey=True)
    for ax, (mu, sd, ttl), lab in zip(axes, [(mu_eb, sd_eb, "maximum marginal likelihood"), (mu_b, np.sqrt(var_b), "posterior inference (HMC)")], "ab"):
        ax.plot(xs, mu, color=BLUE, label="predictive mean")
        band(ax, xs, mu, sd, BLUE, 1.96)
        ax.plot(xs, truth(xs), color=GREY, ls="--", label="truth")
        ax.plot(x, y, "k.", ms=4)
        ax.set_title(ttl, fontsize=10)
        ax.set_xlabel("$x$ [day]")
        panel_label(ax, lab, "upper right")
    axes[0].set_ylabel("$y$ [ppm]")
    axes[0].legend(fontsize=8, loc="lower left")
    fig.tight_layout()
    print("   HMC acceptance %.2f, eps %.4f; mean sd EB %.3f, HMC %.3f over x>7" % (acc, eps, sd_eb[xs > 7].mean(), np.sqrt(var_b)[xs > 7].mean()))
    return savefig(fig, CH, "fig18-18", out)


def fig_18_20(out=None):
    """Additive (GAM) kernel on the diabetes data: ARD amplitudes and the posterior of each component (stand-in for concrete data)."""
    from sklearn.datasets import load_diabetes
    d = load_diabetes()
    X = (d.data - d.data.mean(0)) / d.data.std(0)
    y = (d.target - d.target.mean()) / d.target.std()
    names = d.feature_names
    n, D = X.shape
    Xt = torch.tensor(X)

    def Kadd(t):
        ls, s2 = torch.exp(t[:D]), torch.exp(2 * t[D:2 * D])
        K = 0.0
        for j in range(D):
            K = K + k_se(Xt[:, j:j + 1], Xt[:, j:j + 1], ls[j], s2[j])
        return K

    nllf = lambda t: -log_marglik(Kadd(t), y, torch.exp(2 * t[2 * D]))
    t0 = np.concatenate([np.zeros(D), np.log(0.4) * np.ones(D), [np.log(0.7)]])
    th, v, _ = fit_theta(nllf, t0, maxiter=120)
    ls, sg = np.exp(th[:D]), np.exp(th[D:2 * D])
    sn = np.exp(th[2 * D])
    K = np_(Kadd(torch.tensor(th)))
    L = np.linalg.cholesky(K + sn ** 2 * np.eye(n))
    alpha = sla.cho_solve((L, True), y)
    order = np.argsort(-sg ** 2)
    show = order[:6]
    fig, axes = plt.subplots(2, 3, figsize=(8.8, 4.8))
    for ax, j in zip(axes.ravel(), show):
        g = np.linspace(X[:, j].min(), X[:, j].max(), 100)
        kj = np_(k_se(g, X[:, j], ls[j], sg[j] ** 2))
        mu = kj @ alpha
        V = sla.solve_triangular(L, kj.T, lower=True)
        var = sg[j] ** 2 - (V * V).sum(0)
        ax.plot(g, mu, color=BLUE)
        band(ax, g, mu, np.sqrt(np.maximum(var, 0)), BLUE, 2)
        ax.set_title("%s  ($\\sigma_d^2=%.2f$)" % (names[j], sg[j] ** 2), fontsize=9)
        ax.set_xlabel("standardised input")
    fig.tight_layout()
    print("   additive GP: sigma_d^2 =", dict(zip(names, np.round(sg ** 2, 3))), "noise", round(sn, 3))
    return savefig(fig, CH, "fig18-20", out)


# =========================================================================== time series data
def airline_data():
    """Monthly totals of international airline passengers, 1949-1960 (R's AirPassengers; 144 values)."""
    p = os.path.join(DATA_OUT, "ch18-airline.json")
    if not os.path.exists(p):
        vals = [float(v) for v in open(os.path.join(WORK, "airline.txt")).read().strip().split(",")]
        json.dump({"y": vals, "t0": 1949.0, "dt": 1 / 12}, open(p, "w"))
    d = json.load(open(p))
    y = np.array(d["y"])
    return d["t0"] + np.arange(len(y)) * d["dt"], y


def co2_data():
    """Monthly mean atmospheric CO2 (ppm) at Mauna Loa, March 1958 to December 2001 (statsmodels' weekly record averaged by month)."""
    import statsmodels.api as sm
    df = sm.datasets.co2.load_pandas().data.dropna()
    m = df["co2"].groupby([df.index.year, df.index.month]).mean()
    t = np.array([yr + (mo - 0.5) / 12 for yr, mo in m.index])
    return t, m.values


# =========================================================================== Figure 18.22: compositional kernel search
BASE_K = ("SE", "RQ", "Lin", "Per")


def _base_nparams(name):
    return {"SE": 2, "RQ": 3, "Lin": 2, "Per": 3}[name]


def _eval_base(name, X, Y, p):
    """p: positive parameters."""
    if name == "SE":
        return k_se(X, Y, p[0], p[1])
    if name == "RQ":
        return k_rq(X, Y, p[0], p[1], p[2])
    if name == "Lin":
        return k_lin(X, Y, p[0], p[1])
    if name == "Per":
        return k_periodic(X, Y, p[0], p[1], p[2])


def _base_init(name, scale, rng):
    if name == "SE":
        return [scale * rng.uniform(0.05, 0.5), 1.0]
    if name == "RQ":
        return [scale * rng.uniform(0.05, 0.5), 1.0, 1.0]
    if name == "Lin":
        return [0.3, 0.0]          # offset c is a free (log-positive shifted) parameter below
    if name == "Per":
        return [rng.uniform(0.5, 2.0), 1.0, 1.0]


def kernel_expr_eval(terms, X, Y, theta):
    """terms: list of tuples of base names (a sum of products). theta: flat tensor of log-parameters
    (positive parameters; the Lin offset c is stored as an unconstrained value)."""
    K, pos = 0.0, 0
    for term in terms:
        Kt = 1.0
        for name in term:
            n = _base_nparams(name)
            raw = theta[pos:pos + n]
            pos += n
            if name == "Lin":
                p = [torch.exp(raw[0]), raw[1]]
            else:
                p = [torch.exp(r) for r in raw]
            Kt = Kt * _eval_base(name, X, Y, p)
        K = K + Kt
    return K


def kernel_expr_nparams(terms):
    return sum(_base_nparams(n) for t in terms for n in t)


def fit_expr(terms, x, y, rng, n_init=3, scale=1.0, period_init=(1.0,), extra_init=None):
    """Maximise the marginal likelihood of sum-of-products kernel + white noise over several initialisations."""
    npar = kernel_expr_nparams(terms)

    def nll(t):
        K = kernel_expr_eval(terms, x, x, t[:npar])
        return -log_marglik(K, y, torch.exp(2 * t[npar]) + 1e-6)
    starts = []
    for i in range(n_init):
        th = []
        for term in terms:
            for name in term:
                v = _base_init(name, scale, rng)
                if name == "Per":
                    v[1] = period_init[i % len(period_init)] * rng.uniform(0.97, 1.03)
                th.extend([np.log(v[0]), np.log(v[1])] + ([np.log(v[2])] if len(v) > 2 else []) if name != "Lin" else [np.log(v[0]), v[1]])
        starts.append(np.array(th + [np.log(0.2)]))
    best, val, _ = fit_theta(nll, starts[0], starts[1:], maxiter=150, bounds=[(-8, 6)] * (npar + 1) if False else None)
    return best, val


def kernel_search(x, y, depth=4, seed=22, verbose=True):
    rng = np.random.default_rng(seed)
    scale = x.max() - x.min()
    npar0 = 0
    # the starting point: white noise only
    K0 = torch.zeros(len(x), len(x))
    n = len(x)
    s2 = float(np.var(y))
    best_ml = -0.5 * (y @ y) / s2 - 0.5 * n * np.log(2 * np.pi * s2)
    history = [([], best_ml - 0.5 * 1 * np.log(n), None)]
    cur = []
    cur_bic = best_ml - 0.5 * np.log(n)
    cur_theta = None
    for d in range(depth):
        cands = []
        for b in BASE_K:
            cands.append(cur + [(b,)])
        for i in range(len(cur)):
            for b in BASE_K:
                t2 = [tuple(t) for t in cur]
                t2[i] = t2[i] + (b,)
                cands.append(t2)
        results = []
        for c in cands:
            th, nllv = fit_expr(c, x, y, rng, n_init=2, scale=scale, period_init=(1.0, 2.0))
            k = len(th)
            bic = -nllv - 0.5 * k * np.log(n)
            results.append((bic, c, th, -nllv))
        results.sort(key=lambda r: -r[0])
        bic, c, th, ml = results[0]
        if verbose:
            print("   depth %d: best %s  BIC %.2f (log ML %.2f)" % (d + 1, " + ".join("x".join(t) for t in c), bic, ml))
        if bic <= cur_bic + 1e-6:
            break
        cur, cur_bic, cur_theta = c, bic, th
        history.append((c, bic, th))
    return cur, cur_theta, history


def fig_18_22(out=None):
    """Compositional kernel search on the airline data (BIC), and the fitted components."""
    t, y = airline_data()
    ym, ys = y.mean(), y.std()
    yc = (y - ym) / ys
    tt = t - t.mean()
    terms, theta, hist = kernel_search(tt, yc, depth=4)
    npar = kernel_expr_nparams(terms)
    th = torch.tensor(theta)
    sn2 = float(np.exp(2 * theta[npar])) + 1e-6
    xs = np.linspace(tt.min(), tt.max() + 4.0, 400)
    K = kernel_expr_eval(terms, tt, tt, th[:npar])
    L, alpha = gp_fit(K, yc, sn2)
    # component predictions
    comps, pos = [], 0
    for term in terms:
        n_ = sum(_base_nparams(b) for b in term)
        Kt = kernel_expr_eval([term], xs, tt, torch.cat([th[pos:pos + n_]]))
        comps.append(np_(Kt @ alpha) * ys)
        pos += n_
    mu, var = gp_predict(lambda A, B: kernel_expr_eval(terms, A, B, th[:npar]), tt, yc, xs, sn2)
    mu, sd = np_(mu) * ys + ym, np.sqrt(np_(var)) * ys
    nrow = 1 + len(terms)
    fig, axes = plt.subplots(nrow, 1, figsize=(6.4, 1.8 * nrow + 0.5), sharex=True)
    axes[0].plot(xs + t.mean(), mu, color=BLUE)
    band(axes[0], xs + t.mean(), mu, sd, BLUE, 2)
    axes[0].plot(t, y, "k.", ms=3)
    axes[0].axvline(t.max(), color=GREY, ls=":")
    axes[0].set_title("posterior of the discovered model: " + " + ".join("x".join(tm) for tm in terms), fontsize=9)
    for ax, c, term in zip(axes[1:], comps, terms):
        ax.plot(xs + t.mean(), c, color=GREEN)
        ax.set_title("component: " + " x ".join(term), fontsize=8.5)
    axes[-1].set_xlabel("year")
    fig.tight_layout()
    print("   discovered:", terms, "noise sd", np.sqrt(sn2) * ys)
    return savefig(fig, CH, "fig18-22", out)


# =========================================================================== Figures 18.23, 18.24: spectral mixture kernels
def sm_kernel_np(r, w, mu, v):
    return sum(wi * np.cos(2 * np.pi * mi * r) * np.exp(-2 * np.pi ** 2 * vi * r * r) for wi, mi, vi in zip(w, mu, v))


def fit_sm(x, y, Q, rng, n_restart=6, noise0=0.2, init=None, maxiter=250):
    """Spectral mixture kernel by maximum marginal likelihood; parameters log (w, mu, v) and log noise."""
    def unpack(t):
        return torch.exp(t[:Q]), torch.exp(t[Q:2 * Q]), torch.exp(t[2 * Q:3 * Q]), torch.exp(2 * t[3 * Q])

    def nll(t):
        w, m, v, s2 = unpack(t)
        return -log_marglik(k_sm(x, x, w, m, v), y, s2 + 1e-6)
    starts = []
    span = x.max() - x.min()
    for r in range(n_restart):
        if init is not None and r == 0:
            mu0, w0 = init
            mu0 = np.maximum(mu0[:Q], 1e-3 / span)
        else:
            mu0 = np.exp(rng.uniform(np.log(1.0 / span), np.log(0.5 / np.median(np.diff(x))), Q))
            w0 = np.full(Q, np.var(y) / Q)
        v0 = (1.0 / span * rng.uniform(0.2, 1.0, Q)) ** 2
        starts.append(np.concatenate([np.log(w0), np.log(mu0), np.log(v0), [np.log(noise0)]]))
    th, val, _ = fit_theta(nll, starts[0], starts[1:], maxiter=maxiter)
    w, m, v, s2 = [np_(a) if torch.is_tensor(a) else a for a in unpack(torch.tensor(th))]
    return dict(w=w, mu=m, v=v, s2=float(s2), nll=val)


def fig_18_23(out=None):
    """GP with a spectral mixture kernel in 1d: learned against true kernel, and predictions."""
    rng = np.random.default_rng(23)
    w, mu, v = [1.0, 0.7], [0.35, 1.1], [0.004, 0.012]
    x = np.sort(rng.uniform(0, 10, 90))
    K = sm_kernel_np(x[:, None] - x[None], w, mu, v) + 1e-7 * np.eye(len(x))
    y = np.linalg.cholesky(K) @ rng.standard_normal(len(x)) + 0.1 * rng.standard_normal(len(x))
    fit = fit_sm(x, y, 3, rng, n_restart=8, noise0=0.1)
    xs = np.linspace(0, 14, 300)
    mu_p, var_p = gp_predict(lambda A, B: k_sm(A, B, fit["w"], fit["mu"], fit["v"]), x, y, xs, fit["s2"] + 1e-6)
    tau = np.linspace(0, 5, 300)
    fig, axes = plt.subplots(1, 2, figsize=(8.2, 2.9))
    axes[0].plot(tau, sm_kernel_np(tau, w, mu, v), color=BLUE, label="true kernel")
    axes[0].plot(tau, sm_kernel_np(tau, fit["w"], fit["mu"], fit["v"]), color=RED, ls="--", label="inferred kernel")
    axes[0].set_xlabel(r"$\tau$")
    axes[0].set_ylabel(r"$k(\tau)$")
    axes[0].legend(fontsize=8)
    panel_label(axes[0], "a", "upper right")
    axes[1].plot(x, y, "k.", ms=4, label="data")
    axes[1].plot(xs, np_(mu_p), color=RED, label="prediction")
    band(axes[1], xs, np_(mu_p), np.sqrt(np_(var_p)), RED, 2)
    axes[1].set_xlabel("$x$")
    axes[1].legend(fontsize=8, loc="upper left")
    panel_label(axes[1], "b", "lower right")
    fig.tight_layout()
    print("   SM fit: w %s mu %s v %s noise %.3f" % (np.round(fit["w"], 3), np.round(fit["mu"], 3), np.round(fit["v"], 4), np.sqrt(fit["s2"])))
    return savefig(fig, CH, "fig18-23", out)


def _periodogram_peaks(t, y, Q):
    n = len(t)
    dt = np.median(np.diff(t))
    fr = np.fft.rfftfreq(n, dt)
    P = np.abs(np.fft.rfft(y - y.mean())) ** 2
    idx = [i for i in np.argsort(-P) if fr[i] > 0][:Q]
    return fr[idx], P[idx] / P[idx].sum() * np.var(y)


def extrapolation_fits(t, y, ntrain, Q=4, seed=24):
    """Fit Matern 3/2, RQ, periodic, SE and spectral mixture kernels (empirical Bayes) to the first ntrain points after removing a
    linear trend; returns forecasts for all t."""
    rng = np.random.default_rng(seed)
    tr = slice(0, ntrain)
    p = np.polyfit(t[tr], y[tr], 1)
    r = y - np.polyval(p, t)
    sd = r[tr].std()
    r = r / sd
    tt = t - t[tr].mean()
    x = tt[tr]
    out = {}
    models = {
        "Matern 3/2": (lambda th: (lambda A, B: k_matern(A, B, 1.5, th[0], th[1])), np.log([2.0, 1.0])),
        "RQ": (lambda th: (lambda A, B: k_rq(A, B, th[0], th[1], th[2])), np.log([2.0, 1.0, 1.0])),
        "Periodic": (lambda th: (lambda A, B: k_periodic(A, B, th[0], th[1], th[2])), np.log([1.0, 1.0, 1.0])),
        "SE": (lambda th: (lambda A, B: k_se(A, B, th[0], th[1])), np.log([2.0, 1.0])),
    }
    for name, (mk, th0) in models.items():
        npar = len(th0)

        def nll(th, mk=mk, npar=npar):
            return -log_marglik(mk(torch.exp(th[:npar]))(x, x), r[tr], torch.exp(2 * th[npar]) + 1e-6)
        starts = [np.concatenate([th0 + rng.normal(0, 0.5, npar), [np.log(0.2)]]) for _ in range(5)]
        th, v, _ = fit_theta(nll, starts[0], starts[1:], maxiter=200)
        mu, var = gp_predict(mk(torch.exp(torch.tensor(th[:npar]))), x, r[tr], tt, float(np.exp(2 * th[npar])) + 1e-6)
        out[name] = (np_(mu), np.sqrt(np_(var) + np.exp(2 * th[npar])))
    mu0, w0 = _periodogram_peaks(t[tr], r[tr], Q)
    fit = fit_sm(x, r[tr], Q, rng, n_restart=6, init=(mu0, w0))
    mu, var = gp_predict(lambda A, B: k_sm(A, B, fit["w"], fit["mu"], fit["v"]), x, r[tr], tt, fit["s2"] + 1e-6)
    out["Spectral mixture"] = (np_(mu), np.sqrt(np_(var) + fit["s2"]))
    return {k: (m * sd + np.polyval(p, t), s * sd) for k, (m, s) in out.items()}


def fig_18_24(out=None):
    """Extrapolations on CO2 and airline passengers with five kernels, each with hyper-parameters learned by empirical Bayes."""
    t1, y1 = co2_data()
    t1, y1 = t1[:360], y1[:360]
    t2, y2 = airline_data()
    sets = [("CO2", t1, y1, 180), ("airline", t2, y2, 96)]
    names = ["Matern 3/2", "RQ", "Periodic", "SE", "Spectral mixture"]
    fig, axes = plt.subplots(2, 5, figsize=(11.6, 4.2), sharex="row")
    for r_, (nm, t, y, nt) in enumerate(sets):
        res = extrapolation_fits(t, y, nt)
        for c, k in enumerate(names):
            ax = axes[r_, c]
            mu, sd = res[k]
            ax.plot(t, y, "k.", ms=2.2)
            ax.plot(t, mu, color=BLUE, lw=1.1)
            ax.fill_between(t, mu - 2 * sd, mu + 2 * sd, color=BLUE, alpha=0.2, lw=0)
            ax.axvline(t[nt], color=GREY, ls=":")
            rm = np.sqrt(np.mean((mu[nt:] - y[nt:]) ** 2))
            ax.set_title("%s, %s\ntest RMSE %.1f" % (nm, k, rm), fontsize=8)
            ax.tick_params(labelsize=7)
            print("   %s %s: test RMSE %.2f" % (nm, k, rm))
    fig.tight_layout()
    return savefig(fig, CH, "fig18-24", out)


# =========================================================================== Figures 18.26, 18.28, 18.29
def fig_18_26(out=None):
    """A discontinuous function: GP with a Matern 3/2 kernel against a GP whose Matern kernel acts on a learned MLP feature map."""
    rng = np.random.default_rng(26)
    f = lambda x: np.where(x < 0.1, 0.4 * x - 0.5, 0.9 - 0.4 * x)
    x = np.sort(rng.uniform(-1.5, 1.5, 70))
    y = f(x) + 0.05 * rng.standard_normal(len(x))
    xs = np.linspace(-1.5, 1.5, 300)
    Xt, yt = torch.tensor(x[:, None]), torch.tensor(y)

    # shallow
    nll = lambda t: -log_marglik(k_matern(Xt, Xt, 1.5, torch.exp(t[0]), torch.exp(t[1])), yt, torch.exp(2 * t[2]) + 1e-6)
    th, v, _ = fit_theta(nll, np.log([0.5, 1.0, 0.1]), [np.log([0.2, 0.5, 0.05]), np.log([1.0, 1.0, 0.3])])
    mu_s, var_s = gp_predict(lambda A, B: k_matern(A, B, 1.5, np.exp(th[0]), np.exp(th[1])), x, y, xs, np.exp(2 * th[2]) + 1e-6)
    # deep: MLP 1-15-10 followed by Matern 3/2, trained jointly on the marginal likelihood
    torch.manual_seed(1)
    net = torch.nn.Sequential(torch.nn.Linear(1, 15), torch.nn.Tanh(), torch.nn.Linear(15, 10))
    lp = torch.tensor(np.log([1.0, 1.0, 0.1]), requires_grad=True)
    opt = torch.optim.Adam(list(net.parameters()) + [lp], lr=0.01)
    for it in range(1200):
        opt.zero_grad()
        H = net(Xt)
        loss = -log_marglik(k_matern(H, H, 1.5, torch.exp(lp[0]), torch.exp(lp[1])), yt, torch.exp(2 * lp[2]) + 1e-6)
        loss.backward()
        opt.step()
    with torch.no_grad():
        Hs, H = net(torch.tensor(xs[:, None])), net(Xt)
        mu_d, var_d = gp_predict(lambda A, B: k_matern(A, B, 1.5, torch.exp(lp[0]), torch.exp(lp[1])), H, y, Hs, torch.exp(2 * lp[2]).item() + 1e-6)
    fig, axes = plt.subplots(1, 2, figsize=(8.2, 2.9), sharey=True)
    for ax, mu, var, lab, ttl in zip(axes, [mu_s, mu_d], [var_s, var_d], "ab", ["GP, Matern 3/2 kernel", "GP, MLP + Matern 3/2 kernel"]):
        ax.plot(xs, f(xs), color=GREY, ls="--", label="truth")
        ax.plot(x, y, "k.", ms=4, label="data")
        ax.plot(xs, np_(mu), color=BLUE, label="model")
        band(ax, xs, np_(mu), np.sqrt(np_(var)), BLUE, 2)
        ax.set_xlabel("$x$")
        ax.set_title(ttl, fontsize=9.5)
        panel_label(ax, lab, "lower left")
    axes[0].set_ylabel("$y$")
    axes[0].legend(fontsize=8, loc="upper right")
    fig.tight_layout()
    print("   shallow RMSE vs truth %.3f; deep %.3f; final deep loss %.2f" % (np.sqrt(np.mean((np_(mu_s) - f(xs)) ** 2)), np.sqrt(np.mean((np_(mu_d) - f(xs)) ** 2)), loss.item()))
    return savefig(fig, CH, "fig18-26", out)


def nngp_erf_kernel(x, xp, s0, s):
    """NN-GP kernel of an infinitely wide one-hidden-layer net with erf units (Table 18.4): (2/pi) arcsin(...)."""
    xt = np.stack([np.ones_like(x), x], 1)
    xpt = np.stack([np.ones_like(xp), xp], 1)
    Sig = np.diag([s0 ** 2, s ** 2])
    num = 2 * xt @ Sig @ xpt.T
    d1 = 1 + 2 * np.einsum("ij,jk,ik->i", xt, Sig, xt)
    d2 = 1 + 2 * np.einsum("ij,jk,ik->i", xpt, Sig, xpt)
    return 2 / np.pi * np.arcsin(num / np.sqrt(d1[:, None] * d2[None, :]))


def fig_18_28(out=None):
    """Samples from a GP with the NN-GP kernel of an infinitely wide erf network."""
    x = np.linspace(-5, 5, 300)
    rng = np.random.default_rng(28)
    z = rng.standard_normal(len(x))
    fig, axes = plt.subplots(1, 2, figsize=(8.2, 2.9))
    for ax, s0, lab in zip(axes, [0.0, 5.0], "ab"):
        for s, c in zip([1, 3, 10], [BLUE, ORANGE, GREEN]):
            K = nngp_erf_kernel(x, x, s0, s) + 1e-6 * np.eye(len(x))
            ax.plot(x, np.linalg.cholesky(K) @ z, color=c, lw=1.6, label=r"$\sigma=%d$" % s)
        ax.set_title(r"$\sigma_0=%g$" % s0, fontsize=10)
        ax.set_xlabel("$x$")
        ax.legend(fontsize=8, loc="best")
        panel_label(ax, lab, "lower left")
    fig.tight_layout()
    return savefig(fig, CH, "fig18-28", out)


def mauna_loa_kernel(X, Y, th):
    """Kernel (18.189) = (18.190) + (18.191) + (18.192) + (18.193); th has 11 positive entries theta_0..theta_10."""
    r2 = sqdist(X, Y)
    r = torch.sqrt(torch.clamp(r2, min=1e-30))
    k1 = th[0] ** 2 * torch.exp(-r2 / (2 * th[1] ** 2))
    k2 = th[2] ** 2 * torch.exp(-r2 / (2 * th[3] ** 2) - th[5] * torch.sin(np.pi * r / th[4]) ** 2)
    k3 = th[6] ** 2 * (1 + r2 / (2 * th[8] * th[7] ** 2)) ** (-th[8])
    k4 = th[9] ** 2 * torch.exp(-r2 / (2 * th[10] ** 2))
    return k1 + k2 + k3 + k4


MAUNA_INIT = np.array([60.0, 60.0, 2.5, 90.0, 1.0, 1.3, 0.7, 1.2, 0.8, 0.2, 0.15])


def mauna_loa_fit(ntrain=None, t=None, y=None):
    if t is None:
        t, y = co2_data()
    t0 = 1958.0
    ntr = ntrain or int(np.searchsorted(t, 1990.0))
    x = t[:ntr] - t0
    m = y[:ntr].mean()
    nll = lambda th: -log_marglik(mauna_loa_kernel(x, x, torch.exp(th[:11])), y[:ntr] - m, torch.exp(2 * th[11]) + 1e-6)
    th0 = np.concatenate([np.log(MAUNA_INIT), [np.log(0.1)]])
    th, v, _ = fit_theta(nll, th0, maxiter=400)
    return t, y, ntr, m, th, v


def fig_18_29(out=None):
    """The Mauna Loa CO2 series and GP forecasts with the kernel (18.189)."""
    t, y, ntr, m, th, v = mauna_loa_fit()
    x = t - 1958.0
    ths = torch.exp(torch.tensor(th[:11]))
    xs = np.linspace(0, 2002 - 1958 + 6, 500)
    mu, var = gp_predict(lambda A, B: mauna_loa_kernel(A, B, ths), x[:ntr], y[:ntr] - m, xs, float(np.exp(2 * th[11])) + 1e-6)
    mu, sd = np_(mu) + m, np.sqrt(np_(var))
    fig, axes = plt.subplots(1, 2, figsize=(8.8, 3.0))
    axes[0].plot(t[:ntr], y[:ntr], "k.", ms=2.5)
    axes[0].set_xlabel("year")
    axes[0].set_ylabel("CO$_2$ in ppm")
    panel_label(axes[0], "a", "upper left")
    axes[1].plot(t, y, "k.", ms=2.5, label="data")
    axes[1].plot(xs + 1958, mu, color=BLUE, lw=1.2, label="mean")
    axes[1].fill_between(xs + 1958, mu - 2 * sd, mu + 2 * sd, color=BLUE, alpha=0.25, lw=0, label="confidence")
    axes[1].axvline(t[ntr], color=GREY, ls=":")
    axes[1].set_xlabel("year")
    axes[1].legend(fontsize=8, loc="lower right")
    panel_label(axes[1], "b", "upper left")
    fig.tight_layout()
    print("   theta =", np.round(np.exp(th[:11]), 3), "noise", round(float(np.exp(th[11])), 3), "nll", round(v, 3), "n_train", ntr)
    return savefig(fig, CH, "fig18-29", out)


# =========================================================================== deep GPs (Supplement 18.1)
def step_data(n=20, seed=30, noise=0.1):
    rng = np.random.default_rng(seed)
    x = np.sort(np.concatenate([np.linspace(-1, 1, n)]) + 0.02 * rng.standard_normal(n))
    y = (x > 0).astype(float) + noise * rng.standard_normal(n)
    return x, y


def _rbf_h(F, G, h):
    """exp(-||f - g||^2 / (2 h)) for rows of F (n x H) and G (m x H)."""
    d = (F * F).sum(1)[:, None] + (G * G).sum(1)[None, :] - 2 * F @ G.T
    return torch.exp(-torch.clamp(d, min=0.0) / (2 * h))


def dgp_hmc(x_tr, y, x_te, widths, sigma, n_samples=400, n_warm=400, n_leap=15, seed=0, eps0=0.05):
    """Posterior of a deep GP with RBF kernels by Hamiltonian Monte Carlo on the whitened hidden-layer values.

    widths = [H_1, ..., H_{L-1}] hidden units per layer (the output layer has one unit). The kernel of layer l is
    exp(-||f - f'||^2 / (2 H_{l-1})) with H_0 = D = 1 (Supplement 18.1.0.2). The hidden-layer values at the training
    AND test inputs are latent variables; the last layer is integrated out exactly. Returns, for each sample, the
    output-layer predictive mean and variance at x_te, the hidden values at the test inputs, and the sampler summary."""
    xa = np.concatenate([x_tr, x_te])
    n, ntr = len(xa), len(x_tr)
    Xa = torch.tensor(xa[:, None])
    yt = torch.tensor(y)
    prev = [1] + list(widths)            # width of the input to each layer
    L1 = chol_safe(_rbf_h(Xa, Xa, 1.0), 1e-6)
    sizes = [n * h for h in widths]
    offs = np.concatenate([[0], np.cumsum(sizes)])

    def forward(zv):
        Fs, F = [], None
        for l, h in enumerate(widths):
            Z = zv[offs[l]:offs[l + 1]].reshape(n, h)
            if l == 0:
                F = L1 @ Z
            else:
                K = _rbf_h(F, F, prev[l])
                F = chol_safe(K, 1e-6) @ Z
            Fs.append(F)
        return Fs

    def lp_fn(zv):
        Fs = forward(zv)
        F = Fs[-1]
        K = _rbf_h(F[:ntr], F[:ntr], prev[-1])
        return log_marglik(K, yt, sigma ** 2) - 0.5 * (zv ** 2).sum(), Fs

    def lpg(zn):
        try:
            z = torch.tensor(zn, requires_grad=True)
            lp, _ = lp_fn(z)
            lp.backward()
            return lp.item(), z.grad.numpy().copy()
        except Exception:
            return -np.inf, np.zeros_like(zn)

    rng = np.random.default_rng(seed)
    z0 = rng.standard_normal(offs[-1]) * 0.5
    S, acc, eps = hmc(lpg, z0, n_samples, n_warm, rng, n_leap=n_leap, eps0=eps0)
    res = dict(mu=[], var=[], hidden=[], acc=acc, eps=eps)
    for zn in S:
        with torch.no_grad():
            _, Fs = lp_fn(torch.tensor(zn))
            F = Fs[-1]
            Ktt = _rbf_h(F[:ntr], F[:ntr], prev[-1]) + sigma ** 2 * torch.eye(ntr)
            Lc = chol_safe(Ktt, 0.0)
            a = torch.cholesky_solve(yt.reshape(-1, 1), Lc)
            Kst = _rbf_h(F[ntr:], F[:ntr], prev[-1])
            mu = (Kst @ a)[:, 0]
            Vv = torch.linalg.solve_triangular(Lc, Kst.T, upper=False)
            var = torch.clamp(1.0 - (Vv * Vv).sum(0), min=0.0)
        res["mu"].append(mu.numpy())
        res["var"].append(var.numpy())
        res["hidden"].append([f.numpy() for f in Fs])
    for k in ("mu", "var"):
        res[k] = np.array(res[k])
    return res


def dgp_avg_cov(hidden, widths_last, n_tr):
    """Average of K_2(f_1(x), f_1(x')) over the posterior samples for a 2-layer DGP, on the test inputs."""
    Ks = []
    for hs in hidden:
        F = torch.tensor(hs[0][n_tr:])
        Ks.append(_rbf_h(F, F, widths_last).numpy())
    return np.mean(Ks, 0)


def k_lim(x, y):
    """Limiting kernel of a 2-layer RBF deep GP as the width tends to infinity: exp(exp(-r^2/(2D)) - 1), D = 1."""
    return torch.exp(torch.exp(-0.5 * sqdist(x, y)) - 1.0)


_DGP_CACHE = os.path.join(WORK, "dgp_cache.npz")


def _dgp_runs():
    """All HMC runs for Figures S18.2 to S18.4 (cached: about two minutes)."""
    if os.path.exists(_DGP_CACHE):
        z = np.load(_DGP_CACHE, allow_pickle=True)
        return z["runs"].item()
    x_tr, y = step_data()
    x_te = np.linspace(-2, 2, 41)
    runs = {"x_tr": x_tr, "y": y, "x_te": x_te}
    for w in (1, 16, 256):
        runs["w%d" % w] = dgp_hmc(x_tr, y, x_te, [w], 0.1, n_samples=300, n_warm=300, n_leap=12, seed=w)
    runs["deep4"] = dgp_hmc(x_tr, y, x_te, [1, 1, 1], 0.1, n_samples=600, n_warm=600, n_leap=20, seed=4, eps0=0.03)
    np.savez(_DGP_CACHE, runs=np.array(runs, dtype=object))
    return runs


def fig_sup18_2(out=None):
    """Step function fitted by a standard GP and by a 4-layer deep GP (HMC)."""
    R = _dgp_runs()
    x_tr, y, xs = R["x_tr"], R["y"], R["x_te"]
    mu_g, var_g = gp_predict(lambda A, B: k_se(A, B, 1.0), x_tr, y, xs, 0.01)
    d = R["deep4"]
    mean = d["mu"].mean(0)
    var = d["var"].mean(0) + d["mu"].var(0)
    rng = np.random.default_rng(3)
    fig, axes = plt.subplots(1, 2, figsize=(8.2, 3.0), sharey=True)
    axes[0].plot(xs, np_(mu_g), color=BLUE, label="mean")
    band(axes[0], xs, np_(mu_g), np.sqrt(np_(var_g)), RED, 2, 0.25)
    axes[0].plot(x_tr, y, "o", color=RED, ms=3.5, label="data")
    axes[0].set_title("standard GP, RBF kernel", fontsize=9.5)
    axes[1].plot(xs, mean, color=BLUE)
    band(axes[1], xs, mean, np.sqrt(var), RED, 2, 0.25)
    for i in rng.choice(len(d["mu"]), 40, replace=False):
        axes[1].plot(xs, d["mu"][i] + np.sqrt(d["var"][i]) * rng.standard_normal(len(xs)), ".", color=BLUE, ms=1.6, alpha=0.6)
    axes[1].plot(x_tr, y, "o", color=RED, ms=3.5)
    axes[1].set_title("deep GP, 4 layers of RBF kernels", fontsize=9.5)
    for ax, lab in zip(axes, "ab"):
        ax.set_xlabel("$x$")
        panel_label(ax, lab, "upper left")
    axes[0].set_ylabel("$y$")
    axes[0].legend(fontsize=8, loc="lower right")
    fig.tight_layout()
    print("   deep4 HMC acceptance %.2f, step %.4f" % (d["acc"], d["eps"]))
    return savefig(fig, CH, "fig18-sup2", out)


def fig_sup18_3(out=None):
    """The function learned at each layer of the 4-layer deep GP (three posterior samples)."""
    R = _dgp_runs()
    d = R["deep4"]
    ntr = len(R["x_tr"])
    xs = R["x_te"]
    d_ = d["hidden"]
    idx = np.linspace(len(d_) // 3, len(d_) - 1, 3).astype(int)
    fig, axes = plt.subplots(1, 4, figsize=(10.0, 2.6))
    for ax, l in zip(axes, range(4)):
        for i, c in zip(idx, [BLUE, ORANGE, GREEN]):
            hs = d_[i]
            if l == 0:
                a, b = xs, hs[0][ntr:, 0]
            elif l < 3:
                a, b = hs[l - 1][ntr:, 0], hs[l][ntr:, 0]
            else:
                a, b = hs[2][ntr:, 0], d["mu"][i]
            o = np.argsort(a)
            ax.plot(a[o], b[o], ".-", color=c, ms=2.5, lw=0.8)
        ax.set_xlabel(["input", "layer 1", "layer 2", "layer 3"][l])
        ax.set_ylabel(["layer 1", "layer 2", "layer 3", "output"][l])
        panel_label(ax, "abcd"[l], "upper left")
    fig.tight_layout()
    return savefig(fig, CH, "fig18-sup3", out)


def fig_sup18_4(out=None):
    """2-layer RBF deep GP on the step function for hidden widths 1, 16, 256 (HMC) and infinity (exact limit kernel)."""
    R = _dgp_runs()
    x_tr, y, xs = R["x_tr"], R["y"], R["x_te"]
    ntr = len(x_tr)
    ws = [1, 16, 256]
    fig, axes = plt.subplots(2, 4, figsize=(10.4, 4.6))
    for c, w in enumerate(ws):
        d = R["w%d" % w]
        mean = d["mu"].mean(0)
        sd = np.sqrt(d["var"].mean(0) + d["mu"].var(0))
        axes[0, c].plot(xs, mean, color=BLUE)
        axes[0, c].fill_between(xs, mean - 2 * sd, mean + 2 * sd, color=RED, alpha=0.25, lw=0)
        axes[0, c].plot(x_tr, y, "o", color=RED, ms=3)
        axes[0, c].set_title("width = %d" % w, fontsize=9.5)
        Kb = dgp_avg_cov(d["hidden"], w, ntr)
        axes[1, c].imshow(Kb, origin="lower", extent=[-2, 2, -2, 2], cmap="viridis", vmin=0.0, vmax=1.0)
    mu, var = gp_predict(lambda A, B: k_lim(A, B), x_tr, y, xs, 0.01)
    mu, sd = np_(mu), np.sqrt(np_(var))
    axes[0, 3].plot(xs, mu, color=BLUE)
    axes[0, 3].fill_between(xs, mu - 2 * sd, mu + 2 * sd, color=RED, alpha=0.25, lw=0)
    axes[0, 3].plot(x_tr, y, "o", color=RED, ms=3)
    axes[0, 3].set_title("width = infinity", fontsize=9.5)
    axes[1, 3].imshow(np_(k_lim(xs, xs)), origin="lower", extent=[-2, 2, -2, 2], cmap="viridis", vmin=0.0, vmax=1.0)
    for ax in axes[1]:
        ax.set_xlabel("$x$")
    axes[0, 0].set_ylabel("$f_2(f_1(x))$")
    axes[1, 0].set_ylabel("average posterior kernel")
    fig.tight_layout()
    print("   HMC acceptances:", [round(R["w%d" % w]["acc"], 2) for w in ws])
    return savefig(fig, CH, "fig18-sup4", out)


# =========================================================================== extra figures for the "Filling the gap" boxes
def rff_features(X, ell, D, rng):
    """Random Fourier features (18.42)-(18.43): phi(x) = sqrt(1/D) [sin(Z^T x), cos(Z^T x)], Z = G / ell."""
    X = np.asarray(X, float).reshape(len(X), -1)
    Z = rng.standard_normal((X.shape[1], D)) / ell
    A = X @ Z
    return np.concatenate([np.sin(A), np.cos(A)], 1) / np.sqrt(D)


def fig_S18_1(out=None):
    """Random Fourier features approximate the SE kernel with error of order 1/sqrt(D)."""
    rng = np.random.default_rng(31)
    x = np.linspace(-4, 4, 161)
    ref = np.exp(-0.5 * x ** 2)
    fig, axes = plt.subplots(1, 2, figsize=(8.0, 3.0))
    for D, c in zip([5, 50, 500], [ORANGE, GREEN, BLUE]):
        F = rff_features(np.concatenate([[0.0], x]), 1.0, D, rng)
        axes[0].plot(x, F[1:] @ F[0], color=c, lw=1.2, label="D = %d" % D)
    axes[0].plot(x, ref, "k--", lw=1.4, label="exact SE")
    axes[0].set_xlabel("$r$")
    axes[0].legend(fontsize=8)
    panel_label(axes[0], "a", "upper left")
    Ds = np.array([4, 8, 16, 32, 64, 128, 256, 512, 1024])
    rms, mx = [], []
    for D in Ds:
        e1, e2 = [], []
        for rep in range(40):
            F = rff_features(np.concatenate([[0.0], x]), 1.0, int(D), rng)
            err = F[1:] @ F[0] - ref
            e1.append(np.sqrt(np.mean(err ** 2)))
            e2.append(np.abs(err).max())
        rms.append(np.mean(e1))
        mx.append(np.mean(e2))
    axes[1].loglog(Ds, rms, "o-", color=BLUE, label="rms error over $r$")
    axes[1].loglog(Ds, mx, "s-", color=RED, label="maximum error")
    axes[1].loglog(Ds, 0.5 / np.sqrt(Ds), "k:", label=r"$\propto 1/\sqrt{D}$")
    axes[1].set_xlabel("number of frequencies $D$")
    axes[1].legend(fontsize=8)
    panel_label(axes[1], "b", "lower left")
    fig.tight_layout()
    return savefig(fig, CH, "fig18-S1", out)


def sparse_comparison_data(seed=32):
    rng = np.random.default_rng(seed)
    x = np.sort(np.concatenate([rng.uniform(-3, -0.8, 50), rng.uniform(1.4, 3, 40)]))
    y = np.sin(2 * x) + 0.3 * x + 0.2 * rng.standard_normal(len(x))
    return x, y


def fig_S18_2(out=None):
    """SOR, DTC, FITC and the variational (VFE) approximation against the exact GP, with 6 inducing points."""
    x, y = sparse_comparison_data()
    xs = np.linspace(-4, 4, 200)
    kern = np_kernel("se", ell=0.8, var=1.0)
    s2 = 0.04
    Z = np.array([-2.8, -2.0, -1.2, 1.6, 2.2, 2.9])
    ex = gp_predict(lambda A, B: k_se(A, B, 0.8, 1.0), x, y, xs, s2)
    fig, axes = plt.subplots(2, 3, figsize=(9.6, 5.0), sharex=True, sharey=True)
    panels = [("exact GP", np_(ex[0]), np_(ex[1]), None)]
    for m in ["sor", "dtc", "fitc", "vfe"]:
        r = sparse_gp(kern, x, y, Z, xs, s2, m)
        panels.append((m.upper(), r["mu"], np.maximum(r["var"], 0), r["obj"]))
    for ax, (nm, mu, v, obj), lab in zip(axes.ravel(), panels, "abcde"):
        ax.plot(x, y, "k.", ms=3)
        ax.plot(xs, mu, color=BLUE)
        band(ax, xs, mu, np.sqrt(v), BLUE, 2)
        ax.plot(Z, -2.2 * np.ones_like(Z), "r^", ms=5)
        ax.set_title(nm + ("" if obj is None else ", objective %.1f" % obj), fontsize=9.5)
        panel_label(ax, lab, "upper left")
    # variance comparison panel
    ax = axes[1, 2]
    for nm, mu, v, obj in panels:
        ax.plot(xs, np.sqrt(v), label=nm)
    ax.set_title("latent standard deviation", fontsize=9.5)
    ax.legend(fontsize=7)
    panel_label(ax, "f", "upper left")
    ax.set_xlabel("$x$")
    fig.tight_layout()
    return savefig(fig, CH, "fig18-S2", out)


def erf_kernel_mc(xt, xpt, Sig, H, rng):
    """Empirical kernel (1/H) sum_j erf(u_j . x) erf(u_j . x') of a width-H network with random first layer."""
    U = rng.standard_normal((H, xt.shape[1])) @ np.linalg.cholesky(Sig).T
    return special.erf(xt @ U.T) @ special.erf(xpt @ U.T).T / H


def relu_nngp(xt, xpt, Sig):
    """E[relu(u.x) relu(u.x')] for u ~ N(0, Sig): (1/2pi) |x||x'| (sin theta + (pi - theta) cos theta) in the Sig norm."""
    a = np.sqrt(np.einsum("ij,jk,ik->i", xt, Sig, xt))
    b = np.sqrt(np.einsum("ij,jk,ik->i", xpt, Sig, xpt))
    c = np.clip((xt @ Sig @ xpt.T) / (a[:, None] * b[None, :]), -1, 1)
    th = np.arccos(c)
    return a[:, None] * b[None, :] * (np.sin(th) + (np.pi - th) * c) / (2 * np.pi)


def fig_S18_3(out=None):
    """Finite-width networks against their NN-GP kernels (erf and ReLU units)."""
    rng = np.random.default_rng(33)
    xs = np.linspace(-3, 3, 7)
    xt = np.stack([np.ones_like(xs), xs], 1)
    Sig = np.diag([1.0, 4.0])
    exact_erf = (2 / np.pi) * np.arcsin(2 * xt @ Sig @ xt.T / np.sqrt(np.outer(1 + 2 * np.einsum("ij,jk,ik->i", xt, Sig, xt), 1 + 2 * np.einsum("ij,jk,ik->i", xt, Sig, xt))))
    exact_relu = relu_nngp(xt, xt, Sig)
    Hs = np.array([4, 16, 64, 256, 1024, 4096, 16384])
    e_erf, e_relu = [], []
    for H in Hs:
        a, b = [], []
        for rep in range(30):
            U = rng.standard_normal((H, 2)) @ np.linalg.cholesky(Sig).T
            A = xt @ U.T
            a.append(np.abs(special.erf(A) @ special.erf(A).T / H - exact_erf).max())
            R = np.maximum(A, 0)
            b.append(np.abs(R @ R.T / H - exact_relu).max())
        e_erf.append(np.mean(a))
        e_relu.append(np.mean(b))
    fig, axes = plt.subplots(1, 2, figsize=(8.0, 3.0))
    big = erf_kernel_mc(xt, xt, Sig, 200000, rng)
    iu = np.triu_indices(len(xs))
    axes[0].plot(exact_erf[iu], big[iu], "o", color=BLUE, ms=4)
    lim = [exact_erf.min() - 0.05, exact_erf.max() + 0.05]
    axes[0].plot(lim, lim, "k--", lw=1)
    axes[0].set_xlabel("closed-form arcsine kernel")
    axes[0].set_ylabel("Monte Carlo, $10^5$ units")
    panel_label(axes[0], "a", "upper left")
    axes[1].loglog(Hs, e_erf, "o-", color=BLUE, label="erf")
    axes[1].loglog(Hs, e_relu, "s-", color=ORANGE, label="ReLU")
    axes[1].loglog(Hs, 1.2 / np.sqrt(Hs), "k:", label=r"$\propto H^{-1/2}$")
    axes[1].set_xlabel("hidden width $H$")
    axes[1].set_ylabel("max kernel error")
    axes[1].legend(fontsize=8)
    panel_label(axes[1], "b", "lower left")
    fig.tight_layout()
    return savefig(fig, CH, "fig18-S3", out)


def ntk_experiment(m, seed=0, steps=400, n=8):
    """One-hidden-layer ReLU net in NTK parametrisation f(x) = m^{-1/2} sum a_j relu(w_j x + b_j), trained by gradient descent
    on the squared error. Returns the relative drift of the tangent kernel, and the deviation of the trained function from the
    linearised (kernel) dynamics, on a test grid."""
    rng = np.random.default_rng(seed)
    x = np.linspace(-1, 1, n)
    y = np.sin(3 * x)
    xt = np.linspace(-1.2, 1.2, 25)
    a, w, b = rng.standard_normal(m), rng.standard_normal(m), rng.standard_normal(m)

    def feats(a, w, b, xx):
        z = np.outer(xx, w) + b[None, :]
        act = (z > 0).astype(float)
        J = np.concatenate([np.maximum(z, 0), act * a[None, :] * xx[:, None], act * a[None, :]], 1) / np.sqrt(m)
        f = (np.maximum(z, 0) @ a) / np.sqrt(m)
        return f, J
    f0, J0 = feats(a, w, b, x)
    f0t, J0t = feats(a, w, b, xt)
    T0 = J0 @ J0.T
    eta = 1.0 / np.linalg.eigvalsh(T0).max()
    # finite-width gradient descent
    th = np.concatenate([a, w, b])
    flin, flint = f0.copy(), f0t.copy()
    for s in range(steps):
        aa, ww, bb = th[:m], th[m:2 * m], th[2 * m:]
        f, J = feats(aa, ww, bb, x)
        th = th - eta * J.T @ (f - y)
        # linearised dynamics
        r = flin - y
        flint = flint - eta * J0t @ (J0.T @ r)
        flin = flin - eta * T0 @ r
    aa, ww, bb = th[:m], th[m:2 * m], th[2 * m:]
    f, J = feats(aa, ww, bb, x)
    ft, Jt = feats(aa, ww, bb, xt)
    drift = np.linalg.norm(J @ J.T - T0) / np.linalg.norm(T0)
    dev = np.abs(ft - flint).max()
    return drift, dev, np.abs(f - y).max(), np.abs(ft - f0t).max()


def fig_S18_4(out=None):
    """The neural tangent kernel stays constant as the width grows, and gradient descent follows the linearised dynamics."""
    ms = np.array([8, 32, 128, 512, 2048, 8192])
    drift, dev, train_err, change = [], [], [], []
    for m in ms:
        d, v, te, ch = zip(*[ntk_experiment(int(m), seed=s) for s in range(6)])
        drift.append(np.mean(d))
        dev.append(np.mean(v))
        train_err.append(np.mean(te))
        change.append(np.mean(ch))
    fig, axes = plt.subplots(1, 2, figsize=(8.0, 3.0))
    axes[0].loglog(ms, drift, "o-", color=BLUE, label="tangent kernel drift")
    axes[0].loglog(ms, 3 * ms ** -0.5, "k:", label=r"$\propto m^{-1/2}$")
    axes[0].set_xlabel("width $m$")
    axes[0].legend(fontsize=8)
    panel_label(axes[0], "a", "lower left")
    axes[1].loglog(ms, dev, "s-", color=ORANGE, label="finite net vs linearised")
    axes[1].loglog(ms, change, "o-", color=GREEN, label="change from initial function")
    axes[1].loglog(ms, 3 * ms ** -0.5, "k:", label=r"$\propto m^{-1/2}$")
    axes[1].set_xlabel("width $m$")
    axes[1].legend(fontsize=8)
    panel_label(axes[1], "b", "lower left")
    fig.tight_layout()
    print("   NTK drift", np.round(drift, 4), "deviation", np.round(dev, 4), "train err", np.round(train_err, 4))
    return savefig(fig, CH, "fig18-S4", out)


# Matern state space models (Supplement 18.2)
def matern_ssm(nu, ell, var):
    """F, L, H, q, P_inf of the SDE whose stationary covariance is the Matern(nu) kernel, nu = 1/2, 3/2, 5/2."""
    lam = np.sqrt(2 * nu) / ell
    if nu == 0.5:
        F, L, H = np.array([[-lam]]), np.array([[1.0]]), np.array([[1.0]])
        q = 2 * lam * var
    elif nu == 1.5:
        F = np.array([[0, 1], [-lam ** 2, -2 * lam]])
        L, H = np.array([[0.0], [1.0]]), np.array([[1.0, 0.0]])
        q = 4 * lam ** 3 * var
    elif nu == 2.5:
        F = np.array([[0, 1, 0], [0, 0, 1], [-lam ** 3, -3 * lam ** 2, -3 * lam]])
        L, H = np.array([[0.0], [0.0], [1.0]]), np.array([[1.0, 0.0, 0.0]])
        q = 16 * lam ** 5 * var / 3
    P = sla.solve_continuous_lyapunov(F, -(L * q) @ L.T)
    return F, L, H, q, P


def ssm_covariance(nu, ell, var, tau):
    F, L, H, q, P = matern_ssm(nu, ell, var)
    return np.array([(H @ sla.expm(F * t) @ P @ H.T)[0, 0] for t in tau])


def kalman_smoother_gp(x, y, nu, ell, var, s2):
    """Posterior mean of f at the (sorted) inputs x by Kalman filtering and RTS smoothing of the Matern SSM: O(N)."""
    F, L, H, q, P0 = matern_ssm(nu, ell, var)
    d = F.shape[0]
    n = len(x)
    m = np.zeros(d)
    P = P0.copy()
    ms, Ps, mp, Pp, As = [], [], [], [], []
    prev = x[0]
    for k in range(n):
        dt = x[k] - prev
        A = sla.expm(F * dt) if k > 0 else np.eye(d)
        Q = P0 - A @ P0 @ A.T
        m_ = A @ m
        P_ = A @ P @ A.T + Q
        S = (H @ P_ @ H.T)[0, 0] + s2
        Kg = (P_ @ H.T)[:, 0] / S
        m = m_ + Kg * (y[k] - (H @ m_)[0])
        P = P_ - np.outer(Kg, (H @ P_))
        ms.append(m)
        Ps.append(P)
        mp.append(m_)
        Pp.append(P_)
        As.append(A)
        prev = x[k]
    sm = [None] * n
    Psm = [None] * n
    sm[-1], Psm[-1] = ms[-1], Ps[-1]
    for k in range(n - 2, -1, -1):
        G = Ps[k] @ As[k + 1].T @ np.linalg.inv(Pp[k + 1])
        sm[k] = ms[k] + G @ (sm[k + 1] - mp[k + 1])
        Psm[k] = Ps[k] + G @ (Psm[k + 1] - Pp[k + 1]) @ G.T
    return np.array([(H @ s)[0] for s in sm]), np.array([(H @ P @ H.T)[0, 0] for P in Psm])


def fig_S18_5(out=None):
    """A Matern GP as a linear-Gaussian state space model: covariance functions agree, the Kalman smoother equals GP regression, and costs scale as N against N^3."""
    import time
    tau = np.linspace(0, 6, 200)
    fig, axes = plt.subplots(1, 3, figsize=(10.2, 3.0))
    for nu, c in zip([0.5, 1.5, 2.5], [BLUE, ORANGE, GREEN]):
        ex = np_(k_matern(tau, np.array([0.0]), nu, 1.5, 1.0))[:, 0]
        ss = ssm_covariance(nu, 1.5, 1.0, tau)
        axes[0].plot(tau, ex, color=c, lw=2.2, label=r"$\nu=%s$" % {0.5: "1/2", 1.5: "3/2", 2.5: "5/2"}[nu])
        axes[0].plot(tau, ss, "k--", lw=0.9)
    axes[0].set_xlabel(r"$\tau$")
    axes[0].set_ylabel(r"$k(\tau)$ (dashed: state space model)")
    axes[0].legend(fontsize=8)
    panel_label(axes[0], "a", "upper right")
    rng = np.random.default_rng(34)
    x = np.sort(rng.uniform(0, 10, 120))
    y = np.sin(1.3 * x) + 0.3 * rng.standard_normal(len(x))
    ms, vs = kalman_smoother_gp(x, y, 1.5, 1.5, 1.0, 0.09)
    mu, var = gp_predict(lambda A, B: k_matern(A, B, 1.5, 1.5, 1.0), x, y, x, 0.09)
    axes[1].plot(x, y, "k.", ms=4)
    axes[1].plot(x, ms, color=BLUE, lw=1.8, label="Kalman smoother")
    axes[1].plot(x, np_(mu), color=RED, ls="--", lw=1.2, label="GP regression")
    axes[1].set_xlabel("$x$")
    axes[1].legend(fontsize=8)
    panel_label(axes[1], "b", "upper right")
    Ns = [100, 200, 400, 800, 1600, 3200]
    tg, tk = [], []
    for n in Ns:
        xx = np.sort(rng.uniform(0, n / 10, n))
        yy = np.sin(xx) + 0.3 * rng.standard_normal(n)
        t0 = time.time()
        K = np_(k_matern(xx, xx, 1.5, 1.5, 1.0)) + 0.09 * np.eye(n)
        sla.cho_solve(sla.cho_factor(K), yy)
        tg.append(time.time() - t0)
        t0 = time.time()
        kalman_smoother_gp(xx, yy, 1.5, 1.5, 1.0, 0.09)
        tk.append(time.time() - t0)
    axes[2].loglog(Ns, tg, "o-", color=RED, label="GP, Cholesky")
    axes[2].loglog(Ns, tk, "s-", color=BLUE, label="Kalman smoother")
    axes[2].set_xlabel("$N$")
    axes[2].set_ylabel("seconds")
    axes[2].legend(fontsize=8)
    panel_label(axes[2], "c", "upper left")
    fig.tight_layout()
    print("   max |Kalman - GP| = %.2e; times GP %s Kalman %s" % (np.abs(ms - np_(mu)).max(), np.round(tg, 3), np.round(tk, 3)))
    return savefig(fig, CH, "fig18-S5", out)


# =========================================================================== data for the interactive demonstrations
def export_demo_data(out=None):
    """Write the small JSON files the browser demonstrations read (data/ch18-sparse.json, data/ch18-maunaloa.json)."""
    x, y = sparse_comparison_data()
    kern = np_kernel("se", ell=0.8, var=1.0)
    s2 = 0.04
    xg = np.linspace(-4, 4, 41)
    mu_e, v_e = gp_predict(lambda A, B: k_se(A, B, 0.8, 1.0), x, y, xg, s2)
    ref = {"logml": log_marglik(k_se(x, x, 0.8, 1.0), y, s2).item(), "table": {}}
    for m in (3, 6, 12, 25):
        Z = np.linspace(-3, 3, m)
        for meth in ("sor", "dtc", "fitc", "vfe"):
            r = sparse_gp(kern, x, y, Z, xg, s2, meth)
            ref["table"]["%s_%d" % (meth, m)] = {"obj": float(r["obj"]), "rmse_mean": float(np.sqrt(np.mean((r["mu"] - np_(mu_e)) ** 2))),
                                                  "mean_sd": float(np.sqrt(np.maximum(r["var"], 0)).mean())}
    ref["exact_mean_sd"] = float(np.sqrt(np_(v_e)).mean())
    json.dump({"x": [round(float(v), 6) for v in x], "y": [round(float(v), 6) for v in y], "ell": 0.8, "var": 1.0, "noise_var": s2, "ref": ref},
              open(os.path.join(DATA_OUT, "ch18-sparse.json"), "w"))
    # Mauna Loa
    t, yy, ntr, m, th, v = mauna_loa_fit()
    thp = np.exp(th[:11])
    sn2 = float(np.exp(2 * th[11])) + 1e-6
    xx = t - 1958.0
    ref2 = {}
    subsets = {"full": [1, 1, 1, 1], "no_K1": [0, 1, 1, 1], "no_K2": [1, 0, 1, 1], "no_K3": [1, 1, 0, 1], "no_K4": [1, 1, 1, 0], "K1_only": [1, 0, 0, 0]}

    def kmask(X, Y, mask):
        r2 = sqdist(X, Y)
        r = torch.sqrt(torch.clamp(r2, min=1e-30))
        p = torch.tensor(thp)
        ks = [p[0] ** 2 * torch.exp(-r2 / (2 * p[1] ** 2)),
              p[2] ** 2 * torch.exp(-r2 / (2 * p[3] ** 2) - p[5] * torch.sin(np.pi * r / p[4]) ** 2),
              p[6] ** 2 * (1 + r2 / (2 * p[8] * p[7] ** 2)) ** (-p[8]),
              p[9] ** 2 * torch.exp(-r2 / (2 * p[10] ** 2))]
        return sum(a * k_ for a, k_ in zip(mask, ks))
    for nm, mask in subsets.items():
        lml = log_marglik(kmask(xx[:ntr], xx[:ntr], mask), yy[:ntr] - m, sn2).item()
        mu, var = gp_predict(lambda A, B: kmask(A, B, mask), xx[:ntr], yy[:ntr] - m, xx[ntr:], sn2)
        ref2[nm] = {"logml": lml, "rmse": float(np.sqrt(np.mean((np_(mu) + m - yy[ntr:]) ** 2))),
                    "mean_at_last": float(np_(mu)[-1] + m)}
    json.dump({"t": [round(float(a), 4) for a in t], "y": [round(float(a), 3) for a in yy], "theta": [float(a) for a in thp], "noise": float(np.exp(th[11])),
               "ntrain": int(ntr), "ref": ref2}, open(os.path.join(DATA_OUT, "ch18-maunaloa.json"), "w"))
    print("   wrote data/ch18-sparse.json and data/ch18-maunaloa.json; Mauna Loa full-model log ML %.3f, test RMSE %.3f" % (ref2["full"]["logml"], ref2["full"]["rmse"]))


# =========================================================================== driver
FIGURES = {
    "18.2": fig_18_2, "18.3": fig_18_3, "18.4": fig_18_4, "18.5": fig_18_5, "18.6": fig_18_6, "18.7": fig_18_7,
    "18.8": fig_18_8, "18.9": fig_18_9, "18.10": fig_18_10, "18.11": fig_18_11, "18.14": fig_18_14,
    "18.15": fig_18_15, "18.16": fig_18_16, "18.17": fig_18_17, "18.18": fig_18_18, "18.20": fig_18_20,
    "18.22": fig_18_22, "18.23": fig_18_23, "18.24": fig_18_24, "18.26": fig_18_26, "18.28": fig_18_28,
    "18.29": fig_18_29, "sup18.2": fig_sup18_2, "sup18.3": fig_sup18_3, "sup18.4": fig_sup18_4,
    "data": export_demo_data, "S18.1": fig_S18_1, "S18.2": fig_S18_2, "S18.3": fig_S18_3, "S18.4": fig_S18_4, "S18.5": fig_S18_5,
}

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