第四章不确定知识表示和推理

1第四章不确定知识表示和推理李伟生信科大厦19楼Tel：[e-mail]2第4章不确定知识表示和推理内容提要:4.1不确定推理概述4.2确定型理论—CF模型4.3主观Bayes方法4.4D-S证据理论3在现实世界中，包含有大量的柔性信息，表征出模糊性、复杂性和不精确性，因而不精确推理、非单调推理和模糊推理就变得十分重要了。著名的逻辑学家Russell所说的“所有的传统逻辑都习惯地假设所使用的符号是精确的，所以它就不能适用于我们这个人间的世界，而只能适应于一个理想中的天堂……，逻辑研究比别的任何研究都使我们更接近上帝。4.1不确定推理概述4不确定性问题的代数模型–对于不确定性推理来说，不确定性的描述和不确定性的传播是两个主要问题。–不确定性问题模型需要涉及下面的三个问题。不确定性知识的表示不确定性知识的推理不确定推理的语义不确定推理概述5不确定性知识的表示不确定性知识的表示主要解决用什么方法来描述知识的不确定性问题。常用的方法有数值法和非数值法。数值法以概率方法、确定因子法、D—S证据理论和可能性理论为代表；非数值法则以批注理论和非单调逻辑为代表。数值法表示便于计算、比较，非数值法表示便于定性分析，两种方法的结合是描述不确定性知识的好办法。不确定推理概述6不确定性知识的推理不确定性知识的推理是指知识不确定性的传播和更新，即新的不确定性知识的获取过程。这个过程是在“公理”(比如领域专家给出的规则强度和用户给出的原始证据的不确定性度)的基础上，定义一组函数，计算出“定理”(非原始数据的命题)的不确定性度量。也就是说，根据原始证据的不确定性和知识的不确定性，求出结论的不确定性。算法1：根据规则前提E的不确定性C(E)和规则强度f(H，E)，求出假设H的不确定性C(H)，即定义函数g1，使得C(H)＝g1[C(E)，f(H，E)]不确定推理概述7算法2：根据分别由独立的证据E1和E2所求得的假设H的不确定性C1(H)和C2(H)，求出证据E1和E2的组合所导致的假设H的不确定性C(H)，即定义函数g2，使得C(H)＝g2[C1(H)，C2(H)]算法3：根据两个证据E1和E2的不确定性C(E1)和C(E2)，求出证据E1和E2的合取的不确定性，即定义函数g3，使得C(E1∧E2)＝g3[C(E1)，C(E2)]算法4：根据两个证据E1和E2的不确定性C(E1)和C(E2)，求出证据E1和E2的析取的不确定性，即定义函数g4，使得C(E1∨E2)＝g4[C(E1)，C(E2)]不确定推理概述8观察图所示的推理网络。设A1、A2、A3和A4为原始证据，即已知证据A1、A2、A3和A4的不确定性分别为C(A1)、C(A2)、C(A3)和C(A4)。求A5、A6和A7的不确定性。1．由证据A1和A2的不确定性C(A1)和C(A2)，根据算法4求出A1和A2析取的不确定性C(Al∨A2)。2．由A1和A2析取的不确定性C(Al∨A2)和规则R1的规则强度f1，根据算法1求出A5的不确定性C(A5)。A7A5A6A3A1A2A4ORANDf3f4f1f2R3R4R1R2不确定推理概述93．由证据A3和A4的不确定性C(A3)和C(A4)，根据算法3求出A3和A4合取的不确定性C(A3∧A4)。4．由A3和A4合取的不确定性C(A3∧A4)和规则R2的规则强度f2，根据算法1求出A6的不确定性C(A6)。5．由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)。不确定推理概述10不确定推理的语义对于一个不确定推理问题应指出不确定性表示和推理的含义。基于概率论的方法能较好地解决这个问题。如规则强度f(B，A)可理解为当证据A为真时，对假设B为真的一种影响程度；而C(A)可理解为A为真的程度，即对于f(B，A)和C(A)，应给出:对于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)＝?不确定推理概述11几种主要的不确定性推理方法–确定性理论确定因子法是MYCIN专家系统中使用的不确定性推理方法。该方法以确定性理论为基础，采用可信度来刻画不确定性。其优点是简单、实用，在许多专家系统中得到了应用，取得了较好的效果。–主观贝叶斯方法主观贝叶斯方法是PROSPECTOR专家系统中使用的不确定性推理方法。它是基于贝叶斯(Bayes)公式修正后而形成的一种不确定性推理方法。该方法的优点是具有较强的数学基础，计算工作量也较为适中。不确定推理概述12–D-S证据理论D-S证据理论是由Dempster提出，由他的学生Shafer发展起来的。该理论引进了信任函数，这些函数可以满足比概率函数的公理还要弱的公理，因而可以用来处理由“不知道”所引起的不确定性。–可能性理论可能性理论的基础是Zadeh本人的模糊集合理论。正如概率论处理的是由随机性引起的不确定性一样，可能性理论处理的是由模糊性引起的不确定性。不确定推理概述13–批注理论批注理论(Endorsement)是一种非数值方法。它将系统所使用的推理规则和议程中的任务都加以批注。规则的批注提出前提条件与规则结论的关系，任务的批注指出该任务的结论与议程中另一任务的结论之间的协同、冲突、潜在冲突及冗余情况。这些批注与数据源、数据类型和数据的精度有关。该理论的优点是可以表示出用数值难以表达的较复杂的关系。缺点是系统每步规则推理都要将前提的批注转移到结论中，从而使得结论中的批注迅速增长，对于结论的选择变得困难。不确定推理概述14知识的不确定性–在MYCIN中的知识表示：IFElANDE2AND．．．．．．ANDEnTHENH(x)其中Ei(i＝1，2，...，n)是证据，H可以是一个或多个结论。具有此规则形式的解释为当证据E1、E2、…、En都存在时，结论H具有x大小的确定性因子CF(CertaintyFactor)。即x=CF(H,E1ANDE2AND......ANDEn)x的具体值由领域专家主观地给出，x的取值范围为[-1，1]内。x＞0表示证据存在，增加结论为真的确定性程度，x越大结论越真，x＝1表示证据存在结论为真。相反，x＜0表示证据存在，增加结论为假的确定性程度，x越小结论越假，x＝-1表示证据存在结论为假。x＝0时，则表示证据与结论无关。4.2确定性理论——CF模型15证据的不确定性–在MYCIN系统中，证据的不确定性是用证据的确定性因子CF(E)表示的。原始证据的确定性因子由用户主观地给出，非原始证据的确定性因子由不确定性推理获得。–值域当证据E以某种程度为真时，有0＜CF(E)≤l。当证据E以某种程度为假时，有-1≤CF(E)＜0。当证据E一无所知时，有CF(E)＝0。–典型值当证据E肯定为真时，有CF(E)＝l。当证据E肯定为假时，有CF(E)＝-1。当证据E一无所知时，有CF(E)＝0。确定性理论——CF模型16不确定性推理算法–E肯定存在在证据E肯定存在时有CF(E)＝1，那么结论H的确定性因子为规则的确定性因子，即CF(H)＝CF(H，E)–E不是肯定存在在客观的现实世界中，对证据的观察往往也是不确定的。除此之外，证据E可能还是另一条规则的结论，这时也常常是不确定的。在这种情况下，结论H的确定性因子CF(H)不仅取决于规则的确定性因子CF(H，E)，而且还取决于证据E的确定性因子CF(E)。计算公式为CF(H)＝CF(H，E)·max{0，CF(E)}确定性理论——CF模型17–证据是多个条件的逻辑组合证据是合取连接若系统有规则形如IFE1ANDE2AND．．．ANDEnTHENH(x)，那么，有CF(E)＝CF(E1ANDE2AND...ANDEn)＝min{CF(E1)，CF(E2)，...，CF(En)}证据是析取连接这时，E＝E1ORE2OR...OREn，有CF(E)＝CF(E1ORE20R...OREn)＝max{CF(E1)，CF(E2)，...，CF(En)}确定性理论——CF模型18–两条规则具有相同结论若有两条规则分别是IFE1THENH(CF(H，E1))IFE2THENH(CF(H，E2))那末首先分别计算出CF1(H)和CF2(H)：CF1(H)＝CF(H，E1)·max{0，CF(E1)}CF2(H)＝CF(H，E2)·max{0，CF(E2)}确定性理论——CF模型19然后用公式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(CF1(H)十CF2(H))/(1-min{|CF1(H)|,|CF2(H)|})；其他计算出由E1和E2组合而导出的确定性因子CF12(H)。可以证明该叠加算法：1.拒绝接受一个假设既肯定成立又肯定不成立的情况，除此情况外，若有证据能确定一个假设肯定成立（或肯定不成立）则不必考虑其它证据对该假设的影响。2.两个证据对同一假设的支持作用是相互加强的，但叠加后的可信度不会大于1。确定性理论——CF模型203.两个证据对同一假设的反对作用也是相互加强的，但叠加后的可信度不会小于-1。4.两个证据对同一假设的支持和反对作用是相互削弱的，假设成立的可信度的符号取决于作用较强的一个。5.推理所得的结果与证据提供的顺序无关。6.在对某一假设的成立有起反对作用的证据存在时，对该假设起支持作用的证据的积累可以抵消反对作用，直至可以使假设成立的可信度接近或达到1。反之亦然。确定性理论——CF模型21举例有如下的推理规则：Rulel：IFE1THENH(0.9)Rule2：IFE2THENH(0.7)Rule3：IFE3THENH(-0.8)Rule4：IFE4ANDE5THENE1(0.7)Rule5：IFE6AND(E70RE8)THENE2(1.0)HE1E2E6E4E5ORAND0.9-0.80.71.0R1R3R4R5E3E7E80.7R2AND确定性理论——CF模型22在图中，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)＝0．7×max{0，CF(E4ANDE5)}＝0．7×max{0，min{CF(E4)，CF(E5)}}＝0．7×max{0，min{0．9，0．6}}＝0．7×max{0，0．6}＝o．7×0．6＝0.42确定性理论——CF模型23CF(E2)＝1×max{0，CF(E6AND(E7ORE8))}＝1×max(0，min{CF(E6)，max{CF(E7)，CF(E8)}}}＝1×max{0，min{CF(E6)，max{-0.3，0.8}}}＝1×max{0，min{0.7，0.8}}＝1×max{0，0.7}＝1×0.7＝0.7CF(E3)＝0.3CF1(H)＝0．9×max{0，CF(E1)}＝0．9×max{0，0．42}＝0．9×0．42＝0．38确定性理论——CF模型24CF2(H)＝0．7×max{0，CF(E2)}＝0．7×max{0，0．7}＝0．7×0．7＝0．49CF3(H)＝－0．8×CF(E3)＝－0．8×0．3＝－0．24CF12(H)＝C