Product Quantization（PQ）

Product Quantization 是一种有效的近似最近邻搜索方法，具有较高的搜索效率和较低的内存消耗。该方法已被广泛应用于图像检索、文本检索和机器学习等领域。

PQ 将高维数据点分成多个子空间，并对每个子空间使用独立的编码方法，将数据点映射到一个有限的编码集合中。这个编码过程将高维数据转换成低维编码，从而降低了存储和计算的成本。

Paper：Product Quantization for Nearest Neighbor Search (hal.science)

例如，我们有 N 个 1024 维度的数据点：

将每个向量划分成 8 个 128 维的子向量 subvectors，更多的子向量划分意味着将原始向量空间划分为更多的子空间进行量化，有助于减少量化误差。如下图所示：

对每一组子向量进行聚类，这里簇的数量为 256，聚类的质心数量越多，误差就越小。如下：

聚类之后的每个 subvector 的质心可以作为码本，用于将子向量映射到一个整数。

此时，当我们拿到某一个 1×1024 的数据时，我们就可以通过下面的过程将其量化（用每一个子向量所属质心的编号来表示）：

我们接下来计算下：

1. 量化前：1024 * 4 = 4096 字节
2. 量化后：8 * 1 = 8 字节

Faiss 中 ProductQuantizer 编码和解码实现：

import faiss
import numpy as np


def test():

    data = np.random.rand(10000, 32).astype('float32')
    # 训练码本（向量维度、子向量数量、子向量质心数量（位数））
    pq = faiss.ProductQuantizer(32, 8, 8)
    # pq.verbose = True
    pq.train(data)

    # 编码量化
    x1 = np.random.rand(1, 32).astype('float32')
    x2 = pq.compute_codes(x1)
    # 解码量化
    x3 = pq.decode(x2)

    print('原始向量:\n', x1)
    print('编码量化:\n', x2)
    print('解码量化:\n', x3)


if __name__ == '__main__':
    test()

程序输出结果：

原始向量:
 [[0.7893511  0.04258742 0.02485598 0.8779387  0.6456727  0.5108995
  0.40934694 0.44720596 0.6403179  0.4340338  0.08099802 0.02747925
  0.50549304 0.7623207  0.59890026 0.53147644 0.15379655 0.15767299
  0.6755694  0.01717179 0.55589116 0.5108884  0.28868443 0.3269261
  0.92525804 0.4576955  0.08989486 0.3290053  0.7760333  0.8120166
  0.11302828 0.44827393]]
编码量化:
 [[137  35  19 236  84 100 181 107]]
解码量化:
 [[0.87568134 0.19118658 0.12561512 0.8505063  0.54014504 0.4651005
  0.32801366 0.59519553 0.690649   0.5993807  0.12476301 0.14317577
  0.5528293  0.7269155  0.59982365 0.35701552 0.21440978 0.12651545
  0.6057594  0.12479018 0.46758834 0.5267156  0.3185711  0.3571061
  0.91867924 0.4237765  0.23420191 0.17658444 0.92697316 0.8605662
  0.13733383 0.52912027]]

https://mccormickml.com/2017/10/13/product-quantizer-tutorial-part-1/