Earth Mover’s Distance

Say you’ve got a pile of dirt over here, and you want to move it over there, what is the minimum cost of doing so? (For the purposes of this discussion, assume that cost is the amount of dirt to be moved times the distance it is moved.)

Take this 10ft wide pile of gravel, for example. If you wanted to move it 100ft away, you’d have to pick the whole thing up, and move it over, right?

OTOH, if you just wanted to shift it by 1ft, you can just rearrange the pile a wee bit, by moving some of the dirt over to the right, basically the overlapping part (in red) alone.

The generalization of this solution — the distance between two probability distributions — is called the Earth Mover’s Distance (in statistics. In mathematics, it’s called the Wasserstein Metric. Because…math). It’s an incredibly useful thing, and can be applied to all sorts of fun stuff like machine learning, gerrymandering, and more.

For more, take a look at Jeremy Kun’s article on this topic.