\documentstyle[12pt,eclepsf]{article}
\textheight 250mm
\topmargin -10mm
\textwidth 180mm
\oddsidemargin -7mm

\markright{(Practice at BSTU in fall 2005 -- Kohonen's Self Organizing Map)}

\begin{document}

\title{Kohonen's Self Organizing Map: \\
Reduction of  Dimension}
\author{Akira Imada}
\date{}
\maketitle

\section{Let's construct a framework.}
We can use the Kohonen's SOM for dimension reduction. It's important
because, we, human being couldnt never imagine the space 
whose dimension is more than three. Here to study how it works,
we map 2-dimensional space to 1-dimensional space. 
Though both worlds are visible but this is just to learn how it works.
So the frame work is as Figure \ref{fig:01}

\begin{figure}[h] \label{fig:01}
 \begin{center}
   \epsfile{file=som-from-1-to-2.eps,width=10cm,height=4cm}
 \end{center}
 \caption{A framework of Kohonen's SOM for a mapping from 2-D to 1-D space.}
\end{figure}


\newtheorem{excersise}{Excersise}
\begin{excersise}\label{excersise:01}
As an example of mapping from 2D to 1D,
construct a SOM network with two input and 100 output as follows:
\begin{itemize}
\setlength{\itemsep}{0pt}
\item[(1)] All of the two input neurons connect to all of 100 
output neurons. (So we have 200 syanapses)
\item[(2)] Give each of all these 200 syanapses a random weight
value between 0.00 to 1.00.
\item[(3)] Design a {\it man-machine interface} to show
{\it Winner-Take-All} scheme on the display screen
   \begin{itemize}
   \item[(i)] Display 100 output neurons in a 10 $times$ 10
              rectanglar array on the display screen.
   \item[(ii)] Disign so that the algorithm can accept 2 input
               from key-board.
   \item[(iii)] Make only one neuron (= winner) highlited. 
                The winner is the neuron which has the synaptic weights
                $(w_1, w_2)$ closest to the input $(x_1, x_2)$.
   \end{itemize}
\end{itemize}
\end{excersise}


\begin{figure}[h]
 \begin{center}
   \epsfile{file=display-koh.eps,width=14cm,height=7cm}
 \end{center}
 \caption{An example of the grphic on the display screen to show 
          winner take all algorithm.}
\end{figure}


\section{Let's Renew Weights -- Winner Takes All}

\newtheorem{algorithms}{Algorithm}
\begin{algorithms}
As an example of mapping from 2D to 1D,
construct a SOM network with two input and 100 output as follows:
\begin{itemize}
\setlength{\itemsep}{0pt}
\item[(0)] Initialize all the weights at random from -1 to 1.
\item[(1)] $t$ = 0.
\item[(2)] Pick up a point (x1, x2) randomly from inside 
   a triangle in 2D space which is in the domain $[-1, 1]$
\item[(3)] Give the coordinate (x1, x2) of the point 
           to the SOM as a set of inputs.
\item[(4)] Renew weights only of the winner neuron
           and the next neuron's. That is $2\times 3=6$ weights.
with the equation
\begin{equation}
        w = w + E * K * (x - w)
\end{equation}
where 
\begin{equation}
        E = 0.0001 (25000-t)
\end{equation}
so that learning-ratio is decreased gradually, and
\begin{equation}
K = \left\{
\begin{array}{ll}
1.00 & \hspace{.2in} \mbox{if the neuron is the winner} \\
0.50 & \hspace{.2in} \mbox{if the neuron is the next to the winner} \\
0.00 & \hspace{.2in} \mbox{otherwise}
\end{array}
\right.
\end{equation}
\item[(5)] $t$ = $t$ + 1 
\item[(6)] Repeat (1) to (3)  from  $t$ = 1 to $t$ = 25000 
%\item[(7)] Plot all of (w1, w2)
\end{itemize}
\end{algorithms}


\begin{figure}[h]
 \begin{center}
   \epsfile{file=triangle.eps,width=8cm,height=6cm}
 \end{center}
\end{figure}


\section{Let's observe a dimension reduction.}

\begin{excersise}
Let's observe a dimension reduction, 
with using SOM created via Excersise \ref{excersise:01}
in the following way.
\begin{itemize}
\setlength{\itemsep}{0pt}
\item[1.] Pick up 5 points inside the triangle
          used in Excersise \ref{excersise:01} close to 
          each of the three verteces.
\item[2.] Give each of the three groups a differnt color (e.g. R,G, and B).
\item[3.] Give these 15 points as inputs and give 
          each of the 15 output neurons the corresponding color given in 2.
\item[4.] Show all the 100 output neurons with assigned colors if any.
\end{itemize}
\end{excersise}



\clearpage
%%\newtheorem{excersise}{Excersise}
\begin{excersise} \label{ex:2}
As an example of mapping from 2D to 1D,
construct a SOM network with two input and 100 output with $N_x =100$ and $N_y = 1$. 
\end{excersise}

\begin{figure}[h]
 \begin{center}
   \epsfile{file=som-from-1-to-2.eps,width=12cm,height=4cm}
 \end{center}
\end{figure}

\noindent
Then try the following algorithm.
\begin{itemize}
\item[1.] Choose an input point by sampling it at randome from 2D triangle like (b) below.
           
\begin{figure}[h]
 \begin{center}
   \epsfile{file=kohonen-patterns.eps,width=12cm,height=4cm}
 \end{center}
\end{figure}

\item[2.] Feed the cordinate of the point $(x_1, x_2)$ to the input of the Kohonen SOM network,
           so that weight values  are self-organized according to Eq.(\ref{eq:01}), that is,
\begin{displaymath}
w_d^{i} = w_d^{i} + \epsilon \cdot \exp \{ -(x_d - w_d^{\mbox{\small max}})^2\}
                                   \cdot (x_d - w_d^{i})
\end{displaymath}

where
$w_d^{\mbox{\small max}}$ is the weight value from $x_d$ to the 
output neuron of the winner, 
$d=1,2$ and $i = 1,2, \cdots, 100$.
The value of $\epsilon$ is decreased gradually like, for example,
   \begin{itemize}
   \item[$\cdot$] Starting with $\epsilon = 0.05$ for the 1st repetion 1 -- 5000;
                  $\epsilon = 0.04$ for the 2nd repetion 5001 -- 10000;
                  $\epsilon = 0.03$ for the 3rd repetion 10001 -- 15000; 
                  $\epsilon = 0.03$ for the 4th repetion 15001 -- 20000; 
                  and $\epsilon = 0.01$ for the last repetion 20001 -- 25000
   \end{itemize}
\item[] Or, simply by
\begin{displaymath}
w_d^{i} = w_d^{i} + \epsilon (x_d - w_d^{i})
\end{displaymath}
\item[3.] Repeat 1.~and 2.~above, say, 25000 times.
\item[4.] Plot 100 pairs of weigthts $(w_1^i, w_2^i)$ \hspace{0.05in} $i = 1, 2, \cdots, 100$
\end{itemize}

\noindent
The bellow is an example of the result of plotting
\begin{displaymath}
(w_1^1, w_2^1), (w_1^2, w_2^2), \cdots, (w_1^{100}, w_2^{100})
\end{displaymath}

\begin{figure}[h]
 \begin{center}
   \epsfile{file=som-from-1-to-2.eps,width=12cm,height=4cm}
 \end{center}
\end{figure}

\begin{figure}[h]
 \begin{center}
   \epsfile{file=triangle.eps,width=8cm,height=6cm}
 \end{center}
\end{figure}


\end{document}


\section{Map from 2D to 2D}
We now assume a Neural Network with two input neurons and 
$N_x \times N_y$ output neurons, no hidden layers.\\

\noindent
The location of each of the output neurons is denoted with \\
\begin{displaymath}
\mbox {\bf n} = (n_x, n_y) \hspace{.3in} n_x = 1, \cdots N_x, 
                           \hspace{.15in} \mbox{and} \hspace{.15in} 
                                         n_y = 1, \cdots N_y
\end{displaymath}
Each of the two input neurons connect to each of the output neurons via a synapse.
The weight value of the synapse from the $d$-th input neuron $(d=1,2)$
to the output neuron {\bf n} is denoted as $w_d^{\mbox{\bf n}}$ and we use a notation
\begin{displaymath}
\mbox{\bf w}^{\mbox{{\large {\bf n}}}} = (w_1^{\mbox{\large {\bf n}}}, w_2^{\mbox{\large {\bf n}}})
\end{displaymath}

\begin{figure}[h]
 \begin{center}
   \epsfile{file=kohonen.eps,width=18cm,height=7.5cm}
 \end{center}
\end{figure}

\clearpage
\noindent
Then the $\mbox{\bf w}^{\mbox{\large {\bf n}}}$ can be self-organized in the following way:
\begin{itemize}
\item[1.] Determin $\mbox{\bf w}^{\mbox{\large {\bf n}}}$ at random
\item[2.] The input $\mbox {\bf x} = (x_1, x_2)$
is given by drawing the point $(x_1, x_2)$ at random from a given domain, like

\begin{figure}[h]
 \begin{center}
   \epsfile{file=kohonen-patterns.eps,width=12cm,height=4cm}
 \end{center}
\end{figure}

\item[3.] Select one output neuron $\mbox{\bf n}_{0}$ such that
$\vert\vert \mbox{\bf x} - \mbox{\bf n}_{0} \vert\vert$ is minimum of all 
$\mbox{\bf x} - \mbox{\bf n}$.
\item[4.] Renew weight values as follows:
\begin{equation}\label{eq:01}
\mbox{\bf w}^{\mbox{\large {\bf n}}} = \mbox{\bf w}^{\mbox{\large {\bf n}}}
 + \epsilon \cdot g(\mbox{\bf n} - 
        \mbox{\bf n}_{0})(\mbox{\bf x} - \mbox{\bf w}^{\mbox{\large {\bf n}}}),
\end{equation}
where $\eta$ decreases gradually as the numer of repetition (see Step 5. bellow)
increases,
\begin{displaymath}
g(\mbox{\bf n} - \mbox{\bf n}_{0}) 
   = \exp(-\frac{\vert\vert \mbox{\bf x} - \mbox{\bf n}_{0} \vert\vert^2}{2\delta}),
\end{displaymath}
and $\delta$ is a constant to adjust to obtain an appropriate result.\\
\item[]
Or,
\begin{displaymath}
g(\mbox{\bf n} - \mbox{\bf n}_{0}) \equiv 1.
\end{displaymath}
\item[5.] Repeat 2.~- 4.~above.
\end{itemize}

\clearpage
%%\newtheorem{excersise}{Excersise}
\begin{excersise} \label{ex:2}
As an example of mapping from 2D to 1D,
construct a SOM network with two input and 100 output with $N_x =100$ and $N_y = 1$. 
\end{excersise}

\begin{figure}[h]
 \begin{center}
   \epsfile{file=som-from-1-to-2.eps,width=12cm,height=4cm}
 \end{center}
\end{figure}

\noindent
Then try the following algorithm.
\begin{itemize}
\item[1.] Choose an input point by sampling it at randome from 2D triangle like (b)
           in the previous page,
\item[2.] Feed the cordinate of the point $(x_1, x_2)$ to the input of the Kohonen SOM network,
           so that weight values  are self-organized according to Eq.(\ref{eq:01}), that is,
\begin{displaymath}
w_d^{i} = w_d^{i} + \epsilon \cdot \exp \{ -(x_d - w_d^{\mbox{\small max}})^2\}
                                   \cdot (x_d - w_d^{i})
\end{displaymath}

where
$w_d^{\mbox{\small max}}$ is the weight value from $x_d$ to the 
output neuron of the winner, 
$d=1,2$ and $i = 1,2, \cdots, 100$.
The value of $\epsilon$ is decreased gradually like, for example,
   \begin{itemize}
   \item[$\cdot$] Starting with $\epsilon = 0.05$ for the 1st repetion 1 -- 5000;
                  $\epsilon = 0.04$ for the 2nd repetion 5001 -- 10000;
                  $\epsilon = 0.03$ for the 3rd repetion 10001 -- 15000; 
                  $\epsilon = 0.03$ for the 4th repetion 15001 -- 20000; 
                  and $\epsilon = 0.01$ for the last repetion 20001 -- 25000
   \end{itemize}
\item[] Or, simply by
\begin{displaymath}
w_d^{i} = w_d^{i} + \epsilon (x_d - w_d^{i})
\end{displaymath}
\item[3.] Repeat 1.~and 2.~above, say, 25000 times.
\item[4.] Plot 100 pairs of weigthts $(w_1^i, w_2^i)$ \hspace{0.05in} $i = 1, 2, \cdots, 100$
\end{itemize}

\noindent
The bellow is an example of the result of plotting
\begin{displaymath}
(w_1^1, w_2^1), (w_1^2, w_2^2), \cdots, (w_1^{100}, w_2^{100})
\end{displaymath}

\begin{figure}[h]
 \begin{center}
   \epsfile{file=som-from-1-to-2.eps,width=12cm,height=4cm}
 \end{center}
\end{figure}

\begin{figure}[h]
 \begin{center}
   \epsfile{file=triangle.eps,width=8cm,height=6cm}
 \end{center}
\end{figure}




\subsection*{A more general discription of the Network}
In the more general form, we also assume a two layered Neural Network. 
It has also $N_x \times N_y$ output neurons but the number of  input neurons
is more generally $d$. 
It maps a point in $d$-dimensional space
to a point in two-dimensional space. Hence we might use it for the purpose of 
dimension reduction.






