1 Machines à vecteurs supports

loppement, est d’éviter de substituer à l’objectif initial : la discrimination, un

Machines à vecteurs supports ou des problèmes qui s’avèrent finalement plus complexes à résoudre comme
par exemple l’estimation non-paramétrique de la densité d’une loi multidimen-
sionnelle en analyse discriminante.
Résumé
Le principe de base des SVM consiste de ramener le problème de la discri-
Recherche d’un hyperplan, dit de marge optimale (vaste), pour la mination à celui, linéaire, de la recherche d’un hyperplan optimal. Deux idées
séparation de deux classes dans un espace hibertien défini par ou astuces permettent d’atteindre cet objectif :
un noyau reproduisant associé au produit scalaire de cet espace. • La première consiste à définir l’hyperplan comme solution d’un problème
Estimation de l’hyperplan dans le cas linéaire et séparable ; les d’optimisation sous contraintes dont la fonction objectif ne s’exprime
contraintes actives du problème d’optimisation déterminent les vec- qu’à l’aide de produits scalaires entre vecteurs et dans lequel le nombre
teurs supports. Extension au cas non séparable par pénalisation. de contraintes “actives” ou vecteurs supports contrôle la complexité du
Extension au cas non linéaire par plongement dans un espace hil- modèle.
bertien à noyau reproduisant. • Le passage à la recherche de surfaces séparatrices non linéaires est obtenu
Retour au plan du cours par l’introduction d’une fonction noyau (kernel) dans le produit scalaire
induisant implicitement une transformation non linéaire des données vers
un espace intermédiaire (feature space) de plus grande dimension. D’où
1 Introduction l’appellation couramment rencontrée de machine à noyau ou kernel ma-
Les Support Vector Machines souvent traduit par l’appellation de Sépara- chine. Sur le plan théorique, la fonction noyau définit un espace hilbertien,
teur à Vaste Marge (SVM) sont une classe d’algorithmes d’apprentissage ini- dit auto-reproduisant et isométrique par la transformation non linéaire de
tialement définis pour la discrimination c’est-à-dire la prévision d’une variable l’espace initial et dans lequel est résolu le problème linéaire.
qualitative binaire. Ils ont été ensuite généralisés à la prévision d’une variable Cet outil devient largement utilisé dans de nombreux types d’applications
quantitative. Dans le cas de la discrimination d’une variable dichotomique, ils et s’avère un concurrent sérieux des algorithmes les plus performants (agré-
sont basés sur la recherche de l’hyperplan de marge optimale qui, lorsque c’est gation de modèles). L’introduction de noyaux, spécifiquement adaptés à une
possible, classe ou sépare correctement les données tout en étant le plus éloi- problématique donnée, lui confère une grande flexibilité pour s’adapter à des
gné possible de toutes les observations. Le principe est donc de trouver un situations très diverses (reconnaissance de formes, de séquences génomiques,
classifieur, ou une fonction de discrimination, dont la capacité de généralisa- de caractères, détection de spams, diagnostics...). À noter que, sur le plan algo-
tion (qualité de prévision) est la plus grande possible. rithmique, ces algorithmes sont plus pénalisés par le nombre d’observations,
c’est-à-dire le nombre de vecteurs supports potentiels, que par le nombre de
Cette approche découle directement des travaux de Vapnik en théorie de
variables. Néanmoins, des versions performantes des algorithmes permettent
l’apprentissage à partir de 1995. Elle s’est focalisée sur les propriétés de gé-
de prendre en compte des bases de données volumineuses dans des temps de
néralisation (ou prévision) d’un modèle en contrôlant sa complexité. Voir à
calcul acceptables.
ce sujet le chapitre ?? section ?? concernant la dimension de Vapnik Cherno-
venkis qui est un indicateur du pouvoir séparateur d’une famille de fonctions Le livre de référence sur ce sujet est celui de Schölkopf et Smola (2002).
associé à un modèle et qui en contrôle la qualité de prévision. Le principe De nombreuses présentations des SVM sont accessibles sur des sites comme
fondateur des SVM est justement d’intégrer à l’estimation le contrôle de la par exemple : www.kernel-machines.org. Guermeur et Paugam-Moisy
complexité c’est-à-dire le nombre de paramètres qui est associé dans ce cas au (1999) et « Apprentissage Artificiel : Méthodes et Algorithmes » de Cornuéjols
nombre de vecteurs supports. L’autre idée directrice de Vapnik dans ce déve- et Miclet (2002) en proposent en français.
 2 Machines à vecteurs supports

3 Les SVM linéaires

3.1 Le problème de discrimination linéaire
Un problème de discrimination est dit linéairement séparable lorsqu’il existe
une fonction de décision linéaire (appelé aussi séparateur linéaire), de la
forme D(x) = signe f (x) avec f (x) = v > x + a, v ∈ Rp et a ∈ R,

classant correctement toutes les observations de l’ensemble d’apprentissage

(D(xi ) = yi , i ∈ [1, n]). La fonction f est appelée fonction caractéristique.
C’est un problème particulier qui semble très spécifique, mais qui permet d’in-
troduire de manière pédagogique les principaux principes des SVM : marge,
programmation quadratique, vecteur support, formulation duale et matrice de
gram. Nous allons ensuite généraliser au cas des observations non séparables et
non linéaires par l’introduction de variables d’écart et de noyaux. Ces différent
type de problèmes sont illustrés figure 1.
A toute fonction de décision et donc aux fonction de décision linéaire ont peut
associer une frontière de décision :
F IGURE 1 – Exemples de quatre types de problèmes de discrimination binaire
où il s’agit de séparer les points bleus des croix rouges. La frontière de décision
∆(v, a) = {x ∈ Rp  v > x + a = 0}

est représentée en noir.

Tout comme la fonction de décision linéaire, cette frontière de décision est dé-
2 Le problème de discrimination binaire finie à un terme multiplicatif prés dans le sens ou la frontière définie par le
couple (v, a) est la même que celle engendrée par (kv, ka) ∀ k ∈ R. Cela
Le problème abordé est celui de la discrimination binaire. Il s’agit de trou- est lié à la définition de l’hyperplan affine associé à la fonction caractéristique.
ver un moyen permettant de construire une fonction de décision associant à Pour garantir l’unicité de la solution on peut soit considérer l’hyperplan stan-
chaque observation sa classe. Nous allons nous traiter ce problème dans un dard (tel que kvk = 1) soit l’hyperplan canonique par rapport à un point x (tel
cadre probabiliste spécifique et poser que les formes à discriminer sont des que v > x + a = 1).
vecteurs x ∈ Rp . Le cadre probabiliste du problème consiste à supposer
l’existence d’une loi inconnue P(x, y) sur (Rp , {−1, 1}). Le problème de dis- 3.2 La marge d’un classifieur
crimination vise à construire un estimateur de la fonction de décision idéale
D : Rp → {−1, 1}, minimisant pour toutes les observations x la probabi- Pour un échantillon donnée, il est possible d’associer deux marges à un même
lité d’erreur P(D(x) 6= y | x). Pour construire cet estimateur, on suppose classifieur linéaire : sa marge géométrique et sa marge numérique. La marge
l’existence d’un échantillon {(xi , yi ), i = 1, n} (aussi appelé ensemble d’ap- géométrique m d’un échantillon linéairement séparable est donnée par la plus
prentissage), i.i.d. de loi parente P(x, y) inconnue. petite distance d’un point de l’échantillon à la frontière de décision. La marge
numérique µ est donnée elle par la plus petite valeur de la fonction de décision
 3 Machines à vecteurs supports

