数学之美梳理（一）统计语言模型，用数学的方法描述语言规律

自然语言从诞生开始，逐渐演变成一种上下文相关的信息表达和传递方式（即要理解一个词汇的真实意思，需要结合它前后的内容一起看），因此让计算机处理自然语言，一个基本问题就是为自然语言中这种上下文相关的特性建立数学模型，这个数学模型就是在自然语言处理中常说的统计语言模型（Statistical Language Model），它是所有语言处理的基础，并且广泛应用于机器翻译，语音识别，手写字体识别等领域

用数学方法描述语言规律

统计语言模型产生的初衷是为了解决语音识别问题，在语言识别中，计算机需要知道一段文字序列能构成一个大家能够理解且有意义的句子，然后再显示或者打印给用户。

举个例子，

美联储主席伯克南昨天告诉媒体7000亿美金的救助资金将借给上百家银行，保险公司和汽车公司

这句话很通顺，意思也很明确。

但是如果改变一些词的顺序，或者替换掉一些词，将这句话变成

联主美储席伯诉克南美金告媒昨天体7000亿的资救助金将给借上保险公司百，和汽车公司家银行

这句话基本上读者就会不知所云了。

如果问一个没学过自然语言处理的人，句子为什么会变成这样，他会说第一个句子合乎语法，且语意清晰。上个世界的科学家也是使用这个思路，他们试图通过判断一个句子是否合乎文法来判断一个文字序列是否有明确的含义，但是最后这条路走不通，因为语法规则过多，基本不可能枚举，且不同语言语法规则也不同，无法通用，最后就是很多有明确含义的句子其实也不符合语法规则。

后来贾利尼克换了一种思路，用一个简答的统计模型很简单地解决了这个问题。

贾利尼克的出发点很简单：一个句子是否合理，就看它的可能性大小如何

假定S表示某个有具体含义的句子，由一串有特定顺序排列的词汇$w_1, w_2, w_3,\ldots w_n$ 组成，这里的n是句子的长度。

现在我们想知道句子S在文本中出现的可能性，也就是数学上说的S出现的可能性P(S)。当然，如果我们可以把人类历史上出现的所有的话统计出来，就知道这句话出现的概率是多少了，但是这个方法听起来就不可行，因此我们需要一个模型来估算。

既然$S = w_1, w_2, w_3,\ldots w_n$，那么，不妨把P(S)展开来表示：$P(S) = P(w_1, w_2, w_3, \ldots w_n)$

利用条件概率公式，S这个序列出现的概率等于每一个词汇出现的条件概率相乘，于是$P(w_1, w_2, w_3, \ldots w_n)$ 可以展开为：

$$P(w_1, w_2, w_3,... w_n) = \\ P(w_1) \times P(w_2 | w_1) \times P(w_3 | w_1,w_2) \cdots P(w_n | w_1,w_2,\ldots w_{n-1})$$

条件概率是在已知某个事件发生的条件下，另一个事件发生的概率。它是一种在给定某些信息的前提下，事件发生可能性的量度。用数学语言描述，如果事件A的发生概率非零（P(A) > 0），那么在事件A已经发生的条件下，事件B发生的条件概率表示为 P(B|A)，读作“在事件A发生的条件下事件B发生的概率”。
条件概率可以通过以下公式计算：

$$P(B|A) = \frac{P(A \cap B)}{P(A)}$$

这里的$P(A \cap B)$ 是事件A和事件B同时发生的概率，而$P(A)$ 是事件A发生的概率。

其中$P(w_1)$表示第一个词出现的概率，$P(w_2 | w_1)$表示第一个词出现的前提下，第二个词出现的概率，以此类推，不难看出，最后一个词出现的概率取决于前面所有的词。

从计算上看，估算$P(w-1)$不难，$P(w_2 | w_1)$也还好，但是当n比较大的时候，统计$P(w_n | w_1,w_2,\ldots w_{n-1})$就不可行了，怎么办？

后来有个数学家叫马尔可夫提出，假设任意一个词$w_i$出现的概率只和它前面的那个词$w_{i-1}$有关系，那么问题就简单一些，这种假设被称为马尔可夫假设。

