\documentstyle[12pt,eclepsf]{article}

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

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

\begin{document}
\begin{large}

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

\vspace{1in}
Dokuz Eyl\"{u}l University \\
Computer Engineering Department \\
\hspace*{1in}\\
\begin{large}
24 October 2001 -- \\
\end{large}
\end{center}

%---------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf What is Neural Network?}
\begin{itemize}
\item A system with {\it neurons} connected with {\it synapses},
\item[]where
   \begin{itemize}
   \item each synapse: 
      \begin{itemize}
      \item is given a value called {\it weight};
      \item transmits value with being multiplied by its weight,
      \end{itemize}
   \item each neuron: 
      \begin{itemize}
      \item is given a function called {\it transfer function};
      \item takes multiple (fan-in) inputs, caluculates their weighted 
              sum and outputs its function value.
      \end{itemize}
   \end{itemize}
\item[]that is,
\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=neuron-synapse.eps,width=8cm,height=5cm}
 \end{center}
\end{figure}
\begin{equation}
y = f(\sum_{i=0}^{n}w_{i}\cdot x_{i}).
\end{equation}

\clearpage
\item Typically categorized into two forms:
   \begin{itemize}
   \item[1.] Layered (feed forward);
   \item[2.] Fully-connected\\
   \end{itemize}
\item[] For example:
\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=nn-1.eps,width=12cm,height=6cm}
 \end{center}
\end{figure}
\end{itemize}

\hspace*{1in}\\
\hspace*{1in}\\
\noindent
$\Box$ {\bf Neural Networks What for?}
\begin{itemize}
\item To model human brain;
\item To make computers try things that we are good at 
but they are not. \footnote{Terrence J. Sejnowski said in his foreword
for the book ``Face Image Analysis by Unsupervised Learning'' 
by Marian Stewart Bartlett. Kluwer Academic Publishers (2001) that
{\it Computers are good at many things that we are not good at, like 
sorting a long list of numbers and calculating the trajectory of a 
rocket, but they are not at all good at things that we do easily and 
without much thought, like seeing and hearing.}}
\end{itemize}

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

\newtheorem{excersise}{Excersise\\}
\begin{excersise}
Specify three parameters $w_1$, $w_2$ and $a$ so that a neural network
with two inputs and one output can caluculate the following 
three operations.\\
\hspace*{.5in}1. AND\\
\hspace*{.5in}2. OR\\
\hspace*{.5in}3. XOR
\end{excersise}
\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=and-or.eps,width=12cm,height=7.5cm}
 \end{center}
\end{figure}
\begin{large}
\begin{center}
Did you notice that XOR cannot be rearized with this framework?\\
\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}\\
Then try it by adding one additional layer.
\end{center}
\end{large}

\hspace*{1in}\\
\begin{excersise}
Why do you think XOR cannot be realized in this way?
Plot the four points and try to separate them with a line
\begin{displaymath}
w_1x_1+ w_2x_2 =a.
\end{displaymath}
\end{excersise}

%---------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf Perceptron}
\begin{itemize}
\item A two-layered neural network.
\item[] 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 from the $j$-th input neuron 
            to the $i$-th output neuron is $w_{ij}$;\\
      \end{itemize}
\item[]then\\
\begin{equation}
y_i = f(\sum_{j=1}^{M} w_{ij}x_j),
\end{equation}
\item[] where, typically,\\
\begin{equation}
f(x) = \mbox{sgn} (x - a).
\end{equation}
\end{itemize}

\hspace*{1in}\\
\hspace*{1in}\\
\begin{excersise}
Implement a perceptron which has arbitrary number of inputs and 
outputs, with randomly chosen weight values and with transfer function of 
all neurons being $sgn(\cdot)$ such that the perceptron reads $p$ input data
and outputs $p$~results of the caluculation.
\end{excersise}

%---------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf Perceptron Learning}\\
\hspace*{2in} --- How can we determine weights?\\

\begin{itemize}
\item Assume $M$ input and $N$ output neurons.\\
\end{itemize}

\begin{itemize}
\item Also assume that we have $p$ examples 
\end{itemize}
\begin{equation}
x_{j}^{\mu} \hspace{.2in} (\mu = 1, 2, \cdots, p, 
\hspace{.2in} j = 1,2, \cdots, M) 
\end{equation}
\begin{itemize}
\item[]whose desired output are given, i.e.,
\end{itemize}
\begin{equation}
z_{i}^{\mu} \hspace{.1in} (i = 1,2, \cdots, N),\\
\end{equation}
\begin{itemize}
\item[] while real outputs are
\end{itemize}
\begin{equation}
y_{i}^{\mu} \hspace{.2in} (i = 1,2, \cdots, N).
\end{equation}

\hspace*{1in}\\
\begin{itemize}
\item Then we modify $w_{ij}$ by adding:
\end{itemize}
\begin{equation}
\delta w_{ij} = \epsilon (z_i^{\mu} - y_i^{\mu})\cdot x_j^{\mu},
\end{equation}
\begin{itemize}
\item[] in each iteration of giving example, and we obtain
\end{itemize}
\begin{equation}
w_{ij}^{\mbox{\small{new}}} = w_{ij}^{\mbox{\small{old}}} + \delta w_{ij}
\end{equation}
\begin{itemize}
\item[] (implying {\it if correct do nothing, otherwise modify.)}
\end{itemize}
\hspace*{1in}\\
\begin{itemize}
\item Note that 
each of $x_k^{\mu}, \hspace{.1in} y_k^{\mu}, \hspace{.1in} and  
\hspace{.1in} z_k^{\mu}$ takes either 1 or $-1$.
\end{itemize}

%---------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf How to determine threshold?}\\
\hspace*{3in} also automatically.\\

\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=threshold.eps,width=10cm,height=6cm}
 \end{center}
\end{figure}
\begin{itemize}
\item[]In both cases, we can obtain same output $y$, that is,
\begin{displaymath}
y = \mbox{sgn} (w_1 \cdot x_1 + w_1 \cdot x_1 - a).
\end{displaymath}
\item[]So, we can also specify $a$ as one of weights.
\end{itemize}

