Principal component analysis

原理介绍:

       PCA (Principal Component Analysis),可以算无监督学习的一种。我觉得理解了还算是简单的。PCA主要做的事抽取重要的特征,放弃细节。这样做的目的是为下一步的机器学习做准备。比如一张脸原来是32*32 = 1024的,通过PCA转换成10*10 = 100的向量,这对大量数据来说,是非常可观的。 可以提高计算效率。

        那么PCA是以什么标准衡量哪些特征是重要的呢?可以看看这个资料,但我觉得这个有点不直观,不过步骤很清晰。直观的解释还是从Coursera上得到的。这个解释,我觉得很可以接受。

       比如,现在有m组数据,维度为n,X_{m,n}。然后要找另一组基U_{n,p},将m组数据投影到U_{n,p}空间,Xreduce_{m,p} = X_{m,n}*U_{n,p},使下式值最小。就是Frobenius_norm最小。

    \[\sum\limits_i\sum\limits_j (X_{i,j}-(Xreduce_{m,p} * U_{n,p}^T) _{i,j})^2\]

        这就是要满足的条件,看看这个条件好像似曾相识啊,本来我还在想怎么证明后面的结论,后来发现这原来就是Eckart-Young Theorem。所以结论就有了,取最大的p个特征值对应的向量。而且这个最小值,就是余下的特征值之和。

    \begin{align*} &X^T*X = U\LambdaU^T \\ &U_{n,p} = U(:,1:p) \end{align*}

        然后就可以计算Xreduce_{m,p} = X_{m,n}*U_{n,p},而Xrecover_{m,n} = Xreduce_{m,p}*U_{n,p}^T。为什么这样就是恢复出来的数据呢,可不是下标对上就ok的。回想一下,线性变换变换矩阵。可以这样想,U_{n,p}代表的是一个子空间,然后Xreduce_{m,p} = X_{m,n}*U_{n,p}就是在U_{n,p}中的投影,然后Xreduce_{m,p} = X_{m,n}*U_{n,p},则把对应X空间的相应坐标还原。。坑爹我讲不清。可以用先用一维的X做做实验,就明白这个过程了。

小试牛刀:

        所以至此,原理已经解决。可以看看PCA的运用情况。首先是玩玩。下面左图是原始数据,绿线就是求出的特征向量方向。一共有两根,长的那根就是主向量。应用PCA处理后得到有图,可以看到这些数据的协方差很小,基本不相关。这也是PCA的另一个解释。

origin cov

人脸特征:

        人脸的数据也是从Coursera上的Ng的课程中获得的。一共5000个数据,每个32*32。根据Ng的说法,应用PCA之前,要先对数据预处理,即中心化和”归一化”,大概可能会影响特征值的大小,我没有深入了解为什么这么做。反正我照做了。下图即为PCA处理之后的结果。几乎看不出特征损失,但确实很多细节没有了。具体代码和数据github

recoverface
Recovered Face
originface
Origin Face

人脸向量:

        PCA不是有向量吗?上面也是取了前一百个向量来表示投影人脸数据。想象一下,这一百个向量,都是1024维的,代表的也是原空间的一组向量,可以说,这些向量可能就是一张脸。然后每张脸可以投影过去,再投影回来。所以就画画看这一百个向量长什么样。如下,果然就是人脸的特征。神奇!

principalface
First 36 Vectors

注意事项:

      PCA有个前提,就是数据能在线性空间中表示。像以下的数据是不能直接使用PCA的,要用Kernel PCA。Kernel还是有点难理解的,下次搞明白了单独谈。PCA还有probability pca,蛋碎。

Kernel_pca_input
Input points before kernel PCA From:Wikipedia
734px-Kernel_pca_output_gaussian
After Gaussian kernel PCA From:Wikipedia

Eckart–Young theorem (低维矩阵近似)

       Eckart–Young theorem讲的是有一个矩阵M,找到另一个rank为r(小于M的rank)的矩阵N,使得\sum\limits_i\sum\limits_j (M_{i,j}-N_{i,j})^2 最小。其实是Frobenius norm

      解法是对M进行SVD后得M=U\sum V^*,取前r个最大的特征值和对应的特征向量,即:N = U\sum_r V^*。为何这样做之后|| M -N ||_F最小,可以见课堂笔记。主要是使用了Lagrange Multiplier。以下为实例代码。

      使用Octave计算后,可得如下结果示意图,可见,误差很小。代码见github。图中绿色为结果,蓝色为原始点。

EckartYoung

       后来作业里有一个要求,1_n^T*N = 0,即满足N列均值为0。条件强了很多,所以结果就不好了。图中绿色为结果,蓝色为原始点。

hw

 

参考资料:

  1. SVD
  2. Moreau Envelopes

 

MDS 多维标度法

       现在有一些点,把他们表示成矩阵X,然后很容易就能求出他们的距离矩阵D。反过来,给出距离矩阵求点,就不是那么容易的事。这个问难我初中就觉得很难,最近机器学习课上,老师意外的讲到了一个算法CMDS,解决了我的问题。

      Multidimensional scaling (MDS), 说白了就是给你距离矩阵算点,我们知道这有无数个解(如果有解)。matlab和octave都有内置算法,cmdscale。因为我最讨厌只讲理论不实践的人,当然没办法实验的除外,比如爱因斯坦偶像。所以我就使用octave实现了一下mds。

      具体算法以及为何这么算,见github。我没有办法,在这里把公式全部打出来。下面是算法核心:

       另外这个算法不局限于从距离算点。而且不一定是欧式距离。在机器学习中,有这样一种情形:有很多数据,都是关于某些物体的相似度(距离),我们抽取一些特征,把这些特征在低维空间表示。比如有100种酒,品酒师给出两酒之间的相似程度,然后使用mds算法,算出向量矩阵,一般维数都会降低不少(也就是可以用作降维)。在此基础上统计研究,就方便多了。

      来看一个结果,多么美丽! 刚开始我以为得出的结果只会旋转,没想到还会镜像。。mds_mirror

 

链接:

  1. 台湾清华大学课程