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

原文发布于微信公众号 - 机器学习算法与Python学习(guodongwei1991)

原文发表时间:2017-06-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏深度学习自然语言处理

【干货】基于注意力机制的seq2seq网络

seq2seq seq2seq的用途有很多,比如机器翻译,写诗,作曲,看图写文字等等用途很广泛!该模型最早在2014年被Cho和Sutskever先后提出,前者...

49660
来自专栏AI研习社

机器学习可以生成任何线条图片的 ASCII 码绘画

回顾 1960 年代,贝尔实验室的天才们想出了用计算机语言来绘画的方法。这种绘画形式叫做 ASCII 绘画,尽管这种绘画需要使用计算机,但很难让计算机自动生成图...

16420
来自专栏人工智能头条

深度学习和自然语言处理中的Attention和Memory机制

46550
来自专栏大数据文摘

揭秘自编码器,一种捕捉数据最重要特征的神经网络(视频+代码)

18570
来自专栏素质云笔记

NLP+2vec︱认识多种多样的2vec向量化模型

1、word2vec 耳熟能详的NLP向量化模型。 Paper: https://papers.nips.cc/paper/5021-distributed...

70470
来自专栏人工智能LeadAI

机器学习实战 | 数据探索(变量变换、生成)

1.1、什么是变量变换? 在数据建模中,变换是指通过函数替换变量。 例如,通过平方/立方根或对数x替换变量x是一个变换。 换句话说,变换是一个改变变量与其他变量...

43760
来自专栏null的专栏

优化算法——模拟退火算法

模拟退火算法原理 爬山法是一种贪婪的方法,对于一个优化问题,其大致图像(图像地址)如下图所示: ? 其目标是要找到函数的最大值,若初始化时,初始点...

55740
来自专栏AI研习社

神经机器翻译的编码 - 解码架构有了新进展, 具体要怎么配置?

用于循环神经网络的编码 - 解码架构,在标准机器翻译基准上取得了最新的成果,并被用于工业翻译服务的核心。 该模型很简单,但是考虑到训练所需的大量数据,以及调整模...

28140
来自专栏Python小屋

计算Fibonacci数列第n项的第8种方法(数学推导与Python实现)

感谢山东工商学院学院厉玉蓉老师提供的完美数学推导,我在重写和整理时略加修改,比如变量替换时她喜欢用字母z,而我喜欢用x,哈哈。当然,还有另外几个小地方^_^ 本...

34050
来自专栏AI科技评论

ACL论文 | 深度学习大神新作,神经网络的自然语言翻译应用

在 8月7日在德国柏林召开的2016 计算语言学(ACL)大会上,学者Thang Luong、Kyunghyun Cho 和 Christopher D. Ma...

37550

扫码关注云+社区

领取腾讯云代金券