scipy.stats.

wasserstein_distance_nd#

scipy.stats.wasserstein_distance_nd(u_values, v_values, u_weights=None, v_weights=None)[Quelle]#

Berechnet die Wasserstein-1-Distanz zwischen zwei N-D-diskreten Verteilungen.

Die Wasserstein-Distanz, auch bekannt als Earth Mover's Distance oder optimale Transportdistanz, ist eine Ähnlichkeitsmetrik zwischen zwei Wahrscheinlichkeitsverteilungen [1]. Im diskreten Fall kann die Wasserstein-Distanz als Kosten für einen optimalen Transportplan verstanden werden, um eine Verteilung in die andere umzuwandeln. Die Kosten werden als Produkt der zu bewegenden Wahrscheinlichkeitsmasse und der zurückzulegenden Distanz berechnet. Eine kurze und intuitive Einführung finden Sie unter [2].

Hinzugefügt in Version 1.13.0.

Parameter:
u_values2d array_like

Eine Stichprobe aus einer Wahrscheinlichkeitsverteilung oder die Trägerdichte (Menge aller möglichen Werte) einer Wahrscheinlichkeitsverteilung. Jedes Element entlang Achse 0 ist eine Beobachtung oder ein möglicher Wert, und Achse 1 repräsentiert die Dimensionalität der Verteilung; d. h., jede Zeile ist eine Vektorbeobachtung oder ein möglicher Wert.

v_values2d array_like

Eine Stichprobe aus oder die Trägerdichte einer zweiten Verteilung.

u_weights, v_weights1d array_like, optional

Gewichte oder Zählungen, die den Stichproben- oder Wahrscheinlichkeitsmassen entsprechen, die den Trägerdichten zugeordnet sind. Die Summe der Elemente muss positiv und endlich sein. Wenn nicht angegeben, wird jedem Wert das gleiche Gewicht zugewiesen.

Rückgabe:
distancefloat

Die berechnete Distanz zwischen den Verteilungen.

Siehe auch

wasserstein_distance

Berechnet die Wasserstein-1-Distanz zwischen zwei 1D-diskreten Verteilungen.

Hinweise

Gegeben zwei Wahrscheinlichkeitsmassenfunktionen, \(u\) und \(v\), ist die erste Wasserstein-Distanz zwischen den Verteilungen unter Verwendung der Euklidischen Norm

\[l_1 (u, v) = \inf_{\pi \in \Gamma (u, v)} \int \| x-y \|_2 \mathrm{d} \pi (x, y)\]

wobei \(\Gamma (u, v)\) die Menge der (Wahrscheinlichkeits-)Verteilungen auf \(\mathbb{R}^n \times \mathbb{R}^n\) ist, deren Randverteilungen \(u\) und \(v\) auf dem ersten bzw. zweiten Faktor sind. Für einen gegebenen Wert \(x\) gibt \(u(x)\) die Wahrscheinlichkeit von \(u\) an der Position \(x\) an, und dasselbe gilt für \(v(x)\).

Dies wird auch als das Problem des optimalen Transports oder das Monge-Problem bezeichnet. Sei \(\{x_i\}\) und \(\{y_j\}\) die Menge endlicher Punkte, die die Trägerdichte der Wahrscheinlichkeitsmassenfunktion \(u\) bzw. \(v\) bezeichnen. Das Monge-Problem kann wie folgt ausgedrückt werden:

Sei \(\Gamma\) der Transportplan, \(D\) die Distanzmatrix und,

\[\begin{split}x = \text{vec}(\Gamma) \\ c = \text{vec}(D) \\ b = \begin{bmatrix} u\\ v\\ \end{bmatrix}\end{split}\]

