李宏毅机器学习笔记(十四)——无监督学习(二)：线性数据降维与推荐系统

线性数据降维与推荐系统"/>

李宏毅机器学习笔记(十四)——无监督学习(二)：线性数据降维与推荐系统

文章目录

• 一.什么是数据降维
• 二.主成分分析(PCA)
• • 1.基本思想
  • 2.数学推导
  • 3.从另一个角度看待PCA
  • 4.PCA的效果
• 三.其他线性降维方法
• 四.矩阵分解

一.什么是数据降维

  对于无标签的数据，我们很多时候并不是想将其分类，而是所谓的根据原始特征，精炼出一定的更有代表性的特征，这样既可以减小维度压缩数据量，同时相当于是对数据的一种清洗(例如去除冗余共线性的数据)。
  因此我们的目标就是，对k个n维的行向量数据 x i x_i xi​(下标表示的是第几个输入数据)，我们找到一个函数 f f f，使得 f ( x ) = z f(x)=z f(x)=z，其中 z z z为m维行向量，代表着 x x x转化后的特征，m<n。

二.主成分分析(PCA)

1.基本思想

  在PCA中我们的一个思想就是，高维空间也是多个维度垂直相交组合而成的，那我们就选取一些垂直相交的组合，其中每次选择的投影方向上，数据在这个方向上投影值的方差最大，且与前面的方向垂直。一般来说，这个投影上的方差越大，越说明数据之间的差异就越显著，从而会有更多的信息。
  当然，既然是确定方向，为了计算方便，那就应该是一个单位向量来确定(做投影的时候分母是1直接忽略)。否则的话只要这个向量本身长度很大，那投影值就会很大，从而方差可以任意大，这就失去了意义了。
  从而我们的 f f f就是一个 m ∗ n m*n m∗n的矩阵 W W W，有 z = W x z=Wx z=Wx

2.数学推导

  个人感觉李宏毅老师的推导是全网最清楚的推导之一，只要会拉格朗日乘数法，矩阵求导公式即可轻松自己推出来。
  我们可以一维一维的去看，先去看第一维(也就是选第一个方向向量)。
  在这一维中，我们要确定 W W W中的第一行 w 1 w_1 w1​，使得 z 1 = w 1 ∗ x z_1=w_1*x z1​=w1​∗x，其中 z 1 z_1 z1​是一个数值。对于k个输入，我们就希望通过找合适的 w 1 w_1 w1​，使得 z 1 z_1 z1​的方差最大，即使得 V a r ( z 1 ) Var(z_1) Var(z1​)最大。
