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