An Efficient Algorithm for Learning Bayesian Networks from Data

Issue title: From Mathematical Beauty to the Truth of Nature: to Jerzy Tiuryn on his 60th Birthday

Article type: Research Article

Authors: Dojer, Norbert

Affiliations: Institute of Informatics, Warsaw University, Banacha 2, 02-097 Warszawa, Poland. dojer@mimuw.edu.pl

Note: [] Address for correspondence: Institute of Informatics, Warsaw University, Banacha 2, 02-097 Warszawa, Poland

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.

DOI: 10.3233/FI-2010-318

Journal: Fundamenta Informaticae, vol. 103, no. 1-4, pp. 53-67, 2010