Introduction aux Support Vector Machines (SVM)
Olivier Bousquet
Centre de Mathematiques Appliquees
Ecole Polytechnique, Palaiseau
Orsay, 15 Novembre 2001
2
But de lexpose
Presenter les SVM
Encourager leur utilisation
Encourager leur etude
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
3
Plan
Quel est le contexte ?
Quest-ce que cest ?
Comment cela marche-t-il ?
Pourquoi est-ce utile ?
Pourquoi est-ce que cela marche ?
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
4
Contexte
Probleme dapprentissage
On sinteresse a un phenomene f (eventuellement non-deterministe) qui,
a partir dun certain jeu dentrees x,
produit une sortie y = f (x).
Le but est de retrouver f a partir de la seule observation dun certain nombre
de couples entree-sortie {(xi, yi) : i = 1, . . . , n}
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
5
Contexte
Formalisation
On considere un couple (X, Y ) de variables aleatoires a valeurs dans X Y.
Seul le cas Y = {1, 1} (classification) nous interesse ici (on peut facilement
etendre au cas |Y| = m > 2 et au cas Y = R).
La distribution jointe de (X, Y ) est inconnue.
Donnees: on observe un echantillon S = {(X1, Y1), . . . , (Xn, Yn)} de n
copies independantes de (X, Y ).
But: construire une fonction h : X Y telle que P (h(X) 6= Y ) soit
minimale.
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
6
Exemples de problemes dapprentissage
Reconnaissance de formes
Reconnaissance de chiffres manuscrits (apres segmentation: codes postaux)
Reconnaissance de visages
Entrees: image bidimensionnelle en couleur ou en niveaux de gris
Sortie: classe (chiffre, personne)
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
7
Exemples de problemes dapprentissage
Categorisation de textes
Classification de-mails
Classification de pages web
Entrees: document (texte ou html)
Sortie: categorie (theme, spam/non-spam)
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
8
Exemples de problemes dapprentissage
Diagnostic medical
Evaluation des risques de cancer
Detection darythmie cardiaque
Entrees: etat du patient (sexe, age, bilan sanguin, genome...)
Sortie: classe (a risque ou non)
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
9
Illustration
Trouver une frontiere de decision qui separe lespace en deux regions (pas
forcement connexes).
Probleme doptimisation
Critere: erreur constatee sur les donnees (Erreur empirique)
Espace de recherche: ensemble parametre de fonctions par exemple
Probleme mal pose (solution non unique)
Garanties ?
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
10
Illustration
Sur et sous-apprentissage
Si les donnees sont generees par un modele quadratique
Le modele lineaire est en situation de sous-apprentissage
Le modele de haut degre est en situation de sur-apprentissage (apprentissage
par coeur)
Un compromis est a trouver entre adequation aux donnees et complexite
pour pouvoir generaliser.
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
11
Plan
Quel est le contexte ?
Quest-ce que cest ?
Comment cela marche-t-il ?
Pourquoi est-ce utile ?
Pourquoi est-ce que cela marche ?
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
12
Quest-ce que cest ?
Les Support Vector Machines sont une classe dalgorithmes dapprentissage.
Principe general
Construction dun classifieur a valeurs reelles
Decoupage du probleme en deux sous-problemes
1. Transformation non-lineaire des entrees
2. Choix dune separation lineaire optimale
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
13
Classification a valeurs relles
Plutot que de construire directement h : X {1, 1}, on construit
f : X R.
La classe est donnee par le signe de f
h = sgn(f ) .
Lerreur se calcule avec
P (h(X) 6= Y ) = P (Y f (X) 0) .
Donne une certaine idee de la confiance dans la classification. Idealement,
|Y f (X)| est proportionnel a P (Y |X).
Y f (X) est la marge de f en (X, Y ).
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
14
Transformation des entrees
X est un espace quelconque dobjets.
On transforme les entrees en vecteurs dans un espace F (feature space).
:X F.
F nest pas necessairement de dimension finie mais dispose dun produit
scalaire (espace de Hilbert)
La non-linearite est traitee dans cette transformation, on peut donc choisir
une separation lineaire.
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
15
Choix dune separation
Hyperplan optimal
Choix de la separation: hyperplan qui classifie correctement les donnees (lorsque
cest possible) et qui se trouve le plus loin possible de tous les exemples.
Optimal
Valide
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
16
Maximisation de la marge
Definition geometrique
Marge = distance du point le plus proche a lhyperplan
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
17
Plan
Quel est le contexte ?
Quest-ce que cest ?
Comment cela marche-t-il ?
Pourquoi est-ce utile ?
Pourquoi est-ce que cela marche ?
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
18
Maximisation de la marge
Proprietes
Modele lineaire
f (x) = w x + b
Definition de lhyperplan (frontiere de decision)
wx+b=0
La distance dun point au plan est donnee par
|w x + b|
d(x) =
kwk
Maximiser la marge revient a minimiser kwk sous contraintes
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
19
Implementation
Probleme primal
Un point (xi, y) est bien classe si et seulement si
yf (x) > 0
Comme le couple (w, b) est defini a un coefficient multiplicatif pres, on simpose
yf (x) 1
Rappelons que
|f (x)|
d(x) =
kwk
On obtient le probleme de minimisation sous contraintes
min 21 kwk2
i, yi([Link] + b) 1
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
20
Implementation
Probleme dual
On passe au probleme dual en introduisant des multiplicateurs de Lagrange
pour chaque contrainte.
Ici on a une contrainte par exemple dapprentissage
Pn 1
P
max i=1 i 2 i,j ij yiyj xi xj
i, 0
Pn i
i=1 i yi = 0
Probleme de programmation quadratique de dimension n (nombre dexemples).
Matrice hessienne: (xi xj )i,j .
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
21
Implementation
Proprietes
n
X
w = iyixi
i=1
Seuls les i correspondant aux points les plus proches sont non-nuls. On parle
de vecteurs de support.
Fonction de decision
Xn
f (x) = iyixi x + b
i=1
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
22
Cas non-separable
Traitement des erreurs
On introduit des variables ressort pour assouplir les contraintes.
1 2
Pn
min 2 kwk + C i=1 i
i, yi([Link] + b) 1 i
On penalise par le depassement de la contrainte.
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
23
Cas non-separable
Probleme dual
Le probleme dual a la meme forme que dans le cas separable:
Pn 1
P
max i=1 i 2 i,j ij yiyj xi xj
i, 0 i C
Pn
i=1 i yi = 0
La seule difference est la borne superieure sur les .
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
24
Fonction noyau
Espace intermediaire
Au lieu de chercher un hyperplan dan lespace des entrees, on passe dabord dans
un espace de representation intermediaire (feature space) de grande dimension.
: Rd F
x 7 (x)
On doit donc resoudre
Pn 1
P
max i=1 i 2 i,j ij yiyj (xi) (xj )
i, 0 i C
Pn
i=1 i yi = 0
et la solution a la forme
n
X
f (x) = iyi(xi) (x) + b
i=1
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
25
Fonction noyau
Proprietes
Le probleme et sa solution ne dependent que des produits scalaires (x)(x0).
Plutot que de choisir la transformation non-lineaire : X F, on choisit
une fonction k : X X R appelee fonction noyau.
Elle represente un produit scalaire dans lespace de representation intermediaire.
Elle traduit donc la repartition des exemples dans cet espace.
k(x, x0) = (x) (x0)
Lorsque k est bien choisie, on na pas besoin de calculer la representation
des exemples dans cet espace pour calculer cette fonction.
Permet dutiliser des representations non-vectorielles
Le noyau materialise une notion de proximite adaptee au probleme.
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
26
Fonction noyau
Exemple
Soit x = (x1, x2) et (x) = (x21, 2x1x2, x22). Dans lespace intermediaire, le
produit scalaire donne
2 2
(x) (x0) = x21x01 + 2x1x2x01x02 + x22x02
= (x1x01 + x2x02)2
= (x x0)2
On peut donc calculer (x) (x0) sans calculer .
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
27
Fonction noyau
Exemple
Le passage dans F = R3 rend possible la separation lineaire des donnees.
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
28
Fonction noyau
Conditions de Mercer
Une fonction k(., .) symetrique est un noyau si pour tous les xi possibles,
(k(xi, xj ))i,j est une matrice definie positive.
Dans ce cas, il existe un espace F et une fonction tels que
k(x, x0) = (x) (x0)
Difficile a verifier
Ne donne pas dindication pour la construction de noyaux
Ne permet pas de savoir comment est
En pratique, on combine des noyaux simples pour en obtenir de plus com-
plexes.
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
29
Fonction noyau
Exemples de noyaux
Lineaire
k(x, x0) = x x0
Polynomial
k(x, x0) = (x x0)d ou (c + x x0)d
Gaussien
0 2 /
k(x, x0) = ekxx k
Laplacien
0
k(x, x0) = ekxx k1/
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
30
Plan
Quel est le contexte ?
Quest-ce que cest ?
Comment cela marche-t-il ?
Pourquoi est-ce utile ?
Pourquoi est-ce que cela marche ?
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
31
Pourquoi est-ce utile ?
Flexibilite des noyaux
Noyau mesure de similitude
Temps de calcul raisonnable
Trouver un hyperplan qui minimise lerreur est NP-complet.
Vecteurs de support
Representation parcimonieuse et eventuellement interpretable.
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
32
Noyaux
Exemples
Si les donnees sont sous forme vectorielle, on peut utiliser un noyau classique.
On peut aussi contruire un noyau specifique qui travaille plus directement sur
la representation initiale (structure).
Images 2D: choix dune resolution et dune discretisation des couleurs
vecteur des valeurs des pixels
coefficients dune transformee en ondelettes
histogramme des couleurs
Textes: choix dun dictionnaire (suppression des mots simples)
Sac de mots: vecteur des occurences
Autres attributs (liens, position des mots...)
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
33
Noyaux
Exemples
Sequences dADN
Fenetres de taille fixe (sous-sequence) et representation binaire (un bit par
valeur possible)
... A T A G C A ...
1 0 1 0 0 1
0 1 0 0 0 0 (1,0,0,0,0,1,0,0,1,0,0,0,0,0,1,0,0,0,0,1,1,0,0,0)
0 0 0 1 0 0
0 0 0 0 1 0
Coefficients dun modele probabiliste generateur
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
34
Temps de calcul
Complexite
d = dimension des entrees
n = nombre dexemples dapprentissage
dn2 Complexite dn3
Taille de la matrice hessienne: n2
Methodes de decomposition
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
35
Plan
Quel est le contexte ?
Quest-ce que cest ?
Comment cela marche-t-il ?
Pourquoi est-ce utile ?
Pourquoi est-ce que cela marche ?
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
36
Pourquoi cela marche-t-il ?
Elements de reponse
Plusieurs reponses possibles
Maximisation de la marge
Lensemble des hyperplans de marge donnee M a une VC dimension bornee
par
R2
,
M2
si les X sont dans une boule de rayon R.
Parcimonie de la representation
Lerreur leave-one-out est bornee en moyenne par le nombre de vecteurs
support.
En pratique cela donne des bornes relativement predictives mais tres pes-
simistes.
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
37
Questions Ouvertes
Regularisation
On peut voir lalgorithme SVM comme la minimisation dune fonctionnelle
regularisee:
n
X
min c(f, Xi, Yi) + kf k2H .
f
i=1
1. Choix du parametre de regularisation
2. Penalisation lineaire vs quadratique
3. Lien entre parcimonie et choix de la penalisation
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
38
Questions Ouvertes
Noyaux
1. Choix automatique des parametres
2. Construction de noyaux exotiques (sur des objets structures)
3. Approche non-parametrique pour la construction de noyau
4. Classes etendues de noyaux (conditionnellement positifs)
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
39
Questions Ouvertes
Generalisation
1. Notion de complexite (covering numbers, fat-shattering dimension)
2. Structure du feature space
3. Structure de lespace des fonctions possibles (qui depend des donnees)
4. Proprietes de la matrice de Gram
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
40
Questions Ouvertes
Marge - Parcimonie
1. Bornes de type perceptron (Novikoff)
2. Lien avec la fat-shattering dimension
3. Role de la classification a valeurs reelles
4. Lien avec la marge du boosting
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
41
Conclusion
1. La technique SVM est dune grande flexibilite grace aux noyaux
2. La maximisation de la marge semble etre une bonne heurisitque
3. De nombreuses questions restent ouvertes
Applications: construction de noyaux, adaptation des parametres, imple-
mentation efficace, incorporation dinvariances...
Theorie: comprendre la generalisation, la complexite, la marge, la parci-
monie...
Essayez les SVM !
Etudiez les SVM !
Venez au seminaire/groupe de travail !
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
42
Pour en savoir plus
Page du seminaire/GT:
[Link]
References bibliographiques
Un lien utile:
[Link]
Programmes, articles en ligne, tutoriels...
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
