Méthodes à Noyaux

Résumé

Les méthodes à noyaux constituent l’une des avancées les plus élégantes du machine learning classique. Leur idée centrale, le kernel trick (ou astuce du noyau), permet de résoudre des problèmes non linéairement séparables en travaillant implicitement dans un espace de grande — voire infinie — dimension, sans jamais avoir à calculer explicitement la transformation sous-jacente. Ce guide complet couvre le principe mathématique, l’intuition géométrique, les implémentations Python avec scikit-learn (SVM à noyaux et Kernel PCA), l’optimisation des hyperparamètres, ainsi que quatre cas d’usage concrets en production.

Principe Mathématique

Le Kernel Trick (Astuce du Noyau)

Le problème fondamental du machine learning linéaire est simple : de nombreux jeux de données ne sont pas linéairement séparables dans leur espace d’origine. On pourrait tenter de projeter chaque point xᵢ dans un espace de plus grande dimension via une transformation φ(xᵢ), puis appliquer un algorithme linéaire dans cet espace enrichi. Mais ce calcul explicite de φ(x) peut être prohibitif, voire impossible lorsque l’espace cible est de dimension infinie.

Le kernel trick résout ce paradoxe magistralement. Au lieu de calculer φ(xᵢ) puis de former le produit scalaire ⟨φ(xᵢ), φ(xⱼ)⟩ dans l’espace de grande dimension, on calcule directement :

K(xᵢ, xⱼ) = ⟨φ(xᵢ), φ(xⱼ)⟩

La fonction K est appelée fonction noyau (ou fonction kernel). Elle prend deux vecteurs de l’espace original et retourne un scalaire — exactement comme le ferait un produit scalaire après projection, mais sans jamais avoir besoin de connaître φ explicitement.

Le Noyau RBF (Radial Basis Function)

Le noyau RBF, aussi appelé noyau gaussien, est le plus couramment utilisé en pratique :

K(xᵢ, xⱼ) = exp(−γ · ‖xᵢ − xⱼ‖²)

où γ (gamma) est un hyperparamètre positif qui contrôle la largeur de la fonction gaussienne. Plus γ est grand, plus le noyau est sensible aux petites distances entre les points. Ce noyau correspond à une projection dans un espace de dimension infinie — c’est précisément ce qui le rend si puissant et si difficile à calculer explicitement.

Le noyau RBF possède une propriété remarquable : il est universel. Cela signifie que toute fonction continue peut être approximée arbitrairement bien par une combinaison linéaire de noyaux RBF centrés sur les points d’apprentissage. Cette propriété explique pourquoi les SVM avec noyau RBF excellent sur une grande variété de problèmes.

Le Noyau Polynomial

Le noyau polynomial est une alternative populaire :

K(xᵢ, xⱼ) = (γ · xᵢ · xⱼ + coef0)^degree

où γ est le coefficient multiplicateur, coef0 est un terme constant (qui permet d’ajouter de la flexibilité), et degree (noté d) est le degré du polynôme.

Pour degree = 1, on retrouve le noyau linéaire. Pour degree = 2, le noyau correspond à une projection incluant tous les produits croisés xₐ · x_b et toutes les combinaisons quadratiques. Plus le degré augmente, plus l’espace implicite devient riche — mais aussi plus le risque de surapprentissage (overfitting) est élevé.

Théorème de Mercer

Toute fonction ne peut pas servir de noyau. Le théorème de Mercer fournit la condition nécessaire et suffisante : une fonction K est un noyau valide si et seulement si la matrice de Gram K (dont chaque élément Kᵢⱼ = K(xᵢ, xⱼ)) est semi-définie positive pour tout ensemble fini de points {x₁, …, xₙ}.

Autrement dit, pour toute suite de coefficients réels c₁, …, cₙ, on doit avoir :

Σᵢ Σⱼ cᵢ · cⱼ · K(xᵢ, xⱼ) ≥ 0

