ch4-不確定性推理

1、不確定性推理 1不確定因素模糊性隨機(jī)性不可靠不知道 2不確定性推理定義從具有不確定性的證據(jù)出發(fā)，運(yùn)用不確定性的知識或規(guī)則庫中的知識，最終推出具有一定程度的不確定性，但卻合理的或近乎合理的結(jié)論的思維過程。3不確定性推理方法的分類模型方法：把不確定性證據(jù)和知識與某種度量標(biāo)準(zhǔn)對應(yīng)起來，給出更新結(jié)論不確定性的合適算法，構(gòu)成不確定性推理模型。數(shù)值方法：定量表示和處理不確定性。以模糊集理論為基礎(chǔ)的方法按這種方法，把所有條件中最小的可信度作為總條件的可信度。這種方法類似于當(dāng)把幾根繩子連接起來使用時，總的繩子強(qiáng)度與強(qiáng)度最差的繩子的相同。以概率為基礎(chǔ)的方法這種方法同樣賦予每個證據(jù)以可信度。但當(dāng)把單獨條件的可信度

2、結(jié)合起來求取總的可信度時，它取決于各可信度的乘積。非數(shù)值方法：邏輯法，多值邏輯和非單調(diào)邏輯4不確定性推理方法的分類控制方法：通過領(lǐng)域中引起不確定性的某些特征及控制策略，限制或減少不確定性系統(tǒng)產(chǎn)生的影響，沒有統(tǒng)一模型，效果依賴于控制策略。啟發(fā)式搜索相關(guān)性制導(dǎo)回溯5不確定性推理中的基本問題不確定性的表示證據(jù)知識不確定性的度量不確定性的推理計算不確定性的傳遞問題證據(jù)不確定性的合成問題：證據(jù)間的合成（與/或）結(jié)論不確定性的合成問題：兩個規(guī)則的合成6常用的不確定性推理方法 主觀貝葉斯(Bayes)可信度(確定性) 證據(jù)理論(DS)模糊邏輯推理 可能性理論缺省推理 非單調(diào)推理系統(tǒng) 7概率推理方法主觀Bay

3、es方法 R.O.Duda、P.E.Hart等人1976年在Bayes公式的基礎(chǔ)上經(jīng)適當(dāng)改進(jìn)提出了主觀Bayes方法;最早用于處理不確定性推理的方法之一;已在地礦勘探專家系統(tǒng)PROSPECTOR中得到了成功的應(yīng)用。 8概率推理方法主觀Bayes方法 Bayes公式 若有諸事件A1,A2,，An，彼此獨立，且B為事件A1A2An的子事件，P(Ai)0(i=1,2,n)，P(B)0，那么Bayes公式可表示為：式中， 為先驗概率； 為后驗概率。Bayes公式就是從先驗概率推導(dǎo)出后驗概率的公式。9概率推理方法主觀Bayes方法 為闡明主觀Bayes方法，先引入幾個概念：引入兩個數(shù)值(LS，LN)來作

4、度量LS 表現(xiàn)規(guī)則成立的充分性LN 表現(xiàn)規(guī)則成立的必要性這種表示既考慮了 A 的出現(xiàn)對 B 的支持，又考慮了 A 的不出現(xiàn)對 B 的影響。10對規(guī)則的主觀Bayes方法 對規(guī)則的不確定性度量:直接使用Bayes 公式來做度量時，在計算P(B|A)時需要已知P(A|B)，為避開這個困難，提出了主觀Bayes 方法。對規(guī)則AB的不確定性f(B,A)以(LS，LN)來描述。其中 11對規(guī)則的主觀Bayes方法先建立幾率函數(shù)， 定義為表示的是證據(jù)X的出現(xiàn)概率與不出現(xiàn)概率之比，顯然隨P(X)的加大O(X)也加大，而且當(dāng)P(x)=0時，有 O(x) 0 當(dāng)P(x)=1時，有 O(x) 于是，取值于0,1的

