Hashing on Nonlinear Manifolds

Fumin Shen, Chunhua Shen, Qinfeng Shi, Anton van den Hengel, Zhenmin Tang, Heng Tao Shen

Abstract

Learning based hashing methods have attracted considerable attention due to their ability to greatly increase the scale at which existing algorithms may operate. Most of these methods are designed to generate binary codes preserving the Euclidean similarity in the original space. Manifold learning techniques, in contrast, are better able to model the intrinsic structure embedded in the original high-dimensional data. The complexities of these models, and the problems with out-of-sample data, have previously rendered them unsuitable for application to large-scale embedding, however. In this work, how to learn compact binary embeddings on their intrinsic manifolds is considered. In order to address the above-mentioned difficulties, an efficient, inductive solution to the out-of-sample data problem, and a process by which non-parametric manifold learning may be used as the basis of a hashing method is proposed. The proposed approach thus allows the development of a range of new hashing techniques exploiting the flexibility of the wide variety of manifold learning approaches available. It is particularly shown that hashing on the basis of t-SNE outperforms state-of-the-art hashing methods on large-scale benchmark datasets, and is very effective for image classification with very short code lengths. The proposed hashing framework is shown to be easily improved, for example, by minimizing the quantization error with learned orthogonal rotations. In addition, a supervised inductive manifold hashing framework is developed by incorporating the label information, which is shown to greatly advance the semantic retrieval performance.

Introduction

In the era of big data, efficient image retrieval relies on representing high-dimensional features as compact binary "hash" codes. Traditional hashing methods, such as Locality Sensitive Hashing (LSH) or PCA Hashing, typically assume that data is distributed linearly or that Euclidean distance is the optimal measure of similarity. However, high-dimensional image data often lies on complex, curved surfaces known as nonlinear manifolds. While manifold learning techniques like Laplacian Eigenmaps or t-SNE excel at capturing this intrinsic geometry, they have historically suffered from two major drawbacks: poor scalability due to $O(n^2)$ complexity and the "out-of-sample" problem, where mapping new data points requires re-running the entire embedding process.

The Inductive Manifold Hashing (IMH) Framework

To overcome these limitations, the authors propose Inductive Manifold Hashing (IMH). This framework enables the use of non-parametric manifold learning for large-scale hashing through an inductive approach. The process consists of four key stages:

  1. Base Set Selection: To ensure scalability, the algorithm identifies a small, representative "base set" of anchor points using K-means clustering.
  2. Manifold Embedding: This small base set is embedded into a low-dimensional space using a manifold learning algorithm. A significant finding is that t-SNE is particularly effective for hashing because its objective function prevents data points from "crowding," resulting in a more separable embedding that is easier to binarize.
  3. Inductive Mapping: Leveraging the principle that manifolds are locally linear, the position of any new data point (out-of-sample) is estimated as a weighted combination of its nearest neighbors in the base set. This reduces the computational cost to $O(m)$ per point, where $m$ is the small number of anchors.
  4. Binarization and Optimization: The continuous manifold coordinates are converted into binary codes. To minimize information loss during this "quantization" step, the framework applies an orthogonal rotation to the data, a technique inspired by Iterative Quantization (ITQ).

The framework also supports a supervised variant (IMHs) that incorporates label information via Linear Discriminant Analysis (LDA) to further enhance semantic retrieval performance.

Key Results and Discussion

The IMH framework was evaluated on benchmark datasets including MNIST, CIFAR-10, SIFT1M, and GIST1M.

Visual comparison of retrieval results on MNIST. (a) Queries; (b) Euclidean distance on raw 784D features; (c) LSH with 128 bits; (d) Euclidean distance on the proposed 48D manifold embedding; (e) Hamming distance using 48-bit binary codes from IMH.

As shown in the figure above, preserving the manifold structure leads to significantly better semantic retrieval. While raw Euclidean distance (b) and LSH (c) often return digits of different classes that happen to be close in pixel space, the manifold-based embedding (d) and the resulting binary codes (e) consistently retrieve the correct digit class.

Quantitatively, IMH-tSNE consistently outperformed state-of-the-art methods like ITQ and Spectral Hashing, especially at short code lengths (16–32 bits). On the MNIST dataset, 128-bit binary codes generated by IMH achieved a classification accuracy of 94.1% using a simple linear SVM—matching the performance of the original 784-dimensional raw features while offering massive gains in storage and search speed.

Conclusion

Inductive Manifold Hashing provides a robust bridge between the descriptive power of nonlinear manifold learning and the efficiency requirements of large-scale retrieval. By utilizing t-SNE for embedding and a locally linear inductive step for scalability, IMH captures the intrinsic geometry of data more effectively than Euclidean-based methods, setting a new standard for compact binary hashing.

Summary updated

Abstract

Learning based hashing methods have attracted considerable attention due to their ability to greatly increase the scale at which existing algorithms may operate. Most of these methods are designed to generate binary codes preserving the Euclidean similarity in the original space. Manifold learning techniques, in contrast, are better able to model the intrinsic structure embedded in the original high-dimensional data. The complexities of these models, and the problems with out-of-sample data, have previously rendered them unsuitable for application to large-scale embedding, however. In this work, how to learn compact binary embeddings on their intrinsic manifolds is considered. In order to address the above-mentioned difficulties, an efficient, inductive solution to the out-of-sample data problem, and a process by which non-parametric manifold learning may be used as the basis of a hashing method is proposed. The proposed approach thus allows the development of a range of new hashing techniques exploiting the flexibility of the wide variety of manifold learning approaches available. It is particularly shown that hashing on the basis of t-SNE outperforms state-of-the-art hashing methods on large-scale benchmark datasets, and is very effective for image classification with very short code lengths. The proposed hashing framework is shown to be easily improved, for example, by minimizing the quantization error with learned orthogonal rotations. In addition, a supervised inductive manifold hashing framework is developed by incorporating the label information, which is shown to greatly advance the semantic retrieval performance.
BibTeX
@article{shen2015hashing,
  author = {Fumin Shen and Chunhua Shen and Qinfeng Shi and Anton van den Hengel and Zhenmin Tang and Heng Tao Shen},
  title = {{Hashing on Nonlinear Manifolds}},
  journal = {IEEE Trans. Image Process.},
  year = {2015},
  url = {https://openreview.net/forum?id=e3nds3bssf},
}
Figure