专栏首页算法码上来论文赏析[EACL17]K-best Iterative Viterbi Parsing(K-best迭代维特比句法分析)

论文赏析[EACL17]K-best Iterative Viterbi Parsing(K-best迭代维特比句法分析)

原文链接:

K-best Iterative Viterbi Parsinggodweiyang.com

本文链接:EACL17

介绍

CKY算法或维特比inside算法是成分句法分析的主要方法之一,但是当产生式数量特别大之后,时间复杂度也线性增大。可行的一种方法是剪枝,但是剪枝会造成准确率的下降。所以本文就提出了一种迭代的维特比句法分析算法,通过剪枝去除掉没用的边。实验表明,时间上加快了一个数量级,但是本文并没有说准确率怎么样。。。

本文用到的inside和outside算法之前已经介绍过了,详见PCFG中inside和outside算法详解。

算法框架

分层聚类

首先提出分层聚类的概念。

如上图所示,原来的类别标记有很多,将他们聚类成几个小类,再将这几个小类聚成更小的类,依次下去,最后类别标记会少很多很多。

以上图为例,

,聚类之后的分析表为b图,原始的分析表为a图,聚类之后的表(下面叫粗表)b唯一对应了聚类之前的表(下面叫原始表)a,而反过来原始表a能对应多种不同的粗表b。

形式化定义

我们将类别分为

层,分别表示为

,那么第

层的类别集合

就是原始的类别集合,而

层的类别就称之为收缩符号。

对于

,我们定义

,其中

就是

的一个子集。该式将

中的一个类别

映射为了

中所有聚类为

的类别集合。

举个例子吧,在第一张图中,

。如果

,那么

那么对于

,我们定义产生式

的概率为:

也就是说,粗表中的每一棵句法树都给出了它在原始表中的句法树的分数的上界,通俗说就是,如果把粗表中的收缩符号全部替换成原始表中的符号,那么新的句法树的分数一定会小于等于粗表中的句法树。

引理

如果粗表中的最优句法树

不包含任意收缩符号,那么它等价于原始表中的最优句法树。

证明: 令

等于原始表中的句法树集合,

等于没有出现在粗表中,但是出现在原始表中的句法树集合,

等于粗表中的句法树集合。

那么对于每一个句法树

,都存在唯一的句法树

与之对应。所以可以推出:

这就意味着

也是原始表中的最优句法树。

伪代码

初始化为句法树的最优得分或者负无穷,其中det()用来求解句法树的最优得分,但是没有必要真的求出最优句法树,只需要在每个结点处保留得分最高的边即可。尽管这样得出来的句法树基本不是最高的,但是能够缩小

范围即可。

  • init-chart()首先初始化分析表,全部初始化为收缩符号。
  • 然后开始迭代过程,首先执行维特比inside算法,也就是CKY算法Viterbi-inside(),得到最优句法树

  • 如果最优句法树不含有任意收缩符号,那么迭代结束,直接返回该句法树。
  • 否则的话,更新

为最优句法树的分数best()

  • expand-chart()将所有收缩符号替换为下一层的收缩符号。
  • Viterbi-outside()计算outside值。
  • prune-chart()进行剪枝,过滤掉无用的边。

剪枝过程

算法的重要部分就是prune-chart()剪枝过程,这里要详细讲一下。

对于一条边

,定义

为含有边

的句法树的最大分数。那么如果

,这条边

就没有搜索的必要了,可以从分析表中去掉。

但是每次迭代都从原始表中计算

值太麻烦了,可以在每次迭代的时候计算粗表中的值:

所以当

时,从分析表中删除这条边。虽然搜索空间减少了,但是不影响算法的迭代轮数。

虽然在expand-chart()这一步要扩展收缩符号为下一层所有符号,但是实际运行起来时间比普通的CKY算法大大减少。

K-best扩展

基本框架和1-best是一样的,主要思路就是首先求出最优句法树,如果包含收缩符号,那么就下面步骤和1-best一样。否则的话求出后面k-1棵最优的句法树,如果都不包含收缩符号,直接返回k-best棵句法树。否则从中选出最好的一棵含有收缩符号的句法树,下面的步骤和1-best一样。

实验

数据集用的是PTB中长度小于35的句子。

上面这张表显示出,IVP算法的边的数量远远小于CKY算法,虽然迭代次数大大增加,但是总时间仍然远远小于CKY算法,而且边数减少了之后inside和outside算法的时间可以忽略不计了。最后一行是平均数据。

上图说明了,当k较小时,IVP算法时间快于普通的k-best算法,但是k大了之后就变慢了,原因如下图所示:

当k太大了之后,lb不能很好的得到最优得分的下界,所以无法有效地剪枝。而且k越小,算法收敛的也越快。

结论

提出了K-best IVP算法,基本框架还是inside-outside算法。

但是全文自始自终没有提及算法的准确率,感觉应该不是很高,不知道有没有又高又快的优化方法呢?

本文分享自微信公众号 - 算法码上来(GodNLP),作者:godweiyang

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-12-29

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 每日算法系列【LeetCode 658】找到 K 个最接近的元素

    给定一个排序好的数组,两个整数 k 和 x,从数组中找到最靠近 x(两数之差最小)的 k 个数。返回的结果必须要是按升序排好的。如果有两个数与 x 的差值一样,...

    godweiyang
  • 论文赏析[NAACL19]无监督循环神经网络文法 (URNNG)

    https://godweiyang.com/2019/04/20/NAACL19-URNNG/godweiyang.com

    godweiyang
  • 论文赏析[TACL18]隐式句法树模型真的能学到句子中有意义的结构吗?

    https://aclweb.org/anthology/papers/Q/Q18/Q18-1019/

    godweiyang
  • 【小工匠聊密码学】--base58编码

    Java小工匠
  • 简单模拟答案

    C语言的写法(不知字符那里该怎么改,总是才输入5行左右就异常,下次再看)(挖坑,待解决)

    lollipop72
  • 结构体的大小与内存对其

    最近在群里看到了有人问起结构体的大小问题,好多人的都不太明白。因此写篇文章总结一下。顺便再提一下结构体本身。

    zy010101
  • 55. 跳跃游戏

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/jump-game 著作权归领扣网络所有。商业转载请联系...

    lucifer210
  • qsc oj 22 哗啦啦村的刁难(3)(随机数,神题)

    哗啦啦村的刁难(3) 发布时间: 2017年2月28日 20:00   最后更新: 2017年2月28日 20:01   时间限制: 1000ms   内存限制...

    Angel_Kitty
  • Python学习 Day 13 IO编程 (最后一篇 明天换教材)

    要以读文件的模式打开一个文件对象,使用Python内置的open()函数,传入文件名和标示符:

    统计学家
  • 【翻译】Realm , ObjectBox ,还是 Room ,哪个适合你?

    2017-09-30 by Liuqingwen | Tags: Kotlin Android 翻译 | Hits

    IT自学不成才

扫码关注云+社区

领取腾讯云代金券