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.
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.
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