求解 LDABincheng Li2014 年 2 月 19 日目录1EM 算法12用吉布斯采样求解 LDA21EM 算法LDA 原论文使用 Variational Inference 进行参数估计。VariationalInference 的基本思想是使用琴生不等式（Jensens inequality）找到似然函数 L(x|) 的一类下界。令 Qi为概率分布，满足zQi(z) = 1, Qi(z) 0。其中 z 为决定 x 的隐藏变量。则似然函数为 ilogp(x(i);) =ilogz(i)p(x(i),z(i);)=ilogz(i)Qi(z(i)p(x(i),z(i);)Qi(z(i)geqiz(i)Qi(z(i)logp(x(i),z(i);Qi(z(i)(1)然后使用 EM 算法，求解参数。算法如下：Repeat until convergenceE-step:Qi(z(i) := p(z(i)|x(i);)12用吉布斯采样求解 LDA2M-setp: := argmaxiz(i)Qi(z(i)logp(x(i),z(i);Qi(z(i)在 E 阶段中，x、 给定，只用将 Qi(z(i) 设置为 z 的后验分布即可。而在 M 阶段中，相对 优化现在的下限。这个过程跟 k-means 迭代更新centroid 和样本 label 的过程类似。同 k-means 一样，EM 算法也容易陷入局部最优解。具体使用 Variational Inference 求解 LDA 模型的方法比较复杂，有兴趣可以去看原论文。2用吉布斯采样求解 LDA下面使用 Gibbs Sampling 的方法求解 LDA 模型。这里关于 LDA 以及 Gibbs Sampling 的内容都是参考或引用自 LDA 数学八卦一个讲解LDA 模型极好的系列！与 pLSA 不同，LDA 并不假设每一个 document 有一个确定的 topic比列，也不假设每一个 topic 下 word 的比例是确定的。相反，LDA 为这两者都加上了先验分布相当于最大似然估计到贝叶斯估计的转变。令topic k 下 word 的分布为 k，document d 中 topic 的分布为 d。由于 k和 d所确定的似然函数都服从 Multinomial 分布，因此自然地采用Dirichlet 分布作为他们的先验分布。注意整个 LDA 模型只对 k进行一次抽样，而 d在生成每一篇文档时都进行一次抽样。可以将资料库生成的过程分成两个步骤：1. 给文章的每一个待填入的词生成其所属的 topic。2. 按给定的 topic，生成每一个 word。生成 topic这个过程包含 M 个 Dirichlet 和 Multinomial 共轭，M 为文章数，表示成： m zm。其中， m对应 Dirichlet 分布，sample 一篇文档的 topic 分布。 m zm对应 Multinomial 分布，其产生的结果可以表示成 nm= (n(1)m, ,n(K) m), 其中 n(k) m表示文档 m 中第 topic k 产生的词的个数。根据 Multinomial 和 Dirichlet 共轭，我们得到2用吉布斯采样求解 LDA3 m的后验分布为Dir( m| nm+ )于是生成整个语料库的 topic 的概率为 1p( z | ) =Mm=1p( zm| )=Mm=1( nm+ ) ( )生成 word这个过程包含 K 个 Dirichlet 和 Multinomial 共轭，表示成： k w(k)。其中， w(K)表示语料库中，属于 topic k 的 word 计数。这里LDA-math-LDA 文本建模 中使用了一个 trick：由于生成 word 的过程是相互独立的，所以可以交换生成 word 的顺序，使属于同一 topic 的word 放在一起，就有 K 个 Dirichlet 和 Multinomial 共轭了。很优美！令 nk记录属于 topic k 的 word 数。于是我们有后验分布Dir( k| nk+ )记 w 为语料库中的词， z 为词对应的 topic。我们要求语料库中各个word 的 topic，即 p( z | w)。可以使用 Gibbs Sampling 对其采样。采得的样本可用于进行参数估计，进而估计新样本的 topic 分布。具体地，记语料库中文档 m 的第 n 个词的索引为 i，i 为 i 在语料库中的补集，则 GibbsSampling 所用的转移（采样）概率公式为 (这么长的公式，偷懒就全部引参考文献4自原文了）p(zi= k| zi, w) p(zi= k,wi= t| zi, wi)= p(zi= k,wi= t, m, k| zi, wi)d md k= p(zi= k, m| zi, wi) p(wi= t, k| zi, wi)d md k= p(zi= k| m)p( m| zi, wi) p(wi= t| k)p( k| zi, wi)d md k= p(zi= k| m)Dir( m| nm,i+ )d m p(wi= t| k)Dir( k| nk,i+ )d k= mkDir( m| nm,i+ )d m ktDir( k| nk,i+ )d k= E(mk) E(kt)=mk kt注意到，这里只涉及两个 Multinomial 和 Dirichlet 共轭过程。其中，根据Dirichlet 分布的性质，我们有参数估计 1mk=n(k)m,i+ kKk=1(n(k) m,i+ k) kt=n(t)k,i+ tVt=1(n(t) k,i+ t)根据训练阶段采集得的样本（topic-word 矩阵）就可以进行参数 和 的估计了。当要估计新样本的 topic 分布时，只要稍微改动下 sampling 公式即可带入我们训练出来的 。最后才测试文档上采样出来的 topic-word矩阵就反应了文章的 topic 分布。参考文献1 数 学 八 卦.http:/vdisk.weibo.com/s/q0sGh/1360334108?utm_source=weibolife.2 The em algorithm. http:/cs229.stanford.edu/materials.html.参考文献53 Mixture of gaussians. http:/cs229.stanford.edu/materials.html.