Ben LAHMAR El Habib

 Introduction

Machine à Vecteurs de Support (SVM) est lui aussi un algorithme de classification binaire. Tout comme la régression logistique. 

Les Support Vector Machines souvent traduit par l’appellation de Séparateur à Vaste Marge (SVM) sont une classe d’algorithmes d’apprentissage initialement définis pour la discrimination c’est-à-dire la prévision d’une variable qualitative binaire. Ils ont été ensuite généralisés à la prévision d’une variable quantitative. Dans le cas de la discrimination d’une variable dichotomique, ils sont basés sur la recherche de l’hyperplan de marge optimale qui, lorsque c’est possible, classe ou sépare correctement les données tout en étant le plus éloigné possible de toutes les observations. Le principe est donc de trouver un classifieur, ou une fonction de discrimination, dont la capacité de généralisation (qualité de prévision) est la plus grande possible.

Avant de commencer essayons de comprendre c'est quoi un hyperplan?

Dans un espace de dimension 2 un hyperplan est une ligne

B₀+B₁X₁+B₂X₂=0

Tant que dans un espace de dimension N l'équation devient

B₀+B₁X₁+B₂X₂+…+B_mX_m=0

un hyperplan devise l'espace en deux parties

B₀+B₁X₁+B₂X₂+…+B_mX_m< 0, and

B₀+B₁X₁+B₂X₂+…+B_mX_m> 0

 

 

 

Par contre comme vous pouvez remarqué il existe plusieurs alternatives pour deviser cet espace en deux parties

Il est évident donc qu’il existe une multitude d’hyperplan valide mais la propriété remarquable des SVM est que cet hyperplan doit être optimal.  l'idée donc est  de chercher parmi les hyperplans valides, celui qui passe « au milieu » des points des deux classes d’exemples.

le but de SVM est donc de trouver un classificateur qui va séparer les données et maximiser la distance entre ces deux classes. Avec SVM, ce classificateur est un classificateur linéaire appelé hyperplan.

 

 

 

 Formellement, cela revient à chercher un hyperplan dont la distance minimale aux exemples d’apprentissage est maximale.  

il est claire que la frontière la plus éloignée de tous les points d’entraînement qui est optimale, on dit qu’elle a la meilleure capacité de généralisation. Ainsi, le but d’un SVM est de trouver cette frontière optimale, en maximisant la distance entre les points d’entraînement et la frontière.

On appelle cette distance « marge » entre l’hyperplan et les exemples. L’hyperplan séparateur optimal est celui qui maximise la marge. Comme on cherche à maximiser cette marge, on parlera de séparateurs à vaste marge. Les points les plus proches, qui seuls sont utilisés pour la détermination de l’hyperplan, sont appelés vecteurs de support.

maximiser la marge! mais pourquoi ?

le fait d'avoir une marge plus large procure plus de garantie lorsque l'on classe un nouvel exemple. De plus, si l’on trouve le classificateur qui se comporte le mieux vis-à-vis des données d'apprentissage, il est clair qu’il sera aussi celui qui permettra au mieux de classer les nouveaux exemples. Dans le schéma qui suit, la partie droite nous montre qu'avec un hyperplan optimal, un nouvel exemple reste bien classé alors qu'il tombe dans la marge. On constate sur la partie gauche qu'avec une plus petite marge, l'exemple se voit mal classé.

 

les modèles linéairement séparable et non linéairement séparable.

Parmi les modèles des SVM, on constate les cas linéairement séparable et les cas non linéairement séparable. Les premiers sont les plus simple de SVM car ils permettent  de trouver facilement le classificateur linéaire. Dans la plupart des problèmes réels il n’y a pas de séparation linéaire possible entre les données, le classificateur de marge maximale ne peut pas être utilisé car il fonctionne seulement si les classes de données d’apprentissage sont linéairement séparables.

 

 

 

 

Puisque les ronds sont entourés des étoiles de toute part, il est impossible de trouver de ligne droite qui soit une frontière : on dit que les données d’entraînement ne sont pas linéairement séparables. Cependant, imaginez qu’on arrive à trouver une transformation qui fasse en sorte que notre problème ressemble à ça :

A partir de là, il est facile de trouver une séparation linéaire. Il suffit donc de trouver une transformation qui va bien pour pouvoir classer les objets. Cette méthode est appelée kernel trick, (astuce du noyau). et donc  toute la difficulté est de trouver la bonne transformation.

Pour surmonter les inconvénients des cas non linéairement séparable, l’idée des SVM est de changer l’espace des données. La transformation non linéaire des données peut permettre une séparation linéaire des exemples dans un nouvel espace. On va donc avoir un changement de dimension. Cette nouvelle dimension est appelé « espace de re-description ». En effet, plus la dimension de l’espace de re-description est grande, plus la probabilité de pouvoir trouver un hyperplan séparateur entre les exemples est élevée. Ceci est illustré par le schéma suivant :

 

 

On a donc une transformation d’un problème de séparation non linéaire dans l’espace de représentation en un problème de séparation linéaire dans un espace de re-description de plus grande dimension. Cette transformation non linéaire est réalisée via une fonction noyau. En pratique, quelques familles de fonctions noyau paramétrables sont connues et il revient à l’utilisateur de SVM d’effectuer des test pour déterminer celle qui convient le mieux pour son application. On peut citer les exemples de noyaux suivants : polynomiale, gaussien, sigmoïde et laplacien.

Par exemple la passage de 1 vers 2 est fait via la transformation: z=x²+y². 

 

 

 Formalise des SVM

De façon plus générale que dans les exemples donnés précédemment, les SVM ne se bornent pas à séparer des points dans le plan. Ils peuvent en fait séparer des points dans un espace de dimension quelconque.  Ils peuvent en fait séparer des points dans un espace de dimension quelconque. Par exemple, si on cherche à classer des employés parleurs  rendement, alors que l'on connait leur date d'embauche, le nombre de projets ou ils contribuent , le nombre des jours de par projets et le délai du projets, on travaillera en dimension 4. un autre exemple:  si on cherche à classer des fleurs par espèce, alors que l’on connaît leur taille, leur nombre de pétales et le diamètre de leur tige, on travaillera en dimension 3.  un autre exemple est celui de la reconnaissance d’image : une image en noir et blanc de 28*28 pixels contient 784 pixels, et est donc un objet de dimension 784. Il est ainsi courant de travailler dans des espaces de plusieurs milliers de dimensions.

Dans un espace vectoriel de dimension finie n, un hyperplan est un sous-espace vectoriel de dimension n-1. Ainsi, dans un espace de dimension 2 un hyperplan sera une droite, dans un espace de dimension 3 un hyperplan sera un plan, etc.

Soit l’espace vectoriel E de dimension n, doté de la base (e1,…,en). L’équation caractéristique d’un hyperplan est de la forme w₁e₁+w₂e₂+...+w_ne_n=0

en dimension 2, munie la base usuelle (x,y), ax+by=0 est bien l’équation caractéristique d’une droite vectorielle (qui passe par l’origine).

un hyperplan vectoriel passe toujours par 0. C’est pour cette raison qu’on utilisera un hyperplan affine, qui n’a pas quant à lui obligation de passer par l’origine.

Ainsi, si l’on se place dans Rn muni de la base (e1,…,en), pendant son entraînement le SVM calculera un hyperplan vectoriel d’équation w₁e₁+w₂e₂++w_ne_n, ainsi qu’un scalaire (un nombre réel) b. C’est ce scalaire b qui va nous permettre de travailler avec un hyperplan affine, comme nous allons le voir.

Le vecteur w= est appelé vecteur de poids, le scalaire b est appelé biais.

Une fois l’entraînement terminé, pour classer une nouvelle entrée x de Rⁿ, le SVM regardera le signe de :

h(x)=w₁a₁+…+w_na_n+b=∑ w_ia_i+b=wx+b

Si h(x) est positif ou nul, alors xx est d’un côté de l’hyperplan affine et appartient à la première catégorie, sinon xx est de l’autre côté de l’hyperplan, et donc appartient à la seconde catégorie.

En résumé, on souhaite savoir, pour un point x, s’il se trouve d’un côté ou de l’autre de l’hyperplan. La fonction h nous permet de répondre à cette question, grâce à la classification suivante :

                           {

                                  h(x)≥0x classe 1

                                  h(x)<0 x classe 2

                           }

 

A suivre…