What are Wasserstein and Earth Movers Distances 🌱

Last updated on March 13, 2021

What is Wasserstein distance

$Let (X, d)$ be a Polish metric space, and let $p \in [1, \infty) .$ For any two probability measures $μ, ν$ on $X,$ the Wasserstein distance of order $p$ between $μ$ and $ν$ is defined by the formula $\begin{aligned} W_{p} (μ, ν) & = {(inf_{π \in Π (μ, ν)} \int_{X} d (x, y)^{p} d π (x, y))}^{1 / p} \\ = inf {{[E d (X, Y)^{p}]}^{\frac{1}{p}}, law (X) = μ, law (Y) = ν} \end{aligned}$

W_{p} (μ_{0}, ν) = inf {E {[d {(X_{0}, X_{1})}^{p}]}^{1 / p} ∣ X_{0} comes from μ and X_{1} comes from ν}

What is the Earth Mover’s Distance

Finally, the Earth Mover (EM) (version of Wasserstein distance): Let $Π (P_{r}, P_{g})$ be the set of all joint distributions $γ$ whose marginal distributions are $P_{r}$ and $P_{g} .$ Then. $W (P_{r}, P_{g}) = inf_{γ \in Π (P_{r}, P_{g})} E_{(x, y) \sim γ} [‖ x - y ‖]$

First, the intuitive goal of the EM distance. Probability distributions are defined by how much mass they put on each point. Imagine we started with distribution $P_{r},$ and wanted to move mass around to change the distribution into $P_{g}$ . Moving mass $m$ by distance $d$ costs $m \cdot d$ effort. The earth mover distance is the minimal effort we need to spend. Why does the infimum over $Π (P_{r}, P_{g})$ give the minimal effort? You can think of each $γ \in Π$ as a transport plan. To execute the plan, for all $x, y$ move $γ (x, y)$ mass from $x$ to $y$ Every strategy for moving weight can be represented this way. But what properties does the plan need to satisfy to transform $P_{r}$ into $P_{g} ?$ The amount of mass that leaves $x$ is $\int_{y} γ (x, y) d y .$ This must equal $P_{r} (x),$ the amount of mass originally at $x$ . The amount of mass that enters $y$ is $\int_{x} γ (x, y) d x .$ This must equal $P_{g} (y),$ the amount of mass that ends up at $y$ . This shows why the marginals of $γ \in Π$ must be $P_{r}$ and $P_{g}$ . For scoring, the effort spent is $\int_{x} \int_{y} γ (x, y) | x - y | d y d x = E_{(x, y) \sim γ} [| x - y |]$ Computing the infinum of this over all valid $γ$ gives the earth mover distance.

Check out this link for a good explanation.

Notes mentioning this note

There are no notes linking to this note.

Here are all the notes in this garden, along with their links, visualized as a graph.