降维与度量学习

k近邻学习(KNN)

KNN与Kmeans不同是一种常用的监督学习方法，其工作机制非常简单:给定测试样本,基于某种距离度量找出训练集中与其最近的k个训练样本，然后基于这k个”邻居”的信息来预测.通常，在分类任务中可使用”投票法”,即选择这k个样本中出现最多的类别标记作为预测加过;在回归任务中可使用”平均法”,即将这k个样本的实值输出标记的平均值作为预测结果

在该算法中暂且假设距离计算是“恰当”的,即能够恰当地找出k个近邻。我们来对最近邻分类器(1NN,k=1)在二分类问题上的性能做一个简单的讨论.

给定测试样本x,若其最近邻样本为z,则最近邻分类器出错的概率就是x与z类别标记不同的概率,即

$P(err)=1-\sum_{c∈Y}P(c|x)P(c|z)$

假设样本独立同分布,且对任意x和任意小正数$\delta$,在x附近$\delta$距离范围内总能找到一个训练样本;换言之,对任意测试样本,总能在任意近的范围内找到上式的训练样本z,令$c^* =arg max_{c∈Y}P(c|x)$表示贝叶斯最优分类器的结果,有

$P(err)=1-\sum_{c∈Y}P(c|x)P(c|z)≤1-P^2(c^* |x)≤2×(1-P(c^* |x))$

于是我们得到了结论:最近邻分类器虽简单,但它的泛化错误率不超过贝叶斯最优分类器的错误率的两倍.

低维嵌入

许多学习方法都涉及距离计算,而高维空间会给距离计算带来很大的麻烦,例如当维数很高时甚至连计算内积都不再容易.
事实上,在高维情形下出现的数据样本稀疏、距离计算困难等问题,是所有机器学习方法共同面临的严重障碍,被称为”维度灾难”

缓解维数灾难的一个重要途径是降维，亦称”维数约简”,即通过某种数学变换将原始高维属性空间转变为一个低维“子空间”,在这个子空间中样本密度大幅提高,距离计算也变得更为容易.为什么能进行降维？这是因为在很多情况,人们观测或收集到的数据样本虽是高维的,但与学习任务密切相关的也许仅是某个低维分布,即高维空间中的一个低维”嵌入”(embedding).

若要求原始空间中样本之间的距离在低维空间中得以保持,即得到”多维缩放”(MDS),这是一种经典的降维方法。

假定m个样本在原始空间的距离矩阵为D∈$R^{m×m}$,其第i行j列的元素$dist_{ij}$为样本$x_i$到$x_j$的距离。我们的目标是获得样本在d’维空间的表示Z∈$R^{d’×m}$,d’≤d,且任意两个样本在d’维空间中的欧氏距离等于原始空间中的距离，即$||z_i-z_j||=dist_{ij}$

MDS算法的具体流程是:

对映射到X空间的m个样本的数据集,可轻易计算任意样本$x_i$到$x_j$之间的距离构成m×m大小的距离矩阵D,其中$d_{ij}$代表样本$x_i$到$x_j$的距离
因为假设样本映射到低维空间Z后距离相等,那么映射后任意两个样本$z_i$和$z_j$的内积可以通过之前的距离矩阵D来计算得到,此时算出低维空间映射后的m×m的内积矩阵B
通过内积矩阵B进行特征分解,可以得到一组特征值和特征向量,取最大的d’个特征值构成的对角阵A和对应的特征向量矩阵V
通过对角矩阵A和特征向量矩阵V，我们可以得到原始样本在低维d’空间上的映射

对降维效果的评估,通常是比较降维前后学习器的性能,若性能有所提高则认为降维起到了作用.若将维数降至二维或三维,则可通过可视化技术来直观地判断降维效果。

主成分分析(PCA)

PCA是一种最常用的降维方法.在介绍PCA之前,不妨先考虑这样一个问题:对于正交属性空间中的样本点,如何用一个超平面(直线的高维推广)对所有样本进行恰当的表达？

容易想到,若存在这样的超平面,那么它大概应具有这样的性质:

