搬家

因为发现wordpress.com开始在页面投广告了。。。于是决定自己买个域名来host自己的blog。新的地址是这个:

samuelwxy.com

这个blog将不再更新。

PS: 在新blog上Dirichlet process的第二篇时隔两年后已经更新啦!(=____=)

Advertisements

冬季阅读计划

好像这个site已经被荒废很久了…之前准备用来做bayes nonparametric的阅读笔记站点结果未能如愿 (其实是太懒…QAQ)。这次希望利用空闲时间读一些经典的理论书籍,然后重新启用了这个站点 (铛铛档档),希望这次能坚持做笔记下去…

寒假打算读几(4 ~ 5)本书 (听到这个数量就很危险…真的能坚持下来嘛…),看多少是多少吧。主要是两个方面的书,一个是关于Learning theory和empirical processes的,包括

Vapnik的《The nature of statistical learning》

Talagrand的《The generic chaining》

Van der vaart的《Weak convergence and empirical processes》

Kearns的《Computational complexity of machine learning》。

(大概不太可能全读吧…已经隐隐感觉到要失败了…)  另一方面是关于Monte Carlo算法的书,准备读

Robert和Casella的《Monte Carlo statistical methods》

顺便也看看Jun Liu的书…以前读书真是太少了,希望恶补还来得及吧。希望这次能好好坚持下去,争取能够一周更新一次。

Bayes statistics近况简介

近来实在太忙,没有机会接着写Ferguson的那篇paper的介绍,只好暂且贴一些其他的文章蒙混一下。刚刚看到有童鞋在问Bayes statistics的情况,以及和生统的比较,觉得可以简单介绍一下,以帮助大家更好的在各种不同的方向之间选择。

关于Bayes统计和传统统计的基本区别在之前的帖子里已经大概提到了。这里主要想比较一下这两种方法近来的发展上的区别,以及将来的趋势。很多同学都觉得业界不用Bayes,我觉得这个观点在渐渐过时,现在业界已经在逐渐接受而且更加欢迎Bayes的方法。这主要是近来bayes和machine learning方面紧密联系,以及Bayes方法本身的特点决定的。这我们在后面会讲。传统统计的方法把所有问题转化成一个最优化问题,而Bayes把所有问题转化成一个sampling问题,这点不同就直接导致了两种方法的研究侧重点不同。如果一个问题被划归为最优化问题,你面临的最大困难是如果刻画估计的uncertainty,所以frequentist的重点就是研究各种asymptotic的性质,然后用normal distribution去近似。但如果一个问题被转化为sampling问题,那么最大的困难就是如何实现这个sampling,所以Bayesian研究的很大重点就在于如何有效的从后验分布里抽样。但是这两个问题又是可以互相转化的。对于frequentist而言,如果不想使用传统的Wald’s interval之类的方法去刻画uncertainty,那么可以bootstrap代替。而对于Bayesian而言,如果嫌sampling太慢的话,也可以用Laplacian approximation之类的来代替。所以在实际使用上,两种方法之间没有明确的界限,哪种方便就用哪种。实际上很多时候bayes会比传统方法方便很多,举例来说,如果同样得到了对一个参数\theta的估计,而我们实际还关心另一个参数g(\theta),那么如何得到g(\theta)的uncertainty呢?如果用Bayes的方法,你只要对每个抽样得到的\theta点做个g的变换,就可以得到g(\theta)的后验分布了。但是如果是frequentist,你可能需要delta method去近似,而且结果还可能很糟糕。到头来可能还是只能用bootstrap这种类似于bayes的sampling方法。当然Bayes困扰使用者的最大问题就是prior的选择问题,如果确实有先验信息,那么这是一个优势。但是如果没有,大家可能会担心糟糕的prior很可能会导致不好的估计结果。不过实际上选择一些noninformative的prior的话可以完全避开这个问题。其次利用empirical Bayes的方法(虽然这是所有Bayesian鄙视的方法,而且有重复利用数据的危险),也可以轻易获得一个里估计结果很近的prior。

