A Study Of Hashing For Fast Approximate Nearest Neighbors Retrieval

With the rapid development of Internet, over the last decades, there has been an explosive growth of data on the Internet. Large scale dataset makes it more reliable to train more complex machine learning models and also improves the generalization ability of models to some degree. But at the same time, with huge calculation and time cost in training and testing stage, some machine learning algorithms face great availability problems. Especially, K nearest neighbor (KNN) search plays a fundamental role in machine learning and linear search on large scale dataset for KNN search will take a lot of time. Hashing, one of the most well-known Approximate Nearest Neighbor (ANN) search methods, finding a balance between retrieval efficiency and accuracy, has gained considerable interests in recent years.On the other hand, a large amount of objects on the Web are displayed in different modalities. For example, a microblog may consist of a short text and correlative images or videos. With the fast growth of multimodal content on the Web, the requirement of cross-modal retrieval becomes a new problem to both the industry and the researchers. As data in different modalities may have features with different lengths, a most common way for cross-modal retrieval is to map different modalities into a common latent space, reducing the heterogeneity among the different modal features. Among these methods, cross-modal hashing can achieve fast retrieval.This thesis studies an unsupervised hashing and cross-modal hashing. Due to the effective calculation of binary code distance, hashing may achieve dozens or even hundreds of times faster than linear search for KNN retrieval. In this paper, two aspects are studied:1)a linear unsupervised hashing in Euclidean space(USEH algorithm).Some hashing methods apply RBF kernel functions to measure the similarity between samples in Euclidean space and construct similarity matrix in this way. USEH adopts the same method to preserve similarity between samples while mapped into latent space. However, this pair-wise similarity matrix could be very huge for large train set and will take up a lot of memory. To tackle this problem, USEH uses LSH vectors to approximate RBF kernel functions. Specifically, USEH applies LSH algorithm on the unsupervised dataset to generate pseudo label, and then takes the production of pseudo label matrix and its transpose to approximate the similarity matrix. By this way, it can reduce the memory and time cost in training stage. Besides, as hashing code orthogonal constraints will lead to loss of information, USEH adopts sequential learning strategy to learn hashing function one by one, abandoning orthogonal constraints to retain more variance information. With the growth of hashing code length, the sequential learning method of USEH shows its superiority more obviously compared with the orthogonal constraints method.2) A dictionary learning based cross-modal hashing (DLCMH algorithm). DLCMH maps features from different modalities into a common latent space and assumes the same hashing code for different modal features of an object. Usually, linear projection matrix is hard to correct the bias between distance and semantic similarity within features from the same modality. To tackle this problem, DLCMH introduces dictionary learning to learn semantic information automatically and then uses linear projection matrix to map dictionary representations into Hamming space. In the optimization stage, DLCMH relaxes the hashing code matrix for easier gradient derivation and divides the optimization problem into several small tacklable sub-problems.To test the performance of the proposed methods, several groups of experiments are conducted on some published datasets. The proposed methods are also compared with some state-of-the-arts including unsupervised and cross-modal hashing methods. The results show that the proposed methods can obtain good results and have good potential for application in machine learning, computer vision and information retrieval, etc.