SYNTHÈSE

Une nouvelle méthode d’apprentissage :

Les SVM. Séparateurs à vaste marge.
Antoine Cornuéjols

Maître de Conférence à L’I.I.E.

Et chercheur au LRI, Université de Paris-Sud, Orsay

Ces dernières années, il a soufflé comme un vent prentissage supervisé de concept ; supervisé car on
de révolution en apprentissage artificiel. Du côté des fournit à l'algorithme d'apprentissage l'étiquette asso-
applications, on s'est tourné vers la fouille de très ciée à chaque observation ; de concept car il s'agit d'ap-
grandes bases de données réelles, avec les défis atte- prendre à distinguer deux classes d'observations, ou
nants en termes de complexité en calcul et en espace, de encore une classe contre le reste.
prétraitement nécessaire des données, et de présentation
des résultats aux utilisateurs. Avec aussi de nouveaux x 0=1
besoins d'interactivité entre utilisateurs et outils d'ap-
prentissage. Mais le bouleversement n'a pas semblé
x1
moindre du côté conceptuel. Depuis 1995, nul n'est ¨«
+1 si - wi .x i  0
y  ©
w0
sensé ignorer les enseignements de Vapnik, et il est
ª«-1 sinon
i  0 ,d
x2 w1
devenu quasiment impossible de ne pas essayer les w2
SVMs ou le boosting sur un nouveau problème d'ap-
wd
prentissage. De quoi s'agit-il ?

Nous nous intéressons ici aux SVM. Étant donnée xd a  - w .x i i

leur extraordinaire fortune, qui dépasse les cercles de la i0 , d

communauté de l'apprentissage artificiel, cet article a

pour objectif de les présenter de manière simple, mais Figure 1 : Schéma d’un perceptron à un « neuro-
assez complète, pour un public plus large. Une ne ». Le neurone reçoit en entrée la description d’une
remarque préalable : SVM est l'acronyme de Support observation x, décrite par d attributs x1,…xd. Chacune
Vector Machines en anglais, méthode et terme inventés de ces composantes xi est pondérée par un poids synap-
par Vapnik principalement. Nous traduisons ici ce tique wi, (on ajoute aussi une entrée fictive x0 = 1 pour
terme par Séparateurs à Vaste Marge. Nous verrons permettre l’obtention de séparatrice ne passant pas par
pourquoi. l’origine dans l’espace des observations) et la sortie y
du neurone, –1 ou +1 est décidée par le signe de cette
1. Un retour aux origines : le perceptron somme pondérée.

Le perceptron, inventé par Rosenblatt, date du tout

début des années soixante. Le problème que traite cet Cet automate est en fait l'ancêtre des réseaux
algorithme est le suivant : supposons que nous ayons connexionnistes. Il ne comporte qu'un “ neurone ” rece-
une séquence d'observations x1, x2, …, xm, décrites par vant en entrée les valeurs des d attributs de description,
des mesures sur un ensemble prédéfini d'attributs (par opérant une combinaison linéaire de ces entrées grâce à
exemple : le poids, l'âge, la tension, …), chacune de ces une pondération par le vecteur des poids des «
observations étant affectée à une classe C prise dans synapses » et produisant en sortie un signal de valeur –1
{C1, C2} (par exemple : « risque cardio-vasculaire si la somme pondérée calculée est inférieure à un cer-
élevé », « risque cardio-vasculaire faible »). À partir de tain seuil q, et la valeur 1 sinon. On peut traduire cela
cet échantillon d'apprentissage, nous cherchons à trou- par l'équation (1) suivante :
ver les paramètres d'un automate tel que celui de la
figure 1 afin de permettre de prédire la classe de nou- ¨ *0 ‰ h( x )  1
wT xwO © (1)
velles observations à l'avenir. Il s'agit d'une tâche d'ap-
ª 0 ‰ h( x )  <1
BULLETIN DE L’AFIA
14 numéro 51 - juin 2002
 SYNTHÈSE

Cette équation montre immédiatement, que le per- séparatrice qui se comporte le mieux vis-à-vis des don-
ceptron est en fait un système de recherche d'une sépa- nées d'apprentissage, c'est-à-dire par exemple qui mini-
ratrice linéaire dans l'espace des attributs. Idéalement, mise le nombre d'exemples positifs ou négatifs mal
cette séparatrice doit séparer parfaitement les observa- classés, soit aussi celle qui permettra au mieux de clas-
tions affectées à une classe de celles affectées à l'autre ser les observations à venir, mais encore inconnues.
classe (on parlera fréquemment de la classe + et de la D'où l'algorithme d'apprentissage visant à minimiser la
classe – ainsi que d'exemples positifs et d'exemples mesure de coût sur les exemples d'apprentissage. On
négatifs). L'apprentissage revient ici à chercher un vec- appelle cette mesure un risque empirique car elle est
teur de poids w permettant la séparation des exemples mesurée empiriquement sur les données de l'échantillon
positifs et des exemples négatifs dans l'échantillon d'ap- d'apprentissage. Ce risque est la somme des coûts
prentissage. mesurés pour chaque exemple d'apprentissage et prend
donc la forme :
Pour ce faire, on définit d'abord une fonction de m
1
coût traduisant la plus ou moins bonne séparation des Remp (h) 
m
- l[h( x ), u ]
i 1
i i
exemples des deux classes, puis on utilise une méthode
de descente de gradient dans l'espace des poids w pour où xi est un des m exemples d’apprentissage, ui l’éti-
minimiser cette fonction de coût. Si la fonction de coût quette associée et l la fonction de perte mesurant la dis-
prend une forme quadratique, la descente de gradient tance entre la réponse produite h(xi) et la réponse dési-
est garantie de converger vers l'optimum global. En rée ui. (On notera ici une hypothèse fondamentale
gros, cela signifie qu'il existe une « meilleure » sépara- sous-tendant toute la théorie statistique de l’apprentis-
trice des deux classes d'exemples d'apprentissage, celle sage, à savoir que les exemples sont tirés indépendam-
qui « passe par le milieu ». Nous aurons l'occasion de ment les uns des autres, selon une même distribution).
revenir sur cette notion.
Mais ce qui nous intéresse in fine, c'est de minimi-
2. Qu'est-ce que l'apprentissage ? ser l'espérance des coûts sur les observations à venir, ce
que l'on appelle le risque réel, et qui prend la forme :
Une première question concerne l'espace des
concepts que l'on peut ainsi apprendre. Il est évidem-
ment très restreint dans le cas du perceptron puisque
Rréel  0 l[h( x ), u ]
X =U
i i dF( x, u)
seuls les concepts correspondant à des séparatrices
linéaires dans l’espace des attributs sont apprenables. où cette fois l’intégrale prend en compte la distribution
Plus généralement, il faudra toujours s'interroger sur inconnue F des exemples sur X x U , le produit carté-
l'adéquation de l'espace des hypothèses accessibles à sien de l’espace des observations X et de l’espace des
l'algorithme d'apprentissage à l'espace des concepts étiquettes U.
cibles potentiels pour l'application considérée. Mais
l'espace des hypothèses intervient aussi à un autre titre. La question qui doit alors nous préoccuper est de
savoir si lorsque nous choisissons une hypothèse mini-
En effet, le but poursuivi en apprentissage inductif misant le risque empirique, nous minimisons aussi le
est de parvenir à classer correctement les futures obser- risque réel, ce qui est notre vrai objectif. On appelle ce
vations grâce à la connaissance apprise (ici sous la critère de sélection d'hypothèse : principe de minimisa-
forme d’un automate) à propos d’un échantillon limité tion du risque empirique. Il est à la base de la majorité
de données. Une question centrale de l’apprentissage des techniques d'apprentissage inductif (à côté de prin-
est donc de savoir comment utiliser les données pour cipes inductifs liés à la décision bayésienne). Est-il jus-
avoir une bonne performance en généralisation, c’est-à- tifié ? C'est la question centrale des investigations de
dire sur les observations inconnues à venir. Vapnik durant une vingtaine d'années.

Remarquons que cette question, c'est à peine si elle La réponse est que le lien entre le risque empirique
nous a effleuré lorsque nous avons décrit l'algorithme mesuré et le risque réel espéré est fonction de la
du perceptron. Il a semblé absolument naturel que la « richesse » de l’espace des hypothèses accessibles à

BULLETIN DE L’AFIA
numéro 51 - juin 2002 15
 SYNTHÈSE

l’apprenant. Si l’espace est très contraint, c’est-à-dire De fait la théorie nous apporte même une informa-
que le choix d’une hypothèse est très limité, le risque tion supplémentaire. La taille de l’échantillon d’ap-
empirique mesuré sur la meilleure hypothèse est proba- prentissage suffisante pour avoir, avec une confiance
blement proche du risque réel. En revanche, si l’espace donnée, un risque réel proche de moins de ¡ du risque
d’hypothèses est riche et donc permet de trouver facile- empirique, croît en 1/¡  pour un espace d’hypothèses
ment une hypothèse de risque empirique faible, alors quelconque. Donc, si on veut diviser par deux l’écart
cela ne donne pas de garantie sur la performance en maximal probable ¡, il faut multiplier par quatre le
généralisation, c’est-à-dire le risque réel, de cette hypo- nombre d’exemples d’apprentissage. Cela caractérise la
thèse. Pour des raisons théoriques qui sortent du cadre vitesse de convergence de l’apprentissage. Mais si l’on
de cet article, on mesure la richesse d’un espace d’hy- est certain que l’espace d’hypothèses considéré contient
pothèses, ou encore sa capacité, par un nombre : la le concept cible, alors la vitesse de convergence est plus
dimension de Vapnik-Chervonenkis. En notant cette forte, en 1/¡ . On a donc doublement intérêt à savoir
dimension dVC, on peut exprimer le lien entre le risque cerner à l’avance le bon espace d’hypothèses.
empirique d’une hypothèse et son risque réel par une
équation du type : En résumant, nous devons donc résoudre le dilem-


P max Rréel (h) < Remp (h) * ¡
h DH
 G(d VC , m, ¡ )
me suivant : d’une part, nous avons intérêt à considérer
un espace d’hypothèses le plus riche possible puisque
cela augmente nos chances d’y trouver le concept cible,
Cette équation signifie que la probabilité que ce qui au passage améliore la convergence en appren-
l’écart entre le risque empirique mesuré et le risque réel tissage ; mais, d’autre part, nous avons intérêt aussi à
visé dépasse une certaine valeur e est bornée par G, une limiter autant que possible la richesse de l’espace d’hy-
fonction de la richesse de l’espace des hypothèses pothèses sous peine de distendre inconsidérément le
mesurée par dVC, de la taille m de l’échantillon d’ap- lien entre le risque empirique mesuré et le risque réel et
prentissage et de l’écart admis ¡. donc sous peine d’apprendre une hypothèse n’ayant
rien à voir avec le vrai concept cible.
On remarquera que cette majoration du risque réel
n’est obtenue qu’en probabilité, car tout dépend de la En dehors de bénéficier d’un délit d’initié nous
représentativité de l’échantillon d’apprentissage, et donnant des informations a priori sur le bon espace
c’est seulement en probabilité (avec une probabilité d’hypothèses, pouvons-nous avoir une méthode généra-
croissante avec la taille de l’échantillon) que cet échan- le permettant de résoudre le dilemme posé ?
tillon est représentatif de la distribution des exemples
dans la tâche d’apprentissage. 3. Les SVM (séparateurs à vastes marges)

Cette équation exprime d’une manière mathéma- Lorsqu’une observation est fournie en entrée à un
tique un dilemme bien connu : pour avoir une chance de perceptron, celui-ci produit une réponse qui indique
trouver une bonne hypothèse, il faut un espace d’hypo- seulement si cette observation est du côté de la classe
thèses riche (le risque empirique dans la somme ci-des- « + » (sortie 1) ou du côté de la classe « – » (sortie –1).
sus sera alors faible ou nul), malheureusement, plus Si maintenant nous considérons une variante du per-
l’espace d’hypothèses est riche, et moins il y a de ceptron dans laquelle la sortie non seulement fournit le
garantie que le risque réel soit proche du risque empi- signe (le côté dans lequel tombe l’observation par rap-
rique mesuré. L’une des difficultés de l’apprentissage port à l’hyperplan séparateur) mais fournit aussi une
est donc de savoir régler ce compromis. Naturellement, distance à l’hyperplan, pouvons-nous tirer parti de ce
l’idéal est de disposer d’informations a priori sur l’es- supplément d’information ?
pace des concepts cible. Dans ce cas, on peut choisir un
espace d’hypothèses adapté, c’est-à-dire dans lequel on Cette fois-ci : h(x) = wx + wo, et non plus : h(x) =
sait a priori qu’existe une hypothèse de risque empi- sign(wx + wo)
rique faible ou nul, et suffisamment limité pour qu’il y En supposant qu’il existe un hyperplan permettant
ait de bonnes garanties que le risque réel sera proche du de séparer les exemples positifs des exemples négatifs,
risque empirique. nous n’allons plus nous contenter d’en trouver un, mais

BULLETIN DE L’AFIA
16 numéro 51 - juin 2002
 SYNTHÈSE

