Ch3: 向量量化与 Product Quantization

从标量到向量：为什么要一起看？

上一章的 Lloyd-Max 是标量量化——每个维度独立处理。但想象一个 2D 的例子：数据点沿着一条斜线分布。如果你对 x 轴和 y 轴分别做标量量化，码字会形成一个网格，大量码字浪费在没有数据的区域。

向量量化（VQ）把多个维度当作一个整体，码字直接放在数据密集的地方。1980 年，Linde、Buzo 和 Gray 发表了 LBG 算法——本质上就是 K-means 推广到高维。

🔬 标量量化 vs 向量量化

2D 点云对比：左边是标量量化（网格），右边是向量量化（K-means）。注意码字的位置差异。

直觉理解 标量量化像用网格纸画地图。不管城市在哪里，网格线都是等距的——海洋上浪费大量格子，陆地上格子又不够用。

向量量化像在地图上标记城市。标记点（码字）直接放在有人住的地方——人多的地方标记密集，荒漠里几乎没有标记。不浪费一个码字。

维度诅咒：指数级的灾难

VQ 在 2D 很完美。但真实场景中，embedding 是 128 维、768 维甚至更高。问题来了：

标量量化码本大小 = k | 向量量化码本大小 = k^d

如果 d = 128（典型 embedding 维度），k = 256（8 bit 精度）：

256

标量量化
码本大小

256¹²⁸

向量量化
码本大小

≈ 10³⁰⁸

比宇宙原子数
多 10²²⁸ 倍

指数爆炸有多恐怖？每维 k = 256 个级别（8 bit 精度），看看码本大小如何随维度爆炸：

• d = 1 维：256¹ = 256 个码字（轻松存储）
• d = 2 维：256² = 65,536 个码字（一张表格）
• d = 10 维：256¹⁰ ≈ 1.2 × 10²⁴ 个码字（比地球上所有沙粒还多）
• d = 128 维：256¹²⁸ ≈ 10³⁰⁸ 个码字 🤯

宇宙中的原子总数大约是 10⁸⁰。256¹²⁸ 比这个数大了 10²²⁸ 倍。这就是维度灾难——在高维空间里，直接向量量化是物理上不可能的。

完全不可能存储。即使 k = 2（只分两类），128 维也需要 2¹²⁸ ≈ 10³⁸ 个码字。这就是维度诅咒——高维空间中"体积"指数增长，有限的码本无法覆盖。

Product Quantization：分而治之

2011 年，Hervé Jégou 等人在 PAMI 发表了一个精妙的解决方案：Product Quantization（PQ）。核心思想出奇简单——

把 d 维向量切成 m 段，每段独立做向量量化。

128 维向量

原始数据

→

切成 8 段

每段 16 维

→

各段独立 VQ

每段 256 个码字

→

8 个索引

每个 1 byte

→

8 bytes

64x 压缩

方法	码本大小	每向量存储	可行性
原始 VQ	256¹²⁸ (不可行)	128 bytes	不可能
Product Quantization	8 × 256 = 2,048	8 bytes	64x 压缩
标量量化 (8 bit)	256	128 bytes	4x 压缩

直觉理解 乘积量化像邮政编码系统。如果要给全球 80 亿人每人一个唯一编号，需要 10 位数字。但邮政编码只用 6 位——怎么做到的？

答案：分层编码。前 2 位 = 省（34 个），中间 2 位 = 市（每省 ~100 个），后 2 位 = 区（每市 ~100 个）。
总码本 = 34 + 100 + 100 = 234 个码字，但能表示 34 × 100 × 100 = 34 万个位置。

PQ 同理：128 维向量切成 8 段，每段 256 个码字。总码本 = 8 × 256 = 2,048，但能表示 256⁸ ≈ 1.8 × 10¹⁹ 种组合。代价是丢失了"段与段之间的关联"，但实践证明这个近似非常有效。

PQ 的代价是什么？把向量切段意味着假设各段之间是独立的。这当然不完全正确——维度之间有相关性。PQ 用"牺牲段间相关性"换取了"码本大小从指数降到线性"。这是工程中典型的"够好的近似胜过完美但不可行的方案"。

🔬 PQ 分段可视化

8 维向量被切成 2 段（每段 4 维，简化为 2D 展示）。每段独立聚类，用不同颜色标识。拖动分段数滑块看效果。

分段数 m：2

从论文到工业：FAISS

PQ 不只是理论。2017 年，Meta AI Research 开源了 FAISS（Facebook AI Similarity Search），PQ 是其核心组件之一。

🔍

ADC — 非对称距离计算

