\documentstyle[12pt,eclepsf]{article}

\textheight 260mm
\topmargin -10mm
\textwidth 180mm
\oddsidemargin -7mm

\pagestyle{myheadings}
\markright{(Neural Networks: Advanced)}

\begin{document}
\begin{LARGE}


\begin{center}
\begin{Huge}
\noindent
{\bf Neural Networks: Advanced}\\
\end{Huge}

\vspace{1in}
Dokuz Eyl\"{u}l University \\
Computer Engineering Department \\
\hspace*{1in}\\
\begin{large}
25 September 2000 -- 12 January 2001\\
\end{large}
\end{center}

%-----------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf Contents:}\\
\begin{itemize}
\item Introduction
  \begin{itemize}
  \item What are Neural Networks?
  \item Why Neural Networks?
  \end{itemize}
\item Feed Forward Neural Networks
  \begin{itemize}
  \item Specification of the weight by 
     \begin{itemize}
     \item Back Propagation Algorithm
     \item Genetic Algorithm
     \end{itemize}
   \end{itemize}
\item Free Connected Neural Networks
  \begin{itemize}
  \item Toy model with three neurons
  \end{itemize}
\end{itemize}

%-----------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf What is Neural Network?}\\

\noindent
A system with {\it neurons} connected with {\it synapses}, \\

\noindent
where
\begin{itemize}
\item synapse: 
   \begin{itemize}
   \item[] transmits input state value (usually either one or zero)
           with its weight value being multiplied to the input; and
   \end{itemize}
\item neuron: 
   \begin{itemize}
    \item[] takes the weighted sum of fan-in inputs, and
            outputs its function value of the specified
            {\it transfer function} $f(x)$.\\
   \end{itemize}
\end{itemize}

\hspace{1in}\\

\noindent
Typically categorized into two forms:
\begin{itemize}
\item[1.] Layered (feed forward)
\item[2.] Fully-connected
\end{itemize}

\vfill
\noindent
{\bf Keywords:
\begin{itemize}
\item 
neuron, synapse, weight, transfer-function,
layered, feed-forward, fully-connected
\end{itemize}}

%-----------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf Perceptron:}\\

\noindent
An example of single-layered feed forward neural network.\\

\noindent
Suppose:
\begin{itemize}
\item $M$ inputs: $x_1, \cdots x_M$;
\item $N$ outputs: $y_1, \cdots y_N$;
\item each $N$ output neurons are connected with all $M$ input neurons;
\item weight values (of the synapse) from (input) neuron j to (output)  
      neuron $k$ is $w_{jk}$;
\end{itemize}

\hspace{1in}\\

\noindent
then\\
\begin{equation}
y_i = f(\sum_{k=1}^{N} w_{ki}x_k),
\end{equation}
where\\
\begin{equation}
f(x) = \mbox{sgn} (x) \hspace{.2in}  
\mbox{or} \hspace{.2in} f(x) = \tan ^{-1} (x). 
\end{equation}



\vfill
\noindent
{\bf Keywords:
\begin{itemize}
\item perceptron
\end{itemize}}

%-----------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf The simplest example.}\\

\begin{itemize}
\item[1.] AND with two inputs and one output
   \begin{itemize}
   \item[] e.g., 
      \begin{itemize}
      \item $w_{00}=w_{01}=0.7$
      \end{itemize}
   \end{itemize}
\item[2.] How about OR?
   \begin{itemize}
   \item[] e.g., 
      \begin{itemize}
      \item $w_{00}=w_{01}=1.4$
      \end{itemize}
   \end{itemize}
\item[3.] How about XOR?
   \begin{itemize}
   \item Impossible by single layer perceptron.
   \end{itemize}
\end{itemize}

\vfill
\noindent
{\bf Keywords:
\begin{itemize}
\item synaptic plasticity
\end{itemize}}

%-----------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf Perceptron with hidden layers}\\

\noindent
Adding intermediate layer(s) called {\it hidden layer(s)}
between input and output.
\begin{itemize}
\item Suppose $K$ hidden layers.
\item weight from neuron $i$ of the $k$-th layer
               to neuron $j$ of the next layer is denoted as $w_{ij}^k$.
\end{itemize}


\begin{itemize}
\item XOR revisited
   \begin{itemize}
   \item[] e.g.,
      \begin{itemize}
      \item $w_{00}^0 = w_{01}^0 =0.7$, \hspace{.1in}
            $w_{10}^0=w_{11}^0=1.4$,\\
            \hspace*{1in}\\
            $w_{10}^1 = -1.4, \hspace{.1in} w_{11}^1 =1.4$.
      \end{itemize}
   \end{itemize}
\item Separability
   \begin{itemize}
   \item If we can separate the solution space by hyperplane,
      \begin{itemize}
      \item[] (To be more specific, we can separate 2D solution space of 
               2-input AND/OR by a straight line, but not for XOR.)
      \end{itemize}
   \item[] then we can solve the problem by single perceptron.\\
   \item Multi-layer allows us to separate the space by more flexible
         surface, not necessarily the plane.
   \end{itemize}
\end{itemize}

\vfill
\noindent
{\bf Keywords:
\begin{itemize}
\item hidden layer, separability, solution-space
\end{itemize}}


%-----------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf Back Propagation Algorithm}\\

\noindent
Definition of variables:

\begin{itemize}
\item $L$ layers of neurons.
\item $k_r$ neurons in the $r$-$th$ layer.\hspace{.2in} 
      $r = 1,2, \cdots, L.$
\item $l$ input neurons ($k_0 = l$).
\item $w_{jk}^r$: weight to the $j$-$th$ neuron 
      in the $r$-$th$ layer from the $k$-$th$ neuron 
      in the previous layer.
\item $N$ training pairs: $(\mbox{\bf x}(i),\mbox{\bf y}(i))$, 
      \hspace{.2in} $i = 1, 2, \cdots, N$.
\item $y_k^{r}(i)$: the output of the $k$-$th$ neuron in the $r$-$th$
                     layer when the $i$-$th$ training sample is given.
\item fan-in's to $j$-$th$ neuron in the $r$-$th$
                     layer when the $i$-$th$ training sample is given.
   \begin{itemize}
   \item[] $\displaystyle 
           h_j^r(i) \equiv 
           \sum_{k=1}^{k_{r-1}}w_{jk}^r y_k^{r-1}(i) + w_{j0}^r =
           \sum_{k=0}^{k_{r-1}}w_{jk}^r y_k^{r-1}(i)$,
   \end{itemize}
\item[] where $y_0^{r-1} = 1$ and 
   \begin{itemize}
   \item[] $(y_1^0(i), \cdots,  y_l^0(i)) = 
            (x_1(i),   \cdots,    x_l(i)) = \mbox{\bf x}(i) $. 
   \end{itemize}
\item Each output neuron's error: 
   \begin{itemize}
   \item[] $ e_m(i) \equiv y_m(i)- \hat{y}_m(i)$, \hspace{.2in}
           $ i = 1,2, \cdots, N $.
   \end{itemize}
\item[] where $ (\hat{y}_1(i), \cdots, \hat{y}_{k_{\small L}}(i)) 
                = \mbox{\bf y}(i)$
\item Error function to be minimized:
   \begin{itemize}
   \item[] $\displaystyle D= 
           \frac{1}{2} \sum_{i=1}^{N} \sum_{m=1}^{k_{\small L}} e_m(i)^2$
   \end{itemize}
\end{itemize}


\clearpage
\noindent
The algorithm:
\begin{itemize}
\item[1.] {\it Initialization:} Initialize all the weights with small 
          random values.
\item[2.] {\it Forward computations:} For each of the training vectors
   \begin{itemize}
   \item[] $\mbox{\bf x}(i), \hspace{.2in} i = 1, 2, \cdots, N $
   \end{itemize}
\item[] compute all the 
   \begin{itemize}
   \item[] $y_j^r(i) = f (h_j^r(i))$
   \end{itemize}
\item[] for $j = 1, 2, \cdots, k_r $ and $ r = 1, 2, \cdots, L$.
\item[3.] {Backward computations:} For each $i = 1, 2, \cdots, N$, 
          and $j = 1, 2, \cdots, k_{\small L} $ compute
   \begin{itemize}
   \item[] $ \delta_j^L(i) = e_j(i)f^{\prime}(h_j^L(i))$
   \end{itemize}
\item[] then compute
   \begin{itemize}
   \item[] $ \delta_j^{r-1}(i) = e_j^{r-1}(i)f^{\prime}(h_j^{r-1}(i))$
   \end{itemize}
\item[]for $ r = L, L-1, \cdots ,2$ and $j = 1, 2, \cdots, k_r$ where
   \begin{itemize}
   \item[] $ \displaystyle e_j^{r-1}(i) = 
             \sum_{k=1}^{k_r} \delta_k^r(i)w_{kj}^r $
   \end{itemize}
