% ============================================================================
%  Artificial Neural Networks — Methods, Equations and Graphical
%  Representations
%  Author  : Simon-Pierre Boucher — contact@spboucher.ai
%  Chapter 11 : Normalizing Flows, Diffusion and Autoregressive Models
%               (chapters/11-advanced-generative.tex)
% ============================================================================
\chapter{Normalizing Flows, Diffusion and Autoregressive Models}
\label{chap:advgen}

The previous chapter introduced generative models whose likelihood is either
approximated from below (the variational autoencoder) or never written down
at all (the generative adversarial network). This chapter completes the
generative landscape with three families that take the opposite stance:
they insist on an \emph{explicit} probabilistic account of the data.
\emph{Normalizing flows} construct an invertible map between noise and data
and obtain the exact likelihood from the change-of-variables formula.
\emph{Diffusion models} destroy data with a fixed Markovian noising process
and learn to reverse it, optimizing a variational bound that collapses to a
strikingly simple denoising objective. \emph{Deep autoregressive models}
factorize the joint density exactly with the chain rule and reduce
generation to next-element prediction. For each family we give the defining
equations, the estimation algorithm in pseudocode, and a graphical
representation of the computational structure; we close with a brief look
at energy-based models, which unify several of these views.

% ============================================================================
\section{Normalizing Flows}
\label{sec:agen-flows}

\begin{definition}[Normalizing flow]\label{def:agen-flow}
A \emph{normalizing flow} is a diffeomorphism $T \colon \R^{D} \to \R^{D}$
— an invertible, differentiable map with differentiable inverse — that
transports a simple \emph{base density} $p_Z$ (typically the standard
Gaussian $\mathcal{N}(\vect{0}, \mat{I})$) into a complex data density:
$\vect{x} = T(\vect{z})$ with $\vect{z} \sim p_Z$.
\end{definition}

Because $T$ is invertible, the density of $\vect{x}$ is not merely bounded
or approximated — it is \emph{known exactly}, through the
change-of-variables formula:
\begin{equation}
  \log p_X(\vect{x})
  = \log p_Z\!\big(T^{-1}(\vect{x})\big)
  + \log \left| \det \frac{\partial T^{-1}(\vect{x})}{\partial \vect{x}}
    \right|.
  \label{eq:agen-cov}
\end{equation}
The Jacobian determinant measures how the map locally contracts or expands
volume; it is precisely the correction that keeps total probability mass
equal to one. In practice a single map is too rigid, so the flow is built
as a composition of $K$ simpler bijections,
$T = f_K \circ f_{K-1} \circ \dots \circ f_1$, generating a chain
$\vect{z}_0 \sim p_Z$, $\vect{z}_k = f_k(\vect{z}_{k-1})$,
$\vect{x} = \vect{z}_K$. Log-determinants then simply add along the chain
\cite{rezende2015}:
\begin{equation}
  \log p_X(\vect{x})
  = \log p_Z(\vect{z}_0)
  - \sum_{k=1}^{K} \log \left| \det
      \mat{J}_{f_k}(\vect{z}_{k-1}) \right|,
  \qquad
  \mat{J}_{f_k} = \frac{\partial f_k}{\partial \vect{z}_{k-1}}.
  \label{eq:agen-comp}
\end{equation}
Training maximizes the exact log-likelihood \eqref{eq:agen-comp} by
running the chain backwards (density evaluation); sampling runs it
forwards from Gaussian noise. Figure~\ref{fig:agen-flow} shows the
architecture: a stack of bijective blocks, each contributing one log-det
term to the likelihood.

\begin{figure}[htbp]
  \centering
  \begin{tikzpicture}[node distance=7mm]
    % --- chain of bijections ---
    \node[mem, minimum width=10mm]  (z0) {$\vect{z}_0$};
    \node[bloc, minimum width=10mm, right=of z0]  (f1) {$f_1$};
    \node[mem, minimum width=10mm, right=of f1]   (z1) {$\vect{z}_1$};
    \node[right=5.5mm of z1] (dots) {$\cdots$};
    \node[mem, minimum width=13mm, right=5.5mm of dots] (zk1) {$\vect{z}_{K-1}$};
    \node[bloc, minimum width=10mm, right=of zk1] (fk) {$f_K$};
    \node[blocoutput, minimum width=10mm, right=of fk] (x) {$\vect{x}$};
    \draw[fleche] (z0) -- (f1);
    \draw[fleche] (f1) -- (z1);
    \draw[fleche] (z1) -- (dots);
    \draw[fleche] (dots) -- (zk1);
    \draw[fleche] (zk1) -- (fk);
    \draw[fleche] (fk) -- (x);
    % --- accumulating log-det annotations ---
    \node[etiquette, below=2.5mm of f1]
      {$-\log\big|\det \mat{J}_{f_1}\big|$};
    \node[etiquette, below=2.5mm of fk]
      {$-\log\big|\det \mat{J}_{f_K}\big|$};
    \node[etiquette, below=2.5mm of dots] {$\cdots$};
    % --- direction labels ---
    \draw[fleche, black!50]
      ($(z0.south)+(0,-1.15)$) -- ($(x.south)+(0,-1.15)$)
      node[midway, below, etiquette] {generation $\vect{z}_0 \to \vect{x}$};
    \draw[flechep, black!50]
      ($(x.north)+(0,1.3)$) -- ($(z0.north)+(0,1.3)$)
      node[midway, above, etiquette]
      {density evaluation $\vect{x} \to \vect{z}_0$ via $f_k^{-1}$};
    % --- base density curve above z0 ---
    \begin{scope}[shift={($(z0.north)+(0,0.28)$)}]
      \draw[black!40] (-0.75,0) -- (0.75,0);
      \draw[cinput, thick]
        plot[domain=-0.72:0.72, samples=41] (\x, {0.55*exp(-11*\x*\x)});
    \end{scope}
    % --- warped density curve above x ---
    \begin{scope}[shift={($(x.north)+(0,0.28)$)}]
      \draw[black!40] (-0.75,0) -- (0.75,0);
      \draw[coutput, thick]
        plot[domain=-0.72:0.72, samples=61]
        (\x, {0.45*exp(-26*(\x-0.33)^2) + 0.55*exp(-26*(\x+0.28)^2)});
    \end{scope}
  \end{tikzpicture}
  \caption{A normalizing flow as a chain of $K$ bijections. Sampling runs
  left to right, from the Gaussian base density (blue curve) to the data
  density (red curve); exact density evaluation runs right to left through
  the inverses $f_k^{-1}$, accumulating the log-det terms of
  \eqref{eq:agen-comp}. Every intermediate variable $\vect{z}_k$ keeps the
  full dimension $D$: flows never compress.}
  \label{fig:agen-flow}
\end{figure}

The whole design problem of flows is to make each
$\det \mat{J}_{f_k}$ computable in $O(D)$ rather than $O(D^{3})$ without
destroying expressiveness \cite{rezende2015}. The canonical solution is
the \emph{affine coupling layer} of Real~NVP \cite{dinh2017}. Split the
input into two halves, $\vect{x} = (\vect{x}_{1:d}, \vect{x}_{d+1:D})$;
the layer leaves the first half untouched and applies to the second an
affine transformation \emph{whose parameters are computed from the first}:
\begin{equation}
  \vect{y}_{1:d} = \vect{x}_{1:d},
  \qquad
  \vect{y}_{d+1:D} = \vect{x}_{d+1:D} \odot
    \exp\!\big(s(\vect{x}_{1:d})\big) + t(\vect{x}_{1:d}),
  \label{eq:agen-coupling}
\end{equation}
where $s, t \colon \R^{d} \to \R^{D-d}$ are arbitrary neural networks —
they are never inverted, so they can be as deep as desired. The inverse is
immediate:
\begin{equation}
  \vect{x}_{1:d} = \vect{y}_{1:d},
  \qquad
  \vect{x}_{d+1:D} = \big(\vect{y}_{d+1:D} - t(\vect{y}_{1:d})\big)
    \odot \exp\!\big(-s(\vect{y}_{1:d})\big).
  \label{eq:agen-coupling-inv}
\end{equation}
Because $\vect{y}_{1:d}$ does not depend on $\vect{x}_{d+1:D}$, the
Jacobian of \eqref{eq:agen-coupling} is block-triangular with a diagonal
lower-right block, and its log-determinant is a plain sum — no determinant
computation at all:
\begin{equation}
  \log \left| \det \mat{J} \right|
  = \sum_{j=1}^{D-d} s\big(\vect{x}_{1:d}\big)_j.
  \label{eq:agen-coupling-logdet}
\end{equation}
Alternating which half is transformed from layer to layer (and permuting
or squeezing dimensions between couplings) lets every coordinate
eventually influence every other.

\begin{remark}[Expressiveness versus tractability]\label{rem:agen-tradeoff}
Equations \eqref{eq:agen-coupling}--\eqref{eq:agen-coupling-logdet} are one
point on a general trade-off. Triangular-Jacobian constructions — coupling
layers, and the masked autoregressive flows in which
$x_i = z_i\, \sigma_i(\vect{x}_{1:i-1}) + \mu_i(\vect{x}_{1:i-1})$ — buy an
$O(D)$ log-determinant at the cost of restricting how information mixes in
a single layer; depth restores expressiveness. Unconstrained maps would be
maximally expressive per layer, but their $O(D^{3})$ determinants are
unusable at scale. Flows also require the latent dimension to equal the
data dimension, in sharp contrast with the bottlenecked autoencoders of
the previous chapter.
\end{remark}

Estimation is pure maximum likelihood on \eqref{eq:agen-comp}:

