2

But de l’exposé

• Présenter les SVM

• Encourager leur utilisation

• Encourager leur étude

O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001

 3
Plan

→ Quel est le contexte ?

• Qu’est-ce que c’est ?

• Comment cela marche-t-il ?

• Pourquoi est-ce utile ?

• Pourquoi est-ce que cela marche ?

O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001

 4
Contexte

Problème d’apprentissage

On s’intéresse à un phénomène f (éventuellement non-déterministe) qui,

• à partir d’un certain jeu d’entrées x,
• produit une sortie y = f (x).

→ Le but est de retrouver f à partir de la seule observation d’un certain nombre

de couples entrée-sortie {(xi, yi) : i = 1, . . . , n}

O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001

 5
Contexte

Formalisation

On considère un couple (X, Y ) de variables aléatoires à valeurs dans X × Y.

Seul le cas Y = {−1, 1} (classification) nous intéresse ici (on peut facilement
étendre au cas |Y| = m > 2 et au cas Y = R).
La distribution jointe de (X, Y ) est inconnue.
• Données: on observe un échantillon S = {(X1, Y1), . . . , (Xn, Yn)} de n
copies indépendantes de (X, Y ).
• But: construire une fonction h : X → Y telle que P (h(X) �= Y ) soit
minimale.

O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001

 6
Exemples de problèmes d’apprentissage

Reconnaissance de formes

• Reconnaissance de chiffres manuscrits (après segmentation: codes postaux)

• Reconnaissance de visages

Entrées: image bidimensionnelle en couleur ou en niveaux de gris

Sortie: classe (chiffre, personne)

O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001

 7
Exemples de problèmes d’apprentissage

Catégorisation de textes

• Classification d’e-mails
• Classification de pages web

Entrées: document (texte ou html)

Sortie: catégorie (thème, spam/non-spam)

O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001

 8
Exemples de problèmes d’apprentissage

Diagnostic médical

• Evaluation des risques de cancer

• Detection d’arythmie cardiaque

Entrées: etat du patient (sexe, age, bilan sanguin, génome...)

Sortie: classe (à risque ou non)

O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001

 9
Illustration

Trouver une frontière de décision qui sépare l’espace en deux régions (pas
forcément connexes).

→ Problème d’optimisation
Critère: erreur constatée sur les données (Erreur empirique)
Espace de recherche: ensemble paramétré de fonctions par exemple
→ Problème mal posé (solution non unique)
→ Garanties ?
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
 10
Illustration

Sur et sous-apprentissage

• Si les données sont générées par un modèle quadratique

• Le modèle linéaire est en situation de sous-apprentissage
• Le modèle de haut degré est en situation de sur-apprentissage (apprentissage
par coeur)
→ Un compromis est à trouver entre adéquation aux données et complexité
pour pouvoir généraliser.
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
 11
Plan

• Quel est le contexte ?

→ Qu’est-ce que c’est ?

• Comment cela marche-t-il ?

• Pourquoi est-ce utile ?

• Pourquoi est-ce que cela marche ?

O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001

 12
Qu’est-ce que c’est ?

Les Support Vector Machines sont une classe d’algorithmes d’apprentissage.

Principe général
• Construction d’un classifieur à valeurs réelles
• Découpage du problème en deux sous-problèmes
1. Transformation non-linéaire des entrées
2. Choix d’une séparation linéaire ’optimale’

O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001

 13
Classification à valeurs rélles

• Plutôt que de construire directement h : X → {−1, 1}, on construit

f : X → R.
• La classe est donnée par le signe de f
h = sgn(f ) .
• L’erreur se calcule avec
P (h(X) �= Y ) = P (Y f (X) ≤ 0) .

→ Donne une certaine idée de la confiance dans la classification. Idéalement,

|Y f (X)| est ’proportionnel’ à P (Y |X).
→ Y f (X) est la marge de f en (X, Y ).

O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001

 14
Transformation des entrées

• X est un espace quelconque d’objets.

• On transforme les entrées en vecteurs dans un espace F (feature space).

Φ:X →F.

• F n’est pas nécessairement de dimension finie mais dispose d’un produit

scalaire (espace de Hilbert)

• La non-linéarité est traitée dans cette transformation, on peut donc choisir

une séparation linéaire.

O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001

 15
Choix d’une séparation

Hyperplan optimal

Choix de la séparation: hyperplan qui classifie correctement les données (lorsque

c’est possible) et qui se trouve “le plus loin possible de tous les exemples”.

Optimal

Valide

O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001

 16
Maximisation de la marge

Définition géométrique

Marge = distance du point le plus proche à l’hyperplan

O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001

 17
Plan

• Quel est le contexte ?

• Qu’est-ce que c’est ?

→ Comment cela marche-t-il ?

• Pourquoi est-ce utile ?

• Pourquoi est-ce que cela marche ?