de décision linéaires séparant cet échantillon. La notion de marge offre un cri-

tère de choix parmi toutes ces solutions en admettant que maximiser la marge
|v > x + a| c’est aussi maximiser la confiance et donc minimiser la probabilité d’erreur
d(x, ∆) =
>
(xr , v xr + a) kvk associée au classifieur. Nous allons résoudre le problème suivant :
m : la marge géométrique
max min dist(xi , ∆(v, a))
d(xr , ∆) = m v,a i∈[1,n]

µr
| {z }
marge : m
d(xb , ∆)
(xr , 0)
En introduisant explicitement la marge comme une variable, ce problème se
(xb , 0) réécrit comme un problème d’optimisation sous contraintes :

µb

 max

v,a
m
∆ µ = |v > x + a| |v > xi + a|
(xb , v > xb + a) la marge numérique  avec min
 ≥m
i∈[1,n] kvk
∆ = {x ∈ R2 | v > x + a = 0}
la frontière de décision C’est un problème est mal posé dans le sens ou si (v, a) est une solution,
(kv, ka), ∀ 0 < k l’est aussi. Une manière de traiter cette difficulté est d’ef-
v a
fectuer le changement de variable : w = mkvk et b = mkvk Le problème se
réécrit alors :
F IGURE 2 – iIllustration des deux notions de marge sur un exemple de discri- 
mination linéaire séparable en dimension deux.  max 1
w,b kwk
 avec y (w> x + b) ≥ 1 ; i = 1, n
i i
1
atteinte sur un point de l’échantillon. Leur définition mathématique est : puisque kwk = m. Cela revient à fixer à un la marge numérique du classifieur
recherché (celui de norme minimale). La formulation « classique » des SVM
marge géométrique marge numérique
s’obtient alors en minimisant kwk2 au lieu de maximiser l’inverse de la norme,
m = min dist(xi , ∆(v, a)) µ = min |v > xi + a| ce qui donne le problème suivant qui admet la même solution que le problème
i∈[1,n] i∈[1,n]
précédent.
La figure 2 illustre ces deux notions de marge pour un exemple en deux di-
mensions. On voit que pour une frontière de décision donnée, la marge géo- Définition 3.1 (SVM sur des données linéairement séparables)
métrique m est fixée alors que la marge numérique µ dépend de la « pente » Soit {(xi , yi ); i = 1, n} un ensemble de vecteurs formes étiquetées avec
de l’hyperplan de décision (donc de kvk). En effet, pour une observation don- xi ∈ Rp et yi ∈ {1, −1}. Un séparateur à vaste marge linéaire (SVM
née, les deux marges forment les cotés adjacents d’un triangle rectangle dont et support vector machine) est un discriminateur linéaire de la forme :
l’hypoténuse est définie par la fonction caractéristique v > x + a. D(x) = signe w> x + b où w ∈ Rp et b ∈ R sont donnés par la résolution

du problème suivant :
3.3 Maximisation de la marge d’un classifieur
min 21 kwk2
(
Lorsque des observations sont linéairement séparables, comme l’illustre la fi- w,b

gure 1 (en haut à gauche) il existe dans le cas général une infinité de frontières avec yi (w> xi + b) ≥ 1 i = 1, n
 4 Machines à vecteurs supports

Ce problème d’optimisation sous contraintes est un programme quadratique de d’expliciter son lagrangien. Dans le cas des SVM il s’écrit :
la forme : Xn
1 2 >


(
1 >
min 2 z Az − d z > L(w, b, α) = 2 kwk − α i y i (w x i + b) − 1
z i=1
avec Bz ≤ e
où les αi ≥ 0 sont les multiplicateurs de Lagrange associés aux contraintes.
  Les conditions d’optimalité de Karush, Kuhn et Tucker du programme qua-
I 0
où z = (w, b)> ∈ Rp+1 , d = (0, . . . , 0)> ∈ Rp+1 , A = , I est dratique associé aux SVM permettent de caractériser la solution du problème
0 0 primal (w∗ , b∗ ) et les multiplicateurs de lagrange α∗ associés par le système
la matrice identité de Rp , B = −[diag(y)X, y], e = −(1, . . . , 1)> ∈ Rn , d’équations suivant :
y ∈ Rn le vecteur des signes des observations et X la matrice n × d des n
observations dont la ligne i est le vecteur x>
i . Ce problème est convexe puisque
X
stationarité w∗ − αi∗ yi xi = 0
la matrice A est semidéfinie positive. Il admet donc une solution unique (qui i=1
existe puisque le problème est linéairement séparable par hypothèse) et les Xn

conditions nécessaires d’optimalité du premier ordre sont aussi suffisantes. Ce αi∗ yi = 0

problème (dit primal) admet une formulation duale équivalente qui est aussi i=1
complementarité αi∗ yi (w∗> xi + b∗ ) − 1 = 0


i = 1, . . . , n
un programme quadratique.
admissibilité primale yi (w∗> xi + b∗ )) ≥ 1 i = 1, . . . , n
La résolution du problème des SVM sur des données linéairement séparables admissibilité duale αi∗ )) ≥ 0 i = 1, . . . , n
peut se faire directement (à partir de la formulation primale) par exemple en
utilisant une méthode stochastique de type Gauss-Seidel, une méthode d’en- Les conditions de complémentarité permettent de définir l’ensemble A des in-
semble actif, un algorithme de point intérieur, de Newton avec région de dices des contraintes actives (ou saturées) à l’optimum dont les multiplicateurs
confiance ou type gradient conjugué. Cependant, il est intéressant de passer de Lagrange αi∗ > 0 sont strictement positifs :
par la formation duale de ce problème :
A = {i ∈ [1, n]  yi (w∗> xi + b∗ ) = 1}

• le problème dual est un programme quadratique de taille n (égal au
nombre d’observations) qui peut s’avérer plus facile à résoudre que le Pour les autres contraintes, la condition de complémentarité implique que leur
problème primal, mutiplicateur de Lagrange est égal à zéro et que l’observation associée vérifie
• la formulation duale fait apparaître la matrice de Gram XX > ce qui per- strictement l’inégalité ∀j ∈ / A, yj (w∗> xj + b∗ ) > 1. La solution (w, b, αA )
met dans le cas général (non linéaire) d’introduire la non linéarité à travers vérifie le système linéaire suivant :
des noyaux.  >
w −XA Dy αA =0
Afin de retrouver cette formulation duale nous allons maintenant expliciter

−Dy XA w −by A = −eA
le lagrangien du problème et les conditions d’optimalité de Karush, Kuhn et
−y > A αA =0

Tucker. Ces conditions vont nous permettre d’introduire la notion importante
de vecteur support. avec Dy = diag(y A ), αA = α(A) , y A = y(A) et XA = X(A; :). Le
premier sous système (qui est la condition de stationnarité pour w) est particu-
3.4 Conditions d’optimalité et vecteurs supports lièrement important car il stipule que la solution du problème s’écrit :
Afin d’expliciter les conditions nécessaires d’optimalité du premier ordre il
X
w= αi yi xi
est classique lorsque l’on traite d’un problème d’optimisation sous contraintes i∈A
 5 Machines à vecteurs supports

