《Query Graph Generation for Answering Multi-hop Complex Questions from Knowledge Bases》论文笔记
Query Graph Generation for Answering Multi-hop Complex Questions from Knowledge Bases
这是2020年SMU的Jing Jiang教授课题组发表在ACL上的一篇文章，主题为KBQA、Complex Question、Query Graph Generation
Overview
作者提到当前的复杂问题主要有两类特点：
- Questions with Constraints：问题中有一些限制，例如 “Who is the youngest president of US？”中的youngest就是额外的限制。
- Questions with Multi-hop relation：问题中包含多跳关系，例如 “Who is the wife of the founder of Facebook？” 中包含一个2-hop关系 wife_of和founder_of。
之前的一些工作都是分别独立地针对这两类特点进行研究，因此本文提出一种同时应对这两类特点的方法。作者改进了staged query graph的生成方法，允许更长的关系路径存在；并且，与之前先构建好relation path之后再添加constraints的做法不同，作者设计的模型能够同时处理constraint并extend relation path，或者说，作者把incorporate constraint的过程融进了relation path construction，使得两者能够同步进行。同时，这种同步考虑constraints的做法大大地减小了search space，作者提到如果把关系的长度延长到3-hop，那么每个问题平均要考虑10000条可能的relation path，这是很低效的。但是如果能够加入问题中的constraint，那么search space就会大大减小，效率能够得到提升。举个例子来说：原问题是 “Who is the first wife of TV producer that was nominated for The
Jeff Probst Show ? ”，如果我们单纯搜索所有"nominated for the Jeff Probst Show"的实体，那会有很多结果，但是如果加上限制"TV producer"，那就可以过滤掉很多结果。
Approach
Query Graph Introduction
作者首先概括介绍了什么是query graph。一张query graph包含四类结点：
- grounded entity ：这是在KB中存在的实体，也叫topic entity，query graph中至少有一个，在图中用阴影框表示。
- existential variable ：这是ungrounded entity，在query graph中可能没有也可能有多个，在图中用空白框表示。
- lambda variable ：用于表示答案结点，query graph中只能有一个，在图中用椭圆圈表示。
- aggregation function ：表示一些operation，比如argmin、argmax之类的，在图中用菱形框表示。
作者结合之前的工作总结了query graph生成的四步：
- 从topic entity（grounded entity）出发，找出从topic entity到lambda variable的core relation path。
- 将constraint添加到第一步找出的core relation path，这些constraint可能包含existential variable或者aggregation function
- 得到所有的candidate query graph，用每个candidate与question的进行相似度匹配，然后进行排序。
- 在KB中执行query graph并得到答案
Query Graph Generation
下面来看本文如何生成一张query graph，都以上面所提到的问题为例。
为了进一步减小search space，作者在提取候选query graph的时候使用了beam search。设tt时刻我们得到了top-K的query graph集合GtG_{t}，那么在t+1t+1时刻，对于任意的g∈Gtg \in G_{t}，作者对这张图采用三个操作中的一种：{extend,connect,aggregate}{extend,connect,aggregate}，这样我们就得到了一个新的query graph集合Gt+1′G^{'}{t+1}，然后再使用beam search得到t+1t+1时刻的query graph候选集合Gt+1G{t+1}。下面来看这三种操作分别代表什么。
Extend
这一步操作是通过增加一个relation来对query graph进行扩展，要分为两种情况：
- 如果当前的query graph只有一个grounded entity结点ee（没有lambda variable），那么就在KB中找到连接ee的relation rr，把rr添加到query graph中，并且记rr的另一端为lambda variable。
- 如果当前的query graph有lambda variable xx，那么我们把xx替换成existential variable yy，然后在KB中直接执行这张query graph找到yy的bindings，然后同样的把rr加入query graph，rr的另一端记为lambda variable xx。
Connect
问题中可能会有多个grounded entity，那么对于其他的grounded entity ee，我们考虑将它和lambda variable xx或者和与lambda variable xx相连的existential variable yy进行连接。做法依然是通过执行query graph找出对应的relation rr，然后connect。
Aggregate
这一步就是融合对constraint的处理，作者将question中的aggregation function识别出来，然后把它作为结点与lambda variable或者existential variable进行连接。
Query Graph Ranking
构建好query graph以后，下一步就是相似度匹配然后排序。作者对每张query graph构建了一个7维的特征vgv_{g}：
- 第一维：作者按照操作的顺序把query graph转化成文字描述，省略掉existential variable和lambda variable。例如上面的例子就会变成[the, jeff, probst, show, nominated, for, nominee][the,\ jeff,\ probst,\ show,\ nominated,\ for,\ nominee]。但是作者考虑到query graph中的词和原问题中的词可能会有较大差距，因此实际实验时，作者把query graph的text description与原问题文本进行了拼接。得到文本后用BERT-base进行编码得到第一维特征
- 第二维：accumulated entity linking scores of all grounded entities in the query graph. 这里我不是很清楚accumulated score表示什么
- 第三维：query graph中出现的entity数量
- 第四维：entity type的数量
- 第五维：temporal expression，这个我也不太懂是什么
- 第六维：superlatives，这个就是一些表示序数的词，比如youngest、largest之类的
- 第七维：答案实体的数量
对模型的训练作者使用强化学习的方法，BERT的参数也可训练。
Experiment
数据集：ComplexWebQuestons (CWQ)，WebQuestionsSP (WQSP)，ComplexQuestions (CQ)
本文的方法在三个数据集上均达到了SOTA。
消融实验
作者提到消融BERT并使用LSTM作比较的目的是证明它们的模型效果好并不是因为用了BERT。其次，对三种操作的消融表明extend操作是重要性最高的。
Reflection
这篇文章的创新点在于改进构建query graph的方法，同步考虑constraint，其实也就是aggregate操作，不仅对效果起到了3个百分点的提升，而且缩小了搜索空间，大大提升了效率。