n-gram文法中数据稀疏问题解决方案之一：Good-Turing平滑

关键字全网搜索最新排名

【机器学习算法】：排名第一

【机器学习】：排名第二

【Python】：排名第三

【算法】：排名第四

统计语言模型中，N元语法模型不可避免的一个问题，就是数据稀疏，其原因是大规模语料统计与有限语料的矛盾。根据Zipf法则，我们能够推测知零概率问题不可避免。数据稀疏问题的解决办法就是进行平滑处理。平滑处理的算法有很多，例如：加1法、加法平滑方法、Good-Turing估计法、Katz平滑方法、Jelinek-Mercer平滑方法、Witten-Bell平滑方法等，其中Good-Turing估计法是很多平滑技术的核心，于1953年有古德（I.J.Good）引用图灵（Turing）的方法而提出来的，取名古德-图灵估计法。基本思想是：用观察计数较高的N元语法数重新估计概率量的大小，并把它指派给那些具有零计数或者较低计数的N元语法。

c*是Good-Turing平滑计数，c是某个N元语法出现的频数，Nc是出现次数为c的N-gram词组的个数，是频数的频数，如下所示

举个例子

该例子来源于新浪微博Xwzhong的微博，链接：

http://blog.sina.com.cn/s/blog_8267db980102wqgc.html

数据如下所示：

训练集合：

T={s, what, is, it, what, is, small, ?}, |T|=8

验证集合：

V={what, is, it, small, ?, s, flying, birds, are, a, bird, .}, |V|=12

不实用任何平滑技术来计算各单词的概率

在训练集合上，我们得到：

p(s) = p(it) = p(small) = p(?) = 0.125, p(what) = p(is) = 0.25，其他为0

如果不经过平滑处理，则验证集上两句子的概率分别为：

p(what is it?) =（0.25*2）*（0.125*2）≈ 0.001 p(it is flying.) = 0.125 * 0.25 *（0*2）= 0

现在用古德-图灵算法进行平滑处理，如下：

a. 计算在训练集中的词有多少个在测试集出现过c次，依次为

N(0)=6, N(1)=4, N(2)=2, N(i)=0 ,i>2。

b. 重新估计各平滑后的值c*。

对于发生0次的事件：

c*(.)=c*(flying)=c*(birds)=c*(are)=c*(bird)=c*(a)=(0+1)*N(0+1)/N(0)=1*4/6≈0.667 对于发生1次的事件：

c*(it)=c*(s)=c*(small)=c*(?)=(1+1)*N(1+1)/N(1)=2*2/4=1

对于发生2次的事件：

c*(what)=c*(is)=(2+1)*N(2+1)/N(2)=3*0/2=0，保持原值c*(what)=c*(is)=N(2)=2

c. 归一化的概率：

p`(it)=p`(s)=p`(small)=p`(?)=1/12 ≈0.083 p`(what)=p`(is)= 2/12 ≈0.167 p`(.)=p`(flying)=p`(birds)=p`(are)=p`(bird)=p`(a) = 0.667/12≈0.056

因此

p`(what is it?) = 0.167 * 0.167 * 0.083 * 0.083 ≈ 0.00001921

p`(it is flying.) = 0.083 * 0.167 * 0.056 * 0.056 ≈ 0.0000434681

参考资料：

统计自然语言处理（第二版）宗成庆

http://blog.sina.com.cn/s/blog_8267db980102wqgc.html

http://blog.csdn.net/u010189459/article/details/38236657