[综] Latent Dirichlet Allocation(LDA)主题模型算法

---

多项分布

http://szjc.math168.com/book/ebookdetail.aspx?cateid=1&&sectionid=983

---

二项分布和多项分布

http://blog.csdn.net/shuimu12345678/article/details/30773929

0-1分布：

在一次试验中，要么为0要么为1的分布，叫0-1分布。

二项分布：

做n次伯努利实验，每次实验为1的概率为p,实验为0的概率为1-p;有k次为1，n-k次为0的概率，就是二项分布B(n,p,k)。

二项分布计算：

B（n,p,k) =

换一种表达方式，做n次伯努利实验，每次实验为1的概率是p1, 实验为0的概率是p2,有p1+p2=1；问x1次为实验为1，x2次实验为0,有x1+x2=n,该事件的概率B(x1,x2,p1,p2)是多少?

B(x1,x2,p1,p2) =

多项式分布：

推广一下，考虑如果有三种可能，即伯努利抛硬币试验中，硬币比较厚，有可能立起来，即可能是正面，反面，立起来，其概率分别是p1,p2,p3，那么进行n次试验以后，正面出现x1次，反面x2次，立起来x3次的（保证x1+x2+x3=n)概率是多少？

可以按照上面的规律，猜想式子为：

式子是正确的，这就是多项式的分布的表达式，下面从意义上证明一下式子：

全排列有n！种情况，那么对于每一个正、反、立的序列：

正正反立正反立……立反

都包含这x1!*x2!x3!种全排列的情况，因此可知其成立。

---

持之以恒

The Dirichlet Distribution 狄利克雷分布 (PRML 2.2.1)

http://www.xperseverance.net/blogs/2012/03/510/

Dirichlet分布可以看做是分布之上的分布。如何理解这句话，我们可以先举个例子：假设我们有一个骰子，其有六面，分别为{1,2,3,4,5,6}。现在我们做了10000次投掷的实验，得到的实验结果是六面分别出现了{2000,2000,2000,2000,1000,1000}次，如果用每一面出现的次数与试验总数的比值估计这个面出现的概率，则我们得到六面出现的概率，分别为{0.2,0.2,0.2,0.2,0.1,0.1}。现在，我们还不满足，我们想要做10000次试验，每次试验中我们都投掷骰子10000次。我们想知道，出现这样的情况使得我们认为，骰子六面出现概率为{0.2,0.2,0.2,0.2,0.1,0.1}的概率是多少（说不定下次试验统计得到的概率为{0.1, 0.1, 0.2, 0.2, 0.2, 0.2}这样了）。这样我们就在思考骰子六面出现概率分布这样的分布之上的分布。而这样一个分布就是Dirichlet分布。

首先用上面这一段来点直观印象，然后列一些资料：

维基里面对于狄利克雷分布貌似介绍的挺复杂，不够基础。我找到了一个CMU的PPT：Dirichlet Distribution, Dirichlet Process and Dirichlet Process Mixture，找到一篇华盛顿大学的《Introduction to the Dirichlet Distribution and Related Processes》介绍。

发现CMU那个ppt里面讲到，Beta is the conjugate prior of Binomial，有一种原来如此的感觉。嗯，原来贝塔分布是二项分布的共轭先验分布，那么狄利克雷分布就是多项分布的共轭先验分布。所以要看狄利克雷分布，就要先了解多项分布，然后呢，想要了解狄利克雷之于多元的关系，就要先看贝塔分布和伯努利分布的关系。所以，二项分布、beta分布、以及共轭这三点是理解狄利克雷分布的关键基础知识，这个基础知识记录在这里(PRML2.1整小章介绍了这个)。

下面正式进入狄利克雷分布介绍，首先说一下这个多项分布的参数μ。在伯努利分布里，参数μ就是抛硬币取某一面的概率，因为伯努利分布的状态空间只有{0,1}。但是在多项分布里，因为状态空间有K个取值，因此μ变成了向量μ⃗ =(μ1, …, μk)Tμ→=(μ1, …, μk)T。多项分布的likelihood函数形式是∏k=1Kμmkk∏k=1Kμkmk，因此就像选择伯努利分布的共轭先验贝塔函数时那样，狄利克雷分布的函数形式应该如下：

