基于多级关系路径语义组合的关系推理算法

陈 恒,韩雨婷,李冠宇,王京徽

(1.大连海事大学 信息科学技术学院,辽宁 大连 116026; 2.大连外国语大学 软件学院,辽宁 大连 116044)

0 概述

Freebase[1]、Wordnet[2]、DBpedia[3]、YAGO[4]和NELL[5]等知识图谱(Knowledge Graph,KG)在解决人工智能(Artificial Intelligence,AI)任务方面起着重要作用。然而,手动和自动构建的KG远未达到十分完备的状态[6-7],例如,在Freebase中75%的人缺失国籍,71%的人缺失出生地[8]。因此,知识推理(图谱中隐含知识的挖掘)成为知识图谱研究的热点问题。

本文基于知识图谱实体对间路径信息的分析,提出一种基于多级关系路径语义组合的关系推理算法,研究利用路径信息进行关系推理,提高知识图谱补全质量。

1 相关工作

1.1 知识图谱补全方法

在经典的知识图谱补全方法中,文献[9]提出一种PRA算法,该算法利用知识图谱的图结构特征,通过随机游走的方式计算实体间关系存在的概率进行关系推理,但PRA在实体空间中进行,计算代价高,且扩展性较差。文献[10]提出一种基于翻译的TransE模型,该模型将知识图谱嵌入到低维向量空间,同时认为具有语义相关的实体在空间中的距离也是相近的。因此,通过判断头实体与关系的向量之和是否接近于尾实体向量来对实体间的关系进行推理和判断,进而补全知识图谱,取得了较好的效果。虽然TransE模型精确性高、扩展性好,但仅限于实体间的直接关系,对多级路径关系这种隐藏知识的推理表现不足。文献[11]提出一种基于强化学习的推理方法,利用Agent和环境间的交互,在奖励函数机制下,学习获得两个实体间的路径,通过符号逻辑进行关系推理,但该方法并未考虑路径上的实体和关系的特征。文献[12]提出一种组合向量空间模型,将路径上的关系组合进而推理实体对间的关系,忽略了路径上的实体信息。文献[13]提出一种基于循环神经网络(Recurrent Neural Network,RNN)模型,其通过对关系路径进行建模,充分利用了路径上实体和关系的信息。由于该方法在路径发现过程中依赖于PRA算法,虽然提高了精确性,但计算代价也相对较高。

1.2 知识图谱表示学习

知识表示学习[14-15]的目标是通过机器学习将研究对象的语义信息表示为稠密低维实值向量[16-17],以知识图谱的实体e和关系r为例,将表示学习得到的向量用le和lr来表示,在向量空间中,可以通过欧氏距离或余弦距离等方式,计算任意对象间的语义相似度。表示学习的主要方法有双线性模型RESCAL[18-19]、多层感知机模型MLPs[20]以及TransE[10]、TransH[21]、TransR[22]等翻译模型。通过知识表示得到低维稠密向量,可以更好地用于知识图谱补全工作。

综上所述,本文利用TransE模型将知识图谱中富有语义信息的三元组嵌入到向量空间,从而实现知识图谱的数值化,并受文献[11]的启发,利用强化学习抽取路径关系,以降低计算成本。在文献[13]的基础上,将路径中实体和关系对应的向量作为RNN的输入,经过迭代学习输出多级关系路径语义组合的结果向量。

2 关系推理框架及算法

本文关系推理框架示意图如图1所示。在资源层,以实体关系三元组表示知识图谱;在向量表示层,利用TransE模型将三元组嵌入到低维向量空间;在路径发现层,利用强化学习(Agent与环境交互),发现实体间路径;在关系推理层,将路径中实体和关系对应的向量输入到RNN,经过迭代学习将路径上的语义信息进行组合,输出多级关系路径语义组合的结果向量,并将结果向量与目标向量进行相似度计算,进而进行关系推理。

图1 路径推理框架示意图

2.1 强化学习路径发现算法

