成分句法分析综述（第二版）(二）

基于动态规划的解码算法及其变体

图9：基于动态规划解码算法的句法分析模型图。

这一类解码算法是由传统的CKY算法启发而来的（cocke1970programming）。传统的CKY算法是通过枚举每一个结点处的产生式来状态转移到下一个子结点，然后寻找出概率最大的那一个产生式。而这里的基于动态规划的解码算法是采用神经网络，计算出每个短语的得分，然后枚举它的所有子短语，计算出总得分最高的那棵子树。图9是这一类解码算法加上编码模型整体的模型结构。

动态规划解码

解码算法的初衷是求出得分最高的那棵子树，但是状态空间太大了，不可能枚举所有的句法树，所以就只能用动态规划算法求解了。

对于任意一个跨度 ，我们利用公式1计算所有它所有非终结符的得分。直接取得分最高的那一个非终结符 作为最优的非终结符。

而对于子短语，我们只需要预测出 的最优分割点即可。遍历所有的分割点 k ，取两个子结点 ， 与结点 得分之和最高的那个分割点即可：

注意这里计算得分取了非终结符的得分 ，并没有取跨度的得分 。因为在实际实现中，发现加不加这部分得分影响不大，所以为了简化运算，去掉了这项得分。

动态规划解码算法的时间复杂度是 的，所以对于稍长一点的句子，运行起来还是挺慢的。但是好处是可以搜索到所有的状态空间，所以准确率上比较高。

自顶向下贪心解码

因为动态规划解码算法时间复杂度太高了，所以可以用贪心解码来近似求解最优句法树。思路是自顶向下、贪心地去选择每一个跨度 的最优分割点和最优非终结符 ，这样时间复杂度将降到 。

具体实现如下，首先从根结点也就是 开始，选择一个分割点 ，使得两个子结点 ， 与根结点 的得分之和最高，而非终结符还是像之前那样直接通过短语的向量表示计算得出。具体公式为：

自顶向下贪心解码时间复杂度低，而且实际运行中并没有损失太多精度，所以可以很好地近似动态规划解码算法。而由转移系统的三种遍历顺序，自然而然还可以想到，这里也能推广到自底向上和中序遍历的贪心解码，但是由于这里预测的时候只利用到了局部的短语特征，所以仅仅更改遍历的顺序是没有效果的，还得充分利用到预测的历史信息才行。

基于序列到序列的解码算法

前面几个章节都是将句法树视为若干跨度的集合，并预测这个集合，最后还原出句法树。这个章节将要介绍的方法都是基于序列的，也就是将句法树序列化，通过预测句法树对应的序列，然后还原出句法树。

基于括号表达式

图10：句子“John has a dog .”对应的句法树及其括号表达式。

括号表达式是句法树最为常见的一种序列化方法，图10展示了句子“John has a dog .”对应的括号表达式。可以证明，括号表达式和句法树是一一对应的，所以只要预测出了括号表达式，就可以唯一映射到一棵句法树。这样句法分析任务就转化为了输入一个句子，输出一个括号表达式序列，这可以用常见的序列到序列模型来解决（VinyalsKKPSH15)。类比到机器翻译任务，可以把输入句子当成源语言，输出的括号表达式当做目标语言，这就转化为了一个翻译任务。

但是这种序列化方法存在一个较大的问题，就是限制性太强了，必须要满足输出的序列是一个合法的括号表达式，这就大大增加了预测的难度。所以一般这种序列化方法都是用来重排序的，也就是先用现成的句法分析器预测出概率最大的若干棵句法树，然后预测这几棵句法树对应的括号表达式的语言模型概率，挑选出概率最高的一棵作为最终的模型输出。

基于句法距离

图11：句子“She enjoys playing tennis .”对应的句法树及其句法距离序列。

句法距离（syntactic distance）是由（ShenLHC18)首次提出的新概念，句子中相邻两个单词的句法距离定义为它们俩的最近公共祖先的高度。图11展示了句子“She enjoys playing tennis .”的句法距离序列，对于长度为 n 的句子，它的句法距离序列长度为 n-1 ，并且满足如下条件：对于任意两个相邻的单词对，它们的最近公共祖先高度越高，那么它们俩的句法距离就越大（BengioSCJLS18）。

