Latent Semantic Analysis(LSA/ LSI)算法简介

1. 传统向量空间模型的缺陷

向量空间模型是信息检索中最常用的检索方法,其检索过程是,将文档集D中的所有文档和查询都表示成以单词为特征的向量,特征值为每个单词的TF-IDF 值,然后使用向量空间模型(亦即计算查询q的向量和每个文档di的向量之间的相似度)来衡量文档和查询之间的相似度,从而得到和给定查询最相关的文档。

向量空间模型简单的基于单词的出现与否以及TF-IDF等信息来进行检索,但是“说了或者写了哪些单词”和“真正想表达的意思”之间有很大的区别,其中两 个重要的阻碍是单词的多义性(polysems)和同义性(synonymys)。多义性指的是一个单词可能有多个意思,比如Apple,既可以指水果苹 果,也可以指苹果公司;而同义性指的是多个不同的词可能表示同样的意思,比如search和find。

同义词和多义词的存在使得单纯基于单词的检索方法(比如向量空间模型等)的检索精度受到很大影响。下面举例说明:

假设用户的查询为Q="IDF in computer-based information look-up"

存在三篇文档Doc 1,Doc 2,Doc 3,其向量表示如下:

Access Document Retrieval Information Theory Database Indexing Computer Relevance Match
Doc 1     1       1      1      1     1       R
Doc 2       1 x    1     1 x   M
Doc 3      1       1 x     1 x       R   M

其中Table(i,j)=1表示文档i包含词语j。Table(i,j)=x表示该词语在查询Q中出现。Relevance如果为R表示该文档实际上和查询Q相关,Match为M表示根据基于单词的检索方法判断的文档和查询的相关性。

通过观察查询,我们知道用户实际上需要的是和“信息检索”相关的文档,文档1是和信息检索相关的,但是因为不包含查询Q中的词语,所以没有被检索到。实际 上该文档包含的词语“retrieval”和查询Q中的“look-up”是同义词,基于单词的检索方法无法识别同义词,降低了检索的性能。而文档2虽然 包含了查询中的"information"和"computer"两个词语,但是实际上该篇文档讲的是“信息论”(Information Theory),但是基于单词的检索方法无法识别多义词,所以把这篇实际不相关的文档标记为Match。

总而言之,在基于单词的检索方法中,同义词会降低检索算法的召回率(Recall),而多义词的存在会降低检索系统的准确率(Precision)。

2. Latent Semantic Analysis (Latent Semantic Indexing)

我们希望找到一种模型,能够捕获到单词之间的相关性。如果两个单词之间有很强的相关性,那么当一个单词出现时,往往意味着另一个单词也应该出现(同义 词);反之,如果查询语句或者文档中的某个单词和其他单词的相关性都不大,那么这个词很可能表示的是另外一个意思(比如在讨论互联网的文章中,Apple 更可能指的是Apple公司,而不是水果)  。

LSA(LSI)使用SVD来对单词-文档矩阵进行分解。SVD可以看作是从单词-文档矩阵中发现不相关的索引变量(因子),将原来的数据映射到语义空间内。在单词-文档矩阵中不相似的两个文档,可能在语义空间内比较相似。

SVD,亦即奇异值分解,是对矩阵进行分解的一种方法,一个t*d维的矩阵(单词-文档矩阵)X,可以分解为T*S*DT, 其中T为t*m维矩阵,T中的每一列称为左奇异向量(left singular bector),S为m*m维对角矩阵,每个值称为奇异值(singular value),D为d*m维矩阵,D中的每一列称为右奇异向量。在对单词文档矩阵X做SVD分解之后,我们只保存S中最大的K个奇异值,以及T和D中对应 的K个奇异向量,K个奇异值构成新的对角矩阵S’,K个左奇异向量和右奇异向量构成新的矩阵T’和D’:X’=T’*S’*D’T形成了一个新的t*d矩阵。

假设索引的文档的集合如下:

Term-Document矩阵为:

 1 [[ 1.  0.  0.  1.  0.  0.  0.  0.  0.]
 2  [ 1.  0.  1.  0.  0.  0.  0.  0.  0.]
 3  [ 1.  1.  0.  0.  0.  0.  0.  0.  0.]
 4  [ 0.  1.  1.  0.  1.  0.  0.  0.  0.]
 5  [ 0.  1.  1.  2.  0.  0.  0.  0.  0.]
 6  [ 0.  1.  0.  0.  1.  0.  0.  0.  0.]
 7  [ 0.  1.  0.  0.  1.  0.  0.  0.  0.]
 8  [ 0.  0.  1.  1.  0.  0.  0.  0.  0.]
 9  [ 0.  1.  0.  0.  0.  0.  0.  0.  1.]
10  [ 0.  0.  0.  0.  0.  1.  1.  1.  0.]
11  [ 0.  0.  0.  0.  0.  0.  1.  1.  1.]
12  [ 0.  0.  0.  0.  0.  0.  0.  1.  1.]]

