Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Université de Montréal Modèles à noyaux à structure locale par Pascal Vincent D

Université de Montréal Modèles à noyaux à structure locale par Pascal Vincent Département d’informatique et de recherche opérationnelle Faculté des arts et des sciences Thèse présentée à la Faculté des études supérieures en vue de l’obtention du grade de Philosophiœ Doctor (Ph.D.) en informatique Octobre 2003 ©Pascal Vincent, 2003 ‘-q ç 1LJt ,3Zi 11.3 i( Université de Montréal Direction des bibliothèques AVIS L’auteur a autorisé l’Université de Montréal à reproduire et diffuser, en totalité ou en partie, par quelque moyen que ce soit et sur quelque support que ce soit, et exclusivement à des fins non lucratives d’enseignement et de recherche, des copies de ce mémoire ou de cette thèse. L’auteur et les coauteurs le cas échéant conservent la propriété du droit d’auteur et des droits moraux qui protègent ce document. Ni la thèse ou le mémoire, ni des extraits substantiels de ce document, ne doivent être imprimés ou autrement reproduits sans l’autorisation de l’auteur. Afin de se conformer à la Loi canadienne sur la protection des renseignements personnels, quelques formulaires secondaires, coordonnées ou signatures intégrées au texte ont pu être enlevés de ce document. Bien que cela ait pu affecter la pagination, il n’y a aucun contenu manquant. NOTICE The author of this thesis or dissertation has granted a nonexclusive license allowing Université de Montréal to reproduce and publish the document, in part or in whole, and in any format, solely for noncommercial educational and research purposes. The author and co-authors if applicable retain copyright ownership and moral rights in this document. Neither the whole thesis or dissertation, not substantial extracts from it, may be printed or otherwise reproduced without the author’s permission. In compliance with the Canadian Privacy Act some supporting forms, contact information or signatures may have been removed from the document. While this may affect the document page count, it does not represent any loss of content from the document. Université de Montréal Faculté des études supérieures Cette thèse intitulée: Modèles à noyaux à structure locale présentée par: Pascal Vincent a été évaluée par un jury composé des personnes suivantes: Balzs Kégl président-rapporteur Yoshua Bengio directeur de recherche Jean-Jules Brault membre du jury Sam Roweis examinateur externe Lael PalTott représentant du doyen de la FES o Résumé La plupart des problèmes concrets auxquels on souhaite appliquer les algorithmes d’apprentissage apparaissent en dimension élevée. Or le “fléau de la dimensio nalité” pose un défi pour obtenir de bonnes performances. Aussi le succès des Machines à Vecteurs de Support (SVMs) à noyaux, particulièrement sur des pro blèmes en haute dimension, a engendré un regain d’intérêt pour les méthodes à noyaux. Cette thèse propose trois algorithmes à noyaux, pour l’essentiel des ex tensions d’algorithmes classiques permettant de grandement améliorer leur per formance en haute dimension, et de surpasser les SVMs. Ce faisant, nous amélio rons également notre compréhension des caractéristiques des problèmes en haute dimension. La première partie de l’ouvrage est une introduction au domaine de l’apprentissage statistique. La seconde partie présente les algorithmes à noyaux les plus connus. Dans la troisième partie nous présentons notre recherche, au tra vers de trois articles. Enfin la quatrième partie effectue une synthèse et suggère des pistes pour aller plus loin. Le premier article, KenzeÏ Matching Pursuit, dé finit un algorithme constructif donnant lieu à une solution ayant la même forme que les SVMs mais permettant un strict contrôle du nombre de points de support et donnant lieu à des solutions davantage clairsemées que les SVMs. Le second iv article, K-Local Hyperptane and Convex Distance Nearest Neighbor Atgorithrns, propose une variante de l’algorithme des plus proches voisins, en redéfinissant la distance d’un point à une classe comme la distance à la variété linéaire sup portée par les voisins de ce point. Cette extension permet de surpasser les SVMs sur des problèmes concrets en haute dimension. Le troisième article, Mantfold Parzen Windows, étudie une variante de l’estimateur de densité classique de Par- zen. En utilisant des Gaussiennes aplaties orientées selon les directions principales apparaissant dans les données du voisinage, on peut mieux représenter une den sité concentrée le long d’une variété non linéaire de plus faible dimension, ce qui s’avère profitable en haute dimension. La principale conclusion de ces tra vaux est double. D’une part ils montrent que des algorithmes d’inspiration non paramétrique classique, qui ne font aucunement appel à “l’astuce du noyau”, sont capables de performance aussi bonne, voire supérieure, à celle des SVMs. D’autre part ils montrent qu’en haute dimension il y a beaucoup à gagner à développer des algorithmes sachant tirer partie de l’hypothèse selon laquelle les données seraient davantage concentrées le long de variétés non linéaires de faible dimension. Ceci constitue un espoir pour battre le fléau de la dimensionalité. Mots-c]és méthodes à noyaux, statistiques non paramétriques, fléau de la dimen sionalité, Machines à Vecteurs de Support, solutions clairsemées, k plus proches voisins, fenêtres de Parzen. o Abstract Most real world problems, for which one wishes to apply machine learning tech niques, appear in high dimensional spaces where the “curse of dimensionality” poses a serious challenge. Thus the success of kernelized Support Vector Ma chines (SVMs) on a number of high dimensional tasks has prompted a renewed interest in kernel methods. In this thesis, we propose three alternative kernel me thods, mostly extensions of classical algonthms, with greatly improved perfor mance in high dimension, that are able to outperform SVMs. In the process, we also increase our understanding of important characteristics of high dimensional problems. Part one of the document is a general introduction to machine learning. Part two descnbes the most common kernel methods. In part three, we present our research through three published articles. Finally, part four provides a synthesis of our contribution, and hints to possible future developments. The first article, Keniet liatching Pursuit, defines a constructive algorithm that leads to solutions of the same form as SVMs, but allows a strict control over the number of support vectors, leading to much sparser solutions. The second article, K-Local Hyper- plane and Convex Distance Nearest Neighbor Atgorithms, is a variation of the nearest neighbors algonthm in which we define the distance between a point and vi a class as the distance to the linear sub-manifold supported by the neighbors of that point. This extension allows to outperform SVMs on a number of high dimen sional problems. The third article, Manifold Parzen Windows, studies an extension of the classical Parzen density estimator, in which we use flattened Gaussian pan- cakes oriented along the principal directions appearing in the neighborhood of a point. This allows to better capture a density when it is concentrated along a b wer dimensional non linear manifold, which proves useful in high dimension. The important contribution of our research is twofold. First it shows that algorithms of classical non-parametric inspiration, that do not cail upon the “kemel trick” in any way, are able to perform as well or better than SVMs. Second, our resuits indicate that in high dimension, much is to be gaincd by designing algorithms that take into account the “manifold hypothesis”, i.e. that data might be more concentrated aÏong lower dimensional non linear sub-manifolds. This is so far the best hope we have to beat the curse of dimensionaÏity. Keywords kemel methods, non-parametnc statistics, curse of dimensionality, Support Vector Machines, sparsity, k nearest neighbors, Parzen windows. o Table des matières Résumé iii Abstract y Remerciements xxi I Introduction 3 1 Présentation du domaine de l’apprentissage automatique 4 1.1 Qu’est-ce que l’apprentissage automatique 4 1.2 Situation historique multi-disciplinaire 5 1.2.1 L’ apprentissage automatique par rapport aux statistiques classiques 6 1.3 Les tâches de l’apprentissage 8 1.3.1 L’apprentissage supervisé $ L’apprentissage non-supervisé . L’apprentissage par renforcement Inter-relations entre les techniques 3 Une tentative de classification des algorithmes d’apprentissage 3.1 Les modèles génératifs 3.2 Modélisation directe de la surface de décision 3.3 Extraction progressive de caractéristiques 3.4 Modèles basés sur des distances à des prototypes 3.5 Valeur relative de cette taxonomie défis de la haute dimensionalité Le fléau de la dimensionalité Intuitions géométriques en haute dimension 1.3.2 1.3.3 1.3.4 viii 9 11 11 13 20 2 La généralisation : le grand défi de l’apprentissage 2.1 Mémoriser n’est pas généraliser 2.2 Notations et formalisation du problème 2.3 Mesure de la performance de généralisation . 2.4 Quelques notions de théorie d’apprentissage . 2.5 Pratiques courantes de contrôle de capacité 22 23 24 25 26 28 29 30 30 4 Les 4.1 4.2 ix 4.3 La notion de variété de plus faible dimension 32 II Modèles à noyaux 34 5 Méthodes à noyau classiques et modernes 35 5.1 Noyaux et distances 35 5.2 Méthodes à noyau classiques : non paramétriques 37 5.2.1 L’algorithme des k plus proches voisins (KNN) 37 5.2.2 La régression à noyau: l’estimateur de Nadaraya-Watson . 37 5.2.3 Les fenêtres de Parzen pour l’estimation de densité . . . . 38 5.3 Les méthodes à noyau “modernes” 39 5.3.1 Les machines à vecteurs de support (SVM) linéaires . 39 5.3.2 Du linéaire au non-linéaire 40 5.3.3 L’astuce du noyau 42 5.3.4 Utilisation de l’astuce uploads/Litterature/ vincent-pascal-2003-these.pdf