Year: 2018

Abstract:
Learning effective document-level representation is essential in many important NLP tasks such as document classification, summarization, etc. Recent research has shown that simple weighted averaging of word vectors is an effective way to represent sentences, often outperforming complicated seq2seq neural models in many tasks. While it is desirable to use the same method to represent documents as well, unfortunately, the effectiveness is lost when representing long documents involving multiple sentences. One reason for this degradation is due to the fact that a longer document is likely to contain words from many different themes (or topics), and hence creating a single vector while ignoring all the thematic structure is unlikely to yield an effective representation of the document. This problem is less acute in single sentences and other short text fragments where presence of a single theme/topic is most likely. To overcome this problem, in this paper we present P-SIF, a partitioned word averaging model to represent long documents. P-SIF retains the simplicity of simple weighted word averaging, while taking a document’s thematic structure into account. In particular, P-SIF learns topicspecific vectors from a document and finally concatenates them all to represent the overall document. Through our experiments over multiple real-world datasets and tasks, we demonstrate P-SIF’s effectiveness compared to simple weighted averaging and many other state-of-the-art baselines. We also show that P-SIF is particularly effective in representing long multi-sentence documents. We will release P-SIF’s embedding source code and data-sets for reproducing results.

heading: 1 INTRODUCTION
text: Distributed word embeddings such as word2vec (Mikolov et al., 2013b) have shown their success in representing words as latent continuous features in low-dimensional fixed spaces, which can capture their semantic meaning. These embeddings have shown impressive success for improving the performance of machine learning algorithms such as text classification tasks. The success of these word representations is recently formally explained using the random walk-based latent variable model by (Arora et al., 2016a).
Many approaches such as (Socher et al., 2013; Le & Mikolov, 2014; Ling et al., 2015; Liu et al., 2015a) are proposed which go beyond words to capture the semantic meaning of sentences. These techniques either used simple composition of the word-vectors or sophisticated neural network architectures for sentence representation. Recently, (Arora et al., 2017) proposed smooth inverse frequency of word vector averaging model to embed a sentence. They further improved their embedding by removing the first principal component of the weighted average vectors. However, all these approaches are limited to capturing the meaning of a single sentence and represent the sentence in the same space as words, thus reducing their expressive power. Generally, a longer text contain words from multiple different themes (or topics), and creating a single vector from simple averaging of word-vectors will disregard all the thematic structure. Hence, these techniques are largely unable to capture the semantic meaning of larger pieces of text (phrases, sentences and paragraphs).
To address this problem, in this paper we present a novel document embedding method called partition SIF weighted averaging (P-SIF), which can efficiently embed documents with multiple sentences. P-SIF learns topic-specific vectors from a document and finally concatenates them all to represent the overall document. Thus, P-SIF retains the simplicity of simple weighted word averaging,
while taking a document’s thematic structure into account. (Mekala et al., 2017) recently proposed a clustering based word-vector averaging approach for embedding larger text documents. However, they did not provide any justification or experiments to explain the functionality of their embedding approach. This paper provides an analytical explanation about the success of the mentioned representations and also achieves significant improvements over previous embedding techniques on several natural language tasks. Following are the characteristics of P-SIF.
• P-SIF is capable of embedding larger documents with multiple sentences, as it pays attention to the topic/thematic structure of the document.
• P-SIF is simple because it is based on weighted word vectors averaging rather than complicated tensor factorization or neural networks methods.
• P-SIF is an unsupervised method since it is obtained using pre-trained unsupervised word embeddings without using any label information.
• P-SIF outperforms many existing approaches on textual similarity, textual classification and other supervised tasks.
The remaining part of the paper is organized as follows. Section 2 discusses related work in document representations. Section 3 provides motivation for the partition averaging through a qualitative example. Section 4 describes our embedding algorithm. Section 5 introduces and explains the background needed. These sections are followed by experiments in Section 6 and the analysis with the discussion in Section 7.

heading: 2 RELATED WORK
text: Word embeddings. There are mainly two methodologies proposed for unsupervised wordembedding representations, either by internal representations learned through neural network models of text (Bengio et al., 2003; Collobert & Weston, 2008), and Mikolov et al. (2013b) or by low-rank approximation of co-occurrence statistics by (Levy & Goldberg, 2014; Hashimoto et al., 2016), and Arora et al. (2016a). (Levy & Goldberg, 2014) show that both techniques are equivalent.
Sentence embeddings. Earlier work has computed sentence embedding by coordinate wise vector and matrix based compositional operation over word vectors, e.g., (Levy & Goldberg, 2014) use unweighted averaging of word vectors for representing short phrases, (Singh & Mukerjee, 2015) proposed tfidf-weighted averaging of word vectors to form document vectors, (Socher et al., 2013) proposed a recursive neural network (RNN) defined over a parse tree and trained with supervision. Next, (Le & Mikolov, 2014) proposed PV-DM and PV-DBOW model which treats each sentence as a shared global latent vector (or pseudo word). Other approaches use seq2seq models such as Recurrent Neural Networks (Mikolov et al., 2010) and Long Short Term Memory (Gers et al., 2002) which can handle long term dependency, hence, capturing the syntax structure. Other neural network models include use of hierarchy and convolution neural networks, such as (Kim, 2014) and (Kalchbrenner et al., 2014). (Wieting et al., 2015) learned paraphrastic sentence embedding by modifying word embeddings based on the supervision from the Paraphrase pairs dataset (PPDB). Recently, a lot of work is harnessing topic modeling (Blei et al., 2003) along with word vectors to learn better word and sentence representations, e.g., TWE (Liu et al., 2015a), NTSG (Liu et al., 2015a), WTM (Fu et al., 2016), w2v-LDA (Nguyen et al., 2015), TV+MeanWV (Li et al., 2016a), LTSG (Law et al., 2017), Gaussian-LDA (Das et al., 2015), Topic2Vec (Niu et al., 2015), Lda2vec (Moody, 2016), and MvTM (Li et al., 2016b).
Document embeddings. (Kiros et al., 2015) proposed skip-thought document embedding vectors which transformed the idea of abstracting the distributional hypothesis from word level to sentence level. (Wieting et al., 2016a) proposed a neural network model which optimizes the word embeddings based on the cosine similarity of the sentence embeddings. (Gupta et al., 2016) proposed a method called Bag of Words Vector (BoWV), which employs a clustering based technique and tf-idf values to form a composite document vector. They represented documents in higher dimensions by using hard clustering over word embeddings. (Mekala et al., 2017) later extended the model to SCDV by using a fuzzy clustering technique and direct idf weighting of word vectors. The learned representations tried to capture a global context of sentence, similar to an n-gram model. Their method outperformed previous state of art on a variety of NLP tasks.
Table 1: Words with their Topic Proportions
word 1 2 3 4 5 data 0.3 0.7 0.0 0.0 0.0 interviewing 0.0 0.0 0.8 0.0 0.2 management 0.0 0.0 0.8 0.0 0.2
public 0.0 0.0 0.0 0.7 0.3
Figure 1: Word vector space for corpus C. Words in different partitions are represented by different subscripts and separated by hyperplanes. Bold fonts represent words’ presence in the document

heading: 3 MOTIVATION: AVERAGING VS PARTITION AVERAGING
text: Let’s consider a corpus (C) with N documents with the corresponding most frequent words vocabulary (V ). Figure 1, represents the word-vectors space of V , where similar meaning words occur closer to each other. We can apply sparse coding to partition the word vectors space to a five (total topics K = 5) topic vector space, as shown in figure 1. These five topic vector spaces represent the five topics present in corpus (C). Few words are polysemic and belong to multiple topics with some proportion (see Table 1). In figure 1 we represent the topic number of the word in subscript. Let’s consider a document dn: ‘Data journalists deliver data science news to general public. They often take part in interpreting the data models. In addition, they create graphical designs and interview the directors and CEO’s.‘
One can directly average the word vectors to represent the document (~vdn ), as in (SIF), shown in equation equation 1. Here, + represents element-wise vector addition.
~vdn = ~vdata2 + ~vjournalist4 + ~vnews4 + ~vdatascience1 + ~vpublic4 + ~vinterpreting1 + ~vmodels2+
~vgraphical1 + ~vdesign1 + ~vdirector5 + ~vCEO5 + ~vinterviewing2 (1)
In representation equation 1 it can be seen that we are averaging word vectors which have a very different semantic meaning, e.g., words belonging to partition 1 such as graphical, design, and data are averaged with different semantic meaning words of partition 2 such as datascience, model, and data. In addition, the document is represented in the same d dimensional space as word vectors. Overall, averaging represents the documents as a single point in the vector space and does not consider the 5 different semantic topics or themes.
However, we do a weighted (topic proportion) average of words within a partition and concatenate the average word vectors across partitions to represent the document (~vdn ), as in (P-SIF), shown in equation equation 2. Here, + represents a element-wise vector addition, × represents scalar-vector multiplication, and ⊕ represents concatenation.
~vdn = (~vinterpreting1 + ~vgraphical1 + ~vdesign1 + 0.3× ~vdata1)⊕ (0.7× ~vdata2 + ~vdatascience2 +~vmodels2)⊕ (~vjournalist4 + ~vnews4 + 0.7× ~vpublic4)⊕ (~vdirector5 + 0.3× ~vpublic5 + ~vCEO5
+0.2× ~vinterviewing5)⊕ (0.8× ~vinterviewing3) (2)
In representation equation 2, the final representation takes 5 different semantic topics into account. Words belonging to different semantic topics are separated by concatenation (⊕) as they represent separate meanings, whereas words coming from same topics are simple averages since they represent the same meaning. E.g., average of words belonging to partition 1 such as graphical, design, and data are concatenated to average of words of partition 2 such as data − science, model, and data. The final document vector ~vdn is represented in a higher 5 × d dimension vector space, thus having more representational power, where d is the dimension of word vectors. From equation 2, it is clear that the final representation takes the weight to which each word belongs to various topics into account as well, thus handling the multi-sense nature of words, e.g., words such as data belong to partition 1 with probability 0.3 and partition 2 with probability 0.7. Hence, partitioned averaging with topic weighting is essential for representing longer text documents. Thus, P-SIF takes documents’ thematic structure into account while doing simple weighted word vectors averaging.