现在S出现的概率就变成了

$$P(w_1, w_2, w_3,... w_n) = \\ P(w_1) \times P(w_2 | w_1) \times P(w_3 | w_2) \cdots P(w_n | w_{n-1})$$

上面的公示对应的统计语言的模型是二元模型（Bigram Model）。

当然也可以假设一个词由前面的N-1个词决定，这样会更复杂一点，对应的统计语言模型就是N元模型。

我们还是继续讨论二元模型，接下来的问题就是如何估算条件概率$P(w_i | w_{i-1})$，根据他的定义：

$$P(w_i | w_{i-1}) = \frac{P(w_{i-1}, w_i)}{P(w_{i-1})}$$

而估计联合概率$P(w_{i-1}, w_i)$ 和 边缘概率$P(w_{i-1})$ 现在变得非常简单，因为有了大量的机读文本，也就是专业人士讲的语料库，只要数数$w_{i-1}, w_i$ 这对词在统计的文本中前后相邻出现了多少次$t(w_{i-1}, w_i)$，以及$w_i$ 本身单独出现了多少次$t(w_i)$，然后用两个数分别除以语料库的大小t，就可以得到这些词或者二元组的相对频度

$$f(w_{i-1},w_i) = \frac{t(w_{i-1},w_i)}{t} \\ f(w_i) = \frac{t(w_i)}{t}$$

根据大数定律，只要统计量足够，相对频度就等于概率

$$P(w_{i-1},w_i) = \frac{t(w_{i-1},w_i)}{t} \\ P(w_i) = \frac{t(w_i)}{t}$$

而$P(w_i | w_{i-1})$ 就是这两个数的比值，而它们的分母是相同的，可以直接约掉

$$P(w_i | w_{i-1}) = \frac{t(w_{i-1},w_i)}{t(w_i)}$$

这里其实有个问题还没解决，就是如何分词的问题，也就是如何将一句话拆成不同的词，这个也是个专业的自然语言处理的问题，后续的博客会介绍

现在我们有了$P(w_i | w_{i-1})$，我们就可以估算出$S = w_1, w_2, w_3,\ldots w_n$ 出现的概率了。

当然真正要实现一个好的统计语言模型，还有许多内容要考虑，比如上面公式中的$(w_i | w_{i-1})$ 在语料库中没有出现怎么办，那概率就是0吗？

接下来我们就一起看一下，统计语言模型中的一些工程诀窍。

统计语言模型的工程诀窍

高阶语言模型

二元模型的假设的前提是，句子中的每个词只和前面的词有关系，而和更前面的词就没有关系了，但是这种又太简化了。

现在让我们进一步使用N元模型，假定每个词$w_i$ 的出现和前面的N-1个词有关系，而与更前面的词没有关系，当前词$w_i$ 的概率只取决于前面N-1个词的$P(w_{i - N + 1}, w_{i - N + 2}, \ldots w_{i - 1})$ , 因此：

$$P(w_i | w_1, w_2, \ldots w_{i - 1}) = P(w_i | w_{i - N + 1}, w_{i - N + 2}, \ldots w_{i - 1})$$

这种假设被称为N-1阶马尔可夫假设，对应的语言模型就是N元模型，N=2就是二元模型，N=1就是上下文无关的模型，实际中使用的比较多的是N=3，再高训练成本就会很高，同时效果并不会好多少。

模型的训练，零概率问题和平滑方法

使用语言模型需要知道模型中所有的条件概率，我们把这些概率称为模型的参数。

刚才我们提出的训练方法，看起来很简单，对于二元模型，就是拿到两个数字，即$(w_{i - 1}, w_i)$ 在语料中出现的次数$t(w_{i - 1}, w_i)$ 和$w_{i - 1}$ 在语料中出现的次数$t(w_{i - 1})$ ，然后计算一下比值就好

但问题是，如果$(w_{i - 1}, w_i)$ 在语料中出现的次数为0怎么办，是否意味着$P(w_{i - 1}, w_i)$ 为0呢？

反过来说，如果$(w_{i - 1}, w_i)$ 和$w_{i - 1}$ 都只出现了一次，是否意味着$P(w_{i - 1}, w_i)$ 为1呢？

