Fisher’s linear discriminant

      Fisher’s linear discriminant通常也被称为Linear discriminant analysis (LDA)。LDA的目标是在保持类别信息的基础上降维。这跟PCA以及Factor analysisi很相似,都是降维。值得注意的是,LDA是完全不同的效果。而且LDA是监督学习。

原理介绍:

      先定义两个方差。

    \begin{align*} between-class \quad covariance:\quad\quad & S_b = \sum\limits_{j=1}^c n_j*(m_j - m)*(m_j - m)^T       \\ with-in \quad class\quad covariance:\quad\quad &S_w = \sum\limits_{j=1}^c\sum\limits_{i\in V_j} (x_i-m_j )*(x_i-m_j)^T  \end{align*}

      看起来很复杂。其实就是求方差。第一个求的是每个分类之间的方差,m = \sum\limits_{i=1}^n x_i是所有数据的均值。m_j =\cfrac{1}{n_j} \sum\limits_{i\in V_j} x_i是某类别内的均值。n_j指j类中数据量。

      目标是y = W^TX,这个W要使得J(W) =tr(\cfrac{W^T*S_b*W}{W^T*S_w*W})最大。为什么最大就可以了呢。简单的说就是每个类的内部方差要尽量小,类之间的方差要大。详细推导见链接。

解法:

      过程有点麻烦,反正是根据拉格朗日来的。可以见笔记。解为S_b*W = S_w*W*\Lambda。这个方程叫Generalized eigenvalue problem。解法有很多。老师提到了一本叫 Matrix Computations的书,据说会让人很爽,里面有详细的说明。最简单的方法,是直接求S_t=S_w+S_b伪逆,就算S_t不可逆,这也是精确解。原式就变为pinv(S_t) * S_b*W = W*\Lambda,这个就熟悉了,直接SVD即可。

实验:

      no try no high! 果断来一发。首先假设有两类,这个有助于理解为什么这么做。没有必要两个类别中的数据量一样。写起来方便就设成一样了。可以看到效果如下图。可以看到这两个类还是有明显的界限的。

lda
2 class lda

      这个2类的不好玩啊。我曾经在2维数据上分5类,后来发现傻逼了。LDA做不了这事。LDA是降维到c-1。所以只能3类个3维数据到2维了。否则没法画啊。具体代码见github。效果如下。

origin
LDA Origin Class

projection projection2

PCA vs LDA:

      最直观的解释如下所示:

pcavslda
pca vs lda. From:LSV

      PCA是抽取主要的特征,要取方差最大的方向,不管类别间的差别。而LDA则是根据类别来降维。有本质上的区别。可以看一下3维数据在PCA和LDA方法下的结果。

pca-vs-lda
pca vs lda

Fisher:

      Ronald Aylmer Fisher在统计方面贡献很大。他设计了一个随机实验叫Lady Tasting Tea,是在一本名为《The Design of Experiments》书中提到。然后我们上课的老师说Fisher写了一本书叫《The Lady Tasting Tea》,其实不是他写的,但根据评论来看确实是一本好书,介绍了统计学的发展。

链接:

  1. PCA and LDA, PCA and LDA
  2. Linear discriminants analysis
  3. Fisher Origin Paper

 

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