第5章〓关键词提取
关键词提取是指从文本中提取与文章主题或当前任务最相关的词语，例如，从文献中选取出能够反映文章主题的词语作为关键词。关键词提取可用于自动文摘、文献检索，文本分类等任务。提取关键词最简单的一个方法就是利用词频，将高频出现的词作为关键词，这种方法虽然简单，但是往往结果较差。本章将介绍以下几种关键词提取算法: 基于图的TextRank算法、基于词频和逆文本频率的TFIDF算法、基于分布的LDA算法和PLSA算法。

5.1TextRank关键词提取算法

TextRank［1］是一个无监督的基于图的排序算法，它与Google的PageRank算法相似。PageRank是根据网页之间的链接关系来对网页的重要程度进行排序。也就是说，在进行网页排序的过程中，PageRank算法只需要知道网页间的结构信息，而无须知道网页的具体内容。从图的角度来看，网页可以作为节点，若两个网页间存在链接关系，则相应的两个节点间就存在一条边。图中每个节点的重要程度由图中的这些边决定，即由整张图的结构决定，而非由节点的内部信息决定。TextRank采用了与PageRank相似的思路。在提取关键词时，TextRank由文本中提取出词汇图，以单词作为节点，单词间的关系作为边，然后根据图对单词进行排序。

5.1.1基于图的排序算法

基于图的排序算法会递归地从整张图中提取信息，最终完成对图中节点的重要程度的排序。基于图的排序算法的基本思想是投票，若图中存在由节点A指向节点B的边，则认为节点A为节点B投了一票，图中获得票数越多的节点就越重要。此外，不同的节点投出的票的重要程度是不同的，这取决于投票节点的重要程度。因此决定节点的重要程度的因素有两个: 有多少节点为该节点投票; 为该节点投票的那些节点自身的重要程度。


记有向图为G=(V,E)，其中V代表节点集，E代表边集，E是一个|V|×|V|的矩阵。若图G中存在由Vj指向Vi的边，则矩阵中第i行第j列的元素值为1，否则为0。对于节点Vi，S(Vi)为节点Vi的得分，即节点Vi的所得的票数，每个节点都会被赋予一个随机的初始得分，然后对每个节点的得分进行迭代更新，直至节点的得分值收敛。节点得分的更新方式如下: 

所有指向Vi的节点组成的集合记为In(Vi); 所有由Vi出发所指向的节点组成的集合记为Out(Vj); 则节点Vi经过一次更新后的得分为: 


S(Vi)=(1-d)+d×∑Vj∈In(Vi)1|Out(Vj)|S(Vj)（5.1）


式（5.1）中的d为阻尼系数，其值为0~1，通常取0.85［2］。d用于模拟从一个节点跳转至另一个节点的概率。在用户浏览网页的情景下，可以理解为: 若当前处于网页Vi，用户通过单击此网页上的链接，跳转至新网页Vj(j∈In(Vi))的概率为d; 用户没有单击此网页上的链接，而是直接打开了一个全新的网页Vk(kIn(Vi))的概率为1-d。




图51有向图G



【例51】模拟图的更新过程。

如图51所示的有向图G可以表示为: 


G=(V,E)
V={V1,V2,V3,V4}
E=
0001
1010
1000
0110


假设分数的随机初始值为: 


S(V1)=1，S(V2)=4，S(V3)=2，S(V4)=6


取d=0.85，对于节点V2，第一次的更新过程如下: 


In(V2)={V1,V3}，Out(V1)={V2,V3}，Out(V3)={V2,V4}
S(V2)=(1-0.85)+0.85×1|Out(V1)|S(V1)+1|Out(V3)|S(V3)
=0.15+0.85×12×1+12×2=1.425


则第一次更新后: 

S(V2)=1.425


若从矩阵的角度计算，第一次更新的计算过程为: 


E×D-1×S=
0001
1010
1000
0110×
2000
0100
0020
0001-1×1426
=

0001
0.500.50
0.5000
010.50×1426
=61.50.55


其中,


Dii=∑jeji
S=(1-0.85)+0.85×61.50.55=5.2501.4250.5754.400


则第一次更新后: 


S(V1)=5.250，S(V2)=1.425，S(V3)=0.575，S(V4)=4.400


重复上述过程，对节点的得分进行迭代更新，直至节点的得分收敛，收敛后每个节点的得分即为最终能够反映节点重要程度的得分。

5.1.2基于图的排序算法的拓展运用

传统的基于图的排序算法作用于有向图，但是也可运用于无向图和加权图中。

在无向图中，若想使用基于图的排序算法，只需假设无向图中节点的入度和出度相等且都等于该节点的度，即In(Vi)=Out(Vi)=Degree(Vi)。

加权图是指边有相应权重的图，根据自然语言文本构建的图往往都是加权图，TextRank算法中使用的便是加权图。对于加权图，我们将节点的更新公式修改为: 


WS(Vi)=(1-d)+d×∑Vj∈In(Vi)wji∑Vk∈Out(Vj)wjkWS(Vj)（5.2）





图52带权有向图G



【例52】基于图的排序算法在加权图中的运用。

