138
Support Vector Machines
(SVM)
139
Introduction
1. Classification binaire –Séparation linéaire
[Link] de la marge (I) –Formulation initiale
[Link] de la marge (II) –Formulation duale
Plan [Link] de la séparation imparfaite –Soft Margin
[Link] noyau –Séparation non linéaire
[Link] aux problèmes multi classes
[Link] –Avantages et inconvénients
SVM : Introduction 140
Les machines à vecteurs de support ont été inventées par [Link] et ses collègues dans
les années 1970 en Russie et est devenu connu de l'Occident en 1992,
Les SVM sont des classifieurs linéaires qui consistent à trouver un hyperplan à séparer
deux classes de données, positives et négatives.
Les fonctions noyau (Kernel functions) sont utilisées pour la séparation non linéaire
SVM est fondé sur une base théorique rigoureuse, mais effectue également la
classification avec plus de précision que la plupart des autres méthodes, en particulier pour
des données de grande dimension.
Etapes de formulation de SVM
1 2 3 4
Formulation initiale Convertir SVM à Tolérer des erreurs Permettre
de SVM une forme qu’on • Soft margin l’hyperplan non
• Primal Form peut résoudre linéaire
• Dual form(formulation • Kernel functions
duelle)
2025/11/20 141
Etapes de formulation de SVM
1 2 3 4
Formulation initiale Convertir SVM à Tolérer des erreurs Permettre
de SVM une forme qu’on • Soft margin l’hyperplan non
• Primal Form peut résoudre linéaire
• Dual form(formulation • Kernel functions
duelle)
2025/11/20 142
SVM : Classification Binaire: Concepts de base 143
Soit l’ensemble de données d’entrainement D suivant:
𝒙𝟏 , 𝑦 , 𝒙𝟐 , 𝑦 , … … , 𝒙𝒏 , 𝑦
Où 𝒙𝒊 = 𝑥 , 𝑥 , … … . . , 𝑥 est un vecteur input
et 𝑦 est sa classe label (target) , 𝑦 є −1,1
1: classe positive et -1: classe négative
SVM trouve une fonction linéaire qui sépare les données en deux classes
𝑓 𝒙 = 𝒘𝑻 𝒙 + 𝑏 𝑎𝑣𝑒𝑐 𝑤: 𝑣𝑒𝑐𝑡𝑒𝑢𝑟 𝑑𝑒𝑠 𝑝𝑎𝑟𝑎𝑚è𝑡𝑟𝑒𝑠
1 𝑠𝑖 𝒘𝑻 𝒙𝒊 + 𝑏 ≥ 0
𝑦 =
−1 𝑠𝑖 𝒘𝑻 𝒙𝒊 + 𝑏 < 0
SVM : Hyperplan: classifieur binaire 144
Quand les données sont linéairement séparables
L’hyperplan qui sépare les données d’entrainement en deux classes ( dites positive et
négatives) est
𝑯: 𝒘𝑻 𝒙 + 𝑏=0
Il est aussi appelé la frontière de décision
Plusieurs hyperplans sont possibles, quel est le meilleur?
𝒘𝑻 𝒙 + 𝑏=0
SVM : Hyperplan- Illustration 145
SVM : Hyperplan- Illustration 146
SVM : Recherche de la solution optimale: Quel Hyperplan choisir? 147
Le meilleur hyperplan est celui qui maximise la marge entre les deux classes
Cet hyperplan minimise l’erreur de classification et réduit l’overfitting
Trouver la
distance m
Class + m=?
Class -
m
147
SVM : Hyperplan avec la marge maximale 148
Pour un hyperplan H quelconque d’équation 𝑯: 𝒘𝑻 𝒙 + 𝑏=0, il existe deux hyperplans
parallèles et équidistants de H qui sont
𝑯+: 𝒘𝑻 𝒙 + 𝑏=1 H+ sur le bord de la classe positive
𝑯−: 𝒘𝑻 𝒙 + 𝑏=-1 H- sur le bord de la classe négative
Maximiser m
m est la distance
Class + entre H+ et H-
Class -
m
148
SVM : Les points Support Vecteurs 149
Les points où «s’appuient» les droites «marges» sont les
«vecteurs de support». Si on les retire de l’échantillon, la
solution est modifiée.
• Plusieurs zones sont définies dans l’espace de
représentation
f(x) = 0, on est sur la frontière
f(x) > 0, classe «+»
f(x) < 0, classe «-»
f(x) = +1 ou -1, on est sur les droites délimitant des vecteurs de
support
SVM : Calculer la marge : Règle 150
X*
wTx +b = 0
X – Vector
W
W – Normal Vector
b – Scale Value
Quelle est la distance orthogonale entre un point 𝒙∗ quelconque à une droite wTx+b= 0?
𝑤 𝒙∗ + 𝑏 𝑤 𝒙∗ + 𝑏
𝑑(𝒙∗ ) = =
𝑤
∑ 𝑤
150
SVM : calculer la marge 𝒎 151
𝑚 = 𝑑 𝑥 ,𝐻 + 𝑑 𝑥 ,𝐻
𝒙 𝒙 𝟐
= + = + 𝒎=
𝒘
Maximiser 𝒎 revient à
minimiser 𝒘
𝑯+: 𝒘𝑻 𝒙 + 𝑏=1
𝑯−: 𝒘𝑻 𝒙 + 𝑏=-1
SVM : Un problème d’optimisation: Formulation initiale 152
Il s’agit d’un problème d’optimisation quadratique avec contrainte
1
𝑚𝑖𝑛𝑖𝑚𝑖𝑠𝑒𝑟 𝑤
2
Sous contrainte 𝑦 𝑤 𝑥 + 𝑏 ≥ 1 ∀𝑖
𝒚𝒊 𝒘𝑻 𝒙𝒊 + 𝒃 ≥ 𝟏 ∀𝒊 𝑠𝑖𝑔𝑛𝑖𝑓𝑖𝑒 𝑞𝑢𝑒
𝑤 𝑥 + 𝑏 ≥ 1 pour 𝑦 =1
𝑤 𝑥 + 𝑏 ≤ −1 pour 𝑦 =-1
SVM : Formulation initiale: Inconvénients
1
𝑚𝑖𝑛𝑖𝑚𝑖𝑠𝑒𝑟 𝑤
2
Sous contrainte 𝑦 𝑤 𝑥 + 𝑏 ≥ 1 ∀𝑖
(1)Les algorithmes d’optimisation numérique (prog. quadratique) ne sont pas opérationnels
dès que le nombre de paramètres «p» est grand (> quelques centaines). Ce qui arrive souvent
dans le traitement des données complexes (textmining, image, …) (peu d’exemples, beaucoup
de descripteurs)
(2)Cette écriture ne met pas en évidence la possibilité d’utiliser des fonctions «noyau» qui
permettent d’aller au-delà du cadre des classifieurs linéaires
Etapes de formulation de SVM
1 2 3 4
Formulation initiale Convertir SVM à Tolérer des erreurs Permettre
de SVM une forme qu’on • Soft margin l’hyperplan non
• Primal Form peut résoudre linéaire
• Dual form(formulation • Kernel functions
duale)
2025/11/20 154
Expression duale Un problème d’optimisation possède Une forme duale si on
évolue dans un Espace convexe. ce qui est le cas, On passe
passage au Lagangien alors par le Lagrangien
1
𝑚𝑖𝑛𝑖𝑚𝑖𝑠𝑒𝑟 𝑤
Le problème initial… 2
(1)
Sous contrainte 𝑦 𝑤 𝑥 + 𝑏 ≥ 1 ∀𝑖 = 1, … , 𝑛
(2)
𝑚𝑖𝑛 𝐿 𝑤, 𝑏, 𝛼 = 𝑤 −∑ 𝛼 ( 𝑦 𝑤 𝑥 + 𝑏 − 1)
devient sous sa forme duale La théorie de l'optimisation dit qu'une solution optimale à (1) doit satisfaire
cinq conditions, appelées conditions de Karush-Kuhn-Tucker,
• 𝛼 ≥0 sont les multiplicateurs de Lagrange
• avec 𝛼 (1− 𝑦 𝑤 𝑥 + 𝑏 )=0
• et (𝑦 𝑤 𝑥 + 𝑏 − 1) ≥ 0
• =𝑤−∑ 𝛼 𝑦 𝑥 =0
• =∑ 𝛼 𝑦 =0
155
En introduisant les informations issues de l’annulation des dérivées
partielles du Lagrangien, on obtient une optimisation ne dépendant
La forme duale que des multiplicateurs 𝜶𝒊
La nouvelle fonction objective est exprimée uniquement par i (Lagrange
multipliers)
Remplacer w par sa formule issue de la dérivée
Pour plus de details sur le fondement mathématique, visiter ce lien
[Link]
vector-machines-for-beginners-duality-problem/
L
(3)
sachant que
156
Des points supports aux Puisque les expressions primales et duales
coefficients de l’hyperplan (I) sont deux facettes du même problème, on doit
pouvoir passer de l’un à l’autre.
A partir de la dérivée partielle du Lagrangien =𝑤−∑ 𝛼 𝑦 𝑥 =0 𝑤=∑ 𝛼 𝑦 𝑥
par rapport à w
Seuls les points supports participent au calcul des coefficients, puisque
ce sont les seuls pour lesquels (𝛼 > 0)
On peut obtenir b (pour les (𝛼 > 0)) 𝛼 (1− 𝑦 𝑤 𝑥 + 𝑏 )=0
1−𝑦 𝑤 𝑥
𝑏=
𝑦
157
Charactéristiques de la Solution du problème dual
Plusieurs i sont nuls
w est une combinaison linéaire d’un petit nombre de i
xi avec i non nuls sont appelés support vectors (SV)
L’hyperplan de décision est determiné uniquement par SV
Soient SV les indices du s support vectors.
w est exprimé ainsi
𝒘= 𝜶𝒊 𝒚𝒊 𝒙𝒊
𝒊∈𝑺𝑽
2025/11/20 158
Interpretation Géométrique
Class 2
10=0
8=0.6
7=0
2=0
5=0
1=0.8
4=0
6=1.4
9=0
3=0
Class 1
2025/11/20 159
Trouver les coefficients de l’hyperplan optimal
Dans cet exemple β 𝑐′𝑒𝑠𝑡 𝑙𝑒 𝑣𝑒𝑐𝑡𝑒𝑢𝑟 𝑑𝑒 𝑝𝑎𝑟𝑎𝑚è𝑡𝑟𝑒𝑠 𝑤
𝑤 = β 𝑒𝑡 𝑏 = β
160
Formule finale d’hyperplan H
Equation d’hperplan de decision:
𝐻: 𝑤 𝑥 + 𝑏 = 𝑦 𝛼 𝑥 𝑥+𝑏
∈
Testing:
Soit z une instance de test
𝒔𝒊𝒈𝒏 𝑤 𝑧 + 𝑏 = 𝒔𝒊𝒈𝒏 ∑ ∈ 𝑦 𝛼 𝑥 𝑧+𝑏
Si le résultat est positif alors z est classifié dans la classe
positive.
Sinon, z est classée négative
2025/11/20 161
162
Formulation Duale
Cette écriture est complètement cohérente avec la formulation primale
Elle met mieux en lumière le rôle des points supports avec les pondérations 𝛼
Elle met en lumière également le rôle fondamental du produit scalaire <xi,xi’> dans les calculs, ce sera très
important par la suite (cf. fonctions «noyau»)
Dans les très grandes dimensionnalités (‘’p’’ très élevé, ‘’n’’ relativement faible –traitement d’images,
textmining), cette écriture rend les calculs plus simples pour les techniques d’optimisation
2025/11/20 163
Etape Suivante
1 2 3 4
Convertir SVM à Tolérer des Permettre SVM multi classes
une forme qu’on erreurs l’hyperplan non
peut résoudre • Soft margin linéaire
• Dual form(forme • Kernel functions
duelle)
2025/11/20 164
Rappel
Quand les données sont linéairement séparables, le problème était de
1
𝑚𝑖𝑛𝑖𝑚𝑖𝑠𝑒𝑟 𝑤
2
Avec la contrainte 𝑦 𝑤 𝑥 + 𝑏 ≥ 1 ∀𝑖
Pour réduire le problème d’overfitting , il est judicieux de permettre des
erreurs
165
Tolérer les erreurs dans la solution
Nous tolérons “l’erreur” i en classification; la tolerance à l’erreur doit figurer
dans l’output de la fonction wTx+b
i approxime le nombre des exemples mal classifies,
Class 2
Class 1
2025/11/20 166
Soft Marge d’Hyperplan
Si nous minimisons ii, i peut être trouvé par
i sont “slack variables” en optimisation
Note que i=0 si pas d’erreur pour xi
Nous minimisons
C : constante cost parameter
Le problème d’optimization devient
Avec la contrainte
2025/11/20 167
Formulation de l’optimisation
Formulation Primale
Sous la contrainte
Formulation duale
2025/11/20 168
Etape Suivante
1 2 3 4
Convertir SVM à Tolérer des Permettre La SVM multi
une forme qu’on erreurs l’hyperplan non classes
peut résoudre • Soft margin linéaire
• Dual form(forme • Kernel functions
duelle)
2025/11/20 169
Extension au frontière Non linéaire
Et si les données ne sont pas linéairement séparables?
Comment généraliser le SVM pour le cas non linéaire?
170
Extension au frontière Non linéaire
Pour couvrir la separation non linéaire, les mêmes
formules et techniques sont utilisées,
Il faut juste transformer les données en un autre espace
(généralement de plus grande dimension),
Ce qui permet une séparation linéaire dans le nouvel
espace de données transformé,
Input space: l’espace des données originales xi
Feature space: L’espace des données transformées (xi)
171
Extension au frontière Non linéaire- Illustration
172
Espace transformé
L’idée de base est de transformer les données d’Entrée de
l’espace X vers l’espace de features F via une fonction non
linéaire 𝜙,
Après la transformation, les données d’entrée originales
𝒙𝟏 , 𝑦 , 𝒙𝟐 , 𝑦 , … . , 𝒙𝒏 , 𝑦 devient:
𝝓(𝒙𝟏 ), 𝑦 , 𝝓(𝒙𝟐 ), 𝑦 , … . , 𝝓(𝒙𝒏 ), 𝑦
173
Transformation des données
( )
( ) ( )
( ) ( ) ( )
(.) ( )
( ) ( )
( ) ( )
( ) ( )
( ) ( ) ( )
( )
( )
Input space Feature space
Note: feature space is of higher dimension
than the input space in practice
Dans cet exemple, l’espace transformé est aussi 2-D,
Mais, en general, le nombre de dimensions dans l’espace
des features est plus grand que dans l’espace d’entrée,
2025/11/20 174
Transformation des données
Le problème d’optimisation devient:
minimiser
Sous la contrainte 𝑦 𝑤 𝜙 𝑥 +𝑏 ≥1−𝜉 , 𝜉 ≥0
Sa forme duale correspond à:
La fonction de décision devient:
𝐻: 𝑤 𝜙 𝑥 + 𝑏 = 𝑦𝛼𝜙 𝑥 𝜙 𝑥 +𝑏
∈ 175
Astuce noyau (the Kernel Trick)
La transformation d’espace est très couteuse, puisqu’on doit calculer la
function Ф pour chaque donnée xi,
Cependant, on peut s’en passer du clacul explicite de Ф en l’exprimant sous
forme d’un produit scalaire
On définit alors la fonction kernel K par
176
Un exemple pour (.) et K(.,.)
Suppose (.) est donné comme suit
Un produit scalaire dans l’espace feature est
Alors, si on définit la function kernel comme suit on n’a plus besoin de
calculer (.) explicitement
L’utilisation de kernel function (function noyau) pour éviter le calcul de (.)
explicitement est connu par “kernel trick” (l’astuce de noyau)
2025/11/20 177
Exemples de Kernel Functions
kernel polynomial de degré d
Radial basis function (RBF) kernel avec largeur
Sigmoid kernel with parameter and
178
Non-linear SVMs: Feature spaces
General idea: the original input space can always be mapped to
some higher-dimensional feature space where the training set is
separable:
Φ: x → φ(x)
2025/11/20 179
Exercice
Suppose we have 5 one-dimensional data points
x1=1, x2=2, x3=4, x4=5, x5=6, with 1, 2, 6 as class 1 and 4, 5 as class 2 y1=1,
y2=1, y3=-1, y4=-1, y5=1
We use the polynomial kernel of degree 2
K(x,y) = (xy+1)2
C is set to 100
We first find i (i=1, …, 5) by
2025/11/20 180
Exemple
By using a QP (Quadratic Programming) solver, we get
1=0, 2=2.5, 3=0, 4=7.333, 5=4.833
Note that the constraints are indeed satisfied
The support vectors are {x2=2, x4=5, x5=6}
The discriminant function is
b is recovered by solving f(2)=1 or by f(5)=-1 or by f(6)=1, as x2 and x5 lie on
the line and x4 lies on the line
All three give b=9
2025/11/20 181
Example
Value of discriminant function
class 1 class 2 class 1
1 2 4 5 6
2025/11/20 182
Degree of Polynomial Features
X^1 X^2 X^3
X^4 X^5 X^6
2025/11/20 183
Etape Suivante
1 2 3 4
Convertir SVM à Tolérer des Permettre SVM multi classes
une forme qu’on erreurs l’hyperplan non
peut résoudre • Soft margin linéaire
• Dual form(forme • Kernel functions
duelle)
2025/11/20 184
2025/11/20 185
2025/11/20 186
Bilan
Avantages
•Capacité à traiter de grandes dimensionnalités (#variables élevé)
•Robuste même quand le rapport ‘’#observations / #variables’’ est inversé
•Traitement des problèmes non linéaires avec le choix des noyaux
•Non paramétrique
•Robuste par rapport aux points aberrants (contrôlé avec le paramètre C)
•#points supports donne une bonne indication de la complexité du problème traité
•Souvent performantdans les comparaisons avec les autres approches
•Paramétrage permet de la souplesse (ex. résistance au sur-apprentissage avec C)
Inconvénients
•Difficulté à identifier les bonnes valeurs des paramètres(et sensibilité aux paramètres)
•Difficulté à traiter les grandes bases avec #observations très élevé (capacité mémoire avec matrice de Gram –si
implémentation naïve, temps de calcul)
•Problème lorsque les classes sont bruitées (multiplication des points supports)
•Pas de modèle explicite pour les noyaux non linéaires (utilisation des points supports)
•Difficulté d’interprétations (ex. pertinence des variables)
•Le traitement des problèmes multi-classes reste une question ouverte
187