Embed Size (px)
DESCRIPTION
DEA Perception et Traitement de l’Information. Reconnaissance des formes Apprentissage linéaire S. Canu http://psichaud.insa-rouen.fr/~scanu/RdF. 1. RdF et apprentissage. Les problèmes. Ensemble d’apprentissage (échantillon). 3. A priori sur la nature de la solution. 2. - PowerPoint PPT Presentation
Citation preview
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
