Return to site

Le transport optimal et ses applications en statistiques et apprentissage

Article de vulgarisation issu de l'exposé de Jérémie Bigot, chercheur à l'IMB Bordeaux

On parle beaucoup aujourd'hui d'un thème de recherche en mathématiques à l'intersection entre la géométrie, la théorie de l'information et et les probabilités : le transport optimal. Depuis la médaille fields de l'ultra médiatisé Cédric Villani en 2010, les applications du transport optimal dans le Big Data se multiplient et en fait un sujet en pleine effervescence.

Le mois dernier nous avons reçu Jérémie Bigot, chercheur à l'institut de mathématiques de Bordeaux, au Meetup Pau Machine Learning. Cet article a pour objectif d'introduire ce domaine à des non-spécialistes. Certaines illustrations ont été partagée par Jérémie que nous remercions !

Un vieux problème

Il faut remonter au XVIIIème et au Mémoire sur "La théorie des déblais et des remblais", écrit par Gaspard Monge, pour comprendre les fondements du transport optimal. Dans cet ouvrage, un problème très concret est abordé : comment déplacer un énorme tas de sable avec sa brouette à moindre coût ? Imaginez-vous sur votre plage favorite, ayant creusé un trou avec votre pelle, et avec l'objectif de reboucher le trou pour laisser la plage dans l'état dans lequel vous l'avez trouvée. Se pose alors le problème du choix de la stratégie optimale, puisque vous voyez vite qu'il y a une quantité extraordinaire de façons différentes de reboucher ce trou, à coup d'aller-retour avec votre brouette. Le problème de Monge est l'un des premier problème de recherche opérationelle, c'est-à-dire chercher parmi un grand nombre de possibilités, une solution optimale, au sens d'un certain critère, qu'on peut quantifier ici d'une manière simple : en minimisant la distance parcourue et le poids soulevé par exemple.

Le problème de Monge a été revisité plus récemment par Leonid Kantorovich dans les années 40, avec des applications beaucoup plus pragmatique, comme l'optimisation de la production dans les usines, étant donné des mines produisant du métal et un nombre de ressources donné. Enfin, pour terminer ce petit tour historique, il serait cruel de ne pas citer la médaille Fields décerné en 2010 à Cédric Villani, pour ses travaux concernant « les preuves de l’amortissement de Landau non linéaire et de la convergence vers l’équilibre dans l’équation de Boltzmann», ou dit plus simplement, sur l'ensemble de son oeuvre universitaire dédiée au transport optimal. Le mathématicien français, converti à la politique depuis, a publié également plusieurs ouvrages comme celui-ci de 973 pages sur ce vaste sujet. Citons également pour les lecteurs moins aguérris la parution de "Théorèmes vivants", aux éditions Grasset, qui relatent le quotidien du chercheur Villani et de son collègue Clément Mouhot, ou comment obtenir un médaille Fields en travaillant dans ses toilettes le 25 décembre (véridique).

Vers des moyennes intelligentes

Revenons à nos moutons. Le transport optimal va nous permettre de quitter le monde de la géométrie Euclidienne pour revisiter le concept de moyenne. Pour cela, nous devons introduire quelques notions mathématiques. Considérons une suite de nombres réels a, b, c, d dont nous souhaitons faire la moyenne. La formule de la moyenne au sens usuel est simplement (a+b+c+d)/4, je ne vous apprend rien.

Il existe une autre manière de définir la moyenne, à l'aide du transport. Cette définition est beaucoup plus intéressante pour nous, et aussi beaucoup plus belle mathématiquement, puisqu'elle va nous permettre de généraliser ce concept à des objets beaucoup plus complexes que de simples nombres réels. Pour cela, considérons toujours notre suite a,b,c, d à laquelle on associe une fonction f(x)=(a-x)2+(b-x)2+(c-x)2+(d-x)2

Cette fonction calcule, à partir d'une valeur x, la distance (au carré) entre cette valeur et chaque élément de la suite a,b,c et d et les ajoutent. Il se trouve que la moyenne de cette suite est le (seul) nombre qui va minimiser cette fonction. Si l'on y réfléchit un peu, ce n'est pas très étonnant : le nombre qui minimise cette fonction est bien celui qui n'est pas trop éloigné de chacun des nombres de la suite a,b,c et d.

Cette définition de la moyenne est très intéressante. Dans la formulation ci-dessus, que se passe-t-il si l'on change la manière de calculer la distance entre x et chacune des valeurs a, b, c et d de la suite ? Cette question permet de définir des notions de moyennes différentes, comme la médiane (lorsqu'on enlève le carré). Mais nous pouvons aller plus loin. La définition précédente nous permet également de changer le type d'objets dans notre suite, en associant une distance entre des objets A,B, C et D, comme par exemple. des courbes, des images, des distributions ou encore des surfaces planes. L'exemple ci-dessous nous montre par exemple la moyenne entre un lapin et un signe, résultat précédent calculé à partir de distance entre objets plus complexes calculée elle-même grâce au transport optimal !

Enfin, l'analyse en composante principale (ACP) est un outil très ancien du Data Mining. Basé sur le principe de moyenne et de variance, l'ACP peut de la même manière utiliser des notions de transport optimal pour décrire des suites d'objets complexes, comme l'ensemble des variations dans l'écriture d'un 2 ou d'un 6 (grâce ici au très fameux dataset MNIST) :

Pour aller plus loin...

Aujourd'hui les applications du transport optimal dépassent largement ce cadre statistique et cette notion de moyenne et de variance généralisées. Le transport optimal est utilisé en Machine Learning pour générer des données de tout type, colorer des images, ou encore calculer des distances entre documents.

Pour en savoir plus sur ces applications, cet article de blog détaille comment utiliser le transport optimal pour déterminer la distance entre deux documents, résultant du transport optimal entre la distribution des mots (Bag Of Words) de chacun d'entre eux.

All Posts
×

Almost done…

We just sent you an email. Please click the link in the email to confirm your subscription!

OKSubscriptions powered by Strikingly