基于产生式规则的机器推理.ppt

第6章基于产生式规则的机器推理 2020 4 8 1 2020 4 8 2 第6章基于产生式规则的机器推理 6 1产生式规则6 2产生式系统 2020 4 8 3 6 1产生式规则 6 1 1产生式规则6 1 2基于产生式规则的推理模式 2020 4 8 4 6 1 1产生式规则 1 产生式产生式 Production 一词从波斯特机中借用来的 波斯特机是一种自动机 它是根据串替换规则提出的一种计算模型 其中的每一条规则就叫一个产生式 也称产生式规则 简称规则 这里产生式就是前面讨论过的操作 二阶梵塔问题 猴子摘香蕉问题等 逻辑蕴含式 推理规则以及各种关系 包含经验性联想 的一种逻辑抽象 2020 4 8 5 6 1 1产生式规则 2 产生式的一般形式为 前件 后件 情况 行为 前件是前提 规则的执行条件 后件是结论或动作 规则体 产生式规则的语义 如果前提满足 则可得结论或者执行相应的动作 即后件由前件触发 一个产生式规则就是一条知识 用产生式不仅可以进行推理 也可以实现操作 2020 4 8 6 6 1 1产生式规则 3 产生式规则例子如果银行存款利率下调 那么股票价格上涨 如果炉温超过上限 则立即关闭风门 如果发烧 呕吐并且出现黄疸 那么得了肝炎 0 7 如果键盘突然失灵 且屏幕上出现怪字符 则是病毒发作 2020 4 8 7 6 1 1产生式规则 例 例三个聪明人问题 古代有个国王想知道他的三个大臣中谁最聪明 就在他们每个人前额上都画了一个点 他们都能看到别人点的颜色 但看不到自己点的颜色 国王说 你们中间至少有一个人的点是白色的 于是重复地问他们 谁知道自己点的颜色 三位大臣们头两次都回答说不知道 题目要求证明下一次他们全都会说 知道 并且所有的点都是白色 2020 4 8 8 6 1 1产生式规则 例 分析 这类问题的特点是有有限个受试者 每个人对问题都只有部分了解 无法直接求解 但在推理过程中每个人又可以从别人那里获得新的知识 重新进行推理 可以用产生式来表达推理过程中所用到的各种知识 2020 4 8 9 6 1 1产生式规则 例 状态集合表示 用x1 x2 x3表示三个人点的颜色 1表示白色 0表示非白色 X x1 x2 x3 表示颜色分布状态 全部可能的状态集合 可能界PW0 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 实际给定的状态为现实界X0 x10 x20 x30 用排除法找到X0 2020 4 8 10 6 1 1产生式规则 例 排除过程 第一次 大臣只知道至少有一个人是白点 排除X0 0 0 0 状态 这时如果有人看到两个非白点 根据排除的状态可推知自己是白点 第二次大臣根据没有一个人知道自己点颜色的事实推知至少两人为白点 排除 0 0 1 0 1 0 1 0 0 状态 这时如果有人看到一个非白点 根据排除后得到的状态可推知自己的点是白的 第三次 大臣们根据仍无人知道自己点颜色的新事实推知没有一个非白点出现 即X0 1 1 1 于是三人都知道自己点的颜色是白的 2020 4 8 11 6 1 1产生式规则 例 引入中介状态并定义下述符号 Si i大臣看到的非白点数 Wi i大臣猜出自己点的颜色否 如果他宣布已知道自己点的颜色 为1 否则为0 n X0中白点的个数 2020 4 8 12 6 1 1产生式规则 例 1 n 1 X0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 2 n 1 Si 2 Wi 1 i 1 2 3 下同 3 i Wi 1 n 1 n 1 4 n 1 i Wi 1 5 i Wi 0 n 1 n 2 6 n 2 X0 0 1 1 1 0 1 1 1 0 1 1 1 7 n 2 Si 1 Wi 1 8 i Wi 1 n 2 n 2 9 n 2 i Wi 1 10 i Wi 0 n 2 n 3 11 n 3 X0 1 1 1 12 n 3 i Wi 1 2020 4 8 13 6 1 1产生式规则 例 上述结果可以推广到更一般的情况 设有m个大臣 国王说至少有l个人的点是白色的 则有下述产生式 1 n l X0 x x中的白点数 l 2 n l Si 2 Wi 1 i 1 2 m 下同 3 i Wi 1 n l n l 4 n l i Wi l 5 i Wi 0 n l l n l 1 6 i Wi 0 n l l m 1 n m 2020 4 8 14 6 1 2基于产生式规则的推理模式 A BAB把有前提的操作和逻辑推理统称为推理 产生式系统中的推理是更广义的推理 2020 4 8 15 6 2产生式系统 6 2 1系统结构6 2 2运行过程6 2 3控制策略常用算法6 2 4程序实现 6 2 5产生式系统与问题求解 2020 4 8 16 6 2 1系统结构 1 产生式系统结构 产生式规则库 推理机 全局数据库 2020 4 8 17 6 2 1系统结构 2 组成产生式规则库 作用在全局数据库上的一些规则的集合 每条规则都有一定的条件 若全局数据库中内容满足这些条件可调用这条规则 一般可形成一个称为推理网络的结构图 对应过程性知识 推理机 负责产生式规则的前提条件测试或匹配 规则的调度和选取 规则体的解释和执行 即推理机实施推理 并对推理进行控制 它也是规则的解释程序 对应控制性知识 全局数据库 人工智能系统的数据结构中心 是一个动态数据结构 用来存放初始事实数据 中间结果和最后结果 对应叙述性知识 2020 4 8 18 6 2 1系统结构 3 例旅行推销员问题 求从A城出发 经过其他城市一次且仅一次 最后回到A城的最小费用路线 城市之间的交通费用标在相应的联线上 建立产生式系统 2020 4 8 19 6 2 1系统结构 4 1 全局数据库 已访问过的城镇名称序列 约束条件是除城镇A之外其他名称不得在序列中重复出现 只有所有的名称都在序列中出现后 城镇A才能重复出现 2 规则集 如下表所示 3 推理 A AB ABE 4 终止条件 序列始于A 终止于A 其中包含其他所有城镇一次 且费用最少 5 各种搜索策略选择规则 如广度优先搜索 最好优先搜索等 R2 R5 2020 4 8 20 6 2 1系统结构 5 规则集 2020 4 8 21 6 2 1系统结构 6 与一般分级组织的计算机软件相比具有特点 全局数据库的内容可以为所有规则所访问 没有任何部分是专为某一规则建立的 这种特性便于模仿智能行为中的强数据驱动 规则本身不调用其他规则 规则之间的联系必须通过全局数据库联系 全局数据库 规则和推理机之间相对独立 这种积木式结构便于整个系统增加和修改知识 2020 4 8 22 6 2 2产生式系统的运行过程 1 推理机一次运行过程 2020 4 8 23 6 2 2产生式系统的运行过程 2 产生式系统运行过程实际的产生式系统 目标条件往往要经过多步推理才能满足或者证明问题无解 产生式系统的运行过程就是推理机不断的运用规则库中的规则 作用于动态数据库 不断进行推理并不断检测目标条件是否被满足的过程 产生式系统运行过程是从初始事实出发 寻求到达目标条件的通路的过程 所以也是一个搜索的过程 2020 4 8 24 6 2 3控制策略与常用算法 1 推理方式正向推理 从初始事实数据出发 正向使用规则进行推理 朝目标方向前进 又称为前向推理 正向链 数据驱动的推理 反向推理 从目标出发 反向使用规则进行推理 朝初始事实或数据方向前进 又称反向推理 反向链 目标驱动的推理 2020 4 8 25 6 2 3控制策略与常用算法 2 正向推理算法一步1将初始事实 数据置入动态数据库 步2用动态数据库中的事实匹配目标条件 若目标条件满足 推理成功 结束 步3用规则库中各规则的前提匹配动态数据库中的事实 将匹配成功的规则组成待用规则集 步4若待用规则集为空 则运行失败 退出 步5将待用规则集中各规则的结论加入动态数据库 或者执行其动作 转步2 2020 4 8 26 6 2 3控制策略与常用算法 3 若把动态数据库的每一个状态作为一个节点的话 则上述推理过程就是一个从初始状态到目标状态的状态图搜索过程 如果把动态数据库中的每一个事实 数据作为一个节点的话 则上述推理过程就是一个自底向上的与或树搜索过程 2020 4 8 27 6 2 3控制策略与常用算法 4 反向推理算法步1将初始事实 数据置入动态数据库 将目标条件置入目标链 步2若目标链为空 则推理成功 结束 步3取出目标链中第一个目标 用动态数据库中的事实同其匹配 若匹配成功 转步2 步4用规则集中的各规则的结论同该目标匹配 若匹配成功 则将第一个匹配成功且未用过的规则的前提作为新的目标 并取代原来的父目标加入目标链 转步3 步5若该目标是初始目标 则推理失败 退出 步6将该目标的父目标移回目标链 取代该目标及其兄弟目标 转步3 2020 4 8 28 6 2 3控制策略与常用算法 5 在产生式系统中 从前提到结论的产生式规则通常也是一棵与或树 合取 与节点 一个产生式的前提包含了几个事实 那么它的结论对应这些事实的合取 析取 或节点 一个结论可以由多个产生式得到 则这个结论对应这些产生式的析取 每个产生式系统都隐含着许多这样的与或树 2020 4 8 29 6 2 3控制策略与常用算法 6 事实 中介事实B C D 产生式规则P1 P2 P3 P4 P5 结论 2020 4 8 30 6 2 3控制策略与常用算法 7 例6 1 动物分类问题的产生式系统描述及求解 规则 r1 IF该动物有毛发THEN该动物是哺乳动物r2 IF该动物有奶THEN该动物是哺乳动物r3 IF该动物有羽毛THEN该动物是鸟r4 IF该动物会飞AND会下蛋THEN该动物是鸟r5 IF该动物吃肉THEN该动物是食肉动物r6 IF该动物有犬齿AND有爪AND眼盯前方THEN该动物是食肉动物动物 2020 4 8 31 6 2 3控制策略与常用算法 8 r7 IF该动物是哺乳动物AND有蹄THEN该动物是有蹄类动物r8 IF该动物是哺乳动物AND是嚼反刍动物THEN该动物是有蹄动物r9 IF该动物是哺乳动物AND是食肉动物AND是黄褐色AND身上有暗斑点THEN该动物是金钱豹r10 IF该动物是哺乳动物AND是食肉动物AND是黄褐色AND身上有黑色条纹THEN该动物是虎 2020 4 8 32 6 2 3控制策略与常用算法 9 r11 IF该动物是有蹄类动物AND有长脖子AND有长腿AND身上有暗斑点THEN该动物是长颈鹿r12 IF该动物有蹄类动物AND身上有黑色条纹THEN该动物是斑马r13 IF该动物是鸟AND有长脖子AND有长腿AND不会飞AND有黑白二色THEN该动物是鸵鸟 2020 4 8 33 6 2 3控制策略与常用算法 10 r14 IF该动物是鸟AND会游泳AND不会飞AND有黑白二色THEN该动物是企鹅r15 IF该动物是鸟AND善飞AND不怕风浪THEN该动物是海燕 2020 4 8 34 2020 4 8 35 6 2 3控制策略与常用算法 12 初始事实 f1 某动物有毛发 f2 吃肉 f3 黄褐色 f4 有黑色条纹目标条件为 该动物为什么 2020 4 8 36 6 2 3控制策略与常用算法 13 2020 4 8 37 6 2 3控制策略与常用算法 14 例6 2使用反向推理算法 2020 4 8 38 6 2 3控制策略与常用算法 15 3冲突消解策略给定一组事实之后可用匹配技术寻找可用产生式 其基本思想是将已知事实代入产生式的前件 若前件为真 则该产生式是可用的 提高匹配效率的方法索引匹配 为状态建立可用产生式索引表 减少可用产生式搜索范围 分层匹配 将产生式分成若干层或组 按一定特征进行分层搜索 过滤匹配 边匹配边按某些附加特征或参数对可用产生式进行精选 2020 4 8 39 6 2 3控制策略与常用算法 2 正向推理算法二步1将初始事实 数据置入动态数据库 步2用动态数据库中的事实匹配目标条件 若目标条件满足 推理成功 结束 步3用规则库中各规则的前提匹配动态数据库中的事实 将匹配成功的规则组成待用规则集 步4若待用规则集为空 则运行失败 退出 步5用某种策略 从待用规则集中选取一条规则 将其结论加入动态数据库 或者执行其动作 撤消待用规则集 转步2 2020 4 8 40 6 2 3控制策略与常用算法 16 如果一组事实可以同时使几个产生式前提为真 常用以下方法进行选择 冲突消解策略 优先级法 优先级高者优先 可信度法 可信度高者优先 自然顺序法采用优先级 可信度 代价等冲突消解策略 就是启发式搜索 采用自然顺序法 就是一种盲目碰撞搜索 产生式系统的推理方式 搜索策略及冲突消解策略等成为推理控制策略 产生式系统的控制策略体现在推理机的算法描述中 2020 4 8 41 6 2 4程序实现 产生式规则的程序语言实现规则库的程序实现动态数据库的程序实现推理机的程序实现 2020 4 8 42 6 2 5产生式系统与问题求解 1 如果用正向推理来解决规划性问题 在算法中需要增加以下功能 记录动态数据库状态变化的