#  P-SIF: Document Embeddings Using Partition Averaging

Vivek Gupta1,3, Ankit Saw2, Pegah Nokhiz1, Praneeth Netrapalli3,
Piyush Rai4, Partha Talukdar5
1School of Computing, University of Utah, 2Info Edge (India) Limited,
3Microsoft Research Lab, Bangalore,
4Computer Science Department, IIT Kanpur, 5Indian Institute of Science,
Bangalore
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

Simple weighted averaging of word vectors often yields effective
representations for sentences which outperform sophisticated 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 of the key
reasons is that a longer document is likely to contain words from many
different topics; hence, creating a single vector while ignoring all the
topical structure is unlikely to yield an effective document representation.
This problem is less acute in single sentences and other short text fragments
where the presence of a single topic is most likely. To alleviate this
problem, 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 topical structure into account. In particular, P-SIF
learns topic-specific vectors from a document and finally concatenates them
all to represent the overall document. We provide theoretical justifications
on the correctness of P-SIF. Through a comprehensive set of experiments, we
demonstrate P-SIF’s effectiveness compared to simple weighted averaging and
many other baselines.

## Introduction

Many approaches such as (?; ?; ?; ?) are proposed which go beyond words to
capture the semantic meaning of sentences. These techniques either use the
simple composition of the word-vectors or sophisticated neural network
architectures for sentence representation. Recently, (?) proposed a smooth
inverse frequency (SIF) based 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 representing the
sentence in the same space as words, thus reducing their expressive power.
Generally, longer texts contain words from multiple topics, so creating a
single vector from simple averaging of word-vectors will disregard all the
topical structure. 111Topical structure denotes word distribution across
topics. Hence, these techniques are largely unable to capture the semantic
meanings of larger pieces of text, e.g., multi-sentence documents.

To address these limitations, we present a novel document embedding method
called _partition SIF_ weighted averaging (P-SIF) to embed documents which
usually contain multiple sentences efficiently. 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 topical structure into account. We also
provide theoretical justifications for the proposed approach and demonstrate
its efficacy via a comprehensive set of experiments. P-SIF achieves
significant improvements over several embedding techniques on several tasks
despite being simple. We have released the source code for P-SIF embeddings.
222https://github.com/vgupta123/P-SIF The novel characteristics of P-SIF are
described below:

  * •

P-SIF can embed larger multi-sentence documents, as it pays attention to the
topical structure of the document.

  * •

P-SIF is based on simple weighted word vectors averaging rather than
considerably more sophisticated tensor factorization or neural network-based
methods.

  * •

P-SIF is unsupervised since it only uses pre-trained word embeddings without
using any label information.

  * •

P-SIF outperforms many existing methods on text similarity, text
classification, and other supervised tasks.

## Related Work

Most of the prior work has computed sentence embeddings by coordinate wise
vector and matrix-based compositional operations over word vectors, e.g., (?)
use unweighted averaging of word vectors(?) for representing short phrases,
(?) propose tfidf-weighted averaging of word vectors to form document vectors,
(?) propose a recursive neural network defined over a parse tree, and trained
with supervision.

Next, (?) propose PV-DM and PV-DBOW models which treat each sentence as a
shared global latent vector. Other approaches use seq2seq models such as
Recurrent Neural Networks (?) and Long Short Term Memory (?) which can handle
long term dependency, hence capturing the syntax structure. Other neural
network models include the use of hierarchy and convolutional neural networks
such as (?). (?) learns paraphrastic sentence embeddings by modifying word
embeddings via supervision from the Paraphrase pairs dataset (PPDB) (?).

Recently, a lot of work is harnessing topic modeling (?) along with word
vectors to learn better word and sentence representations, e.g., LDA (?),
weight-BoC (?), TWE (?) , NTSG (?), WTM (?), w2v-LDA (?), TV+MeanWV (?), LTSG
(?), Gaussian-LDA (?), Topic2Vec (?), TM (?), LDA2vec (?), D-ETM (?) and MvTM
(?). (?) propose skip-thought document embedding vectors which transformed the
idea of abstracting the distributional hypothesis from word to sentence level.
(?) propose a neural network model which optimizes the word embeddings based
on the cosine similarity of the sentence embeddings. Moreover, several recent
deep contextual word embeddings such as ELMo (?), USE (?) and BERT (?) are
proposed. These contextual embeddings are state-of-the-art on multiple tasks
as they effectively capture the surrounding contexts.

(?) propose methods which employ a clustering-based technique and tf-idf
values to form a composite document vector extending the Bag-of-Words (BoW)
model (?). They represent documents in higher dimensions by using hard
clustering over word embeddings. (?) extend this by proposing SCDV using an
overlapping clustering technique and direct idf weighting of word vectors. The
learned representations try to capture a global context of a sentence, similar
to an $n$-gram model. Our method is the same in essence, but is based on
topic-based partitioning; moreover, unlike (?)’s approach, our method is
supported by theoretical guarantees.

## Averaging vs Partition Averaging

Figure 1, represents the word-vector space, where similar meaning words occur
closer to each other. We can apply sparse coding to partition the word-vector
space to a five topic vector space. These five topic vector spaces represent
the five topics present in corpus. Some words are multi-sense and belong to
multiple topics with some proportion. In Figure 1 we represent words’ topic
number in subscript and proportion in brackets. Let’s consider a document
$d_{n}$: “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 CEOs.”

Figure 1: Words in different partitions are represented by different
subscripts and separated by hyper-planes. Bold fonts represent words’ presence
in document $d_{n}$.

If we directly average words to represent document ($\vec{v}_{d_{n}}$), as is
done in SIF (?), then different semantic meaning words, e.g., words in
partition $1$ such as ‘graphical’, ‘design’, and ‘data’ are averaged with
words of different semantic meaning of partition $2$ such as ‘data science’,
‘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. However, we can weight (topic proportion) average of words
within a partition and concatenate ($\oplus$) the average word vectors across
partitions to represent document ($\vec{v}_{d_{n}}$), as is done in our
proposed method P-SIF. By doing this, words belonging to different semantic
topics are separated by concatenation ($\oplus$) as they represent separate
meanings, whereas words in similar topics are simply averaged since they
represent the same meaning. For example, average of words belonging to
partition $1$ such as ‘graphical’, ‘design’, and ‘data’ are concatenated to
average of words in partition $2$ such as ‘data science’, ‘model’, and ‘data’.
The final document vector $\vec{v}_{d_{n}}$ is represented in a higher $5$
$\times$ $d$ dimension vector space, thus having more representational power
($d$ is the dimension of word vectors). Overall, the $5$ different semantic
topics are taken into account for representation. Additionally, this
representation also takes the weight according to which each word belongs to
various topics into account, meaning it handles words’ multi-sense natures.
For example, ‘data’ belongs 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.

## The Proposed Algorithm: P-SIF

In this section, we present the new proposed document embedding learning
method in algorithm 1. The feature formation algorithm can be divided into
three major steps:

Sparse Dictionary Learning for Word Vectors (Algo 1: Lines 1 \- 1):  Given
word vectors $v_{w}\in R^{d}$, a sparsity parameter $k$, and an upper bound
$K$ , we find a set of unit norm vectors
$\vec{A}_{1},\vec{A}_{2},\ldots,\vec{A}_{K}$, such that
$\vec{v}_{w}=\sum_{j=1}^{K}\alpha_{(w,j)}\vec{A}_{j}+\vec{\eta}_{w}$ where at
most $k$ out of $K$ of the coefficients $\alpha_{(w,1)},\ldots,\alpha_{(w,K)}$
are nonzero (so-called sparsity constraint), and $\vec{\eta}_{w}$ is a noise
vector. Sparse coding is usually solved for a given $K$ and $k$ by using
alternating minimization such as k-svd (?) to find the $\vec{A}_{i}^{\prime}$s
that minimize the following $L_{2}$-reconstruction error:
$\|\vec{v}_{w}-\sum_{j=1}^{K}\alpha_{(w,j)}\vec{A}_{j}\|$. (?) show that
multiple 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.
Additionally, the atoms of sparse coding ($\vec{A}_{1},\ldots,\vec{A}_{K}$)
over word-vectors ($\vec{v}_{w}$) represent all prominent topics in the
corpus. For a given word $w$, the $k$ non-zero coefficient of $\alpha_{w}$
essentially represents the distribution of words over topics. Furthermore,
restricting $K$ to be much smaller than the number of the words ensures that
the same topic needs to be used for multiple words. The learned $\vec{A}_{j}$
is a significant topic because the sparse coding ensures that each basis
element is softly chosen by many words.

