融合TuckER嵌入和强化学习的知识推理①

于铁忠, 罗 婧, 王利琴,3,4, 董永峰,3,4

1(河北工业大学 人工智能与数据科学学院, 天津 300401)

2(石家庄学院 计算机科学与工程学院, 石家庄 050035)

3(河北省大数据计算重点实验室, 天津 300401)

4(河北省数据驱动工业智能工程研究中心, 天津 300401)

1 引言

知识图谱(knowledge graph, KG)[1]本质上是一种概念网络, 其基本组成单位是形式为(实体, 关系, 实体)的三元组, 目前已经构建了许多知识图谱, 如WordNet[2]、NELL[3]、Freebase[4]等, 并成功应用于信息检索、推荐系统、问答系统等智能服务领域. 因为构建的大规模知识图谱通常是不完备的, 需要不断对其进行补充, 而知识推理[5,6]是从现有的数据中推理出新的实体或关系, 从而不断完善知识图谱, 因此知识推理近年来成为知识图谱研究领域的热点问题之一.

使用张量因子分解或神经网络学习实体和关系的嵌入是目前较为流行的知识推理方法[7-9], 它们将知识图谱中的实体和关系表示成低维稠密向量, 然后利用向量的相似性推理出实体之间的关系或者判定给定的三元组是否为真, 从而补全知识图谱. 这些方法效率较高, 但是依赖于知识图谱的三元组表示形式, 大多数都没有捕捉到多跳路径的关系, 从而限制了其在更复杂的推理任务中的应用. 因此, 结合实体对之间的多跳路径信息成为知识推理的另一种解决方案. 路径排序算法(path ranking algorithm, PRA)[10]使用基于重启推理机制的随机游走来执行多个有界深度优先搜索, 通过监督学习选择更合理的路径, 在一定程度上解决了上述问题. 由于具有可解释性和良好的性能, 最近的工作将多跳推理表述为马尔可夫决策过程(Marcov decision process, MDP)[11], 并利用强化学习(reinforcement learning, RL)[12,13]执行有效路径搜索. 其中DeepPath[14]是第一个将强化学习迁移到知识图谱中的多跳推理方法, 该方法将实体对应强化学习中的状态, 关系对应动作, 旨在使用RL对关系进行采样来扩展路径, 这类方法的提出为知识图谱的推理提供了新的研究思路.

然而在实际知识推理任务当中, 使用强化学习来进行路径搜索的效率并不高, 一方面, 多数强化学习方法在构建知识图谱环境时没有对实体和关系进行较好的嵌入, 从而导致智能体的路径搜索成功率偏低; 另一方面, 知识图谱中存在大量无效路径, 比如对于三元组(人物A, 出生于, 北京)、(北京, 位于, 中国)、(人物A,结婚, 人物B)而言, 可以推出(人物B, 出生于, 中国).在推理过程中, 关系“结婚”是实体, “北京”和“中国”的无效动作, 因为实体“北京”和“中国”不能作为“结婚”的主语或者宾语. 当智能体在游走的过程中选择了某无效动作时, 会停止并退回上一步重新进行选择, 然而智能体可能会不断选择该无效动作; 当选择有效路径时,也会存在同一条路径重复被选择的情况, 均会造成游走死循环. 上述情况都有可能导致智能体在游走初始阶段难以获得策略网络给予的奖励, 使得路径选择的准确率降低.

针对以上提出的在进行知识推理时路径选择效率和准确率偏低的问题, 本文实现了表示学习和强化学习的融合, 提出一种融合TuckER嵌入和强化学习的知识图谱推理方法TuckRL (TuckER reinforcement learning, TuckRL), 将路径选择问题转化为序列决策问题. 通过使用TuckER嵌入得到知识图谱中实体和关系的向量表示, 使智能体在与知识图谱环境的交互中能够更精准的搜索路径, 提高了推理方法的效率; 为了减少无效动作对智能体的干扰, 并鼓励策略网络选择不同的关系, 通过对动作执行随机丢弃操作, 使智能体得到更全面的训练, 提高了模型的泛化能力; 使用长短期记忆网络(long short-term memory, LSTM) 存储智能体历史动作, 在关系选择时强制智能体选择其他动作来避免在同一实体节点上不断停顿, 使其在训练过程中尽可能为推理任务找到成功率较高的路径.

