Le transport optimal numérique et ses applications - Partie 2

Le transport de Kantorovitch

Piste noire Le 4 juin 2019  - Ecrit par  Gabriel Peyré Voir les commentaires

Cet article fait suite à cet article sur le problème de transport de Monge. Il explique la reformulation proposée par Leonid Kantorovitch pendant la seconde guerre mondiale. Cette reformulation se prête à une analyse mathématique poussée ainsi qu’à son application à de nombreux problèmes. Elle fait du transport optimal un outil de choix pour aborder l’explosion récente de la science des données.

$\newcommand{\Blu}[1]{{\color{blue}#1}} \newcommand{\Red}[1]{{\color{red}#1}} \newcommand{\iC}{\Red{i}} \newcommand{\jC}{\Blu{j}} \newcommand{\aC}{\Red{a}} \newcommand{\bC}{\Blu{b}} \newcommand{\si}{s} \newcommand{\Si}{S} \newcommand{\eq}[1]{\begin{equation*}#1\end{equation*}} \newcommand{\eql}[1]{\begin{equation}#1\end{equation}} \newcommand{\eqdef}{\overset{\Delta}{=}} \renewcommand{\eqdef}{:=} \newcommand{\umin}[1]{\underset{#1}{\min}\;} \newcommand{\RR}{\mathbb{R}} \newcommand{\Pp}{\mathcal{P}} \newcommand{\Bb}{\mathcal{B}} \newcommand{\norm}[1]{|\!| #1 |\!|} \newcommand{\enscond}[2]{ \left\{ #1 \;:\; #2 \right\} } $

Leonid Kantorovitch est un mathématicien et économiste soviétique qui a révolutionné la théorie du transport optimal pendant les années 40. Ses recherches sont issues de considérations pratiques qui l’ont occupé avant et après la seconde guerre mondiale. Il y a joué un rôle important pour assurer une distribution optimale des ressources, en particulier durant le siège de Léningrad. Il a par la même occasion participé au développement de l’optimisation moderne, laquelle a eu un impact énorme dans de très nombreux domaines appliqués. Il a ainsi obtenu en 1975 le prix Nobel d’économie, car les premières applications (mais certainement pas les seules !) de sa théorie se sont manifestées dans ce domaine.

Le problème de Kantorovitch

Le problème de Monge [1], détaillé dans la première partie consiste à chercher la permutation $\si \in \Si_n$ qui a un coût minimum. Ceci signifie que l’on dispose d’une matrice de coût $(C_{\Red{i},\Blu{j}})_{\Red{i},\Blu{j}=1}^n$ (par exemple des temps de trajet entre des points), et on souhaite résoudre le problème d’optimisation
\[\begin{equation}\label{eq:monge} \umin{\si \in \Si_n} \text{Coût}(\si) \eqdef \sum_{\Red{i}} C_{\Red{i},\si(\Red{i})} \end{equation}\]

L’idée centrale de Kantorovitch [2] est de modifier le problème de Monge en remplaçant l’ensemble des permutations par un ensemble plus grand mais plus simple. Tout d’abord on remarque que l’on peut représenter une permutation $\si \in \Si_n$ à l’aide d’une matrice de permutation $P$ qui est une matrice binaire (remplie de 0 et de 1) de taille $n \times n$ telle que $P_{\iC,\jC} = 0$ sauf si $\jC=\si(\iC)$ auquel cas $P_{\iC,\si(\iC)} = 1$. Par exemple, pour $n=3$ points, les permutations
$(\Red{1},\Red{2},\Red{3}) \mapsto (\Blu{1},\Blu{2},\Blu{3})$ (l’identité),
$(\Red{1},\Red{2},\Red{3}) \mapsto (\Blu{3},\Blu{2},\Blu{1})$ et
$(\Red{1},\Red{2},\Red{3}) \mapsto (\Blu{2},\Blu{1},\Blu{3})$ sont représentées par les matrices de taille $3 \times 3$
\[\begin{equation*} \begin{pmatrix} 1&0&0 \\ 0&1&0 \\ 0&0&1 \end{pmatrix}, \quad \begin{pmatrix} 0&0&1 \\ 0&1&0 \\ 1&0&0 \end{pmatrix} \quad\text{et}\quad \begin{pmatrix} 0&1&0 \\ 1&0&0 \\ 0&0&1 \end{pmatrix}. \end{equation*}\]
Dans la suite, on note $\Pp_n$ l’ensemble des $n!$ matrices de permutation de taille $n \times n$.

Comme la matrice est binaire, avec seulement $n$ éléments non-nuls égaux à 1, on peut remplacer la somme de $n$ termes qui apparait dans $\text{Coût}(\si)$ défini en ($\ref{eq:monge}$) par une somme sur l’ensemble des $n \times n$ indices $(\iC,\jC)$, c’est-à-dire que si $P$ est la matrice de permutation associée à $\si$, on a
\[\begin{equation*} \text{Coût}(\si) = \sum_{\iC=1}^n \sum_{\jC=1}^n P_{\iC,\jC} C_{\iC,\jC}. \end{equation*}\]
On peut ainsi remplacer le problème de Monge ($\ref{eq:monge}$) par le problème équivalent
\[\begin{equation}\label{eq:mongematrix} \umin{P \in \Pp_n} \sum_{\iC=1}^n \sum_{\jC=1}^n P_{\iC,\jC} C_{\iC,\jC}. \end{equation}\]

Le génie de Kantorovitch a été de remarquer que l’on peut remplacer l’ensemble discret $\Pp_n$ (c’est-à-dire composé d’un ensemble fini, mais très grand, de $n!$ matrices) par un ensemble « continu » (donc en particulier infini) mais plus simple. On remarque en effet que les matrices de permutation de $\Pp_n$ sont exactement les matrices qui ont un et un seul 1 le long de chaque ligne et de chaque colonne. Ceci peut aussi s’exprimer comme le fait qu’une matrice de permutation est une matrice binaire dont la somme de chaque ligne et de chaque colonne vaut 1, c’est-à-dire
\[\begin{equation*} \Pp_n = \enscond{ P \in \{0,1\}^{n \times n} }{ \forall \iC, \sum_{\jC} P_{\iC,\jC}=1, \forall \jC, \sum_{\iC} P_{\iC,\jC}=1 }. \end{equation*}\]
Ce qui rend cet ensemble très compliqué, c’est la contrainte binaire, c’est-à-dire que ces matrices sont contraintes à être dans $\{0,1\}^{n \times n}$. Kantorovitch propose alors de « relaxer » cette contrainte en supposant simplement que les entrées de $P$ sont entre $0$ et $1$. Ceci définit un ensemble plus grand, l’ensemble des matrices bistochastiques
\[\begin{equation}\label{eq:bistoch} \Bb_n \eqdef \enscond{ P \in [0,1]^{n \times n} }{ \forall \iC, \sum_{\jC} P_{\iC,\jC}=1, \forall \jC, \sum_{\iC} P_{\iC,\jC}=1 }. \end{equation}\]
Le problème de Kantorovitch s’obtient en effectuant ce remplacement dans ($\ref{eq:mongematrix}$), afin de résoudre
\[\begin{equation}\label{eq:kantoassign} \umin{P \in \Bb_n} \sum_{\iC=1}^n \sum_{\jC=1}^n P_{\iC,\jC} C_{\iC,\jC}. \end{equation}\]
L’immense avantage du problème de Kantorovitch ($\ref{eq:kantoassign}$) par rapport à celui de Monge ($\ref{eq:mongematrix}$) est que l’ensemble des matrices bistochastiques est convexe, c’est-à-dire que si l’on considère deux matrices bistochastiques $P,Q \in \Bb_n$, alors toutes les moyennes $(1-t) P+t Q \in \Bb_n$ sont encore bistochastiques pour $t \in [0,1]$. Ceci n’est pas vrai pour les matrices de permutation, puisque la moyenne de deux matrices binaires $(P,Q)$ n’est pas binaire (sauf bien sûr si $P=Q$). Cette convexité est la clef pour le développement d’algorithmes efficaces.
Cette nouvelle formulation a en effet pu bénéficier d’une deuxième révolution initiée par George Dantzig [3], qui, à la même époque, a proposé l’algorithme du simplexe. Celui-ci permet de résoudre efficacement une certaine classe de problèmes d’optimisation convexe : les problèmes de programmation linéaire, dont ($\ref{eq:kantoassign}$) est un cas particulier. Dans le cas du problème de Kantorovitch, il existe en effet un algorithme du simplexe qui a une complexité de l’ordre de $n^3$ opérations, ce qui permet de faire des calculs pour de grands $n$, de l’ordre de plusieurs milliers.
Par exemple, pour $n=20$, un algorithme du simplexe (de complexité $n^3$) prend environ 0.01s, alors qu’une recherche exhaustive des $n!$ possibilités prendrait de l’ordre de 100000 années.

L’équivalence Monge-Kantorovitch

L’ensemble des matrices bistochastiques est plus grand que celui des matrices de permutations, $\Pp_n \subset \Bb_n$, de sorte que l’on a l’inégalité
\[\begin{equation}\label{eq:monge-vs-kanto} \umin{P \in \Bb_n} \sum_{\iC=1}^n \sum_{\jC=1}^n P_{\iC,\jC} C_{\iC,\jC} \leq \umin{P \in \Pp_n} \sum_{\iC=1}^n \sum_{\jC=1}^n P_{\iC,\jC} C_{\iC,\jC} \end{equation}\]
entre les problèmes de Kantorovitch et de Monge. Mais de façon à première vue surprenante, un théorème fondamental dû à George Birkhoff [4] et à John von Neumann [5] assure qu’en fait il y a égalité entre les valeurs de ces deux minimisations. En effet, ce théorème montre qu’il existe toujours une matrice solution du problème de Kantorovitch qui est une matrice de permutation, de sorte qu’elle est aussi solution du problème de Monge. Attention cependant, en général il n’y a pas unicité des solutions de ces problèmes : il peut exister une matrice bistochastique solution du problème de Kantorovitch qui n’est pas une permutation.
La conjonction de deux avancées spectaculaires, dues à Kantorovitch et à Dantzig, a permis de rendre le transport optimal applicable à des problèmes de grande taille, puisque l’algorithme du simplexe permet de résoudre en pratique ces problèmes.

Le cas pondéré

Outre son intérêt pratique, la formulation de Kantorovitch a aussi permis de généraliser le problème initial de Monge, en donnant le bon cadre pour le formaliser et l’étudier mathématiquement. En effet, le problème de Monge est très limité. Que se passe-t-il par exemple si il n’y pas le même nombre $n$ de cafés et $m$ de boulangeries ? Le problème initial ($\ref{eq:monge}$) n’a pas de solution, car on ne peut pas mettre en bijection deux ensembles de tailles différentes. Le bon concept n’est pas le nombre de boulangeries et de cafés, mais plutôt les distributions $(\Red{a_1},\ldots,\Red{a_n})$ de production (associées au boulangeries) et les distributions $(\Blu{b_1},\ldots,\Blu{b_m})$ de consommation des cafés.
Par exemple, si la première boulangerie produit 45 croissants par jour, on prendra $\Red{a_1} =45$, de même $\Blu{b_3} = 34$ signifie que le 3$^\text{e}$ café consomme 34 croissants par jour.
Dans le cas initialement considéré, où $n=m$, toutes les quantités $\Red{a_i}$ et $\Blu{b_j}$ sont égales. Mais dans de nombreux cas concrets, ces quantités sont quelconques. Ces quantités doivent être positives, et vérifier
\[\begin{equation*} \Red{a_1}+\cdots+\Red{a_n} = \Blu{b_1} + \cdots + \Blu{b_m}, \end{equation*}\]
de sorte qu’il y ait autant de production que de consommation. La construction de Kantorovitch s’adapte naturellement à ce cas de distributions générales, en remplaçant les matrices bistochastiques $(\ref{eq:bistoch})$ par des matrices de « couplage » qui satisfont la contrainte de conservation de la masse
\[\begin{equation*} \Bb(\aC,\bC) \eqdef \enscond{ P \in \RR_+^{n \times m} }{ \forall \iC, \sum_{\jC} P_{\iC,\jC}=\Red{a_i}, \forall \jC, \sum_{\iC} P_{\iC,\jC}= \Blu{b_j} }. \end{equation*}\]
Dans le cas initial où $n=m$ et $\Red{a_i}=\Blu{b_j}=1$, alors $\Bb(\aC,\bC) = \Bb_n$ et l’on retrouve des matrices bistochastiques. Dans le cas général, à chaque fois qu’une entrée $P_{\iC,\jC}$ est non-nulle, ceci signifie que l’on transfert de la « masse » (ici une certaine quantité de croissants) entre $\iC$ et $\jC$. Comme le montre la figure suivante, on peut visualiser de différentes façons une telle matrice $P$ couplant deux distributions $(\aC,\bC)$.
Contrairement au cas des matrices bistochastiques, pour lequel il y a toujours une solution qui est une permutation, ici un couplage optimal $\Bb(\aC,\bC)$ peut avoir plus d’une seule entrée non-nulle $P_{\iC,\jC}$ le long d’une ligne indexée par $\iC$ (voir la figure suivante). Ceci signifie que cette boulangerie $\iC$ est connectée à plusieurs cafés, de sorte que sa production est alors séparée en plusieurs lots de croissants distribués, tout en satisfaisant la contrainte de conservation de la masse $\sum_{\jC} P_{\iC,\jC}=\Red{a_i}$.

La figure suivante montre différentes façons de représenter une matrice de couplage $P \in \Bb(\aC,\bC)$ :

  • (a) un tableau de nombres dont les lignes et colonnes ont des sommes prescrites ;
  • (b) un histogramme bidimensionnel dont la taille de carré est proportionnelle à $P_{\iC,\jC}$ ;
  • (c) un ensemble de segments dont la largeur est proportionnelle à $P_{\iC,\jC}$.
  • (d) un graphe biparti, c’est-à-dire avec deux groupes de points reliés par des arrêtes.
(a) matrice (b) histogrammes (c) segments (d) graphe biparti

Le problème de Kantorovitch qui généralise ($\ref{eq:kantoassign}$) s’écrit alors
\[\begin{equation}\label{eq-kanto-gen} \umin{P \in \Bb(\aC,\bC)} \sum_{\iC=1}^n \sum_{\jC=1}^m P_{\iC,\jC} C_{\iC,\jC} \end{equation}\]
ce qui signifie que l’on doit payer un coût $C_{\iC,\jC}$ à chaque fois que l’on transfert une unité de masse entre $\iC$ et $\jC$. Tout comme le problème original ($\ref{eq:kantoassign}$), on peut le résoudre de façon efficace avec l’algorithme du simplexe. La figure précédente montre un exemple de couplage optimal.

Les applications

La première partie de cet article a illustré l’utilisation du transport optimal pour la modification des couleurs d’une image.

On peut également utiliser le transport optimal pour des problèmes plus difficiles [6], en n’utilisant que de façon indirecte la permutation $\si$ ou bien la matrice de couplage optimal $P \in \Bb(\aC,\bC)$. L’idée centrale est que la quantité associée à un couplage optimal $P$ solution de ($\ref{eq-kanto-gen}$)
\[\begin{equation*} W(\aC,\bC) \eqdef \sum_{i,j} P_{\iC,\jC} C_{\iC,\jC} \end{equation*}\]
définit en quelque sorte l’effort nécessaire pour déplacer la masse de la distribution $\aC$ vers la distribution $\bC$. Elle permet donc de quantifier combien ces deux distributions sont « proches ». Par exemple, si $C_{\iC,\jC} = \norm{\Red{x_i} - \Blu{y_j}}^2$ est le carré de la distance euclidienne entre des points, alors la quantité $W(\aC,\bC)^{1/2}$ est une distance entre les distributions, en particulier elle vérifie $W(\aC,\bC)=0$ si et seulement si $\aC=\bC$, et elle vérifie l’inégalité triangulaire. Ces propriétés sont très importantes pour permettre d’appliquer le transport à des problèmes pratiques.

Un exemple typique d’application de cette quantité $W$ consiste à calculer des barycentres entre des distributions [7]. La figure précédente montre un exemple où l’on considère trois distributions $a,b,c$ (montrées aux trois sommets du triangle) qui sont des distributions uniformes de masse à l’intérieur de formes 3D (c’est-à-dire que la masse $a_i$ associée au $i^{\text{e}}$ point est 0 à l’extérieur de la première forme et prend une valeur constante à l’intérieur).
On calcule un barycentre pondéré de ces trois distributions en imitant le fait que dans un espace euclidien, le barycentre pondéré $r$ de trois points $x,y,z$ minimise la somme des distances au carré
\[\begin{equation*} \umin{r} \alpha \norm{x-r}^2 + \beta \norm{y-r}^2 + \gamma \norm{z-r}^2, \end{equation*}\]
où les poids $(\alpha,\beta,\gamma)$ sont les pondérations du barycentre, qui sont des réels positifs et tels que $\alpha+\beta+\gamma=1$.
Le barycentre pondéré $d$ de $(a,b,c)$ minimise ainsi la somme pondérée de distances de transport optimal
\[\begin{equation}\label{eq-bary} \umin{d} \alpha W(a,d) + \beta W(b,d) + \gamma W(c,d). \end{equation}\]
En modifiant les poids $(\alpha,\beta,\gamma)$, on modifie la forme obtenue en se déplaçant à l’intérieur d’un triangle de transport optimal.
On peut utiliser cette distance $W$ pour bien d’autres applications où l’on doit comparer des distributions de probabilité. C’est le cas en apprentissage machine, par exemple pour comparer des textes à l’aide des distributions des mots qui les composent. La figure suivante illustre les histogrammes d’apparition des mots pour deux textes, où la taille des lettres du mot $\iC$ est proportionnelle à la masse $\aC_\iC$. Une question difficile dans ce cas est de savoir quelle matrice de coût $C_{\iC,\jC}$ utiliser entre deux mots $(\iC,\jC)$. Il s’agit d’un travail de linguistique (caractériser la proximité sémantique entre des mots du langages), que l’on peut chercher à résoudre en même temps que le transport optimal [8].

Post-scriptum :

Je tiens à remercier Yassine Ghalem et Ophélie Rouby pour leurs relectures attentives.

Article édité par Jérôme Buzzi

Notes

[1Gaspard Monge. Mémoire sur la théorie des déblais et des remblais. Histoire de l’Académie Royale des Sciences, pages 666-704, 1781.

[2Leonid Kantorovich. On the transfer of masses (in russian). Doklady Akademii Nauk, 37(2) :227-229, 1942.

[3George B Dantzig. Application of the simplex method to a transportation problem. Activity Analysis of Production and Allocation, 13 :359–373, 1951.

[4Garrett Birkhoff. Tres observaciones sobre el algebra lineal. Universidad Nacional de Tucumán Revista Series A, 5 :147–151, 1946.

[5John Von Neumann. A certain zero-sum two-person game equivalent to the optimal assignment problem. Contributions to the Theory of Games, 2 :5–12, 1953.

[6Gabriel Peyré and Marco Cuturi. Computational optimal transport. Foundations and Trends in Machine Learning, 11(5-6), pages 355-607, 2019.

[7Martial Agueh and Guillaume Carlier. Barycenters in the wasserstein space. SIAM Journal on Mathematical Analysis, 43(2) :904–924, 2011.

[8Gao Huang, Chuan Guo, Matt J Kusner, Yu Sun, Fei Sha, and Kilian Q Weinberger. Supervised word mover’s distance. In Advances in Neural Information Processing Systems, pages 4862– 4870, 2016.

Partager cet article

Pour citer cet article :

Gabriel Peyré — «Le transport optimal numérique et ses applications - Partie 2» — Images des Mathématiques, CNRS, 2019

Commentaire sur l'article

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?