Year: 2021

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.

text: 1 INTRODUCTION
The optimal transport (OT) distance is an effective tool for comparing probabilistic distributions. Applications of OT include image processing (Ni et al., 2009; Rabin et al., 2011; De Goes et al., 2012), natural language processing (NLP) (Kusner et al., 2015; Rolet et al., 2016), biology (Schiebinger et al., 2019; Lozupone & Knight, 2005; Evans & Matsen, 2012), and generative models (Arjovsky et al., 2017; Salimans et al., 2018).
A prominent application of OT is the word mover’s distance (WMD) (Kusner et al., 2015) for document comparison. WMD regards a document as a 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 it takes the underlying geometry into account. For example, bag-of-words (BOW) will conclude that two documents are dissimilar if they have no common words, whereas WMD will determine that they are similar if the words are semantically similar (even if they are not exactly the same), as illustrated in Figure 1.
WMD has been widely used in NLP owing to this preferred property. For example, Kusner et 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 et al., 2020; Genevay et al., 2016; 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 crucial 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
classification errors reported in (Kusner et al., 2015). This figure clearly shows that WMD is superior to classical baselines, BOW and TF-IDF1
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 it 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 on 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 on 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 of only two to eight percent at the price of heavy computations. We also confirm that TF-IDF is more effective than raw BOW if we employ adequate normalization.
To understand the mechanism of WMD, we introduce an analogy between WMD and L1-normalized BOW. We experimentally find that the distribution of the distances between matched words is not Gaussian-like but two-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 to classical baselines in document classification with the same normalization.
• We introduce an analogy between WMD and L1-normalized BOW (Proposition 1) and find that WMD resembles BOW in high dimensional spaces (Figure 5).
• We point out several confusing aspects in the evaluations conducted in the original study on WMD. We suspect that many readers and researchers are unaware of these issues. Clarifying them is crucial for a solid evaluation and analysis in this field
Reproducibility. We include our code in the supplementary materials. It contains a script to download datasets and pre-computed results, algorithm implementations, and evaluation code.

heading: 2 RELATED WORK
text: 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) is a method concurrent
1It should be noted that (Kusner et al., 2015) used many stronger baselines such as LSI and LDA. We focus on BOW and TF-IDF because (i) BOW was used as the base performance (Figure 4 in (Kusner et al., 2015), Figure 4 in (Yurochkin et al., 2019)), and (ii) BOW is a special case of WMD (Propositoin 1).
with WMD. It also regards a document as a 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 a document as 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 a structured OT and applied it to a 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 et 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-like distance instead of the standard OT to compare documents. Zhang et al. (2016) and others (Zhang et al., 2017b;a; Grave et al., 2019; Dou & Neubig, 2021) use OT to align word embeddings of different languages. Trapp et 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 a 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).

heading: 3 BACKGROUNDS

heading: 3.1 PROBLEM FORMULATION
text: In this paper, we consider document classification tasks. Each document is represented by a bag-ofword vector x ∈ Rm, where m is the number of unique words in the dataset. The i-th component of x 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 k samples of the smallest distances (with respect to a certain distance) to 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.

heading: 3.2 WORD MOVER’S DISTANCE (WMD)
text: WMD provides an effective distance function utilizing pre-trained word embeddings. Let zi be the embedding of the i-th word. To utilize OT, WMD first regards a document as a discrete probabilistic distribution of words by normalizing the bag-of-word vector:
nL1(x) = x/ ∑ i xi. (1)
WMD defines the cost matrix C ∈ Rm×Rm as the distance of the embeddings, i.e., Cij = ‖zi−zj‖2. The distance between the two documents x and x′ is the optimal value of the following problem:
minimize P∈Rm×m ∑ ij CijPij (2)
s.t. Pij ≥ 0,P1 = nL1(x),P>1 = nL1(x′), where P> denotes the transpose of P , 1 ∈ Rm is the vector of ones. Intuitively, Pij 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,x′,C) ∈ R be the optimal value of eq. (2).