nous allons en plus chercher parmi ceux-ci celui qui primale, implique le réglage de d+1 paramètres, d étant
passe « au milieu » des points des deux classes la dimension de l'espace des entrées X. Cela est pos-
d’exemples. Pourquoi ? Intuitivement, cela revient à sible avec des méthodes de programmation quadratique
chercher l’hyperplan le « plus sûr ». En effet, supposons pour des valeurs de d assez petites, mais devient inen-
qu’un exemple n’ait pas été décrit parfaitement, une visageable pour des valeurs de d dépassant quelques
petite variation ne modifiera pas sa classification si sa centaines. Heureusement, il existe une transformation
distance à l’hyperplan est grande. de ce problème dans une formulation duale que l'on
peut résoudre en pratique.
Formellement, cela revient à chercher un hyper-
plan dont la distance minimale aux exemples d’appren- D'après la théorie de l'optimisation, un problème
tissage est maximale (voir la figure 2). On appelle cette d'optimisation possède une forme duale dans le cas où
distance « marge » entre l’hyperplan et les exemples. la fonction objectif et les contraintes sont strictement
Comme on cherche à maximiser cette marge, on parle- convexes. Dans ce cas, la résolution de l'expression
ra de méthode des séparateurs à vaste marge. duale du problème est équivalente à la solution du pro-
blème original. Ces critères de convexité sont réalisés
Marge dans le problème défini ci-dessus.
maximale
w
h( x) > 1
Après transformation, le problème devient celui de
la recherche de paramètres a vérifiant le système
d’équations :
¨ ¨ m _ < 1 _ i_ j uiu j ( xi .x j )¬­
1
©- i  1 i -
Vecteurs m
w
de support «Max_ ª 2 i , j 1
®
h(x ) = +1 «
Hyperplan
optimal
_
© i * 0 , i  1,..., m (3)
h( x) < -1 « m
«- i , j 1_ i ui  0
h(x) = -1 h(x ) = 0
ª

Figure 2 : L’hyperplan optimal séparant les points L’hyperplan solution correspondant peut alors
de deux classes est celui qui passe « au milieu » de ces s’écrire :
m
classes, c’est-à-dire dont la distance aux points les plus
proches est maximale. Ces exemples les plus proches
h( x )  (w* .x ) w0*  - _ u .( x .x )
i 1
*
i i i j w0* (4)

qui suffisent à déterminer cet hyperplan sont appelés

vecteurs de support, ou encore exemples critiques. La où les _ i* sont solution de l’équation (3) et w0* est obte-
distance séparant l’hyperplan de ces points est appelée nue en utilisant n'importe quel exemple critique (xc,uc)
« marge ». dans l'équation :

_ i ui .(( xi .w* ) w0 ) < 1  0

Cet hyperplan optimal est défini par le vecteur de
poids w vérifiant l’équation :
À ce point, remarquons deux choses. D'abord, que
w, w0
!
Arg max min x < xi : x D½ d , (w T x wO )  0, i  1,..., m # l'hyperplan solution ne requiert que le calcul des pro-
duits scalaires xi .x entre des vecteurs de l'espa-
Pour cet hyperplan, la marge vaut 1/||w||, et donc la ce d'entrée X. Cette observation aura de profondes
recherche de l'hyperplan optimal revient à minimiser répercussions. Ensuite, la solution ne dépend plus de la
||w||, soit à résoudre le problème suivant qui porte sur dimension d de l'espace d'entrée, mais de la taille m de
les paramètres w et w0 : l'échantillon de données et même du nombre mc
d'exemples critiques qui est généralement bien inférieur
¨« 1 2
min imiser w
(2) à m. Les méthodes d'optimisation quadratique standard
© 2
«ªsous les contra int es u i (w T xi wO ) * 1, i  1,..., m suffisent donc pour de nombreux problèmes pratiques.

Cette écriture du problème, appelée formulation Tout cela est très bien, et l’on se croit autorisé à

BULLETIN DE L’AFIA
numéro 51 - juin 2002 17
 SYNTHÈSE

être fort satisfait, sauf que si l’esprit critique ne s’est où xk est la k-ième composante du vecteur x, et où nous
pas complètement endormi, on ne voit guère en quoi cet avons voulu indiquer que généralement, le vecteur
enrichissement de l’algorithme du perceptron a résolu image \(x) est de dimension supérieure à d, la dimen-
le problème posé par le dilemme entre l’utilité d’avoir sion de l’espace d’origine.
un espace d’hypothèses riche et la nécessité de limiter Espace des
cette richesse. représentations
internes
Espace
De fait les perceptrons ont un pouvoir expressif d'entr ées X
très limité qui semble devoir les confiner à des pro-
blèmes très particuliers, comme l’avaient fort bien
Espace
montré en leur temps Minsky et Papert dans leur célé- de sortie

