基于代數(shù)決策圖的貝葉斯網(wǎng)絡(luò)參數(shù)簡(jiǎn)化技術(shù)?

王 瑤,孫 秦

(西北工業(yè)大學(xué)航空學(xué)院，西安 710072)

1 引言

貝葉斯網(wǎng)絡(luò)推理是在一個(gè)不確定性環(huán)境和不完全信息下進(jìn)行決策支持和因果發(fā)現(xiàn)的工具．由于有堅(jiān)實(shí)的概率論和圖論理論基礎(chǔ)，同時(shí)又可以很好地同專(zhuān)家知識(shí)進(jìn)行融合，貝葉斯網(wǎng)絡(luò)推理近年來(lái)已成為人工智能、模式識(shí)別、專(zhuān)家系統(tǒng)等領(lǐng)域的研究熱點(diǎn)[1]．

貝葉斯網(wǎng)絡(luò)推理方法可以分為兩類(lèi)：精確推理和近似推理．比較經(jīng)典的精確推理算法有變量消元算法、聯(lián)結(jié)樹(shù)算法、圖簡(jiǎn)約算法和多樹(shù)傳播算法[1,2]．近似算法有隨機(jī)抽樣、基于搜索的算法等．目前，這些算法均是用一張概率條件表來(lái)表示網(wǎng)絡(luò)中的參數(shù)進(jìn)行推理運(yùn)算的，然而，條件概率表不能捕捉到網(wǎng)絡(luò)參數(shù)呈現(xiàn)出的環(huán)境獨(dú)立特點(diǎn)[3]．代數(shù)決策圖是一種有效的數(shù)據(jù)表達(dá)形式[4]，它可以捕捉到網(wǎng)絡(luò)參數(shù)環(huán)境獨(dú)立的特點(diǎn)．因此，本文采用代數(shù)決策圖取代條件概率表來(lái)表示網(wǎng)絡(luò)參數(shù)，提出了條件概率表到代數(shù)決策圖的轉(zhuǎn)化方法，同時(shí)給出了轉(zhuǎn)化的算法．

2 貝葉斯網(wǎng)絡(luò)推理

貝葉斯網(wǎng)絡(luò)推理問(wèn)題可以歸結(jié)為，在已知證據(jù)變量和網(wǎng)絡(luò)結(jié)構(gòu)的基礎(chǔ)上，求解感興趣變量的后驗(yàn)概率問(wèn)題．?dāng)?shù)學(xué)描述如下：

對(duì)任意變量全集為N={X1,···,Xn}，聯(lián)合概率分布為Pr(X1,···,Xn)的貝葉斯網(wǎng)絡(luò)N，存在三類(lèi)變量，證據(jù)變量E=e，查詢(xún)變量Q，及其它無(wú)關(guān)變量S=N(Q∪M)；后驗(yàn)概率問(wèn)題就是求概率分布Pr(Q|E=e)．根據(jù)文獻(xiàn)[1]中的第二、三章，利用條件獨(dú)立和鏈?zhǔn)椒傻?/p>

繼而根據(jù)貝葉斯定理，計(jì)算

后驗(yàn)概率問(wèn)題可解[1,2]．上式中pai(Xi)表示貝葉斯網(wǎng)絡(luò)中任意節(jié)點(diǎn)Xi的父節(jié)點(diǎn)，P(Xi|pai(Xi))為節(jié)點(diǎn)Xi對(duì)應(yīng)的條件概率分布(簡(jiǎn)稱(chēng)CPD)．

