没有合适的资源?快使用搜索试试~ 我知道了~
用于大规模搜索的有监督离散哈希方法及其优势
Track: Web Search and MiningWWW 2018, April 23-27, 2018, Lyon, France16030用于大规模搜索的可扩展有监督离散哈希0山东大学罗鑫luoxin.lxin@gmail.com0山东大学吴晔kimiwadewu@gmail.com0徐新顺 �0山东大学xuxinshun@sdu.edu.cn0摘要0这些年来,有监督哈希方法引起了很多关注。然而,大多数现有的有监督哈希算法存在以下问题之一。首先,它们大多利用成对相似性矩阵来监督哈希码的学习,而成对相似性矩阵的大小与训练样本数量的平方成正比。因此,在处理大数据时,它们不具备可扩展性。其次,它们大多通过放松离散约束进行简单的优化,然后将学到的实值解量化为二进制哈希码。因此,由于放松引起的量化误差可能导致检索性能下降。为了解决这些问题并使有监督方法适用于大型数据集,我们提出了一种新的哈希方法,称为可扩展有监督离散哈希(SSDH)。具体而言,基于一种新的损失函数,SSDH绕过了对n×n成对相似性矩阵的直接优化。此外,SSDH在学习过程中采用了无放松优化方案,并避免了大量量化误差问题。此外,在学习过程中,它利用了成对相似性矩阵和标签矩阵;因此,可以将更多的语义信息嵌入到哈希码的学习中。我们在包括两个大规模数据集NUS-WIDE和ImageNet在内的六个基准数据集上进行了大量实验证明,SSDH在这些数据集上可以胜过现有的基线方法,证明了其有效性和效率。0关键词0学习哈希;有监督哈希;可扩展搜索;离散优化0ACM参考格式:Xin Luo,Ye Wu和Xin-ShunXu。2018。用于大规模搜索的可扩展有监督离散哈希。在WWW2018:2018年网络会议上,2018年4月23日至27日,法国里昂。ACM,纽约,纽约,美国,10页。https://doi.org/10.1145/3178876.318607201 引言0随着数据的指数增长,诸如推荐[13, 14],检索[39,40]和多媒体分析[38, 41,56]等现实世界的应用发生了巨大变化。其中,许多重要的应用程序利用了相似性搜索技术,该技术可以返回与给定查询实例相似的数据实例。0� 通讯作者。0本文发表在知识共享署名4.0国际(CC BY4.0)许可下。作者保留在其个人和公司网站上传播作品的权利,并附上适当的归属。WWW 2018,2018年4月23日至27日,法国里昂,© 2018IW3C2(国际万维网会议委员会),根据知识共享CC BY 4.0许可发布。ACM ISBN978-1-4503-5639-8/18/04。https://doi.org/10.1145/3178876.31860720随着数据量的爆炸性增长[50,51],在原始高维空间中对查询实例和候选实例进行详尽的比较使得传统的相似性搜索方法不适用于可扩展搜索。为了进行快速相似性搜索,近年来提出了许多有前途的哈希方法[1, 15, 23, 27, 47,63]。它们已经成功应用于许多问题,包括网络图像检索[28,35],移动地标搜索[64],视频检索[12],推荐[59,62],人员重新识别[61],顺序或在线数据搜索[2, 3,54],跨模态或跨视图检索[22, 31, 36,37],分布式环境中的搜索[26]等等。哈希方法通过学习哈希函数将原始数据转换为紧凑的二进制哈希码(通常≤128位);通过存储哈希码而不是原始高维数据,可以大大减少存储成本。当查询到来时,它们首先通过学习的函数将其转换为二进制哈希码;然后,可以通过计算可用数据实例和查询之间的汉明距离来简单地进行相似性搜索。由于两个二进制码之间的汉明距离仅仅是不同位的数量,并且可以使用按位操作XOR计算,因此检索过程可以高效地进行。由于上述优点,即低存储成本和高效的成对比较,哈希方法适用于可扩展的数据搜索。哈希方法可以分为数据无关和数据相关两种。数据无关的哈希方法不考虑具体的数据,并利用随机投影来学习哈希函数。局部敏感哈希(LSH)[8]是最流行的数据无关方法之一。随着LSH的成功,它已经扩展到各种相似性度量,例如p-范数距离[7],马氏距离[21]和核相似性[20]。这些方法的主要缺点是它们需要长的码来保证高精度,这导致了巨大的存储开销。与数据无关的哈希相比,数据相关的哈希方法考虑具体的数据,并学习紧凑的二进制码,可以有效地高效地索引和组织大量数据。文献中提出了许多这样的方法,并可以进一步总结为两类:无监督和有监督方法。无监督方法不利用标签/语义信息,并通过利用训练数据的关系来学习哈希码或哈希函数。有许多代表性的无监督哈希方法,例如谱哈希[52],迭代量化[9],流形上的归纳哈希[46],循环二进制嵌入[57],离散图哈希[33]和可扩展图哈希[17]等。当标签信息可用时,有监督哈希方法可以将语义信息嵌入到哈希码的学习中,并在许多实际应用中表现出比无监督方法更好的性能。因此,有监督哈希方法在许多领域中受到了更多的关注。s.t. B ∈ {−1, 1}n×r .(1)16040最近越来越受到关注。一些代表性的有监督哈希方法包括半监督哈希[48]、最小损失哈希[42]、两步哈希[30]、具有潜在因子的有监督哈希[60]、基于决策树的快速有监督哈希[29]、离散有监督哈希[45]和基于列采样的离散有监督哈希[18]等。在哈希调查中还可以找到更多方法[4, 5,49]。尽管现有的有监督哈希方法已经提供了有希望的性能,但仍然存在一些需要进一步考虑的问题。首先,哈希码的二进制约束导致了一个难以解决的离散优化问题。为了解决这个问题,大多数现有方法首先放松离散约束,将原始问题转化为一个更容易解决的连续问题;然后,将连续解量化为二进制哈希码空间。然而,解可能是次优的,而由于放松引起的误差通常会降低性能。其次,由于有监督方法需要嵌入标签信息,大多数方法在学习过程中构建一个n×n的实例对相似性矩阵,并利用它。这种实例对相似性矩阵有一个明显的缺点,即空间成本。特别是在处理大规模数据时,n×n的空间成本是无法承受的。因此,这些哈希方法耗时且不可扩展。为了解决这个问题,它们必须对训练样本进行采样,并丢弃其他样本。显然,这可能导致信息丢失并导致性能下降。为了解决上述问题,在本文中,我们提出了一种名为可扩展有监督离散哈希(SSDH)的新方法。它可以通过充分利用所有训练样本和语义信息来离散且高效地学习哈希码。总结一下,SSDH的主要贡献包括:0•它同时考虑了成对相似性S和标签矩阵L,可以确保更精确的哈希码。•通过用来自标签矩阵L的实值变换表示哈希码矩阵B,SSDH避免了对n×n大矩阵S的直接优化,这使得在处理大规模数据时空间成本可接受。此外,使用实值矩阵和哈希码而不仅仅是二进制矩阵可以更准确地近似S。•提出了一种交替离散优化算法来高效学习哈希码,该算法可扩展处理大规模数据集。•在六个广泛使用的数据集上进行了大量实验。结果表明SSDH优于最先进的有监督哈希方法。0本文的其余部分组织如下。高度相关的工作在第2节中讨论。第3节介绍了提出的SSDH模型,包括损失函数、优化算法以及对样本外数据的扩展。第4节介绍了在几个基准数据集上的实验结果和分析。最后,第5节总结了本文。02 相关工作:两步哈希0大多数哈希方法同时学习哈希码和哈希函数,我们可以称之为一步哈希。不同的是,两步0哈希方法将哈希码和哈希函数的学习分为两个步骤。在第一步中,两步哈希方法通过损失函数的监督生成哈希码。在第二步中,给定学习到的哈希码,两步哈希方法学习可以将原始特征转换为紧凑二进制码的哈希函数。已经有很多两步哈希方法[18, 29–31,34]。通常,两步哈希方法的性能高度依赖于第一步学习到的哈希码的质量。因此,两步哈希更注重生成哈希码的准则,即损失函数的设计。实际上,正如[30]所揭示的那样,一旦学习到哈希码,对于哈希码的任何位来说,学习将特征投影到其中的相应哈希函数可以被建模为一个二分类问题。因此,任何有效的预测模型都可以在第二步中作为哈希函数,如线性分类器[18, 48,58]、带有RBF核的SVM[30]、深度卷积网络[53]、提升决策树[18,29]。一般来说,使用更强大的分类器作为哈希函数,可以获得更好的准确性,但也会消耗更多的训练时间。提出的SSDH属于两步哈希,它的损失函数以及相应的优化算法使得SSDH与其他两步方法不同。03 我们的方法0本节介绍SSDH的细节。它也是一种两步哈希方法,这意味着SSDH的训练可以分为两个步骤,即哈希码学习步骤和哈希函数学习步骤。0假设我们有n个标记的实例,即xi ∈ Rd与其标签向量yi ∈ {0, 1}c(i = 1, 2, ...,n)。d是每个实例的维度,c是类别数。相应地,X ∈ Rn × d0其中X ∈ {0, 1} n × d和Y ∈ {0, 1} n ×c分别是特征和标签矩阵。例如,X�i� = xi和Y�i� =yi。此外,Yik是y�i的第k个元素;如果xi属于第k类,则Yik =1,否则Yik = 0。此外,S ∈ {− 1, 1} n ×n表示实例对的语义相似性,其中Sij =1表示点i和点j在语义上相似,Sij = −1表示相反。SSDH旨在为每个实例学习一个r位二进制哈希码bi ∈ {−1, 1} r,B ∈ {− 1, 1} n × r是具有每行B�i� =bi的哈希码矩阵。哈希函数F(∙)将X转换为B,即B = F(X) =sign(XW),其中W是投影矩阵,sign(∙)是逐元素的符号函数,定义为sign(x) = 1 if x ≥0,否则为−1。不失一般性,我们假设输入实例为零中心化,即∑ni=1xi = 0。03.2 哈希码学习-损失函数的设计0为了利用语义信息学习哈希码,许多哈希方法[18, 25, 29, 30, 34,53, 60]将相似性矩阵嵌入到以下损失函数中:0min B ∥ rS − BB�∥2F,0Track: Web Search and Mining WWW 2018, April 23-27, 2018, Lyon, France(2)(7)(8)16050正如[34]所证明的,哈希码的内积反映了汉明距离的相反。因此,公式(1)使用内积来近似语义相似性,采用平方损失。这种模型的主要缺点是当n很大时,优化过程耗时。为了解决这个问题,我们提出了以下新的损失函数:0min B, G ∥ rS − B(YG)� ∥2F + µ ∥ B − YG ∥2F0在损失函数中引入了两个矩阵,即G和Y。G ∈ Rc ×r是从Y到B的投影;Y是标签矩阵,µ是平衡参数。公式(2)的设计具有几个主要优点。首先,我们可以通过利用成对相似性S和标签矩阵Y来监督哈希码的学习,而不仅仅是其中之一,这可以确保更精确的哈希码。其次,正如[10]所揭示的,使用公式(1)中的实值信息而不是二进制B可以获得更准确的相似性近似。因此,我们使用实值的YG来替换公式(1)中的一个二进制矩阵B,并且在[11,45]中已经证明YG对于近似B是有效的。第三,通过引入YG并替换一个B,我们可以巧妙地避免对大S的直接优化。如优化部分中所讨论的,我们可以离线计算SY并直接使用SY的项来代替学习中的S。值得注意的是,SY的大小只有n ×c(c通常远小于n);因此,解决优化问题可以变得更加高效。03.3 哈希码学习-损失函数的优化0如上所示,公式(2)中有两个变量,即B和G。为了解决这个优化问题,在本节中,我们提出了一种交替策略,其中有两个交替步骤:固定B更新G和固定G更新B。03.3.1 在固定 B 的情况下更新 G。显然,一旦 B固定,优化问题就有一个闭式解。然后,我们可以通过将(2)对 G的导数设为零来得到 G,即:0G = ( Y � Y ) − 1 ( r ( SY ) � B + µ Y � B )( B � B + µ I r × r0如果我们在优化过程中直接使用S,当训练数据集很大时,空间和时间成本是不可接受的。幸运的是,我们可以在训练之前离线计算 SY,并在优化过程中直接加载SY。将 SY 表示为 A,方程(3)可以进一步改写为:0G = ( Y � Y ) − 1 ( r A � B + µ Y � B )( B � B + µ I r × r )0其中 A 的大小为 n × c,c 通常远小于n。因此,在优化过程中,SSDH可以绕过使用大型成对相似性矩阵的缺点。03.3.2 在固定 G 的情况下更新 B。在更新 B时,我们需要考虑两种情况,即单标签数据和多标签数据。下面分别讨论这两种情况。单标签数据:为了考虑方程(2)中的第一项,受[18]中的工作启发,我们首先用其替换为的Frobenius范数:0L1范数;因此,问题变为:0min B ∥ r S − B ( YG ) � ∥ 1 , s . t ., B ∈ {− 1 , 1 } n× r . (5)0然后我们有解 B = sдn ( SYG)。对于单标签数据,我们可以轻松找到 sдn ( SYG ) 的值等于 sдn (YG )。因此,对于方程(2)中的第一项,解为 B = sдn ( YG)。对于方程(2)中的第二项,我们可以轻松找到 B = sдn ( YG )也是解。因此,对于单标签数据,方程(2)的解为:0B = sдn ( YG ) . (6)0多标签数据:对于这种情况,sдn ( SYG ) 不再等于 sдn ( YG),这意味着 B = sдn ( YG )不再是方程(2)的解。相反,我们使用离散循环坐标下降(DCC)来获得具有闭式解的 B。首先,通过省略常数项 ∥ r S ∥ 2 F , µ∥ B ∥ 2 F 和 µ ∥ YG ∥ 2 F,我们将方程(2)重写为以下形式:0min B ∥ YGB � ∥ 2 F − 2 Tr ( B � SYG + µB 0= ∥ YGB � ∥ 2 F − 2 Tr ( B � ( AG +0= ∥ CB � ∥ 2 F − 2 Tr (0s . t . B ∈ {− 1 , 10其中 A = SY,C = YG,Q = AG + µ C。然后,我们逐位更新B,这意味着我们通过固定其他所有列来迭代学习 B的每一列。为此,我们假设 b 是 B 的第 l 列,即 b是由所有样本的第 l 位组成的向量,l = 1,2 ∙ ∙ ∙,r,B ′ 是除去 b的矩阵。类似地,q 是 Q 的第 l 行,Q ′ 是除去 q 的 Q 的矩阵;c 是C 的第 l 行,C ′ 是除去 c 的 C 的矩阵。然后我们有:0∥ CB � ∥ 2 F = Tr ( BC �CB � )0= ∥ bc ∥ 2 F + 2 cC ′ B ′� b0= 2 c � C ′ B ′� b + const .0这里 ∥ bc ∥ 2 F = Tr ( c � b � bc ) = n c � c =const。相应地,我们有:02 Tr ( B � Q ) = q � b + const . (9)0然后,优化问题可以进一步简化为以下形式:0s . t . b ∈ {− 1 , 1 } n . (10)0最优解是:0b = sдn ( q − B ′ C ′� c ) . (11)0我们可以看到每个位b都是基于预先学习的B的位计算出来的。我们可以迭代更新每个位,直到过程收敛到一组更好的码B。03.3.3 整个算法。SSDH的上述优化过程总结在算法1中。0Track: Web Search and Mining WWW 2018, April 23-27, 2018, Lyon, France16060算法1:SSDH中的离散优化。0输入:A = SY,它是离线计算得到的;标签矩阵Y ∈ {0, 1}n ×c;参数µ;迭代次数t;哈希位长度r。输出:哈希码B ∈ {−1,1}n × r;投影矩阵G。通过随机化初始化G和B。对于iter = 1 →t的每次迭代:0通过固定B,使用公式(4)更新G。如0通过固定G,使用公式(6)更新B。如果是多标签,则:0通过固定G,使用公式(11)更新B。结束。03.4 哈希函数学习0一旦学习到哈希码,SSDH需要学习哈希函数,将原始特征转换为二进制码,例如用于样本外实例。如前所述,哈希函数学习可以看作是任何码位和任何任意分类器的二进制分类问题,可以采用任意分类器作为哈希函数。SSDH选择线性回归,因为它的效率高1。当采用线性回归时,可以通过解决以下平方损失问题获得哈希函数:0Le = ∥ B - XW ∥2F + λe ∥ W ∥2F, (12)0其中λe是平衡参数,∥W∥2F是正则化项。然后,我们可以得到最优解:0W = (X � X + λeI)�¹X � B. (13)03.5 样本外扩展0一旦学习到哈希函数,SSDH可以轻松地为新的查询生成哈希码。假设X query和Bquery分别是查询的原始特征和相应的哈希码。那么,Bquery可以通过以下方式获得:0B query = F(X query) = sign(X query W). (14)03.6 核化0核化是监督哈希文献中一种常用且强大的技术。对于数据点x ∈Rd,我们随机采样了m个锚点,即o1,o2,∙∙∙,om,并将x映射到一个m维的核特征表示,使用以下公式:0ϕ ( x ) = [ exp (∥ x - o1 ∥2 / σ ), ∙ ∙ ∙ , exp (∥ x - om∥2 / σ )] .0这里,σ是核宽度。我们设置m =1,000,并根据训练样本之间的平均欧氏距离估计σ。0表1:六个数据集的基本统计信息0数据集 标签类型 训练大小0查询大小0标签数量0MNIST单标签 69,000 1,000 100MIRFlickr多标签 15,738 1,000 240CIFAR-10单标签 59,000 1,000 100CIFAR-100单标签 59,000 1,000 1000NUS-WIDE多标签 193,833 2,100 210ImageNet单标签 1,198,336 63,070 1,00004 实验结果 4.1 实验设置0数据集:我们在六个公开可用且广泛使用的数据集上进行实验,以评估所提出的方法。0• MNIST 2[24]:该数据集是从NIST中提取的一个更大数据集的子集。它包含了从'0'到'9'的70,000个手写数字图像,因此有10个类别。该数据集中的每个图像由784维特征向量表示。• MIRFlickr 3[16]:这是一个从Flickr网站收集的真实世界数据集,包含25,000个实例。每个实例都手动标注了至少一个标签中的24个标签之一。根据[31,55]中的预处理方法,我们删除了没有标签或者文本标签出现次数少于20次的实例。最终,剩下了16,738个实例。对于每个实例,它的图像由150维边缘直方图表示。• CIFAR-10 4[19]:它是从8000万个小图像中收集的。CIFAR-10中的每个图像都手动标记了10个类别中的一个;每个类别包含6000个样本,因此CIFAR-10总共有60,000个图像。图像由从原始尺寸为32×32的彩色图像中提取的512维GIST [43]特征向量表示。• CIFAR-100 5[19]:它也是从8000万个小图像中收集的。它包含100个类别,每个类别包含600个彩色图像,总共有60,000个图像。每个图像由一个512维的GIST特征向量表示。• NUS-WIDE 6[6]:这是一个从Flickr中收集的真实世界图像数据集,原始数据集包含269,648个样本。根据[45],我们选择了出现频率最高的21个标签进行评估,剩下了195,834个图像。我们使用提供的500维词袋模型特征。• ImageNet 7[44]:我们还在ILSVRC2010的训练集上评估了我们的方法。该数据集是ImageNet的一个子集,包含了1.2百万张图像。这些图像属于1,000个类别,每个类别至少有600个样本。我们使用发布的1,000维词袋模型特征来表示实例。01SSDH可以选择更强大的分类器,进一步提高准确性。但是分类器的选择不是我们论文的重点,我们将其他候选分类器的研究留给未来的追求。2http://yann.lecun.com/exdb/mnist/ 3http://press.liacs.nl/mirflickr/mirdownload.html 4 https://www.cs.toronto.edu/kriz/cifar.html 5 https://www.cs.toronto.edu/ kriz/cifar.html 6http://lms.comp.nus.edu.sg/research/NUS-WIDE.htm 7http://image-net.org/challenges/LSVRC/2010/0Track: Web Search and Mining WWW 2018, April 23-27, 2018, Lyon, FranceITQ0.01250.01510.01700.01930.02030.4680.7111.282.464.01KSH0.02250.02680.02900.03070.033832.6363.60128.91257.12386.89SDH0.02170.03390.04730.05890.03923.835.779.6980.92190.57NSH0.03230.04830.06490.07580.08373.243.534.075.586.99FSDH0.02560.04190.05980.06900.08846.616.556.737.017.57COSDISH0.03790.07520.14490.20190.22921.996.3916.7679.82185.28SSDH0.10010.16400.23480.28240.26743.033.113.163.303.34Track: Web Search and MiningWWW 2018, April 23-27, 2018, Lyon, France16070表2:MNIST上所有方法的MAP结果和训练时间。每个类别的最佳MAP以粗体显示。0MAP 训练时间(秒)0方法 8位 16位 32位 64位 96位 8位 16位 32位 64位 96位0LSH 0.1731 0.2202 0.2686 0.3267 0.3553 0.040 0.044 0.062 0.091 0.1290ITQ 0.3818 0.4132 0.4367 0.4601 0.4673 0.892 1.42 2.72 5.27 7.180KSH 0.7103 0.7880 0.8258 0.8434 0.8428 48.02 90.72 179.82 337.53 508.680SDH 0.5956 0.8544 0.8861 0.8945 0.8963 6.45 7.13 17.27 59.60 127.060NSH 0.7314 0.8667 0.8934 0.9102 0.9105 4.33 5.25 5.38 6.89 8.510FSDH 0.8701 0.8940 0.9139 0.9200 0.9253 8.60 7.93 8.71 9.94 10.460COSDISH 0.7895 0.8498 0.8740 0.8866 0.8861 4.59 8.08 30.31 107.01 241.080SSDH 0.9338 0.9557 0.9639 0.9669 0.9683 3.68 3.80 3.81 3.93 4.090表3:MIRFlickr上所有方法的MAP结果和训练时间。每个类别的最佳MAP以粗体显示。0MAP 训练时间(秒)0方法 8位 16位 32位 64位 96位 8位 16位 32位 64位 96位0LSH 0.5669 0.5760 0.5712 0.5862 0.5885 0.005 0.005 0.007 0.013 0.0160ITQ 0.5760 0.5721 0.5794 0.5796 0.5806 0.134 0.154 0.305 0.589 0.9250KSH 0.5780 0.5775 0.5794 0.5782 0.5790 28.69 57.02 109.05 219.11 329.990SDH 0.6023 0.6071 0.6138 0.6207 0.6220 1.31 1.90 3.99 13.19 30.380NSH 0.6143 0.6180 0.6158 0.6243 0.6270 0.873 0.932 1.03 1.31 1.590FSDH 0.5908 0.5957 0.6053 0.6124 0.6152 2.01 2.02 2.07 2.13 2.200COSDISH 0.6819 0.6939 0.7036 0.7173 0.7185 0.639 1.66 6.04 29.85 69.990SSDH 0.7099 0.7128 0.7154 0.7198 0.7258 0.722 0.849 1.32 3.10 6.290表4:CIFAR-10上所有方法的MAP结果和训练时间。每个类别的最佳MAP以粗体显示。0MAP 训练时间(秒)0方法 8位 16位 32位 64位 96位 8位 16位 32位 64位 96位0LSH 0.1077 0.1165 0.1199 0.1270 0.1360 0.021 0.025 0.032 0.044 0.0640ITQ 0.1429 0.1482 0.1569 0.1487 0.1551 0.483 0.743 1.32 2.54 3.980KSH 0.2315 0.2623 0.2905 0.3095 0.3199 29.91 59.59 121.00 243.73 359.110SDH 0.2373 0.3528 0.3868 0.4049 0.4159 4.58 5.55 9.09 29.54 83.130NSH 0.2902 0.2936 0.3220 0.3390 0.3687 2.99 3.675 3.70 4.81 5.750FSDH 0.3311 0.3884 0.4270 0.4522 0.4646 6.05 6.09 6.26 6.65 7.050COSDISH 0.5012 0.5745 0.6094 0.6321 0.6394 2.10 4.33 15.19 76.99 180.340SSDH 0.5151 0.6698 0.6991 0.7046 0.7063 2.61 2.69 2.66 2.67 2.730表5:CIFAR-100上所有方法的MAP结果和训练时间。每个类别的最佳MAP以粗体显示。0MAP 训练时间(秒)0方法 8位 16位 32位 64位 96位 8位 16位 32位 64位 96位0LSH 0.0117 0.0125 0.0139 0.0153 0.0169 0.021 0.025 0.027 0.0485 0.059AP = 1RMAPi.(16)Track: Web Search and MiningWWW 2018, April 23-27, 2018, Lyon, France16080每个数据集都被随机分成训练集和查询集。在NUS-WIDE数据集上,对于每个标签,随机抽取100张图像(包含重复)作为查询集。在ImageNet数据集上,我们通过随机抽取5%的实例构建查询集。这些数据集的统计信息如表1所示。对于单标签数据集,如果两个样本具有相同的类标签,则认为它们在语义上是相似的,否则是不相似的。对于多标签数据集,如果两个样本共享至少一个语义标签,则认为它们在语义上是相似的。竞争方法:我们将SSDH与七种最先进的哈希算法进行了比较,包括无监督和有监督的算法:0• LSH [ 8 ]:局部敏感哈希(无监督)。其基本思想是对数据库中的点进行哈希,以确保靠近的对象发生碰撞的概率远高于远离的对象。• ITQ [ 9 ]:迭代量化(无监督)。ITQ包含一个简单而高效的交替最小化方案,用于找到将零中心数据旋转以最小化将该数据映射到零中心二进制超立方体顶点的量化误差。• KSH [ 34 ]:基于核的有监督哈希(有监督)。KSH利用了优化代码内积和汉明距离之间的等价性。• SDH [ 45 ]:有监督离散哈希(有监督)。它的学习目标是为线性分类生成最优的二进制哈希码。• NSH [ 32 ]:自然有监督哈希(有监督)。NSH的关键思想是将标签向量视为二进制码,并学习具有与标签向量类似结构的目标码。• FSDH [ 11 ]:快速有监督离散哈希(有监督)。FSDH使用一个非常简单但有效的回归方法,将训练样本的类标签与相应的哈希码进行加速。•COSDISH [ 18 ]:基于列采样的离散有监督哈希(有监督)。COSDISH直接从语义信息中学习离散哈希码。0对于大多数基线,我们使用了作者提供的代码,并根据作者建议的方案仔细调整了它们的参数。由于NSH和FSDH的代码不公开,我们按照它们的算法准确地实现了代码,并根据它们的论文中建议的方案调整了参数。对于SSDH,我们设置 t =5,这足以获得令人满意的性能,µ = 1和λe =1。所有方法在一台配有Intel(R) XEON(R) CPU E5-2650@2.30GHz、128GB内存的工作站上运行。根据[18, 30,34],我们在所有数据集上随机抽取了2,000张图像作为KSH的训练集,因为它的时间复杂度很高。评估指标:为了全面评估SSDH和所有基线,我们采用了三个广泛使用的指标,即平均精度(MAP)、精确率-召回率曲线和topN-精确率曲线。对于所有指标,数值越大表示检索性能越好。查询的平均精度 (AP) 定义为0r = 1 精度 ( r ) δ ( r ) . (15)0其中R是查询在数据库中的真实邻居数量,n是数据库中样本的数量,Precision(r)表示前r个检索实体的精确度,δ(r) =1表示第r个检索实体是真实邻居,δ(r) =0表示否。对于大小为M的查询集,MAP被定义为查询集中所有查询的平均精确度分数的平均值,即0MAP = 10通过改变检索点的汉明半径并评估精确度、召回率和检索点的数量,可以获得精确度-召回率曲线。TopN-精确度曲线反映了精确度随返回给用户的前N个排名最高的实例数量的变化,这对于检索是有意义的。04.2比较结果04.2.1MAP和时间。MNIST、MIRFlickr、CIFAR-10和CIFAR-100上所有方法的MAP结果和训练时间列在表2、3、4和5中。从这些表中我们可以观察到:•SSDH在所有情况下的MAP结果都优于所有基线方法,验证了其有效性。•无监督哈希方法LSH和ITQ需要最少的训练时间。然而,所有有监督的方法都优于它们。•在单标签数据集,即MNIST、CIFAR-10和CIFAR-100上,SSDH可以高效地训练。例如,SSDH所需的时间比其他有监督的基线方法短。此外,SSDH的训练时间对哈希位长度是稳健的,而KSH、SDH和COSDISH在更长的位长度上需要更多的训练时间。•在多标签数据集MIRFlickr上,我们也可以快速训练SSDH。由于SSDH需要逐位学习二进制码,学习更长的哈希码需要更多的时间。然而,与逐位学习哈希码的基线方法KSH、SDH和COSDISH相比,SSDH仍然是最快的。•随着标签数量的增加,数据变得更加复杂,搜索变得更具挑战性。从CIFAR-100上所有方法的MAP结果可以看出,它们比CIFAR-10上的结果要差得多。从这些表中的MAP和时间成本结果可以得出结论,SSDH在这些数据集上是有效和高效的。04.2.2精确度-召回率和TopN-精确度曲线。我们在MNIST、MIRFlickr、CIFAR-10和CIFAR-100上分别绘制了精确度-召回率曲线和TopN-精确度曲线,如图1和图2所示。注意,这些图中的一列展示了一个数据集上的结果。从这些图中,我们可以发现:•在精确度-召回率曲线方面,SSDH在所有情况下都比所有基线方法表现更好。•在TopN-精确度曲线方面,在所有情况下,SSDH相对于最佳基线方法提供的性能提升是显著的。特别是当N较小时,SSDH的结果比其他基线方法要好得多。这意味着00.20.40.60.810.10.20.30.40.50.60.70.80.91RecallPrecision@8 bits LSHITQKSHSDHNSHFSDHCOSDISHSSDH(a) MNIST @8 bits00.20.40.60.810.550.60.650.70.750.80.850.90.95RecallPrecision@8 bits LSHITQKSHSDHNSHFSDHCOSDISHSSDH(f) MIRFlickr @8 bits00.20.40.60.8100.10.20.30.40.50.60.7RecallPrecision@8 bits LSHITQKSHSDHNSHFSDHCOSDISHSSDH(k) CIFAR-10 @8 bits00.20.40.60.8100.020.040.060.080.10.120.14RecallPrecision@8 bits LSHITQKSHSDHNSHFSDHCOSDISHSSDH(p) CIFAR-100 @8 bits00.20.40.60.810.10.20.30.40.50.60.70.80.91RecallPrecision@16 bits LSHITQKSHSDHNSHFSDHCOSDISHSSDH(b) MNIST @16 bits00.20.40.60.810.550.60.650.70.750.80.850.90.95RecallPrecision@16 bits LSHITQKSHSDHNSHFSDHCOSDISHSSDH(g) MIRFlickr @16 bits00.20.40.60.8100.10.20.30.40.50.60.70.80.91RecallPrecision@16 bits LSHITQKSHSDHNSHFSDHCOSDISHSSDH(l) CIFAR-10 @16 bits00.20.40.60.8100.10.20.30.40.50.60.7RecallPrecision@16 bits LSHITQKSHSDHNSHFSDHCOSDISHSSDH(q) CIFAR-100 @16 bits00.20.40.60.8100.10.20.30.40.50.60.70.80.91RecallPrecision@32 bits LSHITQKSHSDHNSHFSDHCOSDISHSSDH(c) MNIST @32 bits00.20.40.60.810.550.60.650.70.750.80.850.9RecallPrecision@32 bits LSHITQKSHSDHNSHFSDHCOSDISHSSDH(h) MIRFlickr @32 bits00.20.40.60.8100.10.20.30.40.50.60.70.80.91RecallPrecision@32 bits LSHITQKSHSDHNSHFSDHCOSDISHSSDH(m) CIFAR-10 @32 bits00.20.40.60.8100.10.20.30.40.50.60.70.80.91RecallPrecision@32 bits LSHITQKSHSDHNSHFSDHCOSDISHSSDH(r) CIFAR-100 @32 bits00.20.40.60.8100.10.20.30.40.50.60.70.80.91Reca
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功