Sparse Dictionary Learning vs. Overlapping Clustering:  Sparse coding can also
be treated as a linear algebraic analogue of overlapping clustering, where the
$\vec{A}_{i}$’s act as cluster centers and each $\vec{v}_{w}$ is assigned to
each cluster in a soft way (using the coefficients $\alpha_{(w,j)}$, of which
only $k$ out of $K$ are non-zero) to a linear combination of at most $k$
clusters. In practice, sparse coding optimization produces coefficients
$\alpha_{(w,j)}$ which are almost all positive, even though unconstrained. One
can use overlapping clustering where each word belongs to every cluster with
some probability $P(c_{k}|w_{i})$ which can be thought of as a substitute for
$\alpha_{(w,k)}$, similar to the approach in SCDV (?). Instead of GMM, we use
a dictionary learning-based approach which imposes a sparsity constraint
implicitly during optimization through regularization. Additionally, such high
dimensional data structure regularizers, e.g., sparse encodings, help in
overcoming the curse of high dimensionality. For single-sentence documents
with a small number of topics, it is better to use overlapping clustering
because of an easier unconstrained optimization. However, in case of multi-
sentence documents where the number of topics is large, dictionary learning
performs better than overlapping clustering due to 1) Sparse constraint
optimization forces non-redundant clusters (minimally sufficient
$\\#$clusters) and 2) The sparse constraint diminishes the noise from the long
tail of word-cluster assignments $P(c_{k}|w_{i})$ (?; ?; ?).

Word Topics Vector Formation (Algo 1: Lines 1 \- 1):  For single sentence
documents all words of a document belong to a single topic. However, for
multi-sentence documents, words of a document generally originate from
multiple topics. To capture this, topic modeling algorithms such as LDA (?)
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 such as word vectors into account. Since our
multi-sentence documents have words from multiple topics, a simple averaging
technique will not work. Hence, we concatenate the word embeddings over words’
topic distributions. This helps to represent semantically similar words in the
same topic, while words which are semantically different are represented in
different topics. Concatenation of word embeddings over topics also helps in
the expression of words’ multi-sense nature. For each word $\vec{w}$, we
create $K$ different word-cluster vectors of $d$ dimensions $\vec{cv}_{wk}$ by
weighting the word embedding with its learned dictionary coefficient
$\alpha_{w,k}$ of the $k^{th}$ context. 333Empirically, we observed that this
weighting generally improves the performance. We then concatenate all the $K$
word-cluster vectors $\vec{cv}_{wk}$ into a $K\times d$ dimensional embedding
to form a word-topic vector $\vec{tv}_{w}$ $\in$ $R^{K\times d}$. We weigh
word-vectors by coefficients of the learned dictionary to capture the cross
correlation $({\alpha_{i}}{\alpha_{j}})$ between topics. The word-topic-vector
$\vec{tv_{w}}$, which we average to represent documents, captures both local
and global semantics.

Data: $d$ dimensional Word embeddings $\\{\vec{v}_{w}:w\in V\\}$ where word
$w$ is in vocabulary $V$. Documents $\\{d_{n}:d_{n}\in D\\}$, a set of
sentences $D$ in corpus $C$, parameter $a$ and estimated unigram probability
$\\{p(w):w\in V\\}$ of word $w$ in $C$, a sparsity parameter $k$, and an upper
bound $K$.

Result: Document vectors $\\{{\vec{v}}_{d_{n}}:d_{n}\in D\\}$

/* Dictionary learning on word-vectors */

1 for  _each word $w$ $in$ $V$_ do

2 $\vec{v}_{w}$ $=$ $\sum_{j=1}^{K}$ $\alpha_{w,j}\vec{A}_{j}$ $+$
$\vec{\eta}_{w}$;

3

4 end for

/* Word topic-vector formation */

5 for  _each word $w$ $in$ $V$_ do

6 for  _each coefficient, $\alpha_{w,k}$ of word $w$_ do

7 $\vec{cv}_{w,k}$ $\leftarrow$ $\vec{v}_{w}$ $\times$ $\alpha_{w,k}$;

8

9 end for

10 $\vec{tv}_{w}$ $\leftarrow$ $\bigoplus_{k=1}^{K}$ $\vec{cv}_{wk}$ ;

/* $\bigoplus$ is concatenation, $\times$ is scalar vector multiplication */

11

12 end for

/* SIF reweighed embedding */

13 for  _each document $d_{n}$ in $D$_ do

14 ${\vec{v}}_{d_{n}}$ $\leftarrow$ $\frac{1}{|d_{n}|}$ $\sum_{w\in
d_{n}}\frac{a}{a+p(w)}$ $\vec{tv}_{w}$;

15

16 end for

17 Form a matrix $X$ whose columns are $\\{\vec{v}_{d_{n}}:d_{n}\in D\\}$, and
let $\vec{u}$ be the first singular vector;

18 for  _each document $d_{n}$ $\in$ $D$_ do

19 ${\vec{v}}_{d_{n}}$ $\leftarrow$ ${\vec{v}}_{d_{n}}$ \-
$\vec{u}\vec{u}^{T}{\vec{v}}_{d_{n}}$ ;

20

21 end for

Algorithm 1 P-SIF Embedding

SIF Weight Averaging and Common Component Removal (Algo 1: Lines 1 \- 1):
Finally, for all words appearing in document $D_{n}$, we weight the word-
topics vectors $\vec{tv}_{i}$ by smooth inverse frequency
($\frac{a}{a+p(w)}$). Next, we remove the common contexts from the weighted
average document vectors by removing the first principal component from the
weighted average vectors. 444We did not remove the common component from final
vectors when we used Doc2VecC-initialized (?) word vectors with P-SIF. Because
frequent words’ word-vectors become close to $\vec{0}$. Common component
removal reduces the noise and redundancy from the document vectors which makes
the representations more discriminating. (?) empirically shows that SIF
weighting outperforms the tf-idf weighting. However, they only use simple
averaging to represent a sentence. Detailed code architecture of P-SIF is in
the supplementary material.
555https://vgupta123.github.io/docs/appendix˙aaai2020.pdf

Derivation of P-SIF Embeddings : We provide theoretical justifications by
showing connections of P-SIF with random-walk based latent variable models (?;
?; ?). Full derivations are provided in the supplementary material 5.

## Kernels meet Embeddings

In this section, we present one of the novelties of this work where we show
that many common sentence embeddings can be represented as similarity kernels
over word and topic vectors. Let $D_{A}$ and $D_{B}$ represent two documents
containing $n$ and $m$ words respectively. ${w^{A}_{1},w^{A}_{2}\ldots
w^{A}_{n}}$ denotes $D_{A}$’s words and ${w^{B}_{1},w^{B}_{2}\ldots
w^{B}_{m}}$ denotes $D_{B}$’s words.

  1. 1.

Simple Word Vector Averaging :
$K^{1}(D_{A},D_{B})=\frac{1}{nm}\sum_{i=1}^{n}\sum_{j=1}^{m}\langle\vec{v}_{w^{A}_{i}}\cdot\vec{v}_{w^{B}_{j}}\rangle$

  2. 2.

TWE: Topical Word Embeddings (?) :
$K^{2}(D_{A},D_{B})=\frac{1}{nm}\sum_{i=1}^{n}\sum_{j=1}^{m}\langle\vec{v}_{w^{A}_{i}}\cdot\vec{v}_{w^{B}_{j}}\rangle+\langle\vec{tv}_{w^{A}_{i}}\cdot\vec{t}_{w^{B}_{j}}\rangle$

  3. 3.

P-SIF: Partition Word Vector Averaging (Our approach) :
$K^{3}(D_{A},D_{B})=\frac{1}{nm}\sum_{i=1}^{n}\sum_{j=1}^{m}\langle\vec{v}_{w^{A}_{i}}\cdot\vec{v}_{w^{B}_{j}}\rangle\times\langle\vec{t}_{w^{A}_{i}}\cdot\vec{t}_{w^{B}_{j}}\rangle$

  4. 4.

Relaxed Word Mover Distance (?) :
$K^{4}(D_{A},D_{B})=\frac{1}{n}\sum_{i=1}^{n}\max_{j}\langle\vec{v}_{w^{A}_{i}}\cdot\vec{v}_{w^{B}_{j}}\rangle$

Here, $\vec{v}_{w}$ represents the word vector of word $w$ and
$\vec{t}_{w}=\alpha_{w}$ $\in$ $R^{K}$ represents the topic vector of word
$w$, where $K$ is the number of topics. $\langle\vec{a}\cdot\vec{b}\rangle$
represents the dot product of two vectors $\vec{a}$ and $\vec{b}$. $c\times d$
represents the scalar product of $c$ and $d$. $\bigoplus$ represents the row-
wise concatenation of the vectors. Refer to the Supplementary material 5 for
the detailed proof.

## Experimental Results

We perform a comprehensive set of experiments on several text similarity and
multiclass or multilabel text classification tasks. Due to limited space, some
details on experiments are in the Supplementary material 5.

### Textual Similarity Task

Datasets and Baselines:  We perform our experiments on the SemEval dataset
(2012 - 2017). These experiments involve $27$ semantic textual similarity
(STS) tasks (2012 - 2016) (?; ?) the SemEval 2015 Twitter task (?), and the
SemEval 2014 Semantic relatedness task (?). The objectives of these tasks are
to predict the similarity between two sentences. We compare our approach with
several unsupervised, semi-supervised and supervised embedding baselines
mostly taken from (?; ?; ?). Details on the baselines are listed below:

Unsupervised: We used ST, avg-GloVe, tfidf-GloVe, and GloVe + WR as a
baseline. ST denotes the skip-thought vectors by (?), avg-GloVe denotes the
unweighted average of the GloVe Vectors by (?) 666We used the 300-dimensional
word vectors that are publicly available at
http://nlp.stanford.edu/projects/glove/., and tfidf-Glove denotes the tf-idf
weighted average of GloVe vectors. We also compared our method with the SIF
weighting ($W$) common component removal ($R$) GloVe vectors (GloVe + $WR$) by
(?). For STS 16, we also compared our embedding with Skip-Thoughts (?), BERT
pretrained embedding average (?) , Universal Sentence Encoder (?) and Sent2Vec
(?) embeddings.

Semi-Supervised: We used avg-PSL, PSL + WR, and the avg-PSL used the
unweighted average of the PARAGRAM-SL999 (PSL) word vectors by (?) as a
baseline, obtained by training on PPDB dataset(?). The word vectors are
trained using unlabeled data. Furthermore, sentence embeddings are obtained
from unweighted word vectors averaging. We also compared our method with the
SIF weighting (W) common component removal (R) PSL word vectors (PSL + WR) by
(?).

Supervised: We compared our method with PP, PP-proj., DAN, RNN, iRNN, LSTM
(o.g), LSTM (no) and GRAN. All these methods are initialized with PSL word
vectors and then trained on the PPDB dataset (?). PP (?) is the average of
word vectors, while PP-proj is the average of word vectors followed by a
linear projection. The word vectors are updated during the training. DAN
denotes the deep averaging network (?). RNN is a Recurrent neural network,
iRNN is the identity activated Recurrent Neural Network based on identity-
initialized weight matrices. The LSTM is the version from (?), either with
output gates (denoted as LSTM (o.g.)) or without (denoted as LSTM (no)). GRAN
denotes state of the art supervised averaging based Gated Recurrent Averaging
Network from (?). For STS 16 we also compared our embedding with Tree-LSTM (?)
embedding.

Experimental Settings: We use the Pearson’s coefficient between the predicted
and the ground-truth scores for the evaluation. We use the PARAGRAM-SL999
(PSL) from (?) as word embeddings, obtained by training on the PPDB (?)
dataset 777For a fair comparison with SIF we use PSL vectors instead of
unsupervised GloVe and Word2Vec vectors.. We use the fixed weighting parameter
$a$ 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 the word-vectors. We fix the non-zero coefficient $k$
= $K/2$, for the SIF experiments. For the GMM-based partitioning of the
vocabulary, we tune the number of clusters’ parameter $K$ through a 5-fold
cross validation.

Table 1: Experimental results (Pearson’s r $\times$ 100) on textual similarity
tasks. Many results are collected from (?), DAN (?) and (?) (GRAN) except for
tfidf-GloVe.

Tasks | PP | PP | DAN | RNN | iRNN | LSTM | LSTM | GRAN | ST | Avg | tfidf | Avg | Glove | PSL | PSIF
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
|  | proj |  |  |  | (no) | (o.g.) |  |  | Glove | Glove | PSL | +WR | +WR | +PSL
STS’12 | 58.7 | 60.0 | 56.0 | 48.1 | 58.4 | 51.0 | 46.4 | 62.5 | 30.8 | 52.5 | 58.7 | 52.8 | 56.2 | 59.5 | 65.7
STS’13 | 55.8 | 56.8 | 54.2 | 44.7 | 56.7 | 45.2 | 41.5 | 63.4 | 24.8 | 42.3 | 52.1 | 46.4 | 56.6 | 61.8 | 64.0
STS’14 | 70.9 | 71.3 | 69.5 | 57.7 | 70.9 | 59.8 | 51.5 | 75.9 | 31.4 | 54.2 | 63.8 | 59.5 | 68.5 | 73.5 | 74.8
STS’15 | 75.8 | 74.8 | 72.7 | 57.2 | 75.6 | 63.9 | 56.0 | 77.7 | 31.0 | 52.7 | 60.6 | 60.0 | 71.7 | 76.3 | 77.3
Sick’14 | 71.6 | 71.6 | 70.7 | 61.2 | 71.2 | 63.9 | 59.0 | 72.9 | 49.8 | 65.9 | 69.4 | 66.4 | 72.2 | 72.9 | 73.4
Twit15 | 52.9 | 52.8 | 53.7 | 45.1 | 52.9 | 47.6 | 36.1 | 50.2 | 24.7 | 30.3 | 33.8 | 36.3 | 48.0 | 49.0 | 54.9

Table 2: P-SIF comparison with the recent embedding techniques on various STS
tasks. Baselines taken from (?), (?), (?), (?), (?) and (?)

Task | ELMo | ELMo | Bert(pr) | USE | p-mean | Fast | Skip | Infer | Char | WME | PSIF | u-SIF
---|---|---|---|---|---|---|---|---|---|---|---|---
| orig+all | orig+top | Avg. |  |  | Text | Thoughts | Sent | pharse | +PSL | +PSL | +PSL
STS 12 | 55 | 54 | 53 | 65 | 54 | 58 | 41 | 61 | 66 | 62.8 | 65.7 | 65.8
STS 13 | 51 | 49 | 67 | 68 | 52 | 58 | 29 | 56 | 57 | 56.3 | 63.98 | 65.2
STS 14 | 63 | 62 | 62 | 64 | 63 | 65 | 40 | 68 | 74.7 | 68.0 | 74.8 | 75.9
STS 15 | 69 | 67 | 73 | 77 | 66 | 68 | 46 | 71 | 76.1 | 64.2 | 77.3 | 77.6
STS 16 | 64 | 63 | 67 | 73 | 67 | 64 | 52 | 77 | - | - | 73.7 | 72.3
Average | 60.4 | 59 | 64.4 | 69.4 | 60.4 | 62.6 | 41.6 | 66.6 | 68.5 | 62.9 | 71.1 | 71.4

Table 3: Comparison of P-SIF (SGNS) with the recently proposed word mover
distance and word mover embedding (?) based on accuracy. In $\pm x$, $x$ is
the variance across several runs.

Dataset | Bbcsport | Twitter | Ohsumed | Classic | Reuters | Amazon | 20NG | Recipe-L
---|---|---|---|---|---|---|---|---
SIF(GloVe) | 97.3 $\pm$ 1.2 | 57.8 $\pm$ 2.5 | 67.1 | 92.7 $\pm$ 0.9 | 87.6 | 94.1 $\pm$ 0.2 | 72.3 | 71.1 $\pm$ 0.5
Word2Vec Avg | 97.3 $\pm$ 0.9 | 72.0 $\pm$ 1.5 | 63 | 95.2 $\pm$ 0.4 | 96.9 | 94.0 $\pm$ 0.5 | 71.7 | 74.9 $\pm$ 0.5
PV-DBOW | 97.2 $\pm$ 0.7 | 67.8 $\pm$ 0.4 | 55.9 | 97.0 $\pm$ 0.3 | 96.3 | 89.2 $\pm$ 0.3 | 71 | 73.1 $\pm$ 0.5
PV-DM | 97.9 $\pm$ 1.3 | 67.3 $\pm$ 0.3 | 59.8 | 96.5 $\pm$ 0.7 | 94.9 | 88.6 $\pm$ 0.4 | 74 | 71.1 $\pm$ 0.4
Doc2VecC | 90.5 $\pm$ 1.7 | 71.0 $\pm$ 0.4 | 63.4 | 96.6 $\pm$ 0.4 | 96.5 | 91.2 $\pm$ 0.5 | 78.2 | 76.1 $\pm$ 0.4
KNN-WMD | 95.4 $\pm$ 1.2 | 71.3 $\pm$ 0.6 | 55.5 | 97.2 $\pm$ 0.1 | 96.5 | 92.6 $\pm$ 0.3 | 73.2 | 71.4 $\pm$ 0.5
SCDV | 98.1 $\pm$ 0.6 | 74.2 $\pm$ 0.4 | 53.5 | 96.9 $\pm$ 0.1 | 97.3 | 93.9 $\pm$ 0.4 | 78.8 | 78.5$\pm$ 0.5
WME | 98.2 $\pm$ 0.6 | 74.5 $\pm$ 0.5 | 64.5 | 97.1 $\pm$ 0.4 | 97.2 | 94.3 $\pm$ 0.4 | 78.3 | 79.2 $\pm$ 0.3
P-SIF | 99.05 $\pm$ 0.9 | 73.39 $\pm$ 0.9 | 67.1 | 96.95 $\pm$ 0.5 | 97.67 | 94.17 $\pm$ 0.3 | 79.15 | 78.24 $\pm$ 0.3
P-SIF (Doc2VecC) | 99.68 $\pm$ 0.9 | 72.39 $\pm$ 0.9 | 67.1 | 97.7 $\pm$ 0.5 | 97.62 | 94.83 $\pm$ 0.3 | 86.31 | 77.61 $\pm$ 0.3

Results and Analysis: The average results for each year are reported in Tables
1 and 2. We denote our embeddings by P-SIF $+$ PSL ($+$ PSL denotes using the
PSL word vectors). We report the average results for the STS tasks. The
detailed results on each sub-dataset are in the Supplementary material 5. We
observe that P-SIF \+ PSL outperforms PSL + WR on all datasets, thus
supporting the usefulness of our partitioned averaging. Despite being simple,
our method outperforms many complicated methods such as seq2seq, Tree-LSTM(?),
and Skip-Thoughts(?). We observe that partitioning through overlapping
clustering algorithms such as GMM generates a better performance compared to
partitioning through sparse dictionary algorithms such as k-svd for some
Semantic Textual Similarity (STS) task datasets. The main reason for this
peculiar observation is related to the fact that some STS datasets contain
documents which are single sentences of a maximum length of $40$ words. As
discussed earlier (sparse dictionary learning vs. overlapping clustering), for
single sentence documents with a small number of topics, overlapping
clustering optimizes better than sparse dictionary learning. Therefore, we use
GMM for partitioning words into suitable clusters for some STS tasks. But both
k-svd and GMM outperform simple averaging (SIF) by significant margins on most
STS tasks. 888k-svd always outperforms GMM on both classification datasets
since the documents are multi-sentence with $\\#$words $>>$ $40$. We also
report qualitative results with real examples in the Supplementary 5.

### Text Classification Task

The document embeddings obtained by our method can be used as direct features
for many classification tasks.

Datasets and Baselines:  We run multi-class experiments on 20NewsGroup
dataset, 999https://bit.ly/2pqLCaN and multi-label classification experiments
on Reuters-21578 dataset. 101010https://goo.gl/NrOfu We use script for
preprocessing the dataset. 111111https://gist.github.com/herrfz/7967781 We
consider several embedding baselines mostly taken from (?; ?; ?). More details
on experimental settings and hyper-parameters’ values are described in the
Supplementary material 5. We considered the following baselines: The Bag-of-
Words (BoW) model (?), the Bag of Word Vector (BoWV) (?) model, Sparse
Composite Document Vector (SCDV) (?) 121212https://github.com/dheeraj7596/SCDV
paragraph vector models (?), Topical word embeddings (TWE-1) (?), Neural
Tensor Skip-Gram Model (NTSG-1 to NTSG-3) (?), tf-idf weighted average word-
vector model(?) and weighted Bag of Concepts (weight-BoC) (?) where we built
document-topic vectors by counting the member words in each topic, and
Doc2VecC (?) where averaging and training of word vectors are done jointly.
Moreover, we used SIF (?) 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 (?), w2v-LDA (?), LDA (?), TV+MeanWV (?)), LTSG (?),
Gaussian-LDA (?), Topic2Vec (?), Lda2Vec (?), MvTM (?) and BERT (?). For BERT,
we reported the results on the unsupervised pre-trained (pr) model because of
a fair comparison to our approach which is also unsupervised.