heading: 3.3 EXPERIMENTAL SETUPS
text: Datasets. We use the same datasets (Greene & Cunningham, 2006; Sanders, 2011; Joachims, 1998; Sebastiani, 2002; Lang, 1995) as in the original paper (Kusner et 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 1 shows the statistics. Here, we point out the first misleading point.
Misleading Point 1 Many duplicate samples exist in the datasets.
The last two rows in Table 1 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, a 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 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 et 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 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.
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 WMD2 normalized the embeddings by the L2 norm, although 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 Distance (Yokoi et al., 2020) proposed to use the angles between word embeddings
2https://github.com/mkusner/wmd
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-IDF, we use a different preprocessing to clearly contrast the results. WMD discards certain words because the word embeddings do not contain all words. In 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 is 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 at the end of Section 4 for completeness.
Evaluation Protocol. WMD, BOW, and TF-IDF all have only one hyperparameter, i.e., size k of the neighborhood in kNN classification. We split the training set into an 80/20 train/validation set uniformly and randomly and select the neighborhood size from {1, 2, · · · , 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-based methods. Nevertheless, we adopt kNN evaluations in the main part to clearly contrast our results with the original evaluation. This is justified because we only use kNN classification for all methods. However, this fact can be a misleading point if other classifiers are used for other methods, as in (Wu et al., 2018; Skianis et al., 2020b; Mollaysa et al., 2017; Gupta et al., 2020). We report this issue in more detail in Appendix B.
Environment. We use a server cluster to 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.

heading: 4 NORMALIZATION IS CRUCIAL
text: 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 if two documents share the same topic, the BOW vectors are distant if their lengths differ. We need to normalize these vectors to effectively use them in the nearest neighbor classification.
Misleading Point 3 The original evaluation did not normalize the BOW and TF-IDF vectors.
To make direct comparisons to WMD, we employ L1 normalization (Eq. (1)) and the L1 distance for BOW and TF-IDF vectors, i.e., dBOW/L1/L1(x,x′) = ‖nL1(x)− nL1(x′)‖1. With this normalization, BOW is a special case of WMD that does not use the underlying geometry. Specifically, let Cunif be the cost matrix of WMD when we use one-hot vectors as word embeddings, i.e., Cunifij = 0 if i = j and Cunifij = 2 if i 6= j. Then, Proposition 1. dBOW/L1/L1(x,x′) = OT(x,x′,Cunif)
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, we can see that the errors of BOW and TF-IDF drastically decrease. Even BOW performs better than WMD in bbcsport 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-IDF.
Comparison with other Normalization. Although normalized BOW and TF-IDF have been employed 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 incompatible 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 L1 normalization and the L2 metric for BOW, i.e., ‖nL1(x) − nL1(x′)‖2, and L2 normalization and the L2 metric for TF-IDF, i.e., ‖nL2(x) − nL2(x′)‖2, where nL2(x) = x/‖x‖2. Note that the L2/L2 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 2 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/L1 scheme is the best for all datasets. This result is natural if we adopt the stance that a document is a distribution of words, and based on the analogy between the L1/L1 BOW and WMD, i.e., Proposition 1. To summarize, the normalization method significantly affects the performance. BOW L1/L1 corresponds to “WMD without OT” (Proposition 1), and BOW None/L1 corresponds “BOW L1/L1 without normalization”. The performances of these methods are
3.931 (BOW None/L1) introducing normalization−−−−−−−−−−−−−→ 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/L1) to normalization (by a factor of 3.9) rather than the OT formulation (by only a factor of 1.09). This “ablation study” indicates that L1 normalization is the most significant factor of improvement in WMD. We stress that the improvements brought about by L1 normalization are obtained almost for
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, we 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 xtfidf ∈ Rd denote a TF-IDF vector. We use nL1(xtfidf) instead of nL1(x) 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 2 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 Cunif. 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 sixty 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 3 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-IDF 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 3 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 a worthwhile candidate over L1/L1 BOW.

heading: 5 WMD RESEMBLES BOW IN HIGH DIMENSIONAL SPACES
text: In this section, we experimentally show that not only the performance of WMD but also the distance values of WMD themselves resemble those of L1/L1 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 = 0, 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 a 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. In contrast to the high dimensional cases, these histograms are almost one 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 is two modal (zero or around one) in high dimensional spaces. In an extreme case, if the distance is exactly zero or one, Proposition 1 shows that WMD coincides with L1/L1 BOW. If not exact, we experimentally show that the distance values of WMD themselves resemble those of L1/L1 BOW.
Figure 5 shows correlations between WMD and L1/L1 BOW distances and reports the Pearson’s correlation coefficients ρ. WMD and L1/L1 BOW are surprisingly similar to each other. To contrast the results with low dimensional cases, we also report the scatter plots using 5-dimensional embeddings in the bottom of Figure 5. In contrast to the high dimensional cases, these scatter plots show that WMD in low dimensional spaces is not similar to L1/L1 BOW. These results indicate that the similarity to L1/L1 BOW is a characteristic phenomenon in 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(“Obama greets”, “band greets”) = 1.342 + 0 < 2WMD(“Obama greets”, “President speaks”) = 1.174 + 0.978,
BOW(“Obama greets”, “band greets”) = 1 < BOW(“Obama greets”, “President speaks”) = 2.
This “almost equally distant” property may not be expected in the two-dimensional illustration (Figure 1). While such an illustration is helpful for understanding the mechanism of WMD, it does not reflect the high dimensional nature of word embeddings. The characteristics of high dimensionality should also be kept in mind to understand the behavior of WMD more precisely.
It should be noted that 5-dimensional WMD performs worse than 300-dimensional WMD because 5-dimensional WMD loses much information on 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 L1/L1 BOW, i.e., a special case of WMD that completely discriminates each word from the others.

heading: 6 CONCLUSION
text: 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 of WMD and classical baselines and found that classical baselines are competitive with WMD if we 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, we 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.

heading: A DUPLICATE DOCUMENTS
text: 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, t) such that s and t are the same, and “duplicate samples” reports the number of samples s such that s 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 bbcsport3 already contained duplicate samples, e.g., athletics/12.txt and athletics/20.txt. We hypothesis this was originated from the data collection process.
Although such duplication is not a 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 et 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.