\begin{algorithm}[htbp]
  \caption{Maximum-likelihood training of a normalizing flow}
  \label{alg:agen-flow}
  \begin{algorithmic}[1]
    \Require dataset $\mathcal{D}$, bijections $f_1, \dots, f_K$ with
      parameters $\theta$, base density $p_Z$, learning rate $\eta$
    \Repeat
      \State sample a minibatch $\{\vect{x}^{(1)}, \dots,
        \vect{x}^{(m)}\} \subset \mathcal{D}$
      \For{each $\vect{x}^{(i)}$ in the minibatch}
        \State $\vect{z}_K \gets \vect{x}^{(i)}$; \quad $\ell^{(i)} \gets 0$
        \For{$k = K, K-1, \dots, 1$}
          \Comment{inverse pass: data $\to$ noise}
          \State $\vect{z}_{k-1} \gets f_k^{-1}(\vect{z}_k)$
          \State $\ell^{(i)} \gets \ell^{(i)}
            - \log\big|\det \mat{J}_{f_k}(\vect{z}_{k-1})\big|$
        \EndFor
        \State $\ell^{(i)} \gets \ell^{(i)} + \log p_Z(\vect{z}_0)$
        \Comment{$\ell^{(i)} = \log p_X(\vect{x}^{(i)})$ by
          \eqref{eq:agen-comp}}
      \EndFor
      \State $\Loss(\theta) \gets -\frac{1}{m}\sum_{i=1}^{m} \ell^{(i)}$
      \State $\theta \gets \theta - \eta \, \nabla_\theta \Loss(\theta)$
    \Until{convergence}
  \end{algorithmic}
\end{algorithm}

% ============================================================================
\section{Diffusion Models}
\label{sec:agen-diffusion}

Diffusion models \cite{ho2020} take a fundamentally different route to an
explicit likelihood: instead of building an invertible map, they
\emph{destroy} the data with a fixed stochastic process and learn only the
reversal. The approach currently dominates image, audio and video
synthesis, and its training objective is among the simplest in all of deep
learning.

\subsection{The forward (noising) process}

Fix a number of steps $T$ (typically $10^{3}$) and a variance schedule
$\beta_1, \dots, \beta_T \in (0,1)$. The \emph{forward process} is a
Markov chain that gradually replaces signal with Gaussian noise:
\begin{equation}
  q(\vect{x}_t \mid \vect{x}_{t-1})
  = \mathcal{N}\!\big(\vect{x}_t;\,
      \sqrt{1-\beta_t}\,\vect{x}_{t-1},\; \beta_t \mat{I}\big),
  \qquad
  q(\vect{x}_{1:T} \mid \vect{x}_0)
  = \prod_{t=1}^{T} q(\vect{x}_t \mid \vect{x}_{t-1}).
  \label{eq:agen-forward}
\end{equation}
Nothing in \eqref{eq:agen-forward} is learned. The scaling
$\sqrt{1-\beta_t}$ is chosen so that variance is preserved: if
$\vect{x}_{t-1}$ has identity covariance, so does $\vect{x}_t$.

\begin{property}[Closed-form marginal]\label{prop:agen-marginal}
Let $\alpha_t = 1 - \beta_t$ and
$\bar{\alpha}_t = \prod_{s=1}^{t} \alpha_s$. Then the forward chain can be
jumped in a single step from $\vect{x}_0$ to any $\vect{x}_t$:
\begin{equation}
  q(\vect{x}_t \mid \vect{x}_0)
  = \mathcal{N}\!\big(\vect{x}_t;\,
      \sqrt{\bar{\alpha}_t}\,\vect{x}_0,\;
      (1-\bar{\alpha}_t)\,\mat{I}\big)
  \;\Longleftrightarrow\;
  \vect{x}_t = \sqrt{\bar{\alpha}_t}\,\vect{x}_0
    + \sqrt{1-\bar{\alpha}_t}\;\vect{\varepsilon},
  \quad \vect{\varepsilon} \sim \mathcal{N}(\vect{0},\mat{I}).
  \label{eq:agen-closed}
\end{equation}
\end{property}

\begin{proof}[Proof sketch]
Compose two steps of \eqref{eq:agen-forward}:
$\vect{x}_t = \sqrt{\alpha_t \alpha_{t-1}}\, \vect{x}_{t-2} +
\sqrt{\alpha_t(1-\alpha_{t-1})}\, \vect{\varepsilon}' +
\sqrt{1-\alpha_t}\, \vect{\varepsilon}''$. The two independent Gaussian
terms merge into a single Gaussian with variance
$\alpha_t(1-\alpha_{t-1}) + (1-\alpha_t) = 1 - \alpha_t\alpha_{t-1}$;
induction over $t$ gives \eqref{eq:agen-closed}.
\end{proof}

Since $\bar{\alpha}_T \approx 0$ for sensible schedules,
$q(\vect{x}_T \mid \vect{x}_0) \approx \mathcal{N}(\vect{0}, \mat{I})$: at
the end of the chain, every trace of the data is gone.
Figure~\ref{fig:agen-schedule} compares the two standard schedules through
the signal coefficient $\bar{\alpha}_t$.

