N-gram语言模型 & Perplexity & 平滑

• • 一、N-gram语言模型
  • 二、Perplexity（困惑度）
  • 三、平滑方法
    • • 问题
      • 常用方法
        • • Laplace平滑 (add-one, add-α)
          • Good-Turing Smoothing
          • Backoff (Katz)
          • Interpolation（Jelinek-Mercer）
          • Recursive Interpolation
          • Absolute Discounting
          • Witten-Bell Smoothing
          • Kneser-Ney discounting
          • Stupid Backoff
      • 小结
  • 四、Reference

一、N-gram语言模型

• 语言模型（Language Model,LM）的一个常见任务，是已知一句话的前面几个词，预测下一个是什么，即对 P(wi|wi−11) $P(w_i|w_1^{i-1})$建模

• N-gram语言模型，是基于Markov假设，假设文本中的每个词只与前面的n-1个词有关，即

  P(wi|wi−11)≈P(wi|wi−1i−n+1)=P(wi|wi−1,…,wi−n+1) $$P(w_i|w_1^{i-1})\approx P(w_i|w_{i-n+1}^{i-1})=P(w_i|w_{i-1},\dots ,w_{i-n+1})$$
  
  这可以通过对训练语料做极大似然估计，
  
  P(wi|wi−1i−n+1)=Count(wi,wi−1,…,wi−n+1)Count(wi−1,…,wi−n+1) $$P(w_i|w_{i-n+1}^{i-1})=\frac{Count(w_i,w_{i-1},\dots ,w_{i-n+1})}{Count(w_{i-1},\dots ,w_{i-n+1)}}$$

• 由此我们可以求一段文本（句子） s $s$ 的概率

  • 首先在句子的首尾增加两个特殊标记 <s>, </s> $\text{<s>, </s>}$

  • 再通过链式法则，以bigram（n=2）为例，
    

    P(s)=P(<s>,w1,…,wN,</s>)=P(<s>)P(w1|<s>)P(w2|w1,<s>)…P(wN|wN−11,<s>)P(</s>|wN1,<s>)=P(w1|<s>)P(w2|w1)…P(wN|wN−1)P(</s>|wN) $$\begin{array}{rl}P(s)& =P(\text{<s>},w_1,\dots ,w_N,\text{</s>})\\ & =P(\text{<s>})P(w_1|\text{<s>})P(w_2|w_1,\text{<s>})\dots P(w_N|w_1^{N-1},\text{<s>})P(\text{</s>}|w_1^N,\text{<s>})\\ & =P(w_1|\text{<s>})P(w_2|w_1)\dots P(w_N|w_{N-1})P(\text{</s>}|w_N)\end{array}$$
    • 这里忽略 P(<s>) $P(\text{<s>})$，因为始终等于1
    • 这里一共是 N+1 $N+1$项（与很多地方说的都不一样）
      
      • 不能没有 </s> $\text{</s>}$
        
        • 可以证明，对于一个固定长度 N $N$，所有可能句子 {SN} $\{S_N\}$的概率之和，即
          ∑s∈{SN}P(<s>,w1,…,wN)=1 $\underset{s\in \{S_N\}}{\sum }P(\text{<s>},w_1,\dots ,w_N)=1$
        • 那么对于不同长度的句子集合，即“所有可能的句子”，其概率之和 > 1
  • 通常，为了防止概率(<1)连乘 导致浮点underflow，对其取对数，这样乘法就变成了加法
    
    logP(s)=logP(w1|<s>)+logP(w2|w1)+⋯+logP(</s>|wN) $$\log P(s)=\log P(w_1|\text{<s>})+\log P(w_2|w_1)+\cdots +\log P(\text{</s>}|w_N)$$

二、Perplexity（困惑度）

刚才我们通过训练集得到了语言模型，而perplexity是一种评价语言模型在测试集上表现的方法

• 对一句句子来说，
  
  Perplexity(s)=P(s)−1N+1=2−1N+1⋅logP(s) $$Perplexity(s)=P(s{)}^{-\frac{1}{N+1}}=2^{-\frac{1}{N+1}\cdot \log P(s)}$$

