D-S證據(jù)理論(知識課件)

浙江大學(xué)研究生《人工智能》課件徐從富(CongfuXu)

PhD,AssociateProfessorEmail:xucongfu@InstituteofArtificialIntelligence,CollegeofComputerScience,ZhejiangUniversity,Hangzhou310027,P.R.ChinaMarch10,2002第一稿September25,2006第四次修改稿第五章D-S證據(jù)理論

(Chapter5D-SEvidentialTheory)1優(yōu)質(zhì)薈萃浙江大學(xué)研究生《人工智能》課件徐從富(CongfuXu)Outline本章的主要參考文獻(xiàn)證據(jù)理論的發(fā)展簡況經(jīng)典證據(jù)理論關(guān)于證據(jù)理論的理論模型解釋證據(jù)理論的實(shí)現(xiàn)途徑基于DS理論的不確定性推理計算舉例2優(yōu)質(zhì)薈萃Outline本章的主要參考文獻(xiàn)2優(yōu)質(zhì)薈萃[1]Dempster,A.P.Upperandlowerprobabilitiesinducedbyamultivaluedmapping.AnnalsofMathematicalStatistics,1967,38(2):325-339.【提出證據(jù)理論的第一篇文獻(xiàn)】[2]Dempster,A.P.GeneralizationofBayesianInference.JournaloftheRoyalStatisticalSociety.SeriesB30,1968:205-247.[3]Shafer,G.AMathematicalTheoryofEvidence.PrincetonUniversityPress,1976.【證據(jù)理論的第一本專著，標(biāo)志其正式成為一門理論】[4]Barnett,J.A.Computationalmethodsforamathematicaltheoryofevidence.In:Proceedingsof7thInternationalJointConferenceonArtificialIntelligence(IJCAI-81),Vancouver,B.C.,Canada,Vol.II,1981:868-875.【第一篇將證據(jù)理論引入AI領(lǐng)域的標(biāo)志性論文】本章的主要參考文獻(xiàn)3優(yōu)質(zhì)薈萃[1]Dempster,A.P.Upperand[5]Zadeh,L.A.ReviewofShafer’samathematicaltheoryofevidence.AIMagazine,1984,5:81-83.【對證據(jù)理論進(jìn)行質(zhì)疑的經(jīng)典文獻(xiàn)之一】[6]Shafer,G.Perspectivesonthetheoryandpracticeofbelieffunctions.InternationalJournalofApproximateReasoning,1990,4:323-362.[7]Shafer,G.Rejoindertocommentson“Perspectivesonthetheoryandpracticeofbelieffunctions”.InternationalJournalofApproximateReasoning,1992,6:445-480.[8]Voorbraak,F.OnthejustificationofDempster’sruleofcombination.ArtificialIntelligence,1991,48:171-197.[9]Smets,P.Thecombinationofevidenceinthetransferablemodel.IEEETransactionsonPatternAnalysisandMachineIntelligence,1990,12(5):447-458.[10]Smets,P,andKennes,R.Thetransferablebeliefmodel.ArtificialIntelligence,1994,66:191-234.本章的主要參考文獻(xiàn)（續(xù)1）4優(yōu)質(zhì)薈萃[5]Zadeh,L.A.ReviewofSh[11]Voobraak,F.AcomputationallyefficientapproximationofDempster-Shafertheory.InternationalJournalofMan-MachineStudy,1989,30:525-536.[12]Dubois,D,Prade,H.Consonantapproximationsofbelieffunctions.InternationalJournalofApproximateReasoning,1990,4:279-283.[13]Tessem,B.Approximationsforefficientcomputationinthetheoryofevidence.ArtificialIntelligence,1993,61:315-329.【注：文獻(xiàn)10-12均為證據(jù)理論近似計算方法】[14]Simard,M.A.,etal.DatafusionofmultiplesensorsattributeinformationfortargetidentityestimationusingaDempster-Shaferevidentialcombinationalgorithm.In:ProceedingsofSPIE-InternationalSocietyforOpticalEngineering,1996,Vol.2759:577-588.【提出了一種實(shí)現(xiàn)證據(jù)理論的“修剪算法”】本章的主要參考文獻(xiàn)（續(xù)2）5優(yōu)質(zhì)薈萃[11]Voobraak,F.Acomputati[15]Josang,A.Theconsensusoperatorforcombiningbeliefs.ArtificialIntelligence,2002,141(1-2):157-170.[16]Yang,Jian-Bo,Xu,Dong-Ling.Ontheevidentialreasoningalgorithmformultipleattributedecisionanalysisunderuncertainty.IEEETransactiononSystems,Man,andCybernetics–PartA:SystemsandHumans,2002,32(3):289-304.[17]Yaghlane,B.B.,etal.Belieffunctionindependence:I.Themarginalcase.InternationalJournalofApproximateReasoning,2002,29(1):47-70.[18]Yaghlane,B.B.,etal.Belieffunctionindependence:II.Theconditionalcase.InternationalJournalofApproximateReasoning,2002,31:31-75.本章的主要參考文獻(xiàn)（續(xù)3）6優(yōu)質(zhì)薈萃[15]Josang,A.Theconsensus[19]段新生.證據(jù)理論與決策、人工智能.中國人民大學(xué)出版社,1993.[20]徐從富等.Dempster-Shafer證據(jù)推理方法理論與應(yīng)用的綜述.模式識別與人工智能,1999,12(4):424-430.[21]徐從富等.面向數(shù)據(jù)融合的DS方法綜述.電子學(xué)報,2001,29(3):393-396.[22]徐從富等.解決證據(jù)推理中一類“0絕對化”問題的方法.計算機(jī)科學(xué),2000,27(5):53-56.[23]李岳峰等.證據(jù)理論中的近似計算方法.吉林大學(xué)自然科學(xué)學(xué)報,1995,(1):28-32.[24]劉大有等.廣義證據(jù)理論的解釋.計算機(jī)學(xué)報,1997,20(2):158-164.[25]劉大有等.凸函數(shù)證據(jù)理論模型.計算機(jī)研究與發(fā)展,2000,37(2):175-181.本章的主要參考文獻(xiàn)（續(xù)4）7優(yōu)質(zhì)薈萃[19]段新生.證據(jù)理論與決策、人工智能.中國人民[26]楊瑩等.對一種基于證據(jù)理論的不確定性處理模型的重要擴(kuò)充.計算機(jī)學(xué)報,1990,(10):772-778.[27]劉大有等.一種簡化證據(jù)理論模型的研究.計算機(jī)研究與發(fā)展,1999,36(2):134-138.[28]肖人彬等.相關(guān)證據(jù)合成方法的研究.模式識別與人工智能,1993,6(3):227-234.[29]孫全等.一種新的基于證據(jù)理論的合成公式.電子學(xué)報,2000,28(8):117-119.[30]曾成,趙保軍,何佩昆.不完備框架下的證據(jù)組合方法.電子與信息學(xué)報,2005,27(7):1043-1046.

