描述逻辑推理优化技术研究

论文摘要

网络的出现,极大地改变了人们的生活,丰富了人们的交流方式,增加了人们获取资料的途径,加速了信息的流通,影响了人们的休闲方式,等等,可以说,网络是二十世纪后期以来对人类影响最大的技术之一。但是目前的网页,其表达语言为超文本标记语言,即HTML,在发明之初,是面向人的,即网页的内容通过浏览器,展示给人,这导致其内容不能很好地被机器所理解,影响了网页内容处理的自动化。随着网络信息的急剧增长,人们从海量的信息中有效地获取知识变得困难。语义网是万维网创始人Tim Borners-Lee提出的下一代网络。通过对网页中的信息增加元数据,以及改善网页的结构等,使得网页中的信息更加规范,从而能够被计算机所自动处理。描述逻辑是语义网的逻辑基础,如果语义网需要对其表达的知识进行推理,发现其中的隐含知识,则需要运用描述逻辑的推理能力。目前的研究表明,对于普通表达能力的描述逻辑语言ALC来说,其复杂度是pspace-complete,因此,如果不加以优化,很难应用在网络化的环境当中。基于人们在利用现有的搜索引擎时,搜索的结果并不总是正确的,提出了利用近似化来提高描述逻辑的推理效率。通过观察到,概念实际上由这些概念包含的个体所定义,设计了利用概念的个体来优化概念包含的判断。概念在解释域上的个体可以通过记录推理中间过程信息来得到,这些个体可以用来减少后续的部分推理。但是对于大本体,这种技术提高的效率有限,因为对于复杂的概念,其包含的个体较少,不能很好表达概念的特征。如果一个概念的所有个体,都是另外一个概念的个体,可以归纳地认为,前概念包含于后概念。虽然这并不准确,但是可以作为一种近似化的手段。在推理时,部分特别复杂的概念,由于其包含的个体较少,其准确性比较低,并且非常耗时。因此,提出了估算知识库可满足性判断的时间复杂度的方法。如果一次推理,其估算的时间复杂度比较高,那么可以通过泛化等方法,牺牲一定的准确性来提高推理的效率。概括了描述逻辑中查询的发展历史和当前的研究现状。由于SHOIQ中的查询在目前还未能得到完全解决,因此提出了利用近似化的方法来解决描述逻辑SHOIQ中的查询问题。对于不同的用户,其个性可以表述为不同的知识,根据这些知识,查询中的不同概念将赋予不同的优先级。针对查询图,提出了基于优先级的遍历方法,这种方法,能够有效的提高结果与用户期望的符合程度。分区可以将大本体分成一些小的本体来处理。概化可以利用ABox中的一些“代表”个体来对ABox进行推理。这两种技术,都能够有效的提高描述逻辑的推理效率。本文讨论了如何基于这两种技术,进行推理的近似化以及个性化。定性偏好语言能够较好的描述不同用户的个性和偏好。提出一种将分级知识库从定性偏好语言转化为用描述逻辑表示的方法。使用描述逻辑来表示偏好,能够很好把偏好表示和推理结合在一起,并且条件偏好等可以增加用户的查询能力,提高了用户查询的方便性。在以上的研究基础之上,通过实验证明了基于个体的推理优化,概念包含的近似计算,语义搜索的偏好表示和推理等方法的有效性。

论文目录

• 摘要
• ABSTRACT
• 目录
• 插图目录
• 表目录
• 第1章 绪论
• 1.1 引言
• 1.2 描述逻辑简介
• 1.2.1 网状结构的知识表示
• 1.2.2 描述逻辑的内容和发展历史
• 1.3 近似化推理的基本思想和方法
• 1.3.1 近似推理的基本思想
• 1.3.2 近似演绎的几种方法
• 1.4 现有方法存在的问题
• 1.5 研究思路与研究内容
• 1.6 论文组织
• 第2章 描述逻辑基础
• 2.1 描述逻辑的语法和语义
• 2.2 ALC介绍
• 2.2.1 语法
• 2.2.2 语义
• 2.3 TBox推理
• 2.4 ABox推理
• 2.5 总结
• 第3章 基于个体的推理优化
• 3.1 分类算法
• 3.1.1 BFM
• 3.1.2 STM
• 3.1.3 ETM
• 3.1.4 CIM
• 3.2 显示包含计算
• 3.3 基于ABox的一致性检查和推理过程的优化
• 3.3.1 ABox的一致性检查
• 3.3.2 分类优化
• 3.3.3 算法
• 3.4 实验结果及分析
• 3.5 基于本体的模块依赖检测
• 3.6 总结
• 第4章 描述逻辑推理近似化
• 4.1 个体获取的语义计算
• 4.2 基于概念泛化和窄化的近似计算
• 4.3 个体获取的近似计算
• 4.4 推理过程的复杂度估计
• 4.4.1 TBox推理的复杂度估算
• 4.4.2 ABox推理的复杂度估算
• 4.5 基于分区的近似化
• 4.5.1 分区方法
• 4.5.2 分布式描述逻辑的近似化
• 4.6 近似化的修正
• 4.7 实验
• 4.7.1 基于语义计算的个体获取
• 4.7.2 概念包含的近似化计算
• 4.7.3 基于推理复杂度估算的近似化
• 4.8 基于本体的制造资源检索
• 4.9 总结
• 第5章 查询近似化
• 5.1 描述逻辑中的查询
• 5.1.1 查询研究的发展
• 5.1.2 查询问题的相关定义
• 5.2 描述逻辑SHOIQ中查询的近似求解
• 5.3 基于优先级的查询近似化
• 5.3.1 带优先级的查询树及其遍历
• 5.3.2 效率分析
• 5.4 基于概化的查询近似化
• 5.5 总结
• 第6章 偏好的OWL表示和推理
• 6.1 引言
• 6.2 定性偏好描述语言
• 6.2.1 分级知识库
• 6.2.2 基本偏好和偏好算子
• 6.2.3 偏好语言
• 6.3 偏好的OWL表示
• 6.3.1 分级知识库的构造
• 6.3.2 模型的表示
• 6.3.3 基本偏好的描述逻辑表示
• 6.3.4 偏好策略算子
• 6.3.5 联结算子
• 6.4 条件偏好
• 6.5 实例和讨论
• 6.6 结论
• 第7章 总结和展望
• 7.1 论文的主要工作概述
• 7.1.1 本文的主要工作
• 7.1.2 本文的创新点
• 7.2 未来工作展望
• 参考文献
• 作者简历及攻读博士学位期间主要的研究成果
• 致谢