Source-linked AI summary
Self-Taught Hashing for Fast Similarity Search
Dell Zhang, Jun Wang, Deng Cai, Jinsong Lu
TL;DR
Large-scale semantic hashing needs compact codes that support fast similarity search, but assigning codes to previously unseen documents remains difficult. STH learns corpus codes without supervision and then trains classifiers to predict codes for new queries. Across three real-world text datasets, its binarised LapEig and linear-SVM implementation significantly outperforms state-of-the-art methods while maintaining high running speed.
Problem
Assigning semantic-hashing codes to previously unseen documents remains challenging despite progress on documents known in advance.
Method
STH first learns l-bit corpus codes through unsupervised learning, then trains l classifiers to predict codes for unseen query documents.
Results
STH with binarised LapEig and linear SVM significantly outperforms state-of-the-art techniques on three real-world text datasets while maintaining high running speed.
Takeaways & Limitations
Decomposing code learning into unsupervised and supervised stages provides a flexible framework for fast semantic hashing.
Takeaways & Limitations
Larger Hamming balls can improve retrieval but may require checking many codes, diminishing semantic hashing’s efficiency gains.
Abstract
from arXiv · showhide
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.
1. INTRODUCTION
Large-scale similarity search matters across IR applications, and semantic hashing accelerates it by assigning similar documents compact codes. STH addresses the challenge of coding unseen documents and reports strong performance with high running speed.
- Motivation: Similarity search underlies applications including near-duplicate detection, plagiarism analysis, collaborative filtering, caching, and multimedia retrieval.
- Motivation: Semantic hashing maps semantically similar documents to compact binary codes with short Hamming distance.Compressed codes support fast in-memory search and efficient Hamming-distance computation.
- Motivation: Returning nearby codes within a Hamming ball can retrieve candidates efficiently before content-based filtering or reranking.A 4-bit code can be searched by checking the query code and codes differing in one bit.
- Contribution: STH first learns optimal l-bit corpus codes unsupervised, then trains l classifiers to predict codes for unseen query documents.
- Results: Experiments on three real-world text datasets show that binarised LapEig with linear SVM significantly outperforms state-of-the-art techniques while maintaining high running speed.
2. RELATED WORK
Hashing methods embed high-dimensional document representations into binary Hamming space while preserving semantic similarity. Prior approaches trade off theoretical guarantees, compactness, data awareness, or applicability to similarity search.
- Hashing methods: Hashing maps high-dimensional feature vectors into low-dimensional Hamming space while retaining semantic similarity structure.Binary codes enable faster similarity search than real-valued dimensionality-reduction representations.
- Hashing methods: LSH uses random projections and thresholding, but its data-oblivious design may require inefficiently long codes in practice.
- Hashing methods: Learned hashing methods use data-aware approaches including stacked RBMs, boosting-based SSC, and Forgiving Hashing.
- Scope: Some hashing representations target accelerating machine-learning algorithms rather than similarity search.The paper positions its objective as the reverse direction.
3. APPROACH
Self-Taught Hashing is a general semantic-hashing framework with two distinct stages: learning corpus codes and learning a hash function from those auto-labelled codes.
- Framework: STH consists of unsupervised learning followed by supervised learning in two distinct stages.
- Framework: The method is called “self-taught” because the hash function is learned from data auto-labelled in the preceding stage.
- Framework: The framework permits flexibility in selecting learning algorithms for its two stages.
Unsupervised Learning of Binary Codes
The unsupervised stage learns binary codes that preserve local document similarity while promoting efficient hash-bin usage. It constructs a sparse neighbourhood graph, solves a relaxed LapEig problem, and binarises the resulting embeddings.
- Code representation: STH represents each document as an m-dimensional vector and seeks an l-bit code in {−1,+1}^l.The code matrix stores one binary code per document.
- Similarity objective: Similarity preservation requires semantically similar documents to receive codes within a short Hamming distance.
- Similarity objective: STH preserves each document’s k-nearest-neighbour structure rather than the global similarity structure of all document pairs.This local focus matches IR emphasis on retrieving a small number of highly similar documents.
- Similarity objective: The weighted Hamming-distance objective penalises similar documents that are mapped far apart and becomes a graph-Laplacian trace objective.
- LapEig relaxation: Relaxing binary discreteness yields LapEig embeddings whose columns are eigenvectors associated with the smallest nontrivial generalized eigenvalues.The constraints prevent collapse into a subspace with dimension below l.
- Binarisation: Median thresholding turns each relaxed dimension into a balanced bit, while orthogonal eigenvectors make different bits uncorrelated.Each bit is on for roughly half of the corpus, improving hash-table utilisation.
Supervised Learning of Hash Function
STH addresses out-of-sample semantic hashing by treating each bit of an unsupervised binary code as a classification target for predicting codes of unseen query documents. Its two-stage pipeline uses corpus-derived codes to train one classifier per bit, with binarised-LapEig and linear-SVM as the chosen methods.
- Supervised Learning of Hash Function: Out-of-sample extension remains difficult because existing methods are computationally expensive or require restrictive data-distribution assumptions.LPI uses eigen-decompositions of two large dense matrices, while SpH assumes uniformly distributed data in a hyper-rectangle.
- Supervised Learning of Hash Function: STH converts each binary code bit into a binary class label and trains a separate classifier to predict that bit for unseen query documents.The learned classifiers' outputs are assembled into the query document's l-bit binary code.
- Supervised Learning of Hash Function: The approach uses binarised-LapEig for unsupervised code learning and linear-SVM for supervised hash-function learning, while allowing other algorithms in principle.The supervised stage uses one SVM classifier per bit; non-linear kernels are possible but are not explored.
- Supervised Learning of Hash Function: The learning pipeline constructs a k-nearest-neighbours graph, embeds documents with LapEig, median-thresholds the embeddings, and trains l SVM classifiers on the resulting pseudo-labels.Because the second stage uses self-generated pseudo-labels, the complete STH approach remains unsupervised.
- Supervised Learning of Hash Function: Prediction classifies a query with the l learned classifiers and assembles the labels into an l-bit code, requiring O(s′) time per linear-SVM classifier operation.Overall learning is roughly quadratic in corpus size and linear in average document size when l and k are treated as small constants.
4. EXPERIMENTS
Experiments evaluate STH across three real-world text datasets and two relevance definitions, comparing retrieval quality, efficiency trade-offs, and approximation sources. STH consistently outperforms the compared semantic hashing methods while remaining fast.
- Evaluation: Relevance is evaluated using either the 25 original nearest neighbours or documents sharing the query’s topic category.Test documents query the training set, with precision, recall, and F1 computed within specified Hamming distances.
- Retrieval trade-offs: Longer codes and larger Hamming-ball radii improve F1, but increase memory and computation; validation queries identify the effectiveness-efficiency trade-off.Figures vary code lengths from 4-bit to 64-bit and radii from 0 to 3.
- Experimental setup: Experiments compare STH with binarised-LSI, LCH, and state-of-the-art SpH on three publicly available real-world text datasets.The STH implementation uses k = 25 for the LapEig nearest-neighbour graph and default LIBLINEAR SVM parameters.
- Comparative results: Across all datasets and both evaluation methodologies, STH outperforms binarised-LSI, LCH, and SpH, with 16-bit radius-1 improvements statistically significant at P value < 0.01.The comparison uses precision-recall curves while varying code length from 4-bit to 64-bit with radius fixed at 1.
- Comparative results: On 20Newsgroups, STH reaches the same F1 = 0.276 as stacked-RBM with 8-bit rather than 128-bit codes.This comparison concerns retrieving same-topic documents.
- Approximation analysis: Most approximation error arises during LapEig dimensionality reduction, whereas median binarisation and SVM out-of-sample extension incur little error.The paper identifies accurate intrinsic-dimensionality detection or reduction as a hard problem.
- Efficiency: A 64-bit STH implementation takes approximately 0.0165 second per document for training and 0.0007 second per document for prediction.Training is reported as about 10 times faster than SpH on the stated ordinary PC.
5. CONCLUSIONS
STH accelerates semantic hashing by decomposing code learning into unsupervised and supervised stages, enabling flexible algorithm choices. The paper also identifies applications and extensions for future work, including text mining, multimedia retrieval, and distributed computing.
- 5. CONCLUSIONS: STH decomposes semantic hashing into unsupervised learning and supervised learning, enabling flexibility in choosing learning algorithms.The reported implementation uses binarised-LapEig first and linear-SVM second.
- 5. CONCLUSIONS: Using binarised-LapEig and linear-SVM, STH significantly outperforms binarised-LSI, LCH, and SpH.
- 5. CONCLUSIONS: The authors propose applying STH to text mining and content-based multimedia retrieval, and combining semantic hashing with distributed computing to improve speed and scalability.