\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?
\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}





\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}

