一種基于改進的多值因果圖的近似推理

劉紹紅，王洪春

(重慶師范大學 數(shù)學科學學院，重慶　401331)

?

一種基于改進的多值因果圖的近似推理

劉紹紅，王洪春

(重慶師范大學 數(shù)學科學學院，重慶401331)

摘要：針對因果圖的精確推理是NP難的，提出尋找近似的推理算法。根據(jù)以往文獻中近似推理的原理，通過一種可能性比值，找到轉化后的連接事件概率。該近似推理保證了多值因果圖在推理過程中概率的歸一性，最后用于實例得出的結果滿足概率論知識且符合實際。

關鍵詞：因果圖；歸一性；近似推理

因果圖理論是一種基于概率論的知識表達推理方法，是張勤教授于1994年綜合吸收了如故障樹、信度網(wǎng)等其他不確定性模型的優(yōu)點而發(fā)展起來的一種不確定性知識的表達和推理模型[1]，常用于故障診斷、預防分析和關系數(shù)據(jù)的知識處理等領域。采用因果圖推理的主要目標是在假定基本事件和連接事件的概率值已知且獨立,在證據(jù)條件已知下求解指定事件的后驗概率[2]。

因果圖表現(xiàn)為一種復雜的賦值因果關系網(wǎng)絡，網(wǎng)絡由節(jié)點和有向邊構成，每個節(jié)點和每條有向邊都代表一個事件，每個節(jié)點代表一個基本事件或中間事件，每條有向邊代表一個連接事件。兩個節(jié)點之間的連接事件用概率刻畫，表示子節(jié)點導致父節(jié)點發(fā)生的概率。如圖1中：B1、B2稱為基本事件；X3稱為節(jié)點事件；P13和P23稱為連接事件。

圖1　因果圖示例

因果圖中的假定基本事件和連接事件可能有多種狀態(tài)(即事件概率是一個矩陣)，到底是哪個狀態(tài)導致了結果事件的發(fā)生，且發(fā)生的概率是多大，在實際中是很難確定的。文獻[2]提出了單賦值變量和多賦值變量的定義，文獻[3-11]提出了一些因果圖的近似推理算法，如模糊推理、迭代推理、歸一化推理等，但是多值因果圖的推理仍是NP難的。于是想到將多值因果圖轉化為單值因果圖，這樣就可以用單值因果圖的推理方法進行后續(xù)計算，但是將單值因果圖推理的4步(① 求節(jié)點事件的一階割集CSs-1； ② 求節(jié)點事件的最終割集CSs-f；③ 求節(jié)點事件的不交化割集DSCs-f；④ 計算某事件的后驗概率Pr{Vi|E})直接用于多值因果圖中，則存在2個問題：① 不嚴格滿足概率論中的歸一性；② 實際中各連接事件不完全具有互斥性。

本文在對多值因果圖進行補充定義下，利用事件各狀態(tài)發(fā)生的可能性比值，提出一種多值因果圖的近似推理算法。

1補充定義

多值因果圖不能直接用單值因果圖的推理算法主要是由于某事件各狀態(tài)發(fā)生的概率不一定滿足歸一性，故要對多值因果圖中的基本事件和連接事件進行補充定義。

根據(jù)補充定義，將多值因果圖進行了改進，對變量引入了缺省狀態(tài)，就不需要對專家給出的數(shù)據(jù)進行強制歸一化處理。

2基本假設

假設1設各基本事件變量Bi相互獨立。

假設2設各事件變量(Xi或Bi)各狀態(tài)發(fā)生的概率與其發(fā)生的可能性值成正比。

假設3設在多值因果圖中原因節(jié)點對結果節(jié)點只貢獻概率值，且每個貢獻間是簡單相加的關系。

設Vik(k=1,2,…,n)表示Vi的第k狀態(tài)，Pr{Vik}(k=1,2,…,n)表示Vi的第k狀態(tài)發(fā)生的概率,ψ(Vik)表示事件Vi的第k狀態(tài)發(fā)生的可能性值。事件Vi的各個狀態(tài)都有一個發(fā)生的可能性值，且某個事件的各個狀態(tài)是互斥的。各狀態(tài)發(fā)生的概率與其發(fā)生的可能性值成正比：

若

令

則P(Vik)(k=1,2,…,n)稱為狀態(tài)概率分配因子。

原因事件Vi的第k狀態(tài)發(fā)生時引起結果變量Vj的第l狀態(tài)發(fā)生的概率記為Pjl;ik。

把Vi的所有狀態(tài)看作一個單事件A,A=Vi1+Vi2+…+Vin,將Vj的所有狀態(tài)看作一個單事件B，B=Vj1+Vj2+…+Vjm。A引起B(yǎng)的連接事件為P,P發(fā)生的概率記為Pr{P}[7]。

由貝葉斯公式得到

(1)

3實例分析

B4=(B41)∶(0.3)

B5=(B51)∶(0.4)

B6=(B61)∶(0.2)

1) 求一階割集CSs-1

X1=P41B4∪P21X2

X2=P52B5∪P12X1

X3=P63B6∪P13X1∪P23X2

2) 求最終割集CSs-f

X1=P41B4∪P21P52B5

X2=P52B5∪P12P41B4

