spb/artificial-neural-networks-book Public
Artificial Neural Networks — Methods, Equations and Graphical Representations: a complete book, every method with rigorous equations, pseudocode and native TikZ figures.
TeX 100%
1% ============================================================================2% Artificial Neural Networks — Methods, Equations and Graphical3% Representations4% Author : Simon-Pierre Boucher — contact@spboucher.ai5% Chapter 11 : Normalizing Flows, Diffusion and Autoregressive Models6% (chapters/11-advanced-generative.tex)7% ============================================================================8\chapter{Normalizing Flows, Diffusion and Autoregressive Models}9\label{chap:advgen}1011The previous chapter introduced generative models whose likelihood is either12approximated from below (the variational autoencoder) or never written down13at all (the generative adversarial network). This chapter completes the14generative landscape with three families that take the opposite stance:15they insist on an \emph{explicit} probabilistic account of the data.16\emph{Normalizing flows} construct an invertible map between noise and data17and obtain the exact likelihood from the change-of-variables formula.18\emph{Diffusion models} destroy data with a fixed Markovian noising process19and learn to reverse it, optimizing a variational bound that collapses to a20strikingly simple denoising objective. \emph{Deep autoregressive models}21factorize the joint density exactly with the chain rule and reduce22generation to next-element prediction. For each family we give the defining23equations, the estimation algorithm in pseudocode, and a graphical24representation of the computational structure; we close with a brief look25at energy-based models, which unify several of these views.2627% ============================================================================28\section{Normalizing Flows}29\label{sec:agen-flows}3031\begin{definition}[Normalizing flow]\label{def:agen-flow}32A \emph{normalizing flow} is a diffeomorphism $T \colon \R^{D} \to \R^{D}$33— an invertible, differentiable map with differentiable inverse — that34transports a simple \emph{base density} $p_Z$ (typically the standard35Gaussian $\mathcal{N}(\vect{0}, \mat{I})$) into a complex data density:36$\vect{x} = T(\vect{z})$ with $\vect{z} \sim p_Z$.37\end{definition}3839Because $T$ is invertible, the density of $\vect{x}$ is not merely bounded40or approximated — it is \emph{known exactly}, through the41change-of-variables formula:42\begin{equation}43 \log p_X(\vect{x})44 = \log p_Z\!\big(T^{-1}(\vect{x})\big)45 + \log \left| \det \frac{\partial T^{-1}(\vect{x})}{\partial \vect{x}}46 \right|.47 \label{eq:agen-cov}48\end{equation}49The Jacobian determinant measures how the map locally contracts or expands50volume; it is precisely the correction that keeps total probability mass51equal to one. In practice a single map is too rigid, so the flow is built52as a composition of $K$ simpler bijections,53$T = f_K \circ f_{K-1} \circ \dots \circ f_1$, generating a chain54$\vect{z}_0 \sim p_Z$, $\vect{z}_k = f_k(\vect{z}_{k-1})$,55$\vect{x} = \vect{z}_K$. Log-determinants then simply add along the chain56\cite{rezende2015}:57\begin{equation}58 \log p_X(\vect{x})59 = \log p_Z(\vect{z}_0)60 - \sum_{k=1}^{K} \log \left| \det61 \mat{J}_{f_k}(\vect{z}_{k-1}) \right|,62 \qquad63 \mat{J}_{f_k} = \frac{\partial f_k}{\partial \vect{z}_{k-1}}.64 \label{eq:agen-comp}65\end{equation}66Training maximizes the exact log-likelihood \eqref{eq:agen-comp} by67running the chain backwards (density evaluation); sampling runs it68forwards from Gaussian noise. Figure~\ref{fig:agen-flow} shows the69architecture: a stack of bijective blocks, each contributing one log-det70term to the likelihood.7172\begin{figure}[htbp]73 \centering74 \begin{tikzpicture}[node distance=7mm]75 % --- chain of bijections ---76 \node[mem, minimum width=10mm] (z0) {$\vect{z}_0$};77 \node[bloc, minimum width=10mm, right=of z0] (f1) {$f_1$};78 \node[mem, minimum width=10mm, right=of f1] (z1) {$\vect{z}_1$};79 \node[right=5.5mm of z1] (dots) {$\cdots$};80 \node[mem, minimum width=13mm, right=5.5mm of dots] (zk1) {$\vect{z}_{K-1}$};81 \node[bloc, minimum width=10mm, right=of zk1] (fk) {$f_K$};82 \node[blocoutput, minimum width=10mm, right=of fk] (x) {$\vect{x}$};83 \draw[fleche] (z0) -- (f1);84 \draw[fleche] (f1) -- (z1);85 \draw[fleche] (z1) -- (dots);86 \draw[fleche] (dots) -- (zk1);87 \draw[fleche] (zk1) -- (fk);88 \draw[fleche] (fk) -- (x);89 % --- accumulating log-det annotations ---90 \node[etiquette, below=2.5mm of f1]91 {$-\log\big|\det \mat{J}_{f_1}\big|$};92 \node[etiquette, below=2.5mm of fk]93 {$-\log\big|\det \mat{J}_{f_K}\big|$};94 \node[etiquette, below=2.5mm of dots] {$\cdots$};95 % --- direction labels ---96 \draw[fleche, black!50]97 ($(z0.south)+(0,-1.15)$) -- ($(x.south)+(0,-1.15)$)98 node[midway, below, etiquette] {generation $\vect{z}_0 \to \vect{x}$};99 \draw[flechep, black!50]100 ($(x.north)+(0,1.3)$) -- ($(z0.north)+(0,1.3)$)101 node[midway, above, etiquette]102 {density evaluation $\vect{x} \to \vect{z}_0$ via $f_k^{-1}$};103 % --- base density curve above z0 ---104 \begin{scope}[shift={($(z0.north)+(0,0.28)$)}]105 \draw[black!40] (-0.75,0) -- (0.75,0);106 \draw[cinput, thick]107 plot[domain=-0.72:0.72, samples=41] (\x, {0.55*exp(-11*\x*\x)});108 \end{scope}109 % --- warped density curve above x ---110 \begin{scope}[shift={($(x.north)+(0,0.28)$)}]111 \draw[black!40] (-0.75,0) -- (0.75,0);112 \draw[coutput, thick]113 plot[domain=-0.72:0.72, samples=61]114 (\x, {0.45*exp(-26*(\x-0.33)^2) + 0.55*exp(-26*(\x+0.28)^2)});115 \end{scope}116 \end{tikzpicture}117 \caption{A normalizing flow as a chain of $K$ bijections. Sampling runs118 left to right, from the Gaussian base density (blue curve) to the data119 density (red curve); exact density evaluation runs right to left through120 the inverses $f_k^{-1}$, accumulating the log-det terms of121 \eqref{eq:agen-comp}. Every intermediate variable $\vect{z}_k$ keeps the122 full dimension $D$: flows never compress.}123 \label{fig:agen-flow}124\end{figure}125126The whole design problem of flows is to make each127$\det \mat{J}_{f_k}$ computable in $O(D)$ rather than $O(D^{3})$ without128destroying expressiveness \cite{rezende2015}. The canonical solution is129the \emph{affine coupling layer} of Real~NVP \cite{dinh2017}. Split the130input into two halves, $\vect{x} = (\vect{x}_{1:d}, \vect{x}_{d+1:D})$;131the layer leaves the first half untouched and applies to the second an132affine transformation \emph{whose parameters are computed from the first}:133\begin{equation}134 \vect{y}_{1:d} = \vect{x}_{1:d},135 \qquad136 \vect{y}_{d+1:D} = \vect{x}_{d+1:D} \odot137 \exp\!\big(s(\vect{x}_{1:d})\big) + t(\vect{x}_{1:d}),138 \label{eq:agen-coupling}139\end{equation}140where $s, t \colon \R^{d} \to \R^{D-d}$ are arbitrary neural networks —141they are never inverted, so they can be as deep as desired. The inverse is142immediate:143\begin{equation}144 \vect{x}_{1:d} = \vect{y}_{1:d},145 \qquad146 \vect{x}_{d+1:D} = \big(\vect{y}_{d+1:D} - t(\vect{y}_{1:d})\big)147 \odot \exp\!\big(-s(\vect{y}_{1:d})\big).148 \label{eq:agen-coupling-inv}149\end{equation}150Because $\vect{y}_{1:d}$ does not depend on $\vect{x}_{d+1:D}$, the151Jacobian of \eqref{eq:agen-coupling} is block-triangular with a diagonal152lower-right block, and its log-determinant is a plain sum — no determinant153computation at all:154\begin{equation}155 \log \left| \det \mat{J} \right|156 = \sum_{j=1}^{D-d} s\big(\vect{x}_{1:d}\big)_j.157 \label{eq:agen-coupling-logdet}158\end{equation}159Alternating which half is transformed from layer to layer (and permuting160or squeezing dimensions between couplings) lets every coordinate161eventually influence every other.162163\begin{remark}[Expressiveness versus tractability]\label{rem:agen-tradeoff}164Equations \eqref{eq:agen-coupling}--\eqref{eq:agen-coupling-logdet} are one165point on a general trade-off. Triangular-Jacobian constructions — coupling166layers, and the masked autoregressive flows in which167$x_i = z_i\, \sigma_i(\vect{x}_{1:i-1}) + \mu_i(\vect{x}_{1:i-1})$ — buy an168$O(D)$ log-determinant at the cost of restricting how information mixes in169a single layer; depth restores expressiveness. Unconstrained maps would be170maximally expressive per layer, but their $O(D^{3})$ determinants are171unusable at scale. Flows also require the latent dimension to equal the172data dimension, in sharp contrast with the bottlenecked autoencoders of173the previous chapter.174\end{remark}175176Estimation is pure maximum likelihood on \eqref{eq:agen-comp}:177178\begin{algorithm}[htbp]179 \caption{Maximum-likelihood training of a normalizing flow}180 \label{alg:agen-flow}181 \begin{algorithmic}[1]182 \Require dataset $\mathcal{D}$, bijections $f_1, \dots, f_K$ with183 parameters $\theta$, base density $p_Z$, learning rate $\eta$184 \Repeat185 \State sample a minibatch $\{\vect{x}^{(1)}, \dots,186 \vect{x}^{(m)}\} \subset \mathcal{D}$187 \For{each $\vect{x}^{(i)}$ in the minibatch}188 \State $\vect{z}_K \gets \vect{x}^{(i)}$; \quad $\ell^{(i)} \gets 0$189 \For{$k = K, K-1, \dots, 1$}190 \Comment{inverse pass: data $\to$ noise}191 \State $\vect{z}_{k-1} \gets f_k^{-1}(\vect{z}_k)$192 \State $\ell^{(i)} \gets \ell^{(i)}193 - \log\big|\det \mat{J}_{f_k}(\vect{z}_{k-1})\big|$194 \EndFor195 \State $\ell^{(i)} \gets \ell^{(i)} + \log p_Z(\vect{z}_0)$196 \Comment{$\ell^{(i)} = \log p_X(\vect{x}^{(i)})$ by197 \eqref{eq:agen-comp}}198 \EndFor199 \State $\Loss(\theta) \gets -\frac{1}{m}\sum_{i=1}^{m} \ell^{(i)}$200 \State $\theta \gets \theta - \eta \, \nabla_\theta \Loss(\theta)$201 \Until{convergence}202 \end{algorithmic}203\end{algorithm}204205% ============================================================================206\section{Diffusion Models}207\label{sec:agen-diffusion}208209Diffusion models \cite{ho2020} take a fundamentally different route to an210explicit likelihood: instead of building an invertible map, they211\emph{destroy} the data with a fixed stochastic process and learn only the212reversal. The approach currently dominates image, audio and video213synthesis, and its training objective is among the simplest in all of deep214learning.215216\subsection{The forward (noising) process}217218Fix a number of steps $T$ (typically $10^{3}$) and a variance schedule219$\beta_1, \dots, \beta_T \in (0,1)$. The \emph{forward process} is a220Markov chain that gradually replaces signal with Gaussian noise:221\begin{equation}222 q(\vect{x}_t \mid \vect{x}_{t-1})223 = \mathcal{N}\!\big(\vect{x}_t;\,224 \sqrt{1-\beta_t}\,\vect{x}_{t-1},\; \beta_t \mat{I}\big),225 \qquad226 q(\vect{x}_{1:T} \mid \vect{x}_0)227 = \prod_{t=1}^{T} q(\vect{x}_t \mid \vect{x}_{t-1}).228 \label{eq:agen-forward}229\end{equation}230Nothing in \eqref{eq:agen-forward} is learned. The scaling231$\sqrt{1-\beta_t}$ is chosen so that variance is preserved: if232$\vect{x}_{t-1}$ has identity covariance, so does $\vect{x}_t$.233234\begin{property}[Closed-form marginal]\label{prop:agen-marginal}235Let $\alpha_t = 1 - \beta_t$ and236$\bar{\alpha}_t = \prod_{s=1}^{t} \alpha_s$. Then the forward chain can be237jumped in a single step from $\vect{x}_0$ to any $\vect{x}_t$:238\begin{equation}239 q(\vect{x}_t \mid \vect{x}_0)240 = \mathcal{N}\!\big(\vect{x}_t;\,241 \sqrt{\bar{\alpha}_t}\,\vect{x}_0,\;242 (1-\bar{\alpha}_t)\,\mat{I}\big)243 \;\Longleftrightarrow\;244 \vect{x}_t = \sqrt{\bar{\alpha}_t}\,\vect{x}_0245 + \sqrt{1-\bar{\alpha}_t}\;\vect{\varepsilon},246 \quad \vect{\varepsilon} \sim \mathcal{N}(\vect{0},\mat{I}).247 \label{eq:agen-closed}248\end{equation}249\end{property}250251\begin{proof}[Proof sketch]252Compose two steps of \eqref{eq:agen-forward}:253$\vect{x}_t = \sqrt{\alpha_t \alpha_{t-1}}\, \vect{x}_{t-2} +254\sqrt{\alpha_t(1-\alpha_{t-1})}\, \vect{\varepsilon}' +255\sqrt{1-\alpha_t}\, \vect{\varepsilon}''$. The two independent Gaussian256terms merge into a single Gaussian with variance257$\alpha_t(1-\alpha_{t-1}) + (1-\alpha_t) = 1 - \alpha_t\alpha_{t-1}$;258induction over $t$ gives \eqref{eq:agen-closed}.259\end{proof}260261Since $\bar{\alpha}_T \approx 0$ for sensible schedules,262$q(\vect{x}_T \mid \vect{x}_0) \approx \mathcal{N}(\vect{0}, \mat{I})$: at263the end of the chain, every trace of the data is gone.264Figure~\ref{fig:agen-schedule} compares the two standard schedules through265the signal coefficient $\bar{\alpha}_t$.266267\begin{figure}[htbp]268 \centering269 \begin{tikzpicture}270 \begin{axis}[271 width=0.62\textwidth, height=0.36\textwidth,272 xlabel={$t/T$}, ylabel={$\bar{\alpha}_t$},273 xmin=0, xmax=1, ymin=0, ymax=1.02,274 legend style={font=\small, at={(0.97,0.97)}, anchor=north east},275 grid=major, grid style={black!12},276 ]277 \addplot[cinput, thick, domain=0:1, samples=120]278 {exp(-(0.1*x + 9.95*x^2))};279 \addlegendentry{linear $\beta_t$ schedule}280 \addplot[coutput, thick, domain=0:1, samples=120]281 {cos((x+0.008)/1.008 * 90)^2};282 \addlegendentry{cosine schedule}283 \end{axis}284 \end{tikzpicture}285 \caption{Remaining signal fraction $\bar{\alpha}_t$ along the forward286 process, for the linear schedule of \cite{ho2020}287 ($\beta_1 = 10^{-4}$ to $\beta_T = 0.02$, $T = 1000$) and the cosine288 schedule. The linear schedule destroys most of the signal in the first289 third of the chain; the cosine schedule spreads the destruction more290 evenly over time.}291 \label{fig:agen-schedule}292\end{figure}293294\subsection{The reverse (generative) process}295296Generation runs the chain backwards: start from pure noise297$p(\vect{x}_T) = \mathcal{N}(\vect{0}, \mat{I})$ and denoise step by step298with a \emph{learned} Markov chain,299\begin{equation}300 p_\theta(\vect{x}_{t-1} \mid \vect{x}_t)301 = \mathcal{N}\!\big(\vect{x}_{t-1};\,302 \vect{\mu}_\theta(\vect{x}_t, t),\; \sigma_t^2 \mat{I}\big).303 \label{eq:agen-reverse}304\end{equation}305The structure of the two chains is summarized in306Figure~\ref{fig:agen-diffusion}. Training maximizes a variational lower307bound on $\log p_\theta(\vect{x}_0)$, exactly as in the VAE, and the bound308decomposes over timesteps into a sum of Kullback--Leibler divergences309between Gaussians:310\begin{equation}311\begin{split}312 \Loss_{\mathrm{VLB}}313 = \E_q\Big[314 &\underbrace{\KL\big(q(\vect{x}_T \mid \vect{x}_0)315 \,\|\, p(\vect{x}_T)\big)}_{\Loss_T} \\[-2pt]316 &+ \sum_{t=2}^{T}317 \underbrace{\KL\big(q(\vect{x}_{t-1} \mid \vect{x}_t, \vect{x}_0)318 \,\|\, p_\theta(\vect{x}_{t-1} \mid \vect{x}_t)\big)}_{\Loss_{t-1}}319 \underbrace{-\, \log p_\theta(\vect{x}_0 \mid \vect{x}_1)}_{\Loss_0}320 \Big].321\end{split}322 \label{eq:agen-elbo}323\end{equation}324Each middle term compares the model's reverse step with the \emph{true}325posterior of the forward chain conditioned on the clean data — which is326itself Gaussian and available in closed form:327\begin{align}328 \tilde{\vect{\mu}}_t(\vect{x}_t, \vect{x}_0)329 &= \frac{\sqrt{\bar{\alpha}_{t-1}}\,\beta_t}{1-\bar{\alpha}_t}\,330 \vect{x}_0331 + \frac{\sqrt{\alpha_t}\,(1-\bar{\alpha}_{t-1})}{1-\bar{\alpha}_t}\,332 \vect{x}_t,333 \label{eq:agen-postmean}\\334 \tilde{\beta}_t335 &= \frac{1-\bar{\alpha}_{t-1}}{1-\bar{\alpha}_t}\,\beta_t.336 \label{eq:agen-postvar}337\end{align}338339\begin{figure}[htbp]340 \centering341 \begin{tikzpicture}[342 dnode/.style={bloc, minimum width=12.5mm, minimum height=9mm},343 ]344 \node[dnode, fill=black!2] (x0) at (0,0) {$\vect{x}_0$};345 \node[dnode, fill=black!12] (x1) at (2.9,0) {$\vect{x}_1$};346 \node (xd) at (5.8,0) {$\cdots$};347 \node[dnode, fill=black!30] (xt) at (8.7,0) {$\vect{x}_{T-1}$};348 \node[dnode, fill=black!45] (xT) at (11.6,0) {$\vect{x}_T$};349 % forward arrows (top, solid, blue)350 \foreach \a/\b in {x0/x1, x1/xd, xd/xt, xt/xT}351 \draw[fleche, cinput!80!black]352 ([yshift=1mm]\a.north east) to[out=35, in=145]353 ([yshift=1mm]\b.north west);354 \node[etiquette, text=cinput!80!black] at (5.8, 1.35)355 {forward: $q(\vect{x}_t \mid \vect{x}_{t-1})$ — fixed};356 % reverse arrows (bottom, dashed, red)357 \foreach \a/\b in {x1/x0, xd/x1, xt/xd, xT/xt}358 \draw[flechep, coutput!85!black]359 ([yshift=-1mm]\a.south west) to[out=215, in=-35]360 ([yshift=-1mm]\b.south east);361 \node[etiquette, text=coutput!85!black] at (5.8, -1.35)362 {reverse: $p_\theta(\vect{x}_{t-1} \mid \vect{x}_t)$ — learned};363 % end labels364 \node[etiquette, above=1.5mm of x0] {data};365 \node[etiquette, above=1.5mm of xT]366 {$\approx \mathcal{N}(\vect{0},\mat{I})$};367 \end{tikzpicture}368 \caption{The two Markov chains of a diffusion model. The fixed forward369 chain (solid blue, eq.~\eqref{eq:agen-forward}) progressively noises the370 data — suggested by the darkening blocks — until only Gaussian noise371 remains. The learned reverse chain (dashed red,372 eq.~\eqref{eq:agen-reverse}) denoises step by step; each reverse step is373 trained to match the tractable posterior374 \eqref{eq:agen-postmean}--\eqref{eq:agen-postvar}.}375 \label{fig:agen-diffusion}376\end{figure}377378\subsection{Noise prediction and the simple loss}379380The decisive reparameterization of \cite{ho2020} is to make the network381predict not the mean $\tilde{\vect{\mu}}_t$ but the \emph{noise}382$\vect{\varepsilon}$ that was added in \eqref{eq:agen-closed}. Substituting383$\vect{x}_0 = (\vect{x}_t - \sqrt{1-\bar{\alpha}_t}\,\vect{\varepsilon})384/\sqrt{\bar{\alpha}_t}$ into \eqref{eq:agen-postmean} gives the model mean385\begin{equation}386 \vect{\mu}_\theta(\vect{x}_t, t)387 = \frac{1}{\sqrt{\alpha_t}}388 \left( \vect{x}_t389 - \frac{\beta_t}{\sqrt{1-\bar{\alpha}_t}}\,390 \vect{\varepsilon}_\theta(\vect{x}_t, t) \right),391 \label{eq:agen-mu}392\end{equation}393and the weighted sum of KL terms in \eqref{eq:agen-elbo}, once the394time-dependent weights are dropped, collapses to a plain denoising395regression:396\begin{equation}397 \Loss_{\mathrm{simple}}(\theta)398 = \E_{t,\, \vect{x}_0,\, \vect{\varepsilon}}399 \Big[ \big\| \vect{\varepsilon}400 - \vect{\varepsilon}_\theta\big(401 \sqrt{\bar{\alpha}_t}\,\vect{x}_0402 + \sqrt{1-\bar{\alpha}_t}\,\vect{\varepsilon},\; t\big)403 \big\|^2 \Big],404 \qquad405 t \sim \mathcal{U}\{1,\dots,T\},\;406 \vect{\varepsilon} \sim \mathcal{N}(\vect{0},\mat{I}).407 \label{eq:agen-simple}408\end{equation}409Train a network (in practice a U-Net) to guess the noise hidden in a410randomly noised example, at a random timestep — that is the entire411training procedure, Algorithm~\ref{alg:agen-ddpm-train}. Sampling412(Algorithm~\ref{alg:agen-ddpm-sample}) then applies \eqref{eq:agen-mu}413from $t = T$ down to $1$, re-injecting fresh noise $\sigma_t \vect{z}$ at414every step except the last.415416\begin{algorithm}[htbp]417 \caption{DDPM training \cite{ho2020}}418 \label{alg:agen-ddpm-train}419 \begin{algorithmic}[1]420 \Require data distribution $q(\vect{x}_0)$, schedule421 $\{\beta_t\}_{t=1}^T$, network $\vect{\varepsilon}_\theta$,422 learning rate $\eta$423 \Repeat424 \State $\vect{x}_0 \sim q(\vect{x}_0)$;\quad425 $t \sim \mathcal{U}\{1, \dots, T\}$;\quad426 $\vect{\varepsilon} \sim \mathcal{N}(\vect{0}, \mat{I})$427 \State $\vect{x}_t \gets \sqrt{\bar{\alpha}_t}\,\vect{x}_0428 + \sqrt{1-\bar{\alpha}_t}\,\vect{\varepsilon}$429 \Comment{one-step jump, eq.~\eqref{eq:agen-closed}}430 \State $\theta \gets \theta - \eta\,\nabla_\theta431 \big\| \vect{\varepsilon}432 - \vect{\varepsilon}_\theta(\vect{x}_t, t) \big\|^2$433 \Comment{eq.~\eqref{eq:agen-simple}}434 \Until{convergence}435 \end{algorithmic}436\end{algorithm}437438\begin{algorithm}[htbp]439 \caption{DDPM ancestral sampling \cite{ho2020}}440 \label{alg:agen-ddpm-sample}441 \begin{algorithmic}[1]442 \Require trained $\vect{\varepsilon}_\theta$, schedule443 $\{\beta_t\}_{t=1}^T$, variances $\sigma_t^2$444 (e.g.\ $\sigma_t^2 = \tilde{\beta}_t$)445 \State $\vect{x}_T \sim \mathcal{N}(\vect{0}, \mat{I})$446 \For{$t = T, T-1, \dots, 1$}447 \State $\vect{z} \sim \mathcal{N}(\vect{0}, \mat{I})$ if $t > 1$,448 else $\vect{z} \gets \vect{0}$449 \State $\vect{x}_{t-1} \gets \dfrac{1}{\sqrt{\alpha_t}}450 \left( \vect{x}_t - \dfrac{\beta_t}{\sqrt{1-\bar{\alpha}_t}}\,451 \vect{\varepsilon}_\theta(\vect{x}_t, t) \right)452 + \sigma_t \vect{z}$453 \Comment{eq.~\eqref{eq:agen-mu}}454 \EndFor455 \State \Return $\vect{x}_0$456 \end{algorithmic}457\end{algorithm}458459\subsection{Faster sampling and guidance}460461Two refinements matter enormously in practice. First, the thousand-step462chain can be shortened. The \emph{denoising diffusion implicit model}463(DDIM) defines a non-Markovian family sharing the marginals464\eqref{eq:agen-closed} — so the very same trained465$\vect{\varepsilon}_\theta$ can be reused — with update466\begin{equation}467 \vect{x}_{t-1}468 = \sqrt{\bar{\alpha}_{t-1}}469 \underbrace{\left(470 \frac{\vect{x}_t - \sqrt{1-\bar{\alpha}_t}\,471 \vect{\varepsilon}_\theta(\vect{x}_t, t)}472 {\sqrt{\bar{\alpha}_t}} \right)}_{\text{predicted } \vect{x}_0}473 + \sqrt{1-\bar{\alpha}_{t-1}-\sigma_t^2}\;474 \vect{\varepsilon}_\theta(\vect{x}_t, t)475 + \sigma_t \vect{z}_t;476 \label{eq:agen-ddim}477\end{equation}478setting $\sigma_t = 0$ makes sampling \emph{deterministic} and allows479$10$--$50$ steps instead of $1000$. Second, conditional generation is480sharpened by \emph{classifier-free guidance}: train one network with the481condition $y$ randomly dropped, then extrapolate between the conditional482and unconditional predictions at sampling time,483\begin{equation}484 \tilde{\vect{\varepsilon}}_\theta(\vect{x}_t, y)485 = (1+w)\,\vect{\varepsilon}_\theta(\vect{x}_t, y)486 - w\,\vect{\varepsilon}_\theta(\vect{x}_t, \varnothing),487 \label{eq:agen-cfg}488\end{equation}489where the guidance scale $w > 0$ trades sample diversity for fidelity to490the condition. Equation \eqref{eq:agen-cfg} is the workhorse of modern491text-to-image systems.492493\subsection{The score-based view and continuous time}494495Diffusion admits an equivalent formulation in terms of the \emph{score496function} $\nabla_{\vect{x}} \log p(\vect{x})$ — the direction of steepest497ascent of log-density. Learning the score at multiple noise levels is498possible without ever knowing $p$, through \emph{denoising score499matching}:500\begin{equation}501 \Loss_{\mathrm{DSM}}(\theta)502 = \frac{1}{L} \sum_{i=1}^{L} \lambda(\sigma_i)\,503 \E_{\vect{x},\, \tilde{\vect{x}} \sim504 \mathcal{N}(\vect{x}, \sigma_i^2 \mat{I})}505 \left[ \left\| \vect{s}_\theta(\tilde{\vect{x}}, \sigma_i)506 + \frac{\tilde{\vect{x}} - \vect{x}}{\sigma_i^2} \right\|^2507 \right],508 \label{eq:agen-score}509\end{equation}510whose minimizer satisfies $\vect{s}_\theta(\tilde{\vect{x}}, \sigma)511\approx \nabla_{\tilde{\vect{x}}} \log p_\sigma(\tilde{\vect{x}})$. In the512continuous-time limit the forward chain \eqref{eq:agen-forward} becomes a513stochastic differential equation514$d\vect{x} = f(\vect{x}, t)\, dt + g(t)\, d\vect{w}$, and generation515solves its \emph{reverse-time} SDE, which involves exactly the score:516\begin{equation}517 d\vect{x}518 = \big[ f(\vect{x}, t)519 - g(t)^2\, \nabla_{\vect{x}} \log p_t(\vect{x}) \big]\, dt520 + g(t)\, d\bar{\vect{w}}.521 \label{eq:agen-sde}522\end{equation}523The DDPM chain is a discretization of a variance-preserving SDE, the524deterministic DDIM sampler \eqref{eq:agen-ddim} a discretization of the525associated probability-flow ODE, and the noise predictor a scaled score,526$\vect{s}_\theta(\vect{x}_t, t) =527-\vect{\varepsilon}_\theta(\vect{x}_t, t)/\sqrt{1-\bar{\alpha}_t}$. One528trained network therefore serves stochastic sampling, deterministic529sampling and exact likelihood computation alike.530531% ============================================================================532\section{Deep Autoregressive Models}533\label{sec:agen-ar}534535The third family needs no latent variable and no invertibility: it writes536the exact likelihood directly with the \emph{chain rule of probability}.537For $\vect{x} = (x_1, \dots, x_n)$ in any fixed ordering,538\begin{equation}539 p(\vect{x}) = \prod_{i=1}^{n}540 p\big(x_i \mid x_1, \dots, x_{i-1}\big).541 \label{eq:agen-chain}542\end{equation}543A single network models all conditionals at once; training is parallel544maximum likelihood (every position is predicted from its prefix,545teacher-forced), while sampling is inherently sequential —546Algorithm~\ref{alg:agen-ar}. This paradigm, applied to discrete tokens, is547next-token prediction, the objective behind GPT-style language models;548applied to pixels and audio samples it yields PixelCNN and WaveNet.549550\paragraph{Masked convolutions.}551PixelCNN models images pixel by pixel in raster order. To let a552convolutional network evaluate all conditionals of \eqref{eq:agen-chain}553in one parallel pass, each kernel is multiplied by a binary554\emph{causality mask} $\mat{M}$ that zeroes every weight looking at the555current or future positions:556\begin{equation}557 \big( (\mat{M} \odot \mat{W}) * \vect{x} \big)_i558 = \sum_{j} (\mat{M} \odot \mat{W})_j \, x_{i+j},559 \qquad560 M_j =561 \begin{cases}562 1 & \text{if position $j$ precedes the center,}\\563 0 & \text{otherwise,}564 \end{cases}565 \label{eq:agen-mask}566\end{equation}567so the receptive field of output $i$ contains only $x_{<i}$ and the568autoregressive property holds by construction.569570\paragraph{Dilated causal convolutions.}571WaveNet \cite{oord2016wavenet} applies \eqref{eq:agen-chain} to raw audio,572where useful context spans thousands of samples. Its building block is the573\emph{dilated causal convolution}, which reads the past with holes of574size $d$:575\begin{equation}576 \big( \mat{W} *_d \vect{x} \big)_t577 = \sum_{k=0}^{K-1} w_k \, x_{t - d\cdot k},578 \label{eq:agen-dilated}579\end{equation}580combined with a gated activation unit that borrows the multiplicative581gating of recurrent networks:582\begin{equation}583 \vect{z} = \tanh\!\big(\mat{W}_f *_d \vect{x}\big)584 \odot \sigma\!\big(\mat{W}_g *_d \vect{x}\big).585 \label{eq:agen-gated}586\end{equation}587Stacking $L$ layers with doubling dilations $d_\ell = 2^{\ell-1}$ and588kernel size $K = 2$ makes the receptive field grow \emph{exponentially}589with depth,590\begin{equation}591 r = 1 + (K-1) \sum_{\ell=1}^{L} d_\ell592 = 1 + \sum_{\ell=1}^{L} 2^{\ell-1}593 = 2^{L},594 \label{eq:agen-rf}595\end{equation}596while the parameter count grows only linearly.597Figure~\ref{fig:agen-wavenet} shows the resulting computation: the598highlighted binary tree gathers all $16 = 2^{4}$ past inputs into a single599output after just four layers.600601\begin{figure}[htbp]602 \centering603 \begin{tikzpicture}[604 snode/.style={circle, draw=black!55, fill=black!8,605 minimum size=3.4mm, inner sep=0pt},606 anode/.style={snode, fill=chidden!70, draw=chidden!85!black},607 hl/.style={draw=chidden!85!black, line width=1.05pt},608 ]609 % ---- nodes: row 0 = input, rows 1..4 = dilations 1,2,4,8 ----610 \foreach \row/\yy in {0/0, 1/1.05, 2/2.1, 3/3.15, 4/4.2}611 \foreach \t in {0,...,15}612 \node[snode] (n\row-\t) at (0.78*\t, \yy) {};613 % ---- all causal edges (gray) ----614 \foreach \row/\d in {1/1, 2/2, 3/4, 4/8} {615 \pgfmathtruncatemacro{\prev}{\row-1}616 \foreach \t in {0,...,15} {617 \draw[black!20] (n\prev-\t) -- (n\row-\t);618 \pgfmathtruncatemacro{\s}{\t-\d}619 \ifnum\s>-1620 \draw[black!20] (n\prev-\s) -- (n\row-\t);621 \fi622 }623 }624 % ---- highlighted binary tree reaching the last output ----625 \foreach \t in {1,3,5,7,9,11,13,15} {626 \pgfmathtruncatemacro{\s}{\t-1}627 \draw[hl] (n0-\t) -- (n1-\t);628 \draw[hl] (n0-\s) -- (n1-\t);629 }630 \foreach \t in {3,7,11,15} {631 \pgfmathtruncatemacro{\s}{\t-2}632 \draw[hl] (n1-\t) -- (n2-\t);633 \draw[hl] (n1-\s) -- (n2-\t);634 }635 \foreach \t in {7,15} {636 \pgfmathtruncatemacro{\s}{\t-4}637 \draw[hl] (n2-\t) -- (n3-\t);638 \draw[hl] (n2-\s) -- (n3-\t);639 }640 \draw[hl] (n3-15) -- (n4-15);641 \draw[hl] (n3-7) -- (n4-15);642 % ---- redraw the tree nodes on top ----643 \foreach \t in {0,...,15} \node[anode] at (n0-\t) {};644 \foreach \t in {1,3,5,7,9,11,13,15} \node[anode] at (n1-\t) {};645 \foreach \t in {3,7,11,15} \node[anode] at (n2-\t) {};646 \foreach \t in {7,15} \node[anode] at (n3-\t) {};647 \node[anode] at (n4-15) {};648 % ---- row labels ----649 \node[etiquette, anchor=east] at (-0.45, 0) {input};650 \node[etiquette, anchor=east] at (-0.45, 1.05) {dilation $d=1$};651 \node[etiquette, anchor=east] at (-0.45, 2.1) {dilation $d=2$};652 \node[etiquette, anchor=east] at (-0.45, 3.15) {dilation $d=4$};653 \node[etiquette, anchor=east] at (-0.45, 4.2) {dilation $d=8$};654 % ---- output arrow ----655 \draw[fleche, coutput!85!black] (n4-15) -- ++(0, 0.75)656 node[above, etiquette, text=coutput!85!black]657 {$p(x_{t+1} \mid x_{t-15}, \dots, x_t)$};658 \end{tikzpicture}659 \caption{WaveNet's stack of dilated causal convolutions660 (eq.~\eqref{eq:agen-dilated}) with kernel size $K=2$ and dilations661 $1, 2, 4, 8$. Gray edges show all connections; the highlighted binary662 tree is the receptive field of the final output — all $2^{4} = 16$ past663 samples reach it after only $4$ layers, as predicted by664 \eqref{eq:agen-rf}.}665 \label{fig:agen-wavenet}666\end{figure}667668\begin{algorithm}[htbp]669 \caption{Autoregressive sampling}670 \label{alg:agen-ar}671 \begin{algorithmic}[1]672 \Require trained conditional model673 $p_\theta(x_i \mid \vect{x}_{<i})$, length $n$674 \For{$i = 1, 2, \dots, n$}675 \State compute the distribution676 $p_\theta(x_i \mid x_1, \dots, x_{i-1})$677 \Comment{one forward pass}678 \State sample $x_i \sim p_\theta(x_i \mid x_1, \dots, x_{i-1})$679 \EndFor680 \State \Return $\vect{x} = (x_1, \dots, x_n)$681 \end{algorithmic}682\end{algorithm}683684\begin{remark}[Exactness versus sampling speed]\label{rem:agen-ar}685Among all generative families, autoregressive models and flows are the686only ones with \emph{exact} likelihoods. The price is paid at sampling687time: generation by Algorithm~\ref{alg:agen-ar} costs one network688evaluation per element, whereas a flow samples in a single pass. Diffusion689sits in between, with tens to thousands of passes depending on the sampler690\eqref{eq:agen-ddim}.691\end{remark}692693% ============================================================================694\section{Energy-Based Models: A Unifying Coda}695\label{sec:agen-ebm}696697Many of the threads above meet in the \emph{energy-based model} (EBM),698which drops all structural constraints and defines a density directly699through a scalar energy network $E_\theta$:700\begin{equation}701 p_\theta(\vect{x}) = \frac{e^{-E_\theta(\vect{x})}}{Z(\theta)},702 \qquad703 Z(\theta) = \int e^{-E_\theta(\vect{x})}\, d\vect{x}.704 \label{eq:agen-ebm}705\end{equation}706The partition function $Z(\theta)$ is intractable, but the707maximum-likelihood gradient takes a contrastive form that never requires708$Z$ itself:709\begin{equation}710 \nabla_\theta \log p_\theta(\vect{x})711 = -\nabla_\theta E_\theta(\vect{x})712 + \E_{\vect{x}' \sim p_\theta}713 \big[ \nabla_\theta E_\theta(\vect{x}') \big]714 \label{eq:agen-ebmgrad}715\end{equation}716— push the energy of real data down (positive phase), push the energy of717model samples up (negative phase). The negative samples $\vect{x}'$ are718drawn by Markov chain Monte Carlo, typically \emph{Langevin dynamics},719which follows the energy gradient with injected noise:720\begin{equation}721 \vect{x}_{k+1} = \vect{x}_k722 - \frac{\eta}{2} \nabla_{\vect{x}} E_\theta(\vect{x}_k)723 + \sqrt{\eta}\; \vect{\varepsilon}_k,724 \qquad \vect{\varepsilon}_k \sim \mathcal{N}(\vect{0}, \mat{I}).725 \label{eq:agen-langevin}726\end{equation}727728\begin{remark}[One object, many views]\label{rem:agen-unify}729Since $\nabla_{\vect{x}} \log p_\theta(\vect{x}) =730-\nabla_{\vect{x}} E_\theta(\vect{x})$, sampling an EBM by731\eqref{eq:agen-langevin} is exactly \emph{score following} — and the noise732predictor of a diffusion model is a scaled score estimate,733$\nabla_{\vect{x}_t} \log p(\vect{x}_t) =734-\vect{\varepsilon}_\theta(\vect{x}_t, t)/\sqrt{1-\bar{\alpha}_t}$.735Diffusion models can thus be read as EBMs whose sampling chain has been736fixed, annealed and amortized. Historically, the same positive/negative737phase structure of \eqref{eq:agen-ebmgrad} appeared in the Boltzmann738machines and restricted Boltzmann machines discussed earlier in this book,739trained by contrastive divergence; the modern generative families of this740chapter are, in that sense, their descendants.741\end{remark}742