D-separation

Bayesian networks encode the dependencies and independencies between variables. Under the causal Markov assumption, each variable in a Bayesian network is independent of its ancestors given the values of its parents. With the causal Markov assumption, we can check some conditional independence in Bayesian networks. For the general conditional independence in a Bayesian network, Pearl [79] proposed a concept – d-separation for the purpose. D-separation is a graphical property of Bayesian networks and has the following implication: If two sets of nodes X and Y are d-separated in Bayesian networks by a third set Z (excluding X and Y), the corresponding variable sets X and Y are independent given the variables in Z. The definition of d-separation is as follows: two sets of nodes X and Y are d-separated in Bayesian networks by a third set Z (excluding X and Y) if and only if every path between X and Y is “blocked”, where the term “blocked” means that there is an intermediate variable V (distinct from X and Y) such that:

- The connection through V is “tail-to-tail” or “tail-to-head” and V is instantiated

- Or, the connection through V is “head-to-head” and neither V nor any of V’s descendants have received evidence.

The graph patterns of “tail-to-tail”, “tail-to-head” and “head-to-head” are shown in Figure 3.

Figure 3 Patterns for paths through a node

The minimal set of nodes which d-separates node A from all other nodes is A's Markov blanket (MB). The Markov blanket MB(A) of node A in a Bayesian network is the set of nodes composed of A's parents, its children, and its children's parents.