注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

罗维的博客

{ 关注机器学习、计算广告、自然语言处理、大规模数据处理等 }

 
 
 
 
 

日志

 
 

需要带tears去理解Bayesian吗?  

2011-06-06 00:09:51|  分类: 机器学习 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

需要带tears去理解Bayesian吗?

——读2篇论文后的体会

罗维(Gerald)

201165

       读书之法无他,惟是笃志虚心,反复详玩,为有功耳。 --朱熹

 

       在谷歌里拿"Bayesian"和"tears"作为关键词来搜,看到的结果主要就是以下三篇文章:

       (1) Charniak在1991年写的《Bayesian Networks without Tears》

       (2) AFM Smith和AE Gelfand在1992年写的《Bayesian Statistics Without Tears: A Sampling-Resampling Perspective》

       (3) Kevin Knight在2009年写的《Bayesian Inference with Tears: a tutorial workbook for natural language researchers》

       (说明:Charniak和Kevin Knight是NLP界非常有名望的学者)

       这三篇文章都是三位大侠以独特的视角来诠释Bayesian的内容。

       第一篇论文是针对贝叶斯网络(也就是概率图模型中的有向图),我没有看这篇文章,这里我就不去介绍它了,以后阅读了就添加体会到这篇文章里。在这篇文章里,就着重写下我对第二篇和第三篇后的理解收获。

       我可不想带上tears。

Bayesian Statistics Without Tears

       sampling(抽样),resampling(重抽样)

       文章的出发点是积分在贝叶斯推断中是一个常用的计算操作,但一般来说,积分的计算代价太大。那么本文从一个非常巧妙的角度,也就是sampling-resampling的角度来认识并解决这个问题。好,下面来看下作者有一个什么样的思维过程。

       众所周知,贝叶斯公式是:

                                                                                                                       (1)

       其中,的先验分布,在观测到x后的后验分布,而其实就是,表达的是在参数下观测到x的似然函数。

       分母上的积分是需要在的整个概率空间中求解的,除了在一些简单的分布情形下,分母的计算量都是非常大的。

不过, (1)式可以看作是将一种概率分布转换为另一种概率分布。而这个问题再转换到抽样的角度时,那就是将满足概率分布的抽样样本转换成满足的抽样样本。而抽样样本的转换问题就可以用resampling的方法来解决。

Resampling问题的一般定义是:如何将满足概率分布的抽样样本转换成满足的抽样样本?更一般的,给出一个非负的函数,它能通过归一化得到,那么如何在给定函数和满足分布的抽样样本下,生成满足的抽样样本?

       注意到其实在函数形式上是一样的,只不过相差个比例系数,它就是。(请思考下面的思考题1)

       论文的第三节给出了resampling的两种解决办法,一种是针对不大于M的情形下,用rejection sampling方法来处理。另一种是针对的上限无法得到的情形下,用带权的bootstrapping方法来处理。论文中有针对重抽样的样本满足分布的详细证明,其中用到的数学知识主要就是:

       (1) 概率分布函数(或称为累计分布函数)的导数就是概率密度函数。

       (2) 应用极限的思想,再反过来应用蒙特卡洛抽样算法。

       这里就不再累述有关具体的证明。

       此外,作者还谈到这两种resampling方法应用在从满足一种后验概率的抽样分本到满足另一种后验概率的抽样分布的问题中,还举了一个实际例子来解释其中的效果。感兴趣的话,可以看看4.2节和第5节。

思考题1

       回过头来看,为什么要引入,而且它的归一化恰好要是?为什么不直接算,而要算

       答:这是专门针对分母是积分,其带有归一化性质的而考虑的resampling方法,同时这点考虑恰好是对应于解决贝叶斯公式中的那个分母。既然是带有积分,那么计算将在的整个空间中计算,之前已经陈述过这个计算量一般很大。所以考虑引入,并计算是避免积分计算的明智选择。

