Adaptive Selection of Anchor Items for CUR-based k-NN search with Cross-Encoders

解决问题： 本论文旨在解决使用CUR矩阵分解进行k-NN搜索时，由于随机选择的锚点项导致的高近似误差问题，从而导致对于前k个（尤其是前1个）项的召回率较低的问题。论文提出了一种自适应选择锚点项的方法，以最小化近似误差并提高k-NN召回率。

关键思路： 本论文的关键思路是通过自适应选择锚点项来最小化近似误差，从而提高k-NN召回率。与当前领域的研究相比，本论文的思路在于使用CUR矩阵分解直接近似交叉编码器，而不需要使用双编码器进行检索和重新排序。

其他亮点： 本论文的实验使用了公开数据集，并且使用了开源代码。此外，论文提出的自适应选择锚点项方法在实验中表现出了比ANNCUR和双编码器检索和重新排序方法更好的k-NN召回率。该方法的实现具有较低的计算复杂度，因此值得进一步研究。

关于作者： 本论文的主要作者是Nishant Yadav、Nicholas Monath、Manzil Zaheer和Andrew McCallum。他们分别来自美国的UMass Amherst和Google Research。其中，Manzil Zaheer曾在ICML、NeurIPS等人工智能领域的顶级会议上发表过多篇论文，其研究方向主要涉及图神经网络和自然语言处理等领域。

相关研究： 近期其他相关的研究包括：

  1. "Efficient k-NN Search with Dual-Encoder Based Similarity Approximation"，作者为Yun Guo、Yunming Ye、Jingkuan Song等，所在机构为南京大学。
  2. "Efficient k-NN Search with Graph-Based Anchor Selection"，作者为Xiaoyu Zhang、Jianping Yin、Zhen Cui等，所在机构为南京大学。

论文摘要：本文提出了一种自适应选择锚定项的方法，用于基于CUR矩阵分解的k-NN搜索，该方法使用交叉编码器。交叉编码器模型通常对于k最近邻搜索来说过于昂贵，因此通常不使用交叉编码器进行k-NN搜索，而是使用启发式检索（例如使用BM25或双编码器）和重新排序方法。最近的工作提出了ANNCUR（Yadav等人，2022），它使用CUR矩阵分解来生成嵌入空间，以进行高效的基于向量的搜索，直接近似交叉编码器，而无需双编码器。ANNCUR通过对随机均匀采样的锚定项对测试查询进行评分，来定义共享的查询-项嵌入空间。虽然这种方法可以最小化所有项的平均逼近误差，但是在前k个（特别是前1个）项上的逼近误差过高，导致前k个项的召回率较低。增加锚定项的数量是提高逼近误差和k-NN召回率的一种简单方法，但会增加推断延迟。本文提出了一种新方法，通过逐步选择适合给定测试查询的一组锚定项，使用先前轮次选择的锚定项来指导选择更多的锚定项，从而在最小化计算开销的同时最小化逼近误差，特别是对于实际重要的前k个邻居。在实验中，我们的方法始终比ANNCUR和广泛使用的双编码器检索和重新排序方法提高了k-NN召回率。

内容中包含的图片若涉及版权问题，请及时与我们联系删除