第四章不确定知识表示和推理.ppt-得力文库

资源描述

《第四章不确定知识表示和推理.ppt》由会员分享，可在线阅读，更多相关《第四章不确定知识表示和推理.ppt（75页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、1第四章不确定知识表示和推理第四章不确定知识表示和推理内容提要内容提要:4.1 4.1 不确定推理概述不确定推理概述 4.2 4.2 确定型理论确定型理论CFCF模型模型 4.3 4.3 主观主观BayesBayes方法方法 4.4 D-S4.4 D-S证据理论证据理论2l在现实世界中，包含有大量的柔性信息，表征出模糊性、复杂性和不精确性，因而不精确推理、非单调推理和模糊推理就变得十分重要了。l著名的逻辑学家Russell所说的“所有的传统逻辑都习惯地假设所使用的符号是精确的，所以它就不能适用于我们这个人间的世界，而只能适应于一个理想中的天堂，逻辑研究比别的任何研究都使我们更接近上帝。4.1

2、4.1 不确定推理概述不确定推理概述3l不确定性问题的代数模型对于不确定性推理来说，不确定性的描述和不确定性的传播是两个主要问题。不确定性问题模型需要涉及下面的三个问题。l不确定性知识的表示l不确定性知识的推理l不确定推理的语义不确定推理概述不确定推理概述4l不确定性知识的表示l 不确定性知识的表示主要解决用什么方法来描述知识的不确定性问题。常用的方法有数值法和非数值法。数值法以概率方法、确定因子法、DS证据理论和可能性理论为代表；非数值法则以批注理论和非单调逻辑为代表。数值法表示便于计算、比较，非数值法表示便于定性分析，两种方法的结合是描述不确定性知识的好办法。不确定推理概述不确定推理概述

3、5l不确定性知识的推理l 不确定性知识的推理是指知识不确定性的传播和更新，即新的不确定性知识的获取过程。这个过程是在“公理”(比如领域专家给出的规则强度和用户给出的原始证据的不确定性度)的基础上，定义一组函数，计算出“定理”(非原始数据的命题)的不确定性度量。也就是说，根据原始证据的不确定性和知识的不确定性，求出结论的不确定性。l 算法1：根据规则前提E的不确定性C(E)和规则强度f(H，E)，求出假设H的不确定性C(H)，即定义函数g1，使得 C(H)g1C(E)，f(H，E)不确定推理概述不确定推理概述6l 算法2：根据分别由独立的证据E1和E2所求得的假设H的不确定性C1(H)和C2(H

4、)，求出证据E1和E2的组合所导致的假设H的不确定性C(H)，即定义函数g2，使得 C(H)g2C1(H)，C2(H)l 算法3：根据两个证据E1和E2的不确定性C(E1)和C(E2)，求出证据E1和E2的合取的不确定性，即定义函数g3，使得 C(E1E2)g3C(E1)，C(E2)l 算法4：根据两个证据E1和E2的不确定性C(E1)和C(E2)，求出证据E1和E2的析取的不确定性，即定义函数g4，使得 C(E1E2)g4C(E1)，C(E2)不确定推理概述不确定推理概述7l 观察图所示的推理网络。设A1、A2、A3和A4为原始证据，即已知证据A1、A2、A3和A4的不确定性分别为C(A1)

5、、C(A2)、C(A3)和C(A4)。求A5、A6和A7的不确定性。1由证据A1和A2的不确定性C(A1)和C(A2)，根据算法4求出A1和A2析取的不确定性C(AlA2)。2由A1和A2析取的不确定性C(AlA2)和规则R1的规则强度f1，根据算法1求出A5的不确定性C(A5)。A7A5A6A3A1A2A4ORANDf3f4f1f2R3R4R1R2不确定推理概述不确定推理概述8 3由证据A3和A4的不确定性C(A3)和C(A4)，根据算法3求出A3和A4合取的不确定性C(A3A4)。4由A3和A4合取的不确定性C(A3A4)和规则R2的规则强度f2，根据算法1求出A6的不确定性C(A6)。5

