Implementation and Evaluation of a Parallel Algorithm for Structure Learning in Bayesian Networks

This thesis is about learning the globally optimal Bayesian network structure from fully observed dataset, by using score-based method. This structure learning problem is NP- hard, and has attracted the attention of many researchers. We first introduce the necessary background of the problem, then review various score-based methods and algorithms proposed in solving the problem. Parallelization has come under the spotlight during recent years, as it can utilize shared memory and computing power of multi-core supercomputers or computer clusters. We implemented a parallel algorithm Para-OS, which is based on dynamic programming. Experiments were performed in order to evaluate the algorithm. We also propose an improved version of Para-OS, which separates the scoring phase totally from the learning phase, performs score pruning by using Sparse Parent Graph, in addition largely reduces the communication between processors. Empirical results shows the new version saves memory comparing to Para-OS, and provides good runtime with multi-treading