LDA入门级学习笔记

一.问题描述

传说搜狗公司请了个大牛,把这方面搞得风生水起。最近组内的LDA用得风风火火的,组内同事也是言必称LDA。 不花点时间看看,都快跟人说不上话了。 当然,学习东西慢就只好从简单的开始了,所以把简单的基础的东西在这里讲讲,希望能把基本问题讲清楚,高深的推导就跳过了。

1.1文本建模相关

统计文本建模的目的其实很简单:就是估算一组参数,这组参数使得整个语料库出现的概率最大。这是很简单的极大似然的思想了,就是认为观测到的样本的概率是最大的。 建模的目标也是这样,下面就用数学来表示吧。 一开始来说,先要注意假设了一些隐变量z,也就是topic。每个文档都符合一个topic的分布,另外是每个topic里面的词也是符合一个分布的,这个似然是以文档为单位的。极大似然式子全部写出来是下面的样子的

其中的M表示文档个数。其中的α,就是每个文档符合的那个topic分布的参数,注意这个家伙是一个向量,后面会再描述;其中的β,就是每个topic里面的词符合的那个分布的参数,注意这个也是一个向量。 本来到这里看起来挺简单的,就是一个普通的极大似然估计,估计好参数α和β,就大功告成了。

如果是传统的极大似然估计,好办了,求个梯度,梯度为0的地方就是解了,这里这个东西偏偏多了个隐变量,就是每个词属于哪个topic的?还有每个文档属于哪个topic的?比如,每个文档的topic是怎么分布的(意思就是,每个文档是按概率属于各个topic的,当然,各个topic的词的分布情况是不一样的,比如有金融,电商两种topic,文档有可能是0.3的概率属于金融,0.7的概率属于电商),还有文档里面每个词有来自哪种类型的词的分布的(意思就是,每个词来自哪个topic的,每个topic里面的词分布不一致的,如金融topic里面“人民币”这个词的概率是0.7,“商品”这个词的概率是0.3;电商topic里面“人民币”这个词的概率是0.4,“商品”这个词的概率是0.6)。

这个玩笑就开大了,直接求解就玩不动了,只好用其他算法了。 候选的比较大众的求解有隐变量的算法有EM。 下面先把似然函数用全概率表示出来再做讨论吧。

假设一个文档w_m的topic分布(doc-topic分布)已知,用向量θ_m表示(这个向量的每一项的和为1,总体可以表示一个概率分布),每个词来自哪个topic已知,用z_(m,n)表示,每个topic的词分布用矩阵

中的一行(topic-word分布)表示(这是一个K*V的矩阵,其中V表示语料库中的词的数量,第一行表示第一个topic里面的词分布)。

在已知上面的这些条件的情况下,计算一个文档的整个联合complete-data的联合分布(意思就是所以变量都已知的情况下)的式子如下

(3) 中括号里面的是生成词的过程,大括号里面是生成文档的过程,最右边的那个概率就是∅的后验概率。注意z_m是一个向量,维度为Nm。 这么一堆东西,还是很复杂的,中间有这么多的奇怪的变量,计算起来的复杂读可想而知了,为了跟似然函数联系起来,通过对θ_m(doc-topic分布)和Φ(topic-word分布)积分,以及对z_(m,n)求和,得到只有w_m的边缘分布

(4) 那个累加号被去掉的原因是:在参数θ_m和φ_(z_(m,n) )都已知的情况下,一个词t被产生的概率是

(5) 这下好了,每个文档的似然概率有了,可惜没啥用,实际上这个边缘分布是求不出来的,因为z_(m,n)是隐藏变量,每个词都跟θ_m和Φ都跟z_(m,n)有关,那个连乘又是非常难用积分得到的,这个就是耦合现象。要注意联合分布和边缘分布对z乘积与加和的区别。另外,有些文献上是没有Φ相关的项的,这个看起来各种费劲,以后想清楚后回来解释。

1.1.1 概率公式相关讨论

对于公式(3),要多讨论点,这个是LDA模型的重要的东西,这里说为啥公式是长这个样子的。 先直接抄《LDA数学八卦》的例子,就是文档怎么生成的,直接截图如下

