Last updated Aug 2026 · ML Theory
How directed graphs let us represent high-dimensional probability distributions compactly, and what independence assumptions a graph structure actually encodes.
Suppose we want to model the joint distribution over a handful of clinical variables collected from a patient monitor: heart rate, temperature, oxygen saturation, an infection indicator, and an alert flag. If each variable is binary, the joint distribution over 5 variables already has $2^5 - 1 = 31$ free parameters. With 20 variables, a realistic count for a richer monitoring setup, that number is over a million. By the chain rule, we can always write
\[p(x_1, x_2, \dotsc, x_n) = p(x_1)\, p(x_2 \mid x_1)\, p(x_3 \mid x_2, x_1) \cdots p(x_n \mid x_{n-1}, \dotsc, x_1),\]but this buys us nothing on its own: the last factor still conditions on every other variable, so we have not reduced the parameter count at all. The point of a graphical model is to make a modeling assumption explicit: each factor depends only on a small subset of the variables that precede it, not all of them.
A Bayesian network represents a joint distribution using a directed acyclic graph (DAG) $G = (V, E)$, together with one conditional probability distribution (CPD) per node. If $x_{A_i}$ denotes the parents of node $i$ in $G$, the network defines
\[p(x_1, \dotsc, x_n) = \prod_{i=1}^{n} p\left(x_i \mid x_{A_i}\right).\]We say a distribution $p$ factorizes over $G$ if it can be written this way. Each CPD is local: it only needs to account for a node’s direct parents, not its full history of ancestors. If every variable is discrete with $d$ values and has at most $k$ parents, each CPD table has at most $O(d^{k+1})$ entries, and the whole network needs only $O(n\, d^{k+1})$ parameters in total, compared to $O(d^n)$ for the unrestricted joint. The graph is doing real work: it is a compression scheme for the distribution, and the compression ratio is set entirely by how sparse the parent sets are.
Worked example. Take three of the monitor variables above: infection status $I$, temperature $T$, and an alert flag $A$ that fires when temperature crosses a threshold. A natural causal story is that infection status influences temperature, and temperature (not infection directly) drives the alert. The corresponding graph is $I \rightarrow T \rightarrow A$, and the factorization is
\[p(i, t, a) = p(i)\, p(t \mid i)\, p(a \mid t).\]Instead of a single 3-variable table, we now need only three small tables, one per node, each conditioned on at most one parent.
The more interesting question is which independencies a given graph structure implies. For a triple of variables $X, Y, Z$, there are three canonical structures, and it is worth internalizing all three because larger networks are built out of exactly these pieces.
These three patterns compose, via the more general criterion of d-separation, to tell us exactly which conditional independencies a graph implies for any pair of nodes. Getting comfortable reading independence off small structures like these is most of the work in reading larger graphs correctly, and it is the piece that later determines how cheaply we can do inference in the network, which is the subject of the next note.