本文采用一种新的路径发现算法,即基于强化学习的路径发现算法。该算法的基本思想是:将知识图谱作为环境进行建模,同时设置一个Agent。首先从环境传递给Agent一个初始状态(State),通过Agent的决策得到一个动作(Action)再传递给环境。从初始状态转移到下一个状态,同时获得一个奖励(Reward)。依此循环往复,便可得到一个从初始状态到目标状态的决策序列。Agent的位置随着中间状态的改变而改变,通过以上过程,当Agent移动到目标状态,即尾实体时,就可获得一条从头节点到尾节点的路径。强化学习过程示意图如图2所示。

图2 强化学习过程示意图

2.1.1 环境部分

本文将强化学习的环境部分建模为马尔科夫决策过程(MDP),由四元组(S,A,P,R)组成,其中,S表示连续的状态(State)空间,对应于实体,A表示所有可选择的动作(Action)集合,对应于每个实体所链接关系的集合,R(s,a)表示每对(s,a)的奖励函数,即在某个状态s选择动作a可得到的奖励,P(St+1=s′|St=s,At=a)表示从当前状态St通过动作At转移到下一个状态St+1的概率矩阵,每个状态通过Agent位置的移动来捕捉。

在知识图谱中,可被Agent选择的动作(Action)数量很多,而与所得到的路径中正确的动作相比,不正确动作的数量随着路径长度的增加而增加。因此 如果每走一步都给出相应奖励,则浪费大量的计算成本,为降低计算成本,本文对奖励的设置如式(1)所示:

(1)

当路径到达目标实体时,给出一个+1的奖励;否则给出一个-1的奖励;同时为鼓励Agent发现更多路径,利用余弦函数设置一个多样性奖励函数,计算当前发现的路径和已得到路径之间的相似性,函数设置如下:

(2)

2.1.2 Agent部分

由于关系图的复杂性,使得Action的空间非常大,对于DQN(Deep Q Network)[23]而言,可能导致非常差的收敛性,同时,为了避免Agent陷入一个中间状态,本文将Agent设置为一个决策网路,如式(3)所示:

πθ(s,a)=p(a|s;θ)

(3)

本文用一个全连接的神经网络来参数化策略函数πθ(s;a),该函数能够将状态映射到所有可选动作的概率分布上,神经网络由两个隐藏层组成,每个隐藏层后面都有一个激活函数ReLU,最后的输出层由Softmax函数来进行归一化,采用随机梯度下降法更新神经网络参数θ。为了避免传统强化学习(Reinforcement Learning,RL)算法收敛性较差的问题,本文引入一种监督学习机制,采用BFS(Breadth-First Search)进行路径发现过程中的监督训练。

在强化学习中,所有的目标都被描述为最大化期望累计奖励,即Agent从起点到终点的过程中将奖励累积到最大。Agent的目标是选择一系列动作去最大化未来总的奖励。本文通过蒙特卡罗策略梯度[21]来累计最大化奖励值,如式(4)所示:

(4)

梯度下降法更新参数如下:

(5)

为尽可能找全实体对间路径,本文采用奖励函数来训练受监督的策略网络。一对实体间路径信息的发现称为一个片段,从源节点开始,Agent根据随机策略π(a|s)选择关系,根据选择的关系,源节点可能会链接到一个新实体,或者什么也没有。后者称为失败的步骤,同时Agent还将得到一个负面的奖励。由于Agent遵循随机的策略,它不会因重复错误的步骤而陷入困境,因此在一个失败步骤之后,Agent仍会处在之前同样的状态。为了提高训练效率,本文用上限max-length来限制一个轮次的长度,max-length设置为10,即每一个轮次进行10次动作选择操作。10次选择后不论是否到达目标节点,都结束这个片段。在每个片段结束后,对策略网络进行更新,如式(6)所示:

(6)

其中,Rtotal=rGLOBAL+rDIVERSITY。基于奖励函数训练的路径发现算法如下:

输入给定的实体对

输出实体对间路径

1.对片段1～N做如下循环:

2.初始化向量S0→St

3.初始化片段长度,step→0

4.当num_steps < max_length时,执行:

5.从随机策略π(a|s)中随机取样动作a