\item[4.] Update the weights for 
          $r=1,2, \cdots, L$ and $j = 1, 2, \cdots, k_r$
   \begin{itemize}
   \item[]$ w_{jk}^{r} \left[ \mbox{new} \right]= 
            w_{jk}^{r} \left[ \mbox{old} \right] + 
            \triangle w_{jk}^r$,
   \end{itemize}
\item[]where
   \begin{itemize}
   \item[] $\displaystyle \triangle w_{jk}^r = 
          - \epsilon \sum_{i=1}^N 
            \delta_j^r(i)y_k^{r-1}(i)$.
   \end{itemize}
\end{itemize}

\clearpage
\noindent
Rationale:\\

From the {\it gradient descent}'s principle, 
\begin{equation}
\triangle w_{jk}^r = - \epsilon \frac {\partial D}{\partial w_{jk}^r}
\end{equation}

where
\begin{equation}
D = \sum_{i=1}^N \varepsilon (i)
\end{equation}

and
\begin{eqnarray}
\varepsilon (i) &=& \frac{1}{2} 
                    \sum_{i=1}^{N} \sum_{m=1}^{k_{\small L}} e_m(i)^2 \\
                &=& \frac{1}{2} 
                    \sum_{i=1}^{N} \sum_{m=1}^{k_{\small L}} 
                                (y_m(i)- \hat{y}_m(i))^2.
\end{eqnarray}

Hence
\begin{equation}
\frac{\partial \varepsilon(i)}{\partial w_{jk}^r} = 
\frac{\partial \varepsilon(i)}{\partial h_{j}^r} 
\frac{\partial h_{j}^r}{\partial w_{jk}^r}.
\end{equation}

Here we define
\begin{equation}
\frac{\partial \varepsilon(i)}{\partial h_{j}^r} \equiv \delta_j^r(i).
\end{equation}

Then
\begin{equation}
\triangle w_{jk}^r = - \epsilon \sum_{i=1}^r(i) \delta_j^r(i) y_k^{r-1}(i).
\end{equation}

\clearpage
\noindent
$\Box$ {\bf Genetic Algorithm (GA)}\\

\noindent
An example:
\begin{itemize}
\item Neural network with 100 input neurons and 10 output neurons 
      with no hidden layer:
   \begin{itemize}
   \item hand-written-characters of the figures from zero to nine
           drawn on the 10x10 pixels are to be recognized 
   \item by activating only the $i$-th neuron of the output
         remaining other neurons not activated.\\
   \end{itemize}
\end{itemize}

\hspace*{1in}\\
\noindent
From a biological analogy, the followings are defined.
\begin{description}
\item {\it Chromosome:}\\ 
      Each chromosome is comprised of 1000 {\it genes},
      representing 1000 weights of one {\it individual} neural network.
\item {\it Population:}\\
      A number of individuals, say 100, create a population.
\item {\it Initialization:}\\
      All genes of all chromosomes are initialized at random, taking a value
      ranging from zero to one. This construct the first {\it generation}.
\end{description}
\clearpage
\hfill (cont'd)
\begin{description}
\item {\it Fitness:}\\
      The ability of each individual is evaluated and assigned
      its fitness value. In our current problem, for example, 
      each individual given a set of weights is evaluated by giving
      each output neuron 0.1 if the output is correct and 0 otherwise.
      Note that in the first generation, every individual performs 
      rather badly but diferrently, since weights are determined at random.
\item {\it Selection:}\\
      Two parents are selected to produce one offspring. 
      Individuals of better performance should be more likely to be
      selected. For example, (1) selection is always from upper half of 
      the population in which individuals have been sorted with an order 
      of their fitness, or (2) selection is made sot that the probability 
      is proportional to the fitness value. The production of an offspring
      is by employing the following two operations: {\it crossover} and
      {\it mutation}
\item {\it Crossover:}\\
      A same position of the two parent chromosomes are determined at
      random (each time when they are selected), and cross them over.
\item {\it Mutation:}\\
      For each gene of the offspring chromosome, produce one integer
      random number from 0 to 99. If the value is zero, then the gene
      is replaced with the other weight value also created at random each
      time.
\end{description}



\clearpage
\noindent
Algorithm:

\begin{enumerate}
\item {\it Initialization:}
  Initialize all the weight values of all the individuals in the first 
  generation at random so that it lies on  $\left[ 0, 1 \right] $.
\item {\it Evaluation:}
  Evaluate fitness of all the individuals of the population.
\item {\it Reproduction:}
  \begin{enumerate}
  \item[(1)] Select two parents from the population.
  \item[(2)] Crossover the two parents and produce one offspring.
  \item[(3)] Mutate the offspring.
  \item[(4)] Repeat (1) to (3) above until new generation of same size 
             is obtained.
  \end{enumerate}
\item Repeat 2. to 3. above until the perfect solution is obtained or 
      prespecified generations is reached.
\end{enumerate}


%-----------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf Associative Memory as a Dynamical System}\\
\begin{figure}[h]
 \begin{center}
    \epsfile{file=what-is-am.eps,width=15cm,height=10cm}
