漫谈 Language Model (2): 实践篇

本文是“漫谈 Language Model 系列”中的第 2 篇，参见本系列的其他文章。在上一次的原理篇中，我们介绍了 Language Model 的基本原理，并大致讲了一下如何来构造一个 Language Model ，然而，在实践中还是会碰到不少问题的，本文将提出其中一部分问题并给出解决办法。

第一个问题是浮点数精度问题，不止是在 Language Model 中，几乎任何做概率计算的程序都会遇到这个问题：浮点数下溢，也就是需要表示的数字（绝对值）太小了，超出了浮点数所能表示的范围。通常情况下，一个双精度的浮点数在计算机里由 8 个字节来存储，按照 IEEE 754 的浮点数标准（这是目前绝大多数计算机采用的表示方法），一个双精度的浮点数的内存布局如下：

其中指数部分采用 Offset Binary 的编码方式，且 bias 为 0x3ff ，而正常情况下 fraction 部分前面有一个默认的 1 ，因此所能表示的最小的浮点数为 $2^{-1022}\approx 2.225\times 10^{-308}$ ，如果考虑 Subnormal Number 的情况的话，也最多能达到 $2^{-1074}\approx 5\times 10^{-324}$ 。其实这已经是一个很高的精度了，通常表示一个词的概率没有什么问题，然而问题出在 Language Model 计算的字符串的概率，这是一个连乘，例如，对于简单的 unigram 的情况：

\[ \displaystyle P(S) = P(w_1w_2\cdots w_n) = \prod_{i=1}^n P(w_i) \]

虽然表示每一个 $P(w_i)$ 都没有问题，但是这么多极小的数字乘起来，一不小心就会超出浮点数的精度范围，这个时候计算机就会把它当作 0 了。其实我们计算概率通常是为了进行比较，如果我们得到两个数 $10^{-400}$ 和 $10^{-500}$ ，本来前者要远远大于后者，然而由于计算机的精度限制，却认为两者是相等的（都为零），就很不好了。解决的办法其实很简单，既然问题出在连乘上，那么就拿连乘开刀——在前面加一个 $\log$ ，让它变成连加：

\[ \displaystyle \begin{aligned} \log P(S) & = \log P(w_1w_2\cdots w_n) \\ & = \log \prod_{i=1}^n P(w_i) \\ & = \sum_{i=1}^n \log P(w_i) \end{aligned} \]

这样就可以有效的避免浮点数下溢的问题了，而且 $\log$ 函数是一个单调递增的函数，原来的大小比较现在还是照样比较即可。不过有一点要注意的地方就是：$\log$ 函数在 0 处是没有定义的（或者说 $-\infty$），因此我们需要避免概率值为 0 的情况出现，这也就是我们要说的下一个问题。

其实，即使不考虑 $\log$ 的问题，我们也是希望极力避免零概率出现的。按照我们之前说的最直接的构造模型的方法，概率的近似值是通过频率估计出来的，亦即 $P(w_i) = \frac{C(w_i)}{C}$ ，其中 $C(w_i)$ 表示 $w_i$ 出现的次数，而 $C$ 是所有单词出现的总次数，但是如果在训练数据中没有出现过 $w_i$ 的话，那么 $P(w_i)$ 就会等于零，这看起来似乎也是蛮合理的，但这样一个零出现在概率连乘中会导致非常尴尬的局面，考虑下面两个句子：

1. $w_i$ is a word
2. I $w_i$ you he Emacs

不论 $w_i$ 是一个什么词，是不是曾经在训练数据中出现，第一个句子的概率总是会比第二个（完全无视语法规则）要大一些，但是如果 $P(w_i)$ 是零的话，导致的结果就是这两个句子的概率现在相等了——都为零。在这样的连乘式里零传染性简直比 N1H1 Influenza 还要可怕呀，并且采用 $\log$ 的办法在这里只会造成更多的混乱—— $-\infty$ 比零处理起来更麻烦。所以，通常我们会想一些办法来避免零的出现，这个过程又叫做 smoothing ，一个最简单的办法就是修改概率近似的公式：

\[ \displaystyle P(w_i) = \frac{N_{w_i}+1}{N+|W|} \]

