Directed Graphical Models

Factorization

Let $G = (V, E)$ be a DAG and $X_v$, $v \in V$, random variables. A probability distribution $P$ factorizes according to $G$ if

$$P(X_V) = \prod_{v \in V} P\big(X_v \,\big|\, X_{\mathrm{pa}(v)}\big)$$

The factors are local probability models.

Sprinkler example $X$ is the season (0 dry, 1 wet), $S$ the sprinkler, $R$ rain, $W$ wet grass, with edges $X \to S$, $X \to R$, $S \to W$, $R \to W$.

$$P(X, S, R, W) = P(W | S, R)\, P(S | X)\, P(R | X)\, P(X)$$

Independence

A DAG $G = (V, E)$ encodes, for all $v \in V$,

$$X_v \perp X_{S_v} \,\big|\, X_{\mathrm{pa}(v)}, \qquad S_v = \big(\{v\} \cup \mathrm{desc}(v) \cup \mathrm{pa}(v)\big)^c = \text{ancestors (other than parents)} \cup \text{incomparable nodes}$$

$P$ factorizes over $G$ iff it satisfies these independence assertions.

d-Separation

For three nodes on a path through $B$:

• Causal chain $A \to B \to C$ or $A \leftarrow B \leftarrow C$: knowing $B$ blocks the path, $A \perp C \mid B$.
• Common cause $A \leftarrow B \to C$: knowing the shared parent $B$ blocks the path, $A \perp C \mid B$.
• Collision $A \to B \leftarrow C$: the path is blocked when nothing is known, so $A \perp C$, but knowing $B$ or any descendant of $B$ unblocks it, $A \not\perp C \mid B$.

If all paths between $X$ and $Y$ are blocked given $Z$, then $X \perp Y \mid Z$.

Compactness

For $n$ random variables with support $\{1, \ldots, r\}$, the full joint needs $r^n - 1 = O(r^n)$ parameters. If it factors with maximum in-degree $d$, it needs at most $n r^d (r-1) = O(n r^{d+1})$. If $d \ll n$, factorization is much better.

Examples of Factorization

Markov chain $X_{k+1} \perp X_1, \ldots, X_{k-1} \mid X_k$, so

$$P(x_1, \ldots, x_n) = P(x_1) \prod_{i=2}^{n} P(x_i | x_{i-1})$$

Naive Bayes $X_k \perp X_1, \ldots, X_{k-1}, X_{k+1}, \ldots, X_n \mid \text{Class}$, so

$$P(c, x_1, \ldots, x_n) = P(c) \prod_{i=1}^{n} P(x_i | c)$$

Mixture model

$$z_i \sim \mathrm{Categorical}(\pi_1, \ldots, \pi_K) \;\; (\text{class}), \qquad x_i \sim \mathcal{N}(\mu_{z_i}, \Sigma_{z_i}) \;\; (\text{observed}), \qquad \sum_{k=1}^{K} \pi_k = 1$$