人工智能-知识表示.ppt

《人工智能-知识表示.ppt》由会员分享，可在线阅读，更多相关《人工智能-知识表示.ppt（160页珍藏版）》请在三一办公上搜索。

1、第二章 知识表示,知识就是力量,2,第2章 知识表示,2.1 知识表示与知识表示的概念2.2 一阶谓词逻辑表示法2.3 产生式表示法2.4 语义网络表示法2.5 框架表示法2.6 状态空间表示法2.7 问题规约表示法2.8 剧本表示法2.9 面向对象表示法,3,2.1.1 知识的概念-何谓知识（一）,知识的一般概念 知识是人们在改造客观世界的实践中积累起来的认识和经验认识：包括对事物现象、本质、属性、状态、关系、联系和运动等的认识经验：包括解决问题的微观方法，如步骤、操作、规则、过程、技巧等 宏观方法，如战略、战术、计谋、策略等知识、信息、数据及其关系原因：认识客观世界的前提是能对其描述，而描

2、述由数据和信息来实现的解释：数据是为描述客观事物而引入的一些数字、符号、文字等 信息是对客观事物的一般性描述，它还不是知识。数据组成结构。关系：数据是信息的载体，本身无确切含义，其关联构成信息 信息是数据的关联，赋予数据特定的含义，仅可理解为描述性知识 知识可以是对信息的关联，也可以是对已有知识的再认识 例如：(1)if 计算机能听懂人类语言 then 可直接与计算机对话(2)if 计算机能听懂人类语言就可直接与计算机对话 then 人类将努力研究自然语言理解问题,4,2.1.1 知识的概念-何谓知识（二）,“知识”有代表性的定义（1）知识是经过剪裁、塑造、解释、选择和转换了的信息（2）知识由

3、特定领域的描述、关系和过程组成（3）知识=事实+信念+启发式“信息”与“关联”是构成知识的两个要素。信息之间关联的形式可以多种多样，最常见的一种形式是：“如果。，则。”,5,2.1.1 知识的概念-知识的属性,真假性与相对性 真假性：可以通过实践和推理来证明知识是真的还是假的 相对性：非绝对性。知识的真与假是相对于条件、环境、事件而言的不确定性 不完备性：解决问题时不具备解决该问题的全部知识 不精确性：知识本身有真假之分，但由于认识水平限制说不清其真假 这时可由可信度、概率等进行描述。模糊性：知识的边界本身就是不清楚的(人的相貌)用可能性、隶属度来描述（模糊搜索）矛盾性和相容性 矛盾性：同一知

4、识集中的知识之间相互对立或不一致（保健专家系统）相容性：一个知识集中的所有知识之间相互不矛盾可表示性与可利用性 可表示性：知识可用适当的形式表示出来。如语言、文字、图形等 可利用性：知识可用来解决各种各样的问题,6,2.1.1 知识的概念-知识的类型（一）,按知识的性质 概念、命题、公理、定理、规则和方法按知识的作用域 常识性知识：通用通识的知识。人们普遍知道的、适应所有领域的 领域性知识：面向某个具体专业领域的。该领域专家才知道的 如：专家经验。专家系统拥有的是此类知识按知识的作用效果 事实性知识：（叙述性知识）描述事物的概念、定义、属性等（神5实现了中华民族的飞天梦想）问题的状态、环境、条

5、件等（气温逐渐下降）过程性知识：用于问题求解过程的操作、演算和行为的知识 用来指出如何使用那些与问题有关的事实性知识的知识 由与求解问题有关的规则、定律、定理及经验所构成 例如：AX2+BX+C=0 控制性知识：即元知识或超知识 如何使用知识的知识，也称为关于知识的知识。例如：推理策略、搜索策略(深度优先、广度优先、启发式)不确定性的传播策略,7,2.1.1 知识的概念-知识的类型（二）,按知识的层次 表层知识：客观事物的现象及这些现象与结论之间关系的知识 他描述简单，但不反映事物的本质。如：经验、感性、事实性知识（专家系统）深层知识：客观事物本质、因果关系内涵、基本原理之类的知识 如：理论知

6、识、理性知识(数据挖掘)按知识的确定性 确定性知识：可以说明其真值为真或为假的知识 不确定性知识：不能确切说明其真假或不能完全知道的知识 包括：不精确、模糊、不完备按知识的等级 零级知识：叙述性知识。描述事物的属性，问题的状态等 一级知识：过程性知识。经验型、启发性的知识 二级知识（元知识、超知识）：如何使用一级知识 三级知识（元元知识）,8,2.1.2 知识表示的概念-知识表示的含义及要求,什么是知识表示 是对知识的描述，即用一组符号把知识编码成计算机可以接受的某种结构。其表示方法不唯一。(请对比计算机如何了解5V电压信号？)知识表示的要求（难度很大）表示能力：能否正确、有效地将问题求解所需

