latent Dirichlet allocation (LDA)[转]

Latent Dirichlet Allocation(LDA) [pdf]模型是近年来提出的一种具有文本主题表示能力的非监督学习模型。

关键所在：it posits that each document is a mixture of a small number of topics and that each word’s creation is attributable to one of the document’s topics。

将文档看成是一组主题的混合，词有分配到每个主题的概率。

Probabilistic latent semantic analysis（PLSA） LDA可以看成是服 从贝叶斯分布的PLSA

LDA，就是将原来向量空间的词的维度转变为Topic的维度，这一点是十分有意义的。

例如，如果一个文档A，包含电脑这个关键词，那么A向量化后可能是,比如电脑这个词是
100万词汇中的第2维（便于举例），微机这个词是100万词汇中的第3维，维上的投影简单看作是tf，即文档中出现的次数。

A={x,2,0,…,x} 表示文档A中电脑出现了2次.x表示出现次数不care
B={x,0,3,…,x} 表示文档B中微机次数出现了3次。

如果是用词做维度的向量空间，做聚类也好，分类也好，A和B在电脑和微机上的这种向量表示，机器理解为A和B完全在表示不同的意义。而事实上，如果在词的 高维空间上看，电脑和微机的维是很近似的，正交性是很低的。

如果能够将高维空间上，近义词或者表示接近的词的维度“捏“成一个维度，比如电脑和微机这两个词被捏成了第2维，但是每个词在这个维上的权重给与不同的度 量（比如概率）。
这样上诉例子变为

A={x,2*pi,x,…x}，pi表示电脑这个词到Topic2的转移概率。
B={x,3*pj,x,…x}

这样，A和B看上去在第二个Topic上显示了一定的相关性。

由于Topic是被捏后的产物，每个Topic的正交性直观上看都很强，LDA开源的工具做出的结果可以把转移到TOpic最Top的那些词提取出来，都 是十分相关或近似的词。而Topic与Topic之间显示出很大的差异性。

短文本分类的商业价值是很大的，在视频分类，广告分类上都可以看作是短文本分类问题，我有幸做了一些这方面的工作，其中提到的短文本的扩展是很好的思路。

问答系统商业价值也很巨大，特别是封闭领域的问答系统，可以拦截投诉，用户提问，降低人工成本。开放领域的问答系统商业上感觉前途有限，当然把搜索引擎的 搜索结果进一步精化的思路肯定是搜索引擎的一个方向，用户会越来越懒，搜索引擎已经让用户懒了一些，还需要让用户继续懒下去。

下面是baidu知道中有人对LDA的解释
lda是一个集合概率模型，主要用于处理离散的数据集合，目前主要用在数据挖掘（dm）中的text mining和自然语言处理中，主要是用来降低维度的。据说效果不错。

以下是在tm中对lda的定义：
Latent Dirichlet allocation (LDA) is a generative probabilistic model of a corpus. The basic idea is
that documents are represented as random mixtures over latent topics, where each topic is characterized
by a distribution over words.

We describe latent Dirichlet allocation (LDA), a generative probabilistic model for collections of
discrete data such as text corpora. LDA is a three-level hierarchical Bayesian model, in which each
item of a collection is modeled as a finite mixture over an underlying set of topics. Each topic is, in
turn, modeled as an infinite mixture over an underlying set of topic probabilities. In the context of
text modeling, the topic probabilities provide an explicit representation of a document.

其实它还可以用在别的方面，早期是被用在自然语言处理的文本表示方面。因为他提供了一个理解相关词为什么在同一文档出现的框架解释模型。

=========================================

Latent Dirichlet allocation

This is a C implementation of variational EM for latent Dirichlet allocation (LDA), a topic model for text or other discrete data. LDA allows you to analyze of corpus, and extract the topics that combined to form its documents. For example, click here to see the topics estimated from a small corpus of Associated Press documents. LDA is fully described inBlei et al. (2003) .

This code contains:

an implementation of variational inference for the per-document topic proportions and per-word topic assignmentsa variational EM procedure for estimating the topics and exchangeable Dirichlet hyperparameterDownloads

Download the readme.txt .

Download the code: lda-c.tgz .

Sample data

2246 documents from the Associated Press [ download ].

Top 20 words from 100 topics estimated from the AP corpus [pdf].

还有一个 普林斯顿大学 的主题模型的邮件列表，牛人们：

https://lists.cs.princeton.edu/mailman/listinfo/topic-models

=============================================

[论文导读][教程][介绍]文本处理、图像标注中的一篇重要论文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）。