Efficient score-based Markov Blanket discovery

Abstract

In a Bayesian Network (BN), the Markov Blanket (MB) of a target node consists of its parents, children, and spouses, and the target node is independent of all other nodes given its MB. Finding the MB has many applications, including feature selection and BN structure learning. We propose two new Markov Blanket discovery algorithms, score-based Simultaneous Markov Blanket discovery (S2TMB) and its more efficient variant, S2TMB+, to improve the efficiency of existing score-based MB learning algorithms. The proposed methods remove the necessity of enforcing the commonly used symmetry constraint by exploiting the coexistence property between spouses and descendants of the target node. S2TMB and S2TMB+ achieve comparable accuracy and better efficiency than state-of-the-art score-based methods. S2TMB and S2TMB+ are proven sound and complete under one conjecture. Empirical results on standard MB discovery datasets demonstrate the superior performances of S2TMB and S2TMB+.