业界里偏向于frequentist是历史的原因。Bayes要算到1992才真正开始发展。一方面虽然MCMC很早就被提出来,但是由于计算机技术上的落后,这个方法很难被有效使用。另一方面Gibbs sampler是Alan他们在1992年第一次使用到bayes估计当中的。Gibbs sampler作为一种特殊的MCMC,是非常高效及快速的。于是Bayes方法从那年之后开始进入了一个全新的发展阶段。现在来回答之前提出来的问题,为什么bayes会越来越受欢迎呢?这主要源自于Bayes在modeling上的优势,以及在计算上的简洁。首先,正因为可以加入prior,Bayes方法可以很轻易的加入一些使用者希望拥有的性质,而且这些性质很多是不能被写进likelihood里面的。比如现在很火的nonparametric baye领域,利用Dirichlet process可以很好的处理infinite mixture model。infinite mixture model可以被用来做clustering。这里使用DP的好处是你可以不用像frequentist或者传统ML那样事先假定有多少个cluster,而是posterior能直接决定cluster的数目,以及cluster的结果。在比如Natural language processing (NLP)里的Latent Dirichlet Allocation (LDA)模型,如果使用者希望topic之间不是简单的独立,而是有相互排斥的性质,那么就可以在prior里加入repulsive process,这些模型可能连likelihood都写不出来,只能通过posterior sampling来做inference. 又比如现在大热的frequentist 的 high dimensional 问题,那些penalized的方法都可以看成是加入了一个prior,比如lasso对应的就是Laplacian distribution。第二,Bayes能很轻松的实现hierarchical modeling,这在frequentist里面被称为random effect model。frequentist里要估计一个一层的hierarchical structure就已经足够复杂了,但是Bayes通过sampling的方法可以轻松的估计所有parameter。而hierarchical modeling本身就是用来model complex problem的,比如某些变量之间有一定的同质性,某些又有一定的排异性,通过hierarchical structure就可以很简单的刻画这些问题,比如在meta analysis上的运用。第三,在计算上,当一个问题的规模很大时,最优化会有很严重的问题。比如要使用newton法的话,储存一个Hessian矩阵占用的空间可能就非常大了,而且计算一个Hessian矩阵需要调用计算likelihood的次数也会很多,结果会占用大量资源,而且收敛也很缓慢。MCMC的话,每次抽样只需要计算Likelihood一次,而且proposal process选的合理的话,不需要储存任何的大型矩阵,在计算资源上会节省很多。不过唯一的问题就是收敛速度慢,所以与之对应现在有了很多其他的抽样方法,比如particle filtering, Hamilton MC 等等。除了sampling以外,Baysian还发展了另外一套近似方法来避开收敛速度慢的问题,比如variation Bayes以及INLA。这写方法主要是利用一些形式简单的函数去近似posterior distribution来避免sampling,可以被看成是Laplacian approximation的发展。

个人感觉machine learning领域已经越来越重视Bayes的方法了,就是因为Bayes方法建模简单,计算方便,比如刚才的LDA模型。而且ML本身也不太care所谓的理论性质渐近性质如何。随着在ML里的广泛使用,Bayes也开始逐渐被业界接受,现在很多大型的IT公司,以及某些金融公司也会专门招聘一些Bayes领域的人。我想说一个学校侧重点是Bayes的话,不代表以后就一定去做Bayes了,往往两个领域里的东西你都能学到。另外Bayes里很多东西需要经验,而frequentist里的东西很多从书中就可以掌握。所以如果以后并不打算从事理论研究,不需要大量证明训练的话,去一个Bayes的系掌握两种不同的统计方法也未尝不是一个好的选择。

最后总结一下近来Bayes的发展作为结束。现在最热的领域当然是nonparametric bayes,包括Dirichlet process有关的一大堆特殊的prior的性质,以及对应的sampling方法。关于这个我可能会写一系列的介绍性文章(主要是读完paper后的理解)。第二就是Bayes处理high dimensional problem的方法,同样也是通过一些神奇的Prior比如Horse shore来实现,而且这些方法的好处是同时可以获得variable selection的uncertainty,这对于frequentist的方法来说是很难的。第三是单纯的sampling或者posterior approximation 算法上的发展,像之前已经提到的SMC, HMC, VB&EP,有很多方法效果很好,但是理论上都还没有被证明有效,所以还有很多研究的空间。第四是manifold&shape learning有关的东西,以及和information theory领域的结合。利用nonparametric bayes本身的优势可以很好的处理manifold learning的问题,这些方法最后很有可能被用在图象处理及相关领域。最后就是Big data的问题,当然这也是frequentist 关心的问题,也是目前工业界都关心的问题。hierarchical modeling可以是一种ad-hoc的解决方法,不过并不永远work。GPU computing有可能成为解决的手段之一,不过也不好说。Big data是现在研究重点所在。Potential的应用不可估量。

