Deep Momentum Uncertainty Hashing

A growing body of research is dedicated to integrating CO and ML, since the latter can make effective decisions for the former with low computational costs [4, 1]. [3] develops a Pointer Net that is equipped with neural attention, which has the ability to find an approximate solution for the Travelling Salesman Problem (TSP). [25] proposes a novel FastColorNet that adopts deep reinforcement learning to color large graphs. [26, 4, 27] focus on leveraging graph embedding networks for robust graph matching [28, 29]. [30] develops a DeepSets architecture for node sets and also provides corresponding permutation invariant functions. With respect to resource management in wireless networks, [31] presents a LORM framework that uses imitation learning to find the best pruning policy. In contrast to the foregoing methods, this paper studies deep hashing that aims to learn the optimal binary code for each data via deep neural networks. Meanwhile, this paper also explores the uncertainty in the optimization process, which is expected to provide new insights for other combinatorial problems.

Hashing aims to project data from high-dimensional pixel space into the low-dimensional binary Hamming space [32]. It has drawn substantial attention of researchers due to the low time and space complexity. Current hashing methods can be grouped into two categories, including data-independent hashing methods and data-dependent hashing methods. For the data-independent hashing methods, the binary hashing codes are generated by random projection or manually constructed without using any training data. Locality sensitive hashing (LSH) [10] is a representative method. Since the data-independent hashing methods usually require long code length to guarantee retrieval performance, more efficient data-dependent hashing methods that learn hashing codes from training data have gained more attention in recent years [32].

The data-dependent hashing methods can be further divided into two types, i.e. unsupervised methods and supervised methods, according to whether using the similarity labels. Iterative quantization hashing (ITQ) [9] and ordinal embedding hashing (OEH) [33] are representative unsupervised hashing methods. Both of them retrieval the neighbors by exploring the metric structure in the data. Other unsupervised hashing methods include discrete graph hashing (DGH) [34], inductive manifold hashing (IMH) [35], and global hashing system (GHS) [36]. Although unsupervised learning avoids the annotation demand of the training data, exploiting available supervisory information usually implies better performance. Representative supervised hashing methods based on hand-crafted features include supervised hashing with kernels (KSH) [37] and column-sampling based discrete supervised hashing (COSDISH) [38], both of which achieve impressive results.

Benefiting from the powerful representation ability of deep neural networks [39], hashing has made further progress in the last few years [40, 41, 42]. [43] is the first one to introduce cross-modal hashing with hierarchical labels to settle real-world problems and also contributes a large-scale dataset. [44, 45] propose to leverage full label information to assist in the learning of multimodal hashing, and present a discrete optimization algorithm to learn binary codes. [46] develops a generative adversarial framework for unsupervised hashing and introduces a semantic similarity matrix to guide hashing coding. [47] digs similarity correlations between cross-modal data via a triplet sampling strategy, and elaborately designs an objective function to learn discriminative hashing codes. [48] builds two subnetworks to learn potential semantic correlations in cross-modal data and hashing codes, respectively. [49] disentangles cross-modal instances into modality-related and modality-unrelated components, and uses the former to boost the reliability of the hashing network. [50] jointly studies the weakly-supervised semantic information and data structures for effective hashing retrieval. [51] performs image-text and video-text retrieval via 2-D and 3-D CNNs respectively, in which both inter-modality and intra-modality information are considered. To understand massive social images, [52] introduces a Deep Collaborative Embedding (DCE) network to learn common representations of images and tags.

Here, uncertainty means the uncertainty of the deep neural network to the current outputs. For traditional deep learning, the network only outputs a deterministic result. However, in many scenarios, such as autonomous driving, we would like to simultaneously obtain the uncertainty of the network to that output. This will facilitate reliability assessment and risk-based decision [53]. Therefore, uncertainty has received much attention in recent years [54, 55]. [56] develops an approximate Bayesian inference framework to represent model uncertainty, which denotes the uncertainty existed in model parameters. [57] proposes to estimate model uncertainty and data uncertainty (existed in the training data) in a unified framework. [58] utilizes uncertainty to learn a confidence map that facilitates 3D deformable modeling. [53] explores the uncertainty in face images with different qualities, significantly boosting recognition performance. [59] introduces uncertainty into the feature learning of person re-identification.

