0% ont trouvé ce document utile (0 vote)

59 vues24 pages

Introduction aux Machines à Vecteurs Support

Transféré par

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

0% ont trouvé ce document utile (0 vote)

59 vues24 pages

Introduction aux Machines à Vecteurs Support

Transféré par

alaouibencherifmo

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Introduction

Séparateur linéaire
Séparateur non linéaire
Exemples

Apprentissage Machine / Statistique

Support Vector Machines (SVM)

P HILIPPE B ESSE

INSA de Toulouse
Institut de Mathématiques

INSA de Toulouse - Apprentissage Machine Machine à Vecteurs Support

Introduction Généralités
Séparateur linéaire Astuces
Séparateur non linéaire Problème
Exemples Espace intermédiaire

Principes généraux
Séparateur à Vaste Marge (SVM)
Machine à Vecteurs Support (MVS)
Apprentissage en discrimination : {-1, 1}
Etendu à m > 2 et R
Hyperplan de marge optimale pour la généralisation
Vapnik (1998) et VC-dimension
Contrôle de la complexité
L’objectif, seulement l’objectif
Coût calcul fonction de n, pas de p

INSA de Toulouse - Apprentissage Machine Machine à Vecteurs Support

Introduction Généralités
Séparateur linéaire Astuces
Séparateur non linéaire Problème
Exemples Espace intermédiaire

Spécificités
Ramener la discrimination à un problème linéaire
Problème d’optimisation sous-contrainte et support
Utilisation d’un espace intermédiaire (feature space)
Produit scalaire et noyau reproduisant

Remarques
Efficacité et flexibililté des noyaux
Schölkopf et Smola (2002)
[Link]

INSA de Toulouse - Apprentissage Machine Machine à Vecteurs Support

Introduction Généralités
Séparateur linéaire Astuces
Séparateur non linéaire Problème
Exemples Espace intermédiaire

Sur-ajustement

Frontière, complexité, généralisation et VC-dimension

INSA de Toulouse - Apprentissage Machine Machine à Vecteurs Support
Introduction Généralités
Séparateur linéaire Astuces
Séparateur non linéaire Problème
Exemples Espace intermédiaire

Notations
Y à valeurs dans {−1, 1}
X = X 1 , . . . , X p les variables prédictives
Y = f (X) un modèle pour Y
Un échantillon statistique de loi F

z = {(x1 , y1 ), . . . , (xn , yn )}

Estimation de bf de f , (Rp (ou F) 7→ {−∞, ∞})

par minimisation de :

P(f (X) 6= Y)

INSA de Toulouse - Apprentissage Machine Machine à Vecteurs Support

Introduction Généralités
Séparateur linéaire Astuces
Séparateur non linéaire Problème
Exemples Espace intermédiaire

Définition de la marge
f définie par une fonction réelle f : bf = signe(f )
L’erreur devient : P(f (X) 6= Y) = P(Yf (X) ≤ 0)
|Yf (X)| est un indicateur de confiance
Yf (X) est la marge de f en (X, Y)

Espace hilbertien
Φ : Rp (ou F) 7→ H
H : feature space de grande dimension avec produit
scalaire
Φ ramène à un problème linéaire : hyperplan séparateur
Première approche : Φ est la fonction identité

INSA de Toulouse - Apprentissage Machine Machine à Vecteurs Support

Introduction
Séparateur linéaire Hyperplan séparateur
Séparateur non linéaire Cas non séparable
Exemples

Recherche du plan de marge maximale

Un hyperplan est défini à l’aide du produit scalaire de H :

hw, xi + b = 0

où w est un vecteur orthogonal au plan

Le signe de la fonction f (x) = hw, xi + b indique la position
de x à prédire
Un point est bien classé si et seulement si : yf (x) > 0
(w, b) est défini à un coef. près ; on impose : yf (x) ≥ 1
Un plan (w, b) est un séparateur si : ∀i yi f (xi ) ≥ 1
|hw,xi+b|
Distance de x au plan (w, b) : d(x) = kwk = |fkwk
(x)|

2
La marge du plan a pour valeur : kwk2

INSA de Toulouse - Apprentissage Machine Machine à Vecteurs Support

Introduction
Séparateur linéaire Hyperplan séparateur
Séparateur non linéaire Cas non séparable
Exemples

Plan de marge maximale

INSA de Toulouse - Apprentissage Machine Machine à Vecteurs Support

Introduction
Séparateur linéaire Hyperplan séparateur
Séparateur non linéaire Cas non séparable
Exemples

Problème primal d’optimisation sous contraintes

 minw 12 kwk2


avec ∀i, yi < w, xi > +b ≥ 1



Problème dual avec multiplicateurs de Lagrange

La solution est un point-selle (w∗ , b∗ , λ∗ ) du lagrangien :
n
X
L(w, b, λ) = 1/2kwk22 − λi [yi (< w, xi > +b) − 1]
i=1

Ce point-selle vérifie : ∀i λ∗i [yi (< w∗ , xi > +b∗ ) − 1] = 0

Vecteurs support : xi avec contrainte active
Appartiennent au plan : yi (< w∗ , xi > +b∗ ) = 1
INSA de Toulouse - Apprentissage Machine Machine à Vecteurs Support
Introduction
Séparateur linéaire Hyperplan séparateur
Séparateur non linéaire Cas non séparable
Exemples

Formule duale du lagrangien

Plan optimal : w∗ = ni=1 λ∗i yi xi et
P Pn ∗
i=1 λi yi = 0
W(λ) = i=1 λi − 21 ni,j=1 λi λj yi yj < xi , xj >
Pn P

Le point-selle maximise W(λ) avec λi ≥ 0 ∀i

Problème d’optimisation quadratique de taille n
Hyperplan optimal : ni=1 λ∗i yi < x, xi > +b∗ = 0
P

avec b∗ = − 12 [< w∗ , svclass+1 > + < w∗ , svclass−1 >]

La prévision de x est fournie par le signe de
n
X
f (x) = λ∗i yi hx, xi i + b∗
i=1

INSA de Toulouse - Apprentissage Machine Machine à Vecteurs Support

Introduction
Séparateur linéaire Hyperplan séparateur
Séparateur non linéaire Cas non séparable
Exemples

Cas non séparable

Assouplissement des contraintes
les termes d’erreur ξi contrôlent le dépassement :

yi hw, xi i + b ≥ +1 − ξi ∀i ∈ {1, . . . , n}

La prédiction de xi est fausse à un vecteur si ξi > 1

La somme des ξi est une borne du nombre d’erreurs
Nouveau problème de minimisation avec pénalisation par
le dépassement de la contrainte :

min 21 kwk2 + δ ni=1 ξi

P
∀i, yi hw, xi i + b ≥ +1 − ξi

INSA de Toulouse - Apprentissage Machine Machine à Vecteurs Support

Introduction
Séparateur linéaire Hyperplan séparateur
Séparateur non linéaire Cas non séparable
Exemples

Remarques
δ contrôle le compromis entre ajustement et généralisation
Même forme duale mais avec les λi bornés par δ
n grand : algorithmes avec décomposition de l’ensemble
d’apprentissage
Capacité de généralisation dépend du nombre de vecteurs
supports mais pas de la taille de l’espace
Si les X sont dans une boule de rayon R, l’ensemble des
hyperplans de marge fixée δ a une VC-dimension bornée
2
par Rδ2 avec kwk ≤ R
Bornes d’erreur estimables mais trop pessimistes