5、P(x)被放大為O(x)，取值為0, 。12對規(guī)則的主觀Bayes方法不難驗證O(B|A)=LSO(B)O(B|A)=LNO(B)由于 兩者相比得 這就是O(B|A)=LSO(B)同樣，也可得O(B|A)=LNO(B)13對規(guī)則的主觀Bayes方法由這兩個公式可看出，LS表示A真時，對B為真的影響程度，表示規(guī)則AB成立充分性。LN表示A假時，對B為真的影響程度，表示規(guī)則AB成立的必要性。14對規(guī)則的主觀Bayes方法幾個特殊值15對規(guī)則的主觀Bayes方法由LS，LN 的定義知，LS，LN均 0,而且LS，LN不是獨立取值的，只能出現(xiàn)LS1，LN1或LS1 或LSLN1。但不能出現(xiàn)兩者同時1或

6、同時1。在實際系統(tǒng)中，LS，LN的值是由專家憑經(jīng)驗給出的，而不是依LS，LN的定義來計算的。16對證據(jù)的主觀Bayes方法證據(jù)的不確定性度量 就以O(shè)(A)或P(A)表示證據(jù)A的不確定性，轉(zhuǎn)換公式是17主觀Bayes方法推理計算 （1） 當(dāng)A確定必出現(xiàn)時，可直接使用O(B|A)LSO(B)O(B|A)=LNO(B)以求得使用規(guī)則AB后，O(B)的更新值O(B/A),O(B/A)。若需要以概率表示，再由計算出P(B|A),P(B|A)。 18主觀Bayes方法推理計算 （2）當(dāng)A是不確定的，即P(A)1時，需作如下考慮。設(shè)A代表與A有關(guān)的所有觀察，對規(guī)則AB來說 Duda 1976年給出公式：P(

7、B|A)=P(B|A)P(A|A)+P(B|A)P(A|A)問題是當(dāng)P(B|A)，AB (LS，LN)以及P(B)已知時，如何更新P(B)或說尋求P(B|A) 。當(dāng)P(A|A)1時，證據(jù)A必然出現(xiàn)有下式成立：19主觀Bayes方法推理計算 證明：20主觀Bayes方法推理計算 當(dāng)P(A|A)=0時，證據(jù)A必然不出現(xiàn)經(jīng)同樣的推導(dǎo)得：21主觀Bayes方法推理計算 當(dāng)P(A|A)=P(A)時，也即觀察A對A無影響。有P(B|A)=P(B|A)P(A)+P(B|A)P(A) =P(BA)+P(BA) =P(B)這樣已可確定P(A|A)為0、P(A)、1時相應(yīng)的P(B|A)的值，便可得線性插值圖。 2

8、2主觀Bayes方法推理計算 線性插值圖23主觀Bayes方法推理計算 P(A|A)的其它取值下的P(B|A)，可通過線性插值圖求得。（3）P(A1A2|A)=minP(A1|A),P(A2|A) P(A1A2|A)=maxP(A1|A),P(A2|A)（4）若A1B, A2B而A1，A2相互獨立，對 A1，A2的有關(guān)觀察分別為A1，A2便有:24主觀Bayes方法推理計算 4.舉例1當(dāng)證據(jù)A1 ， A2 ， A3 ， A4必然發(fā)生后，看B的概率變化。已知B的先驗概率為0.03，而規(guī)則R1： A1 B LS=20 LN=1R2： A2 B LS=300 LN=1R3： A3B LS=75 LN

9、=1R4： A4 B LS=4 LN=1下面進(jìn)行計算。25主觀Bayes方法推理計算 （1）依P(B)0.03便得:（2）依R1，有O(B| A1)=LS O(B) =20(0.030927)=0.6185使用規(guī)則R1后，B1的概率從0.03上升到0.38226主觀Bayes方法推理計算 （3）依R2有O(B| A1 A2 )=300 O(B| A1 )=185.565由于 A2發(fā)生，使B的概率由0.328增到0.99464，對A3 ， A4 的發(fā)生可同樣計算。27主觀Bayes方法推理計算 舉例2當(dāng)證據(jù)A必然發(fā)生，已知B1的先驗證概率為0.03，而規(guī)則R1：A B1 LS=20 LN=1R2

