DS證據(jù)理論(000002)

1、浙江大學研究生浙江大學研究生人工智能人工智能課件課件徐從富徐從富(Congfu Xu) PhD, Associate Professor Email: Institute of Artificial Intelligence, College of Computer Science, Zhejiang University, Hangzhou 310027, P.R. ChinaMarch 10, 2002第一稿第一稿September 25, 2006第四次修改稿第四次修改稿第五章 D-S證據(jù)理論(Chapter5 D-S Evidential Theory )Outlinen本章的主要參考

2、文獻n證據(jù)理論的發(fā)展簡況n經(jīng)典證據(jù)理論n關于證據(jù)理論的理論模型解釋n證據(jù)理論的實現(xiàn)途徑證據(jù)理論的實現(xiàn)途徑n基于DS理論的不確定性推理n計算舉例計算舉例1 Dempster, A. P. Upper and lower probabilities induced by a multivalued mapping. Annals of Mathematical Statistics, 1967, 38(2): 325-339. 【提出證據(jù)理論的第一篇文獻】2 Dempster, A. P. Generalization of Bayesian Inference. Journal of the R

3、oyal Statistical Society. Series B 30, 1968:205-247.3 Shafer, G. A Mathematical Theory of Evidence. Princeton University Press, 1976. 【證據(jù)理論的第一本專著，標志其正式成為一門理論】4 Barnett, J. A. Computational methods for a mathematical theory of evidence. In: Proceedings of 7th International Joint Conference on Artific

4、ial Intelligence(IJCAI-81), Vancouver, B. C., Canada, Vol. II, 1981: 868-875. 【第一篇將證據(jù)理論引入AI領域的標志性論文】本章的主要參考文獻本章的主要參考文獻5 Zadeh, L. A. Review of Shafers a mathematical theory of evidence. AI Magazine, 1984, 5:81-83. 【對證據(jù)理論進行質(zhì)疑的經(jīng)典文獻之一】6 Shafer, G. Perspectives on the theory and practice of belief funct

5、ions. International Journal of Approximate Reasoning, 1990, 4: 323-362. 7 Shafer, G. Rejoinder to comments on “Perspectives on the theory and practice of belief functions”. International Journal of Approximate Reasoning, 1992, 6: 445-480. 8 Voorbraak, F. On the justification of Dempsters rule of com

6、bination. Artificial Intelligence, 1991, 48:171-197.9 Smets, P. The combination of evidence in the transferable model. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1990, 12(5): 447-458. 10 Smets, P, and Kennes, R. The transferable belief model. Artificial Intelligence, 1994, 66: 1

7、91-234. 本章的主要參考文獻本章的主要參考文獻（續(xù)（續(xù)1）11 Voobraak, F. A computationally efficient approximation of Dempster-Shafer theory. International Journal of Man-Machine Study, 1989, 30: 525-536. 12 Dubois, D, Prade, H. Consonant approximations of belief functions. International Journal of Approximate Reasoning, 19

8、90, 4: 279-283. 13 Tessem, B. Approximations for efficient computation in the theory of evidence. Artificial Intelligence, 1993, 61:315-329. 【注：文獻10-12均為證據(jù)理論近似計算方法】14 Simard, M. A., et al. Data fusion of multiple sensors attribute information for target identity estimation using a Dempster-Shafer ev

9、idential combination algorithm. In: Proceedings of SPIE-International Society for Optical Engineering, 1996, Vol.2759: 577-588. 【提出了一種實現(xiàn)證據(jù)理論的“修剪算法”】本章的主要參考文獻本章的主要參考文獻（續(xù)（續(xù)2）15 Josang, A. The consensus operator for combining beliefs. Artificial Intelligence, 2002, 141(1-2): 157-170. 16 Yang, Jian-Bo,

10、Xu, Dong-Ling. On the evidential reasoning algorithm for multiple attribute decision analysis under uncertainty. IEEE Transaction on Systems, Man, and Cybernetics Part A: Systems and Humans, 2002, 32(3): 289-304. 17 Yaghlane, B. B., et al. Belief function independence: I. The marginal case. Internat

