用于最近邻搜索的乘积量化

H. Jégou, M. Douze and C. Schmid, "Product Quantization for Nearest Neighbor Search," in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 33, no. 1, pp. 117-128, Jan. 2011, doi: 10.1109/TPAMI.2010.57.

1. 引言

在许多计算机视觉和机器学习应用中，计算高维向量之间的欧氏距离是一个基本需求。最近邻（NN）搜索问题定义为：给定D维欧氏空间$\mathbb{R}^D$中的有限集合$Y \subset \mathbb{R}^D$，包含n个向量，找到使距离最小的元素：

$$\text{NN}(x) = \arg\min_{y \in Y} d(x, y)$$

其中$d(x,y) = |x - y|$是欧氏距离。由于维度诅咒的存在，当维度D很高时，传统的多维索引方法（如KD树、球树等）的性能急剧下降，甚至不如暴力穷举搜索，后者的复杂度为$O(nD)$。

近似最近邻（ANN）算法通过"仅"以高概率而非概率1找到最近邻来克服这一问题。局部敏感哈希（LSH）是最流行的ANN算法之一，它提供了理论保证但在实际数据上经常被启发式方法超越。这些启发式方法包括随机KD树和层次k-means，它们利用了向量的分布特性。

本文提出的乘积量化方法的关键创新在于将空间分解为低维子空间的笛卡尔积，并分别对每个子空间进行量化。这种方法能够用短码表示向量，同时保持距离估计的准确性。

2. 向量量化背景

2.1 向量量化基础

量化器是一个函数$q: \mathbb{R}^D \to C$，将D维向量$x \in \mathbb{R}^D$映射到码本$C = {c_i, i \in I}$中的一个质心，其中索引集$I = {0, ..., k-1}$是有限的。

Voronoi单元定义为映射到给定索引$i$的所有向量的集合：

$$V_i = \{x \in \mathbb{R}^D : q(x) = c_i\}$$

k个单元形成$\mathbb{R}^D$的一个划分。量化器的质量通过均方误差（MSE）衡量：

$$\text{MSE}(q) = \mathbb{E}_X[d(q(x), x)^2] = \int p(x) d(q(x), x)^2 dx$$

其中$p(x)$是随机变量$X$对应的概率分布函数。

最优量化器必须满足两个Lloyd条件：

1. 向量必须被量化到最近的质心：$q(x) = \arg\min_{c_i \in C} d(x, c_i)$
2. 质心必须是其Voronoi单元中向量的期望值：$c_i = \mathbb{E}X[x|i] = \int{V_i} p(x) x dx$

另一个重要量是均方失真$\xi(q, c_i)$，表示用质心$c_i$重建单元$V_i$中向量时的失真：

$$\xi(q, c_i) = \frac{1}{p_i} \int_{V_i} d(x, q(x))^2 p(x) dx$$

其中$p_i = P(q(x) = c_i)$是向量被分配到质心$c_i$的概率。

2.2 乘积量化器

乘积量化的核心思想是将输入向量$x$分割成$m$个不同的子向量$u_j$，每个维度为$D^* = D/m$（假设D是m的倍数）：

$$x = [x_1, ..., x_{D^*} | x_{D^*+1}, ..., x_{2D^*} | ... | x_{D-D^*+1}, ..., x_D]$$
$$= [u_1(x) | u_2(x) | ... | u_m(x)]$$

子向量使用$m$个不同的量化器分别量化。向量$x$因此被映射为：

$$x \mapsto (q_1(u_1(x)), q_2(u_2(x)), ..., q_m(u_m(x)))$$

乘积量化器的重构值由乘积索引集$I = I_1 \times ... \times I_m$中的元素标识。码本定义为：

$$C = C_1 \times ... \times C_m$$

假设所有子量化器具有相同的有限数量$k^*$个重构值，则质心总数为：

$$k = (k^*)^m$$

在极端情况下，当$m = D$时，向量的所有分量都被单独量化，乘积量化器退化为标量量化器。

图1描述：该图展示了SIFT描述符的量化误差与参数$m$和$k^$的关系。横轴是码长（比特），纵轴是平方失真$D(q)$。图中显示了不同$(m, k^)$组合的曲线，可以观察到对于固定的比特数，使用较小的$m$值（更少的子量化器）配合较大的$k^*$值（每个子量化器更多质心）能获得更低的量化误差。

3. 使用量化进行搜索

3.1 使用量化码计算距离

