Premium
On a simple method for testing independencies in Bayesian networks
Author(s) -
Butz Cory J.,
dos Santos André E.,
Oliveira Jhonatan S.,
Gonzales Christophe
Publication year - 2018
Publication title -
computational intelligence
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.353
H-Index - 52
eISSN - 1467-8640
pISSN - 0824-7935
DOI - 10.1111/coin.12130
Subject(s) - separation (statistics) , undirected graph , bayesian network , directed acyclic graph , simple (philosophy) , computer science , pruning , source separation , bayesian probability , mathematics , graph , artificial intelligence , algorithm , theoretical computer science , machine learning , philosophy , epistemology , agronomy , biology
Abstract Testing independencies is a fundamental task in reasoning with Bayesian networks (BNs). In practice, d‐separation is often used for this task, since it has linear‐time complexity. However, many have had difficulties understanding d‐separation in BNs. An equivalent method that is easier to understand, called m‐separation , transforms 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. In this paper, 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 undirected graph. However, our method is based upon the novel concepts of inaugural variables and rationalization. Thereby, the primary advantage of u‐separation over m‐separation is that m‐separation can prune unnecessarily and add superfluous edges. Our experiment results show that u‐separation performs 73% fewer modifications on average than m‐separation.