6、由A5的不确定性C(A5)和规则R3的规则强度f3，根据算法1求出A7的其中的一个不确定性C(A7)。6.由A6的不确定性C(A6)和规则R4的规则强度f4，根据算法1求出A7的另外一个不确定性C(A7)。7由A7的两个根据独立证据分别求出的不确定性C(A7)和C(A7)，根据算法2求出A7最后的不确定性C(A7)。不确定推理概述不确定推理概述9l不确定推理的语义l对于一个不确定推理问题应指出不确定性表示和推理的含义。基于概率论的方法能较好地解决这个问题。l 如规则强度f(B，A)可理解为当证据A为真时，对假设B为真的一种影响程度；而C(A)可理解为A为真的程度，即对于f(B，A)和C(A)，

7、应给出:对于f(B，A)而言：(1)A为真则B为真，这时f(B，A)?(2)A为真则B为假，这时f(B，A)?(3)A对B没有影响时，这时f(B，A)?对于C(A)而言：(1)A为真时，C(A)?(2)A为假时，C(A)?(3)对A一无所知时，C(A)?不确定推理概述不确定推理概述10l几种主要的不确定性推理方法确定性理论确定因子法是MYCIN专家系统中使用的不确定性推理方法。该方法以确定性理论为基础，采用可信度来刻画不确定性。其优点是简单、实用，在许多专家系统中得到了应用，取得了较好的效果。主观贝叶斯方法主观贝叶斯方法是PROSPECTOR专家系统中使用的不确定性推理方法。它是基于贝叶斯

8、(Bayes)公式修正后而形成的一种不确定性推理方法。该方法的优点是具有较强的数学基础，计算工作量也较为适中。不确定推理概述不确定推理概述11D-S证据理论 D-S证据理论是由Dempster提出，由他的学生Shafer发展起来的。该理论引进了信任函数，这些函数可以满足比概率函数的公理还要弱的公理，因而可以用来处理由“不知道”所引起的不确定性。可能性理论可能性理论的基础是Zadeh本人的模糊集合理论。正如概率论处理的是由随机性引起的不确定性一样，可能性理论处理的是由模糊性引起的不确定性。不确定推理概述不确定推理概述12批注理论批注理论(Endorsement)是一种非数值方法。它将系统所使

9、用的推理规则和议程中的任务都加以批注。规则的批注提出前提条件与规则结论的关系，任务的批注指出该任务的结论与议程中另一任务的结论之间的协同、冲突、潜在冲突及冗余情况。这些批注与数据源、数据类型和数据的精度有关。该理论的优点是可以表示出用数值难以表达的较复杂的关系。缺点是系统每步规则推理都要将前提的批注转移到结论中，从而使得结论中的批注迅速增长，对于结论的选择变得困难。不确定推理概述不确定推理概述13l知识的不确定性在MYCIN中的知识表示：IF El AND E2 ANDAND En THEN H(x)其中Ei(i1，2，.，n)是证据，H可以是一个或多个结论。具有此规则形式的解释为当证据E1

10、、E2、En都存在时，结论H具有x大小的确定性因子CF(Certainty Factor)。即 x=CF(H,E1 AND E2 AND.AND En)x的具体值由领域专家主观地给出，x的取值范围为-1，1内。x0表示证据存在，增加结论为真的确定性程度，x越大结论越真，x1表示证据存在结论为真。相反，x0表示证据存在，增加结论为假的确定性程度，x越小结论越假，x-1表示证据存在结论为假。x0时，则表示证据与结论无关。4.2 4.2 确定性理论确定性理论CFCF模型模型14l证据的不确定性在MYCIN系统中，证据的不确定性是用证据的确定性因子CF(E)表示的。原始证据的确定性因子由用户主观地给

11、出，非原始证据的确定性因子由不确定性推理获得。值域l当证据E以某种程度为真时，有0CF(E)l。l当证据E以某种程度为假时，有-1CF(E)0。l当证据E一无所知时，有CF(E)0。典型值l 当证据E肯定为真时，有CF(E)l。l 当证据E肯定为假时，有CF(E)-1。l 当证据E一无所知时，有CF(E)0。确定性理论确定性理论CFCF模型模型15l不确定性推理算法E肯定存在在证据E肯定存在时有CF(E)1，那么结论H的确定性因子为规则的确定性因子，即 CF(H)CF(H，E)E不是肯定存在在客观的现实世界中，对证据的观察往往也是不确定的。除此之外，证据E可能还是另一条规则的结论，这时也常

