《人工智能原理及应用 教学课件 ppt 作者 罗 兵 第3章 确定性推理方法》由会员分享，可在线阅读，更多相关《人工智能原理及应用 教学课件 ppt 作者 罗 兵 第3章 确定性推理方法（74页珍藏版）》请在金锄头文库上搜索。
1、人工智能原理及应用,第3章 确定性推理方法 二零一二年元月,AI & its Applications,确定性推理方法,知识是人工智能研究的一个核心问题，它包括两个方面：知识表示和知识推理，即如何在人工智能中清晰地表示人类的常识，并运用这些常识去进行符合人类行为的推理。 按照推理过程所用知识的确定性，推理可分为确定性推理和不确定性推理。自然演绎推理和归结推理是经典的确定性推理，它们以数理逻辑的有关理论、方法和技术为理论基础，是机械化的、可在计算机上加以实现的推理方法。,第3章 主要内容,3.1 推理概述 3.2 确定性推理的逻辑基础 3.3 演绎推理方法 3.4 归结推理方法 3.5 归结过程
2、中的控制策略,3.1 推理概述,3.1.1 推理的概念 3.1.2 推理的方法 3.1.3 推理的控制策略 3.1.4 推理中的冲突,3.1 推理概述,3.1.1 推理的概念,所谓推理是指按照某种策略从已知事实出发去推出结论的过程。知识推理是指在计算机或智能机器中，在知识表达的基础上，利用形式化的知识模型，进行机器思维求解问题，实现状态转移的智能操作序列。 推理所用的事实可分为两种情况，一种是与求解问题有关的初始证据；另一种是推理过程中所得到的中间结论，这些中间结论可以作为进一步推理的已知事实或证据。 例：商品是用来交换的，所以，有些用来交换的是商品。 老虎是要吃人的，东北虎是老虎；所以，东北
3、虎是要吃人的。 智能系统的推理包括两个方面的基本问题：一个方面是推理的方法，另一个方面是推理的控制策略。,3.1 推理概述,3.1.2 推理的方法,推理有很多种方法，根据知识表示方式分类分为“图搜索”方法及“逻辑论证”方法；根据逻辑基础分类可分为演绎推理、归纳推理、默认（缺省）推理；根据知识的确定性分类分为确定性推理与非确定性推理；根据推理过程的单调性分类分为单调推理、非单调推理。 1演绎推理： 演绎推理是一种由一般到个别的推理方法，其核心是三段论，由一个大前提、一个小前提和一个结论这三部分组成的。其逻辑式为： 大前提是已知的一般性知识或推理过程得到的判断； 小前提是关于某种具体情况或某个具体
4、实例的判断； 结论是由大前提推出的，并且适合于小前提的判断。,3.1 推理概述,3.1.2 推理的方法,1演绎推理： 例：有如下三个判断： 计算机系的学生都会编程序；（一般性知识） 程强是计算机系的一位学生；（具体情况） 因此程强会编程序。（结论） 这是一个三段论推理。其中：“计算机系的学生都会编程序”是大前提，“程强是计算机系的一位学生”是小前提，那么“程强会编程序”是经演绎推出来的结论。其结论蕴含在大前提中，这就是典型的演绎推理三段论。,3.1 推理概述,3.1.2 推理的方法,2归纳推理 归纳推理的基本思想是：先从已知事实中猜测出一个结论，然后对这个结论的正确性加以验证。例如常用的数学归
5、纳法。 归纳推理的类型按照所选取的事例的广泛性可分为完全归纳推理、不完全归纳推理。归纳推理按照推理所使用的方法可分为枚举归纳推理、类比归纳推理、默认推理等。 （1）枚举归纳推理：是由已观察到的事物都有某属性，而没有观察到相反的事例，从而推出某类事物都有某属性。 （2）类比归纳推理：指在两个或两类事物有许多属性都相同或相似的基础上，推出它们在其它属性上也相同或相似的一种归纳推理。 （3）默认推理：称为缺省推理，它是在知识不完全的情况下假设某些条件已经具备所进行的推理。,3.1 推理概述,3.1.2 推理的方法,3演绎推理与归纳推理的区别： 演绎推理是在已知领域内的一般性知识的前提下，通过演绎求解
6、一个具体问题或者证明一个结论的正确性。它所得出的结论实际上早已蕴含在一般性知识的前提中，演绎推理只不过是将已有事实揭露出来，因此它不能增殖新知识。 归纳推理所推出的结论是没有包含在前提内容中的。这种由个别事物或现象推出一般性知识的过程，是增殖新知识的过程。 4推理的其它分类： （1）确定性推理与不确定推理 （2）单调推理与非单调推理 （3）启发式推理与非启发式推理,3.1 推理概述,3.1.3 推理的控制策略,推理的控制策略是指如何使用领域知识使推理过程尽快达到目标的策略，主要是指推理方向的选择、推理时所用的搜索策略及冲突解决策略等。推理的控制策略包括推理策略和搜索策略。 推理策略主要解决推理
7、方向、求解策略、冲突消解策略等问题。 搜索策略主要解决推理线路、推理效果、推理效率等问题。 按照对推理方向的控制，推理可分为正向推理、反向推理、混合推理及双向推理四种情况。一般都要求系统具有三个要素： 一个存放知识的知识库 一个存放初始事实和中间结果的数据库 一个用于推理的推理机,3.1 推理概述,3.1.3 推理的控制策略,3.1.3.1 正向推理 正向推理是由已知事实出发，正向使用推理规则向结论方向的推理，算法步骤描述如下： （1）把用户提供的初始证据放入综合数据库； （2）检查综合数据库中是否包含了问题的解，若已包含，则求解结束，并成功推出；否则执行下一步；,3.1 推理概述,3.1.3
8、 推理的控制策略,3.1.3.1 正向推理 （3）检查知识库中是否有可用知识，若有，形成当前可用知识集，执行下一步；否则转(5)。 （4）按照某种冲突消解策略，从当前可用知识集中选出一条规则进行推理，并将推出的新事实加入综合数据库种，然后转(2)。,3.1 推理概述,3.1.3 推理的控制策略,3.1.3.1 正向推理 （5）询问用户是否可以进一步补充新的事实，若可补充，则将补充的新事实加入综合数据库中，然后转(3)；否则表示无解，失败退出。,3.1 推理概述,3.1.3 推理的控制策略,例：请用正向推理完成以下问题的求解：假设知识库中包含有以下2条规则： r1： IF B THEN C r2
9、： IF A THEN B 已知初始证据A，求证目标C。 解：本例的推理过程如下： 推理开始前，综合数据库为空。推理开始后，先把A放入综合数据库，然后检查综合数据库中是否含有该问题的解，回答为“N”。接着检查知识库中是否有可用知识，显然r2可用，形成仅含r2的知识集。从该知识集中取出r2，推出新的实事B，将B加入综合数据库，检查综合数据库中是否含有目标C，回答为“N”。再检查知识库中是否有可用知识，此时由于B的加入使得r1为可用，形成仅含r1的知识集。从该知识集中取出r1，推出新的实事C，将C加入综合数据库，检查综合数据库中是否含有目标C，回答为“Y”。 它说明综合数据库中已经含有问题的解，推
10、理成功结束，目标C得证。,3.1 推理概述,3.1.3 推理的控制策略,3.1.3.2 反向推理 反向推理是以某个假设目标作为出发点的一种推理，又称为目标驱动推理或逆向推理。 反向推理过程如图：,3.1 推理概述,3.1.3 推理的控制策略,3.1.3.2 反向推理 算法描述如下： （1）将要求证的目标（称为假设）构成一个假设集； （2）从假设集中选出一个假设，检查该假设是否在综合数据库中，若在，则该假设成立，此时，若假设集为空，则成功退出，否则仍执行(2)；若该假设不在数据库中，则执行下一步； （3）检查该假设是否可由知识库的某个知识导出，若不能由某个知识导出，则询问用户该假设是否为可由用户
11、证实的原始事实，若是，该假设成立，并将其放入综合数据库，再重新寻找新的假设，若不是，则转(5)；若能由某个知识导出，则执行下一步； （4）将知识库中可以导出该假设的所有知识构成一个可用知识集； （5）检查可用知识集是否为空，若是，失败退出；否则执行下一步； （6）按冲突消解策略从可用知识集中取出一个知识，继续； （7）将该知识的前提中的每个子条件都作为新的假设放入假设集，然后转(2)。,3.1 推理概述,3.1.3 推理的控制策略,例：请用反向推理完成以下问题的求解：假设知识库中包含有以下2条规则： r1： IF B THEN C r2： IF A THEN B 已知初始证据A，求证目标C。
12、解：其推理过程如下： 推理开始前，综合数据库和假设集均为空。先将初始证据A和目标C分别放入综合数据库和假设集，然后从假设集中取出一个假设C，查找C是否为综合数据库中的已知事实，回答为“N”。再检查C是否能被知识库中的知识所导出，发现C可由r1导出，于是r1被放入可用知识集。接着从可用知识集中取出r1，将其前提条件B作为新的假设放入假设集。检查B是否为综合数据库中的实事，回答为“N”。再检查B是否能被知识库中的知识所导出，发现B可由r2导出，于是r2被放入可用知识集。从可用知识集中取出r2，将其前提条件A作为新的假设放入假设集。然后从假设集中取出A，检查A是否为综合数据库中的实事，回答为“Y”。
13、 说明该假设成立，由于无新的假设，故推理过程成功结束，于是目标C得证。,3.1 推理概述,3.1.3 推理的控制策略,3.1.3.3 正反向混合推理 正向推理和反向推理相结合的推理方法称为正反向混合推理。混合推理的方法包括： 1. 先正向后逆向 2. 先逆向后正向 3. 双向混合,3.1 推理概述,3.1.4 推理中的冲突,在推理过程中，系统要不断地用数据库中的事实与知识库中的规则进行匹配，当有一个以上规则的条件部分和当前数据库相匹配时，就需要有一种策略来决定首先使用哪一条规则，这就是冲突解决策略。冲突解决策略实际上就是确定规则的启用顺序。 常用排序方法有如下几种: （1）按专一性排序 （2）
14、按规则排序 （3）按数据排序 （4）按就近原则排序 （5）上下文限制 （6）按匹配度排序 （7）按条件个数排序,3.2 确定性推理的逻辑基础,3.2.1 命题公式的解释 3.2.2 等价式 3.2.3 永真蕴含式 3.2.4 前束范式与Skolem范式 3.2.5 置换与合一,本节中要考虑在人工智能中如何利用谓词逻辑表示来完成由问题到结论的推理。,3.2 确定性推理的逻辑基础,3.2.1 命题公式的解释,定义3.1 设D是谓词公式P的非空个体域，若对P中的个体常量、函数和谓词按如下规定赋值： （1）为每个个体常量指派D中的一个元素； （2）为每个n元函数指派一个从 到D的一个映射，其中 （3）
15、为每个n元谓词指派一个从 到F，T的映射。 则称这些指派为P在D上的一个解释I。 定义3.2 对于谓词公式P，如果至少存在D上的一个解释，使公式P在此解释下的真值为T，则称公式P在D上是可满足的。,3.2 确定性推理的逻辑基础,3.2.2 等价式,定义3.3 设P与Q是D上的两个谓词公式，若对D上的任意解释，P与Q都有相同的真值，则称P与Q在D 上是等价的。如果D是任意非空个体域，则称P与Q是等价的，记作 。 常用谓词公式的等价式包括： （1）双重否定律： （2）交换律： （3）结合律： （4）分配律： （5）摩根定律：,3.2 确定性推理的逻辑基础,3.2.2 等价式,常用谓词公式的等价式包括： （6）吸收律： （7）补余律: （8）连词化归律: （9）量词转换律: （10）量词分配律:,3.2 确定性推理的逻辑基础,3.2.3 永真蕴含式,定义3.4 对谓词公式P和Q，如果 永真，则称P 永真蕴含Q，且称Q为P的逻辑结论，P为Q的前提，记作 。 常用永真蕴含式包括： （1）化简式： （2）附加式： （3）析取三段论： （4）假言推理： （5）拒取式：,3.2 确定性推理的逻辑基础,3.2.3 永真蕴含式,常用永真蕴
