LDA于由 David Blei, Andrew Ng和 Michael I. Jordan提出,因为模型的简单和有效,掀起了主题模型研究的波浪。虽然说LDA模型简单,但是它的数学推导却不是那么平易近人,一般初学者会深陷数学细节推导中不能自拔。于是牛人们看不下去了,纷纷站出来发表了各种教程。国内方面rickjin有著名的《LDA数学八卦》,国外的Gregor Heinrich有著名的《Parameter estimation for text analysis》。其实有了这两篇互补的通俗教程,大家沉住心看个4、5遍,基本就可以明白LDA为什么是简单的了。那么其实也没我什么事了,然而心中总有一种被大牛点播的豁然开朗的快感,实在是不吐不快啊。
什么是主题
因为LDA是一种主题模型,那么首先必须明确知道LDA是怎么看待主题的。对于一篇新闻报道,我们看到里面讲了昨天NBA篮球比赛,那么用大腿想都知道它的主题是关于体育的。为什么我们大腿会那么聪明呢?这时大腿会回答因为里面出现了“科比”、“湖人”等等关键词。那么好了,我们可以定义主题是一种关键词集合,如果另外一篇文章出现这些关键词,我们可以直接判断他属于某种主题。但是,亲爱的读者请你想想,这样定义主题有什么弊端呢?按照这种定义,我们会很容易给出这样的条件:一旦文章出现了一个球星的名字,那么那篇文章的主题就是体育。可能你马上会骂我在瞎说,然后反驳说不一定,文章确实有球星的名字,但是里面全部在讲球星的性丑闻,和篮球没半毛钱关系,此时主题是娱乐还差不多。所以一个词不能硬性地扣一个主题的帽子,如果说一篇文章出现了某个球星的名字,我们只能说有很大概率他属于体育的主题,但也有小概率属于娱乐的主题。于是就会有这种现象:同一个词,在不同的主题背景下,它出现的概率是不同的。并且我们都可以基本确定,一个词不能代表一种主题,那么到底什么才是主题呢?耐不住性子的同学会说,既然一个词代表不了一种主题,那我就把所有词都用来代表一种主题,然后你自己去慢慢意会。没错,这样确实是一种完全的方式,主题本来就蕴含在所有词之中,这样确实是最保险的做法,但是你会发现这样等于什么都没做。老奸巨猾的LDA也是这么想的,但他狡猾之处在于它用非常圆滑手段地将主题用所有词汇表达出来。怎么个圆滑法呢?手段便是概率。LDA认为天下所有文章都是用基本的词汇组合而成,此时假设有词库V={v1,v2,....,vn}V={v1,v2,....,vn},那么如何表达主题kk呢?LDA说通过词汇的概率分布来反映主题!多么狡猾的家伙。我们举个例子来说明LDA的观点。假设有词库
{体育,政治}{体育,政治}LDA说体育这个主题就是:{科比:0.3,篮球:0.3,足球:0.3,奥巴马:0.03,希拉里:0.03,克林顿:0.04}{科比:0.3,篮球:0.3,足球:0.3,奥巴马:0.03,希拉里:0.03,克林顿:0.04}(数字代表某个词的出现概率),而政治这个主题就是:{科比:0.03,篮球:0.03,足球:0.04,奥巴马:0.3,希拉里:0.3,克林顿:0.3}{科比:0.03,篮球:0.03,足球:0.04,奥巴马:0.3,希拉里:0.3,克林顿:0.3}LDA就是这样说明什么是主题的,竟说得我无言以对,细思之下也是非常合理。
文章在讲什么
给你一篇文章读,然后请你简要概括文章在讲什么,你可能会这样回答:80%在讲政治的话题,剩下15%在讲娱乐,其余都是废话。这里大概可以提炼出三种主题:政治,娱乐,废话。也就是说,对于某一篇文章,很有可能里面不止在讲一种主题,而是几种主题混在一起的。读者可能会问,LDA是一种可以从文档中提炼主题模型,那他在建模的时候有没有考虑这种情形啊,他会不会忘记考虑了。那您就大可放心了,深谋远虑的LDA早就注意到这些了。LDA认为,文章和主题之间并不一定是一一对应的,也就是说,文章可以有多个主题,一个主题可以在多篇文章之中。这种说法,相信读者只能点头称是。假设现在有KK个主题,有
《体育快讯》,《娱乐周报》《体育快讯》,《娱乐周报》有三个主题体育,娱乐,废话体育,娱乐,废话那么《体育快讯》是这样的:[废话,体育,体育,体育,体育,....,娱乐,娱乐]《体育快讯》是这样的:[废话,体育,体育,体育,体育,....,娱乐,娱乐]而《娱乐周报》是这样的:[废话,废话,娱乐,娱乐,娱乐,....,娱乐,体育]《娱乐周报》是这样的:[废话,废话,娱乐,娱乐,娱乐,....,娱乐,体育]也就是说,一篇文章在讲什么,通过不同的主题比例就可以概括得出。
文章是如何生成的
在前面两小节中,LDA认为,每个主题会对应一个词汇分布,而每个文档会对应一个主题分布,那么一篇文章是如何被写出来的呢?读者可能会说靠灵感+词汇。LDA脸一沉,感觉完蛋,灵感是什么玩意?LDA苦思冥想,最后没办法,想了个馊主意,它说
灵感=随机灵感=随机这也是没办法中的办法。因此对于某一篇文章的生产过程是这样的:确定主题和词汇的分布确定文章和主题的分布随机确定该文章的词汇个数NN如果当前生成的词汇个数小于
只要确定好两个分布(主题与词汇分布,文章与主题分布),然后随机生成文章各个主题比例,再根据各个主题随机生成词,词与词之间的顺序关系被彻底忽略了,这就是LDA眼中世间所有文章的生成过程!聪明的读者肯定觉得LDA完全就是一个骗子,这样认为文章的生成未免也太过天真了吧。然而事实就是如此,这也是为什么说LDA是一个很简单的模型。幸好我们这是用LDA来做主题分析,而不是用来生成文章,而从上上节的分析我们知道,主题其实就是一种词汇分布,这里并不涉及到词与词的顺序关系,所以LDA这种BOW(bag of words)的模型也是有它的简便和实用之处的。
LDA数学分析
上一小节,我们忽略了一个问题,就是如何确定主题和词汇分布,还有文档与词汇的分布,但是要搞明白这个问题,就避免不了一些数学分析了。再次强烈推荐rickjin的《LDA数学八卦》还有Gregor Heinrich有著名的《Parameter estimation for text analysis》。此处我只做一些关键扼要的理论推导 :-)
多项式分布
回忆一下概率论学的东西,假设一个罐子里有红黄两种球,随机抽取抽到红球的概率是pp,如果有放回重复抽
n!n1!n2!,....,nk!p1n1p2n2....pknkn!n1!n2!,....,nk!p1n1p2n2....pknkLDA出来说话了:主题和词汇的分布就是多项式分布!因为一个主题里面不同词汇出现的概率不同,如果只有1个词汇,那么它就是二项分布,但是词汇不可能只有1个,所以它理所当然就是符合多项式分布。这是挺合理的假设,反正我们现在研究的内容是为词汇按主题给出不同的概率分布,其实也就是给出不同词汇在不同主题下的出现比例,我们并不关系词汇之间的顺序关系,所以多项式分布已经很好地刻画出这种关系了。LDA又说:文章和主题之间的分布也是符合多项式分布!因为一篇文章要确定不同主题的出现概率,和主题要确定每个词汇的出现概率是完全可以类比的!思考一下我们也接受了LDA的说法,接下来我们介绍一些记号:VV代表我们字典的词汇个数
对于第mm篇文章,令
z∼Multi(z|θm→)z∼Multi(z|θm→)
那么对于第kk个主题,令
Dirichlet分布
忘记告诉大家,LDA属于江湖中的贝叶斯学派,在贝叶斯学派眼中,像上面提到的ϕk→ϕk→和θm→θm→都是随机变量,随机变量怎么可以没有先验概率分布呢?这岂不是贻笑大方吗?所以LDA整理了一下衣领,马上提出了他们的先验概率分布:
ϕ⃗∼Dirichlet(α⃗)ϕ→∼Dirichlet(α→)而θ⃗∼Dirichlet(β⃗)θ→∼Dirichlet(β→)为什么LDA要说它的先验分布是Dirichlet分布呢?其中最大的原因是因为多项式分布和Dirichlet分布是一对共轭分布,共轭分布有什么好处呢?好处在于计算后验概率有极大的便利!说到底是LDA看中它计算方便。增加了先验概率分布,那么在确定文章与主题分布还有主题与词汇分布的时候,就由先验概率分布先随机生成确定多项式分布的参数。用一个联合概率分布来描述第mm篇文章生成过程:
对于习惯了使用极大似然法的同学,为了使用极大似然法,我们必须将隐含变量消除,那么对于第mm篇文章其生成的边缘概率为:
以上可以看到,边缘概率分布实在是太复杂了,靠普通极大似然法来求解基本无望。不过这并不能难倒我们聪明的计算机科学家,下面我们来介绍一种近似求解法。
Gibbs 采样算法
采样算法的思想
对于一个概率分布p(x⃗)p(x→),我们想得到它得概率分布,无奈有些概率分布形式实在复杂,我们无法直接求解,那么怎么办呢?假设我们的随机变量为:
x⃗=[x1,x2,x3,...,xi,...,xn]x→=[x1,x2,x3,...,xi,...,xn]
其中xi∈{0,1}xi∈{0,1},假设我们知道p(x⃗)p(x→)的概率分布,那么我们可以通过采样的方式得到每一次的样本值:
x⃗(1)=[0,0,0,0,....0]x⃗(2)=[1,1,0,0,....0]x⃗(3)=[1,0,0,0,....0]x⃗(4)=[1,1,0,0,....0].......x⃗(N)=[1,1,0,0,....0]x→(1)=[0,0,0,0,....0]x→(2)=[1,1,0,0,....0]x→(3)=[1,0,0,0,....0]x→(4)=[1,1,0,0,....0].......x→(N)=[1,1,0,0,....0]
那么我们可以统计每个样本出现的次数,然后除以总的采样次数NN来得到相应概率分布。比如我们观察样本值
这是采样的基本思想,但是这里有令人匪夷所思的地方,首先我们不知道概率分布想得到概率分布我们必须通过采样方法来求得,但是采样方法又依赖于我们知道对应的概率分布才能得到相应的采样值,这是一个“鸡生蛋,蛋生鸡“的矛盾,足以令人百思不得其解,此时神奇的Gibbs采样更加令人充满敬畏。
神奇的Gibbs采样
实际应用中,我们通常是有一堆文章,然后要我们去自动提取主题,或者通过现有的文章训练出LDA模型,然后预测新的文章所属主题分类。也就是我们的兴趣点在于求出ΘΘ和ΦΦ的后验概率分布。虽然LDA的模型思想很简单,但是要精确求出参数的后验概率分布却是不可行的,只能通过近似的方式求解。幸好前人已经发现了很多近似求解方法,其中比较简单的就是Gibbs采样,Gibbs的采样精神很简单,对于一个很复杂的高维概率分布:
p(x⃗)p(x→)
我们想获得p(x⃗)p(x→)的样本,从而确定p(x⃗)p(x→)的参数值,也就是我们无法直接求取概率分布的参数,但是我们可以通过神奇的Gibbs采样,获得需要求解的概率分布的样本值,从而反过来确定概率分布。Gibbs采样很简单,它说如果你能很容易求解(通常都是很容易求解,因为此时的分布是一个一维的条件分布)
p(xi|x¬i→)p(xi|x¬i→)
这样的条件分布,那么想获得联合分布的样本,只需执行如下过程:随机初始化x⃗0={x01,x02,...,x0N}x→0={x10,x20,...,xN0}对于 t=1,2,3,4,….T:
xt1∼p(x1|xt−1¬1→)x1t∼p(x1|x¬1t−1→)xt2∼p(x2|xt−1¬2→)x2t∼p(x2|x¬2t−1→)xt3∼p(x3|xt−1¬3→)x3t∼p(x3|x¬3t−1→)….xtN∼p(xN|xt−1¬N→)xNt∼p(xN|x¬Nt−1→)得到一个样本值x⃗(t)=[xt1,xt2,xt3,....,xtN]x→(t)=[x1t,x2t,x3t,....,xNt]
当采样过程收敛之后,通过以上采样得到的样本就是真实的 p(x⃗)p(x→)样本。为什么可以如此神奇地操作,再次推荐rickjin的《LDA数学八卦》!
Collapsed Gibbs Sampler
对于LDA的Inference问题,有了万能的Gibbs采样算法,问题求解变得简单了。上面我们已经知道LDA模型的文档建模的联合分布:
p(zm→,wm→,θm→,Φ|α⃗,β⃗)p(zm→,wm→,θm→,Φ|α→,β→)
为了采样方便,对于参数θm→θm→,ΦΦ,它们本身就是关联z⃗z→和w⃗w→的,也就是我们如果得到z⃗z→和w⃗w→的采样,参数θm→θm→,ΦΦ自然可以得知。那么可以积分化简,得到最终要采样的模型:
p(z⃗,w⃗|α⃗,β⃗)p(z→,w→|α→,β→)
有了联合分布,Gibbs万能算法就可以套用了,首先它必须先解决一个问题(为了表达方便,超参数α⃗,β⃗α→,β→省略):p(zm,i|zm,¬i,wm→)p(zm,i|zm,¬i,wm→)其中zm→={zm,i=k,zm,¬i}zm→={zm,i=k,zm,¬i},zm,¬izm,¬i代表第mm篇文章里面去除主题
判断新文章的主题分布
由上一小节,我们可以通过大量文章求解出LDA这个模型,那么对于一篇新的文章,如何计算它的主题分布呢?一个方式是将文章加入到原来的训练集合里面{z̃⃗,z⃗;w̃⃗,w⃗}{z~→,z→;w~→,w→},然后得到它的采样条件概率为:
p(zi~=k|z̃⃗¬i,z⃗,w⃗,w̃⃗)∝n(t)k+ñ(t)k,¬i+βt∑Vt=1n(t)k+ñ(t)k,¬i+βtn(k)m̃,¬i+αk∑Kk=1n(k)m̃,¬i+αkp(zi~=k|z~→¬i,z→,w→,w~→)∝nk(t)+n~k,¬i(t)+βt∑t=1Vnk(t)+n~k,¬i(t)+βtnm~,¬i(k)+αk∑k=1Knm~,¬i(k)+αk再重新跑一次Gibbs采样,然后得到它的分布。实际上这种做法确实是最优的,但是太慢了,怎么办呢?因为新来的文章,它的词汇是固定的,我们上节已经求出ϕk,tϕk,t,也就是词汇和主题的分布已经是确定的,我们没必要再浪费计算力了,也就是我们认为对一篇新文章,它已经难以撼动之前成千上万文章的统计结果了,也就是说:n(t)k+ñ(t)k,¬i+βt∑Vt=1n(t)k+ñ(t)k,¬i+βt≈n(t)k+βt∑Vt=1n(t)k+βtnk(t)+n~k,¬i(t)+βt∑t=1Vnk(t)+n~k,¬i(t)+βt≈nk(t)+βt∑t=1Vnk(t)+βt所以我们新的条件采样概率变成了:p(zi~=k|w̃i=t,z̃⃗¬i,z⃗,w⃗,w̃¬i→)∝ϕk,t∗(n(k)m̃,¬i+αk)p(zi~=k|w~i=t,z~→¬i,z→,w→,w~¬i→)∝ϕk,t∗(nm~,¬i(k)+αk)然后我们又可以开动Gibbs采样发动机,得到最终的分布结果:θm̃,k=n(k)m̃+αk∑Kk=1n(k)m̃+αkθm~,k=nm~(k)+αk∑k=1Knm~(k)+αk
LDA的Gibbs采样实现
对于程序员来说,看惯代码,没有代码有点无所适从,有没有简单LDA的实现漂亮代码呢?答案是有的,LingPipe里面的LatentDirichletAllocation这个类,完整地按照Gregor Heinrich有著名的《Parameter estimation for text analysis》介绍的算法实现了,代码非常简单,并且可读性极高,建议抓来一看,必然大有毗益。此处我们贴出Gregor中提供的伪代码,以供查看:
初始化阶段,出乎意料的简单,只要初始化4个统计量,分别是:
文档mm对应主题
遍历每一个文档m∈[1,M]m∈[1,M]
遍历每个词汇n∈[1,Nm]n∈[1,Nm]
从多项式分布Mult(1/K)Mult(1/K)得到一个采样值:zmn=kzmn=knkm=nkm+1nmk=nmk+1nm=nm+1nm=nm+1ntk=ntk+1nkt=nkt+1nk=nk+1nk=nk+1Gibbs采样过程,以下是一个采样周期的执行过程:
遍历每一个文档m∈[1,M]m∈[1,M]
遍历每个词汇n∈[1,Nm]n∈[1,Nm]
对于当前的wm,nwm,n的主题kk对应的词汇
nkm=nkm−1nmk=nmk−1nm=nm−1nm=nm−1ntk=ntk−1nkt=nkt−1nk=nk−1nk=nk−1根据p(zi=k|z¬i,w⃗)p(zi=k|z¬i,w→)获得一个采样值:k̂=zm,nk^=zm,n并执行:
nk̂m=nk̂m+1nmk^=nmk^+1nm=nm+1nm=nm+1ntk̂=ntk̂+1nk^t=nk^t+1nk̂=nk̂+1nk^=nk^+1
难以置信的简单,一般在收敛之前,需要跑一定数量的采样次数让采样程序大致收敛,这个次数一般称为:burnin period。我们希望从采样程序中获得独立的样本,但是显然以上的采样过程明显依赖上一个采样结果,那么我们可以在上一次采样后,先抛弃一定数量的采样结果,再获得一个采样结果,这样可以大致做到样本独立,这样真正采样的时候,总有一定的滞后次数,这样的样本与样本的间隔称为:SampleLag。
LDA为什么能work
如果您反复读了前面反复强调的两篇LDA科普大作,并清楚了解它的实现细节,有一些问题可能会慢慢萦绕在心中,挥之不去——为什么LDA能够work?为什么LDA能产生如下结果:
为什么它的结果会这么神奇,每个主题下面的词分布基本符合我们的直觉。比如computers这个主题下面的词汇分布是“computer,model,information,data,……”。
前面我们提到,LDA模型生成过程很简单,基本上是极其naive的,但是为什么它就能产生这样符合直觉的结果呢?(虽然说从直觉上,判断一篇文章的主题,即使文章词的顺序打乱了,我们还是能大致判断主题的,也就是LDA这种BOW模型有它的合理性,但是这并不能解释它为什么能产生如上结果)
现在我们再回顾一下,对于LDA模型,我们推断的目标是它背后的隐结构,也就是“文档-主题分布”和“主题-词汇分布”,那么我们再来仔细观察它的后验概率分布(原谅我为了表达方便,改变了一些记号):
p(z|w,θ)∝p(w,z,θ|α)=∏mp(θm|α)∏np(zmn|θm)p(wmn|zmn,Φ)p(z|w,θ)∝p(w,z,θ|α)=∏mp(θm|α)∏np(zmn|θm)p(wmn|zmn,Φ)
首先需要明确的是隐变量的后验概率分布是正比于联合概率分布的。在极大似然法中,我们会希望模型越接近实际越好,也就是模型在数据上的概率越大越好。我们先只考虑上面表达式的数据似然项p(wmn|zmn,Φ)p(wmn|zmn,Φ),为了使这一似然项越大越好,我们会希望某个主题下对应的词的概率越大越好,由于主题-词汇分布由ΦΦ决定,理想情况下,我们希望ΦΦ矩阵应该是长下面这个样子:
横向代表主题,总共有KK行,列向代表词汇,总共有
我们希望每个主题的词汇概率质量如上图蓝色方块所示(方块的概率和为1),也就是词汇按照主题个数不重叠地切割,这样可以保证词汇在所属主题下概率值最大,因为每一行概率和为1,我们希望概率密度集中在某些词上面,而不是分散地落在每个词上面(请读者思考一下为什么这样会使最终的概率值增大,这里比较难以用文字表达清楚,可以设想一下,假如每个主题的概率密度均匀分配到每个词上面,那么最终每一项p(wmn|zmn,Φ)p(wmn|zmn,Φ)会很小,这与我们的愿望是违背的)。为了使模型在数据上的概率最大,算法会倾向于将主题词汇分布按照上图的形式拟合,也就是“主题-词汇”分布会倾向于成为一个稀疏的分布。
有了上面的讨论,我们再来想想,每个主题会选哪些词汇作为自己的主题词呢? 也就是主题应该选哪些词来将自己的概率质量散落在他们身上。答案是那些经常出现在一起的词。假设主题A下面有主题词:a1,a2,...,ana1,a2,...,an,为了使概率值变大,那么这些词一定是同时出现在很多个文档里面,并且在多个文档中,这些词大部分都同时出现。可以想想为什么要这样,假设不是这样,比如在文档1种主题A的词汇是a1,a2,a3,a4a1,a2,a3,a4,在文档2中主题A的词汇是a5,a6,a7,a8a5,a6,a7,a8,在文档3中主题A的词汇是a9,a10,a11,a12a9,a10,a11,a12,以此类推,如果主题A的词汇真的是这个样子——文档中同一主题都没有在另一个文档中出现,那么主题A下面的词会很多,但是我们上面分析了,为了使模型概率值大,每个主题下面的词必须越少越好,所以这也是有违背愿望的。因此主题下面的词都会倾向于同时出现在多个文档中,到这里为止,读者应该可以大概明白为什么LDA可以产生那么符合直觉的词汇分布了,因为在我们人类自己的概念中,主题词汇就是这样的东西,他们会经常一起出现,比如“银行”,“存款”这些金融主题词汇会很频繁同时出现在多个场合中,所以我们会将他们归为一个主题,而LDA恰恰能捕获这种特性。
Edwin Chen的博客《Introduction to Latent Dirichlet Allocation》也比较直观地介绍了LDA的直觉特性。至于怎么从理论上来说明为什么具有稀疏性质, Quora上面有一个相对直观的解释,我大概总结一下,由于LDA用Dirichlet作为Prior分布,而作为Prior的Dirichlet在其分布参数α⃗α→取很小的时候(一般αα取K/50K/50, ββ取值0.01),可以使得其采样的多项式参数变得稀疏。LDA有两对稀疏对抗,主题与文档的稀疏性和主题与词汇的稀疏性之间的对抗,而LDA会从数据中学习到一个权衡结果。为什么Dirichlet会有稀疏性质呢?可以参照以这篇:
《Notes on Multinomial sparsity and the Dirichlet concentration parameter α》
这篇note提到的Dirichlet其实可以看成几个Gamma分布变换而来,具体变换证明可以参照Quora另一个解答:Construction of Dirichlet distribution with Gamma distribution。另一个好处是,多了先验分布的模型比pLSA更加健壮,不容易导致overfiting,如果看回上面推导Gibbs Sampling的公式,Dirichlet其实起到一种Smooth的效果。可以再参考Kevin Gimpel写的《Modeling Topics》,对于几种常见基础的主题模型的对比,也可以解除不少困惑。