维数灾难

维度灾难用来描述当（数学）空间维度增加时，分析和组织高维空间（通常有成百上千维），因体积指数增加而遇到各种问题场景。这样的难题在低维空间中不会遇到，如物理空间通常只用三维来建模。

[描述来源：维基百科URL：https://en.wikipedia.org/wiki/Curse_of_dimensionality]

举例来说，如果我们有D个输入变量，那么3阶的一般多项式将采用这种形式：

随着D增加，所以独立系数的数量（由于x个变量之间的互换对称性不是所有系数都是独立的）与D^3以成比例地速度增长。在实践中，为了捕捉数据中的复杂依赖关系，我们可能需要使用更高阶的多项式。对于阶数为M的多项式，系数的数量在D^M。虽然这是一个幂律增长，而不是指数级的增长，但它仍然使得该方法迅速变得笨重，实用性有限。

此外，当我们考虑维度更高的空间时，我们的几何直觉可能会严重失败。举一个简单的例子，在D维的空间中考虑一个半径为r = 1的球体，要计算球体的体积在半径r = 1-\epsilon和r = 1之间的比例是多少。由于在D维中半径为r的球体的体积必须按比例r^D缩放，我们可以借此估计这个分数，所以我们写出：

常数K_D仅依赖于D。因此，分数可以通过下式计算得出：

下图显示了不同\epsilon和不同D值求得的分数，我们看到，对于大D，即使对于很小的\epsilon，这个分数也趋于1。因此，在高维空间中，球体的大部分体积实际上集中在表面附近的薄壳中，而这与我们的直觉是相悖的。

[描述来源：Bishop C. M. (2006). Pattern Recognition and Machine Learning. Springer.]

发展历史

描述

维数灾难是一个最早由Richard E. Bellman在考虑优化问题时首次提出来的术语。1968年Hughes发现要在高维特征空间（每个特征都能够取一系列可能值）的有限数据样本中学习一种“自然状态”（可能是无穷分布），要求有相当数量的训练数据含有一些样本组合。而给定固定数量的训练样本，其预测能力随着维度的增加而减小，这一现象被命名为Hughes影响或Hughes现象。

2000年David Donoho分享了他的个人经验：（1）通过解释高维数据分析中正在进行的发展，数学家可以意识到谐波分析中的新问题;（2）很多数据分析问题即使在相当低的维度上也没有解决，就像刚刚才被注意到的许多数学问题一样，在这些问题上的研究实际上才刚刚起步

维度灾难的存在一方面促使研究者们转向不受维度限制的模型——如支持向量机，如1998年Piotr Indyk和Rajeev Motwani提出对k-means算法进行修改使其不受维度影响；另一方面也诱发了不少学者研究通过特征抽取（feature extraction）来降维（dimensionality reduction）的方法，如主成分分析（PCA），线性判别分析（LDA），自动编码机（autoencoder）等。

主要事件

发展分析

瓶颈

维度灾难的存在使得很多传统统计模型在数据高维的情况下都无法使用，如回归模型，从而限制了这些模型的表现。

未来发展方向

如上文所述，一方面维度灾难推动关于模型在高维空间表现的研究；另一方面，高维空间对于聚类等方法实际上是有利的，这也是SVM所基于的逻辑之一。

Contributor: Yuanyuan Li