Weakly-supervised hashing in kernel space

Yadong Mu*, Jialie Shen, Shuicheng Yan

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

132 Citations (Scopus)

Abstract

The explosive growth of the vision data motivates the recent studies on efficient data indexing methods such as locality-sensitive hashing (LSH). Most existing approaches perform hashing in an unsupervised way. In this paper we move one step forward and propose a supervised hashing method, i.e., the LAbel-regularized Max-margin Partition (LAMP) algorithm. The proposed method generates hash functions in weakly-supervised setting, where a small portion of sample pairs are manually labeled to be "similar" or "dissimilar". We formulate the task as a Constrained Convex-Concave Procedure (CCCP), which can be relaxed into a series of convex sub-problems solvable with efficient Quadratic-Program (QP). The proposed hashing method possesses other characteristics including: 1) most existing LSH approaches rely on linear feature representation. Unfortunately, kernel tricks are often more natural to gauge the similarity between visual objects in vision research, which corresponds to probably infinite-dimensional Hilbert spaces. The proposed LAMP has a natural support for kernel-based feature representation. 2) traditional hashing methods assume uniform data distributions. Typically, the collision probability of two samples in hash buckets is only determined by pairwise similarity, unrelated to contextual data distribution. In contrast, we provide such a collision bound which is beyond pairwise data interaction based on Markov random fields theory. Extensive empirical evaluations are conducted on five widely-used benchmarks. It takes only several seconds to generate a new hashing function, and the adopted random supporting-vector scheme enables the LAMP algorithm scalable to large-scale problems. Experimental results well validate the superiorities of the LAMP algorithm over the state-of-the-art kernel-based hashing methods.

Original languageEnglish
Title of host publication2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR 2010
Pages3344-3351
Number of pages8
DOIs
Publication statusPublished - 31 Aug 2010
Externally publishedYes
Event2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR 2010 - San Francisco, CA, United States
Duration: 13 Jun 201018 Jun 2010

Publication series

NameProceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition
ISSN (Print)1063-6919

Conference

Conference2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR 2010
Country/TerritoryUnited States
CitySan Francisco, CA
Period13/06/201018/06/2010

ASJC Scopus subject areas

  • Software
  • Computer Vision and Pattern Recognition

Fingerprint

Dive into the research topics of 'Weakly-supervised hashing in kernel space'. Together they form a unique fingerprint.

Cite this