\end{center}
\end{figure}

\clearpage
\noindent
$\Box$ {\bf A category of trajectories}\\
\begin{figure}[h]
 \begin{center}
    \epsfile{file=trajectory.eps,width=15cm,height=10cm}
\end{center}
\end{figure}

\clearpage
\begin{figure}[t]
 \begin{center}
   \epsfile{file=fig-nn.eps,width=18cm,height=9cm}
 \end{center}
\end{figure}

\noindent
$\Box$ {\bf State Transition}\\

\begin{displaymath}
  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{displaymath}

\clearpage
\noindent
{\bf Example 1}\\
\begin{figure}[h]
 \begin{center}
    \epsfile{file=three-neuron-1-portrait.eps,width=13cm,height=9cm}
\end{center}
\end{figure}

\noindent
An example of state transition in the above toy example:
\begin{eqnarray}
\nonumber
s_{1}\hspace{.02in} (1) &=& sgn \hspace{.02in} \left( \hspace{.04in} 
                            w_{11} \cdot s_1(0) + w_{12} \cdot s_2(0)+ 
                            w_{13} \cdot s_3(0)
                            \hspace{.04in} \right) \\
\nonumber         
                        &=& sgn \hspace{.02in} \left( \hspace{.04in} 
                            0.14 \cdot 1 + (-0.34) \cdot 1 + (-0.52) \cdot 1
                            \hspace{.04in} \right) \\
\nonumber
                        &=& -1
\end{eqnarray}

\clearpage
\noindent
{\bf Example 2}\\
\begin{figure}[h]
 \begin{center}
    \epsfile{file=three-neuron-2-portrait.eps,width=5cm,height=5cm}
\end{center}
\end{figure}

\noindent
$\Box$ {\bf Example 3}\\
\begin{figure}[h]
 \begin{center}
    \epsfile{file=three-neuron-3-portrait.eps,width=4cm,height=6cm}
\end{center}
\end{figure}

%% ========== the Hebbian weights ==========
\clearpage
\noindent
$\Box$ {\bf Hebbian Weights}\\

\begin{displaymath}
w_{ij} = \frac{1}{N} \sum _{ \nu = 1}^{p} 
         {{ \xi }_{i}^{ \nu }{ \xi }_{j}^{ \nu }}
         \hspace{.1in}(i \ne j), \hspace{.1in} w_{ii} = 0.
\end{displaymath}

\hspace*{1in}\\
\hspace*{1in}\\

\begin{itemize}
\item In the above toy example:
\end{itemize}

\begin{displaymath}
\left(
   \begin{array}{ccc}
   0    & 0.11 & 0.11 \\
   0.11 & 0    & 0.11 \\
   0.11 & 0.11 & 0 
   \end{array}
\right)
\end{displaymath}

\hspace*{1in}\\

\begin{itemize}
\item An interpretation of Hebb's rule:
   \begin{itemize}
   \item A strong weight affects neurons at both ends to be same states.
   \end{itemize}
\end{itemize}

\begin{itemize}
\item Many other solutions of a {\it weight configuration} 
      to store a same set of patterns exist.
   \begin{itemize}
   \item Each
      \begin{itemize}
      \item can {\it recall} from
         \begin{itemize}
         \item partial information;
         \item incorrect information
         \end{itemize}
      \item but has a different
         \begin{itemize}
         \item {\it basin of attraction};
         \item {\it storage capacity}.
         \end{itemize}
      \end{itemize}
   \end{itemize}
\end{itemize}

%% ========== the Hebbian weights ==========
\clearpage
\noindent
$\Box$ {\bf The Other Topics of Associative Memory}\\

