详解向量数据库中的PQ算法（Product Quantization）

文章目录

• 1. 核心原理
• • 1.1 基本思想
• 2. 算法步骤
• • 2.1. 训练阶段
  • 2.2. 编码阶段
• 3. 图解说明
• • 1.1 搜索过程图解
• 4. 压缩效果
• 5. 优势与权衡
• 6. 参数选择
• 7. 子空间和子向量的关系
• • 7.1 核心关系
  • 7.2 详细说明
  • 7.3 形象类比
  • 7.4 PQ算法中的应用
  • 7.5 关键要点
  • • 为什么叫"乘积"量化？
    • 数学表达
  • 7.7 实际例子
  • 7.8 子向量和子空间的关系总结

HNSW的原理看这里：图解 HNSW（Hierarchical Navigable Small Worlds）原理 IVF原理看这里：IVF（Inverted File）原理图解：高维向量的分桶加速搜索

PQ算法是Faiss、Milvus等向量数据库的核心技术之一，在保持可接受精度的同时，极大提升了大规模向量检索的效率。

1. 核心原理

Product Quantization（乘积量化）是一种向量压缩技术，通过将高维向量分割成子向量并分别量化，实现大幅度的内存压缩和快速的近似最近邻搜索。

1.1 基本思想

2. 算法步骤

2.1. 训练阶段

原始向量: [x1, x2, x3, x4, x5, x6, x7, x8] (D=8维)
↓ 分割成M=4个子向量
子向量1: [x1, x2]
子向量2: [x3, x4]
子向量3: [x5, x6]
子向量4: [x7, x8]
↓ 每个子空间用K-means聚类
码本1: {c1,1, c1,2, …, c1,256} (256个聚类中心)
码本2: {c2,1, c2,2, …, c2,256}
码本3: {c3,1, c3,2, …, c3,256}
码本4: {c4,1, c4,2, …, c4,256}

2.2. 编码阶段

原始向量 v = [2.1, 3.5, 1.2, 4.8, 0.9, 2.3, 3.7, 1.5]
↓ 分割
[2.1,3.5] → 最近的聚类中心是码本1的第37号 → 编码: 37
[1.2,4.8] → 最近的聚类中心是码本2的第102号 → 编码: 102
[0.9,2.3] → 最近的聚类中心是码本3的第5号 → 编码: 5
[3.7,1.5] → 最近的聚类中心是码本4的第201号 → 编码: 201

最终编码: [37, 102, 5, 201] (4个字节，原本需要32字节)

3. 图解说明

让我用可视化的方式展示PQ算法：

原始高维空间 (例如128维)
┌─────────────────────────────────────────────┐
│ 向量v = [v1, v2, v3, …, v127, v128] │
└─────────────────────────────────────────────┘
↓ 分割成8个子向量
┌──────────┬──────────┬──────────┬──────────┐
│ v1…v16 │v17…v32 │v33…v48 │ … │
│ 子空间1 │ 子空间2 │ 子空间3 │ 子空间8 │
└──────────┴──────────┴──────────┴──────────┘
↓ ↓ ↓ ↓
K-means K-means K-means K-means
↓ ↓ ↓ ↓
┌──────────┐┌──────────┐┌──────────┐┌──────────┐
│ 码本1 ││ 码本2 ││ 码本3 ││ 码本8 │
│ 256个 ││ 256个 ││ 256个 ││ 256个 │
│ 聚类中心 ││ 聚类中心 ││ 聚类中心 ││ 聚类中心 │
└──────────┘└──────────┘└──────────┘└──────────┘

1.1 搜索过程图解

查询向量 q
↓ 分割成子向量
[q1] [q2] [q3] … [q8]
↓ ↓ ↓ ↓
计算与每个码本中所有聚类中心的距离

距离表 (Distance Table):
┌────────────────────────────────┐
│ 码本1 码本2 码本3 … │
│ 中心1 d11 d21 d31 │
│ 中心2 d12 d22 d32 │
│ … … … … │
│中心256 d1,256 d2,256 d3,256 │
└────────────────────────────────┘

