Probabilistic Graphical Models

Bayesian networks, MRFs, d-separation, factor graphs, belief propagation, HMMs

High-dimensional joint distributions are intractable to work with directly — storing and computing over p(X₁,...,Xₙ) is exponential in n.

The key observation is that most real-world variables are not all directly dependent on each other. PGMs formalise this: encode which variables are independent of which using a graph structure, then factorise the joint into local potentials over connected subsets. Inference becomes a local message-passing operation over the graph rather than a global computation over the full joint. Bayesian networks use directed edges to encode generative causal stories; Markov Random Fields use undirected edges to encode symmetric correlations. PGMs largely ceded perception tasks to deep learning after 2012, but remain the right tool when conditional independence structure must be explicitly represented, audited, and explained — medical diagnosis networks, causal models, structured prediction with hard output constraints.

Key points

• Bayesian network: a DAG where each node Xᵢ has parents Pa(Xᵢ). The joint factorises as p(X₁,...,Xₙ) = Πᵢ p(Xᵢ | Pa(Xᵢ)). Every missing edge is a conditional independence assumption. The structure of the DAG is the entire modelling decision — it encodes your beliefs about the causal generating process. A fully connected DAG encodes no independence assumptions and offers no tractability benefit over the full joint.
• Markov Random Field (MRF): undirected graph, joint factorises over cliques: p(X) = (1/Z) Πc ψc(Xc). The partition function Z = Σ_X Πc ψc(Xc) sums over all configurations — typically intractable. This is the central computational problem for MRFs: you can write down the unnormalised joint, but normalising it requires the sum you are trying to avoid. MRFs encode symmetric correlations: image segmentation (neighbouring pixels tend to share labels), spatial statistics, Ising models.
• d-separation is the fundamental tool for reading conditional independence from a Bayesian network. X and Y are d-separated given Z if Z blocks all paths between them. Chains (X → m → Y) and forks (X ← m → Y) are blocked when m ∈ Z. Colliders (X → m ← Y) are blocked when m ∉ Z and no descendant of m is in Z. The collider rule is the surprising one: conditioning on a collider opens the path, creating a dependence that did not exist marginally. This is Berkson's paradox — the mechanism behind selection bias.
• Belief propagation (sum-product) on trees: messages pass between variable and factor nodes. After 2|E| message passes, every node's marginal is exact — you get p(Xᵢ) for every variable by multiplying incoming messages. On loopy graphs, the same algorithm (loopy BP) is an approximation that may not converge, but works well in practice for error-correcting codes and image segmentation. Tree structure is what makes BP exact; loops require approximation.
• HMM is a chain-structured Bayesian network. Hidden Markov chain s₁,...,s_T with transition p(s_t|s_{t-1}). Observations x_t ~ p(x_t|s_t). Forward-backward algorithm (BP on the chain): O(T·K²) to compute all marginals p(s_t|x₁,...,x_T). Viterbi (max-product): most likely state sequence. Baum-Welch (EM for HMMs): parameter learning. These three algorithms form the complete HMM toolkit — and each one is just belief propagation in a different form.
• Exact inference in general Bayesian networks is #P-hard. The junction tree algorithm handles tractable cases: moralise the DAG → triangulate → build a junction tree → run BP on the tree. Complexity is O(K^{treewidth+1} × n) where K is the state space size. Treewidth ≤ ~20 is usually feasible; most real-world networks have higher treewidth, making exact inference impossible and forcing approximations (loopy BP, VI, MCMC).
• Why PGMs lost perception tasks to deep learning after 2012: feature engineering burden (variables and structure had to be hand-specified), inference costs exponential in treewidth, and poor scalability compared to GPU-friendly neural networks. Why PGMs remain in use: auditable conditional independence structure that can be inspected and explained, structured prediction (CRFs for NER still competitive in low-resource settings), domain knowledge encoding in the graph topology, and causal analysis where the direction of edges has scientific meaning.
• CRFs (Conditional Random Fields) are the discriminative version of MRFs for structured prediction: p(Y|X) = (1/Z(X)) Πc ψc(Yc,X). The normaliser Z(X) conditions on input X, making it tractable for linear-chain CRFs via belief propagation. CRFs outperform generative HMMs for sequence labelling when input features are complex and when discriminative training is possible. Largely replaced by BERT fine-tuning for most NLP tasks, but remain relevant when structured output constraints must be hard-enforced.
• Treewidth determines inference complexity: trees (treewidth 1) allow exact inference in O(K² × n); grids (treewidth ≈ √n) require exponential cost per column. Real-world networks often have high treewidth because domain experts add edges to capture every dependency they can think of, creating highly connected graphs. The expressiveness-tractability tradeoff is fundamental to PGMs: every edge you add captures a dependency and potentially increases treewidth.

Recap

• PGMs factorise the joint via a graph — encode independence, turn global computation into local message passing.
• Bayes net = DAG: $p(X)=prod_i p(X_i|Pa(X_i))$, every missing edge is an independence assumption. MRF = undirected, cliques + intractable $Z$.
• Collider rule (the surprising one): conditioning on a collider $X→Z←Y$ opens the path — Berkson's paradox, the mechanism of selection bias.
• Belief propagation exact on trees ($2|E|$ passes); loopy BP on graphs with cycles is approximate but works in practice.
• HMM = chain Bayes net: forward-backward $O(T·K^2)$, Viterbi (best path), Baum-Welch (EM) — all just BP in different forms.
• Treewidth sets inference cost: junction tree $O(K^{tw+1})$; exact only for low treewidth, else loopy BP / VI / MCMC.
• Why PGMs faded then persist: lost perception to deep nets (feature/treewidth cost), but win when structure must be audited and explained.

Check your understanding