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.