Re-evaluating Word Mover's Distance
Authors: Ryoma Sato
Makoto Yamada
Hisashi Kashima
Venue: ICLR 2022 Submitted (2022)
Keywords: optimal transport
word mover's distance

Abstract: The word mover's distance (WMD) is a fundamental technique for measuring the similarity of two documents. As the crux of WMD, it can take advantage of the underlying geometry of the word space by employing an optimal transport formulation. The original study on WMD reported that WMD outperforms classical baselines such as bag-of-words (BOW) and TF-IDF by significant margins in various datasets. In this paper, we point out that the evaluation in the original study could be misleading. We re-evaluate the performances of WMD and the classical baselines and find that the classical baselines are competitive with WMD if we employ an appropriate preprocessing, i.e., L1 normalization. In addition, We introduce an analogy between WMD and L1-normalized BOW and find that not only the performance of WMD but also the distance values resemble those of BOW in high dimensional spaces.

Under review as a conference paper at ICLR 2022
RE- RE-EVALUATING WORD MOVER'S DISTANCE
Anonymous authors Paper under double-blind review
ABSTRACT
The word mover's distance (WMD) is a fundamental technique for measuring the similarity of two documents. As the crux of WMD, it take advantage of the underlying geometry of the word space by employing an optimal transport formulation. The original study WMD reported that WMD outperforms classical baselines such as bag-of-words (BOW) and TF-IDF by significant margins in various datasets. In this paper, point out that the evaluation in the original study could be misleading. We re-evaluate the performances of WMD and the classical baselines and find that the classical baselines are competitive with WMD if we employ an appropriate preprocessing, i.e., LI normalization. In addition, We introduce an analogy between WMD and I.1 -l-nommalleeed BOW and find that not only the performance of WMD but also the distance values resemble those of BOW in high dimensional spaces.
INTRODUCTION
The optimal transport (OT) distance is effective tool for comparing probabilistic distributions. Applications of OT include image pro- cessing (Ni et al., 2009; Rabin et al., 2011; De Goes al., 2012), natural language processing (NLP) (Kusner et al., 2015; Rolet et al., 2016), biology (Schiebinger et al., 2019; Lozupone & Knight, 2005;
Obama speaks the media Illinols
vs the president greets the press Chicago
Cbama
greets
speaks
President
Evans & Matsen, 20, and generative models (Arjovsky et al., 2017; Salimans et al., 2018).
Chicago
media
A prominent application of OT is the word mover's 's distance (WMD) (Kusner al., 2015) for document comparison. WMD regards a doc- ument as probabilistic distribution of words, defines the underlying word geometry using pre-trained word embeddings, and computes the distance using the optimal transport distance between two word distributions (i.e., documents). WMD is preferable because takes the underlying geometry into account. For example, oo-ds (BOW) will conclude that two documents are dissimilar if they have no common words, whereas WMD will determine that they similar if the words are semantically similar (even if they are not exactly the same), as illustrated in Figure 1.
press
Iliinois
Obama speaks the media Illinols
vs The band gave concert in Japan
Obama
gave
band
speaks
media
Japan
concert
Ilinnis
Figure 1: Neither pair of texts has common words. WMD choose similar sen- tence appropriately, whereas the BOW distance cannot dis- tinguish these cases.
WMD has been widely used in NLP owing to this preferred property. For example, Kusner al. (2015) and others (Huang et al., 2016; Li
et al., 2019) used WMD for document classification, Wu et al. (2018)
used WMD for computing document embeddings, Xu et al. (2018)
used WMD for topic modeling, Kilickaya et al. (2017) and others
(Clark et al., 2019; Zhao et al., 2019; 2020; Wang et al., 2020a; Gao et al., 2020; Lu et al., 2019; Chen et al., 2020b) used WMD for evaluating text generation. Many extensions have been proposed including supervised (Huang et al., 2016; Takezawa et al., 2021) and fast (Le et al., 2019; Backurs al., 2020; Genevay et al., 2016 6; Dong et al., 2020; Sato et al., 2020b) variants. WMD is one of the fundamental tools used in NLP, and understanding the deep mechanism of WMD is erucial for further applications.
The most fundamental application of WMD is document classification. The original study on WMD (Kusner et al., 2015) conducted extensive experiments using kNN classifiers. Figure 2 shows the

---

Under review as a conference paper at ICLR 2022
70
4 better
59
61
63
58
KNN classifiction
44
44
42
40
36
33
30
29
29
28
27
21
BOW
TF-ID
BOW
TF-IDF
WMD
BOW
TF-IDF
WMD
BOW
TF-IDF
WMD
BOW
FF-IDF
14
IF-IDE
BOW
IF-IDF
BOW
TF-IDF
WMD
3.5
bbcsport
twitter
recipe
ohsumed
classic
reuters
amazon
20news
Figure 2: kNN classification errors reported in the original WMD paper (Figure in (Kusner et al.,
2015)). Lower is better. WMD outperformed the naive baselines by significant margins.
reported in (Kusner al., 2015). This figure clearly shows that WMD is superior to classical baselines, BOW and TF-IDE
classification
Figure 2 is surprising in the following senses. First, WMD outperforms the classical baselines by excessively large margins. BOW and TF-IDF have long been recognized as effective tools for document classification. Although is reasonable for WMD to outperform them, the improvements are surprisingly large. In particular, the performance is ten times better on the classic dataset and five times better the bbcsport dataset. Such results are excessively impressive. Second, although TF-IDF is known to be more effective than BOW, it performs worse than BOW the ohsumed, reuters, and amazon datasets. In fact, the number of misclassification doubles on the reuters datasets.
In this paper, we point out the possibility that the evaluations conducted in the original WMD study (Kusner et al., 2015) are misleading. Specifically, we found that the main improvements of WMD were due to normalization. Using the same normalization, WMD is comparable to BOW and TF-IDF, or WMD achieves improvements only two to eight percent at the price of heavy computations. We also confirm that TF-IDF is more effective than BOW if employ adequate normalization.
To understand the mechanism of WMD, we introduce an analogy between WMD and LI- n-rommalizeed BOW. We experimentally find that the distribution of the distances between matched words is not Gaussian-lis like but woo-modal in high dimensional spaces. We then find that not only the performance of WMD but also the distance values resemble those of BOW in high dimensional spaces.
The contributions of this paper are summarized as follows.
We point out that the performance of WMD is not as high as we previously believed. The performance is comparable classical baselines in document classification with the same normalization.
We introduce an analogy between WMD and Ll-nnomalized BOW (Proposition 1) and find that WMD resembles BOW in high dimensional spaces (Figure 5).
We point several confusing aspects in the evaluations conducted in the original study WMD. We suspect that many readers and researchers are unaware of these issues. Clarifying them is crucial for solid evaluation and analysis in this field
Reproducibility. We include our code in the supplementary materials. It contains script to download datasets and pre-computed results, algorithm implementations, and evaluation code.
2 RELATED WORK
Word Mover's Distance (WMD) and Optimal Transport (OT) in NLP. WMD (Kusner et al., 2015) is one of the most thriving applications of OT. WMD can take the underlying word geometry into account and inherit many elegant theoretical properties from OT. The success of WMD has facilitated many applications of OT in NLP. EmbDist (Kobayashi et al., 2015) a method concurrent
It should be noted that (Kusner et al., 2015) used many stronger baselines such LSI and LDA. We focus BOW and TF-IDF because () BOW was used as the base performance (Figure 4 in (Kusner et al., 2015), Figure in (Yurochkin al., 2019)), and (ii) BOW special of WMD (Propositoin
2

---

Under review as a conference paper at ICLR 2022
with WMD. It also regards document as distribution of word embeddings but uses greedy matching instead of OT. Kumar et al. (2017) apply WMD to hidden representations of words instead of raw word embeddings. Yurochkin et al. (2019) consider document a distribution of topics and compute the document similarities using OT. They also use the OT distance for computing the ground distance of the topics. Alvarez-Melis et al. (2018) proposed structured OT and applied it document comparison to take the positional consistency into account. Singh et al. (2020) consider a word as a probabilistic distribution of surrounding words and compute the similarity of the words using the OT distance of the distributions. Muzellec & Cuturi (2018) and others (Deudon, 2018; Frogner al., 2019; Sun et al., 2018) embed words or sentences into distributions instead of vectors and compute the distance between embeddings using OT. Chen et al. (2019) and others (Li et al., 2020; Chen et al., 2020a) regularize the text generation models based on the OT distance between the generated texts and the ground truth texts to improve the generation. Nested Wasserstein (Zhang et al., 2020a) compares the distributions of sequences and is successfully used in imitation learning for text generation. Lei et al. (2019) use WMD to generate paraphrase texts for creating adversarial examples. Zhang et al. (2020b) introduced partial OT to drop meaningless words. Michel et al. (2017) use a Gromov Wasserstein-liks distance instead of the standard OT to compare documents. Zhang et al. (2016) and others (Zhang et al., 2b;7;;a; Grave et al., 2019; Dou & Neubig, 2021) use OT to align word embeddings of different languages. Trapp al. (2017) use WMD to compare compositional documents by weighting each document. Kilickaya et al. (2017) and others (Clark et al., 2019; Zhao et al., 2019; 2020; Wang et al., 2020a: Gao et al., 2020; Lu et al.. 2019; Chen et al., 2020b) used WMD for evaluating text generation. BERTScore (Zhang et al., 2020c) is relevant method, but it uses greedy matching instead of OT, To summarize, OT and WMD have been used in many NLP tasks. It is important to understand the underlying mechanism of WMD for further advancements in this field.
Re-evaluation of Existing Methods. Back in 2009, Armstrong et al. (2009) found that, although many studies have claimed statistically significant improvements against the baselines, most have employed excessively weak baselines, and the performance did not improve from the classical baselines in the information retrieval domain. Dacrema et al. (2019) recently found that many of the deep learning- based recommender systems are extremely difficult to reproduce, and for the methods whose results authors could reproduce, the performance was not as high as people had believed, and the deep approaches were actually comparable to classical baselines with an appropriate hyperparameter tuning. Their paper has had a large impact on the community and was awarded thr best paper prize at RecSys 2019. Similar observations have also been made in sentence embeddings (Arora et al., 2017; Shen et al., 2018), session- based recommendations (Ludewig et al., 2019), and graph neural networks (Errica et al., 2020) as well. In general, science communication suffers from publication and confirmation biases. The importance of reproducing existing experiments by third-party groups has been widely recognized in science (Lin, 2018; Sculley et al., 2018; Munafò et al., 2017; Collins & Tabak, 2014; Goodman et al., 2016).
3 BACKGROUNDS
3.1 PROBLEM FORMULATION
In this paper, we consider document classification tasks. Each document is represented by a bag-of- word vector æ E RR"', where m is the number of unique words in the dataset. The i-th component of æ represents the number of occurrences of the i-th word in the document. We focus on the kNN classification following the original paper. The kNN classification gathers l samples of the smallest distances (with respect to certain distance) a test sample from the training dataset and classifies the sample to the majority class of the gathered labels. The design of the distance function is crucial for the performance of kNN classification.
3.2 WORD MOVER'S DISTANCE (WMD)
WMD provides an effective distance function utilizing pre-trained word embeddings. Let z; be the embedding of the i-th word. To utilize OT, WMD first regards a document as discrete probabilistic distribution of words by normalizing the of-d vector:
nui (x) = x >> Di.
(1)
3

---

Under review as a conference paper at ICLR 2022
Table I: Dataset statistics.
bbesport
twitter
recipe
ohsumed
classic
reuters
amazon
20news
Number of documents
737
3108
4370
9152
7093
7674
8000
18821
Number of training documents
517
2176
3059
3999
4965
5485
5600
11293
Number of test documents
220
932
1311
5153
2128
2189
2400
7528
Size vocahulary
13243
5708
31789
24277
22425
42063
29671
Unique words in document
116.5
9.9
48.3
60.2
38.7
36,0
44.6
69.3
Number of classes Split type
5
3
15
10
4
8
4
20
five-fold
live-fold
five-fold
one-fold
five-fold
one-fold
live-fold
one-fold
Duplicate pairs
15
976
1873
2588
143
159
Duplicate sumples
30
474
66
3116
600
197
285
88
WMD defines the cost matrix C' Rm x th the distance of the embeddings, i.e., C.j ||
2y112
z
The distance between the two documents æ and æ' is the optimal value of the following problem:
minimize PER m
Σ
Ciy
(2)
ij
S.t.
P. 2 P1- nLI 11 ("")
where PT denotes the transpose of P. E R.T is the vector of ones. Intuitively, P. represents the amount of word i that is transported to word j. WMD is defined as the minimum total distance to convert one document to another document. Let OT x', C) E IR be the optimal value of eq. (2).
3.3 EXPERIMENTAL SETUPS
Datasets. We use the same datasets (Greene & Cunningham, 2006; Sanders, 2011; 1; Joachims, 1998; Sebastiani, 2002; Lang, 1995) in the original paper (Kusner al., 2015) and use the same train/test splits as in the original paper. Three of the eight datasets have the standard train/test splits (e.g.. based on timestamps), and the other datasets do not. Thus, the original paper used five random splits for such datasets. We refer to the former type as one-fold datasets and the latter as five-fold datasets. Table shows the statistics. Here, we point out the first misleading point.
Mislcading Point Many duplicate samples exist in the datasets.
The last two rows in Table report the numbers of duplicate samples. Some of these samples cross the train/test splits, and some of them have different labels despite having the same contents. This causes problems in the evaluations. If the pairs have different labels, it is impossible to classify both of them correctly. If the pairs have the same label, kNN classifier places more emphasis on this class for no reason. We report this issue in more detail in Appendix A.
The datasets released by the WMD paper have been used many studies (Huang et al., 2016; Yurochkin et al., 2019; Le et al., 2019; Werner & Laber, 2020; Wang et al., 2020b; Wu et al., 2018; Skianis al., 2020b; Mollaysa et al., 2017; Gupta et al., 2020; Skianis al., 2020a) with the same protocol. We suspect that many readers and authors were unaware of the duplicate samples, which might have led to a misleading analysis. We release the indices of duplicate documents and a preprocessing script remove duplicate samples for the following studies. We believe that sharing this fact within the community is considerably important for aiding in a solid evaluation and analysis.
In the following, we first use the same dataset as the WMD paper to highlight the essential differences with the original evaluation. We then evaluate using clean datasets to further corroborate the findings.
Embeddings. We use the same word embeddings as in the original paper (Kusner et al., 2015). Namely, we use the 300-dimentional word2vec embeddings trained on the Google News corpus. We found the second misleading point here.
Misleading Point 2
The official code of 2MD normalized the embeddings by the L2 norm, al- though this was not explicitly stated in the paper.
The hint of word normalization is not in the main logic but only in the preprocessed binary file in the WMD's repository. We accidentally found this when we were debugging the code. Note that the Word Rotator's 's Distance (Yokoi et al., 2020) proposed to use the angles between word embeddings
Pttpps: pistps://gu / www.tthw....o.eeeeeeeeeeeeeeeete http:/.co//uusee//eeeeee wmd
4

---

Under review as a conference paper at ICLR 2022
70
4 better
KNN classificaiin
44.1
44.5
40
40.3
87.8
3..020.929.6
29.1
25.926.8
TF-IDF
TF-IDF
TF-IDF
TF-IDF
BOW
WMD
BOW
WMD
BOW
WMD
10.4
BOW
WMD
10-
3.9
4.1
5.7 5.5 4.0
8.0
bbcsport
twitter
recipe
ohsumed
classic
reuters
amazon
20news
Figure 3: KNN classification errors in our re-evaluation. Lower is better. The shaded bars are the performance without normalization. WMD is comparable to classical baselines with normalization.
for the cost matrix of WMD, but in fact, the original WMD already used angles for the cost matrix. We suspect that most readers missed this point. In this paper, we follow the original evaluation and normalize the embeddings using the L2 norm.
Preprocessing. For WMD, we use the same preprocessing as in the original paper (Kusner et al., 2015), whereas for BOW and TF-ID, WMD discards certain words because the word embeddings do not contain all words. the original study, the authors discard out-of-vocabulary words for WMD but maintain them for BOW and TF-IDF. In this paper, we discard out-of-vocabulary words for BOW and TF-IDF as well and use the same vocabulary for all of WMD, BOW, and TF-IDF. This setting slightly advantageous for WMD. We show that WMD is comparable to BOW and TF-IDF even under this setting. We include the results with out-of-vocabulary words the end of Section for completeness.
different preprocessing to clearly contrast the results.
Evaluation Protocol. WMD, BOW, and TF-IDF all have only one hyperparameter, i.c., size k of the neighborhood kNN classification. We split the training set into an 80/20 train/validation set uniformly and randomly and select the neighborhood size from {1, ... 19) using the validation data. During the process of our re-evaluations, we found that the kNN classifiers were much less capable than we previously thought and that kNN classification may underestimate the performances of distance-basse trast our results with the original evaluation. This is justified because only use kNN classification for all methods. However, this fact can be a misleading point other classifiers are used for other methods, in (Wu et al., 2018; Skianis al., 2020b; Mollaysa al., 2017; Gupta al., 2020). We report this issue in more detail Appendix B.
methods. Nevertheless, we adopt KNN evaluations the main part to clearly con-
Environment. We use server cluster compute WMD. Each node has two 2.4GHz Intel Xeon Gold 6148 CPUs. We use a Linux server with Intel Xeon E7-4830 v4 CPUs to evaluate the performances.
4 NORMALIZATION IS CRUCIAL
Importance of Normalization. In the original paper, raw BOW and TF-IDF vectors are used for the nearest neighbor classification. However, this is problematic because the length of these vectors varies based on the length of the documents. Even two documents share the same topic, the BOW vectors distant if their lengths differ. We need to normalize these vectors effectively use them in the nearest neighbor classification.
Misleading Point The original evaluation did normalize the BOW and TF-IDF vectors.
To make direct comparisons to WMD, we employ LI normalization (Eq. (1)) and the LI distance for BOW and TF-IDF vectors. i.e., dRowLII. (xx, x') [TI. nhr (=,,(x))) (x') With this normalization. BOW is special case of WMD that does not use the underlying geometry. Specifically, let Crumit be the cost matrix of WMD when we use one-hot vectors as word embeddings, i.e., Cunif if and C 2 i # j. Then, Proposition 1. deowLin (æ, x²) OT(ar, x', Cuun

---

Under review as a conference paper at ICLR 2022
Table 2: kNN classification errors. Lower is better. Here, (x/y) uses as the normalization and y as the metric. The last column reports the average relative performance to the normalized BOW. These values correspond to Figure 4 in the original paper, but we use BOW (LI/LI) as the base performances, while the original paper used BOW (None/L2) as the base performances. Figure 4 in (Yurochkin et al., 2019) also reports the relative performances, but uses BOW (L1/L22) as the base performances. The standard deviations are reported for five-fold datasets. The first three rows are the same as Figure 3. For BOW and TF-IDE, a cell is highlighted with bold if the mean score is better than that of WMD. For WMD, cell is highlighted with bold if the mean score is better than those of both BOW and TF-IDF. The fourth row reports the performances with WMD with TF-IDF weighting. The following rows report the performance with different normalization and metrics.
bhesport
twitter
recipe
ohsumed
classic
reuters
amazon
20news
rel.
BOW (LILI)
30.0 1.1
43.4 0.8
44.1
0.5
10.4 0.5
29.1
1,000
TF-IDF (LI/L)
288 + 1.1
28,9
1 0,8
40.1 1 0.7
37.8
3,3 1 0.4
5,5
8.0
1: 0.3
25.9
0.861
WMD
1.2
29.6
1.5
42.9 + 0.8
44.5
2,9 0,4
4.0
7.4
26.8
0.917
WMD-TF-IDF
0.9
28.3 2.3
39.9 1.1
39.7
2.7
4.0
6.6 0.2
24.1
0.804
BOW (None/L2) Kooee aaal C
19.4 3.0
34,2
60.0 2.3
61.6
0,90
11.8
28.2
= 1.0
57.7
3,024
BOW (Nome/1.1)
25.4 1.5
32.7 + 1.6
65.8 + 2.5
69.3
52.1 0.5
14.2
31.4
+ 1.2
73.9
3,931
(None/L22) Kreaer on19)
24.5
38.2
65.0 1,9
65.3
41.2
3.2
3.867
TF-IDF (None/LI)
30.6 1.3
37.8 4.8
70.3 + 1.3
70.6
$2.6 4: 0.2
29.1
41.5 - 4.9
74.6
4,602
BOW (L1/L22) (L./L.2)Vooxiiiootta (2019)
37.0 3.
50.8 : 1.1
56.7
1.5
12.3
35.7 1.3
46.5
2,253
BOW (L2/LI)
1.5
33.3
61.1
65.7
51.1
16.2
32.2 1.3
77.6
3,622
Weree BOW (L2//22)waalk Koctal (2011)
0.7
0..0
46.1 0.6
46.2
0.7
13.1 0.5
33.2
1.254
TE-IDE (L.1/.2)
25.5 11.2
35.7 +: 1.4
54.2
61.4
4.2
24.7
41.9
2.0
45.6
3.226
TF-IF (L2/LI)
7.2
33.4 1.7
64.9
69.7
52.0
19.5
40.8
6.6
78.3
4.245
TF-IDP (L2/22) aaa (209))
al (2099)
0.7
29.8
+ 1.5
43.7 +
1.2
38.4
5.2
10.5
11.1 0.9
31.6
1,145
The proof is in Appendix E. This proposition shows that the difference in the performances between WMD and L1/L1 BOW indicates the benefit of the underlying geometry.
Figure 3 shows the classification errors with normalization. First, and TF-IDF drastically decrease. Even BOW performs better than WMD in bbesport and ohsumed. TF-IDF outperforms WMD in five out of eight datasets. Even in the other datasets where WMD outperforms the baselines, the improvements are far less significant than what was reported in the original evaluation. We can also observe that TF-IDF always performs better than BOW in contrast to the original evaluation. These results make more sense than what was reported in the WMD paper, where BOW outperformed TF-IDE
that the errors of BOW
Comparison with other Normalization. Although normalized BOW and TF-IDF have been em- ployed in other studies (Yurochkin et al., 2019; Li et al., 2019; Werner & Laber, 2020; Wrzalik Krechel, 2019), it was reported that normalized BOW is still far worse than WMD, which is incom- patible with our observations above. We found out that this occurred because of the normalization methods and metrics used to compare the vectors. For example, Yurochkin et al. (2019) used LI normalization and the L2 metric for BOW, i.e., | (x) - nLI(x')]l and L2 normalization and the L2 metric for TF-ID,, i.e., [ 1.2/1.2 scheme corresponds to the cosine similarity. We investigate the performance with different normalization and metrics using the same protocol as in the previous experiments. Table shows the classification errors. First, it is easy to see in the fifth through eighth rows that the performances degrade without normalization. In addition, even with normalization, the performances are still poor if the normalization and metric use different norms. Although the L2/L2 scheme is better than these schemes, the L1/LI scheme is the best for all datasets. This result is natural if we adopt the stance that a document is distribution of words, and based on the analogy between the L1/L1 BOW and WMD, i... Proposition 1. To summarize, the normalization method significantly affects the performance. BOW L./L_1 corresponds to "WMD without OT"" (Proposition 1), and BOW None/1.1 corresponds "BOW LI/LI without normalization". The performances of these methods are
7L2((x))l 22, where n=2(z)) = x/||=|12 Note that the
3.931 (BOW None/L.1) introducing nommalzaaiion 1.000 (BOW L1/L1) introducing OT + 0.917 (WMD)
This means that WMD owes its performance improvements from the naive method (i.e., BOW None/LI) normalization (by factor of 3.9) rather than the OT formulation (by only a factor of 1.09). This "ablation study" indicates that LI normalization is the most significant factor of improvement in WMD. We stress that the improvements brought about by Ll normalization are obtained almost for
6

---

Under review as a conference paper at ICLR 2022
Table 3: kNN classification errors with clean data. Lower is better. The same notations in Table 2.
Iibesport
twitter
recipe
ohsumed
classic
reuters
amazon
20news
BOW (.ILI)
3.7 + 1.0
30.6 + 1.1
42.9 0.6
39.7
4.2 + 0.5
5.5
10.6 + 0.6
29.2
1,000
TF-DF (LILI)
233 1.4
30.2
+ 0.7
40.0 = 1.1
33.4
3.5 0 0.2
5.9
8.0 0.6
25.9
0.866
WMD
5.5
30.6
12
42.9
40.6
344 0.6
1
26.9
0,952
WMD IDF
1.1
28.8 1 1.6
40.2 1 0.9
35.7
2.8 1 0.3
4.3
6.6 0.3
24.2
0.848
Table 4: KNN classification errors with all words and the original datasets. Lower is better. The last column reports the average relative performance to the normalized BOW (the first row in Table 2).
bbesport
twitter
ohsumed
classic
reuters
amazon
20news
rel.
BOW (LI/LI)
3.0 = 0.8
29.5 + 0.7
46.0
3.9 1: 0.4
6.1
12.3
0.5
32.1
1.015
(LI/L.I)
29.4 0.9
3.1
7.9
0.3
0.877
Table 5: KNN classification errors with all words and clean data. Lower is better. The last column reports the average relative performance to the normalized BOW (the first row in Table 3).
bbesport
twitter
ohsumed
classic
reuters
amazon
20news
rel.
BOW (LILI)
2.7 0.6
31.0 2.0
41.0
0.1
6.3
0.3
32.1
1.022
TF-IDF (LI/L)
088
30.3 1.5
3.4
6.4
8.1
0.2
24.8
0.849
free, whereas the improvements by WMD are at the price of substantial computational costs. We should also point out that many papers have not clarified the normalization scheme. Because the normalization method and metrics used to compare the vectors significantly affect the performance, recommend clarifying them in the experimental setups.
To better illustrate the benefit of WMD, we also use TF-IDF weighting for the marginal measures of WMD. Specifically, let Byar TRd denote TF-IDF vector. We n4,1 (aanar) instead of n4,1 (ar) in the marginal constraints in Eq. (2). The TF-IDF weighting makes WMD as robust to noise as TF-IDF. The fourth row in Table shows that WMD with TF-IDF weighting performs the best, with approximately a six percent improvement from the normalized TF-IDF, which corresponds to the WMD-TF-IDF with the uniform distance matrix Cuuif, Investigating the (BOW, WMD) and (TF-IDF, WMD-TF-IDF) pairs illustrates the benefit of the optimal transport formulation. We can observe six to eight percent improvements in the optimal transport formulation from the naive baselines. This is in contrast to the sixly percent improvement claimed in the original study.
Evaluation on Clean Data. We evaluate the methods using clean datasets without duplicate samples. We adopt the same protocol as in the previous experiments except for the removal of duplicate documents. Table reports the classification errors. Although the tendency is the same as that in the previous experiments, the differences between (BOW, WMD) and (TF-IDF, WMD-TF-IDF) become even narrower. Namely, an approximately five percent improvement in WMD and two percent improvement in WMD-TF-IDD are found. The results for other normalization and metrics are reported in Table 7 in the appendix.
Evaluation with Out of Vocabulary Words. We had hypothesized that the two to eight percent improvements of WMD were due to the unnecessarily discarded vocabularies of BOW, which made the evaluations slightly advantageous to WMD. We evaluate BOW and TF-IDF, including words not in the word2vec vocabulary. We use all but the recipe dataset because the raw texts of the recipe dataset have not been released by the authors. We include stopwords for the Twitter dataset and remove them for the other datasets following the original paper. Tables 4 and 5 report the classification errors. Against expectations, these results show that the use of all words does not improve the performance. We hypothesize that this is because the word2vec vocabulary implicitly helps the classification by removing noisy words.
Summary. We should emphasize that we have not concluded that the improvements brought by WMD are spurious. Based on our careful evaluations, we conclude that the two to eight percent improvements from the naive baselines reported in Tables 2 and are genuine. These improvements are less sensational than those reported in the original paper, i.e., sixty percent improvement. However, we believe that our results indicate the true performance of WMD. These results indicate that if the speed is important, WMD may not be worth trying, whereas if the performance is crucial at any cost, WMD may be worthwhile candidate over L./L. BOW.
7

---

Under review as a conference paper at ICLR 2022
hhraport 3dm
beitier 3dim
rec pecppe 3dmm
G2
chsumed, 5:m
1a routers 5dim
clasic 5dim
amazon 5dim
20news 5mm
33
Jalance
Dolance
Ditannc
Dalaroe
Figure 4: Histograms of distances between matched word embeddings. (Top) 300-dimensional embeddings. (Bottom) 5-dimensional embeddings.
WMD RESEMBLES BOW IN HIGH DIMENSIONAL SPACES
In this section, we experimentally show that not only the performance of WMD but also the distance values of WMD themselves resemble those of LI/LI BOW.
Travel Distance Distribution is Two-modal in High Dimensional Spaces. We had assumed that the distribution of distances of matched word embeddings in WMD was a Gaussian-like one modal distribution. However, against expectations, we found that the distribution was actually two-modal in high dimensional spaces.
The top panels in Figure 4 show the histograms for matched words in nearest neighbor document pairs. The x-axis represents the distances of matched words, and the y-axis represents the frequency. All of the histograms have acute peaks at x O, where the source and target words exactly match. Other pairs of matched words are at x 1 and are approximately equally distant. This occurs intuitively because most pairs of embeddings are almost orthogonal in high dimensional spaces.
To contrast the results with low dimensional cases, we project the 300-dimensional word2vec to 5-dimensional space using principal component analysis and compute the same histograms using these low dimensional embeddings. Bottom panels in Figure 4 show the histograms. contrast to the high dimensional cases, these histograms are almost modal. These results indicate that the two modalities are a characteristic phenomenon in high dimensional spaces.
WMD resembles L1/L1 BOW in High Dimensional Spaces. The previous experiments show that the travel distance distribution two modal (zero or around one) in high dimensional spaces. In extreme case, if the distance is exactly zero one, Proposition shows that WMD coincides with L BOW. If not exact, we experimentally show that the distance values of WMD themselves resemble those of L1/LI BOW.
Figure 5 shows correlations between WMD and LI/LI BOW distances and reports the Pearson's 's correlation coefficients p. WMD and LI/LI BOW surprisingly similar to each other. To contrast the results with low dimensional cases, we also report the scatter plots using 5-dimensional embed- dings the bottom of Figure In contrast to the high dimensional cases, these scatter plots show that WMD in low dimensional spaces is not similar to L./L1 BOW. These results indicate that the similarity to L.1/1.1 BOW is characteristic phenomenon high dimensional spaces.
For example, the distance between "Obama" and "President" is 1.174, and the distance between "Obama" and "band" is 1.342 in 300-dimensional word2vec. The distance between "speaks" and "greets" is 0.978, and the distance between "speaks" and "gave" is 1.309. Although "Obama" and "President" seem much more semantically similar than "Obama" and "band", the distances are not much different in high dimensional spaces. In other words, WMD does not identify "Obama" with "President" " in high dimensional spaces. A simple calculation shows that
2WMD("Obamm) greets", "band greets")) = 1.342 0
2WMD("Obama greets", "President speaks") 1.174 + 0.978, BOW("Obama greets", "band greets") =
BOW("Obama greets", "President speaks") = 2.
8

---

Under review as a conference paper at ICLR 2022
bocsport p 0.950
twitter
redpe
ohsumed
0.886
e00.556
p 00882
1.0
1.0
5.4
0.4
64-
0.5
53
200
12
2.0
53
13
20
45
3.5
classic
reuters
amazon
1.4
20naws
0.9.979
0.840
p
122
1.-
0.4
0.5
0.
60W (LI111
B0W (LM1)1
BOW (LA1]1
BOW (LMLD
bocspoott Sdim
[witter 5dim p=03991
recipe. Sdim
66
ahsumed. 5dim
p 0.482
p p-0.611
p
03
022
62
BOW (L111
BOW (12111
BOW (LLRI
BOW (LYLL
amazon 5dim
08
20news
0.299
055
UNN
80W 03831
BOW (1333
D0w (U31))
Figure 5: Scatter plot of WMD and LI/L1 BOW. (Top) 300-dimensional embeddings. WMD is mostly determined by LI/L1 BOW. (Bottom) 5-dimensional embeddings.
This "almost equally distant" property may not be expected the -wo-dimensional illustration (Figure 1). While such an illustration is helpful for understanding the mechanism of WMD, it does not reflect the high dimensional nature word embeddings. The characteristics high dimensionality should also be kept in mind to understand the behavior of WMD more precisely.
should be noted that 5-dimensional WMD performs worse than 300-dimensional WMD because 5-dimensional WMD loses much information the word geometry. On the one hand, by increasing the number of dimensions, the word embeddings become more discriminative, and the performance of WMD increases. On the other hand, by increasing the number of dimensions, the word embeddings become orthogonal, and WMD approaches LI/L1 BOW, i.e., a special case of WMD that completely discriminates each word from the others.
CONCLUSION
In this paper, we pointed out that the major improvement in WMD against classical baselines is not from the inherent feature of WMD but mainly from the normalization. We re-evaluated the performance WMD and classical baselines and found that classical baselines are competitive with WMD if normalize the vectors. We also found that WMD resembled BOW much more than we had thought in two-dimensional illustrations owing to the high dimensionality of the word embeddings. In the process of our re-evaluation, found several confusing aspects in the original evaluations of the original paper on WMD. We pointed them out in this paper to help the following researchers conduct solid evaluations.

---

Under review as a conference paper at ICLR 2022
REFERENCES
David Alvarez-Melis, Tommi S. Jaakkola, and Stefanie Jegelka. Structured optimal transport. In Proceedings of the 21 International Conference on Artificial Intelligence and Statistics, AISTATS, volume 84 of Proceedings of Machine Learning Research, pp. 1771-1780. PMLR, 2018.
Martín Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In Proceedings of the 34th International Conference on Machine Learning. ICMI., pp. 214-223, 2017.
Timothy G. Armstrong, Alistair Moffat, William Webber, and Justin Zobel. Improvements that don't add up: ad-hoc retrieval results since 1998. In Proceedings of the 18th ACM Conference on Information and Knowledge Management, CIKM, pp. 601-610. ACM, 2009.
Sanjeev Arora, Yingyu Liang, and Tengyu Ma. A simple but tough-to-best baseline for sentence embeddings. In 5th International Conference on Learning Representations, ICLR. OpenReview.net, 2017.
Arturs Backurs, Yihe Dong, Piotr Indyk, Ilya P. Razenshteyn, and Tal Wagner. Scalable nearest neighbor search for optimal transport. In Proceedings of the 37th International Conference on Machine Learning, JCML, pp. 497-506, 2020.
Liqun Chen, Yizhe Zhang, Ruiyi Zhang, Chenyang Tao, Zhe Gan, Haichao Zhang, Bai Li, Dinghan Shen, Changyou Chen, and Lawrence Carin. Improving sequence-to- se-quuecc learning via optimal transport. 7th International Conference on Learning Representations, ICLR. OpenReview.net, 2019.
Liqun Chen, Ke Bai, Chenyang Tao, Yizhe Zhang, Guoyin Wang, Wenlin Wang, Ricardo Henao, and Lawrence Carin. Sequence generation with trammmll-rraspot-ennaanceee reinforcement learning. In Proceedings of the 34th AAAI Conference Artificial Intelligence, AAAI, pp. 7512-7520. AAAI
Press, 2020a.
Yu Chen, Lingfei Wu, and Mohammed Zaki. Reinforcement learning based graph-to-sequence model for natural question generation. In 8th International Conference on Learning Representa- tions, ICLR. OpenReview.net, 2020b.
Elizabeth Clark, Asli Celikyilmaz, and Noah A. Smith. Sentence mover's similarity: Automatic evaluation for multi-sentence texts. Proceedings of the 57th Conference of the Association for Computational Linguistics, ACL, pp.
Association for Computational Linguistics, 2019,
Francis S Collins and Lawrence A Tabak. Policy: NIH plans to enhance reproducibility. Nature News, 505(7485):612, 2014.
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. In Advances in Neural Information Processing Systems 26: Annual Conference Neural Information Processing Systems 2013, NeurIPS, pp. 2290-2300, 2013.
Maurizio Ferrari Dacrema, Paolo Cremonesi, and Dietmar Jannach. Are we really making much progress? A worrying analysis of recent neural recommendation approaches. In Proceedings of the 13th ACM Conference on Recommender Systems, RecSys, pp. 101-109. ACM, 2019.
Fernando De Goes, Katherine Breeden, Victor Ostromoukhov, and Mathieu Desbrun. Blue noise through optimal transport. ACM Transactions on Graphics (TOG), 31(6):1-11, 2012.
Michel Deudon. Learning semantic similarity in continuous space. In Advances Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS, pp. 994-1005, 2018
Sofien Dhouib, levgen Redko, Tanguy Kerdoncuff, Rémi Emonct, and Mare Sebban. A swiss army knife for minimax optimal transport. In Proceedings of the 37th International Conference Machine Learning, ICML, pp. 2504-2513, 2020.
Yihe Dong, Yu Gao, Richard Peng, Ilya Razenshteyn, and Saurabh Sawlani. A study performance of optimal transport. arXiv, abs/2005.01 182, 2020.
10

---

Under review as a conference paper at ICLR 2022
Zi-Yi Dou and Graham Neubig. Word alignment by fine-tuning embeddings on parallel corpora. In Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume, EACL, pp. 2112-21222 Association for Computational Linguisties, 2021.
Richard Mansfield Dudley. The speed of mean glivenko-cantelli convergence. The Annals of Mathematical Statistics, 40(1):40-50 1969.
Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. A fair comparison of graph neural networks for graph classification. 8th International Conference on Learning Representations, ICLR. OeenReview.net, 2020.
Steven Evans and Frederick A Matsen. The phylogenetic kantorovich-rubinseenn metric for environmental sequence samples. Journal of the Royal Statisticul Society: Series B (Statistical Methodology), 74(3):569-583 2012.
Charlie Frogner, Farzaneh Mirzazadeh, and Justin Solomon. Learning embeddings into entropic wasserstein spaces. 7th International Conference on Learning Representations, ICLR. OpenRe- view.net, 2019.
Yang Gao, Wei Zhao, and Steffen Eger. SUPERT: towards new frontiers in unsupervised evaluation metrics for multi-document summarization. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, ACI. pp. 1347-1354. Association for Computational Linguistics, 2020.
Aude Genevay, Marco Cuturi, Gabriel Peyré, and Francis R. Bach. Stochastic optimization for large-scale optimal transport. In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, NeurlPS, pp. 3432-3440, 2016.
Aude Genevay, Gabriel Peyré, and Marco Cuturi. Learning generative models with sinkhorn di- vergences. Proceedings of the 23rd International Conference on Artificial Intelligence and Statisties, AISTATS, volume 84 of Proceedings of Machine Learning Research, pp. 1608-1617. PMLR, 2018.
Aude Genevay, Lénaic Chizat, Francis R. Bach, Marco Cuturi, and Gabriel Peyré. Sample complexity of sinkhorn divergences. Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, AISTATS, volume 89 of Proceedings of Machine Learning Research, pp. 1574-1583. PMLR, 2019.
Steven N Goodman, Daniele Fanelli, and John PA Ioannidis. What does research reproducibility mean? Science translational medicine, 8(341):34lps12-344
2016
Edouard Grave, Armand Joulin, and Quentin Berthet. Unsupervised alignment of embeddings with wasserstein procrustes. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, AISTATS, volume 89 of Proceedings of Machine Learning Research, pp. 1880-1890. PMLR, 2019.
Derek Greene and Padraig Cunningham. Practical solutions to the problem of diagonal dominance in kernel document clustering. In Proceedings of the 23rd International Conference on Machine Learning, ICML, pp. 377-384, 2006.
Vivek Gupta, Ankit Saw, Pegah Nokhiz, Praneeth Netrapalli, Piyush Rai, and Partha P. Talukdar. P- SIF: document embeddings using partition averaging. In Proceedings of the 34th AAAI Conference on Artificial Intelligence, AAAI, pp. 7863-7870. AAAI Press, 2020.
Gao Huang, Chuan Guo, Matt J. Kusner, Yu Sun, Fei Sha, and Kilian Q. Weinberger. Supervised word mover's distance. In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, NeurlPS, pp. 4862-4870, 2016.
Minhui Huang, Shiqian Ma. and Lifeng Lai. A riemannian block coordinate descent method for computing the projection robust wasserstein distance. In Proceedings of the 38th International Conference Machine Learning, ICML,, volume 139, pp. 1446-4455 PMLR, 2021.
11

---

Under review as a conference paper at ICLR 2022
Thorsten Joachims. Text categorization with support vector machines: Learning with many relevant features. In Proceedings of the 10th European Conference on Machine Learning, ECML, volume 1398 of Lecture Notes in Computer Science, pp. 137-142. Springer, 1998.
Mert Kilickaya, Aykut Erdem, Nazli Ikizler-Cinbile and Erkut Erdem. Re-evaluating automatic metrics for image captioning. In Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics, EACL. pp. 199-209. Association for Computational Linguistics, 2017.
Hayato Kobayashi, Masaki Noguchi, and Taichi Yatsuka. Summarization based on embedding distributions. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, EMNLP, pp. 1984-1989. The Association for Computational Linguistics, 2015.
Soheil Kolouri, Yang Zou, and Gustavo K. Rohde. Sliced wasserstein kernels for probability distributions. In 2016 IEEE Conference Computer Vision and Putlern Recognition, CVPR, pp. 5258 5268-526,,770 2016.
Soheil Kolouri, Kimia Nadjahi, Umut Simsekli, Roland Badeau, and Gustavo K. Rohde. Generalized sliced wasserstein distances. In Advances Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS, pp. 261-272, 2019.
Sachin Kumar, Soumen Chakrabarti, and Shourya Roy. Earth mover's 's distance pooling over siamese Istms for automatic short answer grading. In Proceedings of the 26th International Joint Conference on Artificial Intelligence, IJCAI, pp. 2046-2052. ijeai.org 2017.
Matt Kusner, Yu Sun, Nicholas I. Kolkin, and Kilian Q. Weinberger. From word embeddings to document distances. In Proceedings of the 32nd International Conference on Machine Learning, ICML, pp. 957-966, 2015.
Ken Lang. News Learning to filter netnews. Proceedings of the 12th International Conference on Machine Learning, ICML, pp. 331-339, 1995.
Tam Le, Makoto Yamada, Kenji Fukumizu, and Marco Cuturi. Tree-sliced variants of wasserstein distances, In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS, pp. 12283-12294, 2019.
Qi Lei, Lingfei Wu, Pin-Yu Chen, Alex Dimakis, Inderjit Dhillon, and Michael J. Witbrock. Discrete adversarial attacks and submodular optimization with applications to text classification. In Proceedings of Machine Learning and Systems 2019, MLSys, mlsys.org, 2019.
Changchun Li, Jihong Ouyang, and Ximing Li. Classifying extremely short texts by exploiting semantic centroids in word mover's distance space. In The World Wide Web Conference, WWW, pp. 939-949, ACM, 2019.
Jianqiao Li, Chunyuan Li. Guoyin Wang. Hao Fu, Yuh-Chen Lin, Liqun Chen, Yizhe Zhang, Chenyang Tao, Ruiyi Zhang, Wenlin Wang. Dinghan Shen, Qian Yang, and Lawrence Carin. Improving text generation with student-forcing optimal transport. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP, pp. Association for Computational Linguistics, 2020.
Jimmy Lin. The neural hype and comparisons against weak baselines. SIGIR Forum, 52(2):40-51, 2018.
Tianyi Lin, Chenyou Fan, Nhat Ho. Marco Cuturi, and Michael Jordan. Projection robust wasser- stein distance and riemannian optimization. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS, 2020.
Catherine Lozupone and Rob Knight. UniFrac: a new phylogenetic method for comparing microbial communities. Appl. Environ. Microbiol., 71(12))8228-8)) 0082288822558.. 2005.
Sidi Lu, Lantao Yu, Siyuan Feng, Yaoming Zhu, and Weinan Zhang. CoT: Cooperative training for generative modeling of discrete data. In Proceedings of the 36th International Conference on Machine Learning, ICMI., pp. 4164 2019.
12

---

Under review as a conference paper at ICLR 2022
Malte Ludewig, Noemi Mauro, Sara Latifi, and Dietmar Jannach. Performance comparison of neural and non-neural approaches to session- based recommendation. Proceedings of the 13th ACM Conference Recommender Systems, RecSys, pp. 462 462-466. ACM, 2019.
Paul Michel, Abhilasha Ravichander, and Shruti Rijhwani. Does the geometry of word embeddings help document classification? A case study on persistent homology- representations. In Proceedings of the 2nd Workshop on Representation Learning for NLP, Rep4NLP@ACI, pp- 235-240. Association for Computational Linguistics, 2017.
Amina Mollaysa, Pablo Strasser, and Alexandros Kalousis. Regularising non-linear models using feature indeiinformttion In Proceedings of the 34th International Conference on Machine Learning, ICML, pp. 2508-2517, 2017.
Marcus R Munafö, Brian A Nosek, Dorothy VM Bishop. Katherine S Button, Christopher D Chambers, Nathalie Percie Du Sert, Uri Simonsohn, Eric-Jan Wagenmakers, Jennifer J Ware, and John PA loannidis. manifesto for reproducible science. Nature human behaviour, 1(1):1-9, 2017.
Boris Muzellec and Mareo Cuturi. Generalizing point embeddings using the wasserstein space of elliptical distributions. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS, pp. 10258-10269, 2018.
Kangyu Ni, Xavier Bresson, Tony F. Chan, and Selim Esedoglu. Local histogram based segmentation using the wasserstein distance. International Journal of Computer Vision, 84(1):97-111 2009.
Giannis Nikolentzos, Polykarpos Meladianos, François Rousseau, Yannis Stavrakas, and Michalis Vazirgiannis. Multivariate gaussian document representation from word embeddings for text categorization. In Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics, EACI, pp. 450-455. Association for Computational Linguistics, 2017.
Giannis Nikolentzos, Antoine J.-P. Tixier, and Michalis Vazirgiannis. Message passing attention networks for document understanding. In Proceedings of the 34th AAAI Conference on Artificial Intelligence, AAAI, pp. 8544-8551. AAAI Press, 2020.
François-Pierre Paty and Marco Cuturi. Subspace robust wasserstein distances. In Proceedings of the 36th International Conference on Machine Learning, ICML, pp. 5072-5081, 2019.
Mathis Petrovich, Chao Liang, Ryoma Sato, Yanbin Liu, Yao-Hung Hubert Tsai, Linchao Zhu, Yi Yang, Ruslan Salakhutdinov, and Makoto Yamada. Feature robust optimal transport for high- dimensional data. arXiv, abs/2005. 12123, 2020.
Julien Rabin, Gabriel Peyré, Julie Delon, and Mare Bernot. Wasserstein barycenter and its application to texture mixing. In Proceedings of Scale Space und Variational Methods in Computer Vision, pp. 435 446, 2011.
Antoine Rolet, Marco Cuturi, and Gabriel Peyré. Fast dictionary learning with smoothed wasserstein loss. In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, AISTATS, pp. 630-638 2016.
Tim Salimans, Han Zhang, Alec Radford, and Dimitris N. Metaxas. Improving gans using optimal transport. In 6th International Conference on Learning Representations, ICLR, 2018.
Nick J Sanders. Sanders-twitter sentiment corpus. Sanders Analytics LLC, 242, 201
Filippo Santambrogio. Optimal transport for applied mathematicians, Birkhauser, 2015.
Ryoma Sato, Marco Cuturi. Makoto Yamada, and Hisashi Kashima. Fast and robust comparison of probability measures in heterogeneous spaces. arXiv, abs/2002.01615, 2020a.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Fast unbalanced optimal transport tree. In Advances Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS, 2020b.
13

---

Under review as a conference paper at ICLR 2022
Geoffrey Schiebinger, Jian Shu, Marcin Tabaka, Brian Cleary, Vidya Subramanian, Aryeh Solomon, Joshua Gould, Siyan Liu, Stacie Lin, Peter Berube, et al. Optimal- analysis of single-cell gene expression identifies developmental trajectories in reprogramming. Cell, 176(4):928-94) 2019.
D. Sculley, Jasper Snock. Alexander B. Wiltschko, and Ali Rahimi. Winner's curse? pace. progress, and empirical rigor. In 6th International Conference on Learning Representations, ICLR. OpenReview.net, 2018.
Fabrizio Sebastiani. Machine learning automated text categorization, ACM Comput. Surv., 34(1): 1-47, 2002.
Dinghan Shen, Guoyin Wang, Wenlin Wang, Martin Renqiang Min, Qinliang Su, Yizhe Zhang, Chunyuan Li, Ricardo Henao, and Lawrence Carin. Baseline needs more love: On simple word- embedding- based models and associated pooling mechanisms. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics, ACL, pp. 440-450. Association for Computational Linguistics, 2018.
Sidak Pal Singh, Andreas Hug, Aymeric Dieuleveut, and Martin Jaggi. Context mover's distance & barycenters: Optimal transport of contexts for building representations. In Proceedings of the 23rd International Conference Artificial Intelligence and Statistics, AISTATS, volume 108, pp. 3437-3449. PMLR, 2020.
Konstantinos Skianis, Fragkiskos D. Malliaros, Nikolaos Tziortziotis, and Michalis Vazirgiannis. Boosting tricks for word mover's s distance. In Artificial Neural Networks and Machine Learning, ICANN, pp. 761-772. Springer, 2020a.
Konstantinos Skianis, Giannis Nikolentzos, Stratis Limnios, and Michalis Vazirgiannis. Rep the set: Neural networks for learning set representations. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, AISTATS, volume 108 of Proceedings of Machine Learning Research, pp. 1410-1420. PMLR, 2020b.
Chi Sun, Hang Yan, Xipeng Qiu, and Xuanjing Huang. Gaussian word embedding with wasserstein distance loss. arXiv, http//88..00011 2018
Yuki Takezawa, Ryoma Sato, and Makoto Yamada. Supervised wesserssenn distance, In Proceedings of the 38th International Conference on Machine Learning, ICML, volume 139, pp. 10086-10095, 2021.
Martin Trapp, Marcin Skowron, and Dietmar Schabus. Retrieving compositional documents us- ing position-sensittee word mover's distance. In Proceedings of the ACM SIGIR International Conference on Theory of Information Retrieval, ICTIR. pp. 233-236 ACM, 2017.
Qingzhong Wang, Jia Wan, and Antoni B Chan. On diversity in image captioning: Metrics and methods. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020a.
Zihao Wang, Datong Zhou, Ming Yang, Yong Zhang, Chenglong Rao, and Hao Wu. Robust document distance with wasserstein-fisherrrao metric. In Proceedings of The 12th Asian Conference on Machine Learning, ACML, volume 129 of Proceedings of Machine Learning Research, pp. 721- 736. PMLR, 2020b.
Jonathan Weed, Francis Bach, al. Sharp asymptotic and finite-sample of convergence of empirical measures in wasserstein distance. Bernoulli, 22244)22600-2648 2019.
Matheus Werner and Eduardo Laber. Speeding up word mover's distance and its variants via properties distances between embeddings. In Proceedings of the 24th European Conference on Artificial Intelligence, ECAI, volume 325 of Frontiers in Artificial Intelligence and Applications, pp. 2204-2211 IOS Press, 2020.
Marco Wrzalik and Dirk Krechel. Balanced word clusters for interpretable document representation. In Second International Workshop on Machine Learning, WML@ICDAR, pp. 103-109. IEEE, 2019.
14

---

Under review as a conference paper at ICLR 2022
Lingfei Wu, Ian En-Hsu Yen, Kun Xu, Fangli Xu, Avinash Balakrishnan, Pin- Yu Chen, Pradeep Ravikumar, and Michael J. Witbrock. Word mover's s embedding: From word2vec to document embedding. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, EMNLP, pp. 4534-4534. Association for Computational Linguistics, 2018.
Hongteng Xu, Wenlin Wang, Wei Liu, and Lawrence Carin. Distilled wasserstein learning for word embedding and topic modeling. Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS, pp. 1723-17322 2018.
Sho Yokoi, Ryo Takahashi, Reina Akama, Jun Suzuki, and Kentaro Inui. Word rotator's ss distance. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP. pp.
Association for Computational Linguisties, 2020.
Mikhail Yurochkin, Sebastian Claici, Edward Chien, Farzaneh Mirzazadeh, and Justin M. Solomon. Hierarchical optimal transport for document representation. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS, pp. 1599-1609, 2019.
Meng Zhang, Yang Liu, Huan- Bo Luan, Maosong Sun, Tatsuya Izuha, and Jie Hao. Building earth mover's 's distance on bilingual word embeddings for machine translation. In Proceedings of the 30th AAAI Conference on Artificial Intelligence, AAAI, pp. 2870-2876. AAAI Press, 2016.
Meng Zhang, Yang Liu, Huanbo Luan, and Maosong Sun. Earth mover's 's distance minimization for unsupervised bilingual lexicon induction. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, EMNLP, pp. 1934-1945, Association for Computational Linguisties, 2017a
Meng Zhang, Haoruo Peng, Yang Liu, Huan-Bo Luan, and Maosong Sun. Bilingual lexicon induction from non-parallel data with minimal supervision. In Proceedings of the 31 AAAI Conference on Arlificial Intelligence, AAAI, pp. 3379-3385. AAAI Press, 2017b.
Ruiyi Zhang, Changyou Chen, Zhe Gan, Zheng Wen, Wenlin Wang, and Lawrence Carin. Nested- wasserstein self-imine seff-mitatiin learning for sequence generation. In Proceedings of the 23rd Interna- tional Conference Artificial Intelligence and Statistics, AISTATS, volume 108 of Proceedings of Machine Learning Research, pp. 422 433. PMLR, 2020a.
Ruiyi Zhang, Changyou Chen, Xinyuan Zhang, Ke Bai, and Lawrence Carin. Semantic matching via optimal partial transport. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: Findings, EMNLP, pp. 212.222. Association for Computational Linguisties, 2020b.
Tianyi Zhang, Varsha Kishore, Felix Wu, Kilian Q. Weinberger, and Yoav Artzi BERTScore: Evalu- ating text generation with BERT. In 8th International Conference on Learning Representations, ICLR. OpenReview.net, 2020c.
Wei Zhao, Maxime Peyrard, Fei Liu, Yang Gao, Christian M. Meyer, and Steffen Eger. Moverscore: Text generation evaluating with contextualized embeddings and earth mover distance. In Proceed- ings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, EMNLP-IJCNLP, pp. 563-578. Association for Computational Linguistics, 2019.
Wei Zhao, Goran Glavas, Maxime Peyrard, Yang Gao, Robert West, and Steffen Eger. On the limitations cross-lingual encoders as exposed by reference-free machine translation evaluation. In Proceedings of the 58th Anmual Meeting of the Association for Computational Linguistics, ACL, pp. 1656-1671 1671. Association for Computational Linguistics, 2020.
15

---

Under review as a conference paper at ICLR 2022
Table 6: Weighted KNN classification errors. Lower is better. The last column reports the average relative performance to the normalized BOW with the standard kNN (the first row in Table 2).
bbesport
twitter
recipe
ohsumed
classic
reulers
arazzon
20news
rel.
BOW (LI/LI/wKNN)
26.4 0.6
1.6
41,1 + 0.5
41.3
3,6
4.7
10.3 0.3
23.3
0.888
TF-DF ( LIWNN/
0.7
1,56
38,3
1.1
36.1
288
0.4
5.8
8.2 = 0.5
20.5
0.787
WMD (wKNN)
4.4
26.2
40.5
1.0
41.1
2.7
3.6
7.1 + 0.5
21.7
0.823
WMD-IF-IDF (WKNN)
3.2
15
37.7
37.0
2.4
4.0
6.3 0.4
19.6
0.743
A DUPLICATE DOCUMENTS
We point out that there are many duplicate samples in the datasets used in the original study. The last two rows in Table 2 report the numbers of duplicate samples. Specifically, "duplicate pair" reports the number of pairs (s, 1) such that and / are the same, and "duplicate samples" reports the number of samples s such that has at least one samples t with the same content. Some of these pairs cross the training and test splits, and some of them have different labels despite having the same contents. This causes problems in the evaluations. If the pairs have different labels, it is impossible to classify both of them correctly. If the pairs have the same label, a kNN classifier places more emphasis on this class for no reason. We found that duplication was caused by different reasons in different datasets. For example, the ohsumed dataset was originally a multi-labeled dataset, and the WMD paper duplicate samples for each label. We found that the original source dataset (Greene & Cunningham, 2006) of bbesport already contained duplicate samples, e.g., and athletics/ 200. txt. We hypothesis this was originated from the data collection process.
/ /22. txt
Although such duplication is not problem if we intend to measure the performances in noisy environments, the analysis could be misleading if we assume a clean environment. The datasets released by the WMD paper have been used in many studies (Huang et al., 2016; Yurochkin et al., 2019; Le et al., 2019; Werner & Laber, 2020; Wang et al., 2020b; Wu et al., 2018; Skianis et al., 2020b; Mollaysa et al., 2017; Gupta et al., 2020; Skianis al., 2020a) with the same protocol. We suspect that many readers and authors were unaware of this fact, which might have led to a misleading analysis. We release the indices of duplicate documents and a preprocessing script to remove duplicate samples for the following studies. We believe that sharing this fact within the community is considerably important for aiding in a solid evaluation and analysis.
B NEAREST NEIGHBOR CLASSIFICATION IS FAR FROM OPTIMAL
WMD is often used as a weak baseline in document classification. In this section, we point out that the poor performances observed in previous studies are not necessarily due to the problem found in the main part but rather due to the choices of classifiers. We found that many existing studies, including the original paper on WMD, used kNN classification for distance-based methods (Kusner et al., 2015; 5; Huang et al., 2016; Wang et al., 2020b). This is reasonable owing to its simplicity regardless of suboptimal performance, However, we found that KNN classification was much farther from optimal than we had thought and caused some improper observations. The most prominent issue appears in comparison with non-kNN classifiers. For example, WMD is used with a kNN classifier as baseline, and other classifiers are adopted for the proposed methods in (Wu et al., 2018; Skianis et al., 2020b; Mollaysa et al., 2017: Li et al., 2019; Gupta et al., 2020; Nikolentzos et al., 2020; 2017). The improvement observed by such evaluations may not be due to the superiority of the proposed methods against WMD, but due to the superiority of the classifier against the kNN classifier. To mitigate this problem, found that weighted kNN classifier (wkNN) with exponential weighting was a good choice for distance- samples and computes the distances {d,.- d4 } to these samples. then defines the weight for sample i exp( -d: d and takes the weighted majority vote, where is a hyperparameter. We can think of wkNN as continuous variant of KNN, which uses a step function as the weight function. As the crux of wkNN, the time and space complexities are the same as in KNN, and it involves no training procedures. Thus, we can easily replace a kNN system with a wkNN system.
methods. Specifically, wkNN first gathers k nearest neighbor
hhttp://mlg ued. www...dddeeeeeeeeeeeeeeeeeeeee ie/datasete /bbc. html
16

---

Under review as a conference paper at ICLR 2022
Table 7: kNN classification errors with clean data. Lower is better. The same notations in Table 2.
bbesport
twitter
recipe
ohsumed
classic
reuters
amazon
20news
rel.
ROW (IIII))
3.7
1.0
30.6 + 1.1
42.9 0.6
39.7
4.2 + 0.5
5.5
10.6
0.6
29.2
1,000
TF-IDF (LILI)
2,3
1.4
30.2 = 0,7
40.0 1.1
33.4
3,5 = 0.2
5.9
8.0 = 0.6
25,9
0.866
WMD
5.5
30.6 12
40.6
3,4 0.6
3.8
7.3 0.4
26,9
0.952
WMD IDF
4.1 1.5
28.8 1 1.6
40.2 0.9
35.7
2.8 0.3
4.3
6.6 0.3
24.2
0.848
BOW (None/L.2)
1.
34.2
1:21:00 0.6
59.1 = 0.9
60.7
36,9 111
11.7
28.9
1.1
58.0
3.227
ROW (Nonel1.1)
25.3
14.0
32,4
73.5
4.044
TF-IDF (None/1.2)
1.18+
0.6
65.6 1.0
62.8
41.1+111
28.3
43.4 +:4
59.8
4.032
TF-IFF (Nons/L1)
1.2
33.6 0.6
70.6 1.8
69.5
55.6 0.2
29.1
4 4.8
74.7
4.804
BOW (LI/22)
1.78
40.2 2.0
51.4
55.8
17.5
12.9
36.8
46.7
2.336
BOW (L2/L1)
1.
3.9
59,9 0.7
64.3
54.0
16.2
32.7
2.17
77.1
3.715
BOW (1.2/L2)
5.3
6.7
13.3
1.263
TF-IFF (L./112)
20.0
79.3 14
54.1 - 2.4
55.2
24.8+30
24.5
43.2++2.0 2.0
45.9
3.168
TF-IFF (L2/L))
28.7
33.5 1.0
-
65.7
55.
19,9
39.0
78.6
4.390
TF-IFF (L2(22)
1.
15
43.6=0.8
33.2
5.2
10.6
111 0.6
31.6
1.127
Table 8: kNN classification errors with dimensional embeddings. Lower is better. The first two rows are the same as Table 2 for reference.
bbesport
twitter
recipe
ohsumed
classic
reuters
amazon
20news
rel.
BOW (LILI)
3,9 = 1.1
30.0 1.1
4344 0.8
44.1
4.1 + 0.5
5.7
10.4 + 0,5
29.1
1.000
WMD
5.1 1.2
29.6
42. 0.8
44.5
2.9 0.4
4.0
7.4 = 0.5
26.8
0.917
WMD dim) 18.5
32.0 1.0
518 1.0
60.2
6.2
1 0.3
6.9
15.9 1 0.8
45.4
1,773
We conduct experiments to show the suboptimality of KNN. As the drawback of wkNN, it has two
hyperparameters i and y. We find that the of wkNN plays a similar role as the maximum ic of kNN in the hyperparameter tuning. Thus, fix k of wkNN to 19 and tune only in the hyperparameter tuning. Recall that the hyperparameter candidates were E {1..... ........ 19} for kNN in the previous 0.095, 0.1} (T) 20)
experiments and original paper. We select y from I f0.005, 0.010, in the hyperparameter tuning". The remaining settings are the same as the previous experiments. Table 6 shows the classification errors. We can see that wkNN performs much better than kNN. The benefit of wkNN (the first row in Table 6 versus the first row in Table 2) is more significant than the benefit of WMD (the third versus the first in Table 2). This indicates that if proposed method uses non-kNN classifiers, ten percent improvements from the KNN baselines may be due to classifiers, the proposed method. This also indicates that there significant room for improvement the classifiers before undergoing a design of better similarity measures.
might be acceptable if all baselines and the proposed method use kNN because the relative performances in Tables 2 and 6 do not change significantly. However, it would be better to use more capable classifiers because the results in a paper will cited as baseline records following papers, in which other classifiers may be employed. In fact, such comparisons have been carried out in (Wu al., 2018; Skianis et al., 2020b; Mollaysa et al., 2017: Gupta et al., 2020). Besides, practitioners may underestimate the performance of distance-based methods based on the reported results. We find wkNN is better choice than kNN because as fast as kNN yet much more effective.
C COMPARISON WITH OTHER NORMALIZATION WITH CLEAN DATA
Table 7 shows the kNN classification errors with clean data. The same tendency as Table 2 can be observed.
D PERFORMANCE OF Low DIMENSIONAL EMBEDDINGS
Table 8 shows the classification errors of WMD with the 5-dimensional embeddings used in Section 5. shows that WMD with the low dimensional embeddings performs worse than with the original 300- dimensional embeddings, although WMD performs differently from BOW with the low dimensional embeddings (Figure 5). In general, an exact match of words indicates a strong similarity. It is
"The magnitude of this range is determined by the empirical distances hetween samples. This arbitrary choice is slight drawback of wkNN. We will investigate how choose it automatically in future work.
17

---

Under review as a conference paper at ICLR 2022
reasonable that counting common words can perform better than relying too much the underlying geometry.
E PROOF OF PROPOSITION 1
We prove the analogy between LI/LI BOW and OT. Recall that dROWLII (z, x') = T (x) - TLLI (2)(("))ll
and
Cannf
0 (i=
2 (i)
Proof of Proposition 1. Without loss of generality, we assume that the marginals æ and x' are already L1 normalized, and Σ, and , hold. Let P mm be the optimal solution of (T x', Cunif). From the marginal constraints, P < min( æạ)) holds. If P: < min(x; æ!). there exists o and i: * such that Púj > 0 and p > from the marginal constraints. Then, let Q E Rmxm
P + min sy. Pk)
(s = -iiit- i)
P min(P) Pk))
(s ---i--= 1)
Qst
P min(P;
Pr Pk)
(s=kAt=> 1)
P + min( Pk)
(s=kAt=]) 5) (otherwise).
P
Then, Q satisfies the constraints of OT and
Cuni p
Σ Cunif Qst
Camil (P - -P + min P Phi))
ij (Pij - (Pi) miinnn min(P,). Pk))) CHail (Phs (Phs min(P, Pij. Pk)))) + kj (Pis Pi + min P.j.. Pk))
(4- Cunif) minnP:;; Pi))
0.
The first equation holds from the definition of Q, and the second equation holds because C = and Cynif Ch 2, and the last inequality holds because Chunif < and min P Pk.) > This contradicts with the optimality of P Therefore,
P = min(x; a!{)
holds. Therefore,
Σ Camif P
Σ 2(11 -diag( diag(1))s{PP)
8t
> P - Σ P
st
2 2 Σ
min( x., X'))
Σ x, + Σ x Σ min (c,, x3) Σ
min( (z,; xx,))
> (x. - min(x,, x()) + (a', - min(x, x()))
Σ x
18

---

Under review as a conference paper at ICLR 2022
F ADDITIONAL RELATED WORK
We review additional related work, which we could not place in the main text because of the page limit, First, it has already been known that OT behaves pathologically in high dimensional spaces, mainly owing to the sample complexity. Dudley (1969) showed that the sample complexity of OT grows exponentially with respect the number of dimensions. Weed et al. (2019) alleviated the bound using other senses of dimensionality, but the dependency is still exponential. Genevay et al. (2019) showed that the sample complexity of the Sinkhorn Divergences (Genevay al., 2018; Cuturi, 2013) matches that of MMD. The crucial difference between our work and theirs is that we shed light on more practical sides, whereas their interests were on the theoretical side. We believe that our analysis and explanation are insightful, especially for practitioners.
Secondly, high-dimensional problems have also been studied from computational aspects. Rabin et al. (2011) and Kolouri et al. (2016) proposed to project embeddings to random one-dimensional spaces to speedup computation because OT a one-dimensional space can be solved efficiently (Santambrogio, 2015). Paty & Cuturi (2019) and others (Kolouri et al., 2019; Dhouib al., 2020; Petrovich et al., 2020; Lin et al., 2020; Huang et al., 2021) proposed robust variants of OT with low dimensional projections. Specifically, their methods adopt the worst distance with respect candidate projections. Although we tried in early experiments several projection methods, including the principal component analysis as Section 5 and Appendix D, tree slicing (Le et al., 2019), and rank-based cost matrices instead of actual distance cost matrices (Sato et al., 2020a), we did not find performance improvements. However, exploring these approaches can be one of the promising future directions with the curse of dimensionality in mind.
19


Reviews:
[{"review_id": "ofB19yjOuRp", "reviewer": "Reviewer_M3dN", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "# Strengths\n\nThis paper identifies issues with the original paper proposing WMD and during the evaluation, it shows the gain mainly due to normalization instead of WMD. It offers detailed analysis and experiments to support its claim.\n\n# Weaknesses\n\nn/a\n", "summary_of_the_paper": "This paper re-evaluates WMD and identifies issues with the original paper. It shows that the gain from the original paper is not the product of WMD but the normalization. When the normalization is controlled, WMD performs similarly to baseline. Finally, it shows WMD resembles classic BOW when normalization is controlled.\n", "summary_of_the_review": "This paper revisits the original WMD paper and offers a detailed evaluation showing what contributes to the performance gain: normalization instead of WMD.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "o9TtH4rOojQ", "reviewer": "Reviewer_5Jna", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper targets a fairer evaluation of WMD. This is a critical problem worth exploring as WMD is a fundamental technique in various research fields. The core claims in this paper include: \n1. In the original study of WMD, many duplicate samples exist in the datasets, and applying L2 norm to word embeddings is not explicitly stated.\n2. The superiority of WMD over BOW and TF-IDF will weaken enormously by normalizing the BOW and TF-IDF.\n3. Both the normalization of word vectors and document-level distance metric (L1 or L2) will impact performance.\n4. WMD coincides with L1/L1 BOW empirically and theoretically, consistent with the two modalities characteristic of high-dimensional word embeddings.\n\nBy designing extensive experiments, the authors present the above observations and corresponding suggestions. They also provide clean datasets without duplicated samples and related code for further research. Following are some of my questions.\n\nIn figure 4, what metric is used for word-level distance?  Experiments show that L1 document-level distance with L1-normalized BOW/TF-IDF will generate the best performance. Regarding WMD, I wonder about the effects of different word-level distances (e.g., L1, L2, or Cosine). For example, WMD uses L2 word-level distance, then what about using other metrics? Besides, what if we use L1 normalization for word embeddings in WMD? \n\nIn my experience, the performance of WMD is extensively affected by the removal of appropriate stop-words. This paper only mentions the stop-word strategy on page 7.  I am wondering if the author removed the stop words in other experiments.\n\nTable 3-5 shows that removing OOV words brings significant performance degradation on bbcsports and ohsumed, which is somewhat against expectations. Is there any explanation for this observation?\n\n", "summary_of_the_paper": "This paper empirically shows that the performance of WMD is not as high as initially reported, and the real performance is comparable to  L1-normalized BOW, which can be formulated as a specific case of WMD. The authors also find that WMD resembles BOW in high-dimensional spaces. ", "summary_of_the_review": "This paper re-evaluates the Word Mover's Distance by well-designed experiments. They reveal the true performance of WMD and draw its relationship with L1-normalized BOW. I am more inclined to accept this paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "hAhH3iJOZ-f", "reviewer": "Reviewer_id2C", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper presents a thorough re-evaluation of the word mover's distance paper by Kusner et al. (2015), focusing on a number of points that are considered misleading. The paper has a point about the fact that the normalization of the word vectors used in WMD by Kusner et al. was not mentioned in the paper, even though it was possible to find out in the code released by the authors (misleading point 2). I think that while welcome as a clarification, I think calling this omission misleading is a bit of a stretch, especially given that this was possible to find in the code released by the authors. The paper then criticises Kusner et al. for not using such a nornalization for the document vectors obtained by BOW and TFIDF, which they find improves their results (misleading point 3). However, it should be noted that the original paper included other methods for comparison, which performed rather competitive to WMD, so while I agree with this paper that Kusner et al. didn't do justice to BoW and TFIDF, they did show that other methods were competitive to WMD but not as good. This paper also admits this too. Furthermore, in WMD the normalization is at the word embedding level, while the L1/L2 normalization on BoW/TFIDF is at the document level, thus it is not a direct correspondence. Thus I don't think there is much to see here, unless the paper would like to be more of a case of how to make the most of token-matching distance metrics.\n\nThe first misleading point is about the datasets containing duplicates. But not sure this has to do that much with the method of Kusner et al. per se, especially given that the datasets are well-known and used frequently. Perhaps they shouldn't be, and a paper could be written about this. As for the misleading point 4, I have to disagree with this paper. The example from figure 1 in Kusner et al illustrates well how word embeddings could help us do something more useful than 0-1 distances in token matching metrics, which would be the case of their example. The arguments in  section 5 on the modes (not modalities) are not particularly tight. If anything, the BoW representation of a word or document is much more high dimensional than that of a (300 dim) word embedding, assuming that one has thousands of words typically. The point that Kusner et al. made was the word embedding distances are more informative than word matching, and this is confirmed in the plots of figure 4: different word pairs get different distances.\n\nOn the whole I believe that much of the criticism of this paper is not justified. The main claims of the Kusner et al. paper still hold, and the experiments in this paper confirm them in my mind. I would suggest that perhaps a better paper would be assessing the evaluation practices in distance metrics more broadly, using multiple state-of-the-art methods. While WMD influenced the way people are thinking, using it for this purpose with old embeddings on text classification which is nowadays dominated by fine-tuning pre-trained language models is not particularly informative.", "summary_of_the_paper": "This paper presents a re-evaluation of a well known distance metric for documents with word embeddings. The authors identify some missing information from the original paper and they provide some extra analyses.", "summary_of_the_review": "On the whole, while I appreciate the work to bring to the community's attention some extra information and analyses of the Word Mover's Distance paper, the paper is not very informative. I think a much more interesting paper would be to survey the evaluation of multiple distance metric learning approaches and discuss common pitfalls more broadly, rather than pick on one paper in the context of a task that it wouldn't be considered a standard method for (fine-tuning BERT style pre-trained models is the go-to method for text classification and is much better than word embeddings from 2015 with kNN).", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "UJIjlMmCzKX", "reviewer": "Reviewer_sFeb", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Strength\nThe paper presents experimental results that the WMD distance doesn't improve performance by a factor of 100% but rather by a factor of 10%. This corrects some misconceptions that may have arisen in a particular sub-field of NLP.\n\n### Weakness\nThe paper will have a low impact, and is too focused on refuting the results of a single paper. I believe that this paper may be well suited to conferences devoted to the particular application area of document classification or NLP in general, but as it is the paper's methodological contribution, or technical contribution is too little.\n\nThe paper presents a sub-section on the \"re-evaluation of existing methods\" in section 2 to answer some of this criticism, but all the papers in that section were much more wide-ranging in their focus-area. E.g. the (Dacrema et al.) paper was not focused on the results of a single paper but on multiple papers, and the paper by (Arora et al. 2017) presented a novel method. The paper by (Shen et al. 2018) was accepted at ACL which is an NLP conference more focused on NLP tasks.\n", "summary_of_the_paper": "This paper shows that when standard baseline methods are carefully evaluated, such as using L1 normalization of the tf-idf/bow vector, then the performance difference between the baselines and the WMD distance based methods shrinks considerably.\n\nThe authors also claim that the findings in the paper are more general in the sense, that the distance between the embeddings of two words behaves more and more like a delta function, which is bimodal : close to one when the words are distinct, and close to 0 when the words are the same.\n", "summary_of_the_review": "The paper corrects some errors made in an earlier paper by (Kusner et al. 2015) and presents a careful evaluation of baselines for document classification applications. However, I believe that the paper is more suited for an NLP conference than ICLR.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors conduct extensive experiments to show that there were some errors in the original claims of the WMD paper and as opposed to what was claimed in the original paper, WMD does not outperform simpler baselines like BOW and TF-IDF. The authors claim that this is significant because WMD is widely used in the literature and hence pointing out errors in the original paper may help the community. 

Out of the 4 reviewers, 1 reviewer wrote a very short review and despite reminders did not elaborate on the reasons for a "Strong Accept". The other reviewer with a "Strong Accept" rating also did not champion the paper in the final discussions. The main objection of the two reviewers who were not in favor of accepting the paper were that (i) it focuses on cirticising a single paper and (ii) some of the criticism is not fair. In response, the authors claim that given the huge amount of derivative work which uses or builds upon the original WMD metric it is crucial to point out these errors. 

Having read the reviews and the responses, it is not clear to me whether such a paper which focuses only on such criticism of a single paper (not matter how popular it is) has enough merit in being accepted. Alternatively, if such criticism was a part of a broader work (maybe a work on new document similarity metrics) then it would have more merit. Further, it should be noted that of the 4 misleading conclusions of the original paper identified by the authors at least 2 are debatable (one being an error in the dataset and the other being a normalisation technique which was not mentioned in the paper but used in the code). The authors have also rephrased one of the original 4 misleading points and from the discussion it seems that they agree it is not misleading. It would have been easier for me to accept the paper if it had a new metric and ablation studies which showed that (i) Hey, normalisation is important and should be done for all baseline algorithms that are being compared (ii) Hey, there are errors in the dataset which affect the results
Decision: Reject