Title: BINARY PARAGRAPH VECTORS

Abstract: Recently Le & Mikolov described two log-linear models, called Paragraph Vector, that can be used to learn state-of-the-art distributed representations of documents. Inspired by this work, we present Binary Paragraph Vector models: simple neural networks that learn short binary codes for fast information retrieval. We show that binary paragraph vectors outperform autoencoder-based binary codes, despite using fewer bits. We also evaluate their precision in transfer learning settings, where binary codes are inferred for documents unrelated to the training corpus. Results from these experiments indicate that binary paragraph vectors can capture semantics relevant for various domain-specific documents. Finally, we present a model that simultaneously learns short binary codes and longer, real-valued representations. This model can be used to rapidly retrieve a short list of highly relevant documents from a large document collection.

1. INTRODUCTION:

One of the significant challenges in contemporary information processing is the sheer volume of available data. Gantz & Reinsel (2012) , for example, claim that the amount of digital data in the world doubles every two years. This trend underpins efforts to develop algorithms that can efficiently search for relevant information in huge datasets. One class of such algorithms, represented by, e.g., Locality Sensitive Hashing (Indyk & Motwani, 1998) , relies on hashing data into short, localitypreserving binary codes (Wang et al., 2014) . The codes can then be used to group the data into buckets, thereby enabling sublinear search for relevant information, or for fast comparison of data items.

In this work we focus on learning binary codes for text documents. An important work in this direction has been presented by Salakhutdinov & Hinton (2009) . Their semantic hashing leverages autoencoders with sigmoid bottleneck layer to learn binary codes from a word-count bag-ofwords (BOW) representation. Salakhutdinov & Hinton demonstrated that semantic hashing codes used as an initial document filter can improve precision of TF-IDF-based retrieval. Learning from BOW, however, has its disadvantages. First, word-count representation, and in turn the learned codes, are not in itself stronger than TF-IDF. Second, BOW is an inefficient representation: even for moderate-size vocabularies BOW vectors can have thousands of dimensions. Learning fullyconnected autoencoders for such high-dimensional vectors is impractical. Salakhutdinov & Hinton restricted the BOW vocabulary in their experiments to 2000 most frequent words.

Recently several works explored simple neural models for unsupervised learning of distributed representations of words, sentences and documents. Mikolov et al. (2013) proposed log-linear models that learn distributed representations of words by predicting a central word from its context (CBOW model) or by predicting context words given the central word (Skip-gram model). The CBOW model was then extended by Le & Mikolov (2014) to learn distributed representations of documents. Specifically, they proposed Paragraph Vector Distributed Memory (PV-DM) model, in which the central word is predicted given the context words and the document vector. During training, PV-DM learns the word embeddings and the parameters of the softmax that models the conditional probability distribution for the central words. During inference, word embeddings and softmax weights are fixed, but the gradients are backpropagated to the inferred document vector.

In addition to PV-DM, Le & Mikolov studied also a simpler model, namely Paragraph Vector Distributed Bag of Words (PV-DBOW). This model predicts words in the document given only the document vector. It therefore disregards context surrounding the predicted word and does not learn word embeddings. Le & Mikolov demonstrated that paragraph vectors outperform BOW and bagof-bigrams in information retrieval task, while using only few hundreds of dimensions. These models are also amendable to learning and inference over large vocabularies. Original CBOW network used hierarchical softmax to model the probability distribution for the central word. One can also use noise-contrastive estimation (Gutmann & Hyvärinen, 2010) or importance sampling (Cho et al., 2015) to approximate the gradients with respect to the softmax logits.

An alternative approach to learning representation of sentences has been recently described by Kiros et al. (2015) . Networks proposed therein, inspired by the Skip-gram model, learn to predict surrounding sentences given the center sentence. To this end, the center sentence is encoded by an encoder network and the surrounding sentences are predicted by a decoder network conditioned on the center sentence code. Once trained, these models can encode sentences without resorting to backpropagation inference. However, they learn representations at the sentence level but not at the document level.

