N-Gram 模型
作者丨Jerry
编辑 丨 zandy
介绍
在搜索引擎中输入搜索词，会自动出来一系列的联想词，猜测用户后续可能需要输入的词，如图1-1所示，用户如果继续输入，那幺联想词会随用户输入变化，如果从中选择符合意图的词作为搜索词，搜索引擎则会展示搜索结果。 搜索引擎的这一功能大大提高了交互性，方便用户更快更好地搜索。 这里应用了N-Gram模型，通过分析大规模的用户日志，展示与用户输入的搜索词组合概率最高的词作为联想词 。
图1-1 搜索引擎搜索联想词示例
对词序列赋予概率的模型称为语言模型(Language Model)，N-Gram是一种在自然语言处理(NLP)中常用的语言模型，常用于语音\手写识别、机器翻译等领域。 N-Gram是N个词的序列，2-gram (或者 bigram)是两个词的序列如“中国/人民”，“打开/大门”，3-gram (或者 trigram)是三个词的序列如“中国/人民/万岁”，“打开/图书馆/大门”，同样的还有4-gram、5-gram等，这里分词用/分隔，后面文章分词也都用/分隔不再另作说明。 下面章节将介绍N-Gram模型如何根据前面的词来估计后面词的概率以及怎幺给整个序列赋予概率值。
N-Gram模型
让我们先从一个小任务介绍开始，给定一个词的前序几个词，如何计算这个词的出现概率呢？
比如前序词为“想/去”，那幺后面一个词为“公园”的概率可表示为：
P(公园|想/去) （2-1）
可以用相对词频的方法估计概率，观察一个较大的语料，计算“想/去”出现的次数：C(想/去)，以及“想去”后面跟“公园”的次数C(想/去/公园)，那幺：
P(公园|想/去)=C(想/去/公园 )/C(想/去) （ 2-2）
如果语料足够大，比如互联网，你可以利用算式2-2进行计算并且估计出概率值。利用这种直接用词频统计的方法来估计概率值对某些例子可以取得较好的效果，然而即使用互联网这幺庞大的语料库对另一些例子也不能很好的估计。因为语言是具有创造性的，它会不停地被创造出来，我们也总是没法覆盖所有的语料。另外对例子的简单扩展也可能在网上找不到任何例子, 比如”王小二/想/去/公园”，导致统计次数为零。
同样的，如果我们想计算整个序列的概率如“想/去/公园”，就需要知道所有含有三个词的序列中有多少是“想/去/公园”这样的序列，这样可以将“想/去/公园”的序列数目除以所有含有三个词的序列数目得到概率，这样感觉也很困难。因此引入了一个比较聪明的办法来估计序列W的概率。将n个单词 表示为 ，我们用 来表示 的联合概率。现在我们开始计算 ，可以使用链式法则进行分解：
（2-3）
应用链式法则得到如下：
（2-4）
从链式法则可以看出计算序列的联合概率与给定前序词序列计算某一个词的条件概率之间的关系，算式2-4说明计算序列的联合概率可以将每个词的条件概率相乘得到，但是链式法则实际上好像也帮不上忙，因为在给定前序词序列的前提下我们不知道如何计算某一个词的条件概率值 。如前所述，不能通过计算跟在一个长序列后的词的出现次数来估计概率值，因为语言具有创造性，新的说法时刻都在产生，某种新的说法还可能从来都没有出现过。n-gram模型并不能计算整个前序词序列的概率，而只是计算最后几个词的近似概率。
Bigram模型仅仅计算条件概率值 ，来替代计算 。举前面的例子：
P(公园|想/去) （2-5）
我们可以用
P(公园|去) （2-6）
来近似估计。当我们用bigram模型来预测下一个词的条件概率时，我们在作如下的近似估计：
（2-7）
某一个词的概率仅仅依赖于它前一个词的概率，这个假设称为马尔可夫(Markov)假设。马尔可夫模型是一种概率模型，假设我们不用回顾太远的历史就可以预测未来事件发生的概率。Bigram往前看一个词，Trigram往前看两个词，而N-Gram往前看n-1个词。
因此，采用n-gram估计一个词序列中下一个词概率的通用算式为：
（2-8）
结合算式2-4和2-7，计算整个词序列的算式可以转换为：
（2-9）
那幺如何来估计bigram或者n-gram概率呢？很容易想到的一种方法就是极大似然估计（maximum likelihood estimation），即从语料中获取要统计的词频，并将其归一化到（0,1）。
举例来说，给定词y的前序词x, 我们来计算bigram概率值，首先我们统计bigram的词频C(xy),然后将其除以以x开头的bigram词频总和进行归一化：
（2-10）
我们还可以对上式进行简化，因为以开头的所有bigram的总和与的unigram（即词频）值是相同的， 算式2-10可转换为：
（2-11）
让我们再看一个有三句话组成的小语料的例子。我们首先对每句话进行扩充，加上句首标记和句尾标记，为了能够让每个单词都有bigram的上下文，如下：
对这个小语料进行bigram概率统计如下：
n-gram的通用的极大似然估计算式如下：
（2-12）
算式2-12类似于算式2-11，通过将观察词序列的出现次数除以它的前缀次数获得。这个比率称为相对词频。通过相对词频来估计词序列概率是极大似然估计的一个例子。极大似然估计即在给定模型M的基础上极大近似地估计了训练集（ ）。举个例子，假设Chinese这个词在拥有一百万词的语料库（如布朗Brown语料库）里出现了400次。那幺从其他也拥有一百万词的语料库随机挑选一个词为Chinese的概率是多少呢？极大似然估计的概率值为 或者0.0004。0.0004并不是Chinese这个词在所有情况下出现概率的最佳估计值，它可能可以说明在其他语料库或者上下文中Chinese这个词并不常用。但是这个概率值使得Chinese这个词在一个一百万词的语料中有极大的可能性会出现400次左右。
让我们再看个小例子，比上面仅仅只有3句话14个词的语料大一点。我们使用的例子来自已经失效的伯克利酒店项目中的语料，这个项目是基于加州伯克利地区的酒店数据库来回答酒店相关问题的一个问答系统。下面是一些用户提问的样本（总样本量为9332个句子，可以从网上获得）：
图2-1显示了伯克利酒店项目中一个语料片段的bigram数目。图表中的大部分统计数据都为0，事实上我们选取得词样本都是在语境中彼此相邻的，如果我们随机选取词样本，统计数据将会变得更加稀疏。
图2-1 8个词样本bigram统计数目（伯克利酒店项目包含9332个句子，词样本数V=1446），统计数为0的单元格灰色表示。
图2-2 伯克利酒店项目8个词样本bigram概率值，概率值为0的单元格灰色表示。
图2-2显示了归一化后的bigram概率（即将图2-1中每个单元格的统计值除以unigram值），unigram取值如下：
一些其他有用的概率值如下：
现在我们可以统计将词的bigram概率值相乘来计算句子的概率值了。如“I want English food”或者“I want Chinese food”。算式如下：
如何计算“I want Chinese food”的概率值留给读者作为练习。那幺我们从bigram模型中统计出了哪些语言现象呢？上述的bigram概率值提示了一些句法规则，比如eat后面跟名词或者形容词，to后面跟动词，还提示了一些人物活动的场景，如一些概率值较高的句子都是以I单词开始，还有一些更多的是给了文化上的提示如人们寻找Chinese Food比寻找English Food的概率值更高。
为了方便讲解，上文我们讲述了bigram模型，对于trigram和4-gram模型也都是通用的，trigam往前看2个词，4-gram往前看3个词。对于高维的n-gram模型，需要在句子的开头和结尾添加伪词作为第一个词或者最后一个词的上下文。举个例子，对于trigram模型来说，我们可以在句子开头添加两个伪词方便计算第一个词的概率值，如P(I|）。
我们喜欢用log的形式来表示语言模型的概率值，因为概率值总是小于或等于1的数，我们将越多的概率值相乘，那幺我们得到的值就越小。将足够多的n-gram概率值相乘会带来下溢效应。用概率值的log值来替代，值就不会变的那幺小。log空间上相加等同于概率值的相乘，所以我们将概率值取log相加。如果我们最终需要转换为实际的概率值，那幺只要将log 空间进行指数转换得到，如下：
语言模型评估
评估语言模型最好的方式是将它嵌入应用中，评估应用是否有改善。 这种端到端的评估方式称为外部评估。 外部评估是衡量某个组件的改善是否真正对整体任务有帮助的唯一有效的评估方式。 比如对于语音识别的应用，我们可以运行两次语音识别应用来比较两个语言模型，每次分别用一个语言模型，最终看用哪个语言模型得到的识别准确率更高。
但是，运行端到端的大型NLP系统代价是比较昂贵的，因此我们需要一种替代的方法能够快速方便地评估语言模型的潜在改善效果。 内部评估可以不依赖于任何应用并能独立评估语言模型的效果。
语言模型的内部评估需要测试集，和大多数的统计模型一样，n-gram模型的概率来自训练的语料，称为训练集或训练语料。 我们用一些没有见过的语料来评估n-gram模型的效果，称为测试集或测试语料。 我们有时也称这种不在训练集中的测试语料为隔离语料（held out corpora)，因为将它们与训练语料隔离开来。
如果我们拥有一个语料库，并且想比较两个n-gram模型的效果，可以将语料库分为训练集和测试集两个部分。 用训练集分别训练两个模型，然后用测试集比较两个模型的效果，即看哪个模型与测试集更符合。
那幺，怎幺才是跟测试集更符合呢？ 答案很简单： 哪个模型给测试集更高的概率值，哪个模型就更好，因为意味着模型能够更精确的预测结果。 给定两个概率模型，更好的模型与测试集会有更好的拟合度或者说能更好地预测测试集的细节，显然它将赋予测试集更高的概率值。
因为我们的评估是依赖测试集的概率值，不让测试语料混入训练集变得非常关键。 假设我们正在计算测试集某一个句子的概率值，如果该句子也出现在训练集中，将会赋予它一个人为的高概率值。 我们将这种情形称为用测试集训练。 这种情况将导致模型概率值偏高。
有时候我们经常使用一种特殊的测试集，并且利用这些隐性特征进行训练。 然后再用从未见过的测试集进行测试。 这种情况下，称第一个测试集为开发测试集或者开发集。 那幺如何将语料划分为开发集、训练集和测试集呢？ 我们希望测试集越大越好，因为过小的测试集没有代表性，同时我们也希望训练集越大越好。 这样，我们就需要一个最小的测试集合，它能够弥补训练集和测试集的统计差异。 实际上，我们通常将语料分为三部分，80%训练集，10%开发集以及10%测试集。 测试集有两种获取方式，一种是从语料连续获取，另一种是随机获取语料中的语句。
评估指标-困难度（Perplexity）
实际操作上，我们并不采用概率值来评估语言模型，而是用困难度(Perplexity)这个变量来评估。 困难度(Perplexity)常用缩写的PP表示。 对于测试集:
困难度表示如下：
(4-1)
通过链式规则转换如下：
(4-2)
如果只计算bigram的概率值，那幺如下：
(4-3)
根据PP(W)的算式定义，词序列的条件概率值越大，困难度越小。 因此语言模型减小测试集的困难度等同于加大词序列的概率值。 算式4-2和4-3使用的词序列为测试集的所有词序列。 因为词序列会跨越句子边界，因此我们需要在句首和句尾添加和标志，方便概率计算。 另外在统计总词数时需要统计句尾标志，但句首标志不统计。
可以换一种方式看待困难度： 作为语言的带权平均分支因子(weighted average branching
factor)。 可以跟在任何词后面的词的数目称为语言分支因子。 有个任务识别英文数字（zero, one, two,…, nine），假定这十个数字在训练集和测试集的出现概率是相同的，都是1/10。 那幺所有这十个数组成小语言集合的困难度为10。 怎幺得到的呢，假设有一个测试字符串全部由数字组成，长度为N，同时在训练集中每个数字出现的概率都相等。 根据算式4-2，困难度如下：
(4-4)
但是让我们考虑另一种情况假设数字零出现的很频繁，出现频率远远大于其他数字。假设在训练集中零出现了91次，其他数字各只出现了一次。现在让我们来观察测试语料：0 0 0 0 0 3 0 0 0 0。对于该测试语料，困难度会降低，因为大多数情况下下一个数字是零，它具有很高的概率值，可预测性很强。这种情况下，分支因子仍然为10，但是困难度或者权重分支因子却要小的多。其实困难度与信息论中熵的概念有类似之处。
最后让我们看一个例子，困难度是如何来评估比较不同的n-gram模型的。我们用含19,979独立词的华尔街日报3800万单词语料库来训练一元（unigram）、二元（bigram）和三元（trigram）语言模型。然后用算式4-2在150万单词的测试集上计算每个语言模型的困难度。结果如下表：
从上表可以看到，从n-gram模型得到的词序列信息越多，那幺困难度越低。 从算式4-2可以看出困难度的值与词序列可能性的呈负相关。
在计算困难度时，n-gram模型的构建不应该依赖于任何的测试集数据或测试集的词典，任何的测试集相关的信息都会使困难度人为降低。 两个语言模型的困难度是否可比较依赖于它们需要建立在相同词典上。
困难度(内部评估指标)的改善不能代表语言处理任务如语音识别或机器翻译（外部评估指标）一定有所提高。 但是困难度经常与外部评估指标的改善相关，因此它经常用来快速检测模型算法的优劣。 但是模型困难度的提高总是需要嵌入到端到端的任务中才能确定模型是否真的得到了改善。
小结
本文是对N-Gram模型及其应用的简单介绍，主要内容参考《Speech and Language Processing (3rd ed. draft)》第三章部分章节进行翻译，大部分图片均来源于该书，疏漏和错误之处，望批评指正。
About The Author
