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