Instance-weighted Central Similarity for Multi-label Image Retrieval

Deep hashing has been widely applied to large-scale image retrieval by encoding high-dimensional data points into binary codes for efficient retrieval. Compared with pairwise/triplet similarity based hash learning, central similarity based hashing can more efficiently capture the global data distribution. For multi-label image retrieval, however, previous methods only use multiple hash centers with equal weights to generate one centroid as the learning target, which ignores the relationship between the weights of hash centers and the proportion of instance regions in the image. To address the above issue, we propose a two-step alternative optimization approach, Instance-weighted Central Similarity (ICS), to automatically learn the center weight corresponding to a hash code. Firstly, we apply the maximum entropy regularizer to prevent one hash center from dominating the loss function, and compute the center weights via projection gradient descent. Secondly, we update neural network parameters by standard back-propagation with fixed center weights. More importantly, the learned center weights can well reflect the proportion of foreground instances in the image. Our method achieves the state-of-the-art performance on the image retrieval benchmarks, and especially improves the mAP by 1.6%-6.4% on the MS COCO dataset.


Introduction
Representing images efficiently is an important task for large-scale multimedia retrieval. Hashing has attracted extensive attention due to its computational and storage efficiency. It aims to encode high-dimensional data points into compact binary codes, hence the original feature space can be efficiently approximated via low-dimension Hamming space [26,20]. Recently, deep learning to hash methods can perform simultaneous feature learning and hash code learning in an end-to-end way, which has shown state-of-the-art performance on many benchmarks [30,12,33   Use multiple hash centers with the equal weights to generate a centroid as the learning target, which does not consider the relationship between the center weights and the proportion of foreground instances in the image. (c) We propose instance-aware weighting approach to automatically learn the hash center weights by an alternative optimization. As illustrated in sub-figure (c), the center weights corresponding to the three foreground instances (shape, dog and chair) are 0.70, 0.18, and 0.12 respectively, which well reflect their proportion in the image.
The existing data-dependent hashing methods mostly generate similar binary codes for similar data points by utilizing pairwise or triplet data similarity [14,28,2]. Yuan et al. [31] analyzed the limitations of the pairwise/triplet based hashing methods, and proposed the Central Similarity Quantization (CSQ) for image retrieval that not only captures the data similarity globally but also improves the learning efficiency. The existing central similarity methods utilize the row vectors or column vectors of Hadamard matrix to generate hash centers [17,3,15,31]. As shown in Figure 1 (a), a single center is used as the target to learn the hash function for single-label image retrieval. For multilabel image retrieval illustrated in 1 (b), however, Yuan et al. [31] only uses multiple hash centers with equal importance to generate one centroid as the learning target. The central similarity based methods neglect the relationship between the importance of the hash centers and the proportion of foreground objects in the image. In addition, the above methods only consider the semantic similarities at image level, which may be suboptimal for multi-label image retrieval.
The existing multi-label image retrieval methods can be divided into two main categories: one is to use the region proposal module to extract foreground objects and generate multiple hash codes for a multi-lable image [13,8,22]. The other is to consider the number of common labels of multi-label image as the metric of similarity [32,21]. The former methods achieve instance-aware retrie, but their limitation is that the generation of hash codes is dependent on the quality of region proposal module. Therefore, how to make the model automatically learn the multi-scale semantic information contained in the image without using region proposal module?
In this paper, we propose an nstance-weighted Central Similarity (ICS) to learn the relative importance of each hash center corresponding to a hash code as shown in 1 (c). Our method use multiple hash centers to guide the model to focus only on the foreground objects and ignore the background. ICS is a two-step alternative optimization approach. In the first step, we apply the maximum entropy regularizer to prevent one hash center from dominating the loss function, and compute the center weights via projection gradient descent. In the second step, the neural network parameters are updated by standard back-propagation. In addition, the center weights learned by ICS can reflect the proportion of foreground objects in the image, instead of leveraging the region proposal generation model to produce hash codes for foreground objects. The performance of proposed ICS for multi-label image retrieval is evaluated on NUS-WIDE [4] and MS COCO [18] datasets. Our contributions are summarized as follows.
• We first consider the relationship between the importance of hash centers and the proportion of foreground instance regions in the image, and propose the ICS to automatically learn the hash center weights by an alternative optimization.
• The maximum entropy regularizer in ICS leads the distribution of center weights to be more reasonable and the learning process of center weights can converge within few iterations via project gradient descent.
• The proposed ICS is also a instance-aware method that the center weight value can well reflect the proportion of foreground objects in the image. Our visualization results can support this point well.
• Our experimental results demonstrate that the ICS can improve the performance on the three data sets NUS-WIDE, MS COCO and FLICKR25K by 0.4%-1.1%, 1.6%-6.4% and 6.0%-7.6% in mAP, respectively.

Related Work
In this section, we briefly review the related works in terms of deep learning to hash methods, and divide them into two categories according to whether the multi-label information in the image is considered.
The first category is represented by HashNet [2] and CSQ [31]. 1) HashNet [2] considered the imbalanced similarity relationships between positive and negative pairwise samples, and used weighted maximum likelihood objective function to learn hash codes. DCH [1] used Cauchy distribution to improve search performance from a Bayesian perspective. However, the above pairwise/triplet based methods ignore the global structure of samples and suffer from low retrieval efficiency. 2) Recent deep hashing methods [17,16,3,31] based on Hadamard matrix show promising results due to its orthogonal and balanced structure. CSQ [31] leveraged Hadamard matrix to generate hash centers for learning central similarities between samples. HCDH [3] used label information to guide the learning of hash centers. For multi-label images, however, the previous methods ignore the relative importance of each hash center and consider each lable equally in a image. In this paper, we consider the proportion of each foreground object should be different and propose to learn the center weights automatically.
The second category is represented by IAH [13] and RCDH [21]. DSRH [32] and IAH [13] used the region proposal module to generate multiple hash codes for a multilable image. The limitation is that the generation of hash codes is dependent on the quality of region proposal module. RCDH [21] considers the number of common labels of multi-label image as the metric of similarity.

The Proposed Method
In this section, we first introduce how to generate hash centers via Hadamard matrix. Afterwards, maximum entropy regularizer is applied to learn the relative importance of each hash center. Finally, we propose the two-step based optimization approach to update the hash center weights and neural network parameters alternatively.

Problem Definition
Let X be a set of training data, i.e.
where D is the dimension of input, M denotes the number of labels, and y i stands for the label corresponding to the i-th sample. Our goal is to learn a nonlinear hash function f θ : K that encodes each data point x into compact Kbit hash code, where θ denotes the model parameters. At the same time, similarities in the original space are preserved in the Hamming space. Given a set of hash centers and their corresponding weights , where c i represents the number of labels of x i . We aim to automatically learn the hash center weights w. In addition, we hope that the value of w can reflect the proportion of the corresponding foreground objects in the image.

Generation of Hash Centers
Following [31], we define the row vectors in Hadamard matrix as hash centers. Hadamard matrix satisfies the independence and balance principles that its row vectors and column vectors are pair-wise orthogonal, and half of bits are 1 or -1. The generation of 2 k -order Hadamard matrix H is rather simple using the Sylvester's algorithm [25]: where ⊗ represents the Kronecker product. The generation of hash centers is related to the number hash bits K and the number of class labels M , which includes three strategies: 1) When M ≤ K, the row vectors are randomly sampled from H as hash center. 2) is utilized to sample hash centers. 3) When 2K ≥ M and K is not the power of 2, each bit in a hash center v is sampled from a Bernoulli distribution Bern(0.5), which means that random half of bits are 1 or -1.