Experimental Settings: We fix the document embeddings and only learn the
classifier. We learn word vector embeddings 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 to either $40$ or $20$ (with Doc2vecC initialize word
vectors) and non-zero coefficient to $k$ = $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 (?). We evaluate the classifiers’
performance using standard metrics such as accuracy, macro-averaging
precision, recall and F-score for multiclass classification tasks.We evaluate
multi-label classifications’ performance using Precision@K, nDCG@k, Coverage
error, Label ranking average precision(LRAPS) and F1
score.131313https://goo.gl/4GrR3M

Table 4: Multi-class classification performance on 20NewsGroups. Model | Acc | Prec | Rec | Fmes
---|---|---|---|---
P-SIF (Doc2VecC) | 86.0 | 86.1 | 86.1 | 86.0
P-SIF | 85.4 | 85.5 | 85.4 | 85.2
BERT (pr) | 84.9 | 84.9 | 85.0 | 85.0
SCDV | 84.6 | 84.6 | 84.5 | 84.6
Doc2VecC | 84.0 | 84.1 | 84.1 | 84.0
RandHash | 83.9 | 83.99 | 83.9 | 83.76
BoE | 83.1 | 83.1 | 83.1 | 83.1
NTSG | 82.5 | 83.7 | 82.8 | 82.4
SIF | 82.3 | 82.6 | 82.9 | 82.2
BoWV | 81.6 | 81.1 | 81.1 | 80.9
LTSG | 82.8 | 82.4 | 81.8 | 81.8
p-means | 82.0 | 81.9 | 82.0 | 81.6
WTM | 80.9 | 80.3 | 80.3 | 80.0
w2v-LDA | 77.7 | 77.4 | 77.2 | 76.9
ELMo | 74.1 | 74.0 | 74.1 | 73.9
TV+MeanWV | 72.2 | 71.8 | 71.5 | 71.6
MvTM | 72.2 | 71.8 | 71.5 | 71.6
TWE-1 | 81.5 | 81.2 | 80.6 | 80.6
Lda2Vec | 81.3 | 81.4 | 80.4 | 80.5
LDA | 72.2 | 70.8 | 70.7 | 70.0
weight-AvgVec | 81.9 | 81.7 | 81.9 | 81.7
BoW | 79.7 | 79.5 | 79.0 | 79.0
weight-BOC | 71.8 | 71.3 | 71.8 | 71.4
PV-DBoW | 75.4 | 74.9 | 74.3 | 74.3
PV-DM | 72.4 | 72.1 | 71.5 | 71.5
Table 5: Performance on multi-label classification on Reuters.

Model | Prec | Prec | nDCG | Cover. | LRAPS | F1
---|---|---|---|---|---|---
| @1 | @5 | @5 | Error | Score |
P-SIF | 94.92 | 37.98 | 50.40 | 6.03 | 93.95 | 82.87
(Doc2VecC) |  |  |  |  |  |
P-SIF | 94.77 | 37.33 | 49.97 | 6.24 | 93.72 | 82.41
BERT (pr) | 93.8 | 37 | 49.6 | 6.3 | 93.1 | 81.9
SCDV | 94.20 | 36.98 | 49.55 | 6.48 | 93.30 | 81.75
Doc2VecC | 93.45 | 36.86 | 49.28 | 6.83 | 92.66 | 81.29
p-means | 93.29 | 36.65 | 48.95 | 10.8 | 91.72 | 77.81
BoWV | 92.90 | 36.14 | 48.55 | 8.16 | 91.46 | 79.16
TWE | 90.91 | 35.49 | 47.54 | 8.16 | 91.46 | 79.16
SIF | 90.40 | 35.09 | 47.32 | 8.98 | 88.10 | 76.78
PV-DM | 87.54 | 33.24 | 44.21 | 13.2 | 86.21 | 70.24
PV-DBoW | 88.78 | 34.51 | 46.42 | 11.3 | 87.43 | 73.68
AvgVec | 89.09 | 34.73 | 46.48 | 9.67 | 87.28 | 71.91
tfidf AvgVec | 89.33 | 35.04 | 46.83 | 9.42 | 87.90 | 71.97

Figure 2: Relative performance improvement of P-SIF and SCDV over SIF w.r.t
the average document length.