heading: 4 THE PROPOSED ALGORITHM: P-SIF
text: In this section, we present the proposed document embedding learning algorithm. We introduce the formal notation needed for the discussion.
• C represents text corpus and V represents vocabulary of words in corpus. • ~vw ∈ Rd represents the word vector of word w, where d is dimension of word vector. • p(w) represents the unigram probability of word w in the corpus. • c0 and ~vc0 ∈ Rd represent common context and it’s corresponding context vector.
The details to construct document embeddings are given in algorithm 1. The feature formation algorithm can be divided into three major steps :
Dictionary Learning for Word Vectors: Given word vectors vw ∈ Rd, a sparsity parameter k, and an upper bound m , we find a set of unit norm vectors ~A1, ~A2, . . . , ~Am, such that ~vw = ∑m j=1 α(w,j)
~Aj + ~ηw , where at most k of the coefficients α(w,1), . . . , α(w,m) are nonzero (so-called sparsity constraint), and ~ηw is a noise vector.
Sparse coding is usually solved for given m, k by using alternating minimization (Arora et al., 2016b) and (Aharon et al., 2006) to find the ~A′is that minimizes the following L2-reconstruction error : ‖~vw − ∑m j=1 α(w,j)
~Aj‖. Here, ~A1, . . . , ~Am will represents important topic basis in the corpus, which we refer to as the atoms of the topic. Furthermore, restricting m to be much smaller than the number of the words ensures that the same topic needs to be used for multiple words. ~Aj is an interesting or significant topic because the sparse coding ensures that each basis element is softly chosen by many words.
Word Topics Vector Formation: For each word ~w, we created K different word-cluster vectors of d dimensions ~cvwk by weighting the word embedding with its learned dictionary coefficient αw,k of the kth context.1. We then concatenated all theK word-cluster vectors ~cvwk into aK×d dimensional embedding to form a word-topics vector ~tvw ∈ RK×d.
~cvw,k ← ~vw × αw,k ; ~tvw ← K⊕ k=1 ~cvwk
Here, ⊕
represents concatenation operation, and × represents vector-scalar multiplication. Smooth Inverse Frequency (SIF) re-weighted: Finally, for all words appearing in document Dn, we weighted the word-topics vectors ~tvi by smooth inverse frequency ( a
a+p(w)
) . Next, we removed
the common context from the weighted average document vectors by removing the first principal 1 Empirically, we observed that this weighting generally improves the performance
component from the weighted average vectors. 2. (Arora et al., 2017) empirically shows that SIF weighting outperforms the tf-idf weighting. They provide a theoretical explanation for their superior performance.
~vdn ← ~vdn − ~u.~uT~vdn
Algorithm 1: P-SIF Embedding Data: Word embeddings {~vw : w ∈ V }, Documents {dn : dn ∈ D}, a set of sentences D, parameter a and estimated probabilities {p(w) : w ∈ V } of the words, a sparsity parameter k, and an upper bound m. Result: Document vectors {~vdn : dn ∈ D} /* Dictionary learning for word-vectors */
1 for each word w in V do 2 ~vw = ∑m j=1 αw,j
~Aj + ~ηw; 3 end /* Word topic-vector formation */ 4 for each word w in V do 5 for each coefficient, αw,k of word w do 6 ~cvw,k ← ~vw × αw,k; 7 end 8 ~tvw ← ⊕K k=1 ~cvwk ;
/* ⊕
is concatenation, × is scalar vector multiplication */ 9 end /* SIF reweighed document vector embedding */
10 for each document dn in D do 11 ~vdn ← 1|dn| ∑ w∈dn a a+p(w)
~tvw; 12 end 13 Form a matrix X whose columns are {~vdn : dn ∈ D}, and let ~u be the first singular vector; 14 for each document dn ∈D do 15 ~vdn ← ~vdn - ~u~uT~vdn ; 16 end

heading: 5 P-SIF DISCUSSIONS
text: For single sentence documents all words of a document belong to a single topic. However, for multiple sentence-documents, words of a document generally originate from multiple topics. To capture this phenomenon, topic modeling algorithms such as LDA (Blei et al., 2003) are used to represent the documents. These representations essentially represent the global contexts of the documents as a distribution over topics. However, these representations do not take the local context initiating from the distributional semantics into account such as word vectors. To consider both local and global contexts, we represented each word as a word-topic-vector ~tvw. In this section, we describe our simple and efficient unsupervised method for document representation in details.
Sparse Dictionary Learning (Algorithm 1: Lines 1 - 3): (Arora et al., 2016b) shows that atoms of sparse coding over word-vectors represent all prominent topics in the corpus. Furthermore, they showed that multiple word senses of a word reside as a linear superposition within the word embedding and can be recovered by simple sparse coding. Therefore, one can use the sparse coding of word vectors to detect multiple senses of words and total senses of all the words (number of basis). To find these topics, we used sparse coding algorithms such as k-svd (Aharon et al., 2006) over word vectors ~vw. For a given word (w), the k non-zero coefficient essentially represents the distribution of words over topics. The k non-zero αw for a given word w, basically represents the multi-sense nature of the words.
Word Topics Vector (Algorithm 1: Lines 3 - 9): Since our multi-sentence documents have words coming from multiple topics, we did not directly average word-vectors with a simple averaging technique. We concatenated the word embeddings over the topic distribution of the words. This helps to represent semantically similar words in the same topic, while words which are semantically 2 We did not remove the common component from final vectors, when we used Doc2VecC (Chen, 2017) initialized word vectors with P-SIF, because frequent words’ word-vectors become close to ~0
different are represented in different topics. Concatenation of word embeddings over topics also helps in the expression of the multi sense nature of the words. We weigh word-vectors by coefficients of the learned dictionary to capture the cross correlation (αiαj) between contexts.
SIF Weight Averaging and Common Component Removal (Algorithm 1: Lines 9 - 16): Instead of assuming a single topic for the whole document, we showed that the total number of topics over a given corpus is K (as shown by (Arora et al., 2016b)) and for a given word, k out of K of them would be active. Compared to SIF which directly averages SIF weighted words-vectors, we first partitioned according to the topics through dictionary learning over word-topics vectors. We finally averaged SIF weighted word-topics vectors. Lastly, we removed the first principal components from the document vectors to remove the common component.
Sparse Dictionary Learning vs. Fuzzy Clustering. Sparse coding can also be treated as a linear algebraic analogue of overlapping clustering, where the ~Ai’s act as cluster centers and each ~vw is assigned to each cluster in a soft way (using the coefficients α(w,j), of which only k are nonzero) to a linear combination of at most k clusters. In practice, sparse coding optimization produces coefficients α(w,j) which are almost all positive, even though unconstrained. One can use fuzzy clustering where each word belongs to every cluster with some probability P (ck|wi), which can be thought as a substitute for α(w,k), similar to the approach in SCDV (Mekala et al., 2017). Practically, when the number of contexts is large, dictionary learning performs better than fuzzy clustering due to 1) better optimization and non-redundant clusters and 2) automatic handling of the tail of P (ck|wi) distribution through sparsity constraints (Olshausen & Field, 1997; Gao et al., 2010; Yang et al., 2009). We observed that for a single sentence document with a small number of topics it is better to use fuzzy clustering because it has a better optimization and learns efficient clusters. Additionally, in fuzzy clustering, the P (ck|wi) is a probability between 0 and 1, which sums to 1 over all contexts. However, to overcome the noise from the non-zero tail probability one can apply hard thresholding on the final vectors, which are directly learned by few non-zero coefficients (αw,j) of the dictionary.
Our approach is averaging the words which belong to similar topics and concatenating these averages across different topics. Therefore, our approach is a strict generalization of the sentence embedding approach by (Arora et al., 2017) which is a special case where total topics or themes is K = 1.

