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

时间:2022-08-17 15:16:11

多项分布

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) =

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

换一种表达方式,做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) =

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

多项式分布:

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

可以按照上面的规律,猜想式子为:

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

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

全排列有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)。

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

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

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)

图模型:

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

2. Mixture of unigrams (LDA 4.2)

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

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

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

至此,产生过程完成。上概率图模型:

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

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

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

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

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

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

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

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

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

五、几何学解释

来看下面这个图:

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

这个图的意思是这样的,外面大三角形的三个顶点代表三个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