NLP（4）Language Model and Smoothing
目录
compute the probability of a sentence or sequence of words.
Language Model：Bigram（come from first order Markov Assumption）
1、Add-one Smoothing <==> Laplace Smoothing
Noisy Channel Model
p(text|source) = [ p(source|text)*p(text) ] / p(source)，p(source)当作常数
p(text|source) ∝ p(source|text)*p(text)，其中p(text)由语言模型决定。
p(中文|英文) ∝ p(英文|中文)*p(中文)
p(正确拼写|错误写法) ∝ p(错误写法|正确拼写)*p(正确拼写)
==============================================================================
Language Model：
compute the probability of a sentence or sequence of words.
p(s) = p(w1,w2,w3,w4......wn)
p(A,B) = p(A|B)*p(B) = p(B|A)*p(A)
A，B独立时，p(A,B) = p(A)p(B)
Chain Rule
p(A,B,C,D) = p(A)p(B|A)p(C|AB)p(D|ABC)
p(w1,w2,w3,w4......wn) = p(w1)p(w2|w1)p(w3|w1w2)p(w4|w1w2w3)......p(wn|w1w2w3......wn-1)
Markov Assumption
p(w1,w2,w3,w4......wn)
first order Markov Assumption：p(w1)p(w2|w1)p(w3|w2)p(w4|w3)......p(wn|wn-1)
second order Markov Assumption：p(w1)p(w2|w1)p(w3|w1w2)p(w4|w2w3)......p(wn|wn-2 wn-1)
......
for example：using 1st Order
==============================================================================
Language Model：Unigram
每个单词都是独立的，不存在依赖关系
Language Model：Bigram（come from first order Markov Assumption）
Language Model：N-gram
作用：Estimating Probability
p(w1,w2,w3,w4......wn) = p(w1)p(w2|w1)p(w3|w1w2)p(w4|w1w2w3)......p(wn|w1w2w3......wn-1)
第n个词出现与前n-1个词相关。N-Gram也是隐马尔科夫中的假设。
整个句子出现的概率 = 各个词出现的概率乘积。各个词出现的概率由语料统计计算得出。
N-gram存在问题：
训练语料毕竟是有限的，这样导致很多事件，如trigram中，w1 w2 w3根本没有出现过。根据最大似然估计，这些事件的概率为零。然而这些事件的真实概率并不一定为零。这个问题被成为数据稀疏问题。
-- MLE给训练样本中未观察到的事件赋以0概率。
-- 若某n-gram在训练语料中没有出现,则该n-gram的概率必定是0。
-- 解决的办法是扩大训练语料的规模。但是无论怎样扩大训练语料，都不可能保证所有的词在训练语料中均出现。
-- 由于训练样本不足而导致所估计的分布不可靠的问题，称为数据稀疏问题。
-- 在NLP领域中，数据稀疏问题永远存在，不太可能有一个足够大的训练语料，因为语言中的大部分词都属于低频词。
解决方法：
--减值法
修改训练样本中的事件的实际计数，是样本中不同时间的概率之和小于1，剩余的概率量分配给未见概率。
--调整方法：最大似然规则
（1）他可保证模型中任何概率均不为0；
（2）数据平滑使模型参数概率分布趋向于更加均匀。低概率（包括0概率）被调高，高概率被调低。
--数据平滑技术（下面讲）
==============================================================================
Evaluation of Language Model
perplexity，尤其是无监督学习下对语言模型进行评估
perplexity = 2^-(x)，x:average log likelihood(可能性)
==============================================================================
Smoothing
- Add-one Smoothing <==> Laplace Smoothing
- Add-k Smoothing
- Interpolation(插入,篡改,添写)
- Good-Turning Smoothing
1、Add-one Smoothing <==> Laplace Smoothing
- c(wi-1，wi)：出现 wi 后出现(wi-1)的次数
- c(wi)：出现 wi 的次数
- V：总共出现的词数
分子加1，分母加V，有效的解决了 c(wi-1，wi)=0 时的情况
2、Add-k Smoothing
k = 1时，即Add-one Smoothing
如何选择k？
- 不断尝试，k = 1,2,3,........
- 设置一个目标函数f(k)，即最优化问题，min perplexsity ==> k' = arg min f(k)
3、Interpolation
要预测Trigram，同时使用unigram, bigram, Trigram
4、Good-Turning Smoothing
Q1：1/18
Q2：3/18
Q3：小于1/18
Good-Turing基本思想是:用观察计数较高的N元语法数重新估计概率量的大小，并把它指派给那些具有零计数或者较低计数的N元语法。
涉及的符号含义为:
- c：出现的频数
- Nc：出现c次的单词的个数
- pGT：good-turning 平滑计数
Sam I am I am Sam I do not eat
N3 = I
N2 = Sam, am,
N1 = do, not, eat
下面是一个实际的词频统计的例子：
第一列是单词出现次数，第二列是出现r次的单词的数量，第三列是期望概率
其中，第三列的期望概率就是通过上述结论计算出来的，例如：
P(1) = (1+1)*263611/1132844 = 0.46539
P(2) = (2+1)*123615/263611 = 1.40679
最后讲一下这个方法论的缺点：
从上图中也可以看出，当单词出现次数慢慢增大时，r值并不是连续性的，但是每一个P®的计算都依赖于r+1的count值。
简单的解决方案是，我们可以通过线性回归之类的方法，平滑的推断出7、9等不存在的r值的对应的count值，然后再带入上式进行计算。
5、Katz改进
基本思想：利用高频率n-gram的频率调整低频的n-gram的频率。
假设N 是样本数据的大小， nr是在N元模型的训练集中正好出现r 次的事件的数目（在这里，事件为N元对 ），即nr表示出现了r次的N元对有多少个
具体操作：
Good-Turing估计适合单词量大并具有大量的观察数据的情况下使用，在观察数据不足的情况下，本身出现次数就是不可靠的，利用它来估计出现次数就更不可靠了。缺乏利用低元模型对高元模型进行线性插值的思想。