N-Gram（有时也称为N元模型）是 自然语言 处理中一个非常重要的概念，通常在NLP中，人们基于一定的语料库，可以利用N-Gram来预计或者评估一个句子是否合理。另外一方面，N-Gram的另外一个作用是用来评估两个字符串之间的差异程度。这是模糊匹配中常用的一种手段。本文将从此开始，进而向读者展示N-Gram在自然语言处理中的各种powerful的应用。
基于N-Gram模型定义的字符串距离
利用N-Gram模型评估语句是否合理
使用N-Gram模型时的数据平滑算法
欢迎关注白马负金羁的博客 http://blog.csdn.net/baimafujinji ，为保证公式、图表得以正确显示，强烈建议你从该地址上查看原版博文。本博客 主要关注方向 包括：数字图像处理、 算法 设计与分析、 数据结构 、 机器学习 、数据挖掘、统计分析方法、自然语言处理。
基于N-Gram模型定义的字符串距离
在自然语言处理时，最常用也最基础的一个操作是就是“模式匹配”，或者称为“字符串查找”。而模式匹配（字符串查找）又分为 精确匹配 和 模糊匹配 两种。
所谓精确匹配，大家应该并不陌生，比如我们要统计一篇文章中关键词 “ information ” 出现的次数，这时所使用的方法就是精确的模式匹配。这方面的算法也比较多，而且应该是计算机相关专业必修的基础课中都会涉及到的内容，例如KMP算法、BM算法和BMH算法等等。
另外一种匹配就是所谓的模糊匹配，它的应用也随处可见。例如，一般的文字处理软件（例如，Microsoft Word等）都会提供拼写检查功能。当你输入一个错误的单词，例如 “ informtaion ” 时，系统会提示你是否要输入的词其实是 “ information ” 。将一个可能错拼单词映射到一个推荐的正确拼写上所采用的技术就是模糊匹配。
模糊匹配的关键在于如何衡量两个长得很像的单词（或字符串）之间的“差异”。这种差异通常又称为“距离”。这方面的具体算法有很多，例如基于编辑距离的概念，人们设计出了 Smith-Waterman 算法和Needleman-Wunsch 算法，其中后者还是历史上最早的应用动态规划思想设计的算法之一。现在Smith-Waterman 算法和Needleman-Wunsch 算法在生物信息学领域也有重要应用，研究人员常常用它们来计算两个DNA序列片段之间的“差异”（或称“距离”）。甚至于在LeetCode上也有一道 “No.72 Edit Distance” ，其本质就是在考察上述两种算法的实现。可见相关问题离我们并不遥远。
N-Gram在模糊匹配中的应用
事实上，笔者在新出版的 《算法之美——隐匿在数据结构背后的原理》 一书中已经详细介绍了包括Needleman-Wunsch算法、Smith-Waterman算法、N-Gram算法、Soundex算法、Phonix算法等在内的多种距离定义算法（或模糊匹配算法）。而今天为了引出N-Gram模型在NLP中的其他应用，我们首先来介绍一下如何利用N-Gram来定义字符串之间的距离。
我们除了可以定义两个字符串之间的编辑距离（通常利用Needleman-Wunsch算法或Smith-Waterman算法）之外，还可以定义它们之间的N-Gram距离。N-Gram（有时也称为N元模型）是自然语言处理中一个非常重要的概念。假设有一个字符串 s
，那么该字符串的N-Gram就表示按长度 N 切分原词得到的词段，也就是 s
中所有长度为 N 的子字符串。设想如果有两个字符串，然后分别求它们的N-Gram，那么就可以从它们的共有子串的数量这个角度去定义两个字符串间的N-Gram距离。但是仅仅是简单地对共有子串进行计数显然也存在不足，这种方案显然忽略了两个字符串长度差异可能导致的问题。比如字符串 girl 和 girlfriend，二者所拥有的公共子串数量显然与 girl 和其自身所拥有的公共子串数量相等，但是我们并不能据此认为 girl 和girlfriend 是两个等同的匹配。
为了解决该问题，有学者便提出以非重复的N-Gram分词为基础来定义 N-Gram距离这一概念，可以用下面的公式来表述：
|GN(s)|+|GN(t)|−2×|GN(s)∩GN(t)|
此处，|GN(s)|
是字符串 s
的 N-Gram集合，N 值一般取2或者3。以 N = 2 为例对字符串Gorbachev和Gorbechyov进行分段，可得如下结果（我们用下画线标出了其中的公共子串）。
有兴趣的读者可以在引用相关JAR包之后在Eclipse中执行上述Java程序，你会发现，和我们预期的一样，字符串Gorbachev和Gorbechyov所得之距离评分较高（=0.7），说明二者很接近；而girl和girlfriend所得之距离评分并不高（=0.3999），说明二者并不很接近。
利用N-Gram模型评估语句是否合理
从现在开始，我们所讨论的N-Gram模型跟前面讲过N-Gram模型从外在来看已经大不相同，但是请注意它们内在的联系（或者说本质上它们仍然是统一的概念）。
为了引入N-Gram的这个应用，我们从几个例子开始。首先，从统计的角度来看，自然语言中的一个句子 s
可以由任何词串构成，不过概率 P(s)
有大有小。例如：
s1
= 我刚吃过晚饭
s2
= 刚我过晚饭吃
显然，对于中文而言 s1
是一个通顺而有意义的句子，而s2
则不是，所以对于中文来说，P(s1)>P(s2)
。但不同语言来说，这两个概率值的大小可能会反转。
其次，另外一个例子是，如果我们给出了某个句子的一个节选，我们其实可以能够猜测后续的词应该是什么，例如
the large green __ . Possible answer may be “mountain” or “tree” ?
Kate swallowed the large green __ . Possible answer may be “pill” or “broccoli” ?
显然，如果我们知道这个句子片段更多前面的内容的情况下，我们会得到一个更加准确的答案。这就告诉我们，前面的（历史）信息越多，对后面未知信息的约束就越强。
如果我们有一个由 m
个词组成的序列（或者说一个句子），我们希望算得概率 P(w1,w2,⋯,wm)
，根据链式规则，可得
P(w1,w2,⋯,wm)=P(w1)P(w2|w1)P(w3|w1,w2)⋯P(wm|w1,⋯,wm−1)
这个概率显然并不好算，不妨利用马尔科夫链的假设，即当前这个词仅仅跟前面几个有限的词相关，因此也就不必追溯到最开始的那个词，这样便可以大幅缩减上诉算式的长度。即P(wi|w1,⋯,wi−1)=P(wi|wi−n+1,⋯,wi−1)
特别地，对于 n
取得较小值的情况当 n=1
, 一个一元模型（unigram model)即为P(w1,w2,⋯,wm)=∏i=1mP(wi)
当 n=2
, 一个二元模型（bigram model)即为P(w1,w2,⋯,wm)=∏i=1mP(wi|wi−1)
当 n=3
, 一个三元模型（trigram model)即为P(w1,w2,⋯,wm)=∏i=1mP(wi|wi−2wi−1)
接下来的思路就比较明确了，可以利用最大似然法来求出一组参数，使得训练样本的概率取得最大值。
对于unigram model而言，其中c(w1,..,wn)
表示 n-gram w1,..,wn
在训练语料中出现的次数，M
是语料库中的总字数（例如对于 yes no no no yes 而言，M=5
）P(wi)=C(wi)M
对于bigram model而言，P(wi|wi−1)=C(wi−1wi)C(wi−1)
对于n
-gram model而言，P(wi|wi−n−1,⋯,wi−1)=C(wi−n−1,⋯,wi)C(wi−n−1,⋯,wi−1)
来看一个具体的例子，假设我们现在有一个语料库如下，其中<s1><s2>
是句首标记，</s2></s1>
是句尾标记：
<s1><s2>yesnonononoyes</s2></s1><s1><s2>nononoyesyesyesno</s2></s1>
下面我们的任务是来评估如下这个句子的概率：<s1><s2>yesnonoyes</s2></s1>
我们来演示利用trigram模型来计算概率的结果P(yes|<s1><s2>)=12,P(no|<s2>yes)=1P(no|yesno)=12,P(yes|nono)=25P(</s2>|noyes)=12,P(</s1>|yes</s2>)=1
所以我们要求的概率就等于：12×1×12×25×12×1=0.05
再举一个来自文献[1]的例子，假设现在有一个语料库，我们统计了下面一些词出现的数量
下面这个概率作为其他一些已知条件给出：P(i|<s>)=0.25P(english|want)=0.0011P(food|english)=0.5P(</s>|food)=0.68
，则可以算得P(s1)=P(i|<s>)P(want|i)P(english|want)P(food|english)P(</s>|food)=0.25×0.33×0.0011×0.5×0.68=0.000031
使用N-Gram模型时的数据平滑算法
有研究人员用150万词的训练语料来训练 trigram 模型，然后用同样来源的 测试 语料来做验证，结果发现23%的 trigram 没有在训练语料中出现过。这其实就意味着上一节我们所计算的那些概率有空为 0，这就导致了数据稀疏的可能性，我们的表3中也确实有些为0的情况。对语言而言，由于数据稀疏的存在，极大似然法不是一种很好的参数估计办法。
这时的解决办法，我们称之为“平滑技术”（Smoothing）或者 “减值” （Discounting）。其主要策略是把在训练样本中出现过的事件的概率适当减小，然后把减小得到的概率密度分配给训练语料中没有出现过的事件。实际中平滑算法有很多种，例如：▸ Laplacian (add-one) smoothing▸ Add-k smoothing▸ Jelinek-Mercer interpolation▸ Katz backoff▸ Absolute discounting▸ Kneser-Ney
对于这些算法的详细介绍，我们将在后续的文章中结合一些实例再来进行讨论。
A Final Word
如果你能从前面那些繁冗、复杂的概念和公式中挺过来，恭喜你，你对N-Gram模型已经有所认识了。尽管，我们还没来得及探讨平滑算法（但它即将出现在我的下一篇博文里，如果你觉得还未过瘾的话），但是其实你已经掌握了一个相对powerful的工具。你可以能会问，在实践中N-Gram模型有哪些具体应用，作为本文的结束，主页君便在此补充几个你曾见过的或者曾经好奇它是如何实现的例子。
Eg.1 搜索引擎 （Google或者Baidu）、或者输入法的猜想或者提示。你在用百度时，输入一个或几个词，搜索框通常会以下拉菜单的形式给出几个像下图一样的备选，这些备选其实是在猜想你想要搜索的那个词串。再者，当你用输入法输入一个汉字的时候，输入法通常可以联系出一个完整的词，例如我输入一个“刘”字，通常输入法会提示我是否要输入的是“刘备”。通过上面的介绍，你应该能够很敏锐的发觉，这其实是以N-Gram模型为基础来实现的，如果你能有这种觉悟或者想法，那我不得不恭喜你，都学会抢答了！
Eg.2 某某作家或者语料库风格的文本自动生成。这是一个相当有趣的话题。来看下面这段话（该例子取材自文献【1】）：
“You are uniformly charming!” cried he, with a smile of associating and now and then I bowed and they perceived a chaise and four to wish for.
你应该还没有感觉到它有什么异样吧。但事实上这并不是由人类写出的句子，而是计算机根据Jane Austen的语料库利用trigram模型自动生成的文段。（Jane Austen是英国著名女作家，代表作有《傲慢与偏见》等）
再来看两个例子，你是否能看出它们是按照哪位文豪（或者语料库）的风格生成的吗？
This shall forbid it should be branded, if renown made it empty.
They also point to ninety nine point six billion dollars from two hundred four oh three percent of the rates of interest stores as Mexico and Brazil on market conditions.
答案是第一个是莎士比亚，第二个是华尔街日报。最后一个问题留给读者思考，你觉得上面两个文段所运用的n-gram模型中，n应该等于多少？
推荐阅读和参考文献：
[1] Speech and Language Processing. Daniel Jurafsky &James H. Martin, 3rd. Chapter 4[2] 本文中的一些例子和描述来自 北京大学 常宝宝 以及 The University of Melbourne “Web Search and Text Analysis” 课程的幻灯片素材
本文整理自网络，主要是对自然语言处理能发展和落地的方向进行总结，也算是对自然语言处理常见任务的总结。
NLP的四大任务如下：
序列标注（Sequence labeling）是我们在解决NLP问题时经常遇到的基本问题之一。在序列标注中，我们想对一个序列的每一个元素标注一个标签。一般来说，一个序列指的是一个句子，而一个元素指的是句子中的一个词。比如信息提取问题可以认为是一个序列标注问题，如提取出会议时间、地点等。
序列标注一般可以分为两类：
命名实体识别（Named entity recognition， NER）是信息提取问题的一个子任务，需要将元素进行定位和分类，如人名、组织名、地点、时间、质量等。
举个NER和联合标注的例子。一个句子为：Yesterday , George Bush gave a speech. 其中包括一个命名实体：George Bush。我们希望将标签“人名”标注到整个短语“George Bush”中，而不是将两个词分别标注。这就是联合标注。
1.1 BIO标注
解决联合标注问题最简单的方法，就是将其转化为原始标注问题。标准做法就是使用BIO标注。
BIO标注：将每个元素标注为“B-X”、“I-X”或者“O”。其中，“B-X”表示此元素所在的片段属于X类型并且此元素在此片段的开头，“I-X”表示此元素所在的片段属于X类型并且此元素在此片段的中间位置，“O”表示不属于任何类型。
比如，我们将 X 表示为名词短语（Noun Phrase, NP），则BIO的三个标记为：
因此可以将一段话划分为如下结果：
我们可以进一步将BIO应用到NER中，来定义所有的命名实体（人名、组织名、地点、时间等），那么我们会有许多 B 和 I 的类别，如 B-PERS、I-PERS、B-ORG、I-ORG等。然后可以得到以下结果：
[图片上传失败...(image-b1cfb3-1609330627120)]
1.2 序列标注常用模型
选择双向LSTM的原因是：当前词的tag和前后文都有关。
1.3 序列标注具体任务
（1）分词
（2）词性标注（Part-of-Speech tagging ，POS tagging)
（3）命名实体标注（name entity recognition, NER）
2.1 分类的具体任务
（1）文本分类、情感分类
3.1 具体任务
（1）句法分析、蕴含关系判断（entailment）
这类任务一般直接面向普通用户，提供自然语言处理产品服务的系统级任务，会用到多个层面的自然语言处理技术。
4.1 具体任务
（1）机器翻译（Machine Translation，MT）
Encoder-Decoder的最经典应用，事实上这一结构就是在机器翻译领域最先提出的。
（2）文本摘要、总结（Text summarization/Simplication）
输入是一段文本序列，输出是这段文本序列的摘要序列。
（3）阅读理解（Reading Comprehension）
将输入的文章和问题分别编码，再对其进行解码得到问题的答案。
（4）语音识别
输入是语音信号序列，输出是文字序列。
（5）对话系统（Dialogue Systerm）
输入的是一句话，输出是对这句话的回答。
（6）问答系统（Question-Answering Systerm）
针对用户提出的问题，系统给出相应的答案。
（7）自动文章分级（Automatic Essay Grading）
给定一篇文章，对文章的质量进行打分或分级。
1. 词法分析（Lexical Analysis）：对自然语言进行词汇层面的分析，是NLP基础性工作
2. 句子分析（Sentence Analysis）：对自然语言进行句子层面的分析，包括句法分析和其他句子级别的分析任务
3. 语义分析（Semantic Analysis）：对给定文本进行分析和理解，形成能勾够表达语义的形式化表示或分布式表示
4. 信息抽取（Information Extraction）：从无结构文本中抽取结构化的信息
5. 顶层任务（High-level Tasks）：直接面向普通用户，提供自然语言处理产品服务的系统级任务，会用到多个层面的自然语言处理技术
【1】序列标注中的BIO标注介绍，地址： https://blog.csdn.net/HappyRocking/article/details/79716212
【2】 http://nlpers.blogspot.com.au/2006/11/getting-started-in-sequence-labeling.html
【3】NLP 四大任务，地址： https://www.dazhuanlan.com/2019/08/21/5d5ca1e2826b9/
【4】NLP基本任务，地址： https://blog.csdn.net/lz_peter/article/details/81588430
【5】微信研究员解析深度学习在NLP中的发展和应用，地址： https://edu.csdn.net/course/play/8673
【6】从Word Embedding到Bert模型—自然语言处理中的预训练技术发展史 - 张俊林的文章 - 知乎 https://zhuanlan.zhihu.com/p/49271699
话说两年前我一脸蒙圈地开始了自己文本挖掘的职业生涯，领导给我的第一个任务就是文本分类任务。小伙伴手把手教我怎么来做一个三分类任务，上手还挺快，正能量爆炸，原来这就自然语言处理，也没有那么复杂吗？无知者无畏。
自然语言处理博大精深，越到细节处越是难，一不小心就从入门到放弃了。一个好的新手任务是入门到深入的前提，而文本分类任务就是一个很不错的选择，保准给你打满鸡血，至于能不能坚持到最后？就暂时不是我们关心的问题。万事开头难，好的开头有好结尾的概率会高一点。不啰嗦，回归正题开始胡说八道。
分类大家都知道吧？我且大胆地尝试下个定义，把事物按某特性划分为几种类别。
生活处处是分类，前段时间上海风风火火地垃圾分类，就算一种！按照垃圾的材质/是否可回收分类。垃圾分类出来没多久，有聪明的小伙伴就说我们是不是可以搞一个垃圾分类的模型，商机无限，我感叹小伙伴这头脑该去做ceo啊，也没有太在意。不过没多久市面上就有各种垃圾分类应用涌现，感觉错过一个亿的商机。
上学的时候，对分类的认识是不够的，觉得搞这么多分类干啥，有啥用啊。那时候文小刚大佬组里的文章喜欢各种分类，奈何智商有限，每次都云里雾里，大佬的世界我不懂。后来做了文本分类任务，才渐渐去想想为什么要分类？我想最简单的，分类意味着对事物认知，可以定位到更细的类别，可以进行筛选；分得越细，说明我们研究的越清楚，最终 …(原谅我浅薄的认知，故事编不下去了)
知道了分类也理解了分类的重要，再谈文本分类就简单了。所谓文本分类，说句废话，就是对文本按照某种特性进行分类。比如情感分类，按照文本的情感极性进行分类；还有最近在聊天机器人中使用到的，情绪分类，把文本分为开心、愤怒、失望…balabala；垃圾文本分类，识别文本是否为垃圾… 还有一些有意思的分类任务，比如去检测一句话的性别偏向，文本是否口语化的 … 都是我脑补的，大家也可以想想有哪些有意思的文本分类任务
从应用的层面来说，做文本分类，你首先要知道你的目标是什么，要构建一个什么样的分类模型？最好是梳理一套明确的分类标准，这样我们就可以去获取数据。或用规则或用人肉，都是可行的。有了数据集合，就可以尝试各种分类模型，可繁可简，可骚可闷… (当然你最终会认识到，模型并不是越复杂越好，简简单单或许才是最好的！)
此处假设我们已经明确了要做的分类任务，也有了一部分数据集。那么我们就可以说道说道文本分类的方法了，从简单到高大上的都可以吹一吹（反正吹牛逼又不用上税，说错了最多被打脸！我脸厚不怕）。
大家玩垃圾邮件识别任务的时候，可能会学到朴素贝叶斯吧，简单来说通过判断每个词在垃圾邮件中出现的概率，最终判断出整个文本是否为垃圾邮件。这时候大家会被反复灌输贝叶斯公式，一听名字觉得高大上，很多同学可能被吓退，但是当你真的写出来并理解之，简单优美大方！（数学果然是不是我这种屌丝气质的人可以搞的。）
不过朴素贝叶斯方法也太简单了，要满足条件独立假设，表现往往一般。这时我们可以上其他常规武器了，比如决策树，决策树的算法逻辑非常有意思，符合人们做决断的逻辑！通过逐一判断特征是否满足某些条件，来对文本进行分类。
如果你觉得一棵树妥妥不足决断，就可以上集成方法。所谓集成方法，就是单兵作战不行，那我们就群殴啊，总有一种办法来干死你。集成方法可以分为两类，一类是bagging方法，就是分别用几颗树单独来做决策，然后把它们的结果组合起来，随机森林就是其中一种；另一类是boosting方法，大概是一棵树决策有误差，那我再用一颗树来学习误差，如果不行我再来…有没有想到某公子子孙孙无穷尽也，当然我们作为凡人…
其他常规算法还有SVM（校招面试算法工程师感觉不会SVM都不好意思说自己懂机器学习），逻辑回归, 感知机 …
常规武器说完，那开始高级武器吧——蛇精网络。不过先慢慢铺垫一下，从我开始准备找工作的时候，深度学习就已经复苏，开始大红大紫，到处都是蛇精网络，深度学习.. 当年nature还是science出了几篇使用蛇精网络做强联量的，感觉整个物理圈子都躁动了，不过大佬们还是比较理性的指出蛇精网络没发总结出基本的物理定律。我们不是大佬，只兴奋滴看到这次饭碗终于有着落了。
个人觉得文本分类最好用的蛇精网络算法是fasttetxt，模型简单效率，准确率也不错，是众屌丝的理想选择。模型可以快速训练和上线应用，分分钟报告领导任务已经完成，请做下一步指示。不过fasttext虽然好，有一个问题啊，你不好吹牛逼啊，到年终汇报，你和各位大佬说我用fasttext完成某某任务，你很大概率和升职加薪绝缘（开个玩笑）。
我们不仅要fasttext来兜底，我们还需要TextCNN（卷积来学习局部的n-gram特征）、RNN（文本就是序列）、迁移学习（虽然任务不一样，但是有共性，所以可以迁移。一般一个神经网络越浅层的网络越通用。预训练什么的也可以认为是在迁移，最近大红大紫的BERT、GPT...）、主动学习(少样本的时候是一个不错的选择，当年我吹过牛逼，主动学习可以帮助我们自动标注出一些没有标注但是置信度高的数据，这一批数据会包含更多的数据，可以逐渐扩展模型的能力)...
算法说多了容易飘，我们回到实际应用，那么有哪些文本的任务呢？其实前面已经说过了，再重复一下
当年一不小心入了文本分类的坑，刚开始沾沾自喜，觉得还挺好玩，后来分类任务越来越复杂，有点招架不住了。做人要低调 ...
分类任务几个要注意的问题，你的数据不足的时候该怎么办？有几个选择使用简单模型、迁移学习，主动学习，文本数据增强（不过文本的增强没有图片效果好；有通过多语种翻译来获得文本增强的，挺好玩）。模型怎么选择？我们前面介绍了很多方法，最终使用什么模型呢？其实最终综合效果+资源，效果好可能耗资源，我们在实际应用的时候，对误差是有忍耐程度的，不一定要十全十美，千万不要强迫症。有聪明的小伙伴，理解数据能帮助我们更好地选择模型。其他问题还有但不限于类别数据分布不均、炼丹调参指南 ...
文本分类唠叨到此，希望大家不要被误导。
https://blog.csdn.net/u014248127/article/details/80774668
