5. 查询图-语义解析-Semantic Parsing via Staged Query Graph Generation_Question Answering with Knowledge Base

• 论文原文：https://www.microsoft.com/en-us/research/publication/semantic-parsing-via-staged-query-graph-generation-question-answering-with-knowledge-base/

1. 简介

• 思想是把自然语言问题转化为逻辑形式，通过逻辑形式转化为查询语句，在知识库中查询得出最终答案。在进行语义解析生成逻辑形式的过程中，主要是在提取自然语言问题中的信息和利用训练好的语法解析器进行解析，这一过程几乎没有使用到知识库里的信息。而在向量建模和信息抽取方法中，我们不仅对问题进行了特征提取，还借助知识库确定了候选答案范围（相比语义解析中的词汇映射要在大范围的知识库实体关系中寻找映射，这样的方式使得搜索范围大大减小），并将候选答案在知识库中的信息作为特征。相比之下，可以看出传统的语义解析和知识库本身的联系是不够紧密的（Decoupled from KB），也就是说，传统语义解析方法对知识库的利用还不够。
• 其中语义解析的第一步，词汇映射（Lexicon）。要将自然语言中的谓语关系映射到知识库中的实体关系仅仅通过统计方式进行映射，效果并不好。如果能考虑知识库中的信息，即可将词汇映射的范围缩小，使用深度学习的办法通过分布式表达来代替基于统计方法的词汇映射，可能会取得更好的效果。
• 于是为了更好的利用知识库中的知识，缩小语义解析树的搜索范围，并获得更多有益的信息，提出本文。

2. 查询图

2.1 定义和组成

• 对于问句*“**Who first voiced Meg on Family Guy?"* (谁是第一个为Family Guy里的MegGriffin角色配音的人，注：Family Guy是美国的一部动画片，MegGriffin是其中的一个角色，有两个人先后为其配音过)

  对于深度学习的向量建模法来说，first这种时序敏感（Time-Aware）词常常会被模型忽略而给出错误答案。语义解析方法可以将first解析为逻辑形式的聚合函数（arg min），但它又难以将问题中的Meg这一缩写词通过词汇表映射为知识库中的MegGriffin。

  为了更好的利用知识库，我们可以先去知识库里搜Family Guy，在它对应的知识库子图中搜索和Meg很接近的实体，也就是说我们一开始就借助知识库，帮我们缩小了范围，这样我们就很容易找到Meg其实对应的是MegGriffin。我们可以借助这样的思想来对我们的语义解析进行改进。用一种图的形式来代替语法解析树表示逻辑形式，这个图被称为查询图（query graph）。

  问句“Who first voiced Meg on Family Guy?"对应的查询图如下图所示：

• 查询图的组成

  • 知识库实体：在图中用圆角矩形表示。
  • 中间变量：在图中用白底圆圈表示。
  • 聚合函数：用菱形表示。
  • lambda变量（答案）：在图中用灰底圆圈表示。

  图中实体节点到答案变量的路径可以转化为一系列join操作，不同路径可以通过intersection操作结合到一起，因此，该查询图在不考虑聚合函数argmin的情况下可以转化为一个lambda表达式，即：

  （上式表示 我们要寻找x，使得在知识库中存在实体y，满足 1. y和FamilyGuy存在cast关系；2. y和x存在actor关系；3.y和MegGriffin存在character关系，这里我们可以把y想象成是一个中间变量，通过对它增加约束来缩小它的范围，通过它和答案x的关系来确定答案x）

2.2 查询图的阶段生成

• 核心推导链（core inferential chain）：问题中的主题词（可以看作是一个根节点）到答案变量的这条路径（如Family Guy - y - x）包含了所有的中间变量，这条路径可以看作是从问题到答案的一个核心推导过程。而对于核心推导链里的中间变量，我们可以对它加一些约束（要求它与其他实体具有一定的关系，如 y - character -> Meg Griifin）和聚合函数（如 y - from -> arg min）。

