Deep Recurrent Quantization for Generating Sequential Binary Codes

1 Introduction

With the significant increase of the mass media contents, image retrieval has become the highly-concerned spot. Image retrieval concentrates on searching similar images from largescale database. The direct way is to use reliable kNN (knearest neighbor) techniques, which usually perform bruteforce searching on database. ANN (approximate nearest neighbor) search is an optimized algorithm which is actually practicable against kNN search. The main idea of ANN search is to find a compact representation of raw features i.e. a binary code with fixed length, which can retain structure of raw feature space and dramatically improve the computation speed.

∗Contact Author

Recently, hashing methods have been widely used in ANN search. They usually learn a hamming space which is refined to maintain similarity between features [Liu et al., 2016; Zhu et al., 2016; Song et al., 2018c; Song et al., 2018b; Song et al., 2018a]. Since the computation of hamming distance is super fast, hashing methods have huge advantages on ANN search. However, hashing methods lack accuracy on feature restoration. Methods based on quantization require a codebook to store some representative features. Therefore, the main goal of quantization is to reserve more information of feature space in codebook. Then, they try to find a combination of codewords to approximate raw features and only to store indexes of these codewords.

Quantization is originated from k-means algorithm, which first clusters data points and uses the clustering centers as codebook. Each data point is represented by index of its corresponding center. In order to decrease computation cost of k-means, product quantization [Jegou et al., 2011] and optimized product quantization [Ge et al., 2013] split whole feature space into a set of sub-regions and perform similar algorithm on each subspace respectively. Such initial quantization methods construct restrictions and well-designed codebooks to accelerate calculation. In the deep learning era, people proposed some end-to-end deep neural networks to perform image feature learning and quantization together. Deep quantization network [Cao et al., 2016] use AlexNet to learn wellseparated image features and use OPQ to quantize features. Deep visual-semantic quantization [Cao et al., 2017] and deep triplet quantization [Liu et al., 2018] quantize features by CQ. Different from these works, product quantization network [Yu et al., 2018] proposed a differentiable method to represent quantization as operations of neural network, so that gradient descent can be applied to quantization. Despite their successes, PQ and its variants have several issues. First, to generate binary codes with different code lengths, a retraining is usually unavoidable. Second, it is tricky for the decomposition of high-dimensional vector space. Different decomposition strategies may result in huge performance differ- Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)

ences. To tackle these issues, we propose a deep quantization method called deep recurrent quantization, which constructs codebook that can be used recurrently to generate sequential binary codes. Extensive experiments show our method outperforms state-of-the-art methods even though they use larger codebooks.

2 Preliminaries

Quantization-based image retrieval tasks are defined as follows: Given a set of images I ∈ {0, 1, · · · , 255}N×H×W×C which contain N images of height H, width W and channel C. We first use a CNN, e.g. AlexNet and VGG to learn a hyper representation X ∈ RN×D of images, where D is the dimension of feature vectors. Then we apply quantization on these feature vectors, to learn a codebook C ∈ RK×D which contains K codewords and each of them has D dimensions. Feature vectors are then compressed to compact binary codes B ∈ {0, 1}N×L where L indicates the code length.

2.1 Integrate Quantization To Deep Learning Architectures

During the procedure of quantization, to pick a closest codeword from feature representation is to compute the distance between codewords and features and find the minimum one, which can be described as:

where x are the features of a data point, and Ck is the kth codeword, ˆQ(x) is quantization function and ˆq is quantized feature. Therefore, ˆq is the approximation of x. Meanwhile, we collect the index of codeword as the quantized code, which is described as:

Since b is in the range of 0 ∼K-1, then all the codes can be binarized to a code length of log2K. Then, the original feature x can be compressed to an extremely short binary code.

However, the formulation of codeword is nondifferentiable, i.e. ∂ˆq ∂C does not exist. It cannot be directed integrated into deep learning architectures. To tackle this issue, we use a convex combination of codewords to approximate features, which is defined as follows:

Here, pk(x) indicates the confidences of each codewords w.r.t. x, i.e. the closer one codeword Ck is to a feature x, the higher pk(x) will be. Then, ˆq is approximated by ˜q, which is the weighted sum of all codewords. We define ˆQ(x) as hard quantization and ˜Q(x) as soft quantization.

3 ProposedMethod

The whole network architecture of our deep recurrent quantization (DRQ) is demonstrated in Fig. 1. DRQ contains two main parts: feature extraction module and quantization module. In feature extraction module, we apply intermediate supervision on top of CNN, to guide the learning of semanticembedded visual features. In quantization module, we design a recurrent quantization block and integrate it into deep learning architecture which can be trained end-to-end.