Cette condition garantit que le problème d’optimisation associé (par exemple l’optimisation quadratique du SVM) est convexe et possède donc un minimum global unique. Les noyaux RBF, polynomial et linéaire satisfont tous cette condition.

Kernel PCA (ACP à Noyau)

L’Analyse en Composantes Principales à Noyau (Kernel PCA) généralise l’ACP classique aux données non linéaires. Alors que l’ACP standard projette les données sur les vecteurs propres de la matrice de covariance (capturant les directions de plus grande variance linéaire), la Kernel PCA procède ainsi :

1. On calcule la matrice de Gram K où Kᵢⱼ = K(xᵢ, xⱼ) pour un noyau choisi (RBF, polynomial, etc.)
2. On centre cette matrice de Gram : K̃ = K − 1ₙK − K1ₙ + 1ₙK1ₙ, où 1ₙ est la matrice n × n dont chaque élément vaut 1/n
3. On calcule les valeurs propres λₖ et les vecteurs propres αₖ de la matrice K̃ centrée
4. La projection d’un point x dans la k-ième composante principale est donnée par : zₖ = Σᵢ αₖⁱ · K(xᵢ, x)

Contrairement à l’ACP classique, la Kernel PCA peut capturer des structures non linéaires complexes comme des spirales, des cercles concentriques ou des variétés courbes.

Intuition Géométrique : Les Ombres Chinoises

Pour comprendre pourquoi le kernel trick fonctionne, imaginez des ombres chinoises projetées sur un mur.

Vous observez deux silhouettes d’objets sur le mur, et ces silhouettes sont entrelacées — impossible de tracer une ligne droite pour les séparer. C’est exactement le problème de la séparabilité linéaire en deux dimensions : les données de chaque classe sont mélangées de manière non linéaire.

Maintenant, imaginez que vous puissiez monter les objets en trois dimensions. En ajoutant cette troisième dimension (la transformation φ), les deux silhouettes se retrouvent à des hauteurs différentes. D’un seul coup, vous pouvez faire glisser une feuille plane entre elles — une séparation linéaire devient possible.

Voilà l’essence du kernel trick : calculer directement cette séparabilité 3D sans avoir à construire le monde 3D. On reste en deux dimensions, nos données n’ont pas bougé, mais grâce au noyau K, on dispose du pouvoir de la 3D sans en payer le coût computationnel.

C’est comme si vous pouviez déterminer si deux silhouettes peuvent être séparées dans la troisième dimension simplement en regardant leur distance relative sur le mur, sans jamais avoir à manipuler l’objet en 3D. Le noyau est cette formule magique qui remplace la géométrie explicite par un calcul de similarité.

Implémentation Python avec scikit-learn

SVM à Noyaux sur des Données Non Linéaires (Moons)

Commençons par un exemple classique : les données « moons » (deux demi-cercles entrelacés), intrinsèquement non linéairement séparables.

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_moons
from sklearn.svm import SVC
from sklearn.model_selection import train_test_split, GridSearchCV
from sklearn.metrics import classification_report, accuracy_score
from sklearn.decomposition import KernelPCA
from sklearn.preprocessing import StandardScaler

# Génération des données
X, y = make_moons(n_samples=1000, noise=0.15, random_state=42)
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.25, random_state=42
)

# Standardisation (importante pour les noyaux basés sur les distances)
scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)
X_test_scaled = scaler.transform(X_test)

# ----- Comparaison des noyaux -----
kernels = {
    "linéaire": "linear",
    "polynomial (deg=3)": "poly",
    "RBF": "rbf"
}

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

