We present a framework for building unsupervised representations of entities and their compositions, where each entity is viewed as a probability distribution rather than a fixed length vector. In particular, this distribution is supported over the contexts which co-occur with the entity and are embedded in a suitable low-dimensional space. This enables us to consider the problem of representation learning with a perspective from Optimal Transport and take advantage of its numerous tools such as Wasserstein distance and Wasserstein barycenters. We elaborate how the method can be applied for obtaining unsupervised representations of text and illustrate the performance quantitatively as well as qualitatively on tasks such as measuring sentence similarity and word entailment, where we empirically observe significant gains (e.g., 4.1% relative improvement over Sent2vec and GenSen).

 The key benefits of the proposed approach include: (a) capturing uncertainty and polysemy via modeling the entities as distributions, (b) utilizing the underlying geometry of the particular task (with the ground cost), (c) simultaneously providing interpretability with the notion of optimal transport between contexts and (d) easy applicability on top of existing point embedding methods. In essence, the framework can be useful for any unsupervised or supervised problem (on text or other modalities); and only requires a co-occurrence structure inherent to many problems. The code, as well as pre-built histograms, are available under https://github.com/context-mover. One of the driving factors behind recent successes in machine learning has been the development of better methods for data representation, thus forming the foundation around which rest of the model architecture gets built. Examples include continuous vector representations for language (Mikolov et al., 2013; Pennington et al., 2014) , convolutional neural network based feature representations for images and text (LeCun et al., 1998; Collobert & Weston, 2008; Kalchbrenner et al., 2014) , or via the hidden state representations of LSTMs (Hochreiter & Schmidhuber, 1997; Sutskever et al., 2014) . Pre-trained unsupervised representations in particular have been immensely useful as general purpose features for model initialization (Kim, 2014) , downstream tasks, (Severyn & Moschitti, 2015; Deriu et al., 2017) and in domains with limited supervised information (Qi et al., 2018) .The shared idea across these methods is to map input entities to dense vector embeddings lying in a low-dimensional latent space where the semantics of inputs are preserved. Thus , each entity of interest (e.g., a word) is represented directly as a single point (i.e., its embedding vector) in space, which is typically Euclidean.In contrast, we approach the problem of building unsupervised representations in a fundamentally different manner. We focus on the co-occurrence information between the entities and their contexts, and represent each entity as a probability distribution (histogram) over its contexts. Here the contexts themselves are embedded as points in a suitable low-dimensional space. This allows us to cast finding distance between entities as an instance of the Optimal Transport problem (Monge, 1781; Kantorovich, 1942; Villani, 2008) . So, our resulting framework intuitively compares the cost of moving the contexts of a given entity to the contexts of another, which motivates the naming Context Mover's Distance (CMD). We will call this distribution over contexts embeddings the distributional estimate of our entity of interest (see FIG0 ), while we refer to the individual embeddings of contexts as point estimates. More precisely, the contexts refer to any generic entities or objects (such as words, phrases, sentences, images, etc.) co-occurring with the entities to be represented.The main motivation for our proposed approach originates from the domain of natural language, where the entities (words, phrases, or sentences) generally have different semantics depending on the context under which they are present. Hence , it is important to consider representations that are able to effectively capture such inherent uncertainty and polysemy, and we will argue that distributional estimates capture more of this information compared to point-wise embedding vectors alone. In particular , we will see that the co-occurrence information required to build the distributions is already obtained as the first step of point-wise embedding methods, like in GloVe (Pennington et al., 2014) , but has largely been ignored in the past.Further, this co-occurrence information that is the crucial building block of our approach is inherent to a wide variety of problems, for instance, recommending products such as movies or web-advertisements (Grbovic et al., 2015) , nodes in a graph (Grover & Leskovec, 2016) , sequence data, or other entities (Wu et al., 2017) . This means that , in principle, our framework can be employed to obtain a representation of various entities present across these problems.Overall, we strongly advocate for representing entities with distributional estimates due to the above stated reasons. But at the same time, our message isn't that point-wise embedding methods should cease to exist, rather that both kinds of methods should go hand in hand. This will be reflected through building distributional estimates on the top of existing point embedding methods, as well as how we can combine them (cf. Section 4) to get the best of these intrinsically different ideas.Lastly, the connection to optimal transport at the level of entities and contexts paves the way to make better use of its vast toolkit (like Wasserstein distances, barycenters, barycentric coordinates, etc.) for applications in NLP, which in the past has primarily been restricted to document distances of original words (Kusner et al., 2015; Huang et al., 2016) , as opposed to contexts. Thanks to the entropic regularization introduced by Cuturi (2013) , optimal transport computations can be carried out efficiently in a parallel and batched manner on GPUs.Contributions: 1) Employing the notion of optimal transport of contexts as a distance measure, we illustrate how our framework can be of benefit for various important tasks, including word and sentence representations, sentence similarity, as well as hypernymy (entailment) detection. The method is static and does not require any additional learning, and can be readily used on top of existing embedding methods.2) The resulting representations, as portrayed in FIG0 , 4, capture the various senses under which the entity occurs. Next, the transport map obtained through CMD (see FIG1 gives a clear interpretation of the resulting distance obtained between two entities.3) Our Context Mover's Distance (CMD) can be used to measure any kind of distance (even asymmetric) between words, by defining a suitable underlying cost on the movement of contexts, which we show can lead to a state-of-the-art metric for word entailment. 4) Defining the transport over contexts has the additional benefit that the representations are compositional -they directly extend from entities to groups of entities (of any size), such as from word to sentence representations. To this end, we utilize the notion of Wasserstein barycenters, which to the best of our knowledge has never been considered in the past. This results in a significant performance boost on multiple datasets, and even outperforming supervised methods like InferSent (Conneau et al., 2017) and GenSen (Subramanian et al., 2018 ) by a decent margin. We advocate for representing entities by a distributional estimate on top of any given co-occurrence structure. For each entity, we jointly consider the histogram information (with its contexts) as well as the point embeddings of the contexts. We show how this enables the use of optimal transport over distributions of contexts. Our framework results in an efficient, interpretable and compositional metric to represent and compare entities (e.g. words) and groups thereof (e.g. sentences), while leveraging existing point embeddings. We demonstrate its performance on several NLP tasks such as sentence similarity and word entailment detection. Thus, a practical take-home message is: do not throw away the co-occurrence information (e.g. when using GloVe), but instead pass it on to our method. Motivated by the promising empirical results, applying the proposed framework on co-occurrence structures beyond NLP is an exciting direction. Summarizing the observations from the above qualitative analysis on News dataset S7 , we conclude the following about the nature of success or failures of each method.• When the subject of the sentence is similar and main difference stems from the predicate, CoMB is the winner. This can be seen for both the case when predicates are equivalent but described distinctly (observation 1) and when predicates are not equivalent (observation 3).• When the predicates are similar and the distinguishing factor is in the subject (or object), SIF takes the lead. This seems to be true for both scenarios when the subject used increases or decreases the similarity as measured by CoMB, (observations 2 and 4).S7 Similar findings can also be seen for the two other datasets in Section S4.5. Table S6 : Examples of some indicative sentence pairs, from News dataset in STS14, with ground-truth scores and ranking as obtained via (best variants of) CoMB and SIF. The total number of sentences is 300 and the ranking is done in descending order of similarity. The method which ranks an example closer to the ground-truth rank is better and is highlighted in blue. CoMB ranking is the one produced when representing sentences via CoMB and then using CMD to compare them. SIF ranking is when sentences are represented via SIF and then employing cosine similarity.• The above two points in a way also signify where having distributional estimates can be better or worse than point estimates.• CoMB and SIF appear to be complementary in the kind of errors they make. Hence, combining the two is an exciting future avenue.Lastly, it also seems worthwhile to explore having different ground metrics for CoMB and CMD (which are currently shared). The ground metric plays a crucial role in performance and the nature of these observations. Employing a ground metric(s) that better handles the above subtleties would be a useful research direction.
Represent each entity as a probability distribution over contexts embedded in a ground space. Proposes to construct word embeddings from a histogram over context words, instead of as point vectors, which allows for measuring distances between two words in terms of optimal transport between the histograms through a method that augments representation of an entity from standard "point in a vector space" to a histogram with bins located at some points in that vector space. 