[31]王永慶.人工智能原理與方法.西安交通大學(xué)出版社,1998.pp.185-197.（第5章第5.5節(jié)“證據(jù)理論”）本章的主要參考文獻(xiàn)（續(xù)5）8優(yōu)質(zhì)薈萃[26]楊瑩等.對一種基于證據(jù)理論的不確定性處理模型5.1證據(jù)理論的發(fā)展簡況1、證據(jù)理論的名稱

證據(jù)理論(EvidentialTheory)

Dempster-Shafer理論

Dempster-Shafer證據(jù)理論

DS(或D-S)理論其它叫法：

Dempster規(guī)則

Dempster合成規(guī)則

Dempster證據(jù)合成規(guī)則9優(yōu)質(zhì)薈萃5.1證據(jù)理論的發(fā)展簡況9優(yōu)質(zhì)薈萃2、證據(jù)理論的誕生和形成

誕生：源于20世紀(jì)60年代美國哈佛大學(xué)數(shù)學(xué)家A.P.Dempster在利用上、下限概率來解決多值映射問題方面的研究工作。自1967年起連續(xù)發(fā)表了一系列論文，標(biāo)志著證據(jù)理論的正式誕生。

形成：Dempster的學(xué)生G.Shafer對證據(jù)理論做了進(jìn)一步的發(fā)展，引入信任函數(shù)概念，形成了一套基于“證據(jù)”和“組合”來處理不確定性推理問題的數(shù)學(xué)方法，并于1976年出版了《證據(jù)的數(shù)學(xué)理論》(AMathematicalTheoryofEvidence)，這標(biāo)志著證據(jù)理論正式成為一種處理不確定性問題的完整理論。10優(yōu)質(zhì)薈萃2、證據(jù)理論的誕生和形成10優(yōu)質(zhì)薈萃

