證據(jù)理論-浙大

浙江大學(xué)研究生《人工智能引論》課件Email:

xucongfu@

zj

Institute

ofArtificial

Intelligence,

College

of

Computer

Science,Zhejiang

University,

Hangzhou

310027,

P.R.

ChinaMarch

10,2002第一稿September

22,2007第五次修改稿第五講

D-S

證據(jù)理論(Chapter

5

D-S

Evidential

Theory

)徐從富(Congfu

Xu)PhD,Associate

ProfessorOutline

本章的主要參考文獻(xiàn)

證據(jù)理論的發(fā)展簡況

經(jīng)典證據(jù)理論

關(guān)于證據(jù)理論的理論模型解釋

基于DS理論的不確定性推理

證據(jù)理論的實現(xiàn)途徑

計算舉例Dempster,A.P.Upper

and

lower

probabilities

induced

by

a

multivalued

mapping.Anna

ls

of

Mathema

tical

Statistics,1967,38(2):325-339.【提出證據(jù)理論的第一篇文獻(xiàn)】Dempster,

A.

P.

Generalization

of

B

ayesian

Inference.

J

ournal

of

theRoyal

Statistical

Society.

Series

B

30,

1968:205-247.Shafer,G.

A

Mathematical

Theory

of

Evidence.Princeton

UniversityPress,1976.【證據(jù)理論的第一本專著，標(biāo)志其正式成為一門理論】Barnett,

J

.A.

Computational

methods

for

a

mathematical

theory

ofevidence.

In:

Proceedings

of

7th

International

J

oint

Conference

on

ArtificialIntelligence(IJ

CAI-81),

Vancouver,

B.

C.,

Canada,

Vol.

II,

1981:

868-875.【第一篇將證據(jù)理論引入AI領(lǐng)域的標(biāo)志性論文】本章的主要參考文獻(xiàn)Zadeh,L.A.Review

of

Shafer’s

a

mathematical

theory

of

evidence.AIMagazine,1984,5:81-83.【對證據(jù)理論進行質(zhì)疑的經(jīng)典文獻(xiàn)之一】Shafer,

G.

Perspectives

on

the

theory

and

practice

of

belief

functions.International

J

ournal

of

Approxima

te

Reasoning,

1990,

4:

323

-362.Shafer,

G.

Rejoinder

to

comments

on

“Perspectives

on

the

theory

andpractice

of

belief

functions”.

International

J

ournal

of

Approxima

teReasoning,

1992,

6:

445

-480.Voorbraak,

F.

On

the

justification

of

Dempster’s

rule

of

combination.Artificial

Intelligence,

1991,

48:171-197.Smets,

P.

The

combination

of

evidence

in

the

transferable

model.

IEEETra

nsactions

on

Pattern

Ana

lysis

and

Machine

Intelligence,

1990,

12(5):447-458.Smets,

P,

and

Kennes,

R.

The

transferable

belief

model.

Artificia

lIntelligence,

1994,

66:

191

-234.本章的主要參考文獻(xiàn)（續(xù)1）Voobraak,

F.

A

computationally

efficient

approximation

of

Dempster-Shafer

theory.

International

J

ournal

of

Man-Machine

Study,

1989,

30:

525-536.Dubois,

D,

Prade,

H.

Consonant

approximations

of

belief

functions.International

J

ournal

of

Approxima

te

Reasoning,

1990,

4:

279-283.Tessem,B.Approximations

for

efficient

computation

in

the

theory

ofevidence.Artificial

Intelligence,1993,61:315-329.【注：文獻(xiàn)10-12均為證據(jù)理論近似計算方法】Simard,

M.

A.,

et

al.

Data

fusion

of

multiple

sensors

attribute

informationfor

target

identity

estimation

using

a

Dempster-Shafer

evidential

combinationalgorithm.

In:

Proceedings

of

SPIE-International

Society

for

OpticalEngineering,1996,Vol.2759:577-588.【提出了一種實現(xiàn)證據(jù)理論的“修剪算法”】本章的主要參考文獻(xiàn)（續(xù)2）Josang,

A.

The

consensus

operator

for

combining

beliefs.

Artificia

lIntelligence,

2002,

141(1-2):

157-170.Yang,

J

ian-Bo,

Xu,

Dong-Ling.

On

the

evidential

reasoning

algorithmfor

multiple

attribute

decision

analysis

under

uncertainty.

IEEE

Tra

nsactionon

Systems,

Man,

and

Cybernetics

–Pa

rt

A:

Systems

and

Huma

ns,

2002,32(3):

289-304.Yaghlane,

B.

B.,

et

al.

Belief

function

independence:

I.

The

marginalcase.

International

J

ournal

of

Approxima

te

Reasoning,

2002,

29(1):

47-70.Yaghlane,

B.

B.,

et

al.

Belief

function

independence:

II.

The

conditional

case.

International

J

ournal

of

Approxima

te

Reasoning,

2002,

31:31-75.本章的主要參考文獻(xiàn)（續(xù)3）分析人的散熱的方式人體適宜的外界溫度是20-25ㄣc,相對濕度為40%-60%，通過以下方式散熱：輻射是散熱最好途徑。氣溫15-25ㄣc時，輻射散熱約占60%，散熱最多部位是頭部（約50%），其次為手及足部。溫度33ㄣc時，輻射散熱降至零。傳導(dǎo)與對流通過對流,接觸和靠近皮膚的冷空氣變暖,變熱 的熱物質(zhì)分子離開,而較冷的物質(zhì)分子則取而代之,逐漸又變熱,如此反復(fù)進行。水傳導(dǎo)較空氣快240倍。蒸發(fā)每蒸發(fā)1g水,可散發(fā)2.4kj(0.58kcal)的熱量。分類

A.熱痙攣人在高溫環(huán)境中，身體會大量出汗，丟失大量鹽分，使血液中的鈉含量過低，引起肌肉痙攣.

B.熱衰竭由于水鹽的大量丟失,使得有效循環(huán)血量明顯減少,發(fā)生低血容量休克.集體為了散熱,心輸出量大大增加,使得心血管系統(tǒng)的負(fù)荷加重,導(dǎo)致心血管功能不全或周圍循環(huán)衰竭.

C.日射?。?/p>

在烈日的曝曬下，強烈的日光穿透頭部皮膚及顱骨引起腦細(xì)胞受損，進而造成腦組織的充血、水腫；由于受到傷害的主要是頭部，所以，最開始出現(xiàn)的不適就是劇烈頭痛、惡心嘔吐、煩躁不安，繼而可出現(xiàn)昏迷及抽搐。

D.熱射病是指因高溫引起的人體體溫調(diào)節(jié)功能失調(diào)，體內(nèi)熱量過度積蓄，從而引發(fā)神經(jīng)器官受損。在中暑的分級中就是重癥中暑。該病通常發(fā)生在夏季高溫同時伴有高濕的天氣。這是因為持續(xù)悶熱會使人的皮膚散熱功能下降，而且紅外線和紫外線可穿透皮膚直達(dá)肌內(nèi)深層，體內(nèi)熱量不能發(fā)散，此時熱量集聚在臟器及肌肉組織，引起皮膚干燥、肌肉溫度升高、導(dǎo)致汗段新生.證據(jù)理論與決策、人工智能.中國人民大學(xué)出版社,1993.徐從富等.Dempster-Shafer證據(jù)推理方法理論與應(yīng)用的綜述.模式識別與人工智能,1999,12(4):424-430.徐從富等.面向數(shù)據(jù)融合的DS方法綜述.電子學(xué)報,2001,29(3):393-396.徐從富等.解決證據(jù)推理中一類“0絕對化”問題的方法.計算機科學(xué),2000,27(5):53-56.李岳峰等.證據(jù)理論中的近似計算方法.吉林大學(xué)自然科學(xué)學(xué)報,

1995,(1):28-32.劉大有等.廣義證據(jù)理論的解釋.計算機學(xué)報,1997,20(2):158-164.劉大有等.凸函數(shù)證據(jù)理論模型.計算機研究與發(fā)展,2000,37(2):175-181.本章的主要參考文獻(xiàn)（續(xù)4）楊瑩等.對一種基于證據(jù)理論的不確定性處理模型的重要擴充.計算機學(xué)報,1990,(10):772-778.劉大有等.一種簡化證據(jù)理論模型的研究.計算機研究與發(fā)展,

1999,36(2):134-138.肖人彬等.相關(guān)證據(jù)合成方法的研究.模式識別與人工智能,1993,6(3):

227-234.孫全等.一種新的基于證據(jù)理論的合成公式.電子學(xué)報,2000,28(8):117

-119.曾成,趙保軍,何佩昆.不完備框架下的證據(jù)組合方法.電子與信息學(xué)報,2005,27(7):1043-1046.王永慶.人工智能原理與方法.西安交通大學(xué)出版社,1998.pp.185-197.（第5章第5.5節(jié)“證據(jù)理論”）本章的主要參考文獻(xiàn)（續(xù)5）5.1

