DS證據(jù)理論分析課件

1、浙江大學(xué)研究生人工智能課件徐從富(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 )第1頁(yè)，共69頁(yè)。Outline本章的主要參考文獻(xiàn)證據(jù)理論的發(fā)展簡(jiǎn)況經(jīng)典證據(jù)理論

2、關(guān)于證據(jù)理論的理論模型解釋證據(jù)理論的實(shí)現(xiàn)途徑基于DS理論的不確定性推理計(jì)算舉例第2頁(yè)，共69頁(yè)。1 Dempster, A. P. Upper and lower probabilities induced by a multivalued mapping. Annals of Mathematical Statistics, 1967, 38(2): 325-339. 【提出證據(jù)理論的第一篇文獻(xiàn)】2 Dempster, A. P. Generalization of Bayesian Inference. Journal of the Royal Statistical Society. S

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

4、 Vancouver, B. C., Canada, Vol. II, 1981: 868-875. 【第一篇將證據(jù)理論引入AI領(lǐng)域的標(biāo)志性論文】本章的主要參考文獻(xiàn)第3頁(yè)，共69頁(yè)。5 Zadeh, L. A. Review of Shafers a mathematical theory of evidence. AI Magazine, 1984, 5:81-83. 【對(duì)證據(jù)理論進(jìn)行質(zhì)疑的經(jīng)典文獻(xiàn)之一】6 Shafer, G. Perspectives on the theory and practice of belief functions. International Journal

5、 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 combination. Artificial Intell

6、igence, 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: 191-234. 本章的主要參考文獻(xiàn)（續(xù)1）第4頁(yè)，共6

7、9頁(yè)。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, 1990, 4: 279-283. 13 Tessem, B.

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

9、m. In: Proceedings of SPIE-International Society for Optical Engineering, 1996, Vol.2759: 577-588. 【提出了一種實(shí)現(xiàn)證據(jù)理論的“修剪算法”】本章的主要參考文獻(xiàn)（續(xù)2）第5頁(yè)，共69頁(yè)。15 Josang, A. The consensus operator for combining beliefs. Artificial Intelligence, 2002, 141(1-2): 157-170. 16 Yang, Jian-Bo, Xu, Dong-Ling. On the evidentia

10、l 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. International Journal of Approximate Re

11、asoning, 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. 本章的主要參考文獻(xiàn)（續(xù)3）第6頁(yè)，共69頁(yè)。19 段新生. 證據(jù)理論與決策、人工智能. 中國(guó)人民大學(xué)出版社, 1993. 20 徐從富 等. Dempster-Shafer證據(jù)推理方法理論與應(yīng)用的綜述. 模式識(shí)別與人工智能, 1999, 12(4)

12、: 424-430. 21 徐從富 等. 面向數(shù)據(jù)融合的DS方法綜述. 電子學(xué)報(bào), 2001, 29(3): 393-396.22 徐從富 等. 解決證據(jù)推理中一類“0絕對(duì)化”問(wèn)題的方法. 計(jì)算機(jī)科學(xué), 2000, 27(5): 53-56. 23 李岳峰 等. 證據(jù)理論中的近似計(jì)算方法. 吉林大學(xué)自然科學(xué)學(xué)報(bào), 1995, (1):28-32.24 劉大有 等. 廣義證據(jù)理論的解釋. 計(jì)算機(jī)學(xué)報(bào), 1997, 20(2): 158-164.25 劉大有 等. 凸函數(shù)證據(jù)理論模型. 計(jì)算機(jī)研究與發(fā)展, 2000, 37(2): 175-181.本章的主要參考文獻(xiàn)（續(xù)4）第7頁(yè)，共69頁(yè)。26

13、楊瑩 等. 對(duì)一種基于證據(jù)理論的不確定性處理模型的重要擴(kuò)充. 計(jì)算機(jī)學(xué)報(bào), 1990, (10): 772-778. 27 劉大有 等. 一種簡(jiǎn)化證據(jù)理論模型的研究. 計(jì)算機(jī)研究與發(fā)展, 1999, 36(2): 134-138.28 肖人彬 等. 相關(guān)證據(jù)合成方法的研究. 模式識(shí)別與人工智能, 1993, 6(3): 227-234. 29 孫全 等. 一種新的基于證據(jù)理論的合成公式. 電子學(xué)報(bào), 2000, 28(8): 117-119.30 曾成, 趙保軍, 何佩昆. 不完備框架下的證據(jù)組合方法. 電子與信息學(xué)報(bào), 2005, 27(7): 1043-1046. 31 王永慶. 人工智能

