• 12 heures
  • Moyenne

Ce cours est visible gratuitement en ligne.

course.header.alt.is_video

course.header.alt.is_certifying

J'ai tout compris !

Mis à jour le 31/05/2019

Classifiez vos données avec une SVM à noyau

Connectez-vous ou inscrivez-vous gratuitement pour bénéficier de toutes les fonctionnalités de ce cours !

SVM à noyau

Prenons un jeu de données $\(\{x^{(1)}, x^{(2)}, \dots, x^{(n)}\}\)$ étiquetées par $\(\{y^{(1)}, y^{(2)}, \dots, y^{(n)}\}\)$ , et une application  $\(\Phi: \mathbb{R}^p \rightarrow H\)$  qui permet de redécrire ces données dans l'espace de redescription H.

Plutôt que d'utiliser une SVM linéaire pour apprendre un modèle linéaire qui explique y comme une fonction linéaire des coordonnées de x, nous pouvons utiliser ce même algorithme de SVM linéaire dans H pour apprendre un modèle qui explique y comme une fonction linéaire des coordonnées de $\(\Phi(x)\)$ . Nous créons ainsi un modèle non-linéaire dans l'espace initial.

Regardons de plus près ce que cela veut dire, et reprenons pour cela l'expression duale de l'apprentissage du SVM :

$\(\arg \max \alpha \in \mathbb{R}^n -\frac{1}{2} \sum_{i=1}^n \sum_{l=1}^n \alpha_i \alpha_l y^{(i)} y^{(l)} \langle x{(i)}, x^{(l)} \rangle + \sum_{i=1}^n \alpha_i\)$

avec $\(\alpha_i \geq 0\)$ pour tout i et $\(\sum_{i=1}^n \alpha_i y^{(i)} = 0\)$ .

Comme nous apprenons notre SVM non pas dans l'espace initial dans lequel les données sont décrites, mais dans l'espace de redescription H, nous remplaçons donc x par  $\(\Phi(x)\)$ dans le problème d'optimisation en question :

$\(\arg \max \alpha \in \mathbb{R}^n -\frac{1}{2} \sum_{i=1}^n \sum_{l=1}^n \alpha_i \alpha_l y^{(i)} y^{(l)} \langle \Phi(x{(i)}), \Phi(x^{(l)}) \rangle + \sum_{i=1}^n \alpha_i\)$

Nous pouvons faire la même manipulation sur la fonction de décision : la prédiction se fait en fonction du signe de

$\(f(x) = \sum_{i=1}^n \alpha_i^* y^{(i)} \langle \Phi(x^{(i)}), \Phi(x) \rangle + b\)$

Noyau

Appelons maintenant k la fonction qui à $\((x^{(i)}, x^{(l)})\)$ associe $\(k(x^{(i)}, x^{(l)}) = \langle \Phi(x^{(i)}), \Phi(x^{(l)})\rangle\)$ . Je peux réécrire et le problème d'optimisation et la fonction de décision en utilisant uniquement k et non plus $\(\Phi\)$ :

$\(\arg \max \alpha \in \mathbb{R}^n -\frac{1}{2} \sum_{i=1}^n \sum_{l=1}^n \alpha_i \alpha_l y^{(i)} y^{(l)} k(x{(i)}, x^{(l)}) + \sum_{i=1}^n \alpha_i\)$

et

 $\(f(x) = \sum_{i=1}^n \alpha_i^* y^{(i)} k(x^{(i)}, x) + b\)$  

La fonction k s'appelle un noyau (kernel en anglais, d'où la notation k), et a deux propriétés mathématiques intéressantes :

  • elle est définie positive, autrement dit, étant donnés un nombre arbitraires de points $\(x^{(1)}, x^{(2)}, \dots, x^{(m)} \in \mathbb{R}^p\)$ , la matrice K de dimensions m x m telle que $\(K_{il} = k(x^{(i)}, x^{(l)})\)$ est définie positive.

  • quelle que soit la fonction $\(h: \mathbb{R}^p \times \mathbb{R}^p \to \mathbb{R}\)$ , si h est définie positive, alors il existe un espace de Hilbert H et une application $\(\psi: \mathbb{R}^p \to H\)$ telle que $\(h(x, x') = \langle \psi(x), \psi(x') \rangle\)$ .

