Deep Discrete Supervised Hashing

Qing-Yuan Jiang, Xue Cui, Wu-Jun Li

TL;DR

Deep Discrete Supervised Hashing (DDSH) is the first end-to-end framework that uses supervised information to directly guide both discrete binary code learning and deep feature representation simultaneously. By avoiding the common pitfall of "continuous relaxation," DDSH achieves state-of-the-art accuracy in large-scale image retrieval across multiple benchmarks.

What Problem Does This Paper Address?

In the era of massive data, finding similar images quickly requires hashing: mapping high-dimensional images into short, binary codes (e.g., 32 bits). This allows for lightning-fast searches using Hamming distance.

The authors identify a major gap in existing research. Most "deep hashing" methods use deep learning to extract features but rely on relaxation strategies—treating discrete binary bits as continuous values during training to make them compatible with gradient descent. This often leads to sub-optimal binary codes. Conversely, "discrete supervised hashing" methods optimize binary codes directly but usually rely on hand-crafted features rather than learning them from scratch.

DDSH bridges this gap by creating a unified framework where supervised labels (knowing which images are similar) directly influence both the discrete optimization of the codes and the training of the neural network.

Methods

The DDSH architecture consists of two main components: a Feature Learning Part and a Loss Part.

  1. Feature Learning: The authors utilize a CNN-F architecture (5 convolutional layers and 3 fully-connected layers). The final layer outputs a vector that is passed through a sign function to generate binary codes.
  2. Discrete Optimization via Column Sampling: To handle the massive computational cost of comparing every image pair in a large dataset, DDSH uses a "column sampling" method. It randomly samples a subset of the training data ($\mathbf{X}^\Omega$) to serve as anchors.
  3. Alternating Learning Strategy: The model trains in two alternating steps:
  4. Step 1: Fix the CNN and optimize the discrete binary codes for the sampled set ($\mathbf{B}^\Omega$) using Binary Quadratic Programming (BQP). This ensures the codes are truly discrete and optimal for the given features.
  5. Step 2: Fix the binary codes and update the CNN parameters. Since the sign function has a zero gradient, they use a tanh relaxation during backpropagation to allow the network to learn "hash-friendly" features.

Datasets

The authors evaluated DDSH on three standard image retrieval benchmarks:

  • CIFAR-10: 60,000 images across 10 classes (single-label).
  • SVHN (Street View House Numbers): Over 600,000 images of digits in natural scenes (single-label).
  • NUS-WIDE: A large-scale dataset of ~270,000 images with multi-label annotations (the authors focused on the top 10 most frequent concepts).

Key Insights and Ideas

  • The Power of Direct Guidance: The "aha moment" here is that supervised information shouldn't just be at the end of the pipeline. By including similarity labels in the discrete code optimization and the feature learning, the two processes provide better feedback to each other.
  • Avoiding the "Relaxation Gap": Most deep hashing methods lose accuracy when they "round" continuous values into binary bits at the very end. By optimizing discrete codes during training, DDSH ensures the network learns representations that are inherently suited for binary quantization.
  • Efficiency through Sampling: The use of column sampling (inspired by the earlier COSDISH algorithm) proves that you don't need to compute a full $N \times N$ similarity matrix to train a high-performing deep model, making it scalable to larger datasets.

Key Results

DDSH consistently outperformed nine state-of-the-art baselines, including popular deep methods like DPSH and DSH.

  • Accuracy (MAP): On CIFAR-10 with 32-bit codes, DDSH achieved a Mean Average Precision (MAP) of 0.835, significantly higher than DSH (0.786) and DPSH (0.740).
  • Consistency: The performance gains were consistent across all bit lengths (12, 24, 32, and 48 bits) and all three datasets.
  • Lookup Success: In hash lookup tasks (finding a neighbor within a small Hamming radius), DDSH reached a success rate of nearly 0.9 for 48-bit codes on CIFAR-10, outperforming competitors by a wide margin.

Limitations and Future Work

  • Pairwise Focus: This paper specifically focuses on pairwise labels (similar/dissimilar). The authors note that extending this discrete optimization framework to triplet labels (ranking A as more similar to B than C) is a promising direction for future research.
  • The Tanh Proxy: While the code optimization is discrete, the CNN update still relies on a tanh approximation to handle gradients. Finding a way to perform truly discrete gradient-based updates for the neural network remains an open challenge in the field.
  • Dataset Scale: While NUS-WIDE is large, testing on even more massive, "in-the-wild" datasets (like ImageNet-100k) would further validate the scalability of the column sampling approach.

Summary updated

Abstract

Hashing has been widely used for large-scale search due to its low storage cost and fast query speed. By using supervised information, supervised hashing can significantly outperform unsupervised hashing. Recently, discrete supervised hashing and feature learning based deep hashing are two representative progresses in supervised hashing. On one hand, hashing is essentially a discrete optimization problem. Hence, utilizing supervised information to directly guide discrete (binary) coding procedure can avoid sub-optimal solution and improve the accuracy. On the other hand, feature learning based deep hashing, which integrates deep feature learning and hash-code learning into an end-to-end architecture, can enhance the feedback between feature learning and hash-code learning. The key in discrete supervised hashing is to adopt supervised information to directly guide the discrete coding procedure in hashing. The key in deep hashing is to adopt the supervised information to directly guide the deep feature learning procedure. However, most deep supervised hashing methods cannot use the supervised information to directly guide both discrete (binary) coding procedure and deep feature learning procedure in the same framework. In this paper, we propose a novel deep hashing method, called deep discrete supervised hashing (DDSH). DDSH is the first deep hashing method which can utilize pairwise supervised information to directly guide both discrete coding procedure and deep feature learning procedure and thus enhance the feedback between these two important procedures. Experiments on four real datasets show that DDSH can outperform other state-of-the-art baselines, including both discrete hashing and deep hashing baselines, for image retrieval.
BibTeX
@article{jiang2018deep,
  author = {Qing-Yuan Jiang and Xue Cui and Wu-Jun Li},
  title = {{Deep Discrete Supervised Hashing}},
  journal = {IEEE Trans. Image Process.},
  year = {2018},
  url = {https://openreview.net/forum?id=nfWliC23Zu},
}

Loading related content...

Figure