Week 13: Graphical Models (lite)

Why Graphs#

In Week 4, we factored a joint distribution using the chain rule:

Without any assumptions, the conditioning set for $X_n$ includes $n-1$ variables. This is exponentially expensive — for binary variables, the full joint table has $2^n$ entries.

Structure saves us. Most real-world systems have sparse dependencies. A person's cholesterol level might depend on their diet and genetics, but not directly on the weather in a different city. Graphical models encode these sparsity assumptions explicitly through conditional independence statements, reducing the number of parameters from exponential to something manageable.

The core idea: missing edges in the graph $\iff$ conditional independence in the distribution.

Directed Models (Bayes Nets)#

A Bayesian network (Bayes net) is a directed acyclic graph (DAG) where:

• Nodes represent random variables $X_1, \ldots, X_n$.
• Edges $X_i \to X_j$ mean $X_i$ directly influences $X_j$.
• Each node has a conditional probability table (CPT) $P(X_i \mid \text{parents}(X_i))$.

The joint distribution factorises as:

The graph tells you the factorisation. Variables without parents have marginal (prior) distributions.

Worked example — 3-node chain. Rain $\to$ Sprinkler $\to$ Wet Grass:

• $P(R)$: probability of rain.
• $P(S \mid R)$: probability sprinkler is on, given rain or no rain.
• $P(W \mid S)$: probability grass is wet, given sprinkler on/off.

The joint factorises as:

Instead of $2^3 - 1 = 7$ free parameters for a full joint table, this model needs $1 + 2 + 2 = 5$ parameters — and the savings grow dramatically with more variables.

Causal interpretation (cautious): Directed edges can represent causal relationships, but not necessarily — they may just encode statistical dependence. In ML, treat the DAG as a factorisation device first; causal claims require stronger assumptions (do-calculus, beyond this course).

Undirected Models (Markov Random Fields)#

An undirected graphical model (Markov Random Field, or MRF) uses an undirected graph where:

• Nodes represent random variables.
• Edges represent direct probabilistic interaction (no directionality).
• The joint distribution factorises over cliques (fully connected subgraphs):

where $\psi_C \ge 0$ are potential functions (not probabilities — they need not sum to 1) and $Z = \sum_X \prod_C \psi_C(X_C)$ is the partition function (normaliser).

Key difference from Bayes nets:

• In a Bayes net, each factor $P(X_i \mid \text{parents})$ is a proper conditional probability that sums to 1.
• In an MRF, the potentials are arbitrary non-negative scores. The partition function $Z$ is needed to make the product a valid distribution.

The partition function problem: Computing $Z$ requires summing over all possible assignments of all variables — exponentially expensive in general. This is the central computational challenge of undirected models and appears in energy-based models, restricted Boltzmann machines, and the normalising flow literature.

When to use each:

• Directed: When there is a natural generative story — causes produce effects. Good for models with latent variables (e.g., topic models, HMMs).
• Undirected: When variables interact symmetrically — pixels in an image, atoms in a molecule, nodes in a relational network. No natural direction.

Reading Independencies (d-separation)#

In a DAG, we can read conditional independence statements directly from the graph using d-separation (directional separation). Three basic motifs cover the key patterns:

1. Chain: $A \to B \to C$#

$A$ and $C$ are marginally dependent (information flows through $B$). But given $B$, $A$ and $C$ are conditionally independent: $A \perp\!\!\!\perp C \mid B$. Knowing the intermediate variable blocks the path.

Example: Rain $\to$ Traffic $\to$ Late. If you know there's traffic, knowing it rained doesn't give additional information about lateness.

2. Fork: $A \leftarrow B \to C$#

$A$ and $C$ are marginally dependent (they share a common cause $B$). Given $B$, $A$ and $C$ become conditionally independent: $B$ "explains away" the correlation.

Example: Diet $\leftarrow$ Health-consciousness $\to$ Exercise. If you know someone is health-conscious, their diet and exercise are independent (conditionally).

3. Collider (v-structure): $A \to B \leftarrow C$#

$A$ and $C$ are marginally independent (no edge between them). But given $B$, they become dependent! This is "explaining away": if you know the common effect occurred, learning about one cause changes beliefs about the other.

