Soutenance mémoire
INTRODUCTION
La variabilité de l’écriture manuscrite permet de confronter les algorithmes de classification et d’apprentissage à des problèmes difficiles et réalistes. Les réseaux de neurones ont montré des résultats remarquables dans ce domaine. Mais la nécessité de performances élevées dans des applications réelles ont poussé la recherche vers des modèles de classification de plus en plus complexes. Ainsi, depuis le neurone formel jusqu’au Lenet5 de ATT [55], plusieurs générations de machines d’apprentissage ont vu le jour dans le but de classifier, de catégoriser ou de prédire des structures particulières dans les données. La classification de caractères constituait, par ailleurs, la principale application des machines d’apprentissage dont les différents travaux ont permis une nouvelle appréhension des modèles de classification. Dans le domaine de la reconnaissance du manuscrit, les premiers systèmes dits intelligents reconnaissaient déjà des caractères imprimés à l’aide du perceptron de Rosenblatt [83]. Par la suite, le besoin d’automatisation massive a donné lieu à toute une multitude d’applications dont la lecture de chèques bancaires, des adresses postales, des documents imprimés, etc. Jusqu’à très récemment, le perceptron multicouche (PMC) constituait le modèle de prédilection pour traiter diverses tâches d’apprentissage supervisé. Ce modèle est facile à construire et à entraîner, et a été efficacement adopté dans beaucoup de systèmes de reconnaissance de caractères. En 1979, Vapnik a mis au point le principe de la minimisation du risque structurel qui évite le sur-apprentissage des données à la convergence, contrairement au risque empirique qui représente un estimé optimiste de l’erreur et que minimise le PMC avec l’algorithme de rétro-propagation de gradient [119]. Depuis, le SVM (de l’anglais «Support Vector Machine») n’a cessé de susciter l’intérêt de plusieurs communautés de chercheurs de différents domaines d’expertise. Ainsi, Cortes et al. dans [27], Scholkopf et al. dans [88], et Burges et al. dans [22] ont appliqué le SVM à la reconnaissance de chiffres manuscrits isolés. Blanz et al. dans [17] ont utilisé le SVM pour la classification d’objets 2D de vues différentes. Schmidt et al. dans [86] ont exploré la tâche de reconnaissance d’ orateur. Osuna et al. ont développé un système de reconnaissance de visages [7 4]. Dans la plupart des cas, la performance du SVM égale ou dépasse celle des classifieurs classiques.
Motivation
Le SVM est un modèle discriminant qui tente de minimiser les erreurs d’apprentissage tout en maximisant la marge séparant les données des classes. La maximisation de la marge est une méthode de régularisation qui réduit la complexité du classifieur. Elle sert à pénaliser les paramètres du modèles de la même façon que la méthode du «weight decay» qui altère les poids de grande amplitude dans un PMC [43]. La pénalisation des paramètres du SVM dans le but de maximiser la marge est une méthode de sélection de modèle implicite à l’apprentissage. Ce processus produit un ensemble réduit de prototypes faisant partie de l’ensemble d’apprentissage qu’on appelle communément vecteurs de support. Son comportement est, par ailleurs, conditionné par le type du noyau utilisé et par les valeurs octroyées à ses paramètres. Le noyau d’un SVM est une fonction symétrique défini-positive qui permet de projeter les données dans un espace transformé de grande dimension dans lequel s’opère plus facilement la séparation des classes, de la même façon que les neurones cachés d’un PMC permettent de projeter les données entrées dans un espace de représentation dans lequel les poids de la couche de sortie définissent des fonction discriminantes linéaires des classes. Les valeurs des paramètres de noyaux affectent directement la complexité de la frontière de décision du classifieur. Aussi, ses valeurs influencent le nombre de vecteurs de support du classifieur. De nombreux travaux ont démontré la supériorité du SVM sur les méthodes discriminantes classiques telles que le PMC, le discriminant de Fisher, le réseau RBF, etc. Des versions modifiées du SVM permettent les meilleures performances sur plusieurs bases de données standards [55]. Sa robustesse vis à vis de la dimensionalité des données et son pouvoir accru de généralisation, font que le SVM est nettement plus avantageux. Le SVM compte principalement deux variantes : SVM LI et SVM L2. La première applique une pénalisation quasi-linéaire sur l’erreur d’apprentissage alors que la deuxième opère une pénalisation quadratique de l’erreur. Le SVM L2, de par sa règle d’inférence quadratique, est sensible aux données marginales dont l’effet peut biaiser notablement la solution du SVM surtout en l’absence d’une quantité suffisante de données. Aussi, dans un problème fortement débalancé (distribution a priori des classes non égales), l’influence des exemples de la classe majoritaire est magnifié au risque de négliger les exemples de la classe minoritaire. Le terme ‘amnésie’ est parfois utilisé pour désigner ce phénomène. Cependant, le SVM LI est moins sensible aux données marginales. Aussi, en présence de classes fortement débalancées, sa solution est plus robuste. Dans cette thèse, nous avons opté pour cette variante du SVM 1. Par ailleurs, le SVM est un classifieur binaire, qui ne traite habituellement que des données étiquetées par rapport à deux classes d’appartenance. Donc, traiter des données multiclasses comme c’est le cas en reconnaissance de chiffres, requiert la combinaison d’un ensemble de SVMs, chacun se spécialisant en une partie du problème. Parmi les schémas de combinaison les plus utilisés, on citera l’approche un-contre-tous et l’approche uncontre-un. La première consiste à entraîner chacun des classifieurs pour séparer une classe du restant des classes. La deuxième consiste à entraîner les SVMs afin d’obtenir toutes les frontières de décision séparant les classes une à une. Il en existe K(K-I)/2 pour un problème à K classes. D’autres schémas de décomposition permettent de considérer un plus grand nombre de classifieurs à combiner. Dietterich et al. montrent que la performance de l’ensemble dépend de son pouvoir à corriger les éventuelles erreurs de vote produits .
MACHINES À VECTEURS DE SUPPORT : ÉTAT DE L’ART
Introduction L’origine des machines à vecteurs de support (SVM) remonte à 1975 lorsque Vapnik et Chervonenkis proposèrent le principe du risque structurel et la dimension VC pour caractériser la capacité d’une machine d’apprentissage . A cette époque, ce principe n’a pas trouvé place et il n’existait pas encore un modèle de classification solidement appréhendé pour être utilisable. Il a fallu attendre jusqu’à l’an 1982 pour que Vapnik propose un premier classificateur basé sur la minimisation du risque structurel baptisé SVM [120]. Ce modèle était toutefois linéaire et l’on ne connaissait pas encore le moyen d’induire des frontières de décision non linéaires. En 1992, Boser et al. proposent d’introduire des noyaux non-linéaires pour étendre le SVM au cas non-linéaire [18]. En 1995, Cortes et al. proposent une version régularisée du SVM qui tolère les erreurs d’apprentissage tout en les pénalisant [27]. Depuis, les SVMs (le pluriel est utilisé pour désigner les différentes variantes du SVM) n’ont cessé de susciter l’intérêt de plusieurs communautés de chercheurs de différents domaines d’expertise. Par exemple, Cortes et al. dans [27], Scholkopf et al. [88], et Burges et al. [22] ont appliqué les SVM à la reconnaissance de chiffres manuscrits isolés, Blanz et al. [17] ont expérimenté le SVM sur des objets 2D de vues différentes. Schmidt et al. [86] ont exploré la tâche de reconnaissance d’orateur. Osuna et al. ont traité de la reconnaissance d’images de visages [74]. Dans la plupart des cas, la performance du SVM égale ou dépasse celle de modèles classiques déjà établis. L’estimation de densité de probabilité [128] et la décomposition ANOVA [102] ont été aussi explorées. D’autres auteurs ont aussi étudié l’apport de la connaissance a priori pour ce type de classificateurs. Ainsi, le SVM virtuel de Burges et al. améliorent la généralisation en appliquant un bruit spécifique à l’ensemble de vecteurs de support [22]. Smola et al. ainsi que Wahba ont mis en évidence la ressemblance entre le SVM et la théorie de régularisation [96, 37, 122]. Ils ont démontré qu’associer un noyau particulier à un SVM revient à considérer une pénalisation différente de l’erreur d’apprentissage en maximisant la marge. Ce qui nous permet de dire que la maximisation de la marge dans l’espace augmenté est une forme de régularisation de l’apprentissage. Dès lors, le SVM permet de répondre à deux problèmes centraux de la théorie de l’apprentissage statistique que sont:
– le contrôle de la capacité du classifieur,
– le sur-apprentissage des données.
KMOD
Un nouveau noyau pour la classification En général, nous ne connaissons pas la fonction qui transforme l’espace d’origine en un espace augmenté plus grand. L’existence d’une telle fonction pour un noyau donné est assurée néanmoins par le théorème de Mercer [28]. Ces noyaux expriment un produit scalaire dans l’espace augmenté. Ils appartiennent essentiellement à deux familles : 1. noyaux de projection prenant la forme k(x, y) = k(x.y), 2. noyaux de distance prenant forme k(x, y) = k (iix- vil). Dans la deuxième formulation, connaissant une estimation de la distance euclidienne entre deux points dans l’espace d’origine, nous obtenons leur degré de corrélation dans l’espace augmenté. Dans ce contexte, une question naturelle est : y a t-il un critère permettant de préférer un noyau à un autre ? Dans le RBF (Figure 4), la corrélation des points voisins dans l’espace augmenté est contrôlée par un seul paramètre qui est l’écart type CJ (Tableau III). Dans l’espace augmenté, les images des points très proches vont être hautement corrélées, alors que les images des points lointains vont être non corrélées. Ceci se traduit par une valeur du noyau égale à 1 pour une corrélation parfaite (distance nulle entre les points), et une corrélation nulle lorsque les points sont assez distants l’un de 1′ autre. S’il était possible de contrôler davantage la corrélation des points dans l’espace augmenté, il serait possible d’influencer la séparabilité des classes dans le SVM puisque celle-ci dépend du produit scalaire W.(x), où (x) est l’image de l’observation x par le noyau, et West le vecteur orthogonal au plan de séparation du SVM (celui-ci dépend de l’ensemble des vecteurs de support et de leurs multiplicateurs ai ). En particulier, il serait souhaitable d’assurer un compromis qui permette de contrôler la dynamique de la fonction de corrélation tout en préservant l’information sur le voisinage lointain. Cette propriété donnerait à l’algorithme le moyen de prendre en compte toute l’information de voisinage.
Analyse en Composantes Principales non-linéaire
L’Analyse en Composantes Principales (ACP) est une technique descriptive qui calcule les axes d’inertie d’un nuage de points (l’axe WpcA dans la figure 6 représente l’axe principal des points). Les axes d’inertie représentent des directions orthogonales suivant lesquelles la variance des données est maximale. Le terme «composante principale» est l’association d’une direction principale et de son amplitude. Les composantes principales est une solution au sens des moindres carrés qui revient à procéder à une rotation de l’ensemble des données suivie d’une translation. L’ ACP peut être utilisée pour réduire la dimensionalité des données en conservant uniquement un sous-ensemble des composantes principales. Toutefois, l’ ACP est une méthode linéaire qui ne détecte pas les structures non-linéaires des données. L’ ACP non linéaire rend possible l’extraction de ces propriétés grâce à l’utilisation de noyaux de Mercer de la même façon que dans le SVM ou le KFD.
|
Table des matières
ABSTRACT
REMERCIEMENTS
LISTE DES TABLEAUX
LISTE DES FIGURES
LISTE DES ABRÉVIATIONS ET SIGLES
CHAPITRE 1 INTRODUCTION
1.1 Motivation
1.2 Propositions
1.3 Organisation de la thèse
CHAPITRE 2 RECONNAISSANCE DE CARACTÈRES MANUSCRITS
2.1 Introduction
2.2 Reconnaissance de caractères
2.3 Extraction de caractéristiques
2.4 Classification par discrimination
2.4.1 Décision Bayesienne
2.4.2 Perceptron multicouche
2.4.3 Réseaux de fonctions à base radiale
2.4.4 Réseau à convolution
2.5 Conclusion
CHAPITRE 3 MACHINES À VECTEURS DE SUPPORT : ÉTAT DE L’ART
3.1 Introduction
3.2 Risque structurel
3.3 Espace augmenté
3.3.1 Noyau polynomial
3.4 KMOD : un nouveau noyau pour la classification
3.5 Formulation
3.5.1 Hyper-plans de séparation
3.5.2 Hyper-plans à marge optimale
3.5.3 Hyper-plans à marge molle
3.5.4 Le SVM non-linéaire
3.5.5 Conditions de Karush-Kuhn-Tucker
3.5.6 Calcul du biais b
3.5.7 Le v-SVM
3.6 Discriminant de Fisher non-linéaire (KFD)
3.7 Analyse en Composantes Principales non-linéaire
3.8 Classification mono-classe
3.8.1 Méthode de l’hyper-sphère
3.8.2 Méthode de l’hyper-plan
3.9 Algorithmes d’apprentissage du SVM
3.9.1 Méthode de chunking
3.9.2 Méthode de décomposition successive
3.9.3 Méthode de minimisation séquentielle : SMO
3.10 Algorithme de Joachims
3.10.1 Stratégie de décomposition
3.10.2 Sous-problème QP
3.10.3 Sélection de l’ensemble actif
3.11 Classification de données multiclasses
3.11.1 Approche Un-contre-Tous
3.11.2 Approche Un-contre-Un
3.11.3 Calcul des probabilités à posteriori des classes
3.11.4 Couplage optimal des classes
3.12 Conclusion
CHAPITRE 4 SÉLECTION DE MODÈLES POUR LES MACHINES À VECTEURS DE SUPPORT : ÉTAT DE L’ART
4.1 Introduction
4.2 Sélection de modèles
4.2.1 Approche par erreur de validation
4.2.2 Approche algébrique
4.2.3 Approche bayesienne
4.2.4 Approche par minimisation du risque structurel
4.3 Critères d’optimisation du SVM
4.3.1 Ensemble de validation
4.3.2 Nombre de vecteurs de support
4.3.3 Borne de Jaakkola-Haussler
4.3.4 Borne de Opper-Winther
4.3.5 Dimension VC
4.3.6 Borne de Joachim
4.3.7 Portée des vecteurs de support ( «Span bound»)
4.3.8 Erreur de Validation Croisée Généralisée- GACV
4.4 Conclusion
CHAPITRE 5 OPTIMISATION DES HYPER-PARAMÈTRES DU SVM : CAS BICLASSE
5.1 Introduction
5.2 Minimisation de la dimension VC
5.2.1 Algorithme
5.3 Minimisation de l’Erreur Empirique
5.3.1 Critère d’optimisation
5.3.2 Estimation de la probabilité à posteriori
5.3.3 Algorithme
5.3.4 Accélération par la méthode de Quasi-Newton
5.4 Minimisation de l’Erreur de Validation Croisée Généralisée (GACV)
5.4.1 Algorithme
5.5 Conclusion
CHAPITRE 6 OPTIMISATION DES HYPER-PARAMÈTRES DU SVM : CAS MULTICLASSE
6.1 Introduction
6.2 Optimisation locale des hyper-paramètres de SVM
6.3 Optimisation globale des hyper-paramètres de SVM
6.3.1 Minimisation de l’erreur multiclasse
6.4 Conclusion
CHAPITRE 7 EXPÉRIMENTATION : SÉLECTION DE MODÈLES POUR DES DONNÉES BICLASSES
7.1 Introduction
7.2 Données synthétiques bidasses
7.2.1 Minimisation de la dimension VC
7.2.2 Minimisation du GACV
7.2.3 Minimisation de l’erreur empirique
7.3 Étude expérimentale
7.3.1 Problème GAUSS2
7.3.2 Problème XOR
7.3.3 Influence de la taille de l’ensemble de validation
7.4 Conclusion
CHAPITRE 8 EXPÉRIMENTATION: OPTIMISATION DE SVMS SUR DES DONNÉES MULTICLASSES
8.1 Données synthétiques multiclasse
8.2 Reconnaissance d’images de chiffres manuscrits arabes
8.2.1 La base de données de USPS
8.2.2 Minimisation de l’erreur empirique
8.3 La base de données de chiffres indiens
8.3.1 Primitives perceptuelles
8.3.2 Primitives statistiques
8.3.3 Expériences
8.3.4 Analyse des résultats
8.4 Conclusion
CHAPITRE 9 CONCLUSION GÉNÉRALE
9.1 Contributions majeures
9.2 Perspectives
BIBLIOGRAPHIE
Télécharger le rapport complet