heading: B NEAREST NEIGHBOR CLASSIFICATION IS FAR FROM OPTIMAL
text: 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 we 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; 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 a 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, we found that a weighted kNN classifier (wkNN) with exponential weighting was a good choice for distance-based methods. Specifically, wkNN first gathers k nearest neighbor samples and computes the distances {d1, · · · , dk} to these samples. It then defines the weight for sample i as exp(−di/γ) and takes the weighted majority vote, where γ is a hyperparameter. We can think of wkNN as a 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.
3http://mlg.ucd.ie/datasets/bbc.html
We conduct experiments to show the suboptimality of kNN. As the drawback of wkNN, it has two hyperparameters k and γ. We find that the k of wkNN plays a similar role as the maximum k of kNN in the hyperparameter tuning. Thus, we fix k of wkNN to 19 and tune only γ in the hyperparameter tuning. Recall that the hyperparameter candidates were k ∈ {1, · · · , 19} for kNN in the previous experiments and original paper. We select γ from Γ = {0.005, 0.010, · · · , 0.095, 0.1} (|Γ| = 20) in the hyperparameter tuning4. The remaining settings are the same as in 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 row in Table 2). This indicates that if a proposed method uses non-kNN classifiers, ten percent improvements from the kNN baselines may be due to classifiers, not to the proposed method. This also indicates that there is significant room for improvement in the classifiers before undergoing a design of better similarity measures.
It 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 be cited as baseline records in following papers, in which other classifiers may be employed. In fact, such comparisons have been carried out in (Wu et 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 a better choice than kNN because it is as fast as kNN yet much more effective.

heading: C COMPARISON WITH OTHER NORMALIZATION WITH CLEAN DATA
text: Table 7 shows the kNN classification errors with clean data. The same tendency as Table 2 can be observed.

heading: D PERFORMANCE OF LOW DIMENSIONAL EMBEDDINGS
text: Table 8 shows the classification errors of WMD with the 5-dimensional embeddings used in Section 5. It 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
4The magnitude of this range is determined by the empirical distances between samples. This arbitrary choice is a slight drawback of wkNN. We will investigate how to choose it automatically in future work.
reasonable that counting common words can perform better than relying too much on the underlying geometry.

heading: E PROOF OF PROPOSITION 1
text: We prove the analogy between L1/L1 BOW and OT. Recall that dBOW/L1/L1(x,x
′) = ‖nL1(x)− nL1(x′)‖1, and
Cunifij =
{ 0 (i = j)
2 (i 6= j).
Proof of Proposition 1. Without loss of generality, we assume that the marginals x and x′ are already L1 normalized, and ∑ i xi = 1 and ∑ i x ′ i = 1 hold. Let P
∗ ∈ Rm×m be the optimal solution of OT(x,x′,Cunif). From the marginal constraints, P ∗ii ≤ min(xi,x′i) holds. If P ∗ii < min(xi,x′i), there exists j 6= i and k 6= i such that P ∗ij > 0 and P ∗ki > 0 from the marginal constraints. Then, let Q ∈ Rm×m be
Qst =  P ∗ii + min(P ∗ ij ,P ∗ ki) (s = i ∧ t = i) P ∗ij −min(P ∗ij ,P ∗ki) (s = i ∧ t = j) P ∗ki −min(P ∗ij ,P ∗ki) (s = k ∧ t = i) P ∗kj + min(P ∗ ij ,P ∗ ki) (s = k ∧ t = j)
P ∗st (otherwise). Then, Q satisfies the constraints of OT and(∑
st
Cunifst P ∗ st
) − (∑ st Cunifst Qst ) = Cunifii (P ∗ ii − (P ∗ii + min(P ∗ij ,P ∗ki))) + Cunifij (P ∗ij − (P ∗ij −min(P ∗ij ,P ∗ki)))
+ Cunifki (P ∗ ki − (P ∗ki −min(P ∗ij ,P ∗ki))) + Cunifkj (P ∗kj − P ∗kj + min(P ∗ij ,P ∗ki)))
= (4−Cunifkj ) min(P ∗ij ,P ∗ki) > 0.
The first equation holds from the definition of Q, and the second equation holds because Cunifii = 0 and Cunifij = C unif jk = 2, and the last inequality holds because C unif kl ≤ 2 and min(P ∗ij ,P ∗ki) > 0. This contradicts with the optimality of P ∗. Therefore, P ∗ii = min(xi,x ′ i) holds. Therefore, ∑ st Cunifst P ∗ st
= ∑ st 2(11> − diag(1))stP ∗st
= 2 ∑ st P ∗st − 2 ∑ s P ∗ss
= 2− 2 ∑ s min(xs,x ′ s)
= ∑ s xs + ∑ s x′s − ∑ s min(xs,x ′ s)− ∑ s min(xs,x ′ s)
= ∑ s (xs −min(xs,x′s)) + (x′s −min(xs,x′s))
= ∑ s |xs − x′s| = ‖x− x′‖1.

heading: F ADDITIONAL RELATED WORK
text: 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 to 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 et 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 in a one-dimensional space can be solved efficiently (Santambrogio, 2015). Paty & Cuturi (2019) and others (Kolouri et al., 2019; Dhouib et 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 to candidate projections. Although we tried in early experiments several projection methods, including the principal component analysis as in 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.

Review summaries:
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.