Hopfield Network

Hopfield network is a fully connected single layer auto associative recurrent neural network. It was proposed by John Hopfield in 1982. It uses Hebbian Learning. It is used for different pattern recognition problems.

Hopfield network uses content addressable memory — retrive data by similarity rather than exact address.

Associative memory

Associative memory is a content addressable structure that maps a set of input patterns to a set of output patterns. There are two types:

a) Auto-associative memory — retrieves a previously stored pattern which most closely resembles the current pattern. It is used for pattern recognition, pattern completion, denoising etc. Use cases include facial recognition, handwriting recognition etc. Ex: Hopfield network

b) Hetero-associative memory — maps one set of patterns to another set of patterns which allows it to recognize associations or relationships (semantic) between different types of data. Use cases include language translation, object recognition and retrieval etc.

Store and Recall

The purpose of a Hopfield network is to store one or more patterns and to recall the full patterns based on partial or noisy inputs.

Storage Phase — “Learning the Patterns”

The network stores patterns as stable states by memorizing certain input patterns in its weights. Training is done to adjust the strength of connections between the neurons so that they encode (remember) the patterns. If two neurons are often “on” at the same time in a pattern, the connection between them is made stronger. If they are opposite, the connection between them is made weaker or negative.

Retrieval Phase — “Remembering the Pattern”

The network converges to the closest stored full pattern when given an incomplete or courrupted version of the stored pattern by communicating using the stored connections.

Example: Scan input text to display corresponding ASCII

The Hopfield network is mapped out such that each pixel is one node in the network. It is trained to recognize the 52 alphabets (upper and lower case). Let us say, we input a noisy pattern of the letter ‘T’. After a few iterations, it reproduces the correct pattern ‘T’.

Architecture

Hopfield network has only one layer, with each neuron connected to every other neuron. All neurons act as input and output. The network has no hidden nodes or layers. Nodes have binary outputs. The output of the neuron is feedback, via a unit delay element, to each of the other neurons. There is no self-feedback. The number of feedback loops is equal to the number of neurons. Weights between the nodes should be symmetric, ie. wij = wji.

Fig 1 : Hopfield Network (Source- http://vlabs.iitkgp.ac.in/rtes/exp13/index.html)

Hopfield Network Training Algorithm

During the training process, the weights get updated. We can have both binary as well as bipolar input vectors. Convert binary input (1 → +1 and 0 → -1) into bipolar before starting training.

Given N neurons and P patterns, each pattern can be represented as Fig 2.

Fig 2 : Representation of patterns

Step 1: Initialize a weight matrix — Fill all the values in the matrix with zero.

Step 2: Apply Hebbian learning — For each pattern p = 1,2,…P, we apply Fig 3 to compute the weight matrix. The self connections are zeroed out.

Fig 3 : Hebbian Learning Rule

Hopfield Network Retrieval Algorithm

Step 1: Initialize state — s(0) = input pattern

Step 2: Update neurons as given in Fig 4 and Fig 5.

Fig 4: Asynchronous update — preferred for convergence

Fig 5 : Synchronous update — update all neurons together

Step 3: Convergence check — Stop when s(t+1) = s(t). This implies that the network has reached a stable state.

Solving a Hopfield network example using the algorithm

Let us consider 4 neurons that are supposed to remember 2 patterns.

x(1) = [1 -1 1 -1] and x(2) = [1 1 -1 -1]

Training: Apply hebbian learning such that weight matrix W is calculated as given in Fig 6.

Fig 6a: Weight matrix computation using Hebbian Learning

Fig 6b : Pattern 1

Fig 6c : Pattern 2

Fig 6d : Final weight matrix after zeroeing out the diagonal representing self loop and adding each pattern matrix

Retrieval: Suppose we give a noisy input pattern s(0) = [1 1 1 -1]. Update the neurons as given in Fig 7.

The first neuron gets updated by mutliplying s(0) = [1 1 1 -1] and first row of the weight matrix [0 0 0 -2]. The second neuron gets updated by multiplying s(0) = [1 1 1 -1] and the second row of weight matrix [ 0 0 -2 0], and so on.

We get h1 = 2. Output +1 if value is positive, -1 is value is negative, 0 if value is 0. Since h1 = 2 and it is a postive value, its outputted as +1.

Fig 7 : Updating neurons asynchronously using the weight matrix

The final recalled pattern obtained from this example is s = [1 -1 1 -1] which is exactly the stored pattern x(1). Incase it doesn’t match any input pattern, continue the retrieval iteration with the new s value [1 -1 1 -1] and weight matrix. Finally, we observe that even with the noise, the network recovered the correct pattern.

A detailed proof shows that a Hopfield network of N nodes can achieve 100% correct retrieval on P patterns if P < N/(4*ln(N)). This implies that, similar to the human memory, recall can be slowed when there is too much memory crammed. As more patterns gets added to the network, the average correlations will be less liekly to match the correlations in any particular pattern. This increases the likelihood of retrieval error. The key to perfect recall is selective ignorance.

I wrote this article while summarizing my learnings for an examination. Hope this helps!