Support Vector Machine

Master ESA

Christophe Hurlin

Université d’Orléans

Septembre 2020

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 1 / 228
1. Introduction

Dé…nition (SVM)
Les machines à vecteurs de support ( support vector machine ou SVM), introduites par
Vladimir Vapnik (Vapnik (1995, 1998)), sont un ensemble de techniques d’apprentissage
supervisé destinées à résoudre des problèmes de classi…cation ou de régression.

Vapnik V.N. (1995). The Nature of Statistical Learning Theory. Springer.

Vapnik V.N. (1998). Statistical Learning Theory. John Wiley.

Varian H.R. (2014). Big Data: New Tricks for Econometrics. The Journal of Economic
Perspectives, 28(2), 3-27.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 2 / 228
1. Introduction

Remarque : Les SVM sont aussi appelés séparateurs à vastes marges.

Boser B.E, Guyon I.M., Vapnik V.N. (1992). A Training Algorithm for Optimal Margin
Classi…ers, Fifth Annual Workshop on Computational Learning Theory, pages 144–152.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 3 / 228
1. Introduction

Remarque : SVM et SVR

Dans le cas d’un problème de classi…cation, on parle de SVM (machine à vecteurs

de support)

Dans le cas d’une régression on parle de SVR (régression à vecteurs de support).

Dans la suite de ce cours, nous présenterons le problème de classi…cation, puis nous

étondrons au cas de la régression.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 4 / 228
1. Introduction

Les SVM reposent sur deux idées clés :

1 La notion de marge maximale

2 La notion de fonction noyau (kernel)

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 5 / 228
1. Introduction

Intuition des SVM : marge maximale

La marge est la distance entre la frontière (hyperplan) de séparation et les

observations les plus proches. Ces derniers sont appelés vecteurs supports.

Dans les SVM, la frontière de séparation optimale est choisie comme celle qui
maximise la marge.

Le problème consiste à trouver cette frontière séparatrice optimale à partir d’un

ensemble d’apprentissage.

la solution consiste à formuler le problème comme un problème d’optimisation

quadratique.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 6 / 228
1. Introduction

Intuition des SVM : kernel trick

Dans le cas où les données ne sont pas linéairement séparables, la deuxième idée
clé des SVM est de transformer l’espace de représentation des données d’entrées
en un espace de plus grande dimension (possiblement de dimension in…nie), dans
lequel il est probable qu’il existe une séparation linéaire.

L’astuce consiste à utiliser une fonction noyau qui ne nécessite pas la connaissance
explicite de la transformation à appliquer pour le changement d’espace.

Les fonctions noyau permettent de transformer un produit scalaire (calcul coûteux

dans un espace de grande dimension) en une simple évaluation ponctuelle d’une
fonction.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 7 / 228
1. Introduction

Bibliographie

Cristianini, N., and Shawe-Taylor, J. (2000). An Introduction to Support Vector Machines

and Other Kernel-Based Learning Methods. New York: Cambridge University Press.

Hastie, T., Tibshirani R., and Friedman J. (2009). The elements of statistical learning. Data
mining, inference, and prediction. 2nd ed. Springer.

Suykens J. & Vandewalle J. (1999). Least Squares Support Vector Machine Classi…ers.
Neural Processing Letters, 9(3), 293-300.

Suykens J., Van Gestel T., De Brabanter J., De Moor B. and Vandewalle J. (2002). Least
Squares Support Vector Machine. Singapore: World Scienti…c.

Vapnik V.N. (1995). The Nature of Statistical Learning Theory. Springer, First Edition.

Vapnik V.N. (1998). Statistical Learning Theory. John Wiley.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 8 / 228
1. Introduction

Autres notes de cours (liste non exhaustive)

Bousquet O. Introduction aux Support Vector Machines, CMA, Ecole Polytechnique.

Clemençon S.,Introduction à la Théorie de l’Apprentissage, Telecom Paris-Tech.

Rakotomalala R., Support Vector Machine, Université Lumière Lyon 2.

Rakotomamonjy A., Séparateurs à Vaste Marge Linéaires, INSA Rouen.

Revel A., Support Vector Machines, Université La Rochelle.

Zhao A., Support Vector Machines, Metis.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 9 / 228
1. Introduction

Sélection d’applications des SVM/SVR en risk management

Baesens,B., VanGestel,T., Viaene,S., Stepanova,M., Suykens,J., Vanthienen,J. (2003).

Benchmarking State-of-the-Art Classi…cation Algorithms for Credit Scoring. Journal of the
Operational Research Society, 54, 627-635.

Loterman G., Brown I., Martens D., Mues C. & Baesens B. (2012). Benchmarking
Regression Algorithms for Loss Given Default Modeling. International Journal of
Forecasting, 28(1), 161-170.

Tobback E., Martens D., Van Gestel T. & Baesens B. (2014). Forecasting Loss Given
Default Models: Impact of Account Characteristics and the Macroeconomic State. Journal
of the Operational Research Society, 65(3), 376-392.

Yao X., Crook J. & Andreeva G. (2015). Support Vector Regression for Loss Given Default
Modelling. European Journal of Operational Research, 240(2), 528-538.

Yao X., Crook J. & Andreeva G. (2017). Enhancing Two-Stage Modelling Methodology for
Loss Given Default with Support Vector Machines. European Journal of Operational
Research, 263(2), 679-689.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 10 / 228
1. Introduction

Le plan de ce chapitre est le suivant :

Section 2 : Intuition des SVM : les cas linéairement séparable
Section 3 : Formalisation du SVM
Section 4 : Soft margin
Section 5 : Kernel trick
Section 6 : Application du SVM sous SAS, R, Python et Matlab
Section 7 : Extensions du SVM
Sous section 7.1. SVM et scores
Sous section 7.2. SVM multiclasses
Sous section 7.3. Régressions à vecteurs de support (SVR)
Sous section 7.4. LS-SVM

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 11 / 228
 Section 2

Intuition des SVM

Le cas d’un échantillon linéairement séparable

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 12 / 228
2. Intuition des SVM

Objectifs

1 Comprendre l’intuition du SVM dans le cas d’un problème de classi…cation

2 Introduite la notion de classi…eur linéaire

3 Introduite la notion d’échantillon linéairement séparable

4 Introduire la notion de marge (margin)

5 Introduire la notion d’hyperplan séparateur

6 Introduire la notion de vecteurs de support (support vectors)

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 13 / 228
2. Intuition des SVM

Problème d’apprentissage

On s’intéresse à un phénomène f (déterministe ou stochastique) qui, à partir d’un

certain jeu d’entrées (prédicteurs, variables) x , produit une sortie (label, étiquette)
y = f (x ).

Le but est de retrouver f (inconnue) a partir d’un échantillon d’apprentissage

fxi , yi g , i = 1, ..., n.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 14 / 228
2. Intuition des SVM

Formalisation

Soit un couple de variables aléatoires (x , y ) à valeurs dans X Y.

On s’intéresse tout d’abord au cas de la classi…cation avec Y = f 1, 1g.

On peut étendre au cas card (Y ) = m > 2 ou Y = R (cas de la régression).

La variable X est vectorielle, avec dans le cas de prédicteurs réels X = Rd .

L’espace X est muni d’un produit scalaire.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 15 / 228
2. Intuition des SVM

Dé…nition (classi…eur et fonction de décision)

On cherche une fonction ( classi…eur) g : X ! f 1, 1g qui minimise la probabilité
d’erreur de classi…cation
Pr (g (x ) 6= y )
Plutôt que de construire g directement, on construit généralement une fonction de
décision h : X ! R et on y associe le classi…eur

g (x ) = sgn (h (x ))

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 16 / 228
2. Intuition des SVM

Dé…nition (classi…eur linéaire)

