Réseaux de neurones - Formations en Informatique de …decomite/ue/MFFDD/NN.pdf · R eseaux de neurones F. De Comite Licence-Master Informatique 21 mars 2011 F. De Comite R eseaux

Reseaux de neurones

F. De Comite

Licence-Master Informatique

21 mars 2011

F. De Comite Reseaux de neurones

Notes

Fonctionnement du cerveau


Notes

Cerveau

Neurones connectes par l’intermediaire des synapses

Activation depend du niveau de stimuli.

’Declenchement’ −→ notion de seuil d’activation.

Neurone = unite elementaire de calcul.


Notes

Cerveau

Reseau tres fortement interconnecte de neurones.

100 milliards de neurones.

10.000 connections par neurones.

Temps de reaction d’un neurone : un millieme de seconde.

Reconnaıtre un visage : 1 dixieme de seconde.


Notes

Vers l’informatique

Comment utiliser ces observations ?

Simuler le fonctionnement du cerveau pour mieux lecomprendre (neuro-biologistes)

Deduire de ces observations un modele de calcul(informaticiens).

Programmation simple :

Definir un neurone.

Definir l’architecture du reseau.

Faire circuler les stimuli . . .


Notes

Biologie ←→ Informatique

Frontiere floue entre les deux domaines :

Les definitions viennent de la neurobiologie, sontimplementees en informatique.

Experiences definies par les neurobiologistes, prouvees depuissance limitee par les informaticiens.

Conclusion des informaticiens servant d’arguments auxneurobiologistes.


Notes

Plan

On se concentre sur la vision purement informatique, en limitantles ambitions (par rapport au ’vrai’ cerveau) :

Neurones limites : puissance de calcul, nombre de connections. . .

Structure du reseau :

’Peu’ de neurones.’Peu’ de connections.Fonctionnement synchrone.Informations moins riches (booleens, reels).


Notes

Un premier modele : MacCulloch & Pitts


Notes

MacCulloch & Pitts

1943

Entrees et sorties booleennes (θ reel).

Si un seul inhibiteur vaut vrai, la sortie vaut faux.

Sinon, on calcule∑

xi :

≥ θ =⇒ f = vraif =faux sinon.


Notes

Expressivite : And


Notes

Expressivite : Or


Notes

Expressivite : Not


Notes

Expressivite

Toute fonction logique peut etre synthetisee par un reseau adeux niveaux (cf cours d’architecture).

Ajouter des poids positifs n’augmente pas l’expressivite.

Poids negatifs (inhibition relative) : pas plus puissant.

Passer du binaire au discret (plus de deux valeurs) ne changerien (cout du codage . . .)

Autoriser un stockage d’information dans les neurones (cfbascules JK) ne change rien non plus.


Notes

Critique du modele

Ne ressemble pas a un ’vrai’ neurone.

Trop proche des portes logiques.

Reseaux figes.

Pas d’apprentissage.


Notes

Perceptron de Rosenblatt 1958


Notes

Rosenblatt

Chaque neurone de la region de projection recoit desinformations de certains neurones de la retine.

La region d’association regroupe les infos de plusieursneurones de la zone de projection.

Zone de reponse : reconnaissance de structures sur la retine.

Liaisons aleatoires entre les trois dernieres couches.

Chaque lien associe a un coefficient (poids).


Notes

Rosenblatt

L’apprentissage se fait a partir d’exemples (algorithmenumerique . . .)Neurones : unites lineaires a seuil :

θ

x

x

w

w

11

22

1 si Σ x w > θ0 sinon

ii


Notes

Minsky & Pappert

1960’s

Amelioration et precision du modele de Rosenblatt.

Analyse complete du modele.


Notes

Minsky & Papert

W1

W2

W3

W4

W5

θ

Retine Predicats Neurone


Notes

Minsky & Papert

Retine : tableaux de pixels (noir et blanc).

Predicats : peuvent tout calculer.

Contraintes :

Nombre d’entrees borne.Diametre borne.

Neurone lineaire a seuil en sortie (reconnaissance de formes)

les xi sont des reels.


Notes

Minsky & Papert

Quelles formes peut-on reconnaıtre ?

Quelles sont les formes que l’on ne pourra pas reconnaıtre ?


Notes

Minsky & Papert

Applications du modele :

Savoir si un pixel est sur une frontiere.

Savoir si un pixel est sur une frontiere localement verticale(resp horizontale)

