Deep Polarized Network for Supervised Learning of Accurate Binary Hashing Codes

1 Introduction

The ultimate goal of learning to hash (LtH) is to preserve the similarity of neighboring data points such that semantically similar items are grouped together and can be efficiently retrieved upon querying requests. Generally, the learning objective is often formulated as the minimization of a loss based on the pairwise hash code differences e.g. in [Lin et al., 2013]:

in which yij = {-1,+1} is the given similar/dissimilar relations for a sample data pairs (xi, xj), the loss L(Φ(xi),Φ(xj), yij) simultaneously minimizes intra-class and maximizes inter-class Hamming distances between similar/dissimilar hash codes, and Φ : X → Hb are the binary hash functions to be learned.

One central difficulty for optimizing (Eq. 1) lies in the vanishing gradients of binary hashing functions Φ(xi) which in general lead to a NP-hard binary optimization problem. Two principled solutions have been proposed in the literature - the first solution is to approximate Φ with continuous relaxation e.g. either by evolving a smoothed activation function [Cao et al., 2017] or simply eliminating the hard binary constrains and penalizing large deviations from the desired binary outcomes [Liu et al., 2016]. This continuous relaxation allows gradient-based optimization methods e.g. backpropagation to be directly applied, yet deviations from binary codes inevitably induces quantization errors and arguably gives rise to sub-optimal hash codes [Su et al., 2018]. The second solution is to decompose the original optimization problem into two sub-problems i.e. binary code inference and hash function learning [Lin et al., 2013]. Although the optimal hash functions can be learned with respect to a variety of loss functions defined on the recovered binary codes, the assignment of appropriate codes to each data points in the initial step is itself a non-trivial task and sophisticated algorithms e.g. bit-wise block coordinate descent or discrete cyclic coordinate descent have to be employed [Lin et al., 2013; Shen et al., 2015]. Bearing in mind the merits and shortcomings of these two aforementioned solutions, one may wonder whether it is possible to come up with a simple differentiable loss that is guaranteed to minimize the original Hamming distance based loss with no quantization errors incurred, and at the same time, no sophisticated binary optimization solvers are needed. This open problem is the primary motivation of our work illustrated in this paper.

To this end, the present paper proposes a novel deep polarized network (DPN) for learning to hash as illustrated in Figure 1, in which each channel in the network outputs is enforced towards either positive or negative extremes by employing a differentiable bit-wise hinge-like loss which we dubbed as "polarization loss". A number of methodological advantages of the proposed polarized networks are as follows. First, it is demonstrated by both theoretical proof and empirical investigations, that the proposed polarization loss strictly bounds from above the Hamming distance between similar/dissimilar hash code pairs. As such, minimizing the polarization loss is equivalent to simultaneous minimizing the intra-class and maximizing inter-class Hamming distances (see Proposition 3). Second, the subtask of binary code inferences in the two-step approach becomes extremely simple - even random codes assigned to each class suffice to result in state-of-the-art performances, as demonstrated in CIFAR10, NUS-WIDE and ImageNet100 datasets. Moreover, hash codes accuracies can be consistently elevated above thestate-of-the-art, by encoding non-polarized network outputs with an intermediate state i.e. 0 between {-1,+1}. This ternary assignment results in 2% to 8% improvements of mAP for experiments in all three datasets.

1.1 RelatedWork

Numerous hashing methods have been proposed over the years and, due to limited space, we only review those related to our method. Please refer to [Li et al., 2016; Lin et al., 2017; Cakir et al., 2018; Wang et al., 2018; Cakir et al., 2019] for thorough reviews of related works. As shown in Table 1, we broadly categorize existing hashing methods according to two dimensions i.e. (i) what type of label information is exploited, and (ii) in which way low-level (image) features are extracted.