6.观察奖励Rt,以及下一个状态St+1

7.如果Rt=-1,则:

8.保存〈St,a〉到Mneg

9.如果到达了目标节点或者num_steps=max_length

10.跳出循环

11.增加步数

12.如果失败则更新参数θ

14.如果成功则:

15.Rtotal←r1rGLOBAL+r2rDIVERSITY

16.更新参数θ

2.2 实体和关系向量组合模型

在利用强化学习获得两个实体间路径信息后,为更好地提高关系推理的精确性,本文将路径上实体和关系的特征考虑在内,如图3所示。

图3 实体对间的路径信息

在图3中,假设实体对(Melinda,Seattle)之间有两条路径,若判断它们之间是否存在关系Live in,由路径信息可以看出通过Bill这条路径得到结果的可靠性比通过路径Marry这条路径的可靠性大,因此考虑路径上实体和关系的特征是有必要的。本文通过建立一种如图4所示的RNN模型,将路径中实体和关系对应的向量作为RNN的输入,经过迭代学习将输出一个关系路径语义组合的结果向量,并将该结果向量与目标关系向量进行相似度计算。相似度值越高,通过该路径得到目标关系的概率越大,进而提高结果的精确性。

图4 RNN模型

本文用(esource,etarget)来表示一个实体对,它们之间的关系用r表示,且(e∈E,r∈R),让π={e0,r0,e1,r1,…,rt-1,et}表示实体对间的路径。由于实体对间可能存在多条路径,本文用S表示它们之间路径集合;len(π)=k,len表示路径的长度,值为k,即路径中实体与关系的个数, 让lei表示第i个实体向量,lri表示第i个关系向量。然后RNN模型对路径π上的实体和关系进行向量组合,在步骤t时刻的输出,如式(7)所示:

ht=f(Whhht-1+Wihlrt+Wehlet)

(7)

路径的最终输出结果向量用lπ表示,目标关系向量用lr表示,它们之间的相似度计算公式,如式(8)所示:

score(π,r)=lπ·lr

(8)

由于实体对间有多条路径相连,需通过式(9)所示的函数找到相似度值最高的路径。

P(r|es,et)=maxσ(score(π,r)),∀π∈S

(9)

图4中每一步需要利用一个实体和关系向量,路径向量是整个路径信息的最终表示,它与查询关系之间的点乘给出置信度得分,即与目标关系向量的相似度得分。

该算法在表示学习已经训练好样本的基础上进行数据处理。在强化学习阶段,通过给定的头结点对图进行遍历的时间复杂度是O(n2);在利用RNN进行路径信息融合阶段,对文本信息处理的时间复杂度是O(n),因此该算法的时间复杂度是O(n2+n),即O(n2)。

由于该算法针对文本中n个向量进行线性计算,因此该算法的空间复杂度是O(n)。

3 实验结果与分析

3.1 实验平台及数据

本文实验平台运行在Window7系统、Quad-Core处理器、4 GB物理内存。实验工具为Pycharm,使用Python3.6作为编程语言编写程序。在知识图谱数据集选择方面,本文选用了FB15K-237[25]和NELL-995[26],它们分别是从FB15K和NELL995中选取的子集。

由于原始数据集数量庞大,对路径发现而言,在每一步每个实体面对可选择的action数量,因存在一些不相关性关系而增加,这些不相关的关系会导致大量不必要的计算,进而影响实验效果。因此,本文选择特定领域关系的数据子集进行实验,同时为降低噪声数据的影响,都在选取时删除冗余及对推理没有任何价值的三元组。本文最终在FB15K-237数据集中选取20种关系任务,在NELL-995中选取12种关系任务进行推理工作。这些任务是来自不同领域,如体育、电影、人物等。为得到更加精确的推理关系,选取最高的相似度值作为路径的推理关系。在进行实验前,将数据集随机地分为8∶2,其中80%作为训练集,剩下的20%作为测试集。实验数据集如表1所示。

表1 实验数据集

3.2 参数设置

在实验中,本文将参数配置如下:学习率λ=0.001,边际值γ=1,维度设置为k=200,采用L2正则化参数优化,并将值设置为0.01,batch大小设置为B∈{64,128,512,1 024}。在RNN模型中,β1=0.9,β2=0.999,实验进行1 000次迭代,测试结果通过测试集上的平均排名来选取。

3.3 度量方法

本文通过在链接预测和事实预测上的MAP(Mean Average Precision)指标来评价实验结果。链接预测指的是对给定查询实体对应的目标实体进行排名。具体表现为在训练中,将一个正例样本,即对一个正确三元组,将其中的尾实体用其他实体替换,从而形成一个负例样本。为保证实验效果的精确性,本文尽量让每个正例样本都对应10个负例样本。最后,通过对这些目标实体的排序,进行正确三元组和错误三元组的划分。事实预测的目标是判断一个三元组(es,r,et)是否成立,即判断头实体es和尾实体et之间是否真的存在关系r。

3.4 实验结果

用RL+RNN表示本文模型,其中在FB15K-237数据集上的链接预测结果如表2所示,在NELL-995数据集上的链接预测结果如表3所示。

表2 不同模型在FB15K-237数据集上的链接预测结果

Table 2 Link prediction results of different models on the FB15K-237 dataset

TasksPRARL+RNNTransETransHteamSp..0.9870.9430.8960.763birthPl..0.4410.5010.4030.405personN0.8470.8410.6410.695filmDir.0.3490.4520.3860.401filmWr..0.6010.4420.5630.567filmLa..0.6630.6680.6420.644tvLang.0.9600.9660.8040.821capital..0.8290.7920.5540.798origani.0.2810.2950.3900.351musici..0.4620.4960.3610.368︙︙︙︙︙overall0.5410.5930.5320.537

表3 不同模型在NELL-995数据集上的链接预测结果

Table 3 Link prediction results of different models on the NELL-995 dataset

TasksPRARL+RNNTransETransHath..P..T0.5470.7320.6720.658ath..P..L0.8410.9610.7730.897ath..H.S0.8590.8870.7180.731ath..P..S0.4740.9310.8760.981team.P.S0.7910.7420.7610.805orgHq.C0.8110.7930.6200.763worksF..0.6810.6890.6770.672bornLo..0.6680.7640.7120.801pers.L.O0.7000.8210.7510.762orgH..P..0.5990.7630.7190.720︙︙︙︙︙overall0.6750.7910.7370.753

从表2和表3可以看出,本文方法在链接预测的实验结果优于PRA、翻译模型TransE与TransH,这说明本文提出的模型具有良好的推理能力。对于大部分关系,由于翻译模型并不能考虑到路径上的信息,预测结果显著低于本文提出的模型或者PRA,但当没有足够的路径信息时,翻译模型还是具有良好的表现能力。同时也说明,本文提出的模型能够较好地利用路径上的信息,并能有效提升知识图谱中信息预测的精确性。

在FB15K-237数据集上的事实预测结果如表4所示,在NELL-995数据集上的事实预测结果如表5所示。

表4 不同模型在FB15K-237数据集上的事实预测结果

Table 4 Fact prediction results of different models on the FB15K-237 dataset

模型MAPPRA0.301TransE0.277TransH0.309RL+RNN0.314

表5 不同模型在NELL-995数据集上的事实预测结果

Table 5 Fact prediction results of different models on the NELL-995 dataset

模型MAPPRA0.387TransE0.383TransH0.389RL+RNN0.417

从表4和表5可以看出,本文提出的方法在事实预测中的结果均优于其他3个模型,同时也表明路径上的实体和关系信息对关系推理具有良好的促进作用,在一定程度上提高了关系推理的质量和效率。

4 结束语

本文提出一种基于多级关系路径语义组合的关系推理算法。该算法利用关系推理,在一定程度上提高了知识图谱补全质量,并将知识图谱嵌入到向量空间,减少了计算开销。下一步研究除考虑知识图谱中已存在的路径信息外,对结构相似性的知识图谱补全问题以及如何处理新引入的知识也将是进一步的研究重点。