考虑查询向量$x$和数据库向量$y$，我们提出两种计算近似欧氏距离的方法。

对称距离计算（SDC）：向量$x$和$y$都由各自的质心$q(x)$和$q(y)$表示。距离$d(x,y)$通过以下方式近似：

$$\hat{d}(x, y) = d(q(x), q(y)) = \sqrt{\sum_{j=1}^m d(q_j(x), q_j(y))^2}$$

其中距离$d(c{j,i}, c{j,i'})^2$从与第$j$个子量化器相关的查找表中读取。每个查找表包含子量化器所有质心对$(i, i')$之间的平方距离，即$(k^*)^2$个平方距离。

非对称距离计算（ADC）：数据库向量$y$由$q(y)$表示，但查询$x$不被编码。距离通过以下方式近似：

$$\tilde{d}(x, y) = d(x, q(y)) = \sqrt{\sum_{j=1}^m d(u_j(x), q_j(u_j(y)))^2}$$

其中平方距离$d(uj(x), c{j,i})^2$对于$j = 1...m, i = 1...k^*$在搜索前预先计算。

图2描述：该图说明了对称和非对称距离计算的区别。左图(a)显示SDC方法，其中$x$和$y$都被量化到各自的质心，距离$d(x,y)$通过$d(q(x), q(y))$估计。右图(b)显示ADC方法，只有$y$被量化，距离通过$d(x, q(y))$估计。图中清楚地展示了ADC方法由于只量化一个向量而产生更小的误差。

3.2 距离误差分析

使用$\tilde{d}(x, y)$代替$d(x, y)$时的距离误差分析不依赖于乘积量化器的使用，对满足Lloyd最优性条件的任何量化器都有效。

距离失真通过距离上的均方距离误差（MSDE）衡量：

$$\text{MSDE}(q) = \iint (d(x, y) - \tilde{d}(x, y))^2 p(x)dx \cdot p(y)dy$$

通过三角不等式：

$$d(x, q(y)) - d(y, q(y)) \leq d(x, y) \leq d(x, q(y)) + d(y, q(y))$$

可以得到：

$$(d(x, y) - d(x, q(y)))^2 \leq d(y, q(y))^2$$

将此不等式与MSDE的定义结合，得到：

$$\text{MSDE}(q) \leq \int p(x) \left[\int d(y, q(y))^2 p(y) dy\right] dx = \text{MSE}(q)$$

这表明我们方法的距离误差在统计上由量化器的MSE界定。对于对称版本，类似的推导表明误差由$2 \cdot \text{MSE}(q)$界定。

图3描述：该图展示了在1000个SIFT向量集合中查询一个SIFT向量的典型结果。比较了SDC和ADC估计器获得的距离$d(x,y)$。使用了$m=8$和$k^*=256$（即64位码向量）。图中清晰显示ADC估计器（红色点）比SDC估计器（蓝色点）更接近对角线（真实距离），证实了ADC的优越性。

3.3 平方距离的估计器

如实验所示，使用$\hat{d}$或$\tilde{d}$的估计会导致平均低估点之间的距离。为了消除偏差，我们计算平方距离的期望值。

给定向量$y$的量化索引$q(y) = c_i$，$x$与随机变量$Y$（满足$q(Y) = q(y) = c_i$）之间的期望平方距离为：

$$\tilde{e}(x, y) = \mathbb{E}_Y[(x - Y)^2 | q(Y) = c_i]$$

$$= \int_{V_i} (x - y)^2 p(y|i) dy$$

$$= \frac{1}{p_i} \int_{V_i} (x - c_i + c_i - y)^2 p(y) dy$$

展开平方表达式并使用Lloyd条件$\int_{V_i} (y - c_i) p(y) dy = 0$，得到：

$$\tilde{e}(x, y) = \tilde{d}(x, y)^2 + \xi(q, q(y))$$

其中$\xi(q, q(y))$是与用其重构值重建$y$相关的失真。

使用乘积量化器，修正后的期望平方距离计算为：

$$\tilde{e}(x, y) = \tilde{d}(x, y)^2 + \sum_{j=1}^m \xi_j(y)$$

其中修正项$\xi_j(y) = \xi(q_j, q_j(u_j(y)))$是使用第$j$个子量化器将$u_j(y)$量化到$q_j(y)$的平均失真，可以预先学习并存储在查找表中。

图4描述：该图展示了非对称方法距离估计误差$d - \tilde{d}$的概率分布函数（PDF），在10,000个SIFT向量集合上评估，使用$m=8$和$k^*=256$。估计器$\tilde{d}$的偏差（-0.044）通过误差量化项$\xi(q, q(y))$得到纠正（偏差变为-0.002）。然而，修正后误差的方差增加：$\sigma^2(d - \tilde{e}) = 0.00155$，而$\sigma^2(d - \tilde{d}) = 0.00146$。

4. 非穷举搜索

为了避免穷举搜索，我们结合倒排文件系统与非对称距离计算（IVFADC）。

4.1 粗量化器与局部定义的乘积量化器

类似于"Video-Google"方法，使用k-means学习一个码本，产生粗量化器$q_c$。对于SIFT描述符，与$q_c$相关的质心数量$k'$通常在1,000到1,000,000之间。

除了粗量化器，我们采用类似的策略来优化向量的描述：用乘积量化器获得的码来编码残差向量：

$$r(y) = y - q_c(y)$$

向量近似为：

$$\ddot{y} = q_c(y) + q_p(y - q_c(y))$$

它由元组$(q_c(y), q_p(r(y)))$表示。粗量化器提供最重要的位，而乘积量化器码对应于最不重要的位。

图5描述：该图展示了带有非对称距离计算的倒排文件（IVFADC）索引系统的概述。顶部显示向量插入过程：向量$y$首先通过粗量化器$q_c$量化得到$q_c(y)$，然后计算残差$r(y) = y - q_c(y)$，最后用乘积量化器$q_p$编码残差得到码。底部显示搜索过程：查询$x$被分配到$w$个最近的粗质心，计算残差$r(x)$，然后在相应的倒排列表中使用预计算的距离表搜索最近邻。

4.2 索引结构

使用粗量化器实现倒排文件结构，作为列表数组$L1...L{k'}$。如果$Y$是要索引的向量数据集，与质心$c_i$相关的列表$L_i$存储集合${y \in Y : q_c(y) = c_i}$。

在倒排列表$L_i$中，对应于$y$的条目包含：

• 向量标识符
• 编码的残差$q_p(r(y))$

标识符字段是倒排文件结构带来的开销。对于描述图像的局部描述符，图像标识符可以替代向量标识符，即同一图像的所有向量具有相同的标识符。因此，20位字段足以从100万个图像数据集中识别一个图像。

4.3 搜索算法

查询向量$x$的最近邻搜索包括以下步骤：

1. 将$x$量化到码本$q_c$中的$w$个最近邻
2. 对每个子量化器$j$和每个质心$c_{j,i}$，计算平方距离$d(uj(r(x)), c{j,i})^2$
3. 计算$r(x)$与倒排列表中所有索引向量之间的平方距离，通过求和$m$个查找值
4. 基于估计距离选择$K$个最近邻

只有第3步依赖于数据库大小。与ADC相比，假设倒排列表是平衡的，需要解析约$n \cdot w/k'$个条目，因此搜索速度显著提升。

5. 实验评估

5.1 数据集

实验在两个数据集上进行：局部SIFT描述符和全局彩色GIST描述符。每个数据集有三个向量子集：学习集、数据库集和查询集。

表3：SIFT和GIST数据集总结
| 向量数据集 | SIFT | GIST |
|------------|------|------|
| 描述符维度 $d$ | 128 | 960 |
| 学习集大小 | 100,000 | 100,000 |
| 数据库集大小 | 1,000,000 | 1,000,991 |
| 查询集大小 | 10,000 | 500 |

5.2 内存与搜索精度的权衡

图6描述：该图评估了SDC和ADC估计器在SIFT数据集上的性能，展示了recall@100作为内存使用量（码长）的函数。使用了不同的参数$(k^ = 16, 64, 256, ..., 4096)$和$(m = 1, 2, 4, 8, 16)$。图中清楚显示，对于固定的比特数，使用较小数量的子量化器配合许多质心比使用许多子量化器配合较少比特要好。ADC显著优于SDC：例如，ADC使用$m=8, k^=64$可以达到与SDC使用$m=8, k^*=256$相同的精度。

图7描述：该图展示了IVFADC方法在SIFT数据集上的recall@100作为内存使用量的函数，使用$k^*=256$和不同的$m \in {1, 2, 4, 8, 16}$、$k' \in {1024, 8192}$和$w \in {1, 8, 64}$值。可以观察到recall@100强烈依赖于这些参数，如果$w$不够大，增加码长是无用的，因为未分配到查询相关的$w$个质心之一的最近邻将永远丢失。

5.3 组件分组的影响

表4：维度分组对ADC检索性能的影响（recall@100, $k^*=256$）

该表展示了不同维度分组策略的影响：

• 自然顺序：按原始顺序分组连续组件
• 随机顺序：随机分组
• 结构化顺序：将相关维度分组在一起

对于SIFT，结构化顺序意味着将相同方向的梯度bin分组；对于GIST，意味着将具有相同索引模8的维度分组。结果显示，组件的选择对性能有显著影响，使用随机顺序会导致较差的结果。

5.4 与最先进方法的比较

图8描述：该图展示了SIFT数据集上不同R值的recall@R比较。比较了SDC、ADC、IVFADC、谱哈希（SH）和汉明嵌入（HE）方法。使用了$m=8, k^*=256$（SDC/ADC）和$k'=1024$（HE和IVFADC）。所有乘积量化方法都显著优于谱哈希。IVFADC在低秩时提供了比ADC的改进，并显著优于谱哈希。

图9描述：该图展示了GIST数据集上不同R值的recall@R比较。比较了SDC、ADC、IVFADC和谱哈希方法。使用了$m=8, k^*=256$（SDC/ADC）和$k'=1024$（IVFADC）。结果模式与SIFT数据集类似，证实了方法的通用性。

图10描述：该图比较了IVFADC与FLANN在搜索质量（1-recall@1）和搜索时间之间的权衡。IVFADC方法通过短列表大小$R$（用于用$L_2$距离重排向量）以及倒排文件的两个参数$w$和$k'$（分别对应分配数量和粗质心数量）进行参数化。图显示IVFADC在大范围的操作点上优于FLANN，并且内存占用更小（IVFADC小于25MB，而FLANN需要超过250MB的RAM）。

5.5 复杂度和速度

表5：GIST数据集（500个查询）的搜索时间

该表报告了不同方法的搜索时间。IVFADC通过避免穷举搜索显著提高了性能。对于大型数据集，$k'$的较高值产生更高的搜索效率，因为搜索受益于解析更小部分的内存。

5.6 大规模实验

为了评估乘积量化方法在更大规模上的搜索效率，我们从100万张图像中提取了20亿个SIFT描述符。

图11描述：该图展示了在不断增大的数据集中SIFT描述符的搜索时间（每个查询）。比较了HE和IVFADC两种搜索方法，两者都使用相同的20,000词粗量化器、$w=1$和64位签名。IVFADC所需的额外量化步骤的成本在小数据库大小时清晰可见。对于更大的规模，与数据库向量的距离计算变得占主导地位。应用于倒排列表每个元素的处理在两种情况下大致相同。

图12描述：该图比较了IVFADC和汉明嵌入方法在Holidays数据集上的平均精度（mAP）作为干扰图像数量（最多100万）的函数。对两种方法使用了相同的粗量化器（$k'=20,000$）和单一分配策略（$w=1$），IVFADC固定$k^*=256$。IVFADC获得的增益是显著的：例如，对于100万个干扰项，使用64位签名的HE报告的mAP为0.497，而IVFADC提高到0.517。

6. 结论

我们引入了乘积量化用于近似最近邻搜索。我们的紧凑编码方案提供了欧氏距离的准确近似。此外，它与倒排文件系统结合以避免穷举搜索，从而实现高效率。我们的方法在搜索质量和内存使用之间的权衡方面显著优于现有技术。SIFT和GIST图像描述符的实验结果表现优异，表明基于我们对描述符设计的先验知识对组件进行分组进一步提高了结果。我们方法的可扩展性在20亿向量的数据集上得到了验证。

附录：数学推导

A. Lloyd最优性条件的推导

给定量化器$q$和概率分布$p(x)$，均方误差定义为：

$$\text{MSE}(q) = \int_{\mathbb{R}^D} \|x - q(x)\|^2 p(x) dx = \sum_{i=1}^k \int_{V_i} \|x - c_i\|^2 p(x) dx$$

为了最小化MSE，我们需要找到最优的划分${V_i}$和质心${c_i}$。

第一个Lloyd条件：固定质心，最优划分应该满足：

$$V_i = \{x : \|x - c_i\| \leq \|x - c_j\|, \forall j \neq i\}$$

证明：如果存在$x \in V_i$但$|x - c_j| < |x - c_i|$对某个$j \neq i$，则将$x$重新分配到$V_j$会减少MSE。

第二个Lloyd条件：固定划分，最优质心通过对$c_i$求导得到：

$$\frac{\partial}{\partial c_i} \int_{V_i} \|x - c_i\|^2 p(x) dx = -2 \int_{V_i} (x - c_i) p(x) dx = 0$$

因此：

$$c_i = \frac{\int_{V_i} x p(x) dx}{\int_{V_i} p(x) dx} = \mathbb{E}[X | X \in V_i]$$

B. 乘积量化器的MSE分解

对于乘积量化器，输入空间被分解为$m$个正交子空间。设$x = [u_1(x), ..., u_m(x)]$，其中每个$u_j(x) \in \mathbb{R}^{D^}$，$D^ = D/m$。

由于子空间是正交的，欧氏距离可以分解为：

$$\|x - q(x)\|^2 = \sum_{j=1}^m \|u_j(x) - q_j(u_j(x))\|^2$$

因此，乘积量化器的MSE为：

$$\text{MSE}(q) = \mathbb{E}_X\left[\sum_{j=1}^m \|u_j(X) - q_j(u_j(X))\|^2\right] = \sum_{j=1}^m \text{MSE}(q_j)$$

这表明总失真等于各个子量化器失真的和。

C. 非对称距离计算的误差界

给定查询$x$和数据库向量$y$，非对称距离估计为$\tilde{d}(x, y) = d(x, q(y))$。

使用三角不等式的两种形式：

$$d(x, y) \leq d(x, q(y)) + d(q(y), y)$$
$$d(x, y) \geq |d(x, q(y)) - d(q(y), y)|$$

组合得到：

$$|d(x, y) - d(x, q(y))| \leq d(y, q(y))$$

平方两边：

$$(d(x, y) - d(x, q(y)))^2 \leq d(y, q(y))^2$$

对两边取期望：

$$\mathbb{E}_{X,Y}[(d(X, Y) - d(X, q(Y)))^2] \leq \mathbb{E}_Y[d(Y, q(Y))^2] = \text{MSE}(q)$$

D. 期望平方距离估计器的推导

给定$q(y) = c_i$，我们要计算：

$$\tilde{e}(x, y) = \mathbb{E}_Y[\|x - Y\|^2 | q(Y) = c_i]$$

使用条件期望：

$$\tilde{e}(x, y) = \int_{V_i} \|x - y\|^2 p(y|q(y) = c_i) dy$$

其中$p(y|q(y) = c_i) = p(y|y \in V_i) = \frac{p(y)}{p_i}$，$p_i = P(Y \in V_i)$。

展开$|x - y|^2 = |x - c_i + c_i - y|^2$：

$$\|x - y\|^2 = \|x - c_i\|^2 + 2\langle x - c_i, c_i - y \rangle + \|c_i - y\|^2$$

对$V_i$上积分：

$$\tilde{e}(x, y) = \|x - c_i\|^2 + \frac{2}{p_i}\langle x - c_i, \int_{V_i}(c_i - y)p(y)dy \rangle + \frac{1}{p_i}\int_{V_i}\|c_i - y\|^2 p(y)dy$$

由Lloyd第二条件，$\int_{V_i}(c_i - y)p(y)dy = 0$，因此：

$$\tilde{e}(x, y) = \|x - c_i\|^2 + \xi(q, c_i) = \tilde{d}(x, y)^2 + \xi(q, c_i)$$

其中$\xi(q, c_i)$是将$V_i$中的向量量化到$c_i$的平均失真。

E. 残差向量的量化

在IVFADC中，向量$y$首先被粗量化器$q_c$量化，然后残差$r(y) = y - q_c(y)$被乘积量化器$q_p$量化。

残差的能量比原始向量小：

$$\mathbb{E}[\|r(Y)\|^2] = \mathbb{E}[\|Y - q_c(Y)\|^2] = \text{MSE}(q_c)$$

这解释了为什么量化残差比直接量化原始向量更精确。向量的最终近似为：

$$\ddot{y} = q_c(y) + q_p(r(y))$$

近似误差为：

$$\|y - \ddot{y}\| = \|r(y) - q_p(r(y))\|$$

由于残差的能量较小，这个误差通常比直接量化$y$的误差更小。

F. 计算复杂度分析

表2：不同量化器的内存使用和分配复杂度

其中HKM参数化为树高度$l$和分支因子$bf$。

对于乘积量化器，存储码本只需要$mk^D^$个浮点值，远小于显式存储所有$(k^)^m$个质心所需的$(k^)^m D$个值。这使得乘积量化器能够在内存中索引大值的$k$。