An Efficient Algorithm for Learning Bayesian Networks from Data

Abstract

We propose an algorithm for learning an optimal Bayesian network from data. Our method is addressed to biological applications, where usually datasets are small, and sets of random variables are large. Moreover, we assume that there is no need to examine the acyclicity of the graph. We provide polynomial bounds (with respect to the number of random variables) for time complexity of our algorithm for two generally used scoring criteria: Minimal Description Length and Bayesian-Dirichlet equivalence. Then we show how to adapt these criteria to work with continuous data and prove polynomial bounds for adapted scores. Finally, we briefly describe applications of proposed algorithm in computational biology.