Techniques d’apprentissage

IFT603

Machines à vecteurs de support

Par
Pierre-Marc Jodoin
/
Hugo Larochelle

Méthode à Noyau
Au chapitre précédent, nous avons vu les méthodes à noyau
 Entraînement
 1 
a   K  I N  t
 Prédiction Matrice de Gram
N
  
y x    k x , xn a n Noyau
n 1

Malheureusement, on doit toujours avoir accès aux données

d’entraînement

 
Comparaison entre x et toutes les données d’entraînement xn  n

1
 Machine à vecteur de Support
(support vector machine, SVM en anglais)

‣ Algorithme principalement dédié à la classification binaire

‣ Après l’entraînement, SVM seulement un sous-ensemble des données
d’entraînement
‣ Plusieurs des a n vont être à 0

Classification linéaire RAPPEL

Classe C0
t  1
x2 
t 1 yw x   w0  w1 x1  w2 x2
 
 w0  wT x
Classe C1

 x1
w
Un problème est linéairement séparable
si on peut séparer les éléments de chaque
classe avec un hyperplan.

2
 Au cœur des machines à vecteurs de support
figure la notion de marge.

Marge
  
x2
yw ( x )  wT x  w0

y w ( x )  0

w

y w ( x )  0

x'


yw  x '

w w
 0
|| w ||

x1

yw ( x )  0 6

3
 Marge
  
x2
yw ( x )  wT x  w0

y w ( x )  0

w

y w ( x )  0

x'


yw  x ' Distance signée

w w
 0
|| w ||

x1

Preuve au tableau yw ( x )  0 7

Marge
  
x2
yw ( x )  wT x  w0

y w ( x )  0

w

y w ( x )  0

x'


yw x '
t1 
w
w
 0
|| w ||

x1

yw ( x )  0 8

4
 
Pour être général, on va considérer  (x )
 
  T  
x2 y  x   w   x   w0

w
 
y w (  x )  0

w
 
y w (  x )  0

x'

 
 
yw  x '
t1 
w
w
 0
|| w ||

x1
 
 
yw   x   0 9

La marge est la plus petite distance entre la

surface de séparation et les données d’entraînement


 y w   xn 
marge  min n  t n 
 
w  >0
 
<0

Vecteur de support

Marge

10

5
 Classifieur à marge maximale

Un SVM cherche les paramètres wT et w0 de l’hyperplan qui
maximisent la marge

arg max
 margew , w0 
w , w0

 arg max

min n  t n
 


 y w   xn  


w, w0
 w 
 

T 
  w
  xn   w0 
 arg max
  min t
n n  
w, w0
  w 
 1
 arg max

w, w0  w
  min  t
n n
T  
w  xn   w0 
 
11

11

Problème!

Il existe une infinité de solutions au problème de la page précédente!


La marge est la même si on multiplie wT et w0 par une constante non nulle (a)

T   T  
w   xn   w0 aw  xn   aw0
tn   t n 
w aw
12

12

6
 Solution!

Contraindre la solution pour que les vecteurs de support

   
  T  
t n y w   xn   t n w  xn   w0  1

13

13

Sans contrainte

T  
t n w   xn   w0  0 
>0

<0

Vecteur de support

Marge

14

14

7
 Avec contrainte

T  
t n w   xn   w0  1 
=1

= -1

Vecteur de support

Marge

15

15

Exemple de résultat au terme

d’une optimisation SVM

Vecteurs de
support

16

16

8
 En supposant que l’ensemble d’entraînement est linéairement
séparable, on a :

 1
arg max
 
w, w0  w
 min t
n n
T  
w   xn   w0 
 

2 façons de résoudre ce problème :

Approche primale
Approche duale
17

17

18

18

9
 Approche primale

 1
arg max
 
T  
  min n t n w   xn   w0
w, w0  w

 =1 

19

19

Approche primale

 1
arg max
  
w, w0  w
min t
n n w
T  
  xn   w0 
 =1 

1  2 
arg min
  w 
w , w0 2
Équivalent à  
T  
 
t.q. t n w   xn   w0  1 n

Ce problème d’optimisation est un programme quadratique

pour lequel il existe de nombreuses bibliothèques informatiques

20

10
 Approche duale:
inclure les noyaux dans SVM

21

21

Approche duale
1  2 
arg min
  w 
w , w0 2
 
   
t.q. t n wT xn   w0  1 n
On peut enlever les contraintes en introduisant les multiplicateurs de Lagrange
(voir Bishop, Annexe E)

  1 2 N   

Lw, w0 , a   w   an t n wT  xn   w0  1
2
  t.q an  0
n 1

22

11
 Approche duale
1  2 
arg min
  w 
w , w0 2
 
 T  
t.q. t n w  xn   w0  1 n
On peut enlever les contraintes en introduisant les multiplicateurs de Lagrange
(voir Bishop, Annexe E)

  1 2 N   