Among the four different types of label information i.e. pointwise, pairwise, triplet and rank labels that were used for LtH, the pairwise labels is probably the most commonly employed e.g. in [Kulis and Darrell, 2009; Jeong and Song, 2018; Cakir et al., 2019], with computational complexity O(N 2 ) for N data points. In terms of neural network architectures, Siamese networks are often needed to take pairs or triplets images as inputs during the learning stage [Li et al., 2016; Wang et al., 2016; Zhuang et al., 2016]. In contrast, pointwise labels lead to loss functions which are faster to compute and easier to optimize. Although pointwise labels enjoyed computational and network simplicities e.g. as shown in [Shen et al., 2019], previous works did not disclose the intrinsic connection between pointwise and pairwise losses, which is illustrated in Section 2.2 of this paper.

Recent LtH methods have witnessed significant improvements in terms of hashing accuracies by replacing handcrafted (image) features with Deep CNN features which are first pre-trained for classification task e.g. with ImageNet dataset and subsequently fine-tuned for hashing [Lin et al., 2015; Zhao et al., 2015; Cao et al., 2018]. It was also demonstrated e.g. by [Shen et al., 2015; Yang et al., 2018] that jointly learning features with hash functions may improve the hashing accuracies.

A hinge-like loss (Eq. 4) with a Hamming Ball radius parameter was adopted in [Norouzi and Blei, 2011] to differentiate similar/dissimilar points. In a similar vein, hinge-like losses were also adopted for triplet or rank based labels e.g. within the well-developed Hamming Distance Metric Learning framework [Norouzi et al., 2012]. However all these hinge-like losses are defined in the binary Hamming space, which are different from the polarization loss defined on realvalued network outputs (see definition in Section 2.2).

The proposed polarization network bears some similarities with the binary weight networks used for network compression e.g. [Hu et al., 2018]. Also a sign loss was used to embed signatures into deep neural networks to provide ownership verification for IP protection [Fan et al., 2019]. Nevertheless, motivations of these applications were different from LtH and, moreover, the connection with pairwise hashing objectives disclosed in this paper was not mentioned there.

2 Deep Polarized Networks

This section illustrates a novel deep polarized network (DPN), in which the network outputs are pushed away from zero to either positive or negative sides. We first formulate below the DPN within the well developed Hamming Distance Metric Learning framework [Norouzi et al., 2012] and then elaborate the proposed polarization loss, which, to our best knowledge, is the only single differentiable loss term that simultaneously minimizes inter-class and maximizes intraclass Hamming distances.

2.1 Deep Polarized Network for Hamming Distance Metric Learning

Our goal is to learn a hash mapping that maps real-valued data points x ∈ Rp into K-bit binary codes b ∈ HK := {-1,+1}K , such that similar data are mapped to similar binary codes with small Hamming distances, and vice versa.

For K-bit binary codes b, the hash mapping function Φ is parameterized by w,

in which the general function Ψ : Rp → RK admits different forms of implementations as shown in the Hamming Distance Metric Learning framework [Norouzi et al., 2012]. In this work, Ψ can be implemented in any existing deep CNN appended with a fully connected output layer that consists of K channels representing K bits. See Figure 1 for a diagram of the DPN architecture.

The choice of loss function is crucial for learning good similarity measures. While majority of the existing LtH methods formulate learning objectives in terms of pairwise or triplet similarities e.g. in [Norouzi and Blei, 2011; Norouzi et al., 2012], we show that pairwise or triplet label information are actually not needed for the polarization loss proposed below.

2.2 Polarization Loss

Definition 1 (Polarization loss). For each data x ∈ X and its corresponding output vector v := Ψ(x;w) ∈ RK , the polarization loss is defined on the vector v with respect to a pre-set target binary code t ∈ H as follows,

where the margin threshold is pre-set, m ≥ 1, for the bound in Lemma 1 to be strict.

By minimizing the polarization loss (Eq. 3) during the learning phase, magnitudes of each DPN output channels are induced above the threshold m while corresponding signs are aligned to the target vector t. Figure 5 illustrates the distribution of outputs v, for example images fed to a DPN. Clearly large margins push the network outputs further away from zero. It must be noted that, the outputs for correctly coded images are polarized while non-polarized outputs are more likely observed for mis-classified ones.

