---
title: Structured Probabilistic Models
module: Probabilistic Methods
moduleNumber: 8
lessonNumber: 1
order: 801
summary: >
  A joint distribution over $n$ variables is a table with exponentially many
  entries; nobody can store it, fit it, or sample from it directly. Structure
  fixes this: a graph whose missing edges encode conditional independencies that
  factor the joint into small local pieces. We build the two dialects, directed
  (Bayesian networks) and undirected (Markov random fields), read independence off
  the graph, and connect the machinery to the latent-variable and energy-based
  models that power deep generative learning.
topics: [Probabilistic Methods]
sources:
  - book: Goodfellow
    ref: "Ch. 16 — Structured Probabilistic Models for Deep Learning"
  - book: Goodfellow
    ref: "§16.2 Using Graphs to Describe Model Structure; §16.5 Inference and Approximate Inference"
---

A generative model is, in the end, a claim about a joint distribution $p(x_1,
\dots, x_n)$. The trouble is the size of that object. If each of $n$ variables is
binary, the joint is a table with $2^n - 1$ free parameters, one per
configuration, less one for the normalization constraint. At $n = 100$ that is
$2^{100} - 1 \approx 10^{30}$ numbers. The table cannot be
stored, cannot be estimated from any finite sample, and cannot be summed over to
answer a query.[^gf-curse]

$$
\text{full joint over } n \text{ binary variables} \;\Longrightarrow\;
2^n - 1 \text{ free parameters.}
$$

Every tractable model achieves tractability by **leaving some interactions
unmodeled**: it asserts that most variables are conditionally independent of
most others. A graph is the bookkeeping device for those assertions: nodes are
random variables, and the _absence_ of an edge is an independence assertion. The
graph factors the unmanageable joint into a product of small local factors, each
over a handful of variables.[^gf-graphs]

> **Definition (Structured probabilistic model).** A probability distribution over
> many variables described by a graph $G$ whose nodes are the variables and whose
> edges encode direct interactions. The graph licenses a factorization of the joint
> into a product of factors, each over a small subset of variables, so the parameter
> count grows with the number of edges rather than with $2^n$. Also called a
> _graphical model_.

The same distribution admits two graphical representations, distinguished by whether
the edges carry arrows. They differ in what a factor _is_, how the product is
normalized, and how independence is read off the picture.

| | Directed (Bayesian network) | Undirected (Markov random field) |
| --- | --- | --- |
| Graph | DAG, arrows $x_i \to x_j$ | undirected edges |
| Factor | conditional $p(x_i \mid \mathrm{Pa}(x_i))$ | clique potential $\phi_C(x_C) \ge 0$ |
| Factorization | $\prod_i p(x_i \mid \mathrm{Pa}(x_i))$ | $\tfrac1Z \prod_C \phi_C(x_C)$ |
| Normalization | automatic ($Z=1$, each factor normalized) | global $Z = \sum_x \prod_C \phi_C(x_C)$ |
| Independence test | d-separation | graph separation |
| Sampling | ancestral (one forward pass, exact) | MCMC (iterative, approximate) |
| Natural for | causal / generative stories | soft symmetric constraints |
| Deep example | VAE, autoregressive models, sigmoid belief net | RBM, deep Boltzmann machine |

## Directed models: Bayesian networks

A directed model lays the variables out as a **directed acyclic graph** and reads
each variable as a conditional on its parents. The chain rule of probability is
always true and always useless,

$$
p(x_1, \dots, x_n) = \prod_{i=1}^{n} p\parens{x_i \mid x_1, \dots, x_{i-1}},
$$

because the $i$-th factor conditions on $i-1$ variables, the last one on all the
rest, recovering the full table. The directed model's single idea is that most of
that conditioning is _superfluous_: $x_i$ depends only on a small set of
**parents** $\mathrm{Pa}(x_i) \subseteq \{x_1, \dots, x_{i-1}\}$, and the rest drop
out.

> **Definition (Directed graphical model).** A distribution $p$ factorizes over a
> DAG $G$ when, for some ordering consistent with $G$,
> $$
> p(x_1, \dots, x_n) = \prod_{i=1}^{n} p\parens{x_i \mid \mathrm{Pa}(x_i)},
> $$
> where $\mathrm{Pa}(x_i)$ are the parents of node $i$ in $G$. Each factor is a
> _locally normalized_ conditional distribution, so the product is automatically a
> valid joint with $Z = 1$.

Consider a small diagnostic network: a season influences whether it rains and
whether the sprinkler runs; rain and sprinkler each wet the grass; wet grass makes
it slippery. Five variables, but each is governed only by its immediate causes.