A l’optimum, le vecteur w est une combinaison linéaire des observations xi Résoudre le problème revient à rechercher parmi les exemples disponibles
liées aux contraintes actives i ∈ A et pour lesquelles |w∗> xi + b∗ | = 1. Ces ceux qui vont devenir vecteurs supports ce qui nous donne l’ensemble A.
observations sont appelées vecteurs supports dans le sens où elles supportent Une fois cet ensemble connu, la résolution du problème s’effectue en utilisant
l’hyperplan de discrimination puisque leur marge numérique est égale à un. le premier sous système pour éliminer w. Le problème devient :
Les autres données n’interviennent pas dans le calcul et leur marge numérique
est strictement supérieure à un. La figure 3 vient illustrer le fait que les vec- 
Dy XA XA>
Dy αA +by A = eA
teurs support définissent la frontière de décision. La fonction de décision peut >
y A αA =0
alors s’écrire de deux formes différentes selon que l’on considère les variables
primales ou les variables duales :
le cardinal de A est égal au nombre d’inconnues (p + 1) et la solution est :
d
X X
αi yi (x> xi ) + b


D(x) = sign f (x) avec f (x) = wj xj +b = y> >
A (Dy XA XA Dy )
−1
eA >
b= > >
et αA = (Dy XA XA Dy )−1 (e − by A )
j=1 i∈A y A (Dy XA XA Dy )−1 y A

>
classe 1
ce qui permet d’utiliser le fait que la matrice Dy XA XA Dy est définie positive.
classe 2
frontière de décision 6 L’algorithme associé est :
marge géométrique
vecteurs supports

A LGORITHME 1 : calcul de la solution des SVM connaissant A

Xa = diag(y(A))*X(A, :) ; %A est l’ensemble actif
U = chol(Xa*Xa’) ; %factorisation de Choleski
a = U\ (U’\ e(A)) ; %résolution des systèmes tri sup
c = U\ (U’\ y(A)) ;
b = (y(A)’*a)\(y(A)’*c) ;
alpha = U\ (U’\ (e(A) - b*y(A))) ;
w = Xa’*alpha ;

F IGURE 3 – illustration de la notion de vecteur support dans le cas d’un pro-

blème linéairement séparable. Les vecteurs supports des deux classes sont en-
tourés par un rond rouge. Le tableau suivant récapitule les deux cas possibles.
3.5 Formulation duale et biduale
Le dual de Wolfe dual du problème des SVM séparables est :
observation inutile observation importante  n
vecteur support
X
1
kwk2 αi yi (w> xi + b) − 1


max −


 2
contrainte non saturée contrainte active  w,b,α

 i=1
i∈/A i∈A avec αi ≥ 0 i = 1, . . . , n
 n n
αi = 0 0 < αi 


 w−
X
αi yi xi = 0 et
X
αi yi = 0
yi (w∗> xi + b∗ ) > 1 yi (w∗> xi + b∗ ) = 1

i=1 i=1
 6 Machines à vecteurs supports

L’élimination de la variable primale w donne la formulation duale du pro- Primal Dual

blème des SVM :
n X n n


1 >
− e> α
X X
> minn 2 α Gα
1

min α α y y x x − αi
 1 2

min 2 kwk
j i i j j i
 

 α 2   α∈R
p
w∈R ,b∈R >

i=1 j=1 i=1 avec y α=0
n avec yi (w> xi + b) ≥ 1 
 et 0 ≤ αi i = 1, n
 X
avec αi yi = 0 et 0 ≤ αi i = 1, . . . , n
 
i = 1, n

 

i=1
• n inconnues (les influences des
que l’on écrit matriciellement : • p + 1 inconnues (les influences observations)
 des variables) • n contraintes de boites
1 >
 minn
 α∈R 2 α Gα − e> α • n contraintes linéaires • G matrice des influences de
D > • QP de forme générale chaque couple de points
avec y α=0
 • préférable lorsque d < n • préférable lorsque d ≥ n
 0 ≤ αi i = 1, n
avec G = Dy XX > Dy la matrice symétrique n × n de terme général Gij = Le problème est essentiellement pratique et lié à la mise en œuvre. Cette ques-
yi yj x>
j xi . Le Lagrangien de ce problème dual est : tion n’est pas résolue et il existe des approches primales et des approches
n duales très efficaces permettant de traiter un grès grand nombre de données
X
1 > > > en grande dimension. Cependant, quelle que soit l’approche choisie, il semble
LD (α, β, γ) = 2 α Gα − e α + β y α − γi αi
i=1 important de ne pas trop pousser l’optimisation et que son arrêt prématuré peut
offrir des gains de performance (technique appelée early stoping).
où β est le multipicateur associé à la contrainte d’égalité et γi ≥ 0 les mul-
tipicateurs de Lagrange associés aux contraintes d’inégalité. On en déduit le 3.6 Le cas des données non séparables
problème bidual associé :
 Dans le cas où les données ne sont pas linéairement séparables, il est pos-
1 >
 max
 β∈R,γ∈Rn − 2 α Gα sible de suivre la même démarche adoptée dans le cas séparable au prix de
avec Gα − e + βy − γ = 0 l’introduction de variables d’écart. L’idée est de modéliser les erreurs poten-


0 ≤ γi i = 1, n tielles par des variables d’écart positives ξi associées à chacune des observa-
tions (xi , yi ), i ∈ [1, n]. Dans le cas où le point vérifie la contrainte de marge
En posant w = Xdiag(y)α et en identifiant b et β on retrouve la formula- i (w> xi + b) ≥ 1, la variable d’écart est nulle. On a donc les deux cas sui-
y
tion initiale du problème primal. Le biais b est donné par le multiplicateur de vants :
Lagrange associé à la condition d’égalité y > α = 0.
pas d’erreur : yi (w> xi + b) ≥ 1 ⇒ ξi = 0
Ces deux formulations équivalentes primale et duale méritent d’être mis en erreur : yi (w> xi + b) < 1 ⇒ ξi = 1 − yi (w> xi + b) > 0
parallèle pour mieux faire ressortir leurs avantages respectifs et permettre de
On associe à cette définition une fonction cout appelée « cout charnière » du
décider quand il est préférable d’utiliser la formulation primale et quand utili-
fait de la forme de son graphe représentée figure 4 :
ser le dual. Le tableau suivant récapitule les principales caractérises des SVM
linéaires primales et duales. ξi = max 0, 1 − yi (w> xi + b)


 7 Machines à vecteurs supports

Le problème consiste alors à simultanément maximiser la marge et minimiser permet de poser le problème sous la forme suivante :
n

 min 1 kwk2 + C X ξ d

d i=1 i


w,b,ξ 2
classe 1
(P rimal linéaire SVM)
classe 2
frontière de décision 6
cout 0/1
max(0,1ïz)

 avec yi (w> xi + b) ≥ 1−ξi i = 1, n
2
marge géométrique

max(0,1ïz)
ξi ≥ 0 i = 1, n
vecteurs supports


Comme nous l’avons fait précédemment, on recherche un point selle du la-

Cout
grangien :
j
||w||
w’x + b = 1 n n n
1 CX d X
X
αi yi (w> xi +b)−1+ξi −
1
w’x + b = 0 L(w, b, α, β) = kwk2 + ξi − βi ξ i
2 d i=1 i=1 i=1
0
w’x + b = ï1 ï1
avec des multiplicateurs de Lagrange αi ≥ 0 et βi ≥ 0. Le calcul des gradients
0
z = y (w’ x + b)
1

est identique par rapport à w et b. Dans le cas où d = 1, la dérivée partielle

F IGURE 4 – illustration de la notion d’écart (à gauche) et de la fonction de du lagrangien par par rapport aux variables d’écart s’écrit : ∂ξi L(w, b, α) =
cout charnière (droite). Dans cet exemple tous les écarts sont nuls sauf un, C −αi −βi . Cette condition supplémentaire de stationnarité permet d’éliminer
celui du point bleu mal classé. Cet écart mesure la distance du point à la marge les β car :
numérique de l’hyperplan séparateur. βi ≥ 0 et C − αi − βi = 0 ⇒ αi ≤ C
L’ensemble de ces conditions nous permet d’obtenir la formulation duale qui
est le programme quadratique à résoudre pour obtenir la solution des SVM.
la somme des terme d’erreurs à la puissance d (avec typiquement d = 1 ou 2).
Il s’écrit alors : Définition 3.2 (formulation duale des SVM L1) Le problème dual des SVM
avec une variable d’écart et le cout charnière (appelé aussi L1 SVM) s’écrit :

minn 12 α> Gα − e> α
  1 2
2 kwk
 
 
 α∈R
n


 min
 X (Dual SVM L1) avec y > α = 0
1
ξid

w,b,ξ  d 
0 ≤ αi ≤ C i = 1, n
 
i=1
yi (w> xi +

avec b) ≥ 1−ξi



avec G la matrice symétrique n × n de terme général Gij = yi yj x>
j xi .

ξi ≥ 0 i = 1, n


Ce problème reste un programme quadratique avec des contraintes de boites.

On constate que si toutes les variables d’écart ξi = 0, on retrouve le problème Les multiplicateurs α représentant l’influence de chacun des exemples sont
des SVM linéairement séparables. La résolution du problème précédent peut maintenant bornés supérieurement par C qui représente l’influence maximale
s’effecteur grâce à l’introduction d’un terme d’équilibrage C > 0 fixé qui permise pour un exemple.
 8 Machines à vecteurs supports

Dans le cas où d = 2, la contrainte de positivité sur les variables d’écart est

inutile et le problème dual s’écrit (L2 SVM) :
 1 >
 minn
 α∈R 2
α (G + 1
C
I)α − e> α
(Dual L2 SVM) avec >
y α=0

0 ≤ αi i = 1, n


avec I la matrice identité. Dans ce cas, la matrice G est « préconditionnée »

d’un facteur C1 .

3.7 Autres formulations et généralisation

F IGURE 5 – Exemple de discrimation de données normalisées par SVM (la
Il existe d’autres manières de poser le problème permettant d’arriver au même frontière est en noir) et par SVDD avec une marge de 0.05 (la frontière de
résultat et qui permettent d’éclairer différents aspects des SVM. décision est en bleu).
Si l’on considère la minimisation de la distance entre les enveloppes convexes
de chacune des classes on retrouve le problème dual des SVM :

 minn ku − vk2 linéaire avec sélection de variable). Il existe de nombreuses autres variantes.
 α∈R
 X X Citons le cas q = 0 L0 SVM (le problème est alors non convexe), et elastic net

 avec u =

α i xi , v= α i xi SVM avec à la fois un terme avec q = 1 et un autre avec q = 2 qui débouche
{i|yi =1} {i|yi =−1} aussi sur un programme quadratique. Les Ci permettent de moduler l’influence
 X X
αi = 1, 0 ≤ αi i = 1, n



 αi = 1, des observations par exemple en fonction de leur classe (utile dans le cas de

{i|yi =1} {i|yi =−1} classes déséquilibrées).
et Une autre approche (appelée en anglais support vector data description ou
2 2
kuk − kvk 2 SVDD) consiste à rechercher l’enveloppe sphérique de rayon minimal englo-
u> x − v > x et b =


f (x) = 2 2 bant les points d’une classe et excluant ceux de l’autre classe. Le rayon de cette
ku − vk ku − vk
enveloppe est noté R et m désigne une marge de confiance sur cette classifica-
Une autre manière de poser le problème consiste à utiliser une formulation de tion. Le problème posé s’écrit pour C et m fixés :
type « régularisation du risque empirique ». Dans ce formalisme on considère  X X −
que m’on cherche à minimiser une forme pénalisée du cout charnière. Le cout 
 min n R2 +C
 c,R,ξ∈R ξi+ + ξi
yi =1 yi =−1
charnière est vu comme un terme d’attache aux données et la pénalité un terme
 avec kxi − ck2 ≤ R2 −m+ξi+ , ξi+ ≥ 0 quand yi = 1
de régularisation : 

kx − ck2 ≥ R2 +m−ξ − , ξ − ≥ 0 quand y = −1
i i i i
n

