Distance de Wasserstein

En mathématiques et plus particulièrement en théorie des probabilités et en statistique, la distance de Wasserstein (ou distance de Kantorovitch, ou distance de Kantorovitch – Rubinstein) est une distance définie entre des mesures de probabilité sur un espace polonais. La plupart des publications en français adoptent l'orthographe allemande Wasserstein pour ce nom russe d'origine allemande.

Liée au problème du transport optimal, plus précisément au travail minimal à fournir pour modifier un tas de terre en un autre, la distance de Wasserstein est parfois appelée distance du cantonnier ou encore distance du terrassier, en anglais : Earth Mover's Distance (EMD). Dans cette métaphore, chaque vecteur est vu comme un tas de terre et la distance reflète un travail : le poids de la terre déplacée multiplié par la distance parcourue. En informatique, cette distance est très utilisée pour la comparaison d'images, notamment dans la recherche d'image par le contenu et dans la reconnaissance de formes.

L'appellation de distance de Wasserstein est due à Roland Dobrouchine en 1970, sa définition ayant été trouvée dans des travaux datant de 1969 du mathématicien russe Léonid Wasserstein (ou Vaseršteĭn). Mais cette distance avait déjà été définie par Léonid Kantorovitch dans son célèbre rapport de 1939 intitulé Méthodes mathématiques pour l'organisation et la planification de la production (en russe : Математические методы организации и планирования производства). Ce rapport avait été présenté et discuté lors d'une réunion de la section de mathématiques et de mécaniques de l'université de Léningrad la même année. Les méthodes en question établissent un cadre formel pour la planification optimale du transport des marchandises et des matériaux. Certains chercheurs encouragent donc plutôt l'utilisation du terme de distance de Kantorovitch.

Définition[modifier | modifier le code]

