Predicting the Hardness of Learning Bayesian Networks


  • Brandon Malone University of Helsinki
  • Kustaa Kangas University of Helsinki
  • Matti Jarvisalo University of Helsinki
  • Mikko Koivisto University of Helsinki
  • Petri Myllymaki University of Helsinki



There are various algorithms for finding a Bayesian networkstructure (BNS) that is optimal with respect to a given scoring function. No single algorithm dominates the others in speed, and, given a problem instance, it is a priori unclear which algorithm will perform best and how fast it will solve the problem. Estimating the runtimes directly is extremely difficult as they are complicated functions of the instance. The main contribution of this paper is characterization of the empirical hardness of an instance for a given algorithm based on a novel collection of non-trivial, yet efficiently computable features. Our empirical results, based on the largest evaluation of state-of-the-art BNS learning algorithms to date, demonstrate that we can predict the runtimes to a reasonable degree of accuracy, and effectively select algorithms that perform well on a particular instance. Moreover, we also show how the results can be utilized in building a portfolio algorithm that combines several individual algorithms in an almost optimal manner.




How to Cite

Malone, B., Kangas, K., Jarvisalo, M., Koivisto, M., & Myllymaki, P. (2014). Predicting the Hardness of Learning Bayesian Networks. Proceedings of the AAAI Conference on Artificial Intelligence, 28(1).



AAAI Technical Track: Reasoning under Uncertainty