Rescuing Deep Hashing from Dead Bits Problem

1 Introduction

Hashing has been widely used in image retrieval [Cao et al., 2017; Jiang and Li, 2018; Wu et al., 2019; Zhao et al., 2020; Wu et al., 2018; Zhang et al., 2020], video retrieval [Yuan et al., 2020], and cross-modal retrieval [Jiang and Li, 2017] due to its high computation efficiency and low storage cost. Traditional hashing methods are based on hand-crafted features. The representative methods include LSH [Gionis et al., 1999], ITQ [Gong et al., 2012] and SDH [Shen et al., 2015].

In recent years, deep hashing methods have greatly improved the retrieval performance due to their powerful representation ability. Large number of deep hashing methods have been proposed, including single-label hashing methods [Gui et al., 2017; Zhao et al., 2020; Li et al., 2020] and multi-label hashing methods [Zhao et al., 2015; Lai et al.,

∗Corresponding author

2016; Wu et al., 2017]. However, for all these deep hashing methods, the optimization is an intractable problem because of the discrete property of the binary hash codes.

Previous methods usually adopt binary approximation to tackle the above problem. A common strategy in these methods is to adopt an activation function, e.g. sigmoid(·) or tanh(·), and minimize a quantization loss to approximate the discrete values. However, this paradigm may make more and more wrong hash bits stuck into the saturated area of the activation functions, and these wrong hash bits will never escape (as shown in Figure 1). We call this problem "Dead Bits Problem (DBP)". Besides, we call the wrong bits (red bar) stuck in the saturated area as "Dead Bits", because the gradients are nearly zero. What's more, the number of dead bits will increase with the training epoch. This is because different bits have different change trends, i.e. uncertainty [Fu et al., 2020]. As a result, the direction of optimization of each hash bit is oscillatory. Some bits may "incautiously" fall into the saturated area and hard to escape.

Moreover, the quantization loss widely used in hashing methods will also aggravate DBP, such as L2 quantization loss [Li et al., 2015] or log cosh quantization loss [Zhu et al., 2016]. These quantization loss functions drag bits into -1 or +1 simply according to their current sign, which may conflict with the similarity preserving requirement. For example, if the hash bits of two similar images fall into different sides of zero, the quantization loss will push them apart, while the similarity preserving loss will pull them together.

To address these issues, we propose a simple but effective deep hashing component named Gradient Amplifier which can detect and rescue dead bits by amplifying their gradients. Moreover, we devise an error-aware quantization loss function. For correct bits, it adaptively reduce their quantization loss to generate high-quality hash codes. For dead bits, they are propagated to the similarity preserving loss. This will avoid the negative effect brought by the original quantization loss.

The main contributions of this work can be summarized as follows:

• To the best of our knowledge, we are the first to formalize the "Dead bits Problem": the saturated area of activation function and existing quantization loss will "kill" more and more hash bits.
• We propose a gradient amplifier which detects the dead bits and amplifies their gradients to rescue them. Furthermore, we design an error-aware quantization loss, which will further alleviate the DBP. The proposed gradient amplifier and error-aware quantization loss can be compatible with a various of deep hashing methods.
• Extensive experiments on three datasets demonstrate the efficiency of the proposed gradient amplifier and the error-aware quantization loss.

2 RelatedWork

Learning to hash aims to project data from high-dimensional space into low-dimensional Hamming space and can be categorized into traditional hashing methods and deep hashing methods.

Traditional hashing methods leverage hand-crafted features to learn hash function. LSH [Gionis et al., 1999] generates a random projection matrix to map the features into hash codes. ITQ [Gong et al., 2012] uses PCA to perform dimension reduction. SDH [Shen et al., 2015] adopts discrete cyclic coordinate descent (DCC) to optimize hash codes directly.

Deep hashing methods involve CNN models into the learning of hash codes. CNNH [Xia et al., 2014] is a twostage hashing method that utilizes CNN model to generate hash codes. DNNH [Lai et al., 2015] is the first end-to-end deep hashing method that learns features and hash codes simultaneously. DPSH [Li et al., 2015] leverages pairwise supervised information to learn hash function. And DSDH [Li et al., 2020] introduces classification information into the training process and optimizes database codes by DCC [Shen et al., 2015]. Recently, asymmetric architecture of deep hashing has shown great potential to improve the retrieval performance. DAPH [Shen et al., 2017] adopts two different CNN model to learn a hash function simultaneously. ADSH [Jiang and Li, 2018] utilizes a CNN for query images, while the database codes are learned directly by DCC. DIHN [Wu et al., 2019] aims to learn a hash function incrementally. CCDH [Zhao et al., 2020] leverages variational autoencoder to update the CNN model and database codes efficiently.

For all the deep hashing methods, the optimization for binary hash codes is remain an intractable problem. To approximate the non-differentiable sign(·) function, tanh(·) and quantization loss are introduced and widely used in hashing methods [Zhu et al., 2016; Cao et al., 2017; Wu et al., 2019; Zhao et al., 2020]. However, few research focuses at the problem leading by the saturated area of activation function and the quantization loss in pairwise learning. They will push bits toward wrong direction and can not escape from the saturated area.

3 Preliminaries: Deep HashingModels

Assume we have N training images denoted as X = {xi}Ni=1 , and an N × N similarity matrix S, where Sij = 1 if xi and xj have same label and otherwise Sij = 0. Deep hashing model aims to learn a hash function F(x; θ), mapping an input image x into a K-dimension embedding, where θ is the parameters of the model. Subsequently, we apply sign(·) function to the embeddings for obtaining binary hash codes B = {bi}Ni=1 ∈ {-1,+1}N×K . However, because the gradient of sign(·) function is always 0 expects x = 0, we can not back-propagate it directly. To address this issue, a common strategy in these methods is to adopt sigmoid(·) or tanh(·) function and minimize a quantization loss, i.e. L2 quantization loss, to approximate it. Without loss of generality, we utilize the tanh(·) to illustrate our approach. In the next sections, we firstly characterize a common and serious problem in these saturated functions and quantization losses, then propose a simple but effective method to solve it.

4 Dead Bits Problem

To study DBP, we firstly investigate the gradient of hash loss functions. Without loss of generality, here we choose a representative hash loss, which is formulated as:

where hi ∈ [-1, 1]K is the relaxed continuous codes, Θij = hTi hj 2 , η is the hyper-parameter to control the balance between similarity loss (first term) and quantization loss (second term). This form of hash loss is widely used in hash methods [Li et al., 2015; Zhu et al., 2016; Cao et al., 2017; Chen et al., 2019; Li et al., 2020].

Next, we calculate the derivative of Eq. (1) w.r.t. Fk (xi; θ), where k is the k-th dimension of embedding.

where hki = tanh(Fk (xi; θ)) is the k-th bit of hi, σ(x) = 1 1+e-x is the sigmoid function. The first term in Eq. (2) is the derivate of hash loss and the second is the derivate of tanh(·).

4.1 Why does DBP Appear?

For simplicity, assume we have a pair of hash codes with one bit, hj = 0.9, Sij = 1, η = 1, and we visualize Eq. (2) w.r.t. hi, which is illustrated in Figure 3. The x-axis is divided into 4 areas. In area 1© (the left of green dashed line), the absolute value of gradient should be large because hki is far away from hkj now. However, due to the second term in Eq. (2), the saturated portion of tanh(·) will suppress the gradient, especially when hki is close to -1. Consequently, these bits can not be optimized. To minimize the loss, network tends to change others bits, which may lead to training instability. In area 2© (between green and yellow dashed line), the gradient seems to be decreased. This is because the quantization loss (the second term in Eq. (1)) can not leverage the supervised information and only pushes the bit to +1 or -1 (depends on which side of axis it is on). When the bit is close to 0 from the left side, the punishment of quantization loss will get intense and prevent it from crossing 0 point. If η is large, it may push the bit toward wrong direction, and the network can not be optimized correctly (orange line). In area 3© (between yellow and red dashed line), there is a cliff around 0. The reason is quantization loss changes the direction of punishment around zero point. If hki approaches 0 from the left side, the quantization loss will push it toward -1. Once it crosses zero point, the quantization pushed it toward +1 immediately. In area 4© (the right of read dashed line), the gradient is decreasing as the distance between hki and hkj achieves zero.

