3.3 Machine à vecteurs supports

Les machines à vecteurs supports (Support Vector Machine en anglais, ou SVM en abrégé) forment une autre famille d’algorithmes utilisables en classification supervisée. Au départ, l’idée est simple : il s’agit de déterminer le meilleur hyperplan qui divise l’hyperespace représenté par les attributs décrivant un cas à deux classes. Avec deux attributs seulement (cas le plus simple, disons x1 et x2), cela signifie que nous recherchons une droite qui divise notre plan x1-x2 en deux, chaque région représentant le domaine de l’une des deux classes.

Jusqu’ici, l’idée nous semble assez similaire à l’ADL. La grosse différence, c’est que dans l’ADL nous utilisons toutes les données pour définir la position de la frontière, alors que dans SVM, nous n’utilisons que les individus au niveau de la frontière qui forment les fameux “vecteurs supports” à l’origine du nom de la technique. Ces vecteurs supports définissent une marge autour de la frontière. Cette dernière est positionnée de telle façon que la marge en question soit la plus large possible. En d’autres termes, nous cherchons à définir un “no-man’s land”, un fossé le plus large possible autour de la frontière tracée entre les deux classes. Cette approche s’avère judicieuse et performante en pratique.

Logique de SVM pour positionner la frontière entre les deux classes à l’aide de vecteurs supports définissant une marge (en jaune) de part et d’autre de la frontière (en rouge). La frontière est tracée de telle façon que cette marge soit la plus large possible (schéma issu de Wikipédia, une fois n’est pas coutume).

Bon, il nous reste à contourner deux limitations pour que la méthode soit utilisable dans des situations plus générales :

  1. La frontière entre les deux classes n’est pas forcément linéaire, et en pratique, la plupart du temps elle ne le sera pas
  2. Comment généraliser à une situation à plus de deux classes ?

Abordons ces deux points successivement ci-dessous.

3.3.1 Approche par noyau

Le problème de frontière non linéaire se résout par une transformation de l’hyperespace initial vers une version déformée habilement par projection. Si la fonction qui effectue la déformation est correctement choisie, une frontière non linéaire peut être linéarisée, un peu comme une transformation bien choisie des données pour un nuage de points peut éventuellement le linéariser (nous avons abondamment utilisé cette astuce en modélisation).

Un noyau \(\phi\) judiceusement choisi (qui n’est rien d’autre qu’une fonction réalisant la transformation) va déformer l’hyperespace de telle façon qu’une frontière non linéaire est linéarisée. (schéma issu de Wikipédia)

La transformation appliquée est une fonction mathématique appelée noyau (kernel en anglais). Un certain nombre de noyaux ont été définis pour transformer des frontières de forme précise. Par exemple, si la frontière initiale est circulaire, un noyau existe pour linéariser cette frontière en transformant notre plan en hyperbole tridimensionnelle en calculant une troisième dimension telle que x3 = x12 + x22. Découper notre hyperbole 3D par une frontière plane revient alors à découper notre plan initial à l’aide d’une frontière circulaire. Ceci est illustré dans la vidéo suivante.

A retenir

Avec SVM, le choix du noyau et de ses paramètres est une étape cruciale pour obtenir de bons résultats. Il se peut que vous ayez à essayer différents noyaux et différents paramètres de manière itérative avant d’arriver à un résultat satisfaisant. Par contre, une fois le noyau correctement définit, la technique s’avère très puissante.

3.3.2 SVM multiclasses

Bien qu’il ne semble pas évident au premier abord que SVM ne soit définie que pour un cas à deux classes seulement, c’est ainsi que les mathématiciens l’ont développée. Par contre, cette limitation peut être dépasser par une astuce simple : ramener les situations multiclasses à des cas à deux classes. Nous avons déjà observé, en effet, pour la matrice de confusion que nous pouvons toujours réduire un problème multiclasses à deux classes seulement dès lors que nous choisissons une classe cible. Nous calculons ensuite cette classe cible versus tout ce qui n’est pas de cette classe-là. Cette approche est dite “macro”, par contraste avec l’approche “micro” ou les classes sont confrontées individuellement deux à deux.

