Machines à vecteurs de support

Machines à vecteurs de support#

L’essence de l’apprentissage statistique est de trouver le bon compromis entre la fidélité aux données et la simplicité du modèle.

Vladimir Vapnik

Les machines à vecteurs de support (Support Vector Machines, SVM) constituent l’une des familles d’algorithmes les plus élégantes de l’apprentissage automatique. Développées par Vladimir Vapnik et ses collaborateurs dans les années 1990, les SVM reposent sur une idée géométrique simple mais puissante : trouver l’hyperplan qui sépare les classes avec la marge maximale. Cette approche, fondée sur la théorie de l’apprentissage statistique, offre des garanties théoriques fortes en termes de généralisation. Grâce à l”astuce du noyau (kernel trick), les SVM peuvent également modéliser des frontières de décision non linéaires sans jamais calculer explicitement la transformation vers un espace de grande dimension.

Ce chapitre couvre les SVM linéaires à marge dure et souple, l’astuce du noyau, les noyaux classiques, l’extension à la régression (SVR), et des exemples complets avec Scikit-learn.

Hide code cell source

 
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
from sklearn import svm
from sklearn.datasets import make_blobs, make_circles, make_moons, make_classification
from sklearn.model_selection import train_test_split, GridSearchCV, cross_val_score
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline
from sklearn.metrics import classification_report, confusion_matrix

sns.set_theme(style="whitegrid", palette="muted", font_scale=1.1)
np.random.seed(42)

Introduction : intuition géométrique#

Considérons un problème de classification binaire en deux dimensions. Si les deux classes sont linéairement séparables, il existe une infinité d’hyperplans (ici des droites) qui les séparent. Le classifieur à marge maximale choisit celui qui maximise la distance entre l’hyperplan et les points les plus proches de chaque classe. Cette distance est appelée la marge.

Définition 112 (Hyperplan séparateur)

Soit \(\mathcal{X} \subseteq \mathbb{R}^d\) l’espace des features. Un hyperplan dans \(\mathbb{R}^d\) est l’ensemble

\[H = \{\mathbf{x} \in \mathbb{R}^d : \mathbf{w} \cdot \mathbf{x} + b = 0\}\]

où \(\mathbf{w} \in \mathbb{R}^d\) est le vecteur normal à l’hyperplan et \(b \in \mathbb{R}\) est le biais (ou intercept). L’hyperplan divise l’espace en deux demi-espaces : \(\mathbf{w} \cdot \mathbf{x} + b > 0\) et \(\mathbf{w} \cdot \mathbf{x} + b < 0\).

Définition 113 (Marge)

Soit un hyperplan séparateur défini par \((\mathbf{w}, b)\) et un jeu de données \(\{(\mathbf{x}_i, y_i)\}_{i=1}^n\) avec \(y_i \in \{-1, +1\}\). La marge fonctionnelle de l’observation \((\mathbf{x}_i, y_i)\) est

\[\hat{\gamma}_i = y_i (\mathbf{w} \cdot \mathbf{x}_i + b)\]

La marge géométrique est la distance euclidienne entre le point le plus proche et l’hyperplan :

\[\gamma = \min_{i=1,\ldots,n} \frac{y_i (\mathbf{w} \cdot \mathbf{x}_i + b)}{\|\mathbf{w}\|}\]

Hide code cell source

 
# Visualisation de l'intuition : plusieurs hyperplans séparateurs possibles
X, y = make_blobs(n_samples=80, centers=2, cluster_std=1.2, random_state=42)
y = 2 * y - 1  # convertir en {-1, +1}

fig, axes = plt.subplots(2, 1, figsize=(9, 9))

# Plusieurs hyperplans possibles
ax = axes[0]
ax.scatter(X[y == 1, 0], X[y == 1, 1], c='steelblue', edgecolors='k',
           linewidths=0.5, label='Classe +1', s=50)
ax.scatter(X[y == -1, 0], X[y == -1, 1], c='coral', edgecolors='k',
           linewidths=0.5, label='Classe -1', s=50)

xx = np.linspace(X[:, 0].min() - 1, X[:, 0].max() + 1, 100)
for slope, intercept, ls in [(-0.6, 3.5, '--'), (-0.4, 2.8, '-.'), (-0.8, 4.5, ':')]:
    ax.plot(xx, slope * xx + intercept, linestyle=ls, color='gray', alpha=0.7)
ax.set_title("Plusieurs hyperplans séparateurs possibles")
ax.legend(fontsize=9)
ax.set_xlabel("$x_1$")
ax.set_ylabel("$x_2$")

# SVM : hyperplan optimal avec marge
ax = axes[1]
clf = svm.SVC(kernel='linear', C=1000)
clf.fit(X, y)
w = clf.coef_[0]
b_svm = clf.intercept_[0]

xx_svm = np.linspace(X[:, 0].min() - 1, X[:, 0].max() + 1, 100)
yy_decision = -(w[0] * xx_svm + b_svm) / w[1]
yy_margin_plus = -(w[0] * xx_svm + b_svm - 1) / w[1]
yy_margin_minus = -(w[0] * xx_svm + b_svm + 1) / w[1]

ax.scatter(X[y == 1, 0], X[y == 1, 1], c='steelblue', edgecolors='k',
           linewidths=0.5, label='Classe +1', s=50)
ax.scatter(X[y == -1, 0], X[y == -1, 1], c='coral', edgecolors='k',
           linewidths=0.5, label='Classe -1', s=50)

ax.plot(xx_svm, yy_decision, 'k-', linewidth=2, label='Hyperplan')
ax.plot(xx_svm, yy_margin_plus, 'k--', linewidth=1, alpha=0.5)
ax.plot(xx_svm, yy_margin_minus, 'k--', linewidth=1, alpha=0.5)
ax.fill_between(xx_svm, yy_margin_minus, yy_margin_plus, alpha=0.1, color='gold')

# Mettre en évidence les vecteurs de support
sv = clf.support_vectors_
ax.scatter(sv[:, 0], sv[:, 1], s=150, facecolors='none',
           edgecolors='green', linewidths=2, label='Vecteurs de support')

ax.set_title("SVM : hyperplan à marge maximale")
ax.legend(fontsize=9)
ax.set_xlabel("$x_1$")
ax.set_ylabel("$x_2$")

