西电人工智能8确定性推理课件.ppt
Artificial Intelligence (AI)人工智能,主讲：戚玉涛,Email：qi_,第三章：确定性推理,内容提要,第三章：确定性推理,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=a1,a2,，B=b1,b2,并设ai与bi总是成对出现，且当ai有属性P时，bi就有属性Q与此对应，即P(ai)Q(bi) （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，生成一组子节点。把这些子节点中不是节点n先辈的那部分子节点记入集合M，并把这些子节点作为节点n的子节点加入G中(6) 针对M中子节点的不同情况，分别作如下处理： 对那些没有在G中出现过的M成员设置一个指向其父节点（即节点n）的指针，并把它放入OPEN表。（新生成的） 对那些原来已在G中出现过，但还没有被扩展的M成员，确定是否需要修改它指向父节点的指针。（原生成但未扩展的） 对于那些先前已在G中出现过，并已经扩展了的M成员，确定是否需要修改其后继节点指向父节点的指针。（原生成也扩展过的）,图搜索的一般过程(7) 按某种策略对OPEN表中的节点进行排序。(8) 转第(2)步。,状态空间的搜索策略,状态空间的搜索策略,图搜索的一般过程的几点说明：上述过程是状态空间的一般图搜索算法，它具有通用性，后面所要讨论的各种状态空间搜索策略都是上述过程的一个特例。各种搜索策略的主要区别在于对OPEN表中节点的排列顺序不同。例如，广度优先搜索把先生成的子节点排在前面，而深度优先搜索则把后生成的子节点排在前面。,状态空间的搜索策略,图搜索的一般过程的几点说明：在第(6)步针对M中子节点的不同情况进行处理时，如果发生当第种情况，那么，这个M中的节点究竟应该作为哪一个节点的后继节点呢？一般是由原始节点到该节点路径上所付出的代价来决定的，哪一条路经付出的代价小，相应的节点就作为它的父节点。所谓由原始节点到该节点路径上的代价是指这条路经上的所有有向边的代价之和。 如果发生第种情况，除了需要确定该子节点指向父节点的指针外，还需要确定其后继节点指向父节点的指针。其依据也是由原始节点到该节点的路径上的代价。,状态空间的搜索策略,图搜索的一般过程的几点说明：在搜索图中，除初始节点外，任意一个节点都含有且只含有一个指向其父节点的指针。因此，由所有节点及其指向父节点的指针所构成的集合是一棵树，称为搜索树。在搜索过程的第(4)步，一旦某个被考察的节点是目标节点，则搜索过程成功结束。此时，由初始节点到目标节点路径上的所有操作就构成了该问题的解，而路径由第(6)步所形成的指向父节点的指针来确定。如果搜索过程终止在第(2)步，即没有达到目标，且OPEN表中已无可供扩展的节点，则失败结束。,状态空间的搜索策略,状态空间的搜索策略状态空间搜索的基本思想图搜索的一般过程状态空间的盲目搜索广度优先搜索深度优先搜索代价树搜索状态空间的启发式搜索启发性信息和估价函数A算法和A*算法,广度优先搜索,状态空间的广度优先搜索广度优先搜索的基本思想：从初始节点S开始逐层向下扩展，在第n层节点还没有全部搜索完之前，不进入第n+1层节点的搜索。未扩展节点表OPEN表中的节点总是按进入的先后排序，先进入的节点排在前面，后进入的节点排在后面。,广度优先搜索,状态空间的广度优先搜索广度优先搜索算法流程：(1)把初始节点S放入OPEN表中；(2)如果OPEN表为空，则问题无解，失败退出；(3)把OPEN表的第一个节点取出放入CLOSED表，并记该节点为n；(4)考察节点n是否为目标节点。若是，则得到问题的解，成功退出；(5)若节点n不可扩展，则转第(2)步；(6)扩展节点n，将其子节点放入OPEN表的尾部，并为每一个子节点设置指向父节点的指针，然后转第(2)步。,广度优先搜索,广度优先搜索的例子：八数码难题在33的方格棋盘上，分别放置了表有数字1、2、3、4、5、6、7、8的八张牌，初始状态S0，目标状态Sg，如下图所示。要求应用广度优先搜索策略寻找从初始状态到目标状态的解路径。,S0,Sg,广度优先搜索,八数码难题的宽度优先搜索树,广度优先搜索,在上述广度优先算法中需要注意两个问题：对于任意一个可扩展的节点，总是按照固定的操作符的顺序对其进行扩展（空格左移、上移、右移、下移）。在对任一节点进行扩展的时候，如果所得的某个子节点（状态）前面已经出现过，则立即将其放弃，不再重复画出（不送入OPEN表）。因此，广度优先搜索的本质是，以初始节点为根节点，在状态空间图中按照广度优先的原则，生成一棵搜索树。,广度优先搜索,广度优先搜索的特点：优点：只要问题有解，用广度优先搜索总可以得到解，而且得到的是路径最短的解。缺点：广度优先搜索盲目性较大，当目标节点距初始节点较远时将会产生许多无用节点，搜索效率低。,问题？,
