rkif推理引擎设计实现与在提问式检索中应用.doc

《rkif推理引擎设计实现与在提问式检索中应用.doc》由会员分享，可在线阅读，更多相关《rkif推理引擎设计实现与在提问式检索中应用.doc（57页珍藏版）》请在三一办公上搜索。

1、上海交通大学学位论文原创性声明本人郑重声明所呈交的学位论文是本人在导师的指导下独立进行研究工作所取得的成果除文中已经注明引用的内容外本论文不包含任何其他个人或集体已经发表或撰写过的作品成果对本文的研究做出重要贡献的个人和集体均已在文中以明确方式标明本人完全意识到本声明的法律结果由本人承担学位论文作者签名高昊宇日期12004 年 1 月 10 日上海交通大学学位论文版权使用授权书本学位论文作者完全了解学校有关保留使用学位论文的规定同意学校保留并向国家有关部门或机构送交论文的复印件和电子版允许论文被查阅和借阅本人授权上海交通大学可以将本学位论文的全部或部分内容编入有关数据库进行检索 可以采用影印缩

2、印或扫描等复制手段保存和汇编本学位论文保密本学位论文属于不保密请在以上方框内打在年解密后适用本授权书学位论文作者签名高昊宇指导教师签名俞勇日期年月日日期2 年月 日上海交通大学硕士论文RKIF 推理引擎的设计与实现及其在提问式检索中的应用摘 要KIFKnowledge Interchange Format 是由 Stanford 大学提出DARPA 组织倡导的一种知识交换标准它支持非单调推理 元知识表示 高阶谓词 可以通过加入特定的公理而形成各种不同的公理体系由于它的核心小语义清晰表达能力强而迅速成为知识表示的通用标准之一在此基础上实现一个能够对 KIF 描述的知识进行自动推理的推理引擎具有重

3、要的意义 但是 由于 KIF 表达能力的强大导致其在实现上的困难使得现有的系统无法完全实现 KIF 的所有表达能力因此在 KIF 的强大描述能力和可运行性之间作一个折衷得到一个可运行 KIF 子集RKIF(Runnable KIF) 实现其上的推理引擎是一个有意义并富有挑战性的课题由于 RKIF 本身完全符合 KIF 规范 所以它使得用户在 RKIF 表达能力范围内 实现知识库系统时不必在内部推理机制上使用一种语言而在与外界交互时使用另外一种标准语言如 KIF本文讨论了 RKIF 规范的设计和推理引擎的实现最终定义的 RKIF 实际上是一个默认封闭世界假设并去掉了一些不常用的 KIF 语法特性

4、的 KIF 子集在此基础上我们以 Rete 算法为核心实现了一个 RKIF 推理引擎在实现上我们没有沿用传统的 Rete 网络的结点类型 而是根据 RKIF 的语义模型构造了 5 种对应的结点类型并在 Rete 网络的运行和 token 的处理上有所创新为了验证该推理引擎的实用性和效率 我们将其作为一个推理应用系统提问式检索系统的底层推理引擎需要指出的是这一系统本身是一项独立的工作它实现了以一阶谓词推理为基础在中文信息上进行语义推导的方法并将其应用于提问式查询中使用了基于规则的 LFT 方法产生自然语言的谓词表达式作为事实库-5-上海交通大学硕士论文源从 HowNet 中抽取词汇浅层知识作为规

5、则库通过中心词的符号连接进行一阶谓词推理 该系统的推理模块正是建立在 RKIF 推理引擎之上的 因此本文的后半部分将详细介绍这个系统中的推理部分能的改进在这一部分的最后给出了评估测试结果和可关键字KIFRKIF推理引擎一阶谓词封闭世界假设知识库前向推理-6-上海交通大学硕士论文The Design and Implementation of RKIF Inference EngineWith The Application On Question-based QueryABSTRACT（）， ，（），（），-7-上海交通大学硕士论文，Key words: ，-8-上海交通大学硕士论文第 一 章

6、 KIF 简介1.1 知识共享与交换随着 Semantic Web 的兴起与 Agent 技术的提高 越来越多的系统用到的不仅仅是数据 元数据 还有在它们之上的知识 2 知识实际上是对数据操作的方法 当这种方法不是硬编码在程序里而是以一种更灵活的方式存在于系统的规则库里就可以称之为知识例如一个网络爬虫程序 有选择的抓取一些网页 那么控制哪些网页应该被抓取的规则信息就可以称之为知识通常而言 每一个需要用到知识的系统都要对知识进行表示和推理 正因为知识的重要性每个系统都会对自己所使用的知识体系有一套特定的表示和推理机制例如 W3C 在 Semantic Web 中推荐使用的基于描述逻辑的 RDFS