heading: 6 EXPERIMENTAL RESULTS
text: We performed several experiments on several text similarity and classification tasks. We will address the following research questions through our experiments
Q1. Why partition and sparsity is required during word vectors averaging for representing documents?
Q2. Does P-SIF represent large text documents better compared to other techniques used for representing a single sentence?
Q3. What is the effect of SIF weighting and common component removal on document representation?

heading: 6.1 TEXTUAL SIMILARITY TASK
text: Datasets. We performed our experiments on the SemEval dataset (2012-2017). These experiments involved 27 semantic textual similarity (STS) tasks (2012 - 2016) (Agirre et al., 2012; 2013; 2014; 2015; 2016), the SemEval 2015 Twitter task (Xu et al., 2015), and the SemEval 2014 Semantic relatedness task (Marelli et al., 2014). The objectives of these tasks are to predict the similarity between two sentences. We used the Pearsons coefficient (Fleiss & Cohen, 1973) between the predicted scores and the ground-truth scores for the evaluation. Please refer to the supplementary section F.1 for the experimental setting details.
1. Unsupervised: We used ST, avg-Glove, tfidf-Glove and Glove + WR as a baseline. ST denotes the skip-thought vectors by (Kiros et al., 2015), avg-Glove denotes the unweighted average of the Glove Vectors by (Pennington et al., 2014b) 3, and tfidf-Glove denotes the tf-
3 We used the 300-dimensional word vectors that are publicly available at http://nlp.stanford.edu/projects/glove/
More details on the values of the hyper-parameters used for the experiments are described in details in the supplementary section F.1.
Results and Analysis The average results for each year are reported in Table 2. We denoted our embeddings by P-SIF + PSL (+ PSL denotes using the PSL word vectors). We reported the average results for the STS tasks. The detailed results on each sub-dataset are in the supplementary section A. We observed that P-SIF + PSL outperforms PSL + WR on all datasets, thus supporting the usefulness of our partitioned averaging. Our method also outperformed Neural Network models such as LSTM and RNN. Our proposed techniques performed the best over 16 datasets out of 22 compared to methods from (Wieting et al., 2016a) and (Arora et al., 2017) (refer to supplementary section A for details). Our method outperformed supervised averaging based Gated Recurrent Averaging Network (GRAN) on 11 datasets. Furthermore, our results outperformed recently pro-
posed unsupervised methods such as Skip-Thoughts(Kiros et al., 2015), Sent2Vec(Pagliardini et al., 2018), and supervised method such as Tree-LSTM(Tai et al., 2015). We observed that partitioning through fuzzy cluster algorithm such as GMM generates a better performance compared to partitioning through sparse dictionary algorithms such as k-svd for most Semantic Textual Similarity (STS) tasks. The main reason for this peculiar observation was related to the fact that the STS datasets contains documents which are single sentences of a maximum length of 40 words. As discussed in section 5 (sparse dictionary learning vs. fuzzy clustering), for single sentence documents with a small number of topics, fuzzy clustering optimizes better than sparse dictionary learning. Therefore, we used GMM for the STS task which results in partitioning words into suitable clusters. Both ksvd and GMM outperform SIF, however, the improvement was more observable with the GMM-based partitioning. It should be noted that this observation does not hold for 20NewsGroup and Reuters datasets since the documents in these datasets have multiple sentences with a total number of words >> 40. We also report some qualitative results in the supplementary section D with a supporting example in section E. In addition, we report our results on the SICK supervised classification task in supplementary section B.

heading: 6.2 TEXTUAL CLASSIFICATION TASK
text: The document embeddings obtained by our method can be used as direct features for downstream many supervised tasks.
Datasets We ran multi-class experiments on 20NewsGroup dataset 4 and multi-label classification experiments on Reuters-21578 dataset 5. We used script 6 for preprocessing the dataset. Please refer to supplementary section F.1 for the hyperparameter’s details.
Baselines We considered the following baselines: The Bag-of-Words (BoW) model ((Harris, 1954)), the Bag of Word Vector (BoWV) (Gupta et al., 2016) model, Sparse Composite Document Vector (SCDV) (Mekala et al., 2017) 7 paragraph vector models (Le & Mikolov, 2014), Topical word embeddings (TWE-1) (Liu et al., 2015b), Neural Tensor Skip-Gram Model (NTSG-1 to NTSG-3) (Liu et al., 2015a), tf-idf weighted average word-vector model(Singh & Mukerjee, 2015) and weighted Bag of Concepts (weight-BoC) (Kim et al., 2017) where we built document-topic vectors by counting the member words in each topic, and Doc2VecC (Chen, 2017) where averaging and training of word vectors are done jointly. Moreover, we used SIF (Arora et al., 2017) smooth inverse frequency weight with common component removal from weighted average vectors as a baseline. We also compared our results with other topic modeling based document embedding methods such as WTM (Fu et al., 2016), w2v-LDA (Nguyen et al., 2015), LDA (Chen & Liu, 2014), TV+MeanWV (Li et al., 2016a)), LTSG (Law et al., 2017), Gaussian-LDA (Das et al., 2015), Topic2Vec (Niu et al., 2015), Lda2Vec (Moody, 2016) and MvTM (Li et al., 2016b). Please refer to supplementary section F.2 for the hyperparameter’s details.

