2839K-Nearest Neighbors哈希算法何翔宇1，2，王培松1，程建1，2，3R1NLPR，中国科学院自动化研究所，中国2中国科学院大学，中国3中国科学院脑科学与智能技术卓越中心，北京{何翔宇，peisong.wang，jcheng}@ nlpr.ia.ac.cn摘要基于散列的近似最近邻搜索将高维数据嵌入到压缩的二进制代码中，从而实现高效的相似性搜索和存储。然而，非等距sign（·）函数使得必须将连续数据空间中的最近邻投影到离散汉明空间中的最接近码字本文从空间划分的角度重新研究了signn（·）函数具体地说，我们用Shan来弥合k-最近邻和二进制哈希码非 熵 我 们 进 一 步 提 出 了 一 种 新 的 K- 最 近 邻 散 列（KNNH）方法来学习由sign（·）表示的子空间内的KNN的二进制表示。理论和实验结果表明，KNN关系是保持邻域的最重要的方法。bedding，并且所提出的方法在基准数据集上优于现有技术。1. 介绍相似性搜索是机器学习应用中的一个基本问题，如聚类、匹配和分类。随着数据规模的爆炸式增长，穷举搜索、Kd树等数据处理方法受到数据规模和维数的限制。这些问题导致了基于哈希的近似最近邻搜索的繁荣[7，28，29，20]。散列方法将高维数据编码到二进制超立方体的顶点上，同时保持原始数据空间的相似性。保持相似二元码的学习因其计算量小、存储效率高而受到广泛关注。传统的散列方法包括数据无关和数据相关的方法。经典的数据独立方案包括局部敏感散列（LSH）家族[1，6，26，8]，使用随机投影来构造散列函数。毫无疑问，LSH达到了在极高维信息检索中的优势影响尽管如此，LSH仍然是一种效率低下的学习策略。在不考虑输入数据的情况下，LSH的效率严重依赖于编码长度。与数据无关散列的局限性相比，数据相关方法利用数据或语义信息的结构来学习紧凑的二进制表示。现有的数据依赖方法可以进一步分为监督和无监督方案。基于标签的散列，例如具有内核的监督散列[34]、二进制重建嵌入[25]、监督离散散列[39]和保序散列[42]，利用语义标签来优化二进制散列码或聚类之间的汉明距离。最近，深度学习极大地推进了最先进的技术[44，46，4，45，31，30]。语义表示和标签信息都用于深度神经网络来学习哈希码。然而，高性能已经与高计算和存储开销相结合如[12]中所指出的，用于学习二进制代码和用于编码新的测试图像的散列算法应该是高效的和可扩展的。无标签哈希方法专注于数据的自然结构，对标签没有要求。代表性的工作包括迭代量化[12]，锚图哈希[35]，谱哈希[43]，球面哈希[18]，k均值哈希[17]和二进制自动编码器[5]。由于输入特征的冗余，散列方案中的常见初始技术是主成分分析（PCA）[43，13，22]。为了处理方差（即，信息）不平衡，ITQ [12]利用基于最小化量化误差的正交旋转。虽然ITQ仍然是散列中的开创性方法，但仍不清楚失真最小化是否会导致最佳二进制代码。在本文中，我们证明了学习散列函数只从量化误差最小化可能仍然是次优的。受香农熵的启发，我们提出了28402i=1i=1平均量化误差：1.0010-1-一零一(a) PCA对齐。平均量化误差：0.908410-1- 一零一(b) ITQ轮换。平均量化误差：0.909410-1- 一零一(c) KNNH变换图1：K-Nearest Neighbors Hashing（KNNH）的玩具图。二进制嵌入的基本思想是将数据点嵌入到汉明立方体的最近顶点。(a)PCA省去了二进制表示，并将每个聚类划分为不同的顶点。(b)ITQ在最低量化误差的情况下找到了优化的旋转。(c)KNN Hashing努力在旋转过程中保持同一子空间内的k-最近邻（详见第2.4节）。虽然它产生甚至比ITQ更大的量化误差，但所提出的空间分割更接近理想的空间分割。条件熵最小化，这避免了在统一框架内对邻居搜索方案[36，21]的分析sign（·），通过将hashing问题转化为空间划分问题来求解.利用Kozachenko-Leonenko估计，我们进一步证明了条件熵极小化工作：ΣE=||x− d（e（x））||2X该操作鼓励数据点及其k个最近邻共享相同的散列码。如图1所示，所提出的K最近邻散列（KNNH）变换通过将KNN保持在相同的子空间内（即，相同的码字）。大量的实验表明，我们的方法优于国家的最先进的基准数据集，这表明所提出的理论在现实世界中的应用的有效性。2. 方法2.1. 初步形式上，记输入矩阵X∈Rn× d为n个向量X={xi}n的连接.轴对齐的c维超立方体的顶点是{−1，+1}c，记为Bc。一般来说，编码器 bi=sign（ xi）将向量xi∈Rd映射到最近的向量ex esbj∈Bc;因此，我们将Rd分成 2c 个 不 相 交 的 子 空 间 {S1 ， S2 ， . ， 其中，Sj={x|sign（x）=bj}。 给我我的。样本s{xi}n从x∈ Rd的潜在概率密度函数p（x）出发，我们将KNN估计和重新替换应用于非参数估计（见第2.3节）。那么，我们有av ep（bj ）=xp（x，sign（x）=bj）dx=x∈Sjp（x）dx. 对于具有概率质量的离散随机变量Y函数p（Y），定义为H（Y）=−E{logp（y）}= −yp（y）logp（y）。2.2. 均方最小化[11]的作者制定了各种哈希方法[12，41，43]和其他一些近似最近的方法。其中e（·）和d（·）是指编码器和解码器r，例如， x是XR;e（·）是sign（·），d（·）是ITQ [12]中的标量矩阵。最小化E的量化器应该映射任何x到码本中其最近的码字我们认为，这个目标是简单和直观的，但可能不会直接到散列目标。通常的做法是将E转换为众所周知的信噪比（或信噪比）[14]：E（||X||（二）10-1||x− d（e（x））||2）的情况。该目标单独反映了数据的可压缩性，而不是码字相似性。换句话说，失真最小化是一种数据压缩系统，其中E和SNR集中于重构误差的最小化然而，散列的目的是使用码字的最近邻居的近似。不保证优化的压缩导致最接近的码字，因为靠近量化间隔的端点的聚类可以被分成不同的码字。2.3. 条件熵最小化在正交变换的约束下，旋转过程中保持了最近邻的关系。然而，这个好处可能会给我们带来另一个陷阱：正交性是保序的保证。当我们放松离散散列码时，是一个连续的变量，很明显，||2=||xi − xj||2当R T R = I.||2when RTR=I. 但非平滑编码器的存在使得||e（Rxi）−e（Rxj）||2≤2841（v）估计H（B| V）：0.078位10-10.60.50.40.30.20.10估计H（B| V）：0.074位10-11.210.80.60.40.20估计H（B| V）：0.042位10-11.210.80.60.40.20-一零一(a) 随机旋转。-一零一(b) ITQ轮换。- 一零一(c) KNNH变换图2：合同（即， ln（vi;Svi））到H（B|V），显示在colormap中。基于KNN的收缩导联我由于边界附近的混淆点较少，因此条件熵比ITQ旋转低||2一个开放问题（i，j在一个邻域内） 。||2anopenproblem(i,jinaneighborhood). 为了克服这个问题，早期的作品转向宽松的散列函数，例如Sigmoid（·）[42]和tannh（·）[33]，以近似原始问题。 我们证明它是可行的创建特征和散列之间的直接关系我们利用H（B）的替代格式|V），H（B）− H（B |V）= I（B; V）= H（V）−H（V |B）H（B |V）= H（B）− H（V）+H（V|B）。（三）没有近似的代码。为了直接对二进制码字和实值特征之间的联系进行建模，我们绕过了非对于微分熵的估计，我们进一步介绍了-著名的Kozachenko-Leonenko估计量[23]丹光滑sign（·）函数，并对sign（·）划分的子空间感兴趣. 请注意，空间分区中的组件数量通常在H（V）=−（k）+（n）+lncd+ ni=1（4）第一章：一个人的世界概率和统计学习理论，以及最小均方和互信息之间的关系已经在[38，15，16]中讨论过。所有这些工作启发我们在信息论标准中描述散列过程：最小H（B|V）; V = f（X）其中B = sign（V），特征vi来自连续分布，bj是离散输出gallery码。这是其中，f（·）是dig_ amma函数，c_d是d-维单位球，并且k（vi）是距离的两倍v i到它的第k个最近的邻居。与传统的估计的基础上装箱，方程。(4) 具有最小的偏差，并且仅从KNN距离进行估计。这一特性将缓解后来的定义，并导致我们的散列满足h。从等式(4)，我们进一步估计了H_∞（V|B）= jp（v∈Sj）H（V|v∈Sj），消除了在有限区间上的个别积分所产生的误差（E.q. (2))，这样当V已知时，目标最小化B的不确定性。换句话说，最佳特征表示应该使.2002年cH（B|V）=−||SJ|Σ|Σln −容易确定它们的码字。目标符合我们的直觉，但插件n nj=1.丁河方法严重依赖于概率的近似密度函数从形式上讲，-（k）+（n）+ lncd+ni=1lnk（vi）+H（B |V）∫p（v）H（B|V = v）dv（1）v. 2002年cj=1|.|.n--|SJ|）+lncd+Σ≈ −pi、j∫五、b（i，j）logpv，b（i，j）pv（ i）（二）D|SJ|Σni=1ΣΣln k（v i; v∈Sj）.（五）2842其中，pv（i）=iµi（v）dv，估计den的积分第i个bin上的µ sity（v）和p v，b（i，j）=iµi（v∈Sj）dv.显然，将E的右侧Q. (1)作为优化目标。为了跨越障碍，这里|SJ|是指空间S j中的数据点的数量且n_k（v i; v∈ Sj）是v i到Sj中的KNN的距 离的 两倍，g iv ensign（vi）=bj. 请注意，k（vi;v∈Sj）可以是2843i=1i=1FFi=12n12nn4J算法一：无约束KNN哈希。算法2：正交KNN哈希。数据：X ∈ Rn × d的一组数据点{Xi}n。∈Rd的形式数据：X ∈ Rn × d的一组数据点{Xi}n。∈Rd的形式结果：码字B∈ {−1，+1}n×c和变换矩阵W∈Rc×c。X∈Rn×c<$φ（X）;//降维，PCA在这项工作中;而W不收敛V=XW;//这里，f（·）是线性投影;Euclidean-KNN Search（V）∈Nn×k;//返回KNN的索引;对于j= 1：n，Vj<$mean（V[j]）∈R1×c;//更新V，即KNN收缩;结果：码字B∈ {−1，+1}n× c和旋转矩阵R∈ Rc× c。X∈Rn×c<$φ（X）;//降维，PCA在这项工作中;Euclidean-KNNSearch（X）∈Nn×k;//返回KNN的索引;对于j= 1：n，Xj<$mean（X[n]）∈R1×c;//更新X，即KNN收缩;端B，R = arg min||符号（XR）− XR||2个;端W= arg min ||sign（V）− XW ||2个;端B=sign（V）;returnB，W;每个特征点仅在其KNN与Vi处于相同的空间中时才保持其KNN。在这种情况下，我们将双和进行简化-RTR=I//经典哈希问题;returnB，R;一个简单的启发式方法来构造V，它减少了H（B|V）从KNN距离的角度。这一思想源于一种无约束的方法，并通过一个正交优化算法加以改进。约束mationjilnk（vi;v∈Sj） toilnk（vi;Svi）其中Svi ={v|sign（v）=bj=sign（vi）}。 通过将该项代入 Eq. (5) 并 将 双 伽 玛 函 数 逼 近 为 H （ n ） =lnn−1−12+O（1）[2]，H（B|V）可以进一步写为无约束方法如等式所示。(6)，聚类的离群点更有可能落入不同的空间，并且对它的KNN比中心点更敏感换句话说，离群值的（v i; Svi）可能在一个时间内发生巨大变化。丹H（B|V）= nk（vi;Svi）ln+k（vi）向聚类中心迈进一小步，尤其是对于每个特征维数V（i）<$N（0，σ2）.因此，我们建议减少-联系我们term我1−m1m11（六）在基于KNN的集群的卷中的作用，即，KNN收缩为了减轻离群点的影响，我们用每个特征点的k-最近点−2nn j=1 12| S| n=O（n）递归地相邻（在1-nn的情况下从2-nn到k+1-nn仍然是一个局外人）。也就是说，更新后的特征点v_i将是联系我们term II其中m 是满足以下条件的S j的个数：|SJ|=0。 F或mn，很明显，H（B|V）由项I支配，项II接近零。这个结果给我们留下了两个启示：（1）The二值化的信息损失来自边界附近的数据，如图2所示，其中暖色分布在坐标a x es之间;以及2）H（B|（五）应当当vi的KNN都来自同一个空间时，对于m n，第二项仍有下界，1−n−n/12<$−7 ， 我 们 可 以 定 义 一 个 更 大 的 k（vi;Sv）在以下迭代中使用（算法1，2中的for循环事实上，每个特征点都可以看作是与所有其他特征点的加权平均如图2所示收缩台阶对H_∞（B）的降低起着重要作用|V）。 受益于这一信息增益，明尼苏达州||sign（v）−v||2将更好地保留原始特征之间的关系-空间和Hamming空间到目前为止，我们得到了非约束的KNNH，如算法1所示。正交法 虽然无约束的方法2nn12i当k>|SJ|来惩罚单例（带有f e w的空格样品），并平衡对不确定性在两个任期之间。2.4. K近邻散列虽然Eq。(6)它比Eq更具体(1)但标准的落实仍有难度所以我们提出2844如果考虑到（vi;Svi），则有两个-实践中不可避免的问题：1）计算时间，例如，由于大量的计算和内存读写，KNN搜索和while循环中的收缩将花费大量的时间;（2）在无约束条件下，唯一解是平凡解。变换矩阵W最小||sign（V）−XW||F以失去KNN关系为代价，其中大多数数据点2845表1：MNIST数据集上不同代表性无监督哈希方法的比较。每个图像通过其强度表示为784-D（28 ×28）的灰度特征向量。方法汉明排名（mAP，%）N=1000时的精密度精密度（%）@r=21632641632641632LSH[1]20.8825.8331.7137.7750.1661.7325.1055.61上海[43]26.6425.7224.1056.2961.2961.9857.5265.31PCAH[41]27.3324.8521.4756.5659.9957.9736.3665.54SpH[18]25.8130.7734.7549.4861.2769.8551.7164.26KMH[17]32.1233.2935.7860.4367.1972.6561.8868.85ITQ[12]41.1843.8245.3766.3974.0477.4265.7373.14KNNH47.3353.2556.0367.9575.8979.0471.8269.08都装在几个桶里幸运的是，正交约束确实同时解决了这两个问题。由于正交变换保持了向量的长度和向量之间的角度， KNN关系因此，应在生产过程中保持稳定。在这个循环中，i∈Xij（XR）i等价于（i∈XijX i）R，我们可以将KNN搜索和收缩移动到循环之外。注意那么，物体iv e就变成了我的，||sign（v）−v||二、这是一个自然的两阶段方案：基于KNN的收缩和经典的哈希问题，如算法2所示直观地说，人们可 能会认为在原始哈希问题中我们只是用v来代替v，但另一方面，如果我们有满足H（B）的V，|V）=0时，单个“s i g n（·）“应解决散列问题。 在推理时，我们直接应用学习到的对未知数据点的线性投影，即，测试样品，无KNN收缩。3. 结果3.1. 数据集评价方案我们在三个平衡的基准数据集上评估了拟议的K-最近邻哈希（KNNH）：CIFAR- 10 [24]，MNIST [27]和Places 205 [47，3]，我们进一步验证了极不平衡数据集的性能：LabelMe-12-50K [40]. CIFAR-10数据集由10类60，000幅图像组成。每个类别包含6，000个32x32彩色图像。MNIST是一个包含10个类别的70，000个灰色手写数字图像的数据集。每个图像由28x28灰度强度矩阵表示LabelMe-12- 50 K由12类50，000张256 x256JPEG图像组成，类间数据分布不均衡。五个大的样本类占91%的图像，最小的类只包含- ly 0。6%的样本。此外，50%的图像示出了居中的对象，剩余的50%示出了随机选择的图像的该属性与图像检索的现实挑战相匹配。由于其他对象类的实例也可能出现在图像中，因此我们选择具有最大标签值的对象类作为图像标签Places205是一个非常具有挑战性的数据集，因为它的大小和类别数量都很大，包含来自205个场景类别的250万张图像。在[3]之后，我们使用从ImageNet预训练的AlexNet的fc7层中提取的CNN特征，并使用PCA将维数降低到128。我们使用以下评估指标来衡量方法的性能：1）平均精度（mAP），它评估不同对象类的整体性能; 2）汉明半径2的精度（精度@r=2），其测量检索图像的精度具有到查询的汉明距离≤2（如果没有图像满足，则我们报告查询的零精度）;3）精度在N个样本（精度@N），指的是前N个检索样本上的真实邻居的百分比在我们的实验中，我们严格遵循与以前工作相同的比较设置，大部分结果都是作者直接报告的。此外，为了提高统计稳定性，我们重复了10次实验，并以平均值作为最终结果。由于小样本类的性能对查询更敏感，我们在LabelMe-12- 50 K上执行了50次实验，以获得更好的性能。结果。为了证明minH（B|X）导致比直接量化最小化更好的码字，用ITQ解决了KNNH中的问题，并在不同的数据集上对两种方法进行了比较。3.2. 平衡数据集上的结果按照[32，9]中的相同设置，我们从CIFAR-10中随机选择1000个样本，每个类100个作为查询数据，其余59000个图像作为图库集。对于MNIST数据集，我们每类随机抽取100张，总共1000张图像，作为查询数据，并使用剩余的69000张图像作为图库集。查询的基本事实基于它们的类标签。由于散列方法是独立的输入功能，我们比较我们的方法与代表性散列使用手工制作和深度功能。在本小节中，我们将k设置为20，并且不进行微调。2846表2：CIFAR-10数据集上不同代表性无监督哈希方法的比较。每个图像被表示为512-D GIST特征向量。方法汉明排名（mAP，%）N=1000时的精密度精密度（%）@r=21632641632641632LSH[1]12.5513.7615.0716.2119.1022.2516.737.07上海[43]13.1912.9713.1817.7417.9318.4319.4221.73PCAH[41]13.2312.8912.3017.8617.9116.9121.803.00SpH[18]14.5415.1615.9019.6821.3023.0021.9214.53KMH[17]16.0516.1915.7921.2122.5622.8323.4812.80ITQ[12]16.5717.3417.9122.0823.9825.2123.9216.90KNNH17.3218.7619.5422.5225.4827.0823.3615.05表3：深度学习方法和监督方法的比较。顶部是无监督方法，底部是有监督方法（从SDH开始）。方法汉明排名（mAP，%）N=1000时的精密度精密度（%）@r=21632641632641632CIFAR-10查询= 1，000Deepbit[31]14.3516.3317.97–––––卫生署[32]16.1716.6216.9623.7926.0027.7023.3315.77UHBDNN[9]17.8318.52––––24.9718.85KNNH17.3218.7619.5422.5225.4827.0823.3615.05MNIST 查询= 1，000卫生署[32]43.1444.9746.7467.8974.7278.6366.1073.29UHBDNN[9]45.3847.21––––69.1375.26KNNH47.3353.2556.0367.9575.8979.0471.8269.08[第32话]46.7551.0152.5065.1970.1872.3363.9277.07苏丹人民解放军[41]44.2048.2948.3462.9867.8967.9963.7174.06BRE[25]33.3435.0936.8060.7268.8673.0834.0964.21表1显示了MNIST数据集上不同散列方法的检索结果。每个图像通过使用其强度由784维灰度特征向量表示[37]。显然，KNNH在几乎所有标准上都优于其他代表性的无监督散列方法。表2在CIFAR- 10数据集上获得了相同的结果KNNH主要贡献于mAP的增加，mAP直 接 反 映 了 重 呼 顺 序 的 变 化 。 请 注 意 ， KNNH 的precision@r=2值不是很好，但p@r=2实际上不同于众所周知的R-precision，它描述了精度-召回率曲线上的一个点（我们使用p@r=2，因为它在最近的深度哈希中很流行）。在我们的实验中，虽然KNNH的p@r=2值相当差，但KNNH的召回率在r=2时比基线高得多。在相同召回率的情况下，比较不同PR曲线上两个点的精度是常见的这是同一个案例。由于r=2可以是一个经验设置，以减少检索结果的数量，我们还显示了precision@1K的值作为替代。尽管深度无监督哈希方法受到了极大的关注，但我们证明了线性变换可以获得有竞争力的结果。由于Deepbit在[31]中报告了mAP@1K而不是mAP，因此我们重新编译了开源代码并在表3中报告了更新的mAP。与深度哈希相比，我们的方法仍然领先于32/64位的mAP有趣的是，KNNH甚至超过了MNIST上的一些监督方法。在[46，45，9，19]中，作者使用预训练的CNN特征作为非基于CNN的哈希方法的输入，所有方法在大多数评估指标中都实现了更高的性能根据该设置，我们使用VGG特征作为CIFAR-10的输入，并设置类似的实验。查询集包含6，000个随机采样的图像（每个类10%的图像），其余54，000个图像用作图库集。对于MNIST数据集，由于MNIST是灰度的，我们评估了GIST 512-D描述符的性能。与CIFAR-10相似，我们在每个类别中随机抽取10%的图像作为查询数据，并使用剩余的图像作为训练集和检索数据库。表4显示2847表4：使用高级特征的不同无监督方法的mAP（%）。 我们报告了使用VGG-FC 7描述符和使用GIST 512-D描述符的MNIST在RGB数据集（CIFAR-10，LabelMe）上的结果。方法CIFAR-10LabelMe-12-50KMNIST163264163264163264VGG+SH[43]18.3116.5415.7812.6012.5912.2432.5933.2330.65VGG+SpH[18]18.8220.9323.4013.5915.1017.0331.2736.8041.40VGG+KMH[17]18.6820.8222.8713.3615.4716.5831.9637.3941.11VGG+BA[5]25.3826.1627.9916.9618.4220.8048.4851.7252.73VGG+ITQ[12]26.8227.3828.7318.0619.4020.7146.3750.5953.69VGG+KnNH29.0630.8232.6020.1323.7926.2253.0761.1165.55表5：与ITQ[12]在不平衡数据集的小样本类上的比较。报告了使用GIST 512-D和VGG-FC 7描述符的mAP（%，32位）比例反映的是每一类的数量占整个样本的比例。LabelMe-12- 50 K中的所有小样本类类比例签署百分之二点五门二点二书架百分之一点零椅子百分之一点一表百分之零点六键盘百分之零点九头百分之零点七汉明排名（mAP，%）ITQ[12]KNNH3.463.804.764.822.432.501.381.420.740.756.9412.751.561.86VGG+ITQ[12]5.444.0512.333.721.319.767.92VGG+KnNH7.194.7919.424.991.4220.4814.61增加1.32×1.18×1.58×1.34×1.08×2.10×1.84×随着位宽的增加，我们的方法始终优于其他方法。3.3. 不平衡数据集的结果数据不平衡问题一直是机器学习领域的一个热门话题。在本节中，我们评估了KNNH在极不平衡数据集：LabelMe-12- 50 K。由于最小的类只包含100000张图像，我们在每个类中随机选择10%的图像作为查询数据，并使用10000000张图像作为图库集。查询的基本事实基于他们的阶级标签。在本小节中，我们将k设置为20，并且不进行微调。为了避免结果被大样本类别所支配，我们在表4中报告了mAP毫无疑问，KNNH在16/32/64位上处于领先然而，总体表现不足以令人信服，我们在表5中进一步报告了所有小班的mAP结果表明，KNNH确实优于国家的最先进的方法在困难的检索任务。此外，结合鉴别特征，KNNH进一步提高了散列的质量与位宽的增加。在某些情况下，我们实现了200%的改进，但老实说，我们的结果仍然很差。1 .一、42%的mAP显然是一个很大的调查空间。3.4. 大规模数据集上的结果为了应对现实世界的挑战，我们进一步在大规模Places205数据集上评估KNNH [47]。我们从每个类中随机抽取100个图像，构建一个包含20，500个图像的测试集，并使用其余的图像。5M图像作为检索集。查询的基本事实基于他们的阶级标签。由于Places205比以前的数据集大得多，我们将k改为200，并且没有进行微调。如表6所示，我们的方法一致地超过了mAP上代表性的无监督哈希方法。3.5. 各种kk-nn算法的性能会因k的选择而严重下降.但是，一个有效的方法应该在很宽的k范围内实现一致的性能。图3显示了我们方法的鲁棒性。KNNH始终优于领先的方法，很大的差距。 结果令人信服，我们的16- 位KNNH已经超过了MNIST数据集上的64位ITQ。3.6. 计算时间最后，对实际应用中的计算时间进行了分析.因为我们没有引入额外的计算或存储，284864位KNNH32位KNNH16位KNNH64位ITQ地图表6：Places205数据集上不同代表性无监督哈希方法的比较。每个图像都由从AlexNet-FC 7中提取的CNN特征表示，并使用PCA将维数降低到128。方法汉明排名（mAP，%）N=1000时的精密度精密度（%）@r=21632641632641632SpH[18]3.365.157.458.8314.3519.545.6718.84上海[43]4.446.678.5011.3817.5722.117.3622.44PCAH[41]4.667.6010.7411.8919.2825.638.2224.60KMH[17]4.787.6510.6012.1019.2225.328.2924.65英国广播公司[5]5.739.6513.4412.4020.2426.037.9623.65ITQ[12]5.899.6913.5312.5320.1626.287.9923.32KNNH7.6012.1715.9213.4521.0426.438.7619.9919.55619.05418.55218.0504817.517.05 10 15 2025K(a) CIFAR-10。465 10 15 20 25K(b) MNIST。图3：不同k下CIFAR-10和MNIST与ITQ的比较。我们报告了使用GIST 512-D描述符和使用784-D（28×28）强度特征向量的MNIST在由于ITQ与k无关，因此性能与两个图中的蓝色实线相同。在推理时间上，KNNH算法与第二阶段哈希算法保持相同的速度。在我们的实验中，KNNH在32位Cifar-10上的测试时间为1。7×10−6秒，Intel 3.0GHz CPU。因此，我们重点研究了KNN搜索和KNN的训练时间，收缩形式上，给定d维特征，KNN收缩具有线性时间复杂度：时间复杂度为O（n）（大约是k次内存读取，n次内存写入，（k-1）次加法/减法和nd次乘法）。 因此，我们认为，KNNH的主要问题是它在递归KNN搜索中的巨大复杂性：时间复杂度为O（n2logn），时间复杂度为O（n2d）.通过利用GPU在并行计算上的强大功能[10]，我们将CIFAR-10（32位）上的搜索时间从27.06秒减少到1.81秒（3.00GHz Intel CPU vs. Nvidia TITAN Xp）。MNIST和LabelMe在32位上的计算时间相似，分别为2.43秒和1.09秒。对于Places205，训练时间大约是110分钟，因为k是比在小数据集上训练大10倍，并且巨大的数据大小限制了GPU的进一步加速。另外，我们注意到特征点的维数只有很小的-l对计算时间的影响，这使得有可能以增加位宽来实现更高的性能。一般来说，我们的训练方法可以在合理的时间内实现，而不会失去运行时速度的性能。4. 结论在散列码的学习过程中，我们引入了一个隐藏因子，即子空间中的k-近邻关系。采用条件熵最小化的观点，进一步提出了一种简单而有效的提高哈希质量的方法。 总之，我们通过k-近邻在二进制码字和输入特征之间建立了一个直接的连接。未来的工作应该将这些结果扩展到其他数据集。直接最小化H（B|（五）值得进一步探讨。5. 确认本 工 作 得 到 了 国 家 自 然 科 学 基 金 项 目（No.61876182，61872364）和中国科学院重大科技攻关项目（No.XDB32050200）的部分资助64位KNNH32位KNNH16位KNNH64位ITQ地图2849引用[1] 亚历山大·安多尼和彼得·因迪克。高维近似最近邻的近优散列算法。Commun. ACM，51（1）：117 -122，2008.[2] J. M. Bernardo算法103：Psi（digamma）函数。皇家统计学会杂志。Series C（Applied Statistics），25（3）：315 -317，1976.[3] FatihCaki r，KunHe，SarahAdelBa rg al，andStanSclaro f f.Mihash：基于互信息的在线哈希算法。在IEEE国际计算机视觉会议，ICCV 2017，意大利威尼斯，2017年10月22日至29日，第437[4] Yue Cao，Mingsheng Long，Jianmin Wang，Han Zhu，and Qingfu Wen.用于高效图像检索的深度量化网络。第三十届AAAI人工智能会议论文集，2016年2月12日至17日，美国亚利桑那州凤凰城。，第3457-3463页[5] 米格尔·A'. Carreira-Perp ina´ nandRaminRaziperchi k olaei.使用二进制自动编码器进行散列。 在IEEE会议计算机视觉和模式识别，CVPR 2015，波士顿，MA，美国，2015年6月7-12日，第557-566页，2015年。[6] 摩西·查瑞卡来自舍入算法的相似性估计技术。在Proceedings on 34th Annual ACM Symposium on Theory ofComputing，May 19-21，2002，Montr e′ al，Qu e′ bec，Canad a，pages380-388，2002。[7] 程建，冷聪，吴家祥，崔海南，陆汉庆.用于三维重建的级联散列快速精确图像匹配。在2014年IEEE计算机视觉和模式识别会议，CVPR 2014，美国俄亥俄州哥伦布，2014年6月23-28日，第1-8页[8] Mayur Datar、Nicole Immorlica、Piotr Indyk和Vahab S.米罗克尼基于p-稳定分布的局部敏感哈希算法。在Proceedings of the 20th ACM Sym-10 th on ComputationalGeometry，Brooklyn，New York，USA，2004年6月8-11日，第253-262页[9] Thanh-Toan Do Anh-Dzung Doan和Ngai-Man Cheung。学习使用二进制深度神经网络进行哈希。在ComputerVision-ECCV2016-14thEuropeanConference ，Ambassador，The Netherlands，October 11-14，2016，Proceedings，Part V，pages 219[10] 文森特·加西亚，埃里克·德布鲁夫，米歇尔·巴洛。使用GPU的快速k近邻搜索。在IEEE计算机视觉和模式识别会议，CVPR研讨会2008，安克雷奇，AK，美国，2008年6月23-28日，第1-6页，2008年。[11] 葛铁铮，何开明，柯启发，孙建。优化的产品量化近似最近邻搜索。在2013年IEEE计算机视觉和模式识别会议上，美国俄勒冈州波特兰，2013年6月23-28日，第2946-2953页[12] Yunchao Gong，Svetlana Lazebnik，Albert Gordo，andFlorent Perronnin.迭代量化：学习二进制代码用于大规模图像检索的procrustean方法。IEEE传输模式分析马赫内特尔，35（12）：2916[13] 艾伯特·戈多，弗洛朗·佩龙宁，龚云超，斯韦拉娜·拉泽布尼克. 二进制嵌入的非对称距离叮。 IEEE Trans. 模式分析马赫内特尔，36（1）：33[14] R. 格雷矢量量化IEEE ASSP Magazine，1（2）：4[15] DongningGuo，ShlomoShamai，andSe r gioVer du'. 高斯信 道 中 的 互 信 息 与 最 小 均 方 误 差 。 IEEE Trans.Information Theory，51（4）：1261 - 1282，2005.[16] DongningGuo ， YihongWu ， ShlomoShamai（Shitz），and Se r gioVer du'. 高斯噪声中的估计：最小均 方 误 差 的性 质 IEEE Trans. Information Theory ， 57（4）：2371[17] 何开明，方文，孙建。K-means哈希：学习二元紧码的一种保仿射量化方法。在2013年IEEE计算机视觉和模式识别会议上，美国俄勒冈州波特兰，2013年6月23-28日，第2938-2945页[18] Jae-Pil Heo 、 Youngwoon Lee 、 Junfeng He 、 Shih-FuChang和Sung-Eui Yoon。球形散列。在2012年IEEE计算机视觉和模式识别会议上，Providence，RI，USA，2012年6月16-21日，第2957-2964页[19] Tuan Hoang，Thanh-Toan Do，Dang-Khoa Le Tan，andNgai- Man Cheung.增强非监督散列的特征鉴别。在2017年IEEE图像处理国际会议，ICIP 2017，中国北京，2017年9月17日至20日，第3710-3714页[20] 胡
