Source-linked AI summary
Fast Supervised Discrete Hashing
Jie Gui, Tongliang Liu, Zhenan Sun, Dacheng Tao, Tieniu Tan
TL;DR
FSDH addresses the inefficiency of discrete optimization in supervised hashing and the performance loss from relaxing binary constraints. It reverses the usual regression direction to obtain a faster hashing method, which generally outperforms SDH and other comparative methods.
Problem
Relaxing binary hash-code constraints simplifies optimization but can produce suboptimal codes, while SDH’s iterative discrete optimization is time-consuming.
Method
FSDH regresses class labels to corresponding hash codes and uses a closed-form hash-learning solution within the supervised discrete hashing framework.
Results
FSDH is efficient and generally outperforms comparative methods; on CIFAR-10 with 128 bits, it is about 12-times faster than SDH.
Takeaways & Limitations
FSDH provides a fast supervised discrete hashing alternative that improves overall performance compared with SDH across image classification and face recognition experiments.
Takeaways & Limitations
Combining FSDH with deep learning as the nonlinear embedding technique slows the original method, and effective integration remains under investigation.
Abstract
from arXiv · showhide
Learning-based hashing algorithms are ``hot topics" because they can greatly increase the scale at which existing methods operate. In this paper, we propose a new learning-based hashing method called ``fast supervised discrete hashing" (FSDH) based on ``supervised discrete hashing" (SDH). Regressing the training examples (or hash code) to the corresponding class labels is widely used in ordinary least squares regression. Rather than adopting this method, FSDH uses a very simple yet effective regression of the class labels of training examples to the corresponding hash code to accelerate the algorithm. To the best of our knowledge, this strategy has not previously been used for hashing. Traditional SDH decomposes the optimization into three sub-problems, with the most critical sub-problem - discrete optimization for binary hash codes - solved using iterative discrete cyclic coordinate descent (DCC), which is time-consuming. However, FSDH has a closed-form solution and only requires a single rather than iterative hash code-solving step, which is highly efficient. Furthermore, FSDH is usually faster than SDH for solving the projection matrix for least squares regression, making FSDH generally faster than SDH. For example, our results show that FSDH is about 12-times faster than SDH when the number of hashing bits is 128 on the CIFAR-10 data base, and FSDH is about 151-times faster than FastHash when the number of hashing bits is 64 on the MNIST data-base. Our experimental results show that FSDH is not only fast, but also outperforms other comparative methods.
1 INTRODUCTION
Large-scale visual search has driven interest in learning-based hashing, which maps examples to binary codes intended to preserve similarities. FSDH addresses the computational cost of discrete supervised hashing with a closed-form, single-step hash-code solution and is generally faster than SDH while typically performing better.
- Learning-based hashing maps examples to binary feature vectors designed to preserve structure such as similarities in the original space.
- Discrete constraints make hash-learning optimization mixed-integer and generally NP-hard, motivating relaxed optimization followed by quantization.The relaxation simplifies optimization but can produce suboptimal codes because of accumulated quantization error, especially for long hash codes.
- FSDH regresses class labels to corresponding hash codes rather than using ordinary least-squares regression from hash codes to labels.The paper presents this regression direction as a new strategy for hashing intended to improve SDH's performance and speed.
- FSDH solves hash-code learning with a closed-form solution requiring one step, replacing SDH's iterative discrete cyclic coordinate descent.FSDH is also usually faster than SDH when solving the projection matrix for least-squares regression.
- FSDH remains non-convex and therefore reaches only local minima, despite generally accelerating and outperforming SDH.
2 OUR PROPOSED METHOD
FSDH replaces SDH’s regression direction while retaining its three-step alternating optimization, yielding a closed-form hash-code update and lower projection-matrix complexity. The method also preserves within-class and between-class code properties and is analyzed for stability.
- Implementation: The method uses Gaussian-kernel features from randomly selected training examples, with projection matrix P mapping those features into a low-dimensional space.The feature map is m-dimensional, and P projects φ(x) into the l-bit code space.
- FSDH formulation: FSDH regresses class labels to corresponding hash codes, reversing SDH’s first regression term while retaining the same three-step optimization structure.SDH regresses B to Y, whereas FSDH regresses Y to B; both optimize W, P, and B through alternating updates.
- Code properties: The first regression term and the nonlinear embedding jointly produce similar within-class and between-class binary-code properties, allowing the regression term to be replaced.The first term contributes between-class differences, while the third term contributes differences among all examples, including within classes.
- FSDH formulation: FSDH learns binary codes in one closed-form B-step, unlike SDH’s iterative discrete cyclic coordinate descent that updates codes bit by bit.The single FSDH hash-code-solving step is identified as the source of its faster discrete optimization.
- Theoretical analysis: FSDH’s W-learning step is stable under the stated bounded-loss assumption, and stability implies differences between learned parameters and codes decrease as sample size increases.The analysis attributes W-step stability to ℓ2 regularization and contrasts SDH’s lack of stability when learning B.
3 EXPERIMENTS
Experiments on CIFAR-10, MNIST, and FRGC evaluate FSDH against representative hashing methods across retrieval quality, accuracy, and runtime. FSDH generally combines strong retrieval performance with substantially faster training, although other methods lead on some metrics and settings.
- Experimental setup: Experiments compare FSDH with BRE, SSH, KSH, FastHash, AGH, IMH, CCA-ITQ, and PCA-ITQ across three image datasets.Evaluation uses Hamming ranking, hash lookup, accuracy, training time, and test time.
- CIFAR-10: On CIFAR-10, FSDH outperforms the other methods in accuracy and precision at 500 retrieved examples, and exceeds them on Hamming-radius-2 precision above 32 bits.At 16 bits, KSH performs best for Hamming-radius-2 precision.
- CIFAR-10: 32.8 seconds versus 406.4 seconds: FSDH is about 12-times faster than SDH for 128-bit CIFAR-10 training.FastHash takes 1183.3 seconds in the same setting, making FSDH about 36-times faster than FastHash.
- MNIST: On MNIST, FSDH performs best for recall and F-measure, while SDH leads precision and FastHash leads MAP and accuracy.FSDH still outperforms all other methods across the reported metric curves, and trains about 151-times faster than FastHash.
- FRGC: On FRGC, FSDH leads precision, recall, and F-measure, while SDH leads MAP and precision and CCA-ITQ leads accuracy.FSDH performs best at 64 hashing bits for MAP; KSH leads when the number of bits is at least 128.
4 CONCLUSION
FSDH is presented as an efficient and effective data-dependent hashing method based on SDH, with applications to large-scale visual tasks and an unresolved efficiency challenge for deep-learning integration.
- FSDH regresses class labels to corresponding hash codes, improving speed and overall performance compared with SDH.The paper presents this regression direction as the basis of FSDH.
- FSDH can compress high-dimensional features into short binary codes for large-scale visual tasks such as ImageNet image classification.The paper identifies this as an application that could significantly speed up those tasks.
- Embedding deep learning within the SDH framework slows the original method, motivating investigation of more effective and efficient combinations.The authors state that combining deep learning with SDH remains under investigation.