PaperlayerView exact revision on arXiv

Source-linked AI summary

Hashing on Nonlinear Manifolds

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

arXiv:1412.0826v1cs.CV

TL;DR

Manifold learning can better model intrinsic nonlinear structure than conventional Euclidean hashing, but its computational complexity and out-of-sample limitations impede large-scale embedding. The paper introduces an efficient inductive framework that converts manifold embeddings into binary codes, and reports that t-SNE-based hashing outperforms state-of-the-art methods while rotations and supervision further improve performance.

  • Problem

    Manifold learning can model intrinsic high-dimensional structure better than Euclidean similarity, but its complexity and out-of-sample limitations hinder large-scale hashing.

  • Method

    The paper learns a manifold from a small subset, inductively embeds new points through efficient regression, and derives binary encodings reflecting manifold geodesic distances.

  • Results

    t-SNE-based IMH outperforms state-of-the-art methods on several large-scale datasets, while learned rotations and supervised extensions further improve retrieval performance.

  • Takeaways & Limitations

    The framework provides a practical connection between non-parametric manifold learning and efficient hash-function learning for large-scale retrieval.

Abstract

from arXiv · show

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.

I. INTRODUCTION

Hashing seeks compact binary codes that preserve data structure, while manifold learning can better capture nonlinear neighborhood structure but is difficult to scale and extend to new data. This work addresses those barriers with inductive manifold hashing and extensions for improved retrieval.

  • Motivation: Hashing encodes images or documents as short binary codes while preserving similarities, enabling efficient Hamming-space search and larger-scale processing.Compact codes support retrieval through nearby Hamming buckets and can also be used for image classification.
  • Motivation: Nonlinear manifold learning better preserves local structure than linear methods, and Figure 2 motivates its use by showing more semantically accurate neighbors after nonlinear embedding.The comparison considers Euclidean and Hamming search in original and t-SNE embedding spaces.
  • Challenges: Manifold hashing is hindered by O(n^2) graph construction, inefficient out-of-sample extension, and Nyström methods that cannot directly handle non-spectral methods such as t-SNE.These constraints make conventional manifold learning unsuitable for large-scale hashing and new-sample code generation.
  • Approach: The proposed framework uses efficient non-parametric regression for out-of-sample embedding and converts manifold structure into binary encodings reflecting geodesic distances.This enables hashing methods based on a range of manifold learning approaches, including t-SNE.
  • Contributions: Inductive Manifold-Hashing learns a manifold from a small subset and inserts remaining or unseen points in O(m) time per point, outperforming state-of-the-art methods on several large-scale datasets.The framework is also extended through quantization-error minimization with orthogonal rotations and supervised subspace learning.
  • Contributions: The extended paper adds learned rotations for quantization-error minimization and a supervised inductive manifold hashing framework for semantic retrieval.These are identified as major improvements over the earlier version.

II. RELATED WORK

Prior hashing methods approximate or preserve manifold structure through spectral, anchor-based, locally linear, or learned classifiers, but scalability and out-of-sample extension remain central concerns. The proposed inductive formulation addresses these concerns by embedding new points from local neighbors and a small base set.

  • Spectral Hashing: Spectral Hashing learns binary codes with balanced, uncorrelated bits, but constructing its affinity matrix costs O(dn^2) and Nyström extension costs O(rn).Its uniform-distribution assumption can also destroy the original manifold structure when the assumption is false.
  • Graph-based hashing: Anchor Graph Hashing approximates the affinity matrix with a low-rank anchor graph, achieving linear training and constant search time for Laplacian eigenmaps embeddings.Its generalized eigenfunction remains specific to the Laplacian eigenmaps embedding.
  • Graph-based hashing: Locally Linear Hashing combines locality-sensitive sparse-coding affinities with a joint objective for LLE embedding error and quantization loss.
  • Self-Taught Hashing: Self-Taught Hashing obtains each hash function by training an SVM whose class labels are pre-learned binary codes, but this can impose prohibitive computational and memory costs.The SVM training process may be especially time-consuming for dense data.
  • Inductive extension: For a new point, the inductive formulation preserves local neighborhood relationships by representing its embedding as a sparse locally linear combination of base embeddings.The objective places the new embedding near the low-dimensional embeddings of its nearest original-space neighbors.
  • Inductive extension: The formulation applies the local-linearity assumption to hash-function learning, but direct computation remains O(n^2) for some manifold methods and O(n) for out-of-sample extension.A small base set is then introduced to approximate new embeddings more efficiently.

B. The prototype algorithm

The prototype algorithm uses entropy numbers to cover the embedding with clusters, then samples weighted representatives to construct an approximate query embedding. Its approximation improves with stronger clustering and more sampled representatives.

  • B. The prototype algorithm: Entropy numbers measure the smallest radius needed to cover the embedding with at most m balls.Each ball induces a cluster with a center and index set.
  • B. The prototype algorithm: The algorithm samples indices from each cluster in proportion to their weights, with higher cluster mass receiving more draws.At least one draw is made from every cluster.
  • B. The prototype algorithm: At most 2m unique embedded points are used in the constructed approximation.This follows from the sampling allocation across m clusters.
  • B. The prototype algorithm: The prototype preserves the mean while maintaining small variance, as established by the accompanying lemma and proof.The proof invokes Chebyshev’s inequality and an earlier lemma.
  • B. The prototype algorithm: Stronger clustering and larger sample counts yield smaller approximation error.When points lie close to cluster centers, the entropy number is small and approximation improves.

C. Approximation of the prototype algorithm

The approximation replaces full-data manifold computations with cluster-center-based inductive embeddings and sign thresholding. This yields a general IMH framework whose training cost is linear in dataset size when the base set is much smaller than the training set.

  • C. Approximation of the prototype algorithm: The prototype approximates a query embedding by sampling from clusters, using cluster centers as representatives of overall weight.The method relies on cluster centers and their similarities to the data rather than all pairwise weights.
  • C. Approximation of the prototype algorithm: IMH embeds a base set, predicts the full embedding through normalized base-set weights, and thresholds the result at zero.The framework can use K-means centers as the base set.
  • C. Approximation of the prototype algorithm: The inductive hash function generalizes to new data with constant O(dm + rk) time.The embedding is binarized through the sign function.
  • C. Approximation of the prototype algorithm: IMH is not restricted to Laplacian eigenmaps because the base embedding can be learned by any manifold method preserving the target similarity.The paper identifies t-SNE as one potentially better choice for binary codes.
  • C. Approximation of the prototype algorithm: With m much smaller than n, IMH training is linear in the training-set size, although K-means dominates the computational cost.The K-means step costs O(dmnl), where l is the iteration count.

D. Stochastic neighborhood preserving hashing

The paper instantiates IMH with t-SNE to preserve local and some global structure in a low-dimensional embedding. Because original t-SNE is quadratic and non-parametric, the method applies it to a base set and uses inductive extension for new points.

  • D. Stochastic neighborhood preserving hashing: The proposed stochastic-neighborhood-preserving hashing method is based on t-SNE, a non-spectral embedding method.t-SNE is presented as a demonstration of the general IMH approach.
  • D. Stochastic neighborhood preserving hashing: t-SNE preserves local structure while retaining some global structure, making it suitable for nearest-neighbor search.Its cost function is also described as maximizing smoothed recall of queries and neighbors.
  • D. Stochastic neighborhood preserving hashing: Original t-SNE has quadratic time complexity in n and lacks a simple out-of-sample mapping.IMH addresses these issues by first applying t-SNE to the base set and then extending embeddings inductively.
  • D. Stochastic neighborhood preserving hashing: After optimizing the base-set t-SNE embedding, IMH-tSNE computes hash codes for the entire dataset through the inductive embedding.The codes are obtained from the embeddings produced by the inductive mapping.

