Learning Deep Unsupervised Binary Codes for Image Retrieval

1 Introduction

With the explosive growth of large volume and high dimensional multimedia data like images and videos, efficient largescale visual retrieval has received growing attention [Li et al., 2015; Gong et al., 2013]. Hashing, one of the approximate nearest neighbors (ANN) retrieval methods [Andoni and Indyk, 2006], has been widely used in many applications such as image retrieval, due to its computation efficiency and low storage cost. It maps high dimensional data into compact binary codes, where semantically similar items can be indexed by similar binary codes. Existing hashing methods can roughly be divided into two categories: data-independent hashing and data-dependent hashing [Cao et al., 2016; Gong et al., 2013]. It has been shown that the data-dependent methods achieve better performance than the data-independent ones, e.g. Locality Sensitive Hashing(LSH) [Datar et al., 2004]. In this paper, we focus on data-dependent methods to learn binary codes for efficient image retrieval.

Many data-dependent hashing methods have been proposed to learn efficient binary codes for the retrieval task [Cao et al., 2016; Gong et al., 2013; Li et al., 2015; Liu et al., 2011; Zhang et al., 2017; Duan et al., 2017; Erin Liong et al., 2015; Lin et al., 2016; Huang et al., 2017; Do et al., 2016]. These hashing methods can be further divided into supervised hashing and unsupervised hashing. While supervised methods make use of provided labels to mitigate the gap between highlevel semantic and low-level feature representation of items, the performance is always hindered by the availability of supervision information. This is especially challenging when deep models are considered as a large amount of labeled data is typically needed for the training. As it is much easier to collect a high volume of unlabeled data, deep unsupervised hashing learning methods become attractive. Deep unsupervised hashing learns multiple hierarchical transformations to capture the nonlinear manifold structure of data [Erin Liong et al., 2015]. While some kernel-based methods [Liu et al., 2012] have been developed for the hashing task, they are however not scalable.

Among the existing deep unsupervised hashing methods proposed for image retrieval [Duan et al., 2017; Erin Liong et al., 2015; Lin et al., 2016; Huang et al., 2017], most of them make use of a simple quadratic constraint to minimize the difference between the compact representations and the target binary codes during the training, which inevitably causes severe information loss and thus produces suboptimal binary codes. Also, as discussed in [Cao et al., 2016; Ge et al., 2014], to quantize all input vectors effectively with vector quantization (VQ) [Gray, 1984], the data should exhibit a clustering structure. Hence it is also important to learn the image representations so that such a clustering structure can be resulted.

In this paper, we propose an unsupervised deep hashing model called DeepQuan (Deep Quantization) to address the aforementioned problems. Our contributions can be summarized as follows:

• Instead of forcing the outputs of the deep network to be binary using a quadratic constraint, we propose to generate binary codes with product quantization (PQ) [Jegou et al., 2011; Ge et al., 2014]. To the best of our knowl-

edge, the proposed model DeepQuan is the first attempt to incorporate PQ into a deep model to learn binary code in an unsupervised way. This model is built upon a deep autoencoder, and an alternating optimization method is proposed for the model learning. By optimizing the objective function, more discriminative feature representations (i.e. a more discriminative clustering structure) can be obtained so that PQ can quantize the feature vectors more effectively.

• To avoid trivial solutions and poor generalization, we propose a novel weighted triplet loss to learn more discriminative features and demonstrate its effectiveness empirically.
• Experimental results on two standard datasets (i.e. CIFAR-10 and MNIST) show that DeepQuan outperforms the existing deep unsupervised methods and achieves the state-of-the-art performance in the image retrieval application.

The rest of the paper is organized as follows. In Sec. 2, we introduce some related work. Details of the proposed DeepQuan are described in Sec. 3 The experimental results and discussion are presented in Sec. 4. Sec. 5 concludes the paper with future research directions.

2 RelatedWork

Unsupervised hashing methods exploits the intrinsic manifold structure of the input data to achieve the hashing objective. For example, Spectral Hashing (SH) [Weiss et al., 2009] was proposed to learn the hash codes by solving a spectral graph partitioning problem. Iterative Quantization (ITQ) obtains the hash codes by imposing an orthogonal transformation matrix to minimize the quantization loss [Gong et al., 2013]. K-means Hashing (KMH) tries to index every quantized codeword with a binary code so that the distance between them is minimized [He et al., 2013].

