PRML系列:1.4 The Curse of Dimensionality

随便扯扯

PRML例举了一个人工合成的数据集,这个数据集中表示一个管道中石油,水,天然气各自所占的比例。这三种物质在管道中的几何形状有三种不同的配饰,被称为“同质状”、“环状”和“薄片状”。

输入有12个维度,是用伽马射线密度计采集的数据,输出对应的是三个类别:同质状,环状和薄片状。为了能够直观的呈现数据在二维空间中的分布,PRML可视化了x6x_6和x7x_7维度,对应100条数据。如下图:

图中标注了一个”x”点,可以发现在”x”点附近大量聚集了红色类别的点,而蓝色的点和绿色点离”x”点较远,或者说蓝色呈现的空间并不在”x”点附近。于是PRML得出了一个直观的结论:”x”点的性质能够由它附近点所决定(有点像KNN),但随着空间距离的增加,越远的点对它的影响则越小。

所以,直观的做法,对图中100个数据点进行空间划分,分成如上16个单元格,统计每个单元格出现类别最多的,作为预测标签。

但上述做法有两种致命的缺陷:

  • 随着维度的增加,单元格的数目呈指数级增长,比如D = 2,对应的是4^2 = 16个单元格,而当D = 3时,为4^3 = 64个单元格。
  • 这种简单粗暴的方法没法适应数据稀疏的问题,这要求每个单元格内至少有一堆数据存在,所以随着维度的增加,对数据大小的要求也是指数上升的。(非常感性的认识)

这里给出理性的解释,比如假设对应一维特征的取值范围为[0, 4],那么固定样本大小100,在一维线密度如下: 100 / 5 = 20,表示平均每个坐标点周围能够得到20个样本。考虑二维,两特征依旧在范围[0, 4],平面面积为 5 x 5 = 25, 面密度如下:100 / 25 = 4, 同理D= 3时,则体密度为0.8。单位区域内的样本数量急剧下降,自然地超平面的划分在高维空间越容易,不过所带来的就是过拟合问题(高维空间的描述能力大大超越了低维,而实际上数据集是由低维空间产生的,因此高维过剩的力量只能用来描述噪声了,自然就过拟合)。

维度灾难有一篇很好的中文参考博文【机器学习中的维度灾难】,其中有一段解释如下:

图8用不同的方式解释上面的内容。假设我们只使用一个特征来训练分类器,1D特征值的范围限定在0到1之间,且每只猫和狗对应的特征值是唯一的。如果我们希望训练样本的特征值占特征值范围的20%,那么训练样本的数量就要达到总体样本数的20%。现在,如果增加第二个特征,也就是从直线变为平面2D特征空间,这种情况下,如果要覆盖特征值范围的20%,那么训练样本数量就要达到总体样本数的45%(0.45*0.45=0.2)。而在3D空间中,如果要覆盖特征值范围的20%,就需要训练样本数量达到总体样本数的58%(0.58*0.58*0.58=0.2)。

如果增加特征维度,为了覆盖同样的特征值范围、防止过拟合,那么所需的训练样本数量就会成指数型增长。

实际上我并没有理解为什么所占数据集在二维情况下就从20%上升到了45%(该解释可能是错的)。这里给一波我对此处产生维度灾难的解释:

在石油例子中PRML中提到了一个结论:”x”附近的点对”x”的预测有着至关重要的影响,所以我们考虑”x”的邻近区域,并以投票的形式来决定”x”的类别,不过为了防止过拟合,我们希望这个邻近区域在一定范围内能够覆盖尽可能多样本,比如每个邻近区域占样本的20%,这样以这20%的样本进行投票还是比较可靠的,为了让模型变现的更优,显然邻域也是越小越好。综上:邻域越小且占领样本数越多,模型则越优。