2 相关工作

目前面向知识图谱的知识推理方法可分为以下3类: 基于嵌入的方法、基于关系路径的方法以及基于强化学习的方法, 本节将按照此分类对知识推理方法的国内外研究工作进行概述.

基于嵌入的推理是将实体和关系映射到向量空间中, 通过计算得到的向量相似度完成推理. 其中最经典的模型是Bordes等[8]于2013年提出来的TransE, 该模型将关系视为实体对之间的某种翻译, 在处理简单关系时表现良好, 但在面对1-N、N-1、N-N等复杂关系时会存在错误; Wang等[15]提出的TransH通过设置一个关系超平面, 使不同关系下的实体有不同的表示,解决了TransE在处理复杂关系时的局限性. Ji等[16]提出的TransD同时考虑实体和关系的多样性, 通过设置两个投影矩阵分别将头尾实体投影到关系空间, 模型更加灵活; 陈文杰等[17]提出的TransGraph模型学习三元组信息的同时, 还考虑到知识图谱的网络结构特征和语义信息, 从而增强三元组的表示效果; Trouillon等[18]提出的ComplEx将实体和关系嵌入到复数向量空间中, 以推理对称和反对称关系; Balažević等[19]提出的TuckER将知识图谱表示成三阶二元张量, 每个元素对应一个三元组, 具有较强的学习特征能力.

基于关系路径的推理方法侧重于捕捉KG中路径上的信息, 也就是说, 此类方法不仅可以预测实体之间的直接关系, 还考虑其多跳关系的丰富语义. 早期的研究路径排序算法PRA通过在KG上随机游走得到实体对之间的所有路径, 并利用二分类器推理缺失的关系. Lin等[20]提出的PTransE通过组合每条路径中的所有关系得到路径的嵌入, 并设计了路径约束资源分配算法(path-constraint resource allocation, PCRA)衡量关系路径的可靠性. Das等[21]提出Path-RNN (pathrecurrent neural network, Path-RNN)神经网络模型, 将每条路径分解为关系序列, 通过RNN组合关系路径的语义信息, 构造出路径的向量表示. Wang等[22]提出知识感知的路径循环网络(knowledge-aware path recurrent network, KPRN)模型, 在嵌入实体和向量之后,LSTM通过组合实体和关系的语义生成路径表示, 利用路径中的序列依赖项进行关系补全.

基于强化学习的推理方法将实体之间的路径游走视为马尔可夫决策过程, 使用基于策略的智能体搜索推理路径. Xiong等[14]提出第一个考虑在知识图谱中学习路径的强化学习方法DeepPath; Das等[23]提出的MINERVA是使用强化学习训练用于多跳KG查询应答的端到端模型; Shen等[24]提出的M-Walk是一个由RNN和蒙特卡洛树组成的智能体, 用来编码路径状态以及生成有效路径. Li等[25]提出的DIVINE是一种基于生成对抗学习的框架, 通过学习推理策略和奖励函数来增强知识图谱中基于RL的推理. Meilicke等[26]提出基于规则的多跳推理模型, 引入强化学习指导规则采样过程, 有助于获取更有价值的规则. Lei等[27]提出的RuleGuider利用基于符号方法生成的高质量规则为智能体提供奖励监督. 崔员宁等[28]提出的TransPath通过在目标任务之外增加单步游走选择有效动作的源任务来提高路径选择的成功率.