11、ional Journal of Approximate Reasoning, 2002, 29(1): 47-70.18 Yaghlane, B. B., et al. Belief function independence: II. The conditional case. International Journal of Approximate Reasoning, 2002, 31: 31-75. 本章的主要參考文獻本章的主要參考文獻（續(xù)（續(xù)3）19 段新生. 證據(jù)理論與決策、人工智能證據(jù)理論與決策、人工智能. 中國人民大學出版社, 1993. 20 徐從富 等. Dempster

12、-Shafer證據(jù)推理方法理論與應用的綜述證據(jù)推理方法理論與應用的綜述. 模式識別與人工智能, 1999, 12(4): 424-430. 21 徐從富 等. 面向數(shù)據(jù)融合的面向數(shù)據(jù)融合的DS方法綜述方法綜述. 電子學報, 2001, 29(3): 393-396.22 徐從富 等. 解決證據(jù)推理中一類解決證據(jù)推理中一類“0絕對化絕對化”問題的方法問題的方法. 計算機科學, 2000, 27(5): 53-56. 23 李岳峰 等. 證據(jù)理論中的近似計算方法證據(jù)理論中的近似計算方法. 吉林大學自然科學學報, 1995, (1):28-32.24 劉大有 等. 廣義證據(jù)理論的解釋廣義證據(jù)理論的解

13、釋. 計算機學報, 1997, 20(2): 158-164.25 劉大有 等. 凸函數(shù)證據(jù)理論模型凸函數(shù)證據(jù)理論模型. 計算機研究與發(fā)展, 2000, 37(2): 175-181.本章的主要參考文獻本章的主要參考文獻（續(xù)（續(xù)4）26 楊瑩 等. 對一種基于證據(jù)理論的不確定性處理模型的重要擴充對一種基于證據(jù)理論的不確定性處理模型的重要擴充. 計算機學報, 1990, (10): 772-778. 27 劉大有 等. 一種簡化證據(jù)理論模型的研究一種簡化證據(jù)理論模型的研究. 計算機研究與發(fā)展, 1999, 36(2): 134-138.28 肖人彬 等. 相關證據(jù)合成方法的研究相關證據(jù)合成方法的

14、研究. 模式識別與人工智能, 1993, 6(3): 227-234. 29 孫全 等. 一種新的基于證據(jù)理論的合成公式一種新的基于證據(jù)理論的合成公式. 電子學報, 2000, 28(8): 117-119.30 曾成, 趙保軍, 何佩昆. 不完備框架下的證據(jù)組合方法不完備框架下的證據(jù)組合方法. 電子與信息學報, 2005, 27(7): 1043-1046. 31 王永慶. 人工智能原理與方法人工智能原理與方法. 西安交通大學出版社, 1998. pp. 185-197. （第5章第5.5節(jié) “證據(jù)理論”）本章的主要參考文獻本章的主要參考文獻（續(xù)（續(xù)5）5.1 5.1 證據(jù)理論的發(fā)展簡況證據(jù)

15、理論的發(fā)展簡況 1 1、證據(jù)理論的名稱、證據(jù)理論的名稱 證據(jù)理論(Evidential Theory) Dempster-Shafer理論 Dempster-Shafer證據(jù)理論 DS (或D-S)理論其它叫法： Dempster規(guī)則 Dempster合成規(guī)則 Dempster證據(jù)合成規(guī)則 2 2、證據(jù)理論的誕生和形成、證據(jù)理論的誕生和形成 誕生誕生：源于20世紀60年代美國哈佛大學數(shù)學家A. P. Dempster在利用上、下限概率來解決多值映射問題利用上、下限概率來解決多值映射問題方面的研究工作。自1967年起連續(xù)發(fā)表了一系列論文，標志著證據(jù)理論的正式誕生。 形成形成：Dempster的學

16、生G. Shafer對證據(jù)理論做了進一步的發(fā)展，引入信任函數(shù)信任函數(shù)概念，形成了一套基于“證據(jù)”和“組合”來處理不確定性推理問題的數(shù)學方法，并于1976年出版了證據(jù)的數(shù)學理論(A Mathematical Theory of Evidence)，這標志著證據(jù)理論正式成為一種處理不確定性問題的完整理論。 3 3、證據(jù)理論的核心、優(yōu)點及適用領域、證據(jù)理論的核心、優(yōu)點及適用領域 核心核心：Dempster合成規(guī)則合成規(guī)則，這是Dempster在研究統(tǒng)計問題時首先提出的，隨后Shafer把它推廣到更為一般的情形。 優(yōu)點優(yōu)點：由于在證據(jù)理論中需要的先驗數(shù)據(jù)比概率推理理論中的更為直觀、更容易獲得，再加上D