In summary, there are three common uncertainty estimation strategies. The first one estimates uncertainty based on the changes of the outputs of the network [56, 60]. For example, for the same input data, there will be multiple outputs by performing multiple different dropouts on the network during the inference phase. In this case, the variance of these outputs reflects the uncertainty. The second one integrates uncertainty into the objective function and directly outputs the uncertainty via the network [57, 58]. The third one estimates uncertainty at the feature level [53, 59]. For example, the feature is represented as a Gaussian distribution that is composed of learnable mean and variance, and the variance indicates the uncertainty. It is obvious that our method belongs to the first category.

The notations employed in our method are listed in Table 1. Concretely, uppercase letters such as $B$ are used to denote matrices, and $B_{ij}$ is used to denote the $(i,j)$-th element of $B$. $B^{\top}$ indicates the transpose of the matrix $B$. Lowercase letters like $b$ denote vectors. $||b||_{2}$ is the Euclidean norm of the vector $b$. $a^{\top}b$ denotes the product of vectors $a$ and $b$. sign($\cdot$) means the element-wise sign function, which returns $+1$ and $-1$ when the element is positive and negative, respectively.

Suppose there are a total of $n$ images $X=\{x_{i}\}^{n}_{i=1}$, where $x_{i}$ means the $i$-th image. For deep supervised hashing, the pairwise similarity between two images is also available. The similarity matrix is denoted as $S$ with $S_{ij}\in\{0,1\}$, where $S_{ij}=1$ means $x_{i}$ and $x_{j}$ are similar and $S_{ij}=0$ means $x_{i}$ and $x_{j}$ are dissimilar.

The purpose of deep supervised hashing is to learn a function that maps the data from high-dimensional pixel space to low-dimensional binary Hamming space. That is, for each image $x_{i}$, we can obtain a binary hashing code $b_{i}\in\{-1,+1\}^{c}$, where $c$ means that the hashing code has $c$ bits. Meanwhile, the semantic similarity should be consistent before and after mapping. For example, if $S_{ij}=1$, there should be as short Hamming distance as possible between $b_{i}$ and $b_{j}$. Otherwise if $S_{ij}=0$, $b_{i}$ and $b_{j}$ should have long Hamming distance. Hamming distance between two binary codes is defined as:

As can be seen from the above definition, we need to find the optimal binary code for each data from all discrete $2^{c}$ possibilities, which is a classic combinatorial optimization problem.

As depicted in Fig. 2, the framework of DMUH contains two networks: a hashing network $\phi_{h}(\cdot,\theta_{h})$ and a momentum-updated network $\phi_{m}(\cdot,\theta_{m})$, where $\theta_{h}$ and $\theta_{m}$ are the weights of the two networks, respectively. Moreover, the two networks have a same architecture: a backbone for feature learning as well as a fully-connected layer for approximate binary coding. The difference lies in that the weights $\theta_{h}$ are updated via back-propagation of gradient, while the weights $\theta_{m}$ are updated by averaging $\theta_{h}$.

Given an input image $x_{i}$, the two networks output approximate binary values $h_{i}=\phi_{h}(x_{i},\theta_{h})$ and $m_{i}=\phi_{m}(x_{i},\theta_{m})$, respectively. Since $\phi_{m}(\cdot,\theta_{m})$ can be seen as an ensemble of $\phi_{h}(\cdot,\theta_{h})$ [20], we can approximatively calculate the change of $h_{i}$ over previous values by comparing the discrepancy between $h_{i}$ and $m_{i}$. As mentioned in Section 1, such change is regarded as the uncertainty of the hashing network to the current output value. For each bit, the larger the difference between $h_{i}$ and $m_{i}$, the more uncertainty the hashing network to that bit. By this means, we can get the bit-level uncertainty. For instance, as shown in Fig. 2, it is obvious that the hashing network is more uncertain about the output of the third bit. In addition, by averaging the uncertainty values of all bits in a hashing code, we can obtain the image-level uncertainty. It represents the uncertainty of the hashing network to the corresponding input image. After obtaining the bit-level and the image-level uncertainty, we will set different attention for different bits and images during training. The detailed optimization process is introduced in the following parts.

