Natural Supervised Hashing

1 Introduction

Hashing has recently attracted considerable research efforts from machine learning, computer vision, information retrieval and related areas. Given a dataset, hashing methods generate binary codes that intend to preserve metric distances or semantic similarities of the original data. Due to the efficient computation of Hamming distance between binary codes, hashing is very suitable for large-scale ANN (approximate nearest neighbor) search. Compact hash codes can produce significant gains in both memory usage and search efficiency, maintaining reasonable accuracies at the same time.

Locality-Sensitive Hashing (LSH) [Gionis et al., 1999] is a well-known data-independent hashing method, which uses random projections to construct hash functions. It has continued to be a research interest in the past decade and efforts have been devoted to expand LSH to more distance metrics including lp distance [Datar et al., 2004] and kernel distance [Kulis and Grauman, 2009]. Due to theoretical guarantees that the original similarity is asymptotically preserved, LSH is a rather popular method in ANN search and usually long codes are used to obtain a good search precision. However, long codes would result in low recall. So in practical settings, LSH also requires multiple hash tables to achieve reasonable recall rate. Both long codes and multiple tables will increase memory usage and reduce search efficiency.

⇤ corresponding author

Unlike data-independent hashing which uses random prjections, data-dependent methods try to learn hash functions from training data. Data-dependent hashing can produce more compact binary codes and can usually achieve better accuracy even with much shorter codes. Due to this property, researchers have been putting a lot of efforts on designing good hash codes. Data-dependent hashing can be roughly divided into three categories: unsupervised, semi-supervised and supervised hashing.

Unsupervised hashing uses unlabeled data to train a set of hash functions, aiming at preserving the metric neighborhood (usually, l2 metric) of the original data. The representative of unsupervised hashing algorithms includes Spectral Hashing (SH) [Weiss et al., 2009], Iterative Quantization (ITQ) [Gong and Lazebnik, 2011], Isotropic Hashing (IsoH) [Kong and Li, 2012], Harmonious Hashing (HamH) [Xu et al., 2013] e.t.c. Among these methods, ITQ uses PCA projections as initialization, and then tries to find an orthogonal matrix which minimizes the quantization loss between binary codes and rotated points. Due to the structure-preserving property of rotation and minimization of quantization loss, ITQ has achieved state-of-the-art performance in unsupervised hashing methods. Recently, the idea of ITQ is also used in producing very long codes for high-dimensional features [Gong et al., 2013; Xia et al., 2015] and has shown promising results.

However, metric neighbors are not necessarily semantic neighbors. While unsupervised hashing achieves promising performance in preserving metric distances, in some applications we want ANN search to return semantic neighbors for a given query. This leads to (semi-)supervised hashing methods. In this paper, we focus on formulation and optimization of supervised hashing.

In contrast to unsupervised hashing whose training data is unlabeled, (semi-)supervised methods use labeled training data to learn semantic-similarity-preserving codes. The difference between semi-supervised and supervised hashing is that supervised methods use pure labeled data, while semisupervised hashing deals with the situation where only part of training data is labeled. The representatives of (semi)supervised hashing include Semi-Supervised Hashing (SSH) [Wang et al., 2012], Sequential Projection Learning Hashing (SPLH) [Wang et al., 2010], Binary Reconstructive Embedding (BRE) [Kulis and Darrell, 2009], Minimal Loss Hashing (MLH) [Norouzi and Blei, 2011], CCA-ITQ [Gong and Lazebnik, 2011], Kernel-based Supervised Hashing (KSH) [Liu et al., 2012], Ranking-based Supervised Hashing (RSH) [Wang et al., 2013], Graph Cut Coding (GCC) [Ge et al., 2014], Fast Hashing (FastH) [Lin et al., 2014], Supervised Discrete Hashing (SDH) [Shen et al., 2015] e.t.c. Research efforts have been devoted to several aspects in the literature, which we briefly discuss in the following text.

