"""Murphy (2023), Chapter 22: Autoregressive models (and Supplement Chapter 22).

Companion code for Chapter 22 of K. P. Murphy, Probabilistic Machine Learning: Advanced Topics
(MIT Press, 2023; December 2025 draft), pp. 821-828. The supplement chapter 22 (pp. 199-200) has a
title page only. Written from scratch with numpy, matplotlib and PyTorch (CPU), to be read next to
the lecture notes (../ch22-autoregressive-models.html).

Methods
* Section 22.1: the chain rule (22.1), k-th order Markov models fitted by counting with a symmetric
  Dirichlet smoother (markov_bits), and a binary source with a long-range dependence whose true
  conditional entropy is known (xor_source, source_entropy_bits).
* Section 22.2: NADE with tied weights (class Nade, with the O(TH) recurrence for the hidden
  pre-activations), MADE with degree-based masks (made_masks, class Made, train_made), the path matrix
  of a masked network (path_matrix), and the exact Gaussian autoregressive model (gauss_ar).
* Section 22.3: receptive fields of causal dilated convolutions (receptive_field_1d), and the
  influence region of a stack of masked 2-d convolutions, with and without the two-stack
  (vertical plus horizontal) trick that removes the blind spot (influence_2d, blind_spot).
* Section 22.4: causal self-attention (causal_attention) and the O(T^2) count.
* Section 22.5: perplexity and bits per token (perplexity).

Skipped figures, with reasons: Figure 22.1 (diagram of a fully connected DAG), 22.2 (WaveNet
diagram), 22.3 (PixelCNN diagram), 22.4 (a GPT-3 prompt and completion), 22.5 (a chat transcript),
22.6 (DALL-E samples): all are diagrams, quotations or samples of models with billions of parameters.
The chapter has no computed figure, so every figure here is my own, named x22.a to x22.c.

Data: simulation, and the 8 x 8 digits data set bundled with scikit-learn (binarised) for the MADE.
"""
import json
import os
import sys

import numpy as np

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

CH = 22
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
os.makedirs(DATA_OUT, exist_ok=True)
torch = common.torch_setup(0)
nn = torch.nn


# =========================================================================== Section 22.1: Markov models
def h2(p):
    """Binary entropy in bits."""
    p = np.clip(p, 1e-300, 1 - 1e-16)
    return float(-p * np.log2(p) - (1 - p) * np.log2(1 - p))


def xor_source(n, eps, seed, lags=(2, 5)):
    """Binary sequence x_t = x_{t-2} XOR x_{t-5} XOR noise_t, noise ~ Ber(eps); the first max(lags) bits are fair coins.

    A model must see five previous symbols to predict well. The conditional entropy given the full
    context is h2(eps) bits per symbol (the noise is independent of the past)."""
    rng = np.random.default_rng(seed)
    L = max(lags)
    x = np.zeros(n, dtype=np.int8)
    x[:L] = rng.integers(0, 2, L)
    noise = (rng.random(n) < eps).astype(np.int8)
    for t in range(L, n):
        v = noise[t]
        for l in lags:
            v ^= x[t - l]
        x[t] = v
    return x


def source_entropy_bits(eps):
    return h2(eps)


def context_ids(x, k, t0):
    """Integer id of the k previous symbols x_{t-k:t-1} (k = 0 gives 0) for t = t0, ..., len(x) - 1."""
    t = np.arange(t0, len(x))
    ids = np.zeros(len(t), dtype=np.int64)
    for j in range(1, k + 1):
        ids = ids * 2 + x[t - j]
    return ids, x[t0:]


def markov_bits(train, test, k, alpha=0.5, t0=10):
    """Bits per symbol of an order-k Markov model fitted to `train` by counting, on train and on test.

    Predictive probability (n_{c,v} + alpha) / (n_c + 2 alpha) for context c and symbol v; all orders are
    scored on the same positions t >= t0 so that the numbers are comparable."""
    ctr, ytr = context_ids(train, k, t0)
    cte, yte = context_ids(test, k, t0)
    m = 2 ** k
    n1 = np.bincount(ctr[ytr == 1], minlength=m).astype(float)
    n0 = np.bincount(ctr[ytr == 0], minlength=m).astype(float)

    def bits(c, y):
        p1 = (n1[c] + alpha) / (n1[c] + n0[c] + 2 * alpha)
        p = np.where(y == 1, p1, 1 - p1)
        return float(-np.log2(p).mean())

    return bits(ctr, ytr), bits(cte, yte)