證據(jù)理論的發(fā)展簡況1、證據(jù)理論的名稱饗證據(jù)理論(Evidential

Theory)饗Dempster-Shafer理論饗Dempster-Shafer證據(jù)理論饗DS(或D-S)理論其它叫法：饗Dempster規(guī)則饗Dempster合成規(guī)則饗Dempster證據(jù)合成規(guī)則2、證據(jù)理論的誕生和形成饗誕生：源于20世紀(jì)60年代美國哈佛大學(xué)數(shù)學(xué)家A.P.Dempster在利用上、下限概率來解決多值映射問題方面的研究工作。自1967年起連續(xù)發(fā)表了一系列論文，標(biāo)志著證據(jù)理論的正式誕生。饗形成：Dempster的學(xué)生G.Shafer對證據(jù)理論做了進一步的發(fā)展，引入信任函數(shù)概念，形成了一套基于“證據(jù)”和“組合”來處理不確定性推理問題的數(shù)學(xué)方法，并于1976年出版了《證據(jù)的數(shù)學(xué)理論》(AMathema

tical

Theoryof

Evidence)，這標(biāo)志著證據(jù)理論正式成為一種處理不確定性問題的完整理論。3、證據(jù)理論的核心、優(yōu)點及適用領(lǐng)域饗核心：Dempster合成規(guī)則，這是Dempster在研究統(tǒng)計問題時首先提出的，隨后Shafer把它推廣到更為一般的情形。饗優(yōu)點：由于在證據(jù)理論中需要的先驗數(shù)據(jù)比概率推理理論中的更為直觀、更容易獲得，再加上Dempster合成公式可以綜合不同專家或數(shù)據(jù)源的知識或數(shù)據(jù)，這使得證據(jù)理論在專家系統(tǒng)、信息融合等領(lǐng)域中得到了廣泛應(yīng)用。饗適用領(lǐng)域：信息融合、專家系統(tǒng)、情報分析、法律案件分析、多屬性決策分析，等等。4、證據(jù)理論的局限性饗要求證據(jù)必須是獨立的，而這有時不易滿足饗證據(jù)合成規(guī)則沒有非常堅固的理論支持，其合理性和有效性還存在較大的爭議饗計算上存在著潛在的指數(shù)爆炸問題5、證據(jù)理論的發(fā)展概況饗“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.00Mary0.000.990.00饗專家系統(tǒng)MYCIN的主要開發(fā)者之一Shortliffe：對證據(jù)理論的理論模型解釋和算法實現(xiàn)進行了研究。饗AI專家Dubois

&

Prade

：指出證據(jù)理論中的信任函數(shù)（Belief

function）是一種模糊測度，以集合論的觀點研究證據(jù)的并、交、補和包含等問題。饗Smets等人：將信任函數(shù)推廣到識別框架的所有模糊子集上，提出Pignistic概率和可傳遞信度模型（TBM）。饗粗糙集理論的創(chuàng)始人Pawlak：認(rèn)為粗糙集理論使得無限框架上的證據(jù)處理向有限框架上的證據(jù)處理的近似轉(zhuǎn)化成為可能。證據(jù)理論的發(fā)展概況（續(xù)1）為了避免證據(jù)組合爆炸，提高證據(jù)合成的效率：饗Voor

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

&

Prade

：提出一種“和諧近似”（Consonantapproximation），即用和諧函數(shù)來代替原來的信任函數(shù)。饗Tessem：提出了一種稱為(k,l,x)近似方法。饗Yen等人：將模糊集引入證據(jù)理論。Yen,J.Generalizingthe

Dempster-Shafer

theory

to

fuzzy

sets.IEEE

Tra

ns.on

Systems,Man,andCybernetics,1990,20(3):559-570.】證據(jù)理論的發(fā)展概況（續(xù)2）6、證據(jù)理論在中國的發(fā)展情況饗段新生：在1993年出版了一本專門論述證據(jù)理論的專著《證據(jù)理論與決策、人工智能》?！咀ⅲ河捎诖藭霭鏁r間較早，故其內(nèi)容不是很新，未能反映證據(jù)理論及其應(yīng)用方面的最新成果】饗劉大有等人：國內(nèi)較早研究證據(jù)理論的專家，并發(fā)表了一系列的論文，主要集中研究該理論的模型解釋、理論擴展、近似實現(xiàn)等問題。饗肖人彬等人：對證據(jù)的相關(guān)性及相關(guān)證據(jù)的組合問題進行了研究。饗蘇運霖、管紀(jì)文等人：對證據(jù)理論與粗糙集理論進行了比較研究。

