2.3. LES ALGORITHMES DE MACHINE LEARNING CHAPITRE 2.
REVUE DE LA LITTÉRATURE
Mémoire de Master II en Informatique 33 c~NJAMEN M.
ZELKIF 2020-2021
2.3.5.3 Cas linéairement séparable
Considérons « l » points
{(x1, y1),
(x2, y2), ...,
(xi, yi)}, xi E RN
Avec i = 1...L et yi E {#177;1}
Ces points sont classés en utilisant une famille de
fonctions linéaires définis par :
(w,x) + b = 0 (Eq 1)
avec w E RN et b E
R de telle sorte que la fonction de décision concernant
l'apparte-nance d'un point à l'une des deux classes soit donnée
par :
f(x) = ((w,x) + b) (Eq 2)
La fonction (Eq 1) représente l'équation de
l'hyperplan H. La fonction de décision (Eq 2) va donc observer de quel
côtéde H se trouve l'élément de x.
On appelle la marge d'un élément la distance
euclidienne prise perpendiculairement entre H et x. Si on prend un
point quelconque t sur H, cette marge peut s'exprimer en :
Mx = w
1w11(x - t) (Eq 3)
La marge de toutes les données est définie comme
étant :
M = minxEEMx (Eq 4)
L'approche de classification par SVM tend à maximiser
cette marge pour séparer le plus clairement possible deux classes.
Intuitivement, avoir une marge la plus large possible sécurise mieux le
processus d'affectation d'un nouvel élément à l'une des
classes. Un SVM fait donc partie des classificateurs à marge
maximale.
Dans le cas simple linéairement séparable il
existe de nombreux hyperplans séparateurs. Selon la théorie de
Vapnik [26], l'hyperplan optimal est celui qui maximise la marge. Cette
dernière étant définie comme la distance entre un
hyperplan et les points échantillons les plus proches. Ces points
particuliers sont les vecteurs supports. La distance entre un point x
quelconque et l'hyperplan est donnée par l'équation suivante.
d(x) =
w.x+b
kwk (Eq 5)
2.3. LES ALGORITHMES DE MACHINE LEARNING CHAPITRE 2.
REVUE DE LA LITTÉRATURE
Donc maximiser la marge va revenir à minimiser
MwM.
1. Forme Primale :
Les paramètres w et b étant
définis à un coefficient multiplicatif près, on choisit de
les normaliser pour que les échantillons les plus proches
(xs) vérifient l'égalitésuivante :
ys(w.xs + b) = 1 (Eq 6).
Donc quelque soit l'échantillon xi on obtient
:
yi(w.xi + b) ~ 1 (Eq 7).
La distance entre l'hyperplan et un point support est donc
définie par1
kwk. La marge
géométrique entre deux classes est égale
à2
kwk. La forme primale (qui dépend seulement
de w et b ) des SVM est donc un
problème de minimisation sous contrainte qui s'écrit :
?
???
???
|
min(1
2MwM2)
V(xi,yi) EAR, yi(w.xi + b) ~
1
|
(Eq 8)
|
|
| 
