译：相似性搜索，第 2 部分：乘积量化

学习有效压缩大数据的强大技术

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

在本系列文章的第一部分中，我们研究了用于执行相似性搜索的 kNN 和倒排文件索引结构。正如我们所知，kNN 是最直接的方法，而倒排文件索引则在其之上发挥作用，建议在速度加速和准确性之间进行权衡。然而，这两种方法都不使用数据压缩技术，这可能会导致内存问题，特别是在数据集较大且 RAM 有限的情况下。在本文中，我们将尝试通过研究另一种称为“乘积量化(Product Quantization)”的方法来解决此问题。

乘积量化是将每个数据集向量转换为短的内存高效表示形式（称为PQ code）的过程。不是完全保留所有向量，而是存储它们的短表示。同时，乘积量化是一种有损压缩方法，预测精度较低，但在实践中，该算法效果很好。

一般来说，量化是将无限值映射到离散值的过程。

训练(Training)

首先，该算法将每个向量分为几个相等的部分——子向量。所有数据集向量的各个部分形成独立的子空间并单独处理。然后对每个向量子空间执行聚类算法。通过这样做，在每个子空间中创建了几个质心。每个子向量都用它所属的质心的 ID 进行编码。此外，所有质心的坐标都会被存储以供以后使用。

子空间质心也称为量化向量(quantized vectors)。

在乘积量化中，簇ID通常被称为再现值(reproduction value)。

Note: 在下图中，矩形表示包含多个值的向量，而正方形表示单个数字。

​ 使用量化进行编码

因此，如果一个原始向量被分为n个部分，那么它可以由n个数字——每个子向量各自质心的 ID 来编码。通常，为了更有效地使用内存，创建的质心k的数量通常选择为 2 的幂。这样，存储编码向量所需的内存为n * log(k)位。

子空间内所有质心的集合称为码本。对所有子空间运行 n 个聚类算法会产生 n 个独立的码本。

压缩示例(Compression example)

想象一下，存储浮点数（32 位）的大小为 1024 的原始向量被分为n = 8个子向量，其中每个子向量由k = 256个簇之一进行编码。因此，对单个簇的 ID 进行编码需要log(256) = 8位。让我们比较两种情况下向量表示的内存大小：

• 原始向量：1024 * 32 位 = 4096 字节。
• 编码向量：8 * 8 位 = 8 字节。

最终压缩512倍！这就是产品量化的真正力量。

​ 量化示例(向量中的数字显示它存储了多少个数字)

以下是一些重要的注意事项：

• 该算法可以在一个向量子集上进行训练（例如，以创建聚类）并用于另一个向量子集：训练完算法后，将传递另一个向量数据集，其中通过使用每个子空间已构造的质心对新向量进行编码。
• 通常，选择 k-means 作为聚类算法。它的优点之一是簇的数量k是一个超参数，可以根据内存使用需求手动定义。

推理查询(Inference)

为了更好地理解，让我们首先看一下几种简单的方法并找出它们的缺点。这也将帮助我们了解为什么它们不应该被正常使用。

朴素方法(Naive approaches)

第一种简单方法包括通过连接每个向量相应的质心来解压缩所有向量。之后，可以计算从查询向量到所有数据集向量的L2距离（或其他度量）。显然，这种方法是可行的，但是非常耗时，因为要对高维解压向量进行暴力搜索和距离计算。

另一种可能的方式是将查询向量分割成子向量，并基于其PQ码计算从每个查询子向量到数据库向量的相应量化向量的距离之和。因此，再次使用暴力搜索技术，并且这里的距离计算仍然需要原始向量维数的线性时间，如前一情况所示。

​ 使用朴素方法计算近似距离（该示例以欧氏距离作为度量）

另一种可能的方法是将查询向量编码成PQ码。然后直接利用该 PQ 代码来计算到所有其他 PQ 代码的距离。然后，具有最短距离的相应 PQ 代码的数据集向量被视为查询的最近邻居。这种方法比前两种方法更快，因为距离始终是在低维 PQ 代码之间计算的。然而，PQ码由簇ID组成，没有太多语义，可以被视为明确用作实数变量的分类变量。显然，这是一种不好的做法，并且这种方法可能会导致预测质量较差。

查询向量被划分为子向量。对于每个子向量，计算到相应子空间的所有质心的距离。最终，该信息存储在表d中。

​ 获取存储部分查询子向量到质心距离的表 d

计算出的子向量到质心的距离通常称为部分距离(partial distances)。

通过使用这个子向量到质心距离表d，可以通过其 PQ 代码轻松获得从查询到任何数据库向量的近似距离：