Un predicat par pixel.


Notes

Minsky & Papert

Aucun neurone a diametre borne ne peut reconnaıtre la connexite

A D

B C


Notes

Minsky & Papert

Aucun neurone a diametre borne ne peut reconnaıtre la connexite


Notes

Perceptron


Notes

Perceptron equivalent


Notes

Calcul de fonctions booleennes : AND


Notes

Calcul de fonctions booleennes : OR


Notes

Calcul de fonctions booleennes : NOT


Notes

Calcul de fonctions booleennes

Au moins m entrees a 1 parmi n.

On peut prendre tous les poids egaux (symetrie).

kw1 > θ pour k ≥ m

kw1 ≤ θ pour k < m

On peut prendre : w1 = 1 et θ = −(m − 1)


Notes

Calcul de fonctions booleennes

Sur les 16 fonctions booleennes a deux variables, 14 peuventetre reconnues par un perceptron : il manque l’egalite et leXOR.

Fonctions de trois variables : 104 sur 256

Quatre variables : 1882 sur 65536


Notes

XOR

w1 + w2 − θ < 0

w1 − θ ≥ 0

w2 − θ ≥ 0

−θ < 0

θ ≥ 0 =⇒ w1 ≥ θetw2 ≥ θ

=⇒ w1 + w2 ≥ 2θ =⇒ w1 + w2− θ ≥ θ ≥ 0


Notes

Pouvoir d’expression

La conditionn∑

i=0

wi xi = 0

definit un hyperplan dans un espace de dimension n.

Un perceptron permet de representer les ensembles d’exempleslineairement separables.

Le XOR ne definit pas un ensemble d’exemples lineairementseparables.


Notes

Separation lineaire : OR

(0,0)

(0,1)

(1,1)

(1,0)


Notes

Separation lineaire : AND

(0,0)

(0,1)

(1,1)

(1,0)


Notes

Apprentissage des perceptrons

Par resolution d’un systeme d’inequations.

Par apprentissage :

Apprentissage exact.Minimisation de l’erreur.


Notes

Apprentissage

1 Fixer des poids aleatoires.

2 Presenter les exemples un par un, modifier les poids pour lesajuster au resultat attendu (zero erreur ou erreur minimale).


Notes

Apprentissage exact

Notation

Soient wi , i ∈ {1 . . . n} les poids du perceptron.

Soit (~x , t) un exemple, ou t est la valeur attendue en sortie (0ou 1), et ~x = (x1 . . . xn).

Soit o la valeur calculee par le perceptron(0 ou 1).


Notes

Modifier les poids

Si l’exemple et bien classe, on ne fait rien.

Sinon, on modifie tous les poids :

wi = wi + ∆wi

∆wi = η(t − o)xi

avec η : taux d’apprentissage.

On s’arrete lorsque tous les exemples sont bien classes.


Notes


Soit un exemple positif mal classe (t = 1, o = 0)

wi′ = wi + η(1− 0)xi = wi + ηxi

Dans le calcul de la sortie du perceptron :

wi′xi = (wi + η(1− 0)xi )xi

wi′xi = wi xi + ηx2

i

Ajout d’un terme positif a un terme a une somme negative.

La sortie du perceptron, pour l’exemple ~x se rapproche des positifs.

La vitesse de ce rapprochement depend de η


Notes


Pour un exemple negatif mal classe :

wi′xi = wi xi − ηx2

i

La somme se rapproche des negatifs.


Notes

Exemple


Notes

Convergence

Theorem

La regle du perceptron converge en un temps fini si :

L’ensemble d’apprentissage est lineairement separable.

η n’est pas trop grand. (de l’ordre de 0.1).


Notes

Convergence

Remarque

Ne converge pas si l’ensemble n’est pas lineairement separable.

Pas de solution approchee dans ce cas.

Sensible au bruit de classification.


Notes

L’algorithme Pocket

Gallant (1990) : memoriser la solution qui commet le moinsd’erreurs.

Si une autre combinaison de valeurs des poids commet moinsd’erreurs, on la memorise (on la met dans sa poche).

Sous certaines conditions, on converge presque surement versla solution optimale.


Notes

La descente de gradient

Methode d’apprentissage moins ’efficace’ mais marchanttoujours . . .

Peut s’utiliser meme quand l’ensemble n’est pas lineairementseparable.

Converge vers un minimum local d’erreur.

Quelle erreur ?


