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.

image.png

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). image.pngimage.png

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. HopfieldNetWork.png

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.

x_i ^ {(k)} = 0,1 \ hspace {10pt} (1 \ leqq i \ leqq N, 1 \ leqq k \ leqq P)
\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.

x_i ^ {(k)} = -1,0,1 \ hspace {10pt} (1 \ leqq i \ leqq N, 1 \ leqq k \ leqq P)
\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.

x_i ^ {(k)} = 0,1 \ hspace {10pt} (1 \ leqq i \ leqq N, 1 \ leqq k \ leqq P)
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}
x_i ^ {(k)} = -1,0,1 \ hspace {10pt} (1 \ leqq i \ leqq N, 1 \ leqq k \ leqq P)
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

Pattern: A class that reads patterns.

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 image.png

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 image.png

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.

Recommended Posts

Try implementing associative memory with Hopfield network in Python
Try implementing Yubaba in Python 3
Try working with binary data in Python
Load the network modeled with Rhinoceros in Python ③
Try implementing two stacks in one array in Python
Try working with Mongo in Python on Mac
Load the network modeled with Rhinoceros in Python ②
Try implementing the Monte Carlo method in Python
Load the network modeled with Rhinoceros in Python ①
Try scraping with Python.
Try gRPC in Python
Try 9 slices in Python
Try implementing Yubaba with Brainf * ck 512 lines (Generate and execute code in Python)
Try embedding Python in a C ++ program with pybind11
Scraping with selenium in Python
Working with LibreOffice in Python
Try implementing RBM with chainer.
Scraping with chromedriver in python
Neural network with Python (scikit-learn)
Debugging with pdb in Python
Try Python output with Haxe 3.2
Try implementing XOR with PyTorch
Working with sounds in Python
Scraping with Selenium in Python
Try LINE Notify in Python
Scraping with Tor in Python
Tweet with image in Python
Combined with permutations in Python
Try running Python with Try Jupyter
Try implementing perfume with Go
Neural network implementation in python
Try face recognition with Python
Network programming with Python Scapy
Try running python in a Django environment created with pipenv
Try scraping the data of COVID-19 in Tokyo with Python
Try sorting your own objects with priority queue in Python
Try to automate the operation of network devices with Python
Try building a neural network in Python without using a library
Number recognition in images with Python
Check for memory leaks in Python
Try scraping with Python + Beautiful Soup
Testing with random numbers in Python
Neural network with OpenCV 3 and Python 3
GOTO in Python with Sublime Text 3
[Python] Generate QR code in memory
Working with LibreOffice in Python: import
[Cloudian # 6] Try deleting the object stored in the bucket with Python (boto3)
Measuring network one-way delay with python
CSS parsing with cssutils in Python
Try to operate Facebook with Python
Try singular value decomposition with Python
Numer0n with items made in Python
Try using LevelDB in Python (plyvel)
Open UTF-8 with BOM in Python
Let's try Fizz Buzz in Python
Try to calculate Trace in Python
Try PLC register access in Python
Use rospy with virtualenv in Python3
Try face recognition with python + OpenCV
Use Python in pyenv with NeoVim
Heatmap with Dendrogram in Python + matplotlib