Utilisez des modèles supervisés non linéaires

SVM à noyau

Prenons un jeu de données $\$\backslash (\backslash \{x^\{(1)\},\; x^\{(2)\},\; \backslash dots,\; x^\{(n)\}\backslash \}\backslash )\$$ étiquetées par $\$\backslash (\backslash \{y^\{(1)\},\; y^\{(2)\},\; \backslash dots,\; y^\{(n)\}\backslash \}\backslash )\$$ , et une application  $\$\backslash (\backslash Phi:\; \backslash mathbb\{R\}^p\; \backslash rightarrow\; H\backslash )\$$  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 $\$\backslash (\backslash Phi(x)\backslash )\$$ . 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 :

$\$\backslash (\backslash arg\; \backslash max\; \backslash alpha\; \backslash in\; \backslash mathbb\{R\}^n\; -\backslash frac\{1\}\{2\}\; \backslash sum\_\{i=1\}^n\; \backslash sum\_\{l=1\}^n\; \backslash alpha\_i\; \backslash alpha\_l\; y^\{(i)\}\; y^\{(l)\}\; \backslash langle\; x\{(i)\},\; x^\{(l)\}\; \backslash rangle\; +\; \backslash sum\_\{i=1\}^n\; \backslash alpha\_i\backslash )\$$

avec $\$\backslash (\backslash alpha\_i\; \backslash geq\; 0\backslash )\$$ pour tout i et $\$\backslash (\backslash sum\_\{i=1\}^n\; \backslash alpha\_i\; y^\{(i)\}\; =\; 0\backslash )\$$ .

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  $\$\backslash (\backslash Phi(x)\backslash )\$$ dans le problème d'optimisation en question :

$\$\backslash (\backslash arg\; \backslash max\; \backslash alpha\; \backslash in\; \backslash mathbb\{R\}^n\; -\backslash frac\{1\}\{2\}\; \backslash sum\_\{i=1\}^n\; \backslash sum\_\{l=1\}^n\; \backslash alpha\_i\; \backslash alpha\_l\; y^\{(i)\}\; y^\{(l)\}\; \backslash langle\; \backslash Phi(x\{(i)\}),\; \backslash Phi(x^\{(l)\})\; \backslash rangle\; +\; \backslash sum\_\{i=1\}^n\; \backslash alpha\_i\backslash )\$$

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

$\$\backslash (f(x)\; =\; \backslash sum\_\{i=1\}^n\; \backslash alpha\_i^*\; y^\{(i)\}\; \backslash langle\; \backslash Phi(x^\{(i)\}),\; \backslash Phi(x)\; \backslash rangle\; +\; b\backslash )\$$

Noyau

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

$\$\backslash (\backslash arg\; \backslash max\; \backslash alpha\; \backslash in\; \backslash mathbb\{R\}^n\; -\backslash frac\{1\}\{2\}\; \backslash sum\_\{i=1\}^n\; \backslash sum\_\{l=1\}^n\; \backslash alpha\_i\; \backslash alpha\_l\; y^\{(i)\}\; y^\{(l)\}\; k(x\{(i)\},\; x^\{(l)\})\; +\; \backslash sum\_\{i=1\}^n\; \backslash alpha\_i\backslash )\$$

et

 $\$\backslash (f(x)\; =\; \backslash sum\_\{i=1\}^n\; \backslash alpha\_i^*\; y^\{(i)\}\; k(x^\{(i)\},\; x)\; +\; b\backslash )\$$  

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 $\$\backslash (x^\{(1)\},\; x^\{(2)\},\; \backslash dots,\; x^\{(m)\}\; \backslash in\; \backslash mathbb\{R\}^p\backslash )\$$ , la matrice K de dimensions m x m telle que $\$\backslash (K\_\{il\}\; =\; k(x^\{(i)\},\; x^\{(l)\})\backslash )\$$ est définie positive.

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

Astuce du noyau