$$
% caption: A directed model (Bayesian network): each node carries a conditional on its parents, and missing arrows are independence claims.
\begin{tikzpicture}[>=stealth, font=\small,
  v/.style={circle, draw, minimum size=11mm, inner sep=1pt}]
  \definecolor{acc}{HTML}{2348F2}
  \node[v, draw=acc, text=acc, thick] (s) at (0,2.4) {season};
  \node[v] (r) at (-2.4,0.6) {rain};
  \node[v] (k) at (2.4,0.6)  {sprink};
  \node[v] (w) at (0,-1.2)   {wet};
  \node[v] (l) at (0,-3.4)   {slip};
  \draw[->, thick] (s) -- (r);
  \draw[->, thick] (s) -- (k);
  \draw[->, thick] (r) -- (w);
  \draw[->, thick] (k) -- (w);
  \draw[->, thick] (w) -- (l);
  \node[align=left, font=\footnotesize, text=acc] at (5.1,0.6)
    {\texttt{one factor}\\\texttt{per node:}\\\texttt{a conditional}\\\texttt{on parents}};
\end{tikzpicture}
$$

With five binary variables the
full table needs $2^5 - 1 = 31$ numbers. The factored model needs only the entries
of its five conditional tables.

| Factor | Conditioning set | Independent entries |
| --- | --- | --- |
| $p(\text{season})$ | — | $1$ |
| $p(\text{rain} \mid \text{season})$ | $1$ parent | $2$ |
| $p(\text{sprink} \mid \text{season})$ | $1$ parent | $2$ |
| $p(\text{wet} \mid \text{rain}, \text{sprink})$ | $2$ parents | $4$ |
| $p(\text{slip} \mid \text{wet})$ | $1$ parent | $2$ |
| **total** | | $\mathbf{11}$ |

Eleven parameters instead of thirty-one, and the gap widens super-exponentially
as $n$ grows, provided the in-degree (number of parents) stays bounded. A node with
$k$ parents costs $2^k$ table entries, so the cost of a directed model is set by its
_widest_ conditional, not by $n$.

For example, hold the maximum in-degree fixed at $m = 2$ and let $n$
grow. The full joint over $n$ binary variables always needs $2^n - 1$ numbers; a
directed model with at most two parents per node needs at most $n \cdot 2^2 = 4n$.
At $n = 20$ that is a million versus eighty; at $n = 40$, a trillion versus a
hundred and sixty. The structured representation is linear in $n$; the unstructured
one is exponential.

$$
% caption: Parameter count, full joint versus a directed model with in-degree at most two, over $n$ binary variables. The full table grows as $2^n-1$; the structured model grows as $4n$. Vertical axis is $\log_{10}$ of the parameter count.
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  % axes
  \draw[->, thick] (0,0) -- (7.4,0) node[right, font=\footnotesize] {n};
  \draw[->, thick] (0,0) -- (0,5.2) node[above, font=\footnotesize] {log10 params};
  % y ticks: 0,3,6,9,12 -> scaled by 0.4 per unit
  \foreach \y/\lab in {0/0,1.2/3,2.4/6,3.6/9,4.8/12} {
    \draw (-0.08,\y) -- (0.08,\y);
    \node[left, font=\scriptsize] at (-0.12,\y) {\lab};
  }
  % x ticks: n = 0,10,20,30,40 -> 0,1.75,3.5,5.25,7 (0.175 per n)
  \foreach \x/\lab in {0/0,1.75/10,3.5/20,5.25/30,7/40} {
    \draw (\x,-0.08) -- (\x,0.08);
    \node[below, font=\scriptsize] at (\x,-0.12) {\lab};
  }
  % full joint: log10(2^n - 1) approx n*0.301; y-scale 0.4/unit, x-scale 0.175/n
  % point (n, 0.4*0.301*n) = (0.175 n, 0.12 n) -> slope in fig: 0.12/0.175
  \draw[acc, very thick] (0,0) -- (7,4.8);
  \node[acc, right, font=\footnotesize] at (1.35,4.7) {\texttt{full: 2\^{}n - 1}};
  % structured 4n: log10(4n). points at n=5:1.30, 10:1.60, 20:1.90, 40:2.20
  % y = 0.4*log10(4n); x = 0.175 n
  \draw[black, very thick]
    (0.35,0.48) -- (0.875,0.64) -- (1.75,0.76) -- (3.5,0.88) -- (7,1.0);
  \node[black, right, font=\footnotesize] at (5.4,1.25) {\texttt{structured: 4n}};
