Wasserstein-Metrik

Die Wasserstein-Metrik (auch Vaserstein-Metrik und Kantorowitsch-Rubinstein-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 $(M, d)$ ein metrischer Raum, in dem jedes Wahrscheinlichkeitsmaß ein Radonmaß auf $M$ ist, auch Radon-Raum genannt. Für $p \geq 1$ sei $P_{p} (M)$ die Menge aller Wahrscheinlichkeitsmaße $μ$ auf $M$ mit endlichem $p$ -ten Moment, das heißt, für ein $x_{0}$ aus $M$ gilt

\int_{M} d (x, x_{0})^{p} d μ (x) < \infty

.

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

W_{p} (μ, ν) := {(inf_{γ \in Γ (μ, ν)} \int_{M \times M} d (x, y)^{p} d γ (x, y))}^{\frac{1}{p}}

,

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

W_{\infty} (μ, ν) := inf_{γ \in Γ (μ, ν)} sup_{(x, y) \in s u p p (γ)} d (x, y),

wobei $s u p p (γ)$ der Träger des Maßes ist.

Beispiele

Dirac-Maß

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

W_{p} (μ, ν) = | a_{1} - a_{2} | .

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

W_{p} (μ, ν) = ‖ a_{1} - a_{2} ‖_{2} .

Normalverteilung

Seien $μ = 𝒩 (m_{1}, C_{1})$ und $ν = 𝒩 (m_{2}, C_{2})$ zwei Normalverteilungen auf dem $ℝ^{n}$ , mit Erwartungswerten $m_{1}, m_{2} \in ℝ^{n}$ und Kovarianzmatrizen $C_{1}, C_{2} \in ℝ^{n \times n}$ . 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:

W_{2} (μ, ν)^{2} = ‖ m_{1} - m_{2} ‖_{2}^{2} + Spur (C_{1} + C_{2} - 2 (C_{2}^{1 / 2} C_{1} C_{2}^{1 / 2})^{1 / 2}) = ‖ m_{1} - m_{2} ‖_{2}^{2} + Spur (C_{1}) + Spur (C_{2}) - 2 Spur ((C_{1} C_{2})^{1 / 2}) .

Dieses Ergebnis verallgemeinert mit $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 $X$ und $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 $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 $W_{p}$ alle Axiome einer Metrik auf $P_{p} (M)$ erfüllt. Zudem ist Konvergenz bezüglich $W_{p}$ äquivalent zur schwachen Konvergenz von Maßen plus die Konvergenz der ersten $p$ Momente.

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

W_{p} (μ, ν) \leq W_{q} (μ, ν) .

Duale Darstellung des W₁

Wenn $μ$ und $ν$ beschränkte Träger haben, dann gilt

W_{1} (μ, ν) = sup {\int_{M} f (x) d (μ - ν) (x) | f : M \to ℝ stetig, L i p (f) \leq 1}

,

wobei $L i p (f)$ die kleinste Lipschitzkonstante von $f$ beschreibt.

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

ρ (μ, ν) := sup {\int_{M} f (x) d (μ - ν) (x) | f : M \to [- 1, 1] stetig}

.

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

2 W_{1} (μ, ν) \leq C ρ (μ, ν)

.

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

Separabilität und Vollständigkeit

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

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 (englisch).
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 (englisch).

Einzelnachweise

1 2 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 (englisch).
↑ 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 (englisch).
↑ 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 (englisch).
↑ 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 (englisch).

[memoli11-1] 1 2 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 (englisch).

[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 (englisch).

[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 (englisch).

[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 (englisch).