Par exemple pour trois classes A, B, et C, dans l’approche “macro” nous comparerons A avec B + C en un classifieur unique pour décider si l’item appartient à A ou non. Dans l’approche “micro”, nous comparerons A avec B d’un côté, puis A avec C d’un autre côté (deux classifieurs différents). Nous établirons ensuite un consensus entre ces deux classifieurs pour décider si l’items appartient à la classe A ou non. Ensuite dans les deux approches, nous faisons de même en ciblant cette fois-ci la classe B, et puis finalement la classe C. En rassemblant tous les résultats et en comparant les probabilités d’appartenance aux différentes classes renvoyées par les classifieurs individuels bi-classes, nous obtenons finalement un classifieur global multiclasses. C’est ainsi que SVM multiclasses fonctionne.

La décomposition d’un classifieur multiclasses en une série de classifieurs bi-classes par approche “macro” ou “micro” est utile en SVM. Elle l’est aussi pour établir des métriques de performance globales sur base de métriques qui ne se calculent normalement qu’en mode bi-classe.

C’est le cas du score F. Ainsi nous pouvons calculer un score F global pour l’ensemble d’un classifieur multiclasses en moyennant les scores F bi-classes individuels. Par contre, comme deux approches co-existent, nous avons donc deux versions : le score F “micro” et le score F “macro”. Le premier déterminera une balance entre les comparaisons deux à deux (un comparé à un) de toutes les classes, tandis que le second envisagera le problème de manière plus globale (un comparé à tous). Les deux points de vue se complètent plus qu’ils ne s’opposent.

Les scores F “micro” et “macro” sont des métriques globales plus utiles que le taux global de reconnaissance (TGR) car ils tiennent compte des performances pour toutes les classes là ou le TGR ne quantifie la situation que de manière générale, délaissant ainsi la classification réalisée pour les classes les plus rares au bénéfice des classes abondantes. Pour faire un parallèle avec la régression, le R2 est un critère utile pour définir l’ajustement d’une droite, mais le critère d’Akaiké sera plus efficace pour définir le meilleur modèle. En classification, c’est pareil : le TGR quantifie les performances globales, mais les scores F micro et macro sont des biens meilleurs critères pour choisir son classifieur optimal.

Les scores F micro et macro sont calculés sur nos objets confusion et renvoyés par summary(). Prenez donc la bonne habitude de les utiliser comme critères globaux de performance de vos classifieurs multiclasses de préférence au TGR ou au taux d’erreur globale.
A retenir

Les approches “micro” et “macro” permettent toutes deux de transformer un problème multiclasses en plusieurs problèmes bi-classes. C’est autant utile pour certains algorithmes comme SVM que pour certaines métriques comme le score F.

3.3.3 SVM et Pima

Voyons maintenant ce que donne une SVM sur notre jeu de données pima1. Une version de SVM étant disponible dans {mlearning}, nous pouvons appliquer cet algorithme facilement avec un code R qui nous est à présent familier (nous choisissons ici la validation croisée dix fois pour en quantifier les performances).

library(mlearning)
set.seed(3674)
pima1_svm <- mlSvm(data = pima1, diabetes ~ .)
pima1_svm_conf <- confusion(cvpredict(pima1_svm, cv.k = 10), pima1$diabetes)
plot(pima1_svm_conf)

summary(pima1_svm_conf)
# 392 items classified with 297 true positives (error = 24.2%)
# 
# Global statistics on reweighted data:
# Error rate: 24.2%, F(micro-average): 0.716, F(macro-average): 0.713
# 
#        Fscore    Recall Precision Specificity       NPV       FPR       FNR
# neg 0.8263254 0.8625954 0.7929825   0.5461538 0.6635514 0.4538462 0.1374046
# pos 0.5991561 0.5461538 0.6635514   0.8625954 0.7929825 0.1374046 0.4538462
#           FDR       FOR     LRPT      LRNT     LRPS      LRNS    BalAcc
# neg 0.2070175 0.3364486 1.900634 0.2515859 2.356920 0.3119842 0.7043746
# pos 0.3364486 0.2070175 3.974786 0.5261402 3.205291 0.4242825 0.7043746
#           MCC    Chisq       Bray Auto Manu A_M  TP FP FN  TN
# neg 0.4319813 73.15029 0.02933673  285  262  23 226 59 36  71
# pos 0.4319813 73.15029 0.02933673  107  130 -23  71 36 59 226

