Qu'est-ce qu'une Machine à Vecteurs de Support (SVM) ?

Une Machine à Vecteurs de Support (SVM) est un modèle de classification binaire dont l'idée fondamentale est de trouver un hyperplan optimal dans l'espace des caractéristiques, maximisant ainsi la marge entre les échantillons positifs et négatifs. Contrairement au modèle du percetpron, une SVM ne se contente pas de séparer correctement les échantillons ; elle cherche une frontière de décision robuste — cet hyperplan doit s'éloigner autant que possible de tous les points de données, ce qui lui confère une meilleure capacité de généralisation.

Fig. : Une SVM maximise la marge pour trouver l'hyperplan optimal. La ligne verte indique la direction du vecteur normal, les segments rouges représentent la distance des vecteurs de support à l'hyperplan.

Concepts Clés : Marge et Vecteurs de Support

• Marge : La distance d'un échantillon à l'hyperplan. La SVM vise à maximiser la « marge minimale » (c'est-à-dire la distance de l'échantillon le plus proche de l'hyperplan).
• Vecteurs de Support : Les points de données les plus proches de l'hyperplan. Ce sont ces points qui déterminent sa position.
• Marge Dure : Exige que tous les échantillons soient correctement classés (applicable aux données linéairement séparables).
• Marge Souple : Autorise un petit nombre d'échantillons à violer la contrainte de marge (applicable aux données bruitées).

Formulation du Problème d'Optimisation SVM

Le noyau de la SVM réside dans la résolution d'un problème d'optimisation sous contraintes. Le problème primal peut s'écrire comme suit :

minimiser (1/2) ||W||²
sous la contrainte : y_i (W · X_i + b) ≥ 1, pour i = 1, 2, ..., m

Où W est le vecteur normal de l'hyperplan, b est le terme de biais, et y_i est le label de l'échantillon (+1/-1).

Transformation en Problème Dual

La résolution directe de ce problème est coûteuse. La SVM utilise la dualité lagrangienne pour le convertir en une forme plus tractable. Les étapes clés sont :

1. Introduire des multiplicateurs de Lagrange α_i.
2. Calculer les dérivées partielles par rapport à W et b, et les annuler.
3. Transformer le problème en un problème de programmation quadratique en les α_i.

Fig. : Processus de dérivation mathématique du problème d'optimisation SVM (issu de res/example.png).

L'avantage du problème dual réside dans :

• La transformation du calcul dans un espace de caractéristiques de haute dimension en opérations de produit scalaire entre échantillons.
• L'introduction naturelle des fonctions noyau pour traiter les problèmes non linéaires.
• La parcimonie de la solution : seuls les α_i correspondant aux vecteurs de support sont non nuls.

Fonctions Noyau : Dépasser la Limite de la Séparabilité Linéaire

Lorsque les données ne sont pas linéairement séparables, la SVM utilise des fonctions noyau pour projeter les échantillons dans un espace de plus haute dimension où ils deviennent séparables. Les fonctions noyau courantes copmrennent :

Types de Fonctions Noyau Usuelles

• Noyau Linéaire : K(X_i, X_j) = X_i · X_j (pour les données linéairement séparables)
• Noyau Polynomial : K(X_i, X_j) = (γ X_i · X_j + r)^d (pour les données non linéaires de faible dimension)
• Noyau Gaussien (RBF) : K(X_i, X_j) = exp(-γ ||X_i - X_j||²) (pour les données non linéaires de haute dimension)

La magie réside dans l'astuce du noyau — il n'est pas nécessaire d'effectuer explicitement la projection en haute dimension ; on calcule directement le produit scalaire dans cet espace via la fonction noyau, ce qui réduit considérablement la complexité de calcul.

Marge Souple et Régularisation

Dans la pratique, les données parfaitement linéairement séparables sont rares. La SVM à marge souple permet à quelques échantillons de violer la contrainte de marge, en introduisant des variables d'écart ξ_i et un paramètre de régularisation C pour équilibrer la maximisation de la marge et les erreurs de classification :

minimiser (1/2) ||W||² + C * Σ ξ_i
sous les contraintes :
    y_i (W · X_i + b) ≥ 1 - ξ_i
    ξ_i ≥ 0, pour i = 1, 2, ..., m

• Valeur de C plus grande : Pénalise davantage les erreurs, risque de sur-apprentissage.
• Valeur de C plus petite : Autorise plus d'erreurs, modèle plus simple, risque de sous-apprentissage.

Utilisation Pratique d'une SVM

Étapes Rapides pour Débuter

1. Préparer les Données : S'assurer que les caractéristiques sont standardisées (les SVM sont sensibles à l'échelle des caractéristiques).
2. Choisir une Fonction Noyau : Suivre l'ordre d'essai : noyau linéaire -> noyau polynomial -> noyau gaussien.
3. Ajuster les Paramètres : Optimiser la valeur de C et les paramètres de la fonction noyau via une validation croisée.
4. Entraîner le Modèle : Utiliser des bibliothèques comme LIBSVM ou scikit-learn.
5. Évaluer le Modèle : Prêter attention à la proportion de vecteurs de support et à la performance de généralisation.

Domaines d'Application et Limitations

Scénarios d'Application

• Tâches de classification sur des jeux de données de taille moyenne à petite.
• Problèmes à caractéristiques de haute dimension comme la classification de texte ou la reconnaissance d'images.
• Scénarios nécessitant une bonne capacité de généralisation.

Limitations

• La complexité de calcul augmente de manière significative avec le nombre d'échantillons.
• Sensible aux données manquantes.
• Le choix de la fonction noyau et l'optimisation de ses paramètres peuvent être complexes.