O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001

 18
Maximisation de la marge

Propriétés

Modèle linéaire
f (x) = w · x + b
Définition de l’hyperplan (frontière de décision)
w·x+b=0
La distance d’un point au plan est donnée par
|w · x + b|
d(x) =
�w�
→ Maximiser la marge revient à minimiser �w� sous contraintes

O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001

 19
Implémentation

Problème primal

Un point (xi, y) est bien classé si et seulement si

yf (x) > 0
Comme le couple (w, b) est défini à un coefficient multiplicatif près, on s’impose
yf (x) ≥ 1
Rappelons que
|f (x)|
d(x) =
�w�
On obtient le problème de minimisation sous contraintes
�
min 12 �w�2
∀i, yi(w.xi + b) ≥ 1

O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001

 20
Implémentation

Problème dual

On passe au problème dual en introduisant des multiplicateurs de Lagrange

pour chaque contrainte.
Ici on a une contrainte par exemple d’apprentissage
 �n 1
�
 max i=1 αi − 2 i,j αiαj yiyj xi · xj
∀i, α ≥ 0
 �n i
i=1 αi yi = 0
Problème de programmation quadratique de dimension n (nombre d’exemples).

Matrice hessienne: (xi · xj )i,j .

O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001

 21
Implémentation

Propriétés

n
�
w∗ = αi∗yixi
i=1
Seuls les αi correspondant aux points les plus proches sont non-nuls. On parle
de vecteurs de support.
Fonction de décision
�n
f (x) = αi∗yixi · x + b
i=1

O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001

 22
Cas non-séparable

Traitement des erreurs

On introduit des variables ’ressort’ pour assouplir les contraintes.

� 1 2
�n
min 2 �w� + C i=1 ξi
∀i, yi(w.xi + b) ≥ 1 − ξi
On pénalise par le dépassement de la contrainte.

O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001

 23
Cas non-séparable

Problème dual

Le problème dual a la même forme que dans le cas séparable:

 �n 1
�
 max i=1 iα − 2 i,j αi αj yi yj xi · xj
∀i, 0 ≤ αi ≤ C
 �n
i=1 αi yi = 0
La seule différence est la borne supérieure sur les α.

O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001

 24
Fonction noyau

Espace intermédiaire

Au lieu de chercher un hyperplan dan l’espace des entrées, on passe d’abord dans
un espace de représentation intermédiaire (feature space) de grande dimension.
Φ : Rd → F
x �→ Φ(x)
On doit donc résoudre
 �n 1
�
 max i=1 αi − 2 i,j αiαj yiyj Φ(xi) · Φ(xj )
∀i, 0 ≤ αi ≤ C
 �n
i=1 αi yi = 0
et la solution a la forme
n
�
f (x) = αi∗yiΦ(xi) · Φ(x) + b
i=1

O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001

 25
Fonction noyau

Propriétés

Le problème et sa solution ne dépendent que des produits scalaires Φ(x)·Φ(x�).

→ Plutôt que de choisir la transformation non-linéaire Φ : X → F, on choisit
une fonction k : X × X → R appelée fonction noyau.
• Elle représente un produit scalaire dans l’espace de représentation intermédiaire.
Elle traduit donc la répartition des exemples dans cet espace.
k(x, x�) = Φ(x) · Φ(x�)
• Lorsque k est bien choisie, on n’a pas besoin de calculer la représentation
des exemples dans cet espace pour calculer cette fonction.
• Permet d’utiliser des représentations non-vectorielles
→ Le noyau matérialise une notion de proximité adaptée au problème.

O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001

 26
Fonction noyau

Exemple

√
Soit x = (x1, x2) et Φ(x) = (x21, 2x1x2, x22). Dans l’espace intermédiaire, le
produit scalaire donne
2 2
Φ(x) · Φ(x�) = x21x�1 + 2x1x2x�1x�2 + x22x�2
= (x1x�1 + x2x�2)2
= (x · x�)2
On peut donc calculer Φ(x) · Φ(x�) sans calculer Φ.

O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001

 27
Fonction noyau

Exemple

→ Le passage dans F = R3 rend possible la séparation linéaire des données.

O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001

 28
Fonction noyau

Conditions de Mercer

Une fonction k(., .) symétrique est un noyau si pour tous les xi possibles,
(k(xi, xj ))i,j est une matrice définie positive.
Dans ce cas, il existe un espace F et une fonction Φ tels que
k(x, x�) = Φ(x) · Φ(x�)
• Difficile à vérifier
• Ne donne pas d’indication pour la construction de noyaux
• Ne permet pas de savoir comment est Φ
→ En pratique, on combine des noyaux simples pour en obtenir de plus com-
plexes.

O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001

 29
Fonction noyau

Exemples de noyaux

