从零实现深度学习框架——N-Gram语言模型

引言

本着“凡我不能创造的，我就不能理解”的思想，本系列文章会基于纯Python以及NumPy从零创建自己的深度学习框架，该框架类似PyTorch能实现自动求导。

要深入理解深度学习，从零开始创建的经验非常重要，从自己可以理解的角度出发，尽量不使用外部完备的框架前提下，实现我们想要的模型。本系列文章的宗旨就是通过这样的过程，让大家切实掌握深度学习底层实现，而不是仅做一个调包侠。

从本文开始就来了解自然语言处理(Natural Language Processing)的基本知识。虽然标题是从零实现深度学习框架，但还是偏重于NLP方面的相关技术。其中最重要的就是L(Language)，那么就不得不提到语言模型(Language model)了，本文主要介绍n-gram语言模型。

语言模型

给定一个句子，要如何预测下一个单词呢？

明犯强汉者，虽远必_

可能你猜到下一个单词是“诛”。这里说的单词不仅表示英文中的单词，还可以表示中文中的词语。本文我们会引入一个模型可以为下一个单词赋予概率。也能为整个句子生成一个概率，用于判断一个句子是否通顺。

能为单词序列赋予概率的模型称为语言模型(Language model,LM)，本文我们会介绍最简单的语言模型——n-gram。

N-Gram

假设句子： w 1 , ⋯   , w m w_1,\cdots,w_m w1​,⋯,wm​。包含 m m m个单词，我们可以计算它出现的概率为：
P ( w 1 , ⋯   , w m ) (1) P(w_1,\cdots,w_m) \tag{1} P(w1​,⋯,wm​)(1)
给定单词出现的历史 h h h，我们可以计算单词 w w w在给定历史下出现的概率。假设历史 h h h为“今天天气好”，然后想知道下一个单词是“晴朗”的概率：
P ( 晴 朗 ∣ 今 天   天 气   好 ) (2) P(晴朗|今天\,天气\,好) \tag{2} P(晴朗∣今天天气好)(2)
一种简单的方法是基于频数：拿一个非常大的语料库，统计我们看到“今天天气好晴朗”的次数，以及后面出现“晴朗”的次数，那么可以就可以计算出公式 ( 2 ) (2) (2)的概率：
P ( 晴 朗 ∣ 今 天   天 气   好 ) = C ( 今 天   天 气   好   晴 朗 ) C ( 今 天   天 气   好 ) (3) P(晴朗|今天\,天气\,好) = \frac{C(今天\,天气\,好\,晴朗)}{C(今天\,天气\,好)} \tag{3} P(晴朗∣今天天气好)=C(今天天气好)C(今天天气好晴朗)​(3)
由于中文和英文不一样，中文需要分词，而分词本身是一个重要的NLP应用。我们这里假设已经用空格分好词了。

为了你的模型能很好的应用，你需要统计所有出现的情况，假设你能统计整个网络中所有出现的次数，但是由于语言具有创造性，新的词语或句子总是被创造出来，你就无法统计所有的句子。

我们需要一种更加聪明的方式。这里引入一些标记，为了表示某个随机变量 X i X_i Xi​取“晴朗”的概率 P ( X i = 晴 朗 ) P(X_i=晴朗) P(Xi​=晴朗)，我们简记为 P ( 晴 朗 ) P(晴朗) P(晴朗)。然后我们表示 n n n个单词的序列(句子)为： w 1 ⋯ w n w_1 \cdots w_n w1​⋯wn​，或 w 1 : n w_{1:n} w1:n​。

我们想要知道某个句子中所有单词的联合概率，这个联合概率就是该句子出现的概率。

对于每个单词出现在句子中的联合概率 P ( X 1 = w 1 , X 2 = w 2 , ⋯   , X n = w n ) P(X_1=w_1,X_2=w_2,\cdots,X_n=w_n) P(X1​=w1​,X2​=w2​,⋯,Xn​=wn​)，我们使用 P ( w 1 , w 2 , ⋯   , w n ) P(w_1,w_2,\cdots,w_n) P(w1​,w2​,⋯,wn​)来简化。

计算这个句子的联合概率有什么用呢？假设我们要设计一个聊天机器人，我们生成了两个句子，其中一个句子的联合概率明显高于另一个，那么肯定选择高的那个当成输出。

