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

第6章基于产生式规那么的机器推理2024/1/10人工智能2第6章基于产生式规那么的机器推理6.1产生式规那么6.2产生式系统2024/1/10人工智能3产生式规那么〔1〕产生式〔Production〕-1943年美国数学家Post在计算形式体系中提出的术语产生式一词从波斯特机中借用来的。波斯特机是一种自动机，它是根据串替换规那么提出的一种计算模型。产生式就是逻辑蕴含式、推理规那么以及各种关系〔包含经验性联想〕的一种逻辑抽象。产生式系统在形式上很简单，但在一定意义上模仿了人类思考的过程。人工智能使用产生式的理由为什么要采用产生式系统作为人工智能系统的主要结构呢？两点理由：用产生式系统结构求解问题的过程和人类求解问题时的思维过程相似，因而可以用来模拟人类求解问题时的思维过程。可把产生式系统作为人工智能系统的根本结构单元或根本模式看待，就像积木中的积木块一样，因而研究产生式系统的根本问题就具有一般意义。2024/1/10人工智能4产生式规那么的界定及内容产生式规那么是产生式系统的主体，是产生式系统知识表示的核心。故直接将产生式称为产生式规那么。一般产生式的结构可表示为自然语言形式，“原因-结果〞，“条件-结论〞，“前提-操作〞，“事实-进展〞，“情况-行为〞等结构都可归结为产生式的知识表达形式。2024/1/10人工智能5可归结为产生式的表达形式例：〔1〕天下雨，地上湿。〔“原因-结果〞〕〔2〕如果把冰加热到零摄氏度以上，冰会融化为水。〔“条件-结论〞〕〔3〕夜来风雨声，花落知多少。〔“事实-进展〞〕〔4〕假设能找到一根适宜的杠杆，就能撬超那座山。〔“前提-操作〞〕〔5〕刚刚开机了，意味着发出了捕获目标图像的信号。〔“情况-行为〞〕2024/1/10人工智能62024/1/10人工智能7产生式规那么〔2〕产生式的一般形式为：AB〔或IFAThenB〕A是产生式的前提〔前件〕，用于指出该产生式是否可用的条件B是一组结论或操作〔后件〕，用于指出当前提A指示的条件满足时，应得出的结论或应执行的操作。一个产生式规那么就是一条知识，用产生式不仅可以进行推理，也可以实现操作。2024/1/10人工智能8产生式规那么〔例〕例三个聪明人问题。古代有个国王想知道他的三个大臣中谁最聪明，就在他们每个人前额上都画了一个点，他们都能看到别人点的颜色，但看不到自己点的颜色。国王说，你们中间至少有一个人的点是白色的。于是重复地问他们：“谁知道自己点的颜色？〞三位大臣们头两次都答复说不知道。题目要求证明下一次他们全都会说“知道〞，并且所有的点都是白色。2024/1/10人工智能9产生式规那么〔例〕分析：这类问题的特点是有有限个受试者，每个人对问题都只有局部了解，无法直接求解。但在推理过程中每个人又可以从别人那里获得新的知识，重新进行推理。可以用产生式来表达推理过程中所用到的各种知识。2024/1/10人工智能10产生式规那么〔例〕状态集合表示：

用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。2024/1/10人工智能11产生式规那么〔例〕排除过程：第一次，大臣只知道至少有一个人是白点，排除X0={(0,0,0)}状态。这时如果有人看到两个非白点，根据排除的状态可推知自己是白点。第二次大臣根据没有一个人知道自己点颜色的事实推知至少两人为白点。排除{(0,0,1)(0,1,0)(1,0,0)}状态。这时如果有人看到一个非白点，根据排除后得到的状态可推知自己的点是白的。第三次，大臣们根据仍无人知道自己点颜色的新事实推知没有一个非白点出现，即X0={(1,1,1)}。于是三人都知道自己点的颜色是白的。2024/1/10人工智能12产生式规那么〔例〕引入中介状态并定义下述符号：Si——i大臣看到的非白点数；Wi——i大臣猜出自己点的颜色否。如果他宣布道自己点的颜色，为1，否那么为0；n——X0中白点的个数。

