www.wikidata.de-de.nina.az

Wasserstein Metrik Die auch Vaserstein Metrik ist eine Metrik zwischen Wahrscheinlichkeitsmaßen auf einem gegebenen metr

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 Bearbeiten

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

wobei der Träger des Maßes ist.

Beispiele Bearbeiten

Dirac-Maß Bearbeiten

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 Bearbeiten

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:

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 Bearbeiten

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 Bearbeiten

Metrische Struktur Bearbeiten

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

Duale Darstellung des W1 Bearbeiten

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 Bearbeiten

Für jedes ist der metrische Raum separabel und vollständig, wenn separabel und vollständig ist.

Literatur Bearbeiten

  • 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 Bearbeiten

  1. ↑ 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.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Die Wasserstein Metrik auch Vaserstein Metrik ist eine Metrik zwischen Wahrscheinlichkeitsmassen auf einem gegebenen metrischen Raum Intuitiv kann man sich vorstellen Naheres unter optimaler Transport Wenn jede Verteilung als ein Haufen von Erde angehauft 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 Vasersteĭn Wasserstein benannte Vasersteĭn fuhrte das Konzept 1969 ein Inhaltsverzeichnis 1 Definition 2 Beispiele 2 1 Dirac Mass 2 2 Normalverteilung 3 Anwendung 4 Eigenschaften 4 1 Metrische Struktur 4 2 Duale Darstellung des W1 4 3 Separabilitat und Vollstandigkeit 5 Literatur 6 EinzelnachweiseDefinition BearbeitenSei M d displaystyle M d nbsp ein metrischer Raum in dem jedes Wahrscheinlichkeitsmass ein Radonmass auf M displaystyle M nbsp ist auch Radon Raum genannt Fur p 1 displaystyle p geq 1 nbsp sei P p M displaystyle P p M nbsp die Menge aller Wahrscheinlichkeitsmasse m displaystyle mu nbsp auf M displaystyle M nbsp mit endlichem p displaystyle p nbsp ten Moment das heisst fur ein x 0 displaystyle x 0 nbsp aus M displaystyle M nbsp gilt M d x x 0 p d m x lt displaystyle int M d x x 0 p mathrm d mu x lt infty nbsp Dann ist die p displaystyle p nbsp te Wasserstein Distanz zwischen zwei Wahrscheinlichkeitsmassen m displaystyle mu nbsp und n displaystyle nu nbsp aus P p M displaystyle P p M nbsp fur p lt displaystyle p lt infty nbsp definiert als W p m n inf g G m n M M d x y p d g x y 1 p 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 nbsp wobei G m n displaystyle Gamma mu nu nbsp die Menge aller Masse auf M M displaystyle M times M nbsp bezeichnet mit m displaystyle mu nbsp und n displaystyle nu nbsp als Randverteilungen bezuglich des ersten beziehungsweise zweiten Faktors G m n displaystyle Gamma mu nu nbsp wird auch die Menge aller Kopplungen zwischen m displaystyle mu nbsp und n displaystyle nu nbsp genannt Fur p displaystyle p infty nbsp ist die Wasserstein Distanz definiert als W m n inf g G m n sup x y s u p p g d x y displaystyle W infty mu nu inf gamma in Gamma mu nu sup x y in mathrm supp gamma d x y nbsp 1 wobei s u p p g displaystyle mathrm supp gamma nbsp der Trager des Masses ist Beispiele BearbeitenDirac Mass Bearbeiten Seien m d a 1 displaystyle mu delta a 1 nbsp und n d a 2 displaystyle nu delta a 2 nbsp zwei Diracmasse mit a 1 a 2 R displaystyle a 1 a 2 in mathbb R nbsp Dann ist die einzige mogliche Kopplung d a 1 a 2 displaystyle delta a 1 a 2 nbsp Nimmt man nun als Distanzfunktion die Betragsfunktion auf R displaystyle mathbb R nbsp so erhalt man fur jedes beliebige p 1 displaystyle p geq 1 nbsp W p m n a 1 a 2 displaystyle W p mu nu a 1 a 2 nbsp Ist nun a 1 a 2 R n displaystyle a 1 a 2 in mathbb R n nbsp und nimmt man statt der Betragsfunktion den euklidischen Abstand so erhalt man W p m n a 1 a 2 2 displaystyle W p mu nu a 1 a 2 2 nbsp Normalverteilung Bearbeiten Seien m N m 1 C 1 displaystyle mu mathcal N m 1 C 1 nbsp und n N m 2 C 2 displaystyle nu mathcal N m 2 C 2 nbsp zwei Normalverteilungen auf dem R n displaystyle mathbb R n nbsp mit Erwartungswerten m 1 m 2 R n displaystyle m 1 m 2 in mathbb R n nbsp und Kovarianzmatrizen C 1 C 2 R n n displaystyle C 1 C 2 in mathbb R n times n nbsp Nimmt man nun als Distanzfunktion den euklidischen Abstand so lasst sich die 2 Wasserstein Metrik zwischen m displaystyle mu nbsp und n displaystyle nu nbsp als Summe der quadratischen euklidischen Distanz der Mittelwerte und einer Funktion der Kovarianzen ausdrucken W 2 m n 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 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 nbsp 2 3 Dieses Ergebnis verallgemeinert mit p 2 displaystyle p 2 nbsp das vorangegangene Beispiel da das Diracmass als Normalverteilung mit Kovarianzmatrix gleich null betrachtet werden kann Dann entfallen die Spurterme und es bleibt nur der Abstand zwischen den Erwartungswerten Anwendung BearbeitenDie Wasserstein Metrik ist ein naturlicher Weg um die Wahrscheinlichkeitsverteilungen zweier Variablen X displaystyle X nbsp und Y displaystyle Y nbsp zu vergleichen wobei eine Variable von der anderen durch kleine ungleichformige Storungen zufallig oder deterministisch abgeleitet wird In der Informatik ist beispielsweise die Metrik W 1 displaystyle W 1 nbsp weit verbreitet um diskrete Verteilungen zu vergleichen zum Beispiel die Farbhistogramme zweier digitaler Bilder Eigenschaften BearbeitenMetrische Struktur Bearbeiten Es lasst sich zeigen dass W p displaystyle W p nbsp alle Axiome einer Metrik auf P p M displaystyle P p M nbsp erfullt Zudem ist Konvergenz bezuglich W p displaystyle W p nbsp aquivalent zur schwachen Konvergenz von Massen plus die Konvergenz der ersten p displaystyle p nbsp Momente Es gilt fur 1 p q lt displaystyle 1 leq p leq q lt infty nbsp und m n P p M displaystyle mu nu in P p M nbsp W p m n W q m n displaystyle W p mu nu leq W q mu nu nbsp 1 Duale Darstellung des W1 Bearbeiten Wenn m displaystyle mu nbsp und n displaystyle nu nbsp beschrankte Trager haben dann gilt W 1 m n sup M f x d m n x f M R stetig L i p f 1 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 nbsp wobei L i p f displaystyle mathrm Lip f nbsp die kleinste Lipschitzkonstante von f displaystyle f nbsp beschreibt Dies lasst sich mit der Definition der Radon Metrik vergleichen r m n sup M f x d m n x f M 1 1 stetig 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 nbsp Falls die Metrik d displaystyle d nbsp durch C gt 0 displaystyle C gt 0 nbsp beschrankt ist so gilt 2 W 1 m n C r m n displaystyle 2W 1 mu nu leq C rho mu nu nbsp Somit impliziert die Konvergenz in der Radon Metrik die Konvergenz bezuglich W 1 displaystyle W 1 nbsp Die Ruckrichtung gilt im Allgemeinen nicht Separabilitat und Vollstandigkeit Bearbeiten Fur jedes p 1 displaystyle p geq 1 nbsp ist der metrische Raum P p M W p displaystyle P p M W p nbsp separabel und vollstandig wenn M d displaystyle M d nbsp separabel und vollstandig ist 4 Literatur BearbeitenAmbrosio L Gigli N amp Savare G Gradient Flows in Metric Spaces and in the Space of Probability Measures ETH Zurich Birkhauser 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 Bearbeiten a b Facundo Memoli 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 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 Dowson D C and Landau B V The Frechet 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 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 Abgerufen von https de wikipedia org w index php title Wasserstein Metrik amp oldid 237348693