数据库中的编码向量: [37, 102, 5, 201]
↓ 查表
近似距离 ≈ d1,37 + d2,102 + d3,5 + d4,201

4. 压缩效果

原始存储：

• 128维浮点向量：128 × 4字节 = 512字节

PQ压缩后（M=8, k=256）：

• 8个子向量编码：8 × 1字节 = 8字节
• 压缩比：64:1

5. 优势与权衡

优势：

• 内存占用减少几十倍
• 搜索速度快（查表操作）
• 适合大规模向量检索

权衡：

• 精度损失（近似搜索）
• 需要训练阶段
• 重构误差随压缩率增加

6. 参数选择

• M（子向量数量）：通常选择8、16、32，必须能整除向量维度
• k（每个码本大小）：通常256（1字节）或更大
• 码本越大：精度越高，但计算和存储成本增加

7. 子空间和子向量的关系

7.1 核心关系

子向量是数据，子空间是几何概念

原始128维向量: [v1, v2, v3, …, v127, v128]
↓ 分割
┌───────────┼───────────┬───────────┐
│ │ │ │
[v1…v16] [v17…v32] [v33…v48] [v49…v64] …
↑ ↑ ↑ ↑
子向量1 子向量2 子向量3 子向量4
│ │ │ │
↓ ↓ ↓ ↓
子空间1 子空间2 子空间3 子空间4
(16维空间) (16维空间) (16维空间) (16维空间)

7.2 详细说明

7.3 形象类比

想象一个3D坐标系 (x, y, z)

原始向量: point = (x=2, y=3, z=5)
↓ 分割
子向量1: (x=2, y=3) ← 这是具体的数值
子向量2: (z=5) ← 这是具体的数值

子空间1: XY平面 ← 这是2维空间
子空间2: Z轴 ← 这是1维空间

7.4 PQ算法中的应用

# 原始128维向量
vector = [v1, v2, ..., v128]

# 分成8个子向量 (每个16维)
sub_vector_1 = vector[0:16] # 具体数据
sub_vector_2 = vector[16:32] # 具体数据
# …

# 对应8个子空间
subspace_1 = R^16 # 第1-16维构成的16维空间
subspace_2 = R^16 # 第17-32维构成的16维空间
# …

# 在每个子空间中训练码本
codebook_1 = KMeans训练(所有样本的sub_vector_1) # 在subspace_1中聚类
codebook_2 = KMeans训练(所有样本的sub_vector_2) # 在subspace_2中聚类

7.5 关键要点

为什么叫"乘积"量化？

因为原始空间被分解为多个子空间的笛卡尔积：

原始空间 R^128 ≈ R^16 × R^16 × R^16 × … × R^16
↑ ↑ ↑ ↑
子空间1 子空间2 子空间3 子空间8

每个向量的量化 = 在每个子空间中独立量化的"乘积"

数学表达

向量 v ∈ R^d

分割后:
v = [v^(1), v^(2), …, v^(M)]

其中:
– v^(m) 是第m个子向量 (数据)
– v^(m) ∈ R^(d/M) 表示它属于第m个子空间 (空间)

7.7 实际例子

# 一个具体的128维向量
vector = np.random.randn(128)

# 分成8个子向量
M = 8
d_sub = 128 // 8 = 16

for m in range(M):
# 提取子向量 (具体数据)
sub_vector = vector[m*16 : (m+1)*16]

# 这个子向量存在于第m个子空间 (16维空间)
# 在这个子空间中进行量化
code[m] = find_nearest_center(sub_vector, codebook[m])

7.8 子向量和子空间的关系总结

• 子向量：数据层面，原始向量的切片
• 子空间：几何层面，子向量所在的低维空间
• 关系：子向量 ∈ 子空间（属于关系）

这就像：

• 点 (子向量) 在 平面 (子空间) 上
• 学生 (子向量) 在 教室 (子空间) 里

PQ算法的巧妙之处在于：把一个高维空间的复杂问题，分解成多个低维子空间的简单问题，分别处理后再组合！