降维与度量学习

原理

《机器学习》周志华

10.1 k近邻学习

• k近邻(k-Nearest Neighbor, kNN)学习是一种常用的监督学习方法，其工作机制非常简单：给定测试样本，基于某种距离度量找出训练集中与其最靠近的k个训练样本，然后基于这k个“邻居”的信息来进行预测。通常，在分类任务中可使用“投票法”，即选择这k个样本中出现最多的类别标记作为预测结果；在回归任务中可使用“平均法”，即将这 k 个样本的实值输出标记的平均值作为预测结果；还可基于距离远近进行加权平均或加权投票，距离越近的样本权重越大。
• 与前面介绍的学习方法相比，k近邻学习有一个明显的不同之处：它似乎没有显式的训练过程！事实上，它是“懒惰学习”(lazy learning) 的著名代表，此类学习技术在训练阶段仅仅是把样本保存起来，训练时间开销为零，待收到测试样本后再进行处理；相应的，那些在训练阶段就对样本进行学习处理的方法，称为“急切学习”(eager learning)。
• 最近邻分类器虽简单，但它的泛化错误率不超过贝叶斯最优分类器的错误率的两倍

10.2 低维嵌入

• 上一节的讨论是基于一个重要假设：任意测试样本x附近任意小的 θ距离范围内总能找到一个训练样本，即训练样本的采样密度足够大，或称为“密采样”(dense sample)。然而，这个假设在现实任务中通常很难满足，例如若 θ = 0.001，仅考虑单个属性，则仅需1000个样本点平均分布在归一化后的属性取值范围内，即可使得任意测试样本在其附近 0.001距离范围内总能找到一个训练样本，此时最近邻分类器的错误率不超过贝叶斯最优分类器的错误率的两倍。
• 然而，这仅是属性维数为1的情形，若有更多的属性，则情况会发生显著变化。例如假定属性维数为20，若要求样本满足密采样条件，则至少需要(1000)²⁰⁼¹⁰60个样本。现实应用中属性维数经常成千上万，要满足密采样条件所需的样本数目是无法达到的天文数字。此外，许多学习方法都涉及距离计算，而高维空间会给距离计算带来很大的麻烦，例如当维数很高时甚至连计算內积都不再容易。
• 事实上，在高维情形下出现的数据样本稀疏、距离计算困难等问题，是所有机器学习方法共同面临的严重障碍，被称为“维数灾难”(curse of dimensionality)。
• 缓解维数灾难的一个重要途径是降维(dimension reduction)，亦称“维数约简”，即通过某种数字变换将原始高维属性空间转变为一个低维“子空间”(subspace)，在这个子空间中样本密度大幅提高，距离计算也变得更为容易，为什么能进行降维？这是因为在很多时候，人们观测或收集到的数据样本虽是高维的，但与学习任务密切相关的也许仅是某个低维分布，即高维空间中的一个低维“嵌入”(embedding)。
• 若要求原始空间中样本之间的距离在低维空间中得以保持，即得到“多维缩放”(Multiple Dimensional Scaling, MDS)这样一种经典的降维方法。
• 基于线性变换来进行降维的方法称为线性降维方法，不同之处是对低维子空间的性质有不同的要求，相当于对W施加了不同的约束。在下一节我们将会看到，若要求低维子空间对样本具有最大可分性，则将得到一种极为常用的线性降维方法。
• 对降维效果的评估，通常是比较降维前后学习器的性能，若性能有所提高则认为降维起到了作用。若将维数降至二维或三维，则可通过可视化技术来直观地判断降维效果。

10.3 主成分分析

• 主成分分析(Principal Component Analysis, PCA)是最常用的一种降维方法。在介绍PCA之前，不妨先考虑这样一个问题：对于正交属性空间中的样本点，如何用一个超平面(直线的高维推广)对所有样本进行恰当的表达？容易想到，若存在这样的超平面，那么它大概应具有这样的性质：
  • 最近重构性：样本点到这个超平面的距离都足够近；
  • 最大可分性：样本点在这个超平面上的投影能尽可能分开。
• 有趣的是，基于最近重构性和最大可分性，能分别得到主成分分析的两种等价推导。
• PCA仅需保留W 与样本的均值向量即可通过简单的向量减法和矩阵-向量乘法将新样本投影至低维空间中。显然，低维空间与原始高维空间必有不同，因为对应于最小的 d - d' 个特征值的特征向量被舍弃了，这是降维导致的结果。但舍弃这部分信息往往是必要的：一方面，舍弃这部分信息之后能使样本的采样密度增大，这正是降维的重要动机；另一方面，当数据受到噪声影响时，最小的特征值所对应的特征向量往往与噪声有关，将它们舍弃能在一定程度上起到去噪的效果。

10.4 核化线性降维

• 线性降维方法假设从高维空间到低维空间的函数映射是线性的，然而，在不少现实任务中，可能需要非线性映射才能找到恰当的低维嵌入。为了对“原本采样的”低维空间与降维后的低维空间加以区别，我们称前者为“本真”(intrinsic)低维空间。
• 非线性降维的一种常用方法，是基于核技巧对线性降维方法进行“核化”(kernelized)。核主成分分析(Kernelized PCA, KPCA)

10.5 流形学习

• 流形学习(manifold learning)是一类借鉴了拓扑形概念的降维方法。“流形”是在局部与欧式空间同胚的空间。换言之，它在局部具有欧氏空间的性质，能用欧氏距离来进行距离计算。这给降维方法带来了很大的启发：若低维流形嵌入到高维空间中，则数据样本在高维空间的分布虽然看上去非常复杂，但在局部上仍具有欧氏空间的性质，因此，可以容易地在局部建立降维映射关系，然后在设法将局部映射关系推广到全局。

10.5.1 等度量映射

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

10.5.2 局部线性嵌入

• 与Isomap试图保持近邻样本之间的距离不同，局部线性嵌入试图保持领域内样本之间的线性关系。

10.6 度量学习

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

Hello World

学术

工程