数据挖掘与知识发现(讲稿21---知识表示).docx

《数据挖掘与知识发现(讲稿21---知识表示).docx》由会员分享，可在线阅读，更多相关《数据挖掘与知识发现(讲稿21---知识表示).docx（30页珍藏版）》请在三一办公上搜索。

1、装订线第2章 知识表示知识表示是人工智能研究中极为重要的研究课题之一。无论应用人工智能技术解决什么问题，首先遇到的就是所涉及的各类知识如何加以表示。不同的知识有不同的表示方法，研究知识表示方法，不单是解决如何将知识存储在计算机中，更重要的是应该能够方便和正确地使用知识。合理的知识表示，可以使问题求解变得容易，并且有较高的求解效率。评价一个好的知识表示系统应具有以下几点： 具有表示某个专门领域所需要的知识能力，并保证知识库中的知识是相容的； 具有从已知知识推导出新知识的能力，容易建立表达新知识所需要的新结构； 便于新知识的获取，最简单的情况是能够由人直接输入知识到知识库中； 便于将启发式知识附加

2、到知识结构中，以便把推理集中在最希望的方向上。为了实现上述目标，人们至今已提出了几十种甚至上百种的知识表示方法。但没有一种表示能包打天下。较为常见的知识表示方法有：l 一阶谓词逻辑表示 l 产生式表示或称规则表示 l 语义网表示 l 框架表示 l 面象对象表示l 过程表示l 脚本表示l 神经元表示l 特性表表示2.1一阶谓词逻辑表示谓词逻辑是一种形式语言，也是目前能够表达人类思维活动的一种最精确的语言。它与人类的自然语言比较接近，即可方便地存储到计算机中，又可被计算机进行精确处理。因此，谓词逻辑是最早且最主要用于人工智能知识描述的方法之一。它是一种基于数理逻辑的知识表示方式。而数理逻辑是一门研

3、究推理的科学，它作为人工智能的基础，在人工智能的发展中占有重要地位。人工智能中用到的逻辑可分为两大类： 一阶经典命题逻辑和谓词逻辑 除经典以外的那些逻辑2.1.1一阶谓词逻辑表示的逻辑基础谓词逻辑是在命题逻辑的基础上发展起来的，为此先讨论一阶谓词逻辑知识表示中所需要的一些逻辑基础。如命题、谓词、连接词、量词、谓词公式等。 1. 命题和真值定义2.1：一个陈述句称为一个断言。凡有真假意义的断言称为命题。（即可以确定真假意义的陈述句）注： 命题的意义通常称为真值，它只有真（T）假（F）两种情况。 在命题逻辑中，命题通常用大写的英文字母来表示。一个命题不能同时为真又为假。 一个命题可在一定条件下为真

4、，在另一条件下为假。如，P：“北京今天有雨”，需根据当天的情况决定其真值。 没有真假意义的感叹句、疑问句等都不是命题。如，P：今天好冷呀！；Q：今天的温度有多少度？ 命题的优点是简单、明确；缺点是无法描述客观事物的结构及其逻辑特征，也无法表示不同事物间的共性。如，“杨青是教师”和“李文是教师”这两个命题，用命题逻辑表示时，无法把两人都是教师这一共同特征表示出来。 2. 论域和谓词 论域是由所讨论对象之全体构成的非空集合。论域中的元素称为个体。论域又称个体域。在谓词逻辑中，命题是用谓词表示的。一个谓词可分为：谓词名和个体两部分。其中，个体是用来表示某个独立存在的事物或者某个抽象的概念；谓词名是用

