人工智能第4章 不確定與非單調推理

1、人工智能Artificial Intelligence,主講：楊利英 西安電子科技大學 E_mail：,第五章不確定與非單調推理,4.1 基本概念 4.2 概率方法 4.3 主觀Bayes方法 4.4 可信度方法 4.5 證據(jù)理論 4.6 模糊推理 4.7 非單調推理,4.1 基本概念,4.1.1 不確定性推理 不確定性推理是建立在非經(jīng)典邏輯基礎上的一種推理，它是對不確定性知識的運用與處理。 不確定性推理就是從不確定性的初始證據(jù)（即事實）出發(fā)，通過運用不確定性的知識，最終推出具有一定程度不確定性的結論。,1. 不確定性的表示與度量 2. 不確定性匹配算法及閾值的選擇 3. 組合證據(jù)不確定性的計

2、算方法 4. 不確定性的傳遞算法 5. 結論不確定性的合成,4.1.2 不確定性推理中的基本問題,4.1.2 不確定性推理中的基本問題,1. 不確定性的表示與度量 不確定性推理中的“不確定性”一般分為兩類：一是知識的不確定性，一是證據(jù)的不確定性。 知識不確定性的表示：目前在專家系統(tǒng)中知識的不確定性一般是由領域專家給出的，通常用一個數(shù)值表示，它表示相應知識的不確定性程度，稱為知識的靜態(tài)強度。 證據(jù)不確定性的表示：證據(jù)不確定性的表示方法與知識不確定性的表示方法一致，通常也用一個數(shù)值表示，代表相應證據(jù)的不確定性程度，稱之為動態(tài)強度。,4.1.2 不確定性推理中的基本問題,2. 不確定性匹配算法及閾值

3、的選擇 設計一個不確定性匹配算法：用來計算匹配雙方相似程度。 指定一個匹配閾值。,4.1.2 不確定性推理中的基本問題,3. 組合證據(jù)不確定性的計算方法 最大最小法： T(E1 AND E2)=minT(E1),T(E2) T(E1 OR E2)=maxT(E1),T(E2) 概率法： T(E1 AND E2)=T(E1)T(E2) T(E1 OR E2)=T(E1)T(E2)T(E1)T(E2) 有界法： T(E1 AND E2)=max0,T(E1)T(E2)1 T(E1 OR E2)=min1,T(E1)T(E2) 其中，T(E)表示證據(jù)E為真的程度（動態(tài)強度），如可信度、概率等。,4.

4、1.2 不確定性推理中的基本問題,4. 不確定性的傳遞算法 在每一步推理中，如何把證據(jù)及知識的不確定性傳遞給結論，即如何計算結論的不確定性。,4.1.2 不確定性推理中的基本問題,5. 結論不確定性的合成 用不同知識進行推理得到了相同結論，但所得結論的不確定性卻不同。此時，需要用合適的算法對結論的不確定性進行合成。,4.1.3 不確定性推理方法的分類,不確定性推理方法主要可分為模型法與控制法。 模型法：在推理一級對確定性推理進行擴展，引入證據(jù)的不確定性及知識的不確定性。 模型方法又分為數(shù)值方法和非數(shù)值方法兩類。數(shù)值方法對不確定性進行定量的描述，按其所依據(jù)的理論又可分為基于概率的方法(概率方法、

5、主觀Bayes方法、可信度方法、證據(jù)理論)和基于模糊理論的方法（模糊推理）。,4.2 概率方法,4.2.1 經(jīng)典概率方法 （1）設有如下產(chǎn)生式規(guī)則： IFE THEN H 其中，E為前提條件，H為結論。條件概率P(H|E) 可以作為在證據(jù)E出現(xiàn)時結論H的確定性程度，即規(guī)則的 靜態(tài)強度。 （2）對于復合條件 E=E1 AND E2 AND AND En 當已知條件概率P(H|E1,E2,En)時，就可把它作為在證據(jù)E1,E2,En出現(xiàn)時結論H的確定性程度。 （3）先驗概率： P(H) 后驗概率： P(H|E),若A1,A2,An是彼此獨立的事件，對于事件B，則有 其中，P(Ai)是事件Ai的先驗

6、概率；P(B|Ai)是在事件Ai發(fā)生條件下事件B的條件概率。 對于一組產(chǎn)生式規(guī)則 IFETHENHi 同樣有后驗概率如下（ Hi 確定性的程度，或規(guī)則的靜態(tài)強度）：,4.2.2 逆概率方法,對于多個證據(jù),逆概率方法舉例,例 設H1,H2,H3分別是三個結論，E是支持這些結論的證據(jù)。已知： P(H1)=0.3, P(H2)=0.4, P(H3)=0.5 P(E|H1)=0.5, P(E|H2)=0.3, P(E|H3)=0.4 求P(H1|E),P(H2|E)及P(H3|E)的值各是多少？ 解： 同理可得： P(H2|E)=0.26, P(H3|E)=0.43,對應的產(chǎn)生式規(guī)則： IFETHEN

