人工智能原理.pptx

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章,普通搜索原理,人工智能原理,第1页,知识表示目标是为了便于计算机求解，是为了处理问题。从问题描述（表示）到问题处理，有个求解过程，也就是搜索过程。在这一过程中采取适当搜索技术，包含各种规则、过程和算法等推理技术，力争找到问题解答。,本章讨论一些早期搜索技术或用于处理比较简单问题搜索原理（启发式搜索、宽度优先、深度优先、有序搜索）。,人工智能原理,第2页,4.1,盲目搜索,盲目搜索又叫做无信息搜索。普通只适合用于求解比较简单问题。,人工智能原理,第3页,O,规则库,搜索树：,R1 R2 A.B.,R1:,如,X/12,为整，则,X/6,为整。,R2 R3 R1 R4 C.D.E.,R2:,如,X/20,为整，则,X/10,为整,R3 R4 R2 R3 R4,S,F.G.H I,R3:,如,X/6,为整，则,X/2,为整。,R4,S,R4 R4,S,R4:,如,X/10,为整，则,X/5,为整。,S,S,S,输入数据库：,N/12,，,N/20 S=success,判断是否,N/5,人工智能原理,第4页,这是一个产生式系统例子。,节点用 表示。每一个节点对应于一个状态，反应当初数据库情况。如节点,O,：,N/12,，,N/20,；节点,A,：,N/12,，,N/20,，,N/6,；节点,D,：,N/12,，,N/20,，,N/6,，,N/2,。每条连线对应于一个操作符。,棋局对应走步，这里对应于一条产生式规则。,人工智能原理,第5页,该搜索树给出了全部可能求解证实渠道。抽象地描述：给定初始节点和目标节点，求图中一条合理路径（所谓合理有指只要找到就行；有要求搜索步骤最少或路径最短等等）。,就这个例子，我们看一下宽度优先搜索、深度优先搜索是怎样进行。当然，并不是全部问题都能够画出图示搜索树（深度不深、每条支路都有解且支路不多）。,人工智能原理,第6页,4.1.1,宽度优先搜索,假如搜索是以靠近起始节点程度依次扩展节点，那么这种搜索就叫做宽度优先搜索。,也就是说，这种搜索是逐层进行。在对下一层任一节点进行搜索之前，必须搜索完本层全部节点。,宽度优先搜索算法（流程框图）以下：,（,1,）把起始节点放到,OPEN,表中（假如该起始节点为目标节点，则求得一个解答）。,OPEN CLOSED,O,人工智能原理,第7页,（,2,）假如,OPEN,表是个空表，则没有解，失溃退出。不然继续。,（,3,）把第一个节点从,OPEN,表中移出，并把它放入,CLOSED,扩展节点表中。,（,4,）扩展该节点。假如没有后继节点，则转向上述第（,2,）步。,（,5,）把该节点全部后继节点放到,OPEN,表末端，并提供这些后继节点返回该节点指针。,（,6,）假如该节点任一个后继节点是个目标节点，则找到一个解答，成功退出；不然转向（,2,）。,人工智能原理,第8页,人工智能原理,第9页,O,规则库,搜索树：,R1 R2,A.B.,R1:,如,X/12,为整，则,X/6,为整。,R2 R3 R1 R4,C.D.E.,R2:,如,X/20,为整，则,X/10,为整,R3 R4 R2 R3 R4,S,F.G.H I,R3:,如,X/6,为整，则,X/2,为整。,R4,S,R4 R4,S,R4:,如,X/10,为整，则,X/5,为整。,S,S,S,输入数据库：,N/12,，,N/20 S=success,判断是否,N/5,人工智能原理,第10页,O,AB,O,OA,BCD,OAB,CDES,OPEN,表,CLOSED,表,O B S,R2 R4(,回溯,),宽度优先搜索方法能够确保在搜索树中找到一条通向目标节点最短路径。,注：,1,、在,OPEN,表中已经有节点，新扩展相关节点不放,OPEN,表中。,2,、,CLOSED,表中所放节点位置前后不主要。,人工智能原理,第11页,人工智能原理,第12页,6,4,人工智能原理,第13页,4.1.2,深度优先搜索,另一个盲目（无信息）搜索叫做深度优先搜索。,在深度优先搜索中，我们首先扩展最新产生（即最深）节点。,节点深度定义以下：,(1),起始节点（即根节点）深度为,0,。,(2),任何其它节点深度等于其父辈节点深度加,1,。,首先、扩展最深节点结果使得搜索沿着状态空间某条单一路径从起始节点向下进行下去；只有当搜索抵达一个没有后代状态时，它才考虑另一条替换路径。,人工智能原理,第14页,对于许多问题，其状态空间搜索树深度可能为无限深，或者可能最少要比某个可接收解答序列已知深度上限还要深。为了防止考虑太长路径（预防搜索过程沿着无益路径扩展下去），往往给出一个节点扩展最大深度,深度界限。任何节点假如到达了深度界限，那么都将它们作为没有后继节点处理。,和宽度优先法不一样之处于于：扩展节点，其后继节点放入,OPEN,表前端,人工智能原理,第15页,O,规则库,搜索树：,R1 R2,A.B.,R1:,如,X/12,为整，则,X/6,为整。,R2 R3 R1 R4,C.D.E.,R2:,如,X/20,为整，则,X/10,为整,R3 R4 R2 R3 R4,S,F.G.H I,R3:,如,X/6,为整，则,X/2,为整。,R4,S,R4 R4,S,R4:,如,X/10,为整，则,X/5,为整。,S,S,S,输入数据库：,N/12,，,N/20 S=success,判断是否,N/5,人工智能原理,第16页,O,AB,O,OA,CDB,OAC,FSDB,OPEN,表,CLOSED,表,O A C S,R1 R2 R4(,回溯,),三步操作，不是最短。如知道最短,2,步，深度界限定为,2,，必定有解且可找到最短路径。但有些情况下（多数），不限定深度不好。,人工智能原理,第17页,4.2,启发式搜索,盲目搜索效率低，花费过多计算空间与时间。假如能够找到一个用于排列待扩展节点次序，即选择最有希望节点加以扩展，那么，搜索效率将会大大提升。,“启发”（,heuristic,）是关于发觉和创造规则及方法研究。在状态空间搜索中，启发式被定义为一系列规则，它从状态空间中选择最有希望抵达问题解路径。,人工智能原理,第18页,人工智能求解者在两种基本情况下利用启发式策略：,(1),一个问题因为问题陈说和数据获取方面固有含糊性可能使它没有一个确定解。,医疗诊疗即是一例：所给出一系列症状可能有多个原因，医生利用启发式搜索来选择最有可能论断，并依此产生治疗计划。,视觉问题又是一例。看到景物经常是含糊。各方面原因造成。河和桥、马路。海面上船、鲸鱼或潜水艇。视觉系统可利用启发式策略选择一给定景像最有可能解释。,人工智能原理,第19页,(2),一个问题可能有确定解，不过求解过程中计算机代价令人难以接收。,在很多问题上（如象棋）中，状态空间增加尤其快，可能状态数伴随搜索深度呈指数级增加、分解。在这种情况下，用盲目搜索方法就不行了（不象前面所举简单例子）。给定棋局，可能下一状态、对手可能应对步骤太多。这时需用启发式策略经过指导搜索向最有希望方向前进，以降低复杂性。经过删除一些状态及其延伸，以消除组合爆炸，并得到令人能接收解。,人工智能原理,第20页,然而，和创造创造全部规则一样，启发式策略也是极易犯错。在处理问题过程中，启发仅仅是下一步将要采取办法一个猜测。经常依据经验和直觉来判断。因为只利用有限信息，一个启发式搜索可能得到一个次最正确解，也有可能一无所获。,上述两种情况第一个多出现在教授系统中，第二种情况多出现在博奕和定理证实中。,下面讨论主要限制在第二种情况。在这种情况下，普通都是：初始状态、算符和目标状态定义都是完全确定，然后决定一个搜索空间。进行搜索时，普通需要一些相关详细领域特征信息。我们把这种信息叫做启发信息，并把,利用启发信息搜索方法叫做启发性搜索方法,。,人工智能原理,第21页,在本节中，我们介绍一个有序搜索（也称为最好优先搜索）方法。这种搜索总是选择“最有希望”节点作为下一个被扩展节点。,何为“最有希望”，取决于你所选,估价函数,f(n),（性能指标）。有序搜索算法中，一个节点希望程度越大，其,估价函数,值就越小。被选为扩展节点，是估价函数最小节点。,给定一个问题后，依据问题特征和解特征，能够有各种方法定义估价函数，用不一样估价函数指导搜索，其效果能够相差很远。假如选得不好，那么有序搜索就可能失去一个最好解，甚至全部解。,人工智能原理,第22页,人工智能原理,第23页,人工智能原理,第24页,对于八数码难题，我们采取了简单估价函数,f(n)=d(n)+w(n),其中：,d(n),是搜索树中节点,n,深度,w(n),用来计算对应于节点,n,数据库中错放棋子个数。,也就是说，该估价函数考虑了两个因数。第一个因数考虑希望节点距根节点（起始节点）越近越好，第二个因数考虑希望节点距目标节点看上去越近越好。,考虑八数码难题，其搜索过程见图。,人工智能原理,第25页,5,人工智能原理,第26页,第五章,高级求解技术,人工智能原理,第27页,上一章我们介绍了几个基本（早期）搜索技术，如宽度优先、深度优先（盲目搜索）、有序搜索（启发式搜索、最好优先）。,对于许多比较复杂系统和问题，用这些方法就极难甚至无法使问题取得处理。这时，就需要应用一些更先进推理求解技术。,本章讨论规则演绎系统、不确定性推理。,人工智能原理,第28页,5.1,规则演绎系统,我们通常习惯用,if then,规则形式表示知识求解问题。基于规则问题求解系统利用下述规则来建立，,IF-THEN,即：,IF IF1,IF2,THEN THEN1,THEN2,其中：,IF,部分可能由几个,IF,组成，而,THEN,部分可能由一个或一个以上,THEN,组成。,人工智能原理,第29页,通常称每个,IF,部分为前项（条件、断言），,THEN,部分为后项（新断言）。这种基于规则系统叫做规则演绎系统。,有时，,THEN,部分用于要求动作，这时称这种基于规则系统为反应式系统或产生式系统。,人工智能原理,第30页,5.1.1,规则正向演绎系统,(,事实、规则、目标,),在基于规则系统中，不论是规则演绎系统或规则产生式系统，都有两种推理方式，即正向推理和逆向推理。从,IF,部分向,THEN,部分推理过程，叫做正向推理。也就是说，正向推理是从事实或情况向目标或动作进行操作。反之，对于从,THEN,部分向,IF,部分推理过程，叫做逆向推理。逆向推理是从目标或动作向事实或情况进行操作。,1.,事实表示式与或形变换,通惯用谓词演算公式来表示事实（用作事实表示式）。如事实表示式：,(U)(V)Q(V,U)(R(V)P(V)S(U,V),通常还存在蕴含关系。,人工智能原理,第31页,在基于规则正向演绎系统中，所要做第一步是将其变换（或叫化成）非蕴含形式与或形。要把一个公式化成与或形，可利用以下恒等式或方法：,(1)W1=W2=W1W2,（利用恒等式，去蕴含符号），在事实表示式中，极少有,=,符号出现,(2),用德,.,摩根公式（定律）把否定符号移进括号内，直到每个否定符号都只含一个谓词为止。,人工智能原理,第32页,(3),对所得表示式进行,skelem,化，消除存在性量词。,X Y mother(Y,X),X mother(f(X),X),(4),删去全称量词，而余下变量都被认为含有全称量化作用。,Q(V,f(V)(R(V)P(V)S(f(V),V),人工智能原理,第33页,2.,事实表示式与或图表示,根节点,Q(V,f(V)(R(V)P(V)S(f(V),V),与、合取,Q(V,f(V)(R(V)P(V)S(f(V),V),或、析取,R(V)P(V)S(f(V),V),叶节点,文字,R(V)P(V),人工智能原理,第34页,通常，把事实表示式与或图表示倒过来画，即把根节点画在最下面，而把其后继节点往上画。,3.,与或图,F,规则变换,我们把允许用作规则公式类型限制为以下形式：,L=W,式中，,L,是单文字；,W,是与或形表示式,人工智能原理,第35页,比如：事实表示式：,PS(TU),规则：,S=(XY)Z,PS(TU),P,析取,S(TU),S,合取,TU,S T U,Z XY,应用一条,F,规则,L=W,X Y,得到与或图,人工智能原理,第36页,4.,作为终止条件目标公式,应用,F,规则目标在于从某个事实公式和某个规则集出发来证实某个目标公式。在正向推理系统中，这种目标表示式只限于可证实表示式，尤其是可证实,文字析取形,目标公式表示式。,结论是：当正向演绎系统产生一个含有目标节点作为终止解图时，此系统就成功地终止。,(,目标可由叶节点,析取,得到,),对上图，若目标为：,PZX,或,PZY,时，就算证出。,人工智能原理,第37页,例：事实,AB,规则,A=CD,，,B=EG,目标,CG,（,CE,，,DG,，,DE,）,AB,消解否证法,A B AC C G BG,A B AB A B,C D E G B,C G,空,把规则化为子句形式：,AC,，,AD,，,BE,，,BG,目标否定：,CG,，其子句形式为,C,，,G,人工智能原理,第38页,5.1.2,规则逆向演绎系统,基于规则逆向演绎系统，其操作过程与正向演绎系统相反，即为从目标到事实操作过程，从,then,到,if,推理过程。,1.,目标表示式与或形式,逆向演绎系统能够处理任意形式目标表示式。首先，采取与变换事实表示式一样过程，把目标表示式化成与或形、即消去蕴含符号，把否定符号移进括号内，消去存在性量词（,skelem,化）等。,例：目标表示式,Y XP(X)=Q(X,Y)R(X)S(Y),化成与或形,P(f(Y)Q(f(Y),Y)R(f(Y)S(Y),人工智能原理,第39页,与事实表示式与或图不一样是，对于目标表示式，与或图中连接符用来区分合取关系子表示式。,P(f(Y)Q(f(Y),Y)R(f(Y)S(Y),或、析取,P(f(Y)Q(f(Y),Y)R(f(Y)S(Y),与、合取,Q(f(Y),Y)R(f(Y)S(Y),R(f(Y)S(Y),该目标公式子句集为：,P(f(Y),，,Q(f(Y),Y)R(f(Y),，,Q(f(Y),Y)S(Y),可从终止在叶节点上解图集读出。目标子句是文字,合取,，目标表示式就是这些子句,析取,。,人工智能原理,第40页,2.,与或图,B,规则变换,现在把这些,B,规则限制为：,W=L,W,为任一与或形表示式，,L,为文字。,W=(L1L2),能够化为两个规则：,W=L1,和,()W=L2,3.,作为终止条件事实节点一致解图,逆向系统中事实表示式均限制为文字合取形。,逆向系统成功终止条件是与或图包含有某个终止在事实节点上一致解图,。,下面讨论一个简单例子，看看基于规则逆向演绎系统是怎样工作。,人工智能原理,第41页,例：事实,F1,：狗（,FD,）；,F2,：叫（,FD,）；,F3,：摇尾（,FD,）；,F4,：猫（,MT,）,规则：,R1,：摇尾（,X,）狗（,X,）,=,温顺（,X,）,R2:,温顺（,X,）叫（,X,）,=,可怕（,X,）,问题：是否存在这么一只猫和一只狗，使得这只猫不怕这条狗。,用目标表示式表示为：,X Y,猫（,Y,）狗（,X,）可怕,(Y,，,X),人工智能原理,第42页,猫（,Y,）狗（,X,）可怕,(Y,，,X),猫（,Y,）狗（,X,）可怕,(Y,，,X),MT/Y FD/X,猫（,MT,）,狗（,FD,）,可怕,(Y,，,X),R2,叫（,X,）温顺,(X),FD/X,叫（,FD,）,温顺,(X),逆向系统一致解图,R1,红色节点为事实节点 摇尾,(X),狗（,X,）,FD/X FD/X,摇尾,(FD),狗（,FD,）,终止在事实节点前置换为,MT/Y,，,FD/X,。把它应用到目标表示式，就得到了该问题解答。,人工智能原理,第43页,5.1.3,规则双向演绎系统,在上两节中，我们所讨论基于规则正向演绎系统和逆向演绎系统都含有不足（正向,L=W,，逆向,W=L,）。,我们希望能够组成一个组合系统，使它含有正向和逆向两系统优点，以克服各自缺点（不足）。这个系统就是我们所要研究规则双向演绎系统。,不停用,F,规则和,B,规则对与或图进行扩展，进行适当置换与合一。一个简单终止条件是某个判定与或图根节点是否为可解过程直接归纳。这个终止条件是建立在事实节点和目标节点一个叫做,CANCEL,对称关系基础上。,人工智能原理,第44页,5.2,不确定性推理,对于许多比较复杂人工智能系统，往往含有复杂性、不完全性、含糊性和不确定性。当采取产生式系统或教授系统结构时，要求设计者建立某种不确定性计算和推理过程。有两种不确定性，即关于证据不确定性和关于规则不确定性。,人工智能原理,第45页,5.2.1,关于证据不确定性,观察事物时，所看到事实经常含有某种不确定性。比如，当你观察某种动物颜色时，你可能说这种动物颜色看起来是白色，但也可能是灰色。这就是说，你观察带有某种程度不确定性，造成证据不确定性。,普通，经过对事实赋于一个介于,0,和,1,之间系数来表示事实不确定性。,1,代表完全确定，,0,代表完全不确定。这个系数被称为可信度。当规则含有一个以上条件时，就需要依据各条件可信度求得总条件部分可信度。已经有方法有两类：,人工智能原理,第46页,1.,以含糊集理论为基础方法,按这种方法，,把全部条件中最小可信度作为总条件可信度,，看起来好像是符合含糊集理论。,C,T,=minC,T,0.9,0.7 0.7,1.0,有时把这种处理可信度方法，称之为以含糊集理论为基础方法。,在,MYCIN,系统中主要采取这种方法。这种方法类似于当把几根绳子连接起来使用时，总绳子强度与强度最差绳子强度相同。,人工智能原理,第47页,2.,以概率为基础方法,总证据可信度为各证据可信度乘积,。,C,T,=C,T1,*C,Tn,0.9,0.7 0.63,1.0,探矿教授系统,PROSPECTOR,就采取这种方法。,人工智能原理,第48页,5.2.2,关于规则和结论不确定性,规则不确定性，它表示,当规则条件被完全满足时，产生某种结论不确定程度,。它也是以赋予规则在,0,和,1,之间系数方法来表示。,比如：规则：假如开启器发出刺耳噪声,那么这个开启器坏可能性是,0.8,该规则表示，假如事实完全必定（,1.0,），那么结论可信度为,0.8,。假如规则条件部分不完全确定，即条件可信度不为,1,，此时求结论可信度简单方法：,人工智能原理,第49页,结论可信度为条件可信度与规则可信度乘积,C,J,=C,G,*C,T,0.5 0.8 0.4,C,out,规则不确定性,5.2.3,多个规则支持同一结论不确定性,当多个规则支持同一结论时，怎样依据这些规则结论可信度求得该结论可信度呢，,一样有两种方法,。,规则：假如 该动物有毛发 那么 它是哺乳动物,规则：假如 该动物能产乳 那么 它是哺乳动物,人工智能原理,第50页,1.,基于含糊集理论方法,取支持该结论各规则结论可信度最大值作为结论可信度,。,（规则,1,结论可信度,C,J1,为,0.9,，规则,2,结论可信度,C,J2,为,0.25,，则总结论可信度,C,J,为,0.9,）,C,J,=maxC,Ji,i,人工智能原理,第51页,2.,基于概率论方法,定义：规则,i,结论可信度为,C,Ji,，可信性百分比为,R,Ji,。,一组规则支持结论可信度，可用以下方法求得：,（,1,）首先把各规则结论可信度,C,Ji,转换成可信性百分比,R,Ji,。可信性百分比,R,Ji,和可信度,C,Ji,之间关系为：,R,Ji,=C,Ji,/(1-C,Ji,),，,C,Ji,=R,Ji,/(1+R,Ji,),（,2,）把各规则结论可信性百分比,R,Ji,相乘以求得这些规则所支持结论可信性百分比。,R,J,=R,J1,*R,J2,*R,Jn,（,3,）按公式求结论可信度,C,J,:C,J,=R,J,/(1+R,J,),人工智能原理,第52页,当条件不确定性、规则不确定性、多个规则支持同一结论时，可按次序依次处理。,MYCIN,医疗教授系统采取反向推理和深度优先搜索方法，用到不确定性推理方法，它用于诊疗和治疗感染性疾病。步骤,4,个：,1.,确定患者有没有需要治疗细菌性感染。,2.,确定可能引发感染有机体。,3.,确定对引发感染有机体有抑制作用药品。,4.,选择一个或几个对治疗患者感染是最适当药品。,前两步诊疗，后两步治疗。,有咨询模块、动态数据库（推理统计）、解释模块、知识库等。,人工智能原理,第53页,