5、来表示个体的性质、状态或个体之间的关系等。通常，谓词名用大写英文字母表示，个体用小写英文字母表示。如：王宏是学生 谓词表示为：STUDENT（Wanghong） 桂林山水甲天下 谓词表示为：甲天下（桂林山水） 桂林在广西的北部 谓词表示为：在（北部，桂林，广西） 广西师大校园坐落在桂林 谓词表示为：坐落在（广西师大校园，桂林） 全州是桂林的县 谓词表示为：县（全州，桂林） x6 谓词表示为：Greater(x,6) 王宏的父亲是教师 谓词表示为：TEACHER（father(Wanghong)） 谓词的形式定义如下：定义2.2 设D是个体域，P:是一个映射，其中 则称P是一个n元谓词。记为：，

6、是个体。注：在谓词中，个体可以是常量、变元或函数。函数的定义形式为： 定义2.3 设D是个体域，的一个映射，则称是D上的一个n元函数。记作：，是个体。说明： 谓词和函数的定义形式相似，但却是两个不同的概念。 谓词的真值是T或F，而函数无真值可言，其值是D中的某个个体。 谓词实现的是从个体域中的个体到T或F的映射，而函数实现的是同一个体域中从一个个体到另一个个体的映射。 在谓词逻辑中，函数本身不能单独使用，它必须嵌入到谓词中。 如果中的个体都是常量、变元或函数，则称其为一阶谓词。若某个本身又是另一个一阶谓词，则称它为二阶谓词。3. 连接词和量词连接词是用来连接简单命题，并由简单命题构成复合命题的

7、逻辑运算符号。在一阶谓词逻辑中，有5个连接词和2个量词。由于命题逻辑可看作谓词逻辑的一种特殊形式，因此5个连接词同样适应于命题逻辑，但2个量词仅适应在于谓词逻辑。：称为“非”。它表示其后命题的否定：称为“析取”。它表示所连接的两个命题之间具有“或”的关系：称为“合取”。它表示所连接的两个命题之间具有“与”的关系：称为“条件”或“蕴含”。它表示“若则”的语义。如，表示“P蕴含Q”，读作：“如果P，则Q”，其中P称为条件的前件，Q称为条件的后件。：称为“双条件”。它表示“当且仅当”的语义。如，表示P当且仅当Q，即读作“P当且仅当Q”。谓词逻辑真值表PQTTFTTTTTFFTFFFFTTTFTFFF

8、TFFTT在一阶谓词逻辑中，引入了2个量词符号：全程量词符号和存在量词符号。-所有的，任一个-至少有一个，存在有量词是由量词符号和被其量化的变元所组成的表达式，是用来对谓词中的个体作出量的规定。如，“对论域中的所有个体”，表示为；“对论域中的某个个体”，表示为。命题为真，当且仅当论域中的所有，都有为真命题为真，当且仅当论域中至少存在一个，使得为真 4. 项与合式公式在一阶谓词逻辑中，合法的表达式称为合式公式（即谓词公式）。定义2.4 项满足如下规则：（1） 单独一个个体词是项；（2） 若是项，是n元函数，则是项；（3） 由（1）、（2）生成的表达式是项。可见，项是把个体常量、个体变量和函数统一

9、起来的概念。定义2.5 原子谓词公式的含义为： 若是项，P是谓词符号，则称P()为原子谓词公式。定义2.6 满足如下规则的谓词演算可得到合式公式：（1） 单个原子谓词公式是合式公式；（2） 若A是合式公式，则也是合式公式；（3） 若A、B是合式公式，则也都是合式公式；（4） 若A是合式公式，是项，则和也都是合式公式。注：在合式公式中，连接词之间的优先级顺序为： 5. 自由变元和约束变元当一个谓词公式含有量词时，通常把位于量词后面的单个谓词或者用括弧括起来的合式公式称为该量词的辖域。辖域内与量词中同名的变元称为约束变元，不受约束的变元称为自由变元。如 这里，是的辖域，其中的是的约束变元；中的是自

