Supervised Discrete Hashing
- 1 June 2015
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636919,p. 37-45
- https://doi.org/10.1109/cvpr.2015.7298598
Abstract
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.Keywords
Other Versions
This publication has 22 references indexed in Scilit:
- Fast Supervised Hashing with Decision Trees for High-Dimensional DataPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2014
- Learning Hash Codes with Listwise SupervisionPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2013
- Inter-media hashing for large-scale retrieval from heterogeneous data sourcesPublished by Association for Computing Machinery (ACM) ,2013
- Inductive Hashing on ManifoldsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2013
- Sparse hashing for fast multimedia searchACM Transactions on Information Systems, 2013
- Iterative Quantization: A Procrustean Approach to Learning Binary Codes for Large-Scale Image RetrievalIEEE Transactions on Pattern Analysis and Machine Intelligence, 2012
- Random maximum margin hashingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2011
- A direct formulation for totally-corrective multi-class boostingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2011
- Regularization Methods for Semidefinite ProgrammingSIAM Journal on Optimization, 2009
- Laplacian Eigenmaps for Dimensionality Reduction and Data RepresentationNeural Computation, 2003