以图11为例，“She”和“enjoys”的最近公共祖先是“S”，所以高度最高，对应的句法距离也最大。“enjoys”和“playing”的最近公共祖先是“VP”，高度排第三，所以对应的句法距离大小也是排第三。依次类推，剩下的句法距离也满足这个性质。可以证明，这个数字序列和句法树是一一对应的。更进一步可以发现，这个序列其实就是“中序遍历的结点的高度”，原文中将其称为句法距离。

当然实际实现中，句法距离并不一定要和结点高度完全对应，甚至不需要是整数，只需要反映出彼此之间的大小关系就行了。预测这个序列也很简单，原文中并没有使用传统的双向LSTM序列标注的模型结构，而是首先将句子输入到一个双向LSTM，然后将每相邻两个单词的隐层输出做一次卷积操作（因为要预测相邻两个单词的最近公共祖先的高度），然后再将卷积输出送到一个双向LSTM中去，最后通过一个前馈神经网络得到每相邻两个单词的句法距离。

解码过程十分简单，对于一个句法距离序列 ，首先找出序列中最大的元素 ，然后下标小于 i 的句子构成了左子树，大于等于 i 的部分构成了右子树，即句法树的括号表达式为 。而对于左右两棵子树，只需要递归解码下去就行了。

当然这种解码方式仍然存在一个问题，就是句法距离序列并不一定能唯一映射回句法树。例如对于序列 ，当出现相同句法距离时，最大的句法距离并不唯一，这时候选谁做根节点都有可能，所以这个句法距离序列可以对应到任意一棵二叉树。当然在实际运行中，因为预测结果都是浮点数，所以几乎不会出现这种情况。

其他解码算法

除了以上介绍的基于转移系统的、基于动态规划的和基于序列预测的解码算法以外，还有一些其他的解码算法。

比如（TengZ18）提出了两种局部模型。一种是直接预测每个跨度 属于句法树的概率，然后使用CKY算法来进行解码。另一种是预测产生式 的概率，然后还是使用CKY算法来进行解码。这两种模型都取得了非常高的F1值。

再比如（TuZZ18）提出了高斯混合隐向量文法（GM-LVeGs），来学习产生式的向量表示，最终的效果也是要好于之前的组合向量文法（CVG）（SocherBMN13）。

若干改进

上面介绍的几种经典的句法分析模型或多或少都有一些问题，有些解码速度很慢，有些效果不是很理想，有些实现起来比较麻烦，对于不同模型要做出不同的设计调整，因此许多工作针对这些模型提出了许多优化，下面选取两个典型的优化来详细说明。

动态指导

在基于转移系统的模型和动态规划模型的自顶向下近似解码模中，都使用到了贪心的解码算法。这样就会出现一个问题，就是训练的时候因为有标准的句法树，所以不论你解码到哪一步，都可以继续按照正确的结果走下去。但是如果在测试阶段，如果你预测出了一个从来没有在训练阶段出现过的状态，那模型可能就无法知道下一步该往哪走了。这时候就要采用动态指导（dynamic oracle），来告诉模型在错误的状态该往哪走。

这里只简单说明一下动态规划模型的自顶向下近似解码中动态指导的定义，基于转移系统的模型的动态指导类似。

假设现在模型预测出了一个跨度 ，那么下面就要预测它的非终结符和分割点。

首先对于非终结符，如果 在标准的句法树中，那么它的非终结符就是标准的非终结符，否则的话就定义为空集 。

然后对于分割点，如果 在标准的句法树中，那么分割点就是标准的分割点。否则的话就在标准的句法树中寻找包含 的最小的跨度 ，然后找出 的所有分割点中，位于 之间的分割点，任意取一个都可以作为动态指导。在实际实现中，取满足条件的最左边一个分割点。不同的分割点对应了不同的二叉化方式，其实无关紧要。在（CrossH16）中有关于动态指导详细的证明过程。

策略梯度

