A Probabilistic Code Balance Constraint with Compactness and Informativeness Enhancement for Deep Supervised Hashing

1 Introduction

Due to the explosive growth of high-dimensional and largescale data in real applications, hashing has attracted significant attention and has been widely utilized for fast information search and retrieval tasks in recent years. Intending to improve storage and search efficiency, hashing encodes high-dimensional data into compact binary codes which preserve the similarities of original data. Parallel to traditional data-independent hashing, e.g., locality sensitive hashing (LSH) [Datar et al., 2004] applying random projections as hash functions, this paper focuses on data-dependent hashing (specifically supervised hashing). It aims to learn taskspecific hash functions to guarantee the similarities in hash coding space as close as those in the original space and is roughly categorized into supervised and unsupervised hashing [Wang et al., 2016; Wang et al., 2018].

∗Corresponding authors

Benefiting from the advances of deep neural models in nonlinear end-to-end representation learning, deep hashing has enjoyed wide attention in similarity retrieval [Wang et al., 2021]. Especially, deep supervised hashing (DSH) methods jointly learn deep representation and hash codes through given similarity/label supervision, achieving state-of-the-art retrieval performance [Wu et al., 2019]. Recent DSH methods focus primarily on refining or customizing objective functions for preserving similarity, e.g., reducing quantization loss caused by continuous relaxation [Gattupalli et al., 2019], weighting training pairs to tackle the label imbalance issue [Cao et al., 2018] and introducing class-wise learning objective [Wang et al., 2020]. However, these methods hardly involve code balance constraints to improve hash quality, e.g., compactness and informativeness of hash codes. In fact, a large number of works have demonstrated that code balance can effectively avoid learning collapse, i.e., generating the same hash codes for all similar datapoints, and facilitate generating compact and informative hash codes [Weiss et al., 2008; Chen et al., 2019]. Figure 1 illustrates an example of random 5, 000 images from the CIFAR-10 dataset. We can observe: figure (b) is overly intensive and figure (c) shows excessive dispersion and intra-cluster overlaps (fewer points in figure), and both two figures show massive inter-cluster overlaps. In contrast, figures (e) and (f) show better performance due to preserving both inter-cluster and intra-cluster discriminability, indicating that code balance promotes code compactness and informativeness.

Unfortunately, traditional code balance constraints, such as bit balance and bit uncorrelation, imposed on whole data population [Weiss et al., 2008], are unsuitable for DSHmethods due to three key issues: 1) finding the zero-mean-thresholded hash functions that achieve bit balance is difficult, especially when building deep hash functions [Wang et al., 2012]; 2) obtaining the hash codes for all datapoints once is both inefficient and impractical when simultaneously learning deep data representation and hash functions; 3) traditional code balance constraints are unsuitable for the conventional batch training in deep models, since guaranteeing code balance across the entire data population hardly hold same balance conditions in each data batch. Due to the above issues, DSH methods rarely consider the benefits obtainable from code balance, which leads to low quality and representability of hash codes.

To tackle the above issues, we propose a novel probabilistic code balance constraint suitable for DSH scenarios. Specifically, we force each hash code to independently satisfy a discrete uniform distribution on {-1, 1}K , i.e., Uni({-1, 1}K ). Our theoretical analysis indicates that it not only covers the traditional bit balance and bit uncorrelation constraints but maximizes the mutual information between the original data and the corresponding hash codes. The deep insights reveal that the constraint introduces random noise to uniformly scatter datapoints into hash space and to improve hash robustness and avoid overfitting. In addition, we propose a Wasserstein regularization that utilizes the Wasserstein-1 distance to measure the distance between the hash code distribution and the target discrete uniform distribution and minimize the regularization to achieve the constraint. The contributions can be summarized as follows:

• We propose a novel probabilistic code balance constraint suitable for DSH and theoretically analyze the effectiveness and insights of the constraint for the first time.
• We introduce Wasserstein regularization to achieve the constraint via Wasserstein-1 distance and propose an empirical estimate of the Wasserstein regularization.
• We conduct extensive experiments using different types of SotA DSH baselines on two benchmark datasets in terms of metrics on retrieval performance and informa-

tiveness. The results show the constraint not only enhances code compactness for promoting retrieval performance but improves the informativeness of hash codes.

2 RelatedWork

