Bayesian Network Structure Learning Approach Based on Searching Local Structure of Strongly Connected Components

Abstract

Learning the structure of Bayesian networks is a challenging problem because it is a NP-Hard problem. As an excellent search & score based method, the K2 algorithm strongly depends on the input of global order of all nodes to ensure the result is a directed acyclic graph. And the K2 algorithm searches parents for each node from the nodes before it in the global order. Incorrect node order is likely to result in a wrong structure. In this paper, we propose a new method to avoid the global order by Local structure Searching for Strongly Connected Components with hill climbing method Twice. Firstly, we search the best parent nodes for each node from all the remaining nodes except itself, and form a global directed graph by concatenating the arcs between nodes and their parents. Then, the directed acyclic structure of all the strongly connected components are determined by hill climbing algorithm twice continuously. Finally, we adopt local search method further to get the final result by taking the previous result as a start point. The proposed algorithm is evaluated on several standard benchmark networks with sampled data. Experimental results show that our algorithm outperforms the four compared algorithms in terms of structural Hamming distance, Bayesian information criterion score and their average ranking.

Keywords

• Bayesian network
• structure learning
• hill climbing search
• strongly connected component