预计算 query 子向量到每段码字的距离（m×k 次），然后对每个数据库向量只需 m 次查表 + 求和。十亿级检索毫秒完成。

ADC 怎么做到毫秒级搜索十亿向量？ 关键：预计算 + 查表。

假设查询向量 q 分成 8 段，每段有 256 个码字。
Step 1（预计算）：计算 q 的每段到 256 个码字的距离 → 共 8 × 256 = 2,048 次距离计算 → 存入查找表
Step 2（对每个库向量）：库向量已编码为 8 个码字 ID → 查表 8 次 + 求和 → 8 次加法

十亿个库向量 × 8 次加法 = 80 亿次加法。现代 CPU 每秒做 100 亿次加法。
所以：搜索 10 亿个向量 ≈ 1 秒。这就是 Spotify 推荐、Google 图片搜索的技术基础。

今天，几乎所有大规模 embedding 检索场景都在用 PQ 或其变体：Meta 的推荐系统、Spotify 的音乐推荐、Airbnb 的房源搜索、Google 的图像搜索。你每天使用的推荐系统背后，很可能就是 PQ 在工作。

🎯 本章要点

向量量化 (VQ)：把多维度当整体量化，码字直接放在数据密集处（= 高维 K-means）
维度诅咒：VQ 码本大小 = k^d，高维不可行（128 维需要 10³⁰⁸ 个码字）
Product Quantization：分段独立 VQ，码本从 k^d 降到 m×k。典型 128 维 → 8 bytes（64x 压缩）
FAISS：Meta 开源的 PQ 工业实现，十亿级检索毫秒完成
Trade-off：PQ 牺牲段间相关性换取可行性——"够好的近似 > 完美但不可行"

📋 人物档案

本章提及

Yoseph Linde, Andres Buzo & Robert Gray

1980 · 美国 · USC / Stanford

三人联合提出 LBG 算法（以三人姓氏首字母命名），将 K-means 聚类从低维标量推广到高维向量空间。LBG 算法是向量量化的标准训练方法：在高维空间中寻找最优码本，使得量化失真最小。这一突破证明了向量量化在理论上可以逼近 Shannon 的率失真极限。

Herve Jegou（埃尔韦·热古）

生年不详 · 法国 · INRIA → Meta AI Research

2011 年在 IEEE PAMI 发表 Product Quantization（乘积量化）论文，提出了解决向量量化"维度灾难"的关键方案：将高维向量切分为多个低维子空间，每个子空间独立量化。这使得十亿级向量的近似最近邻检索成为可能。后来加入 Meta AI，主导开发了 FAISS 库（2017），现已成为工业界向量检索的标准工具。

📐 公式详解

本章公式

向量量化码本规模（维度灾难）

码本大小 = k^d（k 个级别，d 维向量）

直觉：标量量化只需 k 个码字（如 256 个），但向量量化需要 k^d 个——这是指数爆炸。对于 d=128 维、k=256 的情况，码本大小为 256^128 ≈ 10^308，比宇宙中的原子数还多。这就是为什么直接的向量量化在高维空间中不可行。

k — 每维的量化级数（如 256 = 8 bit）
d — 向量维度
k^d — 高维码本所需的码字总数

乘积量化（PQ）分解

k^d → m × k（如 256^128 → 8 × 256 = 2,048）

直觉：把一个 128 维向量切成 8 段（每段 16 维），每段独立用 256 个码字量化。存储空间从 128 字节降到 8 字节（64 倍压缩），码本从天文数字缩减到 2048 个码字。代价是丢失了跨子空间的相关性，但实践中这个近似非常有效。

m — 子空间数量（如 8）
k — 每个子空间的码字数（如 256）
d/m — 每个子空间的维度（如 128/8 = 16）

ADC 非对称距离计算

d(q, x̃) ≈ Σᵢ d(qᵢ, c_mᵢ(xᵢ)) （查表求和）

直觉：查询向量 q 不量化（保持精确），只对库中的向量 x 使用量化近似。计算距离时，预先算好 q 的每个子段到所有码字的距离（建表），然后对每个库向量只需查 m 次表再求和。这使得十亿级检索在毫秒内完成。

q — 查询向量（不量化）
x̃ — 库中向量的 PQ 近似
qᵢ — 查询向量的第 i 个子段
c_mᵢ(xᵢ) — x 第 i 个子段对应的码字

为什么这还不够？

PQ 解决了高维数据的压缩检索问题。但当压缩对象变成神经网络本身——
数十亿个权重参数，每个都有不同的重要性——怎么办？
下一章：当神经网络遇到压缩 — 从剪枝到蒸馏到 GPTQ/AWQ。

向量量化与Product Quantization