product quantization

Reading time ~2 minutes

1.介绍

计算高维向量间的欧氏距离,在许多应用中是一个基本需求。尤其是最近邻搜索问题中被广泛使用。由于维度灾难,最近邻搜索相当昂贵。在D维欧氏空间上,该问题是:在一个n维vectors的有限集合,寻找element ,可以最小化与query vector 间的距离:

…(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使用。这会抛出一些问题:如何学到密码本(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维向量映射到vector q(x)上:

其中:

  • index set 是假设是有限的:
  • reproduction values :表示centroids
  • reproduction values C的集合:称为size k的codebook

vectors映射到一个给定index i上的集合,被称为一个(Voronoi) cell,定义为:

…(2)

一个quantizer的k个cells形成了的一个划分(partition)。通过定义可知:在同一cell 上的所有vectors,可以通过相同centroid 来构建。一个quantizer的quality通常通过input vector x和它的reproduction value 间的MSE来进行测量:

…(3)

其中,是x和y的欧氏距离,是随机变量X的概率分布函数。对于一个专门的概率分布函数,等式(3)数值上使用Monte-Carlo sampling进行计算,作为在一个大数据集样本上的平均。

为了让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 得到的cell 的vector时,获得的均方失真。通过来表示一个vector被分配给centroid 的概率,它可以通过下式计算:

…(6)

注意,MSE可以通过这些quantities来获得:

…(7)

存储index value(没有进一步处理(entropy coding))的内存开销,是 bits。因此,使用一个k的2阶很方法,因为通过quantizer生成的code以binary memory的方式生成。

B. Product quantizers

假设我们考虑一个128维的vector,例如,SIFT descriptor [23]。一个quantizer会产生64-bits codes,例如,每个component只有0.5 bit,包含了的centroids。因此,使用Lloyd算法或HKM并不重要,因为所需的样本数据、以及学习该quantizer的复杂度是:k的数倍。为了表示k个centroids要存储的floating point值是不可能的

product quantization是一个高效的解决该问题的解法。它是source coding中的常用技术,允许选择要进行联合量化(quantized jointly)的components的数目(例如,24个components的groups可以使用强大的Leech lattice来量化)。

input vector x被split成m个不同的subvectors ,维度为,其中D是m的倍数。这些subvectors会使用m个不同的quantizers进行单独量化。一个给定vector x因此根据如下进行映射:

…(8)

其中:

  • 是低复杂度的quantizer,它与第j个subvector有关。
  • subquantizer 与index set 、codebook 、以及相应的reproduction values 有关。

product quantizer的reproduction通过product index set 的一个element进行标识。codebook因此被定义成Cartesian product:

…(9)

以及该set的centroid是m个subquantizers的centroid的拼接(concatenation)。从现在开始,我们假设,所有subquantizers具有相同的有限数目的reproduction values。在该case中,centroids的总数由下式给定:

…(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 对个具有的centroids执行k-means聚类的复杂度。

对codebook C显式存储效率不高。相反,我们会存储所有subquantizer的个centroids,例如:个floating points值。对一个element进行量化需要个floating point操作。表1总结了与k-means、HKM、product k-means对应所需的资源。product quantizer很明显是唯一可以被用于当k为大值时可以进行内存索引的方法。

图片名称

表1

当选择一个常数值,为了提供较好的量化属性,通常每个subvector都应具有一个可对比的energy。确保该特性的一个方法是:通过将该vector乘以一个随机正交矩阵来进行quantization。然而,对于大多数vector types,这并不是必需的,也不推荐,因为连续的components通常通过construction来关联,并可以更好地与相同的subquantizer一起被量化。由于subspaces是正交的,与product quantizer的平方失真(squared distortion)为:

…(11)

其中,是与quantizer 相关的失真(distortion)。图1展示了MSE是一个关于不同tuples的code length的函数,其中code length为,如果是2的幂。该曲线通过一个128维SIFT descriptors的集合获得,详见第V部分。你可以观察到,对于固定数目的bits,最好使用一个小数目的subquantizers以及更多centroids,要比使用许多subquantizers和更少centroids的要好。当m=1的极端情况下,product quantizer会成为一个常规的k-means codebook。

图片名称

图1

的值越高,会增加quantizer的计算开销,如表1所示。它们也会增加存储centroids()的内存使用量,当centroid look-up table不再fit cache内存时,这会进一步降低效率。在这种情况下m=1,超过16 bits来保存这样的开销可追踪将承受不起。使用通常是一个合理的选择。

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)通过近似,它使用一个product quantizer来高效获取:

…(12)

其中,是从一个与第j个subquantizer相关的lookup table中读取。每个lookup table包含了centroids pairs 间所有的squared distances,或者的squared distances。

ADC(Asymmetric distance computa)

database vector y通过q(y)表示,但query x不会被编码。距离d(x,y)通过来近似,它使用decomposition进行计算:

…(13)

其中:

  • squared distances: 是在search之前计算好的

对于最近邻搜索,我们在实际中不会计算均方根(square roots):square root函数是单调递增的,squared distances会生成相同的vector ranking。

表II总结了涉及到vector x与dataset Y中搜索k个最近邻的不同steps的复杂度。可以看到,SDC和ADC具有相同的query准备开销,它不依赖于dataset size n。当n很大时(), 大多数开销操作是公式12和等式13的求和。对于搜索k个最小elements在该表中的复杂度为:当elements是任意顺序时,对于的平均复杂度。

图片名称

表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 ,被称为“coarse quantizer”。对于SIFT descriptors,与相关的centroids数目为,通常范围为k’=1000 ~ 1,000,000。对比在第3节中使用的product quantizers的k来说较小些。

除了coarse quantizer外,我们会采用一个与[20]提出的相似的strategy,例如,一个vector的description通过一个code(由一个product quantizer获得)重定义。然而,为了解释由coarse quantizer提供的信息,例如,centroid 与一个vector y相关,product quantizer 被用于编码residual vector:

…(28)

对应于在Voronoi cell中的offset。对比vector自身,residual vector的energy很小。该vector通过下式近似:

…(29)

它通过tuple 表示。通过与“二进制表示”类比发现,coarse quantizer提供了最高有效位(most significant bits),而product quantizer的code相当于最低有效位(least significant bits)。

d(x,y)的估计值(其中x是query,y是database vector),可以通过x和间的距离 对比:

…(30)

通过定义了第j个subquantizer,我们使用以下decomposition来有效计算该estimator:

…(31)

与ADC的做法相类似,对于每个subquantizer ,在partial residual vector 所有centroids 间的距离是预先计算好并进行存储好的。

在residual vectors集合上学到的product quantizer通过一个learning set收集到。尽管该vectors被coasrse quantizer量化到不同indexes上,生成的residual vectors被用于学习一个唯一的product quantizer。我们假设:当在所有Voronoi cell上的residual的分布是边缘的时,相同的product quantizer是精准的。这可能会为该方法给出差的结果(该方法包含了learning,并为每个Voronoi cell使用一个不同的product quantizer)。然而,这在计算上开销很大,需要存储个product quantizer codebooks,例如:的浮点值,它对于的公共值来说内存过大(memory-intractable)。

B. indexing结构

我们使用coarse quantizer来实现一个inverted file结构作为一个lists数组: 。如果是到index的vector dataset,与的centroid 相关的list ,会存储集合

在inverted list ,一个entry对应于y,包含了一个vector identifier以及被编码的residual

图片名称

表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的一个子集,用于估计距离:只对应的inverted list 会被扫到。

然而,x和它的最邻近并没有被量化到相同的centroid上,而是在附近一个centroid上。为了解决该问题,我们使用多个assignment策略[29]。该query x会被分配到w个indexes上(而非单个),它对应于在的codebook中x的w个最近邻。所有相应的inverted lists都会被扫描到。多个assignment不会被应用到database vectors,因为这将增加内存使用。

图5给出了一个关于一个database是如何被index和search的总览。

Indexing一个vector y的过程

  • 1) 将y量化到
  • 2) 计算residual:
  • 3) 将量化到,对于product quantizer来说,相当于将分配给,其中
  • 4) 添加一个new entry到对应的inverted list中。它包含了vector (或image) identifier以及binary code(product quantizer的indexes)。

Searching

一个query x的最近邻包含了:

  • 1) 将x量化到在codebook 中的w个最近邻。为了简明,在下两个step,我们会通过将r(x)表示与w assignments相关的residuals。这两steps会被应用到所有的w assignments中。
  • 2) 对于每个subquantizer j和每个centroid ,计算squared distance
  • 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量化到的求和step 包含了在D维vectors间计算个距离。假设inverted lists是balanced,那么需要解析个entries。因此,search要比ADC更快,下一节将介绍。

5. NN Search的评估

分析SDC、ADC、IVFADC的参数影响。我们的方法会对比三个SOTA方法:spectral hashing、hamming embedding、FLANN。最终评估复杂度和加速。

参考

PAL position bias介绍

华为在《PAL: a position-bias aware learning framework for CTR prediction in live recommender systems》提出了一种解决position-bias方法。# 摘要在推荐系统中精准预测CTR...… Continue reading

facebook DLRM介绍

Published on November 01, 2019

feedback loops介绍

Published on October 28, 2019