维数灾难

维数灾难（英语：Curse of dimensionality，又名维度的诅咒）是一个最早由美国应用数学家理查德·贝尔曼在考虑优化问题时首次提出来的术语^[1]^[2]，用来描述当（数学）空间维度增加时，分析和组织高维空间（通常有成百上千维），因体积指数增加而遇到各种问题场景。这样的难题在低维空间中不会遇到，如物理空间通常只用三维来建模。

举例来说，100个平均分布的点能把一个单位区间以每个点距离不超过0.01采样；而当维度增加到10后，如果以相邻点距离不超过0.01小方格采样一单位超正方体，则需要10²⁰ 个采样点：所以，这个10维的超正方体也可以说是比单位区间大10¹⁸倍。（这个是理查德·贝尔曼所举的例子）

在很多领域中，如采样、组合数学、机器学习和数据挖掘都有提及到这个名字的现象。这些问题的共同特色是当维数提高时，空间的体积提高太快，因而可用数据变得很稀疏。稀疏性对于任何要求有统计学意义的方法而言都是一个问题，为了获得在统计学上正确并且有可靠的结果，用来支撑这一结果所需要的数据量通常随着维数的提高而呈指数级增长。而且，在组织和搜索数据时也有赖于检测对象区域，这些区域中的对象通过相似度属性而形成分组。然而在高维空间中，所有的数据都很稀疏，从很多角度看都不相似，因而平常使用的数据组织策略变得极其低效。

“维数灾难”通常是用来作为不要处理高维数据的无力借口。然而，学术界一直都对其有兴趣，而且在继续研究。另一方面，也由于本征维度（英语：intrinsic dimension）的存在，其概念是指任意低维数据空间可简单地通过增加空余（如复制）或随机维将其转换至更高维空间中，相反地，许多高维空间中的数据集也可削减至低维空间数据，而不必丢失重要信息。这一点也通过众多降维方法的有效性反映出来，如应用广泛的主成分分析方法。针对距离函数和最近邻搜索，当前的研究也表明除非其中存在太多不相关的维度，带有维数灾难特色的数据集依然可以处理，因为相关维度实际上可使得许多问题（如聚类分析）变得更加容易。另外，对于许多方法因为维数过高而处理棘手的数据集上，像马尔科夫蒙特卡洛或共享最近邻搜索方法^[3]可以表现得很好。

组合学

在一些问题中，每个变量都可取一系列离散值中的一个，或者可能值的范围被划分为有限个可能性。把这些变量放在一起，则必须考虑很多种值的组合方式，这后果就是常说的组合爆炸（英语：Combinatorial explosion）。即使在最简单的二元变量例子中，可能产生的组合总数就已经是在维数上呈现指数级的 $O(2^{d})$ 。一般而言，每个额外的维度都需要成倍地增加尝试所有组合方式的影响。

采样

当在数学空间上额外增加一个维度时，其体积会呈指数级的增长。如，点间距离不超过10^-2=0.01，10²=100个均匀间距的样本点足够采样到一个单位区间（“一个维度的立方体”）；一个10维单元超立方体的等价采样，其相邻两点间的距离为10^-2=0.01则需要10²⁰个样本点。一般而言，点距为10^-n的10维超立方体所需要的样本点数量，是1维超立方体这样的单元区间的10^n(10-1)倍。在上面的n=2的例子中：当样本距离为0.01时，10维超立方体所需要的样本点数量会比单元区间多10¹⁸倍。这一影响就是上面所述组合学问题中的组合结果，距离函数问题将在下面介绍。

优化

当用数值逆向归纳法（英语：backward induction）解决动态优化问题时，目标函数针对每个可能的组合都必须计算一遍，当状态变量的维度很大时，这是极其困难的。

机器学习

在机器学习问题中，需要在高维特征空间（每个特征都能够取一系列可能值）的有限数据样本中学习一种“自然状态”（可能是无穷分布），要求有相当数量的训练数据含有一些样本组合。给定固定数量的训练样本，其预测能力随着维度的增加而减小，这就是所谓的Hughes影响^[4]或Hughes现象（以Gordon F. Hughes命名）。^[5]^[6]

贝叶斯统计

在贝叶斯统计中维数灾难通常是一个难点，因为其后验分布（英语：posterior distributions）通常都包含着许多参数。

然而，这一问题在基于模拟的贝叶斯推理（尤其是适应于很多实践问题的马尔科夫蒙特卡洛方法）出现后得到极大地克服，当然，基于模拟的方法收敛很慢，因此这也并不是解决高维问题的灵丹妙药。

距离函数

当一个度量，如欧几里德距离使用很多坐标来定义时，不同的样本对之间的距离已经基本上没有差别。

一种用来描述高维欧几里德空间的巨型性的方法是将维数 $d$ 且半径 $r$ 的内接超球体体积，和相同维数但边长为 $2r$ 的超立方体体积相比较。这样一个球体的体积计算如下： $V_{\mathrm {hypersphere} }={\frac {2r^{d}\pi ^{d/2}}{d\Gamma (d/2)}}$ ^{[注 1]}

立方体的体积计算如下： $V_{\mathrm {hypercube} }=(2r)^{d}$

随着空间维度 $d$ 的增加，相对于超立方体的体积来说，超球体的体积就变得微不足道了。这一点可以从当 $d$ 趋于无穷时比较前面的比例清楚地看出： ${\frac {V_{\mathrm {hypersphere} }}{V_{\mathrm {hypercube} }}}={\frac {\pi ^{d/2}}{d2^{d-1}\Gamma (d/2)}}\rightarrow 0$

当 $d\rightarrow \infty$ 。因此，在某种意义上，几乎所有的高维空间都远离其中心，或者从另一个角度来看，高维单元空间可以说是几乎完全由超立方体的“边角”所组成的，没有“中部”，这对于理解卡方分布是很重要的直觉理解。给定一个单一分布，由于其最小值和最大值与最小值相比收敛于0，因此，其最小值和最大值的距离变得不可辨别。 $\lim _{d\to \infty }{\frac {\operatorname {dist} _{\max }-\operatorname {dist} _{\min }}{\operatorname {dist} _{\min }}}\to 0$ .

这通常被引证为距离函数在高维环境下失去其意义的例子。

延伸阅读

组合爆炸（英语：Combinatorial explosion）
相似度集中（英语：Concentration of measure）
降维
傅立叶变换列表（英语：Fourier-related transforms）
高维数据聚类（英语：Clustering high-dimensional data）

注释

^ 在

n

维欧氏空间里，半径

R

的球体之

n

维体积为

V_{n}(R)={\frac {\pi ^{n/2}}{\Gamma ({\frac {n}{2}}+1)}}R^{n}

注释-式1

其中 $\Gamma$ 表示Γ函数。因此根据(注释-式1)半径 $r$ 维数 $d$ 的球体体积为

V_{\mathrm {hypersphere} }=V_{d}(r)={\frac {\pi ^{d/2}}{\Gamma ({\frac {d}{2}}+1)}}r^{d}

注释-式2

Γ函数的递回公式为

\Gamma (x+1)=x\Gamma (x)

注释-式3

将(注释-式3)的 $x$ 以 $d/2$ 取代

\Gamma \left({\frac {d}{2}}+1\right)={\frac {d\Gamma (d/2)}{2}}

注释-式4

将(注释-式4)代入(注释-式2)得到

V_{\mathrm {hypersphere} }={\frac {2r^{d}\pi ^{d/2}}{d\Gamma (d/2)}}

注释-式5

参考资料

^ Richard Ernest Bellman; Rand Corporation. Dynamic programming. Princeton University Press. 1957. ISBN 978-0-691-07951-6. ^{[失效链接]}
Republished: Richard Ernest Bellman. Dynamic Programming. Courier Dover Publications. 2003 [2012-05-18]. ISBN 978-0-486-42809-3. （原始内容存档于2021-02-23）.
^ Richard Ernest Bellman. Adaptive control processes: a guided tour. Princeton University Press. 1961 [2012-05-18]. （原始内容存档于2021-02-23）.
^ ^3.0 ^3.1 Michael E. Houle, Hans-Peter Kriegel, Peer Kröger, Erich Schubert, Arthur Zimek. Can Shared-Neighbor Distances Defeat the Curse of Dimensionality?. Springer, Berlin, Heidelberg: 482–500. 2010-06-30 [2018-04-02]. ISBN 9783642138171. doi:10.1007/978-3-642-13818-8_34. （原始内容存档于2018-06-17）（英语）.
^ Thomas Oommen, Debasmita Misra, Navin K. C. Twarakavi, Anupma Prakash, Bhaskar Sahoo, Sukumar Bandopadhyay. An Objective Analysis of Support Vector Machine Based Classification for Remote Sensing. Mathematical Geosciences. 2008-05-01, 40 (4): 409–424 [2018-04-02]. ISSN 1874-8961. doi:10.1007/s11004-008-9156-6. （原始内容存档于2018-06-18）（英语）.
^ Hughes, G.F., 1968. "On the mean accuracy of statistical pattern recognizers", IEEE Transactions on Information Theory, IT-14:55-63.
^ Not to be confused with the unrelated, but similarly named, Hughes effect in electromagnetism (named after Declan C. Hughes^{[永久失效链接]}) which refers to an asymmetry in the hysteresis curves of laminated cores made of certain magnetic materials, such as permalloy or mu-metal, in alternating magnetic fields.
^ R. B. Marimont and M. B. Shapiro, "Nearest Neighbour Searches and the Curse of Dimensionality", Journal of the Institute of Mathematics and its Applications, 24, 1979, 59-70.
^ E. Chavez et al., "Searching in Metric Spaces", ACM Computing Surveys, 33, 2001, 273-321.
^ Thomas Bernecker, Michael E. Houle, Hans-Peter Kriegel, Peer Kröger, Matthias Renz, Erich Schubert, Arthur Zimek. Quality of Similarity Rankings in Time Series. Springer, Berlin, Heidelberg: 422–440. 2011-08-24 [2018-04-02]. ISBN 9783642229213. doi:10.1007/978-3-642-22922-0_25. （原始内容存档于2019-12-23）（英语）.
^ Radovanovi?, Milo?; Nanopoulos, Alexandros; Ivanovi?, Mirjana. Hubs in space: Popular nearest neighbors in high-dimensional data (PDF). Journal of Machine Learning Research. 2010, 11: 2487–2531 [2012-05-18]. （原始内容存档 (PDF)于2019-07-17）.
^ Milos Radovanović, Alexandros Nanopoulos, Mirjana Ivanović. On the existence of obstinate results in vector space models. ACM: 186–193. 2010-07-19 [2018-04-02]. ISBN 9781450301534. doi:10.1145/1835449.1835482.

Bellman, R.E. 1957. Dynamic Programming. Princeton University Press, Princeton, NJ.
- Republished 2003: Dover, ISBN 0486428095.
Bellman, R.E. 1961. Adaptive Control Processes. Princeton University Press, Princeton, NJ.
Powell, Warren B. 2007. Approximate Dynamic Programming: Solving the Curses of Dimensionality. Wiley, ISBN 0470171553.

[7] 在 $n$ 维欧氏空间里，半径 $R$ 的球体之 $n$ 维体积为
$V_{n}(R)={\frac {\pi ^{n/2}}{\Gamma ({\frac {n}{2}}+1)}}R^{n}$ 注释-式1

其中 $\Gamma$ 表示Γ函数。因此根据(注释-式1)半径 $r$ 维数 $d$ 的球体体积为

$V_{\mathrm {hypersphere} }=V_{d}(r)={\frac {\pi ^{d/2}}{\Gamma ({\frac {d}{2}}+1)}}r^{d}$ 注释-式2

Γ函数的递回公式为

$\Gamma (x+1)=x\Gamma (x)$ 注释-式3

将(注释-式3)的 $x$ 以 $d/2$ 取代

$\Gamma \left({\frac {d}{2}}+1\right)={\frac {d\Gamma (d/2)}{2}}$ 注释-式4

将(注释-式4)代入(注释-式2)得到

$V_{\mathrm {hypersphere} }={\frac {2r^{d}\pi ^{d/2}}{d\Gamma (d/2)}}$ 注释-式5

[1] Richard Ernest Bellman; Rand Corporation. Dynamic programming. Princeton University Press. 1957. ISBN 978-0-691-07951-6. ^{[失效链接]}
Republished: Richard Ernest Bellman. Dynamic Programming. Courier Dover Publications. 2003 [2012-05-18]. ISBN 978-0-486-42809-3. （原始内容存档于2021-02-23）.

[2] Richard Ernest Bellman. Adaptive control processes: a guided tour. Princeton University Press. 1961 [2012-05-18]. （原始内容存档于2021-02-23）.

[houle-ssdbm10-3] 3.0 ^3.1 Michael E. Houle, Hans-Peter Kriegel, Peer Kröger, Erich Schubert, Arthur Zimek. Can Shared-Neighbor Distances Defeat the Curse of Dimensionality?. Springer, Berlin, Heidelberg: 482–500. 2010-06-30 [2018-04-02]. ISBN 9783642138171. doi:10.1007/978-3-642-13818-8_34. （原始内容存档于2018-06-17）（英语）.

[4] Thomas Oommen, Debasmita Misra, Navin K. C. Twarakavi, Anupma Prakash, Bhaskar Sahoo, Sukumar Bandopadhyay. An Objective Analysis of Support Vector Machine Based Classification for Remote Sensing. Mathematical Geosciences. 2008-05-01, 40 (4): 409–424 [2018-04-02]. ISSN 1874-8961. doi:10.1007/s11004-008-9156-6. （原始内容存档于2018-06-18）（英语）.

[5] Hughes, G.F., 1968. "On the mean accuracy of statistical pattern recognizers", IEEE Transactions on Information Theory, IT-14:55-63.

[6] Not to be confused with the unrelated, but similarly named, Hughes effect in electromagnetism (named after Declan C. Hughes^{[永久失效链接]}) which refers to an asymmetry in the hysteresis curves of laminated cores made of certain magnetic materials, such as permalloy or mu-metal, in alternating magnetic fields.

[8] R. B. Marimont and M. B. Shapiro, "Nearest Neighbour Searches and the Curse of Dimensionality", Journal of the Institute of Mathematics and its Applications, 24, 1979, 59-70.

[9] E. Chavez et al., "Searching in Metric Spaces", ACM Computing Surveys, 33, 2001, 273-321.

[houle-sstd11-10] Thomas Bernecker, Michael E. Houle, Hans-Peter Kriegel, Peer Kröger, Matthias Renz, Erich Schubert, Arthur Zimek. Quality of Similarity Rankings in Time Series. Springer, Berlin, Heidelberg: 422–440. 2011-08-24 [2018-04-02]. ISBN 9783642229213. doi:10.1007/978-3-642-22922-0_25. （原始内容存档于2019-12-23）（英语）.

[11] Radovanovi?, Milo?; Nanopoulos, Alexandros; Ivanovi?, Mirjana. Hubs in space: Popular nearest neighbors in high-dimensional data (PDF). Journal of Machine Learning Research. 2010, 11: 2487–2531 [2012-05-18]. （原始内容存档 (PDF)于2019-07-17）.

[12] Milos Radovanović, Alexandros Nanopoulos, Mirjana Ivanović. On the existence of obstinate results in vector space models. ACM: 186–193. 2010-07-19 [2018-04-02]. ISBN 9781450301534. doi:10.1145/1835449.1835482.

[1]

[2]

[3]

[4]

[5]

[6]

[注 1]

[7]

[8]

[9]

[10]

[11]

组合学

采样

优化

机器学习

贝叶斯统计

距离函数

最近邻搜索

k近邻分类

延伸阅读

注释

参考资料