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 ein metrischer Raum, in dem jedes Wahrscheinlichkeitsmaß ein Radonmaß auf ist, auch Radon-Raum genannt. Für sei die Menge aller Wahrscheinlichkeitsmaße auf mit endlichem -ten Moment, das heißt, für ein aus gilt

.

Dann ist die -te Wasserstein-Distanz zwischen zwei Wahrscheinlichkeitsmaßen und aus für definiert als

,

wobei die Menge aller Maße auf bezeichnet mit und als Randverteilungen bezüglich des ersten beziehungsweise zweiten Faktors. ( wird auch die Menge aller Kopplungen zwischen und genannt.) Für ist die Wasserstein-Distanz definiert als

[1]

wobei der Träger des Maßes ist.

Beispiele

Dirac-Maß

Seien und zwei Diracmaße mit . Dann ist die einzige mögliche Kopplung . Nimmt man nun als Distanzfunktion die Betragsfunktion auf , so erhält man für jedes beliebige

Ist nun und nimmt man statt der Betragsfunktion den euklidischen Abstand, so erhält man

Normalverteilung

Seien und zwei Normalverteilungen auf dem , mit Erwartungswerten und Kovarianzmatrizen . Nimmt man nun als Distanzfunktion den euklidischen Abstand, so lässt sich die 2-Wasserstein-Metrik zwischen und als Summe der quadratischen euklidischen Distanz der Mittelwerte und einer Funktion der Kovarianzen ausdrücken:

[2][3]

Dieses Ergebnis verallgemeinert mit 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 und 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 weit verbreitet, um diskrete Verteilungen zu vergleichen, zum Beispiel die Farbhistogramme zweier digitaler Bilder.

Eigenschaften

Metrische Struktur

Es lässt sich zeigen, dass alle Axiome einer Metrik auf erfüllt. Zudem ist Konvergenz bezüglich äquivalent zur schwachen Konvergenz von Maßen plus die Konvergenz der ersten Momente.

Es gilt für und

[1]

Duale Darstellung des W1

Wenn und beschränkte Träger haben, dann gilt

,

wobei die kleinste Lipschitzkonstante von beschreibt.

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

.

Falls die Metrik durch beschränkt ist, so gilt

.

Somit impliziert die Konvergenz in der Radon-Metrik die Konvergenz bezüglich . Die Rückrichtung gilt im Allgemeinen nicht.

Separabilität und Vollständigkeit

Für jedes ist der metrische Raum separabel und vollständig, wenn 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.