How should we evaluate supervised hashing?

Alexandre Sablayrolles, Matthijs Douze, Hervé Jégou, Nicolas UsunierICASSP 2016 · DOI · OpenReview

Abstract

Hashing produces compact representations for documents to perform tasks like classification or retrieval based on these short codes. When hashing is supervised, the codes are trained using labels on the training data. This paper shows that current evaluation protocols for supervised hashing are unsatisfactory: a trivial solution encoding classifier output significantly outperforms existing methods while using much shorter codes. We propose two alternative protocols: retrieval on a disjoint set of classes and transfer learning to new classes. We provide baselines (without coding and with unsupervised codes) to bound supervised hashing performance.

Introduction

Hashing is a critical technique for transforming complex data, such as images, into short binary codes to enable rapid retrieval and efficient storage. In supervised hashing, class labels are utilized during training to ensure that semantically similar items are mapped to similar codes. However, the current evaluation methodology in this field is fundamentally flawed. Standard benchmarks typically test systems on the same categories encountered during training. This approach reduces a complex representation problem to a simple classification task; if a model recognizes a "dog," it merely needs to store the label "dog" rather than learning a nuanced data structure.

The Trivial Baseline and Proposed Protocols

To expose these flaws, we introduce a "trivial baseline." Instead of employing complex deep hashing architectures, we:

  1. Train a standard classifier (e.g., a CNN).
  2. Predict the class for any new image.
  3. Store the class index as the "hash code" (e.g., 10 classes require only 4 bits).

To ensure rigorous evaluation, we propose two protocols centered on generalization:

  • Protocol 1 (Retrieval of unseen classes): The model is trained on 75% of a dataset's classes and evaluated on the remaining 25% it has never seen. This tests the ability of the hashing scheme to generalize to categories not encountered during training, a requirement for real-world retrieval systems.
  • Protocol 2 (Transfer learning): Hash codes generated for unseen classes are used to train a new classifier. This tests if the codes preserve sufficient semantic information to be useful for novel tasks.

Experimental Results

We evaluated these protocols using CIFAR-10, CIFAR-100 (split for unseen classes), and ImageNet (ILSVRC 2012). The results demonstrate that existing metrics primarily measure classification accuracy rather than hashing quality.

On CIFAR-10, our trivial "one-hot" baseline achieved a mean Average Precision (mAP) of 73.0 using only 4 bits. In contrast, the state-of-the-art supervised method (SQ) achieved only 71.2 mAP while requiring 128 bits.

Performance comparison on CIFAR-10 showing the trivial 4-bit baseline outperforming state-of-the-art methods.

This phenomenon persists at scale. On the ImageNet dataset, a simple 10-bit classifier-based code reached 66.4 mAP, outperforming complex methods using 128 bits (62.0 mAP).

ImageNet results comparing the 10-bit classifier-based code against 128-bit SQ.

In the new "unseen class" protocol on CIFAR-100, we found that uncompressed features from the conv3 layer achieved 69.6% accuracy, providing a much more challenging and meaningful benchmark for future researchers.

Key Insights

  • The Semantic Bottleneck: Many existing methods encode the final softmax layer. While highly compressible, this layer is often too specialized for general retrieval.
  • Middle-Out Compression: For transfer learning, compressing features from middle layers (e.g., convolutional layers) is more effective. These features are more "general purpose" and describe unseen classes better, despite requiring more bits.
  • Performance Bounds: Supervised hashing should be benchmarked against two extremes: uncompressed features (upper bound) and simple unsupervised methods like Locality Sensitive Hashing (LSH) or Product Quantization (lower bound).

Conclusion

While this study focuses on image retrieval, the implications likely extend to other domains. We do not propose a "new best" algorithm but rather provide the tools and baselines necessary to ensure future progress in supervised hashing is meaningful. Future research should focus on efficiently compressing mid-level features to maintain generalizability for unseen data.

Summary updated

Abstract

Hashing produces compact representations for documents, to perform tasks like classification or retrieval based on these short codes. When hashing is supervised, the codes are trained using labels on the training data. This paper first shows that the evaluation protocols used in the literature for supervised hashing are not satisfactory: we show that a trivial solution that encodes the output of a classifier significantly outperforms existing supervised or semi-supervised methods, while using much shorter codes. We then propose two alternative protocols for supervised hashing: one based on retrieval on a disjoint set of classes, and another based on transfer learning to new classes. We provide two baseline methods for image-related tasks to assess the performance of (semi-)supervised hashing: without coding and with unsupervised codes. These baselines give a lower- and upper-bound on the performance of a supervised hashing scheme.
BibTeX
@inproceedings{sablayrolles2016how,
  author = {Alexandre Sablayrolles and Matthijs Douze and Hervé Jégou and Nicolas Usunier},
  title = {{How should we evaluate supervised hashing?}},
  booktitle = {ICASSP},
  year = {2016},
  doi = {10.1109/icassp.2017.7952453},
}
Figure