In this work we present Binary Paragraph Vector models, an extensions to PV-DBOW and PV-DM that learn short binary codes for text documents. One inspiration for binary paragraph vectors comes from a recent work by Lin et al. (2015) on learning binary codes for images. Specifically, we introduce a sigmoid layer to the paragraph vector models, and train it in a way that encourages binary activations. We demonstrate that the resultant binary paragraph vectors significantly outperform semantic hashing codes. We also evaluate binary paragraph vectors in transfer learning settings, where training and inference are carried out on unrelated text corpora. Finally, we study models that simultaneously learn short binary codes for document filtering and longer, real-valued representations for ranking. While Lin et al. (2015) employed a supervised criterion to learn image codes, binary paragraph vectors remain unsupervised models: they learn to predict words in documents.

2. BINARY PARAGRAPH VECTOR MODELS:

The basic idea in binary paragraph vector models is to introduce a sigmoid nonlinearity before the softmax that models the conditional probability of words given the context. If we then enforce binary or near-binary activations in this nonlinearity, the probability distribution over words will be conditioned on a bit vector context, rather than real-valued representation. The inference in the model proceeds like in Paragraph Vector, except the document code is constructed from the sigmoid activations. After rounding, this code can be seen as a distributed binary representation of the document.

In the simplest Binary PV-DBOW model (Figure 1 ) the dimensionality of the real-valued document embeddings is equal to the length of the binary codes. Despite this low dimensional representationa useful binary hash will typically have 128 or fewer bits -this model performed surprisingly well in our experiments. Note that we cannot simply increase the embedding dimensionality in Binary PV-DBOW in order to learn better codes: binary vectors learned in this way would be too long to be useful in document hashing. The retrieval performance can, however, be improved by using binary codes for initial filtering of documents, and then using a representation with higher capacity to rank the remaining documents by their similarity to the query. Salakhutdinov & Hinton (2009) , for example, used semantic hashing codes for initial filtering and TF-IDF for ranking. A similar document retrieval strategy can be realized with binary paragraph vectors. Furthermore, we can extend the Binary PV-DBOW model to simultaneously learn short binary codes and higher-dimensional realvalued representations. Specifically, in the Real-Binary PV-DBOW model (Figure 2 ) we introduce a linear projection between the document embedding matrix and the sigmoid nonlinearity. During training, we learn the softmax parameters and the projection matrix. During inference, softmax weights and the projection matrix are fixed. This way, we simultaneously obtain a high-capacity representation of a document in the embedding matrix, e.g. 300-dimensional real-valued vector, and a short binary representation from the sigmoid activations. One advantage of using the Real-Binary PV-DBOW model over two separate networks is that we need to store only one set of softmax parameters (and a small projection matrix) in the memory, instead of two large weight matrices.

Additionally, only one model needs to be trained, rather than two distinct networks.

Binary document codes can also be learned by extending distributed memory models. Le & Mikolov (2014) suggest that in PV-DM, a context of the central word can be constructed by either concatenating or averaging the document vector and the embeddings of the surrounding words. However, in Binary PV-DM (Figure 3 ) we always construct the context by concatenating the relevant vectors before applying the sigmoid nonlinearity. This way, the length of binary codes is not tied to the dimensionality of word embeddings. Softmax layers in the models described above should be trained to predict words in documents given binary context vectors. Training should therefore encourage binary activations in the preceding sigmoid layers. This can be done in several ways. In semantic hashing autoencoders Salakhutdinov & Hinton (2009) added noise to the sigmoid coding layer. Error backpropagation then countered the noise, by forcing the activations to be close to 0 or 1. Another approach was used by Krizhevsky & Hinton (2011) in autoencoders that learned binary codes for small images. During the forward pass, activations in the coding layer were rounded to 0 or 1. Original (i.e. not rounded) activations were used when backpropagating errors. Alternatively, one could model the document codes with stochastic binary neurons. Learning in this case can still proceed with error backpropagation, pro-vided that a suitable gradient estimator is used alongside stochastic activations. We experimented with the methods used in semantic hashing and Krizhevsky's autoencoders, as well as with the two biased gradient estimators for stochastic binary neurons discussed by Bengio et al. (2013) . We also investigated the slope annealing trick (Chung et al., 2016) when training networks with stochastic binary activations. From our experience, binary paragraph vector models with rounded activations are easy to train and learn better codes than models with noise-based binarization or stochastic neurons. We therefore use Krizhevsky's binarization in our models.

3. EXPERIMENTS:

