SVM et les réseaux de neurones : classification binaire

Théorie : Exercices :

Cas linéairement séparables

Les SVM simples séparent des clusteurs de données linéairement séparables en créant une frontière (appelée hyperplan) entre ceux-ci. Les SVM sont des classificateurs à sortie binaire, ils permettent donc de discriminer deux classes (ou deux clusters). Plus formellement, un SVM construit une fonction $h$ qui fait correspondre des échantillons $x$ vers un sortie $y$ : $$y = h(x)$$ La fonction $h$ est un vecteur de poids $w = (w_1, ..., w_N)$ où $N$ est la dimension du vecteur représentant un échantillon. La fonction peut alors s'écrire : $$ h(x) = w^T x - b$$ où $x \in \mathbb{R}^N$ et $b$ représente l'offset de la marge. Il est alors décidé que $x$ est de classe 1 si $h(x)\geq 0$ et de classe -1 sinon. L'hyperplan est la fonction $h$ lorsqu'elle vaut 0. Les SVM utilisent l'algorithme d'optimisation minimal séquentiel pour affiner leurs poids et leurs biais.

Dans l'exemple suivant, nous classifions des données linéairement séparables.

Théorème : Soit $X_{0}$ et $X_{1}$ deux clusters de points dans un espace euclidien de dimension $N$. Alors $X_{0}$ et $X_{1}$ sont linéairement séparables si il existe $n+1$ nombres $w_{1}, w_{2},..,w_{n}, k$ tel que chaque point $x \in X_{0}$ satisfasse $\sum^{n}_{i=1} w_{i}x_{i} > k$ et chaque point $x \in X_{1}$ satisfait $\sum^{n}_{i=1} w_{i}x_{i} < k$, où $x_{i}$ est la $i$-ème composante de $x$.

In [*]:
import numpy as np
import matplotlib
import matplotlib.pyplot as plt
from sklearn import svm
from sklearn.datasets import make_blobs

# we create 40 separable points
X, y = make_blobs(n_samples=40, centers=2, random_state=6)
plt.scatter(X[:, 0], X[:, 1], c=y, cmap=plt.cm.Paired)
Out[*]:
<matplotlib.collections.PathCollection at 0x7f7fa1667ef0>

Nous disposons de plusieurs points $x \in \mathbb{R}^N, N=2$ distribués selon deux clusters. Le théorème précédent nous indique que nous devrions trouver une solution avec un poid $w$ composé de seulement deux nombres. Avec sklearn, on peut facilement trouver l'hyperplane $h$ et ses vastes marges. Les points $x$ présents sur la vaste marge s'appellent les vecteurs de supports.

In [ ]:
# fit the model
clf = svm.SVC(kernel='linear')
clf.fit(X, y)

#plot the points
plt.scatter(X[:, 0], X[:, 1], c=y, cmap=plt.cm.Paired)

def plot_svc_decision_function(model, ax=None, plot_support=True):
    """Plot the decision function for a 2D SVC"""
    if ax is None:
        ax = plt.gca()
    xlim = ax.get_xlim()
    ylim = ax.get_ylim()

    # create grid to evaluate model
    x = np.linspace(xlim[0], xlim[1], 30)
    y = np.linspace(ylim[0], ylim[1], 30)
    Y, X = np.meshgrid(y, x)
    xy = np.vstack([X.ravel(), Y.ravel()]).T
    P = model.decision_function(xy).reshape(X.shape)

    # plot decision boundary and margins
    ax.contour(X, Y, P, colors='k',
               levels=[-1, 0, 1], alpha=0.5,
               linestyles=['--', '-', '--'])

    # plot support vectors
    if plot_support:
        ax.scatter(model.support_vectors_[:, 0],
                   model.support_vectors_[:, 1],
                   s=300, linewidth=1, facecolors='none', edgecolors='k')
    ax.set_xlim(xlim)
    ax.set_ylim(ylim)

plot_svc_decision_function(clf, plot_support=True)
plt.show()

On peut désormais faire des prédictions avec le modèle sklearn. On peut bien sûr utiliser la fonction predict(), mais on peut aussi directement utiliser la matrice de poids $w$ et le biais $b$ qui projette nos points $x$ vers la classe $y$. Les poids peuvent être obtenus en utilisant l'attribut coef_ du modèle et le biais via l'attribut intercept_. Le code suivant réalise une prédiction avec le point $x[0]$ et la fonction predict() ou avec la matrice de poids $\begin{bmatrix} -0.2539\\ -0.8380 \end{bmatrix}$ et le biais $-3.2113$.