The first thing to consider is to define some criteria which express desired properties of target codes and guide the design of objective functions. Different algorithms are essentially different from each other on the criterion they are built upon. For example, BRE [Kulis and Darrell, 2009] utilizes pairwise similarity and intends to find binary codes which generate small Hamming distance for similar pairs and large distance for dissimilar ones. The idea of pairwise similarity is subsequently used by other methods (SSH, SPLH, KSH, GCC, FastH) and is now the most popular supervision form in the literature. Different from these approaches, CCA-ITQ and SDH utilize semantic labels of individual samples instead of pairwise similarity. To emphasize the difference, we call them pointwise in this paper. CCA-ITQ consists of two steps. It first uses CCA to find a common space for original features and labels such that in this space embeddings of features and labels have maximum correlation. Then a ITQ process is applied on the embedding of original feature and a rotation matrix is learned to minimize quantization loss just like the unsupervised case. CCA-ITQ relies on the CCA step to exploit supervised information and the correlation maximization is the key criterion. In contrast, the recently proposed SDH is more direct, which requires learnt binary codes to be good features for linear classification with given labels. And due to direct focus on binary codes and carefully designed optimization process, SDH has been reported to achieve state-ofthe-art results [Shen et al., 2015]. In this paper, we propose a new pointwise method which attempts to generate binary codes with close structure to label vectors. We show that our approach is even more direct than SDH and demonstrate its superiority on several datasets.

More complex hash functions are also an interest in the field. The most common hash function is linear projection followed by thresholding, which has been used by many methods. Afterwards, to deal with the situation where samples are not linearly separable, hash functions with kernels are proposed [Kulis and Darrell, 2009; Liu et al., 2012]. Kernelization has been proved able to boost the performance of supervised hashing methods, especially when we are using weak features. Recently, hashing methods based on deep neural networks are quite popular [Xia et al., 2014; Erin Liong et al., 2015]. These approaches have shown great improvement in performance since deep networks can learn much more complex nonlinear functions than a single kernel. In this paper, we choose linear projection and the kernelized version as hash functions. We do not use deep networks because we want to focus on the criterion of hash codes, i.e. design of loss functions. We think that our method can easily accommodate deep networks by changing hash functions to neural networks and modifying the update of projection matrix to update of network weights with back propagation.

In this paper, we investigate label vectors as binary codes for semantic similarity search. Inspired by its good performance, we try to learn hash codes with similar structure to label vectors. Because it is natural to use label vectors to encode semantic information, we dub the proposed approach Natural Supervised Hashing. Our contributions are as follows:

1. We formulate a novel objective function to learn hash codes which produce close inner products to label vectors. And to avoid direct optimization on big n⇥n Gram matrices, we identify an structure-preserving transformation to fill the dimensionality gap between target codes and label vectors. With this transformation, we could implicitly bring close inner products of hash codes and that of label vectors without explicit computation of Gram matrices.
2. We propose an alternating optimization method for our final objective, with each step having an analytical solution. The training process is very fast and scales well. On NUS-WIDE, training 16-bit and 96-bit code cost respectively only 3 and 6 minutes.

The remainder of the paper is organized as follows: section 2 presents the proposed approach and section 3 demonstrates the performance of our method compared with several stateof-the-art algorithms; we conclude the paper in section 4.

2 Natural Supervised Hashing

In this section, we present the objective function and learning algorithm.

2.1 Label vectors as binary codes

For dataset with l labels, the ideal way to encode xi for semantic search is using its label vector yi 2 ¶0↪ 1♦l as binary code. The j-th element in yi equals to 1 if sample i has label j, and is 0 otherwise. For single-label datasets, only one element in yi is 1 while there can be multiple 1s in multi-label cases. This simple code makes sense because the Hamming distance between each pair is just the number of different labels, which we call semantic distance.

