统计语言模型

语言模型概述

语言模型(Language Model)，就是用来计算一个句子概率的模型。从统计的角度看，自然语言中的一个句子可以由任何词串构成。不过P(s)有大有小。比如：

s1 = 我刚吃过晚饭
s2 = 刚我过晚饭吃

可以看出P(s1)>P(s2)。对于给定的句子而言，通常P(s)是未知的。对于一个服从某个概率分布P的语言L，根据给定的语言样本估计P的过程被称作语言建模。
根据语言样本估计出的概率分布P就称为语言L的语言模型。
$$\sum_{s\in L}P(s)=1$$
语言建模技术首先在语音识别研究中提出，后来陆续用到OCR、手写体识别、机器翻译、信息检索等领域。在语音识别中，如果识别结果有多个，则可以根据语言模型计算每个识别结果的可能性，然后挑选一个可能性较大的识别结果。语言模型也可以用于汉语歧义消解。
那么如何计算一个句子的概率呢？对于给定的句子:
$$S=w_1w_2,…,w_n$$
它的概率可以表示为：
$$P(S)=P(w_1,w_2,…,w_n)=P(w_1)P(w_2|w_1)…P(w_n|w_1,w_2,…,w_{n-1})$$
由于上面的式子参数过多，因此需要近似的计算方法，常见的方法有n-gram模型方法、决策树方法、最大熵模型方法、最大熵马尔科夫模型方法、条件随机场(CRF)方法、神经网络方法等。本篇文章主要记录n-gram模型方法。

n-gram模型

对于给定的句子$S=w_1w_2…w_n,$,根据链式规则:
$$
P(S)=P(w_1,w_2,…,w_n)=P(w_1)P(w_2|w_1)…P(w_n|w_1,w_2,…,w_{n-1})=\prod_{i=1}^np(w_i|w_1…w_{i-1})
$$
P(S)就是语言模型，即用来计算一个句子S概率的模型。
那么，如何计算$p(w_i|w_1,w_2,…,w_{i-1})$呢？最简单、直接的方法是计数后做除法，即最大似然估计(Maximum Likelihood Estimate，MLE)，如下：
$$
p(w_i|w_1,w_2,…,w_{i-1})=\frac {count(w_1,w_2,…,w_{i-1},w_i)}{count(w_1,w_2,…,w_{i-1})}
$$
其中，$count(w_1,w_2,…,w_{i-1},w_i)$表示次序列$(w_1,w_2,…,w_{i-1},w_i)$在预料库中出现的频率。

这里面临两个重要的问题：数据稀疏严重和参数空间过大，导致无法实用。实际中，我们一般较长使用N语法模型(n-gram)，它采用了马尔科夫假设，即认为语言中的每个词只与其前面长度为n-1的上下文有关。

假设下一个词的出现不依赖前面的词，即为uni-gram，则有:$$ \begin {aligned}
P(S)&=P(w_1)P(w_2|w_1)p(w_3|w_2,w_1)…p(w_n|w_1,w_2,…,w_{n-1})\\\\&=p(w_1)p(w_2)…p(w_n)
\end{aligned}$$
假设下一个词的出现只依赖前面的一个词，即为bi-gram，则有：$$ \begin {aligned}
P(S)&=P(w_1)P(w_2|w_1)p(w_3|w_2,w_1)…p(w_n|w_1,w_2,…,w_{n-1})\\\\&=p(w_1)p(w_2|w_1)p(w_3|w_2)…p(w_n|w_{n-1})
\end{aligned}$$
假设下一个词的出现依赖它前面的两个词，即为tri-gram，则有：
$$
\begin {aligned} P(S)&=P(w_1)P(w_2|w_1)p(w_3|w_2,w_1)…p(w_n|w_1,w_2,…,w_{n-1})\\\\&=p(w_1)p(w_2|w_1)p(w_3|w_1,w_2)…p(w_n|w_{n-2},w_{n-1})
\end {aligned}
$$

实际上常常在对数空间里面计算概率，原因有两个：

防止溢出；如果计算的句子很长，那么最后得到的结果将非常小，甚至会溢出，比如计算得到的概率是0.001，那么假设以10为底取对数的结果就是-3，这样就不会溢出；
对数空间里面加法可以代替乘法，因为log(p1p2) = logp1 +logp2，在计算机内部，显然加法比乘法执行更快；