Given the binary hashing codes $B$, the likelihood of the pairwise similarity $S$ is formulated as [61, 11]:

where $\Omega_{ij}=\frac{1}{2}b_{i}^{\top}b_{j}$ and $\sigma(\Omega_{ij})=\frac{1}{1+e^{-\Omega_{ij}}}$. Considering the negative log-likelihood of the pairwise similarity $S$, hashing codes $b_{i}$ and $b_{j}$ can be optimized by [11]:

Combining with Eq. (1), we can find that minimizing Eq. (3) will make similar image pairs have shorter Hamming distance, and dissimilar image pairs have longer Hamming distance. Given that the discrete binary hashing codes are not differentiable, a usual solution is to replace the discrete binary codes with continuous real-values. Subsequently, a regularization term is imposed to enforce the real-values to be close to binary ones [11]:

where $h_{i}=\phi_{h}(x_{i},\theta_{h})$ are continuous real-values, $\Theta_{ij}=\frac{1}{2}h_{i}^{\top}h_{j}$, $b_{i}=$ sign$(h_{i})$, and $\beta$ is a hyper-parameter.

During the training process of the hashing network, the output real-value of each hashing bit constantly changes to minimize the objective function Eq. (4). Intuitively, if the real-value of one bit changes a lot during the optimization, it indicates that the hashing network has high uncertainty to that bit. In order to measure this change, a straightforward approach is to store the output of each bit in each optimization step, and then compare the current output with the previous ones. However, it is unfeasible because of the requirement of huge storage memory when training on large-scale datasets.

Inspired by the recently proposed momentum model in unsupervised and semi-supervised learning [18, 19, 20], we introduce a momentum-updated network $\phi_{m}(\cdot,\theta_{m})$ to help to estimate the uncertainty. Different from the hashing network $\phi_{h}(\cdot,\theta_{h})$ that updates its weights $\theta_{h}$ via gradient back-propagation, $\phi_{m}(\cdot,\theta_{m})$ updates $\theta_{m}$ by averaging $\theta_{h}$:

where $\alpha\in[0,1)$ is a momentum coefficient hyper-parameter, whose value controls the smoothness of $\theta_{m}$. A larger $\alpha$ will result in smoother $\theta_{m}$. Such an optimization manner can be seen as assembling the hashing networks in different optimization steps to the momentum-updated network [20]. Therefore, comparing the output of the hashing network and that of the momentum-updated network, we can approximately obtain the change of each bit during training. We regard this change as the bit-level uncertainty. That is, if a bit changes a lot, it means that the hashing network has high uncertainty to the current approximate value. Formally, the uncertainty is defined as:

where $|\cdot|$ is an element-wise absolute value operation. $u_{i}$ is a vector and each element represents the bit-level uncertainty of the corresponding hashing bit. After getting the bit-level uncertainty, by counting the average uncertainty of all bits in a hashing code, we can further obtain the image-level uncertainty of the input image corresponding to that hashing code:

where the image-level uncertainty $\bar{u_{i}}$ is a single value instead of a vector.

After getting the bit-level uncertainty $u_{i}$, we leverage it to guide the optimization of the regularization. Rather than treating each bit equally as Eq. (4), we set different weights for different bits according to the magnitude of the uncertainty, yielding a new optimization objective:

where $e^{u_{i}}$ is multiplied as a weight on the regularization term. The hashing bit with higher uncertainty is given a larger weight during regularization. In addition, the image-level uncertainty allows us to set different weights for different input images. We apply larger weights to the images with higher uncertainty in the optimization of Hamming distance. Considering both the uncertainty $\bar{u_{i}}$ and $\bar{u_{j}}$ of images $x_{i}$ and $x_{j}$, Eq. (8) is reformulated as:

