Word embedding-based similarity measures are currently among the top-performing methods on unsupervised semantic textual similarity (STS) tasks. Recent work has increasingly adopted a statistical view on these embeddings, with some of the top approaches being essentially various correlations (which include the famous cosine similarity). Another excellent candidate for a similarity measure is mutual information (MI), which can capture arbitrary dependencies between the variables and has a simple and intuitive expression. Unfortunately, its use in the context of dense word embeddings has so far been avoided due to difficulties with estimating MI for continuous data. In this work we go through a vast literature on estimating MI in such cases and single out the most promising methods, yielding a simple and elegant similarity measure for word embeddings. We show that mutual information is a viable alternative to correlations, gives an excellent signal that correlates well with human judgements of similarity and rivals existing state-of-the-art unsupervised methods. Neural text embeddings learned from unlabeled data are a key component of modern approaches to semantic textual similarity (STS). Despite the impressive performance of large pretrained models (Kiros et al., 2015; Conneau et al., 2017; Subra-manian et al., 2018; Cer et al., 2018; Peters et al., 2018; Radford, 2018; Devlin et al., 2018; Dai et al., 2019; Yang et al., 2019a) on a a plethora of hard NLP tasks, deep models do not currently offer a clear advantage over much simpler static word embeddings (Bengio et al., 2003; Mikolov et al., 2013; Pennington et al., 2014; Bojanowski et al., 2017; Joulin et al., 2017) on standard unsupervised STS benchmarks (Hill et al., 2016; Arora et al., 2017; Wieting et al., 2016; Wieting and Gimpel, 2018; Zhelezniak et al., 2019b,a,c). Instead, the main sources of improvement here have come from training on supervised paraphrastic corpora (Wieting et al., 2015, 2016; Wieting and Gimpel, 2018), designing better composition functions (Mitchell and Lapata, 2008; De Boom et al., 2016; Arora et al., 2017; Zhao and Mao, 2017; Ruckle et al., 2018; Zhelezniak et al., 2019b,c; Yang et al., 2019b) and exploring novel similarity measures between word embeddings, in particular those inspired by optimal transport (Kusner et al., 2015; Huang et al., 2016), soft and fuzzy sets (Jimenez et al., 2010, 2015; Zhelezniak et al., 2019b), and statistics (Lev et al., 2015; Nikolentzos et al., 2017; Torki, 2018; Zhelezniak et al., 2019a,c). Recently, Zhelezniak et al. (2019a,c) advocated for a new statistical perspective on word embeddings where each word embedding itself is viewed as a sample of (e.g. 300) observations from some scalar random variable. They conducted a statistical analysis of several popular pretrained word embeddings and their compositions and established that the ubiquitous cosine similarity is practically equivalent to Pearson correlation. They also demonstrated significant gains in performance when one instead uses non-parametric rank correlation coefficients (Spearman's  , Kendall's  ) and cross-covariance operators between reproducing kernel Hilbert spaces (Hilbert-Schmidt inde-pendence criterion (HSIC) (Gretton et al., 2005), Centered Kernel Alignment (CKA)) (Cortes et al., 2012; Kornblith et al., 2019). One prominent alternative to those correlation-based approaches is mutual information (MI), which is of great importance in information theory and statistics. In some sense, mutual information is an excellent candidate for a similarity measure between word embeddings as it can capture arbitrary dependencies between the variables and has a simple and intuitive expression. Unfortunately, its use in the context of continuous dense word representations has so far been avoided due to the difficulties in estimating MI for continuous random variables (joint and marginal densities are not known in practice). In this work we make the first steps towards the adoption of MI as a measure of semantic similarity between dense word embeddings. We begin our discussion with how to apply MI for this purpose in principle. Next we carefully summarise the vast literature on estimation of MI for continuous random variables and identify approaches most suitable for our use case. Our chief goal here is to identify the estimators that yield elegant, almost closed-form expressions for the resulting similarity measure as opposed to complicated estimation procedures. Finally, we show that such estimators of mutual information give an excellent signal that correlates very well with human judgements and comfortably rivals existing state-of-the-art unsupervised STS approaches. Suppose we are given a word embedding matrix W  RN  D , where N is the vocabulary size and D is the embedding dimension (commonly D = 300 ). Ultimately, the matrix W is simply a table of some numbers and just like any dataset, it is subject to a statistical analysis. There are essentially two ways we can proceed: we can either choose to view W as N observations from D random variables or we can instead consider WT and view it as D observations from N random variables. The first approach allows us to study global' properties of the word embedding space (e.g. via PCA, clustering, etc.) and defines global' similarity structures, such as Mahalanobis distance, Fisher kernel (Lev et al., 2015), etc. In the second approach we study the distribution P ( W 1 , W 2 , . . . , WN ) , where a word embedding w i is a sample of D ( = 300 ) observations from some scalar random variable W i corresponding to the word w i (Zhelezniak et al., 2019a,c). The local' similarity between two words w i and w j is then encoded in the dependencies between the corresponding random variables W i , W j . Since the distribution P ( W i , W j ) is unknown, we estimate these dependencies based on the sample w i , w j . Certain dependencies can be captured by Pearson, Spearman and Kendall correlation coefficients between word embeddings (cid:98)  ( w i , w j ) , where the choice of the coefficient depends on the statistics of each word embedding model (Zhelezniak et al., 2019a). Conveniently, correlations can also be used to measure semantic similarity between two sets of words (e.g. phrases and sentences) if one considers the correlations between random vectors X = ( X 1 , X 2 , . . . , X l x ) and Y = ( Y 1 , Y 2 , . . . , Y l y ) , where scalar random variables X i correspond to the words in the first sentence and Y j to the words in the second sentence. This, for example, can be done by first pooling (e.g. meanor max-pooling) random vectors into scalar variables X pool and Y pool and then estimating univariate correlations corr ( X pool , Y pool ) as before. Alternatively, we can measure correlations between random vectors directly using norms of cross-covariance ma-trices/operators (e.g. the Hilbert-Schmidt inde-pendence criterion (Gretton et al., 2005)). Both approaches are known to give excellent results on standard STS benchmarks (Zhelezniak et al., 2019c). A viable alternative to correlations is mutual information (MI), which can detect any kind of dependence between random variables, but which has so far not been explored for this problem. We operate within the previous setting where we consider two sentences x = x 1 x 2 . . . x l x and y = y 1 y 2 . . . y l y . Our goal now is to estimate the mutual information I ( X ; Y ) between the corresponding random vectors X = ( X 1 , X 2 , . . . , X l x ) and Y = ( Y 1 , Y 2 , . . . , Y l y ) I ( X ; Y ) = (cid:90)(cid:90) p XY ( x, y ) log p XY ( x, y ) p X ( x ) p Y ( y ) d x d y, (1) where p XY ( x, y ) is the joint density of X and Y and p X ( x ) = (cid:82) Y p XY ( x, y ) d y and p Y ( y ) = (cid:82) X p XY ( x, y ) d x are the marginal densities. Unfortunately, these theoretical quantities are not available to us and we must somehow estimate (cid:98) I ( X ; Y ) directly from the word embeddings (cid:98) X = ( x (1) , x (2) , . . . , x ( l x ) ) and (cid:98) Y = ( y (1) , y (2) , . . . , y ( l y ) ) . Luckily, there is a vast literature on how to estimate mutual information between continuous random variables based on the sample. The first class of methods partitions the supports X , Y into a finite number of bins of equal or unequal (adaptive) size and estimates (cid:98) I ( X ; Y ) based on discrete counts in each bin (Moddemei-jer, 1989; Fraser and Swinney, 1986; Darbellay and Vajda, 1999; Reshef et al., 2011; Ince et al., 2016). While such methods are easy to understand conceptually, they might suffer from the curse of dimensionality (especially when sentences are long) and in some sense violate our desire for an elegant closed-form similarity measure. The next class of methods constructs kernel density estimates (KDE) and then numerically integrates such approximate densities to obtain MI (Moon et al., 1995; Steuer et al., 2002). These methods might require a careful choice of kernels and the bandwidth parameters and also violate our simplicity requirement. The third class of methods that has recently gained popularity in the deep learning community is based on neural-network-based estimation of various bounds on mutual information (e.g. by training a critic to estimate the density ratio in (1)) (Suzuki et al., 2008; Alemi et al., 2017; Belghazi et al., 2018; Hjelm et al., 2019; Poole et al., 2019). Such estimators are usually differentiable and scale well to high dimensions and large sample sizes (Belghazi et al., 2018). However, in our case the sample size (e.g. 300) and dimensionality are not too large (at least for short phrases and sentences), and thus training a separate neural network for a simple similarity computation is hardly justified. This leaves us with the last class of methods that estimates mutual information from the k -nearest neighbour statistics (Kraskov et al., 2004; Ver Steeg and Galstyan, 2013; Ver Steeg, 2014; Ross, 2014; Gao et al., 2015; Gao et al., 2018). These approaches are not without problems (Gao et al., 2015) and inherit the weaknesses of k NN in large dimensions but are very simple to implement. In particular, we focus on the Kraskov StogbauerGrassberger (KSG) estimator (Kraskov et al., 2004) which admits a particularly elegant expression for the resulting similarity measure. It can be verified that the mutual information is given by I ( X ; Y ) = H ( X ) + H ( Y )  H ( X , Y ) , i.e. the difference between the sum of marginal entropies and the joint entropy. Thus, in order to estimate MI, it is sufficient to be able to estimate various entropies in the above equation. In their seminal work, Kozachenko and Leonenko (1987) show how to estimate such differential entropies based on the nearest neighbour statistics. Concretely, these methods approximate the log-density Algorithm 1 KraskovStogbauerGrassberger (KSG) Similarity Measure Require: Word embeddings for the first sentence X  R l x  D Require: Word embeddings for the second sentence Y  R l y  D Require: The number of nearest neighbours k < D (default k = 3 ) Ensure: Similarity measure KSG Z  STACK ROWS ( X , Y ) || z i  z j || Z  max( || x i  x j || X , || y i  y j || Y ) i, j = 1 , . . . , D #  set cardinality for z d , d = 1 , . . . , D do (cid:15) [ d ]  || z d  z d k || , z d k = k -NN of z d n x [ d ]  # { x d (cid:48) : || x d  x d (cid:48) || X < (cid:15) [ d ] } n y [ d ]  # { y d (cid:48) : || y d  y d (cid:48) || Y < (cid:15) [ d ] } d (cid:48)  { 1 , . . . D } \ { d } end for  ( x )  digamma function S  (cid:80) Dd =1 (  ( n x [ d ] + 1) +  ( n y [ d ] + 1)) KSG   ( D ) +  ( k )  S at a point by a uniform density in a e.g. Euclidean or Chebyshev norm ball containing its k -nearest neighbours. Kraskov et al. (2004) modify this idea to construct their famous KSG estimator of mutual information given by KSG ( X ; Y ) =  ( D ) +  ( k )  D (cid:88) d =1 (  ( n x [ d ] + 1) +  ( n y [ d ] + 1)) , (2) where D is the embedding dimension, k is the number of nearest neighbours,  ( x ) =  (cid:48) ( x ) / ( x ) is the digamma function and n x [ d ] , n y [ d ] are certain nearest neighbour statistics. These statistics are obtained by counting the number of neighbours that fall within less than (cid:15) [ d ] from x d and y d in the marginal spaces X and Y respectively, where (cid:15) [ d ] is the distance from z d = ( x d , y d ) to its k nearest neighbour in the joint space ( X , Y ) . We illustrate how the estimator can be applied to measure similarity between sets of word embeddings in Algorithm 1 and refer the reader to Kraskov et al. (2004) for its full derivation and justification as well as an alternative version. We now explore the empirical performance of the KSG similarity measure on a standard suite of Semantic Textual Similarity (STS) benchmarks (Agirre et al., 2012, 2013, 2014, 2015, 2016) and report Spearman correlation between the system and human scores. Our focus here is on fastText vectors (Bojanowski et al., 2017) trained on Common Crawl (600B tokens), as previous literature suggests that among unsupervised vectors fastText yields the best performance for all tasks and similarity measures (Conneau et al., 2017; Perone et al., 2018; Zhelezniak et al., 2019a,b,c). We defer evaluations and significance analysis on all 24 STS subtasks for other word vectors (word2vec and GloVe) to the Appendix. Our evaluations are run in the SentEval toolkit (Conneau and Kiela, 2018) and our code is available on GitHub 1 . Note that we do not report results on the STS13 SMT subtask as it is no longer publicly available. The number of nearest neighbours for KSG that is known to work well in practice on a variety of datasets is k = 3 (Kraskov et al., 2004; Khan et al., 2007). This value seems to strike a good balance between the bias and variance of the estimator. We also run experiments for k = 10 to show that KSG is not very sensitive to this hy-perparameter, at least in our setting. As an interesting addition, we also run KSG ( k = 10 ) for max-pooled scalar random variables (Max-Pool+KSG 10). We compare KSG to the following approaches from the literature: Universal Sentence Encoder (Transformer) (Cer et al., 2018), BERT (penultimate layer, mean-pooling) (Devlin et al., 2018), Word Mover's Distance (WMD) (Kus-ner et al., 2015), soft cardinality (Jimenez et al., 2010, 2015) with cosine similarity and the softness parameter p = 1 , DynaMax-Jaccard (Zhelez-niak et al., 2019b), mean-pooling with cosine similarity (MeanPool+COS) and Smooth Inverse Frequency (SIF) + PCA (Arora et al., 2017). Next we compare KSG with the following top-performing correlations: max-pooling with Spearman correlation (MaxPool+SPR), Centered Kernel Alignment (Gaussian kernel with median estimation for  2 ) and distance correlation (Zhelezniak et al., 2019c). The evaluation results are given in Table 1. In summary, we can see that similarity measures based on mutual information (KSG) perform on par with top correlation-based measures and other leading methods from the literature. Moreover, KSG between pooled variables (MaxPool) is faster and performs only slightly worse than multivariate KSG. In this work we explored how to apply mutual information (MI) as a semantic similarity measure for continuous dense word embeddings. We have summarised the vast literature on estimating MI for continuous random variables from the sample and singled out a simple and elegant KSG estimator which is based on elementary nearest-neighbour statistics. We showed empirically that this estimator and mutual information in general can be an excellent candidate for a similarity measure between dense word embeddings. We would like to thank Adam Bozson and the four anonymous reviewers for their useful feedback and suggestions.
abstain abstain abstain abstain abstain result abstain other other abstain abstain abstain abstain abstain abstain objective objective method objective result method abstain method abstain method abstain abstain abstain other abstain method abstain abstain method other other abstain abstain abstain abstain abstain other abstain method abstain abstain result abstain abstain abstain other other abstain method abstain abstain abstain abstain result abstain abstain result abstain other abstain abstain result abstain objective abstain result other