论文赏析[ACL18]直接到树：基于神经句法距离的成分句法分析(一）

摘要

主要思想是通过预测一个实值向量来构造出成分句法树，该实值向量表示的就是成分句法树的所有split，并且按照中序遍历给出，具体细节之后会讲到。这个方法之前没有见过，很有新意，效果也很不错，虽然比不上之前讲的基于span的方法，但是该模型最大的优点就是可以并行，时间复杂度低。

近些年来，成分句法分析模型大多是通过学习出词和短语的表示，然后用基于转移的或者基于chart的方法进行句法分析，亦或者是上一篇笔记中提到的top-down方法。但是这一类方法都有一些不可避免的缺点，比如基于转移的方法，通过预测转移序列来生成句法分析树，但是一棵句法分析树可能对应着多棵不同的转移序列，所以训练的时候可能产生错误，可以通过动态Oracle技术解决。基于chart的模型缺点就是速度太慢。

本文提出了一种新的概念叫做“syntactic distance”，以下称作句法距离，这个概念首次提出是2017年一篇语言模型的论文中的，本文将其用在了句法分析中。主要思想是这样的：对于一棵二叉树，它的中序遍历的split序列和二叉树是唯一对应的，所以只需要预测这个split序列就行了，而每个split就是用句法距离来表示。下图就是一棵句法树对应的句法距离：

这棵树有两个split，第一个split的高度更高，所以对应的句法距离数值更大。

最后通过top-down顺序进行解码，解码时间复杂度为 。最后模型在PTB上取得了91.8的F1值，CTB上取得了86.5的F1值。

Syntactic Distances

一棵句法树的句法距离如下定义：

对于句法分析树 T ，它的叶子结点也就是句子为 ，记叶子结点 的最近公共祖先LCA为 ，那么句法树 T 的句法距离定义为任意向量 ，并且满足

这个定义可能看起来比较难理解，通俗一点讲就是， 中任意一对元素的大小关系和 中下标相同的一对元素的大小关系是完全一样的，也就是说，句法距离大小反映的是一个句子两两相邻元素的LCA的高度大小。

还用上面那张图举个例子， ，那么它的句法距离 就是满足 的任意向量。

这样就可以将一棵句法树唯一对应到一个句法距离的序列，只要预测这个序列就可以得到句法树了，这比预测span集合更加直接。

那么训练的时候如何将句法树转化为句法距离呢？这里只考虑二叉树，下面的算法1给出了伪代码，将句法树转化为三元组 。其中 d 是两两相邻的叶子结点的LCA的高度向量，可以证明，这和中序遍历得到的结点顺序完全相同。 c 是与之顺序相同的结点的label向量。 t 是叶子结点从左向右的tag标签向量。

从算法中可以看出，采用自顶向下递归的形式，叶子结点高度为0，不存在句法距离和label。而内结点的高度等于左右儿子高度较大的一个加1，句法距离为左儿子句法距离拼接上自身句法距离再拼接上右儿子句法距离，label也是如此。

那么如果得到了一棵句法树的三元组 ，如何还原出这棵句法树呢？算法2给出了构造方法，其实类似于之前那篇论文的top-down方法。

原理很简单，只要在每一步寻找 d 中最大的元素，也就是寻找高度最大的内结点，该内结点对应的下标就是句法树的split，然后对左右子树递归解析就行了。时间复杂度只要 ，而之前的top-down模型时间复杂度为 。

上图是构造句法树的一个例子，和之前一样，通过 的label隐式的将句法树二叉化了，一元还是处理成新的label。图中的矩形高度就代表了句法距离的大小，可以看出，除了 这两个句子开始结束标记的句法距离以外， 最大，所以句法树的split就是 ，然后对右子树递归分析。

在子树递归过程中，可以并行计算，理论上时间复杂度可以降到 ，但是句子长度过短的话，是否与cpu通讯时间都要大于这个数量级了呢？这个并行的意义还有待商榷。