CPD用于描述父子節(jié)點(diǎn)依賴(lài)關(guān)系，其可用一張條件概率表表示(簡(jiǎn)稱(chēng)CPT)．CPT中各行數(shù)據(jù)表示已知父節(jié)點(diǎn)狀態(tài)，子節(jié)點(diǎn)對(duì)應(yīng)狀態(tài)的發(fā)生概率．例如，圖1中節(jié)點(diǎn)Z的CPD以CPT形式給出，該CPT第1行數(shù)據(jù)含義為：當(dāng)父節(jié)點(diǎn){X=0,Y=0}時(shí)，子節(jié)點(diǎn)Z=0的概率為0.1．類(lèi)似于節(jié)點(diǎn)Z，圖1中網(wǎng)絡(luò)的其它節(jié)點(diǎn)T、X、Y和A也存在描述其與父節(jié)點(diǎn)依賴(lài)關(guān)系的CPT．根據(jù)貝葉斯網(wǎng)絡(luò)定義[1]，貝葉斯網(wǎng)絡(luò)每個(gè)節(jié)點(diǎn)均對(duì)應(yīng)唯一的CPD(類(lèi)似于圖1，CPD通常用CPT表示)，找出網(wǎng)絡(luò)證據(jù)變量集合E，并設(shè)置其等于已知變量e=E后，將所有節(jié)點(diǎn)的CPD(P(Xi|pai(Xi)))按照節(jié)點(diǎn)對(duì)應(yīng)關(guān)系進(jìn)行乘法計(jì)算，即可獲得網(wǎng)絡(luò)變量全集各狀態(tài)的概率取值Pr(Q,S,E=e)．利用貝葉斯網(wǎng)絡(luò)邊緣化操作[1]消去變量集合S，即可獲得已知E=e時(shí)變量集合Q的概率分布Pr(Q,E=e)．其中，依照節(jié)點(diǎn)對(duì)應(yīng)關(guān)系進(jìn)行乘法計(jì)算指的是，網(wǎng)絡(luò)中參數(shù)相乘必須是在節(jié)點(diǎn)狀態(tài)相同的情況下進(jìn)行，例如在圖1中，若對(duì)節(jié)點(diǎn)Z和節(jié)點(diǎn)T的CPDP(Z|Y,X)和P(T|A,Z)相乘，鑒于兩節(jié)點(diǎn)的CPD中存在公共節(jié)點(diǎn)Z，因此必須在Z狀態(tài)相同的原則下對(duì)兩節(jié)點(diǎn)CPD中數(shù)據(jù)進(jìn)行乘法運(yùn)算，因此節(jié)點(diǎn)Z的CPT第1、3、5、7行數(shù)據(jù)只能分別與節(jié)點(diǎn)T的CPT前4行數(shù)據(jù)相乘，而不能與節(jié)點(diǎn)T的CPT后4行相乘法；同時(shí)節(jié)點(diǎn)Z的CPT第2、4、6、8行數(shù)據(jù)只能分別與節(jié)點(diǎn)T的CPT后4行數(shù)據(jù)相乘，而不能與節(jié)點(diǎn)T的CPT前4行數(shù)據(jù)相乘．此外，上述邊緣化操作的實(shí)質(zhì)為通過(guò)加法運(yùn)算消去其它無(wú)關(guān)變量集合S，邊緣化操作具體步驟為：對(duì)于通過(guò)乘法運(yùn)算獲得的概率分布Pr(Q,S,E=e)，當(dāng)Q=q時(shí)，找出S各狀態(tài)的對(duì)應(yīng)概率取值并進(jìn)行累加得到Pr(Q=q,E=e)；類(lèi)似的，對(duì)Q所有狀態(tài)，進(jìn)行如上方式的累加以獲得累加值；各累加值即構(gòu)成概率分布Pr(Q,E=e)．例如已知圖1中{X=1,Y=1}為證據(jù)變量，通過(guò)對(duì)各節(jié)點(diǎn)的CPT進(jìn)行相乘可獲得條件概率分布Pr(Z,A,T|X=1,Y=1)，該條件概率分布亦可用CPT表示，具體形式與圖1中節(jié)點(diǎn)T的CPT形式完全相同．若其它無(wú)關(guān)變量集合S={A,Z}，那么將類(lèi)似節(jié)點(diǎn)T的CPT中第1、3、5和7行概率值相加即可獲得Pr(T=0,X=1,Y=1)；將CPT中第2、4、6和8行概率值相加即可獲得Pr(T=1,X=1,Y=1)；概率值Pr(T=0,X=1,Y=1)和Pr(T=1,X=1,Y=1)構(gòu)成最終結(jié)果Pr(T,X=1,Y=1)．

