DeepPath: A Reinforcement Learning Method for Knowledge Graph Reasoning

摘要

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

1.介绍

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

更具体地说，我们将我们的研究置于多跳推理的环境中，这是在给定较大KG的情况下学习显式推理公式的任务。例如，如果KG包含了内马尔为巴萨效力的信念，而巴萨在西甲联赛中，那么机器应该能够学习以下公式:

在测试时间内，通过插入学习到的公式，系统应该能够自动推断出一对实体之间缺失的链接。这种推理机器有可能成为复杂QA系统的一个重要组成部分。

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

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

我们的贡献有三个方面:

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

在下一节中，我们将概述在KGs中寻找路径和嵌入方法的相关工作，并在第三节中描述所提出的方法。我们在第4节展示了实验结果。最后，我们在第5节中总结。

2.相关工作

路径排序算法(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 et al.， 2017)仍然依赖于首次学习PRA路径，这只在一个离散空间中运行。与PRA方法相比，我们的方法在连续空间中进行推理，通过在奖励函数中加入各种准则，我们的强化学习(RL)框架对寻径过程具有更好的控制性和灵活性。

神经符号机器(Liang et al.， 2016)是关于KG推理的最新研究，它也应用了强化学习，但与我们的研究有不同的风格。NSM学习编写能够找到自然语言问题答案的程序，而我们的RL模型试图通过对已有的KG三元组进行推理，向知识图(KG)中添加新的事实。为了得到答案，NSM学习生成一系列动作，这些动作可以组合成一个可执行程序。NSM中的操作空间是一组预定义的标记。在我们的框架中，目标是寻找推理路径，因此动作空间在KG中是关系空间。一个类似的框架(Johnson et al.， 2017)也被应用于视觉推理任务。

3.方法

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

3.1关系推理的强化学习

RL系统由两部分组成(见图1)。第一部分是外部环境，它规定了agent与KG之间相互作用的动态。该环境被建模为马尔可夫决策过程(MDP)。定义一个元组< S, A, P, R >来表示MDP，其中S是连续状态空间，A = {a1, a2，…， an}是所有可用动作的集合，P(St+1 = s 0|St = s, At = a)是转移概率矩阵，R(s, a)是每个(s, a)对的奖励函数。

图1:RL模型概述。左:KG环境E由MDP建模。虚线箭头(部分)显示KG中现有的关系链接，粗体箭头显示RL代理找到的推理路径。−1表示关系的逆。右:策略网络代理的结构。在每一步，通过与环境的交互，代理学会选择一个关系链接来扩展推理路径。

系统的第二部分RL代理被表示为策略网络πθ(s, a) = p(a|s;θ)，将状态向量映射到随机策略。采用随机梯度下降法对神经网络参数θ进行更新。与深度Q网络(DQN) (Mnih et al.， 2013)相比，基于策略的RL方法更适合我们的知识图场景。一个原因是，对于KG中的寻径问题，由于关系图的复杂性，行动空间可能非常大。这可能导致DQN收敛性较差。此外，与DQN等基于值的方法中常见的贪心策略不同，策略网络能够学习一种随机策略，防止agent陷入中间状态。在我们描述策略网络的结构之前，我们首先描述RL环境的组件(动作、状态、奖励)。

3.1.1动作

给定关系为r的实体对(es, et)，我们希望代理找到链接这些实体对的最有信息的路径。从源实体es开始，代理使用策略网络选择最有希望的关系，每一步扩展其路径，直到到达目标实体et。为了保持策略网络输出维数的一致性，将动作空间定义为KG中的所有关系。

3.1.2状态

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

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

3.1.3奖励

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

全局准确性

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

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

路径效率

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

路径多样性

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

 

政策网络

我们利用全连接神经网络参数化策略函数π(s;θ)将状态向量s映射到所有可能动作的概率分布。该神经网络由两个隐藏层组成，每个隐藏层后面都有一个整流非线性层(ReLU)。输出层使用softmax函数进行规范化(参见图1)。

3.2训练管道Training Pipeline

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

3.2.1监督政策的学习

对于每个关系，我们使用所有正样本(实体对)的一个子集来学习监督策略。对于每个正样本，进行双侧BFS以找到实体之间相同的正确路径。对于每一条路径p，其关系序列为r1→r2→…→rn，我们使用蒙特卡洛策略梯度(REINFORCE) (Williams, 1992)更新参数θ以最大化预期累积奖励:

其中J(θ)为某一事件的期望总奖励。对于监督式学习，我们为每一步成功的情节给予+1的奖励。通过插入BFS找到的路径，用于更新策略网络的近似梯度如下图所示：

然而，普通的BFS算法是一种偏向于短路径的有偏差搜索算法。当插入这些有偏差的路径时，代理很难找到可能有用的较长的路径。我们希望路径只由定义好的奖励函数来控制。为了防止偏差搜索，我们采用了一个简单的技巧，即在BFS中加入一些随机机制。我们不直接搜索source和target之间的路径，而是随机选取一个中间节点inter，然后在(esource, einter)和(einter, target)之间进行两次BFS。连接的路径用于训练代理。监督学习节省了agent从失败的行为中学习的大量精力。有了学习到的经验，然后我们训练代理找到理想的路径。

3.2.2Retraining with Rewards

为了找到由奖励函数控制的推理路径，我们使用奖励函数对监督策略网络进行再训练。对于每一个关系，使用一个实体对的推理被视为一个插曲。agent从源节点esource开始，根据随机策略π(a|s)选取一个关系，该随机策略π是所有关系的一个概率分布，以扩展其推理路径。这种联系可能导致一个新的实体，也可能导致什么都没有。这些失败的步骤将导致代理收到负奖励。在这些失败的步骤之后，代理将保持相同的状态。由于代理遵循随机策略，代理不会因为重复错误的步骤而陷入困境。为了提高训练效率，我们用最大长度的上界来限制集的长度。如果代理在最大长度步长内未能到达目标实体，则事件结束。在每一集之后，政策网络使用以下梯度更新:

其中Rtotal为所定义奖励函数的线性组合。再培训过程的细节如算法1所示。在实践中，θ是使用Adam Optimizer (Kingma和Ba, 2014)与L2正则化更新

 再培训带有奖励功能的程序

3.3Bi-directional Path-constrained Search

给定一个实体对，RL代理学习到的推理路径可以作为预测关系链接的逻辑公式。每个公式都通过双向搜索进行验证。在典型的KG中，一个实体节点可以通过相同的关系链路连接到大量的邻居。一个简单的例子是personNationality−1关系，它表示personNationality的反义词。通过这个链接，实体美国可以联系到许多邻近的实体。如果公式包含这样的链接，那么随着我们遵循推理公式，中间实体的数量可以呈指数增长。然而，我们观察到对于这些公式，如果我们从反方向验证公式。中间节点的数量可以大大减少。算法2给出了双向搜索的详细描述。

 4.实验

为了评估我们的RL代理找到的推理公式，我们探索了两个标准的KG推理任务:链接预测(预测目标实体)和事实预测(预测一个未知事实是否成立)。我们将我们的方法与基于路径的方法和基于嵌入的方法进行了比较。然后，我们进一步分析了RL agent所找到的推理路径。这些高度预测的路径验证了奖励函数的有效性。最后，我们进行了一个实验来研究监督学习过程的效果。

4.1数据集与设置

数据集的统计信息。# Ent表示唯一实体的数量，# R表示关系的数量

表1展示了我们进行实验的两个数据集的统计情况。它们都是大型数据集的子集。FB15K-237中的三元组(Toutanova et al.， 2015)取自FB15K (Bordes et al.， 2013)，去除冗余关系。我们对20个具有足够推理路径的关系进行推理。这些任务包括不同领域的关系，如体育、人物、地点、电影等。此外，我们提出了一个新的NELL子集，该子集适用于NELL系统的第995次迭代的多跳推理。我们首先使用关系泛化或haswikipediaurl删除三元组。这两种关系在NELL数据集中出现了超过2M次，但它们没有推理值。在这一步之后，我们只选择具有Top-200关系的三元组。

4.2基线和实现细节

基于路径：PRA(随机游走)

基于嵌入：TransE、TransH、TransR、TransD

PRA的实施基于(Lao et al.， 2011a)发布的代码。我们使用TopK负样本模式为训练样本和测试样本生成负样本。对于每一个正样本，大约有10个对应的负样本。每一个负样本是在每一个三元组(h, r, t)中用假的t‘代替真实的目标实体t而产生的。由PRA产生的这些正、负测试对构成了本文所评估的所有方法的测试集。对于TransE,R,H,D，我们使用正训练实体对学习每个推理任务的单独嵌入矩阵。所有这些嵌入都经过了1000个时代的训练。

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

4.3结果

4.3.1定量结果