其中 $|W|$ 是总的单词的个数，也就是分子上加了 1 的个数了，这样保证了 $\sum_i P(w_i) = 1$ ，经过这样简单的变换，现在所有未在训练数据中出现过的词都被赋予了一个等于 $\frac{1}{C+|W|}$ 的概率，而不是零，不过可惜的是，这样一个 ad hoc 的办法效果并不好，特别是在 n-gram (n > 1) 的模型中。因此，我们在这里介绍一种回退（back-off）的方法，叫做 Katz Smoothing，主要用在 n-gram 的模型中。以一个 trigram 模型为例，我们通过如下的办法计算条件概率：

\[ \displaystyle P_{\text{ML}}(w_3|w_1w_2) = \frac{C(w_1w_2w_3)}{\sum_i C(w_1w_2w_i)} \]

下标 $\text{ML}$ 表示这是通过最大似然的方法估计出来的概率，如前面所说，如果没有 $w_1w_2w_3$ 出现在训练数据中的话，这个式子会得零，这不是我们想看到的，于是在这个时候我们用回退的办法来计算它的概率，减小上下文的长度，因此重新定义一个概率计算公式如下：

\[ \displaystyle P_{\text{Katz}}(w_3|w_1w_2) = \left\{\begin{array}{ll} d_rP_{\text{ML}}(w_3|w_1w_2) & \text{if $C(w_1w_2w_3) > 0$} \\ \alpha(w_1w_2)P_{\text{Katz}}(w_3|w_2) & \text{if $C(w_1w_2w_3) = 0$} \end{array}\right. \]

其中 $\alpha(w_1w_2)$ 是回退系数，$d_r$ 是打折的折扣系数，下标 $r = C(w_1w_2w_3)$。原本所有出现数目大于零的 $w_1w_2w_i$ 的概率加起来等于 1 ，现在用一个系数进行打折，让他们变小，因此相加之和也就小于 1 了，剩下的这一部分概率则经过回退分配到那些没有在训练数据中出现过的 $w_1w_2w_i$ 上。

折扣系数是由我们定的，在 Katz Smoothing 中是根据出现次数 $r$ 来选择系数 $d_r$ 的：

• 对于 $r$ 大于一个常数 $K$ （比如，令为 5）的情况，不进行打折，因此，折扣系数直接赋为 1 。
• 对于 $r \in [1, K)$ 的情况，令 $d_r = \frac{(r+1)n_{r+1}}{rn_{r}}$ ，其中 $n_r$ 表示出现次数为 $r$ 的 trigram 的个数，$n_{r+1}$ 类推。Katz Smoothing 选择这样的折扣系数是根据 Good Turning 计算出来的近似值，具体推导可以参见 An Empirical Study of Smoothing Techniques for Language Modeling 这篇 paper 。

而回退系数则要通过概率和等于 1 这样一个等式来计算。具体来说，我们有

\[ \displaystyle \begin{aligned} 1 & = \sum_{C>0}P_{\text{Katz}}(w_i|w_1w_2) + \sum_{C=0}P_{\text{Katz}}(w_i|w_1w_2) \\ & = \sum_{C>0}d_r P_{\text{ML}}(w_i|w_1w_2) + \sum_{C=0}\alpha(w_1w_2)P_{\text{Katz}}(w_j|w_2) \end{aligned} \]

于是

\[ \displaystyle \begin{aligned} \alpha(w_1w_2) & = \frac{1 - \sum_{C>0}d_r P_{\text{ML}}(w_i|w_1w_2)}{\sum_{C=0}P_{\text{Katz}}(w_j|w_2)} \\ & = \frac{1 - \sum_{C>0}d_r P_{\text{ML}}(w_i|w_1w_2)}{1-\sum_{C>0}P_{\text{Katz}}(w_j|w_2)} \end{aligned} \]

这样不管训练数据中是否有出现该 trigram ，也不会出现概率为零的情况了。另外，回退之后 bigram 的概率计算时如果遇到同样的情况，也使用相同的方法继续回退到 unigram 即可。

最后还要探讨的是模型的修剪问题。我们之前描述的 n-gram 模型，对于在训练数据中出现过的 n-gram ，我们会根据它出现的频率，用最大似然的方法推算出概率值并存储下来，而没有出现过的 n-gram 则使用回退的方式来计算概率。这里可能碰到的问题是：出现过的 n-gram 的数目可能会太多了，无法处理，或者处理起来效率低下，因此需要对模型进行修剪。

修剪的目的是减小模型的大小，把一部分 n-gram 的信息从模型中删掉，当作未出现过的 n-gram 来进行回退处理。当然，我们还要尽量保证修剪过后的模型效果不会比原来差得太多。这里介绍一种基于相对熵的修剪方法，在 Entropy-based Pruning of Backoff Language Models 这篇 paper 的实验中说这样的方法可以在不增加识别错误率的情况下将模型压缩为原来的 26% 大小。

这个方法的想法其实很简单，相对熵又叫做 Kullback–Leibler divergence ，我在讲 Expectation Maximization 的时候也曾提到过一下。简单来说这个东西可以用来衡量两个概率分布的“差别”：

\[ \displaystyle D_{\text{KL}}(P\|Q) = \sum_i P(i) \log \frac{P(i)}{Q(i)} \]

这是一个非负的值，当且仅当 $P$ 和 $Q$ 相同时才等于零。那么，假设在修剪之前的概率分布是 $P$ ，我们分别对于每一个 n-gram ，计算删掉它之后得到的修剪过的概率分布 $P'$ 和 $P$ 的相对熵，最后选取相对熵最小的，也就是删掉之后对概率分布的影响最小的 n-gram 进行修剪。进一步假定各个 n-gram 对概率分布的影响是相互独立的的话，我们可以一股脑删掉那些影响较小的 n-gram ，直到满意为止。

这个方法的好处在于相对熵的计算很方便，虽然根据相对熵的定义，似乎每次计算都要对所有的 n-gram 遍历一次，但是其实在这里可以化简为更简便的公式。假设我们要删除一个 trigram $w_lw_{l+1}w_{l+2}$ ，为了书写方便，我用 $w^*$ 表示 $w_{l+2}$ ，而 $h$ 表示上下文（或者说“历史”，history），亦即 $w_lw_{l+1}$ ，而 $h'$ 表示回退过的上下文 $w_{l+1}$ 。现在考虑如果我们删掉了这个 trigram 之后，原来的概率分布里哪些内容会改变呢？

• 不需要回退的概率值，亦即在训练数据中出现过的那些 n-gram ，除了 $hw^*$ 之外，它们的概率是不需要变的。
• $hw^*$ 将改为采用回退的方式来计算概率：$P(w^*|h) = \alpha'(h)P(w^*|h')$ ，它原来的那部分概率值将纳入所有回退概率的这部分里，所以回退系数 $\alpha(h)$ 需要重新计算，记为 $\alpha'(h)$ （注意其实 $hw^*$ 已经是用的新的回退系数了），这样一来，所有以 $h$ 为上下文的回退概率值都会改变。