Ici, avec tous les arguments par défaut de mlSvm() nous avons un taux d’erreur de 24%, mais plus important, des F micro et macro d’environ 0.71. Si nous comparons à notre classifieur foret aléatoire sur les mêmes données, nous avions 21% d’erreur et F micro ou macro de 0.75. Donc, notre SVM non optimisé fait moins bien que la forêt aléatoire… mais le travail n’est pas terminé. Le noyau par défaut (kernel =) est radial. Les autres options (voir ?e1071::svm) sont linear pour aucune transformation, polynomial (dans ce cas, préciser aussi degree et coef0, 3 et 0 respectivement par défaut) pour une frontière plus générale et sigmoid (préciser coef0, 0 par défaut).

Un noyau linéaire fait mieux que le noyau radial :

set.seed(857)
pima1_svm2 <- mlSvm(data = pima1, diabetes ~ ., kernel = "linear")
pima1_svm2_conf <- confusion(cvpredict(pima1_svm2, cv.k = 10), pima1$diabetes)
plot(pima1_svm2_conf)

summary(pima1_svm2_conf)
# 392 items classified with 305 true positives (error = 22.2%)
# 
# Global statistics on reweighted data:
# Error rate: 22.2%, F(micro-average): 0.74, F(macro-average): 0.736
# 
#        Fscore    Recall Precision Specificity       NPV       FPR       FNR
# neg 0.8415301 0.8816794 0.8048780   0.5692308 0.7047619 0.4307692 0.1183206
# pos 0.6297872 0.5692308 0.7047619   0.8816794 0.8048780 0.1183206 0.4307692
#           FDR       FOR     LRPT      LRNT     LRPS      LRNS    BalAcc
# neg 0.1951220 0.2952381 2.046756 0.2078605 2.726200 0.2768622 0.7254551
# pos 0.2952381 0.1951220 4.810918 0.4885781 3.611905 0.3668110 0.7254551
#           MCC    Chisq       Bray Auto Manu A_M  TP FP FN  TN
# neg 0.4793765 90.08232 0.03188776  287  262  25 231 56 31  74
# pos 0.4793765 90.08232 0.03188776  105  130 -25  74 31 56 231

On se rapproche des scores de la foret aléatoire cici avec un F micro de 0.74 et un F macro de 0.736. Le noyau sigmoïde est ici désastreux, mais le noyau polynomial de degré 2 et avec un coef0 = 1 donne ceci :

set.seed(150)
pima1_svm3 <- mlSvm(data = pima1, diabetes ~ ., kernel = "polynomial",
  degree = 2, coef0 = 1)
pima1_svm3_conf <- confusion(cvpredict(pima1_svm3, cv.k = 10), pima1$diabetes)
plot(pima1_svm3_conf)

summary(pima1_svm3_conf)
# 392 items classified with 308 true positives (error = 21.4%)
# 
# Global statistics on reweighted data:
# Error rate: 21.4%, F(micro-average): 0.747, F(macro-average): 0.739
# 
#        Fscore    Recall Precision Specificity       NPV        FPR        FNR
# neg 0.8494624 0.9045802 0.8006757   0.5461538 0.7395833 0.45384615 0.09541985
# pos 0.6283186 0.5461538 0.7395833   0.9045802 0.8006757 0.09541985 0.45384615
#           FDR       FOR     LRPT      LRNT     LRPS      LRNS   BalAcc
# neg 0.1993243 0.2604167 1.993143 0.1747124 3.074595 0.2695089 0.725367
# pos 0.2604167 0.1993243 5.723692 0.5017202 3.710452 0.3252461 0.725367
#           MCC    Chisq       Bray Auto Manu A_M  TP FP FN  TN
# neg 0.4934705 95.45714 0.04336735  296  262  34 237 59 25  71
# pos 0.4934705 95.45714 0.04336735   96  130 -34  71 25 59 237

Avec un F micro de 0.747 et un F macro de 0.739, nous nous rapprochons très fortement des performances de la forêt aléatoire.

A retenir

L’algorithme SVM est potentiellement très performant, mais il est délicat parce que de nombreux paramètres doivent être optimisés. Nous n’avons discuté que le noyau, mais il y a aussi la mise à l’échelle des variables ou non, la pondération des observations, etc. comme paramètres optimisables.

Pour en savoir plus