Un classi…eur linéaire (ou perceptron) est une fonction de la forme
(
1 si h (x ) 0
g (x ) = sgn (h (x )) =
1 si h (x ) < 0
avec
d
h (x ) = hω, x i + b = x 0 ω + b = ∑ ω j xj + b
j =1

et ω 2 Rd , b 2 R, h., .i désigne le produit scalaire.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 17 / 228
2. Intuition des SVM

Example (classi…eur linéaire)

On dispose d’un échantillon d’apprentissage avec 3 variables (X = R3 ) fyi , xi gni=1 et l’on
considère un classi…eur linéaire avec ω = (3, 2, 7) et b = 2 :

g (x ) = sgn (h (x )) 8 x = ( x 1 , x 2 , x 3 ) 2 R3
d
h (x ) = hω, x i + b = ∑ ωj xj + b = 3x1 + 2x2 + 7x3 2
j =1

Chaque individu peut alors être classi…é. Par exemple :

Individu A (y , x1 , x2 , x3 ) = (1, 0, 2, 4) h (x ) = 26 g (x ) = 1

Individu B (y , x1 , x2 , x3 ) = (1, 8, 1, 2) h (x ) = 38 g (x ) = 1

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 18 / 228
2. Intuition des SVM

Remarque : du fait des propriétés de la fonction sgn (.) , au sens strict, les points de
l’hyperplan ne sont pas classi…és en f 1, 1g
8
< 1
> si h (x ) > 0
g (x ) = sgn (h (x )) = 0 si h (x ) = 0 , x 2 H
>
:
1 si h (x ) < 0

mais généralement on les attribue à l’un ou l’autre des deux sous-espaces

(
1 si h (x ) 0
g (x ) = sgn (h (x )) =
1 si h (x ) < 0

Rappel : pour une variable continue, la probabilité d’être en un point est nulle.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 19 / 228
2. Intuition des SVM

Dé…nition (hyperplan séparateur)

Un hyperplan séparateur H sépare l’espace des données d’entrée X en deux
demi-espaces correspondant aux deux classes prévues pour y . Il est dé…ni par l’équation

h (x ) = 0

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 20 / 228
2. Intuition des SVM

Example (cas d = 2)
On considère le cas X = R2 et un classi…eur linéaire g (x ) dé…ni par ω = (1, 2) et
b= 1:
h (x ) = hω, x i + b = x1 + 2x2 1
(
1 si h (x ) = x1 + 2x2 1 0
g (x ) = sgn (h (x )) =
1 si h (x ) = x1 + 2x2 1 < 0
Par exemple :
h (0, 0) = 1 g (0, 0) = 1
1 1
h 1, =1 g 1, =1
2 2
L’hyperplan (droite) a¢ ne qui sépare X = R2 en deux demi-espaces correspondant
chacun à une classi…cation, est dé…ni par l’équation :

h (x ) = x1 + 2x2 1=0 8x = (x1 , x2 ) 2 R2

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 21 / 228
2. Intuition des SVM

1
h(x ,x )=0
1 2
Observati ons y=-1
Observati ons y=1

0.5
h(1;0.5)=1 g(1,0.5)=1
2
x

0 h(x ,x )=0
1 2
h(0,0)=-1 g(0,0)=-1

-0.5
-1 -0.5 0 0.5 1 1.5 2
x
1

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 22 / 228
2. Intuition des SVM

Example (cas d = 3)
On considère le cas X = R3 et un classi…eur linéaire g (x ) = sgn (h (x )) dé…ni par
ω = (1, 2, 3) et b = 2 :

h (x ) = hω, x i + b = x1 + 2x2 3x3 2

L’équation
h (x ) = x1 + 2x2 3x3 2 = 0, 8x = (x1 , x2 , x3 ) 2 R3
dé…nit un hyperplan qui sépare X = R3 en deux demi-espaces correspondant à une
classi…cation.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 23 / 228
2. Intuition des SVM

0
3
x

-1

-2
2
2
1
1
0
0
x -1 -1 x
2 1

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 24 / 228
2. Intuition des SVM

Classi…eur g (x ) = sgn (h (x ))
g (x ) = 1 g (x ) = 1
y = 1 Pas d’erreur g (y ) y = 1 > 0 g (x ) y = 1 < 0
y =1 g (x ) y = 1 < 0 Pas d’erreur g (x ) y = 1 > 0

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 25 / 228
2. Intuition des SVM

Remarque : la probabilité d’une erreur de classi…cation est égale à

Pr (g (x ) 6= y ) = Pr (h (x ) y 0) = Pr (g (x ) y = 1)

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 26 / 228
2. Intuition des SVM

Dé…nition (échantillon linéairement séparable)

Un échantillon S = f(x1 , y1 ) , . . . , (xn , yn )g 2 (X Y ) est linéairement séparable s’il
existe un classi…eur linéaire qui classe correctement toutes les observations de S.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 27 / 228
2. Intuition des SVM

On considère X = R2 avec
xi = (xi 1 , xi 2 ) et un échantillon
fxi , yi g pour i = 1, . . . , n.
On représente chaque triplet
(xi 1 , xi 2 , yi ) par un point dans le
repère (x1 , x2 )
Lorsque yi = 1 ( 1), l’observation
est représentée par un point bleu
(vert)

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 28 / 228
2. Intuition des SVM

Soit un classi…eur linéaire g (x )

associé à un hyperplan a¢ ne

h (x ) = hω, x i + b = 0

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 29 / 228
2. Intuition des SVM

Si toutes classi…cations g (x ) = 1 se
situent dans la zone bleue et toutes
les classi…cations g (x ) = 1 sont
dans la zone verte, il y aucune erreur
de classi…cation.
Il existe donc un classi…eur linéaire
qui classe correctement toutes les
observations de l’échantillon.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 30 / 228
2. Intuition des SVM

On dit que l’échantillon est

linéairement séparable

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 31 / 228
2. Intuition des SVM

En revanche, cet échantillon n’est

pas linéairement séparable

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 32 / 228
Introduction

En e¤et, il n’existe pas de classi…eur

linéaire permettant de classer
correctement toutes les observations

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 33 / 228
2. Intuition des SVM

Dans la première partie de ce cours (sections 2 et 3), nous supposerons que

l’échantillon est linéairement séparable.

Même dans ce cas simple, le choix de l’hyperplan séparateur n’est pas évident.

Problem

Remarque
Pour un échantillon linéairement séparable, il peut exister plusieurs classi…eurs linéaires
(i.e. plusieurs couples (ω, b )) dont les performances en apprentissage sont identiques
(sans erreur de classi…cation). Quel est alors le classi…eur optimal ?

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 34 / 228
2. Intuition des SVM

Quel est le classi…eur linéaire

optimal pour cet échantillon ?

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 35 / 228
2. Intuition des SVM

Est-ce celui-ci ?

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 36 / 228
2. Intuition des SVM

Est-ce celui-ci ?

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 37 / 228
2. Intuition des SVM

Est-ce celui-ci ?

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 38 / 228
2. Intuition des SVM

On doit se doter d’un critère d’optimalité pour sélectionner les hyperplans : c’est le
critère des marge optimales

Dé…nition (marge)
La marge M représente le double de la distance d du point le plus proche a l’hyperplan.

Idée du SVM : choisir l’hyperplan qui classi…e correctement les données et qui se trouve
le plus loin possible de tous les observations (exemples).

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 39 / 228
2. Intuition des SVM

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 40 / 228
2. Intuition des SVM

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 41 / 228
2. Intuition des SVM

De…nition (vecteurs supports)

Les vecteurs supports correspondent aux observations situées sur la marge.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 42 / 228
2. Intuition des SVM

Reprenons notre exemple : quel est

le classi…eur linéaire optimal ?

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 43 / 228
2. Intuition des SVM

Reprenons notre exemple : quel est

le classi…eur linéaire optimal ?

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 44 / 228
2. Intuition des SVM

Voici le classi…eur à marge optimale

ou SVM

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 45 / 228
2. Intuition des SVM

Voici la classi…cation associée à

l’hyperplan à marge optimale ou
SVM

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 46 / 228
2. Intuition des SVM

De…nition (Machine à Vecteurs de Support)

Dans le cas d’un échantillon linéairement séparable, la machine à vecteurs de support
(SVM) est le classi…eur linéaire (ω , b ) qui classe parfaitement toutes les observations
sur l’échantillon d’apprentissage et qui est associé à la plus grande marge.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 47 / 228
 Concepts clés

1 Classi…eur linéaire et fonction de décision.

2 Hyperplan séparateur.

3 Echantillon linéairement séparable.

4 Marge.

5 Vecteurs de support.

6 Machine à vecteurs de support.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 48 / 228
 Section 3

Formalisation du SVM

Le cas d’un échantillon linéairement séparable

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 49 / 228
3. Formalisation du SVM

Objectifs

1 Comprendre la notion de distance d’un point à un hyperplan

2 Comprendre la notion d’hyperplan (séparateur) canonique.

3 Dé…nir la notion de marge et de vecteurs de support.

4 Comprendre la notion d’hyperplan canonique optimal.

5 Dé…nir le programme primal du SVM.

6 Dé…nir le programme dual du SVM.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 50 / 228
3. Formalisation du SVM

Rappels
Soient deux vecteurs sur Rd , u = (u1 , . . . , ud )0 et v = (v1 , . . . , vd )0
Produit scalaire
d
8 (u, v ) 2 Rd , Rd , hu, v i = ∑ ui vi
i =1
Norme euclidienne
v
q u d
u
8u 2 Rd , ku k = hu, u i = t ∑ ui2
i =1

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 51 / 228
3. Formalisation du SVM

Rappels

Orthogonalité : u et v sont orthogonaux si

hu, v i = 0

La droite normale à un plan en un point est la droite orthogonale à ce plan en ce

point.

Tout vecteur directeur de cette droite est appelé vecteur normal à la surface en ce
point.

Par convention, le vecteur normal a une norme unitaire.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 52 / 228
3. Formalisation du SVM

Source : http://www.methodemaths.fr

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 53 / 228
3. Formalisation du SVM

Notations

On considère une fonction de décision donnée par

h (x ) = hω, x i + b

avec ω 2 Rd et b 2 R.

L’équation h (x ) = 0 dé…nit l’hyperplan séparateur H dans Rd .

Par dé…nition de l’hyperplan séparateur, 8x0 2 H

h (x0 ) = hω, x0 i + b = 0 () hω, x0 i = b

Classi…eur associé
(
1 si h (x ) 0
8x 2 X , g (x ) = sgn (h (x )) =
1 si h (x ) < 0

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 54 / 228
3. Formalisation du SVM

De…nition (vecteur normal)

Le vecteur normal à l’hyperplan séparateur H est dé…ni par
ω
e =
ω
kω k

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 55 / 228
3. Formalisation du SVM

Example (cas d = 2)
On considère le cas X = R2 et x = (x1 , x2 )0 . Soit un classi…eur linéaire
g (x ) = sgn (h (x )), avec h (x ) = hω, x i + b et

ω = (1, 2) b= 1

e le vecteur normal à l’hyperplan séparateur H.

Question : représentez ω

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 56 / 228
3. Formalisation du SVM

Solution : L’équation qui dé…nit l’hyperplan séparateur H est

h (x ) = x1 + 2x2 1 = 0, 8 x = ( x 1 , x 2 ) 2 R2

Le vecteur normal à H est dé…ni par

ω 1 1 2
e =
ω = p (1, 2) = p ,p
k k
ω 1+4 5 5
avec par dé…nition r
p 2 p 2
ek =
kω 1/ 5 + 2/ 5 =1

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 57 / 228
3. Formalisation du SVM

2.5

2 Vecteur (1,2)
norme = 5

1.5

2
x2

1 v ecteur
normal
norme = 1
H
0.5

1
0

-0.5
-1 -0.5 0 0.5 1 1.5 2
x1

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 58 / 228
3. Formalisation du SVM

Dé…nition (distance d’un point à l’hyperplan)

La distance d’un point x 2 Rd à l’hyperplan H est donnée par
jhω, x i + b j jh (x )j
e x
d (x , H ) = jhω, x0 ij = =
kω k kω k
e le vecteur normal à l’hyperplan séparateur H.
avec x0 2 H et ω

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 59 / 228
3. Formalisation du SVM

Preuve :

d (x , H ) = e x x0 ij
jhω,
1
= jhω, x x0 ij
kω k
1
= jhω, x i hω, x0 ij
kω k
1
= jhω, x i + b j
kω k
jh (x )j
=
kω k

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 60 / 228
3. Formalisation du SVM

Example (distance d’un point à l’hyperplan)

On considère le cas X = R2 . Soit un classi…eur linéaire g (x ) = sgn (h (x )), avec
h (x ) = hω, x i + b et
ω = (1, 2) b= 1
Question : quelle est la distance à l’hyperplan séparateur des points suivants ?
3 1 1
A 1; B ,
2 2 2

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 61 / 228
3. Formalisation du SVM

3 1 1
ω = (1, 2) b= 1 A 1; B ,
2 2 2
Solution :
p p
On sait que kω k = 12 + 22 = 5. Il vient :

jh (xA )j j1 1+2 (3/2) 1j 3

d (A, H ) = = p = p
kω k 5 5
jh (xB )j j1 ( 1/2) + 2 ( 1/2) 1j 2, 5
d (B , H ) = = p = p
kω k 5 5

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 62 / 228
3. Formalisation du SVM

Normalisation et hyperplan canonique

En général, on normalise les paramètres ω et b de sorte à ce que la fonction de décision
h (x ) évaluée sur un vecteur de support soit égale à +1 ou 1.
On obtient alors un hyperplan canonique.

Dé…nition (hyperplan canonique)

Un hyperplan séparateur est dit canonique par rapport aux observations fx1 , . . . , xn g si
et seulement si
min jh (xi )j = min jhω, xi i + b j = 1
xi :i =1,..,n xi

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 63 / 228
3. Formalisation du SVM

Intuition. Soit une fonction de décision e

h (x ) telle que
e e
e xi + b
h (x ) = hω,

L’hyperplan séparateur H est dé…ni par 8x 2 H

e e=0
e xi + b
h (x ) = hω,

Cet hyperplan peut être dé…ni de façon équivalente par n’importe quel couple (ωk, bk ),
avec k > 0, et une nouvelle fonction de décision h (x ) telle que 8k 2 R , 8x 2 H :

h (x ) = k e
h (x ) = hk ω, x i + kb = 0

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 64 / 228
3. Formalisation du SVM

Intuition (suite). Supposons que les vecteurs de support situés respectivement au dessus
+ ) et en dessous (x ) de l’hyperplan H véri…ent
(xsv sv

e +
h xsv = ω, +
e xsv + be = +c
e +
h xsv e=
e xsv + b
= ω, c
avec c 2 R . Il est toujours possible de dé…nir une nouvelle fonction de décision
h (x ) = e
h (x ) /c telle que
+ +
h xsv = ω, xsv + b = +1

h xsv = ω, xsv + b = 1
avec
e
ω e
b
ω= b=
c c

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 65 / 228
3. Formalisation du SVM

Intuition (suite).
e e=
e xi + b
h (xsv ) = hω, c
1e
h (xsv ) = h (xsv ) = hω, x i + b = 1
c

Les classi…eurs associés à e

h (.) et h (.) sont par dé…nition identiques.

Les équations h (x ) = 0 et e
h (x ) = 0 dé…nissent le même hyperplan séparateur H.

L’équation h (x ) = 0 dé…nit un hyperplan canonique puisque

minxi :i =1,..,n jh (xi )j = jh (xsv )j = 1

/ H, h (x ) 6= e
Pour x 2 h (x ).

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 66 / 228
3. Formalisation du SVM

Example (cas d = 2)
On considère le cas X = R2 et un classi…eur linéaire g (x ) = sgn (e
h (x )), avec
e e x = (x1 , x2 )0 et
e x i + b,
h (x ) = hω,

e = (1, 2)
ω e=
b 1

On admet que le vecteur (1, 1) est un vecteur de support. Question : quelle est la
fonction de décision associée à l’hyperplan canonique H ?

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 67 / 228
3. Formalisation du SVM

Solution : On pose
e
h (x ) = x1 + 2x2 1
Soit le vecteur de support xsv = (1, 1) :
e
h (xsv ) = 1 + 2 1=2 ge (xsv ) = sgn (2) = 1

L’équation de l’hyperplan canonique est alors dé…nie par :

1e
h (x ) = h (x ) = hω, x i + b = 0, 5x1 + x2 0, 5 = 0
2
avec ω = (0, 5; 1) et b = 0, 5. Par dé…nition :

h (xsv ) = 0, 5 + 1 0, 5 = 1 g (xsv ) = sgn (1) = 1

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 68 / 228
 e
h (x ) = x1 + 2x2 1 h (x ) = 0, 5x1 + x2 0, 5

2 2

h(x)=2,4 h(x)=1,2
h(x)=3 h(x)=1,5
1.5 1.5

h(x)=2,7 h(x)=1,35
1 h(x)=0 1 h(x)=0
h(x)=2 h(x)=1
x2

x2
0.5 0.5

0 0

h(x)=-2 h(x)=-1
-0.5 -0.5
h(x)=-2,5 h(x)=-1,25

-1 -1
-1 -0.5 0 0.5 1 1.5 2 -1 -0.5 0 0.5 1 1.5 2
x1 x1

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 69 / 228
3. Formalisation du SVM

Dé…nition (vecteurs de support)

Dans un hyperplan canonique, les vecteurs de support sont les observations xi 2 S qui
véri…ent
h (xi ) = 1 8i 2 S
yi h (xi ) = yi (hω, xi i + b ) = 1 8i 2 S

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 70 / 228
3. Formalisation du SVM

Remarque
Pour un hyperplan canonique, les conditions d’une classi…cation parfaite (sur
l’échantillon d’apprentissage) sont de la forme :

h (xi ) = hω, xi i + b 1 si yi = 1

h (xi ) = hω, xi i + b 1 si yi = 1
8i = 1, ..., n. Ces conditions peuvent se réécrire sous la forme :

yi h (xi ) 1 8i = 1, ..., n

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 71 / 228
3. Formalisation du SVM

Dé…nition (marge)
La marge M (ω, b ) correspond au double de la distance entre un vecteur de support xsv
et l’hyperplan canonique séparateur H.
jh (xsv )j 2
M (ω, b ) = 2 d (xsv , H ) = 2 =
kω k kω k
puisque par dé…nition h (xsv ) = 1.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 72 / 228
3. Formalisation du SVM

Dé…nition (hyperplan canonique optimal)

Un hyperplan canonique h (x ) = hω , x i + b = 0 est optimal par rapport aux
observations fxi , yi gni=1 si cet hyperplan maximise la marge M (ω, b ) et classi…e
parfaitement toutes les observations. Il véri…e alors :
2
(ω , b ) = arg max
ω 2Rd ,b 2R kω k
sc : yi h (xi ) 1 8i = 1, . . . , n

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 73 / 228
3. Formalisation du SVM

Trouver un hyperplan qui maximise la marge M (ω ) équivaut à trouver un hyperplan

paramétré par (ω , b ) tel que :
2
(ω , b ) = arg max M (ω ) =
ω 2Rd ,b 2R kω k
sc : yi h (xi ) 1 8i = 1, . . . , n

Ce qui est équivalent à

1
(ω , b ) = arg min k ω k2
ω 2Rd ,b 2R 2
sc : yi h (xi ) 1 8i = 1, . . . , n

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 74 / 228
3. Formalisation du SVM

Dé…nition (hyperplan canonique optimal)

Une écriture équivalente du programme primal du SVM permettant de déterminer
l’hyperplan séparateur canonique optimal est
1
(ω , b ) = arg min k ω k2
ω 2Rd ,b 2R 2
sc : yi h (xi ) 1 8i = 1, . . . , n

avec h (x ) = hω, x i + b, 8x 2 X .

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 75 / 228
3. Formalisation du SVM

1
min k ω k2
ω 2Rd ,b 2R 2
sc : yi h (xi ) 1 8i = 1, . . . , n

Puisque ce problème d’optimisation est convexe, il est equivalent de résoudre le

problème primal ou le problème dual.

Le problème dual implique d’introduire les multiplicateurs de Lagrange associés aux

n contraintes (nombre d’exemples / observations).

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 76 / 228
3. Formalisation du SVM

Dé…nition (Lagrangien)
Le Lagrangien associé au programme du SVM s’écrit
n
1
L (ω, b, λ) =
2
k ω k2 ∑ λi [yi (hω, xi i + b ) 1]
i =1

avec λ = (λ1 , ..., λn )0 le vecteur des multiplicateurs véri…ant 8i = 1, . . . , n

λi 0

λi [yi (hω, xi i + b ) 1] = 0

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 77 / 228
3. Formalisation du SVM

Remarques
n
1
L (ω, b, λ) =
2
k ω k2 ∑ λi [yi (hω, xi i + b ) 1]
i =1
λi [yi (hω, xi i + b ) 1] = 0 avec λi 0

1 Le Lagrangien doit être minimisé par rapport à ω et b, et maximisé par rapport à λ

2 Si la contrainte [yi (hω, xi i + b ) 1] = 0 est satisfaite, alors λi > 0 et xi est un

vecteur de support.

3 Si [yi (hω, xi i + b ) 1] > 0, alors λi = 0 et le point xi , situé au delà de la marge,

est bien classé. En pratique beaucoup de λi sont nuls.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 78 / 228
3. Formalisation du SVM

Remarque. Si l’on dé…nit xi = (xi 1 , . . . , xid )0 , 8i = 1, . . . , n et ω = (ω 1 , . . . , ω d )0 , le

Lagrangien s’écrit comme suit :
n
1
L (ω, b, λ) =
2
k ω k2 ∑ λi [yi (hω, xi i + b ) 1]
i =1
" ! #
1 d 2 n d

2 j∑ ∑ λi ∑ ωj xij + b
= ωj yi 1
=1 i =1 j =1

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 79 / 228
3. Formalisation du SVM

Dé…nition (conditions de Karush-Kuhn-Tucker )

Les conditions de Karush-Kuhn-Tucker (ou Kuhn-Tucker) sont dé…nies par
n
∂L (ω, b, λ)
∂ω
=ω ∑ λi yi xi =0
i =1
n
∂L (ω, b, λ)
∂b
= ∑ λi yi =0
i =1
λi (yi h (xi ) 1) = λi [yi (hω, xi i + b ) 1] = 0
λi 0, 8i = 1, ..., n

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 80 / 228
3. Formalisation du SVM

En introduisant les conditions de KKT, on obtient une optimisation ne dépendant que

des multiplicateurs
n
1
L (ω, b, λ) =
2
k ω k2 ∑ λi [yi (hω, xi i + b ) 1]
i =1
n n n
1
=
2
hω, ω i ∑ λi yi hω, xi i b ∑ λi yi + ∑ λi
i =1 i =1 i =1
n n
1
=
2
hω, ω i ∑ λi yi hω, xi i + ∑ λi
i =1 i =1

puisque ∑ni=1 λi yi = 0.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 81 / 228
3. Formalisation du SVM

n n
1
L (ω, b, λ) =
2
hω, ω i ∑ λi yi hω, xi i + ∑ λi
i =1 i =1
De plus, nous savons que ω = ∑ni=1 λi yi xi , dès lors il vient :

1 n n
2 i∑ ∑ λi λj yi yj xi , xj
L (ω, b, λ) =
=1 j =1
n n n
∑ λi yi ∑ λj yj xi , xj + ∑ λi
i =1 j =1 i =1

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 82 / 228
3. Formalisation du SVM

Dé…nition (problème dual)

Le problème du SVM s’exprime sous forme duale comme :
n
1 n n
λ = arg max ∑ λi 2 i∑ ∑ λi λj yi yj xi , xj
λ1 ,..,λn i =1 =1 j =1
sc : λi 0
n
sc : ∑ λi yi =0
i =1

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 83 / 228
3. Formalisation du SVM

Le terme xi , xj correspond au terme de la i ème ligne et j ème colonne de la matrice de

Gram (ou matrice Hessienne)
0 1
hx1 , x1 i hx1 , x2 i ... ... hx1 , xn i
B hx2 , x1 i hx2 , x2 i ... ... ... C
matrice de Gram = Ω = B @
C
A
n n ... ... ... ... ...
hxn , x1 i ... ... ... hxn , xn i

Remarque : si X = (x1 : .. : xn ) est une matrice n d , alors la matrice de Gram peut

s’écrire sous la forme XX 0 .

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 84 / 228
3. Formalisation du SVM

Solution optimale du SVM

1 Une fois obtenu les multiplicateurs optimaux λ , on en déduit le vecteur de

coe¢ cients ω comme
n
ω = ∑ λi yi xi = ∑ λi yi xi
i =1 i 2S

où S désigne l’ensemble des vecteurs de supports, puisque λι = 0 pour i 2

/ S.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 85 / 228
3. Formalisation du SVM

Solution optimale du SVM

2 Pour déterminer la constante b , on considère n’importe quel vecteur de support

i 2 S tel que
yi (hω , xi i + b ) = 1
On en déduit b comme
1
b = h ω , xi i , 8i 2 S
yi
Puisque yi 2 f 1, 1g , on peut aussi écrire

b = yi h ω , xi i , 8i 2 S

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 86 / 228
3. Formalisation du SVM

Dé…nition (fonction de décision optimale)

Pour tout point x 2 X , la fonction de décision optimale h (x ) est

h (x ) = h ω , x i + b = ∑ λi yi hxi , x i + b
i 2S

où S désigne l’ensemble des vecteurs de support. Le classi…eur associé est :

(
1 si h (x ) 0
g (x ) = sgn (h (x )) =
1 si h (x ) < 0

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 87 / 228
3. Formalisation du SVM

Solution optimale du SVM

h (x ) = ∑ λi yi hxi , x i + b 8x 2 X
i 2S

Seuls les vecteurs de supports (pondérés par λi ) déterminent le classement de toutes

observations des échantillon d’apprentissage et de test.

Le SVM s’apparente à un algorithme des plus proches voisins.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 88 / 228
3. Formalisation du SVM

Programme primal Programme dual

λ = arg max ∑ni=1 λi

(ω , b ) = arg min 1
k ω k2 λ1 ,..,λn
ω 2Rd ,b 2R
2 1
2 ∑ni=1 ∑nj=1 λi λj yi yj xi , xj
sc : yi h (xi ) 1 8i = 1, ..., n sc : λi 0
sc : ∑ni=1 λi yi = 0

h (x ) = h ω , x i + b ω = ∑ i 2S λ i y i x i
b = yi h ω , xi i , 8i 2 S
h (x ) = ∑ i 2S λ i y i hx i , x i + b

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 89 / 228
3. Formalisation du SVM

Programme primal ou dual ?

Les deux programmes (primal et dual) donnent bien évidemment la même solution.

Le programme dual montre que seuls les vecteurs de support sont nécessaires pour
classer toutes les observations

Cette formulation met en outre en évidence l’importance des termes de la matrice de

Gram ( xi , xj ) qui permettra l’introduction des fonctions kernel.

Dans les problèmes de grande dimension (d grand par rapport à n) comme le

text-mining, le traitement d’image, la forme duale rend les calculs plus simples pour
les techniques d’optimisation.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 90 / 228
3. Formalisation du SVM

Example (SVM)
On considère x = (x1 , x2 )0 2 R2 et un échantillon d’apprentissage de taille n = 10 pour
lequel on observe les données suivantes. Question : en utilisant un programme
d’optimisation quadratique résoudre le programme primal du SVM et déterminez
l’équation de l’hyperplan séparateur canonique optimal.

x1 x2 y
4 8 -1
2 4 -1
4 6 -1
6 6 -1
8 8 -1
6 10 -1
12 6 1
10 6 1
8 2 1
6 2 1

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 91 / 228
3. Formalisation du SVM

12
Y=-1
Y=1
10

8
X2

0
0 2 4 6 8 10 12 14
X1

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 92 / 228
3. Formalisation du SVM

(ω , b ) = arg min 1
2 k ω k2
ω 2R2 ,b 2R

sc : yi h (xi ) 1 8i = 1, ..., n

Ecrivons ce progamme sous forme matricielle, a…n d’utiliser un programme d’optimisation

quadratique sous Matlab:
0
θ = ω1 ω2 b
0 10 1
1 0 0 ω1
1 1 1 1
k ω k2 = ω 21 + ω 22 = ω 1 ω 2 b @ 0 1 0 A @ ω 2 A = θH θ 0
2 2 2 2
0 0 0 b

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 93 / 228
3. Formalisation du SVM
(ω , b ) = arg min 1
2 k ω k2
ω 2R2 ,b 2R

sc : yi h (xi ) 1 8i = 1, ..., n

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 94 / 228
3. Formalisation du SVM

Solution
On obtient comme solution
1 1 0
ω = , b = 1
2 2
La fonction de décision s’écrit donc :
1 1
h (xi ) = h ω , xi i + b = x x 1 8xi 2 R2
2 1i 2 2i
L’équation de l’hyperplan canonique optimale est dé…nie par :

h (xi ) = 0 , x2i = x1i 2

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 95 / 228
3. Formalisation du SVM

Solution
1 1
h (xi ) = x x 1 h (xi ) yi 1
2 1i 2 2i

x1i x2i yi h (xi ) yi h (xi ) Statut λi

4 8 1 3 3 — 0
2 4 1 2 2 — 0
4 6 1 2 2 — 0
6 6 1 1 1 vecteur de support 0, 1423
8 8 1 1 1 vecteur de support 0, 1077
6 10 1 3 3 — 0
12 6 1 2 2 — 0
10 6 1 1 1 vecteur de support 0, 1789
8 2 1 2 2 — 0
6 2 1 1 1 vecteur de support 0, 0711

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 96 / 228
3. Formalisation du SVM

12
y=-1
y=1 -3
10 Support Vector
h(x)=0

-3 -1
8

-2 -1 1 2
X2

-2
4

1 2
2

0
0 2 4 6 8 10 12 14
X1

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 97 / 228
3. Formalisation du SVM

Example (SVM et prévision)

On considère l’échantillon d’apprentissage de la question précédente. On souhaite prévoir
la classe associée aux observations suivantes de l’échantillon de test :

xA = (6, 8)0

xB = (10, 2)0
Question : en n’utilisant que les multplicateurs de Lagrange λi des vecteurs de support
(cf. tableau précédent), déterminez la prévision sur les variables yA et yB ?

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 98 / 228
3. Formalisation du SVM

Solution

x1 x2 y h (x ) yh (x ) Statut λ
6 6 1 1 1 vecteur de support 0, 1423
8 8 1 1 1 vecteur de support 0, 1077
10 6 1 1 1 vecteur de support 0, 1789
6 2 1 1 1 vecteur de support 0, 0711

On sait que pour une observation x = (x1 , x2 ) 2 R2 , la fonction de décision s’écrit

comme :
b
h (x ) = ∑ λi yi hxi , x i + b
i 2S
= 0, 1423 (6x1 + 6x2 ) 0, 1077 (8x1 + 8x2 )
+0, 1789 (10x1 + 6x2 ) + 0, 0711 (6x1 + 2x2 ) 1

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 99 / 228
3. Formalisation du SVM

Solution
On obtient donc pour
xA = (6, 8)0 xB = (10, 2)0
les décisions suivantes
b
h (xA ) = 0, 1423 (6 6 + 6 8) 0, 1077 (8 6 + 8 8)
+0, 1789 (10 6 + 6 8) + 0, 0711 (6 6 + 2 8) 1= 2

b
h (xB ) = 0, 1423 (6 10 + 6 2) 0, 1077 (8 10 + 8 2)
+0, 1789 (10 10 + 6 2) + 0, 0711 (6 10 + 2 2) 1=3

On en déduit les prévisions sur la variable dépendante

ybA = sgn b
h (xA ) = sgn ( 2) = 1

ybB = sgn b
h (xB ) = sgn (3) = 1

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 100 / 228
3. Formalisation du SVM

12
y=-1
y=1
10 Support Vector
h(x)=0

-2
8
X2

3
2

0
0 2 4 6 8 10 12 14
X1

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 101 / 228
3. Formalisation du SVM

Example (matrice de Gram)

On considère le même échantillon d’apprentissage (cf. tableau infra). Question :
déterminez la matrice de Gram.

Obs. x1,i x2,i yi

1 4 8 1
2 2 4 1
3 4 6 1
4 6 6 1
5 8 8 1
6 6 10 1
7 12 6 1
8 10 6 1
9 8 2 1
10 6 2 1

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 102 / 228
3. Formalisation du SVM

Solution La matrice de Gram associée au kernel linéaire est dé…nie par

0 1
hx1 , x1 i hx1 , x2 i ... ... hx1 , xn i
B hx2 , x1 i hx2 , x2 i ... ... ... C
Ω =B @
C
A
(n n ) ... ... ... ... ...
hxn , x1 i ... ... ... hxn , xn i

Ici, il vient
0 1
80 40 64 72 96 104 96 88 48 40
B 40 20 32 36 48 52 48 44 24 20 C
B C
B 64 32 52 60 80 84 84 76 44 36 C
B C
B 72 36 60 72 96 96 108 96 60 48 C
B C
B 96 48 80 96 128 128 144 128 80 64 C
Ω =B B
C
C
(10 10 ) B 104 52 84 96 128 136 132 120 68 56 C
B 96 48 84 108 144 132 180 156 108 84 C
B C
B 88 44 76 96 128 120 156 136 92 72 C
B C
@ 48 24 44 60 80 68 108 92 68 52 A
40 20 36 48 64 56 84 72 52 40

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 103 / 228
3. Formalisation du SVM

Example (SVM programme dual)

On considère le même échantillon d’apprentissage (cf. tableau infra). Question : en
utilisant un programme d’optimisation quadratique résoudre le programme dual du SVM
et déterminez l’équation de l’hyperplan séparateur canonique optimal.

Obs. x1,i x2,i yi

1 4 8 1
2 2 4 1
3 4 6 1
4 6 6 1
5 8 8 1
6 6 10 1
7 12 6 1
8 10 6 1
9 8 2 1
10 6 2 1

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 104 / 228
3. Formalisation du SVM

n
λ = arg max ∑ λi
λ1 ,..,λn i =1
n n
1
2 i∑ ∑ λi λj yi yj xi , xj
=1 j =1
sc : λi 0
n
sc : ∑ λi yi =0
i =1

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 105 / 228
3. Formalisation du SVM

Solution
Le vecteur de coe¢ cients ω est dé…ni par

ω = ∑ λi yi xi
i 2S
6 8 10 6
= 0, 1423 0, 1077 + 0, 1789 + 0, 0711
6 8 6 2
1/2
=
1/2

La constante b véri…e
b = yi h ω , xi i , 8i 2 S
0
Donc, pour le vecteur de support (6, 6) , il vient :

1 1
b = 1 6 6 = 1
2 2

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 106 / 228
3. Formalisation du SVM

Solution
On sait que pour x = (x1 , x2 )0 2 R2 , la fonction de décision s’écrit comme :

h (x ) = ∑ λi yi hxi , x i + b = hω , x i + b
i 2S

1 1 0
ω = 2 2 b = 1

L’équation de l’hyperplan canonique optimal est donc dé…nie par

1 1
h xj = x x 1=0
2 1j 2 2j
ou encore
x2j = x1j 2

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 107 / 228
3. Formalisation du SVM

Concepts clés

1 Distance d’un point à l’hyperplan séparateur.

2 Marge.

3 Vecteurs de support.

4 Hyperplan canonique optimal.

5 Programme primal et dual du SVM.

6 Matrice de Gram.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 108 / 228
 Section 4

Soft margin

Le cas d’un échantillon non séparable

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 109 / 228
4. Soft margin

Objectifs

1 Comprendre la notion de variable ressort (slack variable).

2 Comprendre la notion de soft margin.

3 Dé…nir le paramètre de pénalisation (ou paramètre de coût).

4 Dé…nir le programme primal du SVM avec variables ressort.

5 Dé…nir le programme dual du SVM avec variables ressort.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 110 / 228
4. Soft margin

Hypothèse
On suppose à présent que l’échantillon d’apprentissage n’est pas linéairement séparable.
Deux cas :
1 l’échantillon est presque linéairement séparable : la séparation "optimale" est
linéaire, mais quelques observations ne peuvent pas être correctement classées.

2 l’échantillon n’est pas linéairement séparable : la séparation "optimale" est

non-linéaire.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 111 / 228
4. Soft margin

Un exemple d’échantillon presque

linéairement séparable

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 112 / 228
4. Soft margin

Dé…nition (variables ressort)

Dans le cas d’un échantillon presque linéairement séparable, on introduit n variables de
relaxation des contraintes de classi…cation yi h (xi ) 1. Ces variables, notées
ξ = (ξ 1 , ..., ξ n )0 , sont appelées variables "ressort" (slack variables) et véri…ent :

yi (hω, xi i + b ) 1 ξ i avec ξ i 0

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 113 / 228
4. Soft margin

Dé…nition (soft margin)

On parle alors de soft margin, puisque certaines observations (xi , yi ) peuvent être bien
classés mais en deça de la marge (si 0 < ξ i < 1), voire mal classées, dès lors que ξ i > 1.

yi (hω, xi i + b ) 1 ξ i avec ξ i 0

Cortes C. and V. Vapnik (1995), Support-Vector Networks, Machine Learning, 20 .

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 114 / 228
4. Soft margin

Soft Margin
yi (hω, xi i + b ) 1 ξ i avec ξ i 0

Trois con…gurations peuvent apparaître suivant les valeurs de ξ i :

1 Si ξ i = 0, yi h (xi ) 1 : l’observation (xi , yi ) est correctement classée.

2 Si ξ i 1, alors l’observation (xi , yi ) peut être située du mauvais côté de la frontière

si e¤ectivement yi h (xi ) < 0.

3 Si 0 < ξ i < 1 : l’observation (xi , yi ) est nécessairement située du bon côté de la

frontière (bien classée), mais peut être située à une distance de l’hyperplan
séparateur inférieure à la moitié de la marge.
1
d (xi , H ) <
kω k

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 115 / 228
4. Soft margin

Source : https://towardsdatascience.com

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 116 / 228
4. Soft margin

Dé…nition (programme primal avec soft margin)

Le problème primal du SVM dans le cas non-séparable (avec variables ressort) est
dé…ni par
n
1
(ω , b , ξ ) = arg min k ω k2 + C ∑ ξ i
ω 2Rd ,b 2R,ξ 2Rn 2 i =1
sc : yi (hω, xi i + b ) 1 ξ i 8i = 1, ..., n
sc : ξi 0

où C > 0 désigne un coe¢ cient de pénalisation (ou paramètre de coût).

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 117 / 228
4. Soft margin

Interpretation

n
1
(ω , b , ξ ) = arg min
2
k ω k2 + C
|{z} ∑ ξi
ω 2Rd ,b 2R,ξ 2Rn | {z } paramètre de coût i =1
marge
| {z }
Erreurs de classi…cation
sc : yi (hω, xi i + b ) 1 ξ i 8i = 1, ..., n
sc : ξi 0

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 118 / 228
4. Soft margin

Remarque :
Le paramètre de pénalisation C contrôle l’arbitrage entre la dimension de la marge et le
taux d’erreur.

Si C est petit, les erreurs de classi…cation sont moins pénalisées et l’accent est mis
sur la maximisation de la marge.
I Il y a un risque de sous-apprentissage (mauvais taux de classi…cation sur l’échantillon
d’apprentissage).
Si C est grand, l’accent est mis sur l’absence de mauvaise classi…cation au prix d’une
marge plus faible.
I Il y a un risque de sur-apprentissage (over-…tting).

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 119 / 228
4. Soft margin

Formulation Lagrangienne
Dans le cas non linéairement séparable, le Lagrangien associé au programme du SVM
s’écrit
n
1
L (ω, b, ξ, λ, µ) = k ω k2 + C ∑ ξ i
2 i =1
n n
∑ λi [yi (hω, xi i + b ) (1 ξ i )] ∑ µi ξ i
i =1 i =1
0 0
avec λ = (λ1 , ..., λn ) et µ = (µ1 , ..., µn ) véri…ant 8i = 1, ..., n

λi 0 µi 0 ξi 0

λi [yi (hω, xi i + b ) (1 ξ i )] = 0 µi ξ i = 0

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 120 / 228
4. Soft margin

Dé…nition (conditions de Karush-Kuhn-Tucker )

Les conditions de Karush-Kuhn-Tucker sont dé…nies par
n
∂L (ω, b, ξ, λ, µ)
∂ω
=ω ∑ λi yi xi =0
i =1
n
∂L (ω, b, ξ, λ, µ)
∂b
= ∑ λi yi =0
i =1
∂L (ω, b, ξ, λ, µ)
=C µi λi = 0
∂ξ i
λi [yi (hω, xi i + b ) (1 ξ i )] = 0
µi ξ i = 0
λi 0, µi 0 8i = 1, ..., n

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 121 / 228
4. Soft margin

Dé…nition (problème dual avec soft margin)

Le problème dual du SVM dans le cas non-séparable s’écrit comme :
n
1 n n
λ = arg max ∑ λi 2 i∑ ∑ λi λj yi yj xi , xj
λ1 ,..,λn i =1 =1 j =1
sc : 0 λi C
n
sc : ∑ λi yi =0
i =1

où C > 0 désigne un coe¢ cient de pénalisation (ou paramètre de coût).

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 122 / 228
4. Soft margin

Remarque :
n
1 n n
λ = arg max ∑ λi 2 i∑ ∑ λi λj yi yj xi , xj
λ1 ,..,λn i =1 =1 j =1
sc : 0 λi C
n
sc : ∑ λi yi =0
i =1

Le programme est identique au cas séparable : la seule di¤érence est la borne supérieure
sur les multiplicateurs de Lagrange λi .

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 123 / 228
4. Soft margin

Trois con…gurations peuvent apparaître suivant les valeurs de λi :

1 Si λi = 0, alors yi (hω, xi i + b ) 1, µi = C > 0, ξ i = 0 : l’observation (xi , yi ) est

correctement classée.

2 Si 0 < λi < C alors yi (hω, xi i + b ) = 1, µi = C λi > 0, ξ i = 0 : on en déduit

que ξ i = 0. L’observation xi est un vecteur de support.

3 Si λi = C , alors yi (hω, xi i + b ) = 1 ξ i et ξ i > 0 car µi = C λi = 0 :

l’observation (xi , yi ) peut être située dans la marge (bien classée) ou du mauvais
côté de la frontière (mal classée).

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 124 / 228
4. Soft margin

Solution optimale du SVM

Une fois obtenu les multiplicateurs optimaux λ , on en déduit les coe¢ cients ω et b
comme
n
ω = ∑ λi yi xi = ∑ λi yi xi
i =1 i 2S

b = yi h ω , xi i , 8i 2 S
où S désigne l’ensemble des vecteurs de supports (0 < λi < C ) et des variables
ressorts (λi = C ).

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 125 / 228
3. Formalisation du SVM

Dé…nition (fonction de décision optimale)

Pour tout point x 2 X , la fonction de décision optimale h (x ) est

h (x ) = h ω , x i + b = ∑ λi yi hxi , x i + b
i 2S

où S désigne l’ensemble des vecteurs de support. Le classi…eur associé est :

(
1 si h (x ) 0
g (x ) = sgn (h (x )) =
1 si h (x ) < 0

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 126 / 228
4. Soft margin

Programme primal Programme dual

λ = arg max ∑ni=1 λi

(ω , b , ξ ) = arg min 1
2 k ω k2 λ1 ,..,λn
ω 2Rd ,b 2R,ξ 2Rn 1
∑ni=1 ∑nj=1 λi λj yi yj xi , xj
+C ∑ni=1 ξ i 2

sc : 0 λi C
sc : yi h (xi ) 1 ξ i 8i = 1, ..., n
sc : ∑ni=1 λi yi = 0

h (x ) = h ω , x i + b ω = ∑ i 2S λ i y i x i
— b = yi h ω , xi i , 8i 2 S
— h (x ) = ∑ i 2S λ i y i hx i , x i + b

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 127 / 228
4. Soft margin

Paramètre de pénalisation

Dans la pratique, les performances du SVM sont très sensibles au choix du

paramètre de pénalisation (coût) C .

Comment sélectionner un hyper-paramètre C "optimal" ?

Méthode de validation croisée (Cross Validation ou CV).

Pour plus de détails cf. cours Big Data: Arbres de décision et les méthodes
d’agrégation (responsable : Sessi Tokpavi).

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 128 / 228
4. Soft margin

Première solution : validation croisée

1 L’échantillon est partitionné en 3 échantillons d’apprentissage (training ), validation

(validation) et test (test) par sous-échantillonnage aléatoire. L’échantillon de test
est utilisé pour évaluer les performances out-of-sample du classi…eur.

2 Sur l’échantillonage d’apprentissage, on applique le SVM pour di¤érentes valeurs de

C.

3 On cherche ensuite à déterminer la valeur de C qui minimise la probabilité d’erreur

de classi…cation mesurée sur l’échantillon de validation.
Remarque : sous SAS, cette approche correspond à l’option SELECT
CV=VALIDATESET.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 129 / 228
4. Soft margin

Deuxième solution : k-fold

La méthode k-fold cross validation se décompose de la façon suivante :

1 On coupe l’échantillon E de taille n en k sous-échantillons E1 , ..., Ep de taille n/k

2 On modélise le SVM sur E fEi g de taille n n/k

3 On évalue la probabilité d’erreur de classi…cation sur Ei

4 On cherche la valeur de C qui minimise la moyenne des probabilités d’erreurs.

Remarque : sous SAS, cette approche correspond à l’option SELECT CV=RANDOM

FOLD=k. En général, on choisit k = 10.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 130 / 228
4. Soft margin

Concepts clés

1 Echantillon presque linéairement séparable.

2 Variables ressort (slack).

3 Soft margin.

4 Programme primal et dual avec variables ressorts.

5 Paramètre de pénalisation (de coût).

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 131 / 228
 Section 5

Kernel trick

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 132 / 228
5. Kernel trick

Objectifs

1 Comprendre la notion d’espace de représentation intérmédiaire (feature space).

2 Comprendre l’astuce du kernel (kernel trick).

3 Introduire la notion de kernel.

4 Dé…nir les conditions de Mercer.

5 Dé…nir le programme primal du SVM avec kernel.

6 Dé…nir le programme dual du SVM avec kernel.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 133 / 228
5. Kernel trick

Idée générale

La plupart des problèmes de classi…cation relèvent de séparations non-linéaires.

Mais l’espace des données peut toujours être plongé dans un espace de plus grande
dimension dans lequel les données peuvent être séparées linéairement.

A complex pattern-classi…cation problem, cast in a high-dimensional space

nonlinearly, is more likely to be linearly separable than in a low-dimensional
space, provided that the space is not densely populated. (T.M. Cover, 1965)

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 134 / 228
5. Kernel trick

Un échantillon non linéairement ...devient séparable dans un espace

séparable... de plus grande dimension

1 14

0.8
12
0.6
10
0.4

0.2 8

X2
0
6
-0.2
4
-0.4

-0.6 2

-0.8
0
-1
-5 -4 -3 -2 -1 0 1 2 3 4 5 -5 -4 -3 -2 -1 0 1 2 3 4 5
X X

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 135 / 228
5. Kernel trick

Astuce kernel (kernel trick)

La résolution des SVM s’appuie sur le produit scalaire xi , xj entre les vecteurs
d’entrée.

Si les données d’apprentissage sont plongées dans un espace de plus grande

dimension via la transformation Φ (x ) .

Cet espace de Hilbert est associé au produit scalaire

K xi , xj = Φ (xi ) , Φ xj

où K xi , xj est appelée fonction noyau (kernel).

Pour implémenter le SVM, seul le noyau est important sans qu’il soit nécessaire
d’appliquer la transformation Φ (.) = > astuce du kernel

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 136 / 228
5. Kernel trick

Dé…nition (Feature space)

Au lieu de chercher un hyperplan dans l’espace des entrées X (Rd dans la suite de ce
chapitre), on passe d’abord dans un espace de représentation intermédiaire (feature
space) de plus grande dimension.

Φ : X !F
x 7 ! Φ (x )

Example
Soit x = (x1 , x2 ) 2 R2 , on considère la transformation

Φ : R2 ! R3
p
(x1 , x2 ) 7! Φ (x ) = x12 , 2x1 x2 , x22

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 137 / 228
5. Kernel trick

Problème

Φ : R2 ! R3
p
(x1 , x2 ) 7! Φ (x ) = x12 , 2x1 x2 , x22

Dans cet exemple,

p au lieu de manipuler 2 variables d’entrées x1 , x2 , on doit manipuler 3
variables x12 , 2x1 x2 , x22 , ce qui alourdit les calculs et le coût de stockage.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 138 / 228
5. Kernel trick

Kernel trick : dans cet espace intermédiaire, nous n’avons besoin que du produit scalaire
dé…nit par :

Φ (xi ) , Φ xj = xi21 xj21 + 2xi 1 xij xi 2 xj 2 + xi22 xj22

2
= xi 1 xj 1 + xi 2 xj 2
2
= xi , xj

On peut donc calculer le produit scalaire hΦ (x ) , Φ (x )i sans calculer Φ (x ) grâce à la

fonction kernel
2
K xi , xj = Φ (xi ) , Φ xj = xi , xj

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 139 / 228
5. Kernel trick

Example
Soit x = (x1 , x2 ) 2 R2 , on considère la transformation

Φ : R2 ! R6
p p p
(x1 , x2 ) 7! Φ (x ) = 1, 2x1 , 2x2 , x12 , x22 , 2x1 x2

Question : Déterminez la fonction kernel associée à cette transformation.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 140 / 228
5. Kernel trick

Solution. Soient deux vecteurs u = (u1 , u2 )0 et v = (v1 , v2 )0 , il vient

p p p
Φ (u ) = 1, 2u1 , 2u2 , u12 , u22 , 2u1 u2
p p p
Φ (v ) = 1, 2v1 , 2v2 , v12 , v22 , 2v1 v2

La fonction kernel correspondante est alors dé…nie par

K (u, v ) = hΦ (u ) , Φ (v )i
= 1 + 2u1 v1 + 2u2 v2 + u12 v12 + u22 v22 + 2u1 v1 u2 v2
= (1 + u1 v1 + u2 v2 )2
= (1 + hu, v i)2

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 141 / 228
5. Kernel trick

Example
p 0 p 0
On considère deux vecteurs u = 1, 3 2 et v = 1, 2 2 et la transformation Φ (.)
suivante

Φ : R2 ! R6
p p p
(x1 , x2 ) 7! Φ (x1 , x2 ) = 1, 2x1 , 2x2 , x12 , x22 , 2x1 x2

Question : Montrez que la fonction kernel K (u, v ) = (1 + hu, v i)2 est associée à la
transformation Φ (x ) pour ces deux vecteurs.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 142 / 228
5. Kernel trick

Solution. Soit la transformation

Φ : R2 ! R6
p p p
(x1 , x2 ) 7! Φ (x1 , x2 ) = 1, 2x1 , 2x2 , x12 , x22 , 2x1 x2

p 0 p 0
Pour les deux vecteurs u = 1, 3 2 et v = 1, 2 2 , il vient
p
Φ (u ) = 1, 2, 6, 1, 18, 6
p
Φ (v ) = 1, 2, 4, 1, 8, 4

On obtient donc :
p p
hΦ (u ) , Φ (v )i = 1 1+ 2 2+4 6+1 1 + 18 8+4 6
= 196

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 143 / 228
5. Kernel trick

Solution. On peut retrouver ce résultat directement avec la fonction kernel

K (u, v ) = (1 + hu, v i)2

p 0 p 0
Pour les deux vecteurs u = 1, 3 2 et v = 1, 2 2 , il vient
p p
hu, v i = 1 1+3 2 2 2 = 13

Dès lors
K (u, v ) = (1 + hu, v i)2 = (1 + 13)2 = 196
On véri…e que
K (u, v ) = hΦ (u ) , Φ (v )i

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 144 / 228
5. Kernel trick

Dé…nition (kernel trick)

La fonction kernel représente le produit scalaire associé à l’espace de représentation
intermédiaire. Pour une fonction kernel K xi , xj , il existe un espace de Hilbert F et
une fonction de transformation Φ (.) tels que

Φ : Rd ! Rm m > d
K xi , xj = Φ (xi ) , Φ xj ()
x 7 ! Φ (x )

Dans la pratique, l’astuce du noyau consiste à choisir une fonction kernel, sans
nécessairement caractériser l’espace F et la fonction Φ (.).

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 145 / 228
5. Kernel trick

Démarche

1 On transforme l’espace de représentation des données d’entrées en un espace de

plus grande dimension (possiblement de dimension in…nie).

2 Dans cet espace, il est probable qu’il existe une séparation linéaire.

3 On cherche alors à déterminer l’hyperplan canonique à marge maximale (ou

SVM) avec ou sans variables ressort (soft margin).

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 146 / 228
5. Kernel trick

Dé…nition (programme primal avec transformation de l’espace)

Le problème primal du SVM avec soft margin et transformation de l’espace de
représentation des données d’entrée est dé…ni par
n
1
(ω , b , ξ ) = arg min k ω k2 + C ∑ ξ i
ω 2Rd ,b 2R,ξ 2Rn 2 i =1
sc : yi (hω, Φ (xi )i + b ) 1 ξ i 8i = 1, ..., n
sc : ξi 0

où C > 0 désigne un coe¢ cient de pénalisation et Φ : X ! F désigne une

transformation.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 147 / 228
5. Kernel trick

Remarque

n
1
(ω , b , ξ ) = arg min k ω k2 + C ∑ ξ i
ω 2Rd ,b 2R,ξ 2Rn 2 i =1
sc : yi (hω, Φ (xi )i + b ) 1 ξ i 8i = 1, ..., n
sc : ξi 0

Le programme primal implique d’utiliser (et de connaître) la transformation Φ (x ), ce qui

n’est pas le cas du programme dual qui n’implique que la fonction kernel (kernel trick).

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 148 / 228
5. Kernel trick

Dé…nition (problème dual avec transformation de l’espace)

Le problème dual du SVM avec soft margin et kernel trick est dé…ni par
n
1 n n
λ = arg max ∑ λi 2 i∑ ∑ λi λj yi yj K xi , xj
λ1 ,..,λn i =1 =1 j =1
sc : 0 λi C
n
sc : ∑ λi yi =0
i =1

où C > 0 désigne un coe¢ cient de pénalisation et K xi , xj désigne la fonction kernel

associée à la transformation (inconnue) Φ : X ! F .

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 149 / 228
5. Kernel trick

Dé…nition (fonction de décision optimale)

Pour tout point x 2 X , la fonction de décision optimale h (x ) est

h (x ) = hω , Φ (x )i + b = ∑ λi yi K (xi , x ) + b
i 2S

b = yj ∑ λi yi K (xi , x ) , 8j 2 S
i 2S
où S désigne l’ensemble des vecteurs de support et des ressorts. Le classi…eur associé est :
(
1 si h (x ) 0
g (x ) = sgn (h (x )) =
1 si h (x ) < 0

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 150 / 228
5. Kernel trick

Programme primal Programme dual

λ = arg max ∑ni=1 λi

(ω , b , ξ ) = arg min 1
2 k ω k2 λ1 ,..,λn
ω 2Rd ,b 2R,ξ 2Rn 1
∑ni=1 ∑nj=1 λi λj yi yj K xi , xj
+C ∑ni=1 ξ i 2

sc : 0 λi C
sc : yi h (Φ (xi )) 1 ξ i 8i = 1, ..., n
sc : ∑ni=1 λi yi = 0

h (x ) = hω , Φ (x )i + b h (x ) = ∑ i 2S λ i y i K (x i , x ) + b
— b = yj ∑ i 2S λ i y i K (x i , x ) , 8j 2 S
— ω = ∑ i 2S λ i y i Φ (x i )

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 151 / 228
5. Kernel trick

Choix de la fonction kernel

1 Quelle est la dé…nition d’une fonction kernel ? = > conditions de Mercer

2 Quels sont les fonctions kernel disponibles dans SAS, R, Python et Matlab ?

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 152 / 228
5. Kernel trick

Dé…nition (conditions de Mercer)

Une fonction K (., .) continue, symétrique et positive est une fonction noyau (kernel) si
pour tous les xi 2 X possibles, la matrice de Gram K xi , xj i ,j est une matrice
symétrique et semi-dé…nie positive. Dans ce cas, il existe un espace de Hilbert F et une
fonction Φ tels que
K xi , xj = Φ (xi ) , Φ xj

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 153 / 228
5. Kernel trick

Matrice de Gram
0 1
K (x1 , x1 ) K (x1 , x2 ) ... ... K (x1 , xn )
B K (x2 , x1 ) K (x2 , x2 ) ... ... ... C
B
matrice de Gram = Ω = @ C
n n ... ... ... ... ... A
K (xn , x1 ) ... ... ... K (xn , xn )

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 154 / 228
5. Kernel trick

Kernels usuels

Noyau linéaire permet de retrouver le cas F = X

K xi , xj = xi , xj

Noyau polynomial de degré p (hyperparamètres : c, p)

p
K xi , xj = c + xi , xj

Remarque : sous SAS, le noyau polynomial ne dépend que de p

p
K xi , xj = 1 + xi , xj

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 155 / 228
5. Kernel trick

Kernels usuels

Noyau Radial Basis Function (RBF) ou Gaussien (hyperparamètre : σ)

2
!
xi xj
K xi , xj = exp
2σ2

Noyau sigmöide (perceptron à 2 couches) (hyperparamètres : θ 1 , θ 2 )

K xi , xj = tanh θ 1 xi , xj + θ 2

où tanh (.) désigne la fonction tangente hyperbolique.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 156 / 228
5. Kernel trick

Kernels disponibles dans les pincipaux logiciels

SAS (procédure HPSVM) : kernels linéaire, polynomial, RBF et sigmoïde.

Matlab (fonction …tcsvm) : kernels linéaire, polynomial, RBF, et possibilité

d’introduire un autre kernel en spéci…ant la matrice de Gram associée.

R (package e1071) : kernels linéaire, polynomial, RBF et sigmoïde.

Python (package scikit-learn)) : kernels linéaire, polynomial, RBF, sigmoïde, et

possibilité d’introduire un autre kernel en spéci…ant la matrice de Gram associée.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 157 / 228
5. Kernel trick

Construction de fonctions kernel

Il est possible de construire d’autres noyaux que les noyaux usuels en utilisant les
propriétés suivantes.
Propriétés : Si K1 (x , y ) et K2 (x , y ) sont des fonctions kernels, α 2 R + , alors les
fonctions K (x , y ) suivantes sont aussi des fonctions kernel
K (x , y ) = K 1 (x , y ) + K 2 (x , y )

K (x , y ) = αK1 (x , y )

K (x , y ) = hK1 (x , y ) , K2 (x , y )i

K (x , y ) = xAy > , où A est une matrice symétrique et semi-dé…nie positive

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 158 / 228
5. Kernel trick

Au …nal, la démarche du SVM avec transformation de l’espace de représentation des

données d’entrée est la suivante :

1 Séléction de la fonction kernel.

2 Sélection des hyperparamètres et du paramètre de pénalisation C sur une base

d’entrainement (training) par cross-validation.

3 Mesure de la performance prédictive sur une base de test

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 159 / 228
5. Kernel trick

Remarque (mise en garde)

Les performances prédictives du SVM sont très sensibles au choix du kernel, des valeurs
de C (paramètre de pénalisation) et des hyperparamètres de la fonction kernel.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 160 / 228
5. Kernel trick

Concepts clés

1 Echantillon non linéairement séparable.

2 Espace de représentation intérmédiaire (feature space).

3 Kernel.

4 Programme primal et dual avec transformation de l’espace de représentation des

données.

5 Conditions de Mercer.

6 Fonctions kernel usuelles.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 161 / 228
 Section 6

Application du SVM sous SAS, R, Python et Matlab

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 162 / 228
6. Application du SVM

1 Application du SVM sous SAS

2 Application du SVM sous Matlab

3 Application du SVM sous R

4 Application du SVM sous Python

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 163 / 228
6. Application du SVM

1 Application du SVM sous SAS

2 Application du SVM sous Matlab

3 Application du SVM sous R

4 Application du SVM sous Python

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 164 / 228
6. Application du SVM

Application du SVM sous SAS

Sous SAS, il y a deux possibilités pour appliquer les SVM :
1 Entreprise Miner

2 Procedure HPSVM (High Performance Support Vector Machine)

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 165 / 228
6. Application du SVM

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 166 / 228
6. Application du SVM

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 167 / 228
6. Application du SVM

La procédure HPSVM permet de :

1 D’implémenter un SVM pour un problème de classi…cation binaire.

2 De paralléliser les calculs sur plusieurs coeurs ou plusieurs machines, et d’utiliser des
données distribuées.

3 Deux méthodes d’optimisation (active-set ou interior point).

4 Choisir di¤érents kernels (linear, polynomial, radial basis function ou sigmoid).

5 Partionner automatiquement l’échantillon en échantillons d’apprentissage, de

validation, et de test.

6 De …xer la constante de pénalisation ou de contrôler la méthode de sélection

(cross-validation de type k-fold ou autre).

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 168 / 228
6. Application du SVM

La procédure HPSVM ne permet pas de :

1 D’implémenter un SVM pour un problème de classi…cation à plus de deux modalités.

2 D’implémenter un SVR pour un problème de régression.

3 De choisir un kernel di¤érent des 4 fonctions kernel proposées (linear, polynomial,

radial basis function ou sigmoid).

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 169 / 228
6. Application du SVM

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 170 / 228
6. Application du SVM

Exemple de code SAS : utilisation de la méthode d’optimisation active-set, d’un kernel

de type RBF avec un paramètre …xé à 1,5.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 171 / 228
6. Application du SVM

Exemple de code SAS : utilisation de la méthode d’optimisation interior point,

évaluation de 4 valeurs pour le paramètre de pénalité, sélection par validation croisée
(3-fold cross-validation) de type split (cf. option select).

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 172 / 228
6. Application du SVM

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 173 / 228
6. Application du SVM

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 174 / 228
6. Application du SVM

Example (SVM)
On considère x = (x1 , x2 )0 2 R2 et un échantillon d’apprentissage de taille n = 10 pour
lequel on observe les données suivantes (cf. tableau infra). Question : en utilisant la
procédure HPSVM, retrouvez les résultats obtenus par programmation quadratrique dans
la section 3 (Formalisation du SVM).

Obs. x1,i x2,i yi

1 4 8 1
2 2 4 1
3 4 6 1
4 6 6 1
5 8 8 1
6 6 10 1
7 12 6 1
8 10 6 1
9 8 2 1
10 6 2 1

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 175 / 228
6. Application du SVM

Example (SVM et kernel trick)

On considère x = (x1 , x2 )0 2 R2 et un échantillon d’apprentissage de taille n = 400
acessible dans le …chier Dataset2.xls. Question : en utilisant la procédure HPSVM et un
kernel de type RBF, représentez les observations de l’échantillon, les vecteurs support et
l’hyperplan séparateur.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 176 / 228
6. Application du SVM

Scatter Diagram with the Decision Boundary

0.8

0.6

0.4

0.2

-0.2

-0.4

-0.6
-1
-0.8 1
Support Vectors

-1 -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 1

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 177 / 228
6. Application du SVM

Example (SVM et credit scoring)

On considère le …chier Housing.rar. La base contient 5960 crédits avec un taux de défaut
de 20%. La variable dépendante est la variable "BAD" (dernière colonne), la variable
"REASON" est une variable binaire (1 ou 2) et "JOB" est une variable qualitative à 4
modalités, recodée en 4 variables binaires (JOB_1, JOB_2, JOB_3 et JOB_4). Les
autres variables sont des variables quantitatives. Question : Evaluez les performances
prédictives du HPSVM pour di¤érents choix de kernel et di¤érentes valeurs du paramètre
de coût C .

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 178 / 228
6. Application du SVM

1 Application du SVM sous SAS

2 Application du SVM sous Matlab

3 Application du SVM sous R

4 Application du SVM sous Python

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 179 / 228
6. Application du SVM

Application du SVM sous Matlab

Sous Matlab, il y a plusieurs fonctions reliées au SVM qui permettent (entre autre):

1 D’implémenter un SVM pour un problème de classi…cation binaire : fonctions

…tcsvm et …tckernel.

2 D’implémenter un SVR pour un problème de régression : fonction …trsvm

3 D’implementer un SVR/SVM sur des problèmes de classi…cation ou de régression de

très grande dimension en réduisant le temps de calcul : fonctions …tclinear et
…trlinear

4 De calculer les probabilités a posteriori (scores) : fonction …tSVMPosterior

5 De prévoir les labels : fonction predict.

6 D’implémenter un SVM pour un problème multiclasse : fonction …tcecoc

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 180 / 228
6. Application du SVM

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 181 / 228
6. Application du SVM

Example (SVM)
On considère x = (x1 , x2 )0 2 R2 et un échantillon d’apprentissage de taille n = 10 pour
lequel on observe les données suivantes (cf. tableau infra). Question : en utilisant la
fonction …tcsvm,retrouvez les résultats obtenus par programmation quadratrique dans la
section 3 (Formalisation du SVM).

Obs. x1,i x2,i yi

1 4 8 1
2 2 4 1
3 4 6 1
4 6 6 1
5 8 8 1
6 6 10 1
7 12 6 1
8 10 6 1
9 8 2 1
10 6 2 1

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 182 / 228
6. Application du SVM

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 183 / 228
6. Application du SVM

12
y=-1
y=1 -3
10 Support Vector
h(x)=0

-3 -1
8

-2 -1 1 2
X2

-2
4

1 2
2

0
0 2 4 6 8 10 12 14
X1

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 184 / 228
6. Application du SVM

Example (SVM et kernel trick)

On considère x = (x1 , x2 )0 2 R2 et un échantillon d’apprentissage de taille n = 400
acessible dans le …chier Dataset2.xls. Question : en utilisant la fonction …tcsvm et un
kernel de type RBF, représentez les observations de l’échantillon, les vecteurs support et
l’hyperplan séparateur.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 185 / 228
6. Application du SVM

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 186 / 228
6. Application du SVM

Scatter Diagram with the Decision Boundary

0.8

0.6

0.4

0.2

-0.2

-0.4

-0.6
-1
-0.8 1
Support Vectors

-1 -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 1

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 187 / 228
6. Application du SVM

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 188 / 228
6. Application du SVM

1 Application du SVM sous SAS

2 Application du SVM sous Matlab

3 Application du SVM sous R

4 Application du SVM sous Python

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 189 / 228
6. Application du SVM

Application du SVM sous R

Les codes pour les SVM/SVR sont disponibles dans le package e1071 (David Meyer
et al.).

Ce package inclut di¤érentes fonctions pour :

[..] latent class analysis, short time Fourier transform, fuzzy clustering,
support vector machines, shortest path computation, bagged clustering, naive
Bayes classi…er, ...

Les principales fonctions liées au SVM sont :

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 190 / 228
6. Application du SVM

Les principales fonctions liées au SVM sous R sont :

plot.svm : permet de générer un scatter plot des données d’entrée en mettant en

évidence les classes et les vecteurs de support. En option, cette fonction dessine un
tracé des contours des classes.

predict.svm : prédit les labels basés à partir d’un SVM construit sur un échantillon
d’apprentissage.

svm : est utilisée pour entraîner un SVM. Cette fonction peut être utilisée pour
e¤ectuer une régression, une classi…cation ou l’estimation d’une densité.

write.svm : permet d’exporter un objet de type SVM.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 191 / 228
6. Application du SVM

Exemple de code R

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 192 / 228
6. Application du SVM

Example (SVM)
On considère x = (x1 , x2 )0 2 R2 et un échantillon d’apprentissage de taille n = 10 pour
lequel on observe les données suivantes (cf. tableau infra). Question : en utilisant la
fonction svm de R , retrouvez les résultats obtenus par programmation quadratrique dans
la section 3 (Formalisation du SVM).

Obs. x1,i x2,i yi

1 4 8 1
2 2 4 1
3 4 6 1
4 6 6 1
5 8 8 1
6 6 10 1
7 12 6 1
8 10 6 1
9 8 2 1
10 6 2 1

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 193 / 228
6. Application du SVM

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 194 / 228
6. Application du SVM

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 195 / 228
6. Application du SVM

Pour plus de détail sur ces fonctions, voir (entre autres) :

Meyer D. et al. (2017), Package ’e1071’, TU Wien.

Meyer D. (2017), Support Vector Machines: the Interface to libsvm in package e1071,
Working Paper TU Wien.

Rakotomalala R. (2016), Mise en oeuvre des SVM sous R et Python, Université Lumière
Lyon 2. .

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 196 / 228
6. Application du SVM

1 Application du SVM sous SAS

2 Application du SVM sous Matlab

3 Application du SVM sous R

4 Application du SVM sous Python

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 197 / 228
6. Application du SVM

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 198 / 228
6. Application du SVM

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 199 / 228
 Section 7

Extensions du SVM

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 200 / 228
7. Extensions

1 SVM et scores

2 SVM multi-classes

3 Régression à vecteurs de support (SVR)

4 Extension de type LS-SVRM

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 201 / 228
7. Extensions

1 SVM et scores

2 SVM multi-classes

3 Régression à vecteurs de support (SVR)

4 Extension de type LS-SVRM

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 202 / 228
7.1. SVM et scores

Deux questions :

Comment calculer les probabilités d’appartenance aux classes ?

Comment transformer l’output des SVM en probabilités ?

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 203 / 228
7.1. SVM et scores

Pour n’importe quelle observation x 2 X de l’échantillon d’apprentissage ou de test, ou

pour une observation nouvelle, l’output du SVM est une classi…cation
(
1 si h (x ) 0
yb = g (x ) = sgn (h (x )) =
1 si h (x ) < 0

avec la fonction de décision optimale

h (x ) = h ω , x i + b = ∑ λi yi hxi , x i + b
i 2S

où S désigne l’ensemble des vecteurs de support.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 204 / 228
7.1. SVM et scores

Dé…nition (méthode de Platt)

La méthode de Platt (platt scaling) est une méthode qui a pour objet de transformer
l’output d’un modèle de classi…cation en une distribution de probabilité sur les classes

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 205 / 228
7.1. SVM et scores

Méthode de Platt

La méthode de Platt consiste à utiliser une fonction paramétrique ou non

paramétrique qui permet de mapper les valeurs de h (x ) dans l’intervalle [0, 1].

On peut utiliser ici n’importe quelle fonction de répartition (cdf).

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 206 / 228
7.1. SVM et scores

Exemples :

Loi logistique (fonction sigmoïde simple) :

1
Pr ( y = 1j x ) =
1 + exp ( h (x ))

Modèle Logit : on estime par ML les paramètres (θ 1 , θ 2 ) tels que :

1
Pr ( y = 1j x ) =
1 + exp ( (θ 1 + θ 2 h (x )))

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 207 / 228
7. Extensions

1 SVM et scores

2 SVM multi-classes

3 Régression à vecteurs de support (SVR)

4 Extension de type LS-SVRM

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 208 / 228
7.2. SVM multi-classes

SVM multi-classes

Les SVM peuvent être adaptés pour traiter des problèmes multi-classes.

On suppose que la variable discrète y a k modalités, avec y 2 fm1 , ..., mk g

Il existe deux grandes approches

1 L’approche "un contre tous" (one-against-rest)
2 L’approche "un contre un" (one vs. one ou pairwise)

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 209 / 228
7.2. SVM multi-classes

Approche un contre tous

L’idée consiste simplement à transformer le problème à k classes en k classi…eurs

binaires.

On construit k modèles binaires pour des variables dichotomiques yj :

(
1 si y = mj
yj =
1 sinon

On obtient k fonctions de décision hj (x ), on prédit la classe présentant le score le

plus élévé
yb = mc avec c = arg max hj (x )
j =1,..,k

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 210 / 228
7.2. SVM multi-classes

Approche un contre un

On construit k (k 1) /2 modèles SVM pour chaque paires de modalités. Par

exemple : (
1 si y = mi
yij =
1 si y = mj
On obtient k (k 1) /2 fonctions de décision hij (x ). Le classement est donné par le
vote majoritaire (ou une autre règle).

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 211 / 228
7.2. SVM multi-classes

Approche un contre un

Le nombre de vote Dj (x ) et le classement véri…ent:

yb = mc avec c = arg max Dj (x )

j =1,..,k

k
D j (x ) = ∑ sgn hij (x )
i 6=j ,i =1

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 212 / 228
7. Extensions

1 SVM et scores

2 SVM multi-classes

3 Régression à vecteurs de support (SVR)

4 Extension de type LS-SVRM

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 213 / 228
7.3. Régression à vecteurs de support (SVR)

On considère à présent le cas d’une régression.

Données : f(xi , yi )gi =1,..,n avec xi 2 Rd , y 2 R

Prédicteur : soit β 2 Rd et b 2 R

h (x ) = x > β + b

Norme : q
kh k = k β k = β> β
Critère : moindres carrés
n
∑ (yi h (xi ))2
i =1

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 214 / 228
7.3. Régression à vecteurs de support (SVR)

Dé…nition (SVR)
L’idée de la régression à vecteur de support (SVR) consiste à imposer une contrainte
sur la norme L2 des poids
n
b b
β, b = arg min ∑ (yi h (xi ))2
β2Rd ,b 2R i =1
sc : kh k λ

où λ est un paramètre de pénalisation.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 215 / 228
7.3. Régression à vecteurs de support (SVR)

On obtient ainsi une régression de type ridge (cf. cours Régressions Pénalisées).

Dé…nition (SVR et régression ridge)

La régression à vecteur de support (SVR) peut s’écrire sous la forme d’une régression
ridge
n
b b = arg min
β, b ∑ (yi h (xi ))2 + C kh k2
β2Rd ,b 2R i =1

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 216 / 228
7.3. Régression à vecteurs de support (SVR)

Solution
n
b b = arg min
β, b ∑ (yi h (xi ))2 + C kh k2
β2Rd ,b 2R i =1

La solution est de la forme

1
b
β = X > X + C Id X >Y

avec X = (x1 , ..., xn )> et Y = (y1 , ..., yn )>

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 217 / 228
7.3. Régression à vecteurs de support (SVR)

On cherche un prédicteur sous la forme

n
h (x ) = ∑ αi K (xi , x )
i =1

où K (xi , x ) est une fonction kernel.

Soit Ω = K xi , xj i ,j la matrice de Gram, on dé…nit

kh k2K = α> Ωα

avec α = (α1 , ..., αn )>

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 218 / 228
7.3. Régression à vecteurs de support (SVR)

Dé…nition (SVR et forme duale)

La régression à vecteur de support (SVR) peut s’écrire comme
n
b
α = arg min
α2Rn
∑ (yi Ωα)2 + C α> Ωα
i =1

>
avec α = (α1 , ..., αn ) et Ω = K xi , xj i ,j la matrice de Gram associée au kernel
K (., .).

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 219 / 228
7.3. Régression à vecteurs de support (SVR)

Solution
n
b
α = arg min
α2Rn
∑ (yi Ωα)2 + C α> Ωα
i =1
La solution est de la forme
1
α = ( Ω + C In )
b Y

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 220 / 228
7.3. Régression à vecteurs de support (SVR)

source : www.quora.com

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 221 / 228
7. Extensions

1 SVM et scores

2 SVM multi-classes

3 Régression à vecteurs de support (SVR)

4 Extension de type LS-SVRM

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 222 / 228
7.4. Extension de type LS-SVM

Least Square Support Vector Machine (LS-SVM)

Le LS-SVM et son équivalent pour la régression LS-SVR, ont été introduits par
Suykens et Vandewalle (1999) et Suykens et al. (2002).

Cette méthode a un faible coût de calcul car elle équivaut à résoudre un système
linéaire d’équations au lieu de résoudre un problème de programmation quadratique.

Suykens J. et Vandewalle J. (1999). Least Squares Support Vector Machine Classi…ers.

Neural Processing Letters, 9(3), 293-300.

Suykens J., Van Gestel T., De Brabanter J., De Moor B. et Vandewalle J. (2002). Least
Squares Support Vector Machine. Singapore World Scienti…c.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 223 / 228
7.4. Extension de type LS-SVM

Dé…nition (LS-SVM)
Le problème primal du LS-SVM est dé…ni par

C1 C2 n 2
2 i∑
(ω , b ) = arg min k ω k2 + ξi
ω 2Rd ,b 2R 2 =1
sc : yi (hω, Φ (xi )i + b ) 1 ξ i 8i = 1, ..., n
sc : ξi 0

où (C1 , C2 ) 2 R+2 désigne des coe¢ cients de pénalisation. Cette spéci…cation du

classi…eur LS-SVM s’interprète comme une régression avec une variable dépendante
binaire y = f 1, 1g .

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 224 / 228
7.4. Extension de type LS-SVM

Sachant que y 2 = 1, le programme du LS-SVM peut se réécrire sous la forme

C1 C2 n
2 i∑
(ω , b ) = arg min k ω k2 + [yi (hω, Φ (xi )i + b )]2
ω 2Rd ,b 2R 2 =1
sc : yi (hω, Φ (xi )i + b ) 1 ξ i 8i = 1, ..., n
sc : ξi 0

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 225 / 228
7.4. Extension de type LS-SVM

Solution (LS-SVM)
On peut montrer à partir des conditions du premier ordre, que déterminer la solution
revient à résoudre un système linéaire : c’est le principal avantage du LS-SVM

0 en> ω 0
=
en Ω + γ 1 In b Y

où en désigne le vecteur unité, In la matrice identité de dimension n n, Ω la matrice de

Gram, Y = (y1 , ..., yn )0 et γ = C2 /C1 .

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 226 / 228
7.4. Extension de type LS-SVM

Applications du LS-SVR en risk management

Plusieurs auteurs ont montré les bonnes performances du LS-SVR pour la modélisation
de la LGD, notamment :

Loterman G., Brown I., Martens D., Mues C. & Baesens B. (2012). Benchmarking
Regression Algorithms for Loss Given Default Modeling. International Journal of
Forecasting, 28(1), 161-170.

Nazemi A., Fatemi Pour F., Heidenreich K. & Fabozzi F.J. (2017). Fuzzy Decision Fusion
Approach for Loss-Given-Default Modeling. European Journal of Operational Research,
262(2), 780-791.

Yao X., Crook J. & Andreeva G. (2015). Support Vector Regression for Loss Given Default
Modelling. European Journal of Operational Research, 240(2), 528-538.

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 227 / 228
 Fin du chapitre

Christophe Hurlin (Université d’Orléans)

Christophe Hurlin (Université d’Orléans) Support Vector Machine Septembre 2020 228 / 228