Apprentissage Automatique
Cours 6
Machines à Vecteurs Support
Séparateurs à Vaste Marge SVM
Support Vector Machines
Mazari ac
M1-Informatique (ISTW)
[Link]
Approche Générale
• Les machines à vecteurs de support ou
séparateurs à vastes marges (notées SVM
pour Support Vector Machines) [Gun 98] ont
été introduites lors de la conférence COLT en
1992 [Bos 92]. Elles s'appliquent aussi bien à
des problèmes linéairement séparables que
non séparables.
Sources
La majeure partie provient de : « Fouille de données dans
les corpus de textes, Classification supervisée : SVM. »
Michèle Jardino, LIMSI
SVM, Support Vector Machines, Marti Hearst, Berkeley,
[Link]
[Link]
"Using very large corpora/Spelling correction/clustering"
SVM, Séparateurs à Vastes Marges, Antoine
Cornuéjols, Orsay [Link]
2
Plan
Classification binaire
généralités
– exemples et définition
– linéaire/non-linéaire
– séparable/non séparable
Perceptron
Séparateurs (classifieurs) à Vastes Marges
Fonctions noyau
3
GÉNÉRALITÉS
4
Classification binaire : exemples
Filtrage du courrier électronique : (spam / non spam)
Classification des messages (urgent / non urgent)
Recherche d'information (correct / incorrect)
Classification des opinions (positive / négative)
Classifications multiples
Transformation en classification binaire
Pour chaque classe, 1 classe contre toutes les autres
5
Classification binaire
Données : quelques éléments (textes) qui appartiennent à
deux classes différentes
classe 1 (+1 ) et classe 2 (-1 )
ou
classe positive (+1 ) et classe négative (-1 )
Tâche : entraîner un classifieur sur ces données (dites
d'apprentissage) puis prédire la classe d'un nouvel élément
(nouveau texte)
Géométriquement : trouver une séparation entre les deux
classes dans l’espace de représentation (d dimensions)
6
Séparation linéaire / non linéaire
Données séparables linéairement :
tous les points associés aux données peuvent être séparés
correctement par une frontière linéaire
hyperplan séparateur
– Seuil pour un espace de dimension 1
– Droite pour un espace de dimension 2
– Plan pour un espace de dimension 3
7
Données séparables linéairement
Classe 1
Frontière de décision linéaire Classe 2
8
Données non séparables linéairement
Classe 1
Classe 2
9
Données non séparables linéairement
Classe 1
Classifieur Non Linéaire
Classe 2
10
Algorithmes linéaire / non linéaire
Données séparables linéairement ou non linéairement ?
réponse empirique
Algorithmes Linéaires
Algorithmes qui trouvent une frontière linéaire
Quand on pense que les données sont linéairement séparables
Avantages
– Simples, peu de paramètres à régler
Désavantages
– Données dans espace de grande dimension sont souvent non linéairement
séparables
Exemples d'algorithmes : Perceptron, SVM
Note : on peut utiliser des algorithmes linéaires pour des problèmes non
linéaires
– voir fonctions noyau en fin de cours
11
Algorithmes linéaire / non linéaire
Non linéaires
Quand les données sont non linéairement séparables
Avantages
– Plus précis
Désavantages
– Plus complexes, plus de paramètres à régler
Note: la distinction entre linéaire et non linéaire est valable
pour la classification multi-classes
12
Algorithmes linéaires simples
Algorithme du Perceptron
Réseau de neurones à une couche
Linéaire
Classification binaire
En ligne (apprentissage séquentiel, une donnée à la fois )
Apprentissage sur les erreurs
13
Algorithmes linéaires simples
Données : {(xi,yi)}i=1...n
x dans Rd (x est un vecteur dans un espace de dimension d)
à vecteur de caractéristiques
y dans {-1,+1}
à étiquette de la classe
Question:
Trouver une frontière linéaire d’équation wx + b = 0 (hyperplan) telle que la
règle de classification associée donne une probabilité d'erreur minimale
règle de classification (décision):
– y = signe (w x + b) qui signifie :
– si wx + b > 0 alors y = +1
– si wx + b < 0 alors y = -1
From Gert Lanckriet, Statistical Learning Theory Tutorial 14
Classification binaire linéaire
Trouver un hyperplan
(w,b) dans Rd+1
qui classe aussi bien que
possible les données (points)
Progressivement : un point
à la fois, en modifiant les poids
wx + b = 0
si nécessaire
Règle de Classification :
y = signe(wx + b)
From Gert Lanckriet, Statistical Learning Theory Tutorial 15
PERCEPTRON
16
Algorithme du Perceptron
Initialisation : w1 = 0
Mise à jour des poids Pour chaque point x
si classe(x) != decision(x,w) wk +1
alors
wk+1 = wk + yixi
k = k + 1 0 wk+1
sinon
wk+1 = wk
-1
decision(x, w): wk x + b = 0
si wx + b >= 0 alors renvoie +1 Wk+1 x + b = 0
Sinon renvoie -1
From Gert Lanckriet, Statistical Learning Theory Tutorial 17
Algorithme du Perceptron
Progressif : s'adapte toujours aux nouvelles données
Avantages
Simple et efficace
Garantie d'apprendre un problème linéairement séparable
(convergence, optimum global)
Limitations
Seulement séparations linéaires
Converge seulement pour données séparables
Pas très efficace dès qu'il y a trop de caractéristiques (d trop
grand)
From Gert Lanckriet, Statistical Learning Theory Tutorial 18
- SUPPORT VECTOR MACHINE
- SÉPARATEUR À VASTE MARGE
- MACHINE À VECTEURS SUPPORT
19
Séparateur à Vaste Marge
Une autre famille d'algorithmes linéaires
Intuition (Vapnik, 1965)
Si les classes sont linéairement séparables :
Séparer les données
Hyper-plan “loin” des données :
– large marge
résultats statistiques garantis
– bonne généralisation
MAUVAIS
From Gert Lanckriet, Statistical Learning Theory Tutorial 20
Séparateur à Vaste Marge
Une autre famille d'algorithmes linéaires
Intuition (Vapnik, 1965)
Si les classes sont linéairement séparables :
Séparer les données
Hyper-plan “loin” des données :
– large marge
résultats statistiques garantis
– bonne généralisation
BON
à Classifieur à Marge Maximale
From Gert Lanckriet, Statistical Learning Theory Tutorial 21
Séparateur à Vaste Marge
Si non séparable linéairement
Permettre quelques erreurs : perméabilité
Essayer encore de placer un hyperplan “loin” de chaque classe
From Gert Lanckriet, Statistical Learning Theory Tutorial 22
Séparateur à Vaste Marge
Avantages
Meilleur théoriquement
barres d'erreurs mieux connues
Limitations
Calculs plus coûteux
Programmation/Optimisation quadratique
23
Vecteurs Support
wTxa + b = 1
Classifieur Vaste Marge M
wTxb + b = -1
Cas linéairement séparable
But :
trouver l' hyperplan qui maximise la marge
wT x + b = 0
Vecteurs Support
From Gert Lanckriet, Statistical Learning Theory Tutorial 24
Hyperplan de plus vaste marge
Hyperplan
valide
Marge
maximale
Hyperplan
optimal
25
Optimisation de la marge
Hyperplan
valide
Marge
maximale
w D(x) > 1
1
Vecteurs w
de support
Hyperplan D(x) = +1
D(x) < -1 optimal
D(x) = 0
D(x) = -1
26
Optimisation de la marge
w.x + b
La distance d’un point à l’hyperplan est : D(x) =
w
L’hyperplan optimal est celui pour lequel la distance aux points les plus
proches est maximale.
2
La marge entre les deux classes vaut
w
Maximiser la marge revient donc à
⎧ 1 2
minimiser w sous contraintes: ⎪ min w
⎨ 2
⎪ ∀i y (w. x + b) ≥ 1
⎩ i i
27
PROBLÈME NON LINÉAIRE
33
Problèmes non linéairement
séparables dans X
La majorité des problèmes !!!
Idée :
Projeter dans un espace de redescription de très
grande dimension
➥ Presque toujours le problème devient linéairement
séparable
Mais :
Fléau de la dimensionalité
d explose !!?
34
Problème non linéaire
35
Problème non linéaire
36
Fonctions noyau
Famille d’algorithmes non linéaires
Transforme un problème non linéaire en un problème
linéaire
Projection des données dans un espace de traits
caractéristiques différents
– de plus grande dimension
Utilisation d’algorithmes linéaires dans le nouvel espace
From Gert Lanckriet, Statistical Learning Theory Tutorial 37
! M(#'%'#+0')/0&2#/(#+0')/0&2[#2'#?/,,/'@#?/&#q#
M(#'%'#+0')/0&2#/(#+0')/0&2[#2'#?/,,/'@#?/&#q#
Fonction noyau
2 2
Cours Cours
« SVM«etSVM
(x , x ) → (x , x )
et1méthodes
méthodes à noyaux
à2 noyaux » Cornuéjols)
» 1 (A. 2 (A. Cornuéjols) 3835 /
35 / 74
Issu de A. Cornuéjols
$4/'-2E2'@#F2#&2?&),2'@/J%'#0F)/+#
! $4/'-2E2'@#F2#&2?&),2'@/J%'#0F)/+#
Fonction noyau
Issu de A. Cornuéjols 39
Cours « SVM et méthodes à noyaux » (A. Cornuéjols) 38 /
Principe de méthodes à base de
fonctions noyau
Φ : Rd à RD (D >> d)
wTΦ(x)+b=0
X=[x z] Φ(X)=[x2 z2 xz]
f(x) = signe(w1x2+w2z2+w3xz +b)
From Gert Lanckriet, Statistical Learning Theory Tutorial 40
Les fonctions noyau
… encodent :
Une mesure de similarité sur les données
Les fonctions de décision
Le type de régularisation réalisée
– ex : les fonctions gaussiennes favorisent les solutions régulières
Le type de covariance dans l’espace des entrées
– ex : fonctions noyau invariantes par rotation
Sorte de distribution de probabilité a priori sur l’espace des
hypothèses
44
RÉALISATIONS
46
La mise en pratique
Il faut choisir :
Le type de fonction noyau K
– sa forme
– ses paramètres
La valeur de la constante C
La sélection rigoureuse de ces paramètres exige une estimation de la
dimension de Vapnik-Chervonenkis et l’application de la borne de
généralisation ε
Dans le cas séparable, il est possible de déterminer ces paramètres
Dans le cas non séparable, il faut tester avec des méthodes empiriques
pour faire le meilleur choix
47
Exemple : données d'apprentissage
48
Effet des paramètres de contrôle
Apprentissage de deux classes
exemples tirés uniformément sur l'échiquier
SVM à noyau gaussien (base radiale)
2
x−x'
−
2σ 2
K(x, x ') = e
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
49
Paramètres de contrôle : les fonctions
noyau
47 exemples (22 +, 25 -)
Exemples critiques : 4 + et 3 -
Ici fonction polynomiale de degré 5 et C = 10000
[Link] 50
Paramètres de contrôle : fonctions
noyau
(5-, 4+) (3-, 4+) (5-, 4+)
47 exemples (22 +, 25 -)
Exemples critiques : 4 + et 3 - Ici fonction polynomiale de degré 2, 5, 8 et C = 10000
(10-, 11+) (8-, 6+) (4-, 5+)
Ici fonction Gaussienne de σ = 2, 5, 10, 20 et C = 10000
51
Ajout de quelques points ...
47 + 8 exemples (30 +, 25 -)
Exemples critiques : 5 + et 8 -
Ici fonction polynomiale de degré 5 et C = 10000
[Link]
52
Domaines d’application des SVMs
Traitement d’images
– Reconnaissance de caractères manuscrits
– Reconnaissance de scènes naturelles
– Reconnaissance de visages
Entrées : image bidimensionnelle en couleur ou en
niveaux de gris
Sortie : classe (chiffre / personne)
53
Domaines d’application des SVMs
Catégorisation de textes
– Classification d’e-mails
– Classification de pages web
Entrées : document texte, html, etc.
– Approche « sac de mots »
– Document = vecteur de mots (lemmatisés pondérés par tf-idf)
Sortie : catégorie (thème, spam/non-spam)
Noyau :
– Produit scalaire des vecteurs
– C = ∞ (marge dure)
54
Domaines d’application des SVMs
Diagnostic médical
– Évaluation du risque de cancer
– Détection d’arythmie cardiaque
– Évaluation du risque d’accidents cardio-vasculaires à moins
de 6 ans
Entrées : état du patient (sexe, age, bilan sanguin, …)
Sortie :
– Classe : à risque ou non
– Probabilité d’accident à échéance donnée
55
Domaines d’application des SVMs
Étude de séquences en bio-informatique
– Biologie structurale prédictive (prédiction de structure secondaire du
génome)
– Identification de régions codantes de l’ADN génomique
– Phylogénie …
Entrées : chaînes d’acides aminées
Sortie :
– Structure secondaire
– Intron / exon
– Ancêtre
Noyau relationnel :
– Modèle génératif
(chaînes de Markov : insertion, délétion, remplacement, …)
61
Autres domaines d’applications
• Classification de données physiques,
Classification de documents numériques.
• Reconnaissance d’expressions faciales,
Classification de textures, e-learning.
• Détection d’intrusion, Reconnaissance de la
parole.
• Reconnaissance d’Image Basée Contenu (CBIR :
Content Based Image Retrieval).
62
Conclusion