【蘇運霖,

管紀(jì)文等.

證據(jù)論與約集論.

軟件學(xué)報,

1999,10(

3)

:

277-

282.

注：此處的“約集”即為“粗糙集”(

Rough

s

et

)

】饗曾成等人：研究了不完備的識別框架下的證據(jù)合成問題，并提出相應(yīng)的證據(jù)合成公式。饗顧偉康等人：對證據(jù)合成公式進行擴展，提出一種改進的證據(jù)合成公式。饗徐從富等人：1999-2001總結(jié)國內(nèi)外關(guān)于證據(jù)理論及其應(yīng)用的代表性文獻(xiàn)，先后發(fā)表2篇關(guān)于證據(jù)理論及其應(yīng)用的綜述文章。饗??證據(jù)理論在中國的發(fā)展情況（續(xù)）5.2

經(jīng)典證據(jù)理論1、證據(jù)理論的主要特點饗滿足比Bayes概率理論更弱的條件，即不必滿足概率可加性。饗具有直接表達(dá)“不確定”和“不知道”的能力，這些信息表示在mass函數(shù)中，并在證據(jù)合成過程中保留了這些信息。饗證據(jù)理論不但允許人們將信度賦予假設(shè)空間的單個元素，而且還能賦予它的子集，這很象人類在各級抽象層次上的證據(jù)收集過程。2、基本概念A(yù)癥Θ設(shè)Θ是一個識別框架，或稱假設(shè)空間。（1）基本概率分配基本概率分配：Basic

Probability

Assignment，簡稱B

PA。在識別框架Θ上的B

PA是一個2

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

=

0

且∑m(A)

=1其中，使得m(A)>0的A稱為焦元(Focal

elements)。（2）信任函數(shù)B癥A信任函數(shù)也稱信度函數(shù)（Belief

function）。在識別框架Θ上基于B

PA

m的信任函數(shù)定義為：Bel(A)

=

∑m(B)（3）似然函數(shù)似然函數(shù)也稱似然度函數(shù)(Plausibility

function)。在識別框架Θ上基于B

PA

m的似然函數(shù)定義為：Pl

(A)

=

∑

m(B)B

A≠堯在證據(jù)理論中，對于識別框架Θ中的某個假設(shè)A，根據(jù)基本概率分配B

PA分別計算出關(guān)于該假設(shè)的信任函數(shù)Bel(A)和似然函數(shù)Pl(A)組成信任區(qū)間[Bel(A),Pl(A)]，用以表示對某個假設(shè)的確認(rèn)程度。（4）信任區(qū)間“Teach

us

to

number

our

days

aright,

that

we

may

gain

a

heart

of

wisdom.”F

rom

Psalms

90:

123、Dempster合成規(guī)則Dempster合成規(guī)則（Dempster’s

combinational

rule）也稱證據(jù)合成公式，其定義如下：對于瘍A癥Θ，Θ上的兩個mass函數(shù)m1,m2的Dempster合成規(guī)則為：1

21

2m⊕m(A)=

1

∑m(B)匭m(C)K

B

C

=A其中，K為歸一化常數(shù)K=∑m1

(B)匭m2

(C)=1藝∑m1

(B)匭m2

(C)B

C

≠堯

B

C

=堯n個mass函數(shù)的Dempster合成規(guī)則對于瘍A癥Θ，識別框架Θ上的有限個mass函數(shù)m1,m2,...,

mn的Dempster合成規(guī)則為：1

2

nK∑A1

A2

An

=A(m

⊕m

⊕

⊕m

)(A)

=

1m1

(A1

)匭m2

(A2

)mn

(An

)其中，m1

(A1

)匭m2

(A2

)

mn

(An

)m1

(A1

)匭m2

(A2

)

mn

(An

)=1藝K

=∑∑A1

An

≠堯A1

An

=堯m1()m2()m12()Peter0.990.000.00Paul0.010.011.00Mary0.000.990.004、Dempster合成規(guī)則計算舉例例1.“Zadeh悖論”：某宗“謀殺案”的三個犯罪嫌疑人組成了識別框架Θ={Peter,Paul,Mary}，目擊證人（W1,W2）分別給出下表所示的B

PA?！疽蟆浚河嬎阕C人W1和W2提供證據(jù)的組合結(jié)果?！窘狻浚菏紫?，計算歸一化常數(shù)K。K=∑m1

