Structured Probabilistic Models

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.¹

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.²

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 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,

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.

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.

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.

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.

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.

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.³

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:

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.

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, ${\varphi }_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

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: 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$.⁴

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, $\varphi (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

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.

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.

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.

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.

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.

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.

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.

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 $\varphi (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.

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.

This is the natural language of latent-variable models. A variational autoencoder 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.⁶

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.

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/\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 approximate the intractable sums by sampling, and 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 $\mathrm{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_{\varphi }(z\mid x)$ fit by the same stochastic variational 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.