Artificial Neural Network Lecture 6- Associative Memories & Discrete Hopfield networks

Associate Memory & Discrete Hopfield Network

1. 1
CS407 Neural Computation
Lecture 6:
Associative Memories and Discrete
Hopfield Network.
Lecturer: A/Prof. M. Bennamoun

2. 2
AM and Discrete
Hopfield
Network.
„
Introduction
„
Basic Concepts
„
Linear Associative Memory (Hetero-associative)
„
Hopfield’s Autoassociative Memory
„
Performance Analysis for Recurrent Autoassociation Memory
„
References and suggested reading
„
Introduction
„
Basic Concepts
„
Linear Associative Memory (Hetero-associative)
„
Hopfield’s Autoassociative Memory
„
Performance Analysis for Recurrent Autoassociation Memory
„
References and suggested reading

3. 3
Fausett
Introduction… „
To a significant extent, learning is the process of forming associations between related patterns.
„
Aristotle observed that human memory connects items (ideas, sensations, etc.) that are
–S
im
ila
r
–
C
ontrary
–
O
ccur in close proximity (spatial)
–
O
ccur in close succession (temporal)
„
The patterns we associate together may be
–
o
f the
same type or sensory modality
(e.g. a visual
image may be associated with another visual image)
–
o
r of different types (e.g. a fragrance may be
associated with a visual image or a feeling).
„
Memorization of a pattern (or a group of patterns) may be considered to be associating the pattern with itself.

4. 4
„
In this lecture, we will consider some relatively simple (single layer) NNs that can learn a set of pattern pairs (or associations).
„
An associative memory (AM) net may serve as a
highly
simplified model of human memory.
However, we shall not
address the question whether they are all realistic models.
„
AM provide an approach of storing and retrieving data based on content
rather
than
storage address
(info.
storage in a NN is distributed throughout the system in the net’s weights, hence a pattern does not have a storage address)
Introduction… Address-addressable memory
Content-addressable memory

5. 5
Introduction…
„
Each association is an I/P O/P vector pair ,
s
:
f
.
„
Two types of associations. For two patterns
s
and
f
–
If
s
=
f
the net is called auto-associative memory.
–
If
s
!=
f
the net is called hetero-associative memory

6. 6
Introduction… „
In each of these cases, the net not only learns the specific patterns pairs that were used for training, but is also able to recall the desired response pattern when given an I/P stimulus that is similar, but not identical, to the training I/P.
„
Associative recall
–
e
voke associated
patterns
–
r
ecall a pattern by
part of it
–
e
voke/recall with
incomplete/ noisy patterns

7. 7
Introduction… „
Before training an AM NN,
the original patterns must
be converted to an appropriate representation for computation.
„
However, not all representations of the same pattern are equally powerful or efficient.
„
In a simple example, the or
iginal pattern might consist
of “on” and “off” signals, and the conversion could be “on”
Æ
+1 , “off”
Æ
0 (
binary representation
) or
“on”
Æ
+1, “off”
Æ
-1 (
bipolar representation
).
„
Two common training methods
for single layer nets are
usually considered:
–
H
ebbian
learning rule and its variations
–
g
radient descent

8. 8
Introduction… „
Architectures of NN associative memory may be
–
F
eedforward
o
r
–
R
ecurrent (iterative).
„
On that basis we distinguish 4 types of AM:
–
Feedforward Hetero-associative
–
Feedforward Associative
–
Iterative Hetero-associative
–
Iterative associative
„
A key question for all associative nets is
–
h
ow many patterns can be stored before the net
starts to “forget” patterns it has learned previously (storage capacity)

9. 9
Introduction
„
Associative memories
: Systems for
associating the input patterns with the stored patterns (prototypes)
–
Dynamic systems
with feedback networks
–
Static/Feedforward
systems
without
feedback networks
„
Information recording
: A large set of patterns
(the priori information) are stored (memorized)
„
Information retrieval/recall
: S
t
ored
prototypes are excited according to the input key patterns

10. 10
Introduction…
„
No usable addressing scheme exists
–
M
emory information spatially distributed
and superimposed through the network
–
N
o memory locations have addresses
„
Expectations regarding associative memories
–
A
s large of a capacity of
P
stored
patterns as possible
–
D
ata to be stored in a robust manner
–
A
daptability: Addition or elimination of
associations