The core reason leading to DBP is the saturated area in tanh(·). From Eq. (2) and Figure 3, if there is a continuous hash bit hki = +1 or -1, whatever hkj is, the gradient is always 0. Furthermore, there are two reasons that may aggravate the problem. First, in Eq. (2), the first term in braces shows the gradient of Fk (xi; θ) is depended on the sum of the relations between hki and hkj . Limited by the noise in data and the capacity of CNN model, some bits may be optimized incorrectly. Once they get stuck in the saturated area, they can not escape from it. The other problem may aggravate DBP is the quantization loss. Existing quantization losses, e.g., L2 quantization loss [Li et al., 2015], log cosh quantization loss [Zhu et al., 2016], do not leverage the similarity information. They just push bit to -1 or +1 (depend on which side of axis it is on). If the parameter of quantization loss is selected improperly (Figure 3, orange line), it may push the bit toward wrong direction and lead to DBP. Furthermore, these dead bits will disturb the optimization process of others bits due to Eq. (2), and lead to sub-optimal retrieval performance.

5 Rescuing Deep Hashing

To address DBP, we propose Rescuing Deep Hashing (RDH), which consists of two components: Gradient Amplifier and Error-Aware Quantization Loss, as illustrated in Figure 2.

Gradient amplifier aims to amplify the gradient of dead bits in saturated area. Its formulation is as following:

where GA(·) is the gradient amplifier, gk i is the gradient of hki , α = 1 1-τ 2 is the amplification factor and τ ∈ [0, 1) is the threshold to determine whether to amplify gradient.

During the forward-propagation phase, gradient amplifier collects continuous hash codes h. At the back-propagation stage, it fetches gradients from later layers and takes out h. If the direction of the gradient is equal to the bit, it means the bit need to be moved toward the opposite direction. Furthermore, the bit is in the saturated area of tanh(·) if |hki | ≥ τ and it can not escape from the area. Then gradient amplifier will magnify the gradient of it and help it move toward the correct direction.

Error-aware quantization loss is to solve the problem that ordinary quantization loss [Li et al., 2015; Zhu et al., 2016; Li et al., 2020] can not aware the correct direction of hash bits. The formulation is as following:

where δ = sign(hki ) sign(hkj ).

Traditional quantization loss just pushes the continuous bit toward -1, if the bit is on the left of 0; +1 otherwise. It does not leverage the similarity information and may push the bit toward the wrong direction. Error-aware quantization loss chooses bits that satisfy 1). Sij = 1 and sign(hki ) = sign(hkj ); 2). Sij = 0 and sign(hki ) ̸= sign(hkj ). For others bits, we ignore and delegate them to the similarity preserving loss to optimize them, because the number of correct and wrong bits is imbalance and dynamic during training. Optimizing them will introduce extra hyper-parameter and increase the difficulty of tuning.

Due to the flexibility of gradient amplifier and error-aware quantization loss, they can be seamlessly assembled with existing similarity preserving loss in hashing methods [Li et al., 2015; Cao et al., 2017; Chen et al., 2019], we denote these losses as Lsim. Finally, the overall objective function is

The learning algorithm is summarized in Algorithm 1.

6 Experiments

6.1 Datasets

The experiments of RDH are conducted on three widely used datasets: CIFAR-10 [Krizhevsky et al., 2009], MSCOCO [Lin et al., 2014], and NUS-WIDE [Chua et al., 2009].

• CIFAR-10 1 is a single-label dataset, containing 60,000 color images with 32 × 32 resolution, belonging to

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

Algorithm 1 The learning algorithm for RDH

