维数灾难 · aiwiki.page

维数灾难是在高维空间中进行分析、学习或计算时所遇到的各种困难的统称。在统计学和机器学习中，相对于观测数据所处的空间，数据会变得稀疏；在数值计算中，维持固定的分辨率可能需要投入随维度呈指数增长的资源。这一说法源于理查德·贝尔曼对动态规划的研究。它描述的是若干相互关联的现象，而不是一个普遍适用的定理，也不是一道超过后计算就不可能进行的固定门槛。(cs.cmu.edu)

指数增长与稀疏覆盖

一个基本例子是 $d$ 维单位立方体中的规则网格。如果每个坐标轴上都有 $m$ 个网格位置，那么它们的笛卡尔积包含

N=m^d

个点。每个坐标轴上设置十个位置，在二维空间中需要 100 个点，在六维空间中需要一百万个点，而在十维空间中则需要一百亿个点。因此，维度即使只增加少许，也可能使穷举制表变得不切实际。在离散化的优化问题中，如果需要存储每一种可能状态对应的值，这一点尤为重要。(cs.cmu.edu)

同样的增长规律也影响采样。假设训练数据在 $[0,1]^d$ 上服从均匀分布。一个边长为 $r$ 、各边与坐标轴平行且完全位于单位立方体内的小立方体，其体积占单位立方体体积的比例为 $r^d$ 。因此，在 $n$ 个观测值中，落在其中的观测值数量的期望值为 $nr^d$ 。要使这一期望数量保持为 $k$ ，就需要 $n=k/r^d$ ；当 $r<1$ 且固定不变时，所需样本量随 $d$ 呈指数增长。(stat.cmu.edu)

反过来，包含总体中比例为 $q$ 的观测值的小立方体，其边长为 $q^{1/d}$ 。当 $q=0.01$ 时，这一边长在二维空间中约为 0.10，在十维空间中约为 0.63，在一百维空间中约为 0.955。因此，一个仅包含少量观测值的邻域，可能在每个坐标方向上都几乎横跨整个取值范围。这些计算依赖于均匀分布假设，但说明了为什么“局部”估计会变得困难。(courses.cs.cornell.edu)

高维几何

高维欧几里得空间还会出现距离集中现象。在适当的假设下，例如各坐标相互独立且尺度相近，欧几里得距离的平方是许多分量的总和。它的绝对大小通常随维度增加而增大，相对波动却会减小。因此，距离在区分邻近观测值与一般观测值时，可能不再那么有效。这并不意味着所有距离都会变得完全相等，也不意味着每个数据集都会失去有意义的邻域结构。(courses.cs.cornell.edu)

边界效应提供了另一个例子。单位立方体中，与每一个面都至少相距 $\epsilon$ 的区域，其体积占比为

(1-2\epsilon)^d,\qquad 0<\epsilon<\tfrac12.

对于固定的 $\epsilon$ ，这一比例随着维度增加而趋于零：几乎所有体积都位于至少一个边界面的附近。这里说的是到最近面的距离，而不一定是到某个顶点的距离。沿每个坐标方向去除边界带后，剩下的是一个较小的立方体；上述结论可直接由其体积得出。(stat.cmu.edu)

统计学习

K近邻算法利用邻近的观测值进行预测。除非样本量大幅增加，否则稀疏的覆盖会迫使该算法使用越来越宽的邻域。同样，密度估计和局部回归也必须在两种情况之间寻求平衡：邻域过小会导致观测值不足，邻域过大则会把真实的变化平滑掉。这体现了偏差-方差权衡：更强的平滑会降低方差，但可能增大估计量的偏差。(stat.cmu.edu)

在标准的光滑性假设下，带宽为 $h$ 的局部回归估计量，其偏差的平方可为 $h^4$ 量级，方差可为 $1/(nh^d)$ 量级。平衡这两项，可得均方误差的收敛速率为

n^{-4/(d+4)}

量级。随着维度增加，指数的绝对值越来越小。这是一个有代表性的非参数结果，而不是适用于所有学习算法的性能公式。(stat.cmu.edu)

与维度有关的困难也不同于过拟合。不受约束的模型可能拟合有限样本中的偶然模式，但即使没有复杂的模型拟合，稀疏覆盖也可能损害预测效果。泛化（机器学习）取决于样本量、噪声、模型假设和数据结构，而不仅仅取决于所记录的特征数量。(stat.cmu.edu)

计算上的影响

在动态规划中，用于表示离散状态空间上价值函数的表，其规模可能随状态变量数量呈指数增长。贝尔曼方程提供了递推关系，但仅靠递推并不能消除表示所有状态所需的开销。(cs.cmu.edu)

最近邻搜索面临的是另一种计算困难。基于树的索引在低维空间中能够高效排除大片区域，但随着维度增加，其剪枝优势往往会减弱。搜索的开销可能接近逐一检查所有观测值的开销。性能还取决于样本量、距离度量和数据集的内在结构；高维并不会给所有方法施加一个统一的计算复杂性界限。(scikit-learn.org)

结构假设与缓解方法

数据所在空间的坐标维数，不一定等于数据的有效维数。观测值可能分布在某个低维线性子空间或流形附近。降维方法，包括主成分分析和流形学习，旨在寻找能够利用这种结构的数据表示。特征选择则是保留原始变量的一个子集。这些方法是否有用，取决于降维后的表示能否保留与任务相关的信息。(scikit-learn.org)

正则化限制的是模型的灵活性，而不一定减少输入变量的数量。例如，套索回归可以将系数设为零，而岭惩罚会缩小系数，但通常不会使其归零。这类约束牺牲了不受限制的逼近能力，以换取更稳定的估计。(scikit-learn.org)

一些数值方法也能避免穷尽整个空间。在样本相互独立且被积函数的方差有限时，蒙特卡洛积分的均方根误差与 $n^{-1/2}$ 成正比。然而，其方差和函数求值成本本身可能依赖于维度，因此，指数与维度无关，并不保证计算工作量也与维度无关。(arxiv.org)

参考来源

Dynamic Programmingcs.cmu.edu
ADAfaEPoVstat.cmu.edu
k-nearest neighbors / Curse of Dimensionalitycourses.cs.cornell.edu
Waste, fraud and abuse: Sources of failure in applied statistical learning projectsstat.cmu.edu
6. Nearest Neighbors — scikit-learn documentationscikit-learn.org
Is the k-NN classifier in high dimensions affected by the curse of dimensionality?arxiv.org
1. Linear Models — scikit-learn documentationscikit-learn.org
Approximate and integrate: Variance reduction in Monte Carlo integration via function approximationarxiv.org
A Note on Monte Carlo Integration in High Dimensionsarxiv.org