Bayesian Network Representation

D-separation

A method to determine if two nodes are conditionally independent given a set of other nodes in a directed graph.

The goal is to understand when can we guarantee that an independence $X\perp Y\mid Z$ holds in a distribution associated with a BN structure $G$.

Types of connections between X and Y

Direct connection: if $X$ and $Y$ are directly connected $X\to Y$, they can always influence each other regardless of evidence $Z$. Information can transmit over the edge. This means that changes in $X$ can directly cause changes in $Y$, and vice versa, without the need for any intermediate variables.

Indirect connection between $X$ and $Y$: a simple three-node network, there are four cases:

Indirect Causal Effect

• A. If G is observed, I and L are independent ($I\perp L\mid G$).
• B. If G is not observed, I influences L through G.
• Causal trail $X\to Z\to Y$ is active if (if and only if) Z is NOT observed;

Indirect Evidential Effect

• A. Observing L affects beliefs about I.
• B. Observing G blocks the effect of L on I.
• Evidential trail $X\leftarrow Z\leftarrow Y$ is active iff Z is NOT observed;

Common Cause

• A. G and S are correlated if I is not observed.
• B. Observing I blocks the path between G and S.
• Common cause $X\leftarrow Z\to Y$ is active iff Z is NOT observed;

Common Effect

• A. I and D are independent if G is not observed.
• B. Observing G (hard evidence) makes I and D correlated.
• C. Observing a descendant of G (like L) also makes I and D correlated.
• D. Explaining away occurs: observing G or its descendant affects beliefs in both I and D.
• Common effect $X\to Z\leftarrow Y$ is active iff either Z or Z’s descendant is observed.

General Cases:

A longer trail $X_1\Rightarrow \cdots \Rightarrow X_n$ for influence flow from $X_1$ to $X_n$:

a. $X_1$ can influence $X_n$ if every two-edge trail $X_{i-1}\Rightarrow X_n\Leftarrow X_{n+1}$ along the trail allows the influence to flow. b. Definition: Let $\mathcal{G}$ be a BN structure and $X_1\Rightarrow \cdots \Rightarrow X_n$ a trail in $\mathcal{G}$. Let $Z$ be a subset of observed variables, the trail is active given $Z$ ($Z$ is the set of observations) if: i. Whenever we have a v-structure $X_{i-1}\to X_i\leftarrow X_{i+1}$ when $X_i$ itself or one of its descendants is in $Z$. ii. No other node along the trail is in $Z$. c. Examples: The trail $D\to G\leftarrow I\to S$ is active or not given $Z$? i. If $Z=\mathrm{\varnothing }$, the trail is not active because $G$ is not observed.
ii. If $Z=\{G\}$, the trail is active.
iii. If $Z=\{L\}$, the trail is active because $L$ is the descendant of $G$.
iv. If $Z=\{L,I\}$, it is not active because $I$ blocks the diverging trail $G\leftarrow I\to S$.

A simpler definition: Two nodes $X$ and $Y$ are d-separated by a set of $Z$ if all trails between $X$ and $Y$ are blocked by $Z$.

Intuition: If nodes $X$ and $Y$ are d-separated by a set of $Z$, then:

$$X\perp Y\mid Z$$

Definition: Let $X,Y,Z$ be three sets of nodes in a Bayesian network $G$, we say that $X$ and $Y$ are d-separated given $Z$ denoted as ${\text{d-sep}}_G(X;Y\mid Z)$ if there is no active trail between any node $X\in X$ and $Y\in Y$ given $Z$.

We use $\mathcal{I}(G)$ to denote the set of independencies that correspond to d-separation:

$$\mathcal{I}(G)=\{(X\perp Y\mid Z):{\text{d-sep}}_G(X;Y\mid Z)\}$$

it is called the set of global Markov independencies.

D-separation is a condition/algorithm for answering the queries, a criterion that helps to decide given a graph, whether one set of variable is independent of another set of variables, given a third set.