Cours SVM
SVMs SVMs (Séparateurs à Vastes Marges)(Séparateurs à Vastes Marges) etet
Méthodes à noyauxMéthodes à noyaux
Laurent Orseau
AgroParisTech
à partir des transparents d'Antoine Cornuéjols
Cours SVM (L. Orseau) 2/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
PlaPlann
1- Induction
2- Les SVMs
3- Les méthodes à noyau
4- Mise en œuvre
5- Applications
6- Bilan
Cours SVM (L. Orseau) 3/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Apprentissage inductif Apprentissage inductif supervisésupervisé
À partir de l’échantillon d’apprentissage S = {(xi, ui)}1,m
on cherche à identifier une loi de dépendance sous-jacente
Par exemple une fonction h aussi proche possible de f
(fonction cible) tq : ui = f(xi)
Ou bien de la distribution de probabilités P(xi, ui)
afin de prédire l’avenir
Cours SVM (L. Orseau) 4/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Apprentissage inductif Apprentissage inductif supervisésupervisé
Échantillon d’apprentissage
Identification : h « proche de » f
Prédiction : h « bonne règle de décision »
Cours SVM (L. Orseau) 5/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Hyperplans séparateursHyperplans séparateurs
Tâche de classification Cas de la séparation linéaire
- On cherche h sous forme d’une fonction linéaire : h(x) = w.x + b
- La surface de séparation est donc l’hyperplan :
- Elle est valide si
- L’hyperplan est dit sous forme canonique lorsque
ou encore
w. x b 0
i ui h(xi ) 0
mini
w.x b 1
i ui (w.xi b) 1
Cours SVM (L. Orseau) 6/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Discrimination linéaire : Discrimination linéaire : le Perceptronle Perceptron
Cours SVM (L. Orseau) 7/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Hyperplan de plus vaste margeHyperplan de plus vaste marge
Margemaximale
Hyperplan
optimal
Hyperplanvalide
Cours SVM (L. Orseau) 8/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Optimisation de la margeOptimisation de la marge
Margemaximale
Hyperplan
optimal
Hyperplanvalide
D(x) = 0
D(x) = +1
D(x) = -1
Vecteursde support
D(x) > 1
D(x) < -1
w
1
w
Cours SVM (L. Orseau) 9/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Optimisation de la Optimisation de la marge marge
La distance d’un point à l’hyperplan est :
L’hyperplan optimal est celui pour lequel la distance aux points les plus
proches (marge) est maximale. Cette distance vaut
Maximiser la marge revient donc à minimiser ||w|| sous contraintes:
2
w
d (x ) w. x w0
w
min1
2w
2
i ui (w. xi w0 ) 1
Cours SVM (L. Orseau) 10/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
SVMs : SVMs : un problème d’optimisation quadratiqueun problème d’optimisation quadratique
Il faut donc déterminer w et w0 minimisant :
(afin de maximiser le pouvoir de généralisation)
sous les contraintes (hyperplan séparateur) :
(w ) 1
2w 2
ui (w . xi ) w0 1 , i 1,..., n
EXPRESSIONPRIMAIRE
Cours SVM (L. Orseau) 11/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Résolution de la forme primaire du problèmeRésolution de la forme primaire du problème
Il faut régler d + 1 paramètres
Possible quand d est assez petit
avec des méthodes d'optimisation quadratique
Impossible quand d est grand (> qqs 103)
d : dimension de l’espace d’entrée
Cours SVM (L. Orseau) 12/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Transformation du problème d’optimisationTransformation du problème d’optimisation
Méthode des multiplicateurs de Lagrange
Problème dual
L(w, w0 , ) 1
2w 2 i {(xi .w w0 )ui 1}
i1
l
i i 0
max
i 1
2 i j ui u j (xi . x j )
j1
l
i1
l
i1
l
i i 0
i ui 0i1
l
EXPRESSIONDUALE
Cours SVM (L. Orseau) 13/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Propriétés de la forme dualePropriétés de la forme duale
La conversion est possible car les fonctions de coût et les contraintes sont
strictement convexes (Th. de Kuhn-Tucker)
La complexité du problème d'optimisation est
m (taille de l'échantillon d'apprentissage) et non d ( taille de l'espace d'entrée X )
Possible d'obtenir des solutions pour des problèmes
impliquant ≈ 105 exemples
Cours SVM (L. Orseau) 14/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Solution du problème d’optimisationSolution du problème d’optimisation
Propriété1 : seuls les i correspondant aux points les plus proches sont non-nuls.
On parle de points de supportpoints de support (exemples critiques).
Propriété 2 : seuls interviennent les produits scalaires produits scalaires entre les observations entre les observations xx
dans le problème d’optimisation.
* : estimé
(xS,uS) étant n'importe quel
point de support
D(x) (w* .x w0* )
w* i* ui xi
i1
m
w0* us i
* ui (xi .xs )i1
m
Cours SVM (L. Orseau) 15/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Pourquoi ça marche ?Pourquoi ça marche ?
La marge est liée à la capacité en généralisation
Normalement, la classe des hyperplans de Rd est de dH = d + 1
Mais la classe des hyperplans de marge
est bornée par : dH ≤ Min (R2 c, d) + 1
où R est le rayon de la plus petite sphère englobant l'échantillon
d'apprentissage S
Peut être beaucoup plus petit que la dimension d de l'espace d'entrée X
1
w tq. w
2 c
Cours SVM (L. Orseau) 16/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Les fonctions noyau Les fonctions noyau (kernel functions)(kernel functions)
Fonction k telle que :
où : Espace de redescriptionmuni d’un produit interne
Cours SVM (L. Orseau) 17/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Les fonctions noyau : exempleLes fonctions noyau : exemple
Rq (non unicité de l’espace F défini par ) :
est une fonction noyau
(le même noyau calcule le produit interne dans cet espace aussi)
Cours SVM (L. Orseau) 18/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Les méthodes à noyauLes méthodes à noyau
Modularité
Découplage entre Les algorithmes (linéaires) La description des données
Cours SVM (L. Orseau) 19/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Petite digression …Petite digression …
… La reconnaissance de chiffres manuscrits par réseaux de neurones (ATT Bell labs, 1993)
1
2
3
4
5
6
7
8
9
0
Matrice 16 x 16 12 détecteursde traits (8 x 8)
12 détecteursde traits (4 x 4)
30 cellules
10 cellulesde sortie
Cours SVM (L. Orseau) 20/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Leçons Leçons (provisoires)(provisoires)
L’emploi de fonctions noyau permet :
D’utiliser les algorithmes de recherche de régularités linéaires
pour la recherche de régularités non linéairesrecherche de régularités non linéaires
D’employer ces algorithmes même sur des données non données non
vectoriellesvectorielles (du moment que l’on sait trouver une fonction
noyau adéquate)
De redécrire implicitement les données dans des espaces de espaces de
grande dimensiongrande dimension sans en avoir le coût computationnel
Cours SVM (L. Orseau) 21/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Les méthodes à noyauxLes méthodes à noyaux
Tout passe par les produits internes dans F !!!Tout passe par les produits internes dans F !!!
Philosophie de représentation des donnéesradicalement différente
Cours SVM (L. Orseau) 22/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Conséquences d’une représentation par noyauConséquences d’une représentation par noyau
Des informations sont perdues
Orientation (invariance de la matrice K par rotation)
Alignement des données avec les axes (idem)
Cours SVM (L. Orseau) 23/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Les fonctions noyau : définitionLes fonctions noyau : définition
Fonction noyau positive définie
Symétrique :
Positive définie :
Théorème de Mercer
Toute fonction positive définie peut être exprimée comme Toute fonction positive définie peut être exprimée comme
un produit interne dans un espace de descriptionun produit interne dans un espace de description
Cours SVM (L. Orseau) 24/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Fonctions noyau pour des vecteursFonctions noyau pour des vecteurs
Noyaux polynomiaux
Tous les produits d’exactementd variables
Tous les produits d’au plusd variables
Noyaux gaussiens
Sorte de décompositionen série de Fourrier
Noyaux sigmoïdes
Pas définie positive.Mais fonction de décision
proche des réseaux connexionnistes
Cours SVM (L. Orseau) 25/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Morale Morale
Les données s’expriment à travers la matrice noyau
La matrice noyau contrôle la régularisation du
risque
Cours SVM (L. Orseau) 26/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Solution du problème d’optimisation dualSolution du problème d’optimisation dual
Dans la forme duale :
mS : nb de points de support
Cours SVM (L. Orseau) 27/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Schéma de fonctionnement des SVMsSchéma de fonctionnement des SVMs
K K K K
1 2 3
4
Sortie :
Comparaison : K(xi, x)
Échantillon x1, x2, x3, ...
Vecteur d'entrée x
sign(i ui K(xi,x) + w0)
sign(i ui K(xi,x) + w0)
Cours SVM (L. Orseau) 28/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
IllustrationIllustration
Soient 5 points sur la droite : {(x1=1, u1 =1), (x2=2, u2= 1), (x3= 4, u3= -1), (x4= 5, u4 = -1),
(x5= 6, u5= 1)}
Utilisation d’un noyau polynomial de degré 2
k(xi, xj) = (xi xj + 1)2
C = 100
Recherche de i par :
1 2 4 5 6
Cours SVM (L. Orseau) 29/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
IllustrationIllustration
Utilisation d’un programme de résolution de problème quadratique
1=0, 2=2.5, 3=0, 4=7.333, 5=4.833
Les points de supports sont : { x2=2, x4= 5, x5= 6}
La fonction de décision est :
h(x) = (2.5)(1)(2x+1)2 + 7.333(1)(5x+1)2 + 4.833(1)(6x+1)2+b
= 0.6667 x2 - 5.333 x + b
Avec b obtenue par h(2)=1 ou par h(5)=-1 ou par h(6)=1, puisque x2,
x4 et x5 sont sur la droite ui(wT(x)+b)=1
ce qui donne b=9
D’où :h(x) = 0.6667 x2 - 5.333 x + 9
Cours SVM (L. Orseau) 30/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
IllustrationIllustration
Valeur de la fonction discriminante
1 2 4 5 6
classe 2 classe 1classe 1
{x=2, x=5, x=6} sont points supports
Cours SVM (L. Orseau) 31/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Séparation linéaire dans l'espace des featuresSéparation linéaire dans l'espace des features
Cours SVM (L. Orseau) 32/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Illustration : lIllustration : le cas du e cas du XORXOR
1
1-1
-1
x1
x2
Index i x u
1 (1,1) 1
2 (1,-1) -1
3 (-1,-1) 1
4 (-1,1) -1
Cours SVM (L. Orseau) 33/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Illustration : lIllustration : le cas du XORe cas du XOR
Fonction noyau polynomiale de d° 2 :
K(x,x') = [1 + (xT . x')]2
soit : K(x,xi ) = 1 + x12xi1
2 + 2 x1x2xi1xi2 + x22xi2
2 + 2x1xi1 + 2x2xi2
correspondant à la projection :
[1, x12, √2 x1x2, x2
2, √2 x1, √2 x2 ] T
Cours SVM (L. Orseau) 34/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Illustration : lIllustration : le cas du XORe cas du XOR
Ici :
max
i 1
2 i j ui u j K (xi , x j )
j1
l
i1
l
i1
l
i 0 i C
i ui 0i1
l
Q 1 2 3 4
1
2 (91
2 21 2 213 21 4
922 223 224 93
2 23 4 9 4
2 )
Cours SVM (L. Orseau) 35/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Illustration : lIllustration : le cas du XORe cas du XOR
L'optimisation de Q() en fonction des multiplicateurs de Lagrange
conduit au système d'équations :
91 2 3 4 1
1 92 3 4 1
1 2 93 4 1
1 2 3 9 4 1
La valeur optimale des multiplicateurs de Lagrange est :
1* 2
* 3* 4
* 1
8
Cours SVM (L. Orseau) 36/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Illustration : lIllustration : le cas du XORe cas du XOR
Les 4 exemples sont donc des exemples critiques ("support vectors")
La valeur optimale de Q() est :
Et : soit :
Q*( ) 14
1
2 w*
1
4w*
1
2
Cours SVM (L. Orseau) 37/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Les 4 exemples sont donc des exemples critiques ("support vectors") ( i , i ≠ 0)
La fonction de décision s’écrit :
Illustration : lIllustration : le cas du XORe cas du XOR
Cours SVM (L. Orseau) 38/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Illustration : lIllustration : le cas du XORe cas du XOR
En revenant dans l’espace d’origine :
Le vecteur poids optimal est :
w* 1
8
1
1
2
1
2
2
1
1
2
1
2
2
1
1
2
1
2
2
1
1
2
1
2
2
0
0
1 2
0
0
0
w* 1
8 (x1 ) (x2 ) (x3 ) (x4 )
soit :
Cours SVM (L. Orseau) 39/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Illustration : lIllustration : le cas du XORe cas du XOR
L'hyperplan optimal correspond à :
w*T.(x) 0, 0, 1
2, 0, 0, 0
1
x12
2x1x2
x22
2x1
2x2
x1 x2 0
Cours SVM (L. Orseau) 40/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Illustration : lIllustration : le cas du XORe cas du XOR
Séparatrice dans l'espace d'entrée
D(x) = -x1x2
Séparatrice dans l'espace (X)(espace à 6 dimensions)
2 x1x2 0
Cours SVM (L. Orseau) 41/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Cas du problème non séparable : Cas du problème non séparable : marges doucesmarges douces
On introduit des variables “ressort” qui pénalisent l’erreur commise :
Le problème dual a la même forme à l’exception d’une constante C
min1
2w 2 C i
i1
l
i ui (w. xi w0 ) 1 i
Cours SVM (L. Orseau) 42/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
La mise en La mise en pratiquepratique
Il faut choisir :
Le type de fonction noyau k
Sa forme
Ses paramètres
La valeur de la constante C
La sélection de ces paramètres requiert l’utilisation de méthodes
empiriques pour faire le meilleur choix (validation croisée)
Cours SVM (L. Orseau) 43/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
QuickTime™ and aGIF decompressor
are needed to see this picture.
ExempleExemple
: exemple +
• : exemple -
Dans cercle : points de support
Fct noyau polynomiale de degré 3
Démo :
http://svm.research.bell-labs.com/
http://svm.dcs.rhbnc.ac.uk/pagesnew/GPat.shtml
Cours SVM (L. Orseau) 44/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Les données d'apprentissageLes données d'apprentissage
Cours SVM (L. Orseau) 45/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Effet des paramètres de contrôleEffet des paramètres de contrôle
Apprentissage de deux classes
exemples tirés uniformément sur l'échiquier
SVM à fonctions noyau gaussienne
Ici deux valeurs de En haut : petite valeur
En bas : grande valeur
Les gros points sont des exemples critiques
Plus en haut qu'en bas
Dans les deux cas : Remp = 0
K(x, x' ) e
x x' 2
2 2
Cours SVM (L. Orseau) 46/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Paramètres de contrôle : Paramètres de contrôle : les fonctions noyaules fonctions noyau
http://svm.dcs.rhbnc.ac.uk/pagesnew/GPat.shtml
47 exemples (22 +, 25 -)
Exemples critiques : 4 + et 3 -
Ici fonction polynomiale de degré 5 et C = 10000
Cours SVM (L. Orseau) 47/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Paramètres de contrôle : Paramètres de contrôle : les fonctions noyaules fonctions noyau
47 exemples (22 +, 25 -)
Exemples critiques : 4 + et 3 -Ici fonction polynomiale de degré 2, 5, 8 et C = 10000
Ici fonction Gaussienne de = 2, 5, 10 et C = 10000
(4-, 5+)(8-, 6+)(10-, 11+)
(5-, 4+) (3-, 4+) (5-, 4+)
Cours SVM (L. Orseau) 48/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Ajout de quelques points ...Ajout de quelques points ...
http://svm.dcs.rhbnc.ac.uk/pagesnew/GPat.shtml
47 + 8 exemples (30 +, 25 -)
Exemples critiques : 5 + et 8 -
Ici fonction polynomiale de degré 5 et C = 10000
Cours SVM (L. Orseau) 49/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Estimation de la performance Estimation de la performance
Empiriquement : par validation croisée
Heuristiquement (mais théoriquement fondé)
Nombre de points de supports
Moins il y en a, mieux c’est
Caractéristiques de la matrice noyau
Si pas de structure dans K, aucune régularité ne peut-être trouvée
E.g.
Si les termes hors diagonale sont très petits : sur-adaptation
Si matrice uniforme : sous-apprentissage : tous les points sont
attribués à la même classe
Cours SVM (L. Orseau) 50/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Construction de fonctions noyauConstruction de fonctions noyau
Construction à partir de fonctions noyau de base(Propriétés de clôture)
K(x,z) = K1(x,z) + K2(x,z)
K(x,z) = a K1(x,z)
K(x,z) = K1(x,z) . K2(x,z) …
Construction de fonctions noyau dédiées
Splines Bm
Expansion de Fourrier Ondelettes ...
Cours SVM (L. Orseau) 51/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Construction de noyauxConstruction de noyaux
Noyau invariant par translation
Noyau défini sur des ensembles
Cours SVM (L. Orseau) 52/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Stratégies de constructionStratégies de construction
Noyau vu comme un moyen de coder de l’information a priori
Invariance: synonymie, longueur de document, …
Traitements linguistiques: normalisation des mots, semantique,
stopwords, weighting scheme, …
Noyaux de convolution :
le texte est une structure de données récursivement définie.
Pb : construire un noyau global à partir de noyaux locaux ?
Noyaux à partir de modèles génératifs :
la “topologie” du problème est traduite en une fonction noyau
Cours SVM (L. Orseau) 53/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
ApplicationsApplications
Catégorisation de textes
Reconnaissance de caractères manuscrits
Détection de visages
Diagnostic de cancer du sein
Classification de protéines
Prévision de consommation électrique
Recherche de vidéos par du texte
Trained SVM classifiers for pedestrian and face object detection (Papageorgiou, Oren, Osuna and Poggio, 1998)
Cours SVM (L. Orseau) 54/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Implémentation des SVMsImplémentation des SVMs
Minimisation de fonctions différentiables convexes à plusieurs variables Pas d’optima locaux Mais :
Problèmes de stockage de la matrice noyau (si milliers d’exemples) Long dans ce cas
D’où mise au point de méthodes spécifiques Gradient sophistiqué Méthodes itératives, optimisation par morceaux
Plusieurs packages publics disponibles SVMTorch SVMLight SMO …
Cours SVM (L. Orseau) 55/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Bilan : état des recherchesBilan : état des recherches
Deux tâches évidentes Conception de noyaux
Commence à être bien étudié Encore des recherches pour certains types de données
Noyautiser les algorithmes classiques (« kernelization ») SVM Kernel Régression Kernel PCA Clustering (K-means, …) Estimation de densité, détection de nouveauté Tri (ranking) …
Recherche sur la sélection automatique des modèles
(choix des paramètres)
Cours SVM (L. Orseau) 56/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
ExtensionsExtensions
Classification multi-classes
Régression
Détection de « nouveautés »
Analyse en composantes principales par noyaux
Cours SVM (L. Orseau) 57/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
SVM et régressionSVM et régression
Fonction de perte :
Régression linéaire :
Soit à minimiser :
Généralisation :
x x
xx
x
x
xx
x x0
x
Cours SVM (L. Orseau) 58/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
SVM et apprentissage non superviséSVM et apprentissage non supervisé
Détection de « nouveautés »
w /||w||
/||w||
On cherche à séparer au maximum
le nuage de points de l’origine
Cours SVM (L. Orseau) 59/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
BilanBilan
Les méthodes à noyau sont :
Une bonne idée
Destinées à durer
Offrent une boîte à outils
Très versatile
Avec de bons fondements théoriques
E.g. garanties de performance
Cours SVM (L. Orseau) 60/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
BilanBilan
Nouvelle philosophie de représentation
Toute l’information sur les données passe par le filtre de la matrice noyau
De l’information est perdue
Permet des manipulations particulières E.g. ajout d’une constante sur la diagonale marge souple ou
terme de régularisation
Incorporation de connaissances a priori
Matrice noyau : interface entre les modules de traitement
La qualité de l’apprentissage peut être estimée à partir des caractéristiques de
la matrice noyau
Cours SVM (L. Orseau) 61/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Sources documentairesSources documentaires
Ouvrages / articles Cornuéjols & Miclet (10) : Apprentisage artificiel. Concepts et algorithmes. Eyrolles,
2010.
Herbrich (02) : Learning kernel classifiers. MIT Press, 2002.
Schölkopf, Burges & Smola (eds) (98) : Advances in Kernel Methods : Support Vector Learning. MIT Press, 1998.
Schölkopf & Smola (02) : Learning with kernels. MIT Press, 2002.
Shawe-Taylor & Cristianini(04) : Kernel methods for pattern analysis. Cambridge University Press, 2004.
Smola, Bartlett, Schölkopf & Schuurmans (00) : Advances in large margin classifiers. MIT Press, 2000.
Vapnik (95) : The nature of statistical learning. Springer-Verlag, 1995.
Sites web
http://www.kernel-machines.org/ (point d’entrée)
http://www.support-vector.net (point d’entrée)
Cours SVM (L. Orseau) 62/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Les fonctions noyauLes fonctions noyau
Efficacité computationnelle :
Cours SVM (L. Orseau) 63/86
Induction
Les SVMs
• Principe
• Problème
associé
Méthodes à
noyaux
• Fonctions
noyau
. Illustration
. Marge douce
Mise en œuvre
• Validation
• Construction
de
noyaux
Applications
Bilan
Justification impliquant la fonction noyauJustification impliquant la fonction noyau
Norme du vecteur de poids
Espace d’hypothèses de norme bornée
Avec prob ≥ 1-
Fonction de perte (hinge loss)
Alors : Complexité de Rademacher de