Optimisation de ressources pour la sélection de modele des SVM

La reconnaissance de formes dont le but consiste à associer une étiquette (une classe) à une donnée qui peut se présenter sous forme d’une image ou d’un signal, est un axe fort important du domaine de l’intelligence artificielle, qui trouve application dans beaucoup de systèmes comme les interfaces visuelles, l’analyse de données, la bioinfom1atique, le multimédia, etc. Plusieurs méthodes ont été développées dans ce domaine, en particulier les réseaux de neurones avec le perceptron multicouche (MLP). Les réseaux de neurones ont fait l’ objet de nombreuses recherches et ont donné des résultats impressionnants comme moyen de prédiction. Et depuis longtemps, les perceptrons multicouches ont été utilisés avec succès pour résoudre de nombreux problèmes de classification. Mais, de plus en plus, avec la diversité des applications de reconnaissance de formes, plusieurs problèmes non linéaires faisant intervenir la classification sont rendus complexes. Ainsi, depuis quelques années, pour contourner la complexité des fonctions de décision construites pour les problèmes non linéaires, les recherches ont donné naissance à de nouvelles méthodes de classification basées sur les noyaux (kemel methods) qui s’avèrent plus robustes et plus simples que d’autres méthodes telles que les couches cachées introduites dans les réseaux de neurones.

La méthode des noyaux est une technique récente en reconnaissance de formes. Elle consiste à projeter les données qui sont initialement non séparables dans un autre espace de dimension plus élevée où elles peuvent le devenir. Les classifieurs utilisant la méthode des noyaux, contrairement aux classifieurs traditionnels, construisent la fonction de décision dans un nouvel espace autre que 1′ espace des caractéristiques d’entrée; ce qui permet de réduire la complexité de la fonction de décision tout en gardant une bonne performance du classifieur. Les machines à vecteurs de support, issues des travaux de Vapnik, utilisent cette technique des noyaux qui permet de traiter linéairement dans le nouvel espace les problèmes préalablement non linéaires.

Les machines à vecteurs de support constituent une famille de classifieurs basés sur le principe du risque structurel qui leur confère un fort pouvoir de généralisation. La minimisation du risque structurel permet d’éviter le phénomène de sur-apprentissage des données à la convergence du processus d’apprentissage des machines de classification. Ainsi, le risque structurel permet de garantir une estimation moins biaisée du risque réel. Cependant, le choix des hyper-paramètres (les paramètres du noyaux et la valeur de pénalisation des variables d’écarts) définissant l’architecture d’une SVM affecte de façon significative sa performance. Alors, il faut utiliser une bonne stratégie de sélection pour optimiser les valeurs des hyper-paramètres d’une SVM afin d’espérer une bonne performance.

Plusieurs travaux de sélection de modèle pour les machines à vecteurs de support ont été effectués. En 2001, Chapelle et al. [l] ont proposé pour la première fois une méthode automatique pour sélectionner les hyper-paramètres d’un SVM en se basant sur des bornes de l’erreur en généralisation dérivée de LOO (Leave-one-out). Il s’agit de la dimension VC donnant la borne «rayon-marge» (radius-margin) et celle mesurant l’écartement des vecteurs de support (span bound). Mais ces méthodes développées pour réaliser l ‘ajustement automatique des paramètres nécessitent l’inversion de la matrice de Gram-Schmidt des vecteurs de support et la résolution d’un problème d’optimisation quadratique additionnel, ce qui requiert un temps de calcul important et un espace mémoire non négligeable. En 2003, Kai-Min et al. [4] utilisent le même critère « radiusmargin » pour optimiser automatiquement les hyper paramètres sans inverser la matrice de Gram- Schmidt dans Je calcul du gradient, mais ils ne pouvaient pas se passer de la résolution du problème QP additionnel.

Récemment, un nouveau critère de sélection de modèle pour les SVM appelé l’erreur empirique a été développé par Ayat et al. [5, 6]. Cette méthode minimise l’erreur de généralisation à travers un ensemble de validation. Ce critère est une fonction linéaire simple qui ne nécessite guère la résolution d’un autre problème QP, à part celui de l’apprentissage du SVM. De plus, nous avons la dérivabilité de la fonction coût qui permet de quantifier l’erreur empirique. Cependant, l’apprentissage des machines à vecteurs de support demande d’importantes ressources en temps et en stockage au fur et à mesure que la base d’apprentissage devient large. Alors, cette procédure de sélection de modèle automatique, malgré qu’elle soit plus rapide et simple en complexité que les autres critères, reste coûteuse en temps de calcul et en espace mémoire pour de grandes bases de données.

L’Analyse discriminante généralisée (GDA) 

L’analyse discriminante linéaire (LDA) est une technique statistique. Cette méthode basée sur la minimisation de la variance intra-classe par rapport à la variance inter-classe a eu beaucoup de succès dans les problèmes de classification. Mais en ce qui concerne les problèmes non linéaires, la LDA n’est pas efficace. Cette limite  de la LDA fut franchie par l’approche des noyaux, puisque dans le « feature espace » les données qui n’étaient pas linéairement séparables peuvent le devenir. Cette nouvelle approche de discrimination a été développée par Baudat et al. dans [16].

L’analyse discriminante linéaire part de la connaissance de la partition en classes des individus d’une population et cherche les combinaisons linéaires des variables décrivant les individus, qui conduisent à la meilleure discrimination entre les classes. L’idée de base est de créer une méthode pour choisir parmi les combinaisons linéaires des variables celle qui maximise l’homogénéité de chaque classe. Une fois cette combinaison choisie, on procède à la projection des données sur les axes qui sont les plus discriminants suivant la variance inter-classe.

Classification multi-classe avec les SVM

Les machines à vecteurs de support traitent habituellement des problèmes bi-classes. Cependant, il existe des techniques de combinaison pour résoudre des problèmes multiclasses. Deux types d’approches sont souvent utilisés pour réaliser des classifieurs multiclasses à base des SVMs :
– l’ approche un-contre-un
– l’ approche un-contre-tous .

Approche un-contre-tous 

L’idée est de construire autant de SVMs que de classes où chaque SVM permet de séparer une classe de toutes les autres. Ainsi, pour un problème à c classes, il faut entraîner c SVMs qui seront ensuite couplés pour prendre des décisions lors du test. Le couplage naïf qui consiste à attribuer à une observation la classe dont la sortie du SVM est positive, n’est pas satisfaisant. Car pour certaines observations ambiguës, plusieurs sorties peuvent être positives.

Pour réaliser un bon couplage, il est recommandé de nonnaliser la sortie des SVMs ou de les convertir en mesure de probabilités. Ainsi, un exemple est associé à la classe du SVM ayant la plus forte valeur de sortie normalisée ou de probabilité.

Table des matières

INTRODUCTION
CHAPITRE 1 CLASSIFIEURS À NOYAUX ET SVM
1.1 Introduction
1.2 Méthodes des noyaux
1.2.1 Principe et Théorème de Mercer
1.2.2 Propriétés des noyaux
1.2.3 Exemples des noyaux
1.3 Description de certains algorithmes utilisant la méthode des noyaux
1.3.1 Kemel PCA
1.3.2 Kemel Fisher discriminant
1.3.3 L’Analyse discriminante généralisée (GDA)
1.3.4 Feature Vectors Selection (FVS)
1.3.5 Relevance Vector Machine (RVM)
1.4 Principe et Modélisation des SVM
1.4.1 Risque structurel et dimension VC
1.4.2 Principe des SVM: maximisation de la marge de séparation
1.4.3 SVM linéaire et séparable
1.4.4 SVM linéaire et marge molle (cas non séparable)
1.4.5 SVM non linéaire: « astuce du noyau » («kernel trick»)
1.5 Algorithmes d’apprentissage des SVM
1.5.1 Méthode de décomposition
1.5.2 Algorithme de Joachims : méthode de décomposition améliorée
1.5.3 Optimisation séquentielle minimale : SMO
1.6 Classification multi-classe avec les SVM
1.6.1 Approche un-contre-tous
1.6.2 Approche un-contre-un
1.7 Conclusion
CHAPITRE 2 SÉLECTION DE MODÈLE POUR LES SVM: ÉTAT DE L’ART
2.1 Introduction
2.2 Technique de la validation croisée
2.2.1 Théorie de la validation croisée
2.2.2 Validation croisée généralisée approchée (GACV)
2.3 Bomes de « leave-one-out » pour les SVM
2.3.1 Nombre de vecteurs de support
2.3.2 Bome de Jaakkola-Haussler
2.3.3 Bome de Opper-Winter
2.3.4 Bome de Joachims
2.3.5 Borne basée sur l’écartement des vecteurs de support
2.3.6 Borne « Rayon-Marge »
2.4 Erreur empirique
2.5 Conclusion
CHAPITRE 3 STRATÉGIES D’OPTIMISATION DES RESSOURCES
3.1 Introduction
3.2 Approximation du gradient de l’erreur empirique
3.3 Optimisation des paramètres avec l’apprentissage incrémental
3.3.1 Rappel des techniques d’apprentissage incrémental
3.3.2 Jumelage de l’apprentissage incrémentai avec la sélection de modèle
3.4 Analyse de l’espace mémoire et de la complexité
3.4.1 Espace mémoire
3.4.2 Coût de calcul
3.5 Conclusion
CHAPITRE 4 NOUVELLE FORMULATION DU SVM-Ll
4.1 Introduction
4.2 Description de la nouvelle formulation
4.3 Équation de l’hyperplan de séparation avec la nouvelle formulation
4.4 Propriétés de k(x;.xj) = Ck(xi.xj)
4.5 Avantages de cette nouvelle formulation pour la sélection de modèle
4.6 Conclusion
CHAPITRE 5 EXPÉRIMENTATIONS ET DISCUSSIONS
5.1 Introduction
5.2 Perfonnance de nos stratégies dans la sélection de modèle
5.2.1 Données artificielles
5.2.2 Benchmark UCI
5.2.3 Base de données MNIST
5.3 Analyse des propriétés de nos stratégies
5.3.1 Impact de l’approximation du gradient
5.3.2 Impact de l’apprentissage incrémental
5.3.3 Impact global des deux stratégies en fonction de la taille
5.3.4 Impact de la taille initiale deS
5.4 Expérimentation de ia nouvelle formulation du SVM-Ll
5.5 Conclusion
CONCLUSION GÉNÉRALE

Cours gratuitTélécharger le document complet

Télécharger aussi :

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *