人工智能推理技术.ppt

第7章 基本的推理技术 推理技术概述基于规则的演绎推理正向演绎推理逆向演绎推理双向演绎推理不确定性推理概率推理 人工智能是用计算机来模拟人的智能 就是用能在计算机上实现的技术和方法来模拟人的思维规律和过程 1 在确定知识表达方法后 就可以把知识表示出来并存储到计算机中 2 然后 利用知识进行推理以求得问题的解 利用知识进行推理是知识利用的基础 各种人工智能应用领域如专家系统 智能机器人 模式识别 自然语言理解等都是利用知识进行广义问题求解的智能系统 7 1推理技术概述 1 推理的概念与类型 推理是人类求解问题的主要思维方法 所谓推理就是按照某种策略从已有事实和知识推出结论的过程 推理是由程序实现的 称为推理机 人类的智能活动有多种思维方式 人工智能作为对人类智能的模拟 相应地也有多种推理方式 1 演绎推理 归纳推理 默认推理 1 演绎推理 演绎推理是从全称判断推出特称判断或单称判断的过程 即从一般到个别的推理 最常用的形式是三段论法 例如 1 所有的推理系统都是智能系统 2 专家系统是推理系统 3 所以 专家系统是智能系统 2 归纳推理 是从足够多的事例中归纳出一般性结论的推理过程 是一种从个别到一般的推理过程 3 默认推理 默认推理又称缺省推理 它是在知识不完全的情况下假设某些条件已经具备所进行的推理 2 确定性推理 不确定性推理 如果按推理时所用的知识的确定性来分 推理可分为确定性推理与不确定性推理 1 确定性推理 精确推理 如果在推理中所用的知识都是精确的 即可以把知识表示成必然的因果关系 然后进行逻辑推理 推理的结论或者为真 或者为假 这种推理就称为确定性推理 如归结反演 基于规则的演绎系统等 2 不确定性推理 不精确推理 在人类知识中 有相当一部分属于人们的主观判断 是不精确的和含糊的 由这些知识归纳出来的推理规则往往是不确定的 基于这种不确定的推理规则进行推理 形成的结论也是不确定的 这种推理称为不确定推理 在专家系统中主要使用的方法 3 单调推理 非单调推理 如果按推理过程中推出的结论是否单调增加 或者说推出的结论是否越来越接近最终目标来划分 推理又可分为单调推理与非单调推理 1 单调推理 是指在推理过程中随着推理的向前推进及新知识的加入 推出的结论呈单调增加的趋势 并且越来越接近最终目标 演绎推理是单调推理 2 非单调推理 是指在推理过程中随着推理的向前推进及新知识的加入 不仅没有加强已推出的结论 反而要否定它 使得推理退回到前面的某一步 重新开始 一般是在知识不完全的情况下进行的 4 启发式推理 非启发式推理 如果按推理中是否运用与问题有关的启发性知识 推理可分为启发式推理和非启发式推理 1 启发式推理 如果在推理过程中 运用与问题有关的启发性知识 如解决问题的策略 技巧及经验等 以加快推理过程 提高搜索效率 这种推理过程称为启发式推理 如A A 等算法 2 非启发式推理 如果在推理过程中 不运用启发性知识 只按照一般的控制逻辑进行推理 这种推理过程称为非启发式推理 推理效率较低 容易出现 组合爆炸 问题 推理的控制策略 主要是指推理方向的选择 推理时所用的搜索策略及冲突解决策略等 一般推理的控制策略与知识表达方法有关 产生式系统 1 推理方向 用于确定推理的驱动方式 分为正向推理 由已知事实出发 反向推理 以某个假设目标作为出发点 和正反向混合推理 正向推理和反向推理相结合 系统组成 知识库 KB 初始事实和中间结果的数据库 DB 推理机2 搜索策略 推理时要反复用到知识库中的规则 而知识库中的规则又很多 这样就存在着如何在知识库中寻找可用规则的问题 代价小 解好 可以采用各种搜索策略有效地控制规则的选取 3 冲突解决策略 在推理过程中 系统要不断地用数据库中的事实与知识库中的规则进行匹配 当有一个以上规则的条件部分和当前数据库相匹配时 就需要有一种策略来决定首先使用哪一条规则 这就是冲突解决策略 冲突解决策略实际上就是确定规则的启用顺序 1 专一性排序 条件部分更具体的规则 2 规则排序 规则编排顺序 3 数据排序 所有条件按优先级次序编排起来 4 就近排序 最近使用的规则优先 5 上下文限制 在某种上下文条件下 6 按匹配度排序 计算这两个模式的相似程度 7 按条件个数排序 条件少的优先 7 2基于规则的演绎推理 许多AI系统中所用到的知识一般是由蕴含式直接表示的 但在归结反演中 必须首先将它们转化为子句的形式 所以这种推理是比较低效的 基于规则的演绎推理则是直接的推理方法 它把有关问题的知识和信息划分为规则与事实两种类型 规则由包含蕴含形式的表达式表示 事实由无蕴含形式的表达式表示 并画出相应的与或图 然后通过规则进行演绎推理 可分为正向 反向和正反向演绎推理 在正向推理中 作为F规则用的蕴含式对事实的总数据库进行操作运算 直至得到该目标公式的一个终止条件为止 在反向推理中 作为B规则用的蕴含式对目标的总数据库进行操作运算 直至得到包含这些事实的一个终止条件为止 在双向推理中 分别从两个方向应用不同的规则 F和B 进行操作运算 7 2 1正向演绎推理 正向演绎推理属于正向推理 它是从已知事实出发 反复尝试所有可利用的规则 F规则 进行演绎推理 直到得到某个目标公式的一个终止条件为止 1 事实表达式及其与或图表示正向演绎要求事实用不包含蕴含符号 的与或形表示 把一个表达式转化为标准的与或形的步骤如下 1 利用等价式P Q与 P Q消去蕴含符 2 把否定符号 移到每个谓词符号的前面 3 变量标准化 即重新命名变量 使不同量词约束的变量有不同的名字 4 引入Skolem函数消去存在量词 5 将公式化为前束形 6 略去全称量词 默认变量是全称量词量化的 7 重新命名变量 使同一变量不出现在不同的主要合取式中 例如 有如下的表达式 x y Q y x R y P y S x y 可将其转化为下面标准的与或形 Q z A R y P y S A y 于是 它的标准与或形可用一棵与或树表示出来 在与或图中 节点表示事实表达式及其子表达式 根节点表示整个表达式 叶节点表示其中的单文字 规定 对于一个表示析取表达式 E1 E2 En 的节点 用一个n连接符 含半圆的弧 与连接它的n个子表达式节点相连 对于一个表示合取表达式 E1 E2 En 的节点 用n个1连接符与连接它的n个子表达式节点相连 重要性质 就是由变换表达式得到的一组子句 可以从与或图中读出 每个子句相当于与或图的一个解图 每个子句是由叶节点组合成的公式 上例的3个子句是 Q z A S A y R y S A y P y 这三个子句正是原表达式化成的子句集 因此 与或树可以看成是一组子句的一个简洁的表达式 2 F规则的表示形式 基于规则的正向推理中 要求F规则具有以下形式 L W 具体要求如下 L是单文字 W是任意的与或形表达式 L和W中的所有变量都是全称量词量化的 默认的全称量词作用于整个蕴含式 各条规则的变量各不相同 而且规则中的变量与事实表达式中的变量也不相同 将F规则的左部限制为单文字 是因为与或图的叶节点都是单文字 这样就可用F规则的左部与叶节点进行匹配 大大简化了规则的应用过程 如果所给知识的表示形式不是所要求的形式 则可用如下步骤将其变换成标准形式 1 暂时消去蕴含符号 例如公式 x y z P x y z u Q x u 消去蕴含符号 变为 x y z P x y z u Q x u 2 把否定号 移到每个谓词的前面 可变为 x y z P x y z u Q x u 3 引入skolem函数消去存在量词 消去存在量词后 为 x y P x y f x y u Q x u 4 将公式化为前束式 并略去全称量词 可变为 P x y f x y Q x u 5 恢复为蕴含式 利用等价关系 P Q与P Q将上式变为P x y f x y Q x u 3 目标公式的表示形式要求目标公式用文字的析取式 子句 表示 否则就要化为子句形式 4 推理过程应用F规则作用于表示事实的与或图 改变与或图的结构 从而产生新事实 直至推出了目标公式 过程为 首先用与或图把已知事实表示出来 用F规则的左部和与或图的叶节点进行匹配 并将匹配成功的F规则结论加入到与或图中 即利用F规则转换与或图 重复第 2 步 直到产生一个含有以目标节点作为终止节点的解图为止 当一个目标文字和与或图中的一个文字匹配时 可以将表示该目标文字的节点 目标节点 通过匹配连接到与或图中相应的文字节点上 当演绎产生的与或图包括一个目标节点上结束的解图时 推理便成功结束 1 命题逻辑的情况 应用规则的匹配过程比较简单 设已知事实的与或形表达式为 P Q R S T U 规则为S X Y Z把已知事实用与或图表示 图中有一个叶节点是文字S 它正好与规则的前项的文字S完全匹配 由此可直接用这条规则对与或图进行变换 即把规则后项的与或形公式用与或图表示后添加到已知事实的与或图上 并用一个匹配弧连接起来 规则匹配后演绎的结果如下图所示 图中匹配弧后面是规则部分 例 事实表达式 A B 规则集合 A C D B E G 目标公式 C G应用完这两条规则后 得到的与或图如图所示 其中有一个解图满足目标公式 C G 所建立的结束条件 2 谓词逻辑的情况 需要讨论对含有变量的目标公式的处理 匹配问题 对具有量词量化变量的目标公式来说 化简时要使用Skolem化过程的对偶形式 即目标中属于存在量词辖域内的全称量化变量要用存在量化变量的Skolem函数来替代 经过Skolem化的公式只剩下存在量词 然后对析取元作变量改名 最后再把存在量词省略掉 例如 设目标公式为 y x P x y Q x y 用函数消去全称量词后有 y P f y y Q f y y 然后进行变量改名 使每个析取元具有不同的变量符号 于是有 y P f y y y1 Q f y1 y1 最后省去存在量词 P f y y Q f y1 y1 以后目标公式中的变量都假定受存在量词的约束 下面举例说明应用一条规则L W对与或图进行变换的过程 设与或图中有一个端节点的文字L 和L可合一 mgu是u 则这条规则可应用 这时用匹配弧连接的后裔节点是L 它是规则后项Wu对应的与或图表示的根节点 在匹配弧上标记有u 表示用u置换后可与规则匹配 例 事实与或形表示P x y Q x A R B y 规则蕴涵式P A B S A X B 下图是应用规则变换后得到的与或图 它有两个解图 对应的两个子句是S A X B Q A A S A X B R B B 它们正是事实和规则公式组成的子句集对文字P进行归结时得到的归结式 图7 7 应用一条含有变量的规则后得到的与或图 当一个与或图含有多个的匹配弧 应用了多条规则时 任一解图可能含多个匹配弧 对应的置换是u1 u2 un 故在列写解图的子句集合时 只考虑具有一致的匹配弧置换的那些解图 一致解图 一个一致解图表示的子句是对得到的文字析取式应用一个合一复合的置换之后所得到的子句 设有一个置换集U u1 u2 un 其中ui ti1 vi1 ti2 vi2 tim i vim i 是置换对集合 t是项 v是变量 根据这个置换集 定义变量集和项集 U1 v11 v1m 1 v21 v2m 2 vn1 vnm n 由每个置换ui中的变量vi构成 U2 t11 t1m 1 t21 t2m 2 tn1 tnm n 由每个置换ui中的项ti构成 则置换U一致的充要条件是U1和U2是可合一的 而U的合一复合u mgu U1 U2 可以验证对一个置换集合求合一复合的运算是可结合和可交换的 求置换的合成是不可交换的 因此一个解图对应的合一复合不依赖于构造这个解图时所产生的匹配弧的次序 例 设事实和规则描述如下 Fidobarksandbites orFidoisnotadog F DOG FIDO BARKS FIDO BITES FIDO Allterriersaredogs R1 x DOG x TERRIER x 原规则的逆否 Anyonewhobarksisnoisy R2 y BARKS y NOISY y 要证明的目标是Thereexistssomeonewhoisnotaterriersorwhoisnoisy 目标公式 z TERRIER z NOISY z 上图给出了演绎得到的与或图 图中结束在目标节点的一个一致解图 有置换集合 FIDO x FIDO y FIDO z 它的合一复合是u FIDO x FIDO y FIDO z 根据这个一致解图 目标公式是事实和规则的逻辑推论 因而得到了证明 如果用这个合一复合u应用于这个目标公式 可得 TERRIER FIDO NOISY FIDO 它是已证目标公式的例 可作为一个回答语句 7 2 2反向演绎推理 它从目标表达式出发 通过反向运用规则进行演绎推理 直到得到包含已知事实的终止条件为止 1 目标表达式及其与或图表示首先 要将目标表达式转化为无蕴涵符 的与或形式 并用与或图表示 要采用正向演绎中对事实表达式的变换的对偶形式 即skolem化全称量词量化的变量 略去存在量词 与正向演绎中对目标表达式的处理一致 例如 有如下的目标表达式 y x P x Q x y R x S y 可转化为如下与或形式 P f y Q f y y R f y S y 为使析取式具有不同的变量名 重命名变量 得 P f z Q f y y R f y S y 与或形式的目标表达式可以用与或图表示 但其表示方式与正向演绎中事实表达式的与或图不同 它的n连接符用来把具有合取关系的子表达式连接起来 而在正向演绎中是把事实表达式具有析取关系的子表达式连接起来 上例的目标表达式的与或图如下图所示 图中根节点为目标表达式 称为目标节点 叶节点表示单个文字 若把叶节点用它们之间的合取及析取关系连接起来 就可得到原目标表达式的三个子目标 P f z Q f y y R f y Q f y y S y 可以看出 子目标是文字的合取式 其中的变量是存在量词量化的 2 B规则的表示形式反向演绎推理中的规则称为B规则 其表示形式为W L 其中W为任一与或形式表达式 L为单一文字 为了方便匹配 如果规则不符合这一要求 则要变换成这种形式 如规则W L1 L2 可以转换为两个B规则 即W L1 W L2 规则中应Skolem化存在量词量化的变量 并略去全称量词 3 已知事实的表示形式在反向演绎推理中 要求已知事实表达式是文字的合取式 可表示为文字的集合 对任意事实表达式 应当用Skolem函数代替事实表达式中存在量词量化的变量 并略去全称量词量化的变量 将表达式转化为标准的文字的合取式 4 推理过程 具体过程如下 用与或图将目标表达式表示出来 在目标与或图中 如果有一个文字L 能够与L合一 则可应用B规则W L 并将L 节点通过一个标有L和L 的最简单合一者的匹配弧与L相连 再将匹配成功的B规则加入与或图中 一条规则可用多次 每次应使用不同的变量 当一个事实文字和与或图中的一个文字可以合一时 可将该事实文字通过匹配弧连接到与或图中相应的文字上 匹配弧应标明两个文字的最简单的合一者 重复进行第2步 直到与或图中包括一个结束在事实节点上的一致解图 该解图的合一复合作用于目标表达式就是解答语句 例 设有事实 F1 DOG FIDO FIDO是一只狗F2 BARKS FIDO FIDO不叫F3 WAGS TAIL FIDO FIDO摆尾巴F4 MEOWS MYRTLE MYRTLE喵喵叫规则如下 R1 WAGS TAIL x1 DOG x1 FRIENDLY x1 摆尾巴的狗是友好的R2 FRIENDLY x2 BARKS x2 AFRAID y2 x2 友好且不叫的是不令对方害怕的R3 DOG x3 ANIMAL x3 狗是动物R4 CAT x4 ANIMAL x4 猫是动物R5 MEOWS x5 CAT x5 喵喵叫的是猫问题是 是否存在一只猫和一条狗 这只猫不怕这条狗 该问题的目标公式是 x y CAT x DOG y AFRAID x y 求解该问题的过程如下图 从上图可看出 最后得到的是一个一致解图 图中共有8条匹配弧 每条匹配弧上都标有置换 分别为 x x5 MYRTLE x FIDO y x y2 y x2 FIDO y y x1 FIDO y 和 FIDO y 这些置换的合一复合为 MYRTLE x5 MYRTLE x FIDO y MYRTLE y2 FIDO x2 FIDO x1 将合一复合作用于目标表达式就得到解答语句 CAT MYRTLE DOG FIDO AFRAID MYRTLE FIDO 它表示有一只名叫MYRTLE的猫和一条名叫FIDO的狗 这只猫不怕那条狗 使用条件 正向系统事实表达式是任意形式规则形式为L W或L1 L2 W L为单文字 W为任意形式 目标公式为文字析取形 逆向系统事实表达式是文字合取形规则形式为W L或W L1 L2 L为单文字 W为任意形式 目标公式为任意形式 化简过程 正向系统用skolem函数消去事实表达式中的存在量词 化简的公式受全称量词的约束 对规则的处理同上 用skolem函数 对偶形 消去目标公式中的全称量词 化简的公式受存在量词约束 逆向系统skolem函数 对偶形 消去目标公式中的全称量词 化简的公式受存在量词约束 对规则的处理同下 用skolem函数消去事实表达式中的存在量词 化简的公式受全称量词的约束 7 2 3双向演绎推理 正向演绎推理要求目标表达式是文字的析取式 而反向演绎推理要求事实公式为文字的合取式 为充分发挥正向演绎和反向演绎的优点 克服各自的局限性 可将两种演绎推理相结合 这就是双向演绎推理 在双向演绎推理中 已知事实用与或图表示 目标表达式用另一个与或图表示 这两个与或图分别由正向演绎的F规则和反向演绎的B规则进行操作 并且仍限制F规则的左部为单文字 而B规则的右部为单文字 双向演绎推理分别从正反两个方向进行推理 两个与或图分别扩展 最关键也是最复杂的是如何判断推理是否结束 推理的终止处位于两个与或图分别扩展后的某个交接处 当正反两个方向的与或图对应的叶节点都可合一时 推理就结束 上图说明了双向演绎推理的过程 图中对应的已知事实表达式和目标表达式分别为 Q x A R x S A P f y Q f y y R f y S y 图中 共有3个匹配弧 并标有各自的置换 这些置换是一致的 其合一复合为 f A x A y 在推理过程中 没有使用B规则和F规则 这里主要说明双向推理是如何在交接处终止的 7 3不确定性推理 逻辑推理是一种运用确定性知识进行的精确推理 但是 现实世界中的事物以及事物之间的关系是极其复杂的 在人类知识中 有相当一部分是不精确的 模糊的 因此不精确的推理模型是人工智能和专家系统的一个核心研究问题 实际上 AI系统的智能主要反映在求解不精确性问题的能力上 不确定性推理就是从不确定性初始事实 证据 出发 通过运用不确定性的知识 最终推出具有一定程度的不确定性是合理或者近乎合理的结论的思维过程 一概率方法 1 条件概率 设A和B是某随机试验中的两个事件 如果在事件B发生的条件下考虑事件A发生的概率 就称它为事件A的条件概论 记做P A B 若P B 0 则 2 全概率公式 设事件A1 A2 An满足 两两互不相容 即当i j Ai