Article

文献题目：DIVINE: A Generative Adversarial Imitation Learning Framework for Knowledge Graph Reasoning
文献时间：2019
发表期刊：EMNLP

摘要

知识图谱（KGs）经常遭受稀疏和不完整的困扰。知识图谱推理为解决此类问题提供了一种可行的方法。最近对知识边图推理的研究表明，基于强化学习 (RL) 的方法可以提供最先进的性能。然而，现有的基于 RL 的方法需要大量的路径寻找试验，并且严重依赖细致的奖励工程来适应特定的数据集，这对于快速发展的 KG 来说效率低下且费力。在本文中，我们提出了 DIVINE，这是一种基于生成对抗模仿学习的新型即插即用框架，用于增强现有的基于 RL 的方法。 DIVINE 引导寻路过程，并通过模仿从 KG 中自动采样的演示自适应地学习推理策略和奖励函数。在两个基准数据集上的实验结果表明，我们的框架在没有额外奖励工程的情况下证明了现有基于 RL 的方法的性能。

引言

知识图谱，通常由大量的关系三元组组成，是许多下游自然语言处理应用程序的有用资源，例如信息提取和问答。尽管现有的 KG 具有非常大的规模，但它们仍然高度不完整（Min 等，2013 年），导致了广泛的研究工作，即从观察到的证据中自动推断缺失信息。在本文中，我们关注 KG 中的多跳推理问题，它从现有的三元组中学习显式推理公式以完成缺失的三元组。
为了解决多跳推理，各种基于路径的方法（Lao et al., 2011; Gardner et al., 2013, 2014; Guu et al., 2015; Neelakantan et al., 2015; Toutanova et al., 2016; Das et al., 2017) 已经被提出，它利用 KG 中精心选择的关系路径作为推理证据。然而，这样的证据路径是通过随机游走获得的，这不可避免地会引入劣质甚至嘈杂的路径。为了解决这个问题，基于 RL 的方法，如 Deep Path (Xiong et al., 2017) 和 MINERVA (Das et al., 2018)，通过策略条件行走来争取更可靠的证据路径，并实现状态-最先进的表演。他们将寻路问题表述为马尔可夫决策过程，其中基于策略的代理根据当前状态和推理策略不断选择最有希望的状态转换关系。一旦找到关系路径，推理策略就会根据路径质量由奖励函数更新。最后，通过这样的试错过程，训练有素的基于策略的智能体可以用来寻找预测的证据路径。
然而，这些基于 RL 的方法仍然存在以下痛点。首先，它们往往需要从头开始进行多次试验才能找到可靠的证据路径，因为由于 KG 的复杂性，动作空间可能非常大，这会导致收敛性差。其次，也是最重要的，RL 中的有效试错优化需要手动设计奖励函数以适应特定数据集。然而，这种奖励工程依赖于具有领域专业知识的精细人工设计，这在实践中可能具有很大的挑战性（Ng et al., 2000）。特别是，这些基于 RL 的方法对其奖励函数极为敏感，稍有变化就可能导致推理性能出现显着波动。因此，对于不同的数据集，RL 中的奖励函数需要手动调整才能获得良好的性能，这不仅效率低、费力，而且难以适应现实世界 KG 的快速演变（Shi 和 Weninger，2018 年）。
在本文中，我们提出了一种基于生成对抗模仿学习 (GAIL) (Ho and Ermon, 2016) 的新型即插即用框架，用于增强现有的基于 RL 的方法，该框架被称为 DIVINE，用于“深度推理”通过模仿非人类专家”。 DIVINE 通过使用生成对抗训练从演示中训练一个由生成器和判别器组成的推理器，其中生成器可以是现有基于 RL 的方法中的任何基于策略的代理，而判别器可以是被认为是一种自适应奖励函数。这样，对于不同的数据集，可以自动调整奖励函数以接近最佳性能，从而消除额外的奖励工程和人工干预。特别是，为了使基于策略的代理能够找到更多不同的预测证据路径，我们提出了一种基于路径的 GAIL 方法，该方法可以通过模仿演示的路径级语义特征来学习推理策略。此外，为了在不进行额外人工劳动的情况下获得演示，我们为我们的框架设计了一个自动采样器，以根据每个实体的特定环境动态地从 KG 中采样关系路径作为演示。
总之，我们的贡献有三方面：
- 我们提出了一个基于 GAIL 的即插即用框架，通过模仿演示来学习推理策略和奖励函数，从而增强 KG 中现有的基于 RL 的推理。据我们所知，我们是第一个将 GAIL 引入知识图谱推理领域的人。
- 我们提出了一种基于路径的 GAIL 方法来鼓励证据路径的多样性，并为我们的框架设计一个自动采样器来对演示进行采样，而无需额外的人工劳动。
- 我们对两个基准数据集进行了广泛的实验。实验结果表明，我们的框架提高了当前最先进的基于 RL 的方法的性能，同时消除了额外的奖励工程。

