"""Murphy (2023), Chapter 8: Gaussian filtering and smoothing.

Companion code for Chapter 8 of K. P. Murphy, Probabilistic Machine Learning: Advanced Topics (MIT Press,
2023; December 2025 draft), pp. 359-400, and its supplement (Supplementary Chapter 8, "Inference for
state-space models", pp. 85-98), written from scratch with numpy, scipy and matplotlib, to be read next to
the lecture notes (../ch08-gaussian-filtering-smoothing.html).

Methods implemented (the notes use these functions by name)
* Linear-Gaussian building blocks (Algorithm 8.1): lin_gauss_joint, gauss_condition.
* Linear-Gaussian SSMs (Section 8.2): kalman_filter (Algorithm 8.2, with inputs and offsets), rts_smoother
  (8.64)-(8.69) with the lag-one cross covariances, ffbs_sample (8.85)-(8.88), fixed_lag_smoother,
  information_filter (8.89)-(8.98), information_smoother (8.110)-(8.115), two_filter_smoother (a backward
  information filter combined with the forward filter), and joint_gaussian_lgssm, which builds the whole
  joint Gaussian of (z_{1:T}, y_{1:T}) so that every recursion can be compared with brute-force conditioning.
* Local linearisation (Section 8.3): taylor_transform (Algorithm 8.3), ekf (the iterated EKF of Algorithm 8.4
  with n_iter > 1), eks (extended RTS smoother).
* Sigma points (Sections 8.4-8.5): sigma_points (Algorithm 8.5), unscented_joint (Algorithm 8.6), ukf, uks,
  gauss_hermite_points, cubature_points, moments_by_points (generic Gaussian filtering moments), slr
  (statistical linear regression (8.163)), enkf (Section 8.5.4).
* Assumed density filtering (Section 8.6): collapse_mixture (8.203)-(8.208), adf_logistic (8.209)-(8.223,
  corrected), plus the offline comparisons laplace_logistic and mh_logistic.
* Grid-based filtering and smoothing (Section 8.7.1): grid_filter_smoother.
* Supplement: rls (S8.7)-(S8.14), kf_unknown_noise (S8.15)-(S8.31), predictive_coding_step (S8.32)-(S8.46),
  the pendulum model (S8.56)-(S8.60), eekf_logistic and the natural-gradient form (S8.61)-(S8.113).
* Mulberry, a port of the seeded generator used by the browser demonstrations, so that the pages and this
  module draw exactly the same random numbers.

Data. Everything is simulated (seeds fixed in the code); the book's own simulations use other random numbers,
so curves agree in shape, not draw by draw. Figure 8.2 and Supplementary Figure 8.1 use the demonstration
generator, so the Kalman demonstration reproduces them exactly. The outlier at t = 20 of Figure 8.13 is
placed there on purpose (a stand-in for the book's draw). The 2d logistic-regression data of Figures
8.10-8.12 and Supplementary Figures 8.3-8.4 are simulated (60 points).

Figures. Reproduced here: 8.2, 8.4, 8.5, 8.10, 8.11, 8.12, 8.13, 8.14, and Supplementary Figures 8.1,
8.2 (b, c), 8.3 and 8.4. Skipped, with the reason:
  8.1, 8.9  graphical-model diagrams (nothing computed);
  8.3       a schematic of the kinds of inference (filtering, smoothing, fixed lag, prediction);
  8.6, 8.7, 8.8  schematics (the predict-update-project cycle, a taxonomy, the GPB2 and IMM diagrams);
  S8.2(a)   a drawing of the pendulum.
Extra figures for the notes:
  x8.a  mean squared error of fixed-lag smoothing against the lag;
  x8.b  error of the Taylor, unscented and Gauss-Hermite moments against the prior spread.
Run `python3 ch08_gaussian_filtering_smoothing.py --list`, `python3 ch08_gaussian_filtering_smoothing.py`
(all figures, about a minute) or `--fig 8.2`. Files go to ../img/ch08/; the data used by the browser
demonstrations go to ../data/ch08-*.json.
"""
import json
import os
import sys

os.environ.setdefault("OPENBLAS_NUM_THREADS", "1")

import numpy as np  # noqa: E402
from scipy import stats  # noqa: E402

sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
import common  # noqa: E402
from common import plt, savefig, RED, BLUE, GREEN, ORANGE, GREY, ellipse_xy, sigmoid  # noqa: E402

CH = 8
HERE = os.path.dirname(os.path.abspath(__file__))
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
CHI2_95_2D = float(np.sqrt(stats.chi2.ppf(0.95, 2)))   # 2.4477: radius of the 95% ellipse in 2d


# =========================================================================== seeded generator of the demos
class Mulberry:
    """Port of DK.rng (mulberry32 + Box-Muller with a spare), so Python and the browser draw the same numbers."""
    M = 0xFFFFFFFF

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

    @staticmethod
    def _imul(x, y):
        return (x * y) & 0xFFFFFFFF

    def u(self):
        M = self.M
        self.a = (self.a + 0x6D2B79F5) & M
        a = self.a
        t = self._imul(a ^ (a >> 15), 1 | a)
        t = ((t + self._imul(t ^ (t >> 7), 61 | t)) & M) ^ t
        return ((t ^ (t >> 14)) & M) / 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 = np.sqrt(-2.0 * np.log(self._pos()))
        th = 2.0 * np.pi * self.u()
        self.spare = r * np.sin(th)
        return r * np.cos(th)


# =========================================================================== Algorithm 8.1
def lin_gauss_joint(mu, Sigma, A, b, Omega):
    """Moments of y = A z + b + noise, z ~ N(mu, Sigma), noise ~ N(0, Omega): (mean, S, C=cov(z, y))."""
    m = A @ mu + b
    C = Sigma @ A.T
    S = A @ C + Omega
    return m, S, C


def gauss_condition(mu, Sigma, m, S, C, y):
    """Condition the joint N([mu; m], [[Sigma, C], [C^T, S]]) on y; also return log N(y | m, S)."""
    K = np.linalg.solve(S.T, C.T).T          # solve K S = C instead of inverting S
    e = y - m
    mu_post = mu + K @ e
    Sig_post = Sigma - K @ S @ K.T
    Sig_post = 0.5 * (Sig_post + Sig_post.T)
    L = np.linalg.cholesky(S)
    z = np.linalg.solve(L, e)
    ll = -0.5 * (len(y) * np.log(2 * np.pi) + 2 * np.log(np.diag(L)).sum() + z @ z)
    return mu_post, Sig_post, ll


def _seq(M, T):
    """Accept a fixed matrix or a length-T sequence of matrices."""
    M = np.asarray(M, dtype=float)
    return M if M.ndim == 3 else np.repeat(M[None], T, axis=0)


# =========================================================================== Section 8.2: linear-Gaussian SSMs
def kalman_filter(F, Q, H, R, ys, mu0, Sigma0, Bu=None, Du=None):
    """Algorithm 8.2 from N(mu0, Sigma0) at time 0. Bu[t], Du[t] are the offsets B_t u_t + b_t and D_t u_t + d_t.

    Returns dict with filtered (mf, Pf), predicted (mp, Pp), innovations, S, gains and the log likelihood.
    """
    ys = np.atleast_2d(ys)
    T, Ny = ys.shape
    Nz = len(mu0)
    F, Q, H, R = _seq(F, T), _seq(Q, T), _seq(H, T), _seq(R, T)
    Bu = np.zeros((T, Nz)) if Bu is None else np.asarray(Bu, float)
    Du = np.zeros((T, Ny)) if Du is None else np.asarray(Du, float)
    mf, Pf, mp, Pp = (np.zeros((T, Nz)), np.zeros((T, Nz, Nz)), np.zeros((T, Nz)), np.zeros((T, Nz, Nz)))
    lls, Ss, Ks, es = np.zeros(T), np.zeros((T, Ny, Ny)), np.zeros((T, Nz, Ny)), np.zeros((T, Ny))
    mu, P = np.asarray(mu0, float), np.asarray(Sigma0, float)
    for t in range(T):
        mu, P, _ = lin_gauss_joint(mu, P, F[t], Bu[t], Q[t])           # predict (8.23)-(8.24)
        mp[t], Pp[t] = mu, P
        yhat, S, C = lin_gauss_joint(mu, P, H[t], Du[t], R[t])         # (8.26)-(8.27)
        Ks[t] = np.linalg.solve(S.T, C.T).T
        es[t], Ss[t] = ys[t] - yhat, S
        mu, P, lls[t] = gauss_condition(mu, P, yhat, S, C, ys[t])     # (8.28)-(8.31)
        mf[t], Pf[t] = mu, P
    return dict(mf=mf, Pf=Pf, mp=mp, Pp=Pp, ll=lls.sum(), lls=lls, S=Ss, K=Ks, e=es)


def rts_smoother(F, Q, kf):
    """RTS smoother (8.64)-(8.69). Uses F_{t+1}, Q_{t+1} for the step t -> t+1 (0-based F[t+1]).

    Returns smoothed means ms, covariances Ps, backward gains J and lag-one cross covariances
    Pcross[t] = Cov[z_t, z_{t+1} | y_{1:T}] = J_t P_{t+1|T}.
    """
    mf, Pf, mp, Pp = kf["mf"], kf["Pf"], kf["mp"], kf["Pp"]
    T, Nz = mf.shape
    F = _seq(F, T)
    ms, Ps = mf.copy(), Pf.copy()
    J = np.zeros((T, Nz, Nz))
    Pcross = np.zeros((T - 1, Nz, Nz))
    for t in range(T - 2, -1, -1):
        J[t] = np.linalg.solve(Pp[t + 1].T, (Pf[t] @ F[t + 1].T).T).T    # (8.67)
        ms[t] = mf[t] + J[t] @ (ms[t + 1] - mp[t + 1])                    # (8.68)
        Ps[t] = Pf[t] + J[t] @ (Ps[t + 1] - Pp[t + 1]) @ J[t].T           # (8.69)
        Ps[t] = 0.5 * (Ps[t] + Ps[t].T)
        Pcross[t] = J[t] @ Ps[t + 1]
    return dict(ms=ms, Ps=Ps, J=J, Pcross=Pcross)


def ffbs_sample(F, Q, kf, rng, n=1):
    """Forwards filtering, backwards sampling (8.85)-(8.88): n draws of z_{1:T} from p(z_{1:T} | y_{1:T})."""
    mf, Pf, mp, Pp = kf["mf"], kf["Pf"], kf["mp"], kf["Pp"]
    T, Nz = mf.shape
    F = _seq(F, T)
    out = np.zeros((n, T, Nz))
    out[:, -1] = rng.multivariate_normal(mf[-1], Pf[-1], size=n)
    for t in range(T - 2, -1, -1):
        J = np.linalg.solve(Pp[t + 1].T, (Pf[t] @ F[t + 1].T).T).T
        Sig = Pf[t] - J @ Pp[t + 1] @ J.T                                   # (8.87)
        Sig = 0.5 * (Sig + Sig.T)
        L = np.linalg.cholesky(Sig + 1e-12 * np.eye(Nz))
        mean = mf[t] + (out[:, t + 1] - (F[t + 1] @ mf[t])) @ J.T           # (8.86)
        out[:, t] = mean + rng.standard_normal((n, Nz)) @ L.T
    return out


def fixed_lag_smoother(F, Q, H, R, ys, mu0, Sigma0, lag):
    """Estimate of z_s given y_{1:min(s+lag, T)} for every s (lag 0 = filtering, lag >= T-1 = smoothing)."""
    T = len(ys)
    Nz = len(mu0)
    kf = kalman_filter(F, Q, H, R, ys, mu0, Sigma0)
    m, P = np.zeros((T, Nz)), np.zeros((T, Nz, Nz))
    for s in range(T):
        e = min(s + lag, T - 1)
        sub = {k: kf[k][:e + 1] for k in ("mf", "Pf", "mp", "Pp")}
        sm = rts_smoother(F, Q, sub) if e > s else dict(ms=sub["mf"], Ps=sub["Pf"])
        m[s], P[s] = sm["ms"][s], sm["Ps"][s]
    return m, P


def information_filter(F, Q, H, R, ys, mu0, Sigma0, Bu=None, Du=None):
    """Information form (8.89)-(8.98): returns eta_{t|t}, Lambda_{t|t}, eta_{t|t-1}, Lambda_{t|t-1}."""
    ys = np.atleast_2d(ys)
    T, Ny = ys.shape
    Nz = len(mu0)
    F, Q, H, R = _seq(F, T), _seq(Q, T), _seq(H, T), _seq(R, T)
    Bu = np.zeros((T, Nz)) if Bu is None else np.asarray(Bu, float)
    Du = np.zeros((T, Ny)) if Du is None else np.asarray(Du, float)
    Lam = np.linalg.inv(Sigma0)
    eta = Lam @ mu0
    ef, Lf, ep, Lp = np.zeros((T, Nz)), np.zeros((T, Nz, Nz)), np.zeros((T, Nz)), np.zeros((T, Nz, Nz))
    for t in range(T):
        Qi = np.linalg.inv(Q[t])
        M = Lam + F[t].T @ Qi @ F[t]                                         # (8.90)
        J = Qi @ F[t] @ np.linalg.inv(M)                                    # (8.91)
        Lam = Qi - J @ M @ J.T                                              # (8.94)
        eta = J @ eta + Lam @ Bu[t]                                         # (8.95)
        ep[t], Lp[t] = eta, Lam
        Ri = np.linalg.inv(R[t])
        Lam = Lam + H[t].T @ Ri @ H[t]                                      # (8.97)
        eta = eta + H[t].T @ Ri @ (ys[t] - Du[t])                           # (8.98)
        ef[t], Lf[t] = eta, Lam
    return dict(ef=ef, Lf=Lf, ep=ep, Lp=Lp)


def information_smoother(F, Q, inf, index_shift=1, Bu=None):
    """Information-form smoother (8.110)-(8.115). index_shift=1 uses F_{t+1}, Q_{t+1} for the step t -> t+1
    (the consistent indexing); index_shift=0 uses F_t, Q_t as printed in (8.111)-(8.114).
    Bu (the offsets B_t u_t + b_t) adds the terms that (8.115) omits when the dynamics have an offset:
    eta_{t|T} = eta_{t|t} - F^T Q^-1 b + L (Q^-1 b + eta_{t+1|T} - eta_{t+1|t})."""
    ef, Lf, ep, Lp = inf["ef"], inf["Lf"], inf["ep"], inf["Lp"]
    T, Nz = ef.shape
    F, Q = _seq(F, T), _seq(Q, T)
    Bu = np.zeros((T, Nz)) if Bu is None else np.asarray(Bu, float)
    es, Ls = ef.copy(), Lf.copy()
    for t in range(T - 2, -1, -1):
        k = t + index_shift
        Qi = np.linalg.inv(Q[k])
        U = Qi + Ls[t + 1] - Lp[t + 1]                                      # (8.111)
        L = F[k].T @ Qi @ np.linalg.inv(U)                                  # (8.112)
        Ls[t] = Lf[t] + F[k].T @ Qi @ F[k] - L @ U @ L.T                    # (8.114)
        b = Bu[k]
        es[t] = ef[t] - F[k].T @ Qi @ b + L @ (Qi @ b + es[t + 1] - ep[t + 1])   # (8.115) with the offset terms
    return dict(es=es, Ls=Ls)


def two_filter_smoother(F, Q, H, R, ys, mu0, Sigma0):
    """Two-filter smoothing: forward filter times the backward likelihood p(y_{t+1:T} | z_t), the latter
    carried in information form (precision Lb, linear term eb), started from Lb = 0 (no evidence) at t = T."""
    ys = np.atleast_2d(ys)
    T = len(ys)
    Nz = len(mu0)
    F, Q, H, R = _seq(F, T), _seq(Q, T), _seq(H, T), _seq(R, T)
    kf = kalman_filter(F, Q, H, R, ys, mu0, Sigma0)
    Lb, eb = np.zeros((Nz, Nz)), np.zeros(Nz)     # message p(y_{t+1:T} | z_t) at t = T: constant
    ms, Ps = np.zeros((T, Nz)), np.zeros((T, Nz, Nz))
    for t in range(T - 1, -1, -1):
        Pi = np.linalg.inv(kf["Pf"][t])
        Lpost = Pi + Lb
        Ps[t] = np.linalg.inv(Lpost)
        ms[t] = Ps[t] @ (Pi @ kf["mf"][t] + eb)
        if t == 0:
            break
        # include y_t: p(y_{t:T} | z_t) has precision Lb + H^T R^-1 H and linear term eb + H^T R^-1 y_t
        Ri = np.linalg.inv(R[t])
        Lt = Lb + H[t].T @ Ri @ H[t]
        et = eb + H[t].T @ Ri @ ys[t]
        # propagate through z_t = F z_{t-1} + q: integrate z_t out against N(z_t | F z_{t-1}, Q)
        Qi = np.linalg.inv(Q[t])
        G = np.linalg.inv(Qi + Lt)
        Lb = F[t].T @ (Qi - Qi @ G @ Qi) @ F[t]
        eb = F[t].T @ Qi @ G @ et
    return dict(ms=ms, Ps=Ps)


def joint_gaussian_lgssm(F, Q, H, R, mu0, Sigma0, T):
    """Mean and covariance of the stacked vector (z_1..z_T, y_1..y_T) of a time-invariant LG-SSM."""
    Nz, Ny = len(mu0), H.shape[0]
    mz = np.zeros((T, Nz))
    Pz = [[None] * T for _ in range(T)]
    m, P = mu0, Sigma0
    marg = []
    for t in range(T):
        m = F @ m
        P = F @ P @ F.T + Q
        mz[t] = m
        marg.append(P)
    for s in range(T):
        for t in range(T):
            if t >= s:
                Pz[s][t] = marg[s] @ np.linalg.matrix_power(F, t - s).T
            else:
                Pz[s][t] = np.linalg.matrix_power(F, s - t) @ marg[t]
    Szz = np.block(Pz)
    Hb = np.kron(np.eye(T), H)
    Szy = Szz @ Hb.T
    Syy = Hb @ Szz @ Hb.T + np.kron(np.eye(T), R)
    mean = np.concatenate([mz.ravel(), (mz @ H.T).ravel()])
    cov = np.block([[Szz, Szy], [Szy.T, Syy]])
    return mean, cov