10、由变元。公式中所有的都是自由变元。注：在谓词公式中，变元的名字是无关紧要的，可以把一个名字换成别的名字。换名时注意两点：当对量词辖域内的约束变元更名时，必须把同名的约束变元都统一换成另外一个相同的名字，且不能与辖域内的自由变元同名；当对辖域内自由变元更名时，不能改成与约束变元同名。如上例可表示为：命题公式是谓词公式的一种特殊情况，也可用连接词把单个命题连接起来构成合式公式。如，都是命题公式。2.1.2谓词逻辑的知识表示方法谓词逻辑不仅可以用来表示事物的状态、属性、概念等事实性知识，也可以用来表示事物的因果关系。对事实性知识，常用符号连接起来的谓词公式表示。对事物间的因果关系，通常用蕴含式表示。

11、如，对“如果则”可表示为“”当用谓词逻辑表示知识时，先要根据所表示的知识定义谓词，然后再用连接词或者量词把这些词连接起来，形成一个谓词公式。例1 用谓词逻辑表示知识“每个人都有一个父亲”。谓词： PERSON（x）：表示x是人 HASFATHER（x,y）：表示x有父亲y则该知识可用谓词表示为： 例2 用谓词逻辑表示知识“所有教师都有自己的学生”。谓词： TEACHER（x）：表示x是教师 STUDENT（y）：表示y是学生 TEACHERS（x,y）：表示x是y的老师则该知识可用谓词表示为： 例3 用谓词逻辑表示知识“所有的整数不是偶数就是奇数”。谓词： I(x): x是整数 E(x):x是

12、偶数 O(x):x是奇数 则该知识可用谓词表示为： 例4 用谓词逻辑表示知识：王宏是计算机系的一名学生。李明是王宏的同班同学。凡是计算机系的学生都喜欢编程序。谓词： COMPUTER(x): 表示x是计算系的学生 CLASSMATE(x,y): 表示x是y的同班同学 LIKE(x,y): 表示x喜欢y则上述知识表示为： COMPUTER(Wanghong) CLASSMATE(Liming,Wanghong) 2.1.3谓词逻辑表示的应用 示例1 机器人移盒子问题设在一房间里，c处有一个机器，a和b处各有一张桌子，分别称为a桌和b桌，a桌上有一盒子，如图所示。要求机器人从c处出发把盒子从a桌拿

13、到b桌子上，然后再回到c处。试用谓词逻辑来描述机器人的行动过程。分析：此例中的谓词公式，不仅要用来描述事物的状态、位置，而且还要用来表示动作。定义的谓词：TABLE(x)：x是桌子 EMPTY(y)：y手中是空中 AT(y,z): y在z的附近 HOLDS(y,w): y拿着w ON(w,x)：w在x桌面上由此知，问题的初始状态是： 问题的目标状态： AT(robot,c) AT(robot,c) EMPTY(robot) EMPTY(robot) ON(box,a) ON(box,b)TABLE(a) TABLE(a)TABLE(b) TABLE(b)显然，机器人行动的目标是把问题的初始状态

14、转换为目标状态。而要实现问题的状态转换，则需要完成一系列的操作。对于每个操作，一般都可分为条件和动作部分。条件部分用来说明执行该操作必须具备的先决条件，动作部分给出了该操作对问题状态的改变情况。条件部分可用谓词公式来表示，动作部分则是通过在执行该操作前的问题状态中删去和增加相应的谓词来实现。本例中，机器人需要执行的操作： Goto(x,y): 从x处走到y处 Pickup(x): 在x处拿起盒子 Setdown(x): 在x处放下盒子其对应的条件和动作如下： Goto(x,y) 条件：AT(robot,x) 动作：删除表: AT(robot,x) 添加表: AT(robot,y)Pickup(

15、x) 条件：ON(box,x),TABLE(x),AT(robot,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)由此得出，机器人行动规划问题的求解过程为： 示例2 机器人摞积木问题 设机器人有一只机械手，要处理的世界有一张桌子，桌子可堆放若干相同的积木块。机械手有4个操作积木的典型动作：从桌面

