相似度搜索，第二部分：产品量化
学习一种强大的技术，有效压缩大数据
相似性搜索是一个问题，其中给定一个查询，目标是在所有数据库文档中找到与之最相似的文档。
介绍
在数据科学中，相似性搜索经常出现在NLP领域、搜索引擎或推荐系统中，需要检索查询的最相关文档或项目。存在许多不同的方法来提高在大量数据中的搜索性能。
在本系列文章的第一部分中，我们看了kNN和倒排文件索引结构来执行相似性搜索。如我们所学，kNN是最直接的方法，而倒排文件索引在其上执行，建议速度加速和准确性之间的权衡。然而，这两种方法都没有使用数据压缩技术，可能会导致内存问题，特别是在大型数据集和有限的RAM情况下。在本文中，我们将通过查看另一种称为产品量化的方法来解决这个问题。
相似性搜索，第1部分：kNN和倒排文件索引
相似性搜索是一个流行的问题，其中给定一个查询Q，我们需要在所有文档中找到与之最相似的文档。
towardsdatascience.com
定义
产品量化是将每个数据集向量转换为短的存储器有效表示（称为PQ代码）的过程。而不是完全保留所有向量，它们的短表示被存储。同时，产品量化是一种有损压缩方法，可以导致较低的预测准确性，但在实践中，这种算法非常有效。
一般来说，量化是将无限的值映射到离散的值的过程。
训练
首先，该算法将每个向量分成若干相等的部分 – 子向量。所有数据集向量的各个部分形成独立的子空间，并分别进行处理。然后为每个向量子空间执行聚类算法。通过这样做，在每个子空间中创建了几个质心。每个子向量都被编码为它所属的质心的ID。此外，所有质心的坐标都被存储以供以后使用。
子空间质心也称为量化向量。
在产品量化中，簇ID通常称为再现值。
注意。在下面的图中，一个矩形表示包含多个值的向量，而一个正方形表示一个单独的数字。
因此，如果将原始向量分成n个部分，那么它可以通过n个数字进行编码 – 对于其每个子向量的相应质心的ID。通常，创建的质心数量k通常选择为2的幂，以实现更有效的内存使用。这样，存储编码向量所需的内存为n * log（k）位。
子空间内的所有质心的集合称为码本。为所有子空间运行n个聚类算法会产生n个单独的码本。
压缩示例
假设一个大小为1024的原始向量存储浮点数（32位），被分成n = 8个子向量，每个子向量由k = 256个簇之一进行编码。因此，编码单个簇的ID需要log（256）= 8位。让我们比较两种情况下向量表示的内存大小：
- 原始向量：1024 * 32位 = 4096字节。
- 编码向量：8 * 8位 = 8字节。
最终压缩了512倍！这就是产品量化的真正威力。
以下是一些重要说明：
- 该算法可以在一个向量子集上训练（例如创建簇），并用于另一个向量子集：一旦该算法经过训练，就会传递另一个向量数据集，其中新向量通过使用已构建的每个子空间的质心进行编码。
- 通常情况下，k-means被选为聚类算法。它的优点之一是聚类数k是可以手动定义的超参数，根据内存使用要求来确定。
推理
为了更好地理解，让我们首先看一些天真的方法，找出它们的缺点。这也将帮助我们意识到为什么它们通常不应该使用。
天真的方法
第一个天真的方法是通过连接每个向量的对应质心来解压缩所有向量。之后，可以从查询向量到所有数据集向量计算L2距离（或其他度量）。显然，这种方法有效，但非常耗时，因为进行了暴力搜索，距离计算是在高维解压缩向量上执行的。
另一种可能的方法是将查询向量分成子向量，并根据其PQ代码计算每个查询子向量到相应量化向量的距离之和。因此，再次使用暴力搜索技术，这里的距离计算仍需要原始向量维度的线性时间，就像在前一个案例中一样。
另一种可能的方法是将查询向量编码为PQ代码。然后，直接使用此PQ代码计算到所有其他PQ代码的距离。具有最短距离的相应PQ代码的数据集向量然后被认为是查询的最近邻。这种方法比前两种方法更快，因为距离总是在低维PQ代码之间计算。然而，PQ代码由集群ID组成，这些ID没有很多语义含义，可以明确地将其视为实变量使用的分类变量。显然，这是一种不好的做法，这种方法可能会导致预测质量较差。
优化方法
将查询向量分成子向量。对于其每个子向量，计算到相应子空间的所有质心的距离。最终，这些信息存储在表d中。
计算的子向量到质心的距离通常称为部分距离。
通过使用此子向量到质心距离表d，可以通过其PQ代码轻松获得查询到任何数据库向量的近似距离：
- 对于数据库向量的每个子向量，找到最接近的质心j（使用PQ代码的映射值），并采用从该质心到查询子向量i的计算矩阵d中计算出的部分距离d [i] [j]。
- 所有部分距离都被平方并相加。通过对该值取平方根，获得近似欧几里得距离。如果您想知道如何获得其他度量的近似结果，请导航到下面的“其他距离度量的近似”部分。
使用此方法计算近似距离的假设是部分距离d非常接近查询和数据库子向量之间的实际距离a。
然而，这种条件可能不满足，特别是当数据库子向量和其质心之间的距离c很大时。在这种情况下，计算结果的准确性会降低。
在我们获得所有数据库行的近似距离后，我们搜索具有最小值的向量。这些向量将是查询的最近邻居。
其他距离度量的近似
到目前为止，我们已经看过如何通过使用部分距离来近似欧几里得距离。让我们也推广这条规则到其他指标上。
想象一下，我们想要计算一对向量之间的距离度量。如果我们知道指标的公式，我们可以直接应用它以获得结果。但有时我们可以通过以下方式分部分来完成：
- 两个向量被分成n个子向量。
- 对于每对相应的子向量，计算距离度量。
- 计算得到的n个度量然后组合以产生原始向量之间的实际距离。
欧几里得距离是可以通过部分计算的度量的一个例子。基于上面的图，我们可以选择将聚合函数h(z)=z²，g(z₀,z₁,…,zₙ)=sum(z₀,z₁,…,zₙ)和f(z)=√z。
内积是另一个具有聚合函数的度量的例子，h(z)=z，g(z₀,z₁,…,zₙ)=sum(z₀,z₁,…,zₙ)和f(z)=z。
在产品量化的上下文中，这是一个非常重要的属性，因为在推断期间，算法通过部分计算距离。这意味着使用没有这种属性的指标进行产品量化将更加棘手。余弦距离就是这样的指标。
如果仍然需要使用没有此属性的指标，则需要应用额外的启发式方法来聚合部分距离并带有一些误差。
性能
产品量化的主要优势是将作为短PQ代码存储的数据库向量进行大规模压缩。对于一些应用程序，这种压缩率甚至可能高达95％以上！但是，除了PQ代码，还需要存储大小为k x n的矩阵d，其中包含每个子空间的量化向量。
产品量化是一种有损压缩方法，因此压缩率越高，预测精度降低的可能性就越大。
构建高效表示系统需要训练多个聚类算法。除此之外，在推理过程中，需要以暴力方式计算k * n个部分距离，并对每个数据库向量进行求和，这可能需要一些时间。
Faiss实现
Faiss（Facebook AI Search Similarity）是一种用于优化相似性搜索的C++编写的Python库。该库提供了不同类型的索引，这些索引是用于有效存储数据和执行查询的数据结构。
根据Faiss文档中的信息，我们将看到如何利用产品量化。
产品量化实现在IndexPQ类中。对于初始化，我们需要提供3个参数：
- d：数据维数。
- M：每个向量的分割数（与上述使用的n参数相同）。
- nbits：编码单个聚类ID所需的位数。这意味着单个子空间中的总簇数将等于k = 2 ^ nbits。
对于相等的子空间维度分割，参数dim必须可被M整除。
存储单个向量所需的总字节数等于：
如上面的公式所示，为了更有效地使用存储器，M * nbits的值应该可被8整除。
结论
我们已经了解了信息检索系统中非常流行的一种算法，该算法可以高效地压缩大量数据。其主要缺点是推理速度慢。尽管如此，该算法在现代大数据应用程序中广泛使用，特别是与其他相似性搜索技术相结合。
在文章系列的第一部分中，我们描述了反向文件索引的工作流程。实际上，我们可以将这两个算法合并成一个更有效的算法，它将拥有两者的优点！这正是我们将在本系列的下一部分中要做的。
相似性搜索，第3部分：混合反向文件索引和产品量化
在本系列的前两部分中，我们已经讨论了信息检索中的两个基本算法：反向文件索引和产品量化。
小猪AI.com
资源
- 最近邻搜索的产品量化
- Faiss文档
- Faiss存储库
- Faiss索引摘要
除非另有说明，所有图片均为作者所拍。
