DEA Perception et Traitement de l’Information

DEA Perception et Traitement de l’Information

Reconnaissance des formesApprentissage linéaire

S. Canu

http://psichaud.insa-rouen.fr/~scanu/RdF

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 ,

D(x) =signe(w’x+b) bw ˆ,ˆ

0' :décision de frontière , ...

... ,

...

...

te)(croix ver 0

rouges) (ronds 0

linéairedécision de règle

0 : linéairedécision de frontière

tiques)caractéris ( R dans valeursà v.a.

11

1

1

1

bxw

w

w

w

w

x

x

x

x

bxw

bxw

bxw

dX

d

j

d

j

d

jjj

d

jjj

d

jjj

d

Discrimination Linéaire

+

+

+ +

+

++

+

+

+

+

+

+

Codage {-1,1}, fonction de décision de type « heaviside »

-2 -1 0 1 2 3 4

-3

-2

-1

0

1

2

3

Estimation... et rêve

Stratégies d’estimation– Minimiser les erreurs

• moindres carrées• adaline• perceptron• le neurone formel

– estimer les paramètres • max de vraisemblance, puis règle de Bayes

– minimiser un autre critère• analyse discriminante de Fisher

-2 0 2 4 6-4

-2

0

2

4

6

classe 1classe 2estimationbayes

Moindres carrés

yXXXW

yXWXWWJ

xXbwWyXW

ybxwbwJ

bxwxDyxDDJn

iii

i

n

iii

''

0'20)(

)1,(et , avec

'),(

')(et )()(

1

21

21

2

X = [x1 ; x2];X = [X ones(length(X),1)];yi = [ones(length(x1),1) ; -ones(length(x2),1)];

W = (X'*X)\(X'*yi);west = W(1:2);best = W(3);

-2 0 2 4 6 8 10

-4

-3

-2

-1

0

1

2

3

4

5

6

classe 1classe 2estimationbayes

Résistance aux « outliers »

Moindre carrés « stochastiques »ADALINE (Widrow Hoff 1960)

XWXyWXWWXyWX

WWJ

xXbwWyWX

ybxwbwJ

bxwxDyxDDJ

n

ii

n

ii

n

ii

n

iii

i

n

iii

'2

2)(

)1,(et , avec

'),(

')(et )()(

1

1

1

21

21

2

oldnew

init

WW

WWJ

que.....tant

: itérative méthode ! impossible 0

plus*) évoluen'cout leou classés, mals des reste (*il

Algorithme itératif de gradient

=

Le gradient est orthogonal aux lignes d ’iso coût : argument à la « Taylor »

Algorithme de gradient : illustrationdans le plan w1,w2

+

Minimum du coûtLignes d ’iso-coût : J(W) = constante

Direction du gradientJ’(W)

w1

w2

3 solutions

sigmoide)fonction la(

)()( avec '2)(signefonction la approche qui dérivablefonction uneest

2)(PERCEPTRON : 1'

2)(ADALINE : linéaireion approximat

'2)( :gradient le

1

1

1

1

xthxxWxyWxWWJ

xyWxWWJ

xyWxWWJ

xWxyWxWWJ

ii

n

iii

i

n

iii

i

n

iii

ii

n

iii

LE NEURONE FORMEL

Algorithme itératifnbitemax = 50;k=0;

while ((cout > 0) & (k<nbitemax)) K=K+1;

ind = randperm(length(X));

for i=1:length(X)

Dir = (sign(X(ind(i),:)*W)-yi(ind(i)))*X(ind(i),:);W = W - pas*Dir';

end cout = sum(abs(sign(X*W)-yi)); disp([k cout]);

end

Stabilisation du coût (erreur relative)

Randomisation (ok si n grand)

Évaluation du coût : n opérations

-6 -4 -2 0 2 4 6 8 10

-4

-3

-2

-1

0

1

2

3

4

5

6

ADALINE, Ça marche...

-2 -1 0 1 2 3 4 5 6

-3

-2

-1

0

1

2

3

ADALINE des fois ça ne marche pas…

Solution au sens des moindres carrés

-6 -4 -2 0 2 4 6 8 10-4

-3

-2

-1

0

1

2

3

4

5

6

Le Perceptron, des fois ça ne marche pas...

...Quand les exemples ne sont pas linéairement séparables

Règle du perceptron(Rosenblatt 1958)

codage

classébien ' si classé mal ' si '

0 si '0 si 0)(

1'et 1 si '

1 si ' codage

)(

)(

iold

iioldnew

ii

i

iiii

iii

iii

oldnew

xwxxw

w

WxxWx

WWJ

yyxxyxx

xyWxWWJ

WWJww

Règle du perceptron(Rosenblatt 1958)

• Pas de fonction coût minimisée• preuve de convergence (dans le cas linéairement séparable)

modif) de (nombre

avec min

0 ,1)(hypothèse monde lebien tout classe qui un vecteur soit

classé malest ou fois de nombre le avec

0

1

*

1

**

*

*

1

n

ii

ii

n

iii

i

ii

n

iii

init

ioldnew

mMwxMwxmww

wxniw

xmxmw

wxww

Règle du perceptron(Rosenblatt 1958)

'''

''' :2et 1

max avec :2

itérations après doncet max

2

avec min :1

22

2*22*2

222

2222

222

2222

1

*

1

**

MkwMkMcwwwwMc

xcMcw

Mxww

xw

xwxww

mMwxMwxmww

xww

ii

ii

oldnew

iold

ioldioldnew

n

ii

ii

n

iii

ioldnew

Convergence des algorithmes de gradient

converge algorithmel' Alorsconvexecout

0limet lim si

)(

1

2

1

1

k

jk

k

k

jk

k

kkk WWJww

Performances des algorithmes linéaires

2/2*

***

1)(

212)ˆ(

,/21 ,, de jointe loi la

)( )(minarg coutson et monde)(du linéairer classifieumeilleur

)(minargˆ

empirique risquedu on minimisati

exemples 1)(

:erreurs des fréquence : ageapprentissd'erreur )()(

:erreurd' éprobabiliterreur

nd

D

empD

n

iyxDemp

d

edn

eJDJP

dnndYX

DJJDJD

DJD

nIn

DJ

RXYXDPDJ

ii

Théorème (Vapnik & Chervonenkis, 1974)

Performances des algorithmes linéaires

2/2*

***

212)ˆ(

,/21 ,, de jointe loi la

)( )(minarg coutson et monde)(du linéairer classifieumeilleur

)(minargˆ : empirique risquedu on minimisatidimension en exemples

nd

D

empD

edn

eJDJP

dnndYX

DJJDJD

DJDdn

Théorème (Vapnik & Chervonenkis, 1974)

Probabilitéd’erreur

risqueempirique

Malédiction de la dimensionnalité

Asymptotiquement« jouable »

précision

borne

Maximum de vraisemblance

Distance de Mahalanobis

2

121

121

211

log'21et

avec 0'

ppb

wbxw

1, 11

1 '21

xx

X exf ' 1

11 xx

2221

1

)1(

111

21

11

1)2(

1)1(

ˆˆ2

1ˆ

1ˆˆ ˆ

,1,,,1, geappentissad' ensemble n échantillo1

nnn

xn

mnn

np

nixnixn

ii

ii

2

121

121

211

ˆˆlog- ˆˆˆ ˆˆ

21ˆet

ˆˆˆˆ avec 0ˆ'ˆ

ppmmmm b

mmwbxw

1

11

)1(1

)1(1 ˆˆ

11ˆ

n

i

Tii mxmx

n

Analyse discriminante de Fisher2 classes

ˆ avec

ˆˆmin

221

WW

T

T

RvS

vSv

mmvMV

d

Quelle est la direction de l’espace des caractéristiquesqui sépare le mieux les deux classes ?

Voilà la critère !

Analyse discriminante de Fishermulti classes

1 avec min :direction une rechercheon

ou 0 :solution min

ˆ : classesINTRA inertie

ˆˆ : classes INTER inertie

observées variables les mieux""au résumant variable"nouvelle" une rechercheon ,

ˆ,ˆ :moyenne la estimeon classe chaquepour

: totalnombre , classe la dans exemples

classes,

1

1

C

1

vSvvSvvSv

vvSvvSv

nnS

mmmmnnS

dvRx

mc

nncn

C

WT

WT

BT

Rv

WT

BT

Rv

c

C

c

cW

Ti

C

ci

cB

dcc

ccc

d

d

Analyse discriminante de Fishermulti classes

vvSS

vSvS

vvSvvSv

vSvvSv

vSvvSv

vSvvSvvSv

BW

WB

WT

BT

WT

BT

Rv

WT

BT

Rv

WT

WT

BT

Rv

d

d

d

0 -

01 -

1 - min

1 avec min

1 avec min

1

On recherche les vecteurs propres de la matrice BW SS 1

AD en matlabind1=find(yi==1); X1=Xi(ind1,:);ind2=find(yi==2); X2=Xi(ind2,:);ind3=find(yi==3); X3=Xi(ind3,:);

n1=length(ind1); n2=length(ind2); n3=length(ind3);n = n1+n2+n3; Sw = (n1*cov(X1)+n2*cov(X2)+n2*cov(X3))/n; %AD m1 = mean(X1); m2 = mean(X2); m3 = mean(X3); mm = mean(Xi);Sb = (n1*(m1-mm)'*(m1-mm)+n2*(m2-mm)'*(m2-mm)+n3*(m3-mm)'*(m3-mm))/n;

% L = chol(Sw);% Linv = inv(L);% [v l]=eig(Linv*Sb*Linv'); % AD% v = Linv'*v; [v l]=eig(inv(Sw)*Sb); % AD [val ind] = sort(-abs(diag(l))); P = [v(:,ind(1)) v(:,ind(2))]; xi = Xn*P;

Conclusion : discrimination linéaire– Minimiser les erreurs

• moindres carrées : erreur quadratique• adaline : erreur quadratique• perceptron : le nombre de mal classé• le neurone formel : les formes frontière• nombre d’erreur : le simplex -> les SVM

– estimer les paramètres • max de vraisemblance, puis règle de Bayes

– minimiser un autre critère• analyse discriminante de Fisher : REPRESENTATION

Apprentissage bayésien

Malédiction de la dimensionalité

– Un problème inatendu– estimation de la matrice de covariance– capacité d’un classifieur linéaire– le problème de l’erreur moyenne !

Estimation du taux d’erreur