从以上研究可以发现, 很少有将嵌入模型和强化学习相结合的方法, 且在使用强化学习进行推理的过程中, 没有充分利用智能体的历史路径信息. 因此, 本文提出采用TuckRL方法解决此类问题, 首先将实体和关系进行低维嵌入, 完成知识图谱环境的创建; 然后在强化学习的框架中, 为减少无效动作对推理结果的干扰, 通过随机丢弃智能体的输出边进行动作修剪, 并引入LSTM网络作为记忆组件存储历史路径, 以提高路径选择的效率.

3 融合TuckER嵌入和强化学习的知识推理

知识推理的具体任务是在实体对之间找到可靠的预测路径, 所以为了提高路径搜索的效率和质量, 本文提出了一种融合TuckER嵌入和强化学习的知识推理方法TuckRL, 将寻找实体对之间可能存在的关系以及路径信息转化为强化学习的序列决策问题. 模型如图1所示, 分为3部分.

图1 融合TuckER嵌入和强化学习的知识推理模型框架图

其中, 第1部分为知识图谱环境模块: 使用TuckER嵌入将实体和关系映射成含有三元组语义信息的向量;第2部分为强化学习环境模块: 将TuckER嵌入得到的实体和关系的连续向量化表示作为基于强化学习的神经网络的输入, 使得模型能够充分利用知识图谱已经存在的三元组信息, 且RL智能体在游走的过程中进行策略网络的训练, 使用动作修剪和LSTM网络来控制关系选择和路径搜索, 帮助智能体选择有效动作, 以便提高模型的性能; 第3部分为策略引导的路径推理模块: 智能体与知识图谱环境进行交互, 在知识推理阶段采用训练好的策略, 完成推理任务.

3.1 TuckER嵌入

知识图谱嵌入是KG建模的方法, 通过学习评分函数 f(eH,eT)来定义空间中的三元组, 使得语义相近的实体在嵌入空间中的向量表示距离也相近. TuckER具备完全表达能力, 即通过训练学习, 能够将正三元组和负三元组完全区分开, 且性能较优于当前的线性嵌入模型. 图2为TuckER嵌入模型的可视化表示.

图2 TuckER嵌入模型图

在该嵌入模型中, 知识图谱被表示为一个三阶二元张量, 而TuckER分解的核心思想是将该三阶张量分解为1个核心张量和3个矩阵, 每一个元素表示一条事实三元组, 值为1表示真实三元组, 为0表示错误或缺失事实. 定义一个原始张量X ∈RI×J×K, 通过TuckER可以分解为核心张量Z ∈RP×Q×R和 3个矩阵A∈RI×P、B∈RJ×Q、C∈RK×R, 如式(1)所示:

其中, ×n表示沿第n阶模的张量积, 3个矩阵每一行分别为头实体eH、关系r 和尾实体eT的向量表示, 而核心张量 Z 表征了它们之间的交互级别. 头实体和尾实体是等价的, 均用实体嵌入矩阵 E 来表示, 即E=A=C∈Rne×de ,且关系矩阵嵌入为R =B∈Rnr×dr, 其中ne和nr表示实体和关系的数量, de和dr表示实体和关系嵌入向量的维数.

综上, 定义出TuckER的得分函数如式(2)所示:

其中,W∈Rde×dr×de为 核心张量, 即模型参数;wr∈Rdr为R的关系表示.

3.2 强化学习

TuckRL模型是将知识图谱推理问题转化为马尔科夫决策问题, 智能体的状态转移和动作选择都在知识图谱环境中完成, 故本节介绍将知识图谱G 建模为强化学习智能体决策环境的过程.

该过程主要由< S, A , γ, P ＞四部分构成, 其中S表示智能体的连续状态空间, A={a1, a2, …, an}是动作空间, 表示所有可用动作的集合, γ(s, a)为奖励函数, P是状态转移策略.

(1) 状态空间

知识图谱中的实体集合E作为智能体的状态S,将智能体在每个时间步骤的状态表示成 st∈S , 且et表示第t步访问的实体. 为了更好地表达其语义内涵, 采用TuckER嵌入将实体表示成低维稠密向量.

(2) 动作空间

