\documentclass[12pt]{article}

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

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

\newtheorem{algorithm}{Algorithm}

\pagestyle{myheadings}
\markright{(Practice at BSTU in fall 2006 -- Parceptron)}
\thispagestyle{empty}

\begin{document}

\title{Parceptron}
\author{Akira Imada\\
\hspace*{1in}\\
Most recently renewed on}
\maketitle

\newtheorem{excersise}{Task} 

\section{Single Parceptron}
\noindent
Assume we have 10 inputs $x_1, x_2, \cdots, x_{10}$ and one output $y$. 
Also assume each input is binary 1 or $-1$.
All the input is connected to output with synapse whose weight is $w_i$ $(i=1,2, \cdots 10)$.
If $w_1 x_1 + w_2 x_2 + \cdots + w_{10} x_{10}$ is larger than a threshold $\theta$ then $y=1$, 
otherwise $y=-1$. That is,
\begin{equation}
y = sgn (\sum_{i=1}^{10}w_i x_i - \theta).
\end{equation}

\begin{figure}[h]
 \begin{center}
   \includegraphics[width=12cm,height=5cm]{2-layers.eps}
\caption{Schematic diagram of Single Parceptron.}
 \end{center}
\end{figure}

\begin{excersise}[A Framework]
Assigning random weight value from -1 to 1,
create a program which accepts $M$ binary inputs from keyboard, calculate $y$, and 
display 10 input and output with their color being green if the value is 1 or red
if the value is -1. Also show weighted sum of the inputs $\sum_{i=1}^{10}w_i x_i$
on the screen like the following Figure.
\end{excersise}

\begin{figure}[h]
 \begin{center}
   \includegraphics[width=9cm,height=8cm]{display.eps}
\caption{An example of display of the task.}
 \end{center}
\end{figure}



\subsubsection*{Examples of how can it work.}
One of the most typical example is to realise a Boolean function. For example, output is 1 if and only if all the input is 1, otherwise $-1$. \\

\begin{table}[h]
\begin{center}
\caption{An example of Boolean Function assuming 4 inputs case. Note that we call this AND logic when the number of input is 2.}
\begin{tabular}{r r r r r r r r r} \hline\hline
$x_1$    &   $x_2$    &   $x_3$    &   $x_4$    &   $x_5$  &   $x_6$ &   $x_7$   &   $y$    \\ 
\hline
-1       &   -1       &   -1       &   -1       &   -1     &   -1     &   -1     &   -1     \\
-1       &   -1       &   -1       &   -1       &   -1     &   -1     &   -1     &   -1     \\
-1       &   -1       &   -1       &   -1       &   -1     &   -1     &    1     &   -1     \\
-1       &   -1       &   -1       &   -1       &   -1     &   -1     &    1     &   -1     \\
$\cdots$ & $\cdots$   & $\cdots$   & $\cdots$   & $\cdots$ & $\cdots$ & $\cdots$ & $\cdots$ \\
 1       &    1       &    1       &    1       &    1     &    1     &    1     &   -1     \\
 1       &    1       &    1       &    1       &    1     &    1     &    1     &    1     \\  
\hline\hline
\end{tabular} 
\end{center}
\end{table}


\begin{excersise}[Extended AND]
Discover a set of weights and threshold so that $y=1$ if and only if input are all $1$, otherwise $y=-1$.
\end{excersise}


\begin{excersise}[Extended OR]
Discover a set of weights and threshold so that $y=1$ if at least one input is 1 and $y=-1$ if all input is $-1$.
\end{excersise}


\begin{excersise}[EVEN PARITY]
What about the case where $y=1$ if the number of 1 is odd, otherwise $y=-1$?
\end{excersise}



