Les Supports Vecteurs Machines
Leila HAMDAD
Leila HAMDAD Introduction au Machine Learning
Plan
Leila HAMDAD Introduction au Machine Learning
Introduction
Les SVM sont une classe d’algorithmes d’apprentissage, initialement
définie pour le cas de la prévision de variable qualitative binaire par suite
ils ont été généralisé au cas de variables quantitatives (regression).
Ils sont basées sur la recherche de l’hyperplan à marge optimale qui
sépare correctement les données. Elle découle des travaux de Vapnik
(1995) sur la théorie d’apprentissage.
Leila HAMDAD Introduction au Machine Learning
Représentation SVM
Leila HAMDAD Introduction au Machine Learning
Problème des SVM
Transformer le problème de discrimination en un problème linaire de
recherche d’un hyperplan.
Hyperplan est solution d’un problème d’optimisation sous contraintes.
Le passage au cas non linéaire en introduisant un noyau (Induit une
transformation non linéaire des données vers un espace intermédiaire
(feature space) de plus grande dimension.
Leila HAMDAD Introduction au Machine Learning
Domaines d’application
• détection de spam,
• Séquence génomique.
• Diagnostic médical.
• Reconnaissance de forme.
Remarque
Les SVM sont plus pénalisé par le nombre d’observations (nombre de
vecteurs support) que par le nombre de variables.
Leila HAMDAD Introduction au Machine Learning
Principe
Soit une variable Y binaire à prédire à valeurs dans −1, 1 et X 1 , ..., X p
à valeurs dans F , des variables explicatives et f (x) un modèle fonction
de x = x 1 , ..., x p .
l’objectif est d’estimer f (x) de façon est ce que P[f (x) 6= Y ] soit
minimale. Lorsque Y est binaire, cela revient à chercher une frontière de
décision dans F
Marge : La démarche consiste à rechercher une fonction ϕ dont le signe
fournit la prévision :
fˆ = signe(ϕ)
L’erreur dans ce cas est
P(f (x) 6= Y ) = P(Y ϕ(x) 6 0).
Leila HAMDAD Introduction au Machine Learning
Leila HAMDAD Introduction au Machine Learning
Séparateur linéaire
Hyperplan séparateur : Parmi tout les hyperplans solution ( qui sépare
les observations), on choisit celui qui se trouve le plus loin c’est à dire de
marge maximale.
L’Hyperplan est défini :
hw , xi + b = 0
w est une vecteur orthogonal au plan et le signe de
ϕ(x) = hw , xi + b
indique de quel coté se trouve le point x à prédire.
Un point est bien classé si
y hw , xi + b > 1
Un plan hw , bi est un séparateur si
yi ϕ(xi) > 1, ∀i
Leila HAMDAD Introduction au Machine Learning
Distance d(x) au plan hw , bi :
|hw , xi + b| |ϕ(x)|
d(x) = =
kw kâ kw k
2
La marge du plan a pour valeur Problème d’optimisation
kw k
1
min kw k2
2
avec
∀i, yi (hw , xi i + b) > 1 La solution est un point selle (wbi , bbi , λbi du
Lagrangien
n
1 X
L(w , b, λ) = kw k22 − λi [yi (hw , xi + b) − 1]
2
i=1
Les vecteurs supports sont les vecteurs xi qui sont les plus proches du
plan et qui vérifient
yi (hwbi , xi i + b
b) = 1
Leila HAMDAD Introduction au Machine Learning
Phase de construction
La résolution du système aux dérivées partielles mènent aux relations qui
vérifient le plan optimale avec les λ
bi non nuls seulement pour les points
supports
X n
w=
b λbi yi xi
i=1
et
n
X
λbi yi = 0
i=1
Ces derniers permettent de réécrire le Lagrangien comme suite
n n
X 1X
W (λ) = λi − λi λj yi yj hxi , xj i
2
i=1 i=1
Pour trouver le point selle, il suffit de maximiser W (λ) avec λi > 0 pour
tout i = 1, ..., n. La résolution de ce problème donne l’équation de
l’hyperplan optimale
Xn
λbi yi hxi , xj i + b
b
i=1
Leila HAMDAD Introduction au Machine Learning
Procédure de discrimination
Pour une observation supplémentaire à affecter dans l’une des classes, il
suffit de regarder le signe de l’expression
n
X
ϕ(x) = λbi yi hxi , xj i + b
b
i=1
Leila HAMDAD Introduction au Machine Learning
Séparateur non linéaire
Dans ce cas les observations dans F sont considérées comme étant
transformées par une application non linéaire Φ(F ) Dans H muni d’un
produit scalaire et de plus grande dimension.
La formule
Xn
λbi yi hxi , xj i + b
b
i=1
ne fait intervenir les observations que dans le produit scalaire, ainsi il
n’est pas nécessaire d’expliciter la fonction φ, il suffit d’exprimer les
produit scalaire dans H à l’aide d’un fonction symétrique appelée noyau
telle que : 0 0
K (x, x ) = hφ(x), φ(x )i
Leila HAMDAD Introduction au Machine Learning
Le noyau permet d’interpréter la notion de proximité adapté au problème
de discrimination.
Condition de Mercer : une fonction symétrique K (., .) est un noyau si
pour tout les xi la matrice de terme générale K (xi , xj )est une matrice
définie positive. Dans ce cas il existe un espace H et une fonctionφ tel
que : 0 0
K (x, x ) = hφ(x), φ(x )i
Exemple de noyau :
Noyau linéaire : 0 0
K (x, x ) = hx, x i
Polynomial : 0 0
K (x, x ) = c(c + hx, x i)d
Gaussien : 0 0
K (x, x ) = (c + hx, x i)d
Leila HAMDAD Introduction au Machine Learning
Avantages des SVM
? Les SVM offrent une bonne performance de classification sur les
données d’apprentissage.
? Les SVM est plus efficace pour classer des données future.
? Aucune hypothèse forte n’est faite sur les données.
? Pas de sur apprentissage.
Leila HAMDAD Introduction au Machine Learning