\
brissime ouvrage Perceptrons, publié la première fois
en 1969. x h y
Redescription Séparation
Cependant, on n’a retenu depuis que le côté pessi- non linéaire linéaire
miste du livre de Minsky et Papert. Ils avaient en effet
souligné que si les entrées du perceptron résultaient
d’un prétraitement non linéaire sur l’espace des attri-
buts définissant les observations, la séparatrice trouvée
par le perceptron dans cet espace de redescription pou-
vait correspondre à une séparatrice non linéaire dans Figure 3 : Le passage par une redescription des
l’espace des attributs initiaux. Le seul problème, mais il données peut permettre une séparation linéaire des
était de taille, était de trouver les bonnes fonctions de exemples.
redescription. C’est de ce constat que se sont nourris les
efforts ultérieurs pour trouver une règle d’apprentissage Le problème d'optimisation se transcrit dans ce cas
pour des perceptrons multicouches non linéaires. Or par :
l’étude des SVM allait être l’occasion de reprendre les
¨ ¨ m _ < 1
©- i  1 i - _ i_ j uiu j \( xi ), \( x j ) ¬­
m
travaux sur la découverte de fonctions de redescription
«Max_ ª 2 i , j 1
®
permettant de passer d’un espace de description initial «
des données à un espace de redescription dans lequel il _
© i * 0 , i  1,..., m (5)
« m
est possible de trouver une séparatrice linéaire des don- «- i , j 1_ i ui  0
nées. ª

Une approche combinatoire permet en effet d’ima- où .,. dénote le produit scalaire.
giner une telle transformation sans connaissance a prio-
ri sur le problème. L'équation de l'hyperplan séparateur dans le nou-
vel espace devient :
En effet, plus la dimension de l'espace de descrip- m

tion est grande, plus la probabilité de pouvoir trouver h( x )  (w* .x ) w0*  - _ u . \( x ), \( x )