(1)和(2)是貝葉斯網(wǎng)絡(luò)所有精確推理算法的依據(jù)[1]，其算法核心為CPD的存儲(chǔ)以及與CPD之間的乘法、加法運(yùn)算．

圖1:貝葉斯網(wǎng)絡(luò)示意圖

3 條件概率分布的表示

3.1 環(huán)境獨(dú)立

環(huán)境獨(dú)立是指在特定環(huán)境下才成立的條件獨(dú)立關(guān)系．一個(gè)環(huán)境(context)是一組變量及其取值的組合．張連文和郭海鵬[1]給出環(huán)境獨(dú)立概念如下：

定義1設(shè)X,Y,Z,C是4個(gè)兩兩交集為空的變量集合，C的取值是c．如果當(dāng)P(Z,Y,C=c)＞0時(shí)，P(X|Z,Y,C=c)=P(X|Z,C=c)成立，則稱(chēng)在環(huán)境C=c中，X與Y在給定Z時(shí)相互條件獨(dú)立．更進(jìn)一步，若Z為空，則稱(chēng)在環(huán)境C=c中，X與Y相互獨(dú)立．

例如圖2(a)中，有P(Z|Y,X=0)=P(Z|X=0)成立，Y與Z在環(huán)境X=0下相互獨(dú)立．

環(huán)境獨(dú)立是貝葉斯網(wǎng)絡(luò)概率參數(shù)特征的體現(xiàn)．根據(jù)參數(shù)的特點(diǎn)，貝葉斯網(wǎng)絡(luò)參數(shù)數(shù)據(jù)可以減少，故一定程度上可以提高推理效率．

3.2 條件概率表與代數(shù)決策樹(shù)

依據(jù)貝葉斯網(wǎng)絡(luò)的定義，貝葉斯網(wǎng)絡(luò)的每個(gè)節(jié)點(diǎn)X都對(duì)應(yīng)一個(gè)CPD，它存儲(chǔ)了各節(jié)點(diǎn)與其父節(jié)點(diǎn)的依賴(lài)關(guān)系．所謂依賴(lài)關(guān)系，簡(jiǎn)而言之，就是在父節(jié)點(diǎn)狀態(tài)已知情況下，子節(jié)點(diǎn)各狀態(tài)的取值概率．直觀的講，就是“窮舉各父節(jié)點(diǎn)狀態(tài)下，子節(jié)點(diǎn)取各種狀態(tài)的概率大小”．而表格很適用于狀態(tài)窮舉，故貝葉斯網(wǎng)絡(luò)各節(jié)點(diǎn)用條件概率表(CPT)的形式表達(dá)、存儲(chǔ)CPD中的上述依賴(lài)關(guān)系．但對(duì)于很多貝葉斯網(wǎng)絡(luò)，節(jié)點(diǎn)條件概率參數(shù)之間存在了大量的環(huán)境獨(dú)立情況[3]，子節(jié)點(diǎn)與父節(jié)點(diǎn)的依賴(lài)關(guān)系并不需要狀態(tài)窮舉，因此CPT的狀態(tài)窮舉存儲(chǔ)方式將因不能捕捉到網(wǎng)絡(luò)概率參數(shù)環(huán)境獨(dú)立的特點(diǎn)而會(huì)帶來(lái)冗余數(shù)據(jù)的不必要存儲(chǔ)．例如，對(duì)網(wǎng)絡(luò)任意節(jié)點(diǎn)X，其CPDP(X|pai(X))若CPT表示，則需窮舉父節(jié)點(diǎn)與子節(jié)點(diǎn)的所有狀態(tài)組合，且CPT中的條件概率數(shù)目將隨父節(jié)點(diǎn)數(shù)目呈指數(shù)級(jí)別增長(zhǎng)[1,3]，例如圖2(a)中P(Z|Y,X)對(duì)應(yīng)的條件概率表列舉了父節(jié)點(diǎn)Y，X與子節(jié)點(diǎn)Z的所有8種狀態(tài)組合及其對(duì)應(yīng)概率參數(shù)．