\begin{figure}[htbp]
  \centering
  \begin{tikzpicture}
    \begin{axis}[
        width=0.62\textwidth, height=0.36\textwidth,
        xlabel={$t/T$}, ylabel={$\bar{\alpha}_t$},
        xmin=0, xmax=1, ymin=0, ymax=1.02,
        legend style={font=\small, at={(0.97,0.97)}, anchor=north east},
        grid=major, grid style={black!12},
      ]
      \addplot[cinput, thick, domain=0:1, samples=120]
        {exp(-(0.1*x + 9.95*x^2))};
      \addlegendentry{linear $\beta_t$ schedule}
      \addplot[coutput, thick, domain=0:1, samples=120]
        {cos((x+0.008)/1.008 * 90)^2};
      \addlegendentry{cosine schedule}
    \end{axis}
  \end{tikzpicture}
  \caption{Remaining signal fraction $\bar{\alpha}_t$ along the forward
  process, for the linear schedule of \cite{ho2020}
  ($\beta_1 = 10^{-4}$ to $\beta_T = 0.02$, $T = 1000$) and the cosine
  schedule. The linear schedule destroys most of the signal in the first
  third of the chain; the cosine schedule spreads the destruction more
  evenly over time.}
  \label{fig:agen-schedule}
\end{figure}

\subsection{The reverse (generative) process}

Generation runs the chain backwards: start from pure noise
$p(\vect{x}_T) = \mathcal{N}(\vect{0}, \mat{I})$ and denoise step by step
with a \emph{learned} Markov chain,
\begin{equation}
  p_\theta(\vect{x}_{t-1} \mid \vect{x}_t)
  = \mathcal{N}\!\big(\vect{x}_{t-1};\,
      \vect{\mu}_\theta(\vect{x}_t, t),\; \sigma_t^2 \mat{I}\big).
  \label{eq:agen-reverse}
\end{equation}
The structure of the two chains is summarized in
Figure~\ref{fig:agen-diffusion}. Training maximizes a variational lower
bound on $\log p_\theta(\vect{x}_0)$, exactly as in the VAE, and the bound
decomposes over timesteps into a sum of Kullback--Leibler divergences
between Gaussians:
\begin{equation}
\begin{split}
  \Loss_{\mathrm{VLB}}
  = \E_q\Big[
    &\underbrace{\KL\big(q(\vect{x}_T \mid \vect{x}_0)
      \,\|\, p(\vect{x}_T)\big)}_{\Loss_T} \\[-2pt]
    &+ \sum_{t=2}^{T}
    \underbrace{\KL\big(q(\vect{x}_{t-1} \mid \vect{x}_t, \vect{x}_0)
      \,\|\, p_\theta(\vect{x}_{t-1} \mid \vect{x}_t)\big)}_{\Loss_{t-1}}
    \underbrace{-\, \log p_\theta(\vect{x}_0 \mid \vect{x}_1)}_{\Loss_0}
  \Big].
\end{split}
  \label{eq:agen-elbo}
\end{equation}
Each middle term compares the model's reverse step with the \emph{true}
posterior of the forward chain conditioned on the clean data — which is
itself Gaussian and available in closed form:
\begin{align}
  \tilde{\vect{\mu}}_t(\vect{x}_t, \vect{x}_0)
  &= \frac{\sqrt{\bar{\alpha}_{t-1}}\,\beta_t}{1-\bar{\alpha}_t}\,
     \vect{x}_0
   + \frac{\sqrt{\alpha_t}\,(1-\bar{\alpha}_{t-1})}{1-\bar{\alpha}_t}\,
     \vect{x}_t,
  \label{eq:agen-postmean}\\
  \tilde{\beta}_t
  &= \frac{1-\bar{\alpha}_{t-1}}{1-\bar{\alpha}_t}\,\beta_t.
  \label{eq:agen-postvar}
\end{align}

\begin{figure}[htbp]
  \centering
  \begin{tikzpicture}[
      dnode/.style={bloc, minimum width=12.5mm, minimum height=9mm},
    ]
    \node[dnode, fill=black!2]  (x0) at (0,0)    {$\vect{x}_0$};
    \node[dnode, fill=black!12] (x1) at (2.9,0)  {$\vect{x}_1$};
    \node                       (xd) at (5.8,0)  {$\cdots$};
    \node[dnode, fill=black!30] (xt) at (8.7,0)  {$\vect{x}_{T-1}$};
    \node[dnode, fill=black!45] (xT) at (11.6,0) {$\vect{x}_T$};
    % forward arrows (top, solid, blue)
    \foreach \a/\b in {x0/x1, x1/xd, xd/xt, xt/xT}
      \draw[fleche, cinput!80!black]
        ([yshift=1mm]\a.north east) to[out=35, in=145]
        ([yshift=1mm]\b.north west);
    \node[etiquette, text=cinput!80!black] at (5.8, 1.35)
      {forward: $q(\vect{x}_t \mid \vect{x}_{t-1})$ — fixed};
    % reverse arrows (bottom, dashed, red)
    \foreach \a/\b in {x1/x0, xd/x1, xt/xd, xT/xt}
      \draw[flechep, coutput!85!black]
        ([yshift=-1mm]\a.south west) to[out=215, in=-35]
        ([yshift=-1mm]\b.south east);
    \node[etiquette, text=coutput!85!black] at (5.8, -1.35)
      {reverse: $p_\theta(\vect{x}_{t-1} \mid \vect{x}_t)$ — learned};
    % end labels
    \node[etiquette, above=1.5mm of x0] {data};
    \node[etiquette, above=1.5mm of xT]
      {$\approx \mathcal{N}(\vect{0},\mat{I})$};
  \end{tikzpicture}
  \caption{The two Markov chains of a diffusion model. The fixed forward
  chain (solid blue, eq.~\eqref{eq:agen-forward}) progressively noises the
  data — suggested by the darkening blocks — until only Gaussian noise
  remains. The learned reverse chain (dashed red,
  eq.~\eqref{eq:agen-reverse}) denoises step by step; each reverse step is
  trained to match the tractable posterior
  \eqref{eq:agen-postmean}--\eqref{eq:agen-postvar}.}
  \label{fig:agen-diffusion}
