不懂n-gram，怎么学好语言模型？
一、背景
1. 问题
- 一切模型始于问题，我们首先抛出一个问题：如何计算一段文本出现的概率？
这个其实是语言模型要解决的问题，如果它解决了，那么对话系统就可以从生成句子的候选集中选择出现概率最大的进行回答；翻译模型也可以选择最合理的一句话作为翻译结果，一切变得简单直接。
2. 形式化描述
文本序列用S表示，由词条w1, w2 ,..., wT构成。
基于统计的联合概率表示如下：
3. 直观方案
解决这个问题最直观的想法是：把全部文本遍历完，统计该文本出现的频数，计算出现概率。不过这样的回答你自己都会觉得心虚吧~ 首先文本有着数据稀疏的特点，语料中每个文本的频数都很低，很有可能也导致该文本出现的概率为0。如果该文本和语料中某句话只一字之差，忽略了语句的相似度，这样计算出现概率就非常不合理。
看来直观方案并不理想，接下来我们来看n-gram模型是如何解决这个问题的。
二、n-gram模型
1. 介绍
n-gram模型是一种简单有效的统计语言模型，它作为语言模型的基石，很多其他的模型都是从它开始改进演变的。它基于马尔科夫假设，假设第T个词的出现只与前面 n-1 个词相关，与其它任何词都不相关。那么，该文本出现的概率就是各个词出现的后验概率的乘积。这些概率可以通过似然函数，也就是频数直接从语料中统计获得。通常n由于计算量太大，参数受限，常采用1-3之间的值，它们分别称为unigram、bigram和trigram，其他值可以直接称为n-gram，例如：4-gram、5-gram..
另外，n-gram除了以上所说的语言模型，还指的是长度为n的词段，比如这句话 John read a book 可以分解：
- bigram序列：{John, read}, {read, a}, {a, book}
- trigram序列：{John, read, a}, {read, a, book}
2. 解决方案
利用n-gram解决该问题的思路如下：
其中，
例如 bigram利用贝叶斯理论可得如下公式，等式右边可根据词频数统计得到出现概率，到此为止以上问题解决。
举个??：
给定训练语料合计三个文档如下：
D1： John read Moby Dick
D2： Mary read a different book
D3： She read a book by Cher
利用bigram求出句子“John read a book”的概率？
p(John read a book)
= p(John |
= 1/3 * 1 * 2/3 * 1/2 * 1/2 =1/18
注意：开始符号
3. 遇到问题
以上在计算过程中还会存在一个问题，比如当阶数n选择 3 时，三个词同时出现的频数为0很常见，因为这个导致整个文本出现的概率为0。要解决这个问题，需借助以下几种平滑算法，使得频数为0的也能分配到较小的出现概率。（1）拉普拉斯平滑
add-one
add-one是最简单、最直观的一种平滑算法。我们希望没有出现过的n-gram的概率不再是0，那就规定任何一个n-gram在训练语料至少出现一次（注意这里是指任意组成n-gram词段，不分语序）。
默认任意一个n-gram频数都加 1，则wt-1的频数加|V|，V是指wt-1和所有的词可能组成不同n-gram的数量（也就是语料的总词条数量）。由于语料中n-gram频数为0的太多，平滑后，它们占据了整个概率分布中的一个很大的比例。而且，对于未出现在语料中的n-gram，都增加同样的频度值1也不太合适。
add-k
由Add-one衍生出来的另外一种算法就是 Add-k。上面我们认为加1有点多，那么可以选择0-1之间的k值。
（2）内插
把n阶拆解为不同低阶别的n-gram模型线形加权组合后再来使用，权重可以自由指定，也可以通过em算法学习得到。这样n阶频数为0时，我们可以利用低阶的频数来计算。
（3）回溯
与内插有点像，它会尽可能地用最高阶组合计算概率，当高阶组合不存在时，退而求其次找次低阶，直到找到非零组合为止。参考下式，这是一个递归运算。
4. 其他应用
（1）字符串比较相似度
以上介绍的n-gram可以将字符串分解成由 n 个词组成的词段集合，可利用词段集合的交集求得字符串之间的相似度。对于两个句子 S 和 T ，相似度如下：
Similarity = |GN(S)| + |GN(T)| ? 2?|GN(S)∩GN(T)|
其中，GN(S) 和 GN(T) 分别表示字符串 S 和 T 中 n-gram 的集合，n一般取 2或 3。字符串距离越近，它们就越相似，当两个字符串完全相等时，距离为0。
获取长度为n的词段参考代码（环境python2.7），以下列出两种方式：
方式1：
1 # coding:utf-8 2 import json 3 4 tokens = ['小', '狗', '爱', '啃', '骨', '头'] 5 6 def get_ngrams(tokens, n): 7 length = len(tokens) 8 for i in range(length - n + 1): 9 yield tokens[i:i+n] 10 11 ngrams_generator = get_ngrams(tokens, 3) 12 13 for tmp_ngram in ngrams_generator: 14 print(json.dumps(tmp_ngram, ensure_ascii=False))
方式2：
1 def get_ngrams(tokens, n): 2 length = len(tokens) 3 # 生成器 4 slices = (tokens[i:length-n+i+1] for i in range(n)) 5 #print(slices, type(slices)) 6 return zip(*slices) 7 8 ngrams_generator = get_ngrams(tokens, 3) 9 10 for tmp_ngram in ngrams_generator: 11 print(tmp_ngram)
输出：
["小", "狗", "爱"]
["狗", "爱", "啃"]
["爱", "啃", "骨"]
["啃", "骨", "头"]
（2）分词
n-gram用在分词中，可以计算每种切分方式得到的候选句子出现的概率最大，获取分词结果。
一般也用来结合正向最大匹配和反向最大匹配分词方法使用，使用两种匹配方式得到的分词结果，如果相同，则返回。如果不同，则利用n-gram只计算不同的部分，看哪种分词更合理。
（3）搜索提示词
当用搜索引擎输入一个或几个词时，搜索框通常会预测接下来要输入的内容，这其实是以n-gram模型为基础实现的，计算给定输入词的情况下，哪些句子出现的概率最大。三、其他语言模型
n-gram是基于马尔科夫假设，当n=1 时，就会回退为一种最简单的假设：假设每个词和其他词出现相互条件独立。大家是不是想到了朴素贝叶斯算法，它也是利用了这个假设。以下就是n-gram里的unigram，即：
虽然利用似然函数通过频数可计算得出以上等式右边每个词出现的概率，但这种完全忽略了词条之间的语义相似度，严重依赖训练语料，导致计算结果不理想。
我们发现，n-gram这种基于统计的语言模型，会有以下缺点：
（1）数据离散化，忽略词条的语义相似性
（2）因为数据稀疏导致出现概率为0的问题
（3）n不能选择太大，否则计算量太大
基于此，引入了后续的神经网络语言模型。
1. NNLM
NNLM和统计语言模型不同的是，不再是基于频数来计算词条在已知上文的前提下的条件概率，而是通过构造非线性函数 f(wt, wt-1,..., wt-n+1;θ) 利用最大似然求得未知参变量，最后得到该词出现的后验概率。
最大化目标函数：
网络架构只有三层，如图所示：
前n-1个词通过词向量矩阵找到对应向量，相拼接输入到隐层，最后通过softmax获得各词出现的概率。
缺点：
（1）输入固定长度 （2）参数巨多，计算量大2. RNNLM
面临NNLM存在的问题，Mikolov在2010年提出了RNNLM，它实际上是一个时序模型，充分利用语料库中中心词条前面的所有单词为条件进行语言模型建模。同时，RNN的引入后又演进出很多变体，像LSTM、BLSTM、GRU等等，从而在时间序列建模上进行更多更丰富的优化。网络结构如下：
优点：
（1）由于共享模型参数，参数大大减少，提高训练速度
（2）可以接受任意长度输入
（3）n不受局限，利用完整的上文信息
缺点：
（1）每一个时间步需要依赖上一个时间步，计算速度慢
（2）容易发生梯度弥散和梯度爆炸
3. word2vec
和NNLM、RNNLM不同的是，word2vec通过借助中心词的上下文窗口信息，来预测后验概率。提供两个框架CBOW和Skip-gram，CBOW是利用上下文信息来预测中心词，输入的上下文信息并不是拼接而是简单加和作为输入，而Skip-gram利用中心词预测上下文信息。针对NNLM计算量大的缺点提出了新的训练技巧Hierarchical Softmax（将Softmax多分类转换为多个二分类）和Negative Sampling（负采样）。该模型在训练过程中获得很有价值的副产品-词向量，将一个高维稀疏离散向量映射到低维稠密连续向量。
参考：
https://blog.csdn.net/songbinxu/article/details/80209197
https://www.cnblogs.com/iloveai/p/word2vec.html
https://blog.csdn.net/baimafujinji/article/details/51281816
https://blog.csdn.net/baimafujinji/article/details/51297802