Remerciez-le!

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

Support Vector Machines Support Vector Machines S´ eparateurs ` a vaste marge A

Support Vector Machines Support Vector Machines S´ eparateurs ` a vaste marge Arnaud Revel revel.arnaud@gmail.com Support Vector Machines Plan 1 Introduction 2 Formalisation 3 Utilisation des noyaux 4 Cas multi-classes 5 Applications des SVM 6 Bibliographie Support Vector Machines Introduction Plan 1 Introduction 2 Formalisation Cas s´ eparable Cas non-s´ eparable 3 Utilisation des noyaux 4 Cas multi-classes 5 Applications des SVM 6 Bibliographie Support Vector Machines Introduction Qu’est-ce que l’apprentissage ? En psychologie Toute acquisition d’un nouveau comportement ` a la suite d’un entraˆ ınement : habituation, conditionnement... En neurobiologie Modiﬁcations synaptiques dans des circuits neuronaux : r` egle de Hebb, r` egle de Rescorla et Wagner... Apprentissage automatique construire un mod` ele g´ en´ eral ` a partir de donn´ ees particuli` eres But pr´ edire un comportement face ` a une nouvelle donn´ ee approximer une fonction ou une densit´ e de probabilit´ e Support Vector Machines Introduction Formalisation Soit un ensemble d’apprentissage S = {(xi, yi)}1..n dont les ´ el´ ements ob´ eissent ` a la loi jointe P(x, y) = P(x)P(y|x) On cherche ` a approcher une loi sous-jacente f (x) telle que yi = f (xi) par une hypoth` ese hα(x) aussi proche que possible Les α sont les param` etres du syst` eme d’apprentissage. Si f (.) est discr` ete on parle de classiﬁcation Si f (.) est une fonction continue on parle alors de r´ egression Mais que veut-on dire par “aussi proche que possible” ? Support Vector Machines Introduction Calcul du risque Pour mesurer la qualit´ e d’une hypoth` ese hα on va consid´ erer une fonction de coˆ ut Q(z = (x, y), α) ∈[a, b] que l’on cherche ` a minimiser Exemple de fonction de coˆ ut Coˆ ut 0/1 : vaut 0 lorsque les ´ etiquettes pr´ evues et observ´ ees co¨ ıncident, 1 sinon : utilis´ e en classiﬁcation Erreur quadratique : (f (x) −y)2 : utilis´ e en r´ egression On cherche ` a minimiser : R(α) = R Q(z, α)dP(z) Comme on ne peut acc´ eder directement ` a cette valeur, on construit donc le risque empirique qui mesure les erreurs r´ ealis´ ees par le mod` ele : Remp(α) = 1 m Pn i=1 Q(zi, α) Mais quel est le lien entre Remp(α) et R(α) ? Support Vector Machines Introduction Th´ eorie de l’apprentissage de Vapnik (1995) Vapnik a pu montrer l’expression suivante ∀m avec une probabilit´ e au moins ´ egale ` a 1 −η : R(αm) ≤Remp(αm) + (b −a) r dVC(ln(2m/dVC) + 1) −ln(η/4) m (1) La minimisation du risque d´ epend du risque empirique un risque structurel li´ e au terme dVC qui d´ epend de la complexit´ e du mod` ele h choisi (VC-dimension a) a. Dimension de Vapnik et Chervonenkis Support Vector Machines Introduction Support Vector Machines Introduction Ainsi, si pour construire un bon mod` ele d’apprentissage, il est n´ ecessaire de : minimiser les erreurs sur la base d’apprentissage c’est le principe d’induction na¨ ıf utilis´ e dans les r´ eseaux de neurones de construire un syst` eme capable de g´ en´ eraliser correctement Support Vector Machines Introduction Support Vector Machines Introduction Revisitons le probl` eme du perceptron : Classiﬁeur lin´ eaire : y(x) = signe(w · x + b) Support Vector Machines Introduction Quel est le meilleur classiﬁeur ? : Il existe de nombreux choix possibles pour w et b : y(x) = signe(w · x + b) = signe(kw · x + k · b) (2) Support Vector Machines Formalisation Plan 1 Introduction 2 Formalisation Cas s´ eparable Cas non-s´ eparable 3 Utilisation des noyaux 4 Cas multi-classes 5 Applications des SVM 6 Bibliographie Support Vector Machines Formalisation Cas s´ eparable Notion de marge : Dans le cas s´ eparable, on va consid´ erer les points les plus pr` es de l’hyperplan s´ eparateur : vecteurs supports (support vectors). Pour tout point de l’espace des exemples, la distance ` a l’hyperplan s´ eparateur est donn´ ee par : r = |w · x + b| ||w|| (3) On appelle marge d la distance entre les 2 classes C’est cette distance d qu’on souhaiterait maximiser Support Vector Machines Formalisation Cas s´ eparable Quantiﬁcation de la marge : Pour limiter l’espace des possibles on consid` ere que les points les plus proches sont situ´ es sur les hyperplans canoniques donn´ es par : w · x + b = ±1 (4) Dans ce cas, la marge est : d = 2 ||w|| Les conditions d’une bonne classiﬁcation sont : ( w · x + b ≥1, si yi = 1 w · x + b < 1, si yi = −1 (5) Support Vector Machines Formalisation Cas s´ eparable Maximisation de la marge : Le probl` eme revient alors ` a trouver w et b tels que d = 2 ||w|| est maximale ∀(xi, yi) Sous les contraintes : ( w · x + b ≥1, si yi = 1 w · x + b < 1, si yi = −1 (6) De mani` ere ´ equivalent, le probl` eme peut s’´ ecrire plus simplement comme la minimisation de : 1 2||w||2 (7) Sous les contraintes : yi(w · x + b) ≥1, ∀i ∈[1, N] Support Vector Machines Formalisation Cas s´ eparable Maximisation de la marge : Cette minimisation est possible sous les conditions dites de “Karush-Kuhn-Tucker (KKT)” Soit le Lagrangien L : L(w, b, λ) = 1 2||w||2 −PN i=1 λi[yi(w · xi + b) −1] Les conditions de KKT sont alors : ∂L ∂w = 0, ∂L ∂b = 0, ∂L ∂λi ≥0, λj ≥0 λi[yi(w · xi + b) −1] = 0 Par ailleurs la derni` ere condition implique que pour tout point ne v´ eriﬁant pas yi(w · xi + b) = 1 le λi est nul. Les points qui v´ eriﬁent yi(w · xi + b) = 1, sont appel´ es “vecteurs supports”. Ce sont les points les plus pr` es de la marge. Ils sont sens´ es ˆ etre peu nombreux par rapport ` a l’ensemble des exemples. Support Vector Machines Formalisation Cas s´ eparable Le probl` eme dual : Le probl` eme s’exprime sous forme duale comme la minimisation de : W (λ) = N X i=1 λi −1 2 N X i=1 N X j=1 λiλjyiyj(xi · xj) (8) Fait partie des probl` emes d’optimisation quadratique pour lesquels il existe de nombreux algorithmes de r´ esolution SMO r´ esolution analytique (par 2 points), gestion eﬃcace de la m´ emoire, mais converge en un nombre d’´ etapes ind´ etermin´ e SimpleSVM facilite de la reprise a chaud, converge en moins d’´ etapes mais limitation m´ emoire LASVM utilisation en ligne, r´ esolution analytique mais solution sous optimale, plusieurs passes n´ ecessaires pour les petites bases de donn´ ees Support Vector Machines Formalisation Cas non-s´ eparable Classiﬁcation ` a marge souple : Et si les donn´ ees ne sont pas lin´ eairement s´ eparables ? L’id´ ee est d’ajouter des variables d’ajustement ξi dans la formulation pour prendre en compte les erreurs de classiﬁcation ou le bruit Support Vector Machines Formalisation Cas non-s´ eparable Classiﬁcation ` a marge souple : formulation Probl` eme original Minimiser 1 2||w||2 + C PN i=1 ξi ´ Etant donn´ e : yi(w∗· xi + b) ≥1 −ξi pour i = 1, ..., N et ξi ≥0 C est une constante permettant de contrˆ oler le compromis entre nombre d’erreurs de classement, et la largeur de la marge Probl` eme dual Minimiser L(λ) = PN i=1 λi −1 2 PN i=1 PN j=1 λiλjyiyjxi · xj Avec les contraintes 0 ≤λi ≤C Support Vector Machines Formalisation Cas non-s´ eparable Au del` a du s´ eparateur lin´ eaire Que se passe-t-il si l’ensemble d’apprentissage est intrins` equement non s´ eparable ? Pourquoi ne pas plonger le probl` eme dans un espace de plus grande dimensionnalit´ e ? Support Vector Machines Utilisation des noyaux Plan 1 Introduction 2 Formalisation Cas s´ eparable Cas non-s´ eparable 3 Utilisation des noyaux 4 Cas multi-classes 5 Applications des SVM 6 Bibliographie Support Vector Machines Utilisation des noyaux SVM non-lin´ eaires : espace de caract´ eristiques Id´ ee g´ en´ erale L’espace des donn´ ees peut toujours ˆ etre plong´ e dans un espace de plus grande dimension dans lequel les donn´ ees peuvent ˆ etre s´ epar´ ees lin´ eairement Exemple : XOR On eﬀectue la transformation : (x, y) →(x, y, x · y) (9) Dans ce cas le probl` eme peut ˆ etre s´ epar´ e lin´ eairement Support Vector Machines Utilisation des noyaux Le “kernel trick” La r´ esolution des SVM ne s’appuient que sur le produit scalaire < xi, xj > entre les vecteurs d’entr´ ee Si les donn´ ees d’apprentissage sont plong´ ees dans un espace de plus grande dimension via la transformation Φ : x →φ(x), le produit scalaire devient : K(xi, xj) =< φ(xi), φ(xj) > (10) (K(xi, xj) est appel´ ee fonction noyau) Pour faire apprendre le SVM seul le noyau est uploads/Industriel/ svm-algoritomo-classificacioin.pdf