知识图谱推理论文阅读（一）DeepPath

论文原文

DeepPath: A Reinforcement Learning Method for Knowledge Graph Reasoning

发表时间

2017

摘要

我们研究了大规模知识图中的推理学习问题。更具体地说，我们描述了一种新的用于学习多跳关系路径的强化学习框架:我们使用基于知识图嵌入的连续状态的基于策略的agent，它通过抽样最有希望的关系来扩展其路径，在KG向量空间中进行推理。与之前的工作不同，我们的方法包括一个考虑准确性、多样性和效率的奖励功能。在Freebase和Never-Ending的语言学习数据集上，我们的实验表明，我们提出的方法优于基于路径排名的算法和知识图嵌入方法。

介绍

近年来，深度学习技术在各种分类和识别问题上取得了许多最新的成果(Krizhevsky et al.，2012;Hinton et al.，2012; Kim,2014)。然而，复杂的自然语言处理问题往往需要多个相互关联的决策，使深度学习模型具有学习推理的能力仍然是一个具有挑战性的问题。为了处理没有明显答案的复杂查询，智能机器必须能够利用现有资源进行推理，并学会推断一个未知的答案。

更具体地说，我们把我们的研究放在多跳推理的背景下，这是一个给定大知识图谱，学习显式推理公式的任务。 例如，如果KG包括内马尔为巴塞罗那效力，而巴塞罗那在英甲联赛，那么机器应该能够学习以下公式:playerPlaysForteam (P,T)∧teamPlaysInLeague(T,L) \Rightarrow playerPlaysInLeague(P,L)。在测试的时候，通过输入学到的公式，系统应该能够自动推断出一对实体之间缺失的链接。这种推理机可能会成为复杂QA系统的重要组成部分。

近年来，路径排序算法(Path-Ranking Algorithm, PRA) (Lao et al.，2010,2011a)在大型KGs中作为一种有前途的学习推理路径的方法出现。PRA采用随机行走和基于重启的推理机制，执行多个有界深度优先搜索过程来寻找关系路径。再加上基于弹性网的学习，PRA使用监督学习选择更合理的路径。然而，PRA操作在一个完全离散的空间中，这使得评估和比较KG中相似的实体和关系变得困难。

在这项工作中，我们提出了一种新的可控多跳推理方法:我们使用强化学习(RL)为路径学习过程框架。与PRA相比，我们使用基于平移的基于知识的嵌入方法(Bordes et al.，2013)来编码我们的RL 代理的连续状态，这是在知识图的向量空间环境中推理的。代理通过对一个关系进行抽样来扩展它的路径，从而采取增量步骤。为了更好地指导RL agent学习关系路径，我们使用了策略梯度训练(Mnih等人，2015)和一个新的奖励函数，共同鼓励准确性、多样性和效率。实验结果表明，该方法在Freebase和一个永无休止的语言学习(Carlson et al.，2010a)数据集上优于PRA算法和基于嵌入的算法的方法。我们的贡献有三:

1. 我们首先考虑强化学习(RL)方法来学习知识图中的关系路径。
2. 我们的学习方法使用复杂的奖励函数，同时考虑准确性、效率和路径多样性，在寻径过程中提供更好的控制和更大的灵活性。
3. 我们证明，我们的方法可以扩展到大规模的知识图，在两个任务中优于PRA和KG嵌入方法。

在下一节中，我们将概述在KGs中寻径和嵌入方法方面的相关工作。我们将在第3节描述所提出的方法。我们在第4节给出了实验结果。最后，我们在第5节进行总结。

相关工作

路径排序算法(PRA)方法(Lao et al.，2011b)是一种主要的寻路方法，采用带重启策略的随机行走进行多跳推理。Gardner等人(2013;2014)对PRA提出了一种改进，在向量空间中计算特征相似度。Wang和Cohen(2015)提出了一种将背景KG和文本相结合的递归随机行走方法，该方法同时进行逻辑程序的结构学习和文本中的信息提取。随机游走推理的一个潜在瓶颈是，连接大量公式的超级节点将创建巨大的扇出区域，显著降低推理速度并影响精度。

Toutanova等人(2015)为多跳推理提供了一种卷积神经网络解决方案。他们建立了一个基于词汇化依赖路径的CNN模型，该模型由于解析错误而存在错误传播问题。Guu等人(2015)使用KG嵌入来回答路径查询。Zeng et al.(2014)描述了一个用于关系抽取的CNN模型，但它没有明确地建模关系路径。Neelakantan等人(2015)提出了一种用于知识库完成(KBC)中关系路径建模的递归神经网络模型，但它训练了太多的独立模型，因此不能缩放。注意，许多最近的KG推理方法(Neelakantan等人，2015;Das等人，2017)仍然依赖于首次学习PRA路径，这只在离散空间中操作。与PRA相比，我们的方法在连续空间中进行推理，并且通过在奖励函数中引入各种标准，我们的强化学习(RL)框架对寻径过程具有更好的控制和更大的灵活性。神经符号机(Liang et al.，2016)是KG推理的最新成果，它也应用了强化学习，但与我们的工作有不同的风格。NSM学习编写可以找到自然语言问题答案的程序，而我们的RL模型试图通过对已有的KG三元组进行推理，将新的事实添加到知识图(KG)中。为了得到答案，NSM学会生成一系列动作，这些动作可以组合成一个可执行程序。NSM中的操作空间是一组预定义的令牌。在我们的框架中，目标是寻找推理路径，因此动作空间就是KG中的关系空间。类似的框架(Johnson et al.，2017)也被应用于视觉推理任务。

方法

在本节中，我们将详细描述基于rl的多跳关系推理框架。关系推理的具体任务是在实体对之间寻找可靠的预测路径。我们将寻路问题表述为一个可以用RL代理解决的顺序决策问题。我们首先描述环境和基于策略的RL代理。通过与围绕KG设计的环境交互，代理学会选择有希望的推理路径。然后描述了RL模型的训练过程。在此基础上，提出了一种有效的路径约束搜索算法，利用RL代理找到的路径进行关系推理。

关系推理的增强学习

增强学习系统包含了两部分（如图1）。第一个部分是外部环境ε，它描述了代理与图谱之间相互作用的动态过程。环境被建模成马尔科夫决策过程（MDP）。一个三元组<S,A,P,R>被定义去表示MDP，其中S是连续状态空间，A是一系列状态的集合，

是转移可能性矩阵，并且R（s,a)是每个（s,a)对的奖励函数。

系统的第二个部分，RL代理，被表示成一个策略网络，

将状态向量映射成一个随机的策略。神经网络参数θ被使用随机梯度下降更新。与DQN相比，基于策略的RL方法对于我们的知识图语义来说更合适。一个原因是对于在KG中的路径寻找问题，动作空间由于图中关系数量太多而变得太大。这会使DQN难以收敛。此外，该策略网络可以学习随机策略，避免agent在中间状态卡死，而不是像DQN等基于值的方法中常见的贪婪策略。在描述我们的策略网络结构之前，我们首先描述RL环境的组成部分(动作、状态、奖励)。
动作

给定具有关系r的实体对（es,et)，我们想要代理找到最有信息量的路径连接这些实体。从源实体es开始，代理使用策略网络去找到最有前途的关系去扩展每一步的路径知道到达目标实体et。为了使策略网络的输出维度恒定， 动作空间被定义为KG中的所有关系。

状态

KG中的实体和关系自然是离散的原子符号。因为现有的实际KGs，如Freebase (Bollacker et al.， 2008)和NELL (Carlson et al.，2010b)经常有大量的三元组。不可能直接模拟所有状态中的符号原子。为了捕获这些符号的语义信息，我们使用基于翻译的嵌入，如TransE (Bordes et al.，2013)和TransH (Wang et al.，2014)来表示实体和关系。这些嵌入将所有符号映射到一个低维向量空间。在我们的框架中，每个状态捕获代理在KG中的位置。在执行一个操作之后，代理将从一个实体移动到另一个实体。这两者通过代理所采取的动作(关系)联系在一起。时间步t处的状态向量如下:

其中et表示当前实体节点的嵌入，etarget表示目标实体的嵌入，在最初状态中，et=esource，我们没有在状态中加入推理关系，因为在寻径过程中推理关系的嵌入是不变的，这对训练没有帮助。然而，我们发现，通过使用一组针对特定关系的正样本来训练RL agent，该agent可以成功地发现关系语义。

奖励

有几个因素会影响RL代理找到的路径的质量。为了鼓励代理找到预测路径，我们的奖励函数包括以下评分标准:

全局奖励

对于我们的环境设置，代理可以采取的操作数量可能非常大。换句话说，错误的顺序决策比正确的顺序决策多得多。这些错误决策序列的数量会随着路径的长度呈指数增长。鉴于这一挑战，我们添加到RL模型中的第一个奖励函数定义如下:

如果agent在一系列动作后到达目标，它将获得离线正奖励+1。

路径效率

对于关系推理任务，我们观察到短路径比长路径更能提供可靠的推理证据。更短的关系链也可以通过限制RL与环境交互的长度来提高推理的效率。效率奖励的定义如下。

其中p被定义为关系序列r1->r2->...->rn。

路径多样性

我们训练agent为每个关系使用正样本寻找路径。这些训练样本(esource、etarget)在向量空间中具有类似的状态表示。代理倾向于找到具有相似语法和语义的路径。这些路径通常包含冗余信息，因为其中一些路径可能是相关的。为了鼓励agent寻找多样化的路径，我们利用当前路径与现有路径之间的余弦相似度定义一个多样性奖励函数:

其中

表示关系链r1->r2->...->rn的路径嵌入。

策略网络
我们使用一个全连接神经网络去确定把状态向量映射成一个对于所有动作的可能性分布的策略函数∏（s；θ）的参数。这个网络包含两个隐藏层，每个后面都跟着一个非线性层ReLU,输出层被使用一个softmax函数进行标准化（如图1）

训练Pipeline

在实践中，KG推理的一个大挑战是关系集可以相当大。对于一个典型的KG, RL代理经常面临数百(数千)种可能的操作。换句话说，政策网络的输出层通常具有较大的维度。由于关系图的复杂性和大的动作空间，如果直接采用RL算法典型的试错训练方法训练RL模型，RL模型的收敛性很差。经过长时间的训练，代理没有找到任何有价值的途径。为了解决这个问题，我们从阿尔法狗使用的模仿学习管道(Silver et al.，2016)启发的有监督的政策开始训练(Silver et al.，2016)。在围棋游戏中，玩家每一步都要面对近250种可能的合法走法。直接训练agent从原始动作空间中选择动作可能是一项困难的任务。AlphaGo首先利用专家的移动训练一个有监督的策略网络。在我们的例子中，这个有监督策略使用随机广度优先搜索(BFS)进行训练。

有监督学习

对于每个关系，我们使用一个所有正例的子集去学习有监督的策略。对于每个正样本（esource,etarget)，一个双边BFS被用来寻找两个路径之间同样正确的路径。对于有一系列关系r1->r2->...->rn的每条路径p，我们使用蒙特卡洛策略梯度更新参数θ去最大化期望累计奖励：

其中J（θ）是每一个迭代轮次的期望总奖励。对于监督学习，对于每个成功的轮次我们都给出了一个+1的奖励。通过使用BFS查找堵塞路径， 用来更新策略网络的近似梯度如下图所示：

其中rt属于路径p。

然而，vanilla BFS是一种偏向于短路径的搜索算法。当插入这些有偏差的路径时，代理很难找到可能有用的更长的路径。我们希望路径只被定义的奖励功能所控制。为了防止偏移搜索，我们采用了一个简单的技巧，在BFS中添加了一些随机机制。与直接在esource和etarget之间搜索路径不同，我们随机选择了一个中间节点einter，并且在esource和etarget之间执行了两次BFS搜索算法。 连接的路径用于训练代理。有监督的学习可以让agent从失败的动作中学习。通过学习到的经验，我们训练agent找到理想的路径。

有奖励重训练

为了找到被奖励函数控制的推理路径，我们使用奖励函数去重训练有监督的策略网络。对于每个关系，一个实体对的推理被视为一个episode。从源节点esource开始，代理通过有所有关系上的可能性分布的随机策略函数π(a|s)去扩展推理路径。这个关系链路可能引导去一个新的实体也可能什么都没有。这些错误的步骤将会导致代理得到负奖励。并且代理将会在这个错误的步骤后停留在相同的状态上。因为代理是跟从一个随机的策略，所以代理将不会被重复的错误步骤死锁。为了提高训练效率，我们将给episode的长度一个上线max length。如果在maxlength步骤内代理无法到达目标实体这个episode就会结束。在每一个episode后，策略网络使用以下梯度被更新：

这里的Rtotal是被定义的奖励函数的线性组合。重训练过程的细节在算法1中被展示了。在实际中，θ被用L2正则化，用Adam优化器更新。

双向路径限制搜索

给定一个实体对，RL代理学习到的推理路径可以被作为逻辑公式去预测关系链路。每一个公式都被使用双向搜索证明了。在一个典型的KG中，一个实体节点可以被同一个关系链接到大量的邻居节点上。一个简单的例子是关系personNationality，这个关系加上实体美国可以到达大量的邻居实体。如果一个公式中包含这样的链路，我们推理的公式的中间实体的数量就会指数级增加。然而，我们观察这些公式，如果我们反向验证这些公式，那么中间节点的数量将会显著地减少，算法2中展示了提出的双向搜索的详细描述。

实验

为了验证我们的强化学习代理找到的推理公式，我们探究了两个标准KG推理任务：链路预测（预测目标实体）和实体预测（预测一个未知事实是否存在）。我们将我们的方法与基于路径的方法和基于嵌入的方法做比较。在这之后，我们进一步分析了我们的RL代理找到的推理路径。这些高度语言的路径验证了奖励函数的有效性。最后，我们进行了一个实验去调查监督学习过程的效果。