12、常是不确定的。在这种情况下，结论H的确定性因子CF(H)不仅取决于规则的确定性因子CF(H，E)，而且还取决于证据E的确定性因子CF(E)。计算公式为 CF(H)CF(H，E)max0，CF(E)确定性理论确定性理论CFCF模型模型16证据是多个条件的逻辑组合l证据是合取连接若系统有规则形如 IF E1 AND E2 ANDAND En THEN H(x)，那么，有 CF(E)CF(E1 AND E2 AND.AND En)minCF(E1)，CF(E2)，.，CF(En)l证据是析取连接这时，EE1 OR E2 OR.OR En，有 CF(E)CF(E1 OR E2 0R.OR En)m

13、axCF(E1)，CF(E2)，.，CF(En)确定性理论确定性理论CFCF模型模型17两条规则具有相同结论若有两条规则分别是 IF E1 THEN H(CF(H，E1)IF E2 THEN H(CF(H，E2)那末首先分别计算出CF1(H)和CF2(H)：CF1(H)CF(H，E1)max0，CF(E1)CF2(H)CF(H，E2)max0，CF(E2)确定性理论确定性理论CFCF模型模型18然后用公式 CF1(H)十CF2(H)-CF1(H)CF2(H)；若CFl(H)0且CF2(H)0CF12(H)CF1(H)十CF2(H)十CF1(H)CF2(H)；若CF1(H)0且CF2(H)0

14、(CF1(H)十CF2(H)/(1-min|CF1(H)|,|CF2(H)|)；其他计算出由E1和E2组合而导出的确定性因子CF12(H)。可以证明该叠加算法：1.拒绝接受一个假设既肯定成立又肯定不成立的情况，除此情况外，若有证据能确定一个假设肯定成立（或肯定不成立）则不必考虑其它证据对该假设的影响。2.两个证据对同一假设的支持作用是相互加强的，但叠加后的可信度不会大于1。确定性理论确定性理论CFCF模型模型193.两个证据对同一假设的反对作用也是相互加强的，但叠加后的可信度不会小于-1。4.两个证据对同一假设的支持和反对作用是相互削弱的，假设成立的可信度的符号取决于作用较强的一个。5.推理所

15、得的结果与证据提供的顺序无关。6.在对某一假设的成立有起反对作用的证据存在时，对该假设起支持作用的证据的积累可以抵消反对作用，直至可以使假设成立的可信度接近或达到1。反之亦然。确定性理论确定性理论CFCF模型模型20举例有如下的推理规则：Rule l：IF E1 THEN H(0.9)Rule 2：IF E2 THEN H(0.7)Rule 3：IF E3 THEN H(-0.8)Rule 4：IF E4 AND E5 THEN E1(0.7)Rule 5：IF E6 AND(E7 0R E8)THEN E2(1.0)HE1E2E6E4E5ORAND0.9-0.80.71.0R1R3R4R5E

16、3E7E80.7R2AND确定性理论确定性理论CFCF模型模型21 在图中，E3、E4、E5、E6、E7和E8为原始证据，其确定性因子由用户给出，假定它们的值为：CF(E3)0.3，CF(E4)0.9，CF(E5)0.6，CF(E6)0.7，CF(E7)-0.3，CF(E8)0.8。求CF(H)=？解：先求出CF(E1)、CF(E2)和CF(E3)。CF(E1)07max0，CF(E4 AND E5)07max0，minCF(E4)，CF(E5)07max0，min09，06 07max0，06 o706 0.42确定性理论确定性理论CFCF模型模型22CF(E2)1max0，CF(E6 AN

17、D(E7 OR E8)1max(0，minCF(E6)，maxCF(E7)，CF(E8)1max0，minCF(E6)，max-0.3，0.8 1max0，min0.7，0.8 1max0，0.7 10.7 0.7CF(E3)0.3CF1(H)09max0，CF(E1)09max0，042 09042 038确定性理论确定性理论CFCF模型模型23CF2(H)07max0，CF(E2)07max0，07 0707 049CF3(H)08CF(E3)0803 024CF12(H)CF1(H)十CF2(H)-CF1(H)CF2(H)038十0490380.4906838CF(H)CF123(H)(

18、CF12(H)十CF3(H)/(1min|CF12(H)|,|CF3(H)|)(06838024)/(1 0.24)05839确定性理论确定性理论CFCF模型模型24CF模型的优点是：l简单、直观。主要表现在组合假设和证据的不确定性的计算十分简单，而且不需要把信任和不信任的判断知识表示成概率的形式。我们知道，把某个值指派给一个假设的确定性因子要比把一个概率直接指派给一个假设要容易得多。l计算仅有线性的信息和时间的复杂度，而且推理的近似效果也比较理想。l可以证明，推理的结果与证据提供的顺序无关。推理过程中的阈值l推理所得到的结论中有的可信度很低，可以设定一个阈值，在推理过程中去掉那些可信度低于阈

19、值的结论。l一般阈值定为0.2，当CF0.2时，置CF0，当CF0.2时，CF有意义。确定性理论确定性理论CFCF模型模型25练习练习练习练习设有一组知识：R1：If E1 Then H CF(H，E1)=0.8R2：If E2 Then H CF(H，E2)=0.6R3：If E3 Then H CF(H，E3)=-0.5R4：If E4(E5E6)Then E1 CF(E1，E4(E5E6)=0.7R5：If E7 E8 Then E3 CF(E3，E7 E8)=0.9已知CF(E2)=0.8,CF(E4)=0.5,CF(E5)=0.6,CF(E6)=0.7,CF(E7)=0.6,CF(E

20、8)=0.9,求CF(H)确定性理论确定性理论CFCF模型模型26lBayes定理条件概率设A与B是某个随机试验中的两个事件，如果在事件B发生的条件下考虑事件A发生的概率，就称它为事件A的条件概率，记为P(A|B)。例设样本空间D是扑克牌中的54张牌，即 D=红桃A,方块A,黑桃A,梅花A,红桃2,方块2,小王，大王且有以下两个事件 A=取花脸牌，B=取红桃牌4.3 4.3 主观主观BayesBayes方法方法27求在事件B发生的条件下事件A发生的概率P(A|B)。解：由于事件B已经发生，因此以下事件取到红桃A；取到红桃2；取到红桃3；取到红桃K中必有一个出现。而对事件A，在事件B发生的

21、前提下，只有以下事件取到红桃J；取到红桃Q；取到红桃K中的一个发生时事件A才发生。因此，在事件B发生的条件下事件A发生的概率为3/13。主观主观BayesBayes方法方法28条件概率的计算由上例可以看出，在事件B发生的条件下事件A的条件概率，是把B的样本点作为新的样本空间D1，然后在D1上求出事件AB的概率。P(取花脸牌|取红桃牌)=P(取红桃花脸牌)/P(取红桃牌)=(3/54)(13/54)=3/13主观主观BayesBayes方法方法29l全概率公式设事件A1，A2，An满足：(1)任意两个事件都互不相容，即当ij时，有AiAj=(i=1，2，n；j=1，2，n)；(2)P(Ai)

22、0(i=1，2，n)；n(3)D=U Ai。i=1则对任何事件B有：n P(B)=(P(Ai)P(B|Ai)i=1主观主观BayesBayes方法方法30l例：A1=取红桃牌 A2=取方块牌 A3=取黑桃牌 A4=取梅花牌 A5=取王牌 B=取花脸牌解:P(B)=P(A1)P(B|A1)+P(A2)P(B|A2)+P(A3)P(B|A3)+P(A4)P(B|A4)+P(A5)P(B|A5)=(13/54 3/13)4+2/54 0 =12/54主观主观BayesBayes方法方法31lBayes公式设事件A1，A2，An两两互不相容，且它们构成全部样本空间，则对任何事件B有：我们称这个公式为

24、es公式可以写成为 P(H|E)=P(E|H)P(H)/P(E)在直接使Bayes公式描述不确定性时，计算后验概率P(H|E)需要知道先验概率P(E|H)，如要计算咳嗽的病人患有肺炎的概率，先要要知道肺炎病人有咳嗽症状的概率。而因为先验概率又是难以给出的量，为了克服这一困难，所以就提出了主观Bayes方法。下面我们介绍主观Bayes方法对规则不确定性的描述。主观主观BayesBayes方法方法34 几率函数O(x)l几率函数定义为O(x)P(x)/(1-P(x)。l它表示x出现的概率与不出现概率之比，从定义可知，随着P(x)的增大，O(x)也增大，而且当P(x)0时，有O(x)0 当P(x)

25、1时，有O(x)这样，取值为0，1的P(x)被放大为取值为0,的O(x)。充分性度量LSl充分性度量定义为LSP(E|H)/P(E|H)必要性度量LNl必要性度量定义为LNP(E|H)/P(E|H)主观主观BayesBayes方法方法35规则不确定性描述根据Bayes公式有 P(H|E)P(E|H)P(H)/P(E)(1)P(H|E)P(E|H)P(H)/P(E)(2)将上述两式相除，得P(H|E)/P(H|E)=P(E|H)/P(E|H)P(H)/P(H)再利用几率函数和LS，上式可表示为 O(H|E)LSO(H)可以看出，当LS1时，O(H|E)O(H)，说明E(发热)支持H(肺炎)，LS

26、越大，O(H|E)就越大，即P(H|E)越大，说明E对H的支持越强。当LS时，O(H|E)，从而有P(H|E)1，说明E的存在导致H为真。因此，我们说E对H是充分的，且称LS为充分性度量。主观主观BayesBayes方法方法36 同理，将前面(1)(2)中的E换为E，可以得到 O(H|E)=LNO(H)LN反映了E(发热)不出现对H(肺炎)的反对程度。LN越小，说明E不出现，H的确定性越小。当LN0时，将导致O(H|E)0，说明E不存在导致H为假。因此，我们说E对H是必要的，且称LN为必要性度量。在主观Bayes方法中，一条规则变成了如下的形式：IF E THEN(LS，LN)H 其中参数LS

27、，LN和先验几率O(H)要由领域专家主观给出，先计算出后验几率，再计算出后验概率。LS1&LN1,LS1&LN0，则称A为Bel的焦元；信任函数Bel的所有焦元联合称为核；如果Bel的所有焦元皆为原子命题，则Bel就为贝叶斯的。Dempster组合规则定义定义6 设Bel1和Bel2是同一辨识框架上的两个信任函数，具有基本概率分配函数m1和m2以及核和，且设那么对于所有基本概率分配的非空集A，由下式定义的可以计算这两个证据共同作用产生的基本概率分配函数。合成后的信任函数称作Bel1和Bel2的正交和，记为 Bel2。D-SD-S证据理论证据理论65l对于多个信任函数的合成，设Bel1,B

28、el2,Beln是同一辨识框架上的信任函数，m1,m2,mn分别是其对应的基本概率分配函数，如果存在且基本概率分配函数为m，则l其中，。k-1可作为各数据源矛盾程度的测度，k-1越大，证据间矛盾越激烈。l从上式可以看出，多个证据的结合与次序无关，多个证据的计算可以用两个证据结合的计算递推得到。D-SD-S证据理论证据理论66多个证据的组合多个证据的组合D-SD-S证据理论证据理论BelkBel3BelBel等效于BelkBel2Bel1D-S证据组合Bel2Bel1D-S证据组合D-S证据组合D-S证据组合67例设辨识框架=a,b,c，若基于两组不同证据而导出的基本概率分配函数分别为：m1

29、(a)=0.4，m1(a,c)=0.4，m1(a,b,c)=0.2 m2(a)=0.6，m2(a,b,c)=0.4 计算k=1-0=1将m1和m2合并，m(a)=m1(a)m2(a)+m1(a)m2(a,b,c)+m1(a,c)m2(a)+m1(a,b,c)m2(a)=0.76 m(a,c)=m1(a,c)m2(a,b,c)=0.16 m(a,b,c)=m1(a,b,c)m2(a,b,c)=0.08D-SD-S证据理论证据理论68练习练习设样本空间=a,b,c，m1,m2为定义在上的概率分配函数。已知：m1(a)=0.4,m1(b,c)=0.4,m1(a,b,c)=0.2 m2(a)=0.6,

30、m2(a,b,c)=0.4求它们的正交和m1m2 D-SD-S证据理论证据理论69例：设有规则：(1)如果流鼻涕则感冒但非过敏性鼻炎(0.9)或过敏性鼻炎但非感冒(0.l)(2)如果眼发炎则感冒但非过敏性鼻炎(0.8)或过敏性鼻炎但非感冒(0.05)括号中的数字表示规则前提对结论的支持程度。又有事实：(1)小王流鼻涕(0.9)(2)小王眼发炎(0.4)括号中的数字表示事实的可信程度问：小王患什么病？用证据理论求解这一医疗诊断问题。D-SD-S证据理论证据理论70解：首先，取辨识框架=h1,h2,h3其中，h1表示“感冒但非过敏性鼻炎”，h2表示“过敏性鼻炎但非感冒”，h3表示“

31、同时得了两种病”。再取下面的基本概率分配函数：m1(h1)=规则前提事实可信度*规则结论可信度=0.9*0.9=0.81m1(h2)=0.9*0.1=0.09m1(h1,h2,h3)=1-m1(h1)-m1(h2)=1-0.81-0.09=0.1m1(A)=0(A为的其他子集)m2(h1)=0.4*0.8=0.32m2(h2)=0.4*0.05=0.02m2(h1,h2,h3)=1-m2(h1)-m2(h2)=1-0.32-0.02=0.66m2(A)=0(A为的其他子集)D-SD-S证据理论证据理论71将两个概率分配函数合并：k=1/1-m1(h1)m2(h2)+m1(h2)m2(h1)=1

32、.05 m(h1)=km1(h1)m2(h1)+m1(h1)m2(h1,h2,h3)+m1(h1,h2,h3)m2(h1)=0.87 m(h2)=km1(h2)m2(h2)+m1(h2)m2(h1,h2,h3)+m1(h1,h2,h3)m2(h2)=0.066 m(h1,h2,h3)=1-m(h1)-m(h2)=0.064D-SD-S证据理论证据理论72由信任函数求信任度：Bel(h1)=m(h1)=0.87 Bel(h2)=m(h2)=0.066由似然函数求似然度：Pl(h1)=1-Bel(h1)=1-Bel(h2,h3)=1-m(h2)+m(h3)=1-0.066+0 =0.934 Pl(

33、h2)=1-Bel(h2)=1-Bel(h1,h3)=0.13于是，最后得到：“感冒但非过敏性鼻炎”为真的信任度为0.87，非假的信任度为0.934；“过敏性鼻炎但非感冒”为真的信任度为0.066，非假的信任度为0.13；D-SD-S证据理论证据理论73第四章不确定知识表示和推理基于谓词逻辑的机器推理1.猴子香蕉问题已知一串香蕉挂在天花板上，猴子直接去拿是够不到的，但猴子可以走动且可以搬着梯子走动，也可以爬上梯子来达到吃香蕉的目的。用谓词逻辑描述该问题，并求得该问题的目标状态（猴子吃到香蕉列）。2.设已知：(1)凡是清洁的东西就有人喜欢；(2)人们都不喜欢苍蝇；求证：苍蝇是不清洁的。3.求求下列谓词公式的前束范式、下列谓词公式的前束范式、Skolem标准型及子句集标准型及子句集 x yP(x,y)yQ(x,y)R(x,y)74第四章不确定知识表示和推理知识表示方法1.用语义网络表示下述命题：(1)树和草都是植物。(2)树和草都是有根、有叶的。(3)水草是草，且长在水中。(4)果树是树，且会结果。(5)苹果树是果树中的一种，它结苹果。2.用谓词公式表示下列规则性知识：(1)所有整数要么是偶数要么就是奇数。(2)自然数都是大于零的整数。75第四章不确定知识表示和推理再见

展开阅读全文