View
105
Download
0
Category
Preview:
Citation preview
Les réseaux de neurones pour l’apprentissageESSEC, le 28 Juin 2002
Réseaux de neurones artificielsRéseaux de neurones artificiels
« la rétropropagation du gradient »« la rétropropagation du gradient »
S. Canu,
laboratoire PSI, INSA de Rouenéquipe « systèmes d’information pour
l’environnement »
asi.insa-rouen.fr/~scanu
Les réseaux de neurones pour l’apprentissageESSEC, le 28 Juin 2002Histoire …Histoire …
• 1940 : La machine de Turing
• 1943 : Le neurone formel (McCulloch & Pitts)
• 1948 : Les réseaux d'automates (Von Neuman)
• 1949 : Première règle d’apprentissage (Hebb)
• 1958-62 : Le perceptron (Rosenblatt)
• 1960 : L'adaline (Widrow & Hoff)• 1969 : Perceptrons (Minsky & Papert)
les limites du Perceptron besoin d'architectures + complexes, Comment effectuer l'apprentissage ? On ne sait pas !
• 1974 : Rétropropagation (Werbos)
pas de succès !?!?
Les réseaux de neurones pour l’apprentissageESSEC, le 28 Juin 2002Histoire …Histoire … (suite)(suite)
• 1986 : Rétropropagation (Rumelhart & McClelland)
nouvelles architectures de Réseaux de Neurones
applications :- reconnaissance de l’écriture
- reconnaissance/synthèse de la parole- vision (traitement d’images)
• 1990 : « Société de l’Information »
nouvelles applications - recherche/filtrage d’information dans le Web- extraction d’information / veille technologique- multimedia (indexation, …)- data mining
besoin de combiner différents modèles
Les réseaux de neurones pour l’apprentissageESSEC, le 28 Juin 2002PlanPlan
• Rappels :– Moindres carrés stochastiques
– Algorithmes de gradient
– Perceptron Multicouches
• Principe de la rétropropagation
• Algorithmes de rétropropagation
Les réseaux de neurones pour l’apprentissageESSEC, le 28 Juin 2002
impossible (’ ! ) méthode itérative :winit
Répéter
wnew = wold - Tant qu ’il reste des mals classés ou que le coût n’évolue plus
XWX'yWX2 W
WXyWX2
W
)W(J n
1ii
n
1ii
0W
J
Algorithme itératif de gradient
bx'w)x(D et y)x(D)D(J ii
n
1i
2ii
n
1i
2i
n
1i
2ii yWXybx'w)b,w(J
Moindres carrés « stochastiques »Moindres carrés « stochastiques » ADALINE (Widrow Hoff 1960)ADALINE (Widrow Hoff 1960)
Les réseaux de neurones pour l’apprentissageESSEC, le 28 Juin 2002
Le gradient est orthogonal aux lignes d’iso-coût : argument à la « Taylor »
Algorithme de gradientAlgorithme de gradient
+
Minimum du coûtLignes d’iso-coût :
J(W) = constante
Direction du gradientJ’(W)
w1
w2
• Illustration dans le plan (w1 ,w2)
Les réseaux de neurones pour l’apprentissageESSEC, le 28 Juin 2002Algorithme de gradientAlgorithme de gradient
• Illustration dans le plan (J(w),w) : la « descente » de gradient
w
J(w)
Minimum du coût
Direction du gradientJ’(W)
Les réseaux de neurones pour l’apprentissageESSEC, le 28 Juin 2002
Le gradient :
• Approximation linéaire (Adaline)
• Perceptron : ’=1
• Neurone formel : on remplace par une fonction dérivableex : (x)=th(x) fonction sigmoïde
ii
n
1iii xWx'yWx2
W
)W(J
3 solutions3 solutions
ii
n
1iii xWx'yWx2
W
)W(J
i
n
1iii xyWx2
W
)W(J
i
n
1iii xyWx2
W
)W(J
Les réseaux de neurones pour l’apprentissageESSEC, le 28 Juin 2002Perceptron Multi-CouchesPerceptron Multi-Couches
• Réseau feedforward(1986)
• Fonction de transfert tanh(.) (sauf couche de sortie linéaire)
• Méthode d’apprentissage (supervisé) usuelle :– rétropropagation du gradient
x1
xi
xn0
y
Les réseaux de neurones pour l’apprentissageESSEC, le 28 Juin 2002NotationsNotations
• Biais :– avec x0=1
– idem pour toutes les couches (ex : PMC à une couche cachée)
– W1=[wji]
– W2=[wkj]
j=1:n1 k=1:n2
i
n
0ijii
n
1iji
1j xwfbxwfy
00
i=1:n0
xi
x0
= 1(1)x0=1
yk
wji
wkj
Les réseaux de neurones pour l’apprentissageESSEC, le 28 Juin 2002PropagationPropagation
• Calcul des sorties du réseau en propageant les valeurs de x de couche en couche :
i
n
0iji
1j xwa
0
1
1
1n
0j
1jkj
2k xwa
2
2
)1(j
1j afx
)2(kk agy
wji
wkj
xi
xj(1)
yk
j=1:n1 k=1:n2i=1:n0
Les réseaux de neurones pour l’apprentissageESSEC, le 28 Juin 2002Algorithme de propagationAlgorithme de propagation
Function y = propag(x,w1,w2)
a1 = [x ones(n,1)]*W1; x1 = tanh(a1); a2 = [x1 ones(n,1)]*W2; y = a2;
Parallélisé sur les exemples(si x est une matrice, ça marche !)
Les réseaux de neurones pour l’apprentissageESSEC, le 28 Juin 2002Calcul de l ’erreurCalcul de l ’erreur
• Fonction de coût :– on présente un exemple x=[x1... xn0
] (avec ydes sortie désirée)
– on calcule la sortie correspondante y =[y1... yn2]
– erreur :
– coût associé à l ’exemple :
– coût global :
kdeskk yye
2n
1k
2k)exemple( e
2
1J
n
1l)lexemple(JJ
Les réseaux de neurones pour l’apprentissageESSEC, le 28 Juin 2002Calcul du gradientCalcul du gradient
• Mise à jour de wji et w
kj selon une règle delta:
• Problème = calcul de et
w
Jw
jiw
J
kjw
J
Les réseaux de neurones pour l’apprentissageESSEC, le 28 Juin 2002
2n
1k
2k
desk yy
2
1J
Couche de sortieCouche de sortie
• Calcul de pour un exemple fixé
posons
kjw
J
kdesk yy
kj
2k
2k
k
kkj w
a
a
y
y
J
w
J
wkj
xj(1) y
k
j=1:n1 k=1:n2
1n
0j
1jkj
2k xwa )2(
kk agy
1jx 1ag )2(
k
1jk
kj
x.Errw
J
2kk
desk2
kk agyy
a
JErr
Les réseaux de neurones pour l’apprentissageESSEC, le 28 Juin 2002Couche cachéeCouche cachée
• Calcul de pour un exemple fixé jiw
J
ji
1j
1j
1j
1jji w
a
a
x
x
J
w
J
ix )1(jaf
i
n
0iji
1j xwa
0
)1(j
1j afy
wji
xi
j=1:n1i=1:n0
1jx
2n
0k1j
2k
2k
1j x
a
a
J
x
J
2n
0kkjk1
j
wErrx
J
1j
n
0kkjk1
jj afwErr
a
JErr
2
ijji
x.Errw
J
Les réseaux de neurones pour l’apprentissageESSEC, le 28 Juin 2002Algorithme de rétropropagationAlgorithme de rétropropagation
Function grad = retropropag(x,yd,w1,w2)
...
a1 = [x ones(n,1)]*W1; x1 = tanh(a1);
a2 = [x1 ones(n,1)]*W2; y = a2;
ERRk = -(yd-y).*(1-y.*y);
GradW2 = [x1 ones(n,1)]'* ERRk ;
ERRj = (w2(1:n2-1,:)*ERRk')'.*(1-x1.*x1);
GradW1 = [x ones(n,1)]'* ERRj ;
w1 = w1 - pas1 .* GradW1;
w2 = w2 - pas2 .* GradW2;
Les réseaux de neurones pour l’apprentissageESSEC, le 28 Juin 2002ExempleExemple 1/41/4
• x = [0.5 1] ydes = [0.5 1]
• W1=[0.5 0.5 ; 0.5 0.5] (pas de biais)
• W2=[1 1 ; 1 1]x1= 0.5
x2(1)
y1 = 1.2703
n1 =2 n2 =2n0=2
x2= 1
x1(1)
y2 = 1.2703 a(1)=[0.75 0.75]
x(1)=[0.6351 0.6351]
a(2)=[1.2703 1.2703]y = [1.2703 1.2703]
Les réseaux de neurones pour l’apprentissageESSEC, le 28 Juin 2002ExempleExemple 2/42/4
x1= 0.5
x2(1)
err1 = 0.7703
n1 =2 n2 =2n0=2
x2= 1
x1(1)
err2 = 0.2703
ERRk = [0.7703 0.2703]GradW2 = [0.4893 0.1717 ; 0.4893 0.1717]ERRj = [0.6208 0.6208]GradW1 =[0.3104 0.3104 ; 0.6208 0.6208]
Les réseaux de neurones pour l’apprentissageESSEC, le 28 Juin 2002ExempleExemple 3/43/4
• MAJ de W1 et W2
• Nouvelle propagation, etc...x1= 0.5
x2(1)
y1 = 0.5242
n1 =2 n2 =2n0=2
x2= 1
x1(1)
y2 = 0.6344
w1 =[0.3448 0.3448 ; 0.1896 0.1896]w2 =[0.7554 0.9142 ; 0.7554 0.9142]
y = [0.5242 0.6344]
Les réseaux de neurones pour l’apprentissageESSEC, le 28 Juin 2002ExempleExemple 4/44/4
• Evolution de y1 et y2
0 5 10 150.5
0.6
0.7
0.8
0.9
1
1.1
1.2
1.3
y1
y2
Les réseaux de neurones pour l’apprentissageESSEC, le 28 Juin 2002Gradient batch / séquentielGradient batch / séquentiel
• 2 façons d ’appliquer l’algorithme de rétropropagation :
– « batch » :mise à jour des poids après la présentation de tous les exemples
• calculs et stockage plus lourds si trop d ’exemples
– séquentiel : (on-line, stochastique)mise à jour des poids après chaque exemple
• besoin de tirer l ’exemple au hasard• problèmes de convergence
Les réseaux de neurones pour l’apprentissageESSEC, le 28 Juin 2002
• 2 façons d ’appliquer l’algorithme de rétropropagation :
– « batch » :mise à jour des poids après la présentation de tous les exemples
• calculs et stockage plus lourds si trop d ’exemples
– séquentiel : (on-line, stochastique)mise à jour des poids après chaque exemple
• besoin de tirer l ’exemple au hasard• problèmes de convergence
Gradient batch / séquentielGradient batch / séquentiel
Moins de 5000 exemples,Matlab
plus de 5000 exemplesSNNS, SN, du C
Les réseaux de neurones pour l’apprentissageESSEC, le 28 Juin 2002Pas d’apprentissagePas d’apprentissage
• Pas d’apprentissage :– trop petit = convergence « lente » vers la solution– trop grand = risque d’oscillations…
heuristiques courantes :– diminuer le pas d’apprentissage au fur et a mesure
• « à la main »• en fonction de la forme de la surface d ’erreur
approximations :• premier ordre
Rétropropagation avec un moment d’inertieDelta-Bar-Delta, Rprop, ...
• second ordreQuickpropLevenberg Marquard
Les réseaux de neurones pour l’apprentissageESSEC, le 28 Juin 2002
• Moment d’inertie (Rumelhart et al. 1986)
avec ||<1
• Delta-Bar-Delta (Jacobs 1988)– calcul d ’un « gradient moyen »– modification du pas d’apprentissage selon la direction du
gradient par rapport au gradient moyen
Premier ordrePremier ordre 1/21/2
1twx.Err.tw jiijji
1tx.Err1t jiijji
onsint
01t.tx.Errsidt
01t.tx.Errsiut
1t
ji
jiijji
jiijji
ji
ijjiji x.Err.ttw
on accélère
on freine
Les réseaux de neurones pour l’apprentissageESSEC, le 28 Juin 2002Premier ordrePremier ordre 2/22/2
• Rprop (Riedmiller and Braun 1993)– modification du pas d’apprentissage selon la direction du
gradient par rapport au gradient précédent– on borne le pas d ’apprentissage
– un poids n’est modifié que s ’il va « dans le bon sens »
onsint
01tx.Errtx.Errsi,dtmax
01tx.Errtx.Errsi,utmin
1t
ji
ijijminji
ijijmaxji
ji
on accélère
on freine
onsin0
01tx.Errtx.Errsix.Errsgnt1tw ijijijji
ji
Les réseaux de neurones pour l’apprentissageESSEC, le 28 Juin 2002Second ordreSecond ordre 1/21/2
• Développement de Taylor de la fonction de coût :
– H = matrice Hessienne, « le Hessien » de du coût
– Calcul du gradient :
– on cherche h / le gradient soit nul
hwh2
1h
w
J)w(JhwJ H
2n
2
1n
2
22
2
12
2n1
2
21
2
21
2
w
J
ww
J
w
J
ww
J
ww
J
ww
J
w
J
H
wh)w(w
Jhw
w
JH
)w(w
Jwhw 1
H Problème = calcul de H-1
Les réseaux de neurones pour l’apprentissageESSEC, le 28 Juin 2002Second ordreSecond ordre 2/22/2
• Approximation du Hessien :– hessien = matrice diagonale
– Quickprop (Fahlman 1988)• on évite de calculer H
– Il existe d’autres méthodes qui calculent (partiellement) les informations du 2nd ordre méthodes de gradient conjugué
2
2
w
J
w
J)t(w
)t(w
)t(ww
J)1t(w
w
J
w
J2
2
)1t(ww
J)t(w
w
J
)t(ww
J
)1t(w)t(w
Les réseaux de neurones pour l’apprentissageESSEC, le 28 Juin 2002ConclusionConclusion
– La rétropropagation est une méthode de gradient
– on a un problème d’optimisation à résoudre,….. …. Et tous les coups sont bon !
– On a un problème d’optimisation non linéaire convexe si la fonction coût est quadratique
– Soft : matlab (petits problèmes) - SN (gros problèmes)
Les réseaux de neurones pour l’apprentissageESSEC, le 28 Juin 2002BibliographieBibliographie
• Neural Networks : a comprehensive foundation - S. Haykin (Prenctice Hall)
• Neural Networks : a systematic introduction R. Rojas (Springer)
• The Handbook of Brain Theory and Neural Networks - M.A. Arbib (MIT Press)
• Self-Organizing Maps - T. Kohonen (Springer)• Réseaux Neuronaux et Traitement du Signal - J. Hérault & C.
Jutten (Hermès)• Backpropagator ’s review :
– des informations sur la rétropropagation• http://www.dontveter.com/bpr/bpr.html
– un petit tutoriel :• http://www.dontveter.com/bpr/public2.html
Recommended