论文题目：Differentiable Reasoning on Large Knowledge Bases and Natural Language

论文来源：AAAI 2020 伦敦大学, Facebook

论文链接：https://arxiv.org/abs/1912.10824

代码链接：https://github.com/uclnlp/gntp

关键词：可微推理，机器推理，知识库，自然语言文本，attention

---

---

1 摘要

本文解决的是基于知识库（KB）的推理任务。

基于知识库的推理可以用于许多下游任务，例如机器阅读、对话和问答。

一般的联合学习表示以及文本转换的模型都是数据低效的（data-inefficient），并且难以分析它们的推理过程。

使用端到端的可微推理系统，例如Neural Theorem Provers（NTPs）[1~2]，可以解决上述问题，但只能用于小型的KBs。

可微指的是目标函数可微，因此可以使用反向传播算法优化模型。

本文提出NTPs的扩展Greedy NTPs（GNTPs），摆脱了原有NTP的复杂性和可扩展性的限制，使其能够应用于真实世界的数据集。具体来说，是通过动态构建NTPs的计算图实现的，并且只包含推理过程中最有希望的证明路径，从而得到更有效的模型。

然后作者提出一个方法，通过将逻辑事实和自然语言句子嵌入到共享的向量空间，实现在KBs和文本上的联合推理。

实验结果显示，GNTP需要的计算成本比NTP小，但在链接预测方面有着和NTP可比拟的结果，并且为预测提供了解释，提高了模型的可解释性。

2 引言

（1）传统的自动推理方法

自然语言理解（NLU）和机器阅读（MR）旨在建立能够阅读文本、抽取有意义的知识并能在其上进行推理的模型和系统。这种能力促使了新知识的综合以及验证和更新给定的assertion的可能性。

传统上，应用于文本的自动推理需要使用自然语言处理工具，将其编译成知识库的结构化形式。

然而，编译后的KB往往是不完整的、模糊的、有噪声的，这就影响了标准演绎推理的应用。

---

（2）针对机器阅读的相关研究以及其局限性

已经有许多关于MR的研究解决了上述的问题，例如Natutal Logic、语义分析、自然语言推理和识别文本蕴涵以及问答。

但是这些方法有一些局限性：（1）它们依赖于大量的标注数据来近似数据的隐式分布。当训练数据不充足或者模型的参数先验不合适时，模型的泛化能力就较差。（2）这些方法不能为正确的预测结果提供解释。

---

（3）神经模型和符号推理相结合

一些方法将神经模型和符号（symbolic）推理相结合（两者的优势和劣势可互补）可以解决上述的问题。

1）符号模型

虽然符号模型在训练数据较少时也有着很好的泛化能力，但是当观察结果有很多噪声或模棱两可时，当领域的属性是未知的或难以形式化时，这类模型就不能得到理想的结果。

这些都是考虑自然语言的情况

2）神经模型

相比而言，神经模型对于噪声和模糊性有着更好的鲁棒性，但是可解释性较差，这使得模型不能提供解释或者纳入背景知识。

3）神经符号（neuro-symbolic）系统

最近的神经符号系统的工作已经在端到端的可微推理模型方面取得了进展，这些模型可以通过反向传播进行训练，同时保持了可解释性和泛化能力，继承了符号模型和神经模型两种方法的优点。

---

（4）Neural Theorem Provers（NTPs）

在神经符号系统中，NTPs是基于Prolog编程语言的反向链式算法的端到端的可微演绎推理机，其中原子间的离散统一（discrete unification）替换成了计算其嵌入相似度的可微运算符。

NTPs通过将预测错误反向传播到规则表示，可以从数据中学习到可解释的规则。此外，NTPs中的证明过程是可解释的——得分最大的证明路径（proof path）表示在推理过程中使用了哪些规则和事实。

然而，由于计算复杂度的原因，NTPs只能成功应用于涉及的数据集较小的任务，可扩展性较差。而且，大多数人类知识在KB中是不可得的，但是在自然语言文本上直接进行自动的推理任务又是很困难的。

---

（5）本文提出

作者提出了如下的方法解决了上述的问题：

1）通过减少候选证明路径的数目并引入用于规则归纳的注意力机制，减小了NTPs的时间和空间复杂度；