d C’est un programme linéaire avec des contraintes quadratique dont le dual
X
min 1 q
q kwkq + 1
d Ci max 1 − yi (w> xi + b) ≥ 1, 0
w,b
i=1
est un programme quadratique analogue à celui des SVM. Pour m = 0 on a
la forme originale des SVDD. Dans le cas particulier où les observations sont
avec q = 2, d = 1 et les Ci identiques pour les SVM que nous avons introduits, normées (kxi k = 1) et pour m = 1, le programme quadratique dual des SVDD
Pd
q = 1 (kwk1 = j=1 |wj |) et d = 1 LP SVM (les SVM en programmation est (pratiquement) identique à celui des SVM (voir l’illustration figure 5).
 9 Machines à vecteurs supports

4 Le cas non linéaire : les noyaux complexes comme des images, des graphes, des protéines où des automates
pour ne citer qu’eux. Nous n’avons donc pas besoin de faire d’hypothèse sur
Dans le cas général, la frontière optimale est non linéaire. Dans le cadre des la nature du domaine des observations X et un noyau k est défini de manière
SVM, la prise en compte de non linéarités dans le modèle s’effectue par l’in- générale comme une fonction de deux variables sur R :
troduction de noyaux non linéaires. De manière inattendue, l’utilisation de
noyaux ne modifie pas fondamentalement la nature des SVM (pourvu que l’on k : X , X −→ R (x, x0 ) 7−→ k(x, x0 )
travaille dans le dual).
Définition 4.1 (Matrice de Gram) La matrice de Gram du noyau k(., .) pour
Ce noyau est une fonction k qui associe à tout couple d’observations (x, x0 ) les observations {x , . . . , x , . . . , x } (pour tout entier n fini) est la matrice
1 i n
une mesure de leur « influence réciproque » calculée à travers leur corrélation carrée K de taille n et de terme général K = k(x , x ).
ij i j
ou leur distance. Des exemples typiques de noyaux sont le noyaux polynômial
kx−x0 k2
k(x, x0 ) = (c + hx, x0 i)p et le noyau gaussien k(x, x0 ) = e− 2σ2 . Etant Définition 4.2 (Noyau positif) Un noyau k est dit positif si, pour tout entier
donné le noyau k, la fonction de décision s’écrit D(x) = signe(f (x) + b) et : n fini et pour toutes les suite de n observations possibles {xi , i = 1, n}, la
X X matrice de Gram associée est une matrice symétrique définie positive.
cas linéaire : f (x) = αi yi x>
i x non linéaire : f (x) = αi yi k(xi , x)
i∈A i∈A L’intéret des noyaux positifs c’est qu’il est possible de leur associer un pro-
La fonction de discrimination est une combinaison linéaire des noyaux dont le duit scalaire. Les noyaux dit de Mercer sont des noyaux positifs définis sur un
signe de l’influence dépend de la classe. L’ensemble actif A, les coefficients αi ensemble compact.
associés et le biais b sont donné par la résolution du même problème dual que Construction des noyaux
dans le cas des SVM linéaires (définition 3.2). Seule la définition de la matrice
G change (mais pas sa taille) : Il existe deux façons de construire un noyau positif :

cas linéaire : Gij = yi yj x> 1. soit on s’appuie sur une transformation Φ(x) de X sur un espace H muni
i xj non linéaire : Gij = yi yj k(xi , xj )
d’un produit scalaire et l’on défini le noyau à travers ce produit scalaire :
L’idée ici est de considérer dans le dual l’influence de chacune des observations k(x, x0 ) = hΦ(x), Φ(x0 √ )iH . Par exemple si l’on considère x = (x1 , x2 )
dans la construction de la solution. Le calcul de cette influence passe par la dans R2 et Φ(x) = (x21 , 2x1 x2 , x22 ) est explicite. Dans ce cas, H est de
résolution d’un programme quadratique de taille n (le nombre d’observations). dimension 3 et le produit scalaire dans R3 s’écrit :
L’utilisation de noyaux permet d’introduire de la non linéarité sans modifier la hΦ(x), Φ(x0 )i = x21 x02 0 0 2 02
1 + 2x1 x2 x1 x2 + x2 x2
complexité algorithmique du problème à résoudre.
= (x1 x01 + x2 x02 )2
Nous allons maintenant détailler le cadre théorique et le mécanisme d’action
2
des noyaux. = x> x0
= k(x, x0 ).
4.1 Les noyaux
Définition des noyaux 2. soit on utilise les propriétés algèbriques des noyaux positifs :
• un noyau séparable est un noyau positif,
Outre le passage au non linéaire, l’utilisation de noyaux permet une autre gé- • la somme de deux noyaux positifs est un noyau positif,
néralisation très utile dans la pratique : la définition des SVM sur des objets • le produit de deux noyaux positifs est un noyau positif,
 10 Machines à vecteurs supports

• le produit tensoriel ainsi la somme directe de deux noyaux positifs est La construction de noyaux sur des structures complexes donne lieu à de nom-
un noyau positif, breux développement « d’ingénierie de noyaux » spécifique aux domaines
• le passage à la limite conserve la positivité : si la limite d’une suite de d’applications concernés qui utilisent les techniques de construction présen-
noyaux positif existe, c’est aussi un noyau positif. tées ci-dessus.
On peux ainsi par exemple démontrer la positivité du noyau gaussien.
4.2 Cadre fonctionnel des noyaux
exp(−kx − x0 k2 ) = exp(−kxk2 − kx0 k2 + 2x> x0 )
= exp(−kxk2 ) exp(−kx0 k2 ) exp(2x> x0 ) Etant donné un noyau k, il est possible de représenter des observations x par
une fonction définie par la transformation Φ(x) = k(x, •) (appelée kernel
Puisque x> x0 est un noyau positif et la fonction exp est la limite map). Il se trouve alors que l’espace H dans lequel on plonge les observations
d’un développement en série à coefficients positifs, exp(2x> x0 ) est aussi peut être complètement défini ainsi que sa topologie par le noyau considéré ce
un noyau positif. La fonction exp(−kxk2 ) exp(−kx0 k2 ) étant séparable qui présente de nombreux avantages. Plus précisément, H admet une structure
c’est un noyau positif, ce qui permet de conclure sur la positivité du noyau d’espace de Hilbert à noyau reproduisant (EHNR).
gaussien, le produit de deux noyaux positifs étant un noyau positif.
Définition 4.3 (Espace de Hilbert à noyau reproduisant ) Soit H un espace
Exemples de noyaux de Hilbert muni de son produit scalaire h•, •iH . H est un EHNR si , ∀x ∈ X
Les noyaux positifs se divisent en deux grandes familles principales : les fixé, il existe une fonction k(x, •) ∈ H symétrique telle que :
noyaux radiaux qui dépendent d’une distance et les noyaux projectifs qui sont ∀f ∈ H, f (x) = hf, k(x, •)iH
définis à partir d’un produit scalaire.
Le noyau joue ici le rôle de fonctionnelle d’évaluation et permet d’accéder à la
type nom  2 k(s,
 t) valeur de la fonction en tout point x.
r
radial gaussien exp − σ , r = ks − tk
Théorème 4.4 (EHNR et noyaux positifs) A tout noyau positif on peut asso-
radial laplacien exp(−r/σ)
2 cier un Espace de Hilbert à noyau reproduisant et réciproquement.
radial rationnel 1 − r2r+σ
r p 2
exp(− r )


radial loc. gauss. max 0, 1 − 3σ C’est ce théorème qui permet d’affirmer que choisir de travailler avec un noyau
P (sk −tσk )2 k consiste à rechercher f la partie fonctionnelle de la solution dans le EHNR
non stationnaire χ2 exp(−r/σ), r = k sk +tk
projectif polynomial (s> t)p associé à ce noyaux. Ce cadre fonctionnel présente certains avantages :
projectif affine >
(s t + σ)p • l’universalité puisque, pour certaines familles de noyaux, toute fonction
s> continue peut être approchée arbitrairement par un élément de l’EHNR,
projectif cosinus  t/kskktk  • une certaine « confiance » puisque la convergence des fonctions implique
s> t
projectif correlation exp −σ
kskktk la convergence ponctuelle car ∀x ∈ X :
TABLEAU 1 : Exemples de noyaux pour X = Rp .
∀f, fn ∈ H, |f (x) − fn (x)| ≤ kk(x, .)kH ||f − fn ||H
La plus part de ces noyaux dépendent d’un paramètre σ appelé « largeur de • la régularité des fonctions est contrôlée par leur norme
bande » dont le réglage est souvent critique pour le bon fonctionnement de la
méthode. |f (x) − f (x0 )| ≤ kf kH ||k(x, .) − k(x0 , .)||H
 11 Machines à vecteurs supports

• la possibilité de représenter les fonction comme une combinaison linéaire où les αi ≥ 0 et les βi ≥ 0 sont les multiplicateurs de Lagrange asso-
d’exemples (équation 1), ciés aux contraintes. Les conditions d’optimalité de Karush, Kuhn et Tucker
• la possibilité de construire des noyaux à travers la définition d’un EHNR. du problème qui permettent de caractériser la solution du problème primal
(f ∗ , b∗ , ξ ∗ ) et les multiplicateurs de lagrange α∗ et β ∗ associés s’écrivent :
4.3 Les SVM : le cas général n
X
Définition 4.5 (SVM (L1)) Soit {(xi , yi ); i = 1, n} un ensemble de vecteurs stationarité f ∗ (•) − αi∗ yi k(xi , •) =0
formes étiquetées avec xi ∈ X et yi ∈ {1, −1}. Soit H un EHNR de noyau i=1
n
k. Un séparateur à vaste

marge (SVM) est un discriminateur de la forme :
X
αi∗ yi =0
D(x) = signe f (x) + b où f ∈ H et b ∈ R sont donnés par la résolution du i=1
problème suivant pour un C ≥ 0 donné : C − αi∗
− βi∗
=0 i = 1, n
 1 2
Pn complementarité αi∗ yi (f ∗ (xi ) + b∗ ) − 1 + ξi∗ =0 i = 1, n
 min
 f ∈H,b∈R 2 kf kH + C i=1 ξi βi∗ ξi∗ ) =0 i = 1, n