Définition (distance de Wasserstein) — Soit $({\mathcal {X}},d)$ un espace polonais muni de sa tribu borélienne. Soit $p\in \left[0,+\infty \right[$ et $\mu ,\nu$ deux mesures de probabilités sur ${\mathcal {X}}$ . La distance de Wassertein d'ordre $p$ entre $\mu$ et $\nu$ est

W_{p}(\mu ,\nu ):=\left(\inf _{\pi \in \Pi (\mu ,\nu )}\int _{{\mathcal {X}}\times {\mathcal {X}}}d(x,y)^{p}\mathrm {d} \pi (x,y)\right)^{1/p}

où $\Pi (\mu ,\nu )$ désigne l'ensemble des mesures de probabilités sur ${\mathcal {X}}\times {\mathcal {X}}$ dont les lois marginales sont $\mu$ et $\nu$ .

De manière équivalente, la distance de Wasserstein peut se définir de la manière suivante :

$W_{p}(\mu ,\nu )=\inf \left\{\left(\mathbb {E} \left[d(X,Y)^{p}\right]\right)^{1/p}\,;\,\mathbb {P} _{X}=\mu {\text{ et }}\mathbb {P} _{Y}=\nu \right\}$

où l'infimum est pris sur l'ensemble des couples de variables aléatoires (X, Y) tels que la loi de X est μ et la loi de Y est ν.

La distance de Wasserstein vérifie tous les axiomes d'une distance (symétrie, séparation et inégalité triangulaire) cependant elle peut prendre la valeur infinie. Il est donc courant de restreindre la distance de Wasserstein sur un ensemble où elle prend des valeurs finies.

Définition (espace de Wasserstein) — L'espace de Wasserstein d'ordre $p$ associé à ${\mathcal {X}}$ est défini comme suit

{\mathcal {P}}_{p}({\mathcal {X}}):=\left\{\nu \,;\,\nu {\text{ est une mesure de probabilité telle que }}\int _{\mathcal {X}}d(x_{0},x)^{p}\mathrm {d} \nu (x)<\infty \right\}

où $x_{0}\in {\mathcal {X}}$ est arbitraire.

La définition de ${\mathcal {P}}_{p}({\mathcal {X}})$ ne dépend pas du choix de $x_{0}$ . La distance de Wasserstein restreinte à cet espace est finie dans le sens où pour toutes $\mu ,\nu \in {\mathcal {P}}_{p}({\mathcal {X}}),\,W_{p}(\mu ,\nu )<+\infty$ .

Intuition et lien avec le transport optimal[modifier | modifier le code]

Deux lois unidimensionnelles $\mu$ et $\nu$ , tracées sur les axes x et y, et une loi jointe possible qui définit un plan de transport entre elles. La loi jointe n'est pas unique.

La distance de Wasserstein est liée au problème du transport optimal. Le problème consiste à transformer une mesure finie $\mu$ sur un espace ${\mathcal {X}}$ en une autre mesure finie $\nu$ sur le même espace. Il est fréquent et commode de visualiser les lois $\mu$ et $\nu$ comme deux tas de terre (problème de Monge dans son Mémoire sur les déblais et les remblais). Le but est alors de transformer le tas de terre $\mu$ en un tas de terre $\nu$ . Il faudra pour cela creuser par endroits et éventuellement boucher des trous avec la terre ainsi collectée. En raison de cette analogie, la distance de Wasserstein est parfois appelée, surtout en informatique, distance du cantonnier^[1] ou encore distance du terrassier (Earth Mover's Distance en anglais). Ce déplacement de terre doit se faire, idéalement, de manière optimale, c'est-à-dire en déplaçant le moins de terre possible. En informatique, le problème se ramène généralement à une distribution discrète^[2].

Ce problème n'a de sens que si la pile à créer $\nu$ a la même masse que la pile à déplacer $\mu$ . Il faut donc que $\mu$ et $\nu$ aient la même masse totale. Habituellement on suppose que ces mesures ont une masse totale de 1, ce qui revient à dire que ce sont des mesures de probabilité. Le cas général de mesures finies quelconques s'en déduit alors aisément.

Il reste à préciser ce que le terme « optimal » signifie exactement. Supposons que l'on ait accès à une fonction de coût

c(x,y)\mapsto [0,\infty )

qui donne le coût nécessaire au transport d'une unité de masse depuis le point $x$ jusqu'au point $y$ . Un plan de transport pour transformer $\mu$ en $\nu$ peut être décrit par une fonction $\pi (x,y)$ qui donne la quantité de masse à déplacer de $x$ vers $y$ . Pour que ce plan soit significatif, il doit satisfaire les deux égalités suivantes

{\begin{aligned}\int \pi (x,y)\,\mathrm {d} y=\mu (x)&\qquad {\text{(la quantité de terre déplacée du point }}x{\text{ doit valoir la quantité de terre initiale en ce point)}}\\\int \pi (x,y)\,\mathrm {d} x=\nu (y)&\qquad {\text{(la quantité de terre amenée au point }}y{\text{ doit valoir la quantité finale souhaitée de terre en ce point)}}\end{aligned}}

C'est-à-dire que la masse totale déplacée d'un voisinage infinitésimal autour de $x$ doit être égal à $\mu (x)\mathrm {d} x$ et la masse totale amenée vers un voisinage infinitésimal autour de $y$ doit être égal à $\nu (y)\mathrm {d} y$ . Cela équivaut à exiger que $\pi$ soit une loi de probabilité jointe avec des marginales $\mu$ et $\nu$ . Ainsi, la masse infinitésimale transportée de $x$ à $y$ est $\pi (x,y)\,\mathrm {d} x\,\mathrm {d} y$ , et le coût de ce déplacement est $c(x,y)\pi (x,y)\,\mathrm {d} x\,\mathrm {d} y$ . Par conséquent, le coût total d'un plan de transport $\pi$ est

\iint c(x,y)\pi (x,y)\,\mathrm {d} x\,\mathrm {d} y=\int c(x,y)\,\mathrm {d} \pi (x,y)

.

Le plan de transport $\pi$ n'est pas unique. Le but est de trouver un plan de transport optimal, c'est-à-dire qui minimiserait le coût total donné par la formule ci-dessus. Cette discussion conduit donc naturellement à définir la quantité suivante

C=\inf _{\pi \in \Pi (\mu ,\nu )}\int c(x,y)\,\mathrm {d} \pi (x,y)

où $\Pi (\mu ,\nu )$ est l'ensemble des lois jointes dont les marginales sont $\mu$ et $\nu$ . Si la fonction de coût entre deux points est simplement la distance entre ceux-ci, alors le coût optimal est identique à la définition de la distance de Wasserstein de premier ordre $W_{1}$ .

Exemples[modifier | modifier le code]

Masses ponctuelles[modifier | modifier le code]

Si $\mu _{1}=\delta _{a_{1}}$ et $\mu _{2}=\delta _{a_{2}}$ sont deux masses ponctuelles (c'est-à-dire des mesures de Dirac) situées aux points $a_{1}$ et $a_{2}$ dans $\mathbb {R}$ . Il n'y a qu'un seul couplage possible de ces deux mesures, à savoir la masse ponctuelle $\delta _{(a_{1},a_{2})}$ situé en $(a_{1},a_{2})\in \mathbb {R} ^{2}$ . Ainsi, en utilisant la distance induite par la valeur absolue comme distance sur $\mathbb {R}$ , pour tout $p\geq 1$ , la distance de Wasserstein d'ordre p entre $\mu _{1}$ et $\mu _{2}$ est

W_{p}(\mu _{1},\mu _{2})=|a_{1}-a_{2}|

.

De même si $\mu _{1}=\delta _{a_{1}}$ et $\mu _{2}=\delta _{a_{2}}$ sont des masses ponctuelles situées aux points $a_{1}$ et $a_{2}$ dans $\mathbb {R} ^{n}$ , et si $\mathbb {R} ^{n}$ est muni de la norme euclidienne, alors

W_{p}(\mu _{1},\mu _{2})=\|a_{1}-a_{2}\|_{2}.

Lois normales[modifier | modifier le code]

Soit $\mu _{1}={\mathcal {N}}(m_{1},C_{1})$ et $\mu _{2}={\mathcal {N}}(m_{2},C_{2})$ deux lois normales sur $\mathbb {R} ^{n}$ , de moyennes respectives $m_{1}$ et $m_{2}\in \mathbb {R} ^{n}$ et de matrices de variance-covariance $C_{1}$ et $C_{2}\in \mathbb {R} ^{n\times n}$ . Alors^[3], par rapport à la norme euclidienne usuelle sur $\mathbb {R} ^{n}$ , la distance de Wasserstein d'ordre 2 entre $\mu _{1}$ et $\mu _{2}$ est

W_{2}(\mu _{1},\mu _{2})^{2}=\|m_{1}-m_{2}\|_{2}^{2}+\operatorname {Tr} {\bigl (}C_{1}+C_{2}-2{\bigl (}C_{2}^{1/2}C_{1}C_{2}^{1/2}{\bigr )}^{1/2}{\bigr )}.

où Tr désigne la trace d'une matrice.

Applications[modifier | modifier le code]

La distance de Wasserstein est un moyen naturel de comparer les lois de deux variables aléatoires X et Y, où une variable est dérivée de l'autre par de petites perturbations non uniformes (aléatoires ou déterministes).

En informatique par exemple, la distance W₁ est largement utilisée pour comparer des lois discrètes, par exemple, les histogrammes de couleurs de deux images numériques afin de réaliser une recherche d'image par le contenu ou de façon plus générale, elle est utilisée dans la reconnaissance de motifs pour comparer des signatures de données.

Dans leur article Generative Adversarial Networks, Arjovsky et alii^[4] utilise la distance de Wasserstein d'ordre 1 dans le cadre de réseaux antagonistes génératifs.

La distance de Wasserstein a un lien avec l'analyse procustéenne, avec une application aux mesures de chiralité^[5] et à l'analyse de forme^[6].

Propriétés[modifier | modifier le code]

Structure métrique[modifier | modifier le code]

La distance $W_{p}$ satisfait tous les axiomes d'une distance sur ${\mathcal {P}}_{p}({\mathcal {X}})$ . De plus, la convergence pour cette distance est équivalente à la convergence faible de mesures plus la convergence des premiers p ième moments^[7].

Représentation duale de W₁[modifier | modifier le code]

La représentation duale suivante de W₁ est un cas particulier du théorème de dualité de Kantorovich et Rubinstein (1958)^[8] :

W_{1}(\mu ,\nu )=\sup \left\{\int _{\mathcal {X}}f(x)\,\mathrm {d} (\mu -\nu )(x)\,;\,f:{\mathcal {X}}\to \mathbb {R} {\text{ continue et }}\operatorname {Lip} (f)\leq 1\right\}

où Lip(f) désigne la constante de Lipschitz minimale de f.

Il existe une ressemblance avec la distance de Radon :

\rho (\mu ,\nu ):=\sup \left\{\int _{\mathcal {X}}f(x)\,\mathrm {d} (\mu -\nu )(x)\,;\,f:{\mathcal {X}}\to [-1,1]{\text{ continue}}\right\}

Si la distance d est bornée par une constante C, alors

2W_{1}(\mu ,\nu )\leq C\rho (\mu ,\nu )

et ainsi la convergence pour la distance de Radon (identique à la convergence en variation totale lorsque ${\mathcal {X}}$ est un espace polonais) implique la convergence pour la distance de Wasserstein, mais pas l'inverse.

Équivalence entre W₂ et une norme de Sobolev d'ordre négatif[modifier | modifier le code]

Sous des hypothèses appropriées, la distance de Wasserstein $W_{2}$ d'ordre deux est Lipschitz équivalente à une norme de Sobolev homogène d'ordre négatif^[9]. Plus précisément, si ${\mathcal {X}}$ est une variété riemannienne connexe munie d'une mesure positive $\pi$ , alors on peut définir pour $f\,\colon {\mathcal {X}}\to \mathbb {R}$ la semi-norme

\|f\|_{{\dot {H}}^{1}(\pi )}^{2}=\int |\nabla f(x)|^{2}\,\mathrm {d} \pi

et pour une mesure signée $\mu$ sur ${\mathcal {X}}$ la norme duale

\|\mu \|_{{\dot {H}}^{-1}(\pi )}=\sup {\bigg \{}|\langle f,\mu \rangle |\,;\,\|f\|_{{\dot {H}}^{1}(\pi )}\leq 1{\bigg \}}.

Alors deux mesures de probabilité $\mu$ et $\nu$ sur ${\mathcal {X}}$ satisfont l'inegalité

W_{2}(\mu ,\nu )\leq 2\|\mu -\nu \|_{{\dot {H}}^{-1}(\mu )}.

Inversement, si $\mu$ et $\nu$ ont chacune des densités par rapport à la mesure de volume standard sur ${\mathcal {X}}$ qui sont tous deux délimités au-dessus d'un certain $0<C<\infty$ , et si ${\mathcal {X}}$ a une courbure de Ricci non négative, alors

\|\mu -\nu \|_{{\dot {H}}^{-1}(\mu )}\leq {\sqrt {C}}\,W_{2}(\mu ,\nu ).

Séparabilité et complétude[modifier | modifier le code]

Pour tout $p\geq 1$ , l'espace métrique $({\mathcal {P}}_{p}({\mathcal {X}}),W_{p})$ est séparable, et est complet si $({\mathcal {X}},d)$ est séparable et complet^[10].

Voir également[modifier | modifier le code]

Références[modifier | modifier le code]

Cet article est partiellement ou en totalité issu de l'article intitulé « Distance du terrassier » (voir la liste des auteurs).

↑ Brevet EP 2002378
↑ Définition formelle
↑ Olkin, I. and Pukelsheim, F., « The distance between two random vectors with given dispersion matrices », Linear Algebra Appl., vol. 48,‎ 1982, p. 257–263 (ISSN 0024-3795, DOI 10.1016/0024-3795(82)90112-4)
↑ Martin Arjovsky, Soumith Chintala et Léon Bottou, « Wasserstein Generative Adversarial Networks », ICML,‎ 2017 (lire en ligne)
↑ Petitjean, M., « Chiral mixtures », Journal of Mathematical Physics, vol. 43, n^o 8,‎ 2002, p. 4147–4157 (DOI 10.1063/1.1484559, lire en ligne)
↑ Petitjean, M., « From shape similarity to shape complementarity: toward a docking theory », Journal of Mathematical Chemistry, vol. 35, n^o 3,‎ 2004, p. 147–158 (DOI 10.1023/B:JOMC.0000033252.59423.6b)
↑ Clement et Desch, « An elementary proof of the triangle inequality for the Wasserstein metric », Proceedings of the American Mathematical Society, vol. 136,‎ 2008, p. 333–339 (DOI 10.1090/S0002-9939-07-09020-X, lire en ligne )
↑ ((Dudley, R. M.)), Real Analysis and Probability, Cambridge University Press, coll. « Cambridge Studies in Advanced Mathematics », 2002, 2nd éd. (ISBN 978-0-521-80972-6, DOI 10.1017/CBO9780511755347, lire en ligne), p. 421
↑ Peyre, « Comparison between W₂ distance and Ḣ⁻¹ norm, and localization of Wasserstein distance », ESAIM Control Optim. Calc. Var., vol. 24, n^o 4,‎ 2018, p. 1489–1501 (ISSN 1292-8119, DOI 10.1051/cocv/2017050) (See Theorems 2.1 and 2.5.)
↑ Bogachev et Kolesnikov, A.V., « The Monge–Kantorovich problem: achievements, connections, and perspectives », Russian Math. Surveys, vol. 67, n^o 5,‎ 2012, p. 785–890 (DOI 10.1070/RM2012v067n05ABEH004808)

Liens externes[modifier | modifier le code]

« What is the advantages of Wasserstein metric compared to Kullback–Leibler divergence? », Stack Exchange, 1^er août 2017

[1] Brevet EP 2002378

[2] Définition formelle

[3] Olkin, I. and Pukelsheim, F., « The distance between two random vectors with given dispersion matrices », Linear Algebra Appl., vol. 48,‎ 1982, p. 257–263 (ISSN 0024-3795, DOI 10.1016/0024-3795(82)90112-4)

[4] Martin Arjovsky, Soumith Chintala et Léon Bottou, « Wasserstein Generative Adversarial Networks », ICML,‎ 2017 (lire en ligne)

[5] Petitjean, M., « Chiral mixtures », Journal of Mathematical Physics, vol. 43, n^o 8,‎ 2002, p. 4147–4157 (DOI 10.1063/1.1484559, lire en ligne)

[6] Petitjean, M., « From shape similarity to shape complementarity: toward a docking theory », Journal of Mathematical Chemistry, vol. 35, n^o 3,‎ 2004, p. 147–158 (DOI 10.1023/B:JOMC.0000033252.59423.6b)

[7] Clement et Desch, « An elementary proof of the triangle inequality for the Wasserstein metric », Proceedings of the American Mathematical Society, vol. 136,‎ 2008, p. 333–339 (DOI 10.1090/S0002-9939-07-09020-X, lire en ligne )

[8] ((Dudley, R. M.)), Real Analysis and Probability, Cambridge University Press, coll. « Cambridge Studies in Advanced Mathematics », 2002, 2nd éd. (ISBN 978-0-521-80972-6, DOI 10.1017/CBO9780511755347, lire en ligne), p. 421

[9] Peyre, « Comparison between W₂ distance and Ḣ⁻¹ norm, and localization of Wasserstein distance », ESAIM Control Optim. Calc. Var., vol. 24, n^o 4,‎ 2018, p. 1489–1501 (ISSN 1292-8119, DOI 10.1051/cocv/2017050) (See Theorems 2.1 and 2.5.)

[10] Bogachev et Kolesnikov, A.V., « The Monge–Kantorovich problem: achievements, connections, and perspectives », Russian Math. Surveys, vol. 67, n^o 5,‎ 2012, p. 785–890 (DOI 10.1070/RM2012v067n05ABEH004808)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]