Comprendre Machine à vecteurs de support
Quand deux classes sont séparables, une infinité de frontières atteignent une erreur d’entraînement nulle, et elles ne se valent pas. Une frontière passant très près de certains points d’entraînement est fragile : un échantillon légèrement différent placerait ces points du mauvais côté. La machine à vecteurs de support rend la robustesse explicite en choisissant la frontière qui maximise la marge, la distance au point le plus proche de l’une ou l’autre classe.
La solution obtenue possède une propriété inhabituelle et utile. Seuls les points situés sur la frontière de marge, les vecteurs de support, influencent l’endroit où tombe la frontière. Tout autre point d’entraînement pourrait être déplacé, ou entièrement supprimé, sans changer l’ajustement. Cela contraste vivement avec la régression logistique, où chaque observation contribue à la vraisemblance et donc à l’estimation.
Les données réelles sont rarement proprement séparables, la formulation pratique emploie donc une marge souple qui autorise des violations moyennant un coût. Un paramètre, conventionnellement C, fixe le taux de change : un grand C pénalise lourdement les violations et donne une marge étroite qui épouse de près les données d’entraînement, tandis qu’un petit C tolère davantage de violations pour une frontière plus large et plus stable. C’est le compromis biais-variance qui réapparaît sous un autre nom sur le cadran.
Les frontières non linéaires viennent de l’astuce du noyau. L’optimisation ne dépend des données que par les produits scalaires entre paires de points : remplacer ce produit scalaire par une fonction noyau calcule ce que vaudrait le produit scalaire dans un espace de plus grande dimension, sans jamais construire de coordonnées dans cet espace. Le noyau à base radiale correspond à un espace de dimension infinie et constitue le choix par défaut habituel.
Comment calculer
minimize ½‖w‖² + C Σᵢ ξᵢ subject to yᵢ(w·xᵢ + b) ≥ 1 − ξᵢ, ξᵢ ≥ 0
où
- w, b
- le vecteur de poids et le décalage définissant l’hyperplan séparateur
- ‖w‖
- la norme de w ; la largeur de marge vaut 2/‖w‖, donc minimiser ‖w‖ maximise la marge
- yᵢ ∈ {−1, +1}
- l’étiquette de classe de l’observation i
- ξᵢ
- l’écart : de combien l’observation i empiète dans la marge ou la traverse
- C
- le coût des violations de marge, arbitrant largeur de marge contre erreur d’entraînement
Exemple : Machine à vecteurs de support
Prenez deux amas de points nettement séparés. Bien des droites les séparent, mais la SVM retient celle qui court au milieu du couloir vide entre les classes, aussi loin que possible des deux. Les points touchant les bords de ce couloir sont les vecteurs de support.
Considérez maintenant des données disposées en un amas central d’une classe entouré d’un anneau de l’autre classe. Aucune droite ne peut les séparer. Une SVM linéaire échoue sur ce problème par principe, et non simplement en pratique.
Une SVM à noyau à base radiale les sépare proprement. Le noyau mesure une similarité qui décroît avec la distance, les points proches s’influencent donc fortement et les points éloignés presque pas, ce qui produit une frontière courbe fermée autour de l’amas central. Aucune coordonnée explicite dans l’espace de plus grande dimension n’est jamais calculée.
Avantages et inconvénients
Avantages
- Efficace en grande dimension, y compris quand les variables sont plus nombreuses que les observations.
- La solution ne dépend que des vecteurs de support, elle est donc économe en mémoire à la prédiction.
- Les noyaux offrent des frontières non linéaires souples au sein d’une unique optimisation convexe.
Inconvénients
- L’entraînement passe mal à l’échelle avec le nombre d’observations, ce qui la limite sur de très grands jeux de données.
- Ne produit nativement aucune estimation de probabilité ; la calibration exige une étape d’ajustement supplémentaire.
- Exige une mise à l’échelle des variables et un réglage soigneux de C et des paramètres du noyau.
Questions fréquentes
Pourquoi seule une partie des données détermine-t-elle la frontière ?
Cela découle de l’optimisation. Les points confortablement du bon côté de la marge satisfont leur contrainte avec de la marge à revendre, ils n’exercent donc aucune force sur la solution. Seuls les points sur la marge ou à l’intérieur ont des contraintes actives : ce sont les vecteurs de support.
Que contrôle le paramètre C ?
Le coût de laisser un point violer la marge. Un grand C rend les violations coûteuses et produit une frontière serrée qui risque le surapprentissage ; un petit C permet des violations pour une marge plus large et plus robuste. On le choisit par validation croisée.
Quand préférer un noyau linéaire au noyau RBF ?
Quand les variables sont nombreuses par rapport aux observations, comme en classification de textes, les classes sont fréquemment déjà proches de la séparabilité linéaire, et un noyau linéaire est plus rapide et moins enclin au surapprentissage. Sinon, le RBF est le choix par défaut raisonnable.
En résumé
Une machine à vecteurs de support choisit la frontière de plus large marge, ne dépend que des points les plus proches, et atteint des surfaces de décision non linéaires par des noyaux plutôt que par une construction explicite de variables. Son coût est un mauvais passage à l’échelle en taille d’échantillon et l’absence de probabilités natives.