summaries: The submission explores a new form of word representation based on a histogram over context word vectors, allowing them to measure distances between words in terms of optimal transport between these histograms. The authors speculate that this may allow better representations of polysemous words. The approach is mathematically elegant, and requires no additional training on top of existing approaches like Glove. To improve efficiency, they use clustering on context vectors. They present results on various semantic textual similarity and hypernym detection tasks, outperforming some baselines. The paper proposes a method to augment representation of an entity (such as a word) from standard "point in a vector space" to a histogram with bins located at some points in that vector space. In this model, the bins correspond the context objects, the location of which are the standard point embedding of those objects, and the histogram weights correspond to the strength of the contextual association. The distance between two representations is then measured with, Context Mover Distance, based on the theory of optimal transport, which is suitable for computing the discrepancy between distributions. 
abstractText: We propose a unified framework for building unsupervised representations of entities and their compositions, by viewing each entity as a histogram (or distribution) over its contexts. This enables us to take advantage of optimal transport and construct representations that effectively harness the geometry of the underlying space containing the contexts. Our method captures uncertainty via modelling the entities as distributions and simultaneously provides interpretability with the optimal transport map, hence giving a novel perspective for building rich and powerful feature representations. As a guiding example, we formulate unsupervised representations for text, and demonstrate it on tasks such as sentence similarity and word entailment detection. Empirical results show strong advantages gained through the proposed framework. This approach can potentially be used for any unsupervised or supervised problem (on text or other modalities) with a co-occurrence structure, such as any sequence data. The key tools at the core of this framework are Wasserstein distances and Wasserstein barycenters, hence raising the question from our title.
references.authors: Eneko Agirre Mona Diab Daniel Cer Aitor Gonzalez-Agirre
references.title: Semeval-2012 task 6: A pilot on semantic textual similarity
references.venue: In Proceedings of the First Joint Conference on Lexical and Computational Semantics-Volume 1: Proceedings of the main conference and the shared task, and Volume 2: Proceedings of the Sixth International Workshop on Semantic Evaluation,
references.authors: Eneko Agirre Carmen Banea Claire Cardie Daniel Cer Mona Diab Aitor Gonzalez-Agirre Weiwei Guo Rada Mihalcea German Rigau Janyce Wiebe
references.title: Semeval-2014 task 10: Multilingual se6All the methods use a Wikipedia dump as a training corpus
references.venue: In particular GE and DIVE employ WaCkypedia (a 2009 Wikipedia dump) from Baroni et al. (2009), and D and CMD are based on a 2015 Wikipedia dump
references.authors: Eneko Agirre Carmen Banea Claire Cardie Daniel Cer Mona Diab Aitor Gonzalez-Agirre Weiwei Guo Inigo Lopez-Gazpio Montse Maritxalar Rada Mihalcea
references.title: Semeval-2015 task 2: Semantic textual similarity, english, spanish and pilot on interpretability
references.venue: In Proceedings of the 9th international workshop on semantic evaluation (SemEval
references.authors: Eneko Agirre Carmen Banea Daniel Cer Mona Diab Aitor Gonzalez-Agirre Rada Mihalcea German Rigau Janyce Wiebe
references.title: Semeval-2016 task 1: Semantic textual similarity, monolingual and cross-lingual evaluation
references.venue: In Proceedings of the 10th International Workshop on Semantic Evaluation
references.authors: Martial Agueh Guillaume Carlier
references.title: Barycenters in the wasserstein space
references.venue: SIAM Journal on Mathematical Analysis,
references.authors: Jason Altschuler Jonathan Weed Philippe Rigollet
references.title: Near-linear time approximation algorithms for optimal transport via sinkhorn iteration
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Sanjeev Arora Yingyu Liang Tengyu Ma
references.title: A simple but tough-to-beat baseline for sentence embeddings
references.authors: Ben Athiwaratkun Andrew Gordon Wilson
references.title: Multimodal word distributions
references.venue: arXiv preprint arXiv:1704.08424,
references.authors: Marco Baroni Alessandro Lenci
references.title: How we blessed distributional semantic evaluation
references.venue: In Proceedings of the GEMS 2011 Workshop on GEometrical Models of Natural Language Semantics,
references.authors: Marco Baroni Silvia Bernardini Adriano Ferraresi Eros Zanchetta
references.title: The wacky wide web: a collection of very large linguistically processed web-crawled corpora
references.venue: Language Resources and Evaluation,
references.authors: Marco Baroni Raffaella Bernardi Ngoc-Quynh Do Chung-chieh Shan
references.title: Entailment above the word level in distributional semantics
references.venue: In Proceedings of the 13th Conference of the European Chapter of the Association for Computational Linguistics,
references.authors: Jean-David Benamou Guillaume Carlier Marco Cuturi Luca Nenna Gabriel Peyré
references.title: Iterative bregman projections for regularized transportation problems
references.venue: SIAM Journal on Scientific Computing,
references.authors: Giulia Benotto
references.title: Distributional models for semantic relations: A study on hyponymy and antonymy
references.venue: PhD thesis,
references.authors: Piotr Bojanowski Edouard Grave Armand Joulin Tomas Mikolov
references.title: Enriching word vectors with subword information
references.venue: arXiv preprint arXiv:1607.04606,
references.authors: Haw-Shiuan Chang ZiYun Wang Luke Vilnis Andrew McCallum
references.title: Distributional inclusion vector embedding for unsupervised hypernymy detection
references.venue: arXiv preprint arXiv:1710.00880,
references.authors: Kenneth Ward Church Patrick Hanks
references.title: Word association norms, mutual information, and lexicography
references.venue: Computational linguistics,
references.authors: Ronan Collobert Jason Weston
references.title: A unified architecture for natural language processing: Deep neural networks with multitask learning
references.venue: In Proceedings of the 25th international conference on Machine learning,
references.authors: Alexis Conneau Douwe Kiela
references.title: SentEval: An Evaluation Toolkit for Universal Sentence Representations
references.venue: arXiv preprint arXiv:1803.05449,
references.authors: Marco Cuturi
references.title: Sinkhorn distances: Lightspeed computation of optimal transport
references.venue: In Advances in neural information processing systems,
references.authors: Marco Cuturi Arnaud Doucet
references.title: Fast computation of wasserstein barycenters
references.venue: Proceedings of the 31st International Conference on Machine Learning,
references.authors: Jan Deriu Aurelien Lucchi Valeria De Luca Aliaksei Severyn Simon Müller Mark Cieliebak Thomas Hofmann Martin Jaggi
references.title: Leveraging Large Amounts of Weakly Supervised Data for Multi-Language Sentiment Classification
references.venue: In WWW 2017 - International World Wide Web Conference,
references.authors: Octavian-Eugen Ganea Gary Bécigneul Thomas Hofmann
references.title: Hyperbolic entailment cones for learning hierarchical embeddings
references.venue: arXiv preprint arXiv:1804.01882,
references.authors: Aude Genevay Marco Cuturi Gabriel Peyré Francis Bach
references.title: Stochastic optimization for largescale optimal transport
references.venue: Advances in Neural Information Processing Systems
references.authors: Edouard Grave Armand Joulin Quentin Berthet
references.title: Unsupervised Alignment of Embeddings with Wasserstein Procrustes
references.venue: arXiv preprint arXiv:1805.11222,
references.authors: Mihajlo Grbovic Vladan Radosavljevic Nemanja Djuric Narayan Bhamidipati Jaikit Savla Varun Bhagwan Doug Sharp
references.title: E-commerce in your inbox: Product recommendations at scale
references.venue: In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,
references.authors: Aditya Grover Jure Leskovec
references.title: node2vec: Scalable feature learning for networks
references.venue: In KDD 2016 - Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining,
references.authors: Jiang Guo Wanxiang Che Haifeng Wang Ting Liu
references.title: Learning sense-specific word embeddings by exploiting bilingual resources
references.venue: In Proceedings of COLING 2014, the 25th International Conference on Computational Linguistics: Technical Papers,
references.authors: James Henderson
references.title: Learning word embeddings for hyponymy with entailment-based distributional semantics
references.venue: arXiv preprint arXiv:1710.02437,
references.authors: James Henderson Diana Nicoleta Popa
references.title: A vector space for distributional semantics for entailment
references.venue: arXiv preprint arXiv:1607.03780,
references.authors: Sepp Hochreiter Jürgen Schmidhuber
references.title: Long short-term memory
references.venue: Neural computation,
references.authors: Eric H Huang Richard Socher Christopher D Manning Andrew Y Ng
references.title: Improving word representations via global context and multiple word prototypes
references.venue: In Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics: Long Papers-Volume
references.authors: Gao Huang Chuan Guo Matt J Kusner Yu Sun Fei Sha Kilian Q Weinberger
references.title: Supervised word mover’s distance
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Nal Kalchbrenner Edward Grefenstette Phil Blunsom
references.title: A Convolutional Neural Network for Modelling Sentences
references.venue: In ACL - Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics,
references.authors: Leonid V Kantorovich
references.title: On the translocation of masses
references.venue: In Dokl. Akad. Nauk. USSR (NS),
references.authors: Douwe Kiela Laura Rimell Ivan Vulić Stephen Clark
references.title: Exploiting image generality for lexical entailment detection
references.venue: In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 2: Short Papers),
references.authors: Yoon Kim
references.title: Convolutional Neural Networks for Sentence Classification
references.venue: In EMNLP 2014 - Empirical Methods in Natural Language Processing,
references.authors: Ryan Kiros Yukun Zhu Ruslan R Salakhutdinov Richard Zemel Raquel Urtasun Antonio Torralba Sanja Fidler
references.title: Skip-thought vectors. In Advances in neural information processing
references.authors: Lili Kotlerman Ido Dagan Idan Szpektor Maayan Zhitomirsky-Geffet
references.title: Directional distributional similarity for lexical inference
references.venue: Natural Language Engineering,
references.authors: Matt Kusner Yu Sun Nicholas Kolkin Kilian Weinberger
references.title: From word embeddings to document distances
references.venue: In International Conference on Machine Learning,
references.authors: Omer Levy Yoav Goldberg
references.title: Dependency-based word embeddings
references.venue: In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics
references.authors: Omer Levy Yoav Goldberg
references.title: Neural word embedding as implicit matrix factorization
references.venue: In Advances in neural information processing systems,
references.authors: Omer Levy Ido Dagan Jacob Goldberger
references.title: Focused entailment graphs for open ie propositions
references.venue: In Proceedings of the Eighteenth Conference on Computational Natural Language Learning,
references.authors: Omer Levy Yoav Goldberg Ido Dagan
references.title: Improving distributional similarity with lessons learned from word embeddings
references.venue: Transactions of the Association for Computational Linguistics,
references.authors: Christopher Manning Mihai Surdeanu John Bauer Jenny Finkel Steven Bethard David McClosky
references.title: The stanford corenlp natural language processing toolkit. In Proceedings of 52nd annual meeting of the association for computational linguistics: system
references.authors: Oren Melamud Omer Levy Ido Dagan
references.title: A simple word embedding model for lexical substitution
references.venue: In Proceedings of the 1st Workshop on Vector Space Modeling for Natural Language Processing,
references.authors: Tomas Mikolov Ilya Sutskever Kai Chen Greg S Corrado Jeff Dean
references.title: Distributed representations of words and phrases and their compositionality
references.venue: In Advances in neural information processing systems,
references.authors: Jeff Mitchell Mirella Lapata
references.title: Vector-based models of semantic composition
references.venue: proceedings of ACL-08: HLT, pp
references.authors: Boris Muzellec Marco Cuturi
references.title: Generalizing Point Embeddings using the Wasserstein Space of Elliptical Distributions
references.venue: arXiv preprint arXiv:1805.07594,
references.authors: Maximillian Nickel Douwe Kiela
references.title: Poincaré embeddings for learning hierarchical representations
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Matteo Pagliardini Prakhar Gupta Martin Jaggi
references.title: Unsupervised learning of sentence embeddings using compositional n-gram features
references.venue: arXiv preprint arXiv:1703.02507,
references.authors: Jeffrey Pennington Richard Socher Christopher Manning
references.title: Glove: Global vectors for word representation
references.venue: In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP),
references.authors: Laura Rimell
references.title: Distributional lexical entailment by topic coherence
references.venue: In Proceedings of the 14th Conference of the European Chapter of the Association for Computational Linguistics,
references.authors: Antoine Rolet Marco Cuturi Gabriel Peyré
references.title: Fast dictionary learning with a smoothed wasserstein loss
references.venue: Proceedings of the 19th International Conference on Artificial Intelligence and Statistics,
references.authors: Herbert Rubenstein John B Goodenough
references.title: Contextual correlates of synonymy
references.venue: Communications of the ACM,
references.authors: Yossi Rubner Carlo Tomasi Leonidas J Guibas
references.title: The earth mover’s distance as a metric for image retrieval
references.venue: International journal of computer vision,
references.authors: Enrico Santus Alessandro Lenci Qin Lu S Schulte im Walde
references.title: Chasing hypernyms in vector spaces with entropy. In 14th Conference of the European Chapter of the Association for Computational Linguistics, pp. 38–42
references.venue: EACL (European chapter of the Association for Computational Linguistics),
references.authors: Enrico Santus Frances Yung Alessandro Lenci Chu-Ren Huang
references.title: Evalution 1.0: an evolving semantic dataset for training and evaluation of distributional semantic models
references.venue: In Proceedings of the 4th Workshop on Linked Data in Linguistics: Resources and Applications,
references.authors: Aliaksei Severyn Alessandro Moschitti
references.title: Twitter Sentiment Analysis with Deep Convolutional Neural Networks
references.venue: In 38th International ACM SIGIR Conference,
references.authors: Vered Shwartz Yoav Goldberg Ido Dagan
references.title: Improving hypernymy detection with an integrated path-based and distributional method. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)
references.venue: Association for Computational Linguistics,
references.authors: Richard Sinkhorn
references.title: A relationship between arbitrary positive matrices and doubly stochastic matrices
references.venue: The Annals of Mathematical Statistics,
references.authors: Chi Sun Hang Yan Xipeng Qiu Xuanjing Huang
references.title: Gaussian Word Embedding with a Wasserstein Distance Loss
references.venue: arXiv preprint arXiv:1808.07016v7,
references.authors: Peter D Turney Saif M Mohammad
references.title: Experiments with three approaches to recognizing lexical entailment
references.venue: Natural Language Engineering,
references.authors: Cédric Villani
references.title: Optimal transport: old and new, volume 338
references.venue: Springer Science & Business Media,
references.authors: Luke Vilnis Andrew McCallum
references.title: Word representations via gaussian embedding
references.venue: arXiv preprint arXiv:1412.6623,
references.authors: Julie Weeds David Weir
references.title: A general framework for distributional similarity
references.venue: In Proceedings of the 2003 conference on Empirical methods in natural language processing,
references.authors: Julie Weeds Daoud Clarke Jeremy Reffin David Weir Bill Keller
references.title: Learning to distinguish hypernyms and co-hyponyms
references.venue: In Proceedings of COLING 2014, the 25th International Conference on Computational Linguistics: Technical Papers,
references.authors: Ledell Wu Adam Fisch Sumit Chopra Keith Adams Antoine Bordes Jason Weston
references.title: Starspace: Embed all the things
references.venue: arXiv preprint arXiv:1709.03856,
references.authors: Hongteng Xu Wenlin Wang Wei Liu Lawrence Carin
references.title: Distilled wasserstein learning for word embedding and topic modeling
references.venue: arXiv preprint arXiv:1809.04705,
references.authors: Jianbo Ye Yanran Li Zhaohui Wu James Z Wang Wenjie Li Jia Li
references.title: Determining gains acquired from word embedding quantitatively using discrete distribution clustering
references.venue: In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers),
references.authors: Meng Zhang Yang Liu Huanbo Luan Maosong Sun
references.title: Earth mover’s distance minimization for unsupervised bilingual lexicon induction
references.venue: In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing,
references.authors: Mu Zhu
references.title: Recall, precision and average precision
references.venue: Department of Statistics and Actuarial Science, University of Waterloo, Waterloo,
references.authors: Yukun Zhu Ryan Kiros Richard Zemel Ruslan Salakhutdinov Raquel Urtasun Antonio Torralba Sanja Fidler
references.title: Aligning books and movies: Towards story-like visual explanations by watching movies and reading
references.venue: books. arXiv preprint arXiv:1506.06724,
references.authors: Levy Goldberg
references.title: 2014b) have also suggested the use of the shifted PPMI (SPPMI) matrix where the shift9 by log(s) acts like a prior on the probability of co-occurrence of target and context
references.authors: Agirre
references.title: Ground-truth details. The ground-truth scores (can be fractional) and range from 0 to 5, and the meaning implied by the integral score values can be seen in the Table 10. In the case where different examples have the same ground-truth score, the ground-truth rank is then based on lexicographical ordering of sentences
sections.heading: 1 INTRODUCTION
sections.text: One of the main driving factors behind the recent successes in machine learning and natural language processing has been the development of better representation methods for data modalities. Examples include continuous vector representations for language (Mikolov et al., 2013; Pennington et al., 2014), Convolutional Neural Network (CNN) based text representations (Collobert & Weston, 2008; Kim, 2014; Kalchbrenner et al., 2014; Severyn & Moschitti, 2015; Deriu et al., 2017), or via other neural architectures such as RNNs, LSTMs (Hochreiter & Schmidhuber, 1997; Kiros et al., 2015), all sharing one central idea – to map input entities to dense vector embeddings lying in a low-dimensional latent space where the semantics of the inputs are preserved.
  While these existing methods represent each entity of interest (e.g., a word) directly as a single point in space (i.e., its embedding vector), we here propose a fundamentally different approach. We focus on co-occurrence information of the entities and their contexts (e.g. context words), and leverage embeddings of the contexts instead of the original entities. So instead of a single point per entity, we represent each entity by the histogram of its contexts, where the contexts themselves are represented as points in a suitable metric space. This allows us to cast the distance between histograms associated with the contexts as an instance of the optimal transport problem (Monge, 1781; Kantorovich, 1942; Villani, 2008).
  Our resulting framework then intuitively seeks to minimize the cost of moving the contexts of a given entity to the contexts of another, which motivates the naming Context Mover’s Distance (CMD). Note that the contexts here can be words, phrases, sentences, or any generic entities co-occurring with our entities to be represented, and these entities further could be of various kinds, including e.g., products such as movies or web-advertisements (Grbovic et al., 2015), nodes in a graph (Grover & Leskovec, 2016), sequence data, or any other entities (Wu et al., 2017). Any co-occurrence structure will allow construction of the histogram information, which is the crucial building block of our approach.
  The main motivation for our proposed approach here comes 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 that we consider representations
  that are able to effectively capture such inherent uncertainty and polysemy, and we will argue that histograms (or probability distributions) over embeddings allows to capture more of this information compared to point-wise embeddings alone. We will call this histogram over contexts embeddings as the distributional estimate of our entity of interest, while we refer to the individual embeddings of contexts as point estimates.
  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.
