Earth mover's distance - Wikipedia
Jump to content
Search
Search
Donate
Create account
Log in
Personal tools
Donate
Create account
Log in
Earth mover's distance
3 languages
العربية<br>日本語<br>中文
Edit links
From Wikipedia, the free encyclopedia
Distance between probability distributions
In computer science, the earth mover's distance (EMD )[1] is a measure of dissimilarity between two frequency distributions, densities, or measures, over a metric space D.<br>Informally, if the distributions are interpreted as two different ways of piling up earth (dirt) over D, the EMD captures the minimum cost of building the smaller pile using dirt taken from the larger, where cost is defined as the amount of dirt moved multiplied by the distance over which it is moved.
Over probability distributions, the earth mover's distance is also known as the Wasserstein metric
{\displaystyle W_{1}}
, Kantorovich–Rubinstein metric, or Mallows's distance.[2] It is the solution of the optimal transport problem, which in turn is also known as the Monge-Kantorovich problem, or sometimes the Hitchcock–Koopmans transportation problem;[3] when the measures are uniform over a set of discrete elements, the same optimization problem is known as minimum weight bipartite matching.
Formal definitions<br>[edit]
The EMD between probability distributions
{\textstyle P}
and
{\textstyle Q}
can be defined as an infimum over joint probabilities:
EMD
inf
{\displaystyle {\text{EMD}}(P,Q)=\inf \limits _{\gamma \in \Pi (P,Q)}\mathbb {E} _{(x,y)\sim \gamma }\left[d(x,y)\right]\,}
where
{\displaystyle \Pi (P,Q)}
is the set of all joint distributions whose marginals are
{\displaystyle P}
and
{\displaystyle Q}
By Kantorovich-Rubinstein duality, this can also be expressed as:
EMD
sup
{\displaystyle {\text{EMD}}(P,Q)=\sup \limits _{\|f\|_{L}\leq 1}\,\mathbb {E} _{x\sim P}[f(x)]-\mathbb {E} _{y\sim Q}[f(y)]\,}
where the supremum is taken over all 1-Lipschitz continuous functions, i.e.
{\displaystyle \|\nabla f(x)\|\leq 1\quad \forall x}
EMD between signatures<br>[edit]
In some applications, it is convenient to represent a distribution
{\textstyle P}
as a signature, or a collection of clusters, where the
{\textstyle i}
-th cluster represents a feature of mass
{\textstyle w_{i}}
centered at
{\textstyle p_{i}}
In this formulation, consider signatures
{\textstyle P=\{(p_{1},w_{p1}),(p_{2},w_{p2}),...,(p_{m},w_{pm})\}}
and
{\textstyle Q=\{(q_{1},w_{q1}),(q_{2},w_{q2}),...,(q_{n},w_{qn})\}}
. Let
{\textstyle D=[d_{i,j}]}
be the ground distance between clusters
{\textstyle p_{i}}
and
{\textstyle q_{j}}
. Then the EMD between
{\textstyle P}
and
{\textstyle Q}
is given by the optimal flow
{\textstyle F=[f_{i,j}]}
, with
{\textstyle f_{i,j}}
the flow between
{\textstyle p_{i}}
and
{\textstyle q_{j}}
, that minimizes the overall cost.
min
{\displaystyle \min \limits _{F}{\sum _{i=1}^{m}\sum _{j=1}^{n}f_{i,j}d_{i,j}}}
subject to the constraints:
{\displaystyle f_{i,j}\geq 0,1\leq i\leq m,1\leq j\leq n}
{\displaystyle \sum _{j=1}^{n}{f_{i,j}}\leq w_{pi},1\leq i\leq m}
{\displaystyle \sum _{i=1}^{m}{f_{i,j}}\leq w_{qj},1\leq j\leq n}
min
{\displaystyle \sum _{i=1}^{m}\sum _{j=1}^{n}f_{i,j}=\min \left\{\ \sum _{i=1}^{m}w_{pi},\quad \sum _{j=1}^{n}w_{qj}\ \right\}}
The optimal flow
{\textstyle F}
is found by solving this linear optimization problem. The earth mover's distance is defined as the work normalized by the total flow:
EMD
{\displaystyle {\text{EMD}}(P,Q)={\frac {\sum _{i=1}^{m}\sum _{j=1}^{n}f_{i,j}d_{i,j}}{\sum _{i=1}^{m}\sum _{j=1}^{n}f_{i,j}}}}
Variants and extensions<br>[edit]
Unequal probability mass<br>[edit]
Some applications may require the comparison of distributions with different total masses. One approach is to allow for partial matching,[1] where dirt from the more massive distribution is rearranged to make the less massive, and any leftover "dirt" is discarded at no cost.<br>Formally, let
{\textstyle w_{P}}
be the total weight of
{\textstyle P}
, and
{\textstyle w_{Q}}
be the total weight of
{\textstyle Q}
. We have:
EMD
min
inf
{\displaystyle {\text{EMD}}(P,Q)={\tfrac {1}{\min(w_{P},w_{Q})}}\inf \limits _{\gamma \in \Pi _{\geq }(P,Q)}\int d(x,y)\,\mathrm {d} \gamma (x,y)}
where
{\displaystyle \Pi _{\geq }(P,Q)}
is the set of all measures whose projections are
{\displaystyle \geq P}
and
{\displaystyle \geq Q}
Note that this generalization of EMD is not a true distance between distributions, as it does not satisfy the triangle inequality.
An alternative approach is to allow for mass to be created or destroyed, on a global or local level, as an alternative to transportation, but with a cost penalty. In that case one must specify a real parameter
{\displaystyle \alpha }
, the ratio between the cost of creating or destroying one unit of "dirt", and the cost of transporting it by a unit distance. This is equivalent to minimizing the sum of the earth moving cost...