2024/1/10人工智能13产生式规那么〔例〕(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).2024/1/10人工智能14产生式规那么〔例〕上述结果可以推广到更一般的情况：设有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<m-1)=>(n>=l＋1);(6)(i)(Wi=0)(n>=l)(l＝m-1)=>(n＝m)。

2024/1/10人工智能15基于产生式规那么的推理模式AB

AB

把有前提的操作和逻辑推理统称为推理，产生式系统中的推理是更广义的推理。2024/1/10人工智能166.2产生式系统系统结构运行过程控制策略常用算法程序实现*产生式系统与问题求解2024/1/10人工智能17系统结构〔1〕产生式系统结构产生式规那么库推理机全局数据库2024/1/10人工智能18系统结构〔2〕组成产生式规那么库——作用在全局数据库上的一些规那么的集合。每条规那么都有一定的条件，假设全局数据库中内容满足这些条件可调用这条规那么。一般可形成一个称为推理网络的结构图。对应过程性知识。推理机——负责产生式规那么的前提条件测试或匹配，规那么的调度和选取，规那么体的解释和执行。即推理机实施推理，并对推理进行控制，它也是规那么的解释程序。对应控制性知识。全局数据库——人工智能系统的数据结构中心。是一个动态数据结构，用来存放初始事实数据、中间结果和最后结果。对应表达性知识。2024/1/10人工智能19系统结构〔3〕例

旅行推销员问题。求从A城出发，经过其他城市一次且仅一次，最后回到A城的最小费用路线。城市之间的交通费用标在相应的联线上。建立产生式系统。BCADE713109656710102024/1/10人工智能20系统结构〔4〕〔1〕全局数据库——〔已访问过的城镇名称序列〕。约束条件是除城镇A之外其他名称不得在序列中重复出现；只有所有的名称都在序列中出现后，城镇A才能重复出现。〔2〕规那么集——如下表所示。〔3〕推理：〔A〕〔AB〕〔ABE〕〔4〕终止条件——序列始于A，终止于A，其中包含其他所有城镇一次，且费用最少。〔5〕各种搜索策略选择规那么，如广度优先搜索，最好优先搜索等。

R2R52024/1/10人工智能21系统结构〔5〕规那么集

规则动作条件R1下一步到A系列中包含所有城镇时可用R2下一步到B每条规则只能使用一次，即序列中已有某城镇时，不能再使用相应规则R3下一步到CR4下一步到DR5下一步到E2024/1/10人工智能22系统结构〔6〕与一般分级组织的计算机软件相比具有特点：全局数据库的内容可以为所有规那么所访问，没有任何局部是专为某一规那么建立的，这种特性便于模仿智能行为中的强数据驱动。规那么本身不调用其他规那么。规那么之间的联系必须通过全局数据库联系。全局数据库、规那么和推理机之间相对独立，这种积木式结构便于整个系统增加和修改知识。2024/1/10人工智能23产生式系统的运行过程〔1〕推理机一次运行过程从规则库中取出一条规则，将其前提同当前动态数据库中的事实进行模式匹配匹配成功否？把该规则的结论放入当前动态数据库；或执行规则所规定的动作YN2024/1/10人工智能24产生式系统的运行过程〔2〕产生式系统运行过程实际的产生式系统，目标条件往往要经过多步推理才能满足或者证明问题无解。产生式系统的运行过程就是推理机不断的运用规那么库中的规那么，作用于动态数据库，不断进行推理并不断检测目标条件是否被满足的过程。产生式系统运行过程是从初始事实出发，寻求到达目标条件的通路的过程。所以也是一个搜索的过程。例1一个简单的例子问题：设字符转换规那么 A∧B→C A∧C→D B∧C→G B∧E→F D→E ：A，B 求：F2024/1/10人工智能25例1一个简单的例子〔1〕一、综合数据库 {x}，其中x为字符二、规那么集1，IFA∧BTHENC 2，IFA∧CTHEND 3，IFB∧CTHENG 4，IFB∧ETHENF 5，IFDTHENE2024/1/10人工智能26三、控制策略 顺序排队四、初始条件

{A，B}五、结束条件

