西电人工智能8确定性推理part1

ArtificialIntelligence(AI)

人工智能主讲：戚玉涛：qi_yutao@163第三章：确定性推理内容提要第三章：确定性推理1.推理的根本概念2.搜索战略3.自然演绎推理4.归结演绎推理5.基于规那么的演绎推理内容提要第三章：确定性推理1.推理的根本概念2.搜索战略3.自然演绎推理4.归结演绎推理5.基于规那么的演绎推理推理的根本概念推理的根本概念1.什么是推理2.推理方法及其分类3.推理的控制战略及其分类推理的根本概念什么是推理所谓推理就是按某种战略由知判别推出另一个判别的思想过程。在人工智能中，推理是由程序实现的，称为推理机。智能系统的推理过程实践上就是一种思想过程。按照推理过程所用知识确实定性，推理可分为：确定性推理〔第三章〕不确定性推理〔第四章〕推理的根本概念推理的两个根本问题推理的方法：演绎？归纳？类比？确定？不确定？单调？非单调？启发式？非启发式？推理的控制战略：推理的控制战略是指如何运用领域知识使推理过程尽快到达目的的战略。推理的控制战略又可分为搜索战略和推理战略。推理的根本概念推理方法及其分类1.按推理的逻辑根底分类演绎推理:从知的普通性知识出发，推出蕴含在知知识中的适宜于某种个别情况的结论。是一种由普通到个别的推理方法，其中心是三段论。归纳推理:是一种由个别到普通的推理方法。类比归纳推理:是指在两个或两类事物有许多属性都一样或类似的根底上，推出它们在其他属性上也一样或类似的一种归纳推理。推理的根本概念推理方法及其分类1.按推理的逻辑根底分类演绎推理：假言三段论：A→B，B→C⇒A→C常用的三段论是由一个大前提、一个小前提和一个结论这三部分组成的。大前提是知的普通性知识或推理过程得到的判别；小前提是关于某种详细情况或某个详细实例的判别；结论是由大前提推出的，并且适宜于小前提的判别。推理的根本概念推理方法及其分类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)把