Reproduce “Speeding up Word Mover's Distance and its variants via properties of distances between embeddings” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Matheus Werner, Eduardo Laber
A new method accelerates Word Mover's Distance and its variants by leveraging an empirical observation that only a small subset of word embedding distances are semantically relevant. This approach, implemented as Related Relaxed Word Mover's Distance (Rel-RWMD), achieves substantial computational speed-ups, often multiple times faster than existing methods, while maintaining or slightly improving document classification accuracy.
Key insights
- Distances between word embeddings exhibit a strong dichotomy: most word pairs are semantically unrelated and have large, similar distances, while true semantic relatedness is sparse and confined to a small number of close word pairs.
- By modeling unrelated word distances as a constant `c_max`, the complex optimal transport problem can be simplified, leading to a much sparser representation of the cost matrix.
- This domain-specific insight provides an alternative optimization paradigm to purely mathematical relaxations, effectively reducing the computational burden without compromising the semantic richness of WMD-like metrics.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.