for idx, (nom, k_type) in enumerate(kernels.items(), 1):
    # Configuration du SVM selon le type de noyau
    if k_type == "poly":
        svm = SVC(kernel=k_type, degree=3, coef0=1.0, C=1.0, random_state=42)
    else:
        svm = SVC(kernel=k_type, C=1.0, gamma="scale", random_state=42)

    svm.fit(X_train_scaled, y_train)
    y_pred = svm.predict(X_test_scaled)

    print(f"Noyau {nom} — Précision : {accuracy_score(y_test, y_pred):.4f}")

    # Visualisation de la frontière de décision
    ax = axes[0] if idx == 1 else (axes[1] if idx == 2 else axes[2])
    h = 0.02
    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.arange(x_min, x_max, h),
                         np.arange(y_min, y_max, h))

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

    ax.contourf(xx, yy, Z, alpha=0.3, cmap=plt.cm.coolwarm)
    ax.scatter(X_train_scaled[:, 0], X_train_scaled[:, 1], c=y_train,
               edgecolors="k", cmap=plt.cm.coolwarm, s=30)
    ax.set_title(f"SVM — Noyau {nom}")
    ax.set_xlabel("x₁")
    ax.set_ylabel("x₂")

plt.tight_layout()
plt.savefig("svm_kernels_comparison.png", dpi=150)
plt.show()

La comparaison est édifiante : le noyau linéaire échoue complètement sur les données en forme de lunes, tandis que les noyaux RBF et polynomial capturent parfaitement la structure non linéaire des deux demi-cercles.

Kernel PCA avec Visualisation

La Kernel PCA excelle là où l’ACP classique échoue. Illustrons cela sur des données en forme de spirale :

from sklearn.decomposition import PCA

# Génération de données en spirale (encore plus non linéaires)
def make_spiral(n_points=500, noise=0.1, random_state=42):
    rng = np.random.RandomState(random_state)
    n = n_points // 2
    t1 = np.linspace(0, 3 * np.pi, n)
    t2 = np.linspace(0, 3 * np.pi, n)

    x1 = t1 * np.cos(t1) + rng.randn(n) * noise
    y1 = t1 * np.sin(t1) + rng.randn(n) * noise
    x2 = t2 * np.cos(t2 + np.pi) + rng.randn(n) * noise
    y2 = t2 * np.sin(t2 + np.pi) + rng.randn(n) * noise

    X_spiral = np.vstack([
        np.column_stack([x1, y1]),
        np.column_stack([x2, y2])
    ])
    y_spiral = np.array([0] * n + [1] * n)

    return X_spiral, y_spiral

X_sp, y_sp = make_spiral(n_points=600, noise=0.3)

# ACP classique vs Kernel PCA
fig, axes = plt.subplots(1, 3, figsize=(18, 5))

# Données originales
axes[0].scatter(X_sp[:, 0], X_sp[:, 1], c=y_sp, cmap=plt.cm.coolwarm,
                edgecolors="k", s=30, alpha=0.8)
axes[0].set_title("Données originales (spirales)")
axes[0].set_xlabel("x₁")
axes[0].set_ylabel("x₂")

# ACP classique
pca = PCA(n_components=2)
X_pca = pca.fit_transform(X_sp)
axes[1].scatter(X_pca[:, 0], X_pca[:, 1], c=y_sp, cmap=plt.cm.coolwarm,
                edgecolors="k", s=30, alpha=0.8)
axes[1].set_title("ACP Classique (échoue)")
axes[1].set_xlabel("CP1")
axes[1].set_ylabel("CP2")

# Kernel PCA avec noyau RBF
kpca = KernelPCA(n_components=2, kernel="rbf", gamma=0.05, random_state=42)
X_kpca = kpca.fit_transform(X_sp)
axes[2].scatter(X_kpca[:, 0], X_kpca[:, 1], c=y_sp, cmap=plt.cm.coolwarm,
                edgecolors="k", s=30, alpha=0.8)
axes[2].set_title("Kernel PCA RBF (réussite)")
axes[2].set_xlabel("KCP1")
axes[2].set_ylabel("KCP2")

plt.tight_layout()
plt.savefig("kpca_vs_pca.png", dpi=150)
plt.show()