圖2: 同一概率分布P(Z|Y,X)的三種不同表達(dá)形式

鑒于OBDD(ordered binary decision diagram)能夠通過(guò)判斷并消除結(jié)構(gòu)中的冗余節(jié)點(diǎn)(冗余節(jié)點(diǎn)的判斷實(shí)質(zhì)為對(duì)獨(dú)立信息的判斷)而使得網(wǎng)絡(luò)節(jié)點(diǎn)信息的存儲(chǔ)達(dá)到最簡(jiǎn)單[5]，本文采用一種與OBDD類(lèi)似的代數(shù)決策圖(ADD)來(lái)取代CPT對(duì)網(wǎng)絡(luò)概率參數(shù)進(jìn)行存儲(chǔ)，并通過(guò)消除ADD冗余節(jié)點(diǎn)完成貝葉斯網(wǎng)絡(luò)各節(jié)點(diǎn)CPD的最簡(jiǎn)表達(dá)．例如，圖2(c)中概率參數(shù)用ADD存儲(chǔ)只需要存儲(chǔ)5個(gè)(注意不是3個(gè))，而不是CPT形式的8個(gè)．

下面，首先對(duì)ADD的基本概念進(jìn)行論述，為后續(xù)最簡(jiǎn)ADD構(gòu)造方法的提出提供理論基礎(chǔ)．

與OBDD類(lèi)似，ADD與OBDD的非葉節(jié)點(diǎn)均為表示變量的節(jié)點(diǎn)，例如X、Y等．兩種圖形的唯一區(qū)別在于：ADD的葉節(jié)點(diǎn)為概率數(shù)據(jù)，而OBDD葉節(jié)點(diǎn)仍為表示變量節(jié)點(diǎn)．唯一的區(qū)別意味著若將ADD中概率值相同的子節(jié)點(diǎn)合并視為一個(gè)變量，則OBDD與ADD完全相同，那么OBDD的理論則完全適用于ADD．具體來(lái)講，ADD實(shí)質(zhì)上是一個(gè)僅有一個(gè)根節(jié)點(diǎn)的有向無(wú)環(huán)圖．每個(gè)非葉節(jié)點(diǎn)X為二元變量，虛線指向左孩子，表示X=0，實(shí)線指向右孩子，表示X=1．葉節(jié)點(diǎn)表示一個(gè)實(shí)數(shù)．在貝葉斯網(wǎng)絡(luò)中，ADD的葉節(jié)點(diǎn)表示概率值．

從根節(jié)點(diǎn)到一個(gè)葉節(jié)點(diǎn)稱(chēng)為ADD的一條路徑，每條路徑變量出現(xiàn)的順序必須保持一致，但不要求每個(gè)變量一定要出現(xiàn)．例如，圖2(c)的ADD的變量排列順序?yàn)閄,Y,Z，從X到0.1有{X=0,Z=0}和{X=1,Y=0,Z=1}，前一條路徑表示了圖2(a)中第1、3行數(shù)據(jù)，后一條路徑表示第6行數(shù)據(jù)．需要注意兩點(diǎn)：

1)不同的變量順序會(huì)有不同的ADD對(duì)應(yīng)；

2)相同的變量順序也可能會(huì)有不同的ADD對(duì)應(yīng)．而這些不同的ADD的“最簡(jiǎn)形式”和“完全形式”卻是一致的[5]．圖2中，與(a)對(duì)應(yīng)的(b),(c)分別為完全形式和最簡(jiǎn)形式．

用ADD表示貝葉斯網(wǎng)絡(luò)中的概率參數(shù)存在以下兩個(gè)意義．首先，ADD能更加簡(jiǎn)潔的表示貝葉斯網(wǎng)絡(luò)中的因子．其最壞的情況下也不會(huì)多于CPT表的概率數(shù)量．其次，ADD有一套高效的運(yùn)算規(guī)則[3]，包括乘法和加法．

