Leveraging Graph Neighborhoods for Efficient Inference
Leveraging Graph Neighborhoods for Efficient Inference
复制标题
DOI：
10.1145/3357384.3358049
复制
发表时间：
2019-11
期刊：
影响因子：
--
通讯作者：
M. Chekol;H. Stuckenschmidt
中科院分区：
文献类型：
--
作者：
M. Chekol;H. Stuckenschmidt
描述逻辑语言的几种概率扩展已经被提出并进行了深入研究。然而，它们的实际应用却因各种推理任务的棘手性而受到阻碍。虽然当今的知识库 (KB) 包含数百万个实例和数千个公理，但大多数最先进的推理器都能够处理具有数千个实例的小规模知识库。因此，最近的研究重点是利用知识库和查询的结构来加快推理运行时间。然而，这些努力在提供适合大规模知识库实际使用的推理器方面并不能令人满意。在这项研究中，我们的目标是解决这个具有挑战性的问题。在此过程中，我们使用 OWL RL 的概率扩展（称为 PRORL）作为建模语言，并利用图邻域（无向图模型）进行有效的近似概率推理。我们表明，基于子图提取的推理速度更快，并且具有与全图推理相当的准确性。为了支持我们的主张，我们在包含数百万个实例和数千个公理的 NELL 知识库上进行了多项实验。此外，我们提出了一种新颖的基于图的算法，可以根据推理规则的结构自动划分推理规则，以实现高效的并行推理。
Several probabilistic extensions of description logic languages have been proposed and thoroughly studied. However, their practical use has been hampered by intractability of various reasoning tasks. While present-day knowledge bases (KBs) contain millions of instances and thousands of axioms, most state-of-the-art reasoners are capable of handling small scale KBs with thousands of instances. Thus, recent research has focused on leveraging the structure of KBs and queries in order to speed up inference runtime. However, these efforts have not been satisfactory in providing reasoners that are suitable for practical use in large scale KBs. In this study, we aim to tackle this challenging problem. In doing so, we use a probabilistic extension of OWL RL (called PRORL) as a modeling language and exploit graph neighborhoods (of undirected graphical models) for efficient approximate probabilistic inference. We show that subgraph extraction based inference is much faster and has comparable accuracy to full graph inference. We perform several experiments, in order to support our claim, over a NELL KB containing millions of instances and thousands of axioms. Furthermore, we propose a novel graph-based algorithm to automatically partition inferences rules based on their structure for efficient parallel inference.