Le résultat est sans appel : l’ACP classique mélange les deux spirales dans l’espace réduit, tandis que la Kernel PCA les sépare parfaitement grâce à la projection non linéaire induite par le noyau RBF.

Grid Search sur gamma et C

L’optimisation des hyperparamètres γ et C est cruciale pour les SVM à noyaux. Voici la démarche systématique :

from sklearn.model_selection import GridSearchCV

# Grille de recherche sur gamma et C
param_grid = {
    "C": [0.1, 1.0, 10.0, 100.0],
    "gamma": [0.01, 0.1, 1.0, 10.0],
    "kernel": ["rbf"]
}

grid_search = GridSearchCV(
    SVC(random_state=42),
    param_grid,
    cv=5,
    scoring="accuracy",
    n_jobs=-1,
    verbose=1
)

grid_search.fit(X_train_scaled, y_train)

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

# Évaluation sur l'ensemble de test
best_svm = grid_search.best_estimator_
y_pred_test = best_svm.predict(X_test_scaled)
print(f"Précision test : {accuracy_score(y_test, y_pred_test):.4f}")

# Visualisation de la surface de performance
C_values = param_grid["C"]
gamma_values = param_grid["gamma"]
scores = grid_search.cv_results_["mean_test_score"]
scores = scores.reshape(len(C_values), len(gamma_values))

plt.figure(figsize=(10, 6))
im = plt.imshow(scores, cmap="viridis", aspect="auto")
plt.xticks(range(len(gamma_values)), gamma_values)
plt.yticks(range(len(C_values)), C_values)
plt.xlabel("gamma")
plt.ylabel("C")
plt.title("Grid Search — Précision CV moyenne")
plt.colorbar(im, label="Précision")
for i in range(len(C_values)):
    for j in range(len(gamma_values)):
        plt.text(j, i, f"{scores[i, j]:.3f}",
                 ha="center", va="center", color="white")
plt.tight_layout()
plt.savefig("grid_search_heatmap.png", dpi=150)
plt.show()

Hyperparamètres Détaillés

Le choix des hyperparamètres d’un SVM à noyau détermine fondamentalement le comportement du modèle. Voici un guide détaillé :

Gamma : le paramètre critique du noyau RBF

Gamma est sans doute l’hyperparamètre le plus important pour le noyau RBF. La valeur par défaut “scale” de scikit-learn calcule γ = 1 / (n_features × variance), ce qui est un bon point de départ. Mais selon la distribution de vos données, un ajustement peut être nécessaire :

• γ trop faible : la frontière de décision est trop lisse, le modèle sous-apprend et manque les structures fines des données.
• γ trop élevé : chaque point d’apprentissage influence une zone très restreinte, créant une frontière excessivement complexe qui surapprend le bruit.
• γ optimal : capture la structure réelle des données sans modéliser le bruit d’échantillonnage.

C : le contrôle de la complexité

Le paramètre C détermine le compromis marge / erreur de classification :

• C faible : privilégie une marge large, accepte plus d’erreurs d’apprentissage. Résultat : modèle plus simple, plus généralisable.
• C fort : force le modèle à bien classer chaque point d’apprentissage, quitte à réduire la marge. Résultat : frontière complexe, risque de surapprentissage.

En pratique, on explore C sur une échelle logarithmique (0.01, 0.1, 1, 10, 100) combinée avec gamma.

Avantages et Limites

Avantages

• Puissance non linéaire sans coût computationnel : grâce au kernel trick, les méthodes à noyaux résolvent des problèmes de dimension infinie avec des calculs en dimension d’origine. C’est l’un des résultats les plus élégants du machine learning.
• Fonctionnement en petite dimension : contrairement aux réseaux de neurones profonds qui nécessitent beaucoup de données, les SVM à noyaux excellent avec des échantillons de taille modérée (quelques centaines à quelques milliers d’observations).
• Garanties théoriques solides : le théorème de Mercer garantit la convexité de l’optimisation, et la théorie de Vapnik-Chervonenkis fournit des bornes de généralisation rigoureuses.
• Flexibilité du noyau : on peut concevoir des noyaux sur mesure pour des types de données spécifiques (noyau sur les graphes, noyau sur les chaînes de caractères, noyau sur les distributions).
• Robustesse au surapprentissage : grâce au paramètre C et à la maximisation de marge, les SVM à noyaux sont intrinsèquement robustes, surtout en haute dimension.