预训练

知识图推理

给定一个不完整的知识图 $\{ (h, r, t)|h \in E, t \in E, r \in R \}$ ，其中 $E$ 和 $R$ 分别表示实体集和关系集。知识图推理有两个主要任务，即链接预测和事实预测。链接预测涉及在给定头部实体 $h$ 和查询关系 $r_q$ 的情况下推断尾部实体 $t$ ，而事实预测旨在预测未知事实 $h, r_q, t)$ 是否成立。最近，基于 RL 的推理已成为知识图推理的流行方法，它实现了最先进的性能。一般来说，基于 RL 的推理方法努力寻找关系路径来调整其推理策略以进行预测，并将路径寻找问题表述为马尔可夫决策过程 (MDP)。在这样一个过程中，基于策略的代理根据其推理策略 $π$ 决定从当前状态（即当前实体及其上下文信息） $\in S$ 采取行动 $\in A$ 到达下一个，其中动作空间被定义为 $G$ 中的所有关系。特别地，关系路径中的每个关系链都可以被认为是一个推理链。

模仿学习

模仿学习侧重于从示范中学习政策，在解决奖励工程方面取得了巨大成功。经典的方法是通过逆强化学习 (IRL) (Russel l, 1998; Ng et al., 2000) 找到最佳奖励函数来解释专家的行为。然而，IRL 需要在学习循环中解决 RL，这在大型环境中运行可能会很昂贵。因此，最近提出了生成对抗模拟学习 (GAIL) (Ho and Ermon, 2016)，它通过生成对抗网络 (GAN) 学习专家策略 (Goodfellow et al., 2014)，消除了任何中间 IRL 步骤。
在 GAIL 中，生成器 $G_θ$ 被训练以生成与专家轨迹分布相匹配的轨迹（即演示）。每个轨迹 $τ$ 表示为状态-动作序列 $[(s_t , a_t)]_{t=0}^∞ (s_t \in S, a_t \in A)$ 。此外，还学习了一个鉴别器 $D_ω$ 来区分生成的策略 $π_θ$ 和专家策略 $π_E$ 。对于每个训练时期，首先使用梯度更新鉴别器：
其中 $τ_E$ 表示由 $π_E$ 生成的专家轨迹，轨迹期望可以在 $γ$ 折现的无限视野中计算为：
这里的判别器可以解释为局部奖励函数，为策略学习过程提供反馈。然后，生成器使用信任区域策略优化 (TRPO) 更新成本函数 $l o g (D (s, a))$ (Schulman et al., 2015)。经过充分的对抗训练，GAIL 可以找到最优策略 $\hat{\pi}$ 以合理化专家策略 $π_E$ 。

方法

框架综述

