Problem dependent metaheuristic performance in Bayesian network structure learning.

Wu, Yanghui

Abstract

Bayesian network (BN) structure learning from data has been an active research area in the machine learning field in recent decades. Much of the research has considered BN structure learning as an optimization problem. However, the finding of optimal BN from data is NP-hard. This fact has driven the use of heuristic algorithms for solving this kind of problem. Amajor recent focus in BN structure learning is on search and score algorithms. In these algorithms, a scoring function is introduced and a heuristic search algorithm is used to evaluate each network with respect to the training data. The optimal network is produced according to the best score evaluated. This thesis investigates a range of search and score algorithms to understand the relationship between technique performance and structure features of the problems. The main contributions of this thesis include (a) Two novel Ant Colony Optimization based search and score algorithms for BN structure learning; (b) Node juxtaposition distribution for studying the relationship between the best node ordering and the optimal BN structure; (c) Fitness landscape analysis for investigating the di erent performances of both chain score function and the CH score function; (d) A classifier method is constructed by utilizing receiver operating characteristic curve with the results on fitness landscape analysis; and finally (e) a selective o -line hyperheuristic algorithm is built for unseen BN structure learning with search and score algorithms. In this thesis, we also construct a new algorithm for producing BN benchmark structures and apply our novel approaches to a range of benchmark problems and real world problem.

Citation

WU, Y. 2012. Problem dependent metaheuristic performance in Bayesian network structure learning. Robert Gordon University, PhD thesis.

• Thesis Type: Thesis
• Deposit Date: Dec 21, 2012
• Publicly Available Date: Dec 21, 2012
• Keywords: Bayesian network; Search and score algorithm; Ant colony; Optimisation node; Juxtaposition; Distribution; Fitness; Landscape analysis; Offline hyperheuristic receiver; Operating characteristic
• Public URL: http://hdl.handle.net/10059/790
• Contract Date: Dec 21, 2012
• Award Date: Sep 30, 2012