失眠网 > N-gram语言模型 Perplexity 平滑

N-gram语言模型 Perplexity 平滑

时间：2023-09-06 02:55:54

文章目录

1. N-gram语言模型2. Perplexity（困惑度）3. 平滑方法3.1 问题3.2 常用方法3.2.1 Laplace平滑 (add-one, add-α)3.2.2 Good-Turing Smoothing3.2.3 Backoff (Katz) 3.2.4 Interpolation（Jelinek-Mercer）3.2.5 Recursive Interpolation3.2.6 Absolute Discounting3.2.7 Witten-Bell Smoothing3.2.8 Kneser-Ney discounting3.2.9 Stupid Backoff3.3 小结4. Reference

1. N-gram语言模型

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

N-gram语言模型，是基于Markov假设，假设文本中的每个词只与前面的n-1个词有关，即P(wi∣w1i−1)≈P(wi∣wi−n+1i−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∣w1i−1)≈P(wi∣wi−n+1i−1)=P(wi∣wi−1,…,wi−n+1)

这可以通过对训练语料做极大似然估计，

P(wi∣wi−n+1i−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},…,w_{i−n+1})}{Count(w_{i−1},…,w_{i−n+1)}} P(wi∣wi−n+1i−1)=Count(wi−1,…,wi−n+1)Count(wi,wi−1,…,wi−n+1)

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

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

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

P(s)=P(<s>,w1,…,wN,</s>)=P(<s>)P(w1∣<s>)P(w2∣w1,<s>)…P(wN∣w1N−1,<s>)P(</s>∣w1N,<s>)=P(w1∣<s>)P(w2∣w1)…P(wN∣wN−1)P(</s>∣wN)\begin{aligned} 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^{N−1}_1, \text{<s>})P( \text{</s>} |w^N_1, \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{aligned} P(s)=P(<s>,w1,…,wN,</s>)=P(<s>)P(w1∣<s>)P(w2∣w1,<s>)…P(wN∣w1N−1,<s>)P(</s>∣w1N,<s>)=P(w1∣<s>)P(w2∣w1)…P(wN∣wN−1)P(</s>∣wN)

这里忽略P(<s>)P(\text{<s>})P(<s>)，因为始终等于1这里一共是N+1N+1N+1项（与很多地方说的都不一样）不能没有</s>\text{</s>}</s> 可以证明，对于一个固定长度NNN，所有可能句子{SN}\{S_N\}{SN}的概率之和，即

∑s∈{SN}P(<s>,w1,…,wN)=1\sum_{s \in \{S_N\}} P(\text{<s>}, w_1, \dots, w_N) = 1∑s∈{SN}P(<s>,w1,…,wN)=1那么对于不同长度的句子集合，即“所有可能的句子”，其概率之和 > 1

通常，为了防止概率(<1)连乘导致浮点underflow，对其取对数，这样乘法就变成了加法

log⁡P(s)=log⁡P(w1∣<s>)+log⁡P(w2∣w1)+⋯+log⁡P(</s>∣wN)\log P(s) = \log P(w_1 | \text{<s>}) + \log P(w_2 | w_1) + \dots + \log P(\text{</s>}|w_N)logP(s)=logP(w1∣<s>)+logP(w2∣w1)+⋯+logP(</s>∣wN)

2. Perplexity（困惑度）

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

对一句句子来说，

Perplexity(s)=P(s)−1N+1=2−1N+1⋅log⁡P(s)Perplexity(s) = P(s)^{-\frac{1}{N+1}} = 2^{-\frac{1}{N+1} \cdot \log P(s)}Perplexity(s)=P(s)−N+11=2−N+11⋅logP(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)}} N+1P(w1∣<s>)P(w2∣w1)…P(wN∣wN−1)P(</s>∣wN)1

对于整个测试集，我们再对所有句子的perplexity，求几何平均，得到整体的结果

这里用N′N'N′表示所有测试集中句子长度之和，即N′=∑(Nk+1)N'=\sum (N_k+1)N′=∑(Nk+1)，

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

解释

