these

Sujets

• informatique

Informations

• Publié par: Viod
• Nombre de lectures: 67
• Langue: Français

Extrait

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
c Pascal Vincent, 2003Université 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:
Balázs Kégl
président-rapporteur
Yoshua Bengio
directeur de recherche
Jean-Jules Brault
membre du jury
Sam Roweis
examinateur externe
Lael Parrott
représentant du doyen de la FESRé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, Kernel 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 secondiv
article, K-Local Hyperplane and Convex Distance Nearest Neighbor Algorithms,
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, Manifold
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-clé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.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 algorithms, 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 describes 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,
Kernel Matching 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 Algorithms, is a variation of the
nearest neighbors algorithm in which we define the distance between a point andvi
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 lo-
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 call upon the “kernel trick” in any
way, are able to perform as well or better than SVMs. Second, our results indicate
that in high dimension, much is to be gained by designing algorithms that take
into account the “manifold hypothesis”, i.e. that data might be more concentrated
along lower dimensional non linear sub-manifolds. This is so far the best hope we
have to beat the curse of dimensionality.
Keywords : kernel methods, non-parametric statistics, curse of dimensionality,
Support Vector Machines, sparsity, k nearest neighbors, Parzen windows.Table des matières
Résumé iii
Abstract v
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é . . . . . . . . . . . . . . . . . 8viii
1.3.2 L’apprentissage non-supervisé . . . . . . . . . . . . . . . 9
1.3.3 L par renforcement . . . . . . . . . . . . . 11
1.3.4 Inter-relations entre les techniques . . . . . . . . . . . . . 11
2 La généralisation : le grand défi de l’apprentissage 13
2.1 Mémoriser n’est pas généraliser . . . . . . . . . . . . . . . . . . 13
2.2 Notations et formalisation du problème . . . . . . . . . . . . . . 14
2.3 Mesure de la performance de généralisation . . . . . . . . . . . . 16
2.4 Quelques notions de théorie d’apprentissage . . . . . . . . . . . . 18
2.5 Pratiques courantes de contrôle de capacité . . . . . . . . . . . . 20
3 Une tentative de classification des algorithmes d’apprentissage 22
3.1 Les modèles génératifs . . . . . . . . . . . . . . . . . . . . . . . 23
3.2 Modélisation directe de la surface de décision . . . . . . . . . . . 24
3.3 Extraction progressive de caractéristiques . . . . . . . . . . . . . 25
3.4 Modèles basés sur des distances à des prototypes . . . . . . . . . 26
3.5 Valeur relative de cette taxonomie . . . . . . . . . . . . . . . . . 28
4 Les défis de la haute dimensionalité 29
4.1 Le fléau de la . . . . . . . . . . . . . . . . . . . . 30
4.2 Intuitions géométriques en haute dimension . . . . . . . . . . . . 30ix
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être