再回过头来考虑相对熵的式子：

\[ \displaystyle \begin{aligned} D_{\text{KL}}(P\|P') &= -\sum_{i,j}P(w_i,h_j)[\log P'(w_i|h_j) - \log P(w_i|h_j)] \\ &= -\sum_i P(w_i,h)[\log P'(w_i|h) - \log P(w_i|h)] \\ &= -P(w^*,h)[\log P'(w^*|h)-\log P(w^*|h)] \\ &\qquad-\sum_{C=0}P(w_i,h)[\log P'(w_i|h)-\log P(w_i|h)] \\ &= -P(h)P(w^*|h)[\log P(w^*|h')+\log\alpha'(h)-\log P(w^*|h)] \\ &\qquad -P(h)\sum_{C=0}P(w_i|h)[\log\alpha'(h)-\log\alpha(h)] \\ &= -P(h)P(w^*|h)[\log P(w^*|h')+\log\alpha'(h)-\log P(w^*|h)] \\ &\qquad -P(h)[\log\alpha'(h)-\log\alpha(h)]\sum_{C=0}P(w_i|h) \end{aligned} \]

回忆刚才的内容，回退系数 $\alpha$ 是这样计算的：

\[ \displaystyle \alpha(h) = \frac{1-\sum_{C>0}P(w_i|h)}{1-\sum_{C>0}P(w_i|h')} \]

现在由于 $hw^*$ 被删掉了，因此只需要同时在分子分母上去掉该项即可算出 $\alpha'(h)$，最开始计算 $\alpha(h)$ 的时候保存下分子和分母的话，这里的计算会变得特别简单。而计算相对熵的式子的最后一行的那个和式其实也是计算过的结果：

\[ \displaystyle \sum_{C=0}P(w_i|h) = 1-\sum_{C>0}P(w_i|h) \]

也就是 $\alpha(h)$ 的分子。这样一来，相对熵的值其实可以很容易就计算出来了。 😀 到此为止，我们主要讨论了 Language Model 在实际使用中可能遇到的几个问题以及其解决方案，然而，要真正实现一个 Language Model ，我们还有更多的细节要处理，这些实现相关的问题会在本系列的下一篇再详细讨论。