《62 机器学习机器学习中的维度灾难.docx》由会员分享，可在线阅读，更多相关《62 机器学习机器学习中的维度灾难.docx（11页珍藏版）》请在金锄头文库上搜索。
1、【机器学习】机器学习中的维度灾难深度学习专栏2020-06-23 原文1引见本篇文章，我们将争辩所谓的维度灾难”,并解释在设计一个分类器时它为何 如此重要。在下面几节中我将对这个概念进行直观的解释，并通过一个由于维 度灾难导致的过拟合的例子来讲解。考虑这样一个例子，我们有一些图片，每张图片描绘的是小猫或者小狗。我们 试图构建一个分类器来自动识别图片中是猫还是狗。要做到这一点，我们首先 需要考虑猫、狗的量化特征，这样分类器算法才能利用这些特征对图片进行分 类。例如我们可以通过毛皮颜色特征对猫狗进行识别，即通过图片的红色程 度、绿色程度、蓝色程度不同，设计一个简约的线性分类器：If 0.5*red
2、+0.3*green+0.2*blue0.6:return cat;else :return dog;红、绿、蓝三种颜色我们称之为特征Features，但仅仅利用这三个特征，还 不能得到一个完善的分类器。因此，我们可以添加更多的特征来描述图片。例 如计算图片X和Y方向的平均边缘或者梯度密度。现在总共有5个特征来构 建我们的分类器了。为了得到更好的分类效果，我们可以添加更多特征，例如颜色、纹理分布和统 计信息等。或许我们能得到上百个特征，但是分类器的效果会变得更好吗？答 案有些令人懊丧：并不能！现实上，特征数量超过肯定值的时候，分类器的效 果反而下降。图1显示了这种变化趋势，这就是维度灾难”。维
3、度，对N个原始特征进行线性组合。PCA算法试着找到低维的线性子空 间，保持原始数据的最大方差。然而，数据方差最大不肯定代表数据最显著的 分类信息。最终，一项格外有用的被用来测试和避开过拟合的技术是交叉验证。交叉验证 将原始训练数据分成多个训练样本子集。在分类器进行训练过程中，一个样本 子集被用来测试分类器的精确性，其他样本用来进行参数估量。假如交叉验证的结果与训练样本子集得到的结果不全都，那么就表示发生了过拟合。 假如训练样本无限，那么可以使用k折法或者留一发进行交叉验证。4结论这篇文章我们争辩了特征选择、特征提取、交叉验证的重要性，以及避开由维 度灾难导致的过拟合。通过一个过拟合的简约例子，
4、我们复习了维度灾难的重 要影响。先进制造业+工业互联网0-f0oourolu。七a)d Eusse-。Feature 1Dimensionality (number of features)图1.随着维度添加，分类器功能提升；维度添加到某值后，分类器功能下降下一节我们将解释为什么产生这条曲线并争辩如何避开这种情况发生。2维度灾难与过拟合在之前引入的猫和狗的例子中，我们假设有无穷多的猫和狗的图片，然而，由 于时间和处理力量限制，我们只得到10张图片（猫的图片或者狗的图片）。 我们的最终目标是基于这10张图片构建一个分类器，能够正确对10个样本 之外的无限多的图片进行正确分类。现在，让我们使用一个
5、简约的线性分类器来尝试得到一个好的分类器。假如只 使用一个特征，例如使用图片的平均红色程度redo图2.单个特征对训练样本分类效果不佳图2呈现了只使用一个特征并不能得到一个最佳的分类结果。因此，我们觉得 添加其次个特征：图片的平均绿色程度greenoPpaturp 1FAAturp 1图4.添加第三个特征实现了线性可分，即存在一个平面完全将猫和狗分开来。在三维特征空间，我们可以找到一个平面将猫和狗完全分开。这意味着三个特图3.添加其次个特征仍旧不能线性分割，即不存在一条直线能够将猫和狗完全分开。最终，我们打算再添加第三个特征：图片的平均蓝色程度，得到了三维特征空征的线性组合可以对10个训练样本
6、进行最佳的分类。Fftaturp 1图5.特征越多，越有可能实现正确分类以上的例子好像证明白不断添加特征数量，直到获得最佳分类效果，是构建一 个分类器的最好方法。但是，之前图1中，我们认为情况并非如此。我们需要 留意一个问题：随着特征维度的添加，训练样本的在特征空间的密度是如何呈 指数型下降的？在1D空间中（图2所示），10个训练样本完全掩盖了 1D特征空间，特征 空间宽度为50因此，1D下的样本密度是10/2 = 5。而在2D空间中（图3 所示），同样是10个训练样本，它构成的2D特征空间面积为5x5 = 25.因 此，2D下的样本密度是10/25 = 0.4。最终在3D空间中，10个训练样
7、本构成 的特征空间大小为5x5x5 = 125 ,因此，3D下的样本密度为10/125 = 0.08。假如我们连续添加特征，整个特征空间维度添加，并变得越来越稀疏。由于稀 疏性，我们愈加简约找到一个超平面来实现分类。这是由于随着特征数量变得 无限大,训练样本在最佳超平面的错误侧的可能性将会变得无限小。然而，假 如我们将高维的分类结果投影到低维空间中，将会消灭一个严峻的问题：Fpnturp 1图6.使用太多特征导致过拟合。分类器学习了过多样本数据的特别特征（噪声），而对新数据的泛化力量不好。图6呈现了 3D的分类结果投影到2D特征空间的样子。样本数据在3D是线 性可分的，但是在2D却并非如此。现
8、实上，添加第三个维度来获得最佳的线 性分类效果，等同于在低维特征空间中使用非线性分类器。其结果是，分类器 学习了训练数据的噪声和特别，而对样本外的数据拟合效果并不抱负，甚至很 差。这个概念称为过拟合，是维度灾难的一个直接后果。图7呈现了一个只用2个 特征进行分类的线性分类器的二维平面图。图7.虽然训练样本不能全都分类正确，但这个分类器的泛化力量比图5要好。虽然图7中的简约的线性分类器比图5中的非线性分类器的效果差，但是图7 的分类器的泛化力量强。这是由于分类器没有把样本数据的噪声和特别也进行 学习。另一方面说，使用更少的特征，维度灾难就能避开，就不会消灭对训练 样本过拟合的现象。图8用不同的方
9、式解释上面的内容。假设我们只使用一个特征来训练分类器， 1D特征值的范围限定在0到1之间，且每只猫和狗对应的特征值是独一的。 假如我们期望训练样本的特征值占特征值范围的20%,那么训练样本的数量 就要达到总体样本数的20%。现在，假如添加其次个特征，也就是从直线变 为平面2D特征空间，这种情况下，假如要掩盖特征值范围的20%，那么训练 样本数量就要达到总体样本数的45% ( 0.45*0.45 = 0.2 ) o而在3D空间中， 假如要掩盖特征值范围的20% ,就需要训练样本数量达到总体样本数的58%( 0.58*0.58*0.58=0.2 )。图8.掩盖特征值范围20%所需的训练样本数量随着
10、维度添加呈指数型增长换句话说，假如可用的训练样本数量是固定的，那么假如添加特征维度的话， 过拟合就会发生。另一方面，假如添加特征维度，为了掩盖同样的特征值范 围、防止过拟合，那么所需的训练样本数量就会成指数型增长。在上面的例子中，我们呈现了维度灾难会惹起训练数据的稀疏化。使用的特征 越多，数据就会变得越稀疏，从而导致分类器的分类效果就会越差。维度灾难 还会形成搜索空间的数据稀疏程度分布不均。现实上，围绕原点的数据(在超 立方体的中心)比在搜索空间的角落处的数据要稀疏得多。这可以用下面这个 例子来解释：想象一个单位正方形代表了 2D的特征空间，特征空间的平均值位于这个单位 正方形的中心处，距中心
11、处单位距离的全部点构成了正方形的内接圆。没有落 在单位圆的训练样本距离搜索空间的角落处更距离中心处更近，而这些样本由 于特征值差异很大(样本分布在正方形角落处)，全部难以分类。因此，假如 大部分样本落在单位内接圆里，就会更简约分类。如图9所示：图9.落在单位圆之外的训练样本位于特征空间角落处，比位于特征空间中心处的样本更难进行分类。一个好玩的问题是当我们添加特征空间的维度时，随着正方形（超立方体）的 体积变化，圆形（超球体）的体积是如何变化的？无论维度如何变化，超立方 体的体积都是1 ,而半径为0.5的超球体的体积随着维度d的变化为：V(d)=；山2 府堕+ 1)图10呈现了随着维度d的添加，
12、超球面的体积是如何变化的:aloqdwQdAq(DSJOa)lunoaloqdwQdAq(DSJOa)luno图10.维度d很大时，超球面的体积趋于零这表明白随着维度变得越来越大，超球体的体积趋于零，而超立方体的体积是 不变的。这种令人惊异的反直觉发觉部分解释了在分类中维度灾难的问题：在 高维空间中，大部分的训练数据分布在定义为特征空间的超立方体的角落处。就像之前提到的，特征空间角落处的样本比超球体内的样本愈加难以进行正确 分类。图11分别从2D、3D和可视化的8D超立方体（28 = 256个角落） 的例子论证了这个结论。图11.随着维度添加，大部分数量数据分布在角落处对于8维的超球体，大约9
13、8%的数据集中在它256个角落处。其结果是，当 特征空间的维度变得无限大时，从样本点到质心的最大、最小欧氏距离的差值 与其最小欧式距离的比值趋于零：limdoodistmaxdistmindistTOmin因此，距离测量在高维空间中渐渐变得无效。由于分类器是基于这些距离测量 的（例如 Euclidean 距离、Mahalanobis 距离、Manhattan 距离）,所以 低维空间特征更少，分类愈加简约。同样地，在高维空间的高斯分布会变平坦 且尾巴更长。3如何避开维度灾难定的规章来指定定的规章来指定图1呈现了随着维度变得很大，分类器的功能是下降的。那么问题是很大意 味着什么？过拟合如何避开？很
14、圆满，在分类问题中，没有 该当使用多少特征。现实上，这依靠于训练样本的数量、决策边界的简单性和 使用的是哪个分类器。假如理论上训练样本时无限多的，那么维度灾难不会发生，我们可以使用无限 多的特征来获得一个完善的分类器。训练数据越少，使用的特征就要越少。假 如N个训练样本掩盖了1D特征空间的范围，那么在2D中，掩盖同样密度就 需要N*N个数据，同样在3D中，就需要N*N*N个数据。也就是说，随着 维度添加，训练样本的数量要求随指数添加。此外，那些非线性决策边界的分类器（例如神经网络、KNN分类器、决策树 等）分类效果好但是泛化力量差且简约发生过拟合。因此，当使用这些分类器 的时候，维度不能太高。
15、假如使用泛化力量好的分类器（例如贝叶斯分类器、 线性分类器），可以使用更多的特征，由于分类器模型并不简单。图6呈现了 高维中的简约分类器对应于地位空间的简单分类器。因此，过拟合只在高维空间中猜测相对少的参数和低维空间中猜测多参数这两 种情况下发生。举个例子，高斯密度函数有两类参数：均值和协方差矩阵。在 3D空间中，协方差矩阵是3x3的对称阵，总共有6个值（3个主对角线值和 3个非对角线值），还有3个均值，加在一起，一共要求9个参数；而在 1D ,高斯密度函数只需求2个参数（1个均值，1个方差）；在2D中，高斯 密度函数要求5个参数（2个均值，3个协方差参数）。我们可以发觉，随着 维度添加，参数数量呈平方式增长。在之前的文章里我们发觉，假如参数数量添加，那么参数的方差就会增大（前 提是估量偏差和训练样本数量保持不变）。这就意味着，假如围度添加，估量 的参数方差增大，导致参数估量的质量下降。分类器的方差增大意味着消灭过 拟合。另一个好玩的问题是：该当选择哪些特征。假如有N个特征，我们该当如何 选取M个特征？一种方法是在图1曲线中找到功能最佳的位置。但是，由于 很难对全部的特征组合进行训练和测试，所以有一些其他方法来找到最佳选 择。这些方法称之为特征选择算法，经常用启发式方法（例如贪婪算法
