05 · 维度灾难
⏱ 28 分钟 | 原预计,仅供参考;可以分次读 | ⭐⭐ 先看实验条件,再判断高维风险
🎯 一句话
特征变多后,数据覆盖空间和判断“谁与谁接近”都可能更困难;但高维不等于模型必然失效。
这一章用四个小实验,区分体积、位置、距离和网格覆盖。先看距离实验,再看如何诊断自己的数据;推导可以第二遍再读。
这里的维度 $d$ 是“每个样本用多少个数表示”。一张 RGB 图像可以有很多像素数值,但这些数不一定提供同样多的独立信息。
🔬 一、四个数字实验:先分清在测什么
前两个表由几何公式计算;第三个表来自可复现的随机实验;第四个表是网格计数。它们不是同一分布下的四次实验,也不是模型准确率测试。
实验 1:内切球在立方体里占多少体积?
取边长为 1 的 $d$ 维立方体。内切球与它同中心,半径为 0.5。二维时就是“正方形里的内切圆”。
| 维度 $d$ | 球占立方体的体积比例 |
|---|---|
| 2 | 78.54% |
| 3 | 52.36% |
| 5 | 16.45% |
| 10 | 0.2490% |
| 20 | 0.000002461% |
| 50 | $1.537\times10^{-26}\%$ |
看第二列:维度增加时,内切球覆盖的比例迅速变小。 从立方体中均匀抽一个点,它落在这个球里的概率就是该比例。
“在内切球外”不等于“紧贴某个顶点”。中心仍然存在;只是固定半径的球,覆盖不了立方体里大部分位置。
想核对数字:球体积公式与“角落”的区别
体积比例为:
$$R_d=\frac{\pi^{d/2}}{2^d\Gamma(d/2+1)}$$
- $R_d$:比例,乘 100 后才是百分数。
- $d$:维度;分母中的 $2^d$ 来自半径 $0.5$ 的 $d$ 次方。
- $\Gamma$:阶乘的推广,整数 $k$ 满足 $\Gamma(k+1)=k!$。现在不必掌握它的推导。
立方体确实有 $2^d$ 个顶点,100 维时约为 $1.27\times10^{30}$ 个。但“顶点很多”不是“体积都被顶点瓜分”的证明。
更稳妥的直觉是:欧氏距离把每个坐标的偏差平方相加。对于均匀立方体中的点,到中心的平方距离均值是 $d/12$;内切球的半径平方却一直是 $1/4$。
很多个不大的偏差累积起来,也能把点放到球外,不必有某个坐标极端接近顶点。
实验 2:均匀球内取点,为什么常落在薄壳?
这次换一个取样区域:半径为 1 的球,在球的体积内均匀取点。
最外面 5% 厚度,是“到中心的距离大于 0.95、不超过 1”的区域。不是数学上的零厚度表面。
看右侧比例条:同样是最外 5% 的径向厚度,维度越高,它占的体积比例越大。
| 维度 $d$ | 最外 5% 厚度的体积占比 |
|---|---|
| 1 | 5.0% |
| 3 | 14.3% |
| 10 | 40.1% |
| 50 | 92.3% |
| 100 | 99.4% |
100 维时,约 99.4% 的均匀球内样本落在这层薄壳里。 中心没有消失;只是它附近的一小块占整体的比例很低。
为什么是这些比例?
把半径缩成原来的 0.95,各方向一起缩放,内部球的体积就变成原来的 $0.95^d$。用整体减去内部:
$$S_d=1-0.95^d$$
$S_d$ 是薄壳的体积比例。代入 $d=100$,得到约 0.9941,也就是 99.41%。
这一结论描述的是到中心的位置分布。它本身不能证明任意两点距离相同,更不能单独推出 kNN 分类失败。
对异常检测的提醒:先知道正常样本通常离中心多远。 若正常分布本来就在薄壳附近,不能沿用低维的固定小半径,把大多数正常点都判成异常。
距离仍可用于异常检测,但要结合正常数据的距离分布、尾部概率和验证结果。别把均匀球的结论直接套到稀疏、相关或多簇数据上。
实验 3:最近与最远的距离,差距会缩小吗?
固定样本数为 1000。 每个坐标独立地在 $[0,1)$ 均匀取值;查询点也独立抽取。用欧氏距离找离查询点最近、最远的样本。
用一个比值衡量相对差距:
$$C=\frac{r_{\max}-r_{\min}}{r_{\min}}$$
- $r_{\min}$:查询点到最近样本的距离。
- $r_{\max}$:查询点到最远样本的距离。
- $C$:最远距离比最近距离多出的比例;这里要求 $r_{\min}>0$。
| 维度 $d$ | 相对差距 $C$,保留两位小数 |
|---|---|
| 2 | 280.02 |
| 5 | 7.40 |
| 10 | 2.41 |
| 50 | 0.89 |
| 100 | 0.41 |
| 500 | 0.19 |
这一次 500 维实验中,最远距离比最近距离大约多 18.65%。 表中四舍五入为 0.19,不是“所有 500 维数据必定相差 19%”。
二维这一行很大,是因为这次查询点恰好离某个样本非常近,分母很小。换种子、查询点、样本数或距离定义,数字都会变。
自己复现这六行结果(需要 NumPy)
用途:只观察随机点的距离差距,不训练模型,也不计算分类准确率。完整运行下面一段;随机数生成器在六轮之间连续使用,因此维度列表的顺序也属于复现条件。
import numpy as np
rng = np.random.RandomState(0)
for d in [2, 5, 10, 50, 100, 500]:
X = rng.rand(1000, d)
q = rng.rand(1, d)
dist = np.linalg.norm(X - q, axis=1)
contrast = (dist.max() - dist.min()) / dist.min()
print(f"d={d:<5} 相对差距 = {contrast:.2f}")
- 第 3 行固定随机种子;第 4 行列出表中的全部六个维度。
- 第 5–6 行生成样本和独立查询点。
- 第 7 行沿每个样本的坐标计算欧氏距离。
- 第 8–9 行计算并打印表里的比值。
运行后最后一行的相对差距应为 0.19。它是本次随机实验的结果,不是模型准确率,也不是通用失效阈值。
该警惕什么? 如果许多无关特征把距离差异淹没,邻居可能不再代表相似的任务对象。这会影响 kNN,也可能影响 K-Means、DBSCAN、核方法、相似度检索和异常检测。
不能顺着推出什么? 本实验没有标签、没有比较预测结果,也没有测试余弦相似度。不能由它判定这些算法“全线失效”。
最近邻研究也明确区分会出现距离集中的条件与仍有意义的高维任务;可选阅读:Beyer 等的原始论文。
实验 4:铺满一张网格,需要多少点?
每个坐标轴选 10 个位置,并取所有坐标组合。 这才是完整网格,点数为 $10^d$。
| 维度 $d$ | 完整网格点数 |
|---|---|
| 1 | 10 |
| 3 | 1,000 |
| 5 | 100,000 |
| 10 | $10^{10}$,即 100 亿 |
| 20 | $10^{20}$ |
两个轴各取 10 个位置,要覆盖全部组合需要 100 个点。 只沿对角线放 10 个点,虽然两个轴都出现了 10 个值,却没覆盖其余组合。
这个计数说明:用固定精度铺满整个空间,成本会随维度指数增加。
它不是所有学习任务的样本量下界。模型不一定需要填满空间;有用规律可能只依赖少数特征,或受线性、稀疏、局部结构等约束。因此不能推出“高维必然过拟合”。
🧠 二、统一直觉:多个条件与多个偏差叠加
先记两件事:同时满足很多条件可能很难;很多个小偏差累加也可能很大。
用概率理解,但别漏掉“独立”这个前提
假设各坐标独立,每个坐标落在指定中央区间的概率都是 $p$。那么所有坐标都在区间内的概率是 $p^d$。
若每个坐标偏出该区间的概率为 $q$,至少一个坐标偏出的概率是 $1-(1-q)^d$。当 $0<q<1$ 时,它随维度趋近 1,不能说成无界的“指数增长”。
“某个坐标偏出区间”和“欧氏距离超过某个半径”不是同一个事件。均匀球内的坐标也不独立,不能把这个乘法直接当成薄壳公式的证明。
| 回看哪个实验 | 它真正比较什么 |
|---|---|
| 内切球 | 球与立方体的体积比例 |
| 薄壳 | 球内点到中心的径向位置 |
| 最近邻 | 指定数据与查询分布下的相对距离 |
| 网格 | 覆盖全部坐标组合所需的点数 |
没有一条“点都去角落了”的口号,能代替这四组不同条件。
🔎 三、哪些方法需要重点检查?
风险大小取决于数据表示、任务与样本量,不是只看算法名字或维度数字。
| 方法或用途 | 需要警惕什么 |
|---|---|
| kNN / 核方法 | 选定距离、核与尺度下,邻近是否仍与目标有关 |
| K-Means / DBSCAN | 距离和密度定义能否区分真正的簇 |
| 异常检测 | 正常点的典型距离是什么;是否把正常薄壳当异常 |
| 核密度估计 | 在较少结构约束下,局部区域里是否有足够样本 |
| 其他局部方法 | 邻域仍可定义,但固定样本数下可能难以兼顾“小范围”与“足够点” |
| 2D / 3D 可视化 | 投影保留了什么,又丢掉了什么 |
低维图可以帮助探索,不能独自完成高维验证。 例如 t-SNE 主要服务局部邻域展示;簇间距离、面积和全局分离程度不能直接按原空间解释。
不是“图完全不可信”,而是要回到原特征或模型空间验证。见基础教程第 6 章。
🛠️ 四、五条出路:按任务选择,不排万能名次
① 降维:用更少的坐标表示数据
PCA、自编码器等可以压缩表示,再检查验证效果、稳定性和成本。
PCA 优先保留方差,不保证保留最有预测价值的方向。降维参数应在训练数据或当前训练折上拟合,不能偷看验证集。继续看基础教程第 6 章。
② 特征选择:保留有用的原始特征
如果有很多无关、重复或不稳定的特征,筛选可能比压缩更容易解释。
但“大多数维度都是噪声”不是默认事实。用训练折完成筛选,再比较验证表现;别看完整数据的标签挑完特征,才去做交叉验证。
③ 归纳偏置:利用已知的结构
归纳偏置,就是模型预先偏向哪些规律。 它让模型不必从所有可能函数里毫无方向地寻找。
一张 $224\times224\times3$ 的 RGB 图像有 150,528 个像素数值。CNN 利用局部连接与共享权重,例如在不同位置复用一个 $3\times3$ 卷积核。
- 局部连接:先观察局部组合,而不是每个输出都直接连接所有像素。
- 共享权重:同一种特征在不同位置可以用同一套参数检测。
- 多层组合:再把局部信息逐步组合成较大范围的表示。
平移等变是“输入移动,特征响应也相应移动”;不是“移动后输出完全不变”。理想卷积具有这种等变性,边界处理、步幅和池化会影响实际网络的表现。相关原理见卷积等变性研究。
这降低的是要学习的某些自由度,不是在证明图像的内在维度必然变小。也不能说 kNN 无法处理图像:换成适合任务的图像表示后,邻居检索仍可能有用。见基础教程第 12 章。
④ 正则化 / 先验:限制可接受的解
在拟合数据之外,加入权重大小、稀疏性等约束,可以降低过度追随训练样本的风险。
L2 惩罚可在合适的似然与 MAP 表述下对应高斯先验;不能把所有正则化都叫高斯先验。L1 对应的常见例子是拉普拉斯先验。
接着看第 2 章的概率解释,以及第 9 章的假设空间与复杂度。
⑤ 流形假设:外表维度不等于自由变化的维度
“流形假设”认为:某些高维数据可能主要集中在较低维、局部可用少数坐标描述的结构附近。它是建模假设,不是所有真实数据都满足的定理。
先看一个能完全核对的例子:平面上的点满足 $y=x^2$,并限制 $0\le x\le1$。虽然每个点写成两个坐标,但只要确定 $x$,$y$ 就随之确定。
看曲线上的点:两个坐标,由一个自由参数决定。这是示意例子,不是真实照片的测量结果。
真实照片确实包含结构与相关性,但不能因此断言“所有照片只有几十个内在维度”,也不能用图中这条曲线证明深度学习必然成功。
表示学习 / Embedding 与这个想法有关,但不等同于已证明找到了流形。
- 推荐系统可以把上亿个 ID 的 one-hot 表示映射为 64 维向量;实际常用查表,不必先造出完整 one-hot。
- 64 维是模型的设计选择,是否保留有用关系,需要由任务验证。
- 深度网络的中间层可以升维,也可以降维;每一层都应看它是否形成了更适合任务的表示。
🔬 五、一个实用的诊断
不要用“特征超过多少就失败”或“样本超过 $10^d$ 就安全”做判断。 按下面顺序检查。
- 写清输入。 记录样本数 $n$、特征数 $d$、单位、稀疏程度和重复特征;先确定验证划分。
- 检查距离。 在训练数据上拟合预处理,对多个查询观察近邻、距离分布与标签关系。
- 做一组对照。 比较原特征、筛选后特征、降维表示;使用相同验证划分和评价指标。
- 看结果而非维度标签。 检查验证误差、邻居是否有意义、运行成本和学习曲线,再决定用哪种表示与模型。
距离比值与树模型:两个常见误判
最近 / 最远接近 1,只是相对差距小的信号,不是预测失效判决。 极端值容易受离群点影响,最好同时看分位数、多次查询和邻居的任务相关性。
若用训练样本当查询,要排除它自身。最近距离为 0 时,也不能直接除以它;重复点与相同输入但不同标签的问题应另查。
树模型不直接依赖全维度距离,但不是对高维免疫。 很多无关特征会增加偶然切分、特征选择和搜索成本;每片叶子也需要足够样本。
线性模型同样可能受影响。例如参数比样本多时,无约束拟合可能不唯一或不稳定;结构假设与正则化能帮助,但还要验证。
见ML 基础 04a · 集成学习与 GBDT。不要把“没有这条距离机制”误读成“没有任何维度风险”。
🔗 六、和站内其他章的关系
| 相关内容 | 这章提供的理解 |
|---|---|
| 推荐算法:交互矩阵稀疏 | 观测过的用户—物品组合少;具体稀疏比例取决于数据,不是统一的 99.99% |
| 推荐算法:Embedding | 学任务相关表示,不等于已经证明低维流形 |
| 基础教程第 6 章:PCA | 压缩方差与保留预测信号要分开验证 |
| 基础教程第 6 章:t-SNE | 看局部关系,别把图上的所有距离当原空间距离 |
| 基础教程第 12 章:CNN | 用局部性与共享权重加入结构假设 |
| 基础教程第 4 章:树模型 | 不依赖全维距离,但仍要控制过拟合与噪声特征 |
| 基础教程第 14 章:归纳偏置 vs 数据量 | 假设与任务匹配时,能减少需要从数据中学习的内容 |
✅ 检查点
- 100 维单位球的 99.4% 指哪种分布、哪层区域?能直接判断异常吗?
- 本次 500 维实验测到了什么?为什么不能宣布 kNN 失效?
- $10^d$ 对应哪种采样方式?它能证明必然过拟合吗?
- 四个实验各自比较什么?$p^d$ 又需要什么前提?
- 五条出路是什么?怎么判断对当前任务是否有帮助?
- 曲线例子为什么是两个坐标、一个自由参数?真实数据一定如此吗?
- 树模型避开了哪种距离问题?它还面临哪些高维风险?
展开核对答案
- 球的体积内均匀取点,半径 0.95 到 1 的薄壳。应与正常径向分布比较,不能见远就判异常。
- 固定的随机实验中,相对差距约 0.1865。没有标签与准确率对照,不能判定预测性能。
- 每轴 10 个位置的完整笛卡尔网格。学习可能依赖结构,不必铺满整个空间。
- 分别是体积比例、径向位置、相对距离、完整组合计数。乘出 $p^d$ 需要坐标事件独立且各自概率相同。
- 降维、特征选择、归纳偏置、正则化/先验、利用可能的低维结构。用一致的验证方案比较,不设万能排序。
- $x$ 确定后,$y=x^2$ 随之确定。流形是假设,不能保证所有真实数据都低维。
- 通常不算全维距离;但噪声特征、偶然切分、搜索成本和叶子样本不足仍有风险。
本节回顾
先记住这三件事
- 先看分布、样本数和距离定义;高维不是自动失败。
- 完整网格很贵,不等于每个学习任务都要填满空间。
- 用特征、表示与结构假设做对照,再看验证结果。
下一节 👉 05b-PCA的推导.md