Apprentissage Automatique

Régularisation / SVM

Stéphane Herbin
[email protected]

Apprentissage Automatique – SVM -- 1

 Rappel des cours précédents

Généralités
• Programmation orientée données
• Démarche globale: base de données, analyse préliminaire, sélection
de l’approche, optimisation, évaluation

Apprentissage supervisé
• Plusieurs approches classiques: kNN, bayésien naïf, arbres de
décision, méthodes ensemblistes

Apprentissage Automatique – SVM -- 2

 Aujourd’hui

• Approfondissement:
• Régularisation
• Un algorithme efficace: Support Vector Machines (SVM)
• Multiclasse

• TD:
• SVM: étude de l’influence des paramètres
• Validation croisée

Apprentissage Automatique – SVM -- 3

 Apprentissage supervisé

• On veut construire une fonction de décision F à partir d’exemples

• On dispose d’un ensemble d’apprentissage L sous la forme de paires

{xi,yi} où xi est la donnée à classer et yi est la classe vraie:

𝑫= 𝒙𝑖 , 𝑦𝑖 𝑖=1…𝑛

• L’apprentissage consiste à identifier cette fonction de classification dans

un certain espace paramétrique W optimisant un certain critère L:

𝑾 = arg min 𝐿(𝑫, 𝑾′)

𝑾′
• On l’applique ensuite à de nouvelles données.

𝑦 = 𝐹(𝒙; 𝑾)

Apprentissage Automatique – SVM -- 4

 Régularisation

Apprentissage Automatique – SVM -- 5

 Retour sur le sur-apprentissage

Sous-apprentissage

ln  = - 

Sur-apprentissage

Coefficients des polynômes

Très grandes valeurs!
Apprentissage Automatique – SVM -- 6
 Moindre carrés régularisés

Idée: on rajoute une pénalisation des grandes valeurs des

paramètres à la fonction de coût:
L( W)   ( F (x i , W)  yi ) 2   || W ||2
N

i 1
Coût d’attache
aux données
Paramètre de
Dont l’optimum exact est alors: régularisation

Si on pénalise les grandes valeurs des coefficients du

polynôme, on obtient une fonction moins « zigzagante »

Apprentissage Automatique – SVM -- 7

 Effet de la régularisation

Sous-apprentissage

ln  = - 

Sur-apprentissage

Apprentissage Automatique – SVM -- 8

 Régularisation: E RMS vs. ln( )
N
E RMS (w )   ( F (x i , w )  yi ) 2
1
2 i 1

Apprentissage Automatique – SVM -- 9

 Régularisation: E RMS vs. M
N
E RMS (w )   ( F (x i , w )  yi ) 2
1
2 i 1

Apprentissage Automatique – SVM -- 10

 Influence de la quantité de données

Polynôme d’ordre 9

N = 10

C’est aussi un moyen de

contrôler la régression

Apprentissage Automatique – SVM -- 11

 Compromis Biais-Variance (rappel)

On peut montrer:

E(erreur prédiction) = bruit2 + biais2 + variance

Erreur Erreur due aux Erreur due à la

incompressible mauvaises variabilité des
due à la nature hypothèses sur données
du problème les données d’apprentissage

L’erreur de généralisation est un compromis entre

bonnes hypothèses sur les données et qualité des
données d’apprentissage

Apprentissage Automatique – SVM -- 12

 Erreur de généralisation (rappel)
• Structure
• Biais: écart entre hypothèse de modèle et « vraie » distribution
des données
• Variance: écarts générés par différents jeux d’apprentissage.

• Deux phénomènes à contrôler

• Simplisme: modélisation trop grossière pour rendre
compte de la variété des données
• Biais++, Var –
• Erreur d’apprentissage et de test grandes
• Sur-apprentissage (« Overfitting »): modèle trop
complexe se spécialisant sur les données d’apprentissage
• Biais--, Var++
• Ecart entre erreur d’apprentissage et erreur de test

Apprentissage Automatique – SVM -- 13

 Classification et Régression

y  R(x) Estimation d’une

fonction satisfaisant
des contraintes à
partir des données

Apprentissage Automatique – SVM -- 14

 Classification et Régression

y  D(x) Estimation d’une

fonction satisfaisant
des contraintes à
partir des données