在数理统计中，我们之所以敢用对采样数据观察的结果来预测概率，是因为大数定律在背后做支持，他要有足够的观测值。

要解决这个问题，一个方法是直接增加数据集的大小，但是即使如此，仍然会遇到零概率或者统计量不足的情况。假定要训练一个汉语言的模型，汉语的词汇量大概是20万这个量级，如果我们采用三元模型，训练这样一个模型就会有$200000^3 = 8 \times 10^{15}$ 个参数，也就是我们的模型要有$10^{15}$ 个三元组的概率。假设从互联网上刨去垃圾数据，有100亿个有意义的中文网页，平均每个网页有1000个汉字，那么也依旧只有$10^{13}$个汉字，距离$10^{15}$ 个三元组还有很大的距离。

所以如果用直接的值估算概率，大部份的条件概率依然是0，这种模型我们称之为不平滑，在实际应用中，统计语言模型的零概率问题是无法避免的，必须要解决的。

训练统计语言模型的艺术就在于解决统计样本不足的情况下的概率估计问题。

对此，古德和他的老板图灵提出了一个解决方案，这个公式被称为古德——图灵估计。

它的原理是这样的：对于没有看见的事件，我们不能认为他的概率就是零，因此我们从概率总量中分配很小的比例给那些没被看见的事件，这样那些被看见的事件的概率总和就要小于1了，因此需要将所有可以看见的的事件的概率调小一点，，至于小多少，要根据“越是不可信的统计折扣越多”的原则。

下面以统计词典中每个词的概率为例，来说明古德——图灵估算：

假定语料库中出现r次的词有$N_r$个，未出现的词就有$N_0$ 个，语料库的大小为N，那么，很显然

$$N = \sum_{r=1}^{\infty}rN_r$$

所有出现r次的词在整个语料库的相对频度则是$\frac{rN_r}{N}$，如果不做任何优化处理，就以这个相对频度作为这些词的概率估计

现在假定当r比较小的时候，它的统计可能不可靠，因此在计算那些出现r次的词的概率时，要使用一个更小一点的次数，即$d_r$ （而不直接使用r），古德——图灵估计按照下面公式计算$d_r$:

$$d_r = \frac{(r + 1) \times N_{r+1}}{N_r}$$

显然：

$$\sum_r d_r \times N_r = N$$

一般来说，出现一次的词的数量比出现两次的多，出现两次的比出现三次的多，这种规律被称为 Zipf 定律。即$N_{r+1} \lt N_r$。因此，一般情况下，$d_r \lt r$, 而$d_0 \gt 0$。这样就给为出现的词赋予了一个很小的非零值，解决了零概率的问题，同时下调了出现频率很低的词的概率。

当然，在实际的自然语言处理中，一般对超过次数超过某个阈值的词，频率不下调，只对出现次数低于这个阈值的词，才下调频率，下调得到的频率总和给未出现的词。

这样出现r次的词的概率估计为$d_r \times N_r / N$ 。于是，对于频率超过一定阈值的词，他们的概率估计就是他们在语料库中的相对频度，对于频率小于这个阈值的词，他们的概率估计就小于它们的相对频度，出现次数越少，折扣越多。对于未看见的词，也给予了一个比较小的概率。

对于二元组$(w_{i-1}, w_i)$ 的条件概率的估计也可以做相同的处理，我么知道，通过前一个词$w_{i-1}$ 预测后一个词$w_i$ 的所有可能情况的条件概率总和应该为1，即

$$\sum_{w_i \in V} P(w_i | w_{i-1}) = 1$$

对于出现次数非常少的二元组$(w_{i - 1}, w_i)$ ，需要按照古德——图灵方法打折扣，这样$\sum_{w_i \in V} P(w_i | w_{i-1}) \lt 1$, 同时意味着有一部份概率没有分配出去，留给了没有看到的二元组$(w_{i-1}, w_i)$，基于这种思想，估计二元模型的概率公式如下：

