\documentclass[12pt]{article}

\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{rsfs}

\textheight 230mm
\topmargin 5mm
\textwidth 160mm
\oddsidemargin -2mm

%% \textheight 250mm
%% \topmargin -10mm
%% \textwidth 180mm
%% \oddsidemargin -7mm

\newtheorem{formula}{Rule}
\newtheorem{example}{Example}
\newtheorem{excersize}{Excersize}
\newtheorem{algorithm}{Algorithm}

\begin{document}
\pagestyle{myheadings}
\markright{(Associative Memory by Hopfield Neural Network)} 
\thispagestyle{empty}

\title{{\large (Brest State Technical University 2005 Spring Semester: Corse Practice)}\\
\bigskip
{\bf Associative Memory \\by Hopfield Neural Network}} 
\author{Akira Imada\\
(e-mail akira@bstu.by)\\
\hspace{1in}\\
This document is still under construction and was lastly modified on}
\maketitle

\vspace{0.5in}

\begin{center}{\bf INDEX}\\
\hspace*{1in}\\
1st Week \\
%%\hspace*{1in}\\
Start with random pattern with random weight values.\\
\hspace*{1in}\\
2nd Week \\
%%\hspace*{1in}\\
Store one pattern.\\
\hspace*{1in}\\
3rd Week \\
Store multiple patterns.\\
\hspace*{1in}\\
4th Week \\
How many patterns can be stored?\\
\hspace*{1in}\\
An additional Week \\
Storing animation.

\end{center}

\clearpage
\section{1st week}
\noindent
The first task of this practice is to create your own hopfield network as follows, today.
\begin{itemize}
\item Number of neuron $N=100$
\item At time $t$, neuron $j$ takes a state $S_i(t)= 1$ or $-1$ \hspace*{.01in}
$(i=0,1,2, \cdots, 99).$
   \begin{itemize}
   \item Time here is descrete, that is, $(t = 0, 1, 2, \cdots).$
   \end{itemize}
\item All the neuron inclucing itself connectted with each other.
   \begin{itemize}
   \item Hence total connections are $N^2 = 10,000$
   \end{itemize}
\item Weight value from neuron $i$ to $j$ denoted as $w_{ji}$ takes a random value 
from $-1.0$ to $1.0$, today.
\end{itemize}

\begin{figure}[h]
 \begin{center}
\includegraphics[width=8cm,height=6cm]{hopf-example.eps}
 \end{center}
 \caption{}
\end{figure}

\noindent
The state of neuron at time $t+1$ will be ON $(+1)$ if all the weighted sum from 
all neurons (the other 99 neurons and itself) is positive, otherwise OFF $(-1)$.
That is,

\begin{equation}
S_i (t+1) = {\mbox sgn}( {\sum_{j=0}^{99} {w_{ij}S_i (t)})}
\end{equation}

\begin{excersize}
On your monitor screen, display 100 neuron each of which takes 
a state of $-1$ or 1 at random. This is the pattern at $t=0$.
Then renew states from one time to the next and display states of 
100 neurons.
\end{excersize}



\section{2nd week}
In the hopfield network created in the 1st week, we try to store a pttern.
In the 1st week both state configuration and weight values are random, but this week
we specify them.\\

\noindent
The pattern is constructed as 2-dimensional array of $N=100$ neurons like below.

\begin{figure}[bhtp]\label{fig:well-separate-gaussian}
 \begin{center}
\includegraphics[width=4cm,height=4cm]{hopf-pattern.eps}
 \caption{}
 \end{center}
\end{figure}

\noindent
We interpret it as 2-dimensional pixels, not color, not gray-scale, but black-and-white ones.
That is, The state of 1 is black and the state of $-1$ is white.
Hence, today $w_{ij} = w_{ji}$. \\


\noindent
Weight value is determined such that if and only if the both ends of the connection is $1$,
the weight value of the connection is 1, otherwise $-1$. The weight value of the conection
from one neuron to itself are set to 0, that is, $w_{ii} = 0$, today. That is,

\bigskip
\begin{figure}[bhtp]\label{fig:well-separate-gaussian}
 \begin{center}
\includegraphics[width=12cm,height=1.5cm]{weight.eps}
 \end{center}
 \caption{An example of specifying weight values. The value is +1, $-1$ or 0 depending on
states of neurons of the both end of the connection.}
\end{figure}

\noindent
Or, if you like mathematics, the fomula of determining $w_{ij}$ is
\begin{equation} \label{eq:1-2}
w_{ij} = \xi_i \xi_j \hspace{.1in}(i \ne j), \hspace{.1in} w_{ii} = 0
\end{equation}

\noindent
where $\xi_i$ is the state of $i$-th neuron.

\begin{excersize}
On your monitor screen, display 100 neuron each of which takes 
a state of $-1$ or 1 such that those neurons whose state 1 construct a border of rectangle
while neurons of $-1$ are backgraound. Specify weight of connections using Eq.~(\ref{eq:1-2}).
Start with some noisy pattern try to observe at time is $1,2, \cdots$.
\end{excersize}



\section{3rd week}
With the same frame work as the 2nd week, let's increase the number of patterns.
After storing the 1st pattern as you did last time, add the next patterns
one by one adding +1 to the connection weight if both end of the connection
is +1 for the 2nd pattern otherwise adding -1. To be more specific: 

\begin{equation} \label{eq:1-2}
w_{ij} = \sum _{ \mu = 1}^{p} 
         {{ \xi }_{i}^{ \mu }{ \xi }_{j}^{ \mu }}
         \hspace{.1in}(i \ne j), \hspace{.1in} w_{ii} = 0.
\end{equation}

\noindent
As a result if you store $p$ patterns the weight values ranges from $-n$ to $n.$

\begin{excersize}
Try to store multiple patterns and observe how it is clever.
As an experiment, try to start with the pattern of all white pixcels.
\end{excersize}




\section{4th week}
Then we are curious how many patterns we can store.

\begin{excersize}
Try to store as many as patterns so that we observe a confusion. 
\end{excersize}


\section{An additional week -- For those who failed}
Hopfield network can also store animation made up of $p$ patterns, 
by specifying weights as:

\begin{equation} \label{eq:1-2}
w_{ij} = \sum _{ \mu = 1}^{p} 
         {{ \xi }_{i}^{ \mu+1}{ \xi }_{j}^{ \mu }}
         \hspace{.1in}(i \ne j), \hspace{.1in} w_{ii} = 0.
\end{equation}

\begin{excersize}
Prepare, say, 3 patterns and specify weights with the above equation. Observe
the result starting with one of those 3 patterns.
\end{excersize}

\noindent
Assume now 100 newrons (10 by 10 pixcels) 3 patterns. That is, our pattern is
\begin{displaymath}
\xi^1_1, \xi^1_2, \xi^1_3, \cdots \xi^1_{100}, \hspace{.2in}
\xi^2_1, \xi^2_2, \xi^2_3, \cdots \xi^2_{100}, \hspace{.2in} {\mbox and}\hspace{.1in}
\xi^3_1, \xi^3_2, \xi^3_3, \cdots \xi^3_{100}.
\end{displaymath}
We now take it a try your animation with three frames, like


\begin{figure}[bhtp]\label{fig:well-separate-gaussian}
 \begin{center}
\includegraphics[width=12cm,height=4cm]{animation.eps}
 \end{center}
 \caption{An example of specifying weight values. The value is +1, $-1$ or 0 depending on
states of neurons of the both end of the connection.}
\end{figure}


\end{document}




\begin{figure}[hbtp]
\begin{center}
   \epsfile{file=patterns.eps,width=12cm,height=3cm}
   \caption{An example for $N=3$. White pixcel is represented by $-1$ and 
            white pixel is by $+1$. That is, patterns are represented 
            with 9-bit {\it bipolar} vectors.}
\end{center}
\end{figure}


\noindent
To be more formal, our $p$ patterns are expressed as

\begin{equation}
(\xi^1_1, \xi^1_2, \cdots, \xi^1_N),\hspace{.1in}
(\xi^2_1, \xi^2_2, \cdots, \xi^2_N),\hspace{.1in}
(\xi^3_1, \xi^3_2, \cdots, \xi^3_N),\hspace{.1in} \cdots, \hspace{.1in}
(\xi^p_1, \xi^p_2, \cdots, \xi^p_N).
\end{equation}

\noindent
where $\xi^{\mu}_{i} \in \{-1,1\}$, \hspace{.05in} 
$\mu = 1,2, \cdots, p$ \hspace{.05in} and \hspace{.05in} 
$i = 1,2, \cdots, N^2.$ \\

\hspace*{1in}\\
\noindent
For example, the first example in the Figure 1 is 

\begin{displaymath}
(-1, +1, -1, 
 +1, +1, +1, 
 -1, +1, -1)
\end{displaymath}



\newtheorem{excersize}{Excersize}
\begin{excersize}[10 Patterns to be Stored]
Create your own 10 patterns 
each of which is made up of $10 \times 10$ binary pixels.
\end{excersize}



\section{Construct a Hopfield Neural Network to store your patterns!}

\noindent
Now Let's create a Hopfield Neural Network with $N \times N$ neurons.
All neurons are connected with each other via synapse.\\

\noindent
Each of  neurons are influenced by other $(N \times N -1)$ neurons.
The strength of an influence from one neuron is according to the weight value
of the synapse.  
Thus, state of neuron $i$ at time $t+1$ $s_{i}\hspace{.02in} (t+1) $is given as

%%\begin{Large}
\begin{equation} \label{eq:1-1}
  s_{i}\hspace{.02in} (t+1) 
    = sgn \hspace{.02in} \left( \hspace{.04in} 
      \sum_{j \ne i}^N { w_{ij} \cdot s_{j}(t)} \hspace{.04in} \right).
\end{equation}
%%\end{Large}

\subsubsection{How we update state of neurons?
--- Sinchronous and Asynchronous update}
\noindent
Now a question arise, how are neurons updated? Simultaneously-at-a-time 
or one-by-one? The former is called {\it Sinchronous update} and the latter
is {\it Asynchronous update.} In this practice course we use the asynchronous
update.\\

\noindent
In other words, at time $t$, neuron-1 is firstly updated, and, 
this new state will be used to update other neurons here after; 
next, neuron-2, neuron-3, and so on, until all the neurons are updated.
Then this updated procedures are repeated at time $t+1$, 
and on and on. \footnote {We can update neurons in a random order
different order at every time $t$, but here we update from the 1st neuron
to the last neuron one by one.}

\subsection{An experiment with random weight values:}
Now we have $10^2$ synapses and each snyapse has 
a strength called {\it weight}.
The weight value from neuron-$j$ to neuron-$i$ is denoted here as $w_{ij}$
\hspace{0.05in} $i,j = 1,2, \cdots 100$. \\

\noindent
We must assign these 100 weight values appropriately to store
our patterns. However, we start with a set of 100 random values
each of which is in $[-1, 1]$, such as $-0.534$, are assigned.


\begin{excersize}[Observe the behaviours of your Hopfield Network.]
Give one of your patterns to your Hopfield Network 
with random weight values, and observe what will happen.
That is, set $S_i(0) = \xi_i^\mu$ for all $i = 1, 2, \cdots, N^2$
with a specific $\mu$ you like. Then observe the pattern 
for $t= 1, 2, \cdots$, namely, how the pattern changes as time proceeds. 
\end{excersize}

\section{Let's store your patterns!}

\subsection{Hebbian Learning}
Here we calculate the weight according to the following equation,
called Hebbian Learning.
\begin{Large}
\begin{equation} \label{eq:1-2}
w_{ij} = \frac{1}{N} \sum _{ \mu = 1}^{p} 
         {{ \xi }_{i}^{ \mu }{ \xi }_{j}^{ \mu }}
         \hspace{.1in}(i \ne j), \hspace{.1in} w_{ii} = 0.
\end{equation}
\end{Large}


\begin{excersize}[Observe the behaviours of your Hopfield Network Part II.]
Repeat the previous excersize with the weights calculated with the above
equation, instead of random values.
\end{excersize}

\section{Let's observe how it is clever (or fool)!}
Now if your work is successful
Network recognize your patterns in the following way.
\begin{itemize}
\item[(1)] If you give one of your patterne as it is, 
then the initial state never be changed. \footnote{In
this case the pattern is called {\it fixed point}.}
\item[(2)] If you give a noisy version of your pattern, then
initial state changes several  steps and converges to the 
original pattern. \footnote{We call it ``An initial state
in the vasin of attraction is attracted to its fixed point.}
\item[(3)] If you give a very different pattern from any of 
your patters, then network shows a {\it chaotic} behaviour,
e.g., repeat a same cycle of patterns or changes forever in
a random way.
\end{itemize}

\noindent
Then you may test your Hopfield Network to know how it is clever
or fool.by changing (i) the number of patterns stored and/or
(2) number of noisy bit.

\begin{excersize}[Observe the behaviours of your Hopfield Network Part III.]
Starting with 1 pattern, test the capability of the Network
by incrementing the number of noisy bits from zero, 
and observe when the Network become to be chaotic.
Plot this critical number as a function of number of noise with
a parameter of the number of patterns stored.  
\end{excersize}