Bayesian Inference with Tears

       从内容上看,K.K.的这篇论文其实是与前两篇论文是没有关系的,但也许是为了通俗一点,他就用上tears,并恰好与前两篇文章在名字上的有些共同。K.K.是很谦虚的,他绝对不必要with tears来弄Bayesian Inference。初读他的这篇论文,感觉仅仅是一篇流水账,因为读完了也很难让人把握他的逻辑思维过程。但其实再读一遍并做适当的总结,还是能看出来的,这里介绍下我的理解。

       文章的大概框架是讲K.K.在学术上碰到了两个转折点,先是EM算法,而后是贝叶斯推断,当然后者是这篇文章的重点。针对贝叶斯推断,他依次介绍:Cache model及其模型参数的选择,sampling方法和有关模型的一些修改方案。

       思维的出发点:EM以最大似然概率为优化目标,在一些特定的无监督问题(我想不仅仅是structure learning的一些问题,比如:词性标注、中文分词、树替换文法学习、词语对齐;还应该在其他的问题学习类型中存在)上,EM算法的表现是不行的,因为它倾向于选择大的structure。尽管似然概率确实是最大,但是structure的重用性(reuse)不高。另外,EM算法还有一点不足是模型参数需要占用的存储空间较大。

       解决这些问题的一个办法:考虑引入history,来刻画一个structure的重用性。作者称其为Cache model。

Cache model

       Cache model和EM中的最大似然估计有个共同点,就是它们都是在生成模型的框架下。也就是说它们都有生成故事(generative story)——其实就是一种人工的经验假设,然后可以转为数学表达上的公式。

       在文章的第9到第16节,针对树替换文法(Tree Substitution Grammar, TSG)问题,给出了如下的计算公式:

       P(rule | root(rule) + counts of rules used so far) =

              * (rule | root(rule)) +

              () * count(rule in cache) /

       针对这个公式,就有几点考虑了。基础分布(base distribution)怎么得到?怎么给?

       K.K.不想为开辟任何一点存储空间(因为EM算法的模型参数需要很大存储空间,而K.K.就是不想耗空间),所以在第12节就专门针对设计了一个生成故事,它其实是一个概率计算公式,这样就不用存储任何模型参数的值,因为它们都可以在生成故事的框架下直接算出来。

       可以是一个具体的数值,也可以是一个变化的值,那么如何选?两种方法都行,在第13节给出的方案是设定,也就是说随着历史长度的增加而减少,即在计算的过程中基础分布的权重会越来越低。这时公式可以化简为:

                                                                          (2)

       在第17节中,以汉语分词这个问题来介绍如何使用(2)式。当然这里的生成故事就造一个合适的就好了。但是应用Cache model时碰到一个计算复杂度非常高的实际问题,因为需要列举所有可能的推导(文中用derivation这个词,但其实就是指一种structure),而这个是一个与句子长度相关的计算复杂度为指数级的计算问题。同时Cache model没有像HMM/PCFG那样能用前向后向算法将计算复杂度降为多项式级别,这是因为Cache model在计算时存在长距离的依赖关系。不过还好,可以用Sampling方法来近似求解这个问题。

Sampling方法

       Sampling方法无非就是采样,且要求这采样满足原先的概率分布。采样的一种方法是Gibbs sampling。文章在第18节到26节针对POS问题进行介绍。

       Gibbs sampling的核心步骤就是每次采样就只变动其中一个word所对应的tag,当然这改变是在一个概率分布下变动的,具体的看第26节的算法就应该可以理解。

       当然在这里,当P(new-derivation)的计算是可交换的(exchangablilty,参见第24节)时,计算P(new-derivation)是有增量式的计算方法的(参见第21到第25节),这样计算速度可以加快。

模型参数

       文章的第27和第28两节,才与贝叶斯学派的核心思想扯上关系了,那就是模型参数的值也是随机变量,也是带有概率的。

有关模型的一些修改方案

       这里简要介绍下这些,具体的可以看看文章相应部分的内容。

       第30节介绍了抽样的其他方法;

       第31节论述不同的Cache model的可交换性问题。

       第32节介绍长尾效应(Long tail),就是说希望基础分布能一直影响到后面的结构预测中。

       第33节介绍减1/2法来加速plain EM算法的收敛过程。

The end! Haha, enjoy yourself!



转载请注明出处:http://luowei828.blog.163.com/
  评论这张
 
阅读(2753)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017