3.1 Intermediate Supervision for Features

To get the feature representation of images, we use AlexNet to extract features from the last linear layer. To leverage the clustering performance i.e., to let the images with the same label have higher similarity and vice versa, we apply two losses with intermediate supervision. Specifically, we first collect a triplet in dataset which contains an anchor image I o , a positive sample I + and a negative sample I - w.r.t. anchor (for multi-label images, we define a positive image as one which shares at least one label with anchor, and a negative image as one which does not share any label with an anchor), and feed them into AlexNet to obtain the 4096-d features from fc7 layer. Then we add two linear layers fc8 of 1748-d and fc9 of 300-d. We concatenate fc8 and fc9 to get a final feature x of 2048-d. Since we feed the triplet into the network, the output features are represented as xo , x+, x-.

We apply two supervised objective function on these layers: 1) Adaptive margin loss ℓs, which is from DVSQ [Cao et al., 2017] and applied to fc9 outputs of triplet, and 2) Triplet loss ℓt defined to final feature x, which is a concatenated feature of fc8 and fc9. ℓs is defined as:

Triplet loss ℓt can adjust features to adapt to clustering, which uses the triplet of xo , x+, x-. It is defined as:

3.2 Recurrent Quantization Block

In recurrent quantization model, we adopt a shared codebook that contains K codewords. We denote the level of quantization code as M, which indicates how many iterations the codebook is reused. For each level, we pick a proper codeword as the approximation of feature vectors, and we take the index of picked codeword as the quantization code. For example, if we set K = 256,M = 4, the index range of each level quantization code is 0 - 255, represented as a binary code of log2K=8 bits. The total length of quantization code is M × log2 K = 4×8 = 32. The position 0-7 is the index of first level codeword, 8 - 15 is the index of second level, etc. Therefore, the feature vector can be approximated by a combination of a few codewords in the codebook.

As we described in Sec. 2.1, to perform a quantization, input x and codebook C are necessary. Output is the code b. Inspired by the hierarchical codebooks in stacked quantizer [Martinez et al., 2014], we observe the residual of x can be used as an input to the next quantizer. Therefore, a basic idea is to perform quantization step-by-step:

Specifically, ˆqm is quantized feature explained above, and r1 , r2 , · · · , rM-1 are residuals of x. We put rm to the next quantization to get the qm+1 which approximates rm. Therefore, ∑m qm can be described as an approximation of x, which is much preciser than ˆ q1 . Notice that processing of qm is similar. If we use a shared codebook, the computation in Eq. 7 can be rewritten recurrently:

And the soft and hard quantization of hm-1 is defined as:

The unfolded structure of recurrent quantization is depicted in Fig. 2. Here, h0 ,C0 is the raw features and initial codebook. w is a shared learnable parameter with random initialization. In iteration m, we compute bm to find the best-fitted codeword, then we use Cm, bm, hm to compute residual of hm and treat residual as next input hm+1 . Since the residual is one or more order of magnitudes lower than hm, the next input should be much smaller than codewords in codebook, so we use w ∈ R as a scale factor to adjust the norm of codebook in order to fit the new input. In next iteration m+1, we use the scaled codebook Cm+1 to complete another similar computation. Finally, we learn a codebook C, a scale factor w and sequential binary codes b0 , b1 , · · · , bM . The hard and soft quantization of x can be computed as:

By reusing codebook C, we can reduce the number of parameters by M times.

Objective Function

Since ˆq(x) and ˜q(x) are approximation of feature x, we define a distortion error as:

where Em h is the distortion error between ˆqm and x at iteration m and Em s is the distortion error between ˜qm and x. We sum distortions for each level and the total distortion error is:

We also design a joint central error Ej to align Eh and Es:

3.3 Optimization

In DRQ, there are two main losses: 1) ℓt and ℓs which refine features, 2) Eh, Es, Ej , which control the quantization effectiveness. We split the training procedure into three stages. Firstly, we minimize ℓt, ℓs together to pre-train our preceding neural network. Then, we add recurrent quantization block into network but only perform one recurrent iteration i.e. set M = 1 and optimize ℓt, ℓs,Eh,Es,Ej together. This is to get an initial codebook which are optimized for short binary codes. Finally, we set M to a specified value and optimize the whole network with all losses, until it converges or we reach the max number of training iterations.

4 Experiments

