奇异值分解及应用

Posted on |

$\newcommand{\A}{\mat{A}} \newcommand{\U}{\mat{U}} \newcommand{\V}{\mat{V}} \newcommand{\S}{\mat{\Sigma}}$

奇异值分解

令 $r$ 是 $M \times N$ 的矩阵 $\A$ 的秩； $\U$ 是 $M \times M$ 矩阵，列是 $\A\A\tr$ 的正交特征向量； $\V$ 是 $N \times N$ 矩阵，列是 $\A\tr\A$ 的正交特征向量；那么 $\A$ 存在如下的奇异值分解(SVD)：

\[\A = \U \S \V\tr\]

其中， $\A\A\tr$ 和 $\A\tr\A$ 的特征值相同，均是 $\lambda_1,\dots,\lambda_r$ 。把特征值从大到小排序 $\lambda_i \geq \lambda_{i+1}$ ，对 $1 \leq i \leq r$ ，令 $\sigma_i = \sqrt{\lambda_i}$ ，则中间的 $M \times N$ 矩阵 $\S$ ，满足对角线元素 $\Sigma_{ii} = \sigma_i$ ，其他元素值均为0。这里矩阵 $\S$ 的对角线元素 $\sigma_i$ 就是矩阵 $\A$ 的奇异值(Singular Value)。

把矩阵 $\S$ 对角线上 $r-k$ 个最小的奇异值 $\sigma_{k+1},\dots,\sigma_{r}$ 置为0，其中 $k \leq r$ ，得到矩阵 $\S_k$ ，求得新矩阵 $\A_k$ ：

\[\A_k = \U \S_k \V\tr\]

由于 $\S_k$ 最多包含 $k$ 个非零元素，所以 $\A_k$ 的秩不高于 $k$ ，这个新矩阵称作 $\A$ 的低秩逼近(low-rank approximation)矩阵。可以证明 $\A_k$ 近似于 $\A$ ：

\[\begin{align} \A_k &= \U \S_k \V\tr \\ &= \U \begin{pmatrix} \sigma_1 & 0 & 0 & 0 & 0 \\ 0 & \cdots & 0 & 0 & 0 \\ 0 & 0 & \sigma_k & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & \cdots \end{pmatrix} \V\tr \\ & = \sum_{i=1}^k \sigma_i \mathrm{u}_i \mathrm{v}_i\tr \end{align}\]

其中， $\mathrm{u}_i$ 和 $\mathrm{v}_i$ 分别是 $\U$ 和 $\V$ 的第 $i$ 列。因此， $\mathrm{u}_i \mathrm{v}_i\tr$ 是一个1-秩矩阵，于是 $\A$ 可以表示成 $k$ 个1-秩矩阵的加权和，每个矩阵的权重是一个奇异值。由于 $\sigma_1 \geq \dots \geq \sigma_k$ ，所以当 $i$ 增加时，权重随之减小，相应的小矩阵对整个加权和的影响也越来越小。通常实际应用中，远小于 $r$ 的 $k$ 秩矩阵 $\A_k$ 即可近似表达 $\A$ 。

协同过滤

协同过滤(CF, Collaborative Filtering)一般采用基于物品相似的协同推荐(ItemCF)，算法如下：

  1. 在用户-物品的矩阵中寻找用户没有关联的物品，即值为0；
  2. 对所有与用户没有关联的物品计算与该用户的相似度；
  3. 对相似度取topN推荐给用户。

可以看出第二步的计算量很大，利用SVD可以把物品映射到 $k$ 维空间来计算相似度。

隐性语义分析

隐性语义分析(LSA, Latent Semantic Analysis) 或 隐性语义索引(LSI, Latent Semantic Indexing) 可以处理向量空间模型无法解决的一义多词(synonymy)问题，但不能解决一词多义(polysemy)问题。之所以叫隐性语义，如果A和C共现(collocation)，B和C共现，LSI可以找到A和B之间的的隐含关系(second-order co-ocurrence)。

对 词项-文档矩阵 $\A$ （比如，行为词项、列为文档、矩阵元素为词项的tf-idf值），奇异值分解得到它的低秩逼近矩阵 $\A_k=\U\S_k\V^{\mathsf{T}}$ 。这相当于把原始的文档向量转换到一个低维的隐含语义空间 $\S_k$ ，每个奇异值对应着每种语义的权重，这个过程称为LSA。每篇文档 $\mathrm{q}$ 可以产生一个新的表示 $\mathrm{q}_k$ ，不同的文档向量可以利用这个新的表示来计算相似度，以此来处理一义多词问题。

\[\mathrm{q}_k = \S_k^{-1} \U_k\tr \mathrm{q}\]

数据降维

通过前面的讨论可以看出SVD同样可以对数据进行降维，它实际上也是一种PCA方法。

参考