# =========================================================================== Section 8.3: linearisation
def num_jac(g, x, eps=1e-6):
    x = np.asarray(x, float)
    g0 = np.atleast_1d(g(x))
    Jm = np.zeros((len(g0), len(x)))
    for j in range(len(x)):
        d = np.zeros(len(x))
        d[j] = eps
        Jm[:, j] = (np.atleast_1d(g(x + d)) - np.atleast_1d(g(x - d))) / (2 * eps)
    return Jm


def taylor_transform(mu, Sigma, g, Omega, jac=None):
    """Algorithm 8.3: (yhat, S, C) of the first-order Taylor (linearised) Gaussian joint."""
    G = jac(mu) if jac is not None else num_jac(g, mu)
    yhat = np.atleast_1d(g(mu))
    C = Sigma @ G.T
    S = G @ C + Omega
    return yhat, S, C


def ekf(f, h, Q, R, ys, mu0, Sigma0, Fjac=None, Hjac=None, n_iter=1):
    """Extended Kalman filter; n_iter > 1 is the iterated EKF of Algorithm 8.4 (relinearise h at mu_{t|t}).

    The dynamics are linearised at the previous filtered mean mu_{t-1|t-1}."""
    ys = np.atleast_2d(ys)
    T = len(ys)
    Nz = len(mu0)
    mf, Pf, mp, Pp = np.zeros((T, Nz)), np.zeros((T, Nz, Nz)), np.zeros((T, Nz)), np.zeros((T, Nz, Nz))
    Fs = np.zeros((T, Nz, Nz))
    mu, P, ll = np.asarray(mu0, float), np.asarray(Sigma0, float), 0.0
    for t in range(T):
        Fs[t] = Fjac(mu) if Fjac is not None else num_jac(f, mu)
        mu_p, P_p, _ = taylor_transform(mu, P, f, Q, jac=Fjac)
        mp[t], Pp[t] = mu_p, P_p
        m_it = mu_p
        for _ in range(n_iter):
            Hm = Hjac(m_it) if Hjac is not None else num_jac(h, m_it)
            # linearise h at m_it: h(z) ~ h(m_it) + H (z - m_it), so the predicted y is h(m_it) + H (mu_p - m_it)
            yhat = np.atleast_1d(h(m_it)) + Hm @ (mu_p - m_it)
            C = P_p @ Hm.T
            S = Hm @ C + R
            m_new, P_new, l = gauss_condition(mu_p, P_p, yhat, S, C, ys[t])
            m_it = m_new
        mu, P = m_new, P_new
        ll += l
        mf[t], Pf[t] = mu, P
    return dict(mf=mf, Pf=Pf, mp=mp, Pp=Pp, F=Fs, ll=ll)


def eks(kf):
    """Extended RTS smoother: the RTS recursion with F_{t+1} = Jacobian of f at mu_{t|t}."""
    mf, Pf, mp, Pp, Fs = kf["mf"], kf["Pf"], kf["mp"], kf["Pp"], kf["F"]
    T, Nz = mf.shape
    ms, Ps = mf.copy(), Pf.copy()
    for t in range(T - 2, -1, -1):
        J = np.linalg.solve(Pp[t + 1].T, (Pf[t] @ Fs[t + 1].T).T).T
        ms[t] = mf[t] + J @ (ms[t + 1] - mp[t + 1])
        Ps[t] = Pf[t] + J @ (Ps[t + 1] - Pp[t + 1]) @ J.T
    return dict(ms=ms, Ps=Ps)


# =========================================================================== Sections 8.4-8.5: sigma points
def sigma_points(mu, Sigma, alpha=1.0, beta=0.0, kappa=None):
    """Algorithm 8.5: 2n+1 unscented sigma points (rows) and mean/covariance weights."""
    mu = np.asarray(mu, float)
    n = len(mu)
    if kappa is None:
        kappa = 3.0 - n
    lam = alpha ** 2 * (n + kappa) - n
    L = np.linalg.cholesky(Sigma)
    c = np.sqrt(n + lam)
    X = np.vstack([mu, mu + c * L.T, mu - c * L.T])
    wm = np.full(2 * n + 1, 1.0 / (2 * (n + lam)))
    wc = wm.copy()
    wm[0] = lam / (n + lam)
    wc[0] = lam / (n + lam) + (1 - alpha ** 2 + beta)
    return X, wm, wc


def cubature_points(mu, Sigma):
    """Spherical cubature rule: 2n points mu +- sqrt(n) L e_i with equal weights 1/(2n)."""
    mu = np.asarray(mu, float)
    n = len(mu)
    L = np.linalg.cholesky(Sigma)
    X = np.vstack([mu + np.sqrt(n) * L.T, mu - np.sqrt(n) * L.T])
    w = np.full(2 * n, 1.0 / (2 * n))
    return X, w, w


def gauss_hermite_points(mu, Sigma, order=5):
    """Tensor-product Gauss-Hermite rule with order^n points (probabilists' Hermite polynomials)."""
    mu = np.asarray(mu, float)
    n = len(mu)
    x1, w1 = np.polynomial.hermite_e.hermegauss(order)
    w1 = w1 / w1.sum()
    grids = np.meshgrid(*([x1] * n), indexing="ij")
    U = np.stack([g.ravel() for g in grids], axis=1)
    Wg = np.meshgrid(*([w1] * n), indexing="ij")
    W = np.prod(np.stack([g.ravel() for g in Wg], axis=1), axis=1)
    L = np.linalg.cholesky(Sigma)
    X = mu + U @ L.T
    return X, W, W


def moments_by_points(mu, Sigma, g, Omega, X, wm, wc):
    """Generic Gaussian-filter moments (8.157)-(8.159) by a point rule: (yhat, S, C)."""
    Y = np.array([np.atleast_1d(g(x)) for x in X])
    yhat = wm @ Y
    dY = Y - yhat
    dX = X - mu
    S = (wc[:, None] * dY).T @ dY + Omega
    C = (wc[:, None] * dX).T @ dY
    return yhat, S, C


def unscented_joint(mu, Sigma, g, Omega, alpha=1.0, beta=0.0, kappa=None):
    """Algorithm 8.6 (with the undefined mu_U of lines 5-6 read as yhat)."""
    X, wm, wc = sigma_points(mu, Sigma, alpha, beta, kappa)
    return moments_by_points(mu, Sigma, g, Omega, X, wm, wc)


def _point_rule(kind, mu, Sigma, **kw):
    if kind == "ut":
        return sigma_points(mu, Sigma, kw.get("alpha", 1.0), kw.get("beta", 0.0), kw.get("kappa"))
    if kind == "ckf":
        return cubature_points(mu, Sigma)
    if kind == "gh":
        return gauss_hermite_points(mu, Sigma, kw.get("order", 5))
    raise ValueError(kind)


def sigma_point_filter(f, h, Q, R, ys, mu0, Sigma0, kind="ut", **kw):
    """UKF (kind='ut', (8.152)-(8.154)), cubature KF ('ckf') or Gauss-Hermite KF ('gh').

    Also stores the predicted cross covariances D_t = Cov[z_{t-1}, z_t | y_{1:t-1}] for the smoother."""
    ys = np.atleast_2d(ys)
    T = len(ys)
    Nz = len(mu0)
    mf, Pf, mp, Pp, D = (np.zeros((T, Nz)), np.zeros((T, Nz, Nz)), np.zeros((T, Nz)), np.zeros((T, Nz, Nz)),
                         np.zeros((T, Nz, Nz)))
    mu, P, ll = np.asarray(mu0, float), np.asarray(Sigma0, float), 0.0
    for t in range(T):
        X, wm, wc = _point_rule(kind, mu, P, **kw)
        mu_p, P_p, D[t] = moments_by_points(mu, P, f, Q, X, wm, wc)
        mp[t], Pp[t] = mu_p, P_p
        X, wm, wc = _point_rule(kind, mu_p, P_p, **kw)
        yhat, S, C = moments_by_points(mu_p, P_p, h, R, X, wm, wc)
        mu, P, l = gauss_condition(mu_p, P_p, yhat, S, C, ys[t])
        ll += l
        mf[t], Pf[t] = mu, P
    return dict(mf=mf, Pf=Pf, mp=mp, Pp=Pp, D=D, ll=ll)


def ukf(f, h, Q, R, ys, mu0, Sigma0, alpha=1.0, beta=0.0, kappa=None):
    return sigma_point_filter(f, h, Q, R, ys, mu0, Sigma0, "ut", alpha=alpha, beta=beta, kappa=kappa)