链接预测

这个任务是给定一个查询实体对目标实体进行排序。表2显示了两个数据集上的平均精度(MAP)结果下表展示了两数据集平均精度(MAP)的结果

由于基于路径的方法在这个任务中通常比嵌入方法工作得更好，所以我们在这个表中没有包括其他两个嵌入基线。相反，我们留出时间来展示每个关系推理任务的详细结果。

对于表中最后一行显示的整体MAP，我们的方法在两个数据集上都明显优于基于路径的方法和嵌入方法，这验证了我们的RL模型较强的推理能力。对于大多数关系，由于嵌入方法不能使用KG中的路径信息，它们通常比我们的RL模型或PRA模型性能更差。然而，当实体之间的路径不足时，我们的模型和PRA会给出较差的结果。例如，对于关系filmwrittenby，我们的RL模型只找到了4条独特的推理路径，这意味着KG中实际上没有足够的推理证据存在。另一个观察结果是，我们总是在NELL数据集上获得更好的性能。通过分析KGs中找到的路径，我们认为可能的原因是NELL数据集比FB15K-237有更多的短路径，其中一些只是推理关系的同义词。

事实预测

这个任务没有对目标实体进行排序，而是直接对特定关系的所有正样本和负样本进行排序。这里不包括PRA作为基线，因为PRA代码只给出每个查询节点的目标实体排名，而不是所有三元组的排名。

表3显示了所有方法的总体结果。我们的RL模型在这个任务中得到了更好的结果。我们还观察到，在大多数推理任务中，RL模型优于所有嵌入基线。

 两个数据集的事实预测结果(MAP)  。

4.3.2 定性分析

为了分析推理路径的特性，我们在表5中展示了agent找到的一些推理路径。为了说明效率奖励函数的效果，我们在图2中展示了路径长度分布。为了解释这些路径，以人的国籍关系为例，第一条推理路径表明，如果我们知道事实，那么人x的国籍极有可能是z。这些简短但具有预测性的路径表明了RL模型的有效性。另一个重要的观察结果是，我们的模型使用的推理路径比PRA少得多，这表明我们的模型实际上可以从KG中提取最可靠的推理证据。表4显示了一些关于推理路径数量的比较。我们可以看到，通过预定义的奖励函数，RL代理能够挑选出强的，并过滤出相似或不相关的。

推理路径短，可以从 KG 中提取最可靠的推理证据。

我们的RL模型找到的示例推理路径。前三个关系来自FB15K-237数据集。其他的来自NELL-995。现有关系的逆用−1表示。

两个数据集上路径长度的分布

 表4:PRA和我们的RL模型使用的推理路径数。RL通过更紧凑的学习路径集实现了更好的MAP

4.3.3监督学习的效果

将 RL 应用于 KG 推理的一个主要挑战是大的行为空间。我们通过在奖励再训练步骤之前应用监督学习来解决这个问题。

为了展示监督训练的效果，我们评估了不同训练次数的agent在10步(succ10)内达到目标的成功率。对于每个训练集，使用训练集中的一对实体(源，目标)来寻找路径。所有连接实体的正确路径将获得+1的全局奖励。然后我们插入一些真正的训练路径。succ10是在一个由100对实体对组成的测试集中计算的。对于NELL995数据集，因为我们有200个惟一的关系，所以在添加向后操作后，操作空间的维度将为400。这意味着随机漫步将获得非常低的succ10，因为可能有将近40010个无效路径。图3显示了培训期间的succ10。我们看到，即使代理以前没有见过实体，它实际上也可以选择有希望的关系来扩展它的路径。这也验证了我们的状态表示的有效性。

 5.结论与未来工作

在本文中，我们提出了一种强化学习框架来提高KGs中关系推理的性能，具体地说，我们训练一个RL代理在知识库中寻找推理路径。与之前基于随机漫步的路径查找模型不同，RL模型允许我们控制所找到路径的属性。在许多基于路径的推理方法中，这些有效路径也可以作为PRA的替代方案。对于两个标准的推理任务，使用RL路径作为推理公式，我们的方法通常优于两类基线。

研究结合对抗学习的可能性，以提供比这项工作中使用的人类定义的奖励函数更好的奖励。可以训练判别模型来提供奖励，而不是根据路径特征设计奖励。

此外，为了解决KG没有足够的推理路径时的问题场景，我们有兴趣将我们的RL框架应用于带有KG三元组和文本提及的联合推理。