Browse Month

February 2013

Dirichlet process (一)

这是最早定义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上必须要有拓扑,也就是要能定义“开集”。尽管这个测度P被称为random measure(因为它是一个过程,是建立在分布函数上的分布),但是除了support是A这一点外,P和一般的prior并没有太大的区别。回到我们之前说的normal model,在那个例子里A的元素是所有的正态分布N(\mu,\sigma^2),在\mu,\sigma上加的任何prior也可以被看成是random measure — 只不过一般的random measure的测度都定义在离散点集上,比如经典的Poisson random measure。而在Normal model里的概率可以认为是定义在单点上。离散点集之间的关系比二维欧式空间里的点之间的关系要复杂很多 (比如距离就很难定义),这也就是为什么random measure要复杂的多。所以对于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