更高效的近似最近邻搜索

许多机器学习应用涉及最近邻搜索：数据被表示为高维空间中的点，查询（如图片或文本字符串）被嵌入该空间，检索与查询最接近的数据点作为候选解决方案。然而，计算查询与数据集中每个点的距离通常耗时过高，因此模型构建者采用近似最近邻搜索技术。其中最流行的是基于图的近似方法，将数据点组织成图结构，搜索算法遍历图并持续更新当前遇到的最近邻点列表。

在今年的网络会议上发表的论文中，提出了一种新技术显著提升图基最近邻搜索效率。该技术基于以下观察：当计算查询与当前候选列表中所有点更远的点之间的距离时，近似距离测量通常足够。因此，提出一种高效计算近似距离的方法，可将近似最近邻搜索时间减少20%至60%。

基于图的搜索

近似k最近邻搜索算法（寻找查询向量最近的k个邻居）大致分为三类：量化方法、空间分区方法和基于图的方法。在多个基准数据集上，基于图的方法目前表现最佳。

给定查询q的嵌入，基于图的搜索选择图中一点c并探索其所有邻居（即共享边的节点）。算法计算这些节点与查询的距离，并将最接近的节点加入候选列表。然后从候选节点中选择最接近查询的节点探索其邻居，必要时更新列表。此过程持续进行，直到未探索图节点与查询向量的距离开始增加——表明算法正在离开真实最近邻的邻域。

以往基于图近似的研究集中于底层图的构建方法。例如，有些方法在给定节点与远端节点间添加连接以防止搜索陷入局部最小值；有些方法专注于修剪高度连接的节点以避免重复访问同一节点。每种方法各有优势，但没有一种在所有情况下明显胜出。

本文专注于一种适用于所有图构建方法的技术，因为它提高了搜索过程本身的效率。该技术称为FINGER（图基近似最近邻搜索的快速推理）。

近似距离计算

考虑查询向量q、正在探索邻居的节点c，以及c的邻居d（需要计算其与q的距离）。q和d都可以表示为沿c的投影和与c垂直的"残差向量"之和。这本质上是将c视为空间的基向量。

如果算法正在探索c的邻居，意味着已计算c与q的距离。在论文中证明，利用该现有计算以及节点向量值的某些操作（可预计算并存储），估计q与d之间的距离简化为估计其残差向量之间的夹角。

该夹角可以合理近似为c的直接邻居（图中与c共享边的节点）残差向量之间的夹角。思路是：如果q足够接近c使得c值得探索，那么如果q是图的一部分，它可能是c的最近邻之一。因此，c其他邻居的残差向量之间的关系揭示了其中一个邻居d的残差向量与q的残差向量之间的关系。

性能评估

通过将FINGER与三种先前的图基近似方法在三个不同数据集上进行比较来评估方法。在不同recall10@10率（模型在10个顶级候选中找到查询真实最近邻的比率）范围内，FINGER比所有前代方法搜索更高效。有时差异非常显著——在一个数据集上98%高召回率时达50%，在另一个数据集86%召回率时近88%。

相关研究内容

• 产品检索的更高效缓存：局部敏感哈希使缓存容纳超过三倍查询结果
• 使用双曲面改进产品检索：双曲面嵌入方法比向量嵌入方法提升达33%
• 分布式数据更高效可靠检索：“随时查询"方法适应可用资源

本文涉及技术：图算法优化、近似计算、高维空间搜索、机器学习推理加速