p(μ|α)∝∏k=1Kμαk−1kp(μ|α)∝∏k=1Kμkαk−1  式2.37

上式中，∑kμk=1∑kμk=1，α⃗ =(α1, …, αk)Tα→=(α1, …, αk)T是狄利克雷分布的参数。最后把2.37归一化成为真正的狄利克雷分布：

Dir(μ|α)=Γ(α0)Γ(α1)…Γ(αk)∏k=1Kμαk−1kDir(μ|α)=Γ(α0)Γ(α1)…Γ(αk)∏k=1Kμkαk−1

其中α0=∑k=1Kαkα0=∑k=1Kαk。这个函数跟贝塔分布有点像（取K=2时就是Beta分布）。跟多项分布也有点像。就像Beta分布那样，狄利克雷分布就是它所对应的后验多项分布的参数μ⃗ μ→的分布，只不过μ是一个向量，下图是当μ⃗ =(μ1,μ2,μ3)μ→=(μ1,μ2,μ3)时，即只有三个值时狄利克雷概率密度函数的例子。其中中间那个图的三角形表示一个平放的Simplex，三角形三个顶点分别表示μ⃗ =(1,0,0)μ→=(1,0,0)，μ⃗ =(0,1,0)μ→=(0,1,0)和μ⃗ =(0,0,1)μ→=(0,0,1)，因此三角形中间部分的任意一个点就是μ⃗ μ→的一个取值，纵轴就是这个μ⃗ μ→的Simplex上的概率密度值(PDF)。

对于参数μ⃗ μ→的估计时，可知 后验=似然*先验 的函数形式如下：

p(μ|D,α)∝(D|μ)p(μ|α)∝∏k=1Kμαk+mk−1kp(μ|D,α)∝(D|μ)p(μ|α)∝∏k=1Kμkαk+mk−1

从这个形式可以看出，后验也是狄利克雷分布。类似于贝塔分布归一化后验的方法，我们把这个后验归一化一下，得到：

p(μ|D,α)=Dir(μ|α+m)=Γ(α0+N)Γ(α1+m1)…Γ(αK+mK)∏k=1Kμαk+mk−

---

VergiL Wang的专栏

Latent dirichlet allocation note

http://blog.csdn.net/wangran51/article/details/7408399

---

Stay hungry, Stay foolish

主题模型-LDA浅析

http://blog.csdn.net/huagong_adu/article/details/7937616

---

ZoeChen的博客

Latent Dirichlet Allocation(LDA)主题模型算法实现及源码解析

http://blog.sina.com.cn/s/blog_8eee7fb60101d06p.html

---

持之以恒

【JMLR’03】Latent Dirichlet Allocation （LDA）- David M.Blei

http://www.xperseverance.net/blogs/2012/03/17/

若公式显示有问题请复制链接到新TAB重新打开

听说国外大牛都认为LDA只是很简单的模型，吾辈一听这话，只能加油了~

另外这个大牛写的LDA导读很不错：http://bbs.byr.cn/#!article/PR_AI/2530?p=1

一、预备知识：

1. 概率密度和二项分布、多项分布，在这里

2. 狄利克雷分布，在这里，主要内容摘自《Pattern Recognition and Machine Learning》第二章

3. 概率图模型，在PRML第九章有很好的介绍

二、变量表示：

1. word：word是最基本的离散概念，在自然语言处理的应用中，就是词。我觉得比较泛化的定义应该是观察数据的最基本的离散单元。word的表示可以是一个V维向量v，V是所有word的个数。这个向量v只有一个值等于1，其他等于0。呵呵，这种数学表示好浪费，我以前做过的项目里一般中文词在200-300w左右，每一个都表示成300w维向量的话就不用活了。哈哈，所以真正应用中word只要一个编号表示就成了。

2. document：一个document就是多个word的合体。假设一篇文档有N个词，这些word是不计顺序的，也就是exchangeable的，LDA论文 3.1有说这个概念。论文中document的个数是M。

