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

摘要

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

1.介绍

给定查询对象/点和一个数据集 ，最近的邻居搜索（nns）[1- - - - - -3.就是把最近的邻居放回去至 ．如今，NNS广泛用于许多应用中，例如图像检索，文本分类和推荐系统。然而，随着数据量表的指数增长和高数据量度的灾害，NNS问题现在比以前更难以解决。因此，用于相似性搜索的新高效索引结构和查询算法越来越成为问题的重点。

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

对于大规模的数据检索，时间和空间成本是两个重要问题。如我们所知，现有散列方法的准确性受哈希编码长度的限制，并且通常需要更长的编码来获得更好的准确性。然而，长编码将增加空间成本，网络通信开销和响应时间。

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

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

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

2.预赛和描述

在这一节中，我们将复习LSH(位置敏感散列)的一些基本知识[13.- - - - - -15.]，矢量量化[16.，产品量化[17.这对我们提出的技术至关重要。

2.1。矢量量化

矢量量化（VQ）是一种经典数据压缩技术，它将原始数据压缩到离散矢量中。对于矢量的维，形式上是VQ函数可以指定为 ，在哪里（和尺寸）是原始数据/矢量，是一个倒托级代码集，是码本的代码字 ．VQ函数的目的是通过最低VQ损耗量化原始实数向量到最近的码字。这里，VQ丢失的矢量是（谁）给的

2．2．产品量化

乘积量化(PQ)是矢量量化的一种优化方法。首先，对特征空间进行划分互斥子空间，然后利用VQ对每个子空间分别进行量化。也就是说，每个子空间的编码形成一个小码本 ，小的密码本形成了大的密码本由笛卡尔产品。在此方法中，可以将高维数据分解为低维空间，可以并行处理。假设一个对象是由码字 ，向量乘积量子化的损失是（谁）给的

2.3。随机傅里叶功能

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

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

具体来说，对于两点 ，翻译不变的内核函数[12.］ 满足以下等式： 在哪里 ， 满足均匀的分布 ， 服从概率分布由平移不变核函数导出，和是常数参数。

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

2．4．普罗克汝斯忒斯正交问题

正交的营销问题是解决正交变换矩阵 ，以便最接近,例如, 在哪里 ．该公式不易直接求解，可以通过交替优化进行优化。即，矩阵首先是固定的，矩阵优化，使目标函数值减小。然后矩阵是固定的，和正交变换矩阵优化，使目标函数值减小。

3.非对称学习哈希与可变位编码

3.1。算法框架

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

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

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

3．2．目标函数

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

这将划分数据集根据RFF编码频率分割成子集。通过级联 时间分别，我们可以得到团体散列码。例如,

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

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

作为未知变量在式（8)为乘积关系，展开式(9)中包含两项未知变量，求解比较困难。经过进一步化简，得到如下公式:

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

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

AVBH对数据集进行编码的目标函数是最小化串联编码的重建误差通过找到正交旋转矩阵 ．在数据集是均匀分布的极端情况下，数据集的哈希编码频率没有显著差异，AVBH方法退化为ACH算法[16.］．与ACH散列算法相比，AVBH散列算法更适应真实数据，因为它可以适应各种分布的数据，并且泛化能力更强。

3.3。优化算法

目标函数(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．数据编码

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

3．4．2．查询点编码

最佳旋转矩阵可以从数据集编码的培训过程中获取。对于数据在查询集中，编码的主要目的是保持尽可能多的准确信息，所以查询集中编码不需要压缩并映射到长度位的哈希码。结合公式(14.)，我们可以得到AVBH到查询集的映射函数:

3.5。AVBH的收敛性分析

根据目标函数(8），我们可以得到以下公式： 在哪里是一个(1)每个元素的符号，即正的或负的，在和那个一样吗 ，(2)每个元素不大于相应的位置元素 ．

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

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

4.实验结果

这台实验计算机拥有英特尔酷睿i5-2410M CPU和8gb DDR3内存。我们比较了AVBH与几种典型哈希方法的性能:12.], ITQ [19.]，kmh [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功能集。随机选取其中100000张样本图像作为训练数据，另外10000张样本图像作为测试数据。

4.1.3。要旨^3.

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

4.2。绩效评估

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

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

数据2- - - - - -4为Cifar-10，Sift和GIST上的几种方法显示精确调用欧几里德邻检索的曲线，与欧几里德邻居的地面真相。我们的方法AVBH可以在四个数据集上获得更好的精度性能。由于AVBH算法使用可变位代码，总代码长度小于其他算法。结果，我们的方法有效地降低了存储成本并提高了查询的准确性。

5.结论

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

数据可用性

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

利益冲突

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

致谢

浙江国家自然科学基金资助项目(no . LZ20F020001, LY20F020009)，中国国家自然科学基金资助项目(no . 61472194, no . 61572266)，宁波大学黄国强基金资助项目。关键词:岩石力学，应力-应变关系，应力-应变关系

参考

1. C. S. Anan和R. Hartley，“优化KD树用于快速图像描述符匹配”2008年IEEE计算机学会计算机视觉与模式识别会议论文集， 1-8页，IEEE，安克雷奇，AK，美国，2008年6月。视图:出版商网站|谷歌学者
2. F. Shen，X. Yan，L. Li，Y. Yang，Z. Huang和H. T.沉，“无人藏，”与相似性 - 适应性和离散优化的深度散，“IEEE模式分析与机器智能汇刊，第40卷，不。2018年，第12页3034-3044。视图:出版商网站|谷歌学者
3. 曲晓，易伟，王涛，王士林，肖磊，刘振民，“教学辅助作业的混合整数线性规划模型及其扩展，”科学的规划， 2017年第1期，文章编号9057947,7页。视图:出版商网站|谷歌学者
4. 张志强，邹倩，王倩，林勇，李强，“基于深度相似哈希的多标签图像检索”，2018，https://arxiv.org/abs/1803.02987v1．视图:谷歌学者
5. H.-f.杨，K.林和C.0.。陈，“通过深度卷积神经网络监督了语义保护哈希学习，”IEEE模式分析与机器智能汇刊，第40卷，不。2, pp. 437-451, 2018。视图:出版商网站|谷歌学者
6. S. Berchtold，D. A. Keim和H.P.Kriegel，“X树：高维数据的指数结构”第22届超大数据库国际会议论文集， 28-39页，孟买，印度，1996。视图:谷歌学者
7. 沈昕，刘伟，曾i.w.，曾庆生。太阳,Y.-S。Ong， "通过跨视角搜索进行多标签预测"IEEE神经网络与学习系统汇刊第29卷第2期。9, pp. 4324-4338, 2018。视图:出版商网站|谷歌学者
8. 沈旭东，沈芳。孙永红，杨永红，杨永红。Yuan, Shen H. T.，“半成对离散哈希:学习潜在哈希码用于半成对交叉视图检索”，IEEE控制论汇刊(第47卷第40期)12, pp. 4275-4288, 2016。视图:出版商网站|谷歌学者
9. L. K. Huang，Q. yang和W. S. Zheng，“在线哈希”，神经网络与学习系统汇刊第29卷第2期。6，pp。2309-2322,2017。视图:出版商网站|谷歌学者
10. M. M. Bronstein，A.M.Bronstein，F. Michel和N.Angios，通过使用相似性敏感散列的跨型号度量学习的数据融合，“第23届IEEE计算机视觉与模式识别会议论文集，CVPR 20102010年6月，IEEE，美国旧金山。视图:谷歌学者
11. A. Gordo，F. Perronnin，Y.Gong和S. Lazebnik，“二元嵌入的不对称距离”IEEE模式分析与机器智能汇刊，第36卷，第2期。1，页33-47,2014。视图:出版商网站|谷歌学者
12. Y. LV，W.W.Y.NG，Z.Zeng，D. S. Yeung和P.P.K. Chan，“大规模图像检索的不对称循环散列”，IEEE多媒体汇刊第17卷，没有。8，页1225-1235,2015。视图:出版商网站|谷歌学者
13. A. Gionis, P. Indyk, R. Motwani，“高维哈希相似性搜索”，载于第25届超大数据库国际会议论文集，卷。8，不。2，PP。518-529，爱丁堡，苏格兰，1999年。视图:谷歌学者
14. J. Qian，Q. Zhu，H. Chen，“多粒度局部敏感的绽放滤波器”计算机上的IEEE交易(第64卷)12，页3500-3514,2015。视图:出版商网站|谷歌学者
15. Deng C.， Chen Z.， Liu X.， Gao X.， and D. Tao， "基于三组深度哈希网络的跨模态检索"，IEEE图像处理汇刊，第27卷，第2期。8, pp. 3893-3903, 2018。视图:出版商网站|谷歌学者
16. R. Salakhutdinov和G. Hinton，“语义哈希”，国际大约推理杂志第50卷，没有。7，页969-978,2009。视图:出版商网站|谷歌学者
17. w。Kong和w。Li，“各向同性哈希”神经信息处理系统的进展，第1655-1663页，Curran Associates Inc.，纽约，纽约，美国，2012。视图:谷歌学者
18. M. Raginsky， "移不变内核中的位置敏感二进制码"神经信息处理系统的进展，Curran Associates Inc.，纽约，NY，美国，2009年。视图:谷歌学者
19. Y.Gong，S. Lazebnik，A.Gordo和F. Perronnin，“迭代量化：用于学习大型图像检索的二元码的Procrustean方法”IEEE模式分析与机器智能汇刊第35卷，没有。12页，2916-2929,2013。视图:出版商网站|谷歌学者
20. 何凯，温峰，孙俊杰，“K-means哈希:一种保持相似度的量化学习二进制编码方法”，见2013 IEEE计算机视觉与模式识别会议论文集2013年6月，美国，波特兰。视图:出版商网站|谷歌学者
21. Yu X.， Zhang X. Liu, L. Zhong, and D. N. Metaxas， "基于无监督PCA哈希算法的大规模医学图像搜索"，in2013年IEEE计算机视觉与模式识别研讨会论文集，第393-398页，IEEE，波特兰，或美国，2013年6月。视图:出版商网站|谷歌学者

版权

任衍多等人版权所有©2020这是一篇开放获取的文章知识共享署名许可，允许在任何媒介上不受限制地使用、分发和复制，只要原稿被适当引用。