\section{Perceptron Learning}
\noindent
Assume now we have $m$ input and $n$ output
$w_{ij}$ is a weight value from input $j$ to output neuron $i$. $X^p$ is $p$-th input vector for training, that is, 
\begin{displaymath}
X^p = (x^p_1, x^p_2, x^p_3, ... x^p_n),
\end{displaymath}
\noindent
$\hat{Y}^p$ is target output vector when $p$-th training input $X^p$ is given, that is,
\begin{displaymath}
\hat{Y}^p = (\hat{y}^p_1, \hat{y}^p_2, \hat{y}^p_3, \cdots, \hat{y}^p_m)
\end{displaymath}
\noindent
$Y^p$ is actual output vector, that is,
\begin{displaymath}
Y^p = (y^p_1, y^p_1, y^p_1, \cdots y^p_m)
\end{displaymath}
\noindent
Then we can describe a learning of weights as
\begin{displaymath}
%%w_{ij}(t+1) = w_{ij}(t) + \eta (\hat{Y}^p - Y^p)(X^p)^t.
W(t+1) = W(t) + \eta (\hat{Y}^p - Y^p)^t(X^p).
\end{displaymath}
%Note that $(\hat{Y}^p - Y^p)(X^p)^t$ is an inner product of two vectors, that is,
%\begin{displaymath}
%(\hat{y}^p_1 - y^p_1)x^p_1 + (\hat{y}^p_2 - y^p_2)x^p_2 + (\hat{y}^p_3 - y^p_3)x^p_3 + 
%\cdots + (\hat{y}^p_m - y^p_m)x^p_m.
%\end{displaymath}
\noindent
Note that $(\hat{Y}^p - Y^p)^t(X^p)$ is an outer product of two vectors, and result is a matrix of a same size of $W$, and 
$\eta$ is a learning coefficient set to a small real number ranging $(0<\eta<1$. The learning is repeated until the change in weight value becomes neglectable. In other words, we have to preset $p$ enough a large number so that all of $w_{ij}(t+1) - w_{ij}(t)$ becomes almost 0, after repeating above $p$times. This is also called {\it Widrow-Hoff Learning Algorithm}\\


\noindent
Note that outer product of this specific two vectors is calculated as below.
\begin{eqnarray*}
   \left(
   \begin{array}{c}
      a\\
      b
   \end{array}
   \right )
(x y z)
=
   \left(
   \begin{array}{ccc}
      ax & ay & az \\
      bx & by & bz \\
   \end{array}
   \right )
\end{eqnarray*}


\clearpage
\section{Multi-layer Parceptron}

\begin{figure}[h]
 \begin{center}
   \includegraphics[width=12cm,height=9cm]{3-layers.eps}
\caption{Schematic diagram of Multi-layer Parceptron.}
 \end{center}
\end{figure}

\clearpage
\section{Robot Navigation in a Grid-world}

\begin{figure}[h]
 \begin{center}
   \includegraphics[width=7.5cm,height=5cm]{lake.eps}
   \includegraphics[width=7.5cm,height=4.9cm]{cliff.eps}
\caption{Two examples of grid-world to be explored.}
 \end{center}
\end{figure}

\clearpage
\section{Let's try an evolution of chromosom of lucky dog.}

\begin{itemize}
\item Represent a series of $x_{i}$ as a {\it population} of strings. Each of 
these strings is refered to as {\it chromosome} or sometimes called {\it individual}.
\begin{figure}[hbtp]
\begin{center}
    \includegraphics[width=15cm, height=0.75cm]{chromosome-2.eps}
\end{center}
\end{figure}
\item Define a {\it fitness} evaluation by ``How good is each individual?''
\end{itemize}

\noindent
Then we start an evolution as follows, expecting better solutions from generation to generation.
\begin{itemize}
\item[1.] {\bf (Initialization)} Generate an initial {\it population} of $p$ individuals
           at random.
\item[2.] {\bf (Fitness Evaluation)} Evaluate fitness of each chromosome and 
                sort the chromosomes according to its fitness from the best to the worst.
\item[3.] {\bf (Selection)} Select two chromosomes
   \begin{itemize}
   \item Here, from the best half of the population at random, which is called a 
         {\it Truncate Selection}.
   \end{itemize}
\item[4.] {\bf (Reproduction)} Produce a child by the following two operations:
   \begin{itemize}
   \item {\it Uniform Crossover}, for example
\begin{figure}[hbtp]
\begin{center}
     \includegraphics[width=15cm, height=2.5cm]{crossover.eps}
\end{center}
\end{figure}
   \item {\it Mutation} 

\begin{figure}[hbtp]
\begin{center}
\includegraphics[width=15cm, height=1.3cm]{mutation.eps}
\end{center}
\end{figure}
   \end{itemize}
\item[5.] Create the next generation by repeating the steps from 3 to 4 $n$ times. 
\item[6.] Repeat the steps from 2 to 5 until (near) optimal solution is obtained.
\end{itemize}


\end{document}
