贝叶斯网络精确推理算法的研究

贝叶斯网络是以概率理论为基础的不确定知识表示模型,贝叶斯网络推理的目的是得到随机变量的概率分布。目前,最流行的推理算法是联合树算法,它的主要思想是将贝叶斯网络转化为一棵无向树,在无向树上完成消息传递过程,求出原贝叶斯网络中任意随机变量的概率分布。为了降低算法的计算时空复杂度,对算法进行了不断的改进,为贝叶斯网络推理算法的进一步研究提供了条件。     

基于结构分析的局部Gibbs抽样自动推理算法

提出一种基于结构分析的局部Gibbs抽样的贝叶斯网络推理算法(S-LGSI).S-LGSI算法基于联合树算法的概率图模型分析思想,对贝叶斯网络进行精确分解,然后根据查询结点和证据结点生成具有强相关性的局部网络模型,进而对局部网络模型进行Gibbs抽样推理.与当前基于抽样的其它近似推理算法相比,该算法降低推理的计算维数.同时,由于局部抽样模型包含了与查询结点相关的重要信息,因此该算法保证局部抽样推理的精度.算法分析和在Alarm网的实验结果表明,S-LGSI算法较显著降低时间复杂度,同时也提高推理精度.S-LGSI算法应用于上海证券交易所股票网络的推理结果与实际情况基本一致,表现出较强的实用性.     

开放式动态网络中可渗透路径预测方法仿真

针对机器学习、生物免疫以及条件概率算法下的三种可渗透路径预测方法存在的空间复杂度高、预测覆盖面小问题,提出基于贝叶斯算法的开放式动态网络可渗透路径预测方法。方法对贝叶斯算法进行描述,并基于贝叶斯算法设计可渗透路径预测方法,分析开放式动态网络可渗透过程,然后对可渗透数据进行采集并处理,提取可渗透特征,建立基于贝叶斯算法的预测模型,实现可渗透路径预测。结果表明,与机器学习、生物免疫以及条件概率算法下的三种可渗透路径预测方法相比,所提方法空间复杂度最低,预测覆盖面最大,最高可达98%。     

引入分割团的BK推理算法及其在Robocup中的应用

BK算法是动态贝叶斯网络(DBNs)的一种主要近似推理方法,但对网络的人工分割会引入较大误差.首先通过将决策结点转换成随机结点,给出基于DBNs的Roboeup协作问题的一种建模方法;然后,给出一种引入分割团的新BK算法,以减小网络分割产生的误差,并对Robocup中的两个球员配合射门问题进行推理.引入分割团的BK算法和1.5片联合树推理算法的比较实验结果表明,引入分割团使BK算法在精度损失较小的情况下,时间性能有显著提高.     

网络最短路径的动态算法

在通信网络中,两个节点间最短路径的计算是大多数路由算法的基础,对整个网络的性能有重要的影响。该文针对动态变化的网络环境,提出了一种快速的动态最短路径树算法(DMDT),并给出了算法的实现步骤。随机网络模型的仿真结果表明:DMDT算法生成的最短路径树与Dijstra算法基本一致,计算的时间复杂度较Dijstra算法有很大降低。为动态最短路径树的计算提供了一种新的选择。     

1

基于动态贝叶斯网络处理动态不确定性问题的过程中推理是非常重要的,而推理算法的优劣决定着推理的执行效率.该文提出一种较简单的1 1/2片联合树算法,在不需要限制消去顺序且只作一次扩展的条件下构造联合树,所以算法简单且具有较小的复杂度.     

灵敏性分析下的因果网络参数的扰动学习研究

联合观察数据和扰动数据学习因果网络是一种基于扰动的机器学习方法,通过扰动学习可以利用少量样本发现网络中的因果关系,扰动对于因果关系的影响主要体现在网络参数方面。提出了一种基于灵敏性分析的因果网络参数的扰动学习算法(intervention learning of parameter sensitivity analysis,ILPSA)。对于给定的先验网络,ILPSA算法利用联合树推理算法生成灵敏性函数,通过对灵敏性函数的参数重要性分析提出扰动结点的一种主动选取方法;对扰动结点的主动干扰产生扰动数据,然后联合观察数据和扰动数据,利用最大似然估计(maximum likelihood estimation,MLE)方法学习因果网络的参数,并利用KL距离对学习结果进行评价。算法比较和实验结果表明,ILPSA算法的学习结果明显好于随机选择扰动结点和无扰动情况下的方法,特别在样本较小的情况下优势更明显。     

概率XML文件树结点概率的查询算法

概率XML文件是概率数据的网络数据交换和表示标准,元素取值及其概率的查询与计算是概率XML文件的重要研究内容.概率XML文件树是一种有效的概率XML文件的数据模型,定义了概率XML文件树的基本路径和扩展路径,提出了根据可能世界原理将概率XML文件树分解为普通子XML树的集合的算法,根据路径分析原理将概率XML文件树分解为子概率XML树的集合的算法和相应的查询与计算结点及结点集合概率的算法,并通过实验进行了比较分析.实验结果表明:这两种方法是有效的;与前一种方法比较,后一种方法适合较大的概率XML文件树、结点及结点集合的概率的查询,计算过程较简单.     

基于全局消息传播的贝叶斯推理

在贝叶斯网络中，常常需要作不确定概率推理。然而针对一般复杂网络，精确推理算法由于计算复杂度太高而常常被摒弃。针对这一问题，本文提出了一种基于全局传播的PPJT近似推理算法。PPJT算法采用消息传播机制，通过消息的收集与分发过程，可以更新和修正连接树节点的团势并最终生成相容连接树。与另一种常用的近似推理算法即似然权重（Likelihood Weighting）算法的时间性能对比实验显示，采用消息传播机制的PPJT算法有效地降低了计算的时间复杂度；同时与似然权重算法的性能对比实验表明，在相对小规模观察样本输入条件下，PPJT算法能够保证更高的概率推理精度。PPJT算法为实现一般复杂网络中的概率推理提供了一种新的理论工具。     

基于因素化表示的TD（λ）算法

提出一种新的基于因素法方法的TD（λ）算法。其基本思想是状态因素化表示,通过动态贝叶斯网络表示Markov决策过程（MDP）中的状态转移概率函数,结合决策树表示TD（λ）算法中的状态值函数,降低状态空间的搜索与计算复杂度,因而适用于求解大状态空间的MDPs问题,实验证明该表示方法是有效的。     

1 1/2片联合树算法在动态贝叶斯网精确推理中的应用

基于动态贝叶斯网络处理动态不确定性问题的过程中推理是非常重要的,而推理算法的优劣决定着推理的执行效率。该文提出一种较简单的112片联合树算法,在不需要限制消去顺序且只作一次扩展的条件下构造联合树,所以算法简单且具有较小的复杂度。     

基于MPH的时延约束Steiner树算法

为了在时延约束务件下进一步优化组播树代价,并降低算法计算复杂度,研究了时延受限的Steiner树问题.分析了MPH(minimum path heuristic)算法的计算复杂度;在此基础上设计了一个时延约束Steiner树算法DCMPH(delay-constrained MPH)用于构造时延约束最小代价组播树.该算法中每个目的结点通过与当前组播树有最小代价的路径加入组播树;若时延不满足要求,则通过合并最小时延SPT(shortest path tree)树进而产生一个满足时延约束的最小代价组播树.仿真实验表明,DCMPH算法生成的组播树在保证时延要求的情况下,与同类算法相比取得了很好的代价性能和较低的计算复杂度.     

基于递推分解的Torus网络可靠性研究