It is obvious that Eq. (9) separately treats different input images (the first term) and hashing bits (the second term) under the guidance of the image-level uncertainty and the bit-level uncertainty, respectively. On this basis, we further involve the uncertainty into the optimization objective:

where $\gamma$ is a trade-off parameter. The whole optimization process for the hashing network and the momentum-updated network is summarized in Algorithm 1.

A total of four widely used datasets are employed to evaluate the proposed method, including two single-label (each image merely belongs to one class) datasets CIFAR-10 and Clothing1M, as well as two multi-label (each image belongs to one or multiple classes) datasets NUS-WIDE and MS-COCO.

For a fair comparison with other state-of-the-art methods, we employ the CNN-F network [63] pre-trained on ImageNet as the backbone of the hashing network. As shown in Table 2, the CNN-F network consists of five convolutional layers and three fully connected layers, where the last fully connected layer is modified as the hashing layer with the length of hashing codes (12 bits, 24 bits, 32 bits, and 48 bits). The momentum-updated network has the same architecture as the hashing network. The input images are first resized to 256$\times$256 resolution and then cropped to 224$\times$224. Stochastic Gradient Descent (SGD) is used as the optimizer with 1e-4 weight decay. The initial learning rate is set to 0.05 and gradually reduced to 0.0005. The batch size is set to 128. The momentum coefficient hyper-parameter $\alpha$ in Eq. (5) is set to 0.7, and the hyper-parameters $\beta$ and $\gamma$ in Eq. (10) are set to 50 and 1, respectively. We determine the values of $\beta$ and $\gamma$ by balancing the magnitude of the corresponding loss term. All experiments are conducted on a single NVIDIA TITAN RTX GPU.

In this subsection, we compare our proposed method against the traditional regularization based method (denoted as Regu), whose optimization objective is Eq. (4). The only difference between our method and Regu is the introduced uncertainty, including its estimation and usage.

Fig. 3 (a) depicts the loss curves of the two methods under different training epochs on the CIFAR-10 dataset. Fig. 3 (b) plots the corresponding MAP curves on the training set. Observing the results, we can see that the loss curve of our method converges after about 50 epochs. Meanwhile, the MAP curve reaches its peak and remains stable. By contrast, the loss curve of Regu converges much slower. In particular, the MAP curve of Regu still sharply oscillates at the 90-th epoch. The faster convergence of our method may be due to that we pay more attention on the hashing bits with drastic value changes (benefiting from the bit-level uncertainty) and the hard examples (benefiting from the image-level uncertainty). In addition, although the two methods finally have a similar MAP value in the training phase, our method obtains a much better MAP result (0.815) than Regu (0.739) in the testing phase. This further demonstrates the great generalization ability of our uncertainty based method.

In this subsection, we compare our method against its three variants to reveal the role of each component. Among them, $w/o~{}u_{i}$ means removing the optimization of uncertainty, i.e. the third term of Eq. (10). In such a case, we no longer minimize the output discrepancy between the hashing network and the momentum-updated network. $w/o~{}e^{u_{i}}$ denotes discarding the bit-level uncertainty $e^{u_{i}}$ in the second term of Eq. (10), which means that we ignore the differences among hashing bits. $w/o~{}e^{\bar{u_{i}}+\bar{u_{j}}}$ represents removing the image-level uncertainty in the first term of Eq. (10). At this point, all training images are treated equally during training.

Following the setting of [32], we report Top-5K precision curves to measure retrieval performance on the CIFAR-10, NUS-WIDE, and MS-COCO datasets. The comparison results are reported in Fig. 4. It is observed that our method obtains the best retrieval performance. The improvements of our method over $w/o~{}u_{i}$ suggest the impact of the uncertainty minimizing, which assists in transferring the knowledge from the momentum-updated network to the hashing network [19]. The gains of our method over $w/o~{}e^{u_{i}}$ demonstrate the effectiveness of the bit-level uncertainty. The hashing bits with drastic value changes are given larger weights to stabilize their outputs. The improvements of our method over $w/o~{}e^{\bar{u_{i}}+\bar{u_{j}}}$ prove the validity of the image-level uncertainty. It enables the hard examples to receive more attention during optimization and thereby helps to improve retrieval performance.