如图52所示的带权有向图G可以表示为: 


G=(V,E)
V={V1,V2,V3,V4}
E=
0001
1010
1000
0110


边的权重矩阵为: 


W=
0120
0002
0405
3000



假设分数的随机初始值为: 


S(V1)=1，S(V2)=4，S(V3)=2，S(V4)=6


取d=0.85，对于节点V2，第一次的更新过程如下: 


In(V2)={V1,V3}，Out(V1)={V2,V3}，Out(V3)={V2,V4}
S(V2)=(1-0.85)+0.85×w12w12+w13S(V1)+w32w32+w34S(V3)
=0.15+0.85×11+2×1+44+5×2=1.189


则第一次更新后: 

S(V2)=1.189


若从矩阵的角度计算，第一次更新的计算过程为: 


WT×D-1×S=

0003
1040
2000
0250×
3000
0200
0090
0003-1×
1426
=
0003
1/304/90
2/3000
025/90×1426=1811/92/382/9


其中，


Dii=∑jwij
S=(1-0.85)+0.85×1811/92/382/9=15.4501.1890.7177.894


则第一次更新后: 


S(V1)=15.450，S(V2)=1.189，S(V3)=0.717，S(V4)=7.894


重复上述过程，对节点的得分进行迭代更新，直至节点的得分收敛，收敛后每个节点的得分即能够反映节点的重要程度。

5.1.3基于图的排序算法在关键词提取中的运用

为了将基于图的排序算法运用于自然语言文本，首先需要用图来表示文本。不同级别的文本单元均可以作为节点，例如，节点可以是单词、固定搭配、整个句子等。节点间的关系可以是语法或语义相关、位置相关等。

将基于图的排序模型运用于图，需要以下步骤。

（1） 根据当前任务将文本分割为一个个小的文本单元，并且将这些文本单元作为图的节点。

（2） 定义文本单元间存在哪些关系，并且根据这些关系在节点间构建边。

（3） 使用基于图的排序算法对图进行迭代更新直至节点对应的得分值收敛。

（4） 根据每个节点的得分对节点进行降序排列。

5.1.4TextRank算法

TextRank算法的输入为自然语言文本，其输出为由文本中关键的单词或短语构成的集合。TextRank算法的实现主要包含以下步骤。

（1） 对文本进行过滤和分割，将分割后的文本作为图中的节点。为了防止图的节点数过多，设分割后的一个单元中仅包含一个单词，即文本中一个单词对应图中的一个节点。每一个节点的得分都被初始化为1。

（2） 为存在共现关系的节点建立边。单词间的共现关系定义为: 设一个窗口中最多包含N个单词，若文本中的两个单词出现于同一个窗口，则称这两个单词间存在共现关系。

（3） 使用基于图的排序算法对图进行迭代更新直至收敛。通常需要进行20~30轮迭代。

（4） 根据每个节点的得分对节点进行降序排列，选择得分最高的T个节点对应的单词作为关键词。通常T的值设置为节点数量的三分之一。对于挑选出的关键词，若某些关键词在文本中是相邻的，则将它们组合起来作为一个关键词。

5.2TFIDF关键词提取算法 

TFIDF（Term FrequencyInverse Document Frequency）是一种用于信息检索与数据挖掘的常用加权技术。其中TF是词频，IDF是逆文本频率指数。在关键词提取问题中，TFIDF可以用来评估某个词在文件集的某篇文档中的重要程度。若一个词在某篇文档中高频出现，但是在文件集其他文档中出现的频率较低，则说明这个词较能反映这篇文档的特征。据此，TFIDF中使用了两个指标，即词频TF和逆向文档词频IDF，TF的值与词语在当前文档中出现的频率成正比，IDF的值与词语在文件集所有文档中出现的频率成反比，TFIDF的值即为TF与IDF的乘积。在某篇文档中，某个单词对应的TFIDF值越大说明这个单词在文档中越重要。


TF(w,d)是指词w在文档d中出现的频率。设文档d中共包含Nd个词，其中词w出现了Nd,w次，则


TF(w,d)=Nd,wNd（5.3）


在文件集中，设文档总数为D，词w在Dw篇文档中出现过，则


IDF(w)=lnDDw+1（5.4）


那么，单词w在文档d中的TFIDFd,w值为:


TFIDFd,w=TF(w,d)×IDF(w)（5.5）


【例53】假设在500篇文章中，“自然语言处理”一词在30篇文章中出现过。第一篇文章共包含1000个词，其中“自然语言处理”一词出现了80次。求“自然语言处理”相应的TFIDF值。

“自然语言处理”对应的TF值为: 

TF=80/1000=0.08

“自然语言处理”对应的IDF值为:  

IDF=ln(500/31)≈2.78

那么，“自然语言处理”对应的TFIDF值为: 

TF×IDF=0.08×2.78≈0.22

通过上述过程可以计算出文档中每个词语对应的TFIDF值，并选择TFIDF值较大的词作为关键词。

5.3LDA与PLSA关键词提取算法 

LDA（Latent Dirichlet Allocation［3］）模型和PLSA（Probabilistic Latent Semantic Analysis［4］）模型都属于生成概率模型。模型中会用到以下数据: 单词、文档和语料。