However, we find that although labels are ideal to measure difference of semantic information between samples, it is not necessarily optimal in NN search 1 . This problem stems from inconsistencies between semantic distance and evaluation criteria. In evaluation we decide whether a pair is similar by counting the number of labels they share, i.e. inner product between labels. Due to this criterion, two samples with large semantic distance may be considered similar in experiments. For example, if we have yi = [1↪ 1↪ 1↪ 0]T and yj = [0↪ 1↪ 1↪ 1]T , we tend to determine sample i and sample j as similar because they share 2 labels when there are

1 It is indeed optimal for certain cases, like single-label datasets.

only 4. However the Hamming distance between i and j is Dh(yi↪ yj) = 2, which is not small in 4-bit code.

We believe the suboptimality is a problem with the evaluation criteria commonly adopted, not the label vectors, considering they are ground-truth semantic annotations. In fact, despite this problem, labels still give very good retrieval accuracy. On NUS-WIDE, label vectors achieve a 0▷772 mAP within top-5K retrieved samples, much higher than results obtained by state-of-the-art supervised hashing methods.

Inspired by its good performance, we intend to formulate an objective function and learn hash code from binary labels. Note that while label vector is of fixed length, our desired hash code may have varying number of bits.

2.2 Preserving inner product

We want our code to generate close Hamming distance to labels. Inspired by KSH [Liu et al., 2012], we do not directly work on Hamming distance and try to manipulate code's inner product instead. Unlike KSH which uses -1◁1 bit value during training, we use 0◁1 bit for simplicity.

Intuitively, to make inner product of labels and of target code as close as possible, we can write the objective as follows:

where X 2 Rn⇥d is training data, Y 2 ¶0↪ 1♦n⇥l is label matrix, and P 2 Rd⇥b contains project directions to learn. φ(·) is an elementwise function with φ(x) = 1 for x > 0 and φ(x) = 0 otherwise. This objective seeks directions that bring close two codes' inner product. However, we find it very hard to optimize due to the presence of φ(XP )φ(XP )T . Besides, the two large n⇥n matrices would take a lot of memory (for n = 50000, Y Y T needs about 9▷3 GB memory with single type). So for some large datasets, e.g. NUS-WIDE, which contains 269↪ 648 samples in total, we cannot utilize full training data in learning process.

To resolve these difficulties, we try to find a inner-productpreserving transformation, with which we can achieve the goal without explicit computation of Gram matrices. We observe that if a matrix R 2 Rl⇥m has orthonormal rows, i.e. RRT = Il, then we can get

i.e. YR generates the same Gram matrix as Y . The transformation R preserves Y 's structure. So besides minimizing the distance between φ(XP)φ(XP)T and Y Y T explicitly, we could minimize the distance between φ(XP ) and Y R instead, which brings close two Gram matrices implicitly.

The condition RRT = Il forces a dimensionality constraint: there should be less rows than columns in R. Due to this constraint, our final optimization problem has two cases:

• ÷ For b 6 l,
• ÷ For l < b,

We use R to fill the dimensionality gap between label vectors and target codes, preserving inner product at the same time.

2.3 Optimization

Our goal is to learn project directions P. We optimize the objective function in an alternating way, i.e. fixing P, optimize R and fixing R, update P . For different cases, we have different iteration steps.

For b 6 l

The objective function can be expanded as follows:

where const indicates a constant term that does not depend on either P or R.

• ÷ R step: Fixing P , the optimization problem of R is

This problem turns out to be a Procrustes problem with analytic solutions [Xia et al., 2015]. First we perform SVD Y T φ(XP ) = U⌃V T , where U is an l ⇥ l orthogonal matrix, ⌃ is an l ⇥ b matrix and V is an b ⇥ b orthogonal matrix. Then the solution is R = V ˆU T , where ˆU contains first b columns of U.

• ÷ P step: The problem of P is hard to optimize since the φ function is nonsmooth. Following the idea of SSH [Wang et al., 2012], we relax φ for easy optimization. The problem is now

After setting the gradient to zero, we get a closed-form solution

To prevent singularity, we can add a regularization term to the solution and obtain:

For l < b

The second case is quite similar. The objective function can be written as

The difference to the b 6 l case is minor.