Notes

Perceptron lineaire

Le perceptron lineaire : un perceptron sans unite de seuil.


Notes

La notion d’erreur

definitionErreur quadratique :

E (~w) =1

2

∑d∈D

(td − od )2

D : ensemble des exemples.

td : valeur reelle de la sortie.

od : valeur calculee par le perceptron.

RemarquePour un ensemble d’apprentissage fixe D, l’erreur est fonction deswi .


Notes

Erreur quadratique

Bonne proprietes mathematiques (voir preuve . . .)

Justification (bruit de mesure).

Penalise les solutions exactes presque partout et mauvaises enquelques (rares) points.


Notes

Minimiser l’erreur

E (w) est un paraboloıde (dimension n).

Il faut trouver les valeurs de wi qui correspondent au ’fond’ decette surface.

Pour une erreur donnee : trouver la direction de plus grandepente.

−→ le gradient.


Notes

Forme de l’erreur

-1

0

1

2

-2-1

01

23

0

5

10

15

20

25

w0 w1

E[w

]


Notes

Le gradient

Pente d’une courbe f (x) en dimension 2 :

f ′(x) =∂f (x)

∂x

Direction de la plus grande pente en dimension n :

∇E (~w) =

[∂E

∂w0. . .

∂E

∂wn

]

Comment calculer∂E

∂wi?


Notes

Derivation de la regle

∂E

∂wi=

∂

∂wi

1

2

∑d∈D

(td − od )2

=1

2

∑d∈D

∂(td − od )2

∂wi

=1

2

∑d∈D

2(td − od )∂(td − od )

∂wi


Notes

Derivation de la regle

=∑d∈D

(td − od )∂

∂wi(td − woxod

· · · − wnxnd)

=∑d∈D

(td − od )∂(−wi xid )

∂wi

= −∑d∈D

(td − od )xid


Notes

derivation de la regle

∆wi = η∑d∈D

(td − od )xid

Remarques

Le signe moins a disparu : on descend la pente !

η controle la longueur de la descente.


Notes

Algorithme

1 Fixer des poids aleatoires.2 Repeter :3 ∆wi = 0,∀i ∈ {0 . . . n}4 Pour chaque ~x ∈ D faire :5 ∆wi = ∆wi + (tx − ox )xi6 fait7 Pour tout i ∈ {0 . . . n} faire8 wi = wi + ∆wi9 fin repeter


Notes

Remarques

Il n’y a qu’un minimum.

On est assure de l’atteindre si η n’est pas trop grand ( ? ?)

La convergence peut etre tres longue.

Version stochastique : les poids sont modifies apres lapresentation de chaque exemple.


Notes

Comparaison des methodes

Regle du perceptron Descente du gradient

Ensemble lineairementseparables

Ensembles quelconques

Converge vers la solution. Converge vers le minimum d’er-reur.

poids modifies en cas d’erreur. poids modifies pratiquementtout le temps


Notes

Remarques

Necessite des attributs et des classes continues.

Besoin de coder les donnees :En entree :

du discret au continu.Une entree par valeur possible.

En sortie :

Du continu au discret.Du binaire au n-aire.

Mettre les entrees a la meme echelle.


Notes

Codage des sorties

Les sorties sont forcement entre 0 et 1.

Coder les sorties dans l’ensemble d’apprentissage.

Decoder les reponses du reseau.

Continu : pas de probleme.

Discret : decouper l’intervalle ou une sortie par possibilite(tout garder. . .)


Notes

Reseaux de neurones

Idees

Combiner des perceptrons lineaires.

Probleme : pas de puissance supplementaire : unecombinaison lineaire d’operateurs lineaires est toujours unoperateur lineaire.

Utiliser des perceptrons a seuil ?

Probleme : pas derivable, pas de descente de gradient.


Notes

L’unite sigmoıde


Notes

La fonction sigmoıde


Notes

La fonction sigmoıde

Continue, derivable.

Passe rapidement de 0 a 1 : similitude avec le perceptron aseuil.

Derivee facile a calculer :

dσ(x)

dx= σ(x)(1− σ(x))


Notes

Architecture du reseau

Une couche d’entree.

Une ou plusieurs couches cachees.

Une couche de sortie.

Tous les neurones d’une couche sont les entrees des neuronesde la couche suivante.


Notes

Reseau de neurones


Notes

Erreur

E (~w) =1

2

∑i∈D

∑k∈sorties

(tkd − okd )2

avec

tkd k ieme sortie de l’exemple d

okd la valeur de cette sortie calculee par le reseau.


Notes

Retropropagation du gradient

Idee similaire a la descente du gradient.

Mais il n’y a plus unicite du minimum.

La surface d’erreur est complexe.

Existence de minima locaux.


Notes

Retropropagation du gradient : notations

xji : valeur transmise du nœud i vers le nœud j

wji : poids associe a xji

δj : terme d’erreur du nœud j

netj =∑

wji xji


Notes

Retropropagation du gradient : notations

I

J σ

xji

wji NETj oj

δj


Notes

Algorithme (stochastique)

Tant que non fini faire :

Faire passer (~x ,~t) dans le reseau. Sortie : ~o

Calculer et (retro)propager les erreurs :

Cellule de sortie :

δk = ok (1− ok )(tk − ok )

Cellule interne :

δh = oh(1− oh)∑

k

wkhδk

Mettre a jour les poids :

wji = wji + ηδj xji


Notes

Idee de preuve

minimiser : E (~w) =1

2

∑i∈D

∑k∈sorties

(tkd − okd )2

(erreur quadratique).

descente de gradient :

∇E (~w) =

[∂E

∂w0. . .

∂E

∂wn

]


Notes

Idee de preuve

∂E

∂wji=

∂E

∂netj×∂netj

∂wji

(wji n’influence l’erreur que par l’intermediaire de netj )

∂E

∂wji=

∂E

∂netj× xji


Notes

Idee de preuve (couche de sortie)

Quid de∂E

∂netj?

Cellule de sortie :

∂E

∂netj=∂E

∂oj×

∂oj

∂netj

∂oj

∂netj=∂σ(netj )

∂netj= oj (1− oj )


Notes

Idee de preuve (couche de sortie)

∂E

∂oj=

∂

∂oj

1

2

∑k∈outputs

(tk − ok )2

∂E

∂oj=

∂

∂oj

1

2(tj − oj )

2

∂E

∂oj= −(tj − oj )

Finalement :

∆wji = −η ∂E

∂wji= η(tj − oj )oj (1− oj )xji


Notes

Idee de preuve (couche cachee)

∂E

∂wji=∂

E∂netj × xji

∂E

∂netj=

∑k∈aval

∂E

∂netk× ∂netk

∂netj

∂E

∂netj=

∑k∈aval

−δk ×∂netk

∂netj


Notes


∂netk

∂netj=∂netk

∂oj×

∂oj

∂netj

∂netk

∂oj= wkj

∂oj

∂netj= oj (1− oj )


Notes


Cellule de la couche cachee : le terme d’erreur de la cellule est lasomme coefficientee des termes d’erreurs des cellules en aval.

∂E

∂wji=

∂E

∂netj×∂netj

∂wji

∂E

∂netj=

∑k∈aval

−δk × wkj oj (1− oj )

∂netj

∂wji= xji

δj = − ∂E

∂netj

∆wji = ηδj xji


Notes

Stochastique/ non stochastique

Version non stochastique : cumuler les modifications de poidsavant de les appliquer.

Version stochastique : modifier les poids apres chaqueexemple.

La version stochastique plus efficace en pratique.


Notes

Minima locaux

Surface d’erreur accidentee : convergence vers un minimumlocal.

’secouer les poids’.

Ajouter un moment (une inertie) pour se rappeler de ladirection du mouvement precedent :

∆wji (n) = ηδj xji + α∆wji (n − 1)


Notes

Remarques diverses

Condition d’arret ?

sur-specialisation ?


Notes

Exemple 1 : Alvinn (Pomerleau 1993)

Sharp Left

SharpRight

4 Hidden Units

30 Output Units

30x32 Sensor Input Retina

Straight Ahead


Notes

NETtalk

Sejnowski & Rosenberg 1986.

Prononciation d’un texte.

Entree : Fenetre de 7 caracteres.

Sorties possibles : Liste de phonemes.

Phoneme associe au caractere central de la fenetre.


Notes

NETtalk

H E L L O _ W

29 neurones 29 neurones 29 neurones 29 neurones

80 neurones

26 phonèmes


Notes

NETtalk

Apprentissage : plusieurs centaines de mots et leurtranscription phonetique.

Connecte a un synthetiseur vocal.

Suivi de l’evolution de l’apprentissage.


Notes

NETtalk : analyse

Erreurs d’enfants initiales.

Troubles du langage en abımant certains neurones ( ? ? ?)

Analyse de la couche cachee : apprentissage de regleslinguistiques.


Notes

Probabilites

On dirait que le reseau fournit en sortie la probabilite du phonemeen fonction :

Du caractere et de son environnement.

De l’ensemble sur lequel il a appris.

C’est vrai sous certaines conditions.


Notes

Reconnaissance des chiffres manuscrits

60.000 chiffres manuscrits : matrice 20x20 pixels, 256 niveauxde gris.

Comparaison de plusieurs methodes :

3-plus proches voisins : erreur 2.4 %Reseaux de neurones : 400 entrees, 10 sorties, 300 neuronesdans la couche cachee : 1.6% d’erreur.Reseaux specialises : 0.9%Humains : 0.2% ou 2.5%


Notes

Reconnaissance de caracteres

26 lettres (matrices 5x7).

But : reconnaıtre la lettre.

10 neurones dans la couche cachee.


Notes



Notes



Notes



Notes



Notes

Reconnaissance de visages


Notes

Valeurs minimales des gradients

∆ωi = −γ ∂E

∂ωi+ ε

∆ωi = max(−γ ∂E

∂ωi, ε)


Notes

Pas (=step. . .) adaptatifs

Idee : eviter de rester bloque dans un creux.Silva et Almeida :

Chaque poids ωi a son propre taux d’apprentissage γi

ωi croıt si ∆ωi a garde le meme signe deux fois de suite.

Sinon, γ decroıt.


Notes

Rprop

Meme principe que Silva et Almeida.

les γi sont bornes.

∆ωi = −γ × signe(∂E

∂ωi)


Notes

Methodes de deuxieme ordre

Methodes du gradient : utiliser la derivee de la fonction d’erreurpour trouver un algorithme.Methodes du deuxieme ordre : utiliser aussi les derivees secondes :convergence plus rapide : QuickProp


Notes

Puissance

Toute fonction booleenne peut etre representee par un reseaua deux couches (une cachee, une de sortie).

Toute fonction continue peut etre representee par un reseau adeux couches (une cachee, une de sortie).


Notes

Fonctions continues

x x x2 3 4

Y

Y

Y

0

1

2

x1


Notes

Fonctions continues

X

X−1

X

X−1

0

1

1

2

x

g(x)

Y0

Y1

Yn−1


Notes

Deux entrees,un neurone

sigmoide(x+y)

-10-5

05

10 -10

-5

0

5

10

00.10.20.30.40.50.60.70.80.9

1


Notes

Deux neurones caches

sigmoide(sigmoide(x+y+0.5)+sigmoide(-x-y+0.5))

-4-2

02

4-4

-2

0

2

4

0.730.7350.74

0.7450.75

0.7550.76

0.7650.77

0.7750.78


Notes

Quatre neurones caches

-4 -2 0 2 4x1-4

-20

24

x2

00.10.20.30.40.50.60.70.80.9

1hW(x1, x2)


Notes

Frontieres

F1 F2

head hid who’d hood... ...


Notes

Frontieres


Notes

Le multiplexeur

On force le circuit a memoriser huit valeurs sur trois neurones.Suffisamment de liberte : codage binaire !Converge.


Notes

Codage

Entree neurone 1 neurone 2 neurone 3 seuil10000000 0.992 0.544 0.011 11001000000 0.011 0.036 0.896 00100100000 0.551 0.002 0.137 10000010000 0.339 0.995 0.014 01000001000 0.967 0.105 0.992 10100000100 0.992 0.995 0.966 11100000010 0.009 0.973 0.983 01100000001 0.006 0.356 0.010 000


Notes

Codage avec deux neurones

Entree neurone 1 neurone 210000000 0.67 1.0001000000 0.7 000100000 1 0.2500010000 0 0.2200001000 0 0.6300000100 0.25 000000010 1 0.7200000001 0.22 1


Notes

Resume

Entrees ’larges’

Sorties : discretes, reelles, multiples.

Resistant au bruit.

Classification rapide (mais apprentissage lent . . .)

Modele non explicatif (boıte noire)


Notes

Documents

Réseaux de neurones - Formations en Informatique de …decomite/ue/MFFDD/NN.pdf · R eseaux de neurones F. De Comite Licence-Master Informatique 21 mars 2011 F. De Comite R eseaux