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

伪代码

• 初始化为句法树的最优得分或者负无穷，其中det()用来求解句法树的最优得分，但是没有必要真的求出最优句法树，只需要在每个结点处保留得分最高的边即可。尽管这样得出来的句法树基本不是最高的，但是能够缩小 范围即可。
• init-chart()首先初始化分析表，全部初始化为收缩符号。
  
• 然后开始迭代过程，首先执行维特比inside算法，也就是CKY算法Viterbi-inside()，得到最优句法树 。
• 如果最优句法树不含有任意收缩符号，那么迭代结束，直接返回该句法树。
  
• 否则的话，更新 为最优句法树的分数best()。
• expand-chart()将所有收缩符号替换为下一层的收缩符号。
  
• Viterbi-outside()计算outside值。
  
• prune-chart()进行剪枝，过滤掉无用的边。
  

剪枝过程

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

对于一条边 ，定义 为含有边 e 的句法树的最大分数。那么如果

，这条边 e 就没有搜索的必要了，可以从分析表中去掉。

但是每次迭代都从原始表中计算 值太麻烦了，可以在每次迭代的时候计算粗表中的值：

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

虽然在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算法。

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