一種基于改進(jìn)的多值因果圖的近似推理

劉紹紅，王洪春

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

?

一種基于改進(jìn)的多值因果圖的近似推理

劉紹紅，王洪春

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

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

關(guān)鍵詞：因果圖；歸一性；近似推理

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

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

圖1　因果圖示例

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

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

1補(bǔ)充定義

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

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

2基本假設(shè)

假設(shè)1設(shè)各基本事件變量Bi相互獨(dú)立。

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

假設(shè)3設(shè)在多值因果圖中原因節(jié)點(diǎn)對(duì)結(jié)果節(jié)點(diǎn)只貢獻(xiàn)概率值，且每個(gè)貢獻(xiàn)間是簡(jiǎn)單相加的關(guān)系。

設(shè)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的各個(gè)狀態(tài)都有一個(gè)發(fā)生的可能性值，且某個(gè)事件的各個(gè)狀態(tài)是互斥的。各狀態(tài)發(fā)生的概率與其發(fā)生的可能性值成正比：

若

令

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

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

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

由貝葉斯公式得到

(1)

3實(shí)例分析

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

最終割集展開(kāi)成矩陣形式：

(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∪

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

由多值因果圖的補(bǔ)充定義有：

ψ(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ā)生概率滿(mǎn)足歸一性。

圖1的多值因果圖轉(zhuǎn)化為圖3：

圖3　轉(zhuǎn)化后的多值因果圖

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

4結(jié)束語(yǔ)

通過(guò)多值因果圖在補(bǔ)充定義下進(jìn)行改進(jìn)，然后向單值因果圖轉(zhuǎn)換，可以避開(kāi)對(duì)多值因果圖的每個(gè)事件都求最終割集和進(jìn)行不交化處理，也避開(kāi)了連接事件概率的強(qiáng)制歸一。不用求出每個(gè)事件的最終割集，從而提高速度，且轉(zhuǎn)換后的連接事件概率是合理、有效的。

參考文獻(xiàn)：

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

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

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

[4]梁新元.復(fù)雜因果圖并行推理算法研究[J].計(jì)算機(jī)科學(xué)與探索,2014,4:483-493.

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

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

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

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

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

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

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

(責(zé)任編輯何杰玲)

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

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

中圖分類(lèi)號(hào)：TP181

文獻(xiàn)標(biāo)識(shí)碼：A

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

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

基金項(xiàng)目：國(guó)家社科基金資助項(xiàng)目(13BTJ008)

收稿日期：2015-12-21

引用格式：劉紹紅，王洪春.一種基于改進(jìn)的多值因果圖的近似推理[J].重慶理工大學(xué)學(xué)報(bào)(自然科學(xué))，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.