17、empster合成公式可以綜合不同專家或數(shù)據(jù)源的知識或數(shù)據(jù)，這使得證據(jù)理論在專家系統(tǒng)、信息融合專家系統(tǒng)、信息融合等領域中得到了廣泛應用。 適用領域適用領域：信息融合、專家系統(tǒng)、情報分析、法律案件分析、多屬性決策分析，等等。 4 4、證據(jù)理論的局限性、證據(jù)理論的局限性 要求證據(jù)必須是獨立的證據(jù)必須是獨立的，而這有時不易滿足 證據(jù)合成規(guī)則沒有非常堅固的理論支持，其合理合理性和有效性還存在較大的爭議性和有效性還存在較大的爭議 計算上存在著潛在的指數(shù)爆炸問題指數(shù)爆炸問題 5 5、證據(jù)理論的發(fā)展概況、證據(jù)理論的發(fā)展概況 “Zadeh悖論悖論”：對證據(jù)理論的合成公式的合理性進行質(zhì)疑。 例子例子：利用Dem

18、pster證據(jù)合成規(guī)則對兩個目擊證人（W1, W2）判斷某宗“謀殺案” 的三個犯罪嫌疑人（Peter, Paul, Mary）中究竟誰是真正的兇手，得到的結果（認定Paul是兇手）卻違背了人的常識推理結果，Zadeh認為這樣的結果無法接受。m1()m2()Peter0.990.00Paul0.010.01Mary0.000.99 專家系統(tǒng)專家系統(tǒng)MYCIN的主要開發(fā)者之一的主要開發(fā)者之一Shortliffe：對證據(jù)理論的理論模型解釋和算法實現(xiàn)進行了研究。 AI專家專家Dubois & Prade ：指出證據(jù)理論中的信任函數(shù)（Belief function）是一種模糊測度，以集合論的觀點研究證據(jù)

19、的并、交、補和包含等問題。 Smets等人等人：將信任函數(shù)推廣到識別框架的所有模糊子集上，提出Pignistic概率和可傳遞信度模型（TBM）。 粗糙集理論的創(chuàng)始人粗糙集理論的創(chuàng)始人Pawlak：認為粗糙集理論使得無限框架上的證據(jù)處理向有限框架上的證據(jù)處理的近似轉化成為可能。證據(jù)理論的發(fā)展概況（證據(jù)理論的發(fā)展概況（續(xù)續(xù)1） 為了避免證據(jù)組合爆炸，提高證據(jù)合成的效率：為了避免證據(jù)組合爆炸，提高證據(jù)合成的效率： Voorbraak：提出一種Dempster證據(jù)合成公式的Bayes近似方法，使得焦元個數(shù)小于等于識別框架中元素的個數(shù)。 Dubois & Prade ：提出一種 “和諧近似”（Conso

20、nant approximation），即用和諧函數(shù)來代替原來的信任函數(shù)。 Tessem：提出了一種稱為(k, l, x)近似方法。 Yen等人等人： 將模糊集引入證據(jù)理論。 Yen, J. Generalizing the Dempster-Shafer theory to fuzzy sets. IEEE Trans. on Systems, Man, and Cybernetics, 1990, 20(3): 559-570.】證據(jù)理論的發(fā)展概況（證據(jù)理論的發(fā)展概況（續(xù)續(xù)2） 6 6、證據(jù)理論在中國的發(fā)展情況、證據(jù)理論在中國的發(fā)展情況 段新生：段新生：在1993年出版了一本專門論述證據(jù)理

21、論的專著證據(jù)理論與決策、人工智能?！咀ⅲ河捎诖藭霭鏁r間較早，故其內(nèi)容不是很新，未能反映證據(jù)理論及其應用方面的最新成果】 劉大有等人：劉大有等人：國內(nèi)較早研究證據(jù)理論的專家，并發(fā)表了一系列的論文，主要集中研究該理論的模型解釋、理論擴展、近似實現(xiàn)等問題。 肖人彬等人：肖人彬等人：對證據(jù)的相關性及相關證據(jù)的組合問題進行了研究。 蘇運霖、管紀文等人：蘇運霖、管紀文等人：對證據(jù)理論與粗糙集理論進行了比較研究。 【蘇運霖, 管紀文等. 證據(jù)論與約集論.軟件學報,1999, 10(3): 277-282. 注：此處的“約集”即為“粗糙集”(Rough set)】 曾成等人：曾成等人：研究了不完備的識別框架

