Upload
tuxette
View
146
Download
3
Embed Size (px)
DESCRIPTION
Séminaire GRIMM/SMASH, Université Toulouse 2 (Le Mirail), France October 22nd, 2004
Citation preview
Une introduction aux SVM :Une introduction aux SVM :travail sur des donntravail sur des donnéées es
fonctionnellesfonctionnelles
Nathalie Villa (GRIMM - SMASH)Université Toulouse Le Mirail
Séminaire SMASH8 octobre 2004
Séminaire SMASH23 octobre 2004
Présentation du ProblèmePrésentation du Problème
Séminaire SMASH23 octobre 2004
Discrimination
Y ∈ {-1;1}
Régression
Y réelX ∈ ℑ
X ∈ ℑ
f
f
Séminaire SMASH23 octobre 2004
On dispose de N observations :
Y1,…, YN
X1,…, XN ∈ ℑ
et on cherche à trouver fα la plus proche possible de fparmi les fonctions d’un ensemble
Λ = {fα : ℑ → R ou {-1;1}}α
Séminaire SMASH23 octobre 2004
Théorie de l’ApprentissageThéorie de l’Apprentissage
Une présentation rapide
Séminaire SMASH23 octobre 2004
Le risqueFonction de perte : L : R ×ℑ → [0;1]
exemples : L(y,fα(x)) = (y-fα(x))²L(y,fα(x)) = 1{y = fα(x)}
Risque : R(α) = E (L(Y,fα(X)))exemples : EQM
Probabilité d’erreur
Risque empirique : Remp(α) =
exemples : Erreur quadratique de prédiction Nombre d’erreurs dans l’échantillon
∑=
N
i
ii XfYLN 1
))(,(1
Séminaire SMASH23 octobre 2004
Théorème (Vapnik 95)
Avec une probabilité supérieure à 1 - η, on a
NhRR emp
f
)4/ln()()(sup ηααα
−≤−
Λ∈
où h est la VC-dimension de Λ.
Pour le risque associé à la probabilité d’erreur
Séminaire SMASH23 octobre 2004
VC-dimension ?Exemple : Λ = {1H : H hyperplan de R²}
Λ sépare de toutes les manières possibles trois points du plan non alignés :
Λ ne peut séparer de toutes les manières possibles 4 points du plan.
VC-dimension = 3
Séminaire SMASH23 octobre 2004
SVM pour ClassificationSVM pour Classification
et pour les données fonctionnelles… ?
Séminaire SMASH23 octobre 2004
IdéeΦ (non linéaire)
X1,…, XN ∈ ℑ
Espace image(grande dimension)
Z1,…, ZN
Séminaire SMASH23 octobre 2004
Discriminationpar hyperplansLes hyperplans d’un espace vectoriel ont pour équation <z,w> + b = 0
Λ = {fw,b : z → sign(<z,w>+b), ||w|| ≤ A}
Théorème : Soit R le rayon de la plus petite boule contenant toutes les observations Z1,…,ZN. Alors, Λ a pour VC dimension h tel que
h < R²A² + 1
Séminaire SMASH23 octobre 2004
HyperplansoptimauxReformulation du problème : on cherche à minimiser
2w21
sous la contrainte N...1i,1bw,ZYii
=∀≥
+><
Par la méthode des multiplicateurs de Lagrange, cela revient à maximiser (en λ) :
∑∑==
><−=N
1i
jiji
ji
N
1ii
Z,ZYY)(W λλλλ
Séminaire SMASH23 octobre 2004
Solution :
∑=
=N
1i
ii*
i
*ZYw λ
où seuls un certain nombre de λi sont non nuls (les Zi
correspondants sont appelés vecteurs supports)
Espace image(grande dimension)
Z1,…, ZNVecteurs supports (participent à la construction de la frontière de décision)
Séminaire SMASH23 octobre 2004
Construction del’espace imageDéfinition : on appelle noyau de type positif une fonction K : ℑ×ℑ→R telle que :
)x,...,x(),,...,(,1nn1n1
∀∀≥∀ λλ
0)x,x(Kn
1j,ijiji≥∑
=λλ
Séminaire SMASH23 octobre 2004
Théorème (de Moore-Aronszajn) : Il existe un unique espace de Hilbert F de fonctions définies sur ℑ dont K est un noyau reproduisant ie :
où Kx = K(.,x) = Φ(x).
)'x,x(KK,K,)'x,x(F'xx
2=><ℑ∈∀
Dans l’espace image, le produit scalaire s’écrit simplement à l’aide du noyau K : <z,z’> = K(x,x’).
X Φ
Z
Séminaire SMASH23 octobre 2004
Exemples denoyauxNoyau gaussien :
σ2'xxe)'x,x(K
−=
Noyau polynomial :d
)1'x,x()'x,x(K +><=
Remarque : Il existe des conditions (dans R) pour savoir si un noyau est de type positif (noyaux de Mercer, noyaux de la forme F(||.||²), etc)
QUID POUR LES ESPACES DE DIMENSION INFINIE ?
Séminaire SMASH23 octobre 2004
Autres idées de noyaux :
))'x,x(()'x,x(K δℵ=où ℵ est un noyau sur R et δ est une semi-distance (basée sur l’ACP ou sur des dérivées).
A QUELLE(S) CONDITION(S) KEST-IL UN NOYAU POSITIF ?
Séminaire SMASH23 octobre 2004
Un mot sur lechoix du paramètre1) Fixer une liste possible de paramètres à tester ;2) Pour chaque paramètre :
a. Déterminer l'hyperplan optimal de paramètre w*
correspondant ;b. Evaluer la VC-dimension h associé à cet hyperplan
par la procédure décrite plus loin ;
c. Evaluer l'erreur totale commise : (Remp + g( ))
3) Choisir le paramètre à plus faible erreur.
2*w
h
Séminaire SMASH23 octobre 2004
Evaluation de laVC-dimension
Théorème (de Moore-Aronszajn) : Soit R le rayon de la plus petite boule contenant toutes les observations {Zi}i. Alors l’ensemble des hyperplans discriminants tel que ||w||≤ A a pour VC-dimension h tel que
h < R²A² + 1
On évalue A en calculant la norme de w
On évalue R en minimisant R² sous la contrainte : ||Zi – z*||² ≤ R² (par la méthode du multiplicateur de Lagrange).
Séminaire SMASH23 octobre 2004
Un autre point de vueUn autre point de vue
FIR
Séminaire SMASH23 octobre 2004
IdéeΦ(non linéaire)
Noyau classique
Espace image(grande dimension)
Z
X ∈ ℑ
SIR
<X,a1>,…, <X,aq>
Séminaire SMASH23 octobre 2004
Merci de votre attentionMerci de votre attention