您的当前位置：首页离散动态贝叶斯网络的直接计算推理算法

离散动态贝叶斯网络的直接计算推理算法

来源：画鸵萌宠网

2005年9月第27卷　第9期

文章编号:10012506X(2005)0921626205

系统工程与电子技术

SystemsEngineeringandElectronicsSep.2005Vol.27　No.9

离散动态贝叶斯网络的直接计算推理算法

史建国,高晓光

(西北工业大学电子信息学院,陕西西安710072)

　　摘　要:离散动态贝叶斯网络是对动态过程进行建模和定性推理的有力工具。但是目前所用的各种推理

算法都需要进行复杂的图形变换,不易于计算机编程实现而且计算时间长。为此,基于概率论和贝叶斯网络的基本性质,提出了离散动态贝叶斯网络的直接计算推理算法,从理论上对算法进行了推导并进行了实例验证。该算法的最大优点就是不需要复杂的图形变换,非常适合于计算机编程实现,而且在某些情况下推理速度快于其它算法。

关键词:贝叶斯网络;推理;算法中图分类号:TP181　　　　文献标识码:A

Directcalculationinferencealgorithmfordiscretedynamicbayesiannetwork

SHIJian2guo,GAOXiao2guang

(AcademyofElectronicInformation,NorthWesternPolytechnicUniv.,Xi’an710072,China)

　　Abstract:DiscretedynamicBayesiannetworkisacapabletoolformodelingandqualityinferringfordynamicpro2cess,butthecurrentinferencealgorithmswecanreadinallmaterialsareallbasedoncomplicatedfiguretransforma2tions.Theyarehardtoprogrammingandneedlongtimeforcalculation.Aimedonthisproblem,wepresentadirectcalculationinferencealgorithmfordiscretedynamicBayesiannetworkbasedontheprobabilitytheoryandthebasiccharactersoftheBayesiannetworkandverifyitbysamples.Themostadvantageofthisalgorithmisthatitneedsnotperformingcomplicatedfiguretransformation,itiseasytoprogramming,andundersomeconditions,itcanworkouttheresultsquicklyanddirectly.Itismoreusefulinsomeapplicationswherethetimerequestsisrelaxed.

Keywords:Bayesiannetwork;inference;algorithm

1　引　言

动态贝叶斯网络是对动态系统进行建模和状态估计的主要工具,而离散动态贝叶斯网络是对动态系统进行定性判断和推理的重要工具。其最突出的优点是可以根据多个时刻的观测值来对系统的状态进行定性推理,因此相对于离散静态贝叶斯网络而言,更能够实现观测值的互相补充和修正,更能够处理观测值的不确定性或者误差,推理结果也更可靠。用离散动态贝叶斯网络对动态系统进行定性推理和判断,更能够保持推理判断过程的鲁棒性和推理判断结果的合理性。因此动态贝叶斯网络,特别是离散动态贝叶斯网络,是近年国际上的研究热点[1～4],国内也开始了静态贝叶斯网络和动态贝叶斯网络的研究[5]。动态贝叶斯网络的应用研究的文献非常多[6,7],但是作者目前所见所有介绍离散动态贝叶斯网络的文献,介绍的推理方法都是基于图形变换,而且都没有

收稿日期:2004-11-29;修回日期:2005-03-17。

给出完整的数学公式。文献[2]介绍了离散动态贝叶斯

网络推理的边界算法和接口算法,接口算法是目前应用最广泛的算法,但是其计算过程首先要进行图形变化,然后进行前向后向递推,因此编程繁琐,而且计算时间较长,对于计算机的编程实现很不方便。本文提出离散动态贝叶斯网络的直接推理计算算法,目的就是给出离散动态贝叶斯网络推理的完整的数学公式,使得离散动态贝叶斯网络的推理算法更加规范和直观,易于计算机编程实现。而且理论分析和实际计算,表明在某些情况下,这种算法的计算速度快于接口算法。

2　离散动态贝叶斯网络的接口算法

2.1　接口算法描述

离散动态贝叶斯网络[2]是随时间发展的离散静态贝叶斯网络。对于一个T个时间片的离散动态贝叶斯网络,假定每个时间片有n个隐藏节点,有m个观测节点,分别为

基金项目:国家自然科学基金(0205019),航空支撑基金(04C53009)资助课题

作者简介:史建国(1965-),男,副教授,博士研究生,主要研究方向为先进火力控制理论。E-mail:cheeryapple@126.com

