The Research Of Learning And Inference Algorithm For Bayesian Networks

Bayesian networks (BN) are compactly graphical representation of joint probability distributions over a set of random variables. It has become the tool of choice of many A1 researchers for problems involving reasoning under uncertainty. The research of learning Bayesian networks from data and inference algorithms is two basic tasks for Bayesian networks. The thesis deeply studies some exiting hard problems of leaning and inference on Bayesian Networks, the research problems as follows.(1) Learning Bayesian networks is still a challenging problem with incomplete data. The algorithm for Learning BN based on the framework of EM algorithm can adapt the problems. But it could be prone to halt at local optima, moreover, the computation of expected counts is the bottleneck to keep it from the real-world application. Aimed to the EM algorithm requiring significant computational resources for learning Bayesian Network parameters with large datasets, the PL-EM algorithm is proposed to improve the learning speed. Then based on the work, we deeply analyze structural EM algorithm, and presents a parallel learning algorithm, PL-SEM, for learning Bayesian networks, based on an existing structural EM algorithm (SEM). Since the computation of the expected statistics is in the parametric learning part of the SEM algorithm, PL-SEM exploits a parallel EM algorithm to compute the expected statistics. So, PL-SEM effectively computes the expected statistics, and greatly reduces the time complexity of learning Bayesian networks.(2) Based on the work above, furthermore, we have the deeply empirical study of domain knowledge impact on learning Bayesian Networks with missing data. Our empirical results indicate that with missing data, domain knowledge can be raise serious concerns for leaning Bayesian Networks, especially when there is rarely enough training data to enable accurate learning of the network structures. Based on those. KL-SEM (SEM algorithm with domain knowledge) is proposed, which incorporate domain knowledge into it. The experimental results show that KL-SEM not only enables accurate learning of the structures, but also reduces the search place of network structure. (3) Dynamic Bayesian Networks (DBN) are a species of Bayesian Networks designed to model stochastic temporal processes, which models the stochastic evolution of a set of random variables over time. Since the convergence of Markov chain Monte Carlo algorithm is too slow, a novel method, called DBN-EMC algorithm, is proposed which integrates techniques from genetic algorithm into the Markov chain Monte Carlo framework. The experimental results show the algorithm performs well. It not only can effectively learn the structure of Dynamic Bayesian Networks but also significantly improve the speed convergence of Markov chain Monte Carlo.(4) Probability reasoning is one of the key problems in the course of Bayesian Networks dealing with the problem under uncertainty. The inference algorithms are classified into two categories: exact and approximate algorithms and they are proved to be both NP-hard problems. The Junction tree is a famously exact inference algorithm for Bayesian Networks. However, search for an optimal node elimination sequence for the triangulation of Bayesian networks is an NP-hard problem. In the thesis, a new method, called the TAGA algorithm, is proposed to search for the optimal node elimination sequence. Experimental results show that the TAGA algorithm outperforms existing algorithms.