使用最大似然估计来计算概率存在一个问题：任何有限规模的训练语料库都必然会缺失一些完全合法的英文单词序列。
也就是说，某些特定的 n-gram 在训练数据中从未出现，但在测试集中却出现了。
例如，我们的训练语料可能包含单词 ruby 和 slippers，但恰好没有出现短语 ruby slippers。
这些未出现过的序列，即“零频项”（zeros）——在训练集中不存在但在测试集中出现的序列——会带来两个问题。 首先，它们的存在意味着我们低估了那些可能出现的词序列的概率，从而影响基于该数据运行的任何应用的性能。 其次，如果测试集中某个词的概率为0，那么整个测试集的概率也将变为0。 困惑度（perplexity）是基于测试集逆概率定义的。 因此只要上下文中存在概率为零的词，我们就无法计算困惑度，因为除以零在数学上是未定义的！
为了解决那些本应具有非零概率却被错误地判为“零概率 n-gram”的问题，标准方法被称为平滑（smoothing）或折扣（discounting）。 平滑算法的基本思想是从一些高频事件中“削减”一部分概率质量，并将其分配给那些未见过的事件。 接下来，我们将介绍几种简单的平滑方法：拉普拉斯平滑（Laplace，加一平滑）、愚蠢回退（stupid backoff），以及 n-gram 插值（interpolation）。
3.6.1 拉普拉斯平滑
最简单的平滑方法是在将 n-gram 频次归一化为概率之前，先给所有 n-gram 的频次都加 1。 这样一来，原来频次为零的项现在变为 1，原来频次为 1 的变为 2，依此类推。这种算法被称为拉普拉斯平滑（Laplace smoothing）。 尽管拉普拉斯平滑的效果不足以满足现代 n-gram 模型的需求，但它有助于引入其他平滑算法中常见的许多概念，提供了一个有用的基准，并且在诸如文本分类（第 4 章）等其他任务中仍是一种实用的平滑方法。
我们先从拉普拉斯平滑在 unigram 概率上的应用开始。 回忆一下，词 $w_i$ 的 unigram 概率的最大似然估计值是其频次 $c_i$ 除以词元总数 $N$：
$$ P(w_i) = \frac{c_i}{N} $$拉普拉斯平滑只需在每个频次上加 1（因此它也被称为加一平滑）。 由于词汇表中共有 $V$ 个词，每个词的频次都增加了 1，因此我们也需要调整分母，以计入额外增加的 $V$ 次观测。（如果不增加分母，概率值会怎样？）
$$ P_{\text{Laplace}}(w_i) = \frac{c_i + 1}{N + V} \tag{3.24} $$除了同时修改分子和分母外，另一种更方便的方式是描述平滑算法对分子的影响，方法是定义调整后的频次（adjusted count） $c^∗$。 这种调整后的频次更容易与最大似然估计（MLE）的原始频次直接比较，并且像 MLE 频次一样，可以通过归一化 $N$ 转换为概率。 由于我们在分子上加了 1，为了定义这个频次，还需要乘以一个归一化因子 $\frac{N}{N+V}$：
$$ c^∗_i = (c_i +1)\frac{N}{N + V} \tag{3.25} $$现在，我们可以通过归一化 $N$ 把 $c^∗_i$ 转换为对应的概率 $P^∗_i$。
另一种理解平滑的方式是将其视为折扣（discounting），即降低某些非零频次的值，从而腾出概率质量，分配给那些原本为零的项。 因此，除了使用折扣后的频次 $c^∗_i$ 来描述外，我们还可以用相对折扣值（discount） $d_i$ 来描述一个平滑算法，它表示折扣后频次与原始频次的比值：
$$ d_i = \frac{c^∗_i}{c_i} $$现在我们已经理解了 unigram 情况下的平滑思想，接下来将其应用于伯克利餐厅项目（Berkeley Restaurant Project）的 bigram 模型。 图 3.6 展示了对图 3.1 中的 bigram 进行加一平滑后的频次结果。
| i | want | to | eat | chinese | food | lunch | spend | |
|---|---|---|---|---|---|---|---|---|
| i | 6 | 828 | 1 | 10 | 1 | 1 | 1 | 3 |
| want | 3 | 1 | 609 | 2 | 7 | 7 | 6 | 2 |
| to | 3 | 1 | 5 | 687 | 3 | 1 | 7 | 212 |
| eat | 1 | 1 | 3 | 1 | 17 | 3 | 43 | 1 |
| chinese | 2 | 1 | 1 | 1 | 1 | 83 | 2 | 1 |
| food | 16 | 1 | 16 | 1 | 2 | 5 | 1 | 1 |
| lunch | 3 | 1 | 1 | 1 | 1 | 2 | 1 | 1 |
| spend | 2 | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
图3.6 伯克利餐厅项目语料库（包含了 9322 个句子）中的 1446 个词中的 8 个词的加一平滑 bigram 频次。之前为零的频次用灰色表示。
图 3.7 展示了图 3.2 中bigram的加一平滑后的概率。 回想一下，正常的 bigram 概率计算方式是每一行的频次除以 unigram 频次进行归一化：
$$ P_{MLE}(w_n|w_{n−1}) = \frac{C(w_{n−1}w_n)}{C(w_{n−1})} \tag{3.26} $$| i | want | to | eat | chinese | food | lunch | spend | |
|---|---|---|---|---|---|---|---|---|
| i | 0.0015 | 0.21 | 0.00025 | 0.0025 | 0.00025 | 0.00025 | 0.00025 | 0.00075 |
| want | 0.0013 | 0.00042 | 0.26 | 0.00084 | 0.0029 | 0.0029 | 0.0025 | 0.00084 |
| to | 0.00078 | 0.00026 | 0.0013 | 0.18 | 0.00078 | 0.00026 | 0.0018 | 0.055 |
| eat | 0.00046 | 0.00046 | 0.0014 | 0.00046 | 0.0078 | 0.0014 | 0.02 | 0.00046 |
| chinese | 0.0012 | 0.00062 | 0.00062 | 0.00062 | 0.00062 | 0.052 | 0.0012 | 0.00062 |
| food | 0.0063 | 0.00039 | 0.0063 | 0.00039 | 0.00079 | 0.002 | 0.00039 | 0.00039 |
| lunch | 0.0017 | 0.00056 | 0.00056 | 0.00056 | 0.00056 | 0.0011 | 0.00056 | 0.00056 |
| spend | 0.0012 | 0.00058 | 0.0012 | 0.00058 | 0.00058 | 0.00058 | 0.00058 | 0.00058 |
图 3.7 伯克利餐厅项目（BeRP）语料库（共 9332 个句子，词汇量 V = 1446）中八个词的加一平滑后的 bigram 概率。原先为零的概率值以灰色表示。
对于加一平滑后的 bigram 频次，我们需要在 unigram 频次上加上词汇表中单词类型的总数 $V$：
$$ P_{Laplace}(w_n|w_{n−1}) = \frac{C(w_{n−1}w_n)+ 1}{\sum_w (C(w_{n−1}w)+ 1)} = \frac{C(w_{n−1}w_n)+ 1}{C(w_{n−1}) + V} \tag{3.27} $$因此，前一节给出的每个 unigram 频次都需要加上 $V = 1446$。 结果就是图 3.7 中的平滑后的 bigram 概率。
为了便于观察平滑算法对原始频次的影响程度，通常需要重构计数矩阵。 这些调整后的频次可以通过公式 3.28 计算得到。 图 3.8 展示了重构后的频次：
$$ c^∗(w_{n−1}w_n) = \frac{[C(w_{n−1}w_n) + 1] \times C(w_{n−1})}{C(w_{n−1}) + V} \tag{3.28} $$| i | want | to | eat | chinese | food | lunch | spend | |
|---|---|---|---|---|---|---|---|---|
| i | 3.8 | 527 | 0.64 | 6.4 | 0.64 | 0.64 | 0.64 | 1.9 |
| want | 1.2 | 0.39 | 238 | 0.78 | 2.7 | 2.7 | 2.3 | 0.78 |
| to | 1.9 | 0.63 | 3.1 | 430 | 1.9 | 0.63 | 4.4 | 133 |
| eat | 0.34 | 0.34 | 1 | 0.34 | 5.8 | 1 | 15 | 0.34 |
| chinese | 0.2 | 0.098 | 0.098 | 0.098 | 0.098 | 8.2 | 0.2 | 0.098 |
| food | 6.9 | 0.43 | 6.9 | 0.43 | 0.86 | 2.2 | 0.43 | 0.43 |
| lunch | 0.57 | 0.19 | 0.19 | 0.19 | 0.19 | 0.38 | 0.19 | 0.19 |
| spend | 0.32 | 0.16 | 0.32 | 0.16 | 0.16 | 0.16 | 0.16 | 0.16 |
图 3.8 伯克利餐厅项目（BeRP）语料库（共 9332 个句子，词汇量 V = 1446）中八个词的加一平滑后重构的频次。原先为零的频次以灰色表示。
需要注意的是，加一平滑对原始频次造成了非常显著的改变。
将图 3.8 与图 3.1 中的原始频次对比可以看出，C(want to) 从 608 大幅下降到了 238！
我们也可以从概率空间观察到这一变化：P(to|want) 从未经平滑时的 0.66 下降到了平滑后的 0.26。
观察折扣值 $d$（即新旧频次之比），可以更清楚地看到每个前导词（prefix word）对应的所有 bigram 频次都被大幅削减：want to 的折扣值为 0.39，而 Chinese food 的折扣值更是低至 0.10，相当于缩减为原来的十分之一！
造成这种剧烈变化的原因是，加一平滑将过多的概率质量分配给了所有原本为零的 n-gram。
3.6.2 加-k平滑
加一平滑的一个替代方法是从已见事件向未见事件转移稍微少一些的概率质量。 我们不是给每个频次加1，而是加上一个小于1的分数k（比如0.5？0.01？）。 这种算法因此被称为加-k平滑（add-k smoothing）。
$$ P^*_{Add-k}(w_n|w_{n−1}) = \frac{C(w_{n−1}w_n) + k}{C(w_{n−1}) + kV} \tag{3.29} $$加-k平滑要求我们有一种方法来选择k值；这可以通过在**开发集（devset）**上进行优化来实现。 虽然加-k平滑在某些任务上（包括文本分类）有用，但是结果表明它对于语言模型的效果仍然不佳，生成的频次方差较大，且对折扣的选择常常不恰当（Gale和Church，1994）。
3.6.3 语言模型插值
我们可以利用另一种知识来源来解决 n-gram 零频问题。 当试图计算 $P(w_n|w_{n-2}w_{n-1})$ 时，如果某个特定的 trigram $w_{n-2}w_{n-1}w_n$ 在训练数据中从未出现过，可以改用 bigram 概率 $P(w_n|w_{n-1})$ 来估计其概率。 类似地，如果没有足够的频次来计算 $P(w_n|w_{n-1})$，还可以进一步退回到使用 unigram 概率 $P(w_n)$。 换句话说，有时减少上下文长度反而有助于对模型尚未充分学习的上下文进行更有效的泛化。
利用这种 n-gram 层级结构的最常见方法称为插值（interpolation）：通过加权组合 trigram、bigram 和 unigram 的概率，来计算一个新的概率。 在简单的线性插值中，我们通过线性组合不同阶数的 n-gram 概率来实现。 因此，我们通过混合 unigram、bigram 和 trigram 概率（每个都乘以一个权重 $λ$），来估计 trigram 概率 $P(w_n|w_{n-2}w_{n-1})$：
$$ \begin{align*} \hat{P}(w_n|w_{n-2}w_{n-1}) &= \lambda_1 P(w_n) \\ &+ \lambda_2 P(w_n|w_{n-1}) \\ &+ \lambda_3 P(w_n|w_{n-2}w_{n-1}) \tag{3.30} \end{align*} $$这些 $λ$ 值之和必须为 1，因此公式 3.30 实际上等价于一种加权平均。 在线性插值的一个稍复杂的版本中，每个 $λ$ 权重会根据当前上下文动态计算。 这样，如果某个特定 bigram 的统计频次特别可靠，我们就认为基于该 bigram 的所有 trigram 的估计也更可信，因此可以为这些 trigram 分配更高的 $λ$ 值，从而在插值中赋予其更大的权重。 公式 3.31 展示了带有上下文相关权重的插值公式，其中每个 $λ$ 都以之前的两个词 $w_{n-2:n-1}$ 作为输入参数：
$$ \begin{align*} \hat{P}(w_n|w_{n-2}w_{n-1}) &= \lambda_1(w_{n-2:n-1}) P(w_n) \\ &+ \lambda_2(w_{n-2:n-1}) P(w_n|w_{n-1}) \\ &+ \lambda_3(w_{n-2:n-1}) P(w_n|w_{n-2}w_{n-1}) \tag{3.31} \end{align*} $$这些 $\lambda$ 值是如何设定的？ 无论是简单插值还是条件插值中的 $\lambda$，都是从一个留出语料库（held-out corpus）中学习得到。 该语料库是从训练数据中额外保留出来的，专门用于设定这些 $\lambda$ 值。1 我们选择的 $\lambda$ 值要最大化留出语料库的似然概率。 具体来说，先固定 n-gram 的概率值，然后搜索一组 $\lambda$ 值，使得将它们代入公式 3.30 后，能够使验证语料库的整体概率达到最高。 寻找最优 $\lambda$ 组合的方法有多种。 其中一种是使用EM 算法，这是一种迭代学习算法，能够收敛到局部最优的 $λ$ 值（Jelinek 和 Mercer，1980）。
3.6.4 愚蠢回退（Stupid Backoff）
一种替代插值方法的方案是回退（backoff）。 在回退模型中，如果所需的 n-gram 频次为零，就“回退”到 (n-1)-gram 来进行近似估计。 这一过程持续进行，直到找到一个具有非零频次的历史上下文为止。 为了使回退模型给出正确的概率分布，需要对高阶 n-gram 进行折扣处理（discount），从而为低阶 n-gram 保留一部分概率质量。 但在实际应用中，人们常常采用一种更为简单、无需折扣的回退算法，称为愚蠢回退（stupid backoff）（Brants 等，2007）。
愚蠢回退放弃了让语言模型成为一个严格概率分布的目标。 它不对高阶 n-gram 的概率进行任何折扣处理。 当某个高阶 n-gram 的频次为零时，算法直接回退到低阶 n-gram，并乘以一个固定的（与上下文无关的）权重。 由于该算法不保证输出的是一个概率分布，我们遵循 Brants 等人（2007）的做法，用符号 $S$ 来表示其输出：
$$ S(w_i|w_{i−N+1:i−1}) = \begin{cases} \frac{\mathrm{count}(w_{i−N+1:i})}{\mathrm{count}(w_{i−N+1:i−1})} & \quad \text{若 } \mathrm{count}(w_{i−N+1:i}) > 0 \\ \lambda \cdot S(w_i|w_{i−N+2:i−1}) & \quad \text{否则} \end{cases} \tag{3.32} $$回退过程最终会终止于 unigram，其得分为：$S(w) = \frac{\mathrm{count}(w)}{N}$。Brants 等人（2007）发现，将 $\lambda$ 设为 0.4 时效果较好。
留出语料库通常用于设置超参数（hyperparameters），超参数是一种特殊的参数，与从训练集中学词的常规的频次不同。我们会在第 7 章中讨论超参数。 ↩︎