14、原理與方法. 西安交通大學(xué)出版社, 1998. pp. 185-197. （第5章第5.5節(jié) “證據(jù)理論”）本章的主要參考文獻(xiàn)（續(xù)5）第8頁(yè)，共69頁(yè)。5.1 證據(jù)理論的發(fā)展簡(jiǎn)況 1、證據(jù)理論的名稱 證據(jù)理論(Evidential Theory) Dempster-Shafer理論 Dempster-Shafer證據(jù)理論 DS (或D-S)理論其它叫法： Dempster規(guī)則 Dempster合成規(guī)則 Dempster證據(jù)合成規(guī)則第9頁(yè)，共69頁(yè)。 2、證據(jù)理論的誕生和形成 誕生：源于20世紀(jì)60年代美國(guó)哈佛大學(xué)數(shù)學(xué)家A. P. Dempster在利用上、下限概率來(lái)解決多值映射問(wèn)題方面的研究工

15、作。自1967年起連續(xù)發(fā)表了一系列論文，標(biāo)志著證據(jù)理論的正式誕生。 形成：Dempster的學(xué)生G. Shafer對(duì)證據(jù)理論做了進(jìn)一步的發(fā)展，引入信任函數(shù)概念，形成了一套基于“證據(jù)”和“組合”來(lái)處理不確定性推理問(wèn)題的數(shù)學(xué)方法，并于1976年出版了證據(jù)的數(shù)學(xué)理論(A Mathematical Theory of Evidence)，這標(biāo)志著證據(jù)理論正式成為一種處理不確定性問(wèn)題的完整理論。第10頁(yè)，共69頁(yè)。 3、證據(jù)理論的核心、優(yōu)點(diǎn)及適用領(lǐng)域 核心：Dempster合成規(guī)則，這是Dempster在研究統(tǒng)計(jì)問(wèn)題時(shí)首先提出的，隨后Shafer把它推廣到更為一般的情形。 優(yōu)點(diǎn)：由于在證據(jù)理論中需要的先

16、驗(yàn)數(shù)據(jù)比概率推理理論中的更為直觀、更容易獲得，再加上Dempster合成公式可以綜合不同專家或數(shù)據(jù)源的知識(shí)或數(shù)據(jù)，這使得證據(jù)理論在專家系統(tǒng)、信息融合等領(lǐng)域中得到了廣泛應(yīng)用。 適用領(lǐng)域：信息融合、專家系統(tǒng)、情報(bào)分析、法律案件分析、多屬性決策分析，等等。第11頁(yè)，共69頁(yè)。 4、證據(jù)理論的局限性 要求證據(jù)必須是獨(dú)立的，而這有時(shí)不易滿足 證據(jù)合成規(guī)則沒(méi)有非常堅(jiān)固的理論支持，其合理性和有效性還存在較大的爭(zhēng)議 計(jì)算上存在著潛在的指數(shù)爆炸問(wèn)題第12頁(yè)，共69頁(yè)。 5、證據(jù)理論的發(fā)展概況 “Zadeh悖論”：對(duì)證據(jù)理論的合成公式的合理性進(jìn)行質(zhì)疑。 例子：利用Dempster證據(jù)合成規(guī)則對(duì)兩個(gè)目擊證人（W1,

17、 W2）判斷某宗“謀殺案” 的三個(gè)犯罪嫌疑人（Peter, Paul, Mary）中究竟誰(shuí)是真正的兇手，得到的結(jié)果（認(rèn)定Paul是兇手）卻違背了人的常識(shí)推理結(jié)果，Zadeh認(rèn)為這樣的結(jié)果無(wú)法接受。m1()m2()m12()Peter0.990.000.00Paul0.010.011.00Mary0.000.990.00第13頁(yè)，共69頁(yè)。 專家系統(tǒng)MYCIN的主要開發(fā)者之一Shortliffe：對(duì)證據(jù)理論的理論模型解釋和算法實(shí)現(xiàn)進(jìn)行了研究。 AI專家Dubois & Prade ：指出證據(jù)理論中的信任函數(shù)（Belief function）是一種模糊測(cè)度，以集合論的觀點(diǎn)研究證據(jù)的并、交、補(bǔ)和包含