F∈{x}例1一个简单的例子〔2〕2024/1/10人工智能27综合数据库可触发规则被触发规则A，B（1）（1）A，B，C（2）（3）（2）A，B，C，D（3）（5）（3）A，B，C，D，G（5）（5）A，B，C，D，G，E（4）（4）A，B，C，D，G，E，F求解过程28 问题： N个传教士，N个野人，一条船，可同时乘坐k个人，要求在任何时刻，在河的两岸及船上，传教士人数不能少于野人的人数。

问：如何过河。〔给出综合数据库、初始状态和目标状态、规那么集合的形式化描述〕 以N=3，k=2为例求解。例2：传教士与野人问题〔M-C问题〕29例2：M-C问题〔续1〕

LRLRm30m03c30c03B10B01L—左岸R—右岸B—1〔有船〕、0〔无船〕30例2：M-C问题〔续2〕1，综合数据库 〔m,c,b)， 其中：0≤m,c≤3,b∈{0,1}2，初始状态 〔3，3，1〕(简化，只描述左岸的情况即可)3，目标状态〔结束状态〕 〔0，0，0〕31例2：M-C问题〔续3〕4，规那么集 IF(m,c,1)THEN(m-1,c,0) IF(m,c,1)THEN(m,c-1,0) IF(m,c,1)THEN(m-1,c-1,0) IF(m,c,1)THEN(m-2,c,0) IF(m,c,1)THEN(m,c-2,0)32IF(m,c,0)THEN(m+1,c,1)IF(m,c,0)THEN(m,c+1,1)IF(m,c,0)THEN(m+1,c+1,1)IF(m,c,0)THEN(m+2,c,1)IF(m,c,0)THEN(m,c+2,1)例2：M-C问题〔续4〕例2：N=5，k<=3为例2024/1/10人工智能33例3：猴子摘香蕉问题一个房间里，天花板上挂有一串香蕉，有一只猴子可在房间里任意活动〔到处走动，推移箱子，攀登箱子等〕。设房间里还有一只可被猴子移动的箱子，且猴子登上箱子时才能摘到香蕉，问猴子在某一状态下〔设猴子位置为c，箱子位置为b，香蕉位置为a〕，如何行动可摘取到香蕉。2024/1/10人工智能34abc例3：猴子摘香蕉问题2024/1/10人工智能351，综合数据库 定义5元组〔M,B,Box,On,H〕 M：猴子的位置 B：香蕉的位置 Box：箱子的位置 On=0：猴子在地板上 On=1：猴子在箱子上 H=0：猴子没有抓到香蕉 H=1：猴子抓到了香蕉例4：量水问题对量水问题给出产生式系统描述，并画出状态空间图。有两个无刻度标志的水壶，分别可装5升和2升的水。设另有一水缸，可用来向水壶灌水或倒出水，两个水壶之间，水也可以相互倾灌。5升壶为满壶，2升壶为空壶，问如何通过倒水或灌水操作，使能在2升的壶中量出一升的水来。2024/1/10人工智能36例4：量水问题2024/1/10人工智能372024/1/10人工智能38控制策略与常用算法〔1〕推理方式正向推理——从初始事实数据出发，正向使用规那么进行推理，朝目标方向前进。又称为前向推理、正向链、数据驱动的推理。反向推理——从目标出发，反向使用规那么进行推理，朝初始事实或数据方向前进。又称反向推理、反向链、目标驱动的推理。2024/1/10人工智能39控制策略与常用算法〔2〕正向推理算法一步1将初始事实/数据置入动态数据库；步2用动态数据库中的事实匹配目标条件，假设目标条件满足，推理成功，结束。步3用规那么库中各规那么的前提匹配动态数据库中的事实，将匹配成功的规那么组成待用规那么集。步4假设待用规那么集为空，那么运行失败，退出。步5将待用规那么集中各规那么的结论参加动态数据库，或者执行其动作，转步2。2024/1/10人工智能40控制策略与常用算法〔3〕假设把动态数据库的每一个状态作为一个节点的话，那么上述推理过程就是一个从初始状态到目标状态的状态图搜索过程。如果把动态数据库中的每一个事实/数据作为一个节点的话，那么上述推理过程就是一个自底向上的与或树搜索过程。2024/1/10人工智能41控制策略与常用算法〔4〕反向推理算法步1将初始事实/数据置入动态数据库，将目标条件置入目标链；步2假设目标链为空，那么推理成功，结束。步3取出目标链中第一个目标，用动态数据库中的事实同其匹配，假设匹配成功，转步2。步4用规那么集中的各规那么的结论同该目标匹配，假设匹配成功，那么将第一个匹配成功且未用过的规那么的前提作为新的目标，并取代原来的父目标参加目标链，转步3。步5假设该目标是初始目标，那么推理失败，退出。步6将该目标的父目标移回目标链，取代该目标及其兄弟目标，转步3。2024/1/10人工智能42控制策略与常用算法〔5〕在产生式系统中，从前提到结论的产生式规那么通常也是一棵与或树。合取，与节点：一个产生式的前提包含了几个事实，那么它的结论对应这些事实的合取。析取，或节点：一个结论可以由多个产生式得到，那么这个结论对应这些产生式的析取。每个产生式系统都隐含着许多这样的与或树。2024/1/10人工智能43控制策略与常用算法〔6〕F1P1F3F4F5F6BCDAP2P3P4P5F2事实中介事实B、C、D产生式规那么P1、P2、P3、P4、P5结论2024/1/10人工智能44控制策略与常用算法〔7〕例6.1：动物分类问题的产生式系统描述及求解。规那么：r1：IF该动物有毛发THEN该动物是哺乳动物r2：IF该动物有奶THEN该动物是哺乳动物r3：IF该动物有羽毛THEN该动物是鸟r4：IF该动物会飞AND会下蛋THEN该动物是鸟r5：IF该动物吃肉THEN该动物是食肉动物r6：IF该动物有犬齿AND有爪AND眼盯前方THEN该动物是食肉动物动物2024/1/10人工智能45控制策略与常用算法〔8〕r7：IF该动物是哺乳动物

