【ACL2020】一种新颖的成分句法树序列化方法(一)

简介: 不知不觉在字节跳动实习也快四个月了,在这高强度快节奏的工作生活中,也是收获颇多。然而博客也很久很久没更新过了,论文阅读了那么多,却一直没空写写自己中的这篇。今天趁周末分享一下自己发在今年ACL上的这篇工作,主要贡献就是提出了一种新颖的成分句法树的序列表示方法。建议配合我的PPT阅读,里面有很多例子。


前言


不知不觉在字节跳动实习也快四个月了,在这高强度快节奏的工作生活中,也是收获颇多。然而博客也很久很久没更新过了,论文阅读了那么多,却一直没空写写自己中的这篇。今天趁周末分享一下自己发在今年ACL上的这篇工作,主要贡献就是提出了一种新颖的成分句法树的序列表示方法。建议配合我的PPT阅读,里面有很多例子。

介绍


成分句法分析任务的目的就是解析出一个句子的短语结构树,详细的介绍都可以在我写的综述里找到:成分句法分析综述(第二版)[4]

当前主流的成分句法分析方法我按照归一化目标主要分为两类:

  • 一是基于CKY的「全局归一化」方法,优化整棵句法树得分之和。也就是采用动态规划算法解析,时间复杂度较高(image.png),但同时效果是目前SOTA的。
  • 二是各种「局部归一化」方法,优化目标是单个目标得分(例如span、action、syntactic distance等等)。这一类方法具体包括基于shift-reduce的转移系统、各种序列化方法(例如syntactic distance)、基于CKY解码的局部归一化模型等,速度通常都很快,但由于局部归一化并没有考虑到全局特征,所以效果普遍较差。

详细说两个以往的局部归一化方法吧。例如预测句法树的括号表达式,然后还原成句法树,这种方法效果非常差,因为很难解决括号匹配合法性的问题,模型很难学。再如syntactic distance,因为预测的是浮点数序列,所以约束太松了,只要求相对大小合适就行,可解释性也较差,没有和span紧密结合起来,因此最后效果也一般。最后转移系统也会存在exposure bias的问题,效果也不尽如人意,基本没人使用了。

动机

回到主题,针对上面这么多问题,我想寻找一种更好的序列表示方法,如果能够和span更直接联系起来就最好了。其实这篇论文idea出来的初期,我是想用上GNN(GAT)的,那么就得有一张图,而传统的成分句法树不适合直接GNN建模,因为节点数不确定,图没法提前获得。因此我就联想到了我师兄去年发的一篇依存句法树应用GAT的工作:Graph-based Dependency Parsing with Graph Neural Networks[5]。如果有一个办法能让成分句法树表示成依存树那样就好了!于是我这个idea就逐渐成型了,虽然最后并没有用上GNN。

序列化方法


我原论文里面有很多公式和证明的部分,这里我就跳过了,其实方法的思想非常的简单。

image.png列化示例

如上图所示,句法树原本可能不是二叉的,因此要先转成二叉树,然后这个二叉树在span表中(图c)绿色的部分就是所有的左孩子(包含根结点),红色的部分就是所有的右孩子。

image.png

image.png

同时可以证明,满足如上两个条件的任意非负整数序列都可以唯一还原成一棵句法树。序列化和反序列化伪代码如下:

image.png序列化和反序列化算法

注意这里的反序列化有个前提假设: 一定要是满足上面两个条件的合法序列!至于不合法的怎么办?下面会详细讲。

模型


模型方面没有什么新意,借鉴了依存句法分析模型bi-affine attention。

image.png

反序列化

之前提到过,如果预测出来的序列是非法的怎么办呢?其实之前的两个条件,第一个条件可以通过mask的方式保证满足,一般第二个条件无法满足,也就是会出现交叉的span。

image.png

image.png方法二示例


image.pngimage.png

image.pngimage.png

方法三示例

这个方法效果也完全一样,实现起来可能方便一丢丢。


相关文章
|
12月前
|
存储 算法 Python
Python算法——树的序列化与反序列化
Python算法——树的序列化与反序列化
193 1
|
3月前
|
Java
JDK序列化原理问题之Hessian框架不支持writeObject/readObject方法如何解决
JDK序列化原理问题之Hessian框架不支持writeObject/readObject方法如何解决
|
4月前
|
JSON NoSQL Java
Redis18的Java客户端-StringRedisTemplate,序列化存在的问题,使用StringRedisTemplate解决序列化的方法
Redis18的Java客户端-StringRedisTemplate,序列化存在的问题,使用StringRedisTemplate解决序列化的方法
|
6月前
|
NoSQL 容器 Kubernetes
树、二叉树、树的遍历、树的序列化
树、二叉树、树的遍历、树的序列化
|
6月前
|
存储 算法 数据库
常用的c++序列化方法
常用的c++序列化方法
156 0
剑指offer(C++)-JZ37:序列化二叉树(数据结构-树)
剑指offer(C++)-JZ37:序列化二叉树(数据结构-树)
|
存储 缓存 编解码
【JavaSE专栏21】序列化和反序列化,学会Java的编解码方法
【JavaSE专栏21】序列化和反序列化,学会Java的编解码方法
146 0
|
机器学习/深度学习 人工智能 自然语言处理
【ACL2020】一种新颖的成分句法树序列化方法
【ACL2020】一种新颖的成分句法树序列化方法
103 0
|
JSON 编译器 Go
Go-结构体类型详解(声明、初始化、结构体指针、方法、序列化等)
Go-结构体类型详解(声明、初始化、结构体指针、方法、序列化等)
192 0
Go-结构体类型详解(声明、初始化、结构体指针、方法、序列化等)
|
机器学习/深度学习 自然语言处理 算法
【ACL2020】一种新颖的成分句法树序列化方法(二)
不知不觉在字节跳动实习也快四个月了,在这高强度快节奏的工作生活中,也是收获颇多。然而博客也很久很久没更新过了,论文阅读了那么多,却一直没空写写自己中的这篇。今天趁周末分享一下自己发在今年ACL上的这篇工作,主要贡献就是提出了一种新颖的成分句法树的序列表示方法。建议配合我的PPT阅读,里面有很多例子
113 0
【ACL2020】一种新颖的成分句法树序列化方法(二)