• ÷ R step: For fixed P , the problem with respect to R reduces to

which is also a Procrustes problem. We do SVD φ(XP)T Y = U⌃V T . U is an b ⇥ b orthogonal matrix, ⌃ is an b ⇥ l matrix and V is an l ⇥ l orthogonal matrix. The solution is R = V ˆU T , where ˆU contains first l columns of U.

• ÷ P step: Again we relax φ and the optimization problem is:

After adding a regularizer, we get the solution

For both cases, alternating steps have analytic solutions, leading to fast optimization during training. Note that the term A = (XT X +λId)-1XT Y can be computed only once before iterating, and then P is updated by P = ART or P = AR.

Due to relaxation in P step, objective value may not decline after one iteration. Nevertheless, we find that search qualities do improve along iterations. Figure 1 shows mAP of 5K top-ranked samples on three datasets when we are training 64-bit code. Our result improves along iterations and converges quickly, showing the efficacy of the optimization process. The quick convergence is a result of strict constraints on R. In our experiments, we find that the two variables change little after first several iterations.

2.4 Kernelization

Kernlization is popular in supervised hashing literature. Given a kernel (·↪ ·), we randomly sample m (m < n) anchor points ¶x1↪ x2↪ ▷▷▷↪ xm♦ from training data. Then original data x 2 Rd can be transformed to k(x) = [(x1↪ x)↪ (x2↪ x)↪ ▷▷▷↪ (xm↪ x)]T 2 Rm and the kernelized data matrix is K 2 Rn⇥m. Then we can learn hash functions in the new space P 2 Rm⇥b . The optimization is exactly the same as above, only with φ(XP) replaced by φ(KP). In the experiments, we use RBF kernel because datasets are represented with weak features.

3 Experiments

We evaluate our method on 4 datasets: NUS-WIDE IAPRTC12 2 , ESPGAME 3 , MIRFLICKR25K 4 . For NUSWIDE [Chua et al., 2009], we use the 500 dimensional bagof-words vectors provided by the authors. For the other three, we use the 512 dimensional GIST features provided by [Guillaumin et al., 2010]. Each dataset is split into a database and a query set. Statistics of datasets are given in table 1.

We compare the proposed NSH against six state-of-theart hashing algorithms, including unsupervised LSH [Datar et al., 2004], PCA-ITQ [Gong and Lazebnik, 2011], and supervised BREs [Kulis and Darrell, 2009], KSH [Liu et al., 2012], CCA-ITQ [Gong and Lazebnik, 2011] and SDH [Shen et al., 2015]. BREs indicates the supervised version of BRE. We kernelize the data for all supervised methods, including CCA-ITQ for fair comparion. The kernel we choose is RBF (x↪ y) = exp(♣♣x - y♣♣◁σ2 ) , where σ is set to an appropriate value. 1000 anchors are sampled from databases for all datasets except MIRFLICKR25K, for which we use only 500 anchors considering it is not large-scale and contains less labels.

In supervised methods, BREs and KSH construct a n ⇥ n pairwise similarity matrix to learn hash codes. This matrix takes much memory (9▷3 GB for n = 50000) thus we cannot use all available labeled data for training. Besides, when n is large, training time needed for BREs and KSH is prohibitive. Therefore, we randomly sample 5000 points from databases as training sets for BREs and KSH. In contrast, CCA-ITQ, SDH and our NSH have better scalability and are trained with the whole database. In experiments, we give NSH 50 training iterations and set λ = 10-4 for all cases.

2 http://www.imageclef.org/photodata

3 http://www.hunch.net/⇠jl/

4 http://press.liacs.nl/mirflickr/

We also evaluate two baselines. One is direct linear search with original features, denoted as l2. The other is training a linear SVM on kernelized data for each label. And when received a query, a binary code is first generated with trained SVMs, and then it is used to search through databases of labels. We choose Pegasos [Shalev-Shwartz et al., 2011] as our SVM for its fast training speed and small memory consumption.