\end{figure}

\subsection{Noise prediction and the simple loss}

The decisive reparameterization of \cite{ho2020} is to make the network
predict not the mean $\tilde{\vect{\mu}}_t$ but the \emph{noise}
$\vect{\varepsilon}$ that was added in \eqref{eq:agen-closed}. Substituting
$\vect{x}_0 = (\vect{x}_t - \sqrt{1-\bar{\alpha}_t}\,\vect{\varepsilon})
/\sqrt{\bar{\alpha}_t}$ into \eqref{eq:agen-postmean} gives the model mean
\begin{equation}
  \vect{\mu}_\theta(\vect{x}_t, t)
  = \frac{1}{\sqrt{\alpha_t}}
    \left( \vect{x}_t
      - \frac{\beta_t}{\sqrt{1-\bar{\alpha}_t}}\,
        \vect{\varepsilon}_\theta(\vect{x}_t, t) \right),
  \label{eq:agen-mu}
\end{equation}
and the weighted sum of KL terms in \eqref{eq:agen-elbo}, once the
time-dependent weights are dropped, collapses to a plain denoising
regression:
\begin{equation}
  \Loss_{\mathrm{simple}}(\theta)
  = \E_{t,\, \vect{x}_0,\, \vect{\varepsilon}}
    \Big[ \big\| \vect{\varepsilon}
      - \vect{\varepsilon}_\theta\big(
          \sqrt{\bar{\alpha}_t}\,\vect{x}_0
          + \sqrt{1-\bar{\alpha}_t}\,\vect{\varepsilon},\; t\big)
      \big\|^2 \Big],
  \qquad
  t \sim \mathcal{U}\{1,\dots,T\},\;
  \vect{\varepsilon} \sim \mathcal{N}(\vect{0},\mat{I}).
  \label{eq:agen-simple}
\end{equation}
Train a network (in practice a U-Net) to guess the noise hidden in a
randomly noised example, at a random timestep — that is the entire
training procedure, Algorithm~\ref{alg:agen-ddpm-train}. Sampling
(Algorithm~\ref{alg:agen-ddpm-sample}) then applies \eqref{eq:agen-mu}
from $t = T$ down to $1$, re-injecting fresh noise $\sigma_t \vect{z}$ at
every step except the last.

\begin{algorithm}[htbp]
  \caption{DDPM training \cite{ho2020}}
  \label{alg:agen-ddpm-train}
  \begin{algorithmic}[1]
    \Require data distribution $q(\vect{x}_0)$, schedule
      $\{\beta_t\}_{t=1}^T$, network $\vect{\varepsilon}_\theta$,
      learning rate $\eta$
    \Repeat
      \State $\vect{x}_0 \sim q(\vect{x}_0)$;\quad
        $t \sim \mathcal{U}\{1, \dots, T\}$;\quad
        $\vect{\varepsilon} \sim \mathcal{N}(\vect{0}, \mat{I})$
      \State $\vect{x}_t \gets \sqrt{\bar{\alpha}_t}\,\vect{x}_0
        + \sqrt{1-\bar{\alpha}_t}\,\vect{\varepsilon}$
        \Comment{one-step jump, eq.~\eqref{eq:agen-closed}}
      \State $\theta \gets \theta - \eta\,\nabla_\theta
        \big\| \vect{\varepsilon}
        - \vect{\varepsilon}_\theta(\vect{x}_t, t) \big\|^2$
        \Comment{eq.~\eqref{eq:agen-simple}}
    \Until{convergence}
  \end{algorithmic}
\end{algorithm}

\begin{algorithm}[htbp]
  \caption{DDPM ancestral sampling \cite{ho2020}}
  \label{alg:agen-ddpm-sample}
  \begin{algorithmic}[1]
    \Require trained $\vect{\varepsilon}_\theta$, schedule
      $\{\beta_t\}_{t=1}^T$, variances $\sigma_t^2$
      (e.g.\ $\sigma_t^2 = \tilde{\beta}_t$)
    \State $\vect{x}_T \sim \mathcal{N}(\vect{0}, \mat{I})$
    \For{$t = T, T-1, \dots, 1$}
      \State $\vect{z} \sim \mathcal{N}(\vect{0}, \mat{I})$ if $t > 1$,
        else $\vect{z} \gets \vect{0}$
      \State $\vect{x}_{t-1} \gets \dfrac{1}{\sqrt{\alpha_t}}
        \left( \vect{x}_t - \dfrac{\beta_t}{\sqrt{1-\bar{\alpha}_t}}\,
        \vect{\varepsilon}_\theta(\vect{x}_t, t) \right)
        + \sigma_t \vect{z}$
        \Comment{eq.~\eqref{eq:agen-mu}}
    \EndFor
    \State \Return $\vect{x}_0$
  \end{algorithmic}