heading: 4 http://qwone.com/$\sim$jason/20Newsgroups/ 5 https://goo.gl/NrOfu
text: Multi-class classification We evaluated the classifier’s performance using standard metrics such as accuracy, macro-averaging precision, recall and F-measure. Table 5 shows a comparison on multiple state-of-art document representations on the 20NewsGroup dataset.
Multi-label classification: We evaluated multi-label classification performance using Precision@K, nDCG@k(Bhatia et al., 2015), Coverage error, Label ranking average precision score (LRAPS) 8 and F1-score. Table 4 shows the evaluation results for multi-label text classification on the Reuters-21578 dataset.
Results and Analysis We observed that P-SIF outperforms all other methods by a significant margin on both 20NewsGroup and Reuters datasets. We observed that the dictionary learns more diverse and non-redundant topics compared to fuzzy clustering (SCDV) since we only require 40 partitions rather than 60 partitions in SCDV to obtain the best performance. Simple tf-idf weighted averaging based document representation does not show significant improvement in performance by increasing word vector dimensions. We achieved a < 0.4 % improvement in accuracy when the word vectors dimensions increase from 200 to 500 on 20NewsGroup. We observed that increasing word vectors dimensions beyond 500 does not improve the performance of SIF and P-SIF. We further improved the performance on both datasets using Doc2vecC initialized word-vectors with the help of the P-SIF algorithm. We represented this approach by P-SIF (Doc2VecC) in Table 5 and Table 4. On 20NewsGroup we required only 20 partitioned instead of 40 with Doc2VecC initialized word vectors. This shows that better word vector representations help in learning more diverse and non-redundant partitions. We also reported our results on each of the 20 classes of 20NewsGroup separately in the supplementary section C.

heading: 7 ANALYSIS AND DISCUSSION
text: Effect of Document-Length: We conducted a small experiment to show that our model performs better compared to SIF when we have large size documents. We have divided 26 STS (sentence textual similarity) datasets by average document length, i.e., number of words in documents in bins of (10-20, 20-30, 30-40, 40-50) words. Next, we averaged the relative performance improvement in accuracy with respect to SIF ( P-SIF−SIF SIF % ) and over all datasets in each bin. In Figure 2, we observe that for complex multi-sentence documents with more words P-SIF relatively performs better. We have also observed that short texts require fewer number of partitions to achieve their best performance which was quite intuitive since short text documents will map into fewer topics. 8 https://goo.gl/4GrR3M
Figure 2: Relative performance improvement pf P-SIF over SIF in accuracy
( P-SIF−SIF SIF % )
w.r.t
average numbers of words in documents for 27 sts (sentence textual similarity) datasets.
Effect of Partition: We have concatenated the word embeddings over topic distribution of words which assigned semantically similar words to identical partitions and semantically different words to different partitions. Partitioning and concatenation of word embeddings over topics also helps in the representation of multi-sense words, which would have been left-out by simple averaging of the word embeddings in document representation otherwise. We represented our words by partitioned average of word-vector embeddings distributed over partitions, which grew the representation by the multiplication of the number of partitions, compared to word vector embeddings. Such high dimensional data structure regularizers, e.g., sparse encodings, help in overcoming the curse of dimensionality. We used k-svd (Aharon et al., 2006) a generalized k-means iterative method that alternates between the sparse coding of the examples based on the current dictionary and updating the dictionary atoms to fit the data. SCDV (Mekala et al., 2017) does manual sparse-encoding to ensure sparsity. (Mekala et al., 2017) clustering methodology uses GMM for partitioning the vocabulary space and capturing the topics. Instead of GMM, we used a dictionary learning based approach which imposes a sparsity constraint implicitly during optimization. Since, k-svd is internally and alternatively optimized between sparse encodings and topic representations, we are able to solve the curse of higher dimensionality by automatic sparse representations of the partitions. Emperically, on both datasets, we observed that the dictionary learns more diverse and non-redundant topics compared to fuzzy clustering. We required only 40 partitions rather than 60 in SCDV to obtain the best performance. Additionally, we achieved the best performance with (P-SIF(Doc2VecC)) with just (20 ∗ 300) dimensions of word embeddings (mostly sparse) as compared to (60 ∗ 300) dimensions of word-embeddings (mostly non-sparse) in SCDV. Thus, we obtained a performance gain of 1.5% with 0.33 of the size of the SCDV embeddings.
Effect of SIF and Common Component Removal: We have also shown improvement in shorter text tasks via sentence textual similarity task. We have used SIF based weighted word averaging methods instead of tf-idf averaging (Mekala et al., 2017) or simple averaging of word-embeddings. SIF takes advantage of the generative process of document-formation and represents documents as simple smooth inverse frequency averaging of word embeddings. We also observe that removing the first principal component helps in removing the common component occurring due to frequent common words from document vectors. This observation reduces noise and redundancy from the composed document vectors which make vectors more discriminating.

heading: 8 CONCLUSIONS AND FUTURE WORK
text: We proposed an unsupervised document feature formation technique based on a partitioned word vector averaging method. Our embedding retains the simplicity of simple weighted word averaging, while taking documents’ thematic structure into account. Our simple and efficient approach achieved significantly better performance on several textual similarity tasks, textual classification tasks and
out of domain tasks. In the future, three extensions of our work would be 1. Learning a supervised weighting scheme of words according to the task to improve words weighting, 2. Learning and using context sensitive word embeddings instead of normal skip-gram embeddings to resolve cluster disambuity, and 3. Learning a lower dimensional space manifold to represent word-topic vectors for continuous representations useful in deep leaning applications.

heading: A UNSUPERVISED TASK: TEXTUAL SIMILARITY
text: In this supplementary section, we present the details results for STS tasks for each year. Each year, there are 4 to 6 STS tasks, as shown in Table 6. Note that tasks with the same name in different years are different tasks in reality. We provide detailed results for each tasks in STS 12 - 15 in Table 7. Our method outperforms all other methods from (Arora et al., 2017) and (Wieting et al., 2016a) on all 16 out of 22 tasks. Our method performs significantly better in comparison to all unsupervised embedding methods. In addition, P-SIF is very close to the best performance by supervised methods on the rest of the datasets. The performance difference between best method and our method compared with best method is much small. Our method was also able to outperform state of art supervised averaging based Gated Recurrent Averaging Network (GRAN) (Wieting & Gimpel, 2017) on 11 datasets shown in Table 7. Our results also outperform state of art methods on many recent supervised embedding methods on STS 16 task, as shown in Table 8.

