ch4可信度与证据理论.ppt

1,可信度方法是美国斯坦福大学等人在确定性理论的基础上，结合概率论等提出的一种不确定性推理方法。1976年在专家系统MYCIN中首先应用，它是不确定推理方法中应用最早、且简单有效的方法之一。什么是可信度？根据经验对一个事物或现象为真的相信程度称为可信度。可信度也称作确定性因子。用以度量知识和证据的不确定性。可信度具有较大的主观性和经验性。,C-F(Certainty Factor)模型,2,1、知识不确定性的表示 在该模型中，知识是用产生式规则表示的，不确定性以可信度CF(H,E)表示。一般形式：IF E THEN H(CF(H,E)其中：（1）E是知识的前提或称为证据，可以是命题的合取、析取组合等。（2）结论H可为单一命题，也可以是复合命题。（3）CF(H,E)为确定性因子，简称可信度，用以量度规则的确定性（可信）程度。,C-F模型,3,在MYCIN中 CF(H,E)=MB(H,E)-MD(H,E)其中：MB(H,E)(Measure Belief)指信任增长度，表示因与E匹配的证据出现，使H为真的信任增长度。定义如下：,C-F模型,4,MD(H,E)(Measure Disbelief)指不信增长度，表示因与E匹配的证据出现，使H为真的不信任增长度。定义如下：,C-F模型,5,当p(H/E)p(H)时，表示证据E支持结论H，则有MB0，MD=0；当p(H/E)0；当p(H/E)p(H)时，表示E对H无影响，则有MBMD0。MB与MD的值域为0,1。因此，MB和MD是互斥的。即：当MB0时，MD=0 当MD0时，MB=0,C-F模型,6,根据CF(H,E)的定义及MD和MB的互斥性，可以得到CF(H,E)的计算公式:,C-F模型,7,从CF(H,E)的计算公式可以看出它的意义：（1）若CF(H,E)0，则P(H/E)P(H)；MB0，MD=0。说明CF(H,E)的值越大，增加H为真的可信度就越大。若CF(H,E)=1，P(H/E)=1，说明由于E所对应的证据出现使H为真。（2）若CF(H,E)0。说明CF(H,E)的值越小，增加H为假的可信度就越大。若CF(H,E)=-1，P(H/E)=0，说明由于E所对应的证据出现使H为假。,C-F模型,8,（3）若CF(H,E)=0，则P(H/E)=P(H)；MBMD0。说明E与H无关。由公式知，计算CF(H,E)需要知道P(H)与P(H/E)，然而，在实际应用中这两个值很难获得，而是在建立规则库时由领域专家凭经验主观确定的。,C-F模型,9,2、证据的不确定性表示 证据E的可信度CF(E)取值为-1,1。对于初始证据，若对它的所有观察S能肯定它为真，则使CF(E)=1；若肯定它为假，则使CF(E)=-1；若它以某种程度为真，则使CF(E)为（0，1）中某一值，若对它还未获得任何相关的观察，此时可看作观察S与它无关，则使CF(E)=0。,C-F模型,10,类似于规则的不确定性，证据的可信度往往可由领域专家凭经验主观确定。证据的可信度值来源于两种情况：（1）初始证据由领域专家或用户给出；（2）中间结论由不确定性传递算法计算得到。,C-F模型,11,3、组合证据不确定性的算法(1)当组合证据是多个单一证据的合取时，即：E=E1 AND E2 ANDAND En 则CF(E)=minCF(E1),CF(E2)CF(En)(2)当组合证据是多个单一证据的析取时，即：E=E1 OR E2 OROR En 则CF(E)=maxCF(E1),CF(E2)CF(En),C-F模型,12,4、不确定性的传递不确定性的传递算法定义如下：CF(H)=CF(H,E)max0，CF(E)由上式可以看出:(1)CF(E)0时,CF(H)=0,说明该模型没有考虑证据为假时对结论H所产生的影响。（2）CF(E)=1时,CF(H)=CF(H,E),说明规则可信度CF(H,E)就是证据为真时的结论H的可信度。,C-F模型,13,5、结论不确定性的合成算法 若由多条不同知识推出了相同的结论，但可信度不同，则可用合成算法求出综合的可信度。由于对多条知识的综合可通过两两的合成实现，所以下面只考虑两条知识的情况。设有如下知识：IF E1 THEN H（CF(H,E1)IF E2 THEN H（CF(H,E2)则结论H的综合可信度由两步算出：,C-F模型,14,（1）首先分别对每一条知识求出CF(H)CF1(H)=CF(H,E1)max0,CF(E1)CF2(H)=CF(H,E2)max0,CF(E2),(2)求出E1和E2对H的综合影响所形成的可信度CF1,2（H）,C-F模型,15,例 设有如下一组知识:r1:IF E1 THEN H(0.8)r2:IF E2 THEN H(0.6)r3:IF E3 THEN H(-0.5)r4:IF E4 AND(E5 OR E6)THEN E1(0.7)r5:IF E7 AND E8 THEN E3(0.9),已知:CF(E2)=0.8 CF(E4)=0.5 CF(E5)=0.6 CF(E6)=0.7 CF(E7)=0.6 CF(E8)=0.9求:CF(H)=?,C-F模型,16,解:由r4:CF(E1)=0.7max0,CFE4 AND(E5 OR E6)=0.35由r5:CF(E3)=0.54由r1:CF1(H)=0.28由r2:CF2(H)=0.48由r3:CF3(H)=-0.27根据结论不确定性的合成算法得到:CF1,2(H)=CF1(H)+CF2(H)+CF1(H)CF2(H)=0.63,C-F模型,17,1、知识的不确定性表示 IF E1(1)AND E2(2)AND En(n)THEN H(CF(H,E),)其中，i是加权因子，且,加权不确定性推理,是阈值，01，只有当CF(E)时才可使用该条知识。,18,2、组合证据不确定性算法,E=E1(1)AND E2(2)AND En(n),加权不确定性推理,19,3、不确定性的传递算法 CF(H)=CF(H,E)CF(E),加权不确定性推理,例如：设有下列知识：IF 该动物有蹄（0.3）AND 该动物有长腿（0.2）AND 该动物有长颈（0.2）AND 该动物是黄褐色（0.13）AND 该动物身上有暗黑色斑点（0.13）AND 该动物的体重 200kg（0.04）THEN 该动物是长颈鹿（0.95,0.8）,20,证据为：E1:该动物有蹄（1）E2:该动物有长腿（1）E3:该动物有长颈（1）E4:该动物是黄褐色（0.8）E5:该动物身上有暗黑色斑点（0.6）试问该动物是什么动物？,加权不确定性推理,21,解：CF(E)=0.31+0.21+0.21+0.130.8+0.130.6=0.882因=0.8，而CF(E)，所以知识可以使用，推出该动物是长颈鹿，其可信度为：CF(H)=CF(H,E)CF(E)=0.95 0.882=0.84,加权不确定性推理,22,4、冲突消解设有下述知识r1:IF E1(1)THEN H1(CF(H1,E1),1)r2:IF E2(2)THEN H2(CF(H2,E2),2)且 CF(E1(1)1，CF(E2(2)2若CF(E1(1)CF(E2(2)，则优先使用r1进行推理。,加权不确定性推理,23,例如：设有下列知识：r1:IF E1(0.6)AND E2(0.4)THEN E6(0.8,0.75)r2:IF E3(0.5)AND E4(0.3)AND E5(0.2)THEN E7(0.7,0.6)r3:IF E6(0.7)AND E7(0.3)THEN H(0.75,0.6)已知：CF(E1)=0.9,CF(E2)=0.8,CF(E3)=0.7,CF(E4)=0.6,CF(E5)=0.5求：CF(H),加权不确定性推理,24,解：由r1 有：CF(E1(0.6)AND E2(0.4)=0.60.9+0.40.8=0.86因为1=0.75，CF(E1 AND E2)1故r1可以使用。,加权不确定性推理,25,由r2 有：CF(E3(0.5)AND E4(0.3)AND E5(0.2)=0.50.7+0.30.6+0.20.5=0.63因为2=0.6，CF(E3 AND E4 AND E5)2故r2可以使用。,加权不确定性推理,因为 CF(E1 AND E2)CF(E3 AND E4 AND E5)所以r1先被启用，然后才能启用r2。,26,由r1 有：CF(E6)=0.80.86=0.694由r2 有：CF(E7)=0.70.63=0.441,由r3 有：CF(E6(0.7)AND E7(0.3)=0.70.694+0.30.441=0.6181因为CF(E6 AND E7)3，所以r3被启用，得到：CF(H)=CF(H,E)CF(E)=0.750.6181=0.463575,加权不确定性推理,27,D-S证据理论,D-S证据理论是由丹普斯特（Dempster）提出，并由他的学生莎弗（Shafer）改进的一种不确定推理模型。该理论引入信任函数而非采用概率来量度不确定性，并引用似然函数来处理由不知道而引起的不确定性，从而在实现不确定推理方面显示出很大的灵活性，受到人们的重视。用集合表示命题，命题的不确定性问题转化为集合的不确定性问题。将概率论中的单点赋值扩展为集合赋值，满足比概率更弱的要求，可看作一种广义概率论。,28,不确定性方法比较,可信度方法：证据、结论和知识的不确定性以可信度进行度量。主观Bayes方法：证据与结论的不确定性以概率形式度量，知识的不确定性以数值对（LS,LN）进行度量。DS理论：证据与结论用集合表示，不确定性度量用信任函数与似然函数表示；知识的不确定性通过一个集合形式的可信度因子表示。,29,举 例,假设D是所有可能疾病的集合，医生为进行诊断而进行的各种检查就是获得所需证据的过程，检查得到的结果就是获得的证据，这些证据构成了证据集合E。根据证据集合E中的这些证据，就可以判断病人的疾病。通常，有的证据所支持的不只是一种疾病，而是多种疾病，这些疾病构成集合D中的元素，可以构成D的一个子集H，H就是结论集合。,30,证据理论是用集合表示命题的。设D是变量x的样本空间，其中具有n个元素，在任一时刻变量x的取值都会落入某个子集，也就是说，D的任一子集A都对应于一个关于x的命题，该命题为“x的值在A中”，所以用集合A表示该命题。,D-S证据理论,31,例如：x代表颜色，D=红，黄，蓝。如果A=红，表示“x是红色”。如果A=黄，蓝，表示“x或者是红色，或者是蓝色”。,D-S证据理论,32,1、概率分配函数 设论域D为所有可能假设（表示为原子命题的结论）的有限集合，且D中的元素间是互斥的，则可以在D的幂集2D上定义一个基本概率分配函数M：2D 0,1，满足 则称M是2D上的概率分配函数，M(A)称为A的基本概率数。,D-S证据理论,33,概率分配函数的作用,将D上的任意一个子集A都映射为0,1上的一个数M(A)。当A对应一个命题时，M(A)即是对相应命题不确定性的度量。注意：概率分配函数不是概率，样本空间D上的各元素的基本概率数之和不一定等于1。,34,（1）设样本空间D中有n个元素，则D中子集的个数为2n个，定义中的2D则表示这些子集构成的集合。例如：设D=红，黄，蓝，则它的子集有8个：A1=红，A2=黄，A3=蓝，A4=红，黄，A5=红，蓝，A6=蓝，黄，A7=红，黄，蓝，A8=。,D-S证据理论,35,（2）概率分配函数把D的任意一个子集A都映射为0，1上的一个数M(A)，当AD时，M(A)表示对相应命题的精确信任程度。概率分配函数事实就上是对D的各个子集进行信任分配。例如：A=红，M(A)=0.3 表示对命题“A是红色”的精确信任度为0.3。,D-S证据理论,36,（3）概率分配函数不是概率。例如：M(红)=0.3，M(黄)=0，M(蓝)=0.1，M(红，黄)=0.2，M(红，蓝)=0.2，M(蓝，黄)=0.1，M(红，黄，蓝)=0.1，M()=0。M(红)+M(黄)+M(蓝)=0.4 若按概率的要求，这三者之和应等于1。,D-S证据理论,37,2、信任函数 Bel 信任函数用来对命题的不确定性进行度量。定义5.2命题的信任函数Bel：2D 0,1，对于任意的AD，有 Bel函数又称为下限函数，Bel(A)表示对命题A为真的信任程度，为A所有子集的基本概率数之和。,D-S证据理论,38,易知 Bel()=0，Bel(D)=1；当 A为单一元素集时，Bel(A)=M(A)。例如：对于上例可以求出：Bel(红)=M(红)=0.3 Bel(红，黄)=M(红)+M(黄)+M(红，黄)=0.3+0+0.2=0.5,D-S证据理论,39,3、似然函数Pl 似然函数Pl：2D 0,1，且 Pl(A)=1 Bel(A)对所有的AD Pl(A)表示对A为非假（不否定A）的信任程度，它是所有与A相交的子集的基本概率数之和。似然函数又称为上限函数。在上例中，Pl(红)=1-Bel(蓝，黄)=1-0.2=0.8,D-S证据理论,40,D-S证据理论,Pl(A)=1 Bel(A),41,Bel(A)表示对命题A为真的信任程度；Bel(A)表示对命题 A为真的信任程度，即表示A为假的信任程度；Pl(A)1 Bel(A)表示对A为非假的信任程度。可以看到：A不为假并不代表A一定为真，也就是说对A不为假的信任程度应该大于对A为真的信任程度。,D-S证据理论,42,4、信任函数与似然函数的关系 似然函数有以下特性：Pl(A)Bel(A)Pl()=0，Pl(D)=1 由于Bel(A)表示对A为真的信任程度，Pl(A)表示对A为非假的信任程度，所以 Pl(A)-Bel(A)表示既不为假、又不为真的信任程度或者说既不信任A也不信任A的程度，即是对A是真是假不知道的程度。可以用区间Bel(A),Pl(A)来综合描述A的不确定性。,D-S证据理论,43,易知存在三个特殊的区间：Bel(A),Pl(A)=1,1，表示信任A为真；Bel(A),Pl(A)=0,0，表示信任A为假；Bel(A),Pl(A)=0,1，表示对A是真是假一无所知。Bel(A),Pl(A)=0.25,0.85，表示对A为真的信任度为0.25,A为假的信任度为0.15。0.85-0.25=0.6表示对A不知道的程度。,D-S证据理论,44,5、概率分配函数的正交和 有时对同样的证据会得到两个不同的概率分配函数，例如，对样本空间D=a，b，从不同的来源分别得到如下两个概率分配函数：M1(a)=0.3 M1(b)=0.6 M1(a,b)=0.1 M1()=0M2(a)=0.4 M2(b)=0.4 M2(a,b)=0.2 M2()=0此时需要对它们进行组合，Dempster提出了一种组合方法，即对这两个概率分配函数进行正交和运算。,D-S证据理论,45,定义 设M1和M2是两个概率分配函数，则其正交和M=M1M2为 M()=0其中,如果K0，则正交和M也是一个概率分配函数；如果K=0，则不存在正交和M，称M1和M2矛盾。,D-S证据理论,46,对于多个概率分配函数M1，M2，Mn，如果它们可以组合，也可以通过正交和运算将它们组合为一个概率分配函数。定义 设M1，M2，Mn是n个概率分配函数，则其正交和M=M1M2 Mn为：,D-S证据理论,47,概率分配函数正交和举例,48,概率分配函数正交和举例,49,6、一个具体的不确定性推理模型 已知两元组(Bel(A),Pl(A)可以表示证据的不确定性，同理，它也可以表示不确定的规则。信任函数和似然函数都是基于概率分配函数定义的，随着概率分配函数的定义不同，会产生不同的应用模型。,D-S证据理论,50,1）概率分配函数和类概率函数 在该模型中，样本空间D=s1，s2，sn上的概率分配函数按如下定义：,D-S证据理论,51,特定概率分配函数的特点：1）只有单个元素构成的子集的概率分配函数有可能大于0。2）样本空间D的概率分配函数有可能大于0。3）其它子集的概率分配函数均为0。,D-S证据理论,52,对此特定的概率分配函数M，具有如下性质：,D-S证据理论,53,显然，对任何AD及BD均有：Pl(A)-Bel(A)=Pl(B)-Bel(B)=M(D)它表示对A或B的不知道程度。,D-S证据理论,例如，设D=左，中，右，且设 M（左）=0.3，M（中）=0.5，M（右）=0.1则由上述定义可得：,54,D-S证据理论,55,由该概率分配函数的定义，可把概率分配函数M1、M2正交和M=M1M2简化为：其中,D-S证据理论,56,例如：设D=左，中，右，且设M1(左,中,右,左，中，右,)=(0.3,0.5,0.1,0.1,0)M2(左,中,右,左，中，右,)=(0.4,0.3,0.2,0.1,0)则 K=0.10.1+(0.3 0.4+0.3 0.1+0.1 0.4)+(0.5 0.3+0.5 0.1+0.1 0.3)+(0.1 0.2+0.1 0.1+0.1 0.2)=0.01+0.19+0.23+0.05=0.48,D-S证据理论,57,M(左)=1/0.48 0.3 0.4+0.3 0.1+0.1 0.4=0.19/0.48=0.4同理可得：M(中)=0.48 M(右)=0.1 M(左，中，右)=0.02,D-S证据理论,58,定义 命题A的类概率函数f(A)：f(A)Bel(A)Pl(A)-Bel(A)其中，|A|、|D|分别指示A和D中包含元素的个数。f(A)作为集合A对应命题确定性的度量。类概率函数也称做信任度函数。,D-S证据理论,59,推论：（1）f()=0，（2）f(D)l（3）对于任何A D有 0f(A)1,D-S证据理论,f(A)的性质：(1)（2）对于任何A D有 Bel(A)f(A)Pl(A)，f(A)=1-f(A),60,例如，设D=左，中，右，且设 M(左,中,右,左，中，右,)=(0.3,0.5,0.1,0.1,0)，且设A=左，中，则,D-S证据理论,61,2）知识不确定性的表示 不确定性知识用产生式规则表示：IF E THEN H=h1,h2,hn CF=c1,c2,cn 其中：（1）E为前提条件，它既可以是简单条件，也可以是用AND或OR连接起来的复合条件；（2）H是结论，它用样本空间中的子集表示，h1,h2,hn是该子集中的元素；,D-S证据理论,62,（3）CF是可信度因子，用集合的形式表示，其中ci用来表示hi(i=1,2,n)的可信度，ci与hi 一一对应。ci满足如下条件：,D-S证据理论,63,3）证据不确定性的表示,64,3）证据不确定性的表示 不确定性证据E的确定性用CER（E）表示。对于初始证据，其确定性由用户给出；对于用前面推理所得结论作为当前推理的证据，其确定性由推理得到。CER（E）的取值范围为0，1，即0CER（E）1,D-S证据理论,65,4）组合证据不确定性的算法当组合证据是多个证据的合取时，即 E=E1 AND E2 AND AND En则E的确定性CER(E)为 CER(E)=minCER(E1),CER(E2),CER(En)当组合证据是多个证据的析取时，即 E=E1 OR E2 OR OR En则E的确定性CER(E)为 CER(E)=maxCER(E1),CER(E2),CER(En),D-S证据理论,66,5）不确定性的传递算法对于知识：IF E THEN H=h1,h2,hn CF=c1,c2,cn结论H的确定性通过下述步骤求出：（1）求出H的概率分配函数 H的概率分配函数为：M(h1,h2,hn)=CER(E)c1,CER(E)c2,CER(E)cn,D-S证据理论,H,67,如果有两条知识都支持同一结论H，即：IF E THEN H=h1,h2,hn CF=c1,c2,cn IF E THEN H=h1,h2,hn CF=c1,c2,cn则分别对每一条知识求出概率分配函数：M1(h1,h2,hn)M2(h1,h2,hn)然后再用公式M=M1M2求M1和M2的正交和，从而得到H的概率分配函数M。,D-S证据理论,68,如果有n条知识都同时支持同一结论，则用公式 M=M1M2 Mn得到H的概率分配函数M。(2)求出Bel(H),Pl(H)和f(H),D-S证据理论,69,(3)按如下公式求出H的确定性CER(H)CER(H)=MD(H/E)f(H)其中，MD(H/E)是知识的前提条件与相应证据的匹配度，定义为：,D-S证据理论,70,这样，就对一条知识或者多条有相同结论的知识求出了结论的确定性。如果该结论不是最终结论，则重复上述过程就得到新结论及其确定性。如此反复，直到推出最终结论及其确定性。,D-S证据理论,71,举 例,设有如下推理规则：,推理网络如图所示：,72,举 例,73,举 例,74,举 例,75,举 例,76,举 例,77,举 例,78,当D中的元素很多时，对信任函数Bel及正交和的运算将是相当复杂的，工作量很大，一是需要穷举D的所有子集；二是证据理论要求D中的元素是互斥的，这在很多领域很难做到。鉴于此，巴尼特提出了一种方法，即把D划分为若干组，每组只包含互斥的元素，称为一个辨别框，求解问题时，只要在各自的辨别框上考虑概率分配的影响。,D-S证据理论,79,小 结,概率方法主观Bayes方法LS、LN P(H)P(H/E)或P(H/E)几率EH公式、CP公式可信度方法可信度、MB、MDC-F模型DS证据理论概率分配函数、信任函数、似然函数、类概率函数概率分配函数的正交和,