Research On Structures Learning Of Several Probabilistic Graphical Models

Probabilistic graphical models(PGM)which combine graph theory and probability theory are widely used for modelling and reasoning knowledge with uncertainty.Bayesian network(BN)is one of the most basic subclass of the probabilistic graphical models.It has solid theoretical foundations and is used in a wide variety of applications.Chain graph(CG)is a general subclass of probabilistic graphical models,which contains Bayesian network,only a small portion of the independence models represented by chain graphs can be represented by Bayesian networks.Since the representation and reasoning of problems are based on the topological structure of the network,learning the structure from the data becomes an important issue in the study of the probabilistic graphical model.Therefore,in this thesis,we establish the score-based and constraint-based algorithms to solve the structures learning problems of Bayesian network and chain graph respectively.The main contents are as follows:Firstly,for Bayesian network structure learning problem,we use the novel discrete particle swarm optimization algorithm to learn Bayesian network structures.The algorithm is implemented by designing a new search strategy to maximize the score of each candidate structure.Based on the characteristic of Bayesian network,the velocity and position updating rules are designed with new strategies without changing the optimization mechanism of the classical particle swarm optimization.Meanwhile,the neighbor searching operator is used to improve the performance of the proposed algorithm.The experimental results on benchmark networks illustrate the feasibility and effectiveness of the proposed algorithm.The comparative experiments indicate that the proposed algorithm is superior in network score and running time.Secondly,for further study of the score-based approach for Bayesian networks structure learning,the meta-heuristic algorithm water cycle algorithm is used to solve Bayesian network structure learning problem,and a novel binary encoding water cycle algorithm is proposed.In this method,the sea,rivers and streams correspond to the candidate structures,the logic operators are used to calculate the positions of the individuals.Meanwhile,to balance the exploitation and exploration abilities of the algorithm,the individuals update their positions not only according to the best and better solutions but also based on other individuals in current population.In addition,the evaporation process is designed with the mutation strategy.The convergence analysis of the proposed algorithm is also provided.Experiments on benchmark networks demonstrate that the proposed algorithm is capable of identifying the optimal or near-optimal structures.In comparison to the use of other algorithms,the proposed algorithm performs well in terms of the accuracy and convergence speed.The proposed binary encoding algorithm provides a new heuristic algorithm for Bayesian network structure learning problem,and it also extends the application of water cycle algorithm in discrete optimization.Finally,for chain graph structure learning problem,a constraint-based algorithm is proposed.The algorithm uses the local neighborhood information of nodes to transform the structure learning of chain graph into the problem of recovering adjacent nodes set of each node in network,which effectively reduces the number of the conditional independent tests and avoids the high-order conditional independent test.To control the false discovery rate(FDR)of edges when learning a chain graph,the FDR controlling procedure embedded into the proposed algorithm,collectively considers the hypothesis related to the existence of multiple edges.After recovering the skeleton,the algorithm for complexes recovery is presented.Experimental results on random chain graphs demonstrate that the algorithm with the FDR controlling procedure can control the false discovery rate of the skeleton under a user-specified level,and the proposed algorithm also provides an alternative method for chain graph structure learning.