3、證據(jù)理論的核心、優(yōu)點(diǎn)及適用領(lǐng)域

核心：Dempster合成規(guī)則，這是Dempster在研究統(tǒng)計問題時首先提出的，隨后Shafer把它推廣到更為一般的情形。

優(yōu)點(diǎn)：由于在證據(jù)理論中需要的先驗(yàn)數(shù)據(jù)比概率推理理論中的更為直觀、更容易獲得，再加上Dempster合成公式可以綜合不同專家或數(shù)據(jù)源的知識或數(shù)據(jù)，這使得證據(jù)理論在專家系統(tǒng)、信息融合等領(lǐng)域中得到了廣泛應(yīng)用。

適用領(lǐng)域：信息融合、專家系統(tǒng)、情報分析、法律案件分析、多屬性決策分析，等等。11優(yōu)質(zhì)薈萃3、證據(jù)理論的核心、優(yōu)點(diǎn)及適用領(lǐng)域11優(yōu)質(zhì)薈萃4、證據(jù)理論的局限性

要求證據(jù)必須是獨(dú)立的，而這有時不易滿足

證據(jù)合成規(guī)則沒有非常堅固的理論支持，其合理性和有效性還存在較大的爭議

計算上存在著潛在的指數(shù)爆炸問題12優(yōu)質(zhì)薈萃4、證據(jù)理論的局限性12優(yōu)質(zhì)薈萃

5、證據(jù)理論的發(fā)展概況

“Zadeh悖論”：對證據(jù)理論的合成公式的合理性進(jìn)行質(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.00Mary0.000.990.0013優(yōu)質(zhì)薈萃5、證據(jù)理論的發(fā)展概況m1()m2()m12()Pet

專家系統(tǒng)MYCIN的主要開發(fā)者之一Shortliffe：對證據(jù)理論的理論模型解釋和算法實(shí)現(xiàn)進(jìn)行了研究。

AI專家Dubois&Prade

：指出證據(jù)理論中的信任函數(shù)（Belieffunction）是一種模糊測度，以集合論的觀點(diǎn)研究證據(jù)的并、交、補(bǔ)和包含等問題。

Smets等人：將信任函數(shù)推廣到識別框架的所有模糊子集上，提出Pignistic概率和可傳遞信度模型（TBM）。

粗糙集理論的創(chuàng)始人Pawlak：認(rèn)為粗糙集理論使得無限框架上的證據(jù)處理向有限框架上的證據(jù)處理的近似轉(zhuǎn)化成為可能。證據(jù)理論的發(fā)展概況（續(xù)1）14優(yōu)質(zhì)薈萃專家系統(tǒng)MYCIN的主要開發(fā)者之一Shortliff

為了避免證據(jù)組合爆炸，提高證據(jù)合成的效率：

Voorbraak：提出一種Dempster證據(jù)合成公式的Bayes近似方法，使得焦元個數(shù)小于等于識別框架中元素的個數(shù)。

Dubois&Prade

：提出一種“和諧近似”（Consonantapproximation），即用和諧函數(shù)來代替原來的信任函數(shù)。

Tessem：提出了一種稱為(k,l,x)近似方法。

Yen等人：

將模糊集引入證據(jù)理論。

Yen,J.GeneralizingtheDempster-Shafertheorytofuzzysets.IEEETrans.onSystems,Man,andCybernetics,1990,20(3):559-570.】證據(jù)理論的發(fā)展概況（續(xù)2）15優(yōu)質(zhì)薈萃為了避免證據(jù)組合爆炸，提高證據(jù)合成的效率：證據(jù)理論的

6、證據(jù)理論在中國的發(fā)展情況

段新生：在1993年出版了一本專門論述證據(jù)理論的專著《證據(jù)理論與決策、人工智能》?！咀ⅲ河捎诖藭霭鏁r間較早，故其內(nèi)容不是很新，未能反映證據(jù)理論及其應(yīng)用方面的最新成果】

劉大有等人：國內(nèi)較早研究證據(jù)理論的專家，并發(fā)表了一系列的論文，主要集中研究該理論的模型解釋、理論擴(kuò)展、近似實(shí)現(xiàn)等問題。

肖人彬等人：對證據(jù)的相關(guān)性及相關(guān)證據(jù)的組合問題進(jìn)行了研究。

蘇運(yùn)霖、管紀(jì)文等人：對證據(jù)理論與粗糙集理論進(jìn)行了比較研究?！咎K運(yùn)霖,管紀(jì)文等.證據(jù)論與約集論.軟件學(xué)報,1999,10(3):277-282.注：此處的“約集”即為“粗糙集”(Roughset)】16優(yōu)質(zhì)薈萃6、證據(jù)理論在中國的發(fā)展情況16優(yōu)質(zhì)薈萃

曾成等人：研究了不完備的識別框架下的證據(jù)合成問題，并提出相應(yīng)的證據(jù)合成公式。

顧偉康等人：對證據(jù)合成公式進(jìn)行擴(kuò)展，提出一種改進(jìn)的證據(jù)合成公式。

徐從富等人：1999-2001總結(jié)國內(nèi)外關(guān)于證據(jù)理論及其應(yīng)用的代表性文獻(xiàn)，先后發(fā)表2篇關(guān)于證據(jù)理論及其應(yīng)用的綜述文章。

……

證據(jù)理論在中國的發(fā)展情況（續(xù)）17優(yōu)質(zhì)薈萃曾成等人：研究了不完備的識別框架下的證據(jù)5.2經(jīng)典證據(jù)理論1、證據(jù)理論的主要特點(diǎn)

滿足比Bayes概率理論更弱的條件，即不必滿足概率可加性。

具有直接表達(dá)“不確定”和“不知道”的能力，這些信息表示在mass函數(shù)中，并在證據(jù)合成過程中保留了這些信息。

證據(jù)理論不但允許人們將信度賦予假設(shè)空間的單個元素，而且還能賦予它的子集，這很象人類在各級抽象層次上的證據(jù)收集過程。18優(yōu)質(zhì)薈萃5.2經(jīng)典證據(jù)理論18優(yōu)質(zhì)薈萃2、基本概念

設(shè)是一個識別框架，或稱假設(shè)空間。

（1）基本概率分配基本概率分配：BasicProbabilityAssignment，簡稱BPA。在識別框架上的BPA是一個2

[0,1]的函數(shù)m，稱為mass函數(shù)。并且滿足

m()=0且

其中，使得m(A)>0的A稱為焦元(Focalelements)。19優(yōu)質(zhì)薈萃2、基本概念其中，使得m(A)>0的A稱為焦元(Foc

（2）信任函數(shù)

信任函數(shù)也稱信度函數(shù)（Belieffunction）。在識別框架上基于BPAm的信任函數(shù)定義為：

（3）似然函數(shù)

似然函數(shù)也稱似然度函數(shù)

(Plausibilityfunction)。在識別框架上基于BPAm的似然函數(shù)定義為：20優(yōu)質(zhì)薈萃（2）信任函數(shù)（3）似然函數(shù)20優(yōu)質(zhì)薈萃在證據(jù)理論中，對于識別框架中的某個假設(shè)A，根據(jù)基本概率分配BPA分別計算出關(guān)于該假設(shè)的信任函數(shù)Bel(A)和似然函數(shù)Pl(A)組成信任區(qū)間[Bel(A),Pl(A)]，用以表示對某個假設(shè)的確認(rèn)程度。（4）信任區(qū)間“Teachustonumberourdaysaright,thatwemaygainaheartofwisdom.”FromPsalms90:1221優(yōu)質(zhì)薈萃在證據(jù)理論中，對于識別框架中的某個假設(shè)A

3、Dempster合成規(guī)則

Dempster合成規(guī)則（Dempster’scombinationalrule）也稱證據(jù)合成公式，其定義如下：對于A，上的兩個mass函數(shù)m1,m2的Dempster合成規(guī)則為：其中，K為歸一化常數(shù)22優(yōu)質(zhì)薈萃3、Dempster合成規(guī)則其中，K為歸一化常數(shù)22優(yōu)

對于A，識別框架上的有限個mass函數(shù)m1,m2,...,

mn的Dempster合成規(guī)則為：其中，n個mass函數(shù)的Dempster合成規(guī)則23優(yōu)質(zhì)薈萃對于A，識別框架上的有限個mass函數(shù)m1,m1()m2()m12()Peter0.990.000.00Paul0.010.011.00Mary0.000.990.00

4、Dempster合成規(guī)則計算舉例

例1.“Zadeh悖論”：某宗“謀殺案”的三個犯罪嫌疑人組成了識別框架

={Peter,Paul,Mary}，目擊證人（W1,W2）分別給出下表所示的BPA?！疽蟆浚河嬎阕C人W1和W2提供證據(jù)的組合結(jié)果?！窘狻浚菏紫?，計算歸一化常數(shù)K。24優(yōu)質(zhì)薈萃m1()m2()m12()Peter0.990.000.00其次，利用Dempster證據(jù)合成規(guī)則分別計算Peter,Paul,Mary的組合BPA（即組合mass函數(shù)）。（1）關(guān)于Peter的組合mass函數(shù)（2）關(guān)于Paul的組合mass函數(shù)25優(yōu)質(zhì)薈萃其次，利用Dempster證據(jù)合成規(guī)則分別計算Peter,（3）關(guān)于Mary的組合mass函數(shù)【說明】：對于這個簡單的實(shí)例而言，對于Peter,Paul,Mary的組合mass函數(shù)，再求信任函數(shù)、似然函數(shù)，可知：信任函數(shù)值＝似然函數(shù)值＝組合后的mass函數(shù)值即，Bel({Peter})=Pl({Peter})=m12({Peter})=0Bel({Paul})=Pl({Paul})=m12({Paul})=1Bel({Mary})=Pl({Mary})=m12({Mary})=026優(yōu)質(zhì)薈萃（3）關(guān)于Mary的組合mass函數(shù)【說明】：對于這個簡單的

例2.若修改“Zadeh悖論”表中的部分?jǐn)?shù)據(jù)，如下表所示。請重新計算證人W1和W2提供證據(jù)的組合結(jié)果?！窘狻浚菏紫龋嬎銡w一化常數(shù)K。m1()m2()m12(){Peter}0.9800.49{Paul}0.010.010.015{Mary}00.980.49