AND有蹄

THEN该动物是有蹄类动物r8：IF该动物是哺乳动物

AND是嚼反刍动物

THEN该动物是有蹄动物r9：IF该动物是哺乳动物

AND是食肉动物

AND是黄褐色AND身上有暗斑点

THEN该动物是金钱豹

r10：IF该动物是哺乳动物

AND是食肉动物

AND是黄褐色AND身上有黑色条纹

THEN该动物是虎2024/1/10人工智能46控制策略与常用算法〔9〕r11：IF该动物是有蹄类动物

AND有长脖子

AND有长腿AND身上有暗斑点

THEN该动物是长颈鹿r12：IF该动物有蹄类动物

AND身上有黑色条纹

THEN该动物是斑马r13：IF该动物是鸟

AND有长脖子AND有长腿

AND不会飞AND有黑白二色

THEN该动物是鸵鸟2024/1/10人工智能47控制策略与常用算法〔10〕r14：IF该动物是鸟

AND会游泳AND不会飞

AND有黑白二色

THEN该动物是企鹅r15：IF该动物是鸟

AND善飞AND不怕风浪

THEN该动物是海燕老虎黄褐色有黑色条纹食肉动物哺乳动物有毛发有奶吃肉有爪有犬齿目盯前方金钱豹有黑色斑点长颈鹿有蹄动物有蹄长腿长脖子有暗斑点图6-4动物分类产生式规则集所形成的部分推理网络2024/1/10人工智能49控制策略与常用算法〔12〕初始事实：

f1：某动物有毛发。

f2：吃肉。

f3：黄褐色。

f4：有黑色条纹目标条件为：该动物为什么？2024/1/10人工智能50控制策略与常用算法〔13〕2024/1/10人工智能51控制策略与常用算法〔14〕例6.2使用反向推理算法2024/1/10人工智能52控制策略与常用算法〔15〕3冲突消解策略给定一组事实之后可用匹配技术寻找可用产生式，其根本思想是将事实代入产生式的前件，假设前件为真，那么该产生式是可用的。提高匹配效率的方法索引匹配。为状态建立可用产生式索引表，