def order_curve(train, test, kmax=10, alpha=0.5):
    return [markov_bits(train, test, k, alpha) for k in range(kmax + 1)]


# =========================================================================== Section 22.2: NADE, MADE
class Nade(nn.Module):
    """NADE for D binary variables: h_d = sigmoid(c + W[:, :d-1] x_{:d-1}), p(x_d = 1 | x_{<d}) = sigmoid(b_d + V_d . h_d).

    The weights W (H x D) are tied across d, so the pre-activations obey a_{d+1} = a_d + W[:, d] x_d: the
    cost of the full density is O(DH), not O(D^2 H)."""

    def __init__(self, D, H):
        super().__init__()
        self.D, self.H = D, H
        self.W = nn.Parameter(torch.randn(H, D) * 0.1)
        self.V = nn.Parameter(torch.randn(D, H) * 0.1)
        self.c = nn.Parameter(torch.zeros(H))
        self.b = nn.Parameter(torch.zeros(D))

    def logits(self, x):
        a = self.c.expand(x.shape[0], -1)
        out = []
        for d in range(self.D):
            h = torch.sigmoid(a)
            out.append(self.b[d] + (h * self.V[d]).sum(1))
            a = a + x[:, d:d + 1] * self.W[:, d]            # the O(H) recurrence
        return torch.stack(out, 1)

    def logits_naive(self, x):
        """The same logits computed from scratch for each d (O(D^2 H)); used to confirm the recurrence."""
        out = []
        for d in range(self.D):
            a = self.c + x[:, :d] @ self.W[:, :d].T
            out.append(self.b[d] + (torch.sigmoid(a) * self.V[d]).sum(1))
        return torch.stack(out, 1)

    def nll(self, x):
        return nn.functional.binary_cross_entropy_with_logits(self.logits(x), x, reduction="none").sum(1)


def made_masks(D, hidden, order=None, seed=0):
    """Masks of a MADE (Germain et al. 2015) with L = len(hidden) hidden layers.

    order: a permutation; order[d] is the position (1..D) of input d in the ordering (default natural).
    Hidden degrees: unit j of a layer gets degree 1 + (j mod (D - 1)) (a deterministic, balanced choice; the
    original paper draws them at random). Returns (list of masks, input degrees, hidden degrees).
    Mask between layers: allowed iff degree_next >= degree_prev; output mask: allowed iff output degree > hidden degree."""
    m0 = np.arange(1, D + 1) if order is None else np.asarray(order)
    degs = [m0]
    for H in hidden:
        degs.append(1 + (np.arange(H) % max(D - 1, 1)))
    masks = []
    for a, b in zip(degs[:-1], degs[1:]):
        masks.append((b[:, None] >= a[None, :]).astype(float))       # (H_next, H_prev)
    masks.append((m0[:, None] > degs[-1][None, :]).astype(float))     # (D, H_last)
    return masks, m0, degs[1:]


def order_positions(D, kind):
    """Positions 1..D of the inputs for the three orderings used by the MADE demonstration."""
    from math import gcd
    if kind == "nat":
        return np.arange(1, D + 1)
    if kind == "rev":
        return np.arange(D, 0, -1)
    a = 3
    while gcd(a, D) != 1:
        a += 2
    return (a * np.arange(D) + 2) % D + 1


def path_matrix(masks):
    """P[d, d'] = number of directed paths from input d' to output d through the masked network (product of masks)."""
    P = np.eye(masks[0].shape[1])
    for M in masks:
        P = M @ P
    return P


