CUTURI Marco

Au cours des dernières années, le transport optimal a gagné en popularité en apprentissage automatique comme moyen de comparer des mesures de probabilité. Contrairement aux dissimilarités plus classiques pour les distributions de probabilité, telles que la divergence de Kullback-Leibler, les distances de transport optimal (ou distances de Wasserstein) permettent de comparer des distributions dont les supports sont disjoints en prenant en compte la géométrie de l'espace sous-jacent. Cet avantage est cependant entravé par le fait que ces distances sont généralement calculées en résolvant un programme linéaire, ce qui pose, lorsque l'espace sous-jacent est de grande dimension, des défis statistiques bien documentés et auxquels on se réfère communément sous le nom de ``fléau'' de la dimension. Trouver de nouvelles méthodologies qui puissent atténuer ce problème est donc un enjeu crucial si l'on veut que les algorithmes fondés sur le transport optimal puissent fonctionner en pratique.Au-delà de cet aspect purement métrique, un autre intérêt de la théorie du transport optimal réside en ce qu'elle fournit des outils mathématiques pour étudier des cartes qui peuvent transformer, ou transporter, une mesure en une autre. De telles cartes jouent un rôle de plus en plus important dans divers domaines des sciences (biologie, imagerie cérébrale) ou sous-domaines de l'apprentissage automatique (modèles génératifs, adaptation de domaine), entre autres. Estimer de telles transformations qui soient à la fois optimales et qui puissent être généralisées en dehors des simples données, est un problème ouvert.Dans cette thèse, nous proposons un nouveau cadre d'estimation pour calculer des variantes des distances de Wasserstein. Le but est d'amoindrir les effets de la haute dimension en tirant partie des structures de faible dimension cachées dans les distributions. Cela peut se faire en projetant les mesures sur un sous-espace choisi de telle sorte à maximiser la distance de Wasserstein entre leurs projections. Outre cette nouvelle méthodologie, nous montrons que ce cadre d'étude s'inscrit plus largement dans un lien entre la régularisation des distances de Wasserstein et la robustesse.Dans la contribution suivante, nous partons du même problème d'estimation du transport optimal en grande dimension, mais adoptons une perspective différente : plutôt que de modifier la fonction de coût, nous revenons au point de vue plus fondamental de Monge et proposons d'utiliser le théorème de Brenier et la théorie de la régularité de Caffarelli pour définir une nouvelle procédure d'estimation des cartes de transport lipschitziennes qui soient le gradient d'une fonction fortement convexe.

Nous introduisons une extension du problème du transport optimal lorsque des coûts multiples sont impliqués. En considérant chaque coût comme un agent, nous cherchons à partager équitablement entre les agents le travail de transport d'une distribution à une autre. Pour ce faire, nous minimisons le coût de transport de l'agent qui travaille le plus. Un autre point de vue est celui où l'objectif est de partager équitablement les biens entre les agents en fonction de leurs préférences hétérogènes. Ici, on cherche à maximiser l'utilité de l'agent le moins favorisé. Il s'agit d'un problème de partage équitable. Comme pour le transport optimal, le problème peut être présenté comme un problème d'optimisation linéaire. Lorsqu'il n'y a qu'un seul agent, nous récupérons le problème du transport optimal. Lorsque deux agents sont considérés, nous sommes en mesure de récupérer les métriques de probabilité intégrale définies par les fonctions $\alpha$-H\"older, qui incluent la métrique de Dudley largement connue. A notre connaissance, c'est la première fois qu'un lien est donné entre la métrique de Dudley et le transport optimal. Nous fournissons une régularisation entropique de ce problème qui conduit à un algorithme alternatif plus rapide que le programme linéaire standard.

Pas de résumé disponible.

Pouvoir manipuler et de comparer de mesures de probabilité est essentiel pour de nombreuses applications en apprentissage automatique. Le transport optimal (TO) définit des divergences entre distributions fondées sur la géométrie des espaces sous-jacents : partant d'une fonction de coût définie sur l'espace dans lequel elles sont supportées, le TO consiste à trouver un couplage entre les deux mesures qui soit optimal par rapport à ce coût. Par son ancrage géométrique, le TO est particulièrement bien adapté au machine learning, et fait l'objet d'une riche théorie mathématique. En dépit de ces avantages, l'emploi du TO pour les sciences des données a longtemps été limité par les difficultés mathématiques et computationnelles liées au problème d'optimisation sous-jacent. Pour contourner ce problème, une approche consiste à se concentrer sur des cas particuliers admettant des solutions en forme close, ou pouvant se résoudre efficacement. En particulier, le TO entre mesures elliptiques constitue l'un des rares cas pour lesquels le TO admet une forme close, définissant la géométrie de Bures-Wasserstein (BW). Cette thèse s'appuie tout particulièrement sur la géométrie de BW, dans le but de l'utiliser comme outil de base pour des applications en sciences des données. Pour ce faire, nous considérons des situations dans lesquelles la géométrie de BW est tantôt utilisée comme un outil pour l'apprentissage de représentations, étendue à partir de projections sur des sous-espaces, ou régularisée par un terme entropique. Dans une première contribution, la géométrie de BW est utilisée pour définir des plongements sous la forme de distributions elliptiques, étendant la représentation classique sous forme de vecteurs de R^d. Dans une deuxième contribution, nous prouvons l'existence de transports qui extrapolent des applications restreintes à des projections en faible dimension, et montrons que ces plans "sous-espace optimaux" admettent des formes closes dans le cas de mesures gaussiennes. La troisième contribution de cette thèse consiste à obtenir des formes closes pour le transport entropique entre des mesures gaussiennes non-normalisées, qui constituent les premières expressions non triviales pour le transport entropique. Finalement, dans une dernière contribution nous utilisons le transport entropique pour imputer des données manquantes de manière non-paramétrique, tout en préservant les distributions sous-jacentes.

Les distances de transport optimal (OT) entre les distributions de probabilité sont paramétrées par la métrique de base qu'elles utilisent entre les observations. Leur pertinence pour les applications de la vie réelle dépend fortement du choix approprié de ce paramètre de métrique de base. Le défi de le sélectionner de manière adaptative et algorithmique à partir de connaissances préalables, appelé le problème de l'apprentissage de la métrique de base (GML), est donc apparu dans divers contextes. Dans cet article, nous considérons le problème GML lorsque la métrique apprise est contrainte d'être une distance géodésique sur un graphe qui supporte les mesures d'intérêt. Cela impose une structure riche pour les métriques candidates, mais permet également des procédures d'apprentissage beaucoup plus efficaces par rapport à une optimisation directe sur l'espace de toutes les matrices métriques. Nous utilisons ce cadre pour aborder un problème inverse découlant de l'observation d'une densité évoluant avec le temps. Nous cherchons une métrique de base du graphe telle que l'interpolation OT entre les densités de départ et d'arrivée qui résulte de cette métrique de base concorde avec l'évolution observée. Ce cadre dynamique OT est pertinent pour modéliser des phénomènes naturels présentant des déplacements de masse, tels que l'évolution de la palette de couleurs induite par la modi- fication de l'éclairage et des matériaux.

Bien que les problèmes de transport optimal (OT) admettent des solutions à forme fermée dans un très petit nombre de cas notables, par exemple en 1D ou entre gaussiens, ces formes fermées se sont avérées extrêmement fécondes pour les praticiens afin de définir des outils inspirés de la géométrie OT. D'autre part, la résolution numérique des problèmes d'OT en utilisant la régularisation entropique a donné lieu à de nombreuses applications, mais parce qu'il n'y a pas de solutions connues sous forme fermée pour les problèmes d'OT régularisés entropiquement, ces approches sont principalement algorithmiques, et non informées par des formes fermées élégantes. Dans cet article, nous proposons de combler le vide à l'intersection entre ces deux écoles de pensée en OT en prouvant que le problème de transport optimal régularisé par l'entropie entre deux mesures gaussiennes admet une forme fermée. Contrairement au cas non régularisé, pour lequel la forme explicite est donnée par la distance de Wasserstein-Bures, la forme fermée que nous obtenons est différentiable partout, même pour des gaussiennes avec des matrices de covariance dégénérées. Nous obtenons cette solution sous forme fermée en résolvant l'équation du point fixe derrière l'algorithme de Sinkhorn, la méthode par défaut pour calculer les OT régularisés entropiques. De façon remarquable, cette approche s'étend au cas de déséquilibre généralisé, où les mesures gaussiennes sont mises à l'échelle par des constantes positives. Cette extension conduit à une expression de forme fermée pour les gaussiennes non équilibrées également, et met en évidence le compromis transport de masse/destruction observé dans le transport optimal non équilibré. De plus, dans les deux cas, nous montrons que les plans de transport optimaux sont des gaussiennes (mises à l'échelle) et nous fournissons des formules analytiques de leurs paramètres. Ces formules constituent les premières formes fermées non triviales pour le transport optimal régularisé par l'entropie, fournissant ainsi une vérité de base pour l'analyse de l'OT entropique et de l'algorithme de Sinkhorn.