To assess the performance of binary paragraph vectors, we carried out experiments on two datasets frequently used to evaluate document retrieval methods, namely 20 Newsgroups1 and a cleansed version (also called v2) of Reuters Corpus Volume 12 (RCV1). As paragraph vectors can be trained with relatively large vocabularies, we did not perform any stemming of the source text. However, we removed stop words as well as words shorter than two characters and longer than 15 characters. Results reported by Li et al. (2015) indicate that performance of PV-DBOW can be improved by including n-grams in the model. We therefore evaluated two variants of Binary PV-DBOW: one predicting words in documents and one predicting words and bigrams. Since 20 Newsgroups is a relatively small dataset, we used all words and bigrams from its documents. This amounts to a vocabulary with slightly over one million elements. For the RCV1 dataset we used words and bigrams with at least 10 occurrences in the text, which gives a vocabulary with approximately 800 thousands elements.

The 20 Newsgroups dataset comes with reference train/test sets. In case of RCV1 we used half of the documents for training and the other half for evaluation. We perform document retrieval by selecting queries from the test set and ordering other test documents according to the similarity of the inferred codes. We use Hamming distance for binary codes and cosine similarity for real-valued representations. Results are averaged over queries. We assess the performance of our models with precision-recall curves and two popular information retrieval metrics, namely mean average precision (MAP) and the normalized discounted cumulative gain at the 10th result (NDCG@10) (Järvelin & Kekäläinen, 2002) . The results depend, of course, on the chosen document relevancy measure. Relevancy measure for the 20 Newsgroups dataset is straightforward: a retrieved document is relevant to the query if they both belong to the same newsgroup. However, in RCV1 each document belongs to a hierarchy of topics, making the definition of relevancy less obvious. In this case we adopted the relevancy measure used by Salakhutdinov & Hinton (2009) . That is, the relevancy is calculated as the fraction of overlapping labels in a retrieved document and the query document. Overall, our selection of test datasets and relevancy measures follows Salakhutdinov & Hinton (2009) , enabling comparison with semantic hashing codes.

We use AdaGrad (Duchi et al., 2011) for training and inference in all experiments reported in this work. During training we employ dropout (Srivastava et al., 2014) in the embedding layer. To facilitate models with large vocabularies, we approximate the gradients with respect to the softmax logits using the method described by Cho et al. (2015) . Binary PV-DM networks use the same number of dimensions for document codes and word embeddings.

Performance of 128and 32-bit binary paragraph vector codes is reported in Table 1 and in Fig- ure 4 . For comparison we also report performance of real-valued paragraph vectors. Note that the binary codes perform very well, despite their far lower capacity: on both test sets the 128-bit Binary PV-DBOW trained with bigrams approaches the performance of the real-valued paragraph vectors. Furthermore, Binary PV-DBOW with bigrams outperforms semantic hashing codes: comparison of precision-recall curves from Figure 4 with Salakhutdinov & Hinton (2009, Figures 6 & 7) shows that on both test sets 128-bit codes learned with this model outperform 128-bit semantic hashing codes. Moreover, the 32-bit codes from this model outperform 128-bit semantic hashing codes on the RCV1 dataset, and on the 20 Newsgroups dataset give similar precision up to approximately 3% recall and better precision for higher recall levels. Note that the difference in this case lies not only in retrieval precision: the short 32-bit Binary PV-DBOW codes are more efficient for indexing than long 128-bit semantic hashing codes. We also compared binary paragraph vectors against codes constructed by first inferring short, realvalued paragraph vectors and then using another unsupervised model or hashing algorithm for binarization. When the dimensionality of the paragraph vectors is equal to the size of binary codes, the number of network parameters in this approach is similar to that of Binary PV models. We experimented with an autoencoder with sigmoid coding layer and Krizhevsky's binarization, with a Gaussian-Bernoulli Restricted Boltzmann Machine (Welling et al., 2004) , and with two standard hashing algorithms, namely random hyperplane projection (Charikar, 2002) and iterative quantization (Gong & Lazebnik, 2011) . Paragraph vectors in these experiments were inferred using PV-DBOW with bigrams. Results reported in Table 2 shows no benefit from using a separate algorithm for binarization. On the 20 Newsgroups dataset an autoencoder with Krizhevsky's binarization achieved MAP equal to Binary PV-DBOW, while the other three approaches yielded lower MAP. On the larger RCV1 dataset an end-to-end training of Binary PV-DBOW yielded higher MAP than the baseline approaches. Some gain in precision of top hits can be observed for iterative quantization and an autoencoder with Krizhevsky's binarization. However, it does not translate to an improved MAP, and decreases when models are trained on a larger corpus (RCV1). et al. (2015) argue that PV-DBOW outperforms PV-DM on a sentiment classification task, and demonstrate that the performance of PV-DBOW can be improved by including bigrams in the vocabulary. We observed similar results with Binary PV models. That is, including bigrams in the vocabulary usually improved retrieval precision. Also, codes learned with Binary PV-DBOW provided higher retrieval precision than Binary PV-DM codes. Furthermore, to choose the context size for the Binary PV-DM models, we evaluated several networks on validation sets taken out of the training data. The best results were obtained with a minimal one-word, one-sided context window. This is the distributed memory architecture most similar to the Binary PV-DBOW model. 