X3=P63B6∪P13P41B4∪P13P21P52B5∪

P23P52B5∪P23P12P41B4

最終割集展開成矩陣形式：

(2)

3) 不交化處理

X11=P11;41B41∪P11;22P22;51B51=P11;41B41+

X12=P12;22P22;51B51=0.32

X21=P21;11P11;41B41=0.21

X22=P22;51B51∪P22;11P11;41B41=P22;51B51∪

本文主要是為了尋求轉換后的連接事件概率，所以不需要對X3進行不交化處理。若用經(jīng)典的因果圖推理步驟，應求出每個事件的最終割集和對其進行不交化處理，從式(2)可以看出：對X3進行不交化處理是相當復雜的。這里，可以根據(jù)需要對事件最終割集進行不交化處理。

由多值因果圖的補充定義有：

ψ(X11)=0.328

ψ(X12)=0.32

ψ(X21)=0.21

ψ(X22)=0.418

從而

(3)

由式(1)得：

Pr{P41}=0.3

Pr{P52}=0.4

Pr{P63}=0.2

Pr{P21}=0.33×(0.7+0.1)+

0.67×(0.1+0.8)=0.867

Pr{P12}=0.51×(0.7+0.1)+

0.49×(0.1+0.8)=0.849

Pr{P23}=0.33×(0.5+0.1)+

0.67×(0.1+0.8)=0.667

Pr{P13}=0.51×(0.6+0.1)+

0.49×(0.1+0.7)=0.749

由式(3)可知基本事件各狀態(tài)發(fā)生概率滿足歸一性。

圖1的多值因果圖轉化為圖3：

圖3　轉化后的多值因果圖

根據(jù)補充定義，各事件的每個狀態(tài)發(fā)生的概率之和為1，滿足概率論的歸一性，求得轉換后的連接事件概率都在(0,1)區(qū)間上，說明了轉換的合理性。

4結束語

通過多值因果圖在補充定義下進行改進，然后向單值因果圖轉換，可以避開對多值因果圖的每個事件都求最終割集和進行不交化處理，也避開了連接事件概率的強制歸一。不用求出每個事件的最終割集，從而提高速度，且轉換后的連接事件概率是合理、有效的。

參考文獻：

[1]ZHANG Q.Probabilistic reasoning based on dynamic causality trees/diagrams[J].Reliability Engineering & Systems Safety，1994,46(94):209-220.

[2]張勤.DUCG:一種新的動態(tài)不確定因果知識的表達和推理方法(Ⅰ):離散、靜態(tài)、證據(jù)確定和有向無環(huán)圖情況[J].計算機學報，2010,33(4):625-651.

[3]樊興華，張勤，黃席樾.多值因果圖的一種推理算法[J].計算機工程與應用,2002,38(3):68-73.

[4]梁新元.復雜因果圖并行推理算法研究[J].計算機科學與探索,2014,4:483-493.

[5]王洪春，張勤.基于因果圖的一種近似推理算法[J].重慶大學學報(自然科學版),2004,27(8):96-99.

[6]王洪春，石慶喜，張勤.基于因果圖的一種推理算法[J].微電子學與計算機,2005,22(5):1-3.

[7]梁新元，吳淑皇，石慶喜.模糊因果圖的歸一化研究[J].微電子學與計算機，2006,23(11):1-3.

[8]石慶喜，梁新元，張勤.因果圖的一種快速推理方法[J].計算機工程與應用,2005,41(28):18-20.

[9]梁新元.因果圖迭代推理算法研究[J].系統(tǒng)工程與電子技術,2012,34(6):1299-1304.

[10]樊興華，仲昕，張勤，等.因果圖推理的一種新方法[J].計算機科學,2001,28 (11):48-52.

[11]梁新元.正態(tài)模糊因果圖的推理算子及歸一化算法研究[J].儀器儀表學報，2008,29(2):414-419.

(責任編輯何杰玲)

Approximate Reasoning Based on Improved Multi Valued Causal Graph

LIU Shao-hong, WANG Hong-chun

(School of Mathematical Sciences, Chongqing Normal University, Chongqing 401331, China)

Abstract:The exact inference of causal graph is NP and hard, and the inference algorithm was proposed. Through a possibility ratio, the probability of an event was found after transformation according to the principle of approximate reasoning from previous literature. This approximate reasoning ensured the unification of probability of the multiple value causality diagrams in the reasoning process, and the application to examples drawn from the results meet the knowledge of probability theory and is also in line with the actual.

Key words:causality diagram; normalization; approximate reasoning

文章編號：1674-8425(2016)04-0127-05

中圖分類號：TP181

文獻標識碼：A

doi:10.3969/j.issn.1674-8425(z).2016.04.022

作者簡介：劉紹紅(1992—)，女，重慶人，碩士研究生，主要從事因果圖、人工智能研究。

基金項目：國家社科基金資助項目(13BTJ008)

收稿日期：2015-12-21

引用格式：劉紹紅，王洪春.一種基于改進的多值因果圖的近似推理[J].重慶理工大學學報(自然科學)，2016(4):127-131.

Citation format：LIU Shao-hong, WANG Hong-chun.Approximate Reasoning Based on Improved Multi Valued Causal Graph[J].Journal of Chongqing University of Technology(Natural Science)，2016(4):127-131.