10、：B1B2 LS=300 LN=0.0001又知P(B2)的先驗概率為0.01時，如何計算P(B2 |A)？問題是當(dāng)使用R2時，B1不是必然發(fā)生了，也是不確定的，這時需使用插值方法。28主觀Bayes方法推理計算 （1） 依A必發(fā)生，由R1得P(B1 |A)=0.382（2）但是使用規(guī)則R2時，B1并非確定地發(fā)生，因此要用插值法。 設(shè)P(B1 |A)1，這時依B1)29主觀Bayes方法推理計算 （3） 再設(shè)P(B1|A)P(B1)0.03，即A對B1無影響，P（B2）0.01，根據(jù)這兩個值可進(jìn)行插值計算，求得:見圖30主觀Bayes方法推理計算 P(B2 |A)=0.305131主觀Baye

11、s方法推理計算 總結(jié)主觀Bayes方法優(yōu)點：直觀，明了。問題：要求Bj個事件相互獨立（無關(guān)），實際上是不可能的。P(A/Bi)和P(Bi)難以計算。實際應(yīng)用中，為了避開這一點采用LS, LN的專家給定值。32可信度方法確定性方法可信度的不確定性表示一般通過對事實賦于一個介于0和1之間的系數(shù)來表示事實的不確定性。1代表完全確定0代表完全不確定。系數(shù)被稱為可信度也有一些專家系統(tǒng)，如MYCIN和EXPERT等，取可信度的范圍為-1到+1。 33可信度方法確定性方法證據(jù)的不確定性處理：當(dāng)規(guī)則具有一個以上的條件時，需要根據(jù)各條件的可信度來求得總條件部分的可信度。以概率為基礎(chǔ)的方法這種方法同樣賦予每個證據(jù)

12、以可信度。但當(dāng)把單獨條件的可信度結(jié)合起來求取總的可信度時，它取決于各可信度的乘積。 34可信度方法確定性方法知識的不確定性表示也叫規(guī)則的不確定性它表示當(dāng)規(guī)則的條件被完全滿足時，產(chǎn)生某種結(jié)論的不確定程度。它也是以賦予規(guī)則在0和1之間的系數(shù)的方法來表示的。例：有以下規(guī)則：如果啟動器發(fā)生刺耳的噪聲那么這個啟動器壞的可能性是0.8。該規(guī)則表示，如果“啟動器發(fā)生刺耳的噪聲”這事實完全肯定的可信度為1.0，那么得出“這個啟動器壞”的結(jié)論的可信度為0.8。35可信度方法確定性方法知識的不確定性處理如果規(guī)則的條件部分不完全確定，即可信度不為1時，求知識的可信度方法有兩種：(1)取結(jié)論可信度為條件可信度系數(shù)的乘

13、積。(2)按照某種概率論的解釋，我們假設(shè)規(guī)則的條件部分的可信度Cin和其結(jié)論部分的可信度Cout存在某種關(guān)系，這種關(guān)系可用來代表規(guī)則的不確定性。36可信度方法確定性方法 以產(chǎn)生式作為知識表示方法的專家系統(tǒng)MYCIN中，第一次使用了不確定性推理方法，給出了以確定性因子或稱可信度作為不確定性的度量。這種推理方法必須解決幾個方面的核心問題規(guī)則和證據(jù)的不確定性度量問題不確定性的傳播與更新問題。37可信度方法規(guī)則的表示 以產(chǎn)生式作為知識表示，給出了以確定性因子或稱可信度作為不確定性的度量。有規(guī)則A B，其可信度CF(B, A)定義如下：38可信度方法規(guī)則的表示CF(B,A)表示的意義：證據(jù)為真是相對于P

