Redundancy-resistant Generative Hashing for Image Retrieval

1 Introduction

Image retrieval aims to retrieve relevant images to a given query image from a very large image corpus. Due to the huge amount of computation and storage cost required for similarity evaluation in the original feature space, the core problem in this area has been how to re-represent each image using sufficiently compact codes while preserving the original similarity structure as more as possible.

Learning to hash (LTH) [Wang et al., 2017] is a popular kind of techniques developed for the aforementioned approximate nearest neighbor search problem. By using binary hash codes to represent the original data, the storage cost can be dramatically reduced. Furthermore, search with such binary representations can be efficiently conducted because (1) we can perform Hamming distance computation that is supported via POPCNT on modern CPU/GPU; and (2) we can achieve a constant or sub-linear time complexity for search by using hash codes to construct an index [Kong and Li, 2012].

∗Corresponding author

Since the expressiveness of the learned hash codes can directly affect the final retrieval performance, improving code quality by capturing preferred properties of the hash function is a long-standing topic in LTH studies. Supervised hashing [Xia et al., 2014], semi-supervised hashing [Wang et al., 2012; Zhu et al., 2016], and cross-modal hashing [Jiang and Li, 2016] achieve this goal by assuming the images are labeled or tagged, which requires many human efforts or even be unrealistic for modern applications. In contrast, unsupervised hashing methods do not utilize any semantic relations explicitly, and thus are more challenging to be effective in practice. Representative work along this line include spectral hashing [Weiss et al., 2008], isotropic hashing [Kong and Li, 2012], iterative quantization [Gong et al., 2013], Kmeans hashing [He et al., 2013], discrete graph hashing [Liu et al., 2014], spherical hashing [Heo et al., 2015], graph hashing [Jiang and Li, 2015], binary autoencoder (BAE) hashing [Carreira-Perpin´an and Raziperchikolaei, 2015], stochastic generative hashing (SGH) [Dai et al., 2017], etc. Among them, SGH and BAE enjoy the theoretical advantage of minimum description length (MDL) owing to their auto-encoding architecture. This property is critical to achieve not only fast but also accurate retrieval. Besides, due to its probabilistic nature, SGH avoids commonly used relaxation of the binary constraints (which often leads to inferior results) by optimizing probability distributions over discrete hash codes.

The apparent benefits claimed by SGH are inherited from the auto-encoding variational inference framework [Kingma and Welling, 2014; Rezende et al., 2014]. We note, however, that the MDL principle may be unsatisfied due to the prior constraints in this framework. In fact, recent studies show that such a variational autoencoder (VAE) framework suffers from the deficient usage of latent codes, i.e. there often exist many uninformative latent dimensions in the code space [Sønderby et al., 2016], especially when the decoder network is complex. This phenomenon is caused by the variational pruning [Hoffman, 2017; Yeung et al., 2017], a problem occurs when many latent units collapse early in training before they learned a useful representation.

In this paper, we design a new deep generative architecture which forces the latent hashing codes to not only reconstruct data through the generative (decoder) network but also retain minimal squared L2 difference to the output of the last realvalued decoder hidden layer. We show that such a constrained deep structure has the effect of simplifying the decoder while providing sufficiently good generation/reconstruction quality. A simplified decoder network together with a deep inference (encoder) network are expected to alleviate variational pruning and hence code redundancy. Furthermore, during posterior inference, we propose to regularize the standard autoencoding objective with an additional term that explicitly accounts for the negative redundancy degree of latent code dimensions. We interpret such modifications as Bayesian posterior regularization and design an adversarial strategy to optimize the generative, the variational, and the redundancyresistanting parameters. Experimental results show that our redundancy-resistant generative hashing framework can significantly boost the quality of learned codes and achieve stateof-the-art retrieval performance on image data sets.

2 Model

As a powerful unsupervised representation learning framework, VAE [Kingma and Welling, 2014; Rezende et al., 2014] defines a latent variable generative model as follows

where θ denotes the likelihood is parameterized by a decoder Deep Neural Network (DNN), and Z ∈ RK×N and X ∈ RD×N denote the latents and the observed data, respectively. Specifying qφ(Z|X) = ∏Ni=1 qφ(zi|xi) as the DNN-parameterized inference model (encoder), VAE seeks to maximize the evidence lower bound (ELBO) w.r.t. φ and θ

2.1 Stochastic Generative Hashing

As an instance of VAE, SGH [Dai et al., 2017] uses a linear Gaussian likelihood and imposes the Bernoulli prior on Z:

where ρ = [ρj]Kj=1 ∈ [0, 1]K . Correspondingly, the inference model is parameterized as

where φj(xi) = qφ(zij = 1|xi), and φj represents a scalarvalued linear or deep nonlinear transformation.

2.2 Redundancy-resistant Generative Hashing

To ensure efficient similarity search, we assume the latent hash code z of each data to be binary, thus our Redundancyresistant SGH (R-SGH) model shares the same Bernoulli prior p(Z) as in (1). Compared to SGH, one distinct feature of R-SGH lies in the new deep generative architecture for likelihood computation. Suppose the decoder DNN (generative network) has M+1 layers, where 1) the first layer is the hash code layer, which has prior p(Z) and is the latent variable of our Bayesian model; 2) the last layer is the data reconstruction layer, whose output is used to form the mean and covariance parameters of our Gaussian likelihood on data; and 3) the M-th layer is the last real-valued decoder hidden layer, whose output is denoted by H(M) = [h(M) i ]Ni=1 ). Our idea is to force Z to not only reconstruct data through the decoder network but also retain minimal squared L2 difference to the output of the M-th decoding layer. Thus we propose to add the regularization term-‖Z-H(M) ‖2F into the VAE objective, where ‖·‖F denotes the Frobenius norm of a matrix, and we assume z and h(M) have the same dimension.

Consider the extreme case that the above regularization term is perfectly optimized (Z exactly equals to H(M) ), i.e., the hash code layer is identical to the last decoder hidden layer, then our decoder model is equivalent to a single layer network. Thus, such a constrained deep structure has the effect of simplifying the decoder while providing sufficiently good generation/reconstruction quality. As studied in RNNbased variational language models [Yang et al., 2017], where the overly flexible LSTM decoder in VAE does not make effective use of the latent representation, a simplified decoder network together with a deep unconstrained inference (encoder) network are expected to alleviate variational pruning and hence code redundancy. For our R-SGH, we assume that the inference model has the same form as in (2), and φ is implemented by an encoder DNN (which transforms the input data into Bernoulli parameter for hash code through M hidden layers) with mirrored layer structure as the decoder.

Furthermore, during posterior inference, we propose to regularize the standard auto-encoding variational objective with an additional term that explicitly accounts for the negative redundancy degree of latent code dimensions. The key insight is that, if a latent dimension can be approximated by the linear combination of the other latent dimensions, then this dimension is useless for data generation. To eliminate such redundancy and encourage all latent dimensions to explain the data, we formulate our overall model as follows:

where A ∈ RK×K denotes a combination coefficient matrix. Intuitively, we always find the best possible combination coefficients to account for the redundancy degree of latent dimensions, and δ > 0 and η > 0 are regularization parameters that balance ELBO and redundancy-related terms.

