了解如何结合两个基本的相似性搜索索引以发挥两者的优势
介绍
在数据科学中，相似性搜索经常出现在 NLP 领域、搜索引擎或推荐系统中，其中需要检索最相关的文档或项目以进行查询。有多种不同的方法可以提高海量数据的搜索性能。
在本系列的前两部分中，我们讨论了信息检索中的两种基本算法：倒排文件索引和乘积量化。它们都优化了搜索性能，但侧重于不同的方面：第一个加速了搜索速度，而后者将向量压缩为更小的、节省内存的表示形式。
由于两种算法侧重于不同的方面，自然出现的问题是是否可以将这两种算法合并为一种新算法
在本文中，我们将结合这两种方法的优点来产生快速且内存高效的算法。作为参考，大多数讨论的想法都将基于本文。
在深入研究细节之前，有必要了解残差向量(residual vectors)是什么，并对它们的有用属性有一个简单的直觉。稍后我们将在设计算法时使用它们。
残差向量(Residual vectors)
想象一下执行了一个聚类算法并产生了多个聚类。每个簇都有一个质心和与其关联的点。残差residual是点(向量)与其质心的偏移量。基本上，要找到特定向量的残差，必须从向量的质心中减去该向量。
如果聚类是通过 k-means 算法构建的，则聚类质心是属于该聚类的所有点的平均值。因此，从任意点找到残差相当于从中减去簇的平均值。通过从属于特定簇的所有点中减去平均值，这些点将以 0 为中心。
原始点簇显示在左侧。然后从所有聚类点中减去聚类质心。生成的残差向量显示在右侧。
我们可以观察到一个有用的事实：
用残差替换原始向量不会改变它们之间的相对位置。
也就是说，向量之间的距离始终保持不变。让我们简单地看一下下面的两个方程。
减去平均值不会改变相对距离
第一个方程是一对向量之间的欧氏距离公式。在第二个方程中，从两个向量中减去簇平均值。我们可以看到均值项简单地被抵消了——整个表达式变得与第一个方程中的欧几里得距离相同！
我们通过使用 L2 度量（欧氏距离）公式证明了这一说法。重要的是要记住，此规则可能不适用于其他度量方法。
因此，如果对于给定的查询，目标是找到最近的邻居，则可以仅从查询中减去簇均值，然后继续在残差中进行正常的搜索过程。
从查询中减去平均值不会改变其与其他向量的相对位置
现在让我们看一下下图中的另一个示例，其中有两个簇，其中每个簇向量的残差是单独计算的。
从簇的每个向量中减去相应质心的平均值将使所有数据集向量以 0 为中心。
这是一个有用的观察结果，将来会用到。此外，对于给定的查询，我们可以计算所有集群的查询残差。查询残差允许我们计算到簇的原始残差的距离。
从每个簇中减去平均值后，所有点都以 0 为中心。查询和查询残差与相应簇的其他点的相对位置不会改变。
训练(Training)
考虑到上一节中有用的观察结果后，我们可以开始设计算法。
给定一个向量数据库，构建一个倒排文件索引，将向量集划分为n个Voronoi 分区，从而减少推理查询过程中的搜索范围。
在每个 Voronoi 分区内，从每个向量中减去质心的坐标。结果，来自所有分区的向量变得彼此更接近并且以 0 为中心。此时，不需要原始向量，因为我们存储它们的残差。
之后，对来自所有分区的向量运行乘积量化算法。
重要的方面：乘积量化不是针对每个分区单独执行的——这会降低效率，因为分区的数量通常很高，这可能会导致需要大量内存来存储所有代码本。相反，该算法是同时对所有分区的所有残差执行的。
实际上，现在每个子空间都包含来自不同 Voronoi 分区的子向量。然后，对于每个子空间，像往常一样执行聚类算法并构建k个聚类及其质心。
训练流程
用向量的残差替换向量的重要性是什么？如果向量不被它们的残差替换，那么每个子空间将包含更多不同的子向量（因为子空间将存储来自不同的非相交 Voronoi 分区的子向量，这些分区在空间中可能彼此相距很远）。现在，来自不同分区的向量（残差）相互重叠。由于现在每个子空间的多样性较少，因此有效表示向量所需的再现值较少。换句话说：
在与之前使用的相同长度的PQ码的情况下，向量可以更准确地表示，因为它们具有较小的方差。
推理查询(Inference)
对于给定的查询，找到 Voronoi 分区的k个最近的质心。这些区域内的所有点都被视为候选点。由于原始向量最初被每个 Voronoi 区域中的残差替换，因此还需要计算查询向量的残差。在这种情况下，需要为每个 Voronoi 分区单独计算查询残差（因为每个区域具有不同的质心）。只有所选 Voronoi 分区的残差才会分配给候选者。
然后将查询残差分割成子向量。与原始乘积量化算法一样，对于每个子空间，计算包含从子空间质心到查询子向量的距离的距离矩阵d。 必须记住，每个 Voronoi 分区的查询残差都是不同的。基本上，这意味着需要为每个查询残差单独计算距离矩阵d。这是所需优化的计算成本。
最后，像之前在乘积量化算法中所做的那样，对部分距离进行求和。
排序结果(Sorting results)
计算完所有距离后，需要选择k个最近邻。为了有效地做到这一点，作者建议维护MaxHeap (注：容量为k 的大顶堆用于查最小最近的k个值，小顶堆则相反)数据结构。它的容量有限为k，并且在每一步中，它存储k个当前最小距离。每当计算新距离时，仅当计算值小于 MaxHeap 中的最大值时，才会将其值添加到 MaxHeap 中。计算完所有距离后，查询的答案已存储在 MaxHeap 中。使用 MaxHeap 的优点是其快速构建时间为线性时间O(n) 。（注：高度 h=logn；2^h -h -1 = n - logn -1 => O(n)）
推理查询过程
性能(Performance)
该算法利用了倒排文件索引和乘积量化的优点。根据推理查询过程中 Voronoi 分区探测的数量，需要计算相同数量的子向量到质心矩阵d并将其存储在内存中。这可能看起来像是一个缺点，但与整体优势相比，这是一个相当不错的权衡。
该算法继承了倒排文件索引良好的搜索速度和乘积量化的压缩效率
FAISS实现
根据Faiss 文档中的信息，我们将看到如何将倒排文件和产品量化索引组合在一起形成新的索引。
Faiss 在IndexIVFPQ类中实现所描述的算法，该类接受以下参数：
- quantizer：指定如何计算向量之间的距离。
- d：数据维度。
- nlist：Voronoi 分区的数量。
- M：子空间的数量。
- nbits：编码单个簇 ID 所需的位数。这意味着单个子空间中的总簇数将等于k = 2^nbits。
此外，还可以调整nprobe属性，该属性指定在推理查询期间必须使用多少个 Voronoi 分区来搜索候选者。更改此参数不需要重新训练。
IndexIVFPQ 的 Faiss 实现
存储单个向量所需的内存与原始乘积量化方法相同，只是现在我们添加了 8 个字节来存储有关倒排文件索引中向量的信息。
结论
利用前面文章部分的知识，我们已经完成了最先进的算法的实现，该算法实现了高内存压缩和加速的搜索速度。该算法广泛应用于处理海量数据的信息检索系统中。
Reference
- paper: Product quantization for nearest neighbour search
- Faiss document
- Faiss repository
- Faiss wiki Summary of Faiss indexes
除非另有说明，所有图片均由作者提供。
附操作学习笔记: