不确定性推理之证据理论课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,青岛理工大学 通信学院,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,青岛理工大学 通信学院,*,人工智能,Artificial Intelligence,程雷雷,不确定性推理,不确定性,：,由于客观世界的复杂，多变性和人类自身认识的局限，主观性，致使我们所获得、所处理的信息和知识中，往往含有不肯定、不准确、不完全甚至不一致的成分,2024/9/13,青岛理工大学 通信学院,2,不确定性推理的概念,不确定性推理泛指除精准推理以外的其他各种推理问题，包括不完备、不精准知识的推理，模糊知识的推理，非单调推理等。,不确定性推理实际上是一种从不确定的初始证据出发，通过运用不确定性知识，最终推出具有一定不确定性但却又是合理或基本合理的结论的思维过程。,2024/9/13,青岛理工大学 通信学院,3,不确定性推理方法分类,2024/9/13,青岛理工大学 通信学院,4,不确定性推理,数值方法,非数值方法,框架推理,语义网络推理,常识推理,模糊推理,基于概率的方法,主观,Bayes,方法,证据理论,可信度方法,证据理论,1,形式化描述,2,不确定性推理模型,2024/9/13,青岛理工大学 通信学院,6,1,、,证据理论,概述,由,Dempster,首先提出，并由他的学生,Shafer,发展起来，也称,D-S,理论。在专家系统的不精准推理中已得到广泛的应用。,2024/9/13,青岛理工大学 通信学院,7,1.1,规则正向演绎系统,定义,正向规则演绎系统是从事实到目标进行操作的，即从状况条件到动作进行推理的，也就是从,if,到,then,的方向进行推理的。,求解过程,事实表达式的与或形变换,在基于规则的正向演绎系统中,，,我们把事实表示为非蕴涵形式的与或形，作为系统的总数据库,。,2024/9/13,青岛理工大学 通信学院,8,1.,事实表达式的与或形变换,例如：,(,u) (,v),Q(v,u),(R(v) P(v) S(A,v),表示为非蕴涵形式的与或形：,A/u,Q(,v,A,),R(v),P(v),S(A,v),1.1,规则正向演绎系统,2024/9/13,青岛理工大学 通信学院,9,2.,事实表达式的与或图表示,Q(v,A)R(v)P(v)S(A,v),Q(v,A),R(v)P(v)S(A,v),R(v)P(v),S(A,v),R(v),P(v),图,2.8,一个事实表达式的与或树表示,子句集：,Q(,v,A),R(v)S(A,v),P(v)S(A,v),换名：,Q(w,A),R(v)S(A,v),P(,x,)S(A,x,),2024/9/13,青岛理工大学 通信学院,10,与或图的,F,规则变换,这些规则是建立在某个问题辖域中普通陈述性知识的蕴涵公式基础上的。我们把允许用作规则的公式类型限制为下列形式：,L,W,式中：,L,是单文字；,W,为,与或形的唯一公式,。,下面的证明限定：目标是可以证明的，目标是析取关系,1.1,规则正向演绎系统,2024/9/13,青岛理工大学 通信学院,11,例如：,(,x,),(,y,)(,z,)P(x,y,z),(,u,) Q(x,u),1),暂时消去蕴涵符号：,(,x,),(,y,)(,z,)P(x,y,z),(,u,) Q(x,u),2),减小否定符号的辖域：,(,x,),(,y,)(,z,),P(x,y,z),(,u,) Q(x,u),3),进行,Skolem,标准化：,(,x,) (,y,) P(x,y,f(x,y),),(,u,) Q(x,u),4),换名并消去全称量词：, P(x,y,f(x,y),Q(x,u),5),恢复蕴涵式：,P(x,y,f(x,y),Q(x,u),2024/9/13,青岛理工大学 通信学院,12,(PQ)R,S(TU),PQ,(PQ)R,TU,P,Q,R,S(TU),S,T,U,图,2.9,不含变量的与或图,2024/9/13,青岛理工大学 通信学院,13,(PQ)R,S(TU),PQ,(PQ)R,TU,P,Q,R,S(TU),S,T,U,图,2.10,应用,L,W,规则得到的与或图,S,XY,Z,X,Y,P Q X Z,P Q Y Z,R X Z,R Y Z,2024/9/13,青岛理工大学 通信学院,14,(AB),事实,: AB,规则,:A,CD, B,EG,目标,: CG(,析取,),C,D,C,A,A,B,B,E,G,G,AC,C,G,BG,AB,A,B,B,NIL,结论：以目标节点作为终止解图时，系统成功终止。,2024/9/13,青岛理工大学 通信学院,15,1,.2,规则逆向演绎系统,定义,逆向规则演绎系统是从,then,向,if,进行推理的，即从目标或动作向事实或状况条件进行推理的。,求解过程,目标表达式的与或形式,与或图的,B,规则变换,W,L,L,是单文字；,W,为,与或形的公式,作为终止条件的事实节点的一致解图,2024/9/13,青岛理工大学 通信学院,16,1,.2,规则逆向演绎系统,例如：,(,y,)(,x,),P(x),Q(x,y) ,P(x) S(y),化成与或形：,P(f(y),Q(f(y),y) ,P(f(y) S(y),P(f(y) Q(f(y),y) P(f(y)S(y),Q(f(y),y) P(f(y) S(y),P(f(y),P(f(y)S(y),Q(f(y),y),S(y),P(f(y),目标子句是文字的,合取,：,P(f(z),Q(f(y),y) P(f(y),Q(f(x),x) S(x),2024/9/13,青岛理工大学 通信学院,17,例：,F1: DOG(FIDO),；,狗的名字叫,Fido,F2: BARKS(FIDO),；,Fido,不叫的,F3: WAGS-TAIL (FIDO),；,Fido,摇尾巴,F4: MEOWS(MYRTLE),；,猫咪的名字叫,Myrtle,R1: WAGS-TAIL(x1)DOG(x1),FRIENDLY(x1),；,摇尾巴的狗是温顺的狗,R2: ,FRIENDLY(x2),BARKS(x2),AFRAID(y2,x2),；,温顺而不叫的东西是不值得害怕的,R3: DOG(x3),ANIMAL(x3),；,狗是动物,R4,: CAT(x4),ANIMAL(x4),；,猫是动物,R5,: MEOWS(x5),CAT(x5),；,猫咪是猫,问题：,是否,存在,一只猫和一条狗，使得这只猫不怕这条狗（,找到,一只不怕狗的猫）？,(,x,) (,y,)CAT(x)DOG(y),AFRAID(x,y),2024/9/13,青岛理工大学 通信学院,18,CAT(x)DOG(y),AFRAID(x,y),CAT(x),DOG(y),AFRAID(x,y),WAGS-TAIL (FIDO),DOG(FIDO),DOG(y),AFRAID(y2,x2),FRIENDLY(y),AFRAID(x,y),WAGS-TAIL (y),FIDO/y,FIDO/y,BARKS(FIDO),MEOWS(MYRTLE),y/x1,FIDO/y,MYRTLE/x,R1,DOG(FIDO),FIDO/y,BARKS,(y),x/y2,y/x2,R2,MEOWS,(x),CAT(x5),x/x5,R5,2024/9/13,青岛理工大学 通信学院,19,正向和逆向组合系统是建立在两个系统相结合的基础上的。此组合系统的总数据库由表示目标和表示事实的两个与或图结构组成。这些与或图结构分别用正向系统的,F,规则和逆向系统的,B,规则来修正。,1,.3,规则双向演绎系统,2024/9/13,青岛理工大学 通信学院,20,2,产生式系统,定义,：,用来描述若干个不同的以一个基本概念为基础的系统。这个基本概念就是产生式规则或产生式条件和操作对的概念,。,实质：,在产生式系统中，论域的知识分为两部分：用事实表示静态知识，如事物、事件和它们之间的关系；用产生式规则表示推理过程和行为。由于这类系统的知识库主要用于存储规则，因此又把此类系统称为基于规则的系统。,2024/9/13,青岛理工大学 通信学院,21,2.1,产生式系统的组成,控制策略,图,3.22,产生式系统的主要组成,总数据库,产生式规则,一个产生式系统由下列,3,部分组成：,一个总数据库,(global database),，它含有与具体任务有关的信息。,一套规则,，它对数据库进行操作运算。每条规则由左右两部分组成，左部鉴别规则的适用性或先决条件，右部描述规则应用时所完成的动作。应用规则来改变数据库。,一个控制策略,，它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。,2024/9/13,青岛理工大学 通信学院,22,选择规则到,执行操作的步骤,1,匹配,把当前数据库与规则的条件部分相匹配。,2,冲突,当有一条以上规则的条件部分和当前数据库相匹配时，就需要决定首先使用哪一条规则，这称为冲突解决。,3,操作,操作就是执行规则的操作部分。,2024/9/13,青岛理工大学 通信学院,23,2,.2,产生式系统的推理,正向推理：,从一组表示事实的谓词或命题出发，使用一组产生式规则，用以证明该谓词公式或命题是否成立。,逆向推理：,从表示目标的谓词或命题出发，使用一组产生式规则证明事实谓词或命题成立，即首先提出一批假设目标，然后逐一验证这些假设。,双向推理：,双向推理的推理策略是同时从目标向事实推理和从事实向目标推理，并在推理过程中的某个步骤，实现事实与目标的匹配。,3.非单调推理,2024/9/13,青岛理工大学 通信学院,24,3.1,非单调推理的概念,单调推理：,S1,：已有的知识集,S2,：增加新知识后的知识集,采用经典逻辑的演绎推理，则有下式成立：,显然，在这种推理中，推出的结论是随着知识的,增加而单调增多的。这样的推理就是单调推理。,2024/9/13,青岛理工大学 通信学院,25,非单调推理：假设已有的知识集,S1,，,当知识由,S,1,增加至,S,2,时，尽管有 ，则不一定有,这样的推理称为非单调推理。,人类的思维推理在很多情况下是非单调的。,非单调推理产生的一个主要原因是，在知识不完全的,情况下，为了使推理得以进行下去，而采用了某些假,设。,3.,非单调推理,关于非典调推理的代表性理论,2024/9/13,青岛理工大学 通信学院,26,R.Reiter,等人提出的缺省理论,(Default Theories),。,J.McCarthy,等人提出的界限理论,(Circumscription Theories),。,D.McDermott,与,J.Doyle,提出的非单调逻辑,(Non-monotonic Logic),。,此外，还建立了一些非单调推理系统及基于非单调逻辑的知识表示语言，如多伊尔设计的正确性维持系统,TMS(Truth Maintenance System),，罗伯特等建立的知识表示语言,FRL,等,3.2 缺省理论,缺省理论又称为缺省逻辑，它是在知识不完全的情况下使推理得以继续下去的一种非单调推理的理论。,基本思想：在知识不完全的情况下，为了使推理得以进行下去，假设某些命题成立，并在此基础上进行推理。 作出,“,假设,”,的原则是：如果没有足够的证据能证明某个命题不成立，则认为该命题是成立的。,这样的推理又称为默认推理。,2024/9/13,青岛理工大学 通信学院,27,赖特的缺省理论,1,）缺省理论的核心是缺省规则，形式如下：,其中，,A(x),表示缺省规则的先决条件，,B,i,(x),表示默,认条件，,C(x),表示结论。,M,称为模态算子，表示,“,假,定,是相容的,”,，即其否定不可证明。,（,2,）上述缺省规则表示：如果先决条件,A(x),成立，,而且假定默认条件,B,i,(x),相容，则可推出结论,C(x),成,立。例如：,2024/9/13,青岛理工大学 通信学院,28,缺省规则的分类,缺省规则按其形式可分为规范缺省、半规范缺省及不规范缺省三类。,规范缺省,如果默认条件为,B(x),，且,B(x)=C(x),，则称为规范的缺省规则,缺省规则通常表示,“,大部分,一般,.,都,”,等意思,。,一般来说，鸟都会飞,2024/9/13,青岛理工大学 通信学院,29,半规范缺省,如果默认条件为,B(x),，且有,B(x)=C(x),D(x),则称其为半规范缺省规则,可表示,“,除了,D(x),以外，其余的一般都成立,”,不规范缺省,所有不属于前两类的缺省规则都称为不规范缺省规则。,2024/9/13,青岛理工大学 通信学院,30,缺省逻辑的特点,（,1,）它是非单调的。,（,2,）在新知识加入的时候，要检查与已有知识的相容性。,2024/9/13,青岛理工大学 通信学院,31,完,谢谢,2024/9/13,青岛理工大学 通信学院,32,