14、(B) = 1 - P(B)來說，A對B為真的支持程度，即A發(fā)生更支持B發(fā)生，此時 CF(B,A) 0。相對于P(B)來說，A對B為真的不支持程度。即A發(fā)生不支持B發(fā)生，此時 CF(B,A) 0。它總是滿足條件-1 CF(B,A) 1。39可信度方法規(guī)則的表示CF(B, A)的特殊值：CF(B, A) = 1， 前提真，結(jié)論必真CF(B, A) = -1， 前提真，結(jié)論必假CF(B, A) = 0 ， 前提真假與結(jié)論無關(guān)實際應(yīng)用中CF(B, A)的值由專家確定，并不是由P(B|A), P(B)計算得到的。注意：CF(B,A)表示的是增量P（B|A）P（B）對1P（B）或P（B）的比值，而不是絕

15、對量的比值。40可信度方法證據(jù)的表示證據(jù)A的可信度用CF( A)來表示，為了計算方便，規(guī)定：-1 CF( A) 1可信度CF( A)的如下特殊值的含義：CF( A) = 1， 前提肯定真CF(A) = -1， 前提肯定假CF(A) = 0， 對前提一無所知CF( A) 0， 表示A以CF( A)程度為真CF( A) 0， 表示A以CF( A)程度為假實際使用時，初始證據(jù)的CF值有專家根據(jù)經(jīng)驗提供，其它證據(jù)的CF通過規(guī)則進(jìn)行推理計算得到。41可信度方法不確定性的傳播與更新1）“與”的計算： A1 A2 BCF(A1 A2 ) = min CF(A1), CF(A2) 2）“或”的計算：A1 A2

