0% ont trouvé ce document utile (0 vote)
4 vues28 pages

SVM : Séparateurs à Vastes Marges

C'est un cours de statistiques

Transféré par

zehesimon.imspuac
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
0% ont trouvé ce document utile (0 vote)
4 vues28 pages

SVM : Séparateurs à Vastes Marges

C'est un cours de statistiques

Transféré par

zehesimon.imspuac
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Séparateurs à

Vastes Marges
(SVM)

Prof. Armel
YODE

Principe
général
Séparateurs à Vastes Marges (SVM)
SVM pour des
données
linéairement
séparables

SVM pour les


Prof. Armel YODE
données
linéairement
non séparables
Cas des données
presque
linéairement 6 février 2017
séparables
Cas des données
linéairement non
séparables
Séparateurs à
Vastes Marges
(SVM)

Prof. Armel
YODE
1 Principe général
Principe
général

SVM pour des


données
linéairement
2 SVM pour des données linéairement séparables
séparables

SVM pour les


données
linéairement 3 SVM pour les données linéairement non séparables
non séparables
Cas des données Cas des données presque linéairement séparables
presque
linéairement
séparables
Cas des données linéairement non séparables
Cas des données
linéairement non
séparables
Séparateurs à
Vastes Marges
(SVM)

Prof. Armel
YODE

Principe
général • On dispose de n exemples (x1 , y1 ), . . . , (xn , yn )
SVM pour des
données
. xi ∈ X = Rd est appelée entrée
linéairement . yi ∈ Y sortie ou label ou étiquette. Dans ce cours
séparables
Y = {−1, 1} ; on peut étendre à card(Y) > 2 ou Y = R.
SVM pour les
données
linéairement
• L’objectif est de prédire y pour une nouvelle valeur de x.
non séparables
Cas des données
presque
linéairement
séparables
Cas des données
linéairement non
séparables
Séparateurs à
Vastes Marges
(SVM)

Prof. Armel
YODE

Principe • On cherche un classifieur g : Rd −→ {−1, 1}.


général

SVM pour des • On cherche une fonction de décision f : Rd −→ R telle


données
linéairement que g (x) = sgn(f (x)).
séparables

SVM pour les


• On suppose que la fonction f est de la forme :
données
linéairement
non séparables f (x) = hw , xi + b.
Cas des données
presque
linéairement
séparables
Cas des données
linéairement non
séparables
Séparateurs à
Vastes Marges
(SVM)

Prof. Armel
YODE

Principe
général
Définition
SVM pour des Une SVM (Support Vector Machine) ou Machine à Vecteurs
données
linéairement Supports est une famille d’algorithmes d’apprentissage
séparables
supervisé pour des problèmes de discrimination ou de
SVM pour les
données régression.
linéairement
non séparables
Cas des données Une SVM possède de bonne propriété de généralisation.
presque
linéairement
séparables
Cas des données
linéairement non
séparables
Cas linéairement séparable

Séparateurs à
Vastes Marges
(SVM)

Prof. Armel
YODE

Principe
général

SVM pour des


données
linéairement
séparables

SVM pour les


données
linéairement
non séparables
Cas des données
presque
linéairement
séparables
Cas des données
linéairement non
séparables
Séparateurs à
Vastes Marges
(SVM)

Prof. Armel
On suppose que X = Rd et on note h·, ·i le produit scalaire
YODE usuel.
Principe
général
Définition
SVM pour des Les données (x1 , y1 ), . . . , (xn , yn ) sont dites linérairement
données
linéairement séparables s’il existe (w , b) ∈ Rd × R tel que pour tout i,
séparables

SVM pour les - yi = 1 si hw , xi i + b > 0


données
linéairement - yi = −1 si hw , xi i + b < 0,
non séparables
Cas des données
presque
c’est à dire ∀i = 1, . . . , n yi (hw , xi i + b) > 0.
linéairement
séparables
Cas des données
linéairement non L’équation hw , xi + b = 0 définit un hyperplan séparateur de
séparables
vecteur orthogonal w .
Séparateurs à
Vastes Marges
(SVM)

Prof. Armel
YODE

Principe
général

SVM pour des


données
linéairement
séparables

SVM pour les


données
linéairement
non séparables
Cas des données
presque
linéairement
séparables
Cas des données
linéairement non
séparables

!
Distance d’un point à la frontière de décision

Séparateurs à
Vastes Marges
Soit H(w , b) = {z ∈ Rd : f (z) = hw , zi + b = 0} un hyperplan
(SVM) et soit x ∈ Rd . La distance du point x à l’hyperplan H est :
Prof. Armel
YODE |hx, w i + b|
d(x, H) = .
Principe kw k
général