• 故查询图生成可分为以下步骤：确定主题词，确定核心推导链，是否增加约束和聚合。可如下图这个有限状态机自动机表示：

  其中状态集合\(S=\{\phi,S_e,S_p,S_c\}\)分别表示空集、仅含主题词节点、含核心推导链、含约束节点。而动作集合\(A=\{A_e,A_p,A_a,A_c\}\)分别表示选择主题词节点、选择核心推导链、加入聚合函数、加入约束。

• 查询图可以分阶段生成，这个生成的过程实质上是一个搜索。依照我们的有限状态自动机，根据图所处的状态\(s\)，我们可以确定在该状态下可以采取的动作集合\(\Pi(s)\)（比如当前我们处在状态\(\phi\)，根据有限自动机我们的动作为选择主题词节点，假设检测出来问句有3个主题词候选，那么我们的动作集合大小为3）。因此，查询图生成过程实际上是一个搜索过程，如果对这个搜索不加任何限制，那么这个搜索是指数级复杂度的。因此对于每一个状态\(s\)，我们可以用奖励函数（reward function）对它进行评估，奖励函数\(\gamma\)得分越高表示这个状态对应的查询图和正确的语义解析表达越接近，我们用一个对数线性模型（log-linear）模型来学习奖励函数。有了奖励函数，我们用best-first的策略利用优先队列进行启发式搜索，算法流程如下：

  其中\(T(s,a)\)代表在\(s\)状态下采取动作\(a\)后得到的新状态，我们将优先队列的大小\(N\)限制为1000。上述算法可以简单概括为：每次从队列中取出得分最高的状态分别执行动作集中的每一个动作生成一批新的状态并压入优先队列，始终记录得分最高的状态，最终将得分最高的状态作为最后的查询图。

2.3 查询图生成举例

2.3.1 主题词链接（Linking Topic Entity）

• 从问题中确定主题词
• 作者使用了S-MART作为实体链接系统，该系统是针对带噪音的短文本设计的，适合用于对问句提取主题词，它会为相应的 实体-自然语言短语 链接对 给出链接得分（Linking Score）

2.3.2 核心推导链

• 对于每一个候选的主题词，将它在知识库中对应的实体节点周围长度为1的路径（如下图\(s_5\)和长度为2且包含CVT节点的路径（如下图\(s_3\)和\(s_4\)）作为核心推导链的候选（CVT，即复合值类型 Compound Value Types，是freebase中用于表示复杂数据而引入的概念）。如下图：

• 核心推导链其实就是将自然语言问题映射为一个谓语序列（如cast-actor），因此可以用卷积神经网络来对映射进行打分，如图所示：

• 将自然语言和谓语序列分别作为输入，分别经过两个不同的卷积神经网络得到300维的分布式表达，利用表达向量之间的相似度距离（如cosine距离）计算自然语言和谓语序列的语义相似度得分。

• 输入采用的是字母三元组（letter-trigram），类似于character-CNN。每个单词都拆分成几个 字母三元组，作为CNN的输入。比如单词who可以拆分为#-w-h, w-h-o, h-o-#。每个单词通过前后添加符号#来区分单词界限（并且单词最短只含一个字母，添加两个#可以保证能形成至少一个字母三元组）。

• 采用字母三元组的好处：

  • 1.减小输入维度，这样输入维度可以稳定在字母集大小+1(#号)的三次方，即\(27^3\)，而不是字典大小（同时可以处理一些字典中不存在的词和一些低频词，如缩写词等等）。
  • 相同语义的词语可能因为词根等缘故，前缀或者后缀会比较相似，这样能更好的提取单词语义的特征。
  • 对于现实生活中的用户，有时候可能会发生单词拼写错误，但错误拼写不会对这种输入方式造成太大影响。

2.3.3 增加约束和聚合函数

• 通过增加约束和聚合函数的方式来扩展查询图，缩小答案的范围，以增加准确率，如下图：

• 是否要为CVT节点添加约束节点和聚合节点：

  1. 约束实体出现在问句中
  2. 约束谓词表示事件的结束时间，但没有值（这表示它是当前事件）
  3. 问题中出现约束实体名称的一些单词
  4. 谓语是people.marriage.type_of_union（这说明关系是否是家庭伴侣关系、婚姻关系还是民事关系）
  5. 问句中包含单词 first 或者 oldest，并且谓语是from形式的谓语（表明事件的起始时间）
  6. 问句中包含单词 last, latest 或 newest ，并且谓语是to形式的谓语（表明事件的结束时间）

• 对于答案节点，如果包含以下之一的谓语，我们会增加一个约束节点：

  people.person.gender / common.topic.notable types / common.topic.notable_for

3. 奖励函数的特征定义

• 利用对数线性模型训练奖励函数，需手工定义一个特征向量来表征整个查询图的信息，将其作为对数线性模型的输入。

• 例如问题：“Who first voiced Meg on Family Guy?” 对应的查询图，它的特征如下图所示：

  • 从主题词链接、核心推导链、增加约束聚合三个方面定义特征。

    • 主题词链接特征：实体链接得分（EntityLinkingScore），由实体链接系统给出。例如：EntityLinkingScore(FamilyGuy,"Family Guy")=0.9

    • 核心推导链特征：

      1. PatChain：将问句中的主题词替换为实体符号，和谓语序列同时输入两个不同的CNN，根据CNN输出的表达求语义相似度作为特征。

         如: PatChain("Who first voiced Meg on ", cast-actor) =0.7

      2. QuesEp：将谓语序列和主题词的规范名称（canonical name）连接（concatenate）起来作为输入，和问题求语义相似度

         如: QuesEP(q,“family guy cast-actor”) = 0.6

      3. ClueWeb：用ClueWeb来训练一个更加in-domain的模型。如果一句话包含两个实体和谓语，那么就把这句话和谓语作为一组 数据对 输入模型进行训练。注意：ClueWeb的输入和PatChain是一样的，但是其模型是用不同数据训练的。

      从这定义的三个特征可以看出，这其实是一个ensemble模型，将三种模型的输出结果进行了一个log-linear组合。

    • 约束聚合特征：

      • 对于CVT节点，有以下特征：
        1. 约束实体是否出现在问句中 如ConstraintEntityInQ("Meg Griffin",q)=1
        2. 是否是当前发生的事件
        3. 是否是当前发生的事件，且问句中包含关键词“currently”, “current”, “now”, “present” 和“presently”
        4. 约束实体单词出现在问句中的百分比 如ConstraintEntityWord("Meg Griffin",q)=0.5
        5. 约束谓语的类型是people.marriage.type_of_union
        6. 问题中是否包含“first” 或 “oldest” ，谓语是from形式谓语，并且CVT节点按该from性质排序是第一
        7. 问题中是否包含“last”, “latest” 或 “newest” ，谓语是to形式谓语，并且CVT节点按该to性质排序是最后
      • 对于答案节点有以下特征：
        1. 性别一致性（男性）：约束谓语是gender，并且问句中出现了以下男性关键词中的一个{“dad”, “father”, “brother”, “grandfather”, “grandson”, “son”, “husband”}
        2. 性别一致性（女性）：约束谓语是gender，并且问句中出现了以下女性关键词中的一个{“mom”, “mother”, “sister”, “grandmother”, “granddaughter”, “daughter”, “wife”}
        3. 当约束谓语是 notable_types 或 notable_for 时，约束实体单词出现在问题中的百分比

    • 总体特征

      • 查询图对应的答案数量NumAns
      • 查询图的节点数NumNodes

4. 模型学习

• 根据查询图对应的实体和真实答案的F1-score进行排名。
• 基于lambda-rank算法对一个一层的神经网络进行训练。
• 好处：有些查询图虽然查询得到的答案和真实答案不完全相同，但根据它的相同程度（F1-score）也可以说它比完全错误的查询图要好。