Comparative analysis of search and score metaheuristics for Bayesian network structure learning using node juxtaposition distributions

Yanghui Wu, John McCall, David Corne

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 problem-dependent 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. © 2010 Springer-Verlag.

Original languageEnglish
Title of host publicationParallel Problem Solving from Nature, PPSN XI - 11th International Conference, Proceedings
Pages424-433
Number of pages10
Volume6238 LNCS
EditionPART 1
DOIs
Publication statusPublished - 2010
Event11th International Conference on Parallel Problem Solving from Nature - Krakow, Poland
Duration: 11 Sep 201015 Sep 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume6238 LNCS
ISSN (Print)0302-9743

Conference

Conference11th International Conference on Parallel Problem Solving from Nature
Abbreviated titlePPSN 2010
CountryPoland
CityKrakow
Period11/09/1015/09/10

Keywords

  • Ant Colony Optimization
  • Bayesian Network Structure Learning
  • Chain Model
  • Genetic Algorithm
  • K2
  • Node Ordering

Fingerprint Dive into the research topics of 'Comparative analysis of search and score metaheuristics for Bayesian network structure learning using node juxtaposition distributions'. Together they form a unique fingerprint.

  • Cite this

    Wu, Y., McCall, J., & Corne, D. (2010). Comparative analysis of search and score metaheuristics for Bayesian network structure learning using node juxtaposition distributions. In Parallel Problem Solving from Nature, PPSN XI - 11th International Conference, Proceedings (PART 1 ed., Vol. 6238 LNCS, pp. 424-433). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6238 LNCS, No. PART 1). https://doi.org/10.1007/978-3-642-15844-5_43