Generative Semantic Hashing Enhanced via B oltzmann Machines (2020)

Abstract: Generative semantic hashing is a promising technique for large-scale information retrieval thanks to its fast retrieval speed and small memory footprint. For the tractability of training, existing generative-hashing methods mostly assume a factorized form for the posterior distribution, enforcing independence among the bits of hash codes. From the perspectives of both model representation and code space size, independence is always not the best assumption. In this paper, to introduce correlations among the bits of hash codes, we propose to employ the distribution of Boltzmann machine as the variational posterior. To address the intractability issue of training, we first develop an approximate method to reparameterize the distribution of a Boltzmann machine by augmenting it as a hierarchical concatenation of a Gaussian-like distribution and a Bernoulli distribution. Based on that, an asymptotically-exact lower bound is further derived for the evidence lower bound (ELBO). With these novel techniques, the entire model can be optimized efficiently. Extensive experimental results demonstrate that by effectively modeling correlations among different bits within a hash code, our model can achieve significant performance gains.

## introduction similarity search, also known as nearest-neighbor search, aims to find items that are similar to a query from a large dataset. it plays an important role in modern information retrieval systems and has been used in various applications, ranging from plagiarism analysis @xcite to content-based multimedia retrieval @xcite , etc. however, looking for nearest neighbors in the euclidean space is often computationally prohibitive for large-scale datasets (calculating cosine similarity with high-dimensional vectors is computationally-expensive). semantic hashing circumvents this problem by representing semantically similar documents with compact and binary codes. accordingly, similar documents can be retrieved by evaluating the hamming distances of their hash codes much more efficiently. to obtain similarity-preserving hash codes, extensive efforts have been made to learn hash functions that can preserve the similarity information of original documents in the binary embedding space @xcite . existing methods often require the availability of label information, which is often expensive to obtain in practice. to avoid the use of labels, generative semantic hashing methods have been developed. specifically, the variational autoencoder (vae) is first employed for semantic hashing in @xcite , and their model is termed vdsh. as a two-step process, the continuous document representations obtained from vae are directly converted into binary hash codes. to resolve the two-step training problem, bernoulli priors are leveraged as the prior distribution in nash @xcite , replacing the continuous gaussian prior in vdsh. by utilizing straight-through (st) technique @xcite , their model can be trained in an end-to-end manner, while keeping the merits of vdsh. recently, to further improve the quality of hash codes, mixture priors are investigated in bmsh @xcite , while more accurate gradient estimators are studied in doc2hash @xcite , both under a similar framework as nash. due to the training-tractability issue, the aforementioned generative hashing methods all assume a factorized variational form for the posterior, e.g., independent gaussian in vdsh and independent bernoulli in nash, bmsh and doc2hash. this assumption prevents the models from capturing dependencies among the bits of hash codes. although uncorrelated bits are sometimes preferred in hashing, as reported in @xcite , this may not apply to generative semantic hashing. this is due to the fact that the independent assumption could severely limit a model's ability to yield meaningful representations and thereby produce high-quality hash codes. moreover, as the code length increases (to e.g. 128 bits), the number of possible codes (or simply the code space) will be too large for a dataset with limited number of data points. as a result, we advocate that correlations among bits of a hash code should be considered properly to restrict the embedding space, and thus enable a model to work effectively under a broad range of code lengths. to introduce correlations among bits of hash codes, we propose to adopt the boltzmann-machine (bm) distribution @xcite as a variational posterior to capture various complex correlations. one issue with this setting, relative to existing efficient training methods, is the inefficiency brought in training. to address this issue, we first prove that the bm distribution can be augmented as a hierarchical concatenation of a gaussian-like distribution and a bernoulli distribution. using this result, we then show that samples from bm distributions can be well reparameterized easily. to enable efficient learning, an asymptotically-exact lower bound of the standard evidence lower bound (elbo) is further developed to deal with the notorious problem of the normalization term in boltzmann machines. with the proposed reparameterization and the new lower bound, our model can be trained efficiently as the previous generative hashing models that preserve no bit correlations. extensive experiments are conducted to evaluate the performance of the proposed model. it is observed that on all three public datasets considered, the proposed model achieves the best performance among all comparable models. in particular, thanks to the introduced correlations, we observe the performance of the proposed model does not deteriorate as the code length increases. this is surprising and somewhat contrary to what has been observed in other generative hashing models. ## preliminaries generative semantic hashing in the context of generative semantic hashing, each document is represented by a sequence of words @xmath0, w 2 , • • • , w |x| }, where w i is the i-th word and is denoted by a |v |-dimensional one-hot vector; |x| and |v | denotes the document size (number of words) and the vocabulary size, respectively. each document x is modeled by a joint probability: inference probabilistic models can be trained by maximizing the log-likelihood log p θ (x) with p θ (x) = s p θ (x, s)ds. however, due to the intractability of calculating p θ (x), we instead optimize its evidence lower bound (elbo), i.e., one key requirement for efficient end-to-end training of generative hashing method is the availability of reparameterization for the variational distribution q φ (s|x). for example, when q φ (s|x) is a gaussian distribution as in (4), a sample s from it can be efficiently reparameterized as with ∼ n (0, i). when q φ (s|x) is a bernoulli distribution as in (5), a sample from it can be reparameterized as with these reparameterization tricks, the lower bound in (3) can be estimated by the sample s as ## correlation-enhanced generative semantic hashing in this section, we present a scalable and efficient approach to introducing correlations into the bits of hash codes, by using a boltzmann-machine distribution as the variational posterior with approximate reparameterization. ## related work semantic hashing @xcite is a promising technique for fast approximate similarity search. locality-sensitive hashing, one of the most popular hashing methods @xcite , projects documents into low-dimensional hash codes in a randomized manner. however, the method does not leverage any information of data, and thus generally performs much worse than those data-dependent methods. among the datadependent methods, one of the mainstream methods is supervised hashing, which learns a function that could output similar hash codes for semantically similar documents by making effective use of the label information @xcite . different from supervised methods, unsupervised hashing pays more attention to the intrinsic structure of data, without making use of the labels. spectral hashing @xcite , for instance, learns balanced and uncorrelated hash codes by seeking to preserve a global similarity structure of documents. self-taught hashing @xcite , on the other hand, focuses more on preserving local similarities among documents and presents a two-stage training procedure to obtain such hash codes. in contrast, to generate highquality hash codes, iterative quantization @xcite aims to minimize the quantization error, while maximizing the variance of each bit at the same time. among the unsupervised hashing methods, the idea of generative semantic hashing has gained much interest in recent years. under the vae framework, vdsh @xcite was proposed to first learn continuous the documents' latent representations, which are then cast into binary codes. while semantic hashing is achieved with generative models nicely, the twostage training procedure is problematic and is prone to result in local optima. to address this issue, nash @xcite went one step further and presented an integrated framework to enable the end-to-end training by using the discrete bernoulli prior and the st technique, which is able to estimate the gradient of functions with discrete variables. since then, various directions have been explored to improve the performance of nash. @xcite proposed to employ the mixture priors to improve the model's capability to distinguish documents from different categories, and thereby improving the quality of hash codes. on the other hand, a more accurate gradient estimator called gumbel-softmax @xcite is explored in doc2hash @xcite to replace the st estimator in nash. more recently, to better model the similarities between different documents, @xcite investigated the combination of generative models and ranking schemes to generate hash codes. different from the aforementioned generative semantic hashing methods, in this paper, we focus on how to incorporate correlations into the bits of hash codes. ## conclusion in this paper, by employing the distribution of boltzmann machine as the posterior, we show that correlations can be efficiently introduced into the bits. to facilitate training, we first show that the bm distribution can be augmented as a hierarchical concatenation of a gaussian-like distribution and a bernoulli distribution. then, an asymptoticallyexact lower bound of elbo is further developed to tackle the tricky normalization term in boltzmann machines. significant performance gains are observed in the experiments after introducing correlations into the bits of hash codes.