LDA-math-认识Beta/Dirichlet分布

http://cos.name/2013/01/lda-math-beta-dirichlet/#more-6953

2. 认识Beta/Dirichlet分布
2.1 魔鬼的游戏—认识Beta 分布

统计学就是猜测上帝的游戏,当然我们不总是有机会猜测上帝，运气不好的时候就得揣度魔鬼的心思。有一天你被魔鬼撒旦抓走了，撒旦说：“你们人类很聪明，而我是很仁慈的，和你玩一个游戏，赢了就可以走，否则把灵魂出卖给我。游戏的规则很简单，我有一个魔盒，上面有一个按钮，你每按一下按钮，就均匀的输出一个[0,1]之间的随机数，我现在按10下，我手上有10个数，你猜第7大的数是什么，偏离不超过0.01就算对。”你应该怎么猜呢？

从数学的角度抽象一下，上面这个游戏其实是在说随机变量X1,X2,⋯,Xn∼iidUniform(0,1)，把这n 个随机变量排序后得到顺序统计量 X(1),X(2)，⋯,X(n), 然后问 X(k) 的分布是什么。

对于不喜欢数学的同学而言，估计每个概率分布都是一个恶魔，那在概率统计学中，均匀分布应该算得上是潘多拉魔盒，几乎所有重要的概率分布都可以从均匀分布Uniform(0,1)中生成出来;尤其是在统计模拟中，所有统计分布的随机样本都是通过均匀分布产生的。

潘多拉魔盒Uniform(0,1)

对于上面的游戏而言 n=10,k=7, 如果我们能求出 X(7) 的分布的概率密度，那么用概率密度的极值点去做猜测就是最好的策略。对于一般的情形，X(k) 的分布是什么呢？那我们尝试计算一下X(k) 落在一个区间 [x,x+Δx] 的概率，也就是求如下概率值

P(x≤X(k)≤x+Δx)=?

把 [0,1] 区间分成三段 [0,x),[x,x+Δx],(x+Δx,1],我们先考虑简单的情形，假设n 个数中只有一个落在了区间 [x,x+Δx]内，则因为这个区间内的数X(k)是第k大的，则[0,x)中应该有 k−1 个数，(x,1] 这个区间中应该有n−k 个数。不失一般性，我们先考虑如下一个符合上述要求的事件E

E={X1∈[x,x+Δx],Xi∈[0,x)(i=2,⋯,k),Xj∈(x+Δx,1](j=k+1,⋯,n)}

事件 E

则有

P(E)=∏i=1nP(Xi)=xk−1(1−x−Δx)n−kΔx=xk−1(1−x)n−kΔx+o(Δx)

o(Δx)表示Δx的高阶无穷小。显然，由于不同的排列组合，即n个数中有一个落在 [x,x+Δx]区间的有n种取法，余下n−1个数中有k−1个落在[0,x)的有(n−1k−1)种组合，所以和事件E等价的事件一共有 n(n−1k−1)个。

继续考虑稍微复杂一点情形，假设n 个数中有两个数落在了区间 [x,x+Δx]，

E′={X1,X2∈[x,x+Δx],Xi∈[0,x)(i=3,⋯,k),Xj∈(x+Δx,1](j=k+1,⋯,n)}

事件E’

则有

P(E′)=xk−2(1−x−Δx)n−k(Δx)2=o(Δx)

从以上分析我们很容易看出，只要落在[x,x+Δx]内的数字超过一个，则对应的事件的概率就是 o(Δx)。于是

P(x≤X(k)≤x+Δx)=n(n−1k−1)P(E)+o(Δx)=n(n−1k−1)xk−1(1−x)n−kΔx+o(Δx)

所以，可以得到X(k)的概率密度函数为

f(x)=limΔx→0P(x≤X(k)≤x+Δx)Δx=n(n−1k−1)xk−1(1−x)n−k=n!(k−1)!(n−k)!xk−1(1−x)n−kx∈[0,1]

利用Gamma 函数，我们可以把 f(x) 表达为

f(x)=Γ(n+1)Γ(k)Γ(n−k+1)xk−1(1−x)n−k

还记得神奇的 Gamma 函数可以把很多数学概念从整数集合延拓到实数集合吧。我们在上式中取α=k,β=n−k+1, 于是我们得到

f(x)=Γ(α+β)Γ(α)Γ(β)xα−1(1−x)β−1(1)

这个就是一般意义上的 Beta 分布！可以证明，在α,β取非负实数的时候，这个概率密度函数也都是良定义的。

好，我们回到魔鬼的游戏，这n=10,k=7这个具体的实例中，我们按照如下密度分布的峰值去猜测才是最有把握的。

f(x)=10!(6)!(3)!x6(1−x)3x∈[0,1]

然而即便如此，我们能做到一次猜中的概率也不高，很不幸，你第一次没有猜中，魔鬼微笑着说：“我再仁慈一点，再给你一个机会，你按5下这个机器，你就得到了5个[0,1]之间的随机数，然后我可以告诉你这5个数中的每一个和我的第7大的数相比，谁大谁小，然后你继续猜我手头的第7大的数是多少。”这时候我们应该怎么猜测呢？

2.2 Beta-Binomial 共轭

魔鬼的第二个题目，数学上形式化一下，就是

1. X1,X2,⋯,Xn∼iidUniform(0,1)，对应的顺序统计量是 X(1),X(2)，⋯,X(n), 我们要猜测 p=X(k)；
2. Y1,Y2,⋯,Ym∼iidUniform(0,1), Yi中有m1个比p小，m2个比p大；
3. 问 P(p|Y1,Y2,⋯,Ym) 的分布是什么。

由于p=X(k)在 X1,X2,⋯,Xn中是第k大的，利用Yi的信息，我们容易推理得到 p=X(k) 在X1,X2,⋯,Xn,Y1,Y2,⋯,Ym∼iidUniform(0,1) 这(m+n)个独立随机变量中是第 k+m1大的，于是按照上一个小节的推理，此时p=X(k) 的概率密度函数是 Beta(p|k+m1,n−k+1+m2)。按照贝叶斯推理的逻辑，我们把以上过程整理如下：

1. p=X(k)是我们要猜测的参数，我们推导出 p 的分布为 f(p)=Beta(p|k,n−k+1),称为 p 的先验分布；
2. 数据Yi中有m1个比p小，m2个比p大，Yi相当于是做了m次贝努利实验，所以m1 服从二项分布 B(m,p)；
3. 在给定了来自数据提供的(m1,m2)的知识后，p 的后验分布变为 f(p|m1,m2)=Beta(p|k+m1,n−k+1+m2)

贝努利实验

我们知道贝叶斯参数估计的基本过程是

先验分布 + 数据的知识 = 后验分布

以上贝叶斯分析过程的简单直观的表述就是

Beta(p|k,n−k+1)+Count(m1,m2)=Beta(p|k+m1,n−k+1+m2)

其中 (m1,m2) 对应的是二项分布B(m1+m2,p)的计数。更一般的，对于非负实数α,β，我们有如下关系

Beta(p|α,β)+Count(m1,m2)=Beta(p|α+m1,β+m2)(2)

这个式子实际上描述的就是  Beta-Binomial 共轭，此处共轭的意思就是，数据符合二项分布的时候，参数的先验分布和后验分布都能保持Beta 分布的形式，这种形式不变的好处是，我们能够在先验分布中赋予参数很明确的物理意义，这个物理意义可以延续到后验分布中进行解释，同时从先验变换到后验过程中从数据中补充的知识也容易有物理解释。

而我们从以上过程可以看到，Beta 分布中的参数α,β都可以理解为物理计数，这两个参数经常被称为伪计数(pseudo-count)。基于以上逻辑，我们也可以把Beta(p|α,β)写成下式来理解

Beta(p|1,1)+Count(α−1,β−1)=Beta(p|α,β)(∗∗∗)

其中 Beta(p|1,1) 恰好就是均匀分布Uniform(0,1)。

对于(***) 式，我们其实也可以纯粹从贝叶斯的角度来进行推导和理解。 假设有一个不均匀的硬币抛出正面的概率为p,抛m次后出现正面和反面的次数分别是m1,m2，那么按传统的频率学派观点，p的估计值应该为 p^=m1m。而从贝叶斯学派的观点来看，开始对硬币不均匀性一无所知，所以应该假设p∼Uniform(0,1), 于是有了二项分布的计数(m1,m2)之后，按照贝叶斯公式如下计算p 的后验分布

P(p|m1,m2)=P(p)⋅P(m1,m2|p)P(m1,m2)=1⋅P(m1,m2|p)∫10P(m1,m2|t)dt=(mm1)pm1(1−p)m2∫10(mm1)tm1(1−t)m2dt=pm1(1−p)m2∫10tm1(1−t)m2dt

计算得到的后验分布正好是 Beta(p|m1+1,m2+1)。

百变星君Beta分布

Beta 分布的概率密度我们把它画成图，会发现它是个百变星君，它可以是凹的、凸的、单调上升的、单调下降的；可以是曲线也可以是直线，而均匀分布也是特殊的Beta分布。由于Beta 分布能够拟合如此之多的形状，因此它在统计数据拟合中被广泛使用。

在上一个小节中，我们从二项分布推导Gamma 分布的时候，使用了如下的等式

P(C≤k)=n!k!(n−k−1)!∫1ptk(1−t)n−k−1dt,C∼B(n,p)(3)

现在大家可以看到，左边是二项分布的概率累积，右边实际上是Beta(t|k+1,n−k) 分布的概率积分。这个式子在上一小节中并没有给出证明，下面我们利用和魔鬼的游戏类似的概率物理过程进行证明。

我们可以如下构造二项分布，取随机变量 X1,X2,⋯,Xn∼iidUniform(0,1),一个成功的贝努利实验就是 Xi<p,否则表示失败,于是成功的概率为p。C用于计数成功的次数，于是C∼B(n,p)。

贝努利实验最多成功k次

显然我们有如下式子成立

P(C≤k)=P(X(k+1)>p)

此处X(k+1)是顺序统计量，为第k+1大的数。等式左边表示贝努利实验成功次数最多k次，右边表示第 k+1 大的数必然对应于失败的贝努利实验，从而失败次数最少是n−k次，所以左右两边是等价的。由于X(k+1)∼Beta(t|k+1,n−k), 于是

P(C≤k)=P(X(k+1)>p)=∫1pBeta(t|k+1,n−k)dt=n!k!(n−k−1)!∫1ptk(1−t)n−k−1dt

最后我们再回到魔鬼的游戏，如果你按出的5个随机数字中，魔鬼告诉你有2个小于它手中第7大的数，那么你应该
按照如下概率分布的峰值做猜测是最好的

Beta(x|9,7)=15!(8)!(6)!x8(1−x)6x∈[0,1]

很幸运的，你这次猜中了，魔鬼开始甩赖了：这个游戏对你来说太简单了，我要加大点难度，我们重新来一次，我按魔盒20下生成20个随机数，你同时给我猜第7大和第13大的数是什么，这时候应该如何猜测呢？

2.3 Dirichlet-Multinomial 共轭

对于魔鬼变本加厉的新的游戏规则，数学形式化如下：

1. X1,X2,⋯,Xn∼iidUniform(0,1)，
2. 排序后对应的顺序统计量 X(1),X(2)，⋯,X(n),
3. 问 (X(k1),X(k1+k2))的联合分布是什么；

游戏3

完全类似于第一个游戏的推导过程，我们可以进行如下的概率计算(为了数学公式的简洁对称，我们取x3满足x1+x2+x3=1,但只有x1,x2是变量)

(X(k1),X(k1+k2))的联合分布推导

P(X(k1)∈(x1,x1+Δx),X(k1+k2)∈(x2,x2+Δx))=n(n−1)(n−2k1−1,k2−1)xk1−11xk2−12xn−k1−k23(Δx)2=n!(k1−1)!(k2−1)!(n−k1−k2)!xk1−11xk2−12xn−k1−k23(Δx)2

于是我们得到 (X(k1),X(k1+k2))的联合分布是

f(x1,x2,x3)=n!(k1−1)!(k2−1)!(n−k1−k2)!xk1−11xk2−12xn−k1−k23=Γ(n+1)Γ(k1)Γ(k2)Γ(n−k1−k2+1)xk1−11xk2−12xn−k1−k23

熟悉 Dirichlet的同学一眼就可以看出，上面这个分布其实就是3维形式的 Dirichlet 分布Dir(x1,x2,x3|k1,k2,n−k1−k2+1)。令 α1=k1,α2=k2,α3=n−k1−k2+1,于是分布密度可以写为

f(x1,x2,x3)=Γ(α1+α2+α3)Γ(α1)Γ(α2)Γ(α3)xα1−11xα2−12xα3−13(4)

这个就是一般形式的3维 Dirichlet 分布，即便 α→=(α1,α2,α3) 延拓到非负实数集合，以上概率分布也是良定义的。

从形式上我们也能看出，Dirichlet 分布是Beta 分布在高维度上的推广，他和Beta 分布一样也是一个百变星君，密度函数可以展现出多种形态。

不同 α 下的Dirichlet 分布

类似于魔鬼的游戏2，我们也可以调整一下游戏3，从魔盒中生成m个随机数Y1,Y2,⋯,Ym∼iidUniform(0,1) 并让魔鬼告诉我们Yi和(X(k1),X(k1+k2))相比谁大谁小。于是有如下游戏4

1.  X1,X2,⋯,Xn∼iidUniform(0,1)，排序后对应的顺序统计量 X(1),X(2)，⋯,X(n)
2. 令p1=X(k1),p2=X(k1+k2),p3=1−p1−p2(加上p3是为了数学表达简洁对称),我们要猜测 p→=(p1,p2,p3)；
3. Y1,Y2,⋯,Ym∼iidUniform(0,1), Yi中落到[0,p1),[p1,p2),[p2,1] 三个区间的个数分别为 m1,m2,m3，m=m1+m2+m3；
4.  问后验分布 P(p→|Y1,Y2,⋯,Ym) 的分布是什么。

游戏4

为了方便，我们记

m−→=(m1,m2,m3),k→=(k1,k2,n−k1−k2+1)

由游戏中的信息，我们可以推理得到 p1,p2在X1,X2,⋯,Xn, Y1,Y2,⋯,Ym ∼iidUniform(0,1)这 m+n个数中分别成为了第 k1+m1,k2+m2大的数，于是后验分布 P(p→|Y1,Y2,⋯,Ym) 应该是 Dir(p→|k1+m1,k1+m2,n−k1−k2+1+m3),即Dir(p→|k→+m−→)。按照贝叶斯推理的逻辑，我们同样可以把以上过程整理如下：

1.  我们要猜测参数 p→=(p1,p2,p3)，其先验分布为Dir(p→|k→)；
2.  数据Yi落到[0,p1),[p1,p2),[p2,1]三个区间的个数分别为 m1,m2,m3，所以m−→=(m1,m2,m3) 服从多项分布Mult(m−→|p→)
3.  在给定了来自数据提供的知识m−→后，p→ 的后验分布变为 Dir(p→|k→+m−→)

贝叶斯推理过程

以上贝叶斯分析过程的简单直观的表述就是

Dir(p→|k→)+MultCount(m−→)=Dir(p→|k→+m−→)

令 α→=k→,把α→从整数集合延拓到实数集合，更一般的可以证明有如下关系

Dir(p→|α→)+MultCount(m−→)=Dir(p|α→+m−→)(5)

以上式子实际上描述的就是 Dirichlet-Multinomial 共轭，而我们从以上过程可以看到，Dirichlet 分布中的参数α→都可以理解为物理计数。类似于 Beta 分布，我们也可以把 Dir(p→|α→)作如下分解

Dir(p→|1→)+MultCount(m−→−1→)=Dir(p→|α→)

此处1→=(1,1,⋯,1)。自然，上式我们也可以类似地用纯粹贝叶斯的观点进行推导和解释。

以上的游戏我们还可以往更高的维度上继续推，譬如猜测 X(1),X(2)，⋯,X(n)中的4、5、…等更多个数，于是就得到更高纬度的 Dirichlet 分布和 Dirichlet-Multinomial 共轭。一般形式的 Dirichlet 分布定义如下

Dir(p→|α→)=Γ(∑Kk=1αk)∏Kk=1Γ(αk)∏k=1Kpαk−1k(6)

对于给定的 p→和 N,多项分布定义为

Mult(n→|p→,N)=(Nn→)∏k=1Kpnkk(7)

而 Mult(n→|p→,N) 和 Dir(p→|α→)这两个分布是共轭关系。

Beta-Binomail 共轭和 Dirichlet-Multinomail 共轭都可以用纯粹数学的方式进行证明，我们在这两个小节中通过一个游戏来解释这两个共轭关系，主要是想说明这个共轭关系是可以对应到很具体的概率物理过程的。

2.4 Beta/Dirichlet 分布的一个性质

如果 p∼Beta(t|α,β), 则

E(p)=∫10t∗Beta(t|α,β)dt=∫10t∗Γ(α+β)Γ(α)Γ(β)tα−1(1−t)β−1dt=Γ(α+β)Γ(α)Γ(β)∫10tα(1−t)β−1dt

上式右边的积分对应到概率分布 Beta(t|α+1,β)，对于这个分布，我们有

∫10Γ(α+β+1)Γ(α+1)Γ(β)tα(1−t)β−1dt=1

把上式带入E(p)的计算式，得到

E(p)=Γ(α+β)Γ(α)Γ(β)⋅Γ(α+1)Γ(β)Γ(α+β+1)=Γ(α+β)Γ(α+β+1)Γ(α+1)Γ(α)=αα+β(8)

这说明，对于Beta 分布的随机变量，其均值可以用αα+β来估计。Dirichlet 分布也有类似的结论，如果p→∼Dir(t→|α→)，同样可以证明

E(p→)=(α1∑Ki=1αi,α2∑Ki=1αi,⋯,αK∑Ki=1αi)(9)

以上两个结论很重要，因为我们在后面的 LDA 数学推导中需要使用这个结论。