Earth mover’s distance

Anh-Thi Dinh
MathsData ScienceStatistics

What (general)?

  • In statistics, the earth mover's distance (EMD) is a measure of the distance between two probability distributions over a region D. (ref)
  • In stats or computer science, it's "Earth mover's distance".
  • In maths, it's "Wasserstein metric"
  • The Wasserstein distance is the minimum cost of transporting mass in converting the data distribution q to the data distribution p.

What (math way)?

The idea borrowed from this. The first Wasserstein distance between the distributions and is:
where is the set of (probability) distributions on whose marginals are and on the first and second factors respectively.
If and are the respective CDFs of and , this distance also equals to:

Example of metric

Suppose we wanna move the blocks on the left to dotted-blocks on the right, we wanna find the "energy" (or metric) to do that.
Energy = weight of block x distance to move that block.
Suppose that weight of each block is 1. All below figures are copied from this.
There are 2 ways to do that,
2 ways of moving blocks from left to right.
Above example gives the same energies () but there are usually different as below example,

Coding

1from scipy.stats import wasserstein_distance
1arr1 = [1,2,3,4,5,6]
2arr2 = [1,2,3,4,5,6]
3wasserstein_distance(arr1, arr2)
1# output
20.0
3# they are exactly the same!
1arr1 = [1,2,3]
2arr2 = [4,5,6]
3wasserstein_distance(arr1, arr2)
4# 3.0000000000000004
5
6import seaborn as sns
7sns.distplot(arr1, kde=False, hist_kws={"histtype": "step", "linewidth": 3, "alpha": 1, "color": "b"})
8sns.distplot(arr2, kde=False, hist_kws={"histtype": "step", "linewidth": 3, "alpha": 1, "color": "r"})
 

References