Memoryefficient dynamic programming for learning optimal Bayesian networks

We describe a memory-efficient implementation of a dynamic programming algorithm for learning the op-timal structure of a Bayesian network from training data. The algorithm leverages the layered structure of the dynamic programming graphs representing the re-cursive 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 coeffi-cient. Experimental results show that the approach runs up to an order of magnitude faster and scales to datasets with more variables than previous approaches