4 算法實(shí)現(xiàn)與案例分析

4.1 CPT到ADD算法實(shí)現(xiàn)與驗(yàn)證

對(duì)于一般給定的貝葉斯網(wǎng)絡(luò)，其條件概率分布一般均是以條件概率表的形式給出．那么，如何將條件概率表轉(zhuǎn)化為最簡(jiǎn)ADD，成為利用ADD進(jìn)行貝葉斯網(wǎng)絡(luò)推理的前提和關(guān)鍵．

從第2節(jié)圖2可知，一個(gè)直接的做法是首先為CPT構(gòu)造一個(gè)完全ADD，然后應(yīng)用一定的規(guī)則去掉冗余節(jié)點(diǎn)，直到變?yōu)樽詈?jiǎn)形式．借用Meinel和Thorsten[5]對(duì)OBDD冗余節(jié)點(diǎn)的定義，下面定理成立．

定理1如果ADD存在以下兩種情況，則ADD存在冗余節(jié)點(diǎn)：

1)若存在某個(gè)節(jié)點(diǎn)，該節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)(左孩子和右孩子)是一樣的．表現(xiàn)在ADD中為，該點(diǎn)的實(shí)線邊以及虛線邊都指向同一個(gè)子節(jié)點(diǎn)，則該節(jié)點(diǎn)是重復(fù)的，稱(chēng)為第一類(lèi)冗余節(jié)點(diǎn)；

2)若ADD中存在兩個(gè)節(jié)點(diǎn)，該兩個(gè)節(jié)點(diǎn)均代表變量X，且左孩子均指向同一個(gè)節(jié)點(diǎn)，右孩子均指向同一個(gè)節(jié)點(diǎn)，則這兩個(gè)節(jié)點(diǎn)中有一個(gè)是重復(fù)的，稱(chēng)為第二類(lèi)冗余節(jié)點(diǎn)．

圖2(b)中的完全ADD表面并不符合定理1中的兩種冗余情況，然而，需要注意的是，該完全ADD中若干概率值是相等的，需要對(duì)相同概率值節(jié)點(diǎn)進(jìn)行合并，見(jiàn)圖3(a)．顯然，圖3(a)存在上述兩種冗余情況．合并了ADD葉節(jié)點(diǎn)后，其結(jié)構(gòu)與OBDD完全相同，因此OBDD通過(guò)刪除冗余節(jié)點(diǎn)獲得最簡(jiǎn)結(jié)構(gòu)的方法完全適用于ADD，保證了CPT等價(jià)最簡(jiǎn)ADD構(gòu)造方法的正確性．

現(xiàn)結(jié)合OBDD簡(jiǎn)化理論[5]，總結(jié)從完全ADD得到最簡(jiǎn)ADD的步驟如下：

步驟1指定構(gòu)造ADD的變量順序，并構(gòu)造完全ADD；

步驟2在完全ADD的基礎(chǔ)上，去掉概率值相同的葉節(jié)點(diǎn)，將被去掉的葉節(jié)點(diǎn)的父節(jié)點(diǎn)重新指向保留下的具有相同概率值的唯一葉節(jié)點(diǎn)；

步驟3根據(jù)定理1，自下而上分析是否存在冗余節(jié)點(diǎn)；

步驟4自下而上逐步去掉冗余節(jié)點(diǎn)，直到根節(jié)點(diǎn)結(jié)束．

由Meinel和Thorsten[5]可知，按照如下方法自下而上逐層去掉冗余節(jié)點(diǎn)可以保證得到最簡(jiǎn)ADD．對(duì)于ADD中同層節(jié)點(diǎn)，刪去兩類(lèi)節(jié)點(diǎn)的方法如下：

首先，刪去第一類(lèi)冗余節(jié)點(diǎn)，將該節(jié)點(diǎn)的父節(jié)點(diǎn)直接指向該節(jié)點(diǎn)的子節(jié)點(diǎn)；其次，刪去第二類(lèi)冗余節(jié)點(diǎn)，即去掉兩個(gè)重復(fù)節(jié)點(diǎn)中的任意一個(gè)，將被刪去節(jié)點(diǎn)的父節(jié)點(diǎn)指向被保留的另一重復(fù)節(jié)點(diǎn)，被刪去節(jié)點(diǎn)的指向其左右孩子的兩條邊一同刪去．

