Latent Semantic Analysis and Extension

潜语义分析(LSA,Latent Semantic Analysis; 有时也称作,LSI, Latent Semantic Indexing)是文本建模和分析中常用的模型。LSA是Deerwester, Dumais等在1990年提出的,它引入了矩阵计算中的奇异值分解(SVD, Singular Value Decomposition)和低秩矩阵近似(Low Rank Approximation),对文档集的表示矩阵进行分析,将文档映射到潜语义空间,达到文档潜语义表示和降维的目的。
1.文档的表示
文档表示是文本分析中的基本问题,它可以将人可读文档转化为机器可读数据结构。常用的文本表示方法有向量空间模型(VSM, Vector Space Model),它是一种简单且有效的文档表示方法,广泛的应用于信息检索系统中。
向量空间模型将文档表示为向量,向量的每个维度代表词表中的一个词,对应的值代表的是该词在文档中出现的(加权)次数。
向量空间模型可以很方便的计算出文档与文档之间,文档与查询(query)之间的相似度,度量一般采用cosine相似度(cosine非严格的距离度量方式,其不满足距离度量的三个要素—非负、对称、三角不等式)。


其中, 是文档的空间向量模型表示, , 为词 的权重(可以是Boolean值,也可以是TF-IDF等值), 相似度在 之间。
VSM模型简单,计算方便,可以方便的计算出文档的相关系数( 等),但是VSM模型认为单词之间是独立的,只是简单的表示了文档,并没有引入语法,上下文环境或者语义信息;向量维度为词表大小,当词表较大时,向量会很稀疏;在文档匹配时,长文档的相似度值会过小。
2.SVD
奇异值分解是将矩阵分解成三个特定矩阵——正交矩阵 ,对角矩阵 ,正交矩阵的转置 :


其中, 中的列向量是矩阵 的正交特征向量, 中的列向量是矩阵 , 的正交特征向量, 中对角元素为特征值的平方根降序排列
3.Low Rank Approximation
低秩矩阵近似是一个最小化问题,它是在满足近似矩阵的秩的约束下,代价函数(cost function)最小,它的代价函数是原始矩阵(数据矩阵)和近似矩阵之间的差值。


其中, 表示原始矩阵(数据矩阵), 表示近似矩阵, 表示矩阵D的Frobenius范数。


其中, 的共轭转置,当 时, 。低秩矩阵近似可以通过奇异值分解来得到解


4.LSA
前文提到LSA是引入了SVD和低秩矩阵近似进行文本分析。在LSA中,模型通过对文档集表示矩阵(文档-词矩阵)进行奇异值分解,并低秩矩阵近似对文档集表示矩阵进行近似,得到K维空间中的文档-潜语义、潜语义-词的表示矩阵。


其中, 为对角方阵, 为文档-潜语义表示矩阵, 为潜语义-词表示矩阵。
1-1图1
5.Extension
LSI局限于 正交性假设,SVD的计算时间为 ,其中 为文档集表示矩阵的行数, 为数据矩阵的列数。LSI在处理超大规模文档时,很难高效的求解,模型的可扩展性低。在对文档集表示矩阵进行SVD时,得到的表示无法保证稀疏化,这样得到的结果(文档topic表示)会很稠密。
1-2图2
5.1 RLSI(Regularized LSI)
在LSI的基础上,RLSI[Wang etc., 2013]对文档的主题表示和主题-词之间关系上加入稀疏化控制,同时去除LSI中 正交性假设。按照训练环境,RLSI分为batch-RLSI和online-RLSI,Batch-LSI其定义如下:


其中, 表示第n篇文档的表示向量, 是对 近似表示, 为主题-词的表示矩阵, 为第n篇文档的主题表示向量, 控制 的稀疏程度,当 越大, 越稀疏; 控制 的收缩(Shrinkage)程度,当 越大, 的收缩程度越大。
1-3图-3
上式对于 为非凸问题,但是对于单一的 ,为凸问题。如此,求解上式只需要给定一个变量( ),求解另一变量。
1-4图-4
(1)给定 ,更新


,如此,式(7)可以表示为:


式(8)可以分解成M个独立的优化问题,每个问题形式为:


式(9)是一个 -正则的最小二乘问题,求解方法有多种,比如内点法(Interior Point Method),软阈值的坐标下降(Coordination Descent with Soft-thresholding),Lars-Lasso方法等。以软阈值梯度下降法为例,每次迭代过程中,选取 的一个元素 ,固定剩余的元素,求解式(9)。将式(9)包含 的项单独列出,记为


其中, 为对应矩阵 。上式对应的解为如下形式:


其中,

为合页函数(hinge function)。
1-5图-5
(2)给定 ,更新
类似问题(1),更新 的过程也可以分解成 个独立的优化问题。


式(12)为 -正则的最小二乘问题(统计上,称为岭回归(Ridge Regression)),解为:


1-6图-6
5.2 Online-RLSI
在处理流式文档数据时,文档是按序一一到达,且文档中包含的主题是不断变化的。Online-RLSI可以有效的跟踪话题演化(Topic tracking)。类似式(6),目标方程为:


式(14)中第一项是 个文档的“经验损失(Empirical Loss)”,第二项控制模型复杂度(L1-正则)。
在online-RLSI中,文档是相互独立的。当文档 到达时,online-RLSI将文档投射到主题空间,然后更新主题-词矩阵。
Online-RLSI通过式(15)得到文档 在主题空间的投射,


其中, 为上次迭代得到的主题-词矩阵。
可以通过求解如下问题得到,


类比于batch-RLSI,式(15)是式(12)的近似,式(16)是式(14)的近似。
(1)文档投影
文档投影问题是一个L2正则的最小二乘问题,其解为


(2)更新主题-词矩阵
式(16)等同于下式,


其中, 。类似于式(7)的求解,可以将式(18)分解为 个子问题,


,式(19)的解可以通过图2中所示算法求解。在online-RLSI中,



1-7图-7
6.Conclusion
LSI模型(扩展模型)相对后续介绍的pLSA,LDA,DP等比较简单,仅用常用矩阵分解方式对文档-词矩阵进行分析,同时LSI模型没有对应的概率生成过程描述,无法用概率图模型表示。
7.参考文献
[1].Dumais, S. T. (2004). Latent semantic analysis. Annual review of information science and technology, 38(1), 188-230.
[2].Wikipedia. Latent Semantic Analysis, http://en.wikipedia.org/wiki/Latent_s
emantic_indexing.
[3].Lee, D. D., & Seung, H. S. (2001). Algorithms for non-negative matrix factorization. In Advances in neural information processing systems (pp. 556-562).
[4].Hoyer, P. O. (2004). Non-negative matrix factorization with sparseness constraints. The Journal of Machine Learning Research, 5, 1457-1469.
[5].Strang, G. (2003). Introduction to linear algebra. Cambridge Publication.
[6].Wikipedia. Non-negative Matrix Factorization. http://en.wikipedia.org/wiki/Non-negative_matrix_factorization
[7].Wikipedia. Singular Value Decomposition. http://en.wikipedia.org/wiki/Singular_
value_decomposition
[8].Quan Wang, Jun Xu, Hang Li, and Nick Craswell. (2013). Regularized Latent Semantic Indexing: A New Approach to Large-Scale Topic Modeling. ACM Trans. Inf. Syst. 31

转载请注明:《 Latent Semantic Analysis and Extension | 我爱计算机

Leave a Reply

Your email address will not be published. Required fields are marked *