Utilisation des Machines à Vecteurs de Support (SVM) pour la reconnaissance des chiffres manuscrits

REPUBLIQUE ALGERIENNE DEMOCRATIQUE ET POPULAIRE
Ministère de l'Enseignement Supérieur et de laRecherche Scientifique

Université des Sciences et de la Technologie Houari Boumediene



Faculté d'Electronique et Informatique

Département Instrumentation et Automatique

Mémoire de Projet de Fin d'Etudes d'Ingénieur d'Etat en Electronique

Option : Contrôle

THEME

Utilisation des Machines à Vecteurs de Support (SVM)
pour la reconnaissance des chiffres manuscrits.

Proposé et dirigé par : Présenté par :

Melle. NEMMOUR Hassiba Mr. DIBOUNE Rabah

Mr. CHIBANI Youcef Mr. FELLAH Hassen

Soutenu le Devant le jury com posé de :

Président :

Examinateur :

Promoteur :

Co-promoteur :

Promotion: 2006-2007

Remerciements

Nous remercions El laah de nous avoir donné la volonté et le courage qui nous ont permis de
réaliser ce travail, veuille t-il nous guider dans le droit chemin.

Nous aimons spécialement remercier Mlle H.NEMMOUR et Mr V. CHIBANI, qui nous ont
proposé ce suj et , pour leur grandes disponibilité pendant toute la durée de ce travail, pour
nous avoir toujours encouragé face à la difficulté , mais aussi pour leur gentillesse et leur
hospitalité.

Nous remercions aussi les membres de jury pour avoir accepter de juger notre travail.

Pour terminer, nous remercions toute personne ayant participé de prés ou de loin pour la
réalisation de ce travail.

Dédicaces

A mes très chers parents qui ont toujours été la pour moi, et qui m 'ont donné un magnifique
modèle de labeur et de persévérance et tout mon amour ;
A ma grand -mère khadudja qui a beaucoup sacrifie tout au long de ma vie, qu 'El laah la
pardonne
A mes oncles ;
A mes chers frères et soeurs : Mounir, Mehdi, Islam, Salim ;
A tous mes amis : Hichem, Djamel, Abd el hak , Mbarek, Abd el fattah, Mourad
,Soufianne,... ;
Je dédie ce mémoire

Rabah

A mes très chers parents qui ont toujours été la pour moi, et qui m 'ont donné un magnifique
modèle de labeur et de persévérance et tout mon amour ;
A ma grand -mère Haffssa qui a beaucoup sacrifie tout au long de ma vie, qu 'El laah la
pardonne
A mes oncles ;
A mes chers frères et soeurs : Mohamed, Kamel, Hossine, Salim ;
A tous mes amis : Hichem, Billel, Oualid , Ayman,Hamza , Mohamed ... ;
Je dédie ce mémoire

Tables des Matières

Introduction Générale 1
CHAPITRE 1

Reconnaissance des Chiffres Manuscrits

1. 1.Introduction ..3

1.2. System standard de reconnaissance des chiffres manuscrits ...4

1.2.1 Acquisition de l'image 5

1.2.2. Prétraitement ..5

1.2.2.1. Binarisation de l'image ...5

1.2.2.2. Elimination du bruit ......6

1.2.2.3. Segmentation des chiffres 6

1.2.2.4. Normalisation de l'image.. 6

1.2.3. Classification 7

1.2.4. Post-traitement: ...7

1.3. Méthodes de classification 7

1.3.1 Réseaux de neurones 8

1.3.2 Support Vecteur Machine (Machines à Vecteur de Support) 9

1.4. Conclusion 9

CHAPITRE 2

Machines a Vecteurs de Support

2.1. Introduction 10

2.2. Formulation mathématique des SVMs 10

2.2.1. Principe 10

2. 2.2. Données linéairement séparables .10

2.2.3. Données non linéairement séparable .13

2.2.3.1. Fonction noyau 15
2.2.3.2. Conditions de Mercer.........................................................................16

2.2.3.3. Exemples de noyaux	17
2.3. Implémentation multiclasse	..18
2. 3.1. Un contre tous (OAA : One Against All)	...18
2. 3.2. Un contre un (OAO : One Against One)	19
2.4. Méthode d'entrainement des SVMs	..19
2.4.1. Optimisation minimale et séquentielle SMO	....20
2.4.1.1. Fonctionnement de l'algorithme SMO	.21
2. 4.1.1.1. Optimisation analytique des multiplieurs du lagrangien	24
2. 4.1.1.2. Choix des multiplieurs du Lagrangien	...25
2.4.1.1.3. Mise à jour du seuil b	26
2. 4.1.1.4. Mise à jour de l'erreur	26
2.4.1.2. Pseudo code de l'algorithme SMO	..26
2.5. Conclusion	..30

Chapitre 3

Résultats Expérimentaux

3.1. Introduction	31
3.2. Critères d'évaluations	......31
3.1.1. Base de données USPS	.31
3.1.2. Matrice de confusion	.32
3.3. Apprentissage des SVMs	33
3.3.1. Réglage des paramètres	33
3.3.1.1. Paramètre de régularisation C	33
3.3.1.2 .Réglage des seuils de Tolérance et å	34
3.3.2. Choix du noyau	34
3.4. Classification binaire	34
3.4.1. Choix des pairs de classes	34
3.4.2. Evaluations	.34
3.4.3. Comparaison des résultats et discussions	37
3.5. Classification multi classe	..38

3.5.1. Evaluations 38
3.5.2. Comparaison des résultats et discussions .....................................................44

3.6. Comparaison classification binaire et multi-classe 3.7. Présentation de la plateforme	..47 .47
3.7.1. Fenêtre principale	47
3.7.2 Menu	48
3.7.2.1. Sélection des fichiers	48
3.7.2.2. Sélection des paramètres pour l 'apprentissage	49
3.7.2.3. Evaluation de la classification	.50

3.8. Conclusion 54

Conclusion Générale 55

Références Bibliographies ....A

Liste des figures et des tableaux

Figure 1.1 .Exemple des chiffres séparés	.4
Figure 1 .2.Exemple des chiffres touchés	...4
Figure 1.3.Diagrame des étapes principales de system de reconnaisance standard	5
Figure 1.4.Exemple de segmention des chiffres manuscrits	.6
Figure 1 .5.Exemple des chiffres manuscrits normalisées	6
Figure 1.6. Apprentissage supervisé d'une machine.	.8
Figure 2.1. Hyperplan de séparation linéaire pour des données linéairement séparables ...	11
Figure 2.2 .Hyperplan de séparation linéaire pour des données non linéairement séparables......	13

Figure 2.3.Exemple d'une application CP rendant les données linéairement séparables

15

Figure 2.4. Schéma synoptique de l'implémentation Un Contre Tous 19

Figure 2.5. Deux cas d'optimisations 21
Figure 2.6. Quand les deux multiplieurs sont égaux à la bande C : les vecteurs de support 2 et

r donnent le même seuil b. Les points 8 et _?fournissentè les seuils b1 et b2 respectivement. Les

points d'erreur et le seuil b se trouve entre b1 et b2 26

Figure 3.1.Représentation de la base USPS 31

Figure 3.2. Exemple d'une matrice de confusion .33
Figure 3.3.Taux de bonne reconnaissance(%) pour chaque classe pour différents valeurs du

paramètre du noyau RBF ...45
Figure 3.4.Taux de bonne reconnaissance(%) pour chaque classe pour différents valeurs du

paramètre du noyau Polynomial .45
Figure 3.5.Taux de bonne reconnaissance(%) pour chaque classe pour différents valeurs du

paramètre du noyau KMOD (a =6) 46
Figure 3.6.Taux de bonne reconnaissance(%) pour chaque classe pour différents valeurs du

paramètre du noyau Distance négative ..46

Figure 3.7. Fenêtre principale ...47
Figure 3.8. Rubriques de menu Fichier..48

Figure 3.9. Exemple de chargement de la base d'apprentissage 48

Figure 3.10. Rubriques de menu Apprentis sage ..49

Figure 3.11. Exemple de choix de noyau et les paramètres pour la classification multiclasse.....49 Figure 3.12. Exemple de choix de noyau et réglage des paramètres avec possibilité de sélectionner

deux classes pour la classification biclasse ..50

Figure 3.13. Rubriques de menu Test 51

Figure 3.14.Matrice de confusion avec précision globale ...51
Figure 3.15. Taux de bonne reconnaissance pour chaque classe représenté sous forme

graphique 52
Figure 3.16. Taux de bonne reconnaissance pour déférentes classes représenté sous forme d'une

matrice de confusion et graphique. 53

Figure 3.17.Résumé des résultats ...54

Tableau 2.1. Exemples de noyaux 17
Tableau 3.1. Échantillon représentant la première dizaine d'images binarisées et leurs étiquettes

dans la base de données USPS 32

Tableau 3.2.Matrices de confusion pour les paires de classes (9 ,4) pour chaque type de noyau 35
Tableau 3.3.Matrices de confusion pour les paires de classes (5 ,6) pour chaque type

de noyau 36
Tableau 3.4.Matrices de confusion pour les paires de classes (7 ,1) pour chaque type de noyau .37

Tableau 3.5.Taux global de bonne reconnaissance pour les trois paires de classes (9,4), (7,1) et (5,6) .37

Tableau 3.6.Matrice de confusion de la classification multi classe pour le noyau RBF (ó =3)... .38

Tableau 3.7.Matrice de confusion de la classification multi classe le noyau RBF (ó =10) 39

Tableau 3.8.Matrice de confusion de la classification multi classe le noyau RBF (ó =25) 39

Tableau 3.9.Matrice de confusion de la classification multi classe pour le noyau Polynomial (p=1) 40
Tableau 3.10.Matrice de confusion de la classification multi classe pour le noyau Polynomial

(p=2) 40
Tableau 3.11 .Matrice de confusion de la classification multi classe pour le noyau Polynomial

(p=3) 41
Tableau 3.12.Matrice de confusion de la classification multi classe pour le noyau KMOD ã =0.2

et ó=6 41

Tableau 3.13.Matrice de confusion de la classification multi classe pour le noyau KMOD ã =0.5

et ó=6 .......................................................................................................................42 Tableau 3. 14.Matrice de confusion de la classification multi classe pour le noyau Distance négative ã =0.2 42

Tableau 3.15.Matrice de confusion de la classification multi classe pour le noyau Distance négative ã=0.1 43

Tableau 3.16.Matrice de confusion de la classification multi classe pour le noyau Distance négative ã=0.05 43

Tableau 3.1 7.Résumé des résultats pour la classification multi classe .........44

Introduction générale

Depuis plusieurs années, de nombreux travaux de recherche ont porté sur la reconnaissance des chiffres manuscrits. Deux grandes classes d'application sont aujourd'hui à l'étude : les applications bancaires ou postales, qualifiés de hors lignes ou statiques par exemple en France, deux millions de chèques sont lus chaque jour sans intervention humaine et les applications destinés à la bureautique, qualifiés de en lignes ou dynamiques ou temps réel (voir [8] et respectivement [4] pour des exemples).

Dans ce mémoire, nous nous intéressons à la reconnaissance des chiffres manuscrits hors - ligne qui reste aujourd'hui un thème de recherche ouvert. En effet, bien que le nombre de classes naturelles soit très réduit (chiffres '0' à '9'), on trouve à l'intérieur de chacune d'entre elles, une très grande variabilité de l'écriture, de plus, les conditions souvent relativement précaires dans les quelles sont écrits les chiffres (chèques écrits rapidement sur un coin de table) et la variabilité du matériel utilisé (utilisation de divers stylos, de différentes qualités de papier) tendent à complexifier la reconnaissance.

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. Mais la plupart de ces techniques éprouvent de grandes difficultés à traiter les données de très haute dimension. Pour surmonter ce problème, on procède souvent par la sélection d'une partie des attributs des données pour réduire la dimension de l'espace d'entrée. Mais dans ce cas on aura besoin d'utiliser des hypothèses simplificatrices qui ne se vérifient pas toujours en pratique. Par ailleurs, une méthode issue récemment d'une formulation de la théorie de l'apprentissage statistique due en grande partie à l'ouvrage de Vapnik en 1995 intitulé the nature of learning statistical theory [27] surmonte ce problème en imposant que le nombre de paramètres soit linéairement lié au nombre des données d'apprentissage. Cette technique est appelée Support Vector Machines (SVM) ou machines à vecteurs de support. Bien que récemment proposée, elle a fait l'objet d'un nombre important de publications.

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.