Results and Analysis: We observe that P-SIF outperforms all other methods by a
significant margin on both 20NewsGroup (Table 4) and Reuters (Table 5). We
observe that the dictionary learns more diverse and non-redundant topics
compared to overlapping clustering (SCDV) since we require only $40$
partitions rather than $60$ partitions in SCDV to obtain the best performance.
Simple tf-idf weighted averaging-based document representations do not show
significant improvement in performance by increasing word vector dimensions.
We achieve a $<0.4\%$ improvement in the accuracy when the word-vector
dimensions increase from $200$ to $500$ on 20NewsGroup. We observe that
increasing the word-vectors’ dimensions beyond $500$ does not improve SIF and
P-SIF’s performances. We further improve the performance on both datasets
using Doc2vecC-initialized (?) word-vectors which reduce word level noise in
the P-SIF representations. We represent this approach by P-SIF (Doc2VecC) in
Table 4 and Table 5. On 20NewsGroup, we require only $20$ partitions 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 report our results (micro-F1) on each of the $20$ classes
of 20NewsGroup in the Supplementary material 5. Additionally, we empirically
show that our proposed embedding P-SIF outperforms the word mover distance (?)
and performs comparable with the word mover embedding (?) in Table 3.
141414For datasets and baseline details refer to (?). Overall, P-SIF
outperforms most methods on several datasets by a significant margin.

Comparison with Contextual Embeddings:  Despite its simplicity, P-SIF is able
to outperform unsupervised contextual embeddings such as BERT (pr) and ELMo.
We assume the reason behind this is P-SIF’s focused ability to effectively
capture both global and local semantics in sparse higher dimension
representations. On other hand, BERT tries to capture both syntax and
semantics in single lower dimensional continuous representations. In both
classification and similarity tasks, understanding syntax is not as prominent
as understanding semantics.

## Analysis and Discussion

Effect of Document-Length: We conduct a small experiment to show that our
model performs better compared to SIF when we have large size documents. We
have divided $26$ STS datasets by average document length, i.e., the number of
words in documents in bins of ($10-20$, $20-30$, $30-40$, $40-50$) words.
Next, we average the relative performance improvement by P-SIF and SCDV by
accuracy with respect to SIF ($\frac{\text{Method}-\text{SIF}}{\text{SIF}}$%)
for datasets in each bin. In Figure 2, we observe that for complex multi-
sentence documents with more words, P-SIF performs relatively better than
SCDV. We also note that short texts require fewer number of partitions to
achieve their best performance which is quite intuitive since short text
documents will map into fewer topics.

Effect of Sparse Partitioning: 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. Empirically, on both datasets, we observe
that the dictionary learns more diverse and non-redundant topics compared to
overlapping clustering because of sparsity constraints. We require only $20$
partitions rather than $60$ in SCDV to obtain the best performance, meaning we
just need $(20*300)$ dimensions of embeddings (mostly sparse) compared to
$(60*300)$ dimensions of embeddings (mostly non-sparse). Thus, we obtain a
performance gain (F1-Score) of $~{}1.5\%$ with less than $0.33$ of the size of
the SCDV embeddings. Lastly, due to fewer dimensions, the feature formation
time is less in P-SIF.

## Conclusions and Future Work

We propose a novel unsupervised document feature formation technique based on
partitioned word vector averaging. Our embedding retains the simplicity of
simple weighted word averaging while taking documents’ topical structure into
account. Our simple and efficient approach achieves significantly better
performance on several textual similarity and textual classification tasks,
e.g., we outperform contextual embeddings such as BERT (pr) and ELMo. One
limitation of our work is its ignorance of words’ order and syntax. In the
future, we plan to address this problem and model partitioning, averaging, and
learning as a joint process.

## References

  * [Agirre et al. 2012] Agirre, E.; Diab, M.; Cer, D.; and Gonzalez-Agirre, A.  2012\.  Semeval-2012 task 6.  In Semeval, 385–393.  ACL.
  * [Agirre et al. 2016] Agirre, E.; Banea, C.; Cer, D.; Diab, M.; Gonzalez-Agirre, A.; Mihalcea, R.; Rigau, G.; and Wiebe, J.  2016\.  Semeval-2016.  In SemEval-2016, 497–511.
  * [Aharon et al. 2006] Aharon, M.; Elad, M.; Bruckstein, A.; et al.  2006\.  K-svd: An algorithm for designing overcomplete dictionaries for sparse representation.  IEEE Transactions on signal processing 54(11):4311.
  * [Arora et al. 2016a] Arora, S.; Li, Y.; Liang, Y.; Ma, T.; and Risteski, A.  2016a.  A latent variable model approach to pmi-based word embeddings.  TACL.
  * [Arora et al. 2016b] Arora, S.; Li, Y.; Liang, Y.; Ma, T.; and Risteski, A.  2016b.  Linear algebraic structure of word senses, with applications to polysemy.  arXiv preprint arXiv:1601.03764.
  * [Arora, Liang, and Ma 2017] Arora, S.; Liang, Y.; and Ma, T.  2017\.  A simple but tough-to-beat baseline for sentence embeddings.  ICLR.
  * [Blei et al. 2003] Blei, D. M.; Ng, D. M.; Jordan, M. I.; and Lafferty, J.  2003\.  Latent dirichlet allocation.  Journal of Machine Learning Research.
  * [Cer et al. 2018] Cer, D.; Yang, Y.; Kong, S.-y.; Hua, N.; Limtiaco, N.; John, R. S.; Constant, N.; Guajardo-Cespedes, M.; Yuan, S.; Tar, C.; et al.  2018\.  Universal sentence encoder.  arXiv preprint arXiv:1803.11175.
  * [Chen and Liu 2014] Chen, Z., and Liu, B.  2014\.  Topic modeling using topics from many domains, lifelong learning and big data.  In ICML, 703–711.
  * [Chen 2017] Chen, M.  2017\.  Efficient vector representation for documents through corruption.  ICLR.
  * [Conneau and Kiela 2018] Conneau, A., and Kiela, D.  2018\.  Senteval: An evaluation toolkit for universal sentence representations.  arXiv preprint arXiv:1803.05449.
  * [Das, Zaheer, and Dyer 2015] Das, R.; Zaheer, M.; and Dyer, C.  2015\.  Gaussian lda for topic models with word embeddings.  In ACL.
  * [Devlin et al. 2019] Devlin, J.; Chang, M.-W.; Lee, K.; and Toutanova, K.  2019\.  Bert: Pre-training of deep bidirectional transformers for language understanding.  NAACL.
  * [Dieng, Ruiz, and Blei 2019a] Dieng, A. B.; Ruiz, F. J.; and Blei, D. M.  2019a.  The dynamic embedded topic model.  arXiv preprint arXiv:1907.05545.
  * [Dieng, Ruiz, and Blei 2019b] Dieng, A. B.; Ruiz, F. J.; and Blei, D. M.  2019b.  Topic modeling in embedding spaces.  arXiv preprint arXiv:1907.04907.
  * [Ethayarajh 2018] Ethayarajh, K.  2018\.  Unsupervised random walk sentence embeddings: A strong but simple baseline.  ACL 2018 91\.
  * [Fu et al. 2016] Fu, X.; Wang, T.; Li, J.; Yu, C.; and Liu, W.  2016\.  Improving distributed word representation and topic model by word-topic mixture model.  In ACL, 190–205.
  * [Ganitkevitch, Van Durme, and Callison-Burch 2013] Ganitkevitch, J.; Van Durme, B.; and Callison-Burch, C.  2013\.  Ppdb: The paraphrase database.  In NAACL, 758–764.
  * [Gao et al. 2010] Gao, S.; Tsang, I. W.-H.; Chia, L.-T.; and Zhao, P.  2010\.  Local features are not lonely–laplacian sparse coding for image classification.  In CVPR, 3555–3561.  IEEE.
  * [Gers, Schraudolph, and Schmidhuber 2002] Gers, F. A.; Schraudolph, N. N.; and Schmidhuber, J.  2002\.  Learning precise timing with lstm recurrent networks.  Journal of machine learning research 3(Aug):115–143.
  * [Gupta et al. 2016] Gupta, V.; Karnick, H.; Bansal, A.; and Jhala, P.  2016\.  Product classification in e-commerce using distributional semantics.  In COLING, 536–546.
  * [Harris 1954] Harris, Z.  1954\.  Distributional structure.  Word 10:146–162.
  * [Iyyer et al. 2015] Iyyer, M.; Manjunatha, V.; Boyd-Graber, J.; and Daumé III, H.  2015\.  Deep unordered composition rivals syntactic methods for text classification.  In ACL, volume 1, 1681–1691.
  * [Kim, Kim, and Cho 2017] Kim, H. K.; Kim, H.; and Cho, S.  2017\.  Bag-of-concepts: Comprehending document representation through clustering words in distributed representation.  Neurocomputing.
  * [Kim 2014] Kim, Y.  2014\.  Convolutional neural networks for sentence classification.  In EMNLP, 1746–1751.
  * [Kiros et al. 2015] Kiros, R.; Zhu, Y.; Salakhutdinov, R. R.; Zemel, R.; Urtasun, R.; Torralba, A.; and Fidler, S.  2015\.  Skip thought vectors.  NeurIPS.
  * [Kusner et al. 2015] Kusner, M.; Sun, Y.; Kolkin, N.; and Weinberger, K.  2015\.  From word embeddings to document distances.  In International Conference on Machine Learning, 957–966.
  * [Law et al. 2017] Law, J.; Zhuo, H. H.; He, J.; and Rong, E.  2017\.  Ltsg: Latent topical skip-gram for mutually learning topic model and vector representations.  arXiv preprint arXiv:1702.07117.
  * [Le and Mikolov 2014] Le, Q. V., and Mikolov, T.  2014\.  Distributed representations of sentences and documents.  In ICML, volume 14, 1188–1196.
  * [Levy and Goldberg 2014] Levy, O., and Goldberg, Y.  2014\.  Neural word embedding as implicit matrix factorization.  In NeurIPS, 2177–2185.
  * [Li et al. 2016a] Li, S.; Chua, T.-S.; Zhu, J.; and Miao, C.  2016a.  Generative topic embedding: a continuous representation of documents.  In ACL.
  * [Li et al. 2016b] Li, X.; Chi, J.; Li, C.; Ouyang, J.; and Fu, B.  2016b.  Integrating topic modeling with word embeddings by mixtures of vmfs.  COLING 151––160.
  * [Ling et al. 2015] Ling, W.; Dyer, C.; Black, A.; and Trancoso, I.  2015\.  Two/too simple adaptations of wordvec for syntax problems.  In NAACL.
  * [Liu et al. 2015] Liu, Y.; Liu, Z.; Chua, T.-S.; and Sun, M.  2015\.  Topical word embeddings.  In AAAI, 2418–2424.
  * [Liu, Qiu, and Huang 2015] Liu, P.; Qiu, X.; and Huang, X.  2015\.  Learning context-sensitive word embeddings with neural tensor skip-gram model.  In IJCAI.
  * [Marelli et al. 2014] Marelli, M.; Bentivogli, L.; Baroni, M.; Bernardi, R.; Menini, S.; and Zamparelli, R.  2014\.  Semeval-2014 task 1.  In SemEval 2014.
  * [Mekala et al. 2017] Mekala, D.; Gupta, V.; Paranjape, B.; and Karnick, H.  2017\.  Scdv: Sparse composite document vectors using soft clustering over distributional representations.  In EMNLP, 659–669.
  * [Mikolov et al. 2010] Mikolov, T.; Karafiát, M.; Burget, L.; Černockỳ, J.; and Khudanpur, S.  2010\.  Recurrent neural network based language model.  In ISCA.
  * [Mikolov et al. 2013] Mikolov, T.; Sutskever, I.; Chen, K.; Corrado, G. S.; and Dean, J.  2013\.  Distributed representations of words and phrases and their compositionality.  In NeurIPS, 3111–3119.
  * [Mnih and Hinton 2007] Mnih, A., and Hinton, G.  2007\.  Three new graphical models for statistical language modelling.  In ICML, 641–648.  ACM.
  * [Moody 2016] Moody, C. E.  2016\.  Mixing dirichlet topic models and word embeddings to make lda2vec.  arXiv preprint arXiv:1605.02019.
  * [Nguyen et al. 2015] Nguyen, D. Q.; Billingsley, R.; Du, L.; and Johnson, M.  2015\.  Improving topic models with latent feature word representations.  ACL 3:299–313.
  * [Niu et al. 2015] Niu, L.; Dai, X.; Zhang, J.; and Chen, J.  2015\.  Topic2vec: learning distributed representations of topics.  In IALP, 193–196.  IEEE.
  * [Olshausen and Field 1997] Olshausen, B. A., and Field, D. J.  1997\.  Sparse coding with an overcomplete basis set: A strategy employed by v1?  Vision research 37(23):3311–3325.
  * [Pagliardini, Gupta, and Jaggi 2018] Pagliardini, M.; Gupta, P.; and Jaggi, M.  2018\.  Unsupervised Learning of Sentence Embeddings using Compositional n-Gram Features.  In NAACL 2018.
  * [Pennington, Socher, and Manning 2014] Pennington, J.; Socher, R.; and Manning, C.  2014\.  Glove: Global vectors for word representation.  In EMNLP, 1532–1543.
  * [Perone, Silveira, and Paula 2018] Perone, C. S.; Silveira, R.; and Paula, T. S.  2018\.  Evaluation of sentence embeddings in downstream and linguistic probing tasks.  arXiv preprint arXiv:1806.06259.
  * [Peters et al. 2018] Peters, M. E.; Neumann, M.; Iyyer, M.; Gardner, M.; Clark, C.; Lee, K.; and Zettlemoyer, L.  2018\.  Deep contextualized word representations.  In NAACL.
  * [Singh and Mukerjee 2015] Singh, P., and Mukerjee, A.  2015\.  Words are not equal: Graded weighting model for building composite document vectors.  In ICON.
  * [Socher et al. 2013] Socher, R.; Perelygin, A.; Wu, J. Y.; Chuang, J.; Manning, C. D.; Ng, A. Y.; Potts, C.; et al.  2013\.  Recursive deep models for semantic compositionality over a sentiment treebank.  In EMNLP.
  * [Tai, Socher, and Manning 2015] Tai, K. S.; Socher, R.; and Manning, C. D.  2015\.  Improved semantic representations from tree-structured long short-term memory networks.  In ACL, volume 1, 1556–1566.
  * [Wieting and Gimpel 2017] Wieting, J., and Gimpel, K.  2017\.  Revisiting recurrent networks for paraphrastic sentence embeddings.  ACL.
  * [Wieting et al. 2015] Wieting, J.; Bansal, M.; Gimpel, K.; Livescu, K.; and Roth, D.  2015\.  From paraphrase database to compositional paraphrase model and back.  TACL 3:345–358.
  * [Wieting et al. 2016] Wieting, J.; Bansal, M.; Gimpel, K.; and Livescu, K.  2016\.  Towards universal paraphrastic sentence embeddings.  ICLR.
  * [Wu et al. 2018] Wu, L.; Yen, I. E.-H.; Xu, K.; Xu, F.; Balakrishnan, A.; Chen, P.-Y.; Ravikumar, P.; and Witbrock, M. J.  2018\.  Word mover’s embedding: From word2vec to document embedding.  In EMNLP.
  * [Xu, Callison-Burch, and Dolan 2015] Xu, W.; Callison-Burch, C.; and Dolan, B.  2015\.  Semeval-2015 task 1.  In SemEval 2015, 1–11.
  * [Yang et al. 2009] Yang, J.; Yu, K.; Gong, Y.; and Huang, T.  2009\.  Linear spatial pyramid matching using sparse coding for image classification.  In CVPR, 1794–1801.  IEEE.