\end{algorithm}

\subsection{Faster sampling and guidance}

Two refinements matter enormously in practice. First, the thousand-step
chain can be shortened. The \emph{denoising diffusion implicit model}
(DDIM) defines a non-Markovian family sharing the marginals
\eqref{eq:agen-closed} — so the very same trained
$\vect{\varepsilon}_\theta$ can be reused — with update
\begin{equation}
  \vect{x}_{t-1}
  = \sqrt{\bar{\alpha}_{t-1}}
    \underbrace{\left(
      \frac{\vect{x}_t - \sqrt{1-\bar{\alpha}_t}\,
        \vect{\varepsilon}_\theta(\vect{x}_t, t)}
      {\sqrt{\bar{\alpha}_t}} \right)}_{\text{predicted } \vect{x}_0}
  + \sqrt{1-\bar{\alpha}_{t-1}-\sigma_t^2}\;
    \vect{\varepsilon}_\theta(\vect{x}_t, t)
  + \sigma_t \vect{z}_t;
  \label{eq:agen-ddim}
\end{equation}
setting $\sigma_t = 0$ makes sampling \emph{deterministic} and allows
$10$--$50$ steps instead of $1000$. Second, conditional generation is
sharpened by \emph{classifier-free guidance}: train one network with the
condition $y$ randomly dropped, then extrapolate between the conditional
and unconditional predictions at sampling time,
\begin{equation}
  \tilde{\vect{\varepsilon}}_\theta(\vect{x}_t, y)
  = (1+w)\,\vect{\varepsilon}_\theta(\vect{x}_t, y)
    - w\,\vect{\varepsilon}_\theta(\vect{x}_t, \varnothing),
  \label{eq:agen-cfg}
\end{equation}
where the guidance scale $w > 0$ trades sample diversity for fidelity to
the condition. Equation \eqref{eq:agen-cfg} is the workhorse of modern
text-to-image systems.

\subsection{The score-based view and continuous time}

Diffusion admits an equivalent formulation in terms of the \emph{score
function} $\nabla_{\vect{x}} \log p(\vect{x})$ — the direction of steepest
ascent of log-density. Learning the score at multiple noise levels is
possible without ever knowing $p$, through \emph{denoising score
matching}:
\begin{equation}
  \Loss_{\mathrm{DSM}}(\theta)
  = \frac{1}{L} \sum_{i=1}^{L} \lambda(\sigma_i)\,
    \E_{\vect{x},\, \tilde{\vect{x}} \sim
        \mathcal{N}(\vect{x}, \sigma_i^2 \mat{I})}
    \left[ \left\| \vect{s}_\theta(\tilde{\vect{x}}, \sigma_i)
      + \frac{\tilde{\vect{x}} - \vect{x}}{\sigma_i^2} \right\|^2
    \right],
  \label{eq:agen-score}
\end{equation}
whose minimizer satisfies $\vect{s}_\theta(\tilde{\vect{x}}, \sigma)
\approx \nabla_{\tilde{\vect{x}}} \log p_\sigma(\tilde{\vect{x}})$. In the
continuous-time limit the forward chain \eqref{eq:agen-forward} becomes a
stochastic differential equation
$d\vect{x} = f(\vect{x}, t)\, dt + g(t)\, d\vect{w}$, and generation
solves its \emph{reverse-time} SDE, which involves exactly the score:
\begin{equation}
  d\vect{x}
  = \big[ f(\vect{x}, t)
      - g(t)^2\, \nabla_{\vect{x}} \log p_t(\vect{x}) \big]\, dt
    + g(t)\, d\bar{\vect{w}}.
  \label{eq:agen-sde}
\end{equation}
The DDPM chain is a discretization of a variance-preserving SDE, the
deterministic DDIM sampler \eqref{eq:agen-ddim} a discretization of the
associated probability-flow ODE, and the noise predictor a scaled score,
$\vect{s}_\theta(\vect{x}_t, t) =
-\vect{\varepsilon}_\theta(\vect{x}_t, t)/\sqrt{1-\bar{\alpha}_t}$. One
trained network therefore serves stochastic sampling, deterministic
sampling and exact likelihood computation alike.

% ============================================================================
\section{Deep Autoregressive Models}
\label{sec:agen-ar}

The third family needs no latent variable and no invertibility: it writes
the exact likelihood directly with the \emph{chain rule of probability}.
For $\vect{x} = (x_1, \dots, x_n)$ in any fixed ordering,
\begin{equation}
  p(\vect{x}) = \prod_{i=1}^{n}
    p\big(x_i \mid x_1, \dots, x_{i-1}\big).
  \label{eq:agen-chain}
