语言模型（language model，LM）目前主要采用的是n元语法模型（n-gram model），这种模型构建简单、直接，但同时也因为数据缺乏而必须采取平滑（smoothing）算法。
本章主要介绍n元语法的基本概念和几种常用的数据平滑方法。
n元语法
一个语言模型通常构建为字符串 $ s$ 的概率分布 $ p(s)$ ，这里 $ p(s)$ 试图反映的是字符串 $ s$ 作为一个句子出现的频率。
对于一个由 $ l$ 个基元（“基元”可以为字、词或短语等，为了表述方便，之后统一用“词”来通指）构成的句子 $ s = w_1w_2 \cdots w_l$ ，其概率计算公式可以表示为：
$$
p(s) = p(w_1)p(w_2|w_1)p(w_3|w_1w_2) \cdots p(w_l|w_1 \cdots w_{l - 1})
= \prod ^{l} _{i = 1} {p(w_i | w_1 \cdots w _{i-1} )}
$$
式中，产生第 $ i$ 个词的概率是由已经产生的 $ i - 1$ 个词 $ w_1w_2 \cdots w_{i - 1}$ 决定的。
如果直接这么算的话，自由参数太多，我们几乎不可能从训练数据中正确地估计出这些参数，而且实际上，绝大多数历史根本就不可能在训练数据中出现。因此，为了解决这个问题，可以将历史 $ w_1w_2 \cdots w_{i - 1}$ 按照某个法则映射到等价类 $ E(w_1w_2 \cdots w_{i - 1})$ ，而等价类的数目远远小于不同历史的数目。如将两个历史 $ w_{i - n + 2} \cdots w_{i - 1}w_i$ 和 $ v_{k - n + 2} \cdots v_{k - 1}v_k$ 映射到同一个等价类，当 $ n = 2$ 时，即出现在第 $ i$ 位上的词 $ w_i$ 仅与它前面的一个历史词 $ w_{i-1}$ 有关，二元文法模型被称为一阶马尔可夫链（Markov chain），记作bigram或bi-gram。
以bigram为例，如果用 $ c(w_{i-1}w_i)$ 表示二元语法 $ w_{i-1}w_i$ 在给定文本中的出现次数，则条件概率 $ p(w_i|w_{i-1})$ 可以用如下公式计算：
$$ p(w_i|w_{i-1}) = \frac {c(w_{i-1}w_i)} { \sum _{w_i} {c(w _{i-1} w_i)} } $$
对于n元语法模型，使用的训练语料的规模一般要有几百万个词。上式用于估计 $ p(w_i|w_{i-1})$ 的方法称为 $ p(w_i|w_{i-1})$ 的最大似然估计（maximum likelihood estimation，MLE）。
语言模型性能评价
交叉熵和困惑度越小越好。
在英语文本中，n元语法模型计算的困惑度大约为 $50 \sim 1000 $ 之间（对应的交叉熵范围为 $6\sim 10$ 个比特位），具体值与文本的类型有关。
数据平滑
问题的提出
“数据平滑”是用来解决零概率问题的。“平滑”处理的基本思想是“劫富济贫”，即提高低概率（如零概率），降低高概率，尽量使概率分布趋于均匀。
加法平滑方法
假设每一个n元词法发生的次数比实际统计次数多 $ \delta $ 次， $ 0 \leq \delta \leq 1$ ，则
$$
p _{add} (w_i|w ^{i-1} _{i-n+1}) =
\frac { \delta + c(w _{i-n+1} ^i)} { \delta |V| + \sum _{w_i} {c(w _{i-n+1} ^i)}}
$$
古德-图灵（Good-Turing）估计法
Good-Turing估计法是很多平滑技术的核心。其基本思路是：对于任何一个出现 $ r$ 次n元语法，都假设它出现了 $ r^* $ 次，这里
$$
r^* = (r+1) \frac {n_{r+1}}{n_r}
$$
其中 $ n_r$ 是训练预料中恰好出现 $ r$ 次的 $ n$ 元语法的数目。要把这个统计次数转化为概率，需要进行归一化处理：对于统计数为 $ r$ 的 $ n$ 元语法，其概率为
$$
p_r = \frac { r^* }{N}
$$
其中 $ N = \sum _{r=0} ^{\infty} {n_r r^* } $ 。注意：
$$
N = \sum _{r=0} ^{ \infty } {n_r r^* }
= \sum _{r=0} ^{ \infty } { (r+1) { n _{r+1}} }
= \sum _{r=1} ^{ \infty } {n_rr}
$$
也就是说， $ N$ 等于这个分布中最初的计数。这样，样本中所有事件的概率之和为：
$$
\sum _{r>0} {n_r p_r}
= \sum _{r>0} { \frac {(r+1) n _{r+1} } {N}}
= \sum _{r>1} { \frac {rn_r} {N} }
= 1 - \frac {n_1} {N}
< 1
$$
因此，有 $ \frac {n_1}{N}$ 的概率剩余量可以分配给所有未见过的事件（ $ r=0$ 的事件）。
Good-Turing方法不能实现高阶模型和低阶模型的结合，而高低阶模型的结合通常是获得较好的平滑效果所必须的。通常，Good-Turing方法作为一个基本方法，在其他平滑技术中得到了很好的应用。
Katz平滑方法
1987年S. M. Katz提出了一种后备（back-off）平滑方法，简称Katz平滑方法。其基本思路是，当事件在样本中出现的频次大于某一数值 $ k$ 时，运用最大似然估计法，通过减值来估计其概率值；而当事件的频次小于 $ k$ 时，使用低阶的语法模型作为代替高阶语法模型的后备，但这种代替受归一化因子的约束。换句话说，就是将因减值而节省下来的概率根据低阶语法模型的分布情况分配给未见事件，而不是平均分配。
以bigram为例，对于一个出现次数为 $ r=c(w^i_{i-1})$ 的二元语法 $ w^i_{i-1}$ ，使用如下公式计算修正的计数：
$$
p_{katz}(w^i_{i-1}) =
\begin {cases}
d_r \dfrac {c(w_{i-1}^i)} { c(w_{i-1}) }, & \text {r>0} \\ \alpha (w_{i-1}) p_{ML}(w_i), & \text{r=0}
\end {cases}
$$
也就是说，所有具有非零计数 $ r$ 的二元语法都根据折扣 $ d_r$ 被减值了，折扣率 $ d_r $ 近似地等于 $ \dfrac {r_*}r $ ，这个减值是由Good-Turing估计方法预测的。式中， $ p_{ML}(w_i)$ 为 $ w_i$ 的最大似然估计概率， $ \alpha (w_{i-1})$ 为一个合适的值。
折扣率 $ d_r$ 可以按照如下办法计算：由于大的计数值是可靠的，因此它们不需要进行减值。尤其对于某些 $ k$ ,S. M. Katz取所有 $ r>k$ 的情况下的 $ d_r = 1$ ，并且建议 $ k=5$ 。对于 $ r \leq k$ 的情况下的折扣率，减值率由用于全局二元语法的Good-Turing估计方法计算。
Jelinek-Mercer平滑方法
以bigram为例，将二元文法模型和一元文法模型进行线性插值：
$$
p_{interp}(w_i|w_{i-1}) = \lambda p_{ML}(w_i|w_{i-1}) + (1- \lambda )p_{ML}(w_i)
$$
其中， $ 0 \leq \lambda \leq 1 $ 。
对于多元语法模型，第 $ n$ 阶平滑模型递归地定义为 $ n$ 阶最大似然估计模型和 $ n-1$ 阶平滑模型之间的线性插值：
$$
p_{interp}(w_i|w ^{i-1} _{i-n+1}) = \lambda _{w _{i-n+1} ^{i-1}} p _{ML} (w_i|w ^{i-1} _{i-n+1}) + (1- \lambda _{w _{i-n+1} ^{i-1}}) p _{interp} (w ^{i-1} _{i-n+2})
$$
绝对减值法
绝对减值法（absolute discounting）类似于Jelinek-Mercer平滑算法，涉及高阶和低阶模型的插值问题。然而，这种方法不是采用将高阶最大似然分布乘以因子 $ \lambda w_{i-n+1}^{i-1} $ 的方法，而是通过从每个非零计数中减去一个固定值 $ D \leq 1 $ 的方法来建立高阶分布。
$$
p _{abs} (w_i|w ^{i-1} _{i-n+1}) =
\frac {\max c(w _{i-n+1} ^{i}) - D, 0} { \sum _{w_i} c(w _{i-n+1} ^{i})} + (1- \lambda _{w _{i-n+1} ^{i-1}}) p _{abs} (w ^{i-1} _{i-n+2})
$$
这里假设 $ 0 \leq D \leq 1 $ 。
Kneser-Ney平滑方法
这是一种扩展的绝对减值算法，用一种新的方式建立与高阶分布相结合的低阶分布。在前面的算法中，通常用平滑后的低阶最大似然分布作为低阶分布，在Kneser-Ney平滑方法中，分配给（以bigram为例）每个一元文法计数的数目就是它前面不同单词的数目。
修正的Kneser-Ney平滑方法
不像Kneser-Ney平滑方法那样对所有的非零计数都用一个减值参数 $ D$ ，而是对计数分别为1、2和大于等于3三种情况下的 $ n$ 元模型分别采用3个不同的参数 $ D_1$ 、 $ D_2$ 、 $ D_{3+}$ 。
平滑方法的比较
不管训练语料规模多大，对于二元语法和三元语法而言，Kneser-Ney平滑方法和修正的Kneser-Ney平滑方法的效果都好于其他所有的平滑方法。
语言模型自适应方法
在实际应用中，语言模型对跨领域的脆弱性和独立性假设的无效性是两个最明显的问题。
为了提高语言模型对语料的领域、主题、类型等因素的适应性，提出了以下自适应语言模型。
基于缓存的语言模型
基于缓存的自适应模型针对的问题是，在文本中刚刚出现过的一些词在后边的句子中再次出现的可能性往往更大，比标准的 $ n$ 元语法模型预测的概率要大。
cache-based自适应方法的基本思路是：语言模型通过 $ n$ 元语法的线性插值求得：
$$
\hat p( w_i|w _1 ^{i-1} )
= \lambda \hat p _{Cache} ( w_i|w _1 ^{i-1} ) + ( 1 - \lambda ) \hat p _{n-gram} (w_i|w _{i-n+1} ^{i-1})
$$
常用的方法是：在缓存中保留前面的 $ K $ 个单词，每个词 $ w_i $ 的概率（缓存概率）用其在缓存中出现的相对频率计算得出：
$$
\hat p _{Cache} (w_i|w_1 ^{i-1})
= \frac {1}{K} \sum _{j=i-K} ^{i-1} {I _{w_j = w_i} }
$$
其中， $ I _{\epsilon} $ 为指示器函数（indicator function）。如果 $ \epsilon $ 表示的情况出现，则 $ I _{\epsilon} = 1 $ ，否则， $ I _{\epsilon}=0 $ 。
研究表明，缓存中每个词对当前词的影响随着与该词距离的增大呈指数级衰减，因此上式可写为：
$$
\hat p _{Cache} (w_i|w_1 ^{i-1})
= \beta \sum _{j=1} ^{i-1} {I _{w_j = w_i} } e ^{- \alpha (i-j)}
$$
其中， $ \alpha$ 为衰减率， $ \beta$ 为归一化系数。
基于混合方法的语言模型
针对的问题是：由于大规模训练语料本身是异源的，来自不同领域的语料存在一定的差异，而测试语料一般是同源的，因此，为了获得最佳性能，语言模型必须适应各种不同类型的语料对其性能的影响。
基于混合方法的自适应语言模型的基本思想是：将语言模型划分成 $ n$ 个子模型 $ M_1,M_2, \cdots, M_n$ ，整个语言模型的概率通过下式计算得到：
$$
\hat p(w_i|w_1 ^{i-1})
= \sum _{j=1} ^n \lambda _j \hat p _{M_j} (w_i|w_1 ^{i-1})
$$
基于最大熵的语言模型
上面介绍的两种语言模型自适应方法都是分别建立各个子模型，然后将子模型的输出结合起来。基于最大熵的语言模型却采用不同的实现思路，即通过结合不同信息源的信息构建一个语言模型。每个信息源提供一组关于模型参数的约束条件，在所有满足约束的模型中，选择熵最大的模型。
参考
宗成庆《统计自然语言处理》第五章