动作空间A被定义为KG中的关系集合R, At表示状态 st所对应的实体et在KG中所有可能的输出边, 智能体要选择一个边进行路径搜索, 游走步数T作为路径搜索的终止条件. 动作集合表示如下:

其中, r′、 e′分别表示下一步有可能选择的关系和实体.

(3) 状态转移

状态转移是指智能体根据当前状态做出动作移动到下一个状态的过程. 具体来说, 智能体在当前状态下,通过选择某动作后, 并基于环境的交互实现从当前状态到下一状态的转移. 状态转移P表示如下:

(4) 奖励函数

当智能体从初始状态开始搜索, 最终能够到达目标状态, 则获得正向奖励1, 否则无奖励. 智能体会根据奖励及时更新自己的策略, 尽可能实现奖励最大化, 奖励函数定义如下:

其中, rq表 示查询到的关系, eT表示最终的尾实体.

3.3 基于MDP的策略网络

基于MDP的策略网络是TuckRL的关键部分, 主要用于引导智能体在知识图谱和强化学习的交互环境中进行游走, 做出高效且准确的决策. 在该策略网络中,首先使用Dropout动作修剪, 目的是减少无效动作对于智能体游走的干扰, 提高动作的选择效率, 然后引入长短期记忆网络LSTM作为记忆组件, 避免智能体在同一实体节点上不断停滞的同时, 编码完整的路径游走历史轨迹, 并采用策略梯度下降算法更新策略网络的参数, 以便在推理过程中引导智能体走向更可靠的路径.

(1) 动作修剪

由于无效路径通常比正确路径多, 且更容易被发现, 从而增加了路径搜索的负担, 尤其是当KG随着路径跳数的增长, 动作空间也会呈指数型增加, 从而加大搜索负担, 对于出度较大的实体(即与之相连的关系较多), 这种现象会更严重. 而枚举出来实体对之间所有可能的关系路径在大型知识图谱上是不可行的, 因此如何进行有效的路径探索, 找出推理路径格外重要.

针对这类问题, TuckRL借鉴深度神经网络中Dropout丢弃神经元来缓解过拟合的思想, 提出了一种新的训练机制: 将随机丢弃思想用到强化学习的路径选择中, 按照一定的概率屏蔽当前实体的输出边, 从而实现动作的修剪. 在智能体采样路径的时候, 随机屏蔽当前状态的一些输出边, 智能体根据修剪后的关系分布来采样动作. 这样不仅可以减少智能体的搜索空间,防止GPU内存溢出, 同时还能进一步扩大对于不同路径集的有效探索, 提高路径选择的随机性.

(2) LSTM编码路径

KG中的每一个实体和关系都通过TuckER嵌入分别得到具有语义信息的低维稠密向量e ∈E, r ∈R, 为保存搜索历史路径, 利用3层LSTM记忆和编码智能体的历史动作. 假设初始状态为 h0=0 , 搜索历史ht=(eH,r1,e1,···,rt,eT)由从第1步到第t步所采取的动作序列构成.

其中, r0表 示初始关系, eH为初始实体.

(3) 策略神经网络优化

在知识推理中, 基于策略网络的强化学习将输入状态 st映射到所有可能被选择的动作的概率向量中, 本文将组合得到的状态向量输入到由两个隐藏层组成的神经网络中, 且每个隐藏层后面会有一个ReLU层, 输出层使用Softmax进行归一化. 策略网络π定义如下:

其中, θ为神经网络参数, 动作空间At为所有动作嵌入的集合, W为隐藏层的权重.

对于上述策略网络πθ, 模型使用REINFORCE梯度策略方法来优化参数θ, 如式(10)所示:

其中, J (θ) 表示一个批次的奖励, E 表示训练集上不同三元组对应的期望值.

REINFORCE梯度策略方法使用当前的策略生成的一系列历史轨迹(迭代遍历所有在 G 中的三元组)来估计随机梯度, 然后用随机梯度来更新参数, 如式(11)和式(12)所示:

其中, θ为需要更新的参数, eH表示头实体, rt表示当前关系, πθ(at|st)为 在 st状 态下策略网络选择at的概率. γ为执行该动作所获得的奖励值, β为学习率.

3.4 模型训练

在进行知识推理之前, 对RL智能体进行策略网络的训练, 目的是让智能体在路径游走的过程中尽可能地直接选择正确的动作, 从而更高效的完成多步关系推理. 在训练中, 首先输入知识图谱训练集Train、限制游走长度的最大步数T, 然后是智能体和图谱环境之间的迭代: 根据策略网络的输出结果, 选择一个关系r作为下一步的执行动作, 此时判断起始状态 s0和目前选择的关系r组成的三元组是否在知识图谱 G 中, 若是, 给予奖励并更新策略网络, 具体训练过程如算法1.

算法1. 策略网络训练算法G输入: 知识图谱 , 训练集Train, 最大步数大小T πθ输出: 策略网络 的参数θ 1) for episode 1 to N do 2) initial st = s0, h0 = 0, step = 0 3) while step < T do 5) st=TuckER(et), at=TuckER(rt)πθ(at|st)6) Update ht = LSTM(ht-1, at-1) //根据策略 执行动作a, 得到奖励Reward和状态St+1 7) if Reward = 0 8) step++9) if Reward = 1 or step = T 10) break 11) end while g∝∇θT∑t=1 Reward(st|es,r)logπθ(at|st)12) //更新策略网络13) end for

4 实验分析

4.1 数据集及评价标准

为了评估本文所提方法, 在NELL-995、WN18RR、FB15K-237这3个大规模数据集上进行实验. 其中NELL-995是基于语义机器学习系统NELL的第995次迭代产生的数据集, 包含7.5k个实体、200个关系以及16.9k个三元组, WN18RR的三元组数据来自大型英文语义知识库WordNet, 包含4.0k个实体、11个关系和14.6k个三元组; FB15K-237是包含常见信息的世界知识库FB15K的子集, 通过从验证集和测试集中移除许多关系的逆关系构建, 包含1.4k个实体、237个关系和29.2k个三元组; 数据集的统计信息如表1所示.

表1 数据集的信息

在关系预测任务中, 通常使用平均倒数排名(mean reciprocal rank, MRR)和推理结果命中率Hits@N作为评估指标. 对于三元组中缺失的关系, 模型会对测试集中的实体对(e1, e2), 依据评分函数预测出带有顺序的关系集合r={r1, r2, …, rn}, 正确的关系r在关系集合中排名越靠前, 则说明模型的预测效果越好.

MRR是指正确结果在所有预测结果中排名的倒数平均值, 计算如式(13)所示:

Hits@N表示正确的结果在所有预测结果中排在前n位所占的比例, 计算如式(14)所示:

其中, N是需预测关系的实体对数量; r anki是对需预测的第i个实体对而言正确的关系在所有预测结果中的排序位置. I 为指示函数, 表示当r anki≤n 时 , I =1, 否则I=0.

4.2 参数设置

到的所有实体和关系向量维度设置为100, 这也是策略网络Policy Network的输入大小, 路径编码器LSTM的隐藏层维度设置为100. 选择Adam作为优化器, 学习率 β分别设置为{0.001, 0.002, 0.003}, 对于整个训练过程, Dropout分别为{0, 0.1, 0.2, 0.3, 0.4}, 迭代次数num_epoches和批大小batch_size分别为20和128.

实验使用与RuleGuider[27]相同的训练集、验证集和测试集. 对于每个实体, 将实体的最大输出边数设置为阈值η, 以防止GPU内存溢出, 并保留其具有最高PageRank分数的前n个邻居. 将TuckER模型嵌入得

4.3 实验结果与分析