16、上拣起一块积木；将手中的积木放到桌面上；在积木上再摞上一块积木；从积木上面拣起一块积木。积木世界的布如图所示。分析：定义的谓词：CLEAR(x)：积木x上是空的 ON(x,y)：积木x在积木y的上面 ONTABLE(x): 积木x在桌面上 HOLDING(x): 机械手抓住x HANDEMPTY：机械手是空的由此知，问题的初始状态是： 问题的目标状态： CLEAR(B) ON(B,C) ON(C,A) ON(A,B) CLEAR(C) ONTABLE(B) ONTABLE(A)HANDEMPTY本例中，机械手需要执行4个操作： Pickup(x): 从桌面上拣起一块积木x Putdown(x)

17、: 将手中的积木放到桌面上 Stack(x,y): 在积木x上再摞上一块积木y Unstack(x,y): 从积木x上面拣起一块积木y其对应的条件和动作如下： Pickup(x) 条件： ONTABLE(x)，CLEAR(x), HANDEMPTY 动作： 删除表ONTABLE(x)，HANDEMPTY 添加表HOLDING(x)Putdown(x) 条件：HOLDING(x) 动作：删除表HOLDING(x) 添加表HANDEMPTY，ONTABLE(x)，CLEAR(x)Stack(x,y) 条件：HOLDING(x)，CLEAR(y) 动作：删除表HOLDING(x)，CLEAR(y)

18、添加表HANDEMPTY，ON(x,y)，CLEAR(x)Unstack(x,y) 条件：，HANDEMPTY,CLEAR(y) 动作：删除表HANDEMPTY，ON(y,x) 添加表CLEAR(x),HOLDING(y) 示例3 猴子摘香蕉问题设房间里有一只猴子（即机器人），位于a处。C处上方的天花板上有一串香蕉，猴子想吃，但摸不着。房间b处还有一个箱子，如果猴子站到箱子上就可以摸着天花板。用谓词逻辑描述猴子得到香蕉的行动规划。分析：定义谓词： AT(x,y): 表示x在y处 ONBOX:表示猴子在箱子上面 BH:猴子得到香蕉由此知，问题的初始状态是： 问题的目标状态： AT(Monkey,

19、a) AT(Monkey,c) AT(Box,b) AT(Box,c) ONBOX ONBOX HB HB本例中，猴子需要执行的操作为： Goto(u,v): 表示猴子从u处走到v处 Pushbox(v,w): 表示猴子推着箱子从v处移到w处 Climbbox: 表示猴子爬上箱子 Grasp: 表示猴子摘取香蕉其对应的条件和动作如下：Goto(u,v) 条件：AT(Monkey,u),ONBOX 动作：删除表AT(Monkey,u) 添加表AT(Monkey,v) Pushbox(v,w) 条件：ONBOX，AT(Monkey,v)，AT(BOX,v) 动作：删除表AT(Monkey,v)，A

20、T(BOX,v) 添加表AT(Monkey,w), AT(BOX,w)Climbbox 条件：ONBOX，AT(Monkey,c), AT(BOX,c) 动作：删除表ONBOX 添加表ONBOX Grasp 条件：HB，ONBOX，AT(BOX,c) 动作：删除表HB 添加表HB2.1.4谓词逻辑表示的特性逻辑表示法的主要特点是建立在某种形式逻辑基础上的，并利用了逻辑方法研究推理规律，即条件与结论之间的蕴含关系。逻辑表示法的主要优点： 符号简单，描述易于理解； 自然、严密、灵活、模块化； 具有严格的形式定义； 每项事实仅需表示一次； 具有证明过程中所使用的推理规则； 利用定理证明技术可双从老的