(B)匭m2

(C)B

C≠堯=m1

(Peter)匭m2

(Peter)+m1

(Paul)匭m2

(Paul)+m1

(Ma

ry)匭m2

(Ma

ry)=

0.99

×0

+

0.01×0.01

+

0

×0.99

=

0.0001其次，利用Dempster證據(jù)合成規(guī)則分別計算Peter,Paul,Mary的組合B

PA（即組合mass函數(shù)）。（1）關(guān)于Peter的組合mass函數(shù)1

21

2m

⊕m

({

Peter}

)

=

1m1

(B)匭m2

(C)0.0001=

1

×0.99

×0.00

=

0.00K=

1

匭m({Peter})匭m({Peter})∑K

B

C

={

Peter

}（2）關(guān)于Paul的組合mass函數(shù)1

21

20.0001=

1

×0.01×0.01

=1Km⊕m({Paul})=

1

匭m({Paul})匭m({Paul})（3）關(guān)于Mary的組合mass函數(shù)1

21

2m

⊕m

({

Mary}

)

=

1m1

(B)匭m2

(C)0.0001=

1

×0.00

×0.99

=

0.00K=

1

匭m({Ma

ry})匭m({Mary})∑K

B

C

={

Mary}【說明】：對于這個簡單的實例而言，對于Peter,Paul,Mary的組合mass函數(shù)，再求信任函數(shù)、似然函數(shù)，可知：信任函數(shù)值＝似然函數(shù)值＝組合后的mas

s函數(shù)值即，Bel({Peter})=Pl({Peter})=m12({Peter})=0Bel({

Paul})

=

Pl({

Paul})

=

m12({

Paul})

=

1Bel({

Mary})

=

Pl({

Mary})

=

m12({

Mary})

=

0例2.

若修改“Za

deh悖論”

表中的部分?jǐn)?shù)據(jù)，如下表所示。請重新計算證人W1和W2提供證據(jù)的組合結(jié)果?！窘狻浚菏紫?，計算歸一化常數(shù)K。K=1藝∑m1

(B)匭m2

(C)B

C=堯=1藝[m1

(Peter)匭m2

(Paul)+m1

(Peter)匭m2

(Mary)+m1

(Paul)匭m2

(Ma

ry)]=1藝(0.98×0.01+0.98×0.98+0.01×0.98)=0.02m1()m2()m12(){

Peter}0.9800.49{

Paul}0.010.010.015{

Mary}00.980.49Θ={

Peter,

Paul,

Mary}0.010.010.005歸一化常數(shù)K的另一種計算法：K=∑m1

(B)匭m2

(C)B

C≠堯=m1

(Peter)匭m2

(Θ)+m1

(Paul)匭m2

(Paul)+m1

(Paul)匭m2

(Θ)+m1

(Θ)匭m2

(Paul)+m1

(Θ)匭m2

(Ma

y)+mr

1

(Θ)匭m2

(Θ)=

0.98

×0.01

+

0.01×0.01

+

0.01×0.01+0.01×0.01

+

0.01×0.98

+

0.01×0.01

=

0.021

21

2

1

2m

⊕m

({

Peter})

=

1m1

(B)匭m2

(C)0.02=

1

×(0.98

×0

+

0.98

×0.01)

=

0.49K=

1

匭[m({Peter})匭m({Peter})+m({Peter})匭m(Θ)]∑K

B

C

={

Peter

}（1）計算關(guān)于Peter的組合mass函數(shù)1

21

2

1

2m

⊕m

({

Paul}

)

=

1m1

(B)匭m2

(C)0.02=

1

×(0.01×0.01

+

0.01×0.01

+

0.01×0.01)

=

0.015K=

1

匭[m({Paul})匭m({Paul})+m({Paul})匭m(Θ)+m1

(Θ)匭m2

({Paul})]∑K

B

C

={

Paul}（2）計算關(guān)于Paul的組合mass函數(shù)1

2m1

(B)匭m2

(C)1

2

1

20.02=

1

×(0

×0.98

+

0.01×0.98)

=

0.49Km

⊕m

({

Mary}

)

=

1K=

1

匭[m({Mary})匭m({Mary})+m({Θ})匭m({Mary})]∑B

C

={

Mary}（3）計算關(guān)于Mary的組合mass函數(shù)1

21

21

2=

1

×0.01×0.01

=

