The Research on Structure Learning of Dynamic Bayesian Network
|School||Beijing University of Technology|
|Course||Computer Software and Theory|
|Keywords||Bayesian network dynamic Bayesian network structure learning particle swarm optimization ant colony optimization|
Dynamic Bayesian Networks (DBN) is a species of Bayesian Networks (BN) designed to model stochastic temporal processes, which models the stochastic evolution of a set of random variables over time. Owing to DBN’s significant advantages in describing nonlinear, temporal, evolving and uncertain relationships and strong ability of probabilistic inference, studies on DBN and it’s application are all the time hot topics of AI. This thesis mainly focuses on Dynamic Bayesian Networks structure learning problem in the following three directions:1) A new algorithm for learning DBN’s structure using particle swarm optimization (I-BN-PSO) is proposed by extending the algorithm BN-PSO. First, the new algorithm uses order-0 independence tests to effectively restrict the space of candidate solutions, moreover, the mutual information obtained in independence tests phase is used as heuristic knowledge to initialize the particle swarm. And then, a new particle position’s subtraction operator is designed based on the increase of MDL score, which makes the particle flying effectively. At last, a disturbed strategy is applied to accelerate the particles to overstep the local extremum. The experiment results on the benchmark databases show that these strategies are efficient, and the solution quality of the new algorithm is better.2) To solve the drawbacks of the ant colony optimization for learning Bayesian networks (I-ACOB), a new algorithm based on variable search space and simulated annealing strategy (VSMI-ACOB) is proposed, which combined two basic ideas of Constraint Satisfaction and Score-and-Search together. First, the new algorithm uses order-0 independence tests with a self-adjusting threshold value to effectively restrict the space of candidate solutions, so that the search process for ants can be improved while keeping better solution quality. Then, an optimization scheme based on simulated annealing is introduced to improve the solution quality, and a knowledge-guided strategy is employed to enhance the optimizing efficiency in the local optimization process. Finally, the algorithm is tested on different scale benchmarks and compared with the recently proposed stochastic algorithms. The results show that these strategies are efficient, and the solution quality of the new algorithm precedes the other algorithms while the convergence speed is faster.3) Aiming at the character of Dynamic Bayesian transition networks, the paper proposes a new transition networks learning algorithm based on ant colony optimization by extending the static Bayesian networks structure leaning algorithm VSMI-ACOB. In the new algorithm, ants select arcs from the inter-arcs between time slices before from the intra-arcs in one slice, and then the interval optimization strategy is improved by decreasing the times of optimization operation. A number of experiments and comparisons demonstrate the new algorithm is efficient and can handle large datasets.