class Made(nn.Module):
    """Masked autoencoder for density estimation, Bernoulli outputs: p(x) = prod_d Ber(x_d | sigmoid(f_d(x_{pred(d)})))."""

    def __init__(self, D, hidden, order=None):
        super().__init__()
        masks, self.m0, self.hdeg = made_masks(D, hidden, order)
        self.masks = [torch.tensor(m, dtype=torch.float32) for m in masks]
        sizes = [D] + list(hidden) + [D]
        self.lin = nn.ModuleList([nn.Linear(a, b) for a, b in zip(sizes[:-1], sizes[1:])])
        self.D = D

    def logits(self, x):
        h = x
        for i, (lin, M) in enumerate(zip(self.lin, self.masks)):
            h = nn.functional.linear(h, lin.weight * M, lin.bias)
            if i < len(self.lin) - 1:
                h = torch.relu(h)
        return h

    def nll(self, x):
        return nn.functional.binary_cross_entropy_with_logits(self.logits(x), x, reduction="none").sum(1)

    @torch.no_grad()
    def sample(self, n, seed=0):
        g = torch.Generator().manual_seed(seed)
        x = torch.zeros(n, self.D)
        for pos in np.argsort(self.m0):          # sample in the order of the degrees
            p = torch.sigmoid(self.logits(x)[:, pos])
            x[:, pos] = (torch.rand(n, generator=g) < p).float()
        return x


def digits_binary():
    """8 x 8 digits, binarised at 8 (of 16); 1 400 for training, the remaining 397 for testing."""
    from sklearn.datasets import load_digits
    X = (load_digits().data >= 8).astype(np.float32)
    return torch.tensor(X[:1400]), torch.tensor(X[1400:])


def train_made(Xtr, hidden=(128,), order=None, epochs=250, lr=3e-3, seed=0, wd=0.0):
    torch.manual_seed(seed)
    m = Made(Xtr.shape[1], hidden, order)
    opt = torch.optim.Adam(m.parameters(), lr=lr, weight_decay=wd)
    for ep in range(epochs):
        perm = torch.randperm(len(Xtr))
        for i in range(0, len(Xtr), 100):
            xb = Xtr[perm[i:i + 100]]
            loss = m.nll(xb).mean()
            opt.zero_grad(); loss.backward(); opt.step()
    return m


def gauss_ar(Sigma):
    """Exact Gaussian ARM: x_t | x_{<t} ~ N(w_t . x_{<t}, d_t). Returns (B strictly lower, d) with Sigma = (I-B)^{-1} D (I-B)^{-T}."""
    L = np.linalg.cholesky(Sigma)
    d = np.diag(L) ** 2
    Lu = L / np.diag(L)                                   # unit lower triangular
    A = np.linalg.inv(Lu)                                 # I - B
    return np.eye(len(d)) - A, d


# =========================================================================== Section 22.3: receptive fields
def receptive_field_1d(kernel, dilations):
    """Number of past inputs (including the current position) seen by one output of a stack of causal convs."""
    return 1 + (kernel - 1) * sum(dilations)


def influence_1d(kernel, dilations, T=64):
    """Boolean vector over lags 0..T-1: which past inputs reach the last output, found by propagating the graph."""
    reach = np.zeros(T, dtype=bool)
    reach[0] = True                                       # lag 0 = the last position of the top layer
    for d in dilations[::-1]:
        new = np.zeros(T, dtype=bool)
        for lag in np.nonzero(reach)[0]:
            for j in range(kernel):
                if lag + j * d < T:
                    new[lag + j * d] = True
        reach = new
    return reach


def offsets_2d(k, mask):
    """Offsets (dr, dc) used by a k x k masked kernel: mask A excludes the centre, mask B includes it."""
    h = k // 2
    out = []
    for dr in range(-h, 1):
        for dc in range(-h, h + 1):
            if dr < 0 or (dr == 0 and (dc < 0 or (dc == 0 and mask == "B"))):
                out.append((dr, dc))
    return out


def influence_2d(k, L, scheme="raster"):
    """Set of offsets (dr, dc) of input pixels that influence the output pixel at (0, 0) after L masked layers.

    raster: layer 1 uses mask A and layers 2..L use mask B (a plain PixelCNN stack).
    two-stack: vertical stack (rows above, k//2 columns either side, the current row not included) feeding a
    horizontal stack (the current row to the left); the union is every pixel in the causal box."""
    h = k // 2
    if scheme == "raster":
        reach = {(0, 0)}
        layers = ["A"] + ["B"] * (L - 1)
        for mk in layers[::-1]:                           # the output layer is the last one: walk back to the input
            new = set()
            for (r, c) in reach:
                for (dr, dc) in offsets_2d(k, mk):
                    new.add((r + dr, c + dc))
            reach = new
        # a position may only influence the output through a layer that sees it; the first layer is mask A
        return reach
    R = L * h
    return {(dr, dc) for dr in range(-R, 1) for dc in range(-R, R + 1) if dr < 0 or (dr == 0 and dc < 0)}


