Wasserstein-Metrik

Die Wasserstein-Metrik (auch Vaserstein-Metrik) ist eine Metrik zwischen Wahrscheinlichkeitsmaßen auf einem gegebenen metrischen Raum.

Intuitiv kann man sich vorstellen (Näheres unter optimaler Transport): Wenn jede Verteilung als ein Haufen von „Erde“ angehäuft auf dem metrischen Raum betrachtet wird, dann beschreibt diese Metrik die minimalen „Kosten“ der Umwandlung eines Haufens in den anderen. Wegen dieser Analogie ist diese Metrik in der Informatik als Earth-Mover’s-Metrik bekannt.

Den Namen erhielt die Metrik 1970 von Roland Lwowitsch Dobruschin, der sie nach Leonid Vaseršteĭn ("Wasserstein") benannte. Vaseršteĭn führte das Konzept 1969 ein.

Definition

Sei ${\displaystyle (M,d)}$ ein metrischer Raum, in dem jedes Wahrscheinlichkeitsmaß ein Radonmaß auf ${\displaystyle M}$ ist, auch Radon-Raum genannt. Für ${\displaystyle p\geq 1}$ sei ${\displaystyle P_{p}(M)}$ die Menge aller Wahrscheinlichkeitsmaße ${\displaystyle \mu }$ auf ${\displaystyle M}$ mit endlichem ${\displaystyle p}$-ten Moment, das heißt, für ein ${\displaystyle x_{0}}$ aus ${\displaystyle M}$ gilt

${\displaystyle \int _{M}d(x,x_{0})^{p}\mathrm {d} \mu (x)<\infty }$.

Dann ist die ${\displaystyle p}$-te Wasserstein-Distanz zwischen zwei Wahrscheinlichkeitsmaßen ${\displaystyle \mu }$ und ${\displaystyle \nu }$ aus ${\displaystyle P_{p}(M)}$ für ${\displaystyle p<\infty }$ definiert als

${\displaystyle W_{p}(\mu ,\nu ):=\left(\inf _{\gamma \in \Gamma (\mu ,\nu )}\int _{M\times M}d(x,y)^{p}\mathrm {d} \gamma (x,y)\right)^{\frac {1}{p}}}$,

wobei ${\displaystyle \Gamma (\mu ,\nu )}$ die Menge aller Maße auf ${\displaystyle M\times M}$ bezeichnet mit ${\displaystyle \mu }$ und ${\displaystyle \nu }$ als Randverteilungen bezüglich des ersten beziehungsweise zweiten Faktors. (${\displaystyle \Gamma (\mu ,\nu )}$ wird auch die Menge aller Kopplungen zwischen ${\displaystyle \mu }$ und ${\displaystyle \nu }$ genannt.) Für ${\displaystyle p=\infty }$ ist die Wasserstein-Distanz definiert als

${\displaystyle W_{\infty }(\mu ,\nu ):=\inf _{\gamma \in \Gamma (\mu ,\nu )}\sup _{(x,y)\in \mathrm {supp} (\gamma )}d(x,y),}$^[1]

wobei ${\displaystyle \mathrm {supp} (\gamma )}$ der Träger des Maßes ist.

Beispiele

Dirac-Maß

Seien ${\displaystyle \mu =\delta _{a_{1}}}$ und ${\displaystyle \nu =\delta _{a_{2}}}$ zwei Diracmaße mit ${\displaystyle a_{1},a_{2}\in \mathbb {R} }$. Dann ist die einzige mögliche Kopplung ${\displaystyle \delta _{(a_{1},a_{2})}}$. Nimmt man nun als Distanzfunktion die Betragsfunktion auf ${\displaystyle \mathbb {R} }$, so erhält man für jedes beliebige ${\displaystyle p\geq 1}$

${\displaystyle W_{p}(\mu ,\nu )=|a_{1}-a_{2}|.}$

Ist nun ${\displaystyle a_{1},a_{2}\in \mathbb {R} ^{n}}$ und nimmt man statt der Betragsfunktion den euklidischen Abstand, so erhält man

${\displaystyle W_{p}(\mu ,\nu )=\|a_{1}-a_{2}\|_{2}.}$

Normalverteilung

Seien ${\displaystyle \mu ={\mathcal {N}}(m_{1},C_{1})}$ und ${\displaystyle \nu ={\mathcal {N}}(m_{2},C_{2})}$ zwei Normalverteilungen auf dem ${\displaystyle \mathbb {R} ^{n}}$, mit Erwartungswerten ${\displaystyle m_{1},m_{2}\in \mathbb {R} ^{n}}$ und Kovarianzmatrizen ${\displaystyle C_{1},C_{2}\in \mathbb {R} ^{n\times n}}$. Nimmt man nun als Distanzfunktion den euklidischen Abstand, so lässt sich die 2-Wasserstein-Metrik zwischen ${\displaystyle \mu }$ und ${\displaystyle \nu }$ als Summe der quadratischen euklidischen Distanz der Mittelwerte und einer Funktion der Kovarianzen ausdrücken:

${\displaystyle W_{2}(\mu ,\nu )^{2}=\|m_{1}-m_{2}\|_{2}^{2}+\operatorname {Spur} \left(C_{1}+C_{2}-2(C_{2}^{1/2}C_{1}C_{2}^{1/2})^{1/2}\right)=\|m_{1}-m_{2}\|_{2}^{2}+\operatorname {Spur} \left(C_{1}\right)+\operatorname {Spur} \left(C_{2}\right)-2\operatorname {Spur} \left((C_{1}C_{2})^{1/2}\right).}$ ^[2][3]

Dieses Ergebnis verallgemeinert mit ${\displaystyle p=2}$ das vorangegangene Beispiel, da das Diracmaß als Normalverteilung mit Kovarianzmatrix gleich null betrachtet werden kann. Dann entfallen die Spurterme und es bleibt nur der Abstand zwischen den Erwartungswerten.

Anwendung

Die Wasserstein-Metrik ist ein natürlicher Weg, um die Wahrscheinlichkeitsverteilungen zweier Variablen ${\displaystyle X}$ und ${\displaystyle Y}$ zu vergleichen, wobei eine Variable von der anderen durch kleine, ungleichförmige Störungen (zufällig oder deterministisch) abgeleitet wird.

In der Informatik ist beispielsweise die Metrik ${\displaystyle W_{1}}$ weit verbreitet, um diskrete Verteilungen zu vergleichen, zum Beispiel die Farbhistogramme zweier digitaler Bilder.

Eigenschaften

Metrische Struktur

Es lässt sich zeigen, dass ${\displaystyle W_{p}}$ alle Axiome einer Metrik auf ${\displaystyle P_{p}(M)}$ erfüllt. Zudem ist Konvergenz bezüglich ${\displaystyle W_{p}}$ äquivalent zur schwachen Konvergenz von Maßen plus die Konvergenz der ersten ${\displaystyle p}$ Momente.

Es gilt für ${\displaystyle 1\leq p\leq q<\infty }$ und ${\displaystyle \mu ,\nu \in P_{p}(M)}$

${\displaystyle W_{p}(\mu ,\nu )\leq W_{q}(\mu ,\nu ).}$^[1]

Duale Darstellung des W₁

Wenn ${\displaystyle \mu }$ und ${\displaystyle \nu }$ beschränkte Träger haben, dann gilt

${\displaystyle W_{1}(\mu ,\nu )=\sup \left\{\left.\int _{M}f(x)\,\mathrm {d} (\mu -\nu )(x)\right|f\colon M\to \mathbb {R} {\text{ stetig}},\,\mathrm {Lip} (f)\leq 1\right\}}$,

wobei ${\displaystyle \mathrm {Lip} (f)}$ die kleinste Lipschitzkonstante von ${\displaystyle f}$ beschreibt.

Dies lässt sich mit der Definition der Radon-Metrik vergleichen:

${\displaystyle \rho (\mu ,\nu ):=\sup \left\{\left.\int _{M}f(x)\,\mathrm {d} (\mu -\nu )(x)\right|f\colon M\to [-1,1]{\text{ stetig}}\right\}}$.

Falls die Metrik ${\displaystyle d}$ durch ${\displaystyle C>0}$ beschränkt ist, so gilt

${\displaystyle 2W_{1}(\mu ,\nu )\leq C\rho (\mu ,\nu )}$.

Somit impliziert die Konvergenz in der Radon-Metrik die Konvergenz bezüglich ${\displaystyle W_{1}}$. Die Rückrichtung gilt im Allgemeinen nicht.

Separabilität und Vollständigkeit

Für jedes ${\displaystyle p\geq 1}$ ist der metrische Raum ${\displaystyle (P_{p}(M),W_{p})}$ separabel und vollständig, wenn ${\displaystyle (M,d)}$ separabel und vollständig ist.^[4]

Literatur

• Ambrosio, L., Gigli, N. & Savaré, G.: Gradient Flows in Metric Spaces and in the Space of Probability Measures. ETH Zürich, Birkhäuser Verlag, Basel 2005, ISBN 3-7643-2428-7. 
• Richard Jordan, David Kinderlehrer, Felix Otto: The variational formulation of the Fokker-Planck equation. In: SIAM J. Math. Anal. 29. Jahrgang, Nr. 1, 1998, ISSN 0036-1410, S. 1–17 (electronic), doi:10.1137/S0036141096303359. 

Einzelnachweise

1. ↑ ^{a b} Facundo Mémoli: Gromov–Wasserstein Distances and the Metric Approach to Object Matching. In: Foundation of Computational Mathematics. April 2011, S. 427–430, doi:10.1007/s10208-011-9093-5. 
2. ↑ Olkin, I. and Pukelsheim, F.: The distance between two random vectors with given dispersion matrices. In: Linear Algebra Appl. 48. Jahrgang, 1982, ISSN 0024-3795, S. 257–263, doi:10.1016/0024-3795(82)90112-4. 
3. ↑ Dowson, D. C. and Landau, B. V.: The Fréchet Distance between Multivariate Normal Distributions. In: J. of Multivariate Analysis. 12. Jahrgang, Nr. 3, 1982, ISSN 0047-259X, S. 450–455, doi:10.1016/0047-259X(82)90077-X. 
4. ↑ Bogachev, V.I., Kolesnikov, A.V.: The Monge-Kantorovich problem: achievements, connections, and perspectives. In: Russian Math. Surveys. 67. Jahrgang, S. 785–890, doi:10.1070/RM2012v067n05ABEH004808.