$$P(w_i | w_{i - 1}) = \begin{cases} f(w_i | w_{i - 1}) \qquad if \quad t(w_{i - 1}, w_i) \ge T \\ f_{gt}(w_i | w_{i - 1}) \qquad if \quad 0 \lt t(w_{i - 1}, w_i) \lt T \\ Q(w_{i-1}) \times f(w_i) \qquad otherwise \end{cases}$$

其中T是一个阈值，一般在8-10之间，函数$f_{gt}$ 表示经过古德——图灵估计后的相对频度，而

$$Q(w_{i-1}) = \frac{1 - \sum_{w_iseen} P(w_i | w_{i -1})}{\sum_{w_iunseen} f(w_i)}$$

我们通过上述公式，通过训练集统计出所有二元组的概率，也就是模型的参数，就可以最终用来估计一个文字序列是否是有意义的概率

几个问题

上述过程为《数学之美》中的推导过程，前半段还好，最后突然得到古德——图灵处理后的二元模型的概率估计公式很突兀，因为按照正常的思路，应该这样思考：

在统计语言模型中，二元模型（Bigram Model）是一种基本的语言模型，它假设每个词的出现仅依赖于它前面的那个词。对于稀疏数据问题，即某些词对（word pair，即Bigram）在训练集中没有出现，或者出现次数非常少，从而导致计算得到的条件概率不准确或者是0，我们常常需要进行平滑处理。古德-图灵（Good-Turing）平滑方法是处理这种情况的一种经典方法。

古德-图灵平滑的基本思想是对所有出现次数相同的词对进行统一调整，从而为未见词对（即在训练集中未出现的词对）分配一定的概率，同时对见词（即在训练集中出现的词对）的概率进行适当调整。

对于二元模型来讲，如果词对$(w_{i}, w_{i + 1})$ 在训练语料中出现的次数为$(r(w_i, w_{i+1}))$，则使用古德-图灵公式进行平滑处理后的计数$(d_r)$ 可以表示为：

$$d_{r(w_i, w_{i+1})} = (r(w_i, w_{i+1}) + 1) \cdot \frac{N_{r(w_i, w_{i+1})+1}}{N_{r(w_i, w_{i+1})}}$$

其中，$N_r$ 表示在整个训练集中恰好出现了r次的词对的数量，$N_{r+1}$ 表示恰好出现了 r+1 次的词对数量。

然后，基于调整后的计数$d_r$ ，二元模型中的条件概率可以计算为：

$$\frac{d_{r(w_i, w_{i+1})} \cdot N_{r(w_i, w_{i+1})}}{\sum d_{r(w_i, w_{i+1})} \cdot N_{r(w_i, w_{i+1})}} = \\ \frac{(r(w_i, w_{i+1}) + 1) \cdot \frac{N_{r(w_i, w_{i+1})+1}}{N_{r(w_i, w_{i+1})}} \cdot N_{r(w_i, w_{i+1})}}{\sum d_{r(w_i, w_{i+1})} \cdot N_{r(w_i, w_{i+1})}} = \\ \frac{(r(w_i, w_{i+1}) + 1) \cdot N_{r(w_i, w_{i+1})+1}}{\sum d_{r(w_i, w_{i+1})} \cdot N_{r(w_i, w_{i+1})}} = \\ \frac{(r(w_i, w_{i+1}) + 1) \cdot N_{r(w_i, w_{i+1})+1}}{\sum (r(w_i, w_{i+1}) + 1) \cdot N_{r(w_i, w_{i+1})+1}}$$

推导到这里就没法继续下去了，感觉推导变成了一个圆圈

1. 如果$d_r = \frac{(r + 1) \times N_{r+1}}{N_r}$，其中$N_r$的意思是出现r次的词有几个，假设训练集中一个词最多就出现了10次，也就意味着$N_{11}$ 为0，那$d_{11}$ 等于0吗？
2. 正确的推导过程应该是怎样的，怎样得出书中的结果？
3. 在古德——图灵估计中，$d_0$ 的情况是包含在通用的$d_r$ 中的，没有特殊讨论，但古德——图灵估计应用到二元模型后，为什么还有一个专门的otherwise的情况？
4. $f_{gt}$ 具体是什么？
5. $Q(w_{i-1})$ 是什么，为什么是这个样子，最终的二元模型的概率和还是1吗？如何计算？