Machines à vecteurs de support et noyaux

Deux espèces d’iris, deux mesures du pétale. À l’entraînement, beaucoup de droites les séparent aussi bien. Une machine à vecteurs de support (SVM, de l’anglais support vector machine) choisit celle autour de laquelle reste la bande vide la plus large, la marge. Les fleurs au bord de la bande, dedans ou du mauvais côté sont les vecteurs de support. Elles seules fixent la frontière : on pourrait supprimer toutes les autres fleurs, la frontière resterait la même. Quand les classes se chevauchent, la bande ne peut pas rester vide, alors la SVM paie une pénalité pour chaque fleur dans la bande ou du mauvais côté. Le nombre C fixe le prix de cette pénalité. Un petit C permet une bande large avec beaucoup de violations ; un grand C exige de garder les fleurs du bon côté, même au prix d’une bande étroite.

À vous d’essayer

• Commencez par les pétales avec C = 100. Combien de fleurs tiennent la frontière, et quelle est la largeur de la bande ?
• Baissez C. Pour quel C la validation est-elle la meilleure, et pour lequel la bande est-elle la plus large à résultat presque égal ?
• Passez aux sépales. Un C sépare-t-il ici les espèces ?
• Passez aux vins. Comparez « x seul », les variables √2·x et x², et le noyau (x·z + 1)². Puis passez au noyau RBF et poussez γ (la vitesse à laquelle la ressemblance de deux vins baisse quand ils s’éloignent) jusqu’à 1000.

Une fois vérifié dans le lab, mettons des mots sur ce que vous voyez.

L’idée en termes simples

Une SVM ne calcule pas de probabilités comme la régression logistique. Elle trace une frontière et deux lignes parallèles, une de chaque côté. La bande entre elles doit être la plus large possible, et les fleurs doivent rester dehors, de leur côté. Une fleur qui ne s’y plie pas reçoit une pénalité égale à la profondeur à laquelle elle entre dans la bande. C’est la perte charnière. Le modèle cherche un équilibre : une bande large d’un côté, C fois la somme des pénalités de l’autre.

Pour C = 0,01, les pénalités ne coûtent presque rien. La bande fait 3,9 cm, et les 70 fleurs d’entraînement sont toutes des vecteurs de support : chacune déplace un peu la frontière. Pour C = 100, chaque violation coûte cher. La bande fait 0,15 cm, et 4 fleurs collées à la frontière la tiennent. Le test, lui, change d’une fleur. Sur les pétales, les espèces sont assez éloignées pour que presque toute droite raisonnable classe bien les mêmes fleurs.

On choisit C comme tout hyperparamètre : par la validation, pas par le test. Le lab calcule une validation croisée en 5 parties à l’intérieur des 70 fleurs d’entraînement. La meilleure arrive pour C = 10 : 69 sur 70. Pour C = 0,1, c’est 68 sur 70, et la bande fait 1,4 cm au lieu de 0,34 cm. Une fleur d’écart est du bruit en validation, et une bande plus large appuie la frontière sur plus de fleurs. Le plus petit C exagère dans l’autre sens : 64 sur 70.

La frontière n’a pas à être droite. Sur les vins, on demande seulement si un vin est du cépage 2 ou d’un autre : il y a donc deux classes. Le cépage 2 se trouve au milieu de l’axe des flavonoïdes : le cépage 1 en a 2,98 en moyenne, le cépage 2 2,08 et le cépage 3 0,78. Un seul seuil ne découpe pas le milieu, donc la SVM linéaire préfère ne désigner le cépage 2 nulle part. Validation : 60,0 %, autant que répondre « toujours un autre cépage ». Remplaçons x par deux variables : √2·x et x². Les vins se posent sur une parabole, et une droite dans le plan (√2·x, x²) donne deux seuils sur l’axe, donc un intervalle. La validation monte à 72,0 %.

Un noyau fait la même chose sans ajouter de colonnes. La SVM n’a besoin que des produits scalaires entre paires d’exemples. Le produit scalaire est la somme des produits des coordonnées correspondantes de deux exemples ; la SVM s’en sert comme mesure de leur ressemblance. Le noyau (x·z + 1)² donne exactement le produit scalaire des vecteurs (1, √2·x, x²), donc la frontière est identique à celle des variables √2·x et x². C’est l’astuce du noyau. Le noyau RBF (de radial basis function, fonction à base radiale) exp(−γ(x − z)²) mesure la ressemblance par la distance : γ dit à quelle vitesse la ressemblance baisse quand deux vins s’éloignent. Il correspond à une infinité de telles variables. Pour γ = 3, la validation vaut 78,4 %, la meilleure des huit valeurs de γ, et le test donne ensuite 84,9 %. Pour γ = 0,3, 1 et 10, elle vaut 76,8 %, seulement 2 vins sur 125 de moins. Comme pour C sur les iris, c’est pratiquement un match nul. Pour γ = 1000, l’entraînement monte à 89,6 % et la validation tombe à 69,6 %. La frontière se brise alors en 11 intervalles ajustés à des vins isolés. Le test le plus haut, 86,8 %, arrive pour γ = 100, mais choisir par le test, c’est choisir avec les données qui servent à juger.

Jak to policzono

• Iris : Iris (Fisher, 1936 ; UCI, licence CC BY 4.0), 100 fleurs versicolor et virginica. Mesures en centimètres sans mise à l’échelle, car les deux variables ont la même unité. Découpage stratifié : 70 fleurs pour apprendre, 30 pour le test.
• Vins : Wine (Aeberhard et Forina, 1992 ; UCI, licence CC BY 4.0), 178 vins, la seule teneur en flavonoïdes, C = 1. Découpage : 125 vins pour apprendre, 53 pour le test. Les scores z viennent des seuls vins d’apprentissage, et en validation des vins d’apprentissage de chaque partie.
• Validation : validation croisée stratifiée en 5 parties à l’intérieur de l’entraînement. Modèle : une SVM à marge souple ; les chiffres concordent avec SVC de scikit-learn.

Pourquoi ça marche

Une bande large, c’est de la régularisation, comme la pénalité ridge de la leçon 3.4. La bande fait 2/‖w‖ de large, donc une bande large veut dire de petits poids et une frontière qui dépend moins de fleurs isolées. La marge avec pénalité pour les violations a été décrite par Cortes et Vapnik (1995). L’astuce du noyau est arrivée plus tôt dans les SVM, avec Boser, Guyon et Vapnik (1992) : comme le modèle n’utilise que des produits scalaires, chacun peut être remplacé par un noyau.

Que C change la géométrie plus que le résultat n’est pas un hasard d’un découpage. Sur 20 autres découpages des iris, l’exactitude de test sur les 9 valeurs de C varie au plus de 2 fleurs sur 30, tandis que la bande rétrécit de 3,8–4,1 cm à 0,17–0,36 cm.

Le noyau RBF mesure des distances, donc les unités comptent. Les vins ont 13 mesures : la proline monte jusqu’à 1680, la teinte au plus à 1,71. Sans mise à l’échelle, la distance n’est presque que de la proline. Une SVM RBF sur les 13 mesures trouve alors, sur 20 découpages, 67,2 % des vins de validation en moyenne. Avec une mise à l’échelle apprise sur la seule partie d’apprentissage : 97,9 %.

Une erreur fréquente

Vrai ou faux : « prenez toujours le noyau RBF, c’est le plus souple ». Faux. Sur les pétales d’iris, une SVM linéaire et une SVM RBF, chacune avec ses réglages choisis par validation, trouvent en moyenne 28,5 fleurs de test sur 30 sur 20 découpages. RBF fait mieux sur 1 découpage et moins bien sur 1. La frontière est ici presque droite : la souplesse n’apporte rien et coûte quelque chose, deux hyperparamètres à régler au lieu d’un et un surapprentissage plus facile (γ = 1000 sur les vins). Dans le code ci-dessous, la linéaire obtient 0,950, la RBF 0,947, et RBF fait mieux sur 2 découpages et moins bien sur 4.

La leçon pratique : commencez par un noyau linéaire ou par une régression logistique. Passez au RBF quand la validation montre que la frontière n’est pas droite, comme sur les vins.

import numpy as np
from sklearn.datasets import load_iris, load_wine
from sklearn.model_selection import train_test_split, StratifiedKFold, GridSearchCV, cross_val_score
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.svm import SVC

iris = load_iris(as_frame=True)
keep = iris.target > 0
X, y = iris.data.loc[keep, ["petal length (cm)", "petal width (cm)"]], iris.target[keep]
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.3, stratify=y, random_state=0)
for C in [0.01, 1, 100]:
    m = SVC(kernel="linear", C=C).fit(X_tr, y_tr)
    print(f"C = {C:>6}: band {2 / np.linalg.norm(m.coef_):.2f} cm, {m.n_support_.sum()} support vectors of {len(y_tr)}, test {m.score(X_te, y_te):.3f}")
grids = {"linear": {"svc__kernel": ["linear"], "svc__C": [0.01, 0.1, 1, 10, 100]},
         "RBF": {"svc__kernel": ["rbf"], "svc__C": [0.1, 1, 10, 100], "svc__gamma": [0.01, 0.1, 1, 10]}}
test = {k: [] for k in grids}
for seed in range(20):
    X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.3, stratify=y, random_state=seed)
    cv = StratifiedKFold(5, shuffle=True, random_state=seed)
    for k, grid in grids.items():
        search = GridSearchCV(make_pipeline(StandardScaler(), SVC()), grid, cv=cv).fit(X_tr, y_tr)
        test[k].append(search.score(X_te, y_te))
lin, rbf = np.array(test["linear"]), np.array(test["RBF"])
print(f"20 splits, settings chosen in validation: test linear {lin.mean():.3f}, RBF {rbf.mean():.3f}; RBF better {(rbf > lin).sum()}, worse {(rbf < lin).sum()}, equal {(rbf == lin).sum()}")
wine = load_wine()
cv = StratifiedKFold(5, shuffle=True, random_state=0)
for name, model in [("raw", SVC()), ("scaled inside each fold", make_pipeline(StandardScaler(), SVC()))]:
    print(f"wine, RBF SVM, {name}: validation {cross_val_score(model, wine.data, wine.target, cv=cv).mean():.3f}")

C =   0.01: band 4.21 cm, 70 support vectors of 70, test 1.000
C =      1: band 0.71 cm, 22 support vectors of 70, test 1.000
C =    100: band 0.37 cm, 12 support vectors of 70, test 1.000
20 splits, settings chosen in validation: test linear 0.950, RBF 0.947; RBF better 2, worse 4, equal 14
wine, RBF SVM, raw: validation 0.657
wine, RBF SVM, scaled inside each fold: validation 0.983