d-Separation through examples

Given a Bayesian network, d-Separation presents a way to check if a set of variables, $P$ , is conditionally independent of another set of variables, $Q$ , given an observed set of variables $E$ . The observed set is also called the evidence. In this article, the conditional independence of two single nodes $p$ and $q$ given $E$ is explored. This can be extended to sets. Two sets are conditionally independent if each element of the first set is conditionally independent of every element in the second set.

Reachability

Dependence is associated when there exists an active path connecting the two nodes. If there is no active path between the two nodes, they are said to be separated. Whether a path is active depends on the direction of the edges between the nodes and which nodes are part of the evidence $E$ . Hence, the term d-Separation.

Two nodes $p$ and $q$ are conditionally independent given evidence $E$ , if $p$ and $q$ are d-separated by $E$ . This holds true when all undirected paths between $p$ and $q$ are inactive. The direction of the arrows in the path can fall into one of $3$ cases.

Causal Chain

$\begin{equation*} p \rightarrow e \rightarrow q \end{equation*}$

If $e$ is observed, the triple $p - e - q$ is considered inactive. If $e$ is unobserved, the triple $p - e - q$ is considered active.

Common Cause

$\begin{equation*} p \leftarrow e \rightarrow q \end{equation*}$

If $e$ is observed, the triple $p - e - q$ is considered inactive. If $e$ is unobserved, the triple $p - e - q$ is considered active.

Common Effect

$\begin{equation*} p \rightarrow e \leftarrow q \end{equation*}$

If $e$ or any descendant of $e$ is observed, the triple $p - e - q$ is considered active. Otherwise, the triple $p - e - q$ is considered inactive.

d-Separation

Given query: is $p$ conditionally independent of $q$ , given evidence set $E = \{e_1, e_2, \cdots e_n\}$ .
Mark all the nodes in the evidence set.
For all undirected non-looping paths between and
1. Check whether the path is active. A path is active if each triple along the path is active.
2. If a path is active, it is not guaranteed that $p$ is conditionally independent of $q$ given $E$ .
All paths between $p$ and $q$ have been found inactive. It is guaranteed that $p$ is conditionally independent of $q$ given $E$ .

Example Network

Consider the following Bayesian Network

Rendered by QuickLaTeX.com

Is $A$ conditionally independent of $D$ given $\{C\}$ ?

Rendered by QuickLaTeX.com

One path connecting $A$ and $D$ is active. Thus, it is not guaranteed that $A$ is conditionally independent of $D$ given $\{C\}$ .

Is $A$ conditionally independent of $D$ given $\{B, C\}$ ?

Rendered by QuickLaTeX.com

All paths connecting $A$ and $D$ are inactive. Thus, it is guaranteed that $A$ is conditionally independent of $D$ given $\{B, C\}$ .

Is $A$ conditionally independent of $G$ given $\{C, E\}$ ?

Rendered by QuickLaTeX.com

One path connecting $A$ and $G$ is active. Thus, it is not guaranteed that $A$ is conditionally independent of $G$ given $\{C, E\}$ .

Triple	Evidence	Status
	$e$ is Observed	Inactive
	$e$ is Unobserved	Active

Triple	Evidence	Status
	$e$ is Observed	Inactive
	$e$ is Unobserved	Active

Triple	Evidence	Status
	$e$ is Observed	Active
	$f$ , a descendant of $e$ , is Observed	Active
	$e$ is Unobserved and all descendants of $e$ are Unobserved	Inactive

Path	Triple	Type	Observation	Triple Status	Path Status
$A - C - B - D$
	$A \rightarrow C \leftarrow B$	Common Effect	$C$ is observed	Active
	$C \leftarrow B \rightarrow D$	Common Cause	$B$ is unobserved	Active
					Active

Path	Triple	Type	Observation	Triple Status	Path Status
$A - C - B - D$
	$A \rightarrow C \leftarrow B$	Common Effect	$C$ is observed	Active
	$C \leftarrow B \rightarrow D$	Common Cause	$B$ is observed	Inactive
					Inactive

The Beard Sage

d-Separation through examples

Reachability

Causal Chain

Common Cause

Common Effect

d-Separation

Example Network

Is $A$ conditionally independent of $D$ given $\{C\}$ ?

Is $A$ conditionally independent of $D$ given $\{B, C\}$ ?

Is $A$ conditionally independent of $G$ given $\{C, E\}$ ?

Leave a Reply Cancel reply

Reachability

Causal Chain

Common Cause

Common Effect

d-Separation

Example Network

Is conditionally independent of given ?

Is conditionally independent of given ?

Is conditionally independent of given ?

Leave a Reply Cancel reply

Is $A$ conditionally independent of $D$ given $\{C\}$ ?

Is $A$ conditionally independent of $D$ given $\{B, C\}$ ?

Is $A$ conditionally independent of $G$ given $\{C, E\}$ ?