Before we design specific adversarial algorithm to optimize θ, φ and A alternatingly, we first interpret the formulation in (3) as Bayesian posterior regularization [Zhu et al.,

Solving problem (4), we can get the posterior distribution

As a direct way to impose constraints or incorporate knowledge in Bayesian models, Bayesian posterior regularization is more natural and general than specially designed priors.

2.3 Adversarial Training

The VAE parameters θ, φ aim to maximize (3), while the redundancy-resistanting parameter A plays an adversarial role to minimize it. To optimize them in turn, we have to formulate each sub-problem separately.

Optimizing θ Given φ and A, problem (3) simplifies to

which is straightforward to solve utilizing the reparameterization trick introduced in [Dai et al., 2017]. Specifically, to deal with the discrete variational distribution, we use the Doubly Stochastic Neuron (DSN) that achieves the hash code variable by zij = f(φj(xi), ξj , εj), where ξj , εj ∼ U(0, 1) and

Hence, the objective in (5) can be rewritten as

where zi = f(φ(xi), ξ, ε) = [f(φj(xi), ξj, εj)]Kj=1 . Then it is similar as in the vanilla VAE to derive a Monte Carlo estimator for the gradient of the objective in (6) w.r.t. θ.

Optimizing φ Given θ and A, problem (3) simplifies to

which can also be solved using the reparameterization trick. However, we empirically note that such direct treatment often leads to poor performance since a optimum found this way is easily dominated by the first term. The underlying reason is that the ELBO is upper-bounded while the first term can be arbitrarily large. To this end, we introduce the ϵ-insensitive idea, and reformulate the problem as

where rk is the k-th column of R = Z⊤ - Z⊤A. Following [Dai et al., 2017], we employ the distributional derivative of DSN to derive the gradient of the objective in (8) w.r.t. φ.

Optimizing A Given φ and θ, problem (3) simplifies to

Applying the reparameterization trick again, we can solve this problem via gradient decent. Alternatively, here we show we can get an analytical solution by adding an extra term λ‖A‖2F to the objective, then (9) is converted into

where λ > 0. It can be shown that (10) can be solved in close-form [Lu et al., 2012] with

where D = Eqφ(Z|X) [(ZZ⊤ + λI)-1 ] and diag(A) denotes a vector with its i-th element being the i-th diagonal element of A. By setting λ > 0, ZZ⊤ +λI is ensured to be invertible. When λ → 0, (10) degenerates to (9).

Remarks To reasonably optimize (7) and (9), we alter the terms related to the redundancy-resistanting parameter A and optimize (8) and (10) instead. This leads to different overall objectives for maximization and the adversarial minimization. Inconsistent objectives during block coordinate descent/ascent may lead to instability and misconvergence of optimization. However, in our adversarial framework, we empirically didn't find this is a problem. As will be seen in Figure 1, our algorithm converges steadily. We conjecture that it is due to the equilibrium condition difference between adversarial training and maximum likelihood training.

2.4 Complexity Analysis

Using the gradient estimators of {θ, φ} and the analytical solution of A, the computational complexity of a single joint update of the parameters {θ, φ,A} for the proposed model is O( ˜NCnn + K3 ), where ˜N is the batch size during our mini-batch training, and Cnn is the cost of evaluating the encoder/decoder networks. After training, all parameters are frozen, and we are interested in encoding a query image to its hash code, a procedure of the same complexity O(Cnn) as other deep hashing methods.

3 Experiments

We evaluate the proposed method on two computer vision tasks: 1) Image generation/reconstruction on MNIST [Oliva and Torralba, 2001]; 2) Image retrieval on CIFAR10 [Krizhevsky, 2009] and Caltech-256 [Griffin et al., 2007].

3.1 Experimental Setup

Compared Methods (1) Spectral Hashing (SH) [Weiss et al., 2008]; (2) Iterative Quantization (ITQ) [Gong et al., 2013]; (3) PCA Hashing (PCAH), which projects the input via PCA and performs binarization according to the sign of each dimension; (4) Stochastic Generative Hashing (SGH) [Dai et al., 2017]; and (5) Deep-SGH, a variant of SGH that adopts DNN as the encoder and decoder.

Parameter Settings For the comparedmethods, we use the implementations provided by their authors (Deep-SGH is implemented directly based on SGH) and set the parameters according to their original papers. Without explicit statement, 1) for our R-SGH, the prior parameter ρj is set to 0.5 for any j ∈ {1, ..,K}, the threshold parameter ϵ is set to 0.05, and both δ and η are set to 0.01; and 2) for R-SGH and DeepSGH, the encoder and decoder network structures are set as [D-K-K-K] and [K-K-K-D] respectively, where D and K are the dimensions of input data and hash code respectively. Note, the 4-layer encoder and decoder share the same hash code layer, and all hidden layers have the same dimension.

