Skip to content
Last Dictionary
Plane
Mathematics & StatisticsGenerative MediaMachine Learning

Wasserstein distance

nounAlso: earth mover's distance, EMD, Wasserstein metric, Kantorovich–Rubinstein distance, optimal transport distance, optimal transport, Sinkhorn distance

In plain wordsA way of comparing two spreads of probability by imagining one as heaps of sand that must be shoveled into the shape of the other: the less shoveling, weighted by distance, the more alike they are.

  1. The cost of the cheapest transport plan between two probability distributionsprobability distribution, n.: A complete description of how likely each possible outcome is — for a fair die, one-sixth for each face. A language model produces one of these over its whole vocabulary at every step. on a metric space, where a plan says how much mass moves between each pair of points and moving a unit of mass costs the distance it travels (for the p-Wasserstein distance, that distance raised to the power p, with the p-th root taken of the total). Unlike the KLKullback–Leibler divergence, n.: A score for the cost of believing the wrong odds: on average, how much more surprised you will be by real outcomes than someone who knew the true probabilities. It is zero only when your odds are exactly right. and Jensen–Shannon divergencesJensen–Shannon divergence, n.: A balanced, two-way measure of how different two sets of probabilities are, comparing each with their average. Unlike its better-known cousin, it gives the same answer in both directions., it respects the geometry of the underlying space and stays finite and informative when distributions do not overlap: two point masses a distance d apart are d apart, not infinitely or maximally different. In one dimension the 1-Wasserstein distance is the area between the two cumulative distribution functions. The Wasserstein GAN (2017) trained its generator on a dual form estimated by a 1-LipschitzLipschitz continuity, n.: A guarantee that a function never changes too abruptly: its output can move at most a fixed multiple of how far its input moves. critic, improving stability; the 2-Wasserstein distance between Gaussians underlies the Fréchet inception distanceFréchet inception distance, n.: A score for image generators that compares the overall statistics of their pictures with those of real photos, as seen by an image-recognition network; lower is better.; and optimal-transport ideas inform flow matchingflow matching, n.: A way to train generators that learns, for every point between random noise and real data, which direction to move, so that noise can be steered smoothly into new examples., domain adaptation and the word mover's distance between documents. Exact computation is costly, so entropy-regularized (Sinkhorn) approximations are common.

    The Wasserstein distance between the two label distributions stayed small even though their supports barely overlapped.

Wp(P,Q)=(inf⁡γ∈Π(P,Q)E(x,y)∼γ[d(x,y)p])1/pW_p(P, Q) = \Big(\inf_{\gamma \in \Pi(P,Q)} \mathbb{E}_{(x,y)\sim\gamma}\big[d(x,y)^p\big]\Big)^{1/p}

Origin

The transport problem goes back to Gaspard Monge (1781) and was recast as a linear program by Leonid Kantorovich (1942). Leonid Vaserstein studied the metric in 1969, and Roland Dobrushin's 1970 paper named it after him; the name 'earth mover's distance' entered computer vision through Yossi Rubner, Carlo Tomasi and Leonidas Guibas (1998). Martin Arjovsky, Soumith Chintala and Léon Bottou's Wasserstein GAN (2017) made it famous in deep learning.

Related

See also
  • Kullback–Leibler divergenceKullback–Leibler divergence, n.: A score for the cost of believing the wrong odds: on average, how much more surprised you will be by real outcomes than someone who knew the true probabilities. It is zero only when your odds are exactly right.
  • Jensen–Shannon divergenceJensen–Shannon divergence, n.: A balanced, two-way measure of how different two sets of probabilities are, comparing each with their average. Unlike its better-known cousin, it gives the same answer in both directions.
  • generative adversarial networkgenerative adversarial network, n.: Two neural networks trained as rivals: one forges fake images, the other tries to spot the fakes. As both improve, the forger's output becomes realistic enough to fool people.
  • Lipschitz continuityLipschitz continuity, n.: A guarantee that a function never changes too abruptly: its output can move at most a fixed multiple of how far its input moves.
  • Fréchet inception distanceFréchet inception distance, n.: A score for image generators that compares the overall statistics of their pictures with those of real photos, as seen by an image-recognition network; lower is better.
  • flow matchingflow matching, n.: A way to train generators that learns, for every point between random noise and real data, which direction to move, so that noise can be steered smoothly into new examples.
Contrast with
  • Kullback–Leibler divergenceKullback–Leibler divergence, n.: A score for the cost of believing the wrong odds: on average, how much more surprised you will be by real outcomes than someone who knew the true probabilities. It is zero only when your odds are exactly right.

Sources

  1. Arjovsky, M., Chintala, S. & Bottou, L. (2017). Wasserstein GAN. arXiv:1701.07875. arxiv.org/abs/1701.07875

Mentioned in

Fréchet inception distanceFréchet inception distance, n.: A score for image generators that compares the overall statistics of their pictures with those of real photos, as seen by an image-recognition network; lower is better., Kullback–Leibler divergenceKullback–Leibler divergence, n.: A score for the cost of believing the wrong odds: on average, how much more surprised you will be by real outcomes than someone who knew the true probabilities. It is zero only when your odds are exactly right., linear programminglinear programming, n.: A mathematical way to find the best use of limited resources, such as a factory's machines or an airline's crews, when every cost and limit scales in simple proportion: twice the output needs twice the input., Jensen–Shannon divergenceJensen–Shannon divergence, n.: A balanced, two-way measure of how different two sets of probabilities are, comparing each with their average. Unlike its better-known cousin, it gives the same answer in both directions., Lipschitz continuityLipschitz continuity, n.: A guarantee that a function never changes too abruptly: its output can move at most a fixed multiple of how far its input moves., Wasserstein GANWasserstein GAN, n.: A version of the forger-versus-detective image generator that measures how far its fakes are from real data in a smoother way, making training steadier and easier to monitor.