##  Appendix A Derivation of P-SIF Embeddings

To derive the P-SIF embedding, we propose a generative model which treats
corpus generation as a dynamic process where the $t^{th}$ word is produced at
step $t$. This process is driven by random walk over a unit norm sphere with
the center at the origin. Let $\vec{v}_{c_{t}}$ be the $d$ dimensional vector
from the origin to the current walk point at time $t$. We call this vector the
context vector $\vec{v}_{c_{t}}$ as it represents the context in the
discussion. Let $Z_{c}$ represent the partition function for the random
context vector $\vec{v}_{c_{t}}$, given by
$Z_{c}=\sum_{w}\exp(\langle\vec{v}_{c_{t}},\vec{v}_{w}\rangle)$. $c_{0}$ and
$\vec{v}_{c_{0}}$ represent a common context and its corresponding $d$
dimensional context vector based on syntax.

Using log linear model of (?), we define the probability of observing a word
$w$ from the random walk with current context $c_{t}$ at time $t$ as

$Pr[w|c_{t}]\propto\exp(\langle\vec{c}_{t},\vec{v}_{w}\rangle)$ (1)

It is easy to show that such random walk under some reasonable assumptions (?)
can give word-word co-occurrence probabilities similar to empirical works like
word2vec (?) and GloVe (?). To account for frequent stop-words which occur
more often regardless of context and the common context related to document
syntax, two correction terms need be added: one based on $p(w)$ and the other
on the common context vector $\vec{v}_{c_{0}}$ in Equation (1). These terms
allow words with a low inner product with $\vec{c}_{t}$ a chance to appear
either from $p(w)$ if they are frequent or by the common context $\vec{c}_{0}$
if they have a large dot product with $\vec{c}_{0}$. Given a context vector
$c_{t}$, the probability of a word $w$ in document $d$ being generated by
context $c_{t}$ is given by,

$Pr[w|c_{t}]=\lambda
p(w)+(1-\lambda)\frac{\exp(\langle\vec{c}^{\prime}_{t},\vec{v}_{w}\rangle)}{Z_{c^{\prime}_{t}}}$
(2)

where $\vec{c^{\prime}_{t}}$ = $\beta\vec{c}_{0}+(1-\beta)$ $\vec{c}_{t}$,
$\langle\vec{c}_{0},\vec{c}_{t}\rangle$ $=$ $0$, $\lambda$ and $\beta$ are
scalar hyper-parameters.

For generating a document from the above random walk-based latent variable
model, we consider the following assumptions:

  1. 1.

Context vector ($\vec{v}_{c_{0}}$) does not change significantly while words
are generated from the random walk, as shown by (?), except the jumps due to
topic change.

  2. 2.

Total number of topics in the entire corpus is $K$, which can be determined by
sparse dictionary learning as shown by (?) over word vectors $\vec{v}_{w}$.

  3. 3.

Word vectors $\vec{v}_{w}$ are uniformly distributed, thus making the
partition function $Z_{c}$ roughly the same in all directions for a given
context $c$ emerging from each of the $K$ topics.

For a document $d$, the likelihood of document is being generated by the $K$
contexts is given by:

$p(d|\\{c_{1},c_{2}\ldots c_{K}\\})\propto\prod_{j=1}^{K}{\prod_{\\{w\in
d\\}}p(w|c_{j})}$ (3) $\begin{split}=\prod_{j=1}^{K}\prod_{w\in
d}\Big{[}\lambda
p(w)+(1-\lambda)\frac{\exp(\langle\vec{v}_{w},\vec{v}_{{c}_{j}}\rangle)}{Z_{j}}\Big{]}\end{split}$
(4) $\begin{split}\text{Let, }f_{w}(c_{j})=\log\Big{[}\lambda
p(w)+(1-\lambda)\frac{\exp(\langle\vec{v}_{w},\vec{v}_{{c}_{j}}\rangle)}{Z_{j}}\Big{]}\end{split}$
(5)

Here, $p(w|c_{j})$ is the probability that word $w$ is generated by context
$c_{j}$, the value of which is determined by 1) The overall frequency of word
$w$ in the corpus, i.e., prior probability ($p(w)$) and 2) The relative
frequency of $w$ appearing with context $j$ with respect to other contexts
(determined by $\alpha_{(w,j)}$).

Using simple algebra and treating $p(w)$ as a constant, we can show that
$\nabla(f_{w}(c_{j}))$ equals,

$\begin{split}\frac{1}{\lambda
p(w)+(1-\lambda)\exp(\langle\vec{v}_{w},\vec{v}_{c_{j}}\rangle)/Z_{j}}*\frac{1-\lambda}{Z_{j}}\exp(\langle\vec{v}_{w},\vec{v}_{c_{j}}\rangle)\vec{v}_{w}\end{split}$
(6)

Then, by using the Taylor expansion, we can show

$\begin{split}f_{w}(c_{j})\approx
f_{w}(c_{j}=0)+\nabla(f_{w}(c_{j}=0))^{T}\vec{v}_{c_{j}}\end{split}$ (7)
$f_{w}(c_{j})\approx constant+\nabla(f_{w}(c_{j}=0))^{T}\vec{v}_{c_{j}}$ (8)

Therefore, the maximum likelihood estimator (MLE) for $\vec{v}_{c_{j}}$ on the
unit sphere (ignoring normalization) given $a=\frac{1-\lambda}{\lambda
Z_{j}}$, is approximately 151515Note that
$argmax_{c:\|\vec{c}\|=1}C+\langle\vec{c},\vec{g}\rangle=\frac{\vec{g}}{\|\vec{g}\|}$
for any constant C

$\operatorname*{arg\,max}\sum_{w\in d}f_{w}(c_{j})\propto\sum_{w\in
d}\frac{a}{p(w)+a}\vec{v}_{w}$ (9)

Thus, the MLE estimate is approximately a weighted average of the word-vectors
generated from context $j$ in document $d$ from the random walk. We can get
the overall context representation $\vec{v}_{c_{d}}$ of the document by simple
concatenation over all $K$ topics i.e.
$\vec{v}_{c_{d}}=\bigoplus_{j=1}^{K}\vec{v}_{c_{j}}$. Here, $\bigoplus$
represents the concatenation operation. For a document if no word is generated
from the context $c_{j}$ then we can substitute the context vector
$\vec{v}_{c_{j}}$ by a $\vec{0}$ vector to represent $\vec{v}_{c_{d}}$ in
$K\times d$ dimensions. The embedding of a sentence can be obtained by
$\vec{v}_{c_{s}}=\sum_{\\{w\in s\\}}\frac{a}{p(w)+a}\vec{v}_{w}$ where
$a=\frac{1-\lambda}{\lambda Z_{s}}$.

Relation to SIF model:  (?) show sentences can be represented as averaging of
word vectors, under the two assumptions:

  * •

uniform distribution of word vectors $\vec{v}_{w}$ which implies that the
partition function $Z_{t}$ is roughly the same in all directions for a
sentence.

  * •

context vector $\vec{v}_{c_{h}}$ remains constant while the words in the
sentence are emitted, implying the replacement of $\vec{v}_{c_{h}}$ in the
sentences by $\vec{v}_{c_{s}}$ and partition function $Z_{t}$ by $Z_{s}$.

