关键词：

• 论文标题：DeepPath: A Reinforcement Learning Method for Knowledge Graph Reasoning
• 中文标题：深度路径：知识图谱推理的强化学习方法
• 项目代码：GitHub@DeepPath
• 论文下载：arxiv@1707.06690

序言

最近把之前写综述看的一百多篇paper整理了一下，然后准备抽几篇感觉不错的写点详细的笔注，这篇是讲知识图谱补全中关系路径方法比较好的一篇，看下来感觉的确方法是有创新性的，一些想法很值得借鉴。

最近走回正轨，身体仍然处于恢复期，虽然现在情势并不太乐观，但是仍然要做好充分的准备，万一上半年有比赛能参加是一定要去的，只是一个寒假长了10斤（68kg$\\rightarrow$73kg），压力特别大，很难回到去年年底时的巅峰状态了，返校半个多月基本每天都有训练，耐力始终上不去，实在是令人很不快。老王一个寒假没怎么练，拉垮得比我还厉害，不过他还是报了上半年的厦马，于是我也跟着报了个名，反正大概率也抽不上，希望四月份的上海半马和扬州的世马测试赛能办得了就好了。

慢慢来吧，事情都是急不得的了。

文章目录

• 序言
• 摘要 Abstract
• 1 引入 Introduction
• 2 相关工作 Related Work
• 3 方法 Methodology
• • 3.1 关系推理的强化学习 Reinforcement Learning for Relation Reasoning
  • 3.2 训练管道 Train Pipeline
  • 3.3 双向路径限制搜索 Bi-directional Path-constrained Search
• 4 实验 Experiment
• • 4.1 数据集与配置 Dataset and Settings
  • 4.2 基线与实现细节 Baselines and Implementation Details
  • 4.3 结果 Results
  • • 4.3.1 定量结果 Quantitative Results
    • 4.3.2 推理路径的定量分析 Qualitative Analysis of Reasoning Paths
    • 4.3.3 监督学习的效果 Effect of Supervised Learning
• 5 结论与未来工作 Conclusion and Future Work
• 致谢 Acknowledgments
• 参考文献

摘要 Abstract

• 本文研究如何在大规模的知识图谱中进行推理。
• 本文提出一种强化学习框架用于学习多级关系路径（multi-hop relational paths），具体而言，强化学习的状态（state）是基于知识图谱嵌入（knowledge graph embeddings）的连续型向量，智能体是基于策略的（policy-based agent），即根据策略网络（policy network）进行更新迭代。具体而言，智能体在知识图谱向量空间中通过采样最可信的关系来扩展其路径以实现推理。
• 相较于之前的工作，本文在强化学习的奖励函数（reward function）中考虑了精确性（accuracy），多样性（diversity），功效性（efficiency）。
• 实验表明，本文提出的方法在Freebase与NELL（Never-Ending Language Learning datasets）两个知识图谱数据集上比一种基于路径排序（path-ranking）的算法以及一种知识图谱嵌入方法要表现得更好。

1 引入 Introduction

• 本文的研究是多级推理（multi-hop reasoning），即根据知识图谱中的实体关系信息学习得到显式推理公式（explicit inference formulas）。比如，若知识图谱中包含如下两组事实：

  1. 内马尔效力于巴塞罗那；
  2. 巴塞罗那属于西甲联盟；

  则机器应当能够学习得到如下的公式：
  $$\text{playerPlaysForTeam}(P,T)\wedge \text{teamPlaysInLeague}(T,L)\Rightarrow \text{playerPlaysInLeague}(P,L)$$
  在测试过程中，通过嵌入学习到的公式，系统能够自动推断出实体间可能存在的缺失关系（即知识图谱补全）。

• 参考文献[16 17 18]中提出的路径排序算法（Path-Ranking Algorithm，下简称为PRA）是在大规模知识图谱中学习推理路径的流行方法。PRA使用的是随机游走（random-walk）策略，智能体通过执行多次有限制的深度优先搜索（bounded depth-first search）来寻找关系路径。

  然后与弹性网络（elastic-net，即在损失函数中同时加入一次正则项与二次正则项）相结合，PRA通过监督学习挑选出更合理的路径。

  然而PRA是在全离散空间（fully discrete space）进行搜索，因此它难以评估与比较知识图谱中相似的实体与关系。

• 本文提出使用强化学习来搜索关系路径以实现多级推理。相较于PRA，本文使用的参考文献[2]中基于翻译的（translation-based）嵌入方法来编码强化学习智能体的连续状态，并在知识图谱的向量空间环境（environment）中进行推理。

  智能体通过采样关系不断扩展其路径，为确保智能体更好地学习关系路径，本文使用参考文献[22]中提出的策略梯度训练（policy gradient training）方法，并在强化学习的奖励函数中引入精确性，多样性，功效性三个新指标，最终在Freebase与NELL知识图谱数据集（参考文献[3]）上取得了更好的实验结果。

