Supervised Short-Length Hashing

1 Introduction

With the exponential growth of data, the approximate nearest neighbor (ANN) search in which the ANNs of a query sample are determined within a large database has become vital in many applications, including web image and video retrieval [Li et al., 2015] [Hao et al., 2017]. Hashing provides high efficiency with respect to both storage cost and query speed, and has received significant attention in information retrieval. Hashing encodes media data into a string of complex binary codes, while preserving the similarity of the original media data. The distance in binary codes is calculated using the Hamming distance, which can be implemented on hardware using bit-wise XOR operations, and provides highly efficient computation, compared to the other distance calculations [Wang et al., 2018].

∗Corresponding Author.

†Corresponding Author.

Learning-based hashing, which aims at generating binary hash codes by learning the projections under the guidance of the original data, is one of the extensively-used hashing methods that can provide superior retrieval performance by analyzing the underlying data characteristics. The existing learning-based hashing methods can be roughly divided into two main categories: unsupervised and supervised. Unsupervised hashing does not use label information for the training samples, while supervised hashing methods make full use of the class labels. In general, supervised hashing can perform significantly better than the unsupervised. Therefore, many supervised hashing methods [Shen et al., 2015], [Gui et al., 2018], [Gui et al., 2018], [Luo et al., 2018a], [Lin et al., 2019] been proposed in recent years.

Compactness, which implies that the obtained hash code should be compact and as short as possible, is a crucial factor in learning-based hashing. In general, given a dataset with c categories, the length, L, of the hash code should be greater than log2(c); else, the hash codes cannot distinguish the samples. Therefore, in this study, we define short-length as the length, which is slightly greater than log2(c). For example, for dataset, CIFAR-10, which has 10 categories, log2(10)=3.3, and a length of four can be considered as a short length. Generally, when the hash-code length is smaller than the number of categories, c (note that it is always considerably greater than log2(c)), or even smaller than the feature representation dimension, the performances of the existing hashing methods degrade significantly. Therefore, the length of the hash codes learned by the existing methods is always considerably greater than the number of categories c (e.g. 48, 64, or 128).

Short-length hash codes can reduce the storage cost and computation complexity, and accelerate the retrieval speed [Luo et al., 2018b]. However, retrieval with short-length hash codes usually leads to unexpected poor performance due to the following: 1) Weak classification: Classification ability is important in information retrieval, and hash codes with shorter length lead to weaker classification ability. Therefore, enhancing the classification ability is vital for short-length hashing. 2) Severe information loss: Due to considerable dimension reduction, representing a sample using a shortlength hash code leads to severe information loss. 3) Easy to achieve suboptimal solution: Trivial solutions are generally easier suboptimal solutions during short-length hash learning, particularly, when the hash code length, L, is considerably smaller than the number of categories, c.

In order to address the aforementioned issues, we propose a novel discrete hashing method, termed supervised short-length hashing (SSLH). In the proposed SSLH, a robust estimator is presented with label information to enhance the classification ability, and mutual reconstruction between the hash codes and original features is performed for reducing information loss. In addition, to avoid suboptimal solutions, the balance constraint and regularization are utilized during hash learning.

The SSLH significantly surpasses the existing hashing methods with short-length hash codes. In addition, considerable improvement in performance is achieved with long-length hash codes. To the best of our knowledge, the SSLH is the first linear-model hashing that focuses on both long- and shortlength hash codes for maintaining high precision. The main contributions of this study are summarized as follows:

• We propose a new supervised discrete hashing method for short-length hash learning. In the proposed method, to achieve better performance, robust and mutual regression, matrix factorization, discrete optimization, and balance constraint are seamlessly combined for short-length hash learning.
• Stable and high-precision for both short- and long-length hash codes are achieved using the proposed method. Experiments based on four large-scale datasets demonstrate that the proposed method can significantly improve the performance with short-length hash codes, while considerably improving the performance with the long-length ones, under various scenarios.

2 ProposedMethod

2.1 Formulation

Assume that we have a training set, X, consisting of n instances; i.e., X = {xi}ni=1 , each instance can be represented by an m-dimensional feature. Moreover, a semantic label matrix, Y = {yi}ni=1 , is available, with yi = {yij} ∈ {-1,+1}c being the label vector of the i-th instance, where c is the number of categories in the training set. If the i-th instance belongs to the j-th semantic category, yij = 1, and -1 otherwise. The hash matrix is defined as H = {hi}ni=1 .

||H|| and HT denote the ℓ2-norm and transpose of matrix, H, respectively.

