ch4可信度与证据理论-3ppt课件

1、 可信度方法是美国斯坦福大学可信度方法是美国斯坦福大学E.H.Shortliffe等人在确定等人在确定性理论的基础上，结合概率论等提出的一种不确定性推理方法。性理论的基础上，结合概率论等提出的一种不确定性推理方法。1976年在专家系统年在专家系统MYCIN中首先应用，它是不确定推理方法中首先应用，它是不确定推理方法中应用最早、且简单有效的方法之一。中应用最早、且简单有效的方法之一。什么是可信度？什么是可信度？ 根据经验对一个事物或现象为真的相信程度称为可信度。根据经验对一个事物或现象为真的相信程度称为可信度。 可信度也称作确定性因子。用以度量知识和证据的不确可信度也称作确定性因子。用以度量知识

2、和证据的不确定性。可信度具有较大的主观性和经验性。定性。可信度具有较大的主观性和经验性。 C-F(Certainty Factor)模型模型1、知识不确定性的表示、知识不确定性的表示 在该模型中，知识是用产生式规则表示的，不确定在该模型中，知识是用产生式规则表示的，不确定性以可信度性以可信度CF(H,E)表示。表示。一般形式：一般形式：IF E THEN H (CF(H, E) )其中：其中：（1E是知识的前提或称为证据，可以是命题的合取、是知识的前提或称为证据，可以是命题的合取、析取组合等。析取组合等。 （2结论结论H可为单一命题，也可以是复合命题。可为单一命题，也可以是复合命题。（3CF(

3、H, E)为确定性因子，简称可信度，用以量度为确定性因子，简称可信度，用以量度规则的确定性可信程度。规则的确定性可信程度。C-F模型模型在MYCIN中 CF(H, E) = MB(H, E) - MD(H, E)其中：MB(H, E)(Measure Belief)指信任增长度，表示因与E匹配的证据出现，使H为真的信任增长度。定义如下： C-F模型模型MD(H, E)(Measure Disbelief)指不信增长度，表示因与E匹配的证据出现，使H为真的不信任增长度。定义如下：C-F模型模型当p(H/E)p(H)时，表示证据E支持结论H，则有MB0，MD=0；当p(H/E)0；当p(H/E)p

