【知识图谱论文】AnyBURL：用于知识图完成的随时自下而上的规则学习

Article

文献题目：Anytime Bottom-Up Rule Learning for Knowledge Graph Completion
发表期刊：IJCAI-19

摘要

• 我们提出了一种随时自下而上的技术，用于从大型知识图中学习逻辑规则。 我们应用学习到的规则在知识图完成的上下文中预测候选人。 我们的方法优于其他基于规则的方法，并且与当前基于潜在表示的最先进技术具有竞争力。 此外，我们的方法明显更快，需要更少的计算资源，并根据提出候选人的规则产生解释。

引言

• 在过去的十年中，知识图谱完成已成为一个生动的研究领域。 虽然目前的研究主要关注基于将知识图嵌入低维向量空间的想法的潜在表示，但符号方法引起的关注要少得多 [Wang et al., 2017]。 然而，这种方法有一个很大的优势，那就是它们能够根据触发预测的规则产生解释。
• 在本文中，我们提出了一种自下而上的技术，用于从大型知识图谱中有效地学习逻辑规则。 我们的工作受到自下而上的规则学习方法 Golem [Muggleton and Feng, 1990] 和 Aleph [Srinivasan, 2000] 的启发，这些方法是在归纳逻辑编程 (ILP) 的早期开发的。 自下而上的方法基于这样一种思想，即一个例子是一个非常具体的规则的紧凑表示，可以概括为捕获所有正例的综合子集。 Aleph 就是其中一种方法。 它将给定的正例转换为称为底部规则的霍恩规则。 然后通过从规则主体中删除原子来推广该规则，直到找到满足所选质量标准的规则。 规则涵盖的示例被删除，并再次应用该方法，直到涵盖所有示例。
• 我们的方法在几个方面有所不同。 首先，我们没有严格的边界来告诉我们哪些观察属于给定的例子，哪些不属于它。 相反，我们必须决定以什么为例。 我们的示例概念基于路径的概念。 从这个意义上说，我们的方法类似于路径排名算法 (PRA) [Lao et al., 2011]。 但是，PRA 仅将我们可能学习的规则的子集视为特征。
• 其次，我们有兴趣学习不确定的规则，即，至少涵盖一些正面的规则，通常也包括一些负面的例子。 即使是低置信度的规则也可能有助于我们为知识图完成任务创建更好的候选排名。 此外，我们不能删除规则涵盖的示例，因为可能有其他规则也涵盖（某些）这些示例和其他示例，具有不同的置信度分数。
• 第三，我们的算法旨在成为知识图谱的有效规则挖掘器。 在知识图谱中，所有事实（也称为三元组）都是由带有常数的二元谓词产生的。 因此，可以将知识图谱分解为一组带有边缘标记的路径。 这就是为什么在没有一元谓词或 $n\ge 3$ 的 $n$ 元谓词的情况下关注路径是有意义的主要原因。
• 知识图谱补全（或链接预测）问题目前主要由将给定知识图谱嵌入潜在特征空间的方法主导。学习一个明确的符号表示很少被提议作为替代本机。这可能与基本假设有关，即仅基于规则的方法不能解决的不仅仅是一个琐碎的子集。例如，参见 [Dettmers et al, 2018] 中提出的逆模型的讨论以及与 FB15k 中的冗余相关的批评 [Toutanova and Chen, 2015]。另一个假设可能是规则学习不能应用于大型数据集。出于这个原因，当前的研究架构关注规则和嵌入的组合（例如，[Guo et al 2018]）。我们认为潜在的假设是错误的，并且目前的结果支持我们的主张。特别是，我们提出了一种随时自下而上的学习规则算法，并将我们的方法应用于知识完成任务。我们展示了五个不同数据集的结果。其中三个已被提议作为利用对称性和其他冗余的简单（基于规则）方法的困难案例。我们的方法与最近提出的大多数模型一样好，有时甚至更好。如果我们在短时间内停止算法，我们的方法的结果仍然非常好。此外，与潜在方法所需的资源相比，内存和运行时所需的资源要小得多。

语言偏见

• 知识图 $G$ 定义在词汇 $<C,R>$ 之上，其中 $C$ 是一组常量，$R$ 是一组二元谓词。 因此， G = { r ( a , b ) ∣ r ∈ R , a , b ∈ C } G = \{r(a, b) | r ∈ R, a, b ∈ C\} G={r(a,b)∣r∈R,a,b∈C} 是一组基本原子或事实。 二元谓词称为关系，常量（或常量所指的）也称为实体。 下面我们用小写字母表示常量，用大写字母表示变量。 由于我们不学习任意的 Horn 规则，因此对于可以学习什么样的规则存在语言偏见，如下所述。
• 我们称规则为 $h(c_0,c_1)\leftarrow b_1(c_1,c_2),...,b_n(c_n,c_{n+1})$ 为长度为 $n$ 的地面路径规则。 规则的头部是 $h(...)$，$b_1(...)$ 到 $b_n(...)$ 是它的主体。 如果对于$l$，$c_k\ne c_l$ , 对于 $l\ne k$， k ∈ { 1 , . . . , n } k ∈ \{1, ..., n\} k∈{1,...,n} 并且如果对于$0<k<n+1$， $c_0\ne c_k$ ，我们说基本路径规则是直的。 规则在体内没有循环。 在我们的形式化中，我们从变量的顺序中抽象出来，因为我们也考虑了带有翻转变量的规则，而没有明确地写下来。 直接地路径规则可分为$c_0=c_{n+1}$ 的循环规则和$c_0\ne c_{n+1}$ 的非循环规则。 我们认为，任何来自长度为 $n$ 的直线地面路径规则的有用推广，它也不是较短路径规则的推广或非直线路径规则的推广，属于三种类型 ${AC}_1$、$A{C}_2$ 或 $C$ 定义如下。 我们使用 $X$ 和 $Y$ 表示出现在头部的变量，而 $A_i$是只出现在正文中的变量。
  
• $A{C}_2$ 规则是非循环基本路径规则的推广，$C$ 规则是循环基本路径规则的推广，而 $A{C}_1$ 规则可以从循环$（c_0=c_{n+1}）$和非循环规则$（c_0\ne c_{n+1}）$推广。
• 任何比属于这三种类型的规则更具体的规则都必须有一个 $k<n+1$ 的常量 $c_k$，而不是变量 $A_k$。 关于 $A{C}_1$ 和 $A{C}_2$ 类型，我们必须区分两种情况： (1) body原子 $b_k(...)$ 到 $b_n(...)$ 的结合计算为真，因此可以将它们从规则中删除。 在这种情况下，也可以从长度为 $k$ 的较短路径创建规则。 稍后将澄清我们在整个算法的先前迭代中学习此规则。 (2) 原子 $b_k(...)$ 到 $b_n(...)$ 的合取总是为 false，这导致规则永远不会触发。