Conditional Independence and Bayesian Networks

The problem with full joint distributions

A complete probabilistic model of $n$ Boolean variables is the full joint distribution — $2^n - 1$ numbers. It answers any query by summing entries (marginalisation), but for 30 variables it needs about $10^9$ numbers: impossible to store, estimate or reason with.

Independence is the key to compactness:

• $X \perp Y$ (marginal independence): $P(X, Y) = P(X)P(Y)$.
• $X \perp Y \mid Z$ (conditional independence): $P(X, Y\mid Z) = P(X\mid Z)P(Y\mid Z)$, equivalently $P(X\mid Y, Z) = P(X\mid Z)$.

Conditional independence is far more common in practice: a toothache and a dentist's probe catching are dependent, but independent given whether there is a cavity. Naive Bayes is the simplest structure exploiting it (see naive Bayes).

Bayesian networks

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

• nodes are random variables;
• an edge $X \to Y$ means $X$ directly influences $Y$ (often causally);
• each node $X_i$ has a conditional probability table (CPT) $P(X_i\mid\text{Parents}(X_i))$.

The network represents the joint distribution as a product of local factors:

$$P(x_1, \dots, x_n) = \prod_{i=1}^n P\big(x_i\mid\text{parents}(X_i)\big).$$

Compactness

A Boolean node with $k$ Boolean parents needs $2^k$ CPT numbers. With $n$ nodes and at most $k$ parents each, the network needs $O(n2^k)$ numbers instead of $O(2^n)$.

Building a network: order the variables (causes before effects works best), and for each variable choose as parents a minimal set of predecessors that renders it independent of the other predecessors. A bad ordering (effects first) produces a denser, less intuitive network with more parameters — but it still represents the same distribution.

Independence in the graph

Local Markov property: each node is conditionally independent of its non-descendants given its parents.

The three connection types

Explaining away: two independent causes become dependent once their common effect is observed. If the alarm sounds, an earthquake report "explains" it and makes burglary less likely.

d-separation

Sets $X$ and $Y$ are d-separated by evidence $Z$ if every undirected path between them is blocked; then $X \perp Y \mid Z$ for every distribution the network represents. A path is blocked if it contains

• a chain or fork whose middle node is in $Z$, or
• a collider whose middle node is not in $Z$ and has no descendant in $Z$.

Markov blanket

Parents + children + children's other parents. Given its Markov blanket, a node is independent of everything else in the network.

Reasoning with a network

Any query $P(X\mid \mathbf e)$ can be answered from the factorisation by summing out the hidden variables — exactly, by enumeration or variable elimination, or approximately by sampling.

Quick revision