A FAST AND SPACE-ECONOMICAL APPROACH TO WORD MOVER S DISTANCE
Matheus Werner · 2019
The Word Mover's Distance (WMD) proposed in Kusner et.al. [ICML,2015] is a distance between documents that takes advantage of semantic relations among words that are captured by their Word Embeddings.This distance proved to be quite effective, obtaining state-of-the-art error rates for classification tasks, but also impracticable for large collections or documents because it needs to compute a transportation problem on a complete bipartite graph for each pair of documents.By using assumptions, that are supported by empirical properties of the distances between Word Embeddings, we simplify WMD so that we obtain a new distance whose computation requires the solution of a max flow problem in a sparse graph, which can be solved much faster than the transportation problem in a dense graph.Our experiments show that we can obtain a performance gain up to 3 orders of magnitude over WMD while maintaining the same error rates in document classification tasks.