4、(H)时，表示E对H无影响，则有MBMD0。MB与MD的值域为0,1。因此，MB和MD是互斥的。即： 当MB0时，MD=0 当MD0时，MB=0 C-F模型模型根据CF(H,E)的定义及MD和MB的互斥性，可以得到CF(H,E)的计算公式:)H(P)E/H(P)H(P)E/H(P)H(P)E,H(MD0)H(P)E/H(P0)H(P)E/H(P)H(P1)H(P)E/H(P0)E,H(MB)E,H(CF若若若C-F模型模型 从CF(H,E)的计算公式可以看出它的意义：（1若CF(H,E)0，则P(H/E)P(H)；MB0，MD=0 。说明CF(H,E)的值越大，增加H为真的可信度就越大。若CF

5、(H,E)=1，P(H/E)=1，说明由于E所对应的证据出现使H为真。（2若CF(H,E)0，则P(H/E)0 。说明CF(H,E)的值越小，增加H为假的可信度就越大。若CF(H,E)=-1， P(H/E)=0，说明由于E所对应的证据出现使H为假。C-F模型模型（3若CF(H,E)=0，则P(H/E)=P(H)；MBMD0 。说明E与H无关。 由公式知，计算CF(H,E)需要知道P(H)与P(H/E)，然而，在实际应用中这两个值很难获得，而是在建立规则库时由领域专家凭经验主观确定的。C-F模型模型2 2、证据的不确定性表示、证据的不确定性表示 证据证据E E的可信度的可信度CF(E)CF(E)

6、取值为取值为-1,1-1,1。对于初始证据，。对于初始证据，若对它的所有观察若对它的所有观察S S能肯定它为真，则使能肯定它为真，则使CF(E)=1CF(E)=1；若肯；若肯定它为假，则使定它为假，则使CF(E)=-1CF(E)=-1；若它以某种程度为真，则使；若它以某种程度为真，则使CF(E)CF(E)为为0 0，1 1中某一值，若对它还未获得任何相关的中某一值，若对它还未获得任何相关的观察，此时可看作观察观察，此时可看作观察S S与它无关，则使与它无关，则使CF(E)=0CF(E)=0。C-F模型模型 类似于规则的不确定性，证据的可信度往往可由领域专家凭经验主观确定。 证据的可信度值来源于

7、两种情况： （1初始证据由领域专家或用户给出； （2中间结论由不确定性传递算法计算得到。C-F模型模型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模型模型4 4、不确定性的传递、不确定性的传递不确定性的传递算法

8、定义如下：不确定性的传递算法定义如下： CF(H)= CF(H,E) CF(H)= CF(H,E) maxmax0 0，CF(E)CF(E) 由上式可以看出由上式可以看出: : (1)CF(E)0 (1)CF(E)，所以知识可以使用，推出该动物是长颈鹿，其可信度为：CF(H)=CF(H,E) CF(E) =0.95 0.882 =0.84加权不确定性推理加权不确定性推理4、冲突消解、冲突消解设有下述知识设有下述知识r1: IF E1(1) THEN H1 (CF(H1,E1),1)r2: IF E2(2) THEN H2 (CF(H2,E2),2)且且 C F ( E 1 ( 1 ) ) 1

9、，CF(E2(2)2若若CF(E1(1)CF(E2(2)，则，则优先使用优先使用r1进行推理。进行推理。加权不确定性推理加权不确定性推理例如：设有下列知识：例如：设有下列知识：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

10、)=0.5求：求：CF(H)加权不确定性推理加权不确定性推理解：解：由由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可以使用。可以使用。加权不确定性推理加权不确定性推理由由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(E

11、3 AND E4 AND E5)所以所以r1先被启用，然后才能启用先被启用，然后才能启用r2。由由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加权不确定性推理加权不确定性推理lD-S证据理论是由丹普斯特Dempster提出，并由他的学生莎弗Shafer改

12、进的一种不确定推理模型。该理论引入信任函数而非采用概率来量度不确定性，并引用似然函数来处理由不知道而引起的不确定性，从而在实现不确定推理方面显示出很大的灵活性，受到人们的重视。l用集合表示命题，命题的不确定性问题转化为集合的不确定性问题。l将概率论中的单点赋值扩展为集合赋值，满足比概率更弱的要求，可看作一种广义概率论。不确定性方法比较n可信度方法：证据、结论和知识的不确定性以可信度进行度量。n主观Bayes方法：证据与结论的不确定性以概率形式度量，知识的不确定性以数值对LS,LN进行度量。nDS理论：证据与结论用集合表示，不确定性度量用信任函数与似然函数表示；知识的不确定性通过一个集合形式的可

13、信度因子表示。举 例 假设D是所有可能疾病的集合，医生为进行诊断而进行的各种检查就是获得所需证据的过程，检查得到的结果就是获得的证据，这些证据构成了证据集合E。 根据证据集合E中的这些证据，就可以判断病人的疾病。通常，有的证据所支持的不只是一种疾病，而是多种疾病，这些疾病构成集合D中的元素，可以构成D的一个子集H，H就是结论集合。 证据理论是用集合表示命题的。 设D是变量x的样本空间，其中具有n个元素，在任一时刻变量x的取值都会落入某个子集，也就是说，D的任一子集A都对应于一个关于x的命题，该命题为“x的值在A中”，所以用集合A表示该命题。D-SD-S证据理论证据理论 例如： x代表颜色，D=

14、红，黄，蓝。 如果A=红，表示“x是红色”。 如果A=黄，蓝，表示“x或者是红色，或者是蓝色”。 D-SD-S证据理论证据理论 1 1、概率分配函数、概率分配函数 设论域设论域D D为所有可能假设表示为原子命题的结论为所有可能假设表示为原子命题的结论的有限集合，且的有限集合，且D D中的元素间是互斥的，则可以在中的元素间是互斥的，则可以在D D的幂的幂集集2D2D上定义一个基本概率分配函数上定义一个基本概率分配函数M M：2D 0,12D 0,1，满，满足足 则称则称M M是是2D2D上的概率分配函数，上的概率分配函数，M(A)M(A)称为称为A A的基本概率数。的基本概率数。 DA1)A(M

15、0)(MD-SD-S证据理论证据理论 概率分配函数的作用 将D上的任意一个子集A都映射为0,1上的一个数M(A)。当A对应一个命题时， M(A)即是对相应命题不确定性的度量。 留意：概率分配函数不是概率，样本空间D上的各元素的基本概率数之和不一定等于1。 （1设样本空间D中有n个元素，则D中子集的个数为2n个，定义中的2D则表示这些子集构成的集合。 例如：设D=红，黄，蓝，则它的子集有8个：A1=红， A2=黄， A3=蓝， A4=红，黄，A5=红，蓝， A6=蓝，黄， A7=红，黄，蓝， A8=。D-SD-S证据理论证据理论 （2概率分配函数把D的任意一个子集A都映射为0，1上的一个数M(A

16、)，当AD时， M(A)表示对相应命题的精确信任程度。概率分配函数事实就上是对D的各个子集进行信任分配。 例如：A=红， M(A)=0.3 表示对命题“A是红色的精确信任度为0.3。D-SD-S证据理论证据理论 （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-SD-S证据理论证据理论 2 2、信任函数、信任函数 Bel Bel 信任函数用来对命题的不确定性进行度量

17、。信任函数用来对命题的不确定性进行度量。 定义定义5.25.2命题的信任函数命题的信任函数BelBel：2D 2D 0,10,1，对于，对于任意的任意的A AD D，有，有 BelBel函数又称为下限函数，函数又称为下限函数，Bel(A) Bel(A) 表示对命题表示对命题A A为真的信为真的信任程度，为任程度，为A A所有子集的基本概率数之和。所有子集的基本概率数之和。 ABB(M)A(BelD-SD-S证据理论证据理论 易知 Bel()=0，Bel(D)=1；当 A为单一元素集时，Bel(A)=M(A)。 例如：对于上例可以求出： Bel(红)=M(红)=0.3 Bel(红，黄)=M(红)

18、+M(黄)+M(红，黄) =0.3+0+0.2=0.5D-SD-S证据理论证据理论 3 3、似然函数、似然函数PlPl 似然函数似然函数PlPl：2D 2D 0,10,1，且，且 Pl(A)= 1 Bel( Pl(A)= 1 Bel( A) A) 对所有的对所有的A AD D Pl(A) Pl(A)表示对表示对A A为非假不否定为非假不否定A A的信任程度，它是所的信任程度，它是所有与有与A A相交的子集的基本概率数之和。似然函数又称为相交的子集的基本概率数之和。似然函数又称为上限函数。上限函数。 在上例中，在上例中，Pl(Pl(红红) = 1 - Bel() = 1 - Bel(蓝，黄蓝，黄

19、) = 1 - 0.2 = 0.8) = 1 - 0.2 = 0.8D-SD-S证据理论证据理论 BA)B(M)A(Pl BADEBAACBABABA)B(M)A(Pl0)E(M1) )B(M)C(M(1) )B(M)A(Bel(1)B(M)A(Bel1)B(M)A(PlD-SD-S证据理论证据理论 Pl(A)= 1 Bel(A)()BAMB Bel(A)表示对命题A为真的信任程度； Bel( A)表示对命题 A为真的信任程度，即表示A为假的信任程度； Pl(A) 1 Bel(A)表示对A为非假的信任程度。 可以看到：A不为假并不代表A一定为真，也就是说对A不为假的信任程度应该大于对A为真的信

20、任程度。D-S证据理论证据理论 4 4、信任函数与似然函数的关系、信任函数与似然函数的关系 似然函数有以下特性：似然函数有以下特性： Pl(A) Bel(A) Pl(A) Bel(A) Pl() = 0 Pl() = 0，Pl(D)= 1Pl(D)= 1 由于由于Bel(A)Bel(A)表示对表示对A A为真的信任程度，为真的信任程度， Pl(A) Pl(A)表示对表示对A A为非假的信任程度，所以为非假的信任程度，所以 Pl(A) - Bel(A) Pl(A) - Bel(A)表示既不为假、表示既不为假、又不为真的信任程度或者说既不信任又不为真的信任程度或者说既不信任A A也不信任也不信任

21、A A的程度，的程度，即 是 对即 是 对 A A 是 真 是 假 不 知 道 的 程 度 。 可 以 用 区 间是 真 是 假 不 知 道 的 程 度 。 可 以 用 区 间Bel(A),Pl(A)Bel(A),Pl(A)来综合描述来综合描述A A的不确定性。的不确定性。D-SD-S证据理论证据理论 易知存在三个特殊的区间： 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

22、。0.85-0.25=0.6表示对A不知道的程度。D-SD-S证据理论证据理论 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提出了一种组合提出了一种组合方法，

23、即对这两个概率分配函数进行正交和运算。方法，即对这两个概率分配函数进行正交和运算。 D-SD-S证据理论证据理论 定义定义 设设M1和和M2是两个概率分配函数，则其正交和是两个概率分配函数，则其正交和M=M1M2为为 M()=0其中其中) y(M)x(MK)A(M2Ayx11 ) y(M)x(M) y(M)x(M1K2yx12yx1 如果K0，则正交和M也是一个概率分配函数；如果K=0，则不存在正交和M，称M1和M2矛盾。D-SD-S证据理论证据理论 对于多个概率分配函数M1，M2， ，Mn，如果它们可以组合，也可以通过正交和运算将它们组合为一个概率分配函数。定义 设M1，M2， ，Mn是n个

24、概率分配函数，则其正交和M=M1M2 Mn为： D-SD-S证据理论证据理论 概率分配函数正交和举例概率分配函数正交和举例6、一个具体的不确定性推理模型、一个具体的不确定性推理模型 已知两元组已知两元组(Bel(A),Pl(A)可以表示证据的不确定可以表示证据的不确定性，同理，它也可以表示不确定的规则。性，同理，它也可以表示不确定的规则。 信任函数和似然函数都是基于概率分配函数定义的，信任函数和似然函数都是基于概率分配函数定义的，随着概率分配函数的定义不同，会产生不同的应用模型。随着概率分配函数的定义不同，会产生不同的应用模型。D-SD-S证据理论证据理论 1概率分配函数和类概率函数概率分配函

25、数和类概率函数 在该模型中，样本空间在该模型中，样本空间D=s1，s2，sn上的概上的概率分配函数按如下定义：率分配函数按如下定义：对应集合中元素的个数表示命题其中时或且当A|A|0)A(M,0|A|1|A|DA)4(s(M1)D(M)3(1s(M)2(0)s(M)1(n1iin1iii D-SD-S证据理论证据理论 特定概率分配函数的特点：1只有单个元素构成的子集的概率分配函数有可能大于0。2样本空间D的概率分配函数有可能大于0。3其它子集的概率分配函数均为0。D-SD-S证据理论证据理论 对此特定的概率分配函数M，具有如下性质：1)(Bel1)D(Bel1)D(Pl)A(Bel)D(M)A

26、(Bel)D(M11)s(M)s(M1)s(M1)A(Bel1)A(Pel1)D(M)s(M)D(Bel)s(M)A(BelAisin1iiAisin1iiAisi D-SD-S证据理论证据理论 显然，对任何AD及BD均有： Pl(A)-Bel(A)= Pl(B)-Bel(B)=M(D)它表示对A或B的不知道程度。D-SD-S证据理论证据理论 例如，设D=左，中，右，且设 M（左）=0.3， M（中）=0.5， M（右）=0.1则由上述定义可得：9 . 01 . 01)(Bel1),(Bel1),(Pl8 . 05 . 03 . 0)(M)(M),(Bel1 . 09 . 01)(M)(M)(

27、M1)s(M1)D(Mn1ii 右中左中左中左中左右中左D-SD-S证据理论证据理论 由该概率分配函数的定义，可把概率分配函数M1、 M2正交和M=M1M2简化为：其中)s(M)D(M)D(M)s(M)s(M)s(MK)s(Mi212i1i2i11i )s(M)D(M)D(M)s(M)s(M)s(M)D(M)D(MKi212i1i2i1n1i21 D-SD-S证据理论证据理论 例如：例如：设设D=左，中，右左，中，右，且设，且设M1(左左, 中中, 右右, 左，中，左，中，右右,)=(0.3,0.5, 0.1,0.1,0)M2(左左, 中中, 右右, 左，中，左，中，右右,)=(0.4,0.3

28、, 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.48D-SD-S证据理论证据理论 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.02D-SD-S证据理论证据理论 定义定义 命题命题A A的类概率函数的类概率函数f(A)f(A)： f(A) f(A)Bel(A)B

29、el(A) Pl(A)- Bel(A)Pl(A)- Bel(A)其中，其中，|A|A|、|D|D|分别指示分别指示A A和和D D中包含元素的个数。中包含元素的个数。 f(A) f(A)作为集合作为集合A A对应命题确定性的度量。对应命题确定性的度量。类概率函数也称做信任度函数。类概率函数也称做信任度函数。 |DAD-SD-S证据理论证据理论 推论： （1f()= 0， （2f(D)l （3对于任何A D有 0f(A)1D-SD-S证据理论证据理论 f(A)的性质： (1) （2对于任何A D有 Bel(A) f(A) Pl(A)，f(A)=1-f(A)1)s(fn1ii 例如，设D=左，中，

30、右，且设 M(左, 中, 右, 左，中，右,) =(0.3,0.5, 0.1,0.1,0)，且设A=左，中，那么87.01 .05 .03 .0),(M)(M)(M Bel(A) -Pl(A) Bel(A)f(A)3232DA 右中左中左D-SD-S证据理论证据理论 2知识不确定性的表示知识不确定性的表示 不确定性知识用产生式规则表示：不确定性知识用产生式规则表示： IF E THEN H=h1, h2, hn CF= c1, c2, cn 其中：其中：（1E为前提条件，它既可以是简单条件，也可以是用为前提条件，它既可以是简单条件，也可以是用AND或或OR连接起来的复合条件；连接起来的复合条件

31、；（2H是结论，它用样本空间中的子集表示，是结论，它用样本空间中的子集表示， h1, h2, hn是该子集中的元素；是该子集中的元素；D-SD-S证据理论证据理论 （3CF是可信度因子，用集合的形式表示，其中ci用来表示hi (i=1,2,n)的可信度，ci与hi 一一对应。 ci满足如下条件：1,n,2, 1i ,01niiiccD-SD-S证据理论证据理论 3证据不确定性的表示证据不确定性的表示3证据不确定性的表示证据不确定性的表示 不确定性证据不确定性证据E的确定性用的确定性用CERE表示。表示。 对于初始证据，其确定性由用户给出；对于初始证据，其确定性由用户给出； 对于用前面推理所得结

32、论作为当前推理的证据，其确对于用前面推理所得结论作为当前推理的证据，其确定性由推理得到。定性由推理得到。 CERE的取值范围为的取值范围为0，1，即，即0CERE）1D-SD-S证据理论证据理论 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)为为