Towards Scalable and Data E-cient Learning of Markov Boundaries

We propose algorithms for learning Markov boundaries from data without having to learn a Bayesian network flrst. We study their correctness, scalability and data e‐ciency. The last two properties are important because we aim to apply the algorithms to identify the minimal set of features that is needed for probabilistic classiflcation in databases with thousands of features but few instances, e.g. gene expression databases. We evaluate the algorithms on synthetic and real databases, including one with 139351 features.