\end{tikzpicture}
$$

> **Theorem (Cost of a directed model).** If every node in a directed model over
> $n$ discrete variables, each taking $v$ values, has at most $m$ parents, the model
> is specified by at most $n\,(v-1)\,v^{m}$ parameters: linear in $n$ and
> exponential only in the bounded in-degree $m$, never in $n$.

> **Proof.** Each node $x_i$ contributes one conditional table $p(x_i \mid
> \mathrm{Pa}(x_i))$. The conditioning set takes at most $v^{m}$ joint values; for
> each, the distribution over the $v$ outcomes of $x_i$ has $v-1$ free entries.
> Hence node $i$ costs at most $(v-1)v^{m}$ parameters, and summing over $n$ nodes
> gives $n\,(v-1)\,v^{m}$. The bound is independent of $n$ in the exponent. $\qed$

### Ancestral sampling

A directed model is _trivial_ to sample from. Because the factorization respects a
topological order, you can draw each variable once its parents are fixed: a single
forward sweep, with no rejection and no iteration.

```algorithm
caption: $\textsc{AncestralSample}(G)$ — exact sampling from a directed model
sort nodes in topological order $x_1, \dots, x_n$ // parents before children
for $i \gets 1$ to $n$ do
  look up the conditional $p(x_i \mid \mathrm{Pa}(x_i))$ // parents already drawn
  $x_i \sim p(x_i \mid \mathrm{Pa}(x_i))$ // sample one value
return $(x_1, \dots, x_n)$
```

The correctness is immediate: when the loop reaches $x_i$ all of $\mathrm{Pa}(x_i)$
are already sampled, so the conditional is fully determined, and the product of the
draws is exactly $\prod_i p(x_i \mid \mathrm{Pa}(x_i)) = p(x)$. This is why deep
autoregressive models (pixel-by-pixel or token-by-token generators) are directed
models: each variable conditions on the prefix before it, and
generation is one ancestral pass.[^gf-directed]

For example, run one pass over the sprinkler network. Take
$p(\text{season} = \text{summer}) = 0.5$, then read down the graph in topological
order. In summer, rain is rare and the sprinkler runs often:

$$
\begin{aligned}
\text{season} &\sim (\text{summer}: 0.5,\ \text{winter}: 0.5)
  &&\Rightarrow \text{draw summer},\\
\text{rain} \mid \text{summer} &\sim (\text{yes}: 0.1,\ \text{no}: 0.9)
  &&\Rightarrow \text{draw no},\\
\text{sprink} \mid \text{summer} &\sim (\text{on}: 0.8,\ \text{off}: 0.2)
  &&\Rightarrow \text{draw on},\\
\text{wet} \mid (\text{rain}=\text{no},\, \text{sprink}=\text{on})
  &\sim (\text{yes}: 0.9,\ \text{no}: 0.1)
  &&\Rightarrow \text{draw yes},\\
\text{slip} \mid \text{wet}=\text{yes} &\sim (\text{yes}: 0.7,\ \text{no}: 0.3)
  &&\Rightarrow \text{draw yes}.
\end{aligned}
$$

The sample is $(\text{summer}, \text{no rain}, \text{sprinkler on}, \text{wet},
\text{slippery})$, and its probability under the model is the product of the five
conditionals actually used, $0.5 \times 0.9 \times 0.8 \times 0.9 \times 0.7 =
0.2268$. Every draw used only the values already fixed above it, with no rejection
and no iteration. This is the main appeal of the directed form, and it still holds
when the conditional tables are replaced by neural networks: an
autoregressive image model draws pixel $x_i$ from $p_\theta(x_i \mid x_{<i})$, a
network evaluated on the pixels drawn so far, in one raster-order sweep.

## Undirected models: Markov random fields

Some interactions have no natural direction. Whether two adjacent pixels share a
label, whether two atoms in a molecule are compatible, whether two people in a
social network agree: these are _symmetric_ affinities, and forcing an arrow onto
them is artificial. An **undirected model** drops the arrows and replaces
conditionals with non-negative **potentials** over the **cliques** of the graph.

> **Definition (Clique).** A clique $C$ of an undirected graph is a set of nodes
> that are all pairwise connected. A _maximal_ clique is one not contained in any
> larger clique. Undirected factorizations are products of one factor per (maximal)
> clique.

