Note ABES Efficient sequential learning in structured and constrained environments Apprentissage séquentiel efficace dans des environnements structurés avec contraintes Méthode de Nyström Échantillonnage préférentiel Apprentissage automatique à grande échelle 006.31 Apprentissage automatique Statistique non paramétrique Prédiction séquentielle Optimisation convexe Représentation parcimonieuse Graphes aléatoires Analyse en composantes principales L'avantage principal des méthodes d'apprentissage non-paramétriques réside dans le fait que la nombre de degrés de libertés du modèle appris s'adapte automatiquement au nombre d'échantillons. Ces méthodes sont cependant limitées par le "fléau de la kernelisation": apprendre le modèle requière dans un premier temps de construire une matrice de similitude entre tous les échantillons. La complexité est alors quadratique en temps et espace, ce qui s'avère rapidement trop coûteux pour les jeux de données de grande dimension. Cependant, la dimension "effective" d'un jeu de donnée est bien souvent beaucoup plus petite que le nombre d'échantillons lui-même. Il est alors possible de substituer le jeu de donnée réel par un jeu de données de taille réduite (appelé "dictionnaire") composé exclusivement d'échantillons informatifs. Malheureusement, les méthodes avec garanties théoriques utilisant des dictionnaires comme "Ridge Leverage Score" (RLS) ont aussi une complexité quadratique. Dans cette thèse nous présentons une nouvelle méthode d'échantillonage RLS qui met à jour le dictionnaire séquentiellement en ne comparant chaque nouvel échantillon qu'avec le dictionnaire actuel, et non avec l'ensemble des échantillons passés. Nous montrons que la taille de tous les dictionnaires ainsi construits est de l'ordre de la dimension effective du jeu de données final, garantissant ainsi une complexité en temps et espace à chaque étape indépendante du nombre total d'échantillons. Cette méthode présente l’avantage de pouvoir être parallélisée. Enfin, nous montrons que de nombreux problèmes d'apprentissage non-paramétriques peuvent être résolus de manière approchée grâce à notre méthode. The main advantage of non-parametric models is that the accuracy of the model (degrees of freedom) adapts to the number of samples. The main drawback is the so-called "curse of kernelization": to learn the model we must first compute a similarity matrix among all samples, which requires quadratic space and time and is unfeasible for large datasets. Nonetheless the underlying effective dimension (effective d.o.f.) of the dataset is often much smaller than its size, and we can replace the dataset with a subset (dictionary) of highly informative samples. Unfortunately, fast data-oblivious selection methods (e.g., uniform sampling) almost always discard useful information, while data-adaptive methods that provably construct an accurate dictionary, such as ridge leverage score (RLS) sampling, have a quadratic time/space cost. In this thesis we introduce a new single-pass streaming RLS sampling approach that sequentially construct the dictionary, where each step compares a new sample only with the current intermediate dictionary and not all past samples. We prove that the size of all intermediate dictionaries scales only with the effective dimension of the dataset, and therefore guarantee a per-step time and space complexity independent from the number of samples. This reduces the overall time required to construct provably accurate dictionaries from quadratic to near-linear, or even logarithmic when parallelized. Finally, for many non-parametric learning problems (e.g., K-PCA, graph SSL, online kernel learning) we we show that we can can use the generated dictionaries to compute approximate solutions in near-linear that are both provably accurate and empirically competitive. Electronic Thesis or Dissertation Text en PDF 2328489 text/html https://pepite-depot.univ-lille.fr/LIBRE/EDSPI/2017/50376-2017-Calandriello.pdf https://theses.fr/2017LIL10216/abes Calandriello Daniele Calandriello 1989-08-22 IT 229910491 https://theses.fr/2017LIL10216 2017LIL10216 https://doi.org/10.70675/1e47cd3cz725bz41ffzb6c0z00708c3e3910 2017-12-18 Informatique Lille 1 026404184 Doctorat Docteur es non oui Valko Michal MADS_DIRECTEUR_DE_THESE_1 22360934X Lazaric Alessandro MADS_DIRECTEUR_DE_THESE_2 188701486 École doctorale Sciences pour l'ingénieur (Lille ; 1992-2021) MADS_ECOLE_DOCTORALE_1 147297028 Centre de Recherche en Informatique, Signal et Automatique de Lille MADS_PARTENAIRE_DE_RECHERCHE_1 18388695X ddc:004 Valko Michal Lazaric Alessandro École doctorale Sciences pour l'Ingénieur (Lille) Centre de recherche en informatique, signal et automatique de Lille (CRIStAL) PDF 2328489