In [*]:
input = X[0].reshape(1,-1) #reshaping example from (2,) to (1,2)
weights = clf.coef_.reshape (-1,1) #reshaping weights from (2,1) to (1,2)

print("weights", weights)
print("biais", clf.intercept_)
print("Prediction sklearn", clf.predict(input))

projection = np.matmul(input,weights) #Matrix multiplication 1,2 x 2,1; ok
print("Projection:",projection+clf.intercept_)
if projection >= 1:
    print("Classe 1")
else:
    print("Classe 0")

weights [[-0.2539717 ]
 [-0.83806387]]
biais [-3.21132826]
Prediction sklearn [1]
Projection: [[4.06514436]]
Classe 1

Exercice : imprimez les trois vecteurs de supports $x$ qui se trouvent sur les marges

Un réseau de neurones (Neural Network, NN) est composé de plusieurs couches de perceptrons. Le perceptron (ou neurone) est vu comme l'unité la plus petite d'un NN.


Définition : Un perceptron à $n$ entrées $(x_1,\dots,x_n)$ et à une seule sortie $y$ est défini par l'ensemble de $n$ poids $w$ (ou coefficients synaptiques) $(w_1,\dots,w_n)$ et un biais $b$. La sortie est calculée comme suit : $\sum_{i=1}^n w_i x_i$.
Nous remarquons que le perceptron est donc équivalent à un svm à noyau linéaire.
Reprenons l'exercice précédent et utilisons un perceptron. Pour le faire, nous allons utiliser la librairie pytorch.

In [*]:
import torch.nn as nn
import torch
from sklearn.datasets import make_blobs
import numpy as np
import matplotlib
import matplotlib.pyplot as plt
Nous définissons le NN à l'aide d'une classe que nous nommons Net et qui possède un attribut Linear. L'objet nn.Linear définit un perceptron unique.
In [ ]:
X_cpu, y_cpu = make_blobs(n_samples=40, centers=2, random_state=6)

# transformation des inputs numpy vers torch
X = torch.from_numpy(X_cpu).cuda().float()
y = torch.from_numpy(y_cpu).cuda().float()

# network dimensions
n_input_dim = X.shape[1]
n_output = 1  # Number of output nodes = 1 for binary classifier

# Build the network
class Net(nn.Module):
    def __init__(self):
        super(Net, self).__init__()
        self.linear = nn.Linear(n_input_dim, 1)

    def forward(self, x):
        x = self.linear(x)
        return x

# appelle le constructeur
net = Net().cuda()
Nous choisissons la fonction Binary Cross Entropy comme loss, qui est adaptée pour un problème de classification binaire.
In [ ]:
loss_func = nn.BCELoss() #fonction de la loss
learning_rate = 0.03 #pas d'apprentissage
optimizer = torch.optim.SGD(net.parameters(), lr=learning_rate) # descente de gradient

num_iterations = 500
#on apprend par batch (ou paquet) de 4 exemples
batch_size = 4

for i in range(num_iterations):
    optimizer.zero_grad()

    rand = np.random.choice(X.shape[0], batch_size)
    input = X[rand]
    target = y[rand]

    # forward pass
    prob = net(input)
    #calcul de la loss
    loss = loss_func(torch.sigmoid(prob), target.reshape(-1,1))

    #mis à jour du réseau
    loss.backward()
    optimizer.step()

    #print de la loss
    if i%10==0:
        print("Iter {} - loss: {:.2f}".format(i,loss.item()))

Iter 0 - loss: 2.36
Iter 10 - loss: 1.63
Iter 20 - loss: 1.23
Iter 30 - loss: 0.71
Iter 40 - loss: 0.26
Iter 50 - loss: 0.02
Iter 60 - loss: 0.00
Iter 70 - loss: 0.01
Iter 80 - loss: 0.00
Iter 90 - loss: 0.00

