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的计算方法:TF−IDF(t,d)=TF(t,d)∗IDF(t)TF−IDF(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次重复伯努利试验,一次概率为pp,kk次试验概率函数为P(K=k)=Cknpk(1−p)n−kP(K=k)=Cknpk(1−p)n−k,二项分布计为X∼b(n,p)X∼b(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)=∫∞0tx−1e−tdtΓ(x)=∫∞0tx−1e−tdt这个函数有如下性质Γ(x+1)=xΓ(x)Γ(x+1)=xΓ(x),因此gamma函数可以看作是阶乘在实数集上的延拓Γ(n)=(n−1)!Γ(n)=(n−1)!此外,gamma函数还有如下性质
- 对x∈(0,1)x∈(0,1),Γ(1−x)Γ(x)=πsin(πx)Γ(1−x)Γ(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(1−x)β−1=1B(α,β)xα−1(1−x)β−1f(x;α,β)=Γ(α+β)Γ(α)Γ(β)xα−1(1−x)β−1=1B(α,β)xα−1(1−x)β−1则称x满足Beta分布,Beta分布的均值为αα+β,方差为αβ(α+β)2(α+β+1)。参数α,β共同控制Beta分布的函数的形状,见下图。
假定先验分布p(θ)和似然概率p(x|θ)满足
p(θ)=Γ(α+β)Γ(α)Γ(β)θα−1(1−θ)β−1=1B(α,β)θα−1(1−θ)β−1p(x|θ)=Cknθk(1−θ)n−k那么,考虑到p(x)为常数项,可知后验概率
p(θ|x)=p(x|θ)p(θ)p(x)=1Zθα+k−1(1−θ)β+n−k−1.所以,根据定义,p(θ)和p(θ|x)是共轭分布。
Dirichlet分布
维度k≥2的狄利克雷分布在参数α1,…,αk>0上,其概率密度函数为
f(θ1,..,θk;α1,...,αk)=1B(α)k∏i=1θαi−1iB(α)=∏ki=1Γ(αi)Γ(∑ki=1αi)同上,假设θ=(θ1,…,θk)有先验分布和似然函数,可以有
p(θ)=1B(α)k∏i=1θαi−1ip(x|θ)=n!n1!...nk!θn11...θnkkp(θ|x)=1Zk∏i=1θαi+ni−1i和Dirichlet分布形式一致。
Dirichlet分布的均值向量为(α1∑kiαi,…,αk∑kiαi)。
铺垫模型
定义:
- w表示词,V表示所有单词的个数(固定值)
- z表示主题,k是主题的个数(预先给定,固定值)
- D=(d1,…,dM)表示语料库,其中M是语料库中的文档数(固定值)
- d=(w1,…,wN)表示一个文档,其中N表示一个文档中的词数(随机变量)
Unigram model
对于文档d=(w1,…,wN),用p(wn)表示wn的先验概率,生成文档d的概率为p(d)=∏Nn−1p(wn)unigram model假设文本中的词服从Multinomial分布,而Multinomial分布的先验分布为Dirichlet分布。
上图中,wn是在文本中观察到的第n个词,p和α是隐含未知变量,其中
- p是词服从的Multinomial分布的参数
- α是Dirichlet分布(即Multinomial分布的先验分布)的参数
一般α由经验事先给定,p由观察到的文本中出现的词学习得到,表示文本中出现每个词的概率。
Mixture of unigrams model
Mixture of unigrams model生成过程是:给某个文档先选择一个主题,再根据该主题生成文档,该文档中的所有词都来自一个主题。假设主题有z1,…,zk,生成文档d的概率为
p(d)=∑zp(z)N∏n=1p(wn|z)如上图所示。
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下出现的概率,与主题关系越密切的词,其条件概率越大
文档到词项的生成方法
- 按照概率p(di)选择一篇文档di
- 选定文档di后,从主题分布中按照概率p(zk|di)选择一个隐含的主题类别zk
- 选定zk后,从词分布中按照概率p(wj|zk)选择一个词wj
整个过程便是:选定文档->生成主题->确定主题生成词。
发现文档集中的主题(分布)
如上图所示,文档d和单词w是可被观察到的(样本),但主题z却是隐藏的。因为p(wj|di)是已知的(统计文档词频),根据大量已知的文档-词项信息可以训练出p(zk|di),p(wj|zk)。文档中每个词的生成概率为
p(wj,di)=p(di)p(wj|di)=p(di)K∑k=1p(wj|zk)p(zk|di)其中p(di)可事先计算求出,p(zk|di),p(wj|zk)未知。
考虑词和词(N)之间、文档(M)和文档之间的独立性,则整个语料库中词的分布为
p(w,D)=M∏i=1N∏j=1p(wj,di)n(wj,di)其中n(wj,di)表示词项wj在文档di中出现的次数,n(di)表示文档di中词的总数,并且令p(wj|zk)=ϕkj,p(zk|di)=θik将未知量矩阵化成Φ,Θ。所以得到对数似然函数
l(Φ,Θ)=M∑i=1N∑j=1n(wj,di)logp(wj,di)=M∑i=1N∑j=1n(wj,di)(logp(di)+logK∑k=1p(wj|zk)p(zk|di))=M∑i=1n(di)(logp(di)+N∑j=1n(wj,di)n(di)logK∑k=1ϕkjθik)∝M∑i=1N∑j=1n(wj,di)logK∑k=1ϕkjθik≥M∑i=1N∑j=1n(wj,di)K∑k=1p(zk|di,wj)log(ϕkjθik)含有隐含变量的优化可以使用EM算法求解,很复杂,不具体写了
E步
M步
经过E步,还需考虑约束条件,即
用拉格朗日乘子法解得
ϕkj=∑Mi=1n(di,wj)p(zk|di,wj)∑Mi=1∑Nj=1n(di,wj)p(zk|di,wj)θik=∑Nj=1n(di,wj)p(zk|di,wj)n(di)这样就求解出了Φ,Θ。PLSA的模型示意如下图所示:
LDA(Latent Dirichlet Allocation)
LDA在pLSA的基础上加层贝叶斯框架,在贝叶斯框架下的LDA中,我们不再认为主题分布(各个主题在文档中出现的概率分布)和词分布(各个词语在某个主题下出现的概率分布)是唯一确定的(而是随机变量)。这体现了贝叶斯派的核心思想,把未知参数当作是随机变量,不再认为是某一个确定的值。即选主题和选词依然都是两个随机的过程。
LDA需要两个Dirichlet先验参数,这个Dirichlet先验为某篇文档随机抽取出某个主题分布和词分布。
LDA模型中文档生成方式
α是主题分布的先验分布,β是词分布的先验分布。
- 按照先验概率p(di)选择一篇文档di
- 从Dirichlet分布α中取样生成文档di的主题分布θi,换言之,主题分布θi由超参数为α的Dirichlet分布生成
- 从主题的多项式分布θi中取样生成文档di第j个词的主题zij
- 从Dirichlet分布β中取样生成主题zij对应的词语分布ϕzij,换言之,词语分布ϕzij由参数为β的Dirichlet分布生成
- 从词语的多项式分布ϕzij中采样最终生成词语wij
示意图如下:
LDA在pLSA的基础上给这两参数p(zk|di),p(wj|zk)加了两个先验分布的参数(贝叶斯化):一个主题分布的先验分布Dirichlet分布α,和一个词语分布的先验分布Dirichlet分布β。这里α,β都是参数向量。
LDA生成文档的过程中,先从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+βt∑Vt=1(ntk+βt)θmk=nkm+αk∑Kk=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分布、多项分布的关系