Latent Semantic Indexing

线性代数回顾

矩阵分解（matrix decomposition）：将方阵分解成多个矩阵因子，并且这几个矩阵因子都可以从方阵的特征向量导出。

矩阵对角化定理：令S为MxM的实方阵，并且他有M个线性无关的特征向量，那么存在一个特征分解：

$S=U\Lambda U^{-1}$

其中，U的每一列都是S的特征向量， $\Lambda$ 是按照特征值从大到小排列的对角阵

对称对角化定理：假定S是一个MxM的实对称方阵，并且它有M个线性无关的特征向量，那么存在一个对称对角化分解：

$S=Q\Lambda Q^T$

其中，Q的每一列都是S的互相正交且归一化的特征向量， $\Lambda$ 是对角矩阵，其每个对角线上的值都对应S的一个特征值

词项-文档矩阵及SVD

SVD：令r是MxN矩阵C的秩，那么C存在如下形式的SVD：

$C=U\Sigma V^T$

其中，U是一个MxM的矩阵，其每一列是矩阵 $CC^T$ 的正交特征向量，而NxN矩阵V的每一列都是矩阵 $C^TC$ 的正交特征向量，MxN的矩阵 $\Sigma$ 的主对角线上的值是矩阵C的奇异值。

$CC^T=U\Sigma V^TV\Sigma ^TU^T= U\Sigma\Sigma ^TU^T$

$CC^T$ 矩阵中的（i,j）代表第i个词项与第j个词项基于文档共现次数的一个重合度计算指标。如果C是布尔矩阵，则（i,j）代表第i个词项与第j个词项共现的文档数目。

低秩逼近（low-rank approximation）

给定MxN的矩阵C及正整数k，寻找一个秩不高于k的MxN的矩阵 $C_{k}$ ,使得两个矩阵的差 $X=C-C_{k}$ 的F-范数最小，即下式最小：

$\vert\vert x \vert\vert_{F} = \sqrt{\sum_{i=1}^M\sum_{j=1}^NX_{ij}^2}$ .

X的F-范数度量了 $C_{k}$ 和C之间的差异程度。当k比r小得多时，我们称 $C_{k}$ 为低秩逼近矩阵

步骤：SVD， $C=U\Sigma V^T$

把 $\Sigma$ 中对角线上r-k个最小奇异值置为0，从而得到 $\Sigma _{k}$

计算 $C_{k}=U\Sigma_{k} V^T$ 作为C的逼近

定理： $\min_{Z\vert rank(Z)=k}\vert \vert C-Z\vert \vert _{F}=\vert \vert C-C_{k}\vert \vert _{F}=\sqrt{\sum_{i=k+1}^r\sigma _{i}^2 }$

为什么从 $\Sigma$ 中去掉最小的r-k个奇异值能够产生低误差的k-秩逼近？

$\begin{equation}\begin{aligned}C_{k}&=U\Sigma _{k}V^T \\&=U\left[\begin{matrix} \sigma_{1} & 0 &0 & 0 & 0 \\ 0 &\dots &0 &0 & 0 \\ 0 &0 & \sigma_{k} &0 &0\\ 0 & 0 & 0 & 0 &0 \\0 & 0 & 0 & 0 &\dots\\\end{matrix}\right]V^T\\&=\sum_{i=1}^k\sigma_{i}\vec{u_{i}}\vec{v_{i}}^T \end{aligned}\end{equation}$

$\vec{u_{i}}\vec{v_{i}}^T$ 是一个1-秩矩阵，于是我们将 $C_{k}$ 表示成k个1-秩矩阵的加权和，每个矩阵的权重是对应的奇异值。所以奇异值越小，产生的加权和越小。

LSI

定义：利用SVD分解来找到词项-文档矩阵C的某个低秩逼近，在这个低秩逼近下能够为文档集中的每篇文档产生一个新的表示。同样，查询也可以映射到这个低秩表示的空间，从而可以基于新的表示来进行查询和文档的相似度计算。这个过程称为LSI。

别名：LSA，潜在语义索引，隐含语义索引，隐含语义分析

目的：在向量空间模型下，可以将查询和文档转换成同一空间下的向量，可以基于余弦相似度进行评分计算，能够对不同的词项赋予不同的权重。但是，向量空间模型无法处理自然语言处理中的两个经典问题：一义多词（synonymy）和一词多义（polysemy）问题。向量空间模型将相同含义的词分别表示成独立的一维，因此无法处理一义多词问题。向量空间模型将具有多个含义的词固定在一维，因此在计算相似度时会高估，无法处理一词多义问题。因此，LSI的目的就是利用词项的共现信息来获得词项的隐形语义关联从未减轻这些问题的影响

对一个中等规模的文档及来说，词项-文档矩阵C可能有成千上万的行和列，秩数目大概也是这个数量级。LSI利用SVD分解来构造C的一个低秩逼近 $C_{k}$ ,其中k远小于C的秩（实验时k的取值往往在几百以内），这样我们将词项-文档矩阵中的每行（词项）和每列（文档）映射到一个k维空间， $CC^T$ 和 $C^TC$ 的k个主特征向量（对应k个最大特征值）可以定义该空间。

接下来，和原始空间一样，我们利用新的k-维空间的LSI表示来计算向量的相似度。新的向量可以通过下式变换到LSI空间：

$\vec{q} _{k} =\Sigma _{k} ^{-1} U _{k} ^{T}\vec{q}$

推导： $C=U\Sigma V^T \Rightarrow V^T =\Sigma^{-1}U^TC \Rightarrow V_{k}^T=\Sigma_{k}^{-1}U_{k}^TC \Rightarrow \vec{q_{k}}= \Sigma_{k}^{-1}U_{k}^T\vec{q}$

然后可以利用向量的相似度算法计算查询与文档的相似度。

理解

LSI通过term-document矩阵的SVD将term和document投影到一个低维的空间中，在这个过程中丢弃了一些影响比较小（小的奇异值）的信息，这些信息可能是噪声。

结论

SVD的计算开销很大。

降低k值，召回率将会提高。k越低，LSI空间的维度越低，影响向量距离的因子越少，召回率越高。

对于合适的k值，LSI能部分解决一义多词问题。

当查询和文档重合度很低时，LSI的效果最好。

Latent Semantic Indexing

Latent Semantic Indexing

线性代数回顾

相关阅读更多精彩内容

友情链接更多精彩内容