DeepPath:一种用于知识图推理的强化学习方法

https://arxiv.org/pdf/1707.06690.pdf

https://github.com/xwhan/DeepPath

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

1介绍

用于语音识别中声学建模的深度神经网络近年来,深度学习技术已经在各种分类和识别问题中获得了许多现成的结果(Krizhevsky et al。,2012; Hinton et al。,2012; Kim,2014)。然而,复杂的自然语言处理问题通常需要多个相互关联的决策,并且赋予深度学习模型以学习理性的能力仍然是一个具有挑战性的问题。为了处理没有明显答案的复杂查询,智能机器必须能够推理现有资源,并学会推断未知答案。

更具体地说,我们把我们的研究放在多跳推理的环境中,给出一个大的KG,这是学习显式推理公式的任务。例如,如果KG包含诸如Neymar为巴塞罗那出战的信念,而巴塞罗那在西甲联赛中,那么机器应该能够学习以下公式:playerPlaysForTeam(P,T)∧teamPlaysInLeague(T,L)⇒ playerPlaysInLeague(P,L)。在测试时间内,通过插入学习公式,系统应该能够自动推断一对实体之间的缺失链接。这种推理机可能会成为复杂QA系统的重要组成部分

近年来,路径排序算法(PRA)(Lao et al。,2010,2011a)成为大型幼儿园学习推理路径的一种有前途的方法。PRA使用基于重启的基于推理机制的随机游走来执行多个有界深度优先搜索过程来查找关系路径。加上基于弹性网络的学习,PRA然后使用监督式学习选择更合理的路径。然而,PRA在完全独立的空间中运作,这使得评估和比较KG中类似的实体和关系变得困难。

 

 

在这项工作中,我们提出了一种可控多跳推理的新方法:我们将路径学习过程构建为强化学习(RL)。与PRA相反,我们使用基于翻译的基于知识的嵌入方法(Bordes et al。,2013)来编码我们的RL agent的连续状态,这是导致知识图的向量空间环境的原因。代理通过对关系进行抽样来扩展其路径,从而采取增量步骤。为了更好地指导RL代理学习关系路径,我们使用政策梯度训练(Mnih et al。,2015)和新的奖励函数,共同提高准确性,多样性和效率。从经验上讲,我们证明了我们的方法优于PRA和基于嵌入的数据集,这两种方法在Freebase和Never-Ending Language Learning(Carlson et al。,2010a)数据集上都是基于arXiv:1707.06690v2 [cs.CL] 2018年1月8日。

•我们首先考虑用于学习知识图中关系路径的强化学习(RL)方法;

•我们的学习方法使用复杂的奖励功能,同时考虑准确性,效率和路径多样性,在寻路过程中提供更好的控制和更大的灵活性;

•我们表明,我们的方法可以扩展到大规模的知识图,在两项任务中胜过PRA和KG嵌入方法。

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

2相关工作

路径排序算法(PRA)方法(Lao et al。,2011b)是一种主要的路径寻找方法,它使用随机行走和重启策略进行多跳推理。加德纳等人。(2013; 2014)提出对PRA进行修改,计算向量空间中的特征相似度。Wang和Cohen(2015)介绍了一种用于集成背景KG和文本的递归随机游走方法 – 该方法同时执行逻辑程序的结构学习和来自文本的信息提取。随机行走推断的一个潜在瓶颈是连接到大量公式的超级节点将产生巨大的扇出区域,这会显着减慢推断并影响精度。

Toutanova等人 (2015)为多跳推理提供了卷积神经网络解决方案。他们基于词法化的依赖路径构建了一个CNN模型,该路径受到由于分析错误而导致的错误传播问题的困扰。Guu等人 (2015)使用KG嵌入来回答路径查询。Zeng等人 (2014)描述了用于关系抽取的CNN模型,但它没有明确地建模关系路径。Neelakantan等人。(2015)提出了一种用于在知识库完成(KBC)中建模关系路径的递归神经网络模型,但它训练了太多独立的模型,因此它不能进行缩放。请注意,许多最近的KG推理方法(Neelakantan等,2015; Das等,2017)仍然依赖于首先学习PRA路径,它只在离散空间中运行。与PRA相比,我们的方法原因在于持续的空间,

神经象征机器(Liang et al。,2016)是关于KG推理的最新工作,它也适用于强化学习,但与我们的工作有不同的味道。NSM学习编写可以找到自然语言问题答案的程序,而我们的RL模型试图通过推理现有的KG三元组来增加新的事实到知识图(KG)。为了获得答案,NSM学习生成一系列可组合为可执行程序的动作。NSM中的动作空间是一组预定义的令牌。在我们的框架中,目标是找到推理路径,因此行动空间就是KG中的关系空间。类似的框架(约翰逊等人,2017)也被应用于视觉推理任务。

3方法论

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

3.1关系推理的强化学习

RL系统由两部分组成(见图1)。第一部分是外部环境E,它规定了代理和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模型的概述。左图:由MDP建模的KG环境E。虚线箭头(部分)显示KG中的现有关系链接,粗体箭头显示RL代理发现的推理路径。-1表示关系的倒数。右图:策略网络代理的结构。在每个步骤中,通过与环境交互,代理学习选择关系链接来扩展推理路径。

 

系统的第二部分RL代理被表示为将状态向量映射到随机策略的策略网络πθ(s,a)= p(a | s;θ)。神经网络参数θ使用随机梯度下降来更新。与Deep Q Network(DQN)相比(Mnih et al。,2013),基于策略的RL方法更适合我们的知识图情景。原因之一是,对于KG中的路径寻找问题,由于关系图的复杂性,动作空间可能非常大。这可能会导致DQN收敛性较差。此外,政策网络不是学习像DQN这样的基于价值的方法中常见的贪婪政策,而是能够学习防止代理人被卡在中间状态的随机政策。在我们描述我们政策网络的结构之前,

操作给定实体对(es,et)与关系r,我们希望代理找到链接这些实体对的最有信息的路径。

从源实体开始,代理使用策略网络来选择最有希望的关系,以在每个步骤中扩展其路径,直到它到达目标实体等。为了保持策略网络的输出维度一致,动作空间被定义为KG中的所有关系。

国家KG中的实体和关系是自然离散的原子符号。由于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代理,代理可以成功发现关系语义。

奖励有一些因素会影响RL代理发现的路径的质量。为了鼓励代理人找到预测路径,我们的奖励功能包括以下评分标准:

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

如果经过一系列操作后代理达到目标,代理将获得线下积极报酬+1。路径效率:对于关系推理任务,我们观察到短路径往往比长路径提供更可靠的推理证据。较短的关系链也可以通过限制RL与环境的相互作用的长度来提高推理的效率。效率奖励定义如下:

其中路径p被定义为一系列关系r1→r2→…→rn。

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

当前路径和现有路径之间:

其中ri表示关系链r1→r2→…→rn的路径嵌入。策略网络我们使用完全连接的神经网络来参数化策略函数π(s;θ),它将状态向量s映射到所有可能行为的概率分布。神经网络由两个隐藏层组成,每层隐藏一个整流器非线性层(ReLU)。输出层使用softmax函数进行标准化(参见图1)。

3.2培训管道

在实践中,KG推理的一大挑战是关系集可能相当大。对于典型的公司来说,RL代理人通常面临数百(数千)个可能的行为。换句话说,策略网络的输出层往往具有较大的维度。由于关系图的复杂性和较大的动作空间,如果直接通过反复试验法对RL模型进行训练,这对于RL算法来说是典型的,RL模型将表现出很差的收敛性。经过长时间的培训,代理商无法找到有价值的途径。为了解决这个问题,我们开始了一项监督政策的培训,这个政策受到了AlphaGo使用的模仿学习渠道的启发(Silver等,2016)。在Go游戏中,玩家在每一步都面临着将近250次可能的法律行动。直接培训代理人从原始行动空间挑选行动可能是一项艰巨的任务。AlphaGo首先使用专家动作培训受监管的政策网络。在我们的案例中,受监管的政策是通过随机广度优先搜索(BFS)进行培训的。

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

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

其中rt属于路径p。然而,香草BFS是偏向于短路径的偏向搜索算法。当插入这些偏置路径时,代理变得难以找到可能有用的更长路径。我们希望路径只能通过定义的奖励函数来控制。为了防止偏见的搜索,我们采用一个简单的技巧来向BFS添加一些随机机制。我们不是直接搜索esource和etarget之间的路径,而是随机选择一个中间节点einter,然后在(esource,einter)和(einter,etarget)之间执行两个BFS。连接的路径用于训练代理。监督式学习可以帮助代理人从失败的行为中学习更多的经验。凭借学到的经验,我们然后训练经纪人寻找理想的路径。

奖励再培训为了找到由奖励功能控制的推理路径,我们使用奖励功能来重新培训受监管的政策网络。对于每个关系,具有一个实体对的推理被视为一个情节。从源节点esource开始,代理根据随机策略π(a | s)选择一个关系,以扩展其推理路径,该关系是所有关系的概率分布。这种关系链接可能会导致一个新的实体,或者它可能导致什么都没有。这些失败的步骤会导致代理商收到负面报酬。在这些失败的步骤之后,代理将保持在相同的状态。由于代理人遵循随机策略,因此代理人不会因重复错误的步骤而停滞不前。为了提高训练效率,我们用一个上限最大长度来限制插曲长度。如果代理未能在最大长度步骤内到达目标实体,则该事件结束。每集之后,使用以下渐变更新策略网络:

其中Rtotal是定义的奖励函数的线性组合。再训练过程的细节显示在算法1中。实际上,使用具有L2正则化的Adam Optimizer(Kingma和Ba,2014)更新θ。

3.3双向路径限制搜索

给定实体对,RL代理学习的推理路径可以用作逻辑公式来预测关系链接。每个公式都使用双向搜索进行验证。在典型的KG中,一个实体节点可以链接到具有相同关系链接的大量邻居。一个简单的例子是关系personNationality-1,它表示了personNational的逆。在此链接之后,实体美国可以到达众多邻近实体。如果公式包含这样的链接,那么随着推理公式的增加,中间实体的数量可以呈指数增长。但是,我们观察到对于这些公式,如果我们从反方向验证公式。中间节点的数量可以大大减少。算法2显示了对所提出的双向搜索的详细描述。

4个实验

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

4.1数据集和设置

表1显示了我们进行实验的两个数据集的统计数据。它们都是较大数据集的子集。FB15K-237中的三元组(Toutanova等,2015)是从FB15K(Bordes等,2013)中抽取的,删除了冗余关系。我们对20条有足够推理路径的关系进行推理任务。这些任务包括来自体育,人物,地点,电影等不同领域的关系。此外,我们提出了一个新的NELL子集,适用于NELL系统第995次迭代的多跳推理。我们首先删除具有关系概括或haswikipediaurl的三元组。这两个关系在NELL数据集中出现超过2M倍,但它们没有推理值。在这一步之后,我们只选择具有Top-200关系的三元组。为了便于寻找路径,我们还添加了反三元组。对于每个三元组(h,r,t),我们追加(t,r-1,h)到数据集。用这些反三元组

表1:数据集的统计。#Ent。表示唯一实体的数量,#R表示关系的数量

对于每个推理任务ri,我们从KG中删除ri或r -1的所有三元组。这些被移除的三元组被分割成火车和测试样本。对于链接预测任务,测试三元组{h,r,t}}中的每个h被视为一个查询。一组候选目标实体使用不同的方法进行排序。对于事实预测,真正的测试三元组用一些生成的假三元组进行排名。

4.2基线和实施细节

