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总结说：虽然维度灾难在模式识别应用中是一个重要的问题，但它并不能阻止我们寻找应用于高维空间的有效技术。原因如下：

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

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