[GO] Try implementing associative memory with Hopfield network in Python

Introduction

The Hopfield Network was proposed by the American physicist Hopfield in the early 1980s. Hopfield introduced the concept of energy into neural networks. Furthermore, he showed that it can be applied not only to associative memory but also to optimization problems such as the traveling salesman problem. ** Here, we deal with associative memory. ** Make the neural network memorize the pattern (memorization process) and remind it (recollection process). Specifically, embed the following black-and-white image (the character string has no particular meaning) in the neural network, and give it a noise-added pattern to remind it.

If you set the noise-added pattern as the initial pattern (left image below) and repeat the update, the memory pattern will be recalled (right image below).

Implemented associative memory in Python. If you have a google account, you can do it right away from here (Google Colab).

Model [1] [2]

The structure of the Hopfield network is as follows (for 5 neurons): The double-headed arrow represents the interconnect. The figure below is a structure that does not consider self-joining.

Memorization process

The pattern is memorized by changing the connection load of the neural network. The pattern is represented by the vector $ \ boldsymbol {x} = (x_1, ..., x_N) (x_i: 1 \ leqq i \ leqq N) $. $ N $ is the number of neurons (number of units). $ P $ vectors to be memorized (\ boldsymbol {x} ^ {(1)}, ..., \ boldsymbol {x} ^ {(P)}) (\ boldsymbol {x} ^ {(k) }: 1 \ leqq k \ leqq P) $ When there is a matrix

X
=
\begin{bmatrix}
\boldsymbol{x}^{(1)} \\
\vdots \\
\boldsymbol{x}^{(P)}
\end{bmatrix}
=
\begin{bmatrix}
x_1^{(1)} & \cdots & x_N^{(1)} \\
\vdots & \ddots & \vdots \\
x_1^{(P)} & \cdots & x_N^{(P)}
\end{bmatrix}
(P × N matrix)
\tag{1}

It is expressed as. The pattern you want to memorize is called a memorized pattern. Once the memory pattern is ready, we will embed it in the neural network. When you memorize it, ask them to remember it one by one. The coupling load is changed each time one pattern is applied to the neural network. The binding load $ w_ {ij} $ from neuron $ i $ to neuron $ j $ changes by $ \ Delta w $ in the following equation.

\Delta w = (2x_i^{(k)} - 1)(2x_j^{(k)} - 1) \tag{2}

Equation (2) is when the element of the pattern vector to be embedded is a binary value of 1 or 0. If the elements of the pattern vector are -1,0,1, $ \ Delta w $ becomes the following formula.

\Delta w = x_i^{(k)} x_j^{(k)} \tag{3}

The above equations (2) and (3) are learning rules called ** Hebb's law **. The connection load between neurons with the same output is increased, and the connection load between neurons with different outputs is weakened. When the number of neurons is $ N $, there are $ N × N $ binding loads $ w_ {ij} $. If the pattern prepared in Eq. (1) is embedded in Eqs. (2) and (3), the matrix-type coupling load $ W $ can be expressed as in the following equation.

W
=
\begin{bmatrix}
w_{11} & \cdots & w_{1N} \\
\vdots & \ddots & \vdots \\
w_{N1} & \cdots & w_{NN}
\end{bmatrix}
=
(2X-1)^T(2X-1)
\hspace{10pt}
(N × N matrix)
\tag{4}

W
=
\begin{bmatrix}
w_{11} & \cdots & w_{1N} \\
\vdots & \ddots & \vdots \\
w_{N1} & \cdots & w_{NN}
\end{bmatrix}
=
X^TX
\hspace{10pt}
(N × N matrix)
\tag{5}

Recollection process

