Transcript ppt - Department of Computer Science and Engineering

CS623: Introduction to
Computing with Neural Nets
(lecture-11)
Pushpak Bhattacharyya
Computer Science and Engineering
Department
IIT Bombay
Hopfield net (recap of main points)
• Inspired by associative memory which means
memory retrieval is not by address, but by part
of the data.
• Consists of
N neurons fully connected with
symmetric weight strength wij = wji
• No self connection. So the weight matrix is 0diagonal and symmetric.
• Each computing element or neuron is a linear
threshold element with threshold = 0.
Connection matrix of the network,
0-diagonal and symmetric
j
n1
n2
n3
. . .
n1
n2
i
n3
.
.
.
nk
wij
0 – diagonal
nk
Example
w12 = w21 = 5
w13 = w31 = 3
w23 = w32 = 2
At time t=0
s1(t) = 1
s2(t) = -1
s3(t) = 1
Unstable state: Neuron 1 will flip.
A stable pattern is called an
attractor for the net.
Concept of Energy
• Energy at state s is given by the equation:
E ( s)  w12 x1 x2  w13 x1 x3    w1n x1 xn
 w23 x2 x3    w2 n x2 xn 

 w( n 1) n x( n 1) xn 
Relation between weight vector W
and state vector X
W
Weight vector

XT
Transpose of state vector
For example, in figure 1,
At time t = 0, state of the neural network is:
s(0) = <1, -1, 1> and corresponding vectors are as shown.
1
W
3
2
3
1
1
5
Fig. 1
0 5 3
5 0 2


3 2 0
2
-1
W

X 
T
X 
T
1 
 1
 
1 
0 5 3 1 
5 0 2  1

  
3 2 0 1 
W.XT gives the inputs to the
neurons at the next time instant
W

X 
T
0 5 3 1 
5 0 2  1

  
3 2 0 1 
  2
 7 
 
1 
 1
sgn( W . X T )  1 
 
1 
This shows that the
n/w will change state
Theorem
• In the asynchronous mode of operation,
the energy of the Hopfield net always
decreases.
• Proof:
E(t1)  w12 x1(t1) x2(t1)  w13x1(t1) x3(t1)   w1nx1(t1) xn(t1)
 w23 x 2(t1) x3(t1)    w2 nx 2(t1) xn (t1) 

 w( n  1) nx( n  1)(t1) xn(t1)
Proof
• Let neuron 1 change state by summing and comparing
• We get following equation for energy
E(t 2)  w12 x1(t 2) x2(t 2)  w13x1(t 2) x3(t 2)   w1nx1(t 2) xn(t 2)
 w23 x 2(t 2) x3(t 2)    w2 nx 2(t 2) xn(t 2) 

 w( n  1) nx( n  1)(t 2) xn(t 2)
Proof: note that only neuron 1 changes state
E  E (t 2)  E (t1)
 w12 x1 (t2 ) x2 (t2 )  w13 x1 (t2 ) x3 (t2 )    w1n x1 (t2 ) xn (t2 )
 w12 x1 (t1 ) x2 (t1 )  w13 x1 (t1 ) x3 (t1 )    w1n x1 (t1 ) xn (t1 )
n
  w1 jx1(t 2)  xj (t 2)  x1(t1)  xj (t1)
j 2
Since only neuron 1 changes state, xj(t1)=xj(t2), j=2, 3, 4, …n, and hence
n
  w1 j  xj (t1)x1(t1 )  x1(t2 )
j 2
Proof (continued)
n
  w1 j  xj(t1)x1(t1 )  x1(t2 )