• 对于bigram LM来说，就是
  

  1P(w1|<s>)P(w2|w1)…P(wN|wN−1)P(</s>|wN)−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−√N+1 $$\sqrt[N+1]{\frac{1}{P(w_1|\text{<s>})P(w_2|w_1)\dots P(w_N|w_{N-1})P(\text{</s>}|w_N)}}$$

• 对于整个测试集，我们再对所有句子的perplexity，求几何平均，得到整体的结果
  这里用 N′ $N^{\prime }$表示所有测试集中句子长度之和，即 N′=∑(Nk+1) $N^{\prime }=\sum (N_k+1)$，
  

  Perplexity=P(S)−1N′=2−1N′⋅logP(S)=2−∑logP(sk)∑(Nk+1) $$Perplexity=P(S{)}^{-\frac{1}{N^{\prime }}}=2^{-\frac{1}{N^{\prime }}\cdot \log P(S)}=2^{-\frac{\sum \log P(s_k)}{\sum (N_k+1)}}$$

• 解释

  • 注意上面的指数表达形式，其中 −1N′logp(S) $-\frac{1}{N^{\prime }}\log p(S)$可以理解为（对词平均的）交叉熵（cross-entropy），也就是 H(q,p)=−∑q(w)logp(w) $H(q,p)=-\sum q(w)\log p(w)$
  • 这里 q(w) $q(w)$是经验分布，即 nN′ $\frac{n}{N^{\prime }}$， n=Count(w) $n=Count(w)$， −logp(w) $-\log p(w)$表示其信息量（编码长度，惊讶程度(?)）
  • 所以，perplexity就是在某种编码方式（语言模型）下评估测试集的平均编码长度(平均惊讶程度(?))，也就是交叉熵的含义
  • LM拟合得越好，即模型越贴近真实分布 q $q$，perplexity（交叉熵）越小，KL散度越小，越接近真实分布的熵
    H(q,p)=Eq[−logp]=H(q)+DKL(q∥p)≥H(q) $H(q,p)={\mathbb{E}}_q[-\log p]=H(q)+D_{KL}(q\Vert p)\ge H(q)$
• 注意
  
  • 不同LM比较时，需要有相同的词表，否则比较结果可能会不可靠
    
    • 举个极端的例子：某个模型中词表中只包含两个词：“的” 和 <unk> $\text{<unk>}$（下面提到的OOV的一种处理方式，可以看做一个特殊词），因为两者出现的次数都足够多，那么其LM必然是很准的

三、平滑方法

PS：以下对”ngram”和”词”不做区分

问题

• 假如我们词表的大小是50万，则要覆盖所有的bigram情况，需要至少2500亿个词的语料，参数必然也是这个数量级；对于trigram（n=3）以及更大的n，还会更大，显然这是不现实的
• 很多的词不会相邻出现，即大部分 P(wi|wi−1i−n+1)=0 $P(w_i|w_{i-n+1}^{i-1})=0$ (稀疏)，另外，还有很多训练语料中不存在(OOV, Out-of-vocabulary) 的词
• 所以，如果训练语料数量不够大，或者词表不够全，得到的语言模型容易出现过拟合

常用方法

Laplace平滑 (add-one, add-α)

p=c+αn+αv $p=\frac{c+\alpha }{n+\alpha v}$

其中 0≤α≤1, v=|V| $0\le \alpha \le 1,v=|V|$

• α=0 $\alpha =0$时，即为不做平滑的结果
• α=1 $\alpha =1$时，即为常说的add-one
• 两类词
  
  • 对于词表内的词， ∑v1p=1 $\underset{1}{\overset{v}{\sum }}p=1$，也就是说，在做了平滑之后，表内词概率和为1（也就是说算上OOV所有可能出现的词概率之和>1 !）
    
    • 可以理解为一个利用了 Dirichlet-Multinomial 共轭 的MAP（最大后验估计）
      
      • 假设词表的先验分布 Pprior∼Dir(α⋅Iv) $P_{prior}\sim Dir(\alpha \cdot I_v)$，其中 Iv $I_v$ 是长度为 v $v$，元素都是1的向量（不考虑OOV）（从期望上看，各个词是相等的）
      • 语料中的词 服从多项分布 Pdata∼Mult() $P_{data}\sim Mult()$
      • 则词的后验分布为 Ppost∼Dir({ci+α}) $P_{post}\sim Dir(\{c_i+\alpha \})$，期望为上面的 p $p$
  • 对于OOV的词， c=0⇒p=αn+αv=1n/α+v $c=0\Rightarrow p=\frac{\alpha }{n+\alpha v}=\frac{1}{n/\alpha +v}$， α $\alpha$的选择可以用cross-validation