def uks(kf):
    """Unscented RTS smoother: J_t = D_{t+1} P_{t+1|t}^{-1} with D the sigma-point cross covariance."""
    mf, Pf, mp, Pp, D = kf["mf"], kf["Pf"], kf["mp"], kf["Pp"], kf["D"]
    T, Nz = mf.shape
    ms, Ps = mf.copy(), Pf.copy()
    for t in range(T - 2, -1, -1):
        J = np.linalg.solve(Pp[t + 1].T, D[t + 1].T).T
        ms[t] = mf[t] + J @ (ms[t + 1] - mp[t + 1])
        Ps[t] = Pf[t] + J @ (Ps[t + 1] - Pp[t + 1]) @ J.T
    return dict(ms=ms, Ps=Ps)


def slr(mu, Sigma, yhat, S, C):
    """Statistical linear regression (8.163): A = C^T Sigma^-1, b = yhat - A mu, Omega = S - A Sigma A^T."""
    A = np.linalg.solve(Sigma, C).T
    b = yhat - A @ mu
    Om = S - A @ Sigma @ A.T
    return A, b, Om


def enkf(F, Q, H, R, ys, mu0, Sigma0, Ns, rng, deterministic_obs=False):
    """Ensemble Kalman filter (Section 8.5.4) for a linear model, with perturbed observations
    (8.191)-(8.194) or, with deterministic_obs=True, the variance-reduced gain using H Z and R."""
    ys = np.atleast_2d(ys)
    T = len(ys)
    Nz, Ny = len(mu0), ys.shape[1]
    Z = rng.multivariate_normal(mu0, Sigma0, size=Ns).T
    means, covs = np.zeros((T, Nz)), np.zeros((T, Nz, Nz))
    LQ, LR = np.linalg.cholesky(Q), np.linalg.cholesky(R)
    for t in range(T):
        Z = F @ Z + LQ @ rng.standard_normal((Nz, Ns))
        Zt = Z - Z.mean(1, keepdims=True)
        if deterministic_obs:
            O = H @ Zt
            Ct = Zt @ O.T / (Ns - 1)
            St = O @ O.T / (Ns - 1) + R
            Y = H @ Z + LR @ rng.standard_normal((Ny, Ns))
        else:
            Y = H @ Z + LR @ rng.standard_normal((Ny, Ns))
            Yt = Y - Y.mean(1, keepdims=True)
            Ct = Zt @ Yt.T / (Ns - 1)
            St = Yt @ Yt.T / (Ns - 1)
        K = np.linalg.solve(St.T, Ct.T).T
        Z = Z + K @ (ys[t][:, None] - Y)
        means[t] = Z.mean(1)
        Zc = Z - means[t][:, None]
        covs[t] = Zc @ Zc.T / (Ns - 1)
    return means, covs


# =========================================================================== Section 8.6: ADF
def collapse_mixture(pis, mus, Sigmas):
    """Moment matching of a Gaussian mixture by one Gaussian (8.203)-(8.204)."""
    pis = np.asarray(pis, float) / np.sum(pis)
    mu = np.einsum("k,ki->i", pis, mus)
    d = mus - mu
    Sig = np.einsum("k,kij->ij", pis, Sigmas) + np.einsum("k,ki,kj->ij", pis, d, d)
    return mu, Sig


U_GRID = np.linspace(-8.0, 8.0, 801)          # standardised quadrature grid, shared with the browser demo
U_W = np.full(801, U_GRID[1] - U_GRID[0])
U_W[0] *= 0.5
U_W[-1] *= 0.5
U_PHI = np.exp(-0.5 * U_GRID ** 2) / np.sqrt(2 * np.pi)


def tilted_moments_bernoulli(y, m, v):
    """Mean and variance of p(eta) proportional to Ber(y | sigmoid(eta)) N(eta | m, v) (trapezoid rule on +-8 sd)."""
    eta = m + np.sqrt(v) * U_GRID
    p = sigmoid(eta)
    lik = p if y == 1 else 1.0 - p
    w = U_W * U_PHI * lik
    Z = w.sum()
    mean = (w * eta).sum() / Z
    var = (w * (eta - mean) ** 2).sum() / Z
    return mean, var, Z


def adf_logistic(X, y, mu0, tau0, q=0.0):
    """ADF for online logistic regression with a diagonal Gaussian (Section 8.6.3, with (8.223) corrected:
    a_i = x_i tau_i / sum_j x_j^2 tau_j). Returns the means and variances after every step."""
    N, D = X.shape
    mu, tau = np.array(mu0, float), np.array(tau0, float)
    Mu, Tau = np.zeros((N, D)), np.zeros((N, D))
    for t in range(N):
        tau = tau + q                                         # predict: random-walk drift
        x = X[t]
        m = x @ mu                                            # (8.213)
        v = (x ** 2) @ tau                                    # (8.214)
        mt, vt, _ = tilted_moments_bernoulli(y[t], m, v)      # (8.215)-(8.218)
        a = x * tau / v                                       # (8.223), corrected
        mu = mu + a * (mt - m)                                # (8.221)
        tau = tau + a ** 2 * (vt - v)                         # (8.222)
        Mu[t], Tau[t] = mu, tau
    return Mu, Tau


def eekf_logistic(X, y, mu0, Sigma0, q=0.0):
    """Exponential-family EKF (Supplement 8.3) for Bernoulli observations with yhat = sigmoid(x^T z)."""
    N, D = X.shape
    mu, P = np.array(mu0, float), np.array(Sigma0, float)
    Mu, Ps = np.zeros((N, D)), np.zeros((N, D, D))
    for t in range(N):
        P = P + q * np.eye(D)
        x = X[t]
        p = sigmoid(x @ mu)                                   # (S8.67)
        Hm = (p * (1 - p)) * x[None, :]                       # (S8.70)
        Rt = p * (1 - p)                                      # (S8.69)
        S = Hm @ P @ Hm.T + Rt
        K = P @ Hm.T / S                                      # (S8.71)
        mu = mu + (K * (y[t] - p)).ravel()                    # (S8.73)
        P = (np.eye(D) - K @ Hm) @ P                          # (S8.72)
        P = 0.5 * (P + P.T)
        Mu[t], Ps[t] = mu, P
    return Mu, Ps


def laplace_logistic(X, y, v0, n_iter=50):
    """MAP by Newton's method under the prior N(0, v0 I), and the Laplace covariance (inverse Hessian)."""
    N, D = X.shape
    w = np.zeros(D)
    for _ in range(n_iter):
        p = sigmoid(X @ w)
        g = X.T @ (p - y) + w / v0
        Hs = X.T @ (X * (p * (1 - p))[:, None]) + np.eye(D) / v0
        step = np.linalg.solve(Hs, g)
        w = w - step
        if np.abs(step).max() < 1e-13:
            break
    p = sigmoid(X @ w)
    Hs = X.T @ (X * (p * (1 - p))[:, None]) + np.eye(D) / v0
    return w, np.linalg.inv(Hs)


def mh_logistic(X, y, v0, n=20000, burn=2000, seed=0):
    """Random-walk Metropolis for the logistic-regression posterior, proposal scaled by the Laplace covariance."""
    rng = np.random.default_rng(seed)
    w, C = laplace_logistic(X, y, v0)

    def logp(w):
        a = X @ w
        return float(y @ a - np.logaddexp(0, a).sum() - 0.5 * w @ w / v0)
    L = np.linalg.cholesky(C) * (2.38 / np.sqrt(len(w)))
    cur, lp = w.copy(), logp(w)
    out, acc = np.zeros((n, len(w))), 0
    for i in range(n + burn):
        prop = cur + L @ rng.standard_normal(len(w))
        lq = logp(prop)
        if np.log(rng.random()) < lq - lp:
            cur, lp = prop, lq
            if i >= burn:
                acc += 1
        if i >= burn:
            out[i - burn] = cur
    return out, acc / n


def probit_predictive(m, v):
    """E[sigmoid(eta)] for eta ~ N(m, v) by the probit approximation sigmoid(m / sqrt(1 + pi v / 8))."""
    return sigmoid(m / np.sqrt(1 + np.pi * v / 8))


# =========================================================================== Section 8.7.1: grid filter
def grid_filter_smoother(ys, grid, trans_pdf, obs_pdf, prior_pdf):
    """HMM filter and smoother on a 1d grid (point-mass approximation) for t = 0..T-1 with an observation at
    every step. trans_pdf(z_new - z_old), obs_pdf(y - z), prior_pdf(z0). Returns predictive, filtered, smoothed
    probability vectors (each row sums to one) and the log likelihood (up to the grid spacing)."""
    G = len(grid)
    A = trans_pdf(grid[None, :] - grid[:, None])          # A[i, j] proportional to p(z_new = j | z_old = i)
    A = A / A.sum(1, keepdims=True)
    T = len(ys)
    pred, filt = np.zeros((T, G)), np.zeros((T, G))
    p = prior_pdf(grid)
    p = p / p.sum()
    ll = 0.0
    for t in range(T):
        if t > 0:
            p = filt[t - 1] @ A
        pred[t] = p
        post = p * obs_pdf(ys[t] - grid)
        Z = post.sum()
        ll += np.log(Z)
        filt[t] = post / Z
    smooth = filt.copy()
    for t in range(T - 2, -1, -1):
        ratio = np.where(pred[t + 1] > 0, smooth[t + 1] / np.maximum(pred[t + 1], 1e-300), 0.0)
        smooth[t] = filt[t] * (A @ ratio)
        smooth[t] /= smooth[t].sum()
    return pred, filt, smooth, ll


