LES RÉSEAUX NEURONAUX: MÉMOIRES ASSOCIATIVES
Ce chapitre s´inspire de [Abdi 1994]
Les mémoires
Dans les ordinateurs traditionnels les informations sont stockées
dans des mémoires adressables: Une information est connue par son
adresse et si celle-ci est perdue son contenu aussi et il n´y a aucun
moyen de le retrouver.
Le concept de mémoire associative est très différent: Une information
peut être retrouvée si on fournit un pattern lui ressemblant (soit une
partie de l´information, soit l´information bruitée). Plus généralement
il s´agit d´associer un stimulus en entrée à une réponse en sortie
(comme le fait le perceptron).
On distinguera les mémoires "hétéro-associatives
et les mémoires
auto-asociatives. Les premières, tout comme le perceptron
(voir chapitre 4),
ne comportent que deux couches: Une couche d´entrée
et une couche de sortie reliées par des connexions de poids modifiables
lors d´un apprentissage. Les deuxièmes ne comportent qu´une seule
couche, tous les neurones étant reliés entre eux. À la différence du
perceptron qui est constitué de cellules binaires (réponse 0 ou 1),
les mémoires associatives ont des sorties continues.
Mémoires hétéro-associatives linéaires
Définitions
Les neurones d´une mémoires associatives linéaires ont une
réponse proportionnelle à leur activation:
Avec:
aj = activation de la cellule de sortie numéro j.
oj = réponse de cette cellule.
xi = sortie de la cellule numéro i de la rétine.
wi,j = poids de la connexion i -> j.
c = constante (généralement comprise entre 0 et 1).
On utilisera des notations matricielles:
W = [wi,j] = matrice d´ordre I * J des poids des connexions i -> j
reliant les cellules de la rétine aux cellules de sortie.
X = [xi,k] = matrice d´ordre I * K des K stimuli, xk correspondant à
la colonne numéro k de X. Les vecteurs sont supposés normalisés:
||xk|| = 1
A = [aj,k] = matrice d´ordre J * K des activations des J cellules de
sortie pour les K stimuli. L´activation de l´ensemble du réseau pour
le stimulus numéro k est
donnée par le vecteur ak (colonne numéro k de A).
O = [oj,k] = matrice d´ordre J * K des réponses des J cellules de
sortie pour les K stimuli. La réponse de l´ensemble du réseau pour le
stimulus k est donnée par le vecteur ok (colonne numéro k de O).
T = [tj,k] = matrice d´ordre J * K des réponses théoriques
(souhaitées) des cellules de sortie pour les K stimuli. La réponse
théorique de l´ensemble du réseau pour le stimulus numéro k
est donnée par le vecteur tk (colonne numéro k de T).
La mémoire hétéreo-associative linéaire définie par ce réseau
devra associer un état J de la sortie à un état I de la rétine, ce
qui revient à trouver la matrice W des poids telle que:
tk = ok = WT * xk quel que soit k.
Figure 7-1
Règle de Hebb
Cas d´un seul stimulus
Les poids sont donnés par:
wi,j = c * (tj * xi) (1)
Posons c = 1, on obtient la règle de Hebb selon laquelle si un
axone de la cellule A participe à l´excitation de la cellule B de
façon répétitive ou persistante, alors l´efficacite de la cellule A
pour exciter B est accrue. C´est à dire que le poids wi,j de la
connexion i -> j est proportionnelle au produit du stimulus xi et
de la réponse théorique tj:
En effet, en posant W = |W1 W2 ...|, on a, en appliquant la formule (1)
pour le stimulus 1:
ou plus généralement: W1T = t1 * xiT
o1 = W1T * x1 = t1 * x1T * x1
Mais x1T * x1 = 1 d´ou
o1 = t1
Cas de plusieurs stimuli
Généralisons la formule précédente pour plusieurs stimuli:
Si les stimuli en entrée sont deux à deux orthogonaux, le mémoire
hétéro-associative linéaire permet d´associer parfaitement les stimuli
en entrée aux réponses souhaitées:
Si les stimuli en entrée sont "orthogonaux", c´est à dire si leurs
produits scalaires deux par deux sont nuls:
Alors, dans ce cas, le réseau reconnaît parfaitement les stimuli en entrée,
c´est à dire que la sortie ol est égale à la sortie
théorique tl, en effet:
Si les stimuli en entrée ne sont pas orthogonaux, alors la sortie est:
En supposant les entrées unitaires:
||xk|| = ||xl|| = 1
cos(xk,xl) peut s´interpréter comme une
ressemblance des entrées xk et xl. La réponse
du réseau est donc la réponse théorique corrigée par les réponses aux
autres stimuli xk pondérées par leur ressemblance avec le
stimulus xl.
Règle de Widrow-Hoff
La règle de Widrow-Hoff
s´exprime par:
wij(t + 1) = wij(t) + n * (tj - oj) * xi = wij(t) + dwij
wi,j(t + 1) = poids de la liaison i -> j au temps t + 1
wi,j(t) = poids de la liaison i -> j au temps t
xi = sortie (0 ou 1) de la cellule i de la rétine
oj = réponse de la cellule j de sortie
tj = réponse théorique (souhaitée) de la cellule j de sortie
n = constante positive (entre 0.0 et 1.0), qu´il est préférable de
faire décroître au cours de l´apprentissage.
Solution optimale
Soit oj,k la réponse de la cellule de sortie numéro j
au stimulus en entrée numéro k et soit tj,k la réponse
théorique. L´erreur commise est:
ej,k = tj,k - oj,k
La meilleure solution s´obtient en minimisant ces erreurs pour
tous les j et tous les k, pour cela on cherche à minimiser la
somme de leurs carrés:
On cherche donc w tel que:
o = WT * w
minimisant Q. Si les K stimuli d´entrée sont linéairement
indépendants on sait qu´il existe une solution:
w = X * (XT * X)-1 * t
En effet:
[X * (XT * X)-1]-1 = ((XT * X)-1)-1)-1 * X-1
= (XT * X) * X-1
= XT * (X * X-1) = XT
Le nombre de reconnaissances parfaites de stimuli qu´une mémoire
hétéro-associative peut stocker est donc au plus égale au nombre I
de cellules d´entrée.
Sinon (c´est à dire si les K stimuli d´entrée ne sont pas
linéairement indépendants), (XT * X) n´est pas inversible
et il n´y a peut être pas de solution.
Application à la règle de Widrow-Hoff optimale
Soit f(W) la fonction donnant l´erreur globale du réseau et
définie par:
La
méthode du gradient
et celle de son
ascension stochastique
consiste à
faire évoluer les wi,j dans la direction inverse
du gradient:
Ce qui est la règle de Widrow-Hoff.
Mémoires auto-associatives linéaires
Définitions
C´est une mémoire associative pour laquelle chaque stimulus est
associé à lui-même, elle est de type "auto-adressable" en ce sens
qu´une information peut être retrouvée lorsque l´on n´en donne
qu´une partie (tout comme la mémoire humaine). Une couche d´entrée
est constituée par des capteurs (comme la rétine du perceptron),
chacun étant relié à une cellule de la mémoire, et chaque cellule
de la mémoire est reliée à toutes les autres (voir figure 7-2).
Figure 7-2
Puisque les entrées sont également les sorties, la matrice T des
réponses est égale à la matrice X des stimuli, et les connexions
sont symétriques. D´après la loi de Hebb, on a:
wi,j = c * (xi * xj)
On supposera que c=1.Et les connexions sont symétriques
(car les sorties sont égales aux entrées):
wi,j = c * (xi * xj) =
c * (xj * xi) = wj,i
Stimuli orthogonaux
Si un seul stimulus k est stocké, la matrice W des connexions vérifie:
Wk = WkT = xk * xkT
Elle est symétrique. Calculons la sortie ak pour
l´entrée xk:
ak = Wk * xk = xk * xkT * xk = xk
En supposant les stimulis normés, c´est à dire:
xkT * xk = |xk| = 1
Le réseau restitue donc exactement l´entrée si un seul stimulus est stocké.
Dans le cas général ou plusieurs stimuli sont stockés, on a:
Si les stimuli en entrée sont deux à deux orthogonaux, c´est à dire si:
xiT * xj = 1 pour tout i#j
On a:
Ce qui signifie que les xk sont les vecteurs propres
de la matrice W ayant pour valeurs propres 1 (on dit qu´un vecteur
x est un vecteur propre de la matrice W et de valeur propre c si
W * x = c * x).
Stimuli quelconques
Dans ce cas on a:
Le cosinus peut s´interpréter comme
une ressemblance. Si des stimuli se ressemblent, le réseau les confondera.
On évalue la performance du réseau en calculant la ressemblance
de l´entrée ak et la sortie xk (en supposant les
entrées normées):
Réseaux de Hopfield
Définitions
Les mémoires auto-associatives linéaires que l´on vient de
décrire donnent des réponses qui sont des combinaisons linéaires
des stimuli stockés. Hopfield proposa dans les années 80 des mémoires
auto-associatives non linéaires:
Les réponses du réseau sont binaires et prennent les valeurs 1 ou -1
L´activation de la cellule j est:
aj = activation de la cellule j
xi = sortie (1 ou -1) de la cellule i
wi,j = poids de la connexion i -> j. On suppose que les
cellules ne sont pas auto-connectées, c´est à dire que wi,i = 0
quelque soit i.
La réponse d´une cellule est simplement le signe de l´entrée:
oj = xj = signe(aj)
oj = (aj >= 0) ? 1 : -1
Un stimulus xk est en fait une configuration {1,-1,1,1,...}
du réseau de I cellules. L´ensemble de K stimuli est stocké dans la
matrice X de dimensions I*K. L´ensemble des réponses étant l´ensemble des
entrées, la matrice T des réponses théoriques est égale à X. Soit W
la matrice des poids des connexions de dimensions I*I.
Les cellules calculent leurs activations de manière asynchrone,
c´est à dire une seule fois et dans un ordre aléatoire.
Hopfield a montré en 1982 que si la matrice W est symétrique,
c´est à dire si:
wi,j = wj,i quelque soient i et j
Alors la mise a jours des cellules s´errêtera au bout d´un temps
fini, on dit que le réseau est stable.
Énergie d´un réseau de Hopfield
Le nombre d´états du système est 2I, puisqu´il y a
I cellules pouvant prendre chacune 2 valeurs 1 ou -1.
Par définition l´énergie du système pour un état x (suite ordonnée
de I valeurs 1 ou -1) est:
Exemple pour 3 neurones:
Montrons que E(x) décroît au sens large (c´est à dire décroît ou reste
stable): Il y a tois cas:
1) La cellule j ne change pas d´état après avoir calculé son activation:
Alors E(x) ne change pas non plus.
2) La cellule j passe de l´état 1 à l´état -1 après avoir
calculé son activation: Supposons par exemple que j = 1:
dx1 = x1(t+1) - x1(t) = -1-1 = -2
dE = E(t+1) - E(t) = -0.5 * dx1 * (w1,2 * x2 + w1,3 * x3 + ...)
dE = w1,2 * x2 + w1,3 * x3 + ...
Or l´activation de la cellule 1 est -1, donc son entrée est négative:
w1,2 * x2 + w1,3 * x3 + ... < 0
Donc dE < 0 et l´énergie a diminué.
3) La cellule j passe de l´état -1 a l´état 1 après avoir
calculé son activation:
dx1 = x1(t+1) - x1(t) = 1 - (-1) = 2
dE = - (w1,2 * x2 + w1,3 * x3 + ...)
Or l´activation de la cellule 1 est 1, donc son entrée est positive:
w1,2 * x2 + w1,3 * x3 + ... > 0
Donc dE < 0 et l´énergie a encore diminué
En résumé, quand l´état du réseau change, son énergie ne peut que
rester stable ou décroître, et comme il n´y a qu´un nombre fini
d´états possibles, au bout d´un temps fini, il atteindra
un état d´énergie minimum stable. On dit que l´énergie E est une fonction
de Lyapunov du système. On appelle l´état final stable du réseau un
"attracteur" de la mémoire pour l´entrée initiale. L´ensemble des
attracteurs est l´ensemble de ses états stables, c´est aussi l´ensemble
des configurations qu´il a pu mémoriser.
Quand un réseau de Hopfield converge, il trouve un minimum de
sa fonction d´énergie, mais comme l´ordre de mise à jour de ses
cellules est aléatoire, il n´est pas garanti de trouver le même
attracteur en partant de la même entrée. Les attracteurs correspondant
à la même entrée constituent des "minimums locaux", le meilleur
d´entre eux est le minimum global que l´on n´est pas sur d´atteindre
(voir les machines de Boltzmann).
Reseau de Hopfield continu
En remplacant la fonction signe (binaire) par la fonction
"tangente hyperbolique", on obtient une réponse continue qui
ressemble à la
fonction sigmoide,
mais qui varie
entre -1 et 1 au lieu de 0 et 1 (voir figure 7-3)
Figure 7-3
Les machines de Boltzmann
Définition
L´inconvénient majeur d´un réseau de Hopfield est que celui-ci ne
peut que faire décroître sa fonction d´énergie et risque de se
retrouver coincé dans un minimum local et de manquer ainsi le
minimum absolu. Les machines de Boltzmann résolvent ce problème
en autorisant la fonction d´énergie à croître localement. Plus
précisement, au lieu d´avoir une activation déterministe, les cellules
calculent leurs sortie de façon probabilistique de la même manière
que le
perceptron probabiliste.
Dans un système thermique soit:
P(A) = probabilité pour que le système soit dans un état A
P(B) = probabilité pour que le système soit dans un état B
E(A) = énergie du système lorsqu´il est dans l´état A
E(B) = énergie du système lorsqu´il est dans l´état B
et si T est la température du système, on a:
P(A) / P(B) = exp((E(B) - E(A)) / T)
De façon analogue on définit l´état de la cellule par:
out = 1 avec la probabilité p = 1 / (1 + exp(-G/T))
out = -1 avec la probabilité 1-p
T est un coefficient d´ajustement appelé la "température" du réseau.
G = E-1 -E1 avec:
E-1 = énergie du système si la sortie vaut -1
E1 = énergie du système si la sortie vaut 1
Si G > 0: Si la sortie vaut 1 l´énergie est minimisée.
Si G < 0: Si la sortie vaut -1 l´énergie est minimisée.
Propriétés
1) Si la cellule a une énergie minimum, elle peut soit rester dans
le même état, soit changer d´état, donc augmenter son énergie.
2) Si la cellule a une énergie maximum, elle peut soit rester dans
le même état, soit passer à un état d´énergie inférieure. Le rapport
des probabilités pour que la sortie vaille 1 ou -1 est:
3) Si G = 0, c´est à dire si l´énergie du réseau est la même que
la sortie vaille 1 ou -1, alors p / (1 + p) = exp(0) = 1, donc
p = 1-p et donc p = 0.5: La cellule a la même probabilité de
basculer a 1 ou a -1.
4) Si G < 0 et si |G| grand alors exp(G/T) est petit et l´unité a
une faible probabilité de passer à une énergie supérieure.
Pour un G < 0 donné, par exemple G = -1:
p / (1 - p) = exp(-1/T)
Si T augmente alors 1/T diminue et exp(-1/T) augmente.
Si T diminue alors 1/T augmente et exp(-1/T) diminue.
Donc:
Si T augmente la probabilité d´accroître l´énergie augmente.
Si T diminue la probabilité d´accroître l´énergie diminue.
Si T=0 la probabilité d´accroître l´énergie est nulle et on
retrouve un réseau de Hopfield.
5) Si G > 0 alors exp(G/T) est grand et le système va vers des
énergies inférieures.
On commence donc avec un T grand (ce qui permet l´exploration de
niveaux d´énergies élevés) puis on diminue progressivement la
température.