Chapitre 5
Mémoires associatives
Plan
Architecture
Phases d’opérations
Catégories
Entraînement
Hebb
Delta
Mémoire anticipative
Mémoire itérative
Cours #6 GPA-779
- 2 Application des réseaux de neurones et des systèmes experts
Découverte
3 livres du groupe PDP
Vol. 1: théorie 1986
Vol. 2: modèles bio. 1986
Vol. 3: modèles
informatiques 1988
successeur: PDP++ 2003
[Link]
/PDP++/PDP++.html
Bibles de l’époque
Modèles info. PC-MAC-
UNIX
1. Rumelhart, D.E., J.L. McClelland, and the PDP Research Group, eds.
Parallel Distributed Processing - Explorations in the Microstructure of
Cognition. Volume 1: Foundations. Computational Models of Cognition and
Bases de la rétropropag.
Perception, ed. J.A. Feldman, P.J. Hayes, and D.E. Rumelhart. Vol. 1.
1986, The MIT Press: Cambridge, Massachusetts. 547.
2. McClelland, J.L., D.E. Rumelhart, and the PDP Research Group, eds.
Appendice: analyse
Parallel Distributed Processing - Explorations in the Microstructure of
Cognition. Volume 2: Psychological and Biological Models. Computational
Models of Cognition and Perception, ed. J.A. Feldman, P.J. Hayes, and D.E.
vectorielle
Rumelhart. Vol. 2. 1986, The MIT Press: Cambridge, Massachusetts. 611.
3. McClelland, J.L. and D.E. Rumelhart, Explorations in Parallel
Distributed Processing - A Handbook of Models, Programs, and Exercises.
Cours #6 GPA-779
Computational-Models
3 of Application des réseaux
Cognition and Perception, ed. de
[Link] et des
Feldman, P.J. systèmes experts
Hayes, and D.E. Rumelhart. 1989, Cambridge, Massachusetts: The MIT Press.
Principaux domaines
d ’application
1.
Classification
2. Regroupement
3. Approximation
4. Prédiction
5. Optimisation
de parcours
6. Mémoire
associative
7. Commande
Cours #6 GPA-779
- 4 Application des réseaux de neurones et des systèmes experts
Reconstruction d ’images
Cours #6 GPA-779
- 5 Application des réseaux de neurones et des systèmes experts
• Exemple d’application
Cours #6 GPA-779
- 6 Application des réseaux de neurones et des systèmes experts
5.1 Architecture
x1 y1
x2 y2
W
xN yM
Cours #6 GPA-779
- 7 Application des réseaux de neurones et des systèmes experts
y1
x1
x2 w 1n y2
w 2n
wmn
xn ym
wM
n
xN yM
Cours #6 GPA-779
- 8 Application des réseaux de neurones et des systèmes experts
X = [ x1 x2 L xN ]
Y = [ y1 y2 L yM ]
⎡ w11 w12 L w1n L w1N ⎤
⎢ ⎥
⎢ M M M M M M ⎥
W = ⎢wm1 wm2 L wmn L wmN ⎥
⎢ ⎥
M M M M M M
⎢ ⎥
⎢⎣w M 1 w M 2 L w Mn L w MN ⎥⎦
Y = XW T
€ Y T = WX T
Cours #6 GPA-779
- 9 Application des réseaux de neurones et des systèmes experts
Phases d’opération
1- Entraînement
Prototype à mémoriser: V k 1 ≤k ≤P
p
Mémorisation: W = ∑ W (k)
k:1
Entrée: Tk
2- Recherche Y = XW T
Y T = WX T
Cours #6 GPA-779
- 10 Application des réseaux de neurones et des systèmes experts
Catégories
1- Mémoire auto- Tk → Vk V =T 1 ≤k ≤P
associative k k
2- Mémoire héréro- Tk → Vk V ≠T 1 ≤k ≤P
associative k k
Cours #6 GPA-779
- 11 Application des réseaux de neurones et des systèmes experts
5.2 Entraînement
Règle de Hebb
Algorithme
0- Initialisation
Wmn = 0
1- Pour chaque paire T : V
2- xn = tn
3- ym = vm
4- Wmn = Wmn(précédent) + xnym
Cours #6 GPA-779
- 12 Application des réseaux de neurones et des systèmes experts
Algorithme alternatif: produit externe de vecteurs
⎡t1v1 L t1vm L t1vM ⎤
⎢ M M M⎥
⎢ ⎥
Wk = Tk oVk = TkT × Vk = ⎢t n v1 L t n v1 L t n vM ⎥
⎢ M M M⎥
⎢ ⎥
⎢t N v1 L
⎣ t N v1 L ⎥
t N vM ⎦
P
W = ∑TkT × Vk
k =1
W0 = W −PI
Cours #6 GPA-779
- 13 Application des réseaux de neurones et des systèmes experts
Phase de recherche
X = Tk =l = Tl
Y = XW T
p
= ∑TlTkT Vk
k:1
= TlTl T Vl + ∑TlTkT Vk
k ≠l
1- Entrées non-corrélées (vecteurs orthogonaux)
recouvrement total et parfait
2- Entrées corrélés
recouvrement croisé (bruit d’intercorrélation)
Cours #6 GPA-779
- 14 Application des réseaux de neurones et des systèmes experts
Capacité d’emmagasinement
– Maximum: N-1 (si tous les vecteurs
d’apprentissage sont orthogonaux)
– Pour un réseau de Hopfield (mémoire itérative):
N
< P < 0,15 N
2 log 2
Cours #6 GPA-779
- 15 Application des réseaux de neurones et des systèmes experts
Règle Delta
Règle itérative utilisée pour des vecteurs à
mémoriser qui sont linéairement indépendants
mais non-orthogonaux. La règle atténue les effets
de corrélation croisée et produit une solution de
moindres carrés lorsque les vecteurs ne sont pas
linéairement indépendants
xi = ti
⎛ ⎞
y j = f ⎜∑ xi w ji = net j ⎟
⎝ i ⎠
Δwij = η f ′(net j ) (v j −y j ) xi
Cours #6 GPA-779
- 16 Application des réseaux de neurones et des systèmes experts
5.3 Mémoires anticipatives
Algorithme
1- Entraînement
a) Hebbien
b) Delta
2- Forme (partielle ou bruitée) présentée à l’entrée
netj = ∑ xi w ji
i
netj > 0
1
yj = 0 netj = 0
−1 netj < 0
Cours #6 GPA-779
- 17 Application des réseaux de neurones et des systèmes experts
5.4 Mémoires itératives
5.4.1 Réseau de Hopfield
y1 y3
-2
1 1
wij = w ji
1 wii = 0
+4 +1
x1
-1
⎧1
⎪
∑w ij y j ≥0
1 yi = ⎨ j
x2 y2 ⎪−1 ∑w ij yj < 0
⎩ j
Cours #6 GPA-779
- 18 Application des réseaux de neurones et des systèmes experts
Énergie d’un réseau de Hopfield
Cours #6 GPA-779
- 19 Application des réseaux de neurones et des systèmes experts
Algorithme
1- Entraînement: mémoriser les couples T:V
P
W = ∑TkT Vk −PI
k =1
2- Forme (partielle ou bruitée) présentée à l’entrée
yi = x i
Relaxation:
Pour chaque neurone (pris au hasard):
neti = xi + ∑ y j wij
j
1 neti > θ i
yi = yi neti = θ i
−1 neti < θ i
Cours #6 GPA-779
- 20 Application des réseaux de neurones et des systèmes experts
Un réseau simple de Hopfield
Cours #6 GPA-779
- 21 Application des réseaux de neurones et des systèmes experts
Relaxation
6 7
+1
2 1
-1
5 4 3
Cours #6 GPA-779
- 22 Application des réseaux de neurones et des systèmes experts
Les états stables du réseau
Cours #6 GPA-779
- 23 Application des réseaux de neurones et des systèmes experts
Un réseau de Hopfield comme MA
N
< P < 0,15 N
2 log 2
Cours #6 GPA-779
- 24 Application des réseaux de neurones et des systèmes experts
5.4.2 Mémoire associative
bidirectionnelle - BAM
Cours #6 GPA-779
- 25 Application des réseaux de neurones et des systèmes experts
Exercice
Trouver la matrice de transformation W
(poids) pour emmagasiner les patrons:
»t1=[1 1 -1 -1];
»t2=[-1 1 1 -1];
Cours #6 GPA-779
- 26 Application des réseaux de neurones et des systèmes experts
Solution
»t1=[1 1 -1 -1]; »W=W1+W2
»t2=[-1 1 1 -1];
W=
»W1=t1'*t1
W1 =
2 0 -2 0
0 2 0 -2
1 1 -1 -1
-2 0 2 0
1 1 -1 -1
0 -2 0 2
-1 -1 1 1
-1 -1 1 1
» W0=W-2*eye(4)
»W2=t2'*t2
W0 =
W2 =
0 0 -2 0
1 -1 -1 1
0 0 0 -2
-1 1 1 -1
-2 0 0 0
-1 1 1 -1
0 -2 0 0
1 -1 -1 1
Cours #6 GPA-779
- 27 Application des réseaux de neurones et des systèmes experts