La régularisation de l'entropie dans le transport optimal (OT) a été le moteur de nombreux intérêts récents pour la métrique de Wasserstein et les barycentres dans l'apprentissage automatique. Elle permet de conserver les propriétés géométriques attrayantes de la distance de Wasserstein non régularisée tout en ayant une complexité nettement inférieure grâce à l'algorithme de Sinkhorn. Cependant, l'entropie apporte un biais de lissage inhérent, qui se traduit par exemple par des barycentres flous. Cet effet secondaire a suscité une tentation croissante dans la communauté de se contenter d'un algorithme plus lent tel que l'algorithme de Sinkhorn stabilisé par le domaine logarithmique qui brise la structure parallèle qui peut être exploitée sur les GPU, ou même de revenir à l'OT non régularisé. Nous montrons ici comment ce biais est étroitement lié à la mesure de référence qui définit le régularisateur d'entropie et proposons des barycentres de Wasserstein débités qui préservent le meilleur des deux mondes : des itérations rapides de type Sinkhorn sans lissage d'entropie. Sur le plan théorique, nous prouvons que le barycentre entropique OT des gaussiennes univariées est une gaussienne et quantifions son biais de variance. Ce résultat est obtenu en étendant la différentiabilité et la convexité de l'OT entropique à des mesures sous-gaussiennes avec des supports non bornés. Empiriquement, nous illustrons la réduction du flou et l'avantage computationnel sur diverses applications.

Pas de résumé disponible.

L’analyse topologique des données (ATD) permet d’extraire une information riche des données structurées (telles que les graphes ou les séries temporelles) présentes dans les problèmes modernes d’apprentissage. Elle va représenter cette information sous forme de descripteurs dont font partie les diagrammes de persistance, qui peuvent être décrits comme des mesures ponctuelles supportées sur un demi-plan. À défaut d’être de simples vecteurs, les diagrammes de persistance peuvent néanmoins être comparés entre eux à l’aide de métriques d’appariement partiel. La similarité entre ces métriques et les métriques usuelles du transport optimal - un autre domaine des mathématiques - est connue de longue date, mais un lien formel entre ces deux domaines restait à établir. L’objet de cette thèse est de clarifier cette connexion pour pouvoir utiliser les nombreux acquis du transport optimal afin de développer de nouveaux outils statistiques (théoriques et pratiques) pour manipuler les diagrammes de persistance. Dans un premier temps, nous montrons comment le transport optimal partiel avec frontière, une variante du transport optimal classique, nous fournit un formalisme qui contient les métriques usuelles de l’ATD. Nous illustrons ensuite les apports bénéfiques de cette reformulation dans différentes situations: étude théorique et algorithme pour l’estimation efficace des barycentres de diagrammes de persistance grâce au transport régularisé, caractérisation des représentations linéaires continues des diagrammes et leur apprentissage via un réseau de neurones versatile, ainsi qu’un résultat de stabilité des moyennes linéaires de diagrammes tirés aléatoirement.

Pas de résumé disponible.

Le transport optimal (OT) et les divergences moyennes maximales (MMD) sont désormais couramment utilisés en apprentissage automatique pour comparer des mesures de probabilité. Nous nous concentrons dans cet article sur les \emph{Divergences de Sinkhorn} (SDs), une variante régularisée des distances OT qui peut interpoler, selon la force de régularisation $\varepsilon$, entre OT ($\varepsilon=0$) et MMD ($\varepsilon=\infty$). Bien que le compromis induit par cette régularisation soit maintenant bien compris sur le plan informatique (OT, SDs et MMD nécessitent respectivement $O(n^3\log n)$, $O(n^2)$ et $n^2$ opérations pour une taille d'échantillon $n$), on en sait beaucoup moins en termes de leur \emph{sample complexity}, à savoir l'écart entre ces quantités, lorsqu'elles sont évaluées à l'aide d'échantillons finis \emph{vs.} leurs densités respectives. En effet, alors que la complexité d'échantillon d'OT et de MMD se situe à deux extrêmes, $1/n^{1/d}$ pour OT en dimension $d$ et $1/\sqrt{n}$ pour MMD, celle des SDs n'a été étudiée qu'empiriquement. Dans cet article, nous \emph{(i)} dérivons une borne sur l'erreur d'approximation faite avec les SDs lors de l'approximation d'OT en fonction du régularisateur $\varepsilon$, \emph{(ii)} prouvons que les optimiseurs d'OT régularisés sont bornés dans une boule de Sobolev (RKHS) indépendante des deux mesures et \emph{(iii)} fournissons la première borne de complexité d'échantillon pour les SDs, obtenue en reformulant les SDs comme un problème de maximisation dans un RKHS. Nous obtenons ainsi une mise à l'échelle en $1/\sqrt{n}$ (comme dans la MMD), avec une constante qui dépend toutefois de $\varepsilon$, rendant le pont entre OT et MMD complet.

Les distances de transport optimal (OT) entre les distributions de probabilité sont paramétrées par la métrique de base qu'elles utilisent entre les observations. Leur pertinence pour les applications de la vie réelle dépend fortement du choix approprié de ce paramètre métrique de base. La sélection adaptative et algorithmique de ce paramètre à partir de connaissances préalables, appelée problème de l'apprentissage de la métrique du sol (GML), est donc apparue dans divers contextes. Nous le considérons dans cet article lorsque la métrique apprise est contrainte d'être une distance géodésique sur un graphe qui supporte les mesures d'intérêt. Cela impose une structure riche pour les métriques candidates, mais permet également des procédures d'apprentissage beaucoup plus efficaces par rapport à une optimisation directe sur l'espace de toutes les matrices métriques. Nous utilisons ce cadre pour aborder un problème inverse découlant de l'observation d'une densité évoluant avec le temps : nous cherchons une métrique de base du graphe telle que l'interpolation OT entre les densités de départ et d'arrivée qui résulte de cette métrique de base concorde avec l'évolution observée. Ce cadre dynamique OT est pertinent pour modéliser des phénomènes naturels présentant des déplacements de masse, comme par exemple l'évolution de la palette de couleurs induite par la modification de l'éclairage et des matériaux.

Le test non paramétrique à deux échantillons ou test d'homogénéité est un problème de théorie de la décision qui consiste à identifier les différences entre deux variables aléatoires sans faire d'hypothèses paramétriques sur leurs distributions sous-jacentes. La littérature est ancienne et riche, avec une grande variété de statistiques ayant été conçues et analysées, tant pour le cadre unidimensionnel que multivarié. Dans cette courte étude, nous nous concentrons sur les statistiques de test qui impliquent la distance de Wasserste. En utilisant un lissage entropique de la distance de Wasserstein, nous les connectons à des tests très différents, y compris des méthodes multivariées impliquant des statistiques d'énergie et une divergence moyenne maximale basée sur un noyau, et des méthodes univariées comme le test de Kolmogorov-Smirnov, des diagrammes de probabilité ou de quantile (PP/QQ) et des courbes de caractéristiques d'exploitation du récepteur ou de dominance ordinale (ROC/ODC). Certaines observations sont implicites dans la littérature, tandis que d'autres ne semblent pas avoir été remarquées jusqu'à présent. Étant donné l'importance classique et continue des tests non paramétriques à deux échantillons, notre objectif est de fournir des liens utiles aux théoriciens et aux praticiens qui connaissent un sous-ensemble de méthodes mais pas les autres.

Pas de résumé disponible.

Le transport optimal (OT) définit un cadre puissant pour comparer des distributions de probabilité d'une manière géométriquement fidèle. Cependant, l'impact pratique de l'OT est encore limité en raison de sa charge de calcul. Nous proposons une nouvelle classe d'algorithmes d'optimisation stochastique pour faire face aux problèmes à grande échelle couramment rencontrés dans les applications d'apprentissage automatique. Ces méthodes sont capables de manipuler des distributions arbitraires (discrètes ou continues) en ayant simplement besoin de pouvoir en tirer des échantillons, ce qui est la configuration typique des problèmes d'apprentissage à haute dimension. Cela allège la nécessité de discrétiser ces densités, tout en donnant accès à des méthodes à convergence prouvée qui produisent la distance correcte sans erreur de discrétisation. Ces algorithmes reposent sur deux idées principales : (a) le problème OT dual peut être reformulé comme la maximisation d'une espérance . (b) la régularisation entropique du problème OT primaire donne lieu à une optimisation duale lisse qui peut être traitée par des algorithmes dont la convergence est prouvée comme étant plus rapide. Nous instantions ces idées dans trois configurations différentes : (i) en comparant une distribution discrète à une autre, nous montrons que les schémas d'optimisation stochastique incrémentale peuvent battre l'algorithme de Sinkhorn, l'actuel solveur d'OT en dimension finie de pointe. (ii) lors de la comparaison d'une distribution discrète à une densité continue, une reformulation semi-discrète du programme dual se prête à la descente de gradient stochastique moyennée, ce qui conduit à de meilleures performances que la résolution approximative du problème par discrétisation. (iii) lorsqu'il s'agit de deux densités continues, nous proposons une descente de gradient stochastique sur un espace de Hilbert à noyau reproducteur (RKHS). C'est actuellement la seule méthode connue pour résoudre ce problème, à part le calcul de l'OT sur des échantillons finis. Nous soutenons ces affirmations sur un ensemble de problèmes de référence discrets, semi-discrets et continus.

Cet article définit une nouvelle façon d'effectuer des régressions intuitives et géométriquement fidèles sur des données à valeur d'histogramme. Il s'appuie sur la théorie du transport optimal, et en particulier sur la définition des barycentres de Wasserstein, pour introduire pour la première fois la notion de coordonnées barycentriques pour les histogrammes. Ces coordonnées prennent en compte la géométrie sous-jacente de l'espace de base sur lequel les histogrammes sont définis, et sont donc particulièrement significatives pour les applications graphiques aux formes, à la couleur ou à la modification des matériaux. Outre cette construction abstraite, nous proposons un schéma d'optimisation numérique rapide pour résoudre ce problème à rebours (trouver les coordonnées barycentriques d'un histogramme donné) avec une faible surcharge de calcul par rapport au problème à rebours (calculer le barycentre). Ce schéma repose sur une différenciation algorithmique à rebours de l'algorithme de Sinkhorn qui est utilisé pour optimiser la régularisation entropique des barycentres de Wasserstein. Nous présentons un ensemble illustratif d'applications de ces coordonnées de Wasserstein à divers problèmes d'infographie : approximation de formes, acquisition de BRDF et édition de couleurs.

Connaître l'organisation anatomique et fonctionnelle du cerveau humain au niveau d'un groupe d'individus sains ou de patients est l'objectif principal de la recherche en neuro-imagerie. Pourtant, calculer une moyenne des données d'imagerie cérébrale définies sur une grille de voxels ou une triangulation reste un défi. Les données sont volumineuses, la géométrie du cerveau est complexe et la variabilité entre les sujets entraîne des effets d'intérêt qui ne se chevauchent pas dans l'espace ou dans le temps. Pour résoudre le problème de la variabilité, les données sont généralement lissées avant d'être soumises à une moyenne linéaire de groupe. Dans ce travail, nous nous appuyons sur des idées introduites à l'origine par Kantorovich pour proposer un nouvel algorithme capable de calculer efficacement la moyenne de données non normalisées définies sur des domaines discrets arbitraires en utilisant des métriques de transport. Nous montrons comment les moyennes de Kantorovich peuvent être liées aux barycentres de Wasserstein afin de tirer parti d'une approche de lissage entropique. Cela conduit à un problème d'optimisation convexe lisse et à un algorithme avec de fortes garanties de convergence. Nous illustrons la polyvalence de cet outil et son comportement empirique sur des données de neuroimagerie fonctionnelle, des estimations de sources d'IRM fonctionnelle et de magnétoencéphalographie (MEG), définies sur des grilles de voxels et des triangulations de la surface corticale pliée.