大多数KG推理方法都基于路径公式或KG嵌入。我们在我们的实验中探索了这两个类的方法。对于基于路径的方法,我们将我们的RL模型与PRA(Lao et al。,2011a)算法进行了比较,该算法已用于几种推理方法(Gardner et al。,2013; Neelakantan et al。,2015)。PRA是一种使用随机游走(RW)来查找路径并获取路径特征的数据驱动算法。对于基于嵌入的方法,我们评估了一些为知识库完成而设计的最新嵌入,如TransE(Bordes等,2013),TransH(Wang等,2014),TransR(Lin等, ,2015)和TransD(Ji等,2015)。

表2:两个数据集上的链接预测结果(MAP)

 

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

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

4.3结果

4.3.1定量结果

链接预测此任务是对给定查询实体的目标实体进行排名。表2显示了两个数据集的平均精度(MAP)结果。

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

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

由于基于路径的方法通常比为此任务嵌入方法效果更好,因此我们不在此表中包含其他两个嵌入基线。相反,我们腾出空间来展示每个关系推理任务的详细结果。

对于表中最后一行所示的总体MAP,我们的方法明显优于基于路径的方法和两种数据集上的嵌入方法,这验证了我们RL模型的强推理能力。对于大多数关系来说,由于嵌入方法不能使用KG中的路径信息,它们通常比我们的RL模型或PRA表现得更差。但是,当实体之间路径不足时,我们的模型和PRA可能会导致较差的结果。例如,对于filmWrittenBy关系,我们的RL模型只能找到4条独特的推理路径,这意味着KG中实际上没有足够的推理证据。另一个观察结果是,我们总是在NELL数据集上获得更好的性能。透过分析幼稚园的路径,

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

图3:培训期间的成功率(succ10)。任务:运动员竞技队。

事实预测该任务不是对目标实体进行排名,而是直接对特定关系的所有正面和负面样本进行排名。由于PRA代码仅为每个查询节点提供目标实体排名,而不是所有三元组的排名,因此PRA不作为基准列入此处。表3显示了所有方法的总体结果。我们的RL模型在这项任务中获得更好的结果。我们还观察到RL模型击败了大多数推理任务的所有嵌入基线。

4.3.2推理路径的定性分析

为了分析推理路径的属性,我们在表5中显示了代理发现的一些推理路径。为了说明效率奖励函数的效果,我们在图2中显示路径长度分布。为了解释这些路径,例如,人的民族关系,第一个推理路径表明,如果我们知道事实placeOfBirth(x,y)和locationContains(z,y),那么很有可能人x具有国籍z。这些简短而有预见性的路径表明了RL模型的有效性。另一个重要的观察结果是,我们的模型使用比PRA更少的推理路径,这表明我们的模型实际上可以从KG中提取最可靠的推理证据。表4显示了一些关于推理路径数量的比较。我们可以看到,利用预定义的奖励功能,

4.3.3监督学习的效果

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

表5:我们的RL模型找到的示例推理路径。前三种关系来自FB15K-237数据集。该
人是从NELL-995。现有关系的倒数用-1表示

5结论和未来工作在本文中,我们提出了一个强化学习框架来提高幼儿园关系推理的性能。具体而言,我们培训RL代理以在知识库中查找推理路径。与以前的基于随机行走的路径寻找模型不同,RL模型允许我们控制找到的路径的属性。在许多基于路径的推理方法中,这些有效路径也可以用作PRA的替代方案。对于两个标准推理任务,使用RL路径作为推理公式,我们的方法通常优于两类基线。

对于未来的研究,我们计划研究纳入敌对学习的可能性(Goodfellow等,2014),以提供比本文使用的人类定义的奖励功能更好的奖励。根据路径特征设计奖励,而不是根据路径特征来设计奖励,而是通过训练有差别的模型来给予奖励。此外,为了解决KG在没有足够推理路径时出现问题的情况,我们有兴趣将我们的RL框架用于与KG三元组和文本提及的联合推理。

致谢

我们非常感谢NVIDIA公司在此次研究中捐赠的一颗Titan X Pascal GPU的支持。

Leave a Reply

Your email address will not be published. Required fields are marked *