基于深度学习的散列检索技术研究进展

doi:10.11959/j.issn.1000-0801.2018274

摘要/Abstract

摘要：

大数据时代，数据呈现维度高、数据量大和增长快等特点。面对大量的复杂数据，如何高效地检索相似近邻数据是近似最近邻查询的研究热点。散列技术通过将数据映射为二进制码的方式，能够显著加快相似性计算，并在检索过程中节省存储和通信开销。近年来深度学习在提取数据特征方面表现出速度快、精度高等优异的性能，使得基于深度学习的散列检索技术得到越来越广泛的运用。总结了深度学习散列的主要方法和前沿进展，并对未来的研究方向展开简要探讨。

关键词: 大数据, 近似最近邻查询, 深度学习散列

Abstract:

In the era of big data,data shows the characteristics of high dimension,large amount and rapid growth.How to efficiently retrieve similar data from a large amount of complex data is a research hotspot.By mapping data to binary codes,the hashing technique can significantly accelerate the similarity calculation and reduce storage and communication overhead during the retrieval process.In recent years,deep learning has shown excellent performance in extracting data features.Deep learning-based hash retrieval technique has the advantages of high speed and accuracy.The methods and advanced development of deep learning hashing were mainly summarized,and the future of research direction was briefly discussed.

Key words: big data, approximate nearest neighbor query, deep learning hashing

中图分类号:

TP311

袁明汶,钱江波,董一鸿,陈华辉. 基于深度学习的散列检索技术研究进展[J]. 电信科学, 2018, 34(10): 104-115.

Mingwen YUAN,Jiangbo QIAN,Yihong DONG,Huahui CHEN. Research and development of hash retrieval technology based on deep learning[J]. Telecommunications Science, 2018, 34(10): 104-115.

图/表 3

参考文献 42

[1]	吴军 . 大数据和机器智能对未来社会的影响[J]. 电信科学, 2015,31(2): 7-16.
	WU J . Big data,machine intelligence and their impacts to the future world[J]. Telecommunications Science, 2015,31(2): 7-16.
[2]	尤海浪, 钱锋, 黄祥为 ,等. 基于大数据挖掘构建游戏平台个性化推荐系统的研究与实践[J]. 电信科学, 2014,30(10): 27-32.
	YOU H L , QIAN F , HUANG X W ,et al. Research and practice of building a personalized recommendation system for mobile game platform based on big data mining[J]. Telecommunications Science, 2014,30(10): 27-32.
[3]	徐雅斌, 刘超, 武装 ,等. 基于用户兴趣和推荐信任域的微博推荐[J]. 电信科学, 2015,31(1): 13-20.
	XU Y B , LIU C , WU Z ,et al. Micro-blog recommendation based on user interests and recommendation trust domain[J]. Telecommunications Science, 2015,31(1): 13-20.
