数据压缩与特征降维

我们很希望有足够多的特征(知识)来保准学习模型的训练效果,尤其在图像处理这类的任务中,高维特征是在所难免的,但是,高维的特征也有几个如下不好的地方:

  1. 学习性能下降(知识越多,吸收知识(输入),并且精通知识(学习)的速度就越慢)
  2. 过多的特征难于分辨,你很难第一时间认识某个特征代表的意义。
  3. 最大的问题:特征冗余,如下例子所示,厘米和英尺就是一对冗余特征,他们本身代表的意义是一样的,并且能够相互转换。

特征冗余

我们先来看两个特征降维的例子,如下图所示,原来我们有两个冗余特征—厘米和英尺,现在,我们构造如下的一条绿色直线,并且使每个样本投影到该直线,则原来需要横纵两个维度表示的样本($x_1(厘米1,英尺1),x_2(厘米2,英尺2)$)现在仅需用直线上的相对位置($x_1(位置1),x_2(位置2)$)即可表示。

2D->1D

而在下面这个例子中,我们同样通过构造一个二维平面对三维特征进行投影,成功将三维特征降到二维(3D->2D)

3D->2D

综上,我们可以看到,特征降维的一般过程就是:构造低维空间 —》 将高维特征投影到低维空间

PCA(主成成分分析法)

如下图所示,我们有将近几十个特征来描述国家的经济水平,但是你仔细观察发现,这些特征其实上可以融合压缩的,最终,我们仅需要两个特征就能反映经济水平:(国家整体经济水平,个人经济状况)

国家经济水平

PCA(Principle Component Analysis,主成成分分析法)就是来完成特征降维工作的,顾名思义,其从冗余的特征序列中保留了特征的主要成分,PCA在不太大影响训练效果的前提下大幅提高整个学习系统的性能。

PCA

如上图所示,我们将蓝色线段(样本到红色直线的垂直距离)称作是投影误差(Projection Error),PCA做的就是找到低维空间并且投影特征,并使得各个特征的投影误差足够小。假设我们要将特征从$n$维度降到$k$维:PCA首先找寻$k$个$n$维向量,然后将特征投影到这些向量组成的$k$维空间,并保证投影误差足够小,下例中,为了将三维特征降到二维特征,我们就会先找寻两个三维向量$u^{(1)},u^{(2)}$,二者构成了一个二维平面,然后我们将原来的特征投影到该平面上。

PCA,3D->2D

PCA算法执行流程

(1) 数据归一化处理(mean normalization):平均各特征尺度

$$x_j^{(i)}=\frac{x_j{(i)}-\mu_j}{s_j}$$

其中,$\mu_j$为第$j$个特征的均值$s_j$为第j个特征的标准差

(2) 算法主体:假设我们将特征从$n$维降到$k$

  • 计算协方差矩阵($\sum$)
$$\sum = \frac{1}{m}\sum\limits_{i=1}^{m}(x^{(i)})(x^{(i)})^T$$

上式的矩阵表述为:

$$\sum=\frac{1}{m} \cdot X^TX$$ $$(U,S,V^T) = SVD(\sum)$$
  • U中取出前$k$左奇异向量,构成一个约减矩阵$U_{reduce}$:
$$U_{reduce} = (u^{(1)},u^{(2)},\cdots,u^{(k)})$$
  • 如此,我们就得到了压缩后的特征向量$z$为:
$$z^{(i)}=U_{reduce}^T \cdot x^{(i)}$$

从PCA压缩后的数据进行修复

因为PCA仅保留了特征的主成分,亦即PCA是一种有损的压缩方式:

$$z = U_{reduce}^Tx$$

修复$x$:

$$x_{approx}=U_{reduce}z$$

如下图所示,我们不可能从压缩后的特征完美还原到原特征,但由于PCA尽可能地减小了投影误差,所以还原后的特征也近似于原特征了。

PCA降维前

特征修复

降到多少维度才是合适的(k值的确定)

PCA做到了特征降维,但维度显然也不是被降得越小越好,亦即,在剩下的主成分特征中,各个特征间的差异需要足够大(亦即特征冗余足够小),我们通过如下方式评估特征差异性:

  • 求各样本的投影均方误差:
$$\min\frac{1}{m}\sum\limits_{j=1}^{m}||x^{(i)}-x_{approx}^{(i)}||^2$$
  • 求数据的总变差:
$$\frac{1}{m}\sum\limits_{j=1}^{m}||x^{(i)}||^2$$
  • 评估下式是否成立:
$$\frac{\min\frac{1}{m}\sum\limits_{j=1}^{m}||x^{(i)}-x_{approx}^{(i)}||^2}{\frac{1}{m}\sum\limits_{j=1}^{m}||x^{(i)}||^2} \leq \epsilon$$

其中,$\epsilon$的取值可以为$0.01,0.05,0.10,\cdots$,假设$=0.01$,我们就说$99\%$的差异性得到保留”

不要滥用PCA

由于PCA减小了特征维度,因而也有可能带来过拟合的问题。所以PCA并不是必须的,所以在机器学习中,我们并不是一开始就需要做PCA,尽在学习算法运行速度不理想时再考虑使用PCA。