heading: B OTHER SUPERVISED TASKS
text: We also consider three out of domain supervised tasks: the SICK similarity task, the SICK entailment task, and the Stanford Sentiment Treebank (SST) binary classification task by (Socher et al., 2013). We use the setup similar to (Wieting et al., 2016a) and (Arora et al., 2017) for a fair comparison, including the linear projection maps which take the embedding into 2400 dimension (same as skip-thought vectors), and is learned during the training. We compare our method to PP, DAN, RNN, LSTM, and skip-thoughts and other baselines, details results in Table 9.
Results and Analysis. Our method (P-SIF) gets better performance compared to PSL + WR on all the three tasks similarity, entailment and sentiment. We obtained best results for two of the supervised tasks, despite many of these methods (DAN, RNN, LSTM) are trained with supervision. Furthermore, the skip thought vectors use has a higher dimension of 2400 dimension instead of 300 dimensions (which we projected to 2400 for a fair comparison). Our method wasn’t able to outperform sentiment task compared to supervised tasks because a) due to antonym problem word vectors capture sentimental meaning of words and b) also in our weighted average scheme, we didn’t give more weights to sentiment words such as not,good, bad, there may be some important sentiment words which are down-weighted by SIF weighting scheme. However, we outperform PSL + WR by a significant margin and have lesser performance gap with the best supervised approach.

heading: C CLASS PERFORMANCE: 20NEWSGROUP
text: We also report the precision and recall results of separate 20 classes of the 20 NewsGroup dataset. We compared our embedding (P-SIF) with Bag of Words, SCDV embeddings and our embeddings. Table 10, P-SIF embedding outperform all other embeddings on multiple classes.

heading: D QUALITATIVE RESULTS
text: Table 11 represent successful example pair from STS 2012 MSRvid dataset where P-SIF give similarity score closer to ground truth than SIF. Table 12 represent failed example pair from STS 2012 MSRvid dataset where SIF give similarity score closer to ground truth than P-SIF. We now introduce the headline notation use in the Table 11 and 12.
• GT : represent the given ground truth similarity score in range of 0-5. • NGT : represent normalized ground truth similarity score. NGT is obtain by dividing GT
score by 5 so that it’s in range of 0-1. • SIFsc : represent the SIF embedding similarity score in range of 0-1. • P-SIFsc : represent the P-SIF embedding similarity score in range of 0-5. • SIFerr : represent absolute error ‖SIFsc −NGT‖ between normalized ground truth simi-
larity score and SIF embedding similarity score. • P-SIFerr : represent absolute error ‖P-SIFsc − NGT‖ between ground truth similarity
score and P-SIF embedding similarity score. • Differr : represent absolute difference between SIFerr and P-SIFerr. Examples where P-
SIF perform better Differr = P-SIFerr - SIFerr (used in Table 11). Examples where SIF perform better Differr = SIFerr - P-SIFerr (used in Table 12) • Relerr : represent relative difference between SIFerr and P-SIFerr. Example where P-SIF perform better Relerr = DifferrSIFerr (used in Table 11). Examples where SIF perform better Relerr = DifferrP-SIFerr (used in Table 12)

heading: E QUALITATIVE EXAMPLE
text: Let’s consider a corpus (C) with N documents with corresponding most frequent words vocabulary (V ). Figure 3 represents the word-vectors space of V , where similar meaning words are closer. We can apply sparse coding and partition the words-vector space in five (total topicsK = 5) topic vector spaces. Some words are polysemic and belong to multiple topics with some proportion, as shown in Figure 3. For example, words such as baby, person, dog and kangaroo, belong to multiple topics with
significant proportion. Words and corresponding vectors in these topic vector spaces are represented by topic numbers in subscript. Table 13 shows an example pair from the STS Task 2012 MSRVid dataset, and the corresponding SIF (averaging) and P-SIF (partition averaging) representation vectors. We can see that in SIF representation we are averaging words vectors which semantically have different meanings. The document is represented in the same d dimensional word-vectors space. Overall, the SIF represent the document as a single point in the vector space and doesn’t take account of different semantic meanings of the topics. Whereas, in P-SIF representation we treat the 5 different semantic topics distinctly. Words belonging to different semantic topics are separated by concatenation (⊕) as they represent different meanings, whereas words coming from same topic are average as it’s represent same meaning. The final document vector ~vdn has more representational power as it’s represented in a higher 5× d dimensional vector space. Thus partitioned averaging with topic weighting is important for representing documents. Empirically, P-SIF gave score dissimilar sentences (d1n,d 2 n) 0.16 (0-1 scale) where the ground truth of 0.15 (rescale to 0-1 scale), whereas SIF gave similarity score of 0.57 (0-1 scale), farther then ground score. Thus we obtain a relative improvement of 98% in the error difference from ground truth. Here, simple averaging-based embedding of d1n and d 2 n, bring the document representation closer. But, partitioned based averaging P-SIF of d1n and d 2 n as, project the document in a higher dimensional space.
Table 13: STS Task 2012 MSRVid dataset similarity example pair where P-SIF gave score dissimilar sentences (d1n,d 1 n) 0.16 (0-1 scale) where the ground truth of 0.15 (rescale to 0-1 scale), whereas SIF gave similarity score of 0.57 (0-1 scale). Thus, we obtain a relative improvement of 98% in the error difference. Here, ⊕ represent concatenation. ~vzero is the zero padding vector.
Document 1 (d1n) Document 2 (d2n) Score Doc A man is riding a motorcycle A woman is riding a horse 0.15 SIF ~vman2 + ~vriding3 + ~vmotorcycle4 ~vwoman1 + ~vriding3 + ~vhorse5 0.57
P-SIF ~vzero1 ⊕ ~vman2 ⊕ ~vriding3 ⊕ ~vmotorcycle4 ⊕ ~vzero5 ~vwomen1 ⊕ ~vzero2 ⊕ ~vriding3 ⊕ ~vzero4 ⊕ ~vhorse5 0.16
Figure 3: Word vector space for corpus C. Words in different topic is represented by different subscript and separated by hyperplanes. Bold represent words from example documents.

heading: F EXPERIMENTAL DETAILS
text: F.1 TEXTUAL SIMILARITY TASK:
We use the PARAGRAM-SL999 (PSL) from (Wieting et al., 2015) as word embeddings, obtained by training on PPDB (Ganitkevitch et al., 2013) dataset 9. We use the fix weighting parameter α value of 10−3, and the word frequencies p(w) are estimated from the common-crawl dataset. We tune the number of contexts (K) to minimize the reconstruction loss over word vectors. We fix the non-zero coefficient m = K/2, for the SIF experiments. For GMM based partitioning of the words vocabulary we tune the number of cluster parameter K through 5-fold cross validation.
F.2 TEXTUAL CLASSIFICATION TASK:
We fix the document embeddings and only learn the classifier. We learn word vector embedding using Skip-Gram with a window size of 10, Negative Sampling (SGNS) of 10 and minimum word frequency of 20. We use 5-fold cross-validation on the F1 score to tune hyperparameters. We use LinearSVM for multi-class classification and Logistic regression with the OneVsRest setting for multi-label classification. We fix the number of dictionary elements either 40 or 20 (with Doc2vecC initialize word vectors) and non-zero coefficient tom =K/2 during dictionary learning for all experiments. We use the best parameter settings as reported in all our baselines to generate their results. We use 200 dimensions for tf-idf weighted word-vector model, 400 for paragraph vector model, 80 topics and 400 dimensional vectors for TWE, NTSG, LTSG and 60 topics and 200 dimensional word vectors for SCDV (Mekala et al., 2017). We will released P-SIF’s embedding source code with necessary parameters details and other data-sets used in the paper for reproducing results.
9 For a fair comparison with SIF we uses PSL vectors instead of unsupervised Glove and Word2Vec vectors
G CODE FLOW ARCHITECTURE
H HIGH LEVEL FLOW

heading: I PROOF SKETCH: DERIVATION OF OUR EMBEDDING
text: To derive our embedding, we propose a generative model which treats corpus generation as a dynamic process, where the tth word is produced at step t. The process is driven by random walk over a unit norm sphere with centre at the origin. Let, ~vct be the vector from origin to current walk point at time t. We called this vector as context vector, as it represents the context in the discussion. Below, we introduce formal notation needed for the discussion
• C represents text corpus and V represents vocabulary of words in corpus. • ~vw ∈ Rd represents the word vector of word w , where d is dimension of word vector. • ct represents context and ~vct ∈Rd represents context vector at time t, where d is dimension
of context vector. • Zc represents partition function for the random context vector ~vct , given by Zc =∑ w exp(〈~vct , ~vw〉). • p(w) represents the unigram probability of word w in the corpus. • c0 and ~vc0 ∈ Rd represent common context and its corresponding context vector based on
syntax.
Using log linear model of Mnih & Hinton (2007), we define the probability of observing a word w from the random walk with current context ct at time t as
Pr[w|ct] ∝ exp(〈~ct, ~vw〉) (3)
It is easy to show that such random walk under some reasonable assumptions (Arora et al. (2016a)) can gives word-word co-occurrence probabilities similar to empirical works like word2vec (Mikolov et al. (2013a)) and Glove (Pennington et al. (2014a)). To account for frequent stop-words which occur more often regardless of context and common context related to document syntax, two correction terms need be added: one based on p(w) and other on common context vector ~vc0 in Equation equation 3. These terms allow words with low inner product with ~ct, a chance to appear either from term p(w) if they are frequent or by common context ~c0 , if they have large dot product with ~c0. Given a context vector ct, the probability of a word w in document d being generated by context ct is given by,
Pr[w|ct] = λp(w) + (1− λ) exp(〈~c′t, ~vw〉)
Zc′t (4)
where, ~c′t = β~c0 + (1− β) ~ct, 〈~c0,~ct〉 = 0, λ and β are scalar hyper-parameters. For generating a document from above random walk based latent variable model, we consider the following two assumptions :
1. Total number of theme/topics in the entire corpus is K. The K themes/topics can be determine by sparse dictionary learning as shown by Arora et al. (2016b) over word vectors ~vw = ∑m j=1 αw,j
~Aj + ~ηw, where, ~Aj’s are unit norm vectors representing basis of theme, αw,j are coefficient determining whether w is generated with ~Aj 10 , and ~ηw is a noise vector.
2. Word vectors ~vw are uniformly distributed, thus making the partition function Zc, roughly same in all direction for given context c, where c belongs to one of the K themes/topics, as described earlier. The context vector does not change significantly much while words are generated from random walk, as shown by Arora et al. (2017) except during jumps a.k.a when theme/topic change.
For a document d, the likelihood of document is being generated by the K contexts, is given by :
10 In practice, only k (much lesser than total number of themes/topicK) αw,j will be non-zero, because a word can’t belong to all contexts (exception for frequent stop-words)
p(d|{c1, c2 . . . cK}) ∝ K∏
j=1 ∏ {w∈d} p(w|cj) (5)
= K∏ j=1 ∏ w∈d [ λp(w) + (1− λ) exp(〈~vw, ~vcj 〉) Zj ] (6)
Let,
fw(cj) = log [ λp(w) + (1− λ)
exp(〈~vw, ~vcj 〉) Zj
] (7)
Here, p(w|cj) is the probability that word w is generated by context cj , the value of which is determine by 1) overall frequency of word w in corpus a.k.a prior probability (p(w)) and 2) relative frequency of w appear with context j w.r.t other contexts (determine by α(w,j)).
Using simple calculus, treating p(w) as constant, we can show that∇(fw(cj)) equals,
1 λp(w) + (1− λ) exp(〈~vw, ~vcj 〉)/Zj ∗ 1− λ Zj exp(〈~vw, ~vcj 〉)~vw (8)
Then, by using the Taylor expansion, we can show
fw(cj) ≈ fw(cj = 0) +∇(fw(cj = 0))T~vcj (9)
fw(cj) ≈ constant+∇(fw(cj = 0))T~vcj (10)
Therefore, the maximum likelihood estimator (MLE) for ~vcj on the unit sphere (ignoring normalization) is approximately, 11
argmax ∑ w∈d fw(cj) ∝ ∑ w∈d
a
p(w) + a ~vw (11)
here, a = 1−λλZj
Thus, the MLE estimate is approximately a weighted average of the word vectors generated from context j in the document d from random walk. We can get the overall context representation ~vcd of document, by simple concatenation over all K themes/topics.
~vcd = K⊕ j=1 ~vcj (12)
Here, ⊕
represents concatenation operation. For a document if no words is generated from the context cj the we can substitute the context vector ~vcj by ~0 vector, for representation ~vcd in K × d dimensions.
Relation to SIF model: Arora et al. (2017), shows under the two assumptions :
• uniform distribution of word vectors ~vw’s which implies that the partition function Zt is roughly same in all direction for the a sentence.
• the context vector ~vct , remain constant while the words in the sentence are emitted, implying replacing of ~vct in sentence’s by a single vector ~vcs and partition function by Zs
11 Note that argmaxc:‖~c‖=1C + 〈~c,~g〉 = ~g‖~g‖ for any constant C
the sentence embedding of a sentence can be obtained by ~vcs = ∑ {w∈s} a p(w)+a~vw, here, a = 1−λ λZs .
However, the above assumptions does not hold true for a document with multiple sentences, where one can expect to have more frequent random jumps during random walk 12. Instead of assuming a single context for whole document ch, we assume that the total number of theme/topics over a given corpus is bounded by K (as shown by Arora et al. (2016b)) and the random walk can perform jumps to switch context from one context to the rest K − 1 contexts. The partition function remain same in all directions for only words coming from a same context cj , instead of words coming from all K contexts. Thus, our approach is generalization of sentence embedding approach by Arora et al. (2017) (special case K = 1).

