# Word Mover's distance calculation between word pairs of two documents

According to WMD paper, travel cost or Euclidean distance between word pairs is calculated the way shown in the figure below.

Is this distance calculated in pair wise in a specific order? Such that the first, second and so on from each document as shown in the figure Or Obama's distance is calculated from all four words in D0 and then the minimum of these four is shown in the figure only.

Can someone explain how this works?

Also, why is then all three words in D3 compared with President in D0?

Each word in a document is matched against all other words, but weighted by a flow matrix $\bf{T}$ (with constraints $d_i$, viz., $d_j$ for each row/column). That ensures the resulting distance will be symmetric, even when there is an unequal number of words that need to be matched. The idea for the WMD is based on the "Earth Mover's Distance" (EMD), originally published by Rubner et al. (2000), for measuring image similarities.

If both sentences have an equal number of words to compare (like $D_1$ and $D_0$), that leads to a flow [matrix] that pairs up (or "moves") only the words with the closest distances. I.e., leading to a solution for the matrix $\bf{T}$ where each row and column will have only one non-zero value, namely exactly the constraint's value (here, the sum of flow weights in every row and column must be 0.25, $d_i = d_j = 1/4 = 0.25$, because there are four words), for the best matching pair. Then, the distance between two sentences is the sum over the Euclidian distances [1] between closest word pairs, divided by the number of words. Put differently, the contribution of each pair to the overall distance "sum" is weighted by the flow matrix $\bf{T}$, that is, with 0.25 for each of the closest pairs and zero for all other possible pairings. That means, the flow matrix will only have a single non-zero value in each row and column in cases when both documents have the same number of words. Rather trivial, indeed - so far...

However, for the $(D_0, D_3)$ pair, figuring out the flow matrix $\bf{T}$ gets far more tricky: Each word in $D_3$ now has to be paired with more than one word in $D_0$. That is, because this time the flow constraints are $d_i = 1/4 = 0.25$ and $d_j = 1/3 = 0.33\dot3$, the resulting flow matrix must have more than one non-zero values in each of its three columns (words from $D_3$). Indeed, for a truly proper solution of this flow problem, you might expect that hardly any word pairing will have a flow of exactly zero.

Taking a "relaxed" approach to figuring out the flow matrix, we can simply move each word in $D_3$ to some unique match in $D_0$, with a weight of 0.25 (NB: Keep in mind, the words must not necessarily be paired with their best matches, only some unique match; You will understand why in a bit.) Then, for the remaining flow from each word in $D_3$ ($0.3\dot3 - 0.25 = 0.08\dot3$ here), we simply assign it to the only word in $D_0$ that was not yet matched (here, "President"). Therefore, each of the three columns in $\bf{T}$ (for the three words in $D_3$) will sum to $0.33\dot3$, just as the constraint $d_j$ requires. And each of the four rows (words in $D_0$) will sum to 0.25, either because the word is uniquely matched with that particular weight to a word in $D_0$, or because the word gets "divided up" among all three words in $D_3$, each with a weight of $0.08\dot3$ (because $0.08\dot3 \times 3 = 0.25$), thereby fulfilling the constraint $d_i$ (for each row, including the one for "President").

The interesting (or hard, depending on how you see it) part now is how to choose the unique matches and the remainder word(s). Note the arrows in Figure 2, bottom, seems to not represent the most logical flow; It seems counter-intuitive that "speaks" is not moved onto "greets" at all and only gets moved to "press" and "President", and that "Obama" is not primarily assigned to "President". However, this is a great example to highlight the core issue with this "relaxed" approach. The pairing of "speaks" with "greets", and of "Obama" with "President", which one might expect, would imply that "press" would have to receive all the remaining flows (just like "President" does in the figure), but that probably would have lead to a larger WMD than the one resulting from the assignments as shown in the figure (and described above). But then, given how "speaks" is not moved to "greets" at all, and "President" is not the unique pair for "Obama", you might expect that this "relaxed" way of solving the flow matrix does not work terribly well.

Now, as we already understand, the main problem that WMD needs to solve is that of assigning the weights in the flow matrix for cases where the number of words are different between the two documents. As the authors point out, via the referenced paper by Pele & Werman (2009), finding the best flow matrix (where "speaks" probably would be mostly assigned to "greets" and "President" to "Obama", but with weights lesser than 0.25) has a computational cost of $O(p^3 \log p)$, where $p$ denotes the number of unique words in the documents. Hence, the the paper discusses possible approximations, the best of which, Relaxed WMD (RWMD), as explained above, can bring the optimization cost down to a quadratic problem (in the number of words being compared), i.e., to $O(p^2)$. Those optimization savings result because you only need to trial all reasonable ways of assigning unique pairs while dividing up the remaining flow evenly among the words you did not pair. As it turns out, that relaxed approach comes at hardly any increase in test error - shown in Figure 7 in the paper!

[1] Yes, WMD indeed uses Euclidean distances, not the Cosine similarity (distance), as one might expect; See the WMD paper, section 4, "Word travel cost".

• can you add some explanation for the flow matrix and how it's different than a distance matrix? – utengr Sep 18 '17 at 7:46
• The flow matrix is explained in the EMD paper by Pele & Werman. The flow matrix provides the weights that are multiplied with the Euclidian distances between two connected word pairs. If you like, each element in $\bf{T}$ indicates the "contribution" that pair has to the overall WMD. – fnl Sep 18 '17 at 9:33
• Made some edits to clarify how the flow matrix contributes to the final (scalar) word mover distance being calculated. – fnl Sep 18 '17 at 9:41
• Sorry, I should be checking the paper's contents before citing them, mea culpa. The flow matrix isn't explained there, either, and only is referenced to yet another, earlier paper from 2000 by Rubner et al.. – fnl Sep 18 '17 at 9:52
• OK, had some facts not quite right from my own cursory read and updated this answer to fully explain (as I hope...) the flow matrix and why the arrows look as they do in Figure 2. – fnl Sep 20 '17 at 11:26