The recall process begins with setting any input pattern $ \ boldsymbol {x'} = (x_1', ..., x_N') $ as the initial state of the neural network. This input pattern $ \ boldsymbol {x'} $ is called the initial pattern. The Hamming distance is used to show how different the initial pattern and the memory pattern are. Below are the definitions of the Hamming distance $ d $ for the storage pattern $ \ boldsymbol {x} $ and the initial pattern $ \ boldsymbol {x'} $. In the case of $ x_i ^ {(k)} = -1,0,1 , 1/2 is added to the following formula. $ x_i ^ {(k)} = 0,1 \ hspace {10pt} (1 \ leqq i \ leqq N, 1 \ leqq k \ leqq P) $$

d = \sum_{i=1}^N |x_i - x_i'| \tag{6}

After setting the initial pattern to the initial state, repeat the following update steps ① and ② the specified number of times. ① Randomly select one neuron $ m $ from the neurons. Next, find the output $ y_m (t) $ of the neuron $ m $.

s(u):Step function\\
s(u) = \left\{
\begin{array}{ll}
1 & (u > 0) \\
0 & (u \leqq 0)
\end{array}
\right. \hspace{10pt}
Or\hspace{10pt}
s(u) = \left\{
\begin{array}{lll}
1 & (u > 0) \\
0 & (u = 0) \\
-1 & (u < 0)
\end{array}
\right. \\
\boldsymbol{w_m}:Binding load to neuron m\\
b_m:Bias (threshold, threshold)

y_m(t)=s(u)=s(\boldsymbol{x} \boldsymbol{w_m} + b_m) \tag{7}

(2) Update the next state $ y_m (t + 1) $ of the neuron $ m $ to the value obtained by Eq. (7). Other than the neuron $ m $, it remains unchanged.

y_m(t+1)←y_m(t) \tag{8}

This method of updating only one neuron is called asynchronous update. Hopfield networks seem to refer to asynchronous updates. It has been theoretically shown that the energy of the network keeps falling as the updates are repeated. Energy is defined as follows.

E(t) = -\frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N w_{ij}x_i(t)x_j(t) - \sum_{j=1}^N b_jx_j(t) \tag{9}

Classes and functions

• Class

Pattern: A class that reads patterns.

• Function

weight_cal1 (X): Sets the coupling load when the elements of the pattern vector are 0,1. weight_cal2 (X): Sets the coupling load when the element of the pattern vector is -1,0,1. hamming (ptn_vec1, ptn_vec2): Returns the Hamming distance of the two pattern vectors given as arguments. set_ptn_vec1 (ptn_vec, difference_rate): Initial pattern generation function when the elements of the pattern vector are 0,1. set_ptn_vec2 (ptn_vec, difference_rate): Initial pattern generation function when the elements of the pattern vector are -1,0,1. A step function that returns step_function1 (x): 0,1. A step function that returns step_function2 (x): -1,0,1. sync (ptn_vec, weight, bias, func): A function that performs synchronous updates. ʻAsync (ptn_vec, weight, bias, func) : A function that performs asynchronous updates. ʻEnergy_cal (output, weight, bias): Calculates the energy of the neural network. display_pattern (ptn_vec): Outputs the pattern vector given as an argument to the screen. display_pattern_all (ptn): Outputs all the patterns given in the argument to the screen.

The following three modules are used.

HopfieldNetwork.ipynb

import numpy as np
import random
import matplotlib.pyplot as plt

Practice

First, read the pattern and set the coupling load.

HopfieldNetwork.ipynb

ptn = np.array([[0, 0, 0, 1, 1, 0, 0, 0, 
                 0, 0, 1, 1, 1, 1, 0, 0, 
                 0, 0, 1, 0, 0, 1, 0, 0, 
                 0, 1, 1, 0, 0, 1, 1, 0, 
                 0, 1, 1, 1, 1, 1, 1, 0, 
                 1, 1, 1, 1, 1, 1, 1, 1, 
                 1, 1, 0, 0, 0, 0, 1, 1, 
                 1, 0, 0, 0, 0, 0, 0, 1],
                [0, 0, 0, 0, 0, 0, 0, 0, 
                 1, 1, 0, 0, 0, 0, 1, 1, 
                 1, 1, 0, 0, 0, 0, 1, 1, 
                 1, 1, 1, 1, 1, 1, 1, 1, 
                 1, 1, 1, 1, 1, 1, 1, 1, 
                 1, 1, 0, 0, 0, 0, 1, 1, 
                 1, 1, 0, 0, 0, 0, 1, 1, 
                 0, 0, 0, 0, 0, 0, 0, 0],
                [1, 1, 1, 1, 1, 1, 1, 1, 
                 1, 1, 1, 1, 1, 1, 1, 1, 
                 1, 0, 0, 1, 1, 0, 0, 1, 
                 0, 0, 0, 1, 1, 0, 0, 0, 
                 0, 0, 0, 1, 1, 0, 0, 0, 
                 0, 0, 0, 1, 1, 0, 0, 0, 
                 0, 0, 0, 1, 1, 0, 0, 0, 
                 0, 0, 1, 1, 1, 1, 0, 0]])

#Load pattern
row = column = 8
pattern = Pattern(row, column, ptn)
#Display the loaded pattern
display_pattern_all(pattern.X)
#Determine the coupling load
weight = weight_cal1(pattern.X)
#All biases are 0
bias = np.zeros(pattern.unit)

Execution result

Next, let us recall the case of k = 1. The Hamming distance between the memory pattern and the initial pattern was set to 10.

HopfieldNetwork.ipynb

%%time
#Set the upper limit of the number of updates
time = 1000
#Select a pattern
k = 1
#Generate initial pattern
hamming_distance = 10
ini_ptn_vec = set_ptn_vec1(pattern.X[k-1], hamming_distance/pattern.unit)
#Show initial pattern
print("Initial pattern")
display_pattern(ini_ptn_vec)
#Initial pattern energy
energy = []
energy.append(energy_cal(ini_ptn_vec, weight, bias))
#Continue updating up to 1000 times
for i in range(time):
    #Asynchronous update
    async(ini_ptn_vec, weight, bias, step_function1)
    #Add energy in the process of updating to the list
    energy.append(energy_cal(ini_ptn_vec, weight, bias))
    #Exit the loop if you can recall the memory pattern
    if(hamming(ini_ptn_vec, pattern.X[k-1]) == 0):
        print("Number of updates time=", i)
        break
#Show the pattern that was finally recalled
print("Recollected pattern")
display_pattern(ini_ptn_vec)

Execution result

Check the transition of the energy added to ʻenergy`.

HopfieldNetwork.ipynb

plt.plot(energy)
plt.ylabel("energy", fontsize=18)
plt.xlabel("time", fontsize=18)
plt.show()

Execution result

For the time being, the flow of associative memory by the Hopfield network is as described above. At a later date, I would like to post some experiments.

References

[1] Hopfield, J.J. (1982): “Neural networks and physical systems with emergent collective computational abilities”, Proc. Natl. Sci. USA, 79, 2554-2558. [2] Kaoru Nakano et al. (1990): Basics of Neurocomputer Corona Publishing Co., Ltd.