资源描述：
《贝叶斯网络ve推理算法的并行化研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、云南大学学报(自然科学版),2010,32(4):392~395CN53-1045/NISSN0258-7971JournalofYunnanUniversity*贝叶斯网络VE推理算法的并行化研究向光军,孔兵,欧家钦(云南大学信息学院,云南昆明650091)摘要:贝叶斯网络是一种强有力的不确定性推理和数据分析工具.网络推理是贝叶斯网络的重要内容之一.VE算法是利用联合分布的分解来简化推理的贝叶斯网推理算法.提出一种基于最小缺边搜索算法的消元顺序(PL_OE)算法,使VE算法可并行执行,降低了贝叶斯网推理的时间复
2、杂性.关键词:贝叶斯网络;变量消元(VE)算法;最小缺边搜索(MDS)算法中图分类号:TP181文献标识码:A文章编号:0258-7971(2010)04-0392-04[1]贝叶斯网络(BayesianNetworks,BNs)是元顺序是NP问题.由于不同的消元顺序,VE算法Pearl提出的一种基于概率论和图论的不确定知识的计算量不同,为减少计算量,寻找最优的消元顺[5]表示模型,它一方面用图论的语言直观揭示问题的序,人们先后提出了最大势搜索(MaximumCar[6]结构,另一方面又按照概率论的原理对
3、问题的结构dinalitySearch,MCS)和最小缺边搜索(Minimum加以利用,降低推理的计算复杂度.它以其坚实的DeficiencySearch,MDS)等启发式算法.本文根据理论基础,知识结构的自然表达方式,灵活的推理VE算法的执行过程特点,提出一种基于MDS算法能力,方便的决策机制而成为近年来生物信息学、的消元顺序(PL_OE)算法,该算法生成的消元顺编码学、机器学习等领域的研究热点.在故障诊断、序能够使VE算法并行执行,并通过实验验证了算[2-3]数据挖掘、医疗诊断等领域已得到成功应用.法的高效性.多连
4、通贝叶斯网络是指在有向无环图中至少1贝叶斯网络推理存在这么2个节点,它们之间的路径不是唯一的.对于多连通贝叶斯网络,现有的推理算法都不同程1.1贝叶斯网络推理贝叶斯网络结构隐含着一度地存在一些问题:如联合树算法的空间复杂性种很强的条件独立关系,当一个节点的父节点给定高;消息传递与汇聚算法对多连通网络处理困难;后,除该节点的后继节点以外,它与其余所有节点[4]仿真算法计算复杂性高等.变量消元(Variable之间条件独立.根据条件独立假设和d-分离性Elimination,VE)算法能够较好地处理此类贝叶斯质,贝叶
5、斯网络中变量的联合概率分布为n网络.VE算法是由Zhang和Poole首先提出的,其p(X1,X2,,Xn)=p(Xi
6、(Xi)),原理源自关于不定序动态规划的研究.VE算法的i=1变种也曾独立地出现于其它领域,如计算机生物学其中,(Xi)表示节点Xi的父节点.中进行家系树分析的pruning-and-peeling算贝叶斯网络的推理任务是在给定对一个变量法、隐马尔可夫模型中的forward-backward算集合E的观测值(证据)时,计算出另一个被调查法,以及状态空间模型中的Kalmanfilter
7、ing-的变量集合Q的后验概率分布(即P(Q
8、E)).目smoothing算法等.然而,在VE算法中寻找最优消前已经设计出许多有效的推理算法,包括近似推理*收稿日期:2010-03-18基金项目:国家自然科学基金项目资助(60763007).作者简介:向光军(1983-),男,回族,河南人,硕士生,主要从事贝叶斯网络理论与应用.通讯作者:孔兵(1968-),男,云南人,副教授,主要从事智能数据处理、软件工程方面的研究.第4期向光军等:贝叶斯网络VE推理算法的并行化研究393算法和精确
9、推理算法.已经证明:在一般贝叶斯网returnh(Q)h(Q).[7]Q络上的推理问题,是一个NP问题.但是,利用联Elim(F,Z)合分布的分解,仍然可以简化推理的复杂度,VE算输入:一个函数集合F;待消元变量Z.法就是一个很好的例子.输出:另一个函数集合.1.2VE算法VE算法(算法1)求解的主要思过程:想是首先将贝叶斯网络图形化的联合概率分解为从F中删去所有涉及Z的函数,设这些函数是一系列条件概率表的乘积;然后在符号层面上对公{f1,,fk};式进行变换,改变求和时节点的消元顺序及求和运k算乘积运算的先
10、后顺序,以达到减少求和与乘积运gfi;i=1算量的目的,最后按照变换后的公式进行逐步的求hg;和与乘积运算以得到待求结果.ZElim(F,Z)作为VE算法的基本步骤,我们假将h放回F;设函数F(X1,X2,,Xn),消去消元变量X1得到函returnF.数G(X2,,Xn),可得2VE算法分析与并行化G(X2,,X
