Research On Models And Algorithms For Bayesian Network Structure Learning

Bayesian networks are becoming one of the most powerful tools of studying uncertain problems in recent years.In the theory of Bayesian networks,structure learning plays the key role in encoding uncertain expert knowledge,because it is actually the precondition of parameter learning or probabilistic reasoning.Hence,it is theoretically and practically meaningful to study the models and algorithms for learning Bayesian networks based on data.This paper mainly aims to make efforts on the following topics: analyzing the major reasons for causing swamping and masking in Markov boundary discovery of a single target variable,and finding the corresponding models and solutions;putting forward the notion of Markov boundary for multiple targets,and studying related theories and algorithms;presenting the dummy-variable-based method of solving multi-class problems;building a continuous particle swarm optimization algorithm for Bayesian network structure learning based on the idea of transforming problems to meet algorithms,and then improving it by integrating expert knowledge or empirical information selectively.Chapters 1 is the introduction of this paper.Chapter 2 introduces the two notions of swamping and masking into Bayesian network theory.Swamping and masking are two kinds of bad performance in structure learning.They are consequences of cascading errors caused by unreliable tests due to data insufficiency or consequences of algorithmic premature caused by the violation of preconditions for algorithms such as the faithfulness condition or the local composition assumption.According to this fact,we first analyze how to reduce unreliable tests and build a new algorithm,then discuss how to prevent algorithmic premature in the search process and improve the algorithm accordingly.The new algorithms as well as the post-processing technique can solve the problems of swamping and masking to some extent.Chapter 3 mainly considers the problem of Markov blanket and Markov boundary discovery for multiple targets.The notion of Markov blanket or Markov boundary for multiple targets can play an important role in computing posterior probabilities for multiple variables and in conducting censored data,and it is also an effective tool of dealing with synergy effects among variables.This chapter first shows the additivity property under the faithfulness condition or local intersection assumption,meaning that a Markov boundary of multiple targets can be constructed by simply taking the union of Markov boundaries of single targets and removing the targets themselves.The information flow metaphor is then used to intuitively explain reasonability of additivity.After that,this chapter analyzes why additivity is violated in general cases,and theoretically shows the idea of finding a Markov boundary for multiple targets based on the notion of Markov boundary supplementary.In addition,the notion of an information equivalent valve is defined to extend the information flow metaphor.Further,this chapter proposes two algorithms of Markov boundary discovery for multiple targets based on Markov boundary supplementary,and then remarks the algorithmic complexity,pointing out why the new algorithms are of lower complexity.Furthermore,a damped version for improving tests is discussed.Finally,this chapter uses some benchmarking networks to verify superiority of the new algorithms.Chapter 4 studies the problem of multi-class prediction on the basis of Markov boundary discovery for multiple targets.A good method for multi-class prediction is very meaningful to a lot of practical problems such as complex disease diagnosis,multi-target identification,and so on.This chapter first puts forward a dummy-variable-based method by combining Markov boundary discovery for multiple targets,and shows how this method works theoretically.To make further studies,some widely used machine learning algorithms including the support vector machine,random forest,naive Bayes,neural network,and classification tree are performed preliminarily.Two selected algorithms,support vector machine and random forest,are used to deeply analyze and discuss the HIVA data set which is very challenging because it contains many very unbalanced variables.The experimental results illustrate the significant superiority of the proposed dummy-variable-based method in handling the problems of high dimension and of high complexity.Chapter 5 focuses on global structure learning with respect to some particle swarm optimization algorithms.As well known,global structure learning is a difficult problem in Bayesian network theory because of its NP-hard nature.Fortunately,the introduction of some intelligent optimization algorithms in recent years opens a new way for global structure learning.This chapter first analyzes the principle of particle swarm optimization and its advantages and disadvantages,compares two ideas: “transforming algorithms to meet problems” and “transforming problems to meet algorithms”,and then uses the latter to build a continuous particle swarm optimization algorithm,which is then improved by integrating expert knowledge or empirical information selectively.The optimal flying behaviours of the new algorithms are also discussed detailedly.Finally,this chapter makes a simulation study based on two benchmarking networks.Feasibility of the new idea and superiority of the new algorithms are exemplified.Chapter 6 summarizes the paper and analyzes the future research.