Supervised hashing aims to learn similarity-preserving hash functions via the given/computed similarity relation in the original space [Wang et al., 2018]. With the emergence of early supervised hashing methods, e.g., spectral hashing [Weiss et al., 2008], graph hashing [Liu et al., 2014] and kernel hashing [Liu et al., 2012], which learn hash projection vectors rather than random projections in the data-independent hash, supervised hashing has attracted an increasing amount of research interest and achieved significantly better performance than the data-independent hash [Shi et al., 2017]. To improve hash quality, the non-deep supervised hashing adopts code balance constraints - bit balance and bit uncorrelation - to avoid learning collapse and facilitate generating compact hash codes [Luo et al., 2020].

Deep supervised hashing methods, leveraging the capability of deep learning in representation learning, outperform non-deep hashing methods and has thus been widely applied [Dizaji et al., 2018; Wu et al., 2019]. Most DSH methods focus on refining or customizing objective functions, e.g., quantization loss [Zhu et al., 2016; Gattupalli et al., 2019], weighted pairwise loss [Cao et al., 2018] and triple loss [Liu et al., 2018], for preserving similarity. A couple of works, e.g. pointwise methods [Jiang et al., 2018; Su et al., 2018], further introduce label supervision to capture global position relationship, which is influenced by the quality of classification results. Recently, some works introduce class centers as proxies of classes to ensure continuous semantic similarity, which improves the discriminability of hash codes [Yuan et al., 2020; Wang et al., 2020]. Although these methods can achieve excellent performance, code balance constraints, which are beneficial to improving hash quality, are generally ignored in the DSH context. Quite a few previous methods such as [Chen et al., 2019] consider code balance to improve hash quality. However, those methods often utilize discrete optimization algorithms to solve the objective functions and act on the whole data population, which thus is inefficient under large-scale data and unsuitable for DSH. To tackle these issues, this work proposes a probabilistic code balance suitable for DSH to facilitate the learning of compact and informative hash codes.

3 Preliminary: Supervised Hashing

We first outline the general supervised hashing settings used to achieve similarity-preserving hash codes. Let X ⊂ RD and Y ⊂ {-1, 1}K be the input domain and binary hash domain respectively, where D and K denote their respective dimensions. We have pairwise supervision of similarity information S ∈ {0, 1}n×n for n datapoints where sij = 1 if datapoints xi and xj in X are semantically similar and sij = 0 otherwise. Supervised hashing aims to learn a mapping function Hϕ := X → Y with parameters ϕ (e.g., a neural network) by minimizing the gap between the similarities S in the input domain X and those calculated in the hash domain Y. We then introduce the two traditional code balance constraints.

Code Balance. To avoid severe overfitting and guarantee high-quality hash codes [Wang et al., 2016; Wang et al., 2018], bit balance and bit uncorrelation are usually considered from the information-theoretic perspective. Let X := {xi ∈ X}ni=1 and Y := {yi = HΦ(xi), yi ∈ Y}ni=1 .

• Bit Balance: To generate compacted hash codes, it is desirable to maximize the information contained in each hash bit. According to the maximum entropy principle, hash bits that provide balanced partitioning of X, i.e., ∑ni=1 yi = 0, have maximum information.
• Bit Uncorrelation: A general method of obtaining informative hash codes is to maximize the informativeness in hash codes by forcing the different hash bits to be uncorrelated (mutually orthogonal), i.e., ∑ni=1 yiyT i = nI (where I is an identity matrix of size n).

4 Probabilistic Code Balance Constraint

We propose a novel code balance constraint that suits DSH scenarios. More specifically, we force each generated hash code independently to satisfy a discrete uniform distribution on {-1, 1}K , e.g., y ∼ Uni({-1, 1}K ), where we can prove that the constraint over Y covers the aforementioned bit balance and bit uncorrelation constraint:

Theorem 1 (Coverage of Bit Balance and Bit Uncorrelation). For any yi ∈ Y, if yi ∼ Uni({-1, 1}K ), it satisfies E(∑ni=1 yi) = 0 and E(∑ni=1 yiyT i ) = nI.

Theorem 1 (proved in Appendix A) indicates that y ∼ Uni({-1, 1}K ) can achieve both effects of the above two code balance constraints. Unlike the two constraints performing summation over the hash codes of all datapoints in a symmetrical manner, our proposed asymmetrical constraint forces the hash codes to satisfy the independent discrete uniform distribution and has no need to obtain the hash codes for all datapoints beforehand. It can effectively avoid the difficulty in achieving the zero-mean threshold in the bit balance.

