PaperlayerView exact revision on arXiv

Source-linked AI summary

Asymmetric Deep Supervised Hashing

Qing-Yuan Jiang, Wu-Jun Li

arXiv:1707.08325v1cs.LGstat.ML

TL;DR

Symmetric deep supervised hashing is costly for large databases because it learns one function for queries and database points and often requires sampling. ADSH instead learns the query function while directly learning database codes, achieving state-of-the-art performance with more efficient training.

  • Problem

    Symmetric deep supervised hashing is time-consuming for large databases, with pairwise costs of O(n^2) and frequent database-point sampling.

  • Method

    ADSH learns a deep hash function only for query points while directly learning binary hash codes for database points.

  • Results

    ADSH achieves state-of-the-art performance in real applications and outperforms deep, non-deep supervised, and unsupervised baselines in MAP.

  • Takeaways & Limitations

    ADSH's efficient training allows the whole database to be used for training even when the database is large.

  • Takeaways & Limitations

    The study focuses only on pairwise-label-based supervised hashing.

Abstract

from arXiv · show

Hashing has been widely used for large-scale approximate nearest neighbor search because of its storage and search efficiency. Recent work has found that deep supervised hashing can significantly outperform non-deep supervised hashing in many applications. However, most existing deep supervised hashing methods adopt a symmetric strategy to learn one deep hash function for both query points and database (retrieval) points. The training of these symmetric deep supervised hashing methods is typically time-consuming, which makes them hard to effectively utilize the supervised information for cases with large-scale database. In this paper, we propose a novel deep supervised hashing method, called asymmetric deep supervised hashing (ADSH), for large-scale nearest neighbor search. ADSH treats the query points and database points in an asymmetric way. More specifically, ADSH learns a deep hash function only for query points, while the hash codes for database points are directly learned. The training of ADSH is much more efficient than that of traditional symmetric deep supervised hashing methods. Experiments show that ADSH can achieve state-of-the-art performance in real applications.

1 Introduction

Hashing supports efficient large-scale approximate nearest neighbor search, while deep supervised hashing improves performance through end-to-end feature and hash-code learning. ADSH addresses the scalability limits of symmetric deep supervised hashing by learning query functions and database codes asymmetrically.

  • Hashing encodes data points into compact binary codes for storage- and search-efficient large-scale approximate nearest neighbor search.
  • Data-dependent hashing learns hash functions from training data and typically outperforms data-independent methods with shorter binary codes.
  • Deep supervised hashing integrates feature learning and hash-code learning end to end, significantly outperforming non-deep supervised hashing in many applications.
  • Symmetric deep supervised hashing learns one function for queries and database points, but pairwise costs reach O(n^2) and triplet costs are higher.
  • ADSH learns a deep hash function only for queries while directly learning database codes, enabling more efficient training and state-of-the-art performance on large-scale datasets.

2 Notation and Problem Definition

The problem uses query and database points linked by pairwise similarity labels, seeking binary codes that preserve those similarities while supporting unseen queries. The notation distinguishes vectors, matrices, columns, and binary code length.

  • 2.1 Notation: Boldface lowercase letters denote vectors, boldface uppercase letters denote matrices, and B∗j denotes the jth column of matrix B.
  • 2.2 Problem Definition: The data comprise m query points X and n database points Y connected by pairwise similarity information S.
  • 2.2 Problem Definition: Similarity labels use Sij = 1 for similar query-database pairs and otherwise indicate dissimilarity.
  • 2.2 Problem Definition: The objective is to learn binary query and database codes whose Hamming distances are small for similar pairs and large for dissimilar pairs.
  • 2.2 Problem Definition: The binary code length is c, and a hash function h(xq) must generate codes for unseen query points.
  • 2.2 Problem Definition: When queries are unavailable, a sampled subset or the whole database can serve as the query set, so X ⊆Y.

3 Asymmetric Deep Supervised Hashing

ADSH combines deep feature learning for query points with direct binary-code learning for database points, optimizing their similarity relationships asymmetrically. It uses differentiable approximations during training and can train from either paired queries or sampled database points.

  • 3.1 Model Formulation: ADSH integrates a feature-learning component and a similarity-preserving loss component in one end-to-end framework.
  • 3.1 Model Formulation: Feature learning is performed only for query points; query codes come from a deep hash function, while database codes are directly learned.
  • 3.1.2 Loss Function Part: The formulation optimizes query-database code relationships using inner products while constraining binary query and database codes.
  • 3.1.2 Loss Function Part: Because sign outputs block back-propagation, ADSH uses tanh as a differentiable approximation during optimization.
  • 3.1.3 Training with Only Database Points: When only database points are available, ADSH samples m of them as queries and uses the corresponding similarity submatrix for training.
  • 3.1.3 Training with Only Database Points: For database points also used as queries, ADSH encourages directly learned database codes to match their network representations.
  • 3.1.4 Discussion: Since m ≪n generally, ADSH trains the deep network more efficiently than symmetric methods while producing codes for databases and a query function for new queries.

3.2 Learning Algorithm

ADSH alternates between updating neural-network parameters and database hash codes. With Θ fixed, it updates V bit by bit using an objective derived from the query representations and supervised information.

  • Alternating optimization: ADSH uses alternating optimization, learning Θ with V fixed and then V with Θ fixed across repeated iterations.Each parameter is optimized while the other remains fixed.
  • Learn Θ with V fixed: With V fixed, ADSH samples query points, computes representations by forward propagation, and updates Θ using back-propagation.The query mini-batch supplies the gradient used to update the neural-network parameters.
  • Learn V with Θ fixed: With Θ fixed, ADSH rewrites the database-code optimization in matrix form using V, query representations, and supervised-information terms.The reformulation includes Q = −2cSTeU −2γŪ, with constants independent of V.
  • Learn V with Θ fixed: ADSH updates each column V∗k separately while holding the remaining columns fixed, then applies the resulting optimal solution.The kth-column objective is defined using the corresponding columns of V and eU.
  • Overall procedure: The complete algorithm repeats query-set sampling, mini-batch parameter updates, and bit-by-bit database-code updates for multiple iterations.Each repetition uses a sampled query index set Ω and updates all c code columns.

3.3 Out-of-Sample Extension

After training, ADSH generates binary codes for unseen query points with its learned neural network. Its training complexity is O(n), compared with at least O(n^2) for traditional symmetric methods when all database points are used.

  • Out-of-sample extension: ADSH generates a binary code for each query xq by applying sign to the network output h(xq; Θ).The learned network supports query points not seen during training.
  • Learning algorithm: Algorithm 1 initializes Θ, V, batch size M, and iteration counts before repeatedly sampling query subsets and updating the model.The outer loop samples an index set Ω, while the inner loop performs repeated parameter updates.
  • Learning algorithm: Each inner iteration samples M query points, computes representations by forward propagation, updates Θ by back-propagation, and then updates V∗k for k = 1 to c.The database codes are updated after the neural-network update loop.
  • Computational complexity: O(n): ADSH’s practical training complexity, versus at least O(n^2) for traditional symmetric methods using all database points.ADSH scans only m points per neural-network-training epoch, with m ≪ n, while symmetric methods scan n.
  • Computational complexity: ADSH can use more database points during training because it is more efficient than symmetric methods that often sample only a small database subset.The comparison concerns utilization of supervised information from large databases.

4 Experiment

Experiments on CIFAR-10 and NUS-WIDE compare ADSH with ten hashing baselines using MAP, top-2000 precision, and training-time evaluations. ADSH achieves stronger retrieval performance while training faster, particularly as training sets and code lengths increase.

  • 4.1 Datasets: Experiments evaluate ADSH on CIFAR-10 and NUS-WIDE against ten state-of-the-art hashing baselines.CIFAR-10 contains 60,000 single-label images, while the selected NUS-WIDE subset contains 195,834 images from 21 frequent concepts.
  • 4.3 Accuracy: MAP results show ADSH outperforming deep, non-deep supervised, and unsupervised baselines in most cases.The comparison is reported in Table 1.
  • 4.3 Accuracy: Directly learned database codes outperform hash-function-generated database codes for Lin:V, LFH-D, SDH-D, and COSDISH-D.These adapted counterparts use all database points for training and outperform their corresponding original methods.
  • 4.3 Accuracy: ADSH significantly outperforms other baselines on top-2000 precision across both datasets, especially at larger code lengths.The top-2000 precision results are shown in Figure 2.
  • 4.4 Time Complexity: ADSH trains much faster than other deep hashing methods, while traditional baselines become dramatically more expensive as the training set grows.With 58,000 training points, ADSH remains faster than every deep baseline trained on 5,000 points.
  • 4.4 Time Complexity: On NUS-WIDE with 12-bit codes, ADSH is faster than sampled or whole-database baselines at similar accuracy and achieves higher accuracy with less time.Using the whole database requires more than 10 hours for most baselines to converge; longer codes cost even more.

5 Conclusion

The paper concludes that ADSH is an asymmetric deep supervised hashing method for large-scale nearest neighbor search. Experiments report state-of-the-art performance in real applications.

  • 5 Conclusion: ADSH is presented as the first deep supervised hashing method to adopt an asymmetric strategy for query and database points.It learns a deep hash function for queries while directly learning database binary codes.
  • 5 Conclusion: Experiments show that ADSH achieves state-of-the-art performance in real applications.

A Precision-Recall Curve

The precision-recall curves evaluate hash-lookup accuracy across Hamming radii on two datasets, with ADSH achieving the best performance in most cases.

  • Precision-recall curves measure hash-lookup accuracy, with each marked point corresponding to a Hamming radius from the query code.
  • ADSH achieves the best precision-recall performance on both datasets in most cases.

B The Effectiveness of CNN Network Structure

Using CNN-F network structures improves retrieval accuracy compared with the original structures, so CNN-F is used for fair comparison across deep hashing methods.

  • CNN-F network structures achieve higher retrieval accuracy than the original network structures on CIFAR-10.
  • CNN-F is used as the network structure for all deep hashing methods to ensure fair comparison.

C Sensitity to the Hyper-parameters

ADSH is insensitive to γ across a broad range, while more sampled query points improve retrieval accuracy at increased computation cost.

  • ADSH is not sensitive to γ across the range 10^-2 < γ < 10^3 on CIFAR-10.
  • Larger numbers of sampled query points improve ADSH retrieval accuracy but increase computation cost.
  • With m = 1000, ADSH significantly outperforms deep supervised hashing baselines in both accuracy and efficiency.

D Case Study

The CIFAR-10 case study compares top-10 retrieval results for shared test points, using red rectangles to mark non-ground-truth neighbors; ADSH significantly outperforms three leading baselines at 12 bits.

  • The case study uses randomly sampled test points and displays their top-10 returned samples from the retrieval set.
  • ADSH and all baselines are evaluated using the same test points.
  • At 12 bits, red rectangles identify returned images that are not ground-truth neighbors of the corresponding test images.
  • ADSH significantly outperforms the three best baselines in the CIFAR-10 case study.
Loading 1707.08325v1…