证据理论石峰2019/10/112证据理论(TheoryofEvidence)也称为D-S(Dempster-Shafer)理论。证据理论(D-S理论)最早是基于德姆斯特(A.P.Dempster)所做的工作,他试图用一个概率范围而不是单个的概率值去模拟不确定性。证据理论1、证据理论的诞生和形成诞生:源于20世纪60年代美国哈佛大学数学家A.P.Dempster在利用上、下限概率来解决多值映射问题方面的研究工作。自1967年起连续发表了一系列论文,标志着证据理论的正式诞生。形成:Dempster的学生G.Shafer对证据理论做了进一步的发展,引入信任函数概念,形成了一套基于“证据”和“组合”来处理不确定性推理问题的数学方法,并于1976年出版了《证据的数学理论》(AMathematicalTheoryofEvidence),这标志着证据理论正式成为一种处理不确定性问题的完整理论。2019/10/114莎弗(G.Shafer)进一步拓展了Dempster的工作,这一拓展称为证据推理(EvidentialReasoning),用于处理不确定性、不精确以及间或不准确的信息。由于证据理论将概率论中的单点赋值扩展为集合赋值,弱化了相应的公理系统,满足了比概率更弱的要求,因此可看作一种广义概率论。证据理论证据理论的发展简况2、证据理论的名称证据理论(EvidentialTheory)Dempster-Shafer理论Dempster-Shafer证据理论DS(或D-S)理论其它叫法:Dempster规则Dempster合成规则Dempster证据合成规则3、证据理论的核心、优点及适用领域核心:Dempster合成规则,这是Dempster在研究统计问题时首先提出的,随后Shafer把它推广到更为一般的情形。优点:由于在证据理论中需要的先验数据比概率推理理论中的更为直观、更容易获得,再加上Dempster合成公式可以综合不同专家或数据源的知识或数据,这使得证据理论在专家系统、信息融合等领域中得到了广泛应用。适用领域:信息融合、专家系统、情报分析、法律案件分析、多属性决策分析,等等。4、证据理论的局限性要求证据必须是独立的,而这有时不易满足证据合成规则没有非常坚固的理论支持,其合理性和有效性还存在较大的争议计算上存在着潜在的指数爆炸问题2019/10/118在证据理论中,引入了信任函数来度量不确定性,并引用似然函数来处理由于“不知道”引起的不确定性,并且不必事先给出知识的先验概率,与主观Bayes方法相比,具有较大的灵活性。因此,证据理论得到了广泛的应用。同时,可信度可以看作是证据理论的一个特例,证据理论给了可信度一个理论性的基础。证据理论2019/10/119证据的不确定性在D-S理论中,可以分别用信任函数、似然函数及类概率函数来描述知识的精确信任度、不可驳斥信任度及估计信任度,即可以从各个不同角度刻画命题的不确定性。D-S理论采用集合来表示命题,先建立命题与集合之间的一一对应关系,把命题的不确定性问题转化为集合的不确定性问题。2019/10/1110设Ω为变量x的所有可能取值的有限集合(亦称样本空间),且Ω中的每个元素都相互独立,则由Ω的所有子集构成的集合称为幂集,记为2Ω。当Ω中的元素个数为N时,则其幂集的元素个数为2N,且其中的每一个元素A都对应于一个关于x的命题,称该命题为“x的值在A中”。证据的不确定性2019/10/1111如,用x代表所看到的颜色,Ω={红,黄,蓝},则A={红}表示“x是红色”;若A={红,蓝},则表示“x或者是红色,或者是蓝色”。证据的不确定性2019/10/1112l.概率分配函数定义设函数m:2Ω→[0,1],且满足则称m是2Ω上的概率分配函数,m(A)称为A的基本概率数。m(A)表示依据当前的环境对假设集A的信任程度。1)(0)(AAmm2019/10/1113对于上面给出的有限集Ω={红,黄,蓝},若定义2Ω上的一个基本函数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}分别是幂集中各个子集的基本概率数。显然m满足概率分配函数的定义。例子说明2019/10/1114(1)概率分配函数的作用是把Ω的任意一个子集都映射为[0,1]上的一个数m(A)。当A包含于Ω且A由单个元素组成时,m(A)表示对A的精确信任度;当A包含于Ω、A≠Ω,且A由多个元素组成时,m(A)也表示对A的精确信任度,但却不知道这部分信任度该分给A中哪些元素;当A=Ω时,则m(A)是对Ω的各个子集进行信任分配后剩下的部分,它表示不知道该如何对它进行分配。对概率分配函数的几点说明2019/10/1115以Ω={红,黄,蓝}为例说明。当A={红}时,由于m(A)=0.3,它表示对命题“x是红色”的精确信任度为0.3。当A={红,黄}时,由于m(A)=0.2,它表示对命题“x或者是红色,或者是黄色”的精确信任度为0.2,却不知道该把这0.2分给{红}还是分给{黄}。当A=Ω={红,黄,蓝}时,由于m(A)=0.2,表示不知道该对这0.2如何分配,但它不属于{红},就一定属于{黄}或{蓝},只是基于现有的知识,还不知道该如何分配而已。例如2019/10/1116(2)m是2Ω上而非Ω上的概率分布,所以基本概率分配函数不是概率,它们不必相等,而且m(A)≠l-m(┐A)。事实上m({红})+m({黄})+m({蓝})=0.3+0+0.1=0.4≠1。概率分配函数的几点说明2019/10/11172.信任函数定义信任函数(BeliefFunction)Bel:2Ω→[0,1]对任意的有,Bel(A)表示当前环境下,对假设集A的信任程度,其值为A的所有子集的基本概率之和,表示对A的总的信任度。2019/10/1118以Ω={红,黄,蓝}为例说明。Bel({红,黄})=m({红})+m({黄})+m({红,黄})=0.3+0+0.2=0.5。当A为单一元素组成的集合时,Bel(A)=m(A)。如果命题“x在B中”成立,必带有命题“x在A中”成立。Bel(A)函数又称为下限函数。例如2019/10/11193.似然函数定义似然函数(PlausibilityFunction)对任意的有:Pl(A)=1-Bel(┐A)其中,┐A=Ω-A。似然函数又称为不可驳斥函数或上限函数。由于Bel(A)表示对A为真的信任度,Bel(┐A)表示对┐A的信任度,即A为假的信任度,因此,Pl(A)表示对A为非假的信任度。]1,0[2:Pl2019/10/1120以Ω={红,黄,蓝}为例说明。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,则是知道非假,但却不能肯定为真的那部分。例如2019/10/1121推论该式可推广为BBmPl}{)(})({红红可见,2019/10/1122因此命题“x在A中”的似然性,由与命题“x在B中”有关的m值确定,其中命题“x在B中”并不会使得命题“x不在A中”成立。所以一个事件的似然性是建立在对其相反事件不信任的基础上的。BABmAPl)()(推论2019/10/1123(1)Bel(Φ)=0,Bel(Ω)=l,Pl(Φ)=O,Pl(Ω)=1.(2)如果,则Bel(A)≤Bel(B),Pl(A)≤Pl(B)。(3),Pl(A)≥Bel(A)。(4),Bel(A)+Bel(┐A)≤l,Pl(A)+Pl(┐A)≥1.BAAA信任函数和似然函数有如下的性质2019/10/1124由于Bel(A)和Pl(A)分别表示A为真的信任度和A为非假的信任度,因此,可分别称Bel(A)和Pl(A)为对A信任程度的下限和上限,记为A(Bel(A),Pl(A))Pl(A)-Bel(A)表示既不信任A,也不信任┐A的程度,即对于A是真是假不知道的程度。下限上限信任区间2019/10/1125•如,在前面的例子中,曾求过Bel({红})=0.3,Pl({红})=0.8,•因此有{红}(0.3,0.8)•它表示对{红}的精确信任度为0.3,不可驳斥部分为0.8,肯定不是{红}的为0.2。信任区间2019/10/11264.假设集A的类概率函数f(A)其中|A|、|Ω|分别表示A和Ω中包含元素的个数。类概率函数f(A)也可以用来度量证据A的不确定性。))()((||||)()(ABelAPlAABelAf2019/10/1127f(A)有如下的性质•(1)•(2)•(3)Bel(A)≤f(A)≤Pl(A),forA⊆Ω•(4)f(┐A)=1-f(A),forA⊆Ω1)(,0)(ffAforAf,1)(0证据E的不确定性可以用类概率函数f(E)表示,原始证据的f(E)应由用户给出,作为中间结果的证据可以由下面的不确定性传递算法确定。2019/10/1128证据的组合函数在实际问题中,对于相同的证据,由于来源不同,可能会得到不同的概率分配函数。例如,考虑Ω={红,黄},假设从不同知识源得到的概率分配函数分别为:m1(φ,{红},{黄},{红,黄})=(0,0.4,0.5,0.1)m2(φ,{红},{黄},{红,黄})=(0,0.6,0.2,0.2)在这种情况下,需要对它们进行组合。2019/10/1129•定义设m1和m2是两个不同的概率分配函数,则其正交和m=m1⊕m2满足)()()()(12121ymxmymxmKyxyx其中:正交和概念2019/10/1130•如果K≠O,则正交和m也是一个概率分配函数;•如果K=0,则不存在正交和m,称m1与m2矛盾。注意2019/10/1131•设Ω={a,b},且从不同知识源得到的概率分配函数分别为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=m1⊕m2。例32019/10/1132•解:先求K再求m(φ,{a},{b},{a,b}),由于2019/10/1133•同理可得:m({b})=0.43,m({a,b})=0.03故有m(φ,{a},{b},{a,b})=(0,0.54,0.43,0.03)2019/10/1134规则的不确定性具有不确定性的推理规则可表示为:IfEThenH,CF其中,H为假设,E为支持H成立的假设集,它们是命题的逻辑组合。CF为可信度因子。H可表示为:H={a1,a2,…,am},ai∈Ω(i=l,2,…,m),H为假设集合Ω的子集。2019/10/1135CF={c1,c2,…,cm},ci用来描述前提E成立时ai的可信度。CF应满足如下条件:规则的不确定性2019/10/1136•定义对于不确定性规则:IfEThenH,CF定义:m({ai})=f(E)·ci(i=l,2,…,m)或表示为m({a1},{a2},…,{am})=(f(E)·c1,f(E)·c2,…,f(E)·cm)规则的不确定性2019/10/1137•规定:•而对于Ω的所有其他子集H,均有:m(H)=0。•当H为Ω的真子集时,有:进一步可以计算Pl(H)和f(H)。2019/10/1138不确定性的组合•当规则的前提(证据)E是多个命题的合取或析取时,定义:)}(,),(),(min{)(2121nnEfEfEfEEEf)}(,),(),(max{)(2121nnEfEfEfEEEf2019/10/1139•当有多条规则支持同一结论时,如果H={a1,a2,…,an},则:IfE1Th