人工智能基础0ppt课件

.,目录,第一章绪论第二章搜索技术第三章知识表示第四章推理技术第五章机器学习第六章计算智能第七章数据挖掘第八章智能体技术,.,推理的基本概念消解原理规则演绎系统产生式系统定性推理不确定性推理非单调推理,.,4.1推理的基本概念,4.1.1推理的定义从初始证据出发，按某种策略不断应用知识库中的已知知识，逐步推出结论的过程称为推理。在人工智能系统中，推理是由程序实现的，称为推理机。已知事实和知识是构成推理的两个基本要素。事实又称为证据，用以指出推理的出发点及推理时应该使用的知识。知识是使推理得以向前推进，并逐步达到最终目标的依据。,.,4.1推理的基本概念,4.1.2推理方式及其分类（1）按推出结论的途径来划分，推理可分为：演绎推理（deductiveresoning）：是从全称判断推导出单称判断的过程，即由一般性知识推出适合某一具体情况的结论。一般到个别。归纳推理（inductiveresoning）：是从足够多的事例中归纳出一般性结论的推理过程。个别到一般。默认推理（defaultresoning）：是在知识不完全的情况下假设某些条件已经具备所进行的推理。,.,4.0推理的基本概念,4.0.2推理方式及其分类（2）按推理时所用的知识的确定性来划分，推理可分为：确定性推理：是指推理时所用的知识与证据都是确定的，推出的结论也是确定的，其真值或者为真或者为假，没有第三种情况出现。不确定性推理：是指推理时所用的知识与证据不都是确定的，推出的结论也是不确定的。,.,4.1推理的基本概念,4.1.2推理方式及其分类（3）按推理过程中推出的结论是否越来越接近最终目标来划分，推理可分为：单调推理：是指在推理过程中随着推理向前推进及新知识的加入，推出的结论越来越接近最终目标。非单调推理：是指在推理过程中由于新知识的加入，不仅没有加强已推出的结论，反而要否定它，使推理退回到前面的某一步，然后重新开始。,.,4.1推理的基本概念,4.1.2推理方式及其分类（4）按推理中是否运用与推理有关的启发性知识来划分，推理可分为：启发性推理：是指在推理过程中运用与推理有关的启发性知识。非启发性推理：是指在推理过程中未运用与推理有关的启发性知识。,.,4.1推理的基本概念,4.1.3推理的方向（1）正向推理是以事实作为出发点的一种推理。基本思想：从用户提供的初始已知事实出发，在知识库KB中找出当前可适用的知识，构成可适用知识集KS，然后按某种冲突消解策略从KS中选出一条知识进行推理，并将推出的新事实加入到数据库中作为下一步推理的已知事实，此后再在KB中选取可适用的知识进行推理，如此重复这一过程，直到求得了问题的解或者知识库中再无可适用的知识为止。,.,4.1推理的基本概念,4.1.3推理的方向（2）逆向推理是以某个假设目标为出发点的一种推理。基本思想：首先选择一个假设目标，然后寻找支持该假设的证据，若需的证据都能找到，则说明原假设是成立的；若无论如何都找不到所需的证据，则说明原假设不成立，为此需要另作新的假设。,.,4.1推理的基本概念,4.1.3推理的方向（3）混合推理正向推理具有盲目、效率低等缺点，推理过程中可能会推出许多与问题无关的子目标。逆向推理中，若提出的假设目标不符合实际，也会降低系统效率。可以把正向推理与逆向推理结合起来，使其各自发挥自己的优势，取长补短。这种既有正向推理又有逆向推理称为混合推理。,.,4.1推理的基本概念,4.1.4冲突消解策略系统将当前已知事实与KB中知识匹配的三种情况：（1）已知事实恰好只与KB中的一个知识匹配成功。（2）已知事实不能与KB中的任何知识匹配成功。（3）已知事实可与KB中的多个知识匹配成功；或者多个（组）事实都可与KB中的某一个知识匹配成功；或者多个（组）事实都可与KB中的多个知识匹配成功；第3种情况称为发生了冲突。,.,4.1推理的基本概念,4.1.4冲突消解策略消解冲突的基本思想：对知识进行排序：（1）按针对性排序：优先选择针对性强的知识（规则），即要求条件多的规则。（2）按已知事实的新鲜性排序：后生成的事实具有较大的新鲜性。（3）按匹配度排序：在不确定推理中，需要计算已知事实与知识的匹配度。（4）按条件个数排序：优先应用条件少的产生式规则。,.,4.2消解原理,4.2.1子句集的求取消解原理是针对谓词逻辑知识表示的问题求解方法。消解原理的基础知识：（1）谓词公式、某些推理规则以及置换合一等概念。（2）子句：由文字的析取组成的公式(一个原子公式和原子公式的否定都叫做文字)。（3）消解：当消解可使用时，消解过程被应用于母体子句对，以便产生一个导出子句。例如，如果存在某个公理E1E2和另一公理E2E3，那么E1E3在逻辑上成立。这就是消解，而称E1E3为E1E2和E2E3的消解式。,.,4.2消解原理,4.2.1子句集的求取步骤(1)消去蕴涵符号只应用和符号，以AB替换AB。(AB)BC=(AB)BC=(AB)BC=(AB)BC=（AB）（BB）C=（AB）C,.,4.2消解原理,4.2.1子句集的求取(2)减少否定符号的辖域每个否定符号最多只用到一个谓词符号上，并反复应用狄摩根定律。例如：以AB代替(AB)以AB代替(AB)以A代替(A)以(彐x)A代替(x)A以(x)A代替(彐x)A,.,4.2消解原理,4.2.1子句集的求取(3)对变量标准化在任一量词辖域内，受该量词约束的变量为一哑元(虚构变量)，它可以在该辖域内处统一地被另一个没有出现过的任意变量所代替，而不改变公式的真值。合适公式中变量的标准化意味着对哑元改名以保证每个量词有其自己唯一的哑元。如，对(x)P(x)(彐x)Q(x)标准化可得：(x)P(x)(彐y)Q(y),.,4.2消解原理,4.2.1子句集的求取(4)消去存在量词Skolem函数：(y)(彐x)P(x,y)中，存在量词是在全称量词的辖域内，允许所存在的x可能依赖于y值。令这种依赖关系明显地由函数g(y)所定义，它把每个y值映射到存在的那个x。这种函数叫做Skolem函数。如果用Skolem函数代替存在的x，就可以消去全部存在量词，并写成：(y)P(g(y),y),.,4.2消解原理,4.2.1子句集的求取从一个公式消去一个存在量词的一般规则是以一个Skolem函数代替每个出现的存在量词的量化变量，而这个Skolem函数的变量就是由那些全称量词所约束的全称量词量化变量，这些全称量词的辖域包括要被消去的存在量词的辖域在内。Skolem函数所使用的函数符号必须是新的，即不允许是公式中已经出现过的函数符号。,.,4.2消解原理,4.2.1子句集的求取如果要消去的存在量词不在任何一个全称量词的辖域内，则用不含变量的Skolem函数即常量。例如，(彐x)P(x)化为P(A)，其中常量符号A用来表示人们知道的存在实体。A必须是个新的常量符号，它未曾在公式中其它地方使用过。(彐z)(y)(彐x)P(x,y,z)=(y)P(g(y),y,A),g(y)为一Skolem函数,.,4.2消解原理,4.2.1子句集的求取(5)化为前束形把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。所得公式称为前束形。前束形=（前缀）（母式）全称量词串无量词公式(6)把母式化为合取范式任何母式都可写成由一些谓词公式和(或)谓词公式的否定的析取的有限集组成的合取。这种母式叫做合取范式。如：ABC化为ABBC,.,4.2消解原理,4.2.1子句集的求取(7)消去全称量词消去明显出现的全称量词。(8)消去连词符号用A，B代替(AB)，以消去明显的符号。反复代替的结果，最后得到一个有限集，其中每个公式是文字的析取。任一个只由文字的析取构成的合适公式叫做一个子句。(9)更换变量名称可以更换变量符号的名称，使一个变量符号不出现在一个以上的子句中。,.,4.2消解原理,4.2.1子句集的求取例：将下列谓词演算公式化为一个子句集(x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y)（1）消去蕴涵符号(x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y)（2）减少否定符号辖域(x)P(x)(y)P(y)P(f(x,y)(彐y)Q(x,y)P(y)(x)P(x)(y)P(y)P(f(x,y)(彐y)Q(x,y)P(y)（3）对变量标准化(x)P(x)(y)P(y)P(f(x,y)(彐w)Q(x,w)P(w),.,4.2消解原理,4.2.1子句集的求取（4）消去存在量词(x)P(x)(y)P(y)P(f(x,y)Q(x,g(x)P(g(x)w=g(x)为一个skolem函数。（5）化为前束形(x)(y)P(x)P(y)P(f(x,y)Q(x,g(x)P(g(x)（6）把母式化为合取范式(x)(y)P(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x),.,4.2消解原理,4.2.1子句集的求取（7）消去全称量词P(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x)（8）消去连词符号P(x)P(y)P(f(x,y)，P(x)Q(x,g(x)，P(x)P(g(x)（9）更换变量名称P(x1)P(y)P(f(x1,y)，P(x2)Q(x2,g(x2)，P(x3)P(g(x3),.,4.2消解原理,4.2.2消解推理规则令L1为任一原子公式，L2为另一原子公式；L1和L2具有相同的谓词符号，但一般具有不同的变量。已知两子句L1和L2,如果L1和L2具有最一般合一者，那么通过消解可以从这两个父辈子句推导出一个新子句()。这个新子句叫做消解式。它是由取这两个子句的析取，然后消去互补对而得到的。,.,4.2消解原理,4.2.2消解推理规则常用消解规则(1)假言推理父辈子句PPQ(即PQ)消解式Q,.,4.2消解原理,4.2.2消解推理规则常用消解规则(2)合并父辈子句PQPQ消解式QQ=Q,.,4.2消解原理,4.2.2消解推理规则常用消解规则(3)重言式PQPQPQPQ消解式QQPP,.,4.2消解原理,4.2.2消解推理规则常用消解规则(4)空子句(矛盾)PP消解式NIL,.,4.2消解原理,4.2.2消解推理规则常用消解规则(5)链式(三段论)PQQR消解式PR,.,4.2消解原理,4.2.3含有变量的消解式为了对含有变量的子句使用消解规则，必须找到一个置换，作用于父辈子句使其含有互补文字。例：设有两个字句P(x)Q(x)Q（f(y)）置换=f(y)/x消解可得：P（f(y)）,.,4.2消解原理,4.2.3含有变量的消解式令父辈子句由Li和Mi给出，假设这两个子句中的变量已经分别标准化。设li是Li的一个子集，mi是Mi的一个子集，若是li和mi的最一般的合一，消解两个子句Li和Mi，得到新子句Li-liMi-mi就是这两个子句的消解式。消解两个子句时，可能有一个以上的消解式，因为有多种选择li和mi的方法。,.,4.2消解原理,4.2.3含有变量的消解式例：考虑两个子句：Px,f(A)Px,f(y)Q(y)Pz,f(A)Q(z)取li=Px,f(A)，mi=Pz,f(A)可得消解式Pz,f(y)Q(y)Q(z),=z/x,.,4.2消解原理,4.2.3含有变量的消解式如果取li=Q(y)，mi=Q(z)则可得消解式Px,f(A)Px,f(y)Py,f(A)进一步消解的消解式Py,f(y),=y/z,.,4.2消解原理,4.2.3含有变量的消解式几个含有变量的子句使用消解的例子：,B(x),B(x)C(x),C(x),.,4.2消解原理,4.2.3含有变量的消解式几个含有变量的子句使用消解的例子：,P(x)Q(x),Qf(y),Pf(y),=f(y)/x,.,4.2消解原理,4.2.3含有变量的消解式几个含有变量的子句使用消解的例子：,P(x,f(y)Q(x)Rf(a),y,Pf(f(a),zR(z,w),Q(f(f(a)Rf(a),yR(f(y),w),=f(f(a)/x,f(y)/z,.,4.2消解原理,4.2.4消解反演求解过程1.基本思想把要解决的问题作为一个要证明的命题，其目标公式被否定并化成子句形，然后添加到命题公式集中去，把消解反演系统应用于联合集，并推导出一个空子句(NIL)，产生一个矛盾，这说明目标公式的否定式不成立，即有目标公式成立，定理得证，问题得到解决，与数学中反证法的思想十分相似。,.,4.2消解原理,4.2.4消解反演求解过程2、消解反演反演求解的步骤给出一个公式集S和目标公式L，通过反证或反演来求证目标公式L，其证明步骤如下：(1)否定L，得L；(2)把L添加到S中去；(3)把新产生的集合L，S化成子句集；(4)应用消解原理，力图推导出一个表示矛盾的空子句NIL。,.,4.2消解原理,4.2.4消解反演求解过程反演求解举例例：储蓄问题前提：每个储蓄钱的人都获得利息。结论：如果没有利息，那么就没有人去储蓄钱证明：令S(x,y)表示“x储蓄y”M(x)表示“x是钱”I(x)表示“x是利息”E(x,y)表示“x获得y”于是上述命题写成：,.,4.2消解原理,4.2.4消解反演求解过程(x)(彐y)(S(x,y)M(y)=(彐y)(I(y)E(x,y)结论：(彐x)I(x)=(x)(y)(M(y)=(S(x,y)化为子句集：S=S(x,y)M(y)I(f(x),S(x,y)M(y)E(x,f(x)其中，y=f(x)为Skolem函数。而L=(彐x)I(x)=(x)(y)(s(x,y)=M(y)=I(z),S(a,b),M(b),P=Q等价Q=P,.,4.2消解原理,4.2.4消解反演求解过程按4个步骤进行反演求解（1）否定L，即有L=I(z),S(a,b),M(b)（2）将L添加到S中去,即S=L,S=S(x,y)M(y)I(f(x),S(x,y)M(y)E(x,f(x),I(z),S(a,b),M(b)（3）把新产生的集合化成子句集，即S=S(x,y)M(y)I(f(x),S(x,y)M(y)E(x,f(x),I(z),S(a,b),M(b)（4）应用消解原理，推导出一个表示矛盾的空子句NIL。,.,4.2消解原理,4.2.4消解反演求解过程,S(x,y)M(y)I(f(x),I(z),S(x,y)M(y),=f(x)/z,M(b),S(a,b),=a/x,b/y,NIL,M(b),.,4.2消解原理,4.2.4消解反演求解过程反演求解过程步骤：(1)把由目标公式的否定产生的每个子句添加到目标公式否定之否定的子句中去。(2)按照反演树，执行和以前相同的消解，直至在根部得到某个子句止。(3)用根部的子句作为一个回答语句。,.,4.2消解原理,4.2.4消解反演求解过程例4.3如果无论约翰(John)到哪里去，菲多(Fido)也就去那里，那么如果约翰在学校里，菲多在哪里呢?事实公式集：S=(x)AT(JOHN,x)=AT(FIDO,x),AT(JOHN,SCHOOL)目标公式L：(彐x)AT(FIDO,x)首先证明L在逻辑上遵循公式集SL=(彐x)AT(FIDO,x)=(x)AT(FIDO,x)其子句为AT(FIDO,x),.,4.2消解原理,4.2.4消解反演求解过程例4.3的反演树,AT(FIDO,x),AT(JOHN,y)AT(FIDO,y),AT(JOHN,x),=x/y,NIL,AT(JOHN,SCHOOL),=SCHOOL/x,.,4.2消解原理,4.2.4消解反演求解过程例4.3从消解求取答案的反演树,AT(FIDO,x)AT(FIDO,y),AT(JOHN,y)AT(FIDO,y),AT(JOHN,x)AT(FIDO,x),=x/y,AT(FIDO,SCHOOL),AT(JOHN,SCHOOL),=SCHOOL/x,目标公式的重言式,.,4.3规则演绎系统,规则演绎系统：基于规则的问题求解系统运用下述规则来建立：IfThen其中，If部分可能由几个if组成，而Then部分可能由一个或一个以上的then组成。在所有基于规则系统中，每个if可能与某断言(assertion)集中的一个或多个断言匹配。有时把该断言集称为工作内存。在许多基于规则系统中，then部分用于规定放入工作内存的新断言。这种基于规则的系统叫做规则演绎系统(rulebaseddeductionsystem)。在这种系统中，通常称每个if部分为前项(antecedent)，称每个then部分为后项(consequent)。,.,4.3规则演绎系统,产生式系统：在基于规则系统中，当then部分用于规定动作时，称这种基于规则的系统为反应式系统(reactionsystem)或产生式系统(productionsystem)。产生式系统由3个部分组成：if某种动物是哺乳动物并且吃肉then这种动物是食肉动物,控制策略,产生式规则,总数据库,.,4.4不确定性推理,关于证据的不确定性（1）不确定性的表示一般通过对事实赋于一个介于0和1之间的系数来表示事实的不确定性。1代表完全确定，0代表完全不确定。这个系数被称为置信度。（2）不确定性的处理当规则具有一个以上的条件时，就需要根据各条件的置信度来求得总条件部分的置信度。已有的方法有两类：以模糊集理论为基础的方法按这种方法，把所有条件中最小的置信度作为总条件的置信度。这种方法类似于当把几根绳子连接起来使用时，总的绳子强度与强度最差的绳子的相同。,.,4.4不确定性推理,以概率为基础的方法这种方法同样赋予每个证据以置信度。但当把单独条件的置信度结合起来求取总的置信度时，它取决于各置信度的乘积。关于结论的不确定性（1）不确定性的表示关于结论的不确定性也叫做规则的不确定性，它表示当规则的条件被完全满足时，产生某种结论的不确定程度。它也是以赋予规则在0和1之间的系数的方法来表示的。,.,4.4不确定性推理,（2）不确定性的处理如果规则的条件部分不完全确定，即置信度不为1时，如何求得结论的可信度的方法有以下两种：取结论置信度为条件可信度与上述系数的乘积。按照某种概率论的解释，我们假设规则的条件部分的置信度Cin和其结论部分的置信度Cout存在某种关系，这种关系可用来代表规则的不确定性。例：规则：如果今天闷热，那么明天会下雨0.9证据：星期六闷热0.8,.,4.4不确定性推理,4.4.1概率推理主观Bayes方法设推理规则P=Q是不确定的，其不确定性可以由条件概率p(Q|P)表示；若已知前提P成立的概率p(P)，则可求得PQ成立的概率（P，Q联合概率）p(P,Q)=p(Q|P)p(P)依据Bayes理论，有以下条件概率公式,.,4.4不确定性推理,4.4.1概率推理其中p(P)和p(Q)分别指示前提和结论的先验概率；p(P|Q)称为后验概率，指示结论Q成立时前提P成立的概率。通常后验概率比条件概率更易于获取，所以可不经由统计手段去获得条件概率，而是由上面公式计算。例：令P为汽车轮子发出的刺耳噪声，Q为汽车刹车失调。P可视为征兆，Q则指示引起P的原因。原因和征兆之间的的对应关系可用后验概率p(P|Q)表示。设想根据经验，刹车调整不好会引起刺耳噪声，并估计p(P|Q)=0.7，若同时又获得先验概率p(P)=0.04，p(Q)=0.05，则可求得,.,4.4不确定性推理,4.4.1概率推理即每当发现车轮的刺耳噪声时，可以推测有0.88的可能性是刹车失调。,.,4.4不确定性推理,4.4.2Bayes（网络）推理亦称信念网络（beliefnetwork）：是一种模拟人类推理过程中因果关系的不确定处理模型，其网络拓扑结构是一个有向无环图（DAG）。节点用随机变量或命题来标识，认为有直接关系的命题或变量用弧来连接。,.,Judea.Pearl（1936）加州大学洛杉矶分校计算机科学学院教授、认知系统实验室主任美国国家工程院院士2011年图灵奖获得者主要贡献：（1）提出贝叶斯网络（2）建立因果关系模型,4.4不确定性推理,.,4.4不确定性推理,4.4.2Bayes（网络）推理一个关于家庭防盗的贝叶斯网络。家里安装的报警器能够有效感知盗贼的侵入，并对轻微的地震有一定的感知能力。两个邻居李和张听到报警声时都会友善地来电话提醒，但偶尔李会错将门铃声当作报警声，而张则会因为大声听音乐而听不到报警声。该网络的拓扑结构表明盗贼和地震是警报声响的直接原因，而邻居李和张来电话的直接原因是听到了警报声。,.,4.4不确定性推理,4.5.2Bayes（网络）推理,.,4.4不确定性推理,4.4.2Bayes（网络）推理分别以字母B、E、A、L、Z指示节点（变量）“盗贼入侵”、“地震发生”、“报警声响”、“李来电话”、“张来电话”