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