本文谢绝转载。

Dirichlet process (Ferguson, 1973)(一)

这是最早定义Dirichlet process的文章,发表在1973年的Annals of Statistics上。在当时计算机还没有普及的年代,Bayes的方法基本局限在conjugate的框架之下,这也是Ferguson大神在文章开头就指出的定义Prior需要考虑的条件之一:posterior要足够好算(要有close form)。结果即使在如今计算机十分普及的情况下,人们反而更关注计算速度,于是conjugate的prior使用仍最为广泛。因此当时的Ferguson的考虑结果到如今依然有意义。

Ferguson在文章的开头就指出了,non-parametric Bayes最大的问题就在于没有合适的prior。本质上来说统计的所有估计问题,都是在估计随机变量X的分布函数。在参数模型里我们会假设一个具体的分布,比如

X\sim N(u,\sigma^2)

而正态分布可以被均值和方差唯一决定,于是我们所要做的就是估计\mu, \sigma这两个参数。但是使用参数模型的风险是我们选的模型可能不对,比容把正态模型用到非正态上。非参数模型里不会具体假设一个参数模型,这样就避免了选错模型的问题,但是却带来了更多的问题。在参数模型里,以正态模型为例,假设所有正态分布构成的集合是A,我们默认待估计的分布函数是在A中的,我们只要找出A中那一个最好就可以了(从数据来判断哪个最好)。而正态分布可以用两个参数唯一确定。这样我们就把A中的每个元素和二维欧式空间的点一一对应了起来

N(\mu,\sigma^2)\leftrightarrow (\mu,\sigma)

—–就这个意义来说集合A其实不是很大,应该说很小,比一个二维欧式空间还小。但是在非参数模型里,我们不再默认待估计的分布函数是局限在正态里,现在集合A的元素是任何分布函数—取值在0,1之间的单调右连续函数(更准确地说是说在给定概率空间上的所有测度函数,或者是所有随机变量)。现在集合A有多大呢?至少欧式空间是放不下A的。那么集合A太大带来的问题是什么呢?

为了说明这个问题我们引入一些泛函(functional)的观点。我们把likelihood看成是定义在集合A上的一个函数,因为给定集合A中的任何一个元素(分布函数),我们都可以写出对应的likelihood,并算出相应的值。所以likelihood是把A中元素映到R上的一个映射。由于在这种情况下自变量是函数,而非传统的数值,因此这种函数被称为泛函。对于frequentist来说,他们所用的估计方法是maximum likelihood,即找到A中的一个元素,它刚好最大化likelihood,这个元素就是MLE。但是现在集合A不能被嵌入欧式空间当中,这就意味着原来定义的导数,极限的概念都不能用了,从而给这个最优化问题带来了困难。对于最优化而言,集合A最大的问题是没有“距离”的概念(更多的时候还需要“内积”的概念),所以第一步是要在A上引入距离和内积。但是即使有了距离,欧式空间上原来简洁的导数法则也不再适用了,所以我们还是要尽量把A往欧式空间上靠。幸运的是,如果距离和内积选的比较好,那么我们的集合A就具有了“可分”(separable)的性质。“可分”的意思就是说,我们可以在集合A里面找到一个非常小(可数无穷多个元素)的集合A’,使得其在A中稠密(dense,对于A中的任何一点都可以找到A’中的任何一点,使其任意接近)。如此A’的基(basis)也就成了A的基,从而所有A中的元素都可以唯一表示成集合A’的基的线性和的形式。因为A’只有可数无穷多个,这组基也只可能是可数无穷多。这样来看的话,虽然A不能嵌入欧式空间中,但是A比欧式空间也大不了多少,相当于是无穷维的欧式空间罢了,而且还是线性空间。因此欧式空间中的结果都可以自然推广到A上了。