• 本文的贡献有三：

  1. 首次将强化学习方法用于学习知识图谱中的关系路径；
  2. 通过在奖励函数引入三个新指标，使得路径发现更加灵活与可控；
  3. 本文的方法可以推广到大规模的知识图谱中，并依然表现得比PRA更好；

2 相关工作 Related Work

• PRA起源于参考文献[16 17 18]，此后有学者对其做出改进：

  1. 参考文献[6 7]在PRA中引入计算特征相似度。
  2. 参考文献[26]提出一种递归的随机游走方法来结合知识图谱与文本，该方法对逻辑程序（logic program）进行结构化学习（structure learning），并同时从文本中挖掘信息。
  3. 随机游走的问题在于超节点（supernodes）与大量的公式连接形成庞大的扇出区（fan-out area，通常指深度学习中下一层的节点数），使得推理缓慢且精确性降低。（这个其实还是易于理解的，即随机游走可能会学习得到大量潜在的关系路径，神经网络需要对这些路径进行评估，比如最后以softmax层输出多分类结果，则输出的节点数会非常庞大，分类精确性自然很差）

• 关于多级推理的深度学习方法：

  1. 参考文献[25]提出一种卷积神经网络模型的解决方案，其建立的模型基于句法依存路径（lexicalized dependency paths），因句法解析的错误使得网络传播中也会发生错误。
  2. 参考文献[9]使用知识图谱嵌入来回答路径查询（path queries）。
  3. 参考文献[29]提出一种卷积神经网络模型来建模关系路径用于知识图谱补全，但是它训练太多的小模型，因而无法推广到大规模的情形。
  4. 近期大部分的知识图谱推理方法（参考文献[5 23]）仍然依赖于学习PRA路径，且只是在离散空间中搜索。

• 参考文献[19]提出的神经符号机器（Neural symbolic machine，下简称为NSM）也采用了强化学习方法，但是与本文的研究有所区别。NSM是学习复合程序（compose program）用以对自然语言问题进行作答，本文的模型则是用以向知识图谱中添加新的事实（即知识图谱补全）。

  NSM学习生成得到一系列的行为（actions），并将它们依次合并作为可执行程序（executable program），NSM的行为空间（action space）是一系列预先设置号的标记，而本文的目标是发现推理路径，因此行为空间即知识图谱中的关系空间。

  参考文献[12]中提出得是一个与NSM类似的框架，目前已经被应用于可视化的推理任务中。

3 方法 Methodology

• 再次强调：本文所要解决的多级推理问题是预测实体对之间可能缺失的关系。
• 本文将路径发现问题抽象为序列决策制定问题，从而可以被强化学习方法解决。
• 本文提出的强化学习框架中的智能体是基于策略的（policy-based），在知识图谱向量空间的环境中进行交互，以学习选取得到最可信的推理路径。
• 本节的第二小节与第三小节中将分别阐述模型训练以及如何根据智能体找到的路径进行关系推理的一种路径约束搜索算法（path-constrained search algorithm）。

3.1 关系推理的强化学习 Reinforcement Learning for Relation Reasoning

• 根据Figure 1中的描述，强化学习模型由两部分构成：

  1. 外部环境$\mathcal{E}$：确定智能体与知识图谱的动态交互，由马尔克夫决策过程（Markov Decision Process，下简称为MDP）建模得到。

     具体而言，四元组$(\mathcal{S},\mathcal{A},\mathcal{P},\mathcal{R})$用于定义表示MDP，其中$\mathcal{S}$表示连续的状态空间，$\mathcal{A}=a_1,a_2,...,a_n$是一系列可用的行为，$\mathcal{P}(S_{t+1}=s^{\prime }|S_t=s,A_t=a)$表示转移概率矩阵（transition probability matrix），$\mathcal{R}(s,a)$表示每个$(s,a)$对的奖励函数。

  2. 智能体：由策略网络（policy network）表示，策略函数为${\pi }_{\theta }(s,a)=p(a|s;\theta )$，即将状态向量映射为一个随机策略（stochastic policy）。其中，$\theta$表示神经网络参数，使用随机梯度下降法（stochastic gradient descent，下简称为SGD）进行迭代更新。

