不确定推理方法.ppt

第五章 不确定推理方法,北京物资学院 赵明茹,例:假设有如下的前提知识：（1）自然数是大于零的整数（2）所有整数不是偶数就是奇数（3）偶数除以2是整数求证：所有自然数不是奇数就是其一半为整数的数定义谓词：N(x)表示x是自然数I(x)表示x是整数，E(x)表示x是偶数，O(x)表示x是奇数 GZ(x)表示x大于0，另外用函数S（x）表示x除以2,例：任何通过历史考试并中了彩票的人是快乐的。任何肯学习或幸运的人可以通过所有的考试。John不学习但是很幸运。任何人只要是幸运的就能中彩。求证：John是快乐的。定义谓词：Pass(x,y)表示x能通过y考试；Win(x,y)表示x能够赢得yStudy(x)表示x肯学习Lucky(x)表示x是很幸运的Happy(x)表示x是快乐的,确定性推理,基于一阶谓词逻辑的归结推理方法是一种确定性的推理方法。依据的证据是确定的，谓词表示的知识要么为真，要么为假。推理过程也是以数理逻辑为基础，推理过程是严密的，所推出的结论也是确定的，即结论要么成立，要么不成立。,不确定性推理,信息不够完善、不够精确，即所掌握的知识具有不确定性。人们就是运用这种不确定性知识进行思维、推理、进而求解问题。所以，为了解决实际问题，必须对不确定知识的表示、推理过程等进行研究，这就是本章要讨论的不确定推理方法。不确定性知识的表示：可信度方法、主观Bayes方法和证据理论方法。,5.1 不确定推理概述,人工智能系统中的知识库往往就是由一些具有不确定性的规则组成，而它的数据库中包含了一些具有一定不确定性的证据。在这种情况下，如果在推理过程中仍然采用经典地、基于逻辑的、精确的推理方法，必然会把客观事物原本具有的不确定性以及事物间客观存在的不确定性关系归为确定性的，从而失去对客观世界描述的真实性。,5.2 不确定性推理中的基本问题,1、不确定性的表示（1）证据不确定性的表示（2）知识不确定性的表示2、推理计算（1）不确定性传递问题（2）证据不确定性的合成问题（3）结论不确定性的合成问题3、不确定性的度量,5.3 主观Bayes方法,主观Bayes方法又称主观概率论，是由杜达等人于1976年提出的一种不确定推理模型，它是对概率论中基本Bayes公式的改进，是一种基于概率逻辑的方法。该方法在地矿勘探专家系统PROSPECTOR中得到了成功的应用。,基本Bayes公式,设事件B1,B2,Bn是彼此独立、互不相容的事件,B1 B2 Bn全集，且P(Bi)0(i=1,2,n)。对于任一事件A能且只能与B1,B2,Bn 中的一个同时发生，而且P(A)0。,主观Bayes方法及其推理网络,为了进行不确定推理，把所有的知识规则连接成一个有向图，图中的各节点代表假设结论，弧代表规则，并引入两个数值（LS,LN）与每一条弧相联系，用来度量规则成立的充分性和必要性。LS表示规则成立的充分性，LN表示规则成立的必要性，把这样的有向图称为推理网络。,推理网络,H2,E4,H1,E2,A,E1,E3,（200，0.1）,（100，0.1）,（2，0.001）,（1，0.02）,（0.8，2）,（10，0.3）,知识不确定性的表示,IF E THEN(LS,LN)H(P(H)(LS,LN)是为度量产生式规则的不确定性而引入的一组数值，LS表示规则成立的充分性，用于指出证据E对结论H为真的支持程度；而LN 则表示规则成立的必要性，用于指出证据E对结论H为真的必要性程度。,不确定性的推理计算,主观Bayes方法的任务是根据证据E的概率P(E)及影响结论的知识之规则强度（LS,LN），把H的先验概率P(H)更新为后验概率P(H/E)或P(H/E),1、确定性证据,(1)证据肯定出现的情况 P(E)=1,(2)证据肯定不出现的情况,P(E)=0 P(E)=1,知识规则强度（LN,LS）意义的讨论,充分性度量LS的讨论（1）LS1时，O(H/E)O(H)，再由P(x)与O(x)具有相同单调性特性，可得P(H/E)P(E)。当LS1时，由于证据E的出现，将增大结论H为真的概率，而且LS越大，P(H/E)就越大，即E对H为真的支持越强。,(2)LS=1时O(H/E)=O(H)表明E与H无关。(3)LS1时O(H/E)O(H)表明由于证据E出现，将使H为真的可能性下降。(4)LS=0时O(H/E)=0这表明由于证据E出现，将使H为假。领域专家在为LS赋值时，可参考上面的讨论，当证据E愈是支持H为真时，则使相应LS的值愈大。,必要性度量LN的讨论,当LN1时，有O(H/E)O(H)可得P(H/E)P(H)当LN1时，由于证据E不出现，将增大结论H为真的概率，而且LN越大，P(H/E)就越大，即 E对H为真的支持越强。,(2)LN=1时O(H/E)=O(H)表明 E与H无关。(3)LN1时O(H/E)O(H)表明由于证据E不出现，将使H为真的可能性下降。由此看出，E对H为真的必要性。(4)LN=0时O(H/E)=0这表明由于证据E不出现，将使H为假。领域专家在为LN赋值时，可参考上面的讨论，当证据E对H愈是重要时，则使相应LN的值愈小。,证据的不确定性,证据的不确定性度量用几率函数来描述：,讨论证据发生的各种可能性：,A必出现时（即P（A）1）:O(B|A)=LSO(B)O(B|A)=LNO(B),当A不确定时即P（A）1时A代表与A有关的所有观察，P(B|A)=P(B|A)P(A|A)+P(B|A)P(A|A)当P(A|A)=1时，证据A必然出现当P(A|A)=0时，证据A必然不出现当P(A|A)=P(A)时，观察A对A没有影响：P(B|A)=P(B),当存在两个证据时 P(A1A2|A)=minP(A1|A),P(A2|A)P(A1A2|A)=maxP(A1|A),P(A2|A)多个观察时若A1B，A2B而A1，A2相互独立，对A1，A2的观察分别为A1,A2,已知：P(A)=1,P(B1)=0.04,P(B2)=0.02R1:AB1 LS=20 LN=1R2:B1B2 LS=300 LN=0.001 计算：P(B2|A)分析：当使用规则R2时，证据B1并不是确定的发生了，即P(B1)1，因此要采用插值方法。解：先依照A必然发生，由定义和R1得：O(B1)=0.04/(1-0.04)=0.0417O(B1|A)=LS*O(B1)=0.83P(B1|A)=0.83/(1+0.83)=0.454然后假设P(B1|A)=1,计算：P(B2|B1)=300*0.02/(300*0.02+1)=0.857最后进行插值：P(B2|A)=0.02+(0.857-0.02)*(0.454-0.04)/(1-0.04)=0.410,确定性推理方法,以产生式作为知识表示方法的专家系统MYCIN中，第一次使用了不确定性推理方法，给出了以确定性因子或称可信度作为不确定性的度量。这种推理方法也要解决几个方面的核心问题，即规则和证据的不确定性度量问题，不确定性的传播与更新问题。,确定性方法遵循的原则：,不采用严格的统计理论。使用的是一种接近统计理论的近似方法。用专家的经验估计代替统计数据 尽量减少需要专家提供的经验数据，尽量使少量数据包含多种信息。新方法应适用于证据为增量式地增加的情况。专家数据的轻微扰动不影响最终的推理结论。,规则的不确定性度量:,有规则A B，其可信度CF(B,A)定义如下:,CF(B,A)表示的意义：,证据为真是相对于P(B)=1-P(B)来说，A对B为真的支持程度，即A发生更支持B发生，此时 CF(B,A)0。相对于P(B)来说，A对B为真的不支持程度。即A发生不支持B发生，此时 CF(B,A)0。它总是满足条件-1 CF(B,A)1。,CF(B,A)表示的意义：,CF(B,A)的特殊值：CF(B,A)=1，前提真，结论必真CF(B,A)=-1，前提真，结论必假CF(B,A)=0，前提真假与结论无关 实际应用中CF(B,A)的值由专家确定,证据A的可信度用CF(A)来表示，为了计算方便，规定：-1 CF(A)1不难理解，可信度CF(A)的如下特殊值的含义：CF(A)=1，前提肯定真CF(A)=-1，前提肯定假CF(A)=0，对前提一无所知CF(A)0，表示A以CF(A)程度为真CF(A)0，表示A以CF(A)程度为假实际使用时，初始证据的CF值有专家根据经验提供，其它证据的CF通过规则进行推理计算得到。,不确定性的传播与更新,与的计算：A1 A2 BCF(A1 A2)=min CF(A1),CF(A2)或的计算：A1 A2 BCF(A1 A2)=max CF(A1),CF(A2)“非”的计算：CF(A)=CF(A)由A，A B，求 CF(B)：CF(B)=max(0，CF(A)CF(B,A),合成,由规则A1B可求得CF1（B），同时又有规则A2B，可求得CF2（B）。如何计算其合成后的可信度CF（B）？先有：CF1(B)=max(0，CF(A1)CF(B,A1)CF2(B)=max(0，CF(A2)CF(B,A2),CF(B)的更新计算:,已知证据A 的可信度CF（A），结论B的原有可信度CF（B），求A通过规则AB，作用到B后，B的可信度的更新值CF（B|A）。当CF（A）=1时，即A必然发生时：,当0CF（A）1时，即A可能发生时：此时取CF（A）*CF（B，A）代替上式中的规则可信度CF（B，A）即可。即更新后的可信度公式为：,当CF（A）0时，即A不可能发生时：规则AB不使用，即认为不可能发生的事件（A为假的事件）对结果B没有影响。在MYCIN系统规定CF（A）0.2就认为规则不可使用。,注意：以上公式不满足组合交换性。而且，EMYCIN系统（MYCIN的修正版）对于CF（B），CF（B，A）符号不同时（一个为正，一个为负），采用下面的公式来计算：修改后的公式克服了原来的组合不可交换的缺点。,已知 R1：A1B1 CF（B1，A1）0.8 R2：A2B1 CF（B1，A2）0.5R3：B1A3B2 CF（B2，B1A3）0.8CF（A1）=1CF（A2）1CF（A3）1；CF（B1）=0CF（B2）=0；计算 CF（B1）、CF（B2）,依规则R1，CF(B1|A1)CF(B1)CF(B1,A1)(1CF(B1)0.8，即更新后CF(B1)0.8依规则R2：CF(B1|A2)CF(B1)CF(B1,A2)(1CF(B1)0.9更新后CF(B1)0.9依R3，先计算CF(B1A3)min(CF(A3),CF(B1)0.9由于CF(B1A3)1，CF(B2|B1A3)=CF(B2)+CF(B1A3)CF(B2，B1A3)(1-CF(B2)=0+0.90.8(1-0)=0.72答：更新后的可信度分别是：CF(B1)0.9，CF(B2)0.72,确定性方法的宗旨不是理论上的严密性，而是处理实际问题的可用性。同时，也不可能一成不变地用于任何领域，甚至也不能适用于所有科学领域，推广至一个新领域时必须根据具体情况修改。,1.已知：规则 R1：E1H，CF（H，E1）0.9R2：E2H，CF（H，E2）0.6 R3：E3H，CF（H，E3）-0.5R4：E4(E5E6)E1，CF（E1，E4(E5E6)）0.9 初始数据：CF（E2）0.8，CF（E3）0.6，CF（E4）0.5 CF（E5）0.6，CF（E6）0.8 CF（H）=0 求：CF（H）,