再不懂装懂,搞个概率图模型来看看。

最上面的那个公式代表的就是步骤2——先弄K个topic-word骰子,为了符合贝叶斯学派的口味,这个K个骰子是有先验分布的,先验分布就是一个Dirichlet分布,参数是β,具体在公式(3)中的表现为p(Φ|β)。 步骤3中,“抽取一个doc-topic骰子”,就是图下面的那个第一个水平的箭头,具体在公式(3)中表现为p(θ_m |α)。“投掷这个doc-topic骰子,得到一个topic编号z”这句话说的就是图下方第二个水平的箭头,具体在公式(3)中表现为p(z_(m,n) |θ_m)。步骤3中的第二步“选择K个topic-word骰子中编号为z的那个,投掷这个骰子,得到一个词”这句话说的是图右上角那个垂直的箭头,在公式(3)中具体表现为p(w_(m,n) |φ_(z_(m,n) ))。 就是这个过程,导致了公式(3)长成了现在这个样子,够复杂,而且够棘手,直接去搞公式(4)来计算似然基本没戏的。

1.1.2 似然函数求解

上面小节说过了,计算似然函数是没戏的。 大众候选算法还有EM,其实也不能解这样的问题,因为EM算法依赖条件概率 其中的矩阵Θ,就是doc-topic分布矩阵,是一个M*K的矩阵,只是这也是一个隐变量对应的参数,就是文档的topic的先验分布。 如果非要用EM算法,这里就需要利用另一个分布去拟合这个条件概率,这个就是变分法。变分法的基本思想就是:因为条件概率不好求,但是联合概率是已知的,就可以使用一种类似EM的方法,使用另外的一个概率函数去拟合要求的这个条件概率。具体资料以后再整理。 还好的是LDA没有把参数α和β作为求解的最终目标,目标另有其人。 这个什么极大似然,什么语言模型是个幌子。就像word2vec里面,其实目标是那些词向量,也就是那些参数值。用LDA来解,就更离谱了,连参数α和β这两个参数值都不是目标,而是那些隐变量对应的参数比较重要。 不管用什么方法求解,这个LDA的目的是要做推理。

其实需要求的东西其实是下面的式子

(6) 第一个等号后面的分母p(w_m│α,β)就是上面公式(4)的那个值,参数θ_m(doc-topic分布)和Φ(topic-word分布)不见了是因为这两个量已经用观察到的w_(m,n)和对应的z_(m,n)求积分得到了跟这两个量无关的值,(论文上这个方法叫collapsed Gibbs Sampling,即通过求积分去掉一些未知变量,使Gibbs Sampling的式子更加简单),其实意思就是,参数θ_m和Φ已经使用MCMC的方法估算到了相应的值,估算的时候使用的样本就是训练样本,这里是一个奇怪的地方,有精力回来解释得容易理解点。

就算是这样,哪怕都搞走了这么多参数,分母也不见得好求,一篇文章光求和的项就有K^(N_m )个。 到了这一步,其实大家应该明白了,为啥(6)要表示成那样给大家看看,因为真的只是看看而已,还可以写成其他表现形式,但都不重要了,最后都会给出一个结论的,这个分母没法求,只好用其他办法了。 公式(6)这个条件概率就是要拟合出来的分布。当然,在拟合这个分布过程中,产生了副产品——所有文档的在各个topic上的分布。一旦α和β确定了,每个文档在各个topic上的分布可以直接得到,这个副产品才是求解的目的。 现在问题明确了,贝叶斯推理需要公式(6)的分布,拟合这个分布中产生的副产品是LDA产出的结果,有这结果就能用来做推理。

二.问题求解

2.1 LDA模型求解目标

上面说清楚了,求解LDA就是拟合公式(6)的那个分布,中间要把doc-topic分布矩阵

和topic-word分布矩阵

求出来。 论文总提到的方法是Gibbs Sample方法,下面就开始介绍。

2.1.1 LDA Gibbs Sample方法简介