j 2
(S)
(D)
• Observations:
– When the state changes from -1 to 1, (S) has to be +ve and
(D) is –ve; so ΔE becomes negative.
– When the state changes from 1 to -1, (S) has to be -ve and
(D) is +ve; so ΔE becomes negative.
• Therefore, Energy for any state change always
decreases.
The Hopfield net has to “converge”
in the asynchronous mode of
operation
• As the energy E goes on decreasing, it
has to hit the bottom, since the weight and
the state vector have finite values.
• That is, the Hopfield Net has to converge
to an energy minimum.
• Hence the Hopfield Net reaches stability.
Training of Hopfield Net
• Early Training Rule proposed by Hopfield
• Rule inspired by the concept of electron
spin
• Hebb’s rule of learning
– If two neurons i and j have activation xi and xj
respectively, then the weight wij between the
two neurons is directly proportional to the
product xi ·xj i.e.
wij  xi  x j
Hopfield Rule
• Training by Hopfield Rule
– Train the Hopfield net for a specific memory
behavior
– Store memory elements
– How to store patterns?
Hopfield Rule
• To store a pattern
<xn, xn-1, …., x3, x2, x1>
make
1
wij 
 xi  x j
(n  1)
• Storing pattern is equivalent to ‘Making
that pattern the stable state’
Training of Hopfield Net
• Establish that
<xn, xn-1, …., x3, x2, x1>
is a stable state of the net
• To show the stability of
<xn, xn-1, …., x3, x2, x1>
impress at t=0
<xtn, xtn-1, …., xt3, xt2, xt1>
Training of Hopfield Net
• Consider neuron i at t=1
ai (t  1)  sgn( neti (t  0))
neti (t  0) 
n
w
j i , j 1
ij
 ( x j (t  0))
Establishing stability
n
w
j  i , j 1



ij
x j (t  0)
1
( n  1)
 (x
1
( n  1)
2
(
x
(
t

0
))

[
x
(
t

0
)
]
 i
j
i
(t  0))  ( x j (t  0))  (x j (t  0))
j
j
1
( xi (t  0)) 
( n  1)
1
j 1, j  i
1
 ( xi (t  0))  ( n  1)
( n  1)
 xi (t  0)

Thus ,
xi (t  1)  sgn( xi (t  0))
Example
• We want <1, -1, 1> as
stored memory
• Calculate all the wij
values
• wAB = 1/(3-1) * 1 * -1
= -1/2
• Similarly wBC = -1/2
and wCA = ½
• Is <1, -1, 1> stable?
1
C
A
B
1
-1
Initially
1
C
0.5
-0.5
B
A
-1
1 -0.5
After calculating weight values
Observations
• How much deviation can the net tolerate?
• What if more than one pattern is to be
stored?
Storing k patterns
• Let the patterns be:
P1 : <xn, xn-1, …., x3, x2, x1>1
P2 : <xn, xn-1, …., x3, x2, x1>2
.
.
.
Pk : <xn, xn-1, …., x3, x2, x1>k
• Generalized Hopfield Rule is:
k
1
wij 
xi  x j | p

(n  1) p 1
Pth pattern
Storing k patterns
• Study the stability of
<xn, xn-1, …., x3, x2, x1>
• Impress the vector at t=0 and observer
network dynamics
• Looking at neuron i at t=1, we have
Examining stability of the qth
pattern
xi (1) |q
 sgn( neti (1) |q ); neti (1) |q 
n
w
j 1, j i
ij
 x j (0) |q
wij  x j (0) |q

k
1
[ xi (0) | p  x j (0) | p ]  x j (0) |q
( n  1) p 1

k
1
1
[  xi (0) | p  x j (0) | p ]  x j (0) |q 
xi (0) |q  x j (0) |q  x j (0) |q
( n  1) p 1, p  q
( n  1)

k
1
1
[  xi (0) |q  x j (0) | p ] 
( xi (0) |q )  [ x j (0) |q ]2
( n  1) p 1, p  q
( n  1)
Q
Q
1
 xi (0) |q 1
( n  1)
xi (0) |q
( n  1)
Examining stability of the qth
pattern
Thus,
xi (1)  sgn[  nj 1, j i Q   nj 1, j i
xi (0)
]
(n  1)
 sgn[  j 1, j i Q  xi (0)]
n
 sgn[  j 1, j i
n
Small when k << n
k
 ( x (0) |
p 1, p  q
i
q
 x j (0) |p )  xi (0)]
Storing k patterns
• Condition for patterns to be stable on a
Hopfield net with n neurons is:
k << n
• The storage capacity of Hopfield net is
very small
• Hence it is not a practical memory element