Probabilistic Kernel Function for Fast Angle Testing

本文提出了一种无需渐近假设的确定性投影概率核函数，用于高效的角度测试与相似度搜索，其实验结果表明该方法在近似最近邻搜索任务中的查询吞吐量比主流 HNSW 算法高出 2.5 至 3 倍。

要点

这篇论文主要解决了一个在人工智能和数据科学中非常头疼的问题：如何在海量的数据中，快速找到和“目标”最相似的东西？

想象一下，你有一个巨大的图书馆，里面有几百万本书（数据），每本书都有一个独特的“气味”（向量）。现在，你手里有一本新书（查询向量），你想在几秒钟内找到几本气味最像的书。

传统的做法是拿着新书去闻每一本书，但这太慢了。于是，科学家们发明了一些“快速筛选法”，比如随机投影。

1. 核心问题：现有的“快速筛选法”有什么毛病？

现有的方法（比如论文中提到的 CEOs 或 HNSW+PEOs）就像是一个**“盲猜”游戏**：

• 做法：它们会随机扔出很多根“探测针”（投影向量），看看哪根针离你的目标最近，然后据此猜测哪本书最像。
• 缺点：这些“探测针”是随机乱丢的（通常服从高斯分布，就像撒面粉一样）。
  • 理论缺陷：它们依赖一个假设：“只要我扔的针足够多（无穷多），猜得就准。”但在实际电脑里，我们不可能扔无穷多的针，只能扔有限的几根。
  • 结果：因为针是乱丢的，有时候会离目标很远，导致判断失误，或者为了猜准一点，不得不扔更多的针，反而变慢了。

2. 这篇论文的解决方案：从“盲猜”变成“有备而来”

作者提出了两个新的“概率核函数”（你可以理解为更聪明的筛选规则），核心思想是：不要随机乱丢针，要精心布置针的位置。

类比：寻找失散的朋友

• 旧方法（随机高斯分布）：就像你在一个巨大的广场上，闭着眼睛随机朝各个方向扔飞镖。你想通过飞镖落点来判断朋友在哪。如果飞镖扔得不够多，你可能永远猜不准。
• 新方法（参考角 + 确定性结构）：
  1. 参考角（Reference Angle）：作者发现，判断准不准的关键，不在于扔了多少飞镖，而在于离目标最近的那根飞镖，离目标有多近。这根“最近的飞镖”和目标的夹角越小，判断就越准。
  2. 精心布置（确定性结构）：作者不再随机扔飞镖，而是设计了一种特殊的排列方式（比如像正多面体的顶点，或者对称的点对），确保无论目标在哪里，总有一根飞镖离它非常近。
  3. 随机旋转：为了不让这种排列被敌人（特定的数据分布）看穿，他们在扔飞镖前，会随机旋转一下整个场地。这样既保持了“针离目标很近”的优势，又保留了随机性的安全。

3. 两个具体的“超能力”

这篇论文提出了两种具体的工具，分别解决两个问题：

• 工具一（KS1）：比大小

  • 场景：你有两个候选人 A 和 B，想知道谁更像目标？
  • 作用：KS1 能极快地告诉你"A 比 B 更像”，而且准确率比旧方法（CEOs）略高一点点。
  • 比喻：就像以前是用尺子量距离（慢），现在是用一种特制的“感觉棒”，轻轻一点就知道谁更近。

• 工具二（KS2）：定门槛

  • 场景：你只想要相似度超过 80% 的人，低于 80% 的直接扔掉。
  • 作用：KS2 能极快地判断一个人是否“达标”。如果没达标，直接跳过，不用算精确距离。
  • 比喻：以前过安检，每个人都要把包打开仔细检查（算精确距离）。现在 KS2 像是一个智能金属探测门，如果它觉得你身上没带危险品（相似度不够），直接让你走人，不用开包检查。这大大节省了时间。

4. 实际效果有多牛？

作者把这套新方法装进了目前最流行的搜索算法 HNSW（可以理解为目前最厉害的“图书馆导航系统”）里，变成了 HNSW+KS2。

• 速度提升：在保持搜索准确度几乎不变的情况下，查询速度（每秒能处理多少个请求）提升了 2.5 到 3 倍！
  • 比喻：以前找书要 1 分钟，现在只要 20 秒。
• 更省空间：因为不需要存那么多乱七八糟的随机数据，索引文件的大小还减少了 5%。
• 超越对手：比目前最先进的其他方法（如 HNSW+PEOs）还要快 10% 到 30%。

5. 总结

简单来说，这篇论文做了一件很聪明的事：
它发现以前大家为了快速找相似数据，是在**“乱撒网”。作者改进了渔网的设计，让网眼排列得更科学、更均匀**，并且加了一个**“旋转开关”**。

这样，无论鱼（数据）在哪里，都能被网得更准、更快。这使得我们在处理海量数据（比如给 AI 找素材、推荐电影、人脸识别）时，速度能快好几倍，而且不用花更多的钱买服务器。

一句话总结：把“随机乱猜”变成了“精心布局”，让大数据搜索变得既快又准。

技术摘要

这是一篇关于高维欧几里得空间中角度测试（Angle Testing）问题的学术论文，主要提出了两种基于投影的概率核函数，用于加速相似性搜索。以下是该论文的详细技术总结：

1. 研究背景与问题定义

在高维向量相似性搜索中，计算两个向量夹角的余弦值（即内积）通常耗时 $O(d)$，这在大规模数据和高维场景下成本高昂。因此，研究重点转向角度测试，即在不计算精确角度值的情况下，快速判断：

1. 角度比较（Problem 1.1）：给定查询向量 $q$ 和数据向量 $v_1, v_2$，判断 $\langle q, v_1 \rangle > \langle q, v_2 \rangle$ 是否成立。
2. 角度阈值判定（Problem 1.2）：给定阈值 $\theta$，判断向量 $v$ 与 $q$ 的夹角是否小于 $\theta$（即 $\langle q, v \rangle > \cos \theta$）。

现有方法的局限性：
现有的主流方法（如基于 CEOs 的随机投影技术、Falconn 等）通常依赖从高斯分布中随机抽取投影向量，并利用**极值顺序统计量（Extreme Order Statistics）**的渐近性质（即假设投影向量数量 $m \to \infty$）来建立角度与投影值的关系。

• 理论缺陷：这种关系依赖于 $m$ 趋于无穷大的假设，而在实际应用中 $m$ 是有限的，导致理论保证不足。
• 效率瓶颈：高斯分布生成的投影向量结构不够优化，导致估计精度受限。

2. 核心方法论

作者提出了一种新的视角，不再依赖高斯分布的渐近假设，而是利用参考角（Reference Angle）和确定性结构来设计概率核函数。

2.1 核心观察

1. 高斯分布非必需：决定估计精度的关键因素不是投影向量的分布（如高斯分布），而是参考角（即查询向量 $q$ 与其在投影集合 $S$ 中最近邻向量的夹角）。
2. 确定性关系：通过引入随机旋转矩阵 $H$，参考角变得可预测。作者建立了角度与投影值之间的确定性概率关系，无需 $m \to \infty$ 的假设。

2.2 提出的概率核函数

作者定义了两个核函数 $K^1_S$ 和 $K^2_S$，分别对应上述两个问题：

• $K^1_S(q, v)$：用于角度比较。定义为 $v$ 与 $q$ 在随机旋转后的投影集合 $H_S$ 中的参考向量的内积。
• $K^2_S(q, v)$：用于角度阈值判定。引入了归一化项，利用参考角信息 $A_S(v)$ 来修正估计值，使其更准确地反映角度关系。

2.3 投影向量的配置结构

为了最小化参考角（从而提高精度），作者提出了两种优于纯随机投影的投影向量配置结构：

1. 对径投影（Antipodal Projections, $S_{sym}$）：利用成对的对径点（Antipodal pairs）构建投影集，利用对称性减少计算量并保证参考角为正。
2. 多重交叉多面体（Multiple Cross-polytopes, $S_{pol}$）：基于交叉多面体（Cross-polytope，即高维正八面体）的顶点构建。由于交叉多面体在覆盖球面上具有较小的覆盖半径，这种结构能提供更小的参考角。
   • 算法通过随机旋转多个交叉多面体并选择最佳配置，进一步优化了参考角。
   • 引入了多级结构（Level $L$），类似于乘积量化（Product Quantization），将空间划分为 $L$ 个子空间，进一步降低参考角并平衡索引大小与查询效率。

3. 主要贡献

1. 理论突破：提出了基于参考角的概率核函数，建立了不依赖渐近假设（$m \to \infty$）的精确概率关系（Eq. 4），证明了新核函数在有限 $m$ 下依然具有严格的概率保证。
2. 结构优化：发现高斯分布并非最优，提出了基于对径点和交叉多面体的投影向量配置算法（Alg. 1 & Alg. 2），显著减小了参考角，提升了估计精度。
3. 应用扩展：
   • KS1：基于 $K^1_S$ 改进了现有的 CEOs 技术，用于最大内积搜索（MIPS）和基于 LSH 的搜索。
   • KS2：基于 $K^2_S$ 提出了一种新的路由测试（Routing Test），用于加速基于图的近似最近邻搜索（ANNS）。
4. 性能提升：
   • 在 MIPS 任务中，KS1 比 CEOs 有轻微但一致的精度提升（最高 0.8%）。
   • 在 ANNS 任务中，结合 HNSW 的 HNSW+KS2 方法，在保持高召回率的同时，查询吞吐量（QPS）比原生 HNSW 提高了 2.5 倍至 3 倍，比之前的 SOTA 方法 HNSW+PEOs 提高了 10%-30%，且索引大小减少了约 5%。

4. 实验结果

• 数据集：在 Word, GloVe, SIFT, GIST, Tiny 等六个真实高维数据集上进行了测试。
• MIPS 性能：在 k-MIPS 任务中，使用 $S_{pol}$ 结构的 KS1 在召回率上 consistently 优于使用高斯分布的 CEOs。
• ANNS 性能：
  • QPS 提升：HNSW+KS2 在多个数据集上显著超越了 HNSW 和 HNSW+PEOs。例如在 SIFT 数据集上，QPS 提升显著。
  • 索引效率：由于 KS2 测试公式更简单且存储常数更少，其索引构建开销和存储大小优于 PEOs。
  • 参数敏感性：实验表明，参数 $L$（子空间数量）在 $d' \approx 16$ 时能达到最佳搜索性能与索引大小的平衡。

5. 意义与结论

这篇论文通过重新审视角度测试的底层数学原理，指出了现有基于高斯分布随机投影方法的理论局限性，并提出了一种确定性结构 + 参考角的新范式。

• 理论价值：消除了对 $m \to \infty$ 的依赖，为有限投影向量下的概率搜索提供了更坚实的理论基础。
• 实践价值：提出的 KS1 和 KS2 技术易于实现，且能直接集成到现有的主流搜索算法（如 HNSW）中，显著提升了大规模向量检索系统的速度和效率，为 RAG（检索增强生成）、推荐系统等应用提供了更高效的底层支持。

总结：该工作通过优化投影向量的几何结构（从随机高斯转向交叉多面体）并利用参考角理论，实现了比现有 SOTA 方法更快、更准的相似性搜索。