返回信息流[论文导读][教程][介绍]文本处理、图像标注中的一篇重要论文Latent Dirichlet Allocation
原文信息
Latent Dirichlet Allocation
David.M.Blei
Andrew.Y.Ng
Michael.I.Jordan
JMLR2003
（可google到）
原文的主要内容
有两种方法设计分类器：
1. discriminative model，就是由样本直接设计判别函数，例如SVM；
2. generative model，就是先从样本恢复概率模型——例如我们熟悉的参数方法：混合高斯模型GMM;非参数方法Parzen窗。然后再充分挖掘模型，用以分类。例如Bayes最大后验概率准则；或者将模型中的参数当作提取的特征（参数一般都比较少，所以这么做实际上是在降维），在这些新特征上设计分类器（例如又用SVM）。
恢复的模型可生成新的样本，所以得名generative。
原文就是讲了一种建立generative model的方法，用于文本处理。
对文本（document）中各单词（word）的出现频率（简称词频）建立概率模型通常是文本处理的第一步。
开始讨论前，先做如下约定：
- 仅考虑文本的词频，而不考虑单词在文本中出现的先后顺序及其约束关系
- 文本中的单词来自大小为|V|的词汇表。例如： V = {FILM, MUSIC, TAX, MILLION, STUDENT, TEACHER, SCHOOL}. |V| = 7
- 每篇文本有N个单词
- 文本来自k个主题（topic）。例如: T = {Arts, Budgets, Education}. k = 3
一种简单直观的词频概率模型——unigram model（原文Figure 3(a)）这样描述某一文本中单词的“发生方式”：
For each of the N words w_n:
Choose a word w_n ～ p(w);
其中，w是离散随机变量，在词汇表V中取|V|个离散的值。p(w)是w的分布，可由训练样本通过机器学习或其它方法获得。这个模型就是每个单词的词频，没有考虑文本的主题，过于简单。于是我们引出考虑了文本主题的模型——
Mixture of unigram(原文中Figure 3(b)). 它这样描述某一文本中单词的“发生方式”：
Choose a topic z ～ p(z);
For each of the N words w_n:
Choose a word w_n ～ p(w|z);
其中，z是离散随机变量，在主题T中取k个离散值，p(z)是z的分布；w_n是离散随机变量,在词汇表V中取|V|个离散值，p(w|z)是给定z时w的条件分布。z可取k个值，w可取|V|个值，p(w|z)可看作一个k×|V|的矩阵，可由训练样本通过机器学习或其它方法获得。
对照我们在前面的约定中给出的V和T的具体示例，p(w|z)是3×7矩阵。若p(w|z)的第1行表示主题{Education}——可以想象这个主题的文本中{STUDENT, TEACHER, SCHOOL}的词频会高些，其它单词的词频会低些——因此该行的行向量所表示的分布p(w|z)会在{STUDENT, TEACHER, SCHOOL}附近出现峰值；若第2行表示主题{Budgets}，p(w|z)就会在{TAX,MILLION}附近出现峰值...
在“发生”一篇文本前先随机选出p(w|z)的第z行（根据分布p(z)）；再依次随机选出第z行的w_1,w_2,...,w_N列（每次选取都根据分布p(w|z)）,这就“发生”出了文本中的所有单词。
但是这个模型只允许一篇文本有一个主题，这是不够妥当的。一篇关于北邮科研经费的文本，可能{STUDENT, TEACHER, SCHOOL, TAX, MILLION}的词频都很高——这个文本同时具有两个主题{Education,Budgets}。如何模拟一篇文本多个主题的情形呢？在此，我们跳过pLSI模型，直接引入原文探讨的——
Latent Dirichlet Allocation (LDA, 原文中Figure 1). 它这样描述某一文本中单词的“发生方式”：
Choose parameter θ ～ p(θ);
For each of the N words w_n:
Choose a topic z_n ～ p(z|θ);
Choose a word w_n ～ p(w|z);
其中θ是一个1×k的随机行向量，p(θ)是θ的分布，它的具体函数形式就是Dirichlet分布，这一分布保证θ的k个分量θ_1,θ_2,...,θ_k都取连续的非负值，且θ_1 + θ_2 + ... + θ_k = 1；z_n是离散随机变量，在主题T中取k个离散值，p(z|θ)是给定θ时z的条件分布，它的具体函数形式很简单，就是把θ直接拿来作为概率值：p(z = i|θ) = θ_i,也就是说z取第1,2,...k个主题的概率分别是θ_1,θ_2,...,θ_k；w_n是离散随机变量,在词汇表V中取|V|个离散值，p(w|z)是给定z_n时w的条件分布。和前面一样，可以把它看作k×|V|的矩阵。
LDA在“发生”一篇文本前,先随机生成一个1×k的向量θ（根据Dirichlet分布p(θ)）,生成的这个θ非负且归一化，可以看作某个随机变量的分布(也就是说，Dirichlet可以看作是分布的分布...)；然后随机选取p(w|z)的第z_1行（根据分布p(z|θ)）,接着随机选取z_1行的w_1列（根据分布p(w|z = z_1)）,同样的方法依次选出z_2,w_2,...z_N,w_N,这就“发生”出了文本中的所有单词。
剩下的任务就是如何根据训练样本学习出LDA模型的具体形式。模型无非是含有控制参数的表达式，学习出了参数就确定了模型。我们看看LDA有哪些控制参数呢？
- 分布p(θ)的表达式需要一个1×k行向量的参数，记为α
- p(w|z)可看作k×|V|的矩阵，记该矩阵为β
把w看作观察变量，θ和z看作隐藏变量，就可以通过著名的EM算法学习出α和β，但这一过程中后验概率p(θ,z|w)无法计算出解析表达式，因此需要近似解，原文中使用了基于分解（factorization）假设的变分法(Variational Methods)，其实也就是先假设θ和z在给定w时条件独立：p(θ,z|w) ≈ p(θ|w)*p(z|w)，然后进行后续推导（参考本导读“预备知识” - Variational Inference）。这一套方法原文叫做variational EM，推导过程确实有些复杂，但最后总结出的不过是几个可以通过迭代求解的表达式（参见原文5.3节的1.2.两步）。
最后理一下原文的结构
1 Introduction 综述其它方法
2 Notation and terminology 符号约定
3 Latent Dirichlet allocation 详细介绍
4 Relationship with other latent variable models LDA与unigram, mixture of unigram, pLSI的区别。前两个本导读已经提到了，建议读者再仔细比较pLSI和LDA的区别，理解为什么作者说pLSI不是well-defined graphic model
5 Inference and Parameter Estimation Inference部分介绍了variational inference，就是本导读前面提到的如何近似计算隐藏变量的后验概率。Parameter Estimation就是用EM法估计α和β
6 Examples和7 Applications and Empirical Results 给出的具体例子、应用和实验结果
预备知识
如果牢固掌握这些预备知识，理解原文会更容易些。
- p(X|Y)的记法。注意|右边的Y既可以表示随机变量（已经取定了某具体值），也可以表示普通的非随机变量。这样我们可以在最大似然估计和Bayes方法间方便的“切换”，而不会让符号记法影响我们的表述。例如，考虑具有确定但未知参数μ，Σ的高斯分布p(x),可以记为p(x|μ,Σ);若按照Bayes学派观点，可以将μ和Σ也看作随机变量，x的分布就能记为随机变量μ，Σ取定某值后的条件分布p(x|μ,Σ)——统一的记法。
- k取1分布/多项式分布(Multinomial)。考虑取3个离散值的随机变量x ～ p(x)。这个看似很平庸的分布...就是所谓的k取1分布或称多项式分布。一般我们习惯的把它记为p(x_i) = u_i, i = 1,2,3,且u_1 + u_2 + u_3 = 1. 但在有些数学推导中，将它记为指数形式会更方便些.将x看作3维的随机向量，各分量是“互斥”的，即它只能取(1,0,0),(0,1,0),(0,0,1)三组值。于是可将分布重新记为 p(x) = (u_1^x_1)*(u_2^x_2)*(u_3^x_3).注意论文原文中Multinomial就是这儿说的k取1分布，与一些概率教科书中的定义不同。一般的k维情况依次类推。具体参[Bishop]的2.2节.
- 共轭先验分布(Conjugate Prior)。考虑某概率密度函数，要估计其中的参数t。按照Bayes学派的观点，参数t ～ p(t).我们有p(t|X) ∝ p(X|t)p(t),这个式子说：在没有做任何观测时，我们对t的知识用先验分布p(t)表示。当观察到X后，就通过该式将先验概率p(t)更新（计算）为后验概率p(t|X)，使我们对t的知识增加。仔细观察，若p(t)与p(X|t)有相同的函数形式，那么后验概率p(t|X)就与先验概率p(t)有相同的函数形式——这使得t的后验概率与先验概率具有相同的表达式，只是参数被更新了！ 更妙的是，本次后验概率可以作为下次观测时的先验概率，于是当继续进行观测X_2,X_3...时，只是不断的在更新先验概率p(t)的参数,p(t)的函数形式不变。具体参见[Bishop]的2.2节。
这也是Bayes学派饱受批评的地方：先验概率的选取有时只是方便数学推导，而非准确的反映我们的先验知识。
- Dirichlet分布。现在我们可以说，Dirichlet分布就是k取1分布的Conjugate Prior。若k维随机向量θ ～ Drichlet分布，则θ的k个分量θ_1,θ_2,...,θ_k都取连续的非负值，且θ_1 + θ_2 + ... + θ_k = 1。Dirichlet分布的具体表达式参见[Bishop]的2.2节。
- Simplex。考虑2维的例子：以(0,1)与(1,0)为端点的线段就是simplex。考虑3维的例子，以(0,0,1),(0,1,0),(0,0,1)为端点的三角形内部就是simplex。更高维的情况可依次类推。考虑θ ～ Drichlet分布。注意到θ的k个分量θ_1,θ_2,...,θ_k都取连续的非负值，且θ_1 + θ_2 + ... + θ_k = 1，可知Dirichlet分布的定义域是一个simplex.这也就是原文中Figure 2那个三角形的含义（k = 3的示意图，让这个simplex三角形平躺在水平面上）。参见[Bishop]的2.2节
- Graphical Models. 就是用图来表示随机变量中的依赖关系。这个tutorial一google一大把。建议参考[Bishop]的8.1节，了解几个符号（空心圆圈——隐藏(latent)变量,实心圆圈——观察(observed)变量，方框——重复次数）就足够看懂原文中的Figure 1和Figure 3了。最多再看看[Bishop]的8.2节
- EM.关于这个的tutorial很多，但我觉得[Bishop]的9.2节是数学处理最为简洁，最容易看懂的(有个tutorial在关键的几步中用了大量∑和∏，让人抓狂) 。另外[Bishop]的9.4节也值得看，为理解其它内容如variational inference有好处。
- Variational Inference. 就是计算后验概率的近似方法。考虑随机变量{X,Z}，其中X是观察变量，Z = {Z_1,Z_2}是隐藏变量。用EM法或做Bayes推理的关键一步,就是要求后验概率p(Z|X).不巧的是,在一些复杂问题中p(Z|X)没有解析表达式,需要近似求解.相关的方法很多,一种经常使用的是基于可分解(factorization)假设的方法：p(Z|X) ≈ p(Z_1|X)p(Z_2|X)——就是说强行假设Z_1和Z_2条件独立——然后进行后续推导。
这一假设当然会产生误差，考虑二维高斯分布p(Z|X) = p(Z_1,Z_2|X)，Z_1与Z_2不独立，所以p(Z_1,Z_2|X)的等高图是同心椭圆，椭圆可任意倾斜（例如，若Z_1与Z_2的线性相关系数是1，则椭圆倾斜45°）。现简记p(Z_1|X) = q_1(Z_1), p(Z_2|X) = q_2(Z_2)，我们想改变q_1与q_2，用q_1*q_2去拟合p(Z_1,Z_2|X).但无论如何改变q_1与q_2的形式，q_1*q_2的椭圆等高线都是长轴、短轴分别与Z_1轴、Z_2轴平行！不过，合适的q_1与q_2保证q_1*q_2与p(Z|X)的峰值点重合，一般这就足以解决实际问题了。详细讲解可以参见[Bishop]的第10章。也可参考[Winn]的1.8节。
另外，[Winn]提出了通用的计算框架，你不必每次都先用Variational Inference推导出公式，再手工编写代码；你只用在一个GUI里编辑好Graphical Model，再点start...（作为类比，考虑离散的线性系统转移函数H(z)，你可以由此推导出差分方程的表达式，然后用Matlab编程求解；也可以在Simulink中编辑好框图，再点start...）
参考文献
[Bishop] Pattern Recognition And Machine Learning. C.M.Bishop. Springer, 2006（cryppie在本版曾发过电子版）
[Winn] Variational Message Passing and its Applications. John M. Winn. Ph.D. dissertation, 2004(可google到)
网上资源
可google到LDA的Matlab和C实现
http://vibes.sourceforge.net/index.shtml john winn的通用框架,Java实现（里面有文档指导怎样在Matlab中调Java）。
这是一条镜像帖。来源：北邮人论坛 / ml-dm / #2530同步于 2008/7/1
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ML_DM机器人发帖
[导读]文本处理、图像标注中的一篇重要论文Latent Dirichlet Al
hmily821224
2008/7/1镜像同步60 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
版主加精，大牛出现了
【 在 hmily821224 的大作中提到: 】
: 原文信息
: Latent Dirichlet Allocation
: David.M.Blei
: ...................
文章写得很好，条理清晰：unigram model最原始的模型，没有考虑主题信息；然后引入了主题，mixture of unigram，但是只有一个主题；进而引出了可以描述多个主题的LDA。
这个分析思路和研究思路很值得借鉴。
我有一个问题：能否把参数学习的EM描述的清楚一些。因为我是这么考虑的，LDA模型中的两个missing variables有着不同的意义。unigram model只有一个词表，词表长度为|V|。mixture of unigram的意思是说一个主题就有一个对应的词表，长度都是N。对于mixture of unigram模型，em的e计算了p(missing_variable|obser_variable)，直观地说是每个词与某个主题的对应关系。LDA意思说有多个复杂的表，每个表中是一个mixture model，每个mixture model的分量是unigram，这么复杂的一个模型，我直观感觉它的learning非常复杂。概率上，em的e应该计算p(z,θ|w)，直观上，我理解是应该是两步，p(θ|z)和p(z|w)，为什么在给定w的时候z和θ是独立的？感觉说不过去。
我也在考虑这个东西用在bio上面有没有价值。Jordan好像没把它用在bio上面。最近一次竞赛，jordan他们提交的算法的结果很一般。
【 在 hmily821224 的大作中提到: 】
: 原文信息
: Latent Dirichlet Allocation
: David.M.Blei
: ...................
[QUOTE]文章写得很好，条理清晰：unigram model最原始的模型，没有考虑主题信息；然后引入了主题，mixture of unigram，但是只有一个主题；进而引出了可以描述多个主题的LDA。
这个分析思路和研究思路很值得借鉴。
我有一个问题：能否把参数学习的EM描述的清楚一些。因为我是这么考虑的，LDA模型中的两个missing variables有着不同的意义。unigram model只有一个词表，词表长度为|V|。mixture of unigram的意思是说一个主题就有一个对应的词表，长度都是N。对于mixture of unigram模型，em的e计算了p(missing_variable|obser_variable)，直观地说是每个词与某个主题的对应关系。LDA意思说有多个复杂的表，每个表中是一个mixture model，每个mixture model的分量是unigram，[/QUOTE]
呵呵，看你的分析有点看糊涂了。“LDA有多个表，每个表中是一个mixture model”，不太对吧?也许看一下原文中画出的Graphic Model会有帮助吧。
[QUOTE]这么复杂的一个模型，我直观感觉它的learning非常复杂。概率上，em的e应该计算p(z,θ|w)，直观上，我理解是应该是两步，p(θ|z)和p(z|w)，为什么在给定w的时候z和θ是独立的？感觉说不过去。[/QUOTE]
帖子已经改写了，请重新参见 预备知识 - Variational Inference. 独立只是假设,方便推导用的,一般不符合实际情况.
[QUOTE]我也在考虑这个东西用在bio上面有没有价值。Jordan好像没把它用在bio上面。最近一次竞赛，jordan他们提交的算法的结果很一般。 [/QUOTE]
是啥竞赛啊？介绍一下，科普科普?
把w称作词表，z称作主题，θ称作超主题（呵呵，我不知道怎么叫它）
对你给的LDA的模型我理解是这样的3级结构
给定w，根本推不出来z和θ独立，假设独立确实是可以简化计算的推导，但是我觉得假设更是体现了模型的思想。我看了一下blei的paper，他那个图也说明不了z和θ独立。
另外一方面，从EM的算法来说。让我们从最简单的mixture model说起，EM的E是w和z的从属关系的度量，即描述w有多大可能属于z。好，推广到LDA，我觉得LDA的E应该是(1)z有多大可能属于θ（可能你会说θ是参数，呵呵，在gm里面，参数也可以看作变量），p(θ|z)(2)w有多大可能属于z，p(z|w)。按照你给的p(θ|w)和p(z|w)，如果取极端情况即hard assignment，也就有可能出现跟w相关的θ和z，z根本不是属于θ这个超主题的范畴。我想弄清楚的是这个。
另外，计算可以用gibbs。上个月写了个model就是用gibbs，模型可能跟LDA很像，model的图形结构和hmm的图形结构一样，用了message passing来做inference，用了gibbs做learning。paper还没发，不好细说了，呵呵。
PS：这边做报告，喜欢让你推公式，所以还是有必要说清楚。还有，EM如果按照数学公式去做的话，结果一般是错误的。
Master Wugui says:" No accident"
[QUOTE]给定w，根本推不出来z和θ独立，假设独立确实是可以简化计算的推导，但是我觉得假设更是体现了模型的思想。我看了一下blei的paper，他那个图也说明不了z和θ独立。
另外一方面，从EM的算法来说。让我们从最简单的mixture model说起，EM的E是w和z的从属关系的度量，即描述w有多大可能属于z。好，推广到LDA，我觉得LDA的E应该是(1)z有多大可能属于θ（可能你会说θ是参数，呵呵，在gm里面，参数也可以看作变量），p(θ|z)(2)w有多大可能属于z，p(z|w)。按照你给的p(θ|w)和p(z|w)，如果取极端情况即hard assignment，也就有可能出现跟w相关的θ和z，z根本不是属于θ这个超主题的范畴。我想弄清楚的是这个。 [/QUOTE]
原来你质疑的是：假设它们独立是否合理？
托尔斯泰说过“独立的随机变量总是不相关的，不独立的随机变量却有各种相关方式”。暂时忘掉这儿的θ,z,w，忘掉θ和z是如何搅在一起的.看一个更一般的例子，或许有帮助:
考虑二维高斯分布p(Z|X) = p(Z_1,Z_2|X)，Z_1与Z_2不独立，所以p(Z_1,Z_2|X)的等高图是同心椭圆，椭圆可任意倾斜（例如，若Z_1与Z_2的线性相关系数是1，则椭圆倾斜45°）。现简记p(Z_1|X) = q_1(Z_1), p(Z_2|X) = q_2(Z_2)，我们想改变q_1与q_2，用q_1*q_2去拟合p(Z_1,Z_2|X).但无论如何改变q_1与q_2的形式，q_1*q_2的椭圆等高线都是长轴、短轴分别与Z_1轴、Z_2轴平行！不过，合适的q_1与q_2保证q_1*q_2与p(Z|X)的峰值点重合，一般这就足以解决实际问题了。详细讲解可以参见[Bishop]的第10章。也可参考[Winn]的1.8节。
更近一步说，对二维随机变量的联合分布,能拟合出它峰值出现的位置,这就解决问题了;形状上有差异,无伤大雅.
[QUOTE]另外，计算可以用gibbs。上个月写了个model就是用gibbs，模型可能跟LDA很像，model的图形结构和hmm的图形结构一样，用了message passing来做inference，用了gibbs做learning。paper还没发，不好细说了，呵呵。 [/QUOTE]
祝贺呀,你科研效率真够高的,这么快就出paper了:)
message passing属于exact inference的范畴吧?[Winn]还提出了Variational Message Passing,还把这个方法用在了DNA Microarray Image Analysis上.说不定对你现在的工作有启发.他还给出了Java实现,像Simulink一样方便,连好Grapchical Model的框图,点start,挺方便.
[QUOTE]PS：这边做报告，喜欢让你推公式，所以还是有必要说清楚。还有，EM如果按照数学公式去做的话，结果一般是错误的。
Master Wugui says:" No accident" [/QUOTE]
昏啊,一个叫Wu Gui的硕士?第一眼看还以为是哪个老外,first name叫Wugui, ginven name叫Master,差点去google了，呵呵：）
有时间发个扫盲贴介绍一下你手头做的东西和所用方法呗(原创的工作如果你觉得不合适的话可以不提)?
教科书的方法都是具有指导意义，但是具体模型的应用，还是需要对理论模型进行修改，就像Andrew Yao他们做出的模型，我们拿过来还要根据具体的应用场景进行修改。
我觉得他们不能够独立，是因为z和theta是有因果关系，有一层逻辑关系，怎么消除这层逻辑关系是不是需要更进一步的考虑？另，Graphical model对于node之间的独立条件要求是很严格的。
当然，遇到不能够计算，我可以用二次函数去逼近，得到二次函数的形式，用高斯去表示它的分布，再用random sampling。
我现在三个projects，主要在做马尔科夫场中的热扩散分析，估计大家没有兴趣，哈哈。
【 在 hmily821224 的大作中提到: 】
: [QUOTE]给定w，根本推不出来z和θ独立，假设独立确实是可以简化计算的推导，但是我觉得假设更是体现了模型的思想。我看了一下blei的paper，他那个图也说明不了z和θ独立。
:
: 另外一方面，从EM的算法来说。让我们从最简单的mixture model说起，EM的E是w和z的从属关系的度量，即描述w有多大可能属于z。好，推广到LDA，我觉得LDA的E应该是(1)z有多大可能属于θ（可能你会说θ是参数，呵呵，在gm里面，参数也可以看作变量），p(θ|z)(2)w有多大可能属于z，p(z|w)。按照你给的p(θ|w)和p(z|w)，如果取极端情况即hard assignment，也就有可能出现跟w相关的θ和z，z根本不是属于θ这个超主题的范畴。我想弄清楚的是这个。 [/QUOTE]
: ...................