7、 10 在专家系统中普遍采用的基于 Horn 子句的 prolog 等等从而导致知识在这些系统内部的表示形式可能千差万别当这些系统间需要交换知识时如何通过一个统一的接口对各种知识体系进行清晰 有效的描述使其被无歧义 不丢失信息地表达出来KIF就是这样应运而生的1.2 KIF 简介Knowledge Interchange Format (KIF)是为了在不同计算机程序之间交换知识而产生的规范语言1 它是由美国 Stanford 大学提出DARPA 组织倡导的KIF产生的主要目的既不是为了用户之间的交互也不是力图成为程序内部唯一的知识表示方法虽然它也可以做到这两点它是一种程序员可读的语言为不同的

8、知识应用程序的独立开发架起一道桥梁就像 PostScript 为不同的打印机硬件和软件提供了统一的标准一样 KIF 也为知识的表示和推理提供了统一的标准 11 KIF 具有一个很小的核在这个核添加不同的公理就形成不同的逻辑系统-11-作为一种标准上海交通大学硕士论文语言它具有下列本质特征1具有十分清晰的语义不会因解释器的不同产生歧义2语言是逻辑完备的只要是符合谓词演算的任何表达式都可以写成 KIF形式不象 Prolog 等局限于 Horn 子句3它提供元知识的表述这就使我们能够形式化地表述知识本身1.3 KIF 基本语法KIF 有四个基本概念termsentencedefinition rul

9、eterm 用来表示一切对象实体 sentence 用来表示世界知识 definition 用来定义常量rule 用来描述推理的步骤Term 主要分为常量 term 变量 term 表 term 集合 term 引用 term 逻辑 term和量词 term 前三个与 Lisp 中的对应概念相似引用 term 用于表示元知识逻辑term 先进行条件判断然后选择取哪个 term 量词 term 表示具有某种性质的 term 的抽象所有的 term 都可以作为集合 term 的一个元素sentence 是用量词逻辑符号连接起来的断言它对应于知识系统里的事实包括表示 term 的相等判断的等式/不等

10、式 sentence 用与或非和蕴含符号连接起来的逻辑 sentence 以及包含全称量词或存在量词的量词 sentence 分为 和 两种 型 是充要的 型 仅仅是必要的体现了所定义对象的性质 又分为 和 两种其中 限制该定义不会推导出不包含所定义内容的 所定义内容可以是对象函数关系三种分别用 来表示 其中 等运算作为内建的函数rule 由一组前提和一个 sentence 组成 表示当前提都成立时 sentence 成立 前提由 sentence 组成 中的变量分为两种 和 用来代表单个 -12-上海交通大学硕士论文用来代表 的序列 提供 和 两种基本数据结构 的概念与 中 相似是一组 或

11、的有序组可以用（）来表示其中到 可以是简单的 也可以是 是与 对应的概念 一个 要么是 要么是 为了避免关于集合的经典悖论 引入了概念 一个要么是 要么是 并且只有的 才可以作为一个 的元素两个 set 相等当且仅当它们具有完全一样的元素1.4 KIF 的表达能力总的来说 KIF 可以在语法上可以认为是 Lisp 和 prolog 的组合 在语法形式上KIF 更加倾向于 Lisp但是同时具备了 prolog 的谓词推理能力传统的 Logic Program 可以被容易地转换到 KIF只要添加两个假设1统一名假设 任意两个不同对象常量不相等 2 封闭世界假设 如果一个关系不成立不引起系统不一致那

