嵌入向量搜索高效算法

Question

背景：I有一个机器学习模型，其中给定一个对象返回一个维数为d的嵌入向量，该模型通过训练使两个嵌入向量的语义相似性非常接近。现在，验证过程比较简单，我可以取两个向量的余弦相似度。对于识别来说，这有点复杂，要么我可以遍历所有的锚文档并比较余弦相似性，要么使用类似于kNN (在线)的方法。

问题：I有一个嵌入向量列表，每个向量有一个维数d，长度N。每个向量包含浮点数据。

什么将是一种有效的数据结构+算法，可以执行以下操作：

1. 可以有效地将具有唯一ID的新向量添加到列表中(<=对数复杂度)
2. 使用列表中的随机向量进行搜索，并检索顶部k向量，这样曼哈顿距离/ L1范数对于这些向量是最小的(希望是<=对数复杂度)。

示例：

[
 [1., 2., 3.],
 [5., 6., 8.],
 [-11., 2., 31.]
]

k = 2 query = [1.5, 2.5, 3.2] results:

[
 [1., 2., 3.],
 [5., 6., 8.],
]

Answer 1

我认为Faiss正是你要找的。如果您对实现细节(这是非常技术性的)感兴趣，请参阅这里，教程是这里。

Answer 2

随着神经网络在许多不同的软件产品中的加入，这个问题变得非常普遍，因此有许多算法可供使用。

要为您的问题选择合适的工具，将基于以下两个方面的权衡：

• speed：你希望阿尔戈/库有多快？
• recall：检索到的嵌入是否是最佳邻居。

对于不同的包，这种权衡很好地存在于http://ann-benchmarks.com/中，它基准了许多不同的近似最近邻算法搜索包。这是个很好的开始。

对于长期的可维护性观点，您也希望考虑社区(例如。git回购明星，最新推送，公关)，代码质量等。