E. Hashing with relaxed similarity preservation

The relaxed-similarity formulation learns base embeddings using smoothness within the base set and between the base set and the remaining data. It omits full pairwise smoothness within the remaining data to avoid O(n^2) computation.

  • E. Hashing with relaxed similarity preservation: The relaxed objective computes base embeddings using smoothness within the base set and between the base set and the remaining data.The trade-off parameter λ controls the relative contribution of these terms.
  • E. Hashing with relaxed similarity preservation: The formulation discards the within-X dissimilarity term because constructing X’s similarity matrix costs O(n^2).Smoothness among points in X is implicitly ensured by the inductive mapping.
  • E. Hashing with relaxed similarity preservation: For the LE instantiation, the optimal base embedding uses eigenvectors associated with the smallest nontrivial eigenvalues of M + λT.The trivial zero-eigenvalue eigenvector is excluded.
  • E. Hashing with relaxed similarity preservation: The LE-based method is named IMH-LE, with λ set to 2 in all experiments.This parameter setting is stated for the reported experiments.

F. Manifold learning methods for hashing

Within the IMH framework, t-SNE, SNE, and EE slightly outperform LE by preserving local neighborhoods while limiting crowding, and IMH-PCA substantially outperforms PCAH. LE also performs worse than PCA, while all compared manifold methods outperform exhaustive ℓ2 scanning with uncompressed GIST features.

  • IMH-tSNE, IMH-SNE, and IMH-EE slightly outperform IMH-LE because they preserve local neighborhoods while preventing data points from crowding together.
  • LE performs worse than PCA, whereas manifold methods such as t-SNE and EE better preserve local similarity while forcing dissimilar data apart.
  • IMH-PCA outperforms PCAH by a large margin despite PCAH using the whole training set, supporting generalization from a small data subset.

IV. EXPERIMENTAL RESULTS

Experiments evaluate IMH and competing hashing methods across four large-scale image datasets, with CIFAR-10 results additionally examining performance as the base-set size and nearest-base-point count vary. The reported CIFAR-10 experiment uses 64-bit codes for the parameter-sensitivity comparison.

  • IMH is evaluated on CIFAR-10, MNIST, SIFT1M, and GIST1M, covering large-scale image retrieval datasets.
  • 64-bit CIFAR-10 experiments report MAP while varying base set size m with k = 5 and nearest-base-point count k with m = 400.
  • Table I compares random sampling and K-means for generating base sets on CIFAR-10 across code lengths from 32 to 96 with base set size 400.
  • Nine hashing algorithms are compared, including IMH-tSNE, IMH-LE, PCAH, SH, AGH, STH, BRE, ITQ, and SpH.

A. Base selection

K-means is selected for base construction because it gives superior hashing performance and high practical efficiency. Larger base sets generally improve retrieval but increase training and testing costs, while a 400-point base set supports inductive preservation of MNIST’s local manifold structure.

  • K-means produces better performance than random sampling and K-medians across code lengths, so it is used in subsequent experiments.
  • The proposed methods outperform AGH in all but one case even with randomly sampled bases, while K-means combines superior results with high efficiency.
  • Increasing base set size m consistently improves performance, whereas changing the number of nearest base points k has little effect; IMH-LE outperforms IMH-LEB.
  • IMH-tSNE performance on CIFAR-10 improves consistently for m ≤400 but changes little at larger sizes, with a similar pattern reported on MNIST.
  • Training and testing costs increase with m; on CIFAR-10, IMH-tSNE training takes about 4.3 seconds at m = 400 and more than 21 seconds at m = 1,000.
  • Using 400 K-means base points, the inductive method places most MNIST samples near their corresponding digit clusters in the low-dimensional embedding.

B. Results on CIFAR-10 dataset