18、等問(wèn)題。 Smets等人：將信任函數(shù)推廣到識(shí)別框架的所有模糊子集上，提出Pignistic概率和可傳遞信度模型（TBM）。 粗糙集理論的創(chuàng)始人Pawlak：認(rèn)為粗糙集理論使得無(wú)限框架上的證據(jù)處理向有限框架上的證據(jù)處理的近似轉(zhuǎn)化成為可能。證據(jù)理論的發(fā)展概況（續(xù)1）第14頁(yè)，共69頁(yè)。 為了避免證據(jù)組合爆炸，提高證據(jù)合成的效率： Voorbraak：提出一種Dempster證據(jù)合成公式的Bayes近似方法，使得焦元個(gè)數(shù)小于等于識(shí)別框架中元素的個(gè)數(shù)。 Dubois & Prade ：提出一種 “和諧近似”（Consonant approximation），即用和諧函數(shù)來(lái)代替原來(lái)的信任函數(shù)。 Tess

19、em：提出了一種稱為(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ā)展概況（續(xù)2）第15頁(yè)，共69頁(yè)。 6、證據(jù)理論在中國(guó)的發(fā)展情況 段新生：在1993年出版了一本專門論述證據(jù)理論的專著證據(jù)理論與決策、人工智能?！咀ⅲ河捎诖藭霭鏁r(shí)間較早，故其內(nèi)容不是很新，未能反映證據(jù)理論及其應(yīng)用方面的最新成果】 劉大有

20、等人：國(guó)內(nèi)較早研究證據(jù)理論的專家，并發(fā)表了一系列的論文，主要集中研究該理論的模型解釋、理論擴(kuò)展、近似實(shí)現(xiàn)等問(wèn)題。 肖人彬等人：對(duì)證據(jù)的相關(guān)性及相關(guān)證據(jù)的組合問(wèn)題進(jìn)行了研究。 蘇運(yùn)霖、管紀(jì)文等人：對(duì)證據(jù)理論與粗糙集理論進(jìn)行了比較研究。 【蘇運(yùn)霖, 管紀(jì)文等. 證據(jù)論與約集論.軟件學(xué)報(bào),1999, 10(3): 277-282. 注：此處的“約集”即為“粗糙集”(Rough set)】第16頁(yè)，共69頁(yè)。 曾成等人：研究了不完備的識(shí)別框架下的證據(jù)合成問(wèn)題，并提出相應(yīng)的證據(jù)合成公式。 顧偉康等人：對(duì)證據(jù)合成公式進(jìn)行擴(kuò)展，提出一種改進(jìn)的證據(jù)合成公式。 徐從富等人：1999-2001總結(jié)國(guó)內(nèi)外關(guān)于證據(jù)理

21、論及其應(yīng)用的代表性文獻(xiàn)，先后發(fā)表2篇關(guān)于證據(jù)理論及其應(yīng)用的綜述文章。 證據(jù)理論在中國(guó)的發(fā)展情況（續(xù)）第17頁(yè)，共69頁(yè)。5.2 經(jīng)典證據(jù)理論 1、證據(jù)理論的主要特點(diǎn) 滿足比Bayes概率理論更弱的條件，即不必滿足概率可加性。 具有直接表達(dá)“不確定”和“不知道”的能力，這些信息表示在mass函數(shù)中，并在證據(jù)合成過(guò)程中保留了這些信息。 證據(jù)理論不但允許人們將信度賦予假設(shè)空間的單個(gè)元素，而且還能賦予它的子集，這很象人類在各級(jí)抽象層次上的證據(jù)收集過(guò)程。第18頁(yè)，共69頁(yè)。 2、基本概念 設(shè)是一個(gè)識(shí)別框架，或稱假設(shè)空間。 （1）基本概率分配 基本概率分配：Basic Probability Assign

22、ment，簡(jiǎn)稱BPA。在識(shí)別框架上的BPA是一個(gè)2 0, 1的函數(shù)m，稱為mass函數(shù)。并且滿足 m() = 0 且 其中，使得m(A)0的A稱為焦元(Focal elements)。第19頁(yè)，共69頁(yè)。 （2）信任函數(shù) 信任函數(shù)也稱信度函數(shù)（Belief function）。 在識(shí)別框架上基于BPA m的信任函數(shù)定義為： （3）似然函數(shù) 似然函數(shù)也稱似然度函數(shù) (Plausibility function) 。 在識(shí)別框架上基于BPA m的似然函數(shù)定義為：第20頁(yè)，共69頁(yè)。 在證據(jù)理論中，對(duì)于識(shí)別框架 中的某個(gè)假設(shè)A，根據(jù)基本概率分配BPA分別計(jì)算出關(guān)于該假設(shè)的信任函數(shù)Bel(A)和似然函

23、數(shù)Pl(A)組成信任區(qū)間Bel(A), Pl(A)，用以表示對(duì)某個(gè)假設(shè)的確認(rèn)程度。（4）信任區(qū)間“Teach us to number our days aright, that we may gain a heart of wisdom.”From Psalms 90:12第21頁(yè)，共69頁(yè)。 3、Dempster合成規(guī)則 Dempster合成規(guī)則（Dempsters combinational rule）也稱證據(jù)合成公式，其定義如下： 對(duì)于A，上的兩個(gè)mass函數(shù)m1, m2的Dempster合成規(guī)則為：其中， K為歸一化常數(shù)第22頁(yè)，共69頁(yè)。 對(duì)于A，識(shí)別框架上的有限個(gè)mass函數(shù)m1

24、, m2, ., mn的Dempster合成規(guī)則為：其中，n個(gè)mass函數(shù)的Dempster合成規(guī)則第23頁(yè)，共69頁(yè)。m1()m2()m12()Peter0.990.000.00Paul0.010.011.00Mary0.000.990.00 4、Dempster合成規(guī)則計(jì)算舉例 例1. “Zadeh悖論” ：某宗“謀殺案” 的三個(gè)犯罪嫌疑人組成了識(shí)別框架 =Peter, Paul, Mary ，目擊證人（W1, W2）分別給出下表所示的BPA。【要求】：計(jì)算證人W1和W2提供證據(jù)的組合結(jié)果。【解】：首先，計(jì)算歸一化常數(shù)K。第24頁(yè)，共69頁(yè)。其次，利用Dempster證據(jù)合成規(guī)則分別計(jì)算P

25、eter, Paul, Mary的組合BPA（即組合mass函數(shù)）。（1）關(guān)于Peter的組合mass函數(shù)（2）關(guān)于Paul的組合mass函數(shù)第25頁(yè)，共69頁(yè)。（3）關(guān)于Mary的組合mass函數(shù)【說(shuō)明】：對(duì)于這個(gè)簡(jiǎn)單的實(shí)例而言，對(duì)于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(Mary) = m12(Mary) = 0第26

26、頁(yè)，共69頁(yè)。 例2. 若修改“Zadeh悖論” 表中的部分?jǐn)?shù)據(jù)，如下表所示。請(qǐng)重新計(jì)算證人W1和W2提供證據(jù)的組合結(jié)果?！窘狻浚菏紫龋?jì)算歸一化常數(shù)K。m1()m2()m12()Peter0.9800.49Paul0.010.010.015Mary00.980.49 =Peter, Paul, Mary0.010.010.005第27頁(yè)，共69頁(yè)。歸一化常數(shù)K的另一種計(jì)算法：第28頁(yè)，共69頁(yè)。（1）計(jì)算關(guān)于Peter的組合mass函數(shù)第29頁(yè)，共69頁(yè)。（2）計(jì)算關(guān)于Paul的組合mass函數(shù)第30頁(yè)，共69頁(yè)。（3）計(jì)算關(guān)于Mary的組合mass函數(shù)第31頁(yè)，共69頁(yè)。（4）計(jì)算關(guān)于 =

27、Peter, Paul, Mary的組合mass函數(shù)此外，根據(jù)信任函數(shù)、似然函數(shù)的計(jì)算公式，可得：即， 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第32頁(yè)，共69頁(yè)。 5.3 關(guān)于證據(jù)理論的理論模型解釋 對(duì)Dempster-Shafer證據(jù)理論的

