15 avril 2019

2min

Le Transport Optimal, couteau suisse pour la Data Science

La théorie du transport optimal plonge ses racines dans l’histoire des mathématiques avec un problème formulé au 18ème siècle par Gaspard Monge qui se demandait comment déplacer un tas de sable en fournissant le moindre effort possible. Grace à une succession de progrès théoriques et, plus récemment, algorithmiques, cette théorie trouve aujourd’hui de nombreuses applications pratiques en data science. Elle permet tout à la fois de définir une notion géométrique et naturelle de distance entre deux distributions de probabilités et de « morpher » une distribution en une autre à moindre coût. Cet article est une introduction modérément technique au sujet et s’adresse prioritairement aux data scientist.

Un outil polyvalent encore méconnu

Le terme de transport optimal (TO) convoque immanquablement l’association d’idée avec les problèmes qui préoccupent la SNCF ou la RATP et leurs clients. En vérité cette association n’est pas totalement infondée, même si les liens sont beaucoup plus étroits comme nous le verrons entre le TO et la Data Science qu’avec les questions ferroviaires.

Cependant, commençons par le commencement. La question du déplacement à moindre coût d’un objet est un problème aussi ancien que la mécanique ou la géométrie. On peut se proposer par exemple de chercher le chemin le plus court qui relie deux points sur une surface on parle alors de géodésique. Plus complexe en revanche est le problème qui consiste à déplacer simultanément tous les grains d’un tas de sable pour en former un autre un peu plus loin dont on prescrit la forme et ceci tout en minimisant l’effort à produire.

Il s’agit en l’occurrence de déplacer littéralement une infinité de grains en respectant à la fois la contrainte globale d’effort minimal et la contrainte de la forme prescrite du tas cible. Aussi surprenant que cela paraisse ce problème s’est avéré si ardu que pas moins de 150 ans se sont écoulés entre sa formulation originale par Gaspard Monge et une première esquisse de solution durant la seconde guerre mondiale par un mathématicien russe, Leonid Kantorovitch, alors expert en optimisation d’allocation de ressources.

Et lien avec la Data Science dans tout ça ? Patience, nous y viendrons. Mais avant cela un peu de théorie sera nécessaire pour y voir clair. Les distributions de probabilités étant omniprésentes dans le Machine Learning (ML), qu’elles soient théoriques ou empiriques, qu’on admette simplement pour l’instant qu’il puisse être utile de savoir mesurer leur séparation ou, mieux encore, de pouvoir les transformer à moindre frais.

Pirmin Lemberger

Chercheur, Directeur Data Scientist