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 条评论
登录 后参与评论

相关文章

来自专栏专知

基于信息理论的机器学习-中科院自动化所胡包钢研究员教程分享03(附pdf下载)

【导读】专知于11月24日推出胡老师的基于信息理论的机器学习报告系列教程,大家反响热烈,胡老师PPT内容非常翔实精彩,是学习机器学习信息理论不可多得的好教程,今...

3127
来自专栏人工智能头条

随机森林不可思议的有效性

1475
来自专栏一棹烟波

利用光场进行深度图估计(Depth Estimation)算法之二——匹配算法

光场相机由于能够捕获相机内部光线的强度和方向而得到整个光场,可以实现重聚焦(refocus)和视角变换等功能。进而可以进行深度估计获取深度图,前面说过利用重聚焦...

2776
来自专栏CSDN技术头条

随机森林不可思议的有效性

对于机器学习从业者而言,有自己最喜欢的算法是很常见的。可能这有点不太合乎常理,因为没有一个算法能够完全地主导所有的应用,而且机器学习算法的性能很大程度上依赖于应...

1976
来自专栏大数据挖掘DT机器学习

一元线性回归的细节

文/程sir(简书作者) 原文:http://www.jianshu.com/p/fcd220697182 一元线性回归可以说是数据分析中非常简单的一个知识点,...

2814
来自专栏PPV课数据科学社区

数据咖课堂:R语言十八讲(十八)—R实现主成分分析

? 之前我们在十七讲,将主成分分析的原理和计算过程了解了一遍,今天我们用工具R来实现这一模型.由于R软件中有多个函数可以处理这件事情,所以我们选用两个主要的来...

3868
来自专栏人工智能头条

机器学习的“小无相功”:高斯过程回归的深度科普

1273
来自专栏机器学习算法与Python学习

基于稀疏化鲁棒LS-SVR与多目标优化的铁水硅含量软测量建模

今天跟大家分享一篇之前发表的文章,《基于稀疏化鲁棒LS-SVR与多目标优化的铁水硅含量软测量建模 》。 摘要: 针对高炉炼铁过程的关键工艺指标——铁水硅含量[...

3558
来自专栏机器学习、深度学习

人群计数--Single-Image Crowd Counting via Multi-Column Convolutional Neural Network

Single-Image Crowd Counting via Multi-Column Convolutional Neural Network CVPR...

25110
来自专栏量子位

刘铁岩的对偶监督学习新论文亮相:入选ICML2017

李林 编译整理 量子位 报道 | 公众号 QbitAI 继NIPS2016上提出对偶学习,微软亚洲研究院副院长刘铁岩等又在Arxiv上发布了一篇相关论文:对偶监...

2426

扫码关注云+社区