《数据挖掘与知识发现(讲稿21知识表示).docx》由会员分享,可在线阅读,更多相关《数据挖掘与知识发现(讲稿21知识表示).docx(30页珍藏版)》请在课桌文档上搜索。
1、数据挖掘与知识发现(讲稿21知识表示)知识表示是人工智能研究中极为重要的研究课题之一。不管应用人工智能技术解决什么问题,首先遇到的就是所涉及的各类知识如何加以表示。不一致的知识有不一致的表示方法,研窕知识表示方法,不单是解决如何将知识存储在计算机中,更重要的是应该能够方便与正确地使用知识。合理的知识表示,能够使问题求解变得容易,同时有较高的求解效率。评价一个好的知识表示系统应具有下列几点:具有表示某个专门领域所需要的知识能力,并保证知识库中的知识是相容的;具有从已知知识推导出新知识的能力,容易建立表达新知识所需要的新结构;便于新知识的获取,最简单的情况是能够由人直接输入知识到知识库中;便于将启
2、发式知识附加到知识结构中,以便把推理集中在最希望的方向上。为了实现上述目标,人们至今已提出了几十种甚至上百种的知识表示方法。但没有一种表示能包打天下。较为常见的知识表示方法有: 一阶谓词逻辑表示 产生式表示或者称规则表示 语义网表示 框架表示 面象对象表示 过程表示 脚本表示 神经元表示 特性表表示2.1一阶谓词逻辑表示谓词逻辑是一种形式语言,也是目前能够表达人类思维活动的一种最精确的语言。它与人类的自然语言比较接近,即可方便地存储到计算机中,又可被计算机进行精确处理。因此,谓词逻辑是最早且最要紧用于人工智能知识描述的方法之一。它是一种基于数理逻辑的知识表示方式。而数理逻辑是一门研究推理的科学
3、,它作为人工智能的基础,在人工智能的进展中占有重要地位。人工智能中用到的逻辑可分为两大类:一阶经典命题逻辑与谓词逻辑除经典以外的那些逻辑2.1.1 一阶谓词逻辑表示的逻辑基础谓词逻辑是在命题逻辑的基础上进展起来的,为此先讨论一阶谓词逻辑知识表示中所需要的一些逻辑基础。如命题、谓词、连接词、量词、谓词公式等。1 .命题与真值定义2.1:一个陈述句称之一个断言。凡有真假意义的断言称之命题。(即能够确定真假意义的陈述句)注:命题的意义通常称之真值,它只有真(T)假(F)两种情况。在命题逻辑中,命题通常用大写的英文字母来表示。一个命题不能同时为真又为假。一个命题可在一定条件下为真,在另一条件下为假。如
4、,P:“北京今天有雨”,需根据当天的情况决定其真值。没有真假意义的感叹句、疑问句等都不是命题。如,P:今天好冷呀!;Q:今天的温度有多少度?命题的优点是简单、明确;缺点是无法描述客观事物的结构及其逻辑特征,也无法表示不一致事物间的共性。如,“杨青是教师”与“李文是教师”这两个命题,用命题逻辑表示时,无法把两人都是教师这一共同特征表示出来。2 .论域与谓词论域是由所讨论对象之全体构成的非空集合。论域中的元素称之个体。论域又称个体域。在谓词逻辑中,命题是用谓词表示的。一个谓词可分为:谓词名与个体两部分。其中,个体是用来表示某个独立存在的事物或者者某个抽象的概念;谓词名是用来表示个体的性质、状态或者
5、个体之间的关系等。通常,谓词名用大写英文字母表示,个体用小写英文字母表示。如:王宏是学生谓词表示为:STUDENT(Wanghong)桂林山水甲天下谓词表示为:甲天下(桂林山水)桂林在广西的北部谓词表示为:在(北部,桂林,广西)广西师大校园坐落在桂林谓词表示为:坐落在(广西师大校园,桂林)谓词表示为:县(全州,桂林)谓词表示为:Greater(x,6)谓词表示为:TEACHER (father(Wanghong)全州是桂林的县x6王宏的父亲是教师谓词的形式定义如下:定义2.2设D是个体域,P:DT,F是一个映射,其中Dn=(x1,x2,xn)x,.f),i=1,2,则称P是一个元谓词。记为:P
6、(x1,x2,xw),再2,,瑞是个体。注:在谓词中,个体能够是常量、变元或者函数。函数的定义形式为:定义2.3设D是个体域,,OO的一个映射,则称/是D上的一个n元函数。记作:/(x1,x2,xrt),再,2,,匕是个体。说明:谓词与函数的定义形式相似,但却是两个不一致的概念。谓词的真值是T或者F,而函数无真值可言,其值是D中的某个个体。谓词实现的是从个体域中的个体到T或者F的映射,而函数实现的是同一个体域中从一个个体到另一个个体的映射。在谓词逻辑中,函数本身不能单独使用,它务必嵌入到谓词中。假如尸区,乙)中的玉,当,%个体都是常量、变元或者函数,则称其为一阶谓词。若某个再本身又是另一个一阶
7、谓词,则称它为二阶谓词。3 .连接词与量词连接词是用来连接简单命题,并由简单命题构成复合命题的逻辑运算符号。在一阶谓词逻辑中,有5个连接词与2个量词。由于命题逻辑可看作谓词逻辑的一种特殊形式,因此5个连接词同样习惯于命题逻辑,但2个量词仅习惯在于谓词逻辑。:称之“非”。它表示其后命题的否定v:称之“析取”。它表示所连接的两个命题之间具有“或者”的关系A:称之“合取”。它表示所连接的两个命题之间具有“与”的关系:称之“条件”或者“蕴含”。它表示“若则”的语义。如,PQ表示“P蕴含Q”,读作:“假如P,则Q,其中P称之条件的前件,Q称之条件的后件。:称之“双条件”。它表示“当且仅当”的语义。如,P
8、c。表示P当且仅当Q,即读作“P当且仅当Q“。谓词逻辑真值表PQ-p尸VQ尸AQPTQPCQTTFTTTTTFFTFFFFTTTFTFFFTFFTT在一阶谓词逻辑中,引入了2个量词符号:全程量词符号与存在量词符号3一所有的,任一个三一至少有一个,存在有量词是由量词符号与被其量化的变元所构成的表达式,是用来对谓词中的个体作出量的规定。如,“对论域中的所有个体”,表示为Vx;“对论域中的某个个体”,表示为玉。命题(VX)P(幻为真,当且仅当论域中的所有X,都有P(X)为真命题0x)P(X)为真,当且仅当论域中至少存在一个%O,使得P()为真4 .项与合式公式在一阶谓词逻辑中,合法的表达式称之合式公
9、式(即谓词公式)。定义2.4项满足如下规则:(1)单独一个个体词是项;(2)若小小是项,是n元函数,则/G由,,乙)是项;(3)由(1)、(2)生成的表达式是项。可见,项是把个体常量、个体变量与函数统一起来的概念。定义2.5原子谓词公式的含义为:若”是项,P是谓词符号,则称P32,,露为原子谓词公式。定义2.6满足如下规则的谓词演算可得到合式公式:(1)单个原子谓词公式是合式公式;(2)若A是合式公式,则也是合式公式;(3)若A、B是合式公式,则AVB,AB,4B,AcB也都是合式公式;(4)若A是合式公式,X是项,则(VX)A与(h)A也都是合式公式。注:在合式公式中,连接词之间的优先级顺序
10、为:,V,5 .自由变元与约束变元当一个谓词公式含有量词时,通常把位于量词后面的单个谓词或者者用括弧括起来的合式公式称之该量词的辖域。辖域内与量词中同名的变元称之约束变元,不受约束的变元称之自由变元。如(Vx)(P(x,y)Q(x,y)vR(X,y)这里,(P3,y)Q(xy)是(VX)的辖域,其中的X是(Vx)的约束变元;Ray)中的X是自由变元。公式中所有的y都是自由变元。注:在谓词公式中,变元的名字是无关紧要的,能够把一个名字换成别的名字。换名时注意两点:当对量词辖域内的约束变元更名时,务必把同名的约束变元都统一换成另外一个相同的名字,且不能与辖域内的自由变元同名;当对辖域内自由变元更名
11、时,不能改成与约束变元同名。如上例可表示为:(VZ)(P(z,y)Q(z,y)vR(X,y)命题公式是谓词公式的一种特殊情况,也可用连接词把单个命题连接起来构成合式公式。如,XPVQ),P(QvR),(PQ)(Q砌都是命题公式。2.1.2 谓词逻辑的知识表示方法谓词逻辑不仅能够用来表示事物的状态、属性、概念等事实性知识,也能够用来表示事物的因果关系。对事实性知识,常用,V,八符号连接起来的谓词公式表示。对事物间的因果关系,通常用蕴含式表示。如,对“假如X则y”可表示为“xy”当用谓词逻辑表示知识时,先要根据所表示的知识定义谓词,然后再用连接词或者者量词把这些词连接起来,形成一个谓词公式。例1用
12、谓词逻辑表示知识“每个人都有一个父亲”。谓词:PERSON(x):表示X是人Hasfathera,y):表示X有父亲y则该知识可用谓词表示为:(Vx)0y)(PERSOx)HASFATHERX,y)例2用谓词逻辑表示知识“所有教师都有自己的学生”。谓词:TEACHER(x):表示X是教师STUDENT(y):表示y是学生TEACHERS(x,y):表示X是y的老师则该知识可用谓词表示为:(WX)Qy)(TEACHERA:)TEACHER&x,y)aSTUDENTly)例3用谓词逻辑表示知识“所有的整数不是偶数就是奇数”。谓词:Ia):X是整数E(x):X是偶数O(X):X是奇数则该知识可用谓词
13、表示为:(x)(Z(x)E(x)vO(x)例4用谓词逻辑表示知识:王宏是计算机系的一名学生。李明是王宏的同班同学。凡是计算机系的学生都喜欢编程序。谓词:COMPUTER):表示X是计算系的学生CLASSMATE(Xj):表示X是y的同班同学1.IKE(xj):表示X喜欢y则上述知识表示为:COMPUTER(Wanghong)CLASSMATE(Liming5Wanghong)gx)(fX)MPUTERx)LIKE(x,Programng)2.1.3 谓词逻辑表示的应用示例1机器人移盒子问题设在一房间里,c处有一个机器,a与b处各有一张桌子,分别称之a桌与b桌,a桌上有一盒子,如图所示。要求机器
14、人从C处出发把盒子从a桌拿到b桌子上,然后再回到C处。试用谓词逻辑来描述机器人的行动过程。分析:此例中的谓词公式,不仅要用来描述事物的状态、位置,而且还要用来表示动作。问题的目标状态: AT(robot,c) EMPTY(robot) ON(box,b) TABLE(a) TABLE(b)定义的谓词:TABLE(X):X是桌子EMPTY(y):y手中是空中AT(y,z):y在Z的邻近HOLDS(yw):y拿着WON(w5x):wX桌面上由此知,问题的初始状态是:显然,机器人行动的目标是把问题的初始状态转换为目标状态。而要实现问题的状态转换,则需AT(robot,c)EMPTY(robot)ON
15、(box,a)TABLE(a)TABLE(b)要完成一系列的操作。关于每个操作,通常都可分为条件与动作部分。条件部分用来说明执行该操作务必具备的先决条件,动作部分给出了该操作对问题状态的改变情况。条件部分可用谓词公式来表示,动作部分则是通过在执行该操作前的问题状态中删去与增加相应的谓词来实现。本例中,机器人需要执行的操作:Goto(x,y):从X处走到y处Pickup(x):在X处拿起盒子Setdown(X):在X处放下盒子其对应的条件与动作如下:Goto(x,y)条件:AT(robot,x)动作:删除表:AT(Ibot,x)添加表:AT(robot,y)Pickup(x)条件:ON(box,
16、x),TABLE(x),AT(robot,x),EMPTY(robot)动作:删除表:EMPTY(robot),ON(box,x)添力口表:HOLDS(robot,box)Setdown(x)条件:A(robot,x),TABLE(x),HOLDS(robot,box)动作:册U除表:HOLDS(robot,box)状态1(初始状态)状态2AT(roboc)AT(JobOta)BeginEMPTY(robot) GOto(X,功EMPTY(robot)ON(box,a)寸ON(box,a)IABLE(a)用C代怏 代怏JIABLE(a)TBLE(b)TBLE(b)状态3(初始状态)状态4Ar(
17、Iobola)AT(IoboLb)PiCkUHX)、HoLDS(IobOlbOX) Goto(XMHOLBS(robobox)TBLE(a)TBLE(b)用。代怏X器器用代快X, 5代L添加表:EMPTY(robot),ON(box,x)由此得出,机器人行动规划问题的求解过程为:状态5(初始状态)状态6A(robot,b)AT(IobOtF)SetdOWn(X)EJvFTY,(robot)Goto(x,v)EMPTY(robot).一京H万玄ON(boxjb)-用,代袂XTABL)用6代怏”代袂JON(box,b)IABma)TBLEft)TABLE示例2J机器人摞积木问题设机器人有一只机械手
18、,要处理的世界有一张桌子,桌子可堆放若干相同的积木块。机械手有4个操作积木的典型动作:从桌面上拣起一块积木;将手中的积木放到桌面上;在积木上再摞上一块积木;从积木上面拣起一块积木。积木世界的布如图所示。分析:定义的谓词:CLEARS):积木X上是空的ON(x,y):积木X在积木y的上面ONTABLE(x):积木X在桌面上HOLDINGS):机械手抓住X问题的目标状态:ON(B,C)ON(A,B)Handempty:机械手是空的由此知,问题的初始状态是:CLEAR(B)ON(C,A)CLEAR(C)ONTaBLE(B)ONTABLe(八)Handempty本例中,机械手需要执行4个操作:Pick
19、up(x):从桌面上拣起一块积木XPuldown(X):将手中的积木放到桌面上Stack(x,y):在积木X上再摞上一块积木yUnstack(x,y):从积木X上面拣起-一块积木y其对应的条件与动作如下:Pickup(X)条件:ONTABLE(x),CLEAR(x),HANDEMPTY动作:删除表ONTABLE(x),HANDEMPTY添加表HOLDlNGa)Putdown(X)条件:HOLDING(x)动作:删除表HoLDINGa)添加|表HANDEMPTY,ONTABLE(%),CLEAR(x)Stack(x,y)条件:HOLDING(x),CLEAR(y)动作:删除表HOLDlNG(幻,
20、CLEAR(J)添力口表HANDEMPTY,ON(XJ),CLEAR(x)Unstack(x,y)条件:,HANDEMPTY,CLEAR(y)动作:删除表HANDEMPTY,ON()J)添力表CLEAR(x),HOLDING(y)示例3猴子摘香蕉问题设房间里有一只猴子(即机器人),位于a处。C处上方的天花板上有一串香蕉,猴子想吃,但摸不着。房间b处还有一个箱子,假如猴子站到箱子上就能够摸着天花板。用谓词逻辑描述猴子得到香蕉的行动规划。分析:定义谓词:AT(x,y):表示X在y处ONBoX:表示猴子在箱子上面BH:猴子得到香蕉问题的目标状态:AT( Monkey,c)AT(Box,c)ONBOX
21、HB由此知,问题的初始状态是:AT(Monkey,a)AT(BOX,b)-ONBOX-IHB本例中,猴子需要执行的操作为:Goto(u,v):表示猴子从u处走到V处Pushbox(v,w):表示猴子推着箱子从V处移到W处Climbbox:表示猴子爬上箱子Grasp:表示猴子摘取香蕉其对应的条件与动作如下:Goto(u,v)条件:AT(Monkey,u),-ONBOXPushbox(v,w)动作:删除表AT(MOnkey,u)添加表AT(Monkey,v)条件:一ONBOX,AT(Monkey,v),AT(BOX,v)Climbbox动作:删除表AT(MOnkey,v),AT(BOX,v)添加表
22、AT(Monkey,w),AT(BOX,w)条件:-ONBc)X,AT(Monkey,c),AT(BOX,c)Grasp动作:IM除表-IONBoX添加表ONBOX条件:-HB,ONBOX,AT(BOX,c)动作:删除表HB添加表HB2.1.4谓词逻辑表示的特性逻辑表示法的要紧特点是建立在某种彩式逻辑基础上的,并利用了逻辑方法研究推理规律,即条件与结论之间的蕴含关系。逻辑表示法的要紧优点:符号简单,描述易于懂得;自然、严密、灵活、模块化;具有严格的形式定义;每项事实仅需表示一次;具有证明过程中所使用的推理规则;利用定理证明技术可双从老的事实推出新的事实。逻辑表示法要紧缺点:知识表示能力差难于表
23、示过程式与启发式知识;由于缺乏组织原则,利用该方法表示知识库难于管理;由于弱证明过程,当事实的数目增大时,易产生组合爆炸。系统效率低2.2产生式表示法“产生式”这一术语,是由美国数学家、逻辑学家波斯特(ETost)1943年提出的。他在研究一种称之波斯特机的计算模型时首次使用这一术语。波斯特机的目的在于证明它与“图灵机”具有相同的计算能力。在该模型中,Post要紧用类似于文法的规则对符号串做替换运算,并把其中的每一条符号变换规则称之一个产生式。后在60年代由NeWen(纽厄尔)与Simon(西蒙)等人做了进一步的研究与进展,并将该方法用于斯坦福大学建立的第一个专家系统DENDRAL中。1972
24、年,Newell与SimOn在研究人类的认知模型中又开发了基于规则的产生式系统。(因此,产生式表示法又称之产生式规则表示法)目前,产生式表示法已成为Al中应用最多的一种知识表示模式,特别在专家系统方面,许多成功的专家系统都使用产生式知识表示方式。2.2.1 产生式表示法的基本方法产生式表示法可很容易地描述塞基龙则与它们的丕确定性度量。1 .事实的表示事实可看作是断言一个语言变量的值或者断言多个变量之间关系的匪述包。其中,语言变量的值或者语言变量之间的关系能够是数字,也能够是一个词等。如雪是白的(“雪”是语言变量;“白的”为语言变量的值)王峰热爱祖国(“王峰”、“祖国”是语言变量;“热爱”为语言
25、变量之间的关系)在产生式表示法中,对确定性知识,一个事实可用一个三元组表示:(对象,属性,值)or(关系,对象1,对象2)对不确定性知识,一个事实可用一个四元组表示:(对象,属性,值,可信度因子)其中,“对象”就是语言变量;”可信度因子”是指该事实为确实相信程度,可用01之间的数来表示。事实的表示,在机器内部可用一个表来实现。如(Snow,Color,White)或者(雪,颜色,白的)(Love,Wangfeng,Country)或者(热爱,王峰,祖国)2 .规则的表示规则描述的是事物间的因果关系。规则的产生式表示常称之产生式规则,简称产生式或者规则。其基本形式为:PQ或者者IFPTHENQ含
26、义是:假如前提P满足,则可推出结论Q或者执行Q所规定的操作。这里,P是产生式的前提(或者前件),它给出了该产生式可否使用的先决条件,由事实的逻辑组合来构成;Q是一组结论(或者操作、或者后件),它指出当前提P满足时,应该推出的结论或者应该执行的操作。比如:r6:IF动物有犬齿AND有爪AND眼盯前方THEN该动物是肉食动物3.产生式与蕴含式的区别蕴含式只能表示确定性知识,其真值只能取真或者假;而产生式既可表示确定性知识,又可表示非确定性知识;如,在专家系统MYCIN中有如下产生式IF本生物的染色斑是革兰氏阴性,本微生物的形状呈杆状,病人是中间宿主THEN该微生物是绿脓杆菌,置信度为0.6在产生式
27、表示中,决定一个产生式是否可用是检查已知事实与前提中所规定的条件相匹配来实现的,同时匹配能够精确,也可不精确;而谓词逻辑中的蕴含式,其匹配则要求一定是精确的。2.2.2产生式系统的基本结构把用产生式知识表示方法构造的暨能系统称之产生式系统。一个产生式系统的基本结构包含:综合数据库、规则库与操纵系统三个要紧部分。其关系如图所示。T控制系统IL综合数据库综合数据库也称事实库,是一个用来存放与求解问题有关+*国画一A傣合数据库I的各类当前信息的数据结构。如,问题的初始状态、输入的事实、推理得到的中间结论及最终结构等。2 .规则库规则库是一个用来存放与求解问题有关的所有规则的集合。它包含了将问题从初始
28、状态转换成目标状态所需要的所有变换规则。在推理过程中,当规则库中某条规则的前提能够与综合数据库中的已知事实相匹配时,该规则被激活,由它推出的结论将被作为新的事实放入综合数据库,成为后面推理的已知事实。3 .操纵系统操纵系统也称推理机构,它由一组程序构成,用来操纵整个产生式系统的运行,决定问题求解过程的推理线路,实现对问题的求解。其要紧工作如下:按一定策略从规则库中选择规则与综合数据库中的已知事实进行匹配。若匹配成功,该规则被激活;否则,匹配失败,该规则不可用于当前推理。 当匹配成功的规则多于一条时,推理机构应该能够按照某种策略从中选出一条规则去执行; 对要执行的规则,假如该规则的后件不是问题的
29、目标,则当其为一个或者多个结论时,把这些结论加入到综合数据库中;当其为一个或者多个操作时,执行这些操作; 对要执行的规则,假如该规则的后件满足问题的结束条件,则停止推理; 在问题求解过程中,记住应用过的规则序列,以便最终能够给出问题的解路径。示例一个用于识别老虎、金钱豹、斑马、长颈鹿、企鹅、信天翁这6种动物的产生式系统。其规则库包含15条规则:1IF该动物有毛发THEN该动物是哺乳动物2IF该动物有奶THEN该动物是哺乳动物弓IF该动物有羽毛THEN该动物是鸟4IF该动物会飞AND会下蛋THEN该动物是鸟r5IF该动物吃肉THEN该动物是肉食动物r6IF该动物有犬齿AND有爪AND眼盯前方TH
30、EN该动物是肉食动物7IF该动物是哺乳动物AND有蹄THEN该动物是有蹄类动物为IF该动物是哺乳动物AND有嚼反刍动物THEN该动物是有蹄类动物r9IF该动物是哺乳动物AND是肉食动物AND是黄褐色AND身上有喑斑点THEN该动物是金钱豹0IF该动物是哺乳动物AND是肉食动物AND是黄褐色AND身上有黑色条纹THEN该动物是虎IF该动物是有蹄类动物AND有长脖子AND有长腿AND身上有暗斑点THEN该动物是长颈鹿2IF该动物是有牖类动物AND身上有黑色条纹THEN该动物是斑马13IF该动物是鸟AND有长脖子AND有长腿AND不可能飞场THEN该动物是驼鸟4IF该动物是鸟AND会游泳AND不可能
31、飞AND有黑白二色THEN该动物是个鹅IF该动物是鸟AND善飞THEN该动物是信天翁儿综合数据阵中存放如下事实:动物有暗斑,有长脖,有长腿,有奶,有蹄推理过程为:(1)先从规则库中取出第条规则6,检查其前提是否与综合数据库中的已知事实相匹配。4的前提是“有毛发”,但事实库中没有这一事实,故匹配失败。然后取该前提提可与事实库中的已知事实“有奶”本匹配,G被执行,并将其结论“该动物是哺乳动物”作为新的事实加到综合数据库中。如今,综合数据库的内容变为:动物有暗斑,有长脖,有长腿,有奶,有蹄,是哺乳动物(2)再从规则库中取6,“进行匹配,结果均失败。接着取5匹配,并将其结论加综合数据库中,如今,综合数
32、据库的内容变为:动物有暗斑,有长脖,有长腿,有奶,有蹄,是哺乳动物,是有蹄类动物(3)同上方法知勺匹配,并推出“该动物是长颈鹿二由于“长颈鹿”已是目标集中的一个结论,故障问题求解到此结束。注:上述规则库中的规则是一种直接表示方式,也可用三元组来表示前提中的事实与后件中的假设。如上例中可表示为5:IF(动物,类别,鸟)AND(动物,本领,善飞)THEN(动物,名称,信天翁)2.2.3产生式系统的基本过程产生式系统求解问题的过程是一个反复从规则库中选用合适的规则并执行规则的过程。在此过程中,规则的选用策略将直接影响到问题的求解。问题的求解效率取决于搜索策略与产生式系统的知识结构。初始化综合数据库,
33、把欲解决问题的已知事实送入综合数据库中;检查规则库中是否存在尚未使用过的规则,若有则执行;否则转;检查规则库的未使用规则中是否存在有其前提可与综合数据库中已知事实相匹配的规则,若有则从中选择一个;否则转;执行当前选中规则,并对该规则作上标记,把执行该规则后所得到的结论作为新的事实放入综合数据库;假如该规则的结论是一些操作,则执行这些操作; 检查综合数据库中是否包含了该问题的解,若已包含,则说明已求出解,问题求解过程结束;否则转; 当规则库中还有未使用的规则,但均不能与综合数据库中的已有事实相匹配时,要求用户进一步提供关于该问题的已知事实,若能提供,则转;否则,说明该问题无解,终止问题求解过程;
34、 若知识库中不再有未使用的规则,也说明该问题无解,终止问题求解过程。2.2.4 产生式系统的操纵策略在产生式问题求解过程中,当有多条规则可用时,如何从中选择一条作用于当前综合数据库,是一个操纵策略问题(也称冲突消解问题)。产生式系统的操纵策略总体上可分两类:不可撤回方式与试探性方式(回溯方式、图搜索方式)。不可撤回方式是一直往前走方式。试探性方式:回溯方式是一种碰壁回头方式。抹去过去所引起失败的试探路径。图搜索方式是一种用图或者树把全部求解过程记录下来的方式。记住已试探过的所有路径。2.2.5 产生式系统的类型1 .按推理方向分类(1)正向推理产生式系统正向推理也称之数据驱动方式,它是从初始状
35、态出发,朝着目标状态前进,正向使用规则的一种推理方法。所谓正向使用规则,是指以问题的初始状态作为初始综合数据库,仅当综合数据库中的事实满足某条件规则的前提时,该规则才被使用。优点:简单明了且能求出所有解缺点:执行效率低(2)逆向推理产生式系统逆向推理也称目标驱动方式,它是从目标状态出发,朝着初始状态前进,逆向使用规则的一种推理方法。所谓逆向使用规则,是指以问题的目标状态作为初始综合数据库,仅当综合数据库中的事实满足某条件规则的后件时,该规则才被使用。优点:不寻找无用数据,不使用与问题无关的规则。(3)双向推理产生式系统双向推理是把正向推理与逆向推理结合起来使用的一种推理方式。使用这种方式需要把
36、问题的初始状态与目标状态合并在一起构成综合数据库。2 .按规则库的性质及结构分类(1)可交换的产生式系统假如一个产生式系统对规则的使用次序是无关的,则称该产生式系统为可交换的产生式系统。所谓可交换性是指这些规则能够任意交换次序而不影响对问题的求解。设DB是综合数据库,RB是规则库,。与(i=l,2,)是第i次使用规则后得到的新的综合数据库,RSHB是一个可作用于OBj的规则集合。所谓产生式系统是可交换的,是指其RB与每一个。房都具有如下性质: 对任一规则oRS,C=12),它作用于OL得到新的综合数据库DBr,RS仍然是OBjM的可用规则集; 假如。满足目标条件,则用RS中的任一规则9作用于。
37、房,得到的OBjM仍然满足目标条件; 若对。使用某一规则序列不公,得到一个新的综合数据库。4,则当改变这些规则的使用次序后,仍然可得到。斗。从上述性质知,其综合数据库的内容是递增的。即对任何规则序列不公T,作用于DB后所得到的综合数据库。81,。82一,。人之间有如下关系:DB.uDB?uUDBk示例设给定一个整数集合,c,可通过把集合中任意一对元素的乘积作为新元素添加到集合中的办法来扩大该整数集,要求通过若干次操作后能生成所需的整数集合,c,aXCMX。规则库中包含的规则有:IFaJcTHENaybyc,abr2IF(a,b,cTHENa,b,c,bcriIF(a,bfcTHENa,b,c,
38、ac显然,用产生式求解这个问题时,综合数据库DB可用集合来表示,其初始状态为a,b,c),目标状态为4,。1,。乂46乂(7,。乂。不管先用哪条规则,都可由初始状态达到目标状态。可交换的产生式系统的可交换性,使得其求解过程只需要搜索其中的任意一条路径,就能达到目标,而不必进行回溯。因此,该系统求解过程可使用不可撤回的操纵方式。它无需记录可用规则的作用序列,可节约求解问题的时间,提高求解问题的效率。(2)可分解的产生式系统该法是把一个较大或者较复杂的问题分解成若干个较小或者较简单的问题,然后通过对这些较小或者较简单问题的求解来得到整个问题的解。可分解的产生式系统是把一个整体问题分解成若干子问题,
39、然后再通过对这些子问题的求解来得到整个问题解的一种产生式系统。示例设综合数据库的初始状态为C,B,Z,目标状态为M,M,,M,规则库中有如下重写规则:CD,Lr2:CB,M(6:8M,M:ZB,B,M)解决该问题时,可先把初始综合数据库分为三个子库,然后对这三个子库分别应用规则库中的相应规则进行求解。其求解过程如图所示。(3)可恢复的产生式系统可恢复的产生式系统是指那种使用回溯操纵方式的产生式系统。其求解问题的方法是:当执行某条规则后,假如发现所得到的新的综合数据库不可能求出问题的解,就立即撤消由该规则所产生的结果,使综合数据库恢复到先前的状态,然后再另选别的继续求解。它既可向综合数据库中添加
40、新的内容,又可从综合数据库中删除或者修改老的内容。这种可解方法,更符合人们的通常习惯。2.2.6产生式系统的特点优点:自然性、模块性、有效性、一致性。缺点:效率低、不能表示结构性知识2.3语义网络表示法语义网络是奎廉(J-R.Quillian)1968年在研究人类联想经历时提出的一种心理学模型,他认为经历是由概念间的联系实现的。随后,奎廉又把它用作知识表示。1972年,西蒙在他的自然语言懂得系统中也使用了语义网络表示法。1975年,享德里克(GGHendrix)又对全称量词的表示提出了语义网络分区技术。目前,语义网络已成为AI中应用较多的一种知识表示方法。2.3.1 语义网络的基本概念1 .什
41、么是语义网络?语义网络是一种用实作及造义夫系来表达知识的有向图。其中,结点代表实体,表示各类事物、概念、情况、属性、状态、事件、动作等;弧代表语义关系,表示它所连接的两个实体之间的语义联系。在语义网络中,每个结点与弧都务必带有标识,这些标识用来说明它所代表的实体或者语义。从结构上看,语义网络通常是由一些最基本的语义单元构成的,这种最基本的语义单元被称之语义基元。一个语义基元可用如下三元组来表示:(结点1,弧,结点2)A-B例I用语义基元描述“舵鸟是一种鸟”这一事实。能鸟-一种.鸟当把多个语义基元用相应的语义联系关联在一起时,形成了一个语义网络2 .基本的语义关系从功能上讲,语义网络能够描述任何
42、事物间的任意复杂关系。但是,这种描述是通过把许多基本的语义关系关联到一起来实现的。基本语义关系是构成复杂语义关系的基石,也是语义网络知识的基础。作为参考,这里给出一些常用的基本语义关系:(1)类属关系类属关系是指具有共同属性的不一致事物间的分类关系、成员关系或者实例关至。它表达的是“具体与抽象”、“个体与集体”的概念。类属关系的一个最要紧特征是属性的继承性。处在具体层的结点能够继承抽象层结点的所有属性。常用的类属关系有:A-Kind-of:含义为“是一种”,表示一个事物是另一个事物的一种类型;IIa-kind-of1I鸟类I动物IA-Member-of:含义为“是一员”,表示一个事物是另一个事
43、物的个成员;Ia-member-of李刚I共青团Is-a:含义为“是一个”,表示一个事物是另一个事物的一个实例。同E,区(2)包含关系包含关系也称聚类关系,是指具有组织或者结构特征的“部分与整体”之间的关系。它与类属关系的最要紧区别是包含关系通常不具备属性的继承性。常用的包含关系有:Part-of:含义为“是一部分”,表示一个事物是另一个事物的一部分。如+户Part-of国*ParLof大脑人体黑板墙(3)属性关系属性关系是指事物与其属性之间的关系。常用的属性关系有:Have:含义为“有”,表示一个结点具有另一个结点所描述的属性。Can:含义为“能”、“会”,表示一个结点能做另一结点的情况。如
44、,“鸟有翅膀”的语义网络2鸟上!f翅膀(4)时间关系时间关系是指不一致事件在其发生时间方面的先后次序。常用的时间关系有:Before:含义为“在前”,表示一个事件在另一个事件之前发生。After:含义为“在后”,表示一个事件在另一个事件之后发生。如,“澳门回归要香港回归之后”的语义网络为After澳门回归香港回归(5)位置关系位置关系是指不一致事物在位置方面的关系。常用的有:1.ocated-on:含义为“在上,表示某一物体在另一物体之上。1.ocated-at:含义为“在,表示某一物体所在的位置。1.ocated-under:含义为“在下”,表示某一物体在另一物体之下。1.ocated-in
45、side:含义为“在内”,表示某一物体在另一物体之内。1.ocated-Outside:含义为“在外”,表示某一物体在另一物体之外。(6)相近关系相近关系是指不一致事物在形状、内容等方面相似或者接近。常用的有:Similar-to:含义为“相似”,表示某一事物与另一事物相似;Near-to:含义为“接近”,表示某一事物与另一事物接近;(7)推论关系推论关系是指从一个概念推出另一个概念的语义关系。如,“由成绩好推出学习努力”的网络语义为3.事物与概念的表示(1)用语义网络表示一元关系所谓一元关系是指能够用一元谓词Pa)表示的关系。其中,个体X为实体,谓词p说明实体的性质、属性等。一无关系描述的是一些最简单、最直观的事物或者概念,常用:“是”、“有”、“会”、“能”等语义关系来说明。如,“雪是白的”就是一元关系,white(snow)但语义网络通常描述的是两个结点之间的二元关系。那么如何用它来描述一元关系呢?常用的做法是:用结点1表示实体,用结点2表示实体的性质或者属性等。如,“李刚是人”一推出李刚人(2)用语义网络表示二元关系所谓二元