22、下的證據(jù)合成問題，并提出相應的證據(jù)合成公式。 顧偉康等人：顧偉康等人：對證據(jù)合成公式進行擴展，提出一種改進的證據(jù)合成公式。 徐從富等人：徐從富等人：1999-2001總結國內(nèi)外關于證據(jù)理論及其應用的代表性文獻，先后發(fā)表2篇關于證據(jù)理論及其應用的綜述文章。 證據(jù)理論在中國的發(fā)展情況（證據(jù)理論在中國的發(fā)展情況（續(xù)續(xù)）5.2 5.2 經(jīng)典證據(jù)理論經(jīng)典證據(jù)理論 1 1、證據(jù)理論的主要特點、證據(jù)理論的主要特點 滿足比Bayes概率理論更弱的條件，即不必滿足概不必滿足概率可加性率可加性。 具有直接表達直接表達“不確定不確定”和和“不知道不知道”的能力，這些信息表示在mass函數(shù)中，并在證據(jù)合成過程中保留了

23、這些信息。 證據(jù)理論不但允許人們將信度賦予假設空間的單個元素，而且還能賦予它的子集，這很象人類在各級抽象層很象人類在各級抽象層次上的證據(jù)收集過程次上的證據(jù)收集過程。 2 2、基本概念、基本概念 設是一個識別框架識別框架，或稱假設空間假設空間。 （1）基本概率分配 基本概率分配：Basic Probability Assignment，簡稱BPA。在識別框架上的BPA是一個2 0, 1的函數(shù)m，稱為mass函數(shù)函數(shù)。并且滿足 m() = 0 且 ( )1Am A其中，使得m(A)0的A稱為焦元焦元(Focal elements)。 （2）信任函數(shù) 信任函數(shù)也稱信度函數(shù)信度函數(shù)（Belief fu

24、nction）。 在識別框架上基于BPA m的信任函數(shù)定義為：( )( )BABel Am B （3）似然函數(shù) 似然函數(shù)也稱似然度函數(shù)似然度函數(shù) (Plausibility function) 。 在識別框架上基于BPA m的似然函數(shù)定義為：( )( )BAPl Am B 在證據(jù)理論中，對于識別框架 中的某個假設A，根據(jù)基本概率分配BPA分別計算出關于該假設的信任函信任函數(shù)數(shù)Bel(A)和似然函數(shù)似然函數(shù)Pl(A)組成信任區(qū)間信任區(qū)間Bel(A), Pl(A)，用以表示對某個假設的確認程度。（4）信任區(qū)間“Teach us to number our days aright, that we

25、may gain a heart of wisdom.”From Psalms 90:12 3、Dempster合成規(guī)則合成規(guī)則 Dempster合成規(guī)則（Dempsters combinational rule）也稱證據(jù)合成公式證據(jù)合成公式，其定義如下： 對于A，上的兩個mass函數(shù)m1, m2的Dempster合成規(guī)則合成規(guī)則為：12121( )( )()BCAmmAm BmCK其中， K為歸一化常數(shù)歸一化常數(shù)1212( )()1( )()BCBCKm BmCm BmC 對于A，識別框架上的有限個mass函數(shù)m1, m2, ., mn的Dempster合成規(guī)則合成規(guī)則為：121211221

26、()( )()()()nnnnAAAAmmmAm Am Am AK其中，1111221122()()()1()()()nnnnAAnnAAKmAmAmAmAmAmAn個個mass函數(shù)的函數(shù)的Dempster合成規(guī)則合成規(guī)則m1()m2()m12()Peter0.990.000.00Paul0.010.011.00Mary0.000.990.00 4、Dempster合成規(guī)則計算舉例合成規(guī)則計算舉例 例1. “Zadeh悖論悖論” ：某宗“謀殺案” 的三個犯罪嫌疑人組成了識別框架 =Peter, Paul, Mary ，目擊證人（W1, W2）分別給出下表所示的BPA?！疽蟆浚河嬎阕C人W1和W

