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

原文链接：

本文链接：EACL17

介绍

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

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

算法框架

分层聚类

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

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

以上图为例， ${X_1}{\rm{ = \{ }}A,B{\rm{\} ,}}{X_2}{\rm{ = \{ }}C,D{\rm{\} }}$ ，聚类之后的分析表为b图，原始的分析表为a图，聚类之后的表（下面叫粗表）b唯一对应了聚类之前的表（下面叫原始表）a，而反过来原始表a能对应多种不同的粗表b。

形式化定义

我们将类别分为 $m + 1$ 层，分别表示为 ${N_0} \ldots {N_m}$ ，那么第 $m$ 层的类别集合 $N_m$ 就是原始的类别集合，而 $0$ 到 $m-1$ 层的类别就称之为收缩符号。

对于 $0 \le i \le j \le m$ ，我们定义 ${\pi _{i \to j}}:{N_i} \mapsto \Im ({N_j})$ ，其中 $\Im ({N_j})$ 就是 $N_j$ 的一个子集。该式将 $N_i$ 中的一个类别 $X_i$ 映射为了 $N_j$ 中所有聚类为 $X_i$ 的类别集合。

举个例子吧，在第一张图中， ${\pi _{1 \to 2}}(ADJ\_) = \{ JJ,JJR,JJS\}$ 。如果 $i=j$ ，那么 ${\pi _{i \to j}}(A) = \{ A\}$ 。

那么对于 ${X_i} \in {N_i},{X_j} \in {N_j},{X_k} \in {N_k}$ ，我们定义产生式 ${X_i} \to {X_j}{X_k}$ 的概率为：

$\log q({X_i} \to {X_j}{X_k}) = \mathop {\max }\limits_{\scriptstyle A \in {\pi _{i \to m}}({X_i})\atop{\scriptstyle B \in {\pi _{j \to m}}({X_j})\atop\scriptstyle C \in {\pi _{k \to m}}({X_k})}} \log q(A \to BC)$

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

引理

如果粗表中的最优句法树 ${\hat d}$ 不包含任意收缩符号，那么它等价于原始表中的最优句法树。

证明：
令 $Y$ 等于原始表中的句法树集合， $Y' \subset Y$ 等于没有出现在粗表中，但是出现在原始表中的句法树集合， ${Y''}$ 等于粗表中的句法树集合。

那么对于每一个句法树 $d \in Y'$ ，都存在唯一的句法树 $d' \in Y''$ 与之对应。所以可以推出：
$\forall d \in Y,\exists d' \in Y'',s(d) \le s(d') < s(\hat d)$
这就意味着 $\hat d$ 也是原始表中的最优句法树。

伪代码

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