證據(jù)理論演示文稿課件

1、證據(jù)理論演示文稿課件證據(jù)理論演示文稿課件2022/9/142 證據(jù)理論 (Theory of Evidence)也稱為D-S(Dempster-Shafer)理論。 證據(jù)理論(D-S理論)最早是基于德姆斯特(A.P.Dempster)所做的工作，他試圖用一個概率范圍而不是單個的概率值去模擬不確定性。證據(jù)理論2022/9/104 證據(jù)理論 (Theo 1、證據(jù)理論的誕生和形成 誕生：源于20世紀(jì)60年代美國哈佛大學(xué)數(shù)學(xué)家A. P. Dempster在利用上、下限概率來解決多值映射問題方面的研究工作。自1967年起連續(xù)發(fā)表了一系列論文，標(biāo)志著證據(jù)理論的正式誕生。 形成：Dempster的學(xué)生G.

2、Shafer對證據(jù)理論做了進一步的發(fā)展，引入信任函數(shù)概念，形成了一套基于“證據(jù)”和“組合”來處理不確定性推理問題的數(shù)學(xué)方法，并于1976年出版了證據(jù)的數(shù)學(xué)理論(A Mathematical Theory of Evidence)，這標(biāo)志著證據(jù)理論正式成為一種處理不確定性問題的完整理論。 1、證據(jù)理論的誕生和形成2022/9/144 莎弗(G.Shafer)進一步拓展了Dempster的工作，這一拓展稱為證據(jù)推理(Evidential Reasoning)，用于處理不確定性、不精確以及間或不準(zhǔn)確的信息。 由于證據(jù)理論將概率論中的單點賦值擴展為集合賦值，弱化了相應(yīng)的公理系統(tǒng)，滿足了比概率更弱的要求

3、，因此可看作一種廣義概率論。證據(jù)理論2022/9/106 莎弗(G.Shaf 證據(jù)理論的發(fā)展簡況 2、證據(jù)理論的名稱 證據(jù)理論(Evidential Theory) Dempster-Shafer理論 Dempster-Shafer證據(jù)理論 DS (或D-S)理論其它叫法： Dempster規(guī)則 Dempster合成規(guī)則 Dempster證據(jù)合成規(guī)則 證據(jù)理論的發(fā)展簡況 3、證據(jù)理論的核心、優(yōu)點及適用領(lǐng)域 核心：Dempster合成規(guī)則，這是Dempster在研究統(tǒng)計問題時首先提出的，隨后Shafer把它推廣到更為一般的情形。 優(yōu)點：由于在證據(jù)理論中需要的先驗數(shù)據(jù)比概率推理理論中的更為直觀、更

4、容易獲得，再加上Dempster合成公式可以綜合不同專家或數(shù)據(jù)源的知識或數(shù)據(jù)，這使得證據(jù)理論在專家系統(tǒng)、信息融合等領(lǐng)域中得到了廣泛應(yīng)用。 適用領(lǐng)域：信息融合、專家系統(tǒng)、情報分析、法律案件分析、多屬性決策分析，等等。 3、證據(jù)理論的核心、優(yōu)點及適用領(lǐng)域 4、證據(jù)理論的局限性 要求證據(jù)必須是獨立的，而這有時不易滿足 證據(jù)合成規(guī)則沒有非常堅固的理論支持，其合理性和有效性還存在較大的爭議 計算上存在著潛在的指數(shù)爆炸問題 4、證據(jù)理論的局限性 在證據(jù)理論中，引入了信任函數(shù)來度量不確定性，并引用似然函數(shù)來處理由于“不知道”引起的不確定性，并且不必事先給出知識的先驗概率，與主觀Bayes方法相比，具有較大的

5、靈活性。因此，證據(jù)理論得到了廣泛的應(yīng)用。 同時，可信度可以看作是證據(jù)理論的一個特例，證據(jù)理論給了可信度一個理論性的基礎(chǔ)。證據(jù)理論2022/9/148 在證據(jù)理論中，引入了信任函數(shù)來度量不確定性，并引用 證據(jù)的不確定性 在D-S理論中，可以分別用信任函數(shù)、似然函數(shù)及類概率函數(shù)來描述知識的精確信任度、不可駁斥信任度及估計信任度，即可以從各個不同角度刻畫命題的不確定性。 D-S理論采用集合來表示命題，先建立命題與集合之間的一一對應(yīng)關(guān)系，把命題的不確定性問題轉(zhuǎn)化為集合的不確定性問題。2022/9/149 證據(jù)的不確定性 在D-S理論中， 設(shè)為變量x的所有可能取值的有限集合 (亦稱樣本空間)，且中的每個

6、元素都相互獨立，則由的所有子集構(gòu)成的集合稱為冪集，記為2 。 當(dāng)中的元素個數(shù)為N時，則其冪集的元素個數(shù)為2N，且其中的每一個元素A都對應(yīng)于一個關(guān)于x的命題，稱該命題為“x的值在A中”。 證據(jù)的不確定性2022/9/1410 設(shè)為變量x的所有可能取值的有限集合 如，用x代表所看到的顏色，=紅，黃，藍，則A=紅表示“x是紅色”； 若A=紅，藍，則表示“x或者是紅色，或者是藍色”。 證據(jù)的不確定性2022/9/1411 如，用x代表所看到的顏色，=紅，黃，藍， l.概率分配函數(shù) 定義 設(shè)函數(shù)m: 20,1，且滿足 則稱m是2上的概率分配函數(shù)，m(A)稱為A的基本概率數(shù)。m(A)表示依據(jù)當(dāng)前的環(huán)境對假

7、設(shè)集A的信任程度。2022/9/1412l.概率分配函數(shù) 定義 設(shè)函數(shù)m: 對于上面給出的有限集=紅，黃，藍，若定義2上的一個基本函數(shù)m: m(,紅,黃,藍,紅,黃,紅,藍,黃,藍,紅,黃,藍) =0,0.3,0,0.1,0.2,0.2,0.1,0.1其中，0,0.3,0,0.1,0.2,0.2,0.1,0.1分別是冪集中各個子集的基本概率數(shù)。顯然m滿足概率分配函數(shù)的定義。例子說明2022/9/1413 對于上面給出的有限集=紅，黃，藍，若定義2 （1）概率分配函數(shù)的作用是把的任意一個子集都映射為0,1上的一個數(shù)m(A)。 當(dāng)A包含于且A由單個元素組成時，m(A)表示對A的精確信任度； 當(dāng)A包

8、含于、A,且A由多個元素組成時，m(A)也表示對A的精確信任度，但卻不知道這部分信任度該分給A中哪些元素； 當(dāng)A=時，則m(A)是對的各個子集進行信任分配后剩下的部分，它表示不知道該如何對它進行分配。對概率分配函數(shù)的幾點說明2022/9/1414 （1）概率分配函數(shù)的作用是把的任意一個子集都映射為 以=紅,黃,藍為例說明。 當(dāng)A=紅時，由于m(A)=0.3，它表示對命題 “x是紅色”的精確信任度為0.3。 當(dāng)A=紅，黃時，由于m(A)=0.2，它表示對命題“x或者是紅色，或者是黃色”的精確信任度為0.2，卻不知道該把這0.2分給紅還是分給黃。 當(dāng)A=紅，黃，藍時，由于m(A)=0.2，表示不知

9、道該對這0.2如何分配，但它不屬于紅，就一定屬于黃或藍，只是基于現(xiàn)有的知識，還不知道該如何分配而已。 例如2022/9/1415 以=紅,黃,藍為例說明。例如2022/9/ （2）m 是 2上而非上的概率分布，所以基本概率分配函數(shù)不是概率，它們不必相等，而且m(A)l-m(A)。事實上 m(紅)+m(黃)+m(藍) =0.3+0+0.1=0.41。概率分配函數(shù)的幾點說明2022/9/1416 （2）m 是 2上而非上的概率分布，所以基本概率2.信任函數(shù) 定義 信任函數(shù) (Belief Function) Bel: 2 0,1對任意的 有, Bel(A)表示當(dāng)前環(huán)境下，對假設(shè)集A的信任程度，其值

10、為A的所有子集的基本概率之和，表示對A的總的信任度。2022/9/14172.信任函數(shù) 定義 信任函數(shù) (Belief 以=紅,黃,藍為例說明。 Bel(紅,黃) =m(紅)+m(黃)+m(紅，黃) =0.3+0+0.2=0.5。 當(dāng)A為單一元素組成的集合時,Bel(A)=m(A)。 如果命題“x在B中”成立，必帶有命題“x在A中”成立。Bel(A)函數(shù)又稱為下限函數(shù)。例如2022/9/1418 以=紅,黃,藍為例說明。例如2022/3.似然函數(shù) 定義 似然函數(shù) (Plausibility Function)對任意的 有: Pl(A)=1-Bel(A)其中，A=-A。 似然函數(shù)又稱為不可駁斥函

11、數(shù)或上限函數(shù)。由于Bel(A)表示對A為真的信任度，Bel(A)表示對A的信任度，即A為假的信任度，因此，Pl(A)表示對A為非假的信任度。2022/9/14193.似然函數(shù) 定義 似然函數(shù) (Plausibili 以=紅,黃,藍為例說明。 Pl(紅)=1-Bel(紅) =1-Bel(黃,藍) = 1-(m(黃)+m(藍)+m(黃,藍) =1-(0+0.1+0.1)=0.8這里0.8是“紅”為非假的信任度。 由于“紅”為真的精確信任度為0.3，而剩下的0.8-0.3=0.5，則是知道非假，但卻不能肯定為真的那部分。例如2022/9/1420 以=紅,黃,藍為例說明。例如2022/9/推論該式可

12、推廣為可見，2022/9/1421推論該式可推廣為可見，2022/9/1023 因此命題“x在A中”的似然性，由與命題“x在B中”有關(guān)的m值確定，其中命題“x在B中”并不會使得命題“x不在A中”成立。 所以一個事件的似然性是建立在對其相反事件不信任的基礎(chǔ)上的。 推論2022/9/1422 因此命題“x在A中”的似然性，由與命題“x在B中(1) Bel()=0，Bel()=l， Pl()=O， Pl()=1.(2) 如果 , 則 Bel(A)Bel(B),Pl(A)Pl(B)。(3) , Pl(A)Bel(A)。 , Bel(A)+Bel(A)l， Pl(A)+Pl(A)1.信任函數(shù)和似然函數(shù)有

13、如下的性質(zhì)2022/9/1423(1) Bel()=0，Bel()=l，信任函數(shù)和似然函 由于Bel(A)和Pl(A)分別表示A為真的信任度和A為非假的信任度，因此，可分別稱Bel(A)和Pl(A)為對A信任程度的下限和上限，記為 A(Bel(A), Pl(A) Pl(A)-Bel(A)表示既不信任A，也不信任A的程度，即對于A是真是假不知道的程度。下限上限信任區(qū)間2022/9/1424 由于Bel(A)和Pl(A)分別表示如，在前面的例子中，曾求過Bel(紅)=0.3，Pl(紅)=0.8，因此有 紅（0.3，0.8）它表示對紅的精確信任度為0.3，不可駁斥部分為0.8，肯定不是紅的為0.2。

14、信任區(qū)間2022/9/1425如，在前面的例子中，曾求過Bel(紅)=0.3，Pl(4.假設(shè)集A的類概率函數(shù)f(A) 其中|A|、|分別表示A和中包含元素的個數(shù)。 類概率函數(shù)f(A)也可以用來度量證據(jù)A的不確定性。 2022/9/14264.假設(shè)集A的類概率函數(shù)f(A) 其中|A|、|分別表示f(A)有如下的性質(zhì) (1)(2)(3) Bel(A)f(A)Pl(A), for A (4) f(A)=1-f(A),for A 證據(jù)E的不確定性可以用類概率函數(shù)f(E)表示，原始證據(jù)的f(E)應(yīng)由用戶給出,作為中間結(jié)果的證據(jù)可以由下面的不確定性傳遞算法確定。 2022/9/1427f(A)有如下的性質(zhì)

15、 (1) 證據(jù)E的不確定性可以用 證據(jù)的組合函數(shù) 在實際問題中，對于相同的證據(jù)，由于來源不同，可能會得到不同的概率分配函數(shù)。例如，考慮=紅，黃，假設(shè)從不同知識源得到的概率分配函數(shù)分別為: m1(,紅,黃,紅,黃)=(0,0.4,0.5,0.1) m2(,紅,黃,紅,黃)=(0,0.6,0.2,0.2) 在這種情況下，需要對它們進行組合。 2022/9/1428 證據(jù)的組合函數(shù) 在實際問題中，對于相同的證定義 設(shè)m1和m2是兩個不同的概率分配函數(shù)，則其正交和m= m1m2滿足其中:正交和概念2022/9/1429定義 設(shè)m1和m2是兩個不同的概率分配函數(shù)，則其正交和m=如果KO，則正交和m也是一

16、個概率分配函數(shù)；如果K=0，則不存在正交和m，稱m1與m2矛盾。注意2022/9/1430如果KO，則正交和m也是一個概率分配函數(shù)；注意2022/9設(shè)=a,b，且從不同知識源得到的概率分配函數(shù)分別為 m1(,a,b,a,b)=(0,0.3,0.5,0.2) m2(,a,b,a,b)=(0,0.6,0.3,0.1)求正交和m=m1m2。 例32022/9/1431設(shè)=a,b，且從不同知識源得到的概率分配函數(shù)分別為例3解:先求K再求m(,a,b,a,b)，由于 2022/9/1432解:先求K再求m(,a,b,a,b)，由于 2同理可得: m(b)=0.43 ， m(a,b)=0.03 故有 m(

17、,a,b,a,b) =(0，0.54， 0.43，0.03) 2022/9/1433同理可得:2022/9/1035 規(guī)則的不確定性 具有不確定性的推理規(guī)則可表示為: If E Then H , CF 其中，H為假設(shè)，E為支持H成立的假設(shè)集，它們是命題的邏輯組合。CF為可信度因子。 H可表示為:H=a1,a2, am, ai (i=l,2,m)，H為假設(shè)集合的子集。 2022/9/1434 規(guī)則的不確定性 具有不確定性 CF=c1,c2, cm，ci用來描述前提E成立時ai的可信度。CF應(yīng)滿足如下條件: 規(guī)則的不確定性2022/9/1435 CF=c1,c2, cm，ci用來描述前提E成定義

18、對于不確定性規(guī)則: If E Then H ，CF定義: m(ai)=f(E)ci (i=l,2,m)或表示為 m(a1,a2,am) =(f(E)c1, f(E)c2, f(E)cm) 規(guī)則的不確定性2022/9/1436定義 對于不確定性規(guī)則: 規(guī)則的不確定規(guī)定:而對于的所有其他子集H，均有:m(H)=0。當(dāng)H為的真子集時，有:進一步可以計算Pl(H)和f(H)。2022/9/1437規(guī)定:2022/9/1039 不確定性的組合當(dāng)規(guī)則的前提(證據(jù))E是多個命題的合取或析取時，定義:2022/9/1438 不確定性的組合當(dāng)規(guī)則的前提(證據(jù))E是多個命當(dāng)有多條規(guī)則支持同一結(jié)論時，如果H=a1,

19、a2, an，則: If E1 Then H，CF1 (CF1=c11,c12,c1n) If E2 Then H，CF2 (CF2=c21,c22,c2n) If Em Then H，CFm (CFm=cm1,cm2,cmn) 不確定性的組合2022/9/1439當(dāng)有多條規(guī)則支持同一結(jié)論時，如果H=a1,a2, an 如果這些規(guī)則相互獨立地支持結(jié)論H的成立，可以先計算 mi(a1,a2,an)=( f(Ei)ci1, f(Ei)ci2, f(Ei)cim) (i=l,2,m) 然后根據(jù)前面介紹的求正交和的方法，對這些mi求正交和，以組合所有規(guī)則對結(jié)論H的支持。一旦累加的正交和m(H)計算出來

20、，就可以計算Bel(H)、Pl(H)、f(H)。 不確定性的組合2022/9/1440 如果這些規(guī)則相互獨立地支持結(jié)論H的成立，可以先計有如下的推理規(guī)則：R1: If E1(E2E3) Then A1=a11,a12,a13 CF1=0.2，0.3，0.4R2: If E4(E5E6) Then A2=a21 CF2=0.7R3: If A1 Then A=a1,a2 CF3=0.4，0.5R4: If A2 Then A=a1,a2 CF4=0.4，0.4 例2022/9/1441有如下的推理規(guī)則：例2022/9/1043這些規(guī)則形成如圖所示的推理網(wǎng)絡(luò)。原始數(shù)據(jù)的概率在系統(tǒng)中己經(jīng)給出: f(

21、E1)=0.5, f(E2)=0.7, f(E3)=0.9, f(E4)=0.9, f(E5)=0.8, f(E6)=0.7.假設(shè)|=10，現(xiàn)在需要求出A的確定性f(A)。 2022/9/1442這些規(guī)則形成如圖所示的推理網(wǎng)絡(luò)。假設(shè)|=10，現(xiàn)在需要求解: 第一步，求A1的確定性。2022/9/1443解: 第一步，求A1的確定性。2022/9/1045第二步 ,求A2的確定性。2022/9/1444第二步 ,求A2的確定性。2022/9/1046第三步,求A的確定性。根據(jù)R3和R4,有:m3(a1,a2)=(0.740.4,0.740.5)=(0.30,0.37)m4(a1,a2)=(0.6

22、0.4,0.60.4)=(0.24,0.24)m3()=1-( m3(a1)+m3(a2) =1-(0.30+0.37)=0.33m4()=1-( m4(a1)+m4(a2) =1-(0.24+0.24)=0.522022/9/1445第三步,求A的確定性。根據(jù)R3和R4,有:2022/9/10由正交和公式得到 :2022/9/1446由正交和公式得到 :2022/9/1048則有 : 于是 :Bel(A)=m(a1)+m(a2)=0.37+0.41=0.78Pl(A)=1-Bel(A)=1-0=1f(A)= Bel(A)+(|A|/|)(Pl(A)- Bel(A) =0.78+2/10(1-

23、0.78) =0.822022/9/1447則有 : 于是 :2022/9/1049證據(jù)理論的優(yōu)點在于能夠滿足比概率論更弱的公理系統(tǒng)，可以區(qū)分不知道和不確定的情況，可以依賴證據(jù)的積累，不斷縮小假設(shè)的集合。證據(jù)理論的優(yōu)點：2022/9/1448證據(jù)理論的優(yōu)點在于能夠滿足比概率論更弱的公理系統(tǒng)，可以區(qū)分不證據(jù)理論最早是作為經(jīng)典概率理論的擴展而引入的,所以受到很多的批評；在證據(jù)理論中，證據(jù)的獨立性不易得到保證；基本概率分配函數(shù)要求給的值太多，計算傳遞關(guān)系復(fù)雜，隨著診斷問題可能答案的增加，證據(jù)理論的計算呈指數(shù)增長，傳遞關(guān)系復(fù)雜，比較難以實現(xiàn)。 證據(jù)理論的不足：2022/9/1449證據(jù)理論最早是作為經(jīng)

24、典概率理論的擴展而引入的,所以受到很多的http:/www.hds.utc.fr/tdenoeux/dokuwiki/doku.phphttp:/www.hds.utc.fr/tdenoeu “Zadeh悖論”：對證據(jù)理論的合成公式的合理性進行質(zhì)疑。 例子：利用Dempster證據(jù)合成規(guī)則對兩個目擊證人（W1, W2）判斷某宗“謀殺案” 的三個犯罪嫌疑人（Peter, Paul, Mary）中究竟誰是真正的兇手，得到的結(jié)果（認(rèn)定Paul是兇手）卻違背了人的常識推理結(jié)果，Zadeh認(rèn)為這樣的結(jié)果無法接受。m1()m2()m12()Peter0.990.000.00Paul0.010.011.00

25、Mary0.000.990.00 “Zadeh悖論”：對證據(jù)理論的合成公式的合理性進行質(zhì)疑m1()m2()m12()Peter0.990.000.00Paul0.010.011.00Mary0.000.990.00Dempster合成規(guī)則計算舉例 例1. “Zadeh悖論” ：某宗“謀殺案” 的三個犯罪嫌疑人組成了識別框架 =Peter, Paul, Mary ，目擊證人（W1, W2）分別給出下表所示的BPA?！疽蟆浚河嬎阕C人W1和W2提供證據(jù)的組合結(jié)果?！窘狻浚菏紫龋嬎銡w一化常數(shù)K。m1()m2()m12()Peter0.990.000.00其次，利用Dempster證據(jù)合成規(guī)則分別計

26、算Peter, Paul, Mary的組合BPA（即組合mass函數(shù)）。（1）關(guān)于Peter的組合mass函數(shù)（2）關(guān)于Paul的組合mass函數(shù)其次，利用Dempster證據(jù)合成規(guī)則分別計算Peter, （3）關(guān)于Mary的組合mass函數(shù)【說明】：對于這個簡單的實例而言，對于Peter, Paul, Mary的組合mass函數(shù)，再求信任函數(shù)、似然函數(shù)，可知：信任函數(shù)值似然函數(shù)值組合后的mass函數(shù)值即， Bel(Peter) = Pl(Peter) = m12(Peter) = 0 Bel(Paul) = Pl(Paul) = m12(Paul) = 1 Bel(Mary) = Pl(Ma

27、ry) = m12(Mary) = 0（3）關(guān)于Mary的組合mass函數(shù)【說明】：對于這個簡單的 例2. 若修改“Zadeh悖論” 表中的部分?jǐn)?shù)據(jù)，如下表所示。請重新計算證人W1和W2提供證據(jù)的組合結(jié)果。【解】：首先，計算歸一化常數(shù)K。m1()m2()m12()Peter0.9800.49Paul0.010.010.015Mary00.980.49 =Peter, Paul, Mary0.010.010.005 例2. 若修改“Zadeh悖論” 表中的部分?jǐn)?shù)據(jù)歸一化常數(shù)K的另一種計算法：歸一化常數(shù)K的另一種計算法：（1）計算關(guān)于Peter的組合mass函數(shù)（1）計算關(guān)于Peter的組合mass函數(shù)（2）計算關(guān)于Paul的組合mass函數(shù)（2）計算關(guān)于Paul的組合mass函數(shù)（3）計算關(guān)于Mary的組合mass函數(shù)（3）計算關(guān)于Mary的組合mass函數(shù)（4）計算關(guān)于 =Peter, Paul, Mary的組合mass函數(shù)此外，根