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 $(M,d)$ ein metrischer Raum, in dem jedes Wahrscheinlichkeitsmaß ein Radonmaß auf $M$ ist, auch Radon-Raum genannt. Für $p\ge 1$ sei $P_p(M)$ die Menge aller Wahrscheinlichkeitsmaße $\mu$ auf $M$ mit endlichem $p$-ten Moment, das heißt, für ein $x_0$ aus $M$ gilt

$\underset{M}{\int }d(x,x_0{)}^p\mathrm{d}\mu (x)<\mathrm{\infty }$.

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

$W_p(\mu ,\nu ):={(\underset{\gamma \in \mathrm{\Gamma }(\mu ,\nu )}{\inf }\underset{M\times M}{\int }d(x,y{)}^p\mathrm{d}\gamma (x,y))}^{\frac{1}{p}}$,

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

$W_{\mathrm{\infty }}(\mu ,\nu ):=\underset{\gamma \in \mathrm{\Gamma }(\mu ,\nu )}{\inf }\underset{(x,y)\in \mathrm{s}\mathrm{u}\mathrm{p}\mathrm{p}(\gamma )}{\sup }d(x,y),$

wobei $\mathrm{s}\mathrm{u}\mathrm{p}\mathrm{p}(\gamma )$ der Träger des Maßes ist.

Beispiele

Dirac-Maß

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

$W_p(\mu ,\nu )=|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(\mu ,\nu )=\Vert a_1-a_2{\Vert }_2.$

Normalverteilung

Seien $\mu =𝒩(m_1,C_1)$ und $\nu =𝒩(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 $\mu$ und $\nu$ als Summe der quadratischen euklidischen Distanz der Mittelwerte und einer Funktion der Kovarianzen ausdrücken:

$W_2(\mu ,\nu {)}^2=\Vert m_1-m_2{\Vert }_2^2+\mathrm{Spur}(C_1+C_2-2(C_2^{1/2}{C}_1{C}_2^{1/2}{)}^{1/2})=\Vert m_1-m_2{\Vert }_2^2+\mathrm{Spur}\left(C_1\right)+\mathrm{Spur}\left(C_2\right)-2\mathrm{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\le p\le q<\mathrm{\infty }$ und $\mu ,\nu \in P_p(M)$

$W_p(\mu ,\nu )\le W_q(\mu ,\nu ).$

Duale Darstellung des W₁

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

$W_1(\mu ,\nu )=\sup \{\underset{M}{\int }f(x)\mathrm{d}(\mu -\nu )(x)|f:M\to ℝ\text{ stetig},\mathrm{L}\mathrm{i}\mathrm{p}(f)\le 1\}$,

wobei $\mathrm{L}\mathrm{i}\mathrm{p}(f)$ die kleinste Lipschitzkonstante von $f$ beschreibt.

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

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

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

$2W_1(\mu ,\nu )\le C\rho (\mu ,\nu )$.

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\ge 1$ ist der metrische Raum $(P_p(M),W_p)$ separabel und vollständig, wenn $(M,d)$ separabel und vollständig ist.

Literatur

• Vorlage:Cite book
• Vorlage:Cite journal