介绍
这次要介绍的论文是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为止。