Latent Dirichlet Allocation

TF-IDF

问题的起源是文档排名,就像使用搜索引擎那样,给定关键字,返回排好序的文档列表。既然提到排序,就肯定有衡量标准,给定关键词,一个文档的重要性或者说相关性如何度量呢?

TF

首先,直观地,如果一篇文档中出现要查询的词的次数越多,相关性应该越大。于是很容易想到词频(TF)这个标准

词频TF(t)就是关键词t在文档中出现的次数
IDF

但是仅仅考虑词频必然会出现问题,因为不同的词应该有不同的重要性,举个例子:在计算机科学类的paper中,出现算法和文学类paper中出现算法的重要性是不一样的,又或者“的”这个字在汉语中出现的次数相当大,一篇文档中没有“的”字的概率是很小的,此时仅仅按照关键词中的“的”判断文档排名显然是不准确的。于是,我们希望加大稀缺词的权重,所以定义了逆文档频率(IDF)IDF的定义如下IDF(t)=logNDF(t)IDF(t)=logNDF(t)其中,NN为文档总数,DF(t)DF(t)为所有文档中出现了关键词tt的文档个数。所以,越是普遍的单词(“的”,“因此”等)IDF越小,而稀缺的单词(如文学paper中的“算法”)就对应着比较大的IDF

将TF和IDF结合到一起,得到TF-IDF的计算方法:TFIDF(t,d)=TF(t,d)IDF(t)TFIDF(t,d)=TF(t,d)IDF(t)所以,一篇文档和一条Query的相关度为Query中所有单词在这篇文档中的TF-IDF值之和。而两个文档间的相关度是文档向量的余弦值,余弦值越接近1,就表明夹角越接近0度,也就是两个向量越相似,这就叫”余弦相似性”。

TF-IDF的缺陷
  • 单纯地认为文本频数小的单词就越重要,文本频数大的单词就越无用,并不是完全正确的
  • 不能有效地反映单词的重要程度和特征词的分布情况,TF-IDF的精度并不是很高
  • 没有体现出单词的位置信息,这也是空间向量模型的不足

主题模型

TF-IDF模型中没有考虑文字背后的语义关联,即语义层面上的关联,可能在两个文档共同出现的单词很少甚至没有,但两个文档是相似的。判断文档相关性的时候需要考虑到文档的语义,而语义挖掘的利器是主题模型,LDA就是其中一种比较有效的模型。

主题模型的思想源于生成模型,其思想如下:一篇文章的每个词都是通过:以一定概率选择了某个主题,并从这个主题中以一定概率选择某个词语,形式化表述为p(word|doc)=topicp(word|topic)×p(topic|doc)p(word|doc)=topicp(word|topic)×p(topic|doc),具体内容在下文中描述。

能够发现文档-词语之间所蕴含的潜在语义关系(即主题)——将文档看成一组主题的混合分布,而主题又是词语的概率分布——从而将高维度的“文档-词语”向量空间映射到低维度的“文档-主题”和“主题-词语”空间,有效提高了文本信息处理的性能。

基础知识
二项分布(Binomial distribution)

nn次重复伯努利试验,一次概率为ppkk次试验概率函数为P(K=k)=Cknpk(1p)nkP(K=k)=Cknpk(1p)nk,二项分布计为Xb(n,p)Xb(n,p)

多项式分布

每次试验可能有kk种结果,每种结果的可能性是pipi,则nn次试验各种结果出现次数分别为x1,,xkx1,,xk的概率是

P(x1,...,xk;n,p1,...,pk)=n!x1!...xk!px11...pxkkP(x1,...,xk;n,p1,...,pk)=n!x1!...xk!px11...pxkk

是二项分布的扩展。

gamma函数

gamma函数形如Γ(x)=0tx1etdtΓ(x)=0tx1etdt这个函数有如下性质Γ(x+1)=xΓ(x)Γ(x+1)=xΓ(x),因此gamma函数可以看作是阶乘在实数集上的延拓Γ(n)=(n1)!Γ(n)=(n1)!此外,gamma函数还有如下性质

  • x(0,1)x(0,1)Γ(1x)Γ(x)=πsin(πx)Γ(1x)Γ(x)=πsin(πx)
  • Γ(12)=πΓ(12)=π
共轭先验分布

定义
θθ是总体分布中的参数,p(θ)p(θ)θθ的先验密度函数,假如由抽样信息xx算得的后验密度函数p(θ|x)p(θ|x)p(θ)p(θ)有相同的函数形式(同一个分布簇),则称p(θ)p(θ)p(θ|x)p(θ|x)的(自然)共轭先验分布,称p(θ)p(θ)p(θ|x)p(θ|x)为共轭分布。

Beta分布-二项分布的共轭先验分布

给定参数α>0,β>0α>0,β>0,取值范围为[0,1][0,1]的随机变量xx的概率密度函数为

f(x;α,β)=Γ(α+β)Γ(α)Γ(β)xα1(1x)β1=1B(α,β)xα1(1x)β1f(x;α,β)=Γ(α+β)Γ(α)Γ(β)xα1(1x)β1=1B(α,β)xα1(1x)β1

则称x满足Beta分布,Beta分布的均值为αα+β,方差为αβ(α+β)2(α+β+1)。参数α,β共同控制Beta分布的函数的形状,见下图。

假定先验分布p(θ)和似然概率p(x|θ)满足

p(θ)=Γ(α+β)Γ(α)Γ(β)θα1(1θ)β1=1B(α,β)θα1(1θ)β1p(x|θ)=Cknθk(1θ)nk

那么,考虑到p(x)为常数项,可知后验概率

p(θ|x)=p(x|θ)p(θ)p(x)=1Zθα+k1(1θ)β+nk1.

所以,根据定义,p(θ)p(θ|x)是共轭分布。

Dirichlet分布

维度k2的狄利克雷分布在参数α1,,αk>0上,其概率密度函数为

f(θ1,..,θk;α1,...,αk)=1B(α)ki=1θαi1iB(α)=ki=1Γ(αi)Γ(ki=1αi)

同上,假设θ=(θ1,,θk)有先验分布和似然函数,可以有

p(θ)=1B(α)ki=1θαi1ip(x|θ)=n!n1!...nk!θn11...θnkkp(θ|x)=1Zki=1θαi+ni1i

和Dirichlet分布形式一致。
Dirichlet分布的均值向量为(α1kiαi,,αkkiαi)

铺垫模型

定义:

  • w表示词,V表示所有单词的个数(固定值)
  • z表示主题,k是主题的个数(预先给定,固定值)
  • D=(d1,,dM)表示语料库,其中M是语料库中的文档数(固定值)
  • d=(w1,,wN)表示一个文档,其中N表示一个文档中的词数(随机变量)
Unigram model

对于文档d=(w1,,wN),用p(wn)表示wn的先验概率,生成文档d的概率为p(d)=Nn1p(wn)unigram model假设文本中的词服从Multinomial分布,而Multinomial分布的先验分布为Dirichlet分布。

Unigram modelUnigram model

上图中,wn是在文本中观察到的第n个词,pα是隐含未知变量,其中

  • p是词服从的Multinomial分布的参数
  • α是Dirichlet分布(即Multinomial分布的先验分布)的参数

一般α由经验事先给定,p由观察到的文本中出现的词学习得到,表示文本中出现每个词的概率。

Mixture of unigrams model

Mixture of unigrams model生成过程是:给某个文档先选择一个主题,再根据该主题生成文档,该文档中的所有词都来自一个主题。假设主题有z1,,zk,生成文档d的概率为

p(d)=zp(z)Nn=1p(wn|z)

Mixture of unigrams modelMixture of unigrams model

如上图所示。

PLSA模型

Mixture of unigrams model中假定一篇文档只由一个主题生成,可实际中,一篇文章往往有多个主题,只是这多个主题各自在文档中出现的概率大小不一样。PLSA是一种词袋模型,不关注词和词之间的出现顺序。

假设一组共现(co-occurrence)词项关联着一个隐含的主题类别zk{z1,,zK}。同时定义

  • p(di)表示海量文档中某篇文档被选中的概率
  • p(wj|di)表示词wj在给定文档di中出现的概率
  • p(zk|di)表示具体某个主题zk在给定文档di下出现的概率
  • p(wj|zk)表示具体某个词wj在给定主题zk下出现的概率,与主题关系越密切的词,其条件概率越大

文档到词项的生成方法

  1. 按照概率p(di)选择一篇文档di
  2. 选定文档di后,从主题分布中按照概率p(zk|di)选择一个隐含的主题类别zk
  3. 选定zk后,从词分布中按照概率p(wj|zk)选择一个词wj

整个过程便是:选定文档->生成主题->确定主题生成词。


发现文档集中的主题(分布)

PLSAPLSA

如上图所示,文档d和单词w是可被观察到的(样本),但主题z却是隐藏的。因为p(wj|di)是已知的(统计文档词频),根据大量已知的文档-词项信息可以训练出p(zk|di),p(wj|zk)。文档中每个词的生成概率为

p(wj,di)=p(di)p(wj|di)=p(di)Kk=1p(wj|zk)p(zk|di)

其中p(di)可事先计算求出,p(zk|di),p(wj|zk)未知。

考虑词和词(N)之间、文档(M)和文档之间的独立性,则整个语料库中词的分布为

p(w,D)=Mi=1Nj=1p(wj,di)n(wj,di)

其中n(wj,di)表示词项wj在文档di中出现的次数,n(di)表示文档di中词的总数,并且令p(wj|zk)=ϕkj,p(zk|di)=θik将未知量矩阵化成Φ,Θ。所以得到对数似然函数

l(Φ,Θ)=Mi=1Nj=1n(wj,di)logp(wj,di)=Mi=1Nj=1n(wj,di)(logp(di)+logKk=1p(wj|zk)p(zk|di))=Mi=1n(di)(logp(di)+Nj=1n(wj,di)n(di)logKk=1ϕkjθik)Mi=1Nj=1n(wj,di)logKk=1ϕkjθikMi=1Nj=1n(wj,di)Kk=1p(zk|di,wj)log(ϕkjθik)

含有隐含变量的优化可以使用EM算法求解,很复杂,不具体写了
E步

p(zk|di,wj)=p(zk,di,wj)Kl=1p(zl,di,wj)=ϕkjθikMl=1ϕljθil

M步
经过E步,还需考虑约束条件,即

Nj=1ϕkj=1Kk=1θik=1

用拉格朗日乘子法解得

ϕkj=Mi=1n(di,wj)p(zk|di,wj)Mi=1Nj=1n(di,wj)p(zk|di,wj)θik=Nj=1n(di,wj)p(zk|di,wj)n(di)

这样就求解出了Φ,Θ。PLSA的模型示意如下图所示:

PLSAPLSA

LDA(Latent Dirichlet Allocation)

LDA在pLSA的基础上加层贝叶斯框架,在贝叶斯框架下的LDA中,我们不再认为主题分布(各个主题在文档中出现的概率分布)和词分布(各个词语在某个主题下出现的概率分布)是唯一确定的(而是随机变量)。这体现了贝叶斯派的核心思想,把未知参数当作是随机变量,不再认为是某一个确定的值。即选主题和选词依然都是两个随机的过程。

LDA需要两个Dirichlet先验参数,这个Dirichlet先验为某篇文档随机抽取出某个主题分布和词分布。

LDA模型中文档生成方式

α是主题分布的先验分布,β是词分布的先验分布。

  1. 按照先验概率p(di)选择一篇文档di
  2. 从Dirichlet分布α中取样生成文档di的主题分布θi,换言之,主题分布θi由超参数为α的Dirichlet分布生成
  3. 从主题的多项式分布θi中取样生成文档dij个词的主题zij
  4. 从Dirichlet分布β中取样生成主题zij对应的词语分布ϕzij,换言之,词语分布ϕzij由参数为β的Dirichlet分布生成
  5. 从词语的多项式分布ϕzij中采样最终生成词语wij

示意图如下:

LDALDA

LDA在pLSA的基础上给这两参数p(zk|di),p(wj|zk)加了两个先验分布的参数(贝叶斯化):一个主题分布的先验分布Dirichlet分布α,和一个词语分布的先验分布Dirichlet分布β。这里α,β都是参数向量。

LDA生成文档的过程中,先从dirichlet先验中“随机”抽取出主题分布,然后从主题分布中“随机”抽取出主题,最后从确定后的主题对应的词分布中“随机”抽取出词。虽说是随机取值,但是不同的参数α,β导致可选值的分布是不一样的,如下图所示

不同参数的dirichlet分布不同参数的dirichlet分布

LDA发现文档集中的主题

文档生成后,LDA把这两参数p(zk|di),p(wj|zk)变成随机变量,且加入dirichlet先验。

在pLSA中,我们使用EM算法去估计“主题-词项”矩阵和“文档-主题”矩阵:Φ,Θ,这两参数都是个固定的值。在LDA中,估计Φ,Θ这两未知参数可以用变分(Variational inference)-EM算法,也可以用gibbs采样,前者的思想是最大后验估计MAP(MAP与MLE类似,都把未知参数当作固定的值),后者的思想是贝叶斯估计。

Gibbs采样
Gibbs抽样是马尔可夫链蒙特卡尔理论(MCMC)中用来获取一系列近似等于指定多维概率分布(比如2个或者多个随机变量的联合概率分布)观察样本的算法。

给定一个文档集合,w是可以观察到的已知变量,α,β和是根据经验给定的先验参数,其他的变量zΘΦ都是未知变量。

求解Θ,Φ的过程很复杂,最终求解的Dirichlet分布期望为:

ϕkt=ntk+βtVt=1(ntk+βt)θmk=nkm+αkKk=1(nkm+αk)

其中,ϕkt=p(wt|zk),θmk=p(zk|dm)nkt是词wt在主题zk中出现的次数,nkm是主题zk在文章dm中出现的次数。

引用
[1] LDA-math-神奇的Gamma函数
[2] 共轭先验分布
[3] 通俗理解LDA主题模型
[4] 关于Beta分布、二项分布与Dirichlet分布、多项分布的关系

分享到