28、解釋共有四種： （1）上、下概率解釋（Upper and lower probability interpretation）； （2）廣義化Bayes理論（Generalized Bayesian theory）解釋； （3）隨機(jī)集理論（Random sets）模型解釋； （4）可傳遞信度模型（Transferable belief model，簡(jiǎn)稱TBM）解釋；【注】第(1)(3)這三種解釋都以“概率理論”為基礎(chǔ)的；而第(4)種，即TBM為“純粹的”的DS理論模型，它已經(jīng)完全從任何概率內(nèi)涵中“提純”了出來(lái)，不依賴于任何概率理論。第33頁(yè)，共69頁(yè)。 1、上、下概率解釋 Dempster在19

29、67年發(fā)表的第一篇關(guān)于證據(jù)理論的論文中給出了上、下概率的概念，用以表示不滿足可加性的概率。 2、廣義化Bayes理論解釋 當(dāng)mass函數(shù)m中的所有焦元都是單點(diǎn)集（即單個(gè)假設(shè)集），且這些焦元都滿足Bayes獨(dú)立條件時(shí)，Dempster證據(jù)合成公式就退化為Bayes公式，所以， Bayes公式是Dempster證據(jù)合成公式的特例。反過(guò)來(lái)說(shuō)， Dempster證據(jù)合成公式是Bayes公式的廣義化。第34頁(yè)，共69頁(yè)。 3、隨機(jī)集理論模型解釋 Mahler和Fixsen分別于1996，1997年發(fā)表了下面兩篇論文：1 Mahler, R. P. S. Combining ambiguous evide

30、nce 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. IEEE Transactions on Systems, Man, and Cy

31、bernetics- Part A: Systems and Humans, 1997, 27(1): 27-41.指出條件化(Conditional) Dempster-Shafer理論（簡(jiǎn)稱CDS）和修改的(Modified) Dempster-Shafer理論（簡(jiǎn)稱MDS）都是建立在隨機(jī)集（Random）理論基礎(chǔ)上的。第35頁(yè)，共69頁(yè)。 補(bǔ)充說(shuō)明： （1）當(dāng)證據(jù)和先驗(yàn)知識(shí)都是模糊的情況下，則條件化Dempster-Shafer理論（CDS）是Bayes理論的廣義化，它完全是一種概率理論。 （2）當(dāng)證據(jù)和先驗(yàn)知識(shí)都是統(tǒng)計(jì)獨(dú)立時(shí)，則條件化Dempster-Shafer理論（CDS）的證據(jù)合

32、成相當(dāng)于隨機(jī)條件事件的并（或交）。 Yen在醫(yī)療專家系統(tǒng)GERTIS中提出了擴(kuò)展 （Extended）的Dempster-Shafer理論（簡(jiǎn)稱EDS），實(shí)際上EDS就是一種CDS或MDS?！綴en, J. GERTIS: a Dempster-Shafer approach to diagnosing hierarchical hypotheses. Communications of the ACM, 1989, 32(5): 573-585.】第36頁(yè)，共69頁(yè)。 4、可傳遞信度模型（TBM）解釋 Smets認(rèn)為從信度（Belief）的“更新/條件化”（Updating/Conditio

33、ning）方式中，可以看出各種DS理論模型的主要差別。 (1) TBM模型 Smets發(fā)現(xiàn)許多DS模型的研究者只看到了BPA是在識(shí)別框架 的幕集上的靜態(tài)概率分布，但他們都沒(méi)有研究DS模型的動(dòng)態(tài)部分，即信度是如何更新的，因此，提出了一種不依賴任何概率理論的“可傳遞信度模型TBM”。 第37頁(yè)，共69頁(yè)。 (2) TBM是一個(gè)雙層模型 “credal層”：位于底層，在該層中獲取信度并對(duì)其進(jìn)行量化、賦值和更新處理。 “pignistic層”：位于上層，它將credal層上的信度轉(zhuǎn)換成pignistic概率，并由此做出決策。 只有必須做出決策時(shí)，pignistic層才出現(xiàn)。其中，pignistic概率

