Learning Hash Functions Using Column Generation

By Xi Li, Guosheng Lin, Chunhua Shen, Anton van den Hengel, Anthony R. Dick. 2013

57 citations recorded by the source corpus.

Fast nearest neighbor searching is becoming an increasingly important tool in solving many large-scale problems. Recently a number of approaches to learning data-dependent hash functions have been developed. In this work, we propose a column generation based method for learning data-dependent hash functions on the basis of proximity comparison information. Given a set of triplets that encode the pairwise proximity comparison information, our method learns hash functions that preserve the relative comparison relationships in the data as well as possible within the large-margin learning framework. The learning procedure is implemented using column generation and hence is named CGHash. At each iteration of the column generation procedure, the best hash function is selected. Unlike most other hashing methods, our method generalizes to new data points naturally; and has a training objective which is convex, thus ensuring that the global optimum can be identified. Experiments demonstrate that the proposed method learns compact binary codes and that its retrieval performance compares favorably with state-of-the-art methods when tested on a few benchmark datasets.

Subfields: Artificial Intelligence, 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 Artificial Intelligence

In Computer Vision and Pattern Recognition

Citations in the corpus

Boolean Decision Rules via Column Generation (2018, methodology): “We note that CG has been proposed for other machine learning tasks such as boosting [21, 7] and hash learning [37].”
Learning to Hash for Indexing Big Data—A Survey (2015, methodology): “Other interesting learning ideas include twostep learning methods which treat hash bit learning and hash function learning separately [85][86].”
Feature Learning Based Deep Supervised Hashing with Pairwise Labels (2015, methodology): “Representative ranking label based methods include ranking-based supervised hashing (RSH) [Wang et al., 2013b], column generation hashing (CGHash) [Li et al., 2013], order preserving hashing (OPH) [Wang et al., 2013a], ranking preserving hashing (RPH) [Wang et al., 2015], and some deep hashing…”
Bit-Scalable Deep Hashing With Regularized Similarity Learning for Image Retrieval and Person Re-Identification (2015, methodology): “, 16, 32 or 64 bits) [5][7][12], but one often requires hashing codes of different lengths under different scenarios.”
DeepHash: Getting Regularization, Depth and Fine-Tuning Right (2015, unknown): “…are Iterative Quantization [9], Spectral Hashing [10], Restricted Boltzmann Machines [8], while some examples of state-of-the-art supervised schemes include Minimal Loss Hashing [11], Kernel-based Supervised Hashing [12], Ranking-based Supervised Hashing [13] and Column Generation Hashing [14].”
Discrete Graph Hashing (2014, methodology): “, Semantic Hashing [30], Binary Reconstruction Embeddings [16], Minimal Loss Hashing [27], Kernel-based Supervised Hashing [22], Hamming Distance Metric Learning [28], and Column Generation Hashing [20].”
Supervised Hashing for Image Retrieval via Image Representation Learning (2014, unknown): “KSH (Liu et al. 2012), BRE (Kulis and Darrell 2009), MLH (Norouzi and Blei 2011), CGHash (Li et al. 2013), ITQ-CCA (Gong and Lazebnik 2011) and SSH (Wang, Kumar, and Chang 2010) are some representatives.”
Simultaneous feature learning and hash coding with deep neural networks (2015, background): “Recently, some efforts [17, 10] have been made to learn hash functions that preserve relative similarities of the form “image I is more similar to image I than to image I−”.”
Supervised Discrete Hashing (2015, background): “Hashing has attracted considerable attention of researchers in computer vision, machine learning, information retrieval and related areas [8,10,16,20,21,31,34,38,40].”