Lemma 1. For output vector v = Ψ(x;w), the Hamming distance Dh(b, t) := 12 (K - b · t) between K-bits binary hash code b = sign(v) and the corresponding binary vector t is upper bounded by the polarization loss

for any m ≥ 1 and v ∈ {(v1, · · · , vK)∣∣vk ∈ R}.

Proposition 1. Suppose class C consists of data points {x1, · · · , x|C|} associated with a pre-set target t ∈ H in Hamming space. The averaged intra-class pairwise Hamming distances among the corresponding binary codes {b1, · · · , b|C||bi = Φ(xi; w)} is upper bounded by,

Proposition 2. Suppose there are L classes in the dataset, i.e. C1, · · · , CL. For any two classes Cx and Cy (1 ≤ x ̸= y ≤ L), respectively, with associated targets binary vectors tx and ty and binary hash codes bxi = Φ(xi;w), i ∈ {1, · · · , |Cx|}, byi = Φ(yj;w), j ∈ {1, · · · , |Cy|}, the averaged inter-class pairwise Hamming distances among binary codes ∑1≤i≤|Cx|, 1≤j≤|Cy | Dh(bxi , byj ) is lower bounded by,

Proposition 3. The difference between averaged intra-class pairwise Hamming distance and averaged inter-class pairwise Hamming distance is upper bounded, i.e.

Remarks:

• I Inequality in (Eq. 5) shows that the averaged polarization loss is a strict upper-bound of the averaged pairwise Hamming distances between points of the same class. That is to say, minimizing the RHS of (Eq. 5) effectively minimizes the averaged intra-class pairwise Hamming distances.
• II In terms of the computational complexity, pairwise Hamming distances on the LHS of (Eq. 5) is O(|C|2 ) while the polarization loss on the RHS of (Eq. 5) is O(|C|) only.
• III Inequality in (Eq. 6) shows that minimizing polarization losses on the RHS of (Eq. 6) effectively maximizes the averaged inter-class pair-wised Hamming distances on LHS.
• IV According to Proposition 3, the optimization problem of simultaneous minimizing the intra-class and maximizing inter-class Hamming distances, i.e.

is equivalent to the problem of minimizing the averaged polarization loss over the whole data set, i.e. 1

2.3 Empirical Investigations of Error Terms

LHS of (Eq. 7) is the averaged intra-class Hamming Distance minus the inter-class Hamming distance. This quantity has been used to minimize Hamming distances between similar pairs while maximizing Hamming distances between dissimilar pairs, for both pairwise and triplet based losses e.g. [Norouzi and Blei, 2011; Norouzi et al., 2012]. Proposition 3 proves that LHS is strictly bounded by RHS of (Eq. 7), which is the polarization loss minus the pairwise Hamming distance between the target vectors.

Empirically, Figure 2 shows that the proposed polarization loss is closely related to the intra-class and inter-class Hamming distances between similar/dissimilar data pairs, up to a constant that depends on the pairwise Hamming distances between target vectors. Indeed the measured Pearson correlation between these two plots is as high as 0.9935. We view this strong correlation as an unique and favorable feature of the proposed polarization loss. In contrast, error terms used in [Su et al., 2018] and [Cao et al., 2017] neither bounded intra-class nor inter-class Hamming distances. Note that the scales for these error terms are significantly different and the corresponding Pearson correlation are measured at 0.913 and 0.882 respectively.

1 Due to the limited space, proofs of propositions are omitted from the paper and will be included in an elaborated report.

2.4 The Setting of Target Vectors

The minimization of (Eq. 8) is a simple problem in terms of the number of parameters to be optimized - target binary vectors tx are constants while network parameters w for real-valued outputs vxi (x; w) are directly optimized using the back-propagation, thanks to the differentiable polarization loss LP.