plt.tight_layout()
plt.show()
_images/9574f7dee857b3b79b57775f582a4b69a76894b854bb1f94484d5777c223b289.png

Remarque 107

L’idée fondamentale des SVM est que l’hyperplan à marge maximale est celui qui généralise le mieux. Intuitivement, une marge large laisse plus de « place » pour les nouvelles observations, réduisant le risque de mauvaise classification. Cette intuition est formalisée par la théorie de Vapnik-Chervonenkis, qui montre que maximiser la marge revient à minimiser une borne sur l’erreur de généralisation.

SVM linéaire : formulation#

Problème d’optimisation (marge dure)#

Lorsque les données sont parfaitement séparables, on cherche l’hyperplan qui maximise la marge géométrique. On peut montrer que cela revient à résoudre le problème d’optimisation suivant.

Définition 114 (SVM à marge dure)

Étant donné un jeu d’entraînement \(\{(\mathbf{x}_i, y_i)\}_{i=1}^n\) avec \(y_i \in \{-1, +1\}\), le SVM à marge dure (hard margin SVM) résout le problème d’optimisation convexe :

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

sous les contraintes

\[y_i (\mathbf{w} \cdot \mathbf{x}_i + b) \geq 1, \quad i = 1, \ldots, n\]

La marge géométrique vaut \(\gamma = \frac{2}{\|\mathbf{w}\|}\), de sorte que minimiser \(\|\mathbf{w}\|^2\) revient à maximiser la marge.

Remarque 108

La contrainte \(y_i (\mathbf{w} \cdot \mathbf{x}_i + b) \geq 1\) impose que chaque point soit du bon côté de l’hyperplan, à une distance d’au moins \(\frac{1}{\|\mathbf{w}\|}\). Les points pour lesquels l’égalité est atteinte (\(y_i (\mathbf{w} \cdot \mathbf{x}_i + b) = 1\)) se trouvent exactement sur la frontière de la marge : ce sont les vecteurs de support. Ils sont les seuls points qui déterminent l’hyperplan optimal. Si l’on supprime un point qui n’est pas un vecteur de support, la solution ne change pas.

Problème dual et multiplicateurs de Lagrange#

Le problème d’optimisation se résout en pratique via sa formulation duale, obtenue par la méthode des multiplicateurs de Lagrange.

Proposition 27 (Formulation duale du SVM)

Le problème dual du SVM à marge dure est