依照以上化簡(jiǎn)規(guī)則，圖3給出了圖2(b)中完全ADD的化簡(jiǎn)步驟．結(jié)果與圖2(c)完全一致，驗(yàn)證了算法的正確性．綜上，算法CPT-ADD給出了從任意CPT到其最簡(jiǎn)ADD轉(zhuǎn)化的偽代碼．

圖3:ADD的化簡(jiǎn)步驟示意圖

算法CPT-ADD(CPT,π,n)第5行用以判斷第i個(gè)和第j個(gè)葉節(jié)點(diǎn)所表示的概率參數(shù)是否相等；第12行var(v)的含義是節(jié)點(diǎn)v表示的節(jié)點(diǎn)變量；第15行判斷節(jié)點(diǎn)v的左右孩子節(jié)點(diǎn)是否為一個(gè)；以上分析與算法設(shè)計(jì)均是基于二元變量而言的．對(duì)多元變量的貝葉斯網(wǎng)絡(luò)，通常會(huì)將多元變量轉(zhuǎn)化為等價(jià)二元變量進(jìn)行處理[6]，因而將多態(tài)貝葉斯網(wǎng)絡(luò)轉(zhuǎn)化為等價(jià)二態(tài)網(wǎng)絡(luò)后，其相應(yīng)的條件概率分布也可按上述方法用ADD表示．

算法CPT ADD(CPT,π,n)輸入：CPT:一個(gè)條件概率表n:CPT包含的變量數(shù)目π:CPT中n個(gè)變量的某種排序,π={X1,···,Xn}輸出：最簡(jiǎn)ADD 1：依照順序π，構(gòu)造CPT對(duì)應(yīng)的完全ADD 2:numOfleafNode=exp(n)

由上述構(gòu)造步驟和偽代碼可看出，本文提出的ADD構(gòu)造方法并沒(méi)有對(duì)CPT的參數(shù)取值進(jìn)行限制，因此，該構(gòu)造方法為二態(tài)貝葉斯網(wǎng)絡(luò)一般情形下的代數(shù)決策樹(shù)構(gòu)造方法．但需強(qiáng)調(diào)的是，首先，如2.2節(jié)所述，若CPT本身不存在環(huán)境獨(dú)立情況，ADD概率參數(shù)存儲(chǔ)量與CPT相同，并不能有效改善CPT存儲(chǔ)過(guò)多問(wèn)題．其次，實(shí)際工程應(yīng)用中存在了大量的確定性或部分確定性因果邏輯關(guān)系[7,8]，例如“與”、“或”、“表決”、“功能觸發(fā)”等．由2.1節(jié)對(duì)獨(dú)立情況的定義可知，確定性或部分確定性因果邏輯關(guān)系其存在了大量的“獨(dú)立情況”，例如，對(duì)于“與”邏輯，如果已知有一個(gè)父節(jié)點(diǎn)存在故障，則其它父節(jié)點(diǎn)狀態(tài)與子節(jié)點(diǎn)狀態(tài)就無(wú)關(guān)．因而貝葉斯網(wǎng)絡(luò)作為一種因果邏輯關(guān)系的表達(dá)，其若用ADD存儲(chǔ)確定性或部分確定性邏輯的概率參數(shù)，相對(duì)于CPT存儲(chǔ)法，ADD方式必能大量降低存儲(chǔ)量．因此，本文ADD方法可對(duì)任意CPT進(jìn)行等價(jià)表達(dá)，雖并不意味著可減少任意CPT的概率參數(shù)量，但仍在工程實(shí)踐中具有重要的應(yīng)用價(jià)值．

4.2 案例分析與驗(yàn)證