\vspace{1in}

\begin{excersise}
Explore Perceptron Learning in the following two ways.
\begin{itemize}
\item[1.] Obtain two weights and threshold value to solve
                 two inputs and one output perceptron by a manual 
                 calculation.
\item[2.] Assume you have 100 points each from 2 different 
                 categories of regions in the 2-dimensional x-y coordinate.
                 Design a neural network which classifies a given point 
                 to either of this two categories.
\end{itemize}
\end{excersise}

\clearpage
\noindent
$\Box${\bf Analog Neurons}

\begin{itemize}
\item accept analog inputs and output analog values; 
\item with its transfer function usually being: \footnote{\noindent From 
the definitions:
\begin{equation}
e^{jx} = \cos x + j \sin x;
\end{equation}
\begin{equation}
e^{-jx} = \cos x - j \sin x,
\end{equation}
\noindent
we obtain
\begin{equation}
\cos x = \frac { e^{jx} + e^{-jx}} {2}; 
\end{equation}
\begin{equation}
\sin x = \frac { e^{jx} - e^{-jx}} {2j}; 
\end{equation}
We extend them to
\begin{equation}
\cosh x = \frac { e^{x} + e^{-x}} {2}; 
\end{equation}
\begin{equation}
\sinh x = \frac { e^{x} - e^{-x}} {2}; 
\end{equation}
So,
\begin{equation}
\tanh x = \frac {e^{x} - e^{-x}} {e^{x} + e^{-x}} 
        = \frac {1 - e^{-2x}} {1 + e^{-2x}} 
\end{equation}
}
\begin{equation}
f(X) = \tanh (\beta X) 
\end{equation}
\end{itemize}

%%\hspace*{1in}\\
\begin{excersise} Answer the following questions.
\begin{itemize}
\item[(1)] Draw the graph of the function:
\begin{displaymath}
y = tanh(\beta x)
\end{displaymath}
with three diferent value
of $\beta = 0.1, \hspace{.1in} 1$ and $10$. 
\item[(2)] When $f(x) = \tanh(\beta x)$ verify the relation
\begin{displaymath}
f^{\prime}(x) = \beta \{1 - f^2(x)\}
\end{displaymath}
and think what it means both in the case when $x$ is large enough and $x=0$.
\end{itemize}
\end{excersise}

\clearpage
\noindent
$\bullet \hspace*{.1in} y=\tanh (\beta x)$
\begin{figure}[h]
 \begin{center}
   \epsfile{file=tanh.eps,width=12cm,height=10cm}
 \end{center}
\end{figure}


\clearpage
\noindent
$\Box$ {\bf Gradient Learning}\\
\hspace*{1in}--- Learning for analog neurons.\\

\begin{itemize}
\item Assume that we have $M$ inputs $N$ outputs, and $p$ examples. \\
\item All neurons are analog.\\
\item {\it Total Squared Error} of outputs is difened as:
\begin{equation}\label{eq:error}
D = \sum_{\mu =1}^{p} \sum_{i=1}^{N} (y_i^{\mu} - z_i^{\mu})^2
\end{equation}
\noindent
where
\begin{equation}
y_i^{\mu} = f (\sum_k w_{ik}x_k^{\mu}) \\
\end{equation}
\item[]and usually
\begin{equation}
f(h) = \tanh (\beta h). \\
\end{equation}
\hspace*{1in}\\
\item The Equation (\ref{eq:error})
      defines an {\it error surface} of high dimensionality.\\
\hspace*{1in}\\
\item Then, the {\it gradient} of $D$ with respect to 
$w_{ij}$ modifies $w_{ij}$ as:\footnote{Though there exist many alternatives 
to find minima of a non-linear function $g(\mbox{\bf x})$, 
{\it steepest descent}
\begin{equation}
\mbox{\bf x}_{n+1} = \mbox{\bf x}_n - \epsilon \nabla g(\mbox{\bf x}_n)
\end{equation}
is sufficient in most cases.}\\
\begin{equation}
\delta w_{ik} \equiv - \epsilon \frac{\partial D}{\partial w_{ik}}
= \cdots 
= \epsilon \sum_{\mu} ({\zeta}_i^{\mu} - S_i^{\mu}) f^{\prime} 
  ( \sum_k w_{ik} {\sigma}_k^{\mu}),\\
\end{equation}
\hspace*{1in}\\
\noindent
\item[]where\\
\begin{equation}
f^{\prime}(x) = \beta \{ 1 - f(x)^2 \}. 
\end{equation}
\end{itemize}

\clearpage
\noindent
$\bullet$ A toy example:

\begin{excersise}
Assuming a training set ($p=8$) bellow, answer the following questions.
\begin{table}[hbtp]
\begin{center}
\begin{tabular}{c c c c c} \hline \hline
$\mu$ & $x_1$ & $x_2$ & $z_1$ \\ \hline
1     &  3.2  & -2.4  & 0.8 \\
2     & -4.8  & -3.5  & 0.6 \\
3     & -2.7  &  3.5  & 0.4 \\
4     &  5.3  &  3.5  & 0.2 \\
5     & -1.9  &  3.5  & 0.4 \\
6     &  6.2  & -3.5  & 0.8 \\
7     &  7.6  &  3.5  & 0.2 \\
8     & -3.3  & -3.5  & 0.6 \\ \hline \hline
\end{tabular} 
\end{center}
\end{table}
\begin{itemize}
\item[(1)] What kind of task do you imagine with the training set.
\item[(2)] Guess the output 
           when {\bf x} $= (6.8, -7.4)$ is given as an input.
\item[(3)] Train a neural network with $M=2$ and $N=1$ using Gradient
           Learning.
\end{itemize}
\end{excersise}

