1. 章节主要内容

本章的主要内容是降维与度量学习，这是机器学习领域很重要的一块内容。在进入具体的介绍之前，对降维与度量学习不清楚的小伙伴们其实可以尝试从字面意思上理解一下降维与度量学习是干什么的，而它们又与机器学习有什么关系。

我相信看过科幻小说的人，应该都对降维度打击这个概念不陌生吧，在某些科幻小说中，生活在更高维度的外星人可以通过降低自己的维度来打击低纬度的生命体，而这种方式的打击由于带有部分高纬度的特性，所以低纬度的生物往往很难抵抗（虽然也有的科幻文章说高纬度的生物是无法直接接触到低纬度生命的，这里不做争论）。基于同样的理解，在机器学习领域中，我们是否也可以通过降低维度来获得某种优势呢？抱着这样的疑问，我们进入这一章的内容吧。

1）在开始真正介绍降维和度量学习之前，我们先来了解一个简单的机器学习算法：k 近邻学习

k 近邻（k-Nearest Neighbor，简称kNN）学习是一种常用的监督学习方法，其工作机制非常简单：给定测试样本，基于某种距离度量找出训练集中与其距离最近的 k 个样本，然后基于这 k 个邻居的信息来进行预测。通常可以通过“投票法”或“平均法”来对测试样本进行预测（详情请查看第八章集成学习）。

kNN学习算法的一个特点是它并不需要提前对模型进行训练，只在预测时对训练样本进行计算即可得到预测结果，这是一个典型的“懒惰学习”的算法。下图是一个 kNN 学习算法的示意图：

显然，k的选择十分重要，因为不同 k 的选择会导致预测的结果截然不同，同样的，不同的距离度量方式也会因为选择的邻居不同而导致截然不同的结果。

我们在第一节介绍 kNN 学习的原因在于它的一个性质，那就是如果满足在任意小距离内有一个样本的条件时，其错误率最差不超过最优贝叶斯分类器错误率的两倍。

对于这么简单的一个学习算法，竟然最差错误率不超过贝叶斯最优分类器错误率的两倍，关键这个学习算法还不用提前训练，多么美好呀！

可惜，这个性质是建立在一个假设上的，那就是在任意小距离内测试样本都能找到一个邻居，而要满足这个条件可不是那么容易的。这个不容易性可是和我们这章的主要内容“维度”息息相关的呢！

2）属性数量线性提升带来的困难程度的指数提升问题：维度灾难

对于上节的假设条件，如果归一化后在0.001的距离内都有一个邻居结点的话，我们需要1000个样本数量平均分布到样本空间中才可行，这是属性数量为1的情况。当属性数量为20时，我们需要1000的20次方也就是10的60次方的数据量，这是个天文数字，这个数量级的数据是不可能获得的，更不要说在实际应用中样本的属性可能成千上万。

在高维情形下出现的样本稀疏、距离计算困难等问题，是所有机器学习方法共同面临的严重障碍，被称为“维度灾难”（curse of dimensionality）

缓解维数灾难的一个重要途径是降维（dimension reduction），亦称“维数约简”（在第11章会介绍另一个重要途径：特征选择），即通过某种数学变换将原始高维属性空间转变为一个低维子空间，在这个子空间中样本密度大幅提高，距离计算也变得更加容易。

为什么能降维？这是因为在很多时候，和学习任务密切相关的只是属性空间的某个低维分布，即高维空间的某个低维嵌入。下图给了一个直观的例子，原始高维的样本点在低维空间中更容易学习

若要求原始空间中样本之间的距离在低维空间中得以保持，即得到“多维缩放”（Multiple Dimensional Scaling，简称MDS）这样一个经典的降维方法。

多维缩放的目标是通过缩放后，样本在新的低维空间上的欧式距离和其在原始空间的距离相等

在现实中为了有效降维，往往仅需降维之后的距离与原始空间中的距离尽可能的相近，而不必严格相等。

MDS算法的具体流程是：

［1］对映射到 X 空间的 m 个样本的数据集，可轻易计算任意样本 xi 到 xj 之间的距离，构成 m*m 大小的距离矩阵 D，其中 dij 代表样本 xi 到 xj 的距离

［2］因为假设样本映射到低维空间 Z 后距离相等，那么映射后任意两个样本 zi 和 zj 的内积可以通过之前的距离矩阵 D 来计算得到，此时算出低维空间映射后的 m*m 的内积矩阵 B

［3］通过对内积矩阵 B 进行特征分解，可以得到一组特征值和特征向量，取最大的 d' 个特征值构成的对角矩阵 A 和对应的特征向量矩阵 V

［4］通过对角矩阵 A 和特征向量矩阵 V，我们可以得到原始样本在低维 d' 空间上的映射

个人想法：MDS算法实际上在降维之前就进行了大量的距离、内积计算，这在数据样本和属性维度都十分大时是很耗资源和时间的，所以对于维度灾难来说，MDS的缓解作用并不大。

一般来说要获得低维子空间，最简单的是对原始高维空间进行线性变换。个人想法：这个线性变换的过程在机器学习领域十分的常见，无论是线性回归算法、支持向量机还是神经网络都有用到线性变换。以神经网络来比喻我们这里的降维算法，将 d 维的属性样本降维到 d' 维的属性空间上，其实等同为输入神经元为 d 个、输出神经元为 d' 个的浅层神经网络结构，借用一下第五章的图解释一下

降维后的每个新的属性 x' 其实是高维属性 x1、x2、...、xn 根据权重 W 的线性组合。这种基于线性变换进行降维的方法称为线性降维方法，对低维子空间的性质有不同的要求，相对于对权重 W 施加了不同的约束。对降维效果的评估，通常是比较降维前后学习器的性能，若性能提升了则认为降维起到了效果。

3）一种常用的线性降维方法：主成分分析（Principle Component Analysis，简称PCA ）

主成分分析法是最常用的一种降维方法，它是基于这样的核心思想来设计的：对于一组样本，如果存在一个超平面使得样本在上边的距离都足够近或者投影都尽可能分开，那么这个超平面是对这组样本的一个很恰当的表示。

那么这个超平面本身可以被看作是降维的目标空间，记该超平面由 n 维的正交基向量构成的矩阵 W = {w1,w2,...,wn}，那么主成分分析降维法就是要找到这组正交基向量。

那么这组基向量我们应该怎么求呢？这里用到了一个在机器学习算法中常用的逻辑：既然降维变换到的超平面能很好的代表样本数据，那么我们从超平面上映射回到原始空间中的点应该与没映射之前的点距离相近。我们可以通过最小化这个变化误差来算得最佳的正交基向量矩阵 W

这种选择逻辑在之前的机器学习算法中也有出险，比如在神经网络那一章的

Boltzmann机算法，其训练过程就是依照着这同样的逻辑，其训练过程（对比散度 Contrastive Divergence 算法）如下：通过输入层算出隐层分布，再通过隐层分布重新算出输入层的新分布；并利用新分布与旧分布之间的差别调整连接权重。

幸运的是，在这里我们不需要反复的调整权重来找到最佳的 W，通过课本中的公式计算可知，我们可以通过对样本 X 的协方差矩阵进行特征分解来求得 W。

特征值越大，说明该特征向量对应的是方差变化越大的方向，针对这个方向进行分解将能更好的表示样本数据。所以，如果我们要降维到 d' 维度的话，我们只需要取出排序最高的 d' 个特征向量 (w1, w2,..., wd') 即可。这里 d' 的取值由用户事先决定，我们可以通过交叉验证等方式来选择出一个最好的 d' 取值

上边是基于线性变换的降维方法，那么针对非线性情况时，下节我们将对非线性情况的降维进行介绍

4）一种常用的非线性降维方法：核化线性降维

在现实任务中，有时候直接使用线性降维会导致部分信息丢失的，本书举的例子是基于这样的一个场景，低维空间映射到高维空间后，再次降维到低维空间会导致原始的低维结构丢失。

核化线性降维的本质是基于核技巧对线性降维方法进行“核化”（kernelized），以前边的主成分分析法线性降维为例，核化主成分分析算法是在主成分分析的基础上将高维空间的样本投射 X 转换为被核化的 k(X) 来进行计算，并对核函数对应的核矩阵进行特征分解来求得投影的 d' 维特征向量

5）一种借鉴拓扑流形概念的降维方法：流形学习（manifold learning）

流行学习的核心概念是：样本虽然在高维空间上的分布看上去非常复杂，但是在局部上仍具有欧氏空间的性质，所以我们可以通过在局部建立降维映射关系，然后再将局部映射推广到全局去来简化降维开销。

个人想法：流行学习的本质是要使得降维前后的样本分布在欧氏空间上的性质保持不变。

根据选择的欧氏空间性质的不同可以有不同的流形学习方法，本章介绍了两种著名的流形学习方法。

［1］欧氏空间距离性质：等度量映射（Isometric Mapping，简称Isomap）

等度量映射试图让样本在“流形”上的距离在降维之后仍能保持

等度量映射的基本出发点，是认为低维流形嵌入到高维空间之后，直接在高维空间中计算直线距离具有误导性，因为高维空间中的直线距离在低维空间中是不可达的。

图10.7(a)所示，假设红色线段的两端分别是A点和B点，对于一个生活在二维平面上的生物来说，其从A点到B点的距离是红色线段的长度，而对于生活在三维平面上的生物来说，其从A点到B点的距离是黑色线段的长度。

显然在S型的流行上，红色线段的长度是更为恰当的距离表示，该路径也更贴合样本数据的分布情况。

面对这种情况，等度量映射算法被设计为：

＊ 通过设定最近邻 k 并计算出样本 xi 与近邻之间的距离，非近邻之间距离为无限大

＊ 通过Dijkstra算法计算任意两个样本 xi 与 xj 之间的距离

＊ 利用算好的距离使用多维缩放算法来对样本进行降维

［2］欧氏空间的向量表示性质：局部线性嵌入（Locally Linear Embedding，简称LLE）

与Isomap算法不同，LLE试图保持邻域内样本之间的线性关系，即一个样本可以由其邻域的样本通过线性组合来进行重构，而且这种重构关系在降维之后仍能保持。

值得注意的是，流形学习欲有效进行邻域保持则需样本密采样，而这恰是高维情形下的重大阻碍，因此流形学习方法在实践中的降维性能往往没有预期的好；但邻域保持的想法很有意义，它对其它机器学习的分支也产生了重要的影响，例如半监督学习中有著名的流行假设

6）降维的替代方案，直接学习距离度量：度量学习（metric learning）

在机器学习中，对高维数据进行降维的主要目的是希望找到一个合适的低维空间，在此空间进行学习能比原始空间要好。事实上，每个空间对应了在样本属性上定义的一个合适的距离度量。那么，何不直接尝试“学习”出一个合适的距离度量呢？这就是度量学习的基本动机

欲对距离度量进行学习，我们需要为样本之间的距离计算加上权重，并可以根据具体样本来对权重进行训练，这个权重构成的矩阵我们称为“度量矩阵”。

度量学习的目的就是计算出合适的“度量矩阵”，在实际计算时，我们可以将度量矩阵 M 直接嵌入到近邻分类器的评价体系中去，通过优化该性能指标相应的求得 M.

2. 基础知识

1）懒惰学习（lazy learning）

此类学习技术在训练阶段仅仅是把样本保存起来，训练时间开销为零，待收到测试样本后再进行处理

2）急切学习（eager learning）

与懒惰学习相反，此类学习技术在训练阶段就对样本进行学习处理

3）维度灾难（curse of dimensionality）

在高维情形下出现的样本稀疏、距离计算困难等问题，是所有机器学习方法共同面临的严重障碍，被称为“维度灾难”

4）矩阵的迹（trace）

在线性代数中，一个n×n矩阵A的主对角线（从左上方至右下方的对角线）上各个元素的总和被称为矩阵A的迹（或迹数），一般记作tr(A)。

5）矩阵特征分解（Eigenvalue decomposition）

将矩阵分解为由其特征值和特征向量表示的矩阵之积的方法。需要注意只有对可对角化矩阵才可以施以特征分解。简单理解就是将矩阵变换为几个相互垂直的向量的和，比如在二维空间中，任意一个向量可以被表示为x轴和y轴的组合。

3. 总结

1） k 近邻学习是简单常用的分类算法，在样本分布充足时，其最差误差不超过贝叶斯最优分类器的两倍

2）实际情况下由于属性维度过大，会导致“维数灾难”，这是所有机器学习中的共同障碍

3）缓解维数灾难的有效途径是降维，即将高维样本映射到低维空间中，这样不仅属性维度降低减少了计算开销，还增大了样本密度

4）降维过程中必定会对原始数据的信息有所丢失，所以根据不同的降维目标我们可以得到不同的降维方法

5）多维缩放的目标是要保证降维后样本之间的距离不变

6）线性降维方法目标是要保证降维到的超平面能更好的表示原始数据

7）核线性降维方法目标是通过核函数和核方法来避免采样空间投影到高维空间再降维之后的低维结构丢失

8）等度量映射的目标是让样本在“流形”上的距离在降维之后仍能保持

9）局部线性嵌入的目标是让样本由其邻域向量重构关系在降维后仍能保持

10）度量学习绕过降维的过程，将学习目标转化为对距离度量计算的权重矩阵的学习

有趣的小数据：宇宙间基本粒子的总数约为10的80次方，而一粒灰尘中含有几十亿基本粒子，而要满足k近邻算法假设的属性数量为20的样本数量为10的60次方。