（1） 单词w: 文本由一些离散的基本单元构成，文本中的一个单词被认为是一个基本单元，LDA和PLSA模型中忽略了单词间的顺序关系。

（2） 文档d: 由N个单词的序列构成，表示为d={w1,w2,…,wN}。

（3） 语料D: 由M篇文档组成，D={d1,d2,…,dM}。

对于给定的语料库，LDA模型和PLSA模型都能估计出语料库中每篇文档的主题分布和词分布。

（1） 主题是某些关键词的集合，如果一篇文档中出现这些关键词，认为该文档中包含该主题的内容。一篇文档可能包含多种主题，某一主题的关键词在文中出现的次数越多，则该主题在文档的主题分布中相应的概率值越大。例如，对于一篇新闻文档，其中可能包含“金融”“教育”“科技”3个主题的相关内容，而这3个主题在文档中的分布情况即为该文档的主题分布，比如主题分布可能为{金融: 0.1，教育: 0.6，科技: 0.3}。

（2） 对于某一主题，其中会包含许多关键词，与该主题越相关的词在主题的词分布中相应的概率值越大。

主题分布可以反映主题与文档的相关度，而词分布可以反映主题与词语的相关度，那么这两个相关度的乘积就能够反映词语与文档的相关度。得到文档中各个词语与该文档的相关度后，可以提取与文档相关度较高的词语作为文档的关键词。

LDA模型和PLSA模型都属于词袋模型，即LDA模型和PLSA模型不关注词语间的顺序。LDA模型和PLSA模型中抽取一个词语的过程如下: 对于某文档，根据该文档的主题分布抽取一个主题，再根据主题上的词分布抽取一个词。对于一篇有N个词的文档来说，需要将词语抽取过程重复N次，便可得到一篇文档。在此过程中，已知文档中有哪些词，即已知文档中的词分布，要据此推断文档的主题分布和主题的词分布。为了更好地理解这一过程，可以拿常见的抛硬币问题进行类比: 假设当前有两个质地不均匀的硬币A和硬币B，一次只抛硬币A和硬币B中的一个。抛硬币的过程可以描述为: 先按照一定的概率，从硬币A和硬币B中选择一个，然后多次抛这枚硬币，记录抛出的硬币是正面朝上还是反面朝上。也就是已知多轮抛硬币的结果，求硬币A和硬币B被选中的概率和每枚硬币正面朝上的概率。在这个例子中，选硬币的过程类似选主题的过程，而抛硬币的过程与选词语的过程类似，这个例子在下面还会详述。 

5.3.1相关基础知识
1. 分布

（1）  泊松分布: 泊松分布的参数λ是单位时间（或单位面积）内随机事件的平均发生次数。 在LDA模型中用泊松分布来模拟文档中词语个数的分布情况。泊松分布的概率密度函数为: 


P(X=k)=λkk!e-λ,k=0,1,…（5.6）


（2） 二项式分布（Binomial distribution）: 二项式分布是n个独立的“是/非试验”中成功的次数的离散概率分布，其中每次试验的成功概率为p。当n=1时，二项式分布就是伯努利分布。二项式分布的概率密度函数为: 


P(K=k)=nkpk(1-p)n-k，nk=n!k!(n-k)!（5.7）


（3） 多项式分布（Multinomial Distribution）: 多项式分布是二项式分布在高维度上的推广，二项式分布的试验结果只有两个(是和非)，而多项式分布的试验结果则多于两个。参照二项式分布试验的特点，多项式分布试验的特点如下: 每种结果都有各自发生的概率，所有结果的发生概率之和为1; 各次试验相互独立，每次试验结果都不受其他各次试验结果的影响。


∑ki=1pi=1,pi>0
P(x1,x2,…,xk; N,p1,p2,…,pk)=N!x1!x2!…xk!px11px22…pxkk（5.8）
N=x1+x2+…+xk



（4） Beta分布: Beta分布是一种连续型概率密度分布。给定参数α>0和β>0，取值范围为［0,1］的随机变量x的概率密度函数为: 


p(x; α,β)=1B(α,β)xα-1(1-x)β-1（5.9）
B(α,β)=∫10tα-1(1-t)β-1dt



Beta函数相关性质: 


B(α,β)=(α-1)!(β-1)!(α+β-1)!


函数相关性质为Γ(n+1)=n!,因此


B(α,β)=Γ(α)Γ(β)Γ(α+β)


（5） 狄利克雷分布（Dirichlet Distribution）: 狄利克雷分布是Beta分布在高维度上的推广，概率密度函数为: 


p(x1,x2,…,xk; α1,α2,…,αk)=1B(α)∏ki=1xαi-1i（5.10）



其中，


B(α)=∫10∏ki=1tαi-1idt，∑xi=1
B(α)=∫10∏ki=1tαi-1idt=∏ki=1(αi-1)!∑ki=1αi-1!=∏ki=1Γ(αi)Γ∑ki=1αi


上述分布的关系为: 二项式分布和多项式分布类似，Beta分布和狄利克雷分布类似，Beta分布是二项式分布的共轭先验概率分布，而狄利克雷分布是多项式分布的共轭先验概率分布。

2. 共轭先验分布

贝叶斯公式为: 


P(Ai|B)=p(B|Ai)p(Ai)∑∞j=1p(B|Aj)P(Aj)（5.11）


其中，p(Ai)称为先验分布，p(Ai|B)称为后验分布。

贝叶斯学派里的一个基本观点是: 对于任何一个未知量都可以使用概率分布来描述其未知的状况。在抽样之前，基于已有的知识对于未知量的概率分布进行的预估，这在贝叶斯公式里面被称作先验分布，即式（5.11）中的p(Ai)，然后再基于样本的分布情况得出后验分布，即式（5.11）中的p(Ai|B)。

共轭分布的定义: 在贝叶斯公式中，如果后验分布与先验分布属于同类，则先验分布与后验分布被称为共轭分布。

共轭先验分布: 设θ是总体分布中的参数(或参数向量)，p(θ)是θ的先验密度函数，假如由抽样信息算得的后验密度函数p(θ|x)与p(θ)有相同的函数形式，则称p(θ)是参数θ的共轭先验分布。

【例54】证明Beta分布是二项式分布的共轭先验分布。

设事件A发生的概率P(A)=θ，为了估计θ的值，进行了n次独立实验，其中事件A出现了x次，因此X~B(n,θ)。概率密度函数为: 


p(X=x|θ)=nxθx(1-θ)n-x（5.12）


根据贝叶斯公式，为了得到参数θ的后验概率p(θ|x)，需要知道p(θ)，由于没有其他有用的信息，因此只能认为θ在区间［0,1］上均匀分布，即θ~U(0,1)。

计算联合概率分布p(x,θ): 


p(x,θ)=p(x|θ)p(θ)


根据联合概率分布计算p(x)的边缘概率分布: 


p(x)=∫10p(x,θ)dθ
=∫10nxθx(1-θ)n-xdθ


由于Beta函数B(α,β)=∫10tα-1(1-t)β-1dt，故可推出: 


p(x)=nxB(x+1,n-x+1)


计算p(θ|x): 


p(θ|x)=p(x,θ)p(x)=1B(x+1,n-x+1)θx(1-θ)n-x


即p(θ|x)满足参数为(x+1)和(n-x+1)的β分布，即


p(θ|x)~Beta(x+1,n-x+1)


而先验分布p(θ)满足区间(0,1)上的均匀分布，区间(0,1)上的均匀分布是一种特殊的β分布，即


p(θ)~Beta(1,1)


由此可见，参数θ的先验概率p(θ)与其后验概率p(θ|x)都属于Beta分布，因此Beta分布是二项式分布的共轭先验分布。

【例55】证明Beta分布是伯努利分布的共轭先验分布。

参数为θ的伯努利模型，其结果x的分布情况为: 


P(x|θ)=θx(1-θ)1-x，x=0,1


设参数θ满足参数为α和β的Beta分布，即


P(θ|α,β)=θα-1(1-θ)β-1∫10tα-1(1-t)β-1dt


由于给定样本后P(x)为定值，假设∫10tα-1(1-t)β-1dt也为定值，计算参数θ的后验概率: 


P(θ|x)=P(x|θ)P(θ)P(x)
∝P(x|θ)P(θ)
∝［θx(1-θ)1-x］［θα-1(1-θ)β-1］
=θx+α-1(1-θ)β-x


将θx+α-1(1-θ)β-x进行归一化后得: 


P(θ|x)=θx+α-1(1-θ)β-x∫10tx+α-1(1-t)β-xdt~Beta(x+α,β-x+1)


因此，若假定伯努利分布的参数θ的先验概率为Beta分布，那么其后验概率也属于Beta分布，因此Beta分布是伯努利分布的共轭先验分布。

LDA模型中会使用到狄利克雷（Dirichlet）分布和多项式分布（Multinomial Distribution）。由于词分布和主题分布都服从多项式分布，因此LDA模型需要估计此多项式分布的参数。为了估计此参数，LDA模型设它的先验分布为狄利克雷分布，而LDA模型中选用狄利克雷分布作为参数的先验分布的原因就是: 狄利克雷分布是多项式分布的共轭先验概率分布。

【例56】证明: 狄利克雷分布是多项式分布的共轭先验概率分布。

多项式分布:  


P(x1,x2,…,xm; N,α1,α2,…,αm)=N!x1!x2!…xm!αx11αx22…αxmk
N=x1+x2+…+xm，∑αi=1，αi>0


设参数α=(α1,α2,…,αm)满足参数为k的狄利克雷分布，即参数α的先验分布为Dir(α|k)：


p(α; k)=p(α1,α2,…,αm; k1,k2,…,km)=∏mi=1αki-1iB(k)，∑mi=1ki=1


计算参数α的后验概率: 


P(α|x)=P(x|α)P(α)P(x)
∝P(x|α)P(α; k)
=N!x1!x2!…xm!αx11αx22…αxmk∏mi=1αki-1iB(k)
∝αx11αx22…αxmk∏mi=1αki-1i

