概率估值的光滑(Smoothing)

在经典的贝叶斯算法或者随机过程的算法, 如何概率估值是个很直接的问题。

一般通过频率(Frequency / Counting)来估值的过程中,存在需要光滑(Smoothing)的问题, 这个问题在自然语言处理或者贝叶斯算法中尤为突出。

为什么需要Smoothing?

其实比较简单, 就是在贝叶斯推理里面, 各种概率公式利用乘法来计算同时出现的概率。 但是根据小概率事件,在有限样本中肯定会不出现, 或者出现次数少。 尤其不出现的时候, 根据频率估算的概率值就为零, 这个导致推理中乘法计算后一系列值都为零而相等, 进而变得无法有效比较。 所以早期光滑的目的是防止概率为零。 但是随着交叉验证(Cross Validation)思想的发展,以及缺失值处理(Missing)思想的发展, 新的光滑手段层出不穷。

Smoothing的常见方法?

1. Lapalace (add-one, add-α) [unseen words same probability] 18th century

大神拉普拉斯, 在研究太阳明天升起的概率的时候, 提出的最简单的Smoothing技术。 思路很简单,就是防止概率为零就是给分子偏移1, 同时分母偏移一个较大的值,防止概率整体之和大于1。

但是, 后来又发现1过于生硬, 引入0 <= alpha <= 1近似, 可以学习调整。

但是这个alpha参数如何学习呢?

2. Deleted (held-out) estimation [things-we-saw-once]

开始引入交叉验证早期的Held-out划分的思想, 在概率计算中分层T1和T2部分,然后就进行alpha参数学习和调整了。 但是真正在计算过程中还引入了Zipf Law法制: 任何词出现的频率和它在词频表的排序的倒数成反比。 或者直观上来说, 因为交叉验证可以进行参数调整了, 因此同时希望引入一些先验假设, 来更为准确的估值。

3. Good Turing [things new, assuming leave-one-out] 1953

这个方法是图灵在二次大战中破译德军密码时候的大绝招。 本质上是交叉验证思想从Held-out上升到Leave One Out(LOO)的改进。 对于样本里面没见过, 但是测试里面看到了1次, 假设是LOO的情况发生了, 然后调整概率计算。

4. Back-off (Katz) smoothing [non-linear zero-count] 1987

从Katz方法开始, missing处理的思想就引入Smoothing了。 经典的Missing处理就是替代法(Surrogate), 用均值,中值等替代, 或者差值法(Interploation)。 这里Back-off就是替代法中最简单的一种。思路就是找到自身的一部分出现的概率(整个自己没有出现,但是最核心的部分是出现了的), 然后用这个概率打个折(Discounting) 来替代。

前面的计算全是线性的, 而这种替代是非线性(non-linear)的,因此也开启了非线性光滑的大门。

5. Interpolation (Jelinek-Mercer) smoothing [linear zero-count] 1980

Frederick Jelinek和Robert Mercer是IBM开发翻译系统的两位大神, 这个模型也是IBM翻译模型成功的主要理由之一,因此他们获得了2014年ACL终身成就奖。 差值和替代很大程度的不同在于, 他对整个概率整体做了改写, 而改写成除了它本身, 主要组成部分, 次要组成部分等, 然后加权之和。 这个权重就可以通过交叉验证来调整优化。

6. Witten-Bell [interpolation, diversity of predicted word] 1991

Witten-Bell认为Jelinek-Mercer算法还有改进空间, 不管是计算还是思想。 这是Jelinek-Mercer算法的一种特例, 这个概率的改写嵌套计算, 就是有它本身和它主要组成部分的改写值,这严格的两部分加权之和。 而它主要组成部分的概率再同样进行改写。 这样的一个明显的好处,至少是程序容易实现。 其实还有另外一个好处,就是容易给为出现的东西梯级建模。 没出现的概率, 应该贴近出现1此的概率, 出现1此的概率应该贴近出现2次的概率。 如此递归下去。 这样看上去似乎合理很多 。

7. Absolute discounting [approximating Good-Turing]

人们在广泛应用Good-Turing方法的时候, 发现它有个近似计算的公式, 而且很准。 因此把它定义成绝对折扣,直接应用计算, 简单高效(天下武功, 唯快...)。

8. Kneser-Ney [back-off, diversity of history] 1995

既然差值和替代都出现了,能不能杂交一下呢? 能。

Kneser 和 Ney 就提出一个很好的杂交思想, 是基于Witten-Bell的递归思想改进。 那么如何杂交呢?当然整体框架还是Witten-Bell的递归框架。 但是在计算概率时候, 他们觉得不应该直接用相邻一次的概率进行估算, 应该用多次。 这个类似1阶Markov模型还是多阶Markov模型了的时候, 他们选择了多阶, 并且用类似插值计算的线性思想来计算。

9. Modified Kneser-Ney [interpolated back-off]

其实, Kneser-Ney不算真正意义上的插值杂交啦, 那么有没有真的插值和替代的杂交呢, 有, 就是改进的Kneser-Ney方法。

综上, 我们大体介绍了概率估算的思想和简单实现。

原文发布于微信公众号 - AI2ML人工智能to机器学习(mloptimization)

原文发表时间:2016-11-04

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习算法与Python学习

机器学习正在成为程序员的必备能力

13240
来自专栏大数据文摘

暑期追剧学AI (三) | 10分钟搞定机器学习数学思维:向量和它的朋友们

21150
来自专栏iOSDevLog

十个主题,最全的优秀 TensorFlow 相关资源列表

471110
来自专栏华章科技

不用数学也能讲清贝叶斯理论的马尔可夫链蒙特卡洛方法?这篇文章做到了

感兴趣的参数只是用来抽象我们感兴趣的现象的一些数字。通常我们会使用统计的方法来估计这些参数。例如,如果我们想了解成年人的身高,那么我们需要的参数可能就是以英寸为...

8320
来自专栏钱塘大数据

聚类分析—大数据时代数据挖掘的关键突破口

导读:人类文明已迈入大数据时代,得“数据”者得天下,而数据处理技术是必不可少的,那么说到大数据分析中的应用,最常用的经典算法之一就是聚类法,这是数据挖掘采用的起...

42280
来自专栏专知

【业界】 | 谷歌 NIPS 2017 23篇论文:从注意力到价值预测网络(附论文下载)

【导读】2017年度神经信息处理系统大会(NIPS 2017)将于12 月份在美国长滩举行,本届NIPS共收到 3240 篇论文投稿,录用 678 篇,录用率为...

378100
来自专栏专知

【NAACL2018最佳论文】忘掉Word2vec吧!艾伦人工智能研究院新词向量学习方法,一文了解各大奖项论文

【导读】当地时间6月1日到6月6日,第十六届自然语言处理顶级会议NAACL - HLT(Annual Conference of the North Ameri...

11030
来自专栏大数据文摘

学界丨先睹为快:神经网络顶会ICLR 2018论文接受结果速览

26450
来自专栏专知

基于TensorFlow的机器学习速成课程25讲视频全集(16-18讲)

1.2K20
来自专栏机器之心

学界 | 从感知机到GAN,机器学习简史梳理

选自chatbotnewsdaily 机器之心编译 参与:蒋思源、李亚洲 机器学习是人工智能的一个重要分支,也是如今学界、产业界的热门研究。公司、高校倾倒了许多...

33490

扫码关注云+社区

领取腾讯云代金券