圖4是某型飛機(jī)起落架故障樹(shù)[8]及其等價(jià)的貝葉斯網(wǎng)絡(luò)，該等價(jià)貝葉斯網(wǎng)絡(luò)根據(jù)文獻(xiàn)[9-11]提出的故障樹(shù)到貝葉斯網(wǎng)絡(luò)的映射方法得來(lái)．其中A3節(jié)點(diǎn)對(duì)應(yīng)的條件概率分布如果用CPT表示，則需要用exp(7)個(gè)參數(shù)，見(jiàn)表1，而如果用ADD表示，則只需要2×7=14個(gè)參數(shù)，見(jiàn)圖5．類(lèi)似地，對(duì)于與門(mén)節(jié)點(diǎn)A4，CPT表示方法需用exp(3)個(gè)參數(shù)，而用ADD表示方法需用2×3=6個(gè)參數(shù)．

圖4:某型飛機(jī)主起落架系統(tǒng)模型

表1: 節(jié)點(diǎn)A3的條件概率表

圖5: 用ADD表示 P(A3|X1,X2,···,X6)

用ADD取代CPT不僅可以減少數(shù)據(jù)存儲(chǔ)量，且可進(jìn)一步降低運(yùn)算量．現(xiàn)以求解系統(tǒng)可靠度為例來(lái)說(shuō)明時(shí)間復(fù)雜度降低原理．對(duì)于由故障樹(shù)轉(zhuǎn)化來(lái)的貝葉斯網(wǎng)絡(luò)，系統(tǒng)可靠性等價(jià)于在貝葉斯網(wǎng)絡(luò)中求解概率Pr(T=0)[12-14]．現(xiàn)在采用經(jīng)典變量消元算法求解該概率值，數(shù)學(xué)表達(dá)式如下

上述運(yùn)算過(guò)程中，乘積P(A3|X1,X2,···,X6)P(X6)(節(jié)點(diǎn)A3與節(jié)點(diǎn)X6的條件概率分布的乘積)的計(jì)算最耗時(shí)．若用節(jié)點(diǎn)A3與節(jié)點(diǎn)X6對(duì)應(yīng)的CPTs相乘，運(yùn)算次數(shù)為exp(7)=128次；如果用兩節(jié)點(diǎn)對(duì)應(yīng)的ADDs相乘，計(jì)算次數(shù)為2×7=14次，文獻(xiàn)[1,4]分別對(duì)CPTs與ADDs的運(yùn)算法則進(jìn)行了深入研究．

綜上，利用ADD取代CPT來(lái)表示節(jié)點(diǎn)的CPD，可以大大提高由故障樹(shù)轉(zhuǎn)化而來(lái)的貝葉斯網(wǎng)絡(luò)的推理效率，復(fù)雜度甚至可從指數(shù)級(jí)降到線性級(jí)：對(duì)于有n個(gè)基本事件的與/或門(mén)，采用CPT的存儲(chǔ)方式，其時(shí)間和空間復(fù)雜度均為exp(n+1)；采用ADD存儲(chǔ)方式，其時(shí)間和空間復(fù)雜度均為2(n+1)．對(duì)上述結(jié)論進(jìn)一步推廣：對(duì)于任何貝葉斯網(wǎng)絡(luò)，如果其網(wǎng)絡(luò)參數(shù)具有環(huán)境獨(dú)立特點(diǎn)，應(yīng)用ADD表示方式取代傳統(tǒng)的CPT表示方式可減少概率參數(shù)的存儲(chǔ)，從而進(jìn)一步減少參與推理計(jì)算量，提高計(jì)算效率．

5 結(jié)論

本文通過(guò)對(duì)貝葉斯網(wǎng)絡(luò)基本推理過(guò)程的研究，針對(duì)CPT不能捕捉網(wǎng)絡(luò)參數(shù)環(huán)境獨(dú)立的缺陷，提出了用ADD替代CPT來(lái)表示網(wǎng)絡(luò)參數(shù)的方法，并給出了CPT到ADD的轉(zhuǎn)化方法以及所需偽代碼，保證了計(jì)算機(jī)編程實(shí)現(xiàn)的可行性．理論分析說(shuō)明：利用ADD數(shù)據(jù)結(jié)構(gòu)可減少網(wǎng)絡(luò)參數(shù)存儲(chǔ)量，降低網(wǎng)絡(luò)推理復(fù)雜度，在貝葉斯網(wǎng)絡(luò)推理算法研究方面具有重要意義．