21、事实推出新的事实。逻辑表示法主要缺点： 知识表示能力差 难于表示过程式和启发式知识； 由于缺乏组织原则，利用该方法表示知识库难于管理； 由于弱证明过程，当事实的数目增大时，易产生组合爆炸。 系统效率低2.2 产生式表示法“产生式”这一术语，是由美国数学家、逻辑学家波斯特（E.Post）1943年提出的。他在研究一种称为波斯特机的计算模型时首次使用这一术语。波斯特机的目的在于证明它和“图灵机”具有相同的计算能力。在该模型中，Post主要用类似于文法的规则对符号串做替换运算，并把其中的每一条符号变换规则称为一个产生式。后在60年代由Newell（纽厄尔）和Simon（西蒙）等人做了进一步的研究和发

22、展，并将该方法用于斯坦福大学建立的第一个专家系统DENDRAL中。1972年，Newell和Simon在研究人类的认知模型中又开发了基于规则的产生式系统。（所以，产生式表示法又称为产生式规则表示法）目前，产生式表示法已成为AI中应用最多的一种知识表示模式，尤其在专家系统方面，许多成功的专家系统都采用产生式知识表示方式。2.2.1 产生式表示法的基本方法产生式表示法可很容易地描述事实、规则以及它们的不确定性度量。1. 事实的表示事实可看作是断言一个语言变量的值或断言多个变量之间关系的陈述句。其中，语言变量的值或语言变量之间的关系可以是数字，也可以是一个词等。如雪是白的 （“雪”是语言变量；“白的

23、”为语言变量的值）王峰热爱祖国 （“王峰”、“祖国”是语言变量；“热爱”为语言变量之间的关系）在产生式表示法中，对确定性知识，一个事实可用一个三元组表示： （对象，属性，值） or （关系，对象1，对象2）对不确定性知识，一个事实可用一个四元组表示： （对象，属性，值，可信度因子）其中，“对象”就是语言变量；“可信度因子”是指该事实为真的相信程度，可用01之间的数来表示。事实的表示，在机器内部可用一个表来实现。如（Snow,Color,White）或（雪，颜色，白的）（Love,Wangfeng,Country）或（热爱，王峰，祖国）2. 规则的表示规则描述的是事物间的因果关系。规则的产生式表

24、示常称为产生式规则，简称产生式或规则。其基本形式为： 或者 IF THEN 含义是：如果前提P满足，则可推出结论Q或执行Q所规定的操作。这里，P是产生式的前提（或前件），它给出了该产生式可否使用的先决条件，由事实的逻辑组合来构成；Q是一组结论（或操作、或后件），它指出当前提P满足时，应该推出的结论或应该执行的操作。例如： IF 动物有犬齿 AND 有爪 AND 眼盯前方 THEN 该动物是肉食动物3. 产生式与蕴含式的区别l 蕴含式只能表示确定性知识，其真值只能取真或假；而产生式既可表示确定性知识，又可表示非确定性知识；如，在专家系统MYCIN中有如下产生式 IF 本生物的染色斑是革兰氏阴性，

25、 本微生物的形状呈杆状， 病人是中间宿主 THEN 该微生物是绿脓杆菌，置信度为0.6l 在产生式表示中，决定一个产生式是否可用是检查已知事实与前提中所规定的条件相匹配来实现的，并且匹配可以精确，也可不精确；而谓词逻辑中的蕴含式，其匹配则要求一定是精确的。2.2.2 产生式系统的基本结构把用产生式知识表示方法构造的智能系统称为产生式系统。一个产生式系统的基本结构包括：综合数据库、规则库和控制系统三个主要部分。其关系如图所示。1. 综合数据库综合数据库也称事实库，是一个用来存放与求解问题有关的各种当前信息的数据结构。如，问题的初始状态、输入的事实、推理得到的中间结论及最终结构等。 2. 规则库规

26、则库是一个用来存放与求解问题有关的所有规则的集合。它包含了将问题从初始状态转换成目标状态所需要的所有变换规则。在推理过程中，当规则库中某条规则的前提可以和综合数据库中的已知事实相匹配时，该规则被激活，由它推出的结论将被作为新的事实放入综合数据库，成为后面推理的已知事实。 3. 控制系统控制系统也称推理机构，它由一组程序组成，用来控制整个产生式系统的运行，决定问题求解过程的推理线路，实现对问题的求解。其主要工作如下： 按一定策略从规则库中选择规则与综合数据库中的已知事实进行匹配。若匹配成功，该规则被激活；否则，匹配失败，该规则不可用于当前推理。 当匹配成功的规则多于一条时，推理机构应该能够按照某

27、种策略从中选出一条规则去执行； 对要执行的规则，如果该规则的后件不是问题的目标，则当其为一个或多个结论时，把这些结论加入到综合数据库中；当其为一个或多个操作时，执行这些操作； 对要执行的规则，如果该规则的后件满足问题的结束条件，则停止推理； 在问题求解过程中，记住应用过的规则序列，以便最终能够给出问题的解路径。示例一个用于识别老虎、金钱豹、斑马、长颈鹿、企鹅、信天翁这6种动物的产生式系统。其规则库包含15条规则： IF 该动物有毛发 THEN 该动物是哺乳动物 IF 该动物有奶 THEN 该动物是哺乳动物 IF 该动物有羽毛 THEN 该动物是鸟 IF 该动物会飞 AND 会下蛋 THEN 该

28、动物是鸟 IF 该动物吃肉 THEN 该动物是肉食动物 IF 该动物有犬齿 AND有爪 AND 眼盯前方 THEN 该动物是肉食动物 IF该动物是哺乳动物 AND 有蹄 THEN 该动物是有蹄类动物 IF该动物是哺乳动物 AND 有嚼反刍动物 THEN该动物是有蹄类动物 IF该动物是哺乳动物 AND 是肉食动物 AND 是黄褐色 AND 身上有暗斑点 THEN 该动物是金钱豹 IF 该动物是哺乳动物 AND是肉食动物 AND 是黄褐色 AND 身上有黑色条纹THEN 该动物是虎 IF该动物是有蹄类动物 AND 有长脖子 AND 有长腿 AND 身上有暗斑点 THEN 该动物是长颈鹿 IF该动物

29、是有蹄类动物 AND身上有黑色条纹 THEN 该动物是斑马 IF该动物是鸟 AND有长脖子 AND 有长腿 AND 不会飞场THEN 该动物是驼鸟 IF 该动物是鸟 AND 会游泳 AND 不会飞 AND 有黑白二色 THEN 该动物是个鹅 IF该动物是鸟 AND 善飞 THEN 该动物是信天翁其综合数据库中存放如下事实：动物有暗斑，有长脖，有长腿，有奶，有蹄推理过程为：（1）先从规则库中取出第一条规则，检查其前提是否与综合数据库中的已知事实相匹配。的前提是“有毛发”，但事实库中没有这一事实，故匹配失败。然后取，该前提提可与事实库中的已知事实“有奶”本匹配，被执行，并将其结论“该动物是哺乳动物

30、”作为新的事实加到综合数据库中。此时，综合数据库的内容变为： 动物有暗斑，有长脖，有长腿，有奶，有蹄，是哺乳动物（2）再从规则库中取进行匹配，结果均失败。接着取匹配，并将其结论加综合数据库中，此时，综合数据库的内容变为： 动物有暗斑，有长脖，有长腿，有奶，有蹄，是哺乳动物，是有蹄类动物（3）同上方法知匹配，并推出“该动物是长颈鹿”。由于“长颈鹿”已是目标集中的一个结论，故障问题求解到此结束。注：上述规则库中的规则是一种直接表示方式，也可用三元组来表示前提中的事实和后件中的假设。如上例中可表示为： IF （动物，类别，鸟） AND （动物，本领，善飞） THEN （动物，名称，信天翁）2.2.3

