時間貝葉斯網(wǎng)絡(luò)的擴(kuò)展

時間貝葉斯網(wǎng)絡(luò)的擴(kuò)展

0貝葉斯網(wǎng)絡(luò)的應(yīng)用bn是圖論和概率的結(jié)合。bn是圖論和概率的圖形化描述，提供了一種直觀的可視化知識的方法，并使用了概率分析理論來處理不同知識組成之間的關(guān)系。概率分析的原理用于描述不同知識組成之間的狀態(tài)。每個知識元素之間的關(guān)系是由條件決定的。概率分析的網(wǎng)絡(luò)直觀地表示是一個復(fù)雜的值相關(guān)性圖。每個圖節(jié)點都代表所討論的主題區(qū)域的變量（或事件）。節(jié)點之間的弧表示事件之間的概率關(guān)系。伯里斯網(wǎng)絡(luò)在信息恢復(fù)、故障診斷和檢測、經(jīng)濟(jì)、應(yīng)用醫(yī)學(xué)、交通管理、文化教育、國防系統(tǒng)等領(lǐng)域得到了廣泛應(yīng)用。在貝葉斯網(wǎng)絡(luò)的應(yīng)用中,經(jīng)常會遇到系統(tǒng)中存在反饋、因果關(guān)系與時間相關(guān)等現(xiàn)象.如應(yīng)用貝葉斯網(wǎng)絡(luò)為項目進(jìn)度風(fēng)險建模,應(yīng)為各項活動的持續(xù)時間建模,即時間是模型中的節(jié)點之一;且活動之間的時間緊前關(guān)系、不確定性關(guān)系以及邏輯關(guān)系都可能與時間有關(guān),也就是說節(jié)點之間的關(guān)系是時間相關(guān)的.但傳統(tǒng)的貝葉斯網(wǎng)絡(luò)本質(zhì)上描述的是靜態(tài)的系統(tǒng)特征,不具備表示變量內(nèi)部以及變量之間的時間關(guān)系的機(jī)制.因此有必要對傳統(tǒng)貝葉斯網(wǎng)絡(luò)進(jìn)行適當(dāng)?shù)臄U(kuò)展.時間擴(kuò)展就是解決問題的途徑之一.在BN中表示時間主要有兩種思路,一是通過動態(tài)貝葉斯網(wǎng)絡(luò)(DynamicBayesianNetwork,DBN),將一個系統(tǒng)表示成從起始時間到終止時間的一系列快照,每一個快照包含一個完整的網(wǎng)絡(luò)結(jié)構(gòu),表示系統(tǒng)在該時間(時刻)的狀態(tài),前后兩個快照的相關(guān)節(jié)點之間添加因果聯(lián)系,表示在不同時間的節(jié)點間關(guān)系.另一種思路是對BN進(jìn)行時間擴(kuò)展.Berzuni提出在網(wǎng)絡(luò)中增加一些代表時間區(qū)間的節(jié)點,但這樣可能會顯著增加網(wǎng)絡(luò)的大小和復(fù)雜性.Tawfid和Neufeld提出將節(jié)點的條件概率視為時間的函數(shù),因此需要有關(guān)概率隨時間變化的外生知識而且需要明確網(wǎng)絡(luò)中每個節(jié)點在不同時刻的取值.Santos提出的用時間擴(kuò)展BN網(wǎng)絡(luò)結(jié)構(gòu)的方法是使每個節(jié)點具有針對于時間區(qū)間的值,同時節(jié)點的弧包含時間擴(kuò)展(時間區(qū)間關(guān)系).上述這些時間擴(kuò)展技術(shù)針對已經(jīng)定義好的連續(xù)或離散的時間區(qū)間,對于事先不能明確在不同時間區(qū)間內(nèi)取值的變量無法進(jìn)行概率推斷.本文基于一個非常重要的假設(shè)——網(wǎng)絡(luò)中的節(jié)點在獲得新證據(jù)之前保持原有的狀態(tài),對節(jié)點進(jìn)行時間擴(kuò)展,節(jié)點間的弧通過標(biāo)注因果關(guān)系發(fā)生的遲滯時間而進(jìn)行時間擴(kuò)展.重新定義時間貝葉斯網(wǎng)絡(luò),并給出了網(wǎng)絡(luò)的形式化表示.1時間貝葉斯網(wǎng)絡(luò)定義1時間聚集變量是一個有序的二元組(Σ,Ω),Ω是狀態(tài)集合,Σ是二元組(i,r)集合,i是時間點(時刻),r是定義在Ω上的變量.簡稱時間聚集變量為時間變量.時間變量的賦值?(t,ξ)∈Σ,ξ∈Ω,t表示變量取ξ狀態(tài)的時刻.假設(shè)時間變量在獲得新證據(jù)之前保持原有的狀態(tài)不變.設(shè)Ω={false,true},時間變量X={(0,false),(3,true)},則X在(0,3]時間區(qū)間內(nèi)取值為false,從時刻3開始X的狀態(tài)為true,且一直保持該狀態(tài).定義2時間因果關(guān)系是時間節(jié)點X(ΣX,ΩX)到Y(jié)(ΣY,ΩY)的關(guān)系,X(ΣX,ΩX)是原因節(jié)點,Y(ΣY,ΩY)是結(jié)果節(jié)點,記為X<ΓXY>Y,其中ΓXY是因果關(guān)系發(fā)生的遲滯時間,ΓXY≥0.圖形化表示為XΓXY→Y.X?→ΓXYY.時間貝葉斯網(wǎng)絡(luò)是一個有向圖,其中節(jié)點是時間變量,弧是時間因果關(guān)系.定義3時間貝葉斯網(wǎng)絡(luò)(TemporalBayesianNetwork,TBN)是二元組(V,E),其中V是時間變量集合,E是時間因果關(guān)系集合,對E中的每一個從X到Y(jié)的時間因果關(guān)系,都有X∈V、Y∈V.TBN拓?fù)浣Y(jié)構(gòu)與傳統(tǒng)BN相比,弧的方向與時間流逝的方向一致,弧上添加了遲滯時間,且TBN中允許存在有向循環(huán).BN是TBN的特例,若TBN中不存在有向循環(huán),且所有弧的遲滯時間都等于零,則TBN就是傳統(tǒng)的BN.圖1為一個簡單的時間貝葉斯網(wǎng)絡(luò)示例.模型I為某軟件系統(tǒng)的開發(fā)過程,該系統(tǒng)包含兩個模塊:模塊1和一個COTS部件.弧上標(biāo)注的遲滯時間以工作日為單位,表示的是弧的扇出節(jié)點所對應(yīng)的工作持續(xù)時間.將圖中各節(jié)點分別用X1～X5表示,得到圖1中模型Ⅱ.模型中各節(jié)點均取二值(開始1,未開始0),各節(jié)點的條件概率均為Ρ(Xi=1|Ρa(Xi))={0.8Ρa(Xi)=ˉ10Ρa(Xi)≠ˉ1P(Xi=1|Pa(Xi))={0.80Pa(Xi)=1ˉPa(Xi)≠1ˉ2鏈中弧的方向一致,環(huán)的周期TBN中,由節(jié)點以及節(jié)點間的弧相間組成的序列,且節(jié)點、弧在序列中不重復(fù)出現(xiàn),稱為鏈,其中,鏈中的每條弧連接序列中弧的鄰居節(jié)點.如果鏈的每條弧都是由序列中位于弧之前的節(jié)點指向位于弧之后的節(jié)點,則稱該鏈為路.因此鏈中弧的方向不一致,而路中弧的方向一致.鏈的時間距離是指從鏈的起始節(jié)點到終止節(jié)點,所有弧的遲滯時間之和.顯然,路的時間距離不小于零.如果路的起點和終點相同,則為環(huán).因此環(huán)是一種特殊的路,環(huán)上各條弧的方向一致.環(huán)的時間距離稱為環(huán)的周期.環(huán)的合理性分析是基于對TBN中的節(jié)點在任何時刻只能具有唯一狀態(tài)值的考慮.定義4TBN中,環(huán)的周期大于零,稱該環(huán)是合理的;若TBN中不存在環(huán)或所有環(huán)均是合理的,稱該有環(huán)TBN是合理的.只有合理的時間貝葉斯網(wǎng)絡(luò)才有討論其概率推理的可能.TBN由于引入了時間以及允許循環(huán)的存在,其概率傳播與BN存在很大的差別,但仍然是以BN為基礎(chǔ)的.以下探討合理的TBN的概率推理方法.3非周期tn概率推理方法3.1節(jié)點x、y被3d-分離無環(huán)TBN(V,E)單個節(jié)點信度更新問題已知證據(jù)集合W,求T時刻節(jié)點X的后驗概率P(x|W,T).定義5(d-分離)s是TBN中的一條鏈,W為證據(jù)節(jié)點集合,稱s被Wd-分離,如果s中包含3個相鄰節(jié)點X1、X2、X3,滿足以下3種情況之一:1)X1Γ12→X2Γ23→X31)X1?→Γ12X2?→Γ23X3位于s上,X2∈W2)X1Γ21→X2Γ23→X32)X1?→Γ21X2?→Γ23X3位于s上,X2∈W3)X1Γ12→X2Γ32→X33)X1?→Γ12X2?→Γ32X3位于s上,且(Desc(X2)∪{X2})∩W=>,其中Desc(X2)是指X2的子孫節(jié)點集合.不存在任何證據(jù)節(jié)點(集合)d-分離s,則稱s是d-連通的.若時間貝葉斯網(wǎng)絡(luò)中所有節(jié)點之間的鏈路都是d-連通的,則稱該時間貝葉斯網(wǎng)絡(luò)是d-連通圖.若節(jié)點X、Y之間的所有鏈均被Wd-分離,則稱X、Y被Wd-分離,記為X∥ˉWYX∥ˉWY.無環(huán)時間貝葉斯網(wǎng)絡(luò)是有向無環(huán)圖,因此節(jié)點X、Y被Wd-分離,表明節(jié)點X、Y關(guān)于W條件獨立,因此節(jié)點X、Y中任何一個節(jié)點信度的更新不會影響到另一個.定義6節(jié)點X的d-連通圖是指所有位于以X為端點之一且d-連通的鏈上的所有節(jié)點和弧所構(gòu)成的有向圖.已知TBN′(V′,E′),構(gòu)造X節(jié)點的d-連通圖TBN″(V″,E″):1.初始化V″={X},E″=>;2.檢驗在TBN′(V′,E′)中以X為一端點的所有鏈,如果該鏈不被Wd-分離,則鏈上的節(jié)點→V″,鏈上的弧→E″;3.若?Y∈V″,Y是TBN″=(V″,E″)中孤立節(jié)點,從V″中剔除Y,V″=V″/{Y};4.刪除V″、E″中的冗余元素;5.更新V″中各節(jié)點的條件概率表.定義7證據(jù)節(jié)點集合W的T時刻可達(dá)圖是指從證據(jù)節(jié)點出發(fā),T時間內(nèi)證據(jù)能夠傳播到的所有節(jié)點以及經(jīng)過的弧構(gòu)成的有向圖.已知TBN″=(V″,E″),構(gòu)造節(jié)點集合W′的T時刻可達(dá)圖TBNue087=(Vue087,Eue087):1.初始化Vue087=W′,Eue087為W′集合中內(nèi)部節(jié)點之間的弧.2.對W′中的每一個節(jié)點Y,檢驗在TBN″=(V″,E″)中以Y為一端點的所有鏈,如果該鏈的周期不大于T,則鏈上的節(jié)點→Vue087,鏈上的弧→Eue087.3.刪除Vue087、Eue087中的冗余元素.4.對Vue087中的每個節(jié)點,若其父節(jié)點集合發(fā)生變化,由TBN″=(V″,E″)獲取條件概率表.基于模型化簡的單個節(jié)點信度更新算法的基本思想:通過將模型化簡,將TBN的單個節(jié)點信度更新轉(zhuǎn)化為傳統(tǒng)BN的概率推理問題,然后采用現(xiàn)有的概率推理算法更新被詢問節(jié)點的信度.模型化簡包括排除不受證據(jù)節(jié)點影響的節(jié)點、不影響被詢問節(jié)點的節(jié)點以及T時刻內(nèi)證據(jù)不能到達(dá)的節(jié)點,化簡后的TBN模型中所有節(jié)點都是受證據(jù)節(jié)點影響并影響被詢問節(jié)點且T時刻內(nèi)可得到更新的.其算法如下:1.構(gòu)造證據(jù)節(jié)點集合的d-連通圖TBN′(V′,E′),如果X?V′,則停止,否則2.由TBN′構(gòu)造X節(jié)點的d-連通圖TBN″=(V″,E″),如果W∩V″=>,則停止,否則令W′=W∩V″3.由TBN″構(gòu)造證據(jù)節(jié)點集合W′的T時刻可達(dá)圖TBNue087=(Vue087,Eue087),如果X?Vue087,則停止,否則4.將TBNue087轉(zhuǎn)化成一般BN5.計算X節(jié)點的后驗概率.算法的流程圖如圖2所示.BN是無環(huán)的遲滯時間均為零的TBN.因此通過令TBNue087中所有弧的遲滯時間為零,從而將時間因果關(guān)系轉(zhuǎn)化為因果關(guān)系;同時將時間節(jié)點轉(zhuǎn)化為一般節(jié)點,TBNue087就轉(zhuǎn)化為BN.然后可采用現(xiàn)有的各種BN概率推理方法獲得被詢問節(jié)點的后驗概率,即為T時刻被詢問節(jié)點的后驗概率.3.2構(gòu)造原時間貝葉斯網(wǎng)絡(luò)的,以圖1中的例子說明基于模型化簡的信度更新算法的應(yīng)用.設(shè)當(dāng)前已知模塊1開始測試,即證據(jù)為W={X3=1}.令T=-8,求T時刻,節(jié)點X1的后驗概率P(X1=1|X3=1,T).由于P(X1=1|X3=1,T)=α·P(X1,X3=1,T),其中α為歸一化算子,因此現(xiàn)在計算P(X1,X3=1,T).首先構(gòu)造原時間貝葉斯網(wǎng)絡(luò)的d-連通圖,得到TBN′,X1在TBN′中;接著由TBN′構(gòu)造節(jié)點X1的d-連通圖TBN″,證據(jù)節(jié)點X3在TBN″中;然后由TBN″構(gòu)造X3的T時刻可達(dá)圖TBNue087.本例中,TBN′=TBN″=TBNue087(見圖3),進(jìn)一步轉(zhuǎn)化成一般貝葉斯網(wǎng)絡(luò).接下來可以采用BN眾多概率推理方法的任何一種進(jìn)行模型的求解.如采用桶隊消除算法,設(shè)節(jié)點序為d=X1,X2,X3,X4,X5,則Ρ(X1?X3=1)=∑X2?X3=1Ρ(X1)Ρ(X2|X1)Ρ(X3|X2)=Ρ(X1)∑X2Ρ(X2|X1)∑X3=1Ρ(X3|X2)采用桶隊算法構(gòu)造桶λX3(X2)=∑X3=1Ρ(X3|X2)?λX2(X1)=∑X2=Ρ(X2|X1)λX3(X2)則P(X1,X3=1)=P(X1)λX2(X1)得到P(X1=1│X3=1,-8)=1即T=-8時,模塊1詳細(xì)設(shè)計已經(jīng)開始.4概率推理方法：n4.1節(jié)點概率狀態(tài)更新時間貝葉斯網(wǎng)絡(luò)TBN(V,E),已知證據(jù)集合W,求T時刻網(wǎng)絡(luò)中各個節(jié)點的概率狀態(tài)P(x|W,T).T≥0則意味著預(yù)測未來時刻被詢問節(jié)點的概率狀態(tài);T<0則已知當(dāng)前證據(jù)節(jié)點狀態(tài),擬合過去時刻被詢問節(jié)點的概率狀態(tài).定義8時間貝葉斯網(wǎng)絡(luò)中X的父節(jié)點和子節(jié)點稱為X的一步可達(dá)集.記作R(X)={(Y,tX+τXY)|Y∈Pa(X)∨Y∈Desc(X)}稱tX+τXY為節(jié)點Y的信度更新時間,其中Desc(X)是X的子孫節(jié)點,tX是時間節(jié)點X的概率狀態(tài)發(fā)生時刻,而τXY為τYX={ΓYX?ifYΓYX→X-ΓYX?ifYΓYX→X(1)時間貝葉斯網(wǎng)絡(luò)中當(dāng)前所有證據(jù)節(jié)點的一步可達(dá)集的集合為該時間貝葉斯網(wǎng)絡(luò)的一步可達(dá)集.在算法過程中,為避免陷入死循環(huán),本文并不采用一步可達(dá)集定義構(gòu)造節(jié)點X的一步可達(dá)集,而是記錄更新X的節(jié)點集合為B(X),其中的節(jié)點不再進(jìn)入X的一步可達(dá)集中,即R(X)={(Y,tX+τXY)|(Y∈Pa(X)∨Y∈Desc(X))∧Y?B(X)}其中,更新X的節(jié)點是指導(dǎo)致X信度更新的證據(jù)節(jié)點,或者說X曾是該節(jié)點的一步可達(dá)節(jié)點,且該節(jié)點的信度傳播到了X.時間貝葉斯網(wǎng)絡(luò)中的同一個節(jié)點在概率傳播過程中可能會多次被更新信度,設(shè)節(jié)點X已有賦值X(t(0)x,x(0)),又產(chǎn)生了另一信度更新X(t(1)X,x(1)),則定義操作f(t(0)X,t(1)X,T)以確定此次X的更新時刻tX=f(t(0)X?t(1)X?Τ)={ift(0)X≥Τ∧t(1)X≥Τ?thentX=min(t(j)X?j=1?2)ift(0)X＜Τ∧t(1)X＜Τ?thentX=mɑx(t(j)X?j=1?2)ift(0)X＜Τ∧t(1)X＞Τ?thentX=t(0)Xift(1)X＜Τ∧t(0)X＞Τ?thentX=t(1)X(2)因此,如果節(jié)點X兩次信度更新時間都小于詢問時刻,則取其中較大的更新時間為當(dāng)前信度更新時間;若兩次更新時間都大于詢問時刻,則取較小的更新時間;若一個更新時間大于詢問時刻,一個小于詢問時刻,取小于詢問時刻的更新時間.命題1確定時間貝葉斯網(wǎng)絡(luò)中節(jié)點概率狀態(tài)的更新時刻基于以下兩條規(guī)則:1)小于詢問時刻;2)距離詢問時刻最近.首先滿足第1條規(guī)則,若由第1條規(guī)則仍然不能確定更新時刻,則采用第2條規(guī)則.x是節(jié)點X在tX時刻的取值,記為X(tX,x).已知時間貝葉斯網(wǎng)絡(luò)TBN(V,E),證據(jù)集合為W={W1(0,w1),…,Wk(0,wk)},k≥1,求T時刻網(wǎng)絡(luò)中各個節(jié)點的概率狀態(tài),算法基本思想是從證據(jù)節(jié)點出發(fā),每一步根據(jù)當(dāng)前一步可達(dá)節(jié)點的信度更新時間,選擇下一個概率更新的節(jié)點;直至可達(dá)節(jié)點集合為空集,以此得到被詢問節(jié)點(或節(jié)點子集)的信度更新.具體算法為:1.構(gòu)造證據(jù)集合W的d-連通圖TBN′,令U=W;2.對W中的每一個節(jié)點X,構(gòu)造其一步可達(dá)節(jié)點集合R(X),令R={R(X)|X∈W};3.如果R=>,轉(zhuǎn)至7.否則;4.比較R中各一步可達(dá)節(jié)點的信度更新時間,取時間最小的節(jié)點Y*tX*+τX*Y*=min(tX+τXY)?tY*R(X*)=R(X*)/{(Y*,tX*+τX*Y*)};5.如果?Y*(t(0)Y*,у*(0))∈U且f(t(0)Y*?tY*?Τ)=t(0)Y*,則轉(zhuǎn)至3.否則轉(zhuǎn)至6;6.進(jìn)行信度更新,得到Y(jié)*(tY*,у*),其中tY*=tX*+τXY?U=U/Y*(t(0)Y*?у*(0))?Y*(?tY*??у*)→U.構(gòu)造Y*的一步可達(dá)集合,R(Y*)={(Z,tY*+τYZ}.轉(zhuǎn)至3;7.{X(tX,x)|X∈U∧tX≤T}中的節(jié)點概率狀態(tài)為T時刻該節(jié)點的概率狀態(tài).4.2r.4.2信度檢驗仍然以圖1的例子說明方法的應(yīng)用.當(dāng)前模塊1測試、COTS部件集成兩項工作剛開始進(jìn)行,即W={X3(0,(1,1)),X4(0,(1.1))},求T=3時刻,該軟件項目各項工作的狀態(tài),即時間貝葉斯網(wǎng)絡(luò)各節(jié)點的狀態(tài).W={X3(0,(1,1)),X4(0,(1.1))},U=W;R(X3)={(X2,-7),(X5,3)},R(X4)={(X5,2)}R={R(X3),R(X4)}由U更新X2,得X2(-7,(1,P(x2)=1)).則此時X3、X2的一步可達(dá)集分別為:R(X3)={(X5,3)},R(X2)={(X1,-9)},網(wǎng)絡(luò)的一步可達(dá)集合為R={R(X3),R(X4),R(X2)},U={X3,X4,X2(-7,(1,1))};由U更新X1,得X1(-9,(1,P(X1=1)=1)).此時X2、X1的一步可達(dá)集分別為R(X2)=>,R(X1)={(X5,-7)},網(wǎng)絡(luò)的一般可達(dá)集合為R={R(X3),R(X4),R(X1)},證據(jù)集合為U={X3,X4,X2,X1(-9,(1,1))};由U更新X5,得X5(-7,(0,P(X5=0)=1)).則R(X1)=>,R(X5)={(X3,-4),(X4,-5)},R={R(X3),R(X4),R(X5)},U={X3,X4,X2,X1,X5(-7,(0,1))};由于X3(0,x3)∈U,X4(0,x4)∈U,f(0,-5,T)=0,f(0,-4,T)=0,因此不更新X3、X4的信度,R={R(X3),R(X4)}.由U更新X5,U={X3,X4,X2,X