维亚切斯拉夫-叶菲莫夫

8 分钟阅读

5 月 19 日

相似性搜索是一个给定查询的问题，目标是在所有数据库文档中找到与之最相似的文档。

导言

在数据科学中，相似性搜索经常出现在 NLP 领域、搜索引擎或推荐系统中，在这些领域中，需要为查询检索最相关的文档或项目。在海量数据中，提高搜索性能的方法多种多样。

在本系列的前两部分中，我们讨论了信息检索中的两种基本算法：倒排文件索引和乘积量化。这两种算法都能优化搜索性能，但侧重点不同：前者能加快搜索速度，后者则能将向量压缩到更小、内存效率更高的表示形式。

由于这两种算法的侧重点不同，自然而然就会产生这样的问题：是否有可能将这两种算法合并为一种新算法？

在本文中，我们将结合这两种方法的优点，开发出一种快速、内存效率高的算法。为便于了解，本文中讨论的大部分观点都将以本文为基础。 论文.

在深入了解细节之前，有必要先了解一下什么是残差向量，并对其有用的属性有一个简单的直观认识。我们稍后将在设计算法时使用它们。

残差向量

假设执行了一个聚类算法，并产生了几个聚类。每个聚类都有一个中心点和与之相关的点。残差是一个点（向量）与其中心点的偏移量。基本上，要找到特定向量的残差，必须从其中心点减去该向量。

如果聚类是通过 k-means 算法建立的，那么聚类中心点就是属于该聚类的所有点的平均值。因此，从任意点找出一个残差，就相当于从中减去一个聚类的平均值。通过减去属于某一聚类的所有点的平均值，这些点的中心点就会变为 0。

左侧显示的是原始点群。然后从所有聚类点中减去聚类中心点。右侧显示的是得到的残差向量。

我们可以看到一个有用的事实：

用残差代替原始向量并不会改变它们之间的相对位置。

也就是说，向量之间的距离始终保持不变。让我们简单看看下面的两个等式。

减去平均值不会改变相对距离

第一个等式是一对向量之间的欧氏距离公式。在第二个等式中，两个向量都减去了集群平均值。我们可以看到，平均值项被简单地抵消了--整个表达式变得与第一个等式中的欧氏距离相同！

我们使用 L2 度量（欧氏距离）的公式证明了这一说法。需要注意的是，这一规则可能不适用于其他度量。

因此，如果给定查询的目标是找到最近的邻居，那么只需从查询中减去集群平均值，然后在残差中进行正常搜索即可。

从查询中减去平均值不会改变其与其他向量的相对位置

现在让我们来看下图中的另一个例子，图中有两个聚类，每个聚类的向量残差都是单独计算的。

从聚类的每个向量中减去相应中心点的平均值，就会将所有数据集向量的中心集中在 0 附近。

这是一个有用的观察结果，将在今后使用。此外，对于给定的查询，我们可以计算查询残差到所有聚类的距离。通过查询残差，我们可以计算出与聚类原始残差的距离。

在减去每个簇的平均值后，所有点的中心都变为 0。查询和查询残差与相应簇中其他点的相对位置没有变化。

训练

考虑到上一节中的有用观察结果，我们就可以开始设计算法了。

给定一个向量数据库，构建一个反转文件索引，将向量集分为 n 个沃罗诺伊分区，从而缩小推理过程中的搜索范围。

在每个 Voronoi 分区内，我们会从每个向量中减去中心点的坐标。因此，所有分区中的矢量会变得更加接近，并以 0 为中心。此时，我们不再需要原始矢量，而是存储它们的残差。

然后，在所有分区的向量上运行乘积量化算法。

重要的一点是：不对每个分区单独执行乘积量化--这样做效率很低，因为分区的数量通常会很高，这将导致需要大量内存来存储所有的编码本。相反，该算法会同时对所有分区的所有残差执行。

实际上，现在每个子空间都包含来自不同 Voronoi 分区的子向量。然后，像往常一样，对每个子空间执行聚类算法，并建立 k 个簇及其中心点。

训练过程

用残差替换向量的重要性何在？如果不将向量替换为残差，那么每个子空间将包含更多不同的子向量（因为子空间将存储来自不同不相交的 Voronoi 分区的子向量，这些分区在空间上可能相距很远）。现在，来自不同分区的向量（残差）相互重叠。由于现在每个子空间的种类较少，因此有效表示向量所需的再现值也较少。换句话说

在使用相同长度的 PQ 编码时，由于向量的方差较小，因此可以更准确地表示向量。

推理

对于给定的查询，我们会找到离查询最近的 k 个 Voronoi 分区中心点。这些区域内的所有点都被视为候选点。由于原始矢量最初是由每个 Voronoi 区域中的残差代替的，因此还需要计算查询矢量的残差。在这种情况下，查询残差需要针对每个 Voronoi 分区分别计算（因为每个区域的中心点不同）。只有被选中的 Voronoi 分区的残差才会进入候选。

然后将查询残差分割成子向量。与最初的乘积量化算法一样，对于每个子空间，都要计算包含从子空间中心点到查询子向量之间距离的距离矩阵 d。必须牢记的是，每个 Voronoi 分区的查询残差都是不同的。这基本上意味着需要为每个查询残差分别计算距离矩阵 d。这就是所需的优化计算代价。

最后，对部分距离进行求和，就像之前在乘积量化算法中所做的那样。

结果排序

计算出所有距离后，需要选出 k 个最近的邻居。为了高效地完成这项工作，作者建议维护一个 最大堆数据结构。它的容量有限，为 k，每一步都会存储 k 个当前最小的距离。每当计算出一个新的距离时，只有当计算值小于 MaxHeap 中的最大值时，才会将其值添加到 MaxHeap 中。计算完所有距离后，查询的答案就已存储在 MaxHeap 中。使用 MaxHeap 的优势在于其快速的构建时间（O(n)）。

推理过程

性能

该算法同时利用了反转文件索引和乘积量化的优势。根据推理过程中探测到的 Voronoi 分区数量，需要计算并在内存中存储相同数量的子向量到中心点矩阵 d。这看起来可能是个缺点，但与整体优势相比，这是个很好的权衡。

该算法继承了倒置文件索引的良好搜索速度和乘积量化的压缩效率

Faais 的实现

Faiss(Facebook 人工智能搜索相似性）是一个用 C++ 编写的 Python 库，用于优化相似性搜索。该库提供不同类型的索引，这些索引是用于高效存储数据和执行查询的数据结构。

根据 文件中的信息，我们将看到如何将反转文件和乘积量化索引结合在一起，形成一个新的索引。

Faiss 在 IndexIVFPQ 类中实现了所述算法，该类接受以下参数：

量化器：指定如何计算向量之间的距离。d：数据维度。nlist：沃罗诺伊分区数。M：子空间数。nbits：对单个集群 ID 进行编码所需的比特数。这意味着单个子空间中的群集总数将等于 k = 2^nbits。

此外，还可以调整 nprobe 属性，该属性规定了在推理过程中必须使用多少个 Voronoi 分区来搜索候选对象。更改该参数无需重新训练。

Faiss 实现 IndexIVFPQ

存储单个矢量所需的内存与原始乘积量化方法相同，只是现在我们增加了 8 个字节，用于存储反转文件索引中的矢量信息。

结论

利用前几篇文章中的知识，我们逐步实现了一种最先进的算法，该算法可实现高内存压缩和加速搜索速度。该算法广泛应用于处理海量数据的信息检索系统中。