本文目录导读：
乘积量化是一种高效的高维向量压缩技术,广泛应用于近似最近邻搜索和推荐系统等领域。
它的核心思想是：将高维向量空间分解为多个低维子空间的笛卡尔积，然后在每个子空间中独立地进行量化。
为什么选择PQ：它有效解决了在高维空间中直接用K-Means聚类导致码本过大、无法使用的问题。
核心思想与数学定义
假设原始向量维度为 ( D ),目标是将其压缩。
-
切分：将 ( D ) 维向量 ( x ) 切分为 ( M ) 个互斥的子向量： [ x = (x^1, x^2, \dots, x^M) ] 其中每个子向量 ( x^m \in \mathbb{R}^{D/M} )。
-
量化：对每个子空间 ( m ) 独立地进行K-Means聚类，得到 ( K ) 个聚类中心（也称为码字），所有子空间的码字集合称为码本（Codebook）： [ \mathcal{C} = {\mathcal{C}_1, \mathcal{C}_2, \dots, \mathcal{C}_M} ] ( \mathcal{C}m = {c{m,1}, c{m,2}, \dots, c{m,K}} )。
-
编码：原始向量 ( x ) 被压缩为 ( M ) 个索引的元组，每个索引表示该子向量属于哪个聚类中心： [ \text{code}(x) = (i_1, i_2, \dots, i_M) ] ( i_m \in [1, K] )。
关键参数配置
- ( M )：子空间数量。
- 影响：( M ) 越大，每个子空间的维度 ( D/M ) 越小，量化越粗糙，压缩率越高，但精度下降；( M ) 越小则相反。
- 典型值：通常设置为 ( 2, 4, 8 ) 等2的幂次方。
- ( K )：每个子空间的聚类中心数量（即码本大小）。
- 影响：( K ) 越大，量化越精细,但存储开销和计算复杂度增加。
- 典型值：( K = 256 ) 是一个常见选择。
- 压缩比：每个向量需要 ( M \times \log_2 K ) 比特存储。
- 示例：若 ( M=8, K=256 )，则一个向量被压缩为 ( 8 \times 8 = 64 ) 比特，而原始float32向量（( D=128 )）需要 ( 128 \times 32 = 4096 ) 比特，压缩比约为 64:1。
编码与解码过程
1 编码（压缩）
- 将原始向量 ( x ) 切分为 ( M ) 个子向量。
- 对每个子向量 ( x^m )，在对应子空间的码本 ( \mathcal{C}m ) 中找到最近邻的码字 ( c{m, j} )，记录其索引 ( j )。
- 输出索引序列 ( [j_1, j_2, \dots, j_M] )。
2 解码（重建）
- 将索引序列拆分,得到每个子空间的码字索引。
- 从对应码本中取出码字向量。
- 拼接所有子空间的码字向量，得到一个近似于原始向量的重建向量 ( \hat{x} )。 [ \hat{x} = [c_{1, j1}, c{2, j2}, \dots, c{M, j_M}] ] 注意：解码是可选的，在搜索场景中通常不需要解码，而是直接使用“不对称距离计算”。
搜索加速的核心：不对称距离计算
这是PQ在搜索场景下高效的关键,它避免了实时解码。
场景：给定查询向量 ( q ),在压缩后的数据库中找到最近邻。
方法：
- 将查询向量 ( q ) 不压缩,保持浮点精度。
- 将 ( q ) 切分为 ( M ) 个子向量 ( [q^1, q^2, \dots, q^M] )。
- 预先计算：针对每个子空间 ( m )，计算 ( q^m ) 与码本 ( \mathcal{C}m ) 中每个码字的距离，得到一个 ( M \times K ) 的距离查找表： [ \text{lut}[m][k] = \text{dist}(q^m, c{m,k}) ]
- 快速计算：对于数据库中的任意压缩向量 ( [j_1, j_2, \dots, jM] )，其与查询向量的近似距离为： [ dist(q, x) \approx \sum{m=1}^{M} \text{lut}[m][j_m] ] 这仅需 ( M ) 次查表和加法运算,而无需任何浮点乘加。
优缺点分析
优点
- 极高压缩率：能将向量内存占用降低到1/50甚至更低。
- 速度快：不对称距离计算将搜索复杂度从 ( O(D) ) 降为 ( O(M) )，( M \ll D )。
- 精度可控：通过调整 ( M ) 和 ( K ) 可在精度和效率之间灵活平衡。
缺点
- 训练成本高：需要对每个子空间分别进行K-Means聚类,且需要大量数据训练码本。
- 假设独立性：PQ假设子空间相互独立，如果原始数据特征之间存在强相关,这种分解会损失信息。
- 非通用最优：对于某些数据分布，其他方法（如OPQ、LSH）可能更优。
变体与改进
- OPQ：在PQ之前，先对数据施加一个正交旋转矩阵，使子空间能量分布更均衡,减少分解带来的误差。
- AQ：允许不同子空间使用不同数量的码字，即非均匀量化,适应不同维度的特征重要性。
- DPQ：对量化后的残差再次进行量化,多级量化以提升精度。
实践应用
- 场景：大规模向量搜索（十亿级），如Faiss、Milvus等向量数据库。
- 工具实现：Faiss库中
IndexPQ类。 - 参数配置建议：
- M：对于128维向量，建议 ( M=8 ) 或 ( M=16 )。
- K：通常固定为 ( 256 )（对应8比特），因为 ( \log_2 256 = 8 ) 字节对齐,硬件友好。
- nbits：在Faiss中，设置
nbits=8即等价于 ( K=256 )。
总结一图流
原始向量 (128维)
│
▼ 切分 (M=4)
[32维] [32维] [32维] [32维]
│ │ │ │
▼ ▼ ▼ ▼ 独立K-Means (K=256)
码本1 码本2 码本3 码本4
│ │ │ │
▼ ▼ ▼ ▼ 选择最近邻索引
(id_1) (id_2) (id_3) (id_4)
│ │ │ │
└──────┴──────┴──────┘
│
▼
压缩结果: [id_1, id_2, id_3, id_4] (仅需 4 * 8 = 32 bits)乘积量化的本质就是以空间换精度，以查表换计算,最适合在内存受限且需要快速返回近似结果的场景。
