Upload
pia
View
33
Download
2
Embed Size (px)
DESCRIPTION
DEA PTI Perception et Traitement de l’Information. Reconnaissance des formes Les méthodes à base de noyaux S. Canu http://psichaud.insa-rouen.fr/~scanu/RdF. Buts de la RdF. D : Algorithme de Reconnaissance des Formes. C’est la forme « y=D(x) ». Une forme x (vecteur forme - PowerPoint PPT Presentation
Citation preview
DEA PTI Perception et Traitement de l’Information
Reconnaissance des formes
Les méthodes à base de noyaux
S. Canu
http://psichaud.insa-rouen.fr/~scanu/RdF
Buts de la RdFD : Algorithme
de Reconnaissance
des Formes
Une forme x(vecteur forme
des caractéristiques)
C’est la forme
« y=D(x) »
classe" vraiela" ,
)( ,...,,...,1 : RdF
décisions des ensemble ,...,2,1tiquescaractéris des espace
D(x)Rx
xDxLlRD
LyRx
d
d
d
Nous voulons un algorithme de RdF performant
K
kkXk
D
sSPdxkxfxDsCXDSCEDJ
DJD
1 ,)(,)(,)(
)(min décision de règle uned'Cout D
RdF et apprentissage
D : Algorithme de
Reconnaissancedes Formes
Une forme x(vecteur forme
des caractéristiques)
C’est la forme
« y=D(x) »
A : Algorithme d’apprentissage
niyxS iin ,1 , Ensemble d’apprentissage (échantillon)
)(,)(C,et )(
:couts les
XDSCEDJDJ
A priorisur la
nature de la solution
2
1
3
Les problèmes PYXP ,
Les méthodes à base de Noyau
Ce qui se ressemble s’assemble=
zone d ’influence d’un exemple
niyxS iin ,1 , Ensemble d’apprentissage (échantillon)
« si x ressemble à un xi, il aura l ’étiquette yi »
Zone d’influence
-2 -1 0 1 2 3 4 5 6-5
-4
-3
-2
-1
0
1
2
3
4
5
Définition : Si d(x,xi) < b x appartient à la zone d’influence du point xi
b
-2 -1 0 1 2 3 4 5 6 7 8-6
-4
-2
0
2
4
6
Définition : 1-Si x appartient à la zone d’influence d’un seul point xi, alors il a l’étiquette yi
2-Si x appartient à la zone d’influence de plusieurs points de même étiquette, alors il a cette étiquette3-Si x appartient à la zone d’influence de plusieurs point d’étiquette différentes, alors il y a rejet d’ambiguité4-Si x appartient à la zone d’influence d’aucun point,
alors il y a rejet de distance
1
2
3
4
Règle de décision
4
b
-4 -2 0 2 4 6 8-6
-4
-2
0
2
4
6
0.5
0.5 0.50.5
0.5
0.5
1
1
1 1
1
1
1
1
2
2
2
2
2
2
2
Mise en œuvrefor i = 1:n d(i) = norm((x-xi(i,:))/b);endind = find(d>seuil);
b caractérise la zone d’influence d’un point
-4 -2 0 2 4 6 8
-6
-4
-2
0
2
4
6
Pour b « grand »
La zone d’ambiguïté est trop importante
-3 -2 -1 0 1 2 3 4 5 6 7-4
-3
-2
-1
0
1
2
3
4
5
6k = 1
Pour b plus petit
La zone de rejet de distance est trop importanteil faut cumuler les influences
xx
0)( si 2 classe
0)( si 1 classe)( ),()(
1 xd
xdxDxxGyxd i
n
ii
b
vu
vuG
2
exp),(
Noyau
Distance de la forme x à toutes les forme de l’ensemble d’apprentissage
On peut aussi modifier la zone d ’influence d’un point
au lieu d’avoir uniquement une influence de type « tout ou rien »on peut imaginer de nombreuses autres manières dont un point influence les autres : par exemple :
0)( si 2 classe
0)( si 1 classe)( ),()(
1 xd
xdxDxxGyxd i
n
ii
b
vu
vuG
2
exp),(
Noyau
Frontière de décision
d(x)=0
d(x)
=0
Classe 1
Classe 2
Noyau « matlab »
d = 0
for i = 1:n d = d + yi(i)*exp(-(norm(xi(i,:)-x).^2)/b);end
D=sign(d);
0)( si 2 classe
0)( si 1 classe)( ),()(
1 xd
xdxDxxGyxd i
n
ii
b
vu
vuG
2
exp),(
d(x) est petit si x est loin des xi ou si les rouges et les bleus se compensentrejet de distance et rejet d’ambiguïté ?????
Frontière de décisiond(x)=
Classe 1
Classe 2
sinonrejet
)( si 2 classe
)( si 1 classe
)( ),()(1
xd
xd
xDxxGyxd i
n
ii
Avec rejet
1.0 ici d(
x)=-
rejet
Noyaux avec rejets
Est-ce une bonne idée ?Comment interpréter d ?Comment choisir G ?Comment choisir b ?Comment choisir les seuils ?
2.0 ; 1.0 ici
2 classe sisinon
1 classe sisinon
/et / si ambiguïtéd'rejet
si distance derejet
)(
),()( ; ),()(
21
21
1221
21
12
11
21
ad
d
i
n
ii
n
i
dd
dd
dddd
dd
xD
xxGxdxxGxd
Classe 1Classe 2
Rejet de distance
Rejet d’ambiguïté
Est-ce une bonne idée ? Oui si c’est universellement consistant
bvu
bvu
b
vu
b
vu
i
n
ii
IvuG
IvubvuGbvu
vuG
vuG
vuG
xd
xdxDxxGyxd
),( : uniformenoyau
),( ovEpanechnikd'noyau /1
1),(Cauchy denoyau
exp),( Laplace denoyau
exp),(gaussien noyau
0)( si 2 classe
0)( si 1 classe)( ),()(
2
2
1
2
Comment choisir G : Autres noyaux
-4 -2 0 2 40
0.2
0.4
0.6
0.8
1
x
G(x
)
Gauss et Laplace
-4 -2 0 2 40
0.2
0.4
0.6
0.8
1
x
G(x
)
Cauchy
-4 -2 0 2 4-0.2
0
0.2
0.4
0.6
0.8
1
x
G(x
)
Hermite
-1.5 -1 -0.5 0 0.5 1 1.5
0
0.2
0.4
0.6
0.8
1
1.2
xG
(x)
Epanechnikov et uniforme
Exemples de noyaux
bvu
bvu
b
vu
b
vu
b
vu
I
Ivub
vub
bvu
exp
/1
1
exp
exp
2
2
2
2
2
Noyaux positifs et les autres…
Universellement consistant
dGc
cnn
d
nn
eJDJP
nnnYX
nbbG
deet noyau du dépend qui constante uneest ou
22 32/
00
2*)(
, 0 ),,( de loi la Alors,
limet 0lim sirégulier"."noyau un soit
Définition : un noyau G est dit « régulier » si• il est non négatif• il existe une boule contrée B de rayon r et une constante k telle que :
G(y)dxkIuGSxy
S supet )(
Théorème :
Erreur de notre règle
Erreur de Bayes
)(1
)(ˆ
exp1
)( : exemplepar ; 1et 0)(soit
1
-
2
ib
n
i
b
u
bb
xxGn
xp
ZuG duuGuG
Comment interpréter le règle de décision ? Estimation de densité par des noyaux
Fenêtres de Parzen
Consistance universelle
pp
nbb
pnnixPp
n
d
i
ˆ : alors
lim siet 0lim si
loi lasuivant tiréspoints ,,1,soient ,
nn
Stratégie de RdF : xcp
xcppp
ˆmax : utilisons
max est Bayes de règle la , estime ˆ
c
c
C’est la règle du MAP
Discrimination avec les noyau de Parzen : règle du MAP (3 classes)d1 = 0; d2 = 0; d3 = 0;for i = 1:n
if(yi(i)=1); d1 = d1 + exp(-(norm(xi(i,:)-x).^2)/b); end; % Vraisemblance if(yi(i)=2); d2 = d2 + exp(-(norm(xi(i,:)-x).^2)/b); end; if(yi(i)=3); d3 = d3 + exp(-(norm(xi(i,:)-x).^2)/b); end;end
pc1=length(x1); pc2=length(x2); pc3=length(x3);nt = pc1+pc2+pc3;
pc1=pc1/nt; pc2=pc2/nt; pc3=pc3/nt; % probabilité a priorip = pc1*d1+pc2*d2+pc3*d3; % p(x) (théorème des probabilité totales)
map1 = pc1*d1./p; map2 = pc2*d2./p; map3 = pc3*d3./p;
seuil = .15; rejetD = 0.025;
if (map1>(map2+seuil)) & (map1>(map3+seuil))); classe = 1elseif ((map2>(map1+seuil)) & (map2>(map3+seuil))); classe = 2elseif (map3>(map1+seuil)) & (map3>(map2+seuil))); classe = 3elseif (p<rejetD);
classe = 4 % rejet de distanceelse
classe = 0 % rejet d’ambiguïtéend
MAP sur 3 classes
-4 -2 0 2 4 6 8-6
-4
-2
0
2
4
6map1
0.1
0.2
0.2
0.40.4
0.5
0.60.7
0.7
0.80.8
0.9
0.9
-4 -2 0 2 4 6 8-6
-4
-2
0
2
4
6map2
0.1
0.20.3
0.40.5
0.6
0.7
0.8
0.9
-4 -2 0 2 4 6 8-6
-4
-2
0
2
4
6map3
0.1
0.2
0.6
0.70.80.9
-4 -2 0 2 4 6 8-6
-4
-2
0
2
4
6Discrimination de Parzen
Exemple sur 3 classes
Comment choisir b ?
Minimiser l’erreur en généralisation :
– avec un ensemble de test
– avec une technique de rééchantillonnage
– avec une borne sur l ’erreur
Méthode linéaireméthode « des potentiels »
0)( si 2 classe
0)( si 1 classe)( ),()( ),()(
11 xd
xdxDxxGcxdxxGyxd i
n
iii
n
ii
Les ci sont recherchés de manière à minimiser la probabilité d’erreur
yGc
ycGyxfn
jjj
ci
1
2
1
2
)(min
équivalentnoyau leest ~
),(~
),(),( ),()(11 11
G
xxGyxxGxxGyxxGcxdn
jiji
n
jji
n
iji
n
ii
Les ci traduisent l’influence du point dans le calcul de la solution
Méthodes non linéaires : les RBF
0)( si 2 classe
0)( si 1 classe)( ),()( ),()(
11 xd
xdxDxxGcxdxxGyxd i
n
iii
n
ii
2
2
1)(
i
inm
ii
b
xGcxd
Casser la linéarité : adapter le noyau au problème
– au lieu de choisir xi, optimiser la position du centre– adapter la largeur de bande du noyau– si on a de « bon » noyaux, on peu en réduire le nombre
2
1
2
1
2
,,)(min yxDy
b
xGcsigne
n
jj
m
i i
iji
bc iii
Les ci i et bi sont recherchés de manière à minimiser l’erreur :
ATTENTION : on a maintenant un problème de minimisation non linéaire
Inconvénient des noyauxla malédiction de la dimensionnalité
– n points pour d dimensions
– Formulation géométrique,
– Densité de l’échantillonnage,
– Distance entre 2 points,
– Tous les points sont à la frontière,
– Borne de Stone,
x Rd
r(x) : Rd R
n
1
d nd
En grande dimension la notion de distance ne veut pas dire grand chose
-0.5 0 0.5 1Projection d'une distribution normale
n = 10000 et d = 100
0 0.5 10
1
Loi de la distance au bord du domaine
d = 20
Densité de l’échantillonnage
– n points pour d dimensions
– X ~ N(0,1) d
• x = randn(10000,100)
• proj = x * x(1,:)’;
• hist(proj./proj(1))
– X ~ U(0,1) d
• dist(n,d) = Ej(mini |xi-xj|)
n
1
d nd
n
Conclusion
– Noyau =distance
– malédiction = représentation
– flexibilité = largeur de bande
– des noyaux pour battre la malédiction ?
– vers la non linéarité pour battre la malédiction !
TP matlab– Aller rechercher les données sur le WEB : psichaud.insa-rouen.fr\
~scau\RdF\DataAcor.txt
– ouvrir Matlab : et charger les données• load 'DataAcor.txt'• Xi = DataAcor;
– visualiser les données grâce au programme visu.m
– écrire une programme matlab– 1. Netoyer les données (éliminer les codes -9999)
– 2. Normaliser– 3. diviser les données en apprentissage / test– 4. réaliser l’analyse discriminante– 5. estimer les densités par la méthode de Parzen– 6. calculer et visualiser la matrice de confusion