Article

作者：Wenhan Xiong and Thien Hoang and William Yang Wang
文献题目：DeepPath：一种知识图推理的强化学习方法
文献时间：2017
https://github.com/xwhan/DeepPath.

摘要

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

引言

• 近年来，深度学习技术在各种分类和识别问题上取得了许多最先进的结果(Krizhevsky et al.，2012;Hinton et al.，2012;Kim,2014)。然而，复杂的自然语言处理问题通常需要多个相互关联的决策，使深度学习模型具有学习推理的能力仍然是一个具有挑战性的问题。为了处理没有明显答案的复杂查询，智能机器必须能够利用现有资源进行推理，并学会推断未知答案。
• 更具体地说，我们把我们的研究放在多跳推理的背景下，这是学习显式推理公式的任务，给定一个较大的KG。例如，如果KG包括内马尔为巴塞罗那效力，而巴塞罗那在甲级联赛中，那么机器应该能够学习到以下公式:球员playsf或球队(P,T)∧球队playsinleague (T,L)中球员playsinleague (P,L)。在测试期间，通过插入学到的公式，系统应该能够自动推断出一对实体之间缺失的环节。这种推理机器有可能成为复杂QA系统的重要组成部分。
• 近年来，路径排序算法(PRA) (Lao et al.，2010,2011a)作为学习大型KGs推理路径的一种很有前途的方法出现。PRA采用基于重启的随机漫步推理机制，执行多个有边界深度优先搜索过程来寻找关联路径。结合基于弹性网络的学习，PRA使用监督学习选择更合理的路径。然而，PRA在一个完全离散的空间中运行，这使得在一个KG中评估和比较相似的实体和关系变得困难。
• 在此工作中，我们提出了一种可控多跳推理的新方法:我们将路径学习过程框架为强化学习(RL)。与PRA不同的是，我们使用基于翻译的基于知识的嵌入方法(Bordes et al.，2013)来编码我们的RL agent的连续状态，这是因为在知识图的向量空间环境中。代理通过对一个关系采样来扩展其路径，从而采取增量步骤。为了更好地指导RL agent学习关系路径，我们使用了带有新颖奖励函数的政策梯度训练(Mnih et al.，2015)，该函数共同鼓励准确性、多样性和效率。从经验上看，我们的方法优于基于Freebase和永不结束语言学习(Carlson等人，2010a)数据集的PRA和嵌入方法。
  • 我们是第一个考虑强化学习(RL)方法学习知识图中的关系路径;
  • 我们的学习方法使用复杂的奖励函数，同时考虑准确性、效率和路径多样性，在寻径过程中提供更好的控制和更大的灵活性;
  • 我们的方法可以扩展到大规模的知识图，在两个任务中优于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等(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 等人，2017 年）也已应用于视觉推理任务。

方法

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

关系推理的强化学习

• RL 系统由两部分组成（见图 1）。 第一部分是外部环境 $E$，它指定了代理和 KG 之间交互的动态。 这种环境被建模为马尔可夫决策过程（MDP）。定义了一个元组$<S,A,P,R>$来表示MDP，其中$S$是连续状态空间， A = { a 1 , a 2 , . . . , a n } A = \{ a_1, a_2, ..., a_n \} A={a1​,a2​,...,an​} 是所有可用动作的集合，$P(S_{t+1}=s^{\prime }|S_t=s,A_t=a)$ 是转移概率矩阵，$R(s,a)$ 是每个 $(s,a)$ 对。
  
• 系统的第二部分，即 RL 代理，表示为策略网络 ${\pi }_{\theta }(s,a)=p(a|s;\theta )$，它将状态向量映射到随机策略。 使用随机梯度下降更新神经网络参数 $\theta$。 与 Deep Q Network (DQN) (Mnih et al., 2013) 相比，基于策略的 RL 方法更适合我们的知识图场景。 一个原因是对于 KG 中的寻路问题，由于关系图的复杂性，动作空间可能非常大。 这可能会导致 DQN 收敛性能不佳。 此外，与学习 DQN 等基于价值的方法中常见的贪婪策略不同，策略网络能够学习防止代理陷入中间状态的随机策略。 在我们描述策略网络的结构之前，我们首先描述 RL 环境的组件（动作、状态、奖励）。
• 动作。给定具有关系$r$ 的实体对 $(e_s,e_t)$，我们希望代理找到链接这些实体对的信息最丰富的路径。 从源实体 $e_s$ 开始，代理使用策略网络选择最有希望的关系，以在每一步扩展其路径，直到到达目标实体 $e_t$。 为了保持策略网络的输出维度一致，动作空间被定义为 KG 中的所有关系。
• 状态。KG 中的实体和关系自然是离散的原子符号。 由于像 Freebase (Bollacker et al., 2008) 和 NELL (Carlson et al., 2010b) 这样的实用 KG 通常有大量的三元组。 直接对状态中的所有符号原子进行建模是不可能的。 为了捕获这些符号的语义信息，我们使用基于翻译（translation-based）的嵌入，例如 TransE（Bordes 等，2013）和 TransH（Wang 等，2014）来表示实体和关系。 这些嵌入将所有符号映射到低维向量空间。 在我们的框架中，每个状态都捕获了代理在 KG 中的位置。 采取行动后，代理将从一个实体移动到另一个实体。 这两者通过代理刚刚采取的动作（关系）联系起来。 步骤 $t$ 的状态向量如下：
  
• 其中$e_t$表示当前实体节点的embeddings，$e_{target}$表示目标实体的embeddings。 在初始状态，$e_t=e_{source}$。 我们没有在状态中加入推理关系，因为在寻路过程中推理关系的嵌入保持不变，这对训练没有帮助。 然而，我们发现通过使用一组特定关系的正样本训练 RL 代理，代理可以成功地发现关系语义。
• 奖励。有几个因素会影响 RL 代理找到的路径的质量。 为了鼓励代理找到预测路径，我们的奖励函数包括以下评分标准：
• 全局准确性：对于我们的环境设置，代理可以采取的操作数量可能非常大。 换句话说，不正确的顺序决策比正确的决策要多得多。 这些不正确的决策序列的数量会随着路径的长度呈指数增长。 针对这一挑战，我们添加到 RL 模型中的第一个奖励函数定义如下：
  
• 如果代理在一系列动作后到达目标，则给予离线正奖励 +1。
• 路径效率：对于关系推理任务，我们观察到短路径往往比长路径提供更可靠的推理证据。 较短的关系链还可以通过限制 RL 与环境交互的长度来提高推理效率。 效率奖励定义如下：
  
• 其中路径 $p$ 被定义为一系列关系 $r_1\to r_2\to ...\to r_n$。
• 路径多样性：我们训练代理使用每个关系的正样本找到路径。 这些训练样本$(e_{source},e_{target})$在向量空间中具有相似的状态表示。 代理倾向于找到具有相似语法和语义的路径。 这些路径通常包含冗余信息，因为其中一些可能是相关的。 为了鼓励代理找到不同的路径，我们使用当前路径和现有路径之间的余弦相似度定义了一个多样性奖励函数：
  
• 其中 $p={\sum }_{i=1}^n{r}_i$ 表示关系链 $r_1\to r_2\to ...\to r_n$ 的路径嵌入。
• 策略网络。 我们使用一个完全连接的神经网络来参数化策略函数 $\pi (s;\theta )$，该函数将状态向量 $s$ 映射到所有可能动作的概率分布。 神经网络由两个隐藏层组成，每个隐藏层后跟一个整流非线性层 (ReLU)。 输出层使用 softmax 函数进行归一化（见图 1）。

训练pipeline

• 在实践中，KG 推理的一大挑战是关系集可能非常大。对于典型的 KG，RL 代理经常面临数百（数千）个可能的操作。换句话说，策略网络的输出层具有很大的维度。由于关系图的复杂性和较大的动作空间，如果我们通过试错法直接训练 RL 模型，这是 RL 算法的典型特征，RL 模型将表现出非常差的收敛性。经过长时间的训练，智能体没有找到任何有价值的路径。为了解决这个问题，我们从受 AlphaGo 使用的模仿学习管道启发的监督策略开始我们的训练（Silver 等，2016）。在围棋游戏中，玩家每一步都要面对近 250 种可能的合法走法。直接训练代理从原始动作空间中选择动作可能是一项艰巨的任务。 AlphaGo 首先使用专家动作训练一个有监督的策略网络。在我们的例子中，监督策略是用随机广度优先搜索 (BFS) 训练的。
• 监督策略学习。对于每个关系，我们使用所有正样本（实体对）的子集来学习监督策略。 对于每个正样本$(e_{source},e_{target})$，进行双边 BFS 以在实体之间找到相同的正确路径。 对于具有一系列关系 $r_1\to r_2\to ...\to r_n$ 的每个路径 $p$，我们更新参数 $\theta$ 以使用蒙特卡洛策略梯度（REINFORCE）（威廉姆斯，1992 年）最大化预期累积奖励。
  
• 其中 $J(\theta )$ 是一集的预期总奖励。 对于监督学习，我们对成功情节的每一步都给予 +1 的奖励。 通过插入 BFS 找到的路径，用于更新策略网络的近似梯度如下所示：
  
• 其中$r_t$ 属于路径 $p$。
• 然而，vanilla BFS 是一种偏向搜索算法，它更喜欢短路径。 当插入这些有偏差的路径时，代理很难找到可能有用的更长的路径。 我们希望路径仅由定义的奖励函数控制。 为了防止有偏见的搜索，我们采用了一个简单的技巧来向 BFS 添加一些随机机制。 我们不是直接搜索esource和etarget之间的路径，而是在中间节点einter中随机选择一个，然后在（esource，einter）和（einter，etarget）之间进行两次BFS。 连接的路径用于训练代理。 监督学习节省了代理从失败动作中学习的巨大努力。 有了学到的经验，我们然后训练代理找到理想的路径。
• 注释：BFS（广度优先搜索）
  • 广度优先搜索较之深度优先搜索之不同在于，深度优先搜索旨在不管有多少条岔路，先一条路走到底，不成功就返回上一个路口然后就选择下一条岔路，而广度优先搜索旨在面临一个路口时，把所有的岔路口都记下来，然后选择其中一个进入，然后将它的分路情况记录下来，然后再返回来进入另外一个岔路，并重复这样的操作，用图形来表示则是这样的，例子同上
    
  • 从黑色起点出发，记录所有的岔路口，并标记为走一步可以到达的。然后选择其中一个方向走进去，我们走黑点方块上面的那个，然后将这个路口可走的方向记录下来并标记为2，意味走两步可以到达的地方。
    
• 接下来，我们回到黑色方块右手边的1方块上，并将它能走的方向也记录下来，同样标记为2，因为也是走两步便可到达的地方。
  
  • 这样走一步以及走两步可以到达的地方都搜索完毕了，下面同理，我们可以迅速把三步的格子给标记出来
    
  • 再之后是四步，五步。
    
  • 我们便成功寻找到了路径，并且把所有可行的路径都求出来了。在广度优先搜索中，可以看出是逐步求解的，反复的进入与退出，将当前的所有可行解都记录下来，然后逐个去查看。在DFS中我们说关键点是递归以及回溯，在BFS中，关键点则是状态的选取和标记。
• 用奖励重新训练。为了找到由奖励函数控制的推理路径，我们使用奖励函数来重新训练监督策略网络。对于每个关系，对一个实体对的推理被视为一个情节。从源节点 $e_{source}$ 开始，代理根据随机策略 $\pi (a|s)$ 选择一个关系，这是所有关系的概率分布，以扩展其推理路径。这个关系链接可能会导致一个新的实体，也可能什么也不会。这些失败的步骤将导致代理收到负面奖励。在这些失败的步骤之后，代理将保持相同的状态。由于代理遵循随机策略，代理不会因重复错误步骤而卡住。为了提高训练效率，我们用上限最大长度来限制情节长度。如果代理未能在最大长度步长内到达目标实体，则情节结束。在每一集之后，使用以下梯度更新策略网络：
  
• 其中 $R_{total}$ 是定义的奖励函数的线性组合。 算法 1 中显示了重新训练过程的细节。在实践中，$\theta$ 是使用带有 L2 正则化的 Adam Optimizer（Kingma 和 Ba，2014）更新的。
  

双向路径约束搜索

• 给定一个实体对，RL 代理学习到的推理路径可以用作逻辑公式来预测关系链接。 每个公式都使用双向搜索进行验证。 在一个典型的KG中，
  一个实体节点可以链接到大量具有相同关系链接的邻居。 一个简单的例子是关系 personNationality−1，它表示 personNationality 的倒数。 通过此链接，实体美国可以联系到许多邻近实体。 如果公式由这样的链接组成，那么当我们遵循推理公式时，中间实体的数量会呈指数增长。 但是，如果我们从相反方向验证公式，我们会观察到这些公式。 中间节点的数量可以大大减少。 算法 2 显示了所提出的双向搜索的详细描述。
  

实验

• 为了评估我们的 RL 代理发现的推理公式，我们探索了两个标准的 KG 推理任务：链接预测（预测目标实体）和事实预测（预测未知事实是否成立）。 我们将我们的方法与基于路径的方法和基于嵌入的方法进行比较。 之后，我们进一步分析了我们的 RL 代理发现的推理路径。 这些高度预测的路径验证了奖励功能的有效性。 最后，我们进行了一个实验来研究监督学习程序的效果。

数据集和设置

• 表 1 显示了我们进行实验的两个数据集的统计数据。它们都是较大数据集的子集。 FB15K-237 (Toutanova et al., 2015) 中的三元组是从 FB15K (Bordes et al., 2013) 中采样的，去除了冗余关系。我们在 20 个具有足够推理路径的关系上执行推理任务。这些任务包括来自不同领域的关系，如体育、人物、地点、电影等。此外，我们提出了一个新的 NELL 子集，适用于 NELL 系统第 995 次迭代的多跳推理。我们首先删除具有关系泛化或 haswikipediaurl 的三元组。这两个关系在 NELL 数据集中出现超过 200 万次，但它们没有推理值。在这一步之后，我们只选择具有 Top-200 关系的三元组。为了方便寻路，我们还添加了逆三元组。对于每个三元组 $(h,r,t)$，我们将 $(t,r^{-1},h)$ 附加到数据集。通过这些逆三元组，agent 能够在 KG 中后退。
  
• 对于每个推理任务 $r_i$，我们从 KG 中删除所有具有 $r_i$ 或 ${r_i}^{−1} 的三元组。 这些移除的三元组被分成训练样本和测试样本。 对于链接预测任务，测试三元组 { ( h , r , t ) } \{ (h, r, t) \} {(h,r,t)} 中的每个 $h$ 被视为一个查询。 一组候选目标实体使用不同的方法进行排名。 对于事实预测，真实的测试三元组与一些生成的错误三元组进行排名。

基线和实施细节

• 大多数 KG 推理方法基于路径公式或 KG 嵌入。 我们在实验中探索了这两个类的方法。 对于基于路径的方法，我们将我们的 RL 模型与 PRA（Lao 等人，2011a）算法进行比较，该算法已用于几种推理方法（Gardner 等人，2013 年；Neelakan tan 等人， 2015）。 PRA 是一种数据驱动算法，使用随机游走 (RW) 来寻找路径并获取路径特征。 对于基于嵌入的方法，我们评估了为知识库完成而设计的几种最先进的嵌入，例如 TransE（Bordes 等人，2013 年）、TransH（Wang 等人，2014 年）、TransR（Lin 等人） al., 2015) 和 TransD (Ji et al., 2015)。
• PRA 的实现基于 (Lao et al., 2011a) 发布的代码。 我们使用 TopK 负模式为训练和测试样本生成负样本。 对于每个正样本，大约有 10 个对应的负样本。 每个负样本是通过在每个三元组 $(h,r,t)$ 中用伪造的一个 $t^{\prime }$ 替换真实目标实体 $t$ 来生成的。 PRA 生成的这些正负测试对构成了本文评估的所有方法的测试集。 对于 TransE、R、H、D，我们使用正训练实体对为每个推理任务学习一个单独的嵌入矩阵。 所有这些嵌入都经过了 1000 个 epoch 的训练。
• 我们的 RL 模型利用 TransE 来获得实体和关系的连续表示。 我们使用与 TransE、R 相同的维度来嵌入实体。 具体来说，我们使用的状态向量的维度为 200，这也是策略网络的输入大小。 为了使用路径公式进行推理，我们采用与 PRA 中类似的线性回归方法来重新排列路径。 然而，我们没有使用随机游走概率作为路径特征，这在计算上可能会很昂贵，我们只是使用通过双向搜索获得的二元路径特征。 我们观察到，只有少数挖掘路径公式，我们的方法可以获得比 PRA 的数据驱动方法更好的结果。