Evaluation Metrics (1) L2 reconstruction error; (2) precision at S: the percentage of true relevant instances among top S retrieved ones; and (3) recall at S: the percentage of true relevant instances that are retrieved as the top S similar ones; (4) mean average precision (mAP), which computes the area under the entire precision-recall curve and evaluates the overall retrieval performance of different hashing algorithms. Note that, in evaluating these metrics for a given query image, we use a fixed small set of Euclidean nearest neighbors to the query as its ground-truth relevant images.

3.2 Performance Evaluation

Generation on MNIST To study the discriminative power of learned representations, we re-generate the images with 64 bit hash code on MNIST dataset. Specifically, we first randomly sample an x from the dataset and encode it into binary representation via the learned qφ(z|x), and then, we re-generate an artificial sample from pθ(x|z) by the mean.

We compare the proposed method with SGH. For fairness, we only consider the redundancy-resistant constraint on shallow network, where both the encoder and decoder are single layer neural network. The quantitative comparison is shown in Figure 1 where R-SGH achieves lower reconstruction error than that of SGH eventually, indicating that the hash codes of R-SGH contain richer information for reconstruction owing to their low redundancy merit. The visualization results are shown in Figure 2, which verify the advantage of our model again.

Image Retrieval on CIFAR-10 The CIFAR-10 dataset contains 60,000 color images from 10 object classes. Each original image is of size 32 × 32 and is represented as a 512D GIST feature vector [Oliva and Torralba, 2001]. Following the same setting as in [Erin Liong et al., 2015], we randomly sample 1000 samples, 100 per class, as the query data, and use the remaining 590,00 images as the gallery set.

The parameter δ in R-SGH is set to 0.1 on this dataset. For all considered methods, we repeat the experiments 20 trials and take the averages as the final results. Table 1 lists the mAP results of different hashing methods. Figure 3 shows the recall and precision curves as functions of the retrieved number of instances under different number of hash bits.

First, the clear advantages of our R-SGH over the other compared unsupervised hashing methods can be easily observed in terms of mAP performance, which demonstrate that our redundancy-resistant generative hashing framework can

consistently improve the overall retrieval performance. Second, R-SGH keeps a greater growth of mAP than that of SGH when increasing number of hash bits are used, this is because the redundancy-resistant terms in R-SGH can effectively activate the uninformative bit in the generative model. Third, R-SGH outperforms the other compared methods by a large margin when 128 bits of hash code are used. We attribute this to the fact that higher dimensional latent representations come with higher information redundancy. Finally, we note that SGH and ITQ achieve better recall and precision performances when 32 bits hash code are used. This is due to very little information redundancy contained in the hash code when the number of hash bits is small. In this case, the redundancy-resistant regularization influences the reconstruction procedure and may degrade the performance. Fortunately, if low redundancy is expected in advance, we can prevent the negative impact by setting a small threshold parameter ϵ.

Image Retrieval on Caltech-256 The Caltech-256 dataset consists of 29,780 images associated with 256 object categories. We randomly choose 1000 images as the query set and the rest of the dataset is regarded as the training set. We use the VGG network (VGG-fc7 [Szegedy et al., 2015]) pre-trained on ILSVRC [Russakovsky et al., 2015] as the feature extractor, which transforms each image into a 1024dimensional vector.

We followed the same settings as in the CIFAR-10 experiment and used the same DNN structures. Table 2 displays the mAP performance of different hashing methods on Caltech256 dataset. Figure 4 shows the precision-recall curves for different hashing methods under 32, 64 and 128 bits, respectively. We can see that R-SGH significantly outperforms the other compared methods on this dataset, even under 32 bits hash code. It is probably due to the well known fact that the CNN features their self have some information redundancy. The improvements of R-SGH also show that the negative influence of information redundancy is even greater than that caused by dimensionality reduction for image retrieval, hence R-SGH is more suitable for the CNN features or other information redundant features than the compared methods.

