|
Neural
Computing
1. Introduction
A hopfield network is a recurrent, energy minimisation
network. When given an initial state the network may be iterated and
will approach a stable state. The stable states represent patterns
stored within the network’s connection matrix. The hopfield
network exhibits content addressable properties. A binary hopfield
network is used for the experiments in this report and its connection
matrix is shown in figure 1.
Figure
1. Hopfield network connection matrix as defined by
the connections function
The connections matrix is reliant on the inhibition constant ‘w’. This determines the background intensity of the network. The experiments use the inhibition constants of 0.5 and 1.
We can consider the network states to be arranged in a 3 by 3 grid as shown in figure 2.
Figure
2. 3 by 3 state grid.
Figure 3 shows the grid representation of the connection matrix. The network is fully connected but for simplicity only the connections with value 1 are shown
Figure 3. Connections of value 1.
This configuration indicates that the network will identify horizontal and vertical lines passing through the centre of the grid.
The hopfield network features two update rules. These iterate the network state through one step and cause the network to move closer to the minimum energy state.
The asynchronous update rule is the most common update rule. This selects one of the network’s 9 units at random and updates it according to the following rule.
if
else
Figure 4.
Unit update rule.
The scan update rule applies the unit update rule as shown in figure 4, but applies it to all of the 9 network units in parallel.
2.1 Determining the fixed points
To determine the fixed points, every possible input state is shown to the network. The scan update rule is used to determine if the state changes. If the network remains stable i.e. the output is the same as the input then this is stable point.
A binary counter is implemented to provide an input state to the network. The function ‘inc’ is used to increment this.
The following Mathematica code fragment returns the stable points for the network when given the inhibition constant.
findFixedPoints[inhib_]:=Module[ { W=connections[inhib], iv:={0,0,0,0,0,0,0,0,0}, ov, points:={} }, For[n:=0,n<2^Length[iv],n++, ov:=scan[W,iv]; If
[ov==iv, points=Append[points,iv]]; iv=inc[iv]; ]; points]
Inhibition constant ‘w’ = 0.5
Figure
5. Stable
points when w = 0.5
Inhibition constant ‘w’ = 1
Figure
6. Stable points when w = 1
The fixed points of the network when w = 1 are a subset of the fixed points when w = 0.5. The ‘+’ shaped state is not a stable point when w = 1.
Comparing the fixed points with the connection matrix shows that these patterns occur within the memory of the network.
My observations at this stage. It may be that
increasing the inhibition constant reduces the number of stable points.
2.2
Computing
the Network Energy
By taking each fixed point, calculating the energy at that point and then calculating the energy level of all the adjacent points we can determine whether the point is a local minimum. In this report a local minimum is defined as having an energy value less then that of all the surrounding points.
The energy of a point may be calculated using the Liapunov function as shown below.
Figure 7. Liapunov energy function.
Selecting neighbouring points is done by the function ‘getNeighbours’. This works by inverting each individual bit of the input state to create 9 states which are adjacent to the input state.
The following Mathematica function displays the energy level for each of stable point and the neighbouring points for the network when give the inhibition constant. The function also determines whether the point is a local minimum.
(*
2.2 Find and Print Local Mins *)
findLocalMins[inhib_]
:= Module[{w = connections[inhib]},
fixedPoints = findFixedPoints[inhib]; nabs = Map[getNeighbours[#]
&, fixedPoints]; pointEnergy =
LiapMap[w, fixedPoints]; naberEnergy =
Map[LiapMap[w, #] &, nabs]; pointEnergy2 =
LiapMap2[w, fixedPoints]; naberEnergy2 =
Map[LiapMap2[w, #] &, nabs]; Print["Inibition
= ", inhib]; For[n := 1, n
<= Length[fixedPoints], n++, Print[ TableForm[{{pointEnergy2[[n]],
naberEnergy2[[n]], {"Local Min:",
allLessThan[pointEnergy[[n]], naberEnergy[[n]]]}}}]] ]]; Print[""];
Results
Inhibition constant w = 0.5
Inhibition constant w = 1
It is known that the maximum theoretical capacity of the hopfield network is 0.138n where n is the number of units in the network (Course Notes, p72), since the network has 9 units it is only possible to recall one pattern correctly. This would explain the stable states that are not local minimum. Also Haykin states that it is possible to recall most of the fundamental memories when using the following equation.
Figure 8. Storage capacity of a hopfield network where most of the fundamental memories are recalled perfectly. (Haykin, S. Neural Networks. 1994, p307)
In the case of our network this allows for 2 possible memories and may help explain the 2 local minimum when w = 1.
The states which are not local minimum may be identified as spurious states, these states are matched with only part of the stored pattern.
It appears that when the inhibition constant w is set to 1 that the ‘+’ shaped local minimum that is present when w = 0.5 splits in to two local minima ‘-‘ and ‘|’. The original local minimum’+’ disappears.
2.3 Running The Network
Using the ‘Hopfield’ function the network is initialised with each of the following random initial states.
Init = { {1, 1, 1, 0, 0, 1, 1, 0, 1}, {1, 0, 0, 1, 0, 1,
0, 0, 1}, {1, 1, 0, 0, 1, 0, 0, 0, 1}, {0, 0, 0, 1, 0, 1,
0, 1, 1}, {1, 0, 0, 1, 0, 0, 0, 0, 0}, {1, 1, 0, 1, 1, 0,
1, 1, 1}, {0, 0, 1, 0, 0, 0, 1, 1, 1}, {1, 1, 0, 1, 0, 0,
0, 1, 0}, {0, 1, 0, 1, 0, 1, 0, 0, 0}, {0, 1, 0, 1, 1, 0,
1, 0, 0}, {0, 0, 1, 0, 1, 0, 0, 0, 1}, {0, 1, 0, 1, 1, 1,
0, 1, 1}, {1, 0, 1, 1, 1, 1, 1, 1, 0}, {1, 1, 0, 0, 1, 0,
1, 0, 0}, {1, 0, 0, 1, 0, 1, 0, 0, 0}, {1, 0, 0, 1, 1, 0,
0, 0, 1}, {0, 0, 1, 0, 0, 0, 1, 0, 1}, {1, 0, 0, 1, 1, 0,
1, 0, 1}, {0, 0, 0, 0, 1, 0, 1, 1, 1}, {1, 0, 0, 1, 1, 0,
0, 1, 0}};
Figure
9. Initial states
The network is then run for 50 iterations using both the scan and asynchronous update rules, with inhibition constants 0.5 and 1.
Figure
10. Final states after running the scan update rule
for 50 iterations.
The scan rule always achieves the same final state for a given input state.
Figure 11. Final states after running async update rule for 50 iterations 5 times.
Network energy
The graphs in figure 12 show the network’s energy level of each of the 20 initial states as the network is incremented through 50 iterations.
Figure
12. The energy for the 20 initial states over 50 iterations.
The async method requires more iterations then the scan method to achieve a stable state. This is to be expected as the async method only updates one unit per cycle while the scan method updates all 9 units.
Conclusions
The async rule does not always result in the same final state for a given input. It could be said that using this rule the network is non-deterministic.
The results also indicate that the inhibition constant ‘w’ does as its name suggests and inhibits the network’s ability to achieve lower energy levels.
For multiple runs the scan method returns to the same energy levels for a given input while the async method may not return to the same energy level. The async method does not necessarily fall to the lowest possible energy level for a given input.
The Mathematica Code is available at
/dcs/98/gt/public_html/nn/hopXX.nb
To run the program
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