0.0050.02此外，根據(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.020Km⊕m(Θ)=

1

∑m(B)匭m(C)B

C

=ΘK=

1

匭m(Θ)匭m(Θ)（4）計算關(guān)于Θ={Peter,Paul,Mary}的組合mass函數(shù)Bel({

Mary})

=

0.49;

Pl({

Mary}

)

=

0.49

+

0.005

=

0.495Bel(Θ)

=

Pl(Θ)

=

0.49

+

0.015

+

0.49

+

0.005

=

15.3

關(guān)于證據(jù)理論的理論模型解釋對Dempster-Shafer證據(jù)理論的解釋共有四種：上、下概率解釋（Upper

and

lower

probabilityinterpretation）；廣義化Bayes理論（Generalized

Bayesian

theory）解釋；隨機集理論（Random

sets）模型解釋；可傳遞信度模型（Transferable

beliefmodel，簡稱TBM）解釋；【注】第(1)~(3)這三種解釋都以“概率理論”為基礎(chǔ)的；而第(4)種，即

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

R.

P.

S.

Combining

ambiguous

evidence

with

respect

to

ambiguous

a

priori

knowledge,

I:

Boolean

logic.

IEEE

Tra

nsactions

on

Systems,

Man,

and

Cybernetics-

Part

A:

Systems

and

Huma

ns,

1996,

26(1):

27-41.Fixsen,

D.

and

Mahler,

R.

P.

S.

The

modified

Dempster-

Shafer

approach

toclassification.

IEEE

Tra

nsactions

on

Systems,

Man,

and

Cybernetics-

Part

A:Systems

and

Huma

ns,

1997,

27(1):

27-41.指出條件化(Conditional)Dempster-Shafer理論（簡稱CDS）和修改的(Modified)Dempster-Shafer理論（簡稱MDS）都是建立在隨機集（Random）理論基礎(chǔ)上的。補充說明：當(dāng)證據(jù)和先驗知識都是模糊的情況下，則條件化

Dempster-Shafer理論（CDS）是Bayes理論的廣義化，它完全是一種概率理論。當(dāng)證據(jù)和先驗知識都是統(tǒng)計獨立時，則條件化

Dempster-Shafer理論（CDS）的證據(jù)合成相當(dāng)于隨機條件事件的并（或交）。Yen在醫(yī)療專家系統(tǒng)GERTIS中提出了擴展（Extended）的Dempster-Shafer理論（簡稱EDS），實際上EDS就是一種CDS或MDS?！綴en,J.GERTIS:a

Dempster-Shafer

approach

to

diagnosing

hierarchical

hypotheses.Communica

tions

of

the

ACM,1989,32(5):573-585.】4、可傳遞信度模型（TBM）解釋Smets認(rèn)為從信度（Belief）的“更新/條件化”（Updating/Conditioning）方式中，可以看出各種DS理論模型的主要差別。(1)TBM模型Smets發(fā)現(xiàn)許多DS模型的研究者只看到了B

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

信度模型TBM”。|

A|饗“credal層”：位于底層，在該層中獲取信度并對其進行量化、賦值和更新處理。饗“pignistic層”：位于上層，它將credal層上的信度轉(zhuǎn)換成pignistic概率，并由此做出決策。只有必須做出決策時，pignistic層才出現(xiàn)。其中，

pignistic概率分布公式如下：p(x)

=

∑

m(A)x∈A癥Θ(2)TBM是一個雙層模型(3)TBM模型的意義饗TBM模仿了人類的“思維”和“行動”的區(qū)別，即模仿了“推理”和“行為”的差別：推理：表明信度是如何受證據(jù)影響的行動：從多個可行的行為方案中選擇一個似乎是最好的饗TBM實際上是一種層次化的遞進模型，體現(xiàn)了證據(jù)的層次化描述特征，它比較適用于需要逐層進行數(shù)據(jù)、特征和決策層融合的數(shù)據(jù)融合系統(tǒng)?！菊f明】：上述關(guān)于證據(jù)理論的四種典型的解釋模型，各有其適用領(lǐng)域，沒有哪一個能適用于所有的應(yīng)用領(lǐng)域，也不存在哪種模型更好的情況。5.4

基于DS理論的不確定性推理基于DS理論的不確定性推理步驟如下：步1：概率分配函數(shù)的確定步2：證據(jù)和知識的不確定性表示步3：組合證據(jù)不確定性的算法步4：不確定性的傳遞算法步5：得到最終的推理結(jié)果【注】：對基于DS理論的不確定性推理方法感興趣者，可參考王永慶《人工智能原理與方法》中的“5.5.2一個具體的不確定性推理模型”pp190-198；也可參考高濟教授的《基于知識的軟件智能化技術(shù)》一書中相關(guān)章節(jié)。5.5

證據(jù)理論的實現(xiàn)途徑Dempster合成公式的算法實現(xiàn)一直是困繞著DS理論的一個重點和難點問題，這直接關(guān)系到其實用性。1、實現(xiàn)途徑分類目前主要有如下三種途徑：（1）針對特殊的證據(jù)組織結(jié)構(gòu)，構(gòu)造相應(yīng)的快速算法Shaf

er（注：該方法比較簡單，故從略。感興趣者可參考Bar

net

t,等人的相關(guān)文獻(xiàn)。）近似計算修改DS方法2、Dempster合成規(guī)則的近似計算方法A癥Bm

(A)

=

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

braak的工作—“Bayes近似法”Voorbraak發(fā)現(xiàn)，如果mass函數(shù)的合成將產(chǎn)生一個B

ayes信任函數(shù)（即一個識別框架上的概率測度），則mass函數(shù)用它們的Bayes近似來代替，將不會影響Dempster合成規(guī)則的結(jié)果

Voorbraak給出了mass函數(shù)的B

ayes近似計算公式，即

∑m(B)

∑m(C)匭|

C

|，若A是單個假設(shè)集合

0,否則Voorbraak證明了如下結(jié)論：ma

s

s函數(shù)的Ba

yes近似的合成＝ma

s

s函數(shù)的合成的Baye

s近似

Voorbraak的“B

ayes近似法”的意義：對于那些只關(guān)心識別框架中的“元素”（即單個假設(shè)）而不是其“子集”（即多個假設(shè)組成的子集）的最終結(jié)論的情況是非常有用的，并且大大簡化了計算量?！咀ⅰ浚焊信d趣者可參考本課件給出的Voor

br

aak發(fā)表的相關(guān)論文。

Voobraak,F.A

computationally

efficient

approximation

of

Dempster-Shafertheory.International

J

ournal

of

Man-Machine

Study,1989,30:525-536.Bayes近似法（續(xù)）（2）Dubois&

Prade的工作—“一致近似法”一致近似法：Consonant

approximation特點：通過近似計算后的焦元是嵌套的，且焦元個數(shù)不超過識別框架中的假設(shè)個數(shù)。缺點：該方法不太適合用Dempster合成規(guī)則來進行計算，可能會產(chǎn)生很大的誤差。用途：適用于證據(jù)的表達(dá)?！咀ⅰ浚焊信d趣者可參考本章參考文獻(xiàn)中列的Duboi

s

&Pr

ade發(fā)表的相關(guān)論文。（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ù)值重新歸一化。該算法的特點：它既不給出Bayes