[4]	GONG Y , LAZEBNIK S . Iterative quantization:a procrustean approach to learning binary codes[C]// IEEE Conference on Computer Vision and Pattern Recognition,June 20-25,2011,Colorado Springs,CO,USA. Piscataway:IEEE Press, 2011: 817-824.
[5]	HE J , LIU W , CHANG S F . Scalable similarity search with optimized kernel hashing[C]// ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,July 25-28,2010,Washington,DC,USA. New York:ACM Press, 2010: 1129-1138.
[6]	LIU X , HE J , LANG B ,et al. Hash bit selection:a unified solution for selection problems in hashing[C]// Computer Vision and Pattern Recognition,June 23-28,2013,Portland,OR,USA. Piscataway:IEEE Press, 2013: 1570-1577.
[7]	WANG J , KUMAR S , CHANG S F . Semi-supervised hashing for large-scale search[J]. IEEE Transactions on Pattern Analysis＆ Machine Intelligence, 2012,34(12): 2393-2406.
[8]	WANG J , SHEN H T , SONG J ,et al. Hashing for similarity search:a survey[J]. Computer Science, 2014.
[9]	WEISS Y , TORRALBA A , FERGUS R . Spectral hashing[C]// International Conference on Neural Information Processing Systems,Dec 8-10,2008,Vancouver,British Columbia,Canada. New York:ACM Press, 2008: 1753-1760.
[10]	ANDONI A , INDYK P . Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions[C]// 2006 IEEE Symposium on Foundations of Computer Science,Oct 21-24,2006,Berkeley,CA,USA. Piscataway:IEEE Press, 2006: 459-468.
[11]	CHUM O , PHILBIN J , ZISSERMAN A . Near duplicate image detection:min-hash and tf-idf weighting[C]// British Machine Vision Conference 2008,September 2-4,2008,Leeds,UK.[S.l.:s.n]. 2008.
[12]	JAIN P , KULIS B , GRAUMAN K . Fast image search for learned metrics[C]// 2008 IEEE Conference on Computer Vision and Pattern Recognition,June 23-28,2008,Anchorage,AK,USA. Piscataway:IEEE Press, 2009: 1-8.
[13]	JI J , LI J , YAN S ,et al. Super-bit locality-sensitive hashing[C]// International Conference on Neural Information Processing Systems,Dec 3-6,2012,Lake Tahoe,Nevada,USA. New York:ACM Press, 2012: 108-116.
[14]	RAGINSKY M , LAZEBNIK S . Locality-sensitive binary codes from shift-invariant kernels[C]// Advances in Neural Information Processing Systems 2009,Dec 7-10,2009,Vancouver,British Columbia,Canada.[S.l.:s.n]. 2009: 1509-1517.
[15]	GONG Y , KUMAR S , VERMA V ,et al. Angular quantization-based binary codes for fast similarity search[J]. Advances in Neural Information Processing Systems, 2012: 1196-1204.
[16]	HE K , WEN F , SUN J . K-means hashing:an affinity-preserving quantization method for learning binary compact codes[C]// Computer Vision and Pattern Recognition,June 23-28,2013,Portland,OR,USA. Piscataway:IEEE Press, 2013: 2938-2945.
[17]	KULIS B , JAIN P , GRAUMAN K . Fast similarity search for learned metrics[J]. IEEE Transactions on Pattern Analysis ＆Machine Intelligence, 2009,31(12): 2143-57.
[18]	LIN G , SHEN C , SHI Q ,et al. Fast supervised hashing with decision trees for high-dimensional data[C]// Computer Vision and Pattern Recognition,June 23-28,2014,Columbus,OH,USA. Piscataway:IEEE Press, 2014: 1971-1978.
[19]	NOROUZI M , FLEET D J . Minimal loss hashing for compact binary codes[C]// International Conference on International Conference on Machine Learning,June 28-July 2,2011,Bellevue,Washington,USA. New York:ACM Press, 2011: 353-360.
[20]	SHEN F , SHEN C , SHI Q ,et al. Inductive hashing on manifolds[C]// IEEE Conference on Computer Vision and Pattern Recognition,June 23-28,2013,Portland,OR,USA. Piscataway:IEEE Press, 2013: 1562-1569.
[21]	WANG J , KUMAR S , CHANG S F . Semi-supervised hashing for large-scale search[J]. IEEE Transactions on Pattern Analysis＆ Machine Intelligence, 2012,34(12): 2393-2406.
[22]	KULIS B , GRAUMAN K . Kernelized locality-sensitive hashing for scalable image search[C]// IEEE International Conference on Computer Vision,Sept 29-Oct 2,2009,Kyoto,Japan. Piscataway:IEEE Press, 2010: 2130-2137.
[23]	RAHIMI A , RECHT B . Random features for large-scale kernelmachines[C]// International Conference on Neural Information Processing Systems,Dec 3-6,2007,Vancouver,British Columbia,Canada. New York:ACM Press, 2007: 1177-1184.
[24]	LECUN Y , BENGIO Y , HINTON G . Deep learning[J]. Nature, 2015,521(7553):436.
[25]	KRIZHEVSKY A , SUTSKEVER I , HINTON G E . ImageNet classification with deep convolutional neural networks[C]// International Conference on Neural Information Processing Systems,December 3-6,2012,Lake Tahoe,Nevada,USA. New York:ACM Press, 2012: 1097-1105.
[26]	SALAKHUTDINOV R , HINTON G . Semantic hashing[J]. International Journal of Approximate Reasoning, 2009,50(7): 969-978.
[27]	SALAKHUTDINOV R , HINTON G . Reducing the dimensionality of data with neural networks[J]. Science, 2006,313(5786): 504-507.
[28]	GOLDBERGER J , ROWEIS S , HINTON G E ,et al. Neighbourhood components analysis[C]// International Conference on Neural Information Processing Systems,Nov 22-25,Vancouver,British Columbia,Canada. Cambridge:MIT Press, 2004: 513-520.
[29]	TORRALBA A , FERGUS R , WEISS Y . Small codes and large image databases for recognition[C]// IEEE Conference on Computer Vision and Pattern Recognition,June 23-28,2008,Anchorage,AK,USA. Piscataway:IEEE Press, 2008: 1-8.
[30]	MASCI J , BRONSTEIN A M , BRONSTEIN M M ,et al. Sparse similarity-preserving hashing[J]. Computer Science, 2013.
[31]	GREGOR K , LECUN Y . Learning fast approximations of sparse coding[C]// International Conference on Machine Learning,June 21-24,2010,Haifa,Israel. New York:ACM Press, 2010: 399-406.
[32]	LIONG V E , LU J , WANG G ,et al. Deep hashing for compact binary codes learning[C]// Computer Vision and Pattern Recognition,June 7-12,2015,Boston,MA,USA. Piscataway:IEEE Press, 2015: 2475-2483.
[33]	LIU W , WANG J , JI R ,et al. Supervised hashing with kernels[C]// IEEE Conference on Computer Vision and Pattern Recognition,June 16-21,2012,Providence,RI,USA. Piscataway:IEEE Press, 2012: 2074-2081.
[34]	XIA R , PAN Y , LAI H ,et al. Supervised hashing for image retrieval via image representation learning[J]. Association for the Advance of Artificial Intelligence, 2014: 2156-2162.
[35]	LAI H , PAN Y , LIU Y ,et al. Simultaneous feature learning and hash coding with deep neural networks[J]. Computer Vision and Pattern Recognition, 2015: 3270-3278.
[36]	ZHAO F , HUANG Y , WANG L ,et al. Deep semantic ranking based hashing for multi-label image retrieval[C]// Computer Vision and Pattern Recognition,Sept 11-14,2015,Monterey,CA,USA. Piscataway:IEEE Press, 2015: 1556-1564.
[37]	ZHANG R , LIN L , ZHANG R ,et al. Bit-scalable deep hashing with regularized similarity learning for image retrieval and person re-identification[J]. IEEE Transactions on Image Processing, 2015,24(12): 4766-4779.
[38]	LIU H , WANG R , SHAN S ,et al. Deep supervised hashing for fast image retrieval[C]// Computer Vision and Pattern Recognition,June 27-30,2016,Las Vegas,NV,USA. Piscataway:IEEE Press, 2016: 2064-2072.
[39]	LIN K , YANG H F , HSIAO J H ,et al. Deep learning of binary hash codes for fast image retrieval[C]// Computer Vision and Pattern Recognition Workshops,June 7-12,2015,Boston,MA,USA. Piscataway:IEEE Press, 2015: 27-35.
[40]	YANG H F , LIN K , CHEN C S . Supervised learning of semantics-preserving hash via deep convolutional neural networks[J]. IEEE Transactions on Pattern Analysis ＆ Machine Intelligence, 2015(99):1.
[41]	ZHANG J , PENG Y , YUAN M . SCH-GAN:semi-supervised cross-modal hashing by generative adversarial network[J]. arXiv:1802.02488v1.
[42]	QIAN J , ZHU Q , CHEN H . Multi-granularity locality-sensitive bloom filter[J]. IEEE Communications Letters, 2015,64(12): 3500-3514.

算法	12 bit(mAP)	32 bit(mAP)	48 bit(mAP)	采用方法
CNNH	0.465	0.521	0.532	散列码学习、学习散列函数
NINH	0.552	0.558	0.581	网络分割、阈值损失
DRSCH	—	0.628	0.630	海明码加权、正则约束
DSH	0.615	—	0.675	正则约束、保相似性损失
SSDH	0.872	0.911	0.908	散列重构、编码约束
SCHGAN	0.523/0.859	0.530/0.876	0.548/0.883	半监督的生成对抗学习