Two strategies have been investigated in the setting of target vectors: (i) random assignments; (ii) adaptive updating with random initialization. Algorithm 1 summarizes the pseudo-codes of both setting schemes.

Algorithm 1 Training of Deep Polarized Network

1: Input 2: x,t sample data and target binary vectors 3: Output 4: Ψ(;w)trained DPN 5: procedure TRAIN(Ψ) 6: for number of epochs do 7: v ← Ψ(x; w) 8: w ← w - lr ∗ ∇w(Lp(v, t)) 9: if adaptive updating then 10: vcorrect ← find v with correct prediction 11: for each class, c do 12: b ← sign(vcorrect c ) 13: tc ← sign(mean(b, axis = batch)) 14: end for 15: end if 16: end for 17: end procedure

Random Assignments of Target Vectors

Random projections have long been adopted in the locality sensitive hashing (LSH) as data-independent hashing functions with a theoretical guarantee of successful approximate nearest-neighbour search [Indyk and Motwani, 1998; Andoni and Indyk, 2006]. Following this principle, we adopt a Random Assignment scheme for setting target vectors associated with each class. This random assignment scheme is guaranteed to generate target vectors that are of sufficient inter-class hamming distances as shown below.

Claim: Suppose K-bit Hamming space HK := {-1, 1}K , two binary target vectors tx, ty ∈ HK are sampled with probability p for 1 on each bit. The expectation of Hamming distance is then given by Ep(Dh(tx, ty)) = 2K · p(1 - p), whereas the expectation achieves maxima K when p = 0.5.

Figure 3 plots the expected hamming distances, the measured hamming distances and the hashing accuracies with respect to different ratios of positive bits. Clearly, the maximal inter-class hamming distance gives rise to the optimal hashing accuracy, which is in line with the bound in (Eq. 7). Following the theoretical analysis and the ablation study, we set the ratio of random assignments of positive bits as 0.5 in all the experiments.

Adaptive Updating of Target Vectors

For the adaptive scheme, target vectors are repeatedly updated during the learning of hash functions (see Algorithm 1). It was observed that, (i) frequent updating is not necessary or sometimes bring about adverse effect to the convergence of learning process; (ii) the improvements in hashing accuracies brought by the adaptive updating is marginal (see results in Section 3.3); (iii) updated vectors do reflect the intrinsic similarities among different classes e.g. dog and cat for CIFAR10 dataset (see Figure 4).

3 Experiment Results

This section illustrates the experiment results and ablation study of the hyper-parameter i.e. margin m. Also, an effective ternary assignment is demonstrated with hashing accuracies levitated above the state-of-the-art solutions.

3.1 Datasets and Experiment Settings

CIFAR10 [Krizhevsky, 2009] consists of 10 classes with 60K images. We follow the settings from [Cao et al., 2017] where 100 images per class are selected randomly as query set while the remaining images are used as retrieval set. We randomly sample 500 images per class from the retrieval set for training.

NUS-WIDE [Chua et al., 2009] consists of 81 concepts with 269K multi-labeled images. We follow the settings from [Cao et al., 2017], where 21 of the most frequent concepts are being used as image annotations, and hence 195K images are selected. We selected 100 images per concept randomly as query set while the remaining images as retrieval set. Then we randomly sample 500 images per concept from the retrieval set for training.

ImageNet100 is a subset of ImageNet [Russakovsky et al., 2015] with only 100 classes. We follow the settings from [Cao et al., 2017] and randomly select 100 classes. All the validation images from 100 classes are used as query set while 13K images are randomly sampled from the retrieval set which consists of 128K images.

Our approach is implemented in PyTorch [Paszke et al., 2019], and we used pretrained AlexNet [Krizhevsky et al., 2012] from PyTorch as the initialization and replaced the classification fully-connected layer with a hashing layer consisting of K channels to represent K bits.

3.2 Ablation Study of Marginm

The margin is pre-set m ≥ 1 for Lemma 1 to hold. As shown in Figure 5, the margin essentially determines the magnitudes of polarization between positive and negative outputs i.e. large margins push the outputs v further away from zero, and vice versa.