\end{equation}
A single network models all conditionals at once; training is parallel
maximum likelihood (every position is predicted from its prefix,
teacher-forced), while sampling is inherently sequential —
Algorithm~\ref{alg:agen-ar}. This paradigm, applied to discrete tokens, is
next-token prediction, the objective behind GPT-style language models;
applied to pixels and audio samples it yields PixelCNN and WaveNet.

\paragraph{Masked convolutions.}
PixelCNN models images pixel by pixel in raster order. To let a
convolutional network evaluate all conditionals of \eqref{eq:agen-chain}
in one parallel pass, each kernel is multiplied by a binary
\emph{causality mask} $\mat{M}$ that zeroes every weight looking at the
current or future positions:
\begin{equation}
  \big( (\mat{M} \odot \mat{W}) * \vect{x} \big)_i
  = \sum_{j} (\mat{M} \odot \mat{W})_j \, x_{i+j},
  \qquad
  M_j =
  \begin{cases}
    1 & \text{if position $j$ precedes the center,}\\
    0 & \text{otherwise,}
  \end{cases}
  \label{eq:agen-mask}
\end{equation}
so the receptive field of output $i$ contains only $x_{<i}$ and the
autoregressive property holds by construction.

\paragraph{Dilated causal convolutions.}
WaveNet \cite{oord2016wavenet} applies \eqref{eq:agen-chain} to raw audio,
where useful context spans thousands of samples. Its building block is the
\emph{dilated causal convolution}, which reads the past with holes of
size $d$:
\begin{equation}
  \big( \mat{W} *_d \vect{x} \big)_t
  = \sum_{k=0}^{K-1} w_k \, x_{t - d\cdot k},
  \label{eq:agen-dilated}
\end{equation}
combined with a gated activation unit that borrows the multiplicative
gating of recurrent networks:
\begin{equation}
  \vect{z} = \tanh\!\big(\mat{W}_f *_d \vect{x}\big)
    \odot \sigma\!\big(\mat{W}_g *_d \vect{x}\big).
  \label{eq:agen-gated}
\end{equation}
Stacking $L$ layers with doubling dilations $d_\ell = 2^{\ell-1}$ and
kernel size $K = 2$ makes the receptive field grow \emph{exponentially}
with depth,
\begin{equation}
  r = 1 + (K-1) \sum_{\ell=1}^{L} d_\ell
    = 1 + \sum_{\ell=1}^{L} 2^{\ell-1}
    = 2^{L},
  \label{eq:agen-rf}
\end{equation}
while the parameter count grows only linearly.
Figure~\ref{fig:agen-wavenet} shows the resulting computation: the
highlighted binary tree gathers all $16 = 2^{4}$ past inputs into a single
output after just four layers.

\begin{figure}[htbp]
  \centering
  \begin{tikzpicture}[
      snode/.style={circle, draw=black!55, fill=black!8,
                    minimum size=3.4mm, inner sep=0pt},
      anode/.style={snode, fill=chidden!70, draw=chidden!85!black},
      hl/.style={draw=chidden!85!black, line width=1.05pt},
    ]
    % ---- nodes: row 0 = input, rows 1..4 = dilations 1,2,4,8 ----
    \foreach \row/\yy in {0/0, 1/1.05, 2/2.1, 3/3.15, 4/4.2}
      \foreach \t in {0,...,15}
        \node[snode] (n\row-\t) at (0.78*\t, \yy) {};
    % ---- all causal edges (gray) ----
    \foreach \row/\d in {1/1, 2/2, 3/4, 4/8} {
      \pgfmathtruncatemacro{\prev}{\row-1}
      \foreach \t in {0,...,15} {
        \draw[black!20] (n\prev-\t) -- (n\row-\t);
        \pgfmathtruncatemacro{\s}{\t-\d}
        \ifnum\s>-1
          \draw[black!20] (n\prev-\s) -- (n\row-\t);
        \fi
      }
    }
    % ---- highlighted binary tree reaching the last output ----
    \foreach \t in {1,3,5,7,9,11,13,15} {
      \pgfmathtruncatemacro{\s}{\t-1}
      \draw[hl] (n0-\t) -- (n1-\t);
      \draw[hl] (n0-\s) -- (n1-\t);
    }
    \foreach \t in {3,7,11,15} {
      \pgfmathtruncatemacro{\s}{\t-2}
      \draw[hl] (n1-\t) -- (n2-\t);
      \draw[hl] (n1-\s) -- (n2-\t);
    }
    \foreach \t in {7,15} {
      \pgfmathtruncatemacro{\s}{\t-4}
      \draw[hl] (n2-\t) -- (n3-\t);
      \draw[hl] (n2-\s) -- (n3-\t);
    }
    \draw[hl] (n3-15) -- (n4-15);
    \draw[hl] (n3-7)  -- (n4-15);
    % ---- redraw the tree nodes on top ----
    \foreach \t in {0,...,15} \node[anode] at (n0-\t) {};
    \foreach \t in {1,3,5,7,9,11,13,15} \node[anode] at (n1-\t) {};
    \foreach \t in {3,7,11,15} \node[anode] at (n2-\t) {};
    \foreach \t in {7,15} \node[anode] at (n3-\t) {};
    \node[anode] at (n4-15) {};
    % ---- row labels ----
    \node[etiquette, anchor=east] at (-0.45, 0)    {input};
    \node[etiquette, anchor=east] at (-0.45, 1.05) {dilation $d=1$};
    \node[etiquette, anchor=east] at (-0.45, 2.1)  {dilation $d=2$};
    \node[etiquette, anchor=east] at (-0.45, 3.15) {dilation $d=4$};
    \node[etiquette, anchor=east] at (-0.45, 4.2)  {dilation $d=8$};
    % ---- output arrow ----
    \draw[fleche, coutput!85!black] (n4-15) -- ++(0, 0.75)
      node[above, etiquette, text=coutput!85!black]
      {$p(x_{t+1} \mid x_{t-15}, \dots, x_t)$};
  \end{tikzpicture}
  \caption{WaveNet's stack of dilated causal convolutions
  (eq.~\eqref{eq:agen-dilated}) with kernel size $K=2$ and dilations
  $1, 2, 4, 8$. Gray edges show all connections; the highlighted binary
  tree is the receptive field of the final output — all $2^{4} = 16$ past
  samples reach it after only $4$ layers, as predicted by
  \eqref{eq:agen-rf}.}
  \label{fig:agen-wavenet}