3.3 Sensitivity Analysis

For sensitivity analysis of the proposed model, we use the Caltech-256 data set to evaluate the influences of regularization parameters δ and η. Here, the number of hash bits for each image is fixed to 128. When η is fixed to 0.01, Figure 5 (a) shows the mAP performance of R-SGH with varying δ. When δ is fixed to 0.01, Figure 5 (b) shows the mAP performance of R-SGH with varying η.

It is worth to mention that R-SGH seems to be more sensitive to δ. Unsuitable δ can degrade the mAP performance severely, while η has little impact on the mAP in a relatively large range, i.e., [0.002, 0.07], as shown in Figure 5 (b). Both terms we proposed improves the discriminative power of the learned hash codes.

4 RelatedWork

Learning-based hashing is an effective solution to accelerate similarity search by designing compact binary codes in a low-dimensional space. To enhance the expressiveness of fixed-length hash codes, there already exist some hash learning methods that pursue the independence (or low redundancy) between the hash bits. For example, the iterative quantization method [Gong et al., 2013] maximizes the variance of each binary bit to keep the non-relevance and minimizes the binarization loss to obtain a high performance for image retrieval. Later, Liong et.al [Erin Liong et al., 2015] proposed to use a DNN to learn hash codes with three objectives: (1) the loss between the real-valued feature descriptor and the learned binary codes is minimized; (2) binary codes distribute evenly on each bit; and (3) different bits are as independent as possible. They pursue the independence between hash bits by constraining the weight matrix in the encoders to be high rank. A more recent work named DeepBit [Lin et al., 2016] learns compact binary code based on similar rules, i.e., minimal loss quantization, uncorrelated and evenly distributed bits. Bypassing quantization, our redundancy-resistant generative hashing method clearly differs from these methods.

Recent studies of VAEs for representation learning have revealed the decoupling phenomenon of latent code dimensionality from expressive power. Caused by the variational pruning [Hoffman, 2017; Yeung et al., 2017], this phenomenon can be seen as a virtue of automatic relevance determination if efficiency is not a problem (but it is not the case for hashingbased similarity search), but also as a problem when many units collapse early in training before they learned a useful representation. [Sønderby et al., 2016] observed that such units remain uninformative for the rest of the training, presumably trapped in a local minima or saddle point, with the optimization algorithm unable to re-activate them. In [Bowman et al., 2015; Sønderby et al., 2016], the authors used warm-up strategy to alleviate it by initializing training using the reconstruction error only. As more principled approaches, [Hoffman, 2017] proposed to learn a shared shearing matrix to rotate the variational distribution, and [Tomczak and Welling, 2017] proposed a "Variational Mixture of Posteriors" prior for the latent codes. The most similar strategy to ours is to restrict the power of the decoder by word dropout [Bowman et al., 2015], lossy coding [Chen et al., 2016] and dilated CNN [Yang et al., 2017]. Nevertheless, our adversarial learning framework is more general than these works.

5 Conclusion

We designed a new deep generative architecture which forces the latent hashing codes to not only reconstruct data through the generative network but also retain minimal difference to the last real-valued hidden layer of the network. Furthermore, during posterior inference, we proposed to regularize the standard auto-encoding variational objective with an additional term that explicitly accounts for the negative redundancy degree of latent code dimensions. We designed an adversarial strategy to optimize the generative, the variational, and the redundancy-resistanting parameters. Experimental results show that our redundancy-resistant generative hashing framework can significantly boost the quality of learned codes and achieve state-of-the-art retrieval performance on image data.

Acknowledgements

This work was supported by the National Natural Science Foundation of China (No. 61602449, 61672501, 61603372).