On préférerait classifier en regardant
\(signe(ax+b)\).
Questions :
Comment définir une “bonne” séparation linéaire ?
Comment trouver cette séparation ?
Quelles sont les limites ?
Convention
Aujourd’hui, classification binaire :
Deux classes : \(\{-1,1\}\)
Jeux de données \(D =
\{d^{(1)},\dots,d^{(m)}\}\) où \(d^{(i)} = (\mathbf{x}^i,y^i)\) et \(\mathbf{x}^i = (x^i_1,\dots,x^i_n)\)
features et classe \(y^i \in
\{-1,1\}\).
Fonction \(signe(x) = 1\) si \(x \geq 0\) et \(signe(x) = -1\) si \(x<0\).
Séparation linéaire: trouver \(\mathbf{w}= (w_1,\dots,w_{n})\) tels que
pour tout \((\mathbf{x},y) \in D\),
\[signe(\mathbf{w}^T \mathbf{x}) =
signe(\sum_{i=1,..n} w_i x_i) = y\]
Séparation linéaire vs affine
En dimension \(1\): pour \((x,y)\), on cherche \(w\) tel que \(signe(wx) = y\).
Et si on cherche \(w_1, w_2\) tels
que \(signe(w_1x+w_2) = y\) ?
On se ramène juste au cas en dimension 2 en prenant : \(\mathbf{x}= (x,1)\) pour tout \((x,y)\) du jeu de données.
Dans ce cas, en effet : \((w_1,w_2)^T
\times (x,1) = w_1x+w_2\).
Séparation linéaire en dimension \(n\): hyperplan
Si \(\mathbf{w}= (w_1,\dots,w_n)\)
et \(\mathbf{x}= (x_1,\dots,x_n)\), on
a \(\mathbf{w}^T \mathbf{x}= \sum_{i} w_i
x_i\).
On sépare en : \(\mathbf{w}^T
\mathbf{x}< 0\) et \(\mathbf{w}^T
\mathbf{x}> 0\).
C’est un hyperplan : une droite en dimension \(2\), un plan en dimension \(3\).
Un hyperplan en dimension 3Un hyperplan en dimension 3
Séparation par régression
Principe
Pour \(S = \{((\mathbf{x}^1,y^1), \dots,
(\mathbf{x}^m, y^m)\}\), on cherche \(\mathbf{w}\) minimisant \[E(\mathbf{w}; S) = \sum_{j=1..m}
(\mathbf{w}^T\mathbf{x}^j-y^j)^2\]
On minimise une erreur.
Trouve naturellement un séparateur.
Exemple
Minimiser l’erreur
On cherche \(\mathbf{w}\) tel que
\(E(\mathbf{w}; S)\) est
minimal.
Résolution mathématique possible dans ce cas, mais cela dépend de
\(E\).
Algorithme plus général : descente de gradient
(voir cours de math pour les détails).
Pour \(f(a_1,\dots,a_k)\), le
gradient de \(f\) est \(\Delta f = ({\partial f \over \partial a_1},
\dots, {\partial f \over \partial a_k})\).
Jusqu’à ce qu’on soit satisfait, \(\mathbf{a}^{t+1} = \mathbf{a}^t-\delta \cdot
(\Delta f)(\mathbf{a}^t)\) où \(\delta\) est un “pas” bien choisi.
Si \(\delta\) est bien choisi et
\(f\) suffisamment régulière, cette
procédure converge vers un minimum local de \(f\) (et un minimum global quand \(f\) est convexe).
Descente de gradient pour la régression
\(E(\mathbf{w}; S)\) depends on
variables \(\mathbf{w}= w_1,\dots,
w_n\)
Gradient : \(\Delta E = ({\partial E \over
\partial w_1},\dots,{\partial E \over \partial w_n})\)
\({\partial E \over \partial w_1} =
2(w_1+2w_2-1)w_1 - 2(-w_1+2w_2+1)w_1\)
\({\partial E \over \partial w_2} =
2\cdot2(w_1+2w_2-1)w_2 + 2\cdot 2(-w_1-2w_2+1)w_2\)
Donc \(\Delta E\) en \(\mathbf{w}^0=(1,-1)\) donne \((0,16)\). En prenant \(\delta = 0.1\), on définit \(\mathbf{w}^1 = \mathbf{w}^0 + (0, 1.6) = (1,
0.6)\)
Trop de données ?
\(\Delta E\) dépend de l’ensemble
des points du jeu de données :
La mise à jour est complexe quand il y a beaucoup de données.
Peut générer des gradients très grands (eg dans le cas de l’erreur
quadratique).
On utilise une méthode différentes : le gradient stochastique.
Gradient stochastique
Mini-batch: on sépare les données \(S\) en mini-batches\(B_1,\dots,B_k\) avec \(|S_i|=b\) (un paramètre du problème).
Epoch: On fait \(k\) descentes de gradient avec \(E(\mathbf{w}; B_i)\) pour \(i=1, ... k\).
On répète cela pour \(e\)
epochs.
Critiques de la régression linéaire
Pour la classification, la régression linéaire n’est ici pas optimale
:
La droite va être attirée vers les points extrêmes plutôt qu’être
centrée.
Les termes \((\mathbf{w}^T \mathbf{x}-
y)^2\): pas de signification précise de cette valeur.
SVM
SVM?
“Support Vector Machine”, séparateurs à larges marges.
On cherche à séparer les données avec la plus large bande possible
:
Notion de marge
Distance de \(x\) à l’hyperplan \(\mathbf{w}^T\mathbf{x}=0\)
La distance entre \(\mathbf{x}\) et
l’hyperplan est \(d(\mathbf{x},\mathbf{w}) =
{|\mathbf{w}^T\mathbf{x}| \over \|\mathbf{w}\|}\) où \(\|\mathbf{w}\| = \sqrt{\sum_i w_i^2}\)
(voir cours de cet AM).
si \(y\) est bien classé, c’est la
distance, et \(\geq 0\).
Sinon c’est son opposé et \(\leq
0\).
Trouver la vaste marge
Si \(y \times \mathbf{w}^T\mathbf{x}>
0\) pour tout \((\mathbf{x},y) \in
S\), alors on sépare bien \(S\).
On veut que \(\mathbf{w},b\) soit
loin, alors on va demander \(y \times (\mathbf{w}^T\mathbf{x}+b) \geq
1\).
Si \(y \times \mathbf{w}^T\mathbf{x}>
\epsilon \geq 0\), alors on peut prendre \(\mathbf{w}_0 = {\mathbf{w}\over
\epsilon}\)
On a \(\mathbf{w}_0^T\mathbf{x}= {1 \over
\epsilon}\mathbf{w}^T\mathbf{x}\geq 1\)
Par contre \(\|w_0\| \geq
\|w\|\).
Donc pour trouver un séparateur avec une marge optimal, on veut
résoudre le problème suivant :
\(\min \|\mathbf{w}\|\) tel que pour
tout \((\mathbf{x},y) \in S\)
\(y \times \mathbf{w}^T\mathbf{x}\geq
1\).
\(\mathbf{w}\mapsto \|\mathbf{w}\|\)
est convexe et \(y \times
\mathbf{w}^T\mathbf{x}\) sont des contraintes linéaires donc on a
des outils pour trouver une solution optimale (optimisation
convexe).
Marges douces
L’approche précédente ne permet pas de trouver un bon SVM lorsque le
jeu de données n’est pas linéairement séparable.
On relâche la séparation avec une erreur \(e_i\) pour chaque \((\mathbf{x}^i,y^i) \in S\)
\(\min \|\mathbf{w}\|+C \sum_i e_i\)
tel que pour tout \((\mathbf{x}^i,y^i) \in
S\)