Input: training images X; Similarity matrix S; Threshold τ; Hyper-parameter η

Output: CNN model F(x; θ)

• 1: Initialize a new CNN model and replace the last fully connected layer with a new K-dimension fully connected layer followed by tanh(·) activation function.
• 2: while Not convergence or not reach maximum iterations do
• 3: Forward propagate and get continuous hash codes h.
• 4: Store h for gradient amplification.
• 5: Recognize bits need to be quantified according to Eq. (4).
• 6: Calculate the loss by Eq. (5).
• 7: Backward propagate to obtain the derivate ∂L/∂hki .
• 8: Recognize dead bits according to Eq. (3).
• 9: Amplify gradients through Gradient Amplifier according to Eq. (3).
• 10: Update model parameters θ.
• 11: end while
• 12: return CNNmodel F(x; θ)

10 classes. Each class has 6,000 images. Following [Li et al., 2015; Wu et al., 2019; Zhao et al., 2020; Li et al., 2020], we randomly sample 1,000 images (100 images per class) as the query set, and the rest are used to form the gallery set. Then we randomly select 5,000 images (500 images per class) from the gallery as the training set.

• MS-COCO 2 is a multi-label dataset. It contains 82,783 training images and 40,504 validation images, which belong to 80 classes. We obtain 12,2218 images by combining the training and validation images and pruning images without category annotation. Following [Cao et al., 2017; Jiang and Li, 2018], we randomly sample 5,000 images as the query set, and the rest images are used as the gallery. Furthermore, we random select 10,000 images from the gallery as the training points.
• NUS-WIDE 3 is a multi-label dataset, which contains 269,648 images from 81 classes. Following [Lai et al., 2015; Jiang and Li, 2018; Zhao et al., 2020], we use a subset of original dataset which associates with the 21 most frequent classes to conduct our experiment. Specially, we randomly select 2,100 images (100 images per class) as the query set. From the rest images, we randomly choose 10,500 images (500 images per class) to make up the training set.

6.2 EvaluationMethodology

Following [Li et al., 2015; Wu et al., 2019; Zhao et al., 2020; Li et al., 2020], we adopt the Mean Average Precision (MAP) and Precision-Recall (PR) curves to evaluate the retrieval performance. Particularly, for MS-COCO and NUS-WIDE, the MAP is calculated based on the Top-5K returned samples. For multi-label dataset, e.g. MS-COCO, two images are considered to be similar if they share at least one common label. All experiments are conducted 5 times, and we report the average results of them.

2 https://cocodataset.org/

3 https://lms.comp.nus.edu.sg/wp-content/uploads/2019/research /nuswide/NUS-WIDE.html

6.3 Experimental Details

As a plug-in module, RDH can be adopted with various methods trained with different models and loss functions. We selected some representative deep hashing methods, e.g. DPSH [Li et al., 2015], DHN [Zhu et al., 2016], HashNet [Cao et al., 2017], DAGH [Chen et al., 2019], DSDH [Li et al., 2020] as the baseline methods. All of these methods are implemented on PyTorch [Paszke et al., 2019]. For a fair comparison with other state-of-the-art methods, we retrain all the baseline methods, employing AlexNet [Krizhevsky et al., 2017] pretrained on ImageNet [Deng et al., 2009] as the backbone. The last fully connected layer is removed, and replaced with a new one, where the dimension of the outputs is the hash code length. In RDH, SGD is utilized as the optimizer with 1e-5 weight decay. The initial learning rate is set to 1e-2. Cosine annealing the learning rate scheduler [Loshchilov and Hutter, 2016] is leveraged to gradually reduce learning rate to zero. The batch size is set to 128. We set τ = 0.99. η is set to 1 for CIFAR-10 and 0.1 for the others.

All the experiments are conducted on a single NIVDIA RTX 2080ti GPU.

6.4 Accuracy Comparison

In this section, we compare the performance between with and without RDH on CIFAR-10, MS-COCO and NUSWIDE. Table 1 shows the MAP of different methods with various hash code lengths. "+RDH" represents training model with the gradient amplifier and the error-aware quantization loss.