16、 BCF(A1 A2 ) = max CF(A1), CF(A2) 3）“非”的計算：CF(A ) = CF(A) 4）由A， A B，求 CF(B)：CF(B) = max(0，CF(A)CF(B,A)42可信度方法不確定性的傳播與更新5）合成，由兩條規(guī)則求出再合并：由規(guī)則A1B可求得CF1（B），同時又有規(guī)則A2B，可求得CF2（B）。如何根據(jù)這兩條規(guī)則的產(chǎn)生的結(jié)果，計算其合成后的可信度CF（B）？先有：CF1(B)= max(0，CF(A1)CF(B,A1)CF2(B)= max(0，CF(A2)CF(B,A2)43可信度方法不確定性的傳播與更新CF1(B)和CF2(B)是同時發(fā)生的，即

17、可以是分別從兩條完全獨立的途徑得到的知識。44可信度方法不確定性的傳播與更新6）CF(B)的更新計算：已知證據(jù)A 的可信度CF（A），結(jié)論B的原有可信度CF（B），求A通過規(guī)則AB，作用到B后，B的可信度的更新值CF（B|A）。由于，證據(jù)A不是必然發(fā)生的，是具有一定可信度的，所以必須對可信度的情況進(jìn)行討論。45可信度方法不確定性的傳播與更新當(dāng)CF（A）=1時，即A必然發(fā)生時：46可信度方法不確定性的傳播與更新當(dāng)0CF（A）1時，即A可能發(fā)生時：由于A是否發(fā)生是不確定的，因此CF（B|A）一定比A必然發(fā)生時要小。此時取CF（A）* CF（B，A）代替上式中的規(guī)則可信度CF（B，A）即可。即更新后

18、的可信度公式為：47可信度方法不確定性的傳播與更新當(dāng)CF（A）0時，即A不可能發(fā)生時規(guī)則AB不使用，即認(rèn)為不可能發(fā)生的事件（A為假的事件）對結(jié)果B沒有影響。48可信度方法例題已知 R1：A1B1 CF（B1，A1）0.8 R2：A2B1 CF（B1，A2）0.5 R3：B1A3B2 CF（B2，B1A3）0.8 CF（A1）CF（A2）CF（A3）1； CF（B1）= CF（B2）=0計算更新 CF（B1）、CF（B2）49可信度方法例題解：依規(guī)則R1CF（B1|A1）CF（B1）CF（B1，A1）（1CF（B1）0.8即更新后CF（B1）0.8依規(guī)則R2CF（B1|A2）CF（B1）CF（B

19、1，A2）（1CF（B1）0.9更新后CF（B1）0.950可信度方法例題依R3，先計算CF（B1A3）min（CF（A3），CF（B1）0.9由于CF（B1A3）1，CF（B2| B1A3）= CF（B2）+ CF（B1A3）CF(B2，B1A3)（1-CF（B2）=0+0.90.8(1-0)=0.72答：更新后的可信度分別是：CF（B1）0.9，CF（B2）0.7232.swf51證據(jù)理論（D-S Theory） 證據(jù)理論由Dempster首先提出，并由他的學(xué)生Shafer發(fā)展起來，也稱D-S理論。在專家系統(tǒng)的不精確推理中已得到廣泛的應(yīng)用, 也用在模式識別系統(tǒng)中。證據(jù)理論中引入了信任函數(shù)，

20、它滿足概率論弱公理。在概率論中，當(dāng)先驗概率很難獲得，但又要被迫給出時，用證據(jù)理論能區(qū)分不確定性和不知道的差別。所以它比概率論更合適于專家系統(tǒng)推理方法。當(dāng)概率值已知時，證據(jù)理論就成了概率論。因此，概率論是證據(jù)理論的一個特例，有時也稱證據(jù)理論為廣義概率論。52證據(jù)理論（D-S Theory） 證據(jù)用集合來表示：如U中的每個元素代表一種疾病。討論一組疾病A發(fā)生的可能性時，A就變成了單元的集合。U內(nèi)元素間是互斥的，但Ai中元素間不是互斥的。針對醫(yī)療診斷問題， U就是所有可能疾?。僭O(shè)）的集合，診斷的結(jié)果必是U中確定的元素構(gòu)成的。A表示某一種（單元素）或某幾種疾病。醫(yī)生為了診斷所進(jìn)行的各種檢查就稱作證據(jù)

21、，有的證據(jù)支持的不只是一種疾病而是多種疾病，即構(gòu)成U的一子集A。 53證據(jù)理論（D-S Theory） 證據(jù)理論定義了多個函數(shù)值來描述證據(jù)及規(guī)則的不確定性概率分配函數(shù)M信任函數(shù)Bel似然函數(shù)Pl54證據(jù)理論：概率分配函數(shù)概率分配函數(shù)的作用是把D上的任意一個子集A( 2D)都映射為0,1上的一個數(shù)m(A) 。當(dāng)A對應(yīng)一個命題時, m(A) 就是對應(yīng)命題不確定性的度量.概率分配函數(shù)定義：設(shè)D為樣本空間，領(lǐng)域內(nèi)的命題都用D的子集表示，如果定義函數(shù)m (x)為集合2D到區(qū)間0,1的一個映射函數(shù)，即設(shè)m (x)為集合2D0,1的一個映射，且滿足如下條件：m() = 0 空的為零m(A) = 1 全空間的

22、和為1（ AD）稱m (x)為2D上的概率分配函數(shù).m(A)為命題A的基本概率數(shù)。m是在D的冪集2D 上定義的，取值范圍是0,1。55證據(jù)理論：概率分配函數(shù)概率分配函數(shù)設(shè)m (x)為集合2D0,1的一個映射，且滿足：m() = 0 空的為零m(A) = 1 全空間的和為1（ A2D ）m (x)為2D上的概率分配函數(shù).m(A)為命題A的基本概率數(shù)m是在D的冪集2D 上定義的，取值范圍是0,1?；靖怕屎瘮?shù)的物理意義是：若A屬于D，且不等于D，表示對A的精確信任度若A等于D，表示這個數(shù)不知如何分配.56證據(jù)理論：信任函數(shù)信任函數(shù)是對命題A的不確定性進(jìn)行度量。信任函數(shù)的定義設(shè)D為樣本空間， 2D為

23、D的所有子集表示的命題之集合， A是2D中的一個命題。如果定義函數(shù)Bel(A)為將集合2D映射到區(qū)間0,1上的函數(shù)，且滿足：對所有的 A 2D 稱Bel(A)為信任函數(shù)或稱下限函數(shù)。57證據(jù)理論：信任函數(shù)信任函數(shù)信任函數(shù)Bel：2D 0,1A的信任函數(shù)為：包含于A中的所有集合的概率分配函數(shù)值之和。根據(jù)定義有：Bel() m() = 0Bel(D)m(B) = 1（B屬于D）信任函數(shù)Bel類似于概率密度函數(shù)，表示A中所有子集的基本概率分配數(shù)值的和。表示對A為真的信任程度。58證據(jù)理論：似然函數(shù)似然函數(shù)定義：設(shè)有函數(shù)Pl(A)為將集合2D映射到區(qū)間0,1上的函數(shù)，即似然函數(shù)Pl：2D 0,1且滿足

24、：對所有的 A 2D 則稱Pl(A)為似然函數(shù)。意義：A的似然函數(shù)為Pl(A)：表示對A為非假的信任度程度。即對A不為假的信任程度。59證據(jù)理論：似然函數(shù)對A不為假的信任程度應(yīng)該大于對A為真的信任程度，即Bel(A) Pl(A) 根據(jù)定義有：0 Bel(A) Pl(A) 1，可見Bel是Pl的一部分。稱Bel(A)和Pl(A)是A的下限不確定性值和上限不確定性值。因此可用區(qū)間（Bel(A)，Pl(A)）來表示A的不確定性度量。60證據(jù)理論：類概率函數(shù)f1用類概率函數(shù)f1(A)來衡量A的不確定性，其定義如下：f1(A)= Bel(A) + |A|/|D|(Pl(A) - Bel(A)其中|A|、

25、|D|為集合內(nèi)元素的個數(shù)。有下列式子成立：f1()0f1(D)10f1(A)1，對A屬于D61證據(jù)理論：似然函數(shù)設(shè)函數(shù)f(Bel(A), Pl(A)，下列特殊值的含義f(1, 1) 表示A為真f(0, 0) 表示A為假f(0, 1) 表示對A一無所知f(1, 0) 不可能成立62證據(jù)理論：規(guī)則的不確定性度量設(shè)子集合A, B，其中 A = a1, a2, , al, B = b1, b2, , bk用相應(yīng)的向量 (c1, c2, , ck) 描述規(guī)則A B的不確定性度量，其中ci0, 1ik, 且cj1 1jk。63證據(jù)理論：推理計算1）“與”的計算： f1 (A1A2) = min f1 (A

26、1), f1 (A2)2）“或”的計算f1 (A1A2) = max f1 (A1), f1 (A2)3）“非”的計算f1(A ) = f1 (A )4）由f1 (A)， A B， (c1, c2, , ck)。求f1 (B)m(b1, b2, ,bk) =(f1 (A)c1, f1 (A)c2, , f1 (A)ck)m (D) = 1-f1 (A)ci, i = 1, , k64證據(jù)理論：推理計算5）證據(jù)的組合，m1, m2在D上的合成對于同樣的證據(jù)，由于來源不同，分別得到二個概率分配函數(shù)m1, m2。定義： m1, m2的正交和為 m = m1m2規(guī)定：m() = 0; m(A) = K

27、-1 m1(X)m2(Y), 當(dāng)XY = A其中:若K 0, K = 1 - m1(X)m2(Y), 當(dāng)XY = 或 K = m1(X)m2(Y), 當(dāng)XY 若K = 0,認(rèn)為m1, m2矛盾。沒有聯(lián)合基本概率分配函數(shù)。常數(shù)K是根據(jù)m1m2需對2D的所有元素的基本概率分配之和為1來確定的。65證據(jù)理論：推理計算例題已知：f1(A1) = 0.40 ,f1(A2)=0.50,|D| = 20. A1B=b1,b2,b3，(c1,c2,c3)=(0.1,0.2,0.3) A2B=b1,b2,b3，(c1,c2,c3)=(0.5,0.2,0.1)求：f1(B)解：（1） 先求：m1(b1,b2,b3)=(0.4*0.1,0.4*0.2,0.4*0.3) =(0.04,0.08,0.12);m1(U)=1- m1(b1)+m1(b2)+m1(b3)=0.76;66證據(jù)理論：推理計算例題m2(b1,b2,b3)=(0.5*0.5,0.5*0.2,0.5*0.1) =(0.