接着看上图,在一维情况下,假设以样本20%来进行投票,那么我们只需要让特征覆盖20%的范围即可。到了二维情况,为了还是拿20%的样本去决策该区域的类别,经过计算发现特征值增长到了0.45(0.45 * 0.45 = 0.2),同理到了三维,则需要覆盖0.58的特征范围。我去,取20%样本去决策是为了防止过拟合,结果随着维数的上升,特征范围几乎要覆盖整个区域,考虑r=10%r = 10\%的样本,在10个维度下,需要覆盖特征r1/D=80%r^{1/D} = 80\%的范围,正如图上3维空间所展示的那样,该邻域还是个局部邻域么?显然已经覆盖了大部分地方,并且会造成大量的区域重叠。并不符合如前假设:邻域越小且占领样本数越多,模型则越优。

为了区域不重叠才有了PRML中的单元格划分,但是同样的划分,在高维为了弥补过拟合,则需要在该区域填充更多的数据才行。

PRML举了个3单元格,D = 1, 2, 3的情形,如下:

再来谈谈1.1中提到的多项式拟合问题,在D个维度下,对应多项式阶数M = 3的式子如下:

y(x,w)=w0+∑i=1Dwixi+∑i=1D∑j=1Dwijxixj+∑i=1D∑j=1D∑k=1Dwijkxixjxk

y(x, w) = w_0 + \sum_{i = 1}^D w_i x_i + \sum_{i = 1}^D\sum_{j = 1}^D w_{ij} x_i x_j + \sum_{i = 1}^D \sum_{j = 1}^D \sum_{k = 1}^D w_{ijk} x_i x_j x_k

可以得出,当M = 3固定不变时,能够得到系数的个数为: 1+D+D2+D31 + D + D^2 + D^3, 所以随着D的增长,增长速度正比于D3D^3,那么对于特别的M,速度正比于DMD^M。虽然不是幂函数,但是显然用这种函数拟合高维数据集,显得非常笨重,在实际应用中很受限。

很奇怪,PRML突然举了一个在高维空间球体比的例子,只是为了说明我们在低维空间的直觉在高维空间时不一定起作用。比如在D维下,关于一个半径为r的球体”体积”如下:

VD(r)=KDrD

V_D(r) = K_D r^D

因为二维球面积为:V2=2πrV_2 = 2 \pi r, 三维体积为:V3=43πr3V_3 = \frac{4}{3} \pi r^3,所以才有了上式的推广?

假设在高维情况下,VD(r)=KDrDV_D(r) = K_D r^D成立,那么再考虑一个半径r=1−ϵr = 1 - \epsilon的球体,和半径为r的球体之间的部分占总体积的百分比是多少?我们有:

VD(1)−VD(1−ϵ)VD(1)=1−(1−ϵ)D

\frac{V_D(1) - V_D(1 - \epsilon)}{V_D(1)} = 1 - (1- \epsilon)^D

神奇的事情发生了,即时ϵ\epsilon很小,比如去0.01在低维情况下,这个比值肯定很小,但当D增大到1000时,(1−ϵ)D(1 - \epsilon)^D接近0,所以比值居然是1,这就说明,球体的体积在高维情况下,是聚集在表面附近的薄球壳上!

这的确和我们的直觉有所出入,不过为何高维就一定满足这式子呢?

VD(r)=KDrD

V_D(r) = K_D r^D 求解释。

实际上关于超球体在球面的体积有着很重要的意义,常见的分类器如KNN,SVM都是基于距离度量来实现的。但在高维,我们发现超球的体积大部分分布在薄球面上,(体积可以理解为数据可以分布到的地方),那么显然由于数据聚集在一块,距离度量将接近于0,这就意味着基于距离度量的分类器在高维不再起作用。

PRML还列举了一个高斯分布在各种维度下的密度质量分布。基本思路如下:首先根据高斯分布能够得到各种维度下,在空间中的数据分布情况,比如一维是这样的:

二维是这样的:

接着考虑从原点出发,半径为r,邻域为ϵ\epsilon的薄球壳上积分,发现随着维度的上升,分布最密集的地方离原点的距离也越远。上图:

具体的求解过程如下:

最后PRML总结说:虽然维度灾难在模式识别应用中是一个重要的问题,但它并不能阻止我们寻找应用于高维空间的有效技术。原因如下:

  • 真实的数据经常被限制在有着较低的有效维度的空间区域中,特别地,在⽬标值会发⽣重要变化的⽅向上也会有这种限制。(所以高维数据存在维度冗余,才有了降维技术的发展?)
  • 真实数据通常⽐较光滑(⾄少局部上⽐较光滑),因此⼤多数情况下,对于输⼊变量的微⼩改变,⽬标值的改变也很⼩,因此对于新的输⼊变量,我们可以通过局部的类似于插值的技术来进⾏预测。(可这为什么就能够避免维度灾难问题呢?)

考虑制造业中的一个应用,照相机拍摄了传送带上的相同的平面物体,目标是判断它们的方向,但是采集过程中实际能够得到物体所有的行为信息,如位置,方向,像素灰度值,所以实际上,这些数据呈现在空间内是一种三维流形(什么玩意)。。。或者这么考虑,在一维上,我们行走只有一个方向前或者后,而在二维空间内,我们可以上下左右,移动的方向变多。在三维空间,我们还可以上天,所以自由度越多,我们越自由,选择越多样化。但问题输出可能只需要判断方向,与位置无关,这就很有意义了。(意义在哪呢!)大胆猜测一波,或许可以借用其他信息如物体占空间大小的比例来推断方向。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏腾讯移动品质中心TMQ的专栏

米少熬好粥:数据有限时怎样调优深度学习模型

所谓迁移学习,就是将一个问题上训练好的模型通过简单的调整,使其适用一个新的问题,可以认为是一种模型调优的“取巧”方法。可以类比人的举一反三能力。

3733
来自专栏瓜大三哥

图像配准

图像配准(Image registration)是将同一场景拍摄的不同图像进行对齐的技术,即找到图像之间的点对点映射关系,或者对某种感兴趣的特征建立关联。以同...

1729
来自专栏计算机视觉life

SLIC 超像素分割详解(三):应用

看过上面的介绍后,我们应该思考一下:分割好的超像素有什么用?怎么用?用到哪里? 首先,超像素可以用来做跟踪,可以参考卢湖川课题组发表在IEEE TIP上的《Ro...

30110
来自专栏新智元

【Github 6481 颗星】牛津大学 & DeepMind 2017 深度 NLP 课程

【新智元导读】牛津大学和 DeepMind 联合推出了《NLP深度学习课程》,专攻基于深度学习的自然语言处理,涉及递归神经网络、B-P、LSTM、注意力网络、记...

2747
来自专栏机器之心

业界 | 苹果发文:全局语义信息能否改进神经语言模型?

在 iPhone 上输入文本、发掘用户可能感兴趣的新闻、查明用户遇到问题的答案,以及其他语言相关的任务都取决于稳健的自然语言处理(NLP)模型。词嵌入是一类 N...

842
来自专栏AI研习社

一文读懂 CNN、DNN、RNN 内部网络结构区别

【AI研习社】关注AI前沿、开发技巧及技术教程等方面的内容。欢迎技术开发类文章、视频教程等内容投稿,邮件发送至:zhangxian@leiphone.com 从...

3486
来自专栏智能算法

一文读懂 CNN、DNN、RNN 内部网络结构区别

从广义上来说,NN(或是更美的DNN)确实可以认为包含了CNN、RNN这些具体的变种形式。在实际应用中,所谓的深度神经网络DNN,往往融合了多种已知的结构,包括...

3635
来自专栏量化投资与机器学习

基于 RNN、LSTM 的股票多因子预测模型

前言 在机器学习如何应用到量化投资的系列文章中,今天我们专门来介绍一篇来自国信证券的研究报告,来从券商角度分析这个问题。 对于最直接的问题:能否利用神经网络,要...

9867
来自专栏数据派THU

一文概览图卷积网络基本结构和最新进展(附视频、代码)

来源:机器之心 本文长度为3476字,建议阅读7分钟 本文为你介绍图卷积网络的基本结构和最新的研究进展,并用一个简单的一阶 GCN 模型进行图嵌入。 本文介绍了...

3787
来自专栏社区的朋友们

短视频分类进化:从 LR 到 LSTM

为了跟上这波趋势,我使用深度学习中的 LSTM 网络对短视频分类进行了尝试,并与目前使用的传统分类方法(LR)进行对比,的确取得了更好的效果。

2.6K1

扫码关注云+社区