31、 产生式系统的基本过程 产生式系统求解问题的过程是一个反复从规则库中选用合适的规则并执行规则的过程。在此过程中，规则的选用策略将直接影响到问题的求解。问题的求解效率取决于搜索策略和产生式系统的知识结构。 初始化综合数据库，把欲解决问题的已知事实送入综合数据库中； 检查规则库中是否存在尚未使用过的规则，若有则执行；否则转； 检查规则库的未使用规则中是否存在有其前提可与综合数据库中已知事实相匹配的规则，若有则从中选择一个；否则转； 执行当前选中规则，并对该规则作上标记，把执行该规则后所得到的结论作为新的事实放入综合数据库；如果该规则的结论是一些操作，则执行这些操作； 检查综合数据库中是否包含了该问

32、题的解，若已包含，则说明已求出解，问题求解过程结束；否则转； 当规则库中还有未使用的规则，但均不能与综合数据库中的已有事实相匹配时，要求用户进一步提供关于该问题的已知事实，若能提供，则转；否则，说明该问题无解，终止问题求解过程； 若知识库中不再有未使用的规则，也说明该问题无解，终止问题求解过程。2.2.4 产生式系统的控制策略在产生式问题求解过程中，当有多条规则可用时，如何从中选择一条作用于当前综合数据库，是一个控制策略问题（也称冲突消解问题）。产生式系统的控制策略总体上可分两类：不可撤回方式和试探性方式(回溯方式、图搜索方式)。 不可撤回方式是一直往前走方式。试探性方式：回溯方式是一种碰壁回

33、头方式。抹去过去所引起失败的试探路径。图搜索方式是一种用图或树把全部求解过程记录下来的方式。记住已试探过的所有路径。2.2.5 产生式系统的类型 1. 按推理方向分类（1）正向推理产生式系统 正向推理也称为数据驱动方式，它是从初始状态出发，朝着目标状态前进，正向使用规则的一种推理方法。所谓正向使用规则，是指以问题的初始状态作为初始综合数据库，仅当综合数据库中的事实满足某条件规则的前提时，该规则才被使用。优点：简单明了且能求出所有解缺点：执行效率低（2）逆向推理产生式系统 逆向推理也称目标驱动方式，它是从目标状态出发，朝着初始状态前进，逆向使用规则的一种推理方法。所谓逆向使用规则，是指以问题的目

34、标状态作为初始综合数据库，仅当综合数据库中的事实满足某条件规则的后件时，该规则才被使用。优点：不寻找无用数据，不使用与问题无关的规则。（3）双向推理产生式系统双向推理是把正向推理和逆向推理结合起来使用的一种推理方式。采用这种方式需要把问题的初始状态和目标状态合并在一起构成综合数据库。 2. 按规则库的性质及结构分类（1）可交换的产生式系统如果一个产生式系统对规则的使用次序是无关的，则称该产生式系统为可交换的产生式系统。所谓可交换性是指这些规则可以任意交换次序而不影响对问题的求解。设DB是综合数据库，RB是规则库，（）是第次使用规则后得到的新的综合数据库，是一个可作用于的规则集合。所谓产生式系统

35、是可交换的，是指其RB和每一个都具有如下性质： 对任一规则，它作用于得到新的综合数据库，仍然是的可用规则集； 如果满足目标条件，则用RS中的任一规则作用于，得到的仍然满足目标条件； 若对使用某一规则序列得到一个新的综合数据库，则当改变这些规则的使用次序后，仍然可得到。从上述性质知，其综合数据库的内容是递增的。即对任何规则序列，作用于DB后所得到的综合数据库之间有如下关系： 示例 设给定一个整数集合，可通过把集合中任意一对元素的乘积作为新元素添加到集合中的办法来扩大该整数集，要求通过若干次操作后能生成所需的整数集合a,b,c,。规则库中包含的规则有： IF a,b,c THEN IF a,b,c