11. 11
AM and Discrete
Hopfield
Network.
„
Introduction
„
Basic Concepts
„
Linear Associative Memory (Hetero-associative)
„
Hopfield’s Autoassociative Memory
„
Performance Analysis for Recurrent Autoassociation Memory
„
References and suggested reading
„
Introduction
„
Basic Concepts
„
Linear Associative Memory (Hetero-associative)
„
Hopfield’s Autoassociative Memory
„
Performance Analysis for Recurrent Autoassociation Memory
„
References and suggested reading

12. 12
Basic Concepts
B
. Ch
e
n

& Zu
ra
da
„
Associative Mapping of Inputs to Outputs
[
]
x
v
M
=
:

Retreival

13. 13
Basic Concepts „
M
is a general matrix-type operator
–
M
emory Paradigms (taxonomy)
•
D
ynamic systems
•
S
tatic/Feedforward
systems
–
R
ecording and Retrieval •
Recording
–
M
is expressed as the prototype vectors stored
•
Retrieval
–
M
apping:
x
→
v
–
L
inear or nonlinear
–
I
nput a key vector
x
and find a desired vector
v
previous
ly stored in the network

14. 14
Basic Concepts
–
I
nput/Output Relation •
H
eteroassociative
m
emory
–
W
ith same dimens
ionality or not
•
A
utoassociative
M
emory
()
()
()
()
,...,p
i
i
i
i
i
1
for

=
→
≠
x
v
v
x
()
()
()
()
,...,p
i
i
i
i
i
1
for

=
→
=
x
v
v
x
Two sets of
prototype vectors
One set of
prototype vectors
Output
Most for recovery of
undistorted prototypes
Input

15. 15
Basic Concepts „
The most important classes of associative memories are static and dynamic memories. The
taxonomy
is
entirely based on their recall principles.
„
Static Memory
–
R
ecall an I/P response after an input has been
applied in one feedforward pass, and theoretically without delay.
–
N
on-recurrent (no feedback, no delay)
[
]
k
k
M
x
v
1
=
k denotes the index of recursion M
1
is an operator
symbol
Thi
s
eq. Repre
s
e
n
ts a system of
non-linear
algebraic eqs.

16. 16
Basic Concepts
„
Dynamic Memory
–
P
roduce recall as a result of output/input feedback
interactions, which requires time
–
R
ecurrent, time-delayed
–
D
ynamically evolved and finally converge to an
equilibrium state according to the
recursive
formula
[
]
,
2
1
k
k
k
M
v
x
v
=
+
The operator
M
2
operates at present
instant
k
on the present input
x
k
and
output
v
k
to produce the o/p in the next
instant
k+
1
∆
is a unit delay needed for
cyclic
operation. The pattern is associated to itself (auto-
)
Recurrent Autoassociative Memory

17. 17
Basic Concepts
„
The fig. below shows the block diagram of a recurrent heteroassociative memory net.
„
It associates pairs of vectors (
x
(i),
v
(i)
).
Recurrent Heteroassociative Memory
Association of pairs (x,v) This AM operates with a cycle of 2
∆

18. 18
Basic Concepts „
Dynamic Memory
–
Hopfield
model
: a recurrent
autoassociative
network for which the input
x
0
is used to initialize
v
0
, i.e.
x
0
=
v
0
, and the input
is then removed
for
the following evolution
[
]
2
1
k
k
M
v
v
=
+
nonlinear
mapping
[
]
1
k
k
Wv
v
Γ
=
+
Operator M
2
consists of multipli
cation by a weight matrix followed by the
ensemble of non-linear
mapping operations
v
i
= f(net
i)
per
f
or
med by the layer
of neurons

19. 19
Basic Concepts
(
)
()
()
 
 
⋅
⋅
⋅
=
Γ
sgn

....
..........

0

.........
..........
..........
0
....

sgn

0
0
.........

0

sgn
–
Discrete Hopfield
model
:
•
O
perated on bipolar binary values (
±
1)
•
H
ard-limiting (binary) activation function
(
)(
)
i
i
i
net
net
f
v
sgn
=
=

20. 20
Basic Concepts
1/ If the transitions ter
m
inate with a state mapping
into itself, as in the case
of node A, the the equilibrium
A is the fixed point solution (equilibrium)
Equilibrium states Reg
a
rdi
ng the vector
v
(k+1
)
as the
state of the network
at the (k
+1)’th instant we can
consider the rec
u
rrent equation