那我们如何计算整个序列的概率 P ( w 1 , w 2 , ⋯   , w n ) P(w_1,w_2,\cdots,w_n) P(w1​,w2​,⋯,wn​)呢，我们可以使用链式法则来分解联合概率：
P ( X 1 ⋯ X n ) = P ( X 1 ) P ( X 2 ∣ X 1 ) P ( X 3 ∣ X 1 : 2 ) ⋯ P ( X n ∣ X 1 : n − 1 ) = ∏ k = 1 n P ( X k ∣ X 1 : k − 1 ) (4) \begin{aligned} P(X_1\cdots X_n) &= P(X_1) P(X_2|X_1) P(X_3|X_{1:2})\cdots P(X_n|X_{1:n-1}) \ &= \prod_{k=1}^n P(X_k|X_{1:k-1}) \ \end{aligned} \tag 4 P(X1​⋯Xn​)​=P(X1​)P(X2​∣X1​)P(X3​∣X1:2​)⋯P(Xn​∣X1:n−1​)=k=1∏n​P(Xk​∣X1:k−1​)​(4)
应用链式法则，我们带入单词就可以得到：
P ( w 1 : n ) = P ( w 1 ) P ( w 2 ∣ w 1 ) P ( w 3 ∣ w 1 : 2 ) ⋯ P ( w n ∣ w 1 : n − 1 ) = ∏ k = 1 n P ( w k ∣ w 1 : k − 1 ) (5) \begin{aligned} P(w_{1:n}) &= P(w_1)P(w_2|w_1)P(w_3|w_{1:2}) \cdots P(w_n|w_{1:n-1}) \ &= \prod_{k=1}^n P(w_k|w_{1:k-1}) \end{aligned} \tag 5 P(w1:n​)​=P(w1​)P(w2​∣w1​)P(w3​∣w1:2​)⋯P(wn​∣w1:n−1​)=k=1∏n​P(wk​∣w1:k−1​)​(5)
链式法则可以计算序列的联合概率和给定历史单词下计算下一个单词的条件概率之间的联系。

但是这里有一个问题，我们无法计算某个单词前面所有单词的准确概率 P ( w n ∣ w 1 : n − 1 ) P(w_n|w_{1:n-1}) P(wn​∣w1:n−1​)​。正如上面所说的，我们不能仅仅通过计算每个单词在每个长串之后出现的次数来估计，因为语言是创造性的，任何给定的上下文可能以前从未出现过，比如“鸡你太美”中的“鸡你太”可能之前都没出现过。

而N-gram模型解决了这个问题，它进行简化，只根据前面几个单词来估计历史单词。

比如Bi-gram模型，仅使用前一个单词产生下个单词的条件概率 P ( w n ∣ w n − 1 ) P(w_n|w_{n-1}) P(wn​∣wn−1​)来估计所有历史单词下产生下个单词的概率 P ( w n ∣ w 1 : n − 1 ) P(w_n|w_{1:n-1}) P(wn​∣w1:n−1​)，即
P ( w n ∣ w n − 1 ) ≈ P ( w n ∣ w 1 : n − 1 ) (6) P(w_n|w_{n-1}) \approx P(w_n|w_{1:n-1}) \tag 6 P(wn​∣wn−1​)≈P(wn​∣w1:n−1​)(6)

这里的Bi是双的意思，还有后面会看到的Uni(单)、Tri(三)。

N-gram的这种简化实际上是一种假设，马尔科夫假设——一个单词的概率只取决于前面 N − 1 N-1 N−1个单词的假设。这里 N = 2 N=2 N=2为Bi-gram。类似地，可以有Unigram(与前面单词无关，都是独立的)或Trigram(只依赖于过去的两个单词)甚至n-gram( N > 2 N>2 N>2，依赖于过去的 N − 1 N-1 N−1个单词)。