i 1
*
i i i j w0*
un hyperplan séparateur entre les exemples et les
où les coefficients _ i et w0 sont obtenus comme pré-
* *
contre-exemples est élevée. En transformant l'espace
d'entrée en un espace de redescription de très grande cédemment par résolution de l’équation (5).
dimension, éventuellement infinie, il devient donc pos-
sible d'envisager d'utiliser la méthode des SVM. Tout cela est très bien, sauf que l'objection immé-
diate du praticien concerne le produit scalaire
Notons \ une transformation non linéaire de l'es-
\( xi ), \( x j )
pace d'entrée X en un espace de redescription \(X) :
x  ( x1 ,..., xd )T a \( x )  (\1 ( x ),..., \ d ( x ),...)T qui devient rapidement impossible à calculer quand la
dimension de \(X) augmente (sans parler du cas de la

BULLETIN DE L’AFIA
18 numéro 51 - juin 2002
 SYNTHÈSE

dimension infinie), ceci d'autant plus que l'on utilisera Autre exemple : la fonction noyau K(x,y) = (x.y +
des transformations non linéaires des descripteurs d'en- c)n avec c * 0 correspond à un produit scalaire dans
trée. Pour donner une idée, supposons que l'on cherche l'espace des descripteurs correspondant à tous les pro-
à classer des images de 16 x 16 pixels (par exemple duits d'ordre ) n.
pour faire de la reconnaissance d'écriture manuscrite),
et que l'on suppose nécessaire pour cela de tenir comp- Les fonctions noyau décrites impliquent des cal-
te des corrélations entre 5 pixels quelconques au plus culs dans l'espace X, donc dans un espace de dimension
dans les images. L'espace de redescription, qui contient d. Ils sont par conséquent faciles à calculer. Mais com-
toutes les combinaisons de 5 pixels quelconques parmi ment déterminer quelle fonction noyau aisément calcu-
256, est alors de dimension de l'ordre de 1010. Calculer lable est associée à un espace de redescription \(X)
des produits scalaires dans un tel espace est imprati- dont on pense qu'il peut être intéressant pour trouver un
cable. séparateur linéaire des données ?

Il se trouve heureusement que l'on peut dans cer- En fait, la démarche est inverse : on cherche des
tains cas s'arranger pour littéralement court-circuiter le fonctions noyau dont on peut avoir la garantie a priori
passage par les calculs dans l'espace de redescription. qu'elles correspondent à un produit scalaire dans un cer-
En effet, il existe des fonctions bilinéaires symétriques tain espace qui agira comme un espace de redescrip-
positives K(x,y), appelées fonctions noyau, faciles à tion, mais qui restera virtuel, jamais explicité. Cela
calculer et dont on peut montrer qu'elles correspondent signifie que l'utilisateur devra opérer par essais et
à un produit scalaire dans un espace de grande dimen- erreurs : essayer des fonctions noyau associées à des
sion. Lorsqu'une telle correspondance est exploitable, produits scalaires dans des espaces de redescription et
le problème d'optimisation (5) est équivalent au problè- voir si elles permettent l'obtention de bonnes sépara-
me suivant : trices. Si cet aspect tâtonnant de la méthode peut sem-
bler peu satisfaisant, en revanche, le choix de la fonc-
¨ ¨ m _ < 1
©- i  1 i - _ i_ j uiu j K ( xi , x j )¬­
m
«Max_ ª 2 i , j 1
®
tion noyau devient le seul paramètre à régler,
« contrairement à d'autres techniques d'apprentissage.
©_ i * 0, i  1,..., m
« m (6)
«- i , j 1_ i ui  0 Toute fonction bilinéaire symétrique n’est pas
ª
nécessairement une fonction noyau dans la mesure où
dont la solution est l'hyperplan séparateur d'équation : elle peut ne pas correspondre à un produit scalaire dans
m
un espace. Il faut pour cela qu’une certaine condition
h( x )  - _ u .K ( x , x )
i 1
*
i i i j w0* mathématique appelée condition de Mercer soit véri-
fiée. En pratique, quelques familles de fonctions para-
où les coefficients _ i* et w0* sont obtenus comme pré- métrables sont connues pour satisfaire à ces conditions,
cédemment par résolution de l’équation (6). et l’utilisateur de SVM effectue des tests sur ces
familles de fonctions pour déterminer celle qui convient
Par exemple, il peut être montré que la fonction le mieux pour son application. Le tableau 1 donne les
noyau polynomiale : K(x,y) = (x.y)n réalise implicite- fonctions noyau les plus courantes.
ment un produit scalaire dans l'espace des descripteurs
correspondant à tous les produits d'exactement n
dimensions. Ainsi pour n=2 et x, y D ½ 2 , nous avons :

( x. y)2  ( x11 , x22 , 2 x1 x2 )( y11 , y22 , 2 y1 y2 )T  \( x ), \( y)

qui correspond au changement de description par la

fonction : \( x )  ( x1 , x2 , 2 x1 x2 ), et qui nous fait
1 2

donc passer par une transformation non linéaire dans un

espace de dimension trois, au lieu de deux initialement.

BULLETIN DE L’AFIA
numéro 51 - juin 2002 19
 SYNTHÈSE

La solution s’exprime sous la forme :

mc
h( x )  - _ u .K ( x , x )
i 1
*
i i i j w0*

Fonction noyau Forme fonctionnelle Commentaire

- polynomiale K ( x, y)  ( x. y + c) n
La puissance n est déterminée a
priori par l’utilisateur.
- fonctions à base radiale £ x < y 2¥ L’écart type m2, commun à tous les
K( x, y)  exp² <
2m 2 ´¦
noyaux, est spécifié a priori par
¤ l’utilisateur.
- fonctions sigmoïdes K ( x, y)  tanh( a ( x. y) - b) Le théorème de Mercer n’est vérifié
que pour certaines valeurs de a et b.

Tableau 1 : Les fonctions noyau les plus courantes avec leurs paramètres.

Il est clair que les fonctions noyau encodent des - Le type de covariance dans l'espace des entrées stipu-
connaissances essentielles sur le problème d'induction lant comment des points en divers endroits de l'espa-
étudié, en particulier : ce sont liés les uns aux autres. On peut ainsi chercher
- Une mesure de similarité sur les données. des fonctions noyau invariantes pour certaines trans-
- La forme fonctionnelle des fonctions de décisions formations de l'espace d'entrée, comme par exemple
possibles. la rotation.
- Le type de contrôle réalisé sur les hypothèses : par Il faut donc les choisir avec soin en essayant de
exemple les fonctions noyau Gaussiennes pénalisent traduire grâce à elles le maximum de connaissances
les dérivées de tous les ordres et favorisent donc les préalables dont on dispose sur le problème et sur les
solutions « régulières ». données.

Figure 4 : Dans la fenêtre de gauche, quarante-sept exemples d’apprentissage (vingt-deux de la classe « + » et

25 de la classe « – ») ont été disposés par l’utilisateur. La fenêtre de droite montre la frontière de décision obtenue
avec un SVM de noyau polynomial de degré 5 avec une constante C = 10000 (pénalisant beaucoup les exemples mal
classés). La frontière obtenue s’appuie sur sept exemples critiques, dont quatre dans la classe « + » et trois dans la
classe « – ».

BULLETIN DE L’AFIA
20 numéro 51 - juin 2002
 SYNTHÈSE

Figure 5 : Pour les mêmes exemples d’apprentissage que ceux de la figure 4, on voit l’effet de différents choix
de la fonction noyau (polynomiale de degré 2, 5 et 8 en haut, et Gaussienne d’écart-type 2, 5, et 10 en bas). Le nombre
d’exemples critiques de chaque classe est indiqué entre parenthèses en-dessous de chaque imagette.

4. La mise en œuvre des SVM utilisant l’échantillon de données pour régler les para-
mètres du système, on risque d’identifier des para-
La réalisation d’un programme d’apprentissage mètres suradaptés à cet échantillon de données. C’est
par SVM se ramène essentiellement à résoudre un pro- pourquoi on utilise un troisième jeu de données,
blème d’optimisation impliquant un système de résolu- n’ayant pas servi au processus d’optimisation du systè-
tion de programmation quadratique dans un espace de me, pour évaluer la performance vraie du système.
dimension conséquente. C’est pourquoi ces pro-
grammes utilisent des méthodes spéciales pour y parve- Si la mise en œuvre d’un algorithme de SVM est
nir de manière efficace et il n’est pas recommandé de en général peu coûteuse en temps, il faut cependant
chercher à réaliser soi-même un tel programme. Le lec- compter que la recherche des meilleurs paramètres peut
teur pourra trouver un ensemble d’outils disponibles requérir des phases de test assez longues.
gratuitement sur le site : http://www.kernel-
machines.org/ . Sur ce thème, nous finirons en notant que, pour des
raisons de simplification de cette présentation, nous
L’utilisation de ces programmes revient surtout à avons laissé de côté un détail d’importance. En effet, il
sélectionner une bonne famille de fonctions noyau et à arrive que, même en utilisant un espace de redescrip-
régler les paramètres de ces fonctions (par exemple tion, l’on ne puisse trouver une séparatrice linéaire
l’exposant pour les fonctions noyau polynomiale, ou séparant parfaitement les exemples d’une classe de
bien l’écart type pour les fonctions à base radiale). Ces ceux de l’autre. Cela peut être dû par exemple à des
choix sont le plus souvent faits par une technique de descriptions des données imparfaites ou bruitées. Dans
validation croisée, dans laquelle on estime la perfor- ce cas, on se contentera de trouver une séparatrice opti-
mance du système en la mesurant empiriquement sur male, ne laissant que peu d’exemples mal classés de
des exemples n’ayant pas été utilisés en cours d’ap- chaque côté de la séparatrice choisie. Cette notion
prentissage. L’idée est de chercher les paramètres per- introduit à son tour un nouveau paramètre d’optimisa-
mettant d’obtenir la performance maximale. tion, sous la forme d’une constante C, qu’il faut donc
Cependant, en opérant de cette manière, c’est-à-dire en aussi optimiser.

BULLETIN DE L’AFIA
numéro 51 - juin 2002 21
 SYNTHÈSE

5. Mais finalement, pourquoi ça marche ? schéma, la richesse de l’espace des hypothèses, au lieu
d’être déterminée a priori avant de commencer l’ap-
Nous avons démarré cet article en discutant la légi- prentissage, comme c’est le cas lorsque l’on choisit par
timité du principe inductif reposant sur la minimisation exemple a priori une architecture dans un réseau
du risque empirique, mesuré sur les données d’appren- connexionniste, est ici fixée a posteriori, à partir des
tissage, pour sélectionner la meilleure hypothèse, celle données d’apprentissage. La philosophie, et plus que
qui se comportera bien sur les observations à venir. ça, est alors différente. L’analyse théorique initiale de
L’analyse théorique a en effet montré que le lien entre Vapnik et des autres théoriciens était destinée à borner
le risque empirique et le risque réel était fonction de la la différence entre risque empirique et risque réel quel-
richesse de l’espace d’hypothèse. Si celui-ci est trop le que soit la distribution des données. C’était donc une
riche, la corrélation entre le risque mesuré et le risque analyse dans le pire cas. L’analyse des SVM semble
réel est hasardeuse, nullement garantie. Il faut donc requérir une nouvelle approche dans laquelle on s’inté-
régler au mieux un compromis entre avoir un espace resse aux données observées et où l’on cherche à
trop pauvre pour contenir des hypothèses intéressantes exploiter au mieux la chance que l’on a eue de tomber
et avoir un espace trop riche, pour lequel plus aucune sur une distribution particulière des données telle que le
garantie n’existe sur la performance à venir de l’hypo- révèle l’échantillon d’apprentissage. Si cette distribu-
thèse choisie sur la base d’un échantillon limité de don- tion est favorable, alors la corrélation entre risque empi-
nées. Or qu’avons-nous fait avec les SVM ? rique et risque réel peut être beaucoup plus étroite que
ne le prédit l’analyse dans le pire cas. Le manque de
Il semble qu’en voulant échapper aux limitations place nous interdit de rentrer davantage dans les détails
des perceptrons classiques, et en passant par l’utilisa- ici.
tion d’un espace de redescription, nous soyons passés
d’un extrême à l’autre. Certes le stratagème du passage Si des cadres théoriques se mettent en place pour
par un espace de redescription des données nous aurait rendre compte du succès des méthodes à vaste marge,
permis d'identifier aisément une fonction séparatrice notons que le débat est encore largement ouvert et offre
des données, quelles qu’elles soient, mais nous aurions des opportunités de recherche pour ceux que l’analyse
en même temps perdu toute assurance qu'elle se révèle théorique de nature statistique attire.
performante sur les futures observations. C’est ici que
nous allons remettre en lumière la notion de marge évo- 6. Conclusion
quée plus haut, et qui se trouve au centre des réflexions
en apprentissage artificiel en ce moment. La méthode des SVM est aisée d’emploi. Les logi-
ciels de SVM sont disponibles sur Internet et les expé-
Il faut commencer par remarquer que la marge riences sont faciles à réaliser. On obtient souvent en les
autour d’une séparatrice linéaire est associée à la utilisant des résultats comparables à ceux obtenus avec
richesse de l’espace des hypothèses. En effet, plus la d’autres techniques et les paramètres à régler sont
marge est grande, et plus il est difficile de faire passer moins nombreux. Cette méthode est applicable pour
une séparatrice linéaire avec cette marge entre les don- des tâches de classification à deux classes, mais il exis-
nées des deux classes (revoir la figure 2). Intuitivement, te des extensions pour la classification multiclasse. Plus
en cherchant une séparatrice de marge maximale entre encore, bien que nous n’en ayons pas parlé ici pour des
les données, nous nous obligeons de fait à considérer un raisons d’espace limité, les SVM peuvent également
espace d’hypothèses plus limité et cela nous permet de s’utiliser pour des tâches de régression, c’est-à-dire de
maintenir malgré tout un lien entre le risque empirique prédiction d’une variable continue en fonction d’autres
et le risque réel. Cela correspond à la justification ini- variables, comme c’est le cas par exemple dans de la
tialement avancée par Vapnik pour les SVM. Selon lui, prédiction de consommation électrique en fonction de
cette méthode permettait de régler directement le com- la période de l’année, de la température, etc. Le champ
promis entre adéquation aux données et limitation de la d’application des SVM est donc large. Si ils ne sont pas
richesse de l’espace des hypothèses. la panacée peut être un peu vite annoncée, ils représen-
tent une classe de méthodes très séduisantes. L’un des
Cependant, il a été souligné depuis que, dans ce axes de recherche actuel est de parvenir à coder des

BULLETIN DE L’AFIA
22 numéro 51 - juin 2002
 SYNTHÈSE

connaissances a priori dans ces systèmes, c’est-à-dire à Knowledge Discovery 2(2): 121-167. (Un article
mieux comprendre le rôle des fonctions noyau. d’introduction excellent malgré sa date de parution
déjà ancienne).
Par ailleurs, du point de vue conceptuel, la notion - Cornuéjols, A. and L. Miclet (2002). L'apprentissage
de marge a renouvelé la vision des méthodes inductives artificiel. Méthodes et concepts, Eyrolles. (Ouvrage
en général, et a stimulé tout un courant de recherche général sur l’apprentissage artificiel. L’article présent
dont on peut espérer qu’il débouchera sur de nouvelles est une version simplifiée du chapitre 9 de cet ouvra-
classes de méthodes, encore mieux comprises et encore ge.)
plus adaptables à nos problèmes. - Cristianini, N. and J. Shawe-Taylor (2000). Support
Vector Machines and other kernel-based methods,
Cambridge University Press. (Un bon ouvrage d’in-
Bibliographie (très partielle): troduction aux SVM.)
- Anthony, M. and P. Bartlett (1999). Neural network - Schölkopf, B. and A. Smola (2002). Learning with
learning : theoretical foundations, Cambridge kernels. Support vector machines, regularization,
University Press. (Pour ceux qui veulent aller voir de optimization, and beyond, MIT Press. (L’ouvrage le
plus près les fondements théoriques des SVM.) plus complet et le plus récent sur la question des
- Burges, C. (1998). « A tutorial on support vector SVM, et plus largement des méthodes à vaste marge).
machines for pattern recognition. » Data Mining and

BULLETIN DE L’AFIA
numéro 51 - juin 2002 23