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.
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).
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