理解乘积量化(Product Quantization)

前言:
　　记录一下 PQ(乘积量化)的一些学习笔记以及在 faiss 中的运用，方便以后查找。

应用场景：

解决的是海量数据场景下高维度特征向量数据的近似最近邻快速查找。

Product Quantization 算法

Product Quantization 本质是将原始高维空间分解为有限数量的低维子空间的笛卡尔积，然后分别量化。与此同时也进行了内存空间的压缩。

相似检索(距离计算)

作者提供了两种距离计算方式，分别为 “对称距离计算”(SDC) 和 “非对称距离计算”(ADC) ，分别如下左右图所示:

对称距离计算：直接使用两个压缩向量 x，y 的索引值所对应的码字 q(x),q(y)之间的距离代替之，而 q(x),q(y)之间的距离可以离线计算，因此可以把 q(x),q(y)之间的距离制作成查找表，只要按照压缩向量的索引值进行对应的查找就可以了，所以速度非常快；
非对称距离计算：使用 x，q(y)之间的距离代替 x，y 之间的距离，其中 x 是测试向量。虽然 y 的个数可能有上百万个，但是 q(y)的个数只有 k 个，对于每个 x，我们只需要在输入 x 之后先计算一遍 x 和 k 个 q(y)的距离，制成查找表（因为只有 k 个，所以速度是非常快的），然后按照 y 对应的压缩向量索引值进行取值操作就可以了。

小结：

不管哪种计算方法都可以实现快速的距离计算，但是非对称距离计算由于只量化了 y，所以计算的距离精度更高，效果也更好。距离计算过程中只需要存储码书和对应的索引值就可以完全抛弃原始的图像表达向量，实现数据的压缩和距离的快速计算。
　　但是需要明白的是，这种算法是基于量化的，所以必然存在量化误差，所以距离的计算并不是完全准确的。通常通过这种算法迅速返回 N 个结果，然后再在 N 个结果中进行进一步的匹配计算，得到比较准确的结果。
　　 OPQ 试图寻找一个正交矩阵，将原始矩阵旋转后再行分解，以使量化后的向量重建后，其误差最小。

Faiss PQ 的示例

PQ 示例

d 是输入数据的维度，nbits 是存储向量的 bits 数目。

m = 16                                   # number of subquantizers
n_bits = 8                               # bits allocated per subquantizer
pq = faiss.IndexPQ (d, m, n_bits)        # Create the index
pq.train (x_train)                       # Training
pq.add (x_base)                          # Populate the index
D, I = pq.search (x_query, k)            # Perform a search

IndexRefineFlat

对搜索结果进行精准重排序

q = faiss.IndexPQ(d, M, nbits_per_index)  # nbits_per_index: bits allocated per subquantizer
rq = faiss.IndexRefineFlat(q) # 对搜索结果进行精准重排序
rq.train (xt)
rq.add (xb)
rq.k_factor = 5	# Re-rank时要核实的数据量
D, I = rq:search (xq, 10)

带倒排的 PQ：IndexIVFPQ

coarse_quantizer = faiss.IndexFlatL2(d)
index = faiss.IndexIVFPQ (coarse_quantizer, d,
                          ncentroids, M, nbits_per_index) # ncentroids 类心数目
index.nprobe = 50 # 控制速度和精度的折中,搜索时，检索离目标距离最近的nprobe个块

小结：摘自ANN 中乘积量化与多维倒排小结

向量量化是一种有损压缩。
乘积量化中子空间不一定越多越好，要平衡计算复杂度和量化精度.
类心越多，量化失真(distortion)越小，计算成本也会相应增强。类心数目（centroid）是实际中常调整的超参。
乘积量化有个前提假设，两个子空间（subspace）独立。但实际上大多数不是这样，这里引出了 OPQ 的优化。
- OPQ（Ge T, He K, Ke Q, et al. Optimized Product Quantization[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2013, 36(4):744-755.），是针对 PQ 中子空间存在相关性的优化。主要内容是添加旋转矩阵作用于字典（codebook），并依次迭代 R 和聚类，使得最终的量化损失最小。
- LOPQ（Kalantidis Y , Avrithis Y . Locally Optimized Product Quantization for Approximate Nearest Neighbor Search[C]// 2014 IEEE Conference on Computer Vision and Pattern Recognition. IEEE, 2014.）在 OPQ 的基础上，加入了每个子空间的各自旋转矩阵。下图展示了不同量化方法下的类心分布。