Die Funktion \(\text{vec}()\) bezeichnet die Vektorisierungsfunktion, die eine Matrix in einen Spaltenvektor umwandelt, indem die Spalten der Matrix vertikal gestapelt werden. Der Transportplan \(\Gamma\) ist eine Matrix \([\gamma_{ij}]\), in der \(\gamma_{ij}\) ein positiver Wert ist, der die von \(u(x_i)\) nach \(v(y_i)\) transportierte Wahrscheinlichkeitsmasse darstellt. Die Summe über die Zeilen von \(\Gamma\) sollte die Quellverteilung \(u\) ergeben: \(\sum_j \gamma_{ij} = u(x_i)\) gilt für alle \(i\), und die Summe über die Spalten von \(\Gamma\) sollte die Zielverteilung \(v\) ergeben: \(\sum_i \gamma_{ij} = v(y_j)\) gilt für alle \(j\). Die Distanzmatrix \(D\) ist eine Matrix \([d_{ij}]\), in der \(d_{ij} = d(x_i, y_j)\).

Gegeben \(\Gamma\), \(D\), \(b\), kann das Monge-Problem durch die Verwendung von \(A x = b\) als Nebenbedingungen und \(z = c^T x\) als Minimierungsziel (Summe der Kosten) in ein lineares Optimierungsproblem umgewandelt werden, wobei die Matrix \(A\) folgende Form hat:

\[ \begin{align}\begin{aligned}\begin{array} {rrrr|rrrr|r|rrrr} 1 & 1 & \dots & 1 & 0 & 0 & \dots & 0 & \dots & 0 & 0 & \dots & 0 \cr 0 & 0 & \dots & 0 & 1 & 1 & \dots & 1 & \dots & 0 & 0 &\dots & 0 \cr \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \cr 0 & 0 & \dots & 0 & 0 & 0 & \dots & 0 & \dots & 1 & 1 & \dots & 1 \cr \hline\\ 1 & 0 & \dots & 0 & 1 & 0 & \dots & \dots & \dots & 1 & 0 & \dots & 0 \cr 0 & 1 & \dots & 0 & 0 & 1 & \dots & \dots & \dots & 0 & 1 & \dots & 0 \cr \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \cr 0 & 0 & \dots & 1 & 0 & 0 & \dots & 1 & \dots & 0 & 0 & \dots & 1 \end{array}\end{aligned}\end{align} \]

Durch die Lösung der dualen Form des obigen linearen Optimierungsproblems (mit der Lösung \(y^*\)) kann die Wasserstein-Distanz \(l_1 (u, v)\) als \(b^T y^*\) berechnet werden.

Die obige Lösung ist inspiriert von Vincent Herrmanns Blog [3]. Eine ausführlichere Erklärung finden Sie unter [4].

Die Eingangsverteilungen können empirisch sein, also aus Stichproben stammen, deren Werte effektiv Eingaben der Funktion sind, oder sie können als verallgemeinerte Funktionen betrachtet werden, in welchem Fall sie gewichtete Summen von Dirac-Delta-Funktionen sind, die an den angegebenen Werten lokalisiert sind.

Referenzen

[2]

Lili Weng, „What is Wasserstein distance?“, Lil’log, https://lilianweng.github.io/posts/2017-08-20-gan/#what-is-wasserstein-distance.

[3]

Hermann, Vincent. „Wasserstein GAN and the Kantorovich-Rubinstein Duality“. https://vincentherrmann.github.io/blog/wasserstein/.

[4]

Peyré, Gabriel und Marco Cuturi. „Computational optimal transport.“ Center for Research in Economics and Statistics Working Papers 2017-86 (2017).

Beispiele

Berechnet die Wasserstein-Distanz zwischen zwei dreidimensionalen Stichproben mit jeweils zwei Beobachtungen.

>>> from scipy.stats import wasserstein_distance_nd
>>> wasserstein_distance_nd([[0, 2, 3], [1, 2, 5]], [[3, 2, 3], [4, 2, 5]])
3.0

Berechnet die Wasserstein-Distanz zwischen zwei zweidimensionalen Verteilungen mit drei bzw. zwei gewichteten Beobachtungen.

>>> wasserstein_distance_nd([[0, 2.75], [2, 209.3], [0, 0]],
...                      [[0.2, 0.322], [4.5, 25.1808]],
...                      [0.4, 5.2, 0.114], [0.8, 1.5])
174.15840245217169
Auf dieser Seite