学步园

1
LSA Introduction

LSA(latent
semantic analysis)潜在语义分析，也被称为LSI(latent semantic index)，是Scott Deerwester, Susan T. Dumais等人在1990年提出来的一种新的索引和检索方法。该方法和传统向量空间模型(vector space model)一样使用向量来表示词(terms)和文档(documents)，并通过向量间的关系(如夹角)来判断词及文档间的关系；而不同的是，LSA将词和文档映射到潜在语义空间，从而去除了原始向量空间中的一些“噪音”，提高了信息检索的精确度。

2
传统方法的缺点

传统向量空间模型使用精确的词匹配，即精确匹配用户输入的词与向量空间中存在的词。由于一词多义(polysemy)和一义多词(synonymy)的存在，使得该模型无法提供给用户语义层面的检索。比如用户搜索”automobile”，即汽车，传统向量空间模型仅仅会返回包含”automobile”单词的页面，而实际上包含”car”单词的页面也可能是用户所需要的。

下面是LDA原始Paper^[1]里举的一个例子：

上图是一个Term-Document矩阵，X代表该单词出现在对应的文件里，星号表示该词出现在查询(Query)中，当用户输入查询”IDF
in computer-based information look up” 时，用户是希望查找与信息检索中IDF（文档频率）相关的网页，按照精确词匹配的话，文档2和3分别包含查询中的两个词，因此应该被返回，而文档1不包含任何查询中的词，因此不会被返回。但我们仔细看看会发现，文档1中的access, retrieval, indexing, database这些词都是和查询相似度十分高的，其中retrieval和look up是同义词。显然，从用户的角度看，文档1应该是相关文档，应该被返回。再来看文档2：computer
information theory，虽然包含查询中的一次词information，但文档2和IDF或信息检索无关，不是用户需要的文档，不应该被返回。从以上分析可以看出，在本次检索中，和查询相关的文档1并未返回给用户，而无查询无关的文档2却返回给了用户。这就是同义词和多义词如何导致传统向量空间模型检索精确度的下降。

3
LSA如何解决这些问题

LSA潜在语义分析的目的，就是要找出词(terms)在文档和查询中真正的含义，也就是潜在语义，从而解决上节所描述的问题。具体说来就是对一个大型的文档集合使用一个合理的维度建模，并将词和文档都表示到该空间，比如有2000个文档，包含7000个索引词，LSA使用一个维度为100的向量空间将文档和词表示到该空间，进而在该空间进行信息检索。而将文档表示到此空间的过程就是SVD奇异值分解和降维的过程。降维是LSA分析中最重要的一步，通过降维，去除了文档中的“噪音”，也就是无关信息（比如词的误用或不相关的词偶尔出现在一起），语义结构逐渐呈现。相比传统向量空间，潜在语义空间的维度更小，语义关系更明确。

4 SVD分解^[2]

^{SVD分解作为掌握LSA的基础知识，我单独把它作为一篇文章，可以在这里找到。}

5
LSA技术细节^[1][3]

本节主要讨论LSA技术细节的理论部分，具体代码层面分析和实践在第7节讨论。

LSA的步骤如下：

1.
分析文档集合，建立Term-Document矩阵。

2.
对Term-Document矩阵进行奇异值分解。

3.
对SVD分解后的矩阵进行降维，也就是奇异值分解一节所提到的低阶近似。

4.
使用降维后的矩阵构建潜在语义空间，或重建Term-Document矩阵。

下面是Introduction
to Latent Semantic Analysis里面的一个例子，描述了完整的LSA步骤，例子后面有我的补充：

假设文档集合如下：

原始的Term-Document矩阵如下：

对其进行奇异值分解：

然后对分解后的矩阵降维，这里保留{S}的最大两个奇异值，相应的{W}{P}矩阵如图，注意{P}在公式中需要转置。

到了这一步后，我们有两种处理方法，论文Introduction
to Latent Semantic Analysis是将降维后的三个矩阵再乘起来，重新构建了{X}矩阵如下：

观察{X}矩阵和{X^{^}}矩阵可以发现：

{X}中human-C2值为0，因为C2中并不包含human单词，但是{X^{^}}中human-C2为0.40，表明human和C2有一定的关系，为什么呢？因为C2：”A
survey of user opinion of computer system response time”中包含user单词，和human是近似词，因此human-C2的值被提高了。同理还可以分析其他在{X^{^}}中数值改变了的词。

以上分析方法清晰的把LSA的效果显示出来了，也就是在{X^{^}}中呈现出了潜在语义，然后希望能创建潜在语义空间，并在该空间中检索信息。这里以比较两个单词为例：

设奇异值分解形式为：X
= T S D^T,T代表term，s代表single
value矩阵，D代表Document，D^T表示D的转置。X的两个行向量点乘的值代表了两个词在文档中共同出现的程度。比如T1在D1中出现10词，T2在D1中出现5次，T3在D1中出现0词，那么只考虑在D1维度上的值，T1(dot)T2=50，T1(dot)T2=0，显然T1与T2更相似，T1与T3就不那么相似。那么用矩阵X(dot)X^T就可以求出所有词与词的相似程度。而由奇异值分解的公式的：

X(dot)X^T =
T(dot)S²(dot)T^T =
TS(dot)(TS)^T

上面公式表明了，我们想求X(dot)X^T的(i,j)个元素时，可以点乘TS矩阵的第i和j列来表示。因此我们可以把TS矩阵的行看作是term的坐标，这个坐标就是潜在语义空间的坐标。同理我们还可以推出X^T(dot)X
= D(dot)S²(dot)D^T，从而DS的行表示了文档的坐标。

这样，我们就获得了所有文档和单词在潜在语义空间的坐标，这时我们就可以通过向量间的夹角来判断两个对象的相似程度，方法和传统向量空间模型相同。接下来主要讨论下检索文本的步骤。

用户输入的检索语句被称为伪文本，因为它也是有多个词汇构成，和文本相似。所以很自然的想法就是将该伪文本转换为文档坐标，然后通过比较该伪文档与每个文档的空间夹角，检索出该伪文本的相关文档。设X_q表示伪文本的列向量，其中该列代表文档集合的索引词，该列的值代表伪文本中该索引词出现的次数。比如一个文档集合有索引词{T1,T2,T3}，伪文本为t1,t3,t2,t1，则X_q={2,1,1}。获得X_q后，通过公式

D_q =
X_q^T T
S^-1

计算伪文档的文档坐标。其中T和S分别代表奇异分解中得到的矩阵(S
= T S D^T).注意上面的公式中S^-1代表S的逆矩阵。

D_q计算出来后，就可以迭代比较D_q和文档集合中所有所有文档，计算两者个cosine夹角

6
LSA实践

本节主要讨论LSA的实现，编程语言使用C++，环境Linux
gcc，使用了GNU Scientific Library^[5]。本节代码可以在http://code.google.com/p/lsa-lda/找到。

1.
创建Term-Document矩阵

LSA是基于向量空间模型的，因此首先需要创建一个M
x N的Term-Document矩阵，其中行表示每一个词，列表示每一个文档。而矩阵的值等于相应词的TF*IDF值。待检索的文档集合放在程序根目录下的corpus文件夹，每一个文档一个文件。

首先需要创建语料的单词列表，作为T-D矩阵的列向量，每一个单词对应一个id。

[code=cpp]

CreateVectorSpace.cc

Function
int CreateKeyWordMap()

//
循环读入每个文档

while((ent=readdir(currentDir))!=NULL)

<