为了验证所提方法的性能, 与嵌入模型TransE、DistMult、ComplEx和ConVKB[29], 使用强化学习进行推理的模型DeepPath、MINERVA、AnyBURL和RuleGuider进行对比实验, 得出本模型TuckRL优于大部分模型, 实验结果如表2所示, 其他模型的实验结果使用文献[27]给出的结果. 由表2可知, 基于嵌入的模型虽然比较简单, 但是在多个数据集上的整体结果是不错的, 原因可能是基于嵌入的方法可以将KG中的每个三元组映射到嵌入空间, 从而可以编码整个图谱的连通性; 而TuckRL也正是利用了嵌入模型的这个优点, 也得到了不错的实验结果. 在WN18RR和FB15K-237数据集上比其他方法有较明显提升, 尤其在FB15K-237数据集上, 主要原因可能是FB15K-237实体之间路径长度较长, 在其他模型中动作选择的正确率较低,而TuckRL中使用动作修剪和LSTM编码路径有效避免了选择无效动作. 虽然在大型数据集NELL-995上本文的方法相对于MINERVA没有得到显著改善, 但Hits@1、Hits@3和MRR指标略优于最新模型Rule-Guider和多数嵌入模型.

表2 不同推理方法在不同数据集上的命中率实验结果分析比较 (%)

4.4 Dropout分析

为了考察动作修剪策略对于模型性能的影响, 在FB15K-237引入Dropout={0, 0.1, 0.2, 0.3, 0.4}进行实验, 命中率Hits@N和平均倒数排名MRR的实验结果如图3所示, 可以观察到, Hits@N和MRR一开始随着Dropout的增加而得到提升. 在Dropout=0.3达到最高值, 并之后开始有所下降, 尤其在Hits@10评价指标上最为明显. 分析可知, 一开始Dropout实现了动作修剪,减少了动作空间的大小, 提高了路径选择的正确性和效率, 但是随着Dropout的增加, 有一些有效动作也会伴随着大量的舍弃, 从而导致结果的降低.

图3 在FB15K-237数据集上不同Dropout率的实验结果

4.5 消融实验

为了研究本文模型TuckRL中各个组件的重要性,在NELL-995、WN18RR和FB15K-237数据集上通过替换TuckER嵌入方法(-TuckER)、移除Dropout(-Dropout)和移除路径编码器LSTM (-LSTM)进行消融实验的研究, 并将最终的Hits@3和MRR结果与整个模型进行了比较, 实验结果如表3所示. 由表3可知,移除每个组件都会导致模型性能的下降, 每个组件对模型的最终结果都有不同的影响.

表3 消融实验结果

在该消融实验中, 首先将TuckER嵌入替换为ComplEx嵌入, 原始结果在NELL-995、FB15K-237和WN18RR数据集上的Hits@3和MRR分别有不同程度的下降, 由此可见, 一个性能较好的嵌入方法对于知识推理的作用也是较为明显的; 当移除Dropout动作丢弃组件时, 发现对应的结果也均得到了降低, 由此可见, 删除动作丢弃组件会对策略网络中路径的游走有一定的影响; 最后是去掉可以记忆历史路径的LSTM组件, 也就是说, 智能体仅根据当前的实体和策略函数来选择下一步的动作, 并且无法得到历史路径ht, 从实验结果可以观察到记忆组件LSTM对于模型的性能具有重要影响.

5 结论与展望

本文提出了一种基于强化学习的知识图谱推理方法TuckRL, 该方法融合了表示学习和强化学习, 设计出一个全新的路径游走策略, 在强化学习智能体进行关系选择和路径游走的过程中, 引入了Dropout动作修剪机制和LSTM神经网络, 相比之前的强化学习工作, 更有利于智能体在推理过程中更有效的挖掘高质量路径, 从而完成知识图谱推理任务. 实验部分验证了本文模型的性能, 但是基于RL的方法与基于嵌入的方法在个别指标上的差距仍然存在. 在未来的研究中, 将引入注意力机制来对邻居节点分配不同的权重, 从而更好地捕获两个实体之间每条路径的语义相关性, 来得到更好的推理效果.