To utilize the label information effectively, least squares regression is widely adopted in the existing hashing methods. However, the ordinary least squares regression might be sensitive to outliers [Lawson and Hanson, 1995], [He et al., 2012], [Gui and Li, 2018]. Therefore, in this study, we adopt the concept of "correntropy" [Liu et al., 2007] to enhance the classification ability with a robust estimator. Given a hash matrix, H, and label matrix, Y, a linear projection, W, is defined for describing the relationship between them. Then, the robust estimator can be formulated as follows:

where Tr(·) is the trace of "·", E = Y -WT H, D is a diagonal matrix of size n × n and the i-th diagonal element is defined as

δ is a hyperparameter, which will be set empirically, and (YWT H)i is the i-th column of (Y-WT H).

Moreover, the kernel trick is adopted to deal with the loss of feature information. The kernel trick can capture the local structure of the data and reduce the feature dimension with nonlinear projections. Given a training set, X, a radial basis function is used to map an m-dimension feature to ddimension features. Specifically, we first randomly select d anchor points, {pi}di=1 , from the training set, and each training sample can be transformed into a new representation through

where {pi}di=1 . This process can be calculated in advance; we use V to represent ϕ(X) in the following sections for conciseness.

According to the matrix factorization theory [Deerwester et al., 1990], the latent semantic feature from source datasets can be learned by matrix factorization. As the hash matrix, H, is a semantic representation of the samples, it can be considered as the latent semantic feature of the data. We then have the following equation, according to the matrix factorization theory:

where U is a projection. For out-of-sample extension, we need to learn a projection, P, from the original feature to the hash code, which is

Obviously, Eqs. (4) and (5) can be considered as mutual reconstructions between the original feature and the hash matrix. Therefore, minimizing the reconstruction loss will reduce information loss in short-length hash learning. Then, this problem can be formulated as follows:

where α and β are parameters. Compared to the existing hashing methods that only use one type of reconstruction, the proposed method can preserve more information.

Furthermore, according to the balance property of hash codes, each hash bit has a 50% chance of being -1 or +1 in a hash vector [Shen et al., 2017] [Jiang and Li, 2017]. In this study, the balance property can be formulated as

where 1 is a all-ones vector. Balance constraint can avoid trivial solutions. In addition, the utilization of projection, U, can avoid trivial solutions because trivial solutions for H cannot reconstruct the feature well and will render the loss considerable.

In order to obtain a smooth solution, prevent over-fitting, and improve the stability of linear regression [Hoerl and Kennard, 1970], the ℓ2-norm regularization is adopted in this study. The regularization for W, P, and U can be formulated as

where λ is a hyperparameter.

Finally, the SSLH is formulated as

where α , β, and γ are parameters.

2.2 Optimization

It is challenging to optimize Eq. (9) directly because it is nonconvex and noncontinuous. However, we try to solve this nondifferentiable problem with an iterative framework using the following steps .

W-Step: Learn the projection, W, with the other variables fixed. The problem in Eq. (9) becomes

Setting the derivative of Eq. (10) with respect toWas zero yields

H-Step: Learn the binary code, H, with the other variables fixed. The problem in Eq. (9) becomes

Eq. (12) can be reformulated as

As ‖H‖2 = L ∗ n, Eq. (13) can be rewritten as

Although Eq. (14) is difficult to solve because H is discrete, we can directly leverage the discrete cyclic coordinate descent (DCC) approach [Shen et al., 2015] to learn H bit-by-bit iteratively, until convergence or a fixed number of iterations.

Algorithm 1 Supervised Short-Length Hashing (SSLH)

• Input: Training set: X; semantic label: Y; code length: L; hyperparameters: δ, d, α, β, γ, and λ; number of iterations: T.
• 1: InitializeW, P, andUas random zero-centered matrices, and H as a random {-1, 1}L×n matrix. Calculate V using the kernel function according to Eq. (3).
• 2: repeat
• 3: W-Step Use Eq. (11) to solve W, while the other variables are fixed.
• 4: H-Step Use Eq. (16) to solve H bit-by-bit, while the other variables are fixed.
• 5: P-Step Use Eq. (18) to solve P, while the other variables are fixed.
• 6: U-Step Use Eq. (20) to solve U, while the other variables are fixed.
• 7: D-Step Use Eq. (2) to solve D, while the other variables are fixed.
• 8: until Convergence or a fixed number of iterations.

Output: Hash matrix: H; projection matrix: P.

Specifically, define hT as the l-th row of matrix, H, l = 1, · · · ,L, and H′ as matrix, H, excluding h. Analogously, define qT as the l-th row of matrix, Q. Next, define wT as the l-th row of matrix, W, and W′ as matrix, W, excluding w. Then, define uT as the l-th row of matrix, U, and U′ as matrix, U, excluding u. The problem in Eq. (14) becomes

The analytic solution of h can be expressed as

h = sgn(q-wW′ T H′ DT -βuU′ T H′ -γ1T H′ ), (16) where sgn(·) is a sign function.

P-Step: Learn the projection matrix, P, while holding the other variables fixed. The problem in Eq. (9) becomes

The closed-form solution of P is

U-Step: Learn the projection matrix, U, while holding the other variables fixed. The problem in Eq. (9) becomes

The closed-form solution of U is

D-Step: D can be solved as Eq. (2).

In summary, we try to solve the nonconvex mixed integer optimization problem using above steps . Convergence is reached within a few iterations, which is demonstrated in the "Experimental" section. The algorithm for solving the SSLH is presented as Algorithm 1.

2.3 Time Complexity

The time complexity for learning projection, W, is T · O(2nL2 + ncL), whereas the time complexities for learning projections P and U are T · O(2nd2 + ndL) and T · O(2nL2 + ndL), respectively. The time complexity for learning hash code, H, is T ·O(ndL2 +ncL2 ). As d is considerably greater than c and L, the total training time complexity of the proposed method can be simplified as T ·O(ndL2 ). The time complexity is linearly related to the size of the dataset, making the proposed method scalable to larger datasets.

3 Experiments

In this section, we present the experimental settings and results. The hyperparameter settings employed are listed below. Extensive experiments were conducted on four image datasets to evaluate the proposed method and compare it with several state-of-the-art methods. The experiments were performed on a computer with an Intel(R) Core(TM) i7-4790 CPU and 32-GB RAM.

3.1 Datasets and Experimental Settings

Four extensively-used image datasets were utilized in the experiments: CIFAR-10 1 [Krizhevsky and Hinton, 2009], CALTECH-101 2 [Fei-Fei et al., 2007], MS-COCO 3 [Lin et al., 2014], and NUS-WIDE 4 [Chua et al., 2009].

1 https://www.cs.toronto.edu/∼kriz/cifar.html.

2 http://www.vision.caltech.edu/Image Datasets/Caltech101/.

3 http://cocodataset.org/.

CIFAR-10 is a single-label dataset containing 60,000 images belonging to 10 classes, with 6,000 images per class. We randomly selected 5,000 and 1,000 images (100 images per class) from the dataset as the training and testing sets, respectively.

CALTECH-101 is a single-label dataset including 8,677 images belonging to 101 categories, with 40 to 800 images per category. We randomly selected 5,000 and 1,000 images from the dataset as the training and testing sets, respectively.

The MS-COCO dataset is a multilabel dataset containing 82,783 images belonging to 91 categories. For the training image set, images with no category information were discarded and 82,081 remained. We randomly selected 10,000 and 5,000 images from the dataset as the training and testing sets, respectively.

The NUS-WIDE dataset contains 269,648 web images associated with 1,000 tags. In this multilabel dataset, each image may be annotated with multiple labels. We selected only 195,834 images belonging to the 21 most frequent concepts. We randomly selected 10,500 (500 from each concept) and 2,100 (100 from each concept) images from the dataset as the training and testing sets, respectively. For multi-label datasets, two images were defined as a similar pair, if they shared at least one common label.

For the CIFAR-10, MS-COCO, and NUS-WIDE, we used CNN-F model [Chatfield et al., 2014] to perform feature learning. For the CALTECH-101, each image was represented as a 512-dimension GIST feature. We performed ten runs of our method and averaged the performances, for comparison. As the experimental parameters, we empirically set α = β = γ = λ = 10-4 and δ = 2.

4 http://lms.comp.nus.edu.sg/research/NUS-WIDE.htm.

3.2 EvaluationMetric

To evaluate the proposed method, we used an evaluation metric called mean average precision (mAP). mAP includes the mean of the average precision (AP) values obtained for the top retrieved samples. The AP is defined as

where Z is the number of relevant instances in the retrieved K samples. σ(r)=1, if the r-th instance is relevant to the query and σ(r)=0, otherwise. Precision(r) is the precision score for r samples; the precision score is defined as

