Fast Causal Structure Learning Using Markov Blanket Decomposition

Abstract

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 bothslower 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.