On CIFAR-10, IMH-LE and IMH-tSNE achieve the strongest retrieval results across code lengths, while IMH-tSNE also provides strong visual relevance and competitive efficiency. The comparisons use MAP, F1, precision, recall, and qualitative retrieval quality.

  • Retrieval performance: IMH-LE and IMH-tSNE perform best on MAP across code lengths from 16 to 128 bits.IMH-tSNE outperforms IMH-LE, while IMH-LE remains better than AGH and STH.
  • Retrieval performance: IMH-LE and IMH-tSNE outperform all other methods by large margins on F1 for Hamming-radius-2 lookup.BRE and AGH outperform the remaining methods, but all methods decline as code length grows.
  • Precision and recall: IMH-tSNE, IMH-LE, and ITQ maintain higher precision with relatively larger numbers of retrieved points than STH and AGH.STH and AGH have relatively high precision for small result sets, but their precision drops significantly as more points are retrieved.
  • Qualitative retrieval: IMH-tSNE achieves the best search quality in terms of visual relevance among the compared methods.The qualitative comparison uses sample queries and 32-bit hash codes.
  • Efficiency: IMH-tSNE is slower to train than IMH-LE, AGH, and SH but remains much faster than STH and BRE, with comparable test time to most methods.PCAH is fastest for training, while STH has substantially higher test time on the non-sparse dataset.

D. Results on SIFT1M and GIST1M

On SIFT1M and GIST1M, IMH consistently achieves superior F1 and recall with Hamming radius 2, remaining effective as longer codes make Hamming spaces sparser. On SIFT1M, IMH-tSNE retains an F1 of 0.2 at 64 bits while ITQ falls near zero.

  • Large-scale retrieval: IMH consistently achieves superior F1 and recall on SIFT1M and GIST1M with Hamming radius 2.Each dataset uses one million training samples and 10K test samples, with ground truth defined by the closest 2 percent under Euclidean distance.
  • Large-scale retrieval: 0.2 F1 is achieved by IMH-tSNE at 64 bits on SIFT1M, while ITQ decreases to near zero from its highest 16-bit F1.The passage attributes the broader decline to increasingly sparse Hamming spaces as code length grows.
  • Classification: 94.1% classification accuracy is achieved by IMH with high-bit codes, matching the accuracy from uncompressed 784D features.The uncompressed features occupy several hundred times more space than the learned hash codes.

V. MINIMIZE THE QUANTIZATION DISTORTION BY LEARNED ROTATIONS

Learned orthogonal rotations reduce quantization distortion and improve IMH retrieval performance. Supervised manifold hashing further improves semantic retrieval, while the framework remains efficient but depends on an empirically chosen base-set size.

  • Learned rotations: Orthogonal rotations are applied to zero-centred nonlinear embeddings before binarization to minimize quantization error.The embeddings are normalized and orthogonally rotated before thresholding.
  • Learned rotations: Rotations significantly improve both F1 and recall for IMH-LE and IMH-tSNE, outperforming PCA-ITQ on MNIST and CIFAR.The evaluation uses Hamming radius 2 across varying code lengths.
  • Supervised manifold hashing: Supervised inductive manifold hashing uses supervised subspace learning, with LDA producing 9-bit codes for the 10-class MNIST and CIFAR datasets.The method is compared with SSH, KSH, and CCA-ITQ.
  • Supervised manifold hashing: IMHs significantly improve MAP and F1 over original IMH and other compared supervised methods, while IMHs-ITQ adds further gains, especially on CIFAR.KSH achieves the highest MAPs with IMHs or IMHs-ITQ but requires much longer codes; CCA-ITQ performs best in F1 with long codes.
  • Supervised manifold hashing: Label information produces semantically effective codes, and the supervised framework can also use other supervised subspace or metric-learning algorithms.The framework is not restricted to LDA.
  • Scope and limitation: The framework connects non-parametric manifold learning with efficient hash-function learning, but the base-set size m was selected empirically rather than optimally.Automatically choosing m based on dataset size and distribution is left for future study.
Loading 1412.0826v1…