where N(·) is the number of the specific type. TP represents a true positive, whereas FP represents a false positive. In addition, Precision@n considers only the most relevant retrieved n samples.

Then, the mAP is defined as follows:

where M is the number of query samples and AP(i) is the average precision of the i-th instance.

3.3 Experimental Results and Analysis

We compared the proposed SSLH with the following methods: locality-sensitive hashing (LSH) [Indyk and Motwani, 1998], spectral hashing (SH) [Weiss et al., 2009], principle component analysis (PCA)-iterative quantization (PCA-ITQ)[Gong and Lazebnik, 2011], PCA-random rotation (PCA-RR) [Gong and Lazebnik, 2011], collective matrix factorization hashing (MFH) [Ding et al., 2014], supervised discrete hashing (SDH) [Shen et al., 2015], column sampling based discrete supervised hashing (COSDISH) [Kang et al., 2016], fast supervised discrete hashing (FSDH) [Gui et al., 2018], and scalable supervised discrete hashing (SSDH) [Luo et al., 2018a]. LSH is a data-independent method. SH, PCA-ITQ, PCA-RR and MFH are unsupervised hashing methods, whereas SDH, COSDISH, FSDH, and SSDH are supervised ones. Only nondeep methods were considered for comparison because the proposed method is a linear-model-based method.

All the hyperparameters were initialized as suggested in the original methods. In the experiments, the short length, L, was slightly greater than the log2(c) value that was approximately 3.3, 6.7, 6.5, and 4.4 in the four datasets, respectively. We approximately set the short-length not greater than 10. In addition, the performances of long-length (e.g. 32 and 48) hash codes was also demonstrated in the experiments.

Table 1 lists the mAP values for each method, for singlelabel datasets, CIFAR-10 and CALTECH-101. The mAP performance of the SSLH was considerably better than those of the other methods for these two benchmark datasets, with short-length hash codes. Specifically, the SSLH exhibited more than 80% improvement with an extremely short-length hash code (4-bit in CIFAR-10). In addition, the proposed SSLH demonstrated considerable improvement with longlength hash codes.

In the CALTECH-101 dataset, whose training set is limited and the number of categories is large, most of the previous methods exhibited weak precision due to the controlled experimental setting. However, the proposed SSLH showed significant improvement for CALTECH-101 with short-length as well as long-length hash codes.

Table 2 depicts the mAP value for each method, for multilabel datasets, MS-COCO and NUS-WIDE. The proposed SSLH method outperformed the other methods for these two benchmark datasets. It demonstrated significant improvement with short-length hash codes, and considerable improvement with the long-length ones.

Substantial improvement can also be seen in Figure 1, in terms of the precision score, where the comparison between the proposed SSLH and the existing methods are depicted for different hash lengths. The SSLH exhibited considerably better performance, when the hash code length was shorter. With the increase in length, the improvement reduced, indicating that the proposed SSLH has a distinct advantage with short-length hash codes.

In order to verify the stability of the proposed method, we conducted experiments with different parameter settings. Figure 2 shows the precision score of the SSLH, when α and β ranged from 10-i (i is the number on the coordinate axis); the SSLH method exhibited satisfactory stability and sensitivity with short-length hash codes, and distinguished stability and sensitivity with the long-length ones.

Figure 3 depicts the changes in the objective values achieved by the SSLH for four datasets, where CIF, CAL, MSC, and NUS represent CIFAR-10, CALTECH-101, MS-COCO, and NUS-WIDE, respectively. S and L indicate hash codes with lengths of 8 and 128, respectively. As the number of iterations increased, the objective values become small and stable, indicating that the SSLH appeared to reach convergence rapidly during training, thereby considerably reducing the time required for training.

4 Conclusion

In this study, we proposed a method called supervised shortlength hashing (SSLH), wherein the semantic label information was leveraged by robust regression, while the information loss was restrained by mutual reconstruction. The proposed method achieved more stable and precise performances for short-length hash codes, while satisfactorily performing for long-length hash codes. Experiments conducted on four benchmark datasets indicated that the proposed method exhibits superior performance, compared to the other existing methods. In future, we will attempt to extend the proposed framework to nonlinear-based models.

Acknowledgments

This work is supported by the National Natural Science Foundation of China (61876098, 61671274, 61573219), China Postdoctoral Science Foundation (2016M592190), Shandong Provincial Key Research and Development Plan (2017CXGC1504), Special funds for distinguished professors of Shandong Jianzhu University and the Fostering Project of Dominant Discipline and Talent Team of Shandong Province Higher Education Institutions.