probability principal component analysis

      PCA很有用,可以降维,也很好理解。但是有弱点不能设置参数,数据之间的某些特征也会被剔除。在PCA的基础上,有人提出了probability principal component analysis,简称pPCA。pPCA与高斯分布密切相关。所以先理解一下高斯分布。

高斯分布:

      一维的高斯分布很容易理解。这里说的Multivariate normal distribution。简单来是多维高斯分布的PDF可以表示为: f(\mathbf{x})= \frac{1}{\sqrt { (2\pi)^k|\boldsymbol \Sigma| } } \exp\left(-{1 \over 2} (\mathbf{x}-\boldsymbol\mu)^{\rm T} \boldsymbol\Sigma^{-1} ({\mathbf x}-\boldsymbol\mu)\right)其中\Sigma为协方差矩阵,因此是对称的。\mu是均值。为了直观一点,可以画出二维的图。如下。各个图的意义见参数,可以看到\Sigma\mu起到的作用。

normal distribution
normal distribution

normal distribution
normal distribution 2d

PPCA:

      PPCA的主要问题是把x转换为\mathbf{x }= \mathbf{Wz} + \mathbf{\mu} + \sigma\mathbf{\epsilon},其中x是p维的数据,z是q维向量(q<p),并且\mathbf{z} \sim N(\mathbf{0,I_p}), \mathbf{\epsilon} \sim N(\mathbf{0,I_q})。(如果不考虑\mathbf{\epsilon}就是普通的PCA,解释见slideshare)。要求就是x的最大似然。表示为

    \[L = \prod_{i=1}^{n} \cfrac{1}{|\mathbf{C}|^{1/2}}exp(-\cfrac{1}{2}(\mathbf{x_i-u})\mathbf{C}^{-1}(\mathbf{x_i-u}))\]

ML = log(L).求ML最大即可。如果光是这样事情就好办了。我们可以根据Estimation of Covariance直接得出C。但这里C是要满足一个条件。C = \mathbf{WW^T} + \sigma^2\mathbf{I_p}为什么C能这样表示,详细见论文。推倒还不是很麻烦。麻烦的是推倒p(z|x-\mu)。这里没有用到这个,在EM算法中会用到,所以先不考虑。

解法:

      解法比较多。最直接的就是求导,分别求出\mathbf{W},\sigma。还有就是EM,比较复杂,但是计算上有优势。可以证明他们等价。具体解法见笔记。最终求得

    \begin{align*} \mathbf{W} &= \mathbf{\Phi_q}(\Gamma_q-\sigma^2\mathbf{I_q})^{1/2}V^T \\ \sigma^2 &= \cfrac{1}{p-q}\sum_{j=q+1}^{p}\mathbf{\Gamma_j}\end{align*}

其中V可以是任意正交矩阵。\cfrac{1}{n}\mathbf{X^THHX}\mathbf{\Phi_q} = \mathbf{\Phi_q\Gamma_q},就是求SVD。

实验:

      实验数据是跟PCA一样的产生方法。代码见github。看了结果,第一感觉就是难以置信。虽然这是假数据。从下图可以看到整个高斯分布基本上覆盖了数据。

ppca_dis
ppca distribution

      来张透明点的,可以看到红色的是原数据。绿色的有z生成。这里我有点不能理解。虽然是把x降维了,但是跟z有什么关系啊。根据z生成出来的数据根本不是x啊。以后再想想。

ppca ppca2

后续:

      PPCA还有EM解法,等我复习了再说。还有Kernel PCA等等。有点牛啊!

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