Apprentissage séquentiel efficace dans des environnements structurés avec contraintes

Abstract

L’avantage principal des méthodes d’apprentissage non-paramétriques réside dans le faitque la nombre de degrés de libertés du modèle appris s’adapte automatiquement au nombred’é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 similitudeentre tous les échantillons. La complexité est alors quadratique en temps et espace, ce quis’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 pluspetite que le nombre d’échantillons lui-même. Il est alors possible de substituer le jeude 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 garantiesthéoriques utilisant des dictionnaires comme "Ridge Leverage Score" (RLS) ont aussi unecomplexité 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’avecle dictionnaire actuel, et non avec l’ensemble des échantillons passés. Nous montrons quela taille de tous les dictionnaires ainsi construits est de l’ordre de la dimension effectivedu jeu de données final, guarantissant ainsi une complexité en temps et espace à chaqueétape indépendante du nombre total d’échantillons. Cette méthode présente l’avantage depouvoir être parallélisée.Enfin, nous montrons que de nombreux problèmes d’apprentissage non-paramétriquespeuvent être résolus de manière approchée grâce à notre méthode.