as defining a mapping of the vector
v
into
Itself. The example state transition map for
a me
mory
network can be represented as
shown on the fig. below. Each node of the graph is equivalent
to a state and has one and only one edge
leaving it
[
]
1
k
k
Wv
v
Γ
=
+
2/ If the transitions end in a cycl
e of states as in
nodes B, then we have a limit cycle solution with a certain period. The period is defined as the length of the cycl
e
. The
fig. shows the limit cycl
e
B of length 3.

21. 21
AM and Discrete
Hopfield
Network.
„
Introduction
„
Basic Concepts
„
Linear Associative Memory (Hetero-associative)
„
Hopfield’s Autoassociative Memory
„
Performance Analysis for Recurrent Autoassociation Memory
„
References and suggested reading
„
Introduction
„
Basic Concepts
„
Linear Associative Memory (Hetero-associative)
„
Hopfield’s Autoassociative Memory
„
Performance Analysis for Recurrent Autoassociation Memory
„
References and suggested reading

22. 22
Linear Associative Memory „
Belong to Static Networks
„
No nonlinear or delay operations
„
Dummy neurons with identity activation functions
(
)
i
i
i
net
net
f
v
=
=

Wx
v
=

23. 23
Linear Associative Memory
„
Given
p
associations
„
Apply Hebbian
Learning Rule
(
)
(
)
{
}
i
i
f
s
,
()
()
(
)
(
)
[
]
()
()
()
()
[]
t
i
m
i
i
i
t
i
n
i
i
i
f
f
f
s
s
s
,...,
,
,...,
,
2
1
2
1
==
fs
j
i
ij
ij
s
f
w
w
+
=
′
Inputs Outputs
Stimuli
(e.g. patterns)
Forced response (e.g
. images o
f
in
pu
t
Patters)
t
fs
W
W
+
=
′
W ‘
C
ross-correlation matrix
: m x
n
0
W
=
0
(
)
(
)
t
i
i
s
f
W
=
′
()
()
∑=
=
′
p
i
t
i
i
1
s
f
W
p
pairs learned (
implies superposition of weights)
t
FS
W
=
′
()
(
)
(
)
[
]
()
(
)
(
)
[]
pp
s
s
s
S
f
f
f
F




2
1
2
1
∆
∆
==
outer
pr
oduct (learning r
u
le)
Re
ca
ll that:
n= si
ze of stimuli
m= size of forced response
s
vects.

24. 24
Hebbian
Learning
Review
„
A purely feedforward, unsupervised learning
„
The learning signal is equal to the neuron’s output
„
The weight initialization at small random values around
w
i=0 prior to learning
„
If the cross-product of output and input (or correlation) is positive, it results in an increase of the weight, otherwise the weight decreases
(
)
x
w
ti
i
f
o
r
=
=
(
)
x
x
w
x
w
⋅
=
⋅
⋅
=
∆
ti
i
i
cf
o
c
(
)
j
ti
ij
x
f
c
w
⋅
⋅
=
∆
x
w
or

25. 25
Linear Associative Memory
„
Perform the associative recall using
–
I
f the desired response is •
N
ecessary conditions:
orthonormal
•
R
ather strict and may not always hold
()
(
)
(
)
()
(
)
(
)
()
()
()
()
(
)
(
)
()
j
t
p
p
j
t
j
j
j
t
j
p
i
t
i
i
j
s
s
f
s
s
f
s
s
f
s
s
f
s
W
v
...
...

1
1
1
+
+
+
=


=
′
=
∑
=
(
)
j
s
(
)
j
f
v
=
()
(
)
()
()
1
for

,
0
=
≠
=
j
t
j
j
t
i
j
i
s
s
s
s

26. 26
Linear Associative Memory
„
If a distorted input is presented
–
C
ross-talk noise remains additive at the memory
output to the originally stored association
–
L
inear associative memory perform rather poorly
when with distorted stimuli vectors
•
L
imited usage (not an
accurate
retrieval of the originally
stored association).
()
()
()
j
j
j
∆
s
s
+
=
′
()
()
()
()
(
)
(
)
()
∑≠
+
+
=
p
j
i
j
t
i
i
j
t
j
j
j
∆
s
f
∆
s
f
f
v
(
)
()
()
(
)
∑≠
+
=
p
j
i
j
t
i
i
j
∆
s
f
f
v
()
(
)
orthognal
thus
nt
indenpende
statically

and

If
j
j
∆
s
Cross-talk noise