=∏mi=1αxi+ki-1i


进行归一化处理后P(α|x)=∏mi=1αxi+ki-1iB(x+k)，即参数α的后验概率满足Dir(α|k+x)

综上所述，多项式分布的参数的先验概率为狄利克雷分布时，其后验概率也为狄利克雷分布，因此狄利克雷分布是多项式分布的共轭先验概率分布。

3. EM算法

EM算法是一种迭代算法，用于含有隐含变量的概率模型参数的极大似然估计或极大后验估计。Nature Biotech在他的文章What is the expectation maximization algorithm?［5］中，用了以下投硬币的例子讲述了EM算法的思想，如图53所示。




图53EM算法估计参数



第一步，为硬币A和硬币B的参数θA和θB分别赋值为0.6和0.5，这是根据经验人为设定的值。

第二步（Estep），根据θA和θB的估计值判断第一轮至五轮分别抛的是哪个硬币，例如，对于第一轮抛硬币的结果服从二项式分布: 


P(X=k)=nkpk(1-p)n-k


硬币A抛出5正5反的概率: 


PA(X=5)=1050.65(1-0.6)10-5


硬币B抛出5正5反的概率: 


PB(X=5)=1050.55(1-0.5)10-5


对结果进行归一化后可得，第一次抛硬币抛的是硬币A的概率: 


P(A)=PA(X=5)0PA(X=5)+PB(X=5)≈0.449


抛的是硬币B的概率: 


P(B)=PB(X=5)0PA(X=5)+PB(X=5)≈0.551


将P(A)和P(B)作为权重，对于硬币A: 


0.449×(5H,5T)≈(2.2H,2.2T)


对于硬币B: 


0.551×(5H,5T)≈(2.8H,2.8T)


采用同样的方法对剩下的4轮进行计算。

第三步（Mstep），对于硬币A，将其相应的H系数与T系数分别相加，即为硬币A在抛硬币过程中抛得正面和反面的频数，对于硬币B同理。

已知硬币A和硬币B抛得正面和反面的频数后就可进一步求出新的θA和θB，例如，硬币A抛得的正面的频数（H数相加）: 


2.2+7.2+5.9+1.4+4.5=21.2
2.2+0.8+1.5+2.1+1.9=8.5


θA新的估计值为: 


21.221.2+8.5=0.71


同理,可得θB新的估计值为0.58。

迭代进行第二步和第三步，直至θA和θB收敛，在这个例子中θA和θB收敛于0.8和0.52，即θA和θB最终的估计结果为0.8和0.52。

5.3.2PLSA模型
1. PLSA模型简介

PLSA模型中的相关定义如下。 

（1） P(di)表示文档di被选中的概率。

（2） P(wj|di)表示词wj在文档di中出现的概率，其数值等于词wj在文档di中出现的概率。

（3） P(zk|di)表示主题zk在文档di中出现的概率。

（4） P(wj|zk)表示词wj在主题zk下出现的概率，词wj与主题zk越相关概率值越大。

（5） PLSA是一种词袋模型，不考虑词与词之间出现的顺序。

在PLSA模型中，为文档di抽取一个单词的过程如下。

（1） 根据概率分布P(z|di)，为文档di抽取一个主题zk。

（2） 根据概率分布P(w|zk)，在主题zk下抽取一个词语wj。

重复步骤(1)和(2)，直至生成文档di中所需的N个词。

上述过程每篇文档的主题分布P(z|di)和每个主题下的词分布P(w|zk)即为PLSA模中需要求的参数。




图54PLSA模型生成文档


PLSA模型生成文档的过程可由图54表示。

图54中的d代表文档，w代表词语，z代表主题，M代表文档数量，N代表文档中的单词数量。图54中的d和w为可以人为观测到的数据，而图54中的z不可观测，称之为隐含变量。图54中的方框代表重复，方框右下角的值代表重复的次数。

图54所描述的过程如下。

For i=1，2，3，…，M: 

选择一篇文档; 

For j=1，2，3，…，N: 

根据当前文档的主题分布P(z|di)，为当前文档选择一个主题; 

根据选定的主题下的词分布P(w|zk)，选择一个词; 

将图54中所描述的过程做进一步抽象: 

给定文档di，词语wj出现的概率为


P(wj|di)=∑Kk=1P(wj|zk)P(zk|di)（5.13）


wj和di的联合概率分布为 


P(wj,di)=P(di)P(wj|di)

=P(di)∑Kk=1P(wj|zk)P(zk|di)（5.14）


其中，P(wj,di)和P(di)可以由数据集中直接求得，而P(wj|zk)和P(zk|di)为未知值，是PLSA模型中要估计的参数。


2. PLSA模型的参数估计方法

PLSA模型采用EM算法对参数P(w|zk)和P(z|di)进行估计。EM算法用于含有隐含变量的概率模型参数的极大似然估计或极大后验估计。在PLSA模型中，主题分布即为EM算法中所说的隐含变量。

利用EM算法求解PLSA模型的参数过程如下。

