Die Gromov-Wasserstein-Metrik ist in der Mathematik eine Distanz zwischen metrischen Räumen, die zusätzlich mit einem Wahrscheinlichkeitsmaß ausgestattet sind. Sie vergleicht die innere metrische Struktur zweier Räume, ohne vorauszusetzen, dass beide Räume Teil eines gemeinsamen Umgebungsraumes sind. Die Distanz ist nach Michail Leonidowitsch Gromow und Leonid Vaseršteĭn benannt und verbindet Konzepte der Gromov-Hausdorff-Konvergenz mit dem optimalen Transport.
Die Gromov-Wasserstein-Distanz wird unter anderem zur Analyse und zum Vergleich von geometrischen Formen, Netzwerken und strukturierten Datensätzen verwendet.
Metrische Maßräume Ein metrischer Maßraum ist ein Tripel
wobei ein metrischer Raum und ein auf definiertes Borelmaß ist. Für die Definition der Gromov-Wasserstein-Distanz werden häufig kompakte metrische Räume und Borel-Wahrscheinlichkeitsmaße mit vollem Träger vorausgesetzt:
Zwei metrische Maßräume und heißen isomorph, wenn eine bijektive Isometrie
existiert, welche zugleich die Maße erhält. Dies bedeutet
für alle und
wobei das Bildmaß von unter bezeichnet.
Kopplungen Seien und Wahrscheinlichkeitsmaße auf beziehungsweise . Eine Kopplung der beiden Maße ist ein Wahrscheinlichkeitsmaß auf dem Produktraum , dessen Randverteilungen und sind.
Die Menge aller Kopplungen wird mit
bezeichnet. Für alle messbaren Mengen und gilt somit
und
Eine Kopplung beschreibt eine möglicherweise nicht eindeutige Zuordnung von Masse zwischen den beiden Räumen.
Definition Seien
und
zwei kompakte metrische Maßräume. Für wird die Gromov-Wasserstein-Distanz der Ordnung durch
definiert.
Der Ausdruck
misst, wie stark sich die Abstände zweier Punkte von den Abständen der ihnen durch die Kopplung zugeordneten Punkte unterscheiden. Die Optimierung erfolgt über sämtliche Kopplungen der beiden Wahrscheinlichkeitsmaße.
Für lautet die Definition
Hierbei bezeichnet den Träger der Kopplung. Äquivalent kann das wesentliche Supremum bezüglich des Produktmaßes verwendet werden.
Der Faktor ist eine Konvention, die der entsprechenden Normierung der Gromov-Hausdorff-Distanz entspricht. In Teilen der Literatur wird die Gromov-Wasserstein-Distanz ohne diesen Faktor definiert.
Eigenschaften Die Gromov-Wasserstein-Distanz ist nichtnegativ und symmetrisch. Außerdem erfüllt sie die Dreiecksungleichung. Für zwei kompakte metrische Maßräume mit voll getragenen Wahrscheinlichkeitsmaßen gilt
genau dann, wenn die beiden Räume durch eine maßerhaltende Isometrie miteinander identifiziert werden können.
Damit definiert eine Metrik auf den Isomorphieklassen kompakter metrischer Maßräume. Auf der Menge der Tripel selbst handelt es sich dagegen nur um eine Pseudometrik, da verschiedene Darstellungen desselben metrischen Maßraumes den Abstand null besitzen können.
Anders als die gewöhnliche Wasserstein-Distanz benötigt die Gromov-Wasserstein-Distanz keine vorgegebene Distanz zwischen einem Punkt aus und einem Punkt aus . Verglichen werden ausschließlich die innerhalb der beiden Räume bestimmten Abstände. Die Distanz ist daher gegenüber Isometrien der einzelnen Räume invariant.
Diskreter Fall Seien und endliche metrische Räume mit den Wahrscheinlichkeitsmaßen
und
wobei sowie
gelten. Eine Kopplung kann dann durch eine nichtnegative Matrix
dargestellt werden. Sie muss die Randbedingungen
erfüllen.
Die Gromov-Wasserstein-Distanz ergibt sich damit als
wobei die Menge aller nichtnegativen Matrizen mit den vorgegebenen Zeilen- und Spaltensummen bezeichnet.
Das Optimierungsproblem ist im Allgemeinen ein nichtkonvexes quadratisches Problem. Im Unterschied zum klassischen diskreten optimalen Transport hängt die Zielfunktion quadratisch von der Kopplungsmatrix ab.
Beispiele Metrischer Maßraum mit einem Punkt Sei
der metrische Maßraum mit genau einem Punkt, wobei gilt. Für einen beliebigen metrischen Maßraum
existiert nur eine Kopplung zwischen und . Daher gilt für
Die Distanz entspricht somit der Hälfte des -ten mittleren paarweisen Abstandes in . Für gilt
wobei den Durchmesser von bezeichnet.
Isometrische Räume Sei eine maßerhaltende Isometrie. Die durch
definierte Kopplung ist auf dem Graphen von konzentriert. Für alle Punkte im Träger dieser Kopplung gilt
Die Verzerrung der Kopplung ist daher null und somit
Berechnung Die exakte Berechnung der diskreten Gromov-Wasserstein-Distanz ist aufgrund der quadratischen und im Allgemeinen nichtkonvexen Zielfunktion aufwendig. Numerische Verfahren bestimmen daher häufig nur lokale Minima oder Näherungslösungen.
Ein verbreiteter Ansatz besteht darin, die Zielfunktion um einen Entropieterm zu ergänzen. Die entropische Regularisierung erleichtert die numerische Optimierung und ermöglicht iterative Verfahren, die mit Methoden des regularisierten optimalen Transports verwandt sind. Der erhaltene Wert stimmt jedoch im Allgemeinen nicht exakt mit der unregularisierten Gromov-Wasserstein-Distanz überein.
Weitere Berechnungsverfahren beruhen unter anderem auf bedingten Gradientenverfahren, Fixpunktiterationen, stochastischen Näherungen und hierarchischen Verfahren.
Untere Schranken Da die unmittelbare Berechnung der Gromov-Wasserstein-Distanz im diskreten Fall ein im Allgemeinen nichtkonvexes quadratisches Optimierungsproblem erfordert, werden zur schnellen Abschätzung verschiedene untere Schranken verwendet. Diese beruhen auf Invarianten metrischer Maßräume, die ohne eine vollständige Zuordnung ihrer Punkte verglichen werden können.
Eine einfache untere Schranke ergibt sich aus dem -statistischen Durchmesser
Für zwei metrische Maßräume und gilt
Unterscheiden sich die mittleren inneren Abstände der beiden Räume deutlich, so können die Räume folglich auch hinsichtlich der Gromov-Wasserstein-Distanz nicht nahe beieinanderliegen.
Eine stärkere Schranke berücksichtigt die vollständige Verteilung der paarweisen Abstände. Dazu wird das Produktmaß durch die Distanzfunktion
auf die nichtnegativen reellen Zahlen übertragen. Die daraus entstehende Distanzverteilung ist
Entsprechend wird definiert. Zwischen den Distanzverteilungen gilt die untere Schranke
wobei die Wasserstein-Metrik der Ordnung auf bezeichnet. Da hierbei lediglich eindimensionale Verteilungen verglichen werden, ist diese Schranke wesentlich einfacher zu berechnen als die Gromov-Wasserstein-Distanz selbst. Sie kann jedoch den Wert null annehmen, obwohl die zugrunde liegenden metrischen Maßräume nicht isomorph sind, da verschiedene Räume dieselbe Verteilung paarweiser Abstände besitzen können.
Eine weitere Verfeinerung verwendet lokale Distanzverteilungen. Für jeden Punkt wird
definiert. Dieses Maß beschreibt die Verteilung der Abstände von zu den übrigen Punkten des Raumes. Für und wird daraus die Kostenfunktion
gebildet. Dann gilt
Diese Schranke berücksichtigt, wie ähnlich die Abstandsprofile einzelner Punkte sind. Sie ist mindestens so stark wie die Schranke durch die globalen Distanzverteilungen und kann im endlichen Fall als lineares optimales Transportproblem formuliert werden.
Gromov-Wasserstein-Schwerpunkte Ein Gromov-Wasserstein-Schwerpunkt oder Gromov-Wasserstein-Baryzentrum ist ein metrischer Maßraum, der eine Menge gegebener metrischer Maßräume hinsichtlich ihrer Gromov-Wasserstein-Distanzen zusammenfasst. Für metrische Maßräume und Gewichte mit
wird ein Baryzentrum formal als Lösung des Optimierungsproblems
definiert.
Im diskreten Fall können solche Baryzentren verwendet werden, um mehrere Distanz- oder Kernelmatrizen unterschiedlicher Größe zusammenzufassen, ohne dass eine vorherige punktweise Zuordnung zwischen den Matrizen erforderlich ist.
Anwendungen Die Gromov-Wasserstein-Distanz eignet sich insbesondere für den Vergleich von Objekten, deren Elemente nicht unmittelbar in einem gemeinsamen Merkmalsraum liegen. Zu den untersuchten Anwendungen gehören:
der Vergleich und die Zuordnung geometrischer Formen, die Analyse von Graphen und Netzwerken, der Vergleich von Distanz- und Kernelmatrizen, die Berechnung struktureller Baryzentren, die Angleichung unterschiedlich dargestellter Datensätze, Verfahren des maschinellen Lernens und der Computer Vision.
Bei einer Formanalyse können die Punkte zweier Oberflächen beispielsweise unterschiedliche Koordinatensysteme oder unterschiedliche Anzahlen von Abtastpunkten besitzen. Die Gromov-Wasserstein-Distanz vergleicht in diesem Fall die paarweisen geodätischen oder euklidischen Abstände innerhalb der jeweiligen Form.
In der Bioinformatik wurde eine Näherung der Gromov-Wasserstein-Distanz verwendet, um Proteinoberflächen anhand ihrer elektrostatischen Eigenschaften zu vergleichen. Dabei wurde die Ähnlichkeit der elektrostatischen Isopotentialflächen verschiedener Thioredoxine und Glutaredoxine. untersucht Die Analyse diente dazu, Zusammenhänge zwischen der räumlichen Verteilung elektrostatischer Eigenschaften und der Substratspezifität der Proteine zu untersuchen.
Varianten Neben der klassischen Gromov-Wasserstein-Distanz wurden verschiedene Erweiterungen eingeführt.
Die Fused-Gromov-Wasserstein-Distanz berücksichtigt neben der inneren metrischen Struktur auch Merkmale, die unmittelbar zwischen Punkten der beiden Räume verglichen werden können. Dadurch lassen sich beispielsweise attributierte Graphen behandeln.
Bei der unbalancierten Gromov-Wasserstein-Distanz müssen die beiden Maße nicht dieselbe Gesamtmasse besitzen. Abweichungen von den Randbedingungen werden dabei durch zusätzliche Divergenzterme bewertet.
Die partielle Gromov-Wasserstein-Distanz transportiert nur einen Teil der vorhandenen Masse. Sie kann eingesetzt werden, wenn die zu vergleichenden Räume nur teilweise übereinstimmen oder Ausreißer enthalten.
Abgrenzung zu verwandten Distanzen Die Wasserstein-Metrik vergleicht zwei Wahrscheinlichkeitsmaße auf demselben metrischen Raum oder auf Räumen, zwischen deren Punkten eine Transportkostenfunktion definiert ist. Die Gromov-Wasserstein-Distanz benötigt dagegen nur die beiden internen Distanzfunktionen.
Die Gromov-Hausdorff-Distanz vergleicht kompakte metrische Räume unabhängig von einem Maß. Die Gromov-Wasserstein-Distanz berücksichtigt zusätzlich die Verteilung der Masse innerhalb der Räume. Bereiche mit geringer oder verschwindender Masse beeinflussen die Gromov-Wasserstein-Distanz entsprechend weniger oder werden bei nicht voll getragenen Maßen nicht erfasst.
Weblinks Einführung und Software zum optimalen Transport auf der Internetseite der Python Optimal Transport Toolbox
Einzelnachweise
Kategorie:Metrischer Raum