Example: Skill $\to$ Job Offer $\leftarrow$ Luck. Skill and luck are independent in the population. But if you know someone got a job offer, and you also know they are unskilled, you infer they must have been lucky — conditioning on the collider creates dependence.

The basic d-separation rule: A path between $X$ and $Y$ is blocked (d-separated) given a set $Z$ if:

• There is a chain or fork with the middle node in $Z$, OR
• There is a collider where neither the collider nor any of its descendants are in $Z$.

$X$ and $Y$ are d-separated by $Z$ iff all paths between them are blocked — then $X \perp\!\!\!\perp Y \mid Z$.

ML Touchpoints#

Graphical models appear throughout modern ML, often implicitly:

• Naive Bayes (Week 5): A simple Bayes net with one class node pointing to all features. The missing edges between features encode the conditional independence assumption.
• Hidden Markov Models (HMMs): A chain-structured Bayes net for sequences — $X_1 \to X_2 \to X_3 \to \cdots$ with observations $Y_i$ depending on $X_i$. Used in speech recognition, genomics, and time-series modeling.
• Variational Autoencoders: The generative model $p(z) p(x \mid z)$ is a simple Bayes net with latent $z \to$ observed $x$. The inference network $q(z \mid x)$ flips the edge.
• Conditional Random Fields (CRFs): Undirected models for structured prediction (sequence labelling, image segmentation) — model $P(Y \mid X)$ with cliques over the output variables, conditioned on the input.
• Factor graphs: A more general representation (bipartite graph of variables and factors) used in message-passing algorithms and error-correcting codes.

This week teaches you to read these graphs, not to infer from them. Full inference algorithms (belief propagation, junction tree, variational message passing) are a separate advanced topic.

Knowledge check#

Browser lab#

Enumerate the joint distribution for a tiny 3-node discrete Bayes net and verify a marginal by enumeration.

import numpy as np
import matplotlib.pyplot as plt

# Bayes net: Rain (R) → Sprinkler (S) → Wet (W)
# P(R): [P(R=0), P(R=1)]
P_R = np.array([0.8, 0.2])
# P(S | R): rows=R, cols=S
P_S_given_R = np.array([[0.6, 0.4],
                         [0.1, 0.9]])
# P(W | S): rows=S, cols=W
P_W_given_S = np.array([[0.9, 0.1],
                         [0.05, 0.95]])

joint = np.zeros((2, 2, 2))
for r in range(2):
    for s in range(2):
        for w in range(2):
            joint[r, s, w] = P_R[r] * P_S_given_R[r, s] * P_W_given_S[s, w]

print("Joint P(R, S, W):")
for r in range(2):
    for s in range(2):
        for w in range(2):
            if joint[r, s, w] > 0.0001:
                print(f"  R={r}, S={s}, W={w}: {joint[r,s,w]:.4f}")

# Marginal P(W): sum over R, S
P_W_marginal = joint.sum(axis=(0, 1))
print(f"\nMarginal P(W=0) = {P_W_marginal[0]:.4f}")
print(f"Marginal P(W=1) = {P_W_marginal[1]:.4f}")

# P(W=1 | R=1) by enumeration
mask_R1 = joint[1, :, :]
P_W_given_R1 = mask_R1.sum(axis=0) / mask_R1.sum()
print(f"\nP(W=1 | R=1) = {P_W_given_R1[1]:.4f}")

fig, axes = plt.subplots(1, 2, figsize=(10, 4))
axes[0].bar(["Dry", "Wet"], P_W_marginal, color=["tab:green", "tab:blue"])
axes[0].set_title("Marginal P(W)")
axes[0].set_ylabel("Probability")

states = ["R=0,S=0", "R=0,S=1", "R=1,S=0", "R=1,S=1"]
P_W1_given = np.array([
    P_W_given_S[0, 1], P_W_given_S[1, 1],
    P_W_given_S[0, 1], P_W_given_S[1, 1]
])
axes[1].bar(states, P_W1_given, color="tab:blue", alpha=0.7)
axes[1].set_title("P(W=1 | S) — depends only on S")
axes[1].set_ylabel("Probability")
axes[1].tick_params(axis="x", rotation=45)

plt.tight_layout()
plt.show()