Fast Causal Structure Learning Using Markov Blanket Decomposition
AnhTuanBui · Open Access System for Information Sharing (Pohang University of Science and Technology) · 2012
Causal structure learning algorithms construct Bayesian networks from observational data. Constraint-based algorithms use conditional independence tests to detect relationship among variables. Using non-interventional data, existing constraint-based algorithms may return I-equivalent partially directed acyclic graphs. In worst case, these algorithms may suffer from exponentially complexity. Some recent algorithms utilize Markov blanket approach to deal with this problem. However, these algorithms do not fully exploit graphical properties of Bayesian networks and they require many redundant tests that cause both slower speed and lower accuracy. This thesis introduces some ideas to exploit such properties to enhance causal structure learning performance. Numerical experiments on five benchmarking networks show that the proposed algorithm outperforms recently developed algorithms. Furthermore, theoretical study is also discussed to support the correctness of the proposed method.