> **Definition (Undirected graphical model / MRF).** A distribution over an
> undirected graph $G$ factorizes as
> $$
> p(x) = \frac{1}{Z} \prod_{C \in \mathcal{C}} \phi_C(x_C),
> \qquad
> Z = \sum_{x} \prod_{C \in \mathcal{C}} \phi_C(x_C),
> $$
> where $\mathcal{C}$ is the set of cliques, each **potential** $\phi_C(x_C) \ge 0$
> scores the joint configuration of the variables in $C$, and the **partition
> function** $Z$ renormalizes the product into a distribution. Potentials are
> _not_ probabilities — only their normalized product is.

$$
% caption: An undirected model (Markov random field): the shaded maximal clique $\{a,b,c\}$ carries one potential, and edges are symmetric affinities, not causes.
\begin{tikzpicture}[>=stealth, font=\small,
  v/.style={circle, draw, minimum size=10mm, inner sep=1pt}]
  \definecolor{acc}{HTML}{2348F2}
  % shaded clique region inset behind a,b,c (edges pass between the nodes)
  \fill[acc!15] (-1.55,1.46) -- (-0.21,2.30) -- (-0.19,0.41) -- cycle;
  \draw[acc, thick] (-1.55,1.46) -- (-0.21,2.30) -- (-0.19,0.41) -- cycle;
  \node[v] (a) at (-2.0,1.5) {a};
  \node[v] (b) at (0,2.7)    {b};
  \node[v] (c) at (0,0)      {c};
  \node[v] (d) at (2.2,0.9)  {d};
  \node[v] (e) at (2.2,-1.5) {e};
  \draw[thick] (a) -- (b);
  \draw[thick] (b) -- (c);
  \draw[thick] (a) -- (c);
  \draw[thick] (c) -- (d);
  \draw[thick] (d) -- (e);
  \node[text=acc, font=\footnotesize] at (-1.4,0.55) {clique};
  \node[align=left, font=\footnotesize, text=acc] at (4.5,0.3)
    {\texttt{one potential}\\\texttt{per clique:}\\\texttt{a triangle}\\\texttt{plus two edges}};
\end{tikzpicture}
$$

### Energy and the Gibbs form

Potentials must stay non-negative, which is awkward to enforce during learning. The
standard fix is to write each potential as the exponential of a negative **energy**,
$\phi_C(x_C) = \exp(-E_C(x_C))$. The product of exponentials becomes an exponential
of a sum, and the model takes the **Gibbs** (Boltzmann) form

$$
p(x) = \frac{1}{Z}\exp\!\parens{-\sum_{C} E_C(x_C)} = \frac{1}{Z}\,e^{-E(x)},
\qquad
E(x) = \sum_{C} E_C(x_C),
$$

with $Z = \sum_x e^{-E(x)}$. Now any real-valued $E$ gives a valid
non-negative potential, and the total energy is a _sum of local terms_, exactly
the structure a neural network can parameterize. This is the bridge to
[energy-based and Boltzmann machines](/deep-learning/generative-models/energy-based-and-boltzmann-machines):
an RBM is an undirected model whose only cliques are the visible–hidden edges, with
a bilinear energy $E(v,h) = -v^{T}Wh - b^{T}v - c^{T}h$.[^gf-energy]

> **Theorem (Hammersley–Clifford).** A strictly positive distribution $p(x) > 0$
> satisfies the conditional independencies of an undirected graph $G$ — each
> variable is independent of all others given its neighbors — if and only if it
> factorizes as a product of potentials over the cliques of $G$. Positivity is
> essential; without it the equivalence can fail.

The cost of the undirected form is that $Z$ couples _everything_. Unlike the
directed case, where each factor is self-normalizing, the undirected factors are
unnormalized, so computing any probability or marginal requires the global sum
$Z$ over all $2^n$ configurations.

For example, consider a two-variable Ising-style model.
Take binary $x_1, x_2 \in \{0, 1\}$ with one pairwise potential that
rewards agreement, $\phi(x_1, x_2) = \exp(x_1 x_2)$, so agreement on $1$ scores
$e^1$ and every other configuration scores $e^0 = 1$. The unnormalized weights and
their sum are

$$
\begin{array}{c|c|c}
(x_1, x_2) & \phi(x_1,x_2) & \text{value}\\ \hline
(0,0) & e^{0} & 1\\
(0,1) & e^{0} & 1\\
(1,0) & e^{0} & 1\\
(1,1) & e^{1} & e \approx 2.718
\end{array}
\qquad
Z = 3 + e \approx 5.718.
$$

