Recursion-based Algorithms For Structure Learning Of Bayesian Networks

Bayesian network(BN) is a general graphical model, having the advantages in encoding and reasoning uncertainty knowledge. Meanwhile, it has been successfully applied to a wide range of tasks, such as artificial intelligence, bioinformatics, economic analysis, machine learning and forecast. However, it is difficult to construct a Bayesian network only depending on the domain experts. Therefore, structure learning and inference in Bayesian network from data have become key points. After analyzing relevant theories of Bayesian network, this paper focuses on the structure learning, and proposes a new algorithm. The main works can be summarized as follows:Firstly, after discussing the existing algorithms for the structure learning of BN, the main steps of the RAI and CS algorithm are described and analyzed in detail. At the same time, the advantages and disadvantages of the two algorithms are summarized.Secondly, based on RAI and CS, we propose a new combined recursive algorithm(CRA) to learn structure of Bayesian network. It mainly calls two recursive functions to learn. The first is the RAI function which is used to learn the structure of the ancestor substructures after decomposing. The second is the RTL function which is used to learn the structure between the ancestor substructures and the descendant substructures, and the structure of the descendant substructures itself. Consequently, we can get the best structure. And at the same time, we propose an algorithm for solving the inconsistent structure with RAI.Finally, theoretical results demonstrate the correctness of the CRA. Simulations on the ALARM network prove that our algorithm has advantages over the existing algorithms in terms of the complexity and structure correctness. Not only has it declined the number of CI tests, but also decreased the number of high order of CI tests. Meanwhile, the resulting structure of Bayesian network has small errors on edges.