3.1. TRANSFER LEARNING:

In the experiments presented thus far we had at our disposal training sets with documents similar to the documents for which we inferred binary codes. One could ask a question, whether binary paragraph vectors could be used without collecting a domain-specific training set? For example, what if we needed to hash documents that are not associated with any available domain-specific corpus? One solution could be to train the model with a big generic text corpus, that covers a wide variety of domains. It is not obvious, however, whether such model would capture language semantics meaningful for unrelated documents. To shed light on this question we trained Binary PV-DBOW with bigrams on the English Wikipedia, and then inferred binary codes for the test parts of the 20 Newsgroups and RCV1 datasets. We used words and bigrams with at least 100 occurrences in the English Wikipedia. The results are presented in Table 3 and in Figure 5 . The model trained on an unrelated text corpus gives lower retrieval precision than models with domain-specific training sets, which is not surprising. However, it still performs remarkably well, indicating that the semantics it captured can be useful for different text collections. Importantly, these results were obtained without domain-specific finetuning. MAP NDCG@10 20 Newsgroups 0.24 0.51 RCV1 0.18 0.66 

3.2. RETRIEVAL WITH REAL-BINARY MODELS:

As pointed out by Salakhutdinov & Hinton (2009) , when working with large text collections one can use short binary codes for indexing and a representation with more capacity for ranking. Following this idea, we proposed Real-Binary PV-DBOW model (Section 2) that can simultaneously learn short binary codes and high-dimensional real-valued representations. We begin evaluation of this model by comparing retrieval precision of real-valued and binary representations learned by it. To this end, we trained a Real-Binary PV-DBOW model with 28-bit binary codes and 300-dimensional real-valued representations on the 20 Newsgroups and RCV1 datasets. Results are reported in Figure 6 . The real-valued representations learned with this model give lower precision than PV-DBOW vectors but, importantly, improve precision over binary codes for top ranked documents. This justifies their use alongside binary codes.

Using short binary codes for initial filtering of documents comes with a tradeoff between the retrieval performance and the recall level. For example, one can select a small subset of similar documents by using 28-32 bit codes and retrieving documents within small Hamming distance to the query. This will improve retrieval performance, and possibly also precision, at the cost of recall. Conversely, short codes provide a less fine-grained hashing and can be used to index documents within larger Hamming distance to the query. They can therefore be used to improve recall at the cost of retrieval performance, and possibly also precision. For these reasons, we evaluated Real-Binary PV-DBOW models with different code sizes and under different limits on the Hamming distance to the query. In general, we cannot expect these models to achieve 100% recall under the test settings. Furthermore, recall will vary on query-by-query basis. We therefore decided to focus on the NDCG@10 metric in this evaluation, as it is suited for measuring model performance when a short list of relevant documents is sought, and the recall level is not known. MAP and precision-recall curves are not applicable in these settings.

Information retrieval results for Real-Binary PV-DBOW are summarized in Table 4 . The model gives higher NDCG@10 than 32-bit Binary PV-DBOW codes (Table 1 ). The difference is large when the initial filtering is restrictive, e.g. when using 28-bit codes and 2-bit Hamming distance limit. Real-Binary PV-DBOW can therefore be useful when one needs to quickly find a short list of relevant documents in a large text collection, and the recall level is not of primary importance.

