Abstract: Bayesian network is an effective tool for uncertainty knowledge representation and reasoning.Learning and discovering its structure is the basis of reasoning via this tool.Existing Bayesian network structure learning algorithms often encounter the dilemma of balancing effectiveness and efficiency in real-world applications such as intelligent education.On the one hand,score-and-search methods can find out the high-quality solutions,but they suffer from the high algorithmic complexity.On the other hand,hybrid methods are highly efficient but the quality of the found solutions is not satisfactory.To address the above dilemma,this paper proposes an evolutionary order search based hybrid Bayesian network structure learning method called EvOS.First,the proposed EvOS constructs an undirected graph skeleton through a constraint algorithm,and then applies an evolutionary algorithm to search for the optimal node order,and finally uses the found node order to guide the greedy search so as to obtain the Bayesian network structure.This paper conducts the empirical study to verify the effectiveness and efficiency of the proposed EvOS in the commonly-used benchmark datasets as well as the real-world task of educational knowledge structure discovery.Experimental results show that,compared with the score-and-search methods,EvOS is able to achieve up to 100 times speedup while maintaining the similar accuracy,and its effectiveness is significantly better than that of the hybrid methods.

Key words: Bayesian network, Structure learning, Order search, Evolutionary optimization, Knowledge structure discovery