Instance-weighted Central Similarity
In order to measure the similarity of hash code and its corresponding hash centers {v ij } ci j=1 , Binary Cross Entropy (BCE) is used to measure the Hamming distance d i between the hash code b i and its hash centers v i . The distance function d i = Ω(b i , v i ) can be written as: As illustrated in Figure 1, the proportion of foreground instances in the image is different. Therefore, for the hash centers {v ij } ci j=1 representing different labels, hash code b i should be given different weights according to the distance.
We think the Hamming distance between each hash code b i and its corresponding hash centers {v ij } ci j=1 should be weighted non-uniformly. We introduce weights {w ij } ci j=1 to reflect the weights of hash centers and assume that it is learnable rather than with the same importance. Therefore, we design a weighted central similarity loss: where j = 1, 2, ..., c i represents the number of hash centers corresponding to a hash code. In addition, we regard the probabilities of assigning each hash code to the hash centers as a classification problem. We convert the distance Ω(b i , v i ) based on the adaptive Sigmoid function as follows: where β is a smooth parameter to control its bandwidth. Inspired from HashNet [2], the Sigmoid function with larger β will have larger saturation zone where its gradient is zero. To perform more effective back-propagation, we usually require β ≤ 1 in our experiments. It is easy to see that the smaller Ω(b i , v i ) is, the larger p(Ω(b i , v i )) will be. Therefore, maximizing the likelihood of p(Ω(b i , v i )) will make the Hamming distance between hash centers and hash codes small, which means that the foreground instances with larger proportion in an image, the higher classification probability of the corresponding hash centers.
We define the following likelihood function to learn center weight w: By taking log of p(Ω(b i , v i )), it can be derived as: We redefine the loss function as: We can expand this formula as: However, the direct minimization of above equation with respect to w ij may produce unreasonable hash center weights. This is obvious from the following Lemma 1.
We can obtain a unique minimum solution for Eq. 8 with the weights w ij = 1 if j = argmin 1≤j≤ci d ij and 0 elsewhere. However, the weighted distance function for a multilabel image only minimizes Hamming distance between a hash code and its corresponding one hash center, which obviously makes no sense for multi-label image retrieval. To prevent one hash center from dominating the loss function, we apply the maximum entropy principle to learn the hash center weights.
We can reformulate the loss function as : The above equation has a new parameter λ that is used to control the degree of maximum cross entropy regularization. If λ approaches zeros from positive and w ij approaches 1 ci , then the minimization of above loss function tends to give equal weight to each hash center. If λ approaches a positive infinity, then w ij will approach w ij = 1 if j = argmin 1≤j≤ci d ij and 0 elsewhere. Obviously, such a result is not suitable for multi-label image retrieval. The detailed analysis of how to choose a proper λ will be further demonstrated in section 4.
We also use the quantization loss J q to make the hash codes converge to hash centers [9].

Algorithm 1 Instance-weighted Central Similarity
Input: where γ is fixed and set to 0.05.

Alternative Optimization
In order to automatically solve center weight w and perform model training, we propose a two-step alternative optimization approach. In the first step, parameters of model f θ are frozen and we compute the hash codes {v i } N i=1 via f θ and Hamming distance {d i } N i=1 , we then utilize project gradient descent [27] to optimize {w i } N i=1 . In the second step, update f θ by backpropagation with fixed w. We briefly summarize the major workflow of our proposed ICS method in Algorithm 1. The solving process of w is as follows.
The gradient vector of the objective function J with respect to w i can be derived as: where w t ij denotes the value of parameter w ij at iteration t. Hence, we can find the optimum value of w ij by gradient descent: where η denotes the learning rate. In all experiments, η is set to 0.1. After obtaining solution w t i , in order to compute the Euclidean projection of w t i onto the probability simplex, Algorithm 2 Euclidean projection of w t i onto the probability simplex Input: w t i ∈ R ci Output: w t i s.t.w t ij = max w t ij + ξ, 0 , j = 1, 2, ..., c i 1: Sort w t i into q : the optimization problem is defined as follows: The solution [27] of Eq. 15 is presented in Algorithm 2.

Experiments
We first perform extensive experiments to evaluate our ICS against several state-of-the-art hashing methods on three multi-label datasets, NUS-WIDE [4] and MS COCO [18]. Afterwards, we visualize the convergence behavior of solving the optimization via project gradient descent. Finally, we conduct ablation studies to analyze the effectiveness of the learned hash center weights.

Datasets
The following three benchmark datasets are used in our experiments and their statistics are summarized in Table 1.
NUS-WIDE contains about 0.27M images in 81 categories [4]. Each image belongs to more than one label. We follow similar experimental protocols as CSQ [31], we randomly sample 10,000 images as training set, 5,000 images as queries, the remaining images are used as database.
MS COCO is an image recognition, segmentation, and captioning dataset, which contains 80 common object categories with 82,783 training images and 40,504 validation images [18]. We randomly sample 5,000 images as queries, with the rest images are used as the database; furthermore, we randomly sample 10,000 images from the database as training set.

Implementation Details
We implement the ICS method on the Pytorch framework [23], and adopt AlexNet [10] and ResNet-50 [7] pretrained on ImageNet as backbone architectures to evaluate the performance of our proposed method. We use the standard data argumentation strategies such as random horizontal flip and random crop. Each image is resized to 256×256 and then is cropped to 224×224. We apply Adam optimizer with β 1 = 0.9 and β 2 = 0.99 to optimize model parameters, and set weight decay to 0.9 and batch size to 64. The neural network is trained for 90 epochs where the learning rate starts from 0.0001 and is divided by 10 every 30 epoch.

Experimental Results
As illustrated in Table 2, our method using AlexNet backbone increases the performance by 1.1%, 0.4%, 0.5% for 16 bits, 32 bits and 64 bits on the NUS-WIDE, and yields an improvement of 6.4%, 2.8%, 1.6% for 16 bits, 32 bits, and 64 bits on the MS COCO. The results in Table 3 achieve absolute improvements of 2% and 6.6% for 16 bits on the two datasets, respectively. The above impressive results clearly demonstrate that our method achieves state-of-the-art performance by considering the relationship between the hash center weights and the proportion of foreground instances in the image.
Convergence of Project Gradient Descent We would like to study the convergence behaviour of the adopted projected gradient descent for automatically learning the  Figure 2 shows that the loss converges within 10 iterations or even fewer, which demonstrates that PGD can solve the optimization problem efficiently. The extra computational cost of PGD is relatively small, the time consuming is about 8 ms.

Ablation Study
We analyse the effectiveness of our proposed ICS in the following three aspects.

Equal Center Weights
We compare our proposed ICS with its variant, Equal Weighted Central Similarity (E-WCS). Different from CSQ [31] using single centroid as learning target, E-WCS uses multiple hash centers as learning target and fixes their weights with equal values, 1 ci . As illutrated in Table 4, the average performance of E-WCS is inferior to CSQ, and ICS achieves higher mAP than E-WCS and CSQ for different bits on NUS-WIDE and MS COCO datasets. In addition, The results demonstrate the necessity of automatically learning the hash center weights, rather than fixing them with equal values or learning with single centroid.

Parameter Analysis
We firstly tune the parameter β with fixed λ = 1, and then choose the optimal parameter β for different bits to adjust λ. We construct experiments on the analysis of hyperparameters using AlexNet backbone on Ms COCO dataset, and the chosen hyper-parameters are directly applied to all the other datasets. Parameter β. The β is a smooth parameter on the Sigmoid function Eq. 4 to control its bandwidth. As shown   Figure 5, When β is 0.001, 0.01, 0.1, the model achieves the best performance on 16, 32, and 64 bits respectively. We can conclude that smaller bits achieve the best results with smaller β, For image retrieval in 64 bits, the distance between each hash code and its corresponding hash centers is larger than lower bits. Therefore, larger β makes the curve of Sigmoid function more smoother to prevent the gradient from disappearing, which is consistent with the result of HashNet [2].
Parameter λ. The λ is used to control the maximum entropy regularization. We choose the value of λ from {10, 1, 0.1, 0.01, 0.001, 0.0001} and compare their performance on MS COCO dataset in 16, 32 and 64 bits. As discussed in Lemma 1 and illutrated in Figure 6, larger λ makes one hash center dominate the loss resulting in poor retrieval performance. The results also demonstrate that the     proposed maximum entropy regularization is not very sensitive to the value of λ when λ ≤ 1.

Visualization of Center Weights
We evaluate the model on the MS COCO dataset for visualizing the values of weights. Figure 4.4 shows the weight value of hash center corresponding to each foreground instance belonging to different categories. For example, in the last images in the lower right corner, the center weights of "person", "toothbrush" and "bench" are 0.50, 0.25 and 0.25, respectively. The visualization results illustrate that the weight values learned by ICS can well reflect the proportion of each foreground instance in the image. Moreover, although the "toothbrush" occupy a smaller region than "bench" in the image, they have same values of center weights, which demonstrate that our proposed ICS can guides the model focusing on more semantic and salient regions to improve the retrieval performance.
In addition, we also visualize the distribution of center weights. As shown in Figure 4, our method achieves the best performance 0.764 where the variance of weights is smaller. Compared with CSQ [31] in which all the weight values are equal to 1, our results demonstrate that the more uniform distribution of center weights is conducive to model learning for multi-label image retrieval.

Conclusion
In this paper, we propose to automatically learn the hash center weights by an alternative optimization approach for multi-label image retrieval. The maximum entropy regularizer prevents one hash center from dominating the loss function, and guides the model to identify the relative importance of hash centers. Our method is also an instanceaware method that the learned hash center weights can well reflect the proportion of foreground objects in the image. Experiments on two datasets validate the effectiveness of our proposed method. Beyond the multi-label image retrieval task, our method has great potential on other tasks, which needs to be further explored.