为解决大规模Torus网络可靠度计算中遇到的NP难问题,引入递推分解和组合模型的思想对Torus网络的可靠性进行分析研究.递推分解的算法降低了计算网络可靠度的复杂性,组合模型的方法则降低了网络的结构复杂度.对于大规模的Torus网络,通过采用可靠度上下界逐步逼近的方法,可以得到较高精度的可靠度近似值.实验结果表明,在结点失效概率均小于0.10%时,对多达上千个结点的Torus网络仍超过90%的可靠度,而且提出的方法也适合其它并行体系结构网络的可靠度计算.     

3／2片联合树算法在动态贝叶斯网精确推理中的应用

基于动态贝叶斯网络处理动态不确定性问题的过程中推理是非常重要的，而推理算法的优劣决定着推理的执行效率。该文提出一种较简单的3/2片联合树算法，在不需要限制消去顺序且只作一次扩展的条件下构造联合树，所以算法简单且具有较小的复杂度。     

并行的贝叶斯网络参数学习算法

针对大样本条件下EM算法学习贝叶斯网络参数的计算问题,提出一种并行EM算法(Parallel EM,PL-EM)提高大样本条件下复杂贝叶斯网络参数学习的速度.PL-EM算法在E步并行计算隐变量的后验概率和期望充分统计因子;在M步,利用贝叶斯网络的条件独立性和完整数据集下的似然函数可分解性,并行计算各个局部似然函数.实验结果表明PL-EM为解决大样本条件下贝叶斯网络参数学习提供了一种有效的方法.     

Bayes网络最优近似下边缘分布的不变性

删除Bayes网络中的弧以减小网络结构的复杂性，从而降低概率推理算法的复杂度是一种对Bayes网络进行近似的方法．该文讨论了在删除Bayes网络中的一条弧之后得到的最优近似概率分布和原概率分布之间的关系，证明了对满足一定条件的结点子集而言，其边缘概率分布在近似以后具有不变性．     

混合树增广朴素贝叶斯分类模型

树增广朴素贝叶斯分类算法(TANC)虽然降低了朴素贝叶斯分类算法(NBC)的条件独立性约束,但是该模型同时又要求每个条件属性结点(除树的根结点外)都有两个父结点,这种限制同样降低了分类的正确率.因此,提出了一种基于粗糙集理论的混合树增广朴素贝叶斯分类模型(MTANC).通过在UCI数据集上的仿真实验,验证了该方法的有效性.     

基于约束最大信息熵的贝叶斯网络结构学习算法

贝叶斯网络的学习可分为结构学习和参数学习.基于约束最大信息熵的结构学习算法是一种以搜索最高记分函数为原则的方法.本文以KL距离、相互信息以及最大相互信息为基础,通过附加合适的约束函数降低变量维数和网络结构的复杂度,提出了一种附加约束的最大熵记分函数,并结合爬山法设计一种贝叶斯网络结构学习的启发式算法.通过与著名的K2和B&B-MDL算法的实验比较,结果表明该算法在时间和精度上都具有较好的效果.     

动态贝叶斯网络在战术态势估计中的应用*

针对战术态势估计的特点和要求,分析和建立了应用于态势估计的动态贝叶斯网络模型。该模型以离散变量集为研究对象。由于该动态贝叶斯网络满足Markovian特性和平稳特性,降低了网络的复杂度。相比较于贝叶斯网络模型,该动态贝叶斯网络模型考虑了时序因素,将前时刻的态势因素作为当前时刻态势估计的证据的一部分,并能对下一时刻的态势进行预测。文中采用集树（junction tree）算法,利用相关的贝叶斯网络推理软件进行了实验,实验结果表明基于动态贝叶斯网络的估计结果较贝叶斯网络的估计结果好,验证了该模型的有效性。     

基于无连接多路径路由的负载均衡

介绍了一种可以应用于Internet网络的无连接多路径路由计算方法,称为概率无连接多路径路由(probability-Disjoint Multi-paths Routing,p-DMR)。该方法使用概率构造无连接多路径,降低了在复杂网络环境中计算无连接多路径的复杂度,并将多路径路由与自适应按比例动态流量分割算法相结合,使网络性能得到优化,拥塞得到避免。