　第27卷　第9期离散动态贝叶斯网络的直接计算推理算法

・1627　・　

(X1,X2,…,Xn)和(Y1,Y2,…,Ym),则离散动态贝叶斯网

络的推理的根本目的是计算

p(x11,x12,…,x1n,……xT1,xT2,…,xTn|

y11,y12,…,y1m,……yT1,yT2,…,yTm)

(1)

图中Nt是除接口外其他节点组成的连接树结构。

将所有时间片的BN通过接口连接起来,就构成如图2的连接树形式,这其实是一种连接树的接合形式。

式中:xij(yij)分别表示第j个时间片的第i个隐藏节点(观测节点)处于某个状态。

文献[1]介绍了离散静态贝叶斯网络的基本概念,性质和推理的连接树算法。文献[2]介绍了目前应用最广泛的离散动态贝叶斯网络的边界算法和接口推理算法。接口算法是对边界算法的改进,为了便于和本文提出的直接计算推理算法比较,在此简单介绍离散动态贝叶斯网络推理的接口算法。

接口算法是把向下一个时间片发出弧的所有隐藏节点作为分离集[1,2],包含一个时间片内所有的向下一个时间片发出弧的节点的集合构成的分离集,就称为接口,它是两个时间片通信的界面和接口,记为I。推理的目的是计算P(It|y1∶T)。T为时间片的个数。因为:y1∶T分为两个部分,一部分是y1∶t,另外一部分是yt+1∶T,因此可以将p(It|y1∶T)分成两步进行,先计算出p(It|y1∶t),然后再从最后的时间片逐级吸收p(It|yt+1∶T)。这样就形成前向和后向两个计算过程,称为前向通道和后向通道。

在前向通道,一个时间片内的接口It,受到上一个时间片内的接口It-1的影响,也影响下一个时间片的接口It+1。这样,由上一个时间片内的接口It-1、本时间片内的接口It和本时间片内的所有非接口节点Nt=Vt\\It、以及它们之间的弧,又构成了一个新的离散静态贝叶斯网络(Bayesiannetwork,BN)。完全可以如静态BN的推理一样进行精确推理。这个新的BN称为“1/2时间片离散动态贝叶斯网络(dynamicbayesiannetwork,DBN)”。

前向通道的目的是计算p(It|y1∶t),由于y1∶t是通过I1∶因此需要从t=1开始计算。t-1影响It的。由于初值p(I1|y1)可以通过纯粹的BN推理求出。这样问题变成已知p(It-1|y1∶“1/2时间片DBN结t-1)和构”、条件概率表、观测值、状态转移函数的条件下,计算p(It|y1∶t)的问题。这本质上是一个静态贝叶斯网络的推理问题。采用连接树算法[1],此“1/2时间片DBN”要转换成一棵连接树,但此连接树必须有一个含It-1的圈Dt,和一个含It的圈Ct。这完全可以通过有意识的安排连接树的建立过程来实现,其它节点可以组成其它圈,见文献[1]中连接树的建立过程。

这样一个“1/2时间片DBN”对应的连接树的形式如图1所示。

图2　三个“1/2时间片DBN”对应的连接树

这样前一时刻的BN通过其接口影响当前时刻,当前

(1)构建t时刻的“1/2时间片DBN”对应的连接树Jt,并将所有圈和分离集的势都初始化为1。

(2)从Jt-1的圈Ct-1的势中排斥其它节点,剩下It-1

的势,将其乘到Jt的圈Dt的势上。

(3)对时刻t内的BN中的每一个节点,选择一个包含其所有双亲的圈作为双亲圈,将其条件概率乘到双亲圈的势上。对于观测变量,按文献[1]中的方法更新其势(取当前观测值时势为1,取其它值的势为0),将新的势乘到双亲圈的势上。至此Jt的初始化完成,剩下就是校准连接树,更新Ct的势。

(4)将Ct作为根,向根节点收集证据[1],引起消息传

递,使得连接树中所有的圈的势都更新。

注:势是一个与变量或变量组合的分布成比例的正数。见文献[1]中连接树的初始化。2.1.2　后向通道

(1)输入的已知量是前向通道留下的Ct,Dt及其它圈及分离集的势,还有就是t+1时间片传递过来的代表p(Dt+1|y1∶T)的势,即Dt+1更新过的势。

(2)对Dt+1更新过的势进行排斥,剩下It,此时就是与p(It|y1∶T)成比例的势。其作为Dt+1向Ct传递的消息。

