Skip to content
Lex Blog

零曲率与正曲率空间中的维数灾难

维数灾难并非某种特定的几何结构，而是由高维空间内在性质所引发的一类现象。

维数灾难并非某种特定的几何结构，而是由高维空间的内在性质所引发的一类现象。特别是，测度集中与距离集中等效应会导致度量区分能力退化，使许多基于距离的方法失效。

本文从数学与统计的角度，介绍不同曲率空间中的维数灾难效应。

欧氏空间

要引入维数灾难，我们需要从空间中的样本分布说起。

先从一维情形开始：考虑数值范围 [−1,1][-1,1] 内的一段线段，并假设所有样本在这条线段上随机且均匀地分布。同时，该线段的总测度为 1 个单位长度。

现在考虑包含 90% 测度的内部区域，即区间 [−0.9,0.9][-0.9, 0.9]，并将剩余的 10% 视为具有一定厚度的薄外壳。显然，90% 的样本随机分布在 [−0.9,0.9][-0.9, 0.9] 内，而其余 10% 位于外壳区域，即 [−1,−0.9)[-1, -0.9) 和 (0.9,1](0.9, 1]。

显然，我们可以推出一维情形下分布在薄外壳上的样本比例为 P外壳d=1=10%P_\text{外壳}^{d=1} = 10\%。

现在，让我们把类似的情形推广到二维平面中的圆。众所周知，圆的面积可以用公式 S=πr2S = \pi r^2 计算。同样地，我们考虑包含 90% 测度的内部区域，即 x2+y2≤0.9x^2 + y^2 \leq 0.9，以及剩余的有限外壳 0.9<x2+y2≤10.9 < x^2 + y^2 \leq 1。接下来，我们需要计算分布在这两个区域中的样本比例。

S内部=π⋅(0.9)2=0.81πS外壳=S单位−S内部=π⋅12−π⋅(0.9)2=0.19πP外壳d=2=S外壳S单位=0.19ππ=19%\begin{aligned} S_\text{内部} = \pi \cdot (0.9)^2 = 0.81 \pi \\ S_\text{外壳} = S_\text{单位} - S_\text{内部} = \pi \cdot 1^2 - \pi \cdot (0.9)^{2} = 0.19\pi \\ P^{d=2}_\text{外壳} = \frac{S_\text{外壳}}{S_\text{单位}} = \frac{0.19 \pi}{\pi} = 19\% \end{aligned}

类似地，我们可以继续在三维空间中探索。三维球体的体积为 V=43πr3V=\frac{4}{3} \pi r^3。

V内部=43π⋅(0.9)3=43π×0.729V外壳=V单位−V内部=43π⋅13−43π⋅(0.9)3=43π×0.271P外壳d=3=V外壳V单位=27.1%\begin{aligned} V_\text{内部} = \frac{4}{3} \pi \cdot (0.9)^3 = \frac{4}{3} \pi \times 0.729 \\ V_\text{外壳} = V_\text{单位} - V_\text{内部} = \frac{4}{3} \pi \cdot 1^3 - \frac{4}{3} \pi \cdot (0.9)^{3} = \frac{4}{3} \pi \times 0.271 \\ P^{d=3}_\text{外壳} = \frac{V_\text{外壳}}{V_\text{单位}} = 27.1\% \end{aligned}

在这里，我们似乎可以总结出一个一般规律：随着维数增加，分布在外壳上的样本比例持续增大，从 10%10\% 增至 27.1%27.1\%；而分布在内腔中的样本比例持续减小，从 90%90\% 降至 72.9%72.9\%。

为了严格验证这一结论，我们需要一般的数学推导。对于 dd 维空间，半径为 rr 的超球体体积为：

Vd(r)=πd/2Γ(d2+1)rd V^d(r) = \frac{\pi^{d/2}}{\Gamma\left(\frac{d}{2}+1\right)} r^d

其中：

  • Γ(⋅)\Gamma(\cdot) 是伽马函数；
  • 当 dd 为正整数且为偶数时，Γ(d2+1)=(d2)!\Gamma\left(\frac{d}{2}+1\right) = \left(\frac{d}{2}\right)!；
  • 若 dd 为奇数，伽马函数将给出含 π\sqrt{\pi} 的表达式。

我们有：

P外壳d=V外壳dV单位d=1d−(0.9)dP^{d}_\text{外壳} = \frac{V^d_\text{外壳}}{V^d_\text{单位}} = 1^d - (0.9)^d

对于高维情形 d→+∞d \rightarrow +\infty，我们有以下极限：

lim⁡d→+∞1d−(0.9)d=1−0=1\lim_{d \rightarrow +\infty} 1^d - (0.9)^d = 1 - 0 = 1

也就是说，随着维数 dd 增大，随机均匀样本趋向于分布在外壳上。这一现象被称为薄壳效应（Thin-Shell Effect）。

欧氏距离

考虑高维空间 Rd\mathbb{R}^d 中的随机向量：

x,y∼i.i.d. N(0,Id)x, y \sim \text{i.i.d.} \ \mathcal{N}(0, I_d)

向量 xx 的模长为：

∣∣x∣∣2=∑i=1dxi2||x||^2 = \sum_{i=1}^d x_i^2

由于 xi2∼χ2(1)x_i^2 \sim \chi^2(1)，我们有：

∣∣x∣∣2∼χ2(d)||x||^2 \sim \chi^2(d)

这里，χ2(k)\chi^2(k) 是卡方分布（Chi-Squared Distribution），定义为 kk 个相互独立、服从标准正态分布 N(0,1)\mathcal{N}(0,1) 的随机变量的平方和。在本例中，由于模长的平方是 dd 个这样的变量之和，所以自由度为 k=dk=d。

根据大数定律：

1d∣∣x∣∣2→1\frac{1}{d}||x||^2 \to 1

也就是说，向量的模长近似为 ∣∣x∣∣≈d||x|| \approx \sqrt{d}。

欧氏距离为：

∣∣x−y∣∣2=∣∣x∣∣2+∣∣y∣∣2−2⟨x,y⟩||x - y||^2 = ||x||^2 + ||y||^2 - 2 \langle x, y \rangle

我们已知：

∣∣x∣∣2≈d,∣∣y∣∣2≈d||x||^2 \approx d, \quad ||y||^2 \approx d

向量 x,yx, y 的内积为：

⟨x,y⟩=∑i=1dxiyi\langle x, y \rangle = \sum_{i=1}^d x_i y_i

由于：

  • xi,yix_i, y_i 相互独立
  • E[xiyi]=0E[x_i y_i] = 0
  • Var(xiyi)=1\text{Var}(x_i y_i) = 1

因此：

⟨x,y⟩∼N(0,d)\langle x, y \rangle \sim \mathcal{N}(0, d)

其量级为 O(d)O(\sqrt{d})。

代回距离方程，可得：

∣∣x−y∣∣2=d+d−2⋅O(d)=2d+O(d)∣∣x−y∣∣2≈2d||x - y||^2 = d + d - 2 \cdot O(\sqrt{d}) = 2d + O(\sqrt{d}) \\ ||x - y||^2 \approx 2d

于是：

∣∣x−y∣∣≈2d||x - y|| \approx \sqrt{2d}

再看相对波动：

  • 均值：2d2d
  • 标准差：O(d)O(\sqrt{d})

因此：

标准差均值∼dd=1d→0\frac{\text{标准差}}{\text{均值}} \sim \frac{\sqrt{d}}{d} = \frac{1}{\sqrt{d}} \to 0

结论：距离的相对波动趋于 0，也就是说，所有点之间的距离几乎相同。

角度距离

如果将向量在 ℓ2\ell_2 归一化后投影到单位超球面上：

∣∣x∣∣=∣∣y∣∣=1||x|| = ||y|| = 1

那么：

∣∣x−y∣∣2=2−2cos⁡θ||x - y||^2 = 2 - 2\cos\theta

在高维情形下：

cos⁡θ≈0\cos\theta \approx 0

因此：

∣∣x−y∣∣≈2||x - y|| \approx \sqrt{2}

所有向量之间的角度距离几乎等距。

在高维空间中，根据大数定律，随机向量的范数集中在一个常数附近。此外，独立向量之间的内积只以 O(d)O(\sqrt{d}) 的量级增长，与范数平方的 O(d)O(d) 量级相比可以忽略不计。其结果是，两两距离集中在一个常数附近，从而出现几乎所有点都近似等距的现象。

正曲率黎曼空间

在欧氏空间中，维数灾难源于体积的多项式增长以及坐标的独立结构。然而，在正曲率黎曼流形中，几何本身从根本上重塑了体积分布与距离行为。

一个典型的例子是 dd 维单位球面：

Sd−1=x∈Rd:∣∣x∣∣=1\mathbb{S}^{d-1} = { x \in \mathbb{R}^d : ||x|| = 1 }

它是一个具有常正截面曲率的空间。

球面上的测度集中

与欧氏空间中体积沿径向扩散不同，在球面上所有点都位于固定半径的流形上。因此，「径向壳层」被测地带来取代。

设固定一点 x0∈Sd−1x_0 \in \mathbb{S}^{d-1}，并定义测地球：

B(θ)=x∈Sd−1:∠(x,x0)≤θB(\theta) = { x \in \mathbb{S}^{d-1} : \angle(x, x_0) \leq \theta }

该区域的测度依赖于 sin⁡d−2(θ)\sin^{d-2}(\theta)：

Vol(B(θ))∝∫0θsin⁡d−2(ϕ),dϕ\mathrm{Vol}(B(\theta)) \propto \int_0^\theta \sin^{d-2}(\phi), d\phi

现在观察关键现象：

  • 当 dd 较小时，sin⁡d−2(θ)\sin^{d-2}(\theta) 相对平坦
  • 当 d→∞d \to \infty 时，sin⁡d−2(θ)\sin^{d-2}(\theta) 在以下位置出现尖锐的峰： θ=π2\theta = \frac{\pi}{2}

这导致：大部分质量集中在与任意固定方向正交的赤道附近。

更正式地说，对任意固定的 ϵ>0\epsilon > 0：

P(∣∠(x,x0)−π2∣≤ϵ)→1当 d→∞\mathbb{P}\left( \left| \angle(x, x_0) - \frac{\pi}{2} \right| \leq \epsilon \right) \to 1 \quad \text{当 } d \to \infty

这是正曲率空间上测度集中现象的一种体现。

这种几何解释可以描述为「赤道坍缩」。在欧氏空间中，样本集中在薄外壳中；而在球面上，样本则集中在赤道附近的细环带中。

这可以看作是曲率引起的测度再分布。

正曲率下的角度距离

设：

x,y∼Uniform(Sd−1)x, y \sim \text{Uniform}(\mathbb{S}^{d-1})

则它们的内积满足：

⟨x,y⟩∼N(0,1d)\langle x, y \rangle \sim \mathcal{N}\left(0, \frac{1}{d}\right)

因此：

cos⁡θ=⟨x,y⟩≈0⇒θ≈π2\cos\theta = \langle x, y \rangle \approx 0 \quad \Rightarrow \quad \theta \approx \frac{\pi}{2}

于是我们得出结论：

高维球面上的两个随机点几乎总是正交的。

这意味着：

d测地(x,y)=arccos⁡(⟨x,y⟩)≈π2d_{\text{测地}}(x, y) = \arccos(\langle x, y \rangle) \approx \frac{\pi}{2}

测地度量下的距离集中

与欧氏距离不同，Sd−1\mathbb{S}^{d-1} 上的自然度量是测地距离：

dS(x,y)=arccos⁡(⟨x,y⟩)d_{\mathbb{S}}(x, y) = \arccos(\langle x, y \rangle)

由于：

  • ⟨x,y⟩→0\langle x, y \rangle \to 0
  • 波动为 O(1/d)O(1/\sqrt{d})

我们有：

Var(dS(x,y))→0\text{Var}(d_{\mathbb{S}}(x, y)) \to 0

因此，测地距离同样会集中，即几乎所有点对之间的距离都等于 π2\frac{\pi}{2}。

曲率放大集中

一个重要的洞见是：正曲率并不会消除维数灾难，而是重塑它，并且常常强化它。

为什么？

  • 球面是紧致的，不存在径向扩散
  • 曲率迫使测地线「折返」
  • 体积增长比欧氏空间更慢

结果是：样本集中得更加紧密，角度判别变得更加困难，并且大多数方向变得难以区分。

在正曲率空间中：测度集中在赤道区域，角度集中在 π2\frac{\pi}{2} 附近，测地距离几乎变为常数。维数灾难依然存在，但它以角度坍缩的形式表现，而非径向壳层集中。