\documentstyle[12pt]{article}
\renewcommand{\baselinestretch}{1.5}
\setlength{\topmargin}{-.25in}
\setlength{\textheight}{8.5in}
\setlength{\oddsidemargin}{0in}
\setlength{\textwidth}{6.5in}
\newtheorem{thm}{Theorem}
\newtheorem{defn}{Definition}
\newtheorem{example}{Example}
\newtheorem{lemma}{Lemma}
\newtheorem{proposition}{Proposition}
\newtheorem{algorithm}{Algorithm}
\newcommand{\markex}{\nopagebreak\begin{center}\rule{5in}{.02in}\end{center}}
\newcommand{\mb}{\mbox}
\newcommand{\bm}{\boldmath}
\def\b#1{\mb{\bm$#1$}}
\newfont{\Bb}{msbm10 scaled\magstep1}
\begin{document}

\section{A Self-Organizing Network Model}
Up to now we discussed neural network models that have to have a teacher in order to learn presented patterns. Such mode of learning is referred to as the supervised mode. In this section, we analyze a neural network model that can learn in unsupervised mode and the network undergoes the self-organization process. Specifically, the network is capable of clustering of training patterns. It is assumed that the number of classes, $p$, is known. The network's number of weight vectors is equal to the number of classes in the training set. The weights are initialized and then normalized. After initialization, the training patterns, $\b x^{(1)}, \b x^{(2)}, \ldots, \b x^{(N)}$ are presented. In response to each presented pattern, we compute the winning neuron of the network, that is, we compute the network weight that is closest to the presented pattern. We call this computation the similarity matching. Let the presented pattern be denoted by $\b x$, where, for simplicity, we omitted the index. Then the similarity matching and can be described as
\[
\left\| \b x-\b w^{(k)}\right\|=\min_{1\le j \le p}\left\{ \left\| \b x-\b w^{(j)}\right\|\right\},
\]
where the index $k$ denotes the wining neuron. Searching for the winning neuron corresponds to finding the maximum among the $p$ scalar products,
\[
\max_{j=1,2,\ldots,p}\left\langle \b w^{(j)}, \b x\right\rangle.
\]
To see that this is indeed the case, note that since the weights and the patterns are normalized, that is, $\left\|\b w^{(j)} \right\|=\left\|\b x \right\|=1$, then we have
\begin{eqnarray*}
\left\| \b x-\b w^{(j)}\right\|&=&\left( \left\|\b x \right\|^2-2\left\langle \b w^{(j)},\b x\right\rangle + \left\|\b w^{(j)} \right\|^2\right)^{1/2}\\
&=&\left(2- 2\left\langle \b w^{(j)},\b x\right\rangle\right)^{1/2}.
\end{eqnarray*}
Hence, minimizing $\left\| \b x-\b w^{(j)}\right\|$ is equivalent to maximizing the scalar product $\langle \b w^{(j)},\b x\rangle$. On the other hand,
\[
\langle \b w^{(j)},\b x\rangle=\left\| \b w^{(j)}\right\|\left\| \b x\right\|\cos\left(\b w^{(j)},\b x\right),
\]
which means that the winning neuron is ``more parallel'' to the input pattern $\b x$ than the other neurons.