这样讲比较抽象,我们举一个具体的例子。现在假设我们现在想估计变量X的分布函数,简化版的Weierstrass Theorem告诉我们任何连续密度函数都可以用不同参数的Gaussian density的加权和去无限逼近(scale mixture of Gaussian)。这个定理证明很简单,可以参看http://www.math.sc.edu/~schep/weierstrass.pdf,把最上面等式的积分离散化我们就得到了,

f(x) = \lim_{h\rightarrow 0} \sum_{k=-\infty}^\infty \frac{1}{\sqrt{2\pi}h}e^{-\frac{(x-kh)^2}{2h^2}}\cdot hf(kh)

这里我们的A’就是一小部分Gaussian分布(N(kh,h), k\in\mathcal{Z},可数多个),其中hf(kh), k\in\mathcal{Z}就是需要估计的权重,而A就是所有有连续密度函数的分布函数。我们可以看出来它其中的元素都可以被表示成A’中元素的线性和。于是通过选择A’作为基,A中的任何一个元素f都对应于一组坐标(\cdots, hf(-2h), hf(-h), hf(0), hf(h),\cdots)

对于Bayes来说,情况就略有不同。因为Bayes不依赖于最优化,所以A上有没有“距离”并不重要。但是Bayes需要一个在集合A上的prior P,也就是集合A上的一个测度(叫测度不叫分布函数是为了和集合A的元素区分开来,不然很容易混淆,虽然测度本身和分布函数没有太大区别)作为我们对于所有可能的X的分布函数的先验知识。而这就要求A上必须要有拓扑,也就是要能定义“开集”。尽管Ferguson把这个测度P叫做random measure以示其和一般分布函数的不同(因为它是建立在分布函数上的分布),但是除了support是A这一点外,P和一般的prior并没有太大的区别。回到我们之前说的normal model,在那个例子里A的元素是所有的正态分布N(\mu,\sigma^2),在\mu,\sigma上加的任何prior其实都是所谓的“random measure”,因为这个prior相当于给集合A里面的任何一个正态分布分配了一个概率,所以也是“分布函数上的分布”。只是现在集合A很小,而且因为可以被嵌入二维欧式空间中,所以可以直接用二维欧式空间上已有的测度来做这个P(比如经典的g-prior)。而对于non-parametric的情况,唯一的问题就在于A太大了,不能被直接嵌入欧式空间中来利用欧式空间上已有的各种测度。因此想要在集合A上建立一个概率空间,并找到对应的\sigma-field就会遇到麻烦—A上没有拓扑,没有定义开集,就更无从谈起Borel集了。而这也就是Ferguson这篇paper的主要目的,如何在这么大的A集合上建立一个足够好的测度空间。足够好就意味着这个测度要能覆盖到整个集合A,其次就是posterior要足够好算,要conjugate。前者要求定义这个测度的时候,要顾及到全部分布函数,后者要求定义的方法必须和有限的情形联系起来,是有限情形的推广(这样才能保证posterior好算)。在下一篇里我就会介绍Ferguson是如何构造这个测度P的。

思考:1.证明非参问题里的集合A无法被嵌入有限维欧式空间中?也即证明对于任意n, 总能找到一个从A到[0,1]^n上一个Lebesgue测度不为0的集合的满射。

2.证明任何连续函数都可以被可列个Gaussian density的加权和逼近(即证明文中的离散化公式,然后对于\forall\epsilon>0, 总存在一个h_0,使得当h<h_0|f(x)-\sum N(x;kh,h)\cdot hf(kh)|<\epsilon, x\in R

注:本文谢绝转载。

Bayes Nonparametric的阅读计划

因为Project的关系,准备系统的阅读一下NB有关的paper。计划是从1973年的Ferguson的那篇Dirichlet process开始,到stick-breaking construction以及infinite mixture model,再到Chinese restaurant process和 Indian buffet process,再到现在的一些新的模型和推广。中间会看一些Radford大神关于DP mixture的经典算法,包括conjugate和non-conjugate的情形。另外,计划应该还会涉及一些topic model和unsupervised learning有关的文章,以及Determinant point process有关的模型。目标有二:改进现在的Factor analysis方法,让结果更容易解释;二是以后听别人讲的时候不让自己显得像笨蛋。