您的位置: 首页  >  文章  >  N-gram语言模型 & Perplexity & 平滑

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

分类: 文章 • 2024-08-22 22:56:16

文章目录

1. N-gram语言模型

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

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

    • 首先在句子的首尾增加两个特殊标记 <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∣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(\text{<s>})，因为始终等于1
      • 这里一共是N+1N+1项（与很多地方说的都不一样）
        • 不能没有</s>\text{</s>}
          • 可以证明，对于一个固定长度NN，所有可能句子{SN}\{S_N\}的概率之和，即
            ∑s∈{SN}P(<s>,w1,…,wN)=1\sum_{s \in \{S_N\}} P(\text{<s>}, w_1, \dots, w_N) = 1
          • 那么对于不同长度的句子集合，即“所有可能的句子”，其概率之和 > 1

    • 通常，为了防止概率(<1)连乘 导致浮点underflow，对其取对数，这样乘法就变成了加法
      log⁡P(s)=log⁡P(w1∣&lt;s&gt;)+log⁡P(w2∣w1)+⋯+log⁡P(&lt;/s&gt;∣wN)\log P(s) = \log P(w_1 | \text{&lt;s&gt;}) + \log P(w_2 | w_1) + \dots + \log P(\text{&lt;/s&gt;}|w_N)

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)}

  • 对于bigram LM来说，就是
    1P(w1∣&lt;s&gt;)P(w2∣w1)…P(wN∣wN−1)P(&lt;/s&gt;∣wN)N+1\sqrt[N+1]{\frac{1}{P(w_1 | \text{&lt;s&gt;}) P(w_2 | w_1) \dots P(w_N |w_{N−1})P( \text{&lt;/s&gt;} | w_N)}}

  • 对于整个测试集，我们再对所有句子的perplexity，求几何平均，得到整体的结果
    这里用N′N&#x27;表示所有测试集中句子长度之和，即N′=∑(Nk+1)N&#x27;=\sum (N_k+1)，
    Perplexity=P(S)−1N′=2−1N′⋅log⁡P(S)=2−∑log⁡P(sk)∑(Nk+1)Perplexity = P(S)^{-\frac{1}{N&#x27;}} = 2^{-\frac{1}{N&#x27;} \cdot \log P(S)} = 2^{-\frac{\sum \log P(s_k)}{\sum (N_k+1)}}

  • 解释

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

  • 注意

    • 不同LM比较时，需要有相同的词表，否则比较结果可能会不可靠
      • 举个极端的例子：某个模型中词表中只包含两个词：“的” 和&lt;unk&gt;\text{&lt;unk&gt;}（下面提到的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}) = 0 (稀疏)，另外，还有很多训练语料中不存在(OOV, Out-of-vocabulary) 的词
  • 所以，如果训练语料数量不够大，或者词表不够全，得到的语言模型容易出现过拟合

3.2 常用方法

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

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

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

  • α=0\alpha = 0时，即为不做平滑的结果
  • α=1\alpha = 1时，即为常说的add-one
  • 两类词
    • 对于词表内的词，∑1vp=1\sum_{1}^{v} {p} = 1，也就是说，在做了平滑之后，表内词概率和为1（也就是说算上OOV所有可能出现的词概率之和>1 !）
      • 可以理解为一个利用了 Dirichlet-Multinomial 共轭 的MAP（最大后验估计）
        • 假设词表的先验分布 Pprior∼Dir(α⋅Iv)P_{prior} \sim Dir(\alpha \cdot I_v)，其中 IvI_v 是长度为vv，元素都是1的向量（不考虑OOV）（从期望上看，各个词是相等的）
        • 语料中的词 服从多项分布Pdata∼Mult()P_{data} \sim {Mult}()
        • 则词的后验分布为 Ppost∼Dir({ci+α})P_{post} \sim Dir(\{c_i + \alpha\})，期望为上面的pp
    • 对于OOV的词，c=0⇒p=αn+αv=1n/α+vc=0 \Rightarrow p=\frac{\alpha}{n + \alpha v} = \frac{1}{n/\alpha + v}，α\alpha的选择可以用cross-validation