\noindent
$\bullet$ Memory of a set of Motion Pictures
\begin{equation}\label{eq:motion}
w_{ij}=\frac{1}{N}\sum_{\mu=1}^{p}\xi_i^{\mu+1}\xi_j^{\mu}.\\
\end{equation}

\hspace*{1in}\\
\noindent
$\bullet$ How to forget already stored patterns?

\begin{equation}\label{eq:forget}
w_{ij}=w_{ij}-\frac{\lambda}{N}\xi_i\xi_j.\\
\end{equation}

\begin{itemize}
\item[]e.g., repeat equation(\ref{eq:forget})
             1000 times with $\lambda=0.01$. 
\end{itemize}

\hspace*{1in}\\
\noindent
$\bullet$ Storage capacity (How many patterns can be stored?)

\begin{itemize}
\item[$\cdot$] Under Hebb's rule 
\begin{equation}
p/N < 0.138
\end{equation}
\item[$\cdot$] E.\ Gardner asserts (1988).
\begin{equation}
p/N<2
\end{equation}
\end{itemize}

\clearpage
\indent
In order to obtain $p/N \approx 2$:
\begin{itemize}
\item[$\cdot$] $\xi_i^\mu$ and $\sum_j w_{ij}\xi_j^\mu$ should be 
               a same sign for all $\mu$ = $ 1, \cdots, p$ 
\item[]        (then all stored memories are stable.) 
\item[$\cdot$] So, 
\begin{equation}
\xi_i^\mu \cdot \sum_j w_{ij}\xi_j^\mu  >0.
\end{equation}
\item[]        or more preferably 
\begin{equation}
\xi_i^\mu \cdot \sum_j w_{ij}\xi_j^\mu  > (\kappa >0).
\end{equation}
\item[]        (the bigger $\kappa$, the more stable)
\item[]
\item[$\cdot$] Algorithm for obtaining $p/N \approx 2$:
   \begin{itemize}
   \item[] IF $\sum_j w_{ij}\xi_j^\mu  \ne 1$ for $\forall \mu$
           \hspace{.2in} $(\kappa=1)$
   \item[] THEN $w_{ij}= w_{ij} + \delta w_{ij}$
   \end{itemize}
\item[]         where
\begin{equation}
\delta w_{ij}= \frac{1}{N}\xi_i^\mu\xi_j^\mu(1-\delta_{ij})
             \cdot \theta(\kappa - \gamma_i^\mu)
\end{equation}
\begin{equation}
\gamma_i^\mu=\frac
{\sum_j w_{ij}\xi_i^\mu \xi_j^\mu}
{\sum_j (w_{ij})^2}
\end{equation}
\end{itemize}

\clearpage
\noindent
$\bullet$ How can we observe phenomena?

\begin{itemize}
\item[1)] By displaying $S_i(t)$ at every update time $t=n\triangle t$
               \hspace{.2in}($n=1,2,\cdots$) on a PC screen.
\item[2)] By plotting Hamming distances from initial input.
\item[3)] By plotting a similarity measure of $S_i(t)$ to the
               initial input.
\begin{equation}
m^\mu(t)=\frac{1}{N}\sum_{i=1}^{N}\xi_i^{\mu}S_i^{\mu}(t).\\
\end{equation}
\end{itemize}

\hspace*{1in}\\
\noindent
Try each of the above three methods
   \begin{itemize}
   \item[$\cdot$] Fixed Points
      \begin{itemize}
      \item[] starting with one of stored patterns 
              that is given some noises (1);
      \end{itemize}
   \item[$\cdot$] Convergence to Stored Pattern
      \begin{itemize}
      \item[] starting with non-noisy one of stored patterns (1)-(3);
      \end{itemize}
   \item[$\cdot$] Chaotic Trajectory
      \begin{itemize}
      \item[] starting with random initial state 
              under symmetric random weights (2) or (3);
      \end{itemize}
   \item[$\cdot$] Trajectory to Spingrass Atractor
      \begin{itemize}
      \item[] same as above but under asymmetric random weights 
             (2) or (3);
      \end{itemize}
   \item[$\cdot$] Motion Picture
      \begin{itemize}
      \item observing equation (ref{eq:motion}) (2) or (3).
      \end{itemize}
   \end{itemize}


\noindent
$\bullet$ How appropriate a configuraition of weights is?
\begin{equation}
f=\sum_{\mu=1}^{p}\sum_{t=1}^{t_0}m^\mu(t)
\end{equation}


\clearpage
\noindent
$\Box$ {\bf Home work}\\