n-gram中的n如何选择？

n较大时：提供了更多的上下文语境信息，语境更具有区别性；但是，参数个数多、计算代价大、训练预料需要多，参数估计不可靠；
n较小时：提供的上下文语境少，不具有区别性；但是，参数个数小、计算代价小、训练预料无须太多、参数估计可靠；

理论上，n越大越好，经验上tri-gram用的最多，尽管如此，原则上，能用bi-gram解决，绝不使用tri-gram。

建立n-gram语言模型

构建n-gram语言模型，通过计算最大似然估计构造语言模型。一般的过程如下：

1、数据准备：
- 确定训练语料
- 对语料进行tokenization或切分
- 句子边界，增加特殊的词和开始和结束
2、参数估计：
- 利用训练语料，估计模型参数

令$c(w_1,…,w_n)$表示n-gram $w_1,…,w_n$在训练语料中出现的次数，则：
$$
P_{MLE}(w_n|w_1,…,w_{n-1})=\frac {c(w_1,…,w_n)}{c(w_1,…,w_{n-1})}
$$

语言模型效果评估

目前主要有两种方法判断建立的语言模型的好坏：

实用方法：通过查看该模型在实际应用（如拼写检查、机器翻译）中的表现来评价，优点是直观、实用，缺点是缺乏针对性、不够客观；
理论方法：困惑度(preplexity)，其基本思想是给测试集赋予较高概率值的语言模型较好；

平滑方法

最大似然估计给训练样本中未观察到的事件赋以0概率。如果某个n-gram在训练语料中没有出现，则该n-gram的概率必定是0。这就会使得在计算某个句子S的概率时，如果某个词没有在预料中出现，那么该句子计算出来的概率就会变为0，这是不合理的。
解决的办法是扩大训练语料的规模。但是无论怎样扩大训练语料，都不可能保证所有的词在训练语料中均出现。由于训练样本不足而导致估计的分布不可靠的问题，称为数据稀疏问题。在NLP领域中，稀疏问题永远存在，不太可能有一个足够大的语料，因为语言中的大部分词都属于低频词。

Zipf定律

Zipf定律描述了词频以及词在词频表中的位置之间的关系。针对某个语料库，如果某个词w的词频是f，并且该词在词频表中的序号为r(即w是所统计的语料中第r常用词)，则：
$$f*r=k(k是一个常数)$$
若$w_i$在词频表中的排名50，$w_j$在词频表中排名为150，则$w_i$的出现频率大约是$w_j$的频率的3倍。
Zipf定律告诉我们：

语言中只有很少的常用词
语言中的大部分词都是低频词（不常用的词)

Zipf的解释是Principle of Lease effort

说话的人只想使用少量的常用词进行交流
听话的人只想使用没有歧义的词（量大低频）进行交流

Zipf定律告诉我们：

对于语言中的大多数词，它们在语料中出现是稀疏的
只有少量的词语料库可以提供它们规律的可靠样本

平滑技术

对于语言而言，由于数据稀疏的存在，MLE不是一种很好的参数估计方法。为了解决数据稀疏问题，人们为理论模型实用化而进行了众多的尝试，出现了一系列的平滑技术，它们的基本思想是降低已出现n-gram的条件概率分布，以使未出现的n-gram条件概率分布为非零，且经过平滑后保证概率和为1。目前，已经提出了很多数据平滑技术，如下：

Add-one平滑
Add-delta平滑
Good-Turing平滑
Interpolation平滑
回退模型-Katz平滑
…

Add-one平滑

加一平滑法，又称为拉普拉斯定律，其规定任何一个n-gram在训练预料中至少出现一次（即规定没有出现过的n-gram在训练预料中出现了1次）

$$P_{Add1}(w_1,w_2,…,w_n)=\frac {C(w_1,w_2,…,w_n)+1}{N+V}$$

N:为训练预料中所所有的n-gram的数量(token);
V:所有的可能的不同的n-gram的数量(type);
下面两幅图分别演示了未平滑和平滑后的bi-gram示例：

mark

(注：上图均来自《计算语言学-常宝宝》的课件)

训练语料中未出现的n-gram的概率不再为0，而是一个大于0的较小的概率值。但是，由于训练预料中未出现的n-gram数量太多，平滑后，所有未出现的n-gram占据了整个概率分布中的一个很大的比例。因此，在NLP中，Add-one给训练预料中没有出现过的n-gram分配太多的概率空间。同时，它认为所有未出现的n-gram概率相等，这是否合理？出现在训练语料中的哪些n-gram，都增加同样频度值，不一定合理。

Add-delta平滑

Add-delta平滑，不是加1，而是加一个比1小的整数$\lambda$:
$$
P_{AddD}(w_1,w_2,…,w_n)=\frac {C(w_1,w_2,…,w_n)+\lambda}{N+\lambda V}
$$
通常$\lambda =0.5$，此时又称为Jeffreys-Perks Law或ELE。它的效果要比Add-one好，但是仍然不理想。

Good-Turing平滑

其基本思想是利用频率的类别信息对频率进行平滑。假设N是样本数据的大小，$n_r$是在样本中正好出现r次的事件的数目(在这里，事件为n-gram $w_1,w_2,…,w_n$)。即：出现1的$n_1$个，出现2次的$n_2$个,…。那么：
$$
N=\sum_{r=1}^{\infty} n_r r
$$
由于，$$N=\sum_{r=0}^{\infty}n_r r^*=\sum_{r=0}^{\infty}(r+1)n_{r+1}$$，所以，
$$
r^* = (r+1)\frac {n_{r+1}}{n_r}
$$

那么，Good-Turing估计在样本中出现r次的事件的概率为:
$$
P_r = \frac {r^*}{N}
$$
实际应用中，一般直接使用$n_{r+1}$代替$E(n_{r+1})$，$n_r$代替$E(n_r)$。这样，样本中所有事件的概率之和为：
$$
\sum_{r>0} n_r * P_r = 1 - \frac {n_1}{N} <1
$$
因此，有$\frac {n_1}{N}$的剩余的概率量就可以均分给所有未出现事件(r=0)。
Good-Turing估计适用于大词汇集产生的符合多项式分布的大量的观察数据。
在估计频度为r的n-gram的概率$p_r$时，如果数据集中没有频度为r+1的n-gram怎么办？此时，$N_{r+1}=0$导致$p_r=0$。解决的办法是对$N_r$进行平滑，设S(.)是平滑函数，S(r)是$N_r$的平滑值。
$$
r^* = (r+1)\frac {S(r+1)}{S(r)}
$$

Interpolation平滑

不管是Add-one，还是Good Turing平滑技术，对于未出现的n-gram都一视同仁，难免存在不合理性。所以介绍一种线性差值的的平滑技术，其基本思想是将高阶模型和低阶模型作线性组合，利用低阶n-gram模型对高阶n-gram模型进行线性差值。因为没有足够的数据对高阶n-gram模型进行概率估计时，低阶的n-gram模型通常可以提供有用的信息。因此，可以把不同阶的n-gram模型组合起来产生一个更好的模型。

把不同阶别的n-gram模型线性加权组合：
$$P(w_n|w_{n-1},w_{n-2})=\lambda_1P(w_n)+\lambda_2P(w_n|w_{n-1})+\lambda_3P(w_n|w_{n-1}w_{n-2})$$
其中，$0<=\lambda_i<=1,\sum_i \lambda_i=1$。$\lambda_i$可以根据实验凭经验设定，也也可以通过应用某些算法确定，例如EM算法。

回退模型-Katz平滑

回退模型-Katz平滑，其基本思想是：当某一事件在样本中出现的概率大于K(通常K为0或1)，运用最大似然估计减值来估计其概率，否则使用低阶的，即(n-1)gram概率代替n-gram概率。而这种替代必须受归一化因子$\alpha$的作用。回退模型的一般形式如下：
$$
p_{smooth}(w_i|w_{i-n+1}^{i-1})=\begin{cases}
\hat p(w_i|w_{i-n+1}^{i-1}), & if c(w_{i-n+1}^i)>0 \\
\alpha(w_{i-n+1}^{i-1})\cdot p_{smooth}(w_i|w_{i-n+2}^{i-1}), & if c(w_{i-n+1}^{i-1})=0
\end{cases}$$
参数$\alpha(w_{i-n+1}^{i-1})$是归一化因子，以保证$$\sum_{w_i}p_{smooth}(w_i|w_{i-n+1}^{i-1})=1$$
以bi-gram为例，令$r=c(w_{i-1}w_i)$，如果r>0，则$p_{katz}(w_i|w_{i-1})=d_r\cdot p_{ML}(w_i|w_{i-1})$，$d_r$称为折扣率，给定$w_{i-1}$，从r>0的bi-grams中折除的概率为：$$
S(w_{i-1}) = 1 - \sum_{w_i \in M(w_{i-1})} p_{katz}(w_i|w_{i-1}) \\其中，M(w_{i-1})={w_i|c(w_{i-1}w_i)>0}
$$

