AI第3章--不确定性推理.ppt

人工智能,主讲教师：,李,娜,娜,Instructor: Li Nana E-mail: ,第五章 不确定性推理,概述 可信度方法 (确定性方法) 主观Bayes方法 证据理论,第五章 不确定性推理,概述 确定性方法(可信度方法) 主观Bayes方法 证据理论,概述-不确定推理的概念,推理：从已知事实出发，运用相关知识(或规则)逐步推出结论或者证明某个假设成立或不成立的思维过程。已知事实是推理过程的出发点即推理中使用的知识， 我们把它称为证据。 不确定推理：从具有不确定性的证据出发，运用不确定性的知识(或规则)，最终推出具有一定程度的不确定性，但却是合理的或近乎合理的结论的思维过程。,概述-不确定性的主要表现,1、证据的不确定性 观察度量的不确定性 证据表示的不确定性 多个不确定证据合成时表现出来的不确定性 2、规则的不确定性 3、结论的不确定性,E1H,E2H,概述不确定推理中的基本问题,不确定性的表示 单个证据的不确定性表示 证据的来源： (1)初始证据:通过观察而得到的，由于观察本身的不精确性，因此所得的初始证据具有不确定性； (2)间接证据:在推理过程中利用前面推理出的结论作为当前新的推理证据。 证据不确定性的表示通常为一个数值，用以表示相应证据的不确定性程度。 (1)对于由观察得到的证据，其值一般由用户或专家给出; (2)对于用前面推理所得结论作为当前推理的证据，其值则是由推理中的不确定性传递算法计算得到。 组合证据的不确定性表示 证据不止一个，而是几个，这几个证据间可能是and或or的关系，假设C(E1)表示证据E1的不确定性程度， C(E2)表示证据E2的不确定性程度，如何由C(E1)和C(E2)来计算C(E1E2)和C(E1E2),概述不确定推理中的基本问题,规则的不确定性表示 规则不确定性要由领域专家给出，以一个数值表示，该数值表示了相应知识的不确定性程度。 推理计算结论的不确定性表示 不确定性传递问题： 已知证据E的不确定性度量为C(E)，而规则E H的不确定性度量为CF(H,E)，那么如何计算结论H的不确定性程度C(H)，即如何将证据E的不确定和规则E H的不确定性传递到结论H上。 结论不确定性的合成问题： 如果有两个证据分别由两条规则支持结论，如何根据这两个证据和两条规则的不确定性确定结论的不确定性。即已知 E1 H C(E1),CF(H,E1) E2 H C(E2),CF(H,E2) 如何计算C(H),概述-分类（1）,不确定性推理方法,控制方法,模型方法,数值方法,非数值方法,基于概率的方法,模糊推理方法,可信度方法,主观Bayes方法,证据理论方法,第五章 不确定性推理,概述 可信度方法(确定性方法) 主观Bayes方法 证据理论,可信度方法（确定性方法）,MYCIN系统研制过程中产生的不确定推理方法,第一个采用了不确定推理逻辑，70年代很有名。它是不确定推理方法中应用最早、且简单有效的方法之一。,可信度方法,可信度：人们在实际生活中根据自己的经验或观察对某一事件或现象为真的相信程度,也称为确定度因子。 可信度具有较大的主观性和经验性。但是，对某一具体领域而言，由于该领域专家具有丰富的专业知识及实践经验，要给出该领域知识的可信度还是完全有可能的。,可信度(确定性)方法 证据（前提）的不确定性表示 规则的不确定性表示 推理计算-结论的不确定性表示,确定性(可信度)方法,证据的不确定性度量,单个证据的不确定性获取方法：两种 初始证据：由提供证据的用户直接指定，用可信度因子对证据的不确定性进行表示。如证据E的可信度表示为CF(E)。 如对它的所有观测都能肯定为真，则使CF(E)=1；如能肯定为假，则使CF(E)=-1；若它以某种程度为真，则使其取小于1的正值，即0 CF(E)1;若它以某种程度为假，则使其取大于-1的负值，即-1 CF(E)0;若观测不能确定其真假，此时可令CF(E)=0。 间接证据：用先前推出的结论作为当前推理的证据，对于这种情况的证据，其可信度的值在推出该结论时通过不确定性传递算法计算得到。,证据的不确定性度量,组合证据的不确定性获取方法 当证据是多个单一证据的合取时，即E= E1 E2En 若各证据的可信度分别为CF(E1), CF(E2), , CF(En), 则CF(E ) = min CF(E1), CF(E2 ), CF(En) 当证据是多个单一证据的析取时，即E= E1E2 En 若各证据的可信度分别为CF(E1), CF(E2), , CF(En), 则CF(E ) = max CF(E1), CF(E2 ), CF(En) 当证据是某一证据的非时，即E= A； 则CF(E ) = -CF(A ) 若E= E1（ E2E3) E 4,规则 证据（前提）的不确定性表示 规则的不确定性表示 推理计算-结论的不确定性表示,确定性方法,规则的不确定性度量,规则E H，可信度表示为CF(H,E)。表示当证据E为真时，对结论H为真的支持程度。其取值范围为-1，1。CF(H,E)越大，则E越支持H为真。 遵循的原则：如果由于证据E的出现，使结论H为真的可信度增加了，则使CF(H, E)0，并且这种支持的力度越大，就使CF(H, E)的值越大，相反，如果证据E的出现，使结论H为假的可信度增加，则使CF(H, E)0，并且这种支持的力度越大，就使CF(H, E)的值越小；若证据的出现与否和H无关，则使CF(H, E)=0。 P(H|E)=1 P(H|E)=0 P(H|E)=P(H),规则 规则的不确定性表示 证据（前提）的不确定性表示 推理计算结论的不确定性表示,确定性方法,规则 (推理计算 1）,从不确定的初始证据出发，通过运用相关的不确定知识，最终推出结论并求出结论的可信度值。 最简单的情形：只有单条规则-不确定性传递问题 例如 由E， E H， 求 H。已知证据E的可信度CF(E )和规则CF(H, E )的可信度，则结论H的可信度计算公式为： CF(H) =max0,CF(E )CF(H, E ) (CF(E )0 时CF(H) =0,说明在该模型中没有考虑证据为假时对结论H的影响。),规则 (推理计算 2）,多条知识支持同一结论时-结论不确定性的合成问题 设有如下知识：if E1 then H； if E2 then H； 1) 利用上式分别计算每一条知识的结论可信度CF(H) CF1(H) =max0,CF(E1 )CF(H,E1 ) CF2(H) =max0,CF(E2)CF(H,E2 ) 2) 用下式合成CF1(H) 、CF(H) ，求可信度 CF12(H),例题,已知：R1：A1B1 CF（B1，A1）0.8 R2：A2B1 CF（B1，A2）0.5 R3：B1A3B2 CF（B2，B1A3）0.8 CF（A1）CF（A2）CF（A3）1；而对B1和B2一无所知； 计算 CF（B2） 本题可图示为,解：依规则R1， CF1（B1） CF（B1，A1）max0, CF（A1）0.8， 依规则R2： CF2（B1） CF（B1，A2）max0, CF（A2）0.5， 利用合成算法计算B的综合可信度： CF1( B1)CF1( B1) CF( B) CF1( B1)CF( B)0.9 依R3，先计算 CF（B1A3） min（CF（A3），CF（B1）0.9 CF（B2）= CF(B2，B1A3) max0, CF（B1A3） =0.90.8=0.72 答：CF（B1）0.9，CF（B2）0.72,例 设有一组知识:,解：,规则 (推理计算 3）,已知结论原始可信度的情况下，结论可信度的更新计算方法。 即已知规则E H 的可信度为CF(E,H )，证据E的可信度为CF(E)，同时已知结论H原来的可信度为CF(H)，如何求在证据E下结论 H可信度的更新值CF(H/E) ：,规则 (推理计算 4）,CF(E) =0， 规则E H不可使用，即此计算不必进行。 0 CF(E) = 1，,规则 (推理计算 3）,当E必然发生，CF(E)=1时：,计算: (1)结论X的可信度 (2)结论Y的可信度,解：考虑X、Y具有初始可信度，所以使用更新法计算结论可信度。 (1)X的可信度更新计算 由于证据初始值CF(A)= CF(B)= CF(C)= CF(D)=0.50，使用公式 由规则r1得到X的可信度更新值为： CF(X/A) =CF0(X)+ CF(A) CF(X,A)- CF0(X) CF(A) CF(X,A) =0.1+0.5X0.8- 0.1X0.5X0.8=0.46 由规则r2得到X的可信度更新值为： CF(X/A,B) =CF(X/A)+ CF(B) CF(X,B)- CF(X/A) CF(B) CF(X,B) =0.622 由规则r3得到X的可信度更新值为： CF(X/A,B,C) =CF(X/A,B)+ CF(C) CF(X,C)- CF(X/A,B) CF(C) CF(X,C) =0.698 CF(X/A,B,C)即是X的可信度更新值。,A,B,C,X(0.1),D,XD,Y(0.2),0.8,0.6,0.4,0.3,主观贝叶斯方法(概述）,贝叶斯公式： 设事件H1, Hn是彼此独立、互不相容的事件，则有： 在贝叶斯公式中，P(Hi), i=1, 2, , n称为先验概率，而P(Hi|E) i=1, 2, , n称为后验概率.,例: 一个病人发热(E)，问他患感冒(Hi) 的概率是多少？即求,感冒时发热的概率,患者感冒的概率,发热的概率,主观贝叶斯方法(概述）,直接根据贝叶斯公式进行推理计算简单明了，但是它要求结论Hi相互独立，实际上难以保证。而且P(E| Hi)的计算通常比较困难。所以在求解不确定性推理问题时，还不能直接使用贝叶斯公式，而是使用对其经过改进的主观贝叶斯公式。 1976年提出的，在地矿勘探系统中得到成功的应用。是对概率中基本贝叶斯公式的改进。,主观贝叶斯方法 证据（前提）的不确定性表示 规则的不确定性表示 推理计算-结论的不确定性表示,主观贝叶斯方法,主观贝叶斯方法(概述）,证据的不确定性表示 单个证据：在主观贝叶斯方法中，证据的不确定性用概率表示。例如，对于初始证据E，其先验概率为P(E)。 组合证据 当证据是多个单一证据的合取时，即E= E1 and E2andandEn 若各证据的可信度分别为P(E1), P(En), 则P(E ) = min P(E1), P(En) 当证据是多个单一证据的析取时，即E= E1orE2 ororEn 若各证据的可信度分别为P(E1), P(En),则P(E ) = max P(E1), P(En) 当证据是某一证据的非时，即E= A； 则P(E ) =1-P(A ),主观贝叶斯方法 证据（前提）的不确定性表示 规则的不确定性表示 推理计算-结论的不确定性表示,主观贝叶斯方法,主观贝叶斯方法(概述）,规则的不确定性表示 在主观贝叶斯方法，规则的不确定性是以一个数值对(LS,LN)来进行描述的。 IF E THEN (LS,LN) H (P(H) 取值范围 取值范围 它们的具体取值由领域专家根据实际经验给出。,规则的充分性度量:表示E为真时，对H的影响。,规则的必要性度量:表示E为假时，对H的影响。,H为真时E出现的概率除以H为假时E出现的概率,H为真时E不出现的概率除以H为假时E不出现的概率,主观贝叶斯方法 证据（前提）的不确定性表示 规则的不确定性表示 推理计算-结论的不确定性表示,主观贝叶斯方法,主观贝叶斯方法,推理计算不确定性的传递： 1）已知规则EH的(LS,LN)和P(H)、 P(E)，如何计算P(H/E)或P(H/E) 这里存在三种情况：证据E肯定存在、肯定不存在或以某种程度存在。,(1)证据E肯定存在，即P(E)=1时： 由基本贝叶斯公式，可得： 两式相除得：,主观贝叶斯方法(概述）,几率函数O(X) 数学证明，O(x)与P(x)有相同的单调性,E肯定出现的情况下，H的先验几率更新为后验几率的公式,E肯定出现的情况下，H的先验概率更新为后验概率的公式,讨论LS对后验概率的影响 (1)LS1 O(H/E)O(H)，即 P(H/E)P(H) (2) LS=1 O(H/E)=O(H) (3)01，且越大越好。,E的存在，使H为真的概率增加，且LS越大，P(H/E)越大，表明E对H为真的支持越强。,E与H无关。,E的出现使H为真的可能性下降。,E的出现使H为假。,(2)证据E肯定不存在，即P(E)=0时： P(E)=1，由贝叶斯公式，可得： 两式相除得：,主观贝叶斯方法(概述）,E肯定不出现的情况下，H的先验几率更新为后验几率的公式,E肯定不出现的情况下，H的先验概率更新为后验概率的公式,讨论LN对后验概率的影响 (1)LN1 O(H/E)O(H)，即 P(H/E)P(H) (2)LN=1 O(H/E)=O(H) (3)0LN1 O(H/E)O(H) (4)LN=0 O(H/E)=0 故， E的不存在使H为真的可能性下降，则应该相应的LN 设置的小于1而且越小越好。,E的不存在，使H为真的概率增加，且LN越大，P(H/E)越大，表明E对H为真的支持越强。,E的不存在与H无关。,E的不存在使H为真的可能性下降。,E的不存在使H为假。,主观贝叶斯方法（规则的不确定性）,，且必须满足：,主观贝叶斯方法（规则的不确定性）,对LS、LN赋值时的考虑 LS、LN。 LS, LN不能同时 或 LS, LN可同时1,主观贝叶斯方法,例题(1) 规则如下：R1：E1H1 LS=1 LN=0.003; R2：E2H2 LS=18 LN=1 R3：E3H3 LS=12 LN=1 已知P(H1)=0.4, P(H2)=0.06, P(H3)=0.04 求：证据出现及不出现时，P(Hi/Ei)和P(Hi/Ei)的值各是多少？,R1：E1H1 LS=1 LN=0.003; R2：E2H2 LS=18 LN=1 R3：E3H3 LS=12 LN=1,解： R1中，因为LS=1， 即E1的出现对H1无影响，故： P(H1/E1)= P(H1)=0.4 P(H1/E1)= R2中，因为LN=1， 即E2的不出现对H2无影响，故： P(H2/E2)= P(H2)=0.06 P(H2/E2)=,R3中，因为LN=1，即E3的不出现对H3无影响，故： P(H3/E3)= P(H3)=0.04 P(H3/E3)=0.333,主观贝叶斯方法,推理计算 ： 3）多条知识支持同一结论时-结论不确定性的合成问题 设有如下知识：if E1 then (LS1,LN1) H ； if E2 then (LS2,LN2) H ；已知P(H)，证据E1和E2依次出现后，计算P(H/E1,E2) 1) 根据每条知识分别计算O(H/E1)和O(H/E2) 2) 用下式合成 ，求 O(H/E1，E2),例题（2）,已知：证据E1，E2依次发生，且P（H）0.03 规则如下：R1：E1H LS=20 LN=1; R2：E2H LS=300 LN=1 求P(H/E1,E2). 解： 计算O(H):O(H)= 根据R1得：O(H/E1)= LS1O(H)=0.618 根据R2得：O(H/E2)= LS2O(H)=9.27 所以,习题,可信度CF(E),概率P(E),可信度CF(H,E),(LS,LN),可信度CF(H),后验概率P(H/E)、 P(H/E),在很多实际问题中，证据和结论都是以集合形式存在的。如：医生看病，检查得到的结果是获得的证据，它是一个集合E=E1,En=发烧，腹泻，咳嗽，肺部有阴影，根据这些集合E中的这些证据，可以判断病人得了哪些病D=H1,Hm=肺结核、肠炎。 证据理论处理的是同时有多个证据支持多个结论的情况，在此理论中，它们以集合形式表示，需要定义新的度量不确定的标准。,第五章 不确定性推理,概述 确定性方法 主观Bayes方法 证据理论,第五章 不确定性推理,概述 确定性方法 主观Bayes方法 证据理论,证据理论,概述 证据的不确定性表示 规则的不确定性表示 推理计算,证据理论,概述 由Dempster首先提出，并由他的学生Shafer发展起来，也称D-S理论。在专家系统的不精确推理中已得到广泛的应用。,证据理论,概率分配函数-处理集合关系的函数： 设U是证据或结论集合，U中的元素个数为n， 则U的子集的个数为 个，我们以表示所有子集构成的集合。 概率分配函数m：0,1把U上的每一个子集A都映射到0，1上的一个值m(A)(表示了对的子集A成立的一种信任度)，并且要求：,例: 设D=red, green, blue， 则2D空间由D的8个子集构成，这8个子集分别是： A0=, A1=red, A2=green, A3=blue, A4=red,green, A5=red,blue, A6=green,blue, A7=red,green,blue 假设定义一个函数m(x)，对各子集的概率分配如下：m(A0)=0; m(A1)=0.2; m(A2)=0.1; m(A3)=0.1; m(A4)=0.2; m(A5)=0.1; m(A6)=0.2; m(A7)=0.1;,证据理论,信任函数Bel 0,1。（在的幂集上定义，取值0,1）并且满足 表示A的所有子集的概率分配数值的和，用来表示对A的总信任度。 Bel为信任函数，或称下限函数。容易推出： Bel() =？ Bel() = 例题： Bel(A1)= m(red)=0.2; Bel(A5)= m(red)+ m(blue)+ m(red,blue) =0.4;,证据理论,似然函数/上限函数Pl 0,1，满足 Pl(A) = 1 - Bel(A) = 对中与A有交集的所有集合的概率分配数值的和 - 性质： Bel(A) Bel(A) Pl(A) = 1 - Bel(A) Pl(A) Bel(A),表述对A为真的信任程度,表述对A为真的信任程度，即表示A为假的信任程度,表示对A为非假的信任程度,PI(A1)=1-Bel(A1) =1-Bel(green,blue) =1- M(green)+ M(blue)+ M(green,blue)=0.6 PI(A5),证据理论,信任度函数f 在证据理论中，证据和结论的不确定性，用区间(Bel(A), Pl(A)来进行度量， Bel(A)和Pl(A)作为度量其信任程度的下限和上限 。 但为了推理计算的方便，需要利用Bel(A)和Pl(A)构造一个函数，通过这个函数把一个区间转换成为一个值，该函数的定义如下： 其中|A|、|U|为集合内元素个数，该函数称为信任度函数，该函数的值落在区间(Bel(A), Pl(A)内，用它来度量证据和结论的不确定性。,信任度函数,例： 设U=a,b,c，其概率分配函数m为： m( a, b, c, a,b, a,c, b,c, a,b,c, ) =0.3, 0.5, 0.1, 0, 0, 0, 0.1, 0 且设A=b, c，则f(A)=? 解：Bel(A)= m(b) + m(c)+ m(b,c)=0.6 Pl(A)=1-Bel(A) =1-m(a)=0.7,证据理论,特定概率分配函数为了简化推理模型 特定概率分配函数m：U0,1把U=s1,sn上的每一个子集都映射到0，1上的一个值M(A)(表示了对U的子集A成立的一种信任度)，并且要求： (1)M(si)0 (2) (3)M(U)=1- (4)当A是U的真子集，并且|A|1或|A|=0，则M(A)=0 例,证据理论 (Evident Theory),概述 证据的不确定性表示 规则的不确定性 推理计算,证据理论 (证据的不确定性),对于不确定性证据E，其不确定性用信任函数f(E)表示 1)当E是初始的简单证据时，其信任度f(E)由用户给出； 2)当E是前面推理所得结论，又要作为当前推理的证据时，其信任度f(E)由推理计算得到； 3）当证据E由多个证据组合而成时，其信任度f(E)由下列方法求取。如果E= E1 and E2 andand En，则f(E)= min f(E1), f(E2), f(En)；如果E= E1 or E2 oror En，则f(E)= max f(E1), f(E2 ), f(En),证据理论,概述 证据的不确定性 规则的不确定性 推理计算,证据理论 (规则的不确定性),不确定性知识用如下形式的规则表示 IF E THEN H=h1,hn CF=c1,cn CF是该条知识的可信度因子，用集合形式表示，其中ci用来表示指出由E得到hi的可信度， ci与hi对应。,证据理论,概述 证据的不确定性 规则的不确定性 推理计算,证据理论 (推理计算),推理计算模型： 已知IF E THEN H=h1,hn CF=c1,cn，E的信任度为f(E)，|H| |U|.求结论H的信任度f(H) 第一步：求出H的特定概率分配函数, 对于上述知识，H的概率分配函数 m(h1)=f(E)c1 m(h2)=f(E)c2 m(hn)=f(E)cn m(U)=1- f(E)c1-f(E)c2-f(E)cn 第二步：求出H的信任函数Bel(H)和似然函数PI(H) 第三步：求结论H的信任度f(H),例题,M(D)=1-0.18-0.3=0.52,Pl(B)=,=M(b1)+M(b2)+M(D),=1,作业,设有以下规则：,证据理论 (推理计算),如果两条知识支持同一结论H，即 IF E1 THEN H=h1,hn CF=c1,cn， IF E2 THEN H=h1,hn CF=c1,cn，,m1, m2在U上的合成-概率分配函数的合成运算 定义：m = m1 m2 规定：m() = 0 ， m(A) = 其中 K11 且 K1 0。 若K1 0，认为m1，m2矛盾，没有联合基本概率分配函数 。,推理计算模型： 如果两条知识支持同一结论H，即 IF E1 THEN H=h1,hn CF=c1,cn， IF E2 THEN H=h1,hn CF=c1,cn， 第一步：分别对每一条知识求出概率分配函数, m1(h1,hn)和m2(h1,hn) 然后再用公式m=m1 m2 求m1和m2的正交和，即可得到结论H的概 率分配函数m. 第二步：求出H的信任函数Bel(H)和似然函数PI(H) 第三步：求结论H的信任度f(H),例题,已知：f1(A1) = 0.40 ,f1(A2)=0.50,|U| = 20. A1B=b1,b2,b3，(c1,c2,c3)=(0.1,0.2,0.3) A2B=b1,b2,b3，(c1,c2,c3)=(0.5,0.2,0.1) 求：f1(B) 解：（）先求：m1(b1,b2,b3) =(0.4*0.1,0.4*0.2,0.4*0.3)=(0.04,0.08,0.12); m1(U) =1- m1(b1)+m1(b2)+m1(b3)=0.76; m2(b1,b2,b3) =(0.5*0.5,0.5*0.2,0.5*0.1)=(0.25,0.10,0.05); m2(U) =1- m2(b1)+m2(b2)+m2(b3)=0.70;,例题,求m =m1 m2 1/K =m1(b1)*m2(b1)+ m1(b1)*m2(U)+ m1(b2)*m2(b2)+ m1(b2)*m2(U)+ m1(b3)*m2(b3)+ m1(b3)*m2(U)+ m1(U)*m2(b1)+ m1(U)*m2(b2)+ m1(U)*m2(b3)+ m1(U)*m2(U) =0.01+0.028+0.008+0.056+0.06+0.084+0.19+0.076+0.038+0.532 =1/1.082 有： m(b1) =K*(m1(b1)*m2(b1)+m1(b1)*m2(U)+m1(U)*m2(b1) =1.082*(0.01+0.028+0.19)=0.247 m(b2) =K*(m1(b2)*m2