A comparison of novel and state-of-the-art polynomial Bayesian network learning algorithms

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

Research output: Contribution to conferencePaper

20 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages739-745
Number of pages7
StatePublished - Dec 1 2005
Externally publishedYes
Event20th National Conference on Artificial Intelligence and the 17th Innovative Applications of Artificial Intelligence Conference, AAAI-05/IAAI-05 - Pittsburgh, PA, United States
Duration: Jul 9 2005Jul 13 2005

Other

Other20th National Conference on Artificial Intelligence and the 17th Innovative Applications of Artificial Intelligence Conference, AAAI-05/IAAI-05
CountryUnited States
CityPittsburgh, PA
Period7/9/057/13/05

Fingerprint Dive into the research topics of 'A comparison of novel and state-of-the-art polynomial Bayesian network learning algorithms'. Together they form a unique fingerprint.

Cite this