6.15 基于符号的推理方法

1 . 知识图谱的表示语言

介 绍 知 识 图 谱 中 基 于 符 号 的 推 理 方 法 之前，需要先对知识图谱的知识表示（knowledgerepresentation）有一个了解。 前面提到，知识图谱是一个语义网络，即一种用互联的的节点和弧来表示知识的一个结构[1] 。语义网络中的节点可以代表一个概念（concept）、一个属性（attribute）、一个事件（event）或者一个实体（entity），而弧则用来表示节点之间的关系，弧的标签指明了关系的类型。虽然语义网络作为一种自然语言的知识表示方法受到了很多关注，Woods 在 1975 年的一篇论文指出语义网络中的弧的语义存在问题[2] 。由于一阶谓词逻辑具有形式化语义，所以很多研究人员开始建立一阶谓词逻辑和语义网络之间的对应关系，从而赋予语义网络形式化语义（如文献 [3]）。但是，由于一阶谓词逻辑的推理复杂度是不可判定的，所以一般业界很少关注这种对应。为了使得语义网络同时具备形式化语义和高效推理，一些研究人员提出了易处理（tractable）概念语言，如 KL-ONE [4] 和 CLASSIC [5] ，并且开发了一些商用化的语义网络系统。这些系统的提出，使得针对概念描述的一系列逻辑语言，统称描述逻辑（descriptionlogic），得到了学术界和业界广泛关注。但是这些系统的推理效率难以满足日益增长的数据的需求，最终没能得到广泛应用。这一困局被利物浦大学的Ian Horrocks 教授打破，他开发的 FaCT 系统可以处理一个比较大的医疗术语本体 GALEN，而且性能比其他类似的推理机要好得多[6] 。描述逻辑最终成为了 W3C 推荐的 Web 本体语言 OWL 的逻辑基础[7] 。W3C 还推出了另外一种用于表示 Web 本体的语言 RDF Schema（简称 RDFS） 2 。

2 . 大规模知识推理

虽然描述逻辑推理机的优化取得了很大进展，但是还是跟不上数据增长的速度，特别是当数据规模大到目前的基于内存的服务器无法处理的情况下。为了应对这一挑战，最近几年，研究人员开始考虑将描述逻辑和 RDFS 的推理并行来提升推理的效率和可扩展性，并且取得了很多成果。并行推理工作所借助的并行技术分为以下两类：① 单机环境下的多核、多处理器技术，比如多线程、GPU 技术等；② 多机环境下基于网络通信的分布式技术，比如 MapReduce 计算框架、Peer-To-Peer 网络框架等。很多工作尝试利用这些技术实现高效的并行推理。

基于多核、多处理器技术的大规模推理

单机环境下的并行技术以共享内存模型为特点，侧重于提升本体推理的时间效率。对于实时性要求较高的应用场景，这种方法成为首选。对于表达能力较低的语言，比如 RDFS、OWL EL，单机环境下的并行技术将显著地提升本体推理效率。Goodman 等人在文献 [8] 中利用高性能计算平台Cray XMT 实现了大规模的 RDFS 本体推理，利用平台计算资源的优势限制所有推理任务在内存完成。然而对于计算资源有限的平台，内存使用率的优化成为了不可避免的问题。Motik 等人在文献 [9]工作中将 RDFS，以及表达能力更高的 OWL RL 等价地转换为 Datalog 程序，然后利用 Datalog 中的并行优化技术来解决内存的使用率问题。 在文献 [10] 中，作者尝试利用并行与串行的混合方法来提升 OWL RL 的推理效率。Kazakov 等人在文献 [11] 中提出了利用多线程技术实现 OWL EL 分类(classification) 的方法，并实现推理机 ELK。

基于分布式技术的大规模推理

尽管单机环境的推理技术可以满足高推理性能的需求，但是由于计算资源有限（比如内存、存储容量），推理方法的可伸缩性（scalability）受到不同程度的限制。因此，很多工作利用分布式技术突破大规模数据的处理界限。这种方法利用多机搭建集群来实现本体推理。

Oren 等人[12]是首个尝试利用 Peer-To-Peer的分布式框架实现 RDF 数据推理的工作。实验结果表明，利用分布式技术可以完成很多在单机环境下无法完成的大数据量推理任务。很多工作基于MapReduce 的开源实现（如 Hadoop、Spark 等）设计提出了大规模本体的推理方法。其中较为成功的一个尝试是 Urbani 等人在 2010 年公布的推理系统 WebPIE [13] 。实验结果证实其在大集群上可以完成上百亿的 RDF 三元组的推理。他们又在这个基础上研究提出了基于 MapReduce 的 OWL RL 查询算法[14] 。文献 [15] 提出了利用 MapReduce 来实现OWL EL 本体的推理算法，实验证明 MapReduce技术同样可以解决大规模的 OWL EL 本体推理。在文献 [16] 的工作中，进一步扩展 OWL EL 的推理技术，使得推理可以在多个并行计算平台完成。