Astuce du noyau

Le tour de passe-passe mathématique où j'ai remplacé les produits scalaires faisant intervenir  $\(\Phi\)$ par k peut paraître anodin, mais il est en fait très intéressant : il va nous permettre d'apprendre une SVM non-linéaire et de l'utiliser pour faire des prédictions sans calculer explicitement $\(\Phi\)$ , en utilisant directement k sur l'espace initial. C'est ce que l'on appelle l'astuce du noyau, ou kernel trick en anglais.

D'accord, mais quel est l'intérêt de cette astuce ?

Cette astuce est super intéressante parce que l'espace de redescription H peut être de très très grande dimension, et de ne pas avoir à calculer l'image de chaque point par $\(\Phi\)$ va nous sauver énormément de temps, voire nous permettre d'utiliser des espaces de redescription que nous ne savons pas définir explicitement !

Exemples de noyau

Considérons par exemple un espace H qui permette de décrire une fonction de décision qui soit un polynôme de degré d. La fonction de redescription associe à x l'ensemble de tous les monômes de degré d, autrement dit les polynômes de la forme  $\(x_1^{d_1} x_2^{d_2} \dots x_p^{d_p}\)$ , où $\(d_1 + d_2 + \dots + d_p = d\)$ . H a pour dimension $\(p^d\)$ . Mais prenons maintenant deux points x et x', et calculons le produit scalaire de leurs images : il s'agit en fait tout simplement de $\((\langle x, x'\rangle + 1)^d\)$ . C'est d'ailleurs ce qu'on appelle un noyau polynomial.

Plus fou encore, le noyau gaussien :

