Home > life is fun > Latent Dirichlet Allocation 举例学习

Latent Dirichlet Allocation 举例学习


http://www.zhizhihu.com/html/y2010/1384.html

有两种方法设计分类器:
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节。

Advertisements
Categories: life is fun
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: