第 112 题：乘积量化(PQ)的码本训练，k-means的聚类数量选择？
题目
乘积量化(PQ)的码本训练，k-means的聚类数量选择？
完整讲解
一、乘积量化（PQ）概要
将 $d$ 维向量分成 $m$ 段，每段 $d/m$ 维；每段各自用子码本量化，共 $m$ 个子码本、每码本 $k$ 个码字。向量用 $m$ 个码字索引表示，存储从 $d$ 个 float 变为 $m \cdot \log_2 k$ bit，距离用码字间距离表近似，复杂度 $O(m)$ 而非 $O(d)$。
二、码本训练与 k-means
每个子空间独立做 k-means：对第 $j$ 段的所有训练向量 $\boldsymbol{x}j^{(i)}$ 聚类，得到 $k$ 个聚类中心作为该段的码本 $\mathcal{C}_j = {\boldsymbol{c}{j,1},\ldots,\boldsymbol{c}_{j,k}}$。训练数据通常为全量或采样的底库向量，按段切分后各自聚类，无交叉子空间约束。
量化：$\boldsymbol{x}j \mapsto \arg\min{\boldsymbol{c} \in \mathcal{C}_j} |\boldsymbol{x}_j - \boldsymbol{c}|$，即每段找最近码字，用码字索引 $i_j \in [k]$ 表示。查询时用非对称距离（查询未量化）或对称距离（查表）近似 $|\boldsymbol{q} - \boldsymbol{x}|^2$。
三、聚类数量 $k$ 的选择
- 每段码本大小 $k$：总码本大小为 $k^m$（组合数），实际可区分向量数约 $k^m$。$k$ 大则每段量化误差小、重构好，但码本与距离表大（$m \cdot k$ 个码字、查表 $O(mk)$ 若暴力）；$k$ 小则压缩狠、快但误差大。常用：$k=256$（8 bit/段），平衡精度与存储；$k=64$ 或 512 也常见。
- 段数 $m$：$m$ 大则每段维度 $d/m$ 小，子空间 k-means 更准，但 $m$ 过大每段信息不足、量化误差反升。通常 $m \in [4, 16]$，$d=128$ 时 $m=8$ 常见。
- 经验：先定总 bit 预算（如 64 bit = $m \cdot \log_2 k$），再在 $m$ 与 $k$ 间折中；或用验证集扫 recall@K 与 latency 选 $(m,k)$。
四、工程要点
- 子空间假设（各段独立）在向量旋转/分布不均时可能弱；可先用 OPQ 旋转再 PQ。
- 训练时 k-means 的 $k$ 与推理一致；大规模底库可对每段采样训练以加速码本学习。
面试要点
- 能说明 PQ 的段划分、每段 k-means 得子码本、量化与查表距离。
- 能说清 $k$ 大则精度高、存储与查表成本大；$k$ 小则压缩狠、误差大；常用 $k=256$、$m$ 约 4～16。
- 能提及总 bit 预算、验证集调参、与 OPQ 结合。
记忆要点
- PQ：$d$ 维分 $m$ 段，每段 k-means 得 $k$ 个码字；量化用最近码字索引，距离查表 $O(m)$。
- $k$ 大→精度高、成本大；$k$ 小→压缩狠、误差大；常用 $k=256$、$m=4\sim 16$。
- 总 bit=$m \log_2 k$；可结合 OPQ 旋转再 PQ。