3.2.2 Good-Turing Smoothing
  • 假设语料中出现了rr次的词有NrN_r（出现rr次的词的集合大小），语料大小为NN，则N=∑r=1∞rNrN = \sum_{r=1}^{\infty} r N_r
    • 考虑unigram（n=1），出现rr次的所有词，其概率为rN\frac{r}{N}
  • 当rr较小时，极大似然估计可能不准确，同时我们也要考虑一下那些没有出现（r=0r=0）的词，从而我们给所有rr打一个“折扣”（discount）,
    dr=(r+1)Nr+1Nrd_r = (r + 1)\frac{N_{r+1}}{N_r}
    容易证明，N=∑r=0∞drNrN = \sum_{r=0}^{\infty} d_r N_r
  • 根据Zipf’s law，rr越大，NrN_r越小，所以，一般情况下，r∗&lt;rr^*&lt;r
  • 可以证明，dr≈E(r)=E(c∗(w)∣c(w)=r)d_r \approx E(r) = E(c^{*}(w)|c(w) = r)
    • 因为有未知的信息（unseen ngram），所以观测的统计量的方差较大（但仍是无偏的），所以设计一个条件概率来减小方差（?）
3.2.3 Backoff (Katz)

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

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

PBO(wn∣wn−N+1n−1)={P∗(wn∣wn−N+1n−1),if Count(wn−N+1n)&gt;0α(wn−N+1n−1)PBO(wn∣wn−N+2n−1),else P_{BO}(w_n | w_{n−N+1}^{n-1}) = \begin{cases} P^∗(w_n | w_{n−N+1}^{n-1}), &amp; if\ Count(w_{n−N+1}^{n}) &gt; 0 \\ \alpha(w_{n−N+1}^{n-1}) P_{BO}(w_n | w_{n−N+2}^{n-1}), &amp; else \end{cases}

  • 这里的P∗(wn∣wn−N+1n−1)P^∗(w_n | w_{n−N+1}^{n-1})可以通过上面的Good-Turing Smoothing得到
  • 因为没有加入r=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})
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=1 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

  • 其中λ\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})
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})

3.2.6 Absolute Discounting

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

Church & Gale (1991) 做了一项实验，他们将语料库分成大小相同的两部分（训练集和验证集分别有2200万），观察那些在训练集中出现了rr次的bigram 在验证集中平均出现的次数。
下面给出不同的 rr 的结果，
N-gram语言模型 & Perplexity & 平滑
可以看出，除了r=0或1r =0或1的bigram之外，验证集中的平均出现次数，都约等于 r−0.75r - 0.75。
和Good-Turing Smoothing不同的是，Absolute discounting 直接对rr进行某种确定性的操作，不依赖于训练集的NrN_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)

  • 其中，dd 可以根据Count(wi,wi−1)=0,1或≥2Count(w_i, w_{i-1})=0,1 或 \ge 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）数量
    N-gram语言模型 & Perplexity & 平滑
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)&gt;0}∣P_{continuation}(w) \propto |\{v : C(vw) &gt; 0\}|
    • 然后，我们normalize一下
      Pcontinuation(w)=∣{v:C(v,w)&gt;0}∣∣{v′,w′:C(v′,w′)&gt;0}∣=Count(w可能的上文种类)Count(所有出现过的bigram)P_{continuation}(w) = \frac{|\{v : C(v,w) &gt; 0\}|}{|\{v&#x27;, w&#x27; : C(v&#x27;,w&#x27;) &gt; 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)
    • 如果用的dd是一样的，那么λ(wi−1)=dCount(wi−1)∣w:Count(wi−1,w)&gt;0∣\lambda(w_{i−1}) = \frac{d}{Count(w_{i-1})} |w : Count(w_{i−1}, w) &gt; 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})

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

  • 如果不限制dd是固定的，而采用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),if Count(wn−N+1n)&gt;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}), &amp; if\ Count(w_{n−N+1}^{n}) &gt; 0 \\ \lambda(w_{n−N+1}^{n-1}) S(w_n | w_{n−N+2}^{n-1}), &amp; else \end{cases} \end{aligned}
  • 因为没有对seen ngram做discount，所以总的概率之和>1，这里用SS而不是PP来表示
  • 论文中，λ\lambda 一刀切用了0.4
  • 对大规模语料，ngram的抽取可以用map-reduce并行处理加快速度

3.3 小结

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

4. Reference

相关推荐