Paper Info
Title
Comparative analysis of search and score metaheuristics for Bayesian network structure learning using node juxtaposition distributions
Abstract
Learning Bayesian networks from data is an NP-hard problem with important practical applications. Metaheuristic search on the space of node orderings combined with deterministic construction and scoring of a network is a well-established approach. The comparative performance of different search and score algorithms is highly problemdependent and so it is of interest to analyze, for benchmark problems with known structures, the relationship between problem features and algorithm performance. In this paper, we investigate four combinations of search (Genetic Algorithms or Ant Colony Optimization) with scoring (K2 or Chain). We relate node juxtaposition distributions over a number of runs to the known problem structure, the algorithm performance and the detailed algorithmic processes. We observe that, for different reasons, ACO and Chain both focus the search on a narrower range of orderings. This works well when the underlying structure is compatible but poorly otherwise. We conclude by suggesting future directions for research.
Year
DOI
Venue
2010
10.1007/978-3-642-15844-5_43
PPSN (1)
Keywords
Field
DocType
known structure,algorithm performance,known problem structure,metaheuristic search,score metaheuristics,comparative analysis,comparative performance,different reason,problem feature,bayesian network structure,different search,np-hard problem,benchmark problem,node juxtaposition distribution,ant colony optimization,bayesian network,genetic algorithm
Ant colony optimization algorithms,Mathematical optimization,Computer science,Structure learning,Bayesian network,Artificial intelligence,Machine learning,Genetic algorithm,Metaheuristic
Conference
Volume
ISSN
ISBN
6238
0302-9743
3-642-15843-9
Citations 
PageRank 
References 
2
0.40
11
Authors
3
Name
Order
Citations
PageRank
Yanghui Wu1282.36
John McCall223920.39
David W. Corne32161152.00