A Comparison of Novel and State-of-the-Art Polynomial Bayesian Network Learning Algorithms

Laura E. Brown, Ioannis Tsamardinos, Constantin F. Aliferis

Learning the most probable a posteriori Bayesian network from data has been shown to be an NP-Hard problem and typical state-of-the-art algorithms are exponential in the worst case. However, an important open problem in the field is to identify the least restrictive set of assumptions and corresponding algorithms under which learning the optimal network becomes polynomial. In this paper, we present a technique for learning the skeleton of a Bayesian network, called Polynomial Max-Min Skeleton (PMMS), and compare it with Three Phase Dependency Analysis, another state-of-the-art polynomial algorithm. This analysis considers both the theoretical and empirical differences between the two algorithms, and demonstrates PMMS’s advantages in both respects. When extended with a greedy hill-climbing Bayesian-scoring search to orient the edges, the novel algorithm proved more time efficient, scalable, and accurate in quality of reconstruction than most state-of-the-art Bayesian network learning algorithms. The results show promise of the existence of polynomial algorithms that are provably correct under minimal distributional assumptions.

Content Area: 12. Machine Learning

Subjects: 12. Machine Learning and Discovery

Submitted: May 10, 2005

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.