这里介绍论文中的Gibbs Sample方法怎么拟合的。 这个Gibbs Sample方法也不多介绍,因为具体没弄得特别理解。只知道这个方法的具体步骤:假设观测到的变量是x,隐变量是z(这两个都是向量),通常需要整出来的都是条件概率p(z|x),只是这个条件概率比较难求,只知道了联合概率p(z,x)(必须知道),Gibbs Sample方法的处理方式就是构造下面的条件概率

使用上面的条件抽取z的R个样本z_r,r∈[1,R],当样本数量足够多的时候,条件概率可以用下面的式子近似了

其中的δ函数形式是

也就是,如果u是个0向量,就是1,否则是0. 解决的方案有了,还有个条件需要具备,就是联合概率。

2.1.2求联合概率

联合概率表示如下

这个联合分布是公式(3)利用积分去掉了参数θ_m(doc-topic分布)和Φ(topic-word分布)得到的,可以看到右边的式子,第一个概率跟α,第二个概率跟β无关。这样这两个概率就可以单独处理了。 先看第一个分布p(w|z,β),如果给定了一组topic-word分布Φ,这个概率可以从观测到的词中生成:

其中zi表示语料库中的第i个词的topic,wi表示语料库中的第i个词,W表示语料库中的词数。 意思是,语料库中的W个词是根据主题zi观察到的独立多项分布(我们把每个词看做独立的多项分布产生的结果,忽略顺序因素,所以没有多项分布的系数),就是一个多项式分布。注意φ_(z_i,w_i )是矩阵Φ中的第zi行第i列的元素,顺便提醒一下这个矩阵Φ其实就是LDA要学习的一个东西,是K*V的矩阵,K是topic数,V是词汇数;另一个LDA要学习的东西就是矩阵Θ,也就是doc-topic分布矩阵,是一个M*K的矩阵,矩阵的第一行表示第一个文档的topic分布。 把这个概率拆分到矩阵Φ的每一行和每一列去,得到下面的式子

其中n_(z,t)表示词t在topic z中出现的次数。 那么要求的第一个分布p(w|z,β),就可以通过对Φ的积分来求得

其中

是一个V维向量,表示在topic z中,各个词出现的次数。 从这里看来,整个语料库就可以认为文档是K个独立的多项式分布生成的。 同样的,第二个分布p(z|α)也可以这么计算,给定了如果给定了一组doc-topic分布Θ,这个概率可以从语料库中的每个词的topic来得到

其中di表示第i个词来自哪个文档,n_(m,z)表示文档m中topic z出现的次数。 把这个概率根据矩阵Θ进行积分,就得到第二个分布表示了

其中

是一个K维向量,表示在第m个文档中,各个topic出现的次数。 联合分布就变成了

(7)

2.1.3求完全条件分布

根据上面的公式(7)就能得到Gibbs Sample方法所需要的条件分布

(8) 其中第一个“=”号的分母,是因为根据(1.2.1)中,一个联合概率对zi做了积分得到的结果就是没有这个zi的边缘分布。

表示这个向量没有第i列,t表示第t个词。 1、最后一步那个正比符号出现是因为右下角那一项对所有的zi都一样,无论有一个词分配到了那个topic,

都是一样的,而在Gibbs Sample方法中,同等放大是可以的,所以很多的程序实现都只计算这三项。 2、对于第m篇文档中的第n个词假设刚好就是语料库中的第t类词,它的topic是z,有两个性质可以使用

。另外

。 利用这个式子,抽样就可以进行了。 要注意的是,i是要遍历整个topic空间的,即i从1到K,需要计算K个概率的。 这里的步骤就是不断迭代的,每次迭代都为每个词抽样一个新的topic,然后再根据每个词对应的topic情况估算doc-topic分布Θ和topic-word分布Φ。

2.1.4抽样后更新参数

抽样后怎么更新两个分布矩阵中的元素呢? 来点推导,对于语料库中的第i个词w_i=t,其topic为z_i=k,同时令i=(m,n),意义为该词为第m个文档的第n个词。 回到(1.1.1)中的概率图,

这个概率图分成两个物理过程来看:

,这个过程表示在生成第m 篇文档的时候,先从第一个坛子中抽了一个doc-topic骰子θ_m,然后投掷这个骰子生成了文档中第n个词的topic编号z_(m,n)=k。