Attention : En fonction des poids du perceptron, la sortie du NN peut avoir toute une étendue de valeurs, il ne prédit pas que des 0 et des 1. Les prédictions d'un réseau de neurones ne sont pas binaires tel que "je suis certain que ce point est de la classe 1". Plutôt, le réseau dit "je suis sûr à 75% que ce point appartient à la classe 1". Cette distinction est cruciale car si on ne prédit que des 0 et des 1, il n'y a pas de nuance ou de marge de progression. On a seulement tort ou raison. Mais en sortant des probabilités, il y a de l'espace pour s'améliorer. On peut modifier et ajuster le système pour qu'il aille dans une direction plutôt qu'une autre. La procédure d'apprentissage devient donc un processus controlé et incrémental. C'est pour cela que dans cet exercice, le NN est mis à jour par paquets (batch) de 4 exemples via une descente de gradient (c.f. prochain chapitre). Pour traduire la sortie du NN en termes de probabilités, nous utilisons la fonction sigmoïde, aussi appelée logistique. Cette fonction "écrase" ses entrées entre 0 et 1.

sigmoid

In [*]:
x_min, x_max = X_cpu[:, 0].min() - 1, X_cpu[:, 0].max() + 1
y_min, y_max = X_cpu[:, 1].min() - 1, X_cpu[:, 1].max() + 1

spacing = min(x_max - x_min, y_max - y_min) / 100


xx, yy = np.meshgrid(np.arange(x_min, x_max, spacing),
                     np.arange(y_min, y_max, spacing))

input = torch.from_numpy(np.c_[xx.ravel(), yy.ravel()]).cuda().float()

Z = net(input)

Z = Z.detach().cpu().numpy()
# Put the result into a color plot
Z = Z.reshape(xx.shape)
Z = np.where(Z<0.5,0,1)

cmap = matplotlib.colors.ListedColormap(["lightgrey","skyblue"])
plt.contourf(xx, yy, Z, cmap=cmap)

plt.axis('off')

# Plot also the training points
plt.scatter(X_cpu[:, 0], X_cpu[:, 1], c=y_cpu, facecolors='none', edgecolors='k')
plt.show()
En résumé, nous remarquons que la forme de la fonction apprise par le perceptron et le SVM linéaire est similaire. La différence réside dans la manière de mettre à jour les poids du modèle : la descente de gradient stochastique (SGD) pour le perceptron et l'optimisation minimale séquentiele pour les SVM.
Similarité : Différence :

Exercice : Jouez avec le batch-size et le pas d'apprentissage pour expérimenter la sensibilité du modèle

Cas linéairement non-séparables

Considérons maintenant un dataset qui n'est pas linéairement séparable et réessayons le SVM avec noyau linéaire :
In [4]:
from sklearn.datasets.samples_generator import make_circles
X, y = make_circles(100, factor=.1, noise=.1)

clf = SVC(kernel='linear').fit(X, y)

plt.scatter(X[:, 0], X[:, 1], c=y, s=50, cmap=plt.cm.Paired)
plot_svc_decision_function(clf, plot_support=False)
plt.show()

Pour palier à ce problème, on peut utiliser le "kernel trick". L'idée est de trouver une fonction $K(x, x^\prime)$ qui ajoute une nouvelle dimension au point $x$ pour que le problème devienne séparable. Il existe plusieurs noyaux tels que le polynomial, sigmoïde ou RBF (radial basis function). Le noyau RBF est le suivant : $$K(\mathbf{x}, \mathbf{x'}) = \exp\left(-\frac{\|\mathbf{x} - \mathbf{x'}\|^2}{2\sigma^2}\right)$$ et peut être utilisé facilement pour créer une nouvelle dimension.

Exercice : Sans utiliser sklearn, implémentez le noyau RBF dans le code suivant pour créer une troisième dimension.

In [*]:
from sklearn.datasets.samples_generator import make_circles
from ipywidgets import interact, fixed

X, y = make_circles(100, factor=.1, noise=.1)
r = #implémenter la fonction qui prend X en entrée

def plot_3D(elev=30, azim=30, X=X, y=y):
    ax = plt.subplot(projection='3d')
    ax.scatter3D(X[:, 0], X[:, 1], r, c=y, s=50, cmap=plt.cm.Paired)
    ax.view_init(elev=elev, azim=azim)
    ax.set_xlabel('x')
    ax.set_ylabel('y')
    ax.set_zlabel('r')

interact(plot_3D, elev=(-90, 90), azip=(-180, 180),
         X=fixed(X), y=fixed(y))

Il est désormais possible de trouver l'hyperplan pour séparer les données :

In [*]:
X, y = make_circles(100, factor=.1, noise=.1)
clf = svm.SVC(kernel='rbf', gamma="auto")
clf.fit(X, y)
plt.scatter(X[:, 0], X[:, 1], c=y, s=50, cmap=plt.cm.Paired)
plot_svc_decision_function(clf)
plt.scatter(clf.support_vectors_[:, 0], clf.support_vectors_[:, 1],
            s=300, lw=1, facecolors='none')
plt.show()
Le kernel $K$ est une fonction non-linéaire. Alors qu'un perceptron (ou noyau linéaire pour le SVM) "étend" ou "écrase" l'espace euclidien, les fonctions non-linéaires ont la propriété de les "couper", de les "casser" ou de les "plier". En effet, on peut voir que le noyau RBF a "plié" l'espace pour mettre les points du cercle central en hauteur.
Proposition : Un réseau de neurones est incapable de classifier ce dataset sans fonction non-linéaire et sans une couche de trois neurones minimum, peu importe le nombre de couches qu'il possède.
Nous pouvons reprendre le code utilisé précédemment et modifier le NN pour lui ajouter une couche cachée de trois neurones, suivi d'une non-linéarité, en l'occurence une tangente hyperbolique (tanh) qui est une fonction non-linéaire qui projette son entrée entre -1 et 1.
In [60]:
X_cpu, y_cpu = make_circles(100, factor=.1, noise=.1)

# network dimensions
n_input_dim = X.shape[1]
n_output = 1  # Number of output nodes = 1 for binary classifier

# Build the network
class Net(nn.Module):
    def __init__(self):
        super(Net, self).__init__()

        self.fc1 = nn.Linear(n_input_dim, 3)
        self.tanh = nn.Tanh()
        self.fc2 = nn.Linear(3, 1)

    def forward(self, x):
        x = self.tanh(self.fc1(x))
        x = self.fc2(x)
        return x

net = Net().cuda()

loss_func = nn.BCELoss() #fonction de la loss
learning_rate = 0.1 #pas d'apprentissage
optimizer = torch.optim.SGD(net.parameters(), lr=learning_rate) # descente de gradient

num_iterations = 10000
batch_size = 32

for i in range(num_iterations):
    ...

Iter 0 - loss: 0.68
Iter 100 - loss: 0.70
Iter 200 - loss: 0.71
Iter 300 - loss: 0.67
Iter 400 - loss: 0.66
Iter 500 - loss: 0.59
Iter 600 - loss: 0.54
Iter 700 - loss: 0.42
Iter 800 - loss: 0.37
Iter 900 - loss: 0.44
Iter 1000 - loss: 0.33
Iter 1100 - loss: 0.27
Iter 1200 - loss: 0.26
...
Iter 9800 - loss: 0.01
Iter 9900 - loss: 0.01
Il est donc important de comprendre quel noyau on utilise : selon la proposition, une simple non-linéarité ne suffit pas. On peut en effet le vérifier avec le noyau sigmoïdal $K$ défini par la fonction : $$ K(x, x^\prime) = \tanh(\alpha x^Tx^\prime + c)$$ qui équivaut à un unique peceptron à deux couches. Il ne remplit donc pas les conditions de la proposition. Nous pouvons facilement le vérifier avec la librairie sklearn :
In [*]:
X, y = make_circles(100, factor=.1, noise=.1)
clf = svm.SVC(kernel='sigmoid', gamma="auto")
clf.fit(X, y)
plt.scatter(X[:, 0], X[:, 1], c=y, s=50, cmap=plt.cm.Paired)
plot_svc_decision_function(clf)
plt.scatter(clf.support_vectors_[:, 0], clf.support_vectors_[:, 1],
            s=300, lw=1, facecolors='none')
plt.show()
Similarités : Différence :

Exercice : jouez avec l'application suivante : http://playground.tensorflow.org/. Trouvez les configurations minimales pour classifier les différents datasets. Ajoutez et enlevez des couches ou des non-linéarités et analysez l'impact sur les convergences.


Un dernier point très important est à noter. Un SVM garantit de converger vers la solution optimale (qu'elle soit bonne ou mauvaise). En effet, la solution d'un SVM est globale et unique. Le SVM est une technique statistique qui se base sur des principes théoriques fondés et éprouvés. Les réseaux de neurones sont heuristiques et souffrent d'avoir des minima locaux dans lesquels l'apprentissage peut s'engouffrer, sans trouver l'optimal global. Le NN cherche à tracer une ligne entre les points des exemples sur lesquels il est entrainé, mais cette dernière n'aura peut-être pas une généralisation adéquate pour d'autre exemples non-vus. Vous pouvez d'ailleurs vérifier en relançant les scripts : le SVM vous donnera toujours la même solution, à l'inverse des NN.

Similarités : Différences :