Furthermore, we also give detailed parameter analyses. Table 3 reports the parameter study of the trade-off parameters $\beta$ and $\gamma$ in Eq. (10), and the momentum coefficient $\alpha$ in Eq. (5). As can be seen from Tables 3 (a) and (b), our method is not sensitive to $\beta$ and $\gamma$ in a large range. For example, the MAP value of 24 bits only changes 0.007 when $\beta$ is set from 30 to 70. Table 3 (c) suggests that the optimal value of $\alpha$ is 0.7.

In this subsection, the proposed method is evaluated against a total of 11 state-of-the-art hashing methods, including iterative quantization (ITQ) [9], column sampling based discrete supervised hashing (COSDISH) [38], supervised discrete hashing (SDH) [64], fast supervised hashing (FastH) [6], latent factor hashing (LFH) [61], deep supervised discrete hashing (DSDH) [65], deep discrete supervised hashing (DDSH) [14], deep pairwise-supervised hashing (DPSH) [11], deep supervised hashing (DSH) [15], deep hashing network (DHN) [66], and central similarity quantization (CSQ) [67]. The brief introductions of these methods are as follows:

• -

  ITQ aims to search a rotation of zero-centered data to bridge the quantization discrepancy.

• -

  COSDISH iteratively samples columns from the similarity matrix and hashing codes are alternatively optimized without relaxation.

• -

  SDH learns hashing codes for linear classification, which is solved by discrete cyclic coordinate descent.

• -

  FastH introduces decision trees as hashing coding functions, where the decision trees are learned by a correlative two-step approach.

• -

  LFH proposes to leverage latent factor models to learn similarity-preserving binary hashing codes.

• -

  DSDH takes advantages of both similarity and classification information to learn hashing codes in a one-stream framework.

• -

  DDSH enhances the feedback between hashing coding and deep feature learning via a discrete optimization algorithm.

• -

  DPSH performs joint learning of hashing codes and deep features in an end-to-end framework.

• -

  DSH relaxes binary hashing codes to be real-values and adopts a pairwise training strategy to optimize Hamming distance.

• -

  DHN employs both a pairwise cross-entropy loss and a pairwise quantization loss to improve hashing quality.

• -

  CSQ presents a global central similarity and encourages the hashing codes of similar images to arrive at the corresponding centers.

The above state-of-the-art methods consist of three types of hashing learning approaches. ITQ is a representative unsupervised learning method. COSDISH, SDH, FastH, and LFH are non-deep supervised learning methods. DSDH, DDSH, DPSH, DSH, DHN, and CSQ are deep supervised learning methods.

The comparison results of our method against the state-of-the-art methods are tabulated in Table 4, Table 5, and Table 6, from which we obtain three observations. First, the unsupervised method ITQ lags behind all of the supervised methods, suggesting the great advantage of the supervised information. Second, the performance of deep supervised hashing methods is generally better than that of the non-deep supervised hashing methods. This indicates that the features extracted by deep neural networks are better than the hand-crafted features. Third, our method obtains the highest retrieval accuracy on all of the four datasets. For example, on the CIFAR-10 dataset, our method surpasses DDSH by 3.9% at 24 bits. On the NUS-WIDE dataset, we improve the best MAP values of all bits at least 1.2%. On the MS-COCO dataset, we also get an improvement of 1.6% at 12 bits. Specially, on the large-scale Clothing1M dataset, the MAP value is significantly improved by 3.7%, 3.9%, 4.6%, and 5.5% in terms of 12, 24, 32, and 48 bits, respectively. Compared with the state-of-the-art CSQ, our method also presents more superior performance, obtaining at least 1.8% improvements on the four datasets. The compared deep supervised hashing methods adopt a similar binary approximation that treats all hashing bits equally, such as DSDH uses the activation function Tanh and DPSH uses the regularization. With these in mind, we owe the gains of our method over the competitors to the proposed uncertainty-aware learning approach. It applies different attention weights for different hashing bits and input images according to the magnitude of the bit-level and image-level uncertainty, respectively.