sections.heading: Contributions:
sections.text: • 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.
  • The resulting representations via the transport map give a clear interpretation of the resulting distance (see also Figure 1), on top of the co-occurrence information.
  • Our Context Mover’s Distance 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.
  • Defining the transport over contexts has the added 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.
  The proposed framework is not specific to words or sentences but can allow building unsupervised representations for any entity and composition of entities, where a co-occurrence structure can be devised between entities and their contexts, and we leave this direction for a future work.
sections.heading: 2 RELATED WORK
sections.text: Most of the previous work in building representations for natural language has been focused towards vector space models, in particular, popularized through the groundbreaking work in Word2vec (Mikolov et al., 2013) and GloVe (Pennington et al., 2014). The key idea in these models has been to map words which are similar in meaning to nearby points in a latent space. Based on which, many works (Levy & Goldberg, 2014a; Melamud et al., 2015; Bojanowski et al., 2016) have suggested specializing the embeddings to capture some particular information required for the task at hand. One of the problems that still persists is the inability to capture, within just a point embedding, the various semantics and uncertainties associated with the occurrence of a particular word (Huang et al., 2012; Guo et al., 2014).
  A recent line of work has proposed the view to represent words with Gaussian distributions or mixtures of Gaussian distributions (Vilnis & McCallum, 2014; Athiwaratkun & Wilson, 2017), or hyperbolic cones (Ganea et al., 2018) for this purpose. Also, concurrent works by Muzellec & Cuturi (2018) and Sun et al. (2018) have suggested using elliptical and Gaussian distributions endowed with a Wasserstein metric respectively. While these already provide richer information than typical vector embeddings, their form restricts what could be gained by allowing for arbitrary distributions. In addition, hyperbolic embeddings (Nickel & Kiela, 2017; Ganea et al., 2018) are so far restricted to supervised tasks (and even elliptical embeddings (Muzellec & Cuturi, 2018) to the most extent), not allowing unsupervised representation learning as in the focus of the paper here. To this end, we propose to represent each word with a distributional estimate (i.e., histogram over context embeddings), that inherently relies upon the empirically obtained co-occurrence information of a word and its contexts. Hence, this naturally allows for the use of optimal transport (or Wasserstein
  metric) in the space containing the contexts, and leads to an interpretation (Figure 1) which is not available in the above approaches.
  Amongst the few explorations of optimal transport in NLP, i.e., document distances (Kusner et al., 2015; Huang et al., 2016), topic modelling (Rolet et al., 2016; Xu et al., 2018), document clustering (Ye et al., 2017), bilingual lexicon induction (Zhang et al., 2017), or orthogonal Procrustes mapping (Grave et al., 2018), the focus has been on transporting words directly. For example, the Word Mover’s Distance (Kusner et al., 2015) casts finding the distance between documents as an optimal transport problem between their bag of words representation. Our approach is different as we consider the transport over contexts instead, and use it to propose a representation for words or entities. This provides the added flexibility to establish any kind of distance between entities and extend the representation to composition of entities in a principled manner, as will be illustrated further through the examples of entailment detection and sentence representation respectively.
sections.heading: 3 BACKGROUND ON OPTIMAL TRANSPORT
sections.text: Optimal Transport (OT) provides a way to compare two probability distributions defined over a space G (commonly known as the ground space), given an underlying distance or more generally a cost of moving one point to another in the ground space. In other terms, it lifts a distance between points to a distance between distributions. Other methods of comparing distributions, such as Kullback-Liebler (KL), squared Hellinger, etc., only focus on the probability mass values, thus ignoring the geometry of the ground space: something which we utilize throughout this work via OT. Also, some divergences like KL are not defined when the supports of distributions under comparison don’t match. Hence, we give a short yet formal background on OT in the discrete case.
  Linear Program Formulation. Consider an empirical probability measure of the form µ =∑n i=1 aiδ(xi) where X = (x1, . . . , xn) ∈ Gn, δ(x) denotes the Dirac (unit mass) distribution
  at point x ∈ G, and (a1, . . . , an) lives in the probability simplex Σn := { p ∈ Rn+ | ∑n i=1 pi = 1 } .
  Now given a second empirical measure, ν = ∑m j=1 bjδ(yj), with Y = (y1, . . . , ym) ∈ Gm, and (b1, . . . , bm) ∈ Σm, and if the ground cost of moving from point xi to yj is denoted by Mij , then the Optimal Transport distance between µ and ν is the solution to the following linear program.
  OT(µ, ν;M) := min T∈Rn×m+ ∑ ij TijMij such that ∀i, ∑ j Tij = ai, ∀j, ∑ i Tij = bj . (1)
  Here, the optimal T ∈ Rn×m is referred to as the transportation matrix: Tij denotes the optimal amount of mass to move from point xi to point yi. Intuitively, OT is concerned with the problem of moving goods from factories to shops in such a way that all the demands are satisfied and the overall transportation cost is minimal.
  Distance. When G = Rd and the cost is defined with respect to a metric DG over G (i.e., Mij = DG(xi, yj)
  p for any i, j), OT defines a distance between empirical probability distributions. This is the p-Wasserstein distance, defined as Wp(µ, ν) := OT(µ, ν;D p G)
  1/p. In most cases, we are only concerned with the case where p = 1 or 2.
  The cost of exactly solving OT problem scales at least inO(n3 log(n)) (n being the cardinality of the support of the empirical measure) when using network simplex or interior point methods. Following Cuturi (2013), we consider the entropy regularized Wasserstein distance, Wp,λ(µ, ν), where the search space for the optimal T is instead restricted to a smooth solution close to the extreme points of this linear program. The regularized problem can then be solved efficiently using Sinkhorn iterations (Sinkhorn, 1964), albeit at the cost of some approximation error. The regularization strength λ ≥ 0 controls the accuracy of approximation and recovers the true OT for λ = 0. The cost of the Sinkhorn algorithm is only quadratic in n at each iteration. Recently, Altschuler et al. (2017) have shown that the Sinkhorn algorithm converges in a number of iterations independent of n, thus resulting in an overall complexity of Õ(n2/ 3) for an -accurate solution.
  Barycenters. Further on in our discussion, we will make use of the notion of averaging in the Wasserstein space. More precisely, the Wasserstein barycenter, introduced by Agueh & Carlier (2011),
  man
  poaching
  giraffe
  ivory
  en d an
  ge re
  d
  sk in s
  sp ec
  ie s
  fo ss ils
  El ep
  h an
  t
  Mammal
  is a probability measure that minimizes the sum of (p-th power) Wasserstein distances to the given measures. Formally, given N measures {ν1, . . . , νN} with corresponding weights η = {η1, . . . , ηN} ∈ ΣN , the Wasserstein barycenter can be written as Bp(ν1, . . . , νN ) = arg minµ ∑N i=1 ηiWp(µ, νi)
  p. We similarly consider the regularized barycenter Bp,λ, using entropy regularized Wasserstein distances Wp,λ in the above minimization problem, following Cuturi & Doucet (2014). Employing the method of iterative Bregman projections (Benamou et al., 2015), we obtain an approximation of the solution at a reasonable computational cost.