如图 1 所示，我们的框架 DIVINE 由两个模块组成，即生成对抗推理器和演示采样器。特别地，推理器由生成器和判别器组成。生成器可以是现有基于 RL 的方法中的任何基于策略的代理，判别器可以解释为自适应奖励函数。对于每个查询关系，分别采用采样器和生成器来自动提取演示并从给定的 KG 中生成关系路径。然后使用鉴别器评估生成的路径和演示之间的语义相似性以更新生成器。
figure1：我们的框架 DIVINE 概述，其中生成器可以是任何现有的基于策略的知识图推理代理，而判别器可以被视为自适应奖励函数。
在生成器和判别器之间交替进行充分的对抗训练之后，训练有素的基于策略的代理（即生成器）可用于找到与演示分布相匹配的证据路径，并通过综合这些证据路径进行预测。

生成对抗推理机

在我们的框架中，推理器是通过生成对抗训练从演示中学习的。一种直接的方法是直接应用 GAIL 来训练推理器。特别是，推理器中的基于策略的代理被训练以通过模仿每个专家轨迹（即演示）中的状态-动作对来找到证据路径。但是，这种方法可能会导致性能不佳。主要原因在于智能体在某些状态下倾向于选择与专家轨迹中相同的动作，而忽略了许多在语义上与专家轨迹相似但包含不同推理链的有价值的证据路径。
因此，为了鼓励智能体找到更多样化的证据路径，最好通过模仿每个轨迹而不是每个状态-动作对来训练智能体。此外，在知识图谱推理的场景中，由于推理链仅由关系组成，因此演示不一定包含状态信息。换句话说，演示只能由关系路径组成。
基于上述分析，我们提出了一种基于路径的 GAIL 方法，该方法通过模仿仅由关系路径组成的演示的路径级语义特征来学习推理策略。
在下文中，我们首先描述推理器的两个组件，即生成器和判别器。然后，我们展示了如何提取路径级语义特征。

生成器

生成器可以是现有基于 RL 的方法中的任何基于策略的代理。我们努力使生成器能够找到与语义空间中的演示分布相匹配的更多样化的证据路径。

判别器

为了更好地在语义上区分生成的路径和演示，我们选择卷积神经网络 (CNN) 来构建我们的鉴别器 $D$ ，因为 CNN 在从自然语言中提取语义特征方面表现出高性能 (Kim, 2014)。

语义特征提取

对于每个正实体对，我们分别将当前生成的路径和对应的演示打包在同一个package形式中。对于包含 $N$ 个关系路径的每个package $P = \{ x_1, x_2, ..., x_N \}$ ，我们将package编码为实值矩阵：
其中 $x_n \in R^k$ 是 $k$ 维路径嵌入， $\oplus$ 表示package表示 $\in R^{N×k}$ 的连接算子。特别是，给定一个关系路径 $x = \{ r_1, r_2, ...r_t , ...\}$ ，嵌入路径 $x$ 被编码为：
其中每个关系 $r_t$ 映射到由 TransE 预训练的实值嵌入 $r_t \in R^k$ (Bor des et al., 2013)。
打包后，我们将包表示 $p$ 输入我们的鉴别器 $D$ 以参数化其语义特征 $D (p)$ 。具体来说，首先使用由 ReLU 非线性激活的卷积层通过滑动内核 $\in R^{h×l}$ 来提取局部特征，以获得新的特征图：
其中 $b_c$ 表示偏置项。然后，一个全连接的隐藏层和一个输出层用于进一步的语义特征提取：
其中为简洁起见，上面没有显示相应的偏差，输出层由 sigmoid 函数归一化，而其他层由 ReLU 非线性激活。

演示取样器

对于模仿学习，第一个前提是要有高质量的演示。然而，由于 KG 的规模和复杂性，手动构建大量的推理演示需要大量的时间和专家的努力。因此，我们设计了一个自动采样器来从 KG 中采样可靠的推理演示，而无需监督和额外的人工劳动。

静态演示采样