SVM pour des


données
En effet, soit x ∗ la projection orthogonale de x sur H. on a
linéairement x = x ∗ + a kww ∗ w
k =⇒ x − x = a kw k .
séparables

SVM pour les


On a
données
w
linéairement
non séparables hw , a i = akw k = hw , x − x ∗ i = hw , xi − hw , x ∗ i = hw , xi + b
Cas des données
kw k
presque
linéairement
séparables hw ,xi+b
Cas des données
linéairement non
Ainsi, on obtient : a = kw k . Par suite :
séparables
r
p w w
d(x, H) = hx − x ∗ , x − x ∗ i = ha ,a i = |a|.
kw k kw k
Séparateurs à
Vastes Marges
(SVM)

Prof. Armel
YODE
• La marge est la distance entre la frontière de séparation et
Principe
général les exemples les plus proches :
SVM pour des
données |hw , xi + b|
linéairement d(x, H) = .
séparables kw k
SVM pour les
données
linéairement
• Ces exemples sont appelés vecteurs supports.
non séparables
Cas des données • Dans les SVM, la frontière de séparation choisie est celle
presque
linéairement
séparables
qui maximise la marge
Cas des données
linéairement non
séparables
!

Séparateurs à
Vastes Marges
(SVM)

Prof. Armel
YODE

Principe
général

SVM pour des


données
linéairement
séparables

SVM pour les


données
linéairement
non séparables
Cas des données
presque
linéairement
séparables
Cas des données
linéairement non
séparables

!
Séparateurs à
Vastes Marges
(SVM)

Prof. Armel
YODE

Principe
général

SVM pour des


données
linéairement
séparables

SVM pour les


données
linéairement
non séparables
Cas des données
presque
linéairement
séparables
Cas des données
linéairement non
séparables

!
Séparateurs à Pourquoi maximiser la marge ?
Vastes Marges
(SVM)

Prof. Armel
YODE

Principe
général

SVM pour des


données
linéairement
séparables

SVM pour les !


données
linéairement
non séparables • Le fait d’avoir une marge plus large procure plus de
Cas des données
presque sécurité lorsque l’on classe un nouvel exemple.
linéairement
séparables
Cas des données
• La partie droite nous montre qu’avec un hyperplan
linéairement non
séparables optimal, un nouvel exemple reste bien classé alors qu’il
tombe dans la marge.
• On constate sur la partie gauche qu’avec une plus petite
marge, l’exemple se voit mal classé
Séparateurs à
Vastes Marges
(SVM)

Prof. Armel
YODE
• Un hyperplan est dit canonique par rapport aux données
Principe
général
{x1 , . . . , xn } si
SVM pour des
données min |hw , xi i + b| = 1.
linéairement xi
séparables

SVM pour les


données
• La marge étant définie par
linéairement
non séparables 2
Cas des données M= .
presque
linéairement kw k
séparables
Cas des données
linéairement non
séparables
Expression primale du problème des SVM

Séparateurs à
Vastes Marges
(SVM)

Prof. Armel Trouver un hyperplan séparateur de marge maximale équivaut à


YODE
trouver le couple (w , b) tel que :
Principe
général
1
SVM pour des kw k2 soit minimal
données 2
linéairement
séparables
sous la contrainte yi (hw , xi i + b) ≥ 1, ∀i = 1, . . . , n.
SVM pour les
données
linéairement
non séparables
Cas des données
presque
• Problème d’optimisation convexe sous contraintes
linéairement
séparables linéaires.
Cas des données
linéairement non
séparables • Existence d’un optimum global.
Multiplicateurs de Lagrange

Séparateurs à
Vastes Marges
Le lagrangien est défini par :
(SVM)
n
1 X
Prof. Armel
YODE
L(w , b, α) = kw k2 − αi (yi (hw , xi i + b) − 1) (1)
2
i=1
Principe
général Les multiplicateurs de Lagrange αi ≥ 0.
SVM pour des
données n n
linéairement
∂L(w , b, α) X X
séparables =w− αi yi xi = 0 ⇐⇒ w = αi yi xi . (2)
∂w
SVM pour les i=1 i=1
données n n
linéairement ∂L(w , b, α) X X
non séparables =− αi yi = 0 ⇐⇒ αi yi = 0 (3)
Cas des données ∂b
presque i=1 i=1
linéairement
séparables
Cas des données
linéairement non
En réinjectant (2) et (3) dans l’équation (1), on obtient :
séparables
n n
X 1X
θ(α) = αi − αi αj yi yj hxi , xj i.
2
i=1 i,j
Expression duale du problème des SVM

