xpath为什么取href的值总是取不到_传统推荐算法(一)利用SVD进行推荐(3)6个层面透彻了解奇异值分解...
发布日期:2021-09-13 19:08:32 浏览次数:1 分类:技术文章

本文共 5643 字,大约阅读时间需要 18 分钟。

文章目录

    • 写在前面

    • 1. 从几何变换到奇异值分解

    • 2. 代数角度理解奇异值与奇异向量

      • 2.1 从正交基映射推导SVD

      • 2.2 特征值分解求解奇异值和奇异向量

        • 2.2.1 求解过程

        • 2.2.2 推论

      • 2.3 SVD的另一种形式

    • 3. 几何角度理解奇异值与奇异向量

      • 3.1 从坐标变换理解

        • 3.1.1 从例子到一般

        • 3.1.2 两个问题

      • 3.2 形变的角度理解奇异值

    • 4. 奇异值的最好解读

    • 5. 特征值分解和奇异值分解区别

    • 6. 奇异值分解在PCA中的应用

    • 参考文献

    • 广告

写在前面

读完本篇文章后,你应该可以知道:

奇异值分解到底是什么?

奇异值和奇异向量有什么代数意义?
奇异值和奇异向量有什么几何意义?
如何利用特征值分解求奇异值和奇异向量?
奇异值的个数如何确定?
奇异值分解是否唯一?
奇异值分解什么时候和特征值分解相等?
奇异值分解和特征值分解的区别?


1. 从几何变换到奇异值分解

这部分的内容是[1]中部分内容的翻译,这几张图片大家应该见过很多次。

来看一个二维平面坐标系的例子,在由(1,0)T和(0,1)T确定的二维平面坐标系中:90b487573da8feb2efb933c02cfa1971.png

向量(x,y)T左乘M矩阵,将会得到一个新的向量(新的点)。为了更容易理解变换过程,我们主要关注向量(1,1)T和(1,0)T,(0,1)T,(0,0)T围城的矩形的形变过程。4933d0f63c2e94ade288dacc9b42db7c.png
左乘矩阵M的效果在坐标系中的表现如下:44b4d8c4ac31cb33182b12c11bc7099c.png
直接从图上看不出什么,我们把原先的坐标系逆时针旋转30度,然后左乘M看看效果:

cbd0bade744448961cfe2b7e4c936538.png

好像也没什么特殊的,把原先的坐标系逆时针旋转60度看看:ba84841110c3276f7efdb891dc80be02.png

右边的网格几乎快要正交了,也就是说,原先的正交基逆时针旋转60度后,再经过M变换,几乎可以得到一组新的正交基。

实际上,如果我们把坐标轴逆时针旋转58.28度,就会得到如下效果:cfb1a41596df6db72407ff1ec7dbf0fd.png

从几何上看,旋转后的正交基(1,0)T和(0,1)T,在经过M变换后,得到了另外一组正交基。这其实就是SVD分解的一种解释,即M可以将一组正交基映射到另一组正交基。9d174c6fa562706a5a00f72210224095.png
记映射后的向量Mv1为u1,Mv2为u2,Mv1的模为σ1,Mv2的模为σ2。3286a15f9b610a1bcd8a0c56422504d9.png
接下来我们就可以推导了:

af0755c35d5a47b92300516ae4ca6d6e.png

在v1和v2确定的二维平面中,任意一点x可以表示为:2abfa3a54dba7b9c7824886a822ee483.png

在《利用SVD进行推荐(1)矩阵相乘的本质》中我们讲过,小括号里的点积就是x在v1和v1坐标轴上的投影值(坐标)。我们对这个平面中任意一点x左乘矩阵M进行变换,来看看结果:6f8c1fba78ee1afab5affab91a3f64b7.png
向量点积表示为矩阵乘法就是:8823bdc4994a6f16fd6b13c2440d4785.png
所以变换结果可以进一步推演为:8e5c279503f85f1d0855fa204dfb4de9.png
我们得到了M有关u,v,σ的表达式。将表达式转为矩阵表达形式,即为:bfff2333958b847f33bc1d5de3364e92.png
其中U中的每一列向量ui为映射后的一个单位基向量,V中的每一个列向量vj为原先被映射的单位基向量。这里的推导过于简略,下面我们看看更为严格的推导。


2. 代数角度理解奇异值与奇异向量

