Memory-Efficient Dynamic Programming for Learning Optimal Bayesian Networks

Authors

  • Brandon Malone Mississippi State University
  • Changhe Yuan Mississippi State University
  • Eric Hansen Mississippi State University

Abstract

We describe a memory-efficient implementation of a dynamic programming algorithm for learning the optimal structure of a Bayesian network from training data. The algorithm leverages the layered structure of the dynamic programming graphs representing the recursive decomposition of the problem to reduce the memory requirements of the algorithm from O(n2n) to O(C(n, n/2)), where C(n, n/2) is the binomial coefficient. Experimental results show that the approach runs up to an order of magnitude faster and scales to datasets with more variables than previous approaches.

Downloads

Published

2011-08-04

How to Cite

Malone, B., Yuan, C., & Hansen, E. (2011). Memory-Efficient Dynamic Programming for Learning Optimal Bayesian Networks. Proceedings of the AAAI Conference on Artificial Intelligence, 25(1), 1057-1062. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/8024