7、的各种知识表示出来 表示范围的广泛性 领域知识表示的高效性 对非确定性知识表示的支持程度 可利用性：利用这些知识进行推理，可以求得待解决问题的解 对推理的适应性：推理是根据已知事实利用知识导出结果的过程 对高效算法的支持程度：知识表示要有较高的处理效率 可实现性：要便于计算机直接对其进行处理 可组织性：可以按某种方式把知识组织成某种知识结构 可维护性：便于对知识的增、删、改等操作（知识的一致性）自然性：符合人们的日常习惯 可理解性：知识应易读、易懂、易获取等,9,2.1.2 知识表示的概念-知识表示的观点及方法,知识表示的观点 陈述性观点：知识按某种结构存储，知识的使用由过程来实现 优点：灵活

8、、简洁，演绎过程完整、确定，知识维护方便 缺点：推理效率低、推理过程不透明（1965归结定理）过程性观点：知识寓于使用知识的过程中，表示与运用相结合（P38）。优点：推理效率高、过程清晰 缺点：灵活性差、知识维护不便知识表示的方法 逻辑表示法：一阶谓词逻辑 产生式表示法：产生式规则 结构表示法：语义网络，框架，脚本 过程表示法：面向对象表示法：,10,2.2 一阶谓词逻辑表示法,本节主要讨论：一阶谓词逻辑表示的逻辑基础 仅与知识表示有关的，推理有关的在下一章 命题和真值；论域和谓词；连词和量词；项与合式公式；自由变元与约束变元 谓词逻辑表示的方法 谓词逻辑表示的应用 谓词逻辑表示的特性,11,

9、一阶谓词逻辑表示的逻辑基础-命题与真值,命题的定义：断言：一个陈述句称为一个断言 命题：具有真假意义的断言成为命题可以用大写字母表示命题，如：A:天在下雨。B:天晴C:人是会死的D:他在哭命题的真值：T：表示命题的意义为真 F：表示命题的意义为假表达单一意义的命题称为“原子命题”。命题逻辑就是研究命题和命题之间关系的符号逻辑系统。,12,一阶谓词逻辑表示的逻辑基础-论域和谓词（一）,论域：由所讨论对象的全体构成的集合。也称为个体域个体：论域中的元素。谓词：在谓词逻辑中命题是用形如P(x1,x2,xn)的谓词来表示的 谓词名：是命题的谓语，表示个体的性质、状态或个体之间的关系 个体：是命题的主语

