束搜索与评价翻译结果

束搜索

在上一篇文章seq2seq与注意力机制中，我们提到编码器最终输出了一个背景向量$\boldsymbol{c}$，该背景向量编码了输入序列$\boldsymbol{x}_1,\boldsymbol{x}_2,...,\boldsymbol{x}_T$的信息。假设训练数据中的输出序列是$\boldsymbol{y}_1,\boldsymbol{y}_2,...,\boldsymbol{y}_{T'}$，输出序列的生成概率为

$$ P(\boldsymbol{y}_1,\boldsymbol{y}_2,...,\boldsymbol{y}_{T'})=\prod_{t'=1}^{T'}P(\boldsymbol{y}_{t'}\mid \boldsymbol{y}_1,...,\boldsymbol{y}_{t'-1},\boldsymbol{c}) $$

对于机器翻译的输出来说，如果输出语言的词汇集合$\mathcal{Y}$的大小为$|\mathcal{Y}|$，输出序列的长度$T'$，那么可能的输出序列种类是$O(|\mathcal{Y}|^{T'})$。为了找到生成概率最大的输出序列，一种方法是计算所有$O(|\mathcal{Y}|^{T'})$种可能序列的生成概率，并输出概率最大的序列。我们称该序列为最优序列。但是这种方法的计算开销过高（例如，$10000^{10}=1\times10^{40}$）

我们目前所介绍的解码器在每个时刻只输出生成概率最大的一个词汇。对于任一时刻$t'$，我们从$|\mathcal{Y}|$个词种搜索出输出词

$$ \boldsymbol{y}_{t'} = \operatorname*{argmax}_{\boldsymbol{y}_{t'} \in \mathcal{Y}} P(\boldsymbol{y}_{t'} \mid \boldsymbol{y}_{1}, \ldots, \boldsymbol{y}_{t'-1}, \boldsymbol{c}) $$

因此，搜索计算开销$O(|\mathcal{Y}|\times T')$显著下降（例如，$10000\times 10=1\times 10^{5}$），但这并不能保证一定搜索到最优序列

束搜索（beam search）介于上面二者之间。下面看一个例子

假设输出序列的词典中只包含5个词：$\mathcal{Y}=\{A,B,C,D,E\}$。束搜索的一个超参数叫束宽（beam width）。以束宽等于2为例，设输出序列长度为3。假如时刻1生成概率$P(\boldsymbol{y}_{t'}\mid \boldsymbol{c})$最大的两个词为$A$和$C$，我们在时刻2对于所有的$\boldsymbol{y}_{2}\in \mathcal{Y}$都分别计算$P(\boldsymbol{y}_2\mid A,\boldsymbol{c})$和$P(\boldsymbol{y}_{2}\mid C,\boldsymbol{c})$，从计算出的10个概率中取最大的两个，假设为$P(B\mid A,\boldsymbol{c})$和$P(E\mid C,\boldsymbol{c})$。那么，我们在时刻3对于所有的$\boldsymbol{y}_{3}\in \mathcal{Y}$都分别计算$P(\boldsymbol{y}_3\mid A,B,\boldsymbol{c})$和$P(\boldsymbol{y}_3\mid C,E,\boldsymbol{c})$，从计算出的10个概率中取最大的两个，假设为$P(D\mid A,B,\boldsymbol{c})$和$P(C\mid A,B,\boldsymbol{c})$

接下来，我们可以在输出序列：$A$、$C$、$AB$、$CE$、$ABD$、$ABC$中筛选出以特殊字符EOS结尾的候选序列。再在候选序列中取以下分数最高的序列作为最终候选序列：

$$ \frac{1}{L^\alpha} \log P(\boldsymbol{y}_1, \ldots, \boldsymbol{y}_{L}) = \frac{1}{L^\alpha} \sum_{t'=1}^L \log P(\boldsymbol{y}_{t'} \mid \boldsymbol{y}_1, \ldots, \boldsymbol{y}_{t'-1}, \boldsymbol{c}), $$

其中$L$为候选序列长度，$\alpha$一般可选为0.75。分母上的$L^{\alpha}$是为了惩罚较长序列的分中的对数相加项

评价翻译结果

2002年，IBM团队提出了一种评价翻译结果的指标，叫做BLEU（Bilingual Evaluation Understudy）

设$k$为我们希望评价的n-gram的最大长度，例如$k=4$。n-gram的精度$p_n$为模型输出中的n-gram匹配参考输出的数量与模型输出中的n-gram数量的比值。例如，参考输出（真实值）为ABCDEF，模型输出为ABBCD。那么$p_1=4/5,p_2=3/4,p_3=1/3,p_4=0$。设$\text{len}_{\text{ref}}$和$\text{len}_{\text{MT}}$分别为参考输出和模型输出的词数。那么BLEU的定义为

$$ \exp(\min(0, 1-\frac{\text{len}_{\text{ref}}}{\text{len}_{\text{MT}}}))\prod_{i=1}^{k}p_{n}^{1/2^n} $$

需要注意的是，随着$n$的提高，n-gram精度的权值随着$p_{n}^{1/2^n}$中的指数减小而提高。例如

$$ 0.5^{1/2}\approx 0.7,\ 0.5^{1/4}\approx 0.84,\ 0.5^{1/16}\approx0.96 $$

换句话说，匹配4-gram比匹配1-gram应该得到更多的奖励。另外，模型输出越短往往越容易得到较高的n-gram精度。因此，BLEU公式里连乘项前面的系数是为了惩罚较短的输出。例如当$k=2$时，参考输出为ABCDEF，而模型输出为AB，此时的$p_1=p_2=1$，而$\exp(1-6/2)\approx0.135$，因此BLEU=0.135。当模型输出也为ABCDEF时，BLEU=1