Dans cette première partie, nous nous intéressons à une SVM linéaire. Cette première version de SVM fournit un classifieur linéaire $h(x)$ paramétré par $w$ et $b$ séparant l'espace par l'hyperplan d'équation $w \cdot x + b = 0$
Formellement, on pose $(\mathbf{x_i},y_i)_{i=1}^n$ un ensemble de $n$ points d'entraînement, avec $\mathbf{x_i} \in \mathbb{R}^d$ et $y_i \in \lbrace -1, 1 \rbrace.$\ On résoud ensuite : \begin{array}{ll} \mbox{minimiser } &\frac{1}{2}~||\mathbf{w}||^2 + C \sum_{i=1}^n \zeta_i \ \mbox{sous contraintes } & \forall i, y_i(<\mathbf{w},\mathbf{x_i}> + b) \geq 1 - \zeta_i \ & \forall i, \zeta_i \geq 0\ \end{array}
On obtient alors une suite de coefficients $(\alpha_i)_{i=1}^n, \alpha_i \geq 0$ et
$\mathbf{w}=\sum_{i=1}^n \alpha_i y_i \mathbf{x_i}$
$h(\mathbf{x}) = <\mathbf{w},\mathbf{x}> + b.$
Les vecteurs $\mathbf{x_i}$ tels que $\alpha_i > 0$ sont appelés $ \textbf{vecteurs supports}.$
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
a) Générer un ensemble d’entraînement linéairement séparable. Composé de 50 exemples, avec 2 features. (On peut prendre par exemple des label positif pour x1 > 0.)
- afficher cette ensemble d'entrainement avec les labels en couleurs.
- entrainer un SVM linéaire (from sklearn.svm import LinearSVC)
- afficher l'ensemble de décision avec la fonction plot_boundary
b) Sur cette ensemble, rajouter du bruit aux $y$. (i.e. avec probabilité $p$, $y_i = 1-y_i$)
- Afficher l'ensemble, entrainer un SVM linéaire et faire varier le paramètre C.
c) Cas du XOR :
- générer l'ensemble d'entrainement suivant :
X = ( 0,0 y = (1
1,0 0
0,1 0
1,1) 1)
- afficher cette ensemble d'entrainement avec les labels en couleurs.
- entrainer un SVM linéaire (from sklearn.svm import LinearSVC)
- afficher l'ensemble de décision avec la fonction plot_boundary
from sklearn.svm import LinearSVC
#http://scikit-learn.org/stable/modules/generated/sklearn.svm.LinearSVC.html
def plot_boundary(clf, X, y):
h = 0.002
x_min, x_max = X[:, 0].min() - .1, X[:, 0].max() + .1
y_min, y_max = X[:, 1].min() - .1, X[:, 1].max() + .1
xx, yy = np.meshgrid(np.arange(x_min, x_max, h),
np.arange(y_min, y_max, h))
Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])
Z = Z.reshape(xx.shape)
plt.figure()
plt.contourf(xx, yy, Z, cmap=plt.cm.Paired, alpha=0.8)
plt.scatter(X[:, 0], X[:, 1], c=y, s = 100)
plt.title('score : ' + str(clf.score(X,y)))
plt.xlabel('$x_1$')
plt.ylabel('$x_2$')
np.random.seed(21)
X = np.random.rand(50,2)
y = X[:,0] > 0.5
plt.scatter(X[:,0],X[:,1], c = y, s = 100)
clf = LinearSVC(C=1)
clf.fit(X,y)
print("score d'entrainement:",clf.score(X,y))
plot_boundary(clf,X,y)
np.random.seed(2)
X = np.random.rand(100,2)
y = X[:,0] > 0.5
lines_noise = np.random.choice(range(len(y)), 10)
y[lines_noise] = 1 - y[lines_noise]
plt.scatter(X[:,0],X[:,1], c = y, s = 100)
for C in [10**x for x in range(-5,6)]:
clf = LinearSVC(C=C)
clf.fit(X,y)
print("score d'entrainement:",clf.score(X,y))
plot_boundary(clf,X,y)
plt.title('C = ' + str(C))
X_xor = np.asarray([[0,0],[1,1],[1,0],[0,1]])
y_xor = np.asarray([0,0,1,1])
plt.scatter(X_xor[:,0],X_xor[:,1], c = y_xor, s = 800)
clf_xor = LinearSVC(C=100)
clf_xor.fit(X_xor,y_xor)
print("score d'entrainement:",clf_xor.score(X_xor,y_xor))
plot_boundary(clf_xor,X_xor,y_xor)
"L'astuce du noyau" est une méthode permettant d'étendre l'espace $\mathcal{H}$ d'hypothèses. L'idée est de plonger les données d'entraînements via une fonction $\phi$ dans un espace de grande dimension $(feature\ space$).
La fonction de décision $h$ de prédiction s'écrit maintenant :
$$ h(\mathbf{x}) = \sum_{i=1}^n \alpha_i y_i \phi(x_i) \cdot \phi(x) + b = \sum_{i=1}^n \alpha_i y_i K(\mathbf{x_i},\mathbf{x}) + b. $$The kernel function can be any of the following:
linear: $\langle x, x'\rangle.$
poly (i.e. polynomial): $(\gamma \langle x, x'\rangle + r)^d.$ d is specified by keyword degree, r by $coef0$.
rbf: $\exp(-\gamma |x-x'|^2).$ $\gamma$ is specified by keyword $gamma$, must be greater than 0.
sigmoid : $(\tanh(\gamma \langle x,x'\rangle + r))$, where r is specified by $coef0.$
from sklearn.svm import SVC
#http://scikit-learn.org/stable/modules/generated/sklearn.svm.SVC.html
a) Générer des données d'entrainement non linéairement séparable puis les afficher avec les couleurs. On peut utiliser :
b) avec la même méthode, générer des données de test.
c) Entraîner un SVM avec les différents noyaux possibles. Et avec différentes valeurs de $C$.
d) On peut afficher les vecteurs servant du spport avec l'attribut $support\_vectors\_$
from sklearn.datasets import make_moons
X, y = make_moons(noise = 0.1, random_state=1, n_samples=40)
plt.scatter(X[:,0],X[:,1], c = y, s = 100)
X_test, y_test = make_moons(noise = 0.1, random_state=321)
plt.scatter(X_test[:,0],X_test[:,1], c = y_test, s = 100)
#kernel = 'linear'
for C in [10**x for x in range(-3,5)]:
clf = SVC(C=C, kernel='linear')
clf.fit(X,y)
print("score d'entrainement:",clf.score(X,y), ". score de test:", clf.score(X_test,y_test))
plot_boundary(clf,X,y)
plt.scatter(clf.support_vectors_[:,0],clf.support_vectors_[:,1], c = 'green', s = 200, marker='*')
#kernel = 'poly'
for C in [10**x for x in range(-3,5)]:
clf = SVC(C=C, kernel='poly', degree = 3, coef0 = 1)
clf.fit(X,y)
print("score d'entrainement:",clf.score(X,y), ". score de test:", clf.score(X_test,y_test))
plot_boundary(clf,X,y)
plt.scatter(clf.support_vectors_[:,0],clf.support_vectors_[:,1], c = 'green', s = 200, marker='*')