%---------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf Multi-layered Neural Networks}
\begin{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 a hyper-plane.\\
   \end{itemize}
\item 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 $M$ input neurons ($k_1 = M$) and $N$ output neurons ($k_L = N$).
   \item $w_{ij}^r$: weight from the $j$-$th$ neuron in the $r$-$th$ layer 
                     to the $i$-$th$ neuron in the $r$-$th$ layer.
   \item $p$ training pairs: $(\mbox{\bf x}(\mu),\mbox{\bf z}(\mu))$, 
         \hspace{.2in} $i = 1, 2, \cdots, p$.
   \item $y_i^{r}(\mu)$: the output of the $i$-$th$ neuron in the $r$-$th$
                        layer when the $\mu$-$th$ training sample is given.
   \item fan-in's to $j$-$th$ neuron in the $r$-$th$
                        layer when the $\mu$-$th$ training sample is given.
\begin{equation}\label{eq:fan-in}
\displaystyle 
              h_j^r(\mu) \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{equation}
   \item[] where
\begin{displaymath}
y_0^{r-1} = 1
\end{displaymath}
      \item[] and 
\begin{displaymath}
(y_1^1(\mu), \cdots,  y_M^1(\mu)) = 
               (x_1(\mu),   \cdots,    x_M(\mu)) = \mbox{\bf x}(\mu).
\end{displaymath}
   \item Each output neuron's error:
\begin{equation}\label{eq:error}
e_i(\mu) \equiv y_i(\mu)- z_i(\mu), \hspace{.1in}
i = 1,2, \cdots, N.
\end{equation}
   \item[] where $(z_1(\mu), \cdots, z_N(\mu)) 
                   = \mbox{\bf z}(\mu)$
   \item Error function to be minimized:
\begin{equation}\label{eq:error-function}
\displaystyle D= 
              \frac{1}{2} \sum_{\mu=1}^{p} \sum_{i=1}^{N} e_i(\mu)^2
\end{equation}
   \end{itemize}
\end{itemize}

\clearpage
\noindent
$\bullet$ An example of the notations \\
\begin{itemize}
\item[-] $L=3$,\hspace{.1in} $M=k_1 = 4$, \hspace{.1in} $N = k_3 = 3$ 
\hspace{.1in} and \hspace{.1in}$k_2 = 2$.
\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=backprop.eps,width=12cm,height=10cm}
 \end{center}
\end{figure}
\item[-] e.g.
   \begin{itemize}
   \item[$\star$]
           $h_2^2(\mu) = w_{21}^1 \cdot x_1(\mu) + w_{22}^1 \cdot x_2(\mu)
                       + w_{23}^3 \cdot x_3(\mu) + w_{24}^1 \cdot x_4(\mu).$
   \item[$\star$]
           $h_2^3(\mu) = w_{21}^2 \cdot y_1^2(\mu) 
                       + w_{22}^2 \cdot y_2^2(\mu).$
   \end{itemize}
\end{itemize}

%---------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf Back Propagation}\\
\hspace*{1in} --- Learning for multi-layered analog neural networks.\\

\noindent
$\bullet$ The algorithm:
\begin{itemize}
\item[1.] {\it Initialization:} 
   \begin{itemize}
   \item[$\cdot$]Initialize all the weights with small random values.
   \end{itemize}
\item[2.] {\it Forward computations:} 
   \begin{itemize}
   \item[$\cdot$] For each of the training vectors
      \begin{displaymath}
   \mbox{\bf x}(i), \hspace{.2in} \mu = 1, 2, \cdots, p
   \end{displaymath}
   \item[] compute all the 
\begin{equation}\label{eq:local-output}
y_j^r(\mu) = f (h_j^r(\mu))
\end{equation}
\item[] for \hspace{.1in}$j = 1, 2, \cdots, k_r $ 
\hspace{.1in} and \hspace{.1in}$ r = 1, 2, \cdots, L$.
   \end{itemize}
\item[3.] {\it Backward computations:} 
   \begin{itemize}
   \item[$\cdot$] For each \hspace{.1in} $\mu = 1, 2, \cdots, p$
          \hspace{.1in} and \hspace{.1in} $j = 1, 2, \cdots, N$ 
          \hspace{.1in} compute
\begin{equation}\label{eq:delta}
\delta_j^L(\mu) = e_j(\mu)f^{\prime}(h_j^L(\mu)).
\end{equation}
   \item[$\cdot$] Then compute
\begin{equation}\label{eq:next-delta}
\delta_j^{r-1}(\mu) = e_j^{r-1}(\mu)f^{\prime}(h_j^{r-1}(\mu))
\end{equation}
   \item[]for \hspace{.1in} $ r = L, L-1, \cdots ,2$ \hspace{.1in} and 
\hspace{.1in} $j = 1, 2, \cdots, k_r$ \hspace{.1in} where
\begin{equation}\label{eq:error-propagated}
\displaystyle e_j^{r-1}(\mu) = 
             \sum_{k=1}^{k_r} \delta_k^r(\mu)w_{kj}^{r}.
\end{equation}
   \end{itemize}
\item[4.] Update the weights for \hspace{.1in} $r=1,2, \cdots, L$ 
\hspace{.1in} and \hspace{.1in} $j = 1, 2, \cdots, k_r$
\begin{equation}\label{eq:modify-weights}
w_{jk}^{r} \left[ \mbox{new} \right]= 
            w_{jk}^{r} \left[ \mbox{old} \right] + 
            \triangle w_{jk}^r
\end{equation}
\item[]where
\begin{equation}\label{eq:resulted-weights}
\displaystyle \triangle w_{jk}^r = 
          - \epsilon 
            \delta_j^r(\mu)y_k^{r}(\mu).
\end{equation}
\item[] until no change occurs during the training cycle of 
\hspace{.1in}$\mu = 1,2, \cdots, p$.
\end{itemize}

\clearpage
\begin{center}
($\star$ Forward calculation in our previous toy example: 
From the bottom to top.) \\
\hspace*{1in}\\
\begin{small}
\hspace{.1in}\\
$y_1^1(\mu) = x_1(\mu)$, \hspace{.1in} $y_2^1(\mu) = x_2(\mu)$, 
\hspace{.1in}
$y_3^1(\mu) = x_3(\mu)$, \hspace{.1in} $y_4^1(\mu) = x_4(\mu)$.\\
\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}\\
$h_1^2(\mu)=w_{11}^1\cdot y_1^1+w_{12}^1\cdot y_2^1+w_{13}^1\cdot y_3^1
           +w_{14}^1\cdot y_4^1$ 