參考文獻(xiàn)：

[1]張連文，郭海鵬.貝葉斯網(wǎng)引論[M].北京：科學(xué)出版社，2006:30-53 Zhang L W,Guo H P.An Introduction to Bayesian Networks[M].Beijing:Science Press,2006:30-53

[2]史志富，張安.貝葉斯網(wǎng)絡(luò)理論及其在軍事系統(tǒng)中的應(yīng)用[M].北京：國(guó)防工業(yè)出版社，2012:78-104 Shi Z F,Zhang A.Theory of Bayesian Network and its Application in Military System[M].Beijing:National Defense Industry Press,2012:78-104

[3]Boutilier C,Friedman N,Goldszmidt M,et al.Context-specific independence in Bayesian networks[C]//Proceedings of the Twelfth Annual Conference on Uncertainty in Artificial Intelligence(UAI-96),San Francisco:Morgan Kaufmann Publishers Inc.,1996:115-123

[4]Bahar R I,Frohm E A,Gaona C M,et al.Algebric decision diagrams and their applications[J].Formal Methods in System Design,1997,10(2-3):171-206

[5]Meinel C,Thorsten T.Algorithm and Data Structure in VLSI Design OBDD-Foundations and Applications[M].New York:Springer-Verlag,1988:89-103

[6]Darwiche A.Modeling and Reasoning with Bayesian Networks[M].New York:Cambridge University Press,2012:53-306

[7]Kim M C.Reliability block diagram with general gates and its application to system reliability analysis[J].Annals of Nuclear Energy,2011,38(11):2456-2461

[8]鄧瓊.安全系統(tǒng)工程[M].西安：西北工業(yè)大學(xué)出版社，2009:95-97 Deng Q.Safety System Engineering[M].Xi’an:Northwest Industrial University Press,2009:95-97

[9]楊昌昊，胡小建，竺長(zhǎng)安.從故障樹(shù)到故障貝葉斯網(wǎng)映射的故障診斷方法[J].儀器儀表學(xué)報(bào)，2009,30(7):1481-1486 Yang C H,Hu X J,Zhu C A.Fault diagnosis method mapping from fault trees to fault Bayesian networks[J].Chinese Journal of Scientific Instrument,2009,30(7):1481-1486

[10]Bobbio A,Portinale L,Minichino M,et al.Improving the analysis of dependable systems by mapping fault trees into Bayesian networks[J].Reliability Engineering&System Safety,2001,71(3):249-260

[11]王廣彥，馬志軍，胡起偉.基于貝葉斯網(wǎng)絡(luò)的故障樹(shù)分析[J].系統(tǒng)工程理論與實(shí)踐，2004,24(6):78-83 Wang G Y,Ma Z J,Hu Q W.The fault tree analysis based on Bayesian networks[J].Systems Engineeringtheory&Practice,2004,24(6):78-83

[12]周忠寶，董豆豆，周經(jīng)倫.貝葉斯網(wǎng)絡(luò)在可靠性分析中的應(yīng)用[J].系統(tǒng)工程理論與實(shí)踐，2006,26(6):95-100 Zhou Z B,Dong D D,Zhou J L.Application of Bayesian networks in reliability analysis[J].Systems Engineering-theory&Practice,2006,26(6):95-100

[13]Khakzad N,Khan F,Amyotte P.Safety analysis in process facilities:comparison of fault tree and Bayesian network approaches[J].Reliability Engineering&System Safety,2011,96(8):925-932

[14]Portinale L,Bobbio A.Bayesian networks for dependability analysis:an application to digital control reliability[C]//Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence,San Francisco:Morgan Kaufmann Publishers Inc.,1999:551-558