To validate the effectiveness and efficiency of our adopted deep recurrent quantization, we perform extensive experiments on three public datasets: CIFAR-10, NUS-WIDE and ImageNet. Since existing methods use different settings, to make a thorough comparison with them, we follow these works and compare with them using separate settings. We implement our model with Tensorflow, using a pre-trained AlexNet and construct intermediate layers on top of the fc7 layer. Meanwhile, we randomly initialize codebook with specified M and K, which will be described below. We use Adam optimizer with lr = 0.001, β1 = 0.9, β2 = 0.999 for training.

4.1 Comparison Results Using Setting 1

Settings

We first conduct results and make comparisons with stateof-the art methods on two benchmark datasets: CIFAR-10 and NUS-WIDE. CIFAR-10 is a public dataset labeled in 10 classes. It consists of 50,000 images for training and 10,000 images for validation. We follow [Yu et al., 2018] to combine the training and validation set together, and randomly sample 5,000 images per class as database. The remaining 10,000 images are used as queries. Meanwhile, we use the whole database to train the network. NUS-WIDE is a public dataset consisting of 81 concepts, and each image is annotated with one or more concepts. We follow [Yu et al., 2018] to use the subset of 195,834 images from the 21 most frequent concepts. We randomly sample 1,000 images per concept as the query set, and use the remaining images as the database. Furthermore, we randomly sample 5,000 images per concept from the database as the training set. We use mean Average Precision (mAP@5000) as the evaluation metric.

Results

On CIFAR-10, we compare our DRQ with a few state-ofthe-art methods, including DRSCH [Zhang et al., 2015], DSCH [Zhang et al., 2015], DSRH [Zhao et al., 2015], VDSH [Zhang et al., 2016], DPSH [Li et al., 2015], DTSH [Li et al., 2015], DTSH [Wang et al., 2016], DSDH [Li et al., 2017] and PQNet [Yu et al., 2018], using 16, 24, 36, 48 bits. We set M = 4 and K = 2 LM = 16, 64, 512, 2048. The results on CIFAR dataset are shown in Table 1. Results show our network achieves comparable mAP performance against state-of-the-art methods, i.e. PQNet. Our mAP is only 0.3%- 0.5% lower than PQNet. Results also show our performance is stable with variable bit-lengths. Our method only get 0.1% decrease when bit-length shrinks to 16 bits. Noticed that our recurrent quantization only use a single codebook with K codewords, and therefore our method requires much less parameters compared with other methods, as shown in Tab. 4.

On NUS-WIDE dataset, we compare our method with a few shallow and deep methods. Shallow methods include SH [Salakhutdinov and Hinton, 2009], ITQ [Gong et al., 2013], LFH [Zhang et al., 2014], KSH [Liu et al., 2012], SDH [Shen et al., 2015], FASTH [Lin et al., 2014]. Deep methods include NINH [Lai et al., 2015a], DHN [Zhu et al., 2016], DQN [Cao et al., 2016], DPSH [Li et al., 2015], DTSH [Wang et al., 2016], DSDH [Li et al., 2017] and PQNet [Yu et al., 2018]. The results are generated in 12, 24, 36, 48 bits. We fix K = 2048,M = 4 to generate 48 bits codes, and then slice these codes to get shorter binary codes. The results are shown in Table 2. On NUS-WIDE, our method achieves the highest mAP compared with stateof-the-art methods when the code length is longer than 12 bits. Noticed that our method uses a shared codebook for all code lengths, and it is trained once.

The codebook size w.r.t. code-length comparison between multiple methods is shown in Tab. 4. Our method obtains the smallest codebook size compared with the other methods. Also, to generate binary codes with different lengths, our methods is trained once.

4.2 Comparison Results Using Setting 2

Setting

Following DTQ [Liu et al., 2018], on CIFAR-10, we combine the training and validation set together, and randomly select 500 images per class as the training set, 100 images per class as the query set. The remaining images are used as the database. On NUS-WIDE, we use the subset of 195,834 images from the 21 most frequent concepts. We randomly sample 5,000 images as the query set, and use the remaining images as the database. Furthermore, we randomly select 10,000 images from the database as the training set. On ImageNet, we follow [Cao et al., 2017] to randomly choose 100 classes. We use all the images of these classes in the training set as the database, and use all the images of these classes in the validation set as the queries. Furthermore, we randomly select 100 images for each class in the database for training. We compare our method with 11 classical hash or quantization methods, including 5 shallow methods: ITQCCA [Gong et al., 2013], BRE [Kulis and Darrell, 2009], KSH [Liu et al., 2012], SDH [Shen et al., 2015] and SQ [Martinez et al., 2014], and 6 deep architecture: CNNH [Xia et al., 2014], DNNH [Lai et al., 2015b], DHN [Zhu et al., 2016], DSH [Liu et al., 2016], DVSQ [Cao et al., 2017], DTQ [Liu et al., 2018].