27、2提供證據(jù)的組合結果。【解】：首先，計算歸一化常數(shù)K。12121212( )( )()()()()()()0.99 00.01 0.010 0.990.0001B CKm Bm Cm Peterm Peterm Paulm Paulm Marym Mary 其次，利用Dempster證據(jù)合成規(guī)則分別計算Peter, Paul, Mary的組合BPA（即組合mass函數(shù)）。（1）關于Peter的組合mass函數(shù)1212121()( )()1()()10.990.000.000.0001BCPetermmPeterm BmCKmPetermPeterK（2）關于Paul的組合mass函數(shù)12121

28、()()()10.01 0.0110.0001mmPaulmPaulmPaulK（3）關于Mary的組合mass函數(shù)1212121()( )()1()()10.000.990.000.0001BCMarymmMarym BmCKmMarymMaryK【說明】：對于這個簡單的實例而言，對于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) = P

29、l(Mary) = m12(Mary) = 0 例2. 若修改“Zadeh悖論悖論” 表中的部分數(shù)據(jù)，如下表所示。請重新計算證人W1和W2提供證據(jù)的組合結果?！窘狻俊窘狻浚菏紫龋嬎銡w一化常數(shù)K。121212121( )( )1 ()()()()()()1(0.980.010.980.980.01 0.98)0.02BCKm Bm Cm PetermPaulm PetermMarym PaulmMary m1()m2()m12()Peter0.9800.49Paul0.010.010.015Mary00.980.49 =Peter, Paul, Mary0.010.010.005歸一化常數(shù)K的

30、另一種計算法：12121212121212( )( )()( )()()()( )( )()( )()( )( )0.98 0.010.01 0.010.01 0.010.01 0.010.01 0.980.01 0.010.02B CKm Bm Cm Petermm PaulmPaulm PaulmmmPaulmmMarymm 121212121()( )()1()()()()1(0.9800.980.01)0.490.02BCPetermmPeterm BmCKmPetermPetermPetermK（1）計算關于）計算關于Peter的組合的組合mass函數(shù)函數(shù)12121212121()(

31、 )()1()()()()()()1(0.01 0.010.01 0.010.01 0.01)0.0150.02BCPaulmmPaulm BmCKmPaulmPaulmPaulmKmmPaul （2）計算關于）計算關于Paul的組合的組合mass函數(shù)函數(shù)121212121()( )()1()()( )()1(00.980.01 0.98)0.490.02BCMarymmMarym BmCKmMarymMarymmMaryK（3）計算關于）計算關于Mary的組合的組合mass函數(shù)函數(shù)1212121()( )()1()()10.01 0.010.0050.02BCmmm BmCKmmK （4）計

32、算關于）計算關于 =Peter, Paul, Mary的組合的組合mass函數(shù)函數(shù)此外，根據(jù)信任函數(shù)、似然函數(shù)的計算公式，可得：即， Bel(Peter) = 0.49; Pl(Peter) = 0.49 + 0.005 = 0.495 Bel(Paul) = 0.015; Pl(Paul) = 0.015 + 0.005=0.020 Bel(Mary) = 0.49; Pl(Mary) = 0.49 + 0.005 = 0.495 Bel() = Pl() = 0.49 + 0.015 + 0.49 + 0.005 = 1 5.3 5.3 關于證據(jù)理論的理論模型解釋關于證據(jù)理論的理論模型解釋

33、 對Dempster-Shafer證據(jù)理論的解釋共有四種： （1）上、下概率解釋上、下概率解釋（Upper and lower probability interpretation）； （2）廣義化）廣義化Bayes理論理論（Generalized Bayesian theory）解釋； （3）隨機集理論隨機集理論（Random sets）模型解釋； （4）可傳遞信度模型）可傳遞信度模型（Transferable belief model，簡稱TBM）解釋；【注】第(1)(3)這三種解釋都以“概率理論”為基礎的；而第(4)種，即TBM為“純粹的”的DS理論模型，它已經(jīng)完全從任何概率內(nèi)涵中“提純