\begin{itemize}
\item Using fully connected neural networks
   \begin{itemize}
   \item with 200 neuronsl;
   \item with $p$ random\footnote{To produce integer random number, e.g.,\\
my\_random\_number(int n)\\
\{ \\
r1=(double)rand(); \\
r2=(double)n;\\
r=(int)((r1/RAD\_MAX)*r2);\\
return(r);\\
\}
}
patterns stored by Hebb's rule;
   \item with equal probability of 1 and --1 in patterns.\footnote{We
use random binary patterns, but reproducibility of these random
patterns is preferable. So, for example:\\
\# define SEED\\
$\cdots$\\
randomize()\\
\{ srand(SEED); \} \\
$\cdots$\\
main()\\
\{ \\
$\cdots$ \\
randomize();\\
generate\_pattenrs();\\
$\cdots$\\
\} \\
}
   \end{itemize}
\item[(1)] Study capcity dependency on the number of patterns stored.
   \begin{itemize}
   \item[e.g.,] $f$ (y-axis) vs. $p$ (x-axis)
   \end{itemize}
\item[(2)] Study size of basin of attraction's dependency 
           on the number of patterns stored.
   \begin{itemize}
   \item[e.g.,] $f$ (y-axis) vs. \#-of-noises (x-axis) 
                 with parameter $p$.
   \end{itemize}
\end{itemize}


%========== Chapter ==========
\clearpage
\begin{Huge}
\hspace*{1in}\\
\hspace*{1in}\\
\hspace*{1in}\\
\noindent
Chapter 3 \\
\hspace*{1in}\\
\noindent
Solving Combinatorial Problem \\

\hspace*{3in}by Neural Networks
\end{Huge}


\clearpage
\noindent
$\Box$ {\bf Solving Combinatorial Problem}\\

\begin{itemize}
\item The fully connected neural network model so far 
      we've studied can also solve combinatorial problems.
\item[]e.g.
   \begin{itemize}
   \item[(1)] Multiflop problem:
      \begin{itemize}
      \item Only one out of $n$ neurons is on 
            with all the others off at a moment.
      \item When all weight values are $-2$,
         \begin{itemize}
         \item a unit that is set to 1 inhibits the other units; or
         \item if the network is started with all neurons set to zero, 
               then the excitation of every neuron is zero, 
               which makes the first neuron to be asynchronously selected 
               flip its state to 1 and no other neuron can change its state 
               after this first neuron has been set to 1
         \end{itemize}
      \end{itemize}
   \item[(2)] The eight rooks problem:
      \begin{itemize}
      \item A generalization of multiflop;
      \item If the connection of each neuron to other neurons 
            in the same row or column have the weight $-2$,
            all others have a weight zero and
            all neurons have the threshold $-1$, then
         \begin{itemize}
         \item Any neuron set to 1 inhibits any other neurons in the same 
               row or column; or
         \item if a row or column is all set to 0 when one of its neuron
               is selected it will immediately switch its state to 1
         \end{itemize}
      \end{itemize}
\clearpage
   \item[(3)] The eight queens problem:
      \begin{itemize}
      \item A generalization of eight rooks problem,
      \item taking diagonal lines into consideration too.
      \item This, however,  does not always work 
            due to many {\it local minima.} surrounding the solution
      \item[] \begin{center} $\Downarrow$ \end{center}
      \item[] using stocastic (probabilistic) neurons 
      \end{itemize}
   \end{itemize}
\end{itemize}

\clearpage
\noindent
$\Box$ {\bf A new scheme.}\\

$\bullet$ Stochastic Neurons:
\begin{itemize}
\item[]Instead of using {\bf deterministic neurons} where
\begin{equation}
S_i(t+1)=sgn (\sum_j^N w_{ij}S_j(t))
\end{equation}
\item[]{\bf stochastic neurons} where
\begin{equation}
Pr(S_i(t+1))=f(\sum_j^N w_{ij}S_j(t))
\end{equation}
\item[]are employed, in which
\begin{equation}
f(x)=\frac{1}{1+\exp (-2 \frac{x}{T})}
\end{equation}
\item[] and $T$ is called {\it temperature}.\\
\end{itemize}

$\bullet$ Energy:
\begin{itemize}
\item[] A quantity called {\it energy} is defined corresponding to
        a configuration of the states of neurons as
\begin{equation}
E(t)=-\frac{1}{2} \sum_{ij}^{i \ne j} w_{ij}S_i(t)S_j(t))
\end{equation}
\item[] and network state changes so that $E(t)$ minimizes. 
\end{itemize}