However, the above assumptions do not hold true for a document with multiple
sentences where one can expect to have more frequent jumps during a random
walk due to topic change. 161616It is trivial to assume that these jumps occur
more frequently in multi-sentence documents because of more number of topics.
Instead of assuming a single context for the whole document $c_{h}$, we assume
that the total number of contexts over a given corpus is bounded by the number
of topics $K$ (as shown by (?)), and the random walk can perform jumps to
switch context from one context to the rest of $K-1$ contexts. The partition
function remains the same in all directions only for the words emerging from
the same context $c_{j}$ instead of the words coming from all the $K$
contexts. Thus, our approach is a strict generalization of the sentence
embedding approach by (?) which is a special case of $K=1$.

##  Appendix B Details of Textual Similarity Task

In this supplementary section, we present the details of the 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 B.
Our method outperforms all other methods from (?) and (?) 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. Our method was
also able to outperform state of the art supervised averaging based Gated
Recurrent Averaging Network (GRAN) (?) on $11$ datasets shown in Table B. Our
results also outperform state of the art methods on many recent supervised
embedding methods on the STS $16$ task (See Table
LABEL:table:sts16resultdetail).

Table 6: The STS tasks by year. Tasks with the same name in different years are different tasks STS12 | STS13 | STS14 | STS15 | STS16
---|---|---|---|---
MSRpar | headline | deft forum | anwsers-forums | headlines
MSRvid | OnWN | deft news | answers-students | plagiarism
SMT-eur | FNWN | headline | belief | posteditng
OnWN | SMT | images | headline | answer-answer
SMT-news |  | OnWN | images | question-question
|  | tweet news |  |

Table 7:  Experimental results (Pearson’s r $\times$ 100) on textual similarity tasks. The highest score in each row is in bold. The methods can be supervised (denoted as Su.), semi-supervised (Se.), or unsupervised (Un.). See the main text for description of the methods. Many results are collected from (?) and (?) (GRAN) except the tfidf-GloVe and our representation. TaskType |  Supervised |  UnSupervised |  Semi Supervised |  P-SIF
---|---|---|---|---
Tasks |  PP |  PP |  |  |  |  |  |  |  |  |  |  |  |  |
|  DAN |  RNN |  iRNN |  LSTM |  |  |  |  |  |  |  |  |  |  |
|  LSTM |  |  | (no) |  |  |  |  |  |  |  |  |  |  |
|  GRAN |  ST |  avg |  |  |  |  |  |  |  |  |  |  |  |
|  tfidf |  | Glove |  |  |  |  |  |  |  |  |  |  |  |
|  avg |  |  |  |  |  |  |  |  |  |  |  |  |  |
|  Glove |  |  |  |  |  |  |  |  |  |  |  |  |  |
|  PSL |  |  |  |  |  |  |  |  |  |  |  |  |  |
|  P-SIF |  |  |  |  |  |  |  |  |  |  |  |  |  |
| +PSL |  |  |  |  |  |  |  |  |  |  |  |  |  |
MSRpar | 42.6 | 43.7 | 40.3 | 18.6 | 43.4 | 16.1 | 9.3 | 47.7 | 16.8 | 47.7 | 50.3 | 41.6 | 35.6 | 43.3 | 52.4
MSRvid | 74.5 | 74.0 | 70.0 | 66.5 | 73.4 | 71.3 | 71.3 | 85.2 | 41.7 | 63.9 | 77.9 | 60.0 | 83.8 | 84.1 | 85.6
SMT-eur | 47.3 | 49.4 | 43.8 | 40.9 | 47.1 | 41.8 | 44.3 | 49.3 | 35.2 | 46.0 | 54.7 | 42.4 | 49.9 | 44.8 | 58.7
OnWN | 70.6 | 70.1 | 65.9 | 63.1 | 70.1 | 65.2 | 56.4 | 71.5 | 29.7 | 55.1 | 64.7 | 63.0 | 66.2 | 71.8 | 72.2
SMT-news | 58.4 | 62.8 | 60.0 | 51.3 | 58.1 | 60.8 | 51.0 | 58.7 | 30.8 | 49.6 | 45.7 | 57.0 | 45.6 | 53.6 | 59.5
STS’12 | 58.7 | 60.0 | 56.0 | 48.1 | 58.4 | 51.0 | 46.4 | 62.5 | 30.8 | 52.5 | 58.7 | 52.8 | 56.2 | 59.5 | 65.7
headline | 72.4 | 72.6 | 71.2 | 59.5 | 72.8 | 57.4 | 48.5 | 76.1 | 34.6 | 63.8 | 69.2 | 68.8 | 69.2 | 74.1 | 75.7
OnWN | 67.7 | 68.0 | 64.1 | 54.6 | 69.4 | 68.5 | 50.4 | 81.4 | 10.0 | 49.0 | 72.9 | 48.0 | 82.8 | 82.0 | 84.4
FNWN | 43.9 | 46.8 | 43.1 | 30.9 | 45.3 | 24.7 | 38.4 | 55.6 | 30.4 | 34.2 | 36.6 | 37.9 | 39.4 | 52.4 | 54.8
SMT | 39.2 | 39.8 | 38.3 | 33.8 | 39.4 | 30.1 | 28.8 | 40.3 | 24.3 | 22.3 | 29.6 | 31.0 | 37.9 | 38.5 | 41.0
STS’13 | 55.8 | 56.8 | 54.2 | 44.7 | 56.7 | 45.2 | 41.5 | 63.4 | 24.8 | 42.3 | 52.1 | 46.4 | 56.6 | 61.8 | 64.0
deft forum | 48.7 | 51.1 | 49.0 | 41.5 | 49.0 | 44.2 | 46.1 | 55.7 | 12.9 | 27.1 | 37.5 | 37.2 | 41.2 | 51.4 | 53.2
deft news | 73.1 | 72.2 | 71.7 | 53.7 | 72.4 | 52.8 | 39.1 | 77.1 | 23.5 | 68.0 | 68.7 | 67.0 | 69.4 | 72.6 | 75.2
headline | 69.7 | 70.8 | 69.2 | 57.5 | 70.2 | 57.5 | 50.9 | 72.8 | 37.8 | 59.5 | 63.7 | 65.3 | 64.7 | 70.1 | 70.2
images | 78.5 | 78.1 | 76.9 | 67.6 | 78.2 | 68.5 | 62.9 | 85.8 | 51.2 | 61.0 | 72.5 | 62.0 | 82.6 | 84.8 | 84.8
OnWN | 78.8 | 79.5 | 75.7 | 67.7 | 78.8 | 76.9 | 61.7 | 85.1 | 23.3 | 58.4 | 75.2 | 61.1 | 82.8 | 84.5 | 88.1
tweet news | 76.4 | 75.8 | 74.2 | 58.0 | 76.9 | 58.7 | 48.2 | 78.7 | 39.9 | 51.2 | 65.1 | 64.7 | 70.1 | 77.5 | 77.5
STS’14 | 70.9 | 71.3 | 69.5 | 57.7 | 70.9 | 59.8 | 51.5 | 75.8 | 31.4 | 54.2 | 63.8 | 59.5 | 68.5 | 73.5 | 74.8
ans-forum | 68.3 | 65.1 | 62.6 | 32.8 | 67.4 | 51.9 | 50.7 | 73.1 | 36.1 | 30.5 | 45.6 | 38.8 | 63.9 | 70.1 | 70.7
ans-student | 78.2 | 77.8 | 78.1 | 64.7 | 78.2 | 71.5 | 55.7 | 72.9 | 33.0 | 63.0 | 63.9 | 69.2 | 70.4 | 75.9 | 79.6
belief | 76.2 | 75.4 | 72.0 | 51.9 | 75.9 | 61.7 | 52.6 | 78 | 24.6 | 40.5 | 49.5 | 53.2 | 71.8 | 75.3 | 75.3
headline | 74.8 | 75.2 | 73.5 | 65.3 | 75.1 | 64.0 | 56.6 | 78.6 | 43.6 | 61.8 | 70.9 | 69.0 | 70.7 | 75.9 | 76.8
images | 81.4 | 80.3 | 77.5 | 71.4 | 81.1 | 70.4 | 64.2 | 85.8 | 17.7 | 67.5 | 72.9 | 69.9 | 81.5 | 84.1 | 84.1
STS’15 | 75.8 | 74.8 | 72.7 | 57.2 | 75.6 | 63.9 | 56.0 | 77.7 | 31.0 | 52.7 | 60.6 | 60.0 | 71.7 | 76.3 | 77.3
SICK’14 | 71.6 | 71.6 | 70.7 | 61.2 | 71.2 | 63.9 | 59.0 | 72.9 | 49.8 | 65.9 | 69.4 | 66.4 | 72.2 | 72.9 | 73.4
Twitter’15 | 52.9 | 52.8 | 53.7 | 45.1 | 52.9 | 47.6 | 36.1 | 50.2 | 24.7 | 30.3 | 33.8 | 36.3 | 48.0 | 49.0 | 54.9
Table 8: Experimental results (Pearson’s r $\times$ 100) on textual similarity
tasks on STS 16. The highest score in each row is in bold.

Proof:

$\vec{dv}^{A}=\frac{1}{n}\sum_{i=1}^{n}\vec{v}_{w^{A}_{i}}$ (10)
$\vec{dv}^{A}=\frac{1}{m}\sum_{j=1}^{m}\vec{v}_{w^{B}_{j}}$ (11)
$K^{1}(D_{A},D_{B})=\langle\vec{dv}^{A}\cdot\vec{dv}^{B}\rangle$ (12)

By substituting values from 10 and 11 to 12, we will get

$K^{1}(D_{A},D_{B})=\langle\frac{1}{n}\sum_{i=1}^{n}\vec{v}_{w^{A}_{i}}\cdot\frac{1}{m}\sum_{j=1}^{m}\vec{v}_{w^{B}_{j}}\rangle$
(13)
$K^{1}(D_{A},D_{B})=\frac{1}{nm}\langle\sum_{i=1}^{n}\vec{v}_{w^{A}_{i}}\cdot\sum_{j=1}^{m}\vec{v}_{w^{B}_{j}}\rangle$
(14)

Using the distributive property of dot product

$\langle\sum_{i=1}^{n}\vec{v}_{w^{A}_{i}}\cdot\sum_{j=1}^{m}\vec{v}_{w^{B}_{j}}\rangle=\sum_{i=1}^{n}\sum_{j=1}^{m}\langle\vec{v}_{w^{A}_{i}}\cdot\vec{v}_{w^{B}_{j}}\rangle$
(15)

By substituting 15 in 14, we will get

$K^{1}(D_{A},D_{B})=\frac{1}{nm}\sum_{i=1}^{n}\sum_{j=1}^{m}\langle\vec{v}_{w^{A}_{i}}\cdot\vec{v}_{w^{B}_{j}}\rangle$
(16)

$K^{2}(D_{A},D_{B})$ represents the document similarity between the documents
represented by topical word vectors (?)

Proof:

$\vec{dv}^{A}=\frac{1}{n}\sum_{i=1}^{n}\vec{tv}_{w^{A}_{i}}=\sum_{i=1}^{n}\alpha_{w^{A}_{i}}\oplus\vec{v}_{w^{A}_{i}}$
(17)
$\vec{dv}^{B}=\frac{1}{m}\sum_{j=1}^{m}\vec{tv}_{w^{B}_{i}}=\sum_{j=1}^{m}\alpha_{w^{B}_{i}}\oplus\vec{v}_{w^{B}_{i}}$
(18) $K^{2}(D_{A},D_{B})=\langle\vec{dv}^{A}\cdot\vec{dv}^{B}\rangle$ (19)

By substituting values from 17 and 18 to 19, we will get

$K^{2}(D_{A},D_{B})=\frac{1}{nm}\langle\sum_{i=1}^{n}\vec{tv}_{w^{A}_{i}}\cdot\sum_{j=1}^{m}\vec{tv}_{w^{B}_{j}}\rangle$
(20)

Using the distributive property of dot product

$K^{2}(D_{A},D_{B})=\frac{1}{nm}\sum_{i=1}^{n}\sum_{j=1}^{m}\langle\vec{tv}_{w^{A}_{i}}\cdot\vec{tv}_{w^{B}_{j}}\rangle$
(21)
$K^{2}(D_{A},D_{B})=\frac{1}{nm}\sum_{i=1}^{n}\sum_{j=1}^{m}\left\langle\big{(}\alpha_{w^{A}_{i}}\oplus\vec{v}_{w^{A}_{i}}\big{)}\cdot\big{(}\alpha_{w^{B}_{i}}\oplus\vec{v}_{w^{B}_{i}}\big{)}\right\rangle$
(22)

Using the distributive and scalar multiplication property of dot product

$\left\langle\big{(}\alpha_{w^{A}_{i}}\oplus\vec{v}_{w^{A}_{i}}\big{)}\cdot\big{(}\alpha_{w^{B}_{i}}\oplus\vec{v}_{w^{B}_{i}}\big{)}\right\rangle=\langle\alpha_{w^{A}}\cdot\alpha_{w^{B}}\rangle+\langle\vec{v}_{w^{A}_{i}}\cdot\vec{v}_{w^{B}_{i}}\rangle$
(23)

Since, $t_{w^{A}}$ = $\alpha_{w^{A}}$ and $t_{w^{B}}$ = $\alpha_{w^{B}}$

$\left\langle\big{(}\alpha_{w^{A}_{i}}\oplus\vec{v}_{w^{A}_{i}}\big{)}\cdot\big{(}\alpha_{w^{B}_{i}}\oplus\vec{v}_{w^{B}_{i}}\big{)}\right\rangle=\langle
t_{w^{A}}\cdot
t_{w^{B}}\rangle+\langle\vec{v}_{w^{A}_{i}}\cdot\vec{v}_{w^{B}_{i}}\rangle$
(24)

By substituting 24 in 22, we will get

$K^{2}(D_{A},D_{B})=\frac{1}{nm}\sum_{i=1}^{n}\sum_{j=1}^{m}\langle\vec{v}_{w^{A}_{i}}\cdot\vec{v}_{w^{B}_{j}}\rangle+\langle\vec{t}_{w^{A}_{i}}\cdot\vec{t}_{w^{B}_{j}}\rangle$
(25)

$K^{3}(D_{A},D_{B})$ represents the document similarity between the documents
represented by partition average word vectors (P-SIF)

Proof:

$\vec{dv}^{A}=\frac{1}{n}\sum_{i=1}^{n}\vec{tv}_{w^{A}_{i}}=\sum_{i=1}^{n}\bigoplus_{k=1}^{K}\alpha_{w^{A}_{i},k}\vec{v}_{w^{A}_{i}}$
(26)
$\vec{dv}^{B}=\frac{1}{m}\sum_{j=1}^{m}\vec{tv}_{w^{B}_{i}}=\sum_{j=1}^{m}\bigoplus_{k=1}^{K}\alpha_{w^{B}_{j},k}\vec{v}_{w^{B}_{i}}$
(27) $K^{3}(D_{A},D_{B})=\langle\vec{dv}^{A}\cdot\vec{dv}^{B}\rangle$ (28)

By substituting values from 26 and 27 in 28, we will get

$K^{3}(D_{A},D_{B})=\frac{1}{nm}\langle\sum_{i=1}^{n}\vec{tv}_{w^{A}_{i}}\cdot\sum_{j=1}^{m}\vec{tv}_{w^{B}_{j}}\rangle$
(29)

Using the distributive property of dot product

$K^{3}(D_{A},D_{B})=\frac{1}{nm}\sum_{i=1}^{n}\sum_{j=1}^{m}\langle\vec{tv}_{w^{A}_{i}}\cdot\vec{tv}_{w^{B}_{j}}\rangle$
(30)
$\begin{split}=\frac{1}{nm}\sum_{i=1}^{n}\sum_{j=1}^{m}\left\langle\big{(}\bigoplus_{k=1}^{K}\alpha_{w^{A}_{i},k}\vec{v}_{w^{A}_{i}}\big{)}\cdot\big{(}\bigoplus_{k=1}^{K}\alpha_{w^{B}_{j},k}\vec{v}_{w^{B}_{i}}\big{)}\right\rangle\end{split}$
(31)

Using distributive and scalar multiplication property of dot product

$\begin{split}\left\langle\big{(}\bigoplus_{k=1}^{K}\alpha_{w^{A}_{i},k}\vec{v}_{w^{A}_{i}}\big{)}\cdot\big{(}\bigoplus_{k=1}^{K}\alpha_{w^{B}_{j},k}\vec{v}_{w^{B}_{j}}\big{)}\right\rangle\\\
=\big{(}\sum_{k=1}^{K}(\alpha_{w^{A}_{i},k}\cdot\alpha_{w^{B}_{j},k})\big{)}\times\langle\vec{v}_{w^{A}_{i}}\cdot\vec{v}_{w^{B}_{i}}\rangle\end{split}$
(32)

Since, $t_{w^{A},k}$ = $\alpha_{w^{A},k}$ and $t_{w^{B},k}$ =
$\alpha_{w^{B},k}$

$\begin{split}\left\langle\big{(}\bigoplus_{k=1}^{K}\alpha_{w^{A},k}\vec{v}_{w^{A}_{i}}\big{)}\cdot\big{(}\bigoplus_{k=1}^{K}\alpha_{w^{B},k}\vec{v}_{w^{B}_{i}}\big{)}\right\rangle\\\
=\big{(}\sum_{k=1}^{K}(t_{w^{A}_{i},k}\cdot
t_{w^{B}_{j},k})\big{)}\times\langle\vec{v}_{w^{A}_{i}}\cdot\vec{v}_{w^{B}_{i}}\rangle\end{split}$
(33)
$\begin{split}\left\langle\big{(}\bigoplus_{k=1}^{K}\alpha_{w^{A},k}\vec{v}_{w^{A}_{i}}\big{)}\cdot\big{(}\bigoplus_{k=1}^{K}\alpha_{w^{B},k}\vec{v}_{w^{B}_{i}}\big{)}\right\rangle\\\
=\big{(}\sum_{k=1}^{K}t_{w^{A}_{i},k}\cdot
t_{w^{B}_{j},k}\big{)}\times\langle\vec{v}_{w^{A}_{i}}\cdot\vec{v}_{w^{B}_{i}}\rangle\end{split}$
(34)

From the definition of the dot product of vectors,

$\begin{split}\left\langle\big{(}\bigoplus_{k=1}^{K}\alpha_{w^{A},k}\vec{v}_{w^{A}_{i}}\big{)}\cdot\big{(}\bigoplus_{k=1}^{K}\alpha_{w^{B},k}\vec{v}_{w^{B}_{i}}\big{)}\right\rangle\\\
=\langle\vec{t}_{w^{A}_{i}}\cdot\vec{t}_{w^{B}_{j}}\rangle\times\langle\vec{v}_{w^{A}_{i}}\cdot\vec{v}_{w^{B}_{j}}\rangle\end{split}$
(35)

By subatituting 35 in 31, we will get

$K^{3}(D_{A},D_{B})=\frac{1}{nm}\sum_{i=1}^{n}\sum_{j=1}^{m}\langle\vec{v}_{w^{A}_{i}}\cdot\vec{v}_{w^{B}_{j}}\rangle\times\langle\vec{t}_{w^{A}_{i}}\cdot\vec{t}_{w^{B}_{j}}\rangle$
(36)

$K^{4}(D_{A},D_{B})$ represents the document similarity between the documents
represented by the relaxed word mover distance (?) when words of $D_{A}$ are
matched to $D_{B}$ Proof: From the definition of the relaxed word mover
distance in (?). Relaxed word mover maps each word $w_{i}^{A}$ of document
$D_{A}$ to the closest word $w_{j}^{B}$ of document $D_{B}$.

Since, word $w_{j}^{B}$ of document $D_{B}$ is closer to word $w_{i}^{A}$ of
document $D_{A}$, we will have

$w_{j}^{B}=\operatorname*{arg\,max}_{w_{j}^{B}}\langle\vec{v}_{w^{A}_{i}}\cdot\vec{v}_{w^{B}_{j}}\rangle$
(37)

Therefore, similarity contribution $K_{(i,j)}$ from word $w_{i}^{A}$ of
document $D_{A}$ is given by:

$K_{(i,j)}=\frac{1}{n}\max_{w_{j}^{B}}\langle\vec{v}_{w^{A}_{i}}\cdot\vec{v}_{w^{B}_{j}}\rangle$
(38)

Total similarity contribution from all the $n$ words of the document $d_{A}$:

$K^{4}(D_{A},D_{B})=\frac{1}{n}\sum_{i=1}^{n}K_{(i,j)}=\frac{1}{n}\sum_{i=1}^{n}\max_{w_{j}^{B}}\langle\vec{v}_{w^{A}_{i}}\cdot\vec{v}_{w^{B}_{j}}\rangle$
(39)

We can write $\max_{w_{j}^{B}}$ as $\max_{j}$, thus finally

$K^{4}(D_{A},D_{B})=\frac{1}{n}\sum_{i=1}^{n}\max_{j}\langle\vec{v}_{w^{A}_{i}}\cdot\vec{v}_{w^{B}_{j}}\rangle$
(40)

##  Appendix G Qualitative Example: Document Similarity

Let’s consider a corpus ($C$) with $N$ documents with the corresponding most
frequent vocabulary ($V$). Figure 3 represents the word-vectors space $V$,
where similar meaning words are closer. We can apply sparse coding and
partition the words-vector space into five (total topics $K=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 a significant proportion. Words
and corresponding vectors in these topic vector spaces are represented by
topic numbers in the subscript. Table 11 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 the 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, SIF represents the document as a single point in
the vector space and does not take account of different semantic meanings of
the topics. Whereas, in the P-SIF representation, we treat the five different
semantic topics distinctly. Words belonging to different semantic topics are
separated by concatenation ($\oplus$) as they represent different meanings,
whereas words coming from the same topic are averaged as they represent the
same meaning. The final document vector $\vec{v}_{d_{n}}$ has more
representational power as it is represented in a higher 5 $\times$ $d$
dimensional vector space. Thus, partitioned averaging with topic weighting is
important for representing documents. Empirically, P-SIF assigned a lower
score of $0.16$ (rescaled to a 0-1 scale) for sentences
($d_{n}^{1}$,$d_{n}^{2}$) where the ground truth is $0.15$ (rescaled to a 0-1
scale), whereas SIF gave similarity score of $0.57$ (0-1 scale), farther than
the ground score. Thus, we obtain a relative improvement of $98\%$ in the
error difference from the ground truth. Here, the simple averaging-based
embedding of $d_{n}^{1}$ and $d_{n}^{2}$, brings the document representations
closer. But partitioned based averaging, P-SIF, projects the documents farther
in a higher-dimensional space.

Table 11: STS Task 2012 MSRVid dataset similarity example pair. Here, P-SIF assigns a score of $0.16$ (rescaled to a 0-1 scale) to sentences ($d_{n}^{1}$,$d_{n}^{1}$), where the ground truth of $0.15$ (0-1 scale), whereas SIF assigns a similarity score of $0.57$ (rescaled to a 0-1 scale). Thus, we obtain a relative improvement of $98\%$ in the error difference. Here, $\oplus$ represents concatenation. $\vec{v}_{\mathrm{zero}}$ is the zero padding vector. | Document 1 ($d_{n}^{1}$) | Document 2 ($d_{n}^{2}$) | Score
---|---|---|---
Doc | A $\mathrm{man}$ is $\mathrm{riding}$ a $\mathrm{motorcycle}$ | A $\mathrm{woman}$ is $\mathrm{riding}$ a $\mathrm{horse}$ | 0.15
SIF | $\vec{v}_{\mathrm{man}_{2}}+\vec{v}_{\mathrm{riding}_{3}}+\vec{v}_{\mathrm{motorcycle}_{4}}$ | $\vec{v}_{\mathrm{woman}_{1}}+\vec{v}_{\mathrm{riding}_{3}}+\vec{v}_{\mathrm{horse}_{5}}$ | 0.57
P-SIF |  $\vec{v}_{\mathrm{zero}_{1}}$ $\oplus$ $\vec{v}_{\mathrm{man}_{2}}$ $\oplus$ $\vec{v}_{\mathrm{riding}_{3}}$ $\oplus$ $\vec{v}_{\mathrm{motorcycle}_{4}}$ $\oplus$ $\vec{v}_{\mathrm{zero}_{5}}$ |  $\vec{v}_{\mathrm{women}_{1}}$ $\oplus$ $\vec{v}_{\mathrm{zero}_{2}}$ $\oplus$ $\vec{v}_{\mathrm{riding}_{3}}$ $\oplus$ $\vec{v}_{\mathrm{zero}_{4}}$ $\oplus$ $\vec{v}_{\mathrm{horse}_{5}}$ | 0.16
Figure 3: Words in different topics are represented by different subscripts
and separated by hyperplanes. Bold represents words from example documents.

##  Appendix H Qualitative Results: Similarity task

Table 13 represents successful example pair from STS 2012 MSRvid dataset where
P-SIF assigns similarity scores closer to ground truth than SIF. Table 12
represents the failed example pairs from STS 2012 MSRvid dataset where SIF
assigns a similarity score closer to the ground truth than P-SIF. We now
introduce the header notations used in the Table 13 and 12 in details.

  * •

GT: represents the given ground truth similarity score in a range of 0-5.

  * •

NGT: represents the normalized ground truth similarity score. NGT is obtained
by dividing the GT score by 5 so that it is in a range of 0-1.

  * •

SIFsc: represents the SIF embedding similarity score in a range of 0-1.

  * •

P-SIFsc: represents the P-SIF embedding similarity score in a range of 0-5.

  * •

SIFerr: represents absolute error $\|SIF_{sc}-NGT\|$ between normalized ground
truth similarity score and the SIF embedding similarity score.

  * •

P-SIFerr: represents the absolute error $\|\textsc{P-SIF}_{sc}-NGT\|$ between
the ground truth similarity score and the P-SIF embedding similarity score.

  * •

Differr: represents absolute difference between SIFerr and P-SIFerr. Examples
where P-SIF performs better Differr = P-SIFerr \- SIFerr (used in Table 13).
Examples where SIF performs better Differr = SIFerr \- P-SIFerr (used in Table
12)

  * •

Relerr: represents relative difference between SIFerr and P-SIFerr. Examples
where P-SIF performs better Relerr = $\frac{Diff_{err}}{SIF_{err}}$ (used in
Table 13). Examples where SIF performs better Relerr =
$\frac{Diff_{err}}{\textsc{P-SIF}_{err}}$ (used in Table 12)

Table 12: STS 2012 MSRVid examples where the P-SIF score were far away from the ground truth, whereas the SIF scores were closer to the actual ground truth sentence1 | sentence2 | GT | NGT | SIFsc |  P-SIFsc | SIFerr |  P-SIFerr | Differr | Relerr
---|---|---|---|---|---|---|---|---|---
takes off his sunglasses . | A boy is screaming . | 0.5 | 0.1 | 0.1971 | 0.3944 | 0.0971 | 0.2944 | 0.1973 | 0.6703
The rhino grazed on the grass . | A rhino is grazing in a field . | 4 | 0.8 | 0.7275 | 0.538 | 0.0725 | 0.262 | 0.1895 | 0.7234
An animal is biting a persons finger . | A slow loris is biting a persons finger . | 3 | 0.6 | 0.6018 | 0.7702 | 0.0018 | 0.1702 | 0.1684 | 0.9892
Animals are playing in water . | Two men are playing ping pong . | 0 | 0 | 0.0706 | 0.2238 | 0.0706 | 0.2238 | 0.1532 | 0.6846
Someone is feeding a animal . | Someone is playing a piano . | 0 | 0 | -0.0037 | 0.1546 | 0.0037 | 0.1546 | 0.1509 | 0.976
The lady sliced a tomatoe . | Someone is cutting a tomato . | 4 | 0.8 | 0.693 | 0.5591 | 0.107 | 0.2409 | 0.1339 | 0.5559
The lady peeled the potatoe . | A woman is peeling a potato . | 4.75 | 0.95 | 0.7167 | 0.5925 | 0.2333 | 0.3575 | 0.1242 | 0.3474
A man is slicing something . | A man is slicing a bun . | 3 | 0.6 | 0.5976 | 0.4814 | 0.0024 | 0.1186 | 0.1162 | 0.9802
A boy is crawling into a dog house . | A boy is playing a wooden flute . | 0.75 | 0.15 | 0.1481 | 0.2674 | 0.0019 | 0.1174 | 0.1155 | 0.9839
A man and woman are talking . | A man and woman is eating . | 1.6 | 0.32 | 0.3574 | 0.4711 | 0.0374 | 0.1511 | 0.1137 | 0.7527
A man is cutting a potato . | A woman plays an electric guitar . | 0.083 | 0.0166 | -0.1007 | -0.2128 | 0.1173 | 0.2294 | 0.112 | 0.4884
A person is cutting a meat . | A person riding a mechanical bull | 0 | 0 | 0.0152 | 0.1242 | 0.0152 | 0.1242 | 0.1091 | 0.8778
A woman is playing the flute . | A man is playing the guitar . | 1 | 0.2 | 0.1942 | 0.0876 | 0.0058 | 0.1124 | 0.1065 | 0.948
Table 13: STS 2012 MSRVid example where the P-SIF scores were closer to the ground truth, whereas SIF scores were more away from the ground truth sentence1 | sentence2 | GT | NGT | SIFsc |  P-SIFsc | SIFerr |  P-SIFerr | Differr | Relerr
---|---|---|---|---|---|---|---|---|---
People are playing baseball . | The cricket player hit the ball . | 0.5 | 0.1 | 0.2928 | 0.0973 | 0.1928 | 0.0027 | 0.1901 | 0.986
A woman is carrying a boy . | A woman is carrying her baby . | 2.333 | 0.4666 | 0.5743 | 0.4683 | 0.1077 | 0.0017 | 0.106 | 0.9843
A man is riding a motorcycle . | A woman is riding a horse . | 0.75 | 0.15 | 0.5655 | 0.157 | 0.4155 | 0.007 | 0.4085 | 0.9833
A woman slices a lemon . | A man is talking into a microphone . | 0 | 0 | -0.1101 | -0.0027 | 0.1101 | 0.0027 | 0.1074 | 0.9754
A man is hugging someone . | A man is taking a picture . | 0.4 | 0.08 | 0.2021 | 0.0767 | 0.1221 | 0.0033 | 0.1188 | 0.9731
A woman is dancing . | A woman plays the clarinet . | 0.8 | 0.16 | 0.3539 | 0.1653 | 0.1939 | 0.0053 | 0.1886 | 0.9727
A train is moving . | A man is doing yoga . | 0 | 0 | 0.1674 | -0.0051 | 0.1674 | 0.0051 | 0.1623 | 0.9695
Runners race around a track . | Runners compete in a race . | 3.2 | 0.64 | 0.7653 | 0.6438 | 0.1253 | 0.0038 | 0.1214 | 0.9694
A man is driving a car . | A man is riding a horse . | 1.2 | 0.24 | 0.3584 | 0.2443 | 0.1184 | 0.0043 | 0.114 | 0.9636
A man is playing a guitar . | A woman is riding a horse . | 0.5 | 0.1 | -0.0208 | 0.0955 | 0.1208 | 0.0045 | 0.1163 | 0.9629
A man is riding on a horse . | A girl is riding a horse . | 2.6 | 0.52 | 0.6933 | 0.5082 | 0.1733 | 0.0118 | 0.1615 | 0.9319
A woman is deboning a fish . | A man catches a fish . | 1.25 | 0.25 | 0.4538 | 0.2336 | 0.2038 | 0.0164 | 0.1875 | 0.9196
A man is playing a guitar . | A man is eating pasta . | 0.533 | 0.1066 | -0.0158 | 0.0962 | 0.1224 | 0.0104 | 0.112 | 0.915
A woman is dancing . | A man is eating . | 0.143 | 0.0286 | -0.1001 | 0.0412 | 0.1287 | 0.0126 | 0.1161 | 0.9023
The ballerina is dancing . | A man is dancing . | 1.75 | 0.35 | 0.512 | 0.3317 | 0.162 | 0.0183 | 0.1437 | 0.8871
A woman plays the guitar . | A man sings and plays the guitar . | 1.75 | 0.35 | 0.5036 | 0.3683 | 0.1536 | 0.0183 | 0.1353 | 0.8807
A girl is styling her hair . | A girl is brushing her hair . | 2.5 | 0.5 | 0.7192 | 0.5303 | 0.2192 | 0.0303 | 0.1889 | 0.8618
A guy is playing hackysack | A man is playing a key-board . | 1 | 0.2 | 0.3718 | 0.2268 | 0.1718 | 0.0268 | 0.145 | 0.8441
A man is riding a bicycle . | A monkey is riding a bike . | 2 | 0.4 | 0.6891 | 0.4614 | 0.2891 | 0.0614 | 0.2277 | 0.7876
A woman is swimming underwater . | A man is slicing some carrots . | 0 | 0 | -0.2158 | -0.0562 | 0.2158 | 0.0562 | 0.1596 | 0.7397
A plane is landing . | A animated airplane is landing . | 2.8 | 0.56 | 0.801 | 0.6338 | 0.241 | 0.0738 | 0.1672 | 0.6937
The missile exploded . | A rocket exploded . | 3.2 | 0.64 | 0.8157 | 0.6961 | 0.1757 | 0.0561 | 0.1196 | 0.6806
A woman is peeling a potato . | A woman is peeling an apple . | 2 | 0.4 | 0.6938 | 0.5482 | 0.2938 | 0.1482 | 0.1456 | 0.4956
A woman is writing . | A woman is swimming . | 0.5 | 0.1 | 0.3595 | 0.2334 | 0.2595 | 0.1334 | 0.1261 | 0.4859
A man is riding a bike . | A man is riding on a horse . | 2 | 0.4 | 0.6781 | 0.564 | 0.2781 | 0.164 | 0.1142 | 0.4105
A panda is climbing . | A man is climbing a rope . | 1.6 | 0.32 | 0.4274 | 0.3131 | 0.1074 | 0.0069 | 0.1005 | 0.9361
A man is shooting a gun . | A man is spitting . | 0 | 0 | 0.2348 | 0.1305 | 0.2348 | 0.1305 | 0.1043 | 0.444