Apprentissage et noyaux : séparateur à vaste marge (SVM)

29/08/2017
Auteurs : Stéphane Canu
Publication REE REE 2006-7
OAI : oai:www.see.asso.fr:1301:2006-7:19693
DOI :

Résumé

Apprentissage et noyaux : séparateur à vaste marge (SVM)

Métriques

16
4
2.56 Mo
 application/pdf
bitcache://cc21b5a294f780922d6fadc302a23d41c5825258

Licence

Creative Commons Aucune (Tous droits réservés)
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/1301:2006-7/19693</identifier><creators><creator><creatorName>Stéphane Canu</creatorName></creator></creators><titles>
            <title>Apprentissage et noyaux : séparateur à vaste marge (SVM)</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2017</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Tue 29 Aug 2017</date>
	    <date dateType="Updated">Tue 29 Aug 2017</date>
            <date dateType="Submitted">Fri 20 Jul 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">cc21b5a294f780922d6fadc302a23d41c5825258</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>33464</version>
        <descriptions>
            <description descriptionType="Abstract"></description>
        </descriptions>
    </resource>
.

Dossier DU TRAITEMENT NUMÉRIQUE À LA GESTION DES CONNAISSANCES DE NOUVELLES VOIES D'INVESTIGATION ? fi " partie Apprentissage et noyaux 'Or séparateur à vaste marge (SVM) Stéphane CANU INSA de Rouen, LI>-IS Mots clés Apprentissagestatistique, Discrimination,Noyau, Machineà noyau, Séparateuràvastemarge, Machineàvecteurs supports, SVM Introduction 1 Si l'on doit, à la main, tracer une frontière entre eux classes à partir d'un ensemble d'exemples, un certain nombre de principes vont régir notre vision du problème. Nous proposons de mettre en avant quatre de ces princi- pes illustrés par la figure 1 : . fidélité, . régularité, . décision locale, . points frontière. La fidélité aux données va de soit. Les données sont la seule information dont on dispose : il semble évident qu'il faille les respecter. Ce principe est vrai jusqu'à un certain point. En effet, une croix seule au milieu de ronds sera souvent regardée comme une erreur. La régularité de la solution est moins évidente mais elle est illustrée par la partie droite de la figure 1. Dans cette zone, ronds et croix semblent mélangées. Il n'est pas pour autant souhaitable de les séparer par une frontière chaotique dont la forme nous rappellerait les côtes bretonnes. Nous avons plutôt tendance à privilégier les frontières régulières à qui nous tendons intuitivement à accorder plus de crédit. Il se trouve que cette intuition a des fondements formels que nous allons présenter. L'aspect local de la décision traduit le fait que la pré- sence d'une croix en bas à gauche de la figure ne va pas Dis 0 et de reformuler les contraintes de fidélité : l r'-r)7l -_'rrr nt (), i = I. rr C'est ce m que l'on va appeler la marge du classifieur et qui est défini comme la plus petite distance entre la frontière de décision et les observations : iiiiii 1 i- 1. ?t..' iiiiii 11 Mais pour bien classer tout le monde il suffit de jouer sur les échelles et de se fixer (w - 1) : (.i*) !/, > (1) 2,1.2. Fidélité et droit à l'erreur : minimiser l'erreur Il peut arriver qu'il y ait des erreurs dans les données. La modélisation doit prendre en compte cette éventualité. Une manière de faire consiste à introduire, pour chaque exemple, une variable d'écart /. La fidélité aux données se récrit alors : L 1 1 f,- c - f,-,, 1 l li > (). i On souhaite bien sur que ces variables d'écart soient les plus petites possible. formellement cela revient à minimi- ser un critère de la forme : Il iiiiii i ? - 1 où désigne le vecteur des . Dans la suite nous choi- sirons p - 1. Il est possible de faire d'autres choix sans modification fondamentale des raisonnements (tant que p > 1 le critère reste convexe) Les Çi sont des variables d'écart pour lesquelles on va distinguer trois cas. /xi 0 le point est bien classé avec une bonne confiance puisqu'il est dans la marge. Lorsque 0 < Çi < 1 le point est toujours bien classé, mais il est douteux. Quand enfin Çi > l, le point est carrément mal classé (ou mal étiqueté). Nous allons maintenant voir le critère de régularité. signe (f (.i', 1= 1. l 2.2. Régularité 2.2. 1. Pourquoi une solution régulière Supposons que nous disposions de deux solutions vérifiant = 0, i - 1, n. La quelle choisirions-nous des REE Nn 8 Septembre2006 Apprentissage et noyaux : séparateur à vaste marge (SVM) so !ut!on re!ui:è!'esolution réluliére solution irrégullère Figure 2. Les d (-tixfolictioiis ; ei-te et iiiative sépai-entpafaite- i ? zent les i-onds des ci-oix. \ [til (1, li 111,11, 1, c i, Ili,, i Ille Il, l, [1 il l Figur-e 4. Iiiiisti-atioii de la relation entre la iiiaige et la iioi-ine du elassifieur lirzéaire. 21c] li ii,ilnll,2 1, e(1!. li!u,.irc - pwll,oluii, de noyatix zisiiel.. Lafigtire de droile illlisti-e le inodé defonctioiineiiient des zones d'infltieiiceassociée. à un noyai (. On a alors le raisonnement suivant : . minimiser [P(err) maximiser la marge . maximiser la robustesse maximiser la marge . maximiser la marge minimiser If 12 Mis bout à bout, les critères que nous nous sommes données se formulent ainsi : .f Ui, : cc s i - () i ii nmiy 1 i ,/ i=l Uiilj)!/'' f Reste à préciser dans quel ensemble d'hypothèses nous allons choisir la fonction f Pour définir cet ensemble, nous allons utiliser la notion de noyau. 3. Noyau et hypothèses 3.1. Apprendre c'est choisir une hypothèse A partir des critères que nous venons de formuler, apprendre consiste, pour être universel, à se donner un ensemble d'hypothèses H assez grand a priori dans lequel l'optimisation va s'effectuer. Le problème se pose alors dans H : /1 - 1, ; l \ ( (.', t)./- 1. fi N v Jh" \ 11, c Il /l2 tout en minimisant simultanément -i-J' et 1 1H.. Une première idée pour construire en ensemble d'hypo- thèse très général, consiste à le construire à partir d'une famille génératrice. Soit (0j) Ej une base orthonormée de fonctions (polynômes, Fourier, ondelettes... etc.). Les fonctions qui s'écrivent : ,/ (.1,I) L ,- 1 /l'Fi ; (.r)'/ ; définissent un ensemble d'hypothèses de la forme : 'H, = ,/, 'X: L .-' Dans H, f est linéaire en
() Le noyau Gaussien est positif alors que le noyau d'Epanechnikov ne l'est pas. 3.3. Comment choisir l'ensemble des hypothèses H ? Nous avons vu que l'on peut choisirfà partir d'une .i-l Une autret, ",ex..)era r'jfamille gén't ice :, Une autrefamine génératrice : "' z-/ [/./ tj autre manière de faire en utilisant les noyaux est de considérer les fonctions de la forme : f (.'> ri IC\ " //,A ('.r.- Une amélioration est possible en essayant d'ajuster l'in- fluence de chacun des ponts à travers un coefficient ai : f (;: n L A (.r..r ij On construit ensuite H à partir du noyau K A chaque noyau positif est associé un espace de Hilbert particulier dit « à noyau reproduisant » (EHNR). Nous allons voir que cette propriété de reproduction asso- ciée au noyau est fondamentale. Pour ce faire nous allons montrer comment se construit l'espace fonctionnel asso- cié au noyau. On commence par construire l'ensemble Ho des combinaisons linéaires finies associées au noyau. ' f f ; < :. G iiï ./ (u) -.A' (u.r) 7l; l (u ('J .,'y u = .,-1 f/Afu.',En notant I.=l. 1 nemre positive suivante : on a la forme bili- V/.</&Euro; o. (/.) , f., l f, ti, 7 : f i ) ? 'i-J - ! y ; -i définit un produit scalaire sur Ho qui est alors un espace pré-hilbertien. On dispose dans Ho par construction de la propriété de reproduction qui s'écrit : .,/, 'Ho.,u../* (ti) = Pour des raisons techniques, l'espace des hypothèses H s'obtient par fermeture de Ho au sens de la norme induite par son produit scalaire. L'espace ainsi obtenu est l'es- pace de Hilbert à noyau reproduisant (EHNR) associé au noyau K dans lequel la propriété de reproduction reste vérifiée. Cette propriété s'applique aussi ou noyau qui peut alors être vu comme un produit scalaire : K (1,1. V) l' (il. [\ " (V. Vu sous cet angle, le noyau représente une grande partie de la connaissance a priori. Nous allons maintenant met- tre en relation les deux approches proposées pour construire l'ensemble des hypothèses H. 3.4. L'astuce du noyau Le Théorème de Mercer stipule que, sous certaines conditions assez générales, si K est un noyau défini positif, il existe une famille (cp j)avec orthonormée telle que : LA (x.y) - c (x) (y) .j - J Toute fonction/E//s'écrit alors : (4) f (x) L .-/ 117i (,) j x n E (il (x.x, et a pour norme : 1 1 11,/'1 lh w w = a Ka où K est la matrice de Gram de terme général Ki Kb (xi, x/) Cette approche permet de calculer la norme d'une fonction de H à partir d'un vecteur de dimension n. C'est cette astuce qui va permettre une mise en oeuvre efficace des séparateurs à vaste marge. 4. Les séparateurs à vaste marge 4.1. Quel critère minimiser ? Nous avons vu qu'une bonne fonction de discrimina- tion doit allier fidélité aux données avec régularité de la solution. Pour une fonction de discrimination de la forme suivante : 1) i i, ( (,., + 1)1 ,./ D (.r) sl (/ ( dans l'approche SVM, ces deux critères sont formalisés de la manière suivante : > 1 -'i -, O i - 1. l illili F1 1 11 LC : : , 0 Fidclitr x nnii ' ; w7 1 1 R (''gularit.c1 REE NO 8 Septembre2006 Dossier DU TRAITEMENT NUMÉRIQUE À LA GESTION DES CONNAISSANCES DE NOUVELLES VOIES D'INVESTIGATION ? d- pare) Reste à trouver comment choisir les fonctions de référen- ces Oj (x). C'est une définition particulière de ces fonc- tions associées au noyau, plus les critères à optimiser qui définissent le problème des SVM. Plus précisément, avec les SVM on travaille avec un ensemble d'hypothèses définies à partir d'un noyau Kb de la manière suivante : j " .,. *t fl'- H Ja. c (x) l-,x) - J (X. xi- - Bien souvent on choisi w 1 et cpl est la fonction constante égale à un. On se contente d'ajouter un biais. n,,,p qui désigne le nombre de vecteurs supports dont nous allons voir l'importance. Formellement le SVM est la solution du problème de minimisation sous contraintes suivant : f ilil w 1 1 .,Ww, ('l a.vcc ('l tli,f iX z i-l '-,1 s > 0 : l/ 1, l (5) /'x xf x L li'hOI, (X) b ouOÙ 11-1 et C est un paramètre d'équilibrage donné à priori. C'est un des hyperparamè- tres (avec la largeur de bande du noyau) dont le réglage est crucial pour le bon fonctionnement de la méthode. 4.2. Minimisation sous contraintes (cas séparable) Le cas séparable est le cas le plus simple, lorsque la solution vérifie i - 0, i - 1, n. Dans ce cas, le problème se simplifie : lignes d'iso cout O Domaine admissible Figure 6. Cettefigiii-e illiistr ( le.fait que lorsqu'on iiiiniiiiise une erreur quadratique sous contraintes de valeurs absolues de type L', la solzrtion a tendance à être parcimonieuse. On vistrcrlise (,efait en suivant le cheiiiin de la.olittion lorsque le losange -epi-ésentaiit le doiiiaiiie adiiiissible voit son voliiiiie aiigi ; ieiiiei-. Poiii- l'exeiiiple pi-ésenté, l'ordonizée de Ici solittion est nulle. 0 ; i > 0 exemple support. 4.3. Formulation dans l'espace des exemples A partir du Lagrangien on peut tirer une partie des conditions de Kuhn et Tucker : - i) w.. 1- X, t,f : 1\, ! J' 1-1 A partir de la première condition sur w on en tire la consé quence surf : mm w avec w w ji,f' (x, '/= L C'est un problème de minimisation sous contrainte illustré par la figure 6. La nature des contraintes vaont faire que de nombreuses composantes de la solution vont avoir une valeur nulle. Pour résoudre ce problème on passe par la recherche du point selle du Lagrangien qui s'écrit : iiiiii £ (W 1). A) W. 1, 1 avec C (w. 1). 1\1 ') w " NL A, (p/J (x) - 1 Les Ici > 0 sont appelés les multiplicateurs de Lagrange et traduisent traduisent l'influence de l'exemple i dans la solution. Il s'interprète de la manière suivante : . ; , - 0 = pas d'influence, /fX) - ol,, i X)i 1 1 ( -1 ( n \r i y) » xZ- f =t \'-t/ ,i x A- 1 \ 1 1 . <. (x) (x,i 1 1 1, 1 1\)" -.i V ..x-x.] C'est l'astuce de représentation. Le calcul des 1 est donné par le problème Dual. Celui-ci s'obtient en éliminant w et b du Lagrangien, en concevant la seconde condition d'optimalité et en ajoutant que les multiplicateurs de Lagrange Ài doivent être positifs. On obtient alors le programme quadratique suivant : iiiiii.1) \-/1,\ + C, -/\ i av ('c l avec N L f i 1 ,\, ! Ji - () 0 < À i 1. l où H est la matrice de terme général Hii YiYjKb (XiXj) REE N 8 Septembre2006 et c un vecteur de 1. On a donc transformé le problème initial posé dans un espace fonctionnel très général en un programme quadratique qui ne dépend plus que de n variables et dont on sait que la solution va offrir un grand nombre de coefficients ; , - 0. Les méthodes de résolu- tions de ce problème vont tirer avantage de ce fait. 4.4. SVM dans le cas général Dans le cas général, il faut introduire les variables d'écart i. Le séparateur à vaste marge du problème de dis- crimination à deux classes associé à l'échantillon (x/,/),/ = 1, m avec le codage Yi E {-1, 1}, est la solution du pro- blème d'optimisation sous contrainte suivant pour f E H : ; HUlllitili ') ,/12 -t- ci Il' L x Vt'C et. y;l t (x ;!], (,/* (x, 0- /= 1, i ; 1. ii (6) où C est un scalaire permettant de régler la régularité de la fonction de décision, b un scalaire appelé le biais et les ei des variables d'écart. La solution de ce problème est aussi le point selle du Lagrangien : C(, '. (1 \ 1 -,,1' -', i , :/ x, 1, y,.,1 1. 1 1 1 1 1 (7) dont on tire une partie des conditions de Kuhn et Tucker : V.'U..A.! j.-\. ?') ,) C, , 1,. 4, \. il /. " \.) 1, : ` - , x, x x .. On en déduit que f (x iii AA'(x.x). grâce à cette relation que l'on peut éliminer f du Lagrangien pour aboutir à la formulation duale suivante : f - L\r fl).. + e-,\maxmax th avecet A Y=O ()/\/ (' 1, il où H est la matrice d'influence de terme général Hi} = K (Xi, Xj) et e [1 1... Il]'. La solution du problème SVM sera alors donnée par la résolution d'un problème d'optimisation quadratique en dimension m sous contraintes de boîtes. Il existe une formulation variationnelle du problème ne faisant pas apparaître explicitement les contraintes. Elle s'écrit comme une version pénalisée de la minimisa- tion du coût « charnière » : 1 ) II 1 1 - - (l c fi j) 1, (0 1 -- iii (,f (Xi') -f- 1 ») 1 1+ -1 12C avec p = 1 on retrouve les SVM telles que nous les avons introduites. Avec p " 2 on trouve une variante baptisée les SVM Z. 5. Les SVM Multi classes De nombreux problèmes pratiques de reconnaissances de formes comme la reconnaissance de caractères ne se posent pas comme des problèmes de discrimination à deux classes seulement mais comme des problèmes multi-classes. Le traitement du cas « multi-classe » a donné lieu à une abondante littérature dont il ressort qu'il n'y a pas de « meilleure méthode » et qu'il faudra choisir une stratégie en fonction du nombre de classes à traiter et de la taille de la base d'apprentissage. Les méthodes exis- tantes peuvent être présentées en trois catégories (on considère que l'on dispose de n exemples étiquetés par c > 2 classes). Les méthodes globales qui proposent une solution générale en résolvant un problème de grande taille (de l'ordre de c x n), les méthodes de type « un contre tous » qui proposent de construire la solution en résolvant de l'ordre de c problèmes chacun de taille n et enfin les méthodes de type « un contre un » qui utilisent discriminateurs binaires, chacun deles sorties de discriminateurs binaires, chacun de 1) 11 taille Dans l'approche globale il s'agit de minimiser l'ana- logue d'une marge multi-classe. Pour cela il faut définir c fonctions de discrimination fe, 1 - 1, c dans un ensemble //. Une manière de poser le problème (il existe là encore de nombreuses variantes) consiste à maximiser la marge suivante : mmlillll11 c'-.,Il \'cc in.ec c-i 1 If i-> + ( : 7 /1 1- 1 - [.f -- i - 1 c, 1 i,, i - > 0. ; 1. 1 i -- 1. (. (',. o./ i. - i.r. r Bien que l'estimateur associé à cette formulation ne soit pas consistant, il donne de bons résultats pratiques. Plusieurs méthodes de type « un contre tous » on été proposées. Outre l'approche la plus simple qui consiste à traiter de chaque classe contre tous les autres exemples, il existe d'autres approches plus élaborées. Certains propo- sent de rechercher itérativement les meilleures partitions binaires de l'ensemble d'apprentissage et créer un arbre de décision binaire (approche hiérarchique) ; d'autres pré- conisent l'utilisation d'un codage des classes inspiré des codes correcteurs d'erreur. L'idée est de partitionner arti- fciellement l'ensemble d'apprentissage en deux groupes de classes, plusieurs fois, de telle sorte que les sorties SVM entraînées sur chacun de ces groupes de classes per- mettent de construire une règle de décision multi-classe fiable. Notons qu'en utilisant cette stratégie et en parti- tionnant à l'extrême on peut retrouver le « un contre un ». L'approche « un contre un » a elle aussi donnée lieu à une abondante littérature. Le principe consiste à estimer REE N 8 Septembre2006 Dossier DU TRAITEMENT NUMÉRIQUE À LA GESTION DES CONNAISSANCES DE NOUVELLES VOIES D'INVESTIGATION ? (le " partie) discriminateurs binaires construits sur tous les couples de classes possibles. On parle aussi de discrimi- nation par paire. Les méthodes différent ensuite par le traitement qu'elles vont faire des sorties des classifieurs. La méthode la plus simple est celle du vote majoritaire. D'autres ont proposé de structurer les classifieurs binaires sous la forme d'un arbre de décision binaire (gra- phe dirigé acyclique). Il est aussi possible d'associer des probabilités à chacun des SVM binaires et de cherche une nouvelle combinaison optimale de ces probabilités esti- mées. Cette dernière technique semble donner de meil- leurs résultats. Aucune de ces méthodes n'est meilleure dans tous les cas. Le choix d'une méthode va donc dépendre de la situation et principalement de la taille du problème en ter- mes de nombre d'exemples et de nombre de classes. Si l'on ne dispose que de peu d'exemples et peu de clas- ses, l'approche globale est préférable. Si à l'inverse le problème est de grande taille (mais pas avec trop de clas- ses) on préférera l'approche de type « un contre un ». Enfin, s'il y a trop de classes, seule une approche de type « un contre tous » permettra de traiter le problème. Cette question suggère encore de nombreux travaux. 6. Mise en oeuvre D'une manière générale, pour trouver la SVM il faut résoudre un problème d'optimisation quadratique sous contrainte. L'ordonnancement des calculs est le suivant : d'abord on calcule la matrice K puis on résout le pro- blème ce qui nous donne les coefficients le et le b. Ensuite on calcule le vecteur a et on en déduit la fonction ! 6.1. Comment décomposer le problème des SVM Le principe général des méthodes de décomposition et/ou de contraintes actives repose sur l'observation que seuls les points non contraints dans la solution nécessitent le calcul de leurs coefficients : c'est la parcimonie. En effet, les autres ont pour coefficient une valeur fixe donnée par le problème : celle de la borne qui les contraint (0 et C dans le cas des SVM par exemple). Partant de ce constat, il suffirait de connaître la répartition des points dans trois groupes (contraints à 0, contraints à C et non contraints) pour avoir très rapidement (en une résolution de système linéaire sur les points non contraints) la solution du problème. On appellera par la suite les groupes I, Ic et I,,, respectivement pour les points contraints à 0, à C et non contraints. Ce constat a amené à différentes techniques de décomposition et diffé- rents algorithmes que nous allons détailler après avoir donné quelques outils communs à plusieurs méthodes. Les méthodes de décomposition, comme leur nom l'indique, utilisent des sous-ensembles de la base d'ap- prentissage à chaque étape, de manière à résoudre des problèmes de petite dimension.Les résultats de ces sous- problèmes sont ensuite combinés pour arriver à la solu- tion optimale globale. 6. 1. 1. Chunking La méthode connue sous le nom de chunking élimine les points dont les . valent 0 au fur et à mesure de l'avan- cement de l'algorithme. L'idée est de résoudre le pro- blème QP pour un sous ensemble de points. Le sous ensemble suivant est composé des vecteurs supports de la résolution précédente et des Mpoints sélectionnés dans le reste de la base comme étant ceux qui violent le plus les contraintes K.KT. Ainsi, de sous groupes en sous groupes, on résout le problème en entier. La limite de cette méthode est la taille de la solution finale : on ne peut pas nécessairement stocker l'intégralité de la matrice noyau en mémoire. 6.1.2. Décomposition La technique de décomposition est similaire au chun- king. Pour cette approche, on garde une taille de sous ensemble constante en laissant la possibilité de retirer du sous ensemble courant des points vecteurs supports. Ainsi on peut résoudre les problèmes quadratiques quelle que soit la taille réelle du problème. 6.2. Les solveurs SVM Sous ce nom on trouve de nombreux algorithmes qui permettent de résoudre efficacement le problème de programmation quadratique sous contraintes associées aux SVM. 6.2. 1. SMO Le cas extrême des approches de décomposition consiste à ne considérer que deux points à chaque étape. Cette méthode est connue sous le nom SMO (Sequential Minimal Optimisation). L'intérêt principal est que chaque sous-problème quadratique a une taille suffisamment res- treinte pour être résolu analytiqucment, évitant ainsi une résolution numérique coûteuse. SMO ne considère que les directions admissibles qui ne modifient que deux coefficients et par des valeurs opposées. La variante la plus répandue du SMO repose sur un critère du premier ordre pour sélectionner les pai- res (i, j) qui définissent les directions successives de recherche. 6.2.2. Méthodes de contraintes actives Une alternative à SMO utilise les contraintes actives. Pour les SVM, l'algorithme est baptisé Simple SVM (tou- REE N 8 Septembre2006 tefois il s'applique à tout problème posé sous la forme quadratique convexe sous contraintes de boîtes) et permet de trouver itérativement la répartition en trois groupes. Le principe des méthodes de contraintes actives est de répartir le plus efficacement possible les points dans les trois groupes lo, l et l,v. et de trouver les valeurs des'Ai, i E lw. par la résolution d'un système linéaire. Pour les SVM, l'algorithme est baptisé Simple SVM (toutefois il s'applique à tout problème posé sous la forme quadrati- que convexe sous contraintes de boîtes) et permet de trou- ver itérativement la répartition en trois groupes. A chaque étape, on résout pour le groupe Iw la mini- misation sans contrainte. Si une des valeurs de 1ainsi cal- culées viole les contraintes (c'est-à-dire que la solution trouvée ne se situe plus dans la boîte de contraintes) alors on projette 1 dans l'espace admissible (ce qui revient en pratique à changer de groupe le point indicé par la valeur qui viole les contraintes). reçoit un nouvel exemple issu de fa et met à jour le vec- teur de coefficients À en faisant deux étapes de SMO appelées process et reprocess. 6.2.3. Méthodes du point intérieur Les méthodes de point intérieur, sont le fruit de recherches pour résoudre la programmation linéaire en temps polynomial. Leur dérivation pour la programma- tion semi-définie positive et non linéaire a donné les algo- rithmes de type LOQO et OOQP. Ces méthodes, bien qu'à la pointe de la recherche en optimisation et très effi- caces, sont toutefois surpassées dans le cas considéré par les autres méthodes mieux adaptées. En effet, les métho- des de points intérieurs requièrent de partir de la base d'apprentissage complète et sont donc limitées dans le cas des grandes bases de données, indépendamment de leur efficacité algorithmique. La particularité des problè- mes rencontrés en apprentissage est la parcimonie, cette propriété est le point clef de la résolution des grands pro- blèmes quadratiques. Même en travaillant sur un sous ensemble de points de la base d'apprentissage comme c'est le cas pour les méthodes de décomposition, on gagne en temps et en performance à faire appel à des méthodes qui utilisent la parcimonie pour réduire leur complexité. 6.2.4. Méthodes en ligne et non optimale Regarder du côté des méthodes en ligne est intéressant pour les applications réalistes. En effet leur objectif est de combiner la performance des résultats des méthodes de type SVM à une utilisation à grande échelle et adaptative. LASVM est un algorithme qui combine les atouts de SMO et de Simple SVM pour parvenir à cet objectif. LASVM est un SVM en ligne qui augmente de manière incrémentale la fonction objectif duale. Il main- tient un vecteur des coefficients courants le et l'ensemble des indices des vecteurs supports correspondants I,,, (ici, Iv est l'union de I,, et de 1,,). Chaque itération de LASVM 6.3. Quelle méthode choisir ? Dans le pire des cas le problème à résoudre est de complexité non polynomiale, analogue à un Simplex. Dans la pratique les méthodes de type contraintes actives ou SMO donne une complexité de l'ordre de (0 (iil.5 » @ Il est avantageux d'utiliser les méthodes de contraintes actives lorsque le paramètre C sera grand et SMO lorsque C est petit. On trouvera des boites à outil Matlab aux adresses suivantes : 'asi.insa-rouen.fr/ " gloosIi/simpleSVM.html . asi.insa-rouen.frl - arakotom/toolboxl Pour traiter les très grands problèmes, il faudra utiliser les méthodes approchées comme LASVM qui ont déjà résolu des problèmes avec 8 106 exemples. 7. Conclusion Les machines à noyaux sont des approximateurs uni- versels dont on identifie les coefficients en résolvant un problème d'optimisation convexe. Ces coefficients repré- sentent l'influence de chacun des points dans la solution. Si l'on choisi bien ces critères, et c'est le cas de SVM, la solution est parcimonieuse : de nombreux coefficients sont nuls ce qui signifie que de nombreux points ne ser- vent à rien pour le problème traité. Grâce à cette propriété de parcimonie, les SVM sont très rapides (en général). Si l'on compare les SMV avec d'autres classifieurs universels on peut mettre en avant le fait que par rapport aux techniques de plus proches voisins, l'approche SVM est structurellement plus adaptée puisqu'elle va automati- quement adapter la métrique utilisée en fonction du voi- sinage. Elle est aussi bien plus rapide. Par rapport à la régression logistique elle est aussi plus rapide, car le pro- blème d'optimisation associé à la régression logistique est non linéaire et requiert l'utilisation de techniques ité- ratives du second ordre de type Newton ou quasi Newton. Par rapport aux réseaux de neurones, là encore c'est la nature du problème d'optimisation qui fait la différence. Pour les réseaux de neurones de type perceptron multicou- ches, le problème d'optimisation associé est non convexe ce qui entraîne de nombreuse complications. Enfin, dans de nombreuses applications pratiques que ce soit en traite- ment d'image, de texte, ou de reconnaissance des formes en général, il se trouve que les SVM sont, sinon la meil- leure, du moins panni les meilleures méthodes. En ce qui concerne la régression, il existe une version des SVM adaptée (appelée SVR). Mais il semble que ce soit les méthodes du type LAR avec noyaux qui soient les mieux adaptées. Cette méthode est analogue aux splines REE No 8 Septembre2006 Dossier DU TRAITEMENT NUMÉRIQUE À LA GESTION DES CONNAISSANCES DE NOUVELLES VOIES D'INVESTIGATION ? (le " partie) mais avec un terme de pénalisation des types LI qui per- met d'obtenir parcimonie et vitesse. Un autre intérêt des SVM et des machines à noyaux en général est leur très grande adaptabilité. En effet, on trouve des variantes à noyaux pour de nombreux problè- mes comme l'estimation de densité (le one class SVM), l'analyse en composantes principales (KPCA), l'analyse en composantes indépendantes, les moindres carrés par- tiels, l'analyse de Fisher et la minimisation de contraste en général. Pour en savoir plus Les principaux ouvrages sur les SVM sont les suivants : . V VAPNIK, " Statistical Learnin_q Theory','VViley, 1998. . R, HERBRICH, " Learning Kemet Classifiers,'The MIT Press, 2002. · B. SCHOELKOPF, A.J. SMOLA, " Leaming vith Kernels' ; The MIT Press, 2002. · J. SHAWE-TAYLOR, N. CRISTIANINI, " Kernel Methods for Pattern Ana/ys/s' : Cambridge Univ, Press, 2004. Sur la reconnaissance des formes statistiques : R.O. DUDA, PE. HART et D.G. STORK Pattern Classifica- tion (2nd ed.), John Wiley and Sons, 2001. . T HASTIE, R. TIBSHIRANI, J, FRIEDMAN, " The Elements of Statistical Learning. Data Mining, Inference and Predictions. ", Springer, 2001. Sur le réseau. ekerne ! -mach nes.org . jmlr.csali.mitedu/ ewvv\N.nips.cc/ · www.ph.tn.tudelft.nl/PRlnfo/ . in/libsvm/ aieon.bollou.com/projects/asvm/ . asiinsa-rouen.fr/- scanu L'auteur Stéphane Canu est Directeur du Laboratoire d'Informatique, du traitement de l'information et des systèmes (LlTIS) et Professeur à l'INSAde Rouen, attaché au département ASI qu'il a créé en 1999 Il est animateur du thème de recherche " apprentissage et contexte et travaille sur les méthodes d'apprentissage à noyaux depuis 1995. Il est aussi coordinateur du réseau d'excellence euro- péen PASCAL (attern Analysis, Statistical modelling and ComputAtional Learning). II a effectué un séjour d'un an en 2004 à l'ANU (Australlan National University, Canberra, Australie) dans le cadre d'un congé de recherche (dans l'équipe de Bob Williamson et Alex Smola) REE Nc 8 Septembre2006