数据集和背景

表1显示了我们进行实验的两个数据集的统计数据。他们都是大型数据集的子集。FB15K-237 (Toutanova et al.，2015)中的三重组取自FB15K (Bordes et al.，2013)，去除冗余关系。我们在具有足够推理路径的20个关系上执行推理任务。这些任务包含不同领域的关系，如电子竞技、人物、地点、电影等。此外，我们从NELL系统的995次迭代中提出了一个新的适用于多跳推理的NELL子集。我们首先用关系泛化或haswikipediaurl删除三元组。这两种关系在NELL数据集中出现了超过200万次，但它们没有推理价值。在这一步之后，我们只选择关系为Top-200的三元组。为了便于寻径，我们还添加了逆三元组。对于每个三元组(h, r, t)，我们将(t, r−1,h)附加到数据集。使用这些逆三元组，代理能够在KG中后退。

对于每个推理任务ri，我们把所有ri或者ri-1的三元组从KG中移除。这些被移除的三元组被分成训练和测试样例。对于链路预测任务，在测试三元组中的每个头实体被视为一次查询。一系列的候选目标实体被使用不同的方法排序。对于事实预测，真实的测试三元组与一些生成的错误三元组进行排序。

baseline和实现细节

大多数KG推理方法是基于路径公式或KG嵌入。在我们的实验中，我们探索了这两个类别的方法。对于基于路径的方法，我们将我们的RL模型与PRA (Lao et al.，2011a)算法进行了比较，PRA算法已被用于几种推理方法(Gardner et al.，2013;Neelakantan et al.，2015)。PRA是一种数据驱动的寻路算法，采用RW (random walks)算法进行寻路，获取路径特征。对于基于嵌入的方法，我们评估了几种设计用于知识库补全的最先进的嵌入方法，如TransE (Bordes et al.，2013)、TransH (Wang et al.， 2014)、TransR (Lin et al.，2015)和TransD (Ji et al.，2015)。
PRA的实现是基于(Lao et al.,2011a).发布的代码。我们使用TOPK负模式去生成训练和测试的负样例。对于每个正样例，有接近10个相关的负样例。每个负样本是通过替换三元组中真实目标实体生成的。 这些由PRA生成的正、负测试对构成了本文所评估的所有方法的测试集。对于TransE,R,H,D，我们使用正向训练实体对为每个推理任务学习一个单独的嵌入矩阵。所有这些嵌入都经过了1000个epoch的训练。

我们的RL模型利用TransE得到实体和关系的连续表示。我们使用与TransE, R相同的维度来嵌入实体。具体来说，我们使用的状态向量的维数为200，这也是政策网络的输入大小。为了使用路径公式进行推理，我们采用与PRA类似的线性回归方法对路径重新排序。然而，我们简单地使用双向搜索获得的二进制路径特征，而不是使用计算代价昂贵的随机行走概率作为路径特征。我们观察到，与PRA的数据驱动方法相比，我们的方法仅使用少量的挖掘路径公式，就可以获得更好的结果。

结果

量化的结果

链路预测。这个任务是给定一个查询实体去给目标实体排序。表2展示了在两个数据集上的平均准确率。

由于基于路径的方法通常比嵌入方法在这个任务中工作得更好，我们不包括其他两个嵌入基线在这个表中。相反，我们腾出空间来展示每个关系推理任务的详细结果。
对于表中最后一行所示的整体MAP，我们的方法在两个数据集上显著优于基于路径的方法和嵌入方法，这验证了我们的RL模型强大的推理能力。对于大多数关系，由于嵌入方法没有使用知识图谱中的路径信息，他们整体上表现的不如我们的模型和PRA。然而，当实体间没有足够的路径时，我们的模型和PRA会给出一个错误的结果。比如，对于关系filmWrittenBy,我们的模型只找到了四个不同的推理路径，这意味着确实没有足够的推理证据存在于图谱中。另一个观察是我们总是在NELL数据集上得到更好的结果。通过分析KG中的路径，我们相信潜在的原因是NELL数据集有比FB15K-237更多的短路径，并且它们中的一些只是推理关系的同义词。

事实预测

与对目标实体排序不同，这个任务直接为一个具体的关系排序了所有的正负样例。PRA在这里没有作为baseline，因为PRA代码只给出了对于每一个查询节点的目标实体排名而不是所有三元组的排名。表3展示了所有方法的总体结果。我们的RL模型在这个任务上得到了更好的结果。我们也观察到了RL模型在大多数推理任务中击败了所有的嵌入baseline。