对于每个查询关系，我们使用所有正实体对从给定的 KG 中采样演示候选。具体来说，对于每个正实体对，我们使用双向广度优先搜索来探索两个实体之间的最短路径。特别是，由于较短的路径倾向于表征两个实体之间更直接的相关性，我们更喜欢将它们用于初始化以确保演示候选的质量。至于较长的路径，尽管它们具有潜在的效用价值，但它们更可能包含毫无价值甚至嘈杂的推理步骤，因此我们仅在训练阶段学习它们。这样做，我们可以得到一个演示集 $Ω_E$ ，其中包含我们采样的所有候选者。最后，为了适应判别器 $D$ 的固定输入维度，我们可以简单地选择一个子集 $P_e ⊆ Ω_E$ ，其出现频率最高为 $N$ ，其中 $N$ 通常远小于 $Ω_E|$ 。

动态演示采样

尽管静态演示采样方法很简单，但通过这种方法获得的演示是固定的，并且忽略了给定 KG 中每个实体的特定环境。因此，我们提出了一种通过考虑实体的拓扑相关性来动态采样演示的改进方法。
给定一个正实体对 $e_{head}，e_{tail}⟩$ ，我们引入一个关系集 $R_h$ ，其中包含所有与 $e_{head}$ 直接相关的关系。对于每次推理尝试， $R_h$ 可以被视为代理开始推理的感兴趣区域 (ROI)，其中与 ROI 相关的路径往往与当前实体对更相关。因此，我们通过过滤掉从 $R_h$ 开始的演示来优化演示集：
其中 $Ω_E$ 由静态演示采样方法生成， $r_1(x)$ 表示关系路径 $x = \{ r_1, r_2, ...r_t, ...\}$ 中的第一个关系。
在大多数情况下，我们可以在 $Ω^′_E$ 中获得足够的演示来选择子集 $P_e ⊆ Ω^′_E$ ，方法与静态演示采样方法相同。然而，由于 KG 中数据的稀疏性，我们可能无法在长尾实体上获得足够的演示。为了解决这个问题，我们执行语义匹配以探索剩余候选 $\ Ω E ′ C_E = Ω_E \backslash Ω^′_E$ 的更多演示。由于推理策略是根据生成的路径和演示之间的语义相似性来更新的，因此在语义上与当前演示相似的候选也对模仿过程具有指导意义。
受到一次性模仿学习的邻域注意力的启发（Duan et al., 2017），我们使用 $KaTeX parse error: Expected group after '^' at position 2: Ω^̲'_E$ 中的每个演示来查询与其自身相关的其他候选日期。我们采用点积来衡量两个路径嵌入之间的语义匹配相似度：
其中 $α_i$ 表示当前候选 $\bar{x}_i$ 与 $Ω'_E$ 中现有演示之间的匹配分数之和。最后，我们迭代地选择具有最高 $α$ 的候选者来填充细化的演示集 $Ω^′_E$ ，直到满足所需的输入维度 $N$ 。

训练

在训练阶段，所有的正实体对都被用来为模仿学习过程生成示范候选 $Ω_E$ 。具体来说，对于每一个正实体对，首先需要演示采样器选择对应的演示，同时引导生成器生成一些关系路径。然后，将演示打包到包 $P_e$ 中，生成的路径根据其有效性打包到不同的包年龄 ${ P_g | P_g ⊆ Ω_G\}$ 中，即代理是否可以沿当前路径到达目标实体，其中 $Ω_G$ 是所有生成路径的集合。
对于每个包对 $P_g,P_e⟩$ ，我们通过最小化其损失来训练鉴别器 $D$ ，并期望它成为区分 $P_e$ 和 $P_g$ 的专家。此外，为了使对抗训练过程更加稳定和有效，我们采用 WGAN-GP (Gulrajani et al.,2017) 中提出的损失函数来更新鉴别器：
其中 $L_C$ 、 $L_P$ 和 $L_D$ 分别表示原始评论家损失、梯度惩罚和鉴别器损失， $λ$ 是梯度惩罚系数 $t$ 和 $\tilde{p}$ 沿 $p_g$ 和 $p_e$ 之间的直线均匀采样。根据判别器的反馈，我们计算奖励 $R_G$ 为：
其中 $p_n$ 表示由具有连续均匀分布的随机噪声组成的噪声嵌入， $δ_g$ 是表征包 $P_g$ 有效性的特征函数， $Ω^+_G$ 是所有有效生成路径的集合。我们只对至少比噪声嵌入 $p_n$ 具有更高期望的部分有效路径给予正奖励，噪声嵌入 $p_n$ 过滤掉质量较差的路径，以提高训练过程的收敛效率。一旦获得奖励，我们通过使用 Monte-Carlo 策略梯度（即 REINFORCE）最大化预期累积奖励来更新生成器 $G$ （Williams，1992）。

