A State-transition Framework to Answer Complex Questions over Knowledge Base

这篇是2018年北大发表在EMNLP上的文章，核心侧重于对query graph的构建。之前的方法不能很好的处理复杂问题，比如多跳推理等，因此本文旨在提出一个更好的query graph构建方式，叫做state-transition framework。

Complex Question

本文在introduction部分对复杂问题带来的挑战进行了总结概括，具体来说有以下几点：

1. Multi or implicit relation：多重或隐式关系。例如“Which Russian astronauts died in the same place they were born in?”，died in、born in这两个是显式的relation，而Russian、astronauts是隐式的关系。
2. Multi or no entities：多重或没有实体。例如“Which Russian astronauts were died in Moscow and born in Soviet Union”这句话中有好多实体，像Moscow、Soviet Union。 而 “Who died in the same place they were born in”这句话中就没有任何实体。
3. Variables and co-reference：简单问题中通常只有一个variable，比如wh词，但是“Which Russian astronauts died in the same place they were born in?”这句话中which、astronauts、place、they都是variables。同时，they和astronauts指代的东西相同，这也就是共指问题。
4. Composition：如果上面的各种challenges都出现了，那么问题就会很棘手，怎么构建出好的query graph或者logical form就成为了一个问题。

Overview

总的来说，这篇文章着重研究了怎么构建针对复杂问题的semantic query graph（SQG），方法叫做state-transition。拆开来看这两个词，state其实指的就是某个时刻下的query graph，或者说query graph某个时刻下的状态。而transition就表示不同状态之间进行转移，而转移是通过四种操作来完成的，后面会详细说。作者通过设计一个reward函数并训练一个SVM排序模型来判断最优状态。

此外，本文使用已有的entity linking algorithm外加作者自己设计了一个MCCNN（Multi-Channel CNN）模型来进行实体和关系的提取。

Semantic Query Graph Construction

给定一个问题$N$，我们希望构建出一张semantic query graph $Q^s$。

Node & Relation Extraction

在构建SQG的时候，node extraction和relation extraction是两个子任务，我们需要准确地提取出实体和关系。我们分别来看在本文如何解决这两个子任务

Node Extraction

对于实体抽取，作者一开始是直接使用BiLSTM + CRF，把它当作是NER任务，但是效果不好，因为文本处理的是复杂问题，因此问题都比较长比较复杂，直接使用BiLSTM + CRF不行。所以作者先使用了已有的entity linking algorithm来检测问题中可能的候选结点，得到它们的置信度（对于Freebase的算法叫做S-MART，对于DBpedia的算法叫做DBpedia Lookup），然后再使用BiLSTM + CRF得到最终的所有实体。

但是在实际操作过程中，作者发现有些实体是含有隐藏信息的，需要进行一些解释翻译。比如cosmonauts这个词，它是特指Russian astronauts。对于这一类词，作者又通过一些数据集训练出了一个字典$D^T$，将这种含有隐藏信息的词对应到一张sub-graph上去，这张sub-graph就可以理解为对这个词进行了一些解释。

Relation Extraction

对于关系抽取，作者参考借鉴了之前的模型，比如MCCNNs，设计出了MCCNN，当然此MCCNN非彼MCCNN，虽然很相似。本文的MCCNN有三个channel：

1. 第一个channel的输入：结点$v_i$和$v_j$在依存关系树中的简单路径
2. 第二个channel的输入：除去所有结点之后的问题信息，除去结点剩下的自然就是关系信息了
3. 第三个channel的输入：这个channel是为了解决一些隐式关系，作者把任意一对结点和它们的type作为输入。比如$v_i=China,v_j=actor$，那么输入就是"China-Country-actor-Actor"。

SQG Structure Construction

如何构建起SQG是本文的核心。在上一步我们已经提取出了所有的实体和关系，做好了准备工作。接下来我们来看不同的state之间到底是怎么转移的，那就需要介绍四种操作。

Operations

1. Connect：对于两个结点$u_i,u_j$，如果$\overline{u_i{u}_j}$能在我们提取出的关系中找到，那么就可以将这两个结点连接。

