Simplifying D-Separation and M-Separation in Bayesian Networks
Abstract
Many di erent platforms, techniques, and concepts can be employed while modeling
and reasoning with Bayesian networks (BNs). A problem domain is modeled initially
as a directed acyclic graph (DAG), denoted B, and the strengths of relationships
are quanti ed by conditional probability tables (CPTs). Testing whether two sets X
and Z of variables are conditionally independent given another set Y of variables
is fundamental to BN modeling and inference. There are two well-known methods,
called d-separation and m-separation, for this task.
The founder of BNs suggested d-separation as a method for testing independen-
cies. The crux of the linear implementation of d-separation is to determine all nodes
reachable from X via active paths. We propose inaugural separation (i-separation)
as a new method for testing independencies in BNs. i-Separation has several theo-
retical and practical advantages. There are at least ve ways in which i-separation
is simpler than d-separation, of which the most important is that \blocking" works
in an intuitive fashion. An empirical evaluation shows that i-separation tends to be
faster than d-separation in large BNs.
In practice, d-separation is often utilized, since it has linear-time complexity. How-
ever, many have had di culties in understanding d-separation in BNs. m-Separation
is an equivalent method that is easier to understand by transforming the problem
from directed separation in BNs into classical separation in undirected graphs. Two
main steps of this transformation are pruning the BN and adding undirected edges. We propose u-separation as an even simpler method for testing independencies in
a BN. Our approach also converts the problem into classical separation in an undi-
rected graph. However, our method is based upon the novel concepts of inaugural
variables and rationalization. u-Separation can prune fewer edges from the BN and
add fewer undirected edges. Thereby, the primary advantage of u-separation over m-
separation is that m-separation can prune unnecessarily and add super
uous edges.
Hence, u-separation is a simpler method in this respect.