• Linéaire
k(x, x�) = x · x�
• Polynomial
k(x, x�) = (x · x�)d ou (c + x · x�)d
• Gaussien
� 2 /σ
k(x, x�) = e−�x−x �
• Laplacien
�
k(x, x�) = e−�x−x �1/σ

O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001

 30
Plan

• Quel est le contexte ?

• Qu’est-ce que c’est ?

• Comment cela marche-t-il ?

→ Pourquoi est-ce utile ?

• Pourquoi est-ce que cela marche ?

O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001

 31
Pourquoi est-ce utile ?

• Flexibilité des noyaux

Noyau ≡ mesure de similitude

• Temps de calcul raisonnable

Trouver un hyperplan qui minimise l’erreur est NP-complet.

• Vecteurs de support

Représentation parcimonieuse et éventuellement interprétable.

O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001

 32
Noyaux

Exemples

Si les données sont sous forme vectorielle, on peut utiliser un noyau classique.
On peut aussi contruire un noyau spécifique qui travaille plus directement sur
la représentation initiale (structure).
• Images 2D: choix d’une résolution et d’une discrétisation des couleurs
→ vecteur des valeurs des pixels
→ coefficients d’une transformée en ondelettes
→ histogramme des couleurs
• Textes: choix d’un dictionnaire (suppression des mots simples)
→ Sac de mots: vecteur des occurences
→ Autres attributs (liens, position des mots...)

O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001

 33
Noyaux

Exemples

• Séquences d’ADN
– Fenêtres de taille fixe (sous-séquence) et représentation binaire (un bit par
valeur possible)
... A T A G C A ...
1 0 1 0 0 1
0 1 0 0 0 0 → (1,0,0,0,0,1,0,0,1,0,0,0,0,0,1,0,0,0,0,1,1,0,0,0)
0 0 0 1 0 0
0 0 0 0 1 0
– Coefficients d’un modèle probabiliste générateur

O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001

 34
Temps de calcul

Complexité

d = dimension des entrées

n = nombre d’exemples d’apprentissage

dn2 ≤ Complexite ≤ dn3

Taille de la matrice hessienne: n2

→ Méthodes de décomposition

O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001

 35
Plan

• Quel est le contexte ?

• Qu’est-ce que c’est ?

• Comment cela marche-t-il ?

• Pourquoi est-ce utile ?

→ Pourquoi est-ce que cela marche ?

O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001

 36
Pourquoi cela marche-t-il ?

Eléments de réponse

Plusieurs réponses possibles

• Maximisation de la marge
L’ensemble des hyperplans de marge donnée M a une VC dimension bornée
par
R2
,
M2
si les X sont dans une boule de rayon R.
• Parcimonie de la représentation
L’erreur leave-one-out est bornée en moyenne par le nombre de vecteurs
support.
En pratique cela donne des bornes relativement prédictives mais très pes-
simistes.
O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001
 37
Questions Ouvertes

Régularisation

On peut voir l’algorithme SVM comme la minimisation d’une fonctionnelle

régularisée:
n
�
min c(f, Xi, Yi) + λ�f �2H .
f
i=1
1. Choix du paramètre de régularisation
2. Pénalisation linéaire vs quadratique
3. Lien entre parcimonie et choix de la pénalisation

O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001

 38
Questions Ouvertes

Noyaux

1. Choix automatique des paramètres

2. Construction de noyaux exotiques (sur des objets structurés)
3. Approche non-paramétrique pour la construction de noyau
4. Classes étendues de noyaux (conditionnellement positifs)

O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001

 39
Questions Ouvertes

Généralisation

1. Notion de complexité (covering numbers, fat-shattering dimension)

2. Structure du feature space
3. Structure de l’espace des fonctions possibles (qui dépend des données)
4. Propriétés de la matrice de Gram

O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001

 40
Questions Ouvertes

Marge - Parcimonie

1. Bornes de type perceptron (Novikoff)

2. Lien avec la fat-shattering dimension
3. Rôle de la classification a valeurs réelles
4. Lien avec la marge du boosting

O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001

 41
Conclusion

1. La technique SVM est d’une grande flexibilité grâce aux noyaux

2. La maximisation de la marge semble être une bonne heurisitque
3. De nombreuses questions restent ouvertes
• Applications: construction de noyaux, adaptation des paramètres, implé-
mentation efficace, incorporation d’invariances...
• Théorie: comprendre la généralisation, la complexité, la marge, la parci-
monie...

Essayez les SVM !

Etudiez les SVM !
Venez au séminaire/groupe de travail !

O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001

 42
Pour en savoir plus

Page du séminaire/GT:
http://www.math.u-psud.fr/~blanchard/gtsvm/index.html
→ Références bibliographiques

Un lien utile:
http://www.kernel-machines.org
→ Programmes, articles en ligne, tutoriels...

O. Bousquet: Introduction aux SVM Orsay, 15 Novembre 2001