Lw, w0 , a   w   an t n wT  xn   w0  1
2
  t.q an  0
n 1

23

  1 2 N

  
Lw, w0 , a   w   an t n wT  xn   w0  1
2
  t.q an  0
n 1

 
 
Lw, w0 , a  Lw, w0 , a 
En annulant les dérivées  0 0
w w0

 N   N
w   an t n  xn  a t n n 0
n 1 n 1

24

12
   1 2 N   

Lw, w0 , a   w   an t n wT  xn   w0  1
2
  t.q an  0
n 1

 
 
Lw, w0 , a  Lw, w0 , a 
En annulant les dérivées  0 0
w w0

 N   N
w   an t n  xn  a t n n 0
n 1 n 1


on peut exprimer w comme une
combinaison linéaire des entrées

25

 
On peut alors réécrire Lw, w0 , a  comme suit
 
  xn    xm 
T

N
 1 N N  
L  a    an   an amtn tm k  xn , xm 
n 1 2 n 1 m 1

N
où on a toujours an  0 et a t
n 1
n n 0

26

26

13
  
On peut alors réécrire Lw, w0 , a  comme suit
 
  xn    xm 
T

N
 1 N N  
L  a    an   an amtn tm k  xn , xm 
n 1 2 n 1 m 1

N
où on a toujours an  0 et a t
n 1
n n 0

Solution par programme quadratique

Représentation duale avec l’astuce du noyau

27

27

 
  xn    xm 
T

N
 1 N N  
L  a    an   an amtn tm k  xn , xm 
n 1 2 n1 m 1


On peut démontrer que la solution à L  a  satisfait

an  0
 
tn y  xn   1 et an  0
tn y  xn   1  0
Implique ou

an tn y  xn   1  0 
tn y  xn   1 et an  0

Lié aux conditions de Karush-Kuhn-Tucker (KKT)

(voir Bishop, annexe E)
28

28

14
  
  xn    xm 
T

N
 1 N N  
L  a    an   an amtntm k  xn , xm 
n 1 2 n1 m 1


On peut démontrer que la solution à L  a  satisfait

an  0 Vecteurs de support

 
tn y  xn   1 et an  0
tn y  xn   1  0
Implique ou

an tn y  xn   1  0 
tn y  xn   1 et an  0

Lié aux conditions de Karush-Kuhn-Tucker (KKT)

(voir Bishop, annexe E)
29

29


tn y  xn   1 et an  0 Vecteurs de

Exemple
support

30

30

15
 
tn y  xn   1 et an  0 Vecteurs de

Exemple
support

tn y  xn   1 et an  0

31

31


tn y  xn   1 et an  0 Vecteurs de

Exemple
support

tn y  xn   1 et an  0

32

32

16
 
tn y  xn   1 et an  0 Vecteurs de

Exemple
support

tn y  xn   1 et an  0

La solution aurait été identique,

même si les points n’avaient
pas été dans l’ensemble
d’entraînement!

33

33

Exemple avec noyau gaussien

34

17
 Exemple avec noyau gaussien

Marge

Marge

Marge

Surface de décision

35

Exemple avec noyau gaussien

Vecteurs de support

Marge

Marge

Marge

Surface de décision

36

18
 Exemple avec noyau gaussien
Vecteurs de support

Marge

Marge

Marge

Surface de décision

37

Prédiction avec la représentation duale

 
    
yw  x   wT  x   w0
 N   T  
   ant n  xn   x   w0
 n 1 

  T 

N
  ant n  xn    x   w0
n 1
N
 
  ant n k xn , x   w0
n 1

Seuls les vecteurs de Noyau

support vont voter! 38

38

19
 Prédiction avec la représentation duale

 
    
yw  x   wT  x   w0
 N   T  
   ant n  xn   x   w0
 n 1 


  T 

N
  ant n  xn    x   w0
n 1
N
 
  ant n k xn , x   w0
n 1

Voir équation 7.18 pour calculer w0

39

39

40

40

20
 Données non séparables

41

41

SVM : Approche primale

RAPPEL

 1
arg max
  
w, w0  w
min t
n n
T  
w   xn   w0 
 =1 

1  2 
arg min
  w 
w, w0 2
Équivalent à  
 T  

t.q. t n w  xn   w0  1 n

Ce problème d’optimisation est un programme quadratique

pour lequel il existe de nombreuses bibliothèques

42

21
 SVM : Approche primale
RAPPEL

 1
arg max
 
w, w0  w
 min t
n n w 
T  
  xn   w0 
 =1 
Que faire s’il y a :

- Des données aberrantes dans  d’entraînement?

l’ensemble 
1  2
arg min
  w 
w, w0 2
Équivalent à 
- Si les données des 2 classes se chevauchent? 
   

t.q. t n wT xn   w0  1 n

Ce problème d’optimisation est un programme quadratique

pour lequel il existe de nombreuses bibliothèques

43