那么我们就可以写出n-gram估计下一个单词条件概率的通用公式。这里我们使用 N N N描述n-gram中的大小，所以 N = 2 N=2 N=2意味着bigram。那么下个单词的概率如下：
P ( w n ∣ w 1 : n − 1 ) ≈ P ( w n ∣ w n − N + 1 : n − 1 ) (7) P(w_n|w_{1:n-1}) \approx P(w_n|w_{n-N+1}:n-1) \tag 7 P(wn​∣w1:n−1​)≈P(wn​∣wn−N+1​:n−1)(7)
如果基于bigram计算整个序列的概率，通过将 ( 6 ) (6) (6)带入 ( 5 ) (5) (5)有：
P ( w n ∣ w 1 : n = 1 ) ≈ P ( w n ∣ w n − 1 ) (8) P(w_n|w_{1:n=1}) \approx P(w_n|w_{n-1}) \tag 8 P(wn​∣w1:n=1​)≈P(wn​∣wn−1​)(8)

看起来不错，那么如何计算这些n-gram的概率呢？一种估计概率的直觉做法是最大似然估计(maximum likelihood estimation,MLE)。那么怎么做呢

我们从语料库中获取每个单词的计数，然后进行归一化，得到0~1之间的数值，就可以得到n-gram模型参数的MLE估计。

比如，给定起那么单词 w n − 1 w_{n-1} wn−1​计算单词 w n w_n wn​的bigram概率，我们首先计算bigram数量 C ( w n − 1 w n ) C(w_{n-1}w_n) C(wn−1​wn​)，这里bigram数量指的是这两个单词一起出现的数量。然后使用所有单词 w n − 1 w_{n-1} wn−1​的unigram计算来归一化：
P ( w n ∣ w n − 1 ) = C ( w n − 1 w n ) C ( w n − 1 ) (9) P(w_n|w_{n-1}) = \frac{C(w_{n-1}w_n)}{C(w_{n-1})} \tag 9 P(wn​∣wn−1​)=C(wn−1​)C(wn−1​wn​)​(9)
那么对于n-gram参数的MLE估计则为：
P ( w n ∣ w n − N + 1 : n − 1 ) = C ( w n − N + 1 : n − 1 w n ) C ( w n − N + 1 : n − 1 ) (10) P(w_n|w_{n-N+1:n-1}) = \frac{C(w_{n-N+1:n-1}w_n)}{C(w_{n-N+1:n-1})} \tag{10} P(wn​∣wn−N+1:n−1​)=C(wn−N+1:n−1​)C(wn−N+1:n−1​wn​)​(10)
上面的式子通过将特定序列的观察频次除以前缀的观察频次来估计n-gram概率，得到一个比率，该比率称为相对频率。使用相对频率作为估计概率的一种方法就是最大似然估计(MLE)。在MLE中，所得到 参数使给定模型 M M M(比如 P ( T ∣ M ) P(T|M) P(T∣M))的训练集 T T T​出现的可能性最大化。

这里有一个在实践中值得注意的问题。就是联合概率中，概率相乘的越多，乘积就越小。足够多的n-gram相乘会产生数值下溢。我们可以以对数形式表示为和计算。通过使用对数概率而不是原始概率，我们得到的数值就没那么小了。在对数空间中相加等于在线性空间中相乘，我们也可以在需要的时候转换回概率：
p 1 × p 2 × p 3 × p 4 = exp ⁡ ( log ⁡ p 1 + log ⁡ p 2 + log ⁡ p 3 + log ⁡ p 4 ) (11) p_1\times p_2 \times p_3 \times p_4 = \exp(\log p_1 + \log p_2 + \log p_3 + \log p_4) \tag{11} p1​×p2​×p3​×p4​=exp(logp1​+logp2​+logp3​+logp4​)(11)

评估语言模型

评估语言模型性能的最佳方法将其嵌入到应用程序中，并衡量应用程序的改进程度。这种端到端评价被称为外部评价(extrinsic evaluation)。外在评估它要知道一个特定的改进是否真的能帮助手头的任务的唯一方法。

不幸的是，端到端运行大型NLP系统通常非常昂贵。相反，如果有一个可以用来快速评估语言模型中潜在改进的度量标准就好了。内部评估(intrinsic evaluation)指标是一种独立于任何应用程序来衡量模型质量的指标。

对于语言模型的内在评估，我们需要一个测试集。与我们领域中的许多统计模型一样，n-gram模型的概率来自它被训练的语料库，训练集或训练语料库。然后，我们可以通过n-gram模型在一些不可见的数据(称为测试集或测试语料库)上的性能来衡量它的质量。

所以，如果我们有一个文本语料库，想要比较两个不同的n-gram模型，我们把数据分成训练集和测试集，在训练集上训练两个模型的参数，然后比较两个训练的模型拟合测试集的程度。

但是“拟合测试集”是什么意思呢?答案很简单:哪个模型赋予测试集更高的概率，这意味着它能更准确地预测测试集是一个更好的模型。给定两个概率模型，更好的模型是与测试数据更紧密的模型，或者更好地预测测试数据的细节，因此将为测试数据分配更高的概率。

由于我们的评价指标是基于测试集概率的，所以重要的是不要让测试句子进入训练集。假设我们要计算一个特定的“测试”句子的概率。如果我们的测试句子是训练的一部分语料库中，当它发生时，我们会错误地将其赋值为人为的高概率在测试集中。

我们称这种情况为在测试集上训练。这会引入了一种偏差，使所有的概率看起来都过高，并导致困惑度(perplexity)上的巨大不准确性，困惑度是一个基于概率的指标。

困惑度

给定测试集 W = w 1 w 2 ⋯ w N W=w_1w_2\cdots w_N W=w1​w2​⋯wN​，困惑度(perplexity)简记为PP，计算为：
PP ( W ) = P ( w 1 w 2 ⋯ w N ) − 1 N = 1 P ( w 1 w 2 ⋯ w N ) N (12) \begin{aligned} \text{PP}(W) &= P(w_1w_2\cdots w_N)^{-\frac{1}{N}} \ &= \sqrt[N]{\frac{1}{P(w_1w_2\cdots w_N)}} \end{aligned}\tag{12} PP(W)​=P(w1​w2​⋯wN​)−N1​=NP(w1​w2​⋯wN​)1​ ​​(12)
上面是开 N N N次根。我们可以使用链式法则展开 W W W的概率：
P P ( W ) = ∏ i = 1 N 1 P ( w i ∣ w 1 ⋯ w i − 1 ) N (13) PP(W) = \sqrt[N]{\prod_{i=1}^N\frac{1}{P(w_i|w_1\cdots w_{i-1})}} \tag{13} PP(W)=Ni=1∏N​P(wi​∣w1​⋯wi−1​)1​ ​(13)
如果我们使用bigram语言模型计算 W W W的困惑度：
P P ( W ) = ∏ i = 1 N 1 P ( w i ∣ w i − 1 ) N (14) PP(W) = \sqrt[N]{\prod_{i=1}^N\frac{1}{P(w_i|w_{i-1})}} \tag{14} PP(W)=Ni=1∏N​P(wi​∣wi−1​)1​ ​(14)
注意到公式 ( 13 ) (13) (13)中的倒数，单词序列的条件概率越高，它的困惑度就越低。因此最小化困惑度就相当于最大化测试集概率。

还有另一种方法来看待困惑度：作为一种语言的加权平均分支因子。一种语言的分支因子是指在任何一个单词后面可能出现的下一个单词的数量。考虑识别阿拉伯数字的任务（0,1,2，…，9）。假定（在某些训练集中和某些测试集中）10个数字中的每一个都以相同的概率出现 P = 1 10 P=\frac{1}{10} P=101​ 。这种迷你语言的困惑实际上是10。为了看到这一点，假设一个由长度为N的数字组成的测试字符串，并假设在训练集中，所有的数字都以相同的概率出现。困惑将会是：
P P ( W ) = P ( w 1 w 2 ⋯ w N ) − 1 N = ( 1 10 N ) − 1 N = ( 1 10 ) − 1 = 10 (15) \begin{aligned} PP(W) &= P(w_1w_2\cdots w_N)^{-\frac{1}{N}} \ &= (\frac{1}{10}^N) ^{-\frac{1}{N}}\ &= (\frac{1}{10}) ^{-1}\ &= 10 \end{aligned} \tag {15} PP(W)​=P(w1​w2​⋯wN​)−N1​=(101​N)−N1​=(101​)−1=10​(15)
但是假设数字0非常频繁，而且比其他数字出现得频繁得多。假设0在训练集中出现了91次，其他的数字各出现了1次。现在我们看到以下的测试集：0 0 0 0 0 3 0 0 0 0。我们应该期望这个测试集的困惑度会更低，因为大多数时间下一个数字将是零，这是非常可预测的，即有一个很高的概率为零。因此，虽然分支因子仍然是10，但困惑度或加权分支因子较小。

References

1. Speech and Language Processing
2. 自然语言处理——语言模型