34、分布公式如下：第38頁(yè)，共69頁(yè)。 (3) TBM模型的意義 TBM模仿了人類的“思維”和“行動(dòng)”的區(qū)別，即模仿了“推理”和“行為”的差別： 推理：表明信度是如何受證據(jù)影響的 行動(dòng)：從多個(gè)可行的行為方案中選擇一個(gè)似乎是最好的 TBM實(shí)際上是一種層次化的遞進(jìn)模型，體現(xiàn)了證據(jù)的層次化描述特征，它比較適用于需要逐層進(jìn)行數(shù)據(jù)、特征和決策層融合的數(shù)據(jù)融合系統(tǒng)。【說(shuō)明】：上述關(guān)于證據(jù)理論的四種典型的解釋模型，各有其適用領(lǐng)域，沒(méi)有哪一個(gè)能適用于所有的應(yīng)用領(lǐng)域，也不存在哪種模型更好的情況。第39頁(yè)，共69頁(yè)。 5.4 證據(jù)理論的實(shí)現(xiàn)途徑 Dempster合成公式的算法實(shí)現(xiàn)一直是困繞著DS理論的一個(gè)重點(diǎn)和難點(diǎn)問(wèn)

35、題，這直接關(guān)系到其實(shí)用性。 1、實(shí)現(xiàn)途徑分類 目前主要有如下三種途徑： （1）針對(duì)特殊的證據(jù)組織結(jié)構(gòu)，構(gòu)造相應(yīng)的快速算法 （注：該方法比較簡(jiǎn)單，故從略。感興趣者可參考Barnett, Shafer等人的相關(guān)文獻(xiàn)。） （2）近似計(jì)算 （3）修改DS方法第40頁(yè)，共69頁(yè)。 2、Dempster合成規(guī)則的近似計(jì)算方法 DS近似計(jì)算的基本思想：通過(guò)減少mass函數(shù)的焦元個(gè)數(shù)來(lái)達(dá)到計(jì)算的簡(jiǎn)化。 （1）Voorbraak的工作“Bayes近似法” Voorbraak發(fā)現(xiàn)，如果mass函數(shù)的合成將產(chǎn)生一個(gè)Bayes信任函數(shù)（即一個(gè)識(shí)別框架上的概率測(cè)度），則mass函數(shù)用它們的Bayes近似來(lái)代替，將不會(huì)影

36、響Dempster合成規(guī)則的結(jié)果。Voorbraak給出了mass函數(shù)的Bayes近似計(jì)算公式，即第41頁(yè)，共69頁(yè)。 Voorbraak證明了如下結(jié)論：mass函數(shù)的Bayes近似的合成mass函數(shù)的合成的Bayes近似 Voorbraak的“Bayes近似法”的意義： 對(duì)于那些只關(guān)心識(shí)別框架中的“元素”（即單個(gè)假設(shè)）而不是其“子集”（即多個(gè)假設(shè)組成的子集）的最終結(jié)論的情況是非常有用的，并且大大簡(jiǎn)化了計(jì)算量?！咀ⅰ浚焊信d趣者可參考本課件給出的Voorbraak 發(fā)表的相關(guān)論文。 Voobraak, F. A computationally efficient approximation of

37、 Dempster-Shafer theory. International Journal of Man-Machine Study, 1989, 30: 525-536. Bayes近似法（續(xù)）第42頁(yè)，共69頁(yè)。 （2）Dubois&Prade的工作“一致近似法” 一致近似法：Consonant approximation 特點(diǎn)：通過(guò)近似計(jì)算后的焦元是嵌套的，且焦元個(gè)數(shù)不超過(guò)識(shí)別框架中的假設(shè)個(gè)數(shù)。 缺點(diǎn)：該方法不太適合用Dempster合成規(guī)則來(lái)進(jìn)行計(jì)算，可能會(huì)產(chǎn)生很大的誤差。 用途：適用于證據(jù)的表達(dá)?！咀ⅰ浚焊信d趣者可參考本章參考文獻(xiàn)中列的Dubois&Prade發(fā)表的相關(guān)論文。第43