\hspace{.2in} from (\ref{eq:fan-in})\\
\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}\\
similarly $h_2^2(\mu)$.\\
\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}\\
$y_1^2 = f(h_1^2(\mu))$
\hspace{.2in} from (\ref{eq:local-output})\\
\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}\\
similarly $y_2^2(\mu)$. \\
\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}\\
$h_1^3(\mu) = w_{11}^2 \cdot y_1^2 + w_{12}^2 \cdot y_2^2$
\hspace{.2in} from (\ref{eq:fan-in}) again\\
\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}\\
similarly $h_2^3(\mu)$ \hspace{.2in}and\hspace{.2in} $h_3^3(\mu)$.\\
\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}\\
$y_1^3 = f(h_1^3(\mu))$
\hspace{.2in} from (\ref{eq:local-output}) again \\
\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}\\
similarly $y_2^3(\mu)$ \hspace{.2in}and\hspace{.2in} $y_3^3(\mu)$.\\
\end{small}
\clearpage
($\star$ Backward calculation in our previous toy example:
From the top to bottom.)\\
\hspace*{1in}\\
\begin{small}
\hspace*{1in}\\
$e_1^{(3)} = y_1^3 - z_1(\mu)$
\hspace{.2in} from (\ref{eq:error})\\
\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}\\
similarly $e_2^{(3)}(\mu)$ \hspace{.2in}and\hspace{.2in} $e_3^{(3)}(\mu)$. \\
\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}\\
$\delta_1^3(\mu) = e_1^{(3)} \cdot f^{\prime} (h_1^3(\mu))$
\hspace{.2in} from (\ref{eq:delta})\\
\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}\\
similarly $\delta_2^3(\mu)$  \hspace{.2in}and\hspace{.2in} 
$\delta_3^3(\mu)$.\\
\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}\\
$e_1^2({\mu}) = \delta _1^3 (\mu) \cdot w_{11}^2
              + \delta _2^3 (\mu) \cdot w_{21}^2
              + \delta _3^3 (\mu) \cdot w_{31}^2$ \\
\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}\\ 
similarly $e_2^2({\mu})$\hspace{.2in} from (\ref{eq:error-propagated}).\
\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}\\
$\delta_1^2(\mu) = e_1^2 (\mu) \cdot f^{\prime} (h_1^2(\mu))$
\hspace{.2in} from (\ref{eq:next-delta})\\
\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}\\
similarly $\delta_2^2(\mu)$.\\
\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}\\
$e_1^1({\mu}) = \delta _1^2 (\mu) \cdot w_{11}^1
              + \delta _2^2 (\mu) \cdot w_{21}^1$ \\
$e_2^1({\mu}) = \delta _1^2 (\mu) \cdot w_{12}^1
              + \delta _2^2 (\mu) \cdot w_{22}^1$ \\
$e_3^1({\mu}) = \delta _1^2 (\mu) \cdot w_{13}^1
              + \delta _2^2 (\mu) \cdot w_{23}^1$ \\
$e_4^1({\mu}) = \delta _1^2 (\mu) \cdot w_{14}^1
              + \delta _2^2 (\mu) \cdot w_{24}^1$ \\
\hspace{.2in} from (\ref{eq:error-propagated}) again\\
\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}\\
$\delta_1^1(\mu) = e_1^1 (\mu) \cdot f^{\prime} (h_1^1(\mu))$
\hspace{.2in} from (\ref{eq:next-delta}) again\\
\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}\\
similarly $\delta_2^1(\mu)$, \hspace{.1in}$\delta_3^1(\mu)$, \hspace{.1in}
$\delta_4^1(\mu)$. \\
\end{small}
\end{center}

%---------------------------------------------------------------------
\clearpage
\noindent
$\bullet$ Rationale\\

\noindent
$\star$ Thought Experiment: 1-D weight
\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=function.eps,width=18cm,height=12cm}
 \end{center}
\end{figure}

\noindent
Modification:
\begin{equation}
w^{\mbox{\small{new}}} = w^{\mbox{\small{old}}} + \triangle w
\end{equation}
where
\begin{equation}
\triangle w = - \epsilon \cdot 
                    \frac{dD}{dw} \vert _{w = w^{\mbox{\tiny{old}}}}
\end{equation}

\noindent
means that starting from $w_0$, $w$ gradually approaches the point 
where $D$ takes a minimum value with $\delta w$ being decreased. 

\clearpage
\noindent
$\star$ An example: XOR (revisited)\\

\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=xor.eps,width=6cm,height=12cm}
 \end{center}
\end{figure}

\noindent
In this example, 
\begin{eqnarray}
\nonumber
D  &=& \frac{1}{2} \{{e_1^{(3)}}\}^2 \\
\nonumber
   &=& \frac{1}{2} \{ y_i^{(3)} - z_i\}^2\\