# =========================================================================== supplement
def rls(U, y, mu0, Sigma0, sigma2):
    """Recursive least squares (S8.7)-(S8.10): the Kalman filter with F = I, Q = 0, H_t = u_t^T."""
    mu, P = np.array(mu0, float), np.array(Sigma0, float)
    for u, yt in zip(U, y):
        s = u @ P @ u + sigma2                     # (S8.7)
        k = P @ u / s                              # (S8.8)
        mu = mu + k * (yt - u @ mu)                # (S8.9)
        P = P - np.outer(k, k) * s                 # (S8.10) in the form (S8.12)
    return mu, P


def kf_unknown_noise(F, Qs, hs, ys, mu0, Sigma0s, nu0, tau0):
    """Kalman filter with unknown observation variance V (West and Harrison), (S8.15)-(S8.31) with the
    corrections F Sigma F^T in (S8.22) and mu_t = mu_{t|t-1} + k e in (S8.26).
    Returns the final (mu, Sigma*, nu, tau) and the one-step predictive log densities."""
    mu, P, nu, tau = np.array(mu0, float), np.array(Sigma0s, float), float(nu0), float(tau0)
    lps = []
    for h, yt in zip(hs, ys):
        mp = F @ mu                                # (S8.21)
        Pp = F @ P @ F.T + Qs                      # (S8.22)
        e = yt - h @ mp                            # (S8.23)
        s = h @ Pp @ h + 1.0                       # (S8.24)
        lps.append(stats.t.logpdf(yt, df=nu, loc=h @ mp, scale=np.sqrt(tau * s)))   # (S8.31)
        k = Pp @ h / s                             # (S8.25)
        mu = mp + k * e                            # (S8.26)
        P = Pp - np.outer(k, k) * s                # (S8.27)
        nu_new = nu + 1                            # (S8.28)
        tau = (nu * tau + e ** 2 / s) / nu_new     # (S8.29)
        nu = nu_new
    return mu, P, nu, tau, np.array(lps)


def pendulum_model(dt=0.0125, g=9.8, qc=1.0):
    """Discretised noisy pendulum (S8.58)-(S8.60): f, Jacobian, Q, and the sin-angle observation."""
    f = lambda z: np.array([z[0] + z[1] * dt, z[1] - g * np.sin(z[0]) * dt])
    Fj = lambda z: np.array([[1.0, dt], [-g * np.cos(z[0]) * dt, 1.0]])
    h = lambda z: np.array([np.sin(z[0])])
    Hj = lambda z: np.array([[np.cos(z[0]), 0.0]])
    Q = qc * np.array([[dt ** 3 / 3, dt ** 2 / 2], [dt ** 2 / 2, dt]])
    return f, Fj, h, Hj, Q


# =========================================================================== shared simulated problems
def cv_model(dt=1.0):
    """Constant-velocity model (8.20)-(8.21)."""
    F = np.array([[1, 0, dt, 0], [0, 1, 0, dt], [0, 0, 1, 0], [0, 0, 0, 1]], float)
    H = np.array([[1, 0, 0, 0], [0, 1, 0, 0]], float)
    return F, H


SPIRAL_F = np.array([[0.1, 1.1, 1.0, 0], [-1, 1, 0, 1.0], [0, 0, 0.1, 0], [0, 0, 0, 0.1]])
# demo / figure settings (kept identical in kalman-smoother-demo.html)
TRACK = dict(dyn="cv", q=0.1, r=1.0, s0=0.1, T=20, seed=40, mu0=[8.0, 10.0, 1.0, 0.0])
SPIRAL = dict(dyn="spiral", q=0.001, r=5.0, s0=0.1, T=15, seed=310, mu0=[8.0, 10.0, 1.0, 0.0])


def simulate_lgssm_mulberry(p):
    """Draw z_0 ~ N(mu0, s0 I), z_t = F z_{t-1} + N(0, q I), y_t = H z_t + N(0, r I), t = 1..T, with the
    demonstration generator: 4 normals for z_0, then for each t 4 normals (dynamics) and 2 (observation)."""
    F = cv_model()[0] if p["dyn"] == "cv" else SPIRAL_F
    H = cv_model()[1]
    g = Mulberry(p["seed"])
    z = np.array(p["mu0"], float) + np.sqrt(p["s0"]) * np.array([g.norm() for _ in range(4)])
    Z, Y = [], []
    for _ in range(p["T"]):
        z = F @ z + np.sqrt(p["q"]) * np.array([g.norm() for _ in range(4)])
        y = H @ z + np.sqrt(p["r"]) * np.array([g.norm() for _ in range(2)])
        Z.append(z)
        Y.append(y)
    return F, H, np.array(Z), np.array(Y)


def lgssm_run(p, lag=2):
    """Filter, smoother and fixed-lag results for a demo setting; position MSEs as in Figure 8.2."""
    F, H, Z, Y = simulate_lgssm_mulberry(p)
    Q, R = p["q"] * np.eye(4), p["r"] * np.eye(2)
    mu0, S0 = np.array(p["mu0"], float), p["s0"] * np.eye(4)
    kf = kalman_filter(F, Q, H, R, Y, mu0, S0)
    sm = rts_smoother(F, Q, kf)
    ml, Pl = fixed_lag_smoother(F, Q, H, R, Y, mu0, S0, lag)
    mse = lambda M: float(np.mean(np.sum((M[:, :2] - Z[:, :2]) ** 2, axis=1)))
    return dict(F=F, H=H, Z=Z, Y=Y, kf=kf, sm=sm, ml=ml, Pl=Pl, mse_f=mse(kf["mf"]), mse_s=mse(sm["ms"]),
                mse_l=mse(ml), mse_obs=mse(np.hstack([Y, np.zeros_like(Y)])), ll=kf["ll"],
                trf=float(np.mean([np.trace(P[:2, :2]) for P in kf["Pf"]])),
                trs=float(np.mean([np.trace(P[:2, :2]) for P in sm["Ps"]])))


def kalman_demo_reference():
    """Numbers shown by kalman-smoother-demo.html for each preset."""
    presets = [dict(TRACK, lag=2), dict(TRACK, r=10.0, lag=2), dict(TRACK, lag=5, q=0.5),
               dict(SPIRAL, lag=2), dict(TRACK, q=0.001, lag=2)]
    out = []
    for p in presets:
        r = lgssm_run(p, p["lag"])
        out.append(dict(mse_f=r["mse_f"], mse_s=r["mse_s"], mse_l=r["mse_l"], ll=r["ll"], trf=r["trf"],
                        trs=r["trs"], y0=r["Y"][0].tolist(), zT=r["Z"][-1].tolist()))
    return out


# spiral (8.147)
def spiral_f(dt):
    return (lambda z: np.array([z[0] + dt * np.sin(z[1]), z[1] + dt * np.cos(z[0])]),
            lambda z: np.array([[1.0, dt * np.cos(z[1])], [-dt * np.sin(z[0]), 1.0]]))


def spiral_problem(T=100, dt=0.4, q=0.001, r=1.0, seed=314):
    f, Fj = spiral_f(dt)
    rng = np.random.default_rng(seed)
    z = np.array([1.5, 0.0])
    Z, Y = [], []
    for _ in range(T):
        z = f(z) + np.sqrt(q) * rng.standard_normal(2)
        Z.append(z)
        Y.append(z + np.sqrt(r) * rng.standard_normal(2))
    return f, Fj, np.array(Z), np.array(Y), q * np.eye(2), r * np.eye(2)


# transformation of Figure 8.5 (and sigma-point-transform-demo.html)
TF_MU = np.array([0.0, 0.0])
TF_SIG = np.array([[0.6, -0.55], [-0.55, 1.6]])
TF_A = 0.35


def tf_g(x, a=TF_A):
    """A smooth nonlinear map R^2 -> R^2: quadratic bend plus a sinusoidal shear."""
    x = np.asarray(x, float)
    return np.array([x[0] + a * x[1] ** 2 - a, x[1] + a * np.sin(2 * x[0])])


def tf_jac(x, a=TF_A):
    return np.array([[1.0, 2 * a * x[1]], [2 * a * np.cos(2 * x[0]), 1.0]])


def tf_methods(mu, Sig, a=TF_A, alpha=1.0, beta=0.0, kappa=1.0, order=5):
    Z = np.zeros((2, 2))
    g = lambda x: tf_g(x, a)
    out = {"taylor": taylor_transform(mu, Sig, g, Z, jac=lambda x: tf_jac(x, a))}
    X, wm, wc = sigma_points(mu, Sig, alpha, beta, kappa)
    out["ut"] = moments_by_points(mu, Sig, g, Z, X, wm, wc)
    X, wm, wc = gauss_hermite_points(mu, Sig, order)
    out["gh"] = moments_by_points(mu, Sig, g, Z, X, wm, wc)
    X, wm, wc = gauss_hermite_points(mu, Sig, 30)
    out["exact"] = moments_by_points(mu, Sig, g, Z, X, wm, wc)
    return out


