We re-evaluate the Word Mover's Distance and reveal the true performance of it.

Paper: https://arxiv.org/abs/2105.14403

↓ KNN classification errors in the original evaluation:

↓ kNN classification errors in our re-evaluation (after applying L1 normalization to BOW and TF-IDF):

• Python >= 3.7.3
• numpy >= 1.16.4
• matplotlib >= 3.1.1
• scipy >= 1.5.4
• scikit-learn >= 0.22.1
• gensim >= 3.8.3
• POT >= 0.7.0

Install them by pip install -r requirements.txt.

Please be sure that wget and unzip are available in your machine for downloading the dataests. For example, apt install wget zip unzip in Ubuntu, or brew install wget in Mac will install them. Then,

$ bash ./download.sh

If it fails to download the distance matrices, please download the file from https://drive.google.com/uc?id=1svEiRgQWMDk-mO8NVMhJCrwvkpQy-l4f via a web browser and unzip it to the distance/ directory. There should be, for example, ./distance/bbcsport-emd_tr_te_split.mat.npy after this process.

./dataset/*.mat are the datasets. Please refer to https://github.com/mkusner/wmd for more details.

./distance/*.npy are the distance matrics. They can be loaded by the np.load function. The ij-th element stores the WMD distance between the i-th and j-th documents. See "Compute distances" to compute the matrix by yourself.

Note that there exists an empty document in the 20news dataset. The distance matrix has -1 for the corresponding row and column. We included this document in the distance matrix because we want the shape to match the dataset size. Be sure to handle -1 appropriately.

Figure 3 and Tables 2 and 3 can be reproduced by python evaluate.py. Be sure to create or download the datasets and distance matrices beforehand. Each line reports an error of a method for one-fold datasets and an error and std-dev for five-fold datasets.

$ python evaluate.py
bbcsport-emd_tr_te_split.mat
----------------------------
BOW (L1/L1)     3.9 ± 1.1
TF-IDF (L1/L1)  2.8 ± 1.1
BOW (L1/L2)     11.4 ± 3.6
TF-IDF (L1/L2)  25.5 ± 11.2
BOW (L2/L1)     15.2 ± 1.5
...

python duplication.py checks duplications in the dataset. This script (1) reports the number of duplicated pairs and samples and (2) creates datasets without duplications. For the five-fold datasets, we maintain the original train/test splits, but it varys the size of training data among splits (though they are roughly the same). Therefore, data['TR'] and data['TE'] have different shapes with the original dataset. See evaluate.py for detailed usages.

Results for python evaluate.py (See Table 2 in the paper for more details).

Results for python evaluate.py --clean (See Table 3 in the paper for more details). Be sure to create clean data by python duplication.py before executing this.

python create_lowdim.py creates low dimensional data by the principal component analysis. It generates data in the data/ directory. This process is necessary if you want to generate low dimensional plots, as we describe in the following sections.

Figures 4 and 7 can be reproduced by

$ python plot_scatter.py

Images are created in the imgs/ directory. Be sure to create or download the datasets and distance matrices beforehand. See also "Create low dimensional data."

↓ Scatter plots of WMD vs L1/L1 BOW:

↓ Scatter plots of WMD vs L1/L1 BOW in 5-dimensional spaces:

Figures 5 and 8 can be reproduced by

$ python plot_histogram.py

Images are created in the imgs/ directory. Be sure to create or download the datasets and distance matrices beforehand. See also "Create low dimensional data."

↓ Histograms of distances between matched words:

↓ Histograms of distances between matched words in 5-dimensional spaces:

compute_distances.py and summarize_distances.py are scripts for computing WMD distances by yourself. Note that you do not have to use these scripts if you use pre-computed matrices. See also "Download datasets and distance matrices."

compute_distances.py creates distance files in the out/ directory, and summarize_distances.py creates a numpy.array object in the distance/ directory. Be sure to clean the out/ directory before running compute_distances.py.

These scripts are desingend for (naive) parallerization. The second commandline argument specifys the number of workers and the third commandline argument specifyes the id of the worker. Be sure to control the number of cores it uses by e.g., OMP_NUM_THREADS. For example, if you use three workers, run

$ rm out/*
$ OMP_NUM_THREADS=1 python compute_distances.py data/bbcsport-emd_tr_te_split.mat 3 0
$ OMP_NUM_THREADS=1 python compute_distances.py data/bbcsport-emd_tr_te_split.mat 3 1
$ OMP_NUM_THREADS=1 python compute_distances.py data/bbcsport-emd_tr_te_split.mat 3 2
$ python summarize_distances.py data/bbcsport-emd_tr_te_split.mat

If you do not use parallerization, just run

$ rm out/*
$ python compute_distances.py data/bbcsport-emd_tr_te_split.mat 1 0
$ python summarize_distances.py

When --train flag is specified, it computes a distance matrix between training samples. This flag is valid only for one-fold datasets. This distance matrix is used for validation.

When --tfidf flag is specified, it computes WMD distances with TF-IDF weighting.

Be sure to pass these flags to both compute_distances.py and summarize_distances.py. For example,

$ rm out/*
$ OMP_NUM_THREADS=1 python compute_distances.py data/bbcsport-emd_tr_te_split.mat 3 0 --tfidf
$ OMP_NUM_THREADS=1 python compute_distances.py data/bbcsport-emd_tr_te_split.mat 3 1 --tfidf
$ OMP_NUM_THREADS=1 python compute_distances.py data/bbcsport-emd_tr_te_split.mat 3 2 --tfidf
$ python summarize_distances.py data/bbcsport-emd_tr_te_split.mat --tfidf

Please feel free to contact me at r.sato AT ml.ist.i.kyoto-u.ac.jp, or to open issues.

@article{sato2021reevaluating,
  author    = {Ryoma Sato and
               Makoto Yamada and
               Hisashi Kashima},
  title     = {Re-evaluating Word Mover's Distance},
  journal   = {arXiv},
  year      = {2021},
}