2）提出面向自然语言的NTPs的扩展，通过使用端到端的可微分读取部件，在共享的空间中联合嵌入谓词和文本表面模式（textual surface patterns）。

本文提出的GNTP模型架构如下所示：

3 端到端的可微性证明

NTPs递归地构建了一个神经网络，枚举了所有可能的证明路径（proof paths）来证明给定知识库上的一个query，并通过max pooling聚合所有的证明分数。

NTPs依赖于3个模块：

a unification module比较了逻辑原子（logic atoms）的子符号（sub-symbolic）表示；

互相递归的or和and模块，联合枚举了所有可能的证明路径，在最后的聚合之前，选择得分最高的一个。

---

接下来介绍这些模块，以及用于从数据中学习模型参数的训练过程。

我们假定KB $\mathfrak{K}$K包括形式为$[p, A, B]^2$[p,A,B]2的一系列事实，表示逻辑原子（logical atom）$p(A, B)$p(A,B)，其中$p$p是关系类型，$A, B$A,B是它的要素（arguments）。该KB还包括如下形式的规则：$H\; :-\; B$H:−B，例如$[p, X, Y]\; :- \; [[q, X, Z], [r, Z, Y]]$[p,X,Y]:−[[q,X,Z],[r,Z,Y]]，表示规则$p(X, Y)\; :- \; q(X, Z), r(Z, Y)$p(X,Y):−q(X,Z),r(Z,Y)，意味着$q(X, Z), r(Z, Y)$q(X,Z),r(Z,Y)隐含着$p(X, Y)$p(X,Y)，其中$X, Y, Z$X,Y,Z是一般的量化的变量。

---

（1）Unification Module

在反向链推理算法中，unification是匹配两个逻辑原子的操作符，例如$locatedIn(London, UK)$locatedIn(London,UK)和$situatedIn(X, Y)$situatedIn(X,Y)。

离散的unification检查组成两个原子的元素是否相等（例如$locatedIn\neq situatedIn$locatedIn​=situatedIn），并通过替换将变量绑定到符号上（例如 ${\{X/London, Y/UK}\}${X/London,Y/UK}）。

在NTPs中，unification通过使用可微的相似度函数，比较两个原子的嵌入表示，来对两个原子进行匹配。这里的相似性函数是高斯核函数，对有相似语义的不同符号进行匹配。