10、，表示独立存在的事物或概念定义2.2 设D是个体域，P：DnT，F是一个映射，其中 则称P是一个n元谓词，记为 P(x1,x2,xn)其中，x1,x2,xn为个体，可以是个体常量、变元和函数。例如：GREATER(x,6)x大于6 STUDENT(wanghong)王红是一名学生 TEACHER(father(zhang)张的父亲是一位教师,13,一阶谓词逻辑表示的逻辑基础-连词,连词：称为“非”或者“否定”。它表示对其后面的命题的否定：称为“析取”。它表示所连结的两个命题之间具有“或”：称为“合取”。它表示所连结的两个命题之间具有“与”的关系。：称为“条件”或“蕴含”。表示“若则”的语义。读

11、作“如果P，则Q”。其中，P称为条件的前件，Q称为条件的后件。：称为“双条件”。它表示“当且仅当”的语义。即读作“P当且仅当Q”。例如，对命题P和Q，PQ表示“P当且仅当Q”，,14,蕴含关系的困惑?-例子,蕴含词“若P则Q”与自然语言中的“若P则Q(同属)”既有相似之处，也有本质上的区别。如果P是真的，Q是假的，那么复合命题“若P则Q”是假的。如果P是假的，那么不管Q是真是假，复合命题“若P则Q”都是真的。“如果今天下雨，那么我们就呆在家里”（1）如果今天下雨了，我们呆在家里了，那么复合命题显然是真的。（2）如果今天下雨了，我们却没有呆在家里，那么这显然违背了原命题，即复合命题是假的。（3）

12、如果今天没有下雨，那么不管我们是否呆在家里都不能认为我们违背了复合命题的要求，即复合命题是真的。,15,一阶谓词逻辑表示的逻辑基础-量词,量词：全称量词，意思是“所有的”、“任一个”命题(x)P(x)为真，当且仅当对论域中的所有x，都有P(x)为真 命题(x)P(x)为假，当且仅当对论域中的所有x，都有P(x)为假：存在量词，意思是“至少有一个”、“存在有”命题(x)P(x)为真，当且仅当至少存在一个xi D，使得P(xi)为真 命题(x)P(x)为假，当且仅当至少存在一个xi D，使得P(xi)为假,16,一阶谓词逻辑表示的逻辑基础-项与合式公式,合法的谓词表达式称为合式公式（即谓词公式）。

13、由“项”来定义。个体常量、个体变量和函数称为项。定义2-5 原子谓词公式的含义为：若t1，t2，tn是项，P是谓词符号，则称P(t1，t2，tn)为原子谓词公式。定义2-6 满足如下规则的谓词演算可得到合式公式：单个原子谓词公式是合式公式；若A是合式公式，则A也是合式公式；若A，B是合式公式，则AVB，AB，AB，AB也都是合式公式；若A是合式公式，x是项，则(x)A和(x)A也都是合式公式。根据以上是合式公式的形成规则，可以形成任意复杂的合式公式。例如，P(x，y)VQ(y)，(x)(A(x)B(x)，都是合式公式。连词的优先级：，V，,17,一阶谓词逻辑表示的逻辑基础-自由变元与约束变元,

14、辖域：指位于量词后面的单个谓词或者用括弧括起来的合式公式约束变元：辖域内与量词中同名的变元称为约束变元自由变元：不受约束的变元称为自由变元例子：(x)(P(x，y)Q(x，y)VR(x，y)其中，(P(x，y)Q(x，y)是(x)的辖域 辖域内的变元x是受(x)约束的变元 R(x，y)中的x和所有的y都是自由变元变元的换名：谓词公式中的变元的名字是无关紧要的，可以换名。但需注意两点 第一，当对量词辖域内的变元更名时，必须把同名的约束变元都统一换成另外一个相同的名字，且不能与辖域内的自由变元同名。例如，对公式(x(P(x，y)，可把约束变元x换成z，得到公式(z)(P(z，y)。第二，当对辖域内

15、的自由变元更名时，不能改成与约束变元相同的名字。例如，对公式(x)(P(x，y)，可把自由变元y换成t（但不能换成x），得到公式(z)(P(z，t)。,18,谓词逻辑表示方法（一）,表示步骤：先根据表示的知识定义谓词 再用连词、量词把这些谓词连接起来（事实、因果）例2.1 表示“每个人都有父亲”定义谓词：P(x)表示x是人 HF(x,y)表示x有父亲y 表示知识：(x)(y)(P(x)HF(x,y)P(y)例2.2 表示知识“所有教师都有自己的学生”。定义谓词：T(x)：表示x 是教师。S(x)：表示x是学生。TS(x,y)：表示x是y的老师。此时，该知识可用谓词表示为：(x)(y)(T(x)

16、TS(x,y)S(y)可读作：对所有x，如果x是一个教师，那么一定存在一个个体y，y的老师是x，且y是一个学生。,19,谓词逻辑表示方法（二）,例2.3 表示知识“所有的整数不是偶数就是奇数”。定义谓词：I(x)：x是整数，E(x)：x是偶数，O(x)：x是奇数 知识的谓词表示为：(x)(I(x)E(x)O(x)例2.4 表示如下知识：王宏是计算机系的一名学生。李明是王宏的同班同学。凡是计算机系的学生都喜欢编程序。定义谓词：COMPUTER(x)：表示x是计算机系的学生。CLASSMATE(x,y)：表示x是y的同班同学。LIKE(x,y)：表示x喜欢y。上述知识表示为：COMPUTER(Wa

17、nghong)CLASSMATE(Liming,Wanghong)(x)(COMPUTER(x)LIKE(x,programing),20,练习,用一阶谓词逻辑表示下面的句子：自然数都是大于零的整数。所有整数不是偶数就是奇数。并不是所有的学生都选修了历史和生物。历史考试中只有一个学生不及格。除了选修人工智能的学生外，都去舞会了。,21,谓词逻辑表示的应用-机器人移盒子问题（一）智能规划NP旅行规划、自动武器等,谓词可用来描述状态、动作:机器人从c点出发，将盒子从a桌拿到b桌，然后再回到c处。研究的对象：桌子x的个体域是a,b 机器人y的个体域是robot 位置z的个体域是a,b,c 物体w的个

18、体域是box描述状态的谓词：TABLE(x)：x是桌子 EMPTY(y)：y手中是空的 AT(y,z)：y在z的附近 HOLDS(y,w)：y拿着w ON(w,x)：w在x桌面上,22,谓词逻辑表示的应用-机器人移盒子问题（二）,问题的初始状态 AT(robot,c)EMPTY(robot)ON(box,a)TABLE(a)TABLE(b)问题的目标状态 AT(robot,c)EMPTY(robot)ON(box,b)TABLE(a)TABLE(b)机器人行动的目标把问题的初始状态转换为目标状态，而要实现问题状态的转换需要完成一系列的操作,23,谓词逻辑表示的应用-机器人移盒子问题（三）,操作

19、的表示方法 由条件和动作两部分 条件部分用来说明执行该操作必须具备的先决条件 可用谓词公式来表示 动作部分给出了该操作对问题状态的改变情况 动作部分则是通过在执行该操作前的问题状态中删去和增加相应的谓词来实现的机器人需要执行的操作 Goto(x,y)：从x处走到y处。Pickup(x)：在x处拿起盒子。Setdown(x)：在x处放下盒子。,24,谓词逻辑表示的应用-机器人移盒子问题（三）,操作对应的条件和动作如下Goto(x，y)条件：AT(robot，x)动作：删除：AT(robot，x)添加：AT(robot，y)Pickup(x)条件：ON(box，x)，TABLE(x)，AT(rob

20、ot，x)，EMPTY(robot)动作：删除：EMPTY(robot)，ON(box，x)添加：HOLDS(robot，box)Setdown(x)条件：AT(robot，x)，TABLE(x)，HOLDS(robot，box)动作：删除：HOLDS(robot，box)添加：EMPTY(robot)，ON(box，x)机器人在执行每一操作之前，都需要检查当前状态是否可以满足该操作的先决条件。如果满足，就执行相应的操作，否则就检查下一个操作所要求的先决条件。(归结理论),25,谓词逻辑表示的应用-机器人移盒子问题（四）,这个机器人行动规划问题的求解过程如下：状态1(初始状态)AT(robot

21、,c)开始 EMPTY(robot)=ON(box,a)TABLE(a)TABLE(b)状态2 AT(robot,a)Goto(x,y)EMPTY(robot)=ON(box,a)用c代换x TABLE(a)a代换y TABLE(b)状态3 AT(robot,a)Pickup(x)HOLDS(robot,box)=TABLE(a)用a代换x TABLE(b),26,谓词逻辑表示的应用-机器人移盒子问题（五）,状态4 AT(robot,b)Goto(x,y)HOLDS(robot,box)=TABLE(a)用a代换x TABLE(b)b代换y 状态5 AT(robot,b)Setdown(x)E

22、MPTY(robot)=ON(box,b)用b代换x TABLE(a)TABLE(b)状态6(目标状态)AT(robot,c)Goto(x,y)EMPTY(robot)=ON(box,b)用b代换x TABLE(a)c代换y TABLE(b),27,谓词逻辑表示的应用-机器人摞积木问题（一）,描述状态的谓词(看图找谓词，TABLEEMPTY)CLEAR(x)：积木x上面是空的 ON(x,y)：积木x在积木y的上面 ONTABLE(x)：积木x在桌子上 HOLDING(x)：机械手抓住x HANDEMPTY：机械手是空的其中，x和y的个体域都是A,B,C问题的初始状态 CLEAR(B),ON(C

23、,A),ONTABLE(A),CLEAR(C)HANDEMPTY,ONTABLE(B)问题的目标状态是 ON(B,C),ON(A,B),ONTABLE(C)CLEAR(A),HANDEMPTY,A,B,C,28,谓词逻辑表示的应用（续）,29,谓词逻辑表示的应用-机器人摞积木问题（二）,需要的4个操作 Pickup(x)：从桌面上拣起一块积木x Putdown(x)：将手中的积木x放到桌子上 Stack(x,y)：把积木x摞在积木y上 Upstack(x,y)：把积木x从积木y上面拣起操作对应的先决条件及动作 Pickup(x)(从桌面上拣起一块积木x)条件：ONTABLE(x)，HANDEM

24、PTY，CLEAR(x)动作：删除表：ONTABLE(x)，HANDEMPTY，CLEAR(x)添加表：HOLDING(x)Putdown(x)（将手中的积木x放到桌子上）条件：HOLDING(x)动作：删除表：HOLDING(x)添加表：ONTABLE(x)，HANDEMPTY，CLEAR(x),30,谓词逻辑表示的应用-机器人摞积木问题（三）,Stack(x,y)（把积木x摞在积木y上）条件：HOLDING(x)，CLEAR(y)动作：删除表：HOLDING(x)，CLEAR(y)添加表：HANDEMPTY，ON(x,y)，CLEAR(x)Upstack(x,y)（把积木x从积木y上面拣起

25、）条件：HANDEMPTY，CLEAR(x)，ON(x,y)动作：删除表：HANDEMPTY，ON(x,y)添加表：HOLDING(x)，CLEAR(y)利用上述谓词和操作，即可完成积木世界的求解问题。至于其求解过程，和前述机器人搬盒子问题类似，这里从略。,31,谓词逻辑表示的练习-猴子摘香蕉问题（一）,描述状态的谓词 AT(x,y)：x在y处 ONBOX：猴子在箱子上 HB：猴子得到香蕉其中，x 的个体域是 Monkey,Box,BananaY 的个体域是 a,b,c问题的初始状态 AT(Monkey,a)AT(Box,b)ONBOX，HB问题的目标状态 AT(Monkey,c)，AT(Bo

26、x,c)ONBOX，HB,32,谓词逻辑表示的应用-猴子摘香蕉问题（二）,需要的操作 Goto(u,v)：猴子从u处走到v处 Pushbox(v,w)：猴子推着箱子从v处移到w处 Climbbox：猴子爬上箱子 Grasp：猴子摘取香蕉,33,谓词逻辑表示的应用-猴子摘香蕉问题（二）,操作对应的先决条件及动作Goto(u,v)条件：ONBOX，AT(Monkey,u)，动作：删除表：AT(Monkey,u)添加表：AT(Monkey,v)Pushbox(v,w)条件：ONBOX，AT(Monkey,v)，AT(Box,v)动作：删除表：AT(Monkey,v)，AT(Box,v)添加表：AT(

27、Monkey,w)，AT(Box,w)Climbbox 条件：ONBOX，AT(Monkey,w)，AT(Box,w)动作：删除表：ONBOX 添加表：ONBOXGrasp 条件：ONBOX，AT(Box,c)动作：删除表：HB 添加表：HB,请写出猴子摘香蕉的求解过程,34,谓词逻辑表示的特征,主要优点 自然：一阶谓词逻辑是一种接近于自然语言的形式语言系统，谓词逻辑表示法接近于人们对问题的直观理解，易于被人们接受 明确：人们都可以按照一种标准的方法去解释知识，因此用这种方法表示的知识明确、易于理解 精确：谓词逻辑的真值只有“真”与“假”，其表示、推理都是精确的 灵活：知识和处理知识是分开的，

28、无须程序中考虑处理知识的细节 模块化：各条知识都是相对独立的，它们之间不直接发生联系，因此添加、删除、修改知识的工作比较容易进行主要缺点 知识表示能力差：只能表示确定性知识，而不能表示非确定性知识、过程性知识和启发式知识 知识库管理困难：缺乏知识的组织原则，知识库管理比较困难 存在组合爆炸：由于难以表示启发式知识，因此只能盲目地使用推理规则，这样当系统知识量较大时，容易发生组合爆炸 系统效率低：它把推理演算与知识含义截然分开，抛弃了表达内容中所含有的语义信息，往往使推理过程冗长，降低了系统效率,35,2.3 产生式表示法,是目前人工智能中使用最多的一种知识表示方法2.3.1 产生式表示的基本方

29、法 事实的表示 规则的表示 产生式与蕴含式的区别 产生式与条件语句的区别2.3.2 产生式系统的基本结构及过程2.3.3 产生式系统的控制策略2.3.4 产生式系统的类型2.3.5 产生式系统的特性,36,产生式表示的基本方法-事实的表示,事实的定义 事实是断言一个语言变量的值或断言多个语言变量之间关系的陈述句.语言变量的值或语言变量之间的关系可以是数字、词等.例如：“雪是白的”，其中“雪”是语言变量，“白的”是语言变量的值；“王峰热爱祖国”，其中，“王峰”和“祖国”是两个语言变量“热爱”是语言变量之间的关系。事实的表示 确定性知识，事实可用如下三元组表示：（对象，属性，值）或（关系，对象1，

30、对象2）其中，对象就是语言变量。例如：(Snow,color,White)或（雪，颜色，白）(Love,Wangfeng,Country)或（热爱，王峰，祖国）非确定性知识、事实可用如下四元组表示：（对象，属性，值，可信度因子）其中，“可信度因子”是指该事实为真的相信程度。例如（Like,Liming,Computer,0.9）,产生式表示的基本方法-规则知识的表示,知识的表示方法 1.确定性规则知识的产生式表示PQ 或 IF P THEN Q 其中，P是产生式的前提；Q是一组结论或操作，用于指出前提P所指示的条件被满足时,应该得出的结论或应该执行的操作。2.不确定性规则知识的产生式表示 PQ

31、（置信度）或 IF P THEN Q（置信度）其中，P是产生式的前提；Q是一组结论或操作。已知事实与前提中所规定的条件不能精确匹配时，只要按照“置信度”的要求达到一定的相似度，就认为已知事实与前提条件相匹配，再按照一定的算法将这些可能性（或不确定性）传递到结论。,38,产生式表示的基本方法-产生式与条件语句的区别,前件结构不同 产生式的前件可以是一个复杂的的结构 传统程序设计语言中的左部仅仅是一个布尔表达式控制流程不同 满足前提条件的规则被激活，但不一定被立即执行，能否执行将取决于冲突消解策略 传统程序设计语言中是严格地从一个条件语句向其下一个条件语句传递。,39,产生式系统的基本结构及过程-

32、系统结构及其说明（一）,1.综合数据库（亦称事实库）(1)存放求解问题的各种当前信息 如：问题的初始状态 输入的事实 中间结论及最终结论等(2)用于推理过程的规则匹配推理过程中，当规则库中某条规则的前提和综合数据库的已知事实匹配时，该规则被激活，由它推出的结论将被作为新的事实放入综合数据库，成为后面推理的已知事实。2.规则库 用于存放与求解问题有关的所有规则的集合 规则库包含了问题领域中的一般性知识，是产生式系统问题求解的基础，须重视知识的完整性、一致性、准确性、灵活性和知识组织的合理性,控 制 系 统,规 则 库,综合数据库,40,产生式系统的基本结构及过程-系统结构及其说明（二）,3.控制

33、系统 控制系统的主要作用：亦称推理机构。是规则的解释程序，用于控制整个产生式系统的运行，决定问题求解过程的推理线路。控制系统的主要任务：(1)匹配：按一定策略从规则库种选择规则与综合数据库中的已知事实进行匹配。所谓匹配是指把所选规则的前提与综合数据库中的已知事实进行比较，若事实库中存的事实与所选规则前提一致，则称匹配成功，该规则可被使用；否则，称匹配失败，该规则不可用于当前推理。(2)冲突消解：对匹配成功的规则，按照某种策略从中选出一条规则执行。(3)执行操作：对所执行的规则，若其后件为一个或多个结论，则把这些结论加入综合数据库；若其后件为一个或多个操作时，执行这些操作。检查综合数据库中是否包

34、含有问题的目标，若有，则停止推理。(4)路径解释：在问题求解过程中，记住应用过的规则序列，以便最终能够给出问题的解的路径。,41,产生式系统的基本结构及过程-系统结构及其说明（三）,控制系统的基本过程(1)初始化综合数据库，即把欲解决问题的已知事实送入综合数据库中；(2)检查规则库中是否有未使用过的规则，若无转(7)；（FOR）(3)检查规则库的未使用规则中是否有其前提可与综合数据库中已知事实相匹配的规则，若有，形成当前可用规则集；否则转(6)；(4)按照冲突消解策略，从当前可用规则集中选择一个规则执行，并对该规则作上标记。把执行该规则后所得到的结论作为新的事实放入综合数据库；如果该规则的结论

35、是一些操作，则执行这些操作；(5)检查综合数据库中是否包含了该问题的解，若已包含，说明解已求出，问题求解过程结束；否则，转(2)；(6)当规则库中还有未使用规则，但均不能与综合数据库中的已有事实相匹配时，要求用户进一步提供关于该问题的已知事实，若能提供，则转(2)；否则，执行下一步；(7)若知识库中不再有未使用规则，也说明该问题无解，终止问题求解过程。说明：从第(3)步到第(5)步的循环过程实际上就是一个搜索过程,42,产生式系统的基本结构及过程-产生式系统的例子（一）,动物识别系统 该系统可以识别老虎、金钱豹、斑马、长颈鹿、企鹅、信天翁这6种动物。其规则库包含如下15条规则：r1 IF 该动

36、物有毛发 THEN 该动物是哺乳动物 r2 IF 该动物有奶 THEN 该动物是哺乳动物r3 IF 该动物有羽毛 THEN 该动物是鸟r4 IF 该动物会飞 AND 会下蛋 THEN 该动物是鸟r5 IF 该动物吃肉 THEN 该动物是食肉动物r6 IF 该动物有犬齿 AND 有爪 AND 眼盯前方 THEN 该动物是食肉动物r7 IF 该动物是哺乳动物 AND 有蹄 THEN 该动物是有蹄类动物r8 IF 该动物是哺乳动物 AND 是嚼反刍动物 THEN 该动物是有蹄类动物r9 IF 该动物是哺乳动物 AND 是食肉动物 AND 是黄褐色 AND 身上有暗斑点 THEN 该动物是金钱豹,43

37、,产生式系统的基本结构及过程-产生式系统的例子（二）,r10 IF 该动物是哺乳动物 AND 是食肉动物 AND 是黄褐色 AND 身上有黑色条纹 THEN 该动物是虎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 该动物是

38、鸟 AND 善飞 THEN 该动物是信天翁 其中，ri(i=1,2,.,15)是规则的编号初始综合数据库包含的事实有：动物有暗斑点，有长脖子，有长腿，有奶，有蹄 这些规则的部分推理网络如下图所示,44,产生式系统的基本结构及过程-产生式系统的例子（三）,图中最上层的结点称为“假设”或“结论”中间结点称为“中间假设”；终结点（叶结点）称为“证据”或“事实”每个“结论”都是本问题的一个目标，所有“假设”构成了本问题的目标集合,长颈鹿,斑马,长脖子,长腿,暗斑点,有蹄类,黑条纹,有蹄,哺乳动物,嚼反刍动物,有毛,r2,r7,r8,r11,r12,有奶,r1,45,产生式系统的基本结构及过程-产生式系

39、统的例子（四）,推理机的工作过程(1)先从规则库中取出第一条规则r1，检查其前提是否可与综合数据库中的已知事实相匹配。r1的前提是“有毛发”，但事实库中无此事实，故匹配失败。然后取r2，该前提可与已知事实“有奶”相匹配，r2被执行，并将其结论“该动物是哺乳动物”作为新的事实加入到综合数据库中。此时，综合数据库的内容变为：动物有暗斑，有长脖子，有长腿，有奶，有蹄，是哺乳动物(2)再从规则库中取r3，r4，r5，r6进行匹配，均失败。接着取r7，该前提与已知事实“是哺乳动物”相匹配，r7被执行，并将其结论“该动物是有蹄类动物”作为新的事实加入到综合数据库中。此时，综合数据库的内容变为：动物有暗斑，

40、有长脖子，有长腿，有奶，有蹄，是哺乳动物，是有蹄类动物(3)此后，r8，r9，r10均匹配失败。接着取r11，该前提“该动物是有蹄类动物 AND 有长脖子 AND 有长腿 AND 身上有暗斑”与已知事实相匹配，r11被执行，并推出“该动物是长颈鹿”。由于“长颈鹿”已是目标集合中的一个结论，即已推出最终结果，故问题求解过程结束。说明：上述规则仅是一种直接表示方式，用三元组表示r15如下：r15：IF（动物，类别，鸟）AND（动物，本领，善飞）THEN（动物，名称，信天翁）,46,产生式系统的控制策略,分为不可撤回(Irrevocable)方式、试探性(Tentative)方式1.不可撤回方式（爬

41、山法）是一种“一直往前走”不回头的方式，类似于中国象棋中为过河卒子的规定。它利用问题给定的局部知识来决定选用那条规则的。即根据当前已知的局部知识选取一条规则作用于当前综合数据库，接着再根据新状态继续选取规则，搜索过程一直进行下去，不必考虑撤回用过的规则。不理想规则的应用会多用了一些规则，但仍能找到解。优点是控制过程简单，缺点是当问题有多个解时不一定能找到最优解2.试探性方式 可分为回溯(Backtracking)方式和图搜索(Graph-search)方式。(1)回溯方式 是一种碰壁回头的方式。即在问题求解过程中，允许先试一试某条规则，如果以后发现这条规则不合适，则允许退回去，再另选一条规则来

42、试。需要解决两个主要问题，一是如何确定回溯条件，二是如何减少回溯次数 是一种完备而有效的策略，它容易实现且占内存容量较小。(2)图搜索方式 图搜索方式是一种用图或树把全部求解过程记录下来的方式。由于它记录了已试过的所有路径，因此便于从中选取最优路径。图搜索方式与回溯方式的主要区别在于，回溯方式抹去了所有引起失败的试探路径，而图搜索方式则记住了已试过的所有路径。,产生式系统的推理方式有正向推理、反向推理和双向推理三种：1.正向推理：也称为数据驱动方式或自底向上的方式；从已知事实出发，通过规则库求得结论，便于宽度优先搜索。其推理过程是：1）规则库中的规则的前件与综合数据库中的事实进行匹配，得到匹配

43、的规则集合。2）使用冲突解决算法，从匹配规则集合中选择一条规则作为启用规则。3）执行启用规则的后件，将该启用规则的后件送入综合数据库并对综合数据库进行必要的修改。重复这个过程直至达到目标。正向推理的典型系统：CLIPS（C语言集成产生式系统）优点是简单明了且能求出所有解 缺点是执行效率较低，原因是它驱动了一些与问题无关的规则，具有一定的盲目性。,产生式系统的类型-按推理方向,2.反向推理：也称为目标驱动方式或自顶向下的方式；从目标（作为假设）出发，反向使用规则，求得已知事实；便于深度优先搜索；其推理过程是：1）规则库中的规则后件与目标事实进行匹配，得到匹配的规则集合。2）使用冲突解决算法，从匹

44、配规则集合中选择一条规则作为启用规则。3）将启用规则的前件作为子目标。重复这个过程直至个子目标均为已知事实，则反向推理过程成功结束。反向推理的典型系统：PROLOG优点是不寻找无用数据，不使用与问题无关的规则。因此，对那些目标明确的问题，使用反向推理方式是一种最佳选择。,产生式系统的类型-按推理方向,3.双向推理：推理从两个方向同时进行，直至某个到达相同的中间事实则成功结束。这种推理方式较正向或反向推理所形成的推理网络小，从而推理效果更高。,产生式系统的类型-按推理方向,产生式表示法,正向推理If A Then B，If B Then C，If C Then D反向推理：规则重写为If D T

45、hen C，If C Then B，If B Then A,51,产生式系统的类型-按规则库的性质及结构（一）,可交换的产生式系统 是一种对规则的使用次序无关的产生式系统 可交换性是指任意交换规则的使用次序而不会影响对问题的求解 假设DB是综合数据库，RB是规则库，DBi(i=1,2,)是第i次使用规则后得到的新的综合数据库，RS RB是一个可作用于DBi的规则集合。若一个产生式系统可交换，则其RB和每一个DBi都应具有如下性质：对任一规则rj RS(j=1,2,)，它作用于DBi得到新的综合数据库DBi+1，RS仍然是DBi+1的可用规则集。如果DBi满足目标条件，则用RS中的任一规则rj作

46、用于DBi，得到的DBi+1仍然满足目标条件。若对DBi使用某一规则序列r1,r2,rk得到一个新的综合数据库DBk，则当改变这些规则的使用次序后，仍然可得到DBk。从可交换产生式系统的上述性质可以看出，其综合数据库的内容是递增的，即对任何规则序列r1,r2,rg，其作用于DB 后所得到的综合数据库DB1，DB2，DBg之间存在如下关系：DB1 DB2 DBg 这说明在可交换产生式系统中，其规则的结论部分总是包含着新的内容，一旦执行该规则就会把这些新的内容添加到综合数据库中。,52,产生式系统的类型-按规则库的性质及结构（二）,例2.6 设给定一个整数集合a，b，c，可通过把集合中任意一对元素

47、的乘积作为新元素添加到集合中的办法来扩大该整数集，要求通过若干次操作后能生成所需的整数集合。用产生式求解这个问题时，综合数据库DB可用集合来表示，初始状态为a，b，c 目标状态为a，b，c，ab，bc，ac 规则库中包含的规则有：r1:IF a，b，c THEN a，b，c，ab r2:IF a，b，c THEN a，b，c，bc r3:IF a，b，c THEN a，b，c，ac 显然，无论先使用哪一条规则都可由初始状态达到目标状态。因此，上述由DB和RB所构造的产生式系统是一个可交换的产生式系统，并具有可交换产生式系统三个性质。可交换产生式系统的可交换性，使得其求解过程只需要搜索其中的任意

48、一条路经，就能达到目标，而不必进行回溯。这种系统的求解过程可采用不可撤回的控制方式。,53,产生式系统的类型-按规则库的性质及结构（三）,可分解的产生式系统 这种方法把一个较大或较复杂的问题分解成若干个较小或较简单的问题，然后通过对这些较小或较简单问题的求解来得到整个问题的解。可分解的产生式系统是把一个整体问题分解成若干个子问题，然后再通过对这些子问题的求解来得到整个问题解的一种产生式系统。例2.7 设综合数据库的初始状态为C，B，Z，目标状态为 M，M，M，规则库中有如下规则：r1：CD，L r2：CB，M r3：BM，M r4：ZB，B，M 解决该问题时，可先把初始综合数据库分为三个子库，

49、然后对这三个子库分别应用规则库中的相应规则进行求解。其求解过程如下图所示。,54,产生式系统的类型-按规则库的性质及结构（三）,C,B,Z,C,B,Z,D,L,B,M,M,M,B,B,M,D,L,B,M,M,M,B,M,B,M,M,M,M,M,M,M,M,M,M,M,M,r1,r2,r3,r4,r3,r3,r3,55,产生式系统的类型-按规则库的性质及结构（四）,可恢复的产生式系统 是指那种采用回溯控制方式的产生式系统 其求解问题的方法是：当执行某条规则后，如果发现所得到的新的综合数据库不可能求出问题的解，就立即撤消由该规则所产生的结果，使综合数据库恢复到先前的状态，然后再另选别的规则继续求解

50、。它既可以向综合数据库中添加新的内容，又可以从综合数据库中删除或修改老的内容。这种求解问题的方法，更符合人们的一般习惯。,练习,针对猴子摘香蕉问题，给出产生式系统描述。,57,产生式系统的特点,主要优点自然性 产生式表示法用“如果，则”的形式表示知识，这种表示形式与人类的判断性知识基本一致，既直观、自然，又便于进行推理。模块性 产生式规则是规则库中最基本的知识单元，各规则之间只能通过综合数据库发生联系，而不能相互调用，从而增加了规则的模块性，有利于对知识的增加、删除、修改和扩充。有效性 产生式知识表示法既可以表示确定性知识，又可以表示不确定性知识，既有利于表示启发性知识，又有利于表示过程性知识