用可变位编码进行哈希的非对称学习

摘要

最近邻搜索(NNS)是大数据检索的核心。学习哈希是通过将高维数据表示成紧凑的二进制代码来解决这一问题的有效方法。然而，现有的学习哈希方法需要长位编码来保证查询的准确性，而长位编码带来了较大的存储成本，这严重限制了长位编码在大数据应用中的应用。针对这一问题，提出了一种可变位编码的非对称哈希学习算法。AVBH哈希算法使用两种哈希映射函数将数据集和查询集编码为不同长度的位。对于数据集，统计分析数据集经过随机傅里叶特征编码后的哈希码频率。频率高的哈希码被压缩成较长的编码表示形式，频率低的哈希码被压缩成较短的编码表示形式。查询点被量化为长位哈希码，并与相同长度的级联数据点进行比较。在公共数据集上的实验表明，该算法有效地降低了存储成本，提高了查询的准确性。

1.介绍

给定一个查询对象/点和一个数据集，最近邻搜索(NNS) [1- - - - - -3.就是把最近的邻居退回来来．目前，网络神经网络广泛应用于图像检索、文本分类和推荐系统等领域。然而，随着数据规模的指数级增长和高数据维数的灾难，网络神经网络问题比以前更加难以解决。因此，新的高效的相似度搜索索引结构和查询算法日益成为该问题的研究重点。

基于哈希的NNS方法[3.- - - - - -5引起了广泛关注。一般情况下，哈希方法可以将局部保留的原始数据投影到一个低维汉明空间，即二进制码[4- - - - - -6]．这些方法的复杂性总是在次线性时间内。此外，哈希方法只需要简单的位运算来计算汉明编码的相似度，速度非常快。随着大规模数据检索的高性能，哈希技术在促进跨视图检索任务方面得到了越来越多的关注[7，8，联机检索任务[9，以及度量学习任务[10]．

对于大规模的数据检索，时间和空间成本是两个重要的问题。众所周知，现有哈希方法的精度受到哈希编码长度的限制，通常需要较长的编码来获得更好的精度。但是，长编码会增加空间成本、网络通信开销和响应时间。

为了解决这个问题，一种编码量化机制[11]基于非对称哈希算法[12提出了]。与直接哈希码比较不同，将数据点的编码级联到与查询点相同的编码长度，有效地降低了数据集的编码存储成本，保证了结果的准确性。但该算法对所有数据采用统一的压缩方法，忽略了数据分布的影响。实际上，大规模数据的分布通常是不均匀的。因此，对于大多数哈希算法来说，量化的频率也是不同的。我们知道，较长的编码可以保留大部分原始信息;然而，这将带来高成本，反之亦然。需要研究准确性、计算开销和节省空间之间的权衡。从直观上看，高密度数据需要较长的编码长度，以确保尽可能地保留原始信息，而低密度数据可以使用较短的编码长度，仍然保留大部分原始信息。这就是我们算法背后的思想。

提出了一种非对称学习变位哈希编码算法(AVBH)。AVBH使用两种哈希映射函数分别对数据集和查询集进行量化，对不同长度的哈希码进行编码。具体来说，通过随机傅里叶编码计算数据集的频率，然后将频率高的随机傅里叶编码压缩成较长的哈希码表示，将频率低的随机傅里叶编码压缩成较短的哈希码表示。

本文的主要贡献如下:(1)一个变量位编码机制(名为AVBH)提出了基于散列码频率压缩,使编码空间的有效利用,和(2)实验表明,AVBH可以有效降低存储成本,提高查询的准确性。

2.预赛和描述

在本节中，我们将回顾LSH(位置敏感哈希)的一些基本知识[13- - - - - -15，矢量量化[16，以及乘积量子化[17这对我们所提议的技术是至关重要的。

２.１.矢量量化

矢量量化(VQ)是一种经典的数据压缩技术，它将原始数据压缩成离散的矢量。为一个向量的尺寸，形式上是一个VQ函数可以指定为，在哪里(与维度)是原始数据/向量，是预先训练过的代码集吗密码本里有密码吗．VQ函数的目标是将原始实数向量量化到VQ损耗最小的最接近的码字。这里是矢量的VQ损失是由

２.２.产品量化

乘积量化(PQ)是向量量化的一种优化方法。首先，对特征空间进行划分互相排斥的子空间，然后使用VQ对每个子空间分别量化。即每个子空间的编码形成一个小码本，小码本形成大码本通过笛卡尔积。在这种方法中，可以将高维数据分解为低维空间，可以并行处理。假设一个对象是由码字，矢量乘积量化的损失是由

2．3.随机傅里叶特征

传统的降维方法，如PCA，是将数据映射到独立特征空间，计算出主要的独立特征。该方法忽略了样本分布的非线性信息，不能很好地应用于实际数据。基于随机傅里叶特征(RFF)的特征映射方法，将数据映射到近似核函数下的特征空间，并将特征空间下任意两点的内积近似为其核函数值。与PCA方法相比，RFF可以通过降维或升维来最大化数据分布信息，获得维特征。这种特性适用于特征压缩处理。SKLSH [18]是一种基于RFF的经典哈希算法，在长位数字编码下具有良好的实验结果。

长度编码哈希学习算法首先从原始样本点映射样本点实空间的维数RFF近似核函数特征空间的维数。由于RFF一致性的收敛性，使得任意两个样本点之间的核函数相似性得以保持。

具体来说，有两点，平移不变核函数[12］满足下式: 在哪里，满足均匀分布，服从概率分布由平移不变核函数导出为常数参数。

因此，从维空间到特征空间维数近似核函数可由下式求得: 在哪里对于相同意义的抽样是否服从概率分布和服从同分布抽样，该抽样在服从之间均匀分布．当平移不变核函数是高斯核函数时，，为高斯分布，即，．

２.４.普罗克汝斯忒斯正交问题

正交Procrustes问题是求解一个正交变换矩阵，这是最接近,例如, 在哪里．该公式不易直接求解，可采用交替优化的方法进行优化。也就是说,这个矩阵第一个是固定的，还有矩阵优化使目标函数值降低。然后矩阵是固定的，那么正交变换矩阵呢优化使目标函数值降低。

3.使用可变位编码进行哈希的非对称学习

３．１．算法框架

对于一般的哈希学习算法，通过学习得到的哈希码的长度总是固定的。AVBH采用了非对称哈希算法的思想，即数据集的哈希代码短而不固定，代码的查询点长而固定。AVBH哈希算法的步骤如图所示1，主要包括数据集编码步骤①-③和查询点编码步骤④。

数据集编码部分包括两个阶段:随机傅里叶特征编码(RFF编码)和可变位编码(AVBH编码)。首先，步骤①使用随机傅里叶特征(RFF)对数据集进行映射，得到RFF编码。RFF编码后，考虑到RFF编码频率的差异，按照步骤②对RFF编码频率进行排序。根据需求，可以将原始数据集以RFF代码为长度划分为子集如图所示。如步骤③所示，AVBH子集编码的长度可以通过复制复制吗乘以，然后是汉明码维形成。

在查询点编码部分，将查询点量化编码为长度的RFF编码④通过一步。

３.２．目标函数

AVBH方法的目标是得到长度为的哈希编码组通过哈希函数，也就是说, 在哪里，．

这就划分了数据集根据RFF编码频率划分为子集。通过级联我们可以分别得到集团散列码。例如,

然后结合得到一个整个数据集的位长哈希码．AVBH方法通过在查询过程中计算查询点哈希码与连接数据集之间的汉明距离来计算相似度。因此，对于数据集，我们需要构造哈希映射函数，以便组哈希码的长度，分别，可以尽可能地保留原始信息。因此，AVBH方法通过重构误差(8)之间的最小级联编码和维样本向量：在哪里是正交旋转矩阵,即．

结合结合矩阵的性质和定义F-范数，可以得到:

作为未知变量在公式(8)为乘积关系，展开式(9)中包含两项未知变量，因此很难求解。进一步化简后，可得公式:

作为，这很容易得到．作为，我们可以得到这个无关和．作为一个结果, ，在哪里无关．因此公式(10)简化如下:

因此，最小化重新配置错误(8)等于最小化量化误差(11)．

AVBH对数据集进行编码的目标函数是最小化拼接编码的重构误差通过求正交旋转矩阵．在均匀分布的数据集的极端情况下，数据集的哈希编码频率没有显著差异，AVBH方法退化为ACH算法[16]．与ACH哈希算法相比，AVBH哈希算法更适合于真实数据，因为它能适应各种分布的数据，泛化能力更强。

３．３．优化算法

目标函数(11)可通过交替优化进行优化。也就是旋转矩阵第一个是固定的，和编码矩阵优化使目标函数值降低。然后编码矩阵是固定的和旋转矩阵优化使目标函数值降低。这样，目标函数的值就会减小，直到收敛。下面讨论如何调优和优化目标函数的值。（1）固定旋转矩阵，并对编码矩阵进行优化．鉴于，矩阵是由什么组成的行行,列列的．从公式(11)，则可得下式: 作为无关，对于一个固定的，最小化的问题(12)等于下式的最大化问题: 作为，式的最优解析解(13)是由（2）修正编码矩阵，并优化旋转矩阵．

下，最小化公式的问题(11)等于正交Procrustes问题[9]．这类问题的最优解为如下:

因此，有了优化问题求公式(15)等于下式的最大化问题:

通过计算的奇异值分解，我们可以得到如下公式: 在哪里是由左奇异值向量，是由右奇异值向量组成的矩阵，是一个由相应的奇异值向量组成的对角矩阵，其中的对角元素是．

通过组合公式(16)和(17)，则可得下式:

鉴于，，的对角元素是，和，分别代表了行，．通过Cauchy-Schwarz不等式[11，则得到下式:

因此公式(18)可以写成公式(20.)：

结合公式(19),当，公式(20.)取最大值。为，我们可以得到如下公式: 当，公式(16)取最大值，公式(15)取最小值。因此，我们可以通过公式(21)．

3．4．编码功能

3.4.1。数据编码

当目标函数值收敛时，可以得到映射函数的AVBH数据集，根据公式(14),随机傅里叶特征(RFF)是由样本点的映射阶段获得的吗：

3.4.2。查询点编码

最优旋转矩阵可以从数据集编码的训练过程中得到。为数据在查询集中，编码的主要目标是保持尽可能多的准确信息，因此查询集编码不需要压缩，也不需要映射到长度位的哈希码。结合公式(14)，则得到AVBH到查询集的映射函数:

3．5．AVBH的收敛分析

根据目标函数(8)，则可得式如下: 在哪里是一个(1)中各元素的正负符号和在，(2)每个元素是不是大于元素中对应的位置．

因此，优化目标为转化为两个次优化问题，即和．特别是对于子问题，公式(14)给出最优解。因此，可以保证公式(14)小于或等于前面获得的值。的子问题，公式(21)给出最优解。因此，也可以保证公式(21)小于或等于前面获得的值。

结合两部分，(14)和(21)可以保证更新后的值小于更新前获得的值。我们可以得出AVBH算法是收敛的。

4.实验结果

实验计算机采用Intel Core i5-2410M CPU和8gb DDR3内存。我们比较了AVBH与几种典型哈希方法的性能:ACH [12], ITQ [19],公里[20.], PCAH [21]和LSH [13]．

4．1.实验数据集

以下4.4.1。CIFAR-10¹

它是一套60000 -32 × 32的彩色图像，分为10个类别，每个类别包含6000幅图像。在本实验中，对数据集中的每幅图像提取320-D的gist特征。我们随机选取1000张图像作为测试数据，其余59000张作为训练数据。在训练数据中，将与测试数据点最近的50个数据点(基于欧氏距离)视为其最近的邻居。

4.1.2。筛选²

它是一个包含1,000,000张128-D图像的局部SIFT特征集。随机选取其中10万张样本图像作为训练数据，其他样本图像1万张作为测试数据。

4.1.3。要点^3.

它是一个包含1,000,000张960-D图像的全局GIST特征集。随机选取50万张样本图像作为训练数据，1000张样本图像作为测试数据。

4．2．绩效评估

AVBH的性能主要通过查询的准确性(精度)和召回率(召回率)之间的关系来评价。我们定义

为了公平起见，将AVBH的平均编码长度设置为给定数据集下其他方法的编码长度。

数据2- - - - - -4在CIFAR-10、SIFT和GIST上，利用欧几里得邻域真实值进行欧几里得邻域检索，得到了精确查全曲线。本文提出的AVBH方法在四组数据集上都有较好的精度表现。由于AVBH算法使用的是可变位码，所以总码长小于其他算法。该方法有效地降低了存储成本，提高了查询的准确性。

(一)

(b)

(c)

(d)

(一)

(b)

(c)

(d)

(一)

(b)

(c)

(d)

5.结论

提出了一种非对称学习变位哈希编码算法。通过对数据集进行随机傅里叶特征编码的频率统计，将高频哈希码压缩成较长的编码表示，将低频哈希码压缩成较短的编码表示。对于查询数据，我们将其量化为长位哈希码，并与相同长度的级联数据点进行比较，以检索最近邻。这样可以确保在压缩数据的同时尽可能地保留原始数据信息，从而最大限度地平衡编码压缩和查询性能。在开放数据集上的实验表明，该算法有效地降低了存储成本，提高了查询的准确性。由于我们使用两阶段算法框架生成哈希码，训练阶段需要花费大量时间。在今后的工作中，我们将致力于简化培训流程。

数据可用性

本文实验的数据集如下:(1) CIFAR-10(可在http://www.cs.toronto.edu/∼kriz / cifar.html):一套60,000-32 × 32彩色图像，分10个类别，每个类别包含6000幅图像。在本实验中，对数据集中的每幅图像提取320-D的gist特征。我们随机选取1000张图像作为测试数据，其余59000张作为训练数据。在训练数据中，将与测试数据点最近的50个数据点(基于欧氏距离)视为其最近的邻居。(2) SIFT(可在http://corpus-texmex.irisa.fr):是一个包含1,000,000张128-D图像的局部SIFT特征集。随机选取其中10万张样本图像作为训练数据，其他样本图像1万张作为测试数据。(3) GIST(可于http://corpus-texmex.irisa.fr):它是一个包含1,000,000张960-D图像的全局GIST特征集。随机选取50万张样本图像作为训练数据，1000张样本图像作为测试数据。

的利益冲突

作者声明他们没有利益冲突。

致谢

国家自然科学基金面上项目(no . LZ20F020001, no . LY20F020009)和国家自然科学基金面上项目(no . 61472194, no . 61572266)，以及宁波大学K. C. Wong Magna基金面上项目。

参考文献

C. S. Anan和R. Hartley，“用于快速图像描述符匹配的优化kd -树”2008年IEEE计算机学会计算机视觉与模式识别会议论文集，第1-8页，IEEE, Anchorage, AK, USA, 2008年6月。视图:出版商的网站|谷歌学者
“基于相似自适应和离散优化的无监督深度哈希算法”，中国科学(d)，IEEE模式分析与机器智能汇刊，第40卷，第5期。12, pp. 3034-3044, 2018。视图:出版商的网站|谷歌学者
曲昕，易文，王涛，肖磊，刘铮，“基于混合整数线性规划模型的助教分配与扩展，”科学的规划， vol. 2017, Article ID 9057947, 7 page, 2017。视图:出版商的网站|谷歌学者
张志刚，邹青，王强，林颖，李强，“多标签图像检索的实例相似度深度哈希算法”，2018，https://arxiv.org/abs/1803.02987v1．视图:谷歌学者
H.-F。Yang, K. Lin和c - s。Chen，“基于深度卷积神经网络的语义保持哈希的监督学习”，模式分析与机器智能学报，第40卷，第5期。2，第437-451页，2018。视图:出版商的网站|谷歌学者
S. Berchtold, D. A. Keim，和H. P. Kriegel，“x树:高维数据的索引结构”，刊于第22届超大数据库国际会议论文集，第28-39页，印度孟买，1996。视图:谷歌学者
沈旭东，刘伟，曾伟伟，q- s。太阳,Y.-S。Ong，“通过交叉视图搜索的多标签预测，”神经网络与学习系统，第29卷，第2期9、第4324-4338页，2018。视图:出版商的网站|谷歌学者
沈旭东，沈飞，沈庆生。孙永华，杨永华。Yuan, and H. T. Shen，“半对离散哈希:学习潜在哈希码的半对交叉视图检索，”IEEE控制论汇刊，第47卷，第47期。12, pp. 4275-4288, 2016。视图:出版商的网站|谷歌学者
黄立坤，杨强，郑文生，《在线哈希》，IEEE神经网络与学习系统汇刊，第29卷，第2期6, pp. 2309-2322, 2017。视图:出版商的网站|谷歌学者
M. M. Bronstein, A. M. Bronstein, F. Michel，和N. Paragios，“使用相似敏感哈希的跨模态度量学习的数据融合”，在计算机视觉与模式识别，2010， 2010年6月，美国旧金山，IEEE。视图:谷歌学者
A. Gordo, F. Perronnin, Y. Gong, S. Lazebnik，《二元嵌入的不对称距离》，IEEE模式分析与机器智能汇刊第36卷第2期1, pp. 33-47, 2014。视图:出版商的网站|谷歌学者
吕颖，吴文文，曾志，杨德胜，陈p.p.k.，“大规模图像检索的非对称循环哈希算法”，IEEE多媒体汇刊，第十七卷，第二期8, pp. 1225-1235, 2015。视图:出版商的网站|谷歌学者
A. Gionis, P. Indyk，和R. Motwani，“通过哈希的高维相似性搜索”，在第25届超大数据库国际会议论文集，第8卷，第2期2，第518-529页，爱丁堡，苏格兰，1999。视图:谷歌学者
钱军，朱琪，陈慧卿，“多粒度位置敏感bloom过滤器”，IEEE计算机汇刊号，第64卷。12, pp. 3500-3514, 2015。视图:出版商的网站|谷歌学者
邓超，陈振中，刘旭东，“基于三组的深度哈希网络的跨模态检索，”IEEE图像处理汇刊第27卷第2期8, pp. 3893-3903, 2018。视图:出版商的网站|谷歌学者
R. Salakhutdinov和G. Hinton，“语义哈希”，国际近似推理杂志，第50卷，第5期。7, pp. 969-978, 2009。视图:出版商的网站|谷歌学者
W. Kong和w - j。“各向同性哈希”神经信息处理系统研究进展， p. 1655-1663, Curran Associates Inc.， New York, NY, USA, 2012。视图:谷歌学者
M. Raginsky， "位移不变内核的位置敏感二进制代码"神经信息处理系统研究进展， Curran Associates Inc.，纽约，纽约，美国，2009。视图:谷歌学者
Y. Gong, S. Lazebnik, a . Gordo，和F. Perronnin，“迭代量化:用于大规模图像检索的二进制代码学习的procrustean方法”，模式分析与机器智能学报第35期12, pp. 2916-2929, 2013。视图:出版商的网站|谷歌学者
何文发，孙建平，“K-means哈希:学习二进制紧致码的一种保持亲和的量化方法”，发表于2013 IEEE计算机视觉与模式识别会议论文集2013年6月，美国俄勒冈州波特兰。视图:出版商的网站|谷歌学者
6 .刘波，钟磊，刘波。基于无监督PCA哈希的大规模医学图像搜索2013 IEEE计算机视觉与模式识别研讨会论文集，第393-398页，IEEE，波特兰，OR，美国，2013年6月。视图:出版商的网站|谷歌学者

科学的规划