实验

数据集和评估指标

实验在两个基准数据集上进行：NELL-995 (Xiong et al, 2017) 和 FB15K-237 (Toutanova et al, 2015)。两个数据集的详细信息在表 1 中进行了描述。特别是，NELL-995 是已知的用于推理任务的简单数据集，它是从 NELL 系统的第 995 次迭代（Carlson 等，2010）中通过选择具有前 200 个频繁出现关系的三元组生成的。与 NELL 995 相比，FB15K-237 更具挑战性，更接近真实场景，其事实是从 FB15K (Bordes et al, 2013) 创建的，删除了冗余关系。对于每个三元组 $(h, r, t)$ ，两个数据集都包含逆三元组 $h, r^{−1} , t)$ ，因此智能体可以在 KG 中后退一步，这使得有可能从以前做出的潜在错误决定中恢复过来。对于每个具有查询关系 $r_q$ 的推理任务，所有具有 $r_q$ 或 ${r_q}^{−1}$ 的三元组都从 KG 中删除，并分成训练和测试样本。
表 1：数据集的统计数据。 # Ent: 表示唯一实体的数量和#Rel: 表示关系的数量。
与最近的工作类似（Das 等人，2018；X iong 等人，2017），我们使用平均平均精度（MAP）、平均倒数排名（MRR）和 Hits@k 来评估推理性能，其中 Hits@k 是排名前 $k$ 位的正实例的比例。

基线和实施细节

