束搜索与评价翻译结果

束搜索

在上一篇文章 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