奇异值分解及应用

$\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\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$ :

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

其中, $\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$ ,不同的文档向量可以利用这个新的表示来计算相似度,以此来处理一义多词问题。

数据降维

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

参考