7、H1 IFETHENH2 IFETHENH3 規(guī)則的靜態(tài)強度(Hi為真的程度、或不確定性程度) P(H1|E)=0.32 P(H2|E)=0.26 P(H3|E)=0.43,逆概率法的特點,優(yōu)點： 逆概率法有較強的理論背景和良好的數(shù)學特性，當證據(jù)彼此獨立時計算的復雜度比較低。 缺點： 逆概率法要求給出結論Hi的先驗概率P(Hi)及條件概率P(Ej|Hi)。,4.3 主觀Bayes方法,4.3.1 知識不確定性的表示 在主觀Bayes方法中，知識是用產(chǎn)生式規(guī)則表示的，具體形式為： IFE THEN (LS,LN) H (P(H) 其中， P(H)是結論H的先驗概率，由專家根據(jù)經(jīng)驗給出。 LS稱為

8、充分性度量，用于指出E對H的支持程度，取值范圍為0,)，其定義為： LS=P(E|H)/P(E|H)。 LN稱為必要性度量，用于指出 E對H的支持程度，取值范圍為0,)，其定義為： LN=P(E|H)/P(E|H)=(1-P(E|H)/(1-P(E|H)。 LS和LN的值由領域專家給出，相當于知識的靜態(tài)強度。,4.3.2 證據(jù)不確定性的表示,主觀Bayes方法中，證據(jù)的不確定性也用概率表示。對于證據(jù)E，由用戶根據(jù)觀察S給出P(E|S)，即動態(tài)強度。用P(E|S)描述證據(jù)的不確定性 （證據(jù)E不是可以直接觀測的）。 由于主觀給定P(E|S)有所困難，所以實際中可以用可信度C(E|S)代替P(E|S

9、)。 在探礦專家系統(tǒng)PROSPECTOR中C(E|S)取整數(shù)：-5，.5 C(E|S)=-5表示在觀測S下證據(jù)E肯定不存在P(E|S)=0 C(E|S)= 5表示在觀測S下證據(jù)E肯定存在P(E|S)=1 C(E|S)= 0表示S與E無關,即P(E|S)= P(E),給定C(E|S)后，P(E|S)可近似計算如下（分段線性插值）：,采用主觀Bayes方法 IF E THEN (LS,LN) H (P(H) 時要解決的主要問題： （1）證據(jù)肯定存在時，如何計算P(H|E)？ 此時P(E|S)=1。 （2）證據(jù)肯定不存在時，如何計算P(H| E)？ 此時P(E|S)=0。 （3）證據(jù)具有不確定性時，

10、如何計算P(H|S)？ 此時0P(E|S)1。,4.3.3 組合證據(jù)不確定性的算法,（1）最大最小法 當組合證據(jù)是多個單一證據(jù)的合取時，即 E=E1 AND E2 AND AND En 則：P(E|S)=minP(E1|S),P(E2|S),P(En|S) 當組合證據(jù)是多個單一證據(jù)的析取時，即 E=E1 OR E2 OR OR En 則：P(E|S)=maxP(E1|S),P(E2|S),P(En|S) （2）對于“”運算：P(E|S)=1-P(E|S),4.3.4 不確定性的傳遞算法,（1）根據(jù)證據(jù)E的條件概率P(E|S) 及LS、LN的值，把H的先驗概率P(H)更新為后驗概率P(H|E)

11、。 （2） 分以下3種情況討論： 證據(jù)肯定存在： P(E|S)=1，即P(E)=1 證據(jù)肯定不存在： P(E|S)=0，即P(E)=0 證據(jù)不確定： 0P(E|S)1 （3）引入幾率函數(shù)(x),它與概率的關系為： (x)=P(x)/(1-P(x),P(x)=(x)/(1+(x) 可以看出，概率函數(shù)與幾率函數(shù)具有相同的單調性。,證據(jù)肯定存在時,(x)=P(x)/(1-P(x),P(x)=(x)/(1+(x) 在證據(jù)肯定存在時，P(E)=P(E|S)=1。 由Bayes公式得： P(H|E)=P(E|H)P(H)/P(E)(1) P(H|E)=P(E|H)P(H)/P(E)(2) (1)式除以(2

12、)式得： P(H|E)/P(H|E)=P(E|H)/P(E|H)P(H)/P(H) 由充分性度量LS和幾率函數(shù)的定義可得： (H|E)=LS(H) 即 P(H|E)=LSP(H)/(LS-1)P(H)+1,充分性度量LS的意義,對于知識： IF E THEN (LS,LN) H (P(H) 在證據(jù)E肯定存在時，可以根據(jù)LS給出結論H的可信度P(H|E)。 當LS1時，(H|E)=LS(H)(H)，相應有P(H|E)P(H)，表明由于證據(jù)E的存在，可增強H為真的程度（有利證據(jù)）。一般情況下LS1。 當LS1時，(H|E)=LS(H)(H)，表明E與H無關（無關證據(jù)）。 當LS1時，(H|E)=L

13、S(H)(H)，表明由于證據(jù)E的存在，減小了H為真的程度（不利證據(jù)）。 當LS0時，(H|E)=LS(H)0，表明由于證據(jù)E的存在，導致H為假（否定性的證據(jù)）。,證據(jù)肯定不存在時,在證據(jù)肯定不存在時，P(E)=P(E|S)=0， P(E)=1。 由Bayes公式得： P(H|E)=P(E|H)P(H)/P(E)(1) P(H|E)=P(E|H)P(H)/P(E)(2) (1)式除以(2)式得： P(H|E)/P(H|E)=P(E|H)/P(E|H)P(H)/P(H) 根據(jù)必要性度量LN和幾率函數(shù)的定義，可得： (H|E)=LN(H) 即 P(H|E)=LNP(H)/(LN-1)P(H)+1,必

14、要性度量LN的意義,對于知識： IF E THEN (LS,LN) H (P(H) 在證據(jù)E肯定不存在時，可以根據(jù)LN給出結論H的可信度P(H|E) 。 當LN1時，(H|E)=LN(H)(H)，相應有P(H|E)P(H)，表明由于證據(jù)E不存在，增強了H為真的程度（ E 為有利證據(jù)）。,對LS 和 LN 的說明,LS1: 表明證據(jù) E是對H有利的證據(jù)。 LN1：表明證據(jù)E是對H有利的證據(jù)。 所以： 不能出現(xiàn)LS1且LN1的取值。 LS1， LN1。,證據(jù)不確定時,當0P(E|S)1時，可以證明（Duda等人于1976年證明）: P(H|S)=P(H|E)P(E|S)+P(H|E)P(E|S)

15、當P(E|S)=1時，證據(jù)肯定存在，此時P(H|S)=P(H|E) 。 當P(E|S)=0時，證據(jù)肯定不存在，此時P(H|S)=P(H| E) 。 當P(E|S)=P(E)時，證據(jù)E與觀察S無關。由全概率公式得： P(H|S)=P(H|E)P(E)+P(H|E)P(E)P(H) 當P(E|S)為其它值時，通過分段線性插值計算P(H|S)，即,對于知識： IF E THEN (LS,LN) H (P(H) 給定證據(jù)E的不確定性度量P(E|S)，則結論的可信度可以表示為： 該公式稱為EH公式。用C(E/S) 代替P(E/S)，可得到等價的CP公式。,對于初始證據(jù)，由于其不確定性是用可信度C(E/S

16、) 給出的，此時只要把EH公式中的P(E/S)轉換為C(E/S) ，就得到用可信度C(E/S) 計算P(H/S)的CP公式：,4.3.5 結論不確定性的合成算法,若有n條知識都支持相同的結論，而且每條知識的前提條件所對應的證據(jù)Ei(i=1,2,n)都有相應的觀察Si與之對應，此時只要先對每條知識分別求出幾率函數(shù)(H|Si)，然后就可運用下述公式求出(H|S1S2Sn):,主觀Bayes方法推理示例,例 (王永慶教材 P169) 設有如下知識： R1:IF E1THEN(2, 0.001) H1 R2:IF E2THEN(100, 0.001) H1 R3:IF H1THEN(200, 0.01

17、 ) H2 已知：(H1)0.1， (H2)0.01 C(E1|S1)=2, C(E2|S2)=1 求： (H2|S1S2)=? 1. 計算(H1|S1) P(H1)=(H1)/(1+(H1)=0.09 P(H1|E1)=(H1|E1)/(1+(H1|E1)= LS1(H1)/(1+LS1(H1)=0.17 C(E1|S1)=20 P(H1|S1)=P(H1)+P(H1|E1)-P(H1)1/5C(E1|S1) =0.122 (H1|S1)=P(H1|S1)/(1- P(H1|S1)=0.14,R1:IF E1THEN(2, 0.001) H1 R2:IF E2THEN(100, 0.001)

18、 H1 R3:IF H1THEN(200, 0.01 ) H2 2. 計算(H1|S2) P(H1|E2)=(H1|E2)/(1+(H1|E2)= LS2(H1)/(1+LS2(H1)=0.91 C(E2|S2)=10 P(H1|S2)=P(H1)+P(H1|E2)-P(H1)1/5C(E2|S2) =0.254 (H1|S2)=P(H1|S2)/(1- P(H1|S2)=0.34,R1:IF E1THEN(2, 0.001) H1 R2:IF E2THEN(100, 0.001) H1 R3:IF H1THEN(200, 0.01 ) H2 3. 計算(H1|S1S2) (H1|S1S2)=

19、(H1|S1)/(H1)(H1|S2)/(H1)(H1) =0.476 4. 計算(H2|S1S2) (H1|S1S2)=0.476(H1)=0.1 P(H2|S1S2)=P(H2)+ P(H2|H1)-P(H2) /1-P(H1) P(H1|S1S2)-P(H1)=0.175 (H2|S1S2)=P(H2|S1S2)/(1- P(H2|S1S2)=0.212,優(yōu)點： 主觀Bayes方法中的計算公式大多是在概率論的基礎上推導出來的，具有較堅實的理論基礎。 知識的靜態(tài)強度LS及LN是由領域專家給出，避免了大量的數(shù)據(jù)統(tǒng)計工作。 主觀Bayes方法不僅給出了證據(jù)肯定存在、肯定不存在時更新后驗概率的方

20、法，還給出了證據(jù)不確定時的更新方法，實現(xiàn)了不確定性的逐級傳遞。,主觀Bayes方法的特點,主觀Bayes方法的特點,缺點： 它要求領域專家在給出知識時，同時給出H的先驗概率P(H)，這比較困難。 Bayes定理要求事件間獨立，使其應用受限制。,4.4 可信度方法,4.4.1 可信度的概念 根據(jù)經(jīng)驗對一個事物和現(xiàn)象為真的相信程度稱為可信度。 在可信度方法中，由專家給出規(guī)則或知識的可信度，從而可避免對先驗概率、條件概率的要求。 可信度方法首先在專家系統(tǒng)MYCIN中得到了成功的應用。,4.4.2 C-F模型,C-F模型是基于可信度表示的不確定推理的基本方法。 1、C-F模型中知識不確定性的表示 知識

21、是用產(chǎn)生式規(guī)則表示的，其一般形式為： IFETHENH(CF(H,E) 其中，CF(H,E)是該知識的可信度，稱為可信度因子或規(guī)則強度，即靜態(tài)強度。一般情況下，CF(H,E)-1,1。 CF(H,E)0對應于P(H|E)P(H); CF(H,E)0對應于P(H|E)P(H); CF(H,E)=0對應于P(H|E)=P(H)。,可信度因子的定義,IFETHENH(CF(H,E) CF(H,E)定義為： CF(H,E)=MB(H,E)-MD(H,E) MB反映了證據(jù)對結論有利的一面，MD反映了證據(jù)對結論不利的一面。MB(Measure Belief)稱為信任增長度。MD(Measure Disbe

22、lief)稱為不信任增長度。 MB和MD的定義如下：,當P(H|E)P(H)時： 信任增長度MB(H,E)0， 不信任增長度MD(H,E)=0 。 當P(H|E)0， 信任增長度MB(H,E) =0。 MB(H,E)與MD(H,E)是互斥的： 當MB(H,E)0時，MD(H,E)0 當MD(H,E)0時，MB(H,E)0,CF(H,E)的計算公式,根據(jù)定義CF(H,E)=MB(H,E)-MD(H,E)，及 MB(H,E)與MD(H,E)的互斥性，可得: 從上式可看出： CF(H,E)0對應于P(H|E)P(H); CF(H,E)0對應于P(H|E)P(H); CF(H,E)=0對應于P(H|E

23、)=P(H)。,IFETHENH(CF(H,E) 當且僅當P(H|E)=1時, CF(H,E)=1 當且僅當P(H|E)=0時, CF(H,E)=-1 CF(H,E)定性地反映了P(H|E)的大小,因此可以用CF(H,E)近似表示P(H|E)的大小,從而描述了規(guī)則的可信度。,2. C-F模型中證據(jù)不確定性的表示 證據(jù)的不確定性也用可信度因子表示。如 CF(E)=0.6 CF(E)的取值范圍：-1，+1。 CF(E)0:表示證據(jù)以某種程度為真。 CF(E)0:表示證據(jù)以某種程度為假。 CF(E)表示證據(jù)的強度，即動態(tài)強度。,3. C-F模型中組合證據(jù)不確定性的算法,可采用最大最小法。 若 E=E

24、1 AND E2 ANDAND En, 則 CF(E)=minCF(E1),CF(E2),CF(En) 若 E=E1 OR E2 OROR En, 則 CF(E)=maxCF(E1),CF(E2),CF(En),4. 不確定性的傳遞算法,IFETHENH(CF(H,E) 結論H的可信度由下式計算：CF(H)=CF(H,E)max0,CF(E) 可以看出： (1)若證據(jù)為假，即CF(E)0時,有 CF(H)=0，說明該模型沒有考慮證據(jù)為假時對結論產(chǎn)生的影響。 (2) 若證據(jù)為真，即CF(E)1時，有CF(H)=CF(H,E)，說明知識中的規(guī)則強度CF(H,E)實際上就是在前提條件對應的證據(jù)為真時

25、結論H的可信度。,5. 結論不確定性的合成算法 若由多條不同知識推出了相同的結論，但可信度不同，則用合成算法求出綜合可信度。 設有如下知識： IFE1THENH(CF(H,E1) IFE2THENH(CF(H,E2) 則結論H的綜合可信度分如下兩步算出： 首先分別對每一條知識求出CF(H): 計算CF1(H)、CF2(H) 然后用下述公式求出E1與E2對H的綜合可信度CF12(H):,C-F模型推理示例,例 (王永慶教材 P175) 設有如下一組知識： R1: IFE1THENH(0.8) R2: IFE2THENH(0.6) R3: IFE3THENH(-0.5) R4: IFE4 AND

26、(E5 OR E6)THENE1(0.7) R5: IFE7 AND E8 THENE3(0.9) 已知：CF(E2)=0.8, CF(E4)=0.5, CF(E5)=0.6 CF(E6)=0.7, CF(E7)=0.6, CF(E8)=0.9 求：CF(H)=？ 解：由R4得到： CF(E1)=0.7max0,CFE4 AND (E5 OR E6) =0.7max0,minCF(E4),CF(E5 OR E6) =0.35 由R5得到： CF(E3)=0.9max0,CFE7 AND E8 =0.54,R1: IFE1THENH(0.8) R2: IFE2THENH(0.6) R3: IFE

27、3THENH(-0.5) 由R1得到： CF1(H)=0.8max0,CF(E1)=0.28 由R2得到： CF2(H)=0.6max0,CF(E2)=0.48 由R3得到： CF3(H)=-0.5max0,CF(E3)=-0.27 根據(jù)結論不確定性的合成算法： CF12(H)=CF1(H)+CF2(H)-CF1(H)CF2(H)=0.63 CF123(H)=CF12(H)+CF3(H)/1-min|CF12(H)|,|CF3(H)| =0.49 即最終的綜合可信度為CF(H)=0.49。,IFETHEN H(CF(H,E) C-F模型的核心問題是三個可信度： (1) 知識的可信度CF(H,E

28、)：取值范圍-1，1 CF(H,E)=1 對應于 P(H|E)=1 (證據(jù)絕對支持結論) CF(H,E)=-1 對應于 P(H|E)=0 (證據(jù)絕對否定結論) CF(H,E)=0 對應于 P(H|E)=P(H) (證據(jù)與結論無關) (2) 證據(jù)的可信度CF(E)：取值范圍-1，1 CF(E)=1 對應于 P(E)=1 (證據(jù)絕對存在) ; CF(E)=-1 對應于 P(E)=0; (證據(jù)絕對不存在) CF(E)=0 對應于 P(E)=0.5 (對證據(jù)一無所知)。 (3) 結論的可信度CF(H)：取值范圍-1，1 CF(H)=CF(H,E)max0,CF(E) 該公式隱含了一個知識運用的條件,

29、即CF(E)0。,4.4.3 帶有閾值限度的不確定性推理,1. 知識不確定性的表示 知識用下述形式表示： IFETHENH(CF(H,E),) 其中： E為知識的前提條件，可以是簡單條件，也可以是復合條件。 CF(H,E)為知識的可信度，取值范圍為（0,1， CF(H,E) 的值越大，表示相應知識的可信度越高。 是閾值，明確規(guī)定了知識運用的條件：只有當CF(E)時，該知識才能夠被應用。的取值范圍為(0,1。,IFETHENH(CF(H,E),) 2. 證據(jù)不確定性的表示 證據(jù)E的可信度仍為CF(E)，其取值范圍為：0，1 CF(E)=1 對應于 P(E)=1 (證據(jù)絕對存在) ; CF(E)=

30、0 對應于 P(E)=0; (證據(jù)絕對不存在) 3.組合證據(jù)不確定性的算法 取大取小原則 4. 不確定性的傳遞算法 當CF(E)時，CF(H)=CF(H,E)CF(E),5. 結論不確定性的合成算法 設有多條規(guī)則有相同的結論，即 IFE1THEN H(CF(H,E1),1) IFE2THEN H(CF(H,E2),2) IFEnTHEN H(CF(H,En),n) 如果這n條規(guī)則都滿足：CF(Ei)i，i=1,2,n 且都被啟用，則首先分別對每條知識求出它對CFi(H)； 然后求結論H的綜合可信度CF(H)。,求綜合可信度的幾種方法,極大值法： CF(H)=maxCF1(H),CF2(H),C

31、Fn(H) 加權求和法： 有限和法： 遞推法： C1=CF(H,E1)CF(E1) Ck=Ck-1+(1-Ck-1)CF(H,Ek)CF(Ek),4.4.4 加權的不確定性推理,1. 知識不確定性的表示 IFE1(1) AND E2(2) ANDAND En(n) THEN H (CF(H,E),) 其中i(i=1,2,n)是加權因子，是閾值，其值均由專家給出。 加權因子的取值范圍一般為0,1,且應滿足歸一條件，即,4.4.4 加權的不確定性推理,2. 組合證據(jù)不確定性的算法 若有CF(E1)，CF(E2)，CF( En)，則組合證據(jù)的可信度為：,3. 不確定性的傳遞算法 當一條知識的CF(E

32、)滿足如下條件時， CF(E) 該知識就可被應用。結論H的可信度為： CF(H)=CF(H,E)CF(E) 加權因子的引入不僅可以區(qū)分不同證據(jù)的重要性，同時還可以解決證據(jù)不全時的推理問題。,加權不確定性推理舉例(1),例（王永慶教材 P181） 設有如下知識： R1: IF E1(0.6) AND E2(0.4) THEN E6(0.8,0.75) R2: IF E3(0.5) AND E4(0.3) AND E5(0.2) THEN E7(0.7,0.6) R3: IF E6(0.7) AND E7(0.3) THEN H(0.75,0.6) 已知：CF(E1)=0.9, CF(E2)=0.

33、8, CF(E3)=0.7, CF(E4)=0.6, CF(E5)=0.5 求：CF(H)=? 解：由R1得到： CF(E1(0.6) AND E2(0.4)=0.861=0.75 R1可被應用。,加權不確定性推理舉例(2),由R2得到： CF(E3(0.5) AND E4(0.3) AND E5(0.2)0.632 =0.6 R2可被應用。 0.860.63 R1先被應用。 由R1得到：CF(E6)=0.69 由R2得到：CF(E7)=0.44 由R3得到： CF(E6(0.7) AND E7(0.3)=0.6153 =0.6 R3可被應用,得到： CF(H)=0.46 即最終得到的結論H可

34、信度為0.46,4.4.5 前提條件中帶有可信度因子的不確定推理,1. 知識不確定性的表示 IFE1(cf1) AND E2(cf2) ANDAND En(cfn) THEN H (CF(H,E),) 其中，cfi子條件Ei(i=1,2,n）的可信度。cfi在0,1上取值，其 值由專家給出。 核心思想：知識的前提條件不一定為真，只要前提條件滿足一 定的可信度，或具備一定的為真的可能性，就可以推出結論H。 加入加權因子后得到： IFE1(cf1,1) AND E2(cf2,2) ANDAND En(cfn,n) THEN H (CF(H,E),) 2. 證據(jù)不確定性的表示 證據(jù)Ei的可信度記為c

35、fi,其取值范圍在0,1上。,3. 不確定性匹配算法 不帶加權因子的不確定性匹配算法： 知識：IFE1(cf1) AND E2(cf2) ANDAND En(cfn) THEN H (CF(H,E),) 條件：E1(cf1)，E2(cf2)， En(cfn) 匹配算法： max0,cf1-cf1+max0,cf2-cf2+ max0,cfn-cfn 帶加權因子的不確定性匹配算法： 知識：IFE1(cf1,1) AND E2(cf2,2) ANDAND En(cfn,n) THEN H (CF(H,E),) 匹配算法： (1max0,cf1-cf1)+(2max0,cf2-cf2)+(nmax0

36、,cfn-cfn) ,4. 不確定性的傳遞算法,不帶加權因子時： CF(H)=(1-max0,cf1-cf1)(1-max0,cf2-cf2)(1-max0,cfn-cfn)CF(H,E) 帶加權因子時： CF(H)=(1(1-max0,cf1-f1)(2(1-max0,cf2-cf2)(n(1-max0,cfn-cfn)CF(H,E),基于可信度的不確定性推理方法的特點,優(yōu)點： 簡單、直觀。 缺點： 可信度因子依賴于專家主觀指定，沒有統(tǒng)一、客觀的尺度，容易產(chǎn)生片面性。 隨著推理延伸，可信度越來越不可靠，誤差越來越大。當推理深度達到一定深度時，有可能出現(xiàn)推出的結論不再可信的情況。,4.5 證據(jù)

37、理論,證據(jù)理論是A.P.Dempster于1967年研究統(tǒng)計問題時首先提出的，他給出了上、下限概率的概念及其合成規(guī)則，第一次明確給出了不滿足可加性的概率。Dempster的學生G.Shafer把證據(jù)理論推廣到更加一般的情形，并使之系統(tǒng)化、理論化。因此證據(jù)理論又稱為D-S證據(jù)理論(The D-S theory of evidence)。 1981年J.A.Barnett把該理論引入專家系統(tǒng)，同年J.Garvey等人用它實現(xiàn)了不確定性推理。 該理論滿足比概率論弱的公理，能夠區(qū)分“不確定”與“不知道”的差異，并能處理由“不知道”引起的不確定性，具有較大的靈活性。,4.5.1 D-S理論,證據(jù)理論是建

38、立在一個非空集合D上的理論。D為辨別框架(the frame of discernment)，它是關于某個問題域中所有可能的答案組成的有限集合，并且這些問題相互排斥，對于問題的描述是完備的。 由D的所有子集組成的集類 ，表示判斷該問題正確答案的所有命題構成的集合。 為了描述和處理不確定性，引入了概率分配函數(shù) (BPA, Basic Probability Assignment)，信任函數(shù)(Belief Function)以及似然函數(shù)(Plausibility Function)等概念。,1.概率分配函數(shù),設D為樣本空間，領域內的命題都用D的子集表示，則概率分配函數(shù)定義如下： 定義 設函數(shù)M：

39、0，1， 滿足 M()0， 則稱M是 上的概率分配函數(shù)，M(A)稱為A的基本概率數(shù)。 若子集A滿足M(A)0，則稱A為焦元 (focal element)。,對概率分配函數(shù)的說明,概率分配函數(shù)的作用是把D的任意一個子集A都映射為0，1上的一個數(shù)M(A)。 當A是D的真子集時，M(A)表示對相應命題的精確信度度。當A由多個元素組成時，M(A)不包括對A的子集的精確信任度，而且也不知道該如何進行分配。當AD時，M(A)是對D的各子集進行基本可信度分配后剩下的部分，表示不知道如何分配這部分。 概率分配函數(shù)不是概率。,2. 信任函數(shù)（Belief Function）,定義 命題的信任函數(shù)Bel： 0，

40、1， 且滿足 Bel函數(shù)也稱為下限函數(shù)，Bel(A)表示對命題A為真的信任程度。 由信任函數(shù)和概率分配函數(shù)的定義，可以推出：,3.似然函數(shù)(Plausibility Function),似然度函數(shù)又稱為不可駁斥函數(shù)或上限函數(shù). 定義 似然函數(shù)Pl： 0，1， 且滿足 由于Bel(A)表示對A為真的信任程度，所以Bel(A)表示對A為真，即A為假的信任程度，由此Pl(A)表示對A為非假的信任程度。,似然函數(shù)Pl (A)的另一種表達形式,證明過程：,4.Bel(A)與Pl(A)的關系,由上面兩個公式可以看出，Bel(A)=Pl(A)。 分別稱Bel(A)和Pl (A)為對A信任程度的下限和上限，記

41、為 A(Bel(A)，Pl (A) Pl (A)Bel(A)表示對A不知道的程度，即既非信任又非不信任的那部分。 減小Pl (A)Bel(A)，即減小對A不知道的程度是證據(jù)理論的目的之一。,D-S不確定區(qū)間,證據(jù)理論一個很吸引人的地方是能夠很好的表達未知信息的程度，當D-S證據(jù)理論把一個信度賦給一個子集的同時,并不要求把剩余的信度賦給子集的補，即Bel(B)+Bel(B)1，而1-Bel(B)-Bel(B)=Pl (B)Bel(B)0就表示了未知的程度，用D-S不確定區(qū)間(uncertainty interval)表示這種關系。,D-S不確定區(qū)間,關于信任程度下限和上限的例子,A(Bel(A)

42、，Pl (A) A(0，0)：A為假 A(0，1)：對A一無所知 A(1，1)：A為真 A(0.25，1)：對A為真有0.25的信任度 A(0，0.85)：對A為假有0.15的信任度 A(0.25，0.85)：對A為真的信任度比對A為假的信任度稍高一點,5.概率分配函數(shù)的正交和,兩個概率分配函數(shù)的合成 設M1和M2是同一樣本空間D上的兩個概率分配函數(shù)，根據(jù)Dempster合成規(guī)則，其正交和定義為：,上式中，若分母為0，則表明M1和M2矛盾，正交和不存在。,多個概率分配函數(shù)的合成,設M1、M2、，Mn是同一樣本空間D上的n個概率分配函數(shù)，如果它們不矛盾，可以通過正交和運算將它們組合為一個概率分配

43、函數(shù)，定義如下：,兩種合成方式的等效性,Dempster規(guī)則的多證據(jù)組合和兩個證據(jù)的組合是等效的，而且組合運算具有可交換性和可結合性。因而，多個證據(jù)的合成還可以通過兩個證據(jù)合成的遞歸運算得到。,兩種合成方式的等效性,Dempster合成規(guī)則的空間解釋,Dempster合成規(guī)則的空間解釋,橫條和豎條的交是一個小矩形，其測度為m1(Ai)m2(Bj)。由于該小矩形是同時分配到Ai和Bj上的，所以M1和M2的聯(lián)合作用就是把m1(Ai)m2(Bj)確切的分配到AiBj上。 對于給定的子集A，確切的分配到A上的總概率為 當分配到空集上的總概率不為0時，需對其他非空集合上的總概率進行歸一化。,4.5.2

44、一個具體的不確定性推理模型,在D-S理論中，Bel(A)和Pl (A)分別表示對命題A信任程度的下限和上限，因而可用(Bel(A)，Pl (A)表示證據(jù)的不確定性，同理，也可以用來表示不確定性知識規(guī)則強度的下限和上限。這樣就可以建立相應的不確定性推理模型。 由于Bel(A)和Pl (A)建立在概率分配函數(shù)的基礎之上，概率分配函數(shù)定義的不同，將產(chǎn)生不同的推理模型。 本節(jié)根據(jù)一個特殊的概率分配函數(shù)，討論一個具體的不確定性推理模型。,1.概率分配函數(shù)與類概率函數(shù),在該模型中，樣本空間Ds1,s2,sn上的概率分配函數(shù)滿足： 可以看出，在此概率分配函數(shù)中，只有單個元素構成的子集及樣本空間D的概率分配函

45、數(shù)有可能大于0，其它子集的概率分配函數(shù)都為0。,此概率分配函數(shù)的特性,概率分配函數(shù)的正交和,由該概率分配函數(shù)的定義，可以把M1和M2的正交和簡化為：,類概率函數(shù),定義 命題A的類概率函數(shù)為： f(A)具有如下性質(證明過程 王永慶教材P192)：,關于類概率函數(shù)的推論,2.知識不確定性的表示,在該模型中，不確定性知識用如下形式的產(chǎn)生式規(guī)則表示： IF E THEN Hh1,h2,hn CFc1,c2,cn 其中： （1）E為前提條件，可以是簡單條件，也可以是用AND或OR連接起來的復合條件； （2）H是結論，用樣本空間中的子集表示， h1,h2,hn是該子集中的元素； （3）CF是可信度因子，

46、用集合形式表示，其中ci用來指出hi（i=1,.,n）的可信度，ci滿足：,3.證據(jù)不確定性的表示,不確定性證據(jù)E的確定性用CER(E)表示。 初始證據(jù)的確定性由用戶給出。 對于用前面推理所得結論作為當前推理的證據(jù)，其確定性由推理得到。 CER(E)的取值范圍為0,1。,4.組合證據(jù)不確定性的算法,最大最小法 當組合證據(jù)是多個單一證據(jù)的合取時，即 E=E1 AND E2 AND AND En 則：CER(E)=minCER(E1), CER(E2), CER(En) 當組合證據(jù)是多個單一證據(jù)的析取時，即 E=E1 OR E2 OR OR En 則： CER(E)=maxCER(E1), CER

47、(E2), CER(En),5.不確定性的傳遞算法,對于知識：IF E THEN Hh1,h2,hn CFc1,c2,cn 結論H的確定性通過下述步驟給出： （1）求出H的概率分配函數(shù) 如果有N條知識都支持同一個結論H，則先分別求出N個概率分配函數(shù)，然后計算其正交和，從而得到H的概率分配函數(shù)。,5.不確定性的傳遞算法,（2）求出Bel(H),Pl(H),f(H),5.不確定性的傳遞算法,（3）按如下公式求出H的確定性CER(H) CER(H)=MD(H|E) f(H) 其中， MD(H|E)是知識的前提條件與相應證據(jù)E的匹配度，定義為：,D-S理論的不足與改進,不足： 復雜度成指數(shù)級增長。 要

48、求樣本空間D中元素互斥，這點在許多應用領域中很難滿足。 改進： Barnett提出，將D劃分為若干組，每組只包含互斥的元素，稱為一個辨識框架(the frame of discernment)。求解問題時，只需要在各自的辨別框架中考慮概率分配的影響。,4.6 模糊推理,模糊推理是指基于模糊理論進行的推理。,4. 6.1 模糊命題,含有模糊概念、模糊數(shù)據(jù)的語句稱為模糊命題。 它的一般表示形式為： xis A 或者 x is A(CF) 其中，A是模糊概念或者模糊數(shù)，用相應的模糊集及隸屬函數(shù)刻畫； x是論域上的變量，用以代表所論述對象的屬性； CF是該模糊命題的可信度，它既可以是一個確定的數(shù)，也可

49、以是一個模糊數(shù)或者模糊語言值。 模糊語言值是指表示大小、長短、多少等程度的一些詞匯。如：極大、很大、相當大、比較大。模糊語言值同樣可用模糊集描述。,4.6.2 模糊知識的表示,（1）模糊產(chǎn)生式規(guī)則的一般形式是： IFETHENH(CF,) 其中，E是用模糊命題表示的模糊條件；H是用模糊命題表示的模糊結論；CF是知識的可信度因子，它既可以是一個確定的數(shù)，也可以是一個模糊數(shù)或模糊語言值。是匹配度的閾值，用以指出知識被運用的條件。例如： IFx is A THEN y is B (CF,) （2）推理中所用的證據(jù)也用模糊命題表示，一般形式為 xisA 或者 xisA(CF) （3）模糊推理要解決的問

50、題：證據(jù)與知識的條件是否匹配：如果匹配，如何利用知識及證據(jù)推出結論。,4.6.3 模糊匹配與沖突消解,在模糊推理中，知識前提條件中的A與證據(jù)中的A不一定完全相同，因此首先必須考慮匹配問題。例如： IF x is 小THENy is 大(0.6) x is 較小 兩個模糊集或模糊概念的相似程度稱為匹配度。常用的計算匹配度的方法主要有貼近度、語義距離及相似度等。,1. 貼近度 設A與B分別是論域U=u1,u2,un上的兩個模糊集，則它們的貼近度定義為： (A,B)= AB+(1-AB) /2 其中,計算匹配度的方法,2. 語義距離 (1)海明距離 (2)歐幾里得距離 (3)明可夫斯基距離 (4)切

51、比雪夫距離 匹配度為：1-d(A,B),計算匹配度的方法,3. 相似度 (1) 最大最小法,計算匹配度的方法,計算匹配度的方法,3. 相似度 (2) 算術平均法,計算匹配度的方法,3. 相似度 (3) 幾何平均最小法,計算匹配度的方法,3. 相似度 (4) 相關系數(shù)法,計算匹配度的方法,3. 相似度 (5) 指數(shù)法,匹配度舉例,設U=a,b,c,d A=0.3/a+0.4/b+0.6/c+0.8/d B=0.2/a+0.5/b+0.6/c+0.7/d 貼近度： AB=(0.30.2)(0.40.5)(0.60.6)(0.80.7)=0.7 AB=(0.30.2)(0.40.5)(0.60.6)

52、(0.80.7)=0.3 (A,B)=1/2AB+(1-AB)=1/20.7+(1-0.3)=0.7 海明距離： d(A,B)=1/4(|0.3-0.2|+|0.4-0.5|+|0.6-0.6|+|0.8-0.7|)=0.075 (A,B)=1-d(A,B)=1-0.075=0.925 相似度： 最大最小法： r(A,B)=(0.30.2)+(0.40.5)+(0.60.6)+(0.80.7)/(0.30.2)+(0.40.5)+(0.60.6)+(0.80.7) =1.9/2.2=0.86,(1) 分別計算出每一個子條件與其證據(jù)的匹配度 例如對復合條件 E=x1 is A1 AND x2 i

53、s A2 AND x3 is A3 及相應證據(jù)E: x1 is A1 , x2 is A2 , x3 is A3 分別算出Ai與Ai的匹配度match(Ai,Ai),i=1,2,3。 (2) 求出整個前提條件與證據(jù)的總匹配度。目前常用的方法有“取極小”和“相乘”等。 match(E,E)=minmatch(A1,A1),match(A2,A2), match(A3,A3) match(E,E)=match(A1,A1)match(A2,A2)match(A3,A3) (3) 檢查總匹配度是否滿足閾值條件，如果滿足就可以匹配，否則為不可匹配。,復合條件的模糊匹配,模糊推理中的沖突消解,1. 按匹

54、配度大小排序 2. 按加權平均值排序(把兩個模糊概念的匹配度問題轉換為一個對另一個的隸屬度) 例如，設U=u1,u2,u3,u4,u5, A=0.9/u1+0.6/u2+0.4/u3 B=0.6/u2+0.8/u3+0.5/u4 C=0.5/u3+0.8/u4+1/u5 D=0.8/u1+0.5/u2+0.1/u3 并設有如下模糊知識： R1:IFx is A THEN y is H1 R2:IFx is B THEN y is H2 R3:IFx is C THEN y is H3 用戶提供的初始證據(jù)為： E: x is D,match(A,D)=D(u1)/A(u1)+D(u2)/A(u2

55、)+D(u3)/A(u3) =0.8/0.9+0.5/0.6+0.1/0.4 同理可得： match(B,D)=0.8/0+0.5/0.6+0.1/0.8 match(C,D)=0.8/0+0.5/0+0.1/0.5 以上D與A、B、C的匹配度用模糊集形式表示。 下面求匹配度的加權平均值AV： AV(match(A,D)=(0.80.9+0.50.6+0.10.4)/(0.9+0.6+0.4)=0.56 同理可得： AV(match(B,D)=0.27 AV(match(C,D)=0.1 于是得到： AV(match(A,D)AV(match(B,D)AV(match(C,D) 所以R1是當前

56、首先被選用的知識。,3. 按廣義順序關系排序 由上例可得： match(A,D)=0.8/0.9+0.5/0.6+0.1/0.4 match(B,D)=0.8/0+0.5/0.6+0.1/0.8 match(C,D)=0.8/0+0.5/0+0.1/0.5 下面以match(A,D)與match(B,D)為例說明廣義順序排序的方法： 首先用match(B,D)的每一項分別與match(A,D)的每一項進行比較。比較時D(ui)與D(uj)中取其小者， A(ui)與B(uj)按如下規(guī)則取值：若A(ui)B(uj)則取“1”；若A(ui)0 ，則就認為match(A,D)優(yōu)于match(B,D)

57、，記為match(A,D) match(B,D) 。,按這種方法，對match(A,D)與match(B,D)可以得到： 0.8/1+0.5/1+0.1/1+0.5/1+0.5/1+0.1/0+0.1/1+0.1/0+0.1/0 =0.8/1+0.1/0 由于1=0.80=0.1，所以得到： match(A,D) match(B,D) 同理可得： match(A,D) match(C,D) match(B,D) match(C,D) 最后得到： match(A,D) match(B,D)match(C,D) 由此可知R1應該是首先被選用的知識。,4.6.4 模糊推理的基本模式,1. 模糊假言推理 知識：IF x is A THEN y is B 證據(jù)：x is A - 結論：y is B 對于復合條件有： 知識：IF x1 is A1 AND x2 is A2 ANDAND xn is An THEN y is B 證據(jù)： x1 is A1 ， x2 is A2 ， ， xn is An - 結論： y is B,2. 模糊拒取式推理 知識：IF x is A THEN y is B 證據(jù)：y is B - 結