V a r ( z 1 ) = ∑ z 1 ( z 1 − z ‾ 1 ) 2 = ∑ i = 1 k ( w 1 ( x i − x ‾ ) ) 2 = ∑ i = 1 k ( w 1 ( x i − x ‾ ) ) ( w 1 ( x i − x ‾ ) ) T = ∑ i = 1 k w 1 T ( x i − x ‾ ) ( x i − x ‾ ) T w 1 = w 1 T ( ∑ i = 1 k ( x i − x ‾ ) ( x i − x ‾ ) T ) w 1 \begin{aligned} Var(z_1)&=\sum_{z_1}(z_1-\overline z_1)^2\\ &=\sum_{i=1}^k(w_1(x_i-\overline x))^2\\ &=\sum_{i=1}^k(w_1(x_i-\overline x))(w_1(x_i-\overline x))^T\\ &=\sum_{i=1}^kw_1^T(x_i-\overline x)(x_i-\overline x)^Tw_1\\ &=w_1^T(\sum_{i=1}^k(x_i-\overline x)(x_i-\overline x)^T)w_1 \end{aligned} Var(z1​)​=z1​∑​(z1​−z1​)2=i=1∑k​(w1​(xi​−x))2=i=1∑k​(w1​(xi​−x))(w1​(xi​−x))T=i=1∑k​w1T​(xi​−x)(xi​−x)Tw1​=w1T​(i=1∑k​(xi​−x)(xi​−x)T)w1​​  中间的部分我们可以看出恰好是 n ∗ n n*n n∗n的协方差矩阵 S S S，其中 S i j S_{ij} Sij​表示输入的数据中第 i i i个维度和第 j j j个维度的协方差。
  因此我们就是要使得 w 1 T S w 1 w_1^TSw_1 w1T​Sw1​最大，且有 ∣ ∣ w 1 ∣ ∣ 2 = 1 ||w_1||_2=1 ∣∣w1​∣∣2​=1，因此我们可以使用拉格朗日法求极值，即 g ( w 1 ) = w 1 T S w 1 + α ( w 1 T w 1 − 1 ) g(w_1)=w_1^TSw_1+\alpha(w_1^Tw_1-1) g(w1​)=w1T​Sw1​+α(w1T​w1​−1)  由于 w 1 w_1 w1​也是一个向量，我们要对其中每个值都要求导来求极值，这个计算过程会用到大量矩阵和向量的求导公式，这里就略去了，没什么技术含量。
  最后我们得到有 S w 1 − α w 1 = 0 Sw_1-\alpha w_1=0 Sw1​−αw1​=0即 S w 1 = α w 1 Sw_1=\alpha w_1 Sw1​=αw1​。因此我们发现，也就是说，如果让上面的式子取极值，有 α \alpha α恰好是 S S S的特征值而 w 1 w_1 w1​恰好是 S S S的特征向量。而此时 w 1 T S w 1 = w 1 T α w 1 = α w 1 T w 1 = α w_1^TSw_1=w_1^T\alpha w_1=\alpha w_1^Tw_1=\alpha w1T​Sw1​=w1T​αw1​=αw1T​w1​=α。因此我们取最大的特征值，就可以得到我们想要的 w 1 w_1 w1​
  之后我们以此类推，可以计算后面的维度。后面第i维就是额外加了个条件，使得 w i T w j = 0 ( j < i ) w_i^Tw_j=0 (j<i) wiT​wj​=0(j<i)，即与前面的每个向量都保持垂直。
  同样使用拉格朗日乘数法，即 g ( w i ) = w i T S w i + α ( w i T w i − 1 ) + ∑ j = 1 i − 1 β j ( w i T w j − 0 ) g(w_i)=w_i^TSw_i+\alpha(w_i^Tw_i-1)+\sum_{j=1}^{i-1}\beta_j(w_i^Tw_j-0) g(wi​)=wiT​Swi​+α(wiT​wi​−1)+j=1∑i−1​βj​(wiT​wj​−0)  同样进行求导，我们得到 S w i − α w i − ∑ j = 1 i − 1 β j w j = 0 Sw_i-\alpha w_i-\sum_{j=1}^{i-1}\beta_jw_j=0 Swi​−αwi​−∑j=1i−1​βj​wj​=0。左右同时乘 w i T w_i^T wiT​，由于 w i T w j = 0 w_i^Tw_j=0 wiT​wj​=0，因此也有 S w i = α w i Sw_i=\alpha w_i Swi​=αwi​，从而就是说 w i w_i wi​也是对应的特征向量。结合我们不能重复，因此我们选当前可选的最大特征值的特征向量即可，特征向量之间必正交，也说明了我们选择的合理性。
  因此我们得到了计算矩阵 w w w的方法：首先计算协方差矩阵，之后计算对应的特征值和特征向量，取前面k个特征值的特征向量即可(实对称阵的不同特征值的向量必正交)。