Only after dividing by $Z$ do the weights become probabilities: $p(1,1) = e/Z
\approx 0.475$, and each of the other three configurations gets $1/Z \approx
0.175$. The agreement bias made $(1,1)$ almost half the mass. For two variables the
sum ran over $4$ terms and cost nothing. For $n$ binary variables it runs over
$2^n$ terms, and no factorization of the potentials makes the sum decompose, because
the single scalar $Z$ sits under every configuration at once. Approximating this sum
is what Monte-Carlo estimation exists to do.

> **Definition (Partition function $Z$).** The normalizing constant
> $Z(\theta) = \sum_{x} \prod_C \phi_C(x_C)$ that makes an undirected model a
> distribution. Its gradient $\nabla_\theta \log Z = \mathbb{E}_{x \sim p}[\nabla_\theta
> \log \tilde p(x)]$ is an expectation under the model itself, so $Z$ is generally
> intractable and is the central obstruction to training undirected models, the
> problem that
> [Monte Carlo and MCMC](/deep-learning/probabilistic-methods/monte-carlo-and-mcmc)
> methods exist to attack.

| | Directed | Undirected |
| --- | --- | --- |
| Local factor normalized? | yes — each $p(x_i \mid \mathrm{Pa})$ sums to $1$ | no — potentials are arbitrary $\ge 0$ |
| Global $Z$ needed? | no, $Z = 1$ | yes, $Z = \sum_x \prod_C \phi_C$ |
| Marginal $p(x_i)$ | sum out, factors help | needs $Z$ — intractable in general |
| Sampling | ancestral, exact, one pass | MCMC, approximate, iterative |

## Conditional independence and separation

The entire payoff of a graph is that you can _read independencies off it_ without
touching the numbers. The rule differs between directed and undirected models.

### Undirected: graph separation

For undirected models the rule is the one the eye expects. Two sets of variables
$A$ and $B$ are independent given $C$ exactly when $C$ blocks every path between
them: remove the nodes of $C$ and ask whether $A$ and $B$ fall into disconnected
pieces.

> **Definition (Graph separation).** In an undirected graph, $A$ is separated from
> $B$ by $C$ if every path from a node in $A$ to a node in $B$ passes through some
> node of $C$. Separation in $G$ implies the conditional independence
> $A \perp B \mid C$ in every distribution that factorizes over $G$.

### Directed: d-separation

Directed models are subtler, because an _observed_ node sometimes blocks a path and
sometimes _opens_ one. Three local configurations exhaust the cases. Read each as a
path from $a$ to $b$ through a middle node $m$, asking whether observing $m$ blocks
the flow of dependence.

| Structure | Shape | Path through $m$ is blocked when |
| --- | --- | --- |
| Chain | $a \to m \to b$ | $m$ **is** observed |
| Fork | $a \leftarrow m \to b$ | $m$ **is** observed |
| Collider | $a \to m \leftarrow b$ | $m$ is **not** observed (nor any descendant) |

The collider inverts the rule: a common _effect_ left unobserved keeps its causes
independent, but observing the effect makes them dependent — "explaining away." If
the grass is wet and you learn it rained, you lower your belief that the sprinkler
ran, even though rain and sprinkler had no prior link.

$$
% caption: D-separation in a chain $a \to m \to b$: observing the middle node $m$ (shaded) blocks the only path, so $a \perp b \mid m$.
\begin{tikzpicture}[>=stealth, font=\small,
  v/.style={circle, draw, minimum size=11mm, inner sep=1pt}]
  \definecolor{acc}{HTML}{2348F2}
  \node[v] (a) at (0,0) {a};
  \node[v, fill=acc!15, draw=acc, very thick] (m) at (3,0) {m};
  \node[v] (b) at (6,0) {b};
  \draw[->, thick] (a) -- (m);
  \draw[->, thick] (m) -- (b);
  \node[font=\footnotesize, text=acc] at (3,-1.3) {observed};
  \node[font=\footnotesize, align=center] at (3,1.55) {path blocked};
  \node[font=\footnotesize, text=acc] at (3,-2.3) {$a$ and $b$ independent given $m$};
\end{tikzpicture}
$$

> **Definition (d-separation).** In a DAG, a path from $a$ to $b$ is _blocked_ by an
> observed set $C$ if it contains a chain $a \to m \to b$ or fork $a \leftarrow m
> \to b$ with $m \in C$, or a collider $a \to m \leftarrow b$ with neither $m$ nor
> any of its descendants in $C$. Sets $A$ and $B$ are d-separated by $C$ when _every_
> path between them is blocked; d-separation implies $A \perp B \mid C$.