Figure 4 illustrate the Precision-Recall curves. The results indicates RDH has ability to improve the retrieval performance of the baseline methods and can be used as a plug-andplay component to fit most existing hashing methods. Compared with the baseline methods, RDH outperforms them across all datasets. For example, our proposed method improves the average MAP by 3.29% and 2.33% on CIFAR-10 and MS-COCO respectively. And we can observe the similar results on NUS-WIDE. In addition, on CIFAR-10 dataset, we observe that RDH methods with 24 bits are even better than their baseline methods with 64 bits. It indicates the benefit that dead bits are rescued from the saturated area by our proposed gradient amplifier and error-aware quantization loss have ability to rescue dead bits from the saturated area. Consequently, the retrieval performance is improved significantly.

6.5 Effectiveness of Gradient Amplifier and Error-Aware Quantization Loss

We count the dead bits with/without gradient amplifier and error-aware quantization loss during the training phase. The results are shown in Figure 5.

In Figure 5, blue line represents the results without our proposed gradient amplifier and error-aware quantization, where dead bits are increasing during the training stage and the number of them is kept at a high level. This is mainly because some bits "incautiously" arrive in the saturated area and hard to escape from it. As a result the existence of our proposed 'Dead Bits Problem" can be confirmed.

Nonetheless, with the help of gradient amplifier and erroraware quantization, DBP is mitigated significantly, which is shown by the orange line in Figure 5. Specifically, the number of dead bits is decreased significantly and stays below 200 during the training time. It means many dead bits can escape from the saturated area and have the opportunity to be optimized correctly. Consequently, only few bits get stuck in saturated area mainly due to the noise of dataset or the capacity of CNN model.

6.6 Ablation Study

To analyze the effectiveness of gradient amplifier and erroraware quantization loss, we design some variants of our proposed algorithm, and show some empirical analysis. We compare our algorithm with the following baseline: (1) Without gradients amplifier (w.o. GA). The gradients amplifier is removed in this baseline. (2) Without error-aware quantization loss (w.o. EAQL). We remove the error-aware quantization loss.

Table 2 shows the performance of there variants. We can observe that the retrieval performance drops dramatically when modifying the structure of proposed algorithm. Specifically, when we remove gradient amplifier, dead bits can not be pushed away from saturated area, and the MAP decreases by 2%. When removing error-aware quantization loss, some bits may hard to cross the zero point, leading to the degradation of retrieval performance.

6.7 Sensitivity Analysis

To investigate the sensitivity of the hyper-parameters τ and η, we further conduct experiments under different values of τ and η, the retrieval performance is illustrated in Figure 6. τ is used to control the threshold of range gradients amplifier effects and η is leveraged to balance the trade-off between original loss and EAQ loss.

From Figure 6, we observe that our algorithm is not sensitive to τ. This is mainly because gradient amplifier can amplify gradients of dead bits adaptively according to Eq. (3).

For η, it is not sensitive on multi-label datasets, e.g., MSCOCO and NUS-WIDE. However, on CIFAR-10, the retrieval performance decreases when η is set to a small value. This is mainly because the resolution of images in CIFAR-10 is low and leads to high uncertainty of bits, i.e., the bits will be oscillatory during training time. Large η can help stabilize these bits and improve the retrieval performance.

7 Conclusion

In this paper, we have characterized a serious problem that caused by the saturated area in activation function, e.g. sigmoid(·) or tanh(·) and the traditional quantization loss, called DBP. To address this issue, we have proposed a gradient amplifier to detect and rescue the dead bits. Furthermore, an error-aware quantization loss is proposed to alleviate DBP. Extensive experiments have demonstrated that the proposed method can significantly decrease the number of dead bits and improve the performance of the baseline methods.

Acknowledgements

This work was supported by the National Natural Science Foundation of China under Grants 62006221, the National Key Research and Development Program of China (No. 2018YFC0825102, No.2019YFC0850202).