Good-Turing Smoothing

• 假设语料中出现了 r $r$次的词有 Nr $N_r$（出现 r $r$次的词的集合大小），语料大小为 N $N$，则 N=∑∞r=1rNr $N=\underset{r=1}{\overset{\mathrm{\infty }}{\sum }}r{N}_r$
  
  • 考虑unigram（n=1），出现 r $r$次的所有词，其概率为 rN $\frac{r}{N}$
• 当 r $r$较小时，极大似然估计可能不准确，同时我们也要考虑一下那些没有出现（ r=0 $r=0$）的词，从而我们给所有 r $r$打一个“折扣”（discount）,
  
  dr=(r+1)Nr+1Nr $$d_r=(r+1)\frac{N_{r+1}}{N_r}$$
  
  容易证明， N=∑∞r=0drNr $N=\underset{r=0}{\overset{\mathrm{\infty }}{\sum }}{d}_r{N}_r$
• 根据Zipf’s law， r $r$越大， Nr $N_r$越小，所以，一般情况下， r∗<r $r^{\ast }<r$
• 可以证明， dr≈E(r)=E(c∗(w)|c(w)=r) $d_r\approx E(r)=E(c^{\ast }(w)|c(w)=r)$
  
  • 因为有未知的信息（unseen ngram），所以观测的统计量的方差较大（但仍是无偏的），所以设计一个条件概率来减小方差（?）

Backoff (Katz)

上面的两种处理方式，是对原先概率为0的情况作了一刀切地处理，但是有些ngram其实比另一些更有可能出现，所以这么做肯定不那么准确。由此，我们分两种情况：

1. 对于见过的ngram，优先用训练语料来拟合
2. 对于unseen-ngram，取折扣因子(discounting factor)为剩下的概率，再递归地去寻找 (n-1)-gram（回退补偿，backoff）

