Probability distributions over high-dimensional spaces suffer from an insurmountable combinatorial bottleneck: specifying an arbitrary joint distribution over $N$ binary random variables requires specifying $2^N – 1$ parameters. In the late 1980s, Judea Pearl and Steffen Lauritzen unified graph theory with probability theory, establishing Probabilistic Graphical Models (PGMs). By mapping conditional independence assertions directly to vertex connectivity, graphical models decompose intractable joint probability spaces into compact, factorized representations.
1. Directed Acyclic Graphs: Bayesian Networks
A Bayesian Network is a Directed Acyclic Graph (DAG) $G = (V, E)$ where vertices represent random variables $X_1, dots, X_N$ and directed edges represent direct statistical dependencies. The joint distribution factorizes as the product of conditional distributions of each node given its parents:
$$P(X_1, X_2, dots, X_N) = prod_{i=1}^N P(X_i mid text{Parents}(X_i))$$
If each node has at most $k$ parents, the parameter complexity collapses from $O(2^N)$ to $O(N cdot 2^k)$—enabling exact probabilistic inference across systems of thousands of variables.
2. Judea Pearl’s D-Separation Calculus
How can we determine whether two disjoint sets of variables $A$ and $B$ are conditionally independent given an observed evidence set $Z$ ($A perp B mid Z$)? In 1988, Judea Pearl formulated the d-separation (directional separation) criterion, classifying all three fundamental three-node path motifs:
- Causal / Inverted Chains ($X to Y to Z$ or $X leftarrow Y leftarrow Z$): Information flows freely between $X$ and $Z$ when $Y$ is unobserved. Conditioning on $Y$ blocks the path: $X perp Z mid Y$.
- Common Cause / Forks ($X leftarrow Y to Z$): $Y$ is a latent common cause inducing marginal correlation between $X$ and $Z$. Conditioning on $Y$ renders $X$ and $Z$ conditionally independent: $X perp Z mid Y$.
- Common Effect / Colliders ($X to Y leftarrow Z$): Crucially, marginal correlation is zero ($X perp Z$). However, conditioning on the collider $Y$ (or any of its descendants) activates the path, inducing dependence between $X$ and $Z$! This counterintuitive phenomenon is Berkson’s Paradox or “explaining away”.
Two sets $A$ and $B$ are d-separated by $Z$ if every undirected path between them is blocked. If $A$ and $B$ are d-separated by $Z$, they are conditionally independent under every probability distribution that factorizes over graph $G$.
3. Undirected Graphical Models: Markov Random Fields
When physical systems lack clear causal directionality—such as pixel interactions in computer vision or spin lattices in statistical physics—dependencies are modeled via Markov Random Fields (MRFs). An undirected graph represents conditional independence through simple graph separation: $A perp B mid Z$ if every path between $A$ and $B$ passes through node set $Z$.
How does an undirected graph factorize? The answer is dictated by the foundational Hammersley-Clifford Theorem (1971):
Hammersley-Clifford Theorem: A strictly positive probability distribution $P(X) > 0$ satisfies the Markov conditional independence properties of an undirected graph $G$ if and only if it factorizes as a Gibbs distribution over the maximal cliques $mathcal{C}$ of the graph:
$$P(X) = frac{1}{Z} prod_{C in mathcal{C}} psi_C(X_C) = frac{1}{Z} expleft( -sum_{C in mathcal{C}} E(X_C) right)$$
where $psi_C(X_C) ge 0$ are non-negative potential functions, $E(X_C)$ is the energy function, and $Z = sum_X prod_C psi_C(X_C)$ is the normalization partition function.
4. The Computational Challenge: Partition Functions and Inference
While graphical models make independence assumptions explicit, exact probabilistic inference—computing marginals $P(X_i)$ or posterior queries $P(X_i mid X_{text{observed}})$—requires marginalizing out unobserved variables. For general graphs containing multiple loops, computing the partition function $Z$ is strictly #P-complete.
This computational wall splits graphical models into two evolutionary trajectories: tree-structured graphs solvable in linear time via Pearl’s Belief Propagation (Sum-Product algorithm), and general cyclic loopy networks requiring approximate inference through Markov Chain Monte Carlo (MCMC) and Variational Bayes.
