↓跳到主要内容
  1. 技术笔记/

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

··1678 字 ·2 分钟

1000 维单位球,剥掉最外层 1% 的壳,剩下多少体积?答案小到可以忽略:几乎所有体积都贴着表面。这个反直觉的结论是理解高维几何的起点:随机向量的长度高度集中,方向几乎正交,内积接近 0。TurboQuant 这类量化方法能成立,靠的就是这些集中性质。

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

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

三维球的体积在半径上分布得比较均匀;到了 1000 维以上,几乎所有体积都贴着表面。把这个直觉写成公式:d 维单位球的体积随半径的 d 次方增长,

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

当 d 很大时,半径缩到 1-ε 处的体积占比是

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

这个比值只和 εd 有关,维度越高衰减越快。d=1000、ε=0.01 时,只剥掉外层 1% 的壳,剩余体积是

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

维度越高,这层壳越薄,所谓"球"在几何上更接近一层皮。对 TurboQuant 来说,这意味着高维向量几乎等长,长度集中在球面上;PolarQuant 利用的正是这一点:半径相对稳定,角度承载主要信息。

1.2 随机向量几乎正交 #

在 d 维空间里随机取两个单位向量 u、v,当 d→∞,内积趋于 0:

<u, v> → 0

设 u,v~N(0,I_d),归一化后内积是

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

由大数定律,(1/d)∑u_i v_i→E[u_i v_i]=0,||u||²/d→1,所以内积≈0,夹角≈90°。模拟结果也符合:d=3 时夹角方差很大;d=100 时集中在 90°±8°;d=10000 时集中在 90°±0.8°。

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

对 TurboQuant 的意义是,QJL 的 sign-random-projection 依赖随机方向足够分散;高维里少量投影就能把不同向量区分开。

1.3 高斯分布的集中性 #

一维高斯有厚尾,P(|X|>2σ)≈5%。到了 d 维,||X||²=∑X_i² 高度集中。对 X~N(0,I_d),

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

方差是

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

100 维时,半径几乎都落在 √100=10 附近,分布像一个薄球壳,不再是一维那条带尾巴的钟形曲线。

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

集中不等式干的事情,是给偏离均值的概率加上界。Markov 不等式只需要非负随机变量和期望:对 X≥0、a>0,

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

如果平均工资是 5000,收入超过 50000 的人不超过 10%。这个界很松,但不需要方差,也不需要分布形状。

Chebyshev 不等式把方差用上:

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

它给出的是偏离均值超过 t 的概率上界,比 Markov 更紧,但仍然只用了二阶矩。

Hoeffding 不等式是后面 JL 和 QJL 分析里的核心工具。设 X_1,…,X_n 独立且有界,X_i∈[a_i,b_i],S_n=∑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 指数衰减;只要求有界,不要求正态分布。

亚高斯分布把这套界抽象成一个定义:如果

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

就说 X 是亚高斯的。有界随机变量、正态分布、Rademacher 变量都是例子。独立亚高斯变量的和仍然是亚高斯,方差参数相加。

三、在 TurboQuant/JL 中的应用 #

3.1 Johnson-Lindenstrauss 引理证明骨架 #

JL 引理要证明的是,随机投影 f(x)=1/√k Rx(R_ij~N(0,1))在 k 足够大时保持距离。证明分四步,核心是固定一个向量看投影后的长度。

固定单位向量 x,第 j 个投影分量是

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

于是 ||f(x)||²=∑y_j² 是 k 个独立 χ² 变量之和。用亚指数/χ² 版本的集中不等式,偏差超过 ε 的概率满足

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

最后对所有 n 个点的 C(n,2) 对距离做 union bound,要求

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

这就是 JL 引理的样本复杂度:投影维度只需随 log n 增长,和原始维度 d 无关。

3.2 QJL 的误差分析 #

QJL(Quantized Johnson-Lindenstrauss)用 sign-random-projection 估计内积。查询 q、键 k,投影矩阵 R∈R^{m×d},元素 i.i.d. N(0,1);量化后 q̂=sign(Rq),k̂=sign(Rk);估计量是

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

单个投影的期望是

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

其中 θ=arccos(<q,k>/(||q||||k||)) 是夹角。因为 q̂_i·k̂_i∈{-1,+1} 有界,Hoeffding 直接给出

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

所以 m=O(ε^{-2}log(1/δ)) 足以保证误差小于 ε 的概率大于 1-δ。

3.3 PolarQuant 的几何基础 #

极坐标变换把 x=(x_1,…,x_d) 映射成 (r,θ_1,…,θ_{d-1}):

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

递归结构可以拿 4D 举例:先把 (x1,x2) 变成 (r12,θ12),(x3,x4) 变成 (r34,θ34),再把 (r12,r34) 变成 (R,θ1234),最终存 R、θ12、θ34、θ1234。

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

Level 1: (r12, r34) → (R, θ1234)

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

高维随机向量的方向在球面上均匀分布;TurboQuant 先做随机旋转,让数据各向同性,角度分布更规则,便于量化。每个角度量化引入的误差 δθ 对最终内积的影响约为

Δ ≈ r · sinθ · δθ

高维里 r 稳定,比特可以按层级分给不同角度,控制总误差。

四、这些性质的适用边界 #

这些性质放在一起,才是 QJL 和 PolarQuant 的数学基础:高维向量长度集中,方向近似正交,少量随机投影就能以高概率保住内积;角度量化则利用半径稳定、角度承载主要信息。它们都有前提。数据要经过随机旋转,各向同性才成立;投影维度 k 或 m 要满足上面的集中界,太小则误差界不成立;数据分布如果有强相关结构,随机投影的方差会变大,误差界要重新算。把它们当成"高维一定好"的结论,会在真实 embedding 上翻车。