={Peter,Paul,Mary}0.010.010.00527優(yōu)質(zhì)薈萃例2.若修改“Zadeh悖論”表中的部分?jǐn)?shù)據(jù)歸一化常數(shù)K的另一種計算法：28優(yōu)質(zhì)薈萃歸一化常數(shù)K的另一種計算法：28優(yōu)質(zhì)薈萃（1）計算關(guān)于Peter的組合mass函數(shù)29優(yōu)質(zhì)薈萃（1）計算關(guān)于Peter的組合mass函數(shù)29優(yōu)質(zhì)薈萃（2）計算關(guān)于Paul的組合mass函數(shù)30優(yōu)質(zhì)薈萃（2）計算關(guān)于Paul的組合mass函數(shù)30優(yōu)質(zhì)薈萃（3）計算關(guān)于Mary的組合mass函數(shù)31優(yōu)質(zhì)薈萃（3）計算關(guān)于Mary的組合mass函數(shù)31優(yōu)質(zhì)薈萃（4）計算關(guān)于

={Peter,Paul,Mary}的組合mass函數(shù)此外，根據(jù)信任函數(shù)、似然函數(shù)的計算公式，可得：即，Bel({Peter})=0.49;Pl({Peter})=0.49+0.005=0.495Bel({Paul})=0.015;Pl({Paul})=0.015+0.005=0.020Bel({Mary})=0.49;Pl({Mary})=0.49+0.005=0.495Bel(

)=Pl(

)=0.49+0.015+0.49+0.005=132優(yōu)質(zhì)薈萃（4）計算關(guān)于={Peter,Paul,Mary}的5.3關(guān)于證據(jù)理論的理論模型解釋

對Dempster-Shafer證據(jù)理論的解釋共有四種：

（1）上、下概率解釋（Upperandlowerprobabilityinterpretation）；

（2）廣義化Bayes理論（GeneralizedBayesiantheory）解釋；

（3）隨機(jī)集理論（Randomsets）模型解釋；