The collider is the counterintuitive case. In the sprinkler network, rain and
sprinkler have no edge between them, so unconditionally they are independent: the
season aside, whether it rained tells you nothing about whether the sprinkler ran.
But condition on their common effect, wet grass, and the two become coupled. If the
grass is wet and you learn it did not rain, the sprinkler must account for the water,
so its probability jumps. Observing a shared effect makes its causes compete to
explain it. The wet-grass node is a collider on the path rain $\to$ wet $\leftarrow$
sprinkler, and conditioning on it _opens_ that path rather than closing it.

$$
% caption: The collider (explaining-away) pattern: rain and sprinkler are marginally independent, but observing their common effect wet (shaded) couples them, so the path is open exactly when the middle node is observed. Contrast the chain and fork, where observing the middle node closes the path.
\begin{tikzpicture}[>=stealth, font=\small,
  v/.style={circle, draw, minimum size=10mm, inner sep=1pt}]
  \definecolor{acc}{HTML}{2348F2}
  \node[v] (a) at (0,0) {rain};
  \node[v] (b) at (4.2,0) {sprk};
  \node[v, fill=acc!15, draw=acc, very thick] (m) at (2.1,-1.9) {wet};
  \draw[->, thick] (a) -- (m);
  \draw[->, thick] (b) -- (m);
  \node[font=\footnotesize, text=acc] at (2.1,-3.2) {\texttt{observed: path OPEN}};
  \node[font=\footnotesize, align=center] at (2.1,0.75)
    {\texttt{rain and sprk dependent given wet}};
\end{tikzpicture}
$$

The two notions of separation are not interchangeable: there are independence
patterns a directed graph can express that no undirected graph can, and vice versa.
The collider's "explaining away" is the canonical thing undirected separation cannot
capture, since undirected separation can never make conditioning _create_ a
dependence.

### The Markov blanket

Each rule above answers a global question about paths. There is a local shortcut that
names, for a single variable, the exact set that renders it independent of the whole
rest of the graph. That set is its **Markov blanket**.

