keyword：统计,概率,马尔可夫

计算机处理自然语言，一个基本问题就是为自然语言这种上下文相关的特性建立数学模型。 这个数学模型就是在自然语言处理中常说的统计语言模型。

数学的方法描述语言规律

统计语言模型产生的初衷是为了解决语音识别问题。 在语言识别中，计算机需要知道一个文字序列是否能构成一个大家理解并且有意义的语句。 基于规则的方法在解决这个问题的时候，试图判断这个文字序列是否合乎文法、含义是否正确。 基于统计的方法则只是“简单”地通过可能性大小来判断这个文字序列是否合法。

假设$S$表示一个文字序列，由一连串顺序排序的单词组成：$S = \underbrace{w_1,w_2,…,w_n}_{n个}$。 我们的目标是想知道$S$在文本中出现的可能性，即数学上的概率$P(S)$。已知：

利用条件概率展开：

上式右项中，越往后的条件概率越难计算。为了简化计算，使用马尔可夫假设进行近似估计。

马尔可夫假设：假设一个当前状态只与之前的一个状态相关。即任意一个词$w_i$只与它的前一个词$w_{i-1}$相关。

因此，问题进一步简化为：

上式对应的统计语言模型是二元模型（Bigram Model）。类比得到：假设一个词由前边的$N-1$个词决定，那么就是N元模型。 那么好了，接下来的问题就是计算条件概率$P(w_i|w_{i-1})$。

即条件概率进一步如上展开为联合概率$P(w_{i-1},w_i)$和边缘概率$P(w_{i-1})$的形式。

而现在我们拥有的数据包括：大量的机读文本（语料库Corpus）。在这些文本中，我们可以数出$w_{i-1},w_i$这对词相邻出现的次数 #$(w_{i-1},w_i)$ ， 以及$w_{i-1}$本身出现的次数 #$(w_{i-1})$ 。整个语料库的大小为 # 。即可得到频度：

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

因此，我们前面推导的条件概率可以表示为：

到此，一个复杂的问题被简化为“数一数”的问题。正如书中所说：数学的精彩之处在于简单的模型可以干大事。

统计语言模型的工程诀窍

下面将更加深入地针对上述模型求解过程中可能遇到的问题进行解答。核心问题包括：模型规模的选取（二元、三元还是四元），训练中零概率问题的解决，语料库的选取

高阶语言模型

前边所说的二元模型对问题的简化有点多，只考虑前边的词会让结果误差过多。因此定义：

上式的假设被称为 N-1阶马尔可夫假设，对应的语言模型称为 N元模型。N = 2 为上面的二元模型；N = 1 为上下文无关的一元模型;实际中应用最多的三元模型。 为什么不用更高阶的模型?原因如下：

• N元模型的大小（空间复杂度）和速度（时间复杂度）几乎都是N的指数函数，即$O(|V|^{N})$，因此N不能很大。

• N从1到2，再从2到3是，模型的效果上升显著。而从3到4时，效果的提升就不是很显著了，而资源浪费增加非常快。

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

前面所说的语言模型需要计算的所有条件概率，我们称之为模型的参数。通过对语料的统计，得到这些参数的过程称作模型的训练。

对于二元模型，#$(w_{i-1},w_{i})$和#$(w_{i-1})$的比值便是模型的参数。但是：

• 如果#$(w_{i-1},w_{i})=0$时，是否意味$P(w_i|w_{i-1})=0?$

• 反过来，如果#$(w_{i-1},w_{i})$和#$(w_{i-1})$都只出现一次，是否意味$P(w_i|w_{i-1})=1?$

这涉及到统计的可靠性问题。在数理统计中，我们之所以敢对采样数据进行观测的结果来预测概率，是因为大数定理的支持，它需要足够的观测值。 而在估计语言模型的概率时，很多训练模型的“不管用”都是忽略了这点，从而出现了零概率和不平滑的问题，导致模型“失效”。为了解决这个问题：

• 增加数据量 – 但是，仍然无法彻底解决零概率或统计不足的问题。因为：

    汉语词汇量大致是20万这个量级，训练三元模型就有$200 000^3 = 8 x 10^{15}$个不同的参数。而假如从互联网上刨去垃圾数据，高估可以有$10^{13}$的训练数据。
    因此仍然会出现条件概率为0的情况，称之为`不平滑`。**统计语言模型中零概率问题无法回避，必须解决**。
  

• 古德-图灵估计（Good-Turing Estimate）：

    对于没有看见的事件，不能认为其发生的概率为零。因此从概率的总量中分配一个很小的比例给这些没有看见的事件。这样一来，看见的那些事件的概率总和就要小于1了。
    因此需要将所有看见的事件概率调小一点。至于调小多少，要根据“越是不可信的统计折扣越多”的方法进行。
  

使用古德-图灵估计进行模型训练的原理和结果如下：

假定在语料库中出现$r$次的词有$N_r$个，未出现的词的数量为$N_0$。语料库的大小为$N$。那么：

出现$r$次词的频度为$rN_r/N$，如果不做优化，这个频度就为这些词的概率估计。而古德-图灵估计则是认为当$r$比较小时，它的统计可能性不可靠， 因此要用一个小于$r$的次数$d_r$来取代它来进行概率估计，从而减小它的概率。自己的理解：减少的部分就给那些零概率的事件了（未看见的），也就对应上了上面说的古德-图灵估计的定义了

可得：

根据Zipf定律：$r$越大，词的数量$N_r$越小：

这样就给未出现的值赋予了一个很小的非零值，从而解决了零值问题。

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

关键点：出现次数越少，折扣越多，对于未出现的词，给予一个很小的概率，实现平滑。

下面给出基于古德-图灵估计给出的二元和三元的模型概率公式：

二元：

其中T为一个阈值，在8-10左右；函数$f_{gt}()$表示古德-图灵估计后的相对频度，而：

这种平滑方法成为卡茨退避法（Katz backoff）。

三元：

语料库的选取

模型训练另一个重要问题就是训练数据的选取。要保证：

• 训练数据和应用数据一致。例如某语言模型的应用是网页搜索，那么训练的语料库就要是网页数据、用户搜索，而不是传统的新闻稿。

• 训练数据足够大。模型阶数越高，训练需要数据越大。

• 训练数据一定程度的去噪预处理。少量的（没有模式的）随机噪声清除成本高，通常不处理；但是能够找到模式（容易匹配）的噪声需要去除，例如网页文本中大量的制表符。