38、頁(yè)，共69頁(yè)。 （3）Tessem的工作(k, l, x)近似算法” k：表示保留的焦元的最少個(gè)數(shù)；l： 表示保留的焦元的最多個(gè)數(shù)； x： 表示允許被刪除的最大mass值，x通常在0, 0.1上取值。 算法步驟如下： 步1：先對(duì)mass值從大到小排序； 步2：依次循環(huán)求mass函數(shù)值之和totalmass，若保留的焦元個(gè)數(shù)等于1，或totalmass = 1-x，則循環(huán)結(jié)束，否則，繼續(xù)循環(huán)； 步3：對(duì)保留的焦元所對(duì)應(yīng)的mass函數(shù)值重新歸一化。 該算法的特點(diǎn)：它既不給出Bayes mass函數(shù)，也不給出一致mass函數(shù)，但它確實(shí)減少了焦元。第44頁(yè)，共69頁(yè)。5.5 基于DS理論的不確定性推理

39、 基于DS理論的不確定性推理步驟如下： 步1：概率分配函數(shù)的確定 步2：證據(jù)和知識(shí)的不確定性表示 步3：組合證據(jù)不確定性的算法 步4：不確定性的傳遞算法 步5：得到最終的推理結(jié)果【注】：對(duì)基于DS理論的不確定性推理方法感興趣者，可參考王永慶人工智能原理與方法中的“5.5.2 一個(gè)具體的不確定性推理模型”pp190-198。第45頁(yè)，共69頁(yè)。5.6 計(jì)算舉例假設(shè)在2001年美國(guó)發(fā)生“911事件”之前，布什總統(tǒng)分別接到美國(guó)中央情報(bào)局（CIA）和國(guó)家安全局（NSA）兩大情報(bào)機(jī)構(gòu)發(fā)來(lái)的絕密情報(bào)，其內(nèi)容是關(guān)于中東地區(qū)的某些國(guó)家或組織企圖對(duì)美國(guó)實(shí)施突然的恐怖襲擊。CIA和NSA得到的證據(jù)如表1所示。試計(jì)

40、算并回答下列問(wèn)題： 1. 請(qǐng)直接利用Dempster證據(jù)合成公式計(jì)算表1中的所有“？”內(nèi)容。 2. 根據(jù)BPA（mass函數(shù)值）的Bayes近似計(jì)算公式，重新調(diào)整表1中的BPA分布，并利用Dempster證據(jù)合成公式重新計(jì)算調(diào)整后的表1中的所有“？”內(nèi)容。第46頁(yè)，共69頁(yè)。 情報(bào)部門恐怖分子中央情報(bào)局（CIA）國(guó)家安全局（NSA）布什政府根據(jù)DS理論計(jì)算后的結(jié)果本拉登（簡(jiǎn)稱“本”）0.400.20？薩達(dá)姆（簡(jiǎn)稱“薩”）0.300.20？霍梅尼（簡(jiǎn)稱“霍”）0.100.05？本拉登，薩達(dá)姆0.100.50？ = 本, 薩, 霍0.100.05？表1 美國(guó)CIA和NSA所掌握的證據(jù) 第47頁(yè)，共

41、69頁(yè)。實(shí)例解答：首先，計(jì)算歸一化常數(shù)K。第48頁(yè)，共69頁(yè)。實(shí)例解答（續(xù)1）計(jì)算關(guān)于本拉登（“本”）的組合mass函數(shù)第49頁(yè)，共69頁(yè)。實(shí)例解答（續(xù)2）同理可得：第50頁(yè)，共69頁(yè)。實(shí)例解答（續(xù)3）同理可得：第51頁(yè)，共69頁(yè)。實(shí)例解答（續(xù)4）同理可得：第52頁(yè)，共69頁(yè)。實(shí)例解答（續(xù)5）同理可得：第53頁(yè)，共69頁(yè)。 情報(bào)部門恐怖分子中央情報(bào)局（CIA）國(guó)家安全局（NSA）布什政府根據(jù)DS理論計(jì)算后的結(jié)果本拉登（簡(jiǎn)稱“本”）0.400.200.4658薩達(dá)姆（簡(jiǎn)稱“薩”）0.300.200.3630霍梅尼（簡(jiǎn)稱“霍”）0.100.050.0205本拉登，薩達(dá)姆0.100.500.1438 = 本, 薩, 霍0.100.050.0068表2 經(jīng)Dempster規(guī)則合成后的mass 第54頁(yè)，共69頁(yè)。計(jì)算BPA的Bayes近似根據(jù)BPA的Bayes近似公式：第55頁(yè)，共69頁(yè)。BPA的B