> **Definition (Markov blanket).** The Markov blanket $\mathrm{MB}(x_i)$ of a variable
> is the smallest set of nodes that makes $x_i$ conditionally independent of every
> other variable: $x_i \perp x_j \mid \mathrm{MB}(x_i)$ for all $x_j \notin
> \mathrm{MB}(x_i) \cup \{x_i\}$. In an undirected graph it is just the **neighbors**
> of $x_i$. In a directed graph it is larger: the **parents**, the **children**, and
> the **co-parents** (the other parents of $x_i$'s children).

The co-parents are there precisely because of the collider. A child of $x_i$ is a
collider on the path from $x_i$ to that child's other parents; conditioning on the
child (which the blanket does) opens that path, so the co-parents must be included to
close it back up. This local set is what Gibbs sampling conditions on when it resamples
one variable at a time: to update $x_i$ you need only its blanket, never the full
graph.

$$
% caption: The Markov blanket of the center node in a directed graph: its parents, its children, and the co-parents (other parents of its children). Shaded nodes are the blanket; given them, the center is independent of everything outside.
\begin{tikzpicture}[>=stealth, font=\small,
  v/.style={circle, draw, minimum size=9mm, inner sep=1pt},
  mb/.style={circle, draw=acc, fill=acc!15, very thick, minimum size=9mm, inner sep=1pt}]
  \definecolor{acc}{HTML}{2348F2}
  \node[v, draw=acc, text=acc, very thick] (x) at (0,0) {x};
  \node[mb] (p1) at (-2.2,1.8) {p1};
  \node[mb] (p2) at (2.2,1.8) {p2};
  \node[mb] (c1) at (-2.2,-1.8) {c1};
  \node[mb] (c2) at (2.2,-1.8) {c2};
  \node[mb] (co) at (4.6,-0.4) {co};
  \node[v] (out) at (5.0,2.2) {far};
  \draw[->, thick] (p1) -- (x);
  \draw[->, thick] (p2) -- (x);
  \draw[->, thick] (x) -- (c1);
  \draw[->, thick] (x) -- (c2);
  \draw[->, thick] (co) -- (c2);
  \draw[->, thick] (p2) -- (out);
  \node[font=\footnotesize, text=acc, align=center] at (0,-3.3)
    {\texttt{shaded = blanket: parents, children, co-parents}};
\end{tikzpicture}
$$

## Factor graphs

The undirected picture leaves one ambiguity: the graph shows which variables share a
clique, but not how the potentials are grouped. A triangle $\{a,b,c\}$ might carry
one ternary potential $\phi(a,b,c)$ or three pairwise potentials, and the undirected
graph cannot tell them apart. A **factor graph** removes the ambiguity by drawing
the factors as nodes in their own right.

> **Definition (Factor graph).** A bipartite graph with two kinds of node:
> _variable_ nodes (circles) and _factor_ nodes (squares). A factor node $f$ is
> connected to exactly the variables in its scope, and the distribution is
> $p(x) = \tfrac1Z \prod_f f(x_{\partial f})$, where $\partial f$ is the set of
> variables adjacent to $f$. The factor graph makes the factorization _explicit_,
> the structure message-passing inference (belief propagation) needs.[^gf-factor]

$$
% caption: A factor graph: variable nodes (circles) and factor nodes (squares), with each factor edged to the variables in its scope, making the potential grouping explicit.
\begin{tikzpicture}[>=stealth, font=\small,
  v/.style={circle, draw, minimum size=9mm, inner sep=1pt},
  f/.style={rectangle, draw, fill=acc!15, minimum size=6mm, inner sep=1pt}]
  \definecolor{acc}{HTML}{2348F2}
  \node[v] (a) at (0,0)   {a};
  \node[f, draw=acc, very thick] (f1) at (1.6,0) {$f_1$};
  \node[v] (b) at (3.2,0) {b};
  \node[f, draw=acc, very thick] (f2) at (4.8,0) {$f_2$};
  \node[v] (c) at (6.4,0) {c};
  \node[f, draw=acc, very thick] (f3) at (8.0,0) {$f_3$};
  \node[v] (d) at (9.6,0) {d};
  \draw[thick] (a) -- (f1);
  \draw[thick] (f1) -- (b);
  \draw[thick] (b) -- (f2);
  \draw[thick] (f2) -- (c);
  \draw[thick] (c) -- (f3);
  \draw[thick] (f3) -- (d);
  \node[font=\footnotesize, text=acc] at (4.8,-1.35) {squares = factors, circles = variables};
\end{tikzpicture}
$$

## Plate notation

Models with repeated structure (one factor per data point, per pixel, per time
step) would be unreadable drawn out node by node. **Plate notation** compresses a
repeated subgraph into a rectangle (a _plate_) annotated with the repetition count.
Everything inside the plate is replicated; edges crossing the boundary connect the
shared parameters to every copy.

$$
% caption: Plate notation: the rectangle labelled $N$ means "repeat $N$ times", so one drawing of $z$ and $x_n$ under shared $\theta$ stands for $N$ independent copies.
\begin{tikzpicture}[>=stealth, font=\small,
  v/.style={circle, draw, minimum size=11mm, inner sep=1pt}]
  \definecolor{acc}{HTML}{2348F2}
  % shared parameter outside the plate
  \node[v, draw=acc, text=acc, thick] (th) at (0,-1.0) {param};
  % the plate
  \draw[thick] (1.7,-2.6) rectangle (6.4,1.0);
  \node[font=\footnotesize, anchor=south east] at (6.3,-2.55) {\texttt{repeat N times}};
  \node[v] (z) at (3.1,-0.2) {z};
  \node[v, fill=acc!15, draw=acc, very thick] (x) at (5.2,-0.2) {x};
  \draw[->, thick] (z) -- (x);
  \draw[->, thick] (th) .. controls (1.3,0.4) and (2.0,0.4) .. (z);
  \draw[->, thick] (th) .. controls (1.3,-2.0) and (3.6,-2.0) .. (x);
  \node[font=\footnotesize, text=black] at (5.2,-1.4) {\texttt{observed}};
  \node[font=\footnotesize] at (3.1,-1.15) {\texttt{latent}};
\end{tikzpicture}
$$

This is the natural language of latent-variable models. A
[variational autoencoder](/deep-learning/generative-models/variational-autoencoders)
is precisely the plate above: a per-datum latent $z_n$ drawn from a prior, decoded
into the observation $x_n$ by a shared network $\theta$, with the plate standing for
the whole dataset. The shaded node is observed; the unshaded one is the latent the
model must infer.[^chollet-vae]

## Why deep learning leans on these models

Deep generative models are graphical models with neural networks standing in for the
factors. The graph supplies the _independence structure_; the network supplies the
_parameterization_ of each conditional or potential.

| Deep model | Graphical type | What the network parameterizes |
| --- | --- | --- |
| VAE | directed, latent $z \to x$ | the decoder $p_\theta(x \mid z)$ and encoder $q_\phi(z \mid x)$ |
| Autoregressive (PixelCNN, GPT) | directed chain | each $p(x_i \mid x_{<i})$ |
| Sigmoid belief net | directed, deep latents | layer conditionals $p(x_i \mid \mathrm{Pa})$ |
| RBM | undirected, bipartite | bilinear energy $E(v,h)$ |
| Deep Boltzmann machine | undirected, layered | stacked bilinear energies |

Three structural lessons carry through the rest of this module:

- **Latent variables** add explanatory structure cheaply. A single hidden node
  $z$ pointing at many observed nodes induces _marginal_ dependence among them
  ($x_i \not\perp x_j$) while keeping them _conditionally_ independent given $z$
  ($x_i \perp x_j \mid z$): the fork pattern, run as a generative model.
- **Directed models sample easily but can be hard to fit** when latents must be
  marginalized; **undirected models specify constraints flexibly but are hard to
  sample and normalize** because of $Z$. Most deep generative research is a way
  around one of these two costs.
- **Inference** (computing $p(z \mid x)$ or a marginal) **is the hard operation**, and
  it is intractable in general for both dialects. The two remaining lessons take it
  head-on: [Monte Carlo and
  MCMC](/deep-learning/probabilistic-methods/monte-carlo-and-mcmc) approximate the
  intractable sums by sampling, and [approximate
  inference](/deep-learning/probabilistic-methods/approximate-inference) replaces the
  true posterior with a tractable surrogate.

The graph, in the end, is a specification: it states exactly which dependencies the
model is allowed to use, and everything downstream (the parameter count, the sampling
algorithm, the inference cost) is a consequence of where the edges are and where,
deliberately, they are not.

## From hand-drawn graphs to learned structure

Goodfellow presents the graph as given — an expert draws the edges. Two developments
since automate that step and scale the machinery to the deep era.

**Structure learning** treats the graph itself as a quantity to estimate from data.
The classical formulation (Koller & Friedman, 2009, _Probabilistic Graphical Models_,
the field's standard reference) scores candidate DAGs by penalized likelihood and
searches the combinatorial space of graphs — but that search is $\mathrm{NP}$-hard,
because the acyclicity constraint is discrete. **NOTEARS** (Zheng et al., 2018,
_NeurIPS_) reframed it as a smooth optimization: acyclicity of a weighted adjacency
matrix $W$ holds exactly when $\tr(e^{W \circ W}) - d = 0$, a
differentiable constraint, so gradient methods can learn a DAG end-to-end. The
independence structure this lesson reads off a given graph becomes something
estimated from data.

**Probabilistic programming** turns the plate diagrams into executable code. Systems
like Pyro (Bingham et al., 2019, _JMLR_, built on PyTorch) let you write the generative
story as a program — sample a latent, decode it, observe the data — and then run
gradient-based variational inference or MCMC over it automatically. A VAE is a few lines
in this style: the plate model of the previous section, with the shared decoder a neural
network and the posterior $q_\phi(z \mid x)$ fit by the same
[stochastic variational inference](/deep-learning/probabilistic-methods/approximate-inference)
this module builds toward. The graphical-model structure is unchanged; what changed is
that the factors are neural networks and the inference is compiled, not derived by hand.

In all three settings the graph fixes the independencies — whether an expert draws
it, an optimizer learns it, or a program declares it — and the factorization it
licenses is what makes an otherwise $2^n$-parameter object learnable at all.

[^gf-curse]: **Goodfellow**, _Deep Learning_, §16.1 — The Challenge of Unstructured Modeling: the $2^n$ blow-up in memory, statistics, and inference that motivates structured representations.
[^gf-graphs]: **Goodfellow**, _Deep Learning_, §16.2 — Using Graphs to Describe Model Structure: nodes as variables, missing edges as conditional-independence assertions, and the resulting factorization.
[^gf-directed]: **Goodfellow**, _Deep Learning_, §16.2.1 — Directed Models: the DAG factorization $\prod_i p(x_i \mid \mathrm{Pa}(x_i))$ and ancestral sampling, the substrate of autoregressive generators.
[^gf-energy]: **Goodfellow**, _Deep Learning_, §16.2.4 — Energy-Based Models: the Gibbs form $p(x)=\tfrac1Z e^{-E(x)}$ and the visible–hidden energy of the RBM.
[^gf-factor]: **Goodfellow**, _Deep Learning_, §16.2.3 — Factor Graphs: the bipartite variable/factor representation that disambiguates how potentials are grouped.
[^chollet-vae]: **Chollet**, _Deep Learning with Python_, Ch. 12 — Generative Deep Learning: the VAE as a per-datum latent decoded by a shared network, the plate model made concrete in Keras.