3.6 平滑、插值与回退

使用最大似然概率估计存在一个问题：任何有限训练语料库都会漏掉一些完全合理的英语词序列。也就是说，某个 n 元语法可能从未出现在训练数据中，却出现在测试集中。例如，训练语料库可能同时包含 ruby 和 slippers，却恰好没有短语 ruby slippers。

这些未见序列（unseen sequence）或零计数（zero），即训练集中没有、测试集中却出现的序列，会造成两个问题。第一，它们意味着我们低估了实际可能出现的词序列概率，从而损害任何使用这些数据之应用的性能。第二，只要测试集中的一个词概率为 0，整个测试集的概率就是 0。困惑度依据测试集概率的倒数定义；如果某些上下文中的词概率为零，就会发生除以零，根本无法计算困惑度。

处理理论上应当具有非零概率的“零概率 n 元语法”，标准方法称为平滑（smoothing）或折扣（discounting）。平滑算法从一些较频繁事件中削减少量概率质量，再把它分给未见事件。这里介绍几种简单的平滑算法：Laplace（加一）平滑、加 $k$ 平滑、n 元插值和笨拙回退。

3.6.1 Laplace 平滑¶

最简单的平滑方法是在把 n 元计数归一化为概率之前，先为所有计数加一。原本为 0 的计数变成 1，原本为 1 的变成 2，依此类推。这种算法称为 Laplace 平滑（Laplace smoothing）。Laplace 平滑的表现不足以用于现代 n 元模型，但它能有效引出其他平滑算法中的许多概念，提供一个实用基线，而且在文本分类（附录 B）等其他任务中仍是一种实用平滑算法。

先把 Laplace 平滑应用于一元概率。回想一下，词 $w_i$ 的未平滑最大似然一元概率估计，是其计数 $c_i$ 除以词元总数 $N$：

Laplace 平滑只是为每个计数加一，因此也称加一平滑（add-one smoothing）。由于词表中有 $V$ 个词，每个词的计数都增加了 1，所以分母也必须加入额外的 $V$ 次观测。（如果不增大分母，概率值会怎样？）

理解一元情形后，下面对 Berkeley Restaurant Project 的二元语法进行平滑。图 3.6 给出图 3.1 中各二元语法经过加一平滑后的计数。

图 3.6 Berkeley Restaurant Project 的 9,332 句语料库中，词表 $V=1446$ 的八个词之二元计数经过加一平滑后的结果。原本为零的计数以灰色表示。

图 3.7 给出图 3.2 中各二元语法经过加一平滑后的概率，使用下文式 3.26 计算。普通二元概率是用所在行的一元计数归一化各项计数：

对加一平滑后的二元计数，需要在分母的一元计数中加入词表的词类型总数 $V$。下面的公式说明了原因：分母的一元计数其实是以 $w_{n-1}$ 开头的所有二元计数之和；由于其中每一项都加一，而这样的项共有 $V$ 个，所以分母总共增加 $V$：

因此，前文给出的每个一元计数都要增加 $V=1446$。使用式 3.26 得到图 3.7 中经过平滑的二元概率。

图 3.7 使用式 3.26 计算的 BeRP 语料库二元概率之加一平滑结果。原本为零的概率以灰色表示。

一种有用的可视化方法是重建调整计数 $C^*$，从而观察平滑算法对原始计数作了多大改变。$C^*$ 除以 $C(w_{n-1})$ 后应当得到平滑概率，因此它可以直接与 MLE 计数比较：

整理各项，可以解出：

图 3.8 给出使用式 3.27 计算的重建计数。

图 3.8 使用式 3.27 计算的 BeRP 语料库八个词之加一重建计数。原本为零的计数以灰色表示。

加一平滑对计数作出了非常大的改变。比较图 3.8 与图 3.1 的原始计数可见，$C(want\ to)$ 从 608 变成 238；概率空间中，$P(to|want)$ 也从未平滑时的 0.66 降到平滑后的 0.26。把新旧计数之比定义为折扣 $d$，就能看出每个前缀词的计数下降得多么明显：want to 的折扣为 0.39，Chinese food 的折扣仅为 0.10，缩小了 10 倍。发生这种剧烈变化，是因为过多概率质量被分给了所有零计数项。

3.6.2 加 $k$ 平滑¶

加一平滑的一种替代方法，是从已见事件向未见事件转移更少的概率质量。不为每个计数加 1，而是加一个分数计数 $k$，例如 0.5 或 0.01。因此，这种算法称为加 $k$ 平滑（add-k smoothing）。

加 $k$ 平滑需要选择 $k$ 的方法，例如可以在开发集上进行优化。尽管加 $k$ 对文本分类等任务有用，它在语言建模中的表现仍然不佳，会产生方差不良的计数和往往不合适的折扣（Gale and Church, 1994）。

3.6.3 语言模型插值¶

要解决零频 n 元语法问题，还可以利用另一种知识来源。如果要计算 $P(w_n|w_{n-2}w_{n-1})$，却没有三元语法 $w_{n-2}w_{n-1}w_n$ 的任何实例，可以改用二元概率 $P(w_n|w_{n-1})$ 估计。如果也没有足够计数计算 $P(w_n|w_{n-1})$，则可以使用一元概率 $P(w_n)$。换句话说，对于模型了解不多的上下文，减少上下文有时能够帮助模型更好地泛化。

使用这种 n 元层次最常见的方法称为插值（interpolation）：对三元、二元和一元概率加权并组合，计算一个新概率。在简单的线性插值（linear interpolation）中，不同阶的 n 元语法以线性方式插值。三元概率 $P(w_n|w_{n-2}w_{n-1})$ 的估计是分别由 $\lambda$ 加权的一元、二元和三元概率之和：

各个 $\lambda$ 的总和必须为 1，因此式 3.29 等价于加权平均。稍复杂的线性插值会以当前上下文为条件计算每个 $\lambda$ 权重。如果某个二元语法的计数特别准确，就可以假定以该二元语法为基础的三元计数更可信，从而为相应三元语法设置更高的 $\lambda$，在插值中赋予它更大权重。式 3.30 给出使用上下文条件化权重的插值公式，其中每个 $\lambda$ 的参数都是前两个词构成的上下文：

怎样设置这些 $\lambda$ 值？无论简单插值还是条件插值，$\lambda$ 都从留出语料库（held-out corpus）中学习。留出语料库是一份额外训练语料库；这个名称来自它被留在常规训练数据之外，专门用于设置 $\lambda$。^[3] 我们选择能够最大化留出语料库似然的 $\lambda$ 值：固定 n 元概率，再搜索代入式 3.29 后能为留出集给出最高概率的一组 $\lambda$。求取最优 $\lambda$ 的方法有许多，其中一种是 EM 算法；它是一种迭代学习算法，会收敛到局部最优的 $\lambda$（Jelinek and Mercer, 1980）。

3.6.4 笨拙回退¶

插值的另一种替代方案是回退（backoff）。在回退模型中，如果所需 n 元语法的计数为零，就回退到 $(n-1)$ 元语法进行近似；继续回退，直到到达具有非零计数的历史。要让回退模型给出正确概率分布，必须对高阶 n 元语法进行折扣，为低阶 n 元语法保留一些概率质量。实践中经常不执行折扣，而使用一种简单得多的无折扣回退算法，称为笨拙回退（stupid backoff）（Brants et al., 2007）。

笨拙回退放弃让语言模型构成真正概率分布的目标，不对高阶概率进行折扣。如果高阶 n 元语法计数为零，就直接回退到低一阶 n 元语法，并乘以固定且不依赖上下文的权重。由于算法不产生概率分布，按照 Brants et al.（2007）的做法，把其分数记作 $S$：

回退最终在一元语法处终止，其分数为 $S(w)=\operatorname{count}(w)/N$。Brants et al.（2007）发现，$\lambda=0.4$ 的效果良好。