Dynamic ordering-based search algorithm for Markov blanket discovery

Markov blanket discovery plays an important role in both Bayesian network induction and feature selection for classification tasks. In this paper, we propose the Dynamic Ordering-based Search algorithm (DOS) for learning a Markov blanket of a domain variable from statistical conditional independence tests on data. The new algorithm orders conditional independence tests and updates the ordering immediately after a test is completed. Meanwhile, the algorithm exploits the known independence to avoid unnecessary tests by reducing the set of candidate variables. This results in both efficiency and reliability advantages over the existing algorithms. We theoretically analyze the algorithm on its correctness and empirically compare it with the state-of-the-art algorithm. Experiments show that the new algorithm achieves computational savings of around 40% on multiple benchmarks while securing similar or even better accuracy.