Soutenance mémoire
La Reconnaissance des Formes (RF) dont le but consiste à associer une étiquette (une classe) à une donnée qui peut se présenter sous forme d’une image , d’un signal… etc., est un axe fort important du domaine de l’intelligence artificielle, qui trouve application dans beaucoup de systèmes comme les interfaces visuelles, l’analyse de données, la bioinformatique, le multimédia,… etc. Plusieurs méthodes ont été développées dans ce domaine, en particulier les Réseaux de Neurones avec le perceptron multicouche (MLP). Ces classificateurs ont fait l’objet de nombreuses recherches et ont donné des résultats impressionnants. Et depuis longtemps, les perceptrons multicouches ont été utilisés avec succès pour résoudre de nombreux problèmes de classification en RF.
Mais, de plus en plus, avec la diversité des applications de la Reconnaissance de Formes, plusieurs problèmes non linéaires faisant intervenir la classification sont rendus complexes. Ainsi, depuis quelques années, pour contourner la complexité des fonctions de décision construites pour les problèmes non linéaires, les recherches ont donné naissance à de nouvelles méthodes de classification basées sur les noyaux (kemel methods) qui s’avèrent plus robustes et plus simples que d’autres méthodes telles que les couches cachées introduites dans les Réseaux de Neurones.
La méthode des noyaux est une technique récente en reconnaissance de formes. Elle consiste à projeter les données qui sont initialement non séparables dans un autre espace de dimension plus élevée où elles peuvent le devenir. Les classificateurs utilisant la méthode des noyaux, contrairement aux classificateurs traditionnels, construisent la fonction de décision dans un nouvel espace autre que l’espace des caractéristiques d’entrée; ce qui permet de réduire la complexité de la fonction de décision tout en gardant une bonne performance du classificateur. Les machines à vecteurs de supports (SVMs), issues des travaux de Vapnik [Vapnik,1995], utilisent cette technique des noyaux qui permet de traiter linéairement dans le nouvel espace les problèmes préalablement non linéaires.
L’Apprentissage Automatique et la Classification des données
Généralités
La résolution de problèmes par la construction de machines capables d’apprendre à partir d’expériences caractérise l’approche fondamentale du Machine Learning (ML). Parmi les techniques du ML on trouve entre autres les méthodes supervisées et non-supervisées. Dans le cas des méthodes supervisées, on cherche à estimer (à apprendre) une fonction f(x) à partir d’exemples.
Dans ce cadre, un exemple consiste en un objet ou sa représentation (un document, une image, les caractéristiques d’une fleur, … ) accompagné de la catégorie à laquelle il appartient. La fonction f(x) que l’on va chercher à estimer, détermine la relation entre les objets et leur catégorie. Un classificateur sera donc caractérisé par la fonction f(x) qu’il implémente. On dira qu’un classificateur a un grand pouvoir de généralisation s’il fournit de bons résultats sur des données différentes de celles qui ont été utilisées pour l’apprentissage.
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.
La classification en théorie
Dans l’introduction, nous avons donné une idée intuitive de ce qu’est la classification automatique. Dans cette section, nous nous employons à la formaliser en définissant sa forme mathématique et en introduisant le contexte statistique requis par l’approche Machine Learning Supervisé.
Formulation
La tâche qu’un classificateur doit effectuer peut être exprimée par une fonction que l’on appelle fonction de décision: [Duda et al, 2000]
f : x → y
où x est l’ensemble des objets à classer (aussi appelé espace d’entrée)
y est l’ensemble des catégories (aussi appelé espace d’arrivée)
Dans la suite du document, nous nous limitons à la classification binaire.
Machine d’apprentissage
On désigne par machine d’apprentissage, une machine dont la tâche est d’apprendre une fonction à travers des exemples. Une machine d’apprentissage est donc définie par la classe de fonctions F qu’elle peut implémenter. Dans notre cas, ces fonctions sont des fonctions de décision. Nous notons une famille de fonctions telle que chacun de ses membres est caractérisé par une valuation unique des paramètres Yi. A titre d’exemple considérons la famille qui représente l’ensemble des fonctions de décision d’un classificateur linéaire élémentaire: le perceptron.
Dans la terminologie Machine Learning on l’appelle surgénéralisation – overfitting. Concrètement cela dit deux choses:
● D’une part, en limitant fortement la taille de l’ensemble F , on tend à expliquer la relation entre les objets et leur classe de manière trop grossière (surgénéralisation). Dans ce cas le risque empirique sera élevé mais le modèle ne « collera » pas aux exemples de trop près.
● D’autre part, si on admet un grande nombre de fonctions, la relation sera modélisée de manière complexe et le bruit associé aux mesures (acquisition d’image, de caractères, … ) risque également d’être appris (overfitting). On parle souvent d’apprentissage par cœur parce que le classificateur aura un risque empirique très faible mais ses performances sur d’autres jeux de données seront mauvaises.
Conditions de validité de MRE
Dans cette sous-section, nous effectuons une analyse statistique du type VapnikChervonenkis de MRE. Par souci de clarté, nous préférons présenter une analyse quelque peu simplifiée plutôt qu’un traitement mathématique tout à fait rigoureux. Les résultats obtenus ne seront par conséquent pas les plus raffinés, cependant les concepts dégagés fourniront de bons éléments de réponse à notre question.
|
Table des matières
Introduction générale
Chapitre 1 : L’Apprentissage Automatiques et la Classification des données
1.1 Généralités
1.2 La classification en théorie
1.2.1 Formulation
1.2.2 Modèle génératif des données
1.2.3 Fonction d’erreur et risque
1.2.4 Machine d’apprentissage
1.2.5 Risque empirique
1.3 Analyse statistique de l’apprentissage
1.3.1 Insuffisance de MRE
1.3.2 Conditions de validité de MRE
1.3.3 Dimension VC
1.3.4 Minimisation du risque structurel (MRS)
1.3.5 Régularisation du risque
1.4 La classification en pratique
1.4.1 Ensemble de données
1.4.2 Entraînement ou apprentissage
1.4.3 Evaluation du modèle (test)
1.4.4 Exploitation
1.5 Quelques Méthodes de Classification
1.5.1 Approches statistiques
1.5.2 Méthodes paramétriques
1.5.3 Méthodes non paramétriques
1.5.4 Les Réseaux de Neurones
1.5.5 Classification par Modèle de Markov Caché
Conclusion
Chapitre II : Les Machines à Vecteurs de support
1.1 Introduction
1.2 Risque structurel
2.3 Espace augmenté
2.4 Formulation
2.4.1 Hyper-plans de séparation
2.4.2 Hyper-plans à marge optimale
2.4.3 Hyper-plans à marge molle
2.4.4 Le SVM non-linéaire
2.4.5 Conditions de Karush-Kuhn-Tucker
2.4.6 Calcul du biais
2.5 Discriminant de Fisher non-linéaire (KFD)
2.6 Analyse en Composantes Principales non-linéaire
2.7 Classification mono-classe
2.8 Algorithmes d’apprentissage du SVMs
2.8.1 Méthode de chunking
2.8.2 Méthode de décomposition successive
2.8.3 Méthode de minimisation séquentielle: SMO
2.8.4 Algorithme de Joachims
2.9 Classification de données multi-classes
Conclusion
Chapitre III Techniques pour la Réduction de Dimension
3.1 Introduction
3.2 Propriétés des espaces à grandes e dimension
3.3 Techniques linéaires de Réduction de dimension
3.3.1 Analyse en Composantes Principales (ACP)
3.3.2 Analyse en Composantes Indépendantes (ACI)
3.3.3 Analyse Linéaire Discriminante (LDA)
3.4 Techniques de réduction non- linéaires
3.4.1 Isomap
3.4.2 Plongement localement linéaire
Chapitre IV Contribution et Expérimentations
4.1 Introduction
4 .2 Mise en pratique des Séparateurs à Vaste Marge
4 .3 Proposition d’une nouvelle approche de sélection de vecteurs supports
4.4 Résultats expérimentaux de l’approche de sélection par K-moyenne
4.4.1 Résultats Expérimentation de la base Ripley
4.4.2 Résultats expérimentaux de la base Banana
4.4.3 Autres bases de données
4.5 Sélection de données au sein d’un espace LDA
4.5.1 Calcule du modéle LDA
4.5.1 Résultats expérimentaux de la combinaison LDA/K-moyenne
4.6 Application à la reconnaissance des Mots Arabes manuscrits
4.6.1 Bases de données des noms des Wilayas Algériennes
4.6.2 Prétraitement de l’image
4.6.3 Les Caractéristiques Structurelles
4.6.4 Les caractéristiques statistiques
4.6.7 Résultats expérimentaux de la sélection proposée
Conclusion
Conclusion