\end{figure}

\begin{algorithm}[htbp]
  \caption{Autoregressive sampling}
  \label{alg:agen-ar}
  \begin{algorithmic}[1]
    \Require trained conditional model
      $p_\theta(x_i \mid \vect{x}_{<i})$, length $n$
    \For{$i = 1, 2, \dots, n$}
      \State compute the distribution
        $p_\theta(x_i \mid x_1, \dots, x_{i-1})$
        \Comment{one forward pass}
      \State sample $x_i \sim p_\theta(x_i \mid x_1, \dots, x_{i-1})$
    \EndFor
    \State \Return $\vect{x} = (x_1, \dots, x_n)$
  \end{algorithmic}
\end{algorithm}

\begin{remark}[Exactness versus sampling speed]\label{rem:agen-ar}
Among all generative families, autoregressive models and flows are the
only ones with \emph{exact} likelihoods. The price is paid at sampling
time: generation by Algorithm~\ref{alg:agen-ar} costs one network
evaluation per element, whereas a flow samples in a single pass. Diffusion
sits in between, with tens to thousands of passes depending on the sampler
\eqref{eq:agen-ddim}.
\end{remark}

% ============================================================================
\section{Energy-Based Models: A Unifying Coda}
\label{sec:agen-ebm}

Many of the threads above meet in the \emph{energy-based model} (EBM),
which drops all structural constraints and defines a density directly
through a scalar energy network $E_\theta$:
\begin{equation}
  p_\theta(\vect{x}) = \frac{e^{-E_\theta(\vect{x})}}{Z(\theta)},
  \qquad
  Z(\theta) = \int e^{-E_\theta(\vect{x})}\, d\vect{x}.
  \label{eq:agen-ebm}
\end{equation}
The partition function $Z(\theta)$ is intractable, but the
maximum-likelihood gradient takes a contrastive form that never requires
$Z$ itself:
\begin{equation}
  \nabla_\theta \log p_\theta(\vect{x})
  = -\nabla_\theta E_\theta(\vect{x})
    + \E_{\vect{x}' \sim p_\theta}
      \big[ \nabla_\theta E_\theta(\vect{x}') \big]
  \label{eq:agen-ebmgrad}
\end{equation}
— push the energy of real data down (positive phase), push the energy of
model samples up (negative phase). The negative samples $\vect{x}'$ are
drawn by Markov chain Monte Carlo, typically \emph{Langevin dynamics},
which follows the energy gradient with injected noise:
\begin{equation}
  \vect{x}_{k+1} = \vect{x}_k
    - \frac{\eta}{2} \nabla_{\vect{x}} E_\theta(\vect{x}_k)
    + \sqrt{\eta}\; \vect{\varepsilon}_k,
  \qquad \vect{\varepsilon}_k \sim \mathcal{N}(\vect{0}, \mat{I}).
  \label{eq:agen-langevin}
\end{equation}

\begin{remark}[One object, many views]\label{rem:agen-unify}
Since $\nabla_{\vect{x}} \log p_\theta(\vect{x}) =
-\nabla_{\vect{x}} E_\theta(\vect{x})$, sampling an EBM by
\eqref{eq:agen-langevin} is exactly \emph{score following} — and the noise
predictor of a diffusion model is a scaled score estimate,
$\nabla_{\vect{x}_t} \log p(\vect{x}_t) =
-\vect{\varepsilon}_\theta(\vect{x}_t, t)/\sqrt{1-\bar{\alpha}_t}$.
Diffusion models can thus be read as EBMs whose sampling chain has been
fixed, annealed and amortized. Historically, the same positive/negative
phase structure of \eqref{eq:agen-ebmgrad} appeared in the Boltzmann
machines and restricted Boltzmann machines discussed earlier in this book,
trained by contrastive divergence; the modern generative families of this
chapter are, in that sense, their descendants.
\end{remark}
