Research On Some Problems In Learning Bayesian Network

Bayesian networks, BNs (also called Belief networks, probability networks or casual networks) evolve from path analysis, casual model and impact graph. BNs connected the probabilistic and graphical theory, is a compact representation of complex joint probability distribution. BNs have sound probabilistic semantics, explicit encoding of relevance relationships, inference algorithms and learning algorithms that are fairly efficient and effective in practice, and decision-making mechanism of facility, which led BNs to be one of the best methods for dealing with uncertainty in AI domain. Many researchers researched on it widely, BNs have been applied in many fields, such as modern expert systems, diagnosis engines, decision support systems, and data mining systems. But it is difficult or even impossible to construct BNs only by expert with domain knowledge, so learning BNs from data has become an important problem.Based on BNs, Machine learning and artificial immune genetic algorithm, this thesis conducts a research on learning BNs from data. The main results and contributions included in the thesis are as follows:1. Gives a qualitative and quantities analysis on the structural space of BNsThe structural space of BNs increased exponentially with the number of node (random variable). Select a proper structural space can improve the efficiency of the learning. The thesis compares the size and characters of directed graph, directed acyclic graph and Markov equivalence class space, conclude that learning in Markov equivalence class space is much better. Based on the experiment and theoretical prove, analysis the efficiency of constrain on prior structural space to decrease the size, give an range for choosing the efficient parameters.2. Presents an algorithm which combining the constraint approach and score search approach to orient the edges.The structure of BNs is a directed acyclic graph. The DAG not only represents the conditional independence, but also represents the casual relations between variables. These relations are very important in knowledge modeling and casual discover. This paper presents an algorithm which combining the constraint approach and score search approach to orient the edges. In the algorithm times of zero order and first order CI test is polynomial; The search space can be decomposed to sub graph, improving the efficiency of the algorithm. The output of the algorithm is largest chain graph, which just orienting the statistical distinguishable edges, keep the indistinguishable edges undirected. This graph present the causal relation more accuracy, and more convenient for combining domain knowledge. This algorithm gives a mapping from skeleton space to Markov equivalence class space, which is the base for the immune genetic algorithm presents following.3. Present a skeleton based immune genetic algorithm to learn the Markov equivalence classThe existing algorithms, which learning Bayesian network with genetic algorithm, searching in the directed graph space , the genetic operators could generate illegal offspring structures, the number of illegal structures is exponential, which infect the efficiency of learning; some BNs are Markov equivalent, equivalence structures are statistic indistinguishable, compare the structures in same equivalent class slow down the speed of convergence. This paper resents an immune genetic algorithm to learn the equivalence class of Bayesian network, which combining the constraint based approach and score-search based approach. The algorithm can avoid generating illegal structures; by the property of Markov equivalence, the immune operators mapping the search space from skeleton space to Markov equivalent class space. The experiment show that the search space was decreased, compare with the genetic algorithm search in DAG space, the efficiency and the accuracy was improved.4. Extends the immune genetic algorithm to learn dynamic BNs (DBNs)BNs depict static state, but in real world there are many problem changed with time. DBNs can represent complex stochastic processes. Compare with hidden Markov model and Kalman filter models, DBNs have more generalized presentation ability, and can perform approximate inference. BNs can be viewed as composition of two BNs: prior network that specifies a distribution over initial states, and transition network that specifies the transition probability from one state to the other state. Using immune GA algorithms to learn prior network and transition network respectively, DBNs can be learned.The analysis results of the search space, the presented algorithms to orient the edges and learning BNs and DBNs are theoretical and practical benefit to further researches of BNs.