Bayesian Networks, Conditional Independence & D-Separation

A full joint probability distribution over n Boolean variables requires 2^n - 1 parameters, which is computationally intractable for large domains. Bayesian Networks (Belief Networks) exploit local conditional independence to represent distributions compactly.

Structure of a Bayesian Network:

1. A Directed Acyclic Graph (DAG) where nodes represent random variables X_i and directed edges represent direct statistical dependencies.

2. A Conditional Probability Table (CPT) for each node, specifying P(X_i \mid Parents(X_i)).

The Chain Rule of Bayesian Networks:

$P(X_1, X_2, ..., X_n) = \prod_{i=1}^n P(X_i \mid Parents(X_i))$

Parameter Efficiency: If a network has n Boolean variables and each node has at most k parents, the total number of parameters is at most n \cdot 2^k, scaling linearly with n instead of exponentially (2^n).

Two disjoint sets of nodes A and B are d-separated by conditioning set E (denoted A \perp B \mid E) if every undirected path between any node in A and any node in B is blocked.

A path is blocked by evidence set E if it contains at least one node V such that either:

1. V is a non-collider (chain X \to V \to Z or fork X ≤ftarrow V \to Z) and V \in E (i.e. V is observed), OR

2. V is a collider (X \to V ≤ftarrow Z) and neither V nor any descendant of V is in E (V \notin E and Descendants(V) \cap E = \emptyset).

Theorem: If A and B are d-separated by E, then A and B are conditionally independent given E: P(A, B \mid E) = P(A \mid E) P(B \mid E).

In a Bayesian Network, a node X is conditionally independent of all other nodes in the entire network given its Markov Blanket MB(X).

$MB(X) = Parents(X) \cup Children(X) \cup Spouses(X)$

Where Spouses are the other parents of X's children.

Why Spouses are Mandatory:

If child Y is in the conditioning set, the collider X \to Y ≤ftarrow Z is opened! Therefore, X and Z become dependent via 'explaining away'. To shield X completely from Z, spouse Z must also be conditioned on.