def kl_gauss(m0, S0, m1, S1):
    """KL(N(m0, S0) || N(m1, S1))."""
    k = len(m0)
    S1i = np.linalg.inv(S1)
    d = m1 - m0
    return 0.5 * (np.trace(S1i @ S0) + d @ S1i @ d - k + np.linalg.slogdet(S1)[1] - np.linalg.slogdet(S0)[1])


def transform_demo_reference():
    """Numbers shown by sigma-point-transform-demo.html (presets: scale s of the covariance, a, kappa, order)."""
    presets = [dict(s=1.0, a=0.35, kappa=1.0, order=5), dict(s=0.1, a=0.35, kappa=1.0, order=5),
               dict(s=2.5, a=0.35, kappa=1.0, order=5), dict(s=1.0, a=0.35, kappa=0.0, order=3),
               dict(s=1.0, a=0.8, kappa=1.0, order=7)]
    out = []
    for p in presets:
        r = tf_methods(TF_MU, p["s"] * TF_SIG, p["a"], 1.0, 0.0, p["kappa"], p["order"])
        me, Se = r["exact"][0], r["exact"][1]
        row = dict(exact_m=me.tolist(), exact_S=Se.ravel().tolist())
        for k in ("taylor", "ut", "gh"):
            row[k + "_m"] = r[k][0].tolist()
            row[k + "_S"] = r[k][1].ravel().tolist()
            row[k + "_kl"] = float(kl_gauss(me, Se, r[k][0], r[k][1]))
        out.append(row)
    return out


# logistic-regression data of Figures 8.10-8.12, S8.3, S8.4
LOGREG_V0 = 2.0


def logreg_data(N=60, seed=11):
    rng = np.random.default_rng(seed)
    X2 = rng.standard_normal((N, 2))
    w_true = np.array([0.3, 0.8, -0.6])
    X = np.hstack([np.ones((N, 1)), X2])
    y = (rng.random(N) < sigmoid(X @ w_true)).astype(float)
    return X, y


def logreg_reference():
    X, y = logreg_data()
    D = X.shape[1]
    out = {}
    for name, perm in (("order1", np.arange(len(y))), ("order2", np.random.default_rng(5).permutation(len(y)))):
        Mu, Tau = adf_logistic(X[perm], y[perm], np.zeros(D), np.full(D, LOGREG_V0))
        Me, Pe = eekf_logistic(X[perm], y[perm], np.zeros(D), LOGREG_V0 * np.eye(D))
        out[name] = dict(perm=perm.tolist(), adf_mu=Mu[-1].tolist(), adf_tau=Tau[-1].tolist(),
                         eekf_mu=Me[-1].tolist(), eekf_var=np.diag(Pe[-1]).tolist())
    w, C = laplace_logistic(X, y, LOGREG_V0)
    out["laplace_w"], out["laplace_var"] = w.tolist(), np.diag(C).tolist()
    Mu, Tau = adf_logistic(X, y, np.zeros(D), np.full(D, LOGREG_V0), q=0.01)
    out["adf_drift_mu"] = Mu[-1].tolist()
    Mu, Tau = adf_logistic(X, y, np.zeros(D), np.full(D, 0.1))
    out["adf_v01_mu"] = Mu[-1].tolist()
    return out


# =========================================================================== figures
def _ellipses(ax, M, P, color, nsd=CHI2_95_2D, lw=0.8):
    for m, S in zip(M, P):
        ex, ey = ellipse_xy(m[:2], S[:2, :2], nsd)
        ax.plot(ex, ey, color=color, lw=lw, alpha=0.8)


def fig_8_2(out=None):
    """Kalman filtering and smoothing for 2d tracking with the constant-velocity model."""
    r = lgssm_run(TRACK, 2)
    Z, Y = r["Z"], r["Y"]
    fig, axes = plt.subplots(1, 3, figsize=(11.5, 3.5))
    ax = axes[0]
    ax.plot(Z[:, 0], Z[:, 1], "s-", color=BLUE, ms=4, label="true state")
    ax.plot(Y[:, 0], Y[:, 1], "o", color=GREEN, mfc="none", ms=6, label="observations")
    ax.legend(loc="upper left")
    ax.set_title("(a) data")
    for ax, key_m, key_P, lab, mse in ((axes[1], r["kf"]["mf"], r["kf"]["Pf"], "filtered means", r["mse_f"]),
                                       (axes[2], r["sm"]["ms"], r["sm"]["Ps"], "smoothed means", r["mse_s"])):
        ax.plot(Y[:, 0], Y[:, 1], "o", color=GREEN, mfc="none", ms=6, label="observed")
        ax.plot(Z[:, 0], Z[:, 1], "s-", color=BLUE, ms=3, lw=1, label="true state")
        ax.plot(key_m[:, 0], key_m[:, 1], "-", color=RED, lw=1.8, label=lab)
        _ellipses(ax, key_m, key_P, "k")
        ax.legend(loc="upper left")
        ax.set_title("(%s) %s, MSE %.2f" % ("b" if "filt" in lab else "c", lab.split()[0], mse))
    allp = np.vstack([Z[:, :2], Y])
    lo, hi = allp.min(0) - 2.5, allp.max(0) + 2.5
    for ax in axes:
        ax.set_xlim(lo[0], hi[0])
        ax.set_ylim(lo[1], hi[1] + 3)
    savefig(fig, CH, "fig8-2", out)


def fig_S8_1(out=None):
    """Kalman filtering and smoothing for the spiral dynamics of Supplementary (8.1)."""
    r = lgssm_run(SPIRAL, 2)
    Z, Y = r["Z"], r["Y"]
    fig, axes = plt.subplots(1, 3, figsize=(11.5, 3.6))
    axes[0].plot(Z[:, 0], Z[:, 1], "-", color=BLUE, label="true state")
    axes[0].plot(Y[:, 0], Y[:, 1], "x", color=GREEN, ms=6, label="observations")
    axes[0].set_title("(a) data")
    axes[0].legend(loc="upper left", fontsize=8)
    for ax, M, P, lab, mse in ((axes[1], r["kf"]["mf"], r["kf"]["Pf"], "filtered", r["mse_f"]),
                               (axes[2], r["sm"]["ms"], r["sm"]["Ps"], "smoothed", r["mse_s"])):
        ax.plot(Z[:, 0], Z[:, 1], "-", color=BLUE, label="true state")
        ax.plot(M[:, 0], M[:, 1], "-", color=RED, label=lab)
        _ellipses(ax, M, P, RED, lw=0.6)
        ax.legend(loc="upper left", fontsize=8)
        ax.set_title("(%s) %s, MSE %.2f" % ("b" if lab == "filtered" else "c", lab, mse))
    for ax in axes:
        ax.set_aspect("equal", adjustable="datalim")
    savefig(fig, CH, "figS8-1", out)


def fig_8_4(out=None):
    """EKF and UKF on the spiral of (8.147)."""
    f, Fj, Z, Y, Q, R = spiral_problem()
    mu0, S0 = np.array([1.5, 0.0]), 0.1 * np.eye(2)
    h = lambda z: z
    ek = ekf(f, h, Q, R, Y, mu0, S0, Fjac=Fj, Hjac=lambda z: np.eye(2))
    uk = ukf(f, h, Q, R, Y, mu0, S0, alpha=1.0, beta=0.0, kappa=2.0)
    rm = lambda M: float(np.sqrt(np.mean(np.sum((M - Z) ** 2, 1))))
    fig, axes = plt.subplots(1, 3, figsize=(11.5, 3.6), sharex=True, sharey=True)
    titles = ["(a) noisy observations of the hidden trajectory",
              "(b) EKF, RMSE %.3f" % rm(ek["mf"]), "(c) UKF, RMSE %.3f" % rm(uk["mf"])]
    for k, ax in enumerate(axes):
        ax.plot(Z[:, 0], Z[:, 1], "-", color="k", lw=1.2, label="true states")
        ax.plot(Y[:, 0], Y[:, 1], ".", color=GREY, ms=3, label="observations")
        if k:
            M = ek["mf"] if k == 1 else uk["mf"]
            ax.plot(M[:, 0], M[:, 1], "-", color=RED if k == 1 else BLUE, lw=1.2,
                    label="EKF estimate" if k == 1 else "UKF estimate")
        ax.set_title(titles[k], fontsize=9.5)
        ax.legend(loc="lower left", fontsize=8)
    savefig(fig, CH, "fig8-4", out)
    return rm(ek["mf"]), rm(uk["mf"])