注意上面的指数表达形式，其中−1N′log⁡p(S)-\frac{1}{N'} \log p(S)−N′1logp(S)可以理解为（对词平均的）交叉熵（cross-entropy），也就是H(q,p)=−∑q(w)log⁡p(w)H(q, p) = -\sum q(w) \log p(w)H(q,p)=−∑q(w)logp(w)这里q(w)q(w)q(w)是经验分布，即nN′\frac{n}{N'}N′n，n=Count(w)n=Count(w)n=Count(w)，−log⁡p(w)-\log p(w)−logp(w)表示其信息量（编码长度，惊讶程度(?)）所以，perplexity就是在某种编码方式（语言模型）下评估测试集的平均编码长度(平均惊讶程度(?))，也就是交叉熵的含义LM拟合得越好，即模型越贴近真实分布qqq，perplexity（交叉熵）越小，KL散度越小，越接近真实分布的熵

H(q,p)=Eq[−log⁡p]=H(q)+DKL(q∥p)≥H(q)H(q,p)=\mathbb {E}_q [-\log p] = H(q) + D_{KL}(q\|p) \ge H(q)H(q,p)=Eq[−logp]=H(q)+DKL(q∥p)≥H(q)

注意

不同LM比较时，需要有相同的词表，否则比较结果可能会不可靠举个极端的例子：某个模型中词表中只包含两个词：“的” 和<unk>\text{<unk>}<unk>（下面提到的OOV的一种处理方式，可以看做一个特殊词），因为两者出现的次数都足够多，那么其LM必然是很准的

3. 平滑方法

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

3.1 问题

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

3.2 常用方法

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

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

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

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

3.2.2 Good-Turing Smoothing

假设语料中出现了rrr次的词有NrN_rNr（出现rrr次的词的集合大小），语料大小为NNN，则N=∑r=1∞rNrN = \sum_{r=1}^{\infty} r N_rN=∑r=1∞rNr 考虑unigram（n=1），出现rrr次的所有词，其概率为rN\frac{r}{N}Nr 当rrr较小时，极大似然估计可能不准确，同时我们也要考虑一下那些没有出现（r=0r=0r=0）的词，从而我们给所有rrr打一个“折扣”（discount）,

dr=(r+1)Nr+1Nrd_r = (r + 1)\frac{N_{r+1}}{N_r}dr=(r+1)NrNr+1

容易证明，N=∑r=0∞drNrN = \sum_{r=0}^{\infty} d_r N_rN=∑r=0∞drNr根据Zipf’s law，rrr越大，NrN_rNr越小，所以，一般情况下，r∗<rr^*<rr∗<r可以证明，dr≈E(r)=E(c∗(w)∣c(w)=r)d_r \approx E(r) = E(c^{*}(w)|c(w) = r)dr≈E(r)=E(c∗(w)∣c(w)=r) 因为有未知的信息（unseen ngram），所以观测的统计量的方差较大（但仍是无偏的），所以设计一个条件概率来减小方差（?）

3.2.3 Backoff (Katz)

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

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

PBO(wn∣wn−N+1n−1)={P∗(wn∣wn−N+1n−1),ifCount(wn−N+1n)>0α(wn−N+1n−1)PBO(wn∣wn−N+2n−1),elseP_{BO}(w_n | w_{n−N+1}^{n-1}) = \begin{cases} P^∗(w_n | w_{n−N+1}^{n-1}), & if\ Count(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{cases} PBO(wn∣wn−N+1n−1)={P∗(wn∣wn−N+1n−1),α(wn−N+1n−1)PBO(wn∣wn−N+2n−1),ifCount(wn−N+1n)>0else

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

3.2.4 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=1p_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 pI(wn∣wn−1,wn−2)=λ1p(wn)+λ2p(wn∣wn−1)+λ3p(wn∣wn−1,wn−2)s.tλ1+λ2+λ3=1

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

3.2.5 Recursive Interpolation

递归地调用插值法

pnI(wi∣wi−n+1i−1)=λ(wi−n+1i−1)pn(wi∣wi−n+1i−1)+(1−λ(wi−n+1i−1))pn−1I(wi∣wi−n+2i−1)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})pnI(wi∣wi−n+1i−1)=λ(wi−n+1i−1)pn(wi∣wi−n+1i−1)+(1−λ(wi−n+1i−1))pn−1I(wi∣wi−n+2i−1)

3.2.6 Absolute Discounting

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

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

下面给出不同的 rrr 的结果，

可以看出，除了r=0或1r =0或1r=0或1的bigram之外，验证集中的平均出现次数，都约等于 r−0.75r - 0.75r−0.75。

和Good-Turing Smoothing不同的是，Absolute discounting 直接对rrr进行某种确定性的操作，不依赖于训练集的NrN_rNr。

照着这个思路，

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)PAD(wi∣wi−1)=(Count(wi,wi−1)−d)/Count(wi−1)+λ(wi−1)P(wi)

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

