Hopfield (By John Hopfield, 1982) and Binary Associative Memory (BAM, by Bart Kosko, 1988) neural networks were introduced around 40 years ago, and are simple enough that you can do training and inference with a pen and paper, using only integers. This blog post will show how.
Both networks are associative memory networks that work with binary patterns.
Hopfield networks are auto-associative which means when you give them a pattern as input, they are designed to give you the closest pattern that was part of their training data. This is useful if you have some input pattern that might contain noise or error, and you want to know what the uncorrupted pattern is.
BAM networks are hetero-associative which means they map possibly corrupted input patterns to output patterns. BAM networks are bidirectional, meaning you can also plug a possibly corrupted output pattern in to get an input pattern. You can make a BAM network auto-associative by having it map input patterns to the same patterns as output. If you do that, you get something similar to a Hopfield network, but not quite the same thing.
Interestingly, Hopfield networks have a link to more modern techniques. Apparently, a single update step in a modern continuous Hopfield network is identical to the self-attention mechanism in Transformers. You can read more about that in the 2020 paper “Hopfield Networks is All You Need” : https://arxiv.org/abs/2008.02217. There are also continuous valued versions of Hopfield and BAM but we won’t be talking about those today.
Let’s get into the details.
A Hopfield network takes an N bit vector as input and gives an N bit vector as output. We will make an example Hopfield network that is trained on these two 5 bit binary patterns:
- A = 11000
- B = 10101
Hopfield networks don’t work with binary numbers though, they work with bipolar numbers. Where binary numbers are made up of 0 and 1, bipolar numbers are made up of -1 and +1. So, let’s convert our binary patterns into bipolar:
- A = 1, 1, -1, -1, -1
- B = 1, -1, 1, -1, 1
To train the network, we first need to take the outer product of each training pattern with itself.
We then sum up the matrices, using element wise addition.
Lastly, we zero out the main diagonal, and the training is complete:
Doing Network Inference
Network inference is an iterative process, but usually only requires one iteration.
You take your binary input, convert it from binary (0,1) to bipolar (-1,1) and do a matrix multiply against the matrix H. In the output vector, you convert negative numbers to -1, and positive numbers to 1. If there is a zero in the output vector, you take the value from the input vector.
You repeat that until the output stops changing (input == output) or until you hit a maximum iteration count.
A common implementation of this is to do the matrix multiplication in a shuffled order (update the output values in a random order aka shuffle the order of the dot products that make up the matrix multiply), and have it write the output value back into the input vector for each one. Doing it this way, each element of the input/output vector is a neuron, and the neurons are updated in a shuffled order, but the updated neuron values are visible to other neurons in the same update pass.
Below we will be doing the updates in unshuffled order, as a normal matrix multiplication, but shuffling the order would be a better implementation.
Inference Example: 10000
Let’s put the binary pattern 10000 through the network.
First we convert it to bipolar:
Then we multiply the bipolar vector by our matrix:
We now need to apply the “sign” function to the values in the output vector: If the value is positive, replace it with a 1. If the value is negative, replace it with a -1. If the value is 0, use the input value.
Doing that gives us:
Converting that from bipolar back to binary gives us 11000, which is pattern A that we trained the network with.
Success! We put in a corrupted A pattern, and got the uncorrupted A pattern as output.
More Examples
Here are other patterns I put in to test our network, omitting the matrix multiply and conversion steps.
- 11000 (pattern A) gives 11000 (pattern A)
- 10101 (pattern B) gives 10101 (pattern B)
- 00111 (inverted pattern A) gives 00111 (inverted pattern A)
- 01010 (interved pattern B) gives 01010 (inverted pattern B)
- 10100 gives 10101 (pattern B)
- 10001 gives 10101 (pattern B)
- 01111 gives 00111 (inverted pattern A)
I showed the inverted patterns above because with both Hopfield and BAM networks, they learn the patterns you give them, and also the inverted versions of the patterns.
Multiple Iterations Needed
All of the patterns above took a single iteration to reach a stable pattern. They all gave one of the trained patterns as output, and we saw that the trained patterns as input would give themselves as output, so are stable. Not all input patterns converge after one step, and in fact, not all input patterns converge!
Here is an example infinite iteration loop, which shows why having a maximum iteration count is useful.
-
10010 gives 01000
-
01000 gives 11010
-
11010 gives 01000 (aka GOTO 2) This might seem strange, but look at the table below. It shows how pattern 1 above differs from the 2 explicit and 2 implicit (inverted) patterns that our network has memorized. Doing one iteration step of inference is meant to move our input pattern closer to an output pattern. We can see that it’s just as close to A as it is to inverted B so we would expect it to move closer to at least one of those patterns.
| Name | Pattern | # Bits Differing From Input | | Input | 10010 | 0 | | A | 11000 | 2 | | B | 10101 | 3 | | Inverted A | 00111 | 3 | | Inverted B | 01010 | 2 |
After running inference on 10010, we get as output 01000. Below we can see that it got closer to both of those patterns (A and inverted B) and farther away from B and inverted A. It made forward progress!
| Name | Pattern | # Bits Differing From Input | | Input | 01000 | 0 | | A | 11000 | 1 | | B | 10101 | 4 | | Inverted A | 00111 | 4 | | Inverted B | 01010 | 1 |
After doing another iteration of inference on 01000, we get the output 11010. As you can see that pattern has the same number of bits different from each of the stored patterns. We haven’t moved forwards or backwards, we moved to the side.
| Name | Pattern | # Bits Differing From Input | | Input | 11010 | 0 | | A | 11000 | 1 | | B | 10101 | 4 | | Inverted A | 00111 | 4 | | Inverted B | 01010 | 1 |
If we run another iteration on 11010, it gives us 01000, which again is a sideways move that doesn’t get any better or worse, and enters us into an infinite loop. Even though the pattern didn’t converge, it did improve – it got closer to the patterns it was a closer match to, and farther from the patterns it was a farther match to.
Doing a shuffled order neuron update could help this infinite loop break up by breaking the symmetry.
Other Items
Unsurprisingly, there is a maximum density of patterns that you can store in both a Hopfield and BAM network. The more patterns you give it, the worse they get at recall. One way of thinking about this is that there will be more patterns and inverted patterns available to be close to, and so more “local minima” to get stuck in, instead of arriving at an actual stored pattern.
Before we move on, I also want to note that if you want to train a Hopfield or BAM network on 2d data or higher, you can do that, you just need to flatten all the data into one long 1d vector. This is the same as how a 2d image is a 1D list of pixels in memory, with each row of pixels coming directly after the last row of pixels.
BAM networks are simpler than Hopfield networks, and they can associate input/output pattern pairs. They are less theoretically sound than Hopfield networks though, which is why they are not as well known.
For BAM networks, each training item is an input output pair. Here are the two pairs we will be training our network on:
- A: 11000 -> 011
- B: 10101 -> 100
Once again, we need to convert the patterns from binary to bipolar:
- A: 1,1,-1,-1,-1 -> -1,1,1
- B: 1,-1,1,-1,1 -> 1,-1,-1
Next, for each pattern, we take the outer product of the input and the output:
Lastly, we sum up the outer products. For BAM networks, we DO NOT zero out the main diagonal, even if the matrix is a square matrix.
That is the matrix we use if we want to plug an output pattern in, and recall an input. If we want to plug an input pattern in to get an input, we need to use the transpose matrix:
Doing Network Inference
Inference in a BAM network is much the same as in a Hopfield network. You do a matrix multiply of bipolar values, and put the result through the same sign function as in the Hopfield network
The literature does not say to do a randomized neuron evaluation order though, and one iteration of inference involves two steps:
- Plug in the input vector to get an output vector
- Plug in the output vector to get an input vector
You repeat that until it stabilizes, or until you reach a max iteration count. Note that if you start by plugging in an output vector to get an input vector, the second part of an iteration would be to plug in the input vector to get an output vector.
Inference Example: 10000
We first convert the binary value 10000 to bipolar, to get 1, -1, -1, -1, -1. We next multiply that by the transpose matrix, to get an output value.
We then put the result through the same sign function as the Hopfield Network. Negative values become -1. Positive values become 1. Zero means to take the value from the vector we multiplied the matrix by. That gives us:
Converting that from bipolar to binary gives us: 001.
Success! we gave a corrupted A input value, and got an uncorrupted A output value.
More Examples
- 11000 (pattern A input) gives 001 (pattern A output)
- 001 (pattern A output) gives 11000 (pattern A input)
- 10101 (pattern B input) gives 100 (pattern B output)
- 100 (pattern B output) gives 10101 (pattern B input)
- The inverse pattern A and B are also recalled in the same way as the above 4 bullet points
And another corrupted test: 01011 gives 011 (pattern B inverse).
Hopefully you found this interesting. You can definitely use these neural networks to recall patterns, or do error correction on corrupted patterns, and you can even do it on paper, with a pen or pencil, using only integers. John Hopfield won a Noble Prize in 2024 for work including this neural network.
These networks are old though, so beyond novelty or toy use, you might want to use something newer. It looks like a “Discrete Modern Hopfield Network” is the thing to look at, and is from 2017 https://en.wikipedia.org/wiki/Modern_Hopfield_network.
Here’s a hopfield network implemented in a web page, for learning and recalling 2d binary images interactively:https://visualize-it.github.io/hopfield_networks/simulation.html
Wikipedia: