In
mathematics, the
Wasserstein distance or
Kantorovich
Leonid Vitalyevich Kantorovich ( rus, Леони́д Вита́льевич Канторо́вич, , p=lʲɪɐˈnʲit vʲɪˈtalʲjɪvʲɪtɕ kəntɐˈrovʲɪtɕ, a=Ru-Leonid_Vitaliyevich_Kantorovich.ogg; 19 January 19127 April 1986) was a Soviet ...
–
Rubinstein metric is a
distance function
In mathematics, a metric space is a set together with a notion of ''distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general setting ...
defined between
probability distributions
In probability theory and statistics, a probability distribution is the mathematical function that gives the probabilities of occurrence of different possible outcomes for an experiment. It is a mathematical description of a random phenomenon ...
on a given
metric space
In mathematics, a metric space is a set together with a notion of ''distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general settin ...
. It is named after
Leonid Vaseršteĭn.
Intuitively, if each distribution is viewed as a unit amount of earth (soil) piled on ''
'', the metric is the minimum "cost" of turning one pile into the other, which is assumed to be the amount of earth that needs to be moved times the mean distance it has to be moved. This problem was first formalised by
Gaspard Monge
Gaspard Monge, Comte de Péluse (9 May 1746 – 28 July 1818) was a French mathematician, commonly presented as the inventor of descriptive geometry, (the mathematical basis of) technical drawing, and the father of differential geometry. Durin ...
in 1781. Because of this analogy, the metric is known in
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
as the
earth mover's distance
In statistics, the earth mover's distance (EMD) is a measure of the distance between two probability distributions over a region ''D''. In mathematics, this is known as the Wasserstein metric. Informally, if the distributions are interpreted ...
.
The name "Wasserstein distance" was coined by
R. L. Dobrushin in 1970, after learning of it in the work of
Leonid Vaseršteĭn on Markov processes describing large systems of automata (Russian, 1969). However the metric was first defined by
Leonid Kantorovich
Leonid Vitalyevich Kantorovich ( rus, Леони́д Вита́льевич Канторо́вич, , p=lʲɪɐˈnʲit vʲɪˈtalʲjɪvʲɪtɕ kəntɐˈrovʲɪtɕ, a=Ru-Leonid_Vitaliyevich_Kantorovich.ogg; 19 January 19127 April 1986) was a Soviet ...
in ''The Mathematical Method of Production Planning and Organization'' (Russian original 1939) in the context of optimal transport planning of goods and materials. Some scholars thus encourage use of the terms "Kantorovich metric" and "Kantorovich distance". Most
English
English usually refers to:
* English language
* English people
English may also refer to:
Peoples, culture, and language
* ''English'', an adjective for something of, from, or related to England
** English national ide ...
-language publications use the
German
German(s) may refer to:
* Germany (of or related to)
**Germania (historical use)
* Germans, citizens of Germany, people of German ancestry, or native speakers of the German language
** For citizens of Germany, see also German nationality law
**Ger ...
spelling "Wasserstein" (attributed to the name "Vaseršteĭn" being of
German
German(s) may refer to:
* Germany (of or related to)
**Germania (historical use)
* Germans, citizens of Germany, people of German ancestry, or native speakers of the German language
** For citizens of Germany, see also German nationality law
**Ger ...
origin).
Definition
Let
be a
metric space
In mathematics, a metric space is a set together with a notion of ''distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general settin ...
that is a
Radon space
In the mathematical discipline of general topology, a Polish space is a separable completely metrizable topological space; that is, a space homeomorphic to a complete metric space that has a countable dense subset. Polish spaces are so named be ...
. For
,_the_Wasserstein_
p-distance_between_two_probability_measures_
\mu_and_
\nu_on_
M_with_finite_
p-
,_the_Wasserstein_p-distance_between_two_probability_measure">,_\infty),_the_Wasserstein_p-distance_between_two_probability_measures_
\mu_and_
\nu_on_
M_with_finite_
p-Moment_(mathematics)">moments_is
:
W_p(\mu,_\nu)_=_\left(_\inf__\mathbf__d(x,_y)^p_\right)^
where_
\Gamma(\mu,_\nu)_is_the_set_of_all_coupling_(probability).html" ;"title="Moment_(mathematics).html" ;"title="probability_measure.html" ;"title=", \infty), the Wasserstein
p-distance between two probability measure">, \infty), the Wasserstein
p-distance between two probability measures
\mu and
\nu on
M with finite
p-Moment (mathematics)">moments is
:
W_p(\mu, \nu) = \left( \inf_ \mathbf_ d(x, y)^p \right)^
where
\Gamma(\mu, \nu) is the set of all coupling (probability)">couplings of
\mu and
\nu. A coupling
\gamma is a joint probability measure on
M \times M whose marginal distribution, marginals are
\mu and
\nu on the first and second factors, respectively. That is,
:
\int_M \gamma(x, y) \,\mathrmy = \mu(x)
:
\int_M \gamma(x, y) \,\mathrmx = \nu(y)
Intuition and connection to optimal transport
One way to understand the above definition is to consider the
optimal transport problem
In mathematics and economics, transportation theory or transport theory is a name given to the study of optimal transportation and allocation of resources. The problem was formalized by the French mathematician Gaspard Monge in 1781.G. Monge. '' ...
. That is, for a distribution of mass
\mu(x) on a space
X, we wish to transport the mass in such a way that it is transformed into the distribution
\nu(x) on the same space; transforming the 'pile of earth'
\mu to the pile
\nu. This problem only makes sense if the pile to be created has the same mass as the pile to be moved; therefore without loss of generality assume that
\mu and
\nu are probability distributions containing a total mass of 1. Assume also that there is given some cost function
:
c(x,y) \geq 0
that gives the cost of transporting a unit mass from the point
x to the point
y.
A transport plan to move
\mu into
\nu can be described by a function
\gamma(x,y) which gives the amount of mass to move from
x to
y. You can imagine the task as the need to move a pile of earth of shape
\mu to the hole in the ground of shape
\nu such that at the end, both the pile of earth and the hole in the ground completely vanish. In order for this plan to be meaningful, it must satisfy the following properties
:
\begin
\int \gamma(x,y) \,\mathrm y = \mu(x) & \qquad \text x \text \\
\int \gamma(x,y) \,\mathrm x = \nu(y) & \qquad \text y \text
\end
That is, that the total mass moved ''out of'' an infinitesimal region around
x must be equal to
\mu(x) \mathrmx and the total mass moved ''into'' a region around
y must be
\nu(y)\mathrmy. This is equivalent to the requirement that
\gamma be a
joint probability distribution
Given two random variables that are defined on the same probability space, the joint probability distribution is the corresponding probability distribution on all possible pairs of outputs. The joint distribution can just as well be considered ...
with marginals
\mu and
\nu. Thus, the infinitesimal mass transported from
x to
y is
\gamma(x,y) \, \mathrm x \, \mathrm y, and the cost of moving is
c(x,y) \gamma(x,y) \, \mathrm x \, \mathrm y, following the definition of the cost function. Therefore, the total cost of a transport plan
\gamma is
:
\iint c(x,y) \gamma(x,y) \, \mathrm x \, \mathrm y = \int c(x,y) \, \mathrm \gamma(x,y)
The plan
\gamma is not unique; the optimal transport plan is the plan with the minimal cost out of all possible transport plans. As mentioned, the requirement for a plan to be valid is that it is a joint distribution with marginals
\mu and
\nu; letting
\Gamma denote the set of all such measures as in the first section, the cost of the optimal plan is
:
C = \inf_ \int c(x,y) \, \mathrm \gamma(x,y)
If the cost of a move is simply the distance between the two points, then the optimal cost is identical to the definition of the
W_1 distance.
Examples
Point masses (degenerate distributions)
Let
\mu_ = \delta_ and
\mu_ = \delta_ be two
degenerate distribution
In mathematics, a degenerate distribution is, according to some, a probability distribution in a space with support only on a manifold of lower dimension, and according to others a distribution with support only at a single point. By the latter ...
s (i.e.
Dirac delta distribution
In mathematics, the Dirac delta distribution ( distribution), also known as the unit impulse, is a generalized function or distribution over the real numbers, whose value is zero everywhere except at zero, and whose integral over the entire ...
s) located at points
a_ and
a_ in
\mathbb. There is only one possible coupling of these two measures, namely the point mass
\delta_ located at
(a_, a_) \in \mathbb^. Thus, using the usual
absolute value
In mathematics, the absolute value or modulus of a real number x, is the non-negative value without regard to its sign. Namely, , x, =x if is a positive number, and , x, =-x if x is negative (in which case negating x makes -x positive), an ...
function as the distance function on
\mathbb, for any
p \geq 1, the
p-Wasserstein distance between
\mu_ and
\mu_2 is
:
W_p (\mu_1, \mu_2) = , a_1 - a_2 , .
By similar reasoning, if
\mu_ = \delta_ and
\mu_ = \delta_ are point masses located at points
a_ and
a_ in
\mathbb^, and we use the usual
Euclidean norm
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidean s ...
on
\mathbb^ as the distance function, then
:
W_p (\mu_1, \mu_2) = \, a_1 - a_2 \, _2 .
Normal distributions
Let
\mu_1 = \mathcal(m_1, C_1) and
\mu_2 = \mathcal(m_2, C_2) be two non-degenerate
Gaussian measure
In mathematics, Gaussian measure is a Borel measure on finite-dimensional Euclidean space R''n'', closely related to the normal distribution in statistics. There is also a generalization to infinite-dimensional spaces. Gaussian measures are named ...
s (i.e.
normal distribution
In statistics, a normal distribution or Gaussian distribution is a type of continuous probability distribution for a real-valued random variable. The general form of its probability density function is
:
f(x) = \frac e^
The parameter \mu ...
s) on
\mathbb^n, with respective
expected value
In probability theory, the expected value (also called expectation, expectancy, mathematical expectation, mean, average, or first moment) is a generalization of the weighted average. Informally, the expected value is the arithmetic mean of a l ...
s
m_1 and
m_2 \in \mathbb^n and
symmetric positive semi-definite covariance matrices
In probability theory and statistics, a covariance matrix (also known as auto-covariance matrix, dispersion matrix, variance matrix, or variance–covariance matrix) is a square matrix giving the covariance between each pair of elements of ...
C_ and
C_2 \in \mathbb^. Then, with respect to the usual Euclidean norm on
\mathbb^, the 2-Wasserstein distance between
\mu_ and
\mu_ is
:
W_ (\mu_1, \mu_2)^2 = \, m_1 - m_2 \, _2^2 + \mathop \bigl( C_1 + C_2 - 2 \bigl( C_2^ C_1 C_2^ \bigr)^ \bigr) .
This result generalises the earlier example of the Wasserstein distance between two point masses (at least in the case
p = 2), since a point mass can be regarded as a normal distribution with covariance matrix equal to zero, in which case the
trace
Trace may refer to:
Arts and entertainment Music
* ''Trace'' (Son Volt album), 1995
* ''Trace'' (Died Pretty album), 1993
* Trace (band), a Dutch progressive rock band
* ''The Trace'' (album)
Other uses in arts and entertainment
* ''Trace'' ...
term disappears and only the term involving the Euclidean distance between the means remains.
One-dimensional distributions
Let
\mu_1, \mu_2 \in P_p(\mathbb) be probability measures on
\mathbb, and denote their
cumulative distribution functions
In probability theory and statistics, the cumulative distribution function (CDF) of a real-valued random variable X, or just distribution function of X, evaluated at x, is the probability that X will take a value less than or equal to x.
Ever ...
by
F_1(x) and
F_2(x). Then the transport problem has an analytic solution: Optimal transport preserves the order of probability mass elements, so the mass at quantile
q of
\mu_1 moves to quantile
q of
\mu_2.
Thus, the
p-Wasserstein distance between
\mu_1 and
\mu_2 is
:
W_p(\mu_1, \mu_2) = \left(\int_0^1 \left, F_1^(q) - F_2^(q) \^p \, \mathrm q\right)^
where
F_1^ and
F_2^ are the
quantile functions (inverse CDFs).
In the case of
p=1, a change of variables leads to the formula
:
W_1(\mu_1, \mu_2) = \int_ \left, F_1(x) - F_2(x) \ \, \mathrm x .
Applications
The Wasserstein metric is a natural way to compare the probability distributions of two variables ''X'' and ''Y'', where one variable is derived from the other by small, non-uniform perturbations (random or deterministic).
In computer science, for example, the metric ''W''
1 is widely used to compare discrete distributions, ''e.g.'' the
color histogram
In image processing and photography, a color histogram is a representation of the distribution of colors in an image. For digital images, a color histogram represents the number of pixels that have colors in each of a fixed list of color ranges, ...
s of two
digital images
A digital image is an image composed of picture elements, also known as ''pixels'', each with ''finite'', '' discrete quantities'' of numeric representation for its intensity or gray level that is an output from its two-dimensional functions f ...
; see
earth mover's distance
In statistics, the earth mover's distance (EMD) is a measure of the distance between two probability distributions over a region ''D''. In mathematics, this is known as the Wasserstein metric. Informally, if the distributions are interpreted ...
for more details.
In their paper '
Wasserstein GAN
The Wasserstein Generative Adversarial Network (WGAN) is a variant of generative adversarial network (GAN) proposed in 2017 that aims to "improve the stability of learning, get rid of problems like mode collapse, and provide meaningful learning c ...
', Arjovsky et al. use the Wasserstein-1 metric as a way to improve the original framework of
Generative Adversarial Networks
A generative adversarial network (GAN) is a class of machine learning frameworks designed by Ian Goodfellow and his colleagues in June 2014. Two neural networks contest with each other in the form of a zero-sum game, where one agent's gain is a ...
(GAN), to alleviate the
vanishing gradient
In machine learning, the vanishing gradient problem is encountered when training artificial neural networks with gradient-based learning methods and backpropagation. In such methods, during each iteration of training each of the neural network's ...
and the mode collapse issues. The special case of normal distributions is used in a
Frechet Inception Distance.
The Wasserstein metric has a formal link with
Procrustes analysis
In statistics, Procrustes analysis is a form of statistical shape analysis used to analyse the distribution of a set of shapes. The name ''Procrustes'' ( el, Προκρούστης) refers to a bandit from Greek mythology who made his victims fi ...
, with application to chirality measures, and to shape analysis.
In computational biology, Wasserstein metric can be used to compare between
persistence diagrams of cytometry datasets.
The Wasserstein metric also has been used in inverse problems in geophysics.
The Wasserstein metric is used in
Integrated information theory
Integrated information theory (IIT) attempts to provide a framework capable of explaining why some physical systems (such as human brains) are conscious, why they feel the particular way they do in particular states (e.g. why our visual field appe ...
to compute the difference between concepts and conceptual structures.
Properties
Metric structure
It can be shown that ''W''
''p'' satisfies all the
axiom
An axiom, postulate, or assumption is a statement that is taken to be true, to serve as a premise or starting point for further reasoning and arguments. The word comes from the Ancient Greek word (), meaning 'that which is thought worthy or f ...
s of a
metric
Metric or metrical may refer to:
* Metric system, an internationally adopted decimal system of measurement
* An adjective indicating relation to measurement in general, or a noun describing a specific type of measurement
Mathematics
In mathem ...
on ''P''
''p''(''M''). Furthermore, convergence with respect to ''W''
''p'' is equivalent to the usual
weak convergence of measures
In mathematics, more specifically measure theory, there are various notions of the convergence of measures. For an intuitive general sense of what is meant by ''convergence of measures'', consider a sequence of measures μ''n'' on a space, sharing ...
plus convergence of the first ''p''th moments.
Dual representation of ''W''1
The following dual representation of ''W''
1 is a special case of the duality theorem of
Kantorovich
Leonid Vitalyevich Kantorovich ( rus, Леони́д Вита́льевич Канторо́вич, , p=lʲɪɐˈnʲit vʲɪˈtalʲjɪvʲɪtɕ kəntɐˈrovʲɪtɕ, a=Ru-Leonid_Vitaliyevich_Kantorovich.ogg; 19 January 19127 April 1986) was a Soviet ...
and Rubinstein (1958): when ''μ'' and ''ν'' have
bounded support
Support may refer to:
Arts, entertainment, and media
* Supporting character
Business and finance
* Support (technical analysis)
* Child support
* Customer support
* Income Support
Construction
* Support (structure), or lateral support, a ...
,
:
W_1 (\mu, \nu) = \sup \left\,
where Lip(''f'') denotes the minimal
Lipschitz constant
In mathematical analysis, Lipschitz continuity, named after German mathematician Rudolf Lipschitz, is a strong form of uniform continuity for functions. Intuitively, a Lipschitz continuous function is limited in how fast it can change: there ex ...
for ''f''.
Compare this with the definition of the
Radon metric:
:
\rho (\mu, \nu) := \sup \left\.
If the metric ''d'' is bounded by some constant ''C'', then
:
2 W_1 (\mu, \nu) \leq C \rho (\mu, \nu),
and so convergence in the Radon metric (identical to total variation convergence when ''M'' is a
Polish space
In the mathematical discipline of general topology, a Polish space is a separable completely metrizable topological space; that is, a space homeomorphic to a complete metric space that has a countable dense subset. Polish spaces are so named bec ...
) implies convergence in the Wasserstein metric, but not vice versa.
Proof
The following is an intuitive proof which skips over technical points. A fully rigorous proof is found in.
Discrete case: When
M is discrete, solving for the 1-Wasserstein distance is a problem in linear programming:
\begin
\min_\gamma \sum_ c(x, y) \gamma(x, y) \\
\sum_y \gamma(x, y) = \mu(x) \\
\sum_x \gamma(x, y) = \nu(y) \\
\gamma \geq 0
\endwhere
c: M \times M \to :\begin
__\max__\sum_x_\mu(x)f(x)_+_\sum_y_\nu(y)g(y)\\
__f(x)_+_g(y)_\leq_c(x,_y)
__\endand_by_the_Dual_linear_program#Strong_duality.html" ;"title="Dual_linear_program.html" "title=", \infty) is a general "cost function".
By carefully writing the above equations as matrix equations, we obtain its Dual linear program">dual problem
In mathematical optimization theory, duality or the duality principle is the principle that optimization problems may be viewed from either of two perspectives, the primal problem or the dual problem. If the primal is a minimization problem then th ...
and by the Dual linear program#Strong duality">duality theorem of linear programming, since the primal problem is feasible and bounded, so is the dual problem, and the minimum in the first problem equals the maximum in the second problem. That is, the problem pair exhibits ''strong duality''.
For the general case, the dual problem is found by converting sums to integrals:
and the ''strong duality'' still holds.
This is the Kantorovich duality theorem. Cédric Villani recounts the following interpretation from
The two infimal convolution steps are visually clear when the probability space is
.
For notational convenience, let
denote the infimal convolution operation.
For the first step, where we used
, then at each point, draw a cone of slope 1, and take the lower envelope of the cones as
cannot increase with slope larger than 1. Thus all its secants have slope
.
For the second step, picture the infimal convolution
.
1D Example. When both
That is, the mass should be conserved, and the velocity field should transport the probability distribution