Memory-Efficient Dynamic Programming for Learning Optimal Bayesian Networks
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.
Cite
Text
Malone et al. "Memory-Efficient Dynamic Programming for Learning Optimal Bayesian Networks." AAAI Conference on Artificial Intelligence, 2011. doi:10.1609/AAAI.V25I1.8024Markdown
[Malone et al. "Memory-Efficient Dynamic Programming for Learning Optimal Bayesian Networks." AAAI Conference on Artificial Intelligence, 2011.](https://mlanthology.org/aaai/2011/malone2011aaai-memory/) doi:10.1609/AAAI.V25I1.8024BibTeX
@inproceedings{malone2011aaai-memory,
title = {{Memory-Efficient Dynamic Programming for Learning Optimal Bayesian Networks}},
author = {Malone, Brandon M. and Yuan, Changhe and Hansen, Eric A.},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2011},
pages = {1057-1062},
doi = {10.1609/AAAI.V25I1.8024},
url = {https://mlanthology.org/aaai/2011/malone2011aaai-memory/}
}