Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Click to edit Master title style,西安电子科技大学,Artificial Intelligence(AI),人工智能,主讲：戚玉涛,Email,：,第三章：确定性推理,内容提要,第三章：确定性推理,1.,推理的基本概念,2.,搜索策略,3.,自然演绎推理,4.,归结演绎推理,5.,基于规则的演绎推理,内容提要,第三章：确定性推理,1.,推理的基本概念,2.,搜索策略,3.,自然演绎推理,4.,归结演绎推理,5.,基于规则的演绎推理,推理的基本概念,推理的基本概念,1.,什么是推理,2.,推理方法及其分类,3.,推理的控制策略及其分类,推理的基本概念,什么是推理,所谓推理就是按某种策略由已知判断推出另一个判断的思维过程在人工智能中，推理是由程序实现的，称为推理机智能系统的推理过程实际上就是一种思维过程按照推理过程所用知识的确定性，推理可分为：,确定性推理（第三章）,不确定性推理（第四章）,推理的基本概念,推理的两个基本问题,推理的方法：,演绎？归纳？类比？确定？不确定？单调？非单调？启发式？非启发式？,推理的控制策略：,推理的控制策略是指如何使用领域知识使推理过程尽快达到目标的策略。
推理的控制策略又可分为,搜索策略,和,推理策略,推理的基本概念,推理方法及其分类,1.,按推理的逻辑基础分类,演绎推理,:,从已知的一般性知识出发，推出蕴含在已知知识中的适合于某种个别情况的结论是一种由一般到个别的推理方法，其,核心是三段论,归纳推理,:,是一种由个别到一般的推理方法类比归纳推理,:,是指在两个或两类事物有许多属性都相同或相似的基础上，推出它们在其他属性上也相同或相似的一种归纳推理,推理的基本概念,推理方法及其分类,1.,按推理的逻辑基础分类,演绎推理：,假言三段论：,AB,，,BC AC,常用的三段论是由一个,大前提,、,一个小前提,和,一个结论,这三部分组成的大前提是已知的一般性知识或推理过程得到的判断；,小前提是关于某种具体情况或某个具体实例的判断；,结论是由大前提推出的，并且适合于小前提的判断推理的基本概念,推理方法及其分类,1.,按推理的逻辑基础分类,演绎推理：,例如，有如下三个判断：,计算机系的学生都会编程序；（一般性知识）,程强是计算机系的一位学生；（具体情况）,程强会编程序结论）,这是一个三段论推理其中，是大前提，是小前提；是经演绎推出来的结论可见，,其结论是蕴含在大前提中的,推理的基本概念,推理方法及其分类,1.,按推理的逻辑基础分类,归纳推理：,按照所选事例的,广泛性,可分为,完全归纳推理,和,不完全归纳推理,。
完全归纳推理：,是指在进行归纳时需要考察相应事物的,全部对象,，并根据这些对象是否都具有某种属性，推出该类事物是否具有此属性不完全归纳推理：,是指在进行归纳时只考察了相应事物的,部分对象,，就得出了关于该事物的结论推理的基本概念,推理方法及其分类,1.,按推理的逻辑基础分类,归纳推理：,按照推理所使用的,方法,可分为,枚举,、,类比,、,统计,和,差异归纳推理,等枚举归纳推理：,是指在进行归纳时，如果已知某类事物的,有限可数个具体事物,都具有某种属性，则可推出该类事物都具有此种属性例如，设有如下事例：,王强是计算机系学生，他会编程序；高华是计算机系学生，她会编程序；,当这些具体事例足够多时，就可归纳出一个一般性的知识：凡是计算机系的学生，就一定会编程序推理的基本概念,推理方法及其分类,1.,按推理的逻辑基础分类,类比归纳推理：,若在两个或两类事物有许多属性相同或相似，则推出它们在其他属性上也相同或相似例如：,设,A,、,B,分别是两类事物的集合：,A=a,1,a,2,，,B=b,1,b,2,并设,a,i,与,b,i,总是成对出现，且当,a,i,有属性,P,时，,b,i,就有属性,Q,与此对应，即,P(a,i,)Q(b,i,),（,i=1,2,.,）。
当,A,与,B,中有一新的元素对出现时，若已知,a,有属性,P,，,b,有属性,Q,则类比归纳出结论：,P(a)Q(b,),推理的基本概念,推理方法及其分类,1.,按推理的逻辑基础分类,类比归纳推理：,类比归纳推理的基础是,相似原理,，其可靠程度取决于两个或两类事物的相似程度以及这两个或两类事物的相同属性与推出的那个属性之间的相关程度推理的基本概念,推理方法及其分类,1.,按推理的逻辑基础分类,演绎推理与归纳推理的区别：,演绎推理是在已知领域内的一般性知识的前提下，通过演绎求解一个具体问题或者证明一个结论的正确性它所得出的结论实际上早已蕴含在一般性知识的前提中,，演绎推理只不过是将已有事实揭露出来，因此,它不能增殖新知识,归纳推理所推出的结论是没有包含在前提内容中的,这种由个别事物或现象推出一般性知识的过程，,是增殖新知识的过程,推理的基本概念,推理方法及其分类,2.,按推理过程所用知识的确定性分类,确定性推理,不确定性推理,3.,按推理过程推出的结论是否单调增加分类,单调推理,非单调推理,4.,按推理过程是否利用问题的启发性知识分类,启发式推理,非启发式推理,推理的基本概念,推理的控制策略及其分类,推理过程不仅依赖于所用的推理方法，同时也依赖于推理的控制策略。
推理的控制策略是指如何使用领域知识使推理过程尽快达到目标的策略,推理的控制策略可分为：,搜索策略,推理策略,推理的基本概念,推理的控制策略及其分类,搜索策略：,在知识库中寻找可利用的知识，从而构造一条代价较小的推理路线主要解决推理线路、推理效果、推理效率等问题按是否使用启发式信息可分为：,盲目搜索,启发式搜索,按问题的表示方式可分为：,状态空间搜索,与或树搜索,推理的基本概念,推理的控制策略及其分类,推理策略：,包括推理方向控制策略、求解策略、限制策略、冲突消解策略等,推理方向控制策略：,用于确定推理的控制方向，可分为正向推理、逆向推理、混合推理及双向推理求解策略：,是指仅求一个解，还是求所有解或最优解等限制策略：,是指对推理的深度、宽度、时间、空间等进行的限制冲突消解策略：,是指当推理过程有多条知识可用时，如何从这多条可用知识中选出一条最佳知识用于推理的策略推理的基本概念,推理的控制策略及其分类,推理方向控制策略：,正向推理：,从已知事实出发、正向使用推理规则，亦称为数据驱动推理或前向链推理正向推理从用户提供的初始已知事实出发，在知识库,KB,中找出当前可适用的知识，构成可适用的知识集,KS,；然后按某种冲突消解策略从,KS,中选出一条知识进行推理，并将推出的新事实加入到数据库,DB,中，作为下一步推理的已知事实。
在此之后，再在知识库中选取可适用的知识进行推理如此重复进行这一过程，直到求得所要求的解推理的基本概念,推理的控制策略及其分类,推理方向控制策略：,正向推理中，如何根据已知事实到知识库中选取可用知识？当知识库中有多条知识可用时应该先使用那一条知识？这些问题涉及到了,知识的匹配方法,和,冲突消解策略正向推理的优点：,比较直观，允许用户主动提供有用的事实信息，适合于诊断、设计、预测、监控等领域的问题求解正向推理的缺点：,推理无明确目标，求解问题是可能会执行许多与解无关的操作，导致推理效率较低推理的基本概念,推理的控制策略及其分类,推理方向控制策略：,逆向推理：,从某个假设目标出发，逆向使用规则，亦称为目标驱动推理或逆向链推理逆向推理首先选定一个假设目标，然后寻找支持该假设的证据，若所需的证据都能找到，则说明原假设是成立的；若找不到所需要的证据，则说明原假设不成立，此时需要另作新的假设推理的基本概念,推理的控制策略及其分类,推理方向控制策略：,逆向推理的主要优点：,不必寻找和使用那些与假设目标无关的信息和知识，推理过程的目标明确，有利于向用户提供解释，在诊断性专家系统中较为有效逆向推理的主要缺点：,当用户对解的情况认识不请时，由系统自主选择假设目标的盲目性比较大，若选择不好，可能需要多次提出假设，会影响系统效率。
推理的基本概念,推理的控制策略及其分类,推理方向控制策略：,混合推理：,把正向推理和逆向推理结合起来所进行的推理称为混合推理是一种解决较复杂问题的方法混合推理方法的三种类型：,1.,先正向后逆向：,这种方法先进行正向推理，从已知事实出发推出部分结果，然后再用逆向推理对这些结果进行证实或提高它们的可信度推理的基本概念,推理的控制策略及其分类,推理方向控制策略：,混合推理方法的三种类型：,2.,先逆向后正向：,这种方法先进行逆向推理，从假设目标出发推出一些中间假设，然后再用正向推理对这些中间假设进行证实3.,双向混合：,是指正向推理和逆向推理同时进行，使推理过程在中间的某一步结合起来内容提要,第三章：确定性推理,1.,推理的基本概念,2.,搜索策略,3.,自然演绎推理,4.,归结演绎推理,5.,基于规则的演绎推理,搜索策略,搜索策略,搜索的基本概念,状态空间的搜索策略,与,/,或树的搜索策略,搜索的完备性与效率,搜索的基本概念,搜索的基本概念,搜索是人工智能中的一个基本问题，并与推理密切相关，搜索策略的优劣，将直接影响到智能系统的性能与推理效率搜索的定义：,依靠经验，利用已有知识，根据问题的实际情况，不断寻找可利用知识，从而构造一条代价最小的推理路线，使问题得以解决的过程称为搜索。
搜索的适用情况：,不良结构或非结构化问题；难以获得求解所需的全部信息；更没有现成的算法可供求解使用搜索的基本概念,搜索的类型,按是否使用启发式信息：,盲目搜索：,按预定的控制策略进行搜索，在搜索过程中获得的中间信息并不改变控制策略启发式搜索：,在搜索中加入了与问题有关的启发性信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解按问题的表示方式：,状态空间搜索：,用状态空间法求解问题进行的搜索,与或树搜索：,用问题归约法求解问题进行的搜索,状态空间的搜索策略,状态空间的搜索策略,状态空间搜索的基本思想,图搜索的一般过程,状态空间的盲目搜索,广度优先搜索,深度优先搜索,代价树搜索,状态空间的启发式搜索,启发性信息和估价函数,A,算法和,A*,算法,状态空间的搜索策略,状态空间搜索的基本思想,先把问题的初始状态作为当前,扩展节点,对其进行,扩展,，生成一组子节点然后检查问题的目标状态是否出现在这些子节点中若出现，则搜索成功，找到了问题的解；若没出现，则再,按照某种搜索策略从已生成的子节点中选择一个节点作为当前扩展节点,重复上述过程，直到目标状态出现在子节点中或者没有可供操作的节点为止。
所谓对一个节点进行,“扩展”是指对该节点用某个可用操作进行作用，生成该节点的一组子节点状态空间的搜索策略,状态空间搜索算法的数据结构和符号约定,OPEN,表：,未扩展节点表，用于存放刚生成节点,CLOSED,表：,已扩展节点表，用于存放已经扩展或将要扩展节点的,S,：,用表示问题的初始状态,G,：,表示搜索过程所得到的搜索图,M,：,表示当前扩展节点新生成的且不为自己先辈的子节点集,状态空间的搜索策略,图搜索的一般过程,(1),把初始节点,S,放入未扩展节点表,OPEN,表，并建立目前仅包含,S,的图,G,；,(2),检查,OPEN,表是否为空，若为空，则问题无解，失败退出；,(3),把,OPEN,表的,第一个节点,取出放入已扩展节点表,CLOSED,表，并记该节点为节点,n,；,(4),考察节点,n,是否为目标节点若是则得到了问题的解，成功退出此时的解为追踪图,G,中沿着指针,（步骤,6,中设置的指针）,从,n,到初始节点,S,的路径状态空间的搜索策略,图搜索的一般过程,(5),扩展节点,n,，生成。
