Support Vector Machine — Machine à Vecteurs de Support

Résumé

La Support Vector Machine (SVM), ou machine à vecteurs de support, est l’un des algorithmes de classification supervisée les plus puissants et les plus élégants du machine learning. Inventée par Vladimir Vapnik et Alexey Chervonenkis dans les années 1960, puis popularisée dans les années 1990, la SVM repose sur un principe simple mais mathématiquement profond : trouver l’hyperplan qui sépare deux classes en maximisant la marge — la distance entre l’hyperplan et les points les plus proches de chaque classe. Contrairement à de nombreux autres algorithmes, la SVM ne dépend que de ces points critiques, appelés vecteurs de support, ce qui la rend robuste et efficace même dans des espaces de grande dimension. Grâce à l’astuce du kernel trick, elle peut également résoudre des problèmes non linéairement séparables en projetant implicitement les données dans un espace de dimension supérieure.

Principe mathématique

L’hyperplan séparateur

Au cœur de la SVM se trouve la recherche d’un hyperplan séparateur. Dans un espace à n dimensions, cet hyperplan est défini par l’équation :

$$\mathbf{w} \cdot \mathbf{x} + b = 0$$

où w est le vecteur normal à l’hyperplan (il détermine l’orientation), b est le biais (il détermine la position), et x est un point de données. L’hyperplan divise l’espace en deux demi-espaces : d’un côté, tous les points sont classés comme appartenant à la classe +1, de l’autre côté, ils sont classés comme appartenant à la classe −1. La fonction de décision s’écrit :

$$f(\mathbf{x}) = \text{signe}(\mathbf{w} \cdot \mathbf{x} + b)$$

La marge

La clé de la SVM réside dans le concept de marge. La marge est la distance entre l’hyperplan séparateur et les points de données les plus proches de chaque classe. Maximiser cette marge revient à maximiser la confiance de la classification : plus la marge est grande, plus le classifieur est robuste face à des données nouvelles.

Mathématiquement, la marge vaut :

$$\text{marge} = \frac{2}{|\mathbf{w}|}$$

Les contraintes de classification correcte s’écrivent :

$$y_i(\mathbf{w} \cdot \mathbf{x}_i + b) \geq 1 \quad \forall i$$

où yᵢ ∈ {−1, +1} est l’étiquette du i-ème point.

Problème d’optimisation primal

Le problème d’optimisation de la SVM consiste à trouver les valeurs de w et b qui minimisent la norme de w tout en satisfaisant les contraintes de classification :

$$\min_{\mathbf{w}, b} \frac{1}{2} |\mathbf{w}|^2$$

$$\text{sous contraintes : } y_i(\mathbf{w} \cdot \mathbf{x}_i + b) \geq 1 \quad \forall i$$

Cette formulation est un problème d’optimisation convexe quadratique avec des contraintes linéaires. Sa résolution garantit l’existence d’un minimum global unique.

Formulation duale avec multiplicateurs de Lagrange

En introduisant les multiplicateurs de Lagrange αᵢ ≥ 0 pour chaque contrainte, on obtient le problème dual :

$$\max_{\alpha} \sum_{i=1}^{n} \alpha_i – \frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_i \alpha_j y_i y_j (\mathbf{x}_i \cdot \mathbf{x}_j)$$

$$\text{sous contraintes : } \alpha_i \geq 0 \quad \text{et} \quad \sum_{i=1}^{n} \alpha_i y_i = 0$$

Les points pour lesquels αᵢ > 0 sont précisément les vecteurs de support — les seuls points qui influencent la position de l’hyperplan. Tous les autres points ont αᵢ = 0 et n’ont aucun impact sur le modèle final. C’est cette propriété de parcimonie qui donne à la SVM son efficacité mémoire remarquable.

Le kernel trick (astuce du noyau)

Lorsque les données ne sont pas linéairement séparables dans l’espace original, la SVM utilise le kernel trick. L’idée est de projeter les données dans un espace de dimension supérieure (potentiellement infinie) via une fonction de transformation φ, puis d’y chercher un hyperplan séparateur.

Le point crucial est qu’on n’a jamais besoin de calculer explicitement φ(x). Il suffit de calculer le produit scalaire dans l’espace transformé via une fonction noyau :

$$K(\mathbf{x}_i, \mathbf{x}_j) = \phi(\mathbf{x}_i) \cdot \phi(\mathbf{x}_j)$$

Les noyaux les plus courants sont :