De nombreux travaux ont démontré la supériorité du SVM sur les méthodes discriminantes classiques. Sa robustesse vis-à-vis de la dimensionnalité des données et son pouvoir accru de

généralisation, font que le SVM est nettement plus avantageux [20]. Le succès de cette méthode est justifié par les solides bases théoriques qui la soutiennent.

L'objet de ce mémoire est l'implémentations des SVMs pour la reconnaissance des chiffres manuscrits . Il est organisé en trois chapitres. Le premier chapitre présente les différents blocs, schéma standard de reconnaissance des chiffres manuscrits en mettant l'accent plus précisément sur le bloc classifieur.

Le deuxième chapitre décrit en détail le concept ainsi que la formulation mathématique des SVMs. Pour résoudre le problème d'optimisation des SVMs, une description détaillée de l'algorithme SMO est également présentée dans ce chapitre.

Le troisième chapitre décrit les différentes expériences réalisées sur une base de données de chiffres manuscrits. Les expériences sont réalisées pour une classification binaire puis multiclasse sans oublier l'interface que nous avons développée sous environnement Windows avec le logiciel matlab 6.5 et qui porte le nom « RCSVM ».

Dans la conclusion, nous rappelons l'objectif ainsi que les perspectives de ce travail.



Reconnaissance des Chiffres

Manuscrits

1. 1.Introduction

Durant les vingt cinq dernières années, la lecture optique et la reconnaissance d'écriture manuscrite ont été des domaines de recherches actifs et ont fait l'objet de nombreuses publications. [11] [14] [28] [26] [22] [17] [19] [3] [6]. En effet, le problème de la reconnaissance de caractères manuscrits n'est pas encore parfaitement résolu bien que l'on sache atteindre des taux de reconnaissance supérieure à 90% dans diverses applications, telle que la reconnaissance des 10 chiffres manuscrits. Dans ce sujet de reconnaissance, deux grandes classes de systèmes sont aujourd'hui à l'étude

- Les systèmes pour les applications bancaires ou postales, qualifiés de hors-ligne ou statique. Dans ce cas, il s'agit de réaliser un système pour lire le montant d'un chèque ou pour lire une adresse postale sur une enveloppe, les informations transmises au système seront les pixels d'une image acquise à l'aide d'un scanner.

- Les systèmes destinés à la bureautique, qualifiés de en ligne ou dynamique ou temps réel. Dans ce cas, il s'agit de saisir un texte avec un stylo et une table à digitaliser pour le transmettre à un traitement de texte, les informations se présenteront sous forme d'une suite de points arrivant dans un ordre bien déterminé, information qui sera importante pour la classification [25]. Dans le domaine de reconnaissance, il faut faire une nette distinction entre texte imprimé ou dactylographié et texte manuscrit. Si dans le premier cas, on peut considérer que les principales difficultés ont été surmontées, la situation est entièrement différente en ce qui concerne la reconnaissance d'un manuscrit que nous présenterons dans ce présent chapitre pour le cas des chiffres, où les difficultés resteront celles de la variabilité de l'écriture [9]. Ces variations dépendent en général aussi bien du scripteur que de l'environnement de l'écriture. En effet, la variabilité mett ant en jeu le scripteur peut provenir de l'inclinaison des caractères, de l'inclinaison de la ligne de base des chiffres vue que des différents directions de ligne peuvent coexister sur une même page du fait de changements d'orientation de la feuille en cours d'écriture, etc. [16]. La variabilité liée à l'environnement d'écriture correspond par exemple à la variation de l'épaisseur des traits en fonction du type de stylo utilisé et du support d'écriture disponible, ou à la présence plus ou moins importante de discontinuités [2].

Dans notre mémoire, nous intéressons au problème de reconnaissance d'écriture manuscrite hors-ligne, qui demeure un problème difficile car l'entrée de ces systèmes est une image. D'autres problèmes doivent également surmontés comme par exemple, comment on peut enlever le bruit comme des éléments du fond d'image, comment on peut traiter le manque des

traits etc. De plus, il n'y a pas d'information supplémentaire comme le cas d'en-ligne. D'ailleurs, pour être utilisés largement, ces systèmes doivent traiter rapidement avec le taux de reconnaissance élevé.

Par contre dans le cas de reconnaissance en ligne l'utilisateur écrit sur une table spéciale, il y a moins de bruit. De plus, on peut déterminer comment un caractère est écrit, c'est à dire, l'ordre de traits constituants ce caractère. D'ailleurs, la contrainte du temps de reconnaissance n'est pas stricte, on peut utiliser des algorithmes complexes. C'est pour quoi le taux de reconnaissance de ces systèmes est assez élevé. [18]

Il faut distinguer deux types d'écriture manuscrite hors-ligne. Dans le premier cas, chaque chiffre est séparé par l'utilisateur. Par exemple, chaque chiffre est écrit dans une boîte comme dans la figure suivante :



Figure 1.1 .Exemple des chiffres séparés.

Ce problème est bien résolu. Les algorithmes utilisés sont souvent des SVM (Support Vector Machine), réseau de neurones etc. [18]



Figure 1 .2.Exemple des chiffres touchés.

Dans le deuxième cas, les chiffres sont écrits normalement, c'est à dire, les chiffres se sont touchés. C'est à notre système de séparer ces caractères. Le problème devient plus difficile. Dorénavant, quand on parle d'écriture manuscrite, on aborde le deuxième cas.

1.2. System standard de reconnaissance des chiffres manuscrits

Le diagramme suivant montre les étapes principales du processus de reconnaissance d'écriture manuscrit hors-ligne.

Image Classe



PRE-TRAITE M ENT

Figure 1.3. System standard de reconnaisance des chiffres manuscrits.

La démarche classique suivie en reconnaissance de chiffres manuscrits consiste à opérer selon les étapes suivantes :

1.2.1 Acquisition de l'image

L'écriture est digitalisée par un scanner pour être transformer en une image. Ceci correspond à l'entrée du système. Cette étape est assez simple mais très importante car elle influence sérieusement les étapes suivantes. Deux paramètres importants doivent être

pris en compte :

· Résolution : la résolution normale est de 300 dpi (dot per inch : points par pouce). Cependant, dans certains cas, lorsque la taille de l'écriture est petite, il est nécessaire d'augmenter la résolution pour tenir compte de la finesse de l'écriture.

· Niveau d'éclairage : l'éclairage influe également sur la qualité de la reconnaissance. Trop faible, le bruit devient important .Trop fort, le bruit est réduit mais les traits fins disparaissent.

1.2.2. Prétraitement

Cette étape prépare l'image entrée pour l'étape de reconnaissance. Elle essaie d'effacer les informations indésirables comme le bruit. Les opérations typiques regroupent la binarisation, élimination du bruit, segmentation en chiffres isolés, normalisation et squelettisation.

1.2.2.1. Binarisation de l'image

L'image entrée est représentée en niveau de gris et les algorithmes de reconnaissance courants travaillent souvent sur des images binaires. Donc, il faut appliquer un seuillage. Cependant, quand le fond est très compliqué, cela devient un problème difficile au cas où l'éclairage varie dans l'image entrée, on peut appliquer des techniques comme seuillage adaptatif [18].

1.2.2.2. Elimination du bruit

Le problème du bruit est très important mais très difficile particulièrement dans le cas où l'utilisateur écrit sur une feuille ayant le fond complexe comme un chèque de banque. Une technique simple est de faire la soustraction entre l'image entrée et l'image d'un chèque blanc (Il n'y a pas d'écriture). Cependant, les deux images doivent être alignées et les parties d'écriture qui traversent les éléments du fond vont être enlevées. La reconnaissance d'écriture sur un chèque de banque reste encore un défi [18].

.

1.2.2.3. Segmentation des chiffres

La segmentation consiste à séparer les chiffres les uns des autres. La difficulté de cette étape réside dans le fait que les chiffres ne sont pas alignés et ne présentent pas la même taille, de plus, dans certains cas, les chiffres se chevauchent. Par conséquents, il faut utiliser des techniques de séparation permettant d'isoler les chiffres [23].



Figure 1 .4.Exemple de segmention des chiffres manuscrits

1.2.2.4. Normalisation de l'image

Pour faciliter l'étape de reconnaissance, les chiffres segmentés doivent être normalisées à une taille fixée. La contrainte principale réside dans le choix de cette taille. Trop petite, il y a un risque d'une perte d'information. Trop grande, l'étape de reconnaissance va opérer lentement.



Figure 1 .5.Exemple des chiffres manuscrits normalisées

1.2.3. Classification

La classification consiste à affecter une forme donnée à une classe prédéfinie. Cette phase regroupe les deux taches d'apprentissage et de décision. En effet, à partir de la même description de la forme en paramètres, elles tentent, toutes les deux d'attribuer cette forme à un modèle de référence. Le résultat de l'apprentissage est soit la réorganisation ou le renforcement des modèles existants en tenant compte de l'apport de la nouvelle forme soit la création d'un nouveau modèle de l'apprentissage. Le résultat de la décision est un « avis » sur l'appartenance ou non de la forme aux modèles de l'apprentissage. [1] [24]

1.2.4 Post-traitement

Le post-traitement permet la validation des décisions de l'analyse sur la base de connaissances (du domaine). Cette étape aide à réduire considérablement des erreurs. Cependant, ce n'est pas une étape complètement séparée des étapes précédentes. [7]

1.3. Méthodes de classification

Généralement, un système de reconnaissance est construit à partir des connaissances a priori sur le problème. Le fait de classer un objet correspond donc à prendre une décision sur base d'une ou plusieurs règles. Dès lors, une des premières approches pour automatiser le traitement, fut d'extraire la connaissance experte de spécialistes sous forme de règles. Ainsi, pour chaque catégorie, on disposait d'un ensemble de règles permett ant de déterminer l'appartenance d'un objet à la-dite catégorie (ou classe). Bien que cette façon ait été largement utilisée jusqu'à la fin des années 80, on en conçoit aisément les limites. En effet, quand le nombre d'exemples et de classes est très important, il devient difficile de rassembler toutes les connaissances expertes nécessaires aux prises de décision. Dans les années 90, l'approche Machine Learning (ML) ou apprentissage machine devient très populaire. Il s'agit d'apprendre automatiquement les règles de décision sur base d'un ensemble d'exemples déjà classés.

L'apprentissage machine inclut entre autres les méthodes supervisées et non supervisées.

Dans les techniques non-supervisées, les objets sont présentés sans leur catégorie. Un exemple type de méthodes non-supervisées est le clustering dont le but est de créer des groupes (clusters) d'objets présentant des caractéristiques semblables.

Dans le cas des méthodes supervisées, on cherche à estimer une fonction f(x) à partir des exemples x, comme l'indique la figure ci-dessous. [15]



x,y = f(x)



Machine

f^~(x)

x,y = f(x) : Une donnée et son étiquette
f^~(x) est une estimation de f(x)

Figure 1.6. Apprentis sage supervisé d'une machine.

