统计语言模型
以下内容摘自和修改自吴军《数学之美》
自然语言从它产生开始，逐渐演变成一种上下文相关的信息表达和传递方式。因此让计算机处理自然语言，一个基本问题就是为自然语言这种上下文相关的特性建立数学模型，这个数学模型就是在自然语言处理中常说的统计语言模型(Statistical Language Model)。它是今天所有自然语言处理的基础，并且广泛应用于机器翻译、语音识别、印刷体或手写体识别、拼写纠错、汉字输入和文献查询。
1. 用数学的方法描述语言规律
统计语言模型产生的初衷是为了解决语音识别问题。在语音识别中，计算机需要知道一个文字序列是否能构成一个大家理解并且有意义的句子，然后显示或打印给使用者。
比如：
美联储主席本·伯南克昨天告诉媒体 7000 亿美元的救助资金将借给上百家银行、保险公司和汽车公司。
这句话就很通顺，意义也很明白。
如果改变一些词的顺序，或者替换掉一些词，将这句话变成：
本·伯南克美联储主席昨天 7000 亿美元的救助资金告诉媒体将借给银行、保险公司和汽车公司上百家。
意思就含混了，虽然多少还能猜到一点。
但如果再换成：
联主美储席本·伯诉体南将借天的救克告媒昨助资金 70 元亿 00 美给上百百百家银保行、汽车险公司公司和。
基本上读者就不知所云了。
第一个句子合乎语法，词义清晰。第二个句子虽不合乎语法，但是词义还算清晰。而第三个句子则连词义都不清晰了。上世纪 70 年代以前，科学家们也是这样想的，他们试图判断这个文字序列是否合乎文法、含义是否正确等。但是语言的结构千变万化，要通过制定规则来覆盖所有的文法根本是不可能的。而弗里德里克·贾里尼克(Frederick Jelinek)换了一个角度，用一个简单的统计模型就很漂亮地搞定了这个问题。
贾里尼克的想法
贾里尼克的出发点很简单：一个句子是否合理，就看它的可能性大小如何。上面的例子中，第一个句子出现的概率大致是$10^{−20}$，第二个句子出现的概率是 $10^{−25}$，第三个句子出现的概率是 $10^{−70}$。因此第一个句子出现的可能性最大，是第二个句子的 10万倍，是第三个句子的一百亿亿亿亿亿亿倍。
用更普遍而严格的描述是：
假定 SS 是一个有意义的句子，由一连串特定顺序排列的词 $w_1,w_2,⋯,w_n$组成，n为句子的长度。那么 S 在文本中出现的可能性就是 S 的概率 P(S)。于是可以把 P(S) 展开表示为：
$P(S)=P(w_1,w_2,⋯,w_n)$
利用条件概率公式，SS 这个序列出现的概率等于每一个词出现的条件概率相乘，于是：
$P(w_{1},w_{2},⋯,w_{n})=P(w_{1})⋅P(w_{2}∣w_{1})⋅P(w_{3}∣w_{1},w_{2})⋯P(w_{n}∣w_{1},w_{2},⋯,w_{n−1})P(w_{1},w_{2},⋯,w_{n})=P(w_{1})⋅P(w_{2}∣w_{1})⋅P(w_{3}∣w_{1},w_{2})⋯P(w_{n}∣w_{1},w_{2},⋯,w_{n−1})$
其中 $P(w_{1})$ 表示句子第一个词为 $w_1$ 的概率；$P(w_{2}∣w_{1})$ 是在已知第一个词的前提下，第二个词出现的概率；以此类推。不难看出，词 $w_n$ 的出现概率取决于它前面所有的词。
$P(w_{1})$ 更准确的描述是 $P(w_{1}∣BOS)$ 即这个词在句子开头出现的概率。
从计算上来看，第一个词的条件概率 $P(w_{1})$ 很容易算，第二个词的条件概率 $P(w_{2}∣w_{1})$ 也还不太麻烦，但是从第三个词的条件概率 $P(w_{3}∣w_{1},w_{2})$ 开始就非常难算了，因为它涉及到三个变量 $w_{1},w_{2},w_3$，而每个变量的可能性都是一种语言字典的大小。到了最后一个词 $w_n$，条件概率 $P(w_{n}∣w_{1},w_{2},⋯,w_{n−1})$ 的可能性太多，根本无法估算。
二元模型与 N 元模型
从 19 世纪到 20 世纪初，俄国有个数学家叫马尔可夫(Andrey Markov)，他提出了一种偷懒但还颇为有效的方法：假设任意一个词语 wiwi 出现的概率只同它前面的词 wi−1 有关。于是问题就变得很简单了，这种假设在数学上称为马尔可夫假设。
马尔可夫在 1906 年首先做出了这类过程，而将此一般化到可数无限状态空间是由柯尔莫果洛夫在 1936 年给出的。
现在，S 出现的概率就变得简单了：
$P(S)=P(w_{1})⋅P(w_{2}∣w_{1})⋅P(w_{3}∣w_{2})⋯P(w_{i}∣w_{i−1})⋯P(w_{n}∣w_{n−1})$
上面的公式对应的统计语言模型是二元模型(Bigram Model)。当然，也可以假设一个词由前面的 N−1 个词决定，对应的模型稍微复杂些，被称为 N 元模型。
接下来的问题就是如何估计条件概率 $P(w_{i}∣w_{i−1})$。根据它的定义：
$P(w_{i}∣w_{i−1})=P(w_{i−1},w_{i})P(w_{i−1})P(w_{i}∣w_{i−1})=P(w_{i−1},w_{i})P(w_{i−1})$
而估计联合概率 $P(w_{i−1},w_{i})$ 和边缘概率 $P(w_{i−1})$ 是很简单的。根据大数定理，只要统计量足够，相对频度就等于概率，因而只需在语料库(Corpus)的文本中统计一下 $w_{i−1},w_i$ 这对词前后相邻出现了多少次 $N(w_{i−1},w_{i})$，以及 $w_{i−1}$ 出现了多少次 $N(w_{i−1})$，然后用两个数分别处以语料库的大小 N，即可得到这些词或者二元组的概率：
$$P(w_{i-1},w_i)=f(w_{i-1},w_i)=\frac{N(w_{i-1},w_i)}{N} \ P(w_{i-1})=f(w_{i-1})=\frac{N(w_{i-1})}{N}$$
$$P(w_{i-1},w_i)=f(w_{i-1},w_i)=\frac{N(w_{i-1},w_i)}{N} \ P(w_{i-1})=f(w_{i-1})=\frac{N(w_{i-1})}{N}$$
于是，
$$P(w_i\mid w_{i-1})\approx\frac{N(w_{i-1},w_i)}{N(w_{i-1})}$$
这似乎有点难以置信，用这么简单的数学模型就能解决复杂的语音识别、机器翻译等问题，而用很复杂的文法规则和人工智能却做不到。其实很多语言学家都曾质疑过这种方法的有效性，但事实证明，统计语言模型比任何已知的借助某种规则的解决方法更有效。
2. 高阶语言模型
在基于一阶马尔可夫假设的二元模型中，句子中每个词只和前面一个词有关，这似乎过于简化了，或者说近似地过头了。比如说在句子“美丽的花朵”中，“花朵”其实是和“美丽”有关，也就是说是与前面的第二个词有关。因此，更普遍的假设是某个词和前面的若干个词有关。
正如之前介绍的那样，N 元模型假设每个词 $w_i$ 和前面的 N−1 个词有关，而与更前面的词无关，这样词 $w_i$ 的概率只取决于前面的 N−1 个词 $w_{i−N+1},w_{i−N+2},⋯,w_{i−1}$。因此：
$$P(w_i\mid w_1,w_2,\cdots,w_{i-1})=P(w_i\mid w_{i-N+1},w_{i-N+2},\cdots,w_{i-1})$$
这种假设被称为 N−1 阶马尔可夫假设，对应的语言模型称为 N 元模型(N-Gram Model)。N=2时就是之前介绍的二元模型，而 N=1 的一元模型实际上是一个上下文无关模型，即假定当前词的出现概率与前面的词无关。在实际中应用最多的就是 N=3 的三元模型，更高阶的模型就很少使用了。
为什么 N 取值这么小？
首先，N 元模型的大小（空间复杂度）几乎是 N 的指数函数，即 $O(|V|^N)$，这里 |V|是一种语言词典的词汇量，一般在几万到几十万个。其次，使用 N 元模型的速度（时间复杂度）也几乎是一个指数函数，即 $O(|V|^{N−1})$。因此，N 不能很大。
当 N 从 1 到 2，再从 2 到 3 时，模型的效果上升显著。而当模型从 3 到 4 时，效果的提升就不是很显著了，而资源的耗费却增加地非常快。所以，除非是为了做到极致不惜资源，很少有人会使用四元以上的模型。
还有一个问题，三元、四元或更高阶的模型也并不能覆盖所有的语言现象。在自然语言处理中，上下文之间的相关性可能跨度非常大，甚至可以从一个段落跨到另一个段落。因此，即便再怎么提高模型的阶数，对这种情况也无可奈何，这就是马尔可夫模型的局限性，这是就需要采用其他一些长程的依赖性(Long Distance Dependency)来解决这个问题了。
3. 模型的训练、零概率问题和平滑方法
语言模型中所有的条件概率称为模型的参数，通过对语料的统计，得到这些参数的过程称为模型的训练。前面提到的二元模型训练方法似乎非常简单，只需计算一下 $w_{i−1},w_i$ 前后相邻出现的次数 $N(w_{i−1},w_{i})$ 和 $w_{i−1}$ 单独出现的次数 $N(w_{i−1})$ 的比值即可。但是如果同现的次数 $N(w_{i−1},w_{i})=0$ 怎么办，是否意味着条件概率 $P(w_{i}∣w_{i−1})=0$？反之，如果 $N(w_{i−1},w_{i})$ 和 $N(w_{i−1})$ 都只出现一次，能否得出 $P(w_{i}∣w_{i−1})=1$ 这样非常绝对的结论？
这就涉及到统计的可靠性问题了。在数理统计中，我们之所以敢用对采样数据进行观察的结果来预测概率，是因为有大数定理(Law of Large Number)在背后做支持，它的要求是有足够的观察值。但是在估计语言模型的概率时，很多人恰恰忘了这个道理，因此训练出来的语言模型“不管用”，然后回过头来怀疑这个方法是否有效。那么如何正确地训练一个语言模型呢？
一个直接的办法就是增加数据量，但是即使如此，仍会遇到零概率或者统计量不足的问题。假定要训练一个汉语的语言模型，汉语的词汇量大致是 20 万这个数量级，训练一个三元模型就有 $200,000^3=8×10^{15} $个不同参数。假设抓取 100 亿个有意义的中文网页，每个网页平均 1000 词，全部用作训练也依然只有 $10^{13}$。因此，如果用直接的比值计算概率，大部分条件概率依然是零，这种模型我们称之为“不平滑”。
训练统计语言模型的艺术就在于解决好统计样本不足时的概率估计问题。
古德-图灵估计
1953 年古德(I.J.Good)在他的老板图灵(Alan Turing)的指导下，提出了在统计中相信可靠的统计数据，而对不可信的统计数据打折扣的一种概率估计方法，同时将折扣出的那一小部分概率给予未看见的事件(Unseen Events)。古德和图灵还给出了一个很漂亮的重新估算概率的公式，这个公式后来被称为古德-图灵估计(Good-Turing Estimate)。
古德-图灵估计的原理是：对于没看见的事件，我们不能认为它发生的概率就是零，因此我们从概率的总量(Probability Mass)中，分配一个很小的比例给这些没有看见的事件。这样一来，看见了的事件的概率总和就小于 1了。因此，需要将所有看见了的事件概率调小一点，并且按照“越是不可信的统计折扣越多”的方法进行。
以统计词典中每个词的概率为例：假定在语料库中出现 r 次的词有 $N_r$ 个，特别地，未出现的词数量为 $N_0$。语料库的大小为 N。那么，很显然
$$N=\sum_{r=1}^{\infty}rN_r$$
出现 r 次的词在整个语料库中的相对频度(Relative Frequency)则是 $r/N$，如果不做任何优化处理，就以这个相对频度作为这些词的概率估计。现在假定当 r 比较小时，它的统计可能不可靠，因此在计算那些出现 r 次的词的概率时，要使用一个更小一点的次数，是 $d_r$（而不直接使用r），古德-图灵估计按照下面的公式计算$d_r$：
$$d_r = (r+1)\cdot N_{r+1}/N_r$$
显然
$$\sum_rd_r\cdot N_r=N$$
根据 $Zipf$ 定律，一般情况下 $N_{r+1}<N_r$，因而 $d_r<r$，而 $d_0>0$。这样就给未出现的词赋予了一个很小的非零值，从而解决了零概率的问题。同时下调了出现频率很低的词的概率。实际运用中，一般只对出现次数低于某个阈值的词下调频率，然后把下调得到的频率总和给未出现的词。
一般来说，出现一次的词的数量比出现两次的多，出现两次的比出现三次的多，这种规律称为 Zipf定律(Zipf’s Law)，即 r 越大，词的数量 $N_r$ 越小。
这样出现 r 次的词的概率估计为$d_r/N$。于是，对于频率超过一定阈值的词，它们的概率估计就是它们在语料库中的相对频度，对于频率小于阈值的词，它们的概率估计就小于它们的相对频度，并且出现次数越少，折扣越多。对于未看见的词，也给与了一个比较小的概率。这样所有词的概率估计都很平滑了。
卡茨退避法
对于二元组 $(w_{i−1},w_{i})(w_{i−1},w_{i})$ 的条件概率估计 $P(w_{i}∣w_{i−1})$也可以做同样的处理。我们知道，通过前一个词 $w_{i−1}$ 预测后一个词 $w_i$ 时，所有的可能情况的条件概率总和应该为 1，即
$$\sum_{w_i\in V}P(w_i\mid w_{i-1})=1$$
对于出现次数非常少的二元组 $(w_{i−1},w_{i})(w_{i−1},w_{i})$，需要按照古德-图灵的方法打折扣，这样 $\sum_{w_{i-1},w_i\text{ seen}}P(w_i\mid w_{i-1})\lt 1$，这意味着有一部分概率量没有分配出去，留给了没有看到的二元组 $(w_{i−1},w_{i})(w_{i−1},w_{i})$。基于这种思想，估计二元模型概率的公式为：
$$P(w_i\mid w_{i-1})=\begin{cases}f(w_i\mid w_{i-1})\quad\text{if }N(w_{i-1},w_i) \ge T \f_{gt}(w_i\mid w_{i-1})\quad\text{if }0\lt N(w_{i-1},w_i)\lt T \ Q(w_{i-1})\cdot f(w_i)\quad\text{otherwise}\end{cases}$$
其中 T 是阈值，一般在 8−10 左右，函数 $f_{gt}()$ 表示经过古德-图灵估计后的相对频度，而
$$Q(w_{i-1})=\frac{1-\sum_{w_i \text{ seen}}P(w_i\mid w_{i-1})}{\sum_{w_i\text{ unseen}}f(w_i)}$$
这样可以保证所有的可能情况的条件概率总和为 11。
这种平滑方法最早由前 IBM 科学家卡茨(S.M.Katz)提出，故称为卡茨退避法(Katz backoff)。类似地，对于三元模型，概率估计的公式如下：
$$P(w_i\mid w_{i-2},w_{i-1})=\begin{cases}f(w_i\mid w_{i-2},w_{i-1})\quad\text{if }N(w_{i-2,}w_{i-1},w_i) \ge T \f_{gt}(w_i\mid w_{i-2,}w_{i-1})\quad\text{if }0\lt N(w_{i-2},w_{i-1},w_i)\lt T \ Q(w_{i-2},w_{i-1})\cdot P(w_i\mid w_{i-1})\quad\text{otherwise}\end{cases}$$
对于一般情况的 N 元模型概率估计公式，以此类推。
内伊(Herman Ney)等人在此基础上优化了卡茨退避法，原理大同小异。
线性插值
因为一元组 $(w_{i})$ 出现的次数平均比二元组 $(w_{i−1},w_{i})$ 出现的次数要多很多，根据大数定律，它的相对频度更接近概率分布。类似地，二元组平均出现的次数比三元组要高，二元组的相对频度比三元组更接近概率分布。同时，低阶模型的零概率问题也比高阶模型轻微。因此，用低阶语言模型和高阶模型进行线性插值来达到平滑的目的，也是过去行业中经常使用的一种方法，这种方法称为删除插值(Deleted Interpolation)，详见下面的公式：
$$P(w_i\mid w_{i-2},w_{i-1})=\lambda(w_{i-2},w_{i-1})\cdot f(w_i\mid w_{i-2},w_{i-1}) +\lambda(w_{i-1})\cdot f(w_i\mid w_{i-1})+\lambda f(w_i)$$
其中，三个 λ 为插值权重，均为正数且和为 1。
线性插值法的效果比卡茨退避法略差，故现在已经较少使用了。