最近重构性：样本点到这个超平面的距离都足够近
最大可分性:样本点在这个超平面的投影能尽可能分开
注意在进行PCA之前一定要做中心化,即$\sum_ix_i=0$.

假定数据中心化后,进行投影变换后得到的新的坐标系为${w_1,w_2,…,w_d}$,其中$w_i$是标准正交基向量,$||w_i||_ 2=1,w_i^Tw_j=0(i≠j)$。若丢弃新坐标系中的部分坐标,即将维度降低到d’＜d,则样本点$x_i$在低维坐标系中的投影是$z_i=(z_{i1};z_{i2};…;z_{id’})$,其中$z_{ij}=w_j^Tx_i$是$x_i$在低维坐标系下第j维的坐标.若基于$z_i$来重构$x_i$,则会得到$\hat{x}_i=\sum_{j=1}^{d’}z_{ij}w_j$
考虑整个训练集,原样本点$x_i$与基于投影重构的样本点$\hat{x}_i$之间的距离为

$\sum_{i=1}^m||\sum_{j=1}^{d'}z_{ij}w_j-x_i||_ {2}^2=\sum_{i=1}^mz_i^Tz_i-2\sum_{i=1}^mz_i^TW^Tx_i+const$

上式正比于$-tr(W^T(\sum_{i=1}^mx_ix_{i}^T)W)$
根据最近重构性,上式应该被最小化,考虑到$w_j$是标准正交基,$\sum_ix_ix_{i}^T$是协方差矩阵,有

$min_W -tr(W^TXX^TW)$ $s.t. W^TW=I$

这就是主成分分析的优化目标.

PCA仅需保存W与样本的均值向量即可通过简单的向量减法和矩阵-向量乘法将新样本投影至低维空间中.显然，低维空间与原始高维空间必有不同，因为对应于最小的d-d’个特征值的特征向量被舍弃了，这是降维导致的结果

核化线性降维

线性降维方法假设从高维空间到低维空间的函数映射是线性的,然而在不少现实任务中，可能需要非线性映射才能找到恰当的低维嵌入.

上图为一个例子,样本点从二维空间中的矩形区域采样后以S形曲面嵌入到三维空间，若直接使用线性降维方法对三维空间观察到的样本点进行降维,则将丢失原本的低维结构。为了对”原本采样的”低维空间与降维后的低维空间加以区别,我们称前者为”本真”低维空间.

非线性降维的一种常用方法,是基于核技巧对线性降维方法进行”核化”。
假定我们将在高维特征空间中把数据投影到由W确定的超平面上,即PCA欲求解

$(\sum_{i=1}^mz_iz_i^T)W=\lambda W$

其中$z_i$是样本点$x_i$在高维特征空间中的像.易知,

$W=\frac{1}{\lambda}(\sum_{i=1}^mz_iz_i^T)W=\sum_{i=1}^mz_i\frac{z_i^TW}{\lambda}=\sum_{i=1}^mz_iα_i$

可以对上述方法进行核变换

$(\sum_{i=1}^m\phi(x_i)\phi(x_i)^T)W=\lambda W$

进一步变换为$W=\sum_{i=1}^m\phi(x_i)α_i$
这里引入的核函数为:

$K(x_i,x_j)=\phi(x_i)^T\phi(x_j)$

化简得到

$KA=\lambda A$

流形学习

流形学习是一类借鉴了拓扑流形概念的降维方法.“流形”是在局部与欧氏空间同胚的空间,换言之,他在局部具有欧氏空间的性质,能用欧氏距离来进行距离计算.这给降维方法带来了很大的启发:若低维流形嵌入到高维空间中,则数据样本在高维空间中的分布虽然看上去非常复杂,但在局部上仍具有欧氏空间的性质,因此，可以容易地在局部建立降维映射关系，然后再设法将局部映射关系推广到全局。当维数被降至二维或三维时，能对数据进行可视化展示,因此流形学习也可被用于可视化

Isomap
认为低维流形嵌入到高维空间之后,直接在高维空间中计算直线距离具有误导性，因为高维空间中地直线距离在低维嵌入流形上不可达的.低维嵌入流形上两点间的距离是”测地线”距离。