成分句法分析综述（第二版）(一）-阿里云开发者社区

介绍

成分句法分析近年来取得了飞速的发展，特别是深度学习兴起之后，神经句法分析器的效果得到了巨大的提升。一般来说，句法分析器都可以分为编码模型和解码模型两个部分。编码模型用来获取句子中每个单词的上下文表示，随着表示学习的快速发展，编码模型也由最初的LSTM逐渐进化为了表示能力更强的Transformer （VaswaniSPUJGKP17）。而解码模型方面，也诞生了许多不同类型的解码算法，比如基于转移系统（transition-based）的解码算法（WatanabeS15, CrossH16, LiuZ17a），基于动态规划（chart-based）的解码算法（SternAK17, KleinK18）和基于序列到序列（sequence-to-sequence）的解码算法（BengioSCJLS18, Gomez-Rodriguez18）等等。

基于转移系统的句法分析模型主要通过预测生成句法树的动作序列来还原出一棵句法树。按照遍历树的顺序，具体还可以分为自底向上（bottom-up）的转移统（CrossH16），自顶向下（top-down）的转移系统（WatanabeS15）和基于中序遍历（in-order）（LiuZ17a）的转移系统。基于转移系统的句法分析模型优点是速度快，因为它解码的时间复杂度是线性的。而缺点就是在解码的时候无法考虑短语的边界信息，这会导致解码的精度上相比于基于动态规划的模型稍微差一点。

基于动态规划的句法分析模型主要通过递归地预测每个短语得分最高的子短语，最后回溯还原出最优句法树。优点就是可以枚举出搜索空间中的所有句法树，解码效果比较好。但是动态规划算法时间消耗较大，复杂度是句子长度的平方级别的。所以针对这个缺点，又提出了近似的自顶向下的贪心解码算法（SternAK17），按照句法树的前序遍历顺序进行搜索，在不损失太多性能的前提下，能大大加快解码的速度。

基于序列到序列的句法分析模型主要思想就是将句法树映射为一个唯一对应的序列表示，然后通过序列标注（Gomez-Rodriguez18）或者序列生成（VinyalsKKPSH15）的方式来预测出这个序列。根据句法树序列化的不同定义方式，模型也有许多不同的变体。这一类模型的优点就是速度极快，因为时间复杂度也是线性的，并且模型参数量比基于转移系统的模型少了很多。缺点也是显而易见的，由于预测出的序列需要有很强的约束，不然不能保证可以还原出一棵完整的句法树，所以最终的效果也没有前面两种模型理想。

此外还有许多其他类型的解码算法，比如直接利用神经网络来预测语法产生式的概率，模拟上下文无关文法，最后再利用传统的CKY算法来进行解码（TengZ18）。该模型最终也取得了非常不错的效果，在单模型上的结果超过了之前的几种模型。

成分句法分析可以应用到许多下游任务中去，比如情感分析任务中，可以采用树状LSTM（Tree-LSTM）来对句子的句法树进行建模，从而分析出句子的情感（ZhuSG15）。也可以应用到其他基础任务中去，比如可以将训练好的成分句法树根据规则转化为依存句法树，从而提升依存句法分析的准确率（Gildea04）。

任务定义

成分句法分析是自然语言处理中的一个基础任务，它的任务是给定一个长度为 n 的句子，分析出句子的短语结构句法树 t 。例如给定句子“The little boy likes red tomatoes .”，它的成分句法树如图1所示。

图1：句子“The little boy likes red tomatoes .”对应的句法树。

对于句法树 t ，有多种方式来对它进行表示。目前比较常用的是基于跨度（span）的表示（CrossH16），也就是将句法树表示成组成它的所有短语的集合。而对于每个短语，可以用三元组来表示它，其中 j 和 i 表示这个短语的范围是从单词 wj 到 wi ，而 l 表示这个短语的非终结符标签。这样句法树 t 就可以表示为三元组的集合：

这样预测句法树的任务就可以转化为预测三元组集合了。

当然一般还存在两个小问题，一是如果存在一元产生式怎么办？一种解决方法就是将一元产生式上面的所有非终结符全部拼接成一个新的非终结符，这样整个一元产生式就可以看成一个非终结符了。另一个问题是句法树不一定是二叉树，那么解码的时候就会增加许多搜索的复杂度。解决方法就是新增一个空的非终结符，将非二叉产生式全部转化为多个二叉产生式，其中新增加的临时结点的非终结符全部定义为这个空的非终结符，在还原句法树的时候直接忽略它就行了。

编码模型

给定句子，编码模型的目的就是获得每个单词的上下文表示，并进一步计算出每个短语的向量表示。在实际实现中，一般将单词 xi 的输入向量分为三部分。首先是它对应的随机初始化的嵌入向量 ei 。然后是这个单词的词性对应的随机初始化的嵌入向量 pi ，一般它的词性可以通过外部词性标注器来得到。最后是这个单词的字符级别表示 ci ，这个一般可以通过字符级别的CNN或者LSTM来得到。最后将三部分向量拼接得到最终的输入向量 xi ：

然后将输入向量送入编码器，得到每个单词的上下文表示。而根据采用的编码器的不同，又可以将编码模型分为以下几种主要类型。

LSTM编码

这是最为常用的一种编码方式了，首先将所有 xi 输入到双向LSTM中，得到每个位置的前向隐层表示和后向隐层表示。然后对于短语，它可以表示为：

这样就得到了短语的向量表示，接着就可以计算出它的得分，然后利用解码模型解码出最优的句法树。

Transformer编码

虽然LSTM编码用的最多，但是要问最近这段时间最火的模型是什么，那当然是Transformer了（VaswaniSPUJGKP17）。它可以充分利用GPU的并行计算优势，加快计算速度。还可以利用注意力机制，增强对句子的表示能力。

图2：Transformer结构。

Transformer的输入有三个，查询（query）向量矩阵 Q ，键（key）向量矩阵 K 和值（value）向量矩阵 V 。输出就是查询向量对每个键向量的注意力，然后对值向量加权求和的结果。用矩阵形式表示就是：

当然还可以加入多头（multi-head）注意力机制，增强表示能力，具体这里不再赘述，可以参看原论文。最后将输出乘以参数矩阵 W0 映射回需要的输出维度，得到最终的输出矩阵 H ，具体结构如图2所示。

在本文中， Q ， K 和 V 三个矩阵都是通过对句子的输入向量拼接而成的矩阵 X ，分别乘以参数矩阵 WQ ， WK 和 WV 得到的。但是要注意的一点是，在此前的输入向量 Xi 的基础之上，还得再拼接上每个单词的位置向量 pi ，不然矩阵运算会丢失单词的位置信息。

得到输出矩阵之后，接下来计算短语的表示方法和LSTM编码是类似的。

递归神经网络编码

递归神经网络在自然语言处理中的应用最早是在（SocherBMN13）中提出的。虽然当时取得了不错的效果，但是近些年来递归神经网络已经很少有人使用了，主要因为它存在梯度消失，需要句法树等问题，并且它的初衷（编码树结构信息）由循环神经网络LSTM基本也可以学到，所以没有必要用这种不能并行的网络结构。

对于短语，如果它的两个儿子结点和，那么就可以由和计算得到：

其中， f 是激活函数，一般可以取 tanh 。

当然这种结构现在已经很少使用了，现在用的较多的递归结构是树状LSTM，网络结构和递归神经网络基本相同，唯一的区别就是将计算单元 f 替换成LSTM中的隐层单元，这样可以有效地解决梯度消失和长距离依赖的问题。

得分计算

采用以上几种编码模型得到了每个短语的向量表示之后，接下来可以用两层前馈神经网络计算出它的得分：

其中 f 是激活函数，这里通常取 RElU 。这里我们将短语的得分分成了两部分，一部分是它的非终结符的得分，一部分是跨度的得分

最后，定义一棵句法树的总得分为它包含的所有短语的标签得分与跨度得分之和：

而接下来要介绍的解码模型的任务，就是去寻找一棵句法树，使得它的得分最高。

基于转移系统的解码算法

基于转移系统的解码模型主要分为三种。第一种是自底向上的转移系统，第二种是自顶向下的转移系统，最后一种是基于中序遍历的转移系统。这些转移系统的共同点是都包含两个组成成分，一个是栈（stack），用来存放已分析的句法结构，另一个是缓存（buffer），用来存放待分析的句子。而预测句法树结构就转化为了预测转移系统每一个时刻应该采取的动作（action）序列。下面我们分别介绍几种不同的转移系统，我们用三元组来表示转移系统每一个时刻的状态，分别代表栈顶元素、缓存的第一个单词和句法分析结束标志。

自底向上的转移系统

自底向上的转移系统是根据句法树的后序遍历（post-order）顺序进行句法分析的，首先将缓存中的单词移进栈里，然后将栈顶的若干个单词归约为它们的父结点，直至最后缓存为空并且栈里只有一个根节点。

图3：自底向上的转移系统动作定义。

自底向上转移系统的动作形式化定义如图3所示，其中移进（SHIFT）动作就是将缓存里面的第一个单词移进栈里。归约（REDUCE-L/R-X）动作就是将栈顶的两个元素出栈，并且归约为它们的父结点X，然后再将父结点入栈，而L和R就是用来区分左儿子和右儿子谁是头结点。一元（Unary-X）动作就是将栈顶元素出栈，并且归约为父结点X，这个动作是用来预测一元产生式的。最后完成（FINISH）动作用来判断句法分析是否结束。

注意到这里有一个问题，自底向上转移系统一般要提前对句法树进行二叉化。主要原因是因为自底向上系统有个弊端，就是在不停地移进之后，你不仅要预测哪一步开始归约，还得预测归约的话要归约栈顶的多少个元素，这样预测的状态数就大大增加，导致训练时间也增加了许多。而二叉化后每次预测就只需要预测哪一步归约就行了，每次归约只归约栈顶的两个元素。

图4：自底向上的转移系统的一个例子。

对于图1中的句法树，用自底向上转移系统分析的过程如图4所示。

自底向上转移系统的优点就是可以充分利用已经生成的子树信息，来帮助父结点的非终结符预测。但是缺点也很显然，因为无法知道父结点以及再上层的父结点信息，所以丢失了许多有用的全局信息。另一个缺点就是需要提前进行二叉化，虽然二叉化加入了头结点（head）信息，事实证明是很有用的，但是头结点的标注需要许多语义学知识，非常的耗时耗力。一个较为简洁的做法就是，用空结点来作为句法分析中临时结合两个子结点而产生出的，但是在正确句法树中不存在的结点。在还原树结构的时候忽略这种空结点，这样就可以隐式地进行二叉化操作了。

自顶向下的转移系统

自顶向下的转移系统利用的是句法树的前序遍历（pre-order）序列，首先将父结点入栈，然后不断操作直到它的子结点全部入栈，这时将父结点连同所有子结点全部归约为一个结点，也就是这个父结点自身。

图5：自顶向下的转移系统动作定义。

自顶向下转移系统的动作形式化定义如图5所示，其中移进动作和之前一样，都是将缓存的第一个单词入栈。而非终结符（NT-X）动作就是将非终结符X入栈，也就是接下来的子树的父结点就是X。归约动作就是将栈顶若干个元素，一直到之前移进的那个父结点为止都出栈，然后归约为一个结点，再次入栈。注意到这里不同于自底向上转移系统的地方是没有完成动作，因为自底向上系统存在一元动作，所以最后根节点可能会无限归约下去，因此需要通过完成动作来提前终止分析。当然其实转移系统的动作定义并没有严格的要求，不同论文定义的也都不一样，但是都大同小异，也就是都存在移进和归约这两个动作，所以这些转移系统又可以叫做移进-归约系统。

对于图1中的句法树，用自顶向下系统分析的过程如图6所示。

图6：自顶向下的转移系统的一个例子。

自顶向下转移系统的优缺点和自底向上转移系统恰好互补。优点就是可以充分利用全局信息，例如父结点的信息，并且不需要提前进行二叉化，因为归约的时候只要找到栈里第一个非终结符就行了。而缺点就是无法利用局部信息，也就是已经分析好的子树信息，同样非终结符动作也可能会出现无限多次执行的情况，所以要加上一些限制条件。

基于中序遍历的转移系统

基于中序遍历的转移系统利用的是句法树的中序遍历（in-order）序列，首先将最左边的子结点移进栈里，然后将父结点入栈，再不断操作直到该父结点的剩余子结点全部入栈，然后对它们进行归约。

图7：基于中序遍历的转移系统动作定义。

基于中序遍历的转移系统的动作形式化定义如图7所示，其中移进动作和之前一样，都是将缓存的第一个单词入栈。映射非终结符（PJ-X）动作是预测出当前栈顶的元素的父结点X。归约动作就是将栈顶的若干个元素归约为最里面倒数第二个元素，也就是它们的父结点。

图8：基于中序遍历的转移系统的一个例子。

对于图1中的句法树，用基于中序遍历的系统分析的过程如图8所示。

根据经验，当我们读一个短语时，我们通常会注意到它的第一个单词，然后我们可以根据观察到的词推断出短语的类型。例如，当我们读到“likes”这个词时，我们可以假设紧跟着这个词的是一个动词短语。而后面的单词“red tomotoes”只是这个动词短语的宾语。与自顶向下的转移系统相比，“likes”中的局部信息对于识别这是一个动词短语可能至关重要。此外，动词短语（VP）中的全局信息也有利于之后的预测。

基于中序遍历的转移系统的优点恰好结合了前面两种转移系统，既可以考虑到局部信息，又可以考虑到全局信息。

生成模型

之前介绍的三种转移系统都属于判别式模型，而基于自顶向下转移系统，又诞生出了一种生成式模型——循环神经网络文法（RNNG）。循环神经网络文法本质上就是自顶向下的转移系统，动作定义和章节自顶向下的转移系统介绍的基本一致。只是之前介绍的自顶向下的转移系统是判别式模型，每次移进的单词都是缓存中给定正确的单词。而循环神经网络文法每次移进的单词需要通过动作生成（GEN-X）预测得出，最终模型对预测出来的句子分析出句法树。

正式定义就是，对于句子 X 和对应的句法树 Y ，判别式模型是对条件概率进行建模，而生成式模型是对联合概率进行建模。