多码本量化（MCQ）在高维空间中的搜索和压缩表示的研究

LSQ++：多码本量化1999年10月10日，第一届中国国际航空航天博览会，中国航空工业协会.Hoos1、3和James J.小1{julm,zakhmi,hoos,little}@cs.ubc.ca1英属哥伦比亚大学（UBC），加拿大2Uber ATG，多伦多，加拿大3Leiden Institute of Advanced Computer Science（LIACS），Leiden，Netherlands抽象。多码本量化（MCQ）是在多个基中的离散条目方面尽可能准确地表达一组向量的任务。MCQ的工作主要集中在降低量化误差，从而提高距离估计和召回的视觉描述符在一个固定的内存预算的基准。然而，在这一领域的最新研究和方法很难相互比较，因为它们使用不同的数据集，不同的协议，也许最重要的是，不同的计算预算。在这项工作中，我们首先基准一系列的MCQ基线在平等的基础上我们观察到，局部搜索量化（LSQ）在实践中比它的竞争对手快得多，但不是在所有情况下最准确的方法。然后，我们介绍了两个新的改进，使LSQ(i)更准确和（ii）更快。这些改进易于实现，并定义了MCQ的新技术水平。1介绍这项工作的重点是多码本量化（MCQ），一种类似于k均值聚类的矢量压缩方法，其中聚类中心来自多个码本中的条目的组合组合。用于非常大规模的近似最近邻（ANN）搜索的现代系统通常依赖于列出候选者的数据结构，然后使用从MCQ的变体获得的压缩表示进行搜索[5，16，17，32]。用于在高维空间中进行高效大规模搜索的系统对于机器学习和计算机视觉中的突出问题具有重要应用例如，Mussman et al. [24]使用Gumbel变量来随机地per-turb最近邻查询，并加速对数线性模型中的学习和推理。 Douze等人 [11]使用通过MCQ构建的大规模相似性图来改善深度“低拍摄”模型中的学习。 Guo等人[14]使用基于MCQ的系统在最大内积搜索（MIPS）中实现最先进的性能，并加速大规模推荐系统。最后，Blalock和Guttag [7]使用MCQ来减少内存使用并加速大规模数据挖掘应用程序。2J. Martinez，S. Zakhmi，H. H. Hoos和J. J. 小MCQ是对近似给定数据集的两个潜在变量的优化问题：码本和代码（即，将数据分配给那些码本）。这种近似的误差为ANN和MIPS中的欧氏距离和点积近似因此，找到实现低误差解决方案的优化方法对于提高MCQ应用的性能至关重要在相似性搜索中，我们的目标通常是处理非常大的数据集，因此它重要的是，优化技术可以优雅地扩展IVF将数据集划分为K个不相交的单元，并为每个子集学习量化器。通常情况下，K∈ {212， 213}，因此需要运行训练方法4096− 8 192次。如果一个方法需要一个小时来运行，那么一个人必须等待大约6- 12个月才能完成训练。另一方面，如果一个方法的运行时间为1分钟，那么总的等待时间将减少到大约3- 6天。[4]不幸的是，在最近的MCQ工作中，运行时间通常没有报告。在这里，我们专注于表征最近的MCQ方法的运行时间与准确性的权衡，并介绍了新的改进，在速度和准确性LSQ，一个国家的最先进的MCQ方法。问题表述。MCQ是找到使给定数据集X上的量化误差最小化的一组码B和（多个）码本C的任务。我们的目标是确定minX−CB2，（1）C、B、F其中X ∈ Rd×n包含n个d维向量，C =[C1，C2，. . . ，Cm] ∈Rd×mh由m个子码本Ci∈Rd×h组成，每个子码本具有d维和h个条目。最后，B =[bl，b2，. . . ，bn] ∈{0，1}mh×n包含n个二进制码，每个二进制码具有m个条目bi，j∈ {0，1}h，它们从不同的码本bi=[bi，1，bi，2，.. . . ，bi，m];换句话说，bi，j0= 1且bi，j1= 1。MCQ对于大规模ANN搜索是有用的，因为在这种表示中，Euclide和Σd在quervect或q和abasvect或accd之间进行交换xi≈xi=Mj=1 可以使用以下展开式来2 2Σm2q−x（二）j=1当搜索最近的邻居时，第一项可以被忽略，因为它对于所有数据库向量是恒定的;可以利用预先计算的点积表中的M个查找来计算第二项，并且通常使用一个额外的码本来量化第三（标量）项。注意，当MCQ用于[4]虽然在体外受精中，每个细胞都可以并行学习，但可以对整体计算进行类似于我们的论证。计算时间意味着能量，意味着金钱。LSQ++：更快更准确的多码本量化3近似点积（例如，在MIPS中）或卷积中，不需要存储编码向量的范数，并且可以使用全部存储器预算来提高近似的质量我们通常设置h= 256 [3，12，17，21，27，34]，这意味着可以使用8位来存储码本中的每个索引因此，如果我们使用m={ 7， 15}个码本，并且留出额外的表用于存储具有h= 256个条目，每个向量使用的存储器仅为64（分别128）位。2相关工作MCQ的早期工作采用正交码本[12，17，26]，这可以考虑简化问题并导致非常可扩展的解决方案，但以牺牲精度为代价。最近的工作集中在使用非正交码本，这增加了准确性，但也导致增加的计算成本，阻碍了它们的更广泛的采用。例如，最近发布的FAISS库5[18]仅实现正交MCQ技术。在这项工作中，我们的目标是更好地表征和理解MCQ的最新工作，目标是加速和提高非正交MCQ技术的性能。非正交MCQ Chen等人 [9]介绍了MCQ的非正交码本，并提出了残差矢量量化（RVQ），这是一种贪婪优化方法，以顺序方式在每个码本上运行k均值后来，Ai等人 [1]和Martinez等人 [22]分别独立提出了增强的RVQ和RVQ。堆叠量化器（SQ）是RVQ的改进，其获得较低的量化误差，但保持相同的编码复杂度。Babenko和Lempitsky [3]提出了加性量化（AQ），其使用类似期望最大化（EM）的方法进行优化。作者使用波束搜索更新的代码，和一个共轭梯度法的码本更新步骤。虽然不知道RVQ，本文已证明，由于其见解和适当的表征，在非正交MCQ中出现的硬后来，Martinez等人。 [21]引入了局部搜索量化（LSQ），这是一种基于迭代局部搜索[19]的编码方法，具有迭代条件模式（ICM），它改善了AQ的波束搜索方法的准确度与计算权衡，导致整体更高的召回率。它由OPQ和一个更简单的优化树量化（OTQ）组成[4]。Zhang等人。 [34]提出了复合量化（CQ），它最大限度地减少了量化误差，但也惩罚了交叉码本项与（也是潜在的）常数的偏差该方法也是类似EM的，作者使用ICM进行编码步骤，并使用L-BFGS [25]求解器进行码本更新步骤。初始化由PQ和随后的无约束MCQ组成（表达式1）。最后，Ozan等人。 [27]引入了竞争量化（CompQ），这是一种使用随机梯度下降（SGD）更新码本的5https://github.com/facebookresearch/faiss4J. Martinez，S. Zakhmi，H. H. Hoos和J. J. 小表1.使用64位的SIFT1M上的CQ和LSQ之间的比较。培训Init + train基本编码总计R@1CQ [34]（C++）碱基组4.5hCQ [34]（C++）learn set42 m 10 s42.2 m 0.162LSQ [21]（Julia，C++） learn set9.1 m4.35 m13.5 m 0.294并且在搜索空间内使用波束搜索来更新代码，该搜索空间的大小由权衡精度和计算的超参数控制。3性能比较评价虽然最近的工作使用了不同的实验设置，但幸运的是，所有研究都报告了64位SIFT1M数据集的结果。首先，我们聚焦 比较在该数据集上报告最佳结果的三种方法：CQ [34]（R@1，0.290）、LSQ [21]（R@1，0.298）和CompQ [27]（R@1，0.298）0.352）。我们在一台配备8核i7- 7700 K CPU（4.20 GHz）、32 GB RAM和NVIDIA Titan Xp GPU的台式机上测量所有时间。LSQ与复合量化（CQ）。对于LSQ，我们使用Martinez和Clement， 6在Julia [6]中编写的公开可用的实现作为起点。对于CQ，我们使用最近发布的Zhang7实现。此版本是用多线程C++编写的，并使用了高度优化的库MKL（用于矩阵运算）和libLBFGS（用于码本更新）。我们让CQ使用m= 8个码本，并且LSQ使用m= 7个码本，加上用于数据库范数的额外码本这意味着这两个方法具有相同的查询时间和使用相同的内存量。我们运行这两个方法30次迭代，并使用它们各自的代码版本中提供的所有默认超参数。为了使比较更加公平，我们使用OpenMP多线程将这些方法是从Julia调用的，其余代码保持不变。Zhang等人 [34]在SIFT 1M上报告的结果是在基本集上训练的。SIFT1M具有学习集，并且更常见的协议是专门在学习集[1，3，9，12，17，21，22，26，27，35]上学习模型参数。因此，我们还运行将其参数学习限制到学习集的方法我们在表1中报告了我们的实验结果。当CQ在基本集上训练时，LSQ的召回率略高于CQ，但LSQ的总体运行时间快20倍。当我们在学习集上训练CQ时，CQ的运行时间急剧减少，但学习的参数不能很好地推广到基集（R@1为0.162）。LabelMe22K和MNIST数据集6https://github.com/una-dinosauria/local-search-quantization7https://github.com/hellozting/CompositeQuantizationLSQ++：更快更准确的多码本量化5表2.使用64位的SIFT 1M上CompQ和LSQ之间的比较。Iters Init Training Base encoding TotalR@1 CompQ [27]（C++）250LSQ [21]（Julia，C++）25 2.6 m 6.34 m5.8米（32米）15.2 m 0.340LSQ [21]（Julia，CUDA）25 1.1 m 2.8 m 29 s（32 iters）4.4 m 0.340（传统上没有学习分区），我们观察到LSQ始终比CQ实现更高的召回率，运行时间大约快10倍。从这些结果，我们得出结论，LSQ更快，更准确，更采样效率（即它需要比CQ更少的训练数据）LSQ与竞争性量化（CompQ）。由于没有公开的实施CompQ，我们试图重现报告的结果，适度的成功。我们还没有，例如，能够重现的文件中报告的变换编码初始化，而是使用RVQ，据报道，以实现稍差的结果。我们使用32的波束搜索宽度获得了0.346的R@1，并且训练了250个历元（最佳报告结果的参数回忆率的微小差异可能归因于我们不同的初始化。然而，在我们这边进行实验的最大障碍是我们用Julia编写的CompQ实现，每个epoch运行大约需要40分钟。这意味着我们在64位SIFT 1M上的实验花了将近一周的时间才完成。我们联系了CompQ的作者，他们提到使用了一个多线程的C++实现和固定内存，一个ad-hoc排序实现，以及对线程的特殊处理。它们的实现需要每个epoch 551秒，或大约38小时（1. 5天），在配备10核XeonE5 2650 v3@2.3 GHz CPU的台式机上总共运行250个epoch。我们使用多线程C++实现比较CompQ和LSQ（与表1相同）。我们还总共使用m= 8个码本，其控制关于CompQ的查询时间和存储器使用。我们总共训练了25次迭代，并再次使用LSQ的所有默认参数LSQ和CompQ位于并行性频谱的相反两侧：CompQ使用随机梯度下降（SGD），批量大小为1，因此主要是顺序的，而LSQ是类似EM的，因此非常适合并行化。这意味着CompQ不太可能从GPU实现中受益，因为这些实现需要相当大的批量大小来提供比CPU更高的吞吐量（事实上，使用大批量大小来加速使用SGD的大型深度神经网络的训练是一个活跃的研究领域[13，29]）。为了进一步探索这种算法权衡的后果，我们使用了LSQ编码的公开可用CUDA实现[23]来加速训练和基础处理。我们还在CUDA中实现了OTQ编码我们在表2中报告了我们的实验结果。我们的LSQ的C++实现比CompQ快约150倍，当使用GPU时，LSQ6J. Martinez，S. Zakhmi，H. H. Hoos和J. J. 小实现了CompQ的大约500倍加速。然而，LSQ的召回落后于CompQ 0.012。对CompQ的进一步研究可能会集中在寻找增加其批量大小的方法，以便它可以利用现代GPU。改善LSQ：Desiderata。根据这些结果，我们建议采用以下标准来改善LSQ：(a) 首先，我们想让LSQ更准确，这样它就可以缩小与CompQ在召回方面的差距（理想情况下，超过CompQ）(b) 其次，我们希望保持LSQ的并行性，因为它是一个这是一个独特的特点，使其在实践中快速。(c) 最后，由于LSQ比它的竞争对手更快，我们希望找到一种方法来权衡运行时间和准确性。为了使这种折衷在实践中更有吸引力，我们还希望减少LSQ接下来，我们提出了满足所有这些标准的LSQ的改进。4通过快速码本更新在使用GPU对LSQ进行基准测试时，我们注意到码本更新步骤是LSQ中计算成本最高的部分这在某种程度上是不直观的，因为编码在历史上被识别为MCQ中的瓶颈[3，21]。然而，最近的硬件和算法改进颠覆了这一想法。具体地，在具有m= 8个码本和25次迭代的LSQ的2.8分钟训练时间中（表2的最后一行），2.34分钟的 用于更新码本C。因此，减少码本更新步骤的运行时间将显著减少LSQ的总运行时间。形式上，码本更新步骤相当于确定minX−CB2;（3）CF用于该步骤的当前技术水平的方法最初由Babenko和Lempitsky [3]提出，他们注意到找到C对应于最小二乘问题，其中可以在每个维度上独立地找到C由于B可以被视为非常稀疏的矩阵，因此作者提出在该步骤中使用迭代这具有额外的优点，即B可以被重新用于寻找C分解成的d个问题。我们已经确定了这种方法的两个问题1. 显式稀疏矩阵的构造是低效的。CG API通常要求将B表示为显式稀疏矩阵。 尽管存在用于稀疏矩阵的有效数据结构（例如，，numpy的压缩稀疏行），实际上，B存储为m × n uint8矩阵。我们希望使用这种表示法，避免使用额外的数据结构。2. 未能利用B的二进制性质。矩阵B仅由1和0组成（即，它是二进制）。用于稀疏的数据结构矩阵通常被设计用于非零项是任意实数的一般情况，从而为额外的优化留出空间。LSQ++：更快更准确的多码本量化7NN直接码本更新。我们现在介绍一种用于快速码本更新的方法，该方法利用这两个观察。首先，我们注意到，通过将表达式3重写为正则化最小二乘问题，可以使用直接方法代替迭代CGminX−CB2+ λC2。（四）CF F在这种情况下，可以通过对C求导并将其设置为零来C = XB（BB+ λI）−1。（五）虽然我们对正则化的解不感兴趣，但我们仍然可以通过将λ设置为一个非常小的值（在我们的实验中λ = 10 −4）来受益于这个公式，这只是使解在数值上稳定。这个公式的一个重要优点是矩阵BB+ λI∈Rmh×mh是平方的、对称的、正定的和相当紧的;值得注意的是，其大小与n无关。此外，由于正则化，BB+λI保证是满秩的。因此，矩阵求逆可以直接进行的帮助下，一个Cholesky decom-位置在O（m3h3）的时间。 由于矩阵求逆是一种高效的方法，因此该方法的瓶颈在于计算BB∈Nmh×mh，以及XB∈Rd×mh。 我们利用B中的结构来加速这两个操作。计算BB通过在每个码本上索引B，B= [B1，...，Bm]BB可以写成由大小为m2的块组成的块对称矩阵h×h各：⊤ ⊤ ⊤B1B1B1B2. . . B1 BmB2B B2B. . . B2BBB=1。2.. ..m.（六）.BmBBmB. . . BmB1 2m这里，对角块BNBN是对角矩阵本身，由于B是二进制的，它们的条目是BN中代码的直方图。此外，非对角块是它们的对称对应物的转置：BNB=（BMB）M，并且可以被计算为BM中的代码的双变量直方图和BN。使用这两个观测值，这种方法需要O（m2n）时间，而简单地计算BB需要O（m2h2n）时间。计算预算外 我们再次利用B的结构来加速这一步骤。XB可以写成m个大小为d×h的块的矩阵，XB= [XB，XB，. . . ，XB]。（七）1 2m每个块XB可以通过将B列视为二进制向量来计算我我选择X的列进行求和。时间复杂度为O（mnd）而计算XB的时间复杂度为O（mhnd）。8J. Martinez，S. Zakhmi，H. H. Hoos和J. J. 小CQ中的码本更新。Zhang等人 [34]提出了一种类似于公式5的码本更新公式，他们使用该公式来热启动CQ优化过程，但不引入正则化。由于BB不能保证具有满秩，作者使用SVD计算其逆，忽略与小奇异值相关的解分量。他们也没有利用B中的稀疏性来计算解的其他项。在我们的实验中，他们的方法需要一分钟多的时间来运行，而我们的解决方案运行在一秒之内。5更高的召回率和随机松弛我们在本节中的目标是使LSQ更准确，同时保持它在实践中已经享有的高水平并行性和速度。为此，我们注意到LSQ是快速的，因为它的优化过程是EM式的，这允许它利用高度并行的架构。然而，这种EM类方法的众所周知的问题是它们趋向于收敛到局部最小值。我们还注意到，MCQ类似于k均值聚类（具有组合码本）。 多年来对k-均值的研究已经导致了对原始Lloyd算法的许多改进（例如，，k-均值++初始化[2]，或用于更快编码的聚类闭包[31]），因此我们查阅文献以寻找可以适于改进MCQ的方法5.1随机松弛一个随机松弛（SR），正式由Zeger等人。 [33]在20世纪90年代早期，是一种定义模拟退火近似的方法，其思想是以合理的计算成本提高近似的质量。这个想法最初是为了改进k均值聚类而提出的，在这里我们重新审视并将其适用于MCQ。广义地说，模拟退火（SA）是一种经典的随机局部搜索（SLS）技术，它以3个主要步骤迭代工作：（1）定义优化状态s，（2）通过随机扰动当前状态来创建新状态s’：s′= π（s），和（3）决定是否拒绝或接受新的状态作为下一个微扰的基础（关于这个主题的广泛回顾，见[15]）。步骤3中的接受概率由传统上称为温度的参数控制，该参数通常在步骤2和3的多次迭代中缓慢降低。（已经提出了各种温度计划，并在模拟退火的许多应用中使用随机松弛修改了一些典型的SA步骤，以使它们在计算上更有效。我们现在为我们的方法定义这三个步骤定义SA状态：MCQ的功能视图。作为第一步，我们通常在MCQ中定义优化状态表达式1在两个潜在变量C和B上定义。我们假设优化状态是完全确定的，给定单个变量C或B，其经由预定义函数完全指定另一我们定义LSQ++：更快更准确的多码本量化9– 编码器函数C（X，B）→C，以及– 解码器函数D（X，C）-B。在我们的情况下，C相当于码本更新步骤，我们采用第4节中描述的方法。类似地，D相当于更新代码B;在这种情况下，我们简单地采用LSQ的编码方法我们用两种方式定义了MCQ的优化状态，这将产生两种SR方法。第一种方法称为SR-C，使用编码器函数C，第二种方法称为SR-D，使用解码器函数D。扰乱SA状态。下一步骤是定义在时间步长i处扰动SA状态的方式。我们定义了两种扰动方法，一种用于SR-C，一种用于SR-D。由于我们已经通过代理函数将状态定义为完全确定的给定变量，因此我们可以通过简单地扰动SR-C或SR-D中使用的相应函数来扰动状态我们定义函数– 对于SR-C，C *：=C（πC（X，i），B） →C– D *：= D（X，πD（C，i））→ B对于SR-D。πC（X，i）→X+T（i）·相当于根据预定义的温度计划T（i）将噪声添加到X。我们选择从对角协方差与X成比例的零均值高斯中采样噪声;换句话说，N（0，Σ），其中Σ = diag（cov（X））。k-means和MCQ之间的主要区别在于，在MCQ中，我们使用多个码本。这种差异在SR-D中特别重要，其中噪声影响C，C表示m个不同的码本。由于质心是通过对来自每个码本的一个条目求和而获得的，因此扰动C相当于扰动质心m次。因此，我们稍微不同地定义SR-D的扰动函数：πD（C，i）→C+（T（i）/m）·π。换句话说，我们在SR-D中将噪声乘以1/m的因子温度表。在模拟退火中，通常逐渐降低温度，这控制接受新状态的概率（所谓的Metropolis-Hastings准则）。在SR中，继Zeger et al. [22]，我们使用温度来控制每个时间步长中添加的噪声量。我们用时间表T（i）→（1 −（i/I））p，（8）其中I是迭代的总次数，i表示当前迭代，并且p∈（0， 1]是可调超参数。我们发现p = 0。5产生了良好的结果，我们在所有的实验中都使用了这个参数。验收标准。SA的最终构建块是接受标准，其决定新的（扰动的）状态将被接受还是拒绝。根据Zeger et al. 我们总是接受新的状态。正如我们将要说明的，这个简单的准则在实践中给出了极好的结果10J. Martinez，S. Zakhmi，H. H. Hoos和J. J. 小FFFF算法1 MCQ的 EM类方法[3，21]1：函数LSQ（X，I）2：B ←初始化（X）3： i ←1迭代计数器4：whilei≤I do5：C ←argminCCX-CBX2⊲ 码本更新6：B ←argminB7：i←i+18：结束而9：返回C、B10：结束函数CX-CBX2⊲ 编码步骤总结一下。总而言之，我们介绍了两种定义模拟退火粗略近似的算法：SR-C和SR-D。这些近似实现起来极其简单。为了强调这种简单性，我们在算法1中总结了MCQ的 EM类方法;注意– SR-C完全遵循算法1，除了第5行被替换为C←argminπC（X，i）−CB– SR-D完全遵循算法1，除了第6行被替换为B←argminB X−πD（C，i）B换句话说，SR-C和SR-D相当于在类EM MCQ优化流水线的不同部分中添加噪声，但是执行码本更新以及编码步骤的主力函数保持不变。这具有多个优点。一方面，这意味着我们可以完全保持LSQ的并行性。另一方面，如果将来找到更好的码本更新或编码函数，它们可以无缝集成到我们的管道中。最后，我们注意到，我们的方法只涉及最小的计算开销，因为它们只需要计算X（在SR-C中可以计算一次并多次重复使用）或C的协方差，C是独立于n的紧凑变量。实际上，这种开销可以忽略不计：0<的情况。SR-C为1秒，<0. 01秒，SR-D。我们将SR和快速码本更新的组合称为LSQ++。6实验评价我们通过测量每次LSQ迭代节省的时间来量化我们的码本更新方法的影响（即，在算法1中的第4行和第8行之间），并针对共轭梯度（CG）方法进行头对头大规模评估我们还通过报告召回@N来衡量SR-C和SR-D的影响数 据 集 。 我 们 在 五 个 数 据 集 上 评 估 了 我 们 的 贡 献 。 前 两 个 数 据 集 是LabelMe22K [28]和MNIST。这些数据集最初是为了分类而创建的，并且只有两个分区（训练/测试）。我们学习B和LSQ++：更快更准确的多码本量化11表3.每个LSQ/LSQ++迭代的总时间，取决于我们如何更新C（CG或Cholesky），以及我们如何更新B（使用C++或CUDA实现）。64位128位64位128位SIFT1M CG Chol CG CholJulia，C++14.2 s 5.6 s 38.5 s 22.5 sJulia，CUDA 6.8秒1.2秒20.3秒4.3秒Deep1M CG Chol CG CholJulia，C++9.5 s 7.2 s 30.7 s 24.2 sJulia，CUDA3.3 S1.0秒10.6秒4.1秒C在训练集上，并使用测试集作为查询。LabelMe22K具有d= 512个维度，20019个训练向量和2000个查询。MNIST具有d= 784维度，60 000个训练向量和10 000个查询。其他三个数据集是SIFT 1 M [17]，Deep 1 M和VGG（在[ 21 ]中称为SIFT1M是SIFT [20]特征的经典检索数据集。我们通过从最近引入的Deep1B数据集[5]提供的1000万个示例集中进行采样，将Deep1M数据集放在一起。这些向量来自GoogLeNet v3 [30]网络的最后一个卷积层VGG数据集由来自Chatfield等人[8]的CNN-M-128网络的向量组成。在Imagenet [10]图像上进行评估。这些数据集有三个分区：训练、查询和库。我们遵循标准协议，其使用训练集来学习码本C，然后使用那些码本来编码基集（即，获得B）;然后我们使用查询集在压缩基集中找到近似最近的邻居[1，3，9，12，17，21，22，26，27]。SIFT1M和VGG具有d= 128个维度，并且Deep1M具有d= 96个维度。这三个数据集有10万个训练向量，1M个基向量和10 000个查询。6.1快速码本更新我们在表3中示出了由于我们的码本更新方法而获得的时间节省。我们的方法每次迭代可以节省2.3秒（Deep1M，64位）到16秒（SIFT1M，128位）的训练时间当编码是GPU加速时，这有更大的影响，因为它导致2。2 - 5。6倍的加速比在实践中。大规模的实验。在图1中，我们显示了我们的快速码本更新方法和CG之间的“压力测试”比较，使用的数据集大小为n={ 104， 105， 106， 107}。我们从SIFT1B [17]和Deep1B [5]数据集中获取前n个训练向量，并生成一个随机B。对于CG来说，这是一个特别容易的情况，并且只需要2-3次迭代就可以收敛。即使在这种情况下，我们的方法比以前的工作快几个数量级，并在所有情况下保持在10秒以下，而CG需要高达700秒的n= 10 -7。由于矩阵求逆的复杂性，我们的方法仅在小训练集上较慢，这与n无关。12J. Martinez，S. Zakhmi，H. H. Hoos和J. J. 小103102101100104 105 106107数据集大小（log）104 105 106 107数据集大小（log）CG 128位CG 64位我们的128位我们的64位图1.一、码本更新的时间作为数据集大小的函数，具有多达107个向量。0.500.450.400.350.30MNIST 64位0.500.450.400.350.30LabelMe 64位0.250.200.15CQLSQSR-CSR-DLSQ GPUSR-C GPUSR-DGPUERVQRVQOPQPQ0.250.200.15零点一100101102103104105秒（log）MNIST 128位0.70.60.50.40.30.2100101102103104105秒（log）0.10100101102103104105秒（log）LabelMe 128位0.70.60.50.40.30.2100101102103104105秒（log）图二、在MNIST和LabelMe数据集中作为时间的函数的Recall@16.2随机松弛为了评估我们的第二个贡献，我们报告recall@1，它表示在查询集上计算的经验概率，即查询的实际最近我们在每个数据集上运行每个方法十次，并报告平均结果以说明召回的随机性。我们将我们的贡献与经典的正交MCQ方法PQ [17]和OPQ [12，26]以及最近的RVQ [9]，ERVQ [1，22]，CQ [34]和LSQ [21]进行了比较。所有方法都使用相同的存储器预算（每个向量64或128位）、相同的码本大小h = 256，并且需要相同数量的表查找来近似距离，因此它们的查询时间也是我们将所有方法运行25次迭代。召回@1。图2和图3示出了通过不同方法获得的作为时间的函数我们观察到SR-D在所有方面都比LSQ获得更高的召回率码本更新时间SIFT 1B103码本更新时间深1B102101100秒（log）召回@1召回@1召回@1召回@1LSQ++：更快更准确的多码本量化130.350.300.250.200.150.100.05SIFT1M 64位0.350.300.250.200.150.100.05Deep1M 64位0.350.300.250.200.150.100.05VGG 64位0.00100101102103104105秒（log）SIFT1M 128位0.600.550.500.450.400.350.300.250.20100101102103104105秒（log）0.00100101102103104105秒（log）Deep1M 128位0.600.550.500.450.400.350.300.250.20100101102103104105秒（log）0.00100101102103104105秒（log）VGG 128位0.600.550.500.450.400.350.300.250.20100101102103104105秒（log）图3.第三章。在SIFT1M、Deep1M和VGG数据集中，作为时间函数的Recall@1数据集，以及64和128位，除了128位的SIFT1M。我们的快速码本更新方法，使优化速度比LSQ在所有情况下。SR-C显示出更有趣的行为。当使用64位，该方法either给一个小的提升LSQ，或有一个小的不利影响（LabelMe22K）。然而，当使用128位时，该方法在除Deep1M和VGG之外的所有数据集中表现不佳。我们发现这个结果相当有趣，因为它表明SR-C更适合深度特征，目前在许多机器学习和计算机视觉应用中占主导地位。然而，它在更经典的基准测试中的表现有些令人失望。我们还注意到，一旦我们通过专用一个码本来存储数据库范数来考虑查询时间，RVQ [9]和ERVQ/SQ [1，22]往往比PQ和OPQ表现更差以前的工作仅控制内存使用（增加了查询时间），因此在以前的基准测试中，这个细节并不明显最后，我们还观察到CQ在学习集上训练时无法泛化然而，该方法在LabelMe和MNIST上表现良好，它们没有单独的学习集。这与我们的初步分析一致，并表明CQ需要更多的训练数据（这意味着更多的训练时间）才能很好地推广软件为了我们的实验，我们用C++编写了Rayuela.jl，一个在Julia中实现PQ、OPQ、 OTQ 、RVQ 、 ERVQ 、 CompQ 、 LSQ 和LSQ++ 的 库以 及 OTQ 和LSQ/LSQ++编码的CUDA绑定我们认为CQLSQSR-CSR-DLSQ GPUSR-C GPUSR-D GPUERVQRVQOPQPQ召回@1召回@1召回@1召回@1召回@1召回@114J. Martinez，S. Zakhmi，H. H. Hoos和J. J. 小表4.使用64位的SIFT1M上CompQ、LSQ和LSQ++之间的比较。ItersInit培训基本编码总R@1[27] C++语言250–––38 H0.352LSQ [21]（Julia，CUDA）251.1米2.8 m 29秒（32 iters）4.4米0.340LSQ++（Julia，CUDA）251.1米33 S 29秒（32 iters）2.1米0.346LSQ++（Julia，CUDA）502.2米1.1米58秒（64个）4.3 m0.348LSQ++（Julia，CUDA）1004.4米2.2米1.9 m（128iters）8.5 m0.351LSQ++（Julia，CUDA）1004.4米2.2米3.9 m（256iters）10.5米0.353jl是迄今为止最全面的MCQ方法库。Rayuela.jl可在https://github.com/una-dinosauria/Rayuela.jl获得。与CompQ比较。在表4中，我们根据CompQ更新了基准。开箱即用，LSQ++（具有SR-D）设法将与CompQ的间隙减少一半，从0.012减少到0.006，并且由于更快的码本更新而更快。我们迭代地将LSQ++的计算预算加倍（权衡计算的准确性），并通过100次训练迭代和128次Base编码ILS迭代将召回率的差异提高到0.001将最后一步的预算加倍即使在这种情况下，LSQ++仍然比CompQ快200倍7结论我们已经对最近的非正交MCQ算法进行了基准测试，并且已经发现：（1）LSQ [21]比其竞争对手快得多，（2）LSQ在准确性方面落后于CompQ，以及（3）当使用GPU时，LSQ的计算瓶颈有点违反直觉地是码本更新步骤。基于这些观察，我们已经介绍了两个随机松弛MCQ的方法，提供廉价的近似模拟退火，广泛用于硬组合问题的技术其中一种方法（SR-D）以可忽略的计算成本持续提高LSQ的召回率我们还介绍了一种用于快速码本更新的方法，该方法导致更快的训练。我们的两个贡献都可以用作LSQ之上的开箱即用的改进，并且易于实现。此外，这两个贡献增加了LSQ及其竞争对手之间的运行时间差距，并解释了LSQ和CompQ之间的准确性差异[27]。鸣谢。我们非常感谢NVIDIA为这个项目捐赠GPU。Shobhit在UB C获得了Mitacs Globalink研究实习的支持。我们还提供了一个匿名的审查者，他们提供了多条意见，改进了这个项目。这项研究得到了NSERC的部分支持。LSQ++：更快更准确的多码本量化15引用1. 艾湖余，J.，Guan，T.，He，Y.：通过优化残差矢量量化的高效近似最近邻搜索在：基于内容的多媒体索引（CBMI），国际研讨会（2014）3，4，11，12，132. Arthur，D.，Vassilvitskii，S.：k-means++：小心播种的优点。在：第十八届 年 度 ACM-SIAM 离 散 算 法 研 讨 会 论 文 集 。 pp.1027-1035IndusrialandAppliedMathematics（2007）83. Babenko，A.，Lempitsky，V.：用于极端矢量压缩的加性量化。见：CVPR（2014）3、4、6、10、114. Babenko，A.，Lempitsky，V.：用于大规模相似性搜索和分类的树量化。在：CVPR（2015）35. Babenko，A.，Lempitsky，V.：深度描述符的十亿级数据集的高效索引。In：CVPR（2016）1，116. Bezanson，J.，Edelman，A.，Karpinski，S.，Shah，V.B.：朱莉娅：数值计算的新方法。arXiv预印本arXiv：1411.1607（2014）47. Blalock，D.W.，Guttag，J.V.：Bolt：Accelerated Data Mining with Fast VectorCompression.在：KDD（2017）18. Chatfield，K.，西蒙尼扬，K.，Vedaldi，A.，齐瑟曼，A.：魔鬼的回归细节：深入研究卷积网络。在：BMVC（2014）119. 陈玉，Guan，T.，Wang，C.：基于残差向量的近似最近邻搜索。Sensors10（12），1125910. Deng，J.，Dong，W.，索赫尔河Li，L.J.，Li，K.，李菲菲：Imagenet：一个大规模的分层图像数据库。载于：CVPR（2009）1111. Do uze，M.， Szlam，A.， Hariharan，B. 我走了H ：低-低在：NIPS（2017）112. Ge，T.，他，K.，Ke，Q.孙杰：优化产品量化。见：CVPR（2013）3、4、11、1213. 再见，P.， 做吧，P G i r s hick，R.， 我不知道， 我们都是老K，L.Kyrola，A.， Tul-loch，A.，Jia，Y.，He，K.：精确的大批量SGD：1小时内训练imag