sections.heading: 4 METHODOLOGY
sections.text: In this section, we define the distributional estimate that we use to represent each entity. In view of the guiding example of building text representations, consider each entity to be a word for simplicity.
  Distributional Estimate (PwV ). For a word w, its distributional estimate is built from a histogram over the set of contexts C, and an embedding of these contexts into a space G. The histogram essentially measures how likely it is for a word w to occur in a particular context c, i.e., probability p(w|c). The exact formulation of this distribution is generally intractable and hence it’s common to empirically estimate this by the number of occurrences of the word w in context c, relative to the total frequency of context c in the corpus.
  Thus one way to build this histogram is to maintain a co-occurrence matrix between words in our vocabulary and all possible contexts, where each entry indicates how often a word and context occur in an interval (or window) of a fixed size L. Then, the bin values (Hw)c∈C of the histogram (Hw) for a word w, can be viewed as the row corresponding to w in this co-occurrence matrix. In Section 5, we discuss possible modifications of the co-occurrence matrix to improve associations and how to reduce the number of bins in the histogram.
  The simplest embedding of contexts is into the space of one-hot vectors of all the possible contexts. However, this induces a lot of sparsity/redundancy in the representation and the distance between such emebddings of contexts does not reflect their semantics. A classical solution would be to instead find a dense low-dimensional embedding of contexts that captures the semantics, possibly using techniques such as SVD or deep neural networks. We denote by V = (vc)c∈C an embedding of the contexts into this low-dimensional space G ⊂ Rd, which we refer to as the ground space. (We will consider example cases of how this metric can be obtained in Sections 6 and 7.)
  Combining the histogram Hw and the embedding V , we represent the word w by the following empirical distribution: PwV := ∑ c ∈C (Hw)c δ(vc). (2)
  Recall that δ(vc) denotes the Dirac measure at the position vc of the context c. We refer to this representation (Eq. 2) as the distributional estimate of the word.
  Distance. If we equip the ground space G with a meaningful metric DG , then we can subsequently define a distance between the representations of two words wi and wj , as the solution to the following
  optimal transport problem:
  CMD(wi, wj ;D p G) := OT(P wi V ,P wj V ;D p G) 'Wp,λ(P wi V ,P wj V ) p. (3)
  Under this formulation, we call the above distance (Eq. 3) the Context Mover’s Distance (CMD), borrowing the name from Rubner et al. (2000)’s famous Earth Mover’s Distance in computer vision.
  Intuition. Two words are similar in meaning if the contexts of one word can be easily transported to the contexts of the other, with this cost of transportation being measured by DG . This idea still remains in line with the distributional hypothesis (Harris, 1954; Rubenstein & Goodenough, 1965) that words in similar contexts have similar meanings, but provides a precise way to quantify it. Interpretation. In fact, both elements of the distributional estimate: the histogram and point estimates are closely tied together and required to serve as an effective representation. For instance, let’s take a toy example and discuss a scenario that might arise when we only have the histogram information. Consider three words, ‘Tennis’, ‘Football’, and ‘Law’, admitting as contexts {Stadium, Court, Match, Firm}, with respective histograms shown in left part of Figure 2. Now, if we only took into account the histograms, we would reach the inaccurate conclusion that ‘Tennis’ is closer in semantics to ‘Law’ than to ‘Football’, as there is a considerable overlap at the important context of ‘Court’ for ‘Tennis’ and ‘Law’. Whereas, together with the point estimate information, it is apparent that the context ‘Stadium’ (in HFootball) can be more cheaply moved to ‘Court’ (in HTennis), but moving ‘Firm’ (in HLaw) to some context in HTennis is more costly. Lastly, in the reverse scenario of only considering the point estimates, we would lose much of the uncertainty associated about the contexts in which the words occur. We illustrate these scenarios in Figure 2.
  Roadmap. In the next section we discuss concretely how this can be applied and for the sake of brevity we restrict to the particular case where contexts consist of single words. Section 6 details how this framework can be extended to obtain representation for a composition of entities via Wasserstein barycenter. Lastly in section 7, we utilize the fact that the CMD in 3 is parameterized by ground cost, and show how this flexibility can be used to define an asymmetric cost measuring entailment.
sections.heading: 5 CONCRETE FRAMEWORK
sections.text: Making associations better. We consider co-occurrences of a word and a context word if the latter appears in a symmetric window of size L around the target word (the word whose distributional estimate we seek). While each entry of the co-occurrence matrix reflects the co-occurrence count of a target word and its context, the counts alone may not necessarily suggest a strong association between the two. The well-known Positive Pointwise Mutual Information (PPMI) matrix (Church & Hanks, 1990; Levy et al., 2015) addresses this shortcoming, and is defined as follows: PPMI(w, c) := max(log( p(w,c)p(w)×p(c) ), 0). The PPMI entries are non-zero when the joint probability of co-occurring target and context words is higher than the probability when they are independent. Typically, these probabilities are estimated from the co-occurrence counts in the corpus. Further improvements to the PPMI matrix have been suggested, like in Levy & Goldberg (2014b), and following them we make use of a shifted and smoothed PPMI matrix, denoted by SPPMIα,s where α and s denote the smoothing and k-shift parameters 1. Overall, these variants of PPMI enable us to extract better
  1Please refer to Appendix A.2 for the definition of SPPMI and more details such as our column normalization.
  semantic associations from the co-occurrence matrix. Hence, the bin values (at context c) for the histogram of word w in Eq. 2 can be formulated as: (Hw)c :=
  SPPMIα,s(w,c)∑ c ∈C SPPMIα,s(w,c) .
  Computational considerations. The view of optimal transport between histograms of contexts introduced in Eq. 3 offers a pleasing interpretation (see Figure 1). However, it might be computationally intractable in its current formulation, since the number of possible contexts can be as large as the size of vocabulary (if the contexts are just single words) or even exponential (if contexts are considered to be phrases, sentences and otherwise). This is problematic because the Sinkhorn algorithm for regularized optimal transport (Cuturi, 2013, see Section 3) scales roughly quadratically in the histogram size, and the ground cost matrix can also become prohibitive to store in memory. One possible fix is to instead consider a set of representative contexts in this ground space, for example via clustering. We believe that with dense low-dimensional embeddings and a meaningful metric between them, we may not require as many contexts as needed before. For instance, this can be achieved by clustering the contexts with respect to metric DG . Apart from the computational gain, the clustering will lead to transport between more abstract contexts. This will although come at the loss of some interpretability.
  Now, consider that we have obtained K representative contexts, each covering some part Ck of the set of contexts C. The histogram for word w with respect to these contexts can then be written as P̃w Ṽ = ∑K k=1(H̃ w )k δ(ṽk). Here ṽk ∈ Ṽ is the point estimate of the kth representative context, and (H̃ w )k denote the new histogram bin values with respect to the part Ck,
  (H̃ w )k := SPPMIα,s(w, Ck)∑K k=1 SPPMIα,s(w, Ck) ,with SPPMIα,s(w, Ck) := ∑ c∈Ck SPPMIα,s(w, c). (4)
  Summary. With the above aspects in account and using batched implementations on (Nvidia TitanX) GPUs, it is possible to compute around 13,700 Wasserstein-distances/second (for histogram of size 100). Same also holds for barycenters, where we can compute 4,600 barycenters/second for sentences of length 25 and histogram size of 100. Building this histogram information comes almost for free during the typical learning of embeddings, as in GloVe (Pennington et al., 2014). A practical take-home message of this work thus is to not throw away the co-occurrence information e.g. when using GloVe, but to instead pass it on to our method.