• Noyau linéaire : K(xᵢ, xⱼ) = xᵢ · xⱼ — équivalent à la SVM standard sans transformation
• Noyau polynomial : K(xᵢ, xⱼ) = (γ · xᵢ · xⱼ + coef0)^d — capture des interactions polynomiales de degré d
• Noyau RBF (Radial Basis Function) : K(xᵢ, xⱼ) = exp(−γ ||xᵢ − xⱼ||²) — le plus utilisé, crée des frontières de décision complexes et non linéaires
• Noyau sigmoïde : K(xᵢ, xⱼ) = tanh(γ · xᵢ · xⱼ + coef0) — analogue à un réseau de neurones à une couche

Intuition géométrique

Imaginez que vous devez tracer une route entre deux villages ennemis — les points bleus et les points rouges. Vous voulez que cette route soit aussi large que possible, pour que les habitants de chaque village restent le plus loin possible de la frontière et des conflits. Les maisons qui touchent directement le bord de la route, de part et d’autre, sont les vecteurs de support. Ce sont les seules maisons qui comptent pour déterminer où passe la route centrale. Toutes les autres maisons, celles qui sont loin de la frontière, n’influencent pas du tout le tracé.

C’est exactement le principe de la SVM : elle cherche la frontière la plus large possible entre deux classes, et seuls les points qui sont « collés » à cette marge — les support vectors — déterminent la décision finale. Cette intuition explique pourquoi la SVM est si robuste : même si vous ajoutez ou retirez des points éloignés de la frontière, l’hyperplan ne bouge pas.

Si les deux villages sont mélangés et qu’aucune route droite ne peut les séparer, le kernel trick revient à soulever le terrain dans une troisième dimension : en projetant les données vers le haut selon une courbe, on peut souvent trouver un plan séparateur dans cet espace surélevé. C’est comme si, en ajoutant une dimension, on rendait possible ce qui ne l’était pas dans l’espace d’origine.

Implémentation Python

SVM linéaire avec scikit-learn

from sklearn import datasets
from sklearn.svm import SVC, LinearSVC
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import classification_report, confusion_matrix
import numpy as np

# Chargement du dataset Iris (binaire pour la démonstration)
iris = datasets.load_iris()
X = iris.data[:, :2]  # On garde 2 caractéristiques pour la visualisation
y = (iris.target != 0).astype(int)  # Classification binaire : setosa vs non-setosa

# Division train/test
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.3, random_state=42, stratify=y
)

# Standardisation — cruciale pour la SVM !
scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)
X_test_scaled = scaler.transform(X_test)

# SVM linéaire
svm_linear = SVC(kernel="linear", random_state=42)
svm_linear.fit(X_train_scaled, y_train)

# Prédictions et évaluation
y_pred = svm_linear.predict(X_test_scaled)
print("Matrice de confusion (SVM linéaire) :")
print(confusion_matrix(y_test, y_pred))
print(f"\nVecteurs de support : {svm_linear.n_support_}")

Comparaison RBF vs Polynomial

import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap

# Création d'une grille pour la visualisation
def plot_decision_boundary(model, X, y, title):
    x_min, x_max = X[:, 0].min() - 0.5, X[:, 0].max() + 0.5
    y_min, y_max = X[:, 1].min() - 0.5, X[:, 1].max() + 0.5
    xx, yy = np.meshgrid(np.linspace(x_min, x_max, 200),
                         np.linspace(y_min, y_max, 200))

    Z = model.predict(np.c_[xx.ravel(), yy.ravel()])
    Z = Z.reshape(xx.shape)

    cmap = ListedColormap(["#FFAAAA", "#AAAAFF"])
    plt.contourf(xx, yy, Z, alpha=0.3, cmap=cmap)

    plt.scatter(X[:, 0], X[:, 1], c=y, cmap=ListedColormap(["#FF0000", "#0000FF"]),
                edgecolors="k", s=50)

    # Mise en évidence des support vectors
    sv = model.support_vectors_
    plt.scatter(sv[:, 0], sv[:, 1], s=150, facecolors="none",
                edgecolors="gold", linewidths=2, label="Support Vectors")

    plt.title(title, fontsize=14)
    plt.xlabel("Caractéristique 1")
    plt.ylabel("Caractéristique 2")
    plt.legend()
    plt.tight_layout()
    plt.show()

# SVM avec noyau RBF (par défaut)
svm_rbf = SVC(kernel="rbf", C=1.0, gamma="scale", random_state=42)
svm_rbf.fit(X_train_scaled, y_train)

# SVM avec noyau polynomial
svm_poly = SVC(kernel="poly", degree=3, C=1.0, gamma="scale", coef0=1, random_state=42)
svm_poly.fit(X_train_scaled, y_train)

