TP 3 : SVM

1 - Cas linéaire

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}.$

In [4]:
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline

Questions :

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
In [5]:
from sklearn.svm import LinearSVC
#http://scikit-learn.org/stable/modules/generated/sklearn.svm.LinearSVC.html
In [48]:
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$')
    
In [49]:
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)
Out[49]:
<matplotlib.collections.PathCollection at 0x7fd7a521d828>
In [50]:
clf = LinearSVC(C=1)
clf.fit(X,y)
print("score d'entrainement:",clf.score(X,y))
plot_boundary(clf,X,y)
score d'entrainement: 1.0
In [51]:
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)
Out[51]:
<matplotlib.collections.PathCollection at 0x7fd7a50f6940>
In [83]:
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))
score d'entrainement: 0.75
score d'entrainement: 0.75
score d'entrainement: 0.75
score d'entrainement: 0.775
score d'entrainement: 0.825
score d'entrainement: 0.85
score d'entrainement: 0.85
score d'entrainement: 0.85
score d'entrainement: 0.825
score d'entrainement: 0.5
score d'entrainement: 0.85

Xor

In [53]:
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)
Out[53]:
<matplotlib.collections.PathCollection at 0x7fd7a4a87da0>
In [64]:
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)
score d'entrainement: 0.5

2- Cas non linéaire :

"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. $$

Kernels :

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.$

In [65]:
from sklearn.svm import SVC
#http://scikit-learn.org/stable/modules/generated/sklearn.svm.SVC.html

Questions :

a) Générer des données d'entrainement non linéairement séparable puis les afficher avec les couleurs. On peut utiliser :

  • from sklearn.datasets import make_moons
  • X, y = make_moons(noise = 0.1)

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\_$

In [66]:
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)
/home/thomas/anaconda3/lib/python3.4/site-packages/sklearn/datasets/samples_generator.py:612: DeprecationWarning: using a non-integer number instead of an integer will result in an error in the future
  y = np.hstack([np.zeros(n_samples_in, dtype=np.intp),
Out[66]:
<matplotlib.collections.PathCollection at 0x7fd7a49acac8>
In [67]:
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)
/home/thomas/anaconda3/lib/python3.4/site-packages/sklearn/datasets/samples_generator.py:612: DeprecationWarning: using a non-integer number instead of an integer will result in an error in the future
  y = np.hstack([np.zeros(n_samples_in, dtype=np.intp),
Out[67]:
<matplotlib.collections.PathCollection at 0x7fd7a609bb00>
In [92]:
#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='*')
score d'entrainement: 0.775 . score de test: 0.78
score d'entrainement: 0.775 . score de test: 0.78
score d'entrainement: 0.825 . score de test: 0.82
score d'entrainement: 0.825 . score de test: 0.86
score d'entrainement: 0.85 . score de test: 0.87
score d'entrainement: 0.85 . score de test: 0.87
score d'entrainement: 0.85 . score de test: 0.87
score d'entrainement: 0.85 . score de test: 0.87
In [90]:
#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='*')
score d'entrainement: 0.75 . score de test: 0.74
score d'entrainement: 0.75 . score de test: 0.74
score d'entrainement: 0.8 . score de test: 0.85
score d'entrainement: 0.9 . score de test: 0.94
score d'entrainement: 1.0 . score de test: 0.99
score d'entrainement: 1.0 . score de test: 1.0
score d'entrainement: 1.0 . score de test: 1.0
score d'entrainement: 1.0 . score de test: 1.0