向量数据库FAISS之二：基础进阶版

基础

1.评价类型和距离

1.METRIC_L2

Faiss 使用了欧几里得 (L2) 距离的平方，避免了平方根。

这仍然与欧几里德距离一样单调，但如果需要精确距离，则需要结果的额外平方根。

2.METRIC_INNER_PRODUCT

这通常用于推荐系统中的最大内积搜索。

查询向量的范数不会影响结果的排名（当然数据库向量的范数也很重要）。

这本身并不是余弦相似度，除非向量被归一化

3.其他评价指标

其他指标也被支持在 IndexFlat, IndexHNSW 和 GpuIndexFlat.

如 METRIC_L1, METRIC_Linf, METRIC_Lp

此外还有METRIC_Canberra, METRIC_BrayCurtis and METRIC_JensenShannon

2.Faiss 构建模块：clustering, PCA, quantization

Faiss 建立在一些具有非常高效实现的基本算法之上：k-means 聚类、PCA、PQ 编码/解码。

1.clustering

Faiss 提供了一个高效的 k-means 实现。

对存储在给定二维张量 x 中的一组向量进行聚类，如下所示：

ncentroids = 1024
niter = 20
verbose = True
d = x.shape[1]
kmeans = faiss.Kmeans(d, ncentroids, niter=niter, verbose=verbose)
kmeans.train(x)

生成的质心位于 kmeans.centroids 中。

迭代过程中的目标函数值（k-means 的总平方误差）存储在 kmeans.obj 变量中，更多的统计信息存储在 kmeans.iteration_stats 变量中。

如果附加选项，gpu=True 那么将运行在 GPU 上

• 一些参数：
• nredo：运行聚类的次数，保留最佳质心（根据聚类目标选择）
• verbose：使聚类过程更详细
• spherical：执行球面 k-means – 每次迭代后质心都进行 L2 归一化
• int_centroids：将质心坐标四舍五入为整数
• update_index：每次迭代后重新训练索引？
• min_points_per_centroid / max_points_per_centroid：低于此值会发出警告，高于此值会对训练集进行子采样
• seed：随机数生成器的种子

要想计算 k-means 训练完后，向量 x 到聚类中心的映射

D, I = kmeans.index.search(x, 1)

这将返回 x 中每行向量的最近质心在 I 中。D 包含 L2 距离的平方。

对于相反的操作，例如。要查找 x 中距计算质心最近的 15 个点，必须使用新索引：

index = faiss.IndexFlatL2(d)
index.add(x)
D, I = index.search(kmeans.centroids, 15)

I 大小 (ncentroids, 15) 包含每个质心的最近邻居

2.计算 PCA

减少 40D 向量 到 10D

mt = np.random.rand(1000, 40).astype('float32')
mat = faiss.PCAMatrix(40, 10)
mat.train(mt)
assert mat.is_trained
tr = mat.apply(mt)
print(tr **2).sum(0)

3.量化器

量化器对象继承自 Quantizer，提供三种常用方法.

• train: 在向量矩阵上训练量化器
• compute_codes 和 decode: 编码和解码。编码器通常是有损的，并为每个输入向量返回一个 uint8 代码矩阵。
• get_DistanceComputer: 返回一个 DistanceComputer 对象的方法

Quantizer 对象的状态是训练的结果。字段 code_size 指示由量化器生成的每个代码的字节数。

量化类型

• ScalarQuantizer: 在线性范围内，分别量化每个向量组件
• ProductQuantizer: 在子向量上执行向量量化
• AdditiveQuantizer: 把一个向量编码成 代码表实体的集合，加性量化器细节在这里。加性量化能被训练以几种方式，因此有子类 ResidualQuantizer, LocalSearchQuantizer, ProductAdditiveQuantizer

Additive quantizers
加性量化器在维度 d 上近似一个向量 x 如下
$x\approx x’=T_1[i_1]+\dots +T_M[i_M]$
$T_m$ 是 $i_m$ 索引化的 d 维向量表。表 m 的大小是 $K_m$。被存储去表示 x 的 code 是$(i_1,\dots ,i_M)$。他的大小是 $\lceil lo{g}_2(k_1)\rceil +\dots +\lceil lo{g}_2(k_M)\rceil$ 位。
与 寻常的数据适应量化器一样，$T_1,\dots ,T_M$ 表在训练集上学习。

乘积量化可以被认为是加性量化的一种特殊情况，其中只有大小为 $d/M$ 的子向量在每个表中是非零的

论文

摘要

我们引入了一种新的高维矢量压缩方案，该方案使用来自 M 个不同码本的 M 个码字的和来近似矢量。

我们表明，所提出的方案允许压缩和未压缩矢量之间的有效距离和标量积计算。 我们进一步建议矢量编码和码本学习算法，其可以最小化所提出的方案内的编码误差。

在实验中，我们证明了所提出的压缩可以代替乘积量化或与乘积量化一起使用。

简介

我们提出了一种称为加性量化（AQ）的新编码方法，它可以推广 PQ 并进一步提高 PQ 精度，同时在很大程度上保持其计算效率。

与 PQ 类似，AQ 将每个向量表示为几个组件的总和，每个组件来自单独的码本。

与 PQ 不同，AQ 不会将数据空间分解为正交子空间，因此不会进行任何子空间独立性假设。

因此，每个 AQ 数据集内的码字具有与输入矢量相同的长度，并且通常彼此不正交。

因此，与 PQ 不同，AQ 中的码本是在联合优化过程中学习的。

图1.在大小 K=4 的 M=4 个码本的情况下，乘积量化（PQ）与相加量化（AQ）的比较。
两种编码方法都用 1 到 K 之间的 M 个数字对输入向量进行编码。在 PQ 的情况下，该码对应于长度为 D/M 的 M 个码字的级联。在 AQ 的情况下，该码对应于长度为 D 的 M 个码字的和。
给定合适的码本，AQ 能够实现对输入向量的更好的近似。

至关重要的是，我们表明，与 PQ 类似，AQ 允许使用未压缩向量的基于查找表的非对称距离和标量积计算。 对于 PQ 通常使用的小型码本，AQ 的标量积计算效率与 PQ 几乎相同。

与 PQ 相比，具有 AQ 的距离计算（ADC）需要少量额外时间或少量额外存储器，这在许多应用中通过提高的准确度是合理的。

编码，码本学习，距离计算和对 PQ 的改进，对于短码（例如，四个或八个字节）即极端压缩率都特别有利。 对于更长的代码，可以无缝地组合这两种技术（AQ 和 PQ ）。

加性量化

我们现在引入符号并详细讨论加法量化（AQ）。 下面，我们假设我们处理 D 维向量。

AQ 基于一组 M 个码本，每个码本包含 K 个向量（码字）。 我们将第 m 个码本表示为 $C^m$，将第 m 个码本中的第 k 个码字表示为 $c^m(k)$，此设置类似于 PQ。

然而，在 PQ 中，码字具有长度 D = M，AQ 中的码字长度是 D，即它们具有与正被编码的矢量相同的维度。

AQ 模型将矢量 $x\in R^D$ 编码为 M 个码字的总和（每个码本一个码字）。 更详细地，矢量用码元的 M 元组编码 $[i_1,i_2,\dots ,i_M]$ ，其中每个 ID 在 1 和 K 之间。 编码过程（如下所述）寻找最小化x与相应码字之和之间距离的码：

如果，例如 K = 256（如在我们的大多数实验中那样），则将矢量编码为 M 个字节，每个字节编码单个码字 ID。 AQ 编码矢量的存储器占用空间将与 PQ 编码矢量（对于相同的M和K）相同，而 AQ 可以更准确地表示矢量。 AQ 中的码本占用的内存比 PQ 多 M 倍，但是对于足够大的数据集，这种内存增加通常可以忽略不计。

有趣的是，每个量化器都是前一个量化器的超集。

每个量化器都有一个相应的索引类型，该索引类型还存储一组量化向量。

此外，除 ScalarQuantizer 之外的所有索引都存在于 FastScan 版本中，请参阅 PQ 和 AQ 代码的快速累积

4.距离计算

某些量化器返回 DistanceComputer 对象。其目的是在将一个向量与多个 code 进行比较时有效地计算向量到 code 的距离。在这种情况下，通常可以预先计算一组表来直接计算压缩域中的距离。

因此，DistanceComputer 提供：

• set_query 方法，设置当前未压缩向量以进行比较
• distance_to_code 方法，用于计算给定 code 的实际距离。

5.示例：PQ 编码/解码

d = 32  # data dimension
cs = 4  # code size (bytes)

# train set 
nt = 10000
xt = np.random.rand(nt, d).astype('float32')

# dataset to encode (could be same as train)
n = 20000
x = np.random.rand(n, d).astype('float32')

pq = faiss.ProductQuantizer(d, cs, 8)
pq.train(xt)

# encode 
codes = pq.compute_codes(x)

# decode
x2 = pq.decode(codes)

# compute reconstruction error
avg_relative_error = ((x - x2)**2).sum() / (x ** 2).sum()

标量量化器的工作原理类似

d = 32  # data dimension

# train set 
nt = 10000
xt = np.random.rand(nt, d).astype('float32')

# dataset to encode (could be same as train)
n = 20000
x = np.random.rand(n, d).astype('float32')

# QT_8bit allocates 8 bits per dimension (QT_4bit also works)
sq = faiss.ScalarQuantizer(d, faiss.ScalarQuantizer.QT_8bit)
sq.train(xt)

# encode 
codes = sq.compute_codes(x)

# decode
x2 = sq.decode(codes)

# compute reconstruction error
avg_relative_error = ((x - x2)**2).sum() / (x ** 2).sum()

3.选择一个索引的指南

选择索引并不明显，因此这里有一些可以帮助选择索引的基本问题。它们主要适用于 L2 距离。我们指出：

• 它们每个的 index_factory 字符串。
• 如果有参数，我们将它们表示为相应的 ParameterSpace 参数。

1.您会执行少量搜索吗？

“Flat”

如果您计划仅执行少量搜索（例如 1000-10000），则索引构建时间将不会被搜索时间摊销。那么直接计算是最有效的选择。
这是通过 Flat 索引完成的。如果整个数据集无法容纳在 RAM 中，您可以依次构建小索引，然后合并搜索结果。

2.你需要准确的结果么？

唯一可以保证准确结果的索引是 IndexFlatL2 或 IndexFlatIP。

它为其他指数的结果提供了基线。

它不会压缩向量，不会在向量之上添加开销。

它不支持使用 ids 添加（add_with_ids），仅支持顺序添加，因此如果需要 add_with_ids，请使用“IDMap,Flat”。

扁平索引不需要训练，也没有参数。

Supported on GPU: yes

3.关心内存吗？

请记住，所有 Faiss 索引都存储在 RAM 中。下面考虑的是，如果不需要精确的结果，RAM 是限制因素，并且在内存限制内我们优化精度与速度的权衡。

1. 如果不关心内存：HNSW M 或 IVF1024, PQ N x4fs, RFlat

   如果您有大量 RAM 或 数据集很小，HNSW 是最佳选择，它是一个非常快速且准确的索引。

   4 <= M <= 64 是每个向量的链接数，越高越准确，但使用更多 RAM。

   速度与精度的权衡是通过 efSearch 参数设置的。每个向量的内存使用量为 (d * 4 + M * 2 * 4) 字节。

   HNSW 只支持顺序添加（不支持 add_with_ids），因此这里再次说明，如果需要，请使用 IDMap 前缀。 HNSW 不需要训练，也不支持从索引中删除向量。

   第二种选择比 HNSW 更快。然而，它需要重新排序阶段，因此有两个参数需要调整：重新排序的 k_factor 和 IVF 的 nprobe。

   Supported on GPU: no

2. 如果有点在意，使用”…, Flat”

   “...” 表示必须事先执行数据集的聚类（请参阅下文）。

   聚类后，“Flat” 只是将向量组织到桶中，因此不会压缩它们，存储大小与原始数据集相同。速度和精度之间的权衡是通过 nprobe 参数设置的。

   Supported on GPU: yes

3. 如果非常重要，则 OPQM_D,...,PQMx4fsr

   如果存储整个向量成本太高，则执行两个操作：

   OPQ 变换到 D 维以减少维度

   将向量 PQ 量化为 M 4 位代码。

   因此，每个向量的总存储量为 M/2 字节。

   Supported on GPU: yes

4. 如果超级重要，OPQM_D,…,PQM

   PQM 使用输出 M 字节代码的乘积量化器来压缩向量。

   M 通常 <= 64，对于较大的代码，SQ 通常同样准确且更快。

   OPQ 是向量的线性变换，使它们更容易压缩。

   D 是一个维度，使得：

   • D 是 M 的倍数（必填）
   • D <= d，其中 d 是输入向量的维度（首选）
   • D = 4*M（优选）

   Supported on GPU: yes (note: the OPQ transform is done on CPU, but it is not performance critical)

4.数据集多大

该问题用于填写聚类选项（上文 ...）。

数据集被聚类为多个数据桶，在搜索时，只访问其中的一部分数据桶（nprobe 数据桶）。

聚类是在数据集向量的代表性样本（通常是数据集的样本）上进行的。我们将指出该样本的最佳大小。

1. 如果在 1M 向量以下：...,IVFK,...

   其中 K 为 4**sqrt(N) 到 16**sqrt(N)，N 为数据集的大小。

   这只是用 K 均值对向量进行聚类。训练需要 30K 到 256K 的向量（越多越好）。

   Supported on GPU: yes

2. 如果 1M - 10M：”...IVF65536_HNSW32,...”

   IVF 与 HNSW 结合使用 HNSW 进行集群分配。您将需要 30 * 65536 到 256 * 65536 个向量进行训练。

   Supported on GPU: no (on GPU, use IVF as above)

3. 如果 10M-100M："...,IVF262144_HNSW32,..."

   同上，将 65536 替换为 262144 (2^18)。

   请注意，训练会很慢，为了避免这种情况，有两种选择：

   仅在 GPU 上进行训练，其他所有内容都在 CPU 上运行，请参阅 train_ivf_with_gpu.ipynb。

   进行两级聚类，请参阅 demo_two_level_clustering.ipynb

4. 如果 100M - 1B："...,IVF1048576_HNSW32,..."

   同上，将 65536 替换为 1048576 ($2^{20}$)。训练会更慢！