sections.heading: 6 SENTENCE REPRESENTATION WITH COMB
sections.text: Traditionally, the goal of this task is to develop a representation for sentences, that captures the semantics conveyed by it. Most unsupervised representations proposed in the past rely on the composition of vector embeddings for the words, through either additive, multiplicative, or other ways (Mitchell & Lapata, 2008; Arora et al., 2017; Pagliardini et al., 2017). We propose to represent sentences as probability distributions to better capture the inherent uncertainty and polysemy.
  Our belief is that a sentence representation is meaningful if it best captures the simultaneous occurrence of the words in it. We hypothesize that a sentence, S = (w1, w2, . . . , wN ), can be efficiently represented via the Wasserstein barycenter (see Section 3) of the distributional estimates of its words,
  P̃S := Bp,λ ( P̃w1V , P̃ w2 V , . . . , P̃ wN V ) , (5)
  which is itself again a distribution over the ground space G. We refer to this representation as the Context Mover’s Barycenters (CoMB) henceforth. Interestingly, the classical weighted averaging of point-estimates, like Smooth Inverse Frequency (SIF) in (Arora et al., 2017) (without principal component removal), can be seen as a special case of CoMB, when the distribution associated to a word is just a Dirac at its point estimate. It becomes apparent that having a rich distributional estimate for a word could turn out to be advantageous.
  Since with barycenter representation as in Eq. 5, each sentence is also a distribution over contexts, we can utilize the Context Mover’s Distance (CMD) defined in Eq. 3 to define the distance between two sentences S1 and S2, under a given ground metric DG as follows,
  CMD(S1, S2;D p G) := OT(P̃ S1 V , P̃ S2 V ;D p G) 'Wp,λ(P̃ S1 V , P̃ S2 V ) p. (6)
  Empirical Evaluation. To evaluate CoMB as an effective sentence representation, we consider 24 datasets from SemEval semantic textual similarity (STS) tasks (Agirre et al., 2012; 2013; 2014; 2015; 2016). The objective here is to give a score of how similar two sentences are in their meanings.
  As a ground metric (DG), we consider the Euclidean distance between the point estimates (embeddings) of words. We train the GloVe (Pennington et al., 2014) embeddings on the Toronto Book Corpus (Zhu et al., 2015), and in this process also obtain the histogram information needed for the distributional estimate. Since GloVe embeddings for similar words are constructed to be close in terms of cosine similarity for similar words, we find the representative points by performing K-means clustering with respect to this similarity for K = 300.
  We benchmark4 our performance against SIF (Smooth Inverse Frequency) from Arora et al. (2017) who regard it as a “simple but tough-to-beat baseline”, Skip-thought (Kiros et al., 2015), as well as against the plain Bag of Words (BoW) averaging. Hyperparameters for both SIF and CoMB are tuned on STS16, and the best configurations so obtained are used for comparison on the other STS tasks.
  Table 1 shows that, on all the tasks CoMB outperforms the best variant of SIF on 3 out of 4 tasks in the test set and leads to an overall gain. Please refer to Tables 6 and 7in Appendix A for detailed results and discussion. Also, we encourage the reader to check out Section A.6 where we qualitatively analyse CoMB & SIF.
  Online computation. The principal component removal in SIF, which plays a crucial role as evident from the Table 1, has an aspect that typically goes under the rug. In particular, these principal components are estimated based on embeddings of sentences in the test set. This way it cleverly utilizes the information shared across sentences in the test set of downstream tasks, but can act as a hindrance in the practical usecase. For instance, consider the probable scenario (like for a chatbot) where we have to resolve a query about the similarity of two sentences in an online manner. Here SIF would undergo a significant performance drop, but CoMB is devoid of any issues arising in the online mode while retaining its performance.
  Summary and further prospects. Our focus in these experiments was to compare methods which can build up sentence representations by just obtaining the word vector information. Hence, we didn’t consider unsupervised methods such as Sent2vec (Pagliardini et al., 2017), that are specifically trained to work well on sentence similarity. We observe that CoMB serves as a competitive sentence
  3The SIF numbers reported in Arora et al. (2017) are on Common Crawl which has 840 billion tokens, and hence have some difference on Toronto Book Corpus containing just 0.98 billion tokens.
  4We use SIF’s publicly available implementation (https://github.com/PrincetonML/SIF) and use SentEval (Conneau & Kiela, 2018) for evaluating BoW and CoMB.
  representation method and remains applicable in the online usecase. The empirical results are quite encouraging, given the fact that we haven’t even utilized the important property of non-associativity for Wasserstein barycenters (i.e., Bp(µ,Bp(ν, ξ)) 6= Bp(Bp(µ, ν), ξ)). This implies that we can take into account the word order with various aggregation strategies, like parse trees, and build the sentence representation by recursively computing barycenters phrase by phrase, which although remains beyond the scope of this paper.
  Overall, this highlights towards the advantage of having distributional estimates for words, that can be extended to give a meaningful representation of sentences via CoMB in a principled manner.
sections.heading: 7 HYPERNYMY DETECTION
sections.text: In linguistics, hypernymy is a relation between words (or sentences) where the semantics of one word (the hyponym) are contained within that of another word (the hypernym). A simple form of this relation is the is-A relation, e.g., cat is an animal. Hypernymy is a special case of the more general concept of lexical entailment, the detection of which is relevant for tasks such as Question Answering (QA). Given a database of lexical entailment relations containing, e.g., is-A(Roger Federer, tennis player) might help a QA system answer “Who is Switzerland’s most successful tennis player?”.
  The early unsupervised approaches for this task exploited different linguistic properties of hypernymy (Weeds & Weir, 2003; Kotlerman et al., 2010; Santus et al., 2014; Rimell, 2014). While most of these are count-based, point embedding based methods (Chang et al., 2017; Henderson & Popa, 2016) have become more popular in recent years. Other approaches represent words by Gaussian distributions with KL-divergence as a measure of entailment (Vilnis & McCallum, 2014; Athiwaratkun & Wilson, 2017). These methods have proven to be powerful, as they not only capture the semantics but also the uncertainty about the contexts in which the word appears.
  Therefore, hypernymy detection is a great testbed to verify the effectiveness of our approach (and the particular formulation) to represent each entity by the distribution of its contexts. To be successful on this task, a method has to consider if all contexts of the hyponym can be encompassed within the contexts of the hypernym. It can’t just get away by predicting words that are similar. Hence, it is natural to make use of the Context Mover’s Distance (CMD), Eq. 3, but with an appropriate ground cost that measures entailment relations well.
  For this purpose, we utilize a recently proposed method by (Henderson & Popa, 2016; Henderson, 2017) which explicitly models what information is known about a word, by interpreting each entry of the embedding as the degree to which a certain feature is present. Based on the logical definition of entailment they derive an operator measuring the entailment similarity between two so-called entailment vectors defined as follows: ~vi=~vj = σ(−~vi)·log σ(−~vj), where the sigmoid σ and log are applied component-wise on the embeddings ~vi, ~vj . Thus, we use as ground cost DHend.ij := −~vi = ~vj . This asymmetric ground cost also shows that our framework can be flexibly used with an arbitrary cost function defined on the ground space.
  For tuning the hyperparameters, we utilize the HypeNet training set of Shwartz et al. (2016) (from the random split),
  Evaluation. In total, we evaluated our method on 10 standard datasets: BLESS (Baroni & Lenci, 2011), EVALution (Santus et al., 2015), Benotto (2015), Weeds et al. (2014), BIBLESS (Kiela et al., 2015), Baroni et al. (2012), Kotlerman et al. (2010), Levy et al. (2014), HypeNet-Test (Shwartz et al., 2016), and Turney & Mohammad (2015). As an evaluation metric, we use average precision AP@all Zhu (2004). Following Chang et al. (2017) we pushed any OOV (out-of-vocabulary) words in the test data to the bottom of the list, effectively assuming that the word pairs do not have a hypernym relation.
  The foremost thing that we would like to check is the benefit of having a distributional estimate in comparison to just the point embeddings. Here, we observe that by employing CMD along with the entailment embeddings, leads to a significant boost on most of the datasets, except on Baroni and Turney, where the performance is still competitive with the other state of the art methods like Gaussian embeddings. The more interesting observation is that on some datasets (EVALution, HypeNet, LenciBenotto) we even outperform or match state-of-the-art performance (cf. Table 2), by simply using CMD together with this ground cost DHend.ij based on the entailment embeddings.
  Notably, this approach is not specific to the entailment vectors from Henderson (2017) and more accurate set of vectors might help additionally. Alternatively, this also suggests that using CMD along with a method that produces embedding vectors (specialized for measuring the degree of entailment) can be a potential way to further improve the performance of that method.
sections.heading: 8 CONCLUSION
sections.text: 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. Motivated by the empirical results on the selected tasks, applying the proposed framework on co-occurrence structures beyond NLP is a promising direction.
sections.heading: A SUPPLEMENTARY MATERIAL
sections.heading: A.1 EXPERIMENTAL DETAILS
sections.text: Sentence Representations. While using the Toronto Book Corpus, we remove the errors caused by crawling and pre-process the corpus by filtering out sentences longer than 300 words, thereby removing a very small portion (500 sentences out of the 70 million sentences). We utilize the code7 from GloVe for building the vocabulary of size 205513 (obtained by setting min count=10) and the co-occurrence matrix (considering a symmetric window of size 10). Note that as in GloVe, the contribution from a context word is inversely weighted by the distance to the target word, while computing the co-occurrence. The vectors obtained via GloVe have 300 dimensions and were trained for 75 iterations at a learning rate of 0.005, other parameters being the default ones. The performance of these vectors from GloVe was verified on standard word similarity tasks.
  Hypernymy Detection. The training of the entailment vector is performed on a Wikipedia dump from 2015 with 1.7B tokens that have been tokenized using the Stanford NLP library (Manning et al., 2014). In our experiments, we use a vocabulary with a size of 80’000 and word embeddings with 200 dimensions. We followed the same training procedure as described in Henderson (2017) and were able to reproduce their scores on the hypernymy detection task. For tuning the hyperparameters, we utilize the HypeNet training set of Shwartz et al. (2016) (from the random split), following the procedure indicated in Chang et al. (2017) for tuning DIVE and Gaussian embeddings.
sections.heading: A.2 PPMI DETAILS
sections.text: Formulation and Variants. Typically, the probabilities used in PMIare estimated from the cooccurrence counts #(w, c) in the corpus and lead to
  PPMI(w, c) = max ( log ( #(w, c)× |Z| #(w)×#(c) ) , 0 ) , (7)
  where, #(w) = ∑ c #(w, c), #(c) = ∑ w #(w, c) and |Z| = ∑ w ∑ c #(w, c). Also, it is known that PPMI is biased towards infrequent words and assigns them a higher value. A common solution is to smoothen8 the context probabilities by raising them to an exponent of α lying between 0 and 1. Levy & Goldberg (2014b) have also suggested the use of the shifted PPMI (SPPMI) matrix where the shift9 by log(s) acts like a prior on the probability of co-occurrence of target and context pairs. These variants of PPMI enable us to extract better semantic associations from the co-occurrence matrix. Finally, we have
  SPPMIα,s(w, c) :=max ( log ( #(w, c)× ∑ c′ #(c ′)α
  #(w)×#(c)α
  ) − log(s), 0 ) .
  Computational aspect. We utilize the sparse matrix support of Scipy10 for efficiently carrying out all the PPMI computations.
  PPMI Column Normalizations. In certain cases, when the PPMI contributions towards the partitions (or clusters) have a large variance, it can be helpful to consider the fraction of Ck’s SPPMI (Eq. 8, 9) that has been used towards a word w, instead of aggregate values used in 4. Otherwise the process of making the histogram unit sum might misrepresent the actual underlying contribution. We call this PPMI column normalization (β). In other words, the intuition is that the normlization will balance the effect of a possible non-uniform spread in total PPMI across the clusters. We observe that setting β to 0.5 or 1 help in boosting performance on the STS tasks. The basic form of column
  7https://github.com/stanfordnlp/GloVe 8pα(c) :=
  #(c)α∑ c′ #(c
  ′)α . 9Here, we denote the shift parameter by s instead of the k defined in (Levy et al., 2015) to avoid confusion
  with the other usage of k. 10https://docs.scipy.org/doc/scipy/reference/sparse.html
  normalization is shown in 9.
  (H̃ w )k := (H̄w)k∑K k=1 (H̄ w )k with (8)
  (H̄w)k := SPPMIα,s(w, Ck)∑ w SPPMIα,s(w, Ck) . (9)
  Another possibility while considering the normalization to have an associated parameter β that can interpolate between the above normalization and normalization with respcect to cluster size.
  (H̃ w β )k := (H̄wβ )k∑K k=1 (H̄ w β )k , where (H̄wβ )k := SPPMIα,s(w, Ck)∑ w SPPMIα,s(w, Ck)β
  (10)
  In particular, when β = 1, we recover the equation for histograms as in 9, and β = 0 would imply normalization with respect to cluster sizes.
sections.heading: A.3 OPTIMAL TRANSPORT
sections.text: Implementation aspects. We make use of the Python Optimal Transport (POT)11 for performing the computation of Wasserstein distances and barycenters on CPU. For more efficient GPU implementation, we built custom implementation using PyTorch. We also implement a batched version for barycenter computation, which to the best of our knowledge has not been done in the past. The batched barycenter computation relies on a viewing computations in the form of block-diagonal matrices. As an example, this batched mode can compute around 200 barycenters in 0.09 seconds, where each barycenter is of 50 histograms (of size 100) and usually gives a speedup of about 10x.
  Scalability. For further scalability, an alternative is to consider stochastic optimal transport techniques (Genevay et al., 2016). Here, the idea would be to randomly sample a subset of contexts from the distributional estimate while considering this transport.
  Stability of Sinkhorn Iterations. For all our computations involving optimal transport, we typically use λ around 0.1 and make use of log or median normalization as common in POT to stabilize the Sinkhorn iterations. Also, we observe that clipping the ground metric matrix (if it exceeds a particular large threshold) also sometimes results in performance gains.
  Value of p. It has been shown in Agueh & Carlier (2011) that when the underlying space is Euclidean and p = 2, there exists a unique minimizer to the Wasserstein barycenter problem. But, since we are anyways solving the regularized Wasserstein barycenter (Cuturi & Doucet, 2014) problem over here instead of the exact one, the particular value of p seems less of an issue. Empirically in the sentence similarity experiments, we have observed p = 1 to perform better than p = 2 (by about 2-3 points).
sections.heading: A.4 CLUSTERING.
sections.text: For clustering, we make use of kmcuda’s12 efficient implementation of K-Means algorithm on GPUs.
sections.heading: A.5 SOFTWARE RELEASE
sections.text: Core code and histograms. We plan to make all our code (for all these parts) and our pre-computed histograms (for the mentioned datasets) publicly available on GitHub soon.
  11http://pot.readthedocs.io/en/stable/ 12https://github.com/src-d/kmcuda
  Standard evaluation suite for Hypernymy. To ease the evaluation pipeline, we have collected the most common benchmark datasets and compiled the code for assessing a model’s performance on hypernymy detection or directionality into a Python package, called HypEval, which is publicly available. This also handles OOV (out-of-vocabulary) pairs in a standardized manner and allows for efficient, batched evaluation on GPU.
sections.heading: A.6 QUALITATIVE ANALYSIS OF SENTENCE REPRESENTATIONS
sections.text: Here, we would like to qualitatively probe the kind of results obtained when computing Wasserstein barycenter of the distributional estimates, in particular, when using CoMB to represent sentences. To this end, we consider a few simple sentences and find the closest word in the vocabulary for CoMB (with respect to CMD) and contrast it to SIF with cosine distance.
  Query CoMB (with CMD) SIF (with cosine, no PC removal)
  [’i’, ’love’, ’her’] love, hope, always, actually, because,doubt, imagine, but, never, simply love, loved, breep-breep, want, clash-clash-clang, thysel, know, think, nope, life
  [’my’, ’favorite’, ’sport’] sport, costume, circus, costumes, outfits,super, sports, tennis, brand, fabulous favorite, favourite, sport, wiccan-type, pastime, pastimes, sports, best, hangout, spectator
  [’best’, ’day’, ’of’, ’my’, ’life’] best, for, also, only, or,anymore, all, is, having, especially life, day, best, c.5, writer/mummy, days, margin-bottom, time, margin-left,night
  [’he’, ’lives, ’in’, ’europe’, ’for’] america, europe, decades, asia, millenium,preserve, masters, majority, elsewhere, commerce lives, europe, life, america, lived, world, england, france, people, c.5
  [’he’, ’may’, ’not’, ’live’] unless, perhaps, must, may, anymore,will, likely, youll, would, certainly may, live, should, will, might, must, margin-left, henreeeee, 0618082132, think
  [’can’, ’you’, ’help’, me’, ’shopping’] anytime, yesterday, skip, overnight, wed,afterward, choosing, figuring, deciding, shopping help, can, going, want, go, do, think, need, able, take
  [’he’, ’likes’, ’to’, ’sleep’, ’a’, ’lot’] whenever, forgetting, afterward, pretending, rowan,eden, casper, nash, annabelle, savannah, lot, sleep, much, besides, better, likes, really, think, probably, talk
  Table 3: Top 10 closest neighbors for CoMB and SIF (no PC removed) found across the vocabulary, and sorted in ascending order of distance from the query sentence. Words in italics are those which in our opinion would fit well when added to one of the places in the query sentence. Note that, both CoMB (under current formulation) and SIF don’t take the word order into account.
  Observations. We find that closest neighbors (see Table 3 ) for CoMB consist of relatively more diverse set of words which fit well in the context of given sentence. For example, take the sentence “i love her”, where CoMB captures a wide range of contexts, for example, “i actually love her”, “i love her because”, “i doubt her love” and more. Also for an ambiguous sentence “he lives in europe for”, the obtained closest neighbors for CoMB include: ‘decades’, ‘masters’, ‘majority’, ‘commerce’ , etc., while with SIF the closest neighbors are mostly words similar to one of the query words. Further, if you look at the last three sentences in the Table 3, the first closest neighbor for CoMB even acts as a good next word for the given query. This suggests that CoMB might perform well on the task of sentence completion, but this additional evaluation is beyond the scope of this paper.
sections.heading: A.7 DETAILED RESULTS
sections.text: Detailed results of the hypernymy detection and sentence representation experiments are listed on the following pages.
  A.7.1 HYPERNYMY DETECTION
  The above listed variants of CMD are the ones with best validation performance on HypeNet-Train (Shwartz et al., 2016). The other hyperparameters (common) for both of them are as follows:
sections.heading: Out of Vocabulary Details.
sections.heading: A.7.2 SENTENCE REPRESENTATION
sections.text: We observe empirically that the PPMI smoothing parameter α, which balances the bias of PPMI towards rare words, plays an important role. While its ideal value would vary on each task, we found the settings mentioned in the Table 6 to work well uniformly across the above spectrum of tasks.
sections.heading: A.8 EFFECT OF PPMI PARAMETERS FOR HYPERNYMY DETECTION
sections.text: This table was generated during an earlier version of the paper, when we were not considering the validation on HypeNet-Train. Hence, the above table doesn’t contain numbers on HypeNet-Test, but an indication of performance on it can be seen in Section A.7.1. In any case, this table suggests that our method works well for several PPMI hyper-parameter configurations.
sections.heading: A.9 EFFECT OF NUMBER OF CLUSTERS
sections.text: Here, we analyse the impact of number of clusters on the performance of Context Mover’s Barycenters (CoMB) for the sentence similarity experiments (c.f. Section 6). In particular, we look at the three best performing variants (A, B, C) on the validation set (STS 16) as well as averaged across them.
  We observe in Figure 3 that on average the performance significantly improves when the number of clusters are increased until around K = 300, and beyond that mostly plateaus (± 0.5). But, as can be seen for variants B and C the performance typically continues to rise until K = 500. It seems that the amount of PPMI column normalization (β = 0.5 vs β = 1) might be at play here.
  Overall, going from K = 300 to K = 500 comes at the cost of increased computation time, and doesn’t lead to a substantial gain in performance. This reflects the tradeoff between accuracy and efficiency. Hence, we stick to K = 300 for our results on sentence similarity tasks.
  Such a trend seems to be inline with the ideal case where we wouldn’t need to do any clustering and just take all possible contexts into account. Thus, it suggests that better ways (other than clustering) to deal with this problem might further boost the performance.
sections.heading: B QUALITATIVE ANALYSIS OF SENTENCE SIMILARITY
sections.text: In this section, we aim to qualitatively analyse the particular examples where our method, Context Mover’s Barycenters (CoMB), performs better or worse than the Smooth Inverse Frequency (SIF) approach from Arora et al. (2017).
sections.heading: B.1 EVALUATION PROCEDURE
sections.text: Comparing by rank. It doesn’t make much sense to compare the raw distance values between two sentences as given by Context Mover’s Distance (CMD) for CoMB and cosine distance for SIF. This is because the spread of distance values across sentence pairs can be quite different. Note that the quantitative evaluation of these tasks is also carried out by Pearson/Spearman rank correlation of the predicted distances/similarities with the ground-truth scores.
  Thus, in accordance with this reasoning, we compare the similarity score of a sentence pair relative to its rank based on ground-truth score (amongst the sentence pairs for that dataset). So, the better method should rank sentence pairs closer to the ranking obtained via ground-truth scores.
sections.heading: Ground-Truth Score Implied meaning
sections.text: Ground-truth details. The ground-truth scores (can be fractional) and range from 0 to 5, and the meaning implied by the integral score values can be seen in the Table 10. In the case where different examples have the same ground-truth score, the ground-truth rank is then based on lexicographical ordering of sentences for our qualitative evaluation procedure. (This for instance means that sentence pairs ranging from 62 to 74 would correspond to the same ground-truth score of 4.6). The ranking is done in the descending order of sentence similarity, i.e., most similar to least similar.
  Example selection criteria. For all the examples, we compare the best variants of CoMB and SIF on those datasets. We particularly choose those examples where there is the maximum difference in ranks according to CoMB and SIF, as they would be more indicative of where a method succeeds or fails. Nevertheless, such a qualitative evaluation is subjective and is meant to give a better understanding of things happening under the hood.
sections.heading: B.2 EXPERIMENTS AND OBSERVATIONS
sections.text: We look at examples from three datasets, namely: Images from STS15, News from STS14 and WordNet from STS14 to get a better idea of an overall behavior. In terms of aggregate quantitative performance, on Images and News datasets, CoMB is better than SIF, while the opposite is true for WordNet. These examples across the three datasets may not probably be exhaustive and are up to subjective interpretation, but hopefully will lend some indication as to where and why each method works.
sections.heading: B.2.1 TASK: STS14, DATASET: NEWS
sections.text: We look in detail at the examples in News dataset from STS 2014 (Agirre et al., 2014). The results of qualitative analysis on Images and WordNet datasets can be found in Section B.5. For reference, CoMB does a better job overall with a Pearson correlation (x100) of 64.1 versus 43.0 for SIF, as presented in Table 6. The main observations are:
  Observation 1. Examples 1, 2, 4, 5 are sentence pairs which are equivalent in meaning (c.f. Table 10), but typically have additional details in the predicates of the sentences. Here, CoMB is
  better than SIF at ranking the pairs closer to the ground-truth ranking. This probably suggests the averaging of word embeddings, which is the 1st step in SIF, is not as resilient to the presence of such details than the Wasserstein barycenter of distributional estimates in CoMB. We speculate that when having distributional estimates (where multiple senses or contexts are considered), adding details can help towards refining the particular meaning implied.
  Observation 2. Let’s consider the examples 3 and 6 where SIF is better than CoMB. These are sentence pairs which are equivalent or roughly equivalent in meanings, but with a few words substituted (typically subjects) like “judicial order” instead of “court” in example 3. Here it seems that the substitution is adverse for CoMB while considering varied senses through the distributional estimate, in comparison to looking at the “point” meaning given by SIF.
  Observation 3. In 7, 8, and 10, each sentence pair is about a common topic, but the meaning of individual sentences is quite different. For instance, example 8: “south korea launches new bullet train reaching 300 kph” & “south korea has had a bullet train system since the 1980s”. Or like in example 10: “china is north korea ’ s closest ally” & “north korea is a reclusive state”. Note that typically in these examples, the subject is same in a sentence pair, and the difference is mainly in the predicate. Here, CoMB identifies the difference and ranks them closer to the ground-truth. Whereas, SIF fails to understand this and ranks them as more similar (and far away) than the ground-truth.
  Observation 4. The examples 9, 11, and 12 are related sentences and differ mainly in details such as the name of the country, person, department, i.e. proper nouns. In particular, consider example 9: “south korea and israel oppose proliferation of weapons of mass destruction and an arms race” & “china will resolutely oppose the proliferation of mass destructive weapons”. The main difference in these examples stems from differences in the subject rather than the predicate. CoMB considers these sentence pairs to be more similar than suggested by ground-truth. Hence, in such scenarios where the subject (like the particular proper nouns) makes the most difference, SIF seems to be better.
sections.heading: B.3 CONCLUSIONS FROM QUALITATIVE EXAMPLES
sections.text: Summarizing the observations from the above qualitative analysis on News dataset 13, 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). • 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.
  13Similar findings can also be seen for the two other datasets in Section B.5.
sections.heading: B.4 EFFECT OF SENTENCE LENGTH
sections.text: In this section, we look at the length of sentences across all the datasets in each of the STS tasks. Average sentence length is one measure of the complexity of a particular dataset. But looking at just sentence lengths may not give a complete picture, especially for the textual similarity tasks where there can be many words common between the sentence pairs. The Table 12 shows the various statistics of each dataset, with respect to the sentence lengths along with the better method on each of them (out of CoMB and SIF).
  Task-Dataset # sentence pairs Avg. sentence length Avg. word overlap (per sentence pair) Avg. effective sentence length (excluding common words) Better method
sections.heading: Observations.
sections.text: • We notice that on datasets with longer effective sentence lengths, CoMB performs better than SIF on average. There might be other factors at play here, but if one had to pick on the axis of effective sentence length, CoMB leads over SIF 14. • The above statement also aligns well with the observation 1 from the qualitative analysis
  (c.f. Section B.2.1), that having more details can help in refining the particular meaning or sense implied by CoMB. (Effective sentence length can serve as a good proxy for indicating the amount of details.) • It also seems to explain why both methods don’t perform well (see Table 6) on STS13-
  FNWN, which has on average the maximum effective sentence length (of 20.4). • To an extent, it also points towards the effect of corpora. For instance, in a corpus such as
  WordNet, which has a low average sentence length and with examples typically concerned about word definitions (see Table 14), SIF seems to be better of the methods. On the other hand, CoMB seems to be better for News (Table 11), Image captions (Table 13) or Forum.
  14Effective sentence length averaged across datasets where CoMB is better is 7.48. Contrast this to an average effective sentence length of 5.03 across datasets where SIF is better.
sections.heading: B.5 ADDITIONAL QUALITATIVE ANALYSIS
sections.heading: B.5.1 TASK: STS15, DATASET: IMAGES
sections.text: We consider the sentence pairs from Images dataset in STS15 task (Agirre et al., 2015), as presented in Table 13. As a reminder, CoMB outperforms SIF on this dataset with a Pearson correlation (x100) of 63.1 versus 51.7, as mentioned in Table 7.. The main observations are:
  Observation A. Example 1 to 5 indicate pairs of sentences which are essentially equivalent in meaning, but with varying degrees of equivalence. Here, we can see that CoMB with CMD is able to rank the similarity between these pairs quite well in comparison to SIF, even when their way of describing is different. For instance, example 2 : “a boy waves around a sparkler” & “a young boy is twisting a sparkler around in the air”. This points towards the benefit of having multiple senses or contexts encoded through the distributional estimate in CoMB.
  Observation B. Next, in the examples 7 to 10, which consist of sentence pairs that are not equivalent but have commonalities (about the topic). Here, SIF ranks the sentences closer to the ground-truth ranking while CoMB interprets these pairs as being more common in meaning than given by ground-truth. This could be the consequence of comparing the various senses or contexts implied by the sentence pairs via CMD. Take for instance, example 10, “three dogs running in the dirt” & “the yellow dog is running on the dirt road”. Since these sentences are about the similar topic (and the major difference is in their subject), this can result in CMD considering them more similar than cosine distance.
  Observation C. For sentences which are completely dissimilar as per ground-truth, let’s look at example 11 and 12. Consider 11, which is “a little girl and a little boy hold hands on a shiny slide”
  & “a little girl in a paisley dress runs across a sandy playground”, the sentences meaning totally different things and CoMB seems to be better at ranking than SIF. But, consider example 12: “a little girl walks on a boardwalk with blue domes in the background” & “a man going over a jump on his bike with a river in the background”. One common theme15 can be thought as “a person moving with something blue in the background”, which can result in CoMB ranking the sentence as more similar. SIF also ranks it higher (at 591) than ground-truth (696), but is more closer than CoMB which ranks it at 310.
sections.heading: B.5.2 TASK: STS14, DATASET: WORDNET
sections.text: Lastly, we discuss the examples and observations derived from the qualitative analysis on WordNet dataset from STS14 (Agirre et al., 2014). This dataset is comprised of sentences which are the definitions of words/phrases, and sentence length is typically smaller than the datasets discussed before. For reference, SIF (76.4) does better than CoMB (67.2) in terms of average Pearson correlation (x100), as mentioned in Table 6.
  Observation D. Consider examples 1 to 6 as shown in Table 14, which fall in the category of equivalent sentences but in varying degrees. The sentence pairs essentially indicate different ways of characterizing equivalent things. Here, CoMB is able to rank the similarity between sentences in a better manner than SIF. Specifically, see example 2: “( cause to ) sully the good name and reputation of” & “charge falsely or with malicious intent ; attack the good name and reputation of someone”. It seems that SIF is not able to properly handle the additional definition present in sentence 2 and ranks this pair much lower in similarity at 534 versus 235 for CoMB. This is also in line with observation 1 about added details in the Section B.2.1.
  15Of course, this is upto subjective interpretation.
  Observation E. In the examples 7 to 9, where CoMB doesn’t do well in comparison to SIF, mainly have a slight difference in the object of the sentence. For instance, in example 9: “a person who is a member of the senate” & “a person who is a member of a partnership”. So based on the kind of substituted word, looking at its various contexts via the distributional estimate can make it more or less similar than desired. In such cases, using the “point” meanings of the objects seems to fare better. This also aligns with the observations 2 and 4 in the Section B.2.1.
sections.heading: C QUALITATIVE ANALYSIS OF HYPERNYMY DETECTION
sections.text: Here, our objective is to qualitatively analyse the particular examples where our method of using Context Mover’s Distance (CMD) along with embeddings from Henderson (2017) performs better or worse than just using these entailment embeddings alone.
sections.heading: C.1 EVALUATION PROCEDURE
sections.text: Comparing by rank. Again as in the qualitative analysis with sentence similarity, it doesn’t make much sense to compare the raw distance/similarity values between two words as their spread across word pairs can be quite different. We thus compare the ranks assigned to each word pair by both the methods.
  Ground-truth details. In contrast to graded ground-truth scores in the previous analysis, here we just have a binary ground truth: ‘True’ if the hyponym-hypernym relation exists and ‘False’ when it doesn’t. We consider the BIBLESS dataset (Kiela et al., 2015) for this analysis, which has a total of 1668 examples. Out of these, 33 word pairs are not in the vocabulary (see Table 5), so we ignore them for this analysis. Amongst the 1635 examples left, 814 are ‘True’ and 821 are ‘False’. A perfect method should rank the examples labeled as ‘True’ from 1 to 814 and the ‘False’ examples from 815 to 1635. Of course, achieving this is quite hard, but the better of the methods should rank as many examples in the desired ranges.
  Example selection criteria. We look at the examples where the difference in ranks as per the two methods is the largest. Also, for a few words, we also look at how each method ranks when present as a hypernym and a hyponym. If the difference in ranks is defined as, CMD rank - Henderson Rank, we present the top pairs where this difference is most positive and most negative.
sections.heading: C.2 RESULTS
sections.text: For reference on the BIBLESS dataset, CMD performs better than Henderson embeddings quantitatively (c.f. Table 2). Let’s take a look at some word pairs to get a better understanding.
sections.heading: C.2.1 MAXIMUM POSITIVE DIFFERENCE IN RANKS
sections.text: These are essentially examples where CMD considers the entailment relation as ‘False’ while the Henderson embeddings predict it as ‘True’, and both are most certain about their decisions. Table 15 shows these pairs, along with ranks assigned by the two methods and the ground-truth label for reference.
  Some quick observations: many of the word pairs which the Henderson method gets wrong are co-hyponym pairs, such as: (‘banjo’, ‘flute’), (‘guitar’, ‘trumpet’), (‘turnip, ‘radish’). Additionally, (‘bass’, ‘cello’ ), (‘creature’, ‘gorilla’), etc., are examples where the method has to assess not just if the relation exists, but also take into account the directionality between the pair, which the Henderson method seems unable to do.
sections.heading: C.2.2 MAXIMUM NEGATIVE DIFFERENCE IN RANKS
sections.text: Now the other way around, these are examples where CMD considers the entailment relation as ‘True’ while the Henderson embeddings predict it as ‘False’, and both are most certain about their decisions. Table 16 shows these pairs. The examples where CMD performs poorly like, (‘box’, ‘mortality’), (‘pistol’, ‘initiative’) seem to be unrelated and we speculate that matching the various contexts or
  Hypernym candidate Hypernym candidate Ground Truth CMD rank Henderson rank Better Method
  senses of the distributional estimate causes this behavior. One possibility to deal with this can be to take into account the similarity between word pairs in the ground metric. Overall, CMD does a good job at handling these pairs in comparison to the Henderson method.
  Hyponym candidate Hypernym candidate Ground Truth CMD rank Henderson rank Better Method
title: CONTEXT MOVER’S DISTANCE & BARYCENTERS: OPTIMAL TRANSPORT OF CONTEXTS FOR BUILDING REPRESENTATIONS