瞿錫垚，劉學軍，張 禮

(1.南京航空航天大學 計算機科學與技術學院，江蘇 南京 211106；2.南京林業(yè)大學 信息科學技術學院，江蘇 南京 210037)

0 引 言

貝葉斯網絡[1-3]是一種基于貝葉斯定理的概率圖模型，可表示為BN=<,P>。網絡結構由表示，是一個有向無環(huán)圖，其中V是網絡節(jié)點，E是節(jié)點之間有向邊，P指代條件概率表(conditional probability table，CPT)。貝葉斯網絡同時具有概率論和圖論的理論基礎，擁有不確定知識的表示能力。概率推理(probabilistic inference)和最大后驗概率解釋(maximum a posteriori explanation)是貝葉斯網絡推理的兩個基本問題[4]。概率推理過程分為精確推理[5-7]和近似推理[8-9]兩種，分別適用于網絡復雜度低和復雜度高的場景。最大后驗概率解釋則是對建模問題的計算結果進行解釋性說明與分析。貝葉斯網絡在被提出之初，由于其需要大量的計算且被證明是NP難問題[10]，很長一段時間無法得到廣泛應用。直到計算機的出現，讓貝葉斯網絡重新得到重視，并廣泛應用于故障診斷[11-12]、神經網絡[13]以及作戰(zhàn)重心評估[14]等問題。

目前對于貝葉斯網絡的應用中，大多是在給定網絡結構和條件概率表之后，根據證據節(jié)點計算其他節(jié)點的概率值。而互聯(lián)網時代帶來了數據量的劇增，導致基于貝葉斯網絡的系統(tǒng)決策問題復雜度提升，即貝葉斯網絡結構中節(jié)點數和有效邊數增加。在條件概率表的構造過程中，增加一個節(jié)點會帶來兩種新的狀態(tài)，即該節(jié)點發(fā)生或不發(fā)生，而將這兩種新狀態(tài)加入到原始網絡結構中時，構造條件概率表的工作量將面臨指數級的增加，這在一定程度上限制了貝葉斯網絡的應用范圍。而在實際應用中，貝葉斯網絡節(jié)點之間并非都是完全不一致的，一些節(jié)點之間具有較高的相似性。

針對網絡節(jié)點增加帶來的問題以及節(jié)點之間相似的應用現實，文中提出并實現了一種增加先驗知識庫的貝葉斯網絡推理模型。根據建模問題相關專家給出的節(jié)點類別，以及類別之間的條件概率，建立先驗知識庫，自動生成貝葉斯網絡的條件概率表，使用聯(lián)結樹精確推理算法[15]完成貝葉斯網絡的概率推理。

1 先驗知識庫

圖1展示了一個實例圖，對于多入度節(jié)點D，條件概率公式如下：

(1)

對Pr(A,B,C,D)使用乘法公式展開有：

Pr(A,B,C,D)=Pr(A|B,C,D)*Pr(B|C,D)*Pr(C|D)*Pr(D)

(2)

其中，Pr(C|D)和Pr(D)均可以根據其類型信息從知識庫中直接讀取概率值，對于Pr(A|B,C,D)和Pr(B|C,D)，根據局部馬爾可夫性質(local Markov property),條件概率只依賴于自己的直接父節(jié)點和直接子節(jié)點，因此：

Pr(A|B,C,D)=Pr(A|B,D)

(3)

Pr(B|C,D)=Pr(B|D)

(4)

式4已化簡為可以直接從知識庫中讀取概率值的結果，對于式3，可以由條件概率Pr(A|B)拆分得到：

Pr(A|B)=Pr(A|B,D=F)+Pr(A|B,D=T)

(5)

根據式2～5，Pr(A,B,C,D)可化為：

Pr(A,B,C,D)=Pr(A|B,D)*Pr(B|D)*Pr(C|D)*Pr(D)

(6)

對式1中分母采用相同的化簡方式，可得：

Pr(A,B,C)=Pr(A|B)*Pr(B|C)*Pr(C)

(7)

最終式1化為：

Pr(D|A,B,C)=

(8)

圖1 條件概率表產生實例

根據上述推理方式，可以自動計算貝葉斯網絡中所有節(jié)點的條件概率表，減少數據量增加帶來的巨大工作量，讓使用者能夠將任務時間主要集中于貝葉斯網絡的最大后驗概率解釋。

2 貝葉斯網絡推理

確定貝葉斯網絡結構和條件概率表之后，文中使用聯(lián)結樹算法對網絡進行精確推理。聯(lián)結樹算法是目前貝葉斯網絡精確推理任務中應用最廣泛的算法，可以推理任何網絡(單連通或者多連通)，整個算法流程如圖2所示。

圖2 聯(lián)結樹算法推理過程

子網絡的提取過程是為了減少運算量，在給定證據之后，可以刪除與證據無關的節(jié)點，即證據的祖先節(jié)點中不包含的點。在貝葉斯網絡中依次用無向邊連接每兩個具有共同子節(jié)點的節(jié)點，然后去除所有貝葉斯網絡中有向邊的方向便得到貝葉斯網絡的道德圖。之后使用Kjaerulff算法對道德圖進行三角剖分，該算法具體過程如下：

算法1：Kjaerulff算法。

輸入：貝葉斯網絡道德圖；

輸出：原道德圖中所有完全子圖。

步驟1：復制原貝葉斯網絡BN到BN*，在BN*中選擇具有最小權重的節(jié)點V，權重定義為與該點直接相連的邊數，若有多個節(jié)點權重相同，則選擇需要增加邊數最小的節(jié)點。

步驟2：在BN*中依次連接與節(jié)點V直接相連的節(jié)點，同時在BN中做同樣的連接，得到一個含有V的完全子圖。

步驟3：在BN*中刪除節(jié)點V以及與其相連接的邊。

步驟4：重復以上步驟，直到BN*中沒有節(jié)點為止。

經過三角剖分得到的每一個完全子圖即為一個clique。每一個clique均可看作是由貝葉斯網絡中一組節(jié)點組成的一棵樹，兩個clique中關于貝葉斯網絡節(jié)點的交集為一個分割集。分割集是連接clique的關鍵，將所有的分割集插入clique之間可組建一個聯(lián)結樹。標記已確定的clique為Ci，SCiCj表示Ci與Cj的分割集，S表示分割集集合，其算法具體過程如下：

算法2：建立clique聯(lián)結樹算法。

輸入：clique集合與分割集集合；

輸出：clique聯(lián)結樹。

步驟1：在S中選擇一個具有最大質量的分割集SCiCj(質量的定義是指分割集中元素的個數)。

步驟2：若Ci和Cj屬于兩棵不同的樹，則將SCiCj插入Ci和Cj中，若屬于同一棵樹則重新選擇分割集，SCiCj的插入把兩棵樹合并為一棵樹。

步驟3：重復以上步驟直到所有分割集均被插入。

建立好聯(lián)結樹之后是消息的傳遞，文中使用計算速度快的Hugin消息傳遞算法[16]。消息傳遞是為了讓聯(lián)結樹達到全局一致，在該狀態(tài)下，一個clique的勢函數(用φ表示)即為該clique中所有節(jié)點與證據節(jié)點Ve的聯(lián)合概率。對于貝葉斯網絡中任一節(jié)點V，找到包含該節(jié)點的clique，則該節(jié)點在給定證據下的后驗概率為：

(9)

Hugin算法的具體過程如下：

算法3：Hugin算法。

輸入：clique聯(lián)結樹，證據節(jié)點Ve以及條件概率表；

輸出：貝葉斯網絡中所有節(jié)點對于證據節(jié)點的后驗概率。

