Supervised Binary Hash Code Learning with Jensen Shannon Divergence

Lixin FanICCV 2013 · OpenReview

Abstract

This paper proposes a statistical learning framework for learning binary hash codes by deriving an upper bound on Bayes decision errors. By maximizing the Jensen-Shannon Divergence (JSD), the authors provide a mathematically rigorous method to improve both unsupervised and supervised hashing algorithms. Additionally, the paper introduces Haar-Like hash functions (HALF), which achieve significant speedups in coding time compared to traditional projection-based methods.

Introduction

Efficient similarity search in massive high-dimensional image databases is a cornerstone of modern computer vision. Binary hashing maps data into short bitstrings, enabling rapid similarity calculations via Hamming distance. However, many existing supervised hashing methods rely on heuristic objectives that lack a direct theoretical link to classification error. This work addresses this gap by framing hash learning as a statistical classification problem optimized via Jensen-Shannon Divergence.

Methodology

The JSD Objective

The core contribution is the use of Jensen-Shannon Divergence as an objective function. The authors prove that the probability of a Bayes decision error is upper-bounded by a function of JSD. Maximizing JSD thus directly minimizes the potential for misclassification. This objective naturally balances "bit balance" (an unsupervised goal) and "class separation" (a supervised goal), providing a consistent framework for various hashing tasks.

Sequential Learning

To construct the hash codes, the authors employ a greedy sequential algorithm. Each new bit is selected to maximize the JSD of the cumulative code. Theorem 1 in the paper provides a rigorous proof that this sequential approach monotonically improves the error bound, ensuring that each additional bit contributes to better retrieval performance.

Haar-Like Hash Functions (HALF)

For real-time and mobile applications, the "coding time"—the time required to convert an image feature into a bitstring—is critical. Traditional methods use computationally expensive matrix projections. Inspired by the Viola-Jones detector, the authors propose HALF, which uses simple binary tests (e.g., comparing two dimensions $x_i > x_j$). This approach requires no multiplications, making it orders of magnitude faster than projection-based alternatives.

Experimental Results

The proposed framework was evaluated on standard benchmarks including CIFAR10, CIFAR100, and LabelMe22k using both semantic and Euclidean labels.

Performance Gains

Integrating JSD-based supervision into existing algorithms consistently yields performance boosts. For instance, LSH-JSD shows a marked improvement in precision over standard Locality Sensitive Hashing (LSH) as the number of bits increases, demonstrating the effectiveness of the JSD supervision.

Precision comparison between standard LSH and LSH-JSD across varying bit lengths.

Robustness to Label Noise

A key advantage of the JSD framework is its resilience to imperfect data. Experiments demonstrated that even with significant label noise, the precision-recall performance remains robust. This suggests the method is well-suited for real-world scenarios where labels may be noisy or automatically generated.

Precision-Recall curves showing the robustness of the JSD framework to increasing levels of label noise.

Computational Efficiency

The HALF method achieved coding times of approximately $1.0 \times 10^{-7}$ seconds, representing a 100x to 400x speedup over projection-based methods like KSH. While slightly less precise than the most complex models, the speed-to-accuracy trade-off is highly favorable for mobile deployment.

Conclusion

By grounding binary hashing in the statistical framework of Jensen-Shannon Divergence, this work provides both theoretical guarantees and practical performance improvements. The introduction of HALF further extends the utility of hashing to resource-constrained environments, offering a powerful tool for large-scale, real-time image retrieval.

Summary updated

Abstract

This paper proposes to learn binary hash codes within a statistical learning framework, in which an upper bound of the probability of Bayes decision errors is derived for different forms of hash functions and a rigorous proof of the convergence of the upper bound is presented. Consequently, minimizing such an upper bound leads to consistent performance improvements of existing hash code learning algorithms, regardless of whether original algorithms are unsupervised or supervised. This paper also illustrates a fast hash coding method that exploits simple binary tests to achieve orders of magnitude improvement in coding speed as compared to projection based methods.
BibTeX
@inproceedings{fan2013supervised,
  author = {Lixin Fan},
  title = {{Supervised Binary Hash Code Learning with Jensen Shannon Divergence}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {2013},
  url = {https://openreview.net/forum?id=SkWdsbGdbS},
}
Figure