ACL 2020 | 知识库问答的多跳复杂问题查询图生成

2020 年 7 月 14 日 PaperWeekly

©PaperWeekly 原创 · 作者｜舒意恒

学校｜南京大学硕士生

研究方向｜知识图谱

先前从知识库回答复杂问题的工作通常分别解决两种类型的复杂性：具有约束的问题和具有多跳关系的问题。

在本文中，作者同时处理两种类型的复杂性。通过观察发现，尽早将约束条件纳入查询图可以更有效地减少搜索空间，作者提出了一种改进的分阶段查询图生成方法，该方法具有更灵活的生成查询图的方式。该文实验清楚地表明，其方法在三个基准 KBQA 数据集上达到了最先进的水平。

论文标题：Query Graph Generation for Answering Multi-hop Complex Questions from Knowledge Base

论文来源：ACL 2020

论文链接：https://www.aclweb.org/anthology/2020.acl-main.91.pdf

介绍

知识库问答尝试根据知识库回答事实类问题。它最近吸引了很多研究者的关注。知识库问答的早期研究，关注于只包含一个关系的简单问题。但是，真实的问题通常更加复杂，因此最近的研究关注于复杂的知识库文档。

当前有两种类型的复杂性被研究。

第一，带有约束的单关系问题。例如一个问题，谁是第 1 任美国总统？其中有一个简单的关系是，某个国家的总统。但也有一个约束，也就是第一个这个条件需要被满足。针对这种问题，分阶段的查询图生成方法已经被提出。它首先识别一条关系路径，然后将约束添加进去，生成一个查询图。

第二，有多跳关系的问题。例如一个问题，谁是 Facebook 创始者的妻子？这个答案与 Facebook 之间有两条关系。一个是创始者，另一个是妻子。为了回答这些问题，我们需要考虑更长的关系路径来获得正确的答案。

最主要的挑战是如何限制搜索空间，也就是减少要考虑的多跳关系路径的数量，因为搜索空间随着关系路径的长度，指数级的增长。一种解决方案是使用波束搜索。然而作者认为，几乎没有工作能够同时处理这两种复杂性。

在该文中，作者尝试同时处理两种复杂性，提出了修改分阶段的查询图生成方法以支持更长的关系路径。然而。相比在构建关系路径之后添加约束。作者尝试将添加约束和扩展关系路径同时进行。这使得算法能更有效的减少搜索空间。

方法

2.1 预备

作者的方法很大程度上受启发于现有的分阶段查询图生成方法。一个查询图有 4 种类型的节点，实体（知识库中已有的实体），存在变量（未确定的实体），lambda 变量（未确定的实体，表示答案）和聚合函数（针对实体集合的处理）。一个查询图应该恰好有一个 lambda 变量，0 个或若干个存在变量和聚合函数。

作者将分阶段查询图生成方法总结如下。

第一，从一个问题中的实体开始，找到核心的关系路径，将主题实体和一个 lambda 变量连接。

第二，在第 1 步的基础上，从一个核心关系路径，连接一个或多个在问题中找到的约束。一个约束包含一个实体加关系或一个聚合函数加关系。

第三。在前 2 步的基础上。通过与问题的相似度，对查询图进行排序。这通常是由神经网络完成的，例如 CNN。

第四，执行排序最高的查询图，来获得答案实体。

2.2 动机

将上述概述的现有方法直接应用于有约束多跳 KBQA 时，我们将面临的主要挑战是无法处理包含多跳关系的问题，因为现有工作仅考虑具有单跳。如果通过允许更长的核心关系路径进行简单的修改，搜索空间会突然变得更大。

例如，在 ComplexWebQuestions 数据集上，如果允许最多 3 跳的核心关系路径，则平均每个问题将有大约 10,000 个核心关系路径，这在计算上代价非常高。

最近的多跳知识库问答的工作，通过波束搜索解决这个问题，在生成 t+1 跳关系路径前，只保留 top-K 的 t 跳关系。然而，这种方法忽略了生成关系路径的约束。

因此，作者提出了一种改进的分级查询图生成方法，该方法在将约束附加到它之前不等待每个核心关系路径被完全生成。这种生成查询图的更加灵活的方法，再结合波束搜索机制和语义匹配模型以指导修剪，探索了一个很小的搜索空间，同时仍然保持了找到正确查询图的高可能性。

2.3 查询图生成

形式化地，作者的方法使用波束搜索迭代地生成候选查询图。假设第 t 个迭代产生了 K 个查询图的集合，在 t + 1 次迭代中，

作者使用了 extend、connect、aggregate 三个行为之一来为当前的查询图添加一条边或一个节点。在每个时间步获得查询图之后，用评分函数来对所有查询图进行排序，并找出 top-k。如此持续迭代，直到某一迭代的评分不高于它前一迭代的评分。

在迭代过程中，允许以下的行为来扩展一个查询图。

扩展动作将核心关系路径扩展了 R 中的一个关系。如果当前查询图仅包含主题实体 e，则扩展动作将在 KB 中找到链接到 e 的关系 r，并将路径增长到 r。它还使 r 的另一端成为 lambda 变量 x。如果当前查询图具有 lambda 变量 x，则扩展操作会将 x 更改为存在变量 y，通过对 KB 执行当前查询图来查找 KB 中 y 的所有绑定，找到链接到这些实体之一的关系 r ，最后将 r 附加到 y。r 的另一端成为新的 lambda 变量 x。
除了当前核心关系路径开始处的主题实体之外，问题中通常还会找到其他实体。连接操作将这样的实体 e 链接到 lambda 变量 x 或连接到 x 的存在变量（即 CVT 节点）。要确定使用哪个关系 r 链接 e 和 x，我们可以再次找到 x 的所有绑定，通过执行当前查询图，然后找到这些实体之一与 e 之间存在的关系。
作者使用一组预定义的关键字从问题中检测聚合函数。聚合操作会将检测到的聚合函数作为新节点附加到 lambda 变量 x 或连接到作为 CVT 节点的 x 的存在变量。

该方法的新颖之处在于，可以在连接和聚合操作之后应用扩展操作，而以前的方法是不允许的。扩展和连接操作可以理解为对多跳推理的实现，而聚合操作可理解为对问题约束的实现。

2.4 查询图排序

在第 t 次迭代的末尾，算法对候选查询图进行排序，每个图获得 7 维的特征向量，并将这些向量馈送到一个全连接层。

向量的第一个维度来自基于 BERT 的语义匹配模型。具体来说，算法通过遵循构造查询图 g 所采取的动作序列并将每个步骤所涉及的实体和关系的文本描述顺序添加到序列中，将 g 转换为标记序列。存在变量和 lambda 变量将被忽略。

向量的其他 6 个维度如下：第一个维度是查询图中所有已链接实体的累积实体链接得分。第二个是查询图中出现的链接实体的数量。第三到第五个分别是查询图中实体类型的数量，时间表达式和最高级的数量。最后一个特征是查询图的答案实体的数量。

不过，作者通过 BERT 将一个查询图序列化的方式是否合理，可能是值得讨论的。而其他 6 个维度是对查询图做一些简单的统计。

2.5 学习

为了训练模型，作者使用成对的问题及其正确答案，而没有任何参考的 ground-truth 查询图。遵循 Das 等人的框架，作者使用 REINFORCE 算法以端到端的方式学习策略函数，其中是我们想要学习的参数集，包括要更新的 BERT 参数和 7 维向量的全连接层的梯度。作者使用预测答案的 F1 分数作为奖励（reward）。

实验

本文的实验在三个数据集上进行：ComplexWebQuestions (CWQ)，其中超过 30% 的问题有 2-hop 关系和约束；WebQuestionsSP (WQSP)，仅有 0.5% 的问题有 2-hop 关系和约束；ComplexQuestions (CQ)，没有针对每个问题提供参考的查询图，大多数问题有 1-hop 关系。

可以说，作者研究的多跳，实际上主要是 2-hop 以内。