SVD奇异值分解原理及应用

2 min read

什么是SVD?

奇异值分解(singular value decomposition)是线性代数中一种重要的矩阵分解,在生物信息学、信号处理、金融学、统计学等领域有重要应用,SVD都是提取信息的强度工具。在机器学习领域,很多应用与奇异值都有关系,比如推荐系统、数据压缩(以图像压缩为代表)、搜索引擎语义层次检索的LSI等等。

SVD的原理

矩阵相关知识

正交与正定矩阵

  • 正交矩阵:若一个方阵其行与列皆为正交的单位向量,则该矩阵为正交矩阵,且该矩阵的转置和其逆相等。两个向量正交的意思是两个向量的内积为 0。
  • 正定矩阵:如果对于所有的非零实系数向量 z,都有 z^T \mathbf Az>0,则称矩阵\mathbfA是正定的。正定矩阵的行列式必然大于0,所有特征值也必然>0。相对应的,半正定矩阵的行列式必然 ≥ 0。

转置与共轭转置

矩阵的转置(transpose)是最简单的一种矩阵变换。简单来说,若m\times n的矩阵\mathbf M的转置记为M^T;则\mathbf M^T是一个n\times m的矩阵,并且\mathbf M_{i,j}=\mathbf M^T_{j,i}。因此,矩阵的转置相当于将矩阵按照主对角线翻转;同时,我们不难得出\mathbf M=(\mathbf M^T)^T

矩阵的共轭转置(conjugate transpose)可能是倒数第二简单的矩阵变换。共轭转置只需要在转置的基础上,再叠加复数的共轭即可。因此,若以\mathbf M^{\mathsf H}记矩阵\mathbf M的共轭转置,则有\mathbf M_{i,j} = \overline{\bigl(\mathbf M^{\mathsf H}\bigr)_{j,i}}

酉矩阵

酉矩阵(unitary matrix)是一种特殊的方阵,它满足\mathbf U\mathbf U^{\mathsf H} = \mathbf U^{\mathsf H}\mathbf U = I_n。不难看出,酉矩阵实际上是推广的正交矩阵(orthogonal matrix);当酉矩阵中的元素均为实数时,酉矩阵实际就是正交矩阵。另一方面,由于\mathbf M\mathbf M^{-1} = \mathbf M^{-1}\mathbf M = I_n,所以酉矩阵 \mathbf U 满足\mathbf U^{-1} = \mathbf U^{\mathsf H},事实上,这是一个矩阵是酉矩阵的充分必要条件。

正规矩阵

同酉矩阵一样,正规矩阵(normal matrix)也是一种特殊的方阵,它要求在矩阵乘法的意义下与它的共轭转置矩阵满足交换律。这也就是说,若矩阵 \mathbf M 满足如下条件,则称其为正规矩阵:\mathbf M\mathbf M^{\mathsf H} = \mathbf M^{\mathsf H}\mathbf M。显而易见,复系数的酉矩阵和实系数的正交矩阵都是正规矩阵。显而易见,正规矩阵并不只有酉矩阵或正交矩阵。例如说,矩阵\mathbf M = \begin{pmatrix}1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1\end{pmatrix}即是一个正规矩阵,但它显然不是酉矩阵或正交矩阵;因为\mathbf M\mathbf M^{\mathsf H} = \begin{pmatrix}2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2\end{pmatrix} = \mathbf M^{\mathsf H}\mathbf M

谱定理和谱分解

矩阵的对角化是线性代数中的一个重要命题。谱定理(spectral theorem)给出了方阵对角化的一个结论:若矩阵 \mathbf M 是一个正规矩阵,则存在酉矩阵 \mathbf U,以及对角矩阵\mathbf \Lambda,使得\mathbf M = \mathbf U\mathbf \Lambda\mathbf U^{\mathsf H}。这也就是说,正规矩阵,可经由酉变换,分解为对角矩阵;这种矩阵分解的方式,称为谱分解(spectral decomposition)。

SVD奇异值分解

谱定理给出了正规矩阵分解的可能性以及分解形式。然而,对于矩阵来说,正规矩阵是要求非常高的。因此,谱定理是一个非常弱的定理,它的适用范围有限。在实际生产中,我们遇到的很多矩阵都不是正规矩阵。对于这些矩阵,谱定理就失效了。作为谱定理的泛化,SVD 分解对于原矩阵的要求就要弱得多。

假设\mathbf M是一个m\times n的矩阵,其中的元素全部属于数域\mathbb K(实数域\mathbb R或复数域\mathbb C)。那么,存在m\times m的酉矩阵\mathbf Un\times n的酉矩阵\mathbf V使得:

    \[M_{m×n}=U_{m×m} \Sigma_{m×n} V^T_{n×n}\]

其中 \mathbf\Sigmam\times n的非负实数对角矩阵;并且 \mathbf\Sigma对角线上的元素\mathbf\Sigma_{i, i}\mathbf M的奇异值。一般来说,我们偏好将这些奇异值按从大到小的顺序排列,这样一来\mathbf\Sigma就由\mathbf M唯一确定了。

另一方面,因为 U 和 V 都是酉矩阵,所以 U 和 V 的列向量分别张成 Km 和 Kn 的一组标准正交基。我们将 U 的列向量记作 u⃗ i,1⩽i⩽m;将 V 的列向量记作 v⃗ j,1⩽j⩽n;同时,将 Σ 对角线上的第 i 个元素记作 σk,1⩽k⩽min(m,n)。那么,SVD 分解实际可以将矩阵 M 写作一个求和形式:

    \[\mathbf M = \sum_{i = 1}^{\min(m, n)}\sigma_i\vec u_i\vec v_i^{\mathsf T}\]

SVD 的计算方法

SVD 与特征值

现在,假设矩阵\mathbf M_{m\times n} 的 SVD 分解是\mathbf M = \mathbf U\mathbf\Sigma\mathbf V^{\mathsf H},那么,我们有

    \[\begin{aligned} \mathbf M\mathbf M^{\mathsf H} &{}= \mathbf U\mathbf\Sigma\mathbf V^{\mathsf H}\mathbf V\mathbf\Sigma^{\mathsf H}\mathbf U^{\mathsf H} = \mathbf U(\mathbf\Sigma\mathbf\Sigma^{\mathsf H})\mathbf U^{\mathsf H}\\ \mathbf M^{\mathsf H}\mathbf M &{}= \mathbf V\mathbf\Sigma^{\mathsf H}\mathbf U^{\mathsf H}\mathbf U\mathbf\Sigma\mathbf V^{\mathsf H} = \mathbf V(\mathbf\Sigma^{\mathsf H}\mathbf\Sigma)\mathbf V^{\mathsf H}\\ \end{aligned}\]

这也就是说,\mathbf U的列向量(左奇异向量),是\mathbf M\mathbf M^{\mathsf H}的特征向量;同时,\mathbf V 的列向量(右奇异向量),是\mathbf M^{\mathsf H}\mathbf M的特征向量;另一方面,\mathbf M的奇异值(\mathbf\Sigma 的非零对角元素)则是\mathbf M\mathbf M^{\mathsf H}或者\mathbf M^{\mathsf H}\mathbf M的非零特征值的平方根。

如何计算 SVD

有了这些知识,我们就能手工计算出任意矩阵的 SVD 分解了;具体来说,算法如下:

  • 计算 \mathbf M\mathbf M^{\mathsf H}\mathbf M^{\mathsf H}\mathbf M
  • 分别计算\mathbf M\mathbf M^{\mathsf H}\mathbf M^{\mathsf H}\mathbf M的特征向量及其特征值;
  • \mathbf M\mathbf M^{\mathsf H}的特征向量组成\mathbf U;而\mathbf M^{\mathsf H}\mathbf M的特征向量组成 \mathbf V
  • \mathbf M\mathbf M^{\mathsf H}\mathbf M^{\mathsf H}\mathbf M的非零特征值求平方根,对应上述特征向量的位置,填入\mathbf\Sigma的对角元。

实际计算看看

现在,我们来试着计算\mathbf M = \begin{bmatrix}2 & 4 \\ 1 & 3 \\ 0 & 0 \\ 0 & 0\end{bmatrix}的奇异值分解。计算奇异值分解,需要计算\mathbf M与其共轭转置的左右积;这里主要以\mathbf M\mathbf M^{\mathsf H}为例。

首先,我们需要计算\mathbf M\mathbf M^{\mathsf H}

    \[\mathbf W = \mathbf M\mathbf M^{\mathsf H} = \begin{bmatrix}2 & 4 \\ 1 & 3 \\ 0 & 0 \\ 0 & 0\end{bmatrix}\begin{bmatrix}2 & 1 & 0 & 0 \\ 4 & 3 & 0 & 0\end{bmatrix} = \begin{bmatrix}20 & 14 & 0 & 0 \\ 14 & 10 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0\end{bmatrix}\]

现在,我们要求 W 的特征值与特征向量。根据定义\mathbf W\vec x = \lambda \vec x;因此(\mathbf W - \lambda\mathbf I)\vec x = \vec 0 。这也就是说:

    \[\begin{bmatrix} 20 - \lambda & 14 & 0 & 0 \\ 14 & 10 - \lambda & 0 & 0 \\ 0 & 0 & -\lambda & 0 \\ 0 & 0 & 0 & -\lambda \end{bmatrix}\vec x = \vec 0\]

根据线性方程组的理论,若要该关于\vec x的方程有非零解,则要求系数矩阵的行列式为 0;也就是:

    \[\begin{vmatrix} 20 - \lambda & 14 & 0 & 0 \\ 14 & 10 - \lambda & 0 & 0 \\ 0 & 0 & -\lambda & 0 \\ 0 & 0 & 0 & -\lambda \end{vmatrix} = \begin{vmatrix} 20 - \lambda & 14 \\ 14 & 10 - \lambda \\ \end{vmatrix}\begin{vmatrix} -\lambda & 0 \\ 0 & -\lambda \\ \end{vmatrix} = 0\]

