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.

Pour les articles homonymes, voir EMD.

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

Définition (distance de Wasserstein)  Soit un espace polonais muni de sa tribu borélienne. Soit et deux mesures de probabilités sur . La distance de Wassertein d'ordre entre et est

désigne l'ensemble des mesures de probabilités sur dont les lois marginales sont et .

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

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 associé à est défini comme suit

est arbitraire.

La définition de ne dépend pas du choix de . La distance de Wasserstein restreinte à cet espace est finie dans le sens où pour toutes .

Intuition et lien avec le transport optimal

Deux lois unidimensionnelles et , 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 sur un espace en une autre mesure finie sur le même espace. Il est fréquent et commode de visualiser les lois et 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 en un tas de terre . 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 a la même masse que la pile à déplacer . Il faut donc que et 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

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

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

.

Le plan de transport 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

est l'ensemble des lois jointes dont les marginales sont et . 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 .

Exemples

Masses ponctuelles

Si et sont deux masses ponctuelles (c'est-à-dire des mesures de Dirac) situées aux points et dans . Il n'y a qu'un seul couplage possible de ces deux mesures, à savoir la masse ponctuelle situé en . Ainsi, en utilisant la distance induite par la valeur absolue comme distance sur , pour tout , la distance de Wasserstein d'ordre p entre et est

.

De même si et sont des masses ponctuelles situées aux points et dans , et si est muni de la norme euclidienne, alors

Lois normales

Soit et deux lois normales sur , de moyennes respectives et et de matrices de variance-covariance et . Alors[3], par rapport à la norme euclidienne usuelle sur , la distance de Wasserstein d'ordre 2 entre et est

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

Applications

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 W1 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

Structure métrique

La distance satisfait tous les axiomes d'une distance sur . 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 W1

La représentation duale suivante de W1 est un cas particulier du théorème de dualité de Kantorovich et Rubinstein (1958) : si μ et ν ont un support borné, alors

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

Il existe une ressemblance avec la distance de Radon :

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

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

Équivalence entre W2 et une norme de Sobolev d'ordre négatif

Sous des hypothèses appropriées, la distance de Wasserstein d'ordre deux est Lipschitz équivalente à une norme de Sobolev homogène d'ordre négatif[8] . Plus précisément, si est une variété riemannienne connexe munie d'une mesure positive , alors on peut définir pour la semi-norme

et pour une mesure signée sur la norme duale

Alors deux mesures de probabilité et sur satisfont l'inegalité

Inversement, si et ont chacune des densités par rapport à la mesure de volume standard sur qui sont tous deux délimités au-dessus d'un certain , et si a une courbure de Ricci non négative, alors

Séparabilité et complétude

Pour tout , l'espace métrique est séparable, et est complet si est séparable et complet[9].

Voir également

Références

  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, , 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, (lire en ligne)
  5. Petitjean, M., « Chiral mixtures », Journal of Mathematical Physics, vol. 43, no 8, , 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, no 3, , 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, , p. 333–339 (DOI 10.1090/S0002-9939-07-09020-X, lire en ligne )
  8. Peyre, « Comparison between W2 distance and 1 norm, and localization of Wasserstein distance », ESAIM Control Optim. Calc. Var., vol. 24, no 4, , p. 1489–1501 (ISSN 1292-8119, DOI 10.1051/cocv/2017050) (See Theorems 2.1 and 2.5.)
  9. Bogachev et Kolesnikov, A.V., « The Monge–Kantorovich problem: achievements, connections, and perspectives », Russian Math. Surveys, vol. 67, no 5, , p. 785–890 (DOI 10.1070/RM2012v067n05ABEH004808)

Liens externes


  • Portail des mathématiques
  • Portail de l'informatique théorique
  • Portail de l’imagerie numérique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.