结果

定量结果

• 链接预测。此任务是对给定查询实体的目标实体进行排名。 表 2 显示了两个数据集的平均精度 (MAP) 结果。 由于在此任务中，基于路径的方法通常比嵌入方法更有效，因此我们没有在此表中包含其他两个嵌入基线。 相反，我们腾出空间来展示每个关系推理任务的详细结果。
  
• 对于表最后一行显示的整体 MAP，我们的方法在两个数据集上明显优于基于路径的方法和嵌入方法，这验证了我们 RL 模型的强大推理能力。 对于大多数关系，由于嵌入方法无法使用 KG 中的路径信息，因此它们的性能通常比我们的 RL 模型或 PRA 差。 但是，当实体之间没有足够的路径时，我们的模型和 PRA 可能会给出较差的结果。 例如，对于关系 filmWrittenBy，我们的 RL 模型只找到 4 个唯一的推理路径，这意味着 KG 中实际上没有足够的推理证据。 另一个观察结果是我们总是在 NELL 数据集上获得更好的性能。 通过分析从 KG 中找到的路径，我们相信潜在的原因是 NELL 数据集比 FB15K-237 具有更多的短路径，其中一些只是推理关系的同义词。
• 事实预测。该任务不是对目标实体进行排序，而是直接对特定关系的所有正样本和负样本进行排序。 这里不包括 PRA 作为基线，因为 PRA 代码只给出每个查询节点的目标实体排名，而不是所有三元组的排名。 表 3 显示了所有方法的总体结果。 我们的 RL 模型在这项任务上取得了更好的结果。 我们还观察到 RL 模型在大多数推理任务中击败了所有嵌入基线。
  

