Research On Learning Algorithms Of Probabilistic Graphical Models

Probabilistic graph model,which combines probability theory with graph theory,describes multivariate statistical relations in a compact form,and is widely used in uncertain knowledge representation and reasoning.In the era of big data,how to speed up the learning of network model and make it possible to learn complex network model from massive data in a short time is of great significance to make full use of the value of data.There are two kinds of probabilistic graph models: Bayesian network and Markov network.This paper mainly focuses on Bayesian network learning.Bayesian network learning is divided into structural learning and parameter learning,and structural learning is the focus of research.Bayesian network structure learning is NP-hard,so heuristic algorithms amd random methods are often used to reduce the complexity of networks learning.In this paper,an algorithm based on MCMC method for sampling the order space is proposed to learn Bayesian network structure.Compared with the graph space,order space is much smaller.Furthermore,a new order scoring function is introduced in this paper,which reduces the complexity of the traditional scoring function and improves the speed of the order scoring.A new mapping algorithm between integers and combinations is used to replace the traditional hash algorithm to calculate the storage location of local scores,and to speed up the search process of local scores.In addition,Bayesian estimation method is used to learn the model parameters of the network.Then,the improved learning algorithm is designed in parallel to accelerate Bayesian network learning using GPU on CUDA platform.GPU threads can be used to calculate the local scores in the pre-processing stage and search the best local score of each node in a given order the MCMC iterative learning stage.These two stages are also the core of the whole algorithm,so the learning time of Bayesian network can be significantly reduced.In addition,the new reduction algorithm is applied to obtain the optimal set of parent nodes corresponding to the nodes,which reduces the requirement of memory capacity.Finally,four Bayesian networks of different scales are used to test the performance of mMCL algorithm and PmMCL algorithm based on CUDA GPU,and compared with the classical MCL structure learning algorithm.The experimental results show that mMCL algorithm improves the learning speed of Bayesian network to a certain extent on the premise of ensuring the accuracy of model learning,and thePcMCL algorithm based on GPU significantly speeds up the learning efficiency of Bayesian network.