# Visualisation
fig, axes = plt.subplots(1, 3, figsize=(18, 5))

# Tracé linéaire
plot_decision_boundary(svm_linear, X_train_scaled, y_train, "SVM Linéaire")
# Tracé RBF
plot_decision_boundary(svm_rbf, X_train_scaled, y_train, "SVM RBF (gamma=scale)")
# Tracé polynomial
plot_decision_boundary(svm_poly, X_train_scaled, y_train, "SVM Polynomiale (degré=3)")

Impact du paramètre C

Le paramètre C contrôle le compromis entre une marge large et un faible nombre d’erreurs de classification sur les données d’entraînement :

# Comparaison de différentes valeurs de C
fig, axes = plt.subplots(1, 3, figsize=(18, 5))
C_values = [0.1, 1.0, 100.0]

for i, C_val in enumerate(C_values):
    svm = SVC(kernel="rbf", C=C_val, gamma="scale", random_state=42)
    svm.fit(X_train_scaled, y_train)

    x_min, x_max = X_train_scaled[:, 0].min() - 0.5, X_train_scaled[:, 0].max() + 0.5
    y_min, y_max = X_train_scaled[:, 1].min() - 0.5, X_train_scaled[:, 1].max() + 0.5
    xx, yy = np.meshgrid(np.linspace(x_min, x_max, 200),
                         np.linspace(y_min, y_max, 200))
    Z = svm.predict(np.c_[xx.ravel(), yy.ravel()]).reshape(xx.shape)

    axes[i].contourf(xx, yy, Z, alpha=0.3, cmap=ListedColormap(["#FFAAAA", "#AAAAFF"]))
    axes[i].scatter(X_train_scaled[:, 0], X_train_scaled[:, 1], c=y,
                    cmap=ListedColormap(["#FF0000", "#0000FF"]), edgecolors="k", s=50)
    axes[i].set_title(f"C = {C_val} | Support vectors : {svm.n_support_}")

plt.tight_layout()
plt.show()

• C petit (0.1) : marge large, tolérance aux erreurs — modèle plus général, risque de sous-apprentissage
• C moyen (1.0) : bon équilibre — souvent un bon point de départ
• C grand (100.0) : marge étroite, classification stricte — risque de surapprentissage (overfitting)

Impact du paramètre gamma (RBF)

Le paramètre gamma du noyau RBF contrôle l’influence de chaque point d’entraînement :

fig, axes = plt.subplots(1, 3, figsize=(18, 5))
gamma_values = [0.01, 1.0, 10.0]

for i, g in enumerate(gamma_values):
    svm = SVC(kernel="rbf", C=1.0, gamma=g, random_state=42)
    svm.fit(X_train_scaled, y_train)

    x_min, x_max = X_train_scaled[:, 0].min() - 0.5, X_train_scaled[:, 0].max() + 0.5
    y_min, y_max = X_train_scaled[:, 1].min() - 0.5, X_train_scaled[:, 1].max() + 0.5
    xx, yy = np.meshgrid(np.linspace(x_min, x_max, 200),
                         np.linspace(y_min, y_max, 200))
    Z = svm.predict(np.c_[xx.ravel(), yy.ravel()]).reshape(xx.shape)

    axes[i].contourf(xx, yy, Z, alpha=0.3, cmap=ListedColormap(["#FFAAAA", "#AAAAFF"]))
    axes[i].scatter(X_train_scaled[:, 0], X_train_scaled[:, 1], c=y,
                    cmap=ListedColormap(["#FF0000", "#0000FF"]), edgecolors="k", s=50)
    axes[i].set_title(f"gamma = {g} | Support vectors : {svm.n_support_}")

plt.tight_layout()
plt.show()

• gamma petit (0.01) : grande influence par point — frontière douce, risque de sous-apprentissage
• gamma moyen (1.0) : influence localisée — bon compromis
• gamma grand (10.0) : influence très locale — frontière très irrégulière, risque de surapprentissage

LinearSVC pour les grands datasets

Pour les datasets de grande taille, LinearSVC est plus efficace que SVC(kernel="linear") car il utilise l’algorithme liblinear au lieu de libsvm :

from sklearn.svm import LinearSVC

# LinearSVC — plus rapide sur les grands datasets
linear_svc = LinearSVC(C=1.0, max_iter=10000, random_state=42)
linear_svc.fit(X_train_scaled, y_train)

print(f"Coefficients : {linear_svc.coef_}")
print(f"Biais (intercept) : {linear_svc.intercept_}")
print(f"Précision test : {linear_svc.score(X_test_scaled, y_test):.4f}")

