Marin FERECATU & Michel Crucianu ([email protected])
http ://cedric.cnam.fr/vertigo/Cours/ml2/
Département Informatique Conservatoire National des Arts & Métiers, Paris, France
2 Objectifs et contenu de l’enseignement
3 Séparateurs à vaste marge
4 SVM linéaire (cas séparable)
5 Données non séparables linéairement
“La raison d’être des statistiques, c’est de vous donner raison.” - Abe Burrows
Machines à vecteurs de support (Support Vector Machines SVM) et méthodes à noyau :
Separateurs à vaste marge
Cas linéairement séparable
Cas non-séparable linéairement
Astuce à noyau
SVM non linéaire
SVM et méthodes à noyau :
SVM pour la régression
One-class SVM
Principe des méthodes à noyaux
Kernel PCA, Kernel CCA
SVM à noyaux multiples (Multiple Kernel Learning - MKL)
Noyaux pour des données structurés
Applications
2 Objectifs et contenu de l’enseignement
3 Séparateurs à vaste marge
4 SVM linéaire (cas séparable)
5 Données non séparables linéairement
Linéaire (haut) vs. non-linéaire (bas).
Séparateurs linéaires.
Marge des séparateurs linéaires.
Marge des séparateurs linéaires.
Publicité
Marge des séparateurs linéaires.
Marge : Distance entre le plus proche exemple d’apprentissage et la surface de séparation. Bas d’apprentissage : { ( xi, yi ) , i = 1 , . . ., n}, xi ∈ R , yi ∈{− 1 , 1 }
Fonction de décision : f ( x ) = w x + b = 0
f ( x ) = 0 : hyperplan (surface) de séparation
f ( x ) > 0 : classe 1 ( yi = 1)
f ( x ) < 0 : classe 2 ( yi = − 1)
Fonction de décision : f ( x ) = w x + b = 0 Paramètres :
w est la normale à l’hyperplan,
b est le décalage par rapport à l’origine
Les paramètres w et b ne sont pas uniques. kw et kb donnent la même surface de séparation : kw x + kb = k ( w x + b ) = 0
Quelle fonction de décision choisir : f ( x ) = w x + b = 0
Solution : celle qui maximise la marge.
Si xs est un support vecteur, et H = {x|w x + b = 0 } alors la marge est :
[+] [ b][|] marge = 2 d ( x, H ) = 2 [|]
w || ||
On impose la condition de normalisation |w xs + b = 1 | pour les vecteurs de support xs :
2 marge = w || ||
2 Objectifs et contenu de l’enseignement
3 Séparateurs à vaste marge
4 SVM linéaire (cas séparable)
5 Données non séparables linéairement
Optimisation de la marge : optimisation sous contraintes (problème primal) 1 [2]
1 2 [||] [||] [2]
min w,b
t.q. yi ( w · xi + b ) ≥ 1 , i = 1 , . . ., n
La résolution de ce problème peut se faire directement (méthodes stochastique de type Gauss-Seidel, algorithmes de point intérieur, de type Newton ou de type gradient conjugué) Il est toutefois mieux de passer à la formation duale de ce problème :
Le dual est un problème quadratique de taille n (égal au nombre d’observations)
Pour ce type de problèmes (optimisation quadratique) il existe des algorithmes bien étudiés et très performants
La formulation duale fait apparaître la matrice de Gram XX ce qui permet de gérer le cas non linéaire à travers des noyaux.
Publicité
On introduit les multiplicateurs α de Lagrange :
L ( w, b, α ) = [1]
2 [||] [||] [2][ +]
n
αi [ yi ( w x + b − 1)] i =1
Les conditions nécessaires d’optimum :
∂L ∂b [(] [∗][,][ b][∗][, α][∗] [) = 0][ =] [⇒]
n
αi [∗] i [= 0] i =1
∂L ∂w [(] [∗][,][ b][∗][, α][∗] [) = 0][ =] [⇒] [∗] [=]
n
αi [∗] i i i =1
Par substitution on obtient le problème dual :
max ni =1 [α] i,j =1 [α] [α] i α
[−] [ ]
t.q. αi 0 , i = 1 , . . ., n (admissibilité duale)
- ≥ n i =1 [α] [= 0] [(] [)]
Les vecteurs de support sont ceux pour lesquels αi ≥ 0
Ajouter des échantillons à l’ensemble d’apprentissage qui ne sont pas des vecteurs supports n’a aucune influence sur la solution finale
b [∗] est obtenu 0 partir de la relation |xs [∗] [+] [ b][∗][|] [ = 1] de support
La fonction de décision permettant de classer une nouvelle observation x est
f [∗] ( x ) =
n
αi [∗] i i [+] [ b][∗] i =1
L’hyperplan solution ne dépend que du produit scalaire entre le vecteur d’entrée et les vecteurs de supports. Cette particularité est l’origine de la 2eme innovation majeure des SVM : le passage par un espace de description grâce à des fonctions noyau.
2 Objectifs et contenu de l’enseignement
3 Séparateurs à vaste marge
4 SVM linéaire (cas séparable)
Publicité
5 Données non séparables linéairement
Dans le cas ou les données ne sont pas séparables linéairement on utilise une technique dite de marge souple, qui tolère les mauvais classements :
Rajouter des variables de relâchement des contraintes ξi
Pénaliser ces relâchements dans la fonction objectif.
L’idée : modéliser les erreurs potentielles par des variables d’écart positives ξi associées aux observations ( xi, yi ) , i = 1 , . . . n . Si un point ( xi, yi ) vérifie la contrainte de marge yi w xi + b ) ≥ 1 alors la variable d’écart (qui est une mesure du cout de l’erreur) est nulle. Nous avons donc deux situations :
Pas d’erreur : yi ( w xi + b ) ≥ 1 = ⇒ ξi = 0
Erreur : yi ( w xi + b ) < 1 = ⇒ ξi = 1 − yi ( w xi + b ) > 0
On associe à cette définition une fonction cout appelée « cout charnière » :
- _ξi_ = max 0 _,_ 1 _−_ _yi_ ( _w_ _ _ _xi_ + _b_ )
Un seul point est mal classé (point bleu). L’écart mesure la distance du point à la marge numérique de l’hyperplan séparateur.
Problème d’optimisation dans le cas des données non-séparable : 1 2 [||] [||] [2] min w,b - n i =1 [ξ]
min w,b
1 2 [||] [||] [2]
min - n w,b
i =1 [ξ] t.q. yi ( w · xi + b ) ≥ 1 − ξi , i = 1 , . . ., n ξi ≥ 0 , i = 1 , . . ., n
Si toutes les variables d’écart ξi = 0, on retrouve le problème séparable linéairement
Puisque il faut minimiser les deux termes simultanément on introduit une variable d’équilibrage C > 0 qui permet d’avoir une seule fonction objectif dans le problème d’optimisation :
1 min w,b 2 [||] [||] [2][ +] [ C]
n
ξi i =1
Problème d’optimisation dans le cas des données non-séparable :
t.q. yi ( w · xi + b ) ≥ 1 − ξi , i = 1 , . . ., n ξi ≥ 0 , i = 1 , . . ., n
min w,b
1 2 [||] [||] [2][ +] [ C] [ ] i =1 [ξ]
C est une variable de pénalisation des points mal classés faisant un compromis entre la largeur de la marge et les points mal classés.
ξi s’appellent aussi variables ressort (anglais : slack variables )
Le problème dual devient : max α
Publicité
max ni =1 [α] 2 α
[−] [1]
n 2 i,j =1 [α] [α] i
[1]
t.q. C αi 0 , i = 1 , . . ., n (admissibilité duale)
- ≥ ≥ n i =1 [α] [= 0] [(] [)]
C joue le rôle d’une constante de régularisation (la régularisation est d’autant plus forte que C est proche de 0 !) La différence pour le problème duale entre le cas séparable et non séparable est que les valeurs des αi sont majorées par C . Les points mal classés ou placés dans la marge ont un αi = C b est calculé de sorte que yi f ( xi ) = 1 pour les points tels que C > αi > 0
La fonction de décision permettant de classer une nouvelle observation x est toujours
f [∗] ( x ) =
n
αi [∗] i i [+] [ b][∗] i =1
Implémentations software : Torch, LibSVM, LibLinear, Scikit-Learn
Toch, http ://torch.ch/
LibSVM, https ://www.csie.ntu.edu.tw/~cjlin/libsvm/
LibLinear, https ://www.csie.ntu.edu.tw/~cjlin/liblinear/
Scikit-Learn, http ://scikit-learn.org/
Pratiquement tous les grands environnement de modélisation mathématique possèdent implémentations performantes pour les SVM et méthodes à noyaux (R, Matlab, Mathematica, Scipy, Torch, Scikit-learn, etc.)
Séparation linéaire (vecteurs de support en gras) :
Séparation linéaire (vecteurs de support en gras) :
La version à noyaux (séance suivante) permet de séparer mieux les classes :
Ou même des classes plus compliquées :
Livres, articles, web :
Steinwart, Christmann, Support Vector Machines, Springer 2008
Scholkopf, Smola, Learning with Kernels, The MIT Press, 2001
Hastie, Tibshirani, Friedman, The elements of statistical learning : Data mining, inference, and prediction, New York, Springer Verlag, 2006
—, Machines à vecteurs supports (WikiStat), http ://wikistat.fr