奇异值分解在代数上表现就是A将一组正交基转化为另一组正交基。我们来看一下具体推导。

2.1 从正交基映射推导SVD

2.1内容主要来自[5],靖王你真帅!

假设找到了这样一组正交基:

20a0853cec4ff8cb370c33695f1e9f9a.png

而mxn的实矩阵A将其映射为:4cb5393005e698c739c5f7898c90c8ef.png

我们要使他们两两正交,也就是:295d0f91beacb96ff9ac1ec362d63ba3.png
根据假设,有:8eb1eaa7758aa603ae34840e5ec0f3ae.png
在这种情况下,如果取vi为AT的特征向量的话,那么就有:7fe37fb5729e997a096f72bcf28e852d.png
这样我们就找到了正交基使其映射后还是正交基了。现在我们将映射后的正交基单位化。因为:0bd3e583ddaf84a5375e0daa3553681f.png
也就是:

096558e4c1bba9c88efd2a5107fb53c9.png

所以取单位向量为:161c8fdb73a3def6f9b75ae260ca32d7.png

由此可得:c2a0e7a525d3e15a64ef2e81fc184ed8.png
从上述公式来看,左奇异向量ui是映射后正交基的单位化形式,奇异值σi就是映射后的正交基的模的大小,而右奇异向量vi就是被映射的正交基。此处也可以看出奇异值一定非负(当然本身的定义就是这样)。

当k < i < m时,对u1,u2,…,uk进行扩展u(k+1),…,um,使得u1,u2,…,um为m维空间中的一组正交基,即:

f38e79af994d614099fb74f9ae7d83cb.png

同样的,对v1,v2,…,vk进行扩展v(k+1),…,vn(这n-k个向量存在于A的零空间中,即Ax=0的解空间的基),使得v1,v2,…,vn为n维空间中的一组正交基,即:9d7e3bcda3e50737118f56212305d99c.png

然后我们就可以得到:

50e05cfe18c59425706fe274b457b326.png

从而A的SVD分解为:797cc05c9bc0d5302655e2b1a4a0f91a.png591b2c7bf0ba0681422e099fb69f645f.png

根据论文[3]的分析,任意mxn的实矩阵A=UΣVT,都可以看成一种线性转化, 从n维空间到m维空间的转化。n维空间和m维空间分别由V和U的列向量所形成的基向量确定。

2.2 特征值分解求解奇异值和奇异向量

2.2.1 求解过程

对任意mxn实矩阵A的奇异值分解A=USVT,有:

ATA = VSTSVT
(AAT)vi = VSTSVTvi=σi2vi
这不就是特征值分解吗。也就是说vi是ATA的特征向量,其对应的特征值是σi2,同理ui是AAT的特征向量,其对应的特征值也是σi2。可以从这个角度出发求解特征值和特征向量。

实际上,对于mxn维的实矩阵A,AAT和ATA都是半正定的实对称矩阵(特征值为非负数),且具有相同的非零特征值。且k=rank(AAT)=rank(ATA)=rank(A)[4]。显然实对称矩阵的秩就是非零特征值的个数。因此这两个实对称矩阵有k个相同的非零特征值。当i>rank(A)即使有特征值也全是0。

这里的分析还可以解释2.1中对角阵S上的i为什么最多取到k=rank(A),假设可以取到k+1,按照本节中的推导,奇异值σi+1是找不到对应的非零特征值的,显然σi+1=0。

或者说得专业些,ATA是实对称矩阵,存在n阶正交矩阵V,使得ATA相似于对角矩阵STS(对角线上是ATA的全部特征值)。相似的矩阵有相同的特征多项式,进而有相同的特征值,当然秩更要相同了。所以r(S)=r(STS)=r(ATA)=r(A)。即对角阵S非零奇异值的个数=ATA非零特征值的个数=对称矩阵ATA的秩=A的秩。

2.2.2 推论

好了我们可以总结下了,对于任意实矩阵A的奇异值分解,它的右奇异向量(V的列向量)是ATA的特征向量,它的左奇异向量(U的列向量)是AAT的特征向量,而奇异值是这两个对称矩阵相同的非零特征值的平方根(实际上它们两个非零特征值一模一样)。

SVD分解只告诉我们总是存在这样一个分解,并没有说这个分解是唯一的。很显然:特征值次序就可以不一样,显然SVD分解不唯一。但是我们常常把奇异值按照从大到小的顺序排列,这样S就可以由A唯一确定了。[7]和[8]告诉了我们SVD分解什么情况下是唯一的,感兴趣可以看看。

那什么时候SVD分解和特征值分解相等呢?

[10]里面给出了一种说法:757777c8686e38e7815eb28ea0c402a6.png

2.3 SVD的另一种形式

实矩阵A的奇异值分解A=USVT可以表示为:

492bdb6e68622fd1c992b1d1b5f0ee3a.png

其中k=rank(A),即矩阵A的秩。参照2.2我们知道k=rank(AAT)=rank(ATA)=rank(A),这些奇异值和这两个对称矩阵的相同特征值是一一对应关系(平方根),显然k<=min(m,n)。

使用矩阵的分块乘法,得:

de0df84236c1644f2b2fa492a7b5d32e.png

后面一项是0,所以可以化为:

fc676a1dcf560260bb466b1e77f07f87.png

如果我们令X为mxk的矩阵,Y为kxn的矩阵:1b48eb3f1b7e2ac45e2be205388bf8da.pngd28c7dc589a78e8ae37b63d2b7115f36.png

那么A可以表示为:

7a724f9439ee4994099cd43c8b42aa0e.png

我们把它展开为向量的外积形式,这就是SVD的另一种表达形式:

23ef915a31b62f41f2ee64cb047377c4.png

那么向量x左乘矩阵A是什么呢?我们看看:

9271c7182c3403c6716b37914b727314.png

viTx是个标量,所以有:

c0de6206856a73a8f882f0f566ca43be.png

此时Ax已经表示成了ui的线性组合,每一项线性系数是viTx和σi的乘积,我们知道viTx是x在V坐标系下vi轴上的坐标。结论呼之欲出:在A的作用下,x由n维空间转化到了m维空间中。下一章我们将从空间几何的角度对这个转化进行理解。


3. 几何角度理解奇异值与奇异向量

3.1 从坐标变换理解

3.1.1 从例子到一般

我直接复制[9]中的一个例子过来,作者是西电的张剑湖大佬:

66686df215d5e2c2453cfef24faee650.png9351d030d64afa8c8cf4142305145cba.png6e455258de9165f34926650b3c200c07.png

07b4b1f4eb6b7be074a0048905551141.png

af81b7cd9864e37da79e2dafb2336d2f.png

《利用SVD进行推荐(1)矩阵相乘的本质》一文中提到过,向量左乘正交矩阵可以达到将向量旋转的效果。我们还看了一个2阶非对称方阵的实例,它的奇异值变换就是对向量进行旋转-缩放-旋转的过程。当时并没有讲维度变化这个细节。

我们对更一般的形式进行分析:从奇异值分解的角度出发,Ax=USVTx,VTx就是x在V每个列向量所确定的轴进行投影,是先将x映射到V坐标系中(此时x维度和V确定的空间维度相同,也可以理解为旋转x),然后缩放的同时将维度映射到U-1的维度,最后映射到U-1坐标系中(此时SVTx和U-1坐标系维度相同,可以理解为旋转)。

3.1.2 两个问题

第一个问题是,为什么不是在U-1中进行长度为σi的伸缩,而在U-1坐标系中向量的模长却为σi呢?

是这样的,拿v1举例吧,它太过特殊,在V坐标系中的投影坐标是(1,0,…,0)T。而Σ不仅把这个n维的进行了扩维,将n维的(1,0,…,0)T变为m维的(1,0,…,0),同时还进行了第一维度上长度为σ1的伸缩成为了(σ1,0,…,0)。

所以,在投影到U-1坐标系之前,v1已经转化成一个m空间的向量,它的模长就是σ1。而这个m维空间无论用哪组单位正交基来表示,只不过相当于对向量进行旋转换了方向,向量本身的模是不变的。

第二个问题是,如果如问题1所述,那为什么投影到U-1坐标系中,坐标值恰好与U中的基向量是对应的?

实际上在代数上就是这样没有为什么。从几何角度,我们还是在二维中进行分析吧。假设B点逆时针旋转θ度即为A点,顺时针θ度为C点。x1,y1坐标系和x2,y2坐标系就是U和U-1。现在对于B(σ1,0),我们要向x2,y2坐标系中投影,由其相对关系可知,其投影坐标值其实就相当于A点在x,y坐标系中的投影坐标值,也就是(cosθ,sinθ)T*σ1。

发现了吧,当v1乘以对角阵S维度扩展到m时,此时它的坐标是有一个默认的坐标系的,就如下图中的x,y坐标系。而U和U-1空间也如下图中关系所示,它们使用默认坐标系中的坐标来表示自己。在默认坐标系下x和y轴向的伸缩变换在x2,y2中的表示,就如同x1,y1坐标轴向的伸缩变换在x中的表示,当然使用x1,y1坐标轴的基向量的表示啊。

ce71aedf4851bea911a203500b992ec2.png

我们可以发现,对于x,y坐标系中的向量OB(σ1,0),无论是逆时针转到了坐标系x1,y1中变为(cosθ,sinθ)T*σ1,还是转到x2,y2坐标系中成为(cosθ,-sinθ)T*σ1,它的模是不变的。这与问题一是呼应的。


3.2 形变的角度理解奇异值

在[2]中,马同学从翻绳游戏开始,对奇异值进行了生动形象的分析,[6]中7.4节也有形变的分析,还有相关例题。感兴趣的可以看一看。


4. 奇异值的最好解读

在知乎问题"奇异值的物理意义是什么?"下,看到一位大牛对奇异值的解读[12],个人认为是对奇异值的一种最好的解读。感谢知乎用户“老鸡蛋”。

bfe14bf38f7c07433311ba0c0f465b63.png


5. 特征值分解和奇异值分解区别

  • 适用条件

    特征值分解必须是可对角化矩阵(所以必须是方阵。n阶方阵可对角化的定义是相似于一个对角矩阵,充要条件是A有n个线性无关的特征向量[11]),奇异值分解则适用于任意矩阵。

  • 特征值/奇异值个数

    特征值个数与矩阵的秩没有必然关系,n阶实对称矩阵的非零特征值个数等于矩阵的秩;非零奇异值个数等于矩阵的秩。

  • 几何意义

    关于几何意义之前讲的比较多,内容较多本文就不再赘述。[10]中对于奇异值分解的几何意义给出了一个很直观的讲法:946cb141df5f6665691943f8d590915e.png


6. 奇异值分解在PCA中的应用

在"利用SVD进行推荐(2)特征值与特征向量的直观理解"中我们讲过,对于样本A,PCA的计算过程就是计算协方差矩阵AAT,然后求前k个最大特征值对应的特征向量得到投影矩阵,从而达到降维的目的。当样本非常多的时候,计算协方差矩阵,还要进行特征值分解,这个计算量挺大的。

我们发现SVD分解A=USVT中,左奇异向量ui不就是AAT的特征向量吗?那我们就可以利用SVD分解来计算投影矩阵了。

[13]中Pinard大神说,有些SVD分解算法可以不用求ATA而直接得到A的右奇异矩阵V,也就是可以直接得到U(AT的右奇异矩阵是UT),那这就很nice了。

参考文献

[1] http://www.ams.org/publicoutreach/feature-column/fcarc-svd

[2] https://www.matongxue.com/madocs/306.html
[3] http://www-users.math.umn.edu/~lerman/math5467/svd.pdf
[4] 张绍飞. 矩阵论教程.第2版[M]. 2012.
[5]https://blog.csdn.net/zhongkejingwang/article/details/43053513
[6] Lay D , Lay. 线性代数及其应用[M]. 机械工业出版社, 2017.
[7] http://rakaposhi.eas.asu.edu/s10-cse494-mailarchive/msg00030.html
[8] https://math.stackexchange.com/questions/644327/how-unique-are-u-and-v-in-the-singular-value-decomposition
[9] https://wenku.baidu.com/view/389fabcebceb19e8b8f6ba97.html
[10] https://www.zhihu.com/question/49959130
[11] 申亚男, 张晓丹, 李为东. 线性代数.第2版[M]. 机械工业出版社, 2015.
[12] https://www.zhihu.com/question/22237507
[13] https://www.cnblogs.com/pinard/p/6251584.html

广告

所有传统推荐算法的代码在:https://github.com/wyl6/Traditional-Classical-Conventional-Recommender-Systems

转载地址:https://blog.csdn.net/weixin_39926014/article/details/111129684 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:百度搜索限定时间_如何高效的搜索信息?
下一篇:笔记本通过网口控制单片机_家里是千兆网,但是网口是百兆怎么办?

发表评论

最新留言

第一次来,支持一个
[***.219.124.196]2024年03月20日 02时34分11秒