PBO(wn|wn−1n−N+1)={P∗(wn|wn−1n−N+1),α(wn−1n−N+1)PBO(wn|wn−1n−N+2),if Count(wnn−N+1)>0else $$P_{BO}(w_n|w_{n-N+1}^{n-1})=\{\begin{array}{ll}{P}^{\ast }(w_n|w_{n-N+1}^{n-1}),& ifCount(w_{n-N+1}^n)>0\\ \alpha (w_{n-N+1}^{n-1})P_{BO}(w_n|w_{n-N+2}^{n-1}),& else\end{array}$$

• 这里的 P∗(wn|wn−1n−N+1) $P^{\ast }(w_n|w_{n-N+1}^{n-1})$可以通过上面的Good-Turing Smoothing得到
• 因为没有加入 r=0 $r=0$的情况，所以概率之和<1，剩下的部分就尽量匀给第二种情况，即 α(wn−1n−N+1)=1−∑wnP∗(wn|wn−1n−N+1) $\alpha (w_{n-N+1}^{n-1})=1-\underset{w_n}{\sum }{P}^{\ast }(w_n|w_{n-N+1}^{n-1})$

Interpolation（Jelinek-Mercer）

除了backoff之外，另一种利用多层context的方法是做插值，两者的不同在于

• backoff在“证据充分”的情况下，会尽量用ngram直接估计，不行才会求助于更短的上下文
• 而插值法每次都会综合多个层次，这对于数据量少时减少过拟合很有用

以trigram为例，

pI(wn|wn−1,wn−2)=λ1p(wn)+λ2p(wn|wn−1)+λ3p(wn|wn−1,wn−2)s.t   λ1+λ2+λ3=1 $$\begin{gathered} p_I(w_n|w_{n-1},w_{n-2})={\lambda }_{1}p(w_n)+{\lambda }_{2}p(w_n|w_{n-1})+{\lambda }_{3}p(w_n|w_{n-1},w_{n-2}) \\ s.t{\lambda }_1+{\lambda }_2+{\lambda }_3=1 \end{gathered}$$

• 其中 λ $\lambda$也可以和上文（context）有关，即 λ1(wn−1n−2),λ2(wn−1n−2),λ3(wn−1n−2) ${\lambda }_1(w_{n-2}^{n-1}),{\lambda }_2(w_{n-2}^{n-1}),{\lambda }_3(w_{n-2}^{n-1})$

Recursive Interpolation

递归地调用插值法

pIn(wi|wi−1i−n+1)=λ(wi−1i−n+1) pn(wi|wi−1i−n+1)+(1−λ(wi−1i−n+1)) pIn−1(wi|wi−1i−n+2) $p_n^I(w_i|w_{i-n+1}^{i-1})=\lambda (w_{i-n+1}^{i-1})p_n(w_i|w_{i-n+1}^{i-1})+(1-\lambda (w_{i-n+1}^{i-1}))p_{n-1}^I(w_i|w_{i-n+2}^{i-1})$

Absolute Discounting

上面的很多做法都需要对训练集中的ngram做discount，把剩下的概率匀给unseen ngram。

Church & Gale (1991) 做了一项实验，他们将语料库分成大小相同的两部分（训练集和验证集分别有2200万），观察那些在训练集中出现了 r $r$次的bigram 在验证集中平均出现的次数。
下面给出不同的 r $r$ 的结果，

可以看出，除了 r=0或1 $r=0或1$的bigram之外，验证集中的平均出现次数，都约等于 r−0.75 $r-0.75$。
和Good-Turing Smoothing不同的是，Absolute discounting 直接对 r $r$进行某种确定性的操作，不依赖于训练集的 Nr $N_r$。

照着这个思路，
PAD(wi|wi−1)=(Count(wi,wi−1)−d)/Count(wi−1)+λ(wi−1)P(wi) $P_{AD}(w_i|w_{i-1})=(Count(w_i,w_{i-1})-d)/Count(w_{i-1})+\lambda (w_{i-1})P(w_i)$

• 其中， d $d$ 可以根据 Count(wi,wi−1)=0,1或≥2 $Count(w_i,w_{i-1})=0,1或\ge 2$ 设置不同的值
• 注意右边的第二个插值项（Good-Turing 中没有加这个）， λ $\lambda$ 不是一刀切，和context有关（比如可以用下面的Witten-Bell Smoothing来选择）

Witten-Bell Smoothing

一种确定插值法中 λ $\lambda$的思路

• 某些context ngram的下文的选择较少（e.g spite后一般固定搭配跟of），说明一般这个ngram本身会有一些代表性（信息量），需要 λ $\lambda$大一些
• 反之，对于一些下文分布的可能性较多的context（e.g constant，常见的形容词），这个context的信息量就比较小，要缩小context看看（甚至不用context），所以反过来 λ $\lambda$不能太大
• 具体计算方式，其中考虑每个context的可能的下文（possible extension）数量
  

Kneser-Ney discounting

• 让我们来看一道完形填空： I can’t see without my reading (York/glasses).
  
  • 该选哪个呢？如果用unigram来选的话，York因为经常以New York的形式出现，且出现次数比glasses多，所以瞎猜的话，更倾向于选这个
  • 但是也正因为York前面能选的并不多，而glasses之前的可能性明显更多一点（the, my, buy, break等），所以从这个角度来说，猜glasses更可能对
• 所以，与Witten-Bell的思路类似，但我们这里考虑可能的上文，或者说这个词本身作为下文（as continuation）的可能性
  
  • Pcontinuation(w)∝|{v:C(vw)>0}| $P_{continuation}(w)\propto |\{v:C(vw)>0\}|$
  • 然后，我们normalize一下
    
    Pcontinuation(w)=|{v:C(v,w)>0}||{v′,w′:C(v′,w′)>0}|=Count(w可能的上文种类)Count(所有出现过的bigram) $$P_{continuation}(w)=\frac{|\{v:C(v,w)>0\}|}{|\{v^{\prime },w^{\prime }:C(v^{\prime },w^{\prime })>0\}|}=\frac{Count(w可能的上文种类)}{Count(所有出现过的bigram)}$$

• 从而，我们有
  

  PKN(wi|wi−1)=max(Count(wi,wi−1)−d,0)Count(wi−1)+λ(wi−1)Pcontinuation(wi) $$P_{KN}(w_i|w_{i-1})=\frac{max(Count(w_i,w_{i-1})-d,0)}{Count(w_{i-1})}+\lambda (w_{i-1})P_{continuation}(w_i)$$
  • 这里，我们用 Pcontinuation(wi) $P_{continuation}(w_i)$ 代替了unigram P(wi) $P(w_i)$
  • 如果用的 d $d$是一样的，那么 λ(wi−1)=dCount(wi−1)|w:Count(wi−1,w)>0| $\lambda (w_{i-1})=\frac{d}{Count(w_{i-1})}|w:Count(w_{i-1},w)>0|$

• 对于更高阶的ngram，我们可以用递归的方式
  

  PKN(wi|wi−1i−n+1)=max(CKN(wii−n+1)−d,0)CKN(wi−1i−n+1)+λ(wi−1i−n+1)PKN(wi|wi−1i−n+2) $$P_{KN}(w_i|w_{i-n+1}^{i-1})=\frac{max(C_{KN}(w_{i-n+1}^i)-d,0)}{C_{KN}(w_{i-n+1}^{i-1})}+\lambda (w_{i-n+1}^{i-1})P_{KN}(w_i|w_{i-n+2}^{i-1})$$
  • 其中，
    
    CKN(⋅)={Count(⋅),continuation count(⋅),for the highest orderfor lower order $$\begin{array}{r}{C}_{KN}(\cdot )=\{\begin{array}{ll}Count(\cdot ),& \text{for the highest order}\\ continuationcount(\cdot ),& \text{for lower order}\end{array}\end{array}$$
  • 解释一下，因为采用了递归形式，原先的第二项 Pcontinuation $P_{continuation}$ 没有了；为了能用第一项的形式表达continuation，对于低阶的ngram，其count要用计算continuation时的方法
• 如果不限制 d $d$是固定的，而采用absolute discounting中区分count为0, 1, >1的方法，那就变成了Modified Kneser-Ney discounting，基本是目前效果最好的平滑方法之一了

Stupid Backoff

google提出的一种面向大型语料库的方法，在语料足够多的情况下，效果可以与Kneser-Ney媲美
（有兴趣可以玩一下google ngram）

• 语料足够时（文中最大1.8万亿tokens，3000亿ngram(n=1-5)），对于seen ngram，直接用极大似然的结果，也能保证方差不会太大
• 而对于剩下的情况，用最简单的backoff处理
  
  S(wn|wn−1n−N+1)={P(wn|wn−1n−N+1),λ(wn−1n−N+1)S(wn|wn−1n−N+2),if Count(wnn−N+1)>0else $$\begin{array}{r}S(w_n|w_{n-N+1}^{n-1})=\{\begin{array}{ll}P(w_n|w_{n-N+1}^{n-1}),& ifCount(w_{n-N+1}^n)>0\\ \lambda (w_{n-N+1}^{n-1})S(w_n|w_{n-N+2}^{n-1}),& else\end{array}\end{array}$$
• 因为没有对seen ngram做discount，所以总的概率之和>1，这里用 S $S$而不是 P $P$来表示
• 论文中， λ $\lambda$ 一刀切用了0.4
• 对大规模语料，ngram的抽取可以用map-reduce并行处理加快速度

小结

• backoff/interpolation很管用，能尽可能地利用低阶信息，减少过拟合
  
  • 在训练集比较小时，插值法更好一些
  • 在训练集比较大时，backoff 可以直接用高阶的信息，所以效果会更好
• 具体的参数选择，需要通过在验证集上的表现决定

四、Reference

• Speech and Language Processing 3rd ed, Chapter 4, Daniel Jurafsky.,
• Statistical Machine Translation, Chapter 7, Koehn