ngram是一种在自然语言处理中经常使用的技术，通常来说，我会把它作为一些初步处理和数据分析的方法，也会用来做一些快速模型，其具有可解释性强，实现简单等优点。
原先的理解比较土鳖，最近刚好重新读《统计自然语言处理基础》和《统计自然语言处理》，补充下这块的知识。

背景及主要问题

香农游戏和语言模型问题

香农游戏，即在给定前N个词的情况下，需要尽可能准确预测下一个词。这是语言模型一个比较形象的描述，通常我们所指的语言模型，说白了就是计算某语言片段在上下文的概率。可以认为分别针对两类典型的实际问题：
* 给定前文，给出下一个词的概率分布，也即需要计算
$P(w_n|w_0, ..., w_n-1)$
* 给定一篇完整的文章，计算其在某语言生成模型下的似然概率，也即需要计算
$P(w_0, ..., w_n)$

ngram方法

对于上述问题，ngram是一种经典的解决方法，其通过估计$P(w_i|w_{i-1}, ..., w_{i-n})$来作为概率分布。
显然，由于组合爆炸问题，n的范围不能太大，一般来说实际使用中n介于2-3。

而对于ngram模型，最大的问题在于数据稀疏导致的分布估计不准。可以想见，在测试集上统计的大量长尾频率为0和1的ngram组合，往往是随机不精确的。这部分如何处理，通常认为是平滑问题（如何使得分布更加平滑）。

评测方式

对于语言模型（或者ngram模型）的评测方法，可以使用测试集上的似然估计来衡量。通俗来说，就是当一个机器阅读完训练语料后应该能比较高效地把测试语料压缩。

一种办法就是使用信息熵。信息熵本身是衡量压缩一个事件需要的bit位个数。可以通过计算测试集文本的信息熵，来估算一个模型的好坏（Entropy越小，说明压缩效率越高）

$$Entropy= -\frac{1}{n} \sum_{w_i}log_2 P(w_i)$$

平滑方法

对于ngram，最大的问题是数据稀疏上的处理。书中提到一些经典的处理方法

• Lidstone估计（+1平滑、Addictive Estinmation）
• Good-Turing估计
• Jelinek-Mercer估计、留存估计（hold-out data）
• Knecer-Ney估计及其修正算法

（TODO）

Knecer-Ney估计及其修正算法

• c>0情况：设定参变量D

$$P =\frac {max(c-D, 0)}{N}$$

• c=0情况

$$P=Z \times \frac{c(* w_i)}{c(* *)}$$

其中c=0情况是KN估计的精髓，通过对于平滑更精确的一元估计，给出了更好的效果。其核心思想是，对于一元估计，是根据unique上下文情况进行count，这样能较好地对很强二元关系进行去噪（如San Francisco）。

备注：Z是归一化因子，因为从公式来看，对于c=0情况下的概率和，其实是把c>0中省略的概率补充过来。

$$Z=\frac{D*w_{seem}}{\sum P(w_{unseem})}$$

Toy实现

参考资料