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。最终评估复杂度和加速。
略