\clearpage
\newtheorem{boltzman}{Definition}
\begin{boltzman}[Boltzman machine]
A Boltzman machine is a Hopfield network composed of $n$ neurons 
with states $x_1 \cdots x_n$. The state of neuron $i$ is updated 
asynchronously according to the rule
\begin{eqnarray}
x_i = \left\{
\begin{array}{lll}
1 & \mbox{with probability} \hspace{.2in} & p_i   \\
0 & \mbox{with probability} \hspace{.2in} & 1-p_i \\
\end{array}
\right.
\end{eqnarray}
where 
\begin{equation}
p_i=\frac{1}{\displaystyle 1
       + \exp \{ (- \sum_{j=1}^n w_{ij} x_j -\theta_i)/T \} }
\end{equation}
and $T$ is a positive temperature constant and $\theta_i$
is the threshold of the neurons.
Then the energy is defined as:
\begin{equation}
E=-1/2 \sum_i \sum_j w_{ij} x_i x_j + \sum_i \theta_i x_i
\end{equation}
\end{boltzman}

\begin{center} \underline{\hspace*{7in}} \\ \end{center}

\noindent
Note that if $T$ is very small $p_i \approx 1$ for 
$\displaystyle \sum_i w_{ij}x_j - \theta_i $ is positive
and $p_i \approx 0$ for negative.

\begin{itemize}
\item Examples
   \begin{itemize}
   \item the smallest hopfield network --- the flip-flop
      \begin{itemize}
      \item[] two neurons with 
              \begin{center} 
              $w_{12}=w_{21}=-1$, \hspace{.2in} $w_{11}=w_{22}=0$,
      \item[] $\theta_i = -0.5$ 
      \item[] $\Downarrow$
      \item[] $E_{00}=E_{11}=0, \hspace{.2in} E_{01}=E_{10}=-0.5$ 
              \end{center}
      \end{itemize}
\clearpage
   \item the multi-flop
\begin{eqnarray}
\nonumber
E &=& (\sum_{i=1}^n x_i -1)^2                     \\
\nonumber
  &=& \sum_{i=1}^n x_i^2 + \sum_{i \ne j} x_i x_j 
                         -2 \sum_{i=1}^n x_i + 1  \\
\nonumber
  &=& \sum_{i \ne j} x_i x_j - \sum_{i=1}^n x_i +1\\
\nonumber
  &=& \frac{1}{2} \sum_{i \ne j} (-2)x_ix_j + \sum_{i=1}^n (-1)x_i +1\\
\nonumber
\end{eqnarray}
   \item The eight rooks problem
\begin{eqnarray}
\nonumber
E_1 &=& \sum_{j}(\sum_{i} x_{ij-1})^2 \\
\nonumber
E_2 &=& \sum_{i}(\sum_{j} x_{ij-1})^2 \\
\nonumber
E   &=& E_1+E_2                         \\
\nonumber
\end{eqnarray}
   \end{itemize}
\end{itemize}



\clearpage
\begin{itemize}
\item[$\Box$] {\bf Traveler's Salesman Problem (TSP)}\footnote{We can apply
the problem to ``how we connect each device in LSI in which many, 
say $10^5$, divices are included.''}
   \begin{itemize}
   \item[--] as an NP-complete\footnote{Nondeterministic polynomial}
              combinatorial problem
      \begin{itemize}
      \item A salesman should visit every city once but only once
            such that his traveling route is the shortest\footnote{With
            N cities, the number of all the possible route is 
               \begin{equation}
               (N-1)!=\sqrt{2\pi N} \exp(N\ln N - N)
               \end{equation}
               i.e., {\it not deterministic in polynomial time}.}.
      \end{itemize}
   \end{itemize}
\item[]
\item Representation of a rout by a $N \times N$ matrix
   \begin{itemize}
   \item[$\star$] The rout 1-3-6-4-5-2 of 6-city TSP is represented as
\begin{equation}
\left(
   \begin{array}{cccccc}
   1 & 0 & 0 & 0 & 0 & 0 \\
   0 & 0 & 0 & 0 & 0 & 1 \\
   0 & 1 & 0 & 0 & 0 & 0 \\
   0 & 0 & 0 & 1 & 0 & 0 \\
   0 & 0 & 0 & 0 & 1 & 0 \\
   0 & 0 & 1 & 0 & 0 & 0 
   \end{array}
\right)
\end{equation}
   \item[]where ``$i\alpha$-element is one'' means that the $i$-th city
   is in the $\alpha$-th location in the tour.\\
   \end{itemize}
\item Implementation by a fully connected neural network with $N$ neurons.
   \begin{itemize}
   \item $S_{i \alpha}(t)$ corresponds to the $i\alpha$-element 
         of the matrix.
   \item Starting with a random configuration of the network state,
         it is expected to converge to the matrix corresponding to the 
         shortest route.
   \end{itemize}
\end{itemize}

\clearpage
\noindent
Then the energy of our neural network is
\begin{equation}
E=-\frac{1}{2}\sum_{i,k}^{i \ne k}\sum_{\alpha,\beta}^{\alpha \ne \beta}
w_{i\alpha ,k\beta}S_{i\alpha} S_{k\beta} \\
\end{equation}

\hspace*{1in}\\
\noindent
This can be expanded with appropriate $A$, $B$, and $C$ as
\begin{eqnarray}
\nonumber
E=&-&\frac{1}{2}\sum_{i,k,\alpha}^{i \ne k} d_{ik}S_{i\alpha}
     (S_{k(\alpha-1)} + S_{k(\alpha+1)})\\
\nonumber
&-&\frac{A}{2}\sum_{i,\alpha, \beta}^{\alpha \ne \beta} 
     S_{i\alpha}S_{i\beta}
 -\frac{B}{2}\sum_{i,k,\alpha,}^{i \ne k} 
     S_{i\alpha}S_{k\alpha}\\
&-&\frac{C}{2}\sum_{i,\alpha}(S_{i\alpha}S_N)^2\\
\end{eqnarray}
\begin{itemize}
\item[] Then
   \begin{itemize}
   \item[$\star$] 1st term means total length of the tour;
   \item[$\star$] 2nd term vanishes 
                  iff the raw includes only one ``1'';
   \item[$\star$] 3rd term vanishes 
                  iff the column includes only one ``1'';
   \item[$\star$] 4th term takes its minimum 
                  when exactly $N$ neurons are active.
   \end{itemize}
\end{itemize}

\clearpage
\noindent
$\Box$ {\bf Simmulated Annealing.}\\

\noindent
Annealing is a term from {\it materials science} which describes
the process of {\it eliminating lattice difects in crystals} by 
{\it heating} a crystal to more than melting point and then 
{\it slowly cooling} it to room temperature. \\

\noindent
If it is cooled too rapidly from the molten phase, some atoms are
often captured an energetically infavarable locations in the lattice.\\

\noindent
Hence, the thermal equilibrium distribution should be maintained at 
all times during the cooling process.\\

\begin{itemize}
\item Metropolis Algorithm
   \begin{itemize}
   \item Cost function (Objective function) $E$ that we want to minimize
         is to be modified step by step as follows:\\
      \begin{itemize}
      \item[1.] Start with randomly determined $E$.\\
      \item[2.] {\bf IF} $\triangle E 
                = E^{\mbox {\small old}} -E^{\mbox {\small new}} < 0 $,
                then accept the modification. 
                {\bf ELSE IF} accept it with the
                probability $\exp (- \triangle E /T)$, otherwise
                retain the $E^{\mbox \small old}$.\\
      \item[3.] Repeat step 2.
      \end{itemize}
   \end{itemize}
\clearpage
\item Traveling Salesman's Problem\\
   \begin{itemize}
   \item $E$ is set to the total length of a tour.\\
   \item Then how we modify $E$?
      \begin{itemize}
      \item Lin-Kernighan's two procedures:
         \begin{itemize}
         \item {\it Transport:} A segment of the tour is removed from its 
               old position and  insert it at a new position.
         \item {\it Reversal:} A segment of the tour is selected and the 
               order of cities in this segment is reversed.\\
         \end{itemize}
      \end{itemize}
   \item Run, for example, under the conditions:
      \begin{itemize}
      \item[1.] Start with the temperature $T=LN^{-3/2}$ wher $L$ is the
            length of a initial tour.
      \item[2.] At a temperature, repeat either of two modifications with
                equal probability, until
         \begin{itemize}
         \item $100N$ modifications, or
         \item $10N$ modifications are accepted 
         \end{itemize}
      \item[3.] Reduce $T$ by 5\% and repeat Step 2.
      \end{itemize}
   \end{itemize}
\end{itemize}



\end{LARGE}
\end{document}