If needed, precision can be further improved by using plain Binary PV-DBOW codes for filtering and standard DBOW representation for raking (Table 4 , column C). Note, however, that PV-DBOW model would then use approximately 10 times more parameters than Real-Binary PV-DBOW. 

4. CONCLUSION:

In this article we presented simple neural networks that learn short binary codes for text documents.

Our networks extend Paragraph Vector by introducing a sigmoid nonlinearity before the softmax that predicts words in documents. Binary codes inferred with the proposed networks achieve higher retrieval precision than semantic hashing codes on two popular information retrieval benchmarks. They also retain a lot of their precision when trained on an unrelated text corpus. Finally, we presented a network that simultaneously learns short binary codes and longer, real-valued representations.

The best codes in our experiments were inferred with Binary PV-DBOW networks. The Binary PV-DM model did not perform so well. Li et al. (2015) made similar observations for Paragraph Vector models, and argue that in distributed memory model the word context takes a lot of the burden of predicting the central word from the document code. An interesting line of future research could, therefore, focus on models that account for word order, while learning good binary codes. It is also worth noting that Le & Mikolov (2014) constructed paragraph vectors by combining DM and DBOW representations. This strategy may proof useful also with binary codes, when employed with hashing algorithms designed for longer codes, e.g. with multi-index hashing (Norouzi et al., 2012) .

A VISUALIZATION OF BINARY PV CODES:

For an additional comparison with semantic hashing, we used t-distributed Stochastic Neighbor Embedding (van der Maaten & Hinton, 2008) to construct two-dimensional visualizations of codes learned by Binary PV-DBOW with bigrams. We used the same subset of newsgroups and RCV1 topics that is pictured in Salakhutdinov & Hinton (2009, Figure 5) . Codes learned by Binary PV-DBOW (Figure 7 ) appear slightly more clustered.

(a) A subset of the 20 Newsgroups dataset: green -soc.religion.christian, red -talk.politics.guns, blue -rec.sport.hockey, brown -talk.politics.mideast, magenta -comp.graphics, black -sci.crypt.

128 dimensional codes 32 dimensional codes (b) A subset of the RCV1 dataset: green -disasters and accidents, red -government borrowing, blue -accounts/earnings, magenta -energy markets, black -EC monetary/economic.

128 codes 32 dimensional codes 

:

Available at http://qwone.com/ ˜jason/20Newsgroups

Available at http://trec.nist.gov/data/reuters/reuters.html

Figures and Tables:

Figure 1: The Binary PV-DBOW model. Modifications to the original PV-DBOW model are highlighted.

Figure 2: The Real-Binary PV-DBOW model. Modifications to the original PV-DBOW model are highlighted.

Figure 3: The Binary PV-DM model. Modifications to the original PV-DM model are highlighted.

Figure4: Precision-recall curves for the 20 Newsgroups and RCV1 datasets. Cosine similarity was used with real-valued representations and the Hamming distance with binary codes. For comparison we also included semantic hashing results reported bySalakhutdinov & Hinton (2009, Figures 6 & 7).

Figure 5: Precision-recall curves for the baseline Binary PV-DBOW models and a Binary PV-DBOW model trained on an unrelated text corpus. Results are reported for 128-bit codes.

Figure 6: Information retrieval results for binary and real-valued codes learned by the Real-Binary PV-DBOW model with bigrams. Results are reported for 28-bit binary codes and 300d real-valued codes. A 300d PV-DBOW model is included for reference.

Figure 7: t-SNE visualization of binary paragraph vector codes; the Hamming distance was used to calculate code similarity.

Information retrieval results. The best results with binary models are highlighted.