（4）可傳遞信度模型（Transferablebeliefmodel，簡稱TBM）解釋；【注】第(1)~(3)這三種解釋都以“概率理論”為基礎(chǔ)的；而第(4)種，即TBM為“純粹的”的DS理論模型，它已經(jīng)完全從任何概率內(nèi)涵中“提純”了出來，不依賴于任何概率理論。33優(yōu)質(zhì)薈萃5.3關(guān)于證據(jù)理論的理論模型解釋33優(yōu)質(zhì)薈萃

1、上、下概率解釋

Dempster在1967年發(fā)表的第一篇關(guān)于證據(jù)理論的論文中給出了上、下概率的概念，用以表示不滿足可加性的概率。

2、廣義化Bayes理論解釋

當(dāng)mass函數(shù)m中的所有焦元都是單點(diǎn)集（即單個假設(shè)集），且這些焦元都滿足Bayes獨(dú)立條件時，Dempster證據(jù)合成公式就退化為Bayes公式，所以，

Bayes公式是Dempster證據(jù)合成公式的特例。反過來說，

Dempster證據(jù)合成公式是Bayes公式的廣義化。34優(yōu)質(zhì)薈萃1、上、下概率解釋34優(yōu)質(zhì)薈萃

3、隨機(jī)集理論模型解釋

Mahler和Fixsen分別于1996，1997年發(fā)表了下面兩篇論文：[1]Mahler,R.P.S.Combiningambiguousevidencewithrespecttoambiguousaprioriknowledge,I:Booleanlogic.IEEETransactionsonSystems,Man,andCybernetics-PartA:SystemsandHumans,1996,26(1):27-41.[2]Fixsen,D.andMahler,R.P.S.ThemodifiedDempster-Shaferapproachtoclassification.IEEETransactionsonSystems,Man,andCybernetics-PartA:SystemsandHumans,1997,27(1):27-41.指出條件化(Conditional)Dempster-Shafer理論（簡稱CDS）和修改的(Modified)Dempster-Shafer理論（簡稱MDS）都是建立在隨機(jī)集（Random）理論基礎(chǔ)上的。35優(yōu)質(zhì)薈萃3、隨機(jī)集理論模型解釋35優(yōu)質(zhì)薈萃補(bǔ)充說明：（1）當(dāng)證據(jù)和先驗(yàn)知識都是模糊的情況下，則條件化Dempster-Shafer理論（CDS）是Bayes理論的廣義化，它完全是一種概率理論。（2）當(dāng)證據(jù)和先驗(yàn)知識都是統(tǒng)計獨(dú)立時，則條件化Dempster-Shafer理論（CDS）的證據(jù)合成相當(dāng)于隨機(jī)條件事件的并（或交）。

Yen在醫(yī)療專家系統(tǒng)GERTIS中提出了擴(kuò)展（Extended）的Dempster-Shafer理論（簡稱EDS），實(shí)際上EDS就是一種CDS或MDS?！綴en,J.GERTIS:aDempster-Shaferapproachtodiagnosinghierarchicalhypotheses.CommunicationsoftheACM,1989,32(5):573-585.】36優(yōu)質(zhì)薈萃補(bǔ)充說明：36優(yōu)質(zhì)薈萃

4、可傳遞信度模型（TBM）解釋

Smets認(rèn)為從信度（Belief）的“更新/條件化”（Updating/Conditioning）方式中，可以看出各種DS理論模型的主要差別。

(1)TBM模型

Smets發(fā)現(xiàn)許多DS模型的研究者只看到了BPA是在識別框架

的幕集上的靜態(tài)概率分布，但他們都沒有研究DS模型的動態(tài)部分，即信度是如何更新的，因此，提出了一種不依賴任何概率理論的“可傳遞信度模型TBM”。

37優(yōu)質(zhì)薈萃4、可傳遞信度模型（TBM）解釋37優(yōu)質(zhì)薈萃

(2)TBM是一個雙層模型“credal層”：位于底層，在該層中獲取信度并對其進(jìn)行量化、賦值和更新處理?！皃ignistic層”：位于上層，它將credal層上的信度轉(zhuǎn)換成pignistic概率，并由此做出決策。只有必須做出決策時，pignistic層才出現(xiàn)。其中，pignistic概率分布公式如下：38優(yōu)質(zhì)薈萃(2)TBM是一個雙層模型38優(yōu)質(zhì)薈萃

(3)TBM模型的意義

TBM模仿了人類的“思維”和“行動”的區(qū)別，即模仿了“推理”和“行為”的差別：

