Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

2. Classifieur SVM (Support Vecteur Machines) : 2.1. Historique : Les séparateu

2. Classifieur SVM (Support Vecteur Machines) : 2.1. Historique : Les séparateurs à vastes marges reposent sur deux idées clés : la notion de marge maximale et la notion de fonction noyau. Ces deux notions existaient depuis plusieurs années avant qu'elles ne soient mises en commun pour construire les SVM. L'idée des hyperplans à marge maximale a été explorée dès 1963 par Vladimir Vapnik et A. Lerner, et en 1973 par Richard Duda et Peter Hart dans leur livre Pattern Classification. Les fondations théoriques des SVM ont été explorées par Vapnik et ses collègues dans les années 70 avec le développement de la théorie de Vapnik-Chervonenkis, et par Valiant et la théorie de l'apprentissage PAC. L'idée des fonctions noyaux n'est pas non plus nouvelle : le théorème de Mercer date de 1909, et l'utilité des fonctions noyaux dans le contexte de l'apprentissage artificiel a été montré dès 1964 par Aizermann, Bravermann et Rozoener. Ce n'est toutefois qu'en 1992 que ces idées seront bien comprises et rassemblées par Boser, Guyon et Vapnik dans un article, qui est l'article fondateur des séparateurs à vaste marge. L'idée des variables ressorts, qui permet de résoudre certaines limitations pratiques importantes, ne sera introduite qu'en 1995. À partir de cette date, qui correspond à la publication du livre de Vapnik, les SVM gagnent en popularité et sont utilisés dans de nombreuses applications. Un brevet américain sur les SVM est déposé en 1997 par les inventeurs originels. 2.2. Présentation de SVM : Les SVMs qui sont aussi appelés : séparateurs à vaste marge (support Vector Machine) présentent une technique de classification dont l’apprentissage est supervisé. Cette technique a été introduite par le russe Vladimir Vapnik en 1995 [34]. Les SVMs reposent sur une théorie mathématique solide. Elles ont été à l’origine utilisées pour la classification binaire et la régression. Aujourd’hui, elles sont utilisées par de nombreux chercheurs et dans différents domaines tels que l’aide au diagnostic médical qui fait l’objet de notre étude, le marketing, la biologie, etc. La raison du succès de cette technique est son adaptation rapide aux BDD à grandes dimensions (big data), son nombre réduit de paramètre à régler, et ses bons résultats en pratique. [8] La technique SVM, permet de résoudre des problèmes linéairement et non linéairement séparable. Elle repose sur deux notions clés : celle de la maximisation de la marge et celle de la fonction noyau. Dans la section suivante, les principes de fonctionnement général des deux cas (linéairement et non linéairement séparable) vont être présentés. 2.3. Principes de fonctionnement général de la technique SVM : Le but de l’approche SVM est de trouver une bonne reconnaissance ainsi qu’une bonne séparation entre différentes classes. Le classifieur linéaire qui effectue une séparation de données entre les classes est appelé hyperplan. Sur la figure III.1, on détermine un hyperplan séparant deux classes (cercle bleu, et carré rouge). Figure III.1: Différents hyperplans possibles ainsi que les vecteurs de supports Les échantillons les plus proches des deux classes sont appelés les vecteurs de support. Ces derniers sont utilisés pour la détermination de l’hyperplan (partie droite de la figure). Comme la montre la figure ci-dessus, il existe une multitude d’hyperplans valides, c’est-à-dire qui assurent une séparation entre les deux classes. La principale particularité des SVMs est que l’hyperplan choisi doit être optimal. Nous allons donc en plus chercher parmi les hyperplans valides, celui qui passe au milieu des deux classes. Intuitivement, cela revient à chercher l’hyperplan le plus sûr, c’est-à- dire celui qui passe au milieu des deux classes et qui offre le maximum de précision pour une bonne classification. Formellement, cela revient à chercher un hyperplan dont la distance minimale aux exemples d’apprentissage est maximale. On appelle cette distance « marge » entre l’hyperplan et les exemples. L’hyperplan séparateur optimal est celui qui maximise la marge d’où le nom des séparateurs à vaste marge (Voir figure III.2) [8] Figure III.2: Maximisation de la marge La maximisation de la marge est réalisée dans le but d’obtenir une précision maximale lorsqu’on classe un nouvel exemple (période de test). Dans la figureIII.3 la partie gauche nous montre qu’avec un hyperplan optimal, un nouvel exemple (cercle en jaune) reste bien classé, par contre dans la partie droite où il y a une marge plus petite, le nouvel exemple se voit mal classé. Figure III.3: Choix de l’hyperplan optimal 2.3.1. Séparation linéaire et non linéaire : Il existe deux cas de séparation, les cas linéairement séparables et les cas non linéairement séparables. Le premier cas est le plus simple à réaliser mais dans la majorité des cas pratiques, très peu de problèmes peuvent être séparés d’une manière linéaire. Pour surmonter les inconvénients du deuxième cas, l’idée des SVMs est de changer l’espace des données (figure III.4). La transformation non-linéaire des données peut permettre une séparation linéaire des exemples dans un nouvel espace. On va donc procéder à un changement de dimension. Cette nouvelle dimension est appelée « espace de redescription ». En effet, plus la dimension de l’espace de redescription est grande, plus la probabilité de pouvoir trouver un hyperplan séparateur entre les exemples est élevée. [8] FigureIII.4 : Transformation d’espace Nous avons donc transformé un problème non linéairement séparable dans l’espace de représentation à deux dimensions à un cas linéairement séparable dans un espace de plus grande dimension qui est l’espace de redescription (Featuresspace). Cette transformation est réalisée via une fonction noyau (fonction Kernel). En pratique, quelques familles de fonctions noyaux paramétrables sont connues et il revient à l’utilisateur d’effectuer des tests pour déterminer celle qui convient le mieux à son application. Nous pouvons citer les exemples de noyaux suivants : Linéaire, Polynomiale, Gaussien, et Laplacien. -Le noyau linéaire : (5) -Le noyau polynomial : (6) -Le noyau gaussien : (7) -Le noyau Laplacien : (8) Dans cette partie, nous avons présenté de manière simple le concept et le fonctionnement général de la technique SVM. uploads/Ingenierie_Lourd/ classifieur-svm-support-vecteur-machines-2-1-historique.pdf