-1

Apprentissage Automatique – SVM -- 15

 Trois critères à ne pas confondre

• Risque ou erreur empirique

N
E train (w, D )  1
N  {F (x i , w )  yi }
i 1

• Erreur de généralisation (ou de test, ou idéale…)

E (w )  EX ,Y F (x, w )  y

• Critère à optimiser (forme assez générique)

N
L (w,D )  1
N  l ( F (x i , w ), yi )  r (w )
i 1

Régularisation
Adéquation aux données
Apprentissage Automatique – SVM -- 16
 Validation croisée

Apprentissage Automatique – SVM -- 17

 Validation croisée

• Permet d’estimer l’erreur de généralisation à partir des

données d’apprentissage (« astuce »)
• Principe:
• Division des données en k sous ensembles (« fold »)
• Choix d’une partie comme ensemble de validation fictif, les autres
comme train
• Apprentissage sur l’ensemble train
• Estimation des erreurs sur validation

• On fait tourner l’ensemble de validation sur chacune des parties

• L’erreur de généralisation estimée est la moyenne des erreurs sur

chaque ensemble de validation

Apprentissage Automatique – SVM -- 18

 Stratégies de partitionnement

• k-fold
Données

Train Validation

• Leave-one-out

Apprentissage Automatique – SVM -- 19

 Validation croisée: pour quoi faire?

• Estimer la « vraie » erreur de prédiction (généralisation)

• Estimer la variance d’apprentissage (mais pas le biais)

• Réglage des « hyper-paramètres » (par ex. le coefficient de

régularisation)
• Recherche exhaustive ou par dichotomie (à voir en TD)

• Attention! il y a d’autres sources d’aléatoire qui ne relèvent pas de la

validation croisée
• Random forrests, Bagging
• Initialisation et optimisation des réseaux de neurones (gradient
stochastique)

Apprentissage Automatique – SVM -- 20

 « Support Vector Machines »

Apprentissage Automatique – SVM -- 21

 Deux types d’approches:
génératives vs. discriminatives
On estime directement
Objectif = modéliser les
distributions de données
puis les exploiter 𝑦 = 𝐷(𝒙)

Objectif = construire les

On calcule la frontière à meilleures frontières
partir des modèles
Le premier cours Aujourd’hui
Apprentissage Automatique – SVM -- 22
 Support Vector Machines

• Historique
• Principe: maximiser la marge de séparation d’un hyperplan
• Le cas séparable
• Le cas non séparable: les fonctions de perte (« hinge loss »)
• L’extension au cas non linéaire: les noyaux
• Parcimonie
• Les paramètres de contrôle

Apprentissage Automatique – SVM -- 23

 Historique du Machine Learning

Apprentissage Automatique – SVM -- 24

 Modèles linéaires de décision

Hypothèse = les données sont linéairement séparables.

• En 2D, par une droite
• En ND, par un hyperplan.

0  b   j 1 w j x
m j

0  b   j 1 w j x j
m
0  b   j 1 w j x j
m

Apprentissage Automatique – SVM -- 25

 Classifieur linéaire

• Equation de l’hyperplan séparateur

b  w.x  0

• Expression du classifieur linéaire (pour yi valant -1 et 1)

F (x; w )  sign (b  w.x)

• Erreur
N

 y .sign (b  w.x )  0
1
E test (w, L )  i i
N i 1

Apprentissage Automatique – SVM -- 26

 Quel hyperplan choisir?

Apprentissage Automatique – SVM -- 27

 Classifieur « Large margin »

marge
marge
Choisir l’hyperplan qui maximise la distance
aux points les plus proches
Apprentissage Automatique – SVM -- 28
 Support Vector Machines
• On cherche l’hyperplan qui maximise la marge.

x i positif ( yi  1) : xi  w  b  1
x i négatif ( yi  1) : x i  w  b  1

Pour les vecteurs de xi  w  b  1

support,
Distance entre point et | xi  w  b |
hyperplan: || w ||
Pour les « support vectors »:
wΤ x  b  1 1 1 2
 M  
Support vectors Margin M w w w w w

Apprentissage Automatique – SVM -- 29

 Principe du SVM (Large Margin)

• Maximiser la marge = distance des vecteurs à l’hyperplan

séparateur des vecteurs de supports
1
max 2
w
• Sous contraintes

yi (w  x i  b)  1 i
Le 1 est conventionnel.
• Les vecteurs de support vérifiant: N’importe quelle
constante >0 est valable.

yi ( w  x i  b )  1

Apprentissage Automatique – SVM -- 30

 Formulation du SVM
2
min w,b w
Tel que:
yi ( w  xi  b)  1 i
Si les données sont séparables
Problème d’optimisation quadratique
Avec contraintes linéaires

Problème d’optimisation quadratique classique

Mais avec beaucoup de contraintes! (autant que

d’exemples d’apprentissage)
Apprentissage Automatique – SVM -- 31
 Classification « Soft Margin »

2
min w,b w
Tel que:
yi ( w  xi  b)  1 i

Comment traiter le cas non linéairement séparable?

Apprentissage Automatique – SVM -- 32

 Classification « Soft Margin »

2
min w,b w
Tel que:
yi ( w  xi  b)  1 i

On aimerait obtenir une séparation robuste à

quelques données non séparées
Apprentissage Automatique – SVM -- 33
 Idée: « Slack variables »

2
min w,b w
tq:
yi ( w  xi  b)  1 i
Permet de relacher la
contrainte de
séparabilité pour
chaque exemple.
min w,b w  C i  i
2

slack variables
tq: (une par exemple)
yi ( w  xi  b)  1   i i
i  0
Apprentissage Automatique – SVM -- 34
 « Slack variables »

min w,b w  C i  i
2

Tel que:
yi ( w  xi  b)   i  1 i
i  0

Relâchement de la contrainte

Apprentissage Automatique – SVM -- 35

 Utilisation des « Slack variables »

Compromis entre marge et

marge
pénalisation de la contrainte

Valeur du
min w,b w  C i  i
2 relâchement de la
contrainte
tq
yi ( w  xi  b)  1   i i
Contrainte autorisée
i  0 à être relachée

Apprentissage Automatique – SVM -- 36

 Soft margin SVM

min w,b w  C i  i
2

Tel que
yi ( w  xi  b)  1   i i
i  0

On garde un problème quadratique!

Mais avec un très grand nombre de variables+contraintes

Apprentissage Automatique – SVM -- 37

 Autre formulation

min w,b w  C i  i
2

tq:  i  max(0,1  yi ( w  xi  b))

yi ( w  xi  b)  1   i i
i  0

min w,b w  C i max(0,1  yi ( w  xi  b))

2

Problème d’optimisation non contraint

 Autres méthodes d’optimisation (descente de gradient)

Apprentissage Automatique – SVM -- 38

 Interprétation du « Soft Margin SVM »

min w,b w  C i max( 0,1  yi ( w  xi  b))

2

On retrouve la formulation:
N
Loss (w, D )  1
N  l ( F (x i , w ), yi )  r (w )
i 1

Avec
1
r (w )  w
2

C
l ( F (x i , w ), yi )  max(0,1  yi (w.x i  b))

Le SVM est un cas particulier du formalisme:

« erreur empirique + régularisation »
Apprentissage Automatique – SVM -- 39
 Autres Fonctions de coût

