LSA/LSI by SVD 基于奇异值分解的潜在语义分析

问题的提出

在一个图书馆系统中，如果用户键入“计算机”，系统可能会返回诸如《计算机技术与应用》，《互联网通信技术》《C++编程理论》，《算法之美》，《电脑维修方法》等书籍。我们的知道“计算机” 与“互联网”，“编程”，“算法”，“电脑”有着类似的潜在语义，所以它们被筛选出来是可以理解的，但是系统是怎么知道它们有着类似的潜在语义呢？答案是LSA 或者 LSI

LSA/LSI

LSA，即Latent Semantic Analysis，也有说是LSI，即Latent Semantic Indexing。它们表示的是同一个技术，以下用LSA来表示。

LSA是基于这个前提训练出来的：两个词如果在同一文本（一个书名为一个文本）中出现的次数一样，则认为这两个词含有同一语义，当然这是基于大量文档决定的。比如，系统“见过”《计算机编程方法》，《计算机云应用编程技术》，《编程原理及其计算机系统》，《计算机原理即编程实践》之后，能够学习到“计算机”和“编程”是同一语义的，于是当你要求它给出“计算机”相关书籍时，它能够返回《C++编程理论》，尽管该书名并没有“计算机”三个字。当然它也可能学习到“计算机”和“原理”是同一语义，这并不是我们想要的——要尽量避免这种情况，我们需要大量文档。下面我们就来讲解该学习方法：

我们考虑下面几本书的标题：
c1: Human machine interface for Lab ABC computer applications
c2: A survey of user opinion of computer system response time
c3: The EPS user interface management system
c4: System and human system engineering testing of EPS
c5: Relation of user-perceived response time to error measurement
m1: The generation of random, binary, unordered trees
m2: The intersection graph of paths in trees
m3: Graph minors IV: Widths of trees and well-quasi-ordering

首先构建词汇-文本矩阵：

将矩阵做SVD分解：

$\underset{m\times n}{A} =\underset{m\times m}{U}\underset{m\times n} {\sum} \underset{n\times n}{V^{T}}$

$U=\begin{bmatrix} -0.22 & -0.31 & 0. & 0.41 & -0.32 & 0.58 & 0. & 0. & 0.19 & 0.31 & -0.25 & -0.21 \\ -0.2 & -0.15 & 0. & 0.56 & 0.56 & -0.09 & 0. & -0. & 0.37 & -0.22 & 0.08 & 0.34 \\ -0.24 & 0.17 & 0. & 0.59 & -0.29 & -0.32 & 0. & -0. & -0.56 & -0.09 & 0.17 & -0.13 \\ -0.4 & 0.35 & 0. & -0.09 & 0.5 & 0. & 0. & 0. & -0.25 & 0.44 & -0.43 & -0.11 \\ -0.65 & -0.39 & 0. & -0.34 & -0.26 & -0.18 & 0. & -0. & -0.08 & -0.1 & -0.11 & 0.43 \\ -0.26 & 0.45 & 0. & -0.07 & -0.09 & 0.32 & 0. & 0. & 0.13 & -0.72 & -0.23 & -0.17 \\ -0.26 & 0.45 & 0. & -0.07 & -0.09 & 0.32 & 0. & -0. & 0.13 & 0.28 & 0.66 & 0.28 \\ -0.31 & -0.36 & 0. & -0.19 & 0.3 & 0.03 & 0. & -0. & -0.04 & -0.12 & 0.46 & -0.66 \\ -0.18 & 0.22 & 0. & 0.02 & -0.26 & -0.56 & 0. & 0. & 0.64 & 0.19 & -0.06 & -0.3 \\ 0. & 0. & -0.74 & 0. & 0. & 0. & -0.59 & -0.33 & 0. & 0. & 0. & 0. \\ 0. & 0. & -0.59 & 0. & 0. & 0. & 0.33 & 0.74 & 0. & 0. & 0. & -0. \\ 0. & 0. & -0.33 & 0. & 0. & 0. & 0.74 & -0.59 & 0. & 0. & -0. & 0. \end{bmatrix}$

$\sum = \begin{bmatrix} 3.33 & & & ... & & & & 0\\ & 2.36 & & & & & &\\ & & 2.25 & & & & &\\ & & & 1.64 & & & &\\ & & & & 1.36 & & &\\ & & & & & 0.86 & &\\ & & & & & & 0.8 & \\ & & & & & & & 0.55\\ 0 & & & ... & & & & 0 \\ 0 & & & ... & & & & 0\\ 0 & & & ... & & & & 0\\ 0 & & & ... & & & & 0 \end{bmatrix}$

$V^{T}= \begin{bmatrix} -0.2 & -0.6 & -0.47 & -0.55 & -0.28 & 0. & 0. & 0. \\ -0.12 & 0.53 & -0.23 & -0.61 & 0.53 & 0. & 0. & 0. \\ 0. & 0. & 0. & 0. & 0. & -0.33 & -0.59 & -0.74 \\ 0.95 & 0.03 & -0.04 & -0.27 & -0.14 & 0. & 0. & 0. \\ -0.04 & -0.36 & 0.81 & -0.4 & 0.24 & 0. & 0. & 0. \\ 0.2 & -0.48 & -0.28 & 0.3 & 0.75 & -0. & -0. & -0. \\ -0. & -0. & -0. & -0. & -0. & -0.74 & -0.33 & 0.59 \\ 0. & 0. & 0. & 0. & 0. & -0.59 & 0.74 & -0.33 \end{bmatrix}$

取3个奇异值进行降维，即k=3:

$\underset{m\times n}{A} =\underset{m\times k}{U}\underset{k\times k} {\sum} \underset{k\times n}{V^{T}}$

