Bayesian Network Structure Learning Based On Heuristic Algorithms

Probabilistic graphical model combines probability theory and graph theory to deal with uncertain reasoning problems.Probabilistic graphical model is an abstraction of complex problems,which can be used for learning,modeling and reasoning according to observation data.As an important probabilistic graphical model,Bayesian networks are constructed according to Bayes theorem and conditional independence relationships of probability theory and use graph models to represent the structure abstractly.Bayesian networks are consisted of the structure and parameters.Bayesian network learning algorithms can be divided into structure learning and parameter learning.Structure learning is the basis of subsequent parameter learning and reasoning,which is particularly important in Bayesian networks.However,the computation complexity of structure learning increases exponentially with the number of nodes,which is NP-hard,and it is difficult to find an accurate solution to Bayesian network structure learning problem.There are three strategies constructing Bayesian networks with data learning: constraint-based approach,score-based approach,and hybrid approach.Both of the score-based approach and hybrid approach contain searching process.Due to the complexity of Bayesian network structure learning problem,searching for the optimal network structure in the solution space is NP-hard.One of the effective ways is to use heuristic algorithms to conduct searching process.Therefore,this paper studies Bayesian network structure learning problem from the perspective of heuristic algorithms,and experimental results show that heuristic algorithms can solve Bayesisan network structure learning problem effectively.The main content of this paper is arranged as follows:(1)In this paper,a Bayesian network structure learning algorithm based on Particle Swarm Optimization is proposed.As a representative swarm intelligence algorithm,Particle Swarm Optimization generates a population of particles to randomly search in the solution space.In the searching process,the proposed method combines Particle Swarm Optimization with mutation operator and crossover operator.The proposed method firstly uses PC algorithm to obtain structure priors of the directed acyclic graph,and uses structure priors to improve the initial solutions of Particle Swarm Optimization algorithm.The mutation operator and the crossover operator use the Uniform Mutation by Addition and Deletion(UMAD)model and the Uniform Crossover,respectively.Exprimental results show that the proposed method in this section can achieve better BIC scores with less iterations.(2)In this paper,a Bayesian network structure learning algorithm based on Biased Random-Key Genetic Algorithm(BRKGA)is proposed.Genetic Algorithm is a commonly used evolutionary algorithm.BRKGA is an improved genetic algorithm,which can achieve better searching results than the original Genetic Algorithm.Our proposed method firstly uses Non-combinatorial Optimization via Trace Exponential and Augmented lag Rangian for Structure learning(NOTEARS)algorithm as a decoder and decode random keys into initial solutions to Bayesian network structure learning problem.Then,our proposed method uses the crossover and the mutation operations of Genetic Algorithm to vary the current solution,and searches for more feasible solutions to obtain the optimal structure.Experimental results show that the proposed method in this section can obtain more accurate network structures than other classical methods.(3)In this paper,a Bayesian network structure learning method based on Bayesian Optimization is proposed.As a NP-hard problem,Bayesian network structure learning problem is difficult to solve by classical optimization methods.Bayesian Optimization is a heuristic algorithm and can effectively solve Bayesian network structure learning problem based on continuous fitting and sampling the current observation data.Our proposed method takes BDe score as the optimization object and continuously samples observation data from benchmark networks during the execution process.The proposed method firstly uses the Gaussian Process to fit sampled observation data,and uses acquisition function to search for the sampling points close to the optimal value,and adds them to the original observation data.This process is repeated until the current optimal network structure is obtained.Experimental results show that Bayesian Optimization can solve Bayesian network structure learning problem effectively.