推理路径的定性分析

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

监督学习的效果

• 如第 3.2 节所述，将 RL 应用于 KG 推理的一个主要挑战是大的动作空间。我们通过在奖励再训练步骤之前应用监督学习来解决这个问题。为了显示监督训练的效果，我们评估了代理在不同数量的训练集后在 10 步 (succ10) 内达到目标的成功率。对于每个训练集，训练集中的一对实体$(e_{source},e_{target})$用于查找路径。所有连接实体的正确路径都将获得 +1 全局奖励。然后我们插入一些真实的训练路径。 succ10 是在由 100 个实体对组成的保留测试集上计算的。对于 NELL-995 数据集，由于我们有 200 个唯一关系，因此添加反向动作后动作空间的维度将为 400。这意味着随机游走将获得非常低的 succ10，因为可能有近 40010 条无效路径。图 3 显示了训练期间的 succ10。我们看到，即使智能体之前没有见过实体，它实际上可以选择有希望的关系来扩展其路径。这也验证了我们国家代表的有效性。

结论和未来工作

• 在本文中，我们提出了一个强化学习框架来提高 KG 中关系推理的性能。 具体来说，我们训练 RL 代理以在知识库中找到推理路径。 与之前基于随机游走的寻路模型不同，RL 模型允许我们控制找到的路径的属性。 在许多基于路径的推理方法中，这些有效路径也可以用作 PRA 的替代方法。 对于两个标准推理任务，使用 RL 路径作为推理公式，我们的方法通常优于两类基线。
• 对于未来的研究，我们计划研究结合对抗性学习（Goodfellow 等人，2014 年）的可能性，以提供比这项工作中使用的人类定义的奖励函数更好的奖励。 可以训练判别模型来提供奖励，而不是根据路径特征设计奖励。 此外，为了解决 KG 没有足够推理路径时的问题场景，我们有兴趣将我们的 RL 框架应用于 KG 三元组和文本提及的联合推理。