(SV M L1) avec yi (f (xi ) + b) ≥ 1 − ξi i = 1, n admissibilité primale yi (f ∗ (xi ) + b∗ ) + ξi∗ ) ≥1 i = 1, n
ξi∗ ))


0 ≤ ξi i = 1, n ≥0 i = 1, n
admissibilité duale αi∗ )) ≥0 i = 1, n
Théorème 4.6 (Solution des SVM) La partie fonctionnelle de la solution du βi∗ )) ≥0 i = 1, n
problème des SVM s’écrit comme une combinaison linéaire des fonctions
Les conditions de complémentarité βi∗ ξi∗ = 0 permettent de définir l’ensemble
noyau pris aux points supports :
IC des indices pour lesquels βi∗ = 0. Pour cet ensemble, la troisième condition
∗
(1) de stationnarité implique αi = C. Pour les indices n’appartenant pas à IC , βi
X
f (x) = αi yi k(x, xi )
i∈A
peut être éliminé et cette même condition de stationnarité couplée aux condi-
tions d’admissibilité duale stipule que 0 ≤ αi ≤ C. Une fois les βi éliminés, le
où A désigne l’ensemble des contraintes actives et les αi les solutions du pro- système d’équation se traite comme dans le cas linéaire et conduit au problème
gramme quadratique suivant : dual (2).
Les contraintes initiales (donc les exemples) sont maintenant réparties dans

 minn 12 α> Gα − e> α
 α∈R
trois ensembles illustrés par la figure 6 : IC quand αi = C , I0 pour les αi = 0
(SV M dual) avec y > α = 0 (2)
 et Iα lorsque 0 ≤ αi ≤ C, et l’ensemble des contraintes actives A = Iα ∪ IC .
 0 ≤ αi ≤ C i = 1, n
La plus part des variantes présentées dans le cas linéaire s’étend au cas non
où G est la matrice n×n de terme général Gij = yi yj k(xi , xj ). Le biais b à la linéaire en remplaçant le vecteur w par la fonction f :
valeur du multiplicateur de Lagrange de la contrainte d’égalité à l’optimum.
linéaire non linéaire
x k(•, x)
La démonstration de ce théorème reprend la démarche adoptée dans le cas
kwk kf kH
linéaire puisque le lagrangien s’écrit : >
w xi f (xi ) = hf, k(•, xi )iH
n n n
Ce mécanisme très général et s’adapte à de nombreuses autres méthodes li-
X X X
L = 21 kf k2H + C


ξi − αi yi (f (xi ) + b) − 1 + ξi − βi ξi
i=1 i=1 i=1
néaires comme la régression linéaire, l’analyse en composantes principale ou
 12 Machines à vecteurs supports

L’estimation des probabilités a posteriori permet d’énoncer quelques faits à

propos des SVM :
• dans leur forme générale, avec le noyau adéquat, les SVM sont univer-
sellement consistent (l’erreur de classification des SVM converge vers
l’erreur de Bayes)
• avec les mêmes hypothèses, les SVM convergent vers la règle de bayes
• mais il n’est pas possible de construire un estimateur consistant des pro-
données inutiles données importantes données suspectes babilités a posteriori du fait de la parcimonie),
bien classées support • on peut en revanche donner un intervalle de confiance sur cette probabilité
I0 , αi =
0 Iα , 0 < αi
< C IC , αi =
C qui nécessite l’estimation d’un autre paramètre fonctionnel.
yi f (xi ) + b > 1 yi f (xi ) + b = 1 yi f (xi ) + b < 1
5.2 Les SVM multiclasses
F IGURE 6 – Exemple de répartition des observations en trois ensembles. Les
L’adaptation des SVM bi classes au cas multiclasse peut se faire de trois façons
observations « inutiles » sont en violet sur la figure de gauche, les points sup-
différentes. Le choix va dépendre de la taille du problème.
ports sont en jaune sur la figure du milieu et les points mal classés sont en vert
sur la figure de droite. 1. L’approche un contre tous consiste à entrainer un SVM biclasse en utili-
sant les élément d’une classe contre tous les autres. Il s’agit de résoudre
le filtrage linéaire. L’extension est plus délicate dans le cas de norme 1 ou 0. Le de l’ordre de c problèmes SVM chacun de taille n.
recours au noyau passe alors par l’utilisation d’un dictionnaire de fonctions. 2. L’approche un contre un : consiste à entrainer c(c−1) SVM sur chacun
2
des couples de classes, puis à décider la classe gagnante soit par un vote
5 Autour des SVM majoritaire soit en post traitent les résultats grâce à l’estimation de pro-
babilités a posteriori. Le nombre de classifieurs SVM à entraine peut être
5.1 SVM, probabilités et convergence réduit en utilisant un codage astucieux pour les classes à travers un code
correcteur d’erreur ou un graphe directe acyclique (DAGSVM).
Il est parfois utile d’associer des probabilités aux SVM. Pour ce faire, il
3. L’approche globale consiste à traiter le problème en une seule fois. Cela
est possible de s’appuyer sur le fait que la fonction de discrimination idéale
P(Y =1|x) peut se faire en posant formellement le problème, par exemple si l’on note
log P(Y =−1|x) devrait avoir le même signe que la fonction de discrimination f` (x) − b` la fonction de discrimination associée à la classe ` :
f (x) + b. En posant :  c n c
X CX X
min n 12 kf` k2H + d

b = 1|x)

 ξi`
log
P(Y
= a1 f (x) + a2
 f ∈H,b,ξ∈R d i=1
`=1 `=1,`6=yi