形式上，$unify_{\theta}(H, G, S)=S^{'}$unifyθ​(H,G,S)=S′创造了一个神经网络模块，通过比较两个原子$H, G$H,G的嵌入向量，对两个原子进行匹配。

例如，给定一个目标$G = [locatedIn, London, UK]$G=[locatedIn,London,UK]，一个事实$H = [situatedIn, X, Y]$H=[situatedIn,X,Y]和一个证明状态（proof state）$S = (S_{\psi}, S_{\rho})$S=(Sψ​,Sρ​)（其中$S_{\psi}$Sψ​是替换集合，$S_{\rho}$Sρ​是证明分数），unify模块使用高斯核$k$k比较了$locatedIn$locatedIn和$situatedIn$situatedIn的嵌入表示，更新了绑定到替换集合的变量 $S^{'}_{\psi} = S_{\psi} \cup {\{X/London, Y/UK}\}$Sψ′​=Sψ​∪{X/London,Y/UK}，并计算得到了新的证明分数 $S^{'}_{\rho} = min(S_{\rho}, k(\theta_{locatedIn:}, \theta_{situatedIn:}))$Sρ′​=min(Sρ​,k(θlocatedIn:​,θsituatedIn:​))和证明状态$S^{'} = (S^{'}_{\psi}, S^{'}_{\rho})$S′=(Sψ′​,Sρ′​)。

---

（2） OR Module

Or module计算了一个知识库中一个目标和所有事实和规则头（rule heads）间的unification，然后在相应的规则主体（rule bodies）中递归地调用and module。

对于KB $\mathfrak{K}$K中的每个规则$H\; :-\; B$H:−B，$or^{\mathfrak{K}}_{\theta}(G, d, S)$orθK​(G,d,S)整合了目标$G$G和规则头$H$H，并且调用and module来证明主体$B$B中的原子，保持对最大证明深度d的跟踪：

事实（facts）是没有变量和主体的规则，例如$F\; :-\;[]$F:−[]

例如，给定一个目标$G = [situatedIn, Q, UK]$G=[situatedIn,Q,UK]和一个规则$H \; :- \; B$H:−B，其中$H = [locatedIn, X, Y], B = [ [locatedIn, X, Z], [locatedIn, Z, Y] ]$H=[locatedIn,X,Y],B=[[locatedIn,X,Z],[locatedIn,Z,Y]]。该模型将目标$G$G和规则头$H$H统一起来，并调用and module来证明规则体$B$B中的子目标。

---

（3）AND Module

And module递归地证明了规则体中的列表形式的子目标（sub-goals）。给定第一个子目标$B$B和其余的子目标$\mathbb{B}$B，$and^{\mathfrak{K}}_{\theta}(B\; :\; \mathbb{B}, d, S)$andθK​(B:B,d,S)模块将根据$S$S中的可替换值，对$B$B中的变量进行替换，并且在$B$B上调用or module。

使用最终的结果状态，通过递归地调用and module，证明$\mathbb{B}$B中的原子：

例如，当在上述提到的例子中规则体$B$B上进行调用，对于子目标$[locatedIn, X, Z]$[locatedIn,X,Z]，and module将使用常数替换其中的变量，并调用or module，它的结果状态将是and module在$[locatedIn, X, Z]$[locatedIn,X,Z]下一次调用的偏置（basis）。

---

（4）Proof Aggregation

在构建了用于评估KB $\mathfrak{K}$K上的目标$G$G的所有可能的证明路径（proof paths）的神经网络后，NTPs选择证明分数最大的证明路径：

其中$d\in \mathbb{N}$d∈N是预定义的最大的证明深度（maximum proof depth）。初始的证明状态设为$(\varnothing, 1)$(∅,1)，对应于空的替换集合和proof socre为1。

（5）训练

在NTPs中，递归地mask掉KB中的事实并试图使用其他的事实变量和规则证明出它们，在最终的证明分数上最小化交叉熵损失学习得到嵌入表示。得到负样本的过程记为$corrupt(\cdot)$corrupt(⋅)。损失函数如下所示：

NTPs还可以学习到可解释的规则，有学者指出：规则可以从指定的规则模板中学习得到，例如$H \; :- \; B$H:−B，其中$H = [\theta_{p:}, X, Y], B = [ [\theta_{q:}, X, Z], [\theta_{r:}, Z, Y] ]$H=[θp:​,X,Y],B=[[θq:​,X,Z],[θr:​,Z,Y]]。

其中参数$\theta_{p:}, \theta_{q:}, \theta_{r:} \in \mathbb{R}^k$θp:​,θq:​,θr:​∈Rk表示谓词规则（rule-predicate）的嵌入，可通过最小化式（4）中的损失学习得到，并通过搜索嵌入表示最接近的已知谓词对其编码。

4 在大规模KBs上有效的可微推理

NTPs具有演绎推理的能力，得分最高的证明路径可以为给定的预测提供可读（human-readable）的解释。

然而，枚举并计算出给定目标的所有有深度界限的证明路径（bounded-depth proof paths），如式（3）所示，计算量是很大的，不易计算。

对于每个目标和子目标$G$G，这一过程需要将$G$G和KB中所有的规则头和事实的表示统一起来，即使对于中等大小的KB，这样的计算也是非常耗时的。

此外，通过反向链进行规则的扩展（例如 $p(X, Y):-q(X, Z), r(Z, Y)$p(X,Y):−q(X,Z),r(Z,Y)）会增加需要证明的子目标数目，因为规则体中所有的原子都需要被证明，而且$Z$Z是一个自由变量（free variable）有许多可能的绑定。

给定一个子目标$G$G（例如$[p, A, B]$[p,A,B]）我们考虑两个问题，我们需要高效地选择出：1）$k_f$kf​个最有可能证明子目标$G$G的事实；2）要扩展的$k_r$kr​个规则，以达到高分的证明状态。

---

（1）事实的选择

使用知识库$\mathfrak{K}$K中的所有事实统一一个子目标$G$G，在现实中是不可行的，因为知识库中的事实数量可以到达百万或者十亿级别。

我们将识别出为子目标$G$G提供最大证明分值的事实$F\in \mathfrak{K}$F∈K，转换为如下的最优化问题：

事实$F$F和目标$G$G的统一分数（unification score）是使用高斯核函数，计算它们的嵌入表示$\theta_F, \theta_G$θF​,θG​的相似性$k(\theta_F, \theta_G)$k(θF​,θG​)得到的。

给定一个目标$G$G，NTPs会计算$G$G和KB中每个事实$F$F的统一分数（unification score），计算量是非常大的。然而，$ntp^{\mathfrak{K}}_{\theta}(G, d)$ntpθK​(G,d)只返回了一个最大的证明分数。这就意味着，在推断阶段，我们只需要返回正确的输出最大的证明分数。类似地，在训练阶段，使用单个最大的证明分数，在给定参数$\theta$θ时也可以计算出证明分数的梯度：

本文将给定子目标$G$G和事实$F\in \mathfrak{K}$F∈K间最大统一分数（unification score）的计算视为一个最近邻居搜索问题（NNS）[3]。这是可行的，因为NTPs使用的高斯核是负欧氏距离的单调的变换。

---

（2）规则的选择

使用相似的方法选择出**哪些规则来证明给定的目标$G$G。

我们发现将$G$G与最接近的规则头统一起来，例如$G=[locatedIn, London, UK]$G=[locatedIn,London,UK]和$H=[situatedIn, X, Y]$H=[situatedIn,X,Y]，生成分值高的证明状态的可能性更大。

这是一种符号推理和可微推理间的权衡。符号推理只在heads与目标完全匹配时扩展证明路径，可微推理则会探索所有的证明路径。这促使作者提出了一种启发式的方法，即在推理和学习过程中，动态选择共享模板中的规则。

在实验中，这一用于选择证明路径的启发式方法，能够在目标存在的情况下恢复有效的证明，同时大大降低了可微证明过程的计算复杂度。

作者将KB $\mathfrak{K}$K分割成了$\mathfrak{B} \in 2^{\mathfrak{K}}$B∈2K。$\mathfrak{B}$B将$\mathfrak{K}$K中共享相同模板的规则和事实或者high-level结构划为一组，例如 $\mathfrak{B}$B中的一个元素包含所有有着如下结构的规则：$\theta_{p:}(X, Y) :- \theta_{q:}(X, Z), \theta_{r:}(Z, Y)$θp:​(X,Y):−θq:​(X,Z),θr:​(Z,Y)，其中$\theta_{p:}, \theta_{q:}, \theta_{r:} \in \mathbb{R}^k$θp:​,θq:​,θr:​∈Rk。

将or操作重新定义如下：

也就是说，我们不将所有的规则头和子目标$G$G统一起来，而是仅仅考虑那些是$G$G邻居$\mathcal{N}_P(G)$NP​(G)的规则头。

---

（3）Learning to Attend Over Predicates

尽管NTPs可以用于从数据中学习到可解释的规则，但是Rockt¨ aschel和Riedel提出的方法[4]太低效了。 例如，规则$H:-B,H=[\theta_{p:}, X, Y], B=[ [\theta_{q:}, X, Z], [\theta_{r:}, Z, Y] ]; \theta_{p:}, \theta_{q:}, \theta_{r:} \in \mathbb{R}^k$H:−B,H=[θp:​,X,Y],B=[[θq:​,X,Z],[θr:​,Z,Y]];θp:​,θq:​,θr:​∈Rk，会为模型引入$3k$3k个参数，其中$k$k表示嵌入表示的维度，若$k$k较大时，计算得到这样的嵌入向量会很低效。

作者提出使用注意力机制关注已知的谓词，用于定义rule-predicates embeddings $\theta_{p:}, \theta_{q:}, \theta_{r:}$θp:​,θq:​,θr:​。令$\mathcal{R}$R表示已知的谓词集，$R\in \mathbb{R}^{|\mathcal{R}|\times k}$R∈R∣R∣×k是谓词的嵌入表示矩阵。

我们定义$\theta_{p:} = softmax(a_{p:})^TR$θp:​=softmax(ap:​)TR，其中$a_{p:}\in \mathbb{R}^{|\mathcal{R}|}$ap:​∈R∣R∣是和谓词$p$p相关的可训练的注意力权重集合。

当已知的谓词数量较少时（$|\mathcal{R}|\ll k$∣R∣≪k），为每个规则引入的是$c|\mathcal{R}|$c∣R∣个参数而不用$ck$ck个参数，$c$c是规则中可训练的谓词嵌入的数量。这样就提高了模型的参数高效性。

5 在知识库和自然语言上联合推理

GNTPs可以实现在知识库和自然语言语料上的联合推理。

我们假定知识库$\mathfrak{R}$R由事实、规则和文本提及（textual mentions）组成。一个事实由一个谓词符号和元素的序列组成，例如$[locationOf, London, UK]$[locationOf,London,UK]。一个提及（mention）就是知识库中共现的两个实体间的文本模式，例如“London is located in the UK”。

我们将连接两个实体的每个文本表面模式（textual surface pattern）视为一个新的谓词，并使用端到端的可微读取组件将其嵌入到$d$d维的向量空间中，从而实现使用知识库$\mathfrak{K}$K中的事实和规则同时表示提及（mentions）。

例如句子“United Kingdom borders with Ireland”可以转换成如下的提及：$[ [[arg1], borders, with, [arg2] ], UK, Ireland ]$[[[arg1],borders,with,[arg2]],UK,Ireland]。转换过程的实现步骤如下：首先识别出包含知识库中实体的句子/段落；然后考虑实体间的文本表面模式，将其作为一个额外的关系类型。

使用look-up操作将$\mathcal{R}$R中的谓词编码到谓词嵌入矩阵$R\in \mathbb{R}^{|\mathcal{R}|\times k}$R∈R∣R∣×k中，使用$encode_{\theta}: \mathcal{V}^{*}\rightarrow \mathbb{R}^k$encodeθ​:V∗→Rk模块编码文本表面模式，其中$\mathcal{V}$V是文本表面模式中出现的符号以及单词的单词表。

给定文本表面模式$t\in \mathcal{V}^{*}$t∈V∗，例如$t = [[arg1], borders, with, [arg2] ]$t=[[arg1],borders,with,[arg2]]。编码模块$encode_{\theta}$encodeθ​：

1）首先使用token嵌入矩阵$V\in \mathbb{R}^{|\mathcal{V}|\times k^{'}}$V∈R∣V∣×k′编码$t$t中的每个token $w$w，得到一个模式矩阵$W_t\in \mathbb{|t|\times k^{'}}$Wt​∈∣t∣×k′。

2）然后使用端到端的可微编码器，从$W_t$Wt​中生成一个文本表面模式嵌入向量$\theta_{t:}\in \mathbb{R}^k$θt:​∈Rk。

3）为了评估一个简单的编码结构是否有助于模型，作者使用的$encode_{\theta}$encodeθ​模块，通过mean pooling聚合了组成文本表面模式的tokens的嵌入：$encode_{\theta}(t) = \frac{1}{|t|}\sum_{w \in t} V_{w\cdot} \in \mathbb{R}^k$encodeθ​(t)=∣t∣1​∑w∈t​Vw⋅​∈Rk。

本文使用的可微结构是简单有效的词袋模型（Bag of Embeddings Model），实验证明模型可以得到非常准确的结果。

6 实验

1、数据集

（1）Benchmark datasets

Countries, Nations, UMLS, Kinship

（2）大型数据集

WN18, WN18RR, FB122

2、评估指标

• AUC-PR（Area Under the Precision-Recall Curve）
• MRR（Mean Reciprocal Rank）
• [email protected]

3、实验任务

问答、链接预测

4、对比方法

• NTP

• 以及两个神经符号（neuro-symbolic）推理系统：

1. MINERVA：使用强化学习算法搜索答案
2. NeuralLP：将推断任务编译成可微操作的序列

• 还和两个适用于较大数据集的state-of-the-art的链接预测器：ComplEx和DistMult进行了比较

5、实验结果

（1）和baseline对比的实验结果

---

（2）有生成的mentions的实验结果

为了评估整合textual surface patterns的不同策略，作者在NTPs中以mentions的形式进行了如下的研究。

用人工生成的textual mentions替换了来自Countries S1-S3数据集中的不同数量的训练集三元组。（更多细节见附录）

例如，事实$neighbourOf(UK, Ireland)$neighbourOf(UK,Ireland)可能被替换成textual mention “UK is neighbouring with Ireland”。实体UK和Ireland是元素，它们之间的文本可视为一个新的逻辑谓词，就可以形成一个新的事实“X is neighbouring with Y”(UK, Ireland)。

然后，我们评估了在GNTPs中继承textual mentions的两种方法：1）将它们作为事实添加到KB中；2）使用编码器解析这一mention。结果如图3所示：

从图中可以看出，本文所提出的编码模块和简单地将mentions作为事实添加到KB中相比，结果的准确性更高。

---

（3）链接预测实验结果

在FB122数据集上的链接预测结果如表2所示。结果显示当不知道规则的时候，GNTPs比neural link predictors表现更好。GNTPs能够从数据中归纳出和预测结果有关规则。

---

（4）验证集结果举例

作者还在WN18和WN18RR数据集上评估了GNTP。表3展示了来自于WN18验证集三元组的例子，以及它们的GNTP证明分数和证明路径。

可以看出GNTPs可以学习并利用规则，例如$has\_part(X, Y):=part\_of(Y, X)$has_part(X,Y):=part_of(Y,X)和$hyponym(X, Y):-hypernym(Y, X)$hyponym(X,Y):−hypernym(Y,X)。

而且GNTP还可以基于实体表示间的相似性，为给定的事实找到non-trivial explanations。例如，它可以通过利用ARFICAN_COUNTRY的语义相似性，解释得出Congo（刚果）是Africa的一部分。

7 结论

NTPs结合了基于规则的模型和神经模型的优点，但是它们不能在大型知识库和自然语言上进行推理。

本文克服了这些限制，主要思想是：在构建动态计算图的过程中，仅仅考虑和最大的证明分数相关的证明路径的子集。

本文提出GNTP模型，计算的有效性和以往的工作相比优化了几个量级，并且实现了和NTPs可比拟的预测效果，甚至超越了NTPs。

GNTPs通过将逻辑原子（logic atoms）和textual mentions嵌入到同一个向量空间，实现了在大型知识库和自然语言文本上的端到端的可微推理。

此外，GNTPs具有可解释性，可以从逻辑证明的角度提供有规模的解释。

---

本文解决的是知识推理问题。

本文的亮点在于：实现了基于知识库和自然语言文本的联合推理，并且提高了模型的可解释性。

知识库中的包含的知识是非常有限的，但是直接在自然语言文本上进行推理又十分困难。

本文在NTP的基础之上，对其进行了改进和扩展。NTP的局限性在于：只能应用于基于小规模知识库的任务；只利用了知识库的信息，不能利用自然语言文本的信息。

本文提出的GNTP模型解决了这两个问题：

（1）针对第一个问题，作者提出动态地构建NTP的计算图，通过减少候选证明路径的数目并引入用于规则归纳的注意力机制，减小了NTP的时间和空间复杂度，提高了模型的可扩展能力。

（2）针对第二个问题，作者通过使用端到端的可微分读取部件，在共享的空间中联合嵌入谓词和文本表面模式（textual surface patterns），并使用高斯核函数计算嵌入间的相似性。实现了对自然语言文本信息的利用。

参考文献

[1] Rockt¨ aschel, T., and Riedel, S. 2017. End-to-end Differentiable Proving. In NIPS, 3791–3803

[2] Minervini, P.; Bosnjak, M.; Rockt¨ aschel, T.; and Riedel, S.2018. Towards neural theorem proving at scale. CoRR abs/1807.08204.

[3] Johnson, J.; Douze, M.; and J´ egou, H. 2017. Billionscale similarity search with gpus. arXiv preprint arXiv:1702.08734.

[4] Rockt¨ aschel, T., and Riedel, S. 2017. End-to-end Differentiable Proving. In NIPS, 3791–3803.