Theorem 2 (Mutual Information Maximization). Given X and Y where Y is a deterministic function of X, if PY is a uniform distribution on the space of Y; then mutual information between X and Y, i.e., I(X,Y), is the maximum.

The key insight underpinning the probabilistic code balance constraint is that of maximizing the mutual information between the original data and the corresponding hash codes (as illustrated in Theorem 2 proved in Appendix B). The obtained hash codes, therefore, preserve not only the similarity relationships but also more information from the original data. Intuitively, the constraint uniformly scatters datapoints into hash space via introducing random noises, which facilitates avoiding overfitting training data and improves the generalization robustness of hash functions. In addition, we can easily find that our proposed constraint is irrelevant to the scale of data since the proposed constraint is imposed on every single bit. It is therefore consistent to impose the constraint on data batches and the whole data population, indicating that the constraint is suitable for batch training. In summary, the proposed code balance tackles the three key issues in adopting the traditional code balance constraints and is suitable for DSH. Next, we minimize the distance between the distribution of the generated hash codes and the target discrete uniform distribution to achieve the proposed constraint.

4.1 Wasserstein Regularization

We propose a Wasserstein regularization to estimate the distance between the distribution of generated hash codes and the target discrete uniform distribution, thereby achieving the proposed probabilistic code balance constraint via minimizing the estimated distance. We here denote the discrete uniform distribution as Pr : Uni({-1, 1}K ), and the distribution of hash codes as Pϕ, i.e., yi ∼ Pϕ, which is generated by the specific deep hash function Hϕ. To achieve yi ∼ Uni({-1, 1}K ), we minimize the distance between the two distributions Pr and Pϕ. Accordingly, we introduce the Wasserstein-1 distance (a.k.a. Earth-Mover distance), which is a distance function between probability distributions defined on the same metric space Ω, i.e., Pr and Pϕ defined on space Ω = {-1, 1}K in our case:

where Γ(Pr,Pϕ) denotes the set of all joint distributions γ(y, y′ ), the marginal distributions of which are Pr and Pϕ respectively. Intuitively, we can understand the definition via considering the optimal transport problem: in the given space Ω, the Wasserstein-1 distance reflects the minimal cost of transporting mass from Pr to Pϕ in order to transform the distribution Pr to the distribution Pϕ. Analogously, we propose an empirical estimate of the Wasserstein-1 distance in a way that makes it unnecessary to directly estimate the distribution of hash codes. More specifically, given input data X ∈ Rn×D , we first randomly sample n binary target vectors denoted by A, the elements of which follow Pr:

We then optimally pair the hash code of each datapoint with each target vector respectively such that the sum of the distances between all pairs is minimal. To obtain the optimal pairing matrix P ∈ {0, 1}n×n , we first define a set of constraints (denoted P) for all possible pairing matrices:

where 1n denotes a n-sized vector with all 1s. Given hash codes Y of X, we then optimize the following objective:

where we use a squared ℓ2 distance, and tr(·) denotes the trace function. Once an optimal pairing matrix P is found, the above distance can be regarded as an estimate of the Wasserstein-1 distance between Pr and Pϕ, that is:

Accordingly, the learning objective of DSH equipped with Wasserstein Regularization (WR) contains two components:

Algorithm 1 Alternating Optimization

• 1: Input: Given input data S.
• 2: Initiate the neural network ϕ and set batch size b
• 3: while stopping criteria is not satisfied do
• 4: Fixing ϕ, randomly sample b input samples Xb and calculate ˜Yb.
• 5: Randomly sample Ab from the distribution Pr.
• 6: Solve Pb using Hungarian algorithm.
• 7: Update ϕ using batch gradient descent according to the gradients ∇ϕJ ′ (ϕ).
• 8: end while

the similarity loss used to preserve the similarity S in the original space, and the Wasserstein Regularization which enhances the compactness and informativeness of hash codes:

where Y = Hϕ(X), and β > 0 denotes a balance weight adjusting the importance of Wasserstein Regularization. The similarity loss is calculated via the loss function ℓ and can be specified to the similarity loss of a certain DSH method.

4.2 Optimization

Following the common continuous relaxation treatment [Li et al., 2017; Cao et al., 2018], we approximate the sgn function with a squashing function (e.g., tanh), the output ˜Y of which is within (-1, 1). We thus obtain a differentiable neural function H′ϕ := X → ˜Y and the corresponding learning objective J ′ (ϕ) updated as below, of which the parameters can be solved using gradient-based back propagation algorithm.

