《人工智能5第五章确定性推理精编版》由会员分享,可在线阅读,更多相关《人工智能5第五章确定性推理精编版(74页珍藏版)》请在金锄头文库上搜索。
1、第四章 确定性推理,2020/8/15,1,4.1 确定性推理概述,第四章 确定性推理 4.1概述,2020/8/15,2,推 理,推理是指按照某种策略从巳知事实出发去推出结论的过程 智能系统的推理过程实际上就是一种思维过程。 智能系统的推理过程是通过推理机来完成的。 推理机就是智能系统中用来实现推理的程序。 按照推理过程所用知识的确定性,推理可分为确定性推理和不确定性推理。,第四章 确定性推理 4.1概述,2020/8/15,3,事 实,事实是推理过程中按知识表示方式表示的已知的知识 推理所用的事实可分为两种情况: 与求解问题有关的初始证据 推理过程中所得到的中间结论。,第四章 确定性推理
2、4.1概述,2020/8/15,4,推理的基本问题,智能系统的推理包括两个基本问题: 一个是推理的方法 一个是推理的控制策略 推理方法主要解决: 在推理过程中前提与结论之间的逻辑关系 在非精确性推理中不确定性的传递问题,第四章 确定性推理 4.1概述,2020/8/15,5,推理方法的分类,推理可以有多种不同的分类方法 按照推理的逻辑基础分类: 演绎推理 归纳推理 默认推理 按照所用知识的确定性分类: 确定性推理 不确定性推理 按照推理过程的单调性分类(推理过程所得到的结论是否越来越接近目标): 单调推理 非单调推理,第四章 确定性推理 4.1概述,2020/8/15,6,演绎推理,从已知的一
3、般性知识出发,去推出蕴含在这些已知知识中的适合于某种个别情况的结论。 它是一种由一般到个别的推理方法。 核心是三段论,第四章 确定性推理 4.1概述,2020/8/15,7,归纳推理,从一类事物的大量特殊事例出发,去推出该类事物的一般性结论。 它是一种由个别到一般的推理方法。 基本思想: 先从已知事实中猜测出一个结论,然后对这个结论的正确性加以证明确认 数学归纳法就是归纳推理的一种典型例子。 按照所选事例的广泛性,归纳推理可分为: 完全归纳推理和不完全归纳推理; 按照推理所使用的方法可分为: 枚举归纳推理、类比归纳推理、统计归纳推理和差异归纳推理等。,第四章 确定性推理 4.1概述,2020/
4、8/15,8,默认推理,在知识不完全的倩况下,假设某些条件已经具备所进行的推理,因此也称为缺省推理。 在推理过程中如果发现原先的假设不正确,就撤销原来的假设以及由此假设所推出的所有结论。 重新按新情况进行推理。 解决了在一个不完备的知识集中进行推理的问题。,第四章 确定性推理 4.1概述,2020/8/15,9,推理过程的单调性,按照推理过程所得到的结论是否越来越接近日标,推理可分为单调推理与非单调推理。 单调推理: 在推理过程中,每当使用新的知识后,所得到的结论会越来越接近于目标 不会出现反复情况,即不会由于新知识的加入否定了前面推出的结论。 非单调推理: 在推理过程中,当某些新知识加入后,
5、会否定原来推出的结论。 非单调推理往往是在知识不完全的情况下发生的。,第四章 确定性推理 4.1概述,2020/8/15,10,推理控制策略,推理的控制策略是在推理过程中采用的、解决如何使用领域知识使推理过程尽快达到目标的策略。,第四章 确定性推理 4.1概述,2020/8/15,11,推理控制策略分类,智能系统的推理过程一般表现为一种搜索过程,因此,推理的控制策略又可分为推理策略和搜索策略。 推理策略主要解决推理方向、冲突消解等问题。 搜索策略主要解决推理线路、推理效果、推理效率等问题。,第四章 确定性推理 4.1概述,2020/8/15,12,推理方向,推理方向确定推理过程是从初始证据开始
6、到目标,还是从目标开始到初始证据。按照对推理方向的控制,推理可分为正向推理、逆向推理、混合推理及双向推理四种情况。,第四章 确定性推理 4.1概述,2020/8/15,13,正向推理,正向推理是一种从已知事实出发、正向使用推理规则的推理方式,亦称为数据驱动推理。 基本思想是: 用户需要事先提供一组初始证据,并将其放入综合数据库。 推理机根据综合数据库中的已有事实,到知识库中寻找当前可用知识,形成一个当前可用知识集。 按照冲突消解策略,从该知识集中选择一条知识进行推理,并将新推出的事实加入综合数据库,作为后面继续推理时可用的巳知事实, 重复这一过程,直到求出所需要的解或者知识库中再无可用知识为止
7、,第四章 确定性推理 4.1概述,2020/8/15,14,逆向推理,逆向推理是一种从以某个假设目标作为出发点的推理方法,亦称为目标驱动推理 基本思想是: 将要求证的目标(称为假设)构成一个假设集。 取一个假设对其进行验证, 若在综合数据库里,则假设成立 若能被用户认定为事实,则假设成立,并放入综合数据库 若可由知识库中的一个或多个知识导出,则这些知识构成可用知识集。按照冲突消解策略,从该知识集中选择一条知识,将其前提中的所有子条件作为新的假设加入假设集。 重复这一过程,直到假设集为空或假设集非空但可用知识集空为止,第四章 确定性推理 4.1概述,2020/8/15,15,混合推理,正向推理和
8、逆向推理都有各自的优缺点。当问题较复杂时,单独使用其中哪一种,都会影响到推理效率。 为了取长补短可将它们结合起来使用。 这种把正向推理和逆向推理结合起来所进行的推理称为混合推理。,第四章 确定性推理 4.1概述,2020/8/15,16,混合推理的实现方法,混合推理可有多种具体的实现方法 先正向推理,后逆向推理的方法 先逆向推理,后正向推理的方法 采用随机选择正向和逆向推理的方法(双向混合推理),第四章 确定性推理 4.1概述,2020/8/15,17,混合推理的适用场合,已知事实不够充分。 由正向推理推出的结论可信度不高 希望得出更多的结论 希望从正反两个方向同时进行推理,第四章 确定性推理
9、 4.1概述,2020/8/15,18,冲突消解策略,冲突消解策略是指当推理过程有多条知识可用时,如何从这多条可用知识中选出一条最佳知识用于推理的策略。 冲突消解的基本思想是对可用知识进行排序。 常用的冲突消解策略有: 特殊知识优先 新鲜知识优先 差异性大的知识优先 领域特点知识优先 上下文关系知识优先 前提条件少的知识优先,第四章 确定性推理 4.1概述,2020/8/15,19,自然演绎推理,从一组己知为真的事实出发,直接运用经典逻辑中的推理规则推出结论的过程称为自然演绎推理。 在自然演绎推理中,需要避免两类错误: 肯定后件的错误和否定前件的错误。 优点: 定理证明过程自然,易于理解,有丰
10、富的推理规则 主要缺点: 容易产生知识爆炸,推理过程中得到的中间结论一般按指数规律递增,对于复杂问题的推理不利,甚至难以实现。 因此,提出了归结演绎推理,第四章 确定性推理 4.2自然演绎推理,2020/8/15,20,归结演绎推理,归结演绎推理是一种基于归结原理的推理方法。 归结原理亦称消解原理,是鲁宾逊1965年提出的 归结演绎推理实际上是一种“反正法”,基本思想: 推理就是要对前提P和结论Q,证明P Q永真。 这就要证明P Q在任何一个非空的个体域上都是永真的。这将是非常困难的,甚至是不可实现的。 而用反证法,只要能够证明(P Q)是不可满足的。,第四章 确定性推理 4.3归结演绎推理,
11、2020/8/15,21,子句和子句集,原子谓词公式及其否定都称为文字 文字的析取构成的公式称为子句 不包含任何文字的子句称为空了句 空子句不包含任何文字,因此,不能被任何指派所满足 所以空子句是不可满足的 子句集中的子句之间是合取关系 含空子句的子句集也就一定是不可满足的。,第四章 确定性推理 4.3归结演绎推理,2020/8/15,22,谓词公式转化为子句集,消去蕴涵符号: PQ取代PQ 减少否定符号的管辖域 对变量标准化 消去存在量词 化为前束形 化为合取范式: 如:P(PQ)(PQ) 消去全称量词 获得子句集 更换变量名,第四章 确定性推理 4.3归结演绎推理,2020/8/15,23
12、,化子句集例,例:(z) (x)(y)(P(x) Q(x) R(y) U(z) 1, 消蕴涵符 理论根据:a b = a b (z) (x)(y)(P(x) Q(x) R(y) U(z) 2, 移动否定符 理论根据:(a b) = a b (a b) = a b (x)P(x)=(x)P(x) (x)P(x)=(x)P(x) (z) (x)(y)(P(x) Q(x) R(y) U(z),第四章 确定性推理 4.3归结演绎推理,2020/8/15,24,化子句集例(续1),3, 变量标准化 即:对于不同的约束,对应于不同的变量 (x)A(x) (x)B(x) = (x)A(x) (y)B(y)
13、4, 量词左移 (x)A(x) (y)B(y) = (x) (y) A(x) B(y) 5, 消存在量词 (skolem化) 原则:对于一个受存在量词约束的变量,如果他不受全程量词约束,则该变量用一个常量代替,如果他受全程量词约束,则该变量用一个函数代替。 (z) (x)(y)(P(x) Q(x) R(y) U(z) = (x) (P(x) Q(x) R(f(x) U(a),第四章 确定性推理 4.3归结演绎推理,2020/8/15,25,化子句集例(续2),6, 化为合取范式 即(ab) (cd) (ef)的形式 (x)(P(x) Q(x) R(f(x)U(a) = (x)(P(x) Q(x
14、) R(f(x)U(a) = (x)P(x) R(f(x)U(a) Q(x) R(f(x)U(a) 7, 隐去全程量词 P(x) R(f(x)U(a) Q(x) R(f(x)U(a),第四章 确定性推理 4.3归结演绎推理,2020/8/15,26,化子句集例(续3),8, 表示为子句集 P(x) R(f(x)U(a), Q(x) R(f(x)U(a) 9, 变量标准化(变量换名) P(x1) R(f(x1)U(a), Q(x2) R(f(x2)U(a),第四章 确定性推理 4.3归结演绎推理,2020/8/15,27,归结(消解)原理基本思想,首先把欲证明问题的结论否定,并加入子句集,得到一
15、个扩充的子句集S。 检验子句集S是否含有空子句 若不含空子句,则继续使用归结法,在子句集中选择合适的子句进行归结 直至导出空子句或不能继续归结为止。,第四章 确定性推理 4.3归结演绎推理,2020/8/15,28,归结原理分类,鲁宾逊归结原理可分为: 命题逻辑归结原理 谓词逻辑归结原理,第四章 确定性推理 4.3归结演绎推理,2020/8/15,29,归结式,归结推理的核心是求两个子句的归结式 若P是原子谓词公式,则称P与P为互补文字 设C1和C2是子句集中的任意两个子句 如果C1中的文字L1与C2中的文字L2互补 那么可从C1和C2中分别消去L1和L2 并将C1和C2中余下的部分按析取关系构成一个新的子句C12, 则称这一过程为归结, 称C12为C1和C2的归结式,C1和C2为C12的亲本子句。,第四章 确定性推理 4.3归结演绎推理,2020/8/15,30,消解过程举例,E2 E1 (前提) E2 E3 (前提) (消解式) E1 E3 (结论),第四章 确定性推理 4.2归结