def fig_8_5(out=None):
    """Monte Carlo, Taylor, unscented and Gauss-Hermite approximations of the law of g(x)."""
    rng = np.random.default_rng(0)
    Xs = rng.multivariate_normal(TF_MU, TF_SIG, size=1500)
    Ys = np.array([tf_g(x) for x in Xs])
    r = tf_methods(TF_MU, TF_SIG)
    mc_m, mc_S = Ys.mean(0), np.cov(Ys.T)
    fig, axes = plt.subplots(3, 2, figsize=(7.2, 10.2))
    lim = (-4, 4)

    def ell(ax, m, S, **kw):
        ex, ey = ellipse_xy(m, S, 2.0)
        ax.plot(ex, ey, **kw)
        ax.plot(*m, "o", mfc="none", **{k: v for k, v in kw.items() if k == "color"})
    for ax in axes.ravel():
        ax.set_xlim(*lim)
        ax.set_ylim(*lim)
        ax.set_aspect("equal")
    for row in range(3):
        axes[row, 0].plot(Xs[:, 0], Xs[:, 1], ".", color=GREY, ms=1.5, alpha=0.5, rasterized=True)
        ell(axes[row, 0], TF_MU, TF_SIG, color="k", lw=1.5)
        axes[row, 1].plot(Ys[:, 0], Ys[:, 1], ".", color=GREY, ms=1.5, alpha=0.5, rasterized=True)
        ell(axes[row, 1], mc_m, mc_S, color="k", lw=1.2, ls="--")
    axes[0, 0].set_title("(a) source samples and N(mu, Sigma)")
    ell(axes[0, 1], r["taylor"][0], r["taylor"][1], color=RED, lw=1.6)
    axes[0, 1].set_title("(b) MC moments (dashed), Taylor (red)")
    X, _, _ = sigma_points(TF_MU, TF_SIG, 1.0, 0.0, 1.0)
    axes[1, 0].plot(X[:, 0], X[:, 1], "o", mfc="none", color=BLUE, ms=7, mew=1.5)
    axes[1, 0].set_title("(c) unscented sigma points")
    Yp = np.array([tf_g(x) for x in X])
    axes[1, 1].plot(Yp[:, 0], Yp[:, 1], "o", mfc="none", color=BLUE, ms=7, mew=1.5)
    ell(axes[1, 1], r["ut"][0], r["ut"][1], color=BLUE, lw=1.6)
    axes[1, 1].set_title("(d) unscented transform (blue)")
    X, w, _ = gauss_hermite_points(TF_MU, TF_SIG, 5)
    axes[2, 0].scatter(X[:, 0], X[:, 1], s=8 + 400 * w, facecolors="none", edgecolors=GREEN, lw=1.3)
    axes[2, 0].set_title("(e) Gauss-Hermite points (order 5)")
    Yp = np.array([tf_g(x) for x in X])
    axes[2, 1].scatter(Yp[:, 0], Yp[:, 1], s=8 + 400 * w, facecolors="none", edgecolors=GREEN, lw=1.3)
    ell(axes[2, 1], r["gh"][0], r["gh"][1], color=GREEN, lw=1.6)
    axes[2, 1].set_title("(f) Gauss-Hermite transform (green)")
    savefig(fig, CH, "fig8-5", out)


def _logreg_traces(fig_name, perm, out, method="adf"):
    X, y = logreg_data()
    D = X.shape[1]
    w, C = laplace_logistic(X, y, LOGREG_V0)
    if method == "adf":
        Mu, V = adf_logistic(X[perm], y[perm], np.zeros(D), np.full(D, LOGREG_V0))
    else:
        Mu, P = eekf_logistic(X[perm], y[perm], np.zeros(D), LOGREG_V0 * np.eye(D))
        V = np.array([np.diag(p) for p in P])
    lab = "online (ADF)" if method == "adf" else "online (EEKF)"
    t = np.arange(1, len(y) + 1)
    fig, axes = plt.subplots(1, 3, figsize=(11.5, 3.2))
    for j, ax in enumerate(axes):
        ax.errorbar(t, Mu[:, j], yerr=np.sqrt(V[:, j]), fmt="o", ms=3, color=BLUE, ecolor=BLUE, elinewidth=0.6,
                    capsize=0, label="w%d %s" % (j, lab))
        ax.axhline(w[j], color=RED, ls="--", lw=1.4, label="w%d batch (Laplace)" % j)
        ax.axhspan(w[j] - np.sqrt(C[j, j]), w[j] + np.sqrt(C[j, j]), color=RED, alpha=0.08)
        ax.set_xlabel("number of samples")
        ax.set_ylabel("weight")
        ax.legend(fontsize=8, loc="lower right")
        ax.set_title("(%s)" % "abc"[j])
    savefig(fig, CH, fig_name, out)


def fig_8_10(out=None):
    """ADF marginal posteriors over time against the offline Laplace approximation."""
    X, y = logreg_data()
    _logreg_traces("fig8-10", np.arange(len(y)), out)


def fig_8_11(out=None):
    """Same as Figure 8.10 with the data visited in another order."""
    X, y = logreg_data()
    _logreg_traces("fig8-11", np.random.default_rng(5).permutation(len(y)), out)


def fig_S8_4(out=None):
    """EEKF marginal posteriors over time against the Laplace approximation."""
    X, y = logreg_data()
    _logreg_traces("figS8-4", np.arange(len(y)), out, method="eekf")


def _predictive_panels(panels, fname, out):
    X, y = logreg_data()
    g = np.linspace(-4, 4, 121)
    G1, G2 = np.meshgrid(g, g)
    Xg = np.column_stack([np.ones(G1.size), G1.ravel(), G2.ravel()])
    fig, axes = plt.subplots(1, len(panels), figsize=(3.7 * len(panels), 3.5))
    for ax, (title, P) in zip(np.atleast_1d(axes), panels):
        cs = ax.contourf(G1, G2, P(Xg).reshape(G1.shape), levels=np.linspace(0, 1, 11), cmap="RdBu_r", alpha=0.85)
        ax.contour(G1, G2, P(Xg).reshape(G1.shape), levels=[0.5], colors="k", linewidths=1)
        ax.scatter(X[y == 1, 1], X[y == 1, 2], marker="o", c="#b2182b", edgecolors="w", s=22, lw=0.6)
        ax.scatter(X[y == 0, 1], X[y == 0, 2], marker="s", c="#2166ac", edgecolors="w", s=20, lw=0.6)
        ax.set_title(title)
        ax.set_aspect("equal")
    fig.colorbar(cs, ax=axes, shrink=0.8, label="p(y = 1 | x)")
    savefig(fig, CH, fname, out)


def _pred_fns():
    X, y = logreg_data()
    D = X.shape[1]
    w, C = laplace_logistic(X, y, LOGREG_V0)
    Mu, Tau = adf_logistic(X, y, np.zeros(D), np.full(D, LOGREG_V0))
    Me, Pe = eekf_logistic(X, y, np.zeros(D), LOGREG_V0 * np.eye(D))
    lap = lambda Xg: probit_predictive(Xg @ w, np.einsum("ij,jk,ik->i", Xg, C, Xg))
    adf = lambda Xg: probit_predictive(Xg @ Mu[-1], (Xg ** 2) @ Tau[-1])
    eek = lambda Xg: probit_predictive(Xg @ Me[-1], np.einsum("ij,jk,ik->i", Xg, Pe[-1], Xg))
    return lap, adf, eek


def fig_8_12(out=None):
    """Posterior predictive p(y=1|x): Laplace against ADF at the final step."""
    lap, adf, _ = _pred_fns()
    _predictive_panels([("(a) Laplace predictive", lap), ("(b) ADF predictive", adf)], "fig8-12", out)


def fig_S8_3(out=None):
    """Posterior predictive p(y=1|x): MCMC, Laplace, EEKF."""
    X, y = logreg_data()
    lap, _, eek = _pred_fns()
    W, acc = mh_logistic(X, y, LOGREG_V0, n=20000, seed=1)
    Ws = W[::20]
    mc = lambda Xg: sigmoid(Xg @ Ws.T).mean(1)
    _predictive_panels([("(a) MCMC predictive", mc), ("(b) Laplace predictive", lap), ("(c) EEKF predictive", eek)],
                       "figS8-3", out)


def student_problem(T=26, seed=3):
    """z_t = z_{t-1} + T_2 noise, y_t = z_t + T_2 noise, t = 0..25, with an outlier placed at t = 20."""
    rng = np.random.default_rng(seed)
    z = np.zeros(T)
    z[0] = 3.0
    for t in range(1, T):
        z[t] = z[t - 1] + rng.standard_t(2)
    y = z + rng.standard_t(2, size=T)
    y[20] = z[20] + 12.0
    return z, y


def student_grid():
    grid = np.linspace(-20, 20, 801)
    t2 = lambda d: stats.t.pdf(d, df=2)
    prior = lambda g: stats.norm.pdf(g, 0, 10)
    return grid, t2, prior