(3)Ct通过接口It对Dt+1传来的消息进行吸收,即

图1　“1/2时间片DBN”对应的连接树

　・1628　・

系统工程与电子技术2005年　

∑<

old

<×Dt+1\\ItDt+1ct

Ct\\It

　　分式代表接口It的势的新值与势旧值之比

(4)从Ct开始散布证据,更新所有t时刻Jt中圈和分离集。此时Dt及其它圈及分离集的势都得到更新,因为此时Dt的势代表p(Dt|y1∶T),可以认为是得到了p(It|y1∶T)。

(5)一直递推到t=1,对所有的t,p(It|y1∶T)都计算

间,再假定离散动态贝叶斯网络的时间片个数是T,则接口算法的时间复杂性为O(2T((D+s)+2((k+D-1)×w-1s+2(k+D-1)×sw)))。加入w的范围,经过整理得到接口算法的时间复杂性(不包括连接树的建立时间)为

k+1

O(T(k+D-1)×s)))～O(T(k+D-1)×

k+n

)))

3　动态贝叶斯网络的直接计算推理算法

3.1算法描述

出来了。

2.2　接口算法分析

上述接口算法,最直观的现象就是必须建立一棵连接树,这是图形变换操作。不仅需要大量的计算时间,而且需要大量的存储空间来存储图形结构,且编程实现很麻烦。假定某个离散动态贝叶斯网络每一个时间片有D个节点,其中有n个隐藏节点,有k个节点向下一个时间片发出弧,则每一个“1/2时间片DBN”实际有k+D个节点。对这个“1/2时间片DBN”建立连接树,假定每一个圈中的节点个数为w(w>k)个,则w的数值位于区间[k+1,k+n],最坏的情况可能产生k+D-1个圈,在此连接树上进行推理,进行势的初始化,假定s是节点状态数的最大值,则可能需要进行D×s次乘法运算,进行连接树的初始校准,最多可能需要进行(k+D-1)×sw-1次加法运算和2(k+D-1)×sw次除法和乘法运算。插入证据进行推理也同样需要进行(k+D-1)×sw-1次加法运算和2(k+D-1)×sw次除法和乘法运算。所以,除去连接树建立的时

一个具有n个隐藏节点和m个观测节点的离散静态贝叶斯网络随时间发展就得到T个时间片的离散动态贝叶斯网络,由于观测值只有一种组合状态,因此在此观测值下隐藏变量的分布为(实际是一种后验概率)

p(x11,x12,…,x1n,…,xT1,xT2,…,xTn|

y11,y12,…,y1m,…,yT1,yT2,…,yTm)

　　任何贝叶斯网络推理的基础都是贝叶斯公式(2)和贝叶斯网络的条件假设(3)。

p(x|y)=

p(yx)=

p(y)

∑

p(yx)p(yx)

(2)

p(x1,x2,…,xn)=

i=1

∏p(x

|pa(xi))(3)

式中:(X1,X2,…,Xn)———一个静态贝叶斯网络的节点集合,p(x1,x2,…,xn)———一个贝叶斯网络的所有节点的一个联合分布,pa(xi)———节点Xi的双亲集合。

由式(2)和式(3),可以得到

p(x11,x12,…x1n,……xT1,xT2,…xTn|y11,y12,…y1m,……yT1,yT2,…yTm)=p(x11,x12,…x1n,……xT1,xT2,…xTn,y11,y12,…y1m,……yT1,yT2,…yTm)

x11,x12,…x1n,……xT1,xT2,…xTn

∑

p(x11,x12,…x1n,……xT1,xT2,…xTn,y11,y12,…y1m,……yT1,yT2,…yTm)

(4)

由于离散动态贝叶斯网络本身也符合条件性假设,因此有

p(x11,x12,…x1n,……xT1,xT2,…xTn|y11,y12,…y1m,……yT1,yT2,…yTm)=

p(y∏

i,j

|pa(yij))

)p(x∏

i,k

|pa(xik))(5)

　　因此有

p(x11,x12,…x1n,……xT1,xT2,…xTn|y11,y12,…y1m,……yT1,yT2,…yTm)=

)p(x|pa(x))p(y|pa(y))∏∏

)p(x|pa(xp(y|pa(y))∏∑∏

i,jikx11x12xT1・・xTn

ijijik

ik)

)

(6)

i,ji,k

i∈[1,T],j∈[1,m],K∈[1,n]

式中:xij———Xij的一个取值状态。第一个下标表示第i

