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

第6章 基于产生式规则的机器推理 *1人工智能 第6章基于产生式规则的机器推理 6.1 产生式规则 6.2 产生式系统 Date2人工智能 6.1 产生式规则 6.1.1 产生式规则 6.1.2 基于产生式规则的推理模式 Date3人工智能 6.1.1 产生式规则（1） n产生式（Production）：从波斯特机中借用来的。波 斯特机是一种自动机，它是根据串替换规则提出的一种 计算模型。其中的每一条规则就叫一个产生式。也称产 生式规则，简称规则。 n产生式描述了事物之间的一种对应关系（包括因果关 系和蕴含关系） n图搜索中的状态转换规则和问题变换规则 n三种遗传操作 n逻辑蕴含式和逻辑等价式 n归结原理 n体育比赛中的规则、国家的法律条文 Date4人工智能 6.1.1 产生式规则（2） n产生式的一般形式为： n前件后件（情况行为、前提结论） n前件是前提，规则的执行条件。 后件是结论或动作，规则体。 n产生式规则的语义：如果前提满足，则可得结 论或者执行相应的动作，即后件由前件触发。 n一个产生式规则就是一条知识，用产生式不仅可以进 行推理，也可以实现操作。 n人工智能中将产生式规则作为一种知识表示形式或方 法 Date5人工智能 6.1.1 产生式规则（例） 例 三个聪明人问题。古代有个国王想知道他的 三个大臣中谁最聪明，就在他们每个人前额上都 画了一个点，他们都能看到别人点的颜色，但看 不到自己点的颜色。国王说，你们中间至少有一 个人的点是白色的。于是重复地问他们：“谁知 道自己点的颜色？”三位大臣们头两次都回答说 不知道。题目要求证明下一次他们全都会说“知 道”，并且所有的点都是白色。 Date6人工智能 6.1.1 产生式规则（例） 分析： 这类问题的特点是有有限个受试者，每个 人对问题都只有部分了解，无法直接求解。但在 推理过程中每个人又可以从别人那里获得新的知 识，重新进行推理。可以用产生式来表达推理过 程中所用到的各种知识。 Date7人工智能 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 。 Date8人工智能 6.1.1 产生式规则（例） 排除过程： n第一次，大臣只知道至少有一个人是白点，排 除X0=(0,0,0)状态。这时如果有人看到两个非白点 ，根据排除的状态可推知自己是白点。 n第二次大臣根据没有一个人知道自己点颜色的 事实推知至少两人为白点。排除(0,0,1)(0,1,0)(1,0,0) 状态。这时如果有人看到一个非白点，根据排除后 得到的状态可推知自己的点是白的。 n第三次，大臣们根据仍无人知道自己点颜色的 新事实推知没有一个非白点出现，即X0=(1,1,1)。 于是三人都知道自己点的颜色是白的。 Date9人工智能 6.1.1 产生式规则（例） 引入中介状态并定义下述符号： Si i大臣看到的非白点数； Wi i大臣猜出自己点的颜色否。如果他宣布已知 道自己点的颜色，为1，否则为0； nX0中白点的个数。 Date10人工智能 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). Date11人工智能 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=l1) ; (6)( i ) (Wi=0) (n=l) (lm-1)= (nm)。 Date12人工智能 产生式系统的知识表示（*） n产生式系统的知识表示方法包括事实的表示和规则的表示 。 n事实的表示： n一个语言变量的值或多个语言变量之间的关系的陈 述句 n三元组表示： n（对象，属性，值）：（wang，age，40） n（关系，对象1，对象2）：（friend，wang ,li ） n规则的表示： n单个规则由前项和后项两部分组成。前项由逻辑联 结词组成各种不同的前提条件，后项表示前提条件为真 时，应采取的操作或所得的结论。如果考虑不精确推理 ，则可附加置信度量值。 Date13人工智能 BNF(巴科斯范式)的产生式规则形式描述及语义 n:= n:=| n:=| n:=AND (AND)|OR(OR) n:=(), Date14人工智能 文法规则示例 n$地 nR Rv nR Rp*v nR Rd|a|n*v n历史/n 地/ui 分析/v 中国/ns 的 /ud 历史/n 和/c 现实/n n我们/rr 得dei3/vu 放下/v 架子/n 老老实实/z 地 /ui 按/p 合同/n 办事。 n渐渐 地/ui 苦味淡了 Date15人工智能 MYCIN系统中的规则定义 n=IF THEN ELSE n=(AND) n=(OR)|( n=() n=| n=() n前提条件： n细菌：革氏染色阴性 n形态：杆状 n生长：需氧 n结论： n该细菌是肠杆菌属，CF=0.8 Date16人工智能 产生式知识表示的特点 n以规则作为形式单元，格式固定，易于表示， 知识单元独立，易于建立知识库 n推理方式单纯：适合模拟强数据驱动的智能行 为 n知识库与推理机分离：修改知识库，增加新规 则，不会破坏系统其它部分 n易于对系统推理路径做出解释。 Date17人工智能 6.1.2 基于产生式规则的推理模式 n利用产生式规则可以实现有前提条件的指令性操作， 实现操作的方法是当测试到一条规则的前提条件满足时 ，就执行其后部的操作。这叫规则的触发或点燃 n利用产生式规则可以实现逻辑推理，实现逻辑推理的 方法是当有事实能与某规则的前提匹配（规则的前提成 立）时，就得到该规则后部的结论（即结论也成立） n A B n A n B n把有前提的操作和逻辑推理统称为推理，产生式系统 中的推理是更广义的推理。 Date18人工智能 6.2 产生式系统基本原理 6.2.1 系统结构 6.2.2 运行过程 6.2.3 控制策略常用算法 6.2.4 程序实现* 6.2.5 产生式系统与问题求解 Date19人工智能 6.2.1系统结构-图 n产生式系统（机器中运用产生式进行推理的系统）结构 产生式规则库推理机 全局数据库 产生式系统的结构图 Date20人工智能 6.2.1 系统结构-组成 n产生式系统的组成 n产生式规则库作用在全局数据库上的一些 规则的集合。每条规则都有一定的条件，若全局数 据库中内容满足这些条件可调用这条规则。对应过 程性知识。 n推理机负责产生式规则的前提条件测试或 匹配，规则的调度和选取，规则体的解释和执行。 对应控制性知识。 n全局数据库人工智能系统的数据结构中心 。是一个动态数据结构，用来存放初始事实数据、 中间结果和最后结果。对应叙述性知识。 Date21人工智能 6.2.1 系统结构-TSP例 例 旅行推销员问题。求从A城出发，经过其他城市一次且 仅一次，最后回到A城的最小费用路线。城市之间的交通 费用标在相应的连线上。建立产生式系统。 B C A D E 7 13 10 9 6 5 6 7 10 10 Date22人工智能 6.2.1系统结构-TSP例 （1）全局数据库（已访问过的城镇名称序列）。约 束条件是除城镇A之外其他名称不得在序列中重复出现； 只有所有的名称都在序列中出现后，城镇A才能重复出现 。 （2）规则集如下表所示。 （3）推理： （A） （AB） （ABE） （4）终止条件序列始于A，终止于A，其中包含其他 所有城镇一次，且费用最少。 （5）各种搜索策略选择规则，如广度优先搜索，最好优 先搜索等。 R2R5 Date23人工智能 6.2.1 系统结构-TSP例 规则集 规则动作条件 R1下一步到A 系列中包含所有城镇时 可用 R2下一步到B 每条规则 只能使用一次，即 序列中已有某城镇时 ，不能 在使用相应规则 R3下一步到C R4下一步到D R5下一步到E Date24人工智能 6.2.1 系统结构-特点 n与一般分级组织的计算机软件相比具有特点： n全局数据库的内容可以为所有规则所访问，没 有任何部分是专为某一规则建立的，这种特性便于 模仿智能行为中的强数据驱动。 n规则本身不调用其他规则。规则之间的联系必 须通过全局数据库联系。 n全局数据库、规则和推理机之间相对独立，这 种积木式结构便于整个系统增加和修改知识。 Date25人工智能 6.2.2 产生式系统的运行过程（1） n推理机一次推理过程 从规则库中取出一条规则，将其前提同 当前动态数据库中的事实进行模式匹配 匹配成功否？ 把该规则的结论放入当前动态数据库； 或执行规则所规定的动作 Y N Date26人工智能 6.2.2 产生式系统的运行过程（2） n产生式系统运行过程 n实际的产生式系统，目标条件往往要经过多步推理才能 满足或者证明问题无解。 n产生式系统的运行过程就是推理机不断的运用规则库中 的规则，作用于动态数据库，不断进行推理并不断检测目标 条件是否被满足的过程。 n当推理到某一步，目标条件被满足，则推理成功，系统 运行结束；当再无规则可用，而目标仍未满足，推理失败， 系统运行也结束。 n产生式系统运行过程是从初始事实出发，寻求到达目标 条件的通路的过程。所以也是一个搜索的过程。 Date27人工智能 6.2.3 控制策略与常用算法-推理方式 n推理方式 n正向推理 从初始事实数据出发，正向使用 规则进行推理，朝目标方向前进。又称为前向推理 、正向链、数据驱动的推理。 n反向推理从目标出发，反向使用规则进行 推理，朝初始事实或数据方向前进。又称反向推理 、反向链、目标驱动的推理。 Date28人工智能 6.2.3控制策略与常用算法-正向推理 n正向推理算法一（树式盲目搜索） 步1 将初始事实/数据置入动态数据库； 步2 用动态数据库中的事实或数据匹配或测试目标条件 ，若目标条件满足，推理成功，结束。 步3 用规则库中各规则的前提匹配动态数据库中的事实 ，将匹配成功的规则组成待用规则集。 步4 若待用规则集为空，则运行失败，退出。 步5 将待用规则集中各规则的结论加入动态数据库，或 者执行其动作，转步2。 Date29人工智能 6.2.3控制策略与常用算法-例 例6.1：动物分类问题的产生式系统描述及求解。 规则： r1： IF 某动物有奶 THEN 它是哺乳动物 r2： IF 某动物有毛发 THEN 它是哺乳动物 r3： IF 某动物有羽毛 THEN 它是鸟 r4： IF 某动物会飞 AND 会下蛋 THEN 它是鸟 r5： IF 某动物是哺乳动物 AND 有犬齿 AND 有爪 AND 眼盯前方 THEN 它是食肉动物 r6：IF 某动物是哺乳动物 AND 吃肉 THEN 它是食肉动物 Date30人工智能 6.2.3控制策略与常用算法-例 r7:IF 某动物是哺乳动物 AND 有蹄 THEN 它是有蹄类动物 r8:IF 某动物是有蹄动物 AND 是嚼反刍动物 THEN 它是偶蹄动物 r9:IF某动物是食肉动物 AND 是黄褐色 AND 有黑色条纹 THEN 它是虎 r10:IF某动物是食肉动物 AND是黄褐色 AND有暗斑点 THEN 它是金钱豹 Date31人工智能 6.2.3控制策略与常用算法-例 r11：IF 某动物是有蹄类动物 AND 有长脖子 AND 有长腿 AND 身上有暗斑点 THEN 它是长颈鹿 r12：IF 某动物有蹄类动物 AND 身上有黑色条纹 THEN 它是斑马 r13：IF 某动物是鸟 AND 有长脖子 AND 有长腿 AND 不会飞 AND 有黑白二色 THEN 它是鸵鸟 r14： IF 某动物是鸟 AND 会游泳 AND 不会飞 AND 有黑白二色 THEN 它是企鹅 r15：IF 某动物是鸟 AND 善飞 AND 不怕风浪 THEN 它是海燕 Date32人工智能 老虎 黄褐色有黑色条纹食肉动物 哺乳动物 有毛发有奶 吃肉 有爪有犬齿 目盯前方 金钱豹 有黑色斑点 长颈鹿 有蹄动物 有蹄 长腿 长脖子有暗斑点 图6-4 动物分类产生式规则集所形成的部分推理网络 Date33人工智能 6.2.3控制策略与常用算法-例 初始事实： f1：某动物有毛发。 f2：吃肉。 f3：黄褐色。 f4：有黑色条纹 目标条件为：该动物为什么？ Date34人工智能 6.2.3控制策略与常用算法-例 例6.1 使用正向推理算法 9 Date35人工智能 6.2.3 控制策略与常用算法-正向推理 n若把动态数据库的每一个状态作为一个节点的话，则 上述推理过程就是一个从初始状态到目标状态的状态图 搜索过程。 n如果把动态数据库中的每一个事实/数据作为一个节点 的话，则上述推理过程就是一个自底向上的与或树搜索 过程。 Date36人工智能 6.2.3控制策略与常用算法-正向推理 n在产生式系统中，从前提到结论的产生式规则 通常也是一棵与或树。 n合取，与节点：一个产生式的前提包含了几个 事实，那么它的结论对应这些事实的合取。 n析取，或节点：一个结论可以由多个产生式得 到，则这个结论对应这些产生式的析取。 n每个产生式系统都隐含着许多这样的与或树。 Date37人工智能 6.2.3控制策略与常用算法-正向推理 F1 P1 F3F4F5F6 B C D A P2P3P4P5 F2 事实 中介事实 B、C、D 产生式规则 P1、P2、P3、P4、P5 结论 Date38人工智能 6.2.3 控制策略与常用算法-反向推理 n反向推理由目标驱动，首先假设一个结论，反 向使用规则进行推理（即用规则结论与目标匹配 ，又产生新的目标，然后对新的目标再做同样的 处理）去推导支持假设的事实或数据。 n优点：搜索目的性强，若目标选定正确，推理 效率高。 n缺点： 目标选择具有盲目性，可能会求解许多 为假的目标。 Date39人工智能 6.2.3控制策略与常用算法-反向推理算法 n反向推理算法 步1 将初始事实/数据置入动态数据库，将目标条件置入 目标链； 步2 若目标链为空，则推理成功，结束。 步3 取出目标链中第一个目标，用动态数据库中的事实 同其匹配，若匹配成功，转步2。 步4 用规则集中的各规则的结论同该目标匹配，若匹配 成功，则将第一个匹配成功且未用过的规则的前提作为 新的目标，并取代原来的父目标加入目标链，转步3。 步5 若该目标是初始目标，则推理失败，退出。 步6 将该目标的父目标移回目标链，取代该目标及其兄 弟目标，转步3。 Date40人工智能 6.2.3 控制策略与常用算法-例 例6.2 使用反向推理算法 哺乳类 食肉动物 有毛发有奶黄褐色有黑色条纹 老虎 反向推理推理树 目盯前方有毛发有爪吃肉 r9 r5 r1 r2 r6 Date41人工智能 6.2.3 控制策略与常用算法-正向推理改进 正向推理的执行过程是“匹配”-“冲突消解”-“执行” n匹配：给定一组事实之后可用匹配技术寻找可用产生 式，其基本思想是将已知事实代入产生式的前件，若前 件为真，则该产生式是可用的。 n提高匹配效率的方法 n索引匹配。为状态建立可用产生式索引表，减少可用产 生式搜索范围。 n分层匹配。将产生式分成若干层或组，按一定特征进行 分层搜索。 n过滤匹配。边匹配边 按某些附加特征或参数对可用产生 式进行精选。 Date42人工智能 6.2.3 控制策略与常用算法-正向推理改进 正向推理的执行过程是“匹配”-“冲突消解”-“执行” n冲突消解策略：如果一组事实可以同时使几个产生式 前提为真，常用以下方法进行选择： n优先级法（优先级高者优先） n可信度法（可信度高者优先） n自然顺序法 n采用优先级、可信度、代价等冲突消解策略，就是启 发式搜索；采用自然顺序法，就是一种盲目碰撞搜索。 n产生式系统的推理方式、搜索策略及冲突消解策略等 称为推理控制策略。 n产生式系统的控制策略体现在推理机的算法描述中。 Date43人工智能 6.2.3控制策略与常用算法-正向推理改进 n正向推理算法二（启发式线式搜索） 步1 将初始事实/数据置入动态数据库； 步2 用动态数据库中的事实匹配目标条件，若目标条件 满足，推理成功，结束。 步3 用规则库中各规则的前提匹配动态数据库中的事实 ，将匹配成功的规则组成待用规则集。 步4 若待用规则集为空，则运行失败，退出。 步5 用某种策略，从待用规则集中选取一条规则，将其 结论加入动态数据库，或者执行其动作，撤消待用规则 集，转步2。 Date44人工智能 状态图搜索-可回溯的线式搜索 步1 把初始节点S0放入CLOSED表中； 步2 令N S0 ； 步3 若N是目标节点，则搜索成功，结束。 步4 若N不可