在我们的实验中，我们将两种最先进的基于 RL 的方法作为基线：DeepPath (Xiong et al., 2017) 和 MINERVA (Das et al., 2018)。深度路径将收集到的证据路径提供给 PRA (Lao et al., 2011)，用于链接预测和事实预测任务，而 MINERVA 直接将训练有素的代理应用于链接预测任务以进行问答。对于 Deep Path，我们使用 Xiong 等人 (2017) 发布的代码。对于 MINERVA，我们使用 Das 等人 (2018) 发布的代码。基线的实验设置是根据原始论文中的建议设置的。
在我们框架的实现中，我们将每个路径包 $P$ 的路径编号 $N$ 设置为 5，而路径维度 $k$ 设置为 200，这与基线中的关系维度相同。对于判别器，我们设置卷积核大小为3×5，隐藏层大小为1024，输出层大小为路径维度 $k$ ，同时梯度惩罚系数 $λ$ 设置为5，L2 正则化也用于避免过度拟合。
在测试期间，我们还将答案三元组与 DeepPath 和 MINERVA 中使用的负三元组进行排名。特别是，每个正三元组大约有 10 个对应的负三元组。每个否定三元组都是通过用一个假的 $t^{'}$ 替换答案实体 $t$ 生成的，给定一个正三元组 $(h, r, t)$ 。

结果

两个数据集的主要结果如表 2 所示。我们使用“Div()”表示采用我们的框架 DIVINE 的基于 RL 的方法“”。为了公平比较，我们按照 MINERVA 报告 Hits@k 和 MRR 分数（用“†”表示）来评估问题回答的链接预测性能，它根据代理可以沿证据路径到达实体的概率对实体进行排名。此外，我们还按照 DeepPath 报告事实预测任务的 MAP 分数（用“‡”表示），它直接对给定查询关系的所有正负三元组进行排名。
表 2：NELL-995 和 FB15K-237 的总体结果。 “†”表示带有问答设置的结果，“‡”表示给定查询关系的所有正负三元组直接排序的结果。
从表 2 中显示的结果可以看出，我们的框架在链路预测和事实预测任务上对两种基于 RL 的方法在不同程度上产生了一致的改进。一方面，对于现有的基于 RL 的方法，它们在 FB15K-237 上的结果通常低于 NELL-995 上的结果，因为 FB15K-237 更复杂，并且可以说更难以手动设计适当的奖励函数。然而，我们的框架通过动态学习优越的奖励函数在一定程度上缓解了这个问题，因此我们对具有挑战性的 FB15K-237 做出了更大的改进。另一方面，对于不同的数据集，我们的框架对 DeepPath 的改进差异很大，而 MINERVA 则不然。这是因为 MINERVA 在计算累积折扣奖励时会手动调整其超参数，而 DeepPath 保持不变。显然，它验证了现有的基于 RL 的方法有必要相应地调整其奖励函数以适应不同的数据集。通过我们的框架增强，这些基于 RL 的方法不再需要对不同数据集进行额外的手动调整，这显示出极大的鲁棒性。
与现有的基于 RL 的方法类似，我们还报告了链接预测的分解结果，并使用 MAP 评估表 3 中 NELL-995 上每个查询关系的性能。从结果中，我们可以观察到不同关系的结果具有高方差，增强的基于 RL 的方法对所有查询关系都实现了更好或可比的性能。
表 3：NELL-995 上不同查询关系分解的链接预测结果。

基于路径的 GAIL 方法的有效性

为了研究基于路径的 GAIL 方法的有效性，我们分别通过基于路径的 GAIL 方法和原始 GAIL 方法在 NELL-995 上训练 DeepPath 中的基于策略的代理。特别是，在原始的 GAIL 方法训练智能体的过程中，演示由状态-动作轨迹组成。对于每个状态-动作对 $s_t, a_t)$ ，状态表示 $s_t$ 由 $e_t, e_{tail} - e_t)$ 计算，其中 $e_t$ 和 $e_{tail}$ 分别表示当前实体和尾部实体的嵌入。在图 2 中，我们显示了代理发现的与演示不同的证据路径集 $P_{new}$ 的统计信息。在表 4 中，我们比较了 $P_{new}$ 的平均路径数和两个预测任务的推理性能。
如图 2 和表 4 所示，我们可以观察到，我们的基于路径的 GAIL 方法为大多数查询关系获得了更多的证据路径，并且在链接和事实预测上都取得了更好的性能，这验证了我们基于路径的 GAIL 方法的有效性以及鼓励智能体寻找更多样化的证据路径的合理性。

消融研究

我们通过将 Deep Path 嵌入到我们的框架中来进行消融研究，以量化组件的作用。具体来说，我们通过消融某些组件来重新训练我们的框架：
- W/O Semantic Matching，在长尾实体上不进行语义匹配。相反，我们根据其出现频率直接从剩余的示范候选 CE 中提取一些路径。
- W/O Dynamic Sampling，不执行动态演示采样以结合实体的本地环境。也就是说，我们只采用静态演示采样的方式来获取演示。
- W/O Demo Sampling，其中不使用演示进行模仿学习，而是生成到 DeepPath。
我们使用 MAP 评估表 5 中 NELL-995 和 FB15K-237 上的链路预测性能。从结果中我们可以观察到：（1）基于模仿学习，我们的框架可以有效地提高推理性能，即使我们使用静态演示采样的方法来获得演示；(2) 高质量的演示对于模仿学习至关重要，这表明拓扑过滤和语义匹配在我们框架的演示采样器中都发挥着重要作用。