一、摘要和引言

摘要：研究了大规模知识图(KGs)中的推理学习问题。更具体地说，我们描述了一种新的用于学习多跳关系路径的强化学习框架:我们使用基于知识图嵌入的具有连续状态的基于策略的agent，该agent通过抽样最有希望的关系来扩展其路径，从而在KG向量空间中进行推理。与之前的研究相比，我们的方法包含了一个考虑到准确性、多样性和效率的奖励功能。实验表明，在Freebase和永无休止的语言学习数据集上，我们提出的方法优于基于路径排序的算法和知识图嵌入方法
引言：
更具体地说，我们将我们的研究置于多跳推理的背景下，这是任务学习显式推理公式，给出较大的KG。例如，如果KG包含诸如内马尔为巴塞罗那队效力，巴塞罗那队在西甲联赛，那么机器应该能够学习如下公式:playerPlaysF orTeam(P ,T) ∧ teamPlaysIn-League(T,L) ⇒ playerPlaysInLeague(P ,L).在测试期间，通过插入所学的公式，系统应该能够自动推断出一对实体之间缺失的环节。这种推理机器有可能成为复杂QA系统的重要组成部分。
近年来，路径排序算法(PRA) (Lao et al.， 2010, 2011a)成为在大型KGs中学习推理路径的一种有前景的方法。PRA使用基于重启的随机漫步推理机制执行多个有界深度优先搜索过程来寻找关联路径。与基于弹性网络的学习相结合，PRA使用监督学习来选择更合理的路径。然而，PRA是在一个完全离散的空间中运作的，这使得在一个KG中评估和比较相似的实体和关系变得困难。在这项工作中，我们提出了一种新的可控多跳推理方法:我们将路径学习过程框架为强化学习(RL)。与PRA不同，我们使用基于翻译的基于知识的嵌入方法(Bordes et al.， 2013)对RL代理的连续状态进行编码，这是在知识图的向量空间环境下进行的。代理通过对关系进行抽样来扩展其路径，从而采取增量步骤。为了更好地指导RL agent学习关系路径，我们使用策略梯度训练(Mnih et al.， 2015)和一个新的奖励功能，共同鼓励准确性、多样性和效率。经验表明，我们的方法优于PRA和基于嵌入的方法。基于Freebase和永不停息的语言学习数据集的方法(Carlson et al.， 2010a)。我们的贡献有三方面:
1. 我们首先考虑了知识图中关系路径的强化学习(RL)方法;
2. 我们的学习方法使用了一个复杂的奖励函数，同时考虑了准确性、效率和路径多样性，在寻径过程中提供了更好的控制和更多的灵活性;
3. 结果表明，该方法可以扩展到大规模的知识图，在两个任务中优于PRA和KG嵌入方法。

二、模型介绍和相关工作

模型介绍

关系推理的具体任务是在实体对之间寻找可靠的预测路径。我们将寻径问题定义为一个序贯决策(sequential decision)问题，该问题可以用RL代理来解决。我们首先描述环境和基于策略的RL代理。通过与围绕KG设计的环境交互，agent学会选择有希望的推理路径。然后描述了RL模型的训练过程。在此基础上，我们描述了一种有效的基于RL代理所找到的路径约束的关系推理搜索算法。 1.关系推理的强化学习 RL系统由两部分组成(见图)。第一部分是外部环境E，它规定了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)的奖励函数。

系统的第二部分RL代理表示为一个将状态向量映射到随机策略的策略网络πθ(s, a) = p(a|s;θ)。采用随机梯度下降法更新神经网络参数θ。与Deep Q Network(DQN) (Mnih et al.， 2013)相比，policy-based的RL方法更适合我们的知识图场景。原因之一是，对于KG中的寻径问题，由于关系图的复杂性，行动空间可能非常大。这可能导致DQN的收敛性较差。此外，该策略网络学习的不是DQN等基于价值的方法中常见的贪婪策略，而是可以学习一个防止agent陷入中间状态的随机策略。在我们描述政策网络的结构之前，我们首先描述RL环境的组成部分(行为、状态、奖励)
Actions
给定关系为r的实体对(es, et)，我们希望代理找到连接这些实体对的最有信息价值的路径。开始从源实体es,代理使用政策网络选择最有前途的关系来扩展它的路径在每一步,直到达到目标实体等。保持政策网络的输出尺寸一致,行动空间被定义为所有的关系在KG。
States
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=esource，由于在寻径过程中推理关系的嵌入是不变的，所以我们没有将推理关系包含在状态中，这对训练没有帮助。然而，我们发现，通过使用一组特定关系的正样本训练RL代理，该代理可以成功地发现关系语义。
Rewards

有几个因素影响着RL代理所发现的路径的质量。为了鼓励agent找到预测路径，我们的奖励功能包括以下评分标准:

• 全局准确率（global accuracy）：

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

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

• 路径有效性（path efficiency）：

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

路径p被定义为一系列的关系

• 路径多样性（path diversity）：

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

其中，表示关系嵌入
Policy Network
我们使用一个完全连接的神经网络来参数化策略函数π(s;θ)，它将状态向量s映射到所有可能行动的概率分布。该神经网络由两个隐含层组成，每个隐含层后面有一个整流非线性层(ReLU)。输出层使用softmax函数进行规范化。

模型训练过程

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

监督策略训练：
对于每个关系，我们使用所有正样本(实体对)的子集来学习监督策略。对于每个正样本(e_source, e_target)，进行双边BFS，以找到实体之间相同的正确路径。对于每条路径p，其关系序列为r1→r2→…→rn，我们使用蒙特卡罗政策梯度(RE- carlo Policy Gradient, RE-INFORCE）更新参数最大化期望奖励累计函数。

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

其中rt属于路径p。
然而，传统的BFS算法是一种偏向于短路径的搜索算法。但是，我们希望路径只被定义的奖励功能所控制。为了防止偏差搜索，我们采用了一个简单的技巧，在BFS中添加一些随机机制。我们不是直接搜索esource和etarget之间的路径，而是随机选择一个中间节点einter，然后在(e_source, e_inter)和(e_inter, e_target)之间进行两次BFS。连接的路径用于训练代理。有监督学习为agent从失败的行为中学习节省了大量的精力。通过学习到的经验，我们训练agent去寻找理想的路径。
使用奖励函数再训练：
对于每个关系，一个实体对的推理被视为一个episode。从源节点e_source开始，agent根据随机策略π(a|s)来选择一个关系，π是所有关系的概率分布，扩展其推理路径。

初始点 e_source ,根据所有关系的概率分布 π(a∣s)选择一个动作扩展推理路径，关系链接可能会指向一个新的实体也可能没有对应的下一个实体，这些失败的步骤导致智能体获得一个负的奖励。在经过错误的步骤后，智能体保持相同的状态，由于采用随机策略，智能体不会陷于重复一个错误的步骤。
如果代理未能在最大长度步骤内到达目标实体，则插曲结束。每个episode节目结束后，政策网络将按照以下梯度进行更新:

R_total是已定义的奖励函数的线性组合，在实践中，θ是使用带有l2正则化的Adam优化器
双向路径约束搜索：
给定一个实体对，智能体学习到推理路径可以被用来作为逻辑公式预测关系链接。每个公式使用双向的搜索进行验证，目的是减小搜索空间。举例：对于关系personNationality^⁻¹^，the US 有很多邻居实体，如果一个公式包含很多这样的链接，中间节点会指数增加，但是如果从相反方向来验，中间节点的数量会大大减少。

三、实验

为了验证智能体找到的推理公式，本文实验了两个推理任务：链接预测（找目标实体）、事实预测（事实成不成立）
为了便于寻径，我们还添加了逆三元组。对于每个三元组(h, r, t)，我们将(t, r⁻¹,h)添加到数据集。通过这些逆三元组，代理可以在KG中后退一步

对于每个推理任务r_i，我们从KG中移除所有带有r_i或者r_i^-1的三元组。这些被删除的三元组被分为训练和测试样本。对于链路预测任务，将测试三元组{(h, r, t)}中的每个h视为一个查询。一组候选目标实体使用不同的方法进行排序。对于事实预测，真实测试三元组与一些生成的假三元组进行排序。

定量评估

链路预测

对于大多数关系，因为嵌入方法不能使用知识图谱中的路径信息，所以他们通常表现的不如RL或者PRA方法， 当实体之间没有足够的路径时，我们的模型和PRA可能会给出较差的结果。

事实预测

直接对特定关系的所有正样本和负样本进行排序。

定性评估

agent发现的一些推理路径：

说明效率奖励函数的效果，我们在图2中展示了路径长度分布：

表4显示了关于推理路径数量的一些比较。我们可以看到，通过预定义的奖励功能，RL agent能够挑选出较强的奖励，并过滤掉相似或不相关的奖励。

监督学习的效果

将RL应用于KG推理的一个主要挑战是较大的动作空间。我们通过在奖励再培训步骤（reward retraining step）之前应用监督学习来解决这个问题。为了展示监督训练的效果，我们评估了不同训练集数下agent在10步内达到目标的成功率(succ~10~)。对于每个训练集，使用训练集中的一对实体(e~source~, e~target~)来查找路径。所有连接实体的正确路径将获得+1全局奖励。然后我们插入一些真正的训练路径。succ~10~是在包含100个实体对的测试集上计算的。对于NELL995数据集，因为我们有200个惟一的关系，所以在添加反向操作后，操作空间的维数将为400。这意味着随机漫步的成功率非常低，因为可能有近400^10^个无效路径。图3显示了在训练过程中的succ~10~。我们看到，即使代理以前没有见过实体，它实际上也可以选择有希望的关系来扩展它的路径。这也验证了我们的状态表示的有效性。

四、结论与未来工作

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