写在前面
此论文为 2015 年的论文。 本文会出现一个名为谓语序列（predicate sequence）的名词，论文中没有详细说明。但是估计就是：一个实体至另一个实体的有向路径上的所有谓语的连接形式。如下文第一张图 Family Guy->cvt1->Mila Kunis 的谓语序列就是 cast-actor。
论文概要
论文地址 节选自摘要部分： > 论文提出了一个基于知识库问答的新的语义解析（semantic parsing）框架。首先定义一个类似于知识库的子图（subgraph）的查询图（query graph），可以直接映射到一个语义的逻辑形式（如\(\lambda\)-calculus）。所以语义分析简化为查询图的生成，并将其表示为一个阶段性搜索问题。然后通过使用先进的实体链接系统（Yang and Chang, 2015）以及深度卷积网络来实现问题与谓语序列之间的匹配。在 WEBQUESTIONS 的数据集上，F1 指标达到了 52.5% 的水平，高于以前的方法。
以下大型知识库已经成为支持开放领域问答的重要资源： - DBPedia - Freebase
最先进的 KB-QA 方法都是基于语义解析的，在语义解析中一个问题或者一种表达被映射到它具有一定意义的表示上（如逻辑形式，具体来说可以是 \(\lambda\)-calculus），即将自然语言映射为表达式，然后被翻译为一个 KB 查询。最后，只需要执行查询就可以检索问题的答案。但是大多数传统的语义解析方法在很大程度上都脱离知识库。由于没有前人的贡献累积，因此 QA 问题面临着一系列的挑战。例如： - 当在逻辑形式中使用与知识库中的谓语不同的谓语时，可能需要用到本体匹配（ontology matching）的问题（Kwiatkowski et al., 2013）。 - 即使表示语言与知识库的模式接近，从知识库中的大量词汇表中寻找正确的谓语与语句的描述相关联仍然是一个难题（Berant and Liang, 2014）。
由（Yao and Van Durme, 2014; Bao etal., 2014）的启发，该论文提出了一个语义解析框架，定义一个查询图可以直接地映射到由 \(\lambda\)-calculus 表达的逻辑形式。从语义上来讲，与 \(\lambda\)-DCS（Liang, 2013）十分接近。将解析行为分为 3 步： 1. 定位问题中的主题实体； 2. 找到回答与主题实体之间的主要关联； 3. （通过额外的约束扩大查询图，约束即回答需要附加的额外属性，如最早时间等）或者（答案与其他实体之间的关联）。
至此将一个语义解析问题划分成了一系列的子问题。例如 entity linking 和 relation matching。
文章内容介绍
- Sec. 2: 介绍了图知识库（估计就是知识图谱）的概念和查询图的设计；
- Sec. 3: 介绍了基于搜索方法的查询图生成；
- Sec. 4: 实验结果；
- Sec. 5: 论文中的方法和其他相关工作的比较；
- Sec. 6: 总结。
Knowledge Base
论文中的知识库 K 是一个包含主语、谓语、宾语的三元组（e1, p, e2）的集合，其中 e1 和 e2\(\in\)E，是一个实体。p\(\in\)P，是一个谓语。这种形式的知识库通常称为知识图谱。每一个实体是一个结点，两个相关联的实体由谓语标记的有向边连接，边的方向是从主语实体到宾语实体。如下图就是一个 Freebase 的子图： 
Freebase 中有一个叫 CVT（此链接需要翻墙访问） 的特殊实体类型，它不是一个真正的实体，而是用于收集事件或特殊的关联的多个字段。
Query graph
概念
给定一个知识图谱。执行逻辑形式的查询等价于寻找一个子图，该子图的表现形式可以映射到查询动作。之后解析绑定的变量。
接下来，以实体这个属性来表示真实世界的实体和 CVT 实体以及日期或高度等属性，这些实体之间的区别对于论文中的方法来说并不重要。
下图展示了一个查询图： 
上图是“谁第一次为 Family Guy 中的 Meg 配音？”的问题。MegGriffin 和 FamilyGuy 由圆角矩形表示，圆圈结点 y 表示应该存在一个实体来描述扮演关系，比如角色、演员和开始饰演此角色的时间。阴影圆圈结点也被称为 answer 结点。菱形结点 argmin 限制答案必须是扮演此角色的最早的演员。同样不含聚合函数的\(\lambda-calculus\)逻辑形式查询为$x.y.cast(FamilyGuy,y) actor(y,x) character(y,MegGriffin) $。在使用聚合函数之前，对 K 运行此查询图会匹配 LaceyChabert 以及 MilaKunis，请看第一张图。但是只有 LaceyChabert 是正确答案，因为是她最早开始扮演这个角色。
查询图的设计灵感来源于（Reddyet al., 2014），但是他的查询图是从问题的 CCG 解析中映射出来的，在映射到子图前还需要进一步的转换。从语义上来说，该论文的查询图更像简单的 \(\lambda-DCS\)。
生成
首先树图（tree graph）的根由一个实体结点组成，称为主题实体（topic entity）。其次，只有一个 lambda 变量 x 作为答案结点，从根到 x 有一个定向路径，其中含有 0 个或多个 existential variables。论文中将此路径称为图的核心推理链，因为它描述了答案和主题实体之间的主要关系。这个链除了根结点外只有变量结点。最后，可以将 0 个或多个实体或者聚合函数结点附加到每个变量结点，包括 answer 结点。例如，上图 Family Guy 是根，而 Family Guy->y->x 是核心推理链，分支 y->MegGriffin 阐述了角色，而 y->argmin 限制答案必须是该角色最早的参与者。 定义状态（state）集合\(S = \{\phi, S_e, S_p, S_c\}\)，其中每个状态可以是一个空的图（\(\phi\)），一个主题实体的单结点图（\(S_e\)），一个核心推理链（\(S_p\)）或者带有额外约束的更复杂的查询图（\(S_c\)）。 定义动作（action）集合\(A = \{A_e, A_p, A_c, A_a\}\)，其中\(A_e\)选取实体结点，\(A_p\)确定核心推理链，\(A_c\)和\(A_a\)分别约束和聚合结点。 给出一个示例\(q_{ex}\) = "Who first voiced Meg of Family Guy?"。
链接主题实体
从初始状态\(S_0\)开始，正确的操作是创建一个与给定问题中的主题实体相对应单结点图。例如，\(q_{ex}\)中可能的主题实体是 Family Guy 和 MegGriffin，如下图所示。 ![Two possible topic entity linking actionsapplied to an empty graph, for question “Who firstvoiced[Meg]on[Family Guy]？”](https://blog-content-1256924128.cos.ap-shanghai.myqcloud.com/Semantic%20Parsing%20via%20Staged%20Query%20Graph%20Generation%20Question%20Answering%20with%20Knowledge%20Base/Two%20possible%20topic%20entity%20linking%20actionsapplied%20to%20an%20empty%20graph,%20for%20question%20“Who%20firstvoiced%5BMeg%5Don%5BFamily%20Guy%5D？”.jpg)
使用的实体链接系统是专为短且有噪声的文本设计的，源于（Yang and Chang, 2015）。具体不做赘述，详情可参考相关论文。
确定核心推理链
给定与主题实体 e 对应的单结点图的状态 s，扩展该图的正确操作是确定核心推理链，即主题实体和答案之间的关系。下图展示了扩展\(s_1\)中的单结点图的三个可能的链。具体做法是，当中间的 existential variable 链接 CVT 时，探索长度为 2 的所有路径，如果没有链接，则探索长度为 1 的路径。
本节主要描述了如何确定核心推理链，不过上文一段先描述了如何确定候选的核心推理链。具体做法上一段也已经给出，但是由于原论文讲的也有点不清楚，此处加以说明，以下只是推测。 1. 扩展主题结点 Family Guy 的三个可能的核心推理链，应该是从知识库 K 中入手。请看第一张图，它是知识库 K 中的一张子图。从 Family Guy 中开始可以看到有三条边，两条边上是 cast，一条边上是 writer。由于两条边相同，于是就融为了一条推理链。至于最后一条推理链的谓语是 genre，可能是第一张图的子图中没有标出造成的。总而言之，那三条推理链就是从知识库 K 中获取。 2. existential variable 即 y，lambda variable 即 x。可以把知识库 K 中的 CVT 结点看作是 y，答案看作是 x。
这样做的目的是将自然表达映射到正确的谓语序列上。对于问题“Who first voiced Meg on [Family Guy]?”，需要衡量的是在{cast-actor, writer-start, genre}中每个序列（注：这个元组就是上图的三个候选核心推理链上的谓语）正确捕捉 Family Guy 和 Who 之间关系的可能性。因此将这个问题简化为使用神经网络测量语义相似度。
Deep Convolutional Neural Networks
虽然是陈述一个相同的问题，但是以语义等价的方式来重新表达该问题仍旧拥有巨大的多样性。并且还存在自然语言表达与知识库中的谓语不匹配的情况。为了处理上述两个问题，论文建议使用 Siamese neural networks（Bromley et al., 1993）来识别核心推理链（暹（xiān）罗神经网络，也可以叫连体神经网络。看见这个中文就很好理解了。Siamese neural networks 可以进行语义相似度分析，QA 的匹配等操作。详情可以先看看这篇博客）。注：由于上图可以得知一个问题可以获得几个候选得到核心推理链，这就是因为语言的多样性造成的，所以需要一个方法来识别一条最核心的推理链。 例如，将一个问题映射到一种模式上，方法是将实体替换为通用符号 <e>，然后将其与候选链比较。比如问题“who first voiced meg on <e>”和 cast-actor。该模型由两个神经网络组成，一个处理模式，一个处理核心推理链（这个模型说白了就是 Siamese neural networks）。两个神经网络都映射到 k 维向量作为网络的输出，最后使用距离函数（如余弦相似度）计算语义相似度。
该论文处理匹配问题使用了 CNN 模型。你可能会有点疑惑匹配问题是什么问题，前面压根就没提到过。是的，论文里也没说过，我只能猜测，这里的 CNN 其实就是上述模型的两个神经网络的具体实现。处理模型和处理核心推理链可能都用了 CNN 模型。另外论文中也没有说如何将核心推理链送入 CNN 中。论文中倒是稍微提了一下如何将问题送入 CNN 中，使用 word hashing 技术（Huang et al., 2013）。
增加约束和聚合函数
训练过程
Topic Entity：由实体链接系统返回的分数直接作为特征。 Core Inferential Chain：使用不同的 CNN 模型的相似度分数来衡量核心推理链的质量，以下为 3 个模型。 - PatChain：比较模式和谓语序列。 - QuesEP：将主题实体的名称与谓语序列拼接完成之后，将其与原问题比较。 - ClueWeb：使用 ClueWeb 语料库的 Freebase 注释训练 ClueWeb 模型
Constraints & Aggregations：当查询图中有约束结点，使用一些简单的特征来检查问题中是否存在单词可以与约束实体或者属性相关联。相似地，也可以使用一些预定义的关键字，比如“first”、“current”或者“latest”作为 argmin 结点的特征。 Overall：回答结点的个数和总结点个数也都作为特征。 比如下图，（1）属于 Topic Entity，（2）（3）（4）属于 Core Inferential Chain，（5）（6）（7）属于 Constraints & Aggregations，（8）（9）属于 Overall： 
实验
使用 WEBQUESTIONS 数据集，评价指标有：precision，recall 和 F1。其中 F1 的平均值作为主要的评价指标。
