《类比推理中的一种相似性准贝l》由会员分享，可在线阅读，更多相关《类比推理中的一种相似性准贝l（5页珍藏版）》请在金锄头文库上搜索。
1、国防料拉 大学半报IOURN A LO FN 人TI ON ALUN IV E R S IT YO FD琶r E NS 忆 TE CHNOLO心甘摘12卷第4期l。 。o年1 2月Vol.i aNo一4类比推理中的一种相似性准贝l J 及其验证方法张少平王怀民陈火旺(计算机系). 摘耍类比推理是人工智能领域 中的重要研究方向,而相似性准则是类比推理 中的重要概念。文中给出了类比推理的一种描述框架,定义了相似 性准则,并且基于项重写技 术,提出了相应的验证 方法。关扭词人工智能,推理,规 范/类比推理,相似性准则,项重写软件重用分类号T P1 8在人工智能领域中,类比推理 已有很长的历史。类比是
2、 人们进行思维的重要方法之一,在理解、学习和概括等智能活动中都离不开类比。使用类比推理大致上基于两个方面的 原因,其一 是根据我们已有的知 识,无 法解决某一 问题,通 过类 比推理可以找出该问题 的相似问憾,然 后,根据相似向题的解,作 出关于该向题的一些新的 猜想,从而解决向题,另一 原 因是依据我 们所掌握的知识,不使 角类比推理,虽可 以解决问题,但使用类比推理可以快速、有效地解决向题,类比推理作为有效地获取和使用知识的途径。在进行类比推理时,必须具备两个先决条件:(1)相似性准则。相似性准则是指两个向题相似的标准,即何时两个问题,针对某一目的而言是相似的。相似性准则对于类比推理是极为
3、重要 的,因为没有类比的标准,就无法进行比较。(2)源知识域。源知识域是指通过向题求解或其它方式所获取的知识全体。对于源知识域中的每一个向题,都有一个精确的解。可以认为,类比是有效地联接推理者的过去和现在经历的基本机制。如果没有过去的经历和日积月累所掌握的源知识,类比就缺乏必要的物质基础。源知识域中的源知识的描述以及组织方法,直接影响类比推理的效果。在本文中,以软件重 用向题为背景,讨论了一类相似性准则向题。在定 义这 种相似性准则及其验证方法之前,让我们首先给出类比推理的一种描述框架。1. 00年i月.日收稿国防科技大学学报第1 2卷1类比推理的一种描述框架对于类比推理,可以用一种简单的描
4、述框架,描述其推理 的全过程。该框架由源知识 的表示与组织,源知识 的识别与修改完善三部分组成。(1) 源知识 的表示与组织 对于源知识,我们应以某种语亩对其进行描述,并且对宾加以分类,把它们有效地组 织成为一 个源知识域。源知识域的组织是精确地验证相似性淮 则的基础,也是 有效地识别 源知识 的基础。(2) 源知识的识别根 据相似性准 则,验证识别出的源知识的有效性。对于不熟 悉其解 的问题,我 们如何把该 问题与源知识域中的一 个或多个源知识 联 系起 来呢?最 常见的方 法就是根 据相似性准 则及其验证方法在 源知识域上进行检索。从源知识域中识别出的源知识与欲求解问题 之间是否满足相似性
5、准则,需要进行相似验证。验证可 以分成 语法验 证和语义验证两部分。如果验证 的结 果是满足相似性准则,则称相应的源知识为相似 源。(3)修改 与完善因为相似问题的解是相似的,故对相似源的解稍作修改,即可得 到关于 欲求解问题的解。在得 到该问题 的解以后,还需要把该 问题及其解存入 到源知识域中,为将来的类比推理 作好淮备。源知识 域应 当是 开放型 的,随着类比推理 的逐 步深人,以及其它方式的学习,源知识 域应 当逐 步丰富与完善。2一种关于软件重用的相似性准则软件重用的基本出发点是利 用已实现的成熟软构件构造新的软件。基于重用 的软件开发思想是对上述类比推理一般框架的自然的具体表现。软
6、件重用技术的物质基础是 软构件库的建立与组织。软构件库是软件重用技术的源知识域。欲设计的软件与重用软件间的匹配原 则是软件重用技术的相似性准则。与类比推理 的一般框架相对应,一个软件重 用检索系统由三个主要成 份 构 成,即.重用软件库,软构件识 别系统和软件修 改完善系统。软件重用检索系统与问题分解系统和软构件组装系统结合在 一起,构成 了基于重用技术的软件开发系统的主干。简单地说,软件重用技术是依据我们已掌握的重用软件,快速有效地开 发软件的一种类比推理技术。类比推理首先必须解决的关键性问题是欲求解的问题与源知识的相似性原则,精确地规定相似性准 则的基础是在统一 的语义论域上对欲求解的问题
7、和源知识进行形式化规范描述。. 不同的类比推理系统,依据不同的相似性准则,因为相似性准则与论域紧密相关。由于 我们所感兴 趣的是利用类比推理 进行软件开发,故 用形式化的代数规范描述问题和重用软件6,并且基于代数规范定义相似性准则。代数规范 的一般描述为一个二 元组:第4期张少平等:类比推理中的一种相似性准则及其脸证方法8, =(艺,E)其中,艺为代数规范 的标记,E为等式公理,.它们 分别 对应问题 的语法、语义描迷。假设 源知识域中的成份为软构件,软构件 由其完整代 数规范印和该问题的一种正确有效的解c ode组成。现在的向题是,若s P。为欲求 解问题的 (不完整)代数规范,何谓s尹。与
8、s尹相似呢?直观 上讲,两个规范应具 有相 同的语 法结构,更重要的是两个规范所决定的初始模型也应 当相似,精确地 说,:尹。中的等式公理,应在即所 决定 的初始模型下有效。可以对相似性准则形式 定义如 下:定义设s,。为欲求解问题 的规范 (不完整的或部分 的),印为源知识域中某个软构件的规范,我们说妙。与s夕相似,且 记作:即。、。尹是指:(a)名。g 艺(b)V=s任Eo二= 今I,卜t二s其中艺。二 艺表示 艺。是习的子标记,I a,表示 由规范印所确定 的初始模型,几p卜t=8是指等式二s的初始有效性。例如,设表的代数规范砂: 。中的等式公理 为:append(nil,l)二I()a
9、p pe nd(x1,m)二xappend(l,m).(二 l)re v(nil)二nil(乏)rev(x1)=apPend(rev(l),xnil)(4)对于t一个关于 表的欲求 解 的l b J题,某耀户只知道其 问题 的描 述 为印梦,.:ap pend(xl,m)=xap pe nd(l,m)(;)一re v(re v(l)二l(奋)可以验证:I。, :,.卜aPPend(x1,m)=xaPPe nd(l,m)I,: 二卜rev(rev(l)二l从 而验证 Tsp“。、,p穿,这时 可用s尹:,的实现,求解该问题。3相似 验证对于前面 提 出的相似性准则,如何进 行语义验证,即证明初始
10、有效性呢?过去人们经常用的证 明方法是基于某种结构的归纳法。这 种方法 的缺点是难以算法实现。八十年代,人 们受项重写技 术中完全过程( c。mpl etn essP to c e dure )的启发,发现了一种初始有效性的证 明过程 11 1, 1“。这里我 们仅仅介绍其证 明过程的主要思想。首先,将代数规范的标记集族进一步地 分解成构造符(c on st ruc to r)和定义函数符。例如,s,:,的标记集族由构造符集族n il,和定义 函数符集族 apP end,r ev组成,一般情况下,把前者记为口,后者记为D。称s尹=(CUD,刀)关于C是完全的是指即满足,( 1) 对于由OUD生
11、 成的所 有合法项,都存在由C生成的项。,使得落=百即:t与月在等式理论E上 相等_2 6_鱼二防科抹大堂_竺一鱼一一一一一一一塑竺匕(2)对于由C生成的项t,8,若t=,8,则t与8是同一 个项。下面假设,源知识域中的代数规范是完全的。可验证却:。.是完全的。设s,。(习。,E。)是用户给出的欲求解问题的代数规范,即=(习,E)是源知识域中的代数规范,验证8,s,.的过程可以简单描述如下:(l )根据化简关系把EUE。中的等式定向成为重写规则得到重写系统忍.(例如我们把(l )式 定向为apP end(n il,l ),1,因为规则右边的项是左边项的化简)。(2) 设R是重写系统 (感的初值
12、为0),求R的临界对的集合c户(R)。所谓材,s 任ep(R)是指存在11,1eR,l:,:任R,使l;的位于a的非变元子项王:/a与l:之间存在mgna使得二。(,:),。.a(l:)a,a(,:)1,即s是用口(,:)代换a(l:)中位于a的子项所得 到的项。例如,是rev(r ev(l)1和rev(xl),appe nd(rev(1),xnil)的临界对。a)如果cp(R)为空,则却、s夕。,过程终止。b)否则设任c夕(R);勺如果t,s是 由C生成的不 同项,则s乡与8,。不相似,过程终止。“)否 则:如果公是名的化简,则转3.(3)R十:=R日“s,云艺+l,转2.具体的算法和 证明
13、请参见文1 1。一些实验系统表 明,上面介绍的相似性准则和验证方法可作为 一种软件重用技 术。4结论本文 中所提 出的一类相似性 准 则及其验证方法是针对软件重用技术研究的。基于前面所 阐述的思想,我 们研究设计了一个信息检索系统KDz”,该系统是支持 软件重用的。在KDz系统中,我们把软构件组成一个开 放型的,具有格结构的软件库,把相似性 准则作为匹配软构件的重用理论,通过语法、语义项重 写 子系统来支持 可重 用验证。该系统改善了以往j勺 软构件检索系统中缺乏语 义检索的状况,尽管在运行效率方面还有待于提高,但本文所提出的原则和思想对软件重用技术的研究无疑 是有意义的。通 过具体的实 践,
14、可 以对相似性准则作更具体的一般性规定:(l )相似性准则是一个与问题域及源知识城紧密相关的问题。( 2 )只有把问题城和源知识城置于一致的语义论域之中,才能精确地规定相似性含义,定义相似性准则,进行相似验证。做到这一点的最理想的办法是用具有良好语义性质 的语言,描述欲求解问题和源知识。(3 )相似是论城中的元素之间的某种逻辑相关性。相似性 准 则是 这种相关性的刻划。今考文献1Ca rbonell J G.Le a rn笼皿gb了Analoy,Form恤lati皿9andGeneralizingplaosfro口P.,tExpe rieoee。MaehioeLear立泥。g,l ess,1第
15、4期张少平等:类比推理中的一种相似性准刘及其脸证方法 21Gr.里n erR,8肠(又 )MeDe r口ot tCarbonell19 8 1L.,r 皿ingb了U.de rsta城di皿9Aoalogies,Artifieal2 7I皿tell玉ge.ee,10.,811 4 1J。Lear ningtoUseAnalog了.IJCAI,10 7。JG.AComPutationalModelof Pr ob lem501下ingb了An alogy l.IJC AI,t一万IT甲.rsk了A.Feat往re sofSimi larit了.Ps了eholoie alRe甲ie那,x.77,e
16、-.IG叱ue nJA,T hatehe rJW.WagnerEW.AnInitialA!gebraApProae卜totheSpeeifie ation,Corr eetn essa ndIm plementationofA D T.CT PMIV,lo7e7 1Afshar5K.Soft下a r eReu seViaSo ure eTraosfo rmation。Pro e.C OMPS AC,. 5Cor nPute randAPPI笠eationConf.sBig gerstaff T&RiehterC.Re u sabilityFr a口e,orkAs se ssme nt,andD ireetio,:.Pro e.oftheT,e ntiethAn nu alHawaiiInte r.ationa!Conf.o皿Syste.Se笼enee.1987t公Loqi&Berzi.s.V.RaPi
