论文解读：Query Graph Generation for Answering Multi-hop Complex Questions from Knowledge Bases（2020ACL）
简要信息：
序号 | 属性 | 值 |
1 | 模型名称 | - |
2 | 所属领域 | 自然语言处理 |
3 | 研究内容 | KBQA |
4 | 核心内容 | Beam search；Query Graph Generation |
5 | GitHub源码 | |
6 | 论文PDF |
一、摘要：
先前的工作关于从知识库中回答复杂的问题通常单独处理两类复杂的问题，分别是包含限制条件的问题和含有多跳推理的问题。本文目标是同时处理这两类问题。我们发现较早的将限制条件加入到查询图中可以有效地缩减搜索空间，受到该发现的动机，我们提出一种新的可编辑查询图生成方法（modified stage query graph generation），通过更加灵活的方法生成查询图。我们的方法在三个基准数据集上达到最有效果。
二、动机：
- 先前的KBQA工作关注于简单的问题和单跳推理，但现实中，问题往往很复杂。我们总结了两种复杂问题类型，包括：
（1）single-relation questions with constraint：问题的答案（answer entity）与主题词（topic entity）是单跳关系，但其包含一些限制条件，例如“the first”、“in two years”等。这一类问题的解决方法称为staged query graph generation method，其旨在首先识别出问题的答案与主题词之间的关系（即relation detection），其次在所有与主题词有该关系相连的候选的答案中根据约束条件进行筛选，最终形成一个查询图。
（2）Questions with multiple hops of relations：给定的问题对应的答案与主题词之间存在多跳关系。回答此类问题，通常需要多跳推理，即从主题词开始寻找一条到达答案实体的路径。事实上，随着跳数的增加，搜索空间也在不断上升，因此如何降低搜索空间？一种方法是使用集束搜索（beam search）。
- 我们发现现阶段的工作没有同时解决这两个问题，因此本文，我们同时处理包含限制条件和多跳关系的问题。我们提出一种方法同时将限制条件和关系路径推理结合起来。
三、方法：
问题定义：给定一个知识库，其由一系列三元组构成。给定一个问题 Q ，任务的目标是从知识库中寻找答案。
3.1 staged query graph generation method
查询图包含四种类型的结点：（1）grounded entity：表示KB中存在的实体；（2）existential variable：代表虚拟的结点，该结点只代表一个变量；（3）lambda variable：表示候选答案对应的变量；（4）aggregation function：一种操作函数，包括argmin、count等。一种查询图如下图所示，可知，查询图类似于一种模板，根据答案生成的查询图之后去知识库中做匹配。
因此，staged query graph generation method可以概括分为四个步骤：
- step1：从grounded entity（即主题词）开始寻找一条查询路径；
- step2：在每一条路径上，识别出相应的限制条件，限制条件可以是一个新的grounded entity实体，也可以是对应一类aggregation function；
- step3：根据前两步得到的许多查询图，根据其与答案的相似度进行排序；
- step4：执行最相关的查询图，并从KB中进行匹配以获得答案；
问题动机：
- 作者发现，如果完全将这个方法用在多跳+约束类的问题上，很难有效生成查询图，且随着路径的变长，搜索空间或非常大。例如当跳数达到3个时，候选的路径数量会超过10000个；
- 现阶段解决这问题的有集束搜索（beam search），但他们没有考虑到约束条件。我们发现，当在集束搜索中考虑到了约束条件时，可以进一步缩减空间，也可以指导查询正确的路径。
3.2 查询图生成
我们的方法是同时考虑约束条件和多跳路径查询两个方面，在多跳路径查询时使用集束搜索，每次搜索时融入约束条件以缩减搜索空间。每一跳相当于一次迭代：
**查询图生成的迭代步骤：**假设在第 t 次迭代，生成了 K 个查询图（K即为beam search的大小），记做 ，则在第 t+1 时，对于每一个查询图
我们从 extend、connect和aggregate三个动作中挑选一个动作用于对
进行扩张（扩张是指在此基础上添加一个边和一个节点， 三个动作对于三种扩张方式）。对于第 t 次迭代生成的所有查询图都分别执行这三个动作，形成
(可知此时查询图数量是t时刻的3倍)。随后对这些查询图使用打分函数进行排序，并挑选分值最高的 K 个，最终形成 t+1 时刻的查询图
。一直迭代下去使得得分不再身升高。
根据先前工作描述，这里的三种扩张动作：
- extend：增加关系路径，只有该动作是增加多跳路径的长度的
- connect：将其他的grounded entity或lambda variable连接到CVT结点（existential variable），该动作主要用于实体约束
- aggregate：将aggregate function添加到lambda variable或CVT结点上，该动作主要将函数加入到约束中
为了保证多跳，本文允许extend动作在connect和aggregate动作之后执行
3.3 查询图排序
最后一次迭代，将所有的查询图进行特征提取。作者设计了7个特征，分别有：
- BERT-based semantic matching：将查询图对应的动作序列以及整个图的实体/关系的token序列进行表征。例如上图(a)对应的序列为（the, jeff, probst, show, nominated, for, nominee）；
- entity link score：实体链接工具提供的打分；
- grounded entity number：该类实体在当前查询图中的个数；
- entity type number：实体类型的种类数
- temporal expressions number：模式数量；
- superlative number；
- answer entity number：答案数量；
最终7个特征喂入一个全连接层并进行打分。在训练过程中，由于每个查询图并不知道哪个是ground truth，因此选择使用策略梯度进行训练，其中奖励函数为预测的答案为ground truth的F1值。（训练的方法详见论文：《Go for a walk and arrive at the answer: Reasoning over paths in knowledge bases using reinforcement learning》）
四、实验
实现细节：
- 使用现有的实体链接工具、实体类型工具等完成question与KB的链接；
- 初始化BERT base模型，dropout=0.1，hidden size=768，层数为6，多头注意力头数为12，将Freebase作为知识库，beam search大小 K=3。
- 数据集使用ComplexWebQuestions（CWQ）、WebQuestions（WQSP）和ComplexQuestions（CQ）
- Freebase知识库下载地址：https://developers.google.com/freebase/
实验结果：
（a）为数据集的统计；（b）为本文的模型与baseline的对比，（c）为消融实验
错误分析： 作者随机挑选100个错误的样例并进行分析：
- ranking error：有一些relation很难被识别检测，导致查询图的排序出现错误。例如一些表达关系的词存在简写，比如““Who was VP for Nixon?”文具中，“VP”表达的是“vice president”，但很那被理解，因此这部分需要引入外部知识来辅助；
- topic linking error：实体链接工具对主题词链接产生的误差；
- generation limitation：查询图生成的方法有限，导致有一些问题无法生成查询图（这个说明了当前的查询图方法还是有限的）
五、总结
优势： 本篇文章主要的工作切入点是在生成查询图时，如何尽可能的缩小搜索空间的同时，运用约束条件和集束搜索同时解决复杂约束和多跳的KBQA，而对查询图的排序则使用简单的神经网络打分实现，因此该方法的解释性很强（查询图的每一步迭代生成是确定的三种动作规则）；
缺点： 泛化能力有限，虽然能够解决作者提出的问题，但是对于查询图的生成是过于规则化，泛化能力有限；
相关博客： 实践案例丨ACL2020 KBQA 基于查询图生成回答多跳复杂问题