Self-Taught Hashing for Fast Similarity Search

Dell Zhang, Jun Wang, Deng Cai, Jinsong Lu

Abstract

Similarity search in high-dimensional spaces is a fundamental challenge in information retrieval. Semantic hashing addresses this by mapping documents to short binary codes, but many existing methods struggle with the "out-of-sample" extension—efficiently hashing new query documents. We present Self-Taught Hashing (STH), a two-stage framework that decouples binary code generation from hash function learning. By first finding optimal codes via unsupervised manifold learning and then training linear classifiers to predict these codes, STH achieves state-of-the-art retrieval performance with exceptional computational efficiency.

Introduction

The "curse of dimensionality" makes traditional indexing methods ineffective for large-scale similarity search in high-dimensional document spaces. Semantic hashing has emerged as a powerful alternative, aiming to represent documents as compact binary strings where similar items have small Hamming distances. A critical requirement for any practical hashing scheme is the ability to rapidly generate codes for unseen queries. While some spectral methods provide high accuracy for static datasets, they often lack an efficient out-of-sample extension or rely on restrictive data distribution assumptions.

The Self-Taught Hashing (STH) Framework

STH addresses these limitations through a "self-taught" approach, separating the problem into two distinct phases: an offline "teacher" phase and an online "student" phase.

The STH framework consists of an offline stage for code generation and classifier training, and an online stage for rapid query hashing.

Stage 1: Unsupervised Code Generation (The Teacher)

In the offline phase, STH identifies the optimal $l$-bit binary codes for the training corpus. Unlike methods that attempt to preserve global data structure, STH focuses on the local similarity manifold using Binarized Laplacian Eigenmaps. By constructing a $k$-nearest-neighbor graph, the algorithm ensures that the resulting codes capture the local neighborhood structure most relevant for retrieval. The real-valued vectors produced are thresholded at the median to maximize entropy, ensuring each bit carries maximum information.

Stage 2: Supervised Hash Function Learning (The Student)

The binary codes from Stage 1 serve as "pseudo-labels" for a supervised learning task. For each of the $l$ bits, a separate linear Support Vector Machine (SVM) is trained. The SVMs learn to map the original document features to the corresponding hash bits. This stage is "self-taught" because the labels are generated by the algorithm itself rather than human annotators.

Online Querying

Once trained, the $l$ linear SVMs define the hash function. Hashing a new query document involves a simple set of dot-product operations followed by sign functions. This process is computationally trivial, allowing for near-instantaneous code generation.

Experimental Results

STH was evaluated on three benchmark text datasets: Reuters21578, 20Newsgroups, and TDT2. Performance was compared against Binarized Latent Semantic Indexing (LSI), Laplacian Co-Hashing (LCH), and Spectral Hashing (SpH).

Precision-recall curves on three datasets (32-bit codes). STH consistently outperforms LSI, LCH, and SpH across all benchmarks.

Retrieval Accuracy

As shown in the precision-recall curves, STH significantly outperforms competing methods across all datasets. The use of local manifold learning allows STH to better capture the semantic nuances of the text compared to methods that assume uniform data distributions or global structures.

Efficiency and Generalization

STH demonstrates remarkable bit efficiency; for instance, on the 20Newsgroups dataset, STH with 8 bits achieves performance comparable to other methods using 128 bits. Furthermore, the "maximum-margin" property of the linear SVMs contributes to robust generalization, ensuring that the hash function performs well on out-of-sample query documents. In terms of speed, STH can generate a hash code in less than a millisecond on standard hardware, making it suitable for real-time applications.

Conclusion

Self-Taught Hashing provides a flexible and efficient solution for large-scale similarity search. By decoupling code discovery from function learning, it leverages the strengths of both unsupervised manifold learning and supervised classification. Future work includes scaling the graph construction process for billion-scale datasets and exploring non-linear kernels for further accuracy gains.

Summary updated

Abstract

The ability of fast similarity search at large scale is of great importance to many Information Retrieval (IR) applications. A promising way to accelerate similarity search is semantic hashing which designs compact binary codes for a large number of documents so that semantically similar documents are mapped to similar codes (within a short Hamming distance). Although some recently proposed techniques are able to generate high-quality codes for documents known in advance, obtaining the codes for previously unseen documents remains to be a very challenging problem. In this paper, we emphasise this issue and propose a novel Self-Taught Hashing (STH) approach to semantic hashing: we first find the optimal $l$-bit binary codes for all documents in the given corpus via unsupervised learning, and then train $l$ classifiers via supervised learning to predict the $l$-bit code for any query document unseen before. Our experiments on three real-world text datasets show that the proposed approach using binarised Laplacian Eigenmap (LapEig) and linear Support Vector Machine (SVM) outperforms state-of-the-art techniques significantly.
BibTeX
@inproceedings{zhang2010self,
  author = {Dell Zhang and Jun Wang and Deng Cai and Jinsong Lu},
  title = {{Self-Taught Hashing for Fast Similarity Search}},
  booktitle = {International ACM SIGIR Conference on Research and Development in Information Retrieval},
  year = {2010},
  doi = {10.1145/1835449.1835455},
}
Figure