Supervised Discrete Hashing

By Fumin Shen, Chunhua Shen, Wei David Liu, Heng Tao Shen. 2015

1,164 citations recorded by the source corpus.

Recently, learning based hashing techniques have attracted broad research interests because they can support efficient storage and retrieval for high-dimensional data such as images, videos, documents, etc. However, a major difficulty of learning to hash lies in handling the discrete constraints imposed on the pursued hash codes, which typically makes hash optimizations very challenging (NP-hard in general). In this work, we propose a new supervised hashing framework, where the learning objective is to generate the optimal binary hash codes for linear classification. By introducing an auxiliary variable, we reformulate the objective such that it can be solved substantially efficiently by employing a regularization algorithm. One of the key steps in this algorithm is to solve a regularization sub-problem associated with the NP-hard binary optimization. We show that the sub-problem admits an analytical solution via cyclic coordinate descent. As such, a high-quality discrete solution can eventually be obtained in an efficient computing manner, therefore enabling to tackle massive datasets. We evaluate the proposed approach, dubbed Supervised Discrete Hashing (SDH), on four large image datasets and demonstrate its superiority to the state-of-the-art hashing methods in large-scale image retrieval.

Subfields: Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

Citations in the corpus

SCA-CNN: Spatial and Channel-Wise Attention in Convolutional Networks for Image Captioning (2016, methodology): “We are interested in visual attention models used in the encoder-decoder framework for neural image/video captioning (NIC) and visual question answering (VQA), which fall into the recent trend of connecting computer vision and natural language [14, 41, 24, 23, 42, 12].”
Deep Hashing Network for Efficient Similarity Retrieval (2016, background): “…(Kulis and Darrell 2009; Gong and Lazebnik 2011; Norouzi and Blei 2011; Fleet, Punjani, and Norouzi 2012; Liu et al. 2012; Wang, Kumar, and Chang 2012; Liu et al. 2013; Gong et al. 2013; Yu et al. 2014; Xia et al. 2014; Zhang et al. 2014; Shen et al. 2015; Lai et al. 2015; Erin Liong et al. 2015).”
A Survey on Learning to Hash (2016, methodology): “Quantization is also applied to supervised problems: Supervised discrete hashing [125], [127], [168], [170], presents an SVM-like formulation to minimize the quantization loss and the classification loss in the hash”
Deep Sketch Hashing: Fast Free-Hand Sketch-Based Image Retrieval (2017, methodology): “Inspired by the discrete cyclic coordinate descent (DCC) [54], we learn each row of B by fixing all other m−1 rows, i.”
Central Similarity Quantization for Efficient Image and Video Retrieval (2019, methodology): “Recently, “deep learning to hash” methods [14, 32, 21, 18, 22, 44] have been successfully applied to large-scale image retrieval [44, 48] and video retrieval [8, 28, 21], which can naturally represent a nonlinear hash function for producing hash codes of input data.”
Learning Binary Codes for Maximum Inner Product Search (2015, background): “For this key sub-problem, inspired by the recent progress of binary codes optimization [29], we choose to solve one row of B each time while fixing all other rows, i.”
Deep Supervised Discrete Hashing (2017, methodology): “Supervised Discrete Hashing (SDH) [14] aims to directly optimize the binary hash codes using the discrete cyclic coordinate descend method.”
Pairwise Teacher-Student Network for Semi-Supervised Hashing (2019, methodology): “With the explosion of high-dimensional media data, hashing is widely applied for efficient approximate Nearest Neighbor(ANN) search [6] due to its short retrieval time and small storage space [6, 16, 22, 26].”
Self-Supervised Adversarial Hashing Networks for Cross-Modal Retrieval (2018, methodology): “Most existing shallow cross-modal hashing methods (in both unsupervised [2, 10, 14, 18] and supervised settings [7, 17, 19, 26, 30, 40, 33]), always capture the semantic relevance in a common Hamming space.”
High-Dimensional Sparse Cross-Modal Hashing with Fine-Grained Similarity Embedding (2021, methodology): “Typical examples include Iterative Quantization (ITQ) [13], Discrete Graph Hashing (DGH) [30], Discrete Locality Linear Embedding (DLLH) [18], Supervised Hashing with Kernels (KSH) [31], Super-vised Discrete Hashing (SDH) [41], Discrete Hashing with Multiple Supervision (MSDH) [34], Deep Semantic Re”
A Decade Survey of Content Based Image Retrieval Using Deep Learning (2020, methodology): “(2015) [88] have proposed the supervised discrete hashing (SDH) based generation of image description with the help of the discrete cyclic coordinate descent for retrieval.”
Deep Supervised Hashing for Fast Image Retrieval (2016, methodology): “Methods such as Discrete Graph Hashing (DGH) [16] and Supervised Discrete Hashing (SDH) [23] are proposed to directly optimize the binary codes to overcome the shortcomings of relaxation, and achieves improved retrieval performance.”
Learning to Hash for Indexing Big Data—A Survey (2015, background): “In addition, supervised learning paradigms ranging from kernel learning to metric learning to deep learning have been exploited to learn binary codes, and many supervised hashing methods have been proposed recently [19], [22], [65]–[68].”
SketchMate: Deep Hashing for Million-Scale Human Sketch Retrieval (2018, methodology): “Recently, deep hashing learning has shown superiority on better preserving the semantic information when compared with shallow methods [28, 14, 21].”
HashNet: Deep Learning to Hash by Continuation (2017, background): “Recently, deep learning to hash methods [37, 20, 31, 8, 40] have shown that end-to-end learning of feature representation and hash coding can be more effective using deep neural networks [18, 2], which can naturally encode any nonlinear hash functions.”
Attentional Factorization Machines: Learning the Weight of Feature Interactions via Attention Networks (2017, methodology): “As AFM has a relatively high complexity quadratic to the number of non-zero features, we will consider improving its learning efficiency, for example by using learning to hash [Zhang et al., 2016b; Shen et al., 2015] and data sampling [Wang et al.”
Deep Cauchy Hashing for Hamming Space Retrieval (2018, methodology): “Specifically, compared to SDH, the best shallow hashing method with deep features as input, DCH achieves absolute increases of 14.4%, 13.3% and 21.9% in average MAP@H≤2 with different code lengths on NUS-WIDE, MS-COCO and CIFAR-10, respectively.”
Unsupervised Deep Hashing with Similarity-Adaptive and Discrete Optimization (2018, methodology): “tion error, which yields less effective binary codes [15], [29], [37].”
Feature Learning Based Deep Supervised Hashing with Pairwise Labels (2015, methodology): “Among existing ANN techniques, hashing has become one of the most popular and effective techniques due to its fast query speed and low memory cost [26, 9, 28, 3, 18, 22, 6, 38, 4, 13, 25], especially in image retrieval applications.”