Research On Structure Learning Algorithms For Multi-Node Complex Bayesian Networks

Bayesian network(BN)is the typical representative of probabilistic graphical models,which has clear and transparent expression to represent the causal relations among variables.It supports data-driven methods to construct models and uses conditional probability to describe the degree of dependence between variables.Hence BN provides an important theoretical model frame in probability space for machine learning.When using BN theory to solve practical problems,the primary task is to establish a graphical model that expresses the intrinsic relationship between variables for the research object.However,during the process of BN construction,the scale of the search space containing all possible BN structures grows exponentially with the increasing number of variables,especially when building a large-scale BN structure,the task of detecting the relations among nodes has high time and space complexity.To solve this problem,the dissertation takes advantage of model decomposition to subdivide the large-scale structure learning task into a series of subtasks of small and medium-scale network optimization.At the beginning,small and medium-scale BN structure learning algorithms are proposed to improve the learning accuracy and efficiency for the local neighborhood structures.Then,the above methods are applied to the subgraph learning after splitting a large-scale BN.Finally,the entire directed acyclic graph can be constructed by combining these subgraphs.The main research work of this dissertation is presented as follows:(1)BN structure adaptive learning algorithm based on dual-scale constraint model is proposed,which solves the problem of losing potential optimal solution in the process of topology optimization due to unreasonable structural constraints.The algorithm combines the maximum mutual information and conditional independence(CI)tests to establish a large-scale constraint model for the initialization of the search space.Besides,a small-scale constraint model applied in the iterative process of genetic algorithm is established.It adopts the scoring function and structural complexity evaluation model to achieve small dynamic adjustment of the search space.The simulation results show that when learning small and medium-scale BN structures(less than 50 nodes),the proposed algorithm increases the accuracy by 17.2%~72.3%,compared with other swarm intelligence algorithms.(2)A hybrid learning algorithm based on improved evolutionary method is proposed,which solves the problem of the disruption of the excellent substructures due to random search and the difficulty of identifying the structures in the same Markov equivalence class.Considering the local features of the network,in order to pass on the excellent substructures to the offspring,the algorithm uses the decomposability of the scoring function to establish a model which can save the scores for every individual,so that the convergence speed of the structure learning algorithm can be improved.In addition,the statistical model of the structures in the same equivalence class is built to timely feedback the diversity of the current candidate structures.On this basis,the algorithm can perform different operations to correct the diversity of the population.The simulation results show that the learning accuracy of the proposed algorithm is averagely improved by 25.5%,compared with Max-Min Hill-Climbing(MMHC)algorithm which has remarkable performance when learning BN structures containing less than 50 variables.Besides,compared against other swarm intelligence methods,the proposed algorithm averagely increases the convergence speed by about 4 times.(3)An undirected independence graph construction algorithm based on a three-stage approach for Markov blanket fast discovery is proposed,which solves the problem of high time cost of building an undirected independence graph for large-scale BN due to the low-efficiency CI tests.By introducing a constraint threshold and the maximal information coefficient to establish the Markov blanket filtering model,the algorithm removes the edges with weak connections,thus limiting the candidate Markov blanket search space.Moreover,the algorithm utilizes the local topology information to preferentially perform effective CI tests,reducing the number of the invocations and high orders of CI tests.The simulation results show that when the number of nodes exceeds 50,compared with other Markov blanket discovery methods,the proposed algorithm can averagely cut down the number of CI tests by 6 times,and the sum of the orders of CI tests can be averagely reduced by 7 times.(4)A recursive learning algorithm based on graph partitioning for large-scale BN structures is proposed,which solves the problem of the effective decomposition of an undirected independence graph without prior knowledge.The algorithm evaluates the importance degree of each node during the information propagation process according to the local topology information of the network,so that an undirected independence graph decomposition model is designed.Besides,the termination criterion is developed by using the features of subgraphs.The simulation results show that compared against MMHC algorithm,when the BN consists of more than 100 nodes,the accuracy of the proposed algorithm is averagely increased by 26.7% and the running time is reduced by 24% on average.In addition,compare with other classic learning methods,the proposed algorithm can maintain a balance between the accuracy and the efficiency for BN structure estimation.