12、么它不成立用 KIF 语言可以表示如下统一名假设( not (=1）封闭世界假设（）（）KIF 同时还支持非单调推理 12 例如( bird tweety)( = (flies ?x) (bird ?x) (not (abnormal aspect1 ?x)以上两个 sentence 表示所有鸟 只要它不在 aspect1 上异常 就能飞 而 tweety是鸟系统同时会有一条默认规则(holds ?r ?x ?y) (not (holds ?r ?y ?x)这样我们以后可以直接用 来声明一个关系具有反对称性KIF 中引入 quote 来描述元知识 quote 用来指称符号或表达式本身 它的参数

13、必须是一个合法的 KIF 符号或表达式 例如 为了指称 john 这个符号 我们用(quotejohn) 而为了指称表达式(p a b) 我们用(quote(pab) quote 可以被简写成为了描述一个事实john 相信 moon 是由 stilton 组成的我们可以写(believe john (material moon stilton)如果我们还有(=(believejohn?p)(believesmary?p) 那么我们可以知道 mary 也相信 moon 是由 stilton 组成的例如 mary 只相信 john 对于材料方面的判断如果我们需要更为灵活的表示方法那么我们可以把 q

14、uote 与变量组合起来(= (believes john (listof material ?x ?y)(believes mary (listof material ?x ?y)这个句子可以被简写成(= (believes john (material, ?x, ?y)(believes mary (material, ?x, ?y)作为描述元知识的一个例子KIF 可以自描述1.5 KIF 解释器诚如上文提到 KIF 在设计上是为了兼容所有知识表示方式而提出的一种标准接口而不是作为一种编程语言而提出的所以能够进行解释并推理的 KIF 解释器并-14-上海交通大学硕士论文不是必需的但是实现一

15、个 KIF 解释器有以下好处1它提供一个通用的知识推理引擎的解决方案 虽然针对特定的知识表示方式可能不是最优但是使用户在对效率要求不高的情况下可以省去写一个专用推理引擎的工作2用户可以通过把某种知识表示方法转换成 KIF 后由解释器来自动检查这种表示方法是否有语义上的不一致性正因为 KIF 功能上的强大所以很难或不可能存在一个有效的算法来实现KIF 的所有功能因此在一定程度上有必要对表达能力和推理能力作一个折衷使解释器能够高效地实现 KIF 的一个最大子集相关系统 是 的一种变体 支持一阶谓词的语法和语义 它使用 的后向链技术作为主要的推理手段后向链虽然不是一个完全的定理证明机但是可以处理 子

16、句 否定谓词和简单的等式推理 相对于 它可以处理递归规则而不致陷入无限循环 使用 机制来使知识的管理更加结构化并使用 世界来支持假设推理 的实现语言是 它是一种强类型 类 语言 可以被转化到 和 这样就使得 的目标代码可以容易地被转化成 或 代码一个 的知识库在创建时先是定义一些领域概念和关系 然后加入规则和事实事实可以被 和 所以查询在不同时刻可能是不一样的领域知识被组织在该领域的 里并只在该 中生效 的真值有 种取值 和一个命题不能证明为真或为假时被赋值为 所以 采用的实际上是一个开放世界假设 但是 也允许显式地把一个谓词声明-15-上海交通大学硕士论文为封闭世界假设这样所有关于该谓词的命

17、题如果不能被证明为真或为假都将被赋值为 PowerLoom 在功能上更像一个高级的 prolog 在语法上与 KIF 也不完全兼容Prologic以及它的前身Epilog是Common Lisp的一个函数库 它的功能包括创建维持一个KIF知识库转换知识库和一个sound and complete的推理方法 45 所以严格地说 Prologic并不是一个KIF解释器 而是一个处理KIF知识库的工具 它提供了很多对知识库本身进行操作管理的命令如save添加事实knownp判断命题是否为真识模块等knownx 求使命题为真的自由变量取值include 导入一个知在知识库转换方面提供命令来把所有的存在

18、量词转换成函数形式并定义了的一个子集提供命令来把知识转换为知识在推理能力上 采用 model elimination 方法 13 实现了 的一阶谓词逻辑部分在算法上 同时使用后向链和前向链两种方法1.5.2 评价目前号称实现 相关的解释器还不多 而且多是商业系统 以上两种是比较有代表性的两个系统这些系统的共同特点是都实现了 中的一部分表达能力有的还加入了知识工程中知识管理 模块继承等概念使其更适合知识库系统的开发和应用但是为了体系的完整都没有完全严格地遵守 规范这样做固然有利于提高系统的效率和完整性 但是违背了 设计的初衷 是作为一种知识表示标准而不是程序设计语言而出现的所以这些系统在某种意义

19、上实现的并不是 或其子集的解释器而是一种类 的语言的解释器-16-上海交通大学硕士论文第 二 章 RKIF 的设计与推理引擎实现2.1 目标如上所述KIF 作为知识表示标准已经得到越来越多的应用KIF 的强大的知识表示能力使不同知识库体系通过 KIF 标准即使使用的是不同的逻辑系统也可以相互交流但是正因为 KIF 表达能力的强大使得目前还没有一个系统能够完整地实现它的全部推理能力为此 有必要在 KIF 强大的表达能力和可运行性之间做一个折衷 形成一个可运行的 KIF 子集我们称之为 Runnable KIF简称为 RKIF本毕业设计的目的就是给出一种可行的 RKIF 定义 做出它的推理引擎的实

20、现 并在其上作一个具体的推理应用RKIF 可以给用户带来如下好处1.在多数实际的推理系统应用中RKIF 有足够的能力描述事实库和规则库这样用 RKIF 描述的事实库和规则库既可以作为内部推理系统的直接输入同时因为 RKIF 是 KIF 的一个子集 所以事实库和规则库本身符合 KIF 规范可以直接以 KIF 的形式发布出去2.以 RKIF 为知识库描述语言 可以方便地推导出知识库是否存在矛盾或不一致性从而减轻了校验的工作量2.2 RKIF 的定义从 KIF 中提取一个可运行子集显然有很多方法 在此给出的是一个比较接近于 prolog等谓词逻辑推理机的 RKIF 定义 这是因为大多数的应用都在谓词逻辑体系之内 而相应的推理机制也比较成熟 因此我们在制定 RKIF 范式的时候 尽量保留 KIF 中的规则推理的部分并删去了一些难以实现的特性和细节-17-使其能比较方便地转化为上海交通大学硕士论文谓词推理系统从目标上说我们的设计目的希望能做到以下几点123严格符合 KIF 语法能够满足多数知识库系统的需求存在行之有效的算法4KIF 是程序员可读的RKIF 既为程序员可读的又是机器可读的在具体规范上