After the winning neuron is declared, it is updated, while the remaining weights are not changed. This is the reason for the name of the network---the winner-take-all~(WTA) network. This update algorithm is also known as the {\em Kohonen learning rule\/} after Kohonen who first proposed learning rule. The role of the update is to reduce the distance between the winning neuron, $\b w^{(k)}$, and the presented pattern, $\b x$. One way to accomplish this task is to apply the descent gradient method to the objective function $\frac{1}{2}\left\| \b x-\b w^{(j)}\right\|^2$. The gradient of $\frac{1}{2}\left\| \b x-\b w^{(j)}\right\|^2$ with respect to $\b w^{(j)}$ is
\[
\frac{1}{2}\nabla_{\b w^{(j)}}\left\| \b x-\b w^{(j)}\right\|^2=-\left( \b x-\b w^{(j)}\right).
\]
Applying the descent gradient method to minimize $\frac{1}{2}\left\| \b x-\b w^{(j)}\right\|^2$ with a step size $\alpha_k$ yields
\[
\b w^{(j)}(k+1)=\b w^{(j)}(k)+\alpha_k\left( \b x-\b w^{(j)}(k)\right).
\]
The weights of other neurons are unchanged, that is,
\[
\b w^{(j)}(k+1)=\b w^{(j)}(k),\quad\mb{for}\quad j\ne i.
\]
We summarize our discussion in the form of the following algorithm.
\begin{center}
{\bf Winner-Take-All~(WTA) Learning Algorithm}
\end{center}
\begin{enumerate}
\item {\bf Initialize Weights}\\
Generate the initial weights. Normalize each weight to have unit length: $\frac{\b w}{\|\b w\|}$.
\item {\bf Serially Present Training Patterns}\\
Normalize each training pattern $\b x^{(j)}$ to have unit length. The training patterns can be presented in a random order a fixed number of times.
\item {\bf Select Winning Neuron}\\
For each WTA weight, compute the dot product with the presented pattern. Select a weight that gives to the largest dot product. Call this the winning weight. 
\item {\bf Update Weight of Winning Neuron}\\
Let $i$ be the index of the winning weight. Set
\begin{eqnarray*}
\b w^{(i)}(k+1)&=&\b w^{(i)}(k)+\alpha_k\left(\b x^{(j)}-\b w^{(i)}(k)\right)\\
\b w^{(j)}(k+1)&=&\b w^{(j)}(k),\quad\mb{for}\quad j\ne i
\end{eqnarray*}
Normalize $\b w^{(i)}(k+1)$ to have unit length.
\item {\bf Repeat by Going to Step 2}\\
Repeat until stopping criterion is met.
\end{enumerate}
\markex
\begin{example}\label{ex:wta_zur}\rm
We take the same set of training patterns as in Zurada~\cite[page~407]{zurada92}:
\[
\left[\begin{array}{ccccc}
\b x^{(1)}&\b x^{(2)}&\b x^{(3)}&\b x^{(4)}&\b x^{(5)} 
\end{array}\right]=\left[\begin{array}{ccccc}
0.8  &  0.1736 & 0.707 & 0.342 & 0.6\\
0.6  & -0.9848 & 0.707 & -0.9397 & 0.8
\end{array}\right].
\]
The above patterns are already normalized and are marked in Figure~\ref{fig:wta_ex}. As can be seen from Figure~\ref{fig:wta_ex}, we can classify the training patterns into two classes, that is, $p=2$. The initial normalized weights are
\[
\left[\begin{array}{cc}
\b w^{(1)}_0 & \b w^{(2)}_0
\end{array}\right]=\left[\begin{array}{cc}
1 & -1\\
0 & 0
\end{array}\right].
\]
The initial weights are also marked in Figure~\ref{fig:wta_ex}. The training patterns, $\b x^{(1)}, \b x^{(2)}, \ldots, \b x^{(5)}$ are presented in ascending order and then recycled. After 200 presentations of the training set, we obtained the following final weights of the network:
\[
\left[\begin{array}{cc}
\b w^{(1)} & \b w^{(2)}
\end{array}\right]
=\left[\begin{array}{cc}
0.6628  &  0.2868\\
0.7488  & -0.9580
\end{array}\right].
\]
The final weights are marked in Figure~\ref{fig:wta_ex} with $\ast$.
\begin{figure}
\vspace{3in}
\hskip1.75in \special{eps:c:/bsb/wta_ex.eps y=3in}
\caption{Training patterns, initial weights and the final weights of the WTA network of Example~\ref{ex:wta_zur}.}
\label{fig:wta_ex}
\end{figure}
\end{example}\markex
\end{document}