Learning Hash Functions Using Column Generation

Abstract

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.

9 pages, published in International Conf. Machine Learning, 2013

Cited by in corpus (17)

• Simultaneous Feature Learning and Hash Coding with Deep Neural Networks
• Fast Supervised Hashing with Decision Trees for High-Dimensional Data
• SSDH: Semi-supervised Deep Hashing for Large Scale Image Retrieval
• Feature Learning based Deep Supervised Hashing with Pairwise Labels
• Supervised Hashing Using Graph Cuts and Boosted Decision Trees
• Learning to Hash for Indexing Big Data - A Survey
• DeepHash: Getting Regularization, Depth and Fine-Tuning Right
• Interpretable and Fair Boolean Rule Sets via Column Generation
• Fast Training of Triplet-based Deep Binary Embedding Networks
• On the Evaluation Metric for Hashing
• Hash Function Learning via Codewords
• A General Two-Step Approach to Learning-Based Hashing
• A Scalable Optimization Mechanism for Pairwise based Discrete Hashing
• Hashing with Binary Matrix Pursuit
• Learning Binary Codes and Binary Weights for Efficient Classification
• Structured Learning of Binary Codes with Column Generation
• Learning Hash Function through Codewords