Algorithmes dÇinspiration géométrique, corrigés pour lÇapprentissage en haute dimension

par/by Pascal Vincent
ApSTAT Technologies Inc.

De nombreux algorithmes d'apprentissage statistique classiques, tel celui des k plus proches voisins, trouvent leur inspiration dans des intuitions géométriques en faible dimension (dimension 1, 2 ou 3). Mais lorsqu'on tente de les appliquer tels quels sur des ensembles de données en haute dimension, provenant de problèmes concrets, les performances peuvent être décevantes. L'apprentissage se heurte alors au phénomène dit de la "malédiction de la dimensionalité" : un des défis les plus importants de la recherche en apprentissage. Dans cet exposé, je montrerai qu'il est possible, en tenant compte d'hypothèses raisonnables sur la répartition des données en haute dimension, de concevoir des variantes d'algorithmes classiques donnant lieu à une amélioration importante de la performance. Je présenterai en particulier des versions corrigées de l'algorithme des k plus proches voisins, et de l'algorithme des fenêtres de Parzen. Je tenterai ensuite d'apporter un éclairage nouveau à cette approche fructueuse, au travers de la notion de "transformations invariantes". Nous envisagerons les versions corrigées des algortihmes précédents comme l'apprentissage de telles transformations. Pour finir nous verrons comment ceci permet de généraliser l'approche, notamment à des espaces autres que R^n où l'intuition géométrique n'est plus évidente, et ouvre la voie à de nouveaux algortihmes génériques susceptibles de repousser encore davantage la frontière de la malédiction de la dimensionalité.