36、 THEN IF a,b,c THEN 显然，用产生式求解这个问题时，综合数据库DB可用集合来表示，其初始状态为 a,b,c ，目标状态为a,b,c,。无论先用哪条规则，都可由初始状态达到目标状态。可交换的产生式系统的可交换性，使得其求解过程只需要搜索其中的任意一条路径，就能达到目标，而不必进行回溯。因此，该系统求解过程可采用不可撤回的控制方式。它无需记录可用规则的作用序列，可节省求解问题的时间，提高求解问题的效率。（2）可分解的产生式系统该法是把一个较大或较复杂的问题分解成若干个较小或较简单的问题，然后通过对这些较小或较简单问题的求解来得到整个问题的解。可分解的产生式系统是把一个整体问题分解

37、成若干子问题，然后再通过对这些子问题的求解来得到整个问题解的一种产生式系统。示例 设综合数据库的初始状态为C，B，Z，目标状态为M，M，M，规则库中有如下重写规则： 解决该问题时，可先把初始综合数据库分为三个子库，然后对这三个子库分别应用规则库中的相应规则进行求解。其求解过程如图所示。（3）可恢复的产生式系统可恢复的产生式系统是指那种采用回溯控制方式的产生式系统。其求解问题的方法是：当执行某条规则后，如果发现所得到的新的综合数据库不可能求出问题的解，就立即撤消由该规则所产生的结果，使综合数据库恢复到先前的状态，然后再另选别的继续求解。它既可向综合数据库中添加新的内容，又可从综合数据库中删除或修

38、改老的内容。这种可解方法，更符合人们的一般习惯。2.2.6 产生式系统的特点优点：自然性、模块性、有效性、一致性。缺点：效率低、不能表示结构性知识2.3 语义网络表示法语义网络是奎廉（J.R.Quillian）1968年在研究人类联想记忆时提出的一种心理学模型，他认为记忆是由概念间的联系实现的。随后，奎廉又把它用作知识表示。1972年，西蒙在他的自然语言理解系统中也采用了语义网络表示法。1975年，享德里克（G.G.Hendrix）又对全称量词的表示提出了语义网络分区技术。目前，语义网络已成为AI中应用较多的一种知识表示方法。2.3.1 语义网络的基本概念1. 什么是语义网络？语义网络是一种用

39、实体及语义关系来表达知识的有向图。其中，结点代表实体，表示各种事物、概念、情况、属性、状态、事件、动作等；弧代表语义关系，表示它所连接的两个实体之间的语义联系。在语义网络中，每个结点和弧都必须带有标识，这些标识用来说明它所代表的实体或语义。从结构上看，语义网络一般是由一些最基本的语义单元构成的，这种最基本的语义单元被称为语义基元。一个语义基元可用如下三元组来表示：（结点1，弧，结点2）例 用语义基元描述“舵鸟是一种鸟”这一事实。当把多个语义基元用相应的语义联系关联在一起时，形成了一个语义网络。2. 基本的语义关系从功能上讲，语义网络可以描述任何事物间的任意复杂关系。但是，这种描述是通过把许多基

40、本的语义关系关联到一起来实现的。基本语义关系是构成复杂语义关系的基石，也是语义网络知识的基础。作为参考，这里给出一些常用的基本语义关系：（1）类属关系类属关系是指具有共同属性的不同事物间的分类关系、成员关系或实例关系。它体现的是“具体与抽象”、“个体与集体”的概念。类属关系的一个最主要特征是属性的继承性。处在具体层的结点可以继承抽象层结点的所有属性。常用的类属关系有：A-Kind-of: 含义为“是一种”，表示一个事物是另一个事物的一种类型； A-Member-of: 含义为“是一员”，表示一个事物是另一个事物的一个成员； Is-a: 含义为“是一个”，表示一个事物是另一个事物的一个实例。 （2）包含关系 包含关系也称聚类关系，是指具有组织或结构特征的“部分与整体”之间的关系。它和类属关系的最主要区别是包含关系一般不具