论文赏析[EMNLP18]用序列标注来进行成分句法分析（一）

介绍

本文定义了一种新的树的序列化方法，将树结构预测问题转化为了序列预测问题。该序列用相邻两个结点的公共祖先（CA）数量和最近公共祖先（LCA）的label来表示一棵树，并且证明了这个树到序列的映射是单射但不是满射的，但是提出了一系列方法来解决这个问题。

相比于之前的序列方法，比如Parsing as Language Modeling，本文的序列化有所不同，主要体现在之前的方法都是seq2seq的，也就是输入句子，直接输出树的括号表达式序列。但是这种方法输出不是定长的，所以结果可能会比较差。本文的方法将输出长度固定在了句子长度减1上（只针对不存在一元产生式的句法树，这种情况之后讨论），所以可以将每个预测分配到每个单词上，然后用序列标注的方法来解决。

树的序列化

记号和基础知识

记输入句子为 ，其中 。 为拥有 个叶子结点的不含有一元产生式的句法树集合。句法分析的任务就是将输入句子 w 映射到句法树 。

为了将句法分析转化为序列标注任务，需要定义一个树的序列化方法： ，也就是将一棵有 N 个叶子结点的句法树转化为长度为 的序列。并且该映射函数还得满足一定的条件，首先它一定得是一个函数（也就是对于所有的句法树，都得找到一个对应的序列），然后这个函数还得有单射性（也就是句法树和序列要一一对应，不能存在两个句法树对应同一个序列，否则的话预测出来一个序列可能解码出两棵句法树，那就尴尬了），当然要是还满足满射性就最好了（也就是对于每一个序列，最好都能找到一棵句法树与之对应，不然预测出一个序列无法找到对应的句法树也很尴尬），当然找不到也没事，后文有解决方法。

然后需要定义一个函数，将句子映射为序列： 。这个映射就通过序列标注的LSTM来实现了， 就是LSTM的参数。

最后通过函数 将输入句子转化为对应的句法树。那么 没什么好说的，就是一个序列标注模型，下面重点就是介绍如何设计函数 。

编码

之前说到了将一棵有 N 个叶子结点的句法树转化为长度为 的序列，这个序列是这样生成的：对于单词 ，分配给它一个二元label ，其中 为单词 和 的CA数量， 为它俩的LCA的label。

如上图所示，这个序列的 有两种表示方法。一种就表示成CA的绝对数量，如图中第一行所示。还有一种表示成后一个数与前一个数的差值，这样能减少元组的数量，但是会出现负数。当然在这个例子中貌似并不能看出数量减少了。。。

叉树编码：如果句法树所有产生式全部是 k 叉的，那么还可以将编码进一步简化，具体做法就是将所有的负数 统一为一个负数就行。为什么这里就不需要对负数进行区分了呢？这还得从句法树的解码说起，我们看一看是怎么从序列解码成句法树的。

当遇到一个负数 的时候，说明 到根结点路径的长度比 到根结点路径长度少 个结点。大致结构如下图所示（图画的丑，不要介意）：

可以看出， 这棵子树接在了从 到根结点路径上的第 个结点上。但是 具体在哪还无法确定，只能确定它的子树根结点位置。另外需要解释的是，为什么这里是常数2？因为 到 与 的LCA的距离一定是2，如果不是的话，中间就一定会有其他结点，那么就一定存在结点位于 与 之间，这显然不可能。最后可以注意到，这种情况下，

如果 是正数的话，说明 到根结点路径的长度比 到根结点路径长度多 个结点。大致结构如下图所示：

这种情况下， 这棵子树接在了从 到 路径上的第 个结点处。同样也无法确定它的准确位置，但是它所在的子树确定了从这分叉出去的。

回到正题，之前说到了对于 叉树，所有负数都可以统一起来，为什么呢？继续看上面 负数那张图，对于 所在子树，需要在从 到根结点这条路径上寻找一个分叉点，也就是它俩的LCA。如果这是一个 叉树，那么这个分叉点就一定是第一个孩子数不满 个的结点。因为如果再往下的话，孩子数都满了，再加子树孩子数一定大于 。再往上的话，就会导致这第一个结点孩子数小于 ，因为从左到右遍历的，子树之间不会交叉，以后都不会有子树插入到这个结点处了。

下图就是简化序列化后的二叉树例子，第三行将所有的负数都用一个负号替代了：

我尝试过了按照这个序列构建出一棵树的过程，画了个草图给大家看看，可能有点乱（参照的是上面那个非二叉树的图）：

还有一个小trick就是对于有些直接连到根结点的叶子，用 作为它们的label。