ACL 2018｜中科院软件研究所：基于端到端语义图生成的语义解析
作者：陈波，孙乐，韩先培
ACL 2018
基于端到端语义图生成的语义解析
Sequence-to-Action: End-to-End Semantic Graph Generation for Semantic Parsing
中国科学院软件研究所
Chinese Academy of Sciences
1 引言
传统的语义解析器大部分都基于组合文法， 如组合范畴文法（CCG）、 基于依存的组合语义文法（DCS）。这些语义解析器都利用文法来组合结构， 利用词典来进行语义落地，再利用特征对候选解析结果打分排序。然而，在面向开放域的情况下， 一般很难设计文法， 更难学习到高质量、高覆盖度的词典，此外，要想设计出有效的特征通常也很困难，并且模型的学习也不是端到端的。 为了解决上述问题，近年来语义解析领域内有两个备受关注的技术发展路线：基于语义图的方法，和基于序列-序列的方法。
基于语义图的方法 利用语义图来表示自然语言句子的语义（例如知识库中的一个子图），进而把语义解析转化为语义图匹配/生成的问题。 相比于逻辑表达式，语义图与知识库更加紧密相连，并且语义图的结构与句子的句法结构具有很多的共同点。 同时，来自知识库的结构约束和语义约束能够很好的在解析的过程中加以利用。 基于语义图的方法的最大挑战在于如何去构建一个句子的语义图。现阶段，语义图要么是利用特定的模板，再加上模板匹配而来, 要么从依存树或者句法树转化而来，或者通过启发式的算法。 这些方法都是基于人工设计的，或者启发式的构建过程，这使得这些方法很难处理开放域条件下的复杂句子。
近年来，循环神经网络（RNN）模型在序列-序列的问题上已经取得了很大的成功，如机器翻译、AMR分析，这得益于这类模型拥有强大的表示能力和预测能力。 也有不少工作把序列-序列的模型应用到语义解析任务上来， 这些工作利用循环神经网络模型把句子被解析成序列化的逻辑表达式。这样一来不再需要特定的文法，也不需要学习高质量的词典，更不需要定义有效的特征，并且模型的学习是端到端的， 此外，注意力机制可以用来学习句子中的词语与逻辑表达式中的谓词之间的软（soft）对齐。
在本文，我们提出了一种新的语义解析框架——Sequence-to-Action，该框架能够同时利用到语义图的强语义表示能力，以及循环神经网络模型的强表示学习能力和序列预测能力。 具体地，我们把语义解析问题建模成一个端到端的语义图生成的过程。如图1中的例子所示，对于给定的句子“Which states border Texas”， 我们的模型会把它解析成一个动作序列：[add_variable:A, add_type:state, ...]。为了达到上述目标，首先我们需要设计一个动作集合， 包括添加节点动作，比如：添加-变量节点（add_variable）、添加实体节点（add_entity）和添加类别节点（add_type）， 和添加边动作，如：添加-边（add_edge），还有添加操作符动作，如：添加-最大操作符（add_argmax）、 添加-最小操作符（add_argmin）、添加-计数操作符（add_count）等，该动作集合能够编码语义图的构建。 然后，我们设计一个循环神经网络模型来生成动作序列，该动作序列用于构建句子所对应的语义图。最后，我们还探究了在解码的过程中加入句法约束条件和语义约束条件， 用来及时过滤解码过程中的错误动作，进一步提高解析的准确度。
图1：我们方法的概览，其右侧是一个示例
之前基于语义图的方法都使用人工设定的、或者启发式的生成算法来构建语义图，相比如他们的方法，我们的sequence-to-action模型能够利用循环神经网络模型来生成动作序列， 而动作序列可以用来构建语义图，模型的训练是端到端的（end-to-end）。这样一个可以进行端到端学习的生成形式使得我们的方法更有有效，同时能够适应到更多的不同的情形。
而相比如之前的基于序列-序列（Seq2Seq）的语义解析方法，我们的方法使用循环神经网络模型来生成动作序列，而不是序列化的逻辑表达式。我们发现，我们所采用的动作编码形式 能够捕捉到更多的句法信息和语义信息，同时我们的编码方式更加的紧凑。此外，我们可以加入句法约束条件和语义约束条件来进一步增强语义解析。例如，在Geo数据集中， 动作add_edge:next_to（关系：接壤）必须满足如下语义约束条件：这条边所对应的两个节点的类别只能分别是state（类别：州）和state， 还必须满足如下句法约束条件：边next_to必须连接两个节点，以构成一个有效的图。
我们在三个公开数据集上进行了对比实验，这三个数据集分别为：Geo ，Atis 和Overnight 。 实验结果论证了我们方法的有效性：我们的方法在Atis和Overnight这两个数据集上都取得了现阶段最好的结果，在Geo数据集上也取得了很有竞争力的结果。
本文工作的主要贡献可以总结为以下两点：
1.我们提出了一个新的语义解析框架——Sequence-to-Action，该框架把语义解析问题建模成端到端的语义图生成过程。这个新的框架能够同时利用语义图的语义表示能力和循环神经网络模型的强序列预测能力。
2.我们设计了一个sequence-to-action的生成模型，和一个动作集合用来编码语义图的构建，还有一个循环神经网络模型用来生成动作序列。此外，我们还利用句法和语义条件约束来进一步增强语义解析。 实验结果也论证了我们方法的有效性。
2 端到端的语义图生成方法
给定一个句子
，我们的sequence-to-action模型将生成一个动作序列
，该动作序列将用于构建句子所对应的语义图。 图2展示了一个例子。我们的模型中，由X生成Y的条件概率
利用链式法则可以分解为如下形式：
其中
。
为了达到上述目标，我们需要：1）一个动作集合，该集合能够编码语义图的构建；2）一个编码器（encoder），该编码器把自然语言句子X转化为一个向量表示，和一个解码器（decoder），该解码器根据编码器传过来的向量表示来生成动作序列
。接着，我们将分别介绍这两部分。
图2：例子展示：一个句子，以及该句子所对应的语义图和用来构建该语义图的动作序列
2.1 用于语义图构建的动作集
通常，一个语义图有如下几个成分组成：节点（包括变量节点，实体节点和类别节点）、边（对应到语义关系）和一些通用的操作符（如，最大操作符、最小操作符、计数操作符、求和操作符等）。 为了构建一个语义图，我们设计了六种类型的动作，它们分别是：
添加-变量节点（Add Variable Node:）这类动作表示往语义图上添加一个变量节点。一般情况下，变量节点同时也是返回的节点（对应到疑问词：which, what）， 但也有可能是一个中间变量节点。我们使用如下形式来表示这类动作：add_variable:A，其中A是变量节点的标识ID。
添加-实体节点（Add Entity Node:）这类动作表示往语义图上添加一个实体节点。一个实体节点对应到知识库中的一个实体。我们使用如下形式来表示这类动作：add_entity_node:texas。
添加-类别节点（Add Type Node:）这类动作表示往语义图上添加一个类别节点，如（state，city)）。我们使用如下形式来表示这类动作：add_type_node:state。 实际上，类别节点本来与变量节点和实体节点是不同的，一个类别节点其实是包括一个表示类别的节点，和一条边，只是这条边的值都是一样的，都是类别Type，为了简化一个类别节点， 我们才设计成上面的那样子。
添加-边（Add Edge:）这类动作表示往语义图上的两个节点之间添加一条边。一条边对应到知识库中的一个二元关系。我们使用如下形式来表示这类动作：add_edge:next_to。
操作符动作（Operation Action:）这类动作表示往语义图上加一个操作符。一个操作符可以是：最大（argmax）、最小（argmin）、 计数（count）、求和（sum）、否定（not）等（复杂的情况还有比较（compare），这里我们先不考虑）。由于每一个操作符都有它的辖域， 为了表示一个操作符的辖域，我们定义为每一个操作符定义两个动作：一个开始操作符，表示如：start_operation:most，一个结束操作符，表示如：end_operation:most。 这两个操作符之间的动作序列所构成的语义子图就是该操作符的辖域。在显示的语义图上，我们用一个圈来表示该操作符的辖域。
参数动作（Argument Action:）由于上述的动作中有些类别的动作需要额外的参数信息，如，一条边add_edge:next_to是连接的哪两个节点。因此，我们分别为添加-类别节点（add_type）、 添加边（add_edge）和操作符（operation）设计了参数动作，并且参数动作总是跟在它的主动作的后面。
对于添加-类别节点（add_type）动作，我们添加一个参数动作，这个参数动作用来表明该类别是用来约束哪个节点的这个参数可以是变量节点，可以是实体节点。这类动作可以表示为：arg:A。
对于添加边（add_edge）动作，我们添加两个参数动作：arg1_node和arg2_node，用来表示该边连接哪两个节点。这类动作可以表示为：arg1_node:A和arg2_node:B。
对于不同的操作符（operation），我们又设计了不同的参数，对于求和操作（operation:sum），我们添加3个参数动作：arg-for、arg-in和arg-return， 分别用来表明求和操作所作用的节点，所统计的因素和返回的结果（一般为一个变量节点）；对于计数操作（operation:count）， 我们添加两个参数动作：arg-for和arg-return，分别用来表明所要计数的节点和返回的结果；对于最高级操作（operation:most），我们添加2两个参数动作：均为arg-for， 用来表明所作用的两个节点之间的边，并且这两个节点有先后顺序。
我们可以看到每一个动作都同时建模了句法和语义信息，这使得模型在使用这种编码形式的时候能够捕捉到更多的信息，同时这些信息与知识库保持着紧密的联系。另外，我们还发现使用动作序列的编码形式比直接序列化逻辑表达式的形式 更加的紧凑（详情参加4.3节）。
2.2 词语序列-动作序列的神经网络模型
基于上节介绍的动作编码，这一节我们介绍我们用于把句子解析成动作序列的编码-解码（encoder-decoder）模型。具体地，类似于Jia and Liang (2016)所使用的循环神经网络模型， 我们这里也利用基于注意力机制的序列-序列的循环神经网络模型。图3展示了该模型的示例图。
图3：基于注意力机制的用于生成动作序列的循环神经网络模型，附带一个添加约束条件的控制器
编码器（encoder）：编码器负责使用双向循环神经网络把输入的句子
转化为包含上下文信息的向量表示序列
。首先，每一个词
被映射成它的向量化表示，然后这些向量表示被输入到两个循环神经网络：一个前向循环神经网络（forward RNN）和一个后向循环神经网络(backward RNN)。 最后我们递归使用如下计算方式来生成隐藏状态的序列
：
其中我们采用长短记忆时记忆网络（LSTM）的形式来进行计算。最后，对于输入句子的每个位置
，我们定义它的带有上下文信息的向量化表示为：
。
解码器（decoder）：我们使用经典的基于注意力机制的解码器，该编译器依次生成一个动作，构成动作序列
。 在时间节点
，编译器基于当前的隐藏状态
生成动作
，接着基于
和
更新隐藏状态，得到
。这个编译器是由如下计算公式形式化定义的：
其中归一化后的注意力分数
定义了在输入的词上的概率分布，词上面的每一个概率值表示在时刻
在该词上的注意力集中程度，概率值越大，表明注意力越集中在该词上面。 另外，
是未归一化的注意力分数。
为了能够在解码的过程中加入约束条件，我们在模型中加入了一个控制器（controller），我们将在第3.3节详细介绍该控制器。
动作的向量表示：在上述解码器中需要每一个动作的向量化表示（
）。如前面介绍的，每一个动作都包含两部分：一部分是句法部分（如，add_edge），另一部分是语义部分 （如，next_to）。这样一来，动作与动作可能会共享句法部分或者语义部分。如动作add_edge:next_to和动作add_edge:loc就共享了句法部分，而动作add_node:A和 动作arg_node:A就共享了句法部分。为了减少参数的数量，尽量是参数不稀疏，我们先让每个句法部分和每个语义部分都单独具有它的向量化表示，对于一个动作， 我们把它的句法部分和语义部分的向量串联起来（concatenate）,组成该动作的向量化表示， 比如
add_edge:next_to）=[
add_edge
next_to）] 。其中动作的向量映射函数
通过训练学习而来。
3 带约束条件的神经语义解析模型
在这一节，我们将描述我们是如何利用sequence-to-action模型来建立一个语义解析器的。我们首先介绍我们如何训练我们的模型，以及如何进行推理（inference），接着介绍如何在解码的过程中加入句法约束条件和语义约束条件。
3.1训练
参数学习 我们模型的参数包括：循环神经网络模型的参数
、
和
，词向量映射函数
，和动作向量映射函数
。我们通过训练语料来学习这些参数。 给定一个训练样例（句子X和它所对应的动作序列Y），我们最大化X由生成Y的似然估计。我们的目标函数如下（对其最大化）：
我们使用标准的随机梯度下降算法来更新参数。
逻辑表达式到动作序列的转换 现阶段用于语义解析的语料大多都是以逻辑表达式来标注的。为了训练我们的模型，我们需要得到句子的语义图所对应的动作序列。 我们以语义图作为中间表示把逻辑表达式转换为动作序列（图3展示了转换的一个简单流程图）。具体地，首先我们利用深度优先的算法把逻辑表达式转换成语义图， 再使用相同的顺序从语义图生成动作序列。其中实体，变量和类别都是节点，关系是边。其中作为中间表示的语义图，我们是使用专门的数据结构来进行表示的，类似于函数-参数的形式， 边是函数名，节点是函数的参数，语义图上的一条边和两个节点对应到一组函数-参数的存储结构，整个语义图就对应到函数-参数的存储结构的一个序列，并且是要考虑该序列的顺序的。 一方面，我们可能需要句子利用句子的语义表示在知识库上执行计算，得到信息来辅助训练，另一方面由于语义图的形式，和动作序列的形式都不容易直接理解，为了方便分析，我们也需要句子所对应的逻辑表达式， 我们使用相同的策略，再从动作序列转换到逻辑表达式。
图4：逻辑表达式与动作序列之间相互转换的流程简介图
对于实体的处理机制 实体在语义解析中充当了十分重要的角色，之前的很多工作都直接使用手工实体词汇， 当然也有使用实体链接技术来实现句子中实体的语义落地的。在Dong and Lapata (2016)的工作中， 他们使用预处理的方式，先利用字符串匹配的方法把实体都识别出来，由于实体容易带来数据稀疏的问题（一般一个实体在语料中出现的次数会很少），他们用实体的类别和独有ID来表示实体。 如Texas会表示为State0。在Jia and Liang (2016)的工作中，他们使用神经机器翻译里面经常使用的复制（Copying）机制来处理实体（他们还需要一个实体词典）。 在本文中，我们都尝试并实现两种实体处理的机制，并在后面的实验中比较了这两种实体处理机制。
3.2推导
在测试的时候，给一个新的句子X，我们通过如下公式来得到它所对应的动作序列Y:
其中
的计算是利用[equation-5-1]计算而来。在解码的时候，我们使用了柱搜索（beam search）。我们可以从最优动作序列
得到相应的语义图和逻辑表达式。
3.3 在解码中加入约束条件
在解码的时候，我们依次生成一个动作。显然，动作与动作之间是有很强的关联的，也就是说下一个动作与当前生成的语义子图是有关联的，有一些动作明显是错误的，可以利用句法约束条件和语义约束条件来进行刷选。 已经有工作证明了句法和语义约束条件可以用来增强语义解析。在本文我们也利用句法和语义约束条件，具体的，我们设计了一个控制器，该控制器读入已经生成的动作序列，并构建语义子图， 然后利用如下的句法约束条件和语义约束条件来对动作进行过滤，把违背约束条件的动作滤掉。
句法约束条件 句法约束条件是为了保证生成的动作序列可以构成一个连通的无环图，这是因为语义图一般是连通的，也是无环的。比如，没生成一个添加边的动作，该边都必须有两个不同的节点作为它的参数， 图5中，作为下个动作的候选动作中第三个动作就是违背了这条约束规则，它的两个参数节点是一样的，会导致生成的图有环，不符合语义图的要求。这种类型的约束条件是领域无关的，并且是通用的。 我们在控制器中通过若干条规则来建模句法约束条件。
图5：使用约束条件来过滤错误动作的示例
语义约束条件 语义约束条件是为了保证生成的语义图符合知识库本体模板框架（schema）的约束。具体的，我们建模了两类语义约束条件，一类是选择约束（selectional preference）， 这种约束条件是确保生成的语义图中边的两个参数（节点）的类型必须符合知识库中本体模板框架（schema）中类型的约束。比如，在Geo数据集中，边next_to（关系：接壤）的两个节点参数的类型均是state（州）。 图5中，作为下个动作的候选动作中第二个动作违背了这条约束规则，由于边loc（关系：位于）的两个参数节点类型可以分别是city（类别：城市）和state（类别：州），而例子中， 第一个参数节点（变量节点A）的类型是state（类别：州），而第二个参数节点（实体节点texas:st）的类型也是state（类别：州），这就违背了选择约束。 第二类约束是类别不冲突约束条件，这种约束条件保证每个节点（可以是变量节点，也可以是实体节点）的类别不冲突，比如说一个节点的类型不能同时是city（类别：城市）和state（类别：州）。 图5中，作为下个动作的候选动作中第一个动作违背了这条约束规则，由于这个动作是在实体节点texas:st加一个类别节点（city），而实体节点texas:st的类型已经是state（类别：州）了， 这就违背了节点的类型不冲突约束条件。语义约束条件是领域相关的，不过我们可以从知识库中自动抽取出这类约束条件。在控制器中，我们同样使用若干条规则来编码语义约束条件。
4 实验
4.1 实验结果与分析
对于我们的模型，我们有三种不同的设置，一种是最基本的sequence-to-action模型，没有使用任何约束条件的——Seq2Act；第二种是加上语法约束条件的——Seq2Act (+C1)； 第三种是同时加上语法约束条件和语义约束条件的Seq2Act (+C1+C2)。我们没有设置单独加语义约束条件的，这是因为我们所使用的语义约束条件是在符合句法约束条件的基础上添加的，如果一个语义图不符合句法约束条件， 再来谈语义约束条件是没有意义的。在三个数据机上的结果分别在表1和表2中展示，两个表格中带*号的系统表示该系统有使用额外的语料或资源。从结果我们可以看到：
表1： Geo数据集和Atis数据集上的测试结果
表2：在OVERNIGHT数据集上的测试结果
1）通过同时利用语义图的语义表示能力和循环神经网络模型的表示学习能力以及对序列问题的强预测能力，我们的方法（Seq2Act (+C1+C2)）在Atis数据集和Overnight数据集上都取得了当前最好的结果， 同时在Geo数据集上也取得了与最好成绩不相上下的结果。具体的，在Geo数据集上，我们完整的模型Seq2Act (+C1+C2)在相同的设置条件下取得的结果（88.9的准确率）也是最好的，只落后于两个系统， 一个是Liang et al. (2011)*，该系统有使用额外的人工定义的词汇；另一个是Jia and Liang (2016)* ，该系统使用数据重组（data recombination）的方式对训练语料进行了扩充。 在Atis数据集和Overnight数据集上，我们完整的模型分别取得了85.5和79.0（八个领域的平均准确率）的准确率，都是当前最好的结果，甚至比有利用额外训练语料的Jia and Liang (2016)*结果要好。
2）相比之前的序列-序列（Seq2Seq）的模型中所使用的序列化逻辑表达式，我们所使用的动作序列编码更加有效。在三个数据集上，我们最基本的系统Seq2Act的结果比Seq2Seq模型都要好。在Geo数据集上，Seq2Act的准确率是87.5， 而Seq2Seq模型中最好的结果是87.2；在Atis数据集，Seq2Act的准确率是84.6，与Seq2Seq模型中最好的结果一样；在Overnight数据集上，Seq2Act的准确率是78.0，而Seq2Seq模型中最好的结果是77.5。 我们认为这是因为我们所采用的动作序列编码更紧凑，另外能够编码更多的信息，特别是同时编码句法信息和语义信息（这点与所使用的基于CCG的词汇有点类似）。
3）句法约束条件能够基于保证语义图结构有效原则对候选动作进行刷选，及时过滤违背该约束的动作，这样一来能够有效提高语义解析的性能。在三个数据集上，有使用句法约束条件的系统Seq2Act (+C1)比最基本的系统Seq2Act都有所提高。
4）语义约束条件能够进一步的提高语义解析的性能。在三个数据集上，我们完整的模型Seq2Act (+C1+C2)的结果都超过了Seq2Act和Seq2Act (+C1)的结果。我们认为这是因为我们利用选择约束和类别不冲突约束，能够在解码的时候， 及时过滤掉违背这些约束条件的错误的动作候选，从而提高了最终结果是准确的可能性。
4.2 详细分析
对比两种实体处理机制 在前面章节已经提到，我们实现了两种实体处理机制，一种是基于替代（Replacing）的机制：把实体替换成实体的类别加上独有的ID； 另一种是基于复制（Copying）的机制。为了对比两种实体处理机制，我们用我们的完整模型分别利用两种实体处理机制进行了对比实验，实验结果如表3所示。 我们可以看到在三个数据集上，基于Replacing的实体处理机制比基于Copying的实体处理机制的效果都好。我们认为这是因为Replacing是在预处理中处理的，能够有效消除由实体带来的稀疏问题； 而Copying是存在于训练和测试中的，并且需要额外的Copying机制，详情参见。
表3：在三个数据集上对比两种实体处理机制的结果
对比线性化的逻辑表达式和动作序列 之前的Seq2Seq模型直接使用线性化的逻辑表达式作为目标端的序列，我们使用动作序列作为目标端的序列，表4中显示了两者的平均长度。我们可以看到， 动作序列比线性化的逻辑表达式更加的紧凑：相比线性化的逻辑表达式，动作序列更短，在三个数据集上，长度分别减少了35.5%、9.2%和28.5%。在Overnight数据集上，我们对8个领域分别统计，在进行平均。 这种更短/更紧凑的编码方式能够稍微减缓一下目标端长距离依赖的问题，并且也有利于学习自然语言句子与目标端的语义表示之间的对齐。
表4：在三个数据集上线性化逻辑表达式和动作序列的平均长度
4.3错误分析
我们在错误的样例上进行了错误分析，我们发现有两类错误比较显著，也应该引起我们的注意。我们在表5中展示了几个错误样例，每个例子由三部分组成：句子、正确的逻辑表达式和我们模型预测的逻辑表达式， 另外我们用红颜色标记了错误的地方。这两类错误如下：
表5：错误分析样例
未出现/不正式的句法结构 有些测试样例有没有在语料中出现过的句法结构。表5的第一个例子中，句子的这种句法结构并不常见， 实体词“Iowa”和关系词“borders”都出现在疑问词“how many”之前，正常的形式应该是：“How many states does Iowa border?”。 对于这种问题，我们可以尝试利用句子重写或者复述的方法把有不常见句法结构的句子转换成有常见句法结构的句子。
匹配遗漏（Under-Mapping）像我们所使用的基于注意力机制的循环神经网络模型并没有考虑对齐的历史，当前的注意力分布并没有把之前的注意力分布考虑进行， 这样容易造成源端的有些词语并没有被注意力集中到，从而导致某些词语没有匹配到，出现匹配遗漏的情况，如表5中的第二个例子，“first class”就被忽略了，本来它是要映射到(class_type x first:cl)的。 这类问题在神经机器翻译中也很常见，类似的，我们可以利用注意力覆盖度的机制来处理这种问题。
5 总结
本文同时从语义落地和结构预测两个方面来研究语义解析。针对现有语义解析方法过于依赖于高质量词典、 特定文法和人工定义特征的问题，我们提出了一种端到端语义图生成的语义解析方法。该方法同时利用了语义图的表示优势， 和循环神经网络模型的强序列预测能力。具体的，我们将语义解析问题转换为自然语言句子序列到语义图构建的动作序列的翻译问题， 我们使用循环神经网络模型来建模动作序列的生成。相比于传统语义解析方法，该方法使用语义图来表示句子的语义，不再需要特定文法； 相比于新兴的语义解析方法，该方法使用动作序列来编码语义图的构建，循环神经网络模型来建模动作序列的生成，该过程不再是启发式， 是端到端的，同时在解析的过程中能够考虑到动作与动作之间的相互联系，能够方便地加入句法和语义约束条件，进一步提升语义解析的准确度。 最后，我们在三个公开数据集上进行了实验，实验结果论证了我们方法的有效性。