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

理论证明

主要证明两个性质，一个就是充分性（即每个句法树都能映射为一个序列），另一个就是单射性（即每个序列只能唯一对应一个句法树）。

充分性：这个显而易见，对于每个句法树，相邻两个单词一定存在唯一的LCA，且它的label也是唯一的，所以充分性肯定能保证的。

单射性：为了简便，首先证明不包含非终结符的树结构映射的单射性，再证明加上非终结符也是单射的。

如果用 表示第 i 个叶子结点，那么句法树可以表示成如下的括号表达式：

更进一步，每个 形式肯定是 ，因为如果存在一个闭合的括号对，那么中间肯定还存在着一个叶子结点，这显然不可能。所以我们可以用 来替代 ，用 来替代 ，将 改写为 ，括号表达式可以重写为：

注意到首尾两个元素一定是空的，接下来用 替换 ，得到序列：

更进一步，可以证明 一定只含有 中的一个。因为如果两个都含有的话，说明存在 这种一元产生式，但是因为一元产生式都提前处理过了，所以不可能存在。

接下来可以给每个 分配一个值 ，如果 左右两边都没有括号，那这个值就是0，如果左边有 k 个括号，那值就是 ，如果右边有 k 个括号，那值就是 -k 。如果将这些值写成序列：

这个序列正好对应了之前的第二种编码，也就是编码成LCA的个数之差。这是为什么呢？可以看出，一直到  结束，没有闭合的括号数量正好就是 和 的LCA数量。所以   就是 和 的LCA数量与 和   的LCA数量的差值。

最后这就验证了括号序列和之前的编码是一一对应的，单射性得证。解码的时候只需要将数字直接转化成对应的括号序列就行了。

而加上了非终结符之后，单射性不会受到影响。因为虽然两棵相同结构但是拥有不同非终结符的句法树，转化成括号序列后是相同的。但是因为之前的定义中，还有一个变量 来表示这个非终结符了，所以还是能够唯一对应过去的。

限制

上面定义的序列化函数有两个缺点：一是非满射，二是不能处理一元产生式，下面介绍一下解决方法。

对于一元产生式： 有两种一元产生式，一种是中间结点，还有一种是叶子结点的label。

对于中间结点，直接将一条链上的label合并成一个新的label就行了，方法和之前文章介绍的一样。

而对于叶子结点的label，一个方法是在解码之前先用一个函数预测一下每个叶子结点的label，如果为空，说明没有label，否则就加上这个label，然后再进行正常的解码。另一个方法是将之前的序列化的二元组扩展为三元组 ，其中第三个元素就是每个叶子结点的label。

非满射： 非满射会导致的问题就是产生出来的序列可能无法映射到某一棵句法树。根据文中所说，一共有两种无法映射的情况。

一种情况是对于多叉树，相邻两对叶子结点的LCA的label预测不同。比如在最上面一张图中，“the red toy”如果预测为两个不同的label，那么就会产生矛盾。这种情况很好解决，只要在解码的时候只取第一个label，忽略后一个就行了。

另一种情况是序列可能会产生一元产生式，如下图所示：

根据图中序列，会产生下面那棵句法树，一元结点X并没有预测到。但其实因为一元结点已经提前合并了，所以如果预测到了一元结点，直接删掉不要就行了。

序列标注

这里就不细讲了，用的就是基本的BiLSTM + CRF序列标注模型，具体可以看这篇论文：

End-to-end Sequence Labeling via Bi-directional LSTM-CNNs-CRFarxiv.org

实验

这篇论文最大的卖点不是效果，而是速度快，下面是和其他模型的速度对比，可以看出，速度的确快了不少，达到了大几百句每秒。但是还是存在序列标注模型的老毛病，效果并不好，虽然比之前的高了，但是还是只有90%的F1。

结论与展望

这篇论文定义了一种新的句法树序列化方法，将句法树序列化为长度减1的序列，其中每个值就是相邻两个单词的CA个数和LCA的label。

看完这篇，我仔细想了想，其实之前的chart-based方法也都可以转化成序列，只不过都得特别处理一下一元产生式和多叉树，比较麻烦。以后可以考虑在这方面有所突破，速度快还是很nice的。