word mover's distance

[zachmayer]

See the paper and the gensim implementation.

I've found this method to do a better job of measuring "distance" between documents than summing the word vectors and comparing.

[dselivanov]

There is a emdist package for calculating Earth mover's distance. Not sure it uses the same algorithm as FastEMD.

[zachmayer]

emddist looks really interesting, but it doesn't support matrices with > 4 dimensions, e.g.:

set.seed(1)
x <- matrix(runif(5), nrow=1)
y <- matrix(runif(5), nrow=1)
emdist::emd(x, y)

vs

set.seed(1)
x <- matrix(runif(10), nrow=1)
y <- matrix(runif(10), nrow=1)
emdist::emd(x, y)

[pommedeterresautee]

@dselivanov Below my thought without checking the source code (so may be wrong).
according to the R package PDF :

R code by Simon Urbanek, EMD code by Yossi Rubner.

http://robotics.stanford.edu/~rubner/emd/default.htm
The code on the website from Rubner is based on a paper dated as of 1998

[dselivanov]

@pommedeterresautee I saw comments, but still not sure about algorithm...

Anyway I think it will not too hard to port FastEMD.

[pommedeterresautee]

@dselivanov yep there are obviously several version of the algo implemented. May be taking FastEMD is the easiest option indeed. You will be sure of the quality.
@zachmayer have you tried earth mover on FastSent vectors? (I am not sure it makes sense as you are supposed to sum/mean word vectors to build the vec representation of a doc in FastSent but may be using word mover like you would do with W2V vectors would give interesting results to compare two documents)

[zachmayer]

@pommedeterresautee I haven't tried EMD on fastsent vectors, but that seems like a really interesting idea.

I guess there are 2 ways to use EMD:

1. Compare 2 matrices of word vectors, where each the rows are words and the columns are word vectors.
2. Compare 2 vectors directly, where each vector is a "document" vector of some kind.

I guess 2 is a special case of 1

[dselivanov]

Just re-read paper. Looks really interesting. Also I think we can focus on relaxed word word-movers distance - RWMD, because of following:

1. It has much lower computational complexity - O(N^2) vs O(N^3 * log(N))
2. Results of RWMD are very close to WMD
3. It is quite trivial to efficiently implement it in pure R

@zachmayer did you use euclidean distance or cosine?

[zachmayer]

I tried both euclidean distance and cosine distance. Got much better results from cosine distance and word movers distance than euclidean.

[dselivanov]

I was confused by the fact, that authors used euclidean distance.

[zachmayer]

I agree. They should have compared to cosine distance.

[dselivanov]

@zachmayer I have pretty efficient code for RWMD. Can you suggest any test cases / good datasets? I found these two exaples: blog post and gensim wmd tutorial.

[zachmayer]

Those examples look great to me. The "President greets the press in Chicago" sentence is the one I thought of off the top of my head.

[pommedeterresautee]

http://www.cis.upenn.edu/~ccb/ppdb/ (there are many more if you are interested).

This repository should provide you lots of stuff to work on:
https://github.com/brmson/dataset-sts

http://ixa2.si.ehu.es/stswiki/index.php/Main_Page

[pommedeterresautee]

For what it worth I also implemented it (in Python) and got nice results.
However, it is not that awesome compared to a simple average word embedding + cosine.
I also tried EMD function from a Python package. Results are of similar quality.
Curious to know you opinion @dselivanov

[zachmayer]

Maybe the standford question answering dataset? Probably not the perfect use case, but could be interesting to try out: https://twitter.com/stanfordnlp/status/744539496230707200

[pommedeterresautee]

The new Stanford dataset is about finding the correct answer inside a provided document. As the whole document has the same subject than the question I imagine any simple algo won't work well if it's not trained to perform this specific task.

Paraphrase task seems the task we try to solve and would make sense for a future text2vec Vignette.

[dselivanov]

RWMD and bunch of other distances now are in 0.4 branch - see ?dist2, pdist2 (pdist2 is not finished yet).
I implemented both cosine and euclidean distances for comparing word vectors in RWMD. RWMD with cosine distance is faster and more accurate, based on my quick test. But both euclidean and cosine are much faster than linked python implementations (but mb I missed something). If you use good BLAS such as OpenBLAS/ATLAS/vecLib - RWMD with cosine distance will be parallelised out of the box.

I don't have tutorials/ use cases yet. I only had quick tests on movie_review dataset. Performance on sentiment analysis using KNN with word embeddings trained on wikipedia dump is nearly the same as using KNN on LSA (SVD) vectors.
Looking forward for your feedback.

[zachmayer]

This is awesome, thank you!

[pommedeterresautee]

@dselivanov regarding your findings, as said before, even using the full WMD I don t see a big difference with simply comparing with averaging word vectors. However I have not compared word embedding averaging and... SVD!

[dselivanov]

RWMD in master. Closing, see ?RWMD.

[dselivanov]

Linear-Complexity Relaxed Word Mover’s Distance - https://arxiv.org/abs/1711.07227