34、”了出來，不依賴于任何概率理論。 1、上、下概率解釋 Dempster在1967年發(fā)表的第一篇關于證據(jù)理論的論文中給出了上、下概率的概念，用以表示不滿足可加性的概率。 2、廣義化Bayes理論解釋 當mass函數(shù)m中的所有焦元都是單點集單點集（即單個假設單個假設集集），且這些焦元都滿足Bayes獨立條件時，Dempster證據(jù)合成公式就退化為Bayes公式，所以， Bayes公式是Dempster證據(jù)合成公式的特例特例。反過來說， Dempster證據(jù)合成公式是Bayes公式的廣義化廣義化。 3、隨機集理論模型解釋 Mahler和Fixsen分別于1996，1997年發(fā)表了下面兩篇論文：1 M

35、ahler, R. P. S. Combining ambiguous evidence with respect to ambiguous a priori knowledge, I: Boolean logic. IEEE Transactions on Systems, Man, and Cybernetics- Part A: Systems and Humans, 1996, 26(1): 27-41.2 Fixsen, D. and Mahler, R. P. S. The modified Dempster- Shafer approach to classification.

36、IEEE Transactions on Systems, Man, and Cybernetics- Part A: Systems and Humans, 1997, 27(1): 27-41.指出條件化(Conditional) Dempster-Shafer理論（簡稱CDS）和修改的(Modified) Dempster-Shafer理論（簡稱MDS）都是建立在隨機集（隨機集（Random）理論理論基礎上的。 補充說明：補充說明： （1）當證據(jù)和先驗知識都是模糊的情況下，則條件化Dempster-Shafer理論（CDS）是Bayes理論的廣義化，它完全是一種概率理論。 （2）當證據(jù)和

37、先驗知識都是統(tǒng)計獨立時，則條件化Dempster-Shafer理論（CDS）的證據(jù)合成相當于隨機條件事件的并（或交）。 Yen在醫(yī)療專家系統(tǒng)GERTIS中提出了擴展 （Extended）的Dempster-Shafer理論（簡稱EDS），實際上EDS就是一種CDS或MDS?！綴en, J. GERTIS: a Dempster-Shafer approach to diagnosing hierarchical hypotheses. Communications of the ACM, 1989, 32(5): 573-585.】 4、可傳遞信度模型（可傳遞信度模型（TBM）解釋解釋 Sme

38、ts認為從信度（信度（Belief）的“更新/條件化”（Updating/Conditioning）方式中，可以看出各種DS理論模型的主要差別。 (1) TBM模型模型 Smets發(fā)現(xiàn)許多DS模型的研究者只看到了BPA是在識別框架 的幕集上的靜態(tài)概率分布，但他們都沒有研究DS模型的動態(tài)部分，即信度是如何更新的，因此，提出了一種不依賴任何概率理論的不依賴任何概率理論的“可傳遞可傳遞信度模型信度模型TBM”。 ( )( )|x Am Ap xA (2) TBM是一個雙層模型是一個雙層模型 “credal層”：位于底層，在該層中獲取信度并對其進行量化、賦值和更新處理。 “pignistic層”：位于

39、上層，它將credal層上的信度轉換成pignistic概率，并由此做出決策。 只有必須做出決策時，pignistic層才出現(xiàn)。其中，pignistic概率分布公式如下： (3) TBM模型的意義模型的意義 TBM模仿了人類的“思維思維”和“行動行動”的區(qū)別，即模仿了“推理”和“行為”的差別： 推理：推理：表明信度是如何受證據(jù)影響的 行動：行動：從多個可行的行為方案中選擇一個似乎是最好的 TBM實際上是一種層次化的遞進模型層次化的遞進模型，體現(xiàn)了證據(jù)的層次化描述特征，它比較適用于需要逐層進行數(shù)據(jù)、特征和決策層融合的數(shù)據(jù)融合系統(tǒng)?！菊f明】：上述關于證據(jù)理論的四種典型的解釋模型，各有其適用領域，沒

40、有哪一個能適用于所有的應用領域，也不存在哪種模型更好的情況。 5.4 5.4 證據(jù)理論的實現(xiàn)途徑證據(jù)理論的實現(xiàn)途徑 Dempster合成公式的算法實現(xiàn)一直是困繞著DS理論的一個重點和難點問題重點和難點問題，這直接關系到其實用性直接關系到其實用性。 1、實現(xiàn)途徑分類 目前主要有如下三種途徑： （1）針對特殊的證據(jù)組織結構，構造相應的快速算法針對特殊的證據(jù)組織結構，構造相應的快速算法 （注：該方法比較簡單，故從略。感興趣者可參考Barnett, Shafer等人的相關文獻。） （2）近似計算）近似計算 （3）修改修改DS方法方法 2、Dempster合成規(guī)則的近似計算方法合成規(guī)則的近似計算方法 D