mass函數(shù)，也不給出一致mass函數(shù)，但它確實減少了焦元。5.6計算舉例重新調(diào)整表1中的BPA分布，并利用De

mps

t

er證據(jù)合成公式重新計算調(diào)整后的表1中的所有“？”內(nèi)容。

A癥Bm(A)=

m(C)匭|

C

|

假設(shè)在2001年美國發(fā)生“911事件”之前，布什總統(tǒng)分別接到美國中央情報局（CI

A）和國家安全局（NSA）兩大情報機構(gòu)發(fā)來的絕密情報，其內(nèi)容是關(guān)于中東地區(qū)的某些國家或組織企圖對美國實施突然的恐怖襲擊。CI

A和NSA得到的證據(jù)如表1所示。試計算并回答下列問題：請直接利用De

mps

t

er證據(jù)合成公式計算表1中的所有“？”內(nèi)容。根據(jù)BPA（mas

s函數(shù)值）的Ba

yes近似計算公式，

∑m(B)，若A是單個假設(shè)集合

∑

C癥Θ

0,否則情報部門恐怖分子中央情報局（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ù)實例解答：

首先，計算歸一化常數(shù)K。K=1藝∑m1

(B)匭m2

(C)B

∩C

=φ=1藝[m1

({本})匭m2

({薩})＋m1

({本})匭m2

({霍})＋...+m1

({本,薩})匭m2

({霍})]=1藝(0.4×0.2+0.4×0.05+...+0.1×0.05)=1藝0.27=

0.73實例解答（續(xù)1）

計算關(guān)于本拉登（“本”）的組合mass函數(shù)0.73=

0.4658=

1

(0.08

+

0.2

+

0.02

+

0.02

+

0.02)0.73=

