奇异值分解及应用

奇异值分解

$r$$M \times N$ 的矩阵 $\mathbf{A}$ 的秩; $\mathbf{U}$$M \times M$ 矩阵,列是 $\mathbf{A}\mathbf{A}^\mathsf{T}$ 的正交特征向量; $\mathbf{V}$$N \times N$ 矩阵,列是 $\mathbf{A}^\mathsf{T}\mathbf{A}$ 的正交特征向量;那么 $\mathbf{A}$ 存在如下的奇异值分解(SVD):

$$
\mathbf{A} = \mathbf{U} \mathbf{\Sigma} \mathbf{V}^\mathsf{T}
$$

其中, $\mathbf{A}\mathbf{A}^\mathsf{T}$$\mathbf{A}^\mathsf{T}\mathbf{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$ 矩阵 $\mathbf{\Sigma}$ ,满足对角线元素 $\Sigma_{ii} = \sigma_i$ ,其他元素值均为0。这里矩阵 $\mathbf{\Sigma}$ 的对角线元素 $\sigma_i$ 就是矩阵 $\mathbf{A}$奇异值(Singular Value)。

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

$$
\mathbf{A}_k = \mathbf{U} \mathbf{\Sigma}_k \mathbf{V}^\mathsf{T}
$$

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

$$
\begin{align}
\mathbf{A}_k &= \mathbf{U} \mathbf{\Sigma}_k \mathbf{V}^\mathsf{T} \\
&= \mathbf{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} \mathbf{V}^\mathsf{T} \\
& = \sum_{i=1}^k \sigma_i \mathrm{u}_i \mathrm{v}_i^\mathsf{T}
\end{align}
$$

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

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

$$
\mathrm{q}_k = \mathbf{\Sigma}_k^{-1} \mathbf{U}_k^\mathsf{T} \mathrm{q}
$$

数据降维

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

参考

2012-06-22 12:26
status: part
comments powered by Disqus