SVM : Machines à Support de Vecteurs - Georges Gardarin

SVM : Machines à Vecteurs de Support
ou Séparateurs à Vastes Marges
Mohamadally Hasan
Fomani Boris
BD Web, ISTY3
Versailles St Quentin, France
hmohamad@isty-info.uvsq.fr
bfomanik@isty-info.uvsq.fr 16 janvier 2006 Résumé : Nous présentons une description d'une méthode de classification
par apprentissage particulière, les SVM. Etant donné que les algorithmes
liés aux SVM sont composés de calculs et de fonctions mathématiques
complexes, nous avons décidé de diviser la présentation en différentes
parties, une destinée à un large public où nous décrivons de façon simple
et assez complète les principes de fonctionnement et une destinée à un
public plus ciblé où nous décrivons en détails l'aspect mathématiques des
SVM. Nous intéressons aussi aux différents domaines d'application et nous
insistons sur l'utilisation des machines à supports de vecteurs dans
Oracle. Mots-clés : Apprentissage supervisé, Induction, Classification, Séparateur
à Vaste Marge, Support Vector Machine, Machine à Support de Vecteurs,
Oracle Data Mining Structure : Dans la section 1, nous présentons les SVM et nous effectuons
un rappel sur la notion d'apprentissage. Ensuite dans la section 2, nous
décrivons de manière générale le principe de fonctionnement des SVM. Les
fondements mathématiques sont détaillés dans la section 3. Dans la section
4, nous nous intéressons aux différents domaines d'applications des SVM.
Nous finissons par une présentation de l'implémentation de SVM dans Oracle
dans la section 5 Introduction
Parmi les méthodes à noyaux, inspirées de la théorie statistique de
l'apprentissage de Vladimir Vapnik, les SVM constituent la forme la plus
connue. SVM est une méthode de classification binaire par apprentissage
supervisé, elle fut introduite par Vapnik en 1995. Cette méthode est donc
une alternative récente pour la classification. Cette méthode repose sur
l'existence d'un classificateur linéaire dans un espace approprié. Puisque
c'est un problème de classification à deux classes, cette méthode fait
appel à un jeu de données d'apprentissage pour apprendre les paramètres du
modèle. Elle est basée sur l'utilisation de fonction dites noyau (kernel)
qui permettent une séparation optimale des données.
Dans la présentation des principes de fonctionnements, nous
schématiserons les données par des « points » dans un plan.
La notion d'apprentissage étant importante, nous allons commencer par
effectuer un rappel. L'apprentissage par induction permet d'arriver à des
conclusions par l'examen d'exemples particuliers. Il se divise en
apprentissage supervisé et non supervisé. Le cas qui concerne les SVM est
l'apprentissage supervisé. Les exemples particuliers sont représentés par
un ensemble de couples d'entrée/sortie. Le but est d'apprendre une fonction
qui correspond aux exemples vus et qui prédit les sorties pour les entrées
qui n'ont pas encore été vues. Les entrées peuvent être des descriptions
d'objets et les sorties la classe des objets donnés en entrée. SVM principe de fonctionnement général 1 Notions de base : Hyperplan, marge et support vecteur
Pour deux classes d'exemples donnés, le but de SVM est de trouver un
classificateur qui va séparer les données et maximiser la distance entre
ces deux classes. Avec SVM, ce classificateur est un classificateur
linéaire appelé hyperplan.
Dans le schéma qui suit, on détermine un hyperplan qui sépare les deux
ensembles de points. [pic] Les points les plus proches, qui seuls sont utilisés pour la détermination
de l'hyperplan, sont appelés vecteurs de support. [pic] Il est évident qu'il existe une multitude d'hyperplan valide mais la
propriété remarquable des SVM est que cet hyperplan doit être optimal. Nous
allons donc en plus chercher parmi les hyperplans valides, celui qui passe
« au milieu » des points des deux classes d'exemples. Intuitivement, cela
revient à chercher l'hyperplan le « plus sûr ». En effet, supposons qu'un
exemple n'ait pas été décrit parfaitement, une petite variation ne
modifiera pas sa classification si sa distance à l'hyperplan est grande.
Formellement, cela revient à chercher un hyperplan dont la distance
minimale aux exemples d'apprentissage est maximale. On appelle cette
distance « marge » entre l'hyperplan et les exemples. L'hyperplan
séparateur optimal est celui qui maximise la marge. Comme on cherche à
maximiser cette marge, on parlera de séparateurs à vaste marge. [pic] 2 Pourquoi maximiser la marge ?
Intuitivement, le fait d'avoir une marge plus large procure plus de
sécurité lorsque l'on classe un nouvel exemple. De plus, si l'on trouve le
classificateur qui se comporte le mieux vis-à-vis des données
d'apprentissage, il est clair qu'il sera aussi celui qui permettra au mieux
de classer les nouveaux exemples. Dans le schéma qui suit, la partie droite
nous montre qu'avec un hyperplan optimal, un nouvel exemple reste bien
classé alors qu'il tombe dans la marge. On constate sur la partie gauche
qu'avec une plus petite marge, l'exemple se voit mal classé.
[pic]
En général, la classification d'un nouvel exemple inconnu est donnée
par sa position par rapport à l'hyperplan optimal. Dans le schéma suivant,
le nouvel élément sera classé dans la catégorie des « + ».
[pic]
3 Linéarité et non-linéarité
Parmi les modèles des SVM, on constate les cas linéairement séparable
et les cas non linéairement séparable. Les premiers sont les plus simple de
SVM car ils permettent de trouver facilement le classificateur linéaire.
Dans la plupart des problèmes réels il n'y a pas de séparation linéaire
possible entre les données, le classificateur de marge maximale ne peut pas
être utilisé car il fonctionne seulement si les classes de données
d'apprentissage sont linéairement séparables. [pic] 4 Cas non linéaire
Pour surmonter les inconvénients des cas non linéairement séparable,
l'idée des SVM est de changer l'espace des données. La transformation non
linéaire des données peut permettre une séparation linéaire des exemples
dans un nouvel espace. On va donc avoir un changement de dimension. Cette
nouvelle dimension est appelé « espace de re-description ». En effet,
intuitivement, plus la dimension de l'espace de re-description est grande,
plus la probabilité de pouvoir trouver un hyperplan séparateur entre les
exemples est élevée. Ceci est illustré par le schéma suivant :
[pic] On a donc une transformation d'un problème de séparation non linéaire dans
l'espace de représentation en un problème de séparation linéaire dans un
espace de re-description de plus grande dimension. Cette transformation non
linéaire est réalisée via une fonction noyau. En pratique, quelques
familles de fonctions noyau paramétrables sont connues et il revient à
l'utilisateur de SVM d'effectuer des test pour déterminer celle qui
convient le mieux pour son application. On peut citer les exemples de
noyaux suivants : polynomiale, gaussien, sigmoïde et laplacien.
5 Illustration de transformation de cas non linéaire : le cas XOR
Le cas de XOR n'est pas linéairement séparable, si on place les points
dans un plan à deux dimension, on obtient la figure suivante
Coordonnées des points : (0,0) ; (0,1) ; (1,0) ; (1,1)
[pic] Si on prend une fonction polynomiale (x , y) -> (x , y , x.y) qui fait
passer d'un espace de dimension 2 à un espace de dimension 3, on obtient un
problème en trois dimensions linéairement séparable :
(0,0) -> (0,0,0)
(0,1) -> (0,1,0)
(1,0) -> (1,0,0)
(1,1) -> (1,1,1) [pic] Fondements mathématiques
Nous allons détailler dans les paragraphes ci-dessous les principas
mathématiques sur lesquels repose SVM.
1 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 cette fonction f à partir de la seule observation
d'un certain nombre de couples entrée-sortie {(xi; yi) : i = 1, .. , n}
afin de « prédire » d'autres évènements. On considère un couple (X, Y ) de variables aléatoires à valeurs dans X x
Y.
Seul le cas Y = {-1, 1} (classification) nous intéresse ici (on peut
facilement étendre au cas card(Y) = m > 2 et au cas Y = [pic]). La
distribution jointe de (X, Y ) est inconnue. Sachant qu'on observe un échantillon S = {(X1, Y1),... ,(Xn, Yn)} de n
copies indépendantes de (X, Y ), on veut: construire une fonction h : X > Y
telle que P(h(X) != Y ) soit minimale. Illustration : Trouver une frontière de décision qui sépare l'espace en deux régions (pas
forcément connexes).
[pic] Sur et sous-apprentissage :
[pic]
2 Classification à valeurs réelles
Plutôt que de construire directement h : X> {-1, 1}, on construit :
f : X>R (ensemble des réels).
La classe est donnée par le signe de f ;
h = signe(f) . L'erreur se calcule avec P(h(X) != Y ) = P(Yf(X) ?0). Ceci donne une
certaine idée de la confiance dans la classification. Idéalemen