• 与参考文献[21]中提出的DQN模型相比，基于策略的强化学习方法更适合于本文所研究的知识图谱场景。原因有二：

  1. 知识图谱中的路径发现问题，通常涉及的行为空间是非常大的，因此容易使得DQN模型难以收敛；
  2. DQN模型通常基于价值（Q值）得到一个贪心的策略，策略网络则能够学习随机策略以防止智能体陷于某个中间态（intermediate state）无法继续更新。

• 强化学习框架的组成：

  1. 行为（Actions）：给定实体对$(e_s,e_t)$和它们的关系$r$，我们希望智能体能够找到最富含有用信息的（informative）路径来链接该实体对。

     从源实体$e_s$开始，智能体利用策略网络来选取最可信的关系来扩展其路径，直到抵达目标实体$e_t$为止。为使策略网络的输出维数相一致，我们将行为空间定义为知识图谱中的所有关系的集合。

  2. 状态（States）：知识图谱中的实体与关系通常表示为离散符号，如Freebase（参考文献[1]）与NELL（参考文献[4]）中都包含巨量的三元组，因此想要在状态空间中建模所有的离散符号几乎是不可能的。

     于是本文认为可以使用如TransE（参考文献[2]）与TransH（参考文献[27]）等知识图谱嵌入方法将实体与关系表示为特征向量，以达到降维的目的。此时我们需要记录智能体的当前所在的实体位置以及它下一个即将达到的实体，具体而言：
     $$s_t=(e_t,e_{\text{target}}-e_t)$$
     其中$e_t$表示当前实体的嵌入，$e_{\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{e}\mathrm{t}}$表示目标实体的嵌入，初始状态下有$e_t=e_{\mathrm{s}\mathrm{o}\mathrm{u}\mathrm{r}\mathrm{c}\mathrm{e}}$。

     注意这里并没有将关系嵌入包含在状态中，因为关系嵌入在路径发现过程中是一个常数，对模型训练是没有帮助的。然而我们还是发现如果使用一系列正样本来训练智能体用于发现某个特定的关系，智能体也可以发现关系的语义（即关系嵌入）。

  3. 奖励（Rewards）：为了使得智能体能够更好的找到预测路径，本文在奖励函数中引入新指标指标。

     • 全局精确性（Global accuracy）：前面提到行为空间是非常庞大的，因此可想而知智能体做出的大部分序列决策都是错误的，错误的路径会导致路径长度成指数级增长，因此定义如下的指标：
       $$r_{\mathrm{G}\mathrm{L}\mathrm{O}\mathrm{B}\mathrm{A}\mathrm{L}}=\begin{array}{rlrl}& +1& & \text{if the path reaches }{e}_{\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{e}\mathrm{t}}\\ & -1& & \text{otherwise}\end{array}$$
       即只要路径最终找到了目标实体，就赋值为正，否则赋值为负。

     • 路径功效性（Path efficiency）：就关系推理任务而言，本文发现短路径往往比长路径提供更可靠的推理证据。因此定义如下的指标：
       $$r_{\mathrm{E}\mathrm{F}\mathrm{F}\mathrm{I}\mathrm{C}\mathrm{I}\mathrm{E}\mathrm{N}\mathrm{C}\mathrm{Y}}=\frac{1}{\text{length}(p)}$$
       其中路径$p$定义为一系列关系的序列：$r_1\to r_2\to ...\to r_{}$

       论文标题：DeepPath:AReinforcementLearningMethodforKnowledgeGraphReasoning中文标题：深度路径：知识图谱推理的强化学习方法项目代码：GitHub@DeepPath论文下载：arxiv@1707.06690序言最近把之前写综述看的一百多篇paper整理... 查看详情

       十四，教育知识图谱的概念模型与构建方法研究

       十四，教育知识图谱的概念模型与构建方法研究论文名称：教育知识图谱的概念模型与构建方法研究李振，周东岱.研究对象以知识图谱为基础，构建教育知识图谱概念模型，对其智能化构建方法进一步研究。研究动机知识图谱... 查看详情

       3.知识图谱相关学习资料汇总，提供系统化的知识图谱学习路径。一份详细的指南，补全你知识的漏洞

       目录理论及论文图谱及数据集工具及服务白皮书及报告机构及人物视频课程专栏合集评测竞赛项目案例推广技术文章1.整体概念架构随着知识图谱的发展，与之相关的概念也越来越多，在阅读论文时先准确的把握该论文所要解决... 查看详情

       机器不学习：基于知识图谱推理的关系推演

       对于知识图谱的关注可以分为两个方面：知识图谱的构建和基于知识图谱数据结构的应用。知识图谱的构建主要关注如何整合结构化、非结构化的数据，实现用统一的语义数据结构如三元组RDF形式的数据存储。基于知识图谱的应... 查看详情

       [论文阅读笔记54]面向实体对齐的多视图知识图谱嵌入方法

       1.题目Multi-viewKnowledgeGraphEmbeddingforEntityAlignment面向实体对齐的多视图知识图谱嵌入方法论文：https://arxiv.org/pdf/1906.02390.pdf代码：https://github.com/nju-websoft/MultiKE2.研究背景研究的问题：知识图(KGs)之间基于嵌入 查看详情

       面向知识图谱的图嵌入学习进展

       ...图谱在各个领域的广泛应用，面向知识图谱的图嵌入学习也得到越来越多研究人员的关注.面向知识图谱的图嵌入学习任务旨在为图谱中的实体与关系学习低维且稠密的向量，通过图嵌入向量表达实体与关系的语义信息以... 查看详情

       如何高效学习kubernetes知识图谱？

       简介： Kubernetes知识图谱遵循云原生人才学习路径搭建课程体系框架，及人才发展路线设置不同阶段，由浅入深，帮助云原生人才学习容器基础、Kuternetes网络、存储、资源对象、服务发现、应用编排与管理等Kubern... 查看详情

       如何高效学习kubernetes知识图谱？

       简介：Kubernetes知识图谱遵循云原生人才学习路径搭建课程体系框架，及人才发展路线设置不同阶段，由浅入深，帮助云原生人才学习容器基础、Kuternetes网络、存储、资源对象、服务发现、应用编排与管理等Kubernet... 查看详情

       学人工智能应该选啥专业？

       ...根据学习模式将机器学习分类为监督学习、无监督学习和强化学习等。根据学习方法可以将机器学习分为传统机器学习和深度学习。二、知识图谱知识图谱本质上是结构化的语义知识库，是一种由节点和边组成的图数据结构，以... 查看详情

       01-introduction图机器学习介绍

       ...不确定是否理解合适，原文是theirimpactonfailures）此外，会学习到现实中故障的发生往往伴随可复现的规则，从而用于量化甚至是预测应用：1.社交网络社交圈发现（检测/挖掘）2.工业停电故障检测与预测3.知识知识图谱，混合图... 查看详情

       知识图谱实战应用1-知识图谱的构建与可视化应用(代码片段)

       ...例推理和知识发现等任务。二、知识图谱的涉及哪些深度学习的应用 1.实体链接 ：实体链接是将文本中的实体与知识图谱中的实体进行链接的过程。其中基础算法包括基于字典匹配、基于 查看详情

       论文笔记基于知识图谱的农业智能问答系统

       基于知识图谱的农业智能问答系统前言知识图谱简介知识图谱生命周期知识获取知识抽取知识存储与应用相关技术和工具农业知识图谱构建流程本体层构建实体层构建基于Neo4j的农业知识图谱问答系统算法设计基于知识图谱的问... 查看详情

       人工智能领域常用的开源框架和库（含机器学习/深度学习/强化学习/知识图谱/图神经网络）

       【说在前面】本人博客新手一枚，象牙塔的老白，职业场的小白。以下内容仅为个人见解，欢迎批评指正，不喜勿喷！[认真看图][认真看图]【补充说明】本文主要讨论人工智能领域中常用的支持Python编程语言的开源框架和库，... 查看详情

       关系抽取学习(代码片段)

       ...算法有一个非常重要的假设：对于一个已有的知识图谱（论文用的Freebase）中的一个三元组（由一对实体和一个关系构成），假设外部文档库（论文用的Wikipedia）中任何包含这对实体的句子，在一定程度上都反映了这种关系。基... 查看详情

       c++学习（三零二）知识图谱中的几种关系

       1、强关系数据库表中同一行的两个知识2、中关系文档中同一段落的两个知识3、弱关系文档中不同段落的两个知识 查看详情

       论文阅读|《制造环境下多agv调度的强化学习方法》

       《AReinforcementLearningMethodforMulti-AGVSchedulinginManufacturing》ICIT/20181摘要    这篇文章提出用强化学习求解多AGV流水车间调度问题。AGV在固定轨道上移动，在机器之间运输半成品（semi-finishedproduct）。    目标：最小... 查看详情

       强化学习专栏——reinforcementlearning

       ...nforcementLearning》            1.1强化学习介绍    2论文阅读总结    3论文编程实现注：持续更新中。。。     查看详情

       论文阅读-sciq1-autonomousuavtrajectoryforlocalizinggroundobjectsareinforcementlearningapproach

       AutonomousUAVTrajectoryforLocalizingGroundObjectsAReinforcementLearningApproach摘要主要思想作者目的背景意义核心创新点相关工作方法系统模型（通道和能量）初始扫描（分解两类数据：区域单元CxCy、航路点/路径点waypoint）——Snodes强化学习单... 查看详情