$\(k(x, x') = \exp ( - \frac{\langle x-x', x-x'\rangle^2}{2 \sigma^2})\)$

Il correspond à un espace de redescription de dimension infinie ! Autrement dit, il nous permet de résoudre une SVM dans un espace de redescription qu'on ne peut même pas calculer explicitement... C'est fort !

Le fait que n'importe quelle fonction définie positive soit un noyau donne au SVM non-linéaires un grand pouvoir de modélisation : un noyau, comme un produit scalaire, peut en effet être interprété comme une mesure de similarité (deux vecteurs colinéaires ont un produit scalaire élevé, deux vecteurs orthogonaux ont un produit scalaire nul). Cela signifie que l'on peut créer des noyaux appropriés pour un domaine d'application particulier, et qu'il « suffit » pour cela de construire une mesure de similarité entre observations qui soit définie positive.

En pratique avec scikit-learn

Les SVM à noyaux sont implémentées dans scikit-learn dans les classes sklearn.svm.SVC pour la classification et sklearn.svm.SVR pour la régression. Dans ces deux classes, vous pouvez spécifier un noyau grâce au paramètre « kernel ». Ce noyau peut être un des grands classiques (linéaire, polynomial, RBF), mais vous pouvez aussi définir vos propres noyaux !

Regardons comment utiliser la classe sklearn.svm.SVC en pratique. Nous allons utiliser les données concernant les caractéristiques physico-chimiques de vins blancs portugais disponibles sur l'archive UCI. Il s'agit ici de prédire le score (entre 3 et 9) donné par des experts aux différents vins. Chargeons les données et transformons le problème en un problème de classification, pour lequel il s'agira de prédire si le score est supérieur à 6 (vin de bonne qualité) ou non :

import numpy as np
# charger les données
import pandas as pd
data = pd.read_csv('winequality-white.csv', sep=';')

# créer la matrice de données
X = data.as_matrix(data.columns[:-1])

# créer le vecteur d'étiquettes
y = data.as_matrix([data.columns[-1]])
y = y.flatten()

# transformer en un problème de classification binaire
y_class = np.where(y<6, 0, 1)

Avant toute chose, nous allons découper nos données en un jeu d'entraînement (X_train, y_train) et un jeu de test (X_test, y_test).

from sklearn import model_selection
X_train, X_test, y_train, y_test = \
model_selection.train_test_split(X, y_class, 
                                test_size=0.3)

Nous pouvons maintenant standardiser les variables, c'est-à-dire les centrer (ramener leur moyenne à 0) et les réduire (ramener leur écart-type à 1), afin qu'elles se placent toutes à peu près sur la même échelle.

# standardiser les données
from sklearn import preprocessing
std_scale = preprocessing.StandardScaler().fit(X_train)

X_train_std = std_scale.transform(X_train)
X_test_std = std_scale.transform(X_test)

OK, nous pouvons enfin entraîner notre première SVM à noyau !

# Créer une SVM avec un noyau gaussien de paramètre gamma=0.01
from sklearn import svm
classifier = svm.SVC(kernel='rbf', gamma=0.01)

# Entraîner la SVM sur le jeu d'entraînement
classifier.fit(X_train_std, y_train)

Comment se comporte-t-elle sur le jeu de test ? Nous allons pour le comprendre regarder la courbe ROC.

# prédire sur le jeu de test
y_test_pred = classifier.decision_function(X_test_std)

# construire la courbe ROC
from sklearn import metrics
fpr, tpr, thr = metrics.roc_curve(y_test, y_test_pred)

# calculer l'aire sous la courbe ROC
auc = metrics.auc(fpr, tpr)

# créer une figure
from matplotlib import pyplot as plt
fig = plt.figure(figsize=(6, 6))

# afficher la courbe ROC
plt.plot(fpr, tpr, '-', lw=2, label='gamma=0.01, AUC=%.2f' % auc)

# donner un titre aux axes et au graphique
plt.xlabel('False Positive Rate', fontsize=16)
plt.ylabel('True Positive Rate', fontsize=16)
plt.title('SVM ROC Curve', fontsize=16)

# afficher la légende
plt.legend(loc="lower right", fontsize=14)

# afficher l'image
plt.show()

Et voilà notre courbe ROC, avec une AUC de 0.81, plutôt pas mal !

Courbe ROC d'une SVM avec noyau gaussien sur les données winequality-white.
Courbe ROC d'une SVM avec noyau gaussien sur les données winequality-white.

Sélection des hyperparamètres

Nous allons ici utiliser une validation croisée sur le jeu d'entraînement pour sélectionner les valeurs optimales de C et de gamma parmi une grille de valeurs.

# choisir 6 valeurs pour C, entre 1e-2 et 1e3
C_range = np.logspace(-2, 3, 6)

# choisir 4 valeurs pour gamma, entre 1e-2 et 10
gamma_range = np.logspace(-2, 1, 4)

# grille de paramètres
param_grid = {'C': C_range, 'gamma': gamma_range}

# critère de sélection du meilleur modèle
score = 'roc_auc'

# initialiser une recherche sur grille
grid = model_selection.GridSearchCV(svm.SVC(kernel='rbf'), 
                                    param_grid, 
                                    cv=5, # 5 folds de validation croisée  
                                    scoring=score)

# faire tourner la recherche sur grille
grid.fit(X_train_std, y_train)

# afficher les paramètres optimaux
print("The optimal parameters are %s with a score of %.2f" % \
      (grid.best_params_, grid.best_score_))
The optimal parameters are {'C': 1.0, 'gamma': 1.0} with a score of 0.85

Nous pouvons maintenant évaluer la performance de notre modèle optimisé sur le jeu de test :

# prédire sur le jeu de test avec le modèle optimisé
y_test_pred_cv = grid.decision_function(X_test_std)

# construire la courbe ROC du modèle optimisé
fpr_cv, tpr_cv, thr_cv = metrics.roc_curve(y_test, y_test_pred_cv)

# calculer l'aire sous la courbe ROC du modèle optimisé
auc_cv = metrics.auc(fpr_cv, tpr_cv)

# créer une figure
fig = plt.figure(figsize=(6, 6))

# afficher la courbe ROC précédente
plt.plot(fpr, tpr, '-', lw=2, label='gamma=0.01, AUC=%.2f' % auc)

# afficher la courbe ROC du modèle optimisé
plt.plot(fpr_cv, tpr_cv, '-', lw=2, label='gamma=%.1e, AUC=%.2f' % \
         (grid.best_params_['gamma'], auc_cv))
         

# donner un titre aux axes et au graphique
plt.xlabel('False Positive Rate', fontsize=16)
plt.ylabel('True Positive Rate', fontsize=16)
plt.title('SVM ROC Curve', fontsize=16)

# afficher la légende
plt.legend(loc="lower right", fontsize=14)

# afficher l'image
plt.show()

On obtient alors la courbe ROC suivante, avec une performance optimisée :

Courbe ROC d'une SVM avec noyau gaussien optimisée, sur les données winequality-white
Courbe ROC d'une SVM avec noyau gaussien optimisée, sur les données winequality-white

Matrice de Gram

Quel est l'importance du paramètre gamma ? La documentation nous indique que le noyau RBF gaussien est donné par $\(K(x, x') = \exp(- \gamma ||x - x'||^2)\)$ .

Gamma contrôle la bande passante de la gaussienne : plus gamma est élevé, plus la gaussienne est étroite, autrement dit, plus la distance entre x et x' doit être faible pour que le noyau soit différent de 0.

Pour en visualiser l'effet, nous pouvons visualiser la matrice de Gram des données, autrement dit la matrice K telle que $\(K_{il} = k ( x^{(i)}, x^{(l)})\)$ .

Calculons la matrice de Gram obtenue sur notre jeu d'entraînement quand gamma=0.01 :

from sklearn import metrics
kmatrix = metrics.pairwise.rbf_kernel(X_train_std, gamma=0.01)

Nous allons réduire cette matrice à ses 100 premières lignes et 100 premières colonnes pour en faciliter la visualisation :

kmatrix100 = kmatrix[:100, :100]

Nous pouvons maintenant utiliser plt.pcolor pour visualiser cette matrice :

# dessiner la matrice
plt.pcolor(kmatrix100, cmap=matplotlib.cm.PuRd) 

# rajouter la légende
plt.colorbar()

# définir les axes
plt.xlim([0, X.shape[0]])
plt.ylim([0, X.shape[0]])

# retourner l'axe des ordonnées
plt.gca().invert_yaxis()
plt.gca().xaxis.tick_top()

# afficher l'image
plt.show()
Matrice de Gram pour gamma=0.01
Matrice de Gram pour gamma=0.01

Nous avons ici des valeurs de noyau comprises entre 0.40 et 1.0, avec une diagonale plus forte mais qui n'écrase pas la matrice.

Avec une valeur de gamma plus grande, par exemple, gamma=50, on obtient la matrice de Gram suivante :

Matrice de Gram pour gamma=50
Matrice de Gram pour gamma=50

Cette matrice est à diagonale dominante. Si l'on entraîne une SVM avec cette valeur de gamma, la courbe ROC est beaucoup moins bonne :

Courbe ROC d'une SVM avec noyau gaussien, pour plusieurs valeurs de gamma, sur les données winequality-white.
Courbe ROC d'une SVM avec noyau gaussien, pour plusieurs valeurs de gamma, sur les données winequality-white.

Que faire si la matrice de Gram est dominée par sa diagonale ? Deux choix sont possibles :

  • jouer avec les paramètres du noyau pour réduire la différence entre les valeurs diagonales et les valeurs hors diagonale

  • remplacer la matrice de Gram K par la matrice M telle que $\(M_{il} = \frac{K_{il}}{\sqrt{K_{ii} K_{ll}}}\)$ . Les valeurs diagonales de cette matrice seront de 1.

Exemple de certificat de réussite
Exemple de certificat de réussite