推理：表明信度是如何受證據(jù)影響的

行動：從多個可行的行為方案中選擇一個似乎是最好的

TBM實(shí)際上是一種層次化的遞進(jìn)模型，體現(xiàn)了證據(jù)的層次化描述特征，它比較適用于需要逐層進(jìn)行數(shù)據(jù)、特征和決策層融合的數(shù)據(jù)融合系統(tǒng)。【說明】：上述關(guān)于證據(jù)理論的四種典型的解釋模型，各有其適用領(lǐng)域，沒有哪一個能適用于所有的應(yīng)用領(lǐng)域，也不存在哪種模型更好的情況。39優(yōu)質(zhì)薈萃(3)TBM模型的意義39優(yōu)質(zhì)薈萃5.4證據(jù)理論的實(shí)現(xiàn)途徑

Dempster合成公式的算法實(shí)現(xiàn)一直是困繞著DS理論的一個重點(diǎn)和難點(diǎn)問題，這直接關(guān)系到其實(shí)用性。

1、實(shí)現(xiàn)途徑分類目前主要有如下三種途徑：

（1）針對特殊的證據(jù)組織結(jié)構(gòu)，構(gòu)造相應(yīng)的快速算法（注：該方法比較簡單，故從略。感興趣者可參考Barnett,Shafer等人的相關(guān)文獻(xiàn)。）

（2）近似計算

（3）修改DS方法40優(yōu)質(zhì)薈萃5.4證據(jù)理論的實(shí)現(xiàn)途徑40優(yōu)質(zhì)薈萃

2、Dempster合成規(guī)則的近似計算方法

DS近似計算的基本思想：通過減少mass函數(shù)的焦元個數(shù)來達(dá)到計算的簡化。

（1）Voorbraak的工作—“Bayes近似法”

Voorbraak發(fā)現(xiàn)，如果mass函數(shù)的合成將產(chǎn)生一個Bayes信任函數(shù)（即一個識別框架上的概率測度），則mass函數(shù)用它們的Bayes近似來代替，將不會影響Dempster合成規(guī)則的結(jié)果。Voorbraak給出了mass函數(shù)的Bayes近似計算公式，即41優(yōu)質(zhì)薈萃2、Dempster合成規(guī)則的近似計算方法41優(yōu)

Voorbraak證明了如下結(jié)論：mass函數(shù)的Bayes近似的合成＝mass函數(shù)的合成的Bayes近似Voorbraak的“Bayes近似法”的意義：對于那些只關(guān)心識別框架中的“元素”（即單個假設(shè)）而不是其“子集”（即多個假設(shè)組成的子集）的最終結(jié)論的情況是非常有用的，并且大大簡化了計算量?！咀ⅰ浚焊信d趣者可參考本課件給出的Voorbraak發(fā)表的相關(guān)論文。Voobraak,F.AcomputationallyefficientapproximationofDempster-Shafertheory.InternationalJournalofMan-MachineStudy,1989,30:525-536.Bayes近似法（續(xù)）42優(yōu)質(zhì)薈萃Voorbraak證明了如下結(jié)論：Bayes近

（2）Dubois&Prade的工作—“一致近似法”

一致近似法：Consonantapproximation

特點(diǎn)：通過近似計算后的焦元是嵌套的，且焦元個數(shù)不超過識別框架中的假設(shè)個數(shù)。

缺點(diǎn)：該方法不太適合用Dempster合成規(guī)則來進(jìn)行計算，可能會產(chǎn)生很大的誤差。

用途：適用于證據(jù)的表達(dá)。【注】：感興趣者可參考本章參考文獻(xiàn)中列的Dubois&Prade發(fā)表的相關(guān)論文。43優(yōu)質(zhì)薈萃（2）Dubois&Prade的工作—“一致近似法”43

（3）Tessem的工作—(k,l,x)近似算法”

k：表示保留的焦元的最少個數(shù)；l：表示保留的焦元的最多個數(shù)；x：表示允許被刪除的最大mass值，x通常在[0,0.1]上取值。

算法步驟如下：步1：先對mass值從大到小排序；步2：依次循環(huán)求mass函數(shù)值之和totalmass，若保留的焦元個數(shù)等于1，或totalmass>=1-x，則循環(huán)結(jié)束，否則，繼續(xù)循環(huán)；步3：對保留的焦元所對應(yīng)的mass函數(shù)值重新歸一化。該算法的特點(diǎn)：它既不給出Bayesmass函數(shù)，也不給出一致mass函數(shù)，但它確實(shí)減少了焦元。44優(yōu)質(zhì)薈萃（3）Tessem的工作—(k,l,x)近似算法”45.5基于DS理論的不確定性推理

基于DS理論的不確定性推理步驟如下：

步1：概率分配函數(shù)的確定步2：證據(jù)和知識的不確定性表示

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

1.請直接利用Dempster證據(jù)合成公式計算表1中的所有“？”內(nèi)容。

2.根據(jù)BPA（mass函數(shù)值）的Bayes近似計算公式，重新調(diào)整表1中的BPA分布，并利用Dempster證據(jù)合成公式重新計算調(diào)整后的表1中的所有“？”內(nèi)容。46優(yōu)質(zhì)薈萃5.6計算舉例假設(shè)在2001年美國發(fā)生“911事件”之前，情報部門恐怖分子中央情報局（CIA）國家安全局（NSA）布什政府根據(jù)DS理論計算后的結(jié)果{本

拉登}（簡稱“本”）0.400.20？{薩達(dá)姆}（簡稱“薩”）0.300.20？{霍梅尼}（簡稱“霍”）0.100.05？{本

拉登，薩達(dá)姆}0.100.50？

={本,薩,霍}0.100.05？表1美國CIA和NSA所掌握的證據(jù)47優(yōu)質(zhì)薈萃情報部門中央情報局國家安全局布什政府根據(jù)DS理論實(shí)例解答：首先，計算歸一化常數(shù)K。48優(yōu)質(zhì)薈萃實(shí)例解答：首先，計算歸一化常數(shù)K。48優(yōu)質(zhì)薈萃實(shí)例解答（續(xù)1）計算關(guān)于本拉登（“本”）的組合mass函數(shù)49優(yōu)質(zhì)薈萃實(shí)例解答（續(xù)1）計算關(guān)于本拉登（“本”）的組合mass函數(shù)4實(shí)例解答（續(xù)2）同理可得：50優(yōu)質(zhì)薈萃實(shí)例解答（續(xù)2）同理可得：50優(yōu)質(zhì)薈萃實(shí)例解答（續(xù)3）同理可得：51優(yōu)質(zhì)薈萃實(shí)例解答（續(xù)3）同理可得：51優(yōu)質(zhì)薈萃實(shí)例解答（續(xù)4）同理可得：52優(yōu)質(zhì)薈萃實(shí)例解答（續(xù)4）同理可得：52優(yōu)質(zhì)薈萃實(shí)例解答（續(xù)5）同理可得：53優(yōu)質(zhì)薈萃實(shí)例解答（續(xù)5）同理可得：53優(yōu)質(zhì)薈萃情報部門恐怖分子中央情報局（CIA）國家安全局（NSA）布什政府根據(jù)DS理論計算后的結(jié)果{本

拉登}（簡稱“本”）0.400.200.4658{薩達(dá)姆}（簡稱“薩”）0.300.200.3630{霍梅尼}（簡稱“霍”）0.100.050.0205{本

拉登，薩達(dá)姆}0.100.500.1438

={本,薩,霍}0.100.050.0068表2經(jīng)Dempster規(guī)則合成后的mass54優(yōu)質(zhì)薈萃情報部門中央情報局國家安全局布什政府根據(jù)DS理論計算BPA的Bayes近似根據(jù)BPA的Bayes近似公式：55優(yōu)質(zhì)薈萃計算BPA的Bayes近似根據(jù)BPA的Bayes近似公式：5BPA的Bayes近似（續(xù)1）56優(yōu)質(zhì)薈萃BPA的Bayes近似（續(xù)1）56優(yōu)質(zhì)薈萃BPA的Bayes近似（續(xù)2）57優(yōu)質(zhì)薈萃BPA的Bayes近似（續(xù)2）57優(yōu)質(zhì)薈萃BPA的Bayes近似（續(xù)3）58優(yōu)質(zhì)薈萃BPA的Bayes近似（續(xù)3）58優(yōu)質(zhì)薈萃BPA的Bayes近似（續(xù)4）59優(yōu)質(zhì)薈萃BPA的Bayes