时间片,第二个下标表示该时间片内的第j个隐藏节点。yij———观测变量Yij的取值。pa(yij)———yij的双亲节点

集合。

如果观测值是多状态的,即某些观测变量处于各个状态都有一定的概率。则

　第27卷　第9期离散动态贝叶斯网络的直接计算推理算法

p(x11,x12,…x1n,…xT1,xT2,…xTn|y11o,y12o,…y1mo,…yT1o,yT2o,…yTmo)=

・1629　・　

y11,y12…yTm

∑

x11x21…xT1・・xTn

p(ypa(Y))∏p(x|pa(x))∏

p(y|pa(Y))∏p(x|pa(x∑∏

ij|

i,ji,kijijik

ik))

×∏p(Yij=yijo)

i,ji,k

i∈[1,T],j∈[1,m],K∈[1,n](7)

式中:Yjio———第i个时间片内第j个观测节点yij的观测状

态。p(Yij=yijo)———Yij处于对应状态的概率。3.2　算法分析

假定离散动态贝叶斯网络的每一个时间片有D的节点,其中有n个隐藏节点,节点的最大状态数为s,离散动态贝叶斯网络的时间片个数为T,则计算式(6),计算分母的每一项,需要进行D次乘法运算,计算一个联合分布,需要DsTn次运算。计算出所有联合分布,只需要再进行sTn次除法运算。计算出每一个隐藏变量的分布,需要进行Tn-1ns次加法运算,因此上述算法的时间复杂性为O(nsTn)。和接口算法的时间复杂性(不含连接树建立时间)

k+1k+n

)))O(T(k+D-1)×s)))～O(T(k+D-1)×s

比较,可以看出,当时间片个数较少,并且隐藏节点数目较少时,本文提出的直接推理算法占有明显的时间优势,而且接口算法还需要进行复杂的图形变化。当隐藏节点数目较多,并且时间片数目较多时,接口算法的计算时间就占优势,尽管其需要进行复杂的图形变换。而实际应用中,所用的离散动态贝叶斯网络模型的时间片个数都是有限的,而且一般隐藏节点的个数也是比较少的,所以本文提出的离散动态贝叶斯网络推理的直接计算算法具有一定的应用价值。特别是这种算法编程简单,易于实现,在实时性要求不高的应用中更具有应用价值。

x和y都有两个状态,x可取a或b,y可取s或r,先验

概率为

p(x1=a)=p(x1=b)=0.5

条件概率为

p(yi=s|xi=a)=0.7,　p(yi=s|xi=b)=0.2

p(yi=r|xi=a)=0.3,　p(yi=r|xi=b)=0.8

i=1,2

时间片间的条件概率为p(xi+1=a|xi=a)=0.9,　p(xi+1=b|xi=a)=0.1

p(xi+1=a|xi=b)=0.1,　p(xi+1=b|xi=b)=0.9

i=1,2

假定现在观察2个时刻,观测值为y1=s,y2=s,其含义为

p(y1=s)=1,　p(y2=s)=1,p(y1=r)=0,　p(y2=r)=0

要求计算这种观测值下x1和x2的后验分布。4.1　采用直接计算推理算法计算

式(6)在此处具体化为

p(x1,x2|y1,y2)=

p(y1,y2|x1,x2)p(x2|x1)p(x1)

∑

x1x2

p(y1,y2|x1,x2)p(x2|x1)p(x1)

4　算法的实例检验

待计算的离散动态贝叶斯网络模型如图3所示。

p(y1|x1)p(y2|x2)p(x2|x1)p(x1)

∑

x1x2

p(y1|x1)p(y2|x2)p(x2|x1)p(x1)

则后验概率

图3　计算实例用的离散动态贝叶斯网络

p(x1=a,x2=a|y1=s,y2=s)=

p(y1=s,y2=s|x1=a,x2=a)p(x2=a|x1=a)p(x1=a)∑

x1x2

p(y1=s,y2=s|x1,x2)p(x2|x1)p(x1)

p(y1=s|x1=a)p(y2=s|x2=a)p(x2=a|x1=a)p(x1=a)

∑

x1x2

p(y1=s|x1)p(y2=s|x2)p(x2|x1)p(x1)

　　上式分母的加和表示的四种组合x1x2,用到的都是先验概率和条件概率。

同理计算

p(x1=b,x2=a|y1=s,y2=s),p(x1=a,x2=b|y1

=s,y2=s)和p(x1=b,x2=b|y1=s,y2=s),这样就得到

x1x2的后验分布。通过加和就可以获得x1和x2的后验

　・1630　・

系统工程与电子技术2005年　

分布。

将已知的条件概率代入,计算可得

p(x1=a,x2=a|y1=s,y2=s)=0.87327

p(x1=b,x2=a|y1=s,y2=s)=0.027723p(x1=a,x2=b|y1=s,y2=s)=0.027723p(x1=b,x2=b|y1=s,y2=s)=0.071287

p(x1=a|y1=s,y2=s)=0.90099p(x1=b|y1=s,y2=s)=0.09901p(x2=a|y1=s,y2=s)=0.90099p(x2=b|y1=s,y2=s)=0.09901

上述过程,用Matlab语言编程,在P32900机器上运行,时间不到0.01s。4.2　用接口算法的计算结果

用接口算法,用Matlab语言编程,在P3900机器上运行,得到结果(如图4所示),运行时间为0.03s。p(x1=a|y1=s,y2=s)=0.9010

p(x1=b|y1=s,y2=s)=0.0990p(x2=a|y1=s,y2=s)=0.9010p(x2=b|y1=s,y2=s)=0.0990

优势,而且接口算法还需要进行复杂的图形变化。当隐藏节点数目较多,并且时间片数目较多时,接口算法的计算时间就占优势,尽管其需要进行复杂的图形变换。

该算法的最大优点是不需要进行复杂的图形变化,计算公式简单实用,适合于计算机编程实现,而且可以用并行计算算法实现,以加快算法的计算速度。而实际应用中,所用的离散动态贝叶斯网络模型的时间片个数都是有限的,而且一般隐藏节点的个数也是比较少的,所以本文提出的离散动态贝叶斯网络推理的直接计算算法具有一定的应用价值。特别是这种算法编程简单,易于实现,在实时性要求不高的应用中更具有应用价值。对于空天无人作战飞行器的智能自主控制,需要进行自动目标识别,态势评估和指挥决策,这些问题用离散动态贝叶斯网络建模,都是隐藏变量的个数很少(一般就一个),实际应用中时间片的个数也是很小(一般4级)的,因此本文提出的算法具有较好的应用价值。

参考文献:

[1]HenrikBengtsson.Bayesiannetworks[EB/OL].Mathematical

StatisticsCenterforMathematicalSciencesLundInstituteofTechnology,Sweden2003.

[2]KevinPatrickMurphy.Dynamicbayesiannetworks:representation,in2

ferenceandlearning[EB/oL].Adissertationsubmittedinpartialsat2

isfactionoftherequirementsforthedegreeofDoctorofPhilosophyinComputerScienceinthegraduatedivisionoftheuniversityofCalifor2nia,Berkeley.Fall,2002.

[3]AlexanderKuenzer.AnempiricalstudyofDynamicBayesiannet2

worksforusermodeling.InstituteofIndustrialEngineeringand

图4　接口计算结果柱状图

Ergonomics[EB/OL].AachenUniversityofTechnology,Ger2

many,2002.

从上述两种方法的计算结果看,除了计算的舍入误差之

外,二者的计算结果是完全一致的,这也可以从一个侧面证明本文提出的离散静态信念推理的直接计算算法的正确性。而且经过实际的时间测试,直接计算算法明显快于接口算法。

[4]UriNodelman,SheltonChristianR,DaphneKoller.Learningcon2

tinuoustimebayesiannetworks[EB].2002.

[5]王辉.用于决策支持的贝叶斯网络[J].东北师大学报自然科学

StanfordUniversity.

5　结　论

本文提出的离散动态贝叶斯网络的直接计算推理算法,是由贝叶斯网络的条件无关特性和贝叶斯公式推导而来,理论上是正确的。计算实例也证明了算法的正确性。和最常用的接口算法比较,当时间片个数较少,并且隐藏节点数目较少时,本文提出的直接推理算法占有明显的时间

版,2001,33(4):26-30.

[6]VladimirPavlovi′c1,RehgJamesM,Tat2JenCham.Adynamic

bayesiannetworkapproachtotrackingusinglearnedswitchingdy2namicmodels[EB].CompaqComputerCorporation,2003.[7]VladimirPavlovi′c,RehgJamesM,Tat2JenCham,etal.Ady2

namicbayesiannetworkapproachtofiguretrackingusinglearneddynamicmodels[EB].CompaqComputerCorporation,2003.

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文