3.从另一个角度看待PCA

  首先要介绍一下奇异值分解。
  对于矩阵 A m ∗ n A_{m*n} Am∗n​，必有 A m ∗ n = U m ∗ m Σ m ∗ n V n ∗ n A_{m*n}=U_{m*m}\Sigma_{m*n}V_{n*n} Am∗n​=Um∗m​Σm∗n​Vn∗n​，其中 U U U和 V V V都是正交矩阵， Σ \Sigma Σ是奇异值矩阵。
  证明： A A T = U Σ V V T Σ T U T = U Σ Σ T U T AA^T=U\Sigma VV^T\Sigma^TU^T=U\Sigma \Sigma^TU^T AAT=UΣVVTΣTUT=UΣΣTUT。而 A A T AA^T AAT是半正定阵，我们可以进行相似对角化，得到 A A T = B C B T AA^T=BCB^T AAT=BCBT，其中 B B B是正交阵而 C C C是特征值矩阵。因此我们有 U = B U=B U=B， Σ Σ T = C \Sigma \Sigma^T=C ΣΣT=C。 V V V的证法也同理。
  特别的，我们可以将奇异值矩阵压缩到 k ∗ k ( k < m i n { m , n } ) k*k(k<min\{m,n\}) k∗k(k<min{m,n})，使得 A m ∗ n ≈ U m ∗ k Σ k ∗ k V k ∗ n A_{m*n}\approx U_{m*k}\Sigma_{k*k}V_{k*n} Am∗n​≈Um∗k​Σk∗k​Vk∗n​。下面是一个简单的例子。

  我们回头再看PCA中想要做的事情，我们其实就是找一个 m ∗ n m*n m∗n的矩阵来对输入进行变化，而这个矩阵就可以看成是 m m m个长度为 n n n的向量 u i u_i ui​，每个输入与平均值的差(代表了这个输入的特征)都尽量的表示成这 n n n个向量的带权重的线性叠加。因此我们对于每个输入 x x x，就有如下的表达式： x − x ‾ ≈ ∑ i = 1 m c i u i = x ^ x-\overline x\approx \sum_{i=1}^mc_iu_i=\hat x x−x≈i=1∑m​ci​ui​=x^  我们就希望找到这组向量，使得所有的 ∣ ∣ ( x − x ‾ ) − x ^ ∣ ∣ 2 ||(x-\overline x)-\hat x||_2 ∣∣(x−x)−x^∣∣2​和最小。
  我们把所有的输入全部写出：
x 1 − x ‾ ≈ c 1 1 u 1 + c 2 1 u 2 + . . . + c m 1 u m x 2 − x ‾ ≈ c 1 2 u 1 + c 2 2 u 2 + . . . + c m 2 u m . . . . . . x k − x ‾ ≈ c 1 k u 1 + c 2 k u 2 + . . . + c m k u m \begin{aligned} x^1-\overline x &\approx c_1^1u^1+c_2^1u^2+...+c_m^1u^m\\ x^2-\overline x &\approx c_1^2u^1+c_2^2u^2+...+c_m^2u^m\\ &......\\ x^k-\overline x &\approx c_1^ku^1+c_2^ku^2+...+c_m^ku^m \end{aligned} x1−xx2−xxk−x​≈c11​u1+c21​u2+...+cm1​um≈c12​u1+c22​u2+...+cm2​um......≈c1k​u1+c2k​u2+...+cmk​um​  我们可以将其写成矩阵形式(如果没有理解，可自行转置，转置后十分好理解，这里写成这样是为了后续好操作)
[ x 1 − x ‾ x 2 − x ‾ . . . x k − x ‾ ] = [ u 1 u 2 . . . u m ] [ c 1 1 c 1 2 . . . c 1 k c 2 1 c 2 2 . . . c 2 k . . . c m 1 c m 2 . . . c m k ] [x^1-\overline x\quad x^2-\overline x\quad ...\quad x^k-\overline x]=[u_1\quad u_2\quad ...\quad u_m]\begin{bmatrix} c_1^1 \quad c_1^2 \quad...\quad c_1^k\\ c_2^1 \quad c_2^2 \quad...\quad c_2^k \\ ...\\c_m^1 \quad c_m^2 \quad...\quad c_m^k\end{bmatrix} [x1−xx2−x...xk−x]=[u1​u2​...um​]⎣⎢⎢⎡​c11​c12​...c1k​c21​c22​...c2k​...cm1​cm2​...cmk​​⎦⎥⎥⎤​
  我们观察一下矩阵的维度，发现可以简记为 A n ∗ k = B n ∗ m C m ∗ k A_{n*k}=B_{n*m}C_{m*k} An∗k​=Bn∗m​Cm∗k​，我们可以与奇异值分解 A m ∗ n ≈ U m ∗ k Σ k ∗ k V k ∗ n A_{m*n}\approx U_{m*k}\Sigma_{k*k}V_{k*n} Am∗n​≈Um∗k​Σk∗k​Vk∗n​对应，我们就可以发现这里的 B B B，也就是由 u u u组成的矩阵，就是奇异值分解中，对应着奇异值的最前面的正交矩阵 U U U，因此这里的 B B B就是 X X T XX^T XXT的前 m m m个特征值(这是 X X X的奇异值的概念)对应的特征向量。
  因此我们这样做也得到了PCA的表达式。

