第4章非经典推理ppt课件

1、第四章 非经典推理,第3章讨论的推理方法都属于确定性推理，它们建立在经典逻辑基础上，运用确定性知识进行精确推理，也是一种单调性推理。现实世界中遇到的问题和事物间的关系，往往比较复杂，客观事物存在的随机性、模糊性、不完全性和不精确性，往往导致人们认识上一定程度的不确定性。这时，若仍然采用经典的精确推理方法进行处理，必然无法反映事物的真实性。为此，需要在不完全和不确定的情况下运用不确定知识进行推理，即进行不确定性推理。 本章将介绍一些不确定性推理技术，包括贝叶斯推理、概率推理、可信度方法和证据理论等，它们在后续的专家系统、机器人规划和机器学习等领域获得广泛应用,主要内容如下： 4.1 经典推理和非

2、经典推理 4.2 不确定性推理 4.3 概率推理 4.4 主观贝叶斯方法 4.5 可信度方法 4.6 证据理论,4.1 经典推理和非经典推理,传统人工智能即逻辑学派是建立在符号逻辑推理的基础上的。科学需要思维，思维是科技创新的源泉。思维也需要科学方法，也就是说要有正确的思维、科学的思维。逻辑和推理是以逻辑为基础的人工智能的两个基石。逻辑涉及思维的规范，而推理则与思维的法则有关。 一般提到的逻辑有形式逻辑和数理逻辑，消解原理就是以谓词逻辑为基础的。长期以来，形式逻辑和数理逻辑的研究和应用一直处于主导地位。然而，这两种逻辑存在一些局限性，无法解决面临的一些应用问题，从而出现了一些新的逻辑学派。人们

3、把这些新的逻辑学派称为非经典逻辑，其相应的推理方法则叫做非经典推理。因此相应地把传统的逻辑学派及其推理方法称为经典逻辑和经典推理,可从如下5点来说明非经典逻辑和非经典推理与经典逻辑和经典推理的区别： 1）在推理方法上，经典逻辑采用演绎逻辑推理，而非经典逻辑采用归纳逻辑推理。 2）在辖域取值上，经典逻辑都是二值逻辑，即只有真和假两种，而非经典逻辑都是多值逻辑，如三值、四值和模糊逻辑等。 3）在运算法则上，两种也不大相同。属于经典逻辑的形式逻辑和数理逻辑，它们的许多运算法则在非经典逻辑中就不能成立。 4）在逻辑算符上，非经典逻辑具有更多的逻辑算符。非经典逻辑中引用了附加算符（一般叫做模态算符或算子

4、）。 5）在是否单调上，两者也截然有别。经典逻辑是单调的，即已知事实（定理）均为充分可信的，不含随着新事实的出现而使原有事实变为假。这是人的认知的单调性。由于现实生活中的许多事实是在人们来不及完全掌握其前提条件下初步认可的，而当客观情况发生变化或人们对客观情况的认识有了深化时，一些旧的认识就可能被修正以致否定。这就是人的认识的非单调性。引用非单调推理是非经典逻辑与经典逻辑的又一重要区别,4.2 不确定性推理,不确定性推理（reasoning with uncertainty）也是一种建立在非经典逻辑基础上的基于不确定性知识的推理，它从不确定性的初始证据出发，通过运用不确定性知识，推出具有一定程

5、度的不确定性的和合理的或者近乎合理的结论。 不确定推理中所用的知识和证据都具有某种程度的不确定性，这就给推理机的设计与实现增加了复杂性和难度。除了必须解决推理方向、推理方法、控制策略等基本问题以外，一般还需要解决不确定性的表示与量度、不确定性匹配、不确定性的传递算法以及不确定性的合成等重要问题,一、不确定性的表示与量度,结论不确定性的表示 上述由于使用知识和证据具有的不确定性，使得出的结论也具有不确定性。这种结论的不确定性也叫做规则的不确定性，它表示当规则的条件被完全满足时，产生某种结论的不确定程度,二、不确定性的算法 1、不确定性的匹配算法 推理是一个不断运用知识的过程。为了找到所需的知识，

