Self-taught hashing for fast similarity search

By Dell Zhang, Jun Wang, Deng Cai, Jinsong Lu. Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 2010

394 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/ae5e406971c12cd362319653837840729c39d430

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Chunhua Shen
2. Yi Yang
3. Dacheng Tao
4. Lawrence Carin
5. Jianfeng Gao
6. Qi Tian
7. Jiashi Feng
8. Liang Lin

In Computer Vision and Pattern Recognition

1. Dacheng Tao
2. Luc Van Gool
3. Yi Yang
4. Chunhua Shen
5. Xiaogang Wang
6. Ming-Hsuan Yang
7. Qi Tian
8. Jingdong Wang

Citations in the corpus

• Supervised Hashing for Image Retrieval via Image Representation Learning (2014, methodology): “To avoid this issue, one of the popular ways is decomposing the learning process into a hash code learning stage followed by a hash function learning stage (e.g., (Zhang et al. 2010; Lin et al. 2013)).”
• Inductive Hashing on Manifolds (2013, methodology): “We see that STH and AGH obtain relatively high precisions when a small number of samples are returned, however precision drops significantly as the number of retrieved samples increases.”
• A Survey on Learning to Hash (2016, background): “There aremany other extensions in awide range, including similarity graph extensions [75], [179], [92], [86], [84], [79], [128], [170], hash function extensions [40], [124], weighted Hamming distance [153], self-taught hashing [166], sparse hash codes [177], discrete hashing [164], and so on.”
• Inter-media hashing for large-scale retrieval from heterogeneous data sources (2013, methodology): “Unsupervised hashing just uses unlabeled data, such as spectral hashing [32] and self-taught hashing [36].”
• Semantics-preserving hashing for cross-view retrieval (2015, methodology): “Existing hashing methods can be roughly classified into two categories: single-view hashing [16, 21, 4, 11, 6, 13, 8, 22, 10] and multi-view hashing [1, 9, 20, 24, 23, 18, 27, 14, 3, 25, 17, 26, 19], with the former focusing on data with a single view while the latter focusing on that with multiple…”
• Collective Matrix Factorization Hashing for Multimodal Data (2014, background): “We also prove that CMFH, a similaritypreserving hashing learning method, has upper and lower boundaries.”
• TOPSIG: topology preserving document signatures (2011, methodology): “Recent approaches to similarity search [23] have explored similar ideas to TopSig for mapping documents to N bit”
• Hashing for Similarity Search: A Survey (2014, background): “Self-taught hashing [144] optimizes an objective function, similar to the spectral hashing,”
• Variational Deep Semantic Hashing for Text Documents (2017, methodology): “Self Taught Hashing (STH) [41] is the state-of-the-art hashing methodby decomposing the learning procedure into two steps: generating binary code and learning hash function.”
• Fast Supervised Hashing with Decision Trees for High-Dimensional Data (2014, methodology): “Several state-of-the-art supervised methods are included in this comparison: KSH [16], Supervised SelfTaught Hashing (STHs) [28], and Semi-supervised Hashing (SPLH) [24].”
• Multiple feature hashing for real-time large scale near-duplicate video retrieval (2011, methodology): “Compared with the hashing algorithms proposed in [27, 35] where only local information is considered, it may eliminate the problem of overfitting, making the learning more robust.”
• Discriminative coupled dictionary hashing for fast cross-media retrieval (2014, methodology): “Since then, many extensions of SH have been proposed [27, 11, 20, 21, 5, 12].”
• Learning to Hash for Indexing Big Data—A Survey (2015, methodology): “Another effective hash code ranking method is the query-sensitive hashing, which explores the raw feature of the query sample and learns query-specific weights of hash bits to achieve accurate ǫnearest neighbor search [94].”
• Bit-Scalable Deep Hashing With Regularized Similarity Learning for Image Retrieval and Person Re-Identification (2015, methodology): “Speci fically, unsupervised methods learn the hash functions using unlabeled data, which seek to propagate neighborhood relation of samples from a certain metric space into the Hamming space [13][21][22][23][24].”
• Hashing with binary autoencoders (2015, methodology): “Variations of this include using AnchorGraphs [20] to define the eigenfunctions, or obtaining the hash function directly as a binary classifier using the codes from spectral hashing as labels [31].”
• NASH: Toward End-to-End Neural Architecture for Generative Semantic Hashing (2018, background): “Given that today, an ordinary PC is able to execute millions of Hamming distance computations in just a few milliseconds (Zhang et al., 2010), this semantic hashing strategy is very computationally attractive.”
• Latent semantic sparse hashing for cross-modal similarity search (2014, background): “However, LSH may lead to ineffective codes in practice because it is data-independent [34].”
• Supervised Discrete Hashing (2015, neutral): “The similar idea was also adopted in [17,18,39].”