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

La méthode des noyaux est une technique récente en reconnaissance de formes. Elle consiste à projeter les données qui sont initialement non séparables dans un autre espace de dimension plus élevée où elles peuvent le devenir. Les classifieurs utilisant la méthode des noyaux, contrairement aux classifieurs traditionnels, construisent la fonction de décision dans un nouvel espace autre que 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 classifieur. Les machines à vecteurs de supprot, issues des travaux de Vapnik, utilisent cette technique des noyaux qui permet de traiter linéairement dans le nouvel espace les problèmes préalablement non linéaires.

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

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

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

Dans le cadre de ce mémoire de maîtrise, nous nous sommes donnés pour objectif l’optimisation des ressources au cours de la procédure de sélection de modèle en utilisant l’erreur empirique compte tenue des vertus de ce critère. L’optimisation des ressources vise à réduire le temps de calcul du CPU et l ‘espace de stockage mémoire afin de faciliter l’intégration de la sélection de modèle dans des applications réelles avec moins de coût. Ainsi, pour arriver à nos fins, nous proposons :

• une approximation du gradient de 1′ erreur empirique, ce qui nous permet de déterminer le gradient sans inverser la matrice de Gram-Schmidt, réduisant ainsi la complexité du calcul du gradient.
• une stratégie d’apprentissage incrémentai des SVM, technique qui permet de faire évoluer parallèlement la procédure d’optimisation des paramètres du modèle et l’apprentissage dans une technique de jumelage.

Pour éviter la complexité de la fonction de décision au cours de 1′ apprentissage, il est souvent intéressant de projeter les données dans un autre espace de caractéristiques de dimension plus élevée. Dans ce nouvel espace de représentation, les données qui étaient difficilement séparables peuvent le devenir avec une fonction de décision moins complexe. Comme exemple, considérons deux classes de données représentées par deux cercles concentriques de rayon respectif 1 et 0,5 .

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

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

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

Classitïcation multi-classe avec les SVM

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

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

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