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

ArtificialIntelligence(AI)

人工智能主讲：戚玉涛Email：qi_yutao@163.com第三章：确定性推理内容提要要第三章：：确定性性推理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表中的节节点总是是按进入入的先后后排序，，先进入入的节点点排在前前面，后后进入的