SVD奇异值分解中特征值与奇异值的数学理解与意义

大鹅

发布于 2021-06-16 09:12:24

2.2K0

文章被收录于专栏：大鹅专栏：大数据到机器学习大鹅专栏：大数据到机器学习

前言

之前的博客中SVD推荐算法写得不是很严谨，

\hat{r}_{ui}=\sum_{f=1}^{F}{P_{uf}Q_{fi}}+\mu+b_u+b_i

更像是矩阵分解多一点，没有涉及到SVD的数学意义，这篇博客大概会写一些数学SVD的数学理解，以及SVD在PCA和推荐算法上面的应用。

特征值与特征向量

如果一个向量

是方阵

的特征向量，将可以表示成下面的形式：

Av=\lambda v

此时

就被称为特征向量

对应的特征值，并且一个矩阵的一组特征向量是一组正交向量。特征值分解是将一个矩阵分解成下面的形式：

A=Q\Sigma Q^{-1}

其中

是这个矩阵

的特征向量组成的矩阵，

是一个对角阵，每一个对角线上的元素就是一个特征值。可以简单理解为提取矩阵最重要的特征，

为线性变换中矩阵变换的主要方向(可以参考链接1)。

缺点也非常明显，就是只适用于方阵，但对于实际情景中我们数据大部分都不是方阵，此时就要引入奇异值分解SVD了。

奇异值分解

奇异值分解(Singular Value Decomposition, SVD)是线性代数中一种重要的矩阵分解，在信号处理、统计学等领域有重要应用。奇异值分解是一个能适用于任意的矩阵的一种分解的方法：

A=U\Sigma V^T

假设

是一个N * M的矩阵，那么得到的

是一个N * N的方阵（里面的向量是正交的，U里面的向量称为左奇异向量），

是一个N * M的矩阵（除了对角线的元素都是0，对角线上的元素称为奇异值），

V^T

是一个N * N的矩阵，里面的向量也是正交的，V里面的向量称为右奇异向量）

那么，我们有

AA^T=U\Sigma V^TV\Sigma^TU^T=U(\Sigma \Sigma^T)U^T \\A^TA=V\Sigma^T U^TU\Sigma V^T=V(\Sigma^T \Sigma) V^T

这也就是说，

的列向量（左奇异向量），是

AA^T

的特征向量；同时，

的列向量（右奇异向量），是

A^TA

的特征向量；另一方面，

的奇异值（

的非零对角元素）则是

AA^T

或者

A^TA

的非零特征值的平方根。

将奇异值和特征值是对应起来：我们将一个矩阵

A^T* A

，将会得到一个方阵，我们用这个方阵求特征值可以得到：

(A^TA)v_i=\lambda_iv_i

这里的向量

v_i

，就是我们上面的右奇异向量。此外我们还可以得到：

\sigma_i=\sqrt \lambda_i \ \ ,\ \ u_i=\frac{1}{\sigma_i}Av_i

这里的

σ_i

就是上面说的奇异值，

u_i

就是上面说的左奇异向量。奇异值

σ_i

跟特征值类似，在矩阵

中也是从大到小排列，而且

σ_i

的减少特别的快，在很多情况下，前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上了。也就是说，我们也可以用前r大的奇异值来近似描述矩阵。

定义一下部分奇异值分解：r是一个远小于m和n的数

A_{m*n}\approx U_{m*r}\Sigma_{r*r}V^T_{r*n}

奇异值分解和推荐算法

在之前的博客中的SVD推荐本质上是model-based，跟传统数学意义的SVD没有太大关系，只不过借鉴了SVD分解

R=U*S*V

这个形式，通过最优化方法进行模型拟合，求得

R=U*V

。

我们可以拿这个维度减少的U作为user特征，V作为item特征，之后用降维后的特征去计算相似度。

具体例子可以看参考链接2

奇异值与主成分分析(PCA)

PCA的原理可以理解为对原始的空间中顺序地找一组相互正交的坐标轴，第一个轴是使得方差最大的，第二个轴是在与第一个轴正交的平面中使得方差最大的，第三个轴是在与第1、2个轴正交的平面中方差最大的，这样假设在N维空间中，我们可以找到N个这样的坐标轴，我们取前r个去近似这个空间，这样就从一个N维的空间压缩到r维的空间了，但是我们选择的r个坐标轴能够使得空间的压缩使得数据的损失最小。

具体可以参考之前的PCA博客

回到原问题中，奇异值和PCA是怎么扯上关系的呢？

将上式右乘

可以得到

A_{m*n}V_{n*r}\approx U_{m*r}\Sigma_{r*r}V^T_{r*n}V_{r*n}=U_{m*r}\Sigma_{r*r}=\hat A_{m*r}

即可以表示为

A_{m*n}V_{n*r}=\hat A_{m*r}

可以理解为将一个m * n的矩阵A变换成一个m * r的矩阵，这样就会使得本来有n个feature的，变成了有r个feature了（r < n)，这r个其实就是对n个feature的一种提炼，我们就把这个称为feature的压缩。SVD得出的奇异向量也是从奇异值由大到小排列的，按PCA的观点来看，就是方差最大的坐标轴就是第一个奇异向量，方差次大的坐标轴就是第二个奇异向量。

可以看出，其实PCA几乎可以说是对SVD的一个包装，如果我们实现了SVD，那也就实现了PCA了，而且更好的地方是，有了SVD，我们就可以得到两个方向的PCA，如果我们对A’A进行特征值的分解，只能得到一个方向的PCA。