4.PCA的效果

  PCA对于图片等数据压缩的效果还是不错的，但是由于它是无监督学习且是线性的，因此对有标签数据的效果不如其他方法好，且无法对非线性数据进行有效的降维，后者将在下一篇非线性降维方法中讲解。

  另外PCA其实还有一个隐藏的缺点：既然名字叫“主成分分析”，那就是我们希望我们能够这样得到特征；然而实际上我们是无法达到预期效果的，如下图所示。我们可以看到每个维度都像是一个复杂的结构，而不是所谓的各个数字的特征，比如一个横线一个圈等等。

  问题就出现在PCA的约束太小，这些特征向量的方向是任意的，因此可能会出现有负值像素的向量方向；且最后线性叠加时参数也是任意，所以也可能通过取负值变成相减。这两个可取负值，就使得每张图不用再是一个个组件的叠加，完全可以是各种复杂的图加加减减得到。因此每个维度就是这样很复杂(具体表示什么不得而知)，而不是所谓的简单特征了。
  因此后来提出了一种改进PCA的方式，约束这些向量中的数字和叠加时权重必须都为非负数，称作非负矩阵分解(NMF)，这里就不多作介绍，效果如下，可见我们基本是达到了我们最初想要的效果。

三.其他线性降维方法

  这里和视频中一样，只是做一下简介。详细的内容也许以后会更新。
  1.多维尺度变换(MDS)：主要关注于如何保留初始信息，使得降维的过程中引起的变形最小。
  2.概率主成分分析(PPCA)：额外假设输入是满足一个多元高斯分布的，与降维后的维数相同，结合了PCA和GMM。
  3.核主成分分析(Kernel PCA)：类似于SVM中的核，用于进行非线性特征变换。
  4.典型相关分析(CCA)：对两组多维数据一起分析，去找到它们内部的联系。
  5.独立成分分析(ICA)：重新定义独立向量的概念，去寻找对应的互相独立的向量来进行降维，更适合于去噪等应用。
  6.线性判别分析(LDA)：是一种有监督降维方式，与PCA共同点都是要找到一组垂直的单位向量，但LDA中是使得投影中类内方差最小而类间方差最大。

四.矩阵分解

  个人感觉视频中讲的很好，这里不太想赘述太多了。
  总之对于一个“评分矩阵”这种数值可以用来代表喜欢程度的矩阵，我们可以把这个矩阵当作是已知信息，然后反推我们需要的这两个矩阵，我们恰好可以看出，如果我们要求特征是 k k k维(在这个例子中就是人物属性)，那么这恰好就是前面PCA中SVD的方法，相当于变成了一个降维问题。

  但在上文中，这个评分矩阵完全是已知的，但是在大部分情况下，这个评分矩阵很多时候不是很可靠的，甚至有很多缺失值。我们希望有一种算法， 能够同时的优化矩阵中的缺失值和特征值。这就是所谓的协同过滤算法。
  如果我们上面的矩阵中缺少一定的值，那我们就不再直接使用SVD，而是跳过没有数据的项来一项项求损失函数，即 L = ∑ ( i , j ) ( r i ∗ r j − n i j ) 2 L=\sum_{(i,j)}(r^i*r^j-n_{ij})^2 L=∑(i,j)​(ri∗rj−nij​)2，对其进行梯度下降算法即可。
  利用这种方式得到我们想要的矩阵 r r r之后，我们就可以反过来通过矩阵相乘来得到这些未知值。
  特别的，我们可以对我们的所有的参数进行正则化处理；或者是针对于每个人或者每个角色(针对于上文的例子)来额外再加入一个属于自己的参数等等，但都是些额外的处理，仁者见仁智者见智。
  利用这种算法我们可以同时的去求解并优化所有的参数。