Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
Télécharger au format pdf ou txt
Vous êtes sur la page 1sur 2
ALCTRA R&D
INTRODUCTION AUX MACHINES A VECTEURS DE SUPPORT (SVM)
1. Historique
L’aptitude à généraliser des résultats Le principe théorique des SVM comporte
obtenus à partir d’un échantillon limité deux points fondamentaux : constitue l’enjeu essentiel de l’apprentissage artificiel (machine ! la transformation non linéaire (Φ) learning). Il n’est plus à démontrer que la des exemples de l’espace d’entrée seule minimisation du risque empirique vers un espace dit de redescription (l’erreur d’apprentissage) ne garantit pas de grande dimension muni d’un une faible erreur sur un corpus de test. produit scalaire (espace de Hilbert), Ainsi les techniques de régularisation, utilisées depuis les années 1960, Espace de redescription permettent-elles de réaliser un F Espace compromis entre la capacité du modèle à d’entré e apprendre (liée à sa complexité) et son X aptitude à généraliser. Du point de vue Espace de sortie conceptuel, la notion de risque structurel Φ h introduite par Vladimir Vapnik dans les Redescription séparation années 1990 [1] donne une borne de . . non linéaire linéaire . l’erreur de test en fonction de l’erreur . d’apprentissage et de la complexité du . . modèle. En pratique, les machines à vecteurs de support (Support Vector Machines ou SVM), présentées en 1992 Figure 1. La transformation non linéaire des [2], offrent un moyen opérationnel pour données peut permettre une séparation linéaire des minimiser le risque structurel, ce qui exemples dans un nouvel espace. Adapté de [3]. explique l’engouement suscité dans la communauté scientifique. ! la détermination d’un hyperplan permettant une séparation linéaire 2. Principe optimale dans cet espace de grande dimension. A l’origine conçues pour les tâches de Marge classification ou reconnaissance de maximale
formes, les SVM permettent également
de traiter les problèmes de régression non linéaire. Nous privilégions ici leur intérêt pour la reconnaissance de formes Ve cteurs de 1/||w|| (i.e. la découverte de caractéristiques support Hyperpl an communes dans un ensemble de optimal données sans connaissance a priori du domaine). Dans ce contexte, l’acronyme SVM peut être judicieusement traduit par Figure 2. L’hyperplan séparateur optimal est celui qui Séparateurs à Vaste Marge [3]. maximise la marge dans l’espace de redescription. ALCTRA R&D
L’intérêt est que dans l’espace de Différents programmes d’optimisation
redescription la reconnaissance de sont disponibles gratuitement sur formes peut s’avérer tâche aisée : en Internet [4] : CPLEX, LOQO, MINOS, effet, intuitivement, plus la dimension de SMO, etc. l’espace de redescription est grande, plus la probabilité de pouvoir trouver un hyperplan séparateur entre les exemples 4. Applications est élevée. Ce qu’illustre le schéma suivant. Les méthodes à noyaux, inspirées de la théorie statistique de l’apprentissage de Vapnik, et dont les SVM constituent la forme la plus connue, ont été adaptées à divers contextes : classification avec apprentissage, estimation de support de densité, régression, etc.
Les SVM sont appliqués avec une
efficacité remarquable à la Figure 3. L’idée des SVM : transformer un problème reconnaissance de caractères manu- de séparation non linéaire dans l’espace de représentation scrits, au traitement d’images, à la en un problème de séparation linéaire dans un espace de prédiction de séries temporelles, au re-description de grande dimension. Adapté de [5]. diagnostic médical, au contrôle qualité, etc. Des exemples d’application réussie des SVM peuvent être consultés sur Du point de vue mathématique, la Internet [6]. transformation non linéaire (Φ) est réalisée via une fonction noyau (ou noyau de Hilbert-Schmidt) facile à calculer. Ainsi l’espace de redescription reste virtuel, Références jamais explicité. [1] V. Vapnik, The Nature of Statistical En pratique, quelques familles de Learning Theory, Springer-Verlag, 1995. fonctions noyau paramétrables sont [2] B.E. Boser, I.M. Guyon, V. Vapnik, A connues et il revient à l’utilisateur de SVM Training Algorithm for Optimal Margin d’effectuer des test pour déterminer celle Classifiers, Proc. Fifth Ann. Workshop qui convient le mieux pour son application Computational Learning Theory, ACM (il s’agit de traduire le maximum de Press, 1992, pp. 144-152. connaissances préalables dont on dispose sur le problème étudié et sur les [3] A. Cornuéjols, L. Miclet, Y. Kodratoff, données). Apprentissage artificiel, Eyrolles, 2002. Chapitres 2 et 9. [4] http://www.kernel-machines.org/ 3. Optimisation [5] B. Schölkopf, A.J. Smola, Learning Le problème de recherche de l’hyperplan with kernels, MIT Press, 2002. séparateur optimal possède une formu- [6] http://www.clopinet.com/isabelle/ lation duale. Ceci est particulièrement Projects/SVM/applist.html. intéressant car, sous cette formulation duale, le problème peut être résolu au moyen de méthodes d’optimisation quadratique standard.
Détection des piétons: S'il vous plaît, suggérez un sous-titre pour un livre intitulé « Détection des piétons » dans le domaine de la « Vision par ordinateur ». Le sous-titre suggéré ne doit pas contenir de ':'.