Results

We use mAP@54000 on CIFAR-10 and mAP@5000 on NUS-WIDE and ImageNet. We use 8, 16, 24, 32-bits codes by setting M = 4,K = 256. We also use precision-recall curve and precision@R (returned results) curve to evaluate the retrieval quality. The results are shown in Table 3, Fig. 3 and Fig. 4.

It can be observed that: 1) Our DRQ significantly outperforms the other methods in CIFAR-10 and NUS-WIDE datasets. Specifically, it outperforms the best counterpart (DTQ) by 1.8%, 3.5%, 4.2% and 4.5% on CIFAR-10, and by 1.2%, 1.7% and 2.0% on NUS-WIDE dataset. DRQ is outperformed by DTQ on NUS-WIDE for 8-bit codes. The possible reason is that in DRQ, codebooks are shared by different code lengths, and may lose some accuracy especially for short binary codes. On ImageNet, our method is outperformed by DTQ, which may be caused by the random selection. Also, our DRQ requires much less parameters than DTQ, and our model is only trained once. 2) With the increase of code length, the performance of most indexing methods is improved accordingly. For our DRQ, the mAP increased by 3.4%, 7.3% and 3.6% for CIFAR-10, NUS-WIDE and ImageNet dataset respectively. This verifies our DRQ can generate sequential binary codes to gradually improve accuracy. 3) The performances of precision-recall curves for different methods are consistent with their performances of mAP. The precision curves represent the retrieval precision with respect to number of return results.

4.3 Ablation Study

In this subsection, we study the effect of each part in our architecture using the following settings. 1) Unsupervised quantization: we use raw fc7 output without additional fc8, fc9. 2) Remove Ls: we remove fc9 and Ls, and change fc8 to 2048-d and apply Lt on it directly, to validate the role of Ls. 3) Remove Lt: we remove fc9 and Lt and change fc8 to 300-d with Ls, to validate the role of Lt. 4) ˜q only: we remove the construction of ˆq and associated losses, to validate the role of ˆq. 5) Remove Ej : we remove Ej to validate the effectiveness of joint central loss. 6) Intermediate supervision: we use only fc9, which is 300-d and also apply Lt to fc9, to validate effectiveness of the concatenation of fc8, fc9. We perform ablation study on NUS-WIDE and show results in Tab. 5. In general, DRQ performs the best, and 'Remove ℓs' ranks the second. By removing ℓs, the supervision information is still utilized in ℓt, so mAP drop is not that significant. The unsupervised architecture also achieves good results, indicating the validity of pretrained AlexNet. Notice that if we remove any of the objective functions in the structure, mAP will have a huge loss. This indicates the effectiveness of each part of our DRQ. We get the worst result when we remove the concat, this may be of the significant information loss in 300-d features.

4.4 Qualitatively Results

To qualitatively validate the performance of quantization methods, we also perform t-SNE visualization on DTQ, DVSQ and DRQ, and show the results in Fig.5. Visualizations are created on CIFAR-10, we randomly sample 5,000 images from database and adopt 32 bits quantized features. Our DRQ has a similar performance to DTQ, and they both show distinct clusters in their visualization, which is much better than DVSQ. Our unsupervised structure also has a promising performance since data points are concretely clustered. However, some of the data points with different labels are wrongly clustered together. This indicates the importance of supervision information.

5 Conclusion

In this paper, we propose a Deep Recurrent Quantization (DRQ) architecture to generate sequential binary codes. When the model is trained once, a sequence of binary codes can be generated and the code length can be easily controlled by adjusting the number of recurrent iterations. A shared codebook and a scalar factor is designed to be the learnable weights in the deep recurrent quantization block, and the whole framework can be trained in an end-to-end manner. Experimental results on the benchmark datasets show that our model achieves comparable or even better performance compared with the state-of-the-art for image retrieval, but with much less parameters and training time.

Acknowledgements

This work is supported by the Fundamental Research Funds for the Central Universities (Grant No. ZYGX2014J063, No. ZYGX2016J085), the National Natural Science Foundation of China (Grant No. 61772116, No. 61872064, No. 61632007, No. 61602049).