We follow two search procedures: hamming ranking and hash lookup. Hamming ranking measures search quality through ranking database points according to their Hamming distance to queries and calculating precision, recall and mean Average Precision (mAP) in top-ranked samples. Hash lookup finds database points within a given Hamming radius of queries and calculates precision and recall in retrieved samples. Note that we treat failing to find any samples for a query as zero precision. All our results are obtained on a laptop with Intel Core i5-3210M 2.50 GHz and 12 GB RAM.

3.1 Results on NUS-WIDE

NUS-WIDE is sparsely labeled, with each sample associated with 1▷87 labels on average. We choose NUS-WIDE for its large scale and determine a pair as ground-truth similar if they share at least one label. Training time of evaluated methods is given in table 2, from which we see that NSH costs much less time than BREs, KSH and it scales well when bits increase, while the training cost of SDH seems to be linear with bits. Evaluation results are presented in table 3. We see that NSH consistently attains best mAP and precision within radius 2 under different number of bits, and the margin between NSH and the second best SDH is not small. Considering recall within radius 2, NSH again outperforms other hashing methods. The baseline svm attains high recall@2 because SVMs are trained with much less positive samples than negative samples and tend to predict all zero binary codes, which has a small Hamming distance from sparse labels. This can be inferred from the low precision@2.

3.2 Results on IAPRTC12 and ESPGAME

IAPRTC12 and ESPGAME are also sparsely labeled, with each sample associated with respective 5.72 and 4.69 labels on average. We choose the two datasets because they contain much more labels than NUS-WIDE, 291 for IAPRTC12 and 268 for ESPGAME, leading to a more difficult problem. In evaluation, a pair is determined as similar if they share at least one label. Experimental results are given in table 4. We see that NSH consistently achieves best performance from 8 bits to 128 bits on both datasets, with improvements over other methods ranging from 2% to 5%. The baseline svm considers each label separately and does not take the whole structure into account, resulting in even worse performance than unsupervised hashing methods.

3.3 Results onMIRFLICKR25K

We further evaluate NSH and competitive methods on MIRFLICKR25K, which contains less samples and labels (only 38) than NUS-WIDE. We adopt MIRFLICKR25K because it is more densely labeled, with each sample having 4.72 labels on average, and so we can use more strict similarities. In our experiments, we determine a pair as similar if they contain at least three common labels, making the task challenging in another aspect. Overall results are presented in table 5. Again, NSH attains the best performance with varying number of bits, demonstrating the effectiveness of the proposed method. More detailed results are given in figure 2, where we plot Hamming ranking precision of top-ranked samples under 16, 32 and 64 bits. KSH, CCA-ITQ, and SDH attain close results while NSH surpasses them by a notable margin.

4 Conclusion and future work

In this paper we propose a novel supervised hashing method Natural Supervised Hashing and show its superior performance on 4 image datasets. We attribute the success of NSH to the inner-product-preserving objective. We find that although labels are not optimal binary codes under commonly adopted evaluation criteria, it still gives impressive results on preserving semantic neighborhoods. Inspired by its good performance, we intend to formulate an objective function so that our learnt code can generate close inner product to label vectors. To enable more easy optimization and circumvent large n ⇥ n matrices, we manage to find a transformation which preserves inner products of each pair and so we can use it to bring close labels and our code without explicit computation on inner products. In the end, our objective takes two cases and both can be optimized in an alternating way. We optimize the objective with Procrustes solution and relaxation, leading to efficient learning process. In experiments, NSH consistently surpasses compared methods and attains best results in all 4 benchmark datasets, indicating the efficacy of the objective and learning method. In the end, we think that our method can still be improved, e.g. by utilizing more complex hash functions like neural networks. We intend to look in this direction in our future work.

5 Acknowledgements

This work is supported by NSFC (No. 61272247, 61533012, 61472075), the 863 National High Technology Research and Development Program of China (SS2015AA020501) and the Major Basic Research Program of Shanghai Science and Technology Committee (15JC1400103).