二进制矩阵追踪算法的两阶段哈希方法

二进制矩阵追踪算法Kunh Cakir1，Kun He2，Stan Scaroff21FirstFuel Software，Lexington，MAfcakirs@gmail.com2波士顿大学计算机科学系，马萨诸塞{hekun，sclaroff} @ cs.bu.edu抽象。我们提出了理论和经验的改进两阶段散列方法。我们首先提供了一个理论分析的二进制码的质量，并表明，在温和的假设下，一个剩余的学习计划可以构造二进制码，适合任何neighborhood结构与任意精度。其次，我们证明了使用CNN等高容量哈希函数，可以大大简化许多标准邻域定义的二进制代码推理，从而产生更小的优化问题和更强大的代码。结合我们的研究结果，我们提出了一种新的两阶段哈希方法，显着优于以前的哈希研究广泛使用的图像检索基准。1介绍一个针对“学习”的方法是在问题的关键部分中包含所有内容。大多数方法都是用非线性混合整数规划问题来表示的常见的优化补救措施包括丢弃二进制约束和求解连续边界条件[1- 5 ]。所述存储器模块通常被存储以获得期望的二进制代码。然而，即使是放松的问题也是高度非凸的，需要非平凡的优化过程（例如，例如，在一个实施例中，[6]），并且阈值化的嵌入易于产生大的量化误差，从而需要额外的措施（例如。例如，在一个实施例中，[7]）。松弛方法的一个突出替代方案是两阶段散列，其将优化问题分解为两个阶段：二进制代码推理（i）和散列函数学习（ii）。对于训练集，在推断阶段推断二进制代码，然后将其用作散列函数学习阶段中的目标向量。这种方法密切遵守的离散性质的问题，作为二进制代码直接纳入优化过程。在两阶段散列中，大多数注意力都被吸引到更具挑战性的二进制代码推理步骤。通常，该任务本身被分解成逐阶段问题，其中以迭代方式学习二进制代码虽然通常提供了基础迭代方案的理论保证，但二进制码的整体质量常常被忽视。还期望确定所构造的二进制码的质量。2Fatih Cakir、Kun He和Stan Sclaroff在本文中，我们的第一个贡献是提供一个分析的质量学习二进制代码在两步哈希。 我们专注于经常考虑的用于多个应用的最佳拟合（例如，例如，在一个实施例中，[6，8我们首先证明，普通的汉明距离是无法完全保留的邻域。然后，与加权汉明度量，我们证明了一个剩余的学习计划可以构造二进制码，可以保持任何邻域任意精度在温和的假设下。我们的分析表明，距离缩放以及固定汉明空间的维度（其经常在许多散列图[6，12-14]中采用）是不一致的。另一方面，两阶段散列方法中的一个常见的不便之处在于，步骤（i）和（ii）通常是交错的，以便在训练期间实现位校正[11，15，16]。比特校正已被证明可以提高检索性能，特别是当散列映射构成简单函数（如线性超平面和决策树）时[9]。相比之下，我们证明了这种交错过程对于高容量散列函数（如卷积神经网络（CNN））是不必要的。去除交织的另一个好处是可以根据邻域结构的定义直接构建亲和矩阵，而不是训练实例之间的成对相似性例如，当保持语义相似性时，通常通过类标签协议来定义邻域。相对于标签而不是实例定义亲和度产生用于推理任务（i）的小得多的优化问题，并且为后续散列函数学习（ii）提供鲁棒性。相比之下，基于实例的推理方案导致更大的优化问题，通常需要子采样以减小规模。考虑到这些见解，我们实现了我们的新的两阶段散列方法与标准的CNN架构，并进行多个图像检索数据集上的实验。我们的公式中的亲和矩阵可以或可以不来源于类别标签，并且可以构成二元或多级亲和性。事实上，我们考虑了各种实验，包括多类（CIFAR-10[17]，ImageNet 100[18] ） ， 多 标 签 （ NUSWIDE[19] ） 和 未 标 记 （ 22 KLabelMe[20]）数据集。我们为所有这些数据集实现了新的最先进的性能总的来说，我们的贡献是：1. 我们提供了一个技术分析的推断二进制代码的质量证明，在温和的假设下，我们可以适合任何邻居任意精度。我们的分析与许多两阶段散列方法中使用的配方有关（例如，例如，在一个实施例中，[8、9、11、21、22]）。2. 我们证明，使用CNN等高容量哈希函数，位校正任务是可以消耗的。因此，可以对直接定义邻域的项执行二进制代码推断，从而产生更鲁棒的目标向量并提高检索性能。我们在四个标准的图像检索基准中实现了最先进的性能二进制矩阵追踪算法32相关工作我们只回顾与我们的问题最相关的哈希研究。有关一般调查，请参阅[23]。用于散列的两阶段策略由Lin等人开创。[21]其中作者将二进制代码推理任务简化为一系列二进制二次规划（BQP）问题。目标代码以迭代的方式进行优化，并且采用传统的机器学习分类器（诸如支持向量机（SVM）和拟合目标向量的线性超平面）作为散列函数。在[9]中，作者提出了一种图切割算法来解决BQP问题，并采用提升决策树作为哈希函数。图切割算法已经显示出产生相对于最优值有界的解[24]。作者还证明，利用浅模型，二进制代码推理和散列函数学习的交织过程允许位校正并提高检索性能。不同的是，Xia etal. [8]建议使用具有新的方法的分布式计算器Do等人[11]用半定松弛法和拉格朗日方法解决了BQP问题。他们还调查的质量放松的解决方案，并证明它是在一个因素的全球最小值。Zhuang等[22]证明了相同的BQP方法可以扩展到求解基于三重态的损失函数。其他让人想起这些两阶段方法的工作包括采用交替优化以最小化原始优化问题的散列技术[10，15，16，25]。虽然通常提供了底层迭代方案的误差界和收敛性质，但上述研究都没有提供对所构造的二进制码的整体质量的技术保证。在这项研究中，我们提供了这样的分析。我们的技术分析与低风险资本分析[26-29]有联系，其中在广义下降或矩阵追踪方法中使用了加权条件不同的是，我们用二进制秩一矩阵约束自己此外，虽然不是所有的两阶段哈希研究都遵循交错过程（例如，例如，在一个实施例中，[21，30，31]），据我们所知，所有人都使用训练实例构建亲和这保证了在采用高容量散列函数时对这样的过程的必要性进行深入研究。我们的散列公式遵循矩阵拟合公式，该公式几乎完全用于两阶段方法。该公式最初在[6]中提出，并在随后的散列研究中被广泛采用（e. 例如，在一个实施例中，[8、9、11、21、32]）。虽然本文的主要贡献在于建立二进制代码推理任务的收敛特性，但我们的公式与[6]和其他两阶段方法也有细微和关键的差异。具体地说，我们允许加权汉明距离与最佳学习的权重给出推断的二进制码。我们直接对定义邻域的项执行推断，从而实现更鲁棒的目标向量构造，如将示出的。在检索实验中，我们与最近的散列研究进行比较，包括[4，14，16，33-39 ]，并获得了检索结果。4Fatih Cakir、Kun He和Stan SclaroffX X {···} X × X →−i=12- ∈XX·R3制剂在本节中，我们首先讨论散列公式的两个阶段：二进制码推理和散列映射学习。接下来分析亲和矩阵的构建。补充材料中提供了所有证据3.1二进制代码推理在本节中，我们解释我们的推断步骤（i）。我们给定一个度量空间（，d）其中= x 1，，xn表示项目的集合，并且d：R≥0是度量。注意，X可以对应于实例、标签、多标签或在定义邻域中涉及的任何项。假设邻域是通过度量d定义的，我们学习哈希映射通过优化邻域保持拟合：minΣ[γd（xi，xj）dh（Φ（xi），Φ（xj））]2，（1）Φi、j其中d，h是汉明距离，并且γ是适当选择的缩放参数。在dh的范围内，当已知maxx=max x，y ∈Xd（x，y）时，设γ = b /dmax x.3解方程1需要离散损失最小化，这通常是一个非线性混合整数规划问题。相反，两阶段方法将解决方案分解为两个步骤，第一个步骤涉及一个二进制整数程序，用于查找一组二进制代码或辅助变量{u i∈ H b}n，使等式1.一、该程序可以公式化为：min<$[γd（x，x）−d（u，u）]2=min1Σ[uu-s（x， x）]，（2）ui、jijh i ju4ij i i ii，j其中s（xi，xj）=b2 γd（xi，xj），i，j.而Eq. 2是距离等价问题，RHS是亲和匹配任务。这种基于亲和性的保存目标之前也被考虑过[1，6，14，33]。在我们的公式中，我们通过对u中的每个比特进行加权来考虑加权汉明距离。加权汉明距离已被用于在过去的研究中，以提供更多的颗粒相似性相比，其未加权的对应（e。例如，在一个实施例中， [40-44]）。虽然这对于快速距离计算提高了计算效率，但是对各个比特进行加权使得我们能够构造更好地保持亲和度值的二进制码，如稍后将示出的。我们重新定义方程。通过定义权重向量α=[α1，···，αb]α：1Σ[（α⊙u）u−s（x，x）]2∝1U−R2=f（U），（3）4i、jiji i 2F当re⊙d e不等于Hadamardroduct时，Uij=（α⊙ui）uj，Rij=s（xi，xj），i，j∈并且F表示Frobenius范数。我们注意到，亲和矩阵是实数并且根据其从度量d的构造是对称的。3我们在本节后面的分析只要求dmax有界。二进制矩阵追踪算法5k=1K联系我们BK⊤⊤−∇ U⟨ ∇ ⟩∇−k=1UK设V = [u1，· · ·，un]∈Hn×b表示二进制码矩阵，则U可以berightedemberight edemericesΣbαkvkvhev k1，1 n是V中的第k列。鉴于这一事实，我们的二元推理问题可以重新表述为：minf（U），s.t. U=Σαkv kv，v∈ {−1，+1}n。（四）k=1U的可加性是有吸引力的，因为它表明该问题可以通过在e上添加vk来解决。在特定情况下，我们将应用投影梯度下降算法来求解等式（1）。4.第一章从初始值U0= 0开始，更新步骤可以被公式化为：Ut← Ut−1+αt vt vt，（5）哪里vt = arg maxv∈{− 1，+1}n∠ vv，− ∠f（Ut−1）∠（6）求负梯度方向−f（Ut−1）在秩为1的二元矩阵所构成的子空间中的投影，αt是步长。该投影对于保持等式（1）中的加法性质是重要的。4.第一章由于vv，f=vf v，等式6是一个BQP问题，通常是NP-困难的。在这里，我们采用了一种谱松弛方法，该方法也用于过去的方法（例如：例如，在一个实施例中，[6、21、33]）。一个封闭形式的解决方案，方程。如果二进制向量v松弛为连续值，则存在6具体来说，如果Q=f（），则以下松弛产生瑞利商[45]：Maxvv =n vQv=nλmax（Q），（7）其中λmax表示最大特征值，最优解v * 是相应的特征向量。v*的二进制化值sgn（v*）是方程的近似解。六、该解可以可选地用作针对最大化Eq的BQP求解的初始点。 6，（e. 例如，在一个实施例中， [4 6- 48 ]）。要给出的大多数技术结果并非独立于特定的BQP求解器。负梯度− ⋯f（Ut−1）=R−Σt−1vk v⋯，也是一个对称矩阵。可以认为是迭代t时的残差1.在每次迭代中，我们找到具有该残差的最相关的秩一矩阵，并将我们的解向该方向移动。如果步长αt对于所有t都设为1，则可以分解为二进制码矩阵VV的乘积，产生普通的汉明距离。然而，在步长恒定的情况下，下面的性质表明存在某些亲和矩阵R，使得不存在拟合R的U。物业1. 设Qt是迭代t时的残差−f（Ut）。存在一个R使得t，QtF>0。这样的结果促使我们放松对步长参数αt的约束。如果α被放宽到任何实值，那么我们本质上是加权汉明距离，并且我们证明了在这种情况下可以单调地减少残差R。我们现在给出我们的主要定理：6Fatih Cakir、Kun He和Stan Sclaroff不不不不⊤k=1{···} ∈ X⊙ −不不不定理2. 如果αt∈ R，则梯度下降算法Eq. 5-6 满足t−1其中η∈[0，1]。QtQt−1定理2指出残差的范数仅是单调非增的。然而，它可能不会严格地减少，因为方程的解vt6实际上可以正交于梯度i。例如，v<$Qt−1vt可能为零。如果我们确保在每次迭代中选择非正交方向，则残差严格减小，如以下推论所述。推论3。如果v <$Qt−1 v t/= 0，<$t，则残差范数<$Qt <$F严格地折痕虽然方向vtv是用步长αt贪婪地选择的，但是可以在每次迭代中细化所有过去方向的步长。这通常会导致更快的收敛。更正式地，我们可以通过解决以下回归问题来细化步长α*= arg min1Σαv − R2。（九）α1，···，αt2k=1k kk F幸运的是，Eq。9是一个允许闭形式解的普通最小二乘问题。 令v^k=vec（vkvk）且d^r=vec（R） ，其中vec（ ·） d不表示 vect或 iz。GivenV^t=[v^l，...，v^t]，Eq的最小化。9isα*=（V^V^t）−1V^^r，（10）其中α*=[α*，···，α*]。时间复杂度为O（t3）+O（t2n2）+O（tn2）。t1t√2 2其中n = |X|.如果n> t，时间复杂度为O（tn）term.注意，在实践中，比特数t的典型值很小（100），并且可以被认为是恒定因子。<我们现在提供一个性质，表明步长的这种细化不会破坏定理2和推论3中定义的单调性。财产4. 令Qt是迭代t处的残差矩阵，并且根据定理2设定α t。 LetQ^t是在使用Eq的情况下，通过将所述深度定义为αt=[α1，···，αt]来确定的结果。 10个。 ThenQ^tF≤QtF。在学习U=αkvvt=AVV之后，其中Ak，·=[α1，· · ·，αt]，k我们获得包含目标的二进制码矩阵V =[u1，···， un]n每个元素的代码x 1，，X n。 这 结 束 了 我 们 的 推 断 步 骤（i）。我们总结了我们的推理方案在Alg。二进制码推理。备注。 我们考虑两种不同的二进制推理方案：常数的二进制码构造有恒定的步长，产生普通的汉明距离;和，回归，其中每个位被加权，产生加权汉明距离。F或回归，sice（αui）<$uj=b（12d（xi，xi）/dmi（x） 3，我们可以将常数b嵌入到权重向量变量α中。因此，与必须指定汉明空间维度b的散列方法（例如，例如，在一个实施例中，设置边距和缩放参数[6，10，14]），我们的二进制矩阵追踪算法71不·XX∈ ∈ XXX → {−}算法：二进制代码推理输入：X={ x1，· · ·，xn}，d：X×X →R≥0。布尔变量回归（可选）程序Improve（Q，v0）以改进解vQ vS.T. v ={-1，1}n其中v0是初始解。U= 0。输出：码矩阵V=[u1，···，un]，权重向量α=[α1，···，αT]1 γ=dmax，Rij=1−2γd（xi，xj）（如果回归），Rij=s（xi，xj）×b（如果¬回归）2 对于t← 1，…，没做3vt←特征向量对应于−f（Ut−1）的最大特征值4vt← sgn（vt），αt←15vt←Improve（−f（Ut−1），vt）（可选）6如果回归则//αt∈R7使用等式2设定[α1，· · ·，αt]108端9Ut←Σαtvtv，V·，t←vt//将vt附加到V10 端我只需要一个可以绑定的设备。在其他情况下，重新定义汉明距离或常数需要预先用b进行缩放。方程的近似解7可以通过使用现成的BQP求解器来改进在Alg.二进制代码推理，我们把这种求解器称为子例程Improve（）。在本文中，我们考虑使用一个简单的启发式[46]，它只需要一个积极的目标值方程。六、我们现在进行步骤（ii）：哈希映射学习3.2哈希映射学习回想一下，我们推断目标代码uHb每项x，其中x可以对应于数据实例、类、多标签等，这取决于邻域定义。例如，当数据集是无监督的并且仅通过数据实例定义邻域时，则X可以对应于特征空间，其中d（xi，xi）是欧几里得距离。对于多类数据集，d（xi，xi）可以分别表示类的集合和类对之间的距离值。对于多标签数据集，可以对应于可能的标签组合的集合我们的二进制推理方案构造目标代码的项目，直接定义的邻居。在实验部分，我们涵盖了各种场景。如果不表示特征空间，则在二进制推断步骤（i）之后，根据目标代码和数据实例之间的关系，以一对多的方式将目标代码分配给数据实例。为了清楚起见，我们假设X是本节中的特征空间。我们采用一组散列函数来学习映射，其中函数f：1， 1表示二进制代码中的位的生成在文献中考虑了许多类型的散列函数为了简单起见，我们考虑阈值化的评分函数：f（x），sgn（ψ（x）），（11）不8Fatih Cakir、Kun He和Stan SclaroffnΣ/Σ≤−∈ ∈ XRHb其中ψ可以是诸如线性函数的浅模型，或者是诸如线性函数的深模型。神经网 络的在实验中 ，我们考虑 这两种类型的 嵌入。Φ（x ）=[f1（x），· · ·，fb（x）]则成为要学习的向量值函数。回想一下，我们推断目标代码u对于每个元素x. 在我们处置目标码的情况下，我们现在想要找到Φ，使得Φ（X）与对应的目标码u之间的汉明距离最小化。因此，目标可以表述为：Σdh（Φ（x i），u i）.（十二）i=1将Hamming分布定义为dh（Φ（xi），ui）=dt[[ft（xi）/=uit]]，其中dh和函数ft都是不可微的。幸运的是，我们可以通过丢弃等式中的sgn函数来放松ft11，并推导出汉明损失的上限。注意，dh（Φ（xi），ui）=t[[ft（xi）=uit]]tl（uitΦt（xi））与适当选择的基于凸边缘的函数l。因此，通过将该替代函数代入Eq. 12，我们可以使用随机梯度下降直接最小化这个上界。我们使用铰链损失作为上限l。与其他两阶段散列方法类似，我们的公式的核心是被推断为适合亲和矩阵的目标向量。接下来，我们仔细看看如何构建这个亲和矩阵。3.3亲和矩阵构建亲和度矩阵可以通过直接定义邻域的项目的成对相似性来定义，其可以不对应于训练实例。尽管这种制定的灵活性，以前的相关散列研究一般考虑使用训练实例。对于某些邻域，用训练样本构造亲和矩阵可能会产生次优的二进制码。为了说明这种情况，请考虑图1，其中我们比较了在一系列实验中从两个不同的亲和矩阵推断的两组二进制代码。这些实验中的邻域定义是标准的，通常在几乎所有的散列工作中都可以找到。具体地，我们假设10个类，并定义类亲和矩阵，如图所示。第1（a）段。我们还考虑一个假设的1000个实例的集合，每个实例被分配给这10类之一，并构建亲和矩阵，如图所示。1（b），我们简单地将其称为实例亲和矩阵。实例的相似性被认为是关于所述实例的，并且来自所述实例的相似性被认为是关于所述实例的。我们在不同的长度下的二进制代码，以重建类和实例亲和矩阵。如第3.2节中所解释的，实例被分配其相应类的二进制代码以用于基于类的推断。实验重复5次并报告平均结果我们首先在图1中突出显示残差矩阵Qt范数。第1段（c）分段。注意，基于类的推断的残差范数以较少的迭代收敛到零：40位代码能够以最小的差异重构类亲和矩阵。另一方面，需要更快的代码来完全重建二进制矩阵追踪算法9XAffinity-类Affinity -实例(a)（b）第（1）款0.30.20.10120406010.80.68 12 24 32 48 642001501005008 12 24 32 48 640.3VGGf-all0.2VGGf-fc7GIST1 50 1000.1迭代码长码长历元指数(c)（d）（e）（f）图1：在一系列实验中，我们比较了两组由两个不同的亲和矩阵构建的二进制代码：类（a）和基于实例（b）。（c）-（e）关于剩余范数、mAP和推理时间对比二进制码。从类和实例亲和矩阵推断的二进制代码的结果分别用（）和（）表示。我们还学习了具有不同复杂度的哈希函数，以拟合推断出的二进制代码，并绘制出不匹配位与总位数（f）的比例。实例亲和矩阵。我们还提供了检索性能的两套二进制码。平均精密度（mAP）是评价标准。对于这个实验，从实例集中抽取100个实例作为查询，而其余的构成检索集。如图所示1（d），它们的mAP值有显著差异，尤其是对于紧凑码。差异可以大到0.40。通过实例亲和矩阵推断出的二进制代码的这种类型的次优性也已经被预先观察到（例如，例如，在一个实施例中，[22]）。最后，Fig。1（e）给出了两个推理方案的训练时间虽然推理时间取决于特定的BQP求解器，但决策变量的数量与项目的数量成二次方，如两个推理方案之间的训练时间的巨大差异所示，特别是对于较长的代码。取决于实例矩阵大小，差异可以容易地按比例放大，需要二次采样以减小优化任务的规模。既然有明显的缺点，为什么亲和矩阵是从实例中构造的主要原因是因为在大多数两阶段散列方法中，推理和散列函数学习步骤是交错的，用于动态位校正目的。这需要亲和度矩阵对应于成对实例相似性，因为推断的比特将立即用于训练散列函数。然而，鉴于深度学习的最新进展，高容量预测器变得可用，从而消除了对位校正的需求因此，可以选择求解在直接定义邻域的项目上定义的更小且更鲁棒的优化问题。平均平均精度残差范数推断时间（s）不匹配/总位数10Fatih Cakir、Kun He和Stan Sclaroff×为了说明这一点，我们学习不同复杂度的哈希函数来拟合二进制代码集，并在哈希函数学习过程中绘制不匹配位数占总位数的比例。我们使用CIFAR-10的训练集，并训练散列函数以拟合推断的32位二进制代码（总计：32 50，000比特）。我们考虑GIST[49]上的单层神经网络和在ImageNet[19]上预训练的VGG-F网络[50]的fc 7特征，以及微调所有VGG-F层。图1（f）给出了结果。注意，随着散列函数的容量增加，非匹配位的比率显著降低。虽然在GIST上使用单层神经网络时该比率高于0.25，但在fc7特征上训练的单层神经网络产生略高于10%的不匹配位。当我们对VGG-F网络的所有层进行微调时，这个百分比会降低到10%以下。我们可以用更复杂的体系结构来归纳这一点该比率将进一步减小。我们将这些见解纳入我们的配方和进行检索实验对竞争的方法在下一节中，在那里我们实现了新的国家的最先进的性能。4实验我们在广泛使用的图像检索基准上进行实验：CIFAR-10 [17]、NUSWIDE[18]、22K LabelMe [20]和ImageNet100 [19]。CIFAR-10 是一个用于图像分类和检索的数据集，包含来自10个不同类别的60 K图像我们遵循[2，14，22，38]的设置此设置对应于数据集的两个不同分区。在第一种情况下（cifar-1），我们对每个类别的500个图像进行采样，得到5,000个训练样本来学习哈希映射。测试集包含每个类别100个图像（总共1000个）。然后使用剩余的图像来填充散列表。在第二种情况下（cifar-2），我们每个类别抽取1000张图像来构建测试集（总共10，000张）。其余的项都用于学习散列映射和填充散列表。如果两个图像属于同一类，则它们被视为相邻图像NUSWIDE是一个包含269K图像的数据集。每个图像可以与多个标签相按照[2，14，22，38]中的设置，我们只考虑用21个最常见的标签注释的图像总共相当于195，834张图片。实验装置也有两个不同的分区：nus-1和nus-2。对于这两种情况，通过每个标签随机采样100个图像（总共2，100个图像）来构建测试集。为了学习哈希映射，每个标签随机抽取500个图像（总共10，500个）。然后使用剩余的图像来填充散列表。在第二种情况下，nus-2，除了测试集之外的所有图像都用于学习散列映射并填充散列表。如果两个图像共享一个标签，则它们被视为相邻图像我们还指定了一个更丰富的4 这些二进制代码是从基于类的推理方案中获得的，尽管行为相似展示了与基于实例的推理获得的代码。二进制矩阵追踪算法11X通过允许多层次的亲和性来建立邻居在这种情况下，两个图像的关联度值等于它们共享的公共标签的数量。22KLabelMe由22K个图像组成，每个图像用512维GIST描述符表示。在[3，12]之后，我们将数据集随机划分为两个：分别由20K和2K实例组成的训练集和测试集。训练集的5K子集用于学习散列映射。由于该数据集是无监督的，因此我们使用l2范数来确定邻域。与NUSWIDE类似，我们允许此数据集的多级亲和力我们考虑从训练集推导出的四个距离百分位数，并在实例之间分配多级ImageNet 100是ImageNet [19]的一个子集，包含来自100个类的130K图像。我们遵循[4]，每个类采样100张图像进行训练。将ILSVRC 2012验证集中选定类别中的所有图像用作测试集。如果两个图像属于同一类，则它们被视为相邻图像实验中不使用多层次的亲和力在定义的邻域进行评估，使用一个变种的平均精度（mAP），这取决于我们遵循的协议我们将这些统称为二元亲和力实验。使用归一化贴现累积增益（NDCG）来评估多级相似性实验，NDCG是信息检索中用于测量具有多级相似性的排序质量的度量标准在这两个实验中，汉明距离被用来检索和排名数据实例。我们将我们的方法称为HBMP（二进制矩阵追踪哈希），并将其与最先进的哈希方法进行比较。这些方法包括：谱散列（SH）[33]、迭代量化（ITQ）[34]、核监督散列（SHK）[6]、决策树快速散列（FastHash）[9]、结构化散列（StructHash）[37]、监督离散散列（SDH）[16]、超深神经网络的有效训练（VDSH）[36]、成对标签深度 监 督 散 列 （ DPSH ） [38] 、 具 有 三 元 组 标 签 的 深 度 监 督 散 列（DTSH）[14]和互信息散列（MIHash）[39，51]。这些竞争方法已被证明优于早期和其他作品，如[1，2，8，12，13，41，52]。对 于 CIFAR-10 和 NUSWIDE 实 验 ， 我 们 微 调 VGG-F 架 构 。 对 于ImageNet 100实验，我们微调了AlexNet架构。这两个深度学习模型都是使用ImageNet数据集进行预训练的。对于非深度方法，我们使用两种架构的倒数第二层的输出。为在22K LabelMe基准测试中，我们学习了GIST描述器之上的浅模型。对于基于深度学习的散列方法，这对应于使用单个完全连接的神经网络层。4.1结果我们提供的实验结果与二进制的相似性与mAP作为评价标准，然后与NDCG多层次的相似性。在CIFAR-10中，执行二进制推理的集合表示10个类。对于NUSWIDE，由于邻域是使用多标签定义的，因此12Fatih Cakir、Kun He和Stan SclaroffXXVGG− FCIFAR −10（mAP）NUSWIDE（mAP@5K）方法12位24位32位 48位12位 24位32位48位上海[33]0.1830.1640.1610.1610.6210.6160.6150.612ITQ [34]0.2370.2460.2550.2610.7190.7390.7470.756SHK [6]0.4880.5390.5480.5630.7680.8040.8150.824国家统计局[16]0.4780.5570.5840.5920.7800.8040.8160.824FastHash [9]0.5530.6070.6190.6360.7790.8070.8160.825StructHash [37]0.6640.6930.6910.7000.7480.7720.7900.801VDSH [36]0.5380.5410.5450.5480.7690.7960.8030.807DPSH [38]0.7130.7270.7440.7570.7580.7930.8180.830[14]0.7100.7500.7650.7740.7730.8130.8200.838MIHash [39]0.7380.7750.7910.8160.7730.820 0.831 0.843HBMP0.799 0.804 0.830 0.8310.7570.8050.8220.840表1：使用cifar-I和nus-I分区的CIFAR-10和NUSWIDE数据集底层的深度学习架构是VGG-F。HBMP在CIFAR-10上的性能优于竞争方法，并显示出改进，特别是在NUSWIDE上使用更长的代码。VGG− FCIFAR −10（mAP）NUSWIDE（mAP@50K）方法16位24位32位48位16位24位32位 48位DRSH [52]0.6080.6110.6170.6180.6090.6180.6210.631DRSCH [53]0.6150.6220.6290.6310.7150.7220.7360.741DPSH [38]0.9030.8850.9150.9110.7150.7220.7360.741[14]0.9150.9230.9250.9260.7560.7760.7850.799MIHash [39]0.9270.9380.9420.9430.7980.8140.8190.820HBMP0.942 0.944 0.945 0.945 0.804 0.829 0.841 0.855表2：在具有cifar-2 和nus-2 分区（具有VGG-F 架构）的CIFAR-10 和NUSWIDE数据集HBMP实现了新的最先进的性能，显著改善了竞争方法。然后直观地设置以表示标签组合。在我们的情况下，我们考虑训练集中 的 独 特 标 签 组 合 ， 导 致 = 4850 个 项 目 用 于 二 进 制 推 断 。 对 于22KLabelMe数据集，项目直接对应于训练实例。我们提供的回归二进制推理方案，简称为HBMP的结果。补充材料中给出了常数和回归之间的比较二元亲和力实验。表1给出了cifar-1和nus-1的结果。1实验设置，其中分别针对CIFAR-10和NUSWIDE数据集报告mAP和mAP@5K值。基于深度学习的哈希方法，如DPSH、DTSH和MIHash，优于大多数非深度哈希解决方案。这并不奇怪，因为在这些方法中，特征表示是沿着散列映射同时学习的。两个阶段的方法，E。例如，在一个实施例中，FastHash仍然是具有竞争力的顶级深度学习方法，包括DTSH和MIHash，适用于各种哈希码长度，特别是NUSWIDE。我们的两阶段方法，HBMP，在大多数情况下优于所有竞争方法，包括MIHash，DTSH和DPSH，具有非常大的改进，二进制矩阵追踪算法13−−X--AlexNetImageNet100 （mAP@1K）方法16位32位48位64位HashNet [4]0.5060.6300.6630.683MIHash [39]0.5690.6610.6850.694HBMP0.574 0.692 0.712 0.742表3：使用AlexNet在ImageNet 100上的mAP@1K值。 HBMP优于使用互信息[39]和连续方法[4]的两种最先进的公式。杜松子酒特别是对于CIFAR-10，最好的竞争方法是MIHash，这是一项最近的研究，它使用互信息公式来学习哈希映射对于某些哈希码长度，例如，MIHash的改进超过6%。例如，在一个实施例中， 对于12位0. 799对0的情况。738mAP。我们的方法也比SHK有了显著的改进，SHK也提出了一个矩阵拟合公式，但以交错的方式学习其哈希映射 。 这 验 证 了 在 直 接 定 义 邻 域 的 项 上 定 义 二 进 制 代 码 推 断 。 e.CIFAR-10 的课程。对于NUSWIDE数据集，在训练数据中的标签组合的集合上进行二元推断HBMP证明了可比较的结果或优于最先进的散列方法。最近的一种相关两阶段散列方法是[22]，其中使用相同的设置（cifar-1和nus-1），但对VGG 16架构进行了微调 他们的CIFAR-10和NUSWIDE结果最多为0。80mAP和0. 对于所有散列码长度，分别为75mAP@5K值另一方面，HBMP通过较差的VGG-F架构实现了这些性能为了进一步强调HBMP的优点，我们考虑了实验设置cifar-2和nus-2，并与最近的深度学习哈希方法进行了比较。在此设置中，我们再次微调在ImageNet上预训练的VGG-F表2给出了结果。请注意，我们的方法显著优于所有技术，并为CIFAR-10和NUSWIDE产生了新的最先进的结果。ImageNet100的检索结果在表3中给出。在这些实验中，我们只与MIHash进行比较，MIHash是过去实验中总体上最好的竞争方法，HashNet [4]是另一个最近的基于深度学习的哈希研究。正如所证明的，HBMP建立了新的国家的最先进的图像检索这个基准。HBMP显著优于这两种方法，e. 例如，在一个实施例中，与64位，我们表现出4 6%的改善。这进一步验证了用HBMP产生的二进制代码的质量。多水平亲和力实验。在这些实验中，我们允许多层次的项目之间的相似性集，并使用NDCG作为评价标准。对于NUSWIDE，我们将共享标签的数量视为亲和度值。对于22K LabelMe数据集，我们考虑使用从训练集推导的距离百分位数2%、 5%、 10%、20%来分配训练实例之间的成反比的亲和力值这就强调了多层次的排名在neighgh-14Fatih Cakir、Kun He和Stan SclaroffXNUSWIDE（VGG−F，NDCG）22K LabelMe（GIST、NDCG）方法16位32位48位 64位16位 24位32位48位FastHash [9]0.8850.8960.8990.9020.6720.7160.7400.757StructHash [37]0.8890.8930.8940.8980.7040.7680.8020.824DPSH [38]0.8950.9050.9090.9090.6770.7400.7550.765[14]0.8960.9050.9110.9130.6200.6850.6940.702MIHash [39]0.8860.9030.9090.9120.7130.8220.855 0.873HBMP0.914 0.924 0.927 0.930 0.823 0.8290.8490.866表4：分别使用VGG-F和GIST在NUSWIDE和22 K LabelMe上的多水平亲和力实验NUSWIDE使用的分区是nus-1。评价标准是归一化贴现累积增益（NDCG）。在大多数情况下，HBMP比最新技术水平有所改善bors在原始特征空间中。在22K LabelMe中，我们使用一个完全连接的层作为基于深度学习的方法的哈希映射表4给出了结果。 对于NUSWIDE，HBMP优于所有最先进的方法，包括MIHash。 在22K LabelMe中，HBMP要么实现了最先进的性能，要么紧随其后。一个有趣的观察结果是，当由于使用预先计算的GIST特征而去除特征学习方面时，FastHash和StructHash等非深度方法的 性 能 优 于 深 度 学 习 散 列 方 法 DPSH 和 DTSH 。 虽 然 FastHash 和StruchHash喜欢非线性哈希函数，如提升的决策树，但这也表明DPSH和DTSH的威力可能主要来自特征学习。另一方面，HBMP和MIHash都显示出使用单个全连接层作为哈希映射的最佳性能，这表明它们产生的二进制代码更准确地反映了邻域。关于22K LabelMe，对于HBMP，集合对应于训练实例，与其他方法中类似。这表明，HBMP的性能改善不仅是由于这样的事实，即二进制推理是直接定义的邻域的项目上执行，但也由于我们的配方，学习汉明度量与最佳选择的位权重。5结论我们提出了改进的两阶段哈希方法中常用的配方。我们首先提供了一个理论结果的二进制代码的质量表明，在温和的假设下，我们可以构建二进制代码，适合与任意精度的邻域。其次，我们分析了二进制码的次最优性构造，以适应亲和矩阵，没有定义的项目直接相关的邻域。为了验证我们的发现，我们提出了一种新的两阶段哈希方法，该方法在多个基准上的性能明显优于以前的哈希研究。致谢。作者感谢Sarah Adel Bargal的有益讨