Parmi les méthodes qui ont été développées dans ce contexte (machine d'apprentissage), nous distinguons par exemple les réseaux de neurones et les machines à vecteurs du support (SVM : Support Vector Machines, en anglais).

1.3.1. Réseaux de neurones :

Un réseau de neurones est un assemblage de neurones connectés entre eux. Un réseau réalise une ou plusieurs fonctions algébriques de ses entrées, par composition des fonctions réalisées par chacun des neurones. La capacité de traitement de ce réseau est stockée sous forme de poids d'interconnexions obtenus par un processus d'apprentissage à partir d'un ensemble d'exemples d'apprentissage

Il arrive souvent que les exemples de la base d'apprentissage comportent des valeurs approximatives ou bruitées. Si on oblige le réseau à répondre de façon quasi parfaite relativement à ces exemples, on peut obtenir un réseau qui est biaisé par des valeurs erronées. Par exemple, imaginons qu'on présente au réseau des couples situés sur une droite

d'équation , mais bruités de sorte que les points ne soient pas exactement sur la

droite. S'il y a un bon apprentissage, le réseau répond ax+b pour toute valeur de x présentée. S'il y a surapprentissage, le réseau répond un peu plus que ou un peu moins, car



chaque couple positionné en dehors de la droite va influencer la décision. [10]

1.3.2. Support Vecteur Machine (Machines à Vecteur de Support) :

Les réseaux de neurones éprouvent de grandes difficultés à traiter les données de très haute dimension, de plus, ils possèdent un grand nombre de paramètres d'apprentissage à fixer par l'utilisateur. Pour surmonter ce problème, on procède souvent par la sélection d'une partie des attributs des données pour réduire la dimension de l'espace d'entrée. Mais dans ce cas, on aura besoin d'utiliser des hypothèses simplificatrices qui ne se vérifient pas touj ours en pratique. Par ailleurs, une méthode issue récemment d'une formulation de la théorie de l'apprentissage statistique due en grande partie à l'ouvrage de Vapnik en 1995 intitulé the nature of learning theory [27] surmonte ce problème en imposant que le nombre de paramètres soit linéairement lié au nombre des données d'apprentissage. Cette technique est appelée Support Vector Machines (SVM) ou machines à vecteurs de support. L'avantage principale provient du fait qu'il ya peu de paramètres à régler comparativement aux réseaux de neurones. Elle laisse très peu de place aux paramètres utilisateurs, bien que récemment proposée elle a fait l'objet d'un nombre important de publications.

1.4. Conclusion :

Dans ce chapitre, nous avons présenté les différentes étapes de reconnaissance des chiffres manuscrits hors-ligne et les méthodes de classification fondés sur les machines d'apprentissage.

Dans le système de reconnaissance, nous nous intéressons plus précisément au classifieur fondé sur les SVMs .Aussi, nous abordons dans le prochain chapitre la description détaillée de cette méthode de classification appliquées à la reconnaissance des chiffres manuscrits. Cette technique est appelé machines à vecteurs de support (SVM) qui appliquée avec une efficacité remarquable à la reconnaissance des chiffres manuscrits, au traitement d'images, à la prédiction de séries temporelles, au diagnostic médical, au contrôle qualité, etc. Des exemples d'application réussie des SVM peuvent être consultés sur Internet [12].

.



Machines à Vecteurs de

Support

2.1. Introduction

Le classfieur SVMs a été conçu pour une séparation de deux ensembles de donnée. Il est considéré donc comme un classfieur binaire.

Le but de SVM est de trouver un hyperplan qui va séparer et maximiser la marge de séparation entre deux classes. Le problème de recherche de l'hyperplan séparateur possède une formulation duale. Ceci est particulièrement intéressant car, sous cette formulation duale, le problème peut être résolu au moyen de méthode d'optimisation quadratique.

Différents algorithmes d'optimisation ont été développés parmi eux l'algorithme SMO (optimisation minimale et séquentielle) qui est un algorithme rapide proposé par platt [21] pour résoudre le problème de programmation quadratique des SVMs.

2.2. Formulation mathématique des SVMs

2.2.1. Principe

La tâche, qu'un classifieur doit effectuer, est exprimée par une fonction appelée fonction de décision reliant les exemples à classifier x (appelés espace d'entrée) à leur classes y (appelées espace de sortie). y correspond souvent à {- 1, + 1}.

Soit: {,? Ë}, : " ? {#177; 1}

f_á á f_á R l'ensemble de fonctions tel que (1, ₁ ),,(, )?"× {#177; 1}

xyKxlyl R

sont des exemples d'apprentissage indépendants générés aléatoirement selon une distribution de probabilité P(x,y) inconnue. Dans notre cas, la machine est supposée déterministe pour un x donné et un á donné, on obtient toujours la même sortie f(x, á). Un choix particulier de á génère ce que l'on va appeler «machine entraînée».

L'objectif des SVMs est de trouver un hyperplan permettant de séparer les données d'apprentissage de sorte que tous les points d'une même classe soient d'un même coté de l'hyperplan. Deux cas peuvent se présentent :

· Données linéairement séparables.

· Données non linéairement séparables.

2.2.2. Données linéairement séparables

On définit l'ensemble de données d'apprentissage par :

{}{}" xyilyxR

,, =1,K,,?-1,+1,?

i i i i

En supposant que nous disposons d'un hyperplan séparant les données positives des données négatives, les x_i qui appartiennent à l'hyperplan vérifient la relation :

. x_i·w+b=0 (2.1)
w est la normale de l'hyperplan et b paramètre de l'hyperplan (seuil).

Pour le cas linéairement séparable, l'algorithme de vecteurs de support cherche simplement l'hyperplan séparateur permettant la plus large marge. Ceci est formulé par :

x_i · w+b=+1 poury_i=+1 (2.2)

x_i·w+b=-1 poury_i=-1 (2.3)

Ces équations peuvent être combinées dans l'inégalité suivante :

yi(x _i ·w+b)=1;?i (2.4)



Vecteurs de support

: Données représentes des classes

2

w

x_i

.w+b

0

Figure 2.1. Hyperplan de séparation linéaire pour des données linéairement séparables.

Les points vérifiant l'égalité de (2.2), appartiennent à un hyperplan H1 :

x_i·w+b=+1 (2.5)

Similairement, les points vérifiant l'égalité de (2.3), appartiennent à l'hyperplan H2 :

x_i ·w+b=-1 (2.6)

(comme indiqué par la figure :2.1)

L'hyperplan optimal est celui pour lequel la distance aux points les plus proches (marge) est maximale. Cette distance vaut 2 w .

Maximiser la marge revient donc à minimiser 2

wde l'inégalité (2.4). Pour cela, le problème est reformulé sous forme de Lagrangien. Il y a deux raisons pour cela. La première est que la contrainte dans (2.4) sera remplacée par une contrainte sur les multiplieurs du Lagrangien qui sera plus facile à

traiter. En plus, dans cette reformulation du problème, seules les données d'apprentissage apparaissent sous forme de produit scalaire. Ainsi, on introduit des multiplieurs ái positifs, i = 1,K , l dans (2.4). Les contraintes dans (2.4) sont multipliées par les á_i et sont ensuite

soustraites de 2

1 w pour former le Lagrangien.

2

l l

á (2.7)

i

1 2



L w y x w b

= - · + +

? = ( ) ? =

á

p i i i

2 i 1 1

i

¹

L= ? á- ?

D i ²ⁱj

(2.10)

i

,

áá ·

i j i j i j

y y x x

Lp est appelé lagrangien primal.

On doit minimiser le Lagrangien par rapport à w et simultanément exiger que ses dérivées par rapport à tous les multiplieurs du Lagrangien á_i disparaissent. Une autre contrainte impose que

?i, á_i = 0. En imposant que les gradients de Lp par rapport à w et b disparaissent on obtient :

Vs

w ?

=á

i yx (2.8)

i i

i=1

?_i =0

^ái^yi (2.9)

Vs : Nombre de vecteurs de support.

En substituant les équations (2.8) et (2.9) dans (2.7) nous obtenons :

LD: est appelé lagrangien dual.

Les points dont les ái sont strictement supérieurs à 0 sont appelées vecteurs de support et appartiennent à l'un des hyperplans H1 ou H2. Ces points sont les plus proches de la frontière de décision et forment le plan séparateur.

2.2.3. Données non linéairement séparables

Lorsque les exemples ne sont pas linéairement, séparables les contraintes (2.2) et (2.3) sont relâchées en introduisant des variables d'écart îi ? 0, i =1, ....., l

qui deviennent : x _i ·w+b=1-î _i poury _i = +1 (2.11)

xwb î pour y (2.12)

_i· += -1+_{i i}= -1

î _i =0 ?i (2.13)
Pour qu'une erreur se produise, le î_i correspondant doit être supérieur à 1.



Figure 2.2. Hyperplan de séparation linéaire pour des données non linéairement séparables

Maximiser la marge revient donc à minimiser + ? 2 w /2C i

î i . (2.14)

C :est un paramètre choisi par l'utilisateur, plus qu'il est grand plus la pénalité sur l'erreur est grande.

La formulation lagrangienne devient :



i i

^{1 2}

L wC

P i

= +- i

2

? ? ?

î áîâî

{()}_i

yxwb1(2.15)

iii

· +-+-_i

i

Les â_i sont des multiplieurs du Lagrangien introduits pour forcer la positivité des î_i. Le Lagrangien doit être minimisé par rapport à w, b,î et maximisé par rapport à á etâ.

? Lp ? w

0

w = ? á _i yx (2.16)

i i

i



= 0(2.17)

? ? i

L á

p y

=- i

? b i

? L_p

0

? b

C-á_i-â_i=0 (2.18)

?Lp =

î i

?

0

Ce qui induit à un problème dual :

(2.19)

Maximiser : Lyyxx

= ? á- ?áá·

¹

D i ijijij

i

i , j

2

Sous contrainte que :

0=á_i=C (2.20)

l

et ?i⁼⁰

á_iy (2.21)

i

=

w

V S

?=

i 1

La solution est donnée encore par :

á (2.22)

i^yi^xi

VS est le nombre de vecteurs de support

Dans le cas où 0< á_i <C , nous avons î_i = 0 ce qui nous permettra de déterminer le seuil b après l'optimisation. En effet, une fois w et b sont déterminés la fonction de décision est donnée par

? ?+> fxi () á = ? ?=+ Vs fxisign iyixixb1 si ()0 T ? ?x i fx ? 1 si () 0 ? ? i1 ? ? - < i

(2.23)

Les vecteurs de support aident à bien définir la surface de décision car ces exemples utilisés dans le calcul de cette fonction de décision.

2.2.3.1. Fonctions noyaux

Dans la plupart des cas les données à classer ne sont pas linéairement séparables. Tandis que les SVMs sont conçus pour séparer linéairement les données. L'idée des SVMs est de changer l'espace des données. Cette transformation conduit à un changement de dimension des données d'entrée. Par conséquent, il devient donc possible d'envisager d'utiliser la méthode des SVMs.

Dans le problème d'apprentissage, les données apparaissent sous forme de produit scalaire x_i · x_j.

Supposons que nous avons tracé ces données dans un autre hyperplan .7{ (.7{ étant un espace euclidien dont la dimension peut être infinie) en utilisant une application Ö telle que :



x1

R

^d?.7{

Ö :

Hyperplan
de
séparation

x2

x1

x2

Ö

x3

Figure 2.3. Exemple d'une application Ö rendant les données linéairement séparables

Alors l'algorithme d'apprentis sage va dépendre des données au travers des produits scalaires dans l'espace H des fonctions de la formeÖ(x _i )·Ö(x_j). Cet espace est appelé espace de traits ou feature

space. Il est difficile de travailler explicitement avec Ö. Dans ce cas, une fonction K appelé noyau ou Kernel définie par Ê(x_i ,x_j ) = Ö(x _i )· Ö (x_j). Ainsi, il suffit de définir uniquement le noyau K

sans connaissance explicite de Ö. En remplaçant x_i · x_j par K(x_i ,x_j) partout, nous obtenons une
machine à vecteurs de support fonctionnant dans un espace de dimension infinie. Toutes les considérations décrites précédemment seront vérifiées puisque nous maintenons touj ours la séparation linéaire, mais dans un espace différent.

2.2.3.2. Conditions de Mercer [15]

La fonction noyau ou Kernel évite la connaissance explicite de Ö et permet ainsi de connaître la similarité entre deux exemples. La matrice contenant les similarités entre tous les exemples d'une base d'apprentissage K est appelée matrice de Gram.

? KKK 11 12 1 L l ? ? ? ? KKK 21 222 L l ? K=? ? M M O ? ? ? KKK llll L 1 2 ?

(2.24)

Cependant, pour qu'une fonction K : X× X ?R corresponde au produit scalaire dans l'espace de traits, elle doit répondre à des conditions dite de Mercer.


· Théorème

La fonction K(x_i ,x_j): X× X ? R est un Kernel si et seulement si :

K=(K(x _i ,x _j )/i,j=1, l) (2.25)

est définie positive.

Notons qu'une fonction X× X ? R générant une matrice définie positive possède les trois propriétés fondamentales du produit scalaire : ?x _i ,x_j ? X

1. Positivité : ^K(xi ,x_j ) = 0 (2.26)

2. Symétrie : K(x_i,x_j)=K(x_j,x_i) (2.27)



3. Inégalité de Cauchy-Shwartz : K(x _i ,x_j) = xi·x _j (2.28)

La condition de Mercer nous indique si une fonction est un noyau mais nous n'avons aucun renseignement sur l'application Ö (et donc sur l'espace de traits) induit par ce noyau. Dans le reste de cette section, nous présentons quelques noyaux utilisés dans différentes applications de reconnaissance de formes.

2.2.3.3. Exemples de noyaux

Nous présentons dans le tableau les noyaux utilisées dans ce mémoire pour la reconnaissance des chiffres manuscrits.

Noyau	K(x i ,x j )			Paramètres
RBF (Radial Basis Function)	2 ? - ? ? x i x j ?			ó: est un paramètre qui permet de régler la largeur de la gaussienne.
	expó?^-2 ? 2 ? ?
Polynomial	( )^pp x i , x j +1			: est l'ordre du polynôme.
Distance négative	( ) ãã -x i - x j			: Paramètre du noyau régler dans ]0,2].
KMOD: (de l'anglais «Kernel with Moderate Decreasing»)	? ? ? 2 ?? ã ??A: A	- ^1	? ?	??normalisation. est une constant de ? et : contrôlent ó l'écrasement du noyau.
	??exp2 ? 2 ? -+ó ^xi^xj ? ? ? Avec : 1 A=
	ã 2 ?? - exp1^??
	2 ? ó ?

Tableau 2.1. Exemples de noyaux



M

(2.33)

arg max

)

f

1

(x_i

i=

Il est possible de composer de nouveaux noyaux en utilisant des noyaux existants. Si K₁(·,·), K₂(·,·) sont des fonctions satisfaisant les conditions de Mercer, et étant donnés +

a?R et B une matrice

définie positive, alors les fonctions suivantes sont des noyaux :

1. (ij)(ij)(ij) KxxKxxKxx

,=₁,+₂, (2.29)

2. K(x_i,x_j)=aK₁(x_i,x_j) (2.30)

3. K(x_i x_j ) K(x_i x_j )K(x_i x_j)

,= 1 ,₂ , (2.31)

4. ()_j

Kx_i,x_j=x_iÂx (2.32)

T

2.3. Implémentation multi-classe

A l'origine, les SVMs ont été conçus essentiellement pour la séparation de 2 classes. Cependant, plusieurs approches permettent d'étendre cet algorithme aux cas de plusieurs classes [5].

2.3.1. Un Contre Tous (OAA : One Against All)

Pour chaque classe, on détermine un hyperplan séparant celle-ci de toutes les autres classes. Ainsi, pour M classes, on doit déterminer M fonctions de décision.

Tous les exemples appartenant à la classe considérée sont étiquetés positivement (+1) et tous les exemples n'appartenant pas à la classe sont étiquetés négativement (-1).

La figure 2.4. décrit le schéma synoptique de principe pour la séparation multi-classe.

Ainsi, pour chaque exemple de test, M valeurs de sortie f_i (x)avec (i=1,... M) sont disponibles.

Ainsi, une donnée est affectée à la classe qui correspond à la valeur maximale des fonctions de décision :

Classe 1

SVM1

.

Autres classes

Affectation à la classe

Forme x

.

.

.

Classe M

SVMM

Autres classes

Figure 2.4. Schéma synoptique de l'implémentation Un Contre Tous

2.3.2 Un contre un (OAO : One Against One)

La deuxième méthode, est une méthode dite de Un Contre Un. Au lieu d'apprendre M fonctions de décisions, ici chaque classe est discriminée d'une autre. Ainsi M (M-1 )/2 fonctions de décisions sont apprises et chacune d'entre elles effectue un vote pour l'affectation d'un nouveau point x. La classe de ce point x devient ensuite la classe majoritaire après le vote.

2.4. Méthode d'entraînement des SVMs [21]

Le calcul de la solution d'un SVM consiste à résoudre le problème de programmation quadratique qui est un problème d'optimisation formulé comme suit :

l ll

() ( ) i j

1 max(2.34)

i j i j

,

á ?== ?? =

L y y K x x

Di

^áá á á

= -
i1 1 1

2 ij

Sous contrainte que :

0=á_i = C,?i (2.35)

(2.36)

l

et 0

?=

á _i y i

i =

1

Le problème de programmation quadratique (PQ) provenant d'une SVM ne peut pas être facilement résolu avec les techniques standards. La matrice de gram contient un nombre d'éléments égal au carré du nombre total des données de la base d'apprentissage. Pour résoudre ce problème, Un algorithme appelé Sequential Minimal Optimisation SMO ou Optimisation minimale et séquentielle, a été proposé pour accélérer l'apprentissage d'un SVM [21].

L'optimisation de ce problème se termine lorsque tous les exemples de la base d'apprentissage obéissent aux conditions Karush-Kuhn-Tucker (KKT) [21] suivant :

()^xi

yfx() i i

1,0
î=

i

f x

( )

i i

= ?

1, 0 (2.39)

î

Cy

_i

á =

i i

0 yf 0<<

áC

i

á_i

avec :f(x_i) = x i · w+b

==

(2.37) (2.38)

1,0

î i

2.4.1. Optimisation minimale et séquentielle SMO

L'optimisation minimale et séquentielle est un algorithme rapide proposé par platt[21] pour résoudre le problème de programmation quadratique des SVMs sans la nécessiter de stoker une grande matrice en mémoire (matrice de gram) et sans une routine numérique itérative pour chaque sous-problème. SMO décompose le problème de PQ en plusieurs sous-problèmes aussi mais contrairement aux autres méthodes, à chaque étape SMO optimise le plus petit problème possible. Ainsi à chaque étape il optimise deux multiplieurs de Lagrangien. A chaque étape d'optimisation, SMO cherche les valeurs optimales des deux multiplieurs et effectue une mise à jour de la SVM pour donner le reflet des nouvelles valeurs optimisées.

2.4.1.1. Fonctionnement de l'algorithme SMO

L'algorithme SMO comporte trois éléments :

1. Une méthode analytique pour résoudre le problème de PQ.

2. Des heuristiques pour choisir les deux multiplieurs à optimiser. 3. Une méthode pour calculer le seuil b.

2.4.1.1.1. Optimisation analytique des deux multiplieurs du Lagrangien

Les deux multiplieurs de Lagrange doivent satisfaire toutes les contraintes du problème de (PQ) Rappelons que le problème de programmation quadratique pour entraîner une SVM est décrit par les équations (2.34), (2.35) et (2.36). Les contraintes d'inégalité font situer les multiplieurs de Lagrangien à l'intérieur du carré. La contrainte d'égalité les situe sur une ligne diagonale. Par conséquent, une étape de SMO consiste à trouver le (á)

max _á L_D sur le segment de droite délimité

par le carré, avec :

á i^yi

l

á1y1+á2y2=ã ^où ?

ã=-

i3=

ã=á1 ^old +sá 2 old (2.40)

qui dépend á1,á2 ets = y₁.y₂.

ã est une constante, puisque les autre multiplieurs de Lagrangien qui ne vont pas être optimisés sont considérées comme des constantes.

La contrainte sur chaque á_i est : 0 = á_i = C ainsi, les deux multiplieurs se trouvent dans une surface limitée comme le montre la figure 2.5.

On a deux cas d'optimisation selon que y1 et y2 ont le même signe ou pas.

			á1			á1
^0

(a) (b)



H

á2

H

á2

Figure 2.5. Deux cas d'optimisation

(a) y₁ ? y₂ (b) y₁ = y₂

· Premier cas (a) :

Implique que : aa ^old _y

₁-= (2.41)

old

2

Les limites de á₂ sont donc :

L ( ?ld )

=max0, a 2 - a (2.42)

?ld

1

H = minC, C +á ₂ - á₁ (2.43)

₍ol'ol'₎

· Deuxième cas (b) :

Implique que : ol' + ol' =

á 1 á 2 ã (2.44)

Les limites de á₂ sont donc :

L = max(0,á 1 ol' + á 2 ol' - C) (2.45)

H = minC,á ₁ + á 2 (2.46)

( ol' ol'₎

l ll

LD (á) peut être exprimée par : LD i yyk =- ^?=^á=^??=^áá ^1 i j ij i j 1 2 1 1 iij

(2.47)

Avec: () ()^T

k ij^Kxi^x j et l

=,á = á₁,K,á

En mettant L_D sous forme d'une fonction de á₂ telle que s = y₁ y₂ , á ₁ =ã - sá ₂ et

l

en posant : ? íi=

^yjj^kij á

on obtient : (2.48)

j 3

1 1 1

=- + - + - -

ãááããáá²

skksk

2

2 2 11112 11 2

2 2 2

L_D ()^á2

^k22^á

2 2

(2.49)

- +

^sk122

ãá

kyyáíãí ²-+ 12 2 111

1

s y á í á 2 2 2 2 -

+

L Cons te tan

l

ll

où : Lyyk

conste i

=-

?á¹ (2.50)

tan 2 ??₌^áá

i j ijij

i=3 3 3

i=j

La dérivée première de L_D par rapport à á2 est telle que :



-

+ sy

y₂í

2 12

- skã

^k12^á

11

í

2

+

2

2

ss++ 1 ã

- + + s sk

1 11

(2)222 122 12(2)2(1 ₂)
ãáááãáíí --+ --+ -
skksksy

(2.51)

?L_D

?á₂

=

- - kk

112 22

áá

k 11

La dérivée seconde de L_D par rapport à á2 est donnée par :

? 2

L_D (2.52)
= - - = ç

2

? _á2 12 11 22

2 k kk

Nous pouvons à pré sent calculer le maximum L_D en permutant uniquement le changement de deux multiplieurs. On définit E_i comme étant l'erreur sur l'ieme exemple d'apprentissage, soit :

E _i =u_i -y_i (2.53)
Où u _i est la sortie fournie par le SVM à l'exemple (x_i, y i ).

l

u yk b 1 á 1 =?=1 j j j - j

(2.54)

On trouve :

í=u+b-yák-syák

1 1 2212 2111 (2.55)

Similairement,

í=u+b-yák-yák

2 2 1112 2222 (2.56)

Au point maximal de LD, l'équation (2.57)

?LD est nulle. Ainsi ?á2

á ã í í

2 11 22 12 11 12 2 1 2 1

( k k k ) s ( k k ) y ( ) s

+ - = - + - + - (2.57)
En substituant (2.55) et (2.56) dans (2.57), nous obtenons :

new old yE-E

()

áá

=- (2.58)

21 2

2 2 ç

Une fois new

á est trouvée, il correspond au maximum sans contraintes. Comme il doit être limité

2

par les points limites de la diagonale on utilise :

?H siH

á new =

2

?

,

á new clipped newnew

= ? áá

si L H

<< (2.59)

2 2 2

? =

?L si L

á new

2

Pour calculer new

á, nous utilisons l'équation suivante :

1

áááá^new newclipped old old

+ = +
ss ^,qui conduit à : 1 21 2

á 1 á 1á ₂ á 2

new =^old+ s ? old - new,clipped?

?? _??(2.60)

Remarque : Quand on évalue ç, la dérivée seconde de L_D avec l'équation (2.52), on constate qu'elle est nulle quand plus qu'un exemple dans les exemples de la base d'apprentissage ont le même vecteur d'entrée x. Dans ce cas, on doit chercher dans ce cas, un autre exemple pour l'optimisation. Sous certaines circonstances inusuelles, ç n'est pas négatif. Alors, SMO évalue (maxL_D) aux deux points de fin du segment. (Voir figure 2.5).

2.4.1.1.2. Choix des deux multiplieurs du Lagrangien

L'algorithme SMO est basé sur l'évaluation des conditions de KKT. Quand tous les multiplieurs vérifient ces conditions, l'algorithme s'arrête. En pratique ces conditions sont vérifiées à une erreur près å.

· Choix du premier multiplieur

D'abord, la boucle externe de l'algorithme effectue une itération sur toute la base d'entraînement pour vérifier s'il existe des exemples qui violent les conditions de KKT. Une fois qu'un violateur est trouvé il est immédiatement choisi pour être optimisé.

· Choix du second multiplieur :

SMO utilise une autre heuristique pour le choix du second multiplieur .Cette heuristique tente de maximiser E₁ - E₂ dans l'équation (2.58). On choisit le multiplieur qui permet de donner la plus grande valeur de cette différence. Rappelons qu'une valeur d'erreur E est déjà calculée pour chaque

exemple dont le multiplieur est différent des limites 0 et C, car c'est à partir de ces exemples que le multiplieur est choisi. Si E1 est positive, l'exemple qui possède la plus petite valeur de E2 est choisi. Si E1 est négative, alors l'exemple avec la plus grande erreur E2 est choisi. SMO utilise, en effet, une hiérarchie dans le choix du second multiplieur. S'il n'y a pas un progrès positif, l'algorithme effectue une itération sur les exemples dont les multiplieurs sont différents de 0 et de C en partant d'une position aléatoire. Si aucun d'entre eux ne permet d'avoir un progrès positif, il reprend la recherche sur toute la base d'entraînement en partant d'une position aléatoire.

Et alors les deux multiplieurs sont conjointement optimisés. A la fin de l'optimisation, le SVM est mis à jour et l'algorithme reprend la recherche des exemples violateurs. Après un passage sur toute

la base d'apprentissage, la boucle externe commence à travailler uniquement avec les exemples dont les multiplieurs appartiennent à l'intervalle ]0, C[ jusqu'à ce que tous les exemples vérifient les conditions KKT. A ce moment, la boucle externe reprend l'itération sur toute la base

d'apprentissage. Elle passe alternativement entre toute la base d'apprentissage et l'ensemble des exemples dont les multiplieurs sont différents de 0 et de C, jusqu'à ce que tous les exemples vérifient les conditions KKT à une erreur å près.

Après avoir trouvé les deux multiplieurs à optimiser conjointement, on calcule leurs valeurs grâce aux formules (2.59) et (2.60) et on met à jour la SVM.

L'algorithme SMO s'arrêt lorsque il ne reste aucun multiplieur de Lagrangien qui viole les condition KKT.

2.4.1.1.3. Mise à jour du seuil b

La valeur de b est calculée à la fin de chaque optimisation.

l

Soit u1 la réponse de SVM avec les anciennes valeurs de á₁ etá₂.

old (2.61)

uykykykb

1 1 1 ¹¹ 2 2 22

=++-

ááá

old old old ^old?111

1

1

=3

Si la nouvelle valeur de á1 est différente de C, alors la sortie du SVM après l'optimisation sera y1.

l

(2.62)

Donc : yykykyk b

= + +-
ááá

new newclipped

,

1 1 111 2212 ?111

1 1

1

3

Nous déduisons ainsi :

b E byky k

=+ + ? -

old new old newclipped old

? ,, ?

1 1 1 1 1 1122

?? áááá

??+? -

?? 2 12

_??(2.63)

De la même manière nous obtenons le seuil b2.

b E by k yk

=+ + ?-

oldnew old newclipped old

? , ?

2 ²¹11 12 22

?? áááá

??+ ? -

?? 2 22

??(2.64)



X2

0

ë

á i = C , î _i >1

è

ô

ä

X1

0<á _i <C , î _i =0

á i = C,0 <î _i <1

Figure 2.6. Quand les deux multiplieurs sont égaux à la bande C : les vecteurs de support ë et ô donnent le même seuil b. Les points ä et è fournissent les seuils b1 et b2 respectivement. Les points d'erreur et le seuil b se trouve entre b1 et b2.

Si á i = C , dans ce cas, on peut prendre b new +

= comme étant la valeur du seuil.

b ₁ b 2

2

2.4.1.1.4. Mise à jour de l'erreur

Après l'optimisation, lorsqu'un multiplieur de Lagrange possède une valeur différente de C, l'erreur correspondante est mise à zéro. Les erreurs des autres multiplieurs dont la valeur est différente de C et qui n'ont pas été concernés par l'optimisation sont mises à jour comme suit :

E_k= E+u-u (2.65)

new oldnew old

k k k

Nous obtenons ainsi :

EEykykb b

new = + ? -

old new old? newclipped old

, ?old new

kk ?? á á áá

??+ ? -

k ?? ??+ -

k (2.66)

11 1 122 2 2

Dans ce qui suit, nous donnons le pseudo code de l'algorithme SMO.

2.4.1.2. Pseudo-Code de l'algorithme SMO

Target : il contient la sortie désirée (+1 ou -1).

Routine principal

Début

Initialiser les paramètres d 'apprentissage (C, tolérance, epsilon, type de noyau, paramètres du noyau)

Initialiser les multiplieurs á [i] à zéro.

Initialiser le seuil b à zéro.

Chargement de la base d'apprentissage

Numchanged = 0 /* variable qui incrémente pour chaque optimisation des multiplieurs*/ Examineall = 1

Tantque (Numchanged > 0 ou Examineall==1), Faire

Numchanged = 0

Si Examineall= 1, alors

Pour (i= 1 : l), Faire /*répéter i sur tous les exemples d'apprentissage*/
Numchanged= Numchanged+Examine_Exemple (i) /* Exam ine_Exemple est une fonction

est définie plus loin*/

Fin si

Sinon Faire

Pour (i=1, : l), Faire

Si (á[i] != 0 et á[i] != C), alors faire

Numchanged = Numchanged +Eamine_Exemple(i)

Fin si Fin sinon

Si (Examineall == 1), alors faire

Examineall= 0

Fin si

Sinon Faire

Si (Nnumchanged = 0), alors faire

examineall= 1;

Fin si

Fin sinon Fin Tant que FIN

Fonction Examine Exemple(i1)

/*cette fonction permet le choix de deux multiplieurs à optimiser*/

Chapitre2 Machines à vecteurs de support (SVMs)

Debut

y1 = Target[i1]

á1=á[i1]

Si((á1 >0) et ( á1< C)) alors faire

E1= error _cache[i1] /*Error cache calculé par la fonction takestep*/

Fin si

Sinon Faire

E1= (learnedjunction(i1)- y1 /* learnedjunction clacule la fonction de décision*/

Fin sinon r1=y1 *E1

Si rtolérance etCou rtoléranceet )alors faire

(() ()

<-<> >

) ( 0

á á

1 1 1 1

i2= -1

tmax=0

pour i=1, l faire

Si ((á[] > 0) (á[] < ))

ietiCalors faire))

E2= error _cache[i] temp= abs (E1-E2)

Si (temp >tmax) alors faire

tmax= temp

i2= i

Fin si

Fin si

Si (i2= 0) alors faire

Si (takstep(i1,i2) alors retourner 1 Fin si

Fin si

Fin pour

en commençant à une position aléatoire q

pour i=q ,l+q faire
i2=l modulo n

Si ((á[i2] > 0 ) et (á[i2])< C)) alors faire

Si ((takestep(i1,i2) alors retourner1 Fin si

Chapitre2 Machines à vecteurs de support (SVMs)

Fin si Fin pour

en commençant à une position aléatoire q

pour i=q,q+l faire

i2=l modulo q

Si (takestep(i1, i2)) alors retourner1 Fin si

Fin si Fin pour retourner 0

FIN

Fonction takestep(i1,i2)

/* Cette function permet de :- l 'optimisation de deux multiplieurs choisir

-mise à jour du seuil b

- mise à jour de l'erreur */

Début

Si i1=i2 alors retourner 0 Fin si

á1=á[i1]

y1 =target[i1] á2=á[i2]

y2 = target[i2]

S=y1.y2

Calcule L,H

Si (L=H) retourner 0 Fin si

k11 = kernel(exemple[i1], exemple[i1])

k12 = kernel (exemple[i1], exemple[i2]) k22 = kernel (exemple[i2], exemple[i2])

ç 2.k12 - k₁₁ - ^k22

Si (ç<0) alors faire

ááç

22y2.(E1E2)/ ^new=-- Si(^new

á2<L)

á2=L

new

Sinon si ( new

á2>H)

á2=H

new

Fin si

Sinon alors faire

Calculer Lobj et Hobj à partir de (max L_D) en remplacent new

á=L et new

á=H

Si (Lobj>Hobj+ eps) faire

á2=L

new

Sinon si (Lobj<Hobj-eps) faire á2=H

new

Si non faire á2= á2

new

Fin sinon faire

Si (á^new- á<epsá^new+ á+ eps

22 .(22 )) retourner 0 Fin si

á1 new = á1-(2 new 2

s á-á)

Mise à jour du seuil pour refléter le changement dans les multiplieurs de Lagrangien.

Mise à jour de l'erreur pour les autres exemples et mettre les erreurs des multiplieurs qui viennent d'être optimisés à 0.

FIN

5. Conclusion

Ce chapitre a été consacré à la présentation de la formulation mathématique des SVMs et l'algorithme utilisé pour son optimisation. Celle-ci est fondée sur l'utilisation de l'algorithme SMO qui permet l'accélération de l'apprentissage sans la nécessiter de stoker la matrice de Gram en mémoire. Son principe repose sur l'optimisation de deux multiplieurs de lagrangien à chaque étape. Le prochain chapitre sera consacré à l'évaluation des SVMs pour la reconnaissance des chiffres manuscrits.



Ré sultats exp érimentaux

3.1. Introduction

Dans ce chapitre, nous allons soumettre notre implémentation SVM avec l'algorithme SMO à deux types de tests: les tests binaires appliquées aux paires des chiffres les plus fréquemment confondus et les tests multi-classes Par l'approche un-contre-tous. Différents noyaux serons utilisées avec différents paramètres pour évaluer les performances des SVMs .



Figure 3.1.Représentation de la base USPS.

3.2. Critères d'évaluations

3.1.1. Base de données USPS (de l'anglais«US postal Service »)

L'USPS est une base de données de chiffres manuscrits extraits à partir d'enveloppes. La base de données contient 9298 images de chiffres manuscrits arabes dont 7291 images d'apprentissage servent à construire le classifieur et 2007 images de test servent à tester le classifieur et l'estimation de son taux d'erreur réel. Ces images ont été saisies à partir d'images d'enveloppes collectées au centre CEDAR à Buffalo (États Unis) [30]. Chaque image de chiffre est représentée par 16×16 pixels de niveau de gris allant de 0 à 255 (Tableau 3.1). Il est connu que l'ensemble de test d'USPS est plutôt difficile puisque l'erreur humaine se situe autour de 2.5% [13].

Etiquettes

0

1

2

3

4

5

6

7

8

9



Images

Tableau 3.1. Échantillon représentant la première dizaine d'images binarisées et leurs
étiquettes dans la base de données USPS

Dans ce mémoire, nous nous restreignons à la méthode SVM et aux images originales d'USPS. Une fraction de 500 images a été extraire à partir de 7291 pour servir a l'apprentissage et pour le test nous utilisons tous les prototypes (2007 image).

Pour évaluer la robustesse du classifieur, nous utilisons la matrice de confusion pour estimer le taux de bonne reconnaissance.

3.1.2. Matrice de confusion

Dans la terminologie de l'apprentissage supervisé, la matrice de confusion est un outil servant à mesurer la qualité d'un système de classification. [29].Par exemple, si on considère un système de classification dont le but est de classer des prototypes en classe1 et en classe2, on va vouloir savoir combien de prototypes seront faussement considérés comme du classe1 et combien de classe2 ne seront pas identifiés comme tels. On va supposer qu'on a testé notre classificateur avec 100 prototypes de classe 1 et 100 prototypes de classe2. Ainsi la matrice suivante se lit comme suit :

· sur les 100 prototypes de classe 1, 95 seront considérés comme tels et 5 seront pris pour du classe2 ;

· sur les 100 prototypes de classe2, 3 seront interprétés comme classe1, et 97 seront reconnus en tant que classe 1 ;

· sur les 98 prototypes que le système classe comme classe1, 3 sont en fait du classe2 ;

· sur les 102 prototypes que le système classe comme classe2, 5 sont en fait du classe 1.

· Taux global de bonne reconnaissance (TGBR) : (somme de prototypes bien classées (diagonale)/somme totale) * 100

· Dans cet exemple= ((95+97)/200)*100=96.00



Référence

Classe 1 95 5

Classe 2

Décision

Classe 1

3

Classe 2

97

Figure 3.2.Exemple d'une matrice de confusion

· les colonnes correspondent aux décisions correctes

· les lignes correspondent aux décisions données par le classifieur.

Cette notion peut bien sûr s'étendre à un nombre quelconque de classes. Un système de classification sera d'autant meilleur que sa matrice de confusion s'approchera de la matrice diagonale.

3.3. Apprentissage des SVMs

3.3.1. Réglage des paramètres

Nous avons utilisé pour l'apprentissage binaire et multiclasse les paramètres suivants :

3.3.1.1. Paramètre de régularisation C

La valeur du paramètre C est un hyper-paramètre qui régit la performance du SVM. Ce paramètre sert à fixer le compromis entre la minimisation de l'erreur d'apprentissage et la maximisation de la marge. En pratique, le comportement du SVM est sensible à la valeur de C uniquement si les données d'apprentissage ne sont pas séparables. Dans ce cas, il existe des valeurs critiques qui peuvent compromettre la performance du classifieur. Une très grande valeur de C (quelques milliers) peut faire que la fonction objective minimisée par le SVM ne soit plus convexe et empêcherait sa convergence. Une très faible valeur de C tend à diminuer la capacité du classifieur [20].

Dans ce travail, après quelques expériences, le paramètre C a été fixé à 100 car il offre les meilleures performances.

3.3.1.2 .Réglage des seuils de Tolérance et å (=eps) :

L'algorithme SMO est basé sur l'évaluation des conditions de KKT. Quand tous les multiplieurs vérifient ces conditions, l'algorithme s'arrête. En pratique ces conditions sont vérifiées à une erreur près å . Platt [21] a mentionné dans son article que å est typiquement choisi dans l'intervalle 10^-2 et 10^-3.

La maximisation de la marge doit être tolérée de l'ordre :10%, 0.1%..etc

Dans notre cas nous avons fixé å , et la tolérance a 1 0^-3 .

3.3.2. Choix du noyau

Quatre noyaux ont été utilisés dans notre travail :

· Polynomial

· RBF (Radial Basis Function)

· Distance négative

· KMOD : (de l'anglais «Kernel with Moderate Decreasing») 3.4. Classification binaire

3.4.1. Choix des pairs de classes

Dans cette expérimentation, nous voulons expérimenter la performance des SVMs pour séparer deux classes les plus fréquemment confondus.Ces classes correspondant aux paires (9,4), (5,6) et (7,1).

3.4.2. Evaluations

Pour évaluer l'influence du paramètre de chaque noyau sur la qualité de la classification, nous avons calculé le taux de bonne classification pour chaque paire de classes .Les résultats sont présentés dans les tableaux suivants :

p=1	classe 9		classe4	classe 9
94.91	5.09		classe 4
3.5	96.5

a =3	classe 9		classe4	classe 9
94.91	5.08		classe 4
3.5	96.5

y = 0.2	classe 9		classe4	classe 9
96.04	3.95		classe 4
3	97

p=2	classe 9	classe4
classe 9	95.48	4.52
classe 4	4	96

(a)

a=10	classe 9		classe4	classe 9
96.04	3.95		classe 4
4	96

(b)

y=0.1	classe 9	classe4
classe 9	96.61	3.38
classe 4	4.5	95.50

(c)

p=3			classe 9				classe4
classe 9			96.04				3.95
classe 4			3.5				96.5
a =25			classe 9				classe4
classe 9			94.91				5.08
classe 4			3.5				96.5
y = 0.05	classe 9				classe4
classe 9	96.04				3.95
classe 4	4.5				95.5
a =6 et y=0.2				classe 9				classe4
classe 9				95.48				4.51
classe 4				2.5				97.5
a =6 et y=0.5		classe 9				classe4
classe 9		96.04				3.95
classe 4		3.50				96.50

(d)

Noyau	RBF			polynomial			Distance négative			KMOD
						p=3				a=6	a=6
classe	a=3	a=10	a=25	p=1	p=2		y=0.2	y=0.1	y=0.05	et	et
										y=0.5	y=0.2
9	94.91	96.04	94.91	94.91	95.48	96.04	96.04	96.61	96.04	96.04	95.48
4	96.50	96.00	96.50	96.50	96.00	96.50	97.00	95.50	95.50	96.50	97.50
TGBR	95.75	96.02	95.75	95.75	95.75	95.75	96.55	96.02	95.75	96.28	96.55

Tableau 3.2.Matrices de confusion pour les paires de classes (9 ,4) pour chaque type de noyau (a) Polynomial (b) RBF (c) Distance négative (d) KMOD

p=1			classe 5		classe6
classe 5			98.12		1.87
classe 6			5.29		94.70
a =3			classe 5		classe6
classe 5			98.75		1.25
classe 6			4.70		95.29
y = 0.2	classe 5			classe6
classe 5	98.75			1.25
classe 6	4.70			95.29
p=2		classe 5				classe6
classe 5		98.12				1.87
classe 6		4.70				95.29

(a)

a=10	classe 5		classe6	classe 5
98.12	1.87		classe 6
4.12	95.88

(b)

y=0.1	classe 5	classe6
classe 5	98.12	1.87
classe 6	5.29	94.70

(c)

p=3					classe 5			classe6
classe 5					99.37			0.62
classe 6					7.05			92.94
a =25					classe 5			classe6
classe 5					98.12			1.87
classe 6					4.7			95.29
y = 0.05			classe 5				classe6
classe 5			98.12				1.87
classe 6			4.11				95.88
a =6 et y=0.2	classe 5											classe6
classe 5	98.75											1.25
classe 6	3.52											96.47
a =6 et y=0.5		classe 5									classe6
classe 5		98.75									1.25
classe 6		3.52									96.47
p=1						classe 7			classe1
classe 7						99.31			0.68
classe 1						2.27			97.72
p=2				classe 7						classe1
classe 7				99.31						0.68
classe 1				2.65						97.34

(a)

p=3	classe 7	classe 1
classe 7	100	0
classe 1	2.65	97.34

(d)

Noyau	RBF			polynomial			Distance négative			KMOD
						p=3				a=6	a=6
classe	a =3	a =10	a =25	p=1	p=2		y = 0.2	y = 0.1	y = 0.05	et	et
										y=0.5	y=0.2
5	98.75	98.12	98.12	98.12	98.12	99.37	98.75	98.12	98.12	98.75	98.75
6	95.29	95.88	95.29	94.70	95.29	92.94	95.29	94.70	95.88	96.47	96.47
TGBR	96.96	96.96	96.66	96.36	96.66	96.06	96.96	96.36	96.96	97.57	97.57

Tableau 3.3.Matrices de confusion pour les paires de classes (5 ,6) pour chaque type de noyau (a) Polynomial (b) RBF (c) Distance négative (d) KMOD

a=3			classe 7			classe1
classe 7			100			0
classe 1			3.40			96.59
a=10	classe 7						classe1
classe 7	99.31						0.68
classe 1	2.66						97.34
a=25		classe 7			classe1
classe 7		99.31			0.68
classe 1		2.65			97.34
y=0.2				classe 7				classe1
classe 7				99.31				0.68
classe 1				3.40				96.59

(b)

y=0.1	classe 7	classe1
classe 7	99.31	0.68
classe 1	3.40	96.59

(c)

y=0.05		classe 7			classe1
classe 7		99.31			0.68
classe 1		3.40			96.59
a =6 et y=0.2			classe 7			classe1
classe 7			100			0
classe 1			3.40			96.59
a =6 et	classe 7			classe1
y=0.5
classe 7	100			0
classe 1	3.40			96.59

(d)

Noyau	RBF			polynomial			Distance négative			KMOD
						p=3				a=6	a=6
classe	a =3	a =10	a =25	p=1	p=2		y = 0.2	y = 0.1	y = 0.05	et	et
										y=0.5	y=0.2
7	100	99.31	99.31	99.31	99.31	100	99.31	99.31	99.31	100	100
1	96.59	97.34	97.34	97.72	97.34	97.34	96.59	96.59	96.59	96.59	96.59
TGBR	97.81	98.05	98.05	98.29	98.05	98.29	97.56	97.56	97.56	97.81	97.81

Tableau 3 .4.Matrices de confusion pour les paires de classes (7 , 1) pour chaque type de noyau (a) Polynomial (b) RBF (c) Distance négative (d) KMOD

3.4.3. Comparaison des résultats et discussions

Noyau	RBF			Polynomial			Distance négative			KMOD
pairs	a=3	a=10	a=25	p=1	p=2	p=3	y=0.2	y=0.1	y=0.05	a=6	a=6
										et	et
										y=0.5	y=0.2
(9,4)	95.75	96.02	95.75	95.75	95.75	95.75	96.55	96.02	95.75	96.28	96.55
(5,6)	96.96	96.96	96.66	96.36	96.66	96.06	96.96	96.36	96.96	97.57	97.57
(7,1)	97.81	98.05	98.05	98.29	98.05	98.29	97.56	97.56	97.56	97.81	97.81

Tableau 3.5.Taux global de bonne reconnaissance pour les trois paires de classes (9,4), (7,1) et (5,6).

D'une manière générale, les résultats obtenus sont sensiblement similaires en termes de bonne classification .Cependant, l'analyse comparative montre que le choix du noyau dépend des paires de classes et des paramètres utilisés. En effet nous avons constaté que les noyaux KMOD et Distance négative ont les mêmes performances pour la paire (9,4) .Tandis que le noyau Polynomial fournit le meilleurs taux pour la paire(7,1) .Pour la paire (5,6) le noyau KMOD fournit le meilleurs taux de bonne reconnaissance.

3.5. Classification multi classe

3.5.1. Evaluations

Dans cette section, nous évaluons la classification multi-classe en utilisant l'approche un contre tous pour les différents noyaux et différents paramètres des noyaux.

Les matrices de confusion sont reportées dans les tableaux suivants :

ó =3	zéro	Un	deux	trois	quatre	cinq	six	sept	huit	neuf
zéro	92.75	0	2.50	0.27	1.39	0.55	0.83	0.27	1.39	0
un	0	93.18	0.75	0	3.40	0	1.51	0	1.13	0
deux	1.01	0	84.34	2.02	3.53	1.51	1.01	0.50	6.06	0
trois	1.20	0	3.61	80.12	0.60	7.83	0	0	6.02	0.60
quatre	0	0.50	3.00	0	85.50	0	1.00	0.50	3.00	6.50
cinq	2.50	0	1.25	5.00	1.87	82.50	0	0	5.00	1.87
six	2.35	0	4.70	0	1.76	3.52	86.47	0	1.17	0
sept	0	0	2.04	0.68	6.12	0	0	80.27	4.08	6.80
huit	1.80	0	1.80	0	1.20	3.61	0	0	90.96	0.60
neuf	0	0	0.56	0	3.38	0	0	0.56	2.25	93.22
TGBR											87.84

Tableau 3 .6.Matrice de confusion de la classification multi classe pour le noyau RBF (ó =3)

ó =10	zéro	Un	deux	trois	quatre	cinq	six	sept	huit	neuf
zéro	89.69	0	5.01	1.39	1.39	1.11	0.27	0	0.27	0.83
un	0	95.07	0.37	0	3.40	0	0.37	0	0.37	0.37
deux	1.51	0	80.30	3.53	7.07	2.02	0.50	0.50	4.54	0
trois	1.20	0	3.01	83.73	1.20	3.61	0	0	3.61	3.61
quatre	0.50	0.50	2.00	0	87.00	0.50	0.50	1.00	3.00	5.00
cinq	2.50	0	3.12	10.62	3.12	73.75	0.62	1.25	3.75	1.25
six	2.35	0	7.05	0	4.11	6.47	77.64	0.58	1.17	0.58
sept	0.68	0	2.72	2.72	6.12	0	0	79.59	1.36	6.80
huit	3.01	1.20	2.40	3.61	5.42	4.81	0	1.80	74.09	3.61
neuf	0	0	0.56	0	6.21	0.56	0	1.12	2.25	89.26
TGBR											84.35

Tableau 3 .7.Matrice de confusion de la classification multi classe le noyau RBF (ó = 10)

ó =25	zéro	Un	deux	trois	quatre	cinq	six	sept	huit	neuf
zéro	90.25	0	3.89	1.94	1.39	0.27	0.83	0	1.11	0.27
un	0	95.83	0	0.75	1.89	0	1.13	0	0.37	0
deux	2.02	0	78.78	7.07	6.56	1.01	0.50	0.50	3.53	0
trois	2.40	0	2.40	86.14	1.20	4.81	0	0	2.40	0.60
quatre	0	1.5	3	0	86.00	0	1.00	0	4.50	4.00
cinq	1.87	0.62	5.00	12.50	1.87	72.50	0.62	0	3.75	1.25
six	2.35	0	7.64	0	3.52	3.52	81.17	0	1.76	0
sept	0.68	0.68	2.04	2.72	6.80	0	0	74.82	7.72	9.52
huit	3.61	1.80	3.01	3.61	4.21	2.40	0	1.20	78.91	1.20
neuf	0	1.12	1.12	1.12	5.64	1.12	0	0.56	2.25	87.00
TGBR											84.55

Tableau 3.8.Matrice de confusion de la classification multi classe le noyau RBF (ó =25)

P=1	zéro	Un	deux	trois	quatre	cinq	six	sept	huit	neuf
zéro	89.41	0	3.89	0.55	1.11	2.78	1.11	0.55	0.55	0
un	0	95.07	0	0	2.27	0	1.51	0.37	0.75	0
deux	1.01	0	72.72	2.52	8.08	2.52	4.04	3.03	6.06	0
trois	1.80	0	3.01	68.07	0.60	13.25	0.60	1.20	9.03	2.40
quatre	0.50	1.00	1.00	0	81.50	3.50	1.50	2.50	4.50	4.00
cinq	3.75	0	0	5	1.25	83.75	0	2.5	2.5	1.25
six	2.35	0	2.35	0	2.94	7.64	82.35	0.58	1.76	0
sept	1.36	0	1.36	0.68	3.40	1.36	0	87.07	1.36	3.40
huit	4.21	0	0.60	0.60	3.61	9.63	0	2.40	77.10	1.80
neuf	0	0.56	1.12	0	5.64	2.25	0	5.08	6.77	78.53
TGBR											82.76

Tableau 3.9.Matrice de confusion de la classification multi classe pour le noyau Polynomial (p=1)

P=2	zéro	Un	deux	trois	quatre	cinq	six	sept	huit	neuf
zéro	89.97	0	3.06	0.83	1.67	2.78	1.11	0	0.55	0
un	0	95.45	0	0	3.03	0	1.13	0	0.37	0
deux	1.51	0	73.23	3.03	7.57	2.52	4.04	1.01	7.07	0
trois	3.61	0	2.40	73.49	0.60	10.24	0	0	8.43	1.20
quatre	0.50	1.00	1.50	0	83.50	1.50	1.50	0	3.00	7.50
cinq	3.12	0	0.62	5.00	1.87	85.00	0	0.62	2.50	1.25
six	0.58	0	2.35	0	3.52	8.82	82.35	0	2.35	0
sept	0	0	2.04	0.68	4.76	1.36	0	78.23	2.04	10.88
huit	3.61	1.20	0	1.20	2.40	9.63	0	1.20	78.91	1.80
neuf	0	0.56	0.56	0	5.08	1.69	0	0.56	3.95	87.57
TGBR											84.01

Tableau 3.1 0.Matrice de confusion de la classification multi classe pour le noyau Polynomial (p=2)

P=3	zéro	Un	deux	trois	quatre	cinq	six	sept	huit	neuf
zéro	92.47	0	2.50	1.11	1.39	0.55	0.83	0.27	0	0.83
un	0	95.83	0	0	2.65	0	1.13	0	0.37	0
deux	2.02	0	77.27	3.53	6.56	1.51	4.04	1.51	3.53	0
trois	2.40	0	2.40	80.12	0.60	6.02	0.60	0	4.21	3.61
quatre	1.00	1.00	2.00	0	82.50	1.00	1.50	1.00	2.00	8.00
cinq	1.87	0	1.25	9.37	1.87	79.37	0.62	1.25	1.87	2.5
six	2.35	0	2.35	0	4.70	3.52	85.88	0.58	0.58	0
sept	0	0	2.04	0.68	4.08	1.36	0	82.99	0.68	8.16
huit	4.81	0.60	1.80	1.80	4.21	7.83	0.60	2.40	71.08	4.81
neuf	0	0.56	0.56	0	3.38	1.12	0	0.56	2.25	91.52
TGBR											85.25

Tableau 3.11 .Matrice de confusion de la classification multi classe pour le noyau Polynomial (p=3)

ã=0.2	zéro	Un	deux	trois	quatre	cinq	six	sept	huit	neuf
zéro	93.31	0	3.34	0.27	1.11	0.27	0.83	0.83	0	0
un	0	95.83	0	0	2.27	0	1.51	0.37	0	0
deux	1.51	0	86.86	2.52	3.53	1.51	1.01	2.02	1.01	0
trois	1.80	0	3.61	86.74	0.60	5.42	0.60	0	0	1.20
quatre	0	1.50	5.00	0	85.50	0	1.00	2.50	0	4.50
cinq	1.87	0	3.12	10.62	1.87	78.75	0.62	1.87	0	1.25
six	2.94	0	5.29	0	2.35	2.94	86.47	0	0	0
sept	0.68	0.68	2.72	0.68	3.40	0	0	88.43	0	3.40
huit	2.40	1.80	6.62	8.43	7.83	8.43	0	3.61	56.02	4.81
neuf	0.56	0.56	1.12	0.56	5.64	0.56	0	3.38	6.77	78.53
TGBR											86.00

Tableau 3.1 2.Matrice de confusion de la classification multi classe pour le noyau KMOD ã =0.2 et ó =6

ã =0.5	zéro	Un	deux	trois	quatre	cinq	six	sept	huit	neuf
zéro	93.87	0	1.67	0.55	1.11	0.55	0.55	0.55	0	1.11
un	0	93.81	0	1.13	1.89	0	2.27	0.37	0	1.13
deux	2.52	0	78.28	5.05	5.55	2.02	1.51	2.52	2.02	0.50
trois	1.20	0	2.40	87.34	0.60	6.02	0	0	0	2.40
quatre	0.50	0.50	2.50	0	81.50	1.00	1.00	2	0	10.00
cinq	2.50	0	1.25	8.75	1.87	80.62	0	1.87	0.62	2.50
six	3.52	0	3.52	0	2.35	4.70	85.88	0	0	0
sept	0	0	0.68	0.68	3.40	0	0	89.79	0	5.44
huit	4.81	0	0.60	7.22	4.21	8.43	0	3.01	63.25	8.43
neuf	0.56	0	0.56	0	2.25	0.56	0	2.25	0	93.78
TGBR											85.89

Tableau 3.13 .Matrice de confusion de la classification multi classe pour le noyau KMOD ã =0.5 et ó =6

ã=0.2	zéro	un	deux	trois	quatre	cinq	six	sept	huit	neuf
zéro	90.25	0	1.94	0.83	1.39	3.06	1.67	0	0.83	0
un	0	93.93	0	0	2.27	0	1.51	0	1.51	0.75
deux	2.02	0	68.68	3.03	7.57	2.02	3.53	1.01	12.12	0
trois	2.40	0	1.20	75.90	1.20	5.42	0.60	0.60	10.24	2.40
quatre	1.00	0.50	0.50	0	84.00	0	3.00	1.00	5.00	5.00
cinq	3.12	0	1.25	10	3.12	74.37	0	1.25	5.00	1.87
six	0.58	0	1.17	0	2.94	7.64	85.29	0	2.35	0
sept	0.68	0	1.36	1.36	4.76	0	0	82.31	4.08	5.44
huit	3.01	0	0	1.80	0.60	3.61	0	0	90.36	0.60
neuf	0	0.56	0	0	3.95	1.12	0	0.56	8.47	85.31
TGBR											84.10

Tableau 3.14.Matrice de confusion de la classification multi classe pour le noyau Distance négativeã =0.2

ã=0.1	zéro	un	deux	trois	quatre	cinq	six	sept	huit	neuf
zéro	91.36	0	3.62	0.55	1.11	0.27	2.22	0	0.27	0.55
un	0	95.45	0	0	2.27	0	1.51	0	0	0.75
deux	1.51	0	77.27	4.04	6.06	1.51	4.04	2.02	3.03	0.50
trois	2.40	0	1.20	77.10	2.40	7.22	0.60	1.20	3.01	4.81
quatre	0.50	0.50	1.50	0	82.00	0	4.00	0.50	1.00	10.00
cinq	4.37	0	2.50	12.50	3.12	71.25	0.62	0.62	2.50	2.50
six	1.17	0	2.35	0	2.94	5.29	87.64	0	0.58	0
sept	0	0	1.36	0	4.08	0	0	87.07	0.68	6.80
huit	5.42	1.80	3.61	1.80	4.21	7.83	0	1.20	71.08	3.01
neuf	0	0	0.56	0	3.38	0.56	0	1.12	1.12	93.22
TGBR											84.65

Tableau 3. 15.Matrice de confusion de la classification multi classe pour le noyau Distance négative ã=0.1

ã =0.05	zéro	un	deux	trois	quatre	cinq	six	sept	huit	neuf
zéro	92.75	0	1.39	0.83	1.11	0.27	2.22	0.55	0.27	0.55
un	0	93.93	0	0.75	1.51	0	3.03	0	0	0.75
deux	2.52	0	69.19	7.57	7.07	1.01	6.06	3.03	3.03	0.50
trois	1.80	0	1.20	86.74	0.60	3.61	0.60	1.80	0.60	3.01
quatre	1.00	0.50	1.00	0	84.00	0	3.00	1.50	0.50	8.50
cinq	4.37	0	1.25	13.12	2.50	75.00	0	1.25	0	2.50
six	2.35	0	0	0.58	2.94	5.29	88.82	0	0	0
sept	0.68	0	1.36	0.68	4.08	0	0	89.11	0	4.08
huit	4.81	0.60	0.60	7.83	7.22	7.22	0.60	1.20	66.26	3.61
neuf	0.56	0	0.56	0	5.64	1.12	0	1.69	0.56	89.83
TGBR											84.75

Tableau 3.16.Matrice de confusion de la classification multi classe pour le noyau Distance négative ã=0.05

3.5.2. Comparaison des résultats et discussions

noyau	RBF			polynomial			Distance négative			KMOD
classe										ã = 0.5	ã = 0.2
	ó=3	ó=10	ó=25	p=1	p=2	p=3	ã=0.2	ã=0.1	ã=0.05	ó=6	ó=6
0	92.75	89.69	90.25	89.41	89.97	92.47	90.25	91.36	92.75	93.87	93.31
1	93.18	95.07	95.83	95.07	95.45	95.83	93.93	95.45	93.93	93.18	95.83
2	84.34	80.30	78.78	72.72	73.23	77.27	68.68	77.27	69.19	78.28	86.86
3	80.12	83.73	86.14	68.07	73.49	80.12	75.90	77.10	86.74	87.34	86.74
4	85.50	87.00	86.00	81.50	83.50	82.50	84.00	82.00	84.00	81.50	85.50
5	82.50	73.75	72.50	83.75	85.00	79.37	74.37	71.25	75.00	80.62	78.75
6	86.47	77.64	81.17	82.35	82.35	85.88	85.29	87.64	88.82	85.88	86.47
7	80.27	79.59	74.82	87.07	78.23	82.99	82.31	87.07	89.11	89.79	88.43
8	90.96	74.09	78.91	77.10	78.91	71.08	90.36	71.08	66.26	63.25	56.02
9	93.22	89.26	87.00	78.53	87.57	91.52	85.31	93.22	89.83	93.78	87.57
TGBR	87.84	84.35	84.55	82.76	84.01	85.25	84.10	84.65	84.75	85.89	86.00

Tableau 3. 17.Résumé des résultats pour la classification multi classe

Globalement, les taux de bonne reconnaissance sont sensiblement similaires. Cependant, nous constatons que le choix du noyau et ses paramètres influent sur le taux de bonne de reconnaissance .Le noyau RBF pour ó =3 semble fournir les meilleurs taux de bonne de reconnaissance comparativement aux autres noyaux. L'examen du taux de bonne de reconnaissance pour chaque classe montre qu'il n'existe pas un noyau plus favorable .En fait les résultats obtenus dépendent des classes.

Nous présentons dans les figures suivantes le taux de bonne de reconnaissance pour chaque classe et pour différentes valeurs du paramètre du noyau.



Figure 3.3.Taux de bonne reconnaissance (%) pour chaque classe pour différents valeurs du
paramètre du noyau RBF.



Figure 3.4.Taux de bonne reconnaissance (%) pour chaque classe pour différents valeurs du
paramètre du noyau Polynomial.

Chapitre 3 Résultats expérimentaux



Y Y

Figure 3.5.Taux de bonne reconnaissance (%) pour chaque classe pour différents valeurs du
paramètre du noyau KMOD (a =6)



Y Y Y

Figure 3.6.Taux de bonne reconnaissance (%) pour chaque classe pour différents valeurs du
paramètre du noyau Distance négative

3.6. Comparaison classification binaire et multi-classe

L'analyse comparative entre la classification binaire et la classification multi-classe montre que le taux de bonne reconnaissance pour la classification binaire est meilleur quelques soit le noyau utilisé comparativement à la classification multi-classe. Cela peut se justifier par le fait que le classifieur SVM a beaucoup plus de difficultés à séparer une classe des autres classes comparativement à la classification binaire.

3.7. Présentation de la plateforme

Nous présentons dans cette section la plate forme de reconnaissance de chiffres manuscrits implémentés sous environnement Matlab .Les différentes fonctions implémentés sont décrits dans les sous- sections suivants.

3.7.1. Fenêtre principale

La fenêtre principale est composée (voir figure3.7) de trois menus :

· Fichier,

· Apprentissage

· Test.



Figure 3.7. Fenêtre principale

3.7.2 Menu

3.7.2.1. Sélection des fichiers (voir figure3.8) Le menu Fichier contient trois rubriques :

> Ouvrir la base d 'apprentissage : permet de sélectionner le fichier sur lequel porte l'apprentissage des SVMs .La sélection porte sur (voir figure3.9) :

· Le nom du fichier de données

· Le nom du fichier des classes

· Nombres d'images

· Hauteur de l'image

· Largeur de l'image

> Ouvrir la base de test : permet d'ouvrir la base de test et les classes correspondantes

>



Figure 3.8. Rubriques de menu Fichier

Figure 3.9. Exemple de chargement de la base d'apprentissage.

Fermer : sert à quitter la plateforme.

3.7.2.2. Sélection des paramètres pour l'apprentissage (voir figure3.10) Le menu Apprentissage contient deux rubriques :

> Svm multiclasse : permet de faire la classification multi-classe par le choix du noyau et le réglage de ses paramètres (figure3.11)

> Svm biclasse : permet de faire la classification bi-classe entre deux classes choisis en sélectionnant le noyau et ses paramètres (figure3.12).



Figure 3.10. Rubriques de menu Apprentissage.



Figure 3.11. Exemple de choix de noyau et les paramètres pour la classification multiclasse



Figure 3.12. Exemple de choix de noyau et réglage des paramètres avec possibilité de
sélectionner deux classes pour la classification biclasse.

3.7.2.3. Evaluation de la classification (voir figure 3.13)

Le menu Test contient deux rubriques :

> Test binaire : permet d'afficher la matrice de confusion et la précision globale pour la classification biclasse.

> Test multi : permet pour la classification multiclasse :

+ De calculer la matrice de confusion et la précision globale (voir figure 3.14).

+ D'afficher le taux de bonne reconnaissance de déférentes classes avec leur graphe (voir figure 3.15).

+ D'afficher le taux de bonne reconnaissance de déférentes classes sous forme d'une matrice de confusion et graphique avec la précision globale. (voir figure 3.16).

+ De récapituler tous les résultats obtenus avec les paramètres utilisés et d'afficher le temps d'apprentissage et le temps de test (voir figure 3.17).



Figure 3.13. Rubriques de menu Test.

Figure 3.14.Matrice de confusion avec précision globale.



Figure 3.15. Taux de bonne reconnaissance pour chaque classe représenté sous forme
graphique



Figure 3.16. Taux de bonne reconnaissance pour déférentes classes représenté sous forme
d'une matrice de confusion et graphique.



Figure 3.1 7.Résumé des résultats

3.8. Conclusion

Ce chapitre a été consacré à l'évaluation du classifieur SVM pour la reconnaissance des chiffres manuscrits. Les résultats obtenus montrent que la qualité de la reconnaissance dépend du choix du noyau et du réglage de ses paramètres.

Par ailleurs, nous avons pu constater que la séparation bi-classe permet de séparer plus facilement deux classes que de séparer une classe des autres classes.

CONCLUSION GENERALE

L'objectif de ce travail est l'étude et l'implémentation des machines à vecteurs de support ou SVMs (Support Vector Machines) pour la reconnaissance des chiffres manuscrits.

En général, la plupart des méthodes d'apprentis sage machine comme réseau de neurones possèdent un grand nombre de paramètres d'apprentissage à fixer par l'utilisateur. En contrepartie, la formulation élégante de SVM laisse très peu de place aux paramètres utilisateurs.

Différents algorithme d'optimisation sont disponibles parmi eux l'algorithme SMO (optimisation minimale et séquentielle du risque) qui est un algorithme simple et rapide proposé pour résoudre le problème de programmation quadratique des SVMs sans la nécessité de stocker une grande matrice en mémoire et sans une routine numérique itérative pour chaque sous-problème.

La méthode des SVM que nous avons implémentée a été testée sur des chiffres manuscrits d'une base standard (USPS) avec 500 chiffres pour l'apprentissage et 2007 pour le test en considérant deux stratégies un pour binaire entre deux classes les plus fréquemment confondues et l'autre pour multi classe avec l'approche un contre tous et en essayant dans les deux stratégies différents types de noyaux.

Les résultats obtenus montrent que la classification binaire permet de fournir des résultats meilleurs comparativement à la classification multi-classe.

Nous pensons que ce travail peut être complété par l'évaluation sur d'autres bases de données ainsi que sur d'autres types de noyaux. En outre les méthodes d'extraction des caractéristiques peuvent être envisagées pour améliorer le taux de bonne reconnaissance notamment avec la stratégie multi-classe.

REFERENCES BIBLIOGRAPHIQUES

[1] A. Belaid, et Y. Brlaid, 1992. << Reconnaissance des formes. Méthodes et application >> ; P 14 - 17.

[2] A. El Yacoubi, J-M Bertille, M Gilloux, et G Lorette, 1994. << Techniques de prétraitement pour la reconnaissance offline des mots manuscrits sans contrainte >> Service de Recherche de la Poste SRTP/RD/RVA; Nante, France ; CNED'94; P 3 15-321.

[3] C. Olivier, O. Colot, et P. Courtellemont, 1995. << Choix de paramètres pertinents pour la reconnaissance de chiffres manuscrits >> ; La3i-LACI UFR des Sciences, Université de Rouen, France ; CNED'94 ; P 27.

[4] C. Tappert, C. Y. Suen, and T. Wakahana, 1990. The state of the art in on-line handwrittin grecognition. IEEE Transaction on Pattern Analysis and Machine Intelligence,vol. 12, pp. 787-807.

[5] C.-W.HsuandC. and -J.Lin.A, 2002. comparison of methods for multiclass support vector machines. IEEE Tran-sactionsonNeuralNetworks, 13:41 5-425.

[6] D. Brucq, K. Romeo, M. Lachkar, N. Feray, et F. Bagui, 1982. << Une méthode d'évaluation du codage en reconnaissance de chiffres manuscrits >> ; UFR des Sciences et des Techniques, Mont-Saint-Aignan, France; CNED'94 ; P 19-20.

[7] Choksuriwong, H.LaurentB, 2005. Etude Comparative de Descripteurs Invariants d'Objets A Comparative Study of Objects Invariant DescriptorsA. Emile ENSI de Bourges Universite d'Orleans LaborateVisionetRobotique.

[8]F. Ali and Th. Pavlidis, 1977. Syntactic Recognition of handwritten Numerals. IEEETransaction on Systems, Man and Cybernetics, vol. n°7, pp. 537-541.

[9] G. Lorette, et Y. Lecourtier, 1992. « Reconnaissance et interprétation de textes manuscrits hors-ligne : un problème d 'analyse de scène ? » ; Université de Rennes 1 Campus de Beaulieu ; Mont Saint Aignan ; CNED'92 ; P 109-126.

[10] Hanoi, 15 juillet 2005. Réseaux de neurones pour la reconnaissance des formes

[11] H. S. Baird, 1993. << Recognition technology frontiers >> ; AT&T Bell Laboratoires, USA ; CNED'94 ; P 327.

[12] http://www.clopinet.com/isabelle/ Projects/SVM/applist.html.

[13] J. Bromley, and E. Sackinger, 1991. .Neural-network and k-nearest-neighbor classifiers.

Technical Report 11359-910819-1 6TM,ATT.

[14] J. Mantas, 1985. « An overview of character recognition methodologies >> ; National Centre of Medical Documentation, Greece ; CNED'94 ; P 425-427.

[15] J. Callut, 2002 <<Implémentation efficace des Support Victor Machines pour la classification». Mémoire présenté en vue de l'obtention du grade de Maître en Informatique.

[16] L. Likforman-Sulem, et C. Faure, 1995. << Une méthode de résolution des conflits d'alignements pour la segmentation des documents manuscrits >> ; Télécom Paris /SIG,CNRS URA 820 Paris, France ; CNED'94 ; P 265.

[17] M. Gilloux, 1994. << Reconnaissance de chiffres manuscrits par modèle de Markov pseudo-2D >> ; Service de Recherche Technique de la Poste, SRTP/RD/RVA , Nante, France ; CNED'94 ; P 11-13.

[18] M.NGHIEM Anh Tuan, 2005. <<Reconnaissance d'écriture manuscrite >>.

[19] M. H.Thien, M. Zimmermann, and H. Bunke, 1997. « Off-line handwritten numeral string recognition by combining segmentation-base and segmentation-free methods »; University of Berne, Institut fur Informatik and Mathematik, Neubruckstr, Switzerland ; CNED'94 ; P 257-25 8.

[20] N. Ayat, 2003. << Sélection de modèle automatique des machines à vecteurs de support >> application à la reconnaissance d'images de chiffres manuscrits. Thèse présentée à l'école de technologie supérieure, Montréal,Canada.

[21] J. C. Platt, 1998, Fast Training of Support Vector Machines using Sequential Minimal Optimization, SMO-Book, chap. 12, p. 41-65, In B. Schölkopf, C. J. C. Burges, A. J. Smola, editors, Advance in Kernel Methods - Support Vector Learning, Cambridge, MA, 1998, MIT Press.

[22] P. Telmosse, and R. Palmondon, 1998. « Caractérisation et classification de nombres manuscrits par méthodes statistique » Ecole polytechnique de Montréal, Laboratoire SCRIBENS ; IPAR '86 ; P 871-873.

[23] S.V. Rice, G.Nagy, and T. A. Nartker 1999. << Optical Charcater Recognition: An illustrated guide to the frontier », Kluwer Academic Publishers.

[24] R.W. Smith, « Computer processing offline images : A survey* » ; Departement of Computer Science, Queens Building, University of Bristol, University Walk, Bristol, BS8ITR, U.K ;CNED'94 ; P 8

[25] S. Njah , A. Triki et A. M.Alimi, Novembre1998, << Système de reconnaissance de code postal >> 18 éme Conférence Tunisienne d'Electrotechnique et d'Automatique, , Hammamet, Tunisie.

[26] S. Mori, K. Yamamoto, Member IEEE, and M.Yasuda, Member IEEE, 1992. << Research on machine recognition of hand printed characters >>.

[27]V.Vapnik, 1995 .the nature of statistical learning throry. springer_verlag,New_York,USA.
V. K. Govindan, 1990. << Character recognition - A review >> ; Department of Electrical communication engineering, India ; CNED'94 ; P 671-672.

[29] Vincent Rialle ,2000. Évaluation des systèmes d'aide à la décision- courte introduction. Maître de conférences en informatique. Article de recherche.

[30]Y.LeCun,B.Boser, J.S.Denker, D.Henderson, R.E.Howard, W.Hubbard, and L.D.Jackel . 1 989Backpropagation applied to handwritten zip code recognition. Neural Computation, vol 1, N : 4, pp.541-551.





. (

)

Support Vector Machines (SVMs)

"

"

( SVM ) .

. (SVs)

i

. i (USPS)

.

,

,

.

:

Abstract



In this work, we are interested in a new method of training and classification based on artificial training theory of Vapnik. This method named Support Vector Machines (SVMs) has been adapted and applied to a problem of the handwritten number recognition. The advantage of SVMs is that a restricted number of samples is sufficient to the determination of the vectors support (SVs) allowing discrimination between the classes comparatively to the statistical estimation. Obtained results on image of USPS base are satisfactory and very encouraging.

Key words: training, classification, support vector machines (SVMs), handwritten number recognition.

Résumé

Dans ce travail, nous nous intéressons à une nouvelle méthode d'apprentissage et de classification basée sur la théorie de l'apprentissage artificiel de Vapnik. Cette méthode appelée les Machines à Vecteurs de Support (SVMs pour Support Vector Machines) a été adaptée et appliquée au problème de la reconnaissance des chiffres manuscrits. L'avantage des SVMs est q'un nombre restreint d'échantillon suffit à la détermination des vecteurs de support (SVs) permettant la discrimination entre les classes contrairement à l'estimation statistique. Les résultats obtenus sur des images de la base USPS sont satisfaisants et très encourageants.

Mots dlés : apprentissage, classification, machines à vecteurs de supports (SVMs), reconnaissance des chiffres manuscrits.