6、需要在这一过程中用知识的前提条件与已知证据进行匹配，只有匹配成功的知识才有可能被应用。 在确定性推理中，知识是否匹配成功是很容易确定的。但在不确定性推理中，由于知识和证据都具有不确定性，而且知识所要求的不确定性程度与证据实际具有的不确定性程度不一定相同，因而就出现了“怎样才算匹配成功”的问题。对于这个问题，目前常用的解决方法是：设计一个用来计算匹配双方相似程度的算法，再指定一个相似的限度，用来衡量匹配双方相似的程度是否落在指定的限度内。若干落在指定的限度内，就称它们是可匹配的，相应的知识可被应用；否则就称它们是不可匹配的，相应的知识不可应用。以上用来计算匹配双方相似程度的算法称为不确定性匹配算

7、法，相似的限度称为阈值,2、不确定性的更新算法 不精确推理的根本目的是根据用户提供的初始证据，通过运用不确定性知识，最终推出不确定性的结论，并推算出结论为确定性的程度。所以不精确推理除了要解决前面提出的问题之外，还需要解决不确定性的更新问题，即在推理过程中如何考虑知识不确定性的动态积累和传递。不确定性的更新算法一般包括如下算法： 1）已知规则前提即证据E的不确定性C(E)和规则的强度f(H,E)，其中H表示假设，试求H的不确定性C(H)。即定义算法g1，使得 C(H)=g1C(E), f(H,E) 2）并行规则算法。根据独立的证据E1和E2，分别求得假设H的不确定性为C1(H)和C2(H)。求

8、出证据E1和E2的组合导致结论H的不确定性C(H)，即定义算法g2，使得 C(H)=g2C1(H), C2(H) 3）证据合取的不确定性算法。根据两个证据E1和E2的不确定性值C(E1)和C(E2)，求出证据E1和E2合取的不确定性，即定义算法g3，使得 C(E1 AND E2)=g3C(E1), C(E2,4）证据析取的不确定性算法。根据两个证据E1和E2的不确定性值C(E1)和C(E2)，求出证据E1和E2析取的不确定性，即定义算法g4，使得 C(E1 OR E2)=g4C(E1), C(E2) 证据合取和证据析取的不确定性算法统称为组合证据的不确定性算法。实际上，规则的前提可以是用AND

9、和OR把多个条件连接起来构成的复合条件。目前，关于组合证据的不确定性的计算已经提出了多种方法，其中用得较多的有如下几种。 1）最大最小法 C(E1 AND E2)=minC(E1),C(E2) C(E1 OR E2)=maxC(E1),C(E2) 2）概率方法 C(E1 AND E2)=C(E1)C(E2) C(E1 OR E2)=C(E1)+C(E2)-C(E1)C(E2) 3）有界方法 C(E1 AND E2)=max0,C(E1)+C(E2)-1 C(E1 OR E2)=min1,C(E1)+C(E2) 上述的每一组公式都有相应的适用范围和使用条件，如概率方法只能在事件之间完全独立时使用

10、,4.3 概率推理,目前用的较多的不精确推理模型有概率推理、可信度方法、证据理论、贝叶斯推理和模糊推理等。 一、概率的基本性质和计算公式 在一定条件下，可能发生也可能不发生的试验结果叫做随机事件，简称事件。随机事件有两种特殊情况，即必然事件和不可能事件。必然事件是在一定条件下每次试验都必定发生的事件；不可能事件是指在一定条件下各次试验都一定不发生的事件。概率论是研究随机现象中数量规律的科学。 随机事件在一次试验中是否发生，固然是无法事先肯定的偶然现象，但当进行多种重复试验时，就可以发现其发生的可能性大小的统计规律性。这一统计规律性表明，事件发生的可能性大小是事件本身所固有的一种客观属性。称这种

11、事件发生的可能性大小为事件的概率。 令A表示一个事件，则其概率记为P(A)。 1、概率具有下列基本性质（6点） 2、概率的部分计算公式如下（4个,二、概率推理方法 设有如下产生式规则： IF E THEN H 则证据（或前提条件）E不确定性的概率为P(E)，概率方法不精确推理的目的就是求出在证据E下结论H发生的概率P(H|E)。 把贝叶斯方法用于不精确推理的一个原始条件是：已知前提E的概率P(E)和H的先验概率P(H)，并已知H成立时E出现的条件概率P(E|H)。如果只使用这一条规则作进一步推理，则使用如下最简形式的贝叶斯公式便可从H的先验概率P(H)推得H的后验概率 若一个证据E支持多个假设

12、H1，H2 ，Hn，即 IF E THEN Hi， i=1，2，n 则可得如下贝叶斯公式,若有多个证据E1，E2 ，Em和多个结论H1，H2 ，Hn ，并且每个证据都以一定程度支持结论，则 这时，只要已知Hi的先验概率P(Hi)即Hi成立时证据E1，E2，Em出现的条件概率P(E1|Hi)，P(E2|Hi)， P(Em|Hi) ，就可以利用上述公式计算出在E1，E2 ，Em出现情况下的Hi条件概率 。 例4.1和例4.2所示,概率推理方法具有较强的理论基础和较好的数学描述。当证据和结论彼此独立时，计算不很复杂。但是，应用这种方法时要求给出结论Hi的先验概率P(Hi)及证据Ej的条件概率P(Ej

13、|Hi) ，而要获得这些概率数据却是相当困难的。此外，贝叶斯公式的应用条件相当严格，即要求各事件彼此独立。如果证据间存在依赖关系，那么就不能直接采用这种方法,4.4 主观贝叶斯方法,一、知识不确定性的表示,再定义概率函数为 即X的几率等于X出现的概率与X不出现的概率之比。 经过推导得贝叶斯公式如下： 由上两式可知：当E为真时，可利用LS将H的先验几率O(H)更新为其后验几率O(H|E)；当E为假时，可利用LN将H的先验几率O(H)更新为其后验几率O(H|E,二、证据不确定性的表示 主观贝叶斯方法中证据的不确定性也是用概率表示的。例如对于初始证据E，用户根据观察S给出P(E|S)，它相当于动态强

14、度。由于难以给出P(E|S)，因而在具体应用系统中往往采用适当的变通方法，如在PROSPECTOR中引进了可信度的概念，让用户在-55之间的11个整数这根据实际情况选一个数作为初始证据的可信度，表示对所提供的证据可以相信的程度。可信度C(E|S)与概率P(E|S)的对应关系如下： C(E|S)=-5，表示在观察S下证据E肯定不存在，即P(E|S)=0。 C(E|S)=0，表示S与E无关，即P(E|S)=P(E)。 C(E|S)=5，表示在观察S下证据E肯定存在，即P(E|S)=1。 C(E|S)为其他数时与P(E|S)的对应关系，可通过对上述三点进行分段线性插值得到，如图4.1所示。 从图4.

15、1可求得,从上两式可见，只要用户对初始证据给出相应的可信度C(E|S)，系统就会把它转化为P(E|S)，也就相当于给出了证据E的概率P(E|S)。 当证据不确定时，要用杜达（Duda）等人证明的下列公式计算后验概率： 1、EH公式,2、CP公式,三、主观贝叶斯方法的推理过程 当采用初始证据进行推理时，通过提问用户得到C(E|S)，通过CP公式就可求得P(H|S)。当采用推理过程中得到的中间结论作为证据进行推理时，通过EH公式可求得P(H|S)。 如果有n条知识都支持同一结论H，而且每条知识的前提条件分别是n个相互独立的证据E1，E2 ，En，而这些证据又分别于观察S1 ， S2 ，Sn相对应，

16、这时首先对每条知识分别求出H的后验几率O(H|Si)，然后按下述公式求出所有观察下H的后验几率： 如例4.3所示,主观贝叶斯方法具有下列优点： 1）主观贝叶斯方法的计算公式大多是在概率论的基础上推导出来的，具有比较坚实的理论基础。 2）规则的LS和LN是由领域专家根据实践经验给出的，避免了大量的数据统计工作。此外，它既用LS指出了证据E对结论H的支持程度，又用LN指出了E对H的必要性程度，比较全面地反映了证据与结论间的因果关系，符合现实世界中某些领域的实际情况，使推出的结论具有比较准确的确定性。 3）主观贝叶斯方法不仅给出了在证据确定情况下由H的先验概率更新为后验概率的方法，而且还给出了在证据

17、不确定情况下更新先验概率为后验概率的方法。由其推理过程还可以看出，它确定实现了不确定性的逐级传递。因此可以说主观贝叶斯方法是一种比较实用而又灵活的不确定性推理方法，它已成功地应用在专家系统中。 缺点是：1）它要求领域专家在给出规则的同时，给出H的先验概率P(H)，这是比较困难的。2）贝叶斯定理中关于事件间独立性的要求使主观贝叶斯方法的应用受到一定限制,4.5 可信度方法,可信度方法是肖特里菲（Shortliffe）等人在确定性理论基础上结合概论等理论提出的一种不精确推理模型，它对许多实际应用都是一个合理而有效的推理模式，因此在专家系统等领域获得较广泛的应用。 一、基于可信度的不确定性表示 根据

18、经验对一个事物或现象为真的（相信）程度称为可信度。在MYCIN专家系统中，不确定性用可信度表示，知识用产生式规则表示。每条规则和每个证据都具有一个可信度,1、知识不确定性的表示 在可信度方法中，不精确推理规则的一般形式为 IF E THEN H (CF(H,E) 其中，CF(H,E)是该规则的可信度，称为可信度因子或规则强度。CF(H,E)的作用域为-1,1。CF(H,E)0则表示该证据增加了结论为真的程度，其CF(H,E)的值越大，结论H越真。若CF(H,E)=1则表示该证据使结论为真。反之，若CF(H,E)0则表示该证据增加了结论为假的程度，其CF(H,E)的值越小，结论H越假。CF(H,

19、E)=-1表示该证据使结论为假。CF(H,E)=0表示该证据E和结论H没有关系,定义4.1 CF(H,E)=MB(H,E)-MD(H,E) 式中，MB(measure belief)为信任增长度，表示因证据E的出现而增加对假设H为真的信任增加程度，即当MB(H,E)0时，有P(H|E)P(H)。MD(measure disbelief)为不信任增长度，表示因证据E的出现对假设H为假的信任增加的程度，即当MD(H,E)0时，有P(H|E)P(H)。 定义4.2 定义4.3,下面讨论MB，MD和CF的性质： 1）0MB(H,E)1 0MD(H,E)1 -1CF(H,E)1 2)若MB(H,E)0，

20、MD(H,E)=0，则CF(H,E)=MB(H,E); 若MD(H,E)0，MB(H,E)=0，则CF(H,E)=-MD(H,E); 称这种性质为MB和MD的互斥性。据互斥性和CF的定义，可得CH(H,E)的如下计算公式,3）若P(H|E)=1，即E为真则H为真时，则MB(H,E)=1，MD(H,E)=0，CF(H,E)=1。 若P(H|E)=0，即E为真则H为假时，则MD(H,E)=1，MB(H,E)=0，CF(H,E)=-1。 若P(H|E)=P(H)，即E对H没有影响时，则MD(H,E)=0，MB(H,E)=0，CF(H,E)=0。 4）对于同一个证据E,若存在n个互不相容的假Hi(i=

21、1,2，n),则 据此，假若发现专家给出的可信度CF(H1，E)=0.6，CF(H2，E)=0.7，即出现H1和H2互不相容，则说明规则的可信度是不合理的，应当进行适当调整。 5）从定义可见，可信度CF与概率P有一定的对于关系，但又有所区别。对于概率有P(H|E)+P(H|E)=1 而对CF，有CF(H|E)+CF(H|E)=0 上式可由可信度的定义推出，它表明如果一个证据对某个假设的成立有利，那么就必然对该假设的不成立不利，而且对两者的影响程度相同,根据计算公式2，可由先验概率P(H)和后验概率P(H|E)求出CF(H,E)。但是，在实际应用中，P(H)和P(H|E)的值是难以获得的，因而C

22、F(H,E)的值要由领域专家直接给出。其原则是：若由于相应证据的出现增加了结论H为真的可信度，则使CF(H,E)0；证据的出现越是支持H为真，就使CF(H,E)的值越大。反之，则使CF(H,E)0；当证据肯定为真时，CF(E)=1；当证据以某种程度为假时，CF(E)0；当证据肯定为假时，CF(E)=-1；当证据一无所知时，CF(E)=0,二、可信度方法的推理算法 1、组合证据的不确定性算法 1）合取证据 当组合证据为多个单一证据的合取时： E=E1 AND E2 AND AND En 若已知CF(E1), CF(E2), CF(En),则有： CF(E)=minCF(E1), CF(E2),C

23、F(En) 即对于多个证据合取的可信度，取其可信度最小的那个证据的CF值作为组合证据的可信度。 2）析取证据 当组合证据是多个单一证据的析取时： E=E1 OR E2 OR OR En 若已知CF(E1), CF(E2), CF(En),则有： CF(E)=maxCF(E1), CF(E2),CF(En) 即对于多个证据析取的可信度，取其可信度最大的那个证据的CF值作为组合证据的可信度,2、不确定性的传递算法 不确定性的传递算法就是根据证据和规则的可信度求其结论的可信度。若已知规则为 IF E THEN H (CF(H,E) 且证据E的可信度为CF(E)，则结论H的可信度CF(H)为 CF(H

24、)=CF(H,E)max0，CF(E) 当CF(E)0，即证据以某种程度为真时，则CF(H)=CF(H,E)CF(E)。若CF(E)=1，即证据为真，则CF(H)=CF(H,E)。这说明，当证据E为真时，结论H的可信度为规则的可信度。当CF(E)0，即证据以某种程度为假，规则不能使用时，则CF(H)=0。可见，在可信度方法的不精确推理中，并没有考虑证据为假对结论H所产生的影响。 3、多个独立证据推出同一假设的合成算法 如果两条不同规则推出同一结论，但可信度各不相同，则可用合成算法计算综合可信度,已知如下两条规则： IF E1 THEN H (CF(H, E1) IF E2 THEN H (CF

25、(H, E2) 其结论H的综合可信度可按如下步骤求得： 1）根据传递算法公式CF(H)分别求出： CF1(H)=CF(H, E1)max0，CF(E1) CF2(H)=CF(H, E2)max0，CF(E2) 2）求出E1和E2对H的综合影响所形成的可信的CF1，2(H),在MYCIN系统的基础上形成的专家系统工具EMYCIN中，对上式做了如下修改： 当组合两个以上的独立证据时，可首先组合其中的两个，再将其组合结果与第三个证据进行组合，如此继续进行组合，直至组合完成为止。 例4.4为基于可信度的不精确推理的推理过程应用,4.6 证据理论,一、证据理论的形式化描述,5、信任函数与似然函数的关系

26、Pl（A）Bel（A） 由于Bel（A）和Pl（A）分别表示A为真的信任程度和A为非假的信任程度，因此可分别称Bel（A） 和Pl（A）为对A信任程度的下限和上限，记为 A（Bel（A）， Pl（A,Bel（A）表示对A为真的信任程度；Bel（A）表示对A即A为假的信任程度；Pl（A）表示对A为非假的信任程度；Pl（A）-Bel（A）表示对A不知道的程度，即既非对A信任又非不信任的那部分。 二、证据理论的不确定性推理模型 从上节中我们知道,1、概率分配函数与类概率函数,2、证据不确定性的表示,3、知识不确定性的表示,4、不确定性的传递算法,三、推理示例（例4.9） 证据理论的主要优点：它只需满

27、足比概率论更弱的公理系统，而且能处理由“不知道”所引起的不确定性。由于D的子集可以是多个元素的集合，因而知识的结论部分可以是更一般的假设，这就便于领域专家从不同的语义层次上表达他们的知识，而不必被限制在由单元素所表示的最明确的层次上。 证据理论的主要缺点：要求D中元素满足互斥条件，这对于实际系统是难以做到的。此外，需要给出的概率分配数太多，计算比较复杂,4.7 模糊推理,基于模糊性知识 理论基础：模糊集（对象模糊）、模糊逻辑 1965年L.A.Zadeh（美国计算机与控制论专家）提出 还不充实与完善 可信度与Bayes、证据理论方法都是基于概率论，事件确切，只是因果关联不确定，随机性的,模糊集

28、的产生,概率论:研究和处理随机问题,把数学应用必然现象 偶然现象 模糊数学:研究和处理模糊性问题,数学应用精确现象 模糊现象 模糊聚类分析表达和处理不分明的类属性质,是一种”软划分,4.7.1模糊集理论与模糊逻辑 1.模糊集与隶属函数 定义4.8 论域U上的一个模糊集合A通过一个隶属函数(Membership Function)刻画: :U0,1 xU 称为 x对A的隶属度( Degree of Membership), =0,则x完全不属于A; =1,则x完全属于A; 0 1,则x属于A的隶属度 当 0,1,模糊集合即为经典集合,4.7.1模糊集理论与模糊逻辑 2.模糊集的表示法 当U =x1, x2, , xn 时 注：只是一种记法 当U 是连续论域时,