对于给定的$w_{i-1}$，令：$$
Q(w_{i-1}) = {w_i|c(w_{i-1}w_i)=0}
$$
如何把$S(w_{i-1})$分配给集合$Q(w_{i-1})$中的那些元素？

对于$w_i \in Q(w_{i-1})$，如果$p_{ML}(w_i)$比较大，则应该分配更多的概率给它。所以，若r=0，则：$$
p_{katz}(w_i|w_{i-1})=\frac {p_{ML}(w_i)}{\sum_{w_j\in Q}p_{ML}(w_j)} \cdot S(w_{i-1})
$$
对于bi-gram模型，Katz平滑为：
$$p_{katz}(w_i|w_{i-1})=
\begin{cases}
d_r\cdot p_{ML}(w_i|w_{i-1}), & if r>0 \\
\alpha(w_{i-1}) \cdot p_{ML}(w_i), & if r=0
\end{cases}
\\
其中，\alpha(w_{i-1}) = \frac {1 - \sum_{w_j\in M} p_{katz}(w_j|w_{j-1}) }{\sum_{w_j\in Q} p_{ML}(w_j)}
$$

如何计算$d_r$?

如果$r>k$，不折扣，即$d_r=1$(Katz提出k=5)
如果$0<r \leq k$，按照和Good-Turing估计同样的方式折扣，即按照$\frac {r^{*}}{r}$进行折扣。严格说，要求$d_r$满足，$1-d_r=u(1-\frac {r^{*}}{r})$
根据Good-Turing估计，未出现的n元组估计出现频次是$n_1$，$\sum_{r=1}^k n_r(1-d_r)r=n$
具体而言，若$0<r \leq k$，有$$
d_r = \frac {\frac {r^*}{r} - \frac {(k+1)n_{k+1}}{n_1}} {1 - \frac {(k+1)n_{k+1}}{n!}}
$$

big-gram的Katz平滑模型最终可描述为：
$$p_{katz}(w_i|w_{i-1})=\begin{cases}
c(w_{i-1}w_i)/c(w_{i-1}), & if r>k \\
d_rc(w_{i-1}w_i)/c(w_{i-1}), & if k \geq r > 0 \\
\alpha (w_{i-1})p_{katz}(w_i) & r=0
\end{cases}
$$
n-gram模型的Katz平滑可以此类推。
在回退模型和线性插值模型中，当高阶n-gram未出现时，使用低阶n-gram估算高阶n-gram的概率分布。在回退模型中，高阶n-gram一旦出现，就不再使用低阶n-gram进行估计。在线性插值模型中，无论高阶n-gram是否出现，低阶n-gram都会被用来估计高阶n-gram的概率分布。

大规模n-gram的优化

如果不想自己动手实现n-gram语言模型，推荐几款开源的语言模型项目：