Exemple de classes qui se chevauchent

−2

−2 0 2

44

22
Variables de ressort (slack variables)
Permettre que certains exemples ne respectent pas la
contrainte de marge

1  2  N

arg min

1  2 
 w 
arg min
 
w , w0 , 2

w 

 C 
n 1
n
w, w0 2
 
 
Devient  
t.q. t n yw   xn   1   n
 
 
t.q. t n y w  xn   1 n
n,  n  0

Les variables de ressorts  n correspondent aux violations

des contraintes de marge.

45

Variables de ressort (slack variables)

Permettre que certains exemples ne respectent pas la
contrainte de marge

1  2  N

arg min

1  2 
 w 
arg min
 
w , w0 , 2

w 

 C 
n 1
n
w, w0 2
 
 
Devient  
  t.q. t n yw   xn   1   n
t.q. t n y w  xn   1 n
n,  n  0

Les variables de ressorts  n correspondent aux violations

des contraintes de marge.

46

23
Variables de ressort (slack variables)
Permettre que certains exemples ne respectent pas la
contrainte de marge

1  2  N

arg min
1  2  arg min
  w   C n

w, w0 2
 w  w , w0 , 2
  n 1
  Devient  
  t.q. t n yw   xn   1   n
t.q. t n y w  xn   1 n
n,  n  0

Si  n est plus grand que 1, la donnée est alors mal classée.

47

Variables de ressort (slack variables)

Permettre que certains exemples ne respectent pas la
contrainte de marge

1  2  N

arg min
1  2  arg min
  w   C n

w, w0 2
 w  w , w0 , 2
  n 1
  Devient  
  t.q. t n yw   xn   1   n
t.q. t n y w  xn   1 n
n,  n  0

La constante C  0 est un hyper-paramètre

• Plus C est petit, plus on permet des données mal classées

48

24
 Exemple (variables de ressort)

vecteurs de support

Les entrées qui violent

les contraintes de marge
sont aussi des
vecteurs de support
31

49

49

Variables de ressort – représentation duale

On peut montrer que la représentation duale demeure la même que
sans variable de ressort
N
 1 N N  
L  a    an   an amtntm k  xn , xm 

n 1 2 n 1 m 1
N
mais avec les contraintes C  an  0 et  antn  0
n 1

Reste un problème de programmation quadratique

50

50

25
 Variables de ressort – représentation primale

 1  22  N N
arg min  1 w C C  n
 

arg
w, w0min
, 2 W
W , w , 2 nn 1
0 n 1

t n ytwn yW xxnn11 n nn
t.q. t.q.
n  0 n,  n  0

51

51

Variables de ressort – représentation primale

 1  22  N N
arg min  1 w C C  n
 

arg
w, w0min
, 2 W
W , w, 2 nn 1
0 n 1

t.q.  n n 1W  tnn yw  nxnn
t.q. t y

x  1
 
 
n  0 n,  n  0

52

52

26
 Variables de ressort – représentation primale

1  22 NN

arg min
 W 
w CC max00,1
max ,1 t ntnyywWxxnn 
w,,w 0 2
W
nn11

Forme similaire à celle présentée au chapitre sur la segmentation linéaire!

53

53

Même forme qu’au chapitre 4!

Constante

N
 2
arg min
  max
w, w0
0,1  t y
n w
   x    w
n
n 1
   1 2C 

Fonction de perte Régularisation

(Hinge loss)

Solution obtenue par descente de gradient

54

54

27
 Résumé (SVM sans noyau - primal)
 T 
• Modèle: y w   xn   w   xn   w0

N
• Problème : 1 2
arg min
 w  C n
w , w0 , 2
n 1

t.q.  n  1  tn y w   xn 
n,  n  0

• Hyper-paramètres: C

• Entraînement : résoudre programme quadratique

55

Résumé (SVM sans noyau - primal)

 T 
• Modèle: y w   xn   w   xn   w0

N
• Problème : 1 2
arg min
 w  C n
w , w0 , 2
n 1

t.q.  n  1  tn y w   xn 
n,  n  0

• Hyper-paramètres: C

• Entraînement : descente de gradient

N
 2
arg min
  max0,1  tn yw  xn    w
w, w0
n 1

56

28
 Résumé (SVM avec noyau - dual)
 T 
• Modèle: y w   xn   w   xn   w0
N
1 N N  
• Problème : arg min

a

n 1
an   an amtn tm k  xn , xm 
2 n 1 m1
N
t.q. C  an  0 et  antn  0 Plusieurs des an seront à 0
n 1

• Hyper-paramètres: C

• Entraînement : programme quadratique

N
  
• Prédiction: y  xn    antn k  xn , x   w0
n 1
Seuls les vecteurs de Noyau
support vont voter!

57

Peut s’étendre à la régression

Voir section 7.1.4

y(x) y+ ϵ
ξ >0 y
y− ϵ

ξ> 0

58

58

29