Main Menu

An Associative Memory

What we are going to look at here is an associative memory. This is similar to a Hopfield net, which is why it has been placed in the section directly afterwards. The Hopfield net learns to associate a pattern with itself (it is autoassociative), so that if you give it a corrupted version of a pattern, then it will recreate the original pattern.

A general associative memory, on the other hand, learns to associate pairs of patterns. It might associate a pattern shaped like a star with a smiley face and a pattern shaped like a moon with a sad face, for example. It is given pairs of patterns, "input" and "output", and learns them.

Below you will see a JavaScript version of an associative memory that I saw in an article called "A window into the brain" by Jack Weber in the March 1988 issue of Personal Computer World (I'd recommend it if you can get hold of a copy!) The article showed 3 standard pairs of patterns, and below the input and output layers there are three buttons, each displaying one of the standard pairs of patterns.

You can get the associative memory to learn any particular pattern by clicking on the squares in the input or output layer (to toggle them from black to white or vice-versa) and then clicking on "Learn current pattern" when they are as you want them. This applies to the standard patterns as well - just display them and click on the "Learn" button.

After the JavaScript simulation there is a section explaining how the program works.

The Demonstration

Input
Output
       

The following buttons will display the three standard patterns, but you must still click on the "Learn" button above if you want them to be learned!

   

How the program works

To see the JavaScript program in all its glory, examine the source code of this page and search for the string <!-- Program starts here -->.

The two layers are stored in two 2 one-dimensional arrays, called input_layer[100] and output_layer[100]. Although each layer appears in the form of a square, I found it easier to number the nodes from 0 to 99 across the rows (i.e. the first row contains nodes 0 to 9, the second row nodes 10 to 19 etc.)

There is a two dimensional array which gives the weights between the two layers. The weights are bi-directional, which means that weight weight[x][y] is not only the weight from node x of the input layer to element y of the output layer, but also the other way round.

The associative memory passes the test patterns back and forth between the input and output layers until they stabilise. (This often seems to happen on the very first iteration!) Please note that, just as in the Hopfield net, the patterns aren't guaranteed to stabilise on one of the patterns that have been taught to the net!

Learning is done in a similar way to the Hopfield net, but I have given a slight variation on it. Instead of getting you to enter all the patterns "up front" and then learning them, it simply adds the pattern to the current weights. The crucial line in the program is

weight[i][j] += (input_layer[i] * 2 - 1) *
(output_layer[j] * 2 - 1);

Note that the elements in the input and output layers are stored as 1s and 0s rather than 1s and -1s. Why did I do this? Well, for a start, the demonstration program had them stored this way, and also these values are used to display pictures on the screen. The two image files are called 1.gif and 0.gif, and it would be rather difficult to create one called -1.gif!

However, the algorithm does require the values to be -1 and 1, as in the standard Hopfield net, so whenever a calculation is performed on an input or output value, it is placed into this expression: (2 * simple_value - 1). This turns 1 and 0 into 1 and -1.

The algorithm is similar to that of the Hopfield net, except that it is done in two parts. Firstly, the input values are passed through the weights to get the new output layer values: 

for (j = 0; j < SIZE; j++)
 { var sum = 0;
   for (i = 0; i < SIZE; i++)
    sum += input_layer[i] * weight[i][j];
   if (sum > 0)
    output_layer[j] = 1;
   if (sum < 0)
    output_layer[j] = 0;
   document.images["b" + j].src = output_layer[j] + ".gif";
 }

Then the process is repeated on the (new) output values, passing them through the same weights, to get new values for the input layer. The code is the same with input and output swapped.

Clicking on the button only does this once (i.e. one input to output step followed by one output to input step). Although this is normally enough to make most patterns converge, you may need to click on the button several times to ensure that convergence does occur.

Although the networks do converge, it isn't always on one of the patterns on which you have trained it. The associative net, like the Hopfield net, is prone to converging on some pattern of input and output elements which hasn't been programmed in. You can tell that it has converged by clicking on the test button several times - if the screen doesn't change, then the pattern has converged!

Binary Correlation Matrix Memories

I have recently been introduced to these. I'm not sure whether they count as neural networks, however, but I have them seen referred to as such in the academic press, so I will include them here. They are bi-directional association memories, which means that they associate pairs of binary patterns and can be used either way round i.e., if you associate the binary pattern 11001 with 101110, then you can use 11001 to retrieve 101110, or 101110 to retrieve 11001.

BCMM use arrays (or "matrices" to give them their mathematical name) to store overlapping patterns that hold the individual associations. One pattern is placed along the bottom of the array, the other up the left side. The two patterns needn't be the same length. Here for instance, are the two patterns above:

1
1
0
0
1
1
0
1
1
1
0

The first step is to perform an "outer product" on the two patterns. This means doing a logical AND on the patterns, so that the matrix contains a 1 only in any cell which corresponds to a 1 in both patterns. Effectively, this means that you copy the pattern on the bottom into any row of the array providing that there is a 1 in the first pattern for that row. Below, you will see this done for two pairs of patterns. On the left, 11001 is associated with 101110. On the right, 10101 is associated with 110011.

1
1
0
1
1
1
0
1
1
0
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
1
1
1
0
1
0
1
1
1
0
1
1
1
0
0
1
1
0
0
0
0
0
0
0
1
1
1
0
0
1
1
0
0
0
0
0
0
0
1
1
1
0
0
1
1
1
1
0
0
1
1

You repeat this for as many pairs of patterns as necessary. Be careful not to associate too many pairs, as you may find that the matrix that you will end up with is saturated. Having created all these outer products, perform a logical OR on the matrices that you get. This means that you combine all the matrices into one such that there is a 1 in any cell in which there is a 1 in any of the corresponding cells of the contributing matrices. Compare the matrix that you see below with the two dark red ones next to each other above.

1
1
1
1
1
1
1
0
1
1
1
0
1
1
0
0
1
1
0
0
0
0
0
0
1
1
1
1
1
1

This gives the final correlation matrix memory. The pairs of associations are all stored within it. The question now is, how to we retrieve those associations? Let's suppose we present 10101 to the left side of the matrix, and we want to retrieve 110011 at the bottom. We carry out a logical AND between the presented pattern and each column in the matrix in turn. For example, the first column of the matrix (reading downwards) reads 11101. Carrying out a logical AND with the presented pattern gives 10101, as shown in the first column of the results matrix:

1
1
1
1
1
1
1
0
1
0
1
1
1
0
1
1
1
0
0
1
1
0
0
0
0
0
0
0
1
1
1
1
1
1
1
 
1
1
1
1
1
1
0
0
0
0
0
0
1
1
0
0
1
1
0
0
0
0
0
0
1
1
1
1
1
1
3
3
2
2
3
3

So what are all these 2s and 3s along the bottom row? After having performed the logical AND, I counted the number of 1s in each column. For instance, in the first column we end up with three 1s, and in the third column there are two 1s. The result, 332233 does indeed look a bit like 110011, which is what we want to retrieve. The only thing to do now, is to count the number of 1s in the presented pattern (10101 has three 1s in it), and use that as a "threshold" to compare 332233. Any number within 332233 that is 3 or bigger becomes 1, otherwise it becomes 0. Clearly, the first two numbers and the last two numbers in 332233 becomes 1s as they match the threshold, and the middle two numbers become 0. This means that 332233 turns into 110011, which is the required answer. Of course, there is no reason why we can't present the bottom pattern and retrieve the one at the side. Here we present 101110 at the bottom, perform a logical AND with each row of the matrix and count the number of 1s that result:

1
1
1
1
1
1
1
0
1
1
1
0
1
1
0
0
1
1
0
0
0
0
0
0
1
1
1
1
1
1
1
0
1
1
1
0
4
1
0
1
1
1
0
4
1
0
1
1
1
0
2
1
0
0
0
1
0
0
0
0
0
0
0
0
4
1
0
1
1
1
0
 

This time we get the threshold by counting the 1s in the presented pattern, 101110. This contains four 1s, against which the counts of 44204 are compared. Any digit of this that is 4 or greater, becomes a 1. Otherwise it becomes a 0, so 44204 becomes 11001, which is the original pattern associated with 101110. Clever, isn't it? It's like some sort of magic trick!

Of course, there are drawbacks. For instance, the pattern 00000 could only be associated with 000000 (i.e., one zero pattern can only be associated with another), simply because a logical AND with a zero pattern can only produce a zero pattern. Another problem is that the matrix can easily become saturated - too full of 1s - with the result that patterns can't be retrieved reliably. For instance, associating any pattern that is completely full of 1s with another pattern full of 1s (e.g. 11111 associated with 111111) means that the final CMM will be full of 1s, as it is the result of a logical OR with the component matrices. In the example below, I associate 11111 with 111111, and 00101 with 010110.

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
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
1
1
0
0
0
0
0
0
0
0
1
0
1
0
1
1
0
0
1
0
1
1
0

The resulting CMM is all full of 1s, of course:

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

If you try to retrieve any pattern apart from 00000 (or 000000, of course) you will automatically get a pattern that is all 1s (either 11111 or 111111). The CMM works best when the patterns being associated are sparse (i.e. mainly but not entirely 0s).

In order to try a CMM for yourself, I have created an interactive one below.

 
 
 
 
 
 
 
 
 
 
 


Go back

Top of the page

Go on