def fig_8_13(out=None):
    """Grid filter and smoother with Student noise: data, estimates and the marginals at t = 20."""
    z, y = student_problem()
    grid, t2, prior = student_grid()
    pred, filt, smooth, ll = grid_filter_smoother(y, grid, t2, t2, prior)
    mf, ms = filt @ grid, smooth @ grid
    dz = grid[1] - grid[0]
    fig, axes = plt.subplots(1, 2, figsize=(10, 3.4))
    ax = axes[0]
    t = np.arange(len(y))
    ax.plot(t, z, "k*-", ms=5, lw=1, label="true state")
    ax.plot(t, y, "o-", color=RED, ms=4, lw=1, label="measurements")
    ax.plot(t, mf, "-", color=BLUE, lw=1.2, label="filtered mean")
    ax.plot(t, ms, "-", color=ORANGE, lw=1.2, label="smoothed mean")
    ax.set_xlabel("time")
    ax.legend(fontsize=8)
    ax.set_title("(a)")
    ax = axes[1]
    ax.plot(grid, filt[20] / dz, color=BLUE, label="filtering")
    ax.plot(grid, smooth[20] / dz, color=ORANGE, label="smoothing")
    ax.axvline(z[20], color="k", lw=2, label="true state")
    ax.axvline(y[20], color=RED, lw=2, label="measurement")
    ax.set_xlabel("$z_{20}$")
    ax.set_ylabel("density")
    ax.legend(fontsize=8)
    ax.set_title("(b)")
    savefig(fig, CH, "fig8-13", out)


def fig_8_14(out=None):
    """Discretised filtering and smoothing posteriors over time (heat maps)."""
    z, y = student_problem()
    grid, t2, prior = student_grid()
    pred, filt, smooth, ll = grid_filter_smoother(y, grid, t2, t2, prior)
    dz = grid[1] - grid[0]
    fig, axes = plt.subplots(1, 2, figsize=(11, 3.6))
    for ax, P, lab in ((axes[0], filt, "(a) filtering"), (axes[1], smooth, "(b) smoothing")):
        im = ax.imshow((P / dz).T, aspect="auto", origin="lower", extent=[-0.5, len(y) - 0.5, grid[0], grid[-1]],
                       cmap="viridis", vmax=0.5, interpolation="nearest")
        ax.plot(np.arange(len(y)), z, "x", color=RED, ms=7, mew=1.8)
        ax.plot(np.arange(len(y)), y, "o", mfc="none", color=RED, ms=6)
        ax.set_ylim(-10, 15)
        ax.set_xlabel("time")
        ax.set_title(lab)
        fig.colorbar(im, ax=ax, fraction=0.04)
    savefig(fig, CH, "fig8-14", out)


def pendulum_problem(T=400, dt=0.0125, r=0.3 ** 2, qc=0.1, seed=7):
    f, Fj, h, Hj, Q = pendulum_model(dt, qc=qc)
    rng = np.random.default_rng(seed)
    LQ = np.linalg.cholesky(Q)
    z = np.array([1.5, 0.0])
    Z, Y = [], []
    for _ in range(T):
        z = f(z) + LQ @ rng.standard_normal(2)
        Z.append(z)
        Y.append(h(z) + np.sqrt(r) * rng.standard_normal(1))
    return f, Fj, h, Hj, Q, r * np.eye(1), np.array(Z), np.array(Y), dt


def fig_S8_2(out=None):
    """EKF and UKF for the pendulum observed through sin(angle) (panels b, c)."""
    f, Fj, h, Hj, Q, R, Z, Y, dt = pendulum_problem()
    mu0, S0 = np.array([1.5, 0.0]), 0.1 * np.eye(2)
    ek = ekf(f, h, Q, R, Y, mu0, S0, Fjac=Fj, Hjac=Hj)
    uk = ukf(f, h, Q, R, Y, mu0, S0, 1.0, 0.0, 2.0)
    t = dt * np.arange(1, len(Y) + 1)
    rm = lambda M: float(np.sqrt(np.mean((M[:, 0] - Z[:, 0]) ** 2)))
    fig, axes = plt.subplots(1, 2, figsize=(10, 3.4), sharey=True)
    for ax, M, lab, c in ((axes[0], ek["mf"], "EKF", RED), (axes[1], uk["mf"], "UKF", BLUE)):
        ax.plot(t, Z[:, 0], color="k", lw=1.4, label="true angle")
        ax.plot(t, Y[:, 0], ".", color=GREY, ms=2.5, label="measurements (sin of angle)")
        ax.plot(t, M[:, 0], color=c, lw=1.2, label="%s estimate" % lab)
        ax.set_xlabel("time")
        ax.set_title("(%s) %s, RMSE %.3f" % ("b" if lab == "EKF" else "c", lab, rm(M)))
        ax.legend(fontsize=8, loc="upper right")
    axes[0].set_ylabel("pendulum angle")
    savefig(fig, CH, "figS8-2", out)
    return rm(ek["mf"]), rm(uk["mf"])


def fixed_lag_curve(lags=range(0, 9), reps=200, T=40, seed=1):
    rng = np.random.default_rng(seed)
    F, H = cv_model()
    Q, R = 0.1 * np.eye(4), np.eye(2)
    mu0, S0 = np.array([0.0, 0, 1, 0]), 0.1 * np.eye(4)
    err = np.zeros(len(list(lags)))
    lags = list(lags)
    for _ in range(reps):
        z = rng.multivariate_normal(mu0, S0)
        Z, Y = [], []
        for _t in range(T):
            z = F @ z + np.sqrt(0.1) * rng.standard_normal(4)
            Z.append(z)
            Y.append(H @ z + rng.standard_normal(2))
        Z, Y = np.array(Z), np.array(Y)
        kf = kalman_filter(F, Q, H, R, Y, mu0, S0)
        for i, l in enumerate(lags):
            # MSE at interior times s where s + l <= T - 1, so each lag uses the full lag
            m, _ = fixed_lag_smoother(F, Q, H, R, Y, mu0, S0, l) if l else (kf["mf"], None)
            s = np.arange(5, T - max(lags))
            err[i] += np.mean(np.sum((m[s, :2] - Z[s, :2]) ** 2, 1))
    return np.array(lags), err / reps


def fig_x8_a(out=None):
    """Extra: fixed-lag smoothing error against the lag."""
    lags, err = fixed_lag_curve()
    fig, ax = plt.subplots(figsize=(4.6, 3.2))
    ax.plot(lags, err, "o-", color=BLUE)
    ax.axhline(err[0], color=GREY, ls=":", lw=1)
    ax.set_xlabel("lag $\\ell$")
    ax.set_ylabel("position MSE")
    ax.set_title("fixed-lag smoothing, constant-velocity model")
    savefig(fig, CH, "figx8-a", out)
    return lags, err


def transform_error_curve(scales=np.geomspace(0.05, 4, 25)):
    res = {k: [] for k in ("taylor", "ut", "gh")}
    for s in scales:
        r = tf_methods(TF_MU, s * TF_SIG)
        for k in res:
            res[k].append(kl_gauss(r["exact"][0], r["exact"][1], r[k][0], r[k][1]))
    return scales, {k: np.array(v) for k, v in res.items()}


def fig_x8_b(out=None):
    """Extra: KL from the exact moment-matched Gaussian to each approximation, against the prior scale."""
    scales, res = transform_error_curve()
    fig, ax = plt.subplots(figsize=(4.8, 3.3))
    for k, c, lab in (("taylor", RED, "Taylor (EKF)"), ("ut", BLUE, "unscented (UKF)"), ("gh", GREEN, "Gauss-Hermite, order 5")):
        ax.loglog(scales, np.maximum(res[k], 1e-12), "-", color=c, label=lab)
    ax.set_xlabel("prior covariance scale $s$ (covariance $s\\Sigma$)")
    ax.set_ylabel("KL(exact moments || approximation)")
    ax.legend(fontsize=8)
    savefig(fig, CH, "figx8-b", out)


FIGURES = {"8.2": fig_8_2, "8.4": fig_8_4, "8.5": fig_8_5, "8.10": fig_8_10, "8.11": fig_8_11, "8.12": fig_8_12,
           "8.13": fig_8_13, "8.14": fig_8_14, "S8.1": fig_S8_1, "S8.2": fig_S8_2, "S8.3": fig_S8_3,
           "S8.4": fig_S8_4, "x8.a": fig_x8_a, "x8.b": fig_x8_b}


def export_json():
    os.makedirs(DATA_OUT, exist_ok=True)
    X, y = logreg_data()
    ref = logreg_reference()
    d = dict(note="Simulated 2d logistic-regression data (Murphy 2023, Figures 8.10-8.12 and Supplementary 8.3-8.4 "
                  "stand-in): columns x1, x2 and label y; the bias column is added in the page.",
             x1=[float(v) for v in X[:, 1]], x2=[float(v) for v in X[:, 2]],
             y=[int(v) for v in y], v0=LOGREG_V0, perm2=ref["order2"]["perm"])
    with open(os.path.join(DATA_OUT, "ch08-logreg.json"), "w") as fh:
        json.dump(d, fh, separators=(",", ":"))
    print("wrote", os.path.join(DATA_OUT, "ch08-logreg.json"))


if __name__ == "__main__":
    if "--json" in sys.argv:
        export_json()
    else:
        common.run(FIGURES, CH)
        if "--fig" not in sys.argv and "--list" not in sys.argv:
            export_json()