\nonumber
   &=& \frac{1}{2} \{(f(h^3_i) - z_i\}^2\\
\nonumber
   &=& \frac{1}{2}\{ f (w^2_{11}\cdot y^2_1 + w^2_{12}\cdot y^2_2)
                             -z_i\}^2 \\
\nonumber
   &=& \frac{1}{2}\{ f (w^2_{11}\cdot f(h^2_1) + w^2_{12}\cdot f(h^2_2)
                             -z_i\}^2 \\
\nonumber
   &=& \frac{1}{2}\{ f (w^2_{11} \cdot 
                         f(w^1_{11}\cdot y^1_1 + w^1_{12}\cdot y^1_2) 
                      + w^2_{12}\cdot 
                         f(w^1_{21}\cdot y^1_1 + w^1_{22}\cdot y^1_2)
                             -z_i\}^2 \\
\nonumber
   &=& \frac{1}{2}\{ f (w^2_{11} \cdot 
                         f(w^1_{11}\cdot x_1 + w^1_{12}\cdot x_2) 
                      + w^2_{12}\cdot 
                         f(w^1_{21}\cdot x_1 + w^1_{22}\cdot x_2)
                             -z_i\}^2 \\
\nonumber
\end{eqnarray}
You can see that $D$ is a function of only all the weights
(6-D in this case).

\clearpage
\noindent
$\star$ Is $D$  a function of all the weights?

\begin{itemize}
\item[]We have studied that
\begin{eqnarray}
D  &=& \frac{1}{2} \sum_{i=1}^{N} {e_i}^2 \\
   &=& \frac{1}{2} \sum_{i=1}^{N} (y_i - z_i)^2\\
   &=& \frac{1}{2} \sum_{i=1}^{N} (f(h^L_i) - z_i)^2
\end{eqnarray}
\item[]with
\begin{equation}\label{eq:one}
h^{r+1}_i = \sum_{j=1}^{k_r} w_{ij}^r \cdot y_j^r
\end{equation}
\item[]and
\begin{equation}
y^{r}_j = f(h^r_j).
\end{equation}
\item[]Hence we can conclude that $D$ is a function of all the $w_{ij}^r$ as
in the example of {\it XOR} shown in the previous page.
\item[]
\item[]In order to obtain $\triangle w_{ij}^r$, we calculate
\begin{equation}
\frac{\partial D}{\partial w_{ij}^r} = 
\frac{\partial D}{\partial h_i^{r+1}} \cdot
\frac{\partial h_i^{r+1}}{\partial w_{ij}^r}
\end{equation}
\item[]where we know from (\ref{eq:one})
\begin{equation}
\frac{\partial h_i^{r+1}}{\partial w_{ij}^r} = y^r_j
\end{equation}
What is to be done here is to put
\begin{equation}
\delta ^{r+1}_i \equiv \frac{\partial D}{\partial h_i^{r+1}}
\end{equation}

\end{itemize}

\clearpage
\noindent
$\star$ Where are the definitions of $\delta^{r-1}_j$ and $e^{r-1}_j$
in (\ref{eq:next-delta}) and (\ref{eq:error-propagated}) from?\\

\begin{itemize}
\item[] Again starting with
\begin{equation}
D  = \frac{1}{2} \sum_{j=1}^{N} {e_j}^2 
   = \frac{1}{2} \sum_{j=1}^{N} (y_j - z_j)^2
   = \frac{1}{2} \sum_{j=1}^{N} (f(h^L_j) - z_j)^2
\end{equation}
\item[]So when $r=L$
\begin{equation}
\delta^L_j \equiv \frac{\partial D}{\partial h^L_j}=
e_j^L \cdot f^{\prime}(h^L_j).
\end{equation}
\item[]When $r<L$ holds $D$ can be expressed as a function of $h^r_k$ for
\begin{displaymath}
k = 1,2, \cdots, k_r
\end{displaymath}
and each of these $h^r_k$ are influenced by $h^{r-1}_j$. Hence
$\delta^{r-1}_j$ is defined as \footnote{For a function of
$n$ variables each of which is also a function of $t$, that is,
\begin{equation} 
F(x_1(t),x_2(t),\cdots, x_n(t)),
\end{equation}
the partial derivative of $F$ is
\begin{equation}
\frac{\partial F}{\partial t} =
\frac{\partial F}{\partial x_1} \frac{\partial x_1}{\partial t} +
\frac{\partial F}{\partial x_2} \frac{\partial x_2}{\partial t} +
\cdots +
\frac{\partial F}{\partial x_n} \frac{\partial x_n}{\partial t}.
\end{equation}
}
\begin{equation}
\delta^{r-1}_j \equiv \frac{\partial D}{\partial h^{r-1}_j} 
   = \sum^{k_r}_{k=1}\frac{\partial D}{\partial h^{r}_k}\cdot
                       \frac{\partial h^{r}_k}{\partial h^{r-1}_j}
   = \sum^{k_r}_{k=1}\delta^r_k \cdot
                       \frac{\partial h^{r}_k}{\partial h^{r-1}_j}\\
\end{equation}
\item[]Here, since
\begin{equation}\label{eq:four}
h_k^{r} = \sum_{m=1}^{k_r} w_{km}^r \cdot y_m^r = 
\sum_{m=1}^{k_r} w_{km}^r \cdot f(h_m^{r-1})
\end{equation}
We obtain
\begin{equation}
\frac{\partial h^{r}_k}{\partial h^{r-1}_j} 
   = \frac{\partial \Biggl({\displaystyle \sum^{k_{r-1}}_{m=1}}
                                     w^r_{km} \cdot f(h^{r-1}_m) \Biggl)}
            {\partial h^{r-1}_j} \\
   = w^r_{kj} \cdot f^{\prime}(h^{r-1}_j)
\end{equation}
\item[]Hence,
\begin{equation}
\delta^{r-1}_j = \sum^{k_r}_{k=1} \delta^r_k \cdot w^r_{kj} \cdot
                 f^{\prime}(h^{r-1}_j).
\end{equation}
\item[]In conclusion, if we define
\begin{equation}
e^{r-1}_j = \sum^{k_{r}}_{k=1} \delta^r_k \cdot w^r_{kj}
\end{equation}
\item[]we obtain
\begin{equation}
\delta^{r-1}_j = e^{r-1}_j \cdot f^{\prime}(h^{r-1}_j)
\end{equation}
\end{itemize}
%---------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf Learning by an Evolution:}\\

\noindent
$\bullet$ Artificial Evolution --- 
From a biological analogy, the followings are defined.
\begin{description}
\item {\it Chromosome:}\\ 
      Each chromosome is comprised of {\it genes} each of which is occupied
      by an {\it allele}. It is also called  an {\it individual.}
\item {\it Population:}\\
      A number of individuals constructs a population.
\item {\it Fitness:}\\
      The ability of each individual is evaluated as the degree to how
      the individual fits to the environment 
      which is called a fitness value.
\item {\it Selection:}\\
      Parents are selected to produce one offspring. The higher the fitness
      the more likely to be selected, e.g., (1) selection is always from 
      the best half of the population, or (2) selection is made so that 
      the probability is proportional to the fitness value. 
\item {\it Crossover:}\\
      Child chromosome are produced by picking up genes either from 
      those of the parent chromosomes at the same position.
\item {\it Mutation:}\\
      To introduce new allele some of the genes are replaced with randomely
      generated new gene.
\end{description}

\hspace*{1in}\\
\noindent
$\bullet$ Algorithm:
\begin{enumerate}
\item {\it Initialization:}
  Initialize all the individuals in the 1st generation at random.
\item {\it Fitness Evaluation:}
  Evaluate fitness of all the individuals of the population.
\item {\it Reproduction:}
  \begin{enumerate}
  \item[(1)] Select two parents according to the fitness.
  \item[(2)] Recombine the parents to create an offspring.
  \item[(3)] Mutate the offspring.
  \item[(4)] Repeat (1) to (3) until new generation of same size 
             is obtained.
  \end{enumerate}
\item {\it Evolution:} Repeat 2. to 3. until the perfect individual 
       appears, or prespecified generations is reached.
\end{enumerate}

\clearpage
\noindent
$\Box$ {\bf Chess (Satran\c{c}) by Neural Networks}\\
\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=chess.eps,width=16cm,height=10cm}
 \end{center}
\end{figure}

\noindent
$\bullet$ One possible implementation:
\begin{itemize}
\item[-] 64 input neurons each of which takes a value from --6 to 6 
         representing a stone, plus one input binary neuron representing 
         whose turn, which corresponds to one scene of a game.
\item[-] 2 output neurons: one takes a value from --6 to 6 and the other 
         from 1 to 64, representing a possible best movement, that is,
         which stone should be moved to where? 
         (e.g., output 1 and 48 means that the stone-1 should be moved to 
         \noindent
\end{itemize}

\clearpage
$\Box$ {\bf Backgammon (Tavla) by Neural Networks}
\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=backgamon.eps,width=8cm,height=12cm}
 \end{center}
\end{figure}

\noindent
$\bullet$ One possible implementation:
\begin{itemize}
\item[-] a total of 29 input neurons;
   \begin{itemize}
   \item[$\star$] 26 input neurons\footnote{two of which are for 
         the outside position of mine and opponent's, respectively}
         each of which takes a value from $-15$ to 15,
         representing a number of stones at each cite, positive ones are
         mine and negative ones are opponent's, plus two neurons with each 
         indicating the figure of two dice, 
         and one more neuron representing whose turn.
   \end{itemize}
\item[] \begin{center}\underline{\hspace*{4in}}\end{center}
\item 4 output neurons\footnote{Usually we need two but if the figures
      of two dice are identical, the number of movement is four.}
   \begin{itemize}
   \item[$\star$] each of which takes a value from 1 to 6 which indicates
         how many positions the corresponding stone proceeds.
   \end{itemize}
\item[or]
\item 24 output neurons
   \begin{itemize}
   \item[$\star$] indicating the next scene as the 24 input neurons 
                  for the purpose above. 
   \end{itemize}
\end{itemize}

\clearpage
\noindent
$\Box$ {\bf Reward and Penalty Learning:}\\

\noindent
An example on perceptron with one hidden layer.\\

\begin{itemize}
\item $N_0$ {\it analog} and {\it deterministic} output neurons:
   \begin{equation}
   y_i^2 = f(\sum_j w_{ij}^2 y_j^1)
   \end{equation}
\item[]where
   \begin{equation}
   f(x)=\frac{1}{1+ \exp (-x)}
   \end{equation}
\item {\it Binary} and {\it stochastic} hidden neurons:
   \begin{eqnarray}
   \mbox{prob}(y_i^1=1) &=& f(\sum_j w_{ij}^1 x_j)\\
   \mbox{prob}(y_i^1=0) &=& 1-f(\sum_j w_{ij}^1 x_j)
   \end{eqnarray}
\item Using
   \begin{equation}
   D=\frac{1}{N_0} \sum_i (\hat{y}_i^2 - y_i^2)^2
   \end{equation}
   \begin{itemize}
   \item modify weights to output layer by {\it gradient} method as
   \begin{equation}
   \delta w_{ij}^{\mbox{\small out}} = \epsilon (\hat{z}_i - z_i)
   f^{\prime} (\sum_k w_{ik}^{\mbox{\small out}} y_k)y_j
   \end{equation}
   \item and weights to hidden layer in a stochastic way as
   \begin{eqnarray}
   \nonumber
   \delta w_{ij}^{\mbox{\small hidden}} &=& 
   r \epsilon (y_i - f(\sum_k w_{ik}^{\mbox{\small hidden}} x_k)x_j \\
      &+&   (1-r) \lambda \epsilon (1-y_i - 
            f(\sum_k w_{ik}^{\mbox{\small hidden}} x_k)x_j
   \end{eqnarray}
   \end{itemize}
\item[] where $r$ is signal meaning success/failure of the task, i.e., 
   \begin{itemize}
   \item[$\star$] $r=1$ with probability $1-D$;
   \item[$\star$] $r=0$ with probability $D$.
      \begin{itemize}
      \item[] IF $rand() < 1-D$;
      \item[] \hspace*{.6in}THEN $r=1$;
      \item[] \hspace*{.6in}ELSE $r=0$;
      \end{itemize}
   \end{itemize}
\end{itemize}

\clearpage
$\bullet$ Parameter notations of the previous few pages:\\
\begin{Large}
\begin{center}
The $i$-th output neuron outputs $z_i$\\
while desirerd output is $\hat{z}_i$.\\
\hspace*{1in}\\
$\Uparrow$\\
\hspace*{1in}\\
The $i$-th output neuron takes \\
\begin{displaymath}
\sum_k^{N_{\mbox{\small hidden}}} w_{ik}^{\mbox{\small out}} y_k
\end{displaymath}
from all the hidden neurons.\\
\hspace*{1in}\\
$\Uparrow$\\
\hspace*{1in}\\
Each of hidden neuron outputs $y_k$,\\
\hspace*{1in}\\
$\Uparrow$\\
\hspace*{1in}\\
The $i$-th hidden neuron takes 
\begin{displaymath}
\sum_k^{N_{\mbox{\small input}}} w_{ik}^{\mbox{\small hidden}} x_k
\end{displaymath}
from the input layer.\\
\hspace*{1in}\\
$\Uparrow$\\
\hspace*{1in}\\
Each input neuron takes an input $x_k$, and\\
send to all neurons in the hidden layer. 
\end{center}
\end{Large}

\clearpage
\begin{itemize}
\item Apply this to a task of symmetry detection.
   \begin{itemize}
   \item $n^2$ input, 12 hidden neurons, and 3 output.
   \item if the $n \times n$ pixels of the input are
      \begin{itemize}
      \item horizontally symmetric
      \item vertically symmetric
      \item diagonally symmetric
      \end{itemize}
   \item[] the 1st, 2nd and 3rd neuron should be acctivated.
   \end{itemize}
\item[]
\item Interpretation of the reward and penalty learning.
\end{itemize}

\clearpage
\noindent
$\Box$ {\bf Unsupervised Learning:}\\

\noindent
Unsupervised learning can only do anything useful 
when there is redundancy in the input data. 
{\it In this sence redundancy provides knowledge.}\\

\begin{itemize}
\item Learning by Competition.
\item Kohonen's Self-organizing Map.
\item Reinforcement Learning.\\
\end{itemize}

\noindent
{\bf (1) Unsupervised Learning through Competition:}\\

\noindent
Let $\mbox{\bf x}=(x_1,...,x_n)$ be a normalized input vector, 
i.e., 
\begin{equation}
\sum_{i=1}^n x_i = 1,
\end{equation}
in $n$-dimensional space which we want to classify in one of 
$k$ different clasters.\\

\begin{itemize}
\item The network consitsts of $n$ real-valued input neurons and 
$k$ binary output neurons (with all neurons zero-threshold.)
\item Each output neuron receives
\begin{equation}
h_i = \sum_{j=1}^{n} w_{ij}x_j
\end{equation}
from all the neurons in the input layer.\\
\item Then the only neuron which recieves
\begin{equation}
h_m = \max_i (h_i)
\end{equation}
will be on.
\clearpage
\item Learning Algorithm:\\
   \begin{itemize}
   \item[1.]  Initialize all the weights $w_{ij}$ at random, and 
              normaliz them such that
\begin{equation}
\sum_{j=1}^n w_{ij}=1 \hspace{.2in} \mbox{for} 
\hspace{.2in}\forall i=1,...,k\\
\end{equation}
   \item[2.] Selct a vector $\mbox{\bf x}^{\mu}$ at random 
             from the training sample, and compute
\begin{equation}
h_i = \sum_{j=1}^n w_{ij} x_j \hspace{.2in} \mbox{for} 
\hspace{.2in}\forall i=1,...,k\\
\end{equation}
   \item[3.] {\bf The Winner Takes All Procedure}  
      \begin{itemize}
      \item Modify only the weight $w_{mj}$ which recieves 
\begin{equation}
h_m = \max_{i} h_i
\end{equation} 
as
\begin{equation}
w_{mj}^{\mbox {\small new}} = w_{mj}^{\mbox {\small old}} + \delta w_{mj}
\end{equation}
       where
\begin{equation}\label{eq:delta}
\delta w_{mj} = \epsilon (x_k - w_{ik})
\end{equation}
and normalize them again.\\
      \end{itemize}
\item[4.] Repeat 2 and 3
          until a predetermined number of steps is reached.\\
   \end{itemize}
\item[]
\begin{large}
\item[Note that]
   \begin{itemize}
   \item[$\cdot$] The difference between this algorithm and perceptron 
                 learning is that the input set cannot be classified 
                 a priori in a positive or a negative set or in any of 
                 several different clusters.
   \item[$\cdot$] When we monitor the number of updates for each weight 
                 vector in order to make the process as balanced as 
                 possible, we call this learning with conscience.
   \end{itemize}
\end{large}
\clearpage
\item A numerical excersise:
   \begin{itemize}
   \item[] Assume three input neurons and three output neurons 
           with $w_{ij}$
\begin{eqnarray}
\left(
\begin{array}{rrr}
 0.23 & -0.72 & -0.51 \\
-0.49 &  0.33 & -0.16 \\
 0.23 &  0.68 &  0.84 \\
\end{array}
\right).
\end{eqnarray}
   \item[] Then under an input $(-1, 1, -1)$,
      \begin{itemize}
      \item  (1) obtain $h_m$;
      \item  (2) modify weights.\\
      \end{itemize}
   \end{itemize}
\item How it works?
   \begin{itemize}
   \item When we take {\bf x} and {\bf w} as
\begin{eqnarray}
\nonumber
\mbox{\bf x} &=& (x_{1}, x_{2},\cdots, x_{N_i},) \\
\nonumber
\mbox{\bf w} &=& (w_{i1}, w_{i2},\cdots, w_{i N_i},) \\
\nonumber
\end{eqnarray}
the equation (\ref{eq:delta}) implies a vector such as:
\begin{figure}[h]
 \begin{center}
   \epsfile{file=vector.eps,width=6cm,height=3cm}
 \end{center}
\end{figure}
Therefore $\mbox{\bf w}+\delta\mbox{\bf w}$ makes {\bf w}
become closer to {\bf x}, and\\
\item the more {\bf w} is closer to {\bf x}, the larger
      the inner product $h_i$ becomes.\\
\item What will happen 
      when multiple $\mbox{\bf x}^\mu$ is repeatedly given?
   \end{itemize}
\end{itemize}

\clearpage
\noindent
{\bf (2) Kohonen's Self-organizing Network:}\\

\noindent
Simulation of topology preserving maps in the brain.

\begin{itemize}
\item Kohonen Learning Algorithm
   \begin{itemize}
   \item[]The $n$-dimensional weight vectors $w_1,..,w_m$ of the m computing
     neurons are selected at random. 
     An initial radius $r$, 
     a learning constant $\eta$, 
     and a neighborhood funciton $\phi$ are selected.\\
   \item[1.] Select an input vector $\zeta$ using the desired 
             probability distribution over the input space.\\
   \item[2.] The neuron $k$ with the maximum excitation is selected,
             that is, for which the distabnce between $w_i$ and $\zeta$ 
             is minimal for $i=1,\cdots,m$.\\
   \item[3.] The weight vectors are updated using the nighborhood function 
             and the update rule\\
   \begin{equation}
   w_i=w_i+ \eta \phi(i,k)(\zeta - w_i) \mbox{for} i=1,\cdots,m 
   \end{equation}
   \item[]
   \item[4.]  Stop if the maximum number of iterations has been reached, 
              otherwise modify $\eta$ and $\phi$ as sceduled and continue 
              with step 1.
   \end{itemize}

%%\item Examples:
%%   \begin{itemize}
%%   \item[] (i) from 2D to 1D
%%      \begin{itemize}
%%      \item points inside of a triangle in 2-dimensional space into 11 
%%            classes two inputs for x1,x2 representing coordinate eleven 
%%            outputs corresponding to (wi1,wi2) which is closest to 
%%            the (x1,x2) will be on
%%      \item plot (w,w)
%%      \end{itemize}
%%   \item[] (ii) from 2D to 2D
%%   \end{itemize}

\item An example:
\begin{figure}[htbp]
 \begin{center}
   \epsfile{file=triangle.eps,width=12cm,height=8cm}
 \end{center}
\end{figure}
\end{itemize}

\clearpage
\noindent
{\bf (3) Unsupervised Reinforcement Learning}\\

\begin{itemize}
\item Assume that a set of empirical data is given which consists of 
      the $n$-dimensional vectors $(x_1,\cdots, x_m)$.
\item {\it The first principal component} of this set of vectors is 
       a vector {\bf w} which maximizes
\begin{equation}
\frac{1}{m} \sum_{i=1}^m \| w_i x_i \| ^2
\end{equation}
\item The second principal component is computed by subtracting from each 
      vector $x_i$ its projection on the first principal component.
\item[]
\item architecture
   \begin{itemize}
   \item $n$ input neurons which are given $x_1, \cdots, x_n$
   \item one ouput neuron which receives
   \begin{equation}
   \sum_{i=1}^n w_i x_i
   \end{equation}
   \end{itemize}
\item Algorithm --- Computation of the first principal component
   \begin{itemize}
   \item Let {\bf x} be a $n$-dimensional vector.
   \item The vector {\bf w} is initialized randomly ($w_{i} \ne 0$).
   \item A learning constant $\gamma$ with $0<\gamma \le 1$ is selected.
   \item A vector x is selected randomly from x
   \item The scalar product $\phi=xw$ is computed
         the new weight vector is $w + \gamma \phi (x - \phi w)$
   \item go to update making $\gamma$ smaller. 
   \end{itemize}
\end{itemize}

\clearpage
\noindent
$\Box$ {\bf Fully-connected Neural Networks.}\\
\begin{itemize}
\item Toy Model of Three Neurons:

\begin{figure}[h]
 \begin{center}
   \epsfile{file=fig-nn.eps,width=10cm,height=5cm}
 \end{center}
\end{figure}

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

\item Example 1

\begin{figure}[h]
 \begin{center}
    \epsfile{file=three-neuron-1-portrait.eps,width=10cm,height=7cm}
\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
\item Example 2

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

\item Example 3

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

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

\hspace*{1in}\\
\hspace*{1in}\\
\noindent
$\Box$ {\bf A category of trajectories}\\
\begin{figure}[h]
 \begin{center}
    \epsfile{file=trajectory.eps,width=12cm,height=8cm}
\end{center}
\end{figure}
\end{itemize}
%-----------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf What is Associative Memory}\\

\begin{itemize}
\item $N$ neurons that are fully connected store $N$-bit of  
      $p$ out of $2^N$ patterns simultanously 
      as {\it fixed point attractors.}\footnote{Here we restrict patterns 
                                                to bipolar patterns.}
\item Convergence to the initial state of the noisy stored pattern
      implies an {\it error correcting capability.}
\item How can we determine weights.
   \begin{itemize}
   \item 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}

   \item[] In the above toy example:

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

   \item[] An interpretation of Hebb's rule:
      \begin{itemize}
      \item A strong weight affects neurons at both ends 
            to be same states.
      \end{itemize}
\item[]
   \item Many other solutions of a {\it weight configuration} 
         to store a same set of patterns exist.
     \begin{itemize}
     \item Each 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}

\clearpage
\noindent
$\Box$ {\bf (Virtual) Energy of Network State}\\

\begin{itemize}\item[]
Assuming fully connected $N$ neurons,
given all weight values $w_{ij}$ from $i$-th to $j$-th neuron
and threshold of $i$-th neuron $\theta_i$, each state $\{ x_i \}$
correspond to an energy level $E$ as:


\begin{equation}
E = - \frac{1}{2}\sum_{i=1}^{N} \sum_{i=1}^{N} w_{ij}x_i x_j
                 - \sum_{j=1}^{N} \theta_{i}x_i
\end{equation}

\item[]
\item[]For example:

\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=energy.eps,width=16cm,height=10cm}
 \end{center}
\end{figure}
\end{itemize}

\hspace*{1in}\\
\begin{excersise}
Obtain state of the Garden-of-Eden and stable state(s) 
under three neurons with $w_{12} = w_{21} = w_{23} = w_{32} = -1$,
$w_{13} = w_{31} = 1$ and with all threshold beeing $-0.5$.
\end{excersise}

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

\noindent
The fully connected neural network model so far 
we've studied can also solve combinatorial problems.\\

\noindent
e.g.
\begin{itemize}
\item {\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
             ,that is, the effort to solve the problem grows exponentially
             with size instead of a power of the size (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}
   \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 ``$ij$-element is one'' means that the $i$-th city
             is in the $j$-th location in the tour.\\
      \end{itemize}
   \item Implementation by a fully connected neural network 
         with $N$ neurons.
   \begin{itemize}
      \item $S_{ij}(t)$ state of neuron 
            corresponds to the $ij$-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}
\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}

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

\clearpage
\noindent
$\bullet$ Simpler Version of the TSP\\

\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}
\end{itemize}


\end{large}
\end{document}
