Remerciez-le!

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

ÉCOLE DE TECHNOLOGIE SUPÉRIEURE UNIVERSITÉ DU QUÉBEC MÉMOIRE PRÉSENTÉ À L'ÉCOLE

ÉCOLE DE TECHNOLOGIE SUPÉRIEURE UNIVERSITÉ DU QUÉBEC MÉMOIRE PRÉSENTÉ À L'ÉCOLE DE TECHNOLOGIE SUPÉRIEURE COMME EXIGENCE PARTIELLE À L'OBTENTION DE LA MAÎTRISE EN GÉNIE DE LA PRODUCTION AUTOMATISÉE M.Ing. PAR MATHIAS MAHOUSONZOU ADANKON OPTIMISATION DE RESSOURCES POUR LA SÉLECTION DE MODELE DES SVM MONTRÉAL, LE 16 SEPTEMBRE 2005 (c) droits réservés de Mathias Mahouzonsou Adankon CE MÉMOIRE A ÉTÉ ÉVALUÉ PAR UN JURY COMPOSÉ DE : M. Mohamed Cheriet, directeur de mémoire Département de génie de la production automatisée à l'École de technologie supérieure M. Richard Lepage, président du jury Département de génie de la production automatisée à l'École de technologie supérieure M. Alain Biem, examinateur externe IBM at Watson Research Center, N.Y, USA IL A FAIT L'OBJET D'UNE SOUTENANCE DEVANT JURY ET PUBLIC LE 5 AOÛT 2005 À L'ÉCOLE DE TECHNOLOGIE SUPÉRIEURE OPTIMISATION DE RESSOURCES POUR LA SÉLECTION DE MODELE DES SVM Mathias Mahouzonsou Adankon SOMMAIRE La sélection de modèle, optimisation des hyper-paramètres, est une étape très importante pour garantir une forte performance aux SVM. Cette sélection est souvent réalisée par la minimisation d'un estimé de l'erreur en généralisation basé sur les bornes du "leave-one- out" comme le "radius-margin bound" et sur certaines mesures de performance comme GACV(Generalized Approximate Cross Validation), l'erreur empirique, etc. Ces méthodes de sélection de modèle automatique nécessitent l'inversion de la matrice de Gram-Schmidt ou la résolution d'un problème d'optimisation quadratique supplémentaire, ce qui est très coûteux en temps de calcul et en mémoire lorsque la taille de l'ensemble d'apprentissage devient importante. Dans ce mémoire, nous proposons une méthode rapide basée sur une approximation du gradient de l'erreur empirique avec une technique d'apprentissage incrémentai; ce qui réduit les ressources requises en tennes de temps de calcul et d'espace mémoire. Avec l'approximation du gradient, nous n'avons pas besoin d'inverser la matrice de Gram- Schmidt avant de calculer le gradient de l'erreur empirique. L'apprentissage incrémentai, quant à lui, permet d'optimiser de façon parallèle les paramètres et les hyper-paramètres de la machine, afin de réduire le temps de calcul. Notre méthode testée sur des bases de données synthétiques et réelles a produit des résultats probants confirmant notre approche. En outre, nous avons noté que le gain de temps s'accroît lorsque la taille de l'ensemble d'apprentissage devient large, ce qui rend notre méthode intéressante dans le cas des applications réelles. Nous avons aussi développé une nouvelle expression pour les SVM avec la formulation de la marge molle «soft margin» Ll, ce qui permet d'inclure 1 'hyper-paramètre C dans les paramètres du noyau. Ainsi, nous pouvons résoudre le problème de la différentiation de C et dans certains cas réduire le nombre des hyper-paramètres dans la sélection de modèle. OPTIMIZING RESOURCES IN MODEL SELECTION FOR SVM Mathias Mahouzonsou Adankon ABSTRACT Tuning SVM hyperparameters is an important step for achieving a high-perfmmance learning machine. This is usually done by minimizing an estimate of generalization error based on the bounds of the leave-one-out (loo) as radius-margin bound and on the perfotmance measure as GACV, empirical error, etc. These usual automatic methods used to tune the hyperparameters require an inversion of the Gram-Schmidt matrix or a resolution of an extra quadratic programming problem. In the case of a large dataset these methods require the addition of huge amounts of memory and a long CPU time to the already significant resources used in the SVM training. In this dissertation, we propose a fast method based on an approximation of the gradient of the empirical error along with incrementai learning, which reduces the resources required both in terms of processing time and of storage space. With the gradient approximation, we do not need to invert the Gram-Schmidt matrix for computing the gradient of the empirical error. The incrementai learning makes it possible to optimize both the parameters of the SVM and the hyperparameters and to drastically save on computing time. We tested our method on many benchmarks which have produced promising results confirming our approach. Furthermore, we notice that the gain time increases when the dataset is large. We also develop a new expression for SVM with Ll soft-margin formulation that makes it possible to include the hyper-parameter C in the kemel parameters. Then, we can resolve the problem of C differentiation and in certain cases reduce the number of the hyperparameters for model selection. REMERCIEMENTS J'adresse toute ma reconnaissance au PCBF-ACDI, pour le soutien financier, sans lequel ce travail n'aurait pu être réalisé. Je tiens à remercier mon directeur de recherche, M. Mohamed Cheriet, professeur à l'École de Technologie Supérieure, pour son suivi, pour son soutien et pour ses vifs encouragements tout au long de ce mémoire de maîtrise. Je remercie également M. Alain Biem, chercheur Senior chez IBM à Watson pour s'être intéressé à mon travail et avoir accepté de faire partie de mon jury. Aussi, ma gratitude à M. Richard Lepage, professeur à l'École de Technologie Supérieure, qui a accepté de présider ce jury. Un grand merci à tous les membres du Laboratoire d'Imagerie, de la Vision et de l'Intelligence Artificielle pour leur sympathie et leur gentillesse. Enfin, je dédie ce travail à Pascaline et à toute ma famille pour leur soutien et leur encouragement. Que ces lignes leur témoignent toute ma reconnaissance. TABLE DES MATIÈRES Page SOMMAIRE ................................................................................................................ .i ABSTRACT ................................................................................................................. ii REMERCIEMENTS ........................................................................................................ iii TABLE DES MATIÈRES ............................................................................................... .iv LISTE DES TABLEAUX ............................................................................................... vii LISTE DES FIGURES ................................................................................................... viii LISTE DES ABRÉVIATIONS ET DES SIGLES ............................................................. x INTRODUCTION ............................................................................................................. 1 CHAPITRE 1 CLASSIFIEURS À NOYAUX ET SVM ................................................... 5 1.1 Introduction ..................................................................................................... 5 1.2 Méthodes des noyaux ...................................................................................... 6 1.2.1 Principe et Théorème de Mercer ..................................................................... 6 1.2.2 Propriétés des noyaux ..................................................................................... 7 1.2.3 Exemples des noyaux ...................................................................................... 8 1.3 Description de certains algorithmes utilisant la méthode des noyaux .......... 11 1.3.1 Kemel PCA ................................................................................................... 11 1.3.2 Kemel Fisher discriminant ............................................................................ l3 1.3.3 L'Analyse discriminante généralisée (GDA) ................................................ 14 1.3.4 Feature Vectors Selection (FVS) .................................................................. 17 1.3.5 Relevance Vector Machine (RVM) ............................................................. 19 1.4 Principe et Modélisation des SVM ............................................................... 21 1.4.1 Risque structurel et dimension VC ............................................................... 21 1.4.2 Principe des SVM: maximisation de la marge de séparation ....................... 24 1.4.3 SVM linéaire et séparable ............................................................................. 26 1.4.4 SVM linéaire et marge molle (cas non séparable) ........................................ 28 1.4.5 SVM non linéaire: "astuce du noyau" («kernel trick») ................................ 31 1.5 Algorithmes d'apprentissage des SVM ......................................................... 32 1.5.1 Méthode de décomposition ........................................................................... 32 1.5.2 Algorithme de Joachims : méthode de décomposition améliorée ................. 34 1.5.3 Optimisation séquentielle minimale : SMO .................................................. 35 1.6 Classification multi-classe avec les SVM ..................................................... 37 1.6.1 Approche un-contre-tous ............................................................................... 37 1.6.2 Approche un-contre-un ................................................................................. 38 1.7 Conclusion .................................................................................................... 39 v CHAPITRE 2 SÉLECTION DE MODÈLE POUR LES SVM: ÉTAT DE L'ART ....... .40 2.1 Introduction ................................................................................................... 40 2.2 Technique de la validation croisée ................................................................ 40 2.2.1 Théorie de la validation croisée .................................................................... 40 2.2.2 Validation croisée généralisée approchée (GACV) ..................................... .41 2.3 Bomes de "leave-one-out" pour les SVM .................................................... .42 2.3.1 Nombre de vecteurs de support .................................................................... .42 2.3.2 Bome de Jaakkola-Haussler ......................................................................... .43 2.3.3 Bome de Opper-Winter ................................................................................. 43 2.3.4 Bome de Joachims ........................................................................................ 44 2.3.5 Borne basée sur l'écartement des vecteurs de support .................................. 44 2.3.6 Borne "Rayon-Marge" ................................................................................... 45 2.4 Erreur empirique ........................................................................................... 46 2.5 Conclusion ................................................. , ................................................. 50 CHAPITRE 3 STRATÉGIES D'OPTIMISATION DES RESSOURCES ...................... 51 3.1 Introduction .......................................................................................... , ........ 51 3.2 Approximation du gradient de l'erreur empirique ........................................ 51 3.3 Optimisation des paramètres avec l'apprentissage incrémental.. .................. 61 3.3.1 Rappel des techniques d'apprentissage incrémental.. ................................... 61 3.3.2 Jumelage de l'apprentissage incrémentai avec la sélection de modèle ......... 63 3.4 Analyse de l'espace mémoire et de la complexité ........................................ 68 3.4.1 Espace mémoire ............................................................................................ 69 3.4.2 Coût de calcul ................................................................................................ 69 3.5 Conclusion .................................................................................................... 75 CHAPITRE 4 NOUVELLE FORMULATION DU SVM-Ll.. ....................................... 76 4.1 Introduction ................................................................................................... 76 4.2 Description de la nouvelle formulation ......................................................... 76 4.3 Équation de l'hyperplan de séparation avec la nouvelle formulation ........... 79 4.4 Propriétés de k(x;.xj) = Ck(xi.xj) ................................................................ 80 4.5 Avantages de cette nouvelle formulation pour la sélection de modèle ......... 83 4.6 Conclusion .................................................................................................... 83 CHAPITRE 5 EXPÉRIMENTATIONS ET DISCUSSIONS ......................................... 85 5.1 Introduction ................................................................................................... 85 5.2 Perfonnance de nos stratégies dans la sélection de modèle .......................... 85 5.2.1 Données artificielles ...................................................................................... 85 5.2.2 Benchmark UCI ............................................................................................ 86 5.2.3 Base de données MNIST ............................................................................... 88 5.3 Analyse des propriétés de nos stratégies ....................................................... 90 5.3.1 Impact de l'approximation du gradient.. ....................................................... 90 5.3.2 Impact de l'apprentissage incrémental.. ........................................................ 92 5.3.3 Impact global des deux stratégies en fonction de la taille ............................. 93 5.3.4 Impact de la taille initiale deS ...................................................................... 95 5.4 Expérimentation de ia nouvelle formulation du SVM-Ll ........................... 96 vi 5.5 Conclusion .................................................................................................... 99 CONCLUSION GÉNÉRALE ........................................................................................ 1 00 ANNEXES: 1. Détails du calcul du coût d'apprentissage .......................................................... 102 2. Calcul détaillé du coût d'estimation du gradient approché ................................ 104 3. Calcul détaillé du coût d'estimation du gradient total ....................................... 106 4. Comparaison des taux d'erreur par problème bidasse entre la nouvelle et 1' ancienne formulation ....................................................................................... 108 BIBLIOGRAPHIE ......................................... ................................................................ 110 LISTE DES TABLEAUX Page Tableau I Fonctions de couplage uploads/Industriel/ 2017-efs-ml-qest-2.pdf