Apart fromAwhich is randomly sampled from the distribution Pr, we further need to obtain the optimal pairing matrix P. Obtaining P is a linear assignment problem, which can be solved exactly via Hungarian algorithm [Kuhn, 1955]. Under the batch gradient updates, the algorithm can efficiently perform under the restriction of one batch, significantly reducing the time complexity from O(n3 ) to O(nb2 ), where b is the number of samples in one batch.

Accordingly, we apply an alternating optimization to solve Equation 7. First, when fixing ˜Y, we sample b training samples Xb and calculate its corresponding intermediate matrix ˜Yb. We then randomly sample b target vectors, denoted by Ab from the discrete uniform distribution and solve Pb ∈ Pb with the Hungarian algorithm to optimally pair ˜Yb and Ab. Finally, when fixing Ab and Pb, we update the parameters ϕ via batch gradient descent. The corresponding algorithm is presented in Algorithm 1.

5 Experiments and Evaluation

To verify the effectiveness of the proposed probabilistic code balance in promoting retrieval performance and improving hash code quality, we select six state-of-the-art deep hashing baselines and compare the baselines with their variants equipped with WR on two public image datasets.

5.1 Experimental Setup

Datasets. We adopt two public image datasets for evaluation. 1) CIFAR-10 1 : the dataset consists of 60, 000 32 × 32 images in 10 classes, where each class has 6, 000 images. Two images will be treated as a ground-truth similar pair if they share common label. 2) NUS-WIDE 2 : it contains a total of 269, 648 images. Similar to [Zhu et al., 2016; Liu et al., 2019], we use its subset of 195, 834 images associated with the 21 most frequently concepts, where each concept consists of at least 5000 images, and define two images as a groundtruth similar pair if they share at least one common label.

Baselines. We select different types of SotA DSH methods, including pointwise, pairwise and class-wise methods, for evaluation in our experiments: 1) DSDH [Li et al., 2017] jointly learns a linear classifier based on pointwise groundtruth labels along with the hash functions; 2) HashNet [Cao et al., 2017] tackle the data balance issue by weighting training pairs; 3) DCH [Cao et al., 2018] further introduces a Cauchy cross-entropy loss to measure pairwise similarity; 4) ADSH [Jiang and Li, 2018] directly learns hash codes for all database points asymmetrically and efficiently. 5) CSQ [Yuan et al., 2020], the latest class-wise method, proposes a global similarity metric referring to hash centers. 6) DPAH [Wang et al., 2020] introduces learnable class centers as the global proxies to capture global similarity. Note that non-deep hashing methods are not included in our experiments due to the focus on DSH. To evaluate the effectiveness of our proposed probabilistic code constraint, we construct a WR-enabled variant for each baseline, i.e., adding the Wasserstein regularization to its objective function.

Evaluation Protocol. We follow the experimental settings recommended in [Zhu et al., 2016; Li et al., 2017]. In CIFAR10 and NUS-WIDE, we randomly sample 100 images per class to form the testing set, with the remaining images used as the database, then randomly sample 100 images and 500 images per class from the database to act as the validation set and training set respectively (we adopt the whole database for training in ADSH for consistency.). To facilitate fair comparison, we adopt the same network (see Appendix C), fix batch size to 256 for all baselines, and evaluate the comparative methods over code length K ∈ {16, 32, 48, 64}. We tune the baselines on validation sets to find their optimal configuration. For their WR-enabled variants, we further tune the balance hyperparameter β within the range of 0.1 to 1.0 with step 0.1 to obtain the best results. All experiments have been run five times, and the average results are reported. In the experiments, we report the Mean Average Precision (MAP) to evaluate similarity retrieval performance, while Mutual Information Neural Estimation (MINE) [Belghazi et al., 2018] is used to evaluate the informativeness of hash codes.

5.2 Results and Discussion