$= \begin{bmatrix} -0.22 & -0.31 & 0. \\ -0.2 & -0.15 & 0. \\ -0.24 & 0.17 & 0. \\ -0.4 & 0.35 & 0.\\ -0.65 & -0.39 & 0.\\ -0.26 & 0.45 & 0. \\ -0.26 & 0.45 & 0.\\ -0.31 & -0.36 & 0. \\ -0.18 & 0.22 & 0. \\ 0. & 0.& -0.74 \\ 0. & 0. & -0.59\\ 0. & 0. & -0.33 \end{bmatrix} \begin{bmatrix} 3.33 & 0 & 0\\ 0 & 2.36 & 0 \\ 0 & 0 & 2.25 \end{bmatrix} \begin{bmatrix} -0.2 & -0.6 & -0.47 & -0.55 & -0.28 & 0. & 0. & 0. \\ -0.12 & 0.53 & -0.23 & -0.61 & 0.53 & 0. & 0. & 0. \\ 0. & 0. & 0. & 0. & 0. & -0.33 & -0.59 & -0.74 \end{bmatrix}$

好，我们完成了降维，数据变得简单了。看起来非常顺利，但是我们将词汇-文本矩阵用SVD分解后得到三个矩阵是什么意义呢，降维操作降的是什么东西呢？

在推荐系统的应用中，我们理解： $U$ 的行向量是各个user特征的向量， $\sum$ 的对角线值是权重， $V^{T}$ 的列向量是各个item特征的向量，因为前几个权重占比非常大，所以仅保留user的前几个特征，和item的前几个特征以实现降维是合理的。

在现在讨论的潜在语义分析中，如何理解呢? 我们试着探索一下:

语义空间及其模型的引入

首先我们确定的是原始数据是词汇-文本矩阵， $U$ 是词汇-x矩阵， $\sum$ 是x-y矩阵， $V^{T}$ 是y-文本矩阵：

那么x和y分别是什么呢？我们人为地认为，x=”语义”，y=”主题”，它的合理性在于：一个词汇可以对应不同的语义（ $U$ ），而一个语义可以对应不同主题（ $\sum$ ），而一个主题可以对应不同的文本（ $V^{T}$ ）。且它是可降维的，因为词汇对应的相关性低的语义可以忽略（ $U$ 的降维），被忽略的语义对应的主题也被忽略（ $\sum$ 的降维），文本对应的相关性低的主题可以忽略（ $V^{T}$ 的降维）

检索

在上面的计算中，我们已经得到了降维到3维的语义空间的模型，现在利用该模型计算检索需求。

求：当检索“human computer interaction”时，系统应该返回什么书籍？

计算如下：

检索项目在词汇-文本里面是列向量 $S=\begin{pmatrix} 1\\ 0\\ 1\\ 0\\ 0\\ 0\\ 0\\ 0\\ 0\\ 0\\ 0\\ 0 \end{pmatrix}$ , 将它投影到主题-文本空间的列向量(使用公式)：

$S'^{T}=S^{T}U(\sum )^{-1}$

$= (1,0,1,0,0,0,0,0,0,0,0,0) \begin{bmatrix} -0.22 & -0.31 & 0. \\ -0.2 & -0.15 & 0. \\ -0.24 & 0.17 & 0. \\ -0.4 & 0.35 & 0.\\ -0.65 & -0.39 & 0.\\ -0.26 & 0.45 & 0. \\ -0.26 & 0.45 & 0.\\ -0.31 & -0.36 & 0. \\ -0.18 & 0.22 & 0. \\ 0. & 0.& -0.74 \\ 0. & 0. & -0.59\\ 0. & 0. & -0.33 \end{bmatrix} ( \begin{bmatrix} 3.33 & 0 & 0\\ 0 & 2.36 & 0 \\ 0 & 0 & 2.25 \end{bmatrix} )^{-1}$

$=(-0.14, -0.06, 0.)$

$S'=\begin{pmatrix} -0.14\\ -0.06\\ 0. \end{pmatrix}$

至此，我们得到了主题-文本空间的检索向量。接下来计算该向量与此空间其它的向量（即 $V^{T}$ 的列向量）的相似度，找出相似度最高的那个。

我们通过余弦相似度进行计算。余弦相似度定义为两个向量A,B的夹角：

计算过程：

$\underset{S'->v_{1}}{similarity}= \frac{\begin{bmatrix} -0.2\\ -0.12\\ 0. \end{bmatrix}\cdot \begin{bmatrix} -0.14\\ -0.06\\ 0. \end{bmatrix} }{||\begin{bmatrix} -0.2\\ -0.12\\ 0. \end{bmatrix}||\times ||\begin{bmatrix} -0.14\\ -0.06\\ 0. \end{bmatrix}||}=0.991$

$\underset{S'->v_{2}}{similarity}=0.428$ $\underset{S'->v_{3}}{similarity}=0.998$ $\underset{S'->v_{4}}{similarity}=0.908$ $\underset{S'->v_{5}}{similarity}=0.081$ $\underset{S'->v_{6}}{similarity}=0.0$

$\underset{S'->v_{7}}{similarity}=0.0$ $\underset{S'->v_{8}}{similarity}=0.0$

与 $S'$ 夹角（相似度）由小到大的向量排序： $v_{3},v_{1},v_{4},v_{2},v_{5},v_{6},v_{7},v_{8}$ ，所以系统第一个将返回 $v_{3}$ 对应的书名“The EPS user interface management system”（与直观相违背？没关系，这是因为我们这里用的数据量太小，奇异值取个数也少，所以准确度有待商榷）。在实际中，系统可能会返回按照相关官渡排序的多个结果，且考虑到第5个结果开始相关系急剧下降，则就会返回前4个结果：