3. topic：就是主题啦，比如“钱”的主题可能是“经济”，也可能是“犯罪”~ LDA中主题的表示是隐含的，即只预先确定主题的个数，而不知道具体的主题是什么。论文中表示主题个数的字母是k，表示主题的随机变量是z。

好了，总结一下所有的变量的意思，V是所有单词的个数（固定值），N是单篇文档词的个数（随机变量），M是总的文档的个数（固定值），k是主题的个数（需要预先根据先验知识指定，固定值）。

三、基础模型：

先从两个基础模型说起：

1. Unitgram model (LDA 4.1)

一个文档的概率就是组成它的所有词的概率的乘积，这个一目了然，无需多说：

p(w)=∏n=1Np(wn)p(w)=∏n=1Np(wn)

图模型：

2. Mixture of unigrams (LDA 4.2)

假如我们假设一篇文档是有一个主题的（有且仅有一个主题），可以引入主题变量z，那么就成了mixture of unigrams model。它的图模型如下图：

p(w)=∑zp(z)∏n=1Np(wn|z)p(w)=∑zp(z)∏n=1Np(wn|z)

这个模型的generate过程是，首先选择一个topic z for each docoment，然后根据这个z以及p(w|z)独立同分布产生w。观察这个图，z是在N饼外面的，所以每一个w均来自同一个z，就是说一个文档N个词只有一个topic。这和LDA中z在N饼里面不一样。

四、LDA

接下来正式说LDA的产生过程，对于一个文档w：

1. 选择 N∼Possion(ξ)N∼Possion(ξ)

这一步其实只是选个单词的个数，对整个模型没啥影响

2. 选择一个多项分布参数 θ∼Dir(α)θ∼Dir(α)

这α是狄利克雷分布的参数（k+1维），θ⃗ =(θ1, …, θk)θ→=(θ1, …, θk)是产生主题的多项分布的参数，其中每一个θiθi代表第i个主题被选择的概率。从狄利克雷产生参数θ之后，再用θ去产生z

3. 上两步完成后，开始产生文档中的N个词

(a) 首先选个一个topic z∼Multinomial(θ)z∼Multinomial(θ)

z是从以θ为参数的多项分布中挑选出来的，总共有k个topic，根据θ的概率参数选择其中一个topic作为z

(a) 然后选择一个word from p(wn|zn,β)p(wn|zn,β)

这个参数β也是多项分布，是一个k×Vk×V的矩阵，表示从zi到wj的产生概率即βij=p(wj=1|zi=1)βij=p(wj=1|zi=1)。若已选定zn，则矩阵的第n行就成了用来选择产生w的多项分布，根据这个多项分布产生一个w

至此，产生过程完成。上概率图模型：

整个图的联合概率为(只算单个文档，不算整个corpus的M个文档)：

p(θ,z,w|α,β)=p(θ|α)∏n=1Np(zn|θ)p(wn|zn,β)p(θ,z,w|α,β)=p(θ|α)∏n=1Np(zn|θ)p(wn|zn,β)

把上式对应到图上，可以大致解释成这个样子：

在上面这个新图中，LDA的三个表示层被用三种颜色表示了出来：

1. corpus-level (红色)：α和β是语料级别的参数，也就是说对于每个文档都是一样的，因此在generate过程中只需要sample一次。

2.document-level (橙色)：θ是文档级别的参数，意即每个文档的θ参数是不一样的，也就是说每个文档产生topic z的概率是不同的，所以对于每个文档都要sample一次θ。

3. word-level (绿色)：最后z和w都是文档级别的变量，z由参数θ产生，之后再由z和β共同产生w，一个w对应一个z。

五、几何学解释

来看下面这个图：

