BINARY PARAGRAPH VECTORS
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 & Hyvä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 representation – a 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) (Järvelin & Kekälä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 128- and 32-bit binary paragraph vector codes is reported in Table 1 and in Figure 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.
1Available at http://qwone.com/˜jason/20Newsgroups 2Available at http://trec.nist.gov/data/reuters/reuters.html
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 PVDBOW 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).
Li 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 PVDBOW 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.
Table 3: Information retrieval results for the Binary PV-DBOW model trained on an unrelated text corpus. Results are reported for 128-bit codes.
MAP NDCG@10 20 Newsgroups 0.24 0.51
RCV1 0.18 0.66
10-2 10-1 100
Recall
0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
P re
ci si
o n
training on the 20 Newsgroups training set training on English Wikipedia
(a) 20 Newsgroups
10-2 10-1 100
Recall
0.1
0.2
0.3
0.4
0.5
0.6
0.7
P re ci si o n
training on the RCV1 training set training on English Wikipedia
(b) RCV1
Figure 5: Precision-recall curves for the baseline Binary PV-DBOW models and a Binary PVDBOW model trained on an unrelated text corpus. Results are reported for 128-bit codes.
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 PVDM 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).
ACKNOWLEDGMENTS
This research is supported by the Polish National Science Centre grant no. DEC-2013/09/B/ST6/01549 “Interactive Visual Text Analytics (IVTA): Development of novel, user-driven text mining and visualization methods for large text corpora exploration.” This research was carried out with the support of the “HPC Infrastructure for Grand Challenges of Science and Engineering” project, co-financed by the European Regional Development Fund under the Innovative Economy Operational Programme. This research was supported in part by PL-Grid Infrastructure.
The method in this paper introduces a binary encoding level in the PV-DBOW and PV-DM document embedding methods (from Le & Mikolov'14). The binary encoding consists in a sigmoid with trained parameters that is inserted after the standard training stage of the embedding.
 
For a document to encode, the binary vector is obtained by forcing the sigmoid to output a binary output for each of the embedding vector components. The binary vector can then be used for compact storage and fast comparison of documents.
 
Pros:
 
- the binary representation outperforms the Semantic hashing method from Salakhutdinov & Hinton '09
 
- the experimental approach sound: they compare on the same experimental setup as Salakhutdinov & Hinton '09, but since in the meantime document representations improved (Le & Mikolov'14), they also combine this new representation with an RBM to show the benefit of their binary PV-DBOW/PV-DM
 
Cons:
 
- the insertion of the sigmoid to produce binary codes (from Lin & al. '15) in the training process is incremental
 
- the explanation is too abstract and difficult to follow for a non-expert (see details below)
 
- a comparison with efficient indexing methods used in image retrieval is missing. For large-scale indexing of embedding vectors, derivations of the Inverted multi-index are probably more interesting than binary codes. See eg. Babenko & Lempitsky, Efficient Indexing of Billion-Scale Datasets of Deep Descriptors, CVPR'16
 
Detailed comments:
 
Section 1: the motivation for producing binary codes is not given. Also, the experimental section could give some timings and mem usage numbers to show the benefit of binary embeddings
 
figure 1, 2, 3: there is enough space to include more information on the representation of the model: model parameters + training objective + characteristic sizes + dropout. In particular, in fig 2, it is not clear why "embedding lookup" and "linear projection" cannot be merged in a single smaller lookup table (presumably because there is an intermediate training objective that prevents this).
 
p2: "This way, the length of binary codes is not tied to the dimensionality of word embeddings." -> why not?
 
section 3: This is the experimental setup of  Salakhutdinov & Hinton 2009. Specify this and whether there is any difference between the setups.
 
"similarity of the inferred codes": say here that codes are compared using Hamming distances.
 
"binary codes perform very well, despite their far lower capacity" -> do you mean smaller size than real vectors?
 
fig 5: these plots could be dropped if space is needed.
 
section 3.1: one could argue that "transferring" from Wikipedia to anything else cannot be called transferring, since Wikipedia's purpose is to include all topics and lexical domains
 
section 3.2: specify how the 300D real vectors are compared. L2 distance? inner product?
 
fig4: specify what the raw performance of the large embedding vectors is (without pre-filtering with binary codes), or equivalently, the perf of (code-size, Hamming dis) = (28, 28), (24, 24), etc.