Khoufi Héla,Poinsignon Jean-Marc dea icsv tp1: étude bibliographique

L

Khoufi Héla

Poinsignon Jean-Marc

DEA ICSV

e 4 février 2000


DEA ICSV ---- reconnaissance des formes ----- Stephane CANU

AN IMPROVED TRAINING ALGORITHM FOR SUPPORT VECTOR MACHINES

L'apprentissage des SVM nécessite une large base de données ainsi qu'un grand nombre de vecteurs de support, points de données liés à la bordure entre deux classes. Cette opération va revenir à résoudre un problème de programmation quadratique (PQ) linéaire. Cependant, la stratégie utilisée dans les algorithmes de base, n'autorise pas plus de quelques milliers de points de données. Ainsi, un algorithme de décomposition décrit dans l'article, propose une amélioration garantissant la résolution du problème PQ avec une base de données plus volumineuse et un nombre de supports vecteurs plus important.

La classification SVM permet la construction d'un hyperplan approprié, de façon à former une marge maximale entre deux classes ( linéairement séparable ou non)de vecteurs, minimisant ainsi l'effet de l'erreur de classification, ou risque structurel. Dans le cas de non séparabilité linéaire des deux classes, on cherchera à minimiser en plus le nombre de classifications défectueuses.

Le problème de la classification revient à déterminer le signe de la fonction de décision f(x):

xR^d , yi={+1,-1} , C=cst , 0iC , (xi,yi) ensemble des échantillons

K(x,xi): noyau de la fonction, représente le produit scalaire dans l'espace de caractéristiques.

wx+b=0, l'équation de l'hyperplan

Pour l'apprentissage du SVM, on considère deux conditions:

Les conditions d'optimisation, utilisées pour déterminer la manière suivant laquelle sera résolu le problème PQ original, présenté comme suit:


Minimise W(_^)= - _^^T1 + 0.5*_^^TD <sub>^

^</sub>

sachant que _^^Ty=0 () ^, _^-C10 () , -_^0 ()

W(_^)+-+y = 0

^T (_^- C1) = 0

^T_^ = 0

• 
   0
  

  0

_^ ^T y = 0

_^- C1  0

-_^  0

Conditions KT : nécessaires et suffisants pour l'optimisation

(1)

La stratégie d'amélioration :consiste à décomposer _^ en deux vecteurs _^B et _^N où B est l'ensemble de travail.


Sachant que (- _{^ N} ^T1+0.5* _{+^ N} ^TD _{N N ^ N} ) =cst et _(^B ^TD _{B N ^ N + ^ N} ^TD _{N B ^ B ) = 2^ B} ^T q _{B N}






Algorithme de décomposition :

• 
  Choisir les points de B parmi les données
  
• 
  Résoudre le sous problème en utilisant les variables dans B
  
• 
  En utilisant (1) et (2) avec i  N , on résout le nouveau sous problème donné par (2)
  

Cet algorithme améliore strictement la fonction objective. Si elle est bornée, l'algorithme doit converger vers une solution optimale et globale avec un nombre fini d'itérations.

Implémentation et résultats:

• 
  Matériel : SUN Sparc 20 (128 Mb de RAM ) avec le logiciel solveur MINOS 5.4
  
• 
  Entrée : 110.000 points
  
• 
  Temps d'exécution : 3 heures pour 10.000 vecteurs de support , 48 heures pour 40.000 vecteurs de support et 200 heures pour 110.000 vecteurs de support
  
• 
  Perspective: Résultats obtenus comparables à ceux de l'approche réseaux de neurones où les erreurs de généralisation atteignent environ 53%. Les résultats ont montré que la méthode est valable avec un nombre de SVM supérieur à 100.000.
  

ANALYSE CRITIQUE

Nous allons décomposer cette partie, en une analyse des courbes résultat, puis en une vue d'ensemble de l'article.

Analyse des courbes:

O

n constate que la génération des SV est linéaire en fonction du nombre de données (courbe 1). Remarquons que la pente de la droite est sensiblement inférieure à 1. Ce qui entraîne une génération de SVM un peu inférieure au nombre de points d'entrée, ce qui est visible avec grand nombre de points. En ce qui concerne la deuxième courbe, nous avons fait une approximation linéaire, grâce à laquelle on remarque deux phases: la première se traduit par une évolution rapide du nombre de points traité par unité de temps, soit environ 2000 pts/h . Dès 30000 points on constate un ralentissement de

l'exécution. La deuxième phase est donc plus lente, l'évolution tend vers 400 pts/h. D'après les courbes il semble que l'algorithme se stabilise , dans le cas de l'exemple présent, à partir de 30000 points.

Tous ces élément montrent qu'il y a une "convergence" du coût de l'algorithme en terme de vitesse. Pour généraliser les performances de l'algorithme il serait bien de faire une acquisition de plus de points de façon à mieux suivre l'évolution des courbes. Remarquons que le nombre de points a été fixé à 110 000, que se passe t-il au delà? La date de publication de l'article est 1997 mais les essais datent de 1992, il serait intéressant de renouveler les opérations avec des calculateurs plus ressent de manière à étendre le champ d'étude.
Vue d'ensemble:

Les SVM sont appliqués dans plusieurs études et plus précisément dans le domaine de l'OCR. Ils sont utilisés pour la prédiction de séries de temps " prédicting times series" , pour la classification et les problèmes de régression ainsi que pour l'apprentissage et l'extraction des caractéristiques.

Les SVM sont comparées avec plusieurs approches (ex: RBF= Réseaux des fonctions à base radiale) et ont montrés d'excellentes performances. Aussi ils voient leur application s'étendre, on parlera ainsi de SVM, mais aussi SV mixture. Les inconvénient restent tout de même liés au coût temporel et à la limite en volume de données, cependant avec la croissance des calculateurs, les SVM voient leur intérêt grandir avec l'évolution technologique.