,这个过程表示用如下动作生成语料中第m篇文档的第n个词:在上帝手头的K个topic-word 骰子Φ中,挑选编号为z_(m,n)=k的那个骰子φ_k进行投掷,然后生成词w_(m,n)=t。 对于第一个过程来说,α→θ_m→z_m这个过程会生成第m篇文档的所有tipic。《LDA数学八卦》说过,取先验分布为Dirichlet分布,所以前半部分对应于Dirichlet分布

,θ_m→z_m就对应于Multinomial 分布。这样就构成了一个Dirichlet-Multinomial 共轭结构,如下图

利用这个共轭结构,可以得到参数θ_m的后验概率是

,M个文档就有M个这样的共轭结构,其中n_m是一个K维向量,表示第m个文档中各个topic产生的词数。 由于LDA是一个bag-of-words结构,各个词之间都是可以自由交换的。比如说,在第一步中,可以先把所有文档的所有词的topic先全部生成,再把词一个个生成。这样的话,第二步也可以所有相同的topic放在一起,把相应的词生成。这样的话,对于topic k中的所有词来说,这一步就变成了

,这样再看,前半部分

对应于Dirichlet分布

,后半部分

对应于Multinomial 分布,整体构成一个Dirichlet-Multinomial 共轭结构,如下图

利用这个共轭结构,可以得到参数φ_k的后验概率是

,K个topic就有K个这样的共轭结构,其中n_k是一个V维向量,表示第k个topic中的产生的各个词的数量。 具体为啥共轭机构会有这样的效果,具体参看《LDA数学八卦》,里面说得很清楚了。 根据论文《Parameter estimation for text analysis》中θ_(m,k) 和φ_(k,t) 的定义,计算参数矩阵这两个值的更新方式如下

(9)

(10) 这就得到了更新的式子,但是在实际代码中,往往需要在语料库去掉第i个词对应的(z_i,w_i),当然这不会改变分布的共轭结构,在去掉第i个词后,更新的式子变成如下的情况了。

(11)