Séparateurs à
Vastes Marges
(SVM)
Résoudre
 le problème primal revient à trouver
Prof. Armel
YODE α = α1 , . . . , αn )0 tels que :
Principe
général n n
X 1X
SVM pour des αi − αi αj yi yj hxi , xj i soit maximal
données 2
linéairement i=1 i,j
séparables

SVM pour les sous les contraintes


données
linéairement
non séparables
n
X
Cas des données
presque αi yi = 0 et αi ≥ 0 ∀i.
linéairement
séparables i=1
Cas des données
linéairement non
séparables
La solution α∗ du problème dual est indépendante de la
dimension d ; la SVM ne soufre pas du ”fléau de la dimension”.
Conditions de Karush-Kuhn-Tucker

Séparateurs à
Vastes Marges
(SVM)

Prof. Armel • αi∗ ≥ 0 ∀i = 1, . . . , n


YODE
• yi (hw ∗ , xi i + b ∗ ) ≥ 1 ∀i = 1, . . . , n.
Principe
général • αi∗ (yi (hw ∗ , xi i + b ∗ ) − 1) = 0 ∀i = 1, . . . , n.
SVM pour des
données
linéairement - Seuls les αi∗ > 0 interviennent dans la résolution du
séparables
problème.
SVM pour les
données
linéairement
- Les xi tels que αi∗ > 0 sont appelés les vecteurs supports.
non séparables
Cas des données
Ils sont situés sur les frontières définisssant la marge
presque
linéairement maximale, c’est à dire,
séparables
Cas des données
linéairement non
séparables yi (hw ∗ , xi i + b ∗ ) = 1
Séparateurs à
Vastes Marges • Calcul de b : b n’apparait pas dans le problème dual et
(SVM)
doit donc être calculé à partir du problème primal. Or, on
Prof. Armel
YODE
sait que pour les vecteurs supports, on a :
Principe yi (hw , xi i + b) = 1
général

SVM pour des


données
Faire la moyenne de ces termes pour l’ensemble des
linéairement
séparables
vecteurs supports est plus judicieux afin d’obtenir une
SVM pour les
valeur numérique stable.
données
linéairement • La marge est
non séparables 2  X 1/2
Cas des données = αi .
presque
linéairement kw k
séparables i∈SV
Cas des données
linéairement non
séparables • La fonction de décision :
X
f (x) = hw , xi i + b = hx, xi i + b.
i∈SV
Cas presque linéairement séparable

Séparateurs à
Vastes Marges
(SVM)

Prof. Armel
YODE

Principe
général

SVM pour des


données
linéairement
séparables

SVM pour les


données
linéairement
non séparables
Cas des données
presque
linéairement
séparables
Cas des données
linéairement non
séparables
Séparateurs à
Vastes Marges
(SVM) La solution est d’autoriser quelques vecteurs à être bien classés
Prof. Armel mais dans la région définie par la marge, voire mal classés. La
YODE
contrainte yi (hw , xi i + b) ≥ 1 devient yi (hw , xi i + b) ≥ 1 − ξi
Principe avec ξi ≥ 0
général

SVM pour des - ξ ∈ [0, 1] ⇐⇒ bien classé, mais région définie par la marge
données
linéairement - ξi > 1 ⇐⇒ mal classé
séparables

SVM pour les


données
Définition
linéairement
non séparables On parle de marge souple ou marge relaxé.
Cas des données
presque
linéairement
Les variables ξi sont appelées les variables ressorts (slacks)
séparables
Cas des données
linéairement non
séparables
Les contraintes relaxées ne peuvent pas être utilisées sans
contrepartie sous peine d’obtenir une marge maximale infinie
(en prenant des valeurs de ξi suffisamment grandes).
Problème d’optimisation primal

Séparateurs à
Vastes Marges
(SVM) La solution est de pénaliser les grandes valeurs de ξi . Il s’agira
Prof. Armel
YODE
de trouver w , b et ξ = (xi1 , . . . , ξn ) tels que

Principe n
1 X
général
kw k2 + C ξi soit minimal
SVM pour des 2
données i=1
linéairement
séparables
sous contraintes
SVM pour les
données
linéairement
non séparables
yi (hw , xi i + b) ≥ 1 − ξi , ξi ≥ 0
Cas des données
presque
linéairement
séparables
où C est une variable de pénalisation des points mal classés et
Cas des données
linéairement non faisant un compromis entre la dimension de la marge et les
séparables
points mal classés ; C > 0 est un paramètre ; C est un
paramètre d’entrée de la SVM à ajuster.
Problème d’optimisation dual

Séparateurs à
Vastes Marges
(SVM)

Prof. Armel Résoudre le problème primal revient à trouver


