【西瓜书】第十章 降维与度量学习

显然可以看出, k近邻方法没有显式的训练过程, 它是懒惰学习的著名达标,训练时间开销为零.

k近邻学习中两个重要的点:

假设我们固定住第二点, 并设$k=1$, 来讨论一些这种最近邻分类器在二分类问题上的性能. 此时我们给定测试样本$x$, 并设其最邻近样本为$z$, 则容易得出分类器出错概率为:

假设样本独立同分布, 且对任意$x$和任意小正数$\delta$, 在$x$附近$\delta$距离范围内总能找到一个训练样本. 令$c^*=arg \max_{c\in Y}P(c|x)$表示贝叶斯最有分类器的结果, 则可以推导出:

这表示 最近邻分类器的泛化错误率不超过贝叶斯最有分类器错误率的两倍 .

缓解维数灾难的一种方法就是 降维 , 又称 维数约简 , 即将原始高维属性空间转变成一个低维子空间.
降维的依据在于, 虽然数据样本是高维的,但是与学习任务密切相关的也许仅仅是某个低维分布.

令 $B=Z^TZ\in \mathbb{R}^{m\times m}$, 其中$B$为降维后样本的内积矩阵, $b_{ij}=z_i^T$, 那么有:

为了简化推导, 假设我们已经中心化了样本$Z$, 则推导后可以得到:

由此可以利用降维前的距离矩阵$D$来求降维后的内积矩阵$B$, 并对其做特征值分解$B=V\Lambda V^T$, 其中$\Lambda$ 为特征值组成的对角矩阵, $V$为特征向量矩阵. 假设其中有$d $个非零特征值, 它们组成的对角矩阵$\Lambda $和特征向量矩阵$V*$则有以下关系:

实际中, 为了有效降维(降到$d’$), 则不一定要求降维后的距离严格相等, 此时取前$d’$个非零特征值对应的$\tilde{\Lambda}$和$\tilde{V}$:

除了MDS, 线性变换降维是最简单的降维方法, 这类方法被称作 线性降维方法 , 例如下面要介绍的PCA主成分分析.

假设我们的样本数据都做了均值归一化，那么所有样本点投影后的方差就是$\sum W^Txx^TW$, 其中$W$是变换矩阵。 那么，优化的目标就是：

对上式用拉格朗日乘子法得到：

那么，对协方差矩阵$XX^T$做特征值分解，将求得的特征值排序，取前$d’$个特征值构成的特征向量构成$W$，就得到PCA的解，维数由$d$降到了$d’$。 这里的$d’$值可以人工指定，也可以通过其他开销小的学习器来交叉验证。或者通过重构阈值来设定，例如设$t=95%$,选择合适的$d’$使得

当然，降维不可避免地会丢失一些信息，但是样本有用信息的密度增大，同时也会一定程度的降噪，从信息论的角度来说，数据的信噪比提高了。
然而， 需要注意的是 ， PCA在分类领域往往起到的作用很小，因为虽然它保留了大部分的信息，但是被它抛弃的可能往往是那些能够起到区分作用的信息，例如，字符识别中的O和Q，PCA很可能会丢去掉右下角那个“尾巴”的特征。适当留意它和LDA线性判别的区别，二者一个是寻找能够最大保留信息的主轴方向，一个是用来寻找最有效分类的方向。

另外, 我们这里可以看到, PCA对协方差矩阵$XX^T$做特征分解, 前面的MDS可以看做是对$X^TX$(内积)做特征分解, 因此二者互为对偶方法.

书中给出了核化主成分分析算法(KKPC)

下面介绍两种流形学习的方法.

为了解决该问题, Isomap利用近邻点来计算两点距离,那么计算测地线距离的问题就转变为计算近邻接图上两点的最短路径问题(该问题可以用Dijkstra或者Floyed算法解决), 得到任意两点距离后, 就可以通过前面的MDS算法来获得样本点在低维空间的坐标.
具体算法如下:
Isomap算法

这里需要注意的是, Isomap仅仅得到了训练样本在低维空间的坐标, 但是对于新样本, 如何进行映射呢, 一种常用的做法是训练一个基于训练样本高维坐标和低维左边的回归器, 并应用于新数据. 当然这么做只是一个权宜之计, 但是目前并没有更好的方法.

最近邻图的构建有两种方法:

当近邻范围过大, 则距离很远的点也可能会被误认为近邻, 从而出现短路问题; 当范围过小, 则图中有些区域和其他区域可能不存在连接, 则出现断路问题.

LLE希望这个性质能在低维空间中得以保持. 那么对于每个$x_i$, LLE会根据近邻样本计算出线性重构的系数$w_i$ (拉格朗日乘子法).
然后该性质在低维空间保持$w_i$不变, 接着就要确认$x_i$对应的低维空间坐标$z_i$, 通过前面算出来的$w$组成的$W$,令:

接着, 对$M$做特征值分解, 最小的$d’$个特征值对应的特征向量就组成了$Z^T$. 具体推导过程就不赘述了,那么LLE算法就可以描述如下:
LLE算法

显然, 对于任何$x$, 不在其邻域内的变动都不会对$x$及其对应的$z$产生影响,这种将变动限制在局部的思想在很多方法都有用.

我们这里就需要一个可以调节的参数来对度量进行学习, 对于欧式空间而言, 其平方距离可以写作:

我们设定每个属性的权重为$w$, 权重矩阵即为$W$, 那么重新定义距离:

其中$W$是一个对角矩阵. 此时我们可以通过学习来确定$W$.

更进一步的, 我们取消$W$的对角矩阵限制(即属性之间无关, 互相正交的假设), 令其为一个半正定矩阵$M$, 于是就得到了马氏距离:

其中$M$就叫做度量矩阵, 为了保证距离的非负和对称, 它必须是一个(半)正定对称矩阵, 即$M$可以以正交基的形式重写为$M=PP^T$.

下面我们以近邻成分分析为例来介绍如何学习$M$.

假设以留一正确率作为最大化, 即计算样本除了被自身以外所有样本正确分类的概率:

其中$\Omega_i$表示和$x_i$属于相同类别的样本的下标集合, 则整个样本集上留一法正确率为:

最后代入可以得到NCA总的优化目标为:

可以用梯度下降求解出度量矩阵$M$.

此外, 除了用监督学习的错误率作为优化目标, 可以引入领域知识, 利用pair-wise的必连/勿连约束来优化.

最后用一张图来汇总一些降维方法: