d separation

d-separation is a term from graph theory and describes a property of node sets in directed graphs . The d is the abbreviation for directed, which means directed. Similarly, you can also define the u-separation , i.e. the separation in undirected graphs.

definition

Let and be two nonempty disjoint sets of nodes of a graph and an arbitrary set of nodes. Then d-separated from given if for every undirected path from to it holds that it is blocked by . A path is called blocked by if: ${\ displaystyle X}$ ${\ displaystyle Y}$ ${\ displaystyle Z}$ ${\ displaystyle X}$ ${\ displaystyle Y}$ ${\ displaystyle Z}$ ${\ displaystyle X}$ ${\ displaystyle Y}$ ${\ displaystyle Z}$ ${\ displaystyle Z}$

there is one that lies on the path through an incoming as well as an outgoing edge or ${\ displaystyle z \ in Z}$
there is one that lies on the path through two outgoing edges or ${\ displaystyle z \ in Z}$
there is one that lies on the path through two incoming edges and of which no successor is contained in. ${\ displaystyle z \ notin Z}$ ${\ displaystyle Z}$

algorithm

An efficient method to find all d-separated nodes is the Bayes Ball algorithm .

Applications

Bayesian networks are models for the joint distribution of a set of random variables . They represent dependencies through directed edges in a graph, whereby the nodes correspond to the random variables. One can show that in Bayesian networks the independence of random variables is related to the d-separation of the nodes.

References

^ Dan Geiger, Thomas Verma, Judea Pearl : Identifying independence in Bayesian Networks . In: Networks . 20, 1990, pp. 507-534. Retrieved October 6, 2011.

[1] Dan Geiger, Thomas Verma, Judea Pearl : Identifying independence in Bayesian Networks . In: Networks . 20, 1990, pp. 507-534. Retrieved October 6, 2011.