论文赏析[ACL18]基于RNN和动态规划的线性时间成分句法分析（一）

介绍

这次要介绍的论文是huang liang发表在ACL18的一篇短文，提出了一个基于转移系统的线性时间句法分析器。本文的主要贡献点主要有如下几点：

• 传统的基于转移的句法分析模型都是贪心解码，不能考虑到所有的状态空间，所以本文的模型采用beam search将状态空间提升到了指数级别。
  
• 首次采用cube pruning将分析的时间复杂度降低到了 。
• 采用max-violation损失函数代替原来的求和的损失函数，并且对cross-span的span进行了惩罚。
  
• 在单模型上取得了最高的F1值。
  
• 采用图结构的栈（GSS）代替了原来的stack，这样不需要时刻保存历史信息。
  

模型基础

基于span的转移系统

这个我已经在之前的文章

成分句法分析综述godweiyang.com

中详细阐述过了。核心思想就是stack里面保存的不再是短语结构树，而是span的左右边界下标 ，初始时stack里面是 ，终止状态栈里是 ，SHIFT之后栈顶变为 ，REDUCE之后栈顶变为 （假设之前栈顶两个元素是 。

Bi-LSTM特征

状态转移时用双向LSTM两端的差值计算每个span的表示，然后计算出得分，用来预测action。

动态规划

句法树得分

还是和之前chart-based模型一样，用每个span的label得分之和作为句法树的总得分。

图结构栈（Graph-Struct Stack, GSS）

因为要采用动态规划来枚举每个时刻所有的状态，不是用普通的stack，使用GSS来保存每个时刻的状态。GSS每个时刻只需要保存栈顶的span就行了，假设为 。如果action是SHIFT，那么下一步就变成了 ，如果action是REDUCE，那么还需要知道栈顶第二个元素是什么。因为考虑到了所有的状态空间，所以所有的 都是有可能的。

GSS的具体结构如下图所示：

每个时刻的状态仅用一个span表示，在具体实现的时候，每个span还保存了一个span指针数组，指向它前面所有可能的span，还保存了当前span以及之前所有span的分数之和 c 和当前span子树的分数之和 v。每个状态还保存了一个时刻标记 l ，易知一共有 个时刻。

当采取SHIFT动作时，状态变为了 ，并且新的span 的指针数组中新增加一个span也就是 。prefix分数变为 ，其中 是span 的最高label得分，而inside分数就是span 的分数 。

当采取REDUCE动作时，枚举span 指针数组中所有的前一个span ，然后合并成一个span ，prefix分数变为 ，其中 就是span 的最高label得分，inside分数变为了 。实际代码实现中，REDUCE完了后，span 的指针数组要更新为span 的指针数组。

Beam Search和Cube Pruning

在每个时刻，只保存prefix得分最高的前b个span状态，这样时间复杂度可以降为 ，但是 相对于句子长度来说还是太大了，所以采用cube pruning继续降到 。

cube pruning原理是这样的：普通的beam search每个时刻枚举至多b个span，每个span和之前的至多b个span结合，所以一共最多产生 个span。

而cube pruning在每个时刻都建立一个堆，首先用上一个时刻的beam里的b个span，来产生b个SHIFT的span，送入堆里。理论上来说还应该产生至多 个REDUCE的span，但是在这里对于每个span，只取它的指针数组里得分最高的那个span，来和它结合产生新的span，送入堆里。然后在产生好的堆里，每次取出得分最高的span，出堆，如果它是REDUCE得到的span，那么就继续按照它的指针数组得分从高到低顺序产生一个span，REDUCE完之后送入堆里。依次下去，直到出栈了b个span为止。