对其进行分解后得到X=T*S*DT。其中T为:

 1 [-0.22 -0.11  0.29 -0.41 -0.11 -0.34 -0.52  0.06  0.41]
 2 [-0.2  -0.07  0.14 -0.55  0.28  0.5   0.07  0.01  0.11]
 3 [-0.24  0.04 -0.16 -0.59 -0.11 -0.25  0.3  -0.06 -0.49]
 4 [-0.4   0.06 -0.34  0.1   0.33  0.38 -0.    0.   -0.01]
 5 [-0.64 -0.17  0.36  0.33 -0.16 -0.21  0.17 -0.03 -0.27]
 6 [-0.27  0.11 -0.43  0.07  0.08 -0.17 -0.28  0.02  0.05]
 7 [-0.27  0.11 -0.43  0.07  0.08 -0.17 -0.28  0.02  0.05]
 8 [-0.3  -0.14  0.33  0.19  0.11  0.27 -0.03  0.02  0.17]
 9 [-0.21  0.27 -0.18 -0.03 -0.54  0.08  0.47  0.04  0.58]
10 [-0.01  0.49  0.23  0.02  0.59 -0.39  0.29 -0.25  0.23]
11 [-0.04  0.62  0.22  0.   -0.07  0.11 -0.16  0.68 -0.23]
12 [-0.03  0.45  0.14 -0.01 -0.3   0.28 -0.34 -0.68 -0.18]

DT

1 [-0.2  -0.61 -0.46 -0.54 -0.28 -0.   -0.01 -0.02 -0.08]
2 [-0.06  0.17 -0.13 -0.23  0.11  0.19  0.44  0.62  0.53]
3 [ 0.11 -0.5   0.21  0.57 -0.51  0.1   0.19  0.25  0.08]
4 [-0.95 -0.03  0.04  0.27  0.15  0.02  0.02  0.01 -0.02]
5 [ 0.05 -0.21  0.38 -0.21  0.33  0.39  0.35  0.15 -0.6 ]
6 [-0.08 -0.26  0.72 -0.37  0.03 -0.3  -0.21  0.    0.36]
7 [-0.18  0.43  0.24 -0.26 -0.67  0.34  0.15 -0.25 -0.04]
8 [ 0.01 -0.05 -0.01  0.02  0.06 -0.45  0.76 -0.45  0.07]
9 [ 0.06 -0.24 -0.02  0.08  0.26  0.62 -0.02 -0.52  0.45]
复制代码

Sigma为

1 [ 3.34
2           2.54   
3                     2.35  
4                             1.64     
5                                      1.50    
6                                                1.31  
7                                                         0.85
8                                                                    0.56  
9                                                                              0.36]

我们只保留最大的2个奇异值和其对应的奇异向量,得到的T’为

 1 [-0.22 -0.11]
 2 [-0.2  -0.07]
 3 [-0.24  0.04]
 4 [-0.4   0.06]
 5 [-0.64 -0.17]
 6 [-0.27  0.11]
 7 [-0.27  0.11]
 8 [-0.3  -0.14]
 9 [-0.21  0.27]
10 [-0.01  0.49]
11 [-0.04  0.62]
12 [-0.03  0.45]

D’T

1 [-0.2  -0.61 -0.46 -0.54 -0.28 -0.   -0.01 -0.02 -0.08]
2 [-0.06  0.17 -0.13 -0.23  0.11  0.19  0.44  0.62  0.53]

Sigma’为

1 [[ 3.34        0.    ]
2  [ 0.          2.54  ]]

还原后的X’为

 1 [ 0.16  0.4   0.38  0.47  0.18 -0.05 -0.12 -0.16 -0.09]
 2 [ 0.14  0.37  0.33  0.4   0.16 -0.03 -0.07 -0.1  -0.04]
 3 [ 0.15  0.51  0.36  0.41  0.24  0.02  0.06  0.09  0.12]
 4 [ 0.26  0.84  0.61  0.7   0.39  0.03  0.08  0.12  0.19]
 5 [ 0.45  1.23  1.05  1.27  0.56 -0.07 -0.15 -0.21 -0.05]
 6 [ 0.16  0.58  0.38  0.42  0.28  0.06  0.13  0.19  0.22]
 7 [ 0.16  0.58  0.38  0.42  0.28  0.06  0.13  0.19  0.22]
 8 [ 0.22  0.55  0.51  0.63  0.24 -0.07 -0.14 -0.2  -0.11]
 9 [ 0.1   0.53  0.23  0.21  0.27  0.14  0.31  0.44  0.42]
10 [-0.06  0.23 -0.14 -0.27  0.14  0.24  0.55  0.77  0.66]
11 [-0.06  0.34 -0.15 -0.3   0.2   0.31  0.69  0.98  0.85]
12 [-0.04  0.25 -0.1  -0.21  0.15  0.22  0.5   0.71  0.62]

还原后的X’与X差别很大,这是因为我们认为之前X存在很大的噪音,X’是对X处理过同义词和多义词后的结果。

查询时,对与每个给定的查询,我们根据这个查询中包含的单词(Xq)构造一个伪文档:Dq=XqTS-1,然后该伪文档和D’中的每一行计算相似度(余弦相似度)来得到和给定查询最相似的文档。

参考文献:

[1]  Indexing By Latent Semantic Analysis. Scott Deerwester, Susan T. Dumais, George W.Furnas, Thomas K.Landauer, Richard Harshman.

[2]  Latent Semantic Analysis Note. Zhou Li.

您可以选择一种方式赞助本站

支付宝转账赞助

支付宝扫一扫赞助