除了动态指导解决的问题之外，贪心解码还存在一个问题，就是它只针对当前时刻来进行优化，而不是针对全局优化，所以得到的并非是全局最优解。此外动态指导针对不同的模型要进行单独的设计，这就比较麻烦，所以可以采用强化学习中的策略梯度（policy gradient）来替代它（FriedK18）。

首先用风险函数（risk objective）来作为模型的损失函数：

其中 是训练集中的标准数据。可以看出，风险函数其实就是所有可能的句法树和标准树的差异 的期望，训练的目的就是最小化所有句法树和标准树的差异，这样就解决了之前提到的两个问题。

但是显然不可能枚举所有可能的句法树，这就得用到重要性采样（important sampling）方法。但是不能直接对风险函数进行重要性采样，不然采样后的函数 消失了，就没有办法对其求导了，所以要先对风险函数求导得到：

这里的 是根据分布 采样得到的结果。具体实现中可以将标准树也加入到采样结果中，可以提升准确率。

实验

数据集

成分句法分析使用最为广泛的英文数据集是华尔街日报的PTB数据集，其中第2~21章节划分为了训练集，22章节为验证集，23章节为测试集。中文数据集为CTB数据集，目前已经有5.0，6.0以及8.0等多个版本，但是使用最为广泛的还是5.0版本。

实验结果

表1：不同模型在PTB测试集上的最终结果，其中*代表生成式模型。

表1列举了一些句法分析模型的测试结果，分为了单模型和非单模型两部分。其中单模型就是不使用任何外部知识及重排序等操作的模型，而非单模型则使用了外部语料、预训练模型、模型融合和重排序等各种方法。目前单模型最好的结果来自于（KleinK18），他们采用了Transformer作为编码器，使其结果得到了大大提升。由此可见，目前成分句法分析领域编码器的影响要远远大于解码器。而非单模型领域最好结果则来自于相同团队的工作（abs-1812-11760），这里他们使用了更为强大的预训练模型BERT，使结果上升到了一个难以逾越的高度。

总结与未来展望

本文介绍了成分句法分析领域近些年来的进展，列举了几种不同类型的成分句法分析模型（基于转移系统、基于动态规划、基于序列到序列），并对比分析了它们之间的优缺点，最后提出了几种常见的改进。

可以预见，未来成分句法分析的研究方向将会是在编码模型方面，因为解码模型对性能的提升已经到了瓶颈期，而编码模型不仅可以大大提升模型效果，还可以运用在无监督成分句法分析上。

参考文献

• Attention is All you Need
  
• Transition-based Neural Constituent Parsing
  
• Span-Based Constituency Parsing with a Structure-Label System and Provably Optimal Dynamic Oracles
  
• In-Order Transition-based Constituent Parsing
  
• A Minimal Span-Based Neural Constituency Parser
  
• Constituency Parsing with a Self-Attentive Encoder
  
• Straight to the Tree: Constituency Parsing with Neural Syntactic Distance
  
• Constituent Parsing as Sequence Labeling
  
• Grammar as a Foreign Language
  
• Two Local Models for Neural Constituent Parsing
  
• Long Short-Term Memory Over Tree Structures
  
• Dependencies vs. Constituents for Tree-Based Alignment
  
• A tutorial on particle filtering and smoothing: Fifteen years later
  
• Programming languages and their compilers: Preliminary notes
  
• Parsing with Compositional Vector Grammars
  
• Policy Gradient as a Proxy for Dynamic Oracles in Constituency Parsing
  
• Multilingual Constituency Parsing with Self-Attention and Pre-Training
  
• Fast and Accurate Shift-Reduce Constituent Parsing
  
• Shift-Reduce Constituent Parsing with Neural Lookahead Features
  
• Linear-time Constituency Parsing with RNNs and Dynamic Programming
  
• Recurrent Neural Network Grammars
  
• Effective Inference for Generative Neural Parsing
  
• Parsing as Language Modeling
  
• Extending a Parser to Distant Domains Using a Few Dozen Partially Annotated Examples
  
• Improving Neural Parsing by Disentangling Model Combination and Reranking Effects
  
• Neural Language Modeling by Jointly Learning Syntax and Lexicon
  
• Gaussian Mixture Latent Vector Grammars