3.2.7 Witten-Bell Smoothing

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

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

3.2.8 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\}|Pcontinuation(w)∝∣{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', w' : C(v',w') > 0\}|} = \frac{Count(w可能的上文种类)}{Count(所有出现过的bigram)}Pcontinuation(w)=∣{v′,w′:C(v′,w′)>0}∣∣{v:C(v,w)>0}∣=Count(所有出现过的bigram)Count(w可能的上文种类)

从而，我们有

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)PKN(wi∣wi−1)=Count(wi−1)max(Count(wi,wi−1)−d,0)+λ(wi−1)Pcontinuation(wi)

这里，我们用 Pcontinuation(wi)P_{continuation}(w_i)Pcontinuation(wi) 代替了unigram P(wi)P(w_i)P(wi)如果用的ddd是一样的，那么λ(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|λ(wi−1)=Count(wi−1)d∣w:Count(wi−1,w)>0∣

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

PKN(wi∣wi−n+1i−1)=max(CKN(wi−n+1i)−d,0)CKN(wi−n+1i−1)+λ(wi−n+1i−1)PKN(wi∣wi−n+2i−1)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})PKN(wi∣wi−n+1i−1)=CKN(wi−n+1i−1)max(CKN(wi−n+1i)−d,0)+λ(wi−n+1i−1)PKN(wi∣wi−n+2i−1)

其中，

CKN(⋅)={Count(⋅),forthehighestordercontinuationcount(⋅),forlowerorder\begin{aligned} C_{KN}(\cdot) = \begin{cases} Count(\cdot) ,&\text{for the highest order}\\ continuation\ count(\cdot), &\text{for lower order} \end{cases} \end{aligned}CKN(⋅)={Count(⋅),continuationcount(⋅),forthehighestorderforlowerorder解释一下，因为采用了递归形式，原先的第二项 PcontinuationP_{continuation}Pcontinuation 没有了；为了能用第一项的形式表达continuation，对于低阶的ngram，其count要用计算continuation时的方法

如果不限制ddd是固定的，而采用absolute discounting中区分count为0, 1, >1的方法，那就变成了Modified Kneser-Ney discounting，基本是目前效果最好的平滑方法之一了

3.2.9 Stupid Backoff

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

（有兴趣可以玩一下google ngram）

语料足够时（文中最大1.8万亿tokens，3000亿ngram(n=1-5)），对于seen ngram，直接用极大似然的结果，也能保证方差不会太大而对于剩下的情况，用最简单的backoff处理

S(wn∣wn−N+1n−1)={P(wn∣wn−N+1n−1),ifCount(wn−N+1n)>0λ(wn−N+1n−1)S(wn∣wn−N+2n−1),else\begin{aligned} S(w_n | w_{n−N+1}^{n-1}) = \begin{cases} P(w_n | w_{n−N+1}^{n-1}), & if\ Count(w_{n−N+1}^{n}) > 0 \\ \lambda(w_{n−N+1}^{n-1}) S(w_n | w_{n−N+2}^{n-1}), & else \end{cases} \end{aligned}S(wn∣wn−N+1n−1)={P(wn∣wn−N+1n−1),λ(wn−N+1n−1)S(wn∣wn−N+2n−1),ifCount(wn−N+1n)>0else因为没有对seen ngram做discount，所以总的概率之和>1，这里用SSS而不是PPP来表示论文中，λ\lambdaλ 一刀切用了0.4对大规模语料，ngram的抽取可以用map-reduce并行处理加快速度