2. Merge：这个操作专门处理共指问题。对于结点$u,v$，将$u$ merge给$v$之后的新SQG可以表示为{V−{u},(E−Ed)⋃Ea}\{V - \{u\}, (E-E^{d}) \bigcup E^{a} \}{V−{u},(E−Ed)⋃Ea}。其中$E^d$就是所有$u$射出的边，KaTeX parse error: Undefined control sequence: \and at position 45: …line{uw} \in E \̲a̲n̲d̲ ̲w \ne v \}，简言之$E^a$相当于是把原来$u$到其他结点关系转给了$u$。

3. Expand：这个操作专门处理隐藏信息问题。对于结点$u$，该操作将它expand成一张sub-graph {Vu,Eu}\{V_{u},E_{u}\}{Vu​,Eu​}，然后新的SQG就是{V⋃Vu,E⋃Eu}\{V \bigcup V_{u}, E \bigcup E_{u}\}{V⋃Vu​,E⋃Eu​}。

4. Fold：这个操作专门处理那些多余无用或者说干扰词（参考图中的例子，compose和for这两个关系是无法识别的，但是musicComposer是我们能够识别的关系，因此soundtrack就是一个需要被删除的干扰词）。对于结点$u$，Fold操作会将它删去，但是保留它的所有关系，新的SQG可以表示为{V−{u},(E−Ed)⋃Ea}\{V - \{u\}, (E-E^{d}) \bigcup E^{a} \}{V−{u},(E−Ed)⋃Ea}，其中Ed={uvi‾∣uvi‾∈E}E^{d}\ =\ \{\overline{uv_{i}} | \overline{uv_{i}} \in E\}Ed = {uvi​​∣uvi​​∈E}，KaTeX parse error: Undefined control sequence: \and at position 62: …{uv_{i}} \in E \̲a̲n̲d̲ ̲\overline{uv_{j…。

Conditions

为了减小search space，作者对每一条操作添加了一条condition：

1. Condition for Connect：两个结点$v_i,v_j$能够被连接当且仅当依存关系图种两者的最短路上不存在其他节点$v^{\ast }$。这个其实比较好理解，如果还有其它结点，那$v_i,v_j$并不一定是有关系的。
2. Condition for Merge：结点$u,v$能够进行merge当且仅当其中一个结点是wh-word或者pronoun，能够co-refer另一个结点。
3. Condition for Expand：结点$u$能够被expand当且仅当$u$在$D^T$中。
4. Condition for Fold：结点$u$能够被fold当且仅当至少有一条关系没有出现在relation extraction的结果中。

下图展示了一个SQG的完整构建过程。

Learning the reward function

接下来，作者通过训练一个奖励函数$\gamma ()$来贪心地计算出每部操作后最优的状态。reward function的输入包含Node、Edges、Match三个方面的特征，Node、Edge特征都是利用先前的node、relation extraction模型来计算置信度然后取平均。当某一步操作后所有状态都不优于当前状态时，我们就得到了最终的状态$Q^s$

作者将奖励函数的任务看作是排序任务，通过SVM ranking classifier对它进行训练，ranking score定义为

这里的$F(A_i,A^{\prime })$是根据真实答案与$Q^s$匹配出的答案计算出的F1得分，至于怎么用$Q^s$在知识库中进行匹配，作者直接使用了NFF模型，因为这不是本文的重点。

Experiment

来看实验效果

效果是很不错的

Analysis

作者对他们设计的conditions进行了效果上和效率上的分析

效果上，提升是明显的

效率上，提升也是明显的

作者还进行了Error Analysis，并总结出主要有以下四类问题：

• SQG生成错误
• 没有找到实体：例子中就是没有loyalty这个entity
• 关系抽取错误：没有抽取full name， 而是抽取到了name
• 无法处理复杂的复合问题：例子中的问题其实是两个，需要先找到最矮的NBA球员，然后再找到对应的身高。

Reflection：

总结以下这篇文章：

1. 用entity linking algorithm + BiLSTM-CRF进行node extraction；设计出MCCNN进行relation extraction
2. 设计四种操作加条件构建SQG，设计reward function来学习出最优状态，用SVM ranking model来训练奖励函数
3. 采用的是深度学习的方法，不再使用手工特征

行relation extraction
2. 设计四种操作加条件构建SQG，设计reward function来学习出最优状态，用SVM ranking model来训练奖励函数
3. 采用的是深度学习的方法，不再使用手工特征

很复杂的一篇文章，读完以后最直接的感觉就是复现难度极大……