0/1 loss:
l ( y, y ' )  1 yy '  0 Hinge: l ( y, y ' )  max(0,1  yy ' )
Squared loss: l ( y, y ' )  ( y  y ' ) 2 Exponential: l ( y, y ' )  exp( yy ' )

Apprentissage Automatique – SVM -- 40

 Forme duale du SVM

• Problème d’optimisation sous contrainte

Pour simplifier l’expression des calculs

𝒘 2
Primal argmin𝐰 + 𝐶 ෍ 𝜉𝑖 Multiplicateurs de Lagrange
2
𝑖
𝑠. 𝑡. ∀𝑖, 𝑦𝑖 (𝒘. 𝒙𝑖 +𝑏) ≥ 1 − 𝜉𝑖 𝛼𝑖

𝜉𝑖 ≥ 0 𝛽𝑖
Dual (Lagrangien)
𝐿 𝒘, 𝝃, 𝜶, 𝜷
𝒘 2
= + ෍ 𝐶𝜉𝑖 − 𝛼𝑖 𝑦𝑖 (𝒘. 𝒙𝑖 +𝑏) − 1 + 𝜉𝑖 − 𝛽𝑖 𝜉𝑖
2
𝑖
𝑠. 𝑡. ∀𝑖, 𝛼𝑖 ≥ 0, 𝛽𝑖 ≥ 0
Apprentissage Automatique – SVM -- 41
 Forme duale du SVM

• Lagrangien
Maximisation dans le dual!

1
𝐿 𝛼 = ෍ 𝛼𝑖 − ෍ 𝛼𝑖 𝛼𝑗 𝑦𝑖 𝑦𝑗 𝒙𝑗 . 𝒙𝑗
2
𝑖 𝑖,𝑗

𝑠. 𝑡. ∀𝑖, 0 ≤ 𝛼𝑖 ≤ 𝐶
On garde un
pb. quadratique
Dual des contraintes « slack »
Solution optimale (conditions de Kuhn-Tucker): 𝛼𝑖 𝑦𝑖 𝑤 𝑇 𝑥𝑖 − 1 + 𝜉𝑖 = 0

Interprétation: 𝛼𝑖 = 0 si la contrainte est satisfaite (bonne classification)

𝛼𝑖 > 0 si la contrainte n’est pas satisfaite (mauvaise

classification)
Apprentissage Automatique – SVM -- 42
 Parcimonie du SVM

• Seuls certains 𝛼 sont non nuls = autre manière de définir

les vecteurs de support.
Optimalité = 𝜶𝒊 𝒚𝒊 𝒘𝑻 𝒙𝒊 − 𝟏 + 𝝃𝒊 = 𝟎
Direction de l’hyperplan séparateur 𝒘 = σ𝑖 𝛼𝑖 𝑦𝑖 𝒙𝑖
Y

𝑤𝑇 𝑥 + 𝑏 = 0

Ne contribuent pas au Contraintes actives

calcul de l’hyperplan 𝛼>0
= « Support vector »
Contraintes Inactives
𝛼=0
X

Apprentissage Automatique – SVM -- 43

 Données non linéairement séparables

• Transformation non linéaire 𝜙(𝒙) pour séparer linéairement les

données d’origine

𝑥2
𝑥2 = 𝑥12

𝑥1 𝑥1

𝜙(𝒙) = Transformation polynomiale

Apprentissage Automatique – SVM -- 44

 Données non linéairement séparables

• Transformation non linéaire 𝜙(𝒙) pour séparer linéairement les

données d’origine

Coordonnées polaires
𝑥2
𝜃

𝑥1

𝜙(𝒙) = Transformation polaire

Apprentissage Automatique – SVM -- 45

 Retour sur la formulation duale du SVM

Lagrangien
1
max ෍ 𝛼𝑖 − ෍ 𝛼𝑖 𝛼𝑗 𝑦𝑖 𝑦𝑗 𝒙𝑖 𝒙𝑗
𝛼 2
𝑖 𝑖,𝑗
Produit scalaire
tq ∀𝑖, 0 ≤ 𝛼𝑖 ≤ 𝐶 uniquement

Apprentissage Automatique – SVM -- 46

 « Kernel trick »

1
max ෍ 𝛼𝑖 − ෍ 𝛼𝑖 𝛼𝑗 𝑦𝑖 𝑦𝑗 𝐾(𝒙𝑖 , 𝒙𝑗 )
𝛼 2
𝑖 𝑖,𝑗
Noyau
tq ∀𝑖, 0 ≤ 𝛼𝑖 ≤ 𝐶
Le noyau 𝐾 est un produit scalaire dans l’espace
transformé:
𝐾 𝒙𝑖 , 𝒙𝑗 = 𝜙 𝒙𝑖 𝑇 𝜙(𝒙𝑗 )

Il est uniquement nécessaire de connaître la similarité

entre données pour introduire la non linéarité dans le
problème (avec des conditions…)

Apprentissage Automatique – SVM -- 47

 Utilisation de noyaux dans les SVM

• Permet d’introduire des mesures de similarités propres au domaine

étudié et sans avoir à gérer la complexité de la transformation

• Permet de séparer modélisation = noyau de la classification et SVM

(optimisation)

• Définit la fonction de classification à partir de noyaux « centrés » sur

les vecteurs de support

F 𝒙, 𝒘 = 𝑏 + ෍ 𝛼𝑖 𝑦𝑖 𝑲(𝒙𝑖 , 𝒙)
𝑖

Apprentissage Automatique – SVM -- 48

 Noyaux courants

• Polynômes de degrés supérieurs à d

𝐾 𝒙, 𝒚 = 𝒙. 𝒚 + 1 𝑑

Paramètres à définir
• Noyau gaussien = degré de liberté
supplémentaire

𝒙−𝒚 𝑇 𝒙−𝒚
𝐾 𝒙, 𝒚 = exp −
2𝜎 2

• Intersection d’histogrammes

𝐾 𝒙, 𝒚 = ෍ min(𝑥 𝑖 , 𝑦 𝑖 )
𝑖

Apprentissage Automatique – SVM -- 49

 Résumé sur SVM
• Une formulation optimale quadratique du problème de classification
binaire:
• Primal: optimisation d’un critère empirique + régularisation
• Dual: permet d’introduire parcimonie et « kernel trick »
 plusieurs manières d’optimiser

• Les solutions s’expriment comme des combinaisons linéaires

éparses de noyaux:

F 𝒙 = 𝑏 + ෍ 𝛼𝑖 𝑦𝑖 𝑲(𝒙𝑖 , 𝒙)
𝑖
où 𝛼𝑖 >0 seulement pour les vecteurs de support, 0 sinon.

• En pratique, ce qu’il faut régler:

• Le coefficient de régularisation: C
• Le type de noyau et ses caractéristiques
• Les paramètres de l’optimiseur
Apprentissage Automatique – SVM -- 50
 Multiclasse

Apprentissage Automatique – SVM -- 51

 Différents types de classification

• Binaire
A   1,1
• Multi classe A  1,2...L

• Détection (quoi et où) A  1,2...L R 4

• Caractérisation des données:

• Rejet A  1,2...L, ambigu,inconnu
• Anomalie

Apprentissage Automatique – SVM -- 52

 Hypothèses multiples

• Toutes les classes/hypothèses ne se valent pas

• Classes plus rares que d’autres (non équilibrées)
• Coût d’une erreur de classification dépend des classes (Zèbre vs.
Gazelle vs. Lion)

• Deux stratégies:
• Optimiser un critère multi-hypothèse dans l’apprentissage
• Par exemple entropie dans arbre de décision, softmax dans réseaux de
neurones…
• Utiliser un ensemble de classifieurs binaires
• SVM, adaboost, perceptron…

Apprentissage Automatique – SVM -- 53

 Multiclasse à partir de classifieurs

• Comment passer d’une classification binaire à N classes?

• Plusieurs techniques:
• One vs Rest
• One vs One (ou All vs All)

• OVO:
• On apprend autant de classifieurs que de paires de classes (N(N-1)/2)
• Classification = choix de la classe ayant le plus de votes
• Pb: peut être indécidable dans certains cas

• OVR:
• On apprend un classifieur par classe
• Classification = choix de la classe ayant le meilleur score
• Pb: déséquilibre des données entre classe cible et « reste »

Apprentissage Automatique – SVM -- 54

 Evaluation du multi-classe

• Erreur globale:
nombre d'échantillons mal classés
𝐸𝑟𝑟 =
nombre d'échantillons testés

• Matrice de confusion:
conf 𝑖, 𝑗 =probabilité de classer comme i | vraie classe est j
estimée sur données de test

• Risque ou coût moyen

R = ෍ ෍ 𝜆(𝑖, 𝑗)conf 𝑖, 𝑗 𝑝(𝑗)
𝑗 𝑖
où 𝜆(𝑖, 𝑗) est le coût de décider 𝑖 lorsque 𝑗 est vrai

Apprentissage Automatique – SVM -- 55

 A retenir

• Régularisation
• Un moyen de contrôler le compromis biais-variance

• SVM
• Un algorithme optimal et flexible qui permet de traiter un grand nombre
de configurations de données (en dimension raisonnable)

• Validation croisée
• Un moyen empirique d’estimer l’erreur de généralisation
• Une technique pour optimiser les hyper-paramètres (par ex. ceux du
SVM)

• Multi-classe
• Un problème qui peut s’exprimer et se résoudre de différentes manières

Apprentissage Automatique – SVM -- 56