Specifically, m = 1 results in the bit-wise hinge loss i.e. max(1 - vi · ti, 0). This form of loss function has long been studied in Support Vector Machine (SVM) for binary classification, as well as has been applied to deep neural networks to replace the cross-entropy loss [Tang, 2013]. Nevertheless, the hinge loss was defined over the dot product of network weights and input features, instead of channel wise outputs in our case. Empirically, we found that m = 1 does give rise to the most accurate results while other values of m are suboptimal (see Table 2). Unless stated otherwise, m = 1 is used for all experiments illustrated below.

3.3 Hashing

Hashing accuracies measured by mAP (mean average precision), for different methods are summarized in Table 3. Specifically, four existing methods i.e. HashNet [Cao et al., 2017], MIHash [Cakir et al., 2019], GreedyHash [Su et al., 2018] and JMLH [Shen et al., 2019] are compared with four variants of DPNs. DPN denotes the basic deep polarization network with random assignment of target vectors, and DPNA denotes DPN with adaptive updating of target vectors (see Section 2.4). DPN-T denotes DPN outputs processed with ternary assignment illustrated in Section 3.3 and DPN-A-T is the combinatorial of both aforementioned variants.

It was observed that the hash accuracies achieved by DPN is comparable with the-state-of-the-art, e.g. on ImageNet100 datasets, achieving 0.729 and 0.732 with 64 and 128-bits hash codes, respectively. DPN also slightly outperformed the best performed JMLH on the multi-labeled NUS-Wide dataset, with 1.9% improvement for 64-bits. For 16-bits, however, DPN performances slightly deteriorate, due to the decreased of averaged Hamming distances between target vectors as indicated by (Eq. 7) in Section 2.2.

Although adaptive updating of target vectors reflect intrinsic similarities between classes, as shown in Figure 4, its performances do not consistently improve the random assignment results. Moreover, the adaptive updating actually lead to unstable results for multi-labeled NUS-Wide images. Exploring more stable and effective adaptive updating strategy is one of our future research.

Ternary Assignment

As shown in Figure 5, wrongly retrieved samples often lead to non-polarized outputs. This observation inspired us to adopt an effective ternary assignment as follows:

Hamming distance between a K-bits ternary code ¨b and binary code t is defined as Dh(¨b, t) := 1 2 (K - ¨b · t).

After applying this minor modification to our network outputs, the resulting accuracies of DPN-T are consistently levitated above the-state-of-the-art, by elevations more than 2% for both ImageNet100 and NUS-wide datasets. While for CIFAR10, DPN-T compared favorably with respect to GreedyHash but not as good as that of JMLH 2 . Finally, the adaptive updating for DPN-A-T does not bring about consistent improvements as compared to DPN-T.

4 Conclusions

We proposed a novel learning to hash deep neural network, which uses a differentiable hinge-like loss to enforce polarization of each output channel. Contributions of the proposed DPN are three-folds. On the theoretical side, we proved that the proposed polarization loss is intrinsically related to the intra-class and inter-class Hamming distances between similar/dissimilar pairs. We advocate the polarization loss due to its simplicity and differentiability, which allows direct backpropagation to optimize the network weights. Algorithmwise, a simple random assignment strategy for each class of target binary codes turns out to be surprisingly effective and it achieves the state-of-the-art performances. Finally, a ternary assignment is proposed to consistently levitate hashing accuracies by improvements more than 2% for most cases.

2 We are unable to reproduce the results of JMLH.

Applying channel-wise hinge-like loss is proved to be a simple and effective strategy for hashing in this paper. As one future research direction, we are exploring an effective adaptive updating of target vectors. Other topics within this deep polarization network (DPN) framework, e.g. ternary assignments, call for more research efforts from colleagues interested in DPNs.

Acknowledgements

This work is partially supported by the National Key Research and Development Program of China 208AAA0101100.