Understanding EMD via concept and from-scratch calculation

After studying this text you’ll have an in-depth understanding of how the Earth Mover’s Distance (aka EMD or Wasserstein Distance) is calculated. From that data, you’ll have a good suggestion of its advantages and disadvantages in numerous functions.

Contents

1. Definition and instinct of Earth Mover’s Distance (EMD)
2. Purposes of EMD
3. Calculating EMD from scratch
4. Calculating EMD with the scipy package deal
5. Conclusion

Definition and instinct of Earth Mover’s Distance

The Earth Mover’s Distance is a selected calculation to measure the distinction between two distributions. The identify “Earth Mover’s Distance” comes from its intuitive interpretation. Think about you might have two piles of dust (or earth) which might be in several areas and have completely different shapes. The EMD is how a lot work (outlined as the full quantity of earth moved instances the gap) it takes to maneuver the second pile to appear like the primary pile.

I feel that is greatest illustrated in an instance: Let’s say now we have two distributions, A and B, and we wish to understand how completely different they’re. EMD, solutions this query by reworking A into B and measuring how a lot complete work was executed (i.e. variety of items moved X distance moved) to make the transformation. The instance under illustrates calculating the EMD for 2 easy distributions:

The identify for the set of strikes we make to remodel one distribution into the opposite known as a ‘transport plan’ — consider transporting dust or materials from one location to a different.

The transport plan for the graphic above seems like this:

The transport plan reveals us essentially the most environment friendly means of remodeling distribution A into…