论文阅读：通过动态预测 / 完备在稀疏知识图谱上进行多跳推理

Abstract

以前的大多数推理方法都是为实体之间具有足够路径的稠密知识图谱设计的，但是在稀疏知识图谱（KG）上的效果不佳。 一方面，稀疏知识图谱包含的信息较少，这使得模型难以选择正确的路径。 另一方面，缺乏到目标实体的证据途径也使推理过程变得困难。 为了解决这些问题，我们通过应用新颖的动态预测和动态完备策略，提出了一种针对稀疏知识图谱的多跳推理模型 DacKGR：（1）预期策略利用基于嵌入的模型的潜在预测来使我们的模型在稀疏 KG 上执行更多潜在的路径搜索。（2）基于预期信息，完成策略在路径搜索过程中动态添加边作为附加动作，从而进一步减轻了 KG 的稀疏性问题。

Introduction

虽然现存的多跳知识图谱推理已经取得了不错的结果，但在稀疏 KG 上还是面临着两个重要的问题：（1）信息不足。与传统的 KG 相比，稀疏 KG 包含的信息要少很多，这会使得 agent 难以选择正确的搜索方向。（2）路径缺失。在稀疏的 KG 中，某些实体对之间没有足够的路径作为推理证据，这使得 agent 难以执行推理过程。在本文中，我们提出了一个名为 DacKGR 的多跳推理模型，并提出了两种动态策略来解决上述两个问题：

（1）动态预测。动态预测利用稀疏 KG 中的有限信息来预测潜在目标。 与多跳推理模型相比，基于嵌入的模型对于稀疏的 KG 具有鲁棒性，因为它们依赖于 KG 中的每个单个三元组而不是路径。 为此，我们的预测策略将经过预训练的基于嵌入的模型的结果作为预测信息注入到强化学习的状态中。 此信息可以指导代理避免漫无目的地搜索路径。

（2）动态完备。动态完备功能会临时扩展 KG 的一部分，以丰富推理过程中路径扩展的选项。 在稀疏的 KG 中，许多实体只有很少的关系，这限制了 agent 的选择空间。 因此，我们的完备策略会在搜索推理路径期间根据当前实体的状态信息动态添加一些其他关系。 之后，对于当前实体和其他关系 r，我们使用预训练的基于嵌入的模型来预测尾部实体 e。 然后，附加关系 r 和预测的尾部实体 e 将形成潜在动作（r; e），并添加到当前实体的动作空间中以进行路径扩展。

Methodology

3.1 强化学习框架

近年来，KG 的多跳推理已被制定为 KG 之上的马尔可夫决策过程（MDP）：给定三重查询($e_s$;$r_q$;?)，代理需要从头部实体$e_s$，以最大概率连续选择与当前实体相对应的边缘（关系）作为方向，并跳转到下一个实体，直到最大跳数 T。MDP 通常由以下部分组成：

State: 在多跳推理过程中，代理选择的边（关系）不仅取决于查询关系$r_q$和当前实体$e_t$，还取决于先前的历史搜索路径。 因此，可以将第 t 跳的状态定义为$s_t=(r_q,e_t,h_t)$，其中$h_t$是历史路径的表示。 具体来说，我们使用 LSTM 对历史路径信息进行编码，$h_t$是第 t 步 LSTM 的输出。

Action: 对于状态$s_t=(r_q,e_t,h_t)$，如果 KG 中有一个三元组$(e_t,r_n,e_n)$，则$（r_n,e_n）$是状态$s_t$的动作。 状态$s_t$的所有动作组成其动作空间$A_t=\{(r,e)|(e_t,r,e)\in T\}$。 此外，对于每个状态$s_t$，我们还添加一个附加操作$(r_{LOOP},e_t)$，其中$LOOP$是手动添加的自环关系。 它允许代理停留在当前实体，这类似于“停止”操作。

Transition: 如果当前状态为$s_t=(r_q,e_t,h_t)$，并且 agent 选择$(r_n,e_n)\in A_t$作为下一个动作，则当前状态$s_t$将转换为$s_{t+1}=(r_q,e_n,h_{t+1})$。 在本文中，我们将最大跳数限制为 T，状态转移将在$s_T=(r_q,e_T,h_T)$处结束。

Reward: 对于尾实体$e_o$的给定查询$(e_s,r_q,?)$，如果 agent 最终在正确的实体处停止，即$e_T=e_o$，则奖励为 1，否则，奖励为 0 到 1 之间的一个值，其由函数$f(e_s,r_q,e_T)$给出，其中函数$f$由预训练知识图谱嵌入（KGE）模型给出，该模型用于评估三元组$(e_s,r_q,e_T)$的正确性。

3.2 策略网络

本文将第$t$步的动作表示为$a_t=[r;e]$，其中$r$ 和$e$分别表示关系和目标实体的向量。历史信息$h_t$通过 LSTM 来获得，如下所示：

第$t$步的状态可以表示为$s_t=[r_q;e_t;h_t]$，然后将动作空间表示为$A_t\in {\mathbb{R}}^{|A_t|\times 2d}$，其中$d$表示实体或者关系向量的维度。策略网络定义如下：

其中，$\sigma$为 softmax 运算符，$W_1$和$W_2$为两个线性神经网络。${\pi }_{\theta }(a_t|s_t)$表示了所有动作的概率分布。

3.3 动态预测

KGE 模型不依赖于知识图谱的连接性，因此可在稀疏的知识图谱上有超越多跳推理模型的性能。对于一个查询$(e_s,r_q,?)$，通过预训练的 KGE 模型获得所有实体的概率向量$p$，该向量的第$i$ 个值表示第$i$ 个实体是目标实体的可能性。然后 state 重新定义如下：

其中$e_p$表示通过 KGE 模型获得的预测目标实体。有如下三种策略获得$e_p$：

（1）采样策略。由概率分布$p$进行采样得到

（2）Top-one 策略。从概率分布$p$中选择概率最大的。

（3）平均策略。对所有的实体向量加权求平均得到。

3.4 动态完备

稀疏 KG 中，初始节点到目标节点通常无通路，因此要扩充行为空间。在状态$s_t$下，可扩充行为集合为

$C_t=\left\{(r,e)|r\in R\wedge e\in \epsilon \wedge (e_t,r,e)\notin T\right\}$，由于$C_t$比较大，因此需要从中选择部分概率最高的行为$(r,e)$。可以得到如下条件概率形式：

通过上述公式，可以先进行关系$r$的选择，再通过关系$r$选择目标实体$e$。在状态$s_t$下选择关系$r$，先通过下式计算关系$r$的 attention 值：

然后限定扩充行为空间的大小$N_{add}$为：

其中$N$是当前行为数，$M$是最大扩充行为数。从$w$中选取 top $x$ 的关系集$R_{add}=\left\{r^1,r^2,...,r^x\right\}$。在得到关系集$R_{add}$之后，通过预训练的 KGE 模型对每个关系求目标实体的概率分布。再从中取 top $k$个目标实体得到扩充行为空间$A_{add}^t$，$k$和$x$的关系为$x=\lceil N_{add}/k\rceil$。则最终的行为空间为：

3.5 策略优化

通过最大化训练集中每个三元组的预期奖励来进行训练。

结论

实验细节可以阅读论文，本篇博文不进行说明。论文下载地址：https://arxiv.org/abs/2010.01899