步驟1：初始化算法參數。對每個clique和分割集的勢函數用1進行初始化，對任意一個節(jié)點V，選擇一個包含FV(由節(jié)點V和它父親節(jié)點構成的節(jié)點集)的clique節(jié)點C，更新C的勢函數φC=φC×P(V|Vpa)。其中Vpa表示節(jié)點V的父節(jié)點。

步驟2：設置證據。選擇一個包含證據的clique節(jié)點C，對其勢函數進行更新：φC=φC×P(V=False)。

步驟3：消息全局傳遞。這一步主要包含相鄰clique節(jié)點之間的單一信息傳遞，證據收集COLLECT_EVIDENCE(C)和證據擴散DISTRIBUTE_EVIDENCE(C)三個過程。式10是單一信息傳中的投影過程，式11是吸收過程。

(10)

(11)

COLLECT_EVIDENCE(C)過程首先選擇一個C做標記，對C沒做標記的鄰近clique遞歸調用過程COLLECT_EVIDENCE，傳遞信息從C到調用過程COLLECT_EVIDENCE的clique。之后是DISTRIBUTE_EVIDENCE(C)過程，同樣是選擇一個C做標記，傳遞信息從C到每一個沒做標記的鄰近clique，對C沒做標記的鄰近clique遞歸調用過程DISTRIBUTE_EVIDENCE。

步驟4：經過以上步驟會得到全局一致的聯(lián)結樹，使用式9即可計算貝葉斯網絡節(jié)點在證據節(jié)點下的后驗概率。

3 實例驗證

這部分將使用一個簡單的例子來描述增加先驗知識庫的貝葉斯推理模型的整個處理流程。假設知識庫中有三個類分別為a、b、c，圖3展示了三個類型各自的先驗概率以及它們之間的條件概率。

沒有起始節(jié)點的箭頭表示指向節(jié)點的先驗概率，例如a類節(jié)點的先驗概率為Pr(a=F)=0.5。有起始節(jié)點的箭頭擁有兩個概率值，分別代表起始節(jié)點兩種不同狀態(tài)，例如a類節(jié)點指向b類節(jié)點的箭頭，表示在條件b下，a發(fā)生的概率，概率值為Pr(a=F|b=F)=0.6，Pr(a=F|b=T)=0.5。

在圖3所代表的先驗知識庫下，文中建立一個簡單的貝葉斯網絡，如圖4所示。

圖3 三個類的條件概率表

圖4 實例貝葉斯網絡結構和條件概率表

a類節(jié)點有p1,p5，b類節(jié)點有p2,p6，c類節(jié)點有p3,p4,p7。設置節(jié)點p6為證據節(jié)點，根據第1節(jié)中的推理方法可自動計算出各節(jié)點的條件概率表，圖4中展示了其具體值。表1展示了貝葉斯網絡的最終推理結果。

表1 各節(jié)點在給定證據下的后驗概率

對于證據節(jié)點p6，節(jié)點p7不在其祖先節(jié)點中，所以表1中節(jié)點p7的后驗概率為0,節(jié)點p6作為證據，后驗概率為1。表1的計算結果中節(jié)點p4的后驗概率最大，節(jié)點p3的后驗概率最小，說明在節(jié)點p6發(fā)生的情況下，節(jié)點p4最可能發(fā)生，而節(jié)點p3最不可能發(fā)生。

4 結束語

文中提出了一種增加先驗知識庫的貝葉斯網絡推理模型。對網絡節(jié)點進行類別標記，并添加各類別的先驗概率及各類別間的條件概率，在此基礎上，利用局部馬爾可夫性完成對各網絡節(jié)點條件概率表的自動推理計算，大大減少了人工輸入條件概率表的時間消耗。對于貝葉斯網絡的推理，使用在精確推理任務中速度快、應用最為廣泛的聯(lián)結樹算法，并使用了Hugin消息傳遞，最終通過實例驗證了整個模型的處理流程。