证据理论

证据理论石峰2021/3/212证据理论(TheoryofEvidence)也称为D-S(Dempster-Shafer)理论。证据理论(D-S理论)最早是基于德姆斯特(A.P.Dempster)所做的工作，他试图用一个概率范围而不是单个的概率值去模拟不确定性。证据理论1、证据理论的诞生和形成诞生：源于20世纪60年代美国哈佛大学数学家A.P.Dempster在利用上、下限概率来解决多值映射问题方面的研究工作。自1967年起连续发表了一系列论文，标志着证据理论的正式诞生。形成：Dempster的学生G.Shafer对证据理论做了进一步的发展，引入信任函数概念，形成了一套基于“证据”和“组合”来处理不确定性推理问题的数学方法，并于1976年出版了《证据的数学理论》(AMathematicalTheoryofEvidence)，这标志着证据理论正式成为一种处理不确定性问题的完整理论。2021/3/214莎弗(G.Shafer)进一步拓展了Dempster的工作，这一拓展称为证据推理(EvidentialReasoning)，用于处理不确定性、不精确以及间或不准确的信息。由于证据理论将概率论中的单点赋值扩展为集合赋值，弱化了相应的公理系统，满足了比概率更弱的要求，因此可看作一种广义概率论。证据理论证据理论的发展简况2、证据理论的名称证据理论(EvidentialTheory)Dempster-Shafer理论Dempster-Shafer证据理论DS(或D-S)理论其它叫法：Dempster规则Dempster合成规则Dempster证据合成规则3、证据理论的核心、优点及适用领域核心：Dempster合成规则，这是Dempster在研究统计问题时首先提出的，随后Shafer把它推广到更为一般的情形。优点：由于在证据理论中需要的先验数据比概率推理理论中的更为直观、更容易获得，再加上Dempster合成公式可以综合不同专家或数据源的知识或数据，这使得证据理论在专家系统、信息融合等领域中得到了广泛应用。适用领域：信息融合、专家系统、情报分析、法律案件分析、多属性决策分析，等等。4、证据理论的局限性要求证据必须是独立的，而这有时不易满足证据合成规则没有非常坚固的理论支持，其合理性和有效性还存在较大的争议计算上存在着潜在的指数爆炸问题2021/3/218在证据理论中，引入了信任函数来度量不确定性，并引用似然函数来处理由于“不知道”引起的不确定性，并且不必事先给出知识的先验概率，与主观Bayes方法相比，具有较大的灵活性。因此，证据理论得到了广泛的应用。同时，可信度可以看作是证据理论的一个特例，证据理论给了可信度一个理论性的基础。证据理论2021/3/219证据的不确定性在D-S理论中，可以分别用信任函数、似然函数及类概率函数来描述知识的精确信任度、不可驳斥信任度及估计信任度，即可以从各个不同角度刻画命题的不确定性。D-S理论采用集合来表示命题，先建立命题与集合之间的一一对应关系，把命题的不确定性问题转化为集合的不确定性问题。2021/3/2110设Ω为变量x的所有可能取值的有限集合(亦称样本空间)，且Ω中的每个元素都相互独立，则由Ω的所有子集构成的集合称为幂集，记为2Ω。当Ω中的元素个数为N时，则其幂集的元素个数为2N，且其中的每一个元素A都对应于一个关于x的命题，称该命题为“x的值在A中”。证据的不确定性2021/3/2111如，用x代表所看到的颜色，Ω={红，黄，蓝}，则A={红}表示“x是红色”；若A={红，蓝}，则表示“x或者是红色，或者是蓝色”。证据的不确定性2021/3/2112l.概率分配函数定义设函数m:2Ω→[0,1]，且满足则称m是2Ω上的概率分配函数，m(A)称为A的基本概率数。m(A)表示依据当前的环境对假设集A的信任程度。1)(0)(AAmm2021/3/2113对于上面给出的有限集Ω={红，黄，蓝}，若定义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满足概率分配函数的定义。例子说明2021/3/2114（1）概率分配函数的作用是把Ω的任意一个子集都映射为[0,1]上的一个数m(A)。当A包含于Ω且A由单个元素组成时，m(A)表示对A的精确信任度；当A包含于Ω、A≠Ω,且A由多个元素组成时，m(A)也表示对A的精确信任度，但却不知道这部分信任度该分给A中哪些元素；当A=Ω时，则m(A)是对Ω的各个子集进行信任分配后剩下的部分，它表示不知道该如何对它进行分配。对概率分配函数的几点说明2021/3/2115以Ω={红,黄,蓝}为例说明。当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如何分配，但它不属于{红}，就一定属于{黄}或{蓝}，只是基于现有的知识，还不知道该如何分配而已。例如2021/3/2116（2）m是2Ω上而非Ω上的概率分布，所以基本概率分配函数不是概率，它们不必相等，而且m(A)≠l-m(┐A)。事实上m({红})+m({黄})+m({蓝})=0.3+0+0.1=0.4≠1。概率分配函数的几点说明2021/3/21172.信任函数定义信任函数(BeliefFunction)Bel:2Ω→[0,1]对任意的有,Bel(A)表示当前环境下，对假设集A的信任程度，其值为A的所有子集的基本概率之和，表示对A的总的信任度。2021/3/2118以Ω={红,黄,蓝}为例说明。Bel({红,黄})=m({红})+m({黄})+m({红，黄})=0.3+0+0.2=0.5。当A为单一元素组成的集合时,Bel(A)=m(A)。如果命题“x在B中”成立，必带有命题“x在A中”成立。Bel(A)函数又称为下限函数。例如2021/3/21193.似然函数定义似然函数(PlausibilityFunction)对任意的有:Pl(A)=1-Bel(┐A)其中，┐A=Ω-A。似然函数又称为不可驳斥函数或上限函数。由于Bel(A)表示对A为真的信任度，Bel(┐A)表示对┐A的信任度，即A为假的信任度，因此，Pl(A)表示对A为非假的信任度。]1,0[2:Pl2021/3/2120以Ω={红,黄,蓝}为例说明。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，则是知道非假，但却不能肯定为真的那部分。例如2021/3/2121推论该式可推广为BBmPl}{)(})({红红可见，2021/3/2122因此命题“x在A中”的似然性，由与命题“x在B中”有关的m值确定，其中命题“x在B中”并不会使得命题“x不在A中”成立。所以一个事件的似然性是建立在对其相反事件不信任的基础上的。BABmAPl)()(推论2021/3/2123(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.BAAA信任函数和似然函数有如下的性质2021/3/2124由于Bel(A)和Pl(A)分别表示A为真的信任度和A为非假的信任度，因此，可分别称Bel(A)和Pl(A)为对A信任程度的下限和上限，记为A(Bel(A),Pl(A))Pl(A)-Bel(A)表示既不信任A，也不信任┐A的程度，即对于A是真是假不知道的程度。下限上限信任区间2021/3/2125•如，在前面的例子中，曾求过Bel({红})=0.3，Pl({红})=0.8，•因此有{红}（0.3，0.8）•它表示对{红}的精确信任度为0.3，不可驳斥部分为0.8，肯定不是{红}的为0.2。信任区间2021/3/21264.假设集A的类概率函数f(A)其中|A|、|Ω|分别表示A和Ω中包含元素的个数。类概率函数f(A)也可以用来度量证据A的不确定性。))()((||||)()(ABelAPlAABelAf2021/3/2127f(A)有如下的性质•(1)•(2)•(3)Bel(A)≤f(A)≤Pl(A),forA⊆Ω•(4)f(┐A)=1-f(A),forA⊆Ω1)(,0)(ffAforAf,1)(0证据E的不确定性可以用类概率函数f(E)表示，原始证据的f(E)应由用户给出,作为中间结果的证据可以由下面的不确定性传递算法确定。2021/3/2128证据的组合函数在实际问题中，对于相同的证据，由于来源不同，可能会得到不同的概率分配函数。例如，考虑Ω={红，黄}，假设从不同知识源得到的概率分配函数分别为:m1(φ,{红},{黄},{红,黄})=(0,0.4,0.5,0.1)m2(φ,{红},{黄},{红,黄})=(0,0.6,0.2,0.2)在这种情况下，需要对它们进行组合。2021/3/2129•定义设m1和m2是两个不同的概率分配函数，则其正交和m=m1⊕m2满足)()()()(12121ymxmymxmKyxyx其中:正交和概念2021/3/2130•如果K≠O，则正交和m也是一个概率分配函数；•如果K=0，则不存在正交和m，称m1与m2矛盾。注意2021/3/2131•设Ω={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。例32021/3/2132•解:先求K再求m(φ,{a},{b},{a,b})，由于2021/3/2133•同理可得:m({b})=0.43，m({a,b})=0.03故有m(φ,{a},{b},{a,b})=(0，0.54，0.43，0.03)2021/3/2134规则的不确定性具有不确定性的推理规则可表示为:IfEThenH,CF其中，H为假设，E为支持H成立的假设集，它们是命题的逻辑组合。CF为可信度因子。H可表示为:H={a1,a2,…,am},ai∈Ω(i=l,2,…,m)，H为假设集合Ω的子集。2021/3/2135CF={c1,c2,…,cm}，ci用来描述前提E成立时ai的可信度。CF应满足如下条件:规则的不确定性2021/3/2136•定义对于不确定性规则:IfEThenH，CF定义:m({ai})=f(E)·ci(i=l,2,…,m)或表示为m({a1},{a2},…,{am})=(f(E)·c1,f(E)·c2,…,f(E)·cm)规则的不确定性2021/3/2137•规定:•而对于Ω的所有其他子集H，均有:m(H)=0。•当H为Ω的真子集时，有:进一步可以计算Pl(H)和f(H)。2021/3/2138不确定性的组合•当规则的前提(证据)E是多个命题的合取或析取时，定义:)}(,),(),(min{)(2121nnEfEfEfEEEf)}(,),(),(max{)(2121nnEfEfEfEEEf2021/3/2139•当有多条规则支持同一结论时，如果H={a1,a2,…,an}，则:IfE1ThenH，CF1(CF1={c11,c12,…,c1n})IfE2Th