b = −1|x)
P(Y 

 avec yi fyi (xi ) + byi − f` (xi ) − b` ≥ 1 − ξi`
ξi` ≥ 0 pour i = 1, ..., n; ` = 1, ..., c; ` 6= yi

il est possible d’obtenir un estimateur de la probabilité à postériori de la forme :
Le dual de ce problème est un programme quadratique de même nature
1
b = 1|x) = 1 −
P(Y que celui des SVM et de taille n × c. L’estimateur associé est non consis-
1 + expa1 f (x)+a2 tant mais donne de bons résultats en pratique. Il existe là aussi de nom-
où a1 et a2 sont des paramètres estimés par maximum de vraisemblance. breuses autres formulation (dont certaines consistantes).
 13 Machines à vecteurs supports

5.3 Le choix du noyau : SVM à noyaux multiples montrer que cette solution varie linéairement lorsque C varie dans un voisi-
nage de C0 . Afin d’illustrer ce fait et pour simplifier les calculs on considère le
Le choix du noyau et de ses paramètres comme la largueur de bande est sou- problème sans biais en posant λ = 1 . La fonction cout à minimiser s’écrit :
0 C0
vent un problème pratique et critique lors de la mise en œuvre des SVM.
Une manière d’aborder cette question consiste à utiliser des noyaux multiples. n
X
λo
L’idée est d’optimiser le choix du noyau parmi une collection possible. Ainsi, J(f, λ0 ) h yi f (xi ) + kf k2H
si l’on note km , m ∈ [1, M ] une famille de M noyaux positifs, cette optimi- i=1
2
sation s’effectue à travers le réglage de M coefficients de sorte que le noyau
choisiPs’exprime comme une combinaison positive des noyaux du dictionnaire où h(z) = max(1 − z, 0) désigne la fonction charnière représentée figure 4.
k = Pm dm km , 0 ≤ dm , m ∈ [1, M ]. En imposant en plus une contrainte de La solution fo de ce problème est caractérisée par 0 ∈ ∂f J(fo ) où ∂f J(fo )
type m dm = 1 favorisant la parcimonie, la solution optimale va chercher désigne la sous différentielle du cout au point fo . La sous différentielle de J
à sélectionner les noyaux les plus utiles. En notant Hm l’EHNR associé au par rapport à f dépend des trois ensembles d’indices I0 , Iα et I1 et s’écrit :
noyau km et fm ∈ Hm une fonction de cet EHNR, le problème s’écrit : X X
 ∂f J(f, λ0 ) = { αi yi K(xi , •) − yi K(xi , •) + λ0 f (•)}
1 1 2
P P
 min 2 m dm kfm kHm + C i ξi i∈Iα i∈I1
 {fm },b,ξ,d

 P 

(M KL) avec . yi m fm (xi ) + b ≥ 1 − ξi i = 1, n avec αi ∈] − 1, 0[, la sous différentielle de la fonction h(z) au point z = 1.
0 ≤ ξ , i = 1, n

i On considère maintenant λn un élément du voisinage de λ0 pour lequel les


 P
m dm = 1, 0 ≤ dm , m = 1, M

ensembles I , I and I demeurent inchangés à l’optimum. En particulier aux
0 α C
points xj , j ∈ Iα (fo (xj ) = fn (xj ) = yj ) : ∂f J(f )(xj ) = 0. En écrivant ces
Ce problème peut se résoudre itérativement en utilisant une méthode d’op-
équations puis en en faisant la différence on obtient :
timisation alterné. Pour des dm , m = 1, M fixées, les fm , m = 1, M et b
sont la solution d’un problème de SVM L1 dans le cas général. Lorsque les P P
fm , m = 1, M et b sont fixés, les dm peuvent être optimisée via une itération P i∈Iα αio yi K(xi , xj ) = Pi∈I1 yi K(xi , xj ) − λo yj
de gradient réduit. Lorsqu’un dm est suffisamment petit, le noyau associé est i∈Iα αin yi K(xi , xj ) = i∈I1 yi K(xi , xj ) − λn yj
G(αn − αo ) = (λo − λn )y avec Gij = yi K(xi , xj )
éliminé.

5.4 Règlage du C : chemin de régularisation Cette dernière équation nous permet de faire apparaître l’évolution linéaire de
la solution lorsque λ varie puisque :
Outre le choix du noyau, l’autre hyperparamètre à régler dans les SVM est le
terme d’équilibrage C. Une méthode classique mais couteuse consiste à faire αn = αo + (λo − λn )d avec d = G−1 y
de la validation croisée sur une grille prédéfinie de valeurs de C candidates.
Il existe une alternative particulièrement élégante : la technique du chemin de Pour une valeur critique de λ les ensembles I0 , Iα et I1 changent, la matrice
régularisation qui permet de calculer, pour un cout algorithmique analogue à G change aussi ainsi que le vecteur d.
celui du calcul d’une seule solution, un ensemble de solutions possibles pour L’ensemble de toutes les valeurs critiques de λ et les solutions α associées
un ensemble de valeurs de C remarquables. forment un chemin de régularisation que l’on peut initialiser pour des valeurs
En effet, le formulation duale des SVM est un programme quadratique paramé- très grandes de λ avec tous les points lorsque les deux classes sont équilibrées
trique en fonction de C. Connaissant une solution pour un C0 donnée, on peut et qui évolue lorsque λ décroît en éliminant ou échangeant des exemples.
 14 Machines à vecteurs supports

6 D’autres machines à noyau où K est la matrice de gram n × n de terme général Kij = k(xi , xj ). La
figure 7 illustre le fonctionnement de cette méthode.
Les principes des SVM ont été appliqué à de nombreux autres problèmes et
Remarques :
ont permis la création d’autres machines à noyau. Ces principes requiérent :
• la solution de ce problème est liée à la loi parente de l’échantillon puis-
• un problème initialement linéaire,
qu’elle converge dans certains cas vers la frontière de l’ensemble de me-
• l’utilisation de noyaux et la formulation initiale du problème dans un
sure minimal minE vol(E){E ⊂ X | P(E) = ν}.
EHNR comme un problème de minimisation d’une norme,
• une autre manière presque équivalent de poser le problème est le one class
• un théorème de représentation qui permet de représenter la fonction solu-
SVM dans le quel on cherche à maximiser ρ la valeur minimale de f :
tion comme une combinaison linéaire des observations vues à travers le
( 1
Pn
noyau, min 2 kf k2H − ρ + C i=1 ξi
• la résolution du problème dans le dual qui donne un programme quadra- (OCSV M ) f ∈H,b∈R,ξ
avec f (xi ) ≥ ρ − ξi 0 ≤ ξi i = 1, n
tique de taille n (le nombre d’exemples),
• la parcimonie de la solution qui sélectionne les exemples importants. dont le dual est le même que celui des SVDD avec le terme linéaire de la
Nous avons choisi les SVDD pour faire le lien avec la géométrie algorithmique, fonction cout en moins.
la régression pour le lien avec les splines et l’ordonnancement. • comme dans le cas des SVM, le programme quadratique est paramétrique
et il existe une chemin de régularisation linéaire par morceau permettant
6.1 La plus petite boule englobante d’estimer un ensemble de courbes de niveau de la mesure de probabilité
Dans certains cas les étiquettes yi ne sont pas disponibles. Etant donné un à un moindre cout.
ensemble d’observations xi , i ∈ [1, n] i.i.d. selon une loi P. Il est intéressant de
décrire ces données. Le problème de détection de nouveauté consiste à décider
si une nouvelle observation x est proche ou non de cet ensemble. Une manière
d’aborder ce problème consiste à rechercher une frontière de décision sous la
forme de la plus petite boule englobante (minimum enclosing ball) définie par
son centre f et son rayon R. C’est un problème ancien déjà traité dans le plan
par Sylvester en 1857. Dans le cadre des EHNR le problème est aussi connu
sous le nom de suport vector data description (SVDD) :
( Pn
min R2 + C i=1 ξi
(SV DD) f ∈H,b∈R,ξ
1 2 2
avec 2 kk(•, xi ) − f kH ≤ R + ξi 0 ≤ ξi i = 1, n
1
Le paramètre C = νn permet de régler la proportion ν de points que l’on F IGURE 7 – Exemple de SVDD linéaire (à gauche) et pour un noyau gaussien
désire maintenir en dehors de la boule (outliers). Le dual de ce problème est le (à droite). Les points entourés de rouge sont des vecteurs support. Sur la figure
programme quadratique suivant analogue à celui des SVM : de droite, la solution à été calculée pour deux valeurs de C (en rouge pour 10%
d’outliers et en magenta pour la courbe de niveau à ν = 0, 8). On constate que

 minn 21 α> Kα − 12 α> diag(K)
le point en haut à droite est placé en dehors de l’enveloppe calculée.
 α∈R
(SV DD dual) avec e> α = 1

 0 ≤ αi ≤ C i = 1, n
 15 Machines à vecteurs supports

6.2 SVM et regression Dans cette situation, les noyaux k utilisés sont ceux naturellement associés
à la définition de bases de fonctions. Noyaux de splines, noyaux d’ondelettes
Les SVM peuvent également être mis en oeuvre en situation de régression, ou encore noyau de Dirichlet associé à un développement en série de Fourier
c’est-à-dire pour l’approximation de fonctions quand Y est quantitative. Dans sont des grands classiques. Ils expriment les produits scalaires des fonctions
le cas non linéaire, le principe consiste à rechercher une estimation de la fonc- de la base.
tion par sa décomposition sur une base fonctionnelle. Si l’on se considère un
terme d’attache aux données de type « moindres carrés » pénalisés, la formu- 6.3 SVM et ordonnancement
lation avec contraintes dans l’EHNR H s’écrit :
Il arrive que les étiquettes disponibles yij expriment une préférence de l’ob-
n

 min 1 kf k2 + 1 X ξ 2
 servation xi sur l’observation xj . On définit alors un ensemble P de couples
2 H 2λ i
f ∈H d’indices i, j pour tous les xi préférables à xj . La tâche associée consiste à
i=1
construire une fonction score (de préférence) f permettant d’ordonner des ob-

avec f (xi ) = yi + ξi , i = 1, n

servations candidates. Ce problème est important dans le cadre de la recherche
La solution prend la forme d’une fonction spline. C’est une combinaison li- d’information et de la recommandation. Dans le cadre des machines à noyaux,
néaires des noyaux (comme dans le cas des SVM équation 1). Les coefficients l’apprentissage de cette fonction f peut se formuler de la manière suivante :
α sont les variables du problème dual données par la résolution du système (
min 12 kf k2H + Cd i,j∈P ξij d
P
linéaire suivant : (rankSV M ) f ∈H
(K + λI)α = y avec f (xi ) − f (xj ) ≥ 1 − ξij , 0 ≤ ξij , i, j ∈ P
Dans cette formulation (qui peut être reprise pour la classification et l’estima- Pour le dual de ce problème non linéaire, les card(P) ≤ n2 contraintes vont
tion de densité) toutes les observations sont vecteur support (A = {1, . . . , n}). correspondre à autant de variables ce qui peut s’avérer trop. Il est cependant
Afin d’obtenir de la parcimonie (et espérer un petit nombre de vecteurs sup- toujours possible de résoudre le problème linéaire dans le primal, c’est-à-dire
port), il faut modifier le terme d’attache aux données. Parmi toutes les solutions rechercher le vecteur w tel que f (xi ) − f (xj ) = w> (xi − xj ). Dans ce cas,
envisageables, celle retenue dans le cadre de la support vector regression, est les contraintes s’écrivent matriciellement w> ∆f ≥ e − ξ où ∆f , la matrice
une fonction de déviation en valeur absolue tronquée (appelé aussi le cout t- des différences est de taille n2 × p se décompose ∆f = AX avec X la matrice
insensible). Le problème avec contraintes s’écrit : des observations n × p et A une matrice creuse avec au plus un couple de
( 1
valeurs (1,-1) par ligne. Ce problème peut être lors résolu pour d = 2 par un
kf k2H + C ξi
P
min 2 algorithme de Newton à partir du calcul du gradient g et de la matrice hessiène
(SV R) f ∈H,b∈R
avec |f (xi ) + b − yi | ≤ t + ξi , 0 ≤ ξi , i = 1, n H du problème :

et la formulation équivalente en terme de cout pénalisé est : g = w + C X > A> A AA Xw

H = I + CX > A>
A AA X
n
1 X
kf k2H + C où A désigne l’ensemble des paires qui violent les contraintes. Ainsi le calcul


min max 0, |f (xi ) + b − yi | − t
f ∈H,b∈R 2 i=1 d’une direction de descente d = H −1 g peut être approchée par la méthode
de gradient conjugué qui requière le calcul du produit de la hessiène par un
Le dual est un programme quadratique bi-paramétrique et il existe deux che- vecteur v qui ne nécessite pas la construction explicite de H puisque :
mins de régularisation linéaires, en fonction des paramètres C et t la largeur
de la zone insensible considérée. Hv = v + CX > A> A AA Xv
 16 Machines à vecteurs supports

Il existe de nombreuse extensions et adaptations. Citons l’utilisation de fonc-

tion cout mieux adaptés comme le gain cumulé normalisé (normalized dis-

300

100
counted cumulative gain NDCG@k) pour s = Xw ordonnés et π une permu-

250
tation de ces scores tronquées à k éléments :

50
200
Valeurs observees
k
2sπi − 1

Résidus
DCG@k(s, π)

150
X

0
DCG@k(s, π) = et N DCG@k(s, π) =
log(i + 2) DCG@k(s, πs )

100
i=1

−50
50
où πs désigne la permutation maximisant DCG@k(s, π).

−100
0
Pour plus de détails, le lecteur intéressé par se type de problème pourra consul-
0 50 100 150 200 250 300 0 50 100 150 200 250 300
ter les résultats de la compétition Yahoo Learning to Rank Challenge 1 . Valeurs predites Valeurs predites

7 Exemples de mise en œuvre

F IGURE 8 – Ozone : Valeurs observées et résidus en fonction des valeurs pré-
Même si les SVM s’appliquent à un problème de régression, nous n’illus- dites pour l’échantillon test.
trons que le cas plus classique de la discrimination.

7.1 Cancer du sein FALSE 161 13

La prévision de l’échantillon test par un Séparateur à Vaste marge conduit à TRUE 7 27
la matrice de confusion :
Ce résultat serait à confirmer avec des estimations sytématiques de l’erreur.
ign malignant Les graphiques de la figure 8 montre le bon comportement de ce prédicteur.
benign 83 1 Il souligne notamment l’effet "tunnel" de l’estimation qui accepte des erreurs
malignant 3 50 autour de la diagonale pour se concentrer sur les observations plus éloignées
donc plus difficiles à ajuster.
et donc une erreur estimée de 3%.
7.3 Carte Visa
7.2 Concentration d’ozone
Les données bancaires posent un problème car elles mixent variables quan-
Un modèle élémentaire avec noyau par défaut (gaussien) et une pénalisation titatives et qualitatives. Celles-ci nécessiteraient la construction de noyaux très
de 2 conduit à une erreur de prévision estimée à 12,0% sur l’échantillon test. spécifiques. Leur traitement par SVM n’est pas détaillé ici.
La meilleure prévision de dépassement de seuil sur l’échantillon test initial
est fournie par des SVM d’ε-régression. Le taux d’erreur est de 9,6% avec la
matrice de confusion suivante :

0 1
1. learningtorankchallenge.yahoo.com