让我们从计算P（w | h）的任务开始，w代表一个词，h代表在它之前的文本（历史）。假设历史h是“its water is so transparent that”，我们想知道下一个词是“the”的概率是：
P(the|its water is so transparent that)
估计这个概率的一种方法是用相对频率：取一个非常大的语料库，计算我们看到“its water is so transparent that”的次数，然后计算它后面跟随“the”的次数。通过如下公式计算在我们看到h出现的时候，有多少ci次后面跟着w：
有了足够大的语料库，例如网络，我们可以计算这些计数并估计概率。
不难发现，这个方法非常不现实。我们需要引入更聪明的方法来估计给定历史h的单词w的概率，或者整个单词序列W的概率。
为了表示一个特定的随机变量X_{i}取值“the”的概率P（X_{i}= the）——后面简写为P（the）——我们将由N个词组成的序列写作或者w_{1} ... w_{n}或w_{1}^n。对于具有特定值的序列我们将联合概率写为P（X = w_{1}，Y = w_{2}，Z = w_{3}，..., W=w_{n}），简写为P（w_{1}，w_{2}，...，w_{n}）。
使用链式法则将上述概率分解得：
链规则（chain rule）显示计算一个序列的联合概率，和计算给定之前词的一个词的条件概率之间的联系。上述公式表明我们可以通过将许多条件概率相乘来估计整个词序列的联合概率。而N-gram模型的逻辑在于，我们可以用最后几个单词来估计历史h，而不是计算一个词在整个历史中的概率。
在这里，我们还需要引入马尔科夫假设，假设单词的概率只取决于前一个词的假设称为马尔可夫假设。马尔科夫模型是一类概率模型，它假定我们可以预测未来某个单位的概率，而不用过分追求过去。如果我们仅用最后一个单词对概率进行估计，这就是bigram，我们可以从bigram（仅考虑过去的一个词）到trigram（考虑过去两个词）再推广到N-gram（考虑过去N个词）。
N-gram估计序列中下一个单词的条件概率的一般方程是：
若我们使用bigram模型，则估计序列的联合概率就可以写做：
举例来说，假设目前有三个句子：
<s> I am Sam </s>
<s> Sam I am </s>
<s> I do not like green eggs and ham</s>
用bigram模型，我们可以求得以下概率：
P(I|<s>) = 2/3 P(Sam|<s>) = 1/3 P(am|I) = 2/3
P(</s>|Sam)= 1/2 P(Sam|am) = 1/2 P(do|I) = 1/3
[描述来源：Jurafsky, D.; Martin, J. H.Speech and Language Processing(3rd ed. draft).]
发展历史
描述
n-gram是一种非常常用且应用范围很广的模型，早期应用主要集中在文本压缩，拼写检查，加速字符串查找，文献语种识别等。Peter F. Brown及Jenifer C. Lai等学者讨论了从文本样本中的以前的单词中预测单词的问题，特别是基于词类的n-gram模型，并比较了几种基于与其他词语共同出现频率的词类分类统计算法。
1994年William B. Cavnar和John M. Trenkle提出了一种基于n-gram的文本分类方法，可以容忍文本错误。该系统体积小，速度快，并在一次测试中，对用不同语言编写的Usenet新闻组文章的正确分类率达到99.8％。Marc Damashek将从n-gram模型得到的信息与简单的向量空间技术结合起来，使大量多语言文档集合中的排序，分类和检索切实可行。该方法不需要关于文档内容或语言的先验信息，文中还使用英文和日文文件给出了实例。
2003年继机器翻译社区采用BLEU / NIST评分流程进行自动评估之后，Chin-Yew Lin和Eduard Hovy用unigram进行了类似研究并取得了近似于人类的优秀表现。同年Yoshua Bengio等学者建议通过学习单词的分布式表示来对抗维度灾难，这允许每个训练句子关联指数数量的语义上相邻的句子。他们报告了使用神经网络的实验，在两个文本语料库上的结果都显示所提出的方法显着改进了当时最先进的n-gram模型，并且所提出的方法允许利用更长的上下文。
2010年，以twitter为语料库，Alexander Pak, Patrick Paroubek利用n-gram进行了情感分析和意见挖掘。
主要事件
年份 | 事件 | 相关论文/Reference |
1992 | Peter F. Brown及Jenifer C. Lai等学者讨论了从文本样本中的以前的单词中预测单词的问题，特别是基于词类的n-gram模型，并比较了几种基于与其他词语共同出现频率的词类分类统计算法 | Brown, P. F. et al. (1992).Class-basedn-gram models of natural language. Computational Linguistics. 18(4): 467-479. |
1994 | William B. Cavnar和John M. Trenkle提出了一种基于n-gram的文本分类方法 | Cavnar, W. B.; Trenkle, J. M. (1994).N-Gram-Based Text Categorization.Proceedings of the Third Symposium on Document Analysis and Information Retrieval. |
1995 | Marc Damashek将从n-gram模型得到的信息与简单的向量空间技术结合起来，使大量多语言文档集合中的排序，分类和检索切实可行 | Damashek, M. (1995). Gauging Similarity with n-Grams: Language-Independent Categorization of Text.Science. 267(5199): 843-848. |
2003 | Chin-Yew Lin和Eduard Hovy用unigram进行了机器翻译的自动评估并取得了近似于人类的优秀表现 | Lin, C. Y.; Hovy, E. (2003).Automatic evaluation of summaries using N-gram co-occurrence statistics.Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology. pp 71-78. |
2003 | Yoshua Bengio等学者建议通过学习单词的分布式表示来对抗维度灾难，这允许每个训练句子关联指数数量的语义上相邻的句子 | Bengio, Y.; Ducharme, R.; Vincent, P.; Jauvin, C. (2003).A Neural Probabilistic Language Model. JMLR. 3: 1137-1155. |
2010 | 以twitter为语料库，Alexander Pak, Patrick Paroubek利用n-gram进行了情感分析和意见挖掘 | Pak, A.; Paroubek, P. (2010). Twitter as a Corpus for Sentiment Analysis and Opinion Mining. |
发展分析
瓶颈
n-gram需要大量的训练数据来确定参数，当n增长时，计算压力和参数空间会迅速增长；另外，n-gram还遭受着因数据稀疏导致的平滑问题，不过这一点目前已经存在许多相关研究。
它的缺点是需要相当规模的训练文本来确定模型的参数。当N很大时，模型的参数空间过大。所以常见的N值一般为1,2。还有因数据稀疏而导致的数据平滑问题，不过这一点目前已经存在许多相关研究。
未来发展方向
n-gram的优点在于它包含了前N-1个词所能提供的全部信息，并且原理简单易实现，目前在文本特征提取十分受欢迎。
Contributor: Yuanyuan Li