\[\max_{\boldsymbol{\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)\]

sous les contraintes

\[\alpha_i \geq 0, \quad i = 1, \ldots, n \qquad \text{et} \qquad \sum_{i=1}^n \alpha_i y_i = 0\]

où les \(\alpha_i\) sont les multiplicateurs de Lagrange. À l’optimum, le vecteur de poids se reconstruit par

\[\mathbf{w}^* = \sum_{i=1}^n \alpha_i^* y_i \mathbf{x}_i\]

et les vecteurs de support sont les points pour lesquels \(\alpha_i^* > 0\).

Proof. On introduit les multiplicateurs de Lagrange \(\alpha_i \geq 0\) et on forme le lagrangien

\[\mathcal{L}(\mathbf{w}, b, \boldsymbol{\alpha}) = \frac{1}{2} \|\mathbf{w}\|^2 - \sum_{i=1}^n \alpha_i \left[ y_i (\mathbf{w} \cdot \mathbf{x}_i + b) - 1 \right]\]

Les conditions de stationnarité donnent

\[\frac{\partial \mathcal{L}}{\partial \mathbf{w}} = 0 \implies \mathbf{w} = \sum_{i=1}^n \alpha_i y_i \mathbf{x}_i\]
\[\frac{\partial \mathcal{L}}{\partial b} = 0 \implies \sum_{i=1}^n \alpha_i y_i = 0\]

En substituant ces expressions dans le lagrangien, on obtient le problème dual. Par les conditions KKT (Karush-Kuhn-Tucker), on a \(\alpha_i [y_i (\mathbf{w} \cdot \mathbf{x}_i + b) - 1] = 0\) pour tout \(i\) : si \(\alpha_i > 0\), alors la contrainte est active, c’est-à-dire que \(\mathbf{x}_i\) est un vecteur de support.

Remarque 109

La formulation duale est cruciale pour deux raisons. Premièrement, le nombre de variables d’optimisation est \(n\) (le nombre d’observations) plutôt que \(d\) (la dimension), ce qui est avantageux lorsque \(d \gg n\). Deuxièmement, les données n’apparaissent qu’à travers des produits scalaires \(\mathbf{x}_i \cdot \mathbf{x}_j\), ce qui ouvre la porte à l’astuce du noyau.

Marge souple (soft margin)#

En pratique, les données sont rarement parfaitement séparables. De plus, même si elles le sont, la marge dure est très sensible aux outliers : un seul point mal placé peut modifier considérablement l’hyperplan. La marge souple introduit des variables de relâchement (slack variables) qui autorisent certains points à violer la marge, moyennant une pénalité.

Définition 115 (SVM à marge souple)

Le SVM à marge souple (soft margin SVM) résout le problème

\[\min_{\mathbf{w}, b, \boldsymbol{\xi}} \frac{1}{2} \|\mathbf{w}\|^2 + C \sum_{i=1}^n \xi_i\]

sous les contraintes

\[y_i (\mathbf{w} \cdot \mathbf{x}_i + b) \geq 1 - \xi_i, \quad \xi_i \geq 0, \quad i = 1, \ldots, n\]

où \(\xi_i\) est la variable de relâchement (slack variable) associée à l’observation \(i\), et \(C > 0\) est l”hyperparamètre de régularisation qui contrôle le compromis entre la largeur de la marge et le nombre de violations autorisées.

Remarque 110

L’interprétation des variables de relâchement est la suivante :

  • \(\xi_i = 0\) : le point est correctement classé et se trouve à l’extérieur de la marge ou exactement sur sa frontière.

  • \(0 < \xi_i < 1\) : le point est correctement classé mais se trouve à l’intérieur de la marge.

  • \(\xi_i = 1\) : le point se trouve exactement sur l’hyperplan de décision.

  • \(\xi_i > 1\) : le point est mal classé.

Le paramètre \(C\) joue un rôle analogue à l’inverse du paramètre de régularisation :

  • \(C\) grand : on tolère peu de violations, la marge est étroite et le modèle est plus susceptible d’overfitting.

  • \(C\) petit : on tolère davantage de violations, la marge est large et le modèle est plus régularisé.

Hide code cell source

 
# Effet du paramètre C sur la marge
X_c, y_c = make_blobs(n_samples=100, centers=2, cluster_std=1.8, random_state=6)
y_c = 2 * y_c - 1

fig, axes = plt.subplots(3, 1, figsize=(9, 12))

for ax, C_val in zip(axes, [0.01, 1, 100]):
    clf_c = svm.SVC(kernel='linear', C=C_val)
    clf_c.fit(X_c, y_c)

    w_c = clf_c.coef_[0]
    b_c = clf_c.intercept_[0]

    xx_c = np.linspace(X_c[:, 0].min() - 1, X_c[:, 0].max() + 1, 200)
    yy_dec = -(w_c[0] * xx_c + b_c) / w_c[1]
    yy_mp = -(w_c[0] * xx_c + b_c - 1) / w_c[1]
    yy_mm = -(w_c[0] * xx_c + b_c + 1) / w_c[1]

    ax.scatter(X_c[y_c == 1, 0], X_c[y_c == 1, 1], c='steelblue',
               edgecolors='k', linewidths=0.5, s=40)
    ax.scatter(X_c[y_c == -1, 0], X_c[y_c == -1, 1], c='coral',
               edgecolors='k', linewidths=0.5, s=40)
    ax.plot(xx_c, yy_dec, 'k-', linewidth=1.5)
    ax.plot(xx_c, yy_mp, 'k--', linewidth=0.8, alpha=0.5)
    ax.plot(xx_c, yy_mm, 'k--', linewidth=0.8, alpha=0.5)
    ax.fill_between(xx_c, yy_mm, yy_mp, alpha=0.08, color='gold')

    sv_c = clf_c.support_vectors_
    ax.scatter(sv_c[:, 0], sv_c[:, 1], s=120, facecolors='none',
               edgecolors='green', linewidths=1.5)

    ylim = (X_c[:, 1].min() - 2, X_c[:, 1].max() + 2)
    ax.set_ylim(ylim)
    ax.set_title(f"$C = {C_val}$ — {len(sv_c)} vecteurs de support")
    ax.set_xlabel("$x_1$")
    ax.set_ylabel("$x_2$")

plt.tight_layout()
plt.show()
_images/ee4519a0ed95f70d1c4457fc2c0dcabaada53a906426d8341681cad9687cbcba.png

Proposition 28 (Formulation duale du SVM à marge souple)

Le problème dual du SVM à marge souple est

\[\max_{\boldsymbol{\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)\]

sous les contraintes

\[0 \leq \alpha_i \leq C, \quad i = 1, \ldots, n \qquad \text{et} \qquad \sum_{i=1}^n \alpha_i y_i = 0\]

La seule différence avec le cas à marge dure est la borne supérieure \(\alpha_i \leq C\), qui empêche un seul point d’avoir un poids arbitrairement élevé.

Astuce du noyau (kernel trick)#

Les SVM linéaires ne peuvent modéliser que des frontières de décision linéaires. Pour traiter des problèmes non linéairement séparables, on peut transformer les données dans un espace de dimension supérieure où elles deviennent séparables. L”astuce du noyau permet de réaliser cette transformation de manière implicite, sans jamais calculer les coordonnées dans l’espace transformé.

Définition 116 (Fonction noyau)

Une fonction noyau (kernel function) est une fonction \(K : \mathbb{R}^d \times \mathbb{R}^d \to \mathbb{R}\) telle qu’il existe un espace de Hilbert \(\mathcal{H}\) et une application \(\phi : \mathbb{R}^d \to \mathcal{H}\) vérifiant

\[K(\mathbf{x}, \mathbf{x}') = \langle \phi(\mathbf{x}), \phi(\mathbf{x}') \rangle_{\mathcal{H}}\]

pour tout \(\mathbf{x}, \mathbf{x}' \in \mathbb{R}^d\). On dit que \(K\) est un noyau défini positif si la matrice de Gram \(\mathbf{G}\) définie par \(G_{ij} = K(\mathbf{x}_i, \mathbf{x}_j)\) est semi-définie positive pour tout ensemble fini de points \(\{\mathbf{x}_1, \ldots, \mathbf{x}_n\}\).

Proposition 29 (Théorème de Mercer (version simplifiée))

Une fonction symétrique \(K : \mathbb{R}^d \times \mathbb{R}^d \to \mathbb{R}\) est un noyau valide (c’est-à-dire qu’il existe un espace \(\mathcal{H}\) et une application \(\phi\) tels que \(K(\mathbf{x}, \mathbf{x}') = \langle \phi(\mathbf{x}), \phi(\mathbf{x}') \rangle\)) si et seulement si la matrice de Gram \(\mathbf{G}\) associée est semi-définie positive pour tout choix fini de points.

Ce résultat est fondamental car il garantit que l’on peut remplacer tout produit scalaire \(\mathbf{x}_i \cdot \mathbf{x}_j\) dans la formulation duale par \(K(\mathbf{x}_i, \mathbf{x}_j)\), sans avoir à expliciter \(\phi\).

Remarque 111

L’astuce du noyau est d’une puissance remarquable. Considérons par exemple un noyau gaussien : la transformation \(\phi\) correspondante envoie les données dans un espace de dimension infinie. Le calcul explicite de \(\phi(\mathbf{x})\) serait impossible, mais le calcul du noyau \(K(\mathbf{x}, \mathbf{x}')\) ne coûte que \(O(d)\). La formulation duale du SVM ne fait intervenir que des produits scalaires, que l’on remplace directement par les évaluations du noyau.

Exemple 10

Considérons le noyau polynomial de degré 2 en dimension 2 : \(K(\mathbf{x}, \mathbf{x}') = (\mathbf{x} \cdot \mathbf{x}')^2\). Si \(\mathbf{x} = (x_1, x_2)\) et \(\mathbf{x}' = (x_1', x_2')\), alors

\[K(\mathbf{x}, \mathbf{x}') = (x_1 x_1' + x_2 x_2')^2 = x_1^2 {x_1'}^2 + 2 x_1 x_2 x_1' x_2' + x_2^2 {x_2'}^2\]

Ce qui correspond au produit scalaire dans l’espace de dimension 3 avec la transformation \(\phi(\mathbf{x}) = (x_1^2, \sqrt{2} x_1 x_2, x_2^2)\). Le noyau calcule implicitement ce produit scalaire sans construire \(\phi(\mathbf{x})\).

Hide code cell source

 
# Illustration : données non linéairement séparables rendues séparables
# par une transformation vers un espace de dimension supérieure

X_nl, y_nl = make_circles(n_samples=200, noise=0.1, factor=0.4, random_state=42)

fig, axes = plt.subplots(3, 1, figsize=(9, 12))

# Espace original
ax = axes[0]
ax.scatter(X_nl[y_nl == 0, 0], X_nl[y_nl == 0, 1], c='coral',
           edgecolors='k', linewidths=0.5, s=40, label='Classe 0')
ax.scatter(X_nl[y_nl == 1, 0], X_nl[y_nl == 1, 1], c='steelblue',
           edgecolors='k', linewidths=0.5, s=40, label='Classe 1')
ax.set_title("Espace original (non séparable)")
ax.set_xlabel("$x_1$")
ax.set_ylabel("$x_2$")
ax.legend(fontsize=9)
ax.set_aspect('equal')

# Transformation phi : ajout de x1^2 + x2^2
r = X_nl[:, 0]**2 + X_nl[:, 1]**2
ax = axes[1]
ax3d_data_0 = X_nl[y_nl == 0]
ax3d_data_1 = X_nl[y_nl == 1]
ax.scatter(X_nl[y_nl == 0, 0], r[y_nl == 0], c='coral',
           edgecolors='k', linewidths=0.5, s=40, label='Classe 0')
ax.scatter(X_nl[y_nl == 1, 0], r[y_nl == 1], c='steelblue',
           edgecolors='k', linewidths=0.5, s=40, label='Classe 1')
ax.axhline(y=0.35, color='k', linestyle='--', linewidth=1.5)
ax.set_title(r"Espace transformé $\phi(\mathbf{x}) = (x_1, \|\mathbf{x}\|^2)$")
ax.set_xlabel("$x_1$")
ax.set_ylabel(r"$\|\mathbf{x}\|^2$")
ax.legend(fontsize=9)

# SVM avec noyau RBF dans l'espace original
ax = axes[2]
clf_rbf = svm.SVC(kernel='rbf', C=10, gamma=2)
clf_rbf.fit(X_nl, y_nl)

xx_nl, yy_nl = np.meshgrid(np.linspace(-1.5, 1.5, 300),
                             np.linspace(-1.5, 1.5, 300))
Z_nl = clf_rbf.decision_function(np.c_[xx_nl.ravel(), yy_nl.ravel()])
Z_nl = Z_nl.reshape(xx_nl.shape)

ax.contourf(xx_nl, yy_nl, Z_nl, levels=np.linspace(Z_nl.min(), Z_nl.max(), 20),
            cmap='RdBu', alpha=0.4)
ax.contour(xx_nl, yy_nl, Z_nl, levels=[0], colors='k', linewidths=2)
ax.contour(xx_nl, yy_nl, Z_nl, levels=[-1, 1], colors='k',
           linewidths=1, linestyles='dashed')
ax.scatter(X_nl[y_nl == 0, 0], X_nl[y_nl == 0, 1], c='coral',
           edgecolors='k', linewidths=0.5, s=40)
ax.scatter(X_nl[y_nl == 1, 0], X_nl[y_nl == 1, 1], c='steelblue',
           edgecolors='k', linewidths=0.5, s=40)
ax.set_title("SVM avec noyau RBF")
ax.set_xlabel("$x_1$")
ax.set_ylabel("$x_2$")
ax.set_aspect('equal')

plt.tight_layout()
plt.show()
_images/b1522110f463a3df6e89c5ab86fa5aff5ac026fd8f3c5e8a88a4a6902ab862b8.png

Noyaux classiques#

Plusieurs noyaux sont couramment utilisés en pratique. Le choix du noyau dépend de la nature des données et de la complexité de la frontière de décision recherchée.

Définition 117 (Noyau linéaire)

Le noyau linéaire est simplement le produit scalaire standard :

\[K(\mathbf{x}, \mathbf{x}') = \mathbf{x} \cdot \mathbf{x}' = \sum_{j=1}^d x_j x_j'\]

Il correspond à \(\phi(\mathbf{x}) = \mathbf{x}\) (pas de transformation). Le SVM avec noyau linéaire est équivalent au SVM linéaire classique.

Définition 118 (Noyau polynomial)

Le noyau polynomial de degré \(p\) est défini par

\[K(\mathbf{x}, \mathbf{x}') = (\gamma \, \mathbf{x} \cdot \mathbf{x}' + r)^p\]

où \(p \in \mathbb{N}^*\) est le degré, \(\gamma > 0\) un facteur d’échelle et \(r \geq 0\) le terme constant (coef0). La transformation implicite \(\phi\) envoie les données dans un espace contenant tous les monômes de degré \(\leq p\), de dimension \(\binom{d + p}{p}\).

Définition 119 (Noyau RBF (gaussien))

Le noyau RBF (Radial Basis Function), ou noyau gaussien, est défini par

\[K(\mathbf{x}, \mathbf{x}') = \exp\left(-\gamma \|\mathbf{x} - \mathbf{x}'\|^2\right) = \exp\left(-\frac{\|\mathbf{x} - \mathbf{x}'\|^2}{2\sigma^2}\right)\]

où \(\gamma = \frac{1}{2\sigma^2}\) contrôle la « portée » du noyau. La transformation implicite \(\phi\) envoie les données dans un espace de Hilbert de dimension infinie. Plus \(\gamma\) est grand (ou \(\sigma\) petit), plus le noyau est localisé et la frontière de décision est complexe.

Remarque 112

Le noyau RBF est le choix par défaut dans Scikit-learn et souvent le plus performant en pratique. Il peut approximer n’importe quelle frontière de décision continue avec suffisamment de données. Cependant, il possède deux hyperparamètres sensibles : \(C\) et \(\gamma\). Un \(\gamma\) trop grand conduit à de l’overfitting (chaque point d’entraînement forme son propre « îlot »), tandis qu’un \(\gamma\) trop petit rend le modèle quasi-linéaire.

Définition 120 (Noyau sigmoïde)

Le noyau sigmoïde est défini par

\[K(\mathbf{x}, \mathbf{x}') = \tanh(\gamma \, \mathbf{x} \cdot \mathbf{x}' + r)\]

Il est lié aux réseaux de neurones (la tangente hyperbolique étant une fonction d’activation classique). Ce noyau n’est pas défini positif pour toutes les valeurs de \(\gamma\) et \(r\), il est donc à utiliser avec précaution.

Hide code cell source

 
# Comparaison des noyaux sur un jeu de données non linéaire
X_moons, y_moons = make_moons(n_samples=200, noise=0.2, random_state=42)

kernels = [
    ('Linéaire', 'linear', {}),
    ('Polynomial (d=3)', 'poly', {'degree': 3, 'coef0': 1}),
    ('RBF', 'rbf', {'gamma': 2}),
    ('Sigmoïde', 'sigmoid', {'gamma': 0.5, 'coef0': 0}),
]

fig, axes = plt.subplots(4, 1, figsize=(8, 14))

for ax, (name, kern, params) in zip(axes, kernels):
    clf_k = svm.SVC(kernel=kern, C=10, **params)
    clf_k.fit(X_moons, y_moons)

    xx_k, yy_k = np.meshgrid(np.linspace(X_moons[:, 0].min() - 0.5,
                                           X_moons[:, 0].max() + 0.5, 300),
                               np.linspace(X_moons[:, 1].min() - 0.5,
                                           X_moons[:, 1].max() + 0.5, 300))
    Z_k = clf_k.decision_function(np.c_[xx_k.ravel(), yy_k.ravel()])
    Z_k = Z_k.reshape(xx_k.shape)

    ax.contourf(xx_k, yy_k, Z_k, levels=20, cmap='RdBu', alpha=0.4)
    ax.contour(xx_k, yy_k, Z_k, levels=[0], colors='k', linewidths=2)

    ax.scatter(X_moons[y_moons == 0, 0], X_moons[y_moons == 0, 1],
               c='coral', edgecolors='k', linewidths=0.5, s=30)
    ax.scatter(X_moons[y_moons == 1, 0], X_moons[y_moons == 1, 1],
               c='steelblue', edgecolors='k', linewidths=0.5, s=30)

    score_k = clf_k.score(X_moons, y_moons)
    ax.set_title(f"{name}\nAccuracy : {score_k:.2f}")
    ax.set_xlabel("$x_1$")
    ax.set_ylabel("$x_2$")

plt.tight_layout()
plt.show()
_images/0688119c4cbd839ccf71ee62d40409e32446a4aed21a7f62aa368151d27c0a17.png

Proposition 30 (Choix du noyau)

Noyau

Formule

Quand l’utiliser

Linéaire

\(K(\mathbf{x}, \mathbf{x}') = \mathbf{x} \cdot \mathbf{x}'\)

Données de grande dimension (\(d \gg n\)), texte, problèmes linéairement séparables

Polynomial

\(K(\mathbf{x}, \mathbf{x}') = (\gamma \mathbf{x} \cdot \mathbf{x}' + r)^p\)

Interactions entre features connues, NLP

RBF

\(K(\mathbf{x}, \mathbf{x}') = \exp(-\gamma |\mathbf{x} - \mathbf{x}'|^2)\)

Choix par défaut, non-linéarité modérée à forte

Sigmoïde

\(K(\mathbf{x}, \mathbf{x}') = \tanh(\gamma \mathbf{x} \cdot \mathbf{x}' + r)\)

Rarement utilisé, analogie réseau de neurones

Effet de \(\gamma\) sur le noyau RBF#

Hide code cell source

 
# Visualisation de l'effet de gamma sur la frontière de décision
X_g, y_g = make_moons(n_samples=150, noise=0.25, random_state=42)

fig, axes = plt.subplots(4, 1, figsize=(8, 14))
gammas = [0.1, 1, 10, 100]

for ax, g in zip(axes, gammas):
    clf_g = svm.SVC(kernel='rbf', C=10, gamma=g)
    clf_g.fit(X_g, y_g)

    xx_g, yy_g = np.meshgrid(np.linspace(-1.5, 2.5, 300),
                               np.linspace(-1.2, 1.8, 300))
    Z_g = clf_g.decision_function(np.c_[xx_g.ravel(), yy_g.ravel()])
    Z_g = Z_g.reshape(xx_g.shape)

    ax.contourf(xx_g, yy_g, Z_g, levels=20, cmap='RdBu', alpha=0.4)
    ax.contour(xx_g, yy_g, Z_g, levels=[0], colors='k', linewidths=2)
    ax.scatter(X_g[y_g == 0, 0], X_g[y_g == 0, 1], c='coral',
               edgecolors='k', linewidths=0.5, s=30)
    ax.scatter(X_g[y_g == 1, 0], X_g[y_g == 1, 1], c='steelblue',
               edgecolors='k', linewidths=0.5, s=30)

    n_sv = clf_g.n_support_.sum()
    ax.set_title(f"$\\gamma = {g}$ — {n_sv} SV")
    ax.set_xlabel("$x_1$")
    ax.set_ylabel("$x_2$")

plt.suptitle("Effet de $\\gamma$ sur la frontière de décision (noyau RBF, $C = 10$)",
             fontsize=13, y=1.02)
plt.tight_layout()
plt.show()
_images/42ab305e8bad62ec37fc541e64f6c521043f5a8ced7d5c5b3a47cb13a4accb40.png

Remarque 113

On observe clairement le compromis biais-variance en fonction de \(\gamma\) :

  • \(\gamma = 0.1\) : frontière très lisse, proche d’un hyperplan linéaire (sous-apprentissage).

  • \(\gamma = 1\) : bon compromis, la frontière épouse la forme des données.

  • \(\gamma = 10\) : la frontière devient plus irrégulière.

  • \(\gamma = 100\) : chaque point d’entraînement forme presque son propre îlot, signe clair de surapprentissage.

SVM pour la régression (SVR)#

Les SVM peuvent être adaptés à la régression. Au lieu de maximiser la marge entre deux classes, le SVR (Support Vector Regression) cherche une fonction qui approche les données avec une tolérance \(\varepsilon\) : les erreurs inférieures à \(\varepsilon\) ne sont pas pénalisées.

Définition 121 (Régression à vecteurs de support (\(\varepsilon\)-SVR))

Soit un jeu d’entraînement \(\{(\mathbf{x}_i, y_i)\}_{i=1}^n\) avec \(y_i \in \mathbb{R}\). Le \(\varepsilon\)-SVR résout le problème d’optimisation

\[\min_{\mathbf{w}, b, \boldsymbol{\xi}, \boldsymbol{\xi}^*} \frac{1}{2} \|\mathbf{w}\|^2 + C \sum_{i=1}^n (\xi_i + \xi_i^*)\]

sous les contraintes

\[y_i - (\mathbf{w} \cdot \mathbf{x}_i + b) \leq \varepsilon + \xi_i\]
\[(\mathbf{w} \cdot \mathbf{x}_i + b) - y_i \leq \varepsilon + \xi_i^*\]
\[\xi_i, \xi_i^* \geq 0, \quad i = 1, \ldots, n\]

Le paramètre \(\varepsilon > 0\) définit un tube autour de la fonction de régression : les points situés à l’intérieur du tube ne contribuent pas à la perte. Les variables \(\xi_i\) et \(\xi_i^*\) mesurent les violations au-dessus et en dessous du tube, respectivement.

Définition 122 (Perte \(\varepsilon\)-insensible)

La perte \(\varepsilon\)-insensible (\(\varepsilon\)-insensitive loss) est définie par

\[\begin{split}L_\varepsilon(y, f(\mathbf{x})) = \max(0, |y - f(\mathbf{x})| - \varepsilon) = \begin{cases} 0 & \text{si } |y - f(\mathbf{x})| \leq \varepsilon \\ |y - f(\mathbf{x})| - \varepsilon & \text{sinon} \end{cases}\end{split}\]

Contrairement à la perte quadratique, cette fonction est exactement nulle lorsque l’erreur est inférieure à \(\varepsilon\), ce qui conduit à une solution parcimonieuse (seuls les points hors du tube sont des vecteurs de support).

Hide code cell source

 
# Illustration de la perte epsilon-insensible
fig, axes = plt.subplots(2, 1, figsize=(9, 8))

# Perte epsilon-insensible
ax = axes[0]
residuals = np.linspace(-3, 3, 500)
epsilon = 0.5
loss_eps = np.maximum(0, np.abs(residuals) - epsilon)
loss_quad = residuals**2

ax.plot(residuals, loss_eps, 'steelblue', linewidth=2,
        label=f'$\\varepsilon$-insensible ($\\varepsilon = {epsilon}$)')
ax.plot(residuals, loss_quad, 'coral', linewidth=2, linestyle='--',
        label='Perte quadratique')
ax.axvline(-epsilon, color='gray', linestyle=':', alpha=0.5)
ax.axvline(epsilon, color='gray', linestyle=':', alpha=0.5)
ax.fill_betweenx([0, 5], -epsilon, epsilon, alpha=0.1, color='gold',
                  label=f'Zone de tolérance $\\pm \\varepsilon$')
ax.set_xlabel("Résidu $y - f(\\mathbf{x})$")
ax.set_ylabel("Perte")
ax.set_title("Comparaison des fonctions de perte")
ax.legend(fontsize=9)
ax.set_ylim(-0.2, 5)
ax.grid(True, alpha=0.3)

# Illustration du tube epsilon
ax = axes[1]
np.random.seed(42)
X_svr = np.sort(np.random.uniform(0, 5, 50))
y_svr = np.sin(X_svr) + np.random.normal(0, 0.2, 50)

from sklearn.svm import SVR
svr_model = SVR(kernel='rbf', C=10, epsilon=0.3, gamma=0.5)
svr_model.fit(X_svr.reshape(-1, 1), y_svr)

X_plot = np.linspace(0, 5, 300).reshape(-1, 1)
y_pred_svr = svr_model.predict(X_plot)

ax.scatter(X_svr, y_svr, c='steelblue', edgecolors='k', linewidths=0.5,
           s=40, zorder=3, label='Données')
ax.plot(X_plot, y_pred_svr, 'k-', linewidth=2, label='SVR')
ax.fill_between(X_plot.ravel(), y_pred_svr - 0.3, y_pred_svr + 0.3,
                alpha=0.15, color='gold', label=f'$\\varepsilon$-tube ($\\varepsilon = 0.3$)')

# Vecteurs de support
sv_indices = svr_model.support_
ax.scatter(X_svr[sv_indices], y_svr[sv_indices], s=100, facecolors='none',
           edgecolors='green', linewidths=1.5, zorder=4,
           label=f'{len(sv_indices)} vecteurs de support')

ax.set_xlabel("$x$")
ax.set_ylabel("$y$")
ax.set_title("SVR avec $\\varepsilon$-tube")
ax.legend(fontsize=9)
ax.grid(True, alpha=0.3)

plt.tight_layout()
plt.show()
_images/a3a5dcc15c947f7cde947879d984ff8281d2780b5ab70c1f51adaac485287fdd.png

Remarque 114

Les hyperparamètres du SVR sont :

  • \(C\) : contrôle le compromis entre la platitude de la fonction (\(\|\mathbf{w}\|\) petit) et la tolérance aux erreurs hors du tube. Un \(C\) grand pénalise davantage les violations.

  • \(\varepsilon\) : la largeur du tube. Un \(\varepsilon\) grand ignore plus d’erreurs (modèle plus lisse, moins de vecteurs de support). Un \(\varepsilon\) petit force le modèle à passer plus près de chaque point.

  • \(\gamma\) (pour le noyau RBF) : contrôle la complexité de la fonction, comme en classification.

Exemple complet avec Scikit-learn#

Mettons en pratique l’ensemble des concepts sur un problème de classification plus réaliste.

Génération des données et prétraitement#

Hide code cell source

 
# Génération d'un jeu de données de classification non linéaire
X_full, y_full = make_classification(
    n_samples=500, n_features=2, n_redundant=0, n_informative=2,
    n_clusters_per_class=2, flip_y=0.1, random_state=42
)

X_train, X_test, y_train, y_test = train_test_split(
    X_full, y_full, test_size=0.3, random_state=42, stratify=y_full
)

scaler = StandardScaler()
X_train_sc = scaler.fit_transform(X_train)
X_test_sc = scaler.transform(X_test)

print(f"Entraînement : {X_train_sc.shape[0]} observations")
print(f"Test : {X_test_sc.shape[0]} observations")
print(f"Répartition des classes (train) : {np.bincount(y_train)}")

Entraînement : 350 observations
Test : 150 observations
Répartition des classes (train) : [172 178]

Comparaison des noyaux#

Hide code cell source

 
# Fonction utilitaire pour tracer la frontière de décision
def plot_decision_boundary(clf, X, y, ax, title=""):
    h = 0.05
    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.arange(x_min, x_max, h),
                          np.arange(y_min, y_max, h))

    Z = clf.decision_function(np.c_[xx.ravel(), yy.ravel()])
    Z = Z.reshape(xx.shape)

    ax.contourf(xx, yy, Z, levels=20, cmap='RdBu', alpha=0.4)
    ax.contour(xx, yy, Z, levels=[0], colors='k', linewidths=2)
    ax.contour(xx, yy, Z, levels=[-1, 1], colors='k',
               linewidths=1, linestyles='dashed')

    ax.scatter(X[y == 0, 0], X[y == 0, 1], c='coral',
               edgecolors='k', linewidths=0.5, s=25, alpha=0.8)
    ax.scatter(X[y == 1, 0], X[y == 1, 1], c='steelblue',
               edgecolors='k', linewidths=0.5, s=25, alpha=0.8)

    if hasattr(clf, 'support_vectors_'):
        sv = clf.support_vectors_
        ax.scatter(sv[:, 0], sv[:, 1], s=80, facecolors='none',
                   edgecolors='lime', linewidths=1.2)

    ax.set_xlabel("$x_1$")
    ax.set_ylabel("$x_2$")
    ax.set_title(title)

Hide code cell source

 
# Entraîner et comparer quatre noyaux
models = {
    'Linéaire': svm.SVC(kernel='linear', C=1),
    'Polynomial (d=3)': svm.SVC(kernel='poly', degree=3, coef0=1, C=1),
    'RBF': svm.SVC(kernel='rbf', gamma='scale', C=1),
    'RBF ($C=100$)': svm.SVC(kernel='rbf', gamma='scale', C=100),
}

fig, axes = plt.subplots(4, 1, figsize=(8, 16))

for ax, (name, model) in zip(axes, models.items()):
    model.fit(X_train_sc, y_train)
    score_train = model.score(X_train_sc, y_train)
    score_test = model.score(X_test_sc, y_test)
    n_sv = model.n_support_.sum()

    plot_decision_boundary(model, X_train_sc, y_train, ax,
                           title=f"{name}\nTrain: {score_train:.2f} | "
                                 f"Test: {score_test:.2f} | SV: {n_sv}")

plt.tight_layout()
plt.show()
_images/23f1fb9e94baeedb874014eed4d1a0032d2a446dcb596fbdc76a93a8073123dc.png

Recherche des hyperparamètres par validation croisée#

Hide code cell source

 
# GridSearchCV pour optimiser C et gamma du noyau RBF
pipe = Pipeline([
    ('scaler', StandardScaler()),
    ('svc', svm.SVC(kernel='rbf'))
])

param_grid = {
    'svc__C': [0.1, 1, 10, 100],
    'svc__gamma': ['scale', 'auto', 0.01, 0.1, 1, 10],
}

grid = GridSearchCV(pipe, param_grid, cv=5, scoring='accuracy',
                    return_train_score=True, n_jobs=-1)
grid.fit(X_train, y_train)

print(f"Meilleurs hyperparamètres : {grid.best_params_}")
print(f"Meilleur score CV : {grid.best_score_:.4f}")
print(f"Score sur le test : {grid.score(X_test, y_test):.4f}")

Meilleurs hyperparamètres : {'svc__C': 1, 'svc__gamma': 10}
Meilleur score CV : 0.9086
Score sur le test : 0.8933

Hide code cell source

 
# Visualisation de la heatmap des scores de validation croisée
import pandas as pd

results = pd.DataFrame(grid.cv_results_)
# Filtrer uniquement les gamma numériques pour la heatmap
mask = results['param_svc__gamma'].apply(lambda x: isinstance(x, (int, float)))
results_num = results[mask].copy()

pivot = results_num.pivot_table(
    values='mean_test_score',
    index='param_svc__gamma',
    columns='param_svc__C'
)

fig, ax = plt.subplots(figsize=(8, 5))
sns.heatmap(pivot, annot=True, fmt='.3f', cmap='YlOrRd', ax=ax)
ax.set_xlabel('$C$')
ax.set_ylabel('$\\gamma$')
ax.set_title('Accuracy moyenne (validation croisée) — SVM RBF')
plt.tight_layout()
plt.show()
_images/c2468635d74f875bd8b2800a0a07dcea4fe10f5d001a5e028a9867c0f9073baf.png

Évaluation du meilleur modèle#

Hide code cell source

 
# Rapport de classification et matrice de confusion
best_model = grid.best_estimator_
y_pred_best = best_model.predict(X_test)

print("Rapport de classification :")
print(classification_report(y_test, y_pred_best))

Rapport de classification :
              precision    recall  f1-score   support

           0       0.93      0.85      0.89        74
           1       0.87      0.93      0.90        76

    accuracy                           0.89       150
   macro avg       0.90      0.89      0.89       150
weighted avg       0.90      0.89      0.89       150

Hide code cell source

 
# Matrice de confusion
cm = confusion_matrix(y_test, y_pred_best)

fig, axes = plt.subplots(2, 1, figsize=(9, 9))

# Matrice de confusion
ax = axes[0]
sns.heatmap(cm, annot=True, fmt='d', cmap='Blues', ax=ax,
            xticklabels=['Classe 0', 'Classe 1'],
            yticklabels=['Classe 0', 'Classe 1'])
ax.set_xlabel('Prédiction')
ax.set_ylabel('Vrai label')
ax.set_title('Matrice de confusion')

# Frontière de décision du meilleur modèle
ax = axes[1]
X_test_sc_best = best_model.named_steps['scaler'].transform(X_test)
svc_best = best_model.named_steps['svc']
plot_decision_boundary(svc_best, X_test_sc_best, y_test, ax,
                       title=f"Meilleur SVM sur le test set\n"
                             f"Accuracy : {grid.score(X_test, y_test):.2f}")

plt.tight_layout()
plt.show()
_images/0497d9017a97bb696436041a7c24e49b3c49685b63f10d40bc3de160dbc82b50.png

SVM et données multi-classes#

Remarque 115

Le SVM est nativement un classifieur binaire. Pour traiter les problèmes multi-classes, Scikit-learn utilise par défaut la stratégie un-contre-un (one-vs-one, OVO) : pour \(k\) classes, on entraîne \(\binom{k}{2}\) classifieurs binaires, chacun distinguant une paire de classes. La prédiction finale est obtenue par vote majoritaire. L’alternative un-contre-tous (one-vs-rest, OVR) entraîne \(k\) classifieurs, chacun distinguant une classe de toutes les autres.

Hide code cell source

 
# Exemple multi-classes avec le jeu Iris
from sklearn.datasets import load_iris

iris = load_iris()
X_iris, y_iris = iris.data[:, :2], iris.target  # 2 premières features pour la visualisation

pipe_iris = Pipeline([
    ('scaler', StandardScaler()),
    ('svc', svm.SVC(kernel='rbf', C=10, gamma='scale'))
])

scores_iris = cross_val_score(pipe_iris, X_iris, y_iris, cv=5, scoring='accuracy')
print(f"Iris (2 features) — Accuracy CV : {scores_iris.mean():.3f} (+/- {scores_iris.std():.3f})")

# Visualisation de la frontière de décision multi-classes
pipe_iris.fit(X_iris, y_iris)
scaler_iris = pipe_iris.named_steps['scaler']
svc_iris = pipe_iris.named_steps['svc']
X_iris_sc = scaler_iris.transform(X_iris)

h = 0.05
x_min, x_max = X_iris_sc[:, 0].min() - 1, X_iris_sc[:, 0].max() + 1
y_min, y_max = X_iris_sc[:, 1].min() - 1, X_iris_sc[:, 1].max() + 1
xx_iris, yy_iris = np.meshgrid(np.arange(x_min, x_max, h),
                                np.arange(y_min, y_max, h))
Z_iris = svc_iris.predict(np.c_[xx_iris.ravel(), yy_iris.ravel()])
Z_iris = Z_iris.reshape(xx_iris.shape)

fig, ax = plt.subplots(figsize=(8, 6))
ax.contourf(xx_iris, yy_iris, Z_iris, alpha=0.3, cmap='Set2')
ax.contour(xx_iris, yy_iris, Z_iris, colors='k', linewidths=0.5)

colors_iris = ['coral', 'steelblue', 'seagreen']
for i, name in enumerate(iris.target_names):
    ax.scatter(X_iris_sc[y_iris == i, 0], X_iris_sc[y_iris == i, 1],
               c=colors_iris[i], edgecolors='k', linewidths=0.5,
               s=50, label=name)

ax.set_xlabel(f"{iris.feature_names[0]} (standardisé)")
ax.set_ylabel(f"{iris.feature_names[1]} (standardisé)")
ax.set_title(f"SVM multi-classes sur Iris (2 features)\n"
             f"Accuracy CV : {scores_iris.mean():.3f}")
ax.legend()
plt.tight_layout()
plt.show()

Iris (2 features) — Accuracy CV : 0.800 (+/- 0.060)
_images/0c15991e66256c182347beab8ea9bd48edd12867a898ca9532718ad537fa83c5.png

Résumé#

Les machines à vecteurs de support sont un outil puissant et théoriquement fondé pour la classification et la régression. Voici les points clés à retenir :

Concept

Description

Marge maximale

Le SVM cherche l’hyperplan qui maximise la distance aux points les plus proches (vecteurs de support)

Marge souple

Les variables de relâchement \(\xi_i\) et le paramètre \(C\) permettent de tolérer des erreurs de classification

Astuce du noyau

Remplacer le produit scalaire par une fonction noyau \(K(\mathbf{x}, \mathbf{x}')\) permet de modéliser des frontières non linéaires

Noyau RBF

\(K(\mathbf{x}, \mathbf{x}') = \exp(-\gamma |\mathbf{x} - \mathbf{x}'|^2)\) : choix par défaut, très flexible

SVR

La perte \(\varepsilon\)-insensible et le tube \(\varepsilon\) étendent les SVM à la régression

Hyperparamètres

\(C\) (régularisation), \(\gamma\) (portée du noyau), \(\varepsilon\) (tolérance SVR) : à optimiser par validation croisée

Proposition 31 (Avantages et limites des SVM)

Avantages :

  • Fondements théoriques solides (théorie de Vapnik-Chervonenkis, bornes de généralisation)

  • Efficaces en grande dimension (\(d \gg n\)), notamment avec le noyau linéaire

  • Robustes aux outliers grâce à la marge souple (seuls les vecteurs de support comptent)

  • L’astuce du noyau offre une grande flexibilité sans coût de calcul excessif

Limites :

  • Complexité d’entraînement en \(O(n^2)\) à \(O(n^3)\) selon l’implémentation, ce qui les rend inadaptés aux très grands jeux de données (\(n > 10^5\))

  • Sensibilité aux hyperparamètres (\(C\), \(\gamma\)) : une recherche par grille est souvent nécessaire

  • Pas de probabilités calibrées par défaut (l’option probability=True utilise la méthode de Platt, coûteuse)

  • Difficulté d’interprétation en espace noyau (les vecteurs de support vivent dans l’espace transformé)

Remarque 116

En pratique, la mise à l’échelle des features est indispensable pour les SVM. Puisque la marge dépend des distances euclidiennes (ou des produits scalaires), une feature dont les valeurs sont en milliers dominera une feature entre 0 et 1. Il faut toujours standardiser les données avant d’entraîner un SVM, idéalement au sein d’un Pipeline pour éviter toute fuite de données.

Contenu