SRILM(http://www.speech.sri.com/projects/srilm/)
IRSTLM(http://hlt.fbk.eu/en/irstlm)
MITLM(http://code.google.com/p/mitlm/)
BerkeleyLM(http://code.google.com/p/berkeleylm/)

在使用 n-gram 语言模型时，也有一些技巧在里面。例如，面对 Google N-gram 语料库，压缩文件大小为 27.9G，解压后 1T 左右，如此庞大的语料资源，使用前一般需要先剪枝（Pruning）处理，缩小规模，如仅使用出现频率大于 threshold 的 n-gram，过滤高阶的 n-gram（如仅使用 n<=3 的资源），基于熵值剪枝，等等。

另外，在存储方面也需要做一些优化:

采样Trie数的数据结构，可以优化时间复杂度为$O(log_{|V|}m)$|V|为字母的个数；
借助Bloom filter辅助查询，把String映射为int类型处理；
利用郝夫曼树对词进行编码，将词作为索引值而不是字符串进行存储，能将所有词编码成包含在2个字节内的索引值；
优化概率值存储，概率值原使用的数据类型是（float），用4-8bit来代替原来8Byte的存储内容；

N-gram模型的缺陷

数据稀疏问题：利用平滑技术解决；
空间占用大；
长距离依赖问题；
多义性；
同义性；如 “鸡肉”和“狗肉”属于同一类词，p(肉|鸡)应当等于p(肉|狗)，而在训练集中学习到的概率可能相差悬殊；

语言模型应用

n-gram距离

假设有一个字符串s，那么该字符串的n-gram就表示按长度n切分原词得到的词段，也就是s中长度为n的子串。假设有两个字符串，然后分别求它们的n-gram，那么就可以从它们的共有子串的数量这个角度定义两个字符串间的n-gram距离。但是仅仅是简单地对共有子串进行计数显然也存在不足，这种方案忽略了两个字符长度的差异，可能导致的问题。比如，字符串girl和girlfriend，二者拥有的公共子串数量显然与girl和其自身所拥有的公共子串数量相等，但是不能认为girl和girlfriend是两个等同的匹配。为解决该问题，有学者便提出以非重复的n-gram分词为基础来定义n-gram距离这一概念，可以用下面的公式来表述：

$$|G_N(s)|+|G_N(t)|-2*|G_N(s)\cap G_N(t)|$$

例如，字符串s=”ABC”，t=”AB”，分别在字符串首尾加上begin和end，采用二元语言模型，字符串s产生的bi-gram为：(begin,A),(A,B),(B,C),(C,end)；字符串t产生的bi-gram为：(begin,A),(A,B),(B,end)。
采用上面公式定义:4+3 - 2*2 = 3
显然，字符串之间的距离越小，它们就越接近。当两个字符串完全相等的时候，它们之间的距离就是0。

分词

分词是NLP中一项比较基础且重要的任务。对于X=”我爱中国”这样一句话，有多种切分方案，对于$y_i$这种分词方案，如,$Y_0=(“我”，“爱”，“中国”),Y_1=(“我”，“爱中”，“国”)$，利用贝叶斯公式可以计算出每种切分的概率:$$
P(Y_i|X)=\frac {P(X|Y_i)P(Y_i)}{P(X)}\propto P(X|Y_i)P(Y_i),i=1,2,3,…
$$
无论在哪种$Y_i$下，最终都能生成句子X，因此$P(X|Y_i)=1$，所以$P(Y_i|S)\propto P(Y_i),i=1,2,3…$。所以，只需要最大化$P(Y_i)即可$。例如，根据bi-gram语言模型，$P(Y_0|X)\propto P(Y_0)=P(我)P(爱|我)P(中国|爱)$，$P(Y_1|X)\propto P(Y_1)=P(我)P(爱中|我)P(国|爱中)$，然后利用计算出的概率，选择最大的作为分词方案。

词性标注

词性标注（POS tagging）是一个典型的多分类问题，将每个词标注为名词、动词、形容词、副词、代词等。例如，在“我/爱/中国”句话中，“爱”有很多词性，比如，名词、动词。最简单的标注其语义的方案就是，看语料库中“爱”出现的次数，以及其词性，即：
$$
P(POS_i|爱)=\frac {c(“爱”作为POS_i )}{c(爱),i=1,2,…,k，k为词性总数}
$$
但是，这种简单的词性标注的方案依赖人工，且未考虑上下文。考虑到在一个句子中当前词的词性和前面一两个词关系比较大。因此，可以借用n-gram模型的思路进行求解。比如，在考虑“爱”的词性时，以前面一个词的词性作为参考，即“我”的词性，则，当前这个“爱”的词性概率分布为:
$$P(POS_i|我，爱)=P(POS_i|Pron.,爱)=\frac {前面被“副词”修饰的“爱”的POS_i}{c(前面被“副词”修饰的“爱”)},i=1,2,…,k,k为词性总数$$

计算这个概率需要对语料库进行统计。但是，前提是先判断好“我”的词性。因为，采用的是bi-gram模型，由于“我”已经是第一个词，在二元模型中主需要级简的方案判断即可。

n-gram作为文本特征

在处理文本的特征的时候，通常一个关键词作为一个特征。但是，在某些场景下可能词的表达能力不够，需要提取更多的特征，n-gram就是一个很好的特征。以bi-gram为例，在原始文本中，每个关键词可以作为一个特征，将每个关键词两两组合，得到一个bi-gram组合，在根据n-gram语言模型，计算各个bi-gram组合的概率，作为新的特征。