Limites

• Complexité en O(n²) à O(n³) : le calcul et le stockage de la matrice de Gram deviennent prohibitifs au-delà de 50 000 à 100 000 échantillons. Pour les très grands jeux de données, des approximations comme Nyström ou les features aléatoires de Fourier sont nécessaires.
• Sensibilité aux hyperparamètres : la performance dépend fortement du choix de γ et C. Un mauvais réglage peut mener à un désastre — d’où l’importance cruciale de la validation croisée.
• Interprétabilité réduite : contrairement à un arbre de décision ou une régression linéaire, la frontière de décision d’un SVM à noyau RBF est pratiquement impossible à interpréter humainement.
• Prédiction coûteuse : pour classer un nouveau point, le SVM doit évaluer le noyau avec tous les vecteurs de support. Si le nombre de vecteurs de support est élevé (ce qui arrive avec un C fort), la prédiction est lente.
• Pas de probabilités natives : le SVM produit des scores de décision bruts. Pour obtenir des probabilités, il faut utiliser un calibrage supplémentaire (Platt scaling), qui ajoute un coût computationnel.

Quatre Cas d’Usage Concrets

1. Classification de Textes avec Noyau sur les Séquences

En traitement automatique du langage naturel (TALN), les documents sont souvent représentés comme des sacs de mots. Mais cette représentation perd l’ordre des mots. Un noyau sur les séquences (string kernel) capture les sous-séquences communes entre deux documents tout en respectant leur ordre, améliorant significativement la classification de textes, la détection de spam ou l’analyse de sentiment. En pratique, on utilise un SVM avec un noyau polynomial de degré 2 ou 3 qui capture les interactions entre mots adjacents.

2. Diagnostic Médical par Imagerie

En analyse d’images médicales (radiographies, IRM, scanners), les SVM à noyau RBF sont fréquemment utilisés pour classifier des lésions bénignes versus malignes. Les caractéristiques extraites (texture, forme, intensité) forment un espace de petite dimension où la séparation est fortement non linéaire. Le noyau RBF capture ces interactions complexes sans nécessiter des milliers d’exemples comme le ferait un réseau neuronal profond — un avantage crucial quand les données médicales annotées sont rares et coûteuses à obtenir.

3. Détection d’Anomalies avec One-Class SVM

La One-Class SVM est une variante des méthodes à noyaux pour la détection d’anomalies. Au lieu de séparer deux classes, elle apprend la frontière qui englobe la distribution normale des données. Tout point situé à l’extérieur de cette frontière est signalé comme anomale. Applications typiques : détection de fraude bancaire, surveillance de la qualité industrielle, surveillance de la cybersécurité. Le noyau RBF est ici particulièrement adapté car il modélise la densité locale des données sans hypothèse paramétrique.

4. Réduction de Dimension Non Linéaire avec Kernel PCA

La Kernel PCA sert de prétraitement avant d’autres algorithmes de machine learning. Imaginons que vous disposiez de données génomiques de haute dimension (des milliers de gènes) avec une structure non linéaire sous-jacente (voies métaboliques interactives). L’ACP classique ne capturera que la variance linéaire, manquant les interactions entre gènes. La Kernel PCA avec un noyau RBF projette ces données dans un espace réduit où les structures non linéaires sont préservées, améliorant ensuite la performance d’un classifieur ou d’un modèle de clustering appliqué sur les composantes principales à noyau.

Voir Aussi

• Maîtrisez les Périodes de Pisano en Python : Guide Complet pour Développeurs
• Windows | Ajouter Git aux variables d’environnement