PLAS中需要估计的参数为P(wj|zk)和P(zk|di)，即需要计算得到文档的主题分布和每个主题下的词分布。设主题在文档di上服从参数为θi的多项式分布，其中θi,k表示主题zk在文档di中出现的概率，即


P(zk|di)=θi,k，∑Kk=1θi,k=1（5.15）


设单词在主题zk上服从参数为αk的多项式分布，其中αk,j表示单词wj在主题zk中出现的概率，即


P(wj|zk)=αk,j，∑Kk=1αk,j=1（5.16）


有了上述定义后，模型所需求解的参数用矩阵可以表示为: 


Θ=［θ1,θ2,…,θM］，M为文档数量
A=［α1,α2,…,αK］，K为主题数量



Θ中包含每篇文档的主题分布，A中包含每个主题的词分布。

整个语料库的词分布为: 


P(W|D)=∏Mi=1∏Nj=1P(di,wj)ni,j（5.17）


其中，ni,j表示单词wj在文档di中出现的次数，则文档di中单词的个数为ni=∑wj∈Vni,j

为了计算得到P(W|D)，需得到文档和词语的联合概率分布: 


P(di,wj)=P(di)P(wj|di)

=P(di)∑Kk=1P(wj|zk)P(zk|di)

=P(di)∑Kk=1αk,jθi,k（5.18）


参数Θ和A的对数似然函数为: 


l(Θ,A)=logP(W|D)
=∑Mi=1∑Nj=1ni,jlogP(di,wj)

=∑Mi=1∑Nj=1ni,jlogP(di,wj) 

=∑Mi=1∑Nj=1ni,jlogP(di)∑Kk=1αk,jθi,k 

=∑Mi=1∑Nj=1ni,jlogP(di)+log∑Kk=1αk,jθi,k

=∑Mi=1∑Nj=1ni,jlogP(di)+ni,jlog∑Kk=1αk,jθi,k

=∑Mi=1nilogP(di)+∑Mi=1∑Nj=1ni,jlog∑Kk=1αk,jθi,k（5.19）


由于∑Mi=1nilogP(di)中没有涉及参数Θ和A，因此删去也不会影响似然函数的计算。因此: 


l(Θ,A)=∑Mi=1∑Nj=1ni,jlog∑Kk=1αk,jθi,k（5.20）


由于式（5.20）中存在和的对数，计算较为麻烦，可以使用Jensen不等式对似然函数进行进一步的简化。Jensen不等式可以表述为: 


∑ilog p(x(i); θ)=∑ilog∑z(i)p(x(i),z(i); θ)

=∑ilog∑z(i)Qi(z(i))p(x(i),z(i); θ)Qi(z(i))
≥∑i∑z(i)Qi(z(i))logp(x(i),z(i); θ)Qi(z(i))


其中，


Qi(z(i))=p(x(i),z(i); θ)∑z(i)p(x(i),z(i); θ)


根据Jensen不等式，似然函数可以进一步简化为: 

Qi(z)=αk,jθi,k∑Kk=1αk,jθi,k=P(zk|di,wj)（5.21）


l(Θ,A)=∑Mi=1∑Nj=1ni,jlog∑Kk=1αk,jθi,k
=∑Mi=1∑Nj=1ni,jlog∑Kk=1Qi(z)αk,jθi,kQi(z)
≥∑Mi=1∑Nj=1ni,j∑Kk=1Qi(z)logαk,jθi,kQi(z)
=∑Mi=1∑Nj=1ni,j∑Kk=1P(zk|di,wj)logαk,jθi,kP(zk|di,wj)
=∑Mi=1∑Nj=1ni,j∑Kk=1P(zk|di,wj)(logαk,jθi,k-logP(zk|di,wj))


由于logP(zk|di,wj)中涉及参数Θ和A，且在给定样本后它为定值，因此删去也不会影响似然函数的计算，因此似然函数转化为: 


l(Θ,A)=∑Mi=1∑Nj=1ni,j∑Kk=1P(zk|di,wj)logαk,jθi,k（5.22）


下面采用EM算法来估算参数，首先根据经验为参数Θ、A赋予一个初始的估计值，随后进行EM算法的步骤: Estep和Mstep。

（1） Estep计算隐含变量的后验概率


P(zk|di,wj)=P(zk,di,wj)∑Kl=1P(zl,di,wj)

=P(di)P(zk|di)P(wj|di,zk)∑Kl=1(P(di)P(zl|di)P(wj|di,zl))

=P(zk|di)P(wj|zk)∑Kl=1(P(zl|di)P(wj|zl))

=αk,jθi,k∑Kl=1αl,jθi,l


（2） Mstep实现最大化似然函数，并将Estep求出的后验概率值代入Θ、A的表达式，求出相应参数的解。首先，似然函数为: 


l(Θ,A)=∑Mi=1∑Nj=1ni,j∑Kk=1P(zk|di,wj)logαk,jθi,k


通过最大化似然函数可得: 


θi,k=∑Nj=1ni,jP(zk|di,wj)ni（5.23）
αk,j=∑Mi=1ni,jP(zk|di,wj)∑Nn=1∑Mi=1ni,mP(zk|di,wj)（5.24）



