Note sth about PCA(Principal Component Analysis)
ML6月20日就要考试了，准备日更博客，来记录复习一下这次ML课所学习的一些方法。
博客是在参考老师的ppt，以及戳这里，学习播客之后完成的，主要运用ppt的公式，因为博客公式自己链过去就可以看了（;_;）。
看学习博客的时候，发现它内附了另一篇作者自己的文章，和我微信公众号看到的几乎一模一样。？？？可是作者不是同一个人
动机：
PCA的中文名字——主成分分析。顾名思义，是分析主成分的，何为主成分？那是一个事物组成部分里面为主的成分，至少从我的角度来说开始离题，我区分PCA和LDA（之后会更）的方法就是如此。PCA本身不能做分类（当然可以拿它降维完的特征再进一步进行分类），而LDA最直观的直接分类就是在两类的时候，LDA转换完的特征值可以直接分类（一正一负）。离题结束PCA能的最主要的事情大概就是降维了，这也就是PCA的动机。
PCA算法：
首先，需要明确的是，PCA是根据方差来降维的，假设我们有个N维的向量，我们想降维到k维（k<=N），那么我们应该如何操作？降维至k，其实就是拿k个轴去表示目前的N维特征，显然不一定能够完全表示，但是丢失少量的信息是我们完全可以接受的（参考Subsampling）。那我们是不是第一次应该求出方差最大的轴，那第二次呢？我们应该求出方差次次大的轴！没错，但是约束条件是，第二次的轴必须和第一次的正交（参考XOY坐标系），那么第三个其实就是在垂直前两个轴所组成平面的平面上，方差最大的轴。显然，操作k次之后便得到了k个特征。这里有一种直观感受——如果样本是二维的，并且空间分布为一个椭圆，那么第一次的轴就是实轴，如果还要求第二次的话就是虚轴。
其次，考虑一下方差，方差其实是一维特征的东西，推到高维，计算的应该是协方差。思考一下，互不相关的轴、从大到小的（协）方差。是否可以求出样本的协方差矩阵，最后求得这个矩阵的特征值与特征向量，然后取k个，就是所求答案？答案是肯定的。
算法公式概述：
$$ X in R^{N * m} $$
$$ overline{x} = frac{1}{m} sum_{i=1}^{m} x_i $$
$$ Sigma = frac{1}{m} sum_{i=1}^{m} (x_i-overline{x})(x_i-overline{x})^T $$
$ {lambda_i, mu_i} $ the top k principle components(eigenvalue, eigenvector) and i = 1,2,......,k
问题：
我们不难发现，将N维特征降至k维的方法很好，但也有一个很容易考虑到的问题，k是多少？显然，k越大，我们提取的特征就越接近原来的样本，可是这样就失去了降维的意义；而如果k过小，这样一来我们抓住了重点，可却也只抓住了重点，如果大家在重点上都表现得很好，那么又失去了区分度（类似于考试重点题，大家都会做）。于是乎我看到了老师与博客的不同，先说博客的：试，调节一个阈值去尝试然后评估，最后确定k之。显然可行，也非常符合我的考虑。但是我瞄到了老师的处理方法，发现老师运用了一个很寻常，但是式子很好看的方法——拉格朗日乘子法。为什么可以用拉格朗日乘子法？其实这需要将问题做一些转化，描述如下。
用拉格朗日乘子法解决找k的问题：
$$ x in R^N $$
$$ X = [x_1,x_2,......,x_m] in R^{N * m} $$
$$ U = (mu_1,mu_2,......,mu_n) in R^{N * N} $$
$$ y = Ux $$
$$ x = U^Ty = sum_{i=1}^{N} mu_i y_i $$
$$ widehat{x} = sum_{i=1}^{M} mu_i y_i, (M leq N) $$
$$ epsilon = E{ || x - widehat{x} ||^2 } = frac{1}{m} sum_{j=1}^{m} || x_j - widehat{x_j} || $$
GOAL：
$$ arg min epsilon^2, s.t U^T U = I_N $$
从这里我们可以看出，我们得到了一个优化目标argmin也得到了一个约束条件s.t，那么接下来就是拉格朗日乘子法的过程了。将$epsilon$展开会发现，$epsilon^2 = sum_{i=M+1}^{N} mu_i^TSigmamu_i$，之后结合约束以及拉格朗日乘子法的过程，我们得到：$$ L = epsilon^2 - sum_{i=M+1}^{N} lambda_i(mu_i^Tmu_i-1) $$
之后用L对$mu$求偏导，得到：$ frac{partial L}{partialmu_i} = [2Sigmamu_i-2lambda_imu_i] = 0 $
现在形式就非常明显了——$ Sigmamu_i = lambdamu_i $，解出特征值，特征向量就结束了。
其实，PCA在我看来说白了就是一句话：在方差最大的方向上（信号学相信样本是方差大的，而噪声是方差小的为什么？？？），选择一根轴，使得样本到轴的投影距离之和最小。