Figure 1. Diagram of a Hopfield type network
CIS 311: Neural Networks
Hopfield Networks
1. Recurrent Networks with Multiple Feedbacks
Depending on their connectivity pattern (architecture) the artificial neural networks can be grouped into the following two groups:
- feed-forward neural networks- these are networks whose architecture has no loops, in general the feed-forward networks are static because they produce only one set of output values rather than a sequence of values from a given input data set;
- recurrent (feedback) networks- these are networks in which loops occur because of feedback connections, applying feedbacks means that a time parameter implicitly enters the model, and in this sense these neural networks are dynamic.
There have been developed two kinds of feedback connections for neural networks: 1) local feedbacks- these are links that pass the output of a neuron to itself; and 2) global feedbacks- these are links that pass the output of a neuron to other neurons in the same or lower layers in the multilayer network architecture. Recurrent neural networks with global feedback of Hopfield type are studied here.
A problem that arises in such dynamic neural networks is to achieve stability in the training process, because if the feedbacks are not treated properly the performance can become unstable.
2. Hopfield Type Networks
The Hopfield network is an implementation of a learning matrix with recurrent links. The learning matrix is a weight matrix which actually stores associations between inputs and targets. This network generalizes in the sense that it identifies general dependencies in the given incomplete and noisy training data, in this sense it resembles a learning matrix. This kind of a network is a linear model as it can model only linearly separable data.
The Hopfield Type Network is a multiple-loop feedback neural computation system. The neurons in this network are connected to all other neurons except to themselves, that is there are no self-feedbacks in the network. A connection between two neurons Ni and Nj is two way which is denoted by wij. The connection wij from the output of neuron i to the input of neuron j has the same strength as the connection wji from the output of neuron j to the input of neuron i, in other words the weight matrix is symmetric. Each neuron computes the summation:
si = S j=1n wji xj
where: n is the number of neurons in the network, wji are the weights, and xj are inputs, 1<=j<=n.
The Hopfield network can be made to operate in either continuous or discrete mode. Here it is considered that the network operates in discrete mode using neurons with discrete activation functions. When a neuron fires, its discrete activation function is evaluated and the following output is produced: x'i = 1 if si = S j=1n wji xj >= 0 or x'i = 0 if si < 0.
Figure 1. Diagram of a Hopfield type network
Hopfield networks can be implemented to operate in two modes:
- Synchronous mode of training Hopfield networks means that all neurons fire at the same time.
- Asynchronous mode of training Hopfield networks means that the neurons fire at random.
Example: Consider a Hopfield type recurrent network with three neurons. The network weights at the current time instant are given by the following symmetric matrix:
W = w11 w12 ... w13 = 0 -0.4 0.2
w21 w22 ... w23 -0.4 0 0.5
w31 w32 ... w33 0.2 0.5 0
When the first neuron fires its activation function computes the output:
s1 = 0 * 1 + ( -0.4 ) * 1 + 0.2 * 0 = -0.4
Therefore the new network state becomes: [ 0, 1, 0 ].
When the second neuron fires, again starting from [ 1, 1, 0 ], its activation function computes the output:
s2 = ( -0.4 ) * 1 + 0 * 1 + 0.5 * 0 = -0.4
Therefore the new network state becomes: [ 1, 0, 0 ].
When the third neuron fires, again starting from [ 1, 1, 0 ], its activation function computes the output:
s3 = 0.2 * 1 + 0.5 * 1 + 0 * 0 = 0.7
Therefore the new network state becomes: [ 1, 1, 1 ].
Assuming that the network operates in asynchronous mode starting from [ 1, 1, 0 ], it may reach any of the new three states: [ 0, 1, 0 ], [ 1, 0, 0 ], or [ 1, 1, 1 ]. Assuming that the network operates in synchronous mode starting from [ 1, 1, 0 ] the first neuron will fire leading to [ 0, 1, 0 ], next neuron two will fire leading to [ 0, 0, 0 ], and finally when neuron three fires the result will be [ 0, 0, 1 ]
3. State Table
The recurrent networks of the Hopfield type are complex dynamical systems whose behaviour is determined by the connectivity pattern between the neurons. The inputs to the neurons are not simply externally provided inputs but outputs from other neurons that change with the time. The temporal behaviour of the network implies characteristics that have to be taken into consideration in order to examine the network performance.
The Hopfield networks are dynamical systems whose state changes with the time. The state of the neural network is the set of the outputs of all neurons at a particular moment, time instant. When a neuron fires, its output changes, and so the network state also changes. Therefore the sequence of neuron firings leads to a corresponding sequence of modified neuron outputs, and modified system states. Acquiring knowledge of the state space allows us to study the motion of the neural network in time. The trajectories that the network leaves in the time may be taken to make a state portrait of the system.
A Hopfield net with n neurons has 2n possible states, assuming that each neuron output produces two values 0 and 1. Performance analysis of the network behaviour can be carried out by developing a state table that lists all possible subsequent states. The state table for the above example Hopfield network with 3 neurons is given below.
init state if state if state if state N1 fires N2 fires N3 fires 000 100 010 001 001 101 011 001 010 010 010 011 011 011 011 011 100 100 100 101 101 101 111 101 110 010 100 111 111 011 111 111
4. The Model as a Content-Addressable Memory
Hopfield networks are used as content-addressable memory. The content-addressable memory is such a device that returns a pattern when given a noisy or incomplete version of it. In this sense a content-addressable memory is error-correcting as it can override provided inconsistent information.
The discrete Hopfield network as a memory device operates in two phases: storage phase and retrieval phase. During the storage phase the network learns the weights after presenting the training examples. The training examples for this case of automated learning are binary vectors, called also fundamental memories. The weights matrix is learned using the Widrow-Hoff rule. According to this rule when an input pattern is passed to the network and the estimated network output does not match the given target, the corresponding weights are modified by a small amount. The difference from the single-layer perceptron is that no error is computed, rather the target is taken directly for weight updating.
The Widrow-Hoff learning rule suggests to compute the summation block of the i-th neuron: si = S j=1n wji xj(t), and next to modify the weights depending on the result. There are two cases to consider:
if si >= 0 and xi = 0 the output should be made negative, say –0.1 then each weight has to be decreased: wji = wji - ( 0.1 + si ) / n
if si < 0 and xi = 1 the output should be made positive, say 0.1 then each weight has to be increased: wji = wji + ( 0.1 - si ) / n
During the retrieval phase a testing vector called probe is presented to the network, which initiates computing the neuron outputs and evolving the state. After sending the training input to the recurrent network its output changes for a number of steps until reaching a stable state. The selection of the next neuron to fire is asynchronous, while the modifications of the state are deterministic. After the state evolves to a stable configuration, that is the state is not more updated, the network produces a solution. This state solution can be envisoned as a fixed point of the dynamical network system. The solution is obtained after adaptive training.
Learning and Training Algorithm for Hopfield networks
Learning: Present the given training (binary) vectors to the Hopfield net, and calculate the weights using the Widrow-Hoff rule
if si >= 0 and xi = 0 : wji = wji - ( 0.1 + si ) / n
if si < 0 and xi = 1 : wji = wji + ( 0.1 - si ) / n
Initialization: Let the testing vector become initial state x(0)
Repeat
-update asynchronously the components of the state x(t)
x'i(t) = 1 if si(t) = S j=1n wji xj(t) >= 0 or x'i(t) = 0 if si(t) < 0
-continue this updating until the state remains unchanged
until convergence
Generate output: return the stable state (fixed point) as a result.
5. Energy Minimization
The energy is a behavioural characteristic that can be used to examine the network performance. It is well known that independently from the initial conditions the network will stabilize, it can not oscillate even at the same energy level. The energy of Hopfield nets is defined in the following way:
e = -0.5 S i=1nS j=1n wji xi xj
The energy in the Hopfield model either decreases or remains the same, the energy never increases. If it decreases it can never return to a previous state. The only case when the energy remains the same is when a neuron output changes from 0 to 1. The convergence of the network can be considered as a process of reducing the network energy until reaching an energy well, that is the stable network states are energy wells. Which of the possible energy wells will be reached after training depends on the initial system state and also on the order of firing of the neurons.
Suggested Readings:
S. Haykin (1999). Neural Networks. A Comprehensive Foundation, Second Edition, Prentice-Hall, Inc., New Jersey, 1999, pp.680-696.