Hyperparamètres

La SVM possède plusieurs hyperparamètres clés qu’il est essentiel de comprendre et de régler :

Réglage par recherche sur grille

from sklearn.model_selection import GridSearchCV

param_grid = {
    "C": [0.1, 1, 10, 100],
    "gamma": ["scale", "auto", 0.1, 0.01],
    "kernel": ["rbf", "poly", "linear"]
}

grid_search = GridSearchCV(SVC(random_state=42), param_grid,
                           cv=5, scoring="accuracy", n_jobs=-1)
grid_search.fit(X_train_scaled, y_train)

print(f"Meilleurs paramètres : {grid_search.best_params_}")
print(f"Meilleure précision (validation croisée) : {grid_search.best_score_:.4f}")

Avantages et limites

Avantages

• Efficace en haute dimension : la SVM reste performante même lorsque le nombre de caractéristiques dépasse le nombre d’échantillons
• Robuste au surapprentissage : grâce à la maximisation de la marge, elle généralise bien sur des données nouvelles
• Polyvalente grâce aux noyaux : le kernel trick permet de traiter aussi bien les problèmes linéaires que non linéaires
• Parcimonieuse : la décision ne dépend que des vecteurs de support, pas de l’ensemble du dataset d’entraînement
• Convexité garantie : contrairement aux réseaux de neurones, l’optimisation est convexe — il n’y a pas de risque de rester bloqué dans un minimum local
• Fonctionne bien sur des petits datasets : excellente performance même avec quelques centaines d’échantillons

Limites

• Lent sur les grands datasets : la complexité d’entraînement est en O(n²) à O(n³), ce qui rend la SVM peu pratique au-delà de ~100 000 échantillons
• Sensible aux valeurs aberrantes : un outlier mal placé peut fortement influencer la position de l’hyperplan
• Pas de probabilités directes : la SVM ne produit pas naturellement des probabilités (nécessite un recalibrage par validation croisée avec probability=True)
• Difficile à interpréter : avec un noyau RBF, la frontière de décision est une fonction complexe impossible à visualiser en dimensions élevées
• Standardisation obligatoire : les caractéristiques doivent être mises à l’échelle, sinon la SVM donne des résultats médiocres
• Inadapté au multi-classe natif : la SVM est fondamentalement binaire ; le multi-classe passe par des stratégies one-vs-one ou one-vs-rest

4 cas d’usage concrets

1. Classification de textes et filtrage de spam

La SVM excelle dans les tâches de classification de documents textuels. En combinant une SVM linéaire avec une représentation TF-IDF, on obtient un classifieur de spam extrêmement performant. Les caractéristiques sont très nombreuses (un mot = une dimension), mais c’est précisément le domaine où la SVM brille. Des travaux fondateurs de Thorsten Joachims ont démontré que les SVM linéaires surpassent souvent les méthodes probabilistes comme Naive Bayes sur ce type de tâches.

2. Reconnaissance d’images et vision par ordinateur

Avant l’avènement des réseaux de neurones profonds, les SVM étaient l’approche dominante pour la classification d’images. Elles sont encore utilisées aujourd’hui en combinaison avec des extracteurs de caractéristiques comme HOG (Histogram of Oriented Gradients) ou SIFT. Par exemple, la détection de piétons dans les systèmes ADAS des véhicules autonomes utilise souvent des SVM comme classifieur final après extraction de caractéristiques.

3. Bio-informatique et classification de gènes

En génomique, on cherche souvent à classifier des échantillons (sains vs malades) à partir de l’expression de milliers de gènes. Avec typiquement quelques dizaines d’échantillons et des milliers de caractéristiques — un scénario où n ≤ p — la SVM linéaire est l’algorithme de prédilection. Sa capacité à généraliser efficacement dans ce régime la rend incontournable pour l’identification de marqueurs tumoraux et la médecine personnalisée.

4. Détection d’anomalies (One-Class SVM)

La One-Class SVM est une variante qui apprend la distribution d’une classe « normale » et détecte les déviations. Elle est utilisée pour la détection de fraudes bancaires, la surveillance industrielle (détection de pannes), et la cybersécurité (détection d’intrusions). Au lieu de séparer deux classes, elle apprend une frontière compacte autour des données normales et signale tout ce qui se trouve à l’extérieur.

Voir aussi

• Quoi ? Où ? Quand ? Maîtriser la Programmation Python : Guide Complet pour Débutants
• Maîtrisez le Tri par Paquets en Python : Guide Complet pour Débutants