1

(0.4

×0.2

+

0.4

×0.5

+

0.1×0.2

+

0.4

×0.05

+

0.1×0.2)

1∑m1

(B)匭m2

(C)m1

⊕m2

({本})＝

K1

2

1

2＝

1

[m({本})匭m({本})+m({本})匭m({本,薩})+B

C={本}Km1

({本,薩})匭m2

({本})+m1

({本})匭m2

({θ})+m1

({θ})匭m2

({本})]實例解答（續(xù)2）

同理可得：0.7310.73=

0.363=

(0.06

+

0.15

+

0.02

+

0.015

+

0.02)(0.3

×0.2

+

0.3

×0.5

+

0.2

×0.1

+

0.3

×0.05

+

0.2

×0.1)1∑m1

(B)匭m2

(C)B

C={薩}1

2=Km⊕m({薩})=

1實例解答（續(xù)3）

同理可得：0.73=

0.0205=

1

(0.005

+

0.005

+

0.005)0.73=

1

(0.1×0.05

+

0.1×0.05

+

0.1×0.05)∑m1

(B)匭m2

(C)B

C={霍}1

2Km⊕m({霍})=

1實例解答（續(xù)4）

同理可得：0.73=

0.1438=

1

(0.05

+

0.005

+

0.05)0.73=

1

(0.1×0.5

+

0.1×0.05

+

0.1×0.5)1

2Km⊕m({本,薩})=

1∑m1

(B)匭m2

(C)B

C={本，薩}實例解答（續(xù)5）

同理可得：0.73=

0.0068=

1

×0.0050.73=

1

(0.1×0.05)1

2=

1

[m(Θ)匭m(Θ)]1

21

2KKm⊕m(Θ)=

1

∑m(B)匭m(C)B

C

=Θ情報部門恐怖分子中央情報局（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ī)則合成后的mass計算BPA的Bayes近似

A癥Bm(A)

=

m(C)匭|

C

|

根據(jù)BPA的Bayes近似公式：

∑m(B)

∑，若A是單個假設(shè)集合

C癥Θ

0,否則BPA的Bayes近似（續(xù)1）1.3=

0.46150.4

×1

+

0.3

×1

+

0.1×1

+

0.1×2

+

0.1×30.6m1

({本})匭1＋m1

({薩})匭1＋m1

({霍})匭1＋m1

({本,薩})匭2＋m1

(Θ)匭30.4

+

0.1

+

0.1m1

({本})＋m1

({本,薩})＋m1

(Θ)1m({本})===BPA的Bayes近似（續(xù)2）1.3=

0.38460.4

×1

+

0.3

×1

+

0.1×1

+

0.1×2

+

0.1×30.5m1

({本})匭1＋m1

({薩})匭1＋m1

({霍})匭1＋m1

({本,薩})匭2＋m1

(Θ)匭30.3

+

0.1

+

0.1m1

({薩})＋m1

({本,薩})＋m1

(Θ)1m({薩})===BPA的Bayes近似（續(xù)3）1.3=

0.15380.4

×1

+

0.3

×1

+

0.1×1

+

0.1×2

+

0.1×30.2m1

({本})匭1＋m1

({薩})匭1＋m1

({霍})匭1＋m1

({本,薩})匭2＋m1

(Θ)匭30.1

+

0.1m1

({霍})＋m1

(Θ)1m({霍})===BPA的Bayes近似（續(xù)4）1.6=

0.46880.2

×1

+

0.2

×1

+

0.05

×1

+

0.5

×2

+

0.05

×30.75m2

({本})匭1＋m2

({薩})匭1＋m2

({霍})匭1＋m2

({本,薩})匭2＋m2

(Θ)匭30.2

+

0.5

+

0.05m2

({本})＋m2

({本,薩})＋m2

(Θ)2m({本})===BPA的Bayes近似（續(xù)5）1.6=

0.46880.2

×1

+

0.2

×1

+

0.05

×1

+

0.5

×2

+

0.05

×30.75m2

({本})匭1＋m2

({薩})匭1＋m2

({霍})匭1＋m2

({本,薩})匭2＋m2

(Θ)匭30.2

+

0.5

+

0.05m2

({薩})＋m2

({本,薩})＋m2

(Θ)2m({薩})===BPA的Bayes近似（續(xù)6）1.6=

0.06250.2

×1

+

0.2

×1

+

0.05

×1

+

0.5

×2

+

0.05

×30.1m2

({本})匭1＋m2

(