With the recent progress of deep learning [Simonyan and Zisserman, 2014], many deep hashing methods have been proposed. Some deep supervised hashing methods like Deep Pairwise Supervised Hashing (DPSH) [Li et al., 2015] and Deep Quantization Network (DQN) [Cao et al., 2016] have achieved the state-of-the-art results on many benchmarks. There are also deep unsupervised hashing methods proposed. For example, Deep Hashing (DH) [Erin Liong et al., 2015] builds hierarchical neural networks to learn the binary codes. DeepBit [Lin et al., 2016] and Unsupervised Triplet Hashing (UTH) [Huang et al., 2017] learn the hashing functions with data argumentation. Binary Deep Neural Network (UHBDNN) [Do et al., 2016] was developed by maintaining a discrete binary constraint during training. DBD-MQ [Duan et al., 2017] obtains the hash codes by using K-AutoEncoders network to minimize the reconstruction errors.

Different from the previously proposed deep unsupervised hashing methods, our proposed DeepQuan utilizes the product quantization method to generate binary codes. It simultaneously refines the clustering structure and preserves the data manifold. Furthermore, the proposed weighted triplet loss helps to avoid trivial solutions and poor generalization. We show that our method achieves the state-of-the-art performance on two public datasets for the image retrieval application. For more evaluation results, readers can refer to https://github.com/chenjunjie1994/IJCAI-18.

3 Methodology

In this section, we describe the proposed DeepQuan in detail. We use bold lowercase letters like x to indicate vectors and uppercase letters like X to denote matrices. ‖ · ‖2 and ‖ · ‖0 denote L2 and L0 norms respectively. Given a training set with N image feature vectors X = {xi}Ni=1 , where xi denotes the D-dimensional feature vector of the ith image. The unsupervised hashing problem is defined as learning a mapping function f : x ↦→ h ∈ {0, 1}B , which encodes a feature vector into a B-bit binary vector, so that the pairwise similarity in the original feature space is preserved as much as possible.

Our proposed model DeepQuan is built upon a deep autoencoder network, and the whole architecture is shown in Fig. 1. It accepts feature vectors (i.e., hand-crafted features or deep features) as inputs, and consists of three components: (1) a stack of fully-connected layers used as an encoder to map high-dimensional inputs to low-dimensional compact representations; (2) a symmetric decoder for preserving the manifold structure within data; (3) a proposed weighted triplet loss on low-dimensional representations for training the deep model and learning the binary codes.

3.1 Model Formulation

The model configuration of our deep network follows the setting of [Xie et al., 2016]. It is a symmetric architecture, in which both the encoder and decoder consist of five fully connected layers but reversed to each other. Each fully connected layer learns a nonlinear mapping zli = αl (W l zl-1 i + bl ), where zli is the lth hidden representation of input data xi, W l and bl are the weight and bias parameters of the lth layer respectively. The activation functions for all the layers except the last fully-connected layer are rectifier units (ReLU) α(x) = max(0, x). Unless otherwise specified, we use zi, f(·) and g(·) to represent the middle hidden representation of xi, the encoder and the decoder respectively in the rest of the paper.

Weighted Triplet Loss We employ product quantization (PQ) to generate binary codes from the middle hidden representation zi ∈ RL by minimizing the quantization error. Product quantization is one special case of vector quantization (VQ), where any codeword is taken from the Cartesian product of M sub-codebooks [Ge et al., 2014]. Thus, we first decompose the representation zi into M parts zi = [zi1, zi2, . . . , ziM]T , where zim ∈ RL/M is the subvector related to mth subspace. In each subspace, K codewords can be generated using K-means clustering to quantize all the subvectors {zim}Ni=1 . Finally, there will be KM codewords in total. The way to measure the quantization error, as adopted in [Cao et al., 2016], can take a quadratic form, given as:

where Cm denotes the codebook associated with the mth subspace. The codebook Cm is composed of K codewords Cm = [Cm1,Cm2, . . . ,CmK], where Cmk ∈ RL/M . The constraint indicates that him is a one-hot K-dimensional binary vector, which means each subvector is represented by only one codeword. Following [Ge et al., 2014; Cao et al., 2016; Long et al., 2016], to represent each data point xi with a compact binary vector, each him is compressed into one log2K-bit vector, with which the final binary vector is the concatenation of M log2K-bit vectors. In other words, the length of hash codes B = Mlog2K. For all the experiments we conduct, we set K = 256. Each component thus is represented with 8 bits.

One can simply take Eq. (1) as the objective function and alternatively optimize it with respect to zi and Cm to learn the deep model. However, the result will not be desirable. We conducted a preliminary experiment and found that all the inferred codewords within a codebook are more or less the same as indicated by the average distance among them shown in Fig. 2(a). This indicates that the hidden representations zi do not exhibit an obvious clustering structure for the product quantization to leverage on. We further confirm this by visualizing the learned feature space in Fig. 3.

To promote the clustering structure to be inferred for the hidden representations, we propose a novel weighted triplet loss that takes all the codewords (i.e., clusters) into consideration instead of only the assigned codewords to learn zi during the training. This is to allow more discriminative clustering structure to be obtained. In particular, the proposed weighted triplet loss is formulated as:

where C + i = [C + i1 , C + i2 . . . C + iM ] and C - i = [C - i1 , C - i2 . . .C - iM ] denote the concatenations of all positive and negative codewords respectively. Here, positive codewords are defined as the cluster centers to which zim is assigned via K-means clustering. Negative codewords are defined as those cluster centers to which zim is not assigned. In our experiments, we also define a parameter s which can be interpreted as the "margin" between the positive and the negative codewords. Negative codewords are generated by randomly sampling.

Compared with the simple quadratic loss in Eq. (1) which only considers the relation with positive codewords, our proposed weighted triplet loss simultaneously enlarges the distance between negative codewords C - i and zi so that a discriminative clustering structure can be obtained, which will further benefit the quantization process. We add a weighting parameter λ ∈ (0, 1) to the negative term in Eq. (2) to control the emphasis on learning discriminative representations zi.

Manifold Preserving Loss To ensure that the hidden representation zi can well recover the data manifold in the original feature space , we employ a decoder to define the regularization term formulated as follows:

where xi is the input feature vector and g(·) denotes the decoder network.

Overall Objective We formulate the overall objective function for model training as:

where θ denotes the parameters of the deep neural network, and η is a trade-off parameter to control the balance between feature discrimination and reconstruction quality so as to lead to better generalization.

3.2 Approximate Nearest Neighbor Search

For testing, given a new query point xq, we compute a symmetric distance between xq and the data points xi in the image database based on the inferred binary codes {hi}Ni=1 and the codebooks C for the retrieval. Specifically, we adopt the one used in [Jegou et al., 2011], defined as:

To compute that, we first precompute the distance look-up table of size K × K between the codewords. Thus, there will be M K × K look-up tables altogether. With the M pre-computed look-up tables, the distance SD(xq, xi) can be efficiently computed by summing up the codeword distance values directly obtained from the look-up tables. It is only slightly more costly than computing the Hamming distance [Jegou et al., 2011].

Note that the distance computed with Eq. (5) is an approximation of the Euclidean distance between xq and xi. As discussed in [Jegou et al., 2011], we show that the error is statistically upper bounded by the quantization error.

Theorem 1. The statistical error between the approximated distance SD(xq, xi) and the Euclidean distance d(xq, xi) is upper bounded as :

Proof. The upper bound can be derived by simply using the triangle inequality:

3.3 Alternating Optimization

We propose to optimize Eq. (4) in an alternating way. We learn the compact representation z , the codebooks C, and the binary codes h iteratively until convergence.

LearningModel Parameters θ and z Standard back propagation (BP) is adopted to update the model parameters θ and z. We simply take the gradient of the objective function Lθ with respect to z as follows:

where 1{s - (λ‖zi - C - i ‖2 - ‖zi -C + i ‖2)} is an indicator function which will return 1 if s - (λ‖zi - C - i ‖2 - ‖zi - C + i ‖2) > 0, and 0 otherwise. To optimize the deep model, we back propagate the gradient ∂zi ∂θ through the chain rule and update the parameters θ using the gradient descent method.

LearningC andh As shown inTheorem1, the quality (i.e. measured by quantization error) of codebooks C has crucial impact on the final retrieval performance. By minimizing the quantization error, we can obtain the optimal codebooks C. For the mth subspace, we have

and the estimated values of C and h are obtained using Kmeans following [Jegou et al., 2011]. In our implementation, we update the codebook C and h every epoch. As Eq. (4) tries to drive the hidden features to have a clustering structure, the updating of the cookbook for each cluster will eventually be only affected by the hidden representations assigned to it, but not the others. This makes the alternating optimization to converge. Fig. 2(b) shows that the objective function Eq. (4) converges as the training proceeds.

4 Experimental Results

To evaluate the performance of our proposed DeepQuan method for image retrieval, we conduct extensive experiments on two publicly available datasets. The details of the experiments and the results are described in the following subsections.

4.1 Datasets and Experimental Setting

To make our performance comparison consistent with some recent related work [Lu et al., 2017; Huang et al., 2017; Erin Liong et al., 2015], we here conduct our experiments on two widely used benchmark datasets: CIFAR-10 and MNIST.

CIFAR-10 The CIFAR-10 dataset consists of 60, 000 labeled color images in 10 classes. Each class contains 6, 000 images of size 32 × 32.

MNIST The MNIST dataset contains 70, 000 gray-scale images in 10 classes of digits from "0" to "9". Each image is of size 28 × 28.

To demonstrate the effectiveness of the proposed DeepQuan model, we compare it with several state-of-the-art unsupervised hashing methods including: DH [Lu et al., 2017; Erin Liong et al., 2015], DeepBit [Lin et al., 2016], DBDMQ [Duan et al., 2017], UH-BNN [Do et al., 2016], UTH [Huang et al., 2017], ITQ [Gong et al., 2013], KMH [He et al., 2013], SH [Weiss et al., 2009], LSH [Datar et al., 2004], AGH [Liu et al., 2011], Spherical [Heo et al., 2012], PCAH [Wang et al., 2012]. For the comparison on dataset MNIST, we follow the setting of DH [Lu et al., 2017; Erin Liong et al., 2015]. Specifically, we randomly sample 1, 000 images (100 images per class) to form the test set (i.e., queries) and take the rest 69, 000 images as the training set and the gallery database. Each image is represented by a

784-D gray-scale feature vector with the pixel values as its elements. For the experiments on the dataset CIFAR-10, we put them under two categories according to the input feature vector being used. Following the settings of DH and UHBNN, we compare DeepQuan with those methods whose inputs are 512-D GIST [Oliva and Torralba, 2001] feature vectors extracted from the raw images, including DH, UH-BNN, ITQ, KMH, SH, LSH, AGH, Spherical and PCAH. We denote the CIFAR-10 dataset with these features as CIFAR-10GIST. For the CIFAR-10-GIST dataset, again 1, 000 images (100 images per class) are randomly sampled as the query data. The rest 59, 000 images are used as the training set. For fair comparison with the other deep models (i.e., DeepBit, DBD-MQ, UTH) with raw pixel images as the input and using convolutional neural network (CNN) for feature learning, we extract 7th fully-connected layer from the deep VGG16 [Simonyan and Zisserman, 2014] network as the feature vector inputs for our model. This VGG-16 model is also used in DBD-MQ [Duan et al., 2017] as part of the model. We denote this dataset as CIFAR-10-CNN, where 10, 000 images are sampled as the query set and the rest 50, 000 images are used for training.

Following [Xie et al., 2016], we configure our model as a deep autoencoder with the number of unit of encoder as [D-500-500-2000-L], where D and L are the dimensions of the input vector and the middle hidden layer respectively. The dimension L is essentially the length of binary codes, specifically L = 16M as [Cao et al., 2016]. The trade-off parameter η = 1.0 is adopted for all the experiments. Also, we have tested the cases empirically with s = 1.0, 1.0, 0.001 and λ = 0.1, 0.2, 0.2 for the datasets MNIST, CIFAR-10-CNN and CIFAR-10-GIST respectively. As adopted in most of the related work, the mean average precision (MAP) is used to measure the retrieval performance. For the performance of the existing methods, we make direct reference to the results reported in the corresponding papers. For our model, we report the average performance of 10 trials. We first pre-train the basic deep autoencoder using the training set. Then, we initialize the network accordingly and then further train the model by optimizing Eq. (4) as explained in Section 3.3. We set the batch size as 512 and the learning rate as 0.01 for the stochastic gradient descent. We found that around 3, 500 iterations are enough for the model to converge.

4.2 Performance Comparison

In this subsection, we present the results of performance comparison between DeepQuan and the state-of-the-art methods. The MAP results on MNIST and CIFAR-10-GIST datasets are listed in Table 1. We can find that our DeepQuan method outperforms the state-of-the-art methods by a large margin, especially under the short-bit settings. For example, for the 16-bit experiment of MNIST, DeepQuan outperforms the second best method UH-BNN by about 15%. In Table 2, we show the results evaluated on CIFAR-10-CNN. Compared with deep unsupervised CNN models which take raw pixels images as inputs, DeepQuan also achieves the best performance. Noted that the MAP value is computed on the whole database for MNIST while it is computed on the top 1, 000 returned samples for CIFAR-10-GIST and CIFAR-10CNN (as what being adopted in [Erin Liong et al., 2015; Duan et al., 2017]), which are denoted by MAP@All and MAP@1000 respectively. We believe that these large-margin improvements are due to the capability of the product quantization design incorporated into the deep model to preserve well the underlying data manifold.

4.3 Empirical Analysis of DeepQuan

To better understand how different parts of the proposed DeepQuan contribute to the overall improved performance, we conduct additional experiments. We make use of the datasets MNIST and CIFAR-10-CNN for this set of experiments, and 1, 000 images are sampled from each dataset to form a query set with the rest for training.

To evaluate the effectiveness of the proposed unified framework to learn both discriminative and compact hidden representations and product quantization in DeepQuan, we conduct experiments with relatively shorter bit-length (8 bits and 16 bits), and compute the hidden representations and the product quantization differently. In particular, we run product quantization [Jegou et al., 2011] directly on the original feature vectors, and on the feature vectors extracted from the pre-trained deep autoencoder, denoted as PQ and DAEPQ respectively. The results are reported in Table 3. DeepQuan achieves the best performance. In other words, it learns more discriminative compact features which in turn can ensure more effective quantization.

Next, to evaluate the effectiveness of the proposed weighted triplet loss (Eq. (2)) as compared with the standard quadratic loss (Eq. (1)), we conduct experiments by trying variants of the overall objective function. We tried the following settings: (i) We drop the reconstruction term (i.e. η = 0) and train the model by minimizing only Eq. (1) (denoted as Quad); (ii) We drop the reconstruction term and train the model by minimizing Eq. (2) (denoted as WTPs). As shown in Table 4, Quad gives the worst performance that is anticipated, and then followed by WTPs. DeepQuan considering all the reconstruction term during the training achieves the best results. We further demonstrate that the use of the weighted triplet loss can end up with a much more discriminative clustering structure. Fig. 3 visualizes the hidden features learned from MNIST under 32-bit setting .For 32-bit setting, the hidden representation zi is decomposed into 4 subspaces, each of which is expected to learn K = 256 clusters. Figs. 3(a) and 3(b) show the first two feature spaces learned using the quadratic loss with Eq. (3) as the manifold preserving term denoted as Quad-R, while Figs. 3(c) and 3(d) show the first two feature spaces learned with DeepQuan. It can be seen that the features learned with Quad-R are mixed, but the features learned with DeepQuan exhibit a discriminative clustering structure which benefits the subsegment quantization process.

(c) DeepQuan: 1st subspace (d) DeepQuan: 2nd subspace

Figure 4: Parameters sensitivity analysis.

4.4 Parameters Sensitivity Analysis

Fig. 3 shows the effect of changing the values of the hyperparameters s and λ. The experiments are conducted for varying one parameter at a time while fixing the other. All the results reported are under the 64 bits setting. We can find that DeepQuan can achieve competitive results within the range of 0.001 ≤ λ ≤ 0.2 and 0.001 ≤ s ≤ 1.0 compared with the existing unsupervised hashing methods.

5 Conclusions

In this paper, we propose a novel deep unsupervised method DeepQuan to learn binary codes. In contrast with existing unsupervised hashing methods, the intrinsic data manifold can be better preserved through the integration of product quantization and deep models in an unified framework. Experimental results on two widely used datasets show that our method outperforms the existing state-of-the-art models for image retrieval. An empirical analysis is also conducted to illustrate the effectiveness of the proposed weighted triplet loss in achieving discriminative hidden representations. For future work, we will explore the model with convolution neural networks where features can be directly learned from the raw images to further improve the retrieval accuracy.