将Estep求得的P(zk|di,wj)的值代入θi,k和αk,j的表达式，可以得到新的θi,k和αk,j值。

迭代Estep和Mstep，直至参数Θ、A的值收敛。收敛后参数Θ、A的值即为模型所求的参数值。

5.3.3LDA模型

LDA（Latent Dirichlet Allocation）是一个生成式概率模型，它与PLSA模型十分相似。对于一篇文档，LDA和PLSA都会估计样本的主题分布和词分布，不同的是PLSA模型认为主题的分布和词的分布是未知的，但值是固定的，也就是说，PLSA模型得到的P(zk|di)和P(wj|zk)对应两个固定的实数值。而LDA模型则认为主题分布和词分布为服从某一分布的随机变量，也就是说，无论P(zk|di)和P(wj|zk)是不是固定的值，但它们的值服从一定的分布。LAD模型可以看作在PLSA模型的基础上融合了贝叶斯框架得到的。

【例57】假设有如下主题“财经”“娱乐”“科技”“体育”“教育”，PLSA模型和LDA模型在处理主题分布上有何不同?


设“财经”“娱乐”“科技”“体育”“教育”这几个主题在文档中出现的概率θ=(θ1,θ2,θ3,θ4,θ5)，文档di的抽样结果满足以θ为参数的多项式分布，即


zi~Mul(θ)


PLSA模型和LDA模型的目标都是获得θ,但是它们分别采用了两种方式获得θ，PLSA模型认为各个主题出现的概率θ虽然未知但都为固定值，比如，经过计算后可以得到主题“财经”“娱乐”“科技”“体育”“教育”在文档中出现的概率θ=(θ1,θ2,θ3,θ4,θ5)=(0.2,0.05,0.4,0.05,0.3)，即每个主题都会对应一个固定的概率值。

LDA模型则认为各个主题出现的概率θ是服从某一分布的随机变量。主题的抽样结果服从以θ为参数的多项式分布，且多项式分布的共轭先验分布为狄利克雷分布，因此设θ服从狄利克雷分布，即θ~Dir(α)。也就是说，在LDA模型中最终不会计算得到θ的具体值，而是计算得到θ的分布。

1. LDA模型简介

LDA将词分布和主题分布看作服从某一分布的随机变量。由于词分布和主题分布本身是服从多项式分布的，而前文中证明过狄利克雷分布是多项式分布的共轭先验分布，因此在求词分布和主题分布的过程中，首先人为设定词分布和主题分布的先验分布为狄利克雷分布，然后根据已知数据计算词分布和主题分布的后验分布，这个后验分布即为LDA模型所要求的内容。

LDA模型抽取一个词语的过程如下。

（1） 从狄利克雷分布Dir(α)中取样生成文档i的主题分布中相应的参数θi。

（2） 主题服从参数为θi的多项式分布，即zi~Multinomial(θi)，从中取样生成文档i的第k个主题zi,k。

（3） 从狄利克雷分布Dir(β)中取样生成主题zi,k的词分布中相应的参数k。

（4） 词语服从参数为k的多项式分布，即wk~Multinomial(k)，从中取样生成单词wk,j。

对于一篇包含有N个词语的文档（N服从泊松分布），重复上述步骤N次直至生成文档所需的N个词。






图55LDA模型生成文档


上述过程与PLSA模型中生成文档的过程相比，LDA在PLSA的基础上，为主题分布和词分布各加了一个狄利克雷先验分布。LDA模型将主题分布和词分布当作先验分布为狄利克雷分布的随机变量，最终LDA模型会基于已知数据，计算主题分布和词分布的后验概率，即参数θ和参数β是LDA模型中需要估计的参数。

LDA模型生成文档的过程可由图55表示。


图55中θ是满足参数为α的狄利克雷分布的随机变量: 


p(θ1,θ2,…,θk; α1,α2,…,αk)=Γ∑ki=1αi∏ki=1Γ(αi)∏ki=1θαi-1i，∑θi=1（5.25）


文档的边缘分布为: 


p(w|α,β)=∫p(θ|α)∏Nn=1∑zkp(zk|θ)p(wn|zk,β)dθ（5.26）


其中，p(w|zk,β)为主题zk相应的词分布，此分布的参数由以β为参数的狄利克雷分布中抽样得到。

语料库中共包含M篇文档，因此语料库的边缘分布为: 


p(D|α,β)=∑Md=1∫p(θd|α)∏Ndn=1∑zdnp(zdn|θd)p(wdn|zdn,β)dθd（5.27）


2. LDA模型参数估计方法

LDA模型采用变分EM算法对参数进行估计，变分EM算法即变分推断和EM算法的结合，其基本思路与PLSA中参数的求解方法类似。

若要根据已有数据推断分布P，当P不容易直接求解时，可以使用变分推断的方法，即寻找容易求解的分布Q，使分布Q不断逼近P，当分布Q足够逼近P时，可以将Q作为P的近似分布。

在LDA模型中，希望找到合适的α和β使对似然函数最大化，并求出隐含变量的条件概率分布。但由于隐含变量α和β之间存在耦合关系，



图56增加了变分参数后的LDA模型



使用EM算法时Estep无法直接求解它们基于条件概率分布的期望，且隐含变量α和β的分布很难直接求得，因此使用变分法，假设所有的隐含变量都是通过各自独立的分布生成的，即去掉隐含变量之间的连线和w节点，并赋予θ、z、φ各自独立分布，γ、η、ρ为相应的变分参数，引入变分参数的目的是增加各个隐含变量之间的独立性，如图56所示。



设模型的联合概率分布为p(x,z)，其中x为观测变量，z为隐含变量，求后验概率p(z|x)。变分EM算法用概率分布Q(z)来近似条件分布概率p(z|x)，之后用KL散度KL(Q(z)‖p(z|x))计算两者之间的相似度，Q(z)和p(z|x)越相似KL散度越小，因此为了让变分分布Q(z)能够近似地表示真实后验p(z|x)，需要让二者的KL散度尽可能小。KL散度的计算方法如下: 


KL(Q(z)‖p(z|x))=∑zQ(z)logQ(z)p(z|x)
=∑zQ(z)logQ(z)-∑zQ(z)logp(z,x)+logp(x)
=logp(x)-{EQ［logp(x,z)］-EQ［logQ(z)］}（5.28）


KL散度的值大于或等于0，当且仅当两个分布一致时KL散度为0，即


logp(x)≥EQ［logp(x,z)］-EQ［logQ(z)］


由于x为观测值，所以在给定样本的情况下，p(x)为定值，因此可以设: 


L=EQ［logp(x,z)］-EQ［logQ(z)］（5.29）


称EQ［logp(x,z)］-EQ［logQ(z)］为证据下界，可以通过最大化证据下界来求取Q(z)。

图57中的w为可观测变量，α和β为参数，θ、φ、z为隐含变量，图中的虚线圆圈对应的γ、η、ρ为变分参数。




图57LDA模型



随机变量θ、z、w、φ的联合概率分布为: 


p(θ,z,w,φ|α,β)=p(θ|α)p(z|θ)p(φ|β)p(w|z,φ)


隐含变量的后验分布为: 

Q(θ,z,φ|γ,η,ρ)=Q(θ|γ)Q(z|η)Q(φ|ρ)


L(γ,η,ρ,α,β)=EQ［p(θ,z,w,φ|α,β)］-EQ［Q(θ,z,φ|γ,η,ρ)］
=EQ［p(θ|α)p(z|θ)p(φ|β)p(w|z,φ)］-
EQ［Q(θ|γ)Q(z|η)Q(φ|ρ)］
=EQ［p(θ|α)］+EQ［p(z|θ)］+EQ［p(φ|β)］+EQ［p(w|z,φ)］-
EQ［Q(θ|γ)］+EQ［Q(z|η)］+EQ［Q(φ|ρ)］（5.30）


EM算法求解过程如下。

（1） Estep: 求解变分参数γ、η、ρ。求解参数γ的过程如下: 首先提取出L(γ,η,ρ,α,β)中含有γ的部分记为L(γ); 对提取出的部分对γ求偏导，即求L(γ)γ; 令偏导等于0，即L(γ)γ=0，求出γ。变分参数 η和 ρ 的求法与上述γ的求法类似，都先从L(γ,η,ρ,α,β)提取相关内容，然后求偏导，最后令偏导的值为零，求出参数值。

（2） Mstep: 求模型的参数α、β。以参数α为例，提取出L(γ,η,ρ,α,β)中含有α的部分


L(αk)=∑Mm=1 logΓ∑Kk=1αk-logΓ(αk)+(αk-1)Ψ(γmk)-Ψ∑Kl=1γml


其中，Ψ是digamma函数，是对数伽马函数的一阶导数。对αk求偏导：


g(α)=L(αk)αk=MΨ∑Ki=1αl-Ψ(αk)+∑Mm=1Ψ(γmk)-Ψ∑Kl=1γml


再对αl求偏导：


H(α)=2L(αk)αkαl=MΨ′∑Ki=1αl-δ(k,l)Ψ′(αk)


对参数α的值进行更新: 


αnew=αold-H(αold)-1g(αold)


参数β的更新过程与α的类似: 


βnew=βold-H(βold)-1g(βold)


迭代Estep和Mstep，直至参数α和β的值收敛。收敛后参数α和β的值即为模型所求的主题分布和词分布的后验分布。

参考文献


［1］Mihalcea R，Tarau P.TextRank:  Bringing order into texts［C］//Conference on Empirical Methods in Natural Language Processing，2004.

［2］Brin S.The anatomy of a largescale hypertextual web search engine［C］//7th World Wide Web Conference.Brisbane，1998.

［3］Blei D M，Ng A，Jordan M I.Latent dirichlet allocation［J］.The Journal of Machine Learning Research，2003(3): 9931022.

［4］Hofmann T，Hofmann T. Unsupervised learning by probabilistic latent semantic analysis［J］.Machine Learning，2001，42(12): 177196.

［5］Do C B，Batzoglou S.What is the expectation maximization algorithm?［J］.Nature Biotechnology，2008，26(8): 897901.