def blind_spot(k, L):
    """Past pixels (raster order) inside the receptive box that a raster-masked stack can never see, and their count."""
    h = k // 2
    R = L * h
    seen = influence_2d(k, L, "raster")
    full = influence_2d(k, L, "two-stack")
    bl = sorted(full - seen)
    return bl, len(bl)


def blind_spot_count_formula(k, L):
    """Closed form: row -j sees columns up to +h*min(j, L); the box has columns up to +L h."""
    h = k // 2
    R = L * h
    return sum(R - h * min(j, L) for j in range(1, R + 1))


# =========================================================================== Section 22.4: attention, perplexity
def causal_attention(Q, K, V):
    """softmax(Q K^T / sqrt(d) + causal mask) V, in numpy; also returns the attention matrix."""
    T, d = Q.shape
    S = Q @ K.T / np.sqrt(d)
    S = np.where(np.tril(np.ones((T, T), bool)), S, -np.inf)
    S = S - S.max(1, keepdims=True)
    A = np.exp(S)
    A /= A.sum(1, keepdims=True)
    return A @ V, A


def perplexity(nll_nats_per_token):
    return float(np.exp(nll_nats_per_token))


# =========================================================================== figures
def fig_x22_a(out=None):
    """Own figure: bits per symbol of order-k Markov models on a source with a lag-5 dependence, for two training sizes."""
    eps = 0.1
    fig, axes = panel_grid(1, 2, size=(3.3, 2.7), sharey=True)
    test = xor_source(20000, eps, 1000)
    for ax, N, lab in zip(axes[0], (300, 20000), "ab"):
        tr = xor_source(20000, eps, 7)[:N]
        cur = np.array(order_curve(tr, test, 10))
        ks = np.arange(11)
        ax.plot(ks, cur[:, 0], "o-", color=BLUE, ms=3.5, label="training")
        ax.plot(ks, cur[:, 1], "s-", color=RED, ms=3.5, label="test")
        ax.axhline(source_entropy_bits(eps), color=GREEN, ls="--", lw=1.2, label=r"$h_2(\varepsilon)$")
        ax.set_xlabel("order $k$ (symbols of context)")
        ax.set_title("$N=%d$ training symbols" % N)
        panel_label(ax, lab, "upper right")
    axes[0, 0].set_ylabel("bits per symbol")
    axes[0, 0].legend(loc="center left", fontsize=8)
    savefig(fig, CH, "figx22-a")


def fig_x22_b(out=None):
    """Own figure: MADE on binarised 8 x 8 digits: test negative log-likelihood against orderings, and samples."""
    Xtr, Xte = digits_binary()
    indep = (lambda p: float(-(Xte * np.log(p) + (1 - Xte) * np.log(1 - p)).sum(1).mean()))(
        ((Xtr.sum(0) + 1) / (len(Xtr) + 2)).numpy())
    res = {}
    models = {}
    for name, order in [("natural", None), ("reversed", np.arange(64, 0, -1))]:
        m = train_made(Xtr, (128,), order, epochs=120, seed=0)
        res[name] = float(m.nll(Xte).detach().mean()); models[name] = m
    rng = np.random.default_rng(0)
    rand = []
    for s in range(4):
        m = train_made(Xtr, (128,), rng.permutation(64) + 1, epochs=120, seed=s)
        rand.append(float(m.nll(Xte).detach().mean()))
    fig = plt.figure(figsize=(7.0, 2.9))
    ax = fig.add_axes([0.07, 0.17, 0.36, 0.72])
    vals = [indep, res["natural"], res["reversed"]] + rand
    labs = ["independent", "natural", "reversed"] + ["random %d" % (i + 1) for i in range(4)]
    cols = [GREY, BLUE, BLUE] + [PURPLE] * 4
    ax.bar(range(len(vals)), vals, color=cols)
    for i, v in enumerate(vals):
        ax.text(i, v + 0.4, "%.1f" % v, ha="center", fontsize=7.5)
    ax.set_xticks(range(len(vals))); ax.set_xticklabels(labs, rotation=45, ha="right", fontsize=8)
    ax.set_ylim(min(vals) - 6, max(vals) + 4)
    ax.set_ylabel("test NLL (nats per image)")
    panel_label(ax, "a", "upper right")
    S = models["natural"].sample(24, seed=3).numpy().reshape(24, 8, 8)
    grid = np.zeros((3 * 9, 8 * 9))
    for i in range(24):
        r, c = divmod(i, 8)
        grid[r * 9:r * 9 + 8, c * 9:c * 9 + 8] = S[i]
    ax2 = fig.add_axes([0.5, 0.1, 0.48, 0.8])
    ax2.imshow(grid, cmap="gray_r", interpolation="nearest"); ax2.axis("off")
    ax2.set_title("(b) samples from the MADE (natural order)", fontsize=9)
    savefig(fig, CH, "figx22-b")