Retrieval Performance. The MAP results of each baseline and its corresponding WR-enabled variant are reported in Table 1. As we can observe from the table, the WR-enabled variants outperform their corresponding baselines. More specifically, the WR-enabled variants perform much better on longer code lengths, i.e., 32 bits and 48 bits, where the MAP improvement of each WR-enabled variant over its baseline is over 1.74% and can reach 3.87%. This is intuitively attributable to the fact that the learning of the similaritypreserving objective is more easily distorted, and more vulnerable to the noise introduced by WR, as smaller code lengths. Moreover, we find that the improvement on ADSH, CSQ, and DPAH is larger than that on the others. This is attributable that WR-enabled ADSH trained on the database points improves the quality of the hash codes on these points, while the Wasserstein regularization can further improve the discriminability of the hash codes (especially for similar datapoints) generated from the class-wise methods, i.e, CSQ and DPAH. The above results are impressive since the Wasserstein regularization promotes the retrieval performance on different kinds of DSH methods, including point-wise (labelbased), pairwise and class-based methods. In addition, we investigate the approximation quality of Wasserstein-1 distance (i.e., Equation 5) and observe that the WR-enabled variants get better performance with the increase of batch size and the best MAP when batch size b = 512 (see Appendix D). These results demonstrate that Wasserstein regularization introducing random noises is beneficial to improving the robustness of hash functions and avoiding overfitting training data.

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

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

Training Complexity. We ran the baselines and their WRenabled variants using a single GTX-1080 GPU. The average training time costs on different training batch sizes are reported in Table 2; ∆ denotes the percentage of additional training time cost required by WR-enabled variants over their corresponding baselines. The results show that the time cost for computing Wasserstein regularization increases as the batch size increases. This is because the bulk of the time cost associated with WR computation is linked with predicting hash codes for batch data, i.e., O(bTh) where Th denotes the time complexity for a single datapoint, as well as that for applying the Hungarian algorithm, i.e., O(nb2 ). In addition, the percentage is less than 13% when the batch size b <= 256, indicating that the additional time cost is affordable and worthwhile considering the benefits of WR.

Performance Varying with β. We also investigate the retrieval performance of WR-enabled variants under varying values of β on the two datasets. Note that results on K = 48 are not reported due to space limitations. Comparing the figures of different bits, we find that the WR-enabled variants perform better on longer code lengths and worse on shorter code lengths, confirming the results in Table 1. In addition, the performance of most WR-enabled variants decreases as the values of β increase from 0.3 to 0.9, especially on K = 16 and K = 32. This is reasonable because Wasserstein regularization - i.e., the probabilistic code balance - improves hash quality by introducing random noise and avoiding DSH overfitting from arising during the supervision of similarity in training data. However, when β increases, a larger weight is allocated to Wasserstein regularization; this may result in the hash function being highly biased to noises and greatly degrade the retrieval performance.

5.3 Code Compactness and Informativeness

In this section, we evaluate the compactness and informativeness of the hash codes generated in the first experiment. We first calculate the mutual information between the original data (images) and the corresponding hash codes via MINE by a 100 - 100 - 1 sized three-layer fully-connected neural network, as in Table 3. The results show that WR enables large amounts of mutual information between each original data and its hash codes, which indicates that the Wasserstein regularization improves the informativeness of the generated hash codes. We further visualize the hash codes via T-SNE, as shown in Figure 3. We find that WR-enabled variants achieve good performance, and even outperform their baselines, in terms of similarity preservation. In addition, when comparing WR-enabled variants with their baselines, we easily observe that hash codes generated by WR-enabled variants are scattered and exhibit less overlap, indicating the higher compactness and informativeness of the hash codes. These results demonstrate the effectiveness of the probabilistic code balance and reveal that WR, with its introduction of random noise to scatter hash codes, improves the compactness and informativeness of hash codes and provides benefits for model generalization, i.e., avoiding training data overfitting.

6 Conclusions

To improve the quality of hash codes in deep supervised hashing, we propose a novel probabilistic code balance constraint, which forces each hash bit to independently satisfy a discrete uniform distribution on {-1, 1}K (K is hash code length). We prove and analyze the effectiveness and insights of the proposed constraint, and further incorporate the Wasserstein regularization to implement the constraint. Extensive experiments by comparing six DSH baselines and their WR-enabled variants on two image benchmark datasets demonstrate the probabilistic code balance can effectively promote retrieval performance and improve the compactness and informativeness of hash codes.

Acknowledgments

This work is supported in part by Australian Research Council Discovery Grant (DP190101079), ARC Future Fellowship Grant (FT190100734), the National Key R&D Program of China (2019YFB1406300), National Natural Science Foundation of China (No. 61502033), and the Fundamental Research Funds for the Central Universities.