1.介绍
计算高维向量间的欧氏距离，在许多应用中是一个基本需求。尤其是最近邻搜索问题中被广泛使用。由于维度灾难，最近邻搜索相当昂贵。在D维欧氏空间\(R^D\)上，该问题是：在一个n维vectors的有限集合\(Y \subset R^D\)，寻找element \(NN(x)\)，可以最小化与query vector \(x \in R^D\)间的距离：
\[NN(x) = \underset{y \in Y}{argmin} \ d(x,y)\]…(1)
许多多维索引方法，比如KD-tree或其它branch&bound技术，被提出来减小搜索时间。然而，对于高维空间，发现这样的方法比起brute-force距离计算（复杂度O(nD)）并没有更高效多少。
一些算法文献通过执行ANN（近似最近邻）搜索来解决该问题。这些算法的关键点是：”只”寻找具有较高概率的NN，来替代概率1. 大多数研究都在欧氏距离上，尽量最近有研究在其它metrics上提出[10]。在本paper中，我们只考虑欧氏距离，它可以适用于许多应用。在本case中，一个最流行的ANN算法是欧氏局部敏感哈希算法（E2LSH），它在有限假设的搜索质量上提供了理论保证。它已经被成功用于local descriptors和3D object indexing。然而，对于真实数据，LSH还是通过启发法来执行，会利用vectors的分布。这些方法包括：randomized KD-trees、hierarchical k-means，这两种方法在FLANN选择算法上有实现。
ANN通常会基于search quality和efficiency间的trade-off来进行比较。然而，该trade-off并不能说明indexing结构的内存需要。在E2LSH的case上，内存的使用要比original vectors更高。另外，E2LSH和FLANN需要基于exact L2距离（如果访问速度很重要，它需要在主存中存储indexed vectros）来执行一个final re-ranking step。该constraint会严重限制可被这些算法处理的vectors的数目。最近，研究者们提出了受限内存使用的方法。该问题的关键是涉及大量数据，例如：在大规模场景识别[17]中，需要索引数百万到数十亿的图片。[17]中通过单个global GIST descriptor来表示一个图片，该descriptor可以被映射到一个short binary code上。当使用无监督时，会学到这样的mapping，以便在embedded space中由hamming距离定义的neighborhood可以影响在原features的欧氏空间中的neighborhood。欧氏最近邻的搜索接着被近似成：通过codes间的hamming距离的最近邻搜索。在[19]中，spectral hashing（SH）的效果要好于由RBM、boosting和LSH生成的binary codes。相似的，Hamming embedding方法[20]会在Bag-of-features的图片搜索框架中使用一个binary signature来重新定义quantized SIFT或GIST descriptors。
在本paper中，我们使用quantization来构建short codes。目标是使用vector-to-centroid distances来估计距离，例如：query vector是没有被量化的（quantized），codes只被分配给database vectors。这会减小quantization noise，进而提升搜索质量。为了获得精确的距离，quantization error必须被限制。因此，centroids的总数目k必须足够大，
例如：对于64-bit codes使用\(k=2^{64}\)。这会抛出一些问题：如何学到密码本（codebook）以及分配一个vector？
- 首先，要学到该quantizer所需的样本量很大，比如：k的许多倍。
- 第二，该算法本身的复杂度很高。
- 最后，地球上的计算机内存量不足以存储表示centroids的floating point。
hierarchical k-means(HKM)提升了learning stage、以及assignment过程的efficiency。然而，前面提到的限制仍存在，特别是：内存使用以及learning set的size。另一个可能是scalar quantizers，但他们提供了更差的quantization error特性。对于均匀向量分布，lattice quantizers提供了更好的quantization特性，但该条件在现实vectors中很难满足。特别的，这些quantizers执行在indexing任务上要比k-means更差。在本paper中，我们只关注product quantizers。据我们所知，这样的semi-structured quantizer从没有在任何最近邻搜索方法中考虑。
我们的方法有两个优点：
- 首先，可能的distances的数目要比competing Hamming embedding方法要更高，因为在这些技术中使用的Hamming space只允许少量distinct distance。
- 第二，作为byproduct方法，我们可以获得一个expected squared distance的估计，它对于e-radius搜索或者lowe’s distance ratio criterion来说是必需的。
在[20]使用Hamming space的动机是，高效计算距离。注意，然而，计算Hamming距离的最快方法之一，包含了使用table lookups。我们的方法会使用相同数目的table lookups，来产生相当的效率。
对于非常大的数据集，对所有codes与query vector进行遍历比较开销相当大。因此，引入一个modified inverted file结构来快速访问最相关vectors。会使用一个粗粒度量化器(coarse quantizer)来实现该inverted file结构。其中，对应于一个cluster(index)的vectors会被存储在一个相关列表中。在该list中的vectors通过short codes（通过product quantizer计算得来）来表示，被用于编码对应于聚类中心的其它vector。
我们的方法的关注点是：在两种vectors上进行验证，称为local SIFT和global GIST descriptors。通过SOTA对比，我们的方法要好于之前的技术（比如：SH， Hamming embedding以及FLANN）。
2.背景知识：quantization、product quantizer
关于vector quantization有大量文献提供。在本节，我们聚焦在相关概念上。
A. Vector quantization
Quantization是一个分解性过程（destructive process），它在信息论中被大量研究。它的目标是，减小representation space的基数（cardinality），特别是当输入数据是real-valued时。
正式的：一个quantizer是一个函数q，它将一个D维向量\(x \in R^D\)映射到vector q(x)上：
\[q(x) \in C = \lbrace c_i; i \in I \rbrace\]其中：
- index set \(I\)是假设是有限的：\(I=0, \cdots, k-1\)。
- reproduction values \(c_i\)：表示centroids。
- reproduction values C的集合：称为size k的codebook。
vectors映射到一个给定index i上的集合\(V_i\)，被称为一个(Voronoi) cell，定义为：
\[V_i \triangleq \lbrace x \in R^D : q(x)=c_i \rbrace\]…(2)
一个quantizer的k个cells形成了\(R^D\)的一个划分（partition）。通过定义可知：在同一cell \(V_i\)上的所有vectors，可以通过相同centroid \(c_i\)来构建。一个quantizer的quality通常通过input vector x和它的reproduction value \(q(x)\)间的MSE来进行测量：
\[MSE(q) = E_x[d(q(x), x)^2] = \int p(x) d(q(x),x)^2 dx\]…(3)
其中，\(d(x,y)=\| x-y \|\)是x和y的欧氏距离，\(p(x)\)是随机变量X的概率分布函数。对于一个专门的概率分布函数，等式(3)数值上使用Monte-Carlo sampling进行计算，作为在一个大数据集样本\(\|q(x)-x\|^2\)上的平均。
为了让quantizer是最优的，必须满足L1oyd optimality condition的两个特性。
- 1. vector x必须被quantized到它最近的codebook centroid，根据欧氏距离：
…(4)
作为结果，cells通过超参数来限定。
- 2. 重构值(reconstruction value)必须是在Voronoi cell上vectors的期望值：
…(5)
Lloy quantizer，它对应于k-means cluster算法，通过迭代式分配一个training set的vectors给centroids、并将这些已分配vectors的centroids进行re-estimating的方式来寻找一个接近最优的codebook。
下面，我们会假设两个Lloyd conditions成立，正如我们使用k-means来学习该quantizer。注意，然而，k-means只会根据quantization error来找一个local optimum。
下面会使用到的另一个quantity是：当构建一个由通过相应的centroid \(c_i\)得到的cell \(V_i\)的vector时，获得的均方失真\(e(q,c_i)\)。通过\(p_i=P(q(x)=c_i)\)来表示一个vector被分配给centroid \(c_i\)的概率，它可以通过下式计算：
\[e(q,c_i) = \frac{1}{p_i} \int_{v_i} d(x,q(x))^2 p(x) dx\]…(6)
注意，MSE可以通过这些quantities来获得：
\[MSE(q) = \sum\limits_{i \in I} p_i e(q, c_i)\]…(7)
存储index value（没有进一步处理（entropy coding））的内存开销，是\(log_2 k\) bits。因此，使用一个k的2阶很方法，因为通过quantizer生成的code以binary memory的方式生成。
B. Product quantizers
假设我们考虑一个128维的vector，例如，SIFT descriptor [23]。一个quantizer会产生64-bits codes，例如，每个component只有0.5 bit，包含了\(k=2^{64}\)的centroids。因此，使用Lloyd算法或HKM并不重要，因为所需的样本数据、以及学习该quantizer的复杂度是：k的数倍。为了表示k个centroids要存储\(D \times k\)的floating point值是不可能的。
product quantization是一个高效的解决该问题的解法。它是source coding中的常用技术，允许选择要进行联合量化(quantized jointly)的components的数目（例如，24个components的groups可以使用强大的Leech lattice来量化）。
input vector x被split成m个不同的subvectors \(u_j, 1 \leq j \leq m\)，维度为\(D^* = D/m\)，其中D是m的倍数。这些subvectors会使用m个不同的quantizers进行单独量化。一个给定vector x因此根据如下进行映射：
\[\underbrace{x_1, \cdots, x_{D^*}}_{u_1(x)}, \cdots, \underbrace{x_{D-D^*+1}, \cdots, x_D}_{u_m(x)} \rightarrow q_1(u_1(x)), \cdots, q_m(u_m(x))\]…(8)
其中：
- \(q_j\)是低复杂度的quantizer，它与第j个subvector有关。
- subquantizer \(q_j\)与index set \(I_j\)、codebook \(C_j\)、以及相应的reproduction values \(c_j,i\)有关。
product quantizer的reproduction通过product index set \(I=I_1 \times \cdots \times I_m\)的一个element进行标识。codebook因此被定义成Cartesian product：
\[C = C_1 \times \cdots \times C_m\]…(9)
以及该set的centroid是m个subquantizers的centroid的拼接（concatenation）。从现在开始，我们假设，所有subquantizers具有相同的有限数目\(k^*\)的reproduction values。在该case中，centroids的总数由下式给定：
\[k = (k^*)^m\]…(10)
注意：在极端情况下(m=D)，一个vector x的所有components是被完全独立量化的。这时，product quantizer就变成了一个scalar quantizer。其中，与每个component有关的quantization function是不同的。
一个product quantizer的力量是：使用多个centroids的小集合（它们与subquantizers有关）来生成一个更大的centroids集合。当使用Lloyd算法学习该subquantizers时，会使用有限数目的vectors，在某种程度上，codebook仍会采用数据分布来表示。学习该quantizer的复杂度为： m X 对\(k^*\)个具有\(D^*\)的centroids执行k-means聚类的复杂度。
对codebook C显式存储效率不高。相反，我们会存储所有subquantizer的\(m \times k^*\)个centroids，例如：\(m D^* k^*=k^* D\)个floating points值。对一个element进行量化需要\(k^* D\)个floating point操作。表1总结了与k-means、HKM、product k-means对应所需的资源。product quantizer很明显是唯一可以被用于当k为大值时可以进行内存索引的方法。
表1
当选择一个常数值\(k^*\)，为了提供较好的量化属性，通常每个subvector都应具有一个可对比的energy。确保该特性的一个方法是：通过将该vector乘以一个随机正交矩阵来进行quantization。然而，对于大多数vector types，这并不是必需的，也不推荐，因为连续的components通常通过construction来关联，并可以更好地与相同的subquantizer一起被量化。由于subspaces是正交的，与product quantizer的平方失真（squared distortion）为：
\[MSE(q) = \sum\limits_j MSE(q_j)\]…(11)
其中，\(MSE(q_j)\)是与quantizer \(q_j\)相关的失真（distortion）。图1展示了MSE是一个关于不同\((m, k^*)\)tuples的code length的函数，其中code length为\(l = m log_2 k^*\)，如果\(k^*\)是2的幂。该曲线通过一个128维SIFT descriptors的集合获得，详见第V部分。你可以观察到，对于固定数目的bits，最好使用一个小数目的subquantizers以及更多centroids，要比使用许多subquantizers和更少centroids的要好。当m=1的极端情况下，product quantizer会成为一个常规的k-means codebook。
图1
\(k^*\)的值越高，会增加quantizer的计算开销，如表1所示。它们也会增加存储centroids（\(k^* \times D floating point值\)）的内存使用量，当centroid look-up table不再fit cache内存时，这会进一步降低效率。在这种情况下m=1，超过16 bits来保存这样的开销可追踪将承受不起。使用\(k^*=256\)和\(m=8\)通常是一个合理的选择。
3.使用quantization进行搜索
最近邻搜索依赖于query vector与database vectors间的distances，或者squared distances。这节引入的方法会使用source coding技术的精髓，基于quantization indices的vectors进行比较。我们首先解释了被用于计算distances的product quantizer性质。接着我们提供了一个在distance estimation error上的统计边界，并提出了一个refined estimator来计算squared Euclidean distance。
A.使用quantized codes来计算distances
假设我们考虑query vector x和database vector y。我们提出两种方法来计算它们间的近似欧氏距离：对称法（symmetric）和非对称法（asymmetric）。见图2.
图2 sym和asym的距离计算。对于左图，距离d(x,y)通过d(q(x),q(y))来估计；对于右图，距离d(x,y)通过d(x,q(y))来估计。通常，距离上的MSE受限于quantization error
SDC（Symmetric distance computation）：
vectors x和y通过它们各自的centroids q(x)和q(y)来表示。距离d(x,y)通过\(d(x,y) \triangleq d(q(x), q(y))\)近似，它使用一个product quantizer来高效获取：
\[\hat{d}(x,y) = d(q(x), q(y)) = \sqrt{ \sum\limits_j d(q_j(x), q_j(y))^2}\]…(12)
其中，\(d(c_{j,i}, c_{j,i'})^2\)是从一个与第j个subquantizer相关的lookup table中读取。每个lookup table包含了centroids pairs \((i,i')\)间所有的squared distances，或者\((k^*)^2\)的squared distances。
ADC（Asymmetric distance computa）
database vector y通过q(y)表示，但query x不会被编码。距离d(x,y)通过\(\hat{d}(x,y) \triangleq d(x,q(y))\)来近似，它使用decomposition进行计算：
\[\hat{d}(x,y) = d(x,q(y)) = \sqrt{ \sum\limits_y d(u_j(x), q_j(u_j(y)))^2}\]…(13)
其中：
- squared distances： \(d(u_j(x), c_{j,i})^2: j=1 \cdots m, i= 1 \cdots k^*\)，是在search之前计算好的。
对于最近邻搜索，我们在实际中不会计算均方根（square roots）：square root函数是单调递增的，squared distances会生成相同的vector ranking。
表II总结了涉及到vector x与dataset Y中搜索k个最近邻的不同steps的复杂度。可以看到，SDC和ADC具有相同的query准备开销，它不依赖于dataset size n。当n很大时（\(n > k^* D^*\)）， 大多数开销操作是公式12和等式13的求和。对于搜索k个最小elements在该表中的复杂度为：当elements是任意顺序时，对于\(n >> k\)的平均复杂度。
表2
SDC比ADC好的一个优点是：限制与queries相关的内存使用量，因为query vector通过一个code定义。这在大多数情况没啥太大意义，因而你可以使用一个asym版本，它对于一个相似复杂度可以获得一个更低distance distortion。后续部分我们主要关注ADC。
4.非穷举搜索（non-exhaustive search）
使用PQ的最近邻搜索很快（对于每个距离计算，只需要m个加法），并且可以极大减小内存需求。另外，该search是穷举（exhaustive）的。该方法在global image description的内容上仍然是可扩展的。然而，如果每张图片通过一个local descriptors集合描述，穷举搜索是禁止的，因为我们需要检索数十亿descriptors并执行多个queries。
为了避免穷举搜索，我们会组合一个IVF系统（inverted file system），并使用asynmmetric distance computation（IVFADC）。一个inverted file会对对descriptors进行量化，并在相应的lists中存储图片索引，见图5的“coarse quantizer”。这会允许快速访问图片索引的一小片，这对于非常大规模的搜索是很成功的[26]。除了只存储图片索引外，我们会为每个descriptor添加一个small code，这在[20]中首次这样做。这里，我们会使用一个product quantizer来对vector和它相应的coarse centroid间的不同之处进行编码，见图5。该方法可以极大加速search，每个descriptor只需很少的额外bits/bytes开销。再者，它对search accuracy的提升很微小，因为对残差（residual）进行编码要比对vector自身编码更精准。
图5
A.Coarse quantizer，局部定义了product quantizer
与“Video-Google”[26]方法相似，通过使用k-means学到一个codebook，这会带来一个quantizer \(q_c\)，被称为“coarse quantizer”。对于SIFT descriptors，与\(q_c\)相关的centroids数目为\(k'\)，通常范围为k’=1000 ~ 1,000,000。对比在第3节中使用的product quantizers的k来说较小些。
除了coarse quantizer外，我们会采用一个与[20]提出的相似的strategy，例如，一个vector的description通过一个code（由一个product quantizer获得）重定义。然而，为了解释由coarse quantizer提供的信息，例如，centroid \(q_c(y)\)与一个vector y相关，product quantizer \(q_p\)被用于编码residual vector：
\[r(y) = y - q_c(y)\]…(28)
对应于在Voronoi cell中的offset。对比vector自身，residual vector的energy很小。该vector通过下式近似：
\[\ddot{y} \triangleq q_c(y) + q_p (y - q_c(y))\]…(29)
它通过tuple \((q_c(y), q_p(r(y)))\)表示。通过与“二进制表示”类比发现，coarse quantizer提供了最高有效位（most significant bits），而product quantizer的code相当于最低有效位（least significant bits）。
d(x,y)的估计值（其中x是query，y是database vector），可以通过x和\(\ddot{y}\)间的距离 \(\ddot{y}(x,y)\)对比：
\[\ddot{d}(x,y) = d(x,\ddot{y}) = d(x-q_c(y), q_p(y-q_c(y)))\]…(30)
通过\(q_{p_j}\)定义了第j个subquantizer，我们使用以下decomposition来有效计算该estimator：
\[\ddot{d}(x,y)^2 = \sum\limits_j d(u_j(x - q_c(y)), q_{p_j}(u_j(y-q_c(y))))^2\]…(31)
与ADC的做法相类似，对于每个subquantizer \(q_{p_j}\)，在partial residual vector \(u_j(x-q_c(y))\)与\(q_{p_j}\)所有centroids \(c_{j,i}\)间的距离是预先计算好并进行存储好的。
在residual vectors集合上学到的product quantizer通过一个learning set收集到。尽管该vectors被coasrse quantizer量化到不同indexes上，生成的residual vectors被用于学习一个唯一的product quantizer。我们假设：当在所有Voronoi cell上的residual的分布是边缘的时，相同的product quantizer是精准的。这可能会为该方法给出差的结果（该方法包含了learning，并为每个Voronoi cell使用一个不同的product quantizer）。然而，这在计算上开销很大，需要存储\(k'\)个product quantizer codebooks，例如：\(k' \times d \times k^*\)的浮点值，它对于\(k'\)的公共值来说内存过大(memory-intractable)。
B. indexing结构
我们使用coarse quantizer来实现一个inverted file结构作为一个lists数组： \(L_1 \cdots L_{k'}\)。如果\(y\)是到index的vector dataset，与\(q_c\)的centroid \(c_i\)相关的list \(L_i\)，会存储集合\(\lbrace y \in Y: q_c(y) = c_i \rbrace\)。
在inverted list \(L_i\)，一个entry对应于y，包含了一个vector identifier以及被编码的residual \(q_p(r(y))\)：
表3
由于intered file结构，identifier字段是overhead。依赖于要存储的vectors的特性，identifier不必是唯一的。例如，为了通过local descriptors来描述图片，image identifiers可以替代vector identifiers，例如，所有相同图片的vectors具有相同的identifier。因此，一个20-bit field足够标识来自100w数据集中的一个图片。该内存开销可以使用index压缩进一步减小，它可以将存储该identifier平均开销减小到8bits，取决于参数。注意，一些几何信息可以被插入到该entry中，如[20]中提出的。
C. Search算法
该inverted file是非穷举（non-exhaustive）版本的核心。当搜索一个vector x的最近邻时，inverted file提供了Y的一个子集，用于估计距离：只\(q_c(x)\)对应的inverted list \(L_i\)会被扫到。
然而，x和它的最邻近并没有被量化到相同的centroid上，而是在附近一个centroid上。为了解决该问题，我们使用多个assignment策略[29]。该query x会被分配到w个indexes上（而非单个），它对应于在\(q_c\)的codebook中x的w个最近邻。所有相应的inverted lists都会被扫描到。多个assignment不会被应用到database vectors，因为这将增加内存使用。
图5给出了一个关于一个database是如何被index和search的总览。
Indexing一个vector y的过程
- 1) 将y量化到\(q_c(y)\)
- 2) 计算residual：\(r(y) = y - q_c(y)\)
- 3) 将\(r(y)\)量化到\(q_p(r(y))\)，对于product quantizer来说，相当于将\(u_j(y)\)分配给\(q_j(u_j(y))\)，其中\(j=1 \cdots m\)
- 4) 添加一个new entry到\(q_c(y)\)对应的inverted list中。它包含了vector (或image) identifier以及binary code（product quantizer的indexes）。
Searching
一个query x的最近邻包含了：
- 1) 将x量化到在codebook \(q_c\)中的w个最近邻。为了简明，在下两个step，我们会通过将r(x)表示与w assignments相关的residuals。这两steps会被应用到所有的w assignments中。
- 2) 对于每个subquantizer j和每个centroid \(c_{j,i}\)，计算squared distance \(d(u_j(r(x)), c_{j,i})^2\)
- 3) 计算在r(x)间的squared distance，以及inverted list的所有indexed vectors。使用在前一step计算的subvector-to-centroid distances，这包含了对m个looked-up values求和；
- 4) 基于estimated distances选择x的K个最近邻。这可以通过维护一个固定容量的Maxheap结构来高效实现，它可以存储K个最小值。在每次距离计算后，只有point identifier被添加到该结构，如果它的距离在Maxheap的最大距离之下。
只有step 3依赖于database size。通过与ADC进行对比，将x量化到\(q_c(x)\)的求和step 包含了在D维vectors间计算\(k'\)个距离。假设inverted lists是balanced，那么需要解析\(n \times w/ k'\)个entries。因此，search要比ADC更快，下一节将介绍。
5. NN Search的评估
分析SDC、ADC、IVFADC的参数影响。我们的方法会对比三个SOTA方法：spectral hashing、hamming embedding、FLANN。最终评估复杂度和加速。
略