def fig_x22_c(out=None):
    """Own figure: causal receptive fields (1-d, dilated) and the blind spot of a masked 2-d stack."""
    fig = plt.figure(figsize=(7.2, 3.3))
    ax = fig.add_axes([0.07, 0.16, 0.34, 0.72])
    Ls = np.arange(1, 11)
    for name, f, col in [("constant 1", lambda L: [1] * L, GREY),
                         ("doubling", lambda L: [2 ** i for i in range(L)], BLUE),
                         ("doubling, blocks of 4", lambda L: [2 ** (i % 4) for i in range(L)], ORANGE)]:
        ax.plot(Ls, [receptive_field_1d(2, f(L)) for L in Ls], "o-", ms=3.5, color=col, label=name)
    ax.set_yscale("log"); ax.set_xlabel("layers $L$ (kernel size 2)"); ax.set_ylabel("receptive field")
    ax.legend(fontsize=7.5, loc="upper left"); panel_label(ax, "a", "lower right")
    k, L = 3, 4
    h = k // 2
    R = L * h
    for j, (scheme, title, lab) in enumerate([("raster", "(b) masked stack: blind spot (red)", "b"), ("two-stack", "(c) vertical + horizontal stacks", "c")]):
        a = fig.add_axes([0.46 + 0.27 * j, 0.14, 0.25, 0.7])
        img = np.full((R + 1, 2 * R + 1, 3), 1.0)
        S = influence_2d(k, L, scheme)
        full = influence_2d(k, L, "two-stack")
        for (dr, dc) in full:
            img[dr + R, dc + R] = (0.80, 0.80, 0.80)
        for (dr, dc) in S:
            img[dr + R, dc + R] = (0.12, 0.37, 0.75)
        if scheme == "raster":
            for (dr, dc) in blind_spot(k, L)[0]:
                img[dr + R, dc + R] = (0.84, 0.15, 0.16)
        img[R, R] = (0.0, 0.0, 0.0)
        a.imshow(img, interpolation="nearest"); a.set_xticks([]); a.set_yticks([])
        a.set_title(title, fontsize=8)
    savefig(fig, CH, "figx22-c")


FIGURES = {"x22.a": fig_x22_a, "x22.b": fig_x22_b, "x22.c": fig_x22_c}


def export_json():
    """Data for the three demonstrations."""
    eps_list = (0.05, 0.1, 0.2)
    d = {"eps": list(eps_list), "train": {}, "test": {}, "ref": {}}
    for e in eps_list:
        tr = xor_source(20000, e, 7)
        te = xor_source(20000, e, 1000)
        d["train"][str(e)] = "".join(map(str, tr.tolist()))
        d["test"][str(e)] = "".join(map(str, te.tolist()))
        d["ref"][str(e)] = {"h": source_entropy_bits(e)}
    ref = {}
    for e in eps_list:
        tr = xor_source(20000, e, 7); te = xor_source(20000, e, 1000)
        for N in (300, 3000, 20000):
            ref["%g_%d" % (e, N)] = [[round(a, 6), round(b, 6)] for a, b in order_curve(tr[:N], te, 10, 0.5)]
    d["curves"] = ref
    with open(os.path.join(DATA_OUT, "ch22-markov.json"), "w") as f:
        json.dump(d, f, separators=(",", ":"))


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()
