Le sous-échantillonnage est une tâche récurrente en mathématiques appliquées. Ce paradigme a des applications en traitement du signal, l’analyse des données, l’apprentissage automatique ou bien les statistiques: la discrétisation des signaux analogiques, le calcul approché des intégrales, la réduction de dimension, la réduction du budget d’étiquetage des algorithmes d’apprentissage... Alors qu’ils paraissent différents, ces problèmes peu- vent être abordés avec la même stratégie: chercher les éléments les plus représentatifs d’un ensemble. Un bon sous-ensemble de représentants doit éviter de contenir des informations redondantes. Pour certains problèmes à structure linéaire, l’ensemble peut être plongé dans un espace vectoriel et la redondance d’un sous-ensemble peut se mesurer à l’aide du volume du polytope engendré par ce sous-ensemble. Il se trouve qu’il existe une famille de modèles probabilistes qui définissent des sous-ensembles aléatoires avec une propriété de répulsion: d’une façon informelle, la probabilité d’apparition d’un sous-ensemble est proportionnelle au volume qu’il engendre dans cet espace vectoriel. Ces modèles sont connus sous le nom des processus ponctuels déterminantaux et ils ont été étudiés dans plusieurs domaines: les matrices aléatoires, l’optique quantique, les statistiques spatiales, le traitement des images, l’apprentissage automatique et récemment l’intégration numérique. Cette thèse est consacrée à l’étude de la pertinence des DPPs pour certaines tâches de sous-échantillonnage. Dans un premier temps, nous avons considéré le problème de sélection d’attributs: pour une matrice qui représente des données exprimées sur un système d’attributs, on cherche à sélectionner les attributs les plus représentatifs. En particulier, nous avons étudié l’échantillonnage volumique, un algorithme bien connu dans la littérature, à travers la théorie des DPPs. Nous avons proposé un algorithme impliquant un DPP avec de meilleures garanties théoriques et de meilleures performances empiriques. Le choix de ce DPP était motivé par une nouvelle interprétation géométrique que nous avons mise en évidence: un DPP définit naturellement un sous-espace vectoriel aléatoire qui "flotte" autour d’un sous-espace de référence. A l’aide de cette nouvelle interprétation, nous avons réussi à étudier un autre problème d’approximation: l’approximation d’intégrales de fonctions qui vivent dans un espace à noyau, aussi appelé le problème de quadrature à noyau. Pour ce problème, nous avons proposé une nouvelle classe de quadratures: les quadratures à noyau optimisées et basées sur des noeuds qui suivent la distribution d’un DPP. La définition de ce DPP est basée sur les fonctions propres de l’opérateur d’intégration correspondant. Nous avons montré que les taux de convergence de cette classe de quadratures dépendent des valeurs propres de cet opérateur: plus le noyau est régulier, meilleure est la convergence de la quadrature. Néanmoins, les expériences numériques montrent que ces taux de convergence sont pessimistes pour certains espaces fonctionnels. Cette observation a motivé l’extension de l’échantillonnage volumique au domaine continu. Nous avons étudié le problème de quadrature à noyau ainsi que le problème d’interpolation à noyau pour des noeuds qui suivent cette nouvelle distribution. En particulier, nous avons démontré des formules closes de l’espérance de l’erreur sous cette distribution répulsive. Ces formules ont permis de démontrer l’optimalité de l’échantillonnage volumique pour cette classe de problèmes d’approximation. De plus, cette nouvelle distribution peut être approchée par un algorithme MCMC qui peut être implémenté sans le recours à la décomposition spectrale de l’opérateur d’intégration.
M. Pierre CHAINAIS Centrale Lille Directeur de thèse M. Rémi BARDENET CNRS; CRIStAL; Centrale Lille Examinateur M. Francis BACH Inria, ENS Paris Rapporteur Mme Agnès DESOLNEUX CNRS, CMLA, ENS Paris-Saclay Rapporteure M. Rémi GRIBONVAL Inria; ENS Lyon Examinateur Mme Gersende FORT CNRS; IMT Toulouse Examinatrice M. Chris OATES Newcastle University Invité
Thesis of the team SIGMA defended on 03/11/2020
français
English