↓
  1. 笔记/

高维几何与集中不等式详解

··
研究笔记 研究笔记 Math Theory

高维几何与集中不等式详解 #

一、高维几何：反直觉的世界 #

1.1 高维球体的"空心化" #

直觉（3维 vs 10000维）：

  • 3维球：体积均匀分布
  • 10000维球：99.999…% 的体积集中在表面薄层

数学解释：

$d$ 维单位球体积：

V_d(r) = π^(d/2) / Γ(d/2 + 1) · r^d

当 $d$ 很大时，$r = 1-ε$ 处的体积占比：

V_d(1-ε) / V_d(1) = (1-ε)^d ≈ e^(-εd)

例子：d=1000, ε=0.01（只剥离1%的外壳）

剩余体积 = (0.99)^1000 ≈ e^(-10) ≈ 0.000045
→ 99.995% 的体积在表面1%的薄层！

对 TurboQuant 的意义：

  • 高维向量几乎等长（集中在球面）
  • PolarQuant 利用这一点：半径相对稳定，角度包含主要信息

1.2 随机向量几乎正交 #

现象：

在 $d$ 维空间中随机取两个单位向量 $u, v$，当 $d \to \infty$：

<u, v> → 0

数学证明：

设 $u, v \sim N(0, I_d)$，归一化后：

<u/||u||, v/||v||> = (1/d)∑u_i v_i · d/(||u||||v||)

由大数定律：

  • $(1/d)∑ u_i v_i \to E[u_i v_i] = 0$
  • $||u||^2/d \to 1$

所以内积 ≈ 0，即夹角 ≈ 90°

模拟验证：

d=3:   随机向量夹角平均约 90°，方差大
d=100: 夹角集中在 90° ± 8°
d=10000: 夹角集中在 90° ± 0.8°

对 TurboQuant 的意义：

  • QJL 的 sign-random-projection 可行：随机方向足够"分散"
  • 高维空间中，少量投影即可区分不同向量

1.3 高斯分布的集中性 #

一维 vs 高维：

维度高斯分布特性
1D$P(
d-D$

具体计算：

对于 $X \sim N(0, I_d)$：

||X/√d||^2 = (1/d)∑X_i^2 → 1 (当 d→∞)

方差：

Var(||X||^2/d) = 2/d → 0

可视化理解：

  • 1D：钟形曲线，两边有尾巴
  • 100D：像一个"薄球壳"，半径几乎都是√100=10

二、集中不等式：概率的上界艺术 #

2.1 Markov 不等式（基础） #

定理：

对于非负随机变量 $X \geq 0$，$a > 0$：

P(X ≥ a) ≤ E[X]/a

直观：如果平均工资是5000，那么收入超过50000的人不超过10%

2.2 Chebyshev 不等式（方差控制） #

定理：

P(|X - E[X]| ≥ t) ≤ Var(X)/t^2

改进：利用方差信息，得到"偏离均值"的概率界

2.3 Hoeffding 不等式（核心武器） #

定理：

设 $X_1, ..., X_n$ 是独立有界随机变量，$X_i \in [a_i, b_i]$，令 $S_n = \sum X_i$：

P(|S_n - E[S_n]| ≥ t) ≤ 2exp(-2t^2 / ∑(b_i-a_i)^2)

特殊情况（同分布，$[0,1]$ 有界）：

P(|(1/n)∑X_i - μ| ≥ ε) ≤ 2e^(-2nε^2)

关键特性：

  • 指数衰减：误差概率随 $n$ 指数下降
  • 与分布无关：只要求有界，不要求正态分布

2.4 亚高斯分布（Sub-Gaussian） #

定义：

随机变量 $X$ 是亚高斯的，如果：

P(|X - E[X]| ≥ t) ≤ 2e^(-t^2/2σ^2)

例子：

  • 有界随机变量（Hoeffding）
  • 正态分布 $N(0, \sigma^2)$
  • Rademacher 变量（$\pm 1$ 等概率）

性质：

独立亚高斯变量的和仍是亚高斯，方差参数相加。

三、在 TurboQuant/JL 中的应用 #

3.1 Johnson-Lindenstrauss 引理证明骨架 #

目标：

证明随机投影 $f(x) = \frac{1}{\sqrt{k}}Rx$（$R_{ij} \sim N(0,1)$）保持距离

关键步骤：

  1. 固定向量 $x$，$||x||=1$，看第 $j$ 个投影分量：

    y_j = (1/√k)∑R_{ji}x_i ~ N(0, 1/k)

  2. $||f(x)||^2 = \sum y_j^2$ 是 $k$ 个独立 $\chi^2$ 变量之和

  3. 用集中不等式（亚指数/ $\chi^2$ 版本）：

    P(|||f(x)||^2 - 1| ≥ ε) ≤ 2e^(-ckε^2)

  4. Union Bound：对 $n \choose 2$ 对点同时成立，需要：

    k ≥ 4logn / (ε^2/2 - ε^3/3) = O(ε^(-2)log n)

3.2 QJL 的误差分析 #

问题：用 sign-random-projection 估计内积

设置：

  • 查询 $q$，键 $k$
  • 投影矩阵 $R \in R^{m \times d}$，元素 i.i.d. $N(0,1)$
  • 量化：$\hat{q} = \text{sign}(Rq)$，$\hat{k} = \text{sign}(Rk)$

估计量：

ṡ = (1/m)∑q̂_i · k̂_i

分析：

单个投影的期望：

E[sign(R_i q) · sign(R_i k)] = 1 - 2θ/π

其中 $θ = \arccos(\frac{}{||q||||k||})$ 是夹角

Hoeffding 应用：

$\hat{q}_i \cdot \hat{k}_i \in \{-1, +1\}$，有界！

P(|ṡ - E[ṡ]| ≥ t) ≤ 2e^(-mt^2/2)

所以 $m = O(ε^{-2}\log(1/\delta))$ 足以保证误差 $< ε$ 概率 $> 1-\delta$

3.3 PolarQuant 的几何基础 #

极坐标变换的数学：

x = (x_1, x_2, ..., x_d) → (r, θ_1, θ_2, ..., θ_{d-1})

递归结构（以 4D 为例）：

Level 0: (x1, x2) → (r12, θ12)
         (x3, x4) → (r34, θ34)
         
Level 1: (r12, r34) → (R, θ1234)

最终存储: R, θ12, θ34, θ1234

为何角度集中：

在高维空间中，随机向量的方向（角度）服从球面上的均匀分布。但经过 随机旋转 后（TurboQuant 第一步），数据变得各向同性，角度分布更加规则，易于量化。

误差控制：

每个角度量化引入的误差 $δθ$ 对最终内积的影响：

Δ ≈ r · sinθ · δθ

在高维中，$r$ 稳定（集中），通过精细分配比特给不同层级的角度，控制总误差。

四、可视化总结 #

低维 (d=2)                    高维 (d=1000)
    *                          *******
   /|\                        *       *
  / | \                      *   . .   *
 *--+--*                    *  .     .  *
  \ | /                      *  .     .  *
   \|/                        *   . .   *
    *                          *******
 体积均匀                    体积在表面
 角度分散                    角度稳定
 内积变化大                  内积≈0

集中不等式的作用：

高维 + 集中不等式 = 少量样本即可代表整体

这正是 QJL 只用 $m \ll d$ 个投影就能保持内积的数学保证！