Computational-Linguistics-11

自然语言处理中的话题模型常宝宝北京大学计算语言学研究所[e-mail]概要LatentSemanticAnalysis(LSA)ProbabilisticTopicModelProbabilisticLatentSemanticAnalysis(pLSA)LatentDirichletAllocation(LDA)LatentSemanticAnalysisLatentSemanticAnalysis(LSA)一般译作潜在语义分析，有时候也称作LatentSemanticIndexing(LSI，潜在语义索引)LSA的提出者是ScottDeerwester、SusanT.Dumais等人，发表的时间是1990年LSA的基础是向量空间模型(vectorspacemodel)LSA的基础理念是，基于词项在文档集合中的共现特性，表达词项的潜在意义LSA将文档表示映射到潜在语义空间，从而更好地衡量文本之间的相关性LSA也常被视作一种维数缩减技术，因为它把文档从高维的词项空间映射到低维潜在语义空间，去除了噪音LatentSemanticAnalysis在向量空间模型中，一篇文档(document)可以表示为一个向量，其中每个分量对应一个词项(term)，分量的值是词项在文档中出现的频率(词项频率，termfrequency)或者其它改进后的词项权值。𝑑=𝑡𝑓𝑡1,𝑡𝑓𝑡2,…,𝑡𝑓𝑡𝑀T因此𝑁篇文档组成的集合可以表示称为一个𝑀×𝑁的矩阵𝐶，称作词项-文档矩阵(term-documentmatrix)，矩阵的行对应着词项，矩阵的列对应着文档。LatentSemanticAnalysis向量空间模型通过计算文档向量间的相似度来衡量两个文档之间的相关性，常用的相似度为(夹角)余弦相似度𝑠𝑖𝑚𝑑1,𝑑2=𝑑1∙𝑑2𝑑1×|𝑑2|例如:𝑠𝑖𝑚𝑑2,𝑑3=0×1+1×0+1×0+0×0+0×0𝑑2×|𝑑3|=0文档𝑑2和文档𝑑3没有相关性是否合理？建立在词项空间上文档表示没有考虑到同义词关系LatentSemanticAnalysisLSA的数学基础是线性代数线性相关、线性无关若n个向量是线性相关的，则其中的向量可以写成其它向量的线性组合。如果是线性无关的，则其中的向量不能写成其他向量的线性组合正交向量(垂直向量)若两个向量的內积为0，则称这两个向量是正交的矩阵的秩：矩阵中线性无关的行(列)的数目，有：𝑟𝑎𝑛𝑘𝐶≤min⁡(𝑀,𝑁)特征值和特征向量令𝐶为𝑀×𝑀的矩阵，𝑥为𝑀维非0向量，若有：𝐶𝑥=𝜆𝑥则称𝜆是方阵𝐶的特征值，𝑥称作方阵𝐶的特征向量LatentSemanticAnalysis𝑀阶方阵的特征值的个数最多为𝑟𝑎𝑛𝑘(𝐶)主特征向量：最大特征值所对应的特征向量特征方程𝐶−𝜆𝐼𝑀𝑥=0求解方程𝐶−𝜆𝐼𝑀=0的解，可得到方阵的所有特征值(一元𝑀次方程，解可以是复数)例：𝑆=30000200001特征值：𝜆1=30、𝜆2=20、𝜆3=1特征向量：𝑥1=100、𝑥2=010、𝑥3=001LatentSemanticAnalysis令𝑆是实对称矩阵，则其所有特征值均为实数，且不同特征值所对应的特征向量是正交的矩阵对角化定理:若𝑆是𝑀×𝑀的实值方阵且拥有𝑀个线性无关的特征向量，则𝑆可分解如下：𝑆=𝑈Λ𝑈−1其中，𝑈的列是𝑆的特征向量，Λ是对角矩阵，其对角线上的元素是𝑆的特征值，且按照对角线降序排列𝜆1𝜆2…𝜆𝑀,𝜆𝑖≥𝜆𝑖+1若特征值均不相同，则这样的分解是唯一的LatentSemanticAnalysis对称对角化定理:若𝑆是𝑀×𝑀的实值对称方阵，且拥有𝑀个线性无关的特征向量，则𝑆可分解如下：𝑆=𝑄Λ𝑄T其中，𝑄的列是𝑆的互相正交且归一化的特征向量(正交单位向量)，Λ是对角矩阵，其对角线上的元素是𝑆的特征值，且按照对角线降序排列例：2112=11−11×3001×1/2−1/21/21/22112=1/21/2−1/21/2×3001×1/2−1/21/21/2LatentSemanticAnalysis词项-文档矩阵𝐶不是对称矩阵矩阵𝐶𝐶T、𝐶T𝐶是实值对称矩阵矩阵𝐶𝐶T的含义是任意两个词项的相似度元素代表着两个词项在文档中的共现次数矩阵𝐶T𝐶的含义是任意两个文档的相似度元素代表着两个文档中共同词项的数量按照对称对角化定理，𝐶𝐶T、𝐶T𝐶可以分解令𝐶𝐶T的正交单位特征向量组成的矩阵为𝑈，则𝑈是𝑀×𝑀的矩阵令𝐶T𝐶的正交单位特征向量组成的矩阵为𝑉，则𝑉是𝑁×𝑁的矩阵LatentSemanticAnalysis奇异值分解定理若𝑀×𝑁的矩阵𝐶的秩是𝑟，那么可对𝐶进行如下的奇异值分解(SingularValueDecomposition,SVD)：𝐶=𝑈Σ𝑉𝑇其中𝑈和𝑉的含义如前述，且：(1)𝐶𝐶𝑇的特征值为𝜆1,𝜆2,…,𝜆𝑟，等于𝐶𝑇𝐶的特征值(2)对于1≤𝑖≤𝑟，令𝜆𝑖≥𝜆𝑖+1，𝜎𝑖=𝜆𝑖，则对于1≤𝑖≤𝑟,有Σ𝑖𝑖=𝜎𝑖，此外Σ中的其他元素均为0𝜎𝑖被称作矩阵𝐶的奇异值依据SVD定理，有𝐶𝐶T=𝑈Σ𝑉T𝑉ΣT𝑈T=𝑈ΣΣT𝑈T⁡𝐶T𝐶=𝑉ΣT𝑈T𝑈Σ𝑉T=𝑉ΣTΣ𝑉TLatentSemanticAnalysisSVD图示(𝑀𝑁及𝑀𝑁)SVD截断表示LatentSemanticAnalysis例:110110=230161216−12×3001×1/2−1/21/21/2低秩逼近(low-rankapproximation):寻求矩阵𝐶的近似矩阵𝐶𝑘，且矩阵𝐶𝑘的秩为𝑘，并且𝑘≤𝑟所谓𝐶𝑘逼近𝐶，指的是二者的差矩阵的F范数最小，即下式的值最小，若用𝐶𝑘代替𝐶误差最小:𝐶−𝐶𝑘𝐹=𝐶𝑖𝑗−𝐶𝑘𝑖𝑗2𝑁𝑗=1𝑀𝑖=1LatentSemanticAnalysisSVD可以用来解决低秩逼近问题，给定秩𝑟的矩阵𝐶(1)构造𝐶的SVD分解，有𝐶=𝑈Σ𝑉T(2)将Σ中对角线上𝑟−𝑘个最小的奇异值置为0，得到Σ𝑘(3)计算𝐶𝑘=𝑈Σ𝑘𝑉T，将𝐶𝑘作为𝐶的近似矩阵此时，逼近的误差为:𝜎𝑖2𝑟𝑖=𝑘+1LatentSemanticAnalysisLSA的核心在于将秩𝑟的词项-文档矩阵𝐶进行SVD分解，并寻求词项-文档矩阵的𝑘秩逼近𝐶𝑘在实际问题中：𝑟≈min(𝑀,𝑁)，𝑟通常很大，此时可以选择一个较小的𝑘，即𝑘≪𝑟.此时我们可以说，在进行潜在语义分析之前，文档被隐含表示成𝑟维空间中的向量，而在潜在语义分析之后，文档被表示为𝑘维空间中的向量，也就是潜在语义空间中的向量，向量的维数缩减为𝑘维维数𝑘可以被解释为隐含在文档集合中的话题数量，因此LSA可以被视作一种话题模型LatentSemanticAnalysis对如下的词项-文档矩阵进行潜在语义分析矩阵𝑈(SVD词项矩阵)𝐶=𝑈Σ𝑉TLatentSemanticAnalysis矩阵Σ(奇异值矩阵)矩阵𝑉T(SVD文档矩阵)LatentSemanticAnalysis计算词项-文档矩阵的𝑘秩逼近(令𝑘=2)得到如下的𝐶2(在2维话题空间中的词项-文档矩阵)LatentSemanticAnalysis在原始词项空间中𝑠𝑖𝑚𝑑2,𝑑3=0×1+1×0+1×0+0×0+0×0𝑑2×|𝑑3|=0在潜在语义空间中𝑠𝑖𝑚𝑑2,𝑑3=0.52×0.28+0.36×0.16+0.72×0.36+0.12×0.20+−0.39×(−0.08)𝑑2×|𝑑3|=0.939119𝑑2和𝑑3在潜在语义空间中具有很大相似性，这与我们的直观感觉相符，尽管二者中没有出现重叠的词项，但boat和ship是同义词，二者话题是相近的LatentSemanticAnalysis在原始词项空间中，存在下面的问题(1)词项多义(polysemy)现象引起文档相似度被高估𝑠𝑖𝑚𝑡𝑟𝑢𝑒𝑑1,𝑑2𝑠𝑖𝑚(𝑑1,𝑑2)(2)词项同义(Synonymy)现象引起文档相似度被低估𝑠𝑖𝑚𝑡𝑟𝑢𝑒𝑑1,𝑑2𝑠𝑖𝑚(𝑑1,𝑑2)LSA通过空间映射，将话题接近的文档映射到相近的位置存在SVD标准算法(如Lanczos算法)，复杂度较高LSA缺陷:𝐶𝑘中的元素缺直观解释，甚至可以是负值𝑘的设定是经验性的非统计模型，缺统计学基础概要LatentSemanticAnalysis(LSA)ProbabilisticTopicModelProbabilisticLatentSemanticAnalysis(pLSA)LatentDirichletAllocation(LDA)ProbabilisticTopicModelLSA要点:(1)基于词(项)-文档矩阵归纳语义信息(2)基于维数缩减归纳语义信息(3)文档和词(项)被视作欧式空间中的点进行计算概率话题模型，(3)不成立概率话题模型是生成式模型(generativemodel)概率模型是混合模型(mixturemodel)混合模型中，分布表示为若干部件分布按照一定的比例进行组合典型的概率话题模型ProbabilisticLatentSemanticAnalysisLatentDirichletAllocationProbabilisticTopicModel概率话题模型中(1)文档是关于话题的分布,不同文档拥有不同的话题比例𝑝(𝑧)(2)话题是定义在词表上的概率分布𝑝(𝑤|𝑧)，不同的话题是定义在词表上的不同分布，与LSA不同，话题有着直观的物理解释话题模型是生成模型,文档是话题模型规定的概率过程的产物(1)对每一个文档，首先选择一个话题分布𝑝(𝑧)(2)对文档中的每一个词位，按照话题分布𝑝(𝑧)选择一个话题(3)按照话题-词分布𝑝(𝑤|𝑧)选择一个词在话题模型中，文档中每个词都对应着一个隐含的话题，这些隐含的话题可以通过统计推断的技术从大量的文档集合中提取得到ProbabilisticTopicModel话题表示及提取示例(MarkSteyvers)基于TASAcorpus(37000textpassagesfromeducationalmaterial)共提取300个话题ProbabilisticTopicModel话题模型中的文档与话题ProbabilisticTopicModel基于话题生成文档(generativeprocess)TOPIC-1moneyTOPIC-2riverDOC-1TOPIC-11TOPIC-20DOC-2TOPIC-10.5TOPIC-20.5DOC-3TOPIC-10TOPIC-21ProbabilisticTopicModel基于文档推断模型(modelinference)寻求生成文档的最佳模型每个文档中的话题比例?每个话题中的词的分布?生成每个词的隐含话题?ProbabilisticTopicModel给定文档，令文档中的话题分布为𝑝(𝑧)，话题-词分布为𝑝(𝑤|𝑧)，则有文档中第𝑖个词的概率为：𝑝𝑤𝑖=𝑝𝑤𝑖𝑧𝑖=𝑗𝑝(𝑧𝑗=𝑗)𝑇𝑗=1每个文档均可以视作一个关于词的概率分布，从而表示为一个𝑀维向量，向量中的元素代表某词在该文档中的出现概率，若有𝐷个文档，则文档可以表示为一个𝑀×𝐷的矩阵𝐶因为每个话题也是关于词的概率分布，因此每个话题也可以表示为一个𝑀维的向量，所有𝑇个话题也可以表示为一个𝑀×𝑇的矩阵Φ按照话题模型，每个文