高斯随机投影：一种低调的向量降维技术
在做广告关键词匹配时，遇到一个经典问题：query 和广告词的匹配空间维度极高（几十万维的 bag-of-words），直接算余弦相似度太慢。
当时研究了一阵 Johnsson-Lindenstrauss 引理及其工程实现，写下了这篇。
JL 引理说了什么？
一句话：高维空间中的 N 个点，可以投影到 O(log N) 维空间，同时几乎不改变任意两点之间的欧氏距离。
具体来说：
对于任意 ε ∈ (0,1) 和任意 N 个点，存在一个映射 f: Rᵈ → Rᵏ，其中 k = O(log N / ε²)，使得对所有点对 (u,v)：
(1-ε)||u-v||² ≤ ||f(u)-f(v)||² ≤ (1+ε)||u-v||²
这就是“维数灾难”的一个乐观面：维度可以被大幅压缩而不损失信息。
高斯随机投影
最简单的实现：生成一个随机矩阵 R ∈ Rᵏˣᵈ，每个元素 ~ N(0, 1/k)，然后：
投影向量 = R × 原始向量为什么用高斯分布？因为高斯随机向量在任意方向上的投影方差是一致的（旋转不变性），保证了点对距离的期望不变。
一个直观理解：高维空间中，随机两个向量几乎总是正交的。随机投影本质上是在做一个“随机旋转”，然后只保留前 k 个坐标。
在广告匹配中的应用
原始空间：几十万维的 term 频率向量，稀疏度 > 99.9%
- 用高斯随机矩阵投影到 100-500 维
- 在低维空间做向量检索（L2 或 cosine）
- 找回 Top-K 候选，再在原空间做精确打分
关键优化：
- 稀疏向量 × 稠密矩阵 → 只需遍历非零元素
- 矩阵不需要真的存储，用哈希种子在线生成
局限
- 投影矩阵本身不学习数据分布（相比 PCA 或 SVD）
- 对 cosine 距离的保距性不如 L2（需要先 L2 归一化）
- 现代 Embedding 方法（DNN 训练）通常效果更好
但在 2016 年的广告系统里，这是一个不需要训练、计算量可控的实用方案。
这也是我在百度获得的第一个专利方向。