这也就是

    \[\bigl((20 - \lambda)(10 - \lambda) - 196\bigr)\lambda^2 = 0\]

;解得\lambda_{1} = \lambda_{2} = 0, \lambda_{3} = 15 + \sqrt{221} \approx 29.866,\lambda_{4} = 15 - \sqrt{221} \approx 0.134。将特征值代入原方程,可解得对应的特征向量;这些特征向量即作为列向量,形成矩阵:

    \[\mathbf U = \begin{bmatrix}-0.82 & -0.58 & 0 & 0 \\ -0.58 & 0.82 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1\end{bmatrix}\]

同理可解得(注意,\mathbf M\mathbf M^{\mathsf T}\mathbf M^{\mathsf T}\mathbf M的特征值相同)

    \[\mathbf V = \begin{bmatrix}-0.40 & -0.91 \\ -0.91 & 0.40\end{bmatrix}\]

以及\mathbf\Sigma上的对角线元素由\mathbf W的特征值的算术平方根组成;因此有:

    \[\mathbf\Sigma = \begin{bmatrix}5.46 & 0 \\ 0 & 0.37 \\ 0 & 0 \\ 0 & 0\end{bmatrix}\]

因此我们得到矩阵\mathbf M的 SVD 分解(数值上做了近似):

    \[\begin{bmatrix}2 & 4 \\ 1 & 3 \\ 0 & 0 \\ 0 & 0\end{bmatrix} \approx \begin{bmatrix}-0.82 & -0.58 & 0 & 0 \\ -0.58 & 0.82 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1\end{bmatrix}\begin{bmatrix}5.46 & 0 \\ 0 & 0.37 \\ 0 & 0 \\ 0 & 0\end{bmatrix}\begin{bmatrix}-0.40 & -0.91 \\ -0.91 & 0.40\end{bmatrix}\]

SVD的应用实战

本次实战内容为基于模型的协同过滤算法。假设我们用m个用户,n个商品,每个用户对每个商品的评分可以组成一个m*n的二维矩阵。当然,这个矩阵中会有非常多的值是不知道的,可能是用户没有用过这个商品,也有可能用户使用后没有进行评分。如下图所示:

图中空白位置即未知的值。接下来,我们需要做的是根据这个残缺的二维矩阵中已知的值,预测出未知的值,即预测出每一个用户对每一个商品的评分。可以想象,当矩阵被预测值补充完整之后,矩阵的每一行即表示一个用户对所有商品的评分,可以从这些评分中提取评分最高的几个商品推荐给用户,这样我们就完成了一个推荐系统模型。接下来,就是如何通过已知值预测未知值的问题了,这里我们采用矩阵分解的方式,如图所示:

中间矩阵可以拆分为左边和上边两个矩阵的乘积,这就是奇异值分解,一个矩阵总是可以拆分成两个矩阵相乘。

第一步:安装Python组件及准备数据

1、安装Python推荐系统库:Surprise(Simple Python Recommendation System Engine)

2、准备训练数据

用到的数据集movieslen 100k:https://grouplens.org/datasets/movielens/

Surprise自带数据集就支持movieslen,运行如下代码:

交互窗口提示如下内容:

输入Y以后会自动将数据集下载下来并可直接使用。

第二步:使用SVD进行模型训练

第三步:根据模型结果进行推荐

SVD的缺点

SVD分解是早期推荐系统研究常用的矩阵分解方法,不过该方法具有以下缺点,因此很难在实际系统中应用。

  • 该方法首要需要用一个简单的方法补全稀松评分矩阵。一般来说,推荐系统中的评分矩阵是非常稀疏的,一般都有95%以上的元素是缺失的。而一旦补全,评分矩阵就会变成一个稠密矩阵,从而使评分矩阵的存储需要非常大的空间,这种空间的需求在实际系统中是不可能接受的。
  • 该方法依赖的SVD分解方法的计算复杂度较高,特别是在稠密的大规模矩阵上更是非常慢。一般来说,这里的SVD分解用于1000维以上的矩阵就已经非常慢了,而实际系统动辄上千万的用户和几百万的物品,所以这一方法无法使用。如果仔细研究这方面的论文可以发现,实验都是在几百个用户、几百个商品的数据集上进行的。

如何解决SVD存在的问题,请听下回分解。

参考链接:

打赏作者
微信支付标点符 wechat qrcode
支付宝标点符 alipay qrcode

自然语言处理之小明NLP

最近在盘点Python下的自然语言处理包,今天发现的这个小明NLP,本身这个工具算是一个比较普通的工具,但中间
标点符
20 sec read

自然语言处理之spaCy

spaCy 是一个Python自然语言处理工具包,诞生于2014年年中,号称“Industrial-Stren
标点符
4 min read

自然语言处理工具包之TextBlob

TextBlob简介 TextBlob是一个用Python编写的开源的文本处理库。是自然语言工具包(NLTK)
标点符
1 min read

发表评论

电子邮件地址不会被公开。 必填项已用*标注