【作者】 俞奎；

【导师】 王浩；

【作者基本信息】 合肥工业大学 ， 计算机软件与理论， 2007， 硕士

【摘要】 贝叶斯网络(Bayesian Networks，BN)简洁的不确定性知识表示形式和双向的推理能力，使其成为人工智能领域的研究热点之一。贝叶斯网络建模技术与推理算法的研究是其理论与应用研究的核心和难点问题。本文对贝叶斯网络建模技术和推理算法中存在的一些问题做了深入的研究，具体的研究内容如下：(1)具有缺省数据或含有隐变量的贝叶斯网络参数学习和结构学习是贝叶斯网络学习研究的热点同时也是研究的难点。基于EM算法框架的BN学习算法可以较好的处理上述问题。但该类算法易于收敛到局部最优，同时计算量过大也是其应用的一个瓶颈问题。本文针对EM算法学习贝叶斯网络参数的计算问题，提出了一种并行EM算法提高大样本条件下贝叶斯网络参数学习的速度。在此基础上，我们深入分析了结构EM算法(Structural EM，SEM)，用并行的方法来进行SEM算法的参数学习，从而提出一种并行的贝叶斯网络结构学习算法一并行SEM算法(Parallel SEM，PL-SEM)。PL-SEM算法实现了并行计算期望充分统计因子和当前贝叶斯网络的参数，从而大大降低了结构学习的时间复杂性，也为并行的贝叶斯网络结构学习算法提供一个框架。(2)我们在上述工作的基础上，进一步通过实验深入分析了在数据缺省的情况下领域知识对SEM算法的影响，通过实验分析我们得出：在数据缺省的小样本条件下，领域知识对BN结构学习起着至关重要作用。进而我们提出一种基于知识导向的SEM算法KL-SEM(SEM learning with Domain Knowledge)。实验表明KL-SEM既可保证学习精度，又降低了结构搜索范围。(3)动态贝叶斯网络(Dynamic Bayesian Networks，DBN)是贝叶斯网络模型的扩展，是具有处理时序特征数据能力的复杂随机模型。在分析已有动态贝叶斯网络结构学习算法的基础上，本文提出一种基于进化马尔可夫链蒙特卡罗算法的动态贝叶斯网结构学习算法DBN-EMC。实验结果表明该算法不仅可有效的学习动态贝叶斯网络的结构，而且显著地提高了算法的收敛速度。(4)概率推理是贝叶斯网络在处理不确定性问题过程中要解决的一个核心问题。贝叶斯网络的推理算法分为精确推理和近似推理，都被证明是NP难题。联合树算法是贝叶斯网络的经典的精确推理算法，但联合树构建中的三角化操作是一个NP难题。针对这个问题，我们提出了一种TAGA算法来求解BN的三角化结点删除次序。更多还原

【Abstract】 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.更多还原