1. 对于数据库向量的每个子向量，找到最近的质心j（通过使用 PQ 代码的映射值）以及从该质心到查询子向量i的部分距离d[i][j]（通过使用计算的矩阵d）被获取。
2. 所有部分距离均被平方并求和。通过对该值求平方根，即可获得近似的欧氏距离。如果还想了解如何获得其他度量的近似结果，见其他距离度量的近似值

​ 使用 PQ 代码和距离表计算从查询到数据库向量的距离

使用此方法计算近似距离假设：部分距离d非常接近查询和数据库子向量之间的实际距离a 。

然而，这个条件可能不被满足，特别是当数据库子向量与其质心之间的距离*c很大时。*在这种情况下，计算会导致精度降低。

左边的例子展示了当实际距离非常接近部分距离（c 很小）时的近似情况。在右侧，我们可以观察到一个糟糕的场景，因为部分距离比实际距离长得多（c很大）。

在获得所有数据库行的近似距离后，我们搜索具有最小值的向量。这些向量将是查询的最近邻。

其他距离度量的近似值（Approximation of other distance metrics）

到目前为止，我们已经了解了如何使用部分距离来近似欧氏距离。让我们也将这一规则推广到其他度量方式。

想象一下我们想要计算一对向量之间的距离度量。如果我们知道度量的公式，我们可以直接应用它来得到结果。但有时我们可以通过以下方式分部分完成：

• 两个向量都分为n个子向量。
• 对于每对相应的子向量，计算距离度量。
• 然后将计算出的n 个度量组合起来，生成原始向量之间的实际距离。

该图显示了计算度量的两种方法。在左侧，度量公式直接应用于两个向量。在右侧，计算每对相应子向量的部分距离。然后使用聚合函数 h、g 和 f 将它们组合起来。

欧几里德距离是可以按部分计算度量的。根据上图，我们可以选择聚合函数为h(z) = z²、g(z₀, z₁, …, zₙ) = sum(z₀, z₁, …, zₙ)和f(z) = √z。

​ 欧氏距离可以分部分计算

内积(IP-Inner product )是此类度量的另一个示例，具有聚合函数h(z) = z、g(z₀, z₁, …, zₙ) = sum(z₀, z₁, …, zₙ) 和 f(z) = z。

在乘积量化的背景下，这是一个非常重要的属性，因为在推理查询过程中，算法按部分计算距离。这意味着使用不具有此属性的度量进行乘积量化会出现更多问题。余弦距离是此类度量的一个示例。

如果仍然需要使用没有此属性的度量，则需要应用额外的启发式方法来聚合具有一定误差的部分距离。

性能(Performance)

乘积量化的主要优点是对存储为短 PQ 代码的数据库向量进行大规模压缩。对于某些应用来说，这样的压缩率甚至可能高于95%！然而，除了PQ码之外，还需要存储包含每个子空间的量化向量的大小为k x n的矩阵d 。

乘积量化是一种有损压缩方法，因此压缩率越高，预测精度就越有可能下降。

构建有效表示的系统需要训练多种聚类算法。除此之外，在推理查询过程中，需要以暴力方式计算k * n个部分距离，并对每个数据库向量求和，这可能需要一些时间。

​ 产品量化性能

FAISS 实现

Faiss（Facebook AI Search Comparison）是一个用 C++ 编写, binding Python使用的faiss库, 提供c api 库方便FFI交互，用于优化相似性搜索。该库提供了不同类型的索引，这些索引是用于有效存储数据和执行查询的数据结构。

根据Faiss 文档中的信息，我们将了解如何利用乘积量化。

乘积量化在IndexPQ类中实现。为了初始化，我们需要为其提供 3 个参数：

• d：数据的维度数。
• M ：每个向量的分割数（与上面使用的n参数相同）。
• nbits：编码单个簇 ID 所需的位数。这意味着单个子空间中的总簇数将等于k = 2^nbits。

对于相等的子空间维度分裂，参数d必须能被M整除。

存储单个向量所需的总字节数等于：

正如我们在上面的公式中看到的，为了更有效地使用内存，M * nbits 的值应该能被8整除。

​ IndexPQ 的 Faiss 实现

我们研究了信息检索系统中非常流行的算法，该算法可以有效地压缩大量数据。它的主要缺点是推理查询速度慢。尽管如此，该算法仍广泛应用于现代大数据应用中，特别是与其他相似性搜索技术结合使用。

在本系列文章的第一部分中，我们描述了倒排文件索引的工作流程。事实上，我们可以将这两种算法合并成一种更高效的算法，从而兼具两者的优点！这正是我们在本系列的下一部分中要做的事情。

Reference

原文地址： https://towardsdatascience.com/similarity-search-product-quantization-b2a1a6397701

附操作学习笔记:

faiss_product_quantization.ipynb