Table content: <table><tr><td>Code size</td><td>Model</td><td colspan="5">With bigrams MAP NDCG@10 MAP NDCG@10 20 Newsgroups RCV1</td></tr><tr><td/><td>PV-DBOW</td><td>no yes</td><td>0.4 0.45</td><td>0.75 0.75</td><td>0.25 0.27</td><td>0.79 0.8</td></tr><tr><td>128</td><td>Binary PV-DBOW</td><td>no yes</td><td>0.34 0.35</td><td>0.69 0.69</td><td>0.22 0.24</td><td>0.74 0.77</td></tr><tr><td/><td>PV-DM Binary PV-DM</td><td>N/A</td><td>0.41 0.34</td><td>0.73 0.65</td><td>0.23 0.18</td><td>0.78 0.69</td></tr><tr><td/><td>PV-DBOW</td><td>no yes</td><td>0.43 0.46</td><td>0.71 0.72</td><td>0.26 0.27</td><td>0.75 0.77</td></tr><tr><td>32</td><td>Binary PV-DBOW</td><td>no yes</td><td>0.32 0.32</td><td>0.53 0.54</td><td>0.22 0.25</td><td>0.6 0.66</td></tr><tr><td/><td>PV-DM Binary PV-DM</td><td>N/A</td><td>0.43 0.29</td><td>0.7 0.49</td><td>0.23 0.17</td><td>0.77 0.53</td></tr></table>

Information retrieval results for 32-bit binary codes constructed by first inferring 32d realvalued paragraph vectors and then employing another unsupervised model or hashing algorithm for binarization. Paragraph vectors were inferred using PV-DBOW with bigrams.

Table content: <table><tr><td>Binarization model</td><td colspan="4">20 Newsgroups MAP NDCG@10 MAP NDCG@10 RCV1</td></tr><tr><td colspan="2">Autoencoder with Krizhevsky's 0.32 binarization</td><td>0.57</td><td>0.24</td><td>0.67</td></tr><tr><td>Gaussian-Bernoulli RBM</td><td>0.26</td><td>0.39</td><td>0.23</td><td>0.52</td></tr><tr><td>Random hyperplane projection</td><td>0.27</td><td>0.53</td><td>0.21</td><td>0.66</td></tr><tr><td>Iterative quantization</td><td>0.31</td><td>0.58</td><td>0.23</td><td>0.68</td></tr><tr><td>Li</td><td/><td/><td/><td/></tr></table>

Information retrieval results for the Binary PV-DBOW model trained on an unrelated text corpus. Results are reported for 128-bit codes.

Table content: <table/>

Peer review (iclr2017):
This paper presents a method to represent text documents and paragraphs as short binary codes to allow fast similarity search and retrieval by using hashing techniques. The real-valued paragraph vectors by Le & Mikolov is extended by adding a stochastic binary layer on top of the neural network architecture. Two methods for binarizing the final activations are compared: (1) simply adding noise to sigmoid activations to encourage discritization. (2) binarizing the activations in the forward pass and keeping them real-valued in the backward pass (straight-through estimation). The paper presents encouraging results by using straight-through estimation on 20 newsgroup and RCV1 text datasets by using 128 and 32 bit binary codes. On the plus side, the application presented in the paper is interesting and important. The exposition of the paper is clean and clear. However, the novelty of the approach is limited from a machine learning standpoint. The literature on binary hashing beyond semantic hashing and Krizhevsky*s binary autoencoders in 2011 is not explained. An important baseline is missing where real-valued paragraph vectors are learned first, and then converted to binary codes using off-the-shelf hashing methods (e.g. random projection LSH by Charikar, BRE by Kulis & Darrell, ITQ by Gong & Lazebnik, MLH by Norouzi & Fleet, etc.) Given the lack of novelty and the missing baseline, I do not recommend this paper in its current for publication in the ICLR conference*s proceeding. Moving forward, this paper may be more suitable for NLP conferences as it is more on the applied side. More comments: - I believe from an practical perspective it may be easier to first learn real-valued paragraph vectors and then quantize them for indexing. That said, an end-to-end approach as proposed in this paper may perform better. I would like to see an empirical comparison between the proposed end-to-end approach and a simpler two stage quantization method suggested here. - See *Estimating or Propagating Gradients Through Stochastic Neurons* By Bengio et al - discussing straight through estimation and some other alternatives. - The paper argues that the length of binary codes cannot be longer than 32 bits because longer codes are not suitable for document hashing. This is not quite right given multi-probe hashing mechanisms, for example see *Mult-index Hashing* by Norouzi et al. - See *Hashing for Similarity Search: A Survey* by Wang et al. for a survey of related work on binary hashing and quantization. You seem to ignore the extensive work done on binary hashing.