SVM[1] signifie Support Vector Machines. En français on peut choisir la traduction littérale Machines à Vecteurs de Support, ou bien (pour conserver l'acronyme anglo-saxon) adopter l'expression Séparateurs à Vaste Marge, qui a le mérite d'expliquer un peu mieux (?) en quoi ça consiste.
Il s'agit d'une méthode de classification[2] dont le but est d'identifier des patterns (des formes, des structures ...) dans des données complexes. Il s'agit donc d'une technique utilisée en apprentissage automatique, branche de l'intelligence artificielle. Son développement rapide depuis le début des années 2000 s'explique par son succès dans des domaines appliqués : bio-informatique, reconnaissance d'écriture, reconnaissance de forme en traitement d'image, data mining au sens large ... Elle regroupe des utilisateurs venant de communautés variées : statistiques, optimisation, réseaux de neurones ...
Si ce que j'ai compris devait me conduire à dessiner une mini-arborescence, elle ressemblerait à ça :
L'idée de base des SVM est de déterminer une frontière[3] qui maximise la distance entre elle-même et les points les plus proches. Ce n'est pas très compliqué en 2D (du moins quand il existe une frontière linéaire), mais un peu moins simple en dimension plus grande ...
Il est heureusement possible de se ramener à un problème d'optimisation quadratique sous contraintes, qui sous sa forme duale devient un problème convexe, que l'on sait résoudre en un temps raisonnable (i.e polynomial[4]).
La notion de kernel vient, lorsqu'il n'existe pas de séparateur linéaire, de l'utilisation de fonctions-noyaux permettant de transformer l'espace des données d'entrée en un espace (de plus grande dimension) où l'on peut utiliser un séparateur linéaire.
Quelques liens :
- http://www.support-vector.net/icml-tutorial.pdf
- Machine à vecteurs de support (wikipedia)
- http://fr.wikipedia.org/wiki/Kernel_trick
- http://www.kernel-machines.org/
- une toolbox Matlab sur le site d'Alain Rakotomamonjy
- "Modélisation dynamique par réseaux de neurones et machines à vecteurs supports: contribution à la maîtrise des émissions polluantes de véhicules automobiles." (Thèse de Marc Lucea, Univ. Paris VI, 22/09/2006)
Quelques mots-clés plus ou moins connexes :
- Algorithme espérance-maximisation (Expectation-maximisation - EM - algorithm)
5 réactions
1 De Vicnent - 05/01/2011, 21:28
'tain, t'es encore en vacances pour publier comme ça ? :-)
Sinon, les problèmes d'optimisation dont la fonction est quadratique sont résolubles en temps polynomial dans deux cas :
- la marmotte, elle met simultanément le papier autour du chocolat
- sur un yacht, acheté avec le million de dollar du Clay Institut.
(en 0-1, c'est sûr..., en continu, c'est probablement différent :-)
2 De Eric C. - 05/01/2011, 21:33
Il s'agit évidemment de continu. Plein de softs font ça très bien ...
Quelques idées sur en.wikipedia.org/wiki/Seq... par ex
3 De Eric C. - 05/01/2011, 21:34
(non, plus en vacances, mais ça trainait depuis longtemps, il suffisait d'un coup de chiffon à poussière ... et comme je suis en train de faire des tests sur ce que j'avais fait en fin d'année, j'ai qques moments de temps libre :))
4 De Emmanuel - 06/01/2011, 21:19
Et j'ajouterais les liens suivants, pour ceux qui veulent aller plus loin :
- SVMlib, qui est une bibliothèque très complète (www.csie.ntu.edu.tw/~cjli...
- scikits.learn, qui permet de faire des SVM (et plein d'autres choses) avec ce superbe langage qu'est Python (scikit-learn.sourceforge....
5 De Eric C. - 06/01/2011, 22:53
Merci pour les liens, le 2e a l'air sympa, avec des exemples accessibles à un ingé :)
(Liens corrigés d'ailleurs, dotclear est pénible : quand on met des liens entre parenthèses et qu'il doit les réduire, il considère bêtement que la parenthèse fermante fait partie de l'url ...)