27. 27
Linear Associative Memory
„
Example: three associations
(
)
(
)(
)
(
)
(
)
(
)
)
,
(
),
,
(
),
,
(
3
3
2
2
1
1
f
s
f
s
f
s
()
(
)
(
)
T
T
T
)
1,
0,
0
(
,
)
0,
1,
0
(
,
)
0
,
0
,
1
(
3
2
1
=
=
=
s
s
s
()
(
)
(
)
T
T
T
)
2
,
1,
3
(
,
)
3,
2
,
1
(
,
)
2
,
1,
2
(
3
2
1
=
=
=
f
f
f
()
(
)
(
)
(
)
(
)
(
)
[]
[]
[]
 
 
=
 
 
+
 
 
+
 
 
=
+
+
=
′
2

3

2
1

2

1
3

1

2
1
0
0
213
0
1
0
321
0
0
1
212

3
3
2
2
1
1
t
t
t
M
s
f
s
f
s
f
()
 
 
=
 
 
 
 
=
′
=
321
010
2

3

2
1

2

1
3

1

2
2
s
v
M

28. 28
Alternative View
Dan St
. Cl
a
ir
„
Goal:
Associate an input vector with a
specific output vector in a neural net
„
In this case, Hebb’s
Rule is the same as
taking the outer product of the two vectors:
s
= (s
1
, . . ., s
i, . . . s
n
) and
f
= (f
1
, . . ., f
i, . . . f
m
)
sf
=
[f
1
… f
m
] =
s
1
s
n
...
s
1
f
1
s
1
f
m
s
n
f
1
s
n
f
m
.
.
..
.
Weight matrix

29. 29
Weight Matrix
„
To store more than one association in a neural net using Hebb’s
R
ule
–
A
dd the individual weight matrices
„
This method works only if the input vectors for each association are orthogonal (uncorrelated)
–
T
hat is, if their dot product is 0
s
= (s
1
, . . ., s
i, . . . s
n
) and
f
= (f
1
, . . ., f
i, . . . f
m
)
s f =
[s
1
… s
n
]
f
1
f
m
...
= 0

30. 30
Heteroassociative
A
rchitecture
„
There are n input units and m output units with each input connected to each output unit.
0
w
i1 w
n1
Σ
w
11
0
w
i2 w
n2Σ
w
12
0
w
i3 w
n3
Σ
w
13
For m = 3
x
1
x
i
x
n
n inputs
Activation Functions:
For bipolar targets:
y
i
=
1 if y_in
i
> 0
0 if y_in
i
= 0
-1 if y_in
i
< 0
{
For binary targets:
y
i
=
1 if y_in
i
> 0
0 if y_in
i
<= 0
{

31. 31
Example
„
GOAL: build a neural network which will associate the following two sets of patterns using Hebb’s
R
ule:
s
1
= ( 1 -1 -1 -1) f
1
= ( 1 -1 -1)
s
2
= (-1 1 -1 -1) f
2
= ( 1 -1 1)
s
3
= (-1 -1 1 -1) f
3
= (-1 1 -1)
s
4
= (-1 -1 -1 1) f
4
= (-1 1 1)
The process will involve 4 input neurons and 3 output neurons The algorithm involves finding the four outer products and
adding them

32. 32
Algorithm
1
-1 -1 -1
[
1 –1 –1
] =
1 –1 –1
-1 1 1 -1 1 1 -1 1 1
Pattern pair 1:
-1
1
-1 -1
[
1 –1 1
] =
-1 1 –1
1 -1 1
-1 1 -1 -1 1 -1
Pattern pair 2:
-1 -1
1
-1
[
-1 1 –1
] =
1 –1 1 1 -1 1
-1 1 -1
1 -1 1
Pattern pair 3:
-1 -1 -1
1
[
-1 1 1
] =
1 -1 –1 1 -1 -1 1 -1 -1
-1 1 1
Pattern pair 4:

33. 33
Weight Matrix
„
Add all four individual weight matrices to produce the final weight matrix: 1 –1 –1
-1 1 1 -1 1 1 -1 1 1
-1 1 –1
1 -1 1
-1 1 -1 -1 1 -1
1 –1 1 1 -1 1
-1 1 -1
1 -1 1
1 -1 –1 1 -1 -1 1 -1 -1
-1 1 1
+
+
+
2 -2 –2 2 -2 2
-2 2 -2 -2 2 2
=
Each column defines the weights for an output neuron

34. 34
Example Architecture „
General Structure
x
1
x
2
x
4
x
3
0
2 -2
Σ
2
-2
0
-2 2
Σ
-2
2
0
2 -2
Σ
-2
2
y
i
=
1 if y_in
i
> 0
0 if y_in
i
= 0
-1 if y_in
i
< 0
{
2 -2 –2 2 -2 2
-2 2 -2 -2 2 2

35. 35
Example Run 1
„
Try the first input pattern:
1 -1 -1-1
0
2 -2
Σ
2
-2
0
-2 2
Σ
-2
2
0
2 -2
Σ
-2
2
y
i
=
1 if y_in
i
> 0
0 if y_in
i
= 0
-1 if y_in
i
< 0
{
y_in
1
= 2 –
2
+ 2 + 2 = 4 so y
1
= 1
y_in
2
= -2 + 2 -
2
-
2
= -4 so y
2
= -1
y_in
3
= -2 -
2
+ 2 -
2
= -
4
so y
3
= -1
S
1
= ( 1 -1 -1 -1) f
1
= ( 1 -1 -1)
Where
is this
Where
is this
inform
ation
inform
ation
stored? stored?

36. 36
Example Run II
„
Try the second input pattern:
s
2
= (-1 1 -1 -1) f
2
= ( 1 -1 1)
-1 1 -1-1
0
2 -2
Σ
2
-2
0
-2 2
Σ
-2
2
0
2 -2
Σ
-2
2
y
i
=
1 if y_in
i
> 0
0 if y_in
i
= 0
-1 if y_in
i
< 0
{
y_in
1
= -2 + 2 + 2 + 2 = 4 so y
1
= 1
y_in
2
= 2 -
2
-
2
-
2
= -4 so y
2
= -1
y_in
3
= 2 + 2 + 2 -
2
= 4 so y
3
= 1

37. 37
Example Run III
„
Try the Third input pattern:
s
3
= (-1 -1 1 -1) f
3
= (-1 1 -1)
-1 -1 -11
0
2 -2
Σ
2
-2
0
-2 2
Σ
-2
2
0
2 -2
Σ
-2
2
y
i
=
1 if y_in
i
> 0
0 if y_in
i
= 0
-1 if y_in
i
< 0
{
y_in
1
= -2 -
2
-
2
+ 2 = -
4
so y
1
= -1
y_in
2
= 2 + 2 + 2 -
2
= 4 so y
2
= 1
y_in
3
= 2 -
2
-
2
-
2
= -4 so y
3
= -1

38. 38
Example Run IV
„
Try the fourth input pattern:
s
4
= (-1 -1 -1 1) f
4
= (-1 1 1)
-1 -1 1-1
0
2 -2
Σ
2
-2
0
-2 2
Σ
-2
2
0
2 -2
Σ
-2
2
y
i
=
1 if y_in
i
> 0
0 if y_in
i
= 0
-1 if y_in
i
< 0
{
y_in
1
= -2 -
2
+ 2 -
2
= -
4
so y
1
= -1
y_in
2
= 2 + 2 -
2
+ 2 = 4 so y
2
= 1
y_in
3
= 2 -
2
+ 2 + 2 = 4 so y
3
= 1

39. 39
Example Run V „
Try a non-training pattern
-1 -1 -1-1
0
2 -2
Σ
2
-2
0
-2 2
Σ
-2
2
0
2 -2
Σ
-2
2
y
i
=
1 if y_in
i
> 0
0 if y_in
i
= 0
-1 if y_in
i
< 0
{
y_in
1
= -2 -
2
+ 2 + 2 = 0 so y
1
= 0
y_in
2
= 2 + 2 -
2
-
2
= 0 so y
2
= 0
y_in
3
= 2 -
2
+ 2 -
2
= 0 so y
3
= 0
What do What do the 0’s the 0’s mean? mean?

40. 40
Example Run VI
„
Try another non training pattern
-1 1 11
0
2 -2
Σ
2
-2
0
-2 2
Σ
-2
2
0
2 -2
Σ
-2
2
y
i
=
1 if y_in
i
> 0
0 if y_in
i
= 0
-1 if y_in
i
< 0
{
y_in
1
= -2 + 2 -
2
-
2
= -4 so y
1
= -1
y_in
2
= 2 -
2
+ 2 + 2 = 4 so y
2
= 1
y_in
3
= 2 + 2 -
2
+ 2 = 4 so y
3
= 1
What does What does this result this result mean? mean?

41. 41
AM and Discrete
Hopfield
Network.
„
Introduction
„
Basic Concepts
„
Linear Associative Memory (Hetero-associative)
„
Hopfield’s Autoassociative Memory
„
Performance Analysis for Recurrent Autoassociation Memory
„
References and suggested reading
„
Introduction
„
Basic Concepts
„
Linear Associative Memory (Hetero-associative)
„
Hopfield’s Autoassociative Memory
„
Performance Analysis for Recurrent Autoassociation Memory
„
References and suggested reading

42. 42
Hopfield’s Autoassociative
M
emory
(1982,
1984)
B
. Ch
e
n

& Zu
ra
da
„
Recurrent/Dynamic Associative Memory
„
Discrete-time and
Asynchronous
Update Mode
(
only one unit updates its activation at a time
)
Bipolar Binary
Responses
w
ij
= w
ji
(symmetric weights)
w
ii
=0
(no self connections)
Uses binary
input
vectors
Discrete
HP net

43. 43
Hopfield’s Autoassociative
M
emory
„
Storage Algorithm
To store a set of binary input vectors
s
(m)
–
I
n other words:
–
T
he diagonal elements set to be zero to
avoid self-feedbacks
()
()
()
()
()

≠
=
=
=
−
=
−


=
∑
∑
=
=
j
i
j
i
s
s
w
p
ijij
p
m
m
j
m
i
ij
ij
p
m
t
m
m

if

0

if

1

where ,
1
1
1
δδ
δ
I
s
s
W
Only for bipolar binary response (Bipolar patterns s= +1 or –1)
()
()
0
for
,
1
=
≠
=
∑
=
ii
p
m
m
j
m
i
ij
w
j
i
s
s
w

44. 44
Hopfield’s Autoassociative
M
emory
–
T
he matrix only represents the correlation
terms among the vector entries
–
I
nvariant with respect to the sequence of
storing patterns
–
A
dditional autoassociations
c
an be added
at any time by superimposition
–
a
utoassociations
can also be removed

45. 45
Hopfield’s Autoassociative
M
emory
„
Retrieval Algorithm
–
T
he output update rule can be expressed
as:
–
A
synchronous and random update of
neurons
m, p, q

sgn
1
1


=
∑
=
+
n
j
k
ij
ki
j
v
w
v
[
]
0
0
2
1
02
01
2
....
...
..
...

m
q
p
m
v
v
v
v
v
v
=
v
[
]
0
0
0
1
02
01
1
....
...
..
...

m
q
p
m
v
v
v
v
v
v
=
v
[
]
0
3
2
1
02
01
3
....
...
..
...

m
q
p
m
v
v
v
v
v
v
=
v
First Update Third Update Second Update

46. 46
Hopfield’s Autoassociative
M
emory
„
Example
: two autoassociations
()
(
)
[]
[
]
 
 
−
=
−
−
−
 
 
−−
+
 
 
−
=
 
 
−−
=
 
 
−
=
0

2
-

2

2
-

0

2
2

2
-

0

2

1

1

1
11

1

1

1
-

1
1

11

11

1
,
1

11

2
1
I
W
s
s


=
∑
=
+
n
j
k
ij
ki
j
v
w
v
1
1
sgn
Diagonal & symmetric
 
 
−
=
1

1

1
-

1
v
Ne
ur
on 1
 
 
−
=
1

1

1
-


2
v
 
 
−
=
1

1

1
-


4
v
 
 
−
=
1

1

1
-


3
v
 
 
−
=
1

1

1
-


5
v
 
 
−
=
1

1

1
-


6
v
Neur
on 2
Neur
on 3
Neur
on
1
Neur
on 2
Neur
on 3
convergence
 
 
−
=
11

1

:
input
Test
0
v

47. 47
Hopfield’s Autoassociative
M
emory
„
Example
: Autoassociation
f
or numbers
(Lippmann
1987)
Stored Patterns
A Distorted Input Pattern “6”

48. 48
Hopfield’s Autoassociative
M
emory
„
Example
: Autoassociation
f
or numbers
A Distorted Input Pattern “2”
A Distorted Input Pattern “9”

49. 49
Hopfield’s Autoassociative
M
emory
„
IF Unipolar
B
inary Patterns
(s = 0 or 1)
are
used
–
Scale
and
shift
the association patterns
–
I
n other words:
(
)
()
(
)
()
()
∑
=
−
−
−
=
p
m
m
j
m
i
ij
ij
s
s
w
1
1
2
1
2
1
δ
()
()
()
()
0
for

1
2
1
2
1
=
≠
−
−
=
∑
=
ii
p
m
m
j
m
i
ij
w
j
i
s
s
w

50. 50
Hopfield’s Autoassociative
M
emory
„
Performance Consideration
–
H
opfield autoassociative
m
emory also
referred to as “
Error Correcting Decoder
”
–
G
iven an input equal to the stored memory
with random error,
it produces as output
the original memory that is
close
to the
input
. E
x
ample:

51. 51
Hopfield’s Autoassociative
M
emory
„
Performance Cons
ideration
–
Let us assume that
s
(m
’
)
has been stored in the memory as one of
p patterns.
–
T
his pattern is now at the memory input. The activation value of
the
i-th
neuron for retrieval of pattern
s
(m
’
)
is :
()
()
()
(
)
()
()
(
)
()
n
n
n
s
s
s
s
s
s
ss
w
net
m
ip
m
n
j
m
j
m
j
m
i
n
j
p
m
m
j
m
j
m
i
n
j
m
j
ij
i
≤
≈≅≅=
∑∑∑∑∑
==
′
==
′
=
′
~

where
,

~

'
11111
If
s
(m
’
)
and
s
(m
)
are statistically
independent (also when orthogonal) the
product
vanishes (is zero)
Otherwise,
in the limit
case,
the
product
will reach
n for both vectors
being identical (
note
that it’s the dot
product with entries of vectors = +1 or –
1
)
If the effect of the diagonal
is neglected
w
ij
Th
e

maj
o
r ov
erl
a
p ca
se
.
i.e. s
(m’)
does not produce any update and is therefore stable

52. 52
Hopfield’s Autoassociative
M
emory
„
Performance Consideration
The equilibrium state for the
retrieval
pattern
s
(m
’
)
is considered
1.
If the stored prototypes are
statistically
independent or orthogonal
, and
n>p
(
) ()
()
(
)
m
p
m
t
m
m
m
p
W
′
=
′


−
==
∑
s
I
s
s
s
net
1

j
i
n
j
i
j
t
i
j
t
i
=
=
≠
=
for

for

0
)
(
)
(
)
(
)
(
s
s
s
s
(
)
)
'
(
)
(
)
(
)
2
(
)
2
(
)
(
)
1
(
...

m
p
p
p
s
I
s
s
s
s
s
s
net
t
t
t
1
−
+
+
+
=
i.e.
then
Since it is assumed that n>p, then the network will be in equilibrium state
s
(m
’
)
(
)
(
)
m
p
n
′
−
=
s
net

53. 53
Hopfield’s Autoassociative
M
emory
2.
If the stored prototypes are
not statistically
independent or orthogonal
()
(
)
()
()
(
)
()
()
()
()
()
()
()
()
()
m
t
m
m
m
p
m
m
t
m
m
m
p
m
m
t
m
m
m
W
p
n
′
′
′
′
′
≠
′
′
≠
′
+
−
=
=
+
−
=
∑
∑
s
I
s
s
s
s
s
η
s
s
s
s
net




No
is
e vector (
η
)
()
()
()
()
m
p
m
m
t
m
m
m
m
p
n
′
≠
∑
+
−
=
s
s
s
s
s
net
'
)
'
(
)
'
(
Equilibr
ium
s
t
a
t
e ter
m

(as on the previous slide) -
W
hen the
i-th
e
lement of the nois
e vector is larger
than
and has opposite sign, then

will not be the network’s

equilibrium -
T
he noise term obvious
ly increas
es for an increased number of
stored patterns, and also becomes
relatively significant when the
factor
(n-p)
decreases
(
)
(
)
m
s
p
n
′
−
i

(
)
m
s
′
i

54. 54
AM and Discrete
Hopfield
Network.
„
Introduction
„
Basic Concepts
„
Linear Associative Memory (Hetero-associative)
„
Hopfield’s Autoassociative Memory
„
Performance Analysis for Recurrent Autoassociation Memory
„
References and suggested reading
„
Introduction
„
Basic Concepts
„
Linear Associative Memory (Hetero-associative)
„
Hopfield’s Autoassociative Memory
„
Performance Analysis for Recurrent Autoassociation Memory
„
References and suggested reading

55. 55
Performance Analysis for Recurrent Autoassociation
M
emory
„
Example
Let us look at the convergenc
e properties of an
autoassociative memory that stores the two vectors
s
(1
)
and
s
(2)
()
(
)
[]
[
]
 
 
−
−
−
−
=
−
−
−
 
 
−−
+
−
−
 
 
−−
=
 
 
−−
=
 
 
−−
=
0

0

2

0

0

0

0

2

2

0

0

0

0

2

0

0

2

1

1

1

1
1 1

1

1
1

1

1

1
1

1

11
1 1

1

1
,
1

1

11
2
1
I
W
s
s
()
()
I
s
s
W
p
p
m
t
m
m
−


=
∑
=
1
•
W
hen the net. is allowed to
update, it evolves thr
ough cer
t
ain states which are
sho
w
n on the state transition
diagram on the next slide.
•
S
tates are ver
t
ices of the 4D cube.
•Only transitions between states
hav
e been marked on the graph; the self-
sustaining or
s
t
able state transitions have
been omitted for
clarity of the picture.

56. 56
Performance Analysis for Recurrent Autoassociation
M
emory
•
Since only
asynchronous
transitions are allowed for

autoassociative
r
ecurrent
memory
, every ver
t
ex is connected by
an edge only to the neighbouring ver
t
ex
differing by a single bit. •Thus there are only 4 tr
ansition paths connec
ted to every state.
T
he paths indicate
directions of
possible
transitions.
 
 
−−
=
1

11

1
0
v
 
 
−
=
′
1

1

1

1
0
v
Different update order will lead to different results.

57. 57
Performance Analysis for Recurrent Autoassociation
M
emory
•
Transitions are toward lower energy values
. The energy values for
each state
have been mark
ed in parenthes
es at each vertex.
•Let’s consider some sample
transition
s. Starting at v
(0)
= [-1 1 -1 1]
t
and with
nodes updating asynchronously in ascending order
(
highest entry of the vector
first
)
,
we have the state sequence
As it has been marked
on the state diagram.
•
T
he actual convergence is toward a
negative image of the stored patter
n
s
(2)
•The initial patter
n
had no par
ticular simila
rity to any of the
stored patter
ns and
apparently did not fall into any cl
oseness categor
y
of patterns.
•Let us look at a diffe
rent starting vector v
(0)
= [-1 1 1 1]
t
, the transition starting in
ascending order
leads to
s
(1)
in single step
 
 
−−
=
=
=
 
 
−−
=
 
 
−
=
1
11
1
...
1
11
1
1
1
11
4
3
2
1
v
v
v
v

58. 58
Performance Analysis for Recurrent Autoassociation
M
emory
etc.

11
11
3
4
2
3
2
0
1
v
v
v
v
v
v
v
=
=
 
 
−−
=
=
•
Y
ou can also verify that by car
r
y
ing out the transitions initialized at
v
(0)
, but carr
ied
out in descen
d
in
g node order, pattern
s
(2)
can be recove
red.

59. 59
Advantages and Limits for Associative Recurrent Memories
„
Limits
–
L
imited capability
–
C
onverge to spurious memories (states).
„
Advantage
–
T
he recurrences through the thresholding
layer of processing neurons (threshold functions) tend to eliminate noise superimposed on the initializing input vector

60. 60
AM and Discrete
Hopfield
Network.
„
Introduction
„
Basic Concepts
„
Linear Associative Memory (Hetero-associative)
„
Hopfield’s Autoassociative Memory
„
Performance Analysis for Recurrent Autoassociation Memory
„
References and suggested reading
„
Introduction
„
Basic Concepts
„
Linear Associative Memory (Hetero-associative)
„
Hopfield’s Autoassociative Memory
„
Performance Analysis for Recurrent Autoassociation Memory
„
References and suggested reading

61. 61
Suggested Reading. ƒ
L. Fausett
,
“Fundamentals of Neural Networks”, Prentice-Hall, 1994, Chapter 3. ƒ
J. Zurada
,
“Artificial Neural systems”, West Publishing, 1992, Chapter 6.

62. 62
References:
These lecture notes were based on the references of the
previous slide, and the following references
1.
B
erlin Chen Lecture notes:
Normal University, Taipei,
Taiwan, ROC.
h
t
tp://140.122.185.120
2.
Dan St. Clair, University of Missori-Rolla, http://web.umr.edu/~stclair/clas
s/classfiles/cs404_fs02/Misc/CS
404_fall2001/Lectures/
Lecture 21.