Le tour de passe-passe mathématique où j'ai remplacé les produits scalaires faisant intervenir  $\$\backslash (\backslash Phi\backslash )\$$ 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 $\$\backslash (\backslash Phi\backslash )\$$ , en utilisant directement k sur l'espace initial. C'est ce que l'on appelle l'astuce du noyau, ou kernel trick en anglais.

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 $\$\backslash (\backslash Phi\backslash )\$$ 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  $\$\backslash (x\_1^\{d\_1\}\; x\_2^\{d\_2\}\; \backslash dots\; x\_p^\{d\_p\}\backslash )\$$ , où $\$\backslash (d\_1\; +\; d\_2\; +\; \backslash dots\; +\; d\_p\; =\; d\backslash )\$$ . H a pour dimension $\$\backslash (p^d\backslash )\$$ . Mais prenons maintenant deux points x et x', et calculons le produit scalaire de leurs images : il s'agit en fait tout simplement de $\$\backslash ((\backslash langle\; x,\; x\text{'}\backslash rangle\; +\; 1)^d\backslash )\$$ . C'est d'ailleurs ce qu'on appelle un noyau polynomial.

Plus fou encore, le noyau gaussien :

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

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[data.columns[:-1]].values

# créer le vecteur d'étiquettes
y = data['quality'].values

# 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 !

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 {} with a score of {:.2f}".format(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 :

Matrice de Gram

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

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 $\$\backslash (K\_\{il\}\; =\; k\; (\; x^\{(i)\},\; x^\{(l)\})\backslash )\$$ .

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()

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

# afficher l'image
plt.show()

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 :

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

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 $\$\backslash (M\_\{il\}\; =\; \backslash frac\{K\_\{il\}\}\{\backslash sqrt\{K\_\{ii\}\; K\_\{ll\}\}\}\backslash )\$$ . Les valeurs diagonales de cette matrice seront de 1.

À vous de jouer !

Contexte

Vous êtes le nouveau Data Scientist dans un centre de recherche en cardiologie. Un des grands cardiologues du centre vous propose de l’aider à mettre en place une approche de détection automatique des anomalies grâce aux données des électrocardiogrammes des patients.

Il vous met à disposition un jeu de données où chaque ligne représente les mesures de l’électrocardiogramme d’un patient. La dernière colonne permet de labelliser les patients :

• “0” lorsqu’ils sont sains

• “1” lorsqu’ils comportent une anomalie. 

Les autres colonnes représentent les différents points de mesures de l'électrocardiogramme pour chaque patient.

Le médecin vous dit :

“Nous désirons nous servir de ce dataset pour entraîner un modèle nous permettant de déterminer automatiquement si un nouvel électrocardiogramme que nous mettons en entrée est sain ou s’il présente une anomalie. Cela nous serait très précieux pour améliorer la prise en charge rapide des patients”

Consignes

• Chargez le dataset suivant “ecg.csv”. Observez la dernière colonne du jeu de données pour vérifier que l’échantillon est bien équilibré (c’est à dire que la proportion des électrocardiogrammes sains et comportant une anomalie sont sensiblement identiques).

• Construisez une SVM avec un gamma de 50 et observez sa courbe ROC comme vu dans le cours. 

• Optimisez les performances de votre modèle à l’aide d’une validation croisée.

• Grâce à votre modèle optimisé, quelle valeur d’aire sous la courbe ROC sur le jeu de données de test obtenez-vous ?

Vérifiez votre travail

En résumé

• L’astuce du noyau est un outil mathématique qui permet de transformer un problème non linéaire en un problème linéaire. En pratique, nous allons pouvoir appliquer des algorithmes linéaires tels que la SVM à des problèmes non linéaires.

•  La SVM s’applique sur les problèmes de classification.

•  Lorsque vous voulez utiliser une SVM grâce à la bibliothèque Scikit-learn, vous devez vous assurer de choisir les bons hyperparamètres pour avoir les meilleurs résultats possibles.

•  L’analyse des valeurs de la matrice de Gram permet de voir l’influence de l’hyperparamètre gamma sur la capacité d’apprentissage de la SVM.

•  En pratique, pour choisir les bons hyperparamètres, vous devez effectuer une validation croisée afin d’obtenir les valeurs optimales de C et gamma.

Nous avons appris comment appliquer un algorithme linéaire à un problème non linéaire uniquement pour les cas de problèmes de classification. Nous allons maintenant apprendre à faire la même chose dans le cas d’un problème de régression !