这个图的意思是这样的，外面大三角形的三个顶点代表三个word，这三个word组成一个simplex，那么这个simplex中的一个点，代表什么意思呢？它代表的意思就是一个点就是一个产生这三个word的多项分布的概率密度（对于这个图多项分布的它是一个三维向量）。具体点来说，例如红色的点p1，它就在word1上。这个意思就是说，p1是一个多项分布，其参数为(1.0, 0, 0)，也就是它产生word1的概率为1，产生其它两个word的概率为0。再来看蓝色的点p2，它产生word1的概率正比于它到word1对边的距离（注意可不是到word1那个点的距离哈）。因为正三角形内部任意一点到三边的垂线之和等于高，也就是可以视为等于1。那么正好这个性质满足概率之和等于1。所以p2到三边的垂线非别代表p2产生垂线对面那个顶点的概率。因此，p2产生word 1的概率看起来像是0.1， word2的概率像是0.4，word3像是0.5。

了解了上面这层意思之后，我们再来看这个topic simplex。它是包含在word simplex里面的(sub-simplex)，所以topic simplex上的一点同时也是word simplex上的一个点。这样topic simplex上的一个点，就有了两层含义，一层含义是它是一个产生word的多项分布概率密度，另一层含义就是它是产生topic的多项分布概率密度。在这个图上，还可以发现topic的点相对于word simplex是已经固定的，其实这topic simplex 上的三个顶点到word simplex上的三个顶点对边垂直线总共9个距离，也就是9个概率值，正好是一个3×33×3的矩阵，这个矩阵就是LDA中的β参数。

知道了这些之后，我们就可以来看mixture of unigrams在图上应该怎么表示了。还记得mixture of unigrams是要先选择一个文档的topic z的，然后根据这个topic产生word。所以它在这个图上的产生过程就是，先随机挑选topic simplx(注意是topic simplex)三个顶点中的一个，然后根据这个顶点到word simplex顶点对边线的距离，也就是这个顶点在word simplex上的多项分布产生每一个word。

再来看pLSI，图中间每一个带叉的圈圈就是一个pLSI中的文档，每一个文档(在pLSI中文档被视为观察变量，即每个文档都被视为word那样是有编号的)都有一个独立的产生topic的多项分布，文档点的位置就表示了它产生三个topic的概率值。

对于LDA，汗，不是很理解，LDA places a smooth distribution on the topic simplex denoted by the contour lines。只好先放着了。

2012@3@28，关于上面这个LDA的图形为啥是曲线的问题，我专门请教了北大赵鑫大牛，他的回答很给力而且一针见血。要理解LDA为啥是曲线，要先从pLSI为啥是点说起。因为pLSI中，由文档w产生topic z的概率是一个参数，对于每个单独文档这个参数要被估计一次，参数可不是随机变量，而是固定的值。因此pLSI中每个文档在图中表示为一个确定的点。而LDA呢，文档w产生topic z的概率在论文里后面inference部分已经给出了，它是p(z|w)=p(θ,z|w,α,β)=p(θ,z,w|α,β)p(w|α,β)p(z|w)=p(θ,z|w,α,β)=p(θ,z,w|α,β)p(w|α,β)，也就是隐含变量z的后验分布，它是一个概率分布，这也是整个LDA inference部分最需要估计的东东。因此图中用曲线来表示LDA，也就是说LDA places a smooth distribution on the topic simplex …

2012@4@18 今天看到《Parameter estimation for text analysis》(PETA)里的内容，可以更深入地解释“LDA places a smooth distribution on the topic simplex denoted by the contour lines”这句话。首先给出PETA里面的原话：LDA with a uniform prior Dir(1) is a full Bayesian estimator for the same model for which PLSA provides an ML or MAP estimator。这句话说明了pLSA是用的是最大似然推断或最大后验推断，在最大后验推断中，p(z|w)是一个给定的置信值（这一点PETA中也有说明：最大后验推断中的置信值不等同于概率），这个置信值是一个常量。LDA用的是贝叶斯推断，所以LDA中的p(z|w)是一个概率分布。

---

lda, a Latent Dirichlet Allocation package.

http://chasen.org/~daiti-m/dist/lda/

---

FreedomShe

基于SIFT+Kmeans+LDA的图片分类器的实现

http://www.cnblogs.com/freedomshe/archive/2012/04/24/2468747.html

---