YODE

α = α1 , . . . , αn )0 tels que :
Principe
général
n n
SVM pour des X 1X
données αi − αi αj yi yj hxi , xj i soit maximal
linéairement
séparables
2
i=1 i,j
SVM pour les
données
linéairement sous les contraintes
non séparables
Cas des données n
presque
X
linéairement
séparables
αi yi = 0 et 0 ≤ αi ≤ C ∀i.
Cas des données
linéairement non i=1
séparables
Conditions de Karush-Kuhn-Tucker

Séparateurs à
Vastes Marges
(SVM) • 0 ≤ αi∗ ≤ C ∀i = 1, . . . , n
Prof. Armel
YODE
• yi (hw ∗ , xi i + b ∗ ) ≥ 1 − ξi∗ ∀i = 1, . . . , n.
• αi∗ (yi (hw ∗ , xi i + b∗ ) + ξi∗ − 1) = 0 ∀i = 1, . . . , n.
Principe
général
• ξi∗ (αi∗ − C ) = 0, ∀i = 1, . . . , n.
SVM pour des
données
linéairement
Les xi tels que αi∗ > 0 sont les vecteurs supports.
séparables
Deux types de vecteurs supports :
SVM pour les
données • Les vecteurs correspondant à des variables ressort nulles.
linéairement
non séparables Ils sont situés sur les frontières de la région définissant la
Cas des données
presque
linéairement
marge.
séparables
Cas des données
linéairement non
• Les vecteurs correspondant à des variables ressort non
séparables
nulles : ξi∗ > 0 et dans ce cas αi∗ = C .
Les vecteurs qui ne sont pas supports vérifient αi∗ = 0 et
ξi∗ = 0.
Cas des données linéairement non séparables

Séparateurs à
Vastes Marges Pour surmonter les inconvénients des cas non linéairement
(SVM)
séparable, l’idée des SVM est de changer l’espace des données.
Prof. Armel
YODE La transformation des données peut permettre une séparation
Principe
linéaire des exemples dans un nouvel espace :
général

SVM pour des


données
linéairement
séparables

SVM pour les


données
linéairement
non séparables
Cas des données
presque
linéairement
séparables !
Cas des données
linéairement non
séparables
On a donc une transformation d’un problème de séparation non
linéaire dans l’espace de représentation en un problème de
séparation linéaire dans un de plus grande dimension.
Séparateurs à
Vastes Marges
(SVM)

Prof. Armel
YODE

Principe Envoyer les entrées {xi , i = 1, . . . , n} dans un espace de Hilbert


général
H, de grande dimension, voire de dimension infinie, via une
SVM pour des
données fonction ϕ, et appliquer une SVM linéaire aux nouvelles
linéairement
séparables données {(ϕ(xi ), yi ), i = 1, . . . , n}.
SVM pour les La sortie attribuée à l’entrée x est celle attribuée à son image
données
linéairement ϕ(x).
non séparables
Cas des données
L’espace H est appelé espace de représentation (feature space).
presque
linéairement
séparables
Cas des données
linéairement non
séparables
Comment choisir H et ϕ ?

Séparateurs à
Vastes Marges
(SVM)
La règle de discrimination de la SVM non linéaire est définie
Prof. Armel
par :
YODE

Principe
f (x) = IPni=1 yi α∗i hϕ(xi ),ϕ(xj )i≥0 − IPni=1 yi α∗i hϕ(xi ),ϕ(xj )i<0
général

SVM pour des Les αi∗ sont solutions du problème dual dans l’espace H :
données
linéairement
séparables n n
X 1X
SVM pour les Maximier αi − αi αj yi yj hϕ(xi ), ϕ(xj )i
données 2
linéairement i=1 i,j
non séparables
Cas des données
presque
linéairement sous les contraintes
séparables
Cas des données
linéairement non n
X
séparables
αi yi = 0 et 0 ≤ αi ≤ C ∀i.
i=1
Astuce du noyau

Séparateurs à
Vastes Marges
(SVM)

Prof. Armel
YODE

Principe La connaissance seule de la fonction k définie par


général
k(x, x 0 ) = hϕ(x), ϕ(x 0 )i permet de lancer la SVM dans H ,
SVM pour des
données sans déterminer explicitement H et ϕ.
linéairement
séparables
Définition
SVM pour les
données
linéairement
Une fonction k : X × →R telle que k(x, x 0 ) = hϕ(x), ϕ(x 0 )i
non séparables pour une fonction ϕ : X → H donnée est appelée noyau.
Cas des données
presque
linéairement
séparables
Cas des données
linéairement non
séparables

Vous aimerez peut-être aussi