41、S近似計算的基本思想：通過減少mass函數(shù)的焦元個數(shù)來達到計算的簡化。 （1 1）Voorbraak的工作的工作“Bayes近似法近似法” Voorbraak發(fā)現(xiàn)，如果mass函數(shù)的合成將產(chǎn)生一個Bayes信任函數(shù)（即一個識別框架上的概率測度），則mass函數(shù)用它們的Bayes近似來代替，將不會影響Dempster合成規(guī)則的結果。Voorbraak給出了mass函數(shù)的Bayes近似計算公式，即()()() |0,ABCm BAm Am CC ， 若是 單 個 假 設 集 合 否 則 Voorbraak證明了如下結論：massmass函數(shù)的函數(shù)的BayesBayes近似的合成近似的合成massm

42、ass函數(shù)的合成的函數(shù)的合成的BayesBayes近似近似 Voorbraak的“Bayes近似法”的意義： 對于那些只關心識別框架中的“元素”（即單個假設）而不是其“子集”（即多個假設組成的子集）的最終結論的情況是非常有用的，并且大大簡化了計算量。【注】：感興趣者可參考本課件給出的Voorbraak 發(fā)表的相關論文。 Voobraak, F. A computationally efficient approximation of Dempster-Shafer theory. International Journal of Man-Machine Study, 1989, 30: 525

43、-536. Bayes近似法（續(xù)）近似法（續(xù)） （2 2）Dubois&Prade的工作的工作“一致近似法一致近似法” 一致近似法：Consonant approximation 特點特點：通過近似計算后的焦元是嵌套的，且焦元個數(shù)不超過識別框架中的假設個數(shù)。 缺點缺點：該方法不太適合用Dempster合成規(guī)則來進行計算，可能會產(chǎn)生很大的誤差。 用途用途：適用于證據(jù)的表達?！咀ⅰ浚焊信d趣者可參考本章參考文獻中列的Dubois&Prade發(fā)表的相關論文。 （3）Tessem的工作的工作(k, l, x)近似算法近似算法” k：表示保留的焦元的最少個數(shù)；l： 表示保留的焦元的最多個數(shù)； x： 表示允

44、許被刪除的最大mass值，x通常在0, 0.1上取值。 算法步驟如下： 步1：先對mass值從大到小排序； 步2：依次循環(huán)求mass函數(shù)值之和totalmass，若保留的焦元個數(shù)等于1，或totalmass = 1-x，則循環(huán)結束，否則，繼續(xù)循環(huán)； 步3：對保留的焦元所對應的mass函數(shù)值重新歸一化。 該算法的特點特點：它既不給出Bayes mass函數(shù)，也不給出一致mass函數(shù)，但它確實減少了焦元。5.5 5.5 基于基于DSDS理論的不確定性推理理論的不確定性推理 基于DS理論的不確定性推理步驟如下： 步1：概率分配函數(shù)的確定 步2：證據(jù)和知識的不確定性表示 步3：組合證據(jù)不確定性的算法

45、步4：不確定性的傳遞算法 步5：得到最終的推理結果【注】：對基于DS理論的不確定性推理方法感興趣者，可參考王永慶人工智能原理與方法中的“5.5.2 一個具體的不確定性推理模型”pp190-198。5.6 5.6 計算舉例計算舉例n假設在2001年美國發(fā)生“911事件”之前，布什總統(tǒng)分別接到美國中央情報局（CIA）和國家安全局（NSA）兩大情報機構發(fā)來的絕密情報，其內(nèi)容是關于中東地區(qū)的某些國家或組織企圖對美國實施突然的恐怖襲擊。CIA和NSA得到的證據(jù)如表1所示。試計算并回答下列問題： 1. 請直接利用Dempster證據(jù)合成公式計算表1中的所有“？”內(nèi)容。 2. 根據(jù)BPA（mass函數(shù)值）的

46、Bayes近似計算公式，重新調(diào)整表1中的BPA分布，并利用Dempster證據(jù)合成公式重新計算調(diào)整后的表1中的所有“？”內(nèi)容。( )( )( ) |0,A BCm BAm Am CC，若 是單個假設集合 否則 情報部門恐怖分子中央情報局（CIA）國家安全局（NSA）布什政府根據(jù)DS理論計算后的結果本拉登（簡稱“本本”）0.400.20？薩達姆（簡稱“薩薩”）0.300.20？霍梅尼（簡稱“霍霍”）0.100.05？本本拉登，薩薩達姆0.100.50？ = 本本, 薩薩, 霍霍0.100.05？表1 美國CIA和NSA所掌握的證據(jù) 實例解答：n首先，計算歸一化常數(shù)K。73. 027. 01)05

47、. 01 . 0.05. 04 . 02 . 04 . 0 (1)(),(.)()()()(1)()(121212121霍薩本霍本薩本mmmmmmCmBmKCB實例解答（續(xù)實例解答（續(xù)1）n計算關于本拉登（“本”）的組合mass函數(shù)4658. 0)02. 002. 002. 02 . 008. 0(73. 01)2 . 01 . 005. 04 . 02 . 01 . 05 . 04 . 02 . 04 . 0(73. 01)()()()()(),(),()()()(1)()(1)(21212121212121本本本薩本薩本本本本本本mmmmmmmmmmKCmBmKmmCB實例解答（續(xù)實例解答

48、（續(xù)2）n同理可得：363. 0)02. 0015. 002. 015. 006. 0(73. 01) 1 . 02 . 005. 03 . 01 . 02 . 05 . 03 . 02 . 03 . 0(73. 01)()(1)(2121 薩薩CBCmBmKmm實例解答（續(xù)實例解答（續(xù)3）n同理可得：0205. 0)005. 0005. 0005. 0(73. 01)05. 01 . 005. 01 . 005. 01 . 0(73. 01)()(1)(2121 霍霍CBCmBmKmm實例解答（續(xù)實例解答（續(xù)4）n同理可得：1438. 0)05. 0005. 005. 0(73. 01)5

49、. 01 . 005. 01 . 05 . 01 . 0(73. 01)()(1),(2121 本，薩薩本CBCmBmKmm實例解答（續(xù)實例解答（續(xù)5）n同理可得：0068. 0005. 073. 01)05. 01 . 0(73. 01)()(1)()(1)(212121mmKCmBmKmmCB 情報部門恐怖分子中央情報局（CIA）國家安全局（NSA）布什政府根據(jù)DS理論計算后的結果本拉登（簡稱“本本”）0.400.200.4658薩達姆（簡稱“薩薩”）0.300.200.3630霍梅尼（簡稱“霍霍”）0.100.050.0205本本拉登，薩薩達姆0.100.500.1438 = 本本, 薩

50、薩, 霍霍0.100.050.0068表2 經(jīng)Dempster規(guī)則合成后的mass 計算計算BPA的的Bayes近似近似n根據(jù)BPA的Bayes近似公式：( )( )( ) |0,A BCm BAm Am CC，若 是單個假設集合 否則BPA的的Bayes近似（續(xù)近似（續(xù)1）4615. 03 . 16 . 031 . 021 . 011 . 013 . 014 . 01 . 01 . 04 . 03)(2),(1)(1)(1)()(),()()(111111111mmmmmmmmm薩本霍薩本薩本本本BPA的的Bayes近似（續(xù)近似（續(xù)2）3846. 03 . 15 . 031 . 021 .

51、011 . 013 . 014 . 01 . 01 . 03 . 03)(2),(1)(1)(1)()(),()()(111111111mmmmmmmmm薩本霍薩本薩本薩薩BPA的的Bayes近似（續(xù)近似（續(xù)3）1538. 03 . 12 . 031 . 021 . 011 . 013 . 014 . 01 . 01 . 03)(2),(1)(1)(1)()()()(11111111mmmmmmmm薩本霍薩本霍霍BPA的的Bayes近似（續(xù)近似（續(xù)4）4688. 06 . 175. 0305. 025 . 0105. 012 . 012 . 005. 05 . 02 . 03)(2),(1)(1)(1)()(),()()(222222222mmmmmmmmm薩本霍薩本薩本本本BPA的的Bayes近似（續(xù)近似（續(xù)5）4688. 06 . 175. 0305. 025 . 0105. 012 . 012