heading: J KERNEL CONNECTION TO WORD MOVER DISTANCE
text: Below, we introduce formal notation needed for the discussion:
• C represents text corpus and V represents vocabulary of words in corpus. • ~wvw ∈ Rd represents the word vector of word w , where d is dimension of word vector. • ~tvw ∈ RK represents the theme/topic vector of word w, where K is number of
themes/topics. tw,j = αw,j = P (j|w)
• dA, dB represent two document containing n and m words respectively. wA1 , wA2 . . . wAn represent words of dA and wB1 , w B 2 . . . w B n represents word of dB .
Consider the following document similarity kernels:
K1(dA, dB) = 1
nm n∑ i=1 m∑ j=1 〈 ~wvwAi · ~wvwBj 〉 = Ei,j 〈 ~wvwAi · ~wvwBj 〉
K2(dA, dB) = 1
nm n∑ i=1 m∑ j=1 〈 ~wvwAi · ~wvwBj 〉× 〈~tvwAi · ~tvwBj 〉 = Ei,j 〈 ~wvwAi · ~wvwBj 〉× 〈~tvwAi · ~tvwBj 〉
K3(dA, dB) = 1
n n∑ i=1 max j ~wvwAi · ~wvwBj 〉 = Ei ( max j 〈 ~wvwAi · ~wvwBj 〉 ) K4(dA, dB) = 1
m m∑ j=1 max i 〈 ~wvwAi · ~wvwBj 〉 = Ei ( max i 〈 ~wvwAi · ~wvwBj 〉 ) K5(dA, dB) = K 3(dA, dB) +K 4(dA, dB)
We can conclude the following from the respective kernels:
• K1(dA, dB) represent document similarity between document represented by average word vectors dx = ∑ i ~wv x i • K1(dA, dB) represent document similarity between document represented by partition average word vectors
• K3(dA, dB) represent document similarity between document represented by relax word mover distance when words of dA are matched to dB • K4(dA, dB) represent document similarity between document represented by relax word mover distance when words of dB are matched to dA • K5(dA, dB) represent document similarity between document represented by word mover distance.
We empirically showed that our proposed embedding (kernel) outperform the word mover distance(Kusner et al., 2015) and word mover embedding (Wu et al., 2018) and many other baselines in Table 14 on several datasets 13. 12 It is trivial to assume that these jumps occur more frequently in multiple sentences document, because of increased chances of context change 13 For datasets and baseline details refer to (Wu et al., 2018)

heading: K RECENT BASELINE FOR TEXTUAL SIMILARITY TASK
text: We compared out P-SIF embedding with many other recently proposed baseline like ELMO (Peters et al., 2018), p-means (Rücklé et al., 2018), FastText (Joulin et al., 2016), Skip-Thoughts (Kiros et al., 2015), (Conneau et al., 2017), Charphrase (Wieting et al., 2016b), WME (Wu et al., 2018) and u-SIF Ethayarajh (2018). We used the SentEval package (Conneau & Kiela, 2018) and embedding evaluation paper Perone et al. (2018) for baselines. Except u-SIF we outperform all other embedding. Our P-SIF results was very close to u-SIF in most tasks. Details results are provided in Table 15

heading: L MORE EXPERIMENTAL RESULTS
text: We also compared our embedding extensively on random hashing of words (instead of GMM) (refer Table 16), p-means (Rücklé et al., 2018) (refer Table 17), and ELMO (Peters et al., 2018) (refer Table 18) embedding on 20NewsGroup. P-SIF outperform all three embedding on 20NewsGroup.
We also compared our embedding extensively on p-means (Rücklé et al., 2018) embedding on Reuters. P-SIF outperform p-means on Reuters for various values of p (refer Table 19).

Review summaries:
The paper shows that we could have a better document/sentence embedding by partitioning the word embedding space based on a topic model and summing the embedding within each partition. The writing and presentation of the paper are clear. The method is simple, intuitive, and the experiments show that this type of method seems to achieve state-of-the-art results on predicting semantic similarity between sentences, especially for longer sentences. 

Paper overview: The paper extends the method proposed by Arora 2017 for sentence embeddings to longer document embeddings. The main idea is that, averaging word embedding vectors mixes all the different topics on the document, and therefore is not expressive enough. Instead they propose to estimate the topic of each word (using dictionary learning) through the $\alpha$ weights (see page 4).These weights give "how much" this word belongs to a certain topic. For every topic we compute the $\alpha$-weighted vector of the word and  concatenate them (see word topic vector formation). Finally, we apply SIF (Arora 2017) using these word embeddings on all the document.