(12) 公式(11),(12)还可以用来在Gibbs Sample方法中计算完全条件分布(如下

(13) 这种方式就是《LDA数学八卦》选用的方式。 抽样的过程也要注意的,就是要把一个词属于每个topic的概率都计算完了,利用抛绣球的方式抽到了这个词的一个topic(抛绣球的方式就是:假如topic1的概率是0.2,topic2的概率是0.3,topic3的概率是0.5,那么就弄10个桶,1号和2号是topic1的,3到5号是topic2的,6到10号是topic3的,产生一个1到10的随机数(抛的过程),看落到哪个桶就是那个topic)。

2.2 LDA模型整体流程总结

经过上面的讨论,各个环节也算是整理了一遍,当然是选用了其他通用的方法,其实在拟合条件概率p(z│w,α,β)的方法也是有其他的,这里不打算多介绍了。 下面总结一下LDA模型的训练和推理过程,其实上面那么多的东西,要做的工作其实是能完成对一篇文档的topic分布的估算,无论是用判别模型来做,还是生成模型的方法来做,LDA其实就是解决了这么一个问题。而LDA是一个生成模型,要追溯样本当初来源的那个分布,这就导致了各种分布的拟合与假设,这个方面水比较深,有精力后回来再多解释。 对于目前文本建模的目标来说,是分两步的: 就是要根据当前语料库所有的文档,建立模型,模型建立和选最优往往是伴随着参数的获取得到的,就有了各种估计参数的方法;这一步可以称为训练过程。 有了最优的参数,模型也建立了,就需要对新来的文档,根据目前的参数,计算这个文档的topic分布,这一步可以成为预测过程,也就是推理过程。 借用《LDA数学八卦》的东西,这两步可以用下面的话描述: 估计模型中的两个参数:doc-topic分布矩阵Θ={θ_m }_(m=1)^M和topic-word分布矩阵Φ={φ_k }_(k=1)^K。 对于新来的一篇文档Dnew,能够计算这篇文档的topic分布θ_new。

2.2.1 LDA 训练过程

这个自己就不多写了,直接从《LDA数学八卦》截个图吧。

2.2.12LDA 推理过程

训练过程结束后,得到了参数doc-topic分布矩阵Θ={θ_m }_(m=1)^M和topic-word分布矩阵Φ={φ_k }_(k=1)^K。 第一个doc-topic分布矩阵对于推理来说并没有用处,在工程上一般不保存,但是,如果训练过程就是为了对已有文档进行处理,也可以保存下来就进行使用的。 第二个topic-word分布矩阵Φ={φ_k }_(k=1)^K在推理的时候需要用到。来了一个新文档后,根据Gibbs Sampling公式(13)(公式(8)也可以的)为每个词的topic进行抽样,最终稳定后就得到了这篇文档的topic分布θ_new,注意在利用公式(13)计算条件概率的时候,公式中的φ ̂_(k,t)保持不变。 直接从《LDA数学八卦》截个图吧。

到这,LDA模型基本的东西就完了。

三.未整理的符号说明

以上的符号很多,这里提供一个未整理的,只能大致应的,来自腾讯广告的博客“火光摇曳”。有精力后整理一个本文的吧。


(本文出自:www.flickering.cn )

原文发布于微信公众号 - 大数据挖掘DT数据分析(datadw)

原文发表时间:2015-09-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI研习社

Github 项目推荐 | 用 Python 实现的基础机器学习算法

本库包含了用 Python (3.6 版本及以上)实现的基本的机器学习算法,所有的算法都是从头开始写并且没有用到其他的机器学习库。该库旨在让开发者对这些基本的机...

34811
来自专栏机器之心

深度 | 一文介绍3篇无需Proposal的实例分割论文

选自Medium 作者:Bar Vinograd 机器之心编译 参与:Nurhachu Null、黄小天 本文解析了实例分割领域中的三篇论文,它们不同于主流的基...

3525
来自专栏大数据挖掘DT机器学习

机器学习中的数学(6)-强大的矩阵奇异值分解(SVD)及其应用

上一次写了关于PCA与LDA的文章,PCA的实现一般有两种,一种是用特征值分解去实现的,一种是用奇异值分解去实现的。在上篇文章中便是基于特征值分解的一种解释。 ...

2887
来自专栏AI科技评论

裴健团队KDD新作:革命性的新方法,准确、一致地解释深度神经网络

AI 科技评论按:你有没有想过,深度神经网络是依据什么来准确识别有猫的图片的?随着深度神经网络在金融、医疗及自动驾驶等领域的广泛应用,深度神经网络无法明确解释...

1043
来自专栏fangyangcoder

GAN笔记——理论与实现

GAN这一概念是由Ian Goodfellow于2014年提出,并迅速成为了非常火热的研究话题,GAN的变种更是有上千种,深度学习先驱之一的Yann LeCun...

1152
来自专栏人工智能头条

机器学习笔试题精选

机器学习是一门理论性和实战性都比较强的技术学科。在应聘机器学习相关工作岗位时,我们常常会遇到各种各样的机器学习问题和知识点。为了帮助大家对这些知识点进行梳理和理...

673
来自专栏AI科技大本营的专栏

机器学习笔试题精选

机器学习是一门理论性和实战性都比较强的技术学科。在应聘机器学习相关工作岗位时,我们常常会遇到各种各样的机器学习问题和知识点。为了帮助大家对这些知识点进行梳理和理...

733
来自专栏大数据挖掘DT机器学习

强大的矩阵奇异值分解(SVD)及其应用

PCA的实现一般有两种,一种是用特征值分解去实现的,一种是用奇异值分解去实现的。在上篇文章中便是基于特征值分解的一种解释。 特征值和奇异值在大部分人的印象中,...

2997
来自专栏用户2442861的专栏

斯坦福cs224d 语言模型,RNN,LSTM与GRU

翻译:@胡杨(superhy199148@hotmail.com) && @胥可(feitongxiaoke@gmail.com